《演算法導論》筆記

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

最後提到

• 單調遞增、單調遞減
• floor(x), ceil(x)
• a≡b (mod n)
• forall constant a>1, b in real number
• lim (n->inf) (n^b/a^n) = 0

• n->inf => n ^ b == 0(a^n)
• lim (n->inf) (1+x/n)^n = e^x

還有一些函數的定義（中學數學等）

Ch4 分治法

分治法是用遞迴的方法來解決一個問題。

• 基本情境：只需直接處理不用遞迴
• 遞迴情況下執行：
  • 分解
  • 處理
  • 合併

buttom out：

• 不需繼續遞迴即可以解決
• 分拆分治法的遞迴式

遞迴式

• 基本情況：fib(0) = 1
• 遞迴情況：fib(n) = fib(n-1)+fib(n-2)

n_0 = 閾常數，如果：

• n < n_0 => T(n) = θ (1)
• n >= n_0 => 於有限的遞迴次數終止

=>T(n)是演算法相關的(algorithmic)