爲什麼這個代碼的運行時效率O（n^2）？

-1

對不起，我是大O分析的新手。我需要一些幫助，這：爲什麼這個代碼的運行時效率O（n^2）？

我有下面的代碼段：

int sum; 
for (int i = 0; i < n; ++i) { 
    if (n < 1000)  
     sum++; 
    else  
     sum += foo(n); 
}

解決關鍵說，這是O（n^2）分析，但我不明白爲什麼。循環只交織一次，所以n^2從哪裏來？

另外一個我遇到的麻煩：

for (int i = 0; i < n + 100; ++i) { 
    for (int j = 0; j < i * n ; ++j) 
    sum = sum + j; 
} 

for (int k = 0; k < n + n + n; ++k){ 
    c[k] = c[k] + sum; 
}

這些出來是O（N^3），但我也不能肯定這是如何發生。我知道有3個循環，但它們沒有嵌套，所以n^3從哪裏來？

來源

2014-10-08 nasnasldas

第一個片段的總體時間複雜度取決於'foo（）'的時間複雜度。 – 2014-10-08 20:48:27

好吧，'foo（）'做了什麼？不能完全分析整個循環而不知道每個組件的大O是什麼。我看不出爲什麼第三個循環是O（n^3）。最好是O（3n），這實際上只是O（n）。 – 2014-10-08 20:48:34

「我知道有3個循環，但它們不是嵌套的，所以n^3來自哪裏」 - 這不是複雜性分析的工作原理。你不能簡單地「計數」循環。 – 2014-10-08 20:50:23

1）這可能與foo()的實施有關。如果foo()是O(n)，這種方法將是O(n^2)

2）內循環進入i*n，其中i此亦n，因而是在二次使n兩個環路O(n^3)總共。第三個迴路僅爲O(n)，因此在分析中可以忽略。

來源

2014-10-08 20:50:54 MrHug

爲什麼這個代碼的運行時效率O（n^2）？

回答

相關問題