算法算法的時間複雜度

Question

如何計算函數f的時間複雜度？

void f(int n) 
{ 
    if (n <= 1) 
     return; 
    g(n, n/3); 
} 

void g(int n, int m) 
{ 
    int i = 1; 
    while (m < n) { 
     m += i; 
     i++; 
    } 
    f(n/2); 
} 

答案是開方（N），但我不知道怎樣......

感謝

Answer 1

首先，請注意，該程序現在可以轉換成一個單一的功能程序通過內聯g(n,m)在f()：

void f(int n) 
{ 
    if (n <= 1) 
     return; 
    m = n/3; 
    while (m < n) { 
     m += i; 
     i++; 
    } 
    f(n/2); 
} 

內環在O(sqrt(n))迭代運行，因爲它是從n/3開始，與n結束，增加了1,2,3，...因此，如果我們總結一下我們得到：

n/3 + (1 + 2 + ... + i) >= n 

我們需要解決上述方程找到i終值，我們得到：

1 + 2 + ... + i >= 2n/3 

從算術級數的總和：

i(i+1)/2 >= 2n/3 

從上面的不等式，we can conclude確實i是O(sqrt(n))。

因此，我們可以表示複雜性：

T(n) = T(n/2)    +   O(sqrt(n)) 
     ^       ^
    recursive step     syntatic sugar for some function 
            which is in O(sqrt(n)). 

現在，我們可以看到：

T(n) = T(n/2) + sqrt(n) = T(n/4) + sqrt(n/2) + sqrt(n) = ... = 
    = sqrt(1) + ... + sqrt(n/2) + sqrt(n) 

And the above sum is in O(sqrt(n))

Answer 2

令F _ň是f(n)的時間複雜度和G _n，m的時間複雜度爲g(n,m)。

ģ _N，M = SQRT（納米）+ F _n/2個

˚F_Ñ = G _N，N-/3 = SQRT（NN/3）+ F _Ñ/2 = C sqrt（n）+ F _n/2

所以答案是sqrt（n）。