算法导论2 Problems 答案
2-1
a
插入排序的时间复杂度为$\Theta(k^2)$，这个长度为$n$的数组中，有$\dfrac{n}{k}$个长度为$k$的数组。因此插入排序部分的时间复杂度为$\Theta(k^2)\cdot \dfrac{n}{k}=\Theta(nk)$。
b
先两两将长度为$k$的数组合并成长度为$2k$的，再两两将每个$2k$的数组合并成$4k$的……可以发现这个合并过程是一颗树，整棵树的高度是$\Theta\left(\lg \dfrac{n}{k}\right)$。并且，在每一层的合并过程中，整个数组中的所有数恰好都被遍历了一次，花费的时间复杂度总和为$\Theta(n)$。因此，最坏情况下合并这$k$个数组的时间复杂度为$\Theta\left(n\cdot \lg \dfrac{n}{k}\right)$。
c
修改后的归并排序算法为$\Theta\left(nk + n \lg\dfrac{n}{k}\right)$，也就是$\Theta(nk+n\lg n-n\lg k)$。继续进行如下变换：
$\begin{aligned}
\Theta\left(nk + n \lg\dfrac{n}{k}\right)&=\Theta(nk+n\lg n-n\lg k)\
&=\Theta(n(k-\lg k)+n\lg n)\
&=\Theta(nk+n\lg n)
\end{aligned}$
不难发现$\Theta(k-\lg k)=\Theta(k)$。
按照上面的式子不难看出，只有当$k=\Theta(\lg n)$时，改进后的归并排序算法才能够达到$\Theta(n\lg n)$。
d
根据机器性能多次检验后，$k$将在$\Theta(\lg n)$附近的值中选择。
2-2
a
还需要证明$A’$是$A$的一个置换（也就是说，$A’$的元素都来自于$A$）。
b
循环不变量：$A[j]$是数组$A[j:n]$中的最小值。
初始化：一开始只有一个元素$A[n]$，一个元素的数组的最小值肯定是它自身。
保持：在迭代轮次$j$前，$A[j]$是数组$A[j:n]$的最小值。如果$A[j-1]\le A[j]$，那么$A[j-1]$是数组$A[j-1:n]$的最小值；否则，$A[j]<A[j-1]$，交换$A[j]$和$A[j-1]$后，$A[j-1]$就变成了数组$A[j-1:n]$的最小值。
终止：当$j=i$时循环终止。根据循环不变量，$A[i]$就是数组$A[i:n]$的最小值。
c
循环不变量：数组$A[1:i-1]$是由数组的前$i-1$小的元素升序排列。
初始化：一开始数组是空的，因此是有序的。
保持：在第$i$次循环前，数组$A[1:i-1]$是前$i-1$小的元素升序排列。根据内循环的循环不变量，第$i$次循环完成后，$A[i]$是数组$A[i:n]$的最小值，那么$A[i]$是数组中第$i$小的元素。最终，数组$A[1:i]$是前$i$小的元素升序排列。
终止：最终$i=n+1$，算法终止。根据循环不变量，此时数组$A[1:n]$是由数组的前$n$小的元素升序排列。
d
可以发现，在第$i$次迭代中，内循环总是进行了$n-i$次。最终外循环结束后，总共的运行时间为$\Theta(n^2)$（无论是平均情况还是最坏情况），这与插入排序最坏情况相同。
2-3
a
b
1 | HORNER-NAIVE(A, n, x) |
在第$i$次迭代中，内循环迭代了$i$次，因此整个算法的运行时间为$\Theta(n^2)$，相比原算法慢了很多。
c
令$\displaystyle{p(i)=\sum_{k=0}^{n-(i+1)} A[k+i+1]\cdot x^k}$
初始化：容易发现$p(n)=0$，因为此时求和式的上限值为$-1$，与定义相同。
保持：在第$i$次循环前，$p$的值为$p(i)$。那么在$p(i)$次循环完成后，数值已经变成$p(i)\cdot x+A[i]$。进行以下恒等变换：
$\begin{aligned}
\left(x\cdot \sum{k=0}^{n-(i+1)} A[k+i+1]\cdot x^k\right) + A[i]&=\left( \sum{k=0}^{n-(i+1)} A[k+i+1]\cdot x^{k+1}\right) + A[i]\
&=\left( \sum{k=1}^{n-i} A[k+i]\cdot x^k\right) +A[i]\cdot x^0\
&=\sum{k=0}^{n-i} A[k+i]\cdot x^k\
&=\sum_{k=0}^{n-((i-1)+1)} A[k+(i-1)+1]\cdot x^k\
&=p(i-1)
\end{aligned}$
那么可以发现，完成一次迭代后，$p$的值从$p(i)$转换成$p(i-1)$，循环不变量相同。
终止：当$i=-1$时，循环终止。那么可以发现$\displaystyle{p(-1)=\sum_{k=0}^{n} A[k]\cdot x^k}$，与最终目标所求值一致，因此算法时正确的。
2-4
a
$[(1,5),(2,5),(3,4),(3,5),(4,5)]$
b
置换$\langle n,n-1,n-2,\dots,1\rangle$能够得到最多的逆序数（每一对都包含），其值为$n-1+n-2+\dots + 0=\dfrac{n(n-1)}{2}$。
c
以下是插入排序算法的代码：
1 | INSERTION-SORT(A, n) |
假设$f(i)$的含义是：对于下标元素$A[i]$，满足$j< i, A[j]>A[i]$的下标$j$的数量。数组$A$的逆序数就为$\sum_{i=1}^n f(i)$。
那么，程序的运行时间和值$\sum_{i=1}^n f(i)$线性相关。对于第$i$次循环，while循环体内做的事情恰好是将比所有比$A[i]$大的数向右边移动。最终整个程序的运行时间和这个逆序数线性相关。
d
程序CAL-INVERSION(A, p, r)：计算数组$A[p:r]$中的逆序数，并且对$A[p:r]$进行归并排序。
1 | CAL-INVERSION(A, p, r) |
程序MERGE2(A, p, q, r)：数组$A[p:q],A[q+1:r]$已经有序。将这两个有序数组合并时产生的逆序数。这个程序由程序MERGE(A, p, q, r)修改而来。
1 | MERGE2(A, p, q, r) |