第二章 算法

????????算法是解決特定問(wèn)題求解步驟的描述求冷，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列昨忆，并且每條指令表示一個(gè)火多個(gè)操作隧期。

2.1 開(kāi)場(chǎng)白

????????開(kāi)始增加難度

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

????????數(shù)據(jù)結(jié)構(gòu)中很多時(shí)候會(huì)講算法恰起。

????????在數(shù)據(jù)結(jié)構(gòu)中講到算法幌绍，是為何幫助理解好數(shù)據(jù)結(jié)構(gòu)颁褂，并不會(huì)詳細(xì)談及算法的方方面面。

2.3 兩種算法的比較

????????逐個(gè)累計(jì)算法

????????高斯計(jì)算1+2+...100的算法

2.4 算法定義

????????算法是描述解決問(wèn)題的方法傀广。

????????算法（Algorithm）這個(gè)單詞最早出現(xiàn)在波斯數(shù)學(xué)家阿勒.花剌子蜜在公園825年（相當(dāng)于我國(guó)的唐朝時(shí)期）所寫的《印度數(shù)字算術(shù)》中颁独。如今普遍認(rèn)可的對(duì)算法的定義是：

????????算法是解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列伪冰，并且每條指令表示一個(gè)或多個(gè)操作誓酒。

????????沒(méi)有通用的算法，就如同沒(méi)有包治百病的藥一樣。

????????現(xiàn)實(shí)世界中的問(wèn)題千奇百怪靠柑，算法也要千變?nèi)f化寨辩，沒(méi)有一個(gè)通用的算法可以解決所有的問(wèn)題。甚至解決一個(gè)小問(wèn)題歼冰，很優(yōu)秀的算法卻不一定適合靡狞。

????????為了解決某個(gè)或某類問(wèn)題，需要把指令表示成一定的操作序列隔嫡，操作序列包括一組操作甸怕，每一個(gè)操作都完成特定的功能，這就是算法了腮恩。

2.5 算法的特性

????????算法的五個(gè)基本特性：輸入蕾各、輸出、有窮性庆揪，確定性和可行性式曲。

2.5.1 輸入輸出

????????算法具有零個(gè)或多個(gè)輸入。算法至少有一個(gè)或多個(gè)輸出缸榛。

2.5.2 有窮性

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

2.5.3 確定性

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

????????相同的輸入只有唯一的輸出結(jié)果均澳。算法的每個(gè)步驟都被精確定義而無(wú)歧義恨溜。

2.5.4 可行性

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

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

????????算法不是唯一的。同一個(gè)問(wèn)題躺盛，可以有多重解決問(wèn)題的算法项戴。

2.6.1 正確性

????????正確性：算法的中卻行是只算法至少應(yīng)該具有輸入，輸出和加工處理無(wú)歧義性槽惫，能正確反映問(wèn)題的需求周叮，能夠得到問(wèn)題的正確答案。

????????算法的“正確”通常在用法上有很大的差別界斜，大體分為以下四個(gè)層次仿耽。

????????1.算法程序沒(méi)有語(yǔ)法錯(cuò)誤。

????????2.算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果各薇。

????????3.算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說(shuō)明的結(jié)果项贺。

????????4.算法程序?qū)τ陟o心選擇的，深圳刁難的測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果。

2.6.2 可讀性

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

????????可讀性高有助于人們理解算法，晦澀難懂的算法往往隱含錯(cuò)誤啥箭，不易被發(fā)現(xiàn)谍珊，并且難于調(diào)試和修改。

2.6.3 健壯性

????????健壯性急侥，當(dāng)輸入數(shù)據(jù)不合法時(shí)砌滞，算法也能做出相關(guān)處理，而不是產(chǎn)生異郴倒郑或莫名其妙的結(jié)果贝润。

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

????????最后，好的算法還應(yīng)該具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)铝宵。

????????時(shí)間效率值的是算法的執(zhí)行時(shí)間打掘，對(duì)于同一個(gè)問(wèn)題，如果有多個(gè)算法能夠解決鹏秋，執(zhí)行時(shí)間段的算法效率高尊蚁，執(zhí)行時(shí)間長(zhǎng)的效率低。

????????存儲(chǔ)量需求指的是算法在執(zhí)行過(guò)程中需要的最大存儲(chǔ)空間侣夷，朱啊喲是算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間横朋。

????????設(shè)計(jì)算法應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求。

????????總結(jié)：好的算法應(yīng)該就別正確性百拓，可讀性琴锭，健壯性，高效率和低存儲(chǔ)量的特點(diǎn)衙传。

