今回は選択アルゴリズムの紹介です。 これは、配列からk番目に小さい数を線形時間で 探しだすクイックセレクト(Quick Select)という クイックソートの派生アルゴリズムです。 問題 ソートされていないa1からanまでの数字がn個あり、 その中からk番目に小さい…

クイックセレクト(Quick Select)

世界高校生プログラミング大会IOIも開催されるというので、今回はアルゴリズム解析ネタです。と言っても、昔のノートを引っ張り出してきただけっｹﾞﾌﾝｹﾞﾌﾝ・・・と、とりわけ、再帰プログラムの実行時間の計算に使われる分類定理についてです。 その前に アル…

分類定理(master theorem)