目錄TOC\o"1-2"\h\u319081章數(shù)據(jù)結(jié)構(gòu)為何重要 4295251.1 5203711.2 1727781.3 20302562章算法為何重要 21299813章大O記法 32113243.1大O 32182033.2 34250793.3 3626683.4 37132213.5 38264003.6解釋O(logN 39149593.7 40178403.8 42269004章運(yùn)用大O來給代碼提速 43290254.1 43315514.2 44181174.3 50298284.4 5259524.5 54215854.6 56291164.7 5836695章用或不用大O來優(yōu)化代碼 59168775.1 5949055.2 607315.3 66213155.4 68262475.5 69139425.6大O 7091885.7 7252695.8 73259886章樂觀地調(diào)優(yōu) 74245516.1 74262676.2 75308706.3 81310586.4 8362086.5 86185626.6 89325856.7 91307827章查找迅速的散列表 9265737.1 9291917.2 93162177.3 94280547.4 9852067.5 101128327.6 103284957.7 107199788章用棧和隊(duì)列來構(gòu)造靈巧的代碼 10884998.1 1087908.2 11038478.3 117192888.4 119223068.5 12135849章遞歸 1221776510章飛快的遞歸算法 134285710.1 1341387910.2 1391624110.3 1451798810.4 1481771710.5 1512389110.6 1541038911章基于結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) 1552167911.1 155324611.2 1571586411.3 1591323911.4 1601365211.5 1611865211.6 1641698711.7 16751911.8 168952511.9 172845312章讓一切操作都更快的二叉樹 173658712.1 1732217112.2 1761040112.3 1802446312.4 184792212.5 1931297912.6 1951801913章連接萬物的圖 196420013.1 196340213.2 199185713.3 21082513.4 2152423013.5Dijkstra 2183060913.6 226810514章對付空間限制 2271268014.1描述空間復(fù)雜度的大O 2273005914.2 2301368014.3 2321章數(shù)據(jù)結(jié)構(gòu)為何重要字和字符串。在經(jīng)典的“HelloWorld!”這個(gè)簡單程序中，字符串"Helloxx=y="Howarez="today?"printx+y+zarrayarray=["apples","bananas","cucumbers","dates",在大多數(shù)的編程語言中，索引是從0一般數(shù)據(jù)結(jié)構(gòu)都有以下4（或者說用法）例如，檢查"dates是否存在于食品清單之中，給出其對應(yīng)的索加一個(gè)格子并填入一個(gè)值。例如，往購物清單中多加一項(xiàng)A操作要5步，B操作要500事不宜遲，我們現(xiàn)在就來探索上述4在["apples","bananas","cucumbers","dates",直接跳到索引2，并告訴你那里有"cucumbers。數(shù)組的索引從0該數(shù)組的索引從0算起，其開頭的內(nèi)存地址為1010索引3在索引0后的第3于是索引3的內(nèi)存地址為1013，因?yàn)?01031013但索引2這種逐個(gè)格子去檢查的做法，就是最基本的查找方法——以此類推，一個(gè)格的數(shù)組，其線性查找的最多步數(shù)是（可以是任假設(shè)我們想要在購物清單的末尾插入"figs。那么只需一步。因?yàn)橹?，因?yàn)槲覀兪紫纫獙?elderberries右移一格，以空出位置于是，一個(gè)含有個(gè)元素的數(shù)組，其插入數(shù)據(jù)的最壞情況會(huì)花費(fèi)步。即插入在數(shù)組開頭，導(dǎo)致次移動(dòng)，加上一次插入。雖然刪除"cucumbers好像一步就搞定了，但這帶來了新的問題：數(shù)得把"dates和"elderberries往左移。允許空元素，當(dāng)索引0對于含有5個(gè)元素的數(shù)組，刪除第一個(gè)元素需要1的元素需要499步?？梢酝瞥觯瑢τ诤袀€(gè)元素的數(shù)組，刪除操作最多需要步。下一個(gè)要介紹的數(shù)據(jù)結(jié)構(gòu)是集合，它跟數(shù)組似乎很像，甚至讓人以為要是你想往集合["a""b""c"再插入一個(gè)"b，計(jì)算機(jī)是不會(huì)允許的，因?yàn)榧现幸呀?jīng)有"b了。也導(dǎo)致它在4種基本操作中有1集合的查找也跟數(shù)組的查找無異，需要步去檢查某個(gè)值在不在集合當(dāng)中。刪除也是，總共需要步去刪除和左移填空?！?yàn)檫@就買重復(fù)的東西。如果當(dāng)前集合是["apples","bananas","cucumbers""dates""elderberries"，然后想插入"figs，第2步：檢查索引1第3步：檢查索引2第4步：檢查索引3第5步：檢查索引4換句話說，在個(gè)元素的集合中進(jìn)行插入的最好情況需要步——步去確認(rèn)被插入的值不在集合中，加上最后插入的1步。最壞的情況則是在集合的開頭插入，這時(shí)計(jì)算機(jī)得檢查個(gè)格子以保證集合不包含那個(gè)值，然后用步來把所有值右移，最后再用1步來插入新值?？偣膊?。2章算法為何重要（你猜對了）。即每次插入新值時(shí)，它會(huì)被插入到以數(shù)組[3,17,80,202為例。如上一章所述，計(jì)算機(jī)只要17575第1步：檢查索引0的值，看75第2第4第5第6步：終于可以把75defdeflinear_search(array,#array.eachdo##ifelement==valuereturnvalue#elsifelement>value#returnnil你應(yīng)該憑直覺就知道這個(gè)游戲的策略。一開始你會(huì)先猜處于中間的75之后我告訴你要小一點(diǎn)，你就會(huì)選62或63。下面來演示這個(gè)過程，但僅以1到10然后，用二分查找來找出7它的值為4，那么7就在它的右邊了。由此4第3步：還剩兩個(gè)格子里可能有7defdefbinary_search(array,##lower_bound=upper_bound=array.length-#whilelower_bound<=upper_bounddo#如此找出最中間的格子之索引#（無須擔(dān)心商是不是整數(shù)，因?yàn)镽uby總是把兩個(gè)整數(shù)相除所得的小數(shù)部分去掉midpoint=(upper_bound+lower_bound)/2#獲取該中間格子的值value_at_midpoint=##ifvalue<value_at_midpointupper_bound=midpoint-elsifvalue>value_at_midpointlower_bound=midpoint+1elsifvalue==value_at_midpointreturnmidpoint#returnnil線性查找：100步二分查找：7步長度為3的有序數(shù)組，二分查找所需的最多步數(shù)是2若再翻倍（并加1），變成15個(gè)元素，那么最多步數(shù)會(huì)是4規(guī)律就是，每次有序數(shù)組長度乘以21步，100個(gè)元素就最多要100加1如果數(shù)組變得更大，比如說10000個(gè)元素，那么線性查找最多會(huì)有10000步，而二分查找最多只有14步。再增大到1000000個(gè)元素，則線性查找最多有1000000步，二分查找最多只有203章大O記法量化線性查找效率的更準(zhǔn)確的方式應(yīng)該是：對于具有個(gè)元素的數(shù)組，線性查找最多需要步。當(dāng)然，這聽起來很啰唆。鑒了一種簡潔又通用的方式，那就是大記法。這種規(guī)范化語言使得掌握了大記法，就掌握了算法分析的專業(yè)工具雖說大記法源于數(shù)學(xué)領(lǐng)域，但接下來我們不會(huì)講解任何數(shù)學(xué)術(shù)語，只匯來解釋它，然后在接下來的三章中將其構(gòu)建完善。大記法不復(fù)雜，大O為了統(tǒng)一描述，大不關(guān)注算法所用的時(shí)間，只關(guān)注其所用的步數(shù)第1章介紹過，數(shù)組不論多大，讀取都只需1步。用大記法來表示，就雖然大記法有很多種讀法，但寫法只有一種。意味著一種算法無論面對多大的數(shù)據(jù)量，其步數(shù)總是相同的。就像其他也屬于的操作還包括數(shù)組末尾的插入與刪除。之前已證明，無論數(shù)組有多大，這兩種操作都只需1步，所以它們的效率都是。下面研究一下大記法如何描述線性查找的效率?；叵胍幌?，線性查找于格子數(shù)。即如前所述：對于個(gè)元素的數(shù)組，線性查找需要花步用大記法來表示，即為我將其讀作“ON”若用大記法來描述一種處理一個(gè)元素的數(shù)組需花步的算法的效率，很簡單，就是。前面提過，本書要采用一種易于理解的方式來討論大。當(dāng)然這不學(xué)角度來介紹大。因?yàn)榇蟊揪褪且粋€(gè)數(shù)學(xué)概念，所以人們經(jīng)常用數(shù)學(xué)詞匯介紹它，比如說“大記法可用來描述一個(gè)函數(shù)的增長率的上限”，或者“如果函數(shù)的增長速度不比函數(shù)快，那么就稱屬于”。大家數(shù)學(xué)背景不同，所以這些說法可能對你有識，就可以理解大。如果你想深入研究大背后的數(shù)學(xué)理論，可參考ThomasH.Cormen、CharlesELeiserson、RonaldLRivest和CliffordStein所著的《算法導(dǎo)論》，里面有完整的解析。此外，JustinAbrahms在他的文章中也對大做了不錯(cuò)的定義，維基百科上也有大量的數(shù)學(xué)解從可以看出，大記法不只是用固定的數(shù)字（如22、440）來表示說，大解答的是這樣的問題：當(dāng)數(shù)據(jù)增長時(shí)，步數(shù)如何變化？算法所需的步數(shù)等于數(shù)據(jù)量，意思是當(dāng)數(shù)組增加一個(gè)元素時(shí)，算法就要增加1步。而算法無論面對多大的數(shù)組，其步數(shù)都不從圖中可以看出，呈現(xiàn)為一條對角線。當(dāng)數(shù)據(jù)增加一個(gè)單位時(shí)，相比之下，則為一條水平線，因?yàn)椴还軘?shù)據(jù)量是多少，算法的步數(shù)都恒定。所以，也被稱為常數(shù)時(shí)間。因?yàn)榇笾饕P(guān)注的是數(shù)據(jù)量變動(dòng)時(shí)算法的性能變化，所以你會(huì)發(fā)現(xiàn)，即使一個(gè)算法的恒定步數(shù)不是1，它也可以被歸類為。假設(shè)有個(gè)算也可以表示為。雖然從技術(shù)上來說它需要3步而不是1步，但大記法并不糾結(jié)于此。簡單來說，就是用來表示所有數(shù)據(jù)增長但步數(shù)如果說只要步數(shù)恒定，3步的算法也屬于，那么恒為100步的算法也屬于。雖然100步的算法在效率上不如1步的算法，但如果它的步數(shù)是恒定的，那么它還是比更高效。對于元素量少于100的數(shù)組，算法的步數(shù)會(huì)少于100步的算素，注意，的步數(shù)就多于。因?yàn)閿?shù)據(jù)量從這個(gè)臨界點(diǎn)開始，直至無限，都會(huì)比花更多步數(shù)，所以總體上來說，比低效。這對于步數(shù)恒為1000000的算法來說也是一樣的。當(dāng)數(shù)據(jù)量一直增長時(shí)，一定會(huì)到達(dá)一個(gè)臨界點(diǎn)，使得算法比算法低效，而且之前的章節(jié)我們提到，線性查找并不總是的。當(dāng)要找的元素在組末尾，那確實(shí)是。但如果它在數(shù)組開頭，1步就能找到的話，那么技術(shù)上來說應(yīng)該是。所以概括來說，線性查找的最好情況是，最壞情況是。雖然大可以用來表示給定算法的最好和最壞的情景，但若無特別說明，大記法一般都是指最壞情況。因此盡管線性查找有的最好情況，但大多數(shù)資料還是把它歸類為。面就來看看如何用大記法描述二分查找。它不能寫成，因?yàn)槎植檎业牟綌?shù)會(huì)隨著數(shù)據(jù)量的增長而增長。它也不能寫成，因?yàn)椴綌?shù)比元素?cái)?shù)量要少得多，正如之前我們看到看來，二分查找的時(shí)間復(fù)雜度介于和之間。好了，二分查找的大記法是：我將其讀作“OlogN”。歸于此類的算法，它們的時(shí)間復(fù)雜度都叫作對數(shù)簡單來說，意味著該算法當(dāng)數(shù)據(jù)量翻倍時(shí)，步數(shù)加1。這確實(shí)注意曲線的微彎，使其效率略差于，卻遠(yuǎn)勝于若想理解這種時(shí)間復(fù)雜度為什么是，我們得先學(xué)習(xí)一下對數(shù)。讓我們來研究下為什么二分查找之類的算法被記為，到底log是等于：2×2×結(jié)果為8則將上述計(jì)算反過來，它意思是：要把2乘以自身多少次，才能得到8。因?yàn)樾枰?次，所以，再來一個(gè)例子?？梢越忉尀椋?×2×2×2×2×2=因?yàn)?要乘以自身6次才得到64，所以，可以表達(dá)為：將8不斷地除以2直到1，需要多少個(gè)2。82221（注：按照從左到右的順序計(jì)算。。類似地，可以解釋為：將64除以2多少次，才能得到164/2/2/2/2/2/2=因?yàn)檫@里有6個(gè)2，所以，現(xiàn)在你應(yīng)該明白對數(shù)是怎么回事了，那么就很好懂了解釋O(logN現(xiàn)在回到大記法。當(dāng)我們說時(shí)，其實(shí)指的是，不過你應(yīng)該還記得代表算法處理個(gè)元素需要步。如果元素有8個(gè)，則代表算法處理個(gè)元素需要步。如果有8個(gè)元素，那么這種算法需要3步，因?yàn)椤：唵蝸碚f，算法的步數(shù)等于二分?jǐn)?shù)據(jù)直至元素剩余1個(gè)的次下表是和的效率對比NO(NO(logN每次數(shù)據(jù)量翻倍時(shí)，算法的步數(shù)也跟著翻倍，算法卻只需thingsthings=['apples','baboons','cribs',forthinginprint"Here'sathing:%s"%它的效率要怎么用大記法來表示呢在for循環(huán)中使用print。為了得出它的大記法，我們需要分析這個(gè)算法的步數(shù)。這段代碼的主要部分——for循環(huán)會(huì)走4步，因?yàn)榱斜砜偣灿?個(gè)元素。。printprint'Hello它永遠(yuǎn)都只會(huì)是1步，所以是defdefforiinrange(2,number):ifnumber%i==0:returnFalsereturnTrue它接受一個(gè)參數(shù)，名為number，然后用一個(gè)for循環(huán)來測試number除以2到number之間的數(shù)，看是否有余數(shù)。如果沒有，則number非質(zhì)個(gè)數(shù)都有余數(shù)，那么它就是一個(gè)質(zhì)數(shù)，最后會(huì)返回True。此算法的效率為。它不以數(shù)組為參數(shù)，而是用一個(gè)數(shù)字。如果is_prime傳入的是7，那么for循環(huán)就要差不多走7次（準(zhǔn)確來說是5差不多101次。因?yàn)椴綌?shù)與參數(shù)的大小一致，所以它的效率是。學(xué)會(huì)大記法，我們在比較算法時(shí)就有了一致的參考系。有了它，我們下一章會(huì)用一個(gè)實(shí)際的例子，讓你看到大記法如何幫助我們顯著地提4章運(yùn)用大O來給代碼提速大記法能客觀地衡量各種算法的時(shí)間復(fù)雜度，是比較算法的利器。我步數(shù)為，比線性查找的快得多。接采用首先想到的那種算法了。不過有了大的話，你就可以與其他?！拔业乃惴ǜ鼈兿啾?，是快還是慢？”如果你通過大發(fā)現(xiàn)自己的算法比其他的要慢，你就應(yīng)該退一步，好好想想怎樣優(yōu)化它，才能使它變成更快的那種大。雖然并不總有提升空本章我們會(huì)寫些代碼來解決一個(gè)實(shí)際問題，并且會(huì)用大來測量算法的能。如果它們的順序錯(cuò)了（即左邊的值大于右邊），下面來舉一個(gè)完整的例子。假設(shè)要對[42713進(jìn)行排序。它開始第1第1步：首先，比較4和2第2第3步：比較4和7第5第6步：比較7和3第7此時(shí)7第8步：從比較2和4第10第11步：比較4和3第12第13步：比較2和1第14第15步：比較2和3defbubble_sort(list):unsorted_until_index=len(list)-1sorted=Falsedefbubble_sort(list):unsorted_until_index=len(list)-1sorted=Falsewhilenotsorted:sorted=foriinrange(unsorted_until_index):iflist[i]>list[i+1]:sorted=list[i],list[i+1]=list[i+1],list[i]unsorted_until_index=unsorted_until_index-list=[65,55,45,35,25,15,printlistunsorted_until_indexunsorted_until_index=len(list)-sortedsorted=一開始它應(yīng)該是False。whilenotsorted:sortedwhilenotsorted:sorted=接著是一個(gè)while循環(huán)，除非數(shù)組排好了序，不然它不會(huì)停下來。然其改為False。如果在一次輪回里沒有做過交換，那么sorted就確定為True，我們知道數(shù)組已排好序了。foriinrange(unsorted_until_index):iflist[i]>list[i+1]:foriinrange(unsorted_until_index):iflist[i]>list[i+1]:sorted=list[i],list[i+1]=list[i+1],在e循環(huán)里，還有一個(gè)r環(huán)中，我們會(huì)比較相鄰的元素，如果有順序錯(cuò)誤，就會(huì)進(jìn)行交換，并將d改為e。unsorted_until_indexunsorted_until_index=unsorted_until_index-432110推廣到個(gè)元素，需次比較?，F(xiàn)在把兩種步驟放在一起來看。一個(gè)含有1098765432145次比較，以及45次交換，共902019+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+21190次比較，以及190次交換，共380N再看仔細(xì)一點(diǎn)，你會(huì)發(fā)現(xiàn)隨著的增長，步數(shù)大約增長為2NN因此描述冒泡排序效率的大記法，是規(guī)范一些來說：用算法處理個(gè)元素，大約需要步算法是比較低效的，隨著數(shù)據(jù)量變多，其步數(shù)也劇增，如下圖所注意代表步數(shù)的曲線非常陡峭，的則只呈對角線狀。最后一點(diǎn)：也被叫作二次時(shí)間。functionhasDuplicateValue(array){for(vari=0;i<array.length;i++){for(varjfunctionhasDuplicateValue(array){for(vari=0;i<array.length;i++){for(varj=0;j<array.length;j++)if(i!==j&&array[i]==array[j]){returntrueif(i!==j&&array[i]==array[j]){returntruereturn此函數(shù)用vari來遍歷數(shù)組元素。每當(dāng)i指向下一元素時(shí)，我們又發(fā)起for循環(huán)，用varj來遍歷數(shù)組元素，并在這第二個(gè)循環(huán)過程中檢查i和j兩個(gè)位置的值是否相同。若相同，則表示數(shù)組有重復(fù)值。如果兩層循環(huán)都沒遇到重復(fù)值，則最終返回false，以示數(shù)組沒有重復(fù)雖然可以這么做，但它的效率高嗎？既然我們學(xué)過一點(diǎn)大記法，那么就試試用大來評價(jià)一下這個(gè)函數(shù)吧。記住，大測量的是步數(shù)與數(shù)據(jù)量的關(guān)系。因此，我們要測的就是：給hasDuplicateValue函數(shù)傳入一個(gè)含有個(gè)元素的數(shù)組，最壞情況下將使我們跑遍內(nèi)外兩層循環(huán)，比較完所有i、j組合，才返回false。由此可知個(gè)元素要比較次。因?yàn)橥鈱友h(huán)需要步來遍歷數(shù)組，而這里的每1步，又會(huì)發(fā)起內(nèi)層循環(huán)去用步遍歷數(shù)組。所以步乘以步等于步，此函數(shù)為一個(gè)算法。functionhasDuplicateValue(array){varsteps=0;functionhasDuplicateValue(array){varsteps=0;for(vari=0;i<array.length;i++)for(varj=0;j<array.length;j++){for(varj=0;j<array.length;j++){if(i!==j&&array[i]==array[j]){returntrue;returnfalse;輸出9，表示9次比較。3個(gè)元素需要9次比較，這個(gè)函數(shù)是的經(jīng)典毫無疑問，嵌套循環(huán)算法的效率就是。一旦看到嵌套循環(huán)，你就應(yīng)該馬上想到。雖然hasDuplicateValue是我們目前唯一想到的解決方法，但在確定采用之前，應(yīng)意識到它的意味著低效。當(dāng)遇到低效的算法時(shí)，我functionhasDuplicateValue(array){varexistingNumbers=[];functionhasDuplicateValue(array){varexistingNumbers=[];for(vari=0;i<array.length;i++){if(existingNumbers[array[i]]===undefined){existingNumbers[array[i]]=}elsereturnreturn時(shí)，existingNumbers就會(huì)變成以下這樣。[undefined,[undefined,undefined,undefined,1,undefined,1,undefined,undefined,為了確定這一新算法的時(shí)間復(fù)雜度符合哪種大，我們得考察其最壞情existingNumbers上某索引的值，并與undefined比較，代碼如下。if(existingNumbers[array[i]]if(existingNumbers[array[i]]===可見個(gè)元素就要次比較。因?yàn)檫@里只有一個(gè)循環(huán)，數(shù)組有多少個(gè)元素，它就要迭代多少次。要證明這個(gè)猜想，可以用JavaScriptconsole來functionhasDuplicateValue(array){varsteps=0;functionhasDuplicateValue(array){varsteps=0;varexistingNumbers=for(vari=0;i<array.length;i++){if(existingNumbers[array[i]]===undefined){existingNumbers[array[i]]=1;}elsereturnreturnfalse;因此其大記法是我們知道遠(yuǎn)遠(yuǎn)快于，所以采用第二種算法能極大地（其實(shí)第二種算法有一個(gè)缺點(diǎn)，不過我們在最毫無疑問，熟悉大記法能使我們發(fā)現(xiàn)低效的代碼，有助于我們挑選出更快的算法。然而，偶爾也會(huì)有兩種算法的大相同，但實(shí)際上二者快慢不一的情況。下一章我們就來學(xué)習(xí)當(dāng)大記法太過粗略的時(shí)候，如何5章用或不用大O來優(yōu)化代碼大是一種能夠比較算法效率，并告訴我們在特定環(huán)境下應(yīng)采用何種算大記法完全一樣，但實(shí)際上其中一個(gè)比另一個(gè)要快得多。上一章分析了冒泡排序算法，其效率是?，F(xiàn)在我們再來探索另一重復(fù)第(1)2)第1步：將索引1的值2與目前的最小值42比4還要小，于是將目前的最小值改為2第2步：再與下一個(gè)值做比較。因?yàn)?大于2，所以最小值還是2第3步：將11比2還要小，于是目前的最小值更新為1現(xiàn)在1可以開始第2第6步：將7跟目前的最小值2進(jìn)行比較。因?yàn)?小于72第7步：將4跟目前的最小值2進(jìn)行比較。因?yàn)?小于42第8步：將3跟目前的最小值2進(jìn)行比較。因?yàn)?小于32開始第3準(zhǔn)備工作：從索引2起，其值為7。于是本輪目前最小值為7第9步：比較4與7將4第10步：遇到3，它比4于是3第11步：到數(shù)組盡頭了，將3跟本輪起點(diǎn)7于是3準(zhǔn)備工作：此輪檢查從索引3開始，其值4第12步：比較4和74functionfunctionselectionSort(array)for(vari=0;i<array.length;i++){varlowestNumberIndex=i;for(varj=i+1;j<array.length;j++){if(array[j]<array[lowestNumberIndex])lowestNumberIndex=if(lowestNumberIndex!=i){vartemp=array[i];array[i]=array[lowestNumberIndex];array[lowestNumberIndex]=temp;returnfor(varfor(vari=0;i<array.length;i++)varvarlowestNumberIndex=for(varfor(varj=i+1;j<array.length;j++)此行代碼發(fā)起一個(gè)以i1if(array[j]<array[lowestNumberIndex]){lowestNumberIndex=j;if(array[j]<array[lowestNumberIndex]){lowestNumberIndex=j;小的格子值，就將lowestNumberIndex更新為該格子的索引。if(lowestNumberIndex!=i){vartemp=array[i];if(lowestNumberIndex!=i){vartemp=array[i];array[i]=array[lowestNumberIndex];array[lowestNumberIndex]=temp;不是，就將i所指的值與最小值交換。在之前5個(gè)元素的例子里，我們總共進(jìn)行了10第##432110推廣開來，若有個(gè)元素，就會(huì)有N冒泡排序最多要#選擇排序最多要#14(10+4次交換54(45+9次交換199(180+19次交換819(780+39次交換3239(3160+79次交換但有趣的是，選擇排序的大記法跟冒泡排序是一樣的還記得我們說過，大記法用來表示步數(shù)與數(shù)據(jù)量的關(guān)系。所以你可能會(huì)以為步數(shù)約為的一半的選擇排序，其大會(huì)寫成，以表示個(gè)元素需要步。如下表所示。NN2選擇排序最多要#但事實(shí)上，選擇排序的大記法為，跟冒泡排序一樣。這是因?yàn)榇笥浄ǖ囊粭l重要規(guī)則我們至今還沒提到：大記法忽略常數(shù)換一種不那么數(shù)學(xué)的表達(dá)方式，就是：大記法不包含一般數(shù)字，除非如剛才的例子，嚴(yán)格來說本應(yīng)為，最終得寫成。類似地，要寫成；也寫成；就算是比慢100倍的，也要寫成。得大沒什么意義。就像同為的選擇排序和冒泡排序，其實(shí)前者那么，大還憑什么值得我們學(xué)習(xí)呢大O盡管不能比較冒泡排序和選擇排序，大還是很重要的，因?yàn)樗軌騾^(qū)分不同算法的長期增長率。當(dāng)數(shù)據(jù)量達(dá)到一定程度時(shí)，的算法就會(huì)永遠(yuǎn)快過，無論這個(gè)實(shí)際上是還是。即使是，這個(gè)臨界點(diǎn)也是存在的。（第3章在比較一個(gè)100步的算法與算法時(shí)，也提過這個(gè)概念，不過這次我們會(huì)用另一個(gè)例子來下圖為和的對比此圖在上一章里出現(xiàn)過。它顯示了不管數(shù)據(jù)量是多少，總是快過。在第二幅圖中，我們看到當(dāng)數(shù)據(jù)量少于某個(gè)值時(shí)，是要快的，但過了這個(gè)值之后，便反超，并一直保持優(yōu)這就是大記法忽略常數(shù)的原因。大記法只表明，對于不同分類，存去。至于這個(gè)點(diǎn)在哪里，大并不關(guān)心。因此，不需要寫成，歸類到就好了同樣地，在數(shù)據(jù)量增大到某個(gè)點(diǎn)時(shí)，便會(huì)永遠(yuǎn)超越，即使該算法的實(shí)際步數(shù)為。所以大是極為有用的工具，當(dāng)兩種算法落在不同的大類別時(shí)，你就不過，本章的主要結(jié)論是即使兩種算法的大記法一樣，但實(shí)際速度也可能并不一樣。雖然選擇排序比冒泡排序快1倍，但它們的大記法都是。因此，大記法非常適合用于不同大分類下的算法的對比，對于大同類的算法，我們還需要進(jìn)一步的解析才能分辨出具體差的數(shù)組。你可能會(huì)用數(shù)組的each_with_index方法來做如下遍歷。defevery_other(array)new_array=[]defevery_other(array)new_array=[]array.each_with_indexdo|element,index|new_array<<elementifindex.even?returnnew_array因?yàn)橐x取數(shù)組的每一個(gè)元素，所以讀取有步。插入則只有步，因?yàn)橹挥虚g隔的元素才被放到新數(shù)組里。從技術(shù)上來說，次讀取加次插入，這算法的效率應(yīng)該是，或者是。但因?yàn)榇笥浄ㄒ殉?shù)丟掉，所以只寫成。defevery_other(array)new_arraydefevery_other(array)new_array=[]index=0whileindex<array.lengthnew_array<<array[index]index+=2returnnew_array結(jié)果就是有個(gè)元素，會(huì)有次讀取，次插入。它跟第一種做法一樣，記為。然而，第一種做法實(shí)際有步，比只有步的第二種明顯要慢。雖然現(xiàn)在我們已經(jīng)掌握了一些非常強(qiáng)大的算法分析手法。我們能夠使用大去判斷各種算法的效率，即便兩種算法的大記法一樣，也知道如何比它們。6章樂觀地調(diào)優(yōu)是，但其實(shí)選擇排序比冒泡排序快一倍?，F(xiàn)在來學(xué)第三種排序算法——下面嘗試對[42713數(shù)組運(yùn)用插入排序。到數(shù)組上方的就是temp_value。第2步：因?yàn)?大于2，所以把4第3步：將temp_value插回?cái)?shù)組，完成第一輪。開始第2是temp_value等于7。開始第3第7步：7大于1，于是將7第9步：4大于1，于是也要將4第11步：2比較大，所以將2開始第4第14步：7更大，于是將7第16步：4大于3，所以將4defdefforindexinrange(1,position=indextemp_value=array[index]whileposition>0andarray[position-1]>temp_value:array[position]=array[position-1]position=position-1array[position]=temp_valueforforindexinrange(1,position=indextemp_value=array[index]position=indextemp_value=array[index]whileposition>0andarray[position-1]>temp_value:array[position]=array[position-1]whileposition>0andarray[position-1]>temp_value:array[position]=array[position-1]position=position-然后在內(nèi)部發(fā)起一個(gè)while循環(huán)，以檢查position左側(cè)的值是否大于temp_value。若是，則用array[position]=array[position-側(cè)的值是否大于temp_value……如此重復(fù)，直至遇到的值比temp_value小。array[position]array[position]=推。到最后一輪時(shí)，就要拿temp_value以外的所有值與其進(jìn)行比較。換言之，如果數(shù)組有個(gè)元素，則最后一輪中最多進(jìn)行次比較。次。對于有5123410對于有1012345678945（對于有20個(gè)元素的數(shù)組，最多需要190次比較，以此類推。由此可發(fā)現(xiàn)一個(gè)規(guī)律：對于有個(gè)元素的數(shù)組，大約需要次比（是50，是200）。次比較次平移步輪，所以可以得出結(jié)論：有次移除和次插入。比較和平移的合計(jì)次移除次插入步我們已經(jīng)知道大有一條重要規(guī)則——忽略常數(shù)，于是你可能會(huì)將其簡化成。不過，現(xiàn)在來學(xué)習(xí)一下大的另一條重要規(guī)則：大只保留最高階的。換句話說，如果有個(gè)算法需要步，我們就只會(huì)關(guān)注其中的，即以來表示。為什么呢？NNN101010001000000100010000001000000000隨著的變大，的增長越來越拋離其他階。當(dāng)為1000時(shí)，就比大了1000倍。因此，我們只關(guān)心最高階的。所以在插入排序的例子中，還得進(jìn)一步簡化成排序一樣，都是。不過上一章曾指出，雖然冒泡排序和選擇排序都是，但選擇排序?qū)嶋H上是步，比步的冒泡排序更快。乍一看，你可能會(huì)覺得插入排序跟冒泡排序一樣，因?yàn)樗鼈兌际牵鋵?shí)插入排序是步。值（這兩種操作合計(jì)步）。如果說插入排序的最壞情況需要步，那么平均情況就是步。盡管最終大都會(huì)寫成。最好情況就像[1,234情況就是[4321。平均情況，則如[1342情況，分別需要、、步。為遇到了小于temp_value的值而提早結(jié)束。3好，都要步。因?yàn)檫@個(gè)算法沒有提早結(jié)束某一輪的機(jī)制，不管遇[3,1,4,2和[4536的交集為[34，因?yàn)閮蓚€(gè)數(shù)組都有3和4functionintersection(first_array,second_array){varresult=[];functionintersection(first_array,second_array){varresult=[];for(vari=0;i<first_array.length;i++)for(varj=0;j<second_array.length;j++){if(first_array[i]==second_array[j]){return較，并把相同的值插入到result。插入的步數(shù)微不足道，因?yàn)榧词箖梢莾蓚€(gè)數(shù)組同樣大小，那么比較需要步。這是因?yàn)閿?shù)組一的每值，都要與數(shù)組二的每個(gè)值進(jìn)行對比。于是，兩個(gè)數(shù)據(jù)量都為5的數(shù)組，最終會(huì)比較25次。這種算法效率為。（如果數(shù)組大小不一，比如說分別含、個(gè)元素，那么此過程的步數(shù)就是，但簡單起見，就當(dāng)它們大小一樣吧。）intersection函數(shù)的實(shí)現(xiàn)，無論遇到什么情況都是的，不管你functionintersection(first_array,second_array){varresult=[];functionintersection(first_array,second_array){varresult=[];for(vari=0;i<first_array.length;i++)for(varj=0;j<second_array.length;j++){if(first_array[i]==second_array[j]){return這樣的話，在沒有交集的最壞情況下，我們?nèi)匀灰龃伪容^；在數(shù)組完全一樣的最好情況下，就只需要次比較；在數(shù)組不同但有部分重復(fù)的平均情況下，步數(shù)會(huì)介于到之間。是。7章查找迅速的散列表menumenu=[["frenchfries",0.75],["hamburger",2.5],["hotdog",1.5],找，需要步。有序數(shù)組則可以用二分查找，只需要步盡管也不錯(cuò)，但我們可以做得更好。事實(shí)上，可以好很多。到了本章結(jié)尾，你會(huì)掌握一種名為散列表的數(shù)據(jù)結(jié)構(gòu)，只用步就能menumenu={"frenchfries"=>0.75,"hamburger"=>2.5,"hotdog"=>1.5,"frenchfries"menu["frenchmenu["french在散列表中查找值的平均效率為，因?yàn)橹灰徊健Ｏ旅鎭砜纯礊锳A=B=C=D=E=第2步：把每一位數(shù)字相加，2147第2步：把每一位數(shù)字相乘，2148是4，2×1×4總會(huì)是8，不可能有其他輸出。thesaurusthesaurus=thesaurus["bad"]thesaurus["bad"]={"bad"{"bad"=>BADBAD=2*1*4=thesaurus["cab"]thesaurus["cab"]=CABCAB=3*1*2=thesaurus["ace"]thesaurus["ace"]=ACE的散列值為15（ACE13515），于是"star被放到第{"bad"{"bad"=>"evil","cab"=>"taxi","ace"=>現(xiàn)在要查"bad的同義詞，寫成代碼的話，如下所示。計(jì)算這個(gè)鍵的散列值：BAD2148為"evil。這下你應(yīng)該明白為什么從散列表里讀取數(shù)據(jù)只需要了吧，因?yàn)槠溥^地去找，直至找到為止。無序數(shù)組需要，有序數(shù)組需要。但用散列表的話，我們就能夠以食物作為鍵來做的查找。這就是散thesaurus["dab"]thesaurus["dab"]=DABDAB=4*1*2=計(jì)算散列值DAB4128讀取第8于是線性地在該數(shù)組中查找，檢查每個(gè)子數(shù)組的索引0同義詞（"pat）。組上進(jìn)行。因此散列表的最壞情況就是。完成。要存多少數(shù)據(jù)。有多少可用的格子。用什么樣的散列函數(shù)。PUTPUT=16+21+20=因?yàn)?7不止一位數(shù)字，于是將57拆成5755+7=12也不止一位數(shù)字，于是拆成1211+2=9如果要保存14個(gè)元素，那就得準(zhǔn)備20就是：理想的負(fù)載因子是0.7（7/10個(gè)格子）。插入都需要。varvarset=set["apple"]set["apple"]=set["banana"]=set["cucumber"]=這樣每次插入新值，都只需花的時(shí)間，而不是線性查找的。set["banana"]set["banana"]=散列表確實(shí)非常適用于檢查數(shù)據(jù)的存在性。第4functionfunctionhasDuplicateValue(array){for(vari=0;i<array.length;i++){for(varj=0;j<array.length;j++){if(i!==j&&array[i]==array[j]){returnreturn當(dāng)時(shí)我們說了，該嵌套循環(huán)的效率是于是有了第二個(gè)的方案，不過它只能處理數(shù)據(jù)全為非負(fù)整數(shù)的數(shù)functionhasDuplicateValue(array){varexistingValues={};functionhasDuplicateValue(array){varexistingValues={};for(vari=0;i<array.length;i++){if(existingValues[array[i]]===undefined){existingValues[array[i]]=}elsereturnreturn這種方法也是，其中的existingValues不是數(shù)組而是散列表，varvarvotes=functionaddVote(candidate){["Thomas["ThomasJefferson","JohnAdams","JohnAdams","ThomasJefferson",這樣插入很快，只有functioncountVotes(votes){vartally={};functioncountVotes(votes){vartally={};for(vari=0;i<votes.length;i++){if(tally[votes[i]]){}else{tally[votes[i]]=1;return不過這樣需要，也太慢了varvarvotes=functionaddVote(candidate){if(votes[candidate]){}else{votes[candidate]=1;functioncountVotes(){returnvotes;這樣一來，投票是，并且因?yàn)橥镀睍r(shí)就已經(jīng)在計(jì)數(shù)，所以已完成了高效的軟件離不開散列表，因?yàn)槠涞淖x取和插入帶來了無與倫比的8章用棧和隊(duì)列來構(gòu)造靈巧的代碼只能在末尾插入數(shù)據(jù)。只能讀取末尾的數(shù)據(jù)。只能移除末尾的數(shù)據(jù)。首先，將5再將0這就剩下5壓棧和出棧可被形容為LIFO（lastin，firstout）后進(jìn)先出。解釋起來下面我們來寫一個(gè)初級的vp分析器——一種用來檢查vpt代碼的語法是否正確的工具。因?yàn)関p以做得很復(fù)雜。簡單起見，我們就只專注于檢查括號的閉合情況吧，包括圓括號、方括號、花括號，這些地方搞錯(cuò)的話是很令人郁悶的。(var(varx=這種歸為第1varvarx=這種歸為第2還有第3(var(varx=[1,2,如果棧里沒有任何元素，也就是遇到了右括號但沒有左括號，即第23第2接下來的varx，沒有一個(gè)是括號，因此會(huì)被忽略。第4第5第6然后忽略123第7第9第11classLinterattr_reader:errordef#@stack=[]def#text.each_char.with_indexdo|char,index|ifopening_brace?(char)#elsififcloses_most_recent_opening_brace?(char)#如果讀到右括號，并且它與棧頂?shù)淖罄ㄌ柶ヅ洌?則將棧頂彈出else#@error="Incorrectclosingbrace:#{char}atindex#{index}"if#@error="#{@stack.last}doesnothaveaclosingbrace"def["(","[","{"].include?(char)def[")","]",def{")"=>"(","]"=>"[","}"=>defmost_recent_opening_bracedefcloses_most_recent_opening_brace?(char)opening_brace_of(char)==most_recent_opening_bracelinterlinter=linter.lint("(varx={y:[1,2,3]})")putslinter.errorlinterlinter=linter.lint("(varx={y:[1,2,3])}")putslinter.errorIncorrectIncorrectclosingbrace:)atindexlinterlinter=linter.lint("(varx={y:[1,2,3]}")putslinter.error((doesnothaveaclosing計(jì)算機(jī)科學(xué)家都用縮寫“FIFO”（firstin,firstout）先進(jìn)先出，來形容與棧類似，隊(duì)列也有3個(gè)限制（但內(nèi)容不同）（這跟棧一樣）。（這跟棧相反）。（這也跟棧相反）。然后，插入9接著，插入100想移除數(shù)據(jù)，得先從5接著，移除9這樣一來，隊(duì)列就只剩下100機(jī)的打印任務(wù)。利用Ruby數(shù)組的push方法，將數(shù)據(jù)加到數(shù)組末尾，以及shift方法，將數(shù)據(jù)從數(shù)組開頭移除。你可以這樣來編寫接口類。classclassdefinitialize@queue=[]defqueue_print_job(document)defwhile#Ruby#Ruby的shift方法可移出并返回?cái)?shù)組的第一個(gè)元素\hdef#讓打印機(jī)去打印文檔（為了演示，暫時(shí)先打到終端上putsdocumentprint_manager=PrintManager.newprint_manager.queue_print_job("FirstDocument")print_manager.queue_print_job("SecondDocument")print_manager.queue_print_job("ThirdDocument")print_manager=PrintManager.newprint_manager.queue_print_job("FirstDocument")print_manager.queue_print_job("SecondDocument")print_manager.queue_print_job("ThirdDocument")接著打印機(jī)就會(huì)按3FirstDocumentSecondDocumentThirdDocumentFirstDocumentSecondDocumentThirdDocument9章遞歸functionblah(){functionblah(){functionfunctioncountdown(number){for(vari=number;i>=0;i--){functioncountdown(number){functioncountdown(number){countdown(number-1);第2步：將number（值為10）打印到控制臺(tái)。為number-1等于9）。第23步：調(diào)用countdown(-1。我們可以加個(gè)條件判斷，來保證當(dāng)number為0時(shí)，不再調(diào)functioncountdown(number){functioncountdown(number){if(number===0){}else{countdown(number-1);對于剛才的countdown(函數(shù)來說，0就是基準(zhǔn)情形。333*2*1=555*4*3*2*1=deffactorial(number)ifnumber==1deffactorial(number)ifnumber==1return1returnnumber*factorial(number-ififnumber==1return1returnnumber*factorial(number-1)returnnumber*factorial(number-1)ififnumber==1return1ififnumber==1return1returnnumber*factorial(number-1)調(diào)用factorial(2就會(huì)返回2*factorial(1。要計(jì)算2*所記，你會(huì)發(fā)現(xiàn)那是1。因此，2*factorial(1就是2*1，即是returnnumber*factorial(number-1)代入?yún)?shù)便是3*factorial(2。那么factorial(2是什么呢？你是factorial(3會(huì)返回6（3*26）factorial(2，而在factorial(2返回前，又調(diào)用了其實(shí)還在factorial(2之中，而factorial(2又正讓我們以factorial為例來觀察調(diào)用棧如何運(yùn)作。還在factorial(2中，于是，它將此事也壓入調(diào)用棧中。以返回，不用再調(diào)用factorial。調(diào)用棧的棧頂，發(fā)現(xiàn)那是factorial(2。該先完成的是factorial(2。從更高的角度去看，可以看出計(jì)算機(jī)處理3defdefDir.foreach(directory)doifFile.directory?("#{directory}/#{filename}")&&filename!="."&&filename!=".."puts"#{directory}/#{filename}"#以當(dāng)前目錄為參數(shù)，調(diào)用find_directoriesdeffind_directories(directory)#deffind_directories(directory)#遍歷給定目錄下的文件Dir.foreach(directory)doifFile.directory?("#{directory}/#{filename}")&&filename!="."&&filename!=".."puts"#{directory}/#{filename}"#puts"#{directory}/#{filename}"#遍歷其子目錄下的文件Dir.foreach("#{directory}/#{filename}")doifFile.directory?("#{directory}/#{filename}/#{inner_filename}")&&inner_filename!="."&&inner_filename!=".."puts"#{directory}/#{filename}/#{inner_filename}"#以當(dāng)前目錄為參數(shù)，調(diào)用find_directoriesdefdefDir.foreach(directory)doifFile.directory?("#{directory}/#{filename}")&&filename!="."&&filename!=".."puts"#{directory}/#{filename}"#以當(dāng)前目錄為參數(shù)，調(diào)用find_directories注意，改用遞歸并不會(huì)改變算法的大。但是，在下一章你會(huì)看到，遞10章飛快的遞歸算法第1步：拿左指針（正指向0）與軸（值為3）第4比較左指針（值為2）第8味著3classclassattr_reader:arraydefinitialize(array)@array=defpartition!(left_pointer,right_pointer)#總是取最右的值作為軸pivot_position=pivot=#right_pointer-=1whiletruedowhile@array[left_pointer]<pivotdoleft_pointer+=1while@array[right_pointer]>pivotdoright_pointer-=1ifleft_pointer>=right_pointerswap(left_pointer,right_pointer)#swap(left_pointer,##returnleft_pointerdefswap(pointer_1,pointer_2)temp_value=@array[pointer_1]@array[pointer_1]=@array[pointer_2]@array[pointer_2]=temp_value此partition方法接受兩個(gè)參數(shù)作為左指針和右指針的起始位置，并defquicksort!(left_index,right_index)#defquicksort!(left_index,right_index)#基準(zhǔn)情形：分出的子數(shù)組長度為0或1ifright_index-left_index<=0#pivot_position=partition!(left_index,#對軸左側(cè)的部分遞歸調(diào)用quicksortquicksort!(left_index,pivot_position-1)#對軸右側(cè)的部分遞歸調(diào)用quicksortquicksort!(pivot_position+1,right_index)arrayarray=[0,5,2,1,6,sortable_array=SortableArray.new(array)sortable_array.quicksort!(0,array.length-1)psortable_array.array再回到剛才的例子。最初的數(shù)組是[052163，然后我們做現(xiàn)在，對于這個(gè)[012的子數(shù)組，我們選取其最右端的元素作為讓我們接著之前的第8第10第11這時(shí)左指針的值與軸相等了（因?yàn)樗赶蜉S），第13于是軸（值為2）分出了左側(cè)的子數(shù)組[01接下來將左側(cè)的[01為了專注于[01第14步：比較左指針（值為0）與軸（值為1）第15由于左指針不再小于軸了（因?yàn)樗闹稻褪禽S），最開始我們以3為軸，然后把其左側(cè)的子數(shù)組[012照約定，現(xiàn)在輪到了它右側(cè)的[65[0123[65接下來的分區(qū)以最右端的元素（值為5）左右指針只能同時(shí)指向6第20這樣軸（值為5）盡管隨后我們應(yīng)該遞歸地對[56左右兩側(cè)的子數(shù)組進(jìn)行分區(qū)，但現(xiàn)在軸左側(cè)沒有元素，右側(cè)也只有長度為1——6一次分區(qū)至少有次比較，即數(shù)組的每個(gè)值都要與軸做比較。因?yàn)槊看谓粨Q的次數(shù)則取決于數(shù)據(jù)的排列情況。一次分區(qū)里，交換最少會(huì)有次，最多會(huì)有次，因?yàn)榧词顾性囟夹枰粨Q，我們也只是將左對于隨機(jī)排列的數(shù)據(jù)，粗略來算就是的一半，即次交換。于是，次比較加上次交換，共步。最后根據(jù)大記法的規(guī)則，忽略常數(shù)項(xiàng)，得出分區(qū)操作的時(shí)間為。88個(gè)元素*1.25=103個(gè)元素*1.25=3.754個(gè)元素*1.25=5+2個(gè)元素*1.25=2.5總共約為總共約為21如果再對不同大小的數(shù)組做統(tǒng)計(jì)，你會(huì)發(fā)現(xiàn)個(gè)元素，就要步。想體會(huì)什么是的話，可參考下表。logN×log大記法來表達(dá)的話，它是算法?？焖倥判虻牟綌?shù)接近絕非偶然。如果我們以更平均的情況來如果數(shù)組元素有個(gè)，那就是次。假設(shè)元素有8個(gè)，那就要對半切因?yàn)榈确职l(fā)生了次，而每次都要對總共個(gè)元素做分區(qū)，所以總步數(shù)為。于是在最壞情況下，對8765432個(gè)元素進(jìn)行分區(qū)，一共寫成公式的話，就是個(gè)元素，需步，即步，如下圖所示。又因?yàn)榇蠛雎猿?shù)，所以最終我們會(huì)說，快速排序最壞情況下的效率為。見的平均情況，前者的比后者的好得多，所以總體來假設(shè)子數(shù)組的軸最后落到第3這次分區(qū)過后，最小和第2會(huì)導(dǎo)致的步數(shù)。但快速選擇不同，下一次的分區(qū)操作只需在分析快速選擇的效率，你會(huì)發(fā)現(xiàn)它的平均情況是?；叵朊看畏謪^(qū)8+4+2=14步。于是8個(gè)元素大概是14步。如果是64個(gè)元素，就會(huì)是643216842126步；如果是128個(gè)用公式來表達(dá)，就是對于個(gè)元素，會(huì)步。結(jié)果大概是2N步。由于大忽略常數(shù)，我們最終會(huì)說快速選擇的效率為。defquickselect!(kth_lowest_value,left_index,right_index)#defquickselect!(kth_lowest_value,left_index,right_index)#當(dāng)子數(shù)組只剩一個(gè)格子——即達(dá)到基準(zhǔn)情形時(shí)，#ifright_index-left_index<=0return@array[left_index]##pivot_position=partition!(left_index,ifkth_lowest_value<pivot_positionquickselect!(kth_lowest_value,left_index,pivot_position-1)elsifkth_lowest_value>pivot_positionquickselect!(kth_lowest_value,pivot_position+1,right_index)else#至此kth_lowest_value只會(huì)等于pivot_position#如果分區(qū)后返回的軸的索引等于kth_lowest_value，#那這個(gè)軸就是我們要找的值return@array[pivot_position]想要從一個(gè)無序數(shù)組中找出第2arrayarray=[0,50,20,10,60,sortable_array=psortable_array.quickselect!(1,0,array.length-11章基于結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)接下來的幾章將要學(xué)習(xí)的各種數(shù)據(jù)結(jié)構(gòu)，都涉及一種概念——的鏈（最后一個(gè)結(jié)點(diǎn)的鏈?zhǔn)莕ull，因?yàn)樗墙K點(diǎn)），所以整體占用了8classclassattr_accessor:data,:next_nodedefinitialize(data)@data=datanode_1=Node.new("once")node_2=Node.new("upon")node_1.next_node=node_2node_1=Node.new("once")node_2=Node.new("upon")node_1.next_node=node_2node_3=Node.new("a")node_2.next_node=node_3node_4=Node.new("time")node_3.next_node=node_4、"a和"time4雖然只用Node也可以創(chuàng)建出鏈表，但我們的程序無法由此輕易地得知是一個(gè)最基本的LinkedList的寫法。classLinkedListattr_accessor:first_nodeclassLinkedListattr_accessor:first_nodedefinitialize(first_node)@first_node=listlist=的格子上，其效率為。但在鏈表中就不是這樣了。1classLinkedListattr_accessor:first_nodeclassLinkedListattr_accessor:first_nodedefinitialize(first_node)@first_node=def#從第一個(gè)結(jié)點(diǎn)開始current_node=first_nodecurrent_index=0whilecurrent_index<index#順著鏈往下找，直至我們要找的那個(gè)索引值current_node=current_node.next_nodecurrent_index+=1#如果讀到最后一個(gè)結(jié)點(diǎn)之后，就說明#所找的索引不在鏈表中，因此返回nilreturnnilunlesscurrent_nodereturn點(diǎn)，于是需要步。由于大記法默認(rèn)采用最壞情況，所以我們說讀取鏈表的時(shí)間復(fù)雜度為。這跟讀取數(shù)組的相比，的確是一大劣不在列表里，那就要花步。classLinkedListattr_accessor:first_node#classLinkedListattr_accessor:first_node#其他方法略……def#從第一個(gè)結(jié)點(diǎn)開始current_node=first_nodecurrent_index=0#ifcurrent_node.data==valuereturncurrent_index#current_node=current_node.next_nodecurrent_index+=1endwhile#如果遍歷整個(gè)鏈表都沒找到，就返回nilreturnnil數(shù)據(jù)都右移一格，所以會(huì)導(dǎo)致的時(shí)間復(fù)雜度。然而，若是往鏈表的表頭進(jìn)行插入，則只需一步，即。下面看看為什么。到"blue那一結(jié)點(diǎn)。然后我們想在索引2（"blue和"green之間）插入"purple。由于率為。下面我們來演示一下。既然已到達(dá)索引1因此，鏈表的插入效率為，與數(shù)組一樣classclassattr_accessor##其他方法略definsert_at_index(index,value)#創(chuàng)建新結(jié)點(diǎn)new_node=#如果在開頭插入，則將新結(jié)點(diǎn)的next_node指向原#并為其設(shè)置新的first_nodeifindex==0new_node.next_node=first_nodereturn@first_node=new_nodecurrent_node=first_nodecurrent_index=0#prev_index=index-whilecurrent_index<prev_indexdocurrent_node=current_node.next_nodecurrent_index+=1new_node.next_node=current_node.next_node#使前一結(jié)點(diǎn)的鏈指向新結(jié)點(diǎn)current_node.next_node=那直接讓鏈表以"upon為開頭就好了。list.first_nodelist.first_node=的時(shí)間復(fù)雜度。1步——令倒數(shù)第二的結(jié)點(diǎn)的鏈指向null。然而，要找出倒數(shù)第二的結(jié)點(diǎn)，得花步，因索引1的結(jié)點(diǎn)，將其鏈指向"green結(jié)點(diǎn)。classLinkedListattr_accessor:first_node#classLinkedListattr_accessor:first_node#其他方法略……def##則將first_node#ifindex==deleted_node=first_node@first_node=first_node.next_nodereturndeleted_nodecurrent_node=first_nodecurrent_index=0##將其命名為whilecurrent_index<index-1docurrent_node=current_node.next_nodecurrent_index+=1#deleted_node=current_node.next_nodenode_after_deleted_node=#將current_node的鏈指向node_after_deleted_node，#這樣被刪結(jié)點(diǎn)就被排除在鏈表之外了current_node.next_node=node_after_deleted_node（在末端是）（在前端是）（在末端是）（在前端是）不管這個(gè)列表是數(shù)組還是鏈表，要檢查每個(gè)元素的話，都得花步。然用數(shù)組的話，每次刪除郵件地址，我們就要另外再花步去左移后所以如果存在需要?jiǎng)h除的無效地址，那么除了遍歷郵件地址的步，還得加上步乘以無效地址數(shù)。刪除所帶來的大約100000步的操作（100個(gè)無效地址×）。入是極快的，時(shí)間復(fù)雜度為。鏈表則要。所以在插入方面，但到了刪除的話，就是鏈表更快了，因?yàn)樗灰?，而?shù)組是，另一種是：數(shù)組的插入是，刪除是；鏈表則反過來，分別是和。都為。classclassattr_accessor