为什么这个片段是O(n)？

Question

此代码段假设具有复杂性O(n).但是,我不明白为什么.

sum = 0;
for (k = 1; k <= n; k *= 2)  // For some arbitrary n
  for (j = 1; j <= k; j++)
    sum++;

现在,我理解外部循环本身就是O(log n),所以为什么添加内部循环才能实现O(n).

Answer 1

我们假设n暂时为2的幂.

内循环的最后一次迭代将运行n次.之前的迭代将运行n/2次,倒数第二次迭代n/4次,依此类推,直到第一次迭代将运行一次.这形成了一个 总共2 n - 1次迭代的系列.这是O(n).

(例如,当n  = 16时,内部循环总共运行1 + 2 + 4 + 8 + 16 = 31次.)