合并最差最好情况及推导_雪儿的地盘

个人资料

微博

正文字体大小：大中小

合并最差最好情况及推导

(2014-12-05 22:16:40)

标签：

分类：算法设计与分析基础

.a.对合并排序的最差键值比较次数的递推关系式求解.(for n=2^k)

b.建立合并排序的最优键值比较次数的递推关系式求解.(for n=2^k)

c.对于4.1节给出的合并排序算法,建立它的键值移动次数的递推关系式.考虑了该算法的键值移动次数之后,是否会影响它的效率类型呢?

解:

a. 递推关系式：

b 最好情况(列表升序或降序)下:

C_best(n)=2C_best(n/2)+n/2 for n>1 (n=2^k)

C_best(1)=0

c. 键值比较次数M(n)

M(n)=2M(n)+2n for n>1

M(1)=0

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report