¿Qué significa "log *"?

Me he encontrado con el término O(log* N) en un libro que estoy leyendo sobre estructuras de datos. ¿Qué significa log*? No puedo find it on Google, y WolframAlpha doesn't understand it either.¿Qué significa "log *"?

Fuente

2010-09-26 pauldoo

"No puedo encontrarlo en Google". Buscar en Google para 'log star' funciona bien. – Joren

prueba "logaritmo iterado de x de 0 a 6" o "IteratedLog (4)" en WolframAlpha – vokilam

Posible duplicado de [¿Qué es O (log \ * N)?] (Https://stackoverflow.com/questions/2387656/ what-is-olog-n) –

Es un logaritmo iterado. Consulte here para obtener una descripción de muchas complejidades de tiempo diferentes, y here para obtener más detalles sobre el logaritmo iterado.

El logaritmo iterado es el número de veces que se debe aplicar el logaritmo antes de que el resultado sea uno o menos.

Fuente

2010-09-26 11:45:42 paxdiablo

Se llama iterated logarithm function. Es una función de crecimiento muy lento. Por ejemplo:

lg*(2) = 1
lg*(4) = 2
lg*(16) = 3
lg*(65536) = 4
lg*(2^65536) = 5/nota de que (2^65 536) es mucho mayor que el número de átomos en el universo observable/

O en el caso de Big O podría ser más o menos considerado como tiempo constante.

Fuente

2010-09-26 11:46:29

De manera más sucinta, el logaritmo iterado cuenta el número de veces que tendría que tomar el logaritmo para reducir un número a 1. –

Por lo tanto, el inverso sería exponenciación iterada, que es el siguiente en la secuencia: adición, multiplicación (= suma iterada), exponenciación (= multiplicación iterada), ... –

Hmm, ¿qué pasa con la iteración iterada ... –

* log (n) - "log n estrella" que se conoce como "logaritmo iterado"

En simple palabra se puede asumir ingrese * (n) = log (log (log (..... (registro * (n))))

registro * (n) es muy potente

Ejemplo:.

1) Log * (n) = 5 donde n = Número de átomo en el universo

2) Tree Coloring usando 3 colores se puede hacer en log * (n) whil e colorear los colores del árbol 2 son suficientes, pero la complejidad será O (n) a continuación.

3) 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.

espero que pueda visualizar Log * (n) como este en WolframAlpha Check here

Fuente

2014-09-30 06:25:55

registro * es el número de veces que es necesario aplicar el registro de funciones hasta llegar a un valor que es menor o igual a 1. Por ejemplo: log * (16) = 3, debido registro (log (log (16))) = 1.

Para fines prácticos se puede tratar como una constante , porque esta función crece muy lento.

Fuente

2017-08-12 14:14:59

Respuesta

Cuestiones relacionadas