有人可以向我解釋在這裏做什麼

-1

我不想要答案我想知道如何去做。算法doIt的效率可以表示爲O（f（n））= n^3。精確計算以下程序段的效率，並使用big-O符號。有人可以向我解釋在這裏做什麼

for (i=1; i<=n+1; i++) 
    for (j=1; j<n, j++) 
     doIt (...)

他給了我們不是這個樣子的，他只是畫了幾個廣場等廣場這表明我們，這是一個嵌套的循環內任何事物的例子。他沒有給我們任何類型的代碼，像問題中的代碼。他剛寫

ALG（M，N，K，L）= 3N^3
M = 1N，N = 1的2n，K = 1N，L = 1N^2
N^2 * n個* 2n * n * 3n^3 = 6n^8 = O（n^8）

所以，我假設這是一個嵌套循環，最高的是n^3。或者有人可以爲示例編寫代碼，以便我可以更好地理解它？

代碼示例似乎被切斷 - 請您擴展？另外，縮進你的代碼會使它變得等寬，所以我們可以更容易地閱讀它。謝謝！ – cxw 2014-08-29 18:50:02

for (i=1; i<=n+1; i++) 
for (j=1; j<n, j++) 
    doIt (...)

正如您所提到的，最壞情況下的複雜度爲O（n^3）。

因此，在嵌套循環的情況下，主要關注點是第一個循環引導內部循環，即內部循環通常不運行no。迭代（不一定總是）比外部循環！

正如你的問題，外環運行i = 1到i = n + 1 --- n+1 times。類似地，內循環對於外循環的每次迭代運行j = 1到j< n --- n-1次迭代。此外，函數doIt（）在內部循環內部，複雜度爲O（n^3）。

接下來，根據最壞情況的複雜度，n + 1次迭代的階數爲O（n）。

類似地，根據最壞情況的複雜度，n-1次迭代的階數爲O（n）！

因此，整體的最壞情況複雜= O(n)*O(n)*O(n^3) = O(n^5) ...

如果你無法理解，請在下面發表評論！

2014-08-29 18:59:58

回答