algorithm - log - o n !)

¿Qué es O(log*N)?

Question

¿Qué es O(log* N) ?

Lo sé a lo grande ... Oh, el log* es desconocido.

Answer 1

El bit log* N es un algoritmo iterado que crece muy lentamente, mucho más lento que el log N Básicamente, simplemente mantiene ''registrando'' iterativamente la respuesta hasta que quede por debajo de uno (Ej: log(log(log(...log(N))) ), y la cantidad de veces que tuvo que log() es la respuesta.

De todos modos, esta es una pregunta de cinco años sobre , ¿pero no hay código? (!) Arreglemos eso: aquí hay implementaciones para las funciones recursiva e iterativa (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;
}

Answer 2

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) Tree Coloring usando 3 colores se puede hacer en log * (n) mientras que colorear Tree 2 colores son suficientes pero la complejidad será O (n) a continuación.

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

Answer 3

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

En informática, el logaritmo iterado de n, log * n escrito (generalmente, "estrella de registro"), es el número de veces que la función de logaritmo debe aplicarse iterativamente antes de que el resultado sea menor o igual a 1.