d*****y
发帖数: 140 | 1 vector的长度为n，k<
的跟快的办法么？
thx！ | b********e
发帖数: 58 | 2 not a matlab expert. assuming it is using quick sort, the complexity is n*
log(n) then.
If you just do a scanning, should be fixed at n*k, which is better.
If you maintain a k element array and first sort the first k elements in the
vector, then scan through the rest. Every time if the coming element is
smaller then the minimum, drop it. otherwise, use log(k) steps to insert the
new element in the array and drop the smallest one. The worst case will be
n*(log(k)), even better. | b********e
发帖数: 58 | 3 not a matlab expert. assuming it is using quick sort, the complexity is n*
log(n) then.
If you just do a scanning, should be fixed at n*k, which is better.
If you maintain a k element array and first sort the first k elements in the
vector, then scan through the rest. Every time if the coming element is
smaller then the minimum, drop it. otherwise, use log(k) steps to insert the
new element in the array and drop the smallest one. The worst case will be
n*(log(k)), even better. | d*****n
发帖数: 754 | 4 Use max. Remove the max item, then use max again. Repeat k times.
【在 d*****y 的大作中提到】
: vector的长度为n，k<: 的跟快的办法么？
: thx！
| x*****s
发帖数: 39 | 5 1. For example, if the vector n is a random value vector, you can first use
find() to pre-select almost all the k maxima.
ind=find(vectorn>max-(max-min)*k/n)
if the size of ind is greater than that of k, you are almost done. Otherwise
, you can use max() to pick up a few of the missed.
2. Another fast way is to use mex function importing code written in Fortran
or C.
【在 d*****y 的大作中提到】
: vector的长度为n，k<: 的跟快的办法么？
: thx！
| h******g
发帖数: 69 | 6 It should only take around O(k*log2(n)) to find k max numbers in n numbers.
This is a FAQ for algorithm interview.
i am not sure if there is any MATLAB function which implements this
algorithm, but you can write one by yourself. |
|
