《算法圖解》讀書筆記

下面将按照本書的順序做一下讀書筆記的整理。

1.大O表示法

大O表示法表示的為算法運作的時間複雜度，但不是以秒為機關，而是表示随着操作數n的變大，算法運作時間的增速。

是操作數為n下的查找次數，是指在最糟糕情況下的運作時間複雜度。

常見的二分查找時間複雜度為o（log n），在大O表示法中讨論時間log都是以2為底的對數，快排時間複雜度為O（n*log n），劃分成log n 層，每一層的時間複雜度為n。

2. 數組和連結清單

數組的元素存儲在一起，連結清單的元素分開存儲，每一個元素都存儲了下一個元素的位址；數組讀取快，連結清單插入和删除快。

3.遞歸

每一個遞歸函數都有兩部分組成，基線條件和遞歸條件。基線條件是指函數不在自己調用自己，即遞歸停止的條件。遞歸條件就是自己調用自己。

4. 分而治之

分而治之是一種遞歸式解決問題的辦法，需要将問題逐漸化小。

工作原理：（1）找出簡單的基線條件，當涉及數組時，基線條件一般為數組為空或者數組隻包含一個元素

                  （2）确定如何縮小問題的規模，使其符合基線條件。（經典的分治算法：快速排序）

5. 散清單

散清單就是常說的哈希結構，字典資料結構，由鍵值對組成，模拟映射關系，可以防止重複，緩存記住資料，以免伺服器在生成他們。

當兩個鍵映射到同一個位置時，在這個位置用一個連結清單存儲不同的值。

6.廣度優先搜尋

廣度優先搜尋是一種用于圖結構的查找算法，用于解決兩類問題：1. 是否有從A到B的路徑。2. 從A到B的最短路徑是多少。

圖由節點和邊組成，模拟不同東西是如何相連的，與一個節點直接相連的多個節點被稱為鄰居，兩個節點之間有箭頭指向，被稱為有向圖，無箭頭指向被稱為無向圖，程式設計時用字典模拟這種資料結構。

在用BFS算法實作最短距離（隻要最短、最近的什麼東西就行，不僅僅是距離）查找時，需要用隊列這種資料結構來實作，隊列時先進先出，棧是後進先出。

BFS查找最短路徑的方法：

1. 将問題模組化為圖結構

2. 用資料結構實作圖結構

3. 實作BFS算法（隻有按資料的添加順序去找，才能實作這種目的）

必須按照加入順序去檢查搜尋清單中對象，否則找到的就不是最短路徑，是以搜尋清單必須是隊列，對于檢查過的對象，務必不要再去檢查，否則可能導緻無限循環。

7. 貪婪算法

當一個問題不可能完成時，或者沒有快速算法時，這就是一個NP完全問題，我們要學會識别它，以免浪費時間去尋找快速算法，應學習近似算法，使用它們可以快速找到NP完全問題的近似解，常用的近似算法有貪婪算法。

貪婪算法簡單易行，每一步都采取最優的做法，每一步都選擇局部最優解，最終得到的就是全局最優解，但并不是在所有情況下都有效。

比較經典的問題有旅行商問題，集合覆寫問題。

在集合覆寫問題中，每一次選擇一個廣播台，它可以覆寫最多未覆寫的州，即使已經覆寫了一些重複的。一直重複，直到覆寫了所有的州。需要用集合set來實作。

旅行商問題中，随機選擇出發的城市，然後每次選擇要去的下一個城市時，都選擇還沒去的最近的城市，以此類推，這是個近似解。

如何判别NP完全問題？

1. 元素少，運作開，元素增多，運作非常慢，2 . 涉及所有組合，3. 不能将問題分成小問題，必須考慮各種情況，3. 問題中涉及序列（如旅行商中的城市序列）且難以解決，4， 問題中涉及集合（廣播台集合）且難以解決，5，可轉換為旅行商或者集合覆寫問題。

8.動态規劃

動态規劃就是将某個名額最大化，

可在有限制條件下找到最優解，

可以将問題拆分成彼此獨立且離散的子問題，

每種動态規劃解決方案都設計網格，

單元格中的值就是你要優化的值，每一個單元格都是一個子問題，是以應考慮如何将問題劃分成子問題，有助于找到做坐标軸。

沒有一個統一的動态規劃解決方案的公式。

比較經典的使用動态規劃的題目有：求最長公共子串（連續公共最長），最長公共子序列（非連續，一樣即可）。