二维数组搜索的时间复杂度

Question

在我看来，以下代码的最佳情况时间复杂度为O(1)，即要查找的数字作为第一个元素，但最坏情况时间复杂度为O(n**2)因为每个数组中可以有 n 个元素，二维数组中可以有 n 个数组（嵌套循环搜索）

如果你agree/disagree请告诉我。

注意：下面的代码是一个 NxN 数组的示例。我的问题一般是针对 NxN 数组，而不是针对以下代码。

#include <iostream>

int M[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int x = 20;

bool searchM(){
  for(int i=0;i<3;i++)
  {
    for(int j=0;j<3;j++)
    {
      if(M[i][j]==x)
      {
        return true;
      }
    }
  }
  return false;
} 

int main() {
  std::cout << searchM();
}

Answer 1

如果您的函数可以搜索 arbitrarily-sized（而不是 fixed-size）NxN 矩阵 M，那么您所做的就是顺序搜索。例如：

int M[3][3] = { { 1,2,3 },{ 4,5,6 },{ 7,8,9 } };

bool searchM(int n, int x) {
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<n; j++)
        {
            if (M[i][j] == x)
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    std::cout << searchM(3, 20) << std::endl;
}

因为输入大小是N，所以说这个算法的worst-case复杂度是O(N²).[=12=是正确的]

二维数组搜索的时间复杂度

Time complexity of Search in 2D array

c++

arrays

time-complexity