数据结构考研分类复习真题 第十章 答案[7]

可以做到取a与b进行比较c与d进行比较设a>bc>d(a<b和c<d情况类似)此时需次比较取b和d比较若b>d则有序a>b>d若b<d时则有序c>d>b此时已进行了次比较再把另外两个元素按折半插入排序方法插入到上述某个序列中共需次比较从而共需次比较

本题答案之一请参见第章的四应用题第题这里用分治法求解再给出另一参考答案

对于两个数x和y经一次比较可得到最大值和最小值对于三个数xyz最多经次比较可得最大值和最小值对于n(n>)个数将分成长为n和的前后两部分A和B分别找出最大者和最小者MaxAMinAMaxBMinB最后Max={MaxAMaxB}和Min={MinAMinB}对A 使用同样的方法求出最大值和最小值直到元素个数不超过设C(n)是所需的最多比较次数根据上述原则当n>时有如下关系式

C(n)=

通过逐步递推可以得到C(n)=én/ù显然当n>=时n>n/事实上én/ù是解决这一问题的比较次数的下限

假定待排序的记录有n个由于含n个记录的序列可能出现的状态有n!个则描述n个记录排序过程的判定树必须有n!个叶子结点因为若少一个叶子则说明尚有两种状态没有分辨出来我们知道若二叉树高度是h则叶子结点个数最多为h反之若有u个叶子结点则二叉树的高度至少为éloguù+这就是说描述n个记录排序的判定树必定存在一条长度为élog(n!)ù的路径即任何一个籍助比较进行排序的算法在最坏情况下所需进行的比较次数至少是élog(n!)ù根据斯特林公式有élog(n!)ù =O(nlogn)即籍助于比较进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlogn)证毕

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []