エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
ここにツイート内容が記載されます https://b.hatena.ne.jp/URLはspanで囲んでください
Twitterで共有ONにすると、次回以降このダイアログを飛ばしてTwitterに遷移します
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
こんにちは。データサイエンスチームのtmtkです。 この記事では、中央値を線形時間で選択するアルゴリズ... こんにちは。データサイエンスチームのtmtkです。 この記事では、中央値を線形時間で選択するアルゴリズムを知って驚いたという話をします。 はじめに 最近、T. コルメン他『アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学』(原著:『Introduction to Algorithms』)を始めのほうだけ読みました。わかりやすく書かれており、とてもいい本だと思います。 この本の9.3節では「線形最悪時間選択アルゴリズム」というものが紹介されています。これはn個の要素をもつ集合のi番目に小さい要素を計算量で計算するアルゴリズムです。この記事では、このアルゴリズムを紹介します。 プログラミング言語としては、Python 3で説明します。 最大値の線形時間選択アルゴリズム 最大値を計算するアルゴリズムを考えてみましょう。これは、上で述べた問題でi = nの場合に対応