[理工] [資結]-時間複雜度

看板Grad-ProbAsk作者 (cansister)時間16年前 (2009/12/29 17:21), 編輯推噓1(1推 0噓 6→)
留言7則, 4人參與, 最新討論串26/38 (看更多)
請問建立(1)max heap (2)deap (3)min-max heap三種資料結構的 a.best b.average c.worst的時間複雜度 目前是我認為的答案，有高手知道可以講解一下嗎？ 1. max heap 2.deap 3.min-max heap a.O(n) a.O(n) a.O(n) b.O(n) b.O() b.O() c.O(n) c.O() c.O() 因為沒有答案又問不到人，謝謝指教 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.134.129.184
→
12/29 17:29, , 1F
我只知道 三種的插入 都是O(logN) 都是樹的高度@@
12/29 17:29, 1F
推
12/29 19:17, , 2F
Heap應該是O(nlogn)採Top-down建立的話 我覺得deap/M-m
12/29 19:17, 2F
→
12/29 19:18, , 3F
heap複雜度都跟max heap一樣
12/29 19:18, 3F
→
12/29 19:18, , 4F
Top-down建立的話是worst case
12/29 19:18, 4F
→
12/29 23:11, , 5F
考卷問你heap建立的話，一定是指O(n)那種建法
12/29 23:11, 5F
→
12/29 23:13, , 6F
把n次insert那個忘了吧，至於另兩者就是n次insert
12/29 23:13, 6F
→
12/30 00:44, , 7F
所以另外兩者就是n次insert，都是O(nlogn)的意思嗎？
12/30 00:44, 7F
‣ 更多 cansister 的文章
文章代碼(AID): #1BESe6gr (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 26 之 38 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共38篇)
‣ 更多 cansister 的文章
文章代碼(AID): #1BESe6gr (Grad-ProbAsk)