複雜的代碼段第2部分

的給出了下面的代碼片段的複雜性輸入尺寸 N個方面：複雜的代碼段第2部分

for(int i=0;i<n;i++) // n* 
    for(int j =1;j<=n;j=j*2) // n/2 (its half n, but I assume it still counts as n, or is it log(n)?) 
     a[i]=a[j-1]/2; // 1 

for(int i=0;i-n;i++) // n* 
    if(a[i] %2==0) // 1* 
     a[i]=2*a[i]; // 1

你從下往上開始。複雜性：n^2 + n它是O（n^2）嗎？

有什麼地方可以瞭解如何計算簡單算法的複雜性？

來源

2011-08-20 Evgeny C

如果您向我們展示您的答案有多遠，我們可以爲您提供更多幫助。 – rossum

我做到了。下面的代碼公式和在註釋中：// n代表複雜性，我認爲這條線是成立的。謝謝。 –

當你懷疑，

for(int j =1;j<=n;j=j*2)

這是O（LOGN），因爲每個迭代j被乘以2，所以總時間爲O（nlogn）。至於在哪裏看，我喜歡算法簡介，但任何優秀的教科書都足以滿足簡單算法的分析。

來源

2011-08-20 15:04:36

複雜的代碼段第2部分

回答

相關問題