这段代码的时间复杂度是多少：

Question

int c = 0;对于 (int i = 1; i < n; i += i) { for (int j = 0; j < i; j++) { c++; } }

我尝试通过考虑每个循环运行多少次来分析时间复杂度。我知道只要

i

小于

n

，外循环就会运行，并且

i

每次都会加倍。对于外循环的每次迭代，内循环从 0 运行到

i-1

。

我希望确定代码的总体时间复杂度。最初，我认为复杂度可能是

O(n log n)

，因为由于

log(n)

加倍，外循环运行

i

次，而内循环对于每个

i

运行

i

次。

我对如何计算外循环所有迭代中内循环的操作总数感到困惑。我知道它形成了一个几何级数，但我不确定这如何转化为整体时间复杂度。

有人可以帮助我理解正确的时间复杂度及其背后的原因吗？

Answer 1

在第一次迭代中，内部循环将运行 1 次，然后是 2 次，然后是 3 次，... n-1。 所以时间复杂度就是内循环执行的操作的总和，即 sum(1...n-1) = n(n-1)/2 = (n^2 -1)/2 = O (n^2)

Answer 2

根据我的说法，时间复杂度约为 O(n)，空间复杂度为 O(1) 因为： 外循环运行 log(n) 次，因为循环变量

i

在每次迭代中加倍，直到达到

n

。内循环在外循环的每次迭代中运行

i

次。因此，内循环的迭代总数为 n/2 + n/4 + n/8 + ... + 1，等于 n - 1。

由于内循环每次迭代都会将计数器

c

加 1，因此总操作次数为 n - 1，时间复杂度为 O(n)。

空间复杂度为 O(1)，因为程序使用的内存量不会随着输入大小而增加

n

。