遍历二维数组的时间复杂度是多少

Question

遍历（行，列）二维数组的时间复杂度是多少？

 bool check(int array [9][9])
{
    int num=0;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (array [i][j] == 0) {
                num++;
            }
        }
    }
    return num;
}

I think each for loop will take square root of n so that nested loops totally take O(n) as traversing all elements, where I am defining n 作为输入的总大小（在本例中为 array 中的 81 个元素）。那是对的吗？

原文由 Ahmed Mano 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

当您将 n 定义为输入的总大小时，是的，您提出的算法的运行时间将是 O(n) ：您正在对输入的每个元素执行一个操作，对于 n 总操作。

这个问题引起的混淆是，按照惯例，多维数组不是由它们的总大小来引用，而是由它们的每个维度分别引用。因此，与其将 array 视为大小为 n (81)，不如将其视为大小为 p x q (9 x 9) 的数组。这会给你一个运行时间 O(pq) 。或者，如果我们将其限制为具有两个维度的方数组 r ， O(r^2) 。

一切都是正确的，这就是为什么在谈论时间复杂度时预先明确定义变量很重要的原因。否则，当您使用 n 来表示 总 大小时，大多数人会认为 n 将是一个单一维度，您会引起很多混乱。

原文由 Barry 发布，翻译遵循 CC BY-SA 3.0 许可协议