2016/10/14 Algorithm

開始上chap8 Sorting in Linear Time
hw prob 7-1, 7-4

8.1 lower bond for sorting

• Comparision Sort: 數值之間需要依賴"彼此比較"來做排序的一種sorting method.  我們目前教過的所有sorting method中, 只有counting sort不是Comparision Sort, 其他都是
• Comparision Sort的下限是n lg(n), 可以用decision tree的方法去證明(樹高>=lg(n!)~n lg(n))
• Thus, HeapSort 和 MergeSort 已達到 Comparision Sort的asymptically optimal

8.2 counting sort

• T(n)=O(n+k)  < O(n lg(n))
• k: 資料種類數 
• 此法不適用於種類太多, 分布太發散的數據資料(因為k大=>T(n)大)
• Stable(必須由數據資料的後面sort回來才會stable(?))