如何計算這個循環的複雜度？

這個循環的複雜性是什麼？我無法把頭圍住它。如何計算這個循環的複雜度？

for (i = 0; i < n; ++i) { 
    for (j = i; j < n; ++j) { 
     for (k = 0; k < j; ++k) { 
      // Do something 
     } 
    }

}

2012-12-21 kai

這是一個無限循環，因爲第二個循環增值'i'，而不是'j'。 –

使用trace語句替換'//做某事'並且增加'n'。注意已經打印了多少個跟蹤語句。嘗試使用'1'，'2'和'3'後，您應該能夠看到非常清晰的圖案。 –

@DanAbramov我喜歡通過觀察證明:-) –

O(n^3)，我相信。請參閱Square pyramidal number。

i循環有n迭代。

j loop：（1 + 2 + ... + n），從n迭代開始，並以1結束。

k循環：（1 2 + 2 2 + ... n 2），j循環的每次迭代中的j次。

最後：

enter image description here

2012-12-21 23:02:35

回答