假设我们有一个大小为 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 个象限(根据中间行的二分搜索结果,它们的大小可能不同),然后我们递归搜索其中两个象限。
最佳答案
最坏情况下的运行时间是 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 的成本。
关于algorithm - 搜索排序矩阵的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31634271/