算法設計與分析：C++語言描述(第2版)（簡體書）

《算法設計與分析：C++語言描述（第2版）》為普通高等教育“十一五”國家級規劃教材。本書內容分為3部分：算法和算法分析、算法設計策略及求解困難問題。第1部分介紹問題求解方法、算法複雜度和分析、遞歸算法和遞推關係；第2部分討論常用的算法設計策略：基本搜索和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法；第3部分介紹NP完全問題、隨機算法、近似算法和密碼算法。書中還介紹了兩種新的數據結構：跳表和伸展樹，以及它們特定的算法分析方法，並對現代密碼學做了簡要論述。本書結構清晰、內容翔實、邏輯嚴謹、深入淺出。書中算法有完整的C++程序，程序構思精巧，且有詳細注釋。所有程序都已在VC++環境下編譯通過並能正確運行，它們既是學習算法設計的示例，也能使複雜抽象的算法設計更易為學習者理解和掌握。書中包含大量實例和圖示，並附豐富的習題，便於自學。·

Grady Booch，在軟件架構、軟件工程和建模領域的創新工作是世界知名的。從1981年Rational公司創建開始，他就一直擔任該公司的首席科學家。Grady于2003年3月成為了IBM院士（IBM Fellow）。Grady是統一建模語言（UML）最早的開發者之一，也是幾個Rational產品的最早開發者之一。Grady曾擔任世界各地一些複雜的軟件密集型項目的架構師和架構指導者。Grady是6本暢銷書的作者，包括UML Users Guide和Object-Oriented Analysis with Applications。Grady發表了幾百篇有關軟件工程的技術文章，其中包括在20世紀80年代早期發表的文章，這些文章最先提出了面向對象設計的術語和實踐。他曾在世界各地演講和諮詢。Grady是美國計算機協會（ACM）、美國電氣電子工程師學會（IEEE）、美國科學促進會（AAAS）、有社會責任的計算機專家協會（CPSR）的成員。他是IBM院士、ACM院士、世界技術網絡院士，也是軟件開發論壇夢想家。Grady是敏捷聯盟、Hillside集團和軟件架構師世界學院的創始委員會成員，也是Northface大學的顧問委員會成員。Grady於1977年從美國空軍學院獲得學士學位，于1979年從加州大學聖巴巴拉分校獲得電子工程科學碩士學位。Grady與他的妻子和他的貓生活在科羅拉多。他的興趣包括閱讀、旅行、唱歌和彈奏豎琴。Robert A. Maksimchuk，是Unisys Chief Technology Office的一名研究主管。他關注新出現的建模技術，目的是提升Unisys 3D可視企業建模框架的戰略方向。Bob為這項任務帶來了不同行業的大量系統工程、建模、面向對象分析與設計的專業知識。他是UML for Mere Mortals和UML for Database Design的合著者，也寫了許多文章。他曾經周遊世界各地，在各種技術論壇上作為重要演講者發言，舉辦關於UML和面向對象開發的研討會和培訓。Bob是電氣電子工程師學會（IEEE）和國際系統工程學會（INCOSE）的成員。Michael W. Engle，是洛克希德馬丁公司的首席工程師。他有超過26年的技術和管理經驗--從項目啟動到運營支持，涵蓋了完整的系統開發生命週期。利用系統工程師、軟件工程師和系統架構師的背景，Mike運用了面向對象技術，為複雜的系統開發提供創新的開發方式。Bobbi J. Young， Ph.D.，是Unisys Chief Technology Office的一名研究主管。她有著多年的IT行業從業經驗，與商業公司和國防部合同供應商一同工作。Young博士是一名諮詢師，她在項目管理、企業架構、系統工程和面向對象分析與設計方面提供現場指導。在她的職業生涯中，她關注於系統生命週期過程和方法學，同時也關注企業架構。Young博士擁有生物學、計算機科學和人工智能學位，她獲得了管理信息系統的博士學位，也曾是美國海軍預備役的一名指揮官（已退伍）。Jim Conallen，是IBM Rational的模型驅動開發戰略小組的一名軟件工程師。在這個小組中，他積極參與，將對象管理集團（OMG）的模型驅動架構（MDA）計劃應用於IBM Rational的模型工具中。Jim在基於資產的開發和可複用資產規範（RAS）領域也很活躍。Jim經常在會議上演講，也經常寫文章。他的專業領域是Web應用開發。他開發了UML的Web應用擴展（WAE）。這是對UML的一種擴展，讓開發者能夠利用UML在合適的抽象和細節層面上對Web應用的架構進行建模。這項工作是IBM Rational Rose和Rational XDE Web Modeling功能的基礎。Jim與人合著了兩個版本的Building Web Applications with UML，第一個版本採用微軟公司的ASP技術，後一個版本採用J2EE技術。Jim的經驗也來自於加入Rational之前的工作，那時他曾是獨立的諮詢師、Peace Corps的志願者和大學講師。他還是3個孩子的父親。Jim從Widener大學獲得了計算機和軟件工程的學士學位和碩士學位。Kelli Houston是IBM Rational的IT諮詢專家。她是IBM內部方法的方法架構師，負責編寫方法並集成IBM的方法。除了方法架構師的角色，Kelli還在IBM內部領導Rational Method Composer（RMC）特別興趣小組（SIG）工作，為客戶和IBM內部諮詢師提供有效使用RMC方面的諮詢和現場指導服務。·

