¿Qué es O (log * N)?

80

¿Qué es O (log * N) y en qué se diferencia de O (log N)?

algorithm math complexity-theory logarithm iterated-logarithm Timmy
fuente
Pregunta similar: stackoverflow.com/questions/2307283/…O(log* N) Desafortunadamente, no hay respuesta .
BalusC
1
¿Esta pregunta es sobre el * after log o sobre la notación O () en general?
Bart van Heukelom
1
Está en algunas estructuras de datos avanzadas, aunque estoy fuera de la escuela durante demasiado tiempo para recordar de dónde viene.
Larry
1
Supongo que no tan avanzado, acabo de recordarlo: Union Find con el límite inferior inicial de la compresión de ruta se estableció en O (n log * n) hasta que se redujo a O (A n), donde A es la función inversa de Ackermann ..
Larry
1
Je. En la práctica, creo que estaría satisfecho con una estimación de O (n) para eso. :-)
RBarryYoung

Respuestas:

84

O( log* N )es " logaritmo iterado ":

En ciencias de la computación, el logaritmo iterado de n, escrito log * n (normalmente leído "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 1.

Larry
fuente
9
Eso es algo realmente interesante de lo que no había oído hablar. Q + A +1 cada uno. Supongo que O (log * N) es para todos los efectos O (1). Frio.
Greg
1
@greg, no log (n) significa que a medida que aumenta el número de elementos, el tiempo es más lento. p.ej. 10 veces más elementos solo hace que la función tome el doble de tiempo
Martin Beckett
2
Creo que lo encontré por primera vez en el análisis del algoritmo Union-Find, cuando estaba O( N log* N )antes de que se mejorara O( A N ), donde A es la función de Ackermann inversa. Todavía no entiendo la última prueba, pero el O( N log* N )algoritmo es una lectura relativamente buena.
Larry
13
@Martin, pero esto es log * (n) que sube locamente lentamente, de manera que log * (2 ^ 65536 -1) = 5. También podrías llamar a esa constante.
Greg
4
Lo siento, no había apreciado la diferencia de estrella de registro, gracias, ¡aprendiendo algo nuevo!
Martin Beckett
25

El log* Nbit es un algoritmo iterado que crece muy lentamente, mucho más lento que simplemente log N. Básicamente, simplemente sigue 'registrando' iterativamente la respuesta hasta que esté por debajo de uno (por ejemplo:) log(log(log(...log(N))), y la cantidad de veces que tuvo que hacerlo log()es la respuesta.

De todos modos, esta es una pregunta de cinco años en Stackoverflow, ¿pero no hay código? (!) Arreglemos eso: aquí hay implementaciones para las funciones recursivas e iterativas (ambas dan el mismo resultado):

public double iteratedLogRecursive(double n, double b)
{
    if (n > 1.0) {
        return 1.0 + iteratedLogRecursive( Math.Log(n, b),b );
    }
    else return 0;
}

public int iteratedLogIterative(double n, double b)
{
    int count=0;
    while (n >= 1) {
        n = Math.Log(n,b);
        count++;
    }
    return count;
}
Dan W
fuente
2
¿Cómo responde esto a la pregunta?
Maroun
3
@MarounMaroun: Edité el comienzo de la respuesta para dar más contexto. El código es la descripción / definición que estaba solicitando.
Dan W
9

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 poderoso.

Ejemplo:

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

2) La coloración de árboles con 3 colores se puede hacer en log * (n) mientras que la coloración de árboles con 2 colores es suficiente, pero la complejidad será O (n) entonces.

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.

Manish Kumar
fuente