d****n
发帖数: 130 | 1 Give efficient algorithms for finding the largest k values (in order) out of
a set of n, using comparisons only (e.g. no hashing), in the case where: (a
) k = 3 (b) k = n/2; (c) k = log(n). (You can use a different algorithm for
each case.) State the asymptotic worst-case running time of your algorithms.
"
(b)and (c)有什么不同? |
v*****u
发帖数: 1796 | 2 (b): O(n) -- O(n) to find median and then another n to seperate the set
(c): no idea.
of
(a
for
algorithms.
【在 d****n 的大作中提到】
: Give efficient algorithms for finding the largest k values (in order) out of
: a set of n, using comparisons only (e.g. no hashing), in the case where: (a
: ) k = 3 (b) k = n/2; (c) k = log(n). (You can use a different algorithm for
: each case.) State the asymptotic worst-case running time of your algorithms.
: "
: (b)and (c)有什么不同?
|
C*******l
发帖数: 105 | 3 土问一下，O(n)能找出median吗？
【在 v*****u 的大作中提到】
: (b): O(n) -- O(n) to find median and then another n to seperate the set
: (c): no idea.
:
: of
: (a
: for
: algorithms.
|
d****n
发帖数: 130 | 4 (b) 结果中的K个数字是要SORT好的。你这方法比quick selection快？
【在 v*****u 的大作中提到】
: (b): O(n) -- O(n) to find median and then another n to seperate the set
: (c): no idea.
:
: of
: (a
: for
: algorithms.
|
