Skip to content →

アッカーマンの逆関数

アッカーマンの逆関数は Union Find や最小全域木、半群の区間積など様々な問題の計算量に現れます。この記事ではなぜアッカーマンの逆関数が現れるのかを解き明かしたいと思います。

アッカーマンの逆関数 \(\alpha(y)\) とは、アッカーマン関数 \(A_n(x)\) の逆関数です。
注:\(\alpha\) は、\(x\) ではなく \(n\) に対する逆関数

アッカーマン関数 \(A_n(x)\) とは非負整数 \(n, x\) に対して$$A_n(x) = \begin{cases}
x + 1, & \text{ if }n = 0\\
A_{n-1}(1), & \text{ if }x = 0\\
A_{n-1}(A_n(x-1)), & \text{ otherwise }\\
\end{cases}$$で定義される関数です。三つ目の漸化式を繰り返し適用することで、\(A_{n}\) は \(A_{n-1}\) を \(x+1\) 個合成した$$\begin{align}A_{n}(x) &= \underbrace{(A_{n-1} \circ A_{n-1} \circ \cdots A_{n-1} \circ A_{n-1})}_{x+1 \text{個}} (1) \\
&= A_{n-1}^{x+1} (1)\end{align}$$ の形で書けます。難しく見えますが、二つ目と三つ目の漸化式はこのことを厳密に書いただけです。

\(A_{n}(x)\) は \(n\) 層の再帰的な関数の合成によって定義されており、 \(n\) の増加に伴い、猛烈に大きくなります。
$$\begin{alignat}{3}
&A_1(x)&=&1+(\cdots+(1+(1+1))\cdots)&&= x+2 \\
&A_2(x)&=&2+(\cdots+(2+(2+1))\cdots)&&=2(x+3)-3 \\
&A_3(x)&=&2(\cdots(2(2+1))\cdots)-3&&=2^{x+3}-3 \\
&A_4(x)&= &\underbrace{2^{2^{\cdot^{\cdot^{2^{1+3}}}}}}_{x+1\text{個の}2}-3& &=\underbrace{2^{2^{\cdot^{\cdot^{2^2}}}}}_{x+3\text{個の}2}-3\\
\end{alignat}$$

逆関数を \(\alpha(y)=\min\{ n\ :\ A_n(1) > y \}\) と定義します。\(A_n(x)=A_{n-1}^x(1)\) を思い出すと、
$$\alpha(y) = \min \{\alpha_k(y) \leq 1\}$$
$$\alpha_k(y) = $$

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA