第一章 算法簡介

1.1引言

算法是一組完成任務的指令膏燕。

1.2二分查找

二分查找是一種算法，其輸入是一個有序的元素列表(必須有序的原因稍后解釋)。如果要查找的元素包含在列表中，二分查找返回其位置;否則返回null泣刹。

對于包含n個元素的列表，用二分查找最多需要log2n步犀被，而簡單查找最多需要n步项玛。

對數(shù)運算是冪運算的逆運算。例如：log10100 = 2

僅當列表是有序的時候弱判，二分查找才管用。

一般而言锥惋，應選擇效率最高的算 法昌腰，以最大限度地減少運行時間或占用空間开伏。

最多需要猜測的次數(shù)與列表長度相同，這被稱為線性 時間(linear time)遭商。

二分查找的運行時間為對數(shù)時間(或log時間)固灵。

1.3大O表示法

大O表示法是一種特殊的表示法，指出了算法的速度有多快劫流。

兩種算法的運行時間呈現(xiàn)不同的增速巫玻。也就是說，隨著元素數(shù)量的增加祠汇，二分查找需要的額外時間并不多仍秤，而簡單查找需要的額外時間卻很多。

下面按從快到慢的順序列出了你經(jīng)常會遇到的5種大O運行時間：

a) O(log n)可很，也叫對數(shù)時間诗力，這樣的算法包括二分查找。

b) O(n)我抠，也叫線性時間苇本，這樣的算法包括簡單查找。

c) O(n * log n)菜拓，這樣的算法包括快速排序——一種速度較快的排序算法瓣窄。 ?

d) O(n2)，這樣的算法包括選擇排序——一種速度較慢的排序算法纳鼎。

e) O(n!)俺夕，這樣的算法包括旅行商問題的解決方案——一種非常慢的算法。

我們獲得的主要啟示如下喷橙。

a) 算法的速度指的并非時間啥么，而是操作數(shù)的增速。

b) 談論算法的速度時贰逾，我們說的是隨著輸入的增加悬荣，其運行時間將以什么樣的速度增加。

c) 算法的運行時間用大O表示法表示疙剑。

d) O(log n)比O(n)快氯迂，當需要搜索的元素越多時，前者比后者快得越多言缤。

第二章 選擇排序

2.1 內(nèi)存的工作原理

需要將數(shù)據(jù)存儲到內(nèi)存時嚼蚀，你請求計算機提供存儲空間，計算機給你一個存儲地址管挟。需要存儲多項數(shù)據(jù)時轿曙，有兩種基本方式——數(shù)組和鏈表。

2.2 數(shù)組和鏈表

鏈表中的元素可存儲在內(nèi)存的任何地方。

鏈表的每個元素都存儲了下一個元素的地址导帝，從而使一系列隨機的內(nèi)存地址串在一起守谓。

在需要讀取鏈表的最后一個元素時，你不能直接讀取您单，因為你不知道 它所處的地址斋荞，必須先訪問元素#1，從中獲取元素#2的地址虐秦，再訪問元素#2并從中獲取元素#3的地址平酿，以此類推，直到訪問最后一個元素悦陋。

需要隨機地讀取元素時蜈彼，數(shù)組的效率很高，因為可迅 速找到數(shù)組的任何元素叨恨。

數(shù)組的元素帶編號柳刮，編號從0而不是1開始。

元素的位置稱為索引痒钝。

需要在中間插入元素時秉颗，插入元素很簡單，只需修改 它前面的那個元素指向的地址送矩。而使用數(shù)組時蚕甥，則必須將后面的元素都向后移。

當需要在中間插入元素時栋荸，鏈表是更好的選擇菇怀。

如果你要刪除元素呢?鏈表也是更好的選擇，因為只需修改前一個元素指向的地址即可晌块。而使用數(shù)組時爱沟，刪除元素后，必須將后面的元素都向前移匆背。

