目錄

• 申明
• 1. 數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系
• 2. 兩種算法的比較
• 3. 算法定義
• 4. 算法的特性
• • 4.1 輸入輸出
  • 4.2 有窮性
  • 4.3 確定性
  • 4.4 可行性
• 5. 算法的設(shè)計(jì)要求
• • 5.1 正確性
  • 5.2 可讀性
  • 5.3 健壯性
  • 5.4 時(shí)間效率高和存儲(chǔ)量低
• 6. 算法效率的度量方法
• • 6.1 事后統(tǒng)計(jì)法
  • 6.2 事前分析估算法
• 7. 函數(shù)的逐漸增長(zhǎng)
• 8. 算法時(shí)間復(fù)雜度
• • 8.1 算法時(shí)間復(fù)雜度定義
  • 8.2 推導(dǎo)大O階方法
  • 8.3 常數(shù)階
  • 8.4 線性階
  • 8.5 對(duì)數(shù)階
  • 8.6 平方階
• 9. 常見的時(shí)間復(fù)雜度
• 10. 最壞情況與平均情況
• 11. 算法空間復(fù)雜度
• 12. 總結(jié)回顧
• 13. 專欄知識(shí)鏈接

申明

??本文章屬于原創(chuàng)，其中參考了程杰老師《大話數(shù)據(jù)結(jié)構(gòu)》行文結(jié)構(gòu)和內(nèi)容，侵刪。

1. 數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系

??數(shù)據(jù)結(jié)構(gòu)和算法實(shí)際上是相輔相成的關(guān)系，只談數(shù)據(jù)結(jié)構(gòu)的話，其實(shí)可以在很短的時(shí)間內(nèi)介紹完，但是我們會(huì)不知道這些數(shù)據(jù)結(jié)構(gòu)到底有何用處。在本專題談到的算法，是為了更好的理解數(shù)據(jù)結(jié)構(gòu)，并不會(huì)講到算法的方方面面。

2. 兩種算法的比較

??如果讓你寫一個(gè)從1加到100度求和程序，你應(yīng)該如何實(shí)現(xiàn)？下面這段代碼可能是大多數(shù)人的思路：

int i, sum = 0, n = 100; for (i = 1; i <= n; ++i) {sum = sum + i; } printf("sum result %d", sum);

??然而這樣實(shí)現(xiàn)是否真的高效呢？其實(shí)用高斯公式可以這樣實(shí)現(xiàn)：

int sum = 0, n = 100; sum = (1 + 100) * n / 2; printf("sum result %d", sum);

??可能你在計(jì)算機(jī)上運(yùn)行了上面兩種程序，發(fā)現(xiàn)并沒有區(qū)別，但是如果將求和的范圍擴(kuò)大到一千、一億呢？

3. 算法定義

??如今普遍認(rèn)可的算法定義是：算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

4. 算法的特性

4.1 輸入輸出

??**算法具有零個(gè)或多個(gè)輸入，至少有一個(gè)或者多個(gè)輸出。**輸出的形式可以是打印輸出，也可以是返回一個(gè)或多個(gè)值等。

4.2 有窮性

??有窮性：指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可以接受的時(shí)間內(nèi)完成。

4.3 確定性

??確定性：算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。

4.4 可行性

??可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。

5. 算法的設(shè)計(jì)要求

5.1 正確性

??正確性：算法的正確性是指算法至少應(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é)果。
??層次4幾乎不能用逐一驗(yàn)證的方法來驗(yàn)證所有的輸入都能得到正確的結(jié)果，因此算法的正確性大部分情況下都不可能用程序來證明，而是用數(shù)學(xué)方法來證明。證明一個(gè)復(fù)雜算法在所有層次上都是正確的，代價(jià)非常昂貴。所以一般情況下，我們把層次3作為一個(gè)算法是否正確的標(biāo)準(zhǔn)。

5.2 可讀性

??可讀性：算法設(shè)計(jì)的另一個(gè)目的是為了便于閱讀、理解和交流。

5.3 健壯性

??一個(gè)好的算法應(yīng)該能對(duì)輸入數(shù)據(jù)不合法的情況做合適的處理。比如輸入的時(shí)間或者距離不應(yīng)該是負(fù)數(shù)等。
??健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異常或者莫名其妙的結(jié)果。

5.4 時(shí)間效率高和存儲(chǔ)量低

??時(shí)間效率指的是算法的執(zhí)行時(shí)間，對(duì)于同一問題，如果有多個(gè)算法能夠解決，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長(zhǎng)的效率低。存儲(chǔ)量需求指的是算法在執(zhí)行過程中需要的最大存儲(chǔ)空間，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或者外部硬盤存儲(chǔ)空間。設(shè)計(jì)算法應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求。

