Logarithme itéré

En informatique, le logarithme itéré d'un nombre n, noté (lu "log star" ou "log étoile"), est le nombre de fois que le logarithme doit lui être appliqué avant que le résultat soit inférieur ou égal à 1. Cette fonction est utilisée pour décrire la complexité de certains algorithmes, notamment en algorithmique distribuée.

Graphique montrant le logarithme itéré

DéfinitionModifier

Le logarithme itéré de base b peut être défini par :

 

Sur les nombres réels positifs, le super-logarithme (en) continu (l'inverse de la tétration) est essentiellement équivalente :

 

Le tableau suivant donne les valeurs du logarithme itéré (en base 2) :

   
  0
  1
  2
  3
  4
  5

PropriétésModifier

Cette fonction croît extrêmement lentement. Une fonction usuelle en informatique théorique qui croît encore plus lentement est la réciproque de la fonction d'Ackermann. Ces deux fonctions sont d'ailleurs liées, puisque le logarithme itéré est l'un des niveaux de la hiérarchie de la réciproque d'Ackermann[1].

UtilisationsModifier

Notes et référencesModifier

  1. Gabriel Nivasch, « Inverse Ackermann without pain », .
  2. Référence de l'article de Linial : (en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, no 1,‎ , p. 193-201.
  3. Sanjoy Dasgupta, Christos H. Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill, Inc., (ISBN 0073523402 et 9780073523408, lire en ligne)