计算算法的时间复杂度

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);
} 

答案是 sqrt(n)，但我不知道如何...

谢谢

Answer 1

首先，请注意，通过在 f():

中内联 g(n,m)，程序现在可以转换为单个函数程序

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_n为f(n)的时间复杂度，G_n,m为[=的时间复杂度11=].

G_n,m = sqrt(n-m) + F_{n / 2}

F_n = G_n,n/3 = sqrt(n-n/3) + F_{n / 2} = C sqrt(n) + F_n/2

所以答案是 sqrt(n)。