0

ユーザーが自分のプログラムファイル（.cs、.PHP、.java）をアップロードできるWebサイト（私のアカデミックプロジェクト）を作成しています.Webはプログラムをコンパイルし、時間と空間の複雑さを自動的に言うことができます。これは可能ですか？プログラムの複雑さをどのように計算できますか。プログラムの複雑さを見つけるための Java のコードはありますか? または、コンパイラ自体からこれらを見つけることができますか?

4

2 に答える 2

2

プログラムの時間と空間の複雑さを判断するのは難しい問題です。フィードバックが指摘しているように、一般的に、プログラムが終了するかどうかを指摘することさえできません。(これは停止問題として知られています)

プロジェクトを開始するには、たとえば GMetrics プロジェクトによって計算される循環的複雑度を調べることをお勧めします。

これにより、主題の探索を開始できます。

于 2012-07-13T06:32:20.200 に答える
2

プログラムに与える入力の種類がわかっていると仮定すると、プログラムを実際に実行することを連続して繰り返すことで、複雑さを見積もることができます。ただし、停止問題により、一般的なケースの静的解析は不可能です。

さまざまなサイズの入力セットに対してアプリケーションを複数回実行できる場合は、近似値を作成できます。

数字を並べ替える古典的なケースでは、アプリケーションで 2 つの数字のリストを並べ替え、次に 4、8、16、32 などと並べ替えることができます。基本的には、各実行のメモリと時間の要件をグラフ化します。基本的なカーブ フィッティングは、複雑さの増大を示します。

特定のアルゴリズムには、パフォーマンスが根本的に変化するポイントがある可能性があるため、これは厳密に正確ではないことに注意してください。このようなシステムは、漸近曲線と対数曲線、または指数曲線と多項式曲線など、「一見」似ているが大きく異なる特性を持つ成長の違いに惑わされることもあります。

于 2012-07-13T06:24:51.240 に答える