我们可以使用Big Oh比较算法吗？
从过去的三天开始，我一直在谷歌搜索大o符号，并得出以下结论。
大o符号只是告诉我们，随着输入大小，算法所花费的时间如何增长。
我们只能比较来自两个不同类的算法，而不是从同一类中进行比较。我们可以将
o（n^2）与o（n）进行比较，但不能与其他算法的o（n^2）一起进行比较。 /p>我们省略了常数，因为我们仅考虑生长。
所有这些澄清后，我仍然有疑问：
我们知道
o（10n）比o（n^2）n＆lt慢。 ; 10。那么，我们怎么能说顺序o（n）的算法总是比o（n^2）而没有实际考虑常数？我们如何说明时间复杂性的算法
o（n）总是最好的？如果我们有
f（n）= 10n^2+5n+6，我们省略10，因为该函数始终增加一个常数10。但是，为什么我们要还省略5N+6（不是常数）？它在功能增长中不是很重要吗？
I have been googling about Big O notation from past three days and came to the following conclusions.
Big O notation just tells us how the time taken by an algorithm grows as we increase the input size.
We can compare only algorithms from two different classes and not from the same class i.e; we can compare
O(n^2)withO(n)but not withO(n^2)of some other algorithm.We omit the constants as we are only considered about growth.
After having all this clarification, I still have a doubt:
We know that
O(10n)is slower thanO(n^2)forn<10. Then how can we say that the algorithm of orderO(n)is always best thanO(n^2)without actually considering the constants?How can we state that the algorithm of time complexity
O(n)is always best?If we have
f(n)=10n^2+5n+6, we omit10as the function always increase by a constant 10. But why do we also omit5n+6(not constant)? Isn't it significant in function growth?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
它只告诉我们花费的时间如何渐近。这意味着您甚至无法得出与另一个输入大小所花费的时间相比，对于一个输入大小所花费的时间。给定一个实现的函数
It only tells us how the time taken grows asymptotically. This means you cannot even make conclusions about the time taken for one input size compared to the time taken for another input size. Given an implemented function ????, a run of ????(????=100) may even be faster than a run of ????(n=90), whatever the time complexity of that function is.
If you are comparing execution times, then again, the given time complexities tell us nothing concerning the actual execution times of two algorithms. The difference in asymptotic behaviour may only become noticeable in their execution times for input sizes that are impractically large.
It is not really about growth -- a function may temporarily show a descending slope for increasing input sizes -- but asymptotic behaviour. When the input size increases towards infinity, a constant eventually becomes irrelevant.
No, we do not know that.
For instance, compare these two algorithms:
Here Fun1 is O(10????) = O(????) and Func2 is O(????²). Func1 will never be slower than Func2.
One cannot compare two time complexities in terms of "slower".
We don't say that. On the contrary, this overhead of constants (and linear coefficients, ...etc) does play a role in deciding which algorithm to use. For instance, this is why quick sort is quite popular, even though there are sorting algorithms whose worst case time complexity is better.
We don't state that. And don't forget there are sub-lineair algorithms, whose time complexity is O(log????), or even O(1).
The part that the lower graded terms play in the function becomes less and less important the higher the value of ????. For instance, when ???? is 10000, the terms 5????+6 only influence the value by 0.005%, and it becomes more and more negligible as we increase ????. Asymptotically it has lost all its impact. And so all that remains is ????²
当算法具有时间复杂性o（n²）[为了示例]，我们所知道的是，其实际运行时间不超过一定的n
。真实的时间就像cnlog²n或cn^1.993。也可能是运行时间在3N+125和2N²-3√N之间，具体取决于特定输入。
现在，如果界限紧密并且算法具有平稳的行为，我们确实可以有一个等于CN² +低订单项的时间。如果您想基于此比较两种算法，则应
检查该行为的最低值（如果n的值是天文学的，则实际上没有可用的信息）;
检查低订单条款是否真的可以忽略N;
的实际值
获取对实际实现的两种算法的C常数估算；
估计润滑点点（其中c f（n）= c'g（n））。
这是理论方法。实际上，您很少能够应用它。基准测试是您的朋友。
您都可以使用以下经验规则：
的中等值，
o（n log n）通常比O（n²）更好（n²）；
o（n log n）对于中等值；
的中等值可能无法击败O（n）
n²优于n³;
的中等值
高阶多项式或超级多项式函数仅适用于有限的n值，因此复杂性之间的略有差异（例如O（n^5）与O（2^n））可能无关紧要。
When an algorithm has time complexity O(N²) [for the sake of example], all we know is that its actual running time does not exceed cN² as of a certain N.
First, it can be that the bound is not tight, so that the true time would be like cN log²N or cN^1.993. It could also be that the running time is comprised between 3N+125 and 2N²-3√N, depending on the particular input.
Now if the bound is tight and the algorithm has a smooth behavior, we could indeed have a time equal to cN² + low order terms. If you want to compare two algorithms based on this you should
check for what minimal value of N this behavior holds (if the value of N is astronomical, you have in fact no usable information);
check if the low order terms are truly neglectable for the practical values of N;
get an estimate of the c constants of both algorithms for a real implementation;
estimate the breakeven point (where c F(N) = c' G(N)).
This is the theoretical approach. In practice you are rarely in a position to apply it. Benchmarking is your friend.
Anyway, you can use the following rules of thumb:
O(N log N) is often better than O(N²) for medium and large values of N;
O(N log N) may fail to beat O(N) for moderate values of N;
N² is preferable over N³ for moderate values of N;
higher order polynomials or super-polynomial functions are only usable for limited values of N, so that slight differences between the complexities (say O(N^5) vs. O(2^N)) might not matter.
我有一些直观和简单的答案。
通常，我们不感兴趣算法如何针对小输入尺寸执行，因为对于小输入尺寸，几乎所有内容都很快。优化已经快速的事物是浪费时间。因此，在比较算法时，我们永远不会看这个。例如，如果在现实生活中您想用9件解决一个难题，那么无论您使用哪种算法或拼图中的图片，您都将永远很快。只有当您有1000件的难题时，您可能需要制定策略（例如，首先执行边境）。
的确，5N+6不感兴趣。如果您仅查看大输入尺寸，则只需n^2即可。让我们看看一个实用的Exammple：您有一种需要10n^2+5n+6 ms的算法。您输入的大小为100。因此，您等待10*x100^2 + 5x100 + 6 = 100000 + 500 + 6 = 100506毫秒。值10n^2 = 100000已经非常接近此结果，并且506并不重要。如果您必须等待一分钟40秒的结果，那么您不在乎它迟早是506毫秒。即使对于1.0001n^2 + 100000n等极端情况，您也总是有这种现象。二次增长是主要的。
您在问题2中忽略10的句子，因为它是一个常数有点不精确。在您的示例中6是一个常数。 10是一个恒定的因素。这是一个区别。您可能想知道为什么我们对这个不断的因素不感兴趣。答案是我们只想谈论该算法，而不是它的实现或执行程度。再次一个示例：如果您在Java中编程了算法并在慢速机器上执行它，则结果可能比在汇编程序中实现的同一算法要长10倍，并在快速机器上执行。但这很明显。这是没有价值的信息。不变的因素更是一个问题，您的算法的执行速度有多快，而不是算法的良好性。因此，我们不考虑不断的因素。
I have a few intuitive and easy answers.
Normally we are not interested how an algorithm performs for small input size, because for small input sizes, nearly everything is fast. Optimising something that is already fast is a waste of time. Therefore when comparing algorithms we don't ever look at this. If for example in real life you want to solve a puzzle with 9 pieces, you will always be fast, regardless of what algorithm you use or what picture is on the puzzle. Only if you have a puzzle of 1000 pieces you may want to have a strategy (e.g. doing the border first).
It is true that the 5n+6 are not of interest. If you only look at big input sizes then only n^2 is of interest. Let's see a practical exammple: You have an algorithm that needs 10n^2+5n+6 ms. You input has a size of 100. So you wait 10*x100^2+5x100+6 = 100000 + 500 + 6 = 100506 ms. The value 10n^2 = 100000 is already very close to this result and the 506 do not really matter. If you have to wait one Minute and 40 seconds for a result than you don't care if it is 506 ms sooner or later. You always have this phenomenon, even for extreme cases like 1.0001n^2 + 100000n. The quadratic grow is dominant.
Your sentence in question 2 that you ignore 10 because it is a constant is a bit imprecise. In your example 6 is a constant. 10 is a constant factor. That is a difference. You may wonder why we are not interested in this constant factor. The answer is that we want to talk about the algorithm only and not how well it is implemented or executed. Again an example: If you program an algorithm in Java and execute it on a slow machine, the result may take 10 times longer than the same algorithm implemented in Assembler and executed on a fast machine. But this is obvious. This is no information with value. The constant factor is more a question how fast your algorithm is executed but not a question how good your algorithm is. And therefore we don't look at constant factors.