

ある計算量がわからないアルゴリズムがあったとします。  
そのアルゴリズムをどのように評価したらいいですか。

具体的な例だと`std::list<int>`の計算量を実験的に知りたいなどです。  
単純に実行時間やメモリ消費量を示すのではなく式として一般化するというところまでです。


CC BY-SA 3.0
2015-02-21T17:46:12.913
6881
2015-02-21T23:19:33.513
2015-02-21T23:19:33.513
question
計算量
実験的によって計算量を一般式化


前提として、アルゴリズムの計算量はアルゴリズムがわからないと算出できません。現実の実装での実行結果は、具体的な入力データに依存しますし、アルゴリズムそのもの以外の様々な要素の影響も受けるからです
(例えば動的メモリアロケートが必要な場合、アルゴリズムそのものの計算量に加えてメモリ管理のオーバヘッドも実行結果に出てきてしまうでしょう。)

その上で、ソースのないある関数が与えられた時に実用的な範囲での振る舞いをざっくりと調べたいのであれば、実際に使う範囲での色々な大きさの入力を食わせて実行時間をプロットし、おおざっぱにn,
nlogn, n^2など代表的な値でフィッティングしてみるしかないでしょう。

実験結果からではO(n^1.5)なのかO(nlogn)なのか判別し難い、ということはあり得ますが、 **使う範囲で** 区別できないのなら実用上
**区別する必要はない**
わけです。両者の違いはnがうんと大きくなれば重要ですが、現実に違いが出るデータを与えることはないわけですから。もちろん、こうして得られた値を「アルゴリズムの理論的な計算量」として使うことはできません。そこはちゃんと区別する必要があります。

「理論的に厳密な」計算量を実験的に求めることはできないけれど、「実用上必要な」計算量は実験結果からだいたい見積もることができる、ということです。


CC BY-SA 3.0
2015-02-21T20:15:17.713
6890
2015-02-21T20:24:59.367
2015-02-21T20:24:59.367
5258
5258
6881
answer