Logarytm iterowany

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Definicja[edytuj]

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

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 , gdzie liczba ).

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

.

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

Własności[edytuj]

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

wartość logarytmu iterowanego nie przekracza 5, a wiadomo, że . Z tego względu, dla większości zastosowań praktycznych wartość tej funkcji jest niewielka.