Tri et recherche

Complexité : O(n log n) - drastiquement plus rapide. Pour un million d'éléments, c'est environ 20 millions de comparaisons au lieu d'un billion. C'est ce type d'algorithme qui rend les vrais systèmes d'IA possibles.

Bubble Sort vs Merge Sort à grande échelle

| Éléments | Bubble Sort (O(n²)) | Merge Sort (O(n log n)) | |----------|---------------------|-------------------------| | 100 | 10 000 ops | ~700 ops | | 10 000 | 100 000 000 ops | ~130 000 ops | | 1 000 000 | 1 000 000 000 000 ops | ~20 000 000 ops |

La différence n'est pas théorique - c'est la différence entre « fini en une seconde » et « fini la semaine prochaine ».

Recherche binaire (Binary Search) - L'astuce de l'annuaire

Imaginez chercher « Smith » dans un annuaire. Vous ne commenceriez pas à la page 1 en lisant chaque nom. Vous ouvririez au milieu, verriez où vous en êtes, et sauteriez dans la bonne moitié. Puis vous recommenceriez.

C'est la recherche binaire - et elle ne fonctionne que sur des données triées.

sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

Step 1: Middle = 16 → 23 > 16, search right half
Step 2: Middle = 38 → 23 < 38, search left half
Step 3: Middle = 23 → Found it!

Complexité : O(log n). Dans une liste triée d'un million d'éléments, la recherche binaire trouve n'importe quel élément en 20 étapes maximum. Une recherche linéaire prendrait jusqu'à un million d'étapes.

Comment l'IA utilise le tri et la recherche

Classement des résultats de recherche

Quand Google traite votre requête, il note chaque page pertinente et les trie par pertinence. Les 10 premiers résultats apparaissent en page 1. Sans tri efficace, cela prendrait des minutes.

Systèmes de recommandation

Netflix calcule un « score de correspondance » pour des milliers de titres, puis les trie pour vous montrer les meilleurs en premier. L'algorithme de tri affecte directement ce que vous voyez sur votre écran d'accueil.

K plus proches voisins

Cet algorithme classique d'IA trouve les K éléments les plus similaires à une entrée donnée. Il calcule les distances, puis trie partiellement pour trouver les K plus petites.

Préparation des données d'entraînement

Avant l'entraînement, on trie souvent les données pour créer des lots équilibrés - un mélange d'exemples faciles et difficiles, ou une distribution équilibrée de catégories.

Quand trier vs quand utiliser une hash map

| Scénario | Meilleur choix | Pourquoi | |----------|---------------|----------| | Trouver un élément par clé | Hash map | Recherche en O(1) | | Trouver les 10 meilleurs | Tri | Besoin de résultats ordonnés | | Vérifier l'existence | Hash map | O(1) vs O(log n) | | Obtenir les éléments en ordre | Tri | Les hash maps n'ont pas d'ordre | | Requêtes d'intervalle | Tableau trié + binary search | Les hash maps ne gèrent pas les intervalles |

Points clés à retenir

• Le tri transforme des données chaotiques en données structurées - essentiel pour le classement et les recommandations.
• Les algorithmes O(n²) comme le tri à bulles sont pédagogiques mais impraticables ; les algorithmes O(n log n) comme le tri fusion alimentent les vrais systèmes.
• La recherche binaire est extraordinairement efficace sur les données triées - 20 étapes pour un million d'éléments.
• Choisissez entre tri et hash map selon que vous avez besoin de résultats ordonnés ou de recherches instantanées.