如何找到下面提到的Big-O复杂度

Question

你们能否帮忙理解下面代码的时间复杂度 -

int count = 0;
for (int i = N; i > 0; i /= 2) {
    for (int j = 0; j < i; j++) {
        count += 1;
    }
}

我原先认为这应该是O(nlogn)，但是那是错误的。只是想更新一下我为什么认为它应该是O(nlogn)，因为在第一个循环中，我们将i除以2，也就是说我们把它减半了，那就是log n，在内部循环中，我们运行到i，所以是N，因此复杂度将是O(nlogn)。 提前感谢。

- QuickLearner

---

每个 for 循环都被认为具有 n 复杂度，因此如果一个循环嵌套在另一个循环中，则复杂度将为 n 平方。但在这种情况下，您需要检查通过循环的内容，并计算两个复杂度的总和。 - Óscar Contreras

观察不同值的 N 的 count 将会给你一些线索。（好吧，那就看这里：https://ideone.com/8GH8Me） - Andy Turner

对于这样的问题，我希望 Stack Overflow 能够支持 LaTeX。 - akuzminykh

@ÓscarContreras 这是不正确的。那么这个 for (int i = 1; i < n; i *= 2)，由于步长的原因实际上具有对数复杂度。或者像 for(foo(); bar(); baz())，这完全取决于方法。再比如 for (int i = 0; i < n; i++) { for (int j = i; j < i + 5; j++) {...}}，这不是二次的而是线性的。不要只是按照模式学习，你必须真正理解大O符号的工作原理并正确分析它。 - Zabuzard

@akuzminykh 你说得有道理。我认为这个问题之所以不是一个好问题，是因为OP没有解释为什么他认为它是“O(n log n)”，这将证明他已经尝试过了，然后人们可以集中精力澄清误解，而不是只是解释一切，甚至可能忽略了实际上让OP感到困惑的部分。但我想这不是这样的讨论的正确场所，应该去meta。 - Zabuzard

Answer 1

内层循环很容易 - 每次从0到j。因此，我们只需要理解每次迭代中j的值。
外层循环从N开始，并每次减半，这意味着第一轮是N，第二轮为N/2，第三轮为N/4，以此类推。

因此，我们有N + N/2 + N/4 + N/8 ... 这总共需要执行2N次操作。所以时间复杂度为o(N)。

- Nir Levy

---

嗨。当循环中有一个循环时，我们不应该将迭代乘起来而不是相加吗？ - Hemanth Annavarapu

@HemanthAnnavarapu - 如果我们正在谈论常量大小的迭代（即1->n和1->k），那么是的，N*K将是答案。但由于这里的每个迭代大小都不同，乘法将无效。 - Nir Levy

那么如果迭代不同，我们就不会将两个循环相乘？因此，第一个循环从N-> N/2-> N/4等等进行迭代，而内部循环从N、N/2等等进行迭代。我理解内部循环在添加时大约是2N，但第一个循环呢？ - QuickLearner

Answer 2

正如其他人所指出的那样，每当外部循环迭代时，内部循环执行一半的迭代，从 N 开始：

N + N/2 + N/4 + N/8 ...

这种情况将一直持续到有一个除数为0。然而，在上界复杂度方面，通常考虑无限的情况，也就是假设系列一直延伸下去……但我们可以找到一个收敛值。

在这个特定的情况中，我们发现，提取公因式后会得到：

N * (1 + 1/2 + 1/4 + 1/8 ...)

第一件事只是N，而第二个因素是一个等比数列，其项的形式为1/2^n。（公式和更多解释请见此处）

简单来说，第二个因素——无穷级数收敛于2。所以总体来看我们有2N，这在复杂度方面等同于N。

- ArrayIndexOutOfBounds

Answer 3

在这种情况下，复杂度为O(2N)，相当于O(N)。

为什么：

你有两个循环，外部循环每次得到 N 的一半（除了第一轮），内部循环从 0 到那一半的 N，表示在第一个内部循环中它会是[0, N)，然后是[0, N/2)，[0, N/4)，...

