演算法讀書筆記

CH1

MergeSort: divide-and-conquer經典範例

輸入: 一個沒有規則的數字陣列。
輸出: 排序好的數字陣列
MergeSort是divide-and-conquer方法的展現。recursive divide-and-conquer algorithm是不斷的利用遞迴把問題拆變小，直到問題不能在拆分後再把結果合併回來。對於array把問題變小的方式最直覺就是把array拆兩半，拆到最後再慢慢把array合併回來。

下面是MergeSort的Pseudocode

Input: array A of n distinct integers.
Output: array with the same integers, sorted from
smallest to largest.
// ignoring base cases
C := recursively sort first half of A
D := recursively sort second half of A
return Merge (C,D)

這段程式碼有幾點可以注意

• base cases: 也就是沒辦法再分割，沒辦法再繼續遞迴，返回它自身就是他的回傳值。
• Pseudocode不包含實作細節，例如如果輸入是奇數個元素的狀況下，我們可以將多出的一個element放入一半被拆分的array。Pseudocode只記錄概念上的運作方式，並不會加入任何和個別程式語言有關的實作細節。

在上面的Pseudocode還有一個Merge函式，下面是關於Merge函式的Pseudocode。想法是將
排序好的C和D array依序再排序成新的排序過的array。

Merge
Input: sorted arrays C and D (length n/2 each).
Output: sorted array B (length n).
Simplifying assumption: n is even.
1 i := 1
2 j := 1
3 for k := 1 to n do
4     if C[i] < D[j] then
5         B[k] := C[i] // populate output array
6         i := i + 1 // increment i
7     else // D[j] < C[i]
8         B[k] := D[j]
9         j := j + 1

1.5 MergeSort: The Analysis

計算演算法速度的方式就是計算這個演算法總共需要執行多少次最基礎的計算。也就是計算Running Time

1.5.1 Running Time of Merge

Lemma 1.1 (Running Time of Merge) 對於合併兩個長度為$l/2$的array的，合併最多只會用到6l步(可從前面Merge的Pseudocode推論。)

1.5.2 Running Time of MergeSort

Theorem 1.2 (Running Time of MergeSort) : 對於每個長度$n\geq 1$的array， MergeSort的Merge步驟最多執行$6nlog_2n+6n$個步驟

1.5.3 Proof of Theorem 1.2

從recursion tree 可以看到，每多一個遞迴level，工作被分割的總數就是兩倍，但是工作的array長度是上一個level的一半。因此level-j的subproblems為$2^j$，而level-j地array長度為$n/{2^j}$。根據上一節的結論，對於每個長度$n\geq 1$的array， MergeSort最多執行$6nlog_2n+6n$個步驟。如果我們只看level-j遞迴呼叫以外的工作，就只剩下Merge步驟，因此每個level的運算步驟總共為$6n/2^j$
於是我們可以得到level-j所有的運算步驟總數為$2^j \cdot \frac{6n}{2^j}=6n$
而MergeSort總共會有$log_x^n+1$個level，因此整個MergeSort總共的步驟為$6nlog_2n+6n$

1.6 Guiding Principles for the Analysis of Algorithms

我們在計算演算法速度的時候會有三個原則，以下逐一介紹。因為在有些時候為了簡化計算，我們會做出一些取設，但是為了讓數學分析依然能夠預測演算法的速度，因此我們才用到下面三個原則。

Principle #1: Worst-Case Analysis

在前面推導的結果$6nlog_2n+6n$是不管n是什麼數字這個公式都能夠使用。也就是我們沒有對n做任何的假設。這種分析法稱為Worst-Case Analysis，因為這個演算法最慢的計算時間依然符合這個公式。
除了Worst-Case Analysis之外還有average-case analysis和 analysis of benchmark instances可以使用，但是這兩個使用的時候必須非常清楚所處理的問題的條件。

Principle #2: Big-Picture Analysis

在運行時間界限中，我們不應過於關注小的常數因子或低階項。

參考

Algorithms Illuminated