本文共 2712 字，大约阅读时间需要 9 分钟。

http://www.cnblogs.com/Jiajun/archive/2013/05/02/3055460.html

2-1
a. 每个子序列的元素数量为k，最差的情况下需要进行 k(k−1)/2 次基础操作，一共有 n/k 个子序列，所以总的基础操作次数为

b. 每一遍归并都对所有元素进行拷贝，所以单次复杂度为 Θ(n) ，而将n/k组子序列归并为一个序列最多需要 lg⌊n/k⌋ 次，所以总的时间复杂度为 Θ(nlgn/k)
c. 由前两问的结果可知，复杂度为 Θ(nk+nlgn/k) 。要找到最大的k就应该使得 Θ(nk) 和 Θ(nlgn/k) 的增长率相等，这时 k=lgn ，即
d. 实际应用上k应该选取使得插入排序和归并排序运行时间相同时的输入规模，充分发挥插入排序常数系数小的优势。

2-2
a. 需要证明最终的序列是非递减的，还需要证明最终序列是原序列的一种排列。
b.

• Initialization: 一开始j=A.length，有A[j]不大于子序列[j, A.length]中的元素；
• Maintenance: 接下来，每次循环开始的时候都有A[j]不大于子序列[j, A.length]中的元素。而每次循环都把A[j]和A[j-1]中较小的元素放到A[j-1]，则有A[j-1]不大于子序列[j－1, A.length]中的元素，然后让j减1，满足了循环初始的条件，由于只做了比较和交换操作，所以序列[i, A.length]只是原来序列的一种排列。
• Termination: 最后当循环退出的时候有A[i]不大于子序列[i, A.length]中的元素，即A[i]是子序列[i, A.length]中最小的之一。

c.

• Initialization: 一开始i=1，[1, i－1]中的元素非递减，且[i, A.length]中的元素都不小于[1, i-1]中的元素；
• Maintenance: 接下来，每次循环开始的时候都有[1, i-1]中的元素非递减，且[i, A.length]中的元素不小于[1, i-1]中的元素。而每次循环都把A[i]和[i, A.length]中最小的之一交换，又A[i]不小于[1, i-1]中的元素，所以[1, i]中的元素非递减，且[i+1, A.length]中的元素都不小于[1, i]中的元素，这时i增加1，满足了循环初始的条件。
• Termination: 最后当循环退出的时候有[1, A.length-1]中的元素非递减，且A.length不小于[1, i-1]中的元素。所以整个序列[1, A.length]非递减。

d. 最差的情况下，冒泡排序(bubblesort)需要进行 n(n−1)/2 次比较，所以时间复杂度为 Θ(n2) 和插入排序一致；在最好的情况下，比较的次数不变，而插入排序比较的次数减少为n-1次，总体来说效率比插入排序差。

2-3
a. 循环中的运算可以在常量时间内完成，所以复杂度是 Θ(1) ，循环次数为n，所以总的时间复杂度为 Θ(n) 。
b.

两重循环内的乘法运算次数最多，总数为 所以时间复杂度为 Θ(n2) ，效率低于霍纳法则(Horner's Rule)。
c. 当循环进行到最后一次时，i = 0，可得 得到所求 
d. 根据c的循环不变式可以保证该算法所得结果正确。

2-4
a. (8, 6) (2, 1) (3, 1) (8, 1) (6, 1) 
b. 拥有逆序数最多的是  {

n,n−1,⋯,3,2,1} ，其中任意两个数之间都是逆序的，所以总计 n(n−1)/2 个。
c. 逆序数应该与元素移动的数量相同。插入排序每次移动元素都将一个较大的数移到较小的数后面，使得总逆序数减少1，而排序完成后逆序数是0，所以开始的逆序数和元素移动的次数相同。
d.

利用归并排序，先算出每个子序列的逆序数并排序，使得子序列的逆序数为0，然后再归并成更大的序列并重复计算，最后所有子序列的逆序总和为所求。
在Merge过程中如果R序列中的元素 rj 出现在L中的元素 li 之前，说明 rj 与 [li,ln1] 中的所有元素都组成逆序数，一共有n1 - i + 1个。