# 麻省理工學院公開課-算法導論_第一講-課程簡介及演算法分析
###### tags: `MIT` `Algorithms` `網易`

[課程連結](http://open.163.com/newview/movi/free?pid=M6UTT5U0I&mid=M6V2T1JGF)

## Analysis of Algorithms
演算法分析是關於電腦程式效能與資源利用的理論研究，特別觀注在效能身上，我們要學習如何可以讓事情處理的更快。雖然有不少事情比效能還要重要，但效能已經決定"行不行"。舉例來說，目前很多系統需求為real-time，如果程式的執行速度不夠快，那就直接意謂著做不到。演算法要做的就是將不可能化為可能。

課程中提到，為什麼演算法是基礎?好的演算法決定執行的速度，我們願意拿多少速度來交換其它比執行速度更快議題，像是安全性，或者為什麼用java而不是用更快的c?

## Problem: sorting

排序是一個演算法中非常古老的議題

給定一個輸入序列$a_1, a_2, \cdots, a_n$，我們希望得到一個輸出$a_1', \cdots, a_n'$，其中$a_1' < a_2' < \cdots < a_n'$，由小到大排列。

## Insertion sort

課程中會以pseudocode的方式來呈現演算法的過程，這不是一個正式的程式碼，是一個概念。

1. 外圈loop的條件為$j \leftarrow 2 \space \text{to} \space n$
2. 內圈loop的條件為$i \leftarrow j - 1$
3. 內圈loop會遞減到0為止
4. 已經排序過的就視為invariant

每次的排序目的就是增加已經排序過的數值的長度，也就是簡報中的sorted處。


整個大致過程是：
* 我們找一個$j$，然後將$j-1$這個所在的index(課程中定義為key)的value往$j$複製，一直到找到適合這個key-value($j$)的位置，然後插入(因此稱為insertion sort)
* 接續執行$j+1$

從課堂的範例可以很清楚看到，排序是從第2個元素開始跟第1個元素比較。


running time取決於很多因素：
* input本身，舉例來說，input本身已經是有序的，那自然insertion sort就不需要處理過多事情，至少內圈的部份都不用處理了，而最糟的情況就是整個是逆序的，那全部都要重來
* input size，愈大，那處理時間自然愈長

我們會希望知道整個演算法的執行時間的upper bound，這代表著對使用者的一種承諾，這演算法最多三秒完成，跟這演算法最少三秒，但你不知道最多是不是三年完成，這是兩個完全不一樣的概念。


因此對於分析演算法的執行時間，我們通常只觀注於Worst-case，

符號約定：
* T(n)：給定任意的input size-n，其"最大"執行時間，這意味著只會有一個時間，拿掉"最大"那就不是這個意思了

另外還有Average-case，這但牽扯到期望值，那就跟機率有關，需要做點假設，假設整個input size是uniform distribution，不過基本上不會談到。

最後，還有Best-case，但這是假的(bogus)，no good，因為你可以作弊，弄些東西讓它看起執行的很快，但實際上大多數情況並不是這樣的。


那insertion sort的worst-case為何?這取決幾個因素：
* 執行演算法的電腦
* 如果我們想看的是相對速度，那就是在同一台電腦上執行兩個演算法
* 如果我們想看的是絕對速度，那就是在不同電腦上執行同一個演算法

但這談不完，太多因素了，所以我們會從演算法的大方向來看，也就是asymptotic analysis(漸近分析)，我們忽略掉機器相關的因素，而且不是直接的去計算實際的執行時間，而是演算法執行時間的增長情況，也就是當n無限大的時候，其T(n)為何。


這邊說明幾個漸近符號：
1. $\Theta$，觀念很簡單，就是去掉低階項，然後忽略掉前面的常數
* 舉例來說，$3n^3 + 90n^2 - 5n + 6046 = \Theta(n^3)$

這意謂著，如果$n$趨近於無限，那$T(n^2)$一定會比$T(n^3)$還要快，即使$T(n^2)$是在較慢的電腦，而$T(n^3)$是在較快的電腦上執行，因此，漸近符號的表示一次滿足了上面我們所提的絕對、相對速度，記得，我們觀注的是隨著input size增長而增長的執行時間。


上圖我們可以看到$\Theta(n^2)$與$\Theta(n^3)$執行時間的趨勢線，不管前面的趨勢如何，它們兩個就是會在$n_0$之後，$\Theta(n^2)$永遠有著比$\Theta(n^3)$更小的開銷。

但以工程技術的角度來看，有時候$n_0$大到電腦無法計算。這也是為什麼有些時候我們會對執行速度較慢的演算法有興趣，因為即使它們以漸近分析來看是比較慢的，但在合理的input size內，它們的執行速度還是快的。


剛才我們說過，insertion sort的worst-case就是逆排，也就是由大到小的排序。

假設，每一個元素的操作所花費的時間都是常數時間，而因為我們做的是漸近分析，因此這常數是多少並不是那麼重要。

$T(n) = \sum_{j=2}^n \Theta(j)$，後面的$\Theta(j)$是來自外層迴圈，當$j=2$的時候，內圈的`do`也會做2次的操作，因為我們是考慮worst-case，當$j=3$，那`do`就做3次的操作，因此內層`do`的操作就是$\Theta(j)$，而$T(n) = \sum_{j=2}^n \Theta(j) = \Theta(n^2)$，這是一個等差級數的計算，$1+2+3+4+...+n = \dfrac{n(n + 1)}{2} = \dfrac{n^2}{2} + \dfrac{n}{2}$。

在$n$很小的情況下，insertion sort還算是快，但是當$n$非常大的時候就不是這麼一回事了。


Merge Sort，另一種排序演算法

Merge Sort A[1 ... n]
* 判斷是否n = 1，那就沒有排序的必要
* 當n > 1，則從$\lceil n/2 \rceil$切半遞迴排序，變成$A[1 ... \lceil n/2 \rceil]$與$A[\lceil n/2 \rceil ... n]$
* 合併兩個各自排序好的資料


圖上可以看到兩個各別排序好的資料，而最小值一定在兩個陣列的第一個索引值其中一個，比較誰小之後拿到最終輸出的陣列中，然後刪掉，下一步一樣的，最小值依然在兩個陣列的第一個索引值，一樣的比較誰小，拿到最終輸出的陣列中。

我們做的永遠都是比較兩個陣列的第一個索引值，沒有其它的事，對於$n$個輸入的時間複雜度為$\Theta(n)$，這亦稱為linear time(線性時間)


1. 第一次的判斷只是確定長度，這是一個常數時間，因此為$\Theta(1)$
2. 我們將長度切為兩段，執行兩個工作，因此為$2T$，而每次處理的工作是原來的一半，因此為$2T(n/2)$
3. 合併兩個排序好的資料，這剛已說，為$\Theta(n)$


$$
T(n) =
\begin{cases}
\Theta(1), & \text{if $n=1$} \\
2T(n/2) + \Theta(n), & \text{if $n > 1$}
\end{cases}
$$

解這時間複雜度的方法為Recursion tree(遞迴樹)，$T(n) = 2T(n/2) + cn$，如上圖所示，tree root為cn，而左右兩邊各為$T(n/2)$，整體相加起來依然是$2T(n/2) + cn$。其中$c$可以視為當$n=1$或分解、合併步驟中處理每個element所需的時間。


就這樣一直的下去，最終的節點就是$\Theta(1)$，這意味著樹的高度會接近$\log n$，而最終的節點會有$n$，因為我們整個展開它。

可以發現到，每一層的執行時間都是$cn$，一直到最後$\Theta(n)$(不一定是$cn$，但不影響結果)，整個執行時間為$(cn)\log n + \Theta(n)$，因為高度就是$\log n$，意思就是我們有$\log n$個$cn$。而$(cn)\log n$比$\Theta(n)$高階，忽略$\Theta(n)$，因此為$\Theta(n \log n)$。

很明顯，$\Theta(n \log n)$一定比$\Theta(n^2)$還要來的快，大約在$n > 30$之後，這就會非常明顯。