演算法導論第一課

03-07

1. 演算法分析的定義和意義

Analysis of Algorithms is the theoretical study of computer program performance and resource usage.

在計算機領域有很多內容比performance更重要，例如代碼的correctness、maintainability、security、simplicity等，那麼如果演算法的性能沒那麼重要，我們為什麼還要學習演算法性能呢？原因有以下幾點：

通常performance直接決定了工作是否可用，可以將不可行變成可行，演算法總是處於解決問題的前沿
演算法是一種描述程序行為的語言，已經成為了一種語言而廣泛應用
演算法是用戶體驗的前提

2. 運行時間和演算法分析

運行時間取決於很多東西，例如

取決於input本身，例如排序問題中，如果輸入的是已經排好序的數組，那麼需要的操作就很少，運行時間就大大降低
取決於input size，例如輸入數組大小是6或者600百萬

通常我們將input size參數化，然後根據參數化之後的 $n$ 來進行分析

通常我們更想知道upper bound, 因為這樣能夠給用戶guarantee，例如演算法運行時間不會超過三秒鐘

分析的類型包括三種

worst-case analysis

$T(n)$ 表示針對所有輸入的maximum time，例如在排序問題中完全逆序的數組 $A$
如果我們不關注最大值，那麼 $T(n)$ 和n之間就只是有關係，而無法進行精確衡量，因為同一個 $n$ 的不同輸入會產生多個 $T(n)$ ；而如果關注最大值，就只有一個最大值，那麼 $T(n)$ 和n之間就是函數關係

average-case analysis

$T(n)$ 表示針對所有size為 $n$ 的輸入時間的平均
因為輸入的概率並不知道，因此需要對概率進行假設，最常見的假設是平均假設，所有size為 $n$ 的輸入均等出現

best-case analysis

通常稱為bogus，基本上很難出現，因此很少進行這樣的分析

演算法分析的Big Idea包括兩個

忽略掉依賴於機器的常量
關注運行時間的增長，而不是去檢查真正的運行時間

3. Asymptotic Analysis(漸進分析)

首先我們定義漸進符號表示， $Theta(n)$ 代表去掉低階項、忽略高階項的常數因子之後的表示，例如 $3n^{3}+50n^{2}+44n+16$ 用漸進符號表示為 $Theta(n^{3})$ .

採用漸進符號能夠同時滿足我們對relative speed和absolute speed的比較，因此 $Theta(n^{3})$ 和 $Theta(n^{2})$ 相比，總會有 $n_{0}$ 使得 $Theta(n^{2})$ 的演算法比 $Theta(n^{3})$ 的性能好，哪怕運行 $Theta(n^{3})$ 的計算機是超級計算機，而運行 $Theta(n^{2})$ 的計算機是很爛的機器。

我們對insertion sort進行分析

$T(n)=sum_{j=2}^{n}{Theta(j)}=Theta(n^{2})$

對於 $n$ 比較小，演算法速度較快，當 $n$ 比較大時，演算法速度較慢

我們對merging sort進行分析

$T(n)=2T(n/2)+Theta(n)$

通過recursion tree technique可以得到： $T(n)=cncdot lgn+Theta(n)=Theta(nlgn)$