问如何简化大O表达式

EN

与代数概念/规则相比，大-O表达式与微积分(特别是极限)的关系更为密切。我发现考虑像您提供的示例这样的表达式的最简单方法是先插入一个小数目，然后插入一个非常大的数字，然后观察结果是如何变化的：

Expression: O(10n^4-n^2-10)
use n = 2: O(10(2^4) - 2^2 - 10)
           O(10 * 16 - 4 - 10) = 146
use n = 100: O(10(100^4) - 100^2- 10)
             O(10(100,000,000) - 10,000 - 10) = 999,989,990

从这里你可以看到，n^4项超越了表达式中的所有其他术语。因此，该算法将被表示为具有O(n^4)的运行时间.

所以，是的，你的假设是正确的，你通常应该有最高的幂，滴常数，和降序-1项。

对数实际上是“解”指数。因此，它们将减少算法的总体O-运行时间.然而，当它们与指数运行时间相加时，它们通常会被更大的命令项所推翻。在您提供的示例中，如果我们再次使用实数进行评估：

Expression: O(n^2) + O(5*log(n))
use n=2:    O(2^2) + O(5*log(2))
            O(4) + O(3.4657) = 7.46
use n=100:  O(100^2) + O(5*log(100))
            O(10,000) + O(23.02) = 10,023

您会注意到，虽然对数项在增加，但与n的大小增加相比，这并不是很大的收益。然而，n^2项与n的大小的增加相比，仍然产生了巨大的增长。正因为如此，这些表达式中的Big仍然可以归结为: O(n^2)。

如果您有兴趣进一步阅读这方面的数学方面，您可能需要查看以下文章：https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/algebra/page/algebra.html