如何找到两个和之间的复杂度，以及其中一个是另一个的O，Ω还是Θ？

Question

我们有以下总和f(n) and g(n)。

如何显示f（n）= O（g（n）），f（n）=Ω（g（n））或f（n）=Ω（g（n））？

我知道第一个是谐波数^（-k）。

Answer 1

您的f（n）为Θ（n ^k）（假设常数k为多项式）。 g（n）显然是Ω（2 ⁿ）（它始终大于或等于2 ⁿ）。因为对于任何k n（[k = O（2 ⁿ）（可以找到here证明），所以f（n）= O（g（n））。