[Introduction To Algorithms] 第一堂: Getting Started

  

http://mitpress.mit.edu/algorithms/

第一堂課首先介紹教科書

之前看過幾遍，寫的很好，

得過很多獎項。

研究所也是用這本。

以我們熟悉的 insertion sort 和 merge sort 來導入演算法分析設計的概念。 設計一演算法時，首先要證明它是 correctness ，再來分析 performance。 以 insertion sort 的 correctness 證明來說，因為是迴圈寫的，所以通常是證明 loop invariant (利用數學歸納法)。但要注意的是，並不是要證明所有自然數都成立，因為 input 是有限的。

而要測量演算法的 performance 時，需要考慮演算法的執行環境- computation model。這本書的 model 是 RAM (single process random-access machine) 。而若是跑在multi-process computation model 下，評估的方式就不一樣了。 

一個演算法要餵資料給它執行，而執行的時間跟輸入資料的大小有關 - input size。要注意的是並不是每個演算法的 input size 都一樣，老師有提到像是 insertion sort 的 input size 和 prime 的 input size 不一樣。

insertion sort : the number of elements being sorted

prime:  the number of bits

若是 prime 以 insertion  sort 方式估計 performance 為 O(N .5) 但實際上它是指數的方式遞增。

這讓人有些混淆，課程最後講到 Hard Program 時會比較清楚。

分析一個演算法的 performance 有三種 case :

best case:     算好玩的而已。

average case:  通常 average 會向 worst case 靠 (老師逗了一個哏: 人生不如意之事，十之八九)

worst case:    最重要。

而評估 average case 最難，因為要靠機率來分析，教科書上會有蠻多例子來分析 average case....

分析演算法時並不是每個指令都要分析，找出執行次數最多的指令分析即可 -- basic operation

以迴圈來講，就找出巢狀迴圈的最內層分析就對了。

接下來就分析了 insertion sort 的 performance、開始講 merge sort，

Merge Sort 示意圖

分析 Merge Sort 時，有幾項困難，首先假設input size 是 2 的 次方，這樣就可以用 recursion tree 的方式做估算

這裡要注意的是， 2*T(n/2) 這個式子，是把 n 當作連續來處理，而 computer science 是離散的，正確寫法是 T(Floor n/2) + T(Ceiling n/2)，為什麼用連續的方式寫ok ，以及 c 和 2T(n/2)+cn 中這裡個 c 不是同樣的東西，怎麼可以都用 c 來表赤。


這就是下一堂課要介紹的了。


舒服!!