杭州交通信息网电视剧湘西剿匪记全集:并归排序:并归长度为2的平均比较次数
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/08 17:53:33
并归排序中的关键码比较次数一般较高，因为他不考虑一个表之前结束的事实。例如：第一个表中的所有元素都在第二个表中任何元素之前的情况是可能发生的，因此比较次数仅是第一个的长度。在本练习中，假设俩个表中所有的元素各不相同，并且这些元素的各种排序出现的频率相同。
(1)证明本算法在归并长度为2的俩个有序表时执行的平均次数是8/3。
(2)证明在并归长度在3的俩个有序表时进行比较的平均次数是4.5。
(3)证明在并归长度在4的俩个有序表时进行比较的平均次数是6.4。
(4)证明当m趋于无穷时，并归长度为m的俩个有序表时进行比较的平均次数接近2m-2。
(1)证明本算法在归并长度为2的俩个有序表时执行的平均次数是8/3。
(2)证明在并归长度在3的俩个有序表时进行比较的平均次数是4.5。
(3)证明在并归长度在4的俩个有序表时进行比较的平均次数是6.4。
(4)证明当m趋于无穷时，并归长度为m的俩个有序表时进行比较的平均次数接近2m-2。
M趋进无穷时，频率应该是最大值````