Ressources de référence
Aide-mémoire rapide sur la complexité des opérations des structures de données
| Structure de données | Insérer | Delete | Rechercher | Parcours |
|---|---|---|---|---|
| Tableau | O(n) milieu / O(1) fin | O(n) milieu / O(1) fin | O(1) par index / O(n) par valeur | O(n) |
| Liste simplement chaînée | O(1) tête / O(n) queue | O(1) tête / O(n) position spécifiée | O(n) | O(n) |
| Liste doublement chaînée | O(1) (position connue) | O(1) (position connue) | O(n) | O(n) |
| Pile | O(1) | O(1) | — | — |
| File | O(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 hachage | O(1) en moyenne | O(1) en moyenne | O(1) en moyenne | — |
| Tas | O(log n) | O(log n) | O(1) sommet du tas | — |
| Graphe | O(1) liste d'adjacence | O(E) | O(V+E) DFS/BFS | O(V+E) |
Référence rapide des algorithmes de tri
| Algorithme | Complexité moyenne | Complexité dans le pire des cas | Espace | Stable | En une ligne |
|---|---|---|---|---|---|
| Tri à bulles | O(n²) | O(n²) | O(1) | Oui | Simple mais lent, adapté à l'enseignement |
| Tri par sélection | O(n²) | O(n²) | O(1) | non | Minimum d'échanges |
| Insertion | O(n²) | O(n²) | O(1) | Oui | Optimal pour les petites quantités de données ou les données presque triées |
| Tri rapide | O(n log n) | O(n²) | O(log n) | non | Premier choix universel, idée de partitionnement astucieuse |
| Tri fusion | O(n log n) | O(n log n) | O(n) | Oui | Performance stable mais nécessite de l'espace supplémentaire |
| Tri par tas | O(n log n) | O(n log n) | O(1) | non | Tri en place, espace optimal |
| Tri de Shell | O(n^1.3) | O(n²) | O(1) | non | Version améliorée du tri par insertion |
Classement des complexités Big O
| Complexité | n=10 | n=1000 | n=1000000 | Évaluation |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | Optimal |
| O(log n) | ~3 | ~10 | ~20 | Excellent |
| O(n) | 10 | 1000 | 1000000 | Acceptable |
| O(n log n) | ~30 | ~10000 | ~20000000 | Passable |
| O(n²) | 100 | 1000000 | 10¹² | Soyez prudent |
| O(2ⁿ) | 1024 | Nombre astronomique | Impossible | Inutilisable |
Ressources d'apprentissage recommandées
| Type | Name | Description |
|---|---|---|
| Manuel classique | "Structures de données (édition en langage C)" de Yan Weimin | Manuel 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 ligne | LeetCode (leetcode.com) | Une multitude de problèmes d'algorithmes, choix privilégié pour la pratique des entretiens |
| Pratique en ligne | Nowcoder (nowcoder.com) | Plateforme nationale d'entraînement aux entretiens, adaptée à la préparation aux recrutements universitaires |
| Outil de visualisation | Visualgo (visualgo.net) | Visualisation d'algorithmes, aide à comprendre le processus d'exécution |
| Compilateur en ligne | Compiler Explorer (godbolt.org) | Voir l'assembleur après la compilation du code C, comprendre les détails sous-jacents |