63
A
risposta
73
O(log* N) è "iterated logarithm":
In informatica, il logaritmo iterata di n, registro scritto * n (di solito leggere "stella log"), è il numero di volte che la funzione logaritmica deve essere iterativo applicata prima che il risultato è inferiore o uguale a 1.
+8
Questa è una cosa davvero interessante di cui non avevo sentito parlare. Q + A +1 a testa.Immagino che O (log * N) sia per tutti gli intenti e scopi O (1). Freddo. – Greg
+0
@greg, nessun log (n) significa che il numero di elementi aumenta il tempo più lentamente. per esempio. 10x come molti elementi fa sì che la funzione impieghi 2x volte più a lungo –
+2
Penso di averlo incontrato per la prima volta nell'analisi dell'algoritmo di Union-Find, quando era 'O (N log * N)' prima che fosse migliorato in 'O (AN) ', dove A è la funzione inversa di Ackermann. Ancora non capisco la seconda prova, ma l'algoritmo 'O (N log * N)' è una lettura relativamente buona. – Larry
7
log * (n) - "log stella n" come noto come "logaritmo iterato"
In parole semplici si può presupporre log * (n) = log (log (log (..... (log * (n))))
log * (n) è molto potente.
Esempio:
1) Log * (n) = 5 dove n = numero di atomi nell'universo
2) Albero colorazione utilizzando 3 colori può essere fatto in log * (n) mentre colorano Tree 2 i colori sono sufficienti ma la complessità sarà O (n) allora.
3) Individuazione della triangolazione di Delaunay di un insieme di punti conoscendo l'albero di spanning minimo di Euclide: tempo O (n log * n) casuale.
12
Il log* N bit è un algoritmo iterato che cresce molto lentamente, molto più lentamente del solo log N. In pratica, continui semplicemente a "registrare" la risposta fino a quando non arriva al di sotto di uno (Es .: log(log(log(...log(N)))) e il numero di volte che hai dovuto log() è la risposta.
In ogni caso, questa è una questione vecchia di cinque anni su StackOverflow, ma nessun codice Si può correggere questo - ecco implementazioni sia per le funzioni ricorsive e iterative (entrambi danno lo stesso risultato)? (!):
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;
}
+1
Come risponde la domanda? – Maroun
+2
@ MarounMaroun: Ho modificato l'inizio della risposta per dare più contesto. Il codice è la descrizione/definizione che stava chiedendo. –
Dicci dove l'hai trovato –
Domanda simile: http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly Nessuna risposta su "O (log * N)' sfortunatamente. – BalusC
Questa domanda riguarda il registro * after o la notazione O() in generale? –