Comparaisons
Notions de complexité temporelle
Quelle est la grande différence entre la vitesse de recherche d'un élément quelconque dans une liste chaînée, un buffer circulaire, un arbre ou une table de hashage ? Evidement, aller chercher un élément dans un buffer circulaire est beaucoup plus rapide que pour une table de hashage, mais les deux méthodes ont un point commun : leur vitesse est a peu près indépendante du nombre d'éléments se trouvant dans les structures. Pour le buffer, c'est tout le temps exact, pour la table de hashage, c'est presque tout le temps exact.
Par contre, pour un arbre, la vitesse sera souvent dépendante du logarithme en base 2 du nombre d'éléments, et dans les cas vraiment mal fichus (voir l'exemple de l'ordre alphabétique), ça dépendra directement du nombre d'éléments. De même que pour une liste chaînée, la vitesse pour aller chercher un élément quelconque dépendra linéairement du nombre d'éléments se trouvant dans cette liste.
La complexité temporelle, c'est ça. On se fiche bien de la vitesse « au chronomètre » de la routine, mais bien du rapport entre sa vitesse et le nombre d'éléments (on dit aussi la taille de la donnée). Bref, pour une liste : « si je double le nombre d'éléments, je divise par deux la vitesse de recherche », tandis que pour une table de hashage, « si je double le nombre d'éléments, la vitesse reste grosso-modo la même ». Bien sûr, pour un nombre d'élément petit, il vaut mieux avoir une liste, même si sa complexité est plus grande. Mais ici, on s'intéresse à un nombre très grand d'éléments, et la conclusion arrive rapidement, il vaut mieux avoir un arbre en basic qu'une liste chaînée optimisée en assembleur : le premier sera plus rapide C'est ainsi que la complexité est une bonne mesure de la rapidité d'un algorithme, bien plus que de ses éventuelles optimisations dans tel ou tel langage ou processeur.
Complexité moyenne et complexité worst-case
Comme je l'ai déjà laissé entendre, il y a deux complexités : la complexité « qu'on verra en pratique », c'est à dire moyenne, et la complexité « dans le pire des cas ». Si vous vous occupez à travailler sur un système réactif en temps réel dans un mécanisme de contrôle de pilote automatique d'un avion, il est clair que la complexité « dans le pire des cas » vous intéresse beaucoup : si une fois sur vingt mille le truc met 40fois plus de temps qu'en moyenne pour exécuter une action, vous prenez des risques, même si c'est rare. Dans un programme « normal », on s'en fiche de ce cas sur vingt mille, et la complexité moyenne sera considéré comme « la » complexité.
Je vais faire un tableau récapitulatif des complexités moyennes et worst-case de chaque structures vues dans ce tutoriel, histoire que vous puissiez choisir en connaissance de cause.
Tableaux non cycliques :Actions :
- Rajouter un élément à la fin : Indépendant
- Rajouter un élément n'importe où : Linéaire
- Supprimer un élément : Linéaire
- Retourner un élément via un indice : Indépendant
- Retourner un élément via une clé: Linéaire
- Possibilité de changer la taille dynamiquement. (complexité linéaire)
- Accès immédiat via indice
- A part la rajout à la fin, les opérations de modifications sont linéaires.
Actions :
- Rajouter un élément à la fin : Indépendant
- Rajouter un élément n'importe où : Linéaire
- Supprimer le premier élément : Indépendant
- Supprimer un élément n'importe où : Linéaire
- Retourner un élément via un indice : Indépendant
- Retourner un élément via une clé : Linéaire
- Par rapport aux tableaux non cyclique, la suppression du premier élément est immédiate.
- Pas moyen de changer la taille dynamiquement.
Actions :
- Rajouter un élément au début : Indépendant
- Rajouter un élément n'importe où : Indépendant si on connaît l'élément précédant, linéaire sinon
- Supprimer un élément au début : Indépendant
- Supprimer un élément n'importe où : Indépendant si on connaît l'élément précédant, linéaire sinon
- Retourner un élément : Linéaire
- La taille n'a pas à être fixée à l'avance
- Insertion et suppressions très rapides si on connaît les éléments adjacents
- Accès linéaires.
Actions :
- Rajouter un élément : Logarithmique en moyenne, linéaire dans le pire des cas
- Supprimer un élément : Logarithmique en moyenne, linéaire dans le pire des cas
- Retourner un élément : Logarithmique en moyenne, linéaire dans le pire des cas
- Complexité toujours logarithmique en moyenne.
- La complexité est linéaire dans le pire des cas, sauf si on utilise un algorithme de rééquilibrage
Actions :
- Rajouter un élément : Indépendant en moyenne, linéaire dans le pire des cas
- Supprimer un élément : Indépendant en moyenne, linéaire dans le pire des cas
- Retourner un élément : Indépendant en moyenne, linéaire dans le pire des cas
- Complexité linéaire en moyenne
- Il faut trouver une bonne fonction de hashage, sinon le complexité devient linéaire
- Linéaire dans le pire des cas (n'arrive vraiment jamais si bonne fonction de hashage)