À retenir
- C'est l'opération inverse de la puissance de 2.
- Il mesure l'efficacité des algorithmes qui divisent le travail par deux à chaque étape.
- Il permet de calculer le nombre de bits nécessaires pour représenter un nombre de valeurs données.
Le logarithme binaire est un outil mathématique qui permet de déterminer combien de fois un nombre peut être divisé par 2 avant d'arriver à 1. C'est l'inverse exact de la puissance de 2 : par exemple, comme 2 puissance 3 (2x2x2) égale 8, le logarithme binaire de 8 est 3. On peut l'imaginer comme le nombre de fois qu'il faut plier une feuille en deux pour obtenir un certain nombre d'épaisseurs.
Étymologie
Le mot « logarithme » vient du grec logos (rapport ou raison) et arithmos (nombre). L'adjectif « binaire » est issu du latin binarius (qui contient deux éléments). En informatique, on utilise souvent l'abréviation lb ou log2 pour le désigner.
Exemples d'usage
- Recherche dans un annuaire : Si vous cherchez un nom dans un dictionnaire de 1 000 pages en coupant toujours le livre en deux (méthode par dichotomie), vous trouverez la page en maximum 10 étapes, car le logarithme binaire de 1 000 est environ 10.
- Stockage mémoire : Pour coder 16 couleurs différentes, il faut 4 bits par pixel, car
log2(16) = 4.
Cas d'usage
Il est fondamental pour calculer la complexité des algorithmes : il permet de savoir si un programme restera rapide face à une grande quantité de données. On l'utilise aussi en théorie de l'information pour mesurer la quantité de données (entropie) et dans l'organisation des fichiers sur un disque dur.
Bonnes pratiques
En développement, préférez utiliser la fonction spécifique log2() fournie par votre langage de programmation plutôt qu'une formule de conversion générale (comme log(x)/log(2)), car elle est souvent plus rapide et plus précise au niveau du processeur. Comprendre ce concept aide à choisir les meilleures structures de données, comme les arbres binaires équilibrés.
Synonymes
Antonymes
Conseil
Retenez cette règle simple : chaque fois que vous doublez la taille de vos données, le logarithme binaire n'augmente que de 1. C'est pour cela que les algorithmes basés sur le logarithme (comme le tri rapide ou la recherche dichotomique) sont extrêmement performants, même sur des milliards d'informations.
Questions fréquentes
Pourquoi est-ce si important en informatique ?
Parce que les ordinateurs fonctionnent en binaire (0 ou 1). Le logarithme binaire est donc l'unité naturelle pour mesurer l'information et l'efficacité des calculs.
Quelle est la différence avec le logarithme classique ?
Le logarithme classique (décimal) utilise la base 10, alors que le binaire utilise la base 2. Le principe est le même, seule l'échelle change.
Un logarithme binaire peut-il être décimal ?
Oui, si le nombre n'est pas une puissance parfaite de 2. Par exemple, le logarithme binaire de 10 est environ 3,32 bits.