time-complexity - 不确定我的复杂性分析是否正确

Question

试图找到这个代码块的 Big-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++;
        }
    }
}

我做了一个估计并简化： O(m)O(n)O(1) => O(mn)

看起来所有情况都是 O(mn)，因为 O(1) 操作是否执行并不重要，这是正确的吗？还是有最好/最差/平均的情况？

欣赏任何见解！

谢谢

Answer 1

在您提供的这段代码中，嵌套循环没有上限，因此您不使用 big-O 复杂度函数，而是使用 big-Theta 来描述时间复杂度，在您的情况下，是的，它是 θ( nm) 意味着您的算法将始终花费 θ(nm) 时间，并且这里没有最佳/平均/最差情况。

Answer 2

这是O(mn)因为有 2 个循环（其中一个嵌套在另一个循环中）。O(1) 在这里没有意义。if不算的。它没有中断，因此不会影响两个循环的整个遍历。这里没有最好或更坏，同样因为if不会改变流量，也不会增加 w 无论如何都会影响循环。

Answer 3

是的，这将始终是 O(mn)，因为如果您将测试条件视为操作，那么主体是否会被执行并不重要。

它只是常数 O(mn*1/2) 但因为 1/2 只是常数，你可以忽略它。