给定函数的Big Theta、Big O、Big Omega

Question

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

函数A: 2^(3*n)是否可以用作大θ、欧米茄或O作为F的刻画？为什么？

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

Answer 1

不是的。

2^(3*n)是主项，但除非你做了一些非常错误的事情，否则你不会花那么长时间来计算。Wikipedia很好地列出了各种函数的时间复杂度。你正在做的最复杂的操作是升幂，其复杂性在其他post中讨论过。

因为你正在看一个形式为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在Omega(A)中是不需要动脑筋的。对于足够大的n，存在小于F的A的正倍数(即A本身)。

尝试绘制F与2*A的关系图，你会发现2*A很快就会比F更大，并保持更大。因此，对于足够大的参数，存在大于F的A的正倍数(即2*A)。所以根据O的定义，F在O(A)中。

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