QuickSort 雖然很熟了,但重點是在它的分析。
開始講之前,老師講了 merge sort 的變化 (分成三堆),第二種是分成三堆後用 priority queue 分析的方式排序,第二種感覺比較聰明的做法,但是複雜度反而變差,而這種情況當分成√n 堆時,priority queue 會複雜度會比較低。
Divide and Conquer 若是 master thm 派不上用場,最後都有大絕招,猜,然後建構式歸納。
經過分析,每一次 partition 的複雜度取決於基準邊的選取,如果每次基準邊都選到最大,那複雜度會到θ(n2) 。若是基準邊都挑很平均,那麼複雜度就是 θ(nlgn)。
這是以結果論來看,我們不能夠很武斷的說,就是這樣啊~ 需要證明,用的方法就是把所有的 case 挑出來 (這種分析方式要好好學)。
值得提的是,若是基準邊是以固定比例來分,那複雜度還是θ(nlgn),跟一開始講的 merge sort 分三段一樣。
分析時先試著用直覺的觀念,考慮好壞交錯的情況,發現好壞交錯和最好的情況複雜度相同。
接下來分析 randomized 的版本,在實務應用中,為了避免 worst case 發生,會用 randomize 的方式打散。
分析 best case 只要分析Ω就好,因為上界已經是θ(nlgn)了。
而此分析講義沒有列出,在習題 ex.7.4-2 當作練習。 (跟 worst case 分析ο類似)
worst case 的分析就很重要,先猜,再證明。
這個證明利用到微積分的拋物線球極值的觀念。
再來就是分析 running time 了
有兩種分析方式,這個作者用觀察的方式來證明,這樣證明比較簡單,而習題有傳統分析的方式。
首先觀察 Quicksort 的特性
發現時間在於 Partition 中的比對次數。
所以可以假設 running time 等於,所有比對的次數。random variable 就派上用場了。
p.14 ~ p.17 用 indicator variable 估算出比對次數,這種解法要記!!
老師補充了第二種方式的證明。
p.18 ~ p.23
其中 p.20 頁課本直接用歸納證明,但 full-history recurrence 其實有經典的解法(前次項減後次項)
p.24 列出了一般教科書的解法。
Quicksort 是個很重要的問題,因此有很多種分析方式,熟悉這些事很重要的!!
接下來就用,
沒有留言:
張貼留言