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

即使您知道算法的限制性 big-O 效率，仅第一次和最后一次迭代也不会为您提供足够的信息，因为无法保证每次迭代的时间会精确地扩展到限制效率。例如，如果您的函数在大 n 的限制中是 O(n^2) （我知道在这种情况下不是 - 但这只是为了说明），但实际代码每一步的实际时间类似于 1*log(n) + 10^-6*n + 10^-24*n^2，您可能看不到在您选择查看的 n 范围内的 n^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 回答