时间复杂性与时间复杂性证明

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     ∀n>n₀∈(G)⇔∃k，n₀∈ℕ⇔∃≤

f∈(g)⇔∃k，n₀∈ℕ⇔∃k.g(n)≤f(n)

f∈(g)⇔∃k₁，k₂，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 )：

你能证明lim _ 2^(n+1)/ ( 3^n/n )=0当x→+∞？

如果是这样的话，您证明了对于所有的ε>0都存在这样的δ，使得对于所有n>δ，我们都有2^(n+1)/(3^n/n)<ε

对于ε=2，存在n个₀，使得对于所有n>n₀2^(n+1)<2.3^n/n

你能得出什么结论？