c - O(n^2) 的时间复杂度

Question

void f(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n * n / i; j += i)
            printf(“*”);
}

这段代码的时间复杂度是多少？ 我认为它会是 O(n³) 但结果实际答案是 O(n²)我不知道为什么。 有人可以解释吗？ (有可能是考试出错)

Answer 1

关于内循环有两点需要注意:

1. 这里的“除以 i”:j<=n*n/i

2. 此处的“增量为 i”:j+=i (这给出了另一个“除以 i )

考虑到这一点，我们可以看到内部循环执行多少次取决于 i 的值。 :

i = 1 --> n*n/1/1

i = 2 --> n*n/2/2

i = 3 --> n*n/3/3

i = 4 --> n*n/4/4

....

然后求和:

n*n/1/1 + n*n/2/2 + n*n/3/3 + n*n/4/4 + ...

这是:

n*n/1^2 + n*n/2^2 + n*n/3^2 + n*n/4^2 + ...

这是:

n^2 * (1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + ... )

根据https://en.wikipedia.org/wiki/Basel_problem这是大约:

n^2 * 1.644934

所以复杂度是O(n^2)

只是为了好玩，下面的代码计算了内部循环的执行次数

#include <stdio.h>

unsigned long long  f(int n)
{
    unsigned long long c = 0;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n*n/i; j+=i)
        {
            ++c;
        }
    }
    return c;
}

void g(int n)
{
    unsigned long long c = f(n);
    printf("d=%-10d c=%-10llu c/n^2=%f\n", n, c, (((double)c)/n/n));
}

int main()
{
    g(10);
    g(100);
    g(1000);
    g(10000);
    return 0;
}

输出:

d=10         c=157        c/n^2=1.570000
d=100        c=16395      c/n^2=1.639500
d=1000       c=1644474    c/n^2=1.644474
d=10000      c=164488783  c/n^2=1.644888