Logaritmo iterato

Da Wikipedia, l'enciclopedia libera.

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:


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

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

\log^* n = \lceil \text{slog}_e(n) \rceil

ma sui numeri reali negativi, log-asterisco è 0, mentre \lceil \text{slog}_e(-x)\rceil = -1 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 e^{1/e}\approx1,444667.

Analisi degli algoritmi[modifica | modifica wikitesto]

Il logaritmo iterato è utile nell'analisi dei logaritmi 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 | modifica wikitesto]

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 n\sqrt{\log^*n}.

Note[modifica | modifica wikitesto]

  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 | modifica wikitesto]