作者sdfg014025xx (随便就好)
看板Grad-ProbAsk
标题[理工] 演算法 时间复杂度 多题
时间Wed Dec 5 12:03:30 2018
1.题目
https://i.imgur.com/rcRtOvI.jpg
https://i.imgur.com/l618qKe.jpg
请问为什麽解答画线的部分可以直接那样转变？
2.
https://i.imgur.com/6lQzokS.jpg
这边为什麽是变成8c，是单纯假设吗？
3.
https://i.imgur.com/e3JOmrQ.jpg
这边能设成<=cnlogn吗？
因为看前面类似的题目都是直接设，但这题多了个减常数倍的n是为什麽？
感谢各位
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.194.114.144
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1543982613.A.36D.html
1F：推 cossetannie: 前面有人问过了 标题跟你一样 去看看吧 12/05 12:11
2F：推 wei12f8158: 第一题因爲问的是时间复杂度，所以可以想成T(1,1)=T(n 12/05 14:02
3F：→ wei12f8158: ,n)，T(1,2)=T(n-1,n)...T(1,n-1)=T(2,n)，等号左右 12/05 14:02
4F：→ wei12f8158: 边的式子算起来一样复杂，所以可以化简成接下来的样子 12/05 14:02
5F：推 eatagary: 第三题 如果guess cnlogn 算到後面会发现，guess 错误 12/05 23:24
6F：→ eatagary: ，需用-dn,主要是 配合 substitution 方法不矛盾的经验 12/05 23:24
7F：→ eatagary: 假设法。 12/05 23:24
8F：推 skyHuan: 竟然连题目都一样XDD 12/06 00:03