时间复杂度 O(n^2)

Question

void f(int n)\n{\n    for (int i = 1; i <= n; i++)\n        for (int j = 1; j <= n * n / i; j += i)\n            printf(\xe2\x80\x9c*\xe2\x80\x9d);\n}\n

\n

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

\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