big-o - 嵌套循环的大O (int j = 0; j < i; j++)

Question

for (int i = n; i > 0; i /= 2) {
   for (int j = 0; j < i; j++) {
     //statement
   }
}
Answer: O(N)

我知道 for (int i = n; i > 0; i /= 2) 的第一个循环结果 O(log N) .

第二个循环for (int j = 0; j < i; j++)取决于 i并将首先迭代 i次i / 2 , i / 4 , ... 次。 (其中 i 取决于 n )

我不知道第二个循环的大 O，但我认为答案是 O(log N * something)其中 O(log N)是外循环，something是内循环？

如何获得O(N) ？

Answer 1

外层循环的复杂度为 O(log n)，因为 i/= 2。但是内部循环有点棘手。

内层循环的复杂度为 O(i)，但 i 会随着外层循环的每次迭代而变化。结合外部循环，您会得到 O(n/log n) 的复杂度。你得到这个如下:

内部循环执行的步数类似于 1/(2n) 的总和，如 https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_⋯ 中所述.一开始你在做 n 步骤，然后只做 n/2 步骤，然后 n/4 步骤等等，直到你只做 2 步，最后是 1 步。这加起来就是 2n 的结果。总共运行内部循环 log n 次(由外部循环定义)。这意味着内部循环运行 平均 2n/log n 次。所以你的复杂度为 O(n/log n)。

通过 O(log n) 的外循环和 O(n/log n) 的内循环，你得到 O(log n * n/log n)，可以简化为O(n)。