2011年4月28日 星期四

[Introduction To Algorithms] 第九堂: Medians and Order Statistics



這一講的是一群元素中,不用排序找出第幾大的問題。


















一開始講的是同時找最大最小,需要花得比較次數,直覺想是 2n-3 次,但其實只要 floor(3n/2)-2 次即可。9.1 利用狀態機 model了 Min-max problem 的lower bound。 p4~p10.




這個問題是選i小的問題,不用用到 nlog(n)的時間。基本上是學 quicksort 的 pivot 比較大小,不過 pivot 要小心的挑 。
















9.3 就是講如何小心的挑,
先五個五個做 insertion sort,再找中位數,這是一個經典的演算法。























沒有留言:

張貼留言