迭代對數

迭代對數（英語：Iterated logarithm）也稱為重複對數，是一個增加非常慢的數學函數，可以視為近似常數。一般會用log*  n來表示。一實數的迭代對數是指須對實數連續進行幾次對數運算後，其結果才會小於等於1。最簡單的定義以是以下遞迴函數的結果：

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

說明為何log* 4 = 2

在計算機科學中，lg* 常用來表示實數可以進行幾次以2為底的對數運算，lg*及log*都可以針對所有實數取值，值的結果一定是一個整數。

右圖中以log* 4為例，說明迭代對數的計算方式，圖中的曲線為y=log x，一開始由（4,0）開始畫一垂直線，和y=log x相交於（4,1.386），再由交點畫一水平線到y軸，交點在（0,1.386），再畫一條往右下，和x軸夾角45度的斜線，和x軸交點在（1.386,0），再依以上方式畫垂直線、水平線及斜線，和x軸交點在（0.326,0），再畫垂直線時，和y=log x交點已不在第一象限，因此結束，中間進行了二次log x的計算，因此log* 4=2。

迭代對數的增加速度非常慢，比對數要慢很多。對於實際演算法可能的執行次數而言（n ≤ 2⁶⁵⁵³⁶，此數字比宇宙中已知的原子數目還要多），lg*的結果都小於等於5。

x	lg* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536]	5

演算法分析

迭代對數常用在算法分析及計算複雜性理論中，以下演算法的時間複雜度上限或空間複雜度上限為迭代對數：

• 若有許多點，在已知其歐幾里德最小生成樹（英语：Euclidean minimum spanning tree）的條件下，要找到Delaunay三角網：亂數法需O(n log* n)次。
• 計算整數乘法的Fürer演算法（英语：Fürer algorithm）：O(n log n 2^lg* n)
• 找集合中的近似最大值（approximate maximum，至少和中位數一样大的元素）：需要lg* n − 4至lg* n + 2次平行處理^[1]。

Santhanam^[2]證明NTIME和DTIME的複雜度最多只差${\displaystyle n{\sqrt {\log ^{*}n}}.}$。

其他應用

一個整數的加法韧性和其迭代對數成正比。加法韧性可定義為一數字需計算幾次數字和才能得到其數字根的次數。

迭代對數和對稱level-index代數（英语：symmetric level-index arithmetic）中用到的廣義對數函數有密切關係。

參考資料

1. Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.
2. On Separators, Segregators and Time versus Space. [2012-12-31]. （原始内容存档于2012-06-25）.