嵌套循环的时间复杂度分析（int j = 0; j < i; j++）：大 O 表示法

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(log N * something)，其中 O(log N) 是外层循环的时间复杂度，something 是内层循环的时间复杂度？

那么怎么才能得到 O(N) 的时间复杂度呢？

- csguy

---

你可能想看一下1/（2n）的总和，因为那就是你所做的。 - Progman

@Progman 嗯，所以内部循环是 O(n)，外部循环是 O(log N)？ - csguy

是的和不是的。内部循环是O(i)，但i从外部改变。与外部循环结合起来，内部循环看起来像O(N / log N)。将其乘以外部的O(log N)，你会得到O(N)，与给定答案相同。 - Progman

@Progman，您能详细解释一下 i = n / log n 的原理吗？ - csguy

这是内循环步骤的平均值，基于外部循环和n。第一次迭代是n步，最后一次迭代是1步。通过https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_⋯ 的帮助，您可以得到O(n / log n)。 - Progman

Answer 1

外层循环的复杂度为O(log n)，因为有i /= 2。但内层循环有些棘手。
内层循环的复杂度为O(i)，但是i每次迭代外层循环时都会发生变化。与外层循环结合使用，得到复杂度为O(n / log n)。这个结果可以如下得出：
内层循环所执行的步骤数类似于https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_⋯中描述的1/(2n)之和。一开始你要做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)。

- Progman

---

谢谢。我唯一困惑的部分是为什么我们需要找到平均值？在外部循环的每次迭代中（其运行时间为O(log N)），内部循环将以O(i)运行，其中i = 2n。那么为什么我们需要找到内部循环的平均大O值呢？ - csguy

@csguy i 不是 2n。相反，它取决于外部循环的实际迭代次数。在开始时，它是 n，在结束时，它是 1。因此，平均而言，它是 2n / log n，即 O(n / log n)。如果是 i=2n，那么你可以说它是 O(n)（但它不是），这将导致 O(n * log n)（但它不是）。 - Progman

无论迭代次数是否取决于外层循环，你是否会计算平均值？有时间的话，可以看一下这个链接：https://stackoverflow.com/questions/59872524/big-o-of-nested-loop-int-j-0-j-i-i-j - csguy