計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ ..

765:デフォルトの名無しさん
08/10/29 18:05:02
>>762
上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい．
計算量は全データ数を n とすれば O(n log k)．
k は高々 n なので，計算量はデータ数によらずソートするよりも良い．

実用的にはデータの分布に依存するので，実測しないと何とも．

次ページ