表达式的大 O 表示法
如果我有一个需要 4n^2 + 7n 步才能完成的算法，它的 O 是多少？ O(4n^2)？ O(n^2)？
我知道 7n 被截断，但我不知道是否应该保留 n^2 系数。
谢谢
If I have an algorithm that takes 4n^2 + 7n moves to accomplish, what is its O?
O(4n^2)?
O(n^2)?
I know that 7n is cut off, but I don't know if I should keep the n^2 coefficient or not.
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您应该删除任何系数，因为问题实际上是在“按顺序”询问，它试图将其描述为线性、指数、对数等......也就是说，当 n 非常大时，系数并不重要。
这也解释了为什么你放弃+7n，因为当n非常大时，该项对最终答案的意义相对较小。如果您熟悉微积分，您可能会说 lim n->inf(4*n^2+7n) ~= lim n->inf(4*n^2) ~= lim n->inf(n ^2)
您也可以从图形意义上考虑这个问题...也就是说，如果您将函数 4n^2 + 7n 绘制为越来越大的 n 值，数学家可能会说“它看起来像 n^2”。诚然，它必须是一位相当自由的数学家，因为这不是一个严格的陈述，但这基本上就是 O(...) 试图传达的内容。
You should drop any coefficients because the question is really asking "on the order of", which tries to characterize it as linear, exponential, logarithmic, etc... That is, when n is very large, the coefficient is of little importance.
This also explains why you drop the +7n, because when n is very large, that term has relatively little significance to the final answer. If you are familiar with calculus, you might say lim n->inf(4*n^2+7n) ~= lim n->inf(4*n^2) ~= lim n->inf(n^2)
You can also think about this in a graphical sense... that is, if you graph the function 4n^2 + 7n for larger and larger values of n, a mathematician might say "it looks like n^2". Granted, it would have to be a fairly liberal mathematician, as this isn't a rigorous statement, but that's basically what O(...) is trying to convey.
这些系数与 Big O 表示法无关，因此只是 O(n2)。 正如维基百科所解释的：
The coefficients aren't relevant in Big O notation, so it's just O(n2). As Wikipedia explains:
每个阅读或撰写有关算法复杂性的文章的人都应该确切地知道 Landau 符号 和 渐近符号 是，否则他们并不真正理解发生了什么，或者只是有一个近似值（并且通常误导）的想法。
为了简化（很多），让
f和g是两个函数f : N -> N和g : N -> N。当且仅当存在常数M > 时，我们才说使得f 是 O(g)。 0|f(n)| < M|g(n)|，对于所有n > M。也就是说，更通俗地说，从n的大值开始，所有值f(n)都小于g(n)的倍数code> （即，g比f增长得更快）。该定义相当于
所以，让我们采用
f(n) = 4n^2 + 7n和g(n) = n^2，并尝试证明f 是 O(g)（我将省略{n -> +oo}）：这意味着存在一个
M使得n＞中号==> |f(n)| < M|g(n)|，因此f 是 O(g)。因此，从技术上来说，说
4n^2 + 7n 是 O(4n^2)是正确的，因为说4n^2 + 7n 是 O(n^3)是正确的。 code>、4n^2 + 7n 是 O(e^n)，依此类推。但为了有意义，我们对下界感兴趣。因此，如果f 是 O(e^n)并且f 是 O(n^2)，我们更感兴趣的是知道f 是 O(n^ 2)，因为这限制性更大。非常重要的注意
事项选择算法时极其重要的是要理解大O符号指的是渐近情况，也就是说，当您考虑极其难以想象的情况时巨大的输入，远远超出了已知宇宙中可用的计算能力（即无限的输入集，在数学上用
{n -> +oo}表示）。对于实际用途（即，不是如此巨大的输入），在选择算法时，当然，您会观察候选算法big-O符号，但您必须确保选择的算法非常适合您的（预期）输入（并且性能更好）。
最后，通常性能更好的算法更难以理解和正确实施。在选择算法时，您也必须考虑这一事实（即，我将花在调试和修复该算法的实现上的时间大大优于我必须等待另一个算法的时间）算法，具有更差的大 O 表示法？ 如果是这样，您应该考虑更简单、效率较低的算法，因为整体解决方案会更有效）。
Everyone reading or writing about complexity of algorithms should know exactly what the Landau Symbols and asymptotic notations are, otherwise they don't really understand what is going on, or simply have an approximate (and often misleading) idea.
To simplify (a lot), let
fandgbe two functionsf : N -> Nandg : N -> N. We say thatf is O(g)if and only if there's a constantM > 0such that|f(n)| < M|g(n)|, for alln > M. That is, more informally, starting from a big value ofn, all the valuesf(n)are smaller than a multiple ofg(n)(ie,ggrows faster thanf).That definition is equivalent to
So, let's take
f(n) = 4n^2 + 7nandg(n) = n^2, and try to provef is O(g)(I will omit{n -> +oo}):This implies that there is a
Msuch thatn > M ==> |f(n)| < M|g(n)|, and thusf is O(g).So technically it is correct to say
4n^2 + 7n is O(4n^2), as it is correct to say4n^2 + 7n is O(n^3),4n^2 + 7n is O(e^n), and so on. But to be meaningful, we are interested in the lower bound. So iff is O(e^n)andf is O(n^2), we are more interested into knowing thatf is O(n^2), since this is much more restrictive.VERY IMPORTANT note
What is extremelly important when choosing an algorithm is to understand that big-O notations refers to asymptotic cases, that is, when you consider extremely, unimaginable huge inputs, that can go well beyond the computational power available in the known universe (ie, infinite input sets, expressed mathematically by
{n -> +oo}).For practical uses (ie, not so huge inputs), when choosing an algorithm, sure, you will observe candidate algorithms big-O notations, but you must be sure that the chosen algorithm is well adapted (and performs better) for your (expected) input.
Finally, usually better performing algorithms are more difficult to understand and to implement properly. You must consider this fact as well when choosing an algorithm (ie, is the time I will spend debugging and fixing my implementation of this algorithm considerably superior to the time I would have to wait with another algorithm, with a worse big-O notation?. If so, you should consider the simpler, less efficient algorithm, as the overall solution would be more efficient).
是 O(n^2)。常数因子“移入O”。您只保留最大的指数，因为这是主导的指数。并且您可以省略系数，因为在比较不同的算法时，即使非常大的系数也会比具有较大指数（n 足够大）产生的总数更小。
It's O(n^2). Constant factors "move into the O". You only keep the largest exponent since this is the one dominating. And you can leave out coefficients since when comparing different algorithms even very large coefficients result in smaller total numbers than having a larger exponent (with n large enough).
像这样的语句
意味着对于某个常数乘数
c，表达式cn²最终将超过4n² + 7n。从技术上讲，将系数保留在那里并没有错 -O(n²)和O(4n²)意味着完全相同的事情，因为任何常数c前者的 > 可以用c/4代替后者。然而，这样的事情不太清楚，可能会产生误导，而且绝对不标准。A statement like
means that for some constant multiplier
c, the expressioncn²will eventually overtake4n² + 7n. It's technically not incorrect to leave the coefficient in there —O(n²)andO(4n²)mean the exact same thing, because any constantcfor the former can be replaced byc/4for the latter. However, such a thing is less clear, possibly misleading, and definitely nonstandard.从数学上来说，你可以写成 O(4n²)。这意味着算法的复杂度函数表现为 n->4n² 趋于正无穷。
但在计算机科学/算法中，你只会写 O(n²)，这足以对你的算法进行分类。
Mathematically speaking, you would write O(4n²). It means that the complexity function of your algorithms behaves as n->4n² towards positive infinite.
But in computer science/algorithm, you would only write O(n²), which is sufficient to categorize your algorithm.