2.7 算法效率的度量方法

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

????????事后統(tǒng)計(jì)方法：這種方法主要是通過(guò)設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)决帖，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低粪牲。

????????這種方法的缺陷：

????????必須依據(jù)算法事前編制好程序古瓤，這通常需要花費(fèi)大量的時(shí)間和精力。如果編制出來(lái)發(fā)現(xiàn)他根本是很糟糕的算法腺阳，不是竹籃打水一場(chǎng)空嗎？

????????時(shí)間的比較依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素穿香，有事會(huì)掩蓋算法本身的優(yōu)劣亭引。

????????算法的測(cè)試數(shù)據(jù)設(shè)計(jì)困難，并且程序的運(yùn)行時(shí)間往往還與測(cè)試數(shù)據(jù)的規(guī)模有很大關(guān)系皮获，效率高的算法在小測(cè)測(cè)試數(shù)據(jù)面前往往得不到體現(xiàn)焙蚓。比如10個(gè)數(shù)字的排序，們不管用干什么算法，差異幾乎是0.而如果一百萬(wàn)個(gè)隨機(jī)數(shù)字排序购公，那不同的算法差異就非常大了萌京。

????????基于事后統(tǒng)計(jì)方法有這樣那樣的缺陷，我們考慮不予采納宏浩。

2.7.2 事前分析估算方法

????????事前分析估算方法：在計(jì)算機(jī)程序編制前知残，一句統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。

????????高級(jí)語(yǔ)言編寫的程序在九三級(jí)上運(yùn)行時(shí)鎖小孩的時(shí)間取決于下列因素：

????????1.算法采用的策略比庄、方法

????????2.編譯產(chǎn)生的代碼質(zhì)量

????????3.問(wèn)題的輸入規(guī)模

????????4.機(jī)器執(zhí)行指令的速度求妹。

????????最終，在分析程序的運(yùn)行時(shí)間時(shí)佳窑，最重要的是吧程序看成獨(dú)立于程序設(shè)計(jì)語(yǔ)言的算法和一系列步驟制恍。

????????f(n) = n

????????f(n) = 1

????????f(n) = n^2

????????隨著n值的越來(lái)越大，它們?cè)跁r(shí)間效率上的差異也就越來(lái)越大神凑。

2.8 函數(shù)的漸進(jìn)增長(zhǎng)

????????輸入規(guī)模n在沒(méi)有限制的情況下净神，只要超過(guò)一個(gè)數(shù)值N，這個(gè)函數(shù)就總大于另一個(gè)函數(shù)溉委，我們稱函數(shù)是漸進(jìn)增長(zhǎng)的强挫。

????????函數(shù)的漸進(jìn)增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)證書(shū)N薛躬，是的對(duì)于所有的n>N,f(n)總是比g(n)大俯渤，那么，我們說(shuō)f(n)的增長(zhǎng)漸進(jìn)快于g(n).

????????因?yàn)殡S著n的增大型宝，加法常數(shù)其實(shí)是不影響做種的算法變化的八匠，所以我們可以忽略加法常數(shù)。

????????與最高次項(xiàng)相乘的常數(shù)也并不重要趴酣。

????????判斷一個(gè)算法的效率時(shí)梨树，函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略岖寞，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)抡四。

????????某個(gè)算法，隨著n的增大仗谆，它會(huì)越來(lái)越優(yōu)于另一算法指巡，或者越來(lái)越差于另一算法。這其實(shí)就是事前估算方法的理論依據(jù)隶垮，通過(guò)算法時(shí)間復(fù)雜度來(lái)估算算法時(shí)間效率藻雪。

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

2.9.1 算法時(shí)間復(fù)雜度定義

????????在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)狸吞。算法的時(shí)間復(fù)雜度勉耀，也就是算法的時(shí)間量度指煎，記作：T(n) = O(f(n))。它表示隨問(wèn)題規(guī)模n的增大便斥，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同至壤，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度枢纠。其中f(n)是sentiment規(guī)模n的某個(gè)函數(shù)像街。

????????用大寫O()來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法，我們稱之為大O記法京郑。

????????一般情況下宅广，隨著n的增大，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法些举。

????????顯然跟狱，由此算法時(shí)間復(fù)雜度的定義可知，我們的三個(gè)求和算法的時(shí)間復(fù)雜度分別為O(n),O(1),O(n^2)户魏。我們分別給他們?nèi)×艘粋€(gè)非官方的名稱驶臊，O(1)叫常數(shù)階，O(n)叫線性階叼丑，O(n^2)叫平方階关翎，當(dāng)然，還有其他的一些階鸠信，我們之后會(huì)介紹纵寝。

