反復対数

計算機科学において、反復対数（）は、結果が formula_1 以下となるまでに必要とする対数関数の適用回数である。
概要.
formula_2 についての反復対数は formula_3（ログスター formula_2）と表記され、単純には次のように再帰的に定義される。
関数の反復を用いれば、次のようにも定義できる。
正の実数においては、連続性のに等しい。
言い換えれば、formula_8 を反復対数の底として、formula_2 が区間 formula_10 にあるとき、その反復対数は formula_11 で表される。ここで formula_12 はテトレーションである。ただし、負の実数 formula_13 について、反復対数の値は formula_14 であるが、formula_15 であるので、負の実数においては先に示した関係は成り立たないことになる。
反復対数は実数全体で定義され、非負整数を値域にとる。正の実数に対しては、formula_16 平面の図1において formula_13 軸上の区間 formula_18 に到達するために必要なジグザグの数として図式的に理解できる。
計算機科学においては、自然対数の代わりに二進対数を反復する反復対数 formula_19 も用いられている。数学的には、formula_20 や formula_21 だけでなく、formula_22 より大きい任意の底に対してwell-definedである。
アルゴリズム解析.
反復対数はアルゴリズム解析や計算複雑性理論の分野でよく用いられている。以下に示すアルゴリズムでは、時間計算量との限界値が反復対数で表されている。
反復対数の成長は非常に遅く、対数関数よりもはるかに遅い。実装されている実際のアルゴリズムの実行時間を数えるのに十分な formula_2 のすべての値（すなわち formula_29、この最大値は観測可能な宇宙内の原子数 formula_30 を優に超える）に対して、底 formula_21 の反復対数の値はたったの formula_32 以下である。
より高い底の反復対数は、より小さい値を返す。計算の複雑さの分野で使われるものでいえば、逆アッカーマン関数だけである。
他の応用例.
反復対数は、で用いられると密接に関係している。加法についての（ある数が数字根に到達するまでに、数字をすべての桁の和で置き換える回数）は、formula_33 である。
計算複雑性理論において、によれば、計算資源のDTIME（決定性チューリング機械での計算時間）とNTIME（非決定性チューリング機械での計算時間）とが区別できるのは formula_34 までである。