半分全列挙

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /meet-in-the-middle#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /meet-in-the-middle#noredirect を利用してください。
name
半分全列挙
short description
半分全列挙とは、組合せについて処理するときに使えるテクニックのひとつ。すべての要素を考えたときの組合せの全体は列挙するには多すぎるが、半分程度の数の要素に制限して考えたときの組合せであれば列挙できる、という場合に利用可能である。要素の全体をそれぞれ半分程度の大きさのふたつのグループに分け、それぞれのグループについて組合せを全列挙し、それらふたつの結果を組み合わせて全体に対する結果を得る。そのまま全列挙したときの計算量が $O(f(N))$ であるとき、半分全列挙を行ったときの計算量はたとえば $O(\sqrt{f(N)})$ や $O(\sqrt{f(N)} \log f(N))$ などになる。これを利用するアルゴリズムの代表的なものに baby-step giant-step がある。
time complexity
たとえば $O(n)$ のものが $O(\sqrt{n} \log n)$ になる

関連項目

外部リンク