3

現在のプロジェクトでは、Javaで記述されたアルゴリズムの複雑さを測定しています。漸近的な複雑さ（期待される結果）で操作し、実際の操作数と比較して期待値を検証したいと思います。操作ごとにインクリメントを使用することは、私には少し不器用に思えます。運用の複雑さを測定するためのより良いアプローチはありますか？

ありがとう

編集：詳細

  • アルゴリズムは異なるマシンで実行される可能性があります
  • 分割統治アルゴリズムの一部は事前にキャッシュされている可能性があるため、手順が予想よりも高速になる可能性があります
  • また、漸近的な複雑さを考慮していない乗法定数（または加法定数）を見つけることも重要です。
4

3 に答える 3

2

CPU時間を測定しない特別な理由はありますか？タイムユーティリティまたはプロファイラーが数値を取得します。十分な範囲の入力を使用して各アルゴリズムを実行し、費やされたCPU時間（実時間ではない）をキャプチャするだけです。

于 2012-06-03T17:53:03.100 に答える
1

実行時間を測定する実際のコンピューターでは、getCurrentTimeMillis（）を使用します。Nパラメータを変更して、確実な統計を取得します。エラー推定を行います。基本的な最小二乗法で問題ありません。

アルゴリズムの演算をカウントすることは問題ありませんが、使用が制限されています。さまざまなプロセッサがさまざまな速度で処理を実行します。実装されたアルゴリズムによって実行された式またはステートメントの数を数えることは、ほとんど役に立たないです。アルゴリズムでは、これを使用して微調整の比較を行うことができます。実装では、これはもはや当てはまらず、コンパイラ/ JIT//CPUのトリックが支配的になります。

適切な測定を行う場合、漸近的な動作は計算された/予想されたものに非常に近いはずです。

于 2012-06-03T19:02:01.080 に答える
1

ByCounterは、Javaを（複数のクラスにわたって）インストルメント化し、実行時にJVMによって実行されるバイトコードの数をカウントするために使用できます。

于 2014-07-10T14:56:46.517 に答える