Complexité des algorithmes et algorithmes de tri

Notations O, Ω et Θ, calcul de la complexité des boucles et des fonctions récursives, recherche dichotomique, tris par sélection, insertion, fusion, rapide et par tas, borne inférieure des tris par comparaison.

Acheter · 0,99 €

Aperçu du PDF · 8 pages

+ 6 pages

Sommaire détaillé

01Mesurer la complexitélire l'aperçu ↓
- 1.1 Ce que l'on mesure
- 1.2 Les notations asymptotiques
- 1.3 Les classes usuelles
02Calculer une complexité
- 2.1 Les structures itératives
- 2.2 Les algorithmes récursifs
03Rechercher un élément
04Les algorithmes de tri
- 4.1 Les tris quadratiques
- 4.2 Les tris en $n \log n$
- 4.3 Les notions à maîtriser
- 4.4 La borne inférieure des tris par comparaison
05Méthode, pièges et sujets
- 5.1 Pour analyser un algorithme
- 5.2 Les pièges
- 5.3 Sujets probables

Aperçu gratuit — la première partie en entier

1Mesurer la complexité

1.1Ce que l'on mesure

On ne compte pas des secondes, qui dépendent de la machine : on compte des opérations, et l'on s'intéresse à leur ordre de grandeur quand $n$ devient grand.

Cas	Définition	Exemple : recherche séquentielle d'un élément dans un tableau
Pire cas	Le maximum d'opérations sur toutes les entrées de taille $n$	L'élément est absent ou en dernière position : $n$ comparaisons
Meilleur cas	Le minimum	L'élément est en première position : 1 comparaison
En moyenne	L'espérance, pour une distribution donnée des entrées	Élément présent, position uniforme : environ $n/2$ comparaisons

1.2Les notations asymptotiques

Notation	Définition	Lecture
$f(n) = O(g(n))$	Il existe $c > 0$ et $n_0$ tels que $f(n) \le c\, g(n)$ pour tout $n \ge n_0$	$f$ croît au plus comme $g$ (borne supérieure)
$f(n) = \Omega(g(n))$	Il existe $c > 0$ et $n_0$ tels que $f(n) \ge c\, g(n)$ pour tout $n \ge n_0$	$f$ croît au moins comme $g$ (borne inférieure)
$f(n) = \Theta(g(n))$	$f = O(g)$ et $f = \Omega(g)$	$f$ croît exactement comme $g$ , à une constante près

1.3Les classes usuelles

Classe	Nom	Exemple	Pour $n = 10^6$ , ordre de grandeur
$\Theta(1)$	Constante	Accès à une case de tableau	1
$\Theta(\log n)$	Logarithmique	Recherche dichotomique	20
$\Theta(n)$	Linéaire	Parcours d'un tableau, recherche du maximum	$10^6$
$\Theta(n \log n)$	Quasi linéaire	Tri fusion, tri par tas	$2 \times 10^7$
$\Theta(n^2)$	Quadratique	Tri par sélection, double boucle	$10^{12}$
$\Theta(n^3)$	Cubique	Produit naïf de matrices	$10^{18}$
$\Theta(2^n)$	Exponentielle	Énumération de tous les sous-ensembles	Inaccessible

Schéma

La suite : 4 parties, 8 pages en tout

Calculer une complexité · Rechercher un élément · Les algorithmes de tri · Méthode, pièges et sujets

Débloquer · 0,99 €

Les notions de cette fiche

Sources vérifiées

T. H. Cormen, C. E. Leiserson, R. L. Rivest et C. Stein, Algorithmique, Dunod (trad. de Introduction to Algorithms, MIT Press)
D. E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, Addison-Wesley
C. A. R. Hoare, « Quicksort », The Computer Journal, 1962