Introduction2

演算法的設計通常有一些策略

1.Recursion <==> Divide & Conqure 將一個很複雜的問題切割成許多Subset，一個一個去解決
之後將Subset的結果合併起來 (DS 中通常需要Stack來支援) 是屬於Top-down的方式

2.Dynamic Programming 屬於bottom-up的方式，先解決小問題，之後再考慮較大的問題
看看目前的最佳解是否會比前一次的最佳解還要好，如果有，則取代原先的解 (需要Queue & Table 來記錄整個流程)

3.Greedy Method 屬於bottom-up的方式，找出每個小問題的最佳解(Local)，再一步步往上做，之後得到的是整體的最佳解(Global)，一般來說會牽涉到Backtracking

ex:如何找出 Top 2 Biggest element?
宣告一個陣列，每兩個一組去做比較，贏的人往上走，類似贏家樹，走到最上面的那一個element is Maximal
往後退一個的就是第二大的元素

演算法設計完成通常都要被驗證是否正確 ==> 使用數學歸納法
之後分析演算法的時間複雜度：
1.Worst Case
2.Average Case
3.Amortized Analysis ==> 將比較不常用的Operation 跟其他的Operation 去做成本的分攤
ex: 如果有一資料結構提供下列運算
Inset an element cost O(1)
Search an element cost O(lgN)
Delete an element cost O(n)
因為Delete較不常使用，所以跟Insert動作去分攤成本