如何计算该三重循环的时间复杂度（Big O）？

先贴出修正笔误后的待分析代码（原代码存在语法问题，已调整）：

for (int i = 0; i < n*n; i++) {
  for (int j = 1; j < i; j *= 2) {
    for (int k = 0; k < j; k++) {
      System.out.println("x");
    }
  }
}

拆解分析步骤： #

1. 外层循环：i从0到n²-1，共执行n²次，但i=0时中间循环不会触发，有效循环量级为O(n²)。
2. 中间+内层循环：对每个i（i≥1），中间循环的j取值为1,2,4,...,2^k（直到2^k < i）。内层循环每次执行j次，因此单个i对应的内层总执行次数是等比数列求和：1+2+4+...+2^k。
   • 这个等比数列的和为2^(k+1)-1，由于2^k < i ≤ 2^(k+1)，可得2^(k+1) ≤ 2i，因此该和小于2i，即单个i对应的操作数量级为O(i)。
3. 总操作数求和：把所有i的操作数累加，就是计算从1到n²-1的整数和：

   Σ(i=1到n²-1) i = (n²-1)*n²/2
   

   这个结果的量级是O(n^4)。

你之前的思路偏差在于，错误地将中间循环次数固定为log(n)、内层循环固定为n，但实际上中间循环的次数随i变化，内层总次数是等比数列求和，最终累加后的总复杂度是O(n^4)，而非O(n³·log(n))。

内容的提问来源于stack exchange，提问作者impossibru