Che cosa significa "log *"?

Question

Ho trovato il termine O(log* N) in un libro che sto leggendo su strutture di dati. Cosa significa "log*"? Non riesco a find it on Google e WolframAlpha doesn't understand it either.

Answer 1

È logaritmo iterato. Vedere here per una descrizione di molte diverse complessità temporali e here per ulteriori dettagli sul logaritmo iterato stesso.

Il logaritmo iterato è il numero di volte che il logaritmo deve essere applicato prima che il risultato diventi uno o meno.

Answer 2

Si chiama iterated logarithm function. È una funzione a crescita molto lenta. Ad esempio:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5/notare che (2^65536) è molto più grande del numero di atomi nell'universo osservabile/

O nel caso di Big O potrebbe essere più o meno considerato come tempo costante.

Answer 3

log * (n) - "log Stella n" come noto come "logaritmo iterato"

In parole semplici si può assumere log * (n) = log (registro (log (..... (log * (n))))

log * (n) è molto potente

Esempio:.

1) Accedi * (n) = 5 dove n = numero di atomi nell'universo

2) Albero La colorazione con 3 colori può essere fatta in log * (n) whil e colorare Albero 2 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 copertura minimo di Euclide: tempo O (n log * n) casuale.

spero è possibile visualizzare Log * (n) come questo su WolframAlpha Check here

Answer 4

registro * è il numero di volte in cui è necessario applicare il log-funzione fino a raggiungere un valore che minore o uguale a 1. Per esempio: log * (16) = 3, a causa di log (log (log (16))) = 1.

Ai fini pratici è possibile trattarlo come una costante , perché questa funzione cresce molto lentamente.