三個循環的複雜性

Question

任何人都可以告訴我下面的代碼的複雜性，並解釋計算？

int count=0; 
for(int i=0; i<n;i++) 
    for(int j=i; j<n;j++) 
     for(int k=j;k>i;k--) 
      count++; 

感謝

Answer 1

這僅僅是一個 「簡單」 的數學：

對於第一循環，其相當簡單，它會做n迭代。

二回路是不是要複雜得多：

• i=0：你將有n迭代。
• i=1：n-1迭代
• i=2：n-2迭代
• ...
• i=n-1：總的1迭代

是n(n+1)/2。

• i=n-1：你有0迭代

  第三循環中，我們當j>i只是感興趣。

• i=n-2：1迭代，那就是當j=n-1
• i=n-3：2迭代時j=n-1和1迭代時j=n-2
• i=n-4：3迭代時j=n-1，2迭代時j=n-2，1迭代時j=n-3
• ...
• i=0：n-1迭代時j=n-1，n-2迭代時j=2，...，1迭代時j=1

運行的這段時間是：

O((n-1)n/2 + (n-2)(n-1)/2+...+(n-n+2)(n-n+1)/2+(n-n+1)(n-n)/2)=O((n-1)*(n^2)/2)=O(n^3)