遍历一个二维数组的时间复杂度是什么？

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;
}

我认为每个loop会对n的平方根进行操作，因此嵌套循环完全需要遍历所有元素，共需O(n)的时间，其中我将n定义为输入的总大小（在这种情况下为array中的81个元素）。这样理解正确吗？

- Ahmed Mano

---

n：输入大小为81，数组元素为[9][9]。 - Ahmed Mano

如果n == NN，其中N是每个数组的大小以及数组数量，则O(N**2) == O(n); 但是，依我之见，参数n的定义（n == NN）相当奇怪。 - Dmitry Bychenko

“复杂度”只是向您展示了您的工作增长速度与输入大小增长速度相比的快慢。这意味着它看起来取决于您将什么作为输入大小 - 比如数组中的元素数量或行/列计数。就像用米或英尺测量一件事会得出“不同”的结果一样。 - Matt

@Ahmed 不要将你的问题改成不同的问题。如果你有一个新问题，请提出一个新问题。 - Barry

@AhmedIsmail 首先要缩进所有行并计算大括号。就我所见，你的代码是错误的。 - Matt

Answer 1

如果您将n定义为输入的总大小，那么您提出的算法的运行时间确实是O(n)：您对每个输入元素执行一次单个操作，共进行n次操作。

这个问题的困惑在于，按照惯例，多维数组不是按其总大小而是按其各个维度分别引用。因此，与其将array视为大小为n（81），它应被视为大小为p x q（9 x 9）的数组。这将给您带来O(pq)的运行时间。或者，如果我们限制为两个维度均为r的方阵，则为O(r^2)。

所有这些都是正确的，这就是为什么在谈论时间复杂度时，提前清晰地定义变量非常重要。否则，当您使用n表示总大小时，大多数人会假设n是单个维度，从而会产生很多困惑。

- Barry

---

你的回答非常有建设性，但我想再次核实一下你的逻辑。我的用例是一个对象，其中每个键都有不同长度的数组。例如：{ a: [1,2,3], b: [1], c: [1,2,3,4,5] }。我想要对所有数组中的值求和（在这个例子中是 22），所以我需要遍历每个键并迭代该键的每个元素。您是否认为这是 O(n*m) 的时间复杂度，其中 n 是键的数量，而 m 表示所有数组的长度？我陷入了困境，因为这些数组的长度是不同的。 - Nitsew

Answer 2

对于任何形式的算法

for (1..n) {
    for (1..m) { 
        doSomething();
    }
}

平均、最佳和最差时间复杂度为O(n x m)。如果n=m，则变成O(n^2)。

- RaGe

---

但在我的情况下：使用两个嵌套循环来遍历所有元素 而 n：输入大小的数量将为 81，数组[9][9] 元素的数量 那么为什么不是 O(n)？ - Ahmed Mano

这个答案是错误的。n和m都不是实际输入的大小（假设为N）。在这种情况下，给定n，逻辑上可以得出m = N/n，实际复杂度为O(n * (N/n)) = O(N)。 - Etheryte

@Nit 逻辑上推断出m = N/n。正确，这意味着N=m*n。因此你的答案O(N)变成了O(m*n)。你的答案和我的一样。 - RaGe

@RaGe n * (N/n) = n * m = N。所有这些的复杂度仍然是O(N)，也就是说，与原始输入大小成线性关系。 - Etheryte

@NIT 这实际上取决于您如何量化数据大小。如果我问您数据大小有多大，而您回答n，那么计算所需的时间量将与n^2或nxm成比例。如果您回答N，那么是的，计算时间与N成比例。两者都同样有效。 - RaGe

@RaGe 大O符号总是对应于输入数据的大小，无论你如何注释它。复杂度为O(n)或O(N)，不管你选择变量名为n还是N。 - Etheryte

Answer 3

时间复杂度将会是 O (n*m)，其中 n 是数组的数量，也就是第一维度，m 是每个内部数组的最大大小，即第二维度。

- Rahul Tripathi

---

n：输入大小为81，数组元素数量为[9][9]。 - Ahmed Mano

@AhmedIsmail：在你的情况下，两个数组都被迭代了9次，即n和m都相等，因此时间复杂度将是O(n*n) = O(n^2)。 - Rahul Tripathi

Rahul Tripathi，你能在整个函数编辑后测量复杂度吗？ - Ahmed Mano

如果输入大小固定，时间复杂度将为O(1)，即操作执行的次数？ - Ahmed Mano

@AhmedIsmail 我认为你并没有完全理解大O符号的概念。 - erip

Answer 4

时间复杂度为O(N)，这意味着其时间复杂度是线性的。让我们来看一下时间复杂度的概念。当我们用大O符号表示任何时间复杂度时，我们的意思是在最坏的执行情况下，N与运行时间的图形应该是什么样子。

对于给定的嵌套循环，数据的大小为9*9=81。无论在内部循环中执行什么操作，循环都不会执行超过9*9=81次。如果数组的大小是[10][10]，则循环不会执行超过100次。

如果你用输入或数据的数量绘制代码的执行时间图表，它将是线性的。

- Ashish

Answer 5

时间复杂度是由代码在数据结构中查找元素的次数推导出来的。无论是一维、二维还是n维数组，只要你对n维数组的一个元素进行不超过一次的访问来推断解，复杂度就是线性O(N)，其中N = N1 * N2 * ... *Nn。举个例子，现在有两家不同的酒店，每家酒店都有N个房间。你需要在酒店里寻找你的朋友。在第一种情况下，假设第一家酒店在单一（底层）楼层上有100个房间，你最坏的情况下需要访问100个房间才能找到你的朋友，所以这里的复杂度是线性的，即0（N）或O（100）。在第二种情况下，酒店有4层，每层有25个房间。在最坏的情况下，你必须访问25*4=100个房间（忽略楼层之间的访问时间/过程），因此复杂度仍然是线性的。

- VIKRAM SINGH CHOUHAN

Answer 6

一个二维数组 arr[i][j] 也可以通过单个循环遍历，循环将运行 (i × j) 次。

考虑 n = (i×j)，那么遍历二维数组的时间复杂度为 O(n)。

感谢 coder2design.com。

- Jatinder Pal

---

这个答案非常具有误导性。 - erip

哪一部分是误导性的？ - Jatinder Pal

@JatinderPal 当你将n视为i乘以j时，复杂度就是O(n)。你可以简单地说复杂度是i * j。 - Ahmed Rezk

这将会是复杂度O(i * j)，如果i = j，那么它将是O(i^2)。这种说法有误导性，因为通常当有人说O(n)时，它意味着线性时间，而当i = j时，O(i * j)是二次的。 - Francisco Hanna