time-complexity - 给定函数的 Big Theta、Big O、Big Omega

Question

考虑函数 F：2^(3*n) + n^2

函数 A: 2^(3*n) 可以用作 Big Theta、Omega 或 O 作为 F 的表征吗？为什么？

我正在修改 Big Omega、Big Theta 和 Big O 的概念，我遇到了这个例子，但不知道从哪里开始。

Answer 1

不。

2^(3*n) 是主要术语，但除非你做错了什么，否则你不会花那么长时间来计算。Wikipedia有一个很好的列表，列出了各种函数的时间复杂度。你正在做的最复杂的操作是提升到一个幂，它的复杂性在其他帖子中讨论。

由于您正在查看 g(f(x)) 形式的函数，其中 g(x) = 2^x 和 f(x) = 3x，因此计算时间将为 O(h) + O( k)，其中 h 是 g 的时间复杂度，k 是 f 的时间复杂度。想一想：它不应该超过这个，如果是的话，你可以把操作分成两部分，通过分开做部分来节省时间。因为 h 将在这个总和中占主导地位，所以您通常会忽略 k 项。

Answer 2

是的，三个都行。一般来说，您只需要关注增长最快的词条，因为增长较慢的词条会被增长更快的词条“淹没”。

详细地：

显然 F 比 A 增长得快，所以 F \in \Omega(A) 是不费吹灰之力的。对于所有足够大的 n，存在小于 F 的 A 的正倍数（即 A 本身）。

尝试针对 2*A 绘制 F。你会发现 2*A 很快变得比 F 大并且保持更大。因此，对于足够大的参数，存在大于 F 的 A 的正倍数（即 2*A）。所以根据 O, F \in O(A) 的定义。

最后，由于 F \in \Omega(A) 和 F \in O(A)，F \in \Theta(A)。