4

週末にシミュレーションを実行する必要があります。シミュレーションをできるだけ大きくして、できるだけ説明的なものにしたいのですが、仕事に戻るまでにシミュレーションが終了せず、このソフトウェアでの作業を続けることができなくなりたくありません。

アルゴリズムは、いったん開始すると完了する必要があり、そうしないと実行する意味がまったくありません。

階乗、n^4、および n^2 で実行されるシミュレーションの個々の要素

   n:
<= 6  =         0ms
   7  =         8ms
   8  =        91ms
   9  =     1,089ms
   10 =    14,666ms
   11 =   197,288ms
   12 = 3,091,739ms

WolframAlpha hereでこれらのサンプルに曲線を当てはめました。私が懸念している 2 つのことは、まず n^4 コンポーネントが負であることです。これは、実行時間に寄与する要因であるため、意味がありません。もう 1 つのことは、過去に同様の状況で実行時間を見積もろうとしたことがあり、私の推測は通常かなり外れているということです。

このように入力サイズに基づいてアルゴリズムの実行時間を推測した経験のある人はいますか?

4

2 に答える 2

1

外挿が失敗する理由:
元の範囲外の値を推定しようとしている場合、外挿はかなり外れていることが予想されます。
少なくとも多項式外挿では、誤差は、ポイントからすべてのサンプル ポイントまでの距離と、範囲内の関数の n 次導関数の最大値の積の関数です。この距離が大きい場合、(距離と最大導関数の積) は高くなることが予想されます。

n^4 コンポーネントは、「観測」を説明できる最良の関数を示しているため、負の値を示しています。

サンプル ゾーンからの実行時間を見積もるには、外挿の使用を避けることをお勧めします。既知のサンプルの「快適ゾーン」から外れると、定義上、それらは適切な推定値ではありません。

代替案を考えています:
(コードを静的に分析することにより) 定数の大まかな見積もりを見つけようとします-主に-階乗コンポーネントの定数が非常に小さく、残りの定数が非常に大きいかどうかを確認したいと思います。そうでない場合、n^2 および n^4 コンポーネントは無視できます。これらは階乗コンポーネントと比較して無視できるため、分析がはるかに簡単になります。

PS提供された動的データを見ると、実行時間の差が階乗因子に急速に収束してf(12) ~= 12* f(11)いるように思われるため、関数を階乗として分析し、推定などは合理的な仮定のようです。
安全を確保したい場合は、 を使用できますf(n) = (n + d) * f(n-1)。ここで、d は事前定義された正の定数です (例: ) d = max{0,f(11)/f(10) - 11}。

PS2:
factorial の動作は非常に急進的であるため、シミュレーションを繰り返し実行することがf(1) + f(2) + ... + f(n)できf(n)ますn > 10。そうすることで、オフィスに戻ったときにそれを中止しますが、計算するのに時間をかけた結果が得られます。この動作はいつでも呼び出されます。

于 2012-06-21T06:09:43.210 に答える
1

一般に、O(N 4 ) がある場合、O(N 3 )、O(N 2 )、O(N)、および O(1)の用語も導入する必要があります。つまり、x 3、x 1、および x 0を曲線近似モデルに追加してみてください。

O(N!) があるこの特定のケースでは、非常に速く収束するように思われるため、私はアドバイスに従い、階乗部分のみを検討します。

ただし、いずれにせよ、実際に O(N!) がある場合は、推定する必要はありません。反復的な深化アプローチを使用してください。n=1,2,3,4,5,6,7... のケースをコンピューターに繰り返し実行させ、できる限り実行させます。

コンピューターの時間を無駄にしているように見えるかもしれませんが、それを分析すると、無駄な時間は取るに足らないものであることがわかります。たとえば、すでに n=12 であるため、n=13 の場合、必要な CPU C 13は 13*C 12、C 12 = 12*C 11などになります。測定値を導入すると、sum(C 13 ..C 0 )/C 13 = 1.082 となるため、0 から 13 までのすべての値に対して関数を実行すると、13 に対して実行するよりも 8% だけコストが高くなります。 N の値が大きいほど、このパーセンテージはさらに軽減されます。

更新:

複雑度レベルより下のすべてのべき乗に項を追加する必要がある理由:

複雑さが O(N 3 )の単純な 3 レベルのループを考えてみましょう。

void foo(int n) {
  int i, j, k;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      for (k = 0; k < n; k++)
        do_something(i, j, k);
}

foo(3);

do_something(i, j, k)が n 3回呼び出されることは明らかです。

しかし、実行されるすべての命令を最初から考慮すると、関数の出入り、スタックの設定、およびその他の低レベルのタスクが 1 回実行されるよりもわかります。i=0命令も 1 回実行されます。これらは、n 0コストに対応する命令です。

命令i < nとは n 回呼び出されi++、j=0n 1項に対応します。

命令j < nとは n 2回呼び出され、n 2 項に対応j++します。k=0

まあ、など。

より複雑なケースも同じです。常に、複雑度レベルよりも下のすべての累乗に比例した回数実行される命令があります。

の測定に関してC(0) = 0は、タイミングが十分に正確でないことが問題です。それは非常に小さいかもしれませんが、決して絶対的な 0 ではありません。

最後に、カーブ フィッティングが機能しない場合は、N が原因です。その場合のように、命令も実行されます (n-1)! 回、および (n-2!) 回など。

于 2012-06-21T07:04:41.833 に答える