反復対数

対数を繰り返し適用したもの

計算機科学において、反復対数: iterated logarithm)は、結果が 以下となるまでに必要とする対数関数の適用回数である[1]

図1 自然対数を反復する反復対数 の値が であることを示す図。反復対数の値は、入力値 から区間 に到達するまでの間、曲線 をジグザグに移動することで求められる。ジグザグは点 から始め、次に点 、点 、点 といった順番に移動を繰り返していくことで描かれる。

概要

編集

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

 

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

 

正の実数においては、連続性の超対数英語版に等しい。

 

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

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

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

アルゴリズム解析

編集
底が   の反復対数の値
   
   
   
   
   
   
   
   

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

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

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

他の応用例

編集

反復対数は、symmetric level-index arithmetic英語版[訳語疑問点]で用いられる一般化された対数関数英語版と密接に関係している。加法についての持続係数英語版(ある数が数字根に到達するまでに、数字をすべての桁の和で置き換える回数)は、  である。

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

脚注

編集

出典

編集
  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], “The iterated logarithm function, in Section 3.2: Standard notations and common functions”, Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, pp. 58–59, ISBN 0-262-03384-4 
  2. ^ Devillers, Olivier (1992). “Randomization yields simple   algorithms for difficult   problems”. International Journal of Computational Geometry & Applications 2 (1): 97–111. doi:10.1142/S021819599200007X. MR1159844. 
  3. ^ Alon, Noga; Azar, Yossi (1989). “Finding an approximate maximum”. SIAM Journal on Computing 18 (2): 258–267. doi:10.1137/0218017. MR986665. 
  4. ^ Cole, Richard; Vishkin, Uzi (1986). “Deterministic coin tossing with applications to optimal parallel list ranking”. Information and Control 70 (1): 32–53. doi:10.1016/S0019-9958(86)80023-7. MR853994. 
  5. ^ Santhanam, Rahul (2001). "On separators, segregators and time versus space" (PDF). Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001. IEEE Computer Society. pp. 286–294. doi:10.1109/CCC.2001.933895