algorithm - 如何找出 "Big theta"表示法中的常量

Question

我正在解决“big theta”符号的问题。我知道大 O 表示最坏情况，大 omega 表示最好情况。我也知道我们必须为大 theta 符号找到两个常数 c1 和 c2。我的问题是如何找出常数(c)的值大西塔。

Answer 1

给定函数的 Theta 包围，例如

f(n) = Θ(g(n))

相当于证明极限

lim(n->∞) f(n) / g(n)

存在*。

您可以通过对函数 f 的渐近行为进行有根据的猜测来完成此操作。

然后极限理论告诉你，存在一些 N

n > N => |f(n) / g(n) - C| < ε,

可以写

n > N => C - ε < f(n) / g(n) < C + ε

或

n > N => C1.g(n) < f(n) < C2.g(n).

这就是常量C1和C2的来源。其实这一切都是极限计算的实践。

---

*从技术上讲，下限和上限可能不同，您将执行两种不同的计算。