Ressources de référence

Aide-mémoire rapide sur la complexité des opérations des structures de données

Structure de donnéesInsérerDeleteRechercherParcours
TableauO(n) milieu / O(1) finO(n) milieu / O(1) finO(1) par index / O(n) par valeurO(n)
Liste simplement chaînéeO(1) tête / O(n) queueO(1) tête / O(n) position spécifiéeO(n)O(n)
Liste doublement chaînéeO(1) (position connue)O(1) (position connue)O(n)O(n)
PileO(1)O(1)——
FileO(1)O(1)——
File de priorité (Tas)O(log n)O(log n)——
Arbre binaire (BST)O(log n)~O(n)O(log n)~O(n)O(log n)~O(n)O(n)
Table de hachageO(1) en moyenneO(1) en moyenneO(1) en moyenne—
TasO(log n)O(log n)O(1) sommet du tas—
GrapheO(1) liste d'adjacenceO(E)O(V+E) DFS/BFSO(V+E)

Référence rapide des algorithmes de tri

AlgorithmeComplexité moyenneComplexité dans le pire des casEspaceStableEn une ligne
Tri à bullesO(n²)O(n²)O(1)OuiSimple mais lent, adapté à l'enseignement
Tri par sélectionO(n²)O(n²)O(1)nonMinimum d'échanges
InsertionO(n²)O(n²)O(1)OuiOptimal pour les petites quantités de données ou les données presque triées
Tri rapideO(n log n)O(n²)O(log n)nonPremier choix universel, idée de partitionnement astucieuse
Tri fusionO(n log n)O(n log n)O(n)OuiPerformance stable mais nécessite de l'espace supplémentaire
Tri par tasO(n log n)O(n log n)O(1)nonTri en place, espace optimal
Tri de ShellO(n^1.3)O(n²)O(1)nonVersion améliorée du tri par insertion

Classement des complexités Big O

Complexitén=10n=1000n=1000000Évaluation
O(1)111Optimal
O(log n)~3~10~20Excellent
O(n)1010001000000Acceptable
O(n log n)~30~10000~20000000Passable
O(n²)100100000010¹²Soyez prudent
O(2ⁿ)1024Nombre astronomiqueImpossibleInutilisable

Ressources d'apprentissage recommandées

TypeNameDescription
Manuel classique"Structures de données (édition en langage C)" de Yan WeiminManuel standard pour les universités nationales, système complet
Manuel classique"Introduction à l'algorithmique" (CLRS)Référence faisant autorité dans le domaine des algorithmes, approfondie et systématique
Pratique en ligneLeetCode (leetcode.com)Une multitude de problèmes d'algorithmes, choix privilégié pour la pratique des entretiens
Pratique en ligneNowcoder (nowcoder.com)Plateforme nationale d'entraînement aux entretiens, adaptée à la préparation aux recrutements universitaires
Outil de visualisationVisualgo (visualgo.net)Visualisation d'algorithmes, aide à comprendre le processus d'exécution
Compilateur en ligneCompiler Explorer (godbolt.org)Voir l'assembleur après la compilation du code C, comprendre les détails sous-jacents
Autres extensions