《演算法導論》筆記

ISBN 9786263248366（4/e，繁中譯本，Thomas H. Cormen et al. 著作，賴屺民譯）

經典的演算法導論，但是封面樹形圖在繁中譯本沒有出現。

Ch1、Ch2

任何輸入停止執行+正確答案=>演算法是正確的

1. 不一定有最好的解決方案
2. 有實際的應用

世上沒有一體適用的資料結構。

NP-complete：無法於特定時間內解決

• 平行模型演算法
• 線上演算法（輸入無法一次到位）

機械學習較成功的案例是，演算法中，人類無法理解的（比如自動翻譯）

插入排序法

vertex 頂點

迴圈不變性(loop invariant)

計算模型影響演算法的效率甚大

本書用一台單核的RAM（隨機存取機器）模型來當多數情況下的範例

輸入規模=>執行時間 （在RAM框架內）

一個假設「每行虛擬碼執行的時間是固定的」（雖然有時不是）

簡單的表示法：Big Theta、Big O

呼叫子程序的程序，和執行子程序的程序(caller, callee)分開計算

T(n) = a * n + k：執行時間是n的線性函數

插入排序法：

• 最壞時間，是n^2，即二次函數
• 隨機演算法：輸入不變下，演算法特性不同

通常在本書中僅找最壞狀況

平均請況通常糟如最壞狀況

感興趣的是增長率(rate of growth; order of growth)

我們只於多項式考慮首項

Θ(n^2) = theta of n-squared

big theta(Θ)表示增長率

演算法設計技術

漸增法=>插入排序法

分治法(divide-and-conquer)

分治法處理方法：

• 遞迴結構分成子問題
• 遞迴處理
• 結合子問題

各問題的狀況分成

• 基本情況
• 分解 -> 處理 -> 合併

A[p:r]

求中間索引值 = floor((p+r)/2)

=>遞迴分解

=> 漸次求解

合併排序法，關鍵：

a[p:q] and a[q+1,r]

-> merge(A,p,q,r)

-> a[p:r]

合併要 Θ(n)時間。

合併演算法的T(n) = 2T(n/2) + Θ(n)

Ch4介紹主定理

Ch 3

參考此pdf