檢視《演算法導論》筆記的原始碼

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

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

<span id="ch1ch2"></span>
== Ch1、Ch2 ==

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

# 不一定有最好的解決方案
# 有實際的應用

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

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

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

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

插入排序法

vertex 頂點

迴圈不變性(loop invariant)

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

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

輸入規模=&gt;執行時間 （在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(Θ)表示增長率

演算法設計技術

漸增法=&gt;插入排序法

分治法(divide-and-conquer)

分治法處理方法：

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

各問題的狀況分成

* 基本情況
* 分解 -&gt; 處理 -&gt; 合併

A[p:r]

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

=&gt;遞迴分解

=&gt; 漸次求解

[[合併排序法]]，關鍵：

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

-&gt; merge(A,p,q,r)

-&gt; a[p:r]

合併要 Θ(n)時間。

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

Ch4介紹主定理

==Ch 3==
參考[[:檔案:演算法導論Ch3部分筆記.pdf|此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 &lt; n_0 =&gt; T(n) = θ (1)
* n &gt;= n_0 =&gt; 於有限的遞迴次數終止

=&gt;T(n)是演算法相關的(algorithmic)

[[category:資訊]]