[理工] 105交大（heap)！

[Aa841018 (andrew)]

https://i.imgur.com/ISOhRay.jpg
確認一下48（a)觀念是否有誤：
根據comparison base，至少nlogn次比較應該沒錯
然後每次進行：swap、adjust兩個operation總共做n次=2n
又因為heap是complete BT，所以不太可能有skew的狀況
因此應該不可能到nlogn次operation
因此a錯
只是…如果將at most用big o來想，好像又是對的，因為這樣就變成nlogn是一個
upper bound但不一定要達到，那敘述上好像就沒問題…
請問各位怎麼看這個選項？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.100.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1574734221.A.D16.html
※ 編輯: Aa841018 (27.247.100.172 臺灣), 11/26/2019 10:12:14
※ 編輯: Aa841018 (27.247.100.172 臺灣), 11/26/2019 10:12:47
※ 編輯: Aa841018 (27.247.100.172 臺灣), 11/26/2019 10:13:34
推 zuchang: 時間複雜度不表示實際時間0.1nlogn也在O nlogn裡面
→ Aa841018: 那請問a錯在哪裡？
推 zuchang: a不是對的嗎
→ zuchang: 話說 圖可以大一點嗎 看的眼睛有點痛QQ
推 cry589036511: adjust 不是logn嗎執行n次是nlogn 吧
推 zuchang: 根據decision tree 有n!種leaf 樹高/比較次數就是樹高
→ zuchang:  所以nlogn
→ Aa841018: 下次我試試看拍大一點，我自己是用手機選電腦版在拉大，
→ Aa841018: 清晰度還行！