发信人: coconut (coconut), 信区: Programming
标 题: Re: an algorithm question
发信站: Unknown Space - 未名空间 (Thu Aug 19 16:52:56 2004), 站内信件
The algorithm I mentioned is O (size) no matter what N is. Grab a
Also, the N variable can be discarded. Either it is so small
comparing to size, it is effectively a constant. Or it is on
the order of size, say size/2. Let me also remind you that
algorithms such as finding the median etc are O (size).
A property of divide-n-conquer algorithm is that if you can
at each iteration, reduce the total size of the problem to
a proportionally smaller problem, the entire solution is
【 在 perlgolf (perlgolf) 的大作中提到: 】
: 【 在 coconut (coconut) 的大作中提到: 】
: : 1. get N largest numbers from the array O (size).
: : look it up in any algorithm book.
: : 2. sum.
: you sure? what if N is not constant? should it be N*size?
Imagine the most witty and concise verbal gem ever uttered.
Now imagine I said it, and quoted it here.
※ 来源:．Unknown Space - 未名空间 mitbbs.com．[FROM: 4.29.]