算法圖解算法入門目錄TOC\h\h第1章算法簡介\h1.1引言\h1.1.1性能方面\h1.1.2問題解決技巧\h1.2二分查找\h1.2.1更佳的查找方式\h1.2.2運(yùn)行時間\h1.3大O表示法\h1.3.1算法的運(yùn)行時間以不同的速度增加\h1.3.2理解不同的大O運(yùn)行時間\h1.3.3大O表示法指出了最糟情況下的運(yùn)行時間\h1.3.4一些常見的大O運(yùn)行時間\h1.3.5旅行商\h1.4小結(jié)\h第2章選擇排序\h2.1內(nèi)存的工作原理\h2.2數(shù)組和鏈表\h2.2.1鏈表\h2.2.2數(shù)組\h2.2.3術(shù)語\h2.2.4在中間插入\h2.2.5刪除\h2.3選擇排序\h示例代碼\h2.4小結(jié)\h第3章遞歸\h3.1遞歸\h3.2基線條件和遞歸條件\h3.3棧\h3.3.1調(diào)用棧\h3.3.2遞歸調(diào)用棧\h3.4小結(jié)\h第4章快速排序\h4.1分而治之\h4.2快速排序\h4.3再談大O表示法\h4.3.1比較合并排序和快速排序\h4.3.2平均情況和最糟情況\h4.4小結(jié)\h第5章散列表\h5.1散列函數(shù)\h5.2應(yīng)用案例\h5.2.1將散列表用于查找\h5.2.2防止重復(fù)\h5.2.3將散列表用作緩存\h5.2.4小結(jié)\h5.3沖突\h5.4性能\h5.4.1填裝因子\h5.4.2良好的散列函數(shù)\h5.5小結(jié)\h第6章廣度優(yōu)先搜索\h6.1圖簡介\h6.2圖是什么\h6.3廣度優(yōu)先搜索\h6.3.1查找最短路徑\h6.3.2隊(duì)列\(zhòng)h6.4實(shí)現(xiàn)圖\h6.5實(shí)現(xiàn)算法\h運(yùn)行時間\h6.6小結(jié)\h第7章狄克斯特拉算法\h7.1使用狄克斯特拉算法\h7.2術(shù)語\h7.3換鋼琴\h7.4負(fù)權(quán)邊\h7.5實(shí)現(xiàn)\h7.6小結(jié)\h第8章貪婪算法\h8.1教室調(diào)度問題\h8.2背包問題\h8.3集合覆蓋問題\h近似算法\h8.4NP完全問題\h8.4.1旅行商問題詳解\h8.4.2如何識別NP完全問題\h8.5小結(jié)\h第9章動態(tài)規(guī)劃\h9.1背包問題\h9.1.1簡單算法\h9.1.2動態(tài)規(guī)劃\h9.2背包問題FAQ\h9.2.1再增加一件商品將如何呢\h9.2.2行的排列順序發(fā)生變化時結(jié)果將如何\h9.2.3可以逐列而不是逐行填充網(wǎng)格嗎\h9.2.4增加一件更小的商品將如何呢\h9.2.5可以偷商品的一部分嗎\h9.2.6旅游行程最優(yōu)化\h9.2.7處理相互依賴的情況\h9.2.8計(jì)算最終的解時會涉及兩個以上的子背包嗎\h9.2.9最優(yōu)解可能導(dǎo)致背包沒裝滿嗎\h9.3最長公共子串\h9.3.1繪制網(wǎng)格\h9.3.2填充網(wǎng)格\h9.3.3揭曉答案\h9.3.4最長公共子序列\(zhòng)h9.3.5最長公共子序列之解決方案\h9.4小結(jié)\h第10章K最近鄰算法\h10.1橙子還是柚子\h10.2創(chuàng)建推薦系統(tǒng)\h10.2.1特征抽取\h10.2.2回歸\h10.2.3挑選合適的特征\h10.3機(jī)器學(xué)習(xí)簡介\h10.3.1OCR\h10.3.2創(chuàng)建垃圾郵件過濾器\h10.3.3預(yù)測股票市場\h10.4小結(jié)\h第11章接下來如何做\h11.1樹\h11.2反向索引\h11.3傅里葉變換\h11.4并行算法\h11.5MapReduce\h11.5.1分布式算法為何很有用\h11.5.2映射函數(shù)\h11.5.3歸并函數(shù)\h11.6布隆過濾器和HyperLogLog\h11.6.1布隆過濾器\h11.6.2HyperLogLog\h11.7SHA算法\h11.7.1比較文件\h11.7.2檢查密碼\h11.8局部敏感的散列算法\h11.9Diffie-Hellman密鑰交換\h11.10線性規(guī)劃\h11.11結(jié)語\h練習(xí)答案第1章算法簡介本章內(nèi)容為閱讀后續(xù)內(nèi)容打下基礎(chǔ)。編寫第一種查找算法——二分查找。學(xué)習(xí)如何談?wù)撍惴ǖ倪\(yùn)行時間——大O表示法。了解一種常用的算法設(shè)計(jì)方法——遞歸。1.1引言算法是一組完成任務(wù)的指令。任何代碼片段都可視為算法，但本書只介紹比較有趣的部分。本書介紹的算法要么速度快，要么能解決有趣的問題，要么兼而有之。下面是書中一些重要內(nèi)容。第1章討論二分查找，并演示算法如何能夠提高代碼的速度。在一個示例中，算法將需要執(zhí)行的步驟從40億個減少到了32個！GPS設(shè)備使用圖算法來計(jì)算前往目的地的最短路徑，這將在第6、7和8章介紹。你可使用動態(tài)規(guī)劃來編寫下國際跳棋的AI算法，這將在第9章討論。對于每種算法，本書都將首先進(jìn)行描述并提供示例，再使用大O表示法討論其運(yùn)行時間，最后探索它可以解決的其他問題。1.1.1性能方面好消息是，本書介紹的每種算法都很可能有使用你喜歡的語言編寫的實(shí)現(xiàn)，因此你無需自己動手編寫每種算法的代碼！但如果你不明白其優(yōu)缺點(diǎn)，這些實(shí)現(xiàn)將毫無用處。在本書中，你將學(xué)習(xí)比較不同算法的優(yōu)缺點(diǎn)：該使用合并排序算法還是快速排序算法，或者該使用數(shù)組還是鏈表。僅僅改用不同的數(shù)據(jù)結(jié)構(gòu)就可能讓結(jié)果大不相同。1.1.2問題解決技巧你將學(xué)習(xí)至今都沒有掌握的問題解決技巧，例如：如果你喜歡開發(fā)電子游戲，可使用圖算法編寫跟蹤用戶的AI系統(tǒng)；你將學(xué)習(xí)使用K最近鄰算法編寫推薦系統(tǒng)；有些問題在有限的時間內(nèi)是不可解的！書中討論NP完全問題的部分將告訴你，如何識別這樣的問題以及如何設(shè)計(jì)找到近似答案的算法?？偠灾?，讀完本書后，你將熟悉一些使用最為廣泛的算法。利用這些新學(xué)到的知識，你可學(xué)習(xí)更具體的AI算法、數(shù)據(jù)庫算法等，還可在工作中迎接更嚴(yán)峻的挑戰(zhàn)。需要具備的知識要閱讀本書，需要具備基本的代數(shù)知識。具體地說，給定函數(shù)f(x)=x×2，f(5)的值是多少呢？如果你的答案為10，那就夠了。另外，如果你熟悉一門編程語言，本章（以及本書）將更容易理解。本書的示例都是使用Python編寫的。如果你不懂任何編程語言但想學(xué)習(xí)一門，請選擇Python，它非常適合初學(xué)者；如果你熟悉其他語言，如Ruby，對閱讀本書也大有幫助。1.2二分查找假設(shè)要在電話簿中找一個名字以K打頭的人，（現(xiàn)在誰還用電話簿！）可以從頭開始翻頁，直到進(jìn)入以K打頭的部分。但你很可能不這樣做，而是從中間開始，因?yàn)槟阒酪訩打頭的名字在電話簿中間。又假設(shè)要在字典中找一個以O(shè)打頭的單詞，你也將從中間附近開始。現(xiàn)在假設(shè)你登錄Facebook。當(dāng)你這樣做時，F(xiàn)acebook必須核實(shí)你是否有其網(wǎng)站的賬戶，因此必須在其數(shù)據(jù)庫中查找你的用戶名。如果你的用戶名為karlmageddon，F(xiàn)acebook可從以A打頭的部分開始查找，但更合乎邏輯的做法是從中間開始查找。這是一個查找問題，在前述所有情況下，都可使用同一種算法來解決問題，這種算法就是二分查找。二分查找是一種算法，其輸入是一個有序的元素列表（必須有序的原因稍后解釋）。如果要查找的元素包含在列表中，二分查找返回其位置；否則返回null。下圖是一個例子。下面的示例說明了二分查找的工作原理。我隨便想一個1～100的數(shù)字。你的目標(biāo)是以最少的次數(shù)猜到這個數(shù)字。你每次猜測后，我會說小了、大了或?qū)α?。假設(shè)你從1開始依次往上猜，猜測過程會是這樣。這是簡單查找，更準(zhǔn)確的說法是傻找。每次猜測都只能排除一個數(shù)字。如果我想的數(shù)字是99，你得猜99次才能猜到！1.2.1更佳的查找方式下面是一種更佳的猜法。從50開始。小了，但排除了一半的數(shù)字！至此，你知道1～50都小了。接下來，你猜75。大了，那余下的數(shù)字又排除了一半！使用二分查找時，你猜測的是中間的數(shù)字，從而每次都將余下的數(shù)字排除一半。接下來，你猜63（50和75中間的數(shù)字）。這就是二分查找，你學(xué)習(xí)了第一種算法！每次猜測排除的數(shù)字個數(shù)如下。不管我心里想的是哪個數(shù)字，你在7次之內(nèi)都能猜到，因?yàn)槊看尾聹y都將排除很多數(shù)字！假設(shè)你要在字典中查找一個單詞，而該字典包含240000個單詞，你認(rèn)為每種查找最多需要多少步？如果要查找的單詞位于字典末尾，使用簡單查找將需要240000步。使用二分查找時，每次排除一半單詞，直到最后只剩下一個單詞。因此，使用二分查找只需18步——少多了！一般而言，對于包含n個元素的列表，用二分查找最多需要log2n步，而簡單查找最多需要n步。對數(shù)你可能不記得什么是對數(shù)了，但很可能記得什么是冪。log10100相當(dāng)于問“將多少個10相乘的結(jié)果為100”。答案是兩個：10×10=100。因此，log10100=2。對數(shù)運(yùn)算是冪運(yùn)算的逆運(yùn)算。對數(shù)是冪運(yùn)算的逆運(yùn)算本書使用大O表示法（稍后介紹）討論運(yùn)行時間時，log指的都是log2。使用簡單查找法查找元素時，在最糟情況下需要查看每個元素。因此，如果列表包含8個數(shù)字，你最多需要檢查8個數(shù)字。而使用二分查找時，最多需要檢查logn個元素。如果列表包含8個元素，你最多需要檢查3個元素，因?yàn)閘og8=3（23=8）。如果列表包含1024個元素，你最多需要檢查10個元素，因?yàn)閘og1024=10（210=1024）。說明本書經(jīng)常會談到log時間，因此你必須明白對數(shù)的概念。如果你不明白，可汗學(xué)院（）有一個不錯的視頻，把這個概念講得很清楚。說明僅當(dāng)列表是有序的時候，二分查找才管用。例如，電話簿中的名字是按字母順序排列的，因此可以使用二分查找來查找名字。如果名字不是按順序排列的，結(jié)果將如何呢？下面來看看如何編寫執(zhí)行二分查找的Python代碼。這里的代碼示例使用了數(shù)組。如果你不熟悉數(shù)組，也不用擔(dān)心，下一章就會介紹。你只需知道，可將一系列元素存儲在一系列相鄰的桶（bucket），即數(shù)組中。這些桶從0開始編號：第一個桶的位置為#0，第二個桶為#1，第三個桶為#2，以此類推。函數(shù)binary_search接受一個有序數(shù)組和一個元素。如果指定的元素包含在數(shù)組中，這個函數(shù)將返回其位置。你將跟蹤要在其中查找的數(shù)組部分——開始時為整個數(shù)組。

