查看“︁迭代對數”︁的源代码

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

:<math>
  \log^* n :=
  \begin{cases}
    0                  & \mbox{if } n \le 1; \\
    1 + \log^*(\log n) & \mbox{if } n > 1
   \end{cases}
 </math>

<!--On the positive real numbers, the continuous [[super-logarithm]] (inverse [[tetration]]) is essentially equivalent:
:<math>\log^* n = \lceil \text{slog}_e(n) \rceil</math>
but on the negative real numbers, log-star is 0, whereas <math>\lceil \text{slog}_e(-x)\rceil = -1</math> for positive ''x'', so the two functions differ for negative arguments.
-->
[[Image:Iterated logarithm.png|right|300px|thumb|說明為何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。
<!--
Mathematically, the iterated logarithm is well-defined not only for base 2 and base ''e'', but for any base greater than <math>e^{1/e}\approx1.444667</math>.-->

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

{|class=wikitable
! ''x'' !! lg*&nbsp;''x''
|-
| (−∞, 1] || 0
|-
| (1, 2] || 1
|-
| (2, 4] || 2
|-
| (4, 16] || 3
|-
| (16, 65536] || 4
|-
| (65536, 2<sup>65536</sup>] || 5
|}

==演算法分析==
迭代對數常用在[[算法分析]]及[[計算複雜性理論]]中，以下演算法的時間複雜度上限或空間複雜度上限為迭代對數：
* 若有許多點，在已知其{{link-en|歐幾里德最小生成樹|Euclidean minimum spanning tree}}的條件下，要找到[[Delaunay三角網]]：亂數法需[[大O符号|O]](''n''&nbsp;log*&nbsp;''n'')次。<!--Olivier Devillers-->
* 計算整數乘法的{{link-en|Fürer演算法|Fürer algorithm}}：O(''n''&nbsp;log&nbsp;''n''&nbsp;2<sup>lg*&nbsp;''n''</sup>)
* 找集合中的近似最大值（approximate maximum，至少和中位數一样大的元素）：需要lg*&nbsp;''n'' − 4至lg*&nbsp;''n'' + 2次平行處理<ref>Noga Alon and Yossi Azar, "Finding an Approximate Maximum". ''SIAM Journal of Computing'' '''18''':2 (1989), pp. 258–267.</ref>。

Santhanam<ref>{{Cite web |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392 |title=On Separators, Segregators and Time versus Space |accessdate=2012-12-31 |archive-date=2012-06-25 |archive-url=https://web.archive.org/web/20120625144901/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392 |dead-url=no }}</ref>證明[[NTIME]]和[[DTIME]]的複雜度最多只差<math>n\sqrt{\log^*n}.</math>。

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

迭代對數和{{link-en|對稱level-index代數|symmetric level-index arithmetic}}中用到的廣義對數函數有密切關係。

==參考資料==
{{reflist}}

[[Category:渐近分析]]
[[Category:对数]]