ダブリング

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /doubling#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /doubling#noredirect を利用してください。
name
ダブリング
short description
ダブリングとは、前処理をしておくことによって操作を複数回繰り返した結果を高速に求めるアルゴリズムのひとつ。事前に固定された関数 $f : N \to N$ に対して、関数 $f^0, f^1, f^2, f^4, f^8, \dots, f^{2^{\lfloor \log K \rfloor}}$ を繰り返し二乗法のようにして $O(N \log K)$ で事前に求めておく。すると、クエリとして与えられた $x \in N$ と $K$ 以下の自然数 $k$ に対して、$f^k(x)$ を $O(\log k)$ で求めることができる。これがダブリングである。ただし $N$ とは集合 $\lbrace 0, 1, 2, \dots, N - 1 \rbrace$ のことであり $f^k : N \to N$ は関数 $f^k(x) = \underbrace{f(f(\dots f(} _ {k ~\text{times}} x) \dots))$ のことである。