2.9.2 推導(dǎo)大O階的方法

????????1.用常數(shù)1取代運(yùn)行時(shí)間中所有的加法常數(shù)

????????2.在修改后的雨欣次數(shù)函數(shù)中，值保留最高階項(xiàng)星立。

????????3.如果最高階項(xiàng)存在不是1爽茴，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

????????得到的結(jié)果就是大O階绰垂。

????????似乎很簡(jiǎn)單室奏，但還要看看例子。

2.9.3 常數(shù)階

????????下面的這個(gè)算法劲装，也就是剛才的第二種算法（高斯算法）胧沫，為什么時(shí)間復(fù)雜度不是O(3)而是O(1)。

????????int sum = 0, n = 100;? /* 執(zhí)行一次 */

????????sum = (1+n)*n/2;? ? ? /* 執(zhí)行一次 */

????????printf("%d", sum);? ? /* 執(zhí)行一次 */

????????這個(gè)算法的運(yùn)行次數(shù)函數(shù)是f(n)=3占业。根究我們推導(dǎo)大O階的方法绒怨，第一步就是把常數(shù)項(xiàng)3改為1.在保留最高階項(xiàng)時(shí)發(fā)現(xiàn)，他根本沒(méi)有最高階項(xiàng)纺酸，所以這個(gè)算法的時(shí)間復(fù)雜度為O(1)窖逗。

????????無(wú)論n為多少，與問(wèn)題的大小無(wú)關(guān)餐蔬，執(zhí)行時(shí)間恒定的算法碎紊，我們稱之為具有O(1)的時(shí)間復(fù)雜度，又叫常數(shù)階樊诺。

????????注意：不管這個(gè)常數(shù)是多少仗考，我們都記作O(1)，而不能是O(3)词爬，O(12)等其他任何數(shù)字秃嗜，這是初學(xué)者常常犯的錯(cuò)誤。

????????對(duì)于分支結(jié)構(gòu)而言顿膨，無(wú)論是真锅锨，還是假，執(zhí)行的次數(shù)都是恒定的恋沃，不會(huì)隨著n的變大而發(fā)生變化，所以單純的分支結(jié)構(gòu)（不包含在循環(huán)結(jié)構(gòu)中），其時(shí)間復(fù)雜度也是O(1)冯乘。

2.9.4 線性階

????????線性階的循環(huán)結(jié)構(gòu)會(huì)復(fù)雜很多来涨。要確定某個(gè)算法的階次，我們常常需要確定某個(gè)特定詞語(yǔ)或某個(gè)語(yǔ)句集運(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)的程序步驟序列)*/

????????}

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

下面這段代碼的時(shí)間復(fù)雜度有事多少呢户辞？

????????int count = 1;

????????while(count < n)

????????{

? ? ????????count = count * 2;

????????}

????????由于每次count乘以2之后泌类，就距離n更近了一分。也就是說(shuō)底燎，有多少個(gè)2相乘后大于n刃榨，則會(huì)退出循環(huán)。由2x = n得到 x=log2n书蚪。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)喇澡。

2.9.6 平方階

????????下面的例子是一個(gè)循環(huán)嵌套，它的內(nèi)循環(huán)剛才我們已經(jīng)分析過(guò)殊校，時(shí)間復(fù)雜度為O(n)晴玖。

????????int i,j;

????????for(i = 0; i < n; i++)

????????{

? ? ????????for (j = 0; j < n; j++)

? ????????? {

? ? ? ????????? /* 時(shí)間復(fù)雜度為O(1) 的程序步驟序列 */

? ? ????????}

????????}

外層的循環(huán)，不過(guò)是內(nèi)部這個(gè)時(shí)間復(fù)雜度為O(n)的語(yǔ)句为流，再循環(huán)n次呕屎。所以這頓啊代碼的時(shí)間復(fù)雜度為O(n^2)。

如果外循環(huán)的次數(shù)改為了m敬察，時(shí)間復(fù)雜度就變?yōu)榱薕(mXn)秀睛。

????int i,j;

????for(i = 0; i < m; i++)

????{

? ? ? ? for (j = 0; j < n; j++)

? ????? {

? ? ? ? ????/* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */

? ????? }

????}

????????所以我們可以總結(jié)得出，循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以改循環(huán)運(yùn)行的次數(shù)莲祸。

? ? ? ? 那么下面這個(gè)循環(huán)嵌套蹂安，它的時(shí)間復(fù)雜度是多少呢椭迎？

