Logarithme itéré

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, le logarithme itéré d'un nombre n, noté \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[modifier | modifier le code]

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

\log^* n :=
  \begin{cases}
    0                  & \mbox{si } n \le 1; \\
    1 + \log^*(\log n) & \mbox{si } n > 1.
   \end{cases}


x \log^*x
(−∞, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 265536] 5

Propriétés[modifier | modifier le code]

Cette fonction croît extrêmement lentement. L'une des rares fonctions usuelles en informatique théorique qui croît encore plus lentement est la réciproque de la fonction d'Ackermann[réf. souhaitée].

Utilisations[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. Référence de l'article de Linial : (en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, no 1,‎ 1992, p. 193-201.