线性复杂度和二次复杂度
我只是不确定......
如果您有一个可以以以下复杂度之一执行的代码：
- O(n) 的序列，例如：序列中的两个 O(n)
- O(n²)
首选版本将是可以在线性时间内执行的版本。是否会存在这样的情况：O(n) 的序列太多，而 O(n²) 会更好？换句话说，是语句 C x O(n) < O(n²) 对于任何常数 C 总是成立？
为什么或为什么不呢？有哪些因素会影响条件，从而最好选择 O(n²) 复杂度？
I'm just not sure...
If you have a code that can be executed in either of the following complexities:
- A sequence of O(n), like for example: two O(n) in sequence
- O(n²)
The preferred version would be the one that can be executed in linear time. Would there be a time such that the sequence of O(n) would be too much and that O(n²) would be preferred? In other words, is the statement C x O(n) < O(n²) always true for any constant C?
Why or why not? What are the factors that would affect the condition such that it would be better to choose the O(n²) complexity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为这里有两个问题；首先是符号表示的内容，其次是您在实际程序中实际测量的内容
big O 被定义为 n -> 的极限无穷大，所以就大 O 而言，O(n) <无论任何有限常数如何，O(n^2) 始终为真。
正如其他人指出的那样，实际程序只处理一些有限的输入，因此很有可能为 n 选择一个足够小的值，使得 c*n > 。 n^2即c> n，但是严格来说，您不再处理大 O
I think there are two issues here; first what the notation says, second what you would actually measure on real programs
big O is defiend as a limit as n -> infinity so in terms of big O, O(n) < O(n^2) is always true regardless of any finite constants.
as others have pointed out real programs only ever deal with some finite input, so it is quite possible to pick a small enough value for n such that the c*n > n^2 i.e. c > n, however you are strictly speaking no longer dealing with big O
如果常数 C 大于 n 值，那么 O(n²) 算法会更好。
If your constant C is greater than your value of n, then the O(n²) algorithm would be better.
O 表示法中始终存在一个隐含常数，因此，是的，对于足够小的 n，O(n^2) 可能比 O(n) 更快。如果 O(n) 的常数远小于 O(n^2) 的常数，就会发生这种情况。
There is always an implied constant in O notation, so yes, it's possible that for sufficiently small n that O(n^2) may be faster than O(n). This would happen if the constant for O(n) was much smaller than that for O(n^2).
C×O(n)＜ O(n²) 并不总是为真，n 中有一个点可以逆转条件。
当C大而n小时，则C×O(n)＞0。 O(n²)。
然而，C 始终是常数，因此当 n 缩放到很大的数字时，C x O(n) < O(n²)。
因此，当 n 很大时，O(n) 总是优于 O(n²)。
C x O(n) < O(n²) is NOT always true, there is a point in n where it reverses the condition.
When C is large and n is small, then C x O(n) > O(n²).
However, C is always constant, hence when n scales to a large number, C x O(n) < O(n²).
Therefore, when n is large, O(n) is always better than O(n²).