什么是
O(n^2) 和 O(n.log(n)) 的区别？大O符号表示法：O(n^2)和O(n.log(n))之间的区别是什么？
3
- Jenny
5
从技术角度来看，这取决于N的值... - Jrud
24从技术上讲，不，它没有。 - tvanfosson
那要看情况...他的问题意味着他想知道方程形成曲线的差异...数学术语中，这个问题转化为在给定的n值处差异是什么。 - Jrud
Jrud，我认为根据问题的措辞，支持你的解释非常困难。该问题只是询问O(n^2)和O(n logn)之间的区别。 - harms
2@Jrud：按照定义，O(n)并不取决于n。 - Konrad Rudolph
6个回答
15
n的平方增长速度更快。
- Joe Koberg
9
你从哪里得到这张图片的？它是一个很好的插图。 - Neil Foley
1对于长远来看，对数基数应该是无关紧要的。 - Joe Koberg
这并没有真正传达O(n^2)和O(nlogn)的渐近行为，因为如果绿色曲线恰好是n^2，那么你可能会有另一个函数，它仍然是O(n^2)，但看起来与红色曲线非常相似。对于忽略了Big-O理解中这个关键方面的问题，扣1分。 - harms
1иҝҷдёӘй—®йўҳиҜўй—®дәҶNlogNе’ҢN^2д№Ӣй—ҙзҡ„еҢәеҲ«пјҢиҖҢдёҚжҳҜN^2е’Ң(0.01 * N^2)д№Ӣй—ҙзҡ„еҢәеҲ«... иҝҷжҳҜеӨ§Oз¬ҰеҸ·вҖңеә”иҜҘжҺ©зӣ–вҖқзҡ„гҖӮ - Joe Koberg
一个重要的行为是当 n > log 基数时，在 n < nlogn < n^2。即使有疯狂的系数，这个行为最终也会体现出来。在这里，nlogn 看起来又被人为压缩了。否则，在 n = 100 时，它将超过 100。 - Ewan Todd
显示剩余4条评论
2
Big O计算一个数据集大小（n）相对于运行时间的上限。
O(n*log(n))的算法并不总是比O(n^2)算法更快，但在考虑最坏情况时，它很可能更快。当你复制工作集（最坏情况）时，O(n^2)算法需要大约4倍的时间，而O(n*log(n))算法则需要更少的时间。数据集越大，使用O(n*log(n))算法通常会更快。
编辑：感谢'harms'，我将纠正第一次回答中的错误陈述：我说在考虑最坏情况时O(n^2)总是比O(n*log(n))慢，这是错误的，因为两者都是除了一个常数因子之外相同！
例如：假设我们有最坏情况，我们的数据集大小为100。
O(n^2) --> 100 * 100 = 10000
O(n*log(n)) --> 100 * 2 = 200 (使用log_10)
问题在于两者都可以乘以一个常数因子，比如我们把后面那个乘以c，结果就是：
O(n^2) --> 100 * 100 = 10000
O(n*log(n)) --> 100 * 2 * c = 200 * c (使用log_10)
因此，对于c > 50，我们得到O(n*log(n)) > O(n^2)，n=100。
我必须更新我的声明：对于每个问题，在考虑最坏情况时，O(n*log(n))算法将比O(n^2)算法更快，对于任意大的数据集。
原因是：c的选择是任意的但是常数。如果你增加数据集足够大，它将支配每个c的常数选择的影响，并且当讨论两个算法时，两者的c都是常数！
O(n*log(n))的算法并不总是比O(n^2)算法更快，但在考虑最坏情况时，它很可能更快。当你复制工作集（最坏情况）时，O(n^2)算法需要大约4倍的时间，而O(n*log(n))算法则需要更少的时间。数据集越大，使用O(n*log(n))算法通常会更快。
编辑：感谢'harms'，我将纠正第一次回答中的错误陈述：我说在考虑最坏情况时O(n^2)总是比O(n*log(n))慢，这是错误的，因为两者都是除了一个常数因子之外相同！
例如：假设我们有最坏情况，我们的数据集大小为100。
O(n^2) --> 100 * 100 = 10000
O(n*log(n)) --> 100 * 2 = 200 (使用log_10)
问题在于两者都可以乘以一个常数因子，比如我们把后面那个乘以c，结果就是：
O(n^2) --> 100 * 100 = 10000
O(n*log(n)) --> 100 * 2 * c = 200 * c (使用log_10)
因此，对于c > 50，我们得到O(n*log(n)) > O(n^2)，n=100。
我必须更新我的声明：对于每个问题，在考虑最坏情况时，O(n*log(n))算法将比O(n^2)算法更快，对于任意大的数据集。
原因是：c的选择是任意的但是常数。如果你增加数据集足够大，它将支配每个c的常数选择的影响，并且当讨论两个算法时，两者的c都是常数！
- Johannes Weiss
2
“O(n*log(n))并不总是比O(n^2)更快”，这是正确的。但是后续的“但在考虑最坏情况时，它确实更快”是不正确的。您是否将最坏情况分析与大O分析混淆了（也许将最佳情况与大Omega混淆了）？它们不应该混淆，实际上它们彼此没有任何关系。 - harms
你是正确的，因为它总是「除了一个常数因子」！我会更新我的答案。谢谢 - Johannes Weiss
1
你需要更具体地说明你的问题，但在这种情况下，O(n log(n)) 更快。
- Marek Karbarz
1
n log(n) 的增长速度明显较慢
- gillonba
1
运行时间为O(nlog(n))的算法通常比运行时间为O(n^2)的算法更快。
大O符号定义了性能的上限。随着数据集大小（n）的增长，执行任务所需的时间也会增加。您可能会对iTunes U algorithms course from MIT感兴趣。
- acrosman
5
1所有的O(n^2)函数并不保证在所有n值上都比所有的O(nlogn)函数慢。 +1 - Annabelle
正确。我忽略了这个关系假设n的值足够大。 - acrosman
你还忽略了O()是一个上界的事实。 - Kugel
1Big-O 定义了性能的上限。 - acrosman
链接已损坏。 - Cœur
0
“大O符号”表示算法运行时间增长的上限估计。如果一个算法被认为是O(n^2)，那么简单来说，它表示当n=1时，最多需要1个单位的时间，当n=2时，最多需要4个单位的时间，以此类推。同样地，对于O(n log(n))，它表示增长将遵循O(n log(n))的上限。如果我在这里表述得不够准确，请在评论中纠正我。
希望这可以帮到你。
希望这可以帮到你。
- user59634
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接