Logarithme itéré

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

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

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

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

• Portail de l'analyse
• Portail de l'informatique théorique