運行這個僞的

誰能幫我分析一下下面的僞代碼運行這個僞的

for(i = 0; i < n*n*n; i++) 
    for(j = i; j < n; j++) 
     x++

我看到它的下界歐米茄（N^3）方式的運行時間，因爲這是它會是什麼，如果裏面外部for-loop只是theta（1）。

我對內循環感到困惑，它只爲外循環的前n次迭代運行。我只是平均了內部循環的運行時間：n^3 *（（1/n^2）* n +（1/n）* 1，在這種情況下它是O（n^3）？

來源

2011-11-03 Andrew

取決於如何聰明你的編譯器是該算法可以分爲兩個部分（這可能差一個錯誤，但你的想法）

// i<n 
// O(n^2) 
for(i=0; i<n ; ++i) 
    for(j=i; j<n; ++j) 
    x++ 

// n < i < n*n*n 
// O(n^3) 
for(i=n ; i<n*n*n; ++j) 
    noop(); //do nothing

對於i > n第二部分不執行任何操作，那麼智能編譯器將只環路I至n，在這種情況下，它是O（n^2）。

但是，如果你的編譯器不靈巧，後半部分也會執行，你只需要進行O（1）比較，因此總體行爲是O（n^3）。

來源

2011-11-03 01:45:26

內環將只有i<n所以這是O(n^2)得到執行。

來源

2011-11-03 01:44:54 Dennis

如果你的編譯器足夠聰明，內循環就是O（n），所以它出現在O（n^2）上。 –

@邁克爾安德森：正確。在您的評論前修復了一秒。 – Dennis

你的算法應該是解剖類似如下：

for(i = 0; i < n*n*n; i++) { 
    for(j = i; j < n; j++) { 
     x++ 
    } 
    if (i >= n) { 
     y ++; 
    } 
}

凡x計算內外循環的次數，並y將估計外部循環的迭代次數時，內循環ISN」再被執行。

因此，可以繼續進行正式類似如下：

enter image description here

當n = 10，其結果將是：X = 55，和y = 990，這是與上面的式兼容。

來源

2014-04-12 16:56:16

運行這個僞的

回答

相關問題