math - 确定渐近复杂度

Question

如果给我两个函数并要求我为这两个函数找到渐近复杂度，这意味着什么？是 O() 还是 Big Theta？例如
f1(n)=a^n 和
f2(n)=n^3+n^2

我应该说 f1 是 O(a^n) 而 f2 是 O(n^3) 还是应该使用 big-theta？

Answer 1

O 符号提供了一个渐近的上限；如果 f(n) = O(g(n))，则直观地意味着 f 的增长速度不会比 g 快。

另一方面，Θ 表示法指定了一个紧密的界限。如果 f(n) = Θ(g(n))，这意味着 f 和 g 以相同的速率增长，直到某个常数因子。从技术上讲，f(n) = Θ(n) 意味着 f(n) = O(g(n))，但反过来并不总是正确的。

您可以给出的最精确的分析是使用 Θ 表示法，尽管使用 O 表示法并没有错。

希望这有帮助!