2

実際にコードを実行せずに、アルゴリズムにかかるおおよその時間を計算する必要があります。

ハードウェアによっては完了するまでに数日または数週間かかるため、実際には完全なアルゴリズムを実行することはできません。本質的に対数のアルゴリズム。以下は、アルゴリズムの推定です。もちろん、ここにはロジックは含まれていません。

[n]2の累乗から始めます。これ[n]は大きな数です。

int baseTwo = 2;
double log = 0D;
BigInteger number = 0;
double exponent = 5000000; // 5,000,000.

while (exponent > 0)
{
    number = BigInteger.Pow(baseTwo, (int) exponent); // [baseTwo]=2 raised to the power [exponent].
    number = this.ProcessNumber(number, baseTwo); // Returned number will be slightly smaller than what went in.
    exponent = BigInteger.Log(number, baseTwo); // The Base 2 Log to calculate the slightly decreased exponent (if exponent was 38762, then the result would be 38761.4234 for example).
}

private BigInteger ProcessNumber(BigInteger number)
{
    double rand = 0;
    BigInteger result = 0;

    rand = Random.Next(51, 100) / 100D; // Anywhere between 51% to 99%.
    result = number * rand; // [result] will always be less than [number] but more than half of [number].

    return (result);
}

指数はゼロに向かって反復しているため、反復ごとの時間は反復ごとに自然に減少します。

  • マシンでの最初と最後の反復の実行時間を考慮して、合計時間を計算する方法はありますか?
  • そうでない場合は、[指数] に 5,000,000、4,500,000、4,000,000 などの個別の範囲を取り、そこから計算できますか?
4

2 に答える 2

3

最初と最後の反復だけでは十分な情報が得られません。たとえアルゴリズムの極限効率を知っていたとしても、反復ごとの時間が限界効率に正確にスケーリングされるという保証はないからです。たとえば、関数が大きな n の制限で O(n^2) だった場合 (この場合ではないことはわかっていますが、これは説明のためだけです)、実際のコードのステップごとの実際の時間1*log(n) + 10^-6*n + 10^-24*n^2のようなものだった場合、選択した n の範囲で n^2 の動作が見られない場合があります。したがって、最初と最後の反復で 2 つのポイントが得られますが、それらの間に線を引く方法を知る方法はありません。

提案どおりに定期的にデータをサンプリングし、それをエクスポートしてフィッティングおよび/または数値積分することができます。しかし、おおよその合計時間 (おそらく +/-10%) だけを知る必要があると仮定すると、次の行に沿って何かを行うだけで十分なはずです... 疑似コード:

totaltime = 0;
for i := 0 to 5 do
begin
  starttime = now;
  for j := 0 to 10 do
    run algorithm(i*10^6+j)
  endtime = now;
  totaltime := totaltime + 10^5*(endtime - starttime);
  writeln('10 iterations near ', i*10^6, ' takes ', endtime - starttime, ' seconds');
end;
writeln('approximate time for complete algorithm to run is', totaltime);

..そして、これを書くのにかかった時間よりも短い時間で答えを得ます。

于 2012-08-13T22:12:32.290 に答える
1

アルゴリズムを小さくして入力を増やし、グラフを作成することをお勧めします。

グラフの曲線は突然変化する可能性がありますが、このようなものについては、封筒の裏側で多くの計算を行うよりも、おそらく優れた指標です。

于 2012-08-13T21:54:28.780 に答える