算法複雜N *（M + N）^ 2

Question

我寫一個代碼如下：

for(i = 0 ; i < n; i++){ 
    for(j = 0; j < m + i; j++){ 
     for(k = 0; k < m + i; k++){ 
      dosomething(); 
     } 
    } 
}  

所以平均時間複雜度是O（N *（M + N/2）×（M + N/2））？那麼最糟糕的情況是什麼？我很困惑。

Answer 1

算法在最壞情況，最佳情況和平均情況下的複雜性都是相同的。

對於每個大小（n，m）的輸入，它總是執行相同數量的指令。

• 最糟糕的情況是您將爲某些輸入執行的最大步驟數n,m。這是O(n*(n+m)^2)，並且可以很容易地證明，通過顯示中間和內部循環比從n+m/2到n+m需要更多的時間，並且因爲它在O(n*(n+m)^2)中，那麼也是算法。
• 同樣 - 對於最好的情況，對於給定的n,m，必須採取相同的步數。
• 平均情況下是將大小n,m的輸入來完成操作的預期數量 - 但確切的輸入此處無關緊要，只有n和m大小 - 所以這將保持不變

Answer 2

有條不紊，使用西格瑪符號會給你以下：