Logarytm iterowany

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Definicja[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.