这个求和算法的复杂性是多少？

Question

#include <stdio.h>

int main() {
    int N = 8;  /* for example */
    int sum = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= i*i; j++)
            sum++;

    printf("Sum = %d\n", sum);
    return 0;
}

对于每个n值(i变量),j值将为n ^ 2.所以复杂性将是n.n ^ 2 = n ^ 3.那是对的吗？

如果问题变成:

#include <stdio.h>

int main() {
    int N = 8;  /* for example */
    int sum = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= i*i; j++)
            for (int k = 1; k <= j*j; k++)
                sum++;

    printf("Sum = %d\n", sum);
    return 0;
}

然后你使用现有的n ^ 3.n ^ 2 = n ^ 5？那是对的吗？

Answer 1

根据我的统计，我们有i和。j < i*ik < j*jx^1 * x^2 * (x^2)^2 = x^3 * x^4 = x^7

特别是，因为1 < i < N我们的循环有 O(N) i。因为1 < j <= i^2 <= N^2第二个循环的复杂度为 O(n^2)。扩展逻辑，我们有1 < k <= j^2 <= (i^2)^2 <= N^4第三个循环。

N^4从内循环到外循环，我们为每个循环执行 up to次j，N^2为每个i循环执行 up to 次，并在循环N上执行 up to 次i，使得总数为 order N^4 * N^2 * N = N^7= O(N^7)。