x*********w 发帖数: 533 | 1 为什么quick sort partition 在中间优于在1/3的位置?
换一个角度说,为什么
T(n) = n + T(n/2) + T(n/2)
优于
T(n) = n + T(n/3) + T(2n/3) |
c*******c 发帖数: 726 | |
x*********w 发帖数: 533 | 3
时间复杂度是一样的不一定constant一样啊
【在 c*******c 的大作中提到】 : 我记得n足够大应该是一样的吧……
|
l*********8 发帖数: 4642 | 4 考虑partition生成的二叉树。 如果加上编码:partition在左边的,标记为0,
partition在右边的,标记为1, 那么就是一颗编码树。 每个元素是均等的, 所以每
次partition分成尽可能相等的两份,得到的是Huffman tree, 编码总长度是最优的,
也就是partition的总比较次数是最少的。
【在 x*********w 的大作中提到】 : 为什么quick sort partition 在中间优于在1/3的位置? : 换一个角度说,为什么 : T(n) = n + T(n/2) + T(n/2) : 优于 : T(n) = n + T(n/3) + T(2n/3)
|
x*********w 发帖数: 533 | 5
有道理,但是....
有没有谁能从本质上说说??
谁数学好点的?
【在 l*********8 的大作中提到】 : 考虑partition生成的二叉树。 如果加上编码:partition在左边的,标记为0, : partition在右边的,标记为1, 那么就是一颗编码树。 每个元素是均等的, 所以每 : 次partition分成尽可能相等的两份,得到的是Huffman tree, 编码总长度是最优的, : 也就是partition的总比较次数是最少的。
|
k***x 发帖数: 6799 | 6 这个得解函数方程了,存在性(排脑袋想出的普通形式)还比较好整,要证明唯一性就
比较费劲
【在 x*********w 的大作中提到】 : : 有道理,但是.... : 有没有谁能从本质上说说?? : 谁数学好点的?
|
g********E 发帖数: 178 | 7 quick sort还是merge sort?
二分法每次少一半,三分法每次只少了1/3 |
l*********8 发帖数: 4642 | 8 本质。。。
排序的本质是消除序列的熵,熵为0就排好序了。
一个未排序数组的熵是: log(N!)
partition 为一半一半, 熵是log( (N/2)! * (N/2)! )
partition 为1/3, 2/3, 熵是log( (N/3)! * (2N/3)! )
因为 (N/2)! * (N/2)! < (N/3)! * (2N/3)!
所以,partition 为一半一半的熵更小。
所以,partition 为一半一半, 减少的熵更多,是更好的方法。
【在 x*********w 的大作中提到】 : : 有道理,但是.... : 有没有谁能从本质上说说?? : 谁数学好点的?
|
x*********w 发帖数: 533 | 9
这个,本质是本质了,有没有不是那么抽象的证明....
【在 l*********8 的大作中提到】 : 本质。。。 : 排序的本质是消除序列的熵,熵为0就排好序了。 : 一个未排序数组的熵是: log(N!) : partition 为一半一半, 熵是log( (N/2)! * (N/2)! ) : partition 为1/3, 2/3, 熵是log( (N/3)! * (2N/3)! ) : 因为 (N/2)! * (N/2)! < (N/3)! * (2N/3)! : 所以,partition 为一半一半的熵更小。 : 所以,partition 为一半一半, 减少的熵更多,是更好的方法。
|
t****t 发帖数: 387 | 10 mit open course好像有数学上的证明 |