文章
37
粉丝
0
获赞
7
访问
3.5k
(1) A与B合并,最坏需要35次比较,得到A'(45个元素);A'与C合并,最坏需要45次比较,得到B'(95个元素);D和E合并,最坏需要60次比较,得到C'(110个元素);B'和C'合并,最坏需要110次比较,得到D'(205个元素);D'与F合并,最坏需要205次比较,得到最终的升序表(405个元素)。总次数为35+45+60+110+205=455次比较。
(2) 使用构建哈夫曼树的思想,每次选取两个元素最少的表合并,直到只剩下一个表。理由:对于两个表来说,其最坏比较次数必然为较长者的长度,那么我们的目标就是让较长者的长度达到最短,因此选择构建哈夫曼树让“非叶结点”的值更小。
登录后发布评论
暂无评论,来抢沙发