Exercices : Complexités d'algorithmes
Exercice 3 : Temps d'un algorithme T(n)
Donner les relations d'inclusion entre les ensembles suivants :
- $$O(n \log n)$$,
- $$O(2^n)$$,
- $$O(\log n)$$,
- $$O(1)$$,
- $$O(n^2)$$,
- $$O(n^3)$$,
- $$O(n)$$.
Considérer les deux algorithmes A1 et A2 avec leurs temps d'exécution :
- $$T_1(n) = 9n^2$$
- $$T_2(n) = 100n + 96$$
Déterminer la complexité asymptotique des deux algorithmes dans la notation Grand-O. Quel algorithme a la meilleure complexité asymptotique?
Montrer que vos solutions sont correctes en spécifiant un c et un n0 par algorithme afin que la relation suivante soit satisfaite :
$$O(f) = \{g | \exists c > 0 : \exists n_0 > 0 : \forall n \geq n_0 : g(n) \leq cf(n)\}$$
Exercice 4 : Notation de Landau, Analyse des Algorithmes & Complexités
- Montrer que $$O(f(n) + g(n)) = O(\max(f(n), g(n)))$$.
- Montrer que si $$f(n) \in O(g(n))$$, alors $$S(n) + T(n) \in O(g(n))$$.
- Montrer que $$S(n) \cdot T(n) \in O(f(n) \cdot g(n))$$.
- Soit $$f(x) = 7x^2$$ et $$g(x) = x^3$$.
- Soit $$f(n) = \log_2(n)$$ et $$g(n) = n$$.
- Soit $$f(n) = 2^n$$ et $$g(n) = 3^n$$.
- Pour chacun des algorithmes suivants, indiquer (en mots) quelle est la sortie de l'algorithme et (en notation de Landau) quelle est sa complexité (temporelle pire cas).