ボツ回答
質問「要素の値の小さい順にｋ個までの要素を抽出するためのアルゴリズム」に、とんでもないウソ回答を書いてしまいました。
どんなのかというと、ここには書けないほど悲惨なアルゴリズムでした。
脳が寝ていたに違いありません(笑)
未オープンの間に気がついたのが幸いして、はてなスタッフ様に回答削除していただいて、事なきを得ました。
はてなスタッフ様、ありがとうございました。m(_ _;m
で、もしものとき用に用意していた、言い訳回答が無駄になりましたので、反省を兼ねてここに掲載しておきます。
あぁ!! 私の一回目の回答(回答4)は、激しく間違ってます(滝汗;;;
ごめんなさい、無視してください。m(_ _;;m
すみません、仕切りなおしをさせて下さい。
ご質問のアルゴリズムは、2重構造になります。
外側の構造は、配列X をスキャンするための単純なループです。
要素素がn個ですから、O(n)のオーダーですね。
内側の構造は、解を格納する為のコレクション(仮に大文字のK) を操作するための順序リスト作りです。
ここでは、
- (コレクションK の最大値より小さい) 新しい値の挿入
- そのとき k個を超えた(一番大きな値の)要素の削除
- 挿入・削除を効率よく行うためのコレクションKの逐次ソート
を行います。
お尋ねの件は純粋なアルゴリズムの話ですので、内側の構造で使うコレクションは、B-Treeか(2つめの回答に有ります)二分探索木が正解だと思います。(配列Xの持ち方や、Xの値の数、値のばらつき方等によります)
( B-Treeの説明 )
ただし、kの数が極端に少ない場合は、Tree作成のオーバーヘッドの影響が無視できなくなります。
環境や言語(ライブラリ)の実装にもよりますが、kが100個前後ならLinkedList、10個程度なら普通の配列を使って、線形探索した方が早いこともあります。
以上、お詫びと(大)訂正でした。m(_ _)m
