表达式的大O表示法 [英] Big O Notation of an expression

问题描述

如果我有一个算法需要4n ^ 2 + 7n个动作来完成，它的O是多少? O(4n ^ 2)? O(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)?

我知道7n被截断，但是我不知道是否应该保留n ^ 2系数.

I know that 7n is cut off, but I don't know if I should keep the n^2 coefficient or not.

谢谢

推荐答案

您应该删除所有系数，因为问题实际上是在按...的顺序"询问，它试图将其表征为线性，指数，对数等.即，当n非常大时，该系数的重要性不大.

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.

这也解释了为什么您放弃+ 7n，因为当n非常大时，该术语对最终答案的意义相对较小.如果您熟悉微积分，您可能会说lim n-> inf(4 * n ^ 2 + 7n)〜= lim n-> inf(4 * n ^ 2)〜= lim n-> inf(n ^ 2)

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)

您还可以从图形角度考虑这一点...也就是说，如果对n的值越来越大用函数4n ^ 2 + 7n进行图形绘制，则数学家可能会说看起来像n ^ 2".当然，它必须是一个相当自由的数学家，因为这不是一个严格的陈述，但这基本上是O(...)试图传达的内容.

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.

这篇关于表达式的大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！