● 緊扣教學(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)略、人才強(qiáng)國戰(zhàn)略、創(chuàng)新驅(qū)動發(fā)展戰(zhàn)略，開辟發(fā)展新領(lǐng)域新賽道，不斷塑造發(fā)展新動能新優(yōu)勢。要堅持教育優(yōu)先發(fā)展、科技自立自強(qiáng)、人才引領(lǐng)驅(qū)動，加快建設(shè)教育強(qiáng)國、科技強(qiáng)國、人才強(qiáng)國，堅持為黨育人、為國育才，全面提高人才自主培養(yǎng)質(zhì)量，著力造就拔尖創(chuàng)新人才，聚天下英才而用之。

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

“算法設(shè)計與分析”是計算機(jī)科學(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é)計算機(jī)科學(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 多機(jī)調(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. 輸水管線工程風(fēng)險管理 [張勇 黨亥生 著]
2. 民用航空飛機(jī)標(biāo)準(zhǔn)線路施工 [主編　王志敏　陳明]
3. 不息的水脈—大運河講談錄 [趙珩　著]
4. 實用運籌學(xué) [主編　邢育紅　于晉臣]
5. 三峽梯級電站水資源決策支持系統(tǒng)研究與開發(fā) [姚華明 潘紅忠 湯正]
6. 海南黎族民俗文化鑒賞 [龐國華　著]
7. 石墨烯在太赫茲及中紅外頻段電磁器件設(shè)計中的應(yīng)用 [李艷秀 莊華偉 著]
8. 電子技術(shù)（第二版） [主編 覃愛娜 李飛]
9. 辦公自動化高級應(yīng)用 [陳萍 朱曉玉]
10. 信息處理技術(shù)員考試32小時通關(guān) [薛大龍]
11. 電子產(chǎn)品設(shè)計案例教程（微課版）—基于嘉立創(chuàng)EDA（專業(yè)版） [王靜 莫志宏 陳學(xué)昌 丁紅]
12. C程序設(shè)計實踐教程 [劉衛(wèi)國]
13. C程序設(shè)計（慕課版） [劉衛(wèi)國]
14. Web技術(shù)開發(fā)教程（基于.NET開源MVC框架） [王合闖 韓紅玲 王青正 陳海蕊]
15. 商務(wù)英語翻譯教程（筆譯）（第四版） [主編 王軍平]
16. 智慧零售技術(shù)與應(yīng)用 [洪旭 著]
17. 建設(shè)工程法規(guī)實務(wù) [主編 余瀅]
18. 商務(wù)秘書理論與實務(wù)（第三版） [主編 張同欽]
19. 程序設(shè)計基礎(chǔ)實踐教程（C/C++語言版） [張桂芬 葛麗娜]
20. C++案例項目精講 [主編 楊國興]
21. 勞動爭議處理實務(wù) [主編 王秀卿 羅靜]
22. 工程數(shù)學(xué) [主編 郭立娟 王海]
23. 語音識別理論與實踐 [主編　莫宏偉]
24. 信息系統(tǒng)項目管理師章節(jié)習(xí)題與考點特訓(xùn)（第二版） [主編 薛大龍]
25. 武術(shù)基礎(chǔ)教程 [主編 李代勇 謝志民]
26. 計算機(jī)網(wǎng)絡(luò)實訓(xùn)教程 [主編 張浩軍 趙玉娟]
27. 畫法幾何與機(jī)械制圖習(xí)題集（多學(xué)時） [主編 趙軍]
28. HCIA-Datacom認(rèn)證題庫分類精講 [主 編 韓立剛]
29. SwiftUI完全開發(fā) [李智威 著]
30. 網(wǎng)絡(luò)規(guī)劃設(shè)計師備考一本通 [夏杰 編著]