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}

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. Elle apparaît par exemple dans la complexité de l'algorithme de triangulation de Delaunay.

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