¿Qué es O (log * N)?

Question

¿Qué es O(log* N)?

Sé grande-Oh, el log* es desconocido.

Answer 1

O(log* N) es "iterated logarithm":

En informática, el logaritmo iterado de n, registro escrito * n (por lo general leer 'estrella de registro'), es el número de veces que la función logaritmo debe ser iterativa aplicado antes de que el resultado es menor que o igual a 1.

Answer 2

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

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

log * (n) es muy potente.

Ejemplo:

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

2) árbol colorear usando 3 colores se puede hacer de registro * (n) mientras que colorear los colores del Árbol 2 es suficiente, pero la complejidad será O (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.

Answer 3

El bit log* N es un algoritmo iterado que crece muy lentamente, mucho más lento que solo log N. Básicamente, simplemente mantiene '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 responder a log() es la respuesta.

De todos modos, esta es una cuestión de edad de cinco años en Stackoverflow, pero ningún código Vamos a arreglar eso - aquí está implementaciones tanto para las funciones recursivas e iterativas (ambos 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; 
}