數(shù)組和鏈表哪個用得更多呢?顯然要看情況呼伸。但數(shù)組用得很多，因為它支持隨機訪問钝尸。有兩種訪問方式:隨機訪問和順序訪問括享。順序訪問意味著從第一個元素開始逐個地讀取元素。鏈表只能順序訪問:要讀取鏈表的第十個元素珍促，得先讀取前九個元素铃辖，并沿鏈接找到第十個元素。隨機 10訪問意味著可直接跳到第十個元素猪叙。

下面是常見數(shù)組和鏈表操作的運行時間娇斩。

2.3 選擇排序

你要將這個列表按播放次數(shù)從多到少的順序排列仁卷，從而將你喜歡的樂隊排序。該如何做呢?一種辦法是遍歷這個列表成洗，找出作品播放次數(shù)最多的樂隊五督，并將該樂隊添加到一個新列表中。再次這樣做瓶殃，找出播放次數(shù)第二多的樂隊。繼續(xù)這樣做副签，你將得到一個有序列表遥椿。

要找出播放次數(shù)最多的樂隊，必須檢查列表中的每個元素淆储。需要的總時間為 O(n × n)冠场，即O(n2)。

選擇排序是一種靈巧的算法本砰，但其速度不是很快碴裙。

第三章 遞歸

3.1 遞歸

這個盒子里有盒子，而盒子里的盒子又有盒子点额。鑰匙就在某個盒子中舔株。為找到鑰匙，你將使用什么算法?

下面是一種方法还棱。

1) 創(chuàng)建一個要查找的盒子堆载慈。

2) 從盒子堆取出一個盒子，在里面找珍手。

3) 如果找到的是盒子办铡，就將其加入盒子堆中，以便以后再查找琳要。 (4) 如果找到鑰匙寡具，則大功告成!

4) 回到第二步。

下面是另一種方法稚补。

1) 檢查盒子中的每樣東西童叠。

2) 如果是盒子，就回到第一步孔厉。

3) 如果是鑰匙拯钻，就大功告成!

第一種方法使用的是while循環(huán):只要盒子堆不空，就從中 取一個盒子撰豺，并在其中仔細查找粪般。第二種方法使用遞歸——函數(shù)調(diào)用自己。

遞歸只是讓解決方案更清晰污桦，并 沒有性能上的優(yōu)勢亩歹。實際上，在有些情況下，使用循環(huán)的性能更好小作。

3.2 基線條件和遞歸條件

編寫遞歸函數(shù)時亭姥，必須告訴它何時停止遞歸。正因為如此顾稀，每個遞歸函數(shù)都有兩部分:基線條件(base case)和遞歸條件(recursive case)镣陕。遞歸條件指的是函數(shù)調(diào)用自己，而基線條件則指的是函數(shù)不再調(diào)用自己愉择，從而避免形成無限循環(huán)严衬。

3.3 棧

調(diào)用另一個函數(shù)時，當前函數(shù)暫停 并處于未完成狀態(tài)抚笔。

這個棧用于存儲多個函數(shù)的變量扶认，被稱為調(diào)用棧。

遞歸函數(shù)也使用調(diào)用棧!來看看遞歸函數(shù)factorial的調(diào)用棧殊橙。factorial(5)寫作5!辐宾，其定義如下:5! = 5 * 4 * 3 * 2 * 1。同理膨蛮，factorial(3)為3 * 2 * 1叠纹。下面是計算階乘的遞歸函數(shù)。

def fact(x):

????if x == 1:

????????return 1

????else:

????????return x * fact(x-1)

使用棧雖然很方便鸽疾，但是也要付出代價:存儲詳盡的信息可能占用大量的內(nèi)存吊洼。每個函數(shù)調(diào)用都要占用一定的內(nèi)存，如果棧很高制肮，就意味著計算機存儲了大量函數(shù)調(diào)用的信息冒窍。在這種情況下，你有兩種選擇豺鼻。

