中央値を線形時間で選択するアルゴリズムについて | NHN テコラス Tech Blog | AWS、機械学習、IoTなどの技術ブログ

こんにちは。データサイエンスチームのtmtkです。 この記事では、中央値を線形時間で選択するアルゴリズムを知って驚いたという話をします。 はじめに 最近、T. コルメン他『アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学』（原著：『Introduction to Algorithms』）を始めのほうだけ読みました。わかりやすく書かれており、とてもいい本だと思います。 この本の9.3節では「線形最悪時間選択アルゴリズム」というものが紹介されています。これはn個の要素をもつ集合のi番目に小さい要素を計算量で計算するアルゴリズムです。この記事では、このアルゴリズムを紹介します。 プログラミング言語としては、Python 3で説明します。 最大値の線形時間選択アルゴリズム 最大値を計算するアルゴリズムを考えてみましょう。これは、上で述べた問題でi = nの場合に対応