low=0

high=len(list)-1

你每次都檢查中間的元素。

mid=(low+high)/2←如果(low+high)不是偶數(shù)，Python自動將mid向下取整。

guess=list[mid]

如果猜的數(shù)字小了，就相應(yīng)地修改low。

ifguess<item:

low=mid+1

如果猜的數(shù)字大了，就修改high。完整的代碼如下。

defbinary_search(list,item):

low=0（以下2行）low和high用于跟蹤要在其中查找的列表部分

high=len(list)—1

whilelow<=high:←只要范圍沒有縮小到只包含一個元素，

mid=(low+high)/2←就檢查中間的元素

guess=list[mid]

ifguess==item:←找到了元素

returnmid

ifguess>item:←猜的數(shù)字大了

high=mid-1

else:←猜的數(shù)字小了

low=mid+1

returnNone←沒有指定的元素

my_list=[1,3,5,7,9]←來測試一下！

printbinary_search(my_list,3)#=>1←別忘了索引從0開始，第二個位置的索引為1

printbinary_search(my_list,-1)#=>None←在Python中，None表示空，它意味著沒有找到指定的元素

練習(xí)1.1假設(shè)有一個包含128個名字的有序列表，你要使用二分查找在其中查找一個名字，請問最多需要幾步才能找到？1.2上面列表的長度翻倍后，最多需要幾步？1.2.2運(yùn)行時間每次介紹算法時，我都將討論其運(yùn)行時間。一般而言，應(yīng)選擇效率最高的算法，以最大限度地減少運(yùn)行時間或占用空間?；氐角懊娴亩植檎?。使用它可節(jié)省多少時間呢？簡單查找逐個地檢查數(shù)字，如果列表包含100個數(shù)字，最多需要猜100次。如果列表包含40億個數(shù)字，最多需要猜40億次。換言之，最多需要猜測的次數(shù)與列表長度相同，這被稱為線性時間（lineartime）。二分查找則不同。如果列表包含100個元素，最多要猜7次；如果列表包含40億個數(shù)字，最多需猜32次。厲害吧？二分查找的運(yùn)行時間為對數(shù)時間（或log時間）。下表總結(jié)了我們發(fā)現(xiàn)的情況。1.3大O表示法大O表示法是一種特殊的表示法，指出了算法的速度有多快。誰在乎呢？實(shí)際上，你經(jīng)常要使用別人編寫的算法，在這種情況下，知道這些算法的速度大有裨益。本節(jié)將介紹大O表示法是什么，并使用它列出一些最常見的算法運(yùn)行時間。1.3.1算法的運(yùn)行時間以不同的速度增加Bob要為NASA編寫一個查找算法，這個算法在火箭即將登陸月球前開始執(zhí)行，幫助計(jì)算著陸地點(diǎn)。這個示例表明，兩種算法的運(yùn)行時間呈現(xiàn)不同的增速。Bob需要做出決定，是使用簡單查找還是二分查找。使用的算法必須快速而準(zhǔn)確。一方面，二分查找的速度更快。Bob必須在10秒鐘內(nèi)找出著陸地點(diǎn)，否則火箭將偏離方向。另一方面，簡單查找算法編寫起來更容易，因此出現(xiàn)bug的可能性更小。Bob可不希望引導(dǎo)火箭著陸的代碼中有bug！為確保萬無一失，Bob決定計(jì)算兩種算法在列表包含100個元素的情況下需要的時間。假設(shè)檢查一個元素需要1毫秒。使用簡單查找時，Bob必須檢查100個元素，因此需要100毫秒才能查找完畢。而使用二分查找時，只需檢查7個元素（log2100大約為7），因此需要7毫秒就能查找完畢。然而，實(shí)際要查找的列表可能包含10億個元素，在這種情況下，簡單查找需要多長時間呢？二分查找又需要多長時間呢？請務(wù)必找出這兩個問題的答案，再接著往下讀。Bob使用包含10億個元素的列表運(yùn)行二分查找，運(yùn)行時間為30毫秒（log21000000000大約為30）。他心里想，二分查找的速度大約為簡單查找的15倍，因?yàn)榱斜戆?00個元素時，簡單查找需要100毫秒，而二分查找需要7毫秒。因此，列表包含10億個元素時，簡單查找需要30×15=450毫秒，完全符合在10秒內(nèi)查找完畢的要求。Bob決定使用簡單查找。這是正確的選擇嗎？不是。實(shí)際上，Bob錯了，而且錯得離譜。列表包含10億個元素時，簡單查找需要10億毫秒，相當(dāng)于11天！為什么會這樣呢？因?yàn)槎植檎液秃唵尾檎业倪\(yùn)行時間的增速不同。也就是說，隨著元素?cái)?shù)量的增加，二分查找需要的額外時間并不多，而簡單查找需要的額外時間卻很多。因此，隨著列表的增長，二分查找的速度比簡單查找快得多。Bob以為二分查找速度為簡單查找的15倍，這不對：列表包含10億個元素時，為3300萬倍。有鑒于此，僅知道算法需要多長時間才能運(yùn)行完畢還不夠，還需知道運(yùn)行時間如何隨列表增長而增加。這正是大O表示法的用武之地。大O表示法指出了算法有多快。例如，假設(shè)列表包含n個元素。簡單查找需要檢查每個元素，因此需要執(zhí)行n次操作。使用大O表示法，這個運(yùn)行時間為O(n)。單位秒呢？沒有——大O表示法指的并非以秒為單位的速度。大O表示法讓你能夠比較操作數(shù)，它指出了算法運(yùn)行時間的增速。再來看一個例子。為檢查長度為n的列表，二分查找需要執(zhí)行l(wèi)ogn次操作。使用大O表示法，這個運(yùn)行時間怎么表示呢？O(logn)。一般而言，大O表示法像下面這樣。這指出了算法需要執(zhí)行的操作數(shù)。之所以稱為大O表示法，是因?yàn)椴僮鲾?shù)前有個大O。這聽起來像笑話，但事實(shí)如此！下面來看一些例子，看看你能否確定這些算法的運(yùn)行時間。1.3.2理解不同的大O運(yùn)行時間下面的示例，你在家里使用紙和筆就能完成。假設(shè)你要畫一個網(wǎng)格，它包含16個格子。算法1一種方法是以每次畫一個的方式畫16個格子。記住，大O表示法計(jì)算的是操作數(shù)。在這個示例中，畫一個格子是一次操作，需要畫16個格子。如果每次畫一個格子，需要執(zhí)行多少次操作呢？畫16個格子需要16步。這種算法的運(yùn)行時間是多少？算法2請嘗試這種算法——將紙折起來。在這個示例中，將紙對折一次就是一次操作。第一次對折相當(dāng)于畫了兩個格子！再折，再折，再折。折4次后再打開，便得到了漂亮的網(wǎng)格！每折一次，格子數(shù)就翻倍，折4次就能得到16個格子！你每折一次，繪制出的格子數(shù)都翻倍，因此4步就能“繪制”出16個格子。這種算法的運(yùn)行時間是多少呢？請搞清楚這兩種算法的運(yùn)行時間之后，再接著往下讀。答案如下：算法1的運(yùn)行時間為O(n)，算法2的運(yùn)行時間為O(logn)。1.3.3大O表示法指出了最糟情況下的運(yùn)行時間假設(shè)你使用簡單查找在電話簿中找人。你知道，簡單查找的運(yùn)行時間為O(n)，這意味著在最糟情況下，必須查看電話簿中的每個條目。如果要查找的是Adit——電話簿中的第一個人，一次就能找到，無需查看每個條目?？紤]到一次就找到了Adit，請問這種算法的運(yùn)行時間是O(n)還是O(1)呢？簡單查找的運(yùn)行時間總是為O(n)。查找Adit時，一次就找到了，這是最佳的情形，但大O表示法說的是最糟的情形。因此，你可以說，在最糟情況下，必須查看電話簿中的每個條目，對應(yīng)的運(yùn)行時間為O(n)。這是一個保證——你知道簡單查找的運(yùn)行時間不可能超過O(n)。說明除最糟情況下的運(yùn)行時間外，還應(yīng)考慮平均情況的運(yùn)行時間，這很重要。最糟情況和平均情況將在第4章討論。1.3.4一些常見的大O運(yùn)行時間下面按從快到慢的順序列出了你經(jīng)常會遇到的5種大O運(yùn)行時間。O(logn)，也叫對數(shù)時間，這樣的算法包括二分查找。O(n)，也叫線性時間，這樣的算法包括簡單查找。O(n*logn)，這樣的算法包括第4章將介紹的快速排序——一種速度較快的排序算法。O(n2)，這樣的算法包括第2章將介紹的選擇排序——一種速度較慢的排序算法。O(n!)，這樣的算法包括接下來將介紹的旅行商問題的解決方案——一種非常慢的算法。假設(shè)你要繪制一個包含16格的網(wǎng)格，且有5種不同的算法可供選擇，這些算法的運(yùn)行時間如上所示。如果你選擇第一種算法，繪制該網(wǎng)格所需的操作數(shù)將為4（log16=4）。假設(shè)你每秒可執(zhí)行10次操作，那么繪制該網(wǎng)格需要0.4秒。如果要繪制一個包含1024格的網(wǎng)格呢？這需要執(zhí)行10（log1024=10）次操作，換言之，繪制這樣的網(wǎng)格需要1秒。這是使用第一種算法的情況。第二種算法更慢，其運(yùn)行時間為O(n)。即要繪制16個格子，需要執(zhí)行16次操作；要繪制1024個格子，需要執(zhí)行1024次操作。執(zhí)行這些操作需要多少秒呢？下面按從快到慢的順序列出了使用這些算法繪制網(wǎng)格所需的時間：還有其他的運(yùn)行時間，但這5種是最常見的。這里做了簡化，實(shí)際上，并不能如此干凈利索地將大O運(yùn)行時間轉(zhuǎn)換為操作數(shù)，但就目前而言，這種準(zhǔn)確度足夠了。等你學(xué)習(xí)其他一些算法后，第4章將回過頭來再次討論大O表示法。當(dāng)前，我們獲得的主要啟示如下。算法的速度指的并非時間，而是操作數(shù)的增速。談?wù)撍惴ǖ乃俣葧r，我們說的是隨著輸入的增加，其運(yùn)行時間將以什么樣的速度增加。算法的運(yùn)行時間用大O表示法表示。O(logn)比O(n)快，當(dāng)需要搜索的元素越多時，前者比后者快得越多。練習(xí)使用大O表示法給出下述各種情形的運(yùn)行時間。1.3在電話簿中根據(jù)名字查找電話號碼。1.4在電話簿中根據(jù)電話號碼找人。（提示：你必須查找整個電話簿。）1.5閱讀電話簿中每個人的電話號碼。1.6閱讀電話簿中姓名以A打頭的人的電話號碼。這個問題比較棘手，它涉及第4章的概念。答案可能讓你感到驚訝！1.3.5旅行商閱讀前一節(jié)時，你可能認(rèn)為根本就沒有運(yùn)行時間為O(n!)的算法。讓我來證明你錯了！下面就是一個運(yùn)行時間極長的算法。這個算法要解決的是計(jì)算機(jī)科學(xué)領(lǐng)域非常著名的旅行商問題，其計(jì)算時間增加得非常快，而有些非常聰明的人都認(rèn)為沒有改進(jìn)空間。有一位旅行商。他需要前往5個城市。這位旅行商（姑且稱之為Opus吧）要前往這5個城市，同時要確保旅程最短。為此，可考慮前往這些城市的各種可能順序。對于每種順序，他都計(jì)算總旅程，再挑選出旅程最短的路線。5個城市有120種不同的排列方式。因此，在涉及5個城市時，解決這個問題需要執(zhí)行120次操作。涉及6個城市時，需要執(zhí)行720次操作（有720種不同的排列方式）。涉及7個城市時，需要執(zhí)行5040次操作！推而廣之，涉及n個城市時，需要執(zhí)行n!（n的階乘）次操作才能計(jì)算出結(jié)果。因此運(yùn)行時間為O(n!)，即階乘時間。除非涉及的城市數(shù)很少，否則需要執(zhí)行非常多的操作。如果涉及的城市數(shù)超過100，根本就不能在合理的時間內(nèi)計(jì)算出結(jié)果——等你計(jì)算出結(jié)果，太陽都沒了。這種算法很糟糕！Opus應(yīng)使用別的算法，可他別無選擇。這是計(jì)算機(jī)科學(xué)領(lǐng)域待解的問題之一。對于這個問題，目前還沒有找到更快的算法，有些很聰明的人認(rèn)為這個問題根本就沒有更巧妙的算法。面對這個問題，我們能做的只是去找出近似答案，更詳細(xì)的信息請參閱第10章。最后需要指出的一點(diǎn)是，高水平的讀者可研究一下二叉樹，這在最后一章做了簡要的介紹。1.4小結(jié)二分查找的速度比簡單查找快得多。O(logn)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。算法運(yùn)行時間并不以秒為單位。算法運(yùn)行時間是從其增速的角度度量的。算法運(yùn)行時間用大O表示法表示。

