文献

J-GLOBAL ID：201602012017732213   整理番号：74A0222139

中央値を計算する時間の限界

Linear time bounds for median computations.

著者 (5件)： BLUM M ,  FLOYD P W ,  PRATT V ,  RIVEST R L ,  TARJAN R E
資料名： Proc Annu ACM Symp Theory  (Proceedings of the Annual ACM Symposium on Theory of Computing)
巻： 4th  ページ： 119-124  発行年： 1972年 
JST資料番号： D0804A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： n個の数の中からi番目に大きい数を求めるのに必要な比較の回数の上界と下界を示した。一度に二つの数の大小を比較するが,iが1の場合は最大値を求めることになり,比較の回数はn-1になる。iがn/2の場合は中央値を求めることと同じである。一般にi番目を求めるのに必要な比較の上界は103n/18,下界はn+min(i,n-i+1)+log₂(n)-4を証明した。i番目を求めるアルゴリズムは,まず全体の数をグループに分け,各グループ内で大きさの順に並べる。つぎに全体の中央値を求めて,不必要な数を捨てる。この手続きをくり返して残った数の個数が一定以下になったところで最終決定する;写図3参5

シソーラス用語： オペレーションズリサーチ

タイトルに関連する用語 (3件)： 中央値 ,  計算 ,  限界