该算法最坏情况的运行时间是多少（以大哦表示法）？

Question

输入是一个 N × N 的数字矩阵。每行从左到右递增。每个单独的列从上到下递增。下面给出了 N = 3 的矩阵示例。

3   4   5
4   5   8
6   7   9

以下是在矩阵中搜索项目的基本朴素算法（伪代码）：

bool search2DMatrix( int a[][], int N)
{
       for(int i = 0; i < N; i++)
             for(int j < 0; j < N; j++)
                   if ( item == a[i][j])
                             return true; 
        return false //if not found
}

找到一个 O(N) 最坏情况算法，用于查找某个数字项是否在矩阵中。 写下算法（以伪代码）并显示算法运行时的分析。

我真的很难理解这一点，并且在网上查找并没有产生任何有用的视频或资源。有懂算法分析的人能帮我解决这个问题吗？我正在上数据结构课，教授只发布了 2 年前的视频并且忽略了问题。预先感谢您！

我已经制作了这个伪代码，但我认为这不是问题所要求的。

1. 从矩阵的右上角开始
2. 现在我需要初始化两个变量
   • 值为 0 的行是顶行
   • 值为 N-1 的列是右列
3. 当行小于或等于N-1且列大于或等于0时重复步骤4、5和6
4. 将当前位置矩阵[行][列]处的值与目标值X进行比较
   • 如果它们相等则返回 true，因为 X 存在于矩阵中
   • 如果当前位置的值大于X则按降序向左移动一列
   • 如果当前位置的值小于我按升序移动到下一行
5. 如果我已经用尽了所有可能的位置并且还没有找到X则返回false

Answer 1

使其复杂度为 O(N) 的技巧是不要从矩阵的左上角单元格开始，而是从矩阵的左下角单元格开始。在该位置，您位于 2N-1 个项目的有序序列的中间，这些项目从 (0, 0) 到 (n-1, 0)，再到 (n-1, n-1)。

现在，如果当前单元格的值大于目标值，那么您就知道当前单元格right处的所有值不再相关：我们可以向上移动一行（到第n-2行） 。如果在某个时刻该值小于我们要查找的值，我们可以丢弃我们所在的列，并移至第 1 列。因此我们将范围缩小到目标单元格。

这是代码中的样子（我希望您应该将

item

作为参数传递）：

bool search2DMatrix(int a[][], int N, int item) {
    int r = n - 1;
    int c = 0;
    while (r >= 0 && c < n) {
        if (m[r][c] == item) return true;
        if (m[r][c]  > item) r--;
        else                 c++;
    }
    return false;
}