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

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) 操作是否执行并不重要，这是正确的吗？还是有 best/worst/average 例？

感谢任何见解！

谢谢

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) 的时间，这里没有 best/average/worst 的情况。