w*****1
发帖数: 245 | 1 a matrix, with each row sorted, but colms are NOT. find a target value.
find a way better than nlogn?
真的不觉得能再快了!
大家讨论下吧, 不知道这题以前在这里出现过吗? |
p*****u
发帖数: 310 | 2 Dump to hash table. O(n) |
r****o
发帖数: 1950 | 3 我的想法是对每row,判断target值是不是落在其中，然后用binary search,
这样假设矩阵有m行n列，复杂度mlogn.
楼主是要找更快的方法?
【在 w*****1 的大作中提到】
: a matrix, with each row sorted, but colms are NOT. find a target value.
: find a way better than nlogn?
: 真的不觉得能再快了!
: 大家讨论下吧, 不知道这题以前在这里出现过吗?
|
a***9
发帖数: 364 | 4 感觉 worse case不可能提高.
但如果在搜之前加一个bound check,比如
if (target < matrix[i,0] || target > matrix[i,Last - 1])
对这行就不搜了,那么 best case是 O(n+logn), 这样average会提高. Who knows~
【在 w*****1 的大作中提到】
: a matrix, with each row sorted, but colms are NOT. find a target value.
: find a way better than nlogn?
: 真的不觉得能再快了!
: 大家讨论下吧, 不知道这题以前在这里出现过吗?
|
g**********1
发帖数: 1113 | 5 this n x n matrix. Not total number is n
【在 p*****u 的大作中提到】
: Dump to hash table. O(n)
|
w*****e
发帖数: 197 | 6 I think you can no better. Consider following algorithm:
Extract the n/3 and 2n/3'th elements from each row.
You have altogether 2n elements. Do a pivot operation
(refer to qsort for details), and by some clever bookkeeping,
you can determine whether your target value is in
the first, middle or the last n/3 elements in each row.
So basically speaking, you pay O(2n) time, but you trim your
size by 1/3. Solving this recursion gives a linear time
search!
I am really proud of myself for solving this |
w*****e
发帖数: 197 | 7 My algorithm is WRONG. Sorry for the confusion.
【在 w*****e 的大作中提到】
: I think you can no better. Consider following algorithm:
: Extract the n/3 and 2n/3'th elements from each row.
: You have altogether 2n elements. Do a pivot operation
: (refer to qsort for details), and by some clever bookkeeping,
: you can determine whether your target value is in
: the first, middle or the last n/3 elements in each row.
: So basically speaking, you pay O(2n) time, but you trim your
: size by 1/3. Solving this recursion gives a linear time
: search!
: I am really proud of myself for solving this
|
m****y
发帖数: 28 | 8 你这算法跟逐行binary search毫无区别，把2换成了3而已
你的复杂度是2n*log3(n)
【在 w*****e 的大作中提到】
: I think you can no better. Consider following algorithm:
: Extract the n/3 and 2n/3'th elements from each row.
: You have altogether 2n elements. Do a pivot operation
: (refer to qsort for details), and by some clever bookkeeping,
: you can determine whether your target value is in
: the first, middle or the last n/3 elements in each row.
: So basically speaking, you pay O(2n) time, but you trim your
: size by 1/3. Solving this recursion gives a linear time
: search!
: I am really proud of myself for solving this
|
m****y
发帖数: 28 | 9 如果列之间没有关系，应该不存在快于nlogn的方法了。不难证明。
【在 w*****1 的大作中提到】
: a matrix, with each row sorted, but colms are NOT. find a target value.
: find a way better than nlogn?
: 真的不觉得能再快了!
: 大家讨论下吧, 不知道这题以前在这里出现过吗?
|
l******o
发帖数: 144 | 10 正想吐槽来着，你自己发现了。
My algorithm is WRONG. Sorry for the confusion.
【在 w*****e 的大作中提到】
: My algorithm is WRONG. Sorry for the confusion.
|
|
|
x****r
发帖数: 99 | 11 不是很了解你的意思
如果你是说T(n) = T(N/3) + O(N)
但是你的trivial case(N = 1， 只剩最后一列)的时候是O(N)的complexity，
如果trivial case不是constant time的，可以这样算么。？
【在 w*****e 的大作中提到】
: I think you can no better. Consider following algorithm:
: Extract the n/3 and 2n/3'th elements from each row.
: You have altogether 2n elements. Do a pivot operation
: (refer to qsort for details), and by some clever bookkeeping,
: you can determine whether your target value is in
: the first, middle or the last n/3 elements in each row.
: So basically speaking, you pay O(2n) time, but you trim your
: size by 1/3. Solving this recursion gives a linear time
: search!
: I am really proud of myself for solving this
|
x****r
发帖数: 99 | 12 请问如果用master theorem怎么证明这个算法是2n*log3(N)
虽然intuitively很容易解释。。
谢谢：）
【在 m****y 的大作中提到】
: 你这算法跟逐行binary search毫无区别，把2换成了3而已
: 你的复杂度是2n*log3(n)
|
l******o
发帖数: 144 | 13 他自己都说自己错了。
其实就是T(n,m)=T(n,m/3)+O(n)
所以T(n,n)=O(nlgn)
不是很了解你的意思
如果你是说T(n) = T(N/3) + O(N)
但是你的trivial case(N = 1， 只剩最后一列)的时候是O(N)的complexity，
如果trivial case不是constant time的，可以这样算么。？
【在 x****r 的大作中提到】
: 不是很了解你的意思
: 如果你是说T(n) = T(N/3) + O(N)
: 但是你的trivial case(N = 1， 只剩最后一列)的时候是O(N)的complexity，
: 如果trivial case不是constant time的，可以这样算么。？
|
x****r
发帖数: 99 | 14 我好像是早上开的帖子，晚上回来刚看到就回了，不知道已经讨论了那么多了：P
多谢解释 ：）
【在 l******o 的大作中提到】
: 他自己都说自己错了。
: 其实就是T(n,m)=T(n,m/3)+O(n)
: 所以T(n,n)=O(nlgn)
:
: 不是很了解你的意思
: 如果你是说T(n) = T(N/3) + O(N)
: 但是你的trivial case(N = 1， 只剩最后一列)的时候是O(N)的complexity，
: 如果trivial case不是constant time的，可以这样算么。？
|
w*****e
发帖数: 197 | 15 n^2 numbers put in n rows, each row sorted,
you have altogether (n^2)!/[(n!)^n] possibilities,
is it Log >= nlogn ??? I think Sterling's formula
should easily confirm this?
【在 m****y 的大作中提到】
: 如果列之间没有关系，应该不存在快于nlogn的方法了。不难证明。
|
l******o
发帖数: 144 | 16 n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
法硬套在这里。
n^2 numbers put in n rows, each row sorted,
you have altogether (n^2)!/[(n!)^n] possibilities,
is it Log >= nlogn ??? I think Sterling's formula
should easily confirm this?
【在 w*****e 的大作中提到】
: n^2 numbers put in n rows, each row sorted,
: you have altogether (n^2)!/[(n!)^n] possibilities,
: is it Log >= nlogn ??? I think Sterling's formula
: should easily confirm this?
|
l******o
发帖数: 144 | 17 比如n个数unsorted，有n！种可能，难道find a target value需要
log(n!)=nlogn的时间么？显然O(n)就可以了。
n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
法硬套在这里。
n^2 numbers put in n rows, each row sorted,
you have altogether (n^2)!/[(n!)^n] possibilities,
is it Log >= nlogn ??? I think Sterling's formula
should easily confirm this?
【在 l******o 的大作中提到】
: n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
: 我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
: 法硬套在这里。
:
: n^2 numbers put in n rows, each row sorted,
: you have altogether (n^2)!/[(n!)^n] possibilities,
: is it Log >= nlogn ??? I think Sterling's formula
: should easily confirm this?
|
g**********1
发帖数: 1113 | 18 how can you PROVE it?
Do you want to challenge NPC problem ? |
l******o
发帖数: 144 | 19 不要死读书。
n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
法硬套在这里。
n^2 numbers put in n rows, each row sorted,
you have altogether (n^2)!/[(n!)^n] possibilities,
is it Log >= nlogn ??? I think Sterling's formula
should easily confirm this?
【在 l******o 的大作中提到】
: n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
: 我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
: 法硬套在这里。
:
: n^2 numbers put in n rows, each row sorted,
: you have altogether (n^2)!/[(n!)^n] possibilities,
: is it Log >= nlogn ??? I think Sterling's formula
: should easily confirm this?
|
