Logarytm iterowany

Logarytm iterowany – funkcja używana głównie w teorii złożoności obliczeniowej, dziale informatyki.

Definicja

Logarytm iterowany zdefiniowany jest jako liczba złożeń logarytmu potrzebnych do uzyskania liczby niewiększej od jedności:

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

Powszechnie definicję uściśla się poprzez użycie logarytmu dwójkowego. Jednak ponieważ w informatyce stosuje się notację dużego O, więc zwykle równie dobrze można zmienić podstawę logarytmu na inną większą od 1. Wynika to z tego, że logarytmy o różnych (większych niż 1) podstawach są wprost proporcjonalne (współczynnik proporcjonalności jest dodatni; jeśli a > 1 i b > 1, to $\log_a c = \log_a b \cdot \log_b c$, gdzie liczba $\log_a b > 0$).

Logarytm iterowany jest dobrze zdefiniowaną funkcją dla podstaw większych niż

$e^{1/e}\approx1.444667$.

W przeciwnym razie wyrażenie może nie być zbieżne.

Własności

Jest to funkcja bardzo wolno rosnąca, przykładowo dla wszystkich

$n\leqslant 2^{65536} = 2^{2^{2^{2^{2}}}}$

wartość logarytmu iterowanego nie przekracza 5, a wiadomo, że $2^{65536} > 10^{19600}$. Z tego względu, dla większości zastosowań praktycznych wartość tej funkcji jest niewielka.