作者cansister (cansister)
看板Grad-ProbAsk
標題[理工] [資結] 時間複雜度
時間Tue Dec 29 17:21:08 2009
請問建立(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
1F：→ tedmax100:我只知道 三種的插入 都是O(logN) 都是樹的高度@@ 12/29 17:29
2F：推 yesa315:Heap應該是O(nlogn)採Top-down建立的話 我覺得deap/M-m 12/29 19:17
3F：→ yesa315:heap複雜度都跟max heap一樣 12/29 19:18
4F：→ yesa315:Top-down建立的話是worst case 12/29 19:18
5F：→ ssccg:考卷問你heap建立的話，一定是指O(n)那種建法 12/29 23:11
6F：→ ssccg:把n次insert那個忘了吧，至於另兩者就是n次insert 12/29 23:13
7F：→ cansister:所以另外兩者就是n次insert，都是O(nlogn)的意思嗎？ 12/30 00:44