Logaritmo iterado

Un logaritmo iterado en matemáticas e informática se define como una función entera igual al número de logaritmos iterativos del argumento requerido para que el resultado sea menor o igual a 1 . Esta función está definida para todos los números positivos, pero en las aplicaciones el argumento suele ser un número natural . Un logaritmo iterado más estrictamente se define mediante la fórmula recursiva: ${\ estilo de visualización \ registro ^ {*} n}$

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

El logaritmo iterado se define para las bases A073229 . Si es positivo , entonces la secuencia recursiva que lo define converge a un número mayor que 1. En informática se suele utilizar el logaritmo binario iterado. $b>e^{1/e}\aprox. 1{,}444667$ ${\ Displaystyle b<e^{1/e))$

Esta función crece indefinidamente, pero extremadamente lentamente. Para todos los argumentos concebibles en la práctica, podría reemplazarse por una constante, pero para fórmulas definidas en todo el eje numérico, tal notación sería errónea. Los valores del logaritmo binario iterado para todos los argumentos interesantes en la práctica no superan los 5 y se dan a continuación.

norte	${\ estilo de visualización \ registro _ {2} ^ {*} n}$
(−∞, 1]	0
(12]	una
(2, 4]	2
(4, 16]	3
(16, 65536]	cuatro
(65536, 2 65536 (~10 19660 ))	5

Aplicación

El logaritmo iterado surge en el análisis de algunos algoritmos en estimaciones de su complejidad computacional [5][4][3]]2 []1[ - [6] $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $norte$ $O(\log ^{*}n)$

Notas

↑ Olivier Devillers, "La aleatorización produce algoritmos O(n log* n) simples para problemas difíciles de ω(n)". Revista Internacional de Geometría Computacional y Aplicaciones 2:01 (1992), pp. 971-11.
↑ Noga Alon y Yossi Azar, "Encontrar un máximo aproximado". SIAM Journal of Computing 18 :2 (1989), págs. 2582-67.
↑ Sobre separadores, segregadores y tiempo versus espacio . Consultado el 31 de agosto de 2015. Archivado desde el original el 25 de junio de 2012. (indefinido)
↑ Robert Sedgewick-Robert Sedgewick . Consultado el 31 de agosto de 2015. Archivado desde el original el 8 de marzo de 2021. (indefinido)
↑ Schneider, J. (2008), Un algoritmo conjunto independiente máximo distribuido log-star para gráficos con límites de crecimiento , Actas del simposio sobre principios de computación distribuida Archivado el 30 de julio de 2013 en Wayback Machine .
↑ Richard Cole y Uzi Vishkin: "Lanzamiento de moneda determinista con aplicaciones para la clasificación óptima de listas paralelas", Information and Control 70:1 (1986), págs. 325-3.