《普通高等教育"十一五"國家級規劃教材?卓越工程師培養計劃"十二五"規劃教材?算法設計與分析:C++語言描述(第2版)》可作為高等院校計算機科學與技術和其他相關專業的本科和研究生的“算法設計與分析”課程的教材或參考書，是“算法與數據結構”或“數據結構”課程有益的教學參考書，也可供計算機工作者和其他希望了解和學習算法知識的人員參考。

第1部分 算法和算法分析第1章 算法問題求解基礎1.1 算法概述1.1.1 什麼是算法1.1.2 為什麼學習算法1.2 問題求解方法1.2.1 問題和問題求解1.2.2 問題求解過程1.2.3 系統生命週期1.3 算法設計與分析1.3.1 算法問題求解過程1.3.2 如何設計算法1.3.3 如何表示算法1.3.4 如何確認算法1.3.5 如何分析算法1.4 遞歸和歸納1.4.1 遞歸1.4.2 遞歸算法示例1.4.3 歸納證明本章小結習題1第2章 算法分析基礎2.1 算法複雜度2.1.1 什麼是好的算法2.1.2 影響程序運行時間的因素2.1.3 算法的時間複雜度2.1.4 使用程序步分析算法2.1.5 算法的空間複雜度2.2 漸近表示法2.2.1 大O記號2.2.2 記號2.2.3 記號2.2.4 小o記號2.2.5 算法按時間複雜度分類2.3 遞推關係2.3.1 遞推方程2.3.2 替換方法2.3.3 迭代方法2.3.4 主方法2.4 分攤分析2.4.1 聚集方法2.4.2 會計方法2.4.3 勢能方法本章小結習題2第3章 伸展樹與跳表3.1 伸展樹3.1.1 二叉搜索樹3.1.2 自調節樹和伸展樹3.1.3 伸展操作3.1.4 伸展樹類3.1.5 旋轉的實現3.1.6 插入運算的實現3.1.7 分攤分析3.2 跳表3.2.1 什麼是跳表3.2.2 跳表類3.2.3 級數分配3.2.4 插入運算的實現3.2.5 性能分析本章小結習題3第2部分 算法設計策略第4章 基本搜索和遍歷方法4.1 基本概念4.2 圖的搜索和遍歷4.2.1 搜索方法4.2.2 鄰接表類4.2.3 廣度優先搜索4.2.4 深度優先搜索4.3 雙連通分量4.3.1 基本概念4.3.2 發現關節點4.3.3 構造雙連通圖4.4 與或圖4.4.1 問題分解4.4.2 判斷與或樹是否可解4.4.3 構建解樹本章小結習題4第5章 分治法5.1 一般方法5.1.1 分治法的基本思想5.1.2 算法分析5.1.3 數據結構5.2 求最大最小元5.2.1 分治法求解5.2.2 時間分析5.3 二分搜索5.3.1 分治法求解5.3.2 對半搜索5.3.3 二叉判定樹5.3.4 搜索算法的時間下界5.4 排序問題5.4.1 合併排序5.4.2 快速排序5.4.3 排序算法的時間下界5.5 選擇問題5.5.1 分治法求解5.5.2 隨機選擇主元5.5.3 線性時間選擇算法5.5.4 時間分析5.5.5 允許重複元素的選擇算法5.6 斯特拉森矩陣乘法5.6.1 分治法求解5.6.2 斯特拉森分治法本章小結習題5第6章 貪心法6.1 一般方法6.2 背包問題6.2.1 問題描述6.2.2 貪心法求解6.2.3 算法正確性6.3 帶時限的作業排序6.3.1 問題描述6.3.2 貪心法求解6.3.3 算法正確性6.3.4 可行性判定6.3.5 作業排序貪心算法6.3.6 一種改進算法6.4 最佳合併模式6.4.1 問題描述6.4.2 貪心法求解6.4.3 算法正確性6.5 最小代價生成樹6.5.1 問題描述6.5.2 貪心法求解6.5.3 普裡姆算法6.5.4 克魯斯卡爾算法6.5.5 算法正確性6.6 單源最短路徑6.6.1 問題描述6.6.2 貪心法求解6.6.3 迪傑斯特拉算法6.6.4 算法正確性6.7 磁帶最優存儲6.7.1 單帶最優存儲6.7.2 多帶最優存儲6.8 貪心法的基本要素6.8.1 最優量度標準6.8.2 最優子結構本章小結習題6第7章 動態規劃法7.1 一般方法和基本要素7.1.1 一般方法7.1.2 基本要素7.1.3 多段圖問題7.1.4 資源分配問題7.1.5 關鍵路徑問題7.2 每對結點間的最短路徑7.2.1 問題描述7.2.2 動態規劃法求解7.2.3 弗洛伊德算法7.2.4 算法正確性7.3 矩陣連乘7.3.1 問題描述7.3.2 動態規劃法求解7.3.3 矩陣連乘算法7.3.4 備忘錄方法7.4 最長公共子序列7.4.1 問題描述7.4.2 動態規劃法求解7.4.3 最長公共子序列算法7.4.4 算法的改進7.5 最優二叉搜索樹7.5.1 問題描述7.5.2 動態規劃法求解7.5.3 最優二叉搜索樹算法7.6 0/1背包7.6.1 問題描述7.6.2 動態規劃法求解7.6.3 0/1背包算法框架7.6.4 0/1背包算法7.6.5 性能分析7.6.6 使用啟發式方法7.7 流水作業調度7.7.1 問題描述7.7.2 動態規劃法求解7.7.3 Johnson算法本章小結習題7第8章 回溯法8.1 一般方法8.1.1 基本概念8.1.2 剪枝函數和回溯法8.1.3 回溯法的效率分析8.2 n-皇后8.2.1 問題描述8.2.2 回溯法求解8.2.3 n-皇后算法8.2.4 時間分析8.3 子集和數8.3.1 問題描述8.3.2 回溯法求解8.3.3 子集和數算法8.4 圖的著色8.4.1 問題描述8.4.2 回溯法求解8.4.3 圖著色算法8.4.4 時間分析8.5 哈密頓環8.5.1 問題描述8.5.2 哈密頓環算法8.6 0/1背包8.6.1 問題描述8.6.2 回溯法求解8.6.3 限界函數8.6.4 0/1背包算法8.7 批處理作業調度8.7.1 問題描述8.7.2 回溯法求解8.7.3 批處理作業調度算法本章小結習題8第9章 分枝限界法9.1 一般方法9.1.1 分枝限界法概述9.1.2 LC分枝限界法9.1.3 15謎問題9.2 求最優解的分枝限界法9.2.1 上下界函數9.2.2 FIFO分枝限界法9.2.3 LC分枝限界法9.3 帶時限的作業排序9.3.1 問題描述9.3.2 分枝限界法求解9.3.3 帶時限作業排序算法9.4 0/1背包9.4.1 問題描述9.4.2 分枝限界法求解9.4.3 0/1背包算法9.5 旅行商問題9.5.1 問題描述9.5.2 分枝限界法求解9.6 批處理作業調度9.6.1 問題描述9.6.2 分枝限界法求解9.6.3 批處理作業調度算法本章小結習題9第3部分 求解困難問題第10章 NP完全問題10.1 基本概念10.1.1 不確定算法和不確定機10.1.2 可滿足性問題10.1.3 P類和NP類問題10.1.4 NP難度和NP完全問題10.2 Cook定理和證明10.2.1 Cook定理10.2.2 簡化的不確定機模型10.2.3 證明Cook定理10.3 一些典型的NP完全問題10.3.1 最大集團10.3.2 頂點覆蓋·

