我有一个T(n) = 3T(n/5) + T(n/2) + 2^n的复发,我想找出t(n)的上下界。
但是,我不能用主方法来解决这个问题我刚学会了复现,看来解决这个问题太难了。你能帮我做这个吗?如果我不能使用大师的方法,我该怎么解决呢?

最佳答案

you cant solve this relation with akra-bazzi method because 2^n is not polynomial .
But for solving with finding bounds :

it's obvious that:

1)  T(n) >= 2^n (cause we can see in the relation we have 2^n and other things :)) )
and we know that the :

2) T(n) <= 4T(n/2) + 2^n . and we can solve this with master method and the answer of 4t(n/2) + 2^n is θ(2^n) .

1+2) now we have this : θ(2^n) <= T(n) <= 2^n .

so we have the answer :
T(n) ∈  θ(2^n).

关于algorithm - 推导T(n)= 3T(n/5)+ T(n/2)+ 2 ^ n的上下界,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/54796863/

10-10 06:45