a) 重新編寫代碼综液，轉(zhuǎn)而使用循環(huán)。

b) 使用尾遞歸儒飒。

第四章 快速排序

4.1分而治之

本章的重點是使用學到的新技能來解決問題谬莹。我們將探索分而治之(divide and conquer，D&C)——一種著名的遞歸式問題解決方法桩了。

如何將一塊地均勻地分成方塊附帽，并確保分出的方塊是最大的呢?使用D&C策略!D&C是遞歸的。使用D&C解決問題的過程包括兩個步驟井誉。

(1) 找出基線條件蕉扮，這種條件必須盡可能簡單。

(2) 不斷將問題分解(或者說縮小規(guī)模)颗圣，直到符合基線條件喳钟。

首先屁使，找出基線條件。最容易處理的情況是奔则，一條邊的長度是另一條邊的整數(shù)倍蛮寂。

現(xiàn)在需要找出遞歸條件，這正是D&C的用武之地易茬。根據(jù)D&C的定義酬蹋，每次遞歸調(diào)用都必須縮小問題的規(guī)模。如何縮小前述問題的規(guī)模呢?我們首先找出這塊地可容納的最大方塊抽莱。同時余下一小塊地〕冢現(xiàn)在是頓悟時刻:何不對余下的那一小塊地使用相同的算法呢?

這里重申一下D&C的工作原理:

(1) 找出簡單的基線條件;

(2) 確定如何縮小問題的規(guī)模，使其符合基線條件岸蜗。 D&C并非可用于解決問題的算法，而是一種解決問題的思路叠蝇。

4.2 快速排序

快速排序是一種常用的排序算法璃岳，比選擇排序快得多。例如悔捶，C語言標準庫中的函數(shù)qsort實現(xiàn)的就是快速排序铃慷。快速排序也使用了D&C蜕该。

下面來使用快速排序?qū)?shù)組進行排序犁柜。

首先，從數(shù)組中選擇一個元素堂淡，這個元素被稱為基準值(pivot)馋缅。

接下來，找出比基準值小的元素以及比基準值大的元素绢淀。

4.3 再談大O表示法

快速排序的獨特之處在于萤悴，其速度取決于選擇的基準值。在討論快速排序的運行時間前皆的，我們再來看看最常見的大O運行時間覆履。

還有一種名為合并排序(merge sort)的排序算法，其運行時間為O(n log n)费薄，比選擇排序快得多!快速排序的情況比較棘手硝全，在最糟情況下，其運行時間為O(n2)楞抡。

與選擇排序一樣慢!但這是最糟情況伟众。在平均情況下，快速排序的運行時間為O(n log n)拌倍。

第五章 散列表

5.1 散列函數(shù)

散列函數(shù)“將輸入映射到數(shù)字”赂鲤。

在你將學習的復雜數(shù)據(jù)結構中噪径，散列表可能是最有用的，也被稱為散列映射数初、映射找爱、字典和關聯(lián)數(shù)組。散列表的速度很快!

你可能根本不需要自己去實現(xiàn)散列表泡孩，任一優(yōu)秀的語言都提供了散列表實現(xiàn)车摄。Python提供的散列表實現(xiàn)為字典，你可使用函數(shù)dict來創(chuàng)建散列表仑鸥。

5.2 應用案例

緩存是一種常用的加速方式吮播，所有大型網(wǎng)站都使用緩存，而緩存的數(shù)據(jù)則存儲在散列表中!

散列表適合用于:

a) 模擬映射關系;

b) 防止重復;

c) 緩存/記住數(shù)據(jù)眼俊，以免服務器再通過處理來生成它們意狠。

5.3 沖突

這種情況被稱為沖突(collision):給兩個鍵分配的位置相同。

處理沖突的方式很多疮胖，最簡單的辦法如下:如果兩個鍵映射到了同一個位置环戈，就在這個位置存儲一個鏈表。

這里的經(jīng)驗教訓有兩個澎灸。

