Logarytm iterowany
| Ten artykuł od 2023-08 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
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:
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 i 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
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.
- p
- d
- e
pojęcia definiujące |
|
---|---|
funkcje logarytmiczne |
|
powiązane funkcje |
|
inne pojęcia | |
uczeni |