不確定如果我的複雜性的分析是正確

Question

試圖找到這代碼組塊的大O估計：

int a[][] = new int[m][n]; 
int w = 0; 
for (int i = 0; i<m; i++) { 
    for(int j = 0; j<n; j++) { 
     if (a[i][j]%2 == 0) { 
      w++; 
     } 
    } 
} 

我由esimation和簡化：O（米）爲O（n）O（1）= > O（mn）

看起來好像所有的情況都是O（mn），因爲如果O（1）操作執行與否無關緊要，這是否正確？還是有最好/最差/平均情況？

感謝任何見解！

謝謝

Answer 1

這是O(mn)這裏，因爲2個循環（其中一個嵌套在另一個）的。 O（1）在這裏沒有意義。 if不算。它沒有中斷，所以它不會影響兩個循環的整個遍歷。在這裏沒有最好的或者更糟糕的，因爲if不會改變流量，也不會增加w會影響循環。

Answer 2

是的，這將始終是O（mn），因爲如果您將測試條件作爲操作進行計數，那麼無論是否執行主體都無關緊要。

它只會是常數O（mn * 1/2），但是因爲1/2只是常數，您可以忽略它。

Answer 3

在您提供的代碼中，嵌套循環沒有上限，因此您不使用big-O複雜度函數，而是使用big-Theta來描述時間複雜度，在您的情況下，是它是θ（nm），這意味着您的算法總是需要θ（nm）的時間，並且這裏沒有最佳/平均/最差的情況。