a***n
发帖数: 38 | 1 找中数或者第几大的数，为什么要分成 5个一组， 为什么3个，7个就不行？ 多谢 |
j*****y
发帖数: 1071 | 2 3个好像不行，7个可以
【在 a***n 的大作中提到】
: 找中数或者第几大的数，为什么要分成 5个一组， 为什么3个，7个就不行？ 多谢
|
a***n
发帖数: 38 | 3 能解释一下为什么吗？拜谢
【在 j*****y 的大作中提到】
: 3个好像不行，7个可以
|
d**********x
发帖数: 4083 | 4 去看算法导论，关于 order statistics 那节吧
应该是和 master's theorem 里面的常数有关系的，手边没书，具体的想不起来了
【在 a***n 的大作中提到】
: 能解释一下为什么吗？拜谢
|
j*****y
发帖数: 1071 | 5 比如看 7 个一组把， 就分成了 n/7 组，每组算一个median,
就出来 n/7个 median, 这 n/7个 median 数再找出 mdeian x
现在用 x 做 pivot 来 partion, 比 x 小的至多有 5n/7 个
比 x 大的至多有 5n/7 个
所以 T(n) <= T(n/7) + T(5n/7) + O(n)
T(n) = O(n)
现在看 3个一组, 同样的 idea 能得出
T(n) <= T(n/3) + T(2n / 3) + O(n)
这个时候你会发现右边的两个 sub-size 的和不比 n 小
它们是 n/3 + 2n/ 3 = n, 这个时候得不到 O(n)的解 |
d**********x
发帖数: 4083 | 6 zan...
【在 j*****y 的大作中提到】
: 比如看 7 个一组把， 就分成了 n/7 组，每组算一个median,
: 就出来 n/7个 median, 这 n/7个 median 数再找出 mdeian x
: 现在用 x 做 pivot 来 partion, 比 x 小的至多有 5n/7 个
: 比 x 大的至多有 5n/7 个
: 所以 T(n) <= T(n/7) + T(5n/7) + O(n)
: T(n) = O(n)
: 现在看 3个一组, 同样的 idea 能得出
: T(n) <= T(n/3) + T(2n / 3) + O(n)
: 这个时候你会发现右边的两个 sub-size 的和不比 n 小
: 它们是 n/3 + 2n/ 3 = n, 这个时候得不到 O(n)的解
|
a***n
发帖数: 38 | 7 谢谢你。打了这么多字解释，多谢了。
【在 j*****y 的大作中提到】
: 比如看 7 个一组把， 就分成了 n/7 组，每组算一个median,
: 就出来 n/7个 median, 这 n/7个 median 数再找出 mdeian x
: 现在用 x 做 pivot 来 partion, 比 x 小的至多有 5n/7 个
: 比 x 大的至多有 5n/7 个
: 所以 T(n) <= T(n/7) + T(5n/7) + O(n)
: T(n) = O(n)
: 现在看 3个一组, 同样的 idea 能得出
: T(n) <= T(n/3) + T(2n / 3) + O(n)
: 这个时候你会发现右边的两个 sub-size 的和不比 n 小
: 它们是 n/3 + 2n/ 3 = n, 这个时候得不到 O(n)的解
|
