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好像有数学上的证明 |
