Complexité temporelle et preuve de complexité temporelle

Question

Qu'est-ce qui est vrai et lequel est faux? Je ne peux pas vraiment décider lequel est vrai et lequel faux. Peut-être dans les 3 premiers cas.

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)

et comment prouver celui-ci:

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

Answer 1

Retour aux définitions, avec f et g deux fonctions positives:

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)

Il est facile de voir que: f∈ (g) et f∈ (g) implique f∈ (g)

---

L'utilisation de ces définitions, il est facile de prouver que 1,3,5,6 sont vraies et que 2 et 7 sont faux; alors 1 et 5 vrai implique 4 vrai.

---

pour 2^(n + 1) ∈ O (3^n/n):
peut prouver lim 2^(n + 1)/(3^n/n) = 0 lorsque x → + ∞?
Si oui, vous avez prouvé que pour tout ε> 0 il existe δ tel que pour tout n> δ nous avons 2^(n + 1)/(3^n/n) < ε
Pour ε = 2, il y a existe n₀ tel que pour tout n> n₀ 2^(n + 1) < 2,3^n/n
que pouvez-vous conclure?