中央値の中央値
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/03/21 15:10 UTC 版)
中央値の中央値(ちゅうおうちのちゅうおうち、英: median of medians)とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。
- ^ マヌエル・ブラム; ロバート・フロイド; ヴァーン・プラット(英語: Vaughan Pratt); ロナルド・リベスト; ロバート・タージャン (1973). “Time bounds for selection”. Journal of Computer and System Sciences 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9 .
- ^ a b トーマス・コルメン(英語: Thomas H. Cormen); チャールズ・レイザーソン(英語: Charles E. Leiserson); ロナルド・リベスト; クリフォード・ステイン(英語: Clifford Stein) (2009) [1990]. アルゴリズムイントロダクション(英語: Introduction to Algorithms) (3rd ed.). MIT Press and McGraw-Hill. pp. 220. ISBN 0-262-03384-4
- 中央値の中央値のページへのリンク