三重循環的複雜性

for(I = 0; I < n; I++) 
for(j = I; j < n; j++) 
    for(k = I; k < n; k++) 
    statement;

外循環運行n次。第二循環運行（n-1）次= n（n-1）/ 2次。第三循環運行（n-1）次= n（n-1）/ 2次。所以語句將運行（n（n-1）/ 2）^ 2次。這是正確的嗎？三重循環的複雜性

來源

2013-12-20 Mustehssun Iqbal

該片段不正確：「（n-1）times = n（n-1）/ 2 times」。試着用一種數學上正確的方式來表達它;這可能有幫助。 – anatolyg

「將運行（n（n-1）/ 2）^ 2次，這是正確的嗎？」它看起來不正確。 n（（n-1）/ 2）^ 2更接近。由於三重循環是O（n^3） – OmnipotentEntity

你可以指望這樣來檢查它是否是正確與否

int Cnt = 1; // initialization 
for(I = 0; I < n; I++) 
for(j = I; j < n; j++) 
    for(k = I; k < n; k++, Cnt++) 
    printf ("This is the %dth time\n", Cnt);

來源

2013-12-20 19:29:09

這是O（n^3） - 因爲

O(n^3+AnyConst*n^2+AnyOtherConst*n+ThirdConst)=O(n^3)

O符號估計漸近正進入因此，只有增長最快的組件纔是關鍵。

來源

2013-12-20 19:35:27

三重循環的複雜性

回答

相關問題