今天結束Ch7 Quick Sort, 提早下課5min XD
今天的重點有兩個:
1. Time complexity analysis
要特別注意, 用recursive tree的方法分析worst case, 只能得到lower bound,
不能得到upper bound, 因為找到一個n^2的case也無法證明它是worst
2. 既然worst case是O(n^2), 為什麼Quick Sort會是最快?
因為它的average case: O(nlogn)雖然跟其他例如merge sort或heap sort一樣
但它的係數c會比其他sorting方法來得小
原因是它pivot一旦選好後, 比pivot大的和小的就從此分開, 不會互相比較到
總體而言比較次數是比較低的
(前提是, 你使用課本的神之演算法!! 老師還特別提醒不要改任何細節,
要不然結果一定跑不出來,
不是遇到special case就當掉, 不然就是要多很多if..else判斷式而拖慢整體速度)
是不是應該來寫一下code驗證一下XDD
- - -
今天終於借到這本:
- - -
我覺得演算法這門課, 重點其實不是它介紹的這些演算法本身
而是藉由分析這些可以達成同一目的的演算法寫法, 藉由trace code
讓我們培養欣賞演算法的品味
我覺得這才是真正重要的
沒有留言:
張貼留言