作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 105交大（heap)！
时间Tue Nov 26 10:10:19 2019
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://webptt.com/cn.aspx?n=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
1F：推 zuchang: 时间复杂度不表示实际时间0.1nlogn也在O nlogn里面 11/26 10:40
2F：→ Aa841018: 那请问a错在哪里？ 11/26 10:56
3F：推 zuchang: a不是对的吗 11/26 11:41
4F：→ zuchang: 话说 图可以大一点吗 看的眼睛有点痛QQ 11/26 11:42
5F：推 cry589036511: adjust 不是logn吗执行n次是nlogn 吧 11/26 11:46
6F：推 zuchang: 根据decision tree 有n!种leaf 树高/比较次数就是树高 11/26 11:46
7F：→ zuchang: 所以nlogn 11/26 11:46
8F：→ Aa841018: 下次我试试看拍大一点，我自己是用手机选电脑版在拉大， 11/26 12:24
9F：→ Aa841018: 清晰度还行！ 11/26 12:24