weighted-union heuristic

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /weighted-union-heuristic#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /weighted-union-heuristic#noredirect を利用してください。
name
weighted-union heuristic
short description
weighted-union heuristic とは、ふたつの集まりの間で要素を移動させてひとつにまとめる操作を繰り返す際に、常に要素が少ない方から多い方へと移すようにすると計算量が落ちるというテクである。具体的には、大きさ $a$ のものを大きさ $b$ のものへと $O(a)$ かけてマージし (中身を移し) て大きさ $a + b$ のものを作るという操作を使って、大きさの合計が $n$ であるようないくつかのものをひとつにマージしてまとめたいというような状況において、合計の計算量 $O(n \log n)$ でこれが可能である。データ構造をマージする一般的なテクとも呼ばれる。