Logarithme itéré

Fonction mathématique

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.

La figure présente la courbe du logarithme népérien. On a log 4 = 1.38, puis en reportant la valeur sur l'axe des abscisses par zig zag, on a log 1.38 = 0.32. On a appliqué le logarithme deux fois, donc log* 4 = 2 pour le logarithme itéré en base e.

Définition

modifier

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

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

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

Si est dans l'intervalle... Alors vaut :
0
1
2
3
4
5

Propriétés

modifier

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].

Utilisations

modifier

Notes et références

modifier
  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)