因此，总次数为N + N/2 + N/4 + ...等于N * (1 + 1/2 + 1/4 + 1/8 + ...)，由于1 + 1/2 + 1/4 + 1/8 +...当 N 趋近于无穷大时趋于2，原始表达式趋近于2N。

- Amir MB

Answer 4

第二个for循环将被执行N + N/2 + N/4 +....+ N/N

，第一个for循环决定第二个for循环将执行多少次。

当i = 0时，j循环直到N

，i = N/2时，j循环直到N/2

，依此类推

，N + N/2 + N/4 +....+ N/N的大O符号将是O(N)

- 0xh3xa

Answer 5

人们在处理这些任务时常犯的一个错误是将事情看作“直截了当”，但在许多场景中（比如这个）情况并非如此。

正确的方法是尝试“跟随”程序执行的计算步骤，以及每个步骤需要多长时间来确定时间复杂性（也包括内存复杂性）。

我建议写下前5个左右迭代的发生情况，并尝试找出其中的模式。

因此，在这种情况下，第一个循环将从N开始，一直到0，而索引每次减半。你说的对，它意味着O(log(N))，但让我们写下一些最初的迭代的索引：

i=N
i=N/2
i=N/4
i=N/8
i=N/16
...

现在，真正的事情发生在第二个for循环中，它在第一个循环内部。 首先，你可以看到第二个索引j与i有依赖关系，这应该立即引起我们的警惕，我们应该特别注意它。 第二个循环从0到当前迭代的i进行，增量为1。起初，你可能会说它是O(n)，因为变化是增加1，并且它从0到特定已知整数。但由于该整数是动态变化的，你不能真正地说出来，必须知道i将会是什么。 所以让我们写出上面每个迭代的内部循环的第一次迭代：

i=N       ->  |  j=0  |  j=1  |  j=2  | ... |  j=N    |
i=N/2     ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/2  |
i=N/4     ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/4  |
i=N/8     ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/8  |
i=N/16    ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/16 |
...

现在，我上面写的每个“盒子”（| |）都是程序执行的步骤。正如我之前所说，我们还需要知道每个步骤需要多长时间。在这种情况下，每个步骤（每次迭代）包括一次变量（count）增量操作，我们将其视为O(1)（常数）。

我们应该做的最后一件事是总结我们上面提到的所有步骤及其成本：

第一行将运行N次（0,1,2,..,N）- 每次步骤的成本为O(1)。-> 所以它将是N*1 = N 第二行将运行N/2次（0,1,2,..,N/2）- 每次步骤的成本为O(1)。-> 所以它将是(N/2)*1 = N/2 第三行将运行N/4次（0,1,2,..,N/4）- 每次步骤的成本为O(1)。-> 所以它将是(N/4)*1 = N/4 等等。

当我们总结起来时，程序的成本将是：N+(N/2)+(N/4)+(N/8)+...+~(N/N) = N * ( 1 + (1/2) + (1/4) + (1/8) +... ) ( 1 + (1/2) + (1/4) + (1/8) +... ) 是一个简单的已知数学级数。(您可以从一些网站或通过谷歌搜索来了解这些或更复杂的级数的结果)。 最多等于 2-(2/N)。

因此，最终成本将是：N * ( 2 - (2/N) ) = 2N - 2，总体上为 O(N)。

对于这个问题，这个答案相当长而且详细，但我试图展示一种“思考方式”，而不仅仅是解决问题。我希望它能帮助您（和其他人）在类似这样的问题上思考不同，尝试仔细检查每个循环和每个步骤，以及最重要的（并且经常被忽视）每个步骤的成本。

- SomoKRoceS

Answer 6

对于输入整数 n，内部语句将被执行以下次数。

n + n/2 + n/4 + … 1

因此，时间复杂度 T(n) 可以表示为

T(n) = O(n + n/2 + n/4 + … 1) = O(n)

您可以参考此链接：链接

- Anupam Haldkar