算法設(shè)計與分析

● 緊扣教學(xué)規(guī)律，合理設(shè)計內(nèi)容結(jié)構(gòu)。

● 讓讀者掌握現(xiàn)今流行技術(shù)的底層算法及復(fù)雜度分析。

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

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

在面臨經(jīng)濟發(fā)展轉(zhuǎn)型、科學(xué)技術(shù)“卡脖子”等問題的背景下，高等教育的重點是加強基礎(chǔ)學(xué)科、新興學(xué)科、交叉學(xué)科建設(shè)，加快建設(shè)優(yōu)勢學(xué)科。計算機科學(xué)與技術(shù)學(xué)科緊跟國內(nèi)外計算機科學(xué)與技術(shù)前沿，為國家培養(yǎng)計算機科學(xué)與技術(shù)高層次人才，而計算機科學(xué)與技術(shù)專業(yè)是一個計算機系統(tǒng)與網(wǎng)絡(luò)兼顧的計算機學(xué)科寬口徑專業(yè)，旨在培養(yǎng)具有良好的科學(xué)素養(yǎng)、具有自主學(xué)習(xí)意識和創(chuàng)新意識、科學(xué)型和工程型相結(jié)合的計算機專業(yè)高水平工程技術(shù)人才。

“算法設(shè)計與分析”是計算機科學(xué)與技術(shù)專業(yè)的核心課程，它將高級語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)和計算方法等內(nèi)容緊密地結(jié)合在一起，通過介紹常見的算法設(shè)計策略、復(fù)雜性分析方法和應(yīng)用，培養(yǎng)學(xué)生分析問題和解決問題的能力，使學(xué)生掌握算法設(shè)計的基本方法，熟悉算法分析的基本技術(shù)，并能熟練運用一些常用算法，為學(xué)生開發(fā)高效的軟件系統(tǒng)及參加相關(guān)領(lǐng)域的研究工作奠定堅實的基礎(chǔ)。

本書將社會上比較流行的、比較先進(jìn)的部分互聯(lián)網(wǎng)技術(shù)進(jìn)行分析，挖掘其底層借鑒的基本算法，讓讀者掌握現(xiàn)今流行技術(shù)的底層算法及復(fù)雜度分析，提高讀者的學(xué)習(xí)積極性及主動性，培養(yǎng)讀者積極探索的科學(xué)精神。

全書共分7章：

第1章 算法概述。簡單介紹了算法的概念，算法與程序的區(qū)別與聯(lián)系，算法的時間復(fù)雜度和空間復(fù)雜度分析。

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

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

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

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

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

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

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

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

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

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

編 者

2022年6月

第1章 算法概述 1
1.1 算法與程序 1
1.1.1 算法與程序概述 1
1.1.2 為什么要學(xué)習(xí)算法？ 1
1.1.3 算法的描述方法 2
1.1.4 解決問題的基本步驟 4
1.2 算法的時間復(fù)雜度 5
1.2.1 算法設(shè)計的例子 5
1.2.2 為什么需要對算法進(jìn)行復(fù)雜度
分析？ 8
1.2.3 算法的復(fù)雜度分析 9
1.2.4 算法時間復(fù)雜度的定義 11
1.2.5 運行時間的上界（O記號） 13
1.2.6 運行時間的下界（Ω記號） 15
1.2.7 運行時間的準(zhǔn)確界（Θ記號） 16
1.3 算法的空間復(fù)雜度 18
1.4 NP類問題 19
習(xí)題 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
習(xí)題 34
第3章 分治法 37
3.1 分治法引言 37
3.2 分治法的基本思想 37
3.2.1 基本思想 37
3.2.2 時間復(fù)雜度分析 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 循環(huán)賽日程表 56
習(xí)題 58
第4章 動態(tài)規(guī)劃 63
4.1 幾個實例 63
4.1.1 爬樓梯問題 63
4.1.2 國王挖金礦問題 64
4.1.3 矩陣連乘問題 65
4.2 動態(tài)規(guī)劃算法的基本思想 67
4.2.1 動態(tài)規(guī)劃算法的特征 67
4.2.2 動態(tài)規(guī)劃算法求解過程 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
習(xí)題 90
第5章 貪心算法 93
5.1 貪心算法引言 93
5.1.1 貪心算法實例 93
5.1.2 貪心算法的設(shè)計思想 95
5.2 活動安排問題 96
5.3 貪心算法的基本要素 99
5.4 兩種不同的背包問題 100
5.4.1 0-1背包問題 100
5.4.2 背包問題 101
5.5 最優(yōu)裝載問題 103
5.6 哈夫曼編碼 104
5.7 單源最短路徑 112
5.8 最小生成樹 118
5.8.1 最小生成樹性質(zhì) 119
5.8.2 Prim算法 119
5.8.3 Kruskal算法 122
5.9 多機調(diào)度問題 123
習(xí)題 126
第6章 回溯法 128
6.1 回溯法引言 128
6.2 回溯法的基本思想 129
6.2.1 問題的解空間 129
6.2.2 基本思想 132
6.2.3 構(gòu)造解空間的過程 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 高逐位整除數(shù) 157
6.8 圖的m著色問題 159
6.9 回溯法效率分析 163
習(xí)題 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
習(xí)題 192
參考文獻(xiàn) 194

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