序列中元素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)。

A.19所示的插入排序算法List::insertionSort()，试证明：
a)若所有逆序对的间距均不超过k，则运行时间为o(kn);
b)特别地，当k为常数时，插入排序可在线性时间内完成;
c)若共有I个逆序对，则关键码比较的次数不超过o(I);
d)若共有I个逆序对，则运行时间为o(n+I)。

【参考答案】

a)算法进入到A[j]所对应的那步迭代时，该元素(在输入序列中)的所有前驱应该业已构成一个有序子序列A[0，j)，既然其......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)