algorithm - 搜索排序矩阵的复杂性

Question

假设我们有一个大小为 NxN 的矩阵，其中所有的行和列都按递增顺序排列，我们想知道它是否包含值 v。一种算法是对中间行执行二分查找，以找到值最接近 v 的元素:M[row,col] < v < M[row,col+1](如果我们准确找到 v，则搜索完成)。由于矩阵已排序，我们知道 v 大于子矩阵 M[0..row, 0..col](矩阵的左上象限)中的所有元素，同样它小于中的所有元素子矩阵 M[row..N-1, col+1..N-1](右下象限)。所以我们可以递归搜索右上象限 M[0..row-1, col+1..N-1] 和左下象限 M[row+1..N-1, 0..col]。

问题是这个算法的复杂度是多少？

示例:假设我们有如下所示的 5x5 矩阵，我们正在搜索数字 25:

0 10 20 30 40
1 11 21 31 41
2 12 22 32 42
3 13 23 33 43
4 14 24 34 44

在第一次迭代中，我们对中间行执行二进制搜索，找到小于 25 的最近元素是 22(在 row=2 col=2 处)。所以现在我们知道 25 大于左上角 3x3 象限中的所有项目:

0 10 20
1 11 21
2 12 22

类似地，我们知道 25 小于右下 3x2 象限中的所有元素:

32 42
33 43
34 44

因此，我们递归搜索剩余的象限 - 右上角 2x2:

30 40
31 41

和左下角的 2x3:

3 13 23
4 14 24

等等。我们基本上将矩阵分为 4 个象限(根据中间行的二分搜索结果，它们的大小可能不同)，然后我们递归搜索其中两个象限。

Answer 1

最坏情况下的运行时间是 Theta(n)。当然，这对于正确的算法来说是最好的(考虑一个反对角线，上面的元素小于 v，下面的元素大于 v)。就上限而言，n 行 m 列矩阵的界限是 O(n log(2 + m/n))，正确的递归证明了这一点

                  m-1
f(n, m) = log m + max [f(n/2, j) + f(n/2, m-1 - j)],
                  j=0

那里有两个 子问题，没有一个。这种递归可以用替换法解决。

        ?
f(n, m) ≤ c n log(2 + m/n) - log(m) - 2  [hypothesis; c to be chosen later]

                  m-1
f(n, m) = log m + max [f((n-1)/2, j) + f((n-1)/2, m-j)]
                  j=0

                    m-1
        ≤   log m + max [  c (n/2) log(2 + j/(n/2)) - log(j) - 2
                         + c (n/2) log(2 + (m-j)/(n/2))] - log(m-j) - 2]
                    j=0

        [fixing j = m/2 by the concavity of log]

        ≤ log m + c n log(2 + m/n) - 2 log(m/2) - 4

        = log m + c n log(2 + m/n) - 2 log(m) - 2

        = c n log(2 + m/n) - log(m) - 2.

将 c 设置得足够大，使得对于所有 n，m，

c n log(2 + m/n) - log(m) - 2 ≥ log(m),

其中 log(m) 是基本情况 n = 1 的成本。