[理工] [離散]-複雜度
Suppose we have 4 algorithms designed to solve the same problem if the running
time of the 4 algorithms are expressed by divide-and-conquar recurrence
relations as given below ,then which algorithm would be asymptotically the
best ?
a) f(n) = 10f(n/3) + 10n
b) f(n) = 5f(n/2) + 6n
c) f(n) = 9f(n/3) + 2n^2
d) f(n) = 20f(n/5) +5n^2
10
a為θ(n^log3 )
5
b為θ(n^log2 )
我算d應該最好吧，解答為b!?
c為θ(n^2*logn) 有人跟我看法一樣嗎...？
d為θ(n^2 )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.202.33
※ 編輯: gn00618777 來自: 122.124.202.33 (03/02 18:26)
→
03/02 18:31, , 1F
03/02 18:31, 1F
→
03/02 18:45, , 2F
03/02 18:45, 2F
推
03/02 19:57, , 3F
03/02 19:57, 3F
推
03/02 20:20, , 4F
03/02 20:20, 4F