[理工] 105交大（heap)！
確認一下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
推
11/26 10:40,
6年前
, 1F
11/26 10:40, 1F
→
11/26 10:56,
6年前
, 2F
11/26 10:56, 2F
推
11/26 11:41,
6年前
, 3F
11/26 11:41, 3F
→
11/26 11:42,
6年前
, 4F
11/26 11:42, 4F
推
11/26 11:46,
6年前
, 5F
11/26 11:46, 5F
推
11/26 11:46,
6年前
, 6F
11/26 11:46, 6F
→
11/26 11:46,
6年前
, 7F
11/26 11:46, 7F
→
11/26 12:24,
6年前
, 8F
11/26 12:24, 8F
→
11/26 12:24,
6年前
, 9F
11/26 12:24, 9F