Logarytm iterowany

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

Wykres pokazujący, że iterowany logarytm z 4 (podstawa e) wynosi 2. Krzywa to log(n), a pozostałe linie podążają ścieżką iteracji.

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\leqslant 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}\approx 1{,}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.