Big O，算法分析

Question

我想知道以下每个语句的大 O 表示法是什么：

Sum = 0;
 for i=1 to N^2 do:
   for j=1 to N do:
    'Sum += 1;

当Sum = 0时，它肯定是O(1)，因为它只会被执行一次。但是第二个语句让我感到困惑，它应该是O(N)吗？因为这是第一个循环？还是应该是O(N^2)，因为N^2是关于变量N的二次函数？

- Qianyi Wu

---

不是“for”指令的数量重要，而是程序完成所需的循环次数。这看起来非常像O(n^3)。 - ppeterka

通常认为增量（或任何加法）是O(1)。 事实并非如此。它实际上是O（变量大小）或O（对数值）。然而，对变量进行O(n)次增量仅需要O(n)时间，请参见二进制计数器的平摊分析。 - harold

@harold 尽量不要偏离原问题，但为了OP的利益，我认为需要澄清一下。当您进行复杂性分析时，通常会隐含地定义某些操作所需的时间。在这种情况下，添加到伪变量（它还有一个伪类型！）可能被假定为 O(1)。如果他们正在分析加法算法，则情况并非如此。我相信CLRS算法分析介绍了这些假设。另一种表达方式是，您确定硬件级别的位翻转是 O(1) 吗？在哪些电路上？ - rliu

Answer 1

第一个循环的时间复杂度为O(N²)，因为它执行了N²步。每一步都会执行内部循环，其中包含N个步骤，因此总共有N² * N或N³个步骤，算法的时间复杂度为O(N³)。

- Jonathan Leffler

Answer 2

您将会对N进行三轮循环…所以我说：O(n^3)

- ltiong_sh

Answer 3

算法：

Sum = 0; ~ 1

 for i=1 to N^2 do: ~ 1+2N^2
   for j=1 to N do: ~ (1+2N) * N^2
    'Sum += 1; ~ 1 * N * N^2

时间复杂度：

Time = 1 + 1+2N^2 + (1+2N)*N^2 + 1 * N * N^2

Time = 2 + 2N^2 + N^2 + 2N^3 + N^3

Time = 2 + 3N^2 + 3N^3

O(Time) = O(2 + 3N^2 + 3N^3) ~ O(N^3)

- Khaled.K

---

我对 1+2N^2 这个术语很好奇，乘数 2 是从哪里来的？另外，当涉及到下一行 (1+2N) * N^2 时，那不应该是 (1+2N^2) * N 吗？ - Jonathan Leffler

@JonathanLeffler 不是的，(1+2N) * N^2 是 N 循环的头部，由于它在 N^2 循环内部，所以乘以 N^2。 - Khaled.K