Logaritmo iterato

In informatica, il logaritmo iterato di n, scritto log* n (solitamente letto "log asterisco"), è il numero di volte che la funzione logaritmo deve essere applicata iterativamente prima che il risultato sia minore o uguale a 1. La più semplice definizione formale è il risultato di questa funzione ricorsiva:

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$

Sui numeri reali positivi, il superlogaritmo continuo (tetrazione inversa) è essenzialmente equivalente:

${\displaystyle \log ^{*}n=\lceil {\text{slog}}_{e}(n)\rceil }$

ma sui numeri reali negativi, log-asterisco è 0, mentre ${\displaystyle \lceil {\text{slog}}_{e}(-x)\rceil =-1}$ per x positivi, così le due funzioni differiscono per gli argomenti negativi.

In informatica, lg-* si usa spesso per indicare il logaritmo binario iterato, che itera invece il logaritmo binario. Il logaritmo iterato accetta qualsiasi numero reale positivo e produce un intero. Graficamente, può essere inteso come il numero di "zig-zag" richiesti nella Figura 1 per raggiungere l'intervallo [0, 1] sull'asse delle x.

Matematicamente, il logaritmo iterato è ben definito non solo per la base 2 e la base e, ma per qualsiasi base maggiore di ${\displaystyle e^{1/e}\approx 1,444667}$.

Il logaritmo iterato è utile nell'analisi degli algoritmi e nella complessità computazionale, apparendo nei limiti della complessità temporale e spaziale di alcuni algoritmi come:

• Trovare la triangolazione di Delaunay di un insieme di punti conoscendo l'albero ricoprente minimo euclideo: tempo randomizzato O(n log* n)^[1]
• Algoritmo di Fürer per la moltiplicazione degli interi: O(n log n 2^lg* n)
• Trovare un massimo approssimato (elemento grande almeno quanto la mediana): lg* n − 4 to lg* n + 2 operazioni parallele^[2]
• Algoritmo distribuito per 3-colorare un n-ciclo di Richard Cole e Uzi Vishkin: O(log* n) sessioni di comunicazione sincrona.^[3][4]

Il logaritmo iterato cresce a una velocità estremamente lenta, molto più lenta del logaritmo stesso. Per tutti i valori di n rilevanti per il conteggio dei tempi di esecuzione di algoritmi implementati in pratica (cioè, n ≤ 2⁶⁵⁵³⁶, che è di gran lunga maggiore degli atomi dell'universo conosciuto), il logaritmo iterato con base 2 ha un valore non superiore a 5.

Le basi superiori danno logaritmi iterati minori. In effetti, la sola funzione comunemente usata nella teoria della complessità che cresce più lentamente è la funzione inversa di Ackermann.

Il logaritmo iterato è strettamente legato alla funzione logaritmica generalizzata usata nell'aritmetica con indici di livello simmetrico. È anche proporzionale alla persistenza additiva di un numero, il numero di volte in cui si deve sostituire il numero con la somma delle sue cifre prima di raggiungere la sua radice numerica.

Santhanam^[5] mostra che DTIME e NTIME sono distinti fino a ${\displaystyle n{\sqrt {\log ^{*}n}}.}$

• Thomas H. Cormen, Charles A. Leiserson, Ronald L. Rivest e Clifford Stein, 3.2: Notazioni standard e funzioni comuni, in Introduzione agli algoritmi e strutture dati, 2ª ed., MIT Press e McGraw-Hill, 2001 [1990], pp. 55–56, ISBN 0-262-03293-7.

Portale Informatica

Portale Matematica