计算对数算法的时间

我需要计算算法在不实际运行代码的情况下所花费的大致时间量。计算对数算法的时间

我实际上无法让完整的算法运行，因为需要几天或几周才能完成，具体取决于硬件。本质上是对数的算法。以下是该算法的估计。当然，这里没有任何逻辑。

我们从2提高到[n]的力量，其中[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); 
}

由于指数向零迭代，每次迭代的时间自然会从一次迭代到下一次迭代。

给定我机器上第一次和最后一次迭代的执行时间，是否有计算总时间的方法？
如果不是，我们可以对[exponent]说5,000,000，4,500,000，4,000,000等等的谨慎范围，并从那里计算？

来源

2012-08-13 Raheel Khan

这似乎更像是一个数学问题，而不是编程问题。抽取一些样本，创建一个模型，并使用该模型预测结果。如果您没有碰巧访问专门的建模软件，Microsoft Excel对基本建模有一些体面的支持。 – Servy 2012-08-13 17:05:50

“我”定义在哪里？那应该是'exponent'吗？ – tlehman 2012-08-13 17:15:11

我会接受@Servy的建议。在合理大小的数据上运行一些实验，对其进行绘图，并为其拟合曲线。 – jeff 2012-08-13 17:58:08

即使您知道算法的限制性big-O效率，只是第一次和最后一次迭代都不会提供足够的信息，因为不能保证每次迭代的时间将严格按照极限效率。例如，如果你的函数在大n的极限（我知道它不是在这种情况下 - 但这只是为了插图的缘故）是O（n^2），但是实际代码的每一步的实际时间就像1 * log（n）+ 10^-6 * n + 10^-24 * n^2，你可能不会看到 n^2行为在你选择看的n的范围内。所以你在第一次和最后一次迭代时会有两个点，但没有办法知道如何画出它们之间的界限。

您可以按照您的建议定期采样数据，然后将其导出以进行拟合和/或数值积分。但是assumiong你只需要知道近似的总时间（+/- 10％也许），应当suficient做点什么沿... 伪代码行：

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-13 22:12:32 Penguino

我建议喂养你的算法小但增加输入，并做一个图形。

图表上的曲线可能会突然改变，但它们可能仍然是一个比许多这样的后台计算更好的指标。

来源

2012-08-13 21:54:28 user1277476

计算对数算法的时间

回答

相关问题