Jac*_*ale 18 sorting algorithm data-structures
在算法设计手册中,有这样的消费税
4-26考虑使用比较对n 0和1的序列进行排序的问题.对于两个值x和y的每次比较,算法学习x <y,x = y或x> y中的哪一个.
(a)给出一个算法,在最坏的情况下进行n-1次比较.表明您的算法是最佳的.
(b)给出一种算法,在平均情况下对2n/3次比较进行排序(假设n个输入中的每一个都是0或1,概率相等).表明您的算法是最佳的.
对于(a),我认为这很容易.我可以选择[n-1]作为枢轴,然后执行类似于快速分区的操作,扫描0到n - 2,找到左侧全部为0且右侧全部为1的中间点,这需要进行n - 1次比较.
但对于(b),我无法得到线索.它说"n个输入中的每一个都是0或1,概率相等",所以我想我可以假设0和1的数字相等？但是我怎样才能得到与1/3相关的结果？将整个阵列分成3组？
谢谢
xan*_*xan 11
"0或1具有相同概率"是"平均"情况的条件.其他情况可能有更糟糕的时机.
提示1:2/3 = 1/2 + 1/8 + 1/32 + 1/128 + ......
提示2:将序列视为一对序列,并比较每对中的项目.一半将返回平等; 一半不会.在不相等的一半中,你知道该对中的哪个项目是0,哪个是1,所以那些不需要更多的比较.