Big Theta Notation 公式令人困惑需要澄清

Question

如果 Big Theta 符号的数学规则是：

f(n) = Theta (g(n)) if and only if f(n) >= cg(n) for some c after n >= n0 >=0

那么当 f(n) = 5n² 那么我们认为它是 Theta(n²)
考虑 5n² >= n² 对于 c = 1 和 n₀ = 0
但是
为什么不是 f(n) = theta(n)
考虑 5n² >= n 对于 c = 1 和 n₀ = 0 ??

Answer 1

首先，Theta(g)是一个集合的函数。所以技术上你需要写 f in Theta(g) 而不是 f = Theta(g).

非正式地 Theta(g) 包含所有增长同样强（渐近）的函数。所以它就像一个渐近的=（等于）。

一些 f 在 Theta(g) 中，当且仅当它同时在 O(g) 和 Omega(g) 中。

---

现在举个例子。我们有 f(n) = 5n^2。正如你所说，它在 Theta(n^2) 但它在 Theta(n) 中是 而不是 。你的例子是 c = 1 和 n_0 = 0.

此时你的公式错误。大O的定义是

所以 <= 而不是 >=，那就是 Big-Omega。

我们得到

5n^2 <= 1 * n

为了你的价值观，让我们为所有 n >= n_0 = 0:

绘制它

如上所示，对于所有 n >= n_0，f 而不是 小于 1 * g。因此，它不在 O(n).

中

并且由于 Theta 表示 O 和 Omega，如果您不在 O 中，则不能在 Theta 中。