这个程序的效率如何？

Question

一个简单的程序遍历一个二维整数数组并输出每个元素，其效率（使用大O表示法）是多少？

以以下代码为例：

public static void main(String args[])
{
   int[] array = {{1,2,3,4},
                  {5,6,7,8},
                  {9,10,11,12},
                  {13,14,15,16}};

    for(int i = 0; i < array.length; i++)
    {
       for(int j = 0; j < array[i].length; j++)
       {
          System.out.println(array[i][j]);
       }
    }
}

- nope

---

请看这里：http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ - Robert Harvey

@tomejuan 这不可能是线性的！你在另一个循环中嵌套了一个循环。 - George Kastrinis

在某种程度上，这是一个关于我们计算什么的问题；如果我们正在计算向量的数量，那么是的。 - Charlie Martin

@george 它确实在线性时间内运行，程序的性能与数据集中元素的数量成正比。 - nope

@George Kastrinis 就算你有几个嵌套的循环，也并不意味着结果不能是线性的，甚至可以是次线性的。我见过这种说法很多次，以至于认为强调这样的简化方法真的行不通很重要。如果我们将N定义为整个数组中元素的数量，那么问题就变成了线性解决方案。 - Voo

Answer 1

O (n*m) 表示算法的时间复杂度，其中 n 是数组的数量（第一维），m 是每个内部数组的最大大小（第二维）。

- George Kastrinis

Answer 2

我甚至会指出 m 的大小与 n 的大小相当，并将其表示为 O(n²)。

- Charlie Martin

---

我选择这个，因为大O符号应该描述的是最坏情况下的性能。在这里可以看到一个O(N^2)的例子：http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ - Robert Harvey

@Charlie：如果你认为这很重要，在元站点上提出来。然而，很可能已经在那里讨论过了。 - Robert Harvey

@Charlie：“m不是n的函数”与“我们知道m / n是某个明确定义的常数”相矛盾！ - Oliver Charlesworth

@Charlie 我不明白你如何能够指定m/n是每个可能输入的一个明确定义的常数？假设m和n都依赖于某个k，其中n = k且m = 10^k。因此，如果我们在O(m*n)中用k替换m和n，我们得到O(10^k)，这是指数级的。如果我们事先将其简化为O(n^2)，我们得到O(k^2)，这只是多项式级别的。显然，O(10^k) != O(k^2)。 - Voo

很遗憾：O(n^2)是基于观察这个特定数据集的外推。 - Oliver Charlesworth

Answer 3

考虑到您的算法只访问了数组中的每个元素一次，因此时间复杂度为O(n)，其中n是二维数组的大小。

- matt b

---

不行，因为列表很重要；它是*O(nm)甚至O(n^s)*。 - Charlie Martin

+1：我不知道为什么这个回答被踩了，它是一个有效的答案。如果总共有n个元素，我们只访问每个元素一次；因此时间复杂度为O(n)。 - Oliver Charlesworth

这取决于您对“n”的理解。说“n”是元素的总数并不是一个不合理的观点。 - Random832

@Charie Martin，这正是我为什么说“其中 n 为……”的原因。我们可以说它是 O(rc) 或 O(p)，其中 p = r * c；这是同一件事——该算法与二维数组中的总元素数量成线性关系。这另一种方式是指行数乘以列数。这些都是相同的答案。 - matt b

Answer 4

由于您需要遍历矩阵中的每个元素一次，因此时间复杂度为O(nm)，其中n是行数，m是列数。

- azyoot

Answer 5

这个算法的时间复杂度为O(n)，因为如果你将相同数量的元素放入一维数组中并在单个循环中迭代，它将花费相同的时间。

- Roman Seleznov

Answer 6

这是O(n^2)，因为内部循环依赖于外部循环。 O(n*m) 很少用于描述循环的运行时间 - 这通常用于图形。例如：O(V+E) 表示顶点和边。

- patrick

---

那么你会说一个包含两个长度都为10E100的数组的2D数组受到2D数组长度即2的限制吗？我非常怀疑。没有正式的定义限制m <~ n，因此你不能假设n ~ m。 - Voo