f（n）=Θ（f（n））是真的嗎？

Question

你能證明自反性f（n）等於大的Theta（f（n））嗎？考慮它時，它似乎是直截了當的，因爲f（n）本身是有界的。但是我怎麼寫這個呢？這是否適用於大歐米茄和大O

Answer 1

我相信你正打算要問的是（w.r.t. @emory：的回答）是沿着線的東西：「對於一些功能f(n)，是不是真的f ∈ ϴ(f(n))」

如果你是從Big-Θ符號的正式定義中發現的，則很明顯這是成立的。

---

f ∈ ϴ(g(n))

⇨對於一些正的常數c1，c2，並n0，以下成立：

c1 · |g(n)| ≤ |f(n)| ≤ c2 · |g(n)|, for all n ≥ n0   (+) 

讓f(n)一些任意實值函數。設置g(n) = f(n)並選擇，例如，c1=0.5,c2=2和n0 = 1。然後，自然，(+)認爲：

0.5 · |f(n)| ≤ |f(n)| ≤ 2 · |f(n)|, for all n ≥ 1 

因此，f ∈ ϴ(f(n))成立。

Answer 2

不，我們不能，因爲它不是真的。 ϴ(f(n))是一組。 f(n)是該集合的成員。 f(n)+1也是該集合的成員。