Anonymous : 求数组中元素为另外两个元素和的最大元素

懂了，A[1]+A[1]  A[1]+A[2]......A[1]+A[N]
         A[2]+A[1]  A[2]+A[2] .......A[2]+A[N]
          ...
         A[N]+A[1]  A[N]+A[2] .......A[N]+A[N]
天然的杨氏矩阵
这个思想应该是利用已知的有序，构造一个数据结构，直接查找

这个题目用杨氏矩阵怎么达到nlgn，杨氏矩阵怎么二分，求解释啊

这个题目用杨氏矩阵怎么达到nlgn，杨氏矩阵怎么二分，求解释啊
clseer 发表于 2011-10-6 16:59

    在杨氏矩阵中查找一个元素的时间复杂度可以化为log(n)的吧, 标准的查找是定位到行或列的时候从头开始一个个读, 这里如果用二分可以把复杂度降到log(n) (个人观点), 那么n个就是nlog(n). 当然,我可能会弄错, 感觉应该可以这样做,但是编程就太麻烦了.

回复 13# wwwyhx
其实可以用二分查找的，对于杨氏矩阵，相当于先定位行首元素中不大于key的最大一行，如果等于key则返回，否则从该行开始，查找不大于key的最大一列，等于key则返回，否则就继续在右上边的那个小矩阵上递归查找。当然有些递归出口没有列出来，基本思想就是这样了。

在杨氏矩阵中查找一个元素的时间复杂度可以化为log(n)的吧, 标准的查找是定位到行或列的时候从头开始一个个读, 这里如果用二分可以把复杂度降到log(n) (个人观点), 那么n个就是nlog(n). 当然,我可能会弄错, 感觉应该可以这样做,但是编程就太麻烦了.
wwwyhx 发表于 2011-10-7 01:17

在2D sorted matrix搜索最快是O(lgn ^2)。可以见这个帖子，http://www.leetcode.com/2010/10/ ... matrix-part-ii.html

这个题要求nlgn暂时没想到什么解法。

O(lgn ^2) 比O(nlogn)好, 不过就复杂了点

杨氏矩阵的话复杂度也是O(nlgn)+O(n(n+m))=O(n^2)

nooneknow 发表于 2011-10-27 11:35
在2D sorted matrix搜索最快是O(lgn ^2)。可以见这个帖子，http://www.leetcode.com/2010/10/searching ...

请15楼看清楚该帖子，该帖子写的是在某种最好情况下的复杂度才是O(logn^2)，这远远不是最坏情况；该帖子还说让读者证明最坏情况下仍是O(n)。可能是我孤陋寡闻，但据我所知，杨氏矩阵的查询复杂度还没有低于O(n+m)的简单方法。所以可以推测楼主这题没有O(nlogn)的解法？