如何嵌套具有复杂度O（n）的循环？

Question

给出：

for (int i = 1; i <= n;  i *= 2) {
  for (int j = 0; j < i; j++) {
    // Statement(s) that take(s) constant time
  }
}

运行时间复杂度= O(n)

说明是：

我了解外环为log(n)，内环为O(n)。但是为什么时间复杂度不是O(n log n)？为什么是O(n + log n)？

Answer 1

部分和计算正确。但是，尽管结果确实为O(n)，但总执行时间的解释尚不清楚。通过执行内部语句会消耗实际时间，并且这些语句的执行次数由循环定义。部分和的方法已经考虑了两个循环（i = 1的1个时间单位，i = 2的2个时间单位，i = 4的4个时间单位，等等），总的来说，内部语句为如部分和计算所示，执行O(n)次。因此，总时间为O(n)*O(constant for the internal statements)=O(n)。我看不出有任何理由将O(logn)包括在此处的计算中。