a) 散列函數(shù)很重要院塞。前面的散列函數(shù)將所有的鍵都映射到一個位置，而最理想的情況是性昭， 散列函數(shù)將鍵均勻地映射到散列表的不同位置拦止。

b) 如果散列表存儲的鏈表很長，散列表的速度將急劇下降糜颠。然而汹族，如果使用的散列函數(shù)很好，這些鏈表就不會很長!

5.4 性能

在平均情況下括蝠，散列表執(zhí)行各種操作的時間都為O(1)鞠抑。O(1)被稱為常量時間。你以前沒有見過常量時間忌警，它并不意味著馬上搁拙，而是說 4不管散列表多大，所需的時間都相同法绵。

在使用散列表時箕速，避開最糟情況至關重要。為此朋譬，需要避免沖突盐茎。需要有:

a) 較低的填裝因子

b) 良好的散列函數(shù)

散列表的填裝因子很容易計算：散列表包含的元素數(shù)/位置總數(shù)

良好的散列函數(shù)讓數(shù)組中的值呈均勻分布。糟糕的散列函數(shù)讓值扎堆徙赢，導致大量的沖突字柠。

第六章 廣度優(yōu)先搜索

廣度優(yōu)先搜索讓你能夠找出兩樣東西之間的最短距離探越，不過最短距離的含義有很多!使用廣度優(yōu)先搜索可以:

a) 編寫國際跳棋AI，計算最少走多少步就可獲勝;

b) 編寫拼寫檢查器窑业，計算最少編輯多少個地方就可將錯拼的單詞改成正確的單詞钦幔，如READED改為READER需要編輯一個地方;

c) 根據(jù)你的人際關系網(wǎng)絡找到關系最近的醫(yī)生。

6.1 圖簡介

假設你居住在舊金山常柄，要從雙子峰前往金門大橋鲤氢。你想乘公交車前往，并希望換乘最少西潘【碛瘢可 乘坐的公交車如下。

前往金門大橋的 最短路徑需要三步喷市。這種問題被稱為最短路徑問題(shorterst-path problem)相种。你經(jīng)常要找出最短路徑，這可能是前往朋友家的最短路徑品姓，也可能是國際象棋中把對方將死的最少步數(shù)蚂子。解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。

6.2 圖是什么

圖由節(jié)點和邊組成缭黔。一個節(jié)點可能與眾多節(jié)點直接相連，這些節(jié)點被稱為鄰居蒂破。

6.3 廣度優(yōu)先搜索

廣度優(yōu)先搜索是一種用于圖的查找算法馏谨，可幫助回答兩類問題。

a) 第一類問題:從節(jié)點A出發(fā)附迷，有前往節(jié)點B的路徑嗎?

b) 第二類問題:從節(jié)點A出發(fā)惧互，前往節(jié)點B的哪條路徑最短?

下面來嘗試回答第二類問題——誰是關系最近的芒果銷 售商。例如喇伯，朋友是一度關系喊儡，朋友的朋友是二度關系。假設你經(jīng)營著一個芒果農(nóng)場稻据，需要尋找芒果銷售商艾猜，以便將芒果賣給他。

在廣度優(yōu)先搜索的執(zhí)行過程中捻悯，搜索范圍從起點開始逐漸向外延伸匆赃，即先檢查一度關系，再檢查二度關系今缚。

你需要按添加順序進行檢查算柳。有一個可實現(xiàn)這種目的的數(shù)據(jù)結構，那就是隊列(queue)姓言。

隊列只支持兩種操作:入隊和出隊瞬项。

隊列是一種先進先出(First In First Out蔗蹋，F(xiàn)IFO)的數(shù)據(jù)結構，而棧是一種后進先出(Last In First Out囱淋，LIFO)的數(shù)據(jù)結構猪杭。

6.4 實現(xiàn)圖

圖不過是一系列的節(jié)點和邊，表示它的Python代碼如下绎橘。

