内容简介：本书介绍的第一个算法是利用本节以上面介绍的插入排序为例，展示如何分析算法的运行时间。用常数$c_i$表示计算机模型中基本操作所耗费的时间，推导出整个算法所需时间关于输入规模$n$的函数$T(n)$。算法分析一般只考察
本书介绍的第一个算法是 插入排序 算法。插入 排序 的工作机理和很多人打牌时，整理手中牌时的做法差不多。根据 排序算法 的伪代码，给出如下的 C语言 实现：
void sort(int nums[], int n)
{
for (int i = 1; i < n; i++) {
int key = num[i];
int j;
for (j = i - 1; key < num[j] && j >= 0; j--) {
num[j+1] = num[j];
}
num[j+1] = key;
}
}
利用 循环不变式 可以证明排序算法的正确性。
分析算法
本节以上面介绍的插入排序为例，展示如何分析算法的运行时间。用常数$c_i$表示计算机模型中基本操作所耗费的时间，推导出整个算法所需时间关于输入规模$n$的函数$T(n)$。算法分析一般只考察 最坏情况运行时间 ，这是算法运行时间的上界。
当$n$很大时，$T(n)$的低阶项相对来说不太重要，高阶项的常系数也不重要。忽略它们后，只剩下最重要项的因子。例如，对于插入排序，只剩下$n^2$。我们记插入排序的最坏情况时间代价为$\Theta(n^2)$。
算法设计
本节介绍一种常用设计策略，叫做 分治法 （divide and conquer）。 归并排序 算法遵循分治模式，直观上其操作如下：
- 分解：将$n$个元素分成各含$n/2$个元素的子序列
- 合并：合并两个已排序的子序列以得到排序结果
当待排序的序列长度为1时，递归“开始回升”，在这种情况下不做任何工作，因为长度为1的每个序列已排好序。
为完成算法，需要一个完成合并的辅助过程。由于两个子序列是已经排序好的，所以合并步骤的时间复杂度仅为$\Theta(n)$。它的代码如下：
void merge(int nums[], int aux[], int left, int mid, int right)
{
// 将原数组nums中的元素拷贝到预先分配的辅助数组aux中
for (int k = left; k <= right; k++) {
aux[k] = nums[k];
}
int i = left;
int j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
nums[k] = aux[j++];
} else if (j > right) {
nums[k] = aux[i++];
} else if (aux[j] < aux[i]) {
nums[k] = aux[j++];
} else {
nums[k] = aux[i++];
}
}
}
下面便是递归调用过程的代码， merge_sort
也是辅助过程， sort
是最终的接口函数：
void merge_sort(int nums[], int aux[], int left, int right)
{
if (left < right) {
int mid = left + (right - left)/2;
merge_sort(nums, aux, left, mid); // 递归排序左边
merge_sort(nums, aux, mid + 1, right); // 递归排序右边
merge(nums, aux, left, mid, right); // 合并已排序好的两个数组
}
}
void sort(int nums[], int n)
{
// 开辟动态内存，作为参数传入
int *aux = malloc(n * sizeof(int));
if (aux != NULL) {
merge_sort(nums, aux, 0, n - 1);
free(aux);
} else {
printf("Error: malloc() failed!\n");
}
}
当算法包含对其自身的递归调用时，要利用 递归方程 或 递归式 来描述其运行时间。对于上述的归并排序，算法分解成两个子问题加上一个合并过程，所以递归方程如下：
$$
T(n) =
\begin{cases}
c, & \mbox{若} n=1 \\
2T(n/2)+cn, & \mbox{若} n>1
\end{cases}
$$
根据上面的递归公式，可以计算出归并排序算法的时间复杂度为$\Theta(n \log n)$。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 算法导论阅读笔记 --- 排序算法
- 算法导论学习笔记5 随机算法
- 『算法导论』第 7 章：快速排序
- js实现多种排序算法（算法导论第二章）
- 『算法导论』第 8 章：线性时间排序
- 机器学习的算法和普通《算法导论》里的算法有什么本质上的异同？
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
