算法分析對比復發

Question

讓算法X: T(n) = 7T(n/2)+n^2, and Y: T’(n) = aT’(n/4)+n^2

我需要找到最大的價值a，使得算法Y是漸進的速度比算法X。

Answer 1

使用masters theorem： -

X : T(n) = O(n^log2(7)) 

So to get an asymptotically faster algorithm using masters theorem 

    2 <= log4(a) < log2(7) 

Finding max value such that the condition is true :- 

    log4(a) < log2(7)  
    log2(a)/log2(4) < log2(7) 
    log2(a)/2 < log2(7) 
    log2(a) < 2*log2(7) 
    a < 7^2 = a < 49 

As a is no of subproblems it needs to be integer therefore :- 

a = 48 is max value that a can take so that Y is asymptotically faster than X 

Answer 2

解決方案應該與此類似，但您應該考慮地板和小區。

對於算法X，我們有：

T(n)=7T(n/2)+n^2 
=> O(n)=n^2 + 7(n/2)^2 + 49(n/2)^3 + ... + 7^log(n)(n/2)^(log(n)+1) 
=> O(n)=n^2 . [7/(2^2) + 7^2/2^3 + ... + 7^log(n)/2^(log(n)+1)] 
=> O(n)=n^2 . \sum_{i=1 to log(n)}{1/2x(7/2)^i} <= geometrical series summation easy 

，並按照同爲Y直到你可以比較和查找的a值。