????????int i,j;

????????for(i = 0; i <n; i++)

????????{

????????????for(j = i; j < n; j++)

????????????{

????????????????/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

????????????}

????????}

????????用我們推導(dǎo)大O階的方法，第一條田盈，沒(méi)有加法常數(shù)不予考慮畜号，第二條只保留最高階項(xiàng)，因此保留 n^2/2允瞧；第三條简软，去除這個(gè)項(xiàng)相乘的常數(shù)，也就是去除1/2述暂，最終這段代碼的時(shí)間復(fù)雜度為O(n^2)痹升。

????????理解大O推導(dǎo)不難，難的是對(duì)數(shù)列的醫(yī)學(xué)相關(guān)運(yùn)算畦韭，這更多的是考察你的數(shù)學(xué)知識(shí)能力疼蛾，如果想考研，要想在求算法時(shí)間復(fù)雜度這里不失分廊驼，可能需要強(qiáng)化你的數(shù)學(xué)据过，特別是數(shù)列方面的知識(shí)和解題能力。

????????我們繼續(xù)看例子妒挎，對(duì)于方法調(diào)用的時(shí)間復(fù)雜度又如何分析绳锅？

????????int i,j;

????????for(i = 0; i < n; i++)

????????{

? ? ????????function(i);

????????}

????????void function(int count)

????????{

? ????????? print(count);

????????}

函數(shù)體是打印這個(gè)參數(shù)。其實(shí)這很好理解酝掩，function函數(shù)的時(shí)機(jī)復(fù)雜度是O(1)鳞芙。所以整體的時(shí)間復(fù)雜度為O(n)。

假如function是下面扎樣的：

????????void function(int count)

????????{

????????? ? int j;

????????? ? for(j = count; j < n; j++)

????????? ? {

????????? ? ? ? /* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */

????????? ? }

????????}

事實(shí)上和剛才的例子是一樣的只不過(guò)把嵌套內(nèi)循環(huán)放到函數(shù)中期虾，所以最終的時(shí)間復(fù)雜度為O(n^2)

下面這段相對(duì)復(fù)雜的語(yǔ)句：

????????n++;

????????funciton(n);? ? /* 執(zhí)行次數(shù)為n */

????????int i,j;

????????for(i = 0; i < n; i++)

????????{

????????? ? function(i);

????????}

????????for(i = 0; i < n; i++)

????????{

????????? ? for(j = i; j < n; j++)

????????? ? {

? ? ? ? ????????/* 時(shí)間復(fù)雜度為O（1）的程序步驟序列 */

????????? ? }

????????}

2.10常見(jiàn)的時(shí)間復(fù)雜度

常見(jiàn)的時(shí)間復(fù)雜度如下表

????????常用的時(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)

????????我們前面已經(jīng)談到了O(1)常數(shù)階原朝，O(logn)對(duì)數(shù)階，O(n)線性階镶苞，O(n^2)平方階等喳坠，至于O(nlogn)我們將會(huì)在今后的課程中介紹，而像O(n^3)茂蚓，過(guò)大的n都會(huì)使得結(jié)果變得不現(xiàn)實(shí)壕鹉。同樣指數(shù)階O(2^n)和階乘階O(n!)等除非是很小的n值，否則哪怕n只是100聋涨，都是噩夢(mèng)般的運(yùn)行時(shí)間晾浴。所以這種不切實(shí)際的算法時(shí)間復(fù)雜度，一般我們都不去討論它牍白。

2.11 最壞情況與平均情況

????????最壞情況運(yùn)行時(shí)間是一種保證脊凰，那就是運(yùn)行時(shí)間將不會(huì)再壞了。在應(yīng)用中茂腥，這是一種最重要的需求狸涌，通常切省，除非特別指定，我們提到的運(yùn)行時(shí)間都是最壞情況的裕興時(shí)間杈抢。

????????平均時(shí)間是所有情況中最有意義的数尿，因?yàn)樗瞧谕倪\(yùn)行時(shí)間仑性。但現(xiàn)實(shí)惶楼，平均運(yùn)行時(shí)間很難通過(guò)分析得到，一般都是通過(guò)運(yùn)行一定數(shù)量的試驗(yàn)數(shù)據(jù)后估算出來(lái)的诊杆。

????????一般在沒(méi)有特殊說(shuō)明的情況下歼捐，都是指最壞時(shí)間復(fù)雜度。

2.12 算法空間復(fù)雜度

