準線形時間での選択のためのデータ構造使用

ウィキペディア小見出し辞書

準線形時間での選択のためのデータ構造使用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 14:22 UTC 版)

「選択アルゴリズム」の記事における「準線形時間での選択のためのデータ構造使用」の解説

整列されていないデータのリストがあるとき、最小値を求めるには全要素を調べる必要があるため（さもなくば最小値を見逃す可能性がある）、線形時間 (Ω(n)) を必要とする。リストを作成する際に全データが常に整列するようにすれば、k 番目に大きい値の選択も簡単になる。しかし、そのためにはリストの途中へのデータの挿入に線形時間を必要とする（2つのリストのマージと同様である）。 準線形時間で順序統計量を求める戦略は、データを選択を行うのに適したデータ構造に格納するものである。そのようなデータ構造として木構造ベースのものと度数分布表がある。 最小値（または最大値）だけが必要な場合、優先度付きキューが適している。これは最小値（または最大値）を一定時間で探すことができ、他の挿入などの操作も O(log n) かそれよりよい性能を示す。より一般的には平衡2分探索木を使えば、要素の挿入も k 番目に大きい値の選択も O(log n) の時間で可能である。各ノードには配下に何個のノードがあるかをカウントした値を格納しておき、どのパスを辿るかを決定するのに使用する。この情報はノード（つまり新たなデータ）を追加したとき、接続される上位ノード群だけを修正すればよいので O(log n) の時間で済む。また、木の回転はそれに関わるノード群だけに影響する。 別の単純な戦略として、ハッシュテーブルのようなコンセプトに基づくものがある。データが取りうる値の範囲が予め分かっている場合、それを h 個の部分に分け、h 個の格納場所を設定する。要素を新たに挿入する際、その値が含まれる範囲に対応する格納場所にそれを置く。最大値や最小値を探すには、空でない格納場所を大きいほうからか小さいほうから探していき、その格納場所の中で最大値や最小値を探せばよい。一般に k 番目の要素を探すには、各格納場所に入れた要素数をカウントしておき、端からその値を加算していって k 番目を含む格納場所を探す。そして、その格納場所内の要素群から必要な要素を線形時間アルゴリズムで探し出せばよい。 h のサイズをおよそ sqrt(n) としたとき、データの分布がほぼ一様であれば、この方式による選択は O(sqrt(n)) の時間になる。しかし、データが狭い範囲に固まって出現すると（クラスタリング）、この手法では1つの格納場所に多大な要素が格納されることになってしまう（クラスタリングはハッシュ関数をうまく設定することで排除できるが、k 番目に大きい値をばらばらにハッシュされた中から探すのは現実的でない）。さらにハッシュテーブルと同様で、この方式では要素数 n が増大して h2 より大きくなった場合に、効率を改善するために再構成（つまり h を大きくする）する必要がある。この方式はデータ数が分かっている場合の順序統計量を探すのに適している（例えば学生の成績の統計処理など）。各格納場所の値の範囲を 1 としてそれぞれに要素数をカウントするようにするのが最も優れている。そのようなハッシュテーブルは要約統計量でデータを分類するための度数分布表に似ている。