time-complexity - 确定该程序的时间复杂度

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)）。

标签： time-complexity

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))。