作者Riddle5542 (小丘)
看板Grad-ProbAsk
标题[理工] [离散] 99 中央资工
时间Fri Dec 31 12:14:44 2010
http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_99_03.pdf
上面是题目连结
想请问各位高手大大 离散的第三四题该怎麽解...?
我不知道该如何下手 请给予我一些指教...谢谢 !!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.25.149.117
1F:推 skill91002:我觉得第三题是(a),因为subproblem为两个T(n/3),另外 12/31 13:04
2F:→ skill91002:附加一个for回圈复杂度为Θ(n)。 不过我不懂跟(d)有何 12/31 13:05
3F:→ skill91002:不同耶?!Θ(n)+Θ(1)不是可以看成是Θ(n)吗= = 12/31 13:07
4F:推 skill91002:样子,所以我觉得第四题答案是(d)。 12/31 13:16
5F:→ skill91002:令T(3)=1,由代入替换法可推得时间复杂度约为O(n^2)的 12/31 13:17
6F:→ skill91002:.........为何上两句推文顺序自己颠倒了XD 12/31 13:17
7F:→ xygod:用master theorem得Θ(n)耶,这样是不是该选(e) 01/09 19:20