第2章選擇排序本章內(nèi)容學(xué)習(xí)兩種最基本的數(shù)據(jù)結(jié)構(gòu)——數(shù)組和鏈表，它們無處不在。第1章使用了數(shù)組，其他各章幾乎也都將用到數(shù)組。數(shù)組是個重要的主題，一定要高度重視！但在有些情況下，使用鏈表比使用數(shù)組更合適。本章闡述數(shù)組和鏈表的優(yōu)缺點(diǎn)，讓你能夠根據(jù)要實(shí)現(xiàn)的算法選擇合適的一個。學(xué)習(xí)第一種排序算法。很多算法僅在數(shù)據(jù)經(jīng)過排序后才管用。還記得二分查找嗎？它只能用于有序元素列表。本章將介紹選擇排序。很多語言都內(nèi)置了排序算法，因此你基本上不用從頭開始編寫自己的版本。但選擇排序是下一章將介紹的快速排序的基石?？焖倥判蚴且环N重要的算法，如果你熟悉其他排序算法，理解起來將更容易。需要具備的知識要明白本章的性能分析部分，必須知道大O表示法和對數(shù)。如果你不懂，建議回過頭去閱讀第1章。本書余下的篇幅都會用到大O表示法。2.1內(nèi)存的工作原理假設(shè)你去看演出，需要將東西寄存。寄存處有一個柜子，柜子有很多抽屜。每個抽屜可放一樣?xùn)|西，你有兩樣?xùn)|西要寄存，因此要了兩個抽屜。你將兩樣?xùn)|西存放在這里。現(xiàn)在你可以去看演出了！這大致就是計(jì)算機(jī)內(nèi)存的工作原理。計(jì)算機(jī)就像是很多抽屜的集合體，每個抽屜都有地址。fe0ffeeb是一個內(nèi)存單元的地址。需要將數(shù)據(jù)存儲到內(nèi)存時，你請求計(jì)算機(jī)提供存儲空間，計(jì)算機(jī)給你一個存儲地址。需要存儲多項(xiàng)數(shù)據(jù)時，有兩種基本方式——數(shù)組和鏈表。但它們并非都適用于所有的情形，因此知道它們的差別很重要。接下來介紹數(shù)組和鏈表以及它們的優(yōu)缺點(diǎn)。2.2數(shù)組和鏈表有時候，需要在內(nèi)存中存儲一系列元素。假設(shè)你要編寫一個管理待辦事項(xiàng)的應(yīng)用程序，為此需要將這些待辦事項(xiàng)存儲在內(nèi)存中。應(yīng)使用數(shù)組還是鏈表呢？鑒于數(shù)組更容易掌握，我們先將待辦事項(xiàng)存儲在數(shù)組中。使用數(shù)組意味著所有待辦事項(xiàng)在內(nèi)存中都是相連的（緊靠在一起的）?，F(xiàn)在假設(shè)你要添加第四個待辦事項(xiàng)，但后面的那個抽屜放著別人的東西！這就像你與朋友去看電影，找到地方就坐后又來了一位朋友，但原來坐的地方?jīng)]有空位置，只得再找一個可坐下所有人的地方。在這種情況下，你需要請求計(jì)算機(jī)重新分配一塊可容納4個待辦事項(xiàng)的內(nèi)存，再將所有待辦事項(xiàng)都移到那里。如果又來了一位朋友，而當(dāng)前坐的地方也沒有空位，你們就得再次轉(zhuǎn)移！真是太麻煩了。同樣，在數(shù)組中添加新元素也可能很麻煩。如果沒有了空間，就得移到內(nèi)存的其他地方，因此添加新元素的速度會很慢。一種解決之道是“預(yù)留座位”：即便當(dāng)前只有3個待辦事項(xiàng)，也請計(jì)算機(jī)提供10個位置，以防需要添加待辦事項(xiàng)。這樣，只要待辦事項(xiàng)不超過10個，就無需轉(zhuǎn)移。這是一個不錯的權(quán)變措施，但你應(yīng)該明白，它存在如下兩個缺點(diǎn)。你額外請求的位置可能根本用不上，這將浪費(fèi)內(nèi)存。你沒有使用，別人也用不了。待辦事項(xiàng)超過10個后，你還得轉(zhuǎn)移。因此，這種權(quán)宜措施雖然不錯，但絕非完美的解決方案。對于這種問題，可使用鏈表來解決。2.2.1鏈表鏈表中的元素可存儲在內(nèi)存的任何地方。鏈表的每個元素都存儲了下一個元素的地址，從而使一系列隨機(jī)的內(nèi)存地址串在一起。這猶如尋寶游戲。你前往第一個地址，那里有一張紙條寫著“下一個元素的地址為123”。因此，你前往地址123，那里又有一張紙條，寫著“下一個元素的地址為847”，以此類推。在鏈表中添加元素很容易：只需將其放入內(nèi)存，并將其地址存儲到前一個元素中。使用鏈表時，根本就不需要移動元素。這還可避免另一個問題。假設(shè)你與五位朋友去看一部很火的電影。你們六人想坐在一起，但看電影的人較多，沒有六個在一起的座位。使用數(shù)組時有時就會遇到這樣的情況。假設(shè)你要為數(shù)組分配10000個位置，內(nèi)存中有10000個位置，但不都靠在一起。在這種情況下，你將無法為該數(shù)組分配內(nèi)存！鏈表相當(dāng)于說“我們分開來坐”，因此，只要有足夠的內(nèi)存空間，就能為鏈表分配內(nèi)存。鏈表的優(yōu)勢在插入元素方面，那數(shù)組的優(yōu)勢又是什么呢？2.2.2數(shù)組排行榜網(wǎng)站使用卑鄙的手段來增加頁面瀏覽量。它們不在一個頁面中顯示整個排行榜，而將排行榜的每項(xiàng)內(nèi)容都放在一個頁面中，并讓你單擊Next來查看下一項(xiàng)內(nèi)容。例如，顯示十大電視反派時，不在一個頁面中顯示整個排行榜，而是先顯示第十大反派（Newman）。你必須在每個頁面中單擊Next，才能看到第一大反派（GustavoFring）。這讓網(wǎng)站能夠在10個頁面中顯示廣告，但用戶需要單擊Next九次才能看到第一個，真的是很煩。如果整個排行榜都顯示在一個頁面中，將方便得多。這樣，用戶可單擊排行榜中的人名來獲得更詳細(xì)的信息。鏈表存在類似的問題。在需要讀取鏈表的最后一個元素時，你不能直接讀取，因?yàn)槟悴恢浪幍牡刂罚仨毾仍L問元素#1，從中獲取元素#2的地址，再訪問元素#2并從中獲取元素#3的地址，以此類推，直到訪問最后一個元素。需要同時讀取所有元素時，鏈表的效率很高：你讀取第一個元素，根據(jù)其中的地址再讀取第二個元素，以此類推。但如果你需要跳躍，鏈表的效率真的很低。數(shù)組與此不同：你知道其中每個元素的地址。例如，假設(shè)有一個數(shù)組，它包含五個元素，起始地址為00，那么元素#5的地址是多少呢？只需執(zhí)行簡單的數(shù)學(xué)運(yùn)算就知道：04。需要隨機(jī)地讀取元素時，數(shù)組的效率很高，因?yàn)榭裳杆僬业綌?shù)組的任何元素。在鏈表中，元素并非靠在一起的，你無法迅速計(jì)算出第五個元素的內(nèi)存地址，而必須先訪問第一個元素以獲取第二個元素的地址，再訪問第二個元素以獲取第三個元素的地址，以此類推，直到訪問第五個元素。2.2.3術(shù)語數(shù)組的元素帶編號，編號從0而不是1開始。例如，在下面的數(shù)組中，元素20的位置為1。而元素10的位置為0。這通常會讓新手暈頭轉(zhuǎn)向。從0開始讓基于數(shù)組的代碼編寫起來更容易，因此程序員始終堅(jiān)持這樣做。幾乎所有的編程語言都從0開始對數(shù)組元素進(jìn)行編號。你很快就會習(xí)慣這種做法。元素的位置稱為索引。因此，不說“元素20的位置為1”，而說“元素20位于索引1處”。本書將使用索引來表示位置。下面列出了常見的數(shù)組和鏈表操作的運(yùn)行時間。問題：在數(shù)組中插入元素時，為何運(yùn)行時間為O(n)呢？假設(shè)要在數(shù)組開頭插入一個元素，你將如何做？這需要多長時間？請閱讀下一節(jié)，找出這些問題的答案！練習(xí)2.1假設(shè)你要編寫一個記賬的應(yīng)用程序。你每天都將所有的支出記錄下來，并在月底統(tǒng)計(jì)支出，算算當(dāng)月花了多少錢。因此，你執(zhí)行的插入操作很多，但讀取操作很少。該使用數(shù)組還是鏈表呢？2.2.4在中間插入假設(shè)你要讓待辦事項(xiàng)按日期排列。之前，你在清單末尾添加了待辦事項(xiàng)。但現(xiàn)在你要根據(jù)新增待辦事項(xiàng)的日期將其插入到正確的位置。需要在中間插入元素時，數(shù)組和鏈表哪個更好呢？使用鏈表時，插入元素很簡單，只需修改它前面的那個元素指向的地址。而使用數(shù)組時，則必須將后面的元素都向后移。如果沒有足夠的空間，可能還得將整個數(shù)組復(fù)制到其他地方！因此，當(dāng)需要在中間插入元素時，鏈表是更好的選擇。2.2.5刪除如果你要刪除元素呢？鏈表也是更好的選擇，因?yàn)橹恍栊薷那耙粋€元素指向的地址即可。而使用數(shù)組時，刪除元素后，必須將后面的元素都向前移。不同于插入，刪除元素總能成功。如果內(nèi)存中沒有足夠的空間，插入操作可能失敗，但在任何情況下都能夠?qū)⒃貏h除。下面是常見數(shù)組和鏈表操作的運(yùn)行時間。需要指出的是，僅當(dāng)能夠立即訪問要刪除的元素時，刪除操作的運(yùn)行時間才為O(1)。通常我們都記錄了鏈表的第一個元素和最后一個元素，因此刪除這些元素時運(yùn)行時間為O(1)。數(shù)組和鏈表哪個用得更多呢？顯然要看情況。但數(shù)組用得很多，因?yàn)樗С蛛S機(jī)訪問。有兩種訪問方式：隨機(jī)訪問和順序訪問。順序訪問意味著從第一個元素開始逐個地讀取元素。鏈表只能順序訪問：要讀取鏈表的第十個元素，得先讀取前九個元素，并沿鏈接找到第十個元素。隨機(jī)訪問意味著可直接跳到第十個元素。本書經(jīng)常說數(shù)組的讀取速度更快，這是因?yàn)樗鼈冎С蛛S機(jī)訪問。很多情況都要求能夠隨機(jī)訪問，因此數(shù)組用得很多。數(shù)組和鏈表還被用來實(shí)現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)，這將在本書后面介紹。練習(xí)2.2假設(shè)你要為飯店創(chuàng)建一個接受顧客點(diǎn)菜單的應(yīng)用程序。這個應(yīng)用程序存儲一系列點(diǎn)菜單。服務(wù)員添加點(diǎn)菜單，而廚師取出點(diǎn)菜單并制作菜肴。這是一個點(diǎn)菜單隊(duì)列：服務(wù)員在隊(duì)尾添加點(diǎn)菜單，廚師取出隊(duì)列開頭的點(diǎn)菜單并制作菜肴。你使用數(shù)組還是鏈表來實(shí)現(xiàn)這個隊(duì)列呢？（提示：鏈表擅長插入和刪除，而數(shù)組擅長隨機(jī)訪問。在這個應(yīng)用程序中，你要執(zhí)行的是哪些操作呢？）2.3我們來做一個思考實(shí)驗(yàn)。假設(shè)Facebook記錄一系列用戶名，每當(dāng)有用戶試圖登錄Facebook時，都查找其用戶名，如果找到就允許用戶登錄。由于經(jīng)常有用戶登錄Facebook，因此需要執(zhí)行大量的用戶名查找操作。假設(shè)Facebook使用二分查找算法，而這種算法要求能夠隨機(jī)訪問——立即獲取中間的用戶名?？紤]到這一點(diǎn)，應(yīng)使用數(shù)組還是鏈表來存儲用戶名呢？2.4經(jīng)常有用戶在Facebook注冊。假設(shè)你已決定使用數(shù)組來存儲用戶名，在插入方面數(shù)組有何缺點(diǎn)呢？具體地說，在數(shù)組中添加新用戶將出現(xiàn)什么情況？2.5實(shí)際上，F(xiàn)acebook存儲用戶信息時使用的既不是數(shù)組也不是鏈表。假設(shè)Facebook使用的是一種混合數(shù)據(jù)：鏈表數(shù)組。這個數(shù)組包含26個元素，每個元素都指向一個鏈表。例如，該數(shù)組的第一個元素指向的鏈表包含所有以A打頭的用戶名，第二個元素指向的鏈表包含所有以B打頭的用戶名，以此類推。假設(shè)AditB在Facebook注冊，而你需要將其加入前述數(shù)據(jù)結(jié)構(gòu)中。因此，你訪問數(shù)組的第一個元素，再訪問該元素指向的鏈表，并將AditB添加到這個鏈表末尾。現(xiàn)在假設(shè)你要查找ZakhirH。因此你訪問第26個元素，再在它指向的鏈表（該鏈表包含所有以z打頭的用戶名）中查找ZakhirH。請問，相比于數(shù)組和鏈表，這種混合數(shù)據(jù)結(jié)構(gòu)的查找和插入速度更慢還是更快？你不必給出大O運(yùn)行時間，只需指出這種新數(shù)據(jù)結(jié)構(gòu)的查找和插入速度更快還是更慢。2.3選擇排序有了前面的知識，你就可以學(xué)習(xí)第二種算法——選擇排序了。要理解本節(jié)的內(nèi)容，你必須熟悉數(shù)組、鏈表和大O表示法。假設(shè)你的計(jì)算機(jī)存儲了很多樂曲。對于每個樂隊(duì)，你都記錄了其作品被播放的次數(shù)。你要將這個列表按播放次數(shù)從多到少的順序排列，從而將你喜歡的樂隊(duì)排序。該如何做呢？一種辦法是遍歷這個列表，找出作品播放次數(shù)最多的樂隊(duì)，并將該樂隊(duì)添加到一個新列表中。再次這樣做，找出播放次數(shù)第二多的樂隊(duì)。繼續(xù)這樣做，你將得到一個有序列表。下面從計(jì)算機(jī)科學(xué)的角度出發(fā)，看看這需要多長時間。別忘了，O(n)時間意味著查看列表中的每個元素一次。例如，對樂隊(duì)列表進(jìn)行簡單查找時，意味著每個樂隊(duì)都要查看一次。要找出播放次數(shù)最多的樂隊(duì)，必須檢查列表中的每個元素。正如你剛才看到的，這需要的時間為O(n)。因此對于這種時間為O(n)的操作，你需要執(zhí)行n次。需要的總時間為O(n×n)，即O(n2)。排序算法很有用。你現(xiàn)在可以對如下內(nèi)容進(jìn)行排序：電話簿中的人名旅行日期電子郵件（從新到舊）需要檢查的元素?cái)?shù)越來越少隨著排序的進(jìn)行，每次需要檢查的元素?cái)?shù)在逐漸減少，最后一次需要檢查的元素都只有一個。既然如此，運(yùn)行時間怎么還是O(n2)呢？這個問題問得好，這與大O表示法中的常數(shù)相關(guān)。第4章將詳細(xì)解釋，這里只簡單地說一說。你說得沒錯，并非每次都需要檢查n個元素。第一次需要檢查n個元素，但隨后檢查的元素?cái)?shù)依次為n-1,n–2,…,2和1。平均每次檢查的元素?cái)?shù)為1/2×n，因此運(yùn)行時間為O(n×1/2×n)。但大O表示法省略諸如1/2這樣的常數(shù)（有關(guān)這方面的完整討論，請參閱第4章），因此簡單地寫作O(n×n)或O(n2)。選擇排序是一種靈巧的算法，但其速度不是很快?？焖倥判蚴且环N更快的排序算法，其運(yùn)行時間為O(nlogn)，這將在下一章介紹。示例代碼前面沒有列出對樂隊(duì)進(jìn)行排序的代碼，但下述代碼提供了類似的功能：將數(shù)組元素按從小到大的順序排列。先編寫一個用于找出數(shù)組中最小元素的函數(shù)。

deffindSmallest(arr):

smallest=arr[0]←存儲最小的值

smallest_index=0←存儲最小元素的索引

foriinrange(1,len(arr)):

ifarr[i]<smallest:

smallest=arr[i]

smallest_index=i

returnsmallest_index

現(xiàn)在可以使用這個函數(shù)來編寫選擇排序算法了。

defselectionSort(arr):←對數(shù)組進(jìn)行排序

newArr=[]

foriinrange(len(arr)):

smallest=findSmallest(arr)←找出數(shù)組中最小的元素，并將其加入到新數(shù)組中

newArr.append(arr.pop(smallest))

returnnewArr

printselectionSort([5,3,6,2,10])

2.4小結(jié)計(jì)算機(jī)內(nèi)存猶如一大堆抽屜。需要存儲多個元素時，可使用數(shù)組或鏈表。數(shù)組的元素都在一起。鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址。數(shù)組的讀取速度很快。鏈表的插入和刪除速度很快。在同一個數(shù)組中，所有元素的類型都必須相同（都為int、double等）。

第3章遞歸本章內(nèi)容學(xué)習(xí)遞歸。遞歸是很多算法都使用的一種編程方法，是理解本書后續(xù)內(nèi)容的關(guān)鍵。學(xué)習(xí)如何將問題分成基線條件和遞歸條件。第4章將介紹的分而治之策略使用這種簡單的概念來解決棘手的問題。我懷著激動的心情編寫本章，因?yàn)樗榻B的是遞歸——一種優(yōu)雅的問題解決方法。遞歸是我最喜歡的主題之一，它將人分成三個截然不同的陣營：恨它的、愛它的以及恨了幾年后又愛上它的。我本人屬于第三個陣營。為幫助你理解，現(xiàn)有以下建議。本章包含很多示例代碼，請運(yùn)行它們，以便搞清楚其中的工作原理。請用紙和筆逐步執(zhí)行至少一個遞歸函數(shù)，就像這樣：我使用5來調(diào)用factorial，這將使用4調(diào)用factorial，并將返回結(jié)果乘以5，以此類推。這樣逐步執(zhí)行遞歸函數(shù)可搞明白遞歸函數(shù)的工作原理。本章還包含大量偽代碼。偽代碼是對手頭問題的簡要描述，看著像代碼，但其實(shí)更接近自然語言。3.1遞歸假設(shè)你在祖母的閣樓中翻箱倒柜，發(fā)現(xiàn)了一個上鎖的神秘手提箱。祖母告訴你，鑰匙很可能在下面這個盒子里。這個盒子里有盒子，而盒子里的盒子又有盒子。鑰匙就在某個盒子中。為找到鑰匙，你將使用什么算法？先想想這個問題，再接著往下看。下面是一種方法。(1)創(chuàng)建一個要查找的盒子堆。(2)從盒子堆取出一個盒子，在里面找。(3)如果找到的是盒子，就將其加入盒子堆中，以便以后再查找。(4)如果找到鑰匙，則大功告成！(5)回到第二步。下面是另一種方法。(1)檢查盒子中的每樣?xùn)|西。(2)如果是盒子，就回到第一步。(3)如果是鑰匙，就大功告成！在你看來，哪種方法更容易呢？第一種方法使用的是while循環(huán)：只要盒子堆不空，就從中取一個盒子，并在其中仔細(xì)查找。

