如何计算存在依赖变量的嵌套循环的总操作次数？

原代码块 #

for(int i = 1; i <= n; i *= 2) {
   for(int j = 1; j <= i; j *= 2) {
       // 统计此处的操作次数
   }
}

推导过程 #

你的初始推导方向是正确的，仅需做两处细节修正：外层循环实际运行次数为floor(log₂n)+1，单轮内层循环的运行次数为floor(log₂i)+1，后续推导如下：

• 外层循环的i取值序列为：2^0, 2^1, 2^2,..., 2^k，其中2^k ≤ n < 2^{k+1}，可得 k = floor(log₂n)，外层循环总运行次数为 k+1 次。
• 对于每个取值为2^m的i（m取值范围为0 ≤ m ≤ k），内层循环的j取值序列为2^0, 2^1,..., 2^m，单轮内层循环运行次数为 m+1 次。
• 总操作次数为所有轮次内层循环次数的求和：

  总次数 = Σ（从m=0到m=k）(m+1) = 1 + 2 + 3 +... + (k+1)
  

  等差序列求和可得：

  总次数 = (k+1)*(k+2)/2
  

• 将k = floor(log₂n)代入，得到仅用n表示的精确表达式：
  总操作次数 = ( floor(log₂n) + 1 ) * ( floor(log₂n) + 2 ) / 2
• 渐近时间复杂度为 O( (log₂n)² )，也可简写为 O(log²n)。

示例验证 #

以n=4为例：

• k = floor(log₂4) = 2，代入公式得总次数为(2+1)*(2+2)/2 = 6
• 实际运行统计：i=1时内层1次，i=2时内层2次，i=4时内层3次，总和为6，和公式计算结果一致。

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