c - 这个双循环的复杂性是什么

Question

#include <stdio.h>

int main() {
    int N = 32; /* for example */

    int sum = 0;
    for (int i = 1; i <= N*N; i = i*3)
        for (int j = 1; j <= i; j++)
            sum++;

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

外循环是奇数。

如果检查仅使用 N(而不是 N*N)，那么我每次乘以 3 递增是否意味着外循环需要 N 的 n/3 次迭代？

但是检查是用 N* N 或 N^2 所以这意味着将增长

N^2  / 3 ??? (n squared divided by 3) Is that correct?

如果我尝试使用不同的 N 值，比如每次加倍，则 i 循环(独立)不会增长太多。像对数增长)。我将如何用数学方式表达这一点？

那你怎么看内循环呢？如果它每次都增加到 i，我该如何用数学表达呢？我如何将内循环与 N 联系起来？

我希望 a) 能够用 N 在数学上表达“复杂性”。然后下一步，b) 是使用大 O 表示法。

对此感到困惑。任何帮助将不胜感激。

Answer 1

我认为外部循环执行了 log3(N*N) 次，因为每次你乘以 3 所以你有 1, 3, 9... 它需要以 3 为底的对数N*N 次执行达到 N*N。

内部循环最多执行 N*N 次，所以一切都变成了 log3(N*N)*N*N。