[理工] 105台大资工资演 sdfg014025xx PTT批踢踢实业坊

楼主: sdfg014025xx (随便就好) 2019-02-10 00:24:04

https://i.imgur.com/RgkWy1C.jpg
爬文后的答案好像是
a小题 O(log(n/m))
b小题 O(m)=n
两题都不是很懂，请问有人知道吗？
感谢

作者: anonimo (unknown) 2019-02-10 01:56:00

b小题这个广为流传的答案应该是错的我觉得是m=n^2详细可以看CLRS p.279

作者: plsmaop (plsmaop) 2019-02-10 07:55:00

台大喜欢从clrs里直接出几题

作者: CorkiN (柯基) 2019-02-10 09:39:00

第一题第一小题O(1*logn)第一题第二小题O(1*1)第一小题log里面是n/m，前面打错抱歉><

作者: leviliang (levi) 2019-02-10 21:28:00

https://i.imgur.com/CZxUww2.jpg(b)小题m=O(N)喔，蔡欣穆教授的投影片有证

作者: anonimo (unknown) 2019-02-11 00:09:00

蔡欣穆投影片和这个讲的是不同东西吧一个是在说search是constant time 这题题目是在问两两碰撞次数的期望值https://imgur.com/oAsVsTS

作者: leviliang (levi) 2019-02-11 07:28:00

阿谢谢a大 a大的解答才是对的！楼主可以把a大的解答框起来，以前的讨论全错了XD

作者: GeniusPuddin (GeniusPudding) 2019-02-14 16:12:00

推上面的定理

继续阅读