演算法是一組完成任務的指令。 任何代碼片段都可視為演算法， 我們這裡討論的演算法要麼速度快， 要麼能解決有趣的問題，
一些常見的大O執行時間
O(log n)， 也叫對數時間， 這樣的演算法包括二分查找。
O(n)， 也叫線性時間， 這樣的演算法包括簡單查找。
O(n * log n)， 這樣的演算法包括快速排序。
O(n2 )， 這樣的演算法包括選擇排序。
O(n!)， 這樣的演算法包括接下來將介紹的旅行商問題的解決方案。
使用這幾種演算法繪製一個16格的網格需要的時間如下：
旅行商問題
這著實困擾著很多人， 一位旅行商要去往5個城市，
很多演算法僅在資料經過排序後才管用。 當然很多語言都內置了排序演算法， 因此你基本 上不用從頭開始編寫自己的版本。
陣列和鏈表哪個用得更多呢？顯然要看情況。 但陣列用得很多， 因為它支援隨機訪問， 很多情況都要求能夠隨機訪問， 而不是循序存取。
圖為單向鏈表的結構。
注：同一陣列的元素類型都必須相同。
遞迴遞迴指的是調用自己的函數，遞迴只是讓解決方案更清晰，並 沒有性能上的優勢。實際上，在有些情況下，使用迴圈的性能更好。Leigh Caldwell在Stack Overflow上說的一句話：“如果使用迴圈，程式的性能可能更高；如果使用遞迴，程式可能 更容易理解。如何選擇要看什麼對你來說更重要。”
基線條件和遞迴條件
編寫遞迴函數時，必須告訴它何時停止遞迴。正因為如此，每個遞迴函數都有兩部分：基線 條件（base case）和遞迴條件（recursive case）。遞迴條件指的是函式呼叫自己，而基線條件則指的是函數不再調用自己的條件，從而避免形成無限迴圈。
快速排序
快速排序使用了D&C。對排序演算法來說，基線條件為陣列為空或只包含一個元素。
首先，從陣列中選擇一個元素，這個元素被稱為基準值；
接下來，找出比基準值小的元素以及比基準值大的元素。
再對這兩個子陣列進行快速排序，直到滿足基線條件。
注：歸納證明是一種證明演算法行之有效的方式，它分兩步：基線 條件和歸納條件。
散清單
散列函數
散列函數“將輸入映射到數位”。這個用python字典比較好理解，每次給定key都得到的是同一個數字，每個key都對應一個value。
衝突
間接描述了散清單的性能，衝突就是：給兩 個鍵分配的位置相同。處理衝突的方式 很多，最簡單的辦法如下：如果兩個鍵映射到了同一個位置，就在這個位置存儲一個鏈表。如果一個散列表所有的值都放在第一個記憶體中呢，那和一個鏈表又有什麼區別呢？最理想的情況是， 散列函數將鍵均勻地映射到散列表的不同位置。如果散清單存儲的鏈表很長，散清單的速度將急劇下降。
性能
在平均情況下，散清單執行各種操作的時間都為O(1)。我們來將 散清單同陣列和鏈表比較一下。
廣度優先搜索
如果你要從A點去往B點，這種問題被稱為最短路徑問題需要兩個步驟。
(1) 使用圖來建立問題模型。
(2) 使用廣度優先搜索解決問題。
圖是由節點和邊組成的，圖用於模擬不同的東西是如何相連的。
廣度優先搜索是一種用於圖的查找演算法，可説明回答兩類問題。
第一類問題：從節點A出發，有前往節點B的路徑嗎？
第二類問題：從節點A出發，前往節點B的哪條路徑最短？
還是解決最短路徑的演算法，不過他解決的是加權圖的最短路徑。也就是說在狄克斯特拉演算法中，你給每段都分配了一個數字或權重，因此狄克斯特拉演算法找出 的是總權重最小的路徑。
狄克斯特拉演算法包含4個步驟。
(1) 找出“最便宜”的節點，即可在最短時間內到達的節點。
(2) 更新該節點的鄰居的開銷。
(3) 重複這個過程，直到對圖中的每個節點都這樣做了。
(4) 計算最終路徑。
要計算非加權圖中的最短路徑，可使用廣度優先搜索。要計算加權圖中的最短路徑，可使用狄克斯特拉演算法。
要注意的是狄克斯特拉演算法只適用於無環圖，並且狄克斯特拉演算法無法計算負權的邊。帶負權的邊要使用貝爾曼福德演算法計算（這個我也不會）。
下面代碼就實現了狄克斯特拉演算法計算出最短路徑的代碼。
貪婪演算法很簡單：每步都採取最優的做法，最終得到的就是全域最優解。貪婪演算法並非在任何情況下都行之有效，但它易於實現。
用一個簡單的例子來解釋一下。比如有下麵一張課程表，你學要盡可能多的在一間教室裡上最多的課。
(1) 列出每個可能的廣播台集合，這被稱為冪集（power set）。可能的子集有2n個。
(2) 在這些集合中，選出覆蓋全美50個州的最小集合。問題是計算每個可能的廣播台子集需要很長時間。由於可能的集合有2**n個，因此執行時間為 O(2**n )。
貪婪演算法可化解危機！使用下面的貪婪演算法可得到非常接近的解。
(1) 選出這樣一個廣播台，即它覆蓋了最多的未覆蓋州。即便這個廣播台覆蓋了一些已覆蓋的州，也沒有關係。
(2) 重複第一步，直到覆蓋了所有的州。
這是一種近似演算法（approximation algorithm）。在獲得精確解需要的時間太長時，可使用近似演算法。
判斷近似演算法優劣的標準如下：
速度有多快；
得到的近似解與最優解的接近程度。
這個問題的演算法代碼：
背包問題
一個小偷，背包容納量為4，商店有三件商品可以偷，音響3000塊重量4，電腦2000塊重量3，吉他1500塊重量1。
嘗試一次次的試，時間為O（2**n），這種方法肯定可以使用NP演算法啦，但是不是最優解。
動態規劃先解決子問題，再逐步解決大問題。
每個動態規劃演算法都從一個網格開始，背包問題的網格如下。
第一行是吉他行，你只能選擇拿不拿吉他，只能拿其他肯定會拿偷啊，這樣利益最大化。
第二行是音箱行，你可以選擇吉他或音箱。
第三行電腦行，三種都可以選擇。
這僅僅是程式設計演算法的一小部分，在後面還有很多高級的演算法等著我們，對於本文的一些代碼，如果不太懂他的運行過程可以使用debug一步一步推導出來，演算法是程式設計中極為核心的部分，你的代碼的優秀程度與你的思維有很大的關係，希望初學python程式設計也能很有好的思維方式來解決遇到的問題，因為讀這本書比較淺顯，閱讀也很快，所以可能存在著一些問題，希望各路大神批評指正
謝謝閱讀！
注：同一陣列的元素類型都必須相同。
遞迴遞迴指的是調用自己的函數，遞迴只是讓解決方案更清晰，並 沒有性能上的優勢。實際上，在有些情況下，使用迴圈的性能更好。Leigh Caldwell在Stack Overflow上說的一句話：“如果使用迴圈，程式的性能可能更高；如果使用遞迴，程式可能 更容易理解。如何選擇要看什麼對你來說更重要。”
基線條件和遞迴條件
編寫遞迴函數時，必須告訴它何時停止遞迴。正因為如此，每個遞迴函數都有兩部分：基線 條件（base case）和遞迴條件（recursive case）。遞迴條件指的是函式呼叫自己，而基線條件則指的是函數不再調用自己的條件，從而避免形成無限迴圈。
快速排序
快速排序使用了D&C。對排序演算法來說，基線條件為陣列為空或只包含一個元素。
首先，從陣列中選擇一個元素，這個元素被稱為基準值；
接下來，找出比基準值小的元素以及比基準值大的元素。
再對這兩個子陣列進行快速排序，直到滿足基線條件。
注：歸納證明是一種證明演算法行之有效的方式，它分兩步：基線 條件和歸納條件。
散清單
散列函數
散列函數“將輸入映射到數位”。這個用python字典比較好理解，每次給定key都得到的是同一個數字，每個key都對應一個value。
衝突
間接描述了散清單的性能，衝突就是：給兩 個鍵分配的位置相同。處理衝突的方式 很多，最簡單的辦法如下：如果兩個鍵映射到了同一個位置，就在這個位置存儲一個鏈表。如果一個散列表所有的值都放在第一個記憶體中呢，那和一個鏈表又有什麼區別呢？最理想的情況是， 散列函數將鍵均勻地映射到散列表的不同位置。如果散清單存儲的鏈表很長，散清單的速度將急劇下降。
性能
在平均情況下，散清單執行各種操作的時間都為O(1)。我們來將 散清單同陣列和鏈表比較一下。
廣度優先搜索
如果你要從A點去往B點，這種問題被稱為最短路徑問題需要兩個步驟。
(1) 使用圖來建立問題模型。
(2) 使用廣度優先搜索解決問題。
圖是由節點和邊組成的，圖用於模擬不同的東西是如何相連的。
廣度優先搜索是一種用於圖的查找演算法，可説明回答兩類問題。
第一類問題：從節點A出發，有前往節點B的路徑嗎？
第二類問題：從節點A出發，前往節點B的哪條路徑最短？
還是解決最短路徑的演算法，不過他解決的是加權圖的最短路徑。也就是說在狄克斯特拉演算法中，你給每段都分配了一個數字或權重，因此狄克斯特拉演算法找出 的是總權重最小的路徑。
狄克斯特拉演算法包含4個步驟。
(1) 找出“最便宜”的節點，即可在最短時間內到達的節點。
(2) 更新該節點的鄰居的開銷。
(3) 重複這個過程，直到對圖中的每個節點都這樣做了。
(4) 計算最終路徑。
要計算非加權圖中的最短路徑，可使用廣度優先搜索。要計算加權圖中的最短路徑，可使用狄克斯特拉演算法。
要注意的是狄克斯特拉演算法只適用於無環圖，並且狄克斯特拉演算法無法計算負權的邊。帶負權的邊要使用貝爾曼福德演算法計算（這個我也不會）。
下面代碼就實現了狄克斯特拉演算法計算出最短路徑的代碼。
貪婪演算法很簡單：每步都採取最優的做法，最終得到的就是全域最優解。貪婪演算法並非在任何情況下都行之有效，但它易於實現。
用一個簡單的例子來解釋一下。比如有下麵一張課程表，你學要盡可能多的在一間教室裡上最多的課。
(1) 列出每個可能的廣播台集合，這被稱為冪集（power set）。可能的子集有2n個。
(2) 在這些集合中，選出覆蓋全美50個州的最小集合。問題是計算每個可能的廣播台子集需要很長時間。由於可能的集合有2**n個，因此執行時間為 O(2**n )。
貪婪演算法可化解危機！使用下面的貪婪演算法可得到非常接近的解。
(1) 選出這樣一個廣播台，即它覆蓋了最多的未覆蓋州。即便這個廣播台覆蓋了一些已覆蓋的州，也沒有關係。
(2) 重複第一步，直到覆蓋了所有的州。
這是一種近似演算法（approximation algorithm）。在獲得精確解需要的時間太長時，可使用近似演算法。
判斷近似演算法優劣的標準如下：
速度有多快；
得到的近似解與最優解的接近程度。
這個問題的演算法代碼：
背包問題
一個小偷，背包容納量為4，商店有三件商品可以偷，音響3000塊重量4，電腦2000塊重量3，吉他1500塊重量1。
嘗試一次次的試，時間為O（2**n），這種方法肯定可以使用NP演算法啦，但是不是最優解。
動態規劃先解決子問題，再逐步解決大問題。
每個動態規劃演算法都從一個網格開始，背包問題的網格如下。
第一行是吉他行，你只能選擇拿不拿吉他，只能拿其他肯定會拿偷啊，這樣利益最大化。
第二行是音箱行，你可以選擇吉他或音箱。
第三行電腦行，三種都可以選擇。
這僅僅是程式設計演算法的一小部分，在後面還有很多高級的演算法等著我們，對於本文的一些代碼，如果不太懂他的運行過程可以使用debug一步一步推導出來，演算法是程式設計中極為核心的部分，你的代碼的優秀程度與你的思維有很大的關係，希望初學python程式設計也能很有好的思維方式來解決遇到的問題，因為讀這本書比較淺顯，閱讀也很快，所以可能存在著一些問題，希望各路大神批評指正
謝謝閱讀！