↓ 勉強し直しました ↓
union-find の計算量解析で出てくる \(\alpha(n)\) というのがありますね。 Ackermann 関数の逆関数として知られるやつです。
競プロ er の多くは、次のような認識をしていると思います。
- 計算量に \(\alpha(n)\) が出てくるなら union-find が関係する以外ないと思っている*1
- なぜ union-find でそうなるかはよく知らない
- どういう解析で \(\alpha(n)\) が出てくるのかわからない
- \(\alpha(n)\) がどんな性質を持っているかもあまり知らない
- 実質定数だと思っている
最近、少しお勉強する機会があったので、紹介してみます。 えびちゃんもまだちゃんと仲よしになったわけではないです*2。
\(\star\) 演算子の導入
唐突ですが、\(\star\) 演算子というのを導入します。 関数 \(f(n)\) に対して、次のような漸化式で定義されます。 ただし、\(n > 1 \implies f(n) < n\) とします。
\[ f^\star(n) = \begin{cases} 0, & \text{if }n \le 1;\\ 1 + f^\star(f(n)), & \text{otherwise}. \end{cases} \]
DP に慣れている人は読みやすいと思いますが、「与えられた \(n\) に \(f\) を適用して \(1\) 以下にするために必要な、最小の適用回数」を返します。 例を挙げてみます。
| \(f(n)\) | \(f^\star(n)\) |
|---|---|
| \(n-1\) | \(n-1\) |
| \(n-2\) | \(n/2\) |
| \(n/2\) | \(\log(n)\) |
| \(\sqrt{n}\) | \(\log(\log(n))\) |
| \(\log(n)\) | \(\log^\star(n)\) |
使い道の例
分割統治を例に出します。
サイズ \(n\) の問題があり、これをサイズ \(f(n)\) の問題 \(n/f(n)\) 個に分け、その結果を高々 \(a\cdot n\) 時間で合わせるときの計算量 \(T(n)\) を考えてみましょう。
\[ \begin{aligned} T(n) \le \begin{cases} 0, & \text{if }n\le 1;\\ an + \frac{n}{f(n)}\cdot T(f(n)), & \text{otherwise}. \end{cases} \end{aligned} \]
これを順に展開していくと、次のようになります。
\[ \begin{aligned} T(n) &\le an + \frac{n}{f(n)}\cdot T(f(n)) \\ &\le an + \frac{n}{f(n)}\cdot \left(a\cdot f(n) + \frac{f(n)}{f(f(n))} \cdot T(f(f(n)))\right) \\ &\le an + an + \frac{n}{f(f(n))} \cdot T(f(f(n))) \\ &\le \dots \\ &\le an + \dots + an + \frac{n}{f^k(n)} \cdot T(f^k(n)) \end{aligned} \]
\(n\) に \(f\) を \(k\) 回適用すると \(1\) になるとします。 \(f^k(n) = 1\) のとき、\(T(f^k(n)) = 0\) となることに注意します。
このとき、\(k\) 個の \(an\) があるので、次のように書けることがわかります。
\[ T(n) \le an\cdot f^\star(n). \]
\(\alpha(n)\) の定義
さっきの表の一部を抜粋して再掲します。
| \(f(n)\) | \(f^\star(n)\) |
|---|---|
| \(n-2\) | \(n/2\) |
| \(n/2\) | \(\log(n)\) |
| \(\log(n)\) | \(\log^\star(n)\) |
ある \(f\) に複数回 \(\star\) を適用した場合の挙動が気になりますね。
そこで、\(\alpha_0(n) = n-2\) とし、\(\alpha_{k+1}(n) = \alpha_k^\star(n)\) と定義します。 念のため補足すると、\(n\) に \(\alpha_k\) を \(\alpha_{k+1}(n)\) 回適用すると初めて \(1\) 以下になるということです。
\[ \begin{aligned} \underbrace{\alpha_k(\alpha_k(\dots(n)\dots))}_{\alpha_{k+1}(n)-1\text{ times}} \gt 1,\\ \underbrace{\alpha_k(\alpha_k(\alpha_k(\dots(n)\dots)))}_{\alpha_{k+1}(n)\text{ times}} \le 1.\\ \end{aligned} \]
そして、\(\alpha(n)\) を次のように定義します*3。 \[ \alpha(n) = \min\{k: \alpha_k(n)\le 2\}. \]
\(\alpha_k(n)\) が \(2\) 以下になるような最小の \(k\) を \(\alpha(n)\) とします。 \(2\) である理由は、\(n\ge 4\) に対して \(\alpha_k(n)\) の最小値が \(2\) であるためです。
値の求め方がわかったことで、以前よりは \(\alpha(n)\) が身近に感じられてきませんか？ イメージがつかなければ、手などで計算してみてください。
資料の紹介コーナー
書くのが大変になってきたので、資料の紹介コーナーに移ります。 英語のものばかりですが、英語自体は難しくないと思います。
- 図がたくさんある
- 静的な区間モノイド積が \(\langle O(n\alpha(n)), O(\alpha(n))\rangle\) で解ける話が書いてある
- disjoint sparse table は \(\langle O(n\log(n)), O(1)\rangle\)
- \(\langle O(n), O(\alpha(n))\rangle\) でできるらしい
- union-find の計算量解析も載っている
- 上の定義とは少し異なる \(\alpha(n)\) が用いられている（後述）
- \(\alpha(n) = o(\alpha_k(n))\) などが載っている
Weak Epsilon-Nets, Davenport–Schinzel Sequences, and Related Problems
- 上のリンク先の記事を書いた人の D 論っぽい
- 1 章と Appendix A に \(\alpha(n)\) の話がある
- \(\star\) を用いて定義した \(\alpha(n)\) が Ackermann 関数の逆関数になるのは、帰納的に簡単に示せると書かれている
- \(\alpha(n)\) の亜種（定義が若干異なる）はいくつかあるが、漸近的には同じであることを示す手法が書かれている
- この辺よくわかってません
- あとでよむ
おわり
ほぼ丸投げ記事ですが、興味を持つ人がいてくれたらうれしいかなと思います。