deflook_for_key(main_box):

pile=main_box.make_a_pile_to_look_through()

whilepileisnotempty:

box=pile.grab_a_box()

foriteminbox:

ifitem.is_a_box():

pile.append(item)

elifitem.is_a_key():

print"foundthekey!"

第二種方法使用遞歸——函數(shù)調(diào)用自己，這種方法的偽代碼如下。

deflook_for_key(box):

foriteminbox:

ifitem.is_a_box():

look_for_key(item)←遞歸！

elifitem.is_a_key():

print"foundthekey!"

這兩種方法的作用相同，但在我看來，第二種方法更清晰。遞歸只是讓解決方案更清晰，并沒有性能上的優(yōu)勢。實(shí)際上，在有些情況下，使用循環(huán)的性能更好。我很喜歡LeighCaldwell在StackOverflow上說的一句話：“如果使用循環(huán)，程序的性能可能更高；如果使用遞歸，程序可能更容易理解。如何選擇要看什么對你來說更重要?！?1參見\h/a/72694/139117。很多算法都使用了遞歸，因此理解這種概念很重要。3.2基線條件和遞歸條件由于遞歸函數(shù)調(diào)用自己，因此編寫這樣的函數(shù)時很容易出錯，進(jìn)而導(dǎo)致無限循環(huán)。例如，假設(shè)你要編寫一個像下面這樣倒計(jì)時的函數(shù)。

>3...2...1

為此，你可以用遞歸的方式編寫，如下所示。

defcountdown(i):

printi

countdown(i-1)

如果你運(yùn)行上述代碼，將發(fā)現(xiàn)一個問題：這個函數(shù)運(yùn)行起來沒完沒了！

>3...2...1...0...-1...-2...

（要讓腳本停止運(yùn)行，可按Ctrl+C。）編寫遞歸函數(shù)時，必須告訴它何時停止遞歸。正因?yàn)槿绱?，每個遞歸函數(shù)都有兩部分：基線條件（basecase）和遞歸條件（recursivecase）。遞歸條件指的是函數(shù)調(diào)用自己，而基線條件則指的是函數(shù)不再調(diào)用自己，從而避免形成無限循環(huán)。我們來給函數(shù)countdown添加基線條件。

defcountdown(i):

printi

ifi<=0:←基線條件

return

else:←遞歸條件

countdown(i-1)

現(xiàn)在，這個函數(shù)將像預(yù)期的那樣運(yùn)行，如下所示。3.3棧本節(jié)將介紹一個重要的編程概念——調(diào)用棧（callstack）。調(diào)用棧不僅對編程來說很重要，使用遞歸時也必須理解這個概念。假設(shè)你去野外燒烤，并為此創(chuàng)建了一個待辦事項(xiàng)清單——一疊便條。本書之前討論數(shù)組和鏈表時，也有一個待辦事項(xiàng)清單。你可將待辦事項(xiàng)添加到該清單的任何地方，還可刪除任何一個待辦事項(xiàng)。一疊便條要簡單得多：插入的待辦事項(xiàng)放在清單的最前面；讀取待辦事項(xiàng)時，你只讀取最上面的那個，并將其刪除。因此這個待辦事項(xiàng)清單只有兩種操作：壓入（插入）和彈出（刪除并讀?。Ｏ旅鎭砜纯慈绾问褂眠@個待辦事項(xiàng)清單。這種數(shù)據(jù)結(jié)構(gòu)稱為棧。棧是一種簡單的數(shù)據(jù)結(jié)構(gòu)，剛才我們一直在使用它，卻沒有意識到！3.3.1調(diào)用棧計(jì)算機(jī)在內(nèi)部使用被稱為調(diào)用棧的棧。我們來看看計(jì)算機(jī)是如何使用調(diào)用棧的。下面是一個簡單的函數(shù)。

