2

给出了一个在所有三个维度上排序的 3d 矩阵，我们必须在其中找到一个给定的数字。

对于上述问题，我一直在想：3D 数组arr[m][n][r]就像一堆矩形，其中每个矩形（考虑arr[m][n][0]）将最大的元素作为最右边的元素（arr[m-1][n-1][0]）。我们可以在每个矩形内搜索O(m+n) ：

int row = 0;
int col = N-1;

while (row < M && col >= 0) 
{
  if (mat[row][col] == elem) 
  { 
    return true;
  }
  else if (mat[row][col] > elem) 
  { 
    col--;
  } 
  else 
  { 
    row++;
  } 
}

我在想它可以类似地扩展到第三维，因此使其成为线性复杂度解决方案（O(m+n+r)）。我对吗 ？

有没有人有任何其他想法？复杂度会是多少？

4

3 回答 3

5

您不能将线性复杂度 2D 解决方案扩展到第 3 维，从而产生 O(m+n+r) 解决方案。3D 数组，在每个方向上独立排序，包含 O(N 2 ) 组元素，它们之间没有排序。例如，完全未排序的子arr[i][j][k]数组i+j+k = (m+n+r)/2。所以你必须检查这样一个子数组的每个元素来找到给定的数字。这证明你不能发明一种复杂度比 O(N 2 ) 更好的算法（至少当 m、n 和 r 彼此没有太大差异时）。这只是这个答案的证明的延伸。

这是一个例子：

k=0: |1 x|   k=1: |z 3|
     |y 3|        |3 4|

该数组按所有 3 个维度排序。但这并不能确定元素 x、y、z 的任何排序顺序。您可以将 (1, 3) 范围内的任何值分配给这些元素。在搜索值为“2”的元素时，您必须检查所有这些“未排序”值（x 和 y 和 z）。如果增加数组的大小，您会看到“未排序”值的数量可能会二次增加。这意味着搜索算法的最坏情况时间复杂度也应该二次增加。

您可以找到最小的数组大小（让它为 'r'），并且对于每个矩阵arr[*][*][k]搜索给定的数字 O(m+n) 时间，这给出了 O((m+n)*r) 时间复杂度。

或者，如果其中一个数组大小比其他数组r >> m*n大得多arr[i][j][*]（

于 2012-07-21T15:34:32.370 回答
1

如果内存消耗不是大问题，您可以将数组复制到单个 1D 数组对中，然后按值对该数组进行排序并在其中执行二进制搜索，复杂度为 O(log(n+m+r))。但是初始排序将采用 O((n+m+r)*log(n+m+r)) ，这将定义整个算法的复杂性。

我认为由于 3D 数组在每个维度上都进行了排序，因此可以找到一些算法，将其转换为排序的 1D 数组，速度比 O((n+m+r)*log(n+m+r)) ，但我不知道这样的事情。或许蚩尤试图解释这一点。

于 2012-07-21T16:47:16.893 回答
1

从理论上讲，我可以想到一个对数的递归解决方案。

假设 n 是您在立方体 NxNxN 中寻找的数字。这个立方体按照从东到西、从北到南、从上到下的升序排列。使得在极端东北顶部的数量最小，在极端西南底部的数量最大。

选择立方体中心的数字。如果这个数字等于 n，那么我们就找到了这个数字。如果这个数字大于 n，我们可以忽略所有位于西南底部的数字，因为它们都将大于 n。这些数字是立方体的 1/8。现在我们可以轻松地将立方体的剩余部分分成 7 个立方体并重复该过程。

类似地，如果这个数字小于 n，我们可以忽略所有位于东北顶部的数字。

Point find(int[][][]matrix, int N, int n)
{
    if(N == 0)
    {
      return null;
    }

    int x = matrix[N/2][N/2][N/2];
    if( x == n)
        return new Point(N/2, N/2, N/2);
    else if (x > n)
    {
        for(Matrix m: SplitTheCubeInto8CubesAndIgnoreSouthWestBottomCube(matrix))
        {
            if((p = find(m, N/8, n)) != null)
                return p;
           else
                return p;
        }
    }
    else
    { 
        for(Matrix m: SplitTheCubeInto8CubesAndIgnoreNorthEastTopCube(matrix))
        {
            if((p = find(m, N/8, n)) != null)
                return p;
           else
                return p;
        }
    }
}

复杂度可以表示如下： T(M) = 7*T(M/8)+ 1 （M 是位于立方体中的点的总数。M = N*N*N。在每次比较中，我们是剩下 7 个 M/8 大小的立方体）O = ln (M) [ln 在 8/7 的基础上] 或 O = ln (N)

于 2014-01-14T02:42:29.927 回答