B*********h
发帖数: 800 | 1 ☆─────────────────────────────────────☆
jiahe (JiaHe) 于 (Tue May 15 11:43:09 2007) 提到:
以前的讨论不知道有没有O(log(n))的定论。
下面是我的解法，请指正。
robertt的解答大家可以找到，O(m+n)
不过这里是 n*n 的 square matrix
1. $A_{i,i}
2. if $A_{i,i}
3. if $x > A_{i+1,i+1}$, $x\in A\\A_{[i+1,n],[i+1,n]}$
4. if $A_{i,i}
5. searching for $i$ is $O(log(n))$, search in $[i,n]$ is also $O(log(n))$.
3 log(n) in total.
☆──────────────────────────────── | c*****e
发帖数: 38 | 2 oh, for this, actually linear is the lower bound.
the proof is a reduction to search an element in an unordered array.
observe that one diagonal is unordered.
if you could do this in less than linear, you would be able to search an
element in unordered array in linear. | c*****e
发帖数: 38 | 3 oh, for this, actually linear is the lower bound.
the proof is a reduction to search an element in an unordered array.
observe that one diagonal is unordered.
if you could do this in less than linear, you would be able to search an
element in unordered array in linear. | k****z
发帖数: 550 | 4 LZ的解法不对，错在第2，3步。
每次和主对角线上的元素比较，结果并不能把x限定在一个sub-block里面。反之，每次
只是把x *排除* 出一个sub-block，但还剩下三个sub-block。可以想象，随着sub-
block的尺寸越来越小，sub-block的数量确实越来越多了。
LZ的算法我曾经在一次面试中想到，但是我又立刻证明了这个应该是O(NlogN)的算法。
（不是严格的证明）
最快还是O(N)的算法。 |
|
