求和的渐近表示法

Question

我很难理解为什么下面的等式对于渐近记法是正确的。

​

​

Answer 1

这个公式让我思考了一下。这样做的问题不是，当涉及到渐近符号时，有很多滥用符号的情况，有很多定义是相等的，但更难写下证明。

但是，我将尝试对这个公式进行解释，然后我们看看是否能理解它。

首先，我通常将O(f(n))解释为f(n)为渐近上界的函数集。这就是为什么我更喜欢写g \in O(f)而不是g = O(f)的原因，但因为后者很常见，所以我对它们的理解是一样的。

方程式的右边是一个函数，写成一些函数的和。这里没什么特别的。

在左边，它变得很有趣。一些大O的总和。这里不是很清楚集合的和应该是什么，就像我解释的大O，但如果你读出来，它是有意义的：

某些函数的上界之和是函数之和的上界。

这就是你在算法分析中一直做的事情。如果您有一个函数运行两个子函数，即O(n)中的f和O(m)中的g，那么这两个子函数将一起在O(n+m)中运行

现在这是一个特例，因为函数的和总是使用相同的函数，参数范围从1到n，但这几乎不会改变任何事情。当然，你可以把它们中的一些看作常量，但是左边绝不是独立于@kaya3的n的。至少有最后一个术语O(f(n))表示k = n，它明显依赖于n，然后在总和中还有n术语。因此，即使您将n乘以一个恒定的上限，这也不应该导致一个恒定的上限。

结束这个:对我来说，这看起来像是一个定义:如果你看到左边，就把它想象成右边，你就会得到你想要的结果。