反復対数

計算機科学において、反復対数（）は、結果が以下となるまでに必要とする対数関数の適用回数である。

概要についての反復対数は（ログスター）と表記され、単純には次のように再帰的に定義される。

関数の反復を用いれば、次のようにも定義できる。

正の実数においては、連続性のに等しい。

言い換えれば、を反復対数の底として、が区間にあるとき、その反復対数はで表される。ここではテトレーションである。ただし、負の実数について、反復対数の値はであるが、であるので、負の実数においては先に示した関係は成り立たないことになる。

反復対数は実数全体で定義され、非負整数を値域にとる。正の実数に対しては、平面の図1において軸上の区間に到達するために必要なジグザグの数として図式的に理解できる。

計算機科学においては、自然対数の代わりに二進対数を反復する反復対数も用いられている。数学的には、やだけでなく、より大きい任意の底に対してwell-definedである。

アルゴリズム解析 +底がの反復対数の値︙ 反復対数はアルゴリズム解析や計算複雑性理論の分野でよく用いられている。以下に示すアルゴリズムでは、時間計算量との限界値が反復対数で表されている。

が分かっている点の集合に対してドロネー三角形分割を行うアルゴリズム - 。整数乗算の - 。近似的な最大値を求めるアルゴリズム - から回の演算。とによるグラフの3彩色問題の分散アルゴリズム - 回の同期通信ステップ。

反復対数の成長は非常に遅く、対数関数よりもはるかに遅い。実装されている実際のアルゴリズムの実行時間を数えるのに十分なのすべての値（すなわち、この最大値は観測可能な宇宙内の原子数を優に超える）に対して、底の反復対数の値はたったの以下である。

より高い底の反復対数は、より小さい値を返す。計算の複雑さの分野で使われるものでいえば、逆アッカーマン関数だけである。

他の応用例反復対数は、で用いられると密接に関係している。加法についての（ある数が数字根に到達するまでに、数字をすべての桁の和で置き換える回数）は、である。

計算複雑性理論において、によれば、計算資源のDTIME（決定性チューリング機械での計算時間）とNTIME（非決定性チューリング機械での計算時間）とが区別できるのはまでである。

脚注

出典

Źródło i licencja