● 緊扣教學規律，合理設計內容結構。

● 讓讀者掌握現今流行技術的底層算法及復雜度分析。

● 提供電子課件等資源，方便教學。

黨的二十大報告明確提出，教育、科技、人才是全面建設社會主義現代化國家的基礎性、戰略性支撐。必須堅持科技是第一生產力、人才是第一資源、創新是第一動力，深入實施科教興國戰略、人才強國戰略、創新驅動發展戰略，開辟發展新領域新賽道，不斷塑造發展新動能新優勢。要堅持教育優先發展、科技自立自強、人才引領驅動，加快建設教育強國、科技強國、人才強國，堅持為黨育人、為國育才，全面提高人才自主培養質量，著力造就拔尖創新人才，聚天下英才而用之。

在面臨經濟發展轉型、科學技術“卡脖子”等問題的背景下，高等教育的重點是加強基礎學科、新興學科、交叉學科建設，加快建設優勢學科。計算機科學與技術學科緊跟國內外計算機科學與技術前沿，為國家培養計算機科學與技術高層次人才，而計算機科學與技術專業是一個計算機系統與網絡兼顧的計算機學科寬口徑專業，旨在培養具有良好的科學素養、具有自主學習意識和創新意識、科學型和工程型相結合的計算機專業高水平工程技術人才。

“算法設計與分析”是計算機科學與技術專業的核心課程，它將高級語言程序設計、數據結構和計算方法等內容緊密地結合在一起，通過介紹常見的算法設計策略、復雜性分析方法和應用，培養學生分析問題和解決問題的能力，使學生掌握算法設計的基本方法，熟悉算法分析的基本技術，并能熟練運用一些常用算法，為學生開發高效的軟件系統及參加相關領域的研究工作奠定堅實的基礎。

本書將社會上比較流行的、比較先進的部分互聯網技術進行分析，挖掘其底層借鑒的基本算法，讓讀者掌握現今流行技術的底層算法及復雜度分析，提高讀者的學習積極性及主動性，培養讀者積極探索的科學精神。

全書共分7章：

第1章 算法概述。簡單介紹了算法的概念，算法與程序的區別與聯系，算法的時間復雜度和空間復雜度分析。

第2章 遞歸。通過實例介紹了遞歸方程的設計方法，同時給出求解遞歸方程的方法。

第3章 分治法。介紹了分治法的基本思想，并通過二分搜索、棋盤覆蓋、合并排序、快速排序等應用詳細介紹分治法的設計思想、時間復雜度分析。

第4章 動態規劃。先由幾個實例引出動態規劃算法的基本思想及求解過程，然后分析了備忘錄方法與動態規劃算法的異同，并通過最長公共子序列、最大子段和、合唱隊形問題、0-1背包問題詳細介紹動態規劃算法的設計方法、時間復雜度分析。

第5章 貪心算法。通過實例分析了貪心算法的設計思想、基本要素，并通過活動安排問題、背包問題、最優裝載問題、哈夫曼編碼等應用詳細給出貪心策略的設計方法、貪心策略的證明。

第6章 回溯法。本章首先介紹解空間的基本概念，并給出構造解空間的過程分析，然后介紹回溯法的框架，并通過裝載問題、n后問題、0-1背包問題等詳細介紹回溯法的構造過程，最后分析了影響回溯法效率的原因。

第7章 分支限界法。本章首先介紹分支限界法與回溯法的異同，然后通過單源最短路徑、裝載問題、0-1背包問題詳細介紹分支限界法的求解步驟。

本書采用C++語言作為表述手段，書中介紹了各種算法的設計思路、算法復雜性及實例分析，同時在每一章的章首部分增加了學習要點，每一章的章末附有和本章內容相關的習題，并免費提供電子課件。

本書的編寫得到了齊魯工業大學計算機科學與技術學部人才培養提升計劃優秀教材培育項目的支持，同時得到了齊魯工業大學教材建設基金資助，在此表示衷心的感謝。

本書由趙晶任主編，尉秀梅、李愛民、魯芹、姜雪松任副主編，編寫過程中的校對工作由碩士生鄒慶志、胡玉帥、張榮環、高帥、時俊康、豆希夢、吳棟林、曲相宇、秦宥煊、石明、王浩、張雪峰完成，在此表示感謝。

由于編者的知識和寫作水平有限，書稿雖幾經修改，仍難免存在缺點和錯誤，熱忱歡迎同行專家和讀者惠予批評指正，使本書不斷改進，日臻完善。

編 者

2022年6月

