嵌套 for 循环的大 o 表示法

Question

如何找到以下代码的嵌套 for 循环的大 o 表示法？

int sum = 0;
for(int i = 1; i < N; i *= 2)
   for(int j =0; j <i; j++)
     sum++;

我相信外循环是log(n)，内循环是N，答案不就是n*log(n)吗？如果我的回答是正确的，我们可以假设 j

Answer 1

如果内循环运行从零到 N，你的答案就是正确的。但是，它从零运行到 i，这又以连续的 2 次幂运行。

因此，内部块 sum++ 执行的次数可以计算为

形式的总和

1+2+4+8+16+...

有 log₂N 项。

这是一个几何级数。计算 sum of its first log₂N terms 给出的正确答案是 O(N).

Answer 2

即使你无法从数学上找到答案，经验证据又如何呢？

for (int N = 1; N > 0; N <<= 1) {
    int sum = 0;
    for (int i = 1; i < N; i *= 2)
        for (int j = 0; j < i; j++)
            sum++;
    System.out.println(N + ": " + sum);
}

输出

1: 0
2: 1
4: 3
8: 7
16: 15
32: 31
64: 63
128: 127
256: 255
512: 511
1024: 1023
2048: 2047
4096: 4095
8192: 8191
16384: 16383
32768: 32767
65536: 65535
131072: 131071
262144: 262143
524288: 524287
1048576: 1048575
2097152: 2097151
4194304: 4194303
8388608: 8388607
16777216: 16777215
33554432: 33554431
67108864: 67108863
134217728: 134217727
268435456: 268435455
536870912: 536870911
1073741824: 1073741823

当你加倍N时，你加倍执行sum++的次数，所以答案是：O(N)

嵌套 for 循环的大 o 表示法

big o notation for nested for loop

java

big-o