如果我有一个算法需要4n ^ 2 + 7n个 Action 来完成，那么它的O是多少？
O(4n ^ 2)？
O(n ^ 2)？
我知道7n被截断，但是我不知道是否应该保留n ^ 2系数。
谢谢
最佳答案
您应该删除任何系数，因为问题实际上是在“按...的顺序”询问，它试图将其表征为线性，指数，对数等。也就是说，当n很大时，系数的重要性不大。
这也解释了为什么您放弃+ 7n，因为当n非常大时，该术语对最终答案的意义相对较小。如果您熟悉微积分，您可能会说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(...)试图传达的内容。
关于time-complexity - 表达式的大O表示法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2081846/