我在阅读关于大O表示法的内容。
所以，任何一个O(N)算法也是一个O(N^2)算法。
这对我来说似乎很令人困惑，我知道大O只提供上限。
但是，一个O(N)算法怎么可能也是一个O(N^2)算法。
是否有任何例子可以说明这种情况？
我想不出任何例子。
有人能向我解释一下吗？
6个回答
10
"Upper bound" 的意思是算法所需的时间不会超过（即 ≤）这个时间长度（当输入大小趋近于无穷大时，考虑相关常数因素）。
这并不意味着它将永远需要那么长时间。
O(n) 的复杂度也是 O(n log n)、O(n²)、O(n³)、O(2ⁿ) 以及任何渐进地比 n 大的复杂度。
如果您熟悉相关的数学知识，您也可以从 正式定义中看到这一点。
这并不意味着它将永远需要那么长时间。
O(n) 的复杂度也是 O(n log n)、O(n²)、O(n³)、O(2ⁿ) 以及任何渐进地比 n 大的复杂度。
如果您熟悉相关的数学知识，您也可以从 正式定义中看到这一点。
- Bernhard Barker
4
谢谢您的评论。但是在这里，我们是否尝试更精确地使用大O符号呢？有没有一些例子可以说明O（N）可能是O（N ^ 2）？ - Nadir Laskar
@NadirLaskar，O(N)总是O(N^2)，你正在考虑紧密边界的问题。 - perreal
1@NadirLaskar 不，大O表示的只是一个上界，也就是我在答案中所描述的。O(n) 总是 O(n^2)。如果你想要一个紧密的（下限>=和上限<=）边界，那么大Theta (Θ) 就是你要找的。有时候是Θ(n)，有时候是Θ(n^2)的算法与算法的最佳情况、平均情况和最坏情况有关（每种情况都有自己的复杂度），这完全是一个不同的问题，与大O实际意义和引用中所说的内容无关。 - Bernhard Barker
太酷了！基本上，我写过的每个算法都是O(n!)。至少我真心希望是这样的 :D - Eric Duminil
6
O符号通常可以简单地理解为“小于”。
比如如果我告诉你x小于4，那么显然x小于5和6等等。
O(n)的意思是，如果算法的输入规模为n（n可以是元素的数量、元素的大小或者任何数学上用来描述输入规模的东西），那么该算法运行“大约需要n次迭代”。
更形式化一点，它的意思是算法中步骤的数量x满足以下条件：
x < k*n + C，其中K和C是正实数
换句话说，对于所有可能的输入，如果输入的规模为n，则算法执行的步骤不超过k*n+C个。
O(n^2)类似，只是上限变成了k×n^2+C。因为n是自然数，所以n^2大于等于n，因此该定义仍然成立。事实上，由于x因此，O(n)的算法也是O(n^2)的算法，O(N^3算法)和O(n^n)的算法也是如此。
比如如果我告诉你x小于4，那么显然x小于5和6等等。
O(n)的意思是，如果算法的输入规模为n（n可以是元素的数量、元素的大小或者任何数学上用来描述输入规模的东西），那么该算法运行“大约需要n次迭代”。
更形式化一点，它的意思是算法中步骤的数量x满足以下条件：
x < k*n + C，其中K和C是正实数
换句话说，对于所有可能的输入，如果输入的规模为n，则算法执行的步骤不超过k*n+C个。
O(n^2)类似，只是上限变成了k×n^2+C。因为n是自然数，所以n^2大于等于n，因此该定义仍然成立。事实上，由于x因此，O(n)的算法也是O(n^2)的算法，O(N^3算法)和O(n^n)的算法也是如此。
- Makogan
2
大O表示法描述的是上限，但说O(n)也是O(n^2)并不是错的。 O(n)算法是O(n^2)算法的子集。这就像正方形是所有矩形的子集一样，但并不是每个矩形都是正方形。因此从技术上讲，即使不精确，也可以说O(n)算法是O(n^2)算法。
- dey
2
若某个问题的时间复杂度为O(N)，那么对于大N，该问题所需的时间不会超过一个固定常数k与N的乘积f(N)=k*N。但是它也比k*N^2小。因此，O(N)的含义是O(N^2)，或者更普遍地说，对于所有的m>1，都有O(N^m)。
* 我假设N>=1，这在大N的情况下确实如此。
- Ken Wei
1
大O符号的定义：
对于任意 x >= x0，若函数 f(x) 满足 |f(x)| <= M|g(x)|，则称 f(x) 是 O(g(x))。
显然，如果 g1(x) <= g2(x)，则有 |f(x)| <= M|g1(x)| <= M|g2(x)|。
- Yola
-1
对于只有一个循环的算法，时间复杂度为O(n)，而嵌套循环的算法时间复杂度为O(n^2)。现在考虑冒泡排序算法，它使用了嵌套循环。
如果我们给冒泡排序算法一个已经排好序的输入集合，内部循环将永远不会被执行，因此对于这种情况，时间复杂度为O(n)，而对于其他情况，时间复杂度为O(n^2)。
- Praveen Kumar Karthikeyan
1
这并不是引用语句的意思。因为 O(...) 只涉及一个上限（即已知比某个值大的值），所以将“太大”的值放在括号里总是正确的（但不太有用）。 - Joachim Sauer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
N，那么它也必须被上限为N^2，这是一个更高的上限。但通常情况下，如果我们可以给出一个更紧密的上限O(N)，我们就不会报告它为O(N^2)。 - Tim Biegeleisen