6. 算法效率的度量方法

6.1 事后統(tǒng)計(jì)法

??事后統(tǒng)計(jì)法：這種方法主要是通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序等運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低。
??但是這種方法顯然有很大的缺陷：它受計(jì)算機(jī)軟硬件等環(huán)境因素的影響，同時(shí)測(cè)試數(shù)據(jù)設(shè)計(jì)困難，并且程序的運(yùn)行時(shí)間還與測(cè)試數(shù)據(jù)的規(guī)模有很大的關(guān)系，效率高的算法在小的測(cè)試數(shù)據(jù)面前往往得不到體現(xiàn)。
??所以基于時(shí)候統(tǒng)計(jì)法有這樣那樣的缺陷，我們考慮不予采納。

6.2 事前分析估算法

??事前分析估算法：在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。
??一個(gè)用高級(jí)程序語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：
??1.算法采用的策略、方法。
??2.編譯產(chǎn)生的代碼質(zhì)量。
??3.問題的輸入規(guī)模。
??4.機(jī)器執(zhí)行指令的速度。
??第1條當(dāng)然是算法好壞的根本，第2條需要由軟件來支持，第4條要看硬件性能。也就是說，拋開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，一個(gè)程序的運(yùn)行時(shí)間，依賴于算法的好壞和問題的輸入規(guī)模。所謂問題的輸入規(guī)模是指輸入量的多少。
??還是來看兩種求和算法的例子：
??第一種算法：

int i, sum = 0, n = 100; /* 執(zhí)行1次 */ for (i = 1; i <= n; ++i) /* 執(zhí)行了n+1次 */ {sum = sum + i; /* 執(zhí)行n次 */ } printf("sum result %d", sum); /* 執(zhí)行1次 */

??第二種算法：

int sum = 0, n = 100; /* 執(zhí)行1次 */ sum = (1 + 100) * n / 2; /* 執(zhí)行1次 */ printf("sum result %d", sum); /* 執(zhí)行1次 */

??顯然，第一種算法執(zhí)行了1+（n+1）+n+1次=2n+3次；第二種算法執(zhí)行了1+1+1=3次。事實(shí)上兩種算法第一條和最后一條語句是一樣的，所以我們關(guān)注的代碼其實(shí)是中間那部分，我們把循環(huán)看作一個(gè)整體，忽略頭尾循環(huán)的判斷開銷，那么這兩個(gè)算法就是n次與1次的差距，好壞顯而易見。
??在分析程序的運(yùn)行時(shí)間時(shí)，最重要的是把程序看成是獨(dú)立于程序設(shè)計(jì)語言的算法或一系列步驟。

7. 函數(shù)的逐漸增長(zhǎng)

次數(shù)算法A(2n+3)算法A’(2n)算法B(3n+1)算法B’(3n)

n = 1	5	2	4	3
n = 2	7	4	7	6
n = 3	9	6	10	9
n = 10	23	20	31	30
n = 100	203	200	301	300

??通過觀察表格我們得出這樣的定義，輸入規(guī)模n在沒有限制的情況下，只要超過一個(gè)數(shù)值N，這個(gè)函數(shù)就總是大于另一個(gè)函數(shù)，我們稱函數(shù)是漸近增長(zhǎng)的。
??函數(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)。
??從中我們發(fā)現(xiàn)，隨著n的增大，后面的+3還是+1其實(shí)是不影響最終的算法變化的，所以我們可以忽略這些加法常數(shù)。實(shí)際上通過上述表格舉一反三，最終判斷一個(gè)算法的效率時(shí)，函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略，而更應(yīng)該關(guān)注主項(xiàng)(最高階項(xiàng))的階數(shù)。
??**某個(gè)算法，隨著n的增大，它會(huì)越來越優(yōu)于另一算法，或者越來越差于另一算法。**這其實(shí)就是事前估算法的理論依據(jù)，通過算法時(shí)間復(fù)雜度來估算算法時(shí)間效率。

8. 算法時(shí)間復(fù)雜度

8.1 算法時(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(n2)叫平方階。

8.2 推導(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階。

8.3 常數(shù)階

??如果不存在循環(huán)體，那么根據(jù)大O階大推導(dǎo)方法，不管這個(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)。

8.4 線性階

??線性階的循環(huán)結(jié)構(gòu)會(huì)復(fù)雜很多。要確定某個(gè)算法的階次，我們常常需要確定某個(gè)特定語句或者語句集運(yùn)行的次數(shù)。因此，我們要分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況。
??下面這段代碼，它的循環(huán)的時(shí)間復(fù)雜度為O(n)，因?yàn)檠h(huán)體中的代碼要執(zhí)行n次。

int i; for（i = 0; i < n; i++） {/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */ }

8.5 對(duì)數(shù)階

int count = 1; while count < n） {count = count * 2;/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */ }

??由于每次count乘以2之后，就距離n更近了一分。也就是說，有多少個(gè)2相乘后大于n，則會(huì)退出循環(huán)。由2^n 得到x=log_2?n(以2為底n的對(duì)數(shù))。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)。

