循環迭代分析

請參閱下面的解決方案，我想要一些建設性的反饋意見。循環迭代分析

下面的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

循環迭代分析

回答

相關問題