算法 - 如何使用2n / 3比较对0/1数组进行排序? [英] algorithm - How to sort a 0/1 array with 2n/3 comparisons?
问题描述
在算法设计手册中,有这样一个消费者
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组?
谢谢
0或1等概率是平均情况的条件。提示1:2/3 = 1/2 + 1/8 + 1/32 + 1/128 + ...
p>
提示2:将序列作为对的序列,并比较每对中的项目。一半会平等回报;一半不会。在不平等的一半中,你知道该对中的哪个项目是0,哪个是1,所以这些不需要比较。
In Algorithm Design Manual, there is such an excise
4-26 Consider the problem of sorting a sequence of n 0’s and 1’s using comparisons. For each comparison of two values x and y, the algorithm learns which of x < y, x = y, or x > y holds.
(a) Give an algorithm to sort in n − 1 comparisons in the worst case. Show that your algorithm is optimal.
(b) Give an algorithm to sort in 2n/3 comparisons in the average case (assuming each of the n inputs is 0 or 1 with equal probability). Show that your algorithm is optimal.
For (a), I think it is fairly easy. I can choose a[n-1] as pivot, then do something like in quicksort partition, scan 0 to n - 2, find the middle point where left side is all 0 and right side is all 1, this take n - 1 comparisons.
But for (b), I can't get a clue. It says "each of the n inputs is 0 or 1 with equal probability", so I guess I can assume the numbers of 0 and 1 equal? But how can I get a result which is related to 1/3? divide the whole array into 3 groups?
Thanks
"0 or 1 with equal probability" is the condition for "average" case. Other cases may have worse timing.
Hint 1: 2/3 = 1/2 + 1/8 + 1/32 + 1/128 + ...
Hint 2: Consider the sequence as a sequence of pairs and compare the items in each pair. Half will return equal; half will not. Of the half that are unequal you know which item in the pair is 0 and which is 1, so those need no more comparisons.
这篇关于算法 - 如何使用2n / 3比较对0/1数组进行排序?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!