这个嵌套循环的时间复杂度是多少

Question

我一直在和几个人讨论这个嵌套for循环算法的时间复杂性：

for (i=1;i<=n;i*=2){
for (j=1;j<=i;j++) {
// some O(1) operation
}
}

现在我认为该算法的复杂度是O(NlogN)，原因是外环的复杂度为O(logN)，内环的复杂度则为O(N)。

然而，一些人已经使用一些涉及AP/GP的方法计算出该算法的复杂性为O(N)。

这个算法有多复杂？如果它实际上是O(N)，那么它背后的直觉是什么？

Answer 1

外循环有一个循环变量，它总是2的幂。外循环将进行1+⌊log₂⌋迭代。

每次外部循环的迭代，内部循环的主体执行的次数与的值一样多。因此，总的来说，内部主体的执行次数由以下总和表示：

2⁰+2¹+…+2^⌊log₂⌋

这是一个几何级数。这可以写成一个闭式公式：

(1−2^{1+⌊log₂⌋})/(1−2)

简化：

2·2^⌊log₂⌋−1

因为幂运算补偿了对数，这是的线性数量级

2·2^⌊log₂⌋−1=O(2−1)=O()

直觉

这里的一个关键是对数和幂相互吸收。

要了解它，请注意外循环的迭代次数是如何不变的，无论是16、17、18、19、20。。。或者甚至31。在所有这些情况下，外循环执行5次，内循环执行1+2+4+8+16＝31次。与16相比，加倍时，外部迭代次数仅增加一次。结果是，内体执行也大约加倍，然后。。。所以这两个"；事件"；真的携手并进。。。线性。

的不同值见下表

	体内执行次数
1	1
2	3
3	3
4	7
5	7
6	7
7	7
8	15
9	15
10	15
11	15
12	15
13	25
14	15
15	15