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

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

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

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

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

　　C(n)=

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

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