[理工] [資結] heap的時間複雜度

[juan19283746 (小阮)]

In the worst case,initializing a min heap with n element takes Θ(___) time.

In the average case,initializing a min heap with n element takes Θ(___) time.


insert的時間複雜度是O(logn)

所以是 nlogn嗎??


題目是是非題(Θ(logn))  答案都給F

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.40.91.158
→ mqazz1:不太懂initializing是什麼意思@@
→ juan19283746:我覺得應該是如果一開始有一堆數  然後用這些數字建
→ juan19283746:heap吧  應該吧@@?
推 mqazz1:如果是建heap的話 那這兩題應該都是nlogn
→ tureday:http://ppt.cc/euYa  它上面寫O（n）耶..
→ tureday:還是我搞錯意思了？
→ tureday:好像有top-down（nlogn）和bottom-up（n）兩種方法
推 mqazz1:不好意思XD 那應該是我搞錯了..感謝大大提供的資料
推 tureday:應該是這題只是要判斷是否可能O(logn)，兩種方法都不會是
→ tureday:O(logn)，所以沒講哪方法，其實j大和m大答案應該是正確的.
→ juan19283746:謝謝啦  再來研究TOP-DOWN和BOTTOM-UP 的差別
→ sneak: 如果是建heap的話  https://daxiv.com