第1章 算法概述 1
1.1 算法與程序 1
1.1.1 算法與程序概述 1
1.1.2 為什么要學習算法？ 1
1.1.3 算法的描述方法 2
1.1.4 解決問題的基本步驟 4
1.2 算法的時間復雜度 5
1.2.1 算法設計的例子 5
1.2.2 為什么需要對算法進行復雜度
分析？ 8
1.2.3 算法的復雜度分析 9
1.2.4 算法時間復雜度的定義 11
1.2.5 運行時間的上界（O記號） 13
1.2.6 運行時間的下界（Ω記號） 15
1.2.7 運行時間的準確界（Θ記號） 16
1.3 算法的空間復雜度 18
1.4 NP類問題 19
習題 19
第2章 遞歸 21
2.1 遞歸算法 21
2.2 求解遞歸方程 28
2.2.1 迭代法 28
2.2.2 差消法 29
2.2.3 遞歸樹法 30
2.2.4 主定理法 31
習題 34
第3章 分治法 37
3.1 分治法引言 37
3.2 分治法的基本思想 37
3.2.1 基本思想 37
3.2.2 時間復雜度分析 39
3.3 二分搜索 40
3.3.1 尋找假幣 40
3.3.2 二分搜索問題 42
3.4 棋盤覆蓋 44
3.5 合并排序 47
3.6 快速排序 51
3.7 金塊問題 53
3.8 循環賽日程表 56
習題 58
第4章 動態規劃 63
4.1 幾個實例 63
4.1.1 爬樓梯問題 63
4.1.2 國王挖金礦問題 64
4.1.3 矩陣連乘問題 65
4.2 動態規劃算法的基本思想 67
4.2.1 動態規劃算法的特征 67
4.2.2 動態規劃算法求解過程 68
4.3 備忘錄方法 71
4.4 最長公共子序列 71
4.4.1 最長公共子序列問題 71
4.4.2 所有最長公共子序列 76
4.5 最大子段和 79
4.6 合唱隊形問題 83
4.7 0-1背包問題 85
習題 90
第5章 貪心算法 93
5.1 貪心算法引言 93
5.1.1 貪心算法實例 93
5.1.2 貪心算法的設計思想 95
5.2 活動安排問題 96
5.3 貪心算法的基本要素 99
5.4 兩種不同的背包問題 100
5.4.1 0-1背包問題 100
5.4.2 背包問題 101
5.5 最優裝載問題 103
5.6 哈夫曼編碼 104
5.7 單源最短路徑 112
5.8 最小生成樹 118
5.8.1 最小生成樹性質 119
5.8.2 Prim算法 119
5.8.3 Kruskal算法 122
5.9 多機調度問題 123
習題 126
第6章 回溯法 128
6.1 回溯法引言 128
6.2 回溯法的基本思想 129
6.2.1 問題的解空間 129
6.2.2 基本思想 132
6.2.3 構造解空間的過程 133
6.3 回溯法框架 137
6.3.1 遞歸回溯 137
6.3.2 迭代回溯 138
6.3.3 子集樹 138
6.3.4 排列樹 139
6.4 裝載問題 140
6.5 n皇后問題 146
6.6 0-1背包問題 151
6.7 高逐位整除數 157
6.8 圖的m著色問題 159
6.9 回溯法效率分析 163
習題 164
第7章 分支限界法 165
7.1 分支限界法的基本思想 165
7.1.1 分支限界法與回溯法的異同 165
7.1.2 分支限界法求解步驟 166
7.1.3 常見的兩種分支限界法 167
7.2 單源最短路徑問題 178
7.3 裝載問題 181
7.4 0-1背包問題 187
習題 192
參考文獻 194

1. 信息技術基礎（麒麟操作系統+WPS Office） [主編　芮雪　蔣莉　王亮亮]
2. Office高級應用項目式教程（第2版） [主編 李觀金 張倩文 黎夏克 ]
3. 巧用翻譯學英語：英漢互譯500例 [王學文 著]
4. 高等教育多維評價體系構建與高質量發展研究 [張妍 著]
5. 系統規劃與管理師章節習題與考點特訓（第二版） [主編 薛大龍]
6. 計算機操作系統實踐指導（openEuler版） [主編 秦光 曾陳萍 岳付強]
7. 信息系統管理工程師真題及模考卷精析（適用機考） [主 編 薛大龍 程 剛 上官緒]
8. 航海類院校體育教育教學研究 [張利超 李寧 著]
9. 新時代背景下我國職業教育產教融合長效機制建設研究 [王玉賢 著]
10. 電路分析 [主編 李飛 毛先柏]
11. 信息系統管理工程師（適用第2版大綱）一站通關 [指尖瘋　編著]
12. 傳統山水畫論解讀與實踐 [陳鈉 著]
13. 網絡工程師備考一本通（適配第6版考綱） [夏杰 編著]
14. 陳孝云的職教理想與情懷 [祝吉太 江傳瑞 張義廷 著]
15. 地方本科院校電子信息學科課程思政案例集 [王甫]
16. Excel數據處理與分析（第二版） [主編 張志明 鄒 蕾]
17. 網絡工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
18. 倉儲管理實務（第二版） [周寧武 編著]
19. 基于AE與C#的地理信息系統二次開發 [李小根 賈艷昌 喬翠平 姜彤 ]
20. 2023年長沙市文化和旅游業發展報告 [主編 陳莉]
21. 舞臺化妝造型設計 [主編 劉思彤 張 濤 張憶雨]
22. 產教融合視角高校體育專業實踐教學體系構建研究 [楊柳青 葉華兵 著]
23. 知識圖譜及應用案例 [張善文 黃文準 于長青 陳明淑]
24. Python程序設計案例教程（微課版） [主編　石利平　田輝平　余以勝]
25. 皓月繁星：青少年兒童心理成長手冊 [主　編　林贊歌 副主編　杜志南]
26. 材料力學 [章寶華 趙新勝 徐斌]
27. 系統集成項目管理工程師考試32小時通關（第3版） [主編　薛大龍 副主編　上官緒陽]
28. 軟考論文高分特訓與范文10篇——系統分析師（第二版） [薛大龍 鄒月平 施游]
29. 黃河海勃灣水利樞紐防凌安全運行 [王戰領 王叢發 范瑜彬 著]
30. 大學生心理健康教育 [方雄 著]