loops - 双循环函数的时间复合体

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)

你可以想象这是一个边的正方形roof(log(n))或log(n) + 1如果n是一个精确的对数，即未完全“填充”。这个正方形内的元素数量几乎是面积的一半:

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

所以这将是你的程序的渐近复杂性。