big o - multiple - ¿Qué significa "log*"?

pagerank algorithm

Question

He encontrado el término O(log* N) en un libro que estoy leyendo sobre estructuras de datos. ¿Qué significa log* ? No puedo encontrarlo en Google , y WolframAlpha tampoco lo entiende .

Answer 1

Es el logaritmo iterado. Vea here para una descripción de muchas complejidades de tiempo diferentes, y here para más detalles sobre el logaritmo iterado en sí.

El logaritmo iterado es la cantidad de veces que se debe aplicar el logaritmo antes de que el resultado sea uno o menos.

Answer 2

Se llama here . 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 / note que (2 ^ 65536) es mucho más grande que el número de átomos en el universo observable /

O, en el caso de Big O, podría considerarse un tiempo constante.

Answer 3

log * (n) - "log Star n" conocido como "logaritmo iterado"

En palabras simples, puede asumir log * (n) = log (log (log (..... (log * (n))))

log * (n) es muy potente.

Ejemplo:

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

2) La coloración del árbol utilizando 3 colores se puede hacer en el registro * (n), mientras que los colores del árbol 2 son suficientes, pero la complejidad será O (n).

3) Encontrar la triangulación de Delaunay de un conjunto de puntos que conocen el árbol de expansión mínimo euclidiano: tiempo O (n log * n) aleatorio.

Espero que puedas visualizar el registro * (n) de esta manera en WolframAlpha. Consulta aquí

Answer 4

log * es el número de veces que necesita aplicar la función log hasta que alcanza un valor menor o igual a 1. Para Instancia: log * (16) = 3, porque log ₂ (log ₂ (log ₂ (16) )) = 1.

Por razones prácticas, puedes tratarlo como una constante, porque esta función crece muy lentamente.