不过几分困惑的大O符号 [英] Still sort of confused about Big O notation

问题描述

所以，我一直在试图了解大O符号，以及我可以，但还是有一些事情我感到困惑。所以我一直读，如果事情是O（n），它的一般的是指最坏情况下的算法，，但它并不一定是指最坏情况方案的，这就是为什么我们可以说最好的情况下插入排序的例子是O（n）。但是，我真的不能使这意味着什么意义。我知道，如果最坏的情况是O（n ^ 2），这意味着重新$ P $功能psents该算法在最坏情况下的增长速度不会快于​​N ^ 2（有上限）。但如果你有O（N）的最好的情况下，我应该怎么看，作为？在最好的情况下，该算法的增长速度不小于n？我的图片是带有n的图作为上限，如

So I've been trying to understand Big O notation as well as I can, but there are still some things I'm confused about. So I keep reading that if something is O(n), it usually is referring to the worst-case of an algorithm, but that it doesn't necessarily have to refer to the worst case scenario, which is why we can say the best-case of insertion sort for example is O(n). However, I can't really make sense of what that means. I know that if the worst-case is O(n^2), it means that the function that represents the algorithm in its worst case grows no faster than n^2 (there is an upper bound). But if you have O(n) as the best case, how should I read that as? In the best case, the algorithm grows no faster than n? What I picture is a graph with n as the upper bound, like

如果一个算法的最好情况是O（n），则n为上界的算法的运算速度有多快，在最好的情况下成长，因此他们无法生长于n快......但止跌牛逼意味着他们的可以的增长速度是O（log n）的，或O（1），因为它们是低于上限？这将没有任何意义，但因为O（log n）的，或O（1）比O（n）的一个更好的方案，因此为O（n）将不会是最好的情况？我迷茫笑

If the best case scenario of an algorithm is O(n), then n is the upper bound of how fast the operations of the algorithm grow in the best case, so they cannot grow faster than n...but wouldn't that mean that they can grow as fast as O(log n) or O(1), since they are below the upper bound? That wouldn't make sense though, because O(log n) or O(1) is a better scenario than O(n), so O(n) WOULDN'T be the best case? I'm so lost lol

推荐答案

大澳，大Θ，大Ω独立于最坏情况，平均情况，而最好的情况。

Big-O, Big-Θ, Big-Ω are independent from worst-case, average-case, and best-case.

记号F（N）= O（G（N））是指F（N）的增长的 G（N）不超过更快一些固定倍数的。照片 记号F（N）=Ω（G（N））是指F（N）长的不慢于G（N）的一些固定倍数的。照片 记号F（N）=Θ（G（N））是指两个以上都是真实的。

The notation f(n) = O(g(n)) means f(n) grows no more quickly than some constant multiple of g(n).
The notation f(n) = Ω(g(n)) means f(n) grows no more slowly than some constant multiple of g(n).
The notation f(n) = Θ(g(n)) means both of the above are true.

请注意，F（N），在这里可以重新present最好的情况，最坏的情况下，或一般 - 案例与运行输入大小为n的节目时间。
此外，平均可以有许多含义：它可以指的平均输入的或的平均输入大小的（预期的时间），或者它可以指的在从长远来看，的（摊销时间），或两者​​兼而有之，或别的东西。

Note that f(n) here may represent the best-case, worst-case, or "average"-case running time of a program with input size n.
Furthermore, "average" can have many meanings: it can mean the average input or the average input size ("expected" time), or it can mean in the long run (amortized time), or both, or something else.

通常，人们有兴趣在最坏情况下的的运行程序的时候，摊销整个程序的运行时间的（所以如果事情成本的 ñ的最初但只加1的时间为未来的 N 的元素，它平均出2的成本每个元素）。最有用的东西在这里测量的是的最小上界的上最坏情况下的时间;因此，通常情况下，当你看到别人要求的大O的程序，这是他们在寻找什么。

Often, people are interested in the worst-case running time of a program, amortized over the running time of the entire program (so if something costs n initially but only costs 1 time for the next n elements, it averages out to a cost of 2 per element). The most useful thing to measure here is the least upper bound on the worst-case time; so, typically, when you see someone asking for the Big-O of a program, this is what they're looking for.

类似地，证明的问题本质上是困难的，人们可能会试图表明的最坏情况的（或也许平均情况）运行时间的至少的一个一定量（例如，指数）。
你会使用大Ω符号对于这些，因为你正在寻找这些下限。

Similarly, to prove a problem is inherently difficult, people might try to show that the worst-case (or perhaps average-case) running time is at least a certain amount (for example, exponential).
You'd use Big-Ω notation for these, because you're looking for lower bounds on these.

然而，最坏情况和Big-O，或者最佳案例和大Ω之间没有特殊的关系。
既可以用于任一，这只是其中之一比另一个更典型

However, there is no special relationship between worst-case and Big-O, or best-case and Big-Ω.
Both can be used for either, it's just that one of them is more typical than the other.

所以，上部边界的的最佳的情况下，是不是非常有用。是的，如果算法的总是的需要O（n）的时间，那么你可以说这是为O（n），在最好的情况下，以及平均，以及最糟糕的情况。这是一个完全正常的声明中，除了最好的情况下的通常是非常微不足道的，因此没有兴趣本身。

So, upper-bounding the best case isn't terribly useful. Yes, if the algorithm always takes O(n) time, then you can say it's O(n) in the best case, as well as on average, as well as the worst case. That's a perfectly fine statement, except the best case is usually very trivial and hence not interesting in itself.

此外，请注意，F（N）= N = O（N ² ） - 这在技术上是正确的，因为˚F变得更慢于n ² ，但它的没有用处的，因为它不是的至少的上限 - 有一个很明显的上限这是比这一个，即O（n）的更有用。所以，是的，我们很欢迎你说的最好/最差/运行一个程序的时间平均情况为O（n！）。这就是数学上完全正确的。这只是无用的，因为当有人问大O他们感兴趣的至少的上限，而不是一个随机的上限。

Furthermore, note that f(n) = n = O(n²) -- this is technically correct, because f grows more slowly than n², but it is not useful because it is not the least upper bound -- there's a very obvious upper bound that's more useful than this one, namely O(n). So yes, you're perfectly welcome to say the best/worst/average-case running time of a program is O(n!). That's mathematically perfectly correct. It's just useless, because when people ask for Big-O they're interested in the least upper bound, not just a random upper bound.

另外值得一提的是，也可能只是不足的描述程序的运行时间为f（n）的。 的运行时间通常取决于输入本身，而不仅仅是它的大小的。例如，它可能是的甚至的查询是很轻松的回答，而奇的查询需要很长的时间来回答。
在这种情况下，你不能随便给的 F 的作为的函数的 N 的 - 这将取决于其他变量也是如此。最后，请记住，这只是一套数学工具;这是你的工作，弄清楚如何将它应用到你的程序，并计算出的什么是一个有趣的事情来衡量的。在一个有用的方式使用工具需要一些创造力，和数学也不例外。

It's also worth noting that it may simply be insufficient to describe the running-time of a program as f(n). The running time often depends on the input itself, not just its size. For example, it may be that even queries are trivially easy to answer, whereas odd queries take a long time to answer.
In that case, you can't just give f as a function of n -- it would depend on other variables as well. In the end, remember that this is just a set of mathematical tools; it's your job to figure out how to apply it to your program and to figure out what's an interesting thing to measure. Using tools in a useful manner needs some creativity, and math is no exception.

这篇关于不过几分困惑的大O符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！