计算模型

在能够分析算法之前，我们必须有一个要使用的实现技术的模型，包括描述所用资源及其代价的模型。对于本书的大多数章节，我们假定一种通用的单处理器计算模型——随机访问机（RAM）来作为我们的实现技术。在RAM模型中，指令是一条一条执行。

#插入排序算法的分析

一个算法在特定输入上的运行时间是指执行的基本操作数或步数。执行每行代码需要常量时间。虽然一行与另一行可能需要不同数量的时间，但是我们假设第i行的每次执行需要时间$c_i$ci​，其中$c_i$ci​是一个常量。

对于插入排序，对j=2,3,…,n，其中n=A.length，假设$t_j$tj​表示对那个值j第5行执行while循环测试的次数。当一个for或while循环按通常的方式（即循环头中的测试）退出时，执行测试的次数比执行循环体的次数要多1。

运行时间$T[n]$T[n]:

$T(n)=c_1n+c_2(n-1)+c_4(n-1)+c_5\sum_{j=2}^{n}t_j+c_6\sum_{j=2}^{n}(t_j-1)+c_7\sum_{j=2}^{n}(t_j-1)+c_8(n-1)$T(n)=c1​n+c2​(n−1)+c4​(n−1)+c5​j=2∑n​tj​+c6​j=2∑n​(tj​−1)+c7​j=2∑n​(tj​−1)+c8​(n−1)

即使对给定规模的输入，一个算法的运行时间也可能依赖于给定的是该规模的哪种输入。对于插入排序，若输入数组已经有序，那么出现最好情况。此时$t_j=1$tj​=1，有
$T(n)=c_1n+c_2(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1) \\ \ \ \ \ \ \ =(c_1+c_2+c_4+c_5+c_8)n-(c_1+c_2+c_4+c_5+c_8)$T(n)=c1​n+c2​(n−1)+c4​(n−1)+c5​(n−1)+c8​(n−1)      =(c1​+c2​+c4​+c5​+c8​)n−(c1​+c2​+c4​+c5​+c8​)
我们可以把该运行时间表示为$an+b$an+b，其中常量a跟b依赖于语句代价$c_i$ci​。因此它是n的线性函数。

若输入数组是反向数组，那么出现最坏情况。此时$t_j=j$tj​=j，注意到:
$\sum_{j=2}^{n}j=\frac{(2+n)} {2}(n-1)\\ \ \ \ \ \ = \frac{n(n+1)} {2}-1$j=2∑n​j=2(2+n)​(n−1)     =2n(n+1)​−1
或
$\sum_{j=2}^{n}(j-1)=\frac{n(n-1)} {2}$j=2∑n​(j−1)=2n(n−1)​
所以
$T(n)=(\frac{c_5} {2}+\frac{c_6} {2}+\frac{c_7} {2})n^2+(c_1+c_2+c_4+\frac{c_5} {2}-\frac{c_6} {2}-\frac{c_7} {2}+c_8)n-(c_2+c_4+c_5+c_8)$T(n)=(2c5​​+2c6​​+2c7​​)n2+(c1​+c2​+c4​+2c5​​−2c6​​−2c7​​+c8​)n−(c2​+c4​+c5​+c8​)
我们可以把该运行时间表示为$an^2+bn+c$an2+bn+c，其中常量a、b跟c依赖于语句代价$c_i$ci​。因此它是n的二次函数。
因此，插入排序的最好情况运行时间是线性函数，最坏情况运行时间是二次函数。

在分析算法时，我们往往只会集中求最坏情况运行时间，即对于规模为n的如何输入，算法的最长运行时间。

练习

答：略。

答：伪代码：

for j = 1 to A.length - 1
	least = j
	i = j + 1
	while i <= A.length
		if A[least] > A[i]
			least = i
		i = i + 1
	temp = A[j]
	A[j] = A[least]
	A[least] = temp

把for循环每次开始，包含元素$A[1..j-1]$A[1..j−1]的数组称为子数组，它的循环不变式如下：

