[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,再找中位數,這是一個經典的演算法。
沒有留言:
張貼留言