迭代对数

迭代对数（英语：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）.