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 表示法并没有错。

希望这可以帮助！

Answer 2

Big Oh 和 Big Theta 都用于渐近分析。说函数 f(n) = O(n^3) 意味着它的增长速度不超过 n^3。要说函数 f(n) = Θ(n^3) 意味着它的增长速度与 n^3 一样快。