在O(log n)中的排序矩阵(行n列)中查找数字
noM*_*MAD 40 algorithm performance
假设我有一个矩阵(MxN),其行和列已排序.
- 每行中的所有元素按递增顺序排列
- 每列中的所有元素按递增顺序排列
- 所有元素都是整数
没有其他假设可以做
例:
[1 5 8 20]
[2 9 19 21]
[12 15 25 30]
我必须找到矩阵中是否存在给定数字(基本搜索).我有一个运行的算法O(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(log (MxN)) == O(Log(n))解决方案.有任何想法吗？？
Evg*_*uev 74
O(log(M*N))解决方案不可用于此任务.
让我们看一个简化的任务:在"排序"方形矩阵中假设次要对角线(绿色)之上的所有元素小于给定数量,次要对角线(红色)之下的所有元素都大于给定数量,并且对于次要对角线上的元素没有其他假设(黄色).
这项任务的原始假设和这些额外的假设都没有告诉我们二级对角线上的元素是如何相互关联的.这意味着我们只有一个N个整数的未排序数组.我们无法在未排序的数组中找到比O(N)更快的给定数字.因此对于具有方阵的原始(更复杂)问题,我们无法获得比O(N)更好的解决方案.
对于矩形矩阵,拉伸方形图片并相应地设置其他假设.这里我们有min(N,M)个排序的子阵列,每个子阵列的大小为max(N,M)/ min(N,M).这里搜索的最佳方法是使用线性搜索来查找可能包含给定值的一个或多个子数组,然后在这些子数组中使用二进制搜索.在最坏的情况下,有必要在每个子阵列中进行二进制搜索.复数是O(min(N,M)*(1 + log(max(N,M)/ min(N,M)))).因此,对于矩形矩阵的原始(更复杂)问题,我们无法得到比O更好的解(min(N,M)*(1 + log(max(N,M)) - log(min(N,M))) ).
- 惊讶没有人在这里发布它但是[这个](http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster)证实了你对复杂性的界限,并概述了一个在那段时间内执行的算法. (11认同)
- 另外,他获得了[能力点](http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster) (2认同)
- 由于我们无法在零时间内解决"M == N"情况,因此复杂度应为"O(min(N,M)*(1 + log(max(N,M)) - log(min(N) ,M))))`. (2认同)
不可能比O(n)做得更好.有些人(本页至少有三个人)认为他们可以做得更好,但那是因为他们的算法错误,或者因为他们不知道如何计算算法的复杂性所以他们试图猜测它.这篇博文非常好,并会向您解释这些家伙的错误.
O(n)最优的证明草案:考虑以下矩阵:
1 2 3 4 5 6 … (n-2) (n-1) (n+1)
2 3 4 5 6 7 … (n-1) (n+1) (n+2)
3 4 5 6 7 8 … (n+1) (n+2) (n+3)
… … … … … … … … … …
(n-2) (n-1) … … … … … … … (2n-1)
(n-1) (n+1) … … … … … … … 2n
(n+1) (n+2) … … … … … (2n-1) 2n (2n+1)
如果你n在这个矩阵中寻找,你必须至少检查一行,如果n在行中,因为n可能在任何行.(证据不完整,但这是想法)