算法設計與分析(Python)（簡體書）

本書介紹了演算法設計與分析的基本技巧，主要包括遞迴、分治、動態規劃、貪心和隨機等演算法，以及利用這些演算法求解計算問題的時間複雜度分析等內容。通過諸多有趣的實例，向讀者介紹了演算法設計的思想，以便讀者能形成演算法思維的固定模式去解決問題。在介紹每一類演算法範式以及分析演算法複雜度時，都力求建立直觀的思維過程，而摒棄過深的數學證明。書中所有演算法均採用 Python語言描述，讀者能從中學習到許多演算法實現的技巧，從而提高編寫程式的能力。
本書可作為高等學校電腦專業大一、大二或者學習過程式設計的非電腦專業學生的演算法設計與分析教材。

如果將要處理的資料、問題看作是食材，那麼演算法就是將食材“轉化”成各種令人垂誕美食的過程。中國菜肴到處都是充滿想像力的轉化，將原本普通的食材（大豆和糯米等）轉化為營養和風味都令人歎為觀止的食物（豆腐、酒釀和醬料等等）。《演算法設計與分析（Python）》的主線就是轉化，它不僅有問題的轉化，也有方法的轉化。通過問題的轉化將問題“化繁為簡”，通過方法的轉化以便融會貫通各種演算法設計的技巧。 演算法設計與分析是電腦專業非常重要的一門基礎課程，它不僅是諸多電腦專業課程的基礎，也是諸多資訊科技類公司在招聘員工時，筆試與面試重點考核的內容。演算法設計與分析已經有了諸多經典的著作，然而筆者在教學過程發現，已有的演算法設計與分析教材往往並不適合初學演算法課程的同學。主要是這些著作往往需要較多的程式設計與資料結構的背景知識。《演算法設計與分析（Python）》的內容編排並未要求過多的程式設計或者數學基礎，只需要有一定程式設計基礎即可，具體而言就是能正確寫出一個從1加到100 的函數即可。尤其是，已有的演算法著作在分析演算法複雜度時，為了結果的嚴謹往往忽視了數學分析後的直觀解釋。 《演算法設計與分析（Python）》擯棄了演算法分析過程中繁瑣的數學證明，而主要通過圖示等手段給出演算法分析結果的直觀解釋。此外，已有的教材描述演算法的語言要麼是偽代碼，要麼是C，C 或者Java這類高級程式語言。採用偽代碼描述演算法可以獲得更為精簡的描述，然而缺少可執行的結果會降低初學者對演算法結果的直觀印象。而使用C，C 或者Java這類高級程式語言描述演算法，會降低演算法描述的簡潔性，還會增加初學者調試出正確結果的難度。為此，《演算法設計與分析（Python）》的演算法採用Python 描述。Python 是複雜度介於偽代碼和C，C 之間的一類語言，其語法簡單直觀，如果有一定程式設計基礎的學生可以在1 小時內入門。《演算法設計與分析（Python）》可作為電腦專業大一、大二或者學習過程式設計的非電腦專業學生的演算法設計與分析教材。

第 1章引言 11 1演算法的定義 11 1 1演算法的屬性 21 1 2效率的定義 31 2演算法設計與分析舉例 51 2 1尋找局部高點 -1D 51 2 2圖書管理 81 3小結 10課後習題 11第 2章漸進分析與 Python計算模型 132 1引言 132 2計算模型 132 3演算法的漸進分析 142 4 Python計算模型 172 4 1控制流語句 172 4 2資料結構 192 5演算法分析實例 212 5 1求大值 222 5 2二分搜索 222 5 3子集和問題 232 6小結 24課後習題 25第 3章問題求解與代碼優化 273 1引言 273 2文檔比較 273 2 1問題提出 273 2 2演算法設計 283 2 3演算法優化 313 3拼寫矯正 333 3 1問題提出 333 3 2演算法設計 333 4穩定匹配問題 363 4 1問題提出 363 4 2演算法設計 383 5小結 40課後習題 41第 4章遞迴演算法與遞迴函數 424 1引言 424 2遞迴的組成結構 424 2 1如何籌集鉅款 424 2 2上線與下線 444 3遞迴演算法的執行 454 3 1跟蹤函數的執行 474 4利用遞迴演算法求解問題 514 4 1回文判斷 514 4 2全排列 534 4 3漢諾塔問題 544 4 4雪花曲線 574 5遞迴函數的求解 584 5 1替換法 594 5 2主分析法 604 6小結 62課後習題 63第 5章排序與樹結構 645 1引言 645 2遞迴與排序 655 2 1選擇排序 655 2 2插入排序 675 2 3合併排序 695 3二叉搜尋樹 725 3 1 BST的實現 745 3 2插入新結點 755 3 3 BST上查找 775 3 4二叉樹修剪 785 4堆 815 4 1堆化操作 815 4 2構造堆 835 4 3堆排序 855 4 4合併 k個有序序列 865 5小結 87課後習題 88