algorithm - o(n) 的算法复杂度

Question

我最近开始使用普林斯顿课程中的算法，并观察到以下模式

上）

 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) 是否安全？

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

score 6 · Accepted Answer

这取决于循环的作用。例如，如果我将第二个循环的结尾更改为只执行 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)

score 2 · Accepted Answer

2

是的，如果循环的长度成正比N并且循环像您描述的那样相互嵌套。

于 2013-08-13T17:35:14.600 回答

score 1 · Accepted Answer

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

score 0 · Accepted Answer

是的。即使您减少了迭代间隔，Big-o 表示法也适用于 N 向无穷大增加，并且随着所有循环的长度与 N 成正比增长，这样的算法确实具有时间复杂度 O(N^20)

score 0 · Accepted Answer

我强烈建议您了解为什么每个循环从 0 运行到 N 的双重嵌套循环是 O(N^2)。使用求和来评估 for 循环中涉及的步骤数，然后删除常量和低阶项，你会得到那个算法的大哦。

5 回答 5