作者sdfg014025xx (随便就好)
看板Grad-ProbAsk
标题[理工] 105台大资工 资演
时间Sun Feb 10 00:24:04 2019
https://i.imgur.com/RgkWy1C.jpg
爬文後的答案好像是
a小题 O(log(n/m))
b小题 O(m)=n
两题都不是很懂，请问有人知道吗？
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 110.50.138.157
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549729447.A.4A3.html
1F：推 anonimo: b小题这个广为流传的答案应该是错的 我觉得是m=n^2 02/10 01:56
2F：→ anonimo: 详细可以看CLRS p.279 02/10 01:57
3F：推 plsmaop: 台大喜欢从clrs里直接出几题 02/10 07:55
4F：推 CorkiN: 第一题第一小题O(1*logn) 02/10 09:39
5F：→ CorkiN: 第一题第二小题O(1*1) 02/10 09:39
6F：推 CorkiN: 第一小题log里面是n/m，前面打错抱歉>< 02/10 09:46
8F：→ leviliang: (b)小题m=O(N)喔，蔡欣穆教授的投影片有证 02/10 21:32
9F：推 anonimo: 蔡欣穆投影片和这个讲的是不同东西吧 一个是在说 02/11 00:09
10F：→ anonimo: search是constant time 这题题目是在问两两碰撞次数的 02/11 00:10
11F：→ anonimo: 期望值 02/11 00:11
13F：推 leviliang: 阿 谢谢a大 a大的解答才是对的！ 02/11 07:28
14F：→ leviliang: 楼主可以把a大的解答框起来，以前的讨论全错了XD 02/11 07:30
15F：推 GeniusPuddin: 推上面的定理 02/14 16:12