Redian新闻
>
问一个发表文章相关的问题 (转载)
avatar
问一个发表文章相关的问题 (转载)# Biology - 生物学
w*1
1
a matrix, with each row sorted, but colms are NOT. find a target value.
find a way better than nlogn?
真的不觉得能再快了!
大家讨论下吧, 不知道这题以前在这里出现过吗?
avatar
u*n
2
06/07/2011 Misc. Credit $150 for New Checking $150.00
avatar
w*g
3
现在的娱乐圈整天都是些负面的新闻,正能量的不太多,本来捐款是个正能量的事情,
然而也都搞成了负能量的,吴京被逼捐,而且其他的明星也都差不多,这捐款也成了不
愉快的新闻了,其实明星只要没有逃税之类的,捐款与否还是自己的自由。
再就是出轨的信息,性侵的信息,以及各种财产纠纷和家暴的信息,没有太多的正能量
信息,就算是结婚这种大喜事儿,也都是奢华的攀比,一个比一个花钱多,都是几个亿
的婚礼,这也绝对是负面信息,并不是什么正能量。
所以现在这些娱乐圈的人叫人喜欢不起来,不去努力的钻研演技,带给大家更好的作品
,更是想着办法的只顾着接戏捞钱,甚至现在人气旺比较红,就多接几部戏,多捞点钱
,然而演出来的都实在是很差,一点都不敬业,这样的娱乐圈,是不是应该改一下了。
像赵丽颖这样的就是其中之一,就算刚开始还有观众喜欢她,可是到现在除了那些不理
智的脑残粉之外,正常的观众已经开始反感她了,因为演技没有任何的进步,却不停的
捞钱接戏,不太值得令人称赞了。
avatar
i*9
4
【 以下文字转载自 baby 俱乐部 】
发信人: i999 (爱老公的乖乖), 信区: baby
标 题: 问一个发表文章相关的问题
发信站: BBS 未名空间站 (Sun Sep 4 14:06:42 2011, 美东)
我有一篇从前读书时候做的文章,现在投稿了,改了3轮了,不知道为啥就两个
reviewer第一个reviewer评价极其好,现在完全没有问题了。第二个reviewer给的建议
跟我们做的东西很不相关,一看就是外行,还非得我们加不相干的实验和数据,不管我
们怎么解释,他非得用他外行的观点说我们一个positive control不好。另外坚持我们
加数据。还说我们的数据不足以支撑我们的结论。我们已经按照他的要求把结论改得非
常低调了。他还是死缠烂打,文章返回他就用同一段话还给我们,都三次了。
现在我无法回去加那个完全不相干的实验(开这个实验的头不能给我们文章的结论任何
支持,而且完全是一个巨大的topic,重新做一篇文章都行),我老板转到工业界了,
手上没有资源可以找人做个实验。而且那种外行对positive control的质疑真是死缠烂
打,让我哭笑不得。
请问,这种情况我该怎么办?我老板现在就逼我搞定reviewer#2,其他他不管。看在推
荐信的面子上,我不能不照办啊。有经验的朋友请帮我参考一下解决办法吧。谢谢。
avatar
p*u
5
Dump to hash table. O(n)
avatar
c*b
6
bozi,please
avatar
w*g
7
至少该多表扬一些真正演技好的
avatar
m*r
8
我倒
还以为我走错版了
avatar
r*o
9
我的想法是对每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?
: 真的不觉得能再快了!
: 大家讨论下吧, 不知道这题以前在这里出现过吗?

avatar
i*9
10
我看你的帖子也是这个错觉!xiaxia!

【在 m*******r 的大作中提到】
: 我倒
: 还以为我走错版了

avatar
a*9
11
感觉 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?
: 真的不觉得能再快了!
: 大家讨论下吧, 不知道这题以前在这里出现过吗?

avatar
m*r
12
hehe
patpat,换个杂志投?
欧洲PI从学术去业界比较多点吧?

【在 i**9 的大作中提到】
: 我看你的帖子也是这个错觉!xiaxia!
avatar
g*1
13
this n x n matrix. Not total number is n

【在 p*****u 的大作中提到】
: Dump to hash table. O(n)
avatar
i*9
14
我想建议editor再找一个reviewer,可是我老板说再找reviewer会有更多问题他不肯。

【在 m*******r 的大作中提到】
: hehe
: patpat,换个杂志投?
: 欧洲PI从学术去业界比较多点吧?

avatar
w*e
15
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
avatar
g*1
16

Try to write letter to editor to discredit the second reviewer or let the
editor to get another reviewer for the second opinion.
BTW, why does your PI think that you could address the second reviewer given
the circumstances (he has no lab and you have moved on from his lab already
)? unless you have your own lab, it's impossible to continue that work.
You can tell your PI that you would love to address that when you have your
own lab and resource :)

【在 i**9 的大作中提到】
: 我想建议editor再找一个reviewer,可是我老板说再找reviewer会有更多问题他不肯。
avatar
w*e
17
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

avatar
i*9
18
我pi希望我空手套白狼用empty talk去talk our way out

given
already
your

【在 g****1 的大作中提到】
:
: Try to write letter to editor to discredit the second reviewer or let the
: editor to get another reviewer for the second opinion.
: BTW, why does your PI think that you could address the second reviewer given
: the circumstances (he has no lab and you have moved on from his lab already
: )? unless you have your own lab, it's impossible to continue that work.
: You can tell your PI that you would love to address that when you have your
: own lab and resource :)

avatar
m*y
19
你这算法跟逐行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

avatar
l*n
20
写信给edito,就说reviewer 2 提的意见没有水平,不想干,要求他发。你可以这么说:
reviewer2 提的意见与本文没有太大关系,不能提高我们文章的水平而且不是关键性实
验。我觉得我们无法满足他的要求,建议编辑考虑直接发表。发表不发表就看你的了,
相信你是能帮助我们发表的。
(我看我老板以前就是这么给编辑写的)。
如果reviewer2很牛,那你怎么也发表不了了。
avatar
m*y
21
如果列之间没有关系,应该不存在快于nlogn的方法了。不难证明。

【在 w*****1 的大作中提到】
: a matrix, with each row sorted, but colms are NOT. find a target value.
: find a way better than nlogn?
: 真的不觉得能再快了!
: 大家讨论下吧, 不知道这题以前在这里出现过吗?

avatar
l*o
22
正想吐槽来着,你自己发现了。

My algorithm is WRONG. Sorry for the confusion.

【在 w*****e 的大作中提到】
: My algorithm is WRONG. Sorry for the confusion.
avatar
x*r
23
不是很了解你的意思
如果你是说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

avatar
x*r
24
请问如果用master theorem怎么证明这个算法是2n*log3(N)
虽然intuitively很容易解释。。
谢谢:)

【在 m****y 的大作中提到】
: 你这算法跟逐行binary search毫无区别,把2换成了3而已
: 你的复杂度是2n*log3(n)

avatar
l*o
25
他自己都说自己错了。
其实就是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的,可以这样算么。?

avatar
x*r
26
我好像是早上开的帖子,晚上回来刚看到就回了,不知道已经讨论了那么多了: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的,可以这样算么。?

avatar
w*e
27
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的方法了。不难证明。
avatar
l*o
28
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?

avatar
l*o
29
比如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?

avatar
g*1
30
how can you PROVE it?
Do you want to challenge NPC problem ?
avatar
l*o
31
不要死读书。

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?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。