代码的 Big-O 复杂度是多少？

Question

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
            j=j*2;
      }
}

我无法概括它。

Answer 1

如果我们计算程序执行的乘法次数，复杂度将为 n * log2(n)

您执行 n 次内循环（i 随 n 缩放），并且内循环重复 j <= n。 j呈指数增长

1, 3, 7, 15, 31, 63, 127, ... = (2^n) - 1

这是2^n缩放，所以n的值加倍使得内部循环再次迭代。

log2(n * 2) = log2(n) + 1

What is the Big-O complexity of the code?