stringtranslate.com

Logaritmo iterado

Figura 1. Demostración de log* 4 = 2 para el logaritmo iterado en base e. El valor del logaritmo iterado se puede encontrar haciendo un "zigzag" sobre la curva y = log b (x) desde la entrada n hasta el intervalo [0,1]. En este caso, b = e. El zigzag implica comenzar desde el punto (n, 0) y moverse iterativamente hasta (n, log b (n) ), hasta (0, log b (n) ), hasta (log b (n), 0 ).

En informática , el logaritmo iterado de , escrito log*  (normalmente se lee " log star "), es el número de veces que se debe aplicar iterativamente la función logaritmo antes de que el resultado sea menor o igual a . [1] La definición formal más simple es el resultado de esta relación de recurrencia :

En informática, lg * se utiliza a menudo para indicar el logaritmo iterado binario , 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 base y base e . La función "superlogaritmo" es "esencialmente equivalente" al logaritmo iterado de base (aunque difiere en detalles menores de redondeo ) y forma una inversa a la operación de tetración . [2]

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:

El logaritmo iterado crece a un ritmo extremadamente lento, mucho más lento que el logaritmo mismo o sus repeticiones. Esto se debe a que la tetración crece mucho más rápido que la exponencial iterada:

La inversa crece mucho más lento: .

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 mayor que 5.

Las bases más altas dan logaritmos iterados más pequeños.

Otras aplicaciones

El logaritmo iterado está estrechamente relacionado con la función logaritmo generalizado que se utiliza en la aritmética de índice de nivel simétrico . 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 , es .

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

Véase también

Referencias

  1. ^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. "La función logaritmo iterado, en la Sección 3.2: Notaciones estándar y funciones comunes". Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. págs. 58–59. ISBN 0-262-03384-4.
  2. ^ Furuya, Isamu; Kida, Takuya (2019). "Compactación de numerales de la Iglesia". Algoritmos . 12 (8) 159: 159. doi : 10.3390/a12080159 . MR  3998658.
  3. ^ Devillers, Olivier (marzo de 1992). "La aleatorización produce algoritmos O ( n log ∗ ⁡ n ) {\displaystyle O(n\log ^{\ast }n)} simples para problemas Ω ( n ) {\displaystyle \Omega (n)} difíciles" (PDF) . Revista internacional de geometría computacional y aplicaciones . 2 (1): 97–111. arXiv : cs/9810007 . doi :10.1142/S021819599200007X. MR  1159844. S2CID  60203.
  4. ^ Alon, Noga ; Azar, Yossi (abril de 1989). "Encontrar un máximo aproximado" (PDF) . SIAM Journal on Computing . 18 (2): 258–267. doi :10.1137/0218017. MR  0986665.
  5. ^ Cole, Richard ; Vishkin, Uzi (julio de 1986). "Lanzamiento de moneda determinista con aplicaciones a la clasificación óptima de listas paralelas" (PDF) . Información y Control . 70 (1): 32–53. doi : 10.1016/S0019-9958(86)80023-7 . MR  0853994.
  6. ^ Santhanam, Rahul (2001). "Sobre separadores, segregadores y tiempo versus espacio" (PDF) . Actas de la 16.ª Conferencia Anual del IEEE sobre Complejidad Computacional, Chicago, Illinois, EE. UU., 18-21 de junio de 2001. IEEE Computer Society . págs. 286–294. doi :10.1109/CCC.2001.933895. ISBN . 0-7695-1053-1.