Logarytm iterowany

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.

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{array}{cc}0,& \text{dla }n⩽1;\\ 1+{\log }^{*}(\log n),& \text{dla }n>1.\end{array}$

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⩽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.