2011年3月27日 星期日

[Introduction To Algorithms] 第六堂: Heapsort

開始上演算法的應用了,講的是 HeapSort,Heapsort有兩個用途

  • 排序
  • Priority Queues 的實作
前面屬於資料結構的部分,Heap 的定義、性質、如何 maintain heap (heapify)





接下來討論到 Heapify 的 Running time 
書上直覺地導出上下界。 老師也補充了用 recurrence 的算法。  p.7 注意不能用θ表示。








再來才是分析 worst case(演算法分析要精確)


接下來談到 heap 的建立,也分析了 running time  p.11 ~ p.15
再來就是分析 Heapsort algo....







這裡用到一個 lemma 推導出 n 的 nodes 時,heap 的高度,原理很簡單,自己可以推出來。











這裡老師花了蠻多時間講,列出幾個點

  1.  O(0) 的意義
  2. 用到之前 rule of sum 等 theorem
我下課問了一下老師,為何可以 remove floor and ceiling = =" 這之前才學過 smooth fun 可以去 floor and ceiling !!



這段老師也強調了一下,畫線的那一段書上沒有說明,老師主要補充, lgn+1到 ∞ 那一段不是"master"。










heap build 分析完後,Heapsort 分析就很簡單了。 p.15~p.17


Priority Queue 不管是 max 還是 min 本質上都一樣。
接下來要分析 Priority Queue 運算的時間。
p.18~p.19
















注意 Heap-Increase-Key 這個運算,他其實只要θ(i) 就可以了但是對於整體而言,我們只關心 input size 是 n 時,複雜度是多少,因此θ(n)比較符合需求。












掰!!

沒有留言:

張貼留言