O(n)的算法复杂度

Question

我最近开始尝试普林斯顿大学的this课程中的算法，并观察到以下模式。

O(N)

 double max = a[0];
  for (int i = 1; i < N; i++)
     if (a[i] > max) max = a[i];

O(N^2)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        if (a[i] + a[j] == 0)
           cnt++;

O(N^3)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; k++)
           if (a[i] + a[j] + a[k] == 0)
cnt++;

这里的常见模式是，随着循环中的嵌套层数增加，指数也会增加。 如果我有20个for循环，可以安全地假设我的复杂度为0(N^20)吗？

附注：请注意，20只是我随机选择的一个数字，如果您在代码中嵌套了20个for循环，显然存在问题。

- tawheed

---

想象一下：是什么控制了迭代次数？是N的大小吗？如果所有循环都与N线性变化，那么是的，你会得到N^x，其中x是嵌套循环的数量。 - keyser

请看这个链接：https://dev59.com/enVD5IYBdhLWcg3wXaYd。 - Vedant Terkar

Answer 1

这取决于循环的功能。例如，如果我将第二个循环的结束改为只执行3次迭代，如下所示：

for (int i = 0; i < N; i++)
    for (int j = i; j < i+3; j++)
       if (a[i] + a[j] == 0)
          cnt++;

我们回到O(N)。

---

关键是循环中的迭代次数是否与N相关，并且随着N的增加而线性增加。

---

这里是另一个例子，第二个循环达到了N ^ 2:

for (int i = 0; i < N; i++)
    for (int j = i; j < N*N; j++)
       if (a[i] + a[j] == 0)
          cnt++;

这将是O(N^3)。

- Lee Meador

---

我认为这个答案解释得非常好。 - Ivan

Answer 2

是的，如果循环长度与 N 成正比，并且循环嵌套在彼此之内，就像你所描述的那样。

- FrankPl

Answer 3

在您特定的模式中，是的。但是不能安全地假设一般情况下都是如此。您需要检查每个循环中迭代次数是否为 O(n)，而与所有封闭循环的状态无关。只有在验证了这一点后，才能得出复杂度为 O(n^{loop-nesting-level}) 的结论。

- Ted Hopp

Answer 4

是的。即使您减少了迭代间隔，大O符号也适用于N趋近于无穷大的情况，并且随着所有循环长度与N成比例增长，这样的算法的时间复杂度为O（N ^ 20）。

- user

Answer 5

我强烈建议你理解为什么一个双重嵌套的循环，每个循环从0到N都是O(N^2)。使用求和来评估for循环中涉及的步数，然后删除常数和低阶项，你就可以得到该算法的大O表示。

- Aravind