＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズム大辞典 at TECH

309:デフォルトの名無しさん
07/11/24 19:52:52
>>308
ちと文章が切れてるので何を言いたいか察しかねるが、

計算量係数ってことは O(n) で隠れてる定数部分を
評価したいんでしょ？そのためには、たとえば
　・対象はどう表現されているか（リスト，配列 etc）
　・n として何を数えるか（比較，イテレータの移動，スワップ etc）
　・それぞれどれくらいの計算コストの差があるか
なんか決まらないと、とても評価できない。

「実用上早い」ってのは知られてるけど、計算量の係数が
実際にどんくらい小さいかってのは不明。

あと、306 のコードは「C++ 風の擬似コード」じゃなかったの？
それで「実装は STL を見ろ」というのではあなたの言うところの
擬似コードの意味がよくわからないんだけれど。
それに STL の partition はアルゴリズムは全く決めてないから
例えば「gcc のどのバージョンの STL の実装」とか言わないと。

次ページ

続きを表示

1を表示