アルゴリズムオタクat TECHアルゴリズムオタク - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞのURL■項目テキスト966:デフォルトの名無しさん 08/08/18 01:27:24 STLのpartial_sortの計算時間って、要素数N、ソートする要素数をKとするとNlogKらしいんだけどなんでそうなるの？ http://stdcxx.apache.org/doc/stdlibref/partial-sort.html 967:デフォルトの名無しさん 08/08/18 01:37:51 std::partial_sortって確か内部的にヒープソートを使ってたはず。 968:デフォルトの名無しさん 08/08/18 01:40:14 要素数kのheap作成がO(K)で、その後(N-K)要素をpush/popするのに 一回あたりO(logK)というだけ？ 969:デフォルトの名無しさん 08/08/18 01:43:49 最悪の場合な。だから保証されている。 heap木を壊さないために必要。 970:デフォルトの名無しさん 08/08/18 01:44:00 Wikipediaのselection algorithmsのとこに載ってる、O(N+klogk)の変形quicksortの方が速そうだけど、 わざわざヒープを使ってるのには何か理由があるのかなぁ？ http://en.wikipedia.org/wiki/Selection_algorithm#Optimised_sorting_algorithms 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch