序列中元素A[i]和A[j]若满足i<j且A[i]>A[j],则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort(),试证明:
a)若所有逆序对的间距均不超过k,则运行时间为o(kn);
b)特别地,当k为常数时,插入排序可在线性时间内完成;
c)若共有I个逆序对,则关键码比较的次数不超过o(I);
d)若共有I个逆序对,则运行时间为o(n+I)。
教材81页代码3.20中的List::selectionSort()算法,通过selectMax()在前缀子序列中定位的最大元素max,有可能恰好就是tail的前驱——自然,此时“二者”无需交换。针对这一“问题”,你可能会考虑做些“优化”,以期避免上述不必要的交换,比如将
a)以序列(1980,1981,1982,...,2011,2012;0,1,2,...,1978,1979)为例,这种情况共发生多少次?
b)试证明,在各元素等概率独立分布的情况下,这种情况发生的概率仅为1nn/n→0——也就是说,就渐进意义而言,上述“优化”得不偿失。
A.记载、计算、考查
B.记载、计算
C.计算、考查
D.记载、考查