作者blueskier (blue)
看板Grad-ProbAsk
标题[理工] 103中央 离散 时间复杂度
时间Thu Jan 24 13:16:09 2019
https://imgur.com/a/ISxzT9A
答案是给 C E
但我自己算是这样 不知道错在哪边@@
假设Procedure P 是 T(n)
call Q => θ(n)
loop 和 insert => θ(n*2/5*n) => θ(n^2)
call P(array2) =>T(n/5)
call P(array3) =>T(n/5)
T(n) = 2T(n/5) + θ(n^2)+θ(n)
最後算出来是O(n^(log5 2))
还请大大指点
还有请问算时间复杂度的时候 有没有什麽技巧之类的
可以算快一点(?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.225.118.127
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548306971.A.B29.html
1F：推 meokay: 这题应该是A 01/24 13:54
2F：推 meokay: n的log5^2 比 n 小 ，fn=theta n 01/24 13:59
3F：推 sdfg014025xx: 这题是A 01/24 18:11
4F：推 yp195126: 答案A+1 01/24 18:13
5F：→ blueskier: 了解 感谢各位Q 01/24 20:03