翻訳と辞書
Words near each other
・ 中央会計隊
・ 中央住宅
・ 中央体
・ 中央信号場
・ 中央信用組合
・ 中央信用組合 (曖昧さ回避)
・ 中央信託局
・ 中央信託銀行
・ 中央倉庫
・ 中央値
中央値の中央値
・ 中央倶楽部
・ 中央僧伽大学校
・ 中央優良運転者免許更新センター
・ 中央儲備銀行
・ 中央児童福祉審議会
・ 中央党
・ 中央党 (スウェーデン)
・ 中央党 (ドイツ)
・ 中央党 (ノルウェー)


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

中央値の中央値 : ウィキペディア日本語版
中央値の中央値

中央値の中央値(ちゅうおうちのちゅうおうち、)とは、に基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。
このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、(漸近的な)おおよその中央値選択アルゴリズムを使って、(漸近的な)一般値選択アルゴリズムを構築したものである。
このアルゴリズムは、マヌエル・ブラムらによって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。
== 概要 ==
クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素がn個の場合に\Omicron(n)の計算時間を必要とする。そのためクイックセレクト全体の計算量は、
* もし探索対象の要素数を(一定の割合で)指数関数的に減少させられるなら、等比級数と1段の計算量(\Omicron(n))の積、つまり線形時間\Omicron(n)となる。
* しかし、要素数の減少がとても遅い(例えば、減少する要素数が一定、最悪の場合1つずつしか減らないような線形減少の)場合、各段の計算量の線形和となり、2次時間\Omicron(n^2)となる(三角数は2次となる)。
最悪時間となる場合は、例えば、各段階でピボット値として最小値を選んでしまう時である。これは、既に降順に並び替え済みの配列に対して、最初の要素をピボット値として選択してしまうと実際に起こりうる。
つまり、もし各段階で一貫して「良いピボット値」を選択し続けられるなら、このような最悪の場合を回避することができ、最悪の場合でも線形時間の性能となる。この「良いピボット値」では、全ての要素を一定の割合でより大きい値と小さい値に分割することができ、つまり探索対象の要素数を一定の割合で減らすことができ、ゆえに要素数が指数関数的に減少して、全体的な計算時間は線形のままとなる。
中央値は、そのような「良いピボット値」であり、各段階で探索対象を半分ずつに減らすことができる。ゆえに、もし中央値を線形時間で計算できるなら、各段階では線形時間しか増えないので、全体の計算量は線形時間のままとなる。
中央値の中央値アルゴリズムでは、正確な中央値ではなく、代わりに、30から70パーセンタイルの間(第4十分位数の中間)点であることが保証されたおおよその中央値を使用する。そのため、探索対象の要素数は各段階で一定の割合(最小で30%)で減少する(つまり最大で70%が残る)。
一方、ピボット値計算の増加量は各段階では線形となる(元の探索対象の要素数の20%の要素に対する再帰と、線形時間の和)。よって、各段階で問題の要素数は元の要素数の90%(20%+70%)という一定の割合で削減されるので、全体としての計算量は、要素数nに対して線形\Omicron(n)である(線形性の厳密な証明は後述)。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「中央値の中央値」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.