反復対数

コンピュータサイエンスでは、反復対数${\displaystyle n}$、記録* ${\displaystyle n}$（通常は「log star 」と読みます）は、結果が以下になるまでに、対数関数 を繰り返し適用する必要がある回数です。${\displaystyle 1}$[ ^{1 ]最も単純な形式的定義は、}この漸化式の結果である。

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

コンピュータサイエンスでは、lg *はバイナリ反復対数を表すためによく使用され、これはバイナリ対数（底は ）を反復します。${\displaystyle 2}$自然対数（底がe）の代わりに ) を使用します。数学的には、反復対数は、 より大きい任意の底に対して適切に定義されます。${\displaystyle e^{1/e}\approx 1.444667}$基地だけでなく${\displaystyle 2}$底はe。「スーパー対数」関数${\displaystyle \mathrm {slog} _{b}(n)}$基本と「実質的に同等」である${\displaystyle b}$反復対数（丸めの細かい点で違いはあるが）であり、テトレーションの演算の逆演算を形成する。^{[ 2 ]}

反復対数は、アルゴリズムと計算複雑性の分析に役立ち、次のようなアルゴリズムの時間計算量と空間計算量の境界に現れます。

• ユークリッド最小全域木がわかっている点の集合のドロネー三角形分割を見つける: ランダム化されたO ( n log * n )時間。^{[ 3 ]}  
• 整数乗算のためのフューラーのアルゴリズム：O( n  log n 2 ^{O ( lg * n )} )。   
• 近似最大値（中央値以上の大きさの要素）を見つける：lg * n − 1 ± 3 の並列演算。^{[ 4 ]} 
• リチャード・コールとウジ・ヴィシュキンによるnサイクルの3彩色分散アルゴリズム：O ( log * n )回の同期通信ラウンド。^{[ 5 ]} 

反復対数は非常にゆっくりとした速度で増加し、対数自体やその繰り返しよりもはるかに遅い。これは、テトレーションが反復指数関数よりもはるかに速く増加するためである。

$${\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}}$$

逆数の増加ははるかに遅い。${\displaystyle \log _{b}^{*}x\ll \log _{b}^{n}x}$。

実際に実装されているアルゴリズムの実行時間をカウントすることに関連するすべてのnの値(つまり、 n  ≤  2 ⁶⁵⁵³⁶、これは既知の宇宙の原子の推定数よりもはるかに大きい) に対して、底が 2 の反復対数の値は 5 以下になります。

底が大きいほど、反復対数は小さくなる。

反復対数は、対称レベルインデックス演算で使用される一般化対数関数と密接に関連しています。数の加法持続性、つまり、その数のデジタルルートに到達するまでに、その数をその桁の合計で置き換える必要がある回数は、${\displaystyle O(\log ^{*}n)}$。

計算複雑性理論において、Santhanam ^{[ 6 ]}は、計算リソースDTIME (決定論的チューリングマシンの計算時間) とNTIME (非決定論的チューリングマシンの計算時間) は、以下の点まで異なることを示している。${\displaystyle n{\sqrt {\log ^{*}n}}.}$

• 逆アッカーマン関数は、計算複雑性理論でも用いられる、さらに緩やかに増加する関数である。