算法
算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列焕数，并且每條指令表示一個(gè)或多個(gè)操作
1. 數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系
數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)與數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系（數(shù)組泽疆、隊(duì)列要门、樹榜晦、圖等結(jié)構(gòu)）
算法：解決問題的步驟
數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系：數(shù)據(jù)結(jié)構(gòu)是底層冠蒋，算法高層。數(shù)據(jù)結(jié)構(gòu)為算法提供服務(wù)乾胶。算法圍繞數(shù)據(jù)結(jié)構(gòu)操作抖剿。
2. 算法定義
什么是算法呢？算法是描述解決問題的方法识窿。算法（Algorithm）這個(gè)單詞最早出現(xiàn)在波斯數(shù)學(xué)家阿勒·花刺子密在公元825年（相當(dāng)于我們中國的唐朝時(shí)期）所寫的《印度數(shù)字算術(shù)》中斩郎。如今普遍認(rèn)可的對(duì)算法的定義是：算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列腕扶，并且每條指令表示一個(gè)或多個(gè)操作。
算法定義中吨掌，提到了指令半抱，指令能被人或機(jī)器等計(jì)算裝置執(zhí)行脓恕。它可以是計(jì)算機(jī)指令，也可以是我們平時(shí)的語言文字窿侈。
為了解決某個(gè)或某類問題炼幔，需要把指令表示成一定的操作序列，操作序列包括一組操作史简，每一個(gè)操作都完成特定的功能乃秀，這就是算法了。
3. 算法的特性
算法具有五個(gè)基本特性：輸入圆兵、輸出跺讯、有窮性、確定性和可行性殉农。
- 輸入輸出
算法的輸入可以是零個(gè)刀脏，算法至少有一個(gè)或多個(gè)輸出。 - 有窮性
算法在執(zhí)行有限的步驟之后超凳，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)愈污，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成 - 確定性
算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性轮傍。算法在一定條件下暂雹，只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結(jié)果创夜。算法的每個(gè)步驟被精確定義而無歧義杭跪。 - 可行性
算法的每一步都必須是可行的，也就是說挥下，每一步都能夠通過執(zhí)行有限次數(shù)完成揍魂。可行性意味著算法可以轉(zhuǎn)換為程序上機(jī)運(yùn)行棚瘟，并得到正確的結(jié)果
4. 算法設(shè)計(jì)的要求
正確性 可讀性 健壯性 時(shí)間效率高和存儲(chǔ)量低
正確性
算法的正確性是指算法至少應(yīng)該具有輸入现斋、輸出和加工處理無歧義性、能正確反映問題的需求偎蘸、能夠得到問題的正確答案庄蹋。
但是算法的“正確”通常在用法上有很大的差別，大體分為以下四個(gè)層次迷雪。
1 算法程序沒有語法錯(cuò)誤限书。
2 算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果。
3.算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果章咧。
4.算法程序?qū)τ诰倪x擇的倦西，甚至刁難的測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果。
對(duì)于這四層含義赁严，層次1要求最低扰柠，但是僅僅沒有語法錯(cuò)誤實(shí)在談不上是好算法粉铐。這就如同僅僅解決溫飽，不能算是生活幸福一樣卤档。而層次4是最困難的蝙泼，我們幾乎不可能逐一驗(yàn)證所有的輸入都得到正確的結(jié)果。
因此算法的正確性在大部分情況下都不可能用程序來證明劝枣，而是用數(shù)學(xué)方法證明的汤踏。證明一個(gè)復(fù)雜算法在所有層次上都是正確的，代價(jià)非常昂貴舔腾。所以一般情況下溪胶，我們把層次3作為一個(gè)算法是否正確的標(biāo)準(zhǔn)。可讀性
算法設(shè)計(jì)的另一目的是為了便于閱讀琢唾、理解和交流载荔。
可讀性高有助于人們理解算法，晦澀難懂的算法往往隱含錯(cuò)誤采桃，不易被發(fā)現(xiàn)懒熙，并且難于調(diào)試和修改。健壯性
當(dāng)輸入數(shù)據(jù)不合法時(shí)普办，算法也能做出相關(guān)處理工扎，而不是產(chǎn)生異常或莫名其妙的結(jié)果衔蹲。
一個(gè)好的算法還應(yīng)該能對(duì)輸入數(shù)據(jù)不合法的情況做合適的處理肢娘。比如輸入的時(shí)間或者距離不應(yīng)該是負(fù)數(shù)等。時(shí)間效率高和存儲(chǔ)量低
時(shí)間效率指的是算法的執(zhí)行時(shí)間舆驶，對(duì)于同一個(gè)問題橱健，如果有多個(gè)算法能夠解決，執(zhí)行時(shí)間短的算法效率高沙廉，執(zhí)行時(shí)間長(zhǎng)的效率低拘荡。
存儲(chǔ)量需求指的是算法在執(zhí)行過程中需要的最大存儲(chǔ)空間，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間撬陵。設(shè)計(jì)算法應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求
比如在生活中珊皿，人們都希望花最少的錢，用最短的時(shí)間巨税，辦最大的事蟋定，算法也是一樣的思想，最好用最少的存儲(chǔ)空間草添，花最少的時(shí)間驶兜，辦成同樣的事就是好的算法。
5.算法效率的度量方法
事后統(tǒng)計(jì)方法 事前分析估算方法
-
事后統(tǒng)計(jì)方法
通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較抄淑，從而確定算法效率的高低犀盟。
**缺陷: **- 必須依據(jù)算法事先編制好程序，這通常需要花費(fèi)大量的時(shí)間和精力蝇狼。
- 時(shí)間的比較依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素，有時(shí)會(huì)掩蓋算法本身的優(yōu)劣倡怎。
- 算法的測(cè)試數(shù)據(jù)設(shè)計(jì)困難迅耘，并且程序的運(yùn)行時(shí)間往往還與測(cè)試數(shù)據(jù)的規(guī)模有很大關(guān)系，效率高的算法在小的測(cè)試數(shù)據(jù)面前往往得不到體現(xiàn)监署。
-
事前分析估算方法
在計(jì)算機(jī)程序編制前颤专，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。
一個(gè)用高級(jí)程序語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素:- 算法采用的策略钠乏、方法栖秕。
- 編譯產(chǎn)生的代碼質(zhì)量。
- 問題的輸入規(guī)模晓避。
- 機(jī)器執(zhí)行指令的速度簇捍。
第1條當(dāng)然是算法好壞的根本，第2條要由軟件來支持俏拱，第4條要看硬件性能暑塑。拋開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素锅必，一個(gè)程序的運(yùn)行時(shí)間事格，依賴于算法的好壞和問題的輸入規(guī)模。所謂問題輸入規(guī)模是指輸入量的多少搞隐。
在分析一個(gè)算法的運(yùn)行時(shí)間時(shí)驹愚，重要的是把基本操作的數(shù)量與輸入規(guī)模關(guān)聯(lián)起來，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)
6. 算法時(shí)間復(fù)雜度
算法時(shí)間復(fù)雜度定義
在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)味廊，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)蒸甜。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度余佛，記作：T(n)=O(f(n))柠新。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同辉巡，稱作算法的漸近時(shí)間復(fù)雜度恨憎，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。
這樣用大寫O( )來體現(xiàn)算法時(shí)間復(fù)雜度的記法憔恳，我們稱之為大O記法瓤荔。
一般情況下，隨著n的增大钥组，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法输硝。
O(1)叫常數(shù)階、O(n)叫線性階程梦、O(n 2)叫平方階
- 叫常數(shù)階
//實(shí)例1
int sum = 0,n = 100; /* 執(zhí)行一次 */
sum = (1 + n) * n / 2; /* 執(zhí)行一次 */
printf("%d", sum); /* 執(zhí)行一次 */
//實(shí)例2
int sum = 0, n = 100; /* 執(zhí)行1次 */
sum = (1 + n) * n / 2; /* 執(zhí)行第1次 */
sum = (1 + n) * n / 2; /* 執(zhí)行第2次 */
sum = (1 + n) * n / 2; /* 執(zhí)行第3次 */
sum = (1 + n) * n / 2; /* 執(zhí)行第4次 */
sum = (1 + n) * n / 2; /* 執(zhí)行第5次 */
printf("%d", sum); /* 執(zhí)行1次 */
無論n為多少点把，執(zhí)行時(shí)間恒定的算法，我們稱之為具有O(1)的時(shí)間復(fù)雜度屿附，又叫常數(shù)階郎逃。
注意：不管這個(gè)常數(shù)是多少，我們都記作O(1)挺份，而不能是O(3)褒翰、O(12)等其他任何數(shù)字，這是初學(xué)者常常犯的錯(cuò)誤匀泊。
對(duì)于分支結(jié)構(gòu)而言优训，無論是真，還是假各聘，執(zhí)行的次數(shù)都是恒定的型宙，不會(huì)隨著n的變大而發(fā)生變化，所以單純的分支結(jié)構(gòu)（不包含在循環(huán)結(jié)構(gòu)中）伦吠，其時(shí)間復(fù)雜度也是O(1)妆兑。
- 線性階O(n)
線性階的循環(huán)結(jié)構(gòu)會(huì)復(fù)雜很多。要確定某個(gè)算法的階次毛仪，我們常常需要確定某個(gè)特定語句或某個(gè)語句集運(yùn)行的次數(shù)秉沼。
分析算法的復(fù)雜度带膀，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況滑频。
int i;
for (i = 0; i < n; i++){
/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */
}
//它的循環(huán)的時(shí)間復(fù)雜度為O(n)著拭，因?yàn)檠h(huán)體中的代碼須要執(zhí)行n次。
- 對(duì)數(shù)階O(logn)
int count = 1;
while (count < n){
count = count * 2;
/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */
}
由于每次count乘以2之后衡怀，就距離n更近了一分棍矛。也就是說，有多少個(gè)2相乘后大于n抛杨，則會(huì)退出循環(huán)够委。由2 x=n得到x=log 2 n。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)怖现。
4.平方階O(m×n)
int i, j;
for (i = 0; i < n; i++){
for (j = 0; j < n; j++) {
/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */
}
}
內(nèi)循環(huán)剛才我們已經(jīng)分析過茁帽，時(shí)間復(fù)雜度為O(n)玉罐。而對(duì)于外層的循環(huán)，不過是內(nèi)部這個(gè)時(shí)間復(fù)雜度為O(n)的語句潘拨，再循環(huán)n次吊输。所以這段代碼的時(shí)間復(fù)雜度為O(n 2 )。
所以可以總結(jié)得出铁追，循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)季蚂。
推導(dǎo)大O階方法
推導(dǎo)大O階：
1．用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2．在修改后的運(yùn)行次數(shù)函數(shù)中琅束，只保留最高階項(xiàng)癣蟋。
3．如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)狰闪。
得到的結(jié)果就是大O階。
7.常見的時(shí)間復(fù)雜度
執(zhí)行次數(shù) 函數(shù)階 非正式術(shù)語
- O(1) 常數(shù)階2n+3
- O(n) 線性階3n 2 +2n+1
- O(n 2 ) 平方階5log 2 n+20
- O(logn) 對(duì)數(shù)階2n+3nlog 2 n+19
- O(nlogn) nlogn階6n 3 +2n 2 +3n+4
- O(n 3 ) 立方階2 n
- O(2 n ) 指數(shù)階
常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n 2 ) < O(n 3 ) < O(2 n ) < O(n!)<O(n n )
8. 總結(jié)回顧
算法的定義：算法是解決特定問題求解步驟的描述濒生，在計(jì)算機(jī)中為指令的有限序列埋泵，并且每條指令表示一個(gè)或多個(gè)操作。
算法的特性：有窮性罪治、確定性丽声、可行性、輸入觉义、輸出雁社。
算法的設(shè)計(jì)的要求：正確性、可讀性晒骇、健壯性霉撵、高效率和低存儲(chǔ)量需求。
算法的度量方法：事后統(tǒng)計(jì)方法（不科學(xué)洪囤、不準(zhǔn)確）徒坡、事前分析估算方法。
函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)瘤缩，如果存在一個(gè)整數(shù)N喇完，使得對(duì)于所有的n>N，f(n)總是比g(n)大剥啤，那么锦溪，我們說f(n)的增長(zhǎng)漸近快于g(n)。于是我們可以得出一個(gè)結(jié)論府怯，判斷一個(gè)算法好不好刻诊，我們只通過少量的數(shù)據(jù)是不能做出準(zhǔn)確判斷的，如果我們可以對(duì)比算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)的漸近增長(zhǎng)性牺丙，基本就可以分析出：某個(gè)算法坏逢，隨著n的變大，它會(huì)越來越優(yōu)于另一算法，或者越來越差于另一算法是整。
推導(dǎo)大O階：用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)肖揣。在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)浮入。如果最高階項(xiàng)存在且不是1龙优，則去除與這個(gè)項(xiàng)相乘的常數(shù)。
常見的時(shí)間復(fù)雜度所耗時(shí)間的大小排列：O(1)<O(logn)<O(n)<O(nlogn)<O(n 2 )<O(n 3 )<O(2 n )<O(n!)<O(n n )
