O(n^2)算法与O(n)算法的比较

Question

6

我刚开始学习计算机科学，现在正在学习伪代码，有一些问题需要解答。这是我上学期的第三周，大部分时间都是自学。我的问题如下：

O(n^2)算法和O(n)算法有什么区别？ - 同样地，O(n log n)是什么？ - Ω(n^2)又是什么？

到目前为止，我写出了以下内容：

horner = 0;
for( i = n; i >= 0; i −− )
    horner = x * horner + a[i];

但是发现它的时间复杂度为O(n)，我该如何转换它？

这个算法的运行时间是多少？ - 我知道第一行赋值操作需要1个单位的时间。

在一个实际的算法中，比如C#，它是什么样子的？

- Ronnie Salter

这几乎是C#语法，但我有点困惑。每次x * horner都会为0吗？虽然我可能完全误解了伪代码。 - D. Ben Knoble

@BenKnoble：那是个打字错误。霍纳法每次迭代更新一个“结果”变量，因此只有第一次为零。 - Mike Seymour

@BenKnoble 伪代码可以与真实代码相似。此外，“+a[i]”将在第一次迭代后删除0。 - BradleyDotNET

好的，谢谢。我没有意识到这个问题。 - D. Ben Knoble

2个回答

3

O(n)代表算法达到其结束状态所需的迭代次数、计算次数或步骤数，在最坏情况下，即算法开始时给定的对象数为 n。

假设您有一个包含 5 个元素的数组和一个具有 O(n^2) 复杂度的排序算法。您知道，如果您将此排序应用于该数组，则需要最多 5^2=25 步才能达到其结束状态。

- Dimitris Sfounis

1

我在写评论时犯了很多错误并做了很多修改，以至于我认为我需要使用O(n^3)符号来描述我的评论写作。 - Dimitris Sfounis

5

“它最多需要25步就可以达到终态”不正确。它可能需要3n^2步、10n^2步、1000000n^2步或者n^2+10^100步，但仍然是O(n^2)的。 - T.C.

1

@T.C. 说得好。即使 n + log n + n log n + n^2 也算作 O(n^2)。 - mip

大O符号是关于增长的顺序。如果您使用10个元素运行算法，它将需要一些时间。当元素数量加倍时，需要多长时间？时间加倍意味着它是O(n)，时间增加四倍意味着它是O(n^2)。您可以查看“主定理”以获取有关如何从时间度量中推导出大O符号的更多信息。 - Ray

@Ray 是的，但这是关于增长的渐近阶数 - 所以如果你将10加倍，它可能会比四倍的时间更长，但随着原始数量变得越来越大，这个比率趋近于4。 - Juan Sebastian Lozano

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lucas Crawford · Accepted Answer

你询问的是计算机科学中被称为算法复杂性分析的主题。写程序时考虑算法复杂度非常重要，因为它与运行时间有关，即你的计算需要多长时间才能完成。

大O符号，或者O(n)，代表算法执行的上限运行时间。在这种情况下，O(n)表示对于n个元素，算法计算需要考虑所有n个元素才能完成，是一种线性的计算方式。这种大O时间复杂度的范围从常数时间O(1)到非常缓慢的O(n^n)。同时还要考虑以下方程式：

y=10n+1
y=5n+10

这两个的时间复杂度都是O(n)，因为随着元素数量的增加，方程式会变得越来越大。我们忽略常数，因为方程式将由于变量而变得更大和更快，而不是由于永远不变的常数值而变化。而对于以下方程：

y=10n^2+5n+5

由于10n^2是导致方程增长更快的最大增长元素，因此复杂度将为O(n^2)。我们删除常量并考虑方程中增长最快的组成部分来评估复杂度。

对于Big-Omega复杂度，我们认为这是算法复杂度分析的下限。例如，一个算法可能在Omega(n)（最好情况）下运行得很快，但最长需要O(n^2)（最坏情况），这在排序算法或搜索算法的分析中很常见。

在某些情况下，为了优化原因，我们希望编写具有高效和更快算法的程序，特别是当我们想要更快的解决方案或更快的运行时间时。

您提供的代码示例是O(n)，因为它使用for循环迭代n个元素。考虑双重for循环，其中在当前for循环中有第二个循环。由于在最坏情况下迭代n*n个元素，因此这是O(n^2)。

用于初始化空矩阵的O(n^2)运行时间的Java伪代码：

int result[n][m];
for(int i=0; i<n; ++i){
    for(int j=0; j<m; ++j){
       result[i][j] = 0;
    }
}

请注意，它使用了两个循环，因此导致了O(n^2)的运行时间。

下面是一张图表展示方程式随时间增长的情况（以及它们增长的速度）：