算法的最優性與所求解的問題自身的復雜程度有關。例如，對于在n個元素的集合中尋找一個最大元素的問題，分析表明，任何通過元素之間比較的方式來求解此問題的正確算法，至少需要進行n-1次元素間的比較運算。如果某人編寫一個算法，聲稱他的算法對任意一個有n個元素的集合，僅需執行n-2次元素比較便可求得集合中的最大元素，那么，可以肯定，該算法不可能是正確的。如果一個實際的正確算法，在最壞情況下的確只需n-1次元素比較便可求得最大元素，那么它可稱為最優的。因為n-1次元素比較是求最大元問題所需時間的下界。本書將討論排序和查找問題的時間下界。然而遺憾的是，許多看似簡單的問題，至今仍無法知曉求解該問題所需的時間F界是多少，如：矩陣乘法。
2.1.2影響程序運行時間的因素
一個程序的運行時間是程序運行從開始到結束所需的時間。影響程序運行時間的因素主要有：
（1）程序所依賴的算法；
（2）問題規模和輸入數據；
（3）計算機系統性能。
首先，很容易想到，對于同一程序和相同的輸入數據，如果在不同的計算機上運行該程序，所需的運行時間幾乎可以肯定是不同的。這是因為計算機的硬件性能可能不同，特別是處理器（CPU）速度可能相差很多。程序設計語言及其編譯器不同，生成的目標代碼的效率也會各異。操作系統也是影響計算機系統性能的因素之一。這就是說，算法運行所需的時間依賴于計算機軟、硬件系統。
如果排除計算機的因素，假定在完全相同的計算機環境下運行程序，情況又如何呢？很顯然，求解同一個問題的不同算法，其程序運行時間一般不同。一個好的算法運行時間較少。算法自身的好壞對運行時間的影響是根本的和起決定作用的。例如，使用不同的排序算法對同一組元素進行排序，程序運行的時間通常是不相同的。
程序的一次運行是針對所求解問題的某一特定實例（instance）而言的。例如，執行一個排序算法，需要輸入一組待排序的元素，對該組特定元素的排序是排序問題的一個實例。待排序的元素個數是一個排序問題實例的重要特征（characteristics），它直接影響排序算法的執行時間和所需的存儲空間。因此，分析算法性能需要考慮的一個基本特征是問題實例的規模（size）。使用同一個排序算法對100個整數進行排序與對10000個整數進行排序所需的時間很顯然是不同的。問題的規模一般是指輸入數據的量，必要時也考慮輸出數據的量。對于兩個m×n矩陣加法問題的規模，通常考慮輸入矩陣的元素個數，它正比于m×n；但對于一個由計算機隨機生成并打印一個矩陣的算法來說，其運行時間與所生成的矩陣元素的個數有關，即與輸出數據的量有關。還有一種情況，例如，現代密碼算法需要進行超過200位長度的十進制數運算，顯然算法的運行時間與輸入（輸出）數據的數值大小有關，此時，問題的規模必須考慮數據的數值大小。