4

コード（メソッド関数など）の計算上の複雑さを自動的に計算するプログラム/スクリプトを知っている人はいますか?

そうでない場合、それをサポートする良い方法 (デザイン パターン、アルゴリズムなど) はありますか?

私はこれを一般的にやろうとしているわけではありません。

ほとんどの場合、入力、それを実行するアルゴリズム、停止を構成するものはわかっています。この方法で 2 つ以上のアルゴリズムを比較しようとしています。

例えば

algo #1 - 2x^2 + 10x + 5

algo #2 - 5x^2 + 1x + 3

どちらのアルゴリズムも O(N^2) です。ただし、アルゴ #2 は短期的には優れていますが、アルゴ #1 は長期的に優れています。

4

2 に答える 2

1

問題を一般的に解決するアルゴリズムを開発することは不可能ですが、いくつかの入力例に対してソフトウェアの複雑さを計算するアルゴリズムを作成することはできます。

私が参照できる唯一のソフトウェアはTrend-Profilerです。ただし、結果よりもアルゴリズムに関心がある場合は、ソフトウェアとそのアルゴリズムについて説明している論文がここにあります。

于 2012-10-04T15:48:44.760 に答える
0

異なる量の入力でアルゴリズムをサンプリングするほうがよいのではないでしょうか? 入力ごとに計算された時間を使用して、複雑度関数を概算し、どのアルゴリズムがどの段階で優れているかを判断できます。

于 2012-10-04T16:27:41.177 に答える