電腦演算法基礎 第2版

沈孝鈞

電腦演算法基礎 第2版
  • 出版商: 機械工業
  • 出版日期: 2024-04-01
  • 售價: $474
  • 貴賓價: 9.5 折 $450
  • 語言: 簡體中文
  • 頁數: 408
  • 裝訂: 平裝
  • ISBN: 7111746597
  • ISBN-13: 9787111746591
  • 相關分類: Algorithms-data-structures

    • 立即出貨 (庫存=1)

買這商品的人也買了...

相關主題

商品描述

本書作者根據自己幾十年的教學與研究實踐，系統地總結了電腦演算法的設計與分析方法，
涵蓋了大部分最主要的演算法技術，包括分治法、貪心演算法、動態規劃、圖的遍歷技術、窮舉搜尋等，
涉及一系列重要的演算法問題，包括排序問題、選擇問題、最小生成樹問題、
最短路徑問題、網路流問題、二分圖的匹配問題、字串的匹配問題和幾何演算法問題等。
作者力求透過有趣和難易適中的案例說明演算法的特點和應用場景，使讀者能夠理解如何針對具體問題選擇高效的演算法。

目錄大綱

目　　錄
前言
教學建議
第1章　概論　1
1.1　演算法與資料結構及程式的關係　1
1.1.1　什麼是演算法　1
1.1.2　演算法與資料結構的關係　1
1.1.3　演算法與程式的關係　2
1.1.4　選擇排序的範例　2
1.1.5　演算法的偽碼表示　2
1.2　演算法複雜度分析　 3
1.2.1　演算法複雜度的度量　3
1.2.2　演算法複雜度與輸入資料規模的關係　4
1.2.3　輸入資料規模的度量模型　4
1.2.4　演算法複雜度分析中的兩個簡化假設　5
1.2.5　最好情況、最壞情況和平均情況的複雜度分析　5
1.3　函數成長漸近性態的比較　6
1.3.1　三種比較關係及O、、記號　6
1.3.2　表示演算法複雜度的常用函數　7
1.4　問題複雜度與演算法複雜度的關係　9
1.4.1　問題複雜度是演算法複雜度的下界　9
1.4.2　問題複雜度與最佳演算法　9
1.4.3　易處理問題和難處理問題　9
習題　 10
第2章　分治法　11
2.1　分治法原理　11
2.1.1　二元搜尋的例子　11
2.1.2　表示複雜度的遞推關係　12
2.2　遞推關係式求解　13
2.2.1　替換法　13
2.2.2　序列求和法與遞歸樹法　15
2.2.3　常用序列和公式　16
2.2.4　主方法求解　18
2.3　範例示範　19
習題　 20
第3章　基於比較的排序演算法　24
3.1　插入排序　　24
3.1.1　插入排序的演算法 24
3.1.2　插入排序演算法的複雜度分析　25
3.1.3　插入排序的優缺點　26
3.2　合併排序　26
3.2.1　合併演算法及其複雜度　26
3.2.2　合併排序的演算法及其複雜度　27
3.2.3　合併排序的優缺點　29
3.3　堆排序　 30
3.3.1　堆的資料結構　30
3.3.2　堆的修復演算法及其複雜度　31
3.3.3　為輸入資料建堆　32
3.3.4　堆排序演算法　33
3.3.5　堆排序演算法的複雜度　34
3.3.6　堆排序演算法的優缺點　35
3.3.7　堆用作優先隊列　35
3.4　快排序　36
3.4.1　快排序演算法　36
3.4.2　快排序演算法最壞情況複雜度　39
3.4.3　快排序演算法平均狀況複雜度　40
3.4.4　快排序演算法最好情況複雜度　41
3.4.5　快排序演算法的優缺點　42
習題　 42
第4章　不基於比較的排序演算法　46
4.1　比較排序的下界　46
4.1.1　決策樹模型及排序最壞情況下界　46
4.1.2　二元樹的外路徑總長與排序平均情況下界　 49
4.1.3　二元樹的全路徑總長與堆排序最好情況下界　 51
4.2　不基於比較的線性時間排序演算法　54
4.2.1　計數排序　 54
4.2.2　基數排序　57
4.2.3　桶排序　58
習題　60
第5章　中位數和任一順序數的選擇　63
5.1　問題定義　63
5.2　最大數與最小數的選擇　63
5.2.1　最大與最小順序數的選擇演算法及其複雜度　64
5.2.2　同時找出最大數與最小數的演算法　65
5.3　線性時間求任一順序數的演算法　66
5.3.1　最壞情況複雜度為O(n)的演算法 66
5.3.2　平均情況複雜度為O(n)的演算法　 68
5.4　求k個最大順序數的演算法　69
5.4.1　一個理論連結實際的問題　69
5.4.2　利用堆疊來找k個最大順序數的演算法　 70
5.4.3　利用錦標賽樹來找k個最大順序數的演算法　70
習題　 71
第6章　動態規劃　 73
6.1　動態規劃的基本原理　73
6.2　矩陣連乘問題　 75
6.2.1　定義子問題　75
6.2.2　歸納公式　77
6.2.3　演算法偽碼與範例　78
6.3　最長公共子序列問題　81
6.3.1　定義子問題　81
6.3.2　歸納公式　82
6.3.3　演算法偽碼與範例　82
6.4　最佳二元搜尋樹問題　84
6.4.1　定義子問題和歸納公式　85
6.4.2　演算法偽碼與範例　87
6.5　多級圖及其應用　 89
6.6　最長遞增子序列問題　92
6.6.1　定義子問題　93
6.6.2　歸納公式　93
6.6.3　演算法偽碼與範例　93
習題　 95
第7章　貪心演算法　 103
7.1　最佳郵局設定問題　103
7.2　一個簡單的最佳活動安排問題　105
7.3　其他最佳活動安排問題　106
7.3.1　兩個大禮堂的最佳活動安排問題　106
7.3.2　等長時間的活動的最佳安排問題　109
7.4　哈夫曼編碼問題　112
7.4.1　前綴碼　112
7.4.2　最佳前綴碼－哈夫曼編碼　114
7.5　最佳加油計畫問題　118
7.5.1　最佳加油計畫問題的描述　118
7.5.2　貪心演算法的基本思路　119
7.5.3　貪心演算法的偽碼　120
習題　 121
第8章　圖的周遊演算法　 128
8.1　圖的表示　128
8.1.1　鄰接表　129
8.1.2　鄰接矩陣 129
8.2　廣度優先搜尋及應用程式　130
8.2.1　廣度優先搜尋策略　130
8.2.2　廣度優先搜尋演算法及距離樹　131
8.2.3　無向圖的二著色問題　133
8.3　深度優先搜尋及應用　136

類似商品