9. Analyse du Temps Logarithmique : O(log N)

O(log N) est extrêmement efficace. Cela signifie qu'à mesure que la taille de l'entrée (N) augmente, le nombre d'opérations nécessaires augmente très lentement.

Qu'est-ce que la Croissance Logarithmique ?

Les algorithmes logarithmiques fonctionnent en divisant continuellement la taille du problème par deux (ou une fraction) à chaque étape. Si vous avez 1024 éléments, vous n'avez besoin que de 10 étapes pour réduire le problème à la taille 1 (puisque 2^10 = 1024).

La Puissance de O(log N)

• N = 1 000 000
• O(N) = 1 000 000 opérations.
• O(log N) ≈ 20 opérations.

Exemple : Binary Search

L'exemple le plus célèbre est la Binary Search (recherche binaire) (couverte en détail plus tard). Si vous recherchez un nom dans un annuaire téléphonique massif et alphabétisé, vous l'ouvrez au milieu. Vous éliminez immédiatement la moitié de l'annuaire. Vous répétez ce processus, coupant l'espace de problème restant en deux jusqu'à ce que vous trouviez le nom.