小编Far*_*heh的帖子

此代码段假设具有复杂性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).