《演算法導論》第二章筆記
前言
表示終于有幸能一睹《演算法導論》這本演算法神作了，
雖然之前也或多或少接觸過演算法，比如研究HashMap等資料結構等，
看過我之前博客的小伙伴，應該可以看到我之前寫過排序演算法和查找演算法等（C語言版本），
不過我更希望是像大學學習《運籌學》那樣，系統地整理演算法體系，所以就有這次的博客，針對《演算法導論》的學習筆記，我會將學習《演算法導論》程序中遇到的一些重點，記錄下來，
另外，每章的實作代碼（Java版），我都會另開一篇博客，進行記錄，
摘要
1.回圈不變式
2.回圈不變式的性質：
* 初始化：回圈的第一次迭代之前，它為真
* 保持：如果回圈的某次迭代之前它為真，那么下次迭代之前它仍為真
* 終止：在回圈終止時，不變式為我們提供一個有用的性質，該性質有助于證明演算法是正確的
PS：書中，這里就插入排序，分別闡述了該三條性質
PS：聯系數學歸納法，初始化 針對是數學歸納法中的n = 1這樣的初始條件證明，而 保持 針對的是數學歸納法中 n=m成立=》n=m+1成立 的遞回條件證明，至于 終止 這是區分現實（程式）與理想（數學）的分界線，畢竟現實中程式的執行是存在終點的，
3.書中p11中約定了諸多偽代碼規則，如指標，值傳遞等
4.演算法的分析是采用一種通用的單處理器計算模型——RAM（random-access machine）模型作為實作技術
5.RAM模型包含真實計算機中的常見指令：
* 算數指令（加減乘除，取余，上下取整）
* 資料移動指令（裝入，存盤，復制）
* 控制指令（條件與無條件轉移，子程式呼叫與回傳）
PS：并且設定所有指令的耗時是常量的，實際情況并非如此，但是過于糾結細節，造成計算模型過于復雜，是不必要的，
6.演算法的耗時往往依賴于輸入，所以通常把一個程式的運行時間描述成其輸入規模的函式，
7.輸入規模往往依賴于研究的問題，并且其引數串列也依賴于實際問題，如圖類演算法，往往涉及圖中的頂點數和邊數輸入，
8.一個演算法在特定輸入上的運行時間是指執行的基本運算元或步數，這里同樣假定執行每行代碼需要常量時間（格式化，規范的代碼，而不是壓縮代碼），
9.最壞情況與平均情況分析：往往集中求解最壞運行時間，即對規模為n的任何輸入，演算法的最長運行時間，這樣做的三點理由：
* 一個演算法的最壞情況運行時間給出了任何輸入的運行時間的一個上界
* 對某些演算法，最壞情況經常出現
* “平均情況”往往與最壞情況大致一樣差
PS：上述第三條的理解：“平均情況”的增長量級（時間復雜度）往往和最壞情況一致
PS：特定情況下，我們會對一個演算法的平均情況運行時間感興趣，如概率分析
10.增長量級：對于輸入規模n，在n足夠大時，影響增長量級的是公式中最重要的項（即多項式中冪最大的項）
11.增量方法作為演算法設計的技術之一，插入排序使用了增量方法
12.許多演算法在結構上是遞回的：為了解決一個給定的問題，演算法一次或多次遞回地呼叫其自身以解決緊密相關地若干問題，
PS：遞回令人想起數學歸納法中的 n=m成立=》n=m+1成立的程序
PS：程式中不斷重復一個程序，那么實作無非就是回圈與遞回，如果重復次數直接，明確，可以采用回圈，如果重復次數不明確，甚至需要程序不斷重復后才知道，則采用遞回，
13.遞回演算法增尋分治法地思想：將原問題分解為幾個規模較小但類似原問題的子問題，遞回地求解這些子問題，然后在合并這些子問題的解來建立原問題的解，
14.分治模式在每層遞回時有三個步驟：
* 分解：將問題分解為若干更小的子問題
* 解決：將對應子問題進行求解
* 合并：將這些子問題的解合并，并傳給上一層遞回
15.哨兵：為避免每個基本步驟都要檢查是否有堆為空，故在每個堆的底部防止一個哨兵，它包含一個特殊值，用于簡化代碼，
PS：如在歸并排序中，我通過Integer.MAX_VALUE，來避免為空的判斷，
16.遞回式（長得就像分段函式一樣，只不過分為初始化與遞回兩個階段）
17.遞回樹
18.歸并排序中，完全擴展的遞回樹具有lgn+1層，每層將貢獻總耗時cn，故總代價為cnlgn+cn
練習
練習部分，所以代碼實作，都會放在對應的代碼實作博客，剩下的練習，我只會挑選一些進行記錄（有些東東，手寫還好，用md寫，太麻煩了），當然，如果有小伙伴有疑惑，可以私信或@我
2.3-6
不可以，
雖然上層遍歷元素的時間復雜度為n，而下層采用二分查找（時間復雜度為lgn），看起來整體時間復雜度為nlgn，但是下層并不僅僅是二分查找，查找只是定位到了目標位置，還需要進行當前元素的插入動作，而無論是在陣列，還是別的順序表中，插入的時間復雜度為n，所以就變成了n*(n+lgn)，時間復雜度就變成了n^2，
綜上，無法通過二分查找，將插入排序的時間復雜度從n^2優化到nlgn，
2.3-7
首先，通過歸并排序，對陣列進行排序（因為后面用到的二分查找需要順序表，并且題目只要求確認是否存在，并沒有要求回傳對應index，所以在一開始進行排序操作），
外層通過回圈，依次獲得對應元素，根據branchTarget = target - array[i]這樣的操作獲得兩個元素中的另一個元素，再通過二分查找，判斷集合中是否存在對應的另一個元素，
歸并排序的時間復雜度為nlgn，回圈遍歷的時間復雜度為n，二分查找的時間復雜度為lgn，所以最終的耗時為nlgn+n*lgn，故最終時間復雜度為nlgn，
具體實作，請看本章代碼實作博客，
思考
由于該章的思考題，都需要進行公式計算與展示，而我并不會用MarkDown表示，所以就不寫出來了，如果感興趣，給各位一個資料（Algorithems Solutions），
總結
其實這個章節還是比較簡單的，演算法上面舉了一些有關排序的例子，以及一個折半查找的demo，數學方面，一方面需要還記得高中的數學歸納法，另一方面需要一定的排列組合的認識（進行復雜度的計算表），
附錄
參考
- 《演算法導論》
- Algorithems Solutions
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85168.html
標籤：其他
上一篇：CDQ分治筆記+例題
下一篇：二叉樹中和為某一值的路徑