3

假设我有一个包含 X 行和 Y 列的矩阵。元素的总数是 X*Y，对吗？那么这是否使n = X * Y？

for (i=0; i<X; i++)
{
   for (j=0; j<Y; j++)
   {
      print(matrix[i][j]);
   }
}

那么这不是意味着这个嵌套的for循环是O（n）吗？还是我误解了时间复杂性的工作原理？

一般来说，我认为所有嵌套的for循环都是O（n ^ 2），但是如果它通过X * Y调用print（），这并不意味着时间复杂度是O（X * Y）和X * Y等于n？

4

4 回答 4

1

如果你有一个大小为rows*columns的矩阵，那么内部循环（假设）是O（columns），嵌套循环在一起是O（rows *columns）。

您将 N 的问题大小与 N ^ 2 的问题大小混淆了。您可以说您的矩阵大小为 N 或矩阵大小为 N^2，但除非您的矩阵是正方形，否则您应该说您有一个大小为 Rows*Columns 的矩阵。

于 2012-04-27T04:48:36.270 回答
1

n = X x Y当你说嵌套循环应该是时你是对的，但当你说嵌套循环是错误的O(n)。如果您干运行代码，就可以理解嵌套循环的含义。您会注意到，对于外循环的每次迭代，内循环都会运行n（或大小条件）次。因此，通过简单的数学，您可以推断出它的O(n^2). 但是，如果您在迭代时只有一个循环(X x Y)（例如：for(i = 0; i<(X*Y); i++)元素，那么这将O(n)导致您在任何时候都没有重新开始迭代。希望这是有道理的。

于 2012-04-27T04:49:09.190 回答
0

一般来说，我认为所有嵌套的 for 循环都是 O(n^2)，

你错了。我猜让您感到困惑的是，人们经常使用方形（X==Y）矩阵作为示例，因此复杂度为 n*n（X==n，Y==n）。

如果你想练习你的 O(*) 技能，试着弄清楚为什么矩阵乘法是 O(n^3)。如果您不知道矩阵乘法的算法，很容易在网上找到它。

于 2012-04-27T04:54:11.463 回答
0

这个答案写得很仓促，收到了一些反对意见，所以我决定澄清并重写它

算法的时间复杂度是根据算法要解决的问题的大小来表示算法的操作数。

这里涉及两种尺寸。

  1. 第一个大小是矩阵 X × Y 的元素数量，这对应于复杂性理论中称为input 的大小。令 k = X × Y 表示矩阵中元素的数量。由于双循环中的操作数为 X × Y，因此在 O(k) 中。

  2. 第二个大小是矩阵的列数和行数。设 m = max(X,Y)。双循环中的操作数为 O(m^2)。通常在线性代数中，这种大小用于表征 m × m 矩阵上的矩阵运算的复杂性。

当您谈论复杂性时，您必须准确指定如何对实例问题进行编码以及使用什么参数来指定其大小。在复杂性理论中，我们通常假设算法的输入是来自某个有限字母表的字符串，并根据给定问题实例的操作数上限来衡量算法的复杂性一个长度为 n 的字符串。也就是说，在复杂性理论中，n 通常是 input 的大小。

在算法的实际复杂性分析中，我们经常使用在特定上下文中更有意义的实例大小的其他度量。例如，如果A是图的连接矩阵，我们可以使用顶点数V作为问题实例复杂度的度量，或者如果A是作用于向量空间的线性算子的矩阵，我们可以使用维度向量空间作为这样的度量。对于正方形矩阵的约定是根据矩阵的维数来指定复杂度，即用 n 来衡量作用于 n × n 矩阵的算法的复杂度。它通常具有实际意义，并且也符合特定应用领域的惯例，即使它可能与复杂性理论的惯例相矛盾。

让我们为我们的双循环命名矩阵扫描。您可以合理地说，如果Matrix Scan实例的大小是矩阵的字符串编码的长度。假设条目的大小有界，它是矩阵中元素的数量 k。那么我们可以说矩阵扫描的复杂度在 O(k) 中。另一方面，如果我们将 m = max(X,Y) 作为表征实例复杂度的参数，这在许多应用程序中是惯用的，那么 X×Y 矩阵的复杂度矩阵扫描也将在 O(米^2)。对于方阵 X = Y = m 和 O(k) = O(m^2)。

注意：评论中有人问我们是否总能找到问题的编码来将任何多项式问题简化为线性问题。这不是真的。对于某些算法，操作数量的增长速度快于其输入的字符串编码长度。例如，没有算法可以将两个 m×m 矩阵与 θ(m^2) 次运算相乘。这里输入的大小增长为 m^2，但是Ran Raz证明操作的数量增长至少与 m^2 log m 一样快。如果 n 在 O(m^2) 中，则 m^2 log m 在 O(n log n) 中，并且最著名的算法复杂度随着 O(m^(2+c)) = O(n^(1+ c/2))，其中对于 Coppersmith-Winograd 算法的版本，c 至少为 0.372，对于常见的迭代算法，c = 1。

于 2012-04-27T04:56:44.083 回答