En informática , el logaritmo iterado de, registro escrito * (normalmente se lee " log star "), es el número de veces que la función logaritmo debe aplicarse iterativamente antes de que el resultado sea menor o igual a. La definición formal más simple es el resultado de esta relación de recurrencia :
En los números reales positivos , el superlogaritmo continuo ( tetración inversa ) es esencialmente equivalente:
es decir, el logaritmo iterado en base b es si n se encuentra dentro del intervalo , dónde denota tetración. Sin embargo, en los números reales negativos, log-star es, mientras que por positivo , por lo que las dos funciones difieren para argumentos negativos.
El logaritmo iterado acepta cualquier número real positivo y produce un número entero . Gráficamente, puede entenderse como el número de "zig-zags" necesarios en la Figura 1 para alcanzar el intervaloen el eje x .
En informática, lg * se utiliza a menudo para indicar el logaritmo binario iterado , que itera el logaritmo binario (con base) en lugar del logaritmo natural (con base e ).
Matemáticamente, el logaritmo iterado está bien definido para cualquier base mayor que , no solo para la base y base e .
Análisis de algoritmos
El logaritmo iterado es útil en el análisis de algoritmos y complejidad computacional , apareciendo en los límites de complejidad temporal y espacial de algunos algoritmos como:
- Encontrar la triangulación de Delaunay de un conjunto de puntos conociendo el árbol de expansión mínimo euclidiano : tiempo O ( n log * n ) aleatorio . [1]
- Algoritmo de Fürer para la multiplicación de enteros: O ( n log n 2 O (lg * n ) ).
- Encontrar un máximo aproximado (elemento al menos tan grande como la mediana): lg * n - 4 a lg * n + 2 operaciones paralelas. [2]
- El algoritmo distribuido de Richard Cole y Uzi Vishkin para 3-colorear un n- ciclo : O ( log * n ) rondas de comunicación sincrónica. [3] [4]
- Realización de unión rápida ponderada con compresión de trayectoria. [5]
El logaritmo iterado crece a un ritmo extremadamente lento, mucho más lento que el propio logaritmo. Para todos los valores de n relevantes para contar los tiempos de ejecución de los algoritmos implementados en la práctica (es decir, n ≤ 2 65536 , que es mucho más que el número estimado de átomos en el universo conocido), el logaritmo iterado con base 2 tiene un valor no más de 5.
X | lg * x |
---|---|
(−∞, 1] | 0 |
(1, 2] | 1 |
(2, 4] | 2 |
(4, 16] | 3 |
(16, 65536) | 4 |
(65536, 2 65536 ] | 5 |
Las bases más altas dan logaritmos iterados más pequeños. De hecho, la única función comúnmente utilizada en la teoría de la complejidad que crece más lentamente es la función inversa de Ackermann .
Otras aplicaciones
El logaritmo iterado está estrechamente relacionado con la función de logaritmo generalizado que se utiliza en la aritmética de índice de nivel simétrico . También es proporcional a la persistencia aditiva de un número , la cantidad de veces que alguien debe reemplazar el número por la suma de sus dígitos antes de llegar a su raíz digital .
En la teoría de la complejidad computacional , Santhanam [6] muestra que los recursos computacionales DTIME ( tiempo de cálculo para una máquina de Turing determinista ) y NTIME (tiempo de cálculo para una máquina de Turing no determinista ) son distintos hasta
Notas
- ^ Olivier Devillers, "La aleatorización produce algoritmos simples O (n log * n) para problemas difíciles ω (n)". Revista Internacional de Geometría y Aplicaciones Computacionales 2 : 01 (1992), págs. 97-111.
- ^ Noga Alon y Yossi Azar, "Encontrar un máximo aproximado". SIAM Journal on Computing 18 : 2 (1989), págs. 258-267.
- ^ Richard Cole y Uzi Vishkin: "Lanzamiento de moneda determinista con aplicaciones a la clasificación de lista paralela óptima", Información y control 70: 1 (1986), págs. 32-53.
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8. Sección 30.5.
- ^ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
- ^ Sobre separadores, segregadores y tiempo versus espacio
Referencias
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "3.2: Notaciones estándar y funciones comunes". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 55–56. ISBN 0-262-03293-7.