i**9
发帖数: 351 | 1 大家都知道找最大值和最小值 的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
什么技巧吗？ |
u******e
发帖数: 758 | 2 merge sort?
【在 i**9 的大作中提到】
: 大家都知道找最大值和最小值 的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
: 什么技巧吗？
|
D***h
发帖数: 183 | 3 tournament tree
【在 i**9 的大作中提到】
: 大家都知道找最大值和最小值 的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
: 什么技巧吗？
|
g*****k
发帖数: 623 | 4 这个类似吧。
两两比较得到(a1, a2), (b1, b2)，。。。
共比较n/2
比较a2和b2,
如果a2大，那么再比较a1和b2
如果b2大，那么再比较b1和a2
这一步比较2(n/2)次
一共比较3n/2
【在 i**9 的大作中提到】
: 大家都知道找最大值和最小值 的最佳比较次数 3n/2 (两两比较)，找最大和次大的有
: 什么技巧吗？
|
c******a
发帖数: 789 | |
i**9
发帖数: 351 | 6 thanks, 总之，这个是要 extra memory, 这里有人提过不用extra memory ,我想了半
天也没想
出来，
【在 D***h 的大作中提到】
: tournament tree
|
x*****p
发帖数: 1707 | 7 It only need two extra-memory. Start with (a1,a2) with a1>a2. Then for each
a3, ..., an, compare at most twice to (a1,a2) and do corresponding
replacement. So the total comparison is at most 1 + 2(n-2) = 2n - 3 = O(n). |
i**9
发帖数: 351 | 8 using tournament tree only n+ lgn -2 times of comparison are needed
each
O(n).
【在 x*****p 的大作中提到】
: It only need two extra-memory. Start with (a1,a2) with a1>a2. Then for each
: a3, ..., an, compare at most twice to (a1,a2) and do corresponding
: replacement. So the total comparison is at most 1 + 2(n-2) = 2n - 3 = O(n).
|
P********l
发帖数: 452 | 9 What is the memory requirement of your tournament?
If it is n, why not use heap? It just requires n times comparison.
【在 i**9 的大作中提到】
: using tournament tree only n+ lgn -2 times of comparison are needed
:
: each
: O(n).
|
g*********s
发帖数: 1782 | 10 2n -3 could be 33% slower than 1.5n solution, although both O(N).
each
O(n).
【在 x*****p 的大作中提到】
: It only need two extra-memory. Start with (a1,a2) with a1>a2. Then for each
: a3, ..., an, compare at most twice to (a1,a2) and do corresponding
: replacement. So the total comparison is at most 1 + 2(n-2) = 2n - 3 = O(n).
|
P********l
发帖数: 452 | 11 Compare one round for the largest, n-1.
Compare another round for the second largest, n-2. |
