algorithm - 如何简化 Big-O 表达式

Question

我正在尝试理解 Big-O 表达式背后的代数。我已经回答了几个问题，但仍然不太清楚它是如何完成的。

在处理幂时，我们总是忽略较低的幂，例如:

O(10n^4-n^2-10) = O(10n^4)

当涉及乘法时有什么区别？例如:

O(2n^3+10^2n) * O(n) = O(2n^3) ??

最后，我们如何处理日志？例如:

O(n2) + O(5*log(n))

我认为我们试图摆脱所有常数和较低的权力。我不确定对数如何参与简化以及乘号会有什么不同。谢谢。

Answer 1

与代数概念/规则相比，Big-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 大小的增加相比，n^2 项仍在产生巨大的增加。正因为如此，这些表达式的大 O 仍然可以归结为:O(n^2)。

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