Anuj胁孙、Peggy、Thom和Jonny都沒有鄰居称鳞，這是因為雖然有指向他們的箭頭涮较，但沒有從他們出發(fā)指向其他人的箭頭。這被稱為有向圖(directed graph)冈止，其中的關系是單向的狂票。因此，Anuj是Bob的鄰居熙暴，但Bob不是Anuj的鄰居闺属。無向圖(undirected graph)沒有箭頭，直接相連的節(jié)點互為鄰居周霉。例如掂器，下面兩個圖是等價的。

6.5 實現(xiàn)算法

先概述一下這種算法的工作原理俱箱。

檢查一個人之前国瓮，要確認之前沒檢查過他，這很重要狞谱。為此乃摹，你可使用一個列表來記錄檢查過的人。

考慮到這一點后跟衅，廣度優(yōu)先搜索的最終代碼如下孵睬。

第七章 狄克斯特拉算法

在前一章使用了廣度優(yōu)先搜索，它找出的是段數(shù)最少的路徑伶跷。如果你要找出最快的路徑掰读，該如何辦呢?為此，可使用另一種算法——狄克斯特拉算法(Dijkstra’s algorithm)叭莫。

7.1 使用狄克斯特拉算法

下面來看看如何對下面的圖使用這種算法磷支。

其中每個數(shù)字表示的都是時間，單位分鐘食寡。為找出從起點到終點耗時最短的路徑雾狈，你將使用狄克斯特拉算法。

狄克斯特拉算法包含4個步驟抵皱。

a) 找出“最便宜”的節(jié)點善榛，即可在最短時間內(nèi)到達的節(jié)點辩蛋。

b) 更新該節(jié)點的鄰居的開銷，其含義將稍后介紹移盆。

c) 重復這個過程悼院，直到對圖中的每個節(jié)點都這樣做了。

d) 計算最終路徑咒循。

7.2 術語

狄克斯特拉算法用于每條邊都有關聯(lián)數(shù)字的圖据途，這些數(shù)字稱為權重(weight)。

帶權重的圖稱為加權圖(weighted graph)叙甸，不帶權重的圖稱為非加權圖(unweighted graph)颖医。

要計算非加權圖中的最短路徑，可使用廣度優(yōu)先搜索裆蒸。要計算加權圖中的最短路徑熔萧，可使用狄克斯特拉算法。圖還可能有環(huán)僚祷，而 環(huán)類似右面這樣佛致。

狄克斯特拉算法只適用于有向無環(huán)圖。

7.5 實現(xiàn)

第八章 貪婪算法

8.1 教室調(diào)度問題

你希望在這間教室上盡可能多的課辙谜。如何選出盡可能多且時間不沖突的課程呢?

這個問題好像很難俺榆，不是嗎?實際上，算法可能簡單得讓你大吃一驚装哆。具體做法如下肋演。

a) 選出結束最早的課，它就是要在這間教室上的第一堂課烂琴。

b) 接下來，必須選擇第一堂課結束后才開始的課蜕乡。同樣奸绷，你選擇結束最早的課，這將是要 在這間教室上的第二堂課层玲。

重復這樣做就能找出答案!

貪婪算法很簡單:每步都采取最優(yōu)的做法号醉。

你每步都選擇局部最優(yōu)解，最終得到的就是全局最優(yōu)解辛块。

8.2 背包問題

你力圖往背包中裝入價值最高的商品畔派，你會使用哪種算法呢?

同樣，你采取貪婪策略润绵，這非常簡單线椰。

a) 盜竊可裝入背包的最貴商品。

b) 再盜竊還可裝入背包的最貴商品尘盼，以此類推憨愉。

在有些情況下烦绳，完美是優(yōu)秀的敵人。有時候配紫，你只需找到一個能夠大致解決問題的算法径密，此時貪婪算法正好可派上用場，因為它們實現(xiàn)起來很容易躺孝，得到的結果又與正確結果相當接近享扔。

