增长顺序 - 嵌套循环，具有加倍索引的外部循环

Question

请考虑以下代码片段：

int sum=0;
for (int i = 1; i < n; i *= 2)
{
for (int j = 0; j < i; j++)
{
sum++;
}
}

这个的增长顺序是 (n*log(n(/2(？(基数 2 日志(？

Answer 1

它是O(n(。

实际上，内部循环(以j作为迭代器的循环(从0循环到i。因此，总的来说，它每次都会循环i。

外循环每次加倍j，直到达到n。因此，这意味着我们将按如下方式处理内部循环：

1 + 2 + 4 + … + n

这是一个几何级数[wiki]，因此等于：

∑j=0⌊log n⌋2j= (1-2⌊log n⌋+1)/(1-2) = 2⌊log n⌋+1-1 ≤ 2n-1

因此，sum++指令的总数为2n，因此为O(n(。