- 排序
- 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 的高度,原理很簡單,自己可以推出來。
這裡老師花了蠻多時間講,列出幾個點
- O(0) 的意義
- 用到之前 rule of sum 等 theorem
我下課問了一下老師,為何可以 remove floor and ceiling = =" 這之前才學過 smooth fun 可以去 floor and ceiling !!
沒有留言:
張貼留言