Iterovaný logaritmus
Ve výpočetní technice je iterovaný logaritmus čísla n , zaznamenaný (čtení „log star“ nebo „log star“), kolikrát na něj musí být logaritmus použit, než bude výsledek menší nebo roven 1. This Funkce se používá k popisu složitosti určitých algoritmů, zejména v distribuovaných algoritmech .
log∗(ne){\ displaystyle \ log ^ {*} (n)}![\ log ^ {*} (n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf706147043580232b6e19d25c80a0f73bb2d525)
Definice
Báze opakována logaritmus b mohou být definovány:
logb∗ne: ={0-li ne≤1;1+logb∗(logbne)-li ne>1.{\ displaystyle \ log _ {b} ^ {*} n: = {\ begin {cases} 0 & {\ mbox {si}} n \ leq 1; \\ 1+ \ log _ {b} ^ {*} (\ log _ {b} n) & {\ mbox {si}} n> 1. \ end {cases}}}![{\ displaystyle \ log _ {b} ^ {*} n: = {\ begin {cases} 0 & {\ mbox {si}} n \ leq 1; \\ 1+ \ log _ {b} ^ {*} (\ log _ {b} n) & {\ mbox {si}} n> 1. \ end {cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66a00ffe0ed6ccd901b3bd57489acbb20eb95d00)
Na kladných reálných čísel, kontinuální ( v) super-logaritmus (inverzní tetration ) je v podstatě ekvivalentní:
logE∗ne=⌈slÓGE(ne)⌉{\ displaystyle \ log _ {e} ^ {*} n = \ lceil \ mathrm {slog} _ {e} (n) \ rceil}![{\ displaystyle \ log _ {e} ^ {*} n = \ lceil \ mathrm {slog} _ {e} (n) \ rceil}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f77dce4b8ed8faf9520e71ebe0073daa0ac87948)
Následující tabulka uvádí hodnoty iterovaného logaritmu (v základu 2):
X{\ displaystyle x}
|
log2∗X{\ displaystyle \ log _ {2} ^ {*} x}
|
---|
]-∞;1]{\ displaystyle] - \ infty; 1]}![{\ displaystyle] - \ infty; 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edfc3ee458eec4169c3788c27a6955b3013a2706) |
0
|
]1,2]{\ displaystyle] 1,2]}![{\ displaystyle] 1,2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2545c2ae6bb7fa4444175fe644fa2e4dbfe3ec2) |
1
|
]2,4]{\ displaystyle] 2,4]}![{\ displaystyle] 2,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15f612a16960e64caa44ba64284e443be479eec4) |
2
|
]4,16]{\ displaystyle] 4.16]}![{\ displaystyle] 4.16]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/741160006f2c5fba6e49c8555db27f25a604744a) |
3
|
]16,65536]{\ displaystyle] 16.65536]}![{\ displaystyle] 16.65536]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68bd491c79b17bd294fbfefd9310d16ddd3f3392) |
4
|
]65536,265536]{\ displaystyle] 65536,2 ^ {65536}]}![{\ displaystyle] 65536,2 ^ {65536}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1905c450fdf37c5835cf234989afd13516e382f6) |
5
|
Vlastnosti
Tato funkce roste extrémně pomalu. Běžná funkce v teoretické informatice, která roste ještě pomaleji, je převrácená funkce Ackermanna . Tyto dvě funkce spolu také souvisejí, protože iterovaný logaritmus je jednou z úrovní hierarchie Ackermannovy vzájemnosti.
Použití
Poznámky a odkazy
-
Gabriel Nivasch, „ Inverzní Ackermann bez bolesti “ ,2009.
-
Referenční část Linial: (in) Nathan Linial , „ Locality in Distributed Graph Algorithms “ , SIAM Journal on Computing , vol. 21, n o 1,1992, str. 193-201.
-
Sanjoy Dasgupta , Christos H. Papadimitriou a Umesh Vazirani , Algorithms , McGraw-Hill, Inc.,13. září 2006( ISBN 0073523402 a 9780073523408 , číst online )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">