Logaritmo iterato

tipo di funzione matematica
(Reindirizzamento da Log*)

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:

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

ma sui numeri reali negativi, log-asterisco è 0, mentre per x positivi, così le due funzioni differiscono per gli argomenti negativi.

Figura 1. Dimostrazione di lg* 4 = 2

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 .

Analisi degli algoritmi

modifica

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

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 ≤ 265536, che è di gran lunga maggiore degli atomi dell'universo conosciuto), il logaritmo iterato con base 2 ha un valore non superiore a 5.

x lg* x
(−∞, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 265536] 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.

Altre applicazioni

modifica

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  

  1. ^ Olivier Devillers, "Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.". International Journal of Computational Geometry & Applications 2:01 (1992), pp. 97–111.
  2. ^ Noga Alon e Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.
  3. ^ Richard Cole e Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53.
  4. ^ * Thomas H. Cormen, Charles A. Leiserson, Ronald L. Rivest e Clifford Stein, Sezione 30.5, in Introduzione agli algoritmi e strutture dati, 1ª ed., MIT Press e McGraw-Hill, 1990, ISBN 0-262-03141-8.
  5. ^ On Separators, Segregators and Time versus Space

Bibliografia

modifica
Controllo di autoritàGND (DE4128315-6