9

アルゴリズムが何回反復するかを確認するためにカウンターを保持することによってそれを行うことができますか、それとも期間を記録する必要がありますか？

4

6 に答える 6

11

現在受け入れられているものは、実験的に測定された時間をそれらを近似する関数で何らかの形で適合させることができない限り、理論的な推定を提供しません。この答えはあなたにそれをするための手動のテクニックを与えて、そのギャップを埋めます。

まず、アルゴリズムの理論的な複雑さの関数を推測します。また、ますます大きな問題について、実際の複雑さ（操作の数、時間、または実用的であると思われるもの）を実験的に測定します。

たとえば、アルゴリズムが2次であると推測するとします。時間を測定（言う）し、推測された関数に対する時間の比率（n ^ 2）を計算します。

for n = 5 to 10000 //n: problem size
  long start = System.time()
  executeAlgorithm(n)
  long end = System.time()
  long totalTime = end - start

  double ratio = (double) time / (n * n)
end

。n無限に近づくにつれて、この比率は...

  • ゼロに収束しますか？次に、あなたの推測は低すぎます。より大きなもので繰り返します（例：n ^ 3）
  • 無限に発散しますか？次に、あなたの推測は高すぎます。小さいもので繰り返します（例：nlogn）
  • 正の定数に収束しますか？ビンゴ！あなたの推測はお金にあります（少なくともnあなたが試したのと同じくらい大きな値の理論的な複雑さを概算します）

基本的に、これは大きなO表記の定義を使用します。つまり、f(x) = O(g(x)) <=> f(x) < c * g(x)-f(x)はアルゴリズムの実際のコストでg(x)あり、推測でcあり、定数です。f(x)/g(x)したがって、基本的には、実験的に;の限界を見つけようとします。あなたの推測が実際の複雑さに当たる場合、この比率は定数を推定しcます。

于 2010-10-21T00:33:19.933 に答える
6

アルゴリズムの複雑さは次のように定義されます (次のようなもの:)

アルゴリズムが入力サイズの関数として実行する操作の数。

したがって、さまざまな入力サイズでアルゴリズムを試して (つまり、並べ替えの場合 - 10 個の要素、100 個の要素などを並べ替えてみてください)、アルゴリズムが実行する各操作 (代入、インクリメント、数学演算など) をカウントする必要があります。

これにより、適切な「理論上の」見積もりが得られます。
一方、実際の数値が必要な場合は、プロファイリングを使用してください。

于 2010-10-20T19:15:00.643 に答える
2

他の人が述べたように、理論的な時間の複雑さは、アルゴリズムによって実行される CPU 操作の数の関数です。一般に、プロセッサ時間は、モジュロ定数の適切な近似値である必要があります。ただし、実際の実行時間は、次のようなさまざまな理由により異なる場合があります。

  1. プロセッサ パイプラインのフラッシュ
  2. キャッシュミス
  3. ガベージ コレクション
  4. マシン上のその他のプロセス

十分な数の統計サンプルを使用して、コードがこれらのことのいくつかを体系的に発生させていない限り、観測された実行時間に基づいて、アルゴリズムの時間の複雑さについてかなり良い考えを持っているはずです。

于 2010-10-21T04:11:52.963 に答える
1

最良の方法は、アルゴリズムによって実行された「操作」の数を実際に数えることです。「操作」の定義はさまざまです。クイックソートなどのアルゴリズムの場合、2 つの数値の比較回数になります。

プログラムにかかる時間を測定して大まかな見積もりを得ることができますが、さまざまな要因により、この値は実際の数学的複雑さとは異なる可能性があります。

于 2010-10-20T19:18:18.610 に答える
0

はい。

実際のパフォーマンスと反復回数の両方を追跡できます。

于 2010-10-20T19:14:42.110 に答える
0

ANTS プロファイラーの使用をお勧めします。「実験的」データを使用してアプリを実行している間、この種の詳細が提供されます。

于 2010-10-20T19:17:30.717 に答える