defgreet(name):

print"hello,"+name+"!"

greet2(name)

print"gettingreadytosaybye..."

bye()

這個函數(shù)問候用戶，再調(diào)用另外兩個函數(shù)。這兩個函數(shù)的代碼如下。

defgreet2(name):

print"howareyou,"+name+"?"

defbye():

print"okbye!"

下面詳細(xì)介紹調(diào)用函數(shù)時發(fā)生的情況。說明在Python中，print是一個函數(shù)，但出于簡化考慮，這里假設(shè)它不是函數(shù)。你也這樣假設(shè)就行了。假設(shè)你調(diào)用greet("maggie")，計(jì)算機(jī)將首先為該函數(shù)調(diào)用分配一塊內(nèi)存。我們來使用這些內(nèi)存。變量name被設(shè)置為maggie，這需要存儲到內(nèi)存中。每當(dāng)你調(diào)用函數(shù)時，計(jì)算機(jī)都像這樣將函數(shù)調(diào)用涉及的所有變量的值存儲到內(nèi)存中。接下來，你打印hello,maggie!，再調(diào)用greet2("maggie")。同樣，計(jì)算機(jī)也為這個函數(shù)調(diào)用分配一塊內(nèi)存。計(jì)算機(jī)使用一個棧來表示這些內(nèi)存塊，其中第二個內(nèi)存塊位于第一個內(nèi)存塊上面。你打印howareyou,maggie?，然后從函數(shù)調(diào)用返回。此時，棧頂?shù)膬?nèi)存塊被彈出?，F(xiàn)在，棧頂?shù)膬?nèi)存塊是函數(shù)greet的，這意味著你返回到了函數(shù)greet。當(dāng)你調(diào)用函數(shù)greet2時，函數(shù)greet只執(zhí)行了一部分。這是本節(jié)的一個重要概念：調(diào)用另一個函數(shù)時，當(dāng)前函數(shù)暫停并處于未完成狀態(tài)。該函數(shù)的所有變量的值都還在內(nèi)存中。執(zhí)行完函數(shù)greet2后，你回到函數(shù)greet，并從離開的地方開始接著往下執(zhí)行：首先打印gettingreadytosaybye…，再調(diào)用函數(shù)bye。在棧頂添加了函數(shù)bye的內(nèi)存塊。然后，你打印okbye!，并從這個函數(shù)返回?，F(xiàn)在你又回到了函數(shù)greet。由于沒有別的事情要做，你就從函數(shù)greet返回。這個棧用于存儲多個函數(shù)的變量，被稱為調(diào)用棧。練習(xí)3.1根據(jù)下面的調(diào)用棧，你可獲得哪些信息？下面來看看遞歸函數(shù)的調(diào)用棧。3.3.2遞歸調(diào)用棧遞歸函數(shù)也使用調(diào)用棧！來看看遞歸函數(shù)factorial的調(diào)用棧。factorial(5)寫作5!，其定義如下：5!=5*4*3*2*1。同理，factorial(3)為3*2*1。下面是計(jì)算階乘的遞歸函數(shù)。

deffact(x):

ifx==1:

return1

else:

returnx*fact(x-1)

下面來詳細(xì)分析調(diào)用fact(3)時調(diào)用棧是如何變化的。別忘了，棧頂?shù)姆娇蛑赋隽水?dāng)前執(zhí)行到了什么地方。注意，每個fact調(diào)用都有自己的x變量。在一個函數(shù)調(diào)用中不能訪問另一個的x變量。棧在遞歸中扮演著重要角色。在本章開頭的示例中，有兩種尋找鑰匙的方法。下面再次列出了第一種方法。使用這種方法時，你創(chuàng)建一個待查找的盒子堆，因此你始終知道還有哪些盒子需要查找。但使用遞歸方法時，沒有盒子堆。既然沒有盒子堆，那算法怎么知道還有哪些盒子需要查找呢？下面是一個例子。此時，調(diào)用棧類似于下面這樣。原來“盒子堆”存儲在了棧中！這個棧包含未完成的函數(shù)調(diào)用，每個函數(shù)調(diào)用都包含還未檢查完的盒子。使用棧很方便，因?yàn)槟銦o需自己跟蹤盒子堆——棧替你這樣做了。使用棧雖然很方便，但是也要付出代價(jià)：存儲詳盡的信息可能占用大量的內(nèi)存。每個函數(shù)調(diào)用都要占用一定的內(nèi)存，如果棧很高，就意味著計(jì)算機(jī)存儲了大量函數(shù)調(diào)用的信息。在這種情況下，你有兩種選擇。重新編寫代碼，轉(zhuǎn)而使用循環(huán)。使用尾遞歸。這是一個高級遞歸主題，不在本書的討論范圍內(nèi)。另外，并非所有的語言都支持尾遞歸。練習(xí)3.2假設(shè)你編寫了一個遞歸函數(shù)，但不小心導(dǎo)致它沒完沒了地運(yùn)行。正如你看到的，對于每次函數(shù)調(diào)用，計(jì)算機(jī)都將為其在棧中分配內(nèi)存。遞歸函數(shù)沒完沒了地運(yùn)行時，將給棧帶來什么影響？3.4小結(jié)遞歸指的是調(diào)用自己的函數(shù)。每個遞歸函數(shù)都有兩個條件：基線條件和遞歸條件。棧有兩種操作：壓入和彈出。所有函數(shù)調(diào)用都進(jìn)入調(diào)用棧。調(diào)用?？赡芎荛L，這將占用大量的內(nèi)存。

第4章快速排序本章內(nèi)容學(xué)習(xí)分而治之。有時候，你可能會遇到使用任何已知的算法都無法解決的問題。優(yōu)秀的算法學(xué)家遇到這種問題時，不會就此放棄，而是嘗試使用掌握的各種問題解決方法來找出解決方案。分而治之是你學(xué)習(xí)的第一種通用的問題解決方法。學(xué)習(xí)快速排序——一種常用的優(yōu)雅的排序算法。快速排序使用分而治之的策略。前一章深入介紹了遞歸，本章的重點(diǎn)是使用學(xué)到的新技能來解決問題。我們將探索分而治之（divideandconquer，D&C）——一種著名的遞歸式問題解決方法。本書將深入算法的核心。只能解決一種問題的算法畢竟用處有限，而D&C提供了解決問題的思路，是另一個可供你使用的工具。面對新問題時，你不再束手無策，而是自問：“使用分而治之能解決嗎？”在本章末尾，你將學(xué)習(xí)第一個重要的D&C算法——快速排序?？焖倥判蚴且环N排序算法，速度比第2章介紹的選擇排序快得多，實(shí)屬優(yōu)雅代碼的典范。4.1分而治之D&C并不那么容易掌握，我將通過三個示例來介紹。首先，介紹一個直觀的示例；然后，介紹一個代碼示例，它不那么好看，但可能更容易理解；最后，詳細(xì)介紹快速排序——一種使用D&C的排序算法。假設(shè)你是農(nóng)場主，有一小塊土地。你要將這塊地均勻地分成方塊，且分出的方塊要盡可能大。顯然，下面的分法都不符合要求。如何將一塊地均勻地分成方塊，并確保分出的方塊是最大的呢？使用D&C策略！D&C算法是遞歸的。使用D&C解決問題的過程包括兩個步驟。(1)找出基線條件，這種條件必須盡可能簡單。(2)不斷將問題分解（或者說縮小規(guī)模），直到符合基線條件。下面就來使用D&C找出前述問題的解決方案?？赡隳苁褂玫淖畲蠓綁K有多大呢？首先，找出基線條件。最容易處理的情況是，一條邊的長度是另一條邊的整數(shù)倍。如果一邊長25m，另一邊長50m，那么可使用的最大方塊為25m×25m。換言之，可以將這塊地分成兩個這樣的方塊。現(xiàn)在需要找出遞歸條件，這正是D&C的用武之地。根據(jù)D&C的定義，每次遞歸調(diào)用都必須縮小問題的規(guī)模。如何縮小前述問題的規(guī)模呢？我們首先找出這塊地可容納的最大方塊。你可以從這塊地中劃出兩個640m×640m的方塊，同時余下一小塊地?，F(xiàn)在是頓悟時刻：何不對余下的那一小塊地使用相同的算法呢？最初要劃分的土地尺寸為1680m×640m，而現(xiàn)在要劃分的土地更小，為640m×400m。適用于這小塊地的最大方塊，也是適用于整塊地的最大方塊。換言之，你將均勻劃分1680m×640m土地的問題，簡化成了均勻劃分640m×400m土地的問題！歐幾里得算法前面說“適用于這小塊地的最大方塊，也是適用于整塊地的最大方塊”，如果你覺得這一點(diǎn)不好理解，也不用擔(dān)心。這確實(shí)不好理解，但遺憾的是，要證明這一點(diǎn)，需要的篇幅有點(diǎn)長，在本書中無法這樣做，因此你只能選擇相信這種說法是正確的。如果你想搞明白其中的原因，可參閱歐幾里得算法?？珊箤W(xué)院很清楚地闡述了這種算法，網(wǎng)址為\h/computing/computer-science/ryptography/modarithmetic/a/the-euclidean-algorithm。下面再次使用同樣的算法。對于640m×400m的土地，可從中劃出的最大方塊為400m×400m。這將余下一塊更小的土地，其尺寸為400m×240m。你可從這塊土地中劃出最大的方塊，余下一塊更小的土地，其尺寸為240m×160m。接下來，從這塊土地中劃出最大的方塊，余下一塊更小的土地。余下的這塊土地滿足基線條件，因?yàn)?60是80的整數(shù)倍。將這塊土地分成兩個方塊后，將不會余下任何土地！因此，對于最初的那片土地，適用的最大方塊為80m×80m。這里重申一下D&C的工作原理：(1)找出簡單的基線條件；(2)確定如何縮小問題的規(guī)模，使其符合基線條件。D&C并非可用于解決問題的算法，而是一種解決問題的思路。我們再來看一個例子。給定一個數(shù)字?jǐn)?shù)組。你需要將這些數(shù)字相加，并返回結(jié)果。使用循環(huán)很容易完成這種任務(wù)。

