确定这个程序的时间复杂度

Question

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

我尝试了很多计算时间复杂度，但都错了，如果有人能帮助我了解如何处理这些程序，我将不胜感激。 （答案是O(sqrt(n)）。

Answer 1

下面的解释可以简化，但我尽量谨慎。

等差数列和

首先让我们谈谈以下循环的复杂性（注意m=0）：

int m=0;
int i=1;
while (m < n) {
    m += i;
    i++;
}

循环的不变式是：在 i 次迭代后 m == 1+2+...+i == (1+i)*i/2。所以当满足以下条件时循环停止：

相当于

左右大O相等，都等于O(i)，所以O(i)=O(sqrt(n))就是循环的复杂度

g2 内循环的复杂度

g2 中的循环等同于以下循环：

int n_modified = n - m;
m = 0;
int i=1;
while (m < n_modified) {
    m += i;
    i++;
}

正如我们在上一节中所展示的，O(sqrt(n-m)) 的复杂性。

f2 的复杂度

现在让我们得到 f2 函数复杂度的总体公式。它的复杂度与 g2(n, n/3) 调用的复杂度基本相同。它由两部分组成：g2 循环的复杂性和递归的复杂性。即公式为

这个可以化简估计（等比级数的因式和求和）：

这给了我们最终的答案：f2 的复杂度是 O(sqrt(n)).