遍历2d阵列的时间复杂度是多少？

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

我认为每个for loop将取平方根, n以便嵌套循环完全取O(n)遍遍历所有元素,我将其定义n为输入的总大小(在本例中为81个元素array).那是对的吗？

Answer 1

当您定义n为输入的总大小时,是的,您建议的算法的运行时间将是O(n):您对输入的每个元素执行单个操作,以进行n总操作.

在这个问题产生混淆的地方,按照惯例,多维数组并不是指它们的总大小,而是分别用它们的每个维度来表示.因此,不是将其视为array大小n(81),而是将其视为大小p x q(9 x 9)的数组.这会给你一个运行时间O(pq).或者,如果我们将它限制为具有两个维度的正方形数组r,O(r^2).

一切都是正确的,这就是为什么在谈论时间复杂性时,预先给出变量的清晰定义是很重要的.否则,当你n用来表示大多数人认为是单一维度的总大小时n,你会引起很多混乱.

Answer 2

时间复杂性将是O (n*m)其中n阵列的数量，其是第一尺寸，m每个内部阵列即最大尺寸，第二尺寸。

Answer 3

对于任何形式的算法

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

平均、最好和最坏情况的时间复杂度为O(n x m)。在你的情况下，如果 n=m，它变成O(n^2)

Answer 4

时间复杂度是O(N)，也就是说它的时间复杂度是线性的。我们来看看时间复杂度的概念。N当我们用 Big O 表示法定义任何时间复杂度时，我们的意思是在最坏的执行情况下，运行时间与运行时间的关系图必须是什么样子。

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

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