defsum(arr):

total=0

forxinarr:

total+=x

returntotal

printsum([1,2,3,4])

但如何使用遞歸函數(shù)來完成這種任務(wù)呢？第一步：找出基線條件。最簡單的數(shù)組什么樣呢？請想想這個問題，再接著往下讀。如果數(shù)組不包含任何元素或只包含一個元素，計(jì)算總和將非常容易。因此這就是基線條件。第二步：每次遞歸調(diào)用都必須離空數(shù)組更近一步。如何縮小問題的規(guī)模呢？下面是一種辦法。這與下面的版本等效。這兩個版本的結(jié)果都為12，但在第二個版本中，給函數(shù)sum傳遞的數(shù)組更短。換言之，這縮小了問題的規(guī)模！函數(shù)sum的工作原理類似于下面這樣。這個函數(shù)的運(yùn)行過程如下。別忘了，遞歸記錄了狀態(tài)。提示編寫涉及數(shù)組的遞歸函數(shù)時，基線條件通常是數(shù)組為空或只包含一個元素。陷入困境時，請檢查基線條件是不是這樣的。函數(shù)式編程一瞥你可能想，既然使用循環(huán)可輕松地完成任務(wù)，為何還要使用遞歸方式呢？看看函數(shù)式編程你就明白了！諸如Haskell等函數(shù)式編程語言沒有循環(huán)，因此你只能使用遞歸來編寫這樣的函數(shù)。如果你對遞歸有深入的認(rèn)識，函數(shù)式編程語言學(xué)習(xí)起來將更容易。例如，使用Haskell時，你可能這樣編寫函數(shù)sum。

sum[]=0←基線條件

sum(x:xs)=x+(sumxs)←遞歸條件

注意，這就像是你有函數(shù)的兩個定義。符合基線條件時運(yùn)行第一個定義，符合遞歸條件時運(yùn)行第二個定義。也可以使用Haskell語言中的if語句來編寫這個函數(shù)。

sumarr=ifarr==[]

then0

else(headarr)+(sum(tailarr))

但前一個版本更容易理解。Haskell大量使用了遞歸，因此它提供了各種方便實(shí)現(xiàn)遞歸的語法。如果你喜歡遞歸或想學(xué)習(xí)一門新語言，可以研究一下Haskell。練習(xí)4.1請編寫前述sum函數(shù)的代碼。4.2編寫一個遞歸函數(shù)來計(jì)算列表包含的元素?cái)?shù)。4.3找出列表中最大的數(shù)字。4.4還記得第1章介紹的二分查找嗎？它也是一種分而治之算法。你能找出二分查找算法的基線條件和遞歸條件嗎？4.2快速排序快速排序是一種常用的排序算法，比選擇排序快得多。例如，C語言標(biāo)準(zhǔn)庫中的函數(shù)qsort實(shí)現(xiàn)的就是快速排序?？焖倥判蛞彩褂昧薉&C。下面來使用快速排序?qū)?shù)組進(jìn)行排序。對排序算法來說，最簡單的數(shù)組什么樣呢？還記得前一節(jié)的“提示”嗎？就是根本不需要排序的數(shù)組。因此，基線條件為數(shù)組為空或只包含一個元素。在這種情況下，只需原樣返回?cái)?shù)組——根本就不用排序。

defquicksort(array):

iflen(array)<2:

returnarray

我們來看看更長的數(shù)組。對包含兩個元素的數(shù)組進(jìn)行排序也很容易。包含三個元素的數(shù)組呢？別忘了，你要使用D&C，因此需要將數(shù)組分解，直到滿足基線條件。下面介紹快速排序的工作原理。首先，從數(shù)組中選擇一個元素，這個元素被稱為基準(zhǔn)值（pivot）。稍后再介紹如何選擇合適的基準(zhǔn)值。我們暫時將數(shù)組的第一個元素用作基準(zhǔn)值。接下來，找出比基準(zhǔn)值小的元素以及比基準(zhǔn)值大的元素。這被稱為分區(qū)（partitioning）?，F(xiàn)在你有：一個由所有小于基準(zhǔn)值的數(shù)字組成的子數(shù)組；基準(zhǔn)值；一個由所有大于基準(zhǔn)值的數(shù)組組成的子數(shù)組。這里只是進(jìn)行了分區(qū)，得到的兩個子數(shù)組是無序的。但如果這兩個數(shù)組是有序的，對整個數(shù)組進(jìn)行排序?qū)⒎浅Ｈ菀?。如果子?shù)組是有序的，就可以像下面這樣合并得到一個有序的數(shù)組：左邊的數(shù)組+基準(zhǔn)值+右邊的數(shù)組。在這里，就是[10,15]+[33]+[]，結(jié)果為有序數(shù)組[10,15,33]。如何對子數(shù)組進(jìn)行排序呢？對于包含兩個元素的數(shù)組（左邊的子數(shù)組）以及空數(shù)組（右邊的子數(shù)組），快速排序知道如何將它們排序，因此只要對這兩個子數(shù)組進(jìn)行快速排序，再合并結(jié)果，就能得到一個有序數(shù)組！

quicksort([15,10])+[33]+quicksort([])

>[10,15,33]←一個有序數(shù)組

不管將哪個元素用作基準(zhǔn)值，這都管用。假設(shè)你將15用作基準(zhǔn)值。這個子數(shù)組都只有一個元素，而你知道如何對這些數(shù)組進(jìn)行排序?，F(xiàn)在你就知道如何對包含三個元素的數(shù)組進(jìn)行排序了，步驟如下。(1)選擇基準(zhǔn)值。(2)將數(shù)組分成兩個子數(shù)組：小于基準(zhǔn)值的元素和大于基準(zhǔn)值的元素。(3)對這兩個子數(shù)組進(jìn)行快速排序。包含四個元素的數(shù)組呢？假設(shè)你也將33用作基準(zhǔn)值。左邊的子數(shù)組包含三個元素，而你知道如何對包含三個元素的數(shù)組進(jìn)行排序：對其遞歸地調(diào)用快速排序。因此你能夠?qū)Π膫€元素的數(shù)組進(jìn)行排序。如果能夠?qū)Π膫€元素的數(shù)組進(jìn)行排序，就能對包含五個元素的數(shù)組進(jìn)行排序。為什么呢？假設(shè)有下面這樣一個包含五個元素的數(shù)組。根據(jù)選擇的基準(zhǔn)值，對這個數(shù)組進(jìn)行分區(qū)的各種可能方式如下。注意，這些子數(shù)組包含的元素個數(shù)都在0～4內(nèi)，而你已經(jīng)知道如何使用快速排序?qū)Π?～4個元素的數(shù)組進(jìn)行排序！因此，不管如何選擇基準(zhǔn)值，你都可對劃分得到的兩個子數(shù)組遞歸地進(jìn)行快速排序。例如，假設(shè)你將3用作基準(zhǔn)值，可對得到的子數(shù)組進(jìn)行快速排序。將子數(shù)組排序后，將它們合并，得到一個有序數(shù)組。即便你將5用作基準(zhǔn)值，這也可行。將任何元素用作基準(zhǔn)值都可行，因此你能夠?qū)Π鍌€元素的數(shù)組進(jìn)行排序。同理，你能夠?qū)Π鶄€元素的數(shù)組進(jìn)行排序，以此類推。歸納證明剛才你大致見識了歸納證明！歸納證明是一種證明算法行之有效的方式，它分兩步：基線條件和歸納條件。是不是有點(diǎn)似曾相識的感覺？例如，假設(shè)我要證明我能爬到梯子的最上面。遞歸條件是這樣的：如果我站在一個橫檔上，就能將腳放到下一個橫檔上。換言之，如果我站在第二個橫檔上，就能爬到第三個橫檔。這就是歸納條件。而基線條件是這樣的，即我已經(jīng)站在第一個橫檔上。因此，通過每次爬一個橫檔，我就能爬到梯子最頂端。對于快速排序，可使用類似的推理。在基線條件中，我證明這種算法對空數(shù)組或包含一個元素的數(shù)組管用。在歸納條件中，我證明如果快速排序?qū)Π粋€元素的數(shù)組管用，對包含兩個元素的數(shù)組也將管用；如果它對包含兩個元素的數(shù)組管用，對包含三個元素的數(shù)組也將管用，以此類推。因此，我可以說，快速排序?qū)θ魏伍L度的數(shù)組都管用。這里不再深入討論歸納證明，但它很有趣，并與D&C協(xié)同發(fā)揮作用。下面是快速排序的代碼。

defquicksort(array):

iflen(array)<2:

returnarray←基線條件：為空或只包含一個元素的數(shù)組是“有序”的

else:

pivot=array[0]←遞歸條件

less=[iforiinarray[1:]ifi<=pivot]←由所有小于基準(zhǔn)值的元素組成的子數(shù)組

greater=[iforiinarray[1:]ifi>pivot]←由所有大于基準(zhǔn)值的元素組成的子數(shù)組

returnquicksort(less)+[pivot]+quicksort(greater)

printquicksort([10,5,2,3])

