Big-Oの複雑さに対するコード分析の実行を決定できるツールはありますか？

Question

そこには何も見たことがありませんが、「n」を定義するのが難しいと思います。一般に、複雑な関数を分析するためには、定義する変数が1つまたは2つ以上あるためです。

循環的複雑度の分析ツールはありますが、時間（および/または空間）複雑度の分析ツールはありますか？もしそうなら、どちらか、そうでないなら、なぜですか？実行不可能ですか？不可能？誰かがそれに気付いていないのですか？

理想的には、アプリケーションの全体的な複雑さ（考えられるさまざまな「n」を定義する）およびアプリ内の各メソッドのようなものがあります

編集： Haltingの問題のため、正確な解決は不可能のようですが、何らかのヒューリスティック近似が可能ですか？実用的な目的のためには、優れたプロファイラーがはるかに有用な情報を提供することを認識していますが、それは興味深い問題のようです。

また、プログラムの特定のサブセットに対して計算するものはどうですか？

Answer 1

残念ながら、停止の問題 ...

と呼ばれるこの問題があります。

Answer 2

いいえ、停止の問題のため、これは不可能です。

アプリケーションを改善するためにこれを行いたい場合は、代わりにプロファイリングを検討してください。実際に最も時間がかかっているものを特定することができます。この方法では、小さなデータセットでのみ実行されるO（n ^ 3）アルゴリズムの最適化に時間を費やすことはありません。

Answer 3

いくつかの注意点：

実際のコンピューターはほぼ確定的な有限状態マシンであるため、停止の問題は実際には実際的な制限ではありません。実用的な制限は、あなたが待っていると感じるよりも実行に時間がかかり、分析のブルートフォース方法を排除するアルゴリズムです。

アルゴリズムの複雑さの大まかなアイデアを得るために、ランダム入力のセットでいつでもそれを実行し、かかった時間を測定できます。次に、データ全体に曲線をプロットします。

アルゴリズムの時間の複雑さの分析はかなり複雑になる可能性があり、いくつかの創造的な手順が必要です。 （クイックソートの分析例を参照してください）。この問題は、論理定理の証明とプログラム検証に密接に関連しています。複雑さの半自動ソリューションを可能にする有用なツール、つまり、人間からのヒントが与えられたソリューションを体系的に検索するツールを構築することは可能かもしれませんが、それは確かに簡単ではありません。

Answer 4

これを行うためのツールを見たことはありませんが、プロファイリングツールを使用して、ボトルネックがどこにあるのかをよりよく把握します。それは常に明白ではないので、実際には非常に少ない時間がかかり、逆もまた同様であると私は思っていました。 .NETの世界では、 ANTS と< href = "http://www.jetbrains.com/profiler/" rel = "nofollow noreferrer"> JetBrains ツール。