Yinelenen logaritma - Iterated logarithm

Gelen bilgisayar bilimleri , tekrarlanan logaritmanın ait yazılı günlük * (genellikle "okuma günlüğü yıldızı "), kaç kez logaritma fonksiyonu olmalıdır iteratif sonuç için eşit veya daha az önce uygulanan . En basit biçimsel tanım, bu yineleme ilişkisinin sonucudur : ${\görüntüleme stili n}$ ${\görüntüleme stili n}$${\görüntüleme stili 1}$

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox {if }}n>1\end{durumlar}}}$

On pozitif reel sayılar , sürekli süper logaritma (ters tetrasyon ) esasen eşdeğerdir:

${\displaystyle \log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil }$

örneğin, baz b logaritmasıdır tekrarlanır ise aralığı içinde, n yalan , O anlamına gelir tetrasyon. Ancak negatif reel sayılar, log-yıldız üzerinde , oysa pozitif için iki fonksiyon negatif argümanlar için farklılık yüzden.${\displaystyle \log ^{*}n=y}$${\displaystyle ^{y-1}b<n\leq \ ^{y}b}$${\displaystyle {^{y}b}=\alt ayraç {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}}$${\görüntüleme stili 0}$${\displaystyle \lceil {\text{slog}}_{e}(-x)\rceil =-1}$${\görüntüleme stili x}$

Şekil 1. Base-e yinelenen logaritma için log* 4 = 2'nin gösterilmesi. Yinelenen logaritmanın değeri, n girişinden [0,1] aralığına kadar y = log _b (x) eğrisinde "zikzak çizerek" bulunabilir . Bu durumda, b = e. Zig-zaglama, (n, 0) noktasından başlayıp (n, log _b (n) ), ila (0, log _b (n) ), ila (log _b (n), 0 ) arasında yinelemeli olarak hareket etmeyi gerektirir .

Yinelenen logaritma, herhangi bir pozitif gerçek sayıyı kabul eder ve bir tamsayı verir . Grafik olarak , x ekseni üzerindeki aralığa ulaşmak için Şekil 1'de ihtiyaç duyulan "zig-zag" sayısı olarak anlaşılabilir . ${\görüntüleme stili [0,1]}$

Bilgisayar biliminde, lg * genellikle , doğal logaritma (tabanlı e ile) yerine ikili logaritmayı (tabanlı ) yineleyen ikili yinelemeli logaritmayı belirtmek için kullanılır . ${\görüntüleme stili 2}$

Matematiksel olarak, yinelenen logaritma, yalnızca taban ve e tabanı için değil, ' den büyük herhangi bir taban için iyi tanımlanmıştır . ${\displaystyle e^{1/e}\yaklaşık 1.444667}$${\görüntüleme stili 2}$

Algoritmaların analizi

Yinelenen logaritma, algoritmaların ve hesaplama karmaşıklığının analizinde yararlıdır ve aşağıdakiler gibi bazı algoritmaların zaman ve uzay karmaşıklığı sınırlarında görünür:

• Öklid minimum yayılma ağacını bilerek bir dizi noktanın Delaunay üçgenlemesini bulma : rasgele O ( n log * n ) zaman.  
• Fürer'in tamsayı çarpma algoritması : O( n  log  n  2 ^{O (lg *  n )} ).
• Yaklaşık bir maksimum bulma (en az medyan kadar büyük eleman): lg *  n − 4 ila lg *  n + 2 paralel işlem.
• Richard Cole ve Uzi Vishkin 's bir 3-boyama için bir algoritma dağıtılmış N -cycle : O ( giriş *  N ) eşzamanlı iletişim mermi.
• Yol sıkıştırma ile ağırlıklı hızlı birleştirme gerçekleştirme.

Yinelenen logaritma, logaritmanın kendisinden çok daha yavaş, son derece yavaş bir hızda büyür. Pratikte uygulanan algoritmaların çalışma sürelerinin sayılmasıyla ilgili tüm n değerleri için (yani, bilinen evrendeki tahmini atom sayısından çok daha fazla olan n  ≤ 2 ⁶⁵⁵³⁶ ), taban 2 ile yinelenen logaritma, hayır değerine sahiptir. 5'ten fazla.

Daha yüksek bazlar, daha küçük yinelenen logaritmalar verir. Gerçekten de, karmaşıklık teorisinde yaygın olarak kullanılan ve daha yavaş büyüyen tek fonksiyon, ters Ackermann fonksiyonudur .

Diğer uygulamalar

Yinelenen logaritma, simetrik düzey indeks aritmetiğinde kullanılan genelleştirilmiş logaritma işleviyle yakından ilişkilidir . Aynı zamanda , bir sayının toplama kalıcılığı ile orantılıdır, yani bir kişinin sayısal köküne ulaşmadan önce sayıyı kaç kez rakamları toplamı ile değiştirmesi gerektiğidir .

Olarak hesaplama karmaşıklığı teori , Santhanam gösterir bu hesaplama kaynaklarının DTime - hesaplama süresi bir için deterministik Turing makinası - ve NTIME - bir için hesaplama zamanı belirli olmayan Turing makinası - için farklı kadar olan${\displaystyle n{\sqrt {\log ^{*}n}}.}$

Notlar

Referanslar

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "3.2: Standart gösterimler ve ortak işlevler". Algoritmalara Giriş (2. baskı). MIT Press ve McGraw-Hill. s. 55–56. ISBN'si 0-262-03293-7.