逆アッカーマン関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/10 01:20 UTC 版)
「アッカーマン関数」の記事における「逆アッカーマン関数」の解説
自然数nに対して A ( m − 1 , m − 1 ) < n ≤ A ( m , m ) {\displaystyle A(m-1,m-1)<n\leq A(m,m)} を満たすようなmを取り、 α ( n ) = m {\displaystyle \alpha (n)=m} として関数αを定義する。この関数を逆アッカーマン関数という。このとき定義から逆アッカーマン関数は全域かつ上界を持たないが、その値は非常にゆっくりと大きくなる。 Tarjanの1975年の論文において提唱された素集合データ構造の探索および結合アルゴリズムについて、その計算量が O ( α ( n ) ) {\displaystyle O(\alpha (n))} で見積もられた。 逆アッカーマン関数は原始再帰関数である。
※この「逆アッカーマン関数」の解説は、「アッカーマン関数」の解説の一部です。
「逆アッカーマン関数」を含む「アッカーマン関数」の記事については、「アッカーマン関数」の概要を参照ください。
ウィキペディア小見出し辞書の「逆アッカーマン関数」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 逆アッカーマン関数のページへのリンク
