遍历(行，列)二维数组的时间复杂度是多少？
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;
}
我认为每个 forloop都将取n的平方根，以便嵌套循环完全O(n)遍历所有元素，其中我将n定义为输入的总大小(在本例中为 81 个元素array)。这是对的吗？
当您将n定义为输入的总大小时，是的，您提出的算法的运行时间将是O(n)：您对输入的每个元素执行一个操作，用于n个总操作。
这个问题引起的混淆是，按照惯例，多维数组不是由它们的总大小来指代的，而是分别由它们的每个维度来指代的。因此，与其array将其视为大小为n(81)，不如将其视为大小为p x q(9 x 9) 的数组。那会给你一个运行时间O(pq).或者，如果我们将其限制为两个维度的方阵r，O(r^2).
所有这些都是正确的，这就是为什么在谈论时间复杂度时预先给出变量的明确定义很重要的原因。否则，当你用n来表示总大小时，大多数人会认为n是一个单一的维度，你会招致很多混乱。
时间复杂度将O (n*m)其中n数组的数量，这是第一维，m每个内部数组的最大大小，即第二维。
对于任何形式的算法
for (1..n) {
for (1..m) {
doSomething();
}
}
平均、最佳和最坏情况时间复杂度为O(n x m)。在您的情况下，如果 n=m，它变为O(n^2)
时间复杂度为 O(N)，这意味着它的时间复杂度是线性的。 让我们看一下时间复杂度的概念。当我们在 Big O 表示法中定义任何时间复杂度时，我们的意思是N与运行时的图形在最坏的执行情况下必须是什么样子。
对于给定的嵌套循环，数据的大小为 9*9 = 81.No 无论您在内部执行什么操作 for 循环。循环执行次数不会超过 9*9 = 81 次。如果数组的大小为 [10][10]，循环将执行不超过 100 次。
如果您使用输入或数据的数量绘制代码的执行时间图，它将是线性的。
时间复杂度由代码在数据结构中查找元素以推断结果的次数得出。无论是一维、二维还是 n-D 数组都没有关系。如果访问一个元素不超过一次，以便 n-D 数组推导出解，则复杂度为线性 O(N)，其中 N = N1 * N2 * ... *Nn
让我们以两个不同的酒店各有 N 个房间的真实世界为例来理解这一点。您需要在酒店搜索您的朋友。 在第一种情况下，假设第一家酒店在单层(一楼)有 100 间客房，在最坏的情况下，您需要访问 100 间客房才能找到您的朋友，因此这里的复杂性是线性的，即 0(N) 或 O(100)。 在第二种情况下，酒店有4层，每层有25间客房。在最坏的情况下，您必须访问25 * 4 = 100个房间(忽略楼层之间的访问时间/过程)，因此复杂性再次是线性的。
一个 2-D 数组arr[i][j]也可以由单个循环遍历，循环将运行 (i × j) 次。
考虑n = (i×j)，则遍历二维数组的时间复杂度为 O(n)。
感谢 coder2design.com