8.6 平方階

??下面這個(gè)例子是一個(gè)嵌套循環(huán)，外層循環(huán)次數(shù)改為了m，時(shí)間復(fù)雜度為O(m*n)。

int i,j; for（i = 0; i < m; i++） {for（j = 0; j < n; j++） { /* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */} }

9. 常見的時(shí)間復(fù)雜度

??常見時(shí)間復(fù)雜度如下表：

??注意，經(jīng)常將log2n（以2為底的對(duì)數(shù)）簡(jiǎn)寫成logn
??常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

10. 最壞情況與平均情況

??我們查找一個(gè)有n個(gè)隨機(jī)數(shù)字?jǐn)?shù)組中的某個(gè)數(shù)字，最好的情況是第一個(gè)數(shù)字就是，那么算法的時(shí)間復(fù)雜度為O(1)，但是也有可能這個(gè)數(shù)字在最后，那么算法的時(shí)間復(fù)雜度就是O(n)，這是最壞的一種情況了。
??最壞情況運(yùn)行時(shí)間是一種保證，那就是運(yùn)行時(shí)間將不會(huì)再壞了。在應(yīng)用中，這是一種最重要的需求，通常，除非特別指定，我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間。
??而平均運(yùn)行時(shí)間也就是從概率的角度看，這個(gè)數(shù)字在每一個(gè)位置的可能性是相同的，所以平均的查找時(shí)間為n/2次后發(fā)現(xiàn)這個(gè)目標(biāo)元素。
??**平均運(yùn)行時(shí)間是所有情況中最有意義的，因?yàn)樗瞧谕倪\(yùn)行時(shí)間。**可現(xiàn)實(shí)中，平均分析時(shí)間很難通過分析得到，一般都是通過運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來的。
??對(duì)算法的分析，一種方法是計(jì)算所有情況的平均值，這種時(shí)間復(fù)雜度的計(jì)算方法稱為平均時(shí)間復(fù)雜度。另一種方法是計(jì)算最壞情況下的時(shí)間復(fù)雜度，這種方法稱為最壞時(shí)間復(fù)雜度。一般在沒有特殊說明的情況下，都是指最壞時(shí)間復(fù)雜度。

11. 算法空間復(fù)雜度

??算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法空間復(fù)雜度的計(jì)算公式記作：S(n) = O(f(n))，其中，n為問題的規(guī)模，f(n)為語句關(guān)于n所占存儲(chǔ)空間的函數(shù)。
??一般情況下，一個(gè)程序在機(jī)器上執(zhí)行時(shí)，除了需要存儲(chǔ)程序本身的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要存儲(chǔ)對(duì)數(shù)據(jù)操作的存儲(chǔ)單元。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，這樣只需要分析該算法在實(shí)現(xiàn)時(shí)所需的輔助單元即可。若算法執(zhí)行時(shí)所需的輔助空間相對(duì)于輸入數(shù)據(jù)量而言是個(gè)常數(shù)，則稱此算法為原地工作，空間復(fù)雜度為O(1)。
??通常，我們都使用“時(shí)間復(fù)雜度”來指運(yùn)行時(shí)間的需求，使用“空間復(fù)雜度”指空間需求。當(dāng)不用限定詞地使用“復(fù)雜度”時(shí)，通常都是指時(shí)間復(fù)雜度。

12. 總結(jié)回顧

??算法的定義：算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。
??算法的特性：有窮性、確定性、可行性、輸入、輸出。
??算法的設(shè)計(jì)要求：正確性、可讀性、健壯性、高效率和低存儲(chǔ)量需求。
??算法特性和算法設(shè)計(jì)容易混，需要對(duì)比記憶。
??算法的度量方法：事后統(tǒng)計(jì)方法（不科學(xué)、不準(zhǔn)確）、事前分析估算方法。
??推導(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階。
??常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

13. 專欄知識(shí)鏈接

1. 數(shù)據(jù)結(jié)構(gòu)緒論
2. 線性表詳解(靜態(tài)鏈表、單鏈表、雙向鏈表、循環(huán)鏈表)

總結(jié)

以上是生活随笔為你收集整理的算法绪论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。