????????閏年計(jì)算晨汹，可以寫一個(gè)判斷閏年的算法豹储，也可以寫一個(gè)所有年份的列表，記錄哪一年是閏年淘这。

????????算法的空間復(fù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)剥扣，算法控件復(fù)雜度的計(jì)算公式記作：S(n) = O(f(n))，其中铝穷，n為問(wèn)題的規(guī)模钠怯，f(n)為語(yǔ)句相關(guān)于n所占存儲(chǔ)空間的函數(shù)。

????????一般情況下曙聂，一個(gè)程序在機(jī)器上執(zhí)行時(shí)晦炊，除了需要存儲(chǔ)程序本身的指令，常數(shù)宁脊，變量和輸入數(shù)據(jù)外断国，還需要存儲(chǔ)對(duì)數(shù)據(jù)操作的存儲(chǔ)單元。若輸入數(shù)據(jù)所占空間只取決于問(wèn)題本身榆苞，和算法無(wú)關(guān)稳衬，這樣只需要分析該算法在實(shí)現(xiàn)時(shí)所需的輔助單元即可。若算法執(zhí)行時(shí)所需的輔助空間相對(duì)于輸入數(shù)據(jù)而言是個(gè)常數(shù)坐漏，則稱此算法為原地工作薄疚，空間復(fù)雜度為O(1)。

????????通常仙畦，我們都使用“時(shí)間復(fù)雜度”來(lái)指運(yùn)行時(shí)間的需求输涕，使用“空間復(fù)雜度”指空間需求。當(dāng)不用限定詞地使用“復(fù)雜度”時(shí)慨畸，通常斗志時(shí)間復(fù)雜度莱坎。顯然我們本書(shū)的重點(diǎn)要講的還是算法的時(shí)間復(fù)雜度問(wèn)題。

2.13 總結(jié)回顧

????????算法的定義：算法是解決特定問(wèn)題求解步驟的描述寸士，在計(jì)算機(jī)中為指令的有限序列檐什，并且每條指令表示一個(gè)或多個(gè)操作碴卧。

????????算法的特性：有窮性，確定性乃正，可行性住册，輸入，輸出瓮具。

????????算法的設(shè)計(jì)要求：正確性荧飞，可讀性，健壯性名党，高效率和低存儲(chǔ)量需求叹阔。

????????算法特性與算法設(shè)計(jì)容易混需要對(duì)比記憶。

????????算法的度量方法：事后統(tǒng)計(jì)（不科學(xué)传睹，不準(zhǔn)確）耳幢，事前分析估算方法。

????????事前分析估算方法之前欧啤，我們先給出了函數(shù)漸進(jìn)增長(zhǎng)的定義睛藻。

????????函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N邢隧，使得對(duì)于所有的n>N,f(n)總是比g(n)大店印，那么我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)。于是我們可以得出一個(gè)結(jié)論府框，判斷一個(gè)算法好不好吱窝，我們止痛膏少量的數(shù)據(jù)是不能做出準(zhǔn)確判斷的，如果我們可以對(duì)比算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)漸近增長(zhǎng)性迫靖，基本就可以分析出：某個(gè)算法院峡，隨著n的變大，它會(huì)越來(lái)越優(yōu)于另一個(gè)算法系宜，或者越來(lái)越差于另一算法照激。

????????然后給出了算法時(shí)間復(fù)雜度的定義和推導(dǎo)大O階 的步驟。

推導(dǎo)大O階：

????????用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)

????????在修改后的運(yùn)行次數(shù)函數(shù)中盹牧，只保留最高階項(xiàng)俩垃。

????????如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)汰寓。

????????得到的結(jié)果就是大O階口柳。

????????推導(dǎo)很容易，但如何得到運(yùn)行次數(shù)的表達(dá)式卻是需要數(shù)學(xué)功底的有滑。

????????常見(jiàn)時(shí)間復(fù)雜度所耗時(shí)間的大小排列：

????????O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)<O(n^n)

????????給出類關(guān)于算法最壞情況和平均情況的概念跃闹，以及空間復(fù)雜度的概念。

2.14 結(jié)尾語(yǔ)

????????學(xué)計(jì)算機(jī)專業(yè)，做了很長(zhǎng)時(shí)間的工作望艺，終于明白了算法時(shí)間復(fù)雜度的估算苛秕。可以通過(guò)優(yōu)化讓計(jì)算機(jī)更快更高效的找默。

????????好好利用算法分析工具艇劫，改進(jìn)代碼，讓計(jì)算機(jī)輕松一點(diǎn)惩激，自己也可以更加勝人一籌店煞。