アルゴリズムオタク
at TECH
[
2ch
|
▼Menu
]
■コピペモード
□
スレを通常表示
□
オプションモード
□このｽﾚｯﾄﾞの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
次ページ
最新レス表示
スレッドの検索
類似スレ一覧
話題のニュース
おまかせリスト
▼オプションを表示
レスジャンプ
mixiチェック！
Twitterに投稿
オプション
しおりを挟む
スレッドに書込
スレッドの一覧
暇つぶし2ch
5110日前に更新/245 KB
担当:undef