双循环函数的时间复杂度

Question

我遇到了这个问题：

Func(n)
  for (a = 1; a <= n; a = a * 2)
    for (b = a; b <= n; b = b * 2)
      print a + b

我知道外部循环将运行 loglog(n)，但我很难理解内部循环将运行的大小。还有这个函数的时间复杂度的最终答案是什么。谢谢大家

Answer 1

也许列出几个输出可能会有所帮助。这里我举个例子 n=10.

a=1: (1+1) (1+2) (1+4) (1+8)
a=2: (2+2) (2+4) (2+8)
a=4: (4+4) (4+8)
a=8: (8+8)

如果 n 是一个精确的对数，您可以想象这是一个边缘为 roof(log(n)) 或 log(n) + 1 的正方形，即没有完全“填充”。这个方格内的物品数量几乎是面积的一半：

1/2 * log_2(n) * (log_2(n) + 1)

所以这将是您程序的渐近复杂度。

Time Complex of double loop function