- 309 名前：デフォルトの名無しさん mailto:sage [2007/11/24(土) 19:52:52 ]
- >>308
ちと文章が切れてるので何を言いたいか察しかねるが、
計算量係数ってことは O(n) で隠れてる定数部分を
評価したいんでしょ？ そのためには、たとえば
・対象はどう表現されているか（リスト，配列 etc）
・n として何を数えるか（比較，イテレータの移動，スワップ etc）
・それぞれどれくらいの計算コストの差があるか
なんか決まらないと、とても評価できない。
「実用上早い」ってのは知られてるけど、計算量の係数が
実際にどんくらい小さいかってのは不明。
あと、306 のコードは「C++ 風の擬似コード」じゃなかったの？
それで「実装は STL を見ろ」というのではあなたの言うところの
擬似コードの意味がよくわからないんだけれど。
それに STL の partition はアルゴリズムは全く決めてないから
例えば「gcc のどのバージョンの STL の実装」とか言わないと。