4.3再談大O表示法快速排序的獨(dú)特之處在于，其速度取決于選擇的基準(zhǔn)值。在討論快速排序的運(yùn)行時間前，我們再來看看最常見的大O運(yùn)行時間。上述圖表中的時間是基于每秒執(zhí)行10次操作計(jì)算得到的。這些數(shù)據(jù)并不準(zhǔn)確，這里提供它們只是想讓你對這些運(yùn)行時間的差別有大致認(rèn)識。實(shí)際上，計(jì)算機(jī)每秒執(zhí)行的操作遠(yuǎn)不止10次。對于每種運(yùn)行時間，本書還列出了相關(guān)的算法。來看看第2章介紹的選擇排序，其運(yùn)行時間為O(n2)，速度非常慢。還有一種名為合并排序（mergesort）的排序算法，其運(yùn)行時間為O(nlogn)，比選擇排序快得多！快速排序的情況比較棘手，在最糟情況下，其運(yùn)行時間為O(n2)。與選擇排序一樣慢！但這是最糟情況。在平均情況下，快速排序的運(yùn)行時間為O(nlogn)。你可能會有如下疑問。這里說的最糟情況和平均情況是什么意思呢？若快速排序在平均情況下的運(yùn)行時間為O(nlogn)，而合并排序的運(yùn)行時間總是O(nlogn)，為何不使用合并排序？它不是更快嗎？4.3.1比較合并排序和快速排序假設(shè)有下面這樣打印列表中每個元素的簡單函數(shù)。

defprint_items(list):

foriteminlist:

printitem

這個函數(shù)遍歷列表中的每個元素并將其打印出來。它迭代整個列表一次，因此運(yùn)行時間為O(n)。現(xiàn)在假設(shè)你對這個函數(shù)進(jìn)行修改，使其在打印每個元素前都休眠1秒鐘。

fromtimeimportsleep

defprint_items2(list):

foriteminlist:

sleep(1)

printitem

它在打印每個元素前都暫停1秒鐘。假設(shè)你使用這兩個函數(shù)來打印一個包含5個元素的列表。這兩個函數(shù)都迭代整個列表一次，因此它們的運(yùn)行時間都為O(n)。你認(rèn)為哪個函數(shù)的速度更快呢？我認(rèn)為print_items要快得多，因?yàn)樗鼪]有在每次打印元素前都暫停1秒鐘。因此，雖然使用大O表示法表示時，這兩個函數(shù)的速度相同，但實(shí)際上print_items的速度更快。在大O表示法O(n)中，n實(shí)際上指的是這樣的。c是算法所需的固定時間量，被稱為常量。例如，print_items所需的時間可能是10毫秒*n，而print_items2所需的時間為1秒*n。通常不考慮這個常量，因?yàn)槿绻麅煞N算法的大O運(yùn)行時間不同，這種常量將無關(guān)緊要。就拿二分查找和簡單查找來舉例說明。假設(shè)這兩種算法的運(yùn)行時間包含如下常量。你可能認(rèn)為，簡單查找的常量為10毫秒，而二分查找的常量為1秒，因此簡單查找的速度要快得多?，F(xiàn)在假設(shè)你要在包含40億個元素的列表中查找，所需時間將如下。正如你看到的，二分查找的速度還是快得多，常量根本沒有什么影響。但有時候，常量的影響可能很大，對快速查找和合并查找來說就是如此?？焖俨檎业某Ａ勘群喜⒉檎倚。虼巳绻鼈兊倪\(yùn)行時間都為O(nlogn)，快速查找的速度將更快。實(shí)際上，快速查找的速度確實(shí)更快，因?yàn)橄鄬τ谟錾献钤闱闆r，它遇上平均情況的可能性要大得多。此時你可能會問，何為平均情況，何為最糟情況呢？4.3.2平均情況和最糟情況快速排序的性能高度依賴于你選擇的基準(zhǔn)值。假設(shè)你總是將第一個元素用作基準(zhǔn)值，且要處理的數(shù)組是有序的。由于快速排序算法不檢查輸入數(shù)組是否有序，因此它依然嘗試對其進(jìn)行排序。注意，數(shù)組并沒有被分成兩半，相反，其中一個子數(shù)組始終為空，這導(dǎo)致調(diào)用棧非常長?，F(xiàn)在假設(shè)你總是將中間的元素用作基準(zhǔn)值，在這種情況下，調(diào)用棧如下。調(diào)用棧短得多！因?yàn)槟忝看味紝?shù)組分成兩半，所以不需要那么多遞歸調(diào)用。你很快就到達(dá)了基線條件，因此調(diào)用棧短得多。第一個示例展示的是最糟情況，而第二個示例展示的是最佳情況。在最糟情況下，棧長為O(n)，而在最佳情況下，棧長為O(logn)?，F(xiàn)在來看看棧的第一層。你將一個元素用作基準(zhǔn)值，并將其他的元素劃分到兩個子數(shù)組中。這涉及數(shù)組中的全部8個元素，因此該操作的時間為O(n)。在調(diào)用棧的第一層，涉及全部8個元素，但實(shí)際上，在調(diào)用棧的每層都涉及O(n)個元素。即便以不同的方式劃分?jǐn)?shù)組，每次也將涉及O(n)個元素。因此，完成每層所需的時間都為O(n)。在這個示例中，層數(shù)為O(logn)（用技術(shù)術(shù)語說，調(diào)用棧的高度為O(logn)），而每層需要的時間為O(n)。因此整個算法需要的時間為O(n)*O(logn)=O(nlogn)。這就是最佳情況。在最糟情況下，有O(n)層，因此該算法的運(yùn)行時間為O(n)*O(n)=O(n2)。知道嗎？這里要告訴你的是，最佳情況也是平均情況。只要你每次都隨機(jī)地選擇一個數(shù)組元素作為基準(zhǔn)值，快速排序的平均運(yùn)行時間就將為O(nlogn)。快速排序是最快的排序算法之一，也是D&C典范。練習(xí)使用大O表示法時，下面各種操作都需要多長時間？4.5打印數(shù)組中每個元素的值。4.6將數(shù)組中每個元素的值都乘以2。4.7只將數(shù)組中第一個元素的值乘以2。4.8根據(jù)數(shù)組包含的元素創(chuàng)建一個乘法表，即如果數(shù)組為[2,3,7,8,10]，首先將每個元素都乘以2，再將每個元素都乘以3，然后將每個元素都乘以7，以此類推。4.4小結(jié)D&C將問題逐步分解。使用D&C處理列表時，基線條件很可能是空數(shù)組或只包含一個元素的數(shù)組。實(shí)現(xiàn)快速排序時，請隨機(jī)地選擇用作基準(zhǔn)值的元素?？焖倥判虻钠骄\(yùn)行時間為O(nlogn)。大O表示法中的常量有時候事關(guān)重大，這就是快速排序比合并排序快的原因所在。比較簡單查找和二分查找時，常量幾乎無關(guān)緊要，因?yàn)榱斜砗荛L時，O(logn)的速度比O(n)快得多。

第5章散列表本章內(nèi)容學(xué)習(xí)散列表——最有用的基本數(shù)據(jù)結(jié)構(gòu)之一。散列表用途廣泛，本章將介紹其常見的用途。學(xué)習(xí)散列表的內(nèi)部機(jī)制：實(shí)現(xiàn)、沖突和散列函數(shù)。這將幫助你理解如何分析散列表的性能。假設(shè)你在一家雜貨店上班。有顧客來買東西時，你得在一個本子中查找價(jià)格。如果本子的內(nèi)容不是按字母順序排列的，你可能為查找蘋果（apple）的價(jià)格而瀏覽每一行，這需要很長的時間。此時你使用的是第1章介紹的簡單查找，需要瀏覽每一行。還記得這需要多長時間嗎？O(n)。如果本子的內(nèi)容是按字母順序排列的，可使用二分查找來找出蘋果的價(jià)格，這需要的時間更短，為O(logn)。需要提醒你的是，運(yùn)行時間O(n)和O(logn)之間有天壤之別！假設(shè)你每秒能夠看10行，使用簡單查找和二分查找所需的時間將如下。你知道，二分查找的速度非?？?。但作為收銀員，在本子中查找價(jià)格是件很痛苦的事情，哪怕本子的內(nèi)容是有序的。在查找價(jià)格時，你都能感覺到顧客的怒氣?？磥碚娴男枰幻軌蛴涀∷猩唐穬r(jià)格的雇員，這樣你就不用查找了：問她就能馬上知道答案。不管商品有多少，這位雇員（假設(shè)她的名字為Maggie）報(bào)出任何商品的價(jià)格的時間都為O(1)，速度比二分查找都快。真是太厲害了！如何聘到這樣的雇員呢？下面從數(shù)據(jù)結(jié)構(gòu)的角度來看看。前面介紹了兩種數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表（其實(shí)還有棧，但棧并不能用于查找）。你可使用數(shù)組來實(shí)現(xiàn)記錄商品價(jià)格的本子。這種數(shù)組的每個元素包含兩項(xiàng)內(nèi)容：商品名和價(jià)格。如果將這個數(shù)組按商品名排序，就可使用二分查找在其中查找商品的價(jià)格。這樣查找價(jià)格的時間將為O(logn)。然而，你希望查找商品價(jià)格的時間為O(1)，即你希望查找速度像Maggie那么快，這是散列函數(shù)的用武之地。5.1散列函數(shù)散列函數(shù)是這樣的函數(shù)，即無論你給它什么數(shù)據(jù)，它都還你一個數(shù)字。如果用專業(yè)術(shù)語來表達(dá)的話，我們會說，散列函數(shù)“將輸入映射到數(shù)字”。你可能認(rèn)為散列函數(shù)輸出的數(shù)字沒什么規(guī)律，但其實(shí)散列函數(shù)必須滿足一些要求。它必須是一致的。例如，假設(shè)你輸入apple時得到的是4，那么每次輸入apple時，得到的都必須為4。如果不是這樣，散列表將毫無用處。它應(yīng)將不同的輸入映射到不同的數(shù)字。例如，如果一個散列函數(shù)不管輸入是什么都返回1