Algorithm lecture 2

這一章節主要先以之前所學過的insertion sort當例子。開始解說如何分析一個程式的演算法。

首先，先從分析迴圈開始。initialization, maintenance, termination。三個部分構成一個迴圈。

以一個for迴圈為例：

for(j = 2 to A.length)
key = A[j]
i = j-1

Initialization: j等於2是否小於A這個陣列的長度。是第一次跑這迴圈。

Maintenance:每做一次迴圈，迴圈都會指向下一個陣列。

Termination:當A[j]超過陣列長度時會終止這個迴圈。

分析一個程式分析他的best case, worst case, average case。程式在執行的時候，當然有很多因素在影響。包括電腦的硬體，輸入的值...等等。worst case顧名思義，也就是說一個upper bound on the running time。而average case也往往跟worst case 的結果是一樣的。

設計一個演算法。這章節先大概介紹divide and conque。簡單的概念是把大問題劃分成小問題。解決小問題當然比大問題還簡單。等都解決之後再把結果湊起來，而大問題的解答也因此拼起來了。本章節是以merge sort來做範例說明。

最後用tree的概念。大致分析merge sort。(附在我下面的筆記)