Complexité des algorithmes

Chaque algorithme a sa propre complexité, qui peut être exprimée en notation mathématique. Cette vue d'ensemble montre la complexité typique des algorithmes en fonction de la taille des données d'entrée (c'est-à-dire le nombre d'éléments avec lesquels ils travaillent) et quels types d'algorithmes sont adaptés à quel type de tâche.

En général, il existe un meilleur algorithme spécialisé pour chaque type de problème. Aucun algorithme n'est universellement le meilleur, et vous devez toujours connaître votre contexte.

Notation du grand O

La notation Big O est utilisée pour classer les algorithmes en fonction de l'augmentation de leur temps d'exécution ou de leurs besoins en mémoire lorsque la taille de l'entrée augmente.

Le tableau suivant montre les ordres de croissance les plus courants des algorithmes spécifiés en notation Big O.

Vous trouverez ci-dessous une liste de quelques-unes des notations Big O les plus couramment utilisées ainsi qu'une comparaison de leurs performances pour différentes tailles de données d'entrée.

Complexité des opérations sur les structures de données

| Structure de données | Accès | Recherche | Insertion | Suppression | Commentaire | ... | ----------------------- | :------- : | :------- : | :------- : | :------- : | :-------- | | Array | 1 | n | n | n | n | n | n | | 1 | Stack | n | n | n | n | 1 | 1 | | | | Queueue | n | n | n | 1 | | | | | | Liste de liens** | n | n | n | n | 1 | n | n | Table de hachage | - | n | n | n | n | n | Dans le cas d'une fonction de hachage parfaite, la complexité sera O(1) |. | Dans le cas d'un arbre équilibré, la complexité sera O(log(n)). | B-Tree | log(n) | log(n) | log(n) | log(n) | log(n) | log(n) | log(n) | | | Arbre rouge-noir | log(n) | log(n) | log(n) | log(n) | log(n) | | | | | Arbre AVL | log(n) | log(n) | log(n) | log(n) | log(n) | log(n) | log(n) | | | Filtre Bloom | - | 1 | 1 | - | Lors de la recherche de faux positifs |

Complexité des algorithmes de tri

| Nom de l'algorithme | Meilleur | Moyen | Pire | Mémoire | Stable ? | Commentaire | | --------------------- | :------------- : | :----------------- : | :----------------- : | :------- : | :------- : | :-------- | | Tri à bulles | n | n² | n² | 1 | Oui | | | | Tri par insertion | n | n² | n² | 1 | | | | | | | Tri sélectif | n² | n² | n² | 1 | | | | | | | Tri de tas | n log(n) | n log(n) | n log(n) | 1 | | | Non | | | Tri de fusion | n log(n) | n log(n) | n log(n) | n | Oui | | | | Tri rapide | n log(n) | n log(n) | n² | log(n) | Non | Le tri rapide est généralement exécuté avec une complexité de pile O(log(n)). | | Tri de coquille | n log(n) | dépend de la séquence | n&nbsp ;(log(n))² | 1 | | Non | | | Tri par comptage | n + r | n + r | n + r | n + r | Oui | r - le plus grand nombre dans le tableau | | Tri de Radix | n * k | n * k | n * k | n + k | Oui | k - longueur de la clé la plus longue |

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt