Logarithme itéré

Logarithme itéré

En informatique, le logarithme itéré d'un nombre n est le nombre de fois que le logarithme doit lui être appliqué avant que le résultat soit inférieur ou égal à 1. Elle peut ainsi être définie par :

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

Cette fonction est utilisée pour l'analyse d'algorithme. Elle apparaît par exemple dans la complexité de l'algorithme de triangulation de Delaunay.

Cette fonction croît extrêmement lentement. La seule fonction utilisée en théorie de la complexité qui croît encore plus lentement est l'inverse de la fonction d'Ackermann.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Logarithme itéré de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Logarithme Itéré — En informatique, le logarithme itéré d un nombre n est le nombre de fois que le logarithme doit lui être appliqué avant que le resultat soit inférieur ou égal à 1. La plus simple définition formelle est le resultat de cette fonction récursive: ou …   Wikipédia en Français

  • Logarithme itere — Logarithme itéré En informatique, le logarithme itéré d un nombre n est le nombre de fois que le logarithme doit lui être appliqué avant que le resultat soit inférieur ou égal à 1. La plus simple définition formelle est le resultat de cette… …   Wikipédia en Français

  • PROBABILITÉS (CALCUL DES) — Le calcul des probabilités est certainement l’une des branches les plus récentes des mathématiques, bien qu’il ait en fait trois siècles et demi d’existence. Après s’être cantonné dans l’étude des jeux de hasard, il s’est introduit dans presque… …   Encyclopédie Universelle

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Théorie de la complexité des algorithmes — Pour les articles homonymes, voir Théorie de la complexité. La théorie de la complexité des algorithmes étudie formellement la quantité de ressources (en temps et en espace) nécessitée par l exécution d un algorithme ainsi que la difficulté… …   Wikipédia en Français

  • NOMBRES (THÉORIE DES) - Théorie analytique — Ce qu’on appelle la «théorie analytique des nombres» ne peut pas être considéré comme une théorie mathématique au sens usuel qu’on donne à ces mots, c’est à dire un système organisé de définitions et de théorèmes généraux accompagné… …   Encyclopédie Universelle

  • Algorithme de Fürer — L algorithme de Fürer est un algorithme de multiplication de très grands entiers. L algorithme a été publié par Martin Fürer de Penn State en 2007[1]. Cet algorithme possède asymptotiquement la plus faible complexité parmi les algorithmes de… …   Wikipédia en Français

  • Liste Des Lois Scientifiques — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom de la loi comprend des noms de scientifiques, on se base sur le premier nom propre cité. Si le nom de la loi ne comprend pas de… …   Wikipédia en Français

  • Liste des lois scientifiques — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom de la loi comprend des noms de scientifiques, on se base sur le premier nom propre cité. Si le nom de la loi ne comprend pas de… …   Wikipédia en Français

  • Loi scientifique — Liste des lois scientifiques Liste des lois scientifiques par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom de la loi comprend des noms de scientifiques, on se base sur le premier… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”