i**********e
发帖数: 1145 | 1 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
经给定整数N （N是矩阵维数）, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time的solution.
这题O(N)的解相信大家都知道了，就是从左下角或者右上角开始搜索（很多人已经讨论过了），可以参考原帖：
http://www.mitbbs.com/article_t/JobHunting/31562567.html
我尝试了另一个解法，思路是利用binary search + divide and conquer。
给个例子：
假设我们所要找的是10。先看中间那列（请参考以下图片，灰色的那列），然后利用binary search的变种找到10是9与14之间。那么，我们可以将矩阵给分成两个（请参考图片，黄色与橙色部分），然后分别在那两个小矩阵以再进行同样的搜索。
我可以证明一个case，就是假设每次矩阵被分成两个同样大小的矩阵，那么复杂度就是:
T(n) = 2T(n/2) + c lg n
= O(N) <== 这里我省略了一些证明步骤。
注：N是矩阵的维数。
可是这只是其中的一个case，而且不能证明这是worst case。
问题就是:
以上解法的worst case complexity应该是什么复杂度呢？怎样证明？
虚心请教各位大牛，我会以5个包子答谢！ （不好意思，我没有太多的包子）
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | x***y
发帖数: 633 | 2 At worst, you need to find the divide point with time O(logL), where L is
the length of search row or column.
For this Y table, the worset search is that target is not in the table and
each divide take the most time.
So, to divide until only one element is left, we need (assume the matrix is
M*N)
Log(M-1)+Log(M-2)+...log(2) + log(N-1)+log(N-2)+....log(2)
=O(log(M!)+log(N!)) then using stirling's formula
=O(MlogM+NlogN) in the worse case. | i**********e
发帖数: 1145 | 3 Thanks for your answer.
However, you have made an assumption that each divide is only eliminating
one row/column, which is not true.
Since we always choose the center column, each divide will eliminate half of
the columns (If the partition point is at the top most row/bottom most row)
. Therefore, we only need to perform at most log N divisions, but in your
case, it seems to be doing M+N divisions. How can that be possible?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
is
【在 x***y 的大作中提到】
: At worst, you need to find the divide point with time O(logL), where L is
: the length of search row or column.
: For this Y table, the worset search is that target is not in the table and
: each divide take the most time.
: So, to divide until only one element is left, we need (assume the matrix is
: M*N)
: Log(M-1)+Log(M-2)+...log(2) + log(N-1)+log(N-2)+....log(2)
: =O(log(M!)+log(N!)) then using stirling's formula
: =O(MlogM+NlogN) in the worse case.
| x***y
发帖数: 633 | 4 Hi, I'm sorry I did not check out your approach carefully and I made a
little mistake in the above analysis. It's right there are at most logM+logN
division at most, but actually in each divide, it only decreases the # of
elements; but the totaly number of rows and cols are still the name.
Consider the worse case, that each division splits the matrix into one
subMatrix with one row and subMatrix with n-1 rows, where n is # of rows of
current Matrix. If this type of split is true for evry step, then total time
used for the bigger subMatrix will be log(N)+log(N-1)+...log(2)=log(N!),
which is of course a lower bound. And the time for my first post is less
effiecient than your approach, which should be an upper bound for the worse
case, which is also log(N!). So, we can assume that the log(N!) is tight.
of
row)
【在 i**********e 的大作中提到】
: Thanks for your answer.
: However, you have made an assumption that each divide is only eliminating
: one row/column, which is not true.
: Since we always choose the center column, each divide will eliminate half of
: the columns (If the partition point is at the top most row/bottom most row)
: . Therefore, we only need to perform at most log N divisions, but in your
: case, it seems to be doing M+N divisions. How can that be possible?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
| i**********e
发帖数: 1145 | 5 Thanks again for your post.
Sorry I didn't make it clear in my question. If I am understand correctly,
you are trying to eliminate one row/column each time, therefore getting a lg
(N!) or N lg N solution.
I am asking for the worst case of the approach I mentioned in my first post.
This approach partitions the matrix to two sub-matrices each time, but the
problem is the two sub-matrices could be of different sizes.
There might be a case where each time it partitions the matrix to one sub-matrix
only. (Try to search for -1 in the sample matrix).
In this case, the complexity is:
T(N) = lg N + lg N + ... + lg N
Since the matrix could only be subdivided at most a total of lg N times,
T(N) = (lg N) * (lg N)
= (lg N)^2
Since the above complexity is lower than O(N), this is not the worst case
scenario.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
logN
of
time
worse
【在 x***y 的大作中提到】
: Hi, I'm sorry I did not check out your approach carefully and I made a
: little mistake in the above analysis. It's right there are at most logM+logN
: division at most, but actually in each divide, it only decreases the # of
: elements; but the totaly number of rows and cols are still the name.
: Consider the worse case, that each division splits the matrix into one
: subMatrix with one row and subMatrix with n-1 rows, where n is # of rows of
: current Matrix. If this type of split is true for evry step, then total time
: used for the bigger subMatrix will be log(N)+log(N-1)+...log(2)=log(N!),
: which is of course a lower bound. And the time for my first post is less
: effiecient than your approach, which should be an upper bound for the worse
| x****r
发帖数: 17 | 6 the worst case is not the case when the element is not in the matrix, in
that case, I only need log(n) to finish, along the diagonal, because of Y
table's property left upper = min, right lower = max.
it seems to me, the worst case happens when the element falls as in the
middle as possible along the diagonal ... then we have the most left
elements.... just a guess
thanks for the interesting problem | n******h
发帖数: 50 | 7 无论何种情况，每一步至少能去掉一半的元素(比如search一个中间column区域外的值)。所以worst case应该是O(N) | y*********e
发帖数: 518 | 8 根据题意，该矩阵满足如下条件：
每一行按升序排列, 每一列也按升序排列。
00 02 03 04 05 06
01 04 07 11 15 16
02 05 08 12 19 20
03 06 09 16 22 23
10 13 14 17 24 25
18 21 23 26 30 31
设N是矩阵的长度。比如如上的矩阵N=6
用divide-and-conquer的思路，找8。
第一步：
binary search第六列，找到首个小于8的行。是为第一行。
binary search第一列，找到首个大于8的行。是为第五行。
把第一行，第五行和第六行丢弃掉。
00 02 03 04 05 06 | i**********e
发帖数: 1145 | 9 谢谢你的回复，你的解法我没想过，的确也是另一种对的解法。
但是我的解法和你有点不一样。
就用你给的例子，我们要寻找的target=12。
00 02 03 04 05 06
01 04 07 11 15 16
02 05 08 12 19 20
03 06 09 16 22 23
10 13 14 17 24 25
18 21 23 26 30 31
首先，无论什么情况都好，我们都会选定中间那列来进行binary search。
中间那列就是03,07,08,09,14,23。
binary search告诉我们12在 09 和 14之间。
那么我们就可以把这个矩阵分成两个小矩阵。
XX XX | 03 | 04 05 06
XX XX | 07 | 11 15 16
XX XX | 08 | 12 19 20
XX XX | 09 | 16 22 23 | E********a
发帖数: 124 | 10
coding, 要求
linear time的solution.
论过了），
可以参考原帖：
binary
search的变种找到10是9与14之间。那么，我们可以将矩阵给分成两个（请参考图片，
黄色与橙色
部分），然后分别在那两个小矩阵以再进行同样的搜索。
是:
感觉上差不多是O(N)，worst case证明不容易，因为你每次做binary search的结果是
什么
position还真不好说，但是因为你可以换方向，比如这次选行，下次子问题里面可以根
据情况而选
中间列做binary search，所以我感觉应该是worst case也能达到O（N）的。
如果永远选择在长的方向做binary search，递归式严格的写，就是
T(N,M) = T(i, N/2) + T(N/2， N-i) + Log(M)
where M >= N, i<= N/2
还真不会证明这个式子的worst case
【在 i**********e 的大作中提到】
: 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
: 经给定整数N （N是矩阵维数）, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time的solution.
: 这题O(N)的解相信大家都知道了，就是从左下角或者右上角开始搜索（很多人已经讨论过了），可以参考原帖：
: http://www.mitbbs.com/article_t/JobHunting/31562567.html
: 我尝试了另一个解法，思路是利用binary search + divide and conquer。
: 给个例子：
: 假设我们所要找的是10。先看中间那列（请参考以下图片，灰色的那列），然后利用binary search的变种找到10是9与14之间。那么，我们可以将矩阵给分成两个（请参考图片，黄色与橙色部分），然后分别在那两个小矩阵以再进行同样的搜索。
: 我可以证明一个case，就是假设每次矩阵被分成两个同样大小的矩阵，那么复杂度就是:
: T(n) = 2T(n/2) + c lg n
: = O(N) <== 这里我省略了一些证明步骤。
| i*****o
发帖数: 105 | 11 numbers are ordered in radix, any cut not along center line is
suspicious. | i**********e
发帖数: 1145 | 12 谢谢你们的尝试，我又尝试了一个方案，但还是不能证明worst case的upper bound是O
(N).
思路是这样的：
假设矩阵的大小是 NxM，那么总共有 NxM 个元素。每一次划分可以保证去除正好 NM/2
个元素。第二层的划分又可以保证去除 NM/4 个元素。那么最坏的情况我们可以保证
划分的层数绝对不会超过 lg (NM)。这也表示 recursion 的深度不会超过 lg (NM)。
第一层我们总共用了 lg N 的时间来去除 NM/2 个元素，剩下 NM/2 个元素来搜索。
第二层我们总共用了 lg(i1) + lg(N-i1) 的时间来去除 NM/4 个元素，剩下 NM/4 个
元素。（i1 是第二层选择的划分点）
Complexity:
1st level = lg (N), NM/2 items left
2nd level = lg(i1) + lg(N-i1), NM/4 items left
3rd level = lg(i2) + lg(i1-i2) + lg(i3) + lg(N-i1-i3), NM/8 items left
...
那么复杂度就是把所有以上所有层次所耗的时间全加起来。
T(N,M) =
lg (N) +
lg (i1) + lg (N-i1) +
lg (i2) + lg (i1-i2) + lg (i3) + lg (N-i1-i3) +
...
=
lg (N) + lg (i1 * (N-i1)) + lg (i2 * (i1-i2) * i3 * (N-i1-i3)) + ...
你会发现不管哪一层都好，
i1 + N-i1 = N
i2 + i1-i2 + i3 + N-i1-i3 = N
也就意味着，第 k 层加起来正是 k 个正数相乘 再 lg:
lg (a1 * a2 * ... * ak)
并且以上的 a1,a2,...,ak 满足以下的条件：
a1 + a2 + ... + ak = N
根据维基百科的这个数学公式，
http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means
(a1 + a2 + ... + ak / k) >= (a1 * a2 * ... * ak)^(1/k)
N/k >= (a1 * a2 * ... * ak)^(1/k)
k lg (N/k) >= lg (a1 * a2 * ... * ak)
利用以上的代进去，经过数学的简化，我只能证明 upper bound 是 O(NM lg N).这
upper bound 也太不够 tight 了吧...
Anyway，我决定 move on 了... 哎
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
