作者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