そもそもpartitionを1回するだけで計算量はnかかるんじゃない？quickselectってほんとにそんなに計算量少ないの？疑問が湧いてきたので確かめてみる。 配列サイズをnとして、partitionの計算量はn-1だ。では、partitionをかけるべき配列サイズはどのように小…

実際の応用では、上記の(1),(2)の方法で十分な事が多いと思われる。しかしまぁ、他の方法も見てみよう。 3つ目の方法は、quickselectを使う方法である。quickselectは、配列のk番目の要素を少ないコストで見付けるアルゴリズムだ。配列のk番目を見付けたけれ…

実は、libstdc++のpartial_sort（破壊的操作を行う方）は、部分ソート(1)で紹介したようなアルゴリズムにはなっていなかった。次の様になっている。 先頭のm個の要素を使ってヒープを作る。そこから最後までは、ヒープの最初の要素(つまりルート)と配列の一…

まず、n個の配列をヒープとしてソートする。これは計算コストはnだ。次に、ヒープから最小のm個を取ってくる。popはlog nの操作なので、構築nとm回のlog nによる抽出で、計算量はn + m log nになる。これが伝統的なC++のSTLのpartial_sortのアルゴリズムらし…

長さがnであるような配列があったとしよう。そこから、上位m個の要素を取ってくる、という問題を考えたい。言い替えると、配列の中で上位のm個だけはソートされていることを保証してほしい、ということになる。（残りの要素はソートされていようがいまいが関…