complexity-theory - 时间复杂度和时间复杂度证明

Question

哪个是真的，哪个是假的？我无法确定哪个是真的，哪个是假的。也许在前 3 种情况下。

1. 3n^5 − 16n + 2 ∈ O(n^5)
2. 3n^5 − 16n + 2 ∈ O(n)
3. 3n^5 − 16n + 2 ∈ O(n^17)
4. 3n^5 − 16n + 2 ∈ Ω(n^5)
5. 3n^5 − 16n + 2 ∈ Θ(n^5)
6. 3n^5 − 16n + 2 ∈ Θ(n)
7. 3n^5 − 16n + 2 ∈ Θ(n^17)

以及如何证明这一点：

2^(n+1) ∈ O(3^n/n )

Answer 1

回到定义，f 和 g 有两个正函数：

f∈(g) ⇔ ∃k,n₀∈ℕ ∀n>n₀ f(n) ≤ kg(n)
f∈(g) ⇔ ∃k,n₀∈ℕ ∀n>n₀ kg(n) ≤ f(n)
f∈(g) ⇔ ∃k₁,k₂,n₀∈ℕ ∀n>n₀ k₁.g(n) ≤ f(n) ≤ k₂.g(n)

很容易看出： f∈(g) 和 f∈ (g) 蕴含 f∈(g)

---

使用这些定义很容易证明 1、3、5、6 为真，而 2 和 7 为假；那么 1 和 5 为真意味着 4 为真。

---

对于 2^(n+1) ∈ O(3^n/n ) ：
当 x→+∞ 时，你能证明 lim 2^(n+1)/ ( 3^n/n ) = 0 吗？
如果是这样，你证明了对于所有 ε>0 存在 δ 使得对于所有 n>δ 我们有 2^(n+1)/(3^n/n)<ε
对于 ε=2，存在 n₀ 使得对于所有 n>n₀ 2^(n+1)<2.3^n/n
你能得出什么结论？