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)的解
|