[理工] 复杂度计算一题

楼主: TMDTMD2487 (ㄚ冰)   2017-11-27 13:48:23
https://i.imgur.com/jkauD5Z.jpg
还请各位帮我看看我这样写行不行,尤其是算下限的时候结果是 C≦2
就虽然只要存在应该就没问题了,但这种方法很少用也不确定有没有错XD
考试这种题目如果要写算式,可以忽略floor跟cell吗,还是一定要这样算才行
作者: ken52011219 (呱)   2017-11-27 14:54:00
作者: nat99up (NAt)   2017-11-27 15:08:00
觉得可以 但改的人应该会7pupu
作者: ken52011219 (呱)   2017-11-27 15:10:00
我发现我最后写错了 是OMEGA然后上面 写可分成那边我不该直接写BIG OH 和 OMEGA
作者: Xunion (Xun)   2017-11-27 16:36:00
为什么不直接用master
作者: ken52011219 (呱)   2017-11-27 16:38:00
是指T(n/2) 应该是 T(n/2-1)吗?还是指上面 =>Omega(n/2) = floor(n/2) 那边
作者: djmez   2017-11-27 16:53:00
计算题你要用master之前要先证明master吧 要不然会扣分
作者: ken52011219 (呱)   2017-11-27 17:00:00
作者: djmez   2017-11-27 17:44:00
https://atekihcan.github.io/CLRS/E04.03-03/想起来CLRS有类似题目 floor不能省略但是可以像你一样替代掉https://ita.skanev.com/04/03/03.html 用官方一点的好了
作者: alan23273850   2017-11-27 18:26:00
我考台大资工106的时候看到这种题目说show或justify就通通画递回树搭配算式展开,预估有拿到全部分数临场考试的时候实在很难考虑这么细节的东西

Links booklink

Contact Us: admin [ a t ] ucptt.com