解析矩阵的嵌套 for 循环的时间复杂度

Question

假设我有一个包含 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？

Answer 1

如果您有一个大小为行*列的矩阵，那么内部循环(假设)是 O(columns)，嵌套循环一起是 O(rows*columns)。

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