[理工] min heap 問題

看板Grad-ProbAsk作者 (DaiJouBu)時間13年前 (2012/08/07 21:46), 編輯推噓0(0推 0噓 6→)
留言6則, 3人參與, 最新討論串1/1
(B) in the worst case, initializing a min heap with n elements takes Θ(logN)time (C) in the average case, initializing a min heap with n elements takes Θ(logN)time 這兩個是錯的。有人可以說一下，錯在哪嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.118.254.246
→
08/07 21:47, , 1F
buttom up O(n)
08/07 21:47, 1F
→
08/07 21:56, , 2F
可詳細一點嗎？
08/07 21:56, 2F
→
08/07 22:12, , 3F
建heap絕對不可能只花lgn 不然就太神了XD
08/07 22:12, 3F
→
08/07 23:00, , 4F
先建complete binary tree 然後,由最後一個parent
08/07 23:00, 4F
→
08/07 23:00, , 5F
往上調整,所以 O(n)
08/07 23:00, 5F
→
08/07 23:09, , 6F
知道了。謝謝
08/07 23:09, 6F
‣ 更多 VB2005 的文章
文章代碼(AID): #1G8Hmpld (Grad-ProbAsk)