Logarithme itéré

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.

En informatique, le logarithme itéré d'un nombre n, noté ${\displaystyle \log ^{*}(n)}$ (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.

Définition

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

${\displaystyle \log _{b}^{*}n:={\begin{cases}0&{\mbox{si }}n\leq 1;\\1+\log _{b}^{*}(\log _{b}n)&{\mbox{si }}n>1.\end{cases}}}$

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

${\displaystyle \log _{e}^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil }$

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

Si ${\displaystyle x}$ est dans l'intervalle...	Alors ${\displaystyle \log _{2}^{*}x}$ vaut :
${\displaystyle ]-\infty ;1]}$	0
${\displaystyle ]1,2]}$	1
${\displaystyle ]2,4]}$	2
${\displaystyle ]4,16]}$	3
${\displaystyle ]16,65536]}$	4
${\displaystyle ]65536,2^{65536}]}$	5

Propriétés

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

• Cette fonction est utilisée pour l'analyse d'algorithmes, par exemple pour exprimer la complexité de l'algorithme de triangulation de Delaunay et en algorithmique distribuée, par exemple dans la borne inférieure de Linial pour la coloration de graphe^[2].
• Dasgupta et al., dans leur livre d'algorithmique, présente une analyse de complexité amortie de la structure de données union-find en utilisant le logarithme itéré^[3].
• Le logarithme itéré intervient dans la complexité de l'algorithme de Fürer.

Notes et références

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