循环迭代分析

请参阅下面的解决方案，我想要一些建设性的反馈意见。循环迭代分析

下面的O（n）中的运行时间是多少。

int a = 0; 
int k = n*n*n; //n^3 
while(k > 1) 
{ 
    for (int j=0; j<k; j++) //runs from 0->k 
    { a--; } 
k = k/2; //divides by 2 each iteration 
}

每次for循环运行时，它会给出一个常数x k。

= 0xn^3 + 1x（n^3/2）+ 2x（n^3/4）+ ... + nx（n^3/2^n）
= n^3（0+ 1/2 + 2/4 + ... + n/2^n）< - 有人知道我怎么能进一步简化这个？

编辑：我假设我们会用等差数列莫名其妙....

来源

2012-06-20 warpstar

您的推理是有缺陷的：序列不是0xn^3 + 1x（n^3/2）+ 2x（n^3/4）+ ...，而是1xn^3 + 1x （n^3/2）+ 1x（n^3/4）+ ... = n^3×（1 + 1/2 + 1/4 + 1/8 + ...）= 2×n^3。 –

让我们用K个第一

在第一while循环，for循环的第二运行一段时间k次

循环，for循环运行K/2倍

在第三

while循环中，对循环运行K/4倍

...

所以在总运行（K + K/2 + K/4 + K/8 + ... + 1）倍

提取物中的k之后，它的K *（1 + 1/2 + 1/4 + 1/8 + ... + 1/K）

随着k增加，括号中的部分成为2，我们可以忽略

变化k以N R个3，其结果是O（ n^3）

来源

2012-06-20 03:01:16 xvatar

它似乎并没有真正考虑到嵌套for循环？你为什么乘以（1 + 1/2 + 1/4 + 1/8 + ... + 1/K）by-> k？ – warpstar

@warpstar对不起，如果它不明确，请参阅我的更新 – xvatar

确实愚蠢的算术错误，但仍然不能解释，你没有考虑到嵌套for循环权？所以对于每个值1 + 1/2 + 1/4 + 1/8 + ... + 1/k，您必须考虑for循环运行时间。（这看起来像你还没有完成）...纠正我，如果我错了。 – warpstar

我想你可以通过下面的正式方程式来想出增长复杂性的顺序：

enter image description here

来源

2014-04-05 16:40:42

循环迭代分析

回答

相关问题