作者sjdijojdj (Leo)
看板Grad-ProbAsk
标题[理工] big O()以及"can be"这种题目叙述
时间Tue Dec 10 13:05:48 2019
我举几题104台大电机丙的题目当例子
1.Given two linked list，its deletion operation can be O(logn)
我自己觉得这个应该是True，O(logn)应该可以包含O(1)
2.The height of a Binomial Heap of n nodes can be O(n)
我也觉得是True，理由同上
3.Given a fixed size array，the time complexity to remove the minimum
element can be O(1)
题目没有说它是不是sorted，如果是由大到小排好的话，直接砍掉最後一个就可以在
O(1)内完成了，所以他说can be我也觉得是对的
想问一下，我这样会太执着在can be这种字眼上吗?
还是题目原本就是要这样考的?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.115.200.12 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1575954350.A.B18.html
1F：→ DLHZ: 常数时间在O(n)内没问题 3.我也是同样的想法 12/10 13:47
2F：推 louis117228: 既然题目没讲，为什麽你们会假设array可能sorted？ 12/10 15:52
3F：→ louis117228: 所以我觉得3是错 12/10 15:52
4F：→ DLHZ: 我改变心意了XD 原本想法是 有可能刚好是sort 那直接删就好 12/10 17:32
5F：→ DLHZ: 但如果要这样 有个问题是并不知道输入的阵列是不是 变成要对 12/10 17:32
6F：→ DLHZ: 每个输入的阵列都做删掉最後一个这件事 但这样应该就错了 12/10 17:32
7F：推 mistel: 真心好奇有没有台大电机丙的同学有问过老师是希望看到什 12/10 19:35
8F：→ mistel: 麽回答 12/10 19:35