问大O表示法解释/证明

EN

您所要做的就是考虑f(n)和g(n)在n到infinity时的重要条款。

现在考虑一下f(n)：

​

​

和g(n)：

​

现在的结论是：

我认为这个问题有两个部分。第一种是确定哪个函数(如果两者都有)具有更大的渐近增长。第二是证明你所决定的是正确的。

至于第一部分，我建议简单地看一下序列中最有力的术语。F和g的阶分别为2.5 (5n^2 * sqrt(n)和6n^2 * sqrt(n) )。在丢弃系数后，哪一个在n走向无穷远时增长得更快？结果表明，去掉这些系数会得到相同的精确函数(即n^2 * sqrt(n))，因此这些函数具有相等的渐近增长。这意味着我们可以证明f= O(g)和g= O(f)。

为了证明第一个，我们只需要找到一些C和k，使得对于所有n>k，我们都有C* g(n) > f(n)。我认为最容易做到这一点的方法之一就是用矛盾来证明。这就是说，假设对于所有C和k，f(n) >C* g(n)对于所有n> k，那么，在简化表达式之后，我们可以选择C和k的大值来证明这个假设是错误的。