算法分析，大O符号作业

Question

嗨，有人能给我解释一下如何解决这个作业吗？(n + log )3^n= O((4^n)/n)。我认为这与解决这个不等式是一样的：(n + log )3^n< c((4^n)/n))。

提前感谢

Answer 1

你需要找到一个c(正如你在你的问题中提到的)，并且你需要证明对于大于某个k的所有n，这个不等式都成立。

通过展示你可以找到有问题的c和k，然后by definition，你已经证明了大O的界限。

相反，如果你找不到这样的c和k，这是因为左边的函数并不是右边的函数的上界。然而，这里不应该是这种情况(当你能确切地说出原因时，你会知道你对渐近增长/边界有了更直观的理解)。

Answer 2

根据definition，如果存在一个常数M，使得每n个都有f(n) = O(g(n))，那么|f(n)| < M|g(n)|就是真的。在计算机科学中，数字是非负的，所以这相当于找到一个M，使得f(n) / g(n) < M

反过来，这可以通过证明随着n增加到无穷大(根据极限的定义) f(n) / g(n)有一个有限的极限来完成。在你的(n^2 + n log n) * (3/4)^n中，由于指数函数是如何工作的，这一点非常明显。