Logarytm iterowany
W informatyce , powtórzyć logarytm danej liczby n , zauważył (czytaj „gwiazda dziennika” lub „gwiazda dziennika”), to ile razy logarytm muszą być stosowane do niego przed efektem jest mniejsza lub równa 1. Ten Funkcja służy do opisu złożoności niektórych algorytmów, zwłaszcza w algorytmach rozproszonych .
Definicja
Podstawy powtórzyć logarytm b może być określona przez:
Na dodatnich liczbach rzeczywistych ciągły ( in) super-logarytm (odwrotność tetracji ) jest zasadniczo równoważny:
Poniższa tabela przedstawia wartości iterowanego logarytmu (o podstawie 2):
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
![{\ displaystyle] - \ infty; 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edfc3ee458eec4169c3788c27a6955b3013a2706)
![{\ displaystyle] 1, 2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2545c2ae6bb7fa4444175fe644fa2e4dbfe3ec2)
![{\ displaystyle] 2,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15f612a16960e64caa44ba64284e443be479eec4)
![{\ displaystyle] 4.16]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/741160006f2c5fba6e49c8555db27f25a604744a)
![{\ displaystyle] 16.65536]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68bd491c79b17bd294fbfefd9310d16ddd3f3392)
![{\ Displaystyle] 65536,2 ^ {65536}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1905c450fdf37c5835cf234989afd13516e382f6)
Nieruchomości
Ta funkcja rośnie niezwykle wolno. Powszechną funkcją informatyki teoretycznej, która rozwija się jeszcze wolniej, jest odwrotność funkcji Ackermanna . Te dwie funkcje są również powiązane, ponieważ logarytm iterowany jest jednym z poziomów hierarchii odwrotności Ackermanna.
Używa
- Ta funkcja jest używana do analizy algorytmów, na przykład do wyrażenia złożoności algorytmu triangulacji Delaunaya oraz w algorytmach rozproszonych, na przykład w dolnej granicy Linial dla kolorowania grafów .
- Dasgupta i wsp., W swojej książce algorytmicznej, przedstawiają tłumioną analizę złożoności struktury danych znajdowania sumy przy użyciu iterowanego logarytmu.
- Logarytm iterowany jest zaangażowany w złożoność algorytmu Fürera .
Uwagi i odniesienia
- Gabriel Nivasch, „ Inverse Ackermann bez bólu ” ,2009.
- Sekcja referencyjna Linial: (in) Nathan Linial , „ Locality in Distributed Graph Algorithms ” , SIAM Journal on Computing , vol. 21, n o 1,1992, s. 193-201.
- Sanjoy Dasgupta , Christos H. Papadimitriou i Umesh Vazirani , Algorithms , McGraw-Hill, Inc.,13 września 2006( ISBN 0073523402 i 9780073523408 , czytaj online )