最优矩阵搜索（2D）问题的时间复杂度分析

Question

这对我来说将是一个相当大的问题，因为它需要对问题进行深入而彻底的理解，并且还需要迄今为止为最佳解决方案采取的各种方法。

对于这个问题，我稍后会创建一个博客，因为我这边需要一点时间来写内容等等。所以，一旦准备好，我将提供我的博客链接。

尽管如此，我还是发布此内容以便我们可以开始讨论。

首先，

问题如下：

编写一个高效的算法，在 nxm 表（二维>数组）中搜索值。该表按行和列排序 - 也就是说，

表[i][j] ≤ 表[i][j + 1] 表[i][j] ≤ 表[i + 1][j]。

这里需要注意的是，每一行和每一列都是单调排序的，即每一行和列都按非递减（字典顺序）顺序排序。

对于实际问题以及对此问题的精彩讨论，请单击以下链接：

注意：这篇文章有第 1,2 和 3 部分。

搜索二维矩阵

澳大利亚格里菲斯大学沉洪于1995年12月27日发表了最优解对于串行算法，此问题的复杂度为 O(mlog(2n/m))。

<一href="http://www.google.com/url?sa=t&source=web&cd=2&ved=0CB0QFjAB&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi =10.1.1.116.3096&rep=rep1&type=p df&rct=j&q=hong%20shen%20optimal%20matrix%20search&ei=h_b9TbifMsLtrAe61rnFDw &usg=AFQjCNEYsY81lKG5Eopg9l0lXGvPSd_Rjg&sig2=vzUsFbeObWvKzNhS09KOkg&cad=rja" rel="nofollow" title="洪深广义最优矩阵搜索">洪深--广义最优矩阵搜索

此后出现了大量关于此的论坛讨论、博客以及在线和离线文章和出版物，但截至今天，据我所知，O(((log(n))2) 是这篇文章中改进的二分搜索中最好的说法。

尽管详细的算法尚未公开 提供了。

现在，我 对这个问题做了不同的解决方案，希望使最佳解决方案低于当前最佳解决方案（我认为）

但是，我不太擅长分析算法的时间复杂度。

以下只是其中之一。当我们做出决定时，我将继续为其他人提供帮助，从而在你们的帮助下做出最好的决定。

这是第一个供您分析时间复杂度的

  /*  NIAZ MOHAMMAD

    IntPol2d.cpp

    1. Find the interpolated mid along column
    2. Compare key with each elements in row-wise 
       along the found mid column
    3. IF failed
        DO 
        RECURSIVE call to IntPol2d 
        a. IF(key > a[row][mid])
            THEN SET l = mid + 1 and d = row - 1;
        b. ELSE set r = mid -1 and u = row;
*/


    bool intPol2d(int mat[][6], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol,int &count) {
      count++;
      if (l > r || u > d) return false;

      if (target < mat[u][l] || target > mat[d][r]) return false;

      int mid = l + ((target - mat[u][l])*(r-l))/(mat[d][r]-mat[u][l]);
      int row = u;

      while (row <= d && mat[row][mid] <= target) 
      {
        if (mat[row][mid] == target) 
        {
          targetRow = row;
          targetCol = mid;
          return true;
        }
        row++;
      }
      return intPol2d(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol,count) ||
             intPol2d(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol,count);

    }

如果您需要完整的可执行代码，请告诉我。

感谢您的耐心和帮助，我们在讨论板上再见：

注意：@管理员或版主，如果这不是解决此类冗长问题的正确位置，请告诉我，然后我将转到我的博客。

Answer 1

您不必将数组视为二维事物。它只是一个 mat[n]，其中 n=MxN 并进行复杂度为 O(log(n)) 的二分搜索。请注意，这是以 2 为底的对数，并且是最坏的情况。请注意，复杂度不包括 1 以外的常数，因为它们不随输入大小而变化。实际最坏的情况是测试 2*log(n) 个元素。另外，您可能会在第一次测试中达到您想要的目标。如果不预先构建哈希表或其他关联数组（其中指向您要查找的原始矩阵中的元素的指针位于新数组中的索引），您就无法获得比这更快的速度。您想要值为 46 的元素，因此您在索引表中查找元素索引 46，例如，它指向 (M,N)=(2357,656)。繁荣，建立可重用、内存昂贵的索引表后，复杂性为 O(1)。