1. 初始化：在第一次循环迭代之前（当j=1时），此时子数组没有元素。
2. 保持：在每次循环开始时，在整个数组的剩余元素中找出最小的元素，放到子数组的末尾，所以在第n次迭代之前，此时子数组$A[1..n-1]$A[1..n−1]，其中$A[1]$A[1]是整个数组的最小元素，$A[2]$A[2]是倒数第二小的元素，以此类推，直到$n-1$n−1，所以子数组有序；然后进行本次迭代，找出$A[n..a.length]$A[n..a.length]中最小的元素跟$A[n]$A[n]交换，此时$A[n]$A[n]是数组中倒数第n小的元素，大于等于$A[1..n-1]$A[1..n−1]中的任何元素，所以在第n+1次迭代之前，子数组$A[1…n]有序。
3. 终止：当j=A.length时，循环终止。此时子数组$A[1..A.length-1]$A[1..A.length−1]有序，且$A[A.length]$A[A.length]是最大的元素，所以整个数组有序，算法正确。

在排序时，每次都选出第N小的元素，在迭代进行都n-1个元素时，该元素是第n-1小，所以剩余的最后一个元素是第n小，也就是最大，所以整个数组已经有序，不再需要对最后一个元素进行排序。

根据伪代码可得：

$T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4\sum_{j=1}^{n-1}t_j+c_5\sum_{j=1}^{n-1}(t_j-1)+c_6\sum_{j=1}^{n-1}(t_j-1)+c_7\sum_{j=1}^{n-1}(t_j-1)+c_8(n-1)+c_9(n-1)+c_{10}(n-1)$T(n)=c1​n+c2​(n−1)+c3​(n−1)+c4​j=1∑n−1​tj​+c5​j=1∑n−1​(tj​−1)+c6​j=1∑n−1​(tj​−1)+c7​j=1∑n−1​(tj​−1)+c8​(n−1)+c9​(n−1)+c10​(n−1)

当数组有序，不需要执行least = i语句，此时出现最好情况。

$T(n)= (\frac{c_4} {2}+\frac{c_5} {2}+\frac{c_7} {2})n^2 \\ +(\frac{c_4} {2}-\frac{c_5} {2}-\frac{c_7} {2}+c_1+c_2+c_3+c_8+c_9+c_{10})n \\ -(c_2+c_3+c_4+c_8+c_9+c_{10})$T(n)=(2c4​​+2c5​​+2c7​​)n2+(2c4​​−2c5​​−2c7​​+c1​+c2​+c3​+c8​+c9​+c10​)n−(c2​+c3​+c4​+c8​+c9​+c10​)

我们可以把该运行时间表示为$an^2+bn+c$an2+bn+c，其中常量a、b跟c依赖于语句代价$c_i$ci​。因此它是n的二次函数。

当数组逆向有序，每次都会执行least = i语句，此时出现最坏情况。
$T(n)= (\frac{c_4} {2}+\frac{c_5} {2}+\frac{c_6} {2}+\frac{c_7} {2})n^2 \\ +(\frac{c_4} {2}-\frac{c_5} {2}-\frac{c_6} {2}-\frac{c_7} {2}+c_1+c_2+c_3+c_8+c_9+c_{10})n \\ -(c_2+c_3+c_4+c_8+c_9+c_{10})$T(n)=(2c4​​+2c5​​+2c6​​+2c7​​)n2+(2c4​​−2c5​​−2c6​​−2c7​​+c1​+c2​+c3​+c8​+c9​+c10​)n−(c2​+c3​+c4​+c8​+c9​+c10​)

可以得出结论，选择排序的最好情况运行时间和最坏情况运行时间都为$\Theta(n^2)$Θ(n2)。

答：

平均需要检查输入序列$(n+1)/2$(n+1)/2个元素，在最坏情况下需要检查n个元素。平均情况跟最坏情况的运行时间都为$\Theta(n)$Θ(n)。

证明：根据平均查找长度公式

$ASL=\sum_{i=1}^{n} p_ic_i$ASL=i=1∑n​pi​ci​

其中：$p_i$pi​为查找表中第i个数据元素的概率，$c_i$ci​为找到第i个数据元素时已经比较过的次数。
其平均查找长度为$(n+1)/2$(n+1)/2。
若考虑元素不在数组中的情况，则平均需要检查输入序列$n/2+n/(n+1)$n/2+n/(n+1)个元素
因为查找的过程就是关键字比较的过程，比较次数的多少就是算法的时间复杂度，所以平均情况跟最坏情况的运行时间都为$\Theta(n)$Θ(n)。

答：可以在运行算法之前先检查输入是否是最好情况，如果是，则运行以最好情况条件下编写的算法，以获得最好的最好情况运行时间；如果不是，则运行普通的算法。如我们改变现在排序，我们先判断输入是否有序，如果已经有序，则直接返回，否则运行普通的选择排序。这样修改后，选择排序的最好情况运行时间为$\Theta(n)$Θ(n)。