8.3 集合覆蓋問題

假設你辦了個廣播節(jié)目，要讓全美50個州的聽眾都收聽得到植袍。為此惧眠，你需要決定在哪些廣播臺播出。在每個廣播臺播出都需要支付費用奋单，因此你力圖在盡可能少的廣播臺播出锉试。

每個廣播臺都覆蓋特定的區(qū)域，不同廣播臺的覆蓋區(qū)域可能重疊览濒。

如何找出覆蓋全美50個州的最小廣播臺集合呢?聽起來很容易呆盖，但其實非常難。具體方法如下贷笛。

(1) 列出每個可能的廣播臺集合应又，這被稱為冪集(power set)》啵可能的子集有2n個株扛。

(2) 在這些集合中，選出覆蓋全美50個州的最小集合汇荐。

貪婪算法可化解危機!使用下面的貪婪算法可得到非常接近的解洞就。

(1) 選出這樣一個廣播臺，即它覆蓋了最多的未覆蓋州掀淘。即便這個廣播臺覆蓋了一些已覆蓋 的州旬蟋，也沒有關系。

(2) 重復第一步革娄，直到覆蓋了所有的州倾贰。

這是一種近似算法(approximation algorithm)。在獲得精確解需要的時間太長時拦惋，可使用近

似算法匆浙。判斷近似算法優(yōu)劣的標準如下:

a) 速度有多快;

b) 得到的近似解與最優(yōu)解的接近程度。

第九章 動態(tài)規(guī)劃

略

第十章 K最近鄰算法

10.1 橙子還是柚子

如果判斷這個水果是橙子還是柚子呢? 一般而言厕妖，柚子更大首尼、更紅。一種辦法是看它的鄰居。來看看離它最近的三個鄰居饰恕。

在這三個鄰居中挠羔，橙子比柚子多，因此這個水果很可能是橙子埋嵌。祝賀你破加，你剛才就是使用K 最近鄰(k-nearest neighbours，KNN)算法進行了分類!這個算法非常簡單雹嗦。

KNN算法雖然簡單卻很有用!要對東西進行分類時范舀，可首先嘗試這種算法。

10.2 創(chuàng)建推薦系統(tǒng)

? 特征抽取

在前面的水果示例中了罪，你根據(jù)個頭和顏色來比較水果锭环，換言之，你比較的特征是個頭和顏色〔磁海現(xiàn)在假設有三個水果辅辩，你可抽取它們的特征。

再根據(jù)這些特征繪圖娃圆。

從上圖可知玫锋，水果A和B比較像。下面來度量它們有多像讼呢。要計算兩點的距離撩鹿，可使用畢達哥拉斯公式。

? 回歸

你將使用KNN來做兩項 基本工作——分類和回歸:

a) 分類就是編組;

b) 回歸就是預測結果(如一個數(shù)字)悦屏。

? 挑選合適的特征

使用KNN時节沦，挑選合適的特征進行比較至關重要。

在挑選合適的特征方面础爬，沒有放之四海皆準的法則甫贯，你必須考慮到各種需要考慮的因素。

10.3 機器學習簡介

? OCR

OCR指的是光學字符識別(optical character recognition)看蚜，這意味著你可拍攝印刷頁面的照片叫搁，計算機將自動識別出其中的文字。

OCR的第一步是查看大量的數(shù)字圖像并提取特征失乾，這被稱為訓練(training)。大多數(shù)機器學習算法都包含訓練的步驟:要讓計算機完成任務纬乍，必須先訓練它碱茁。

? 創(chuàng)建垃圾郵件過濾器

垃圾郵件過濾器使用一種簡單算法——樸素貝葉斯分類器(Naive Bayes classifier)

第十一章 接下來如何做

略

<完結>

備注：該文章為個人讀書學習筆記，僅供學習之用仿贬，未經(jīng)允許禁止轉(zhuǎn)載纽竣。