[TOC]
# 第一章(算法设计基础) #
## 知识点 ##
```
1、算法的性质：正确性、健壮性、可理解性、抽象分级、高效性。
2、算法的描述方法：自然语言、流程图、程序设计语言、伪代码。
3、算法的重要特性：输入，输出，有穷，确定，可行。
4、算法：对特定问题求解
```
## 课后题 ##
### 习题四 ###
```c++
//设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。
#include<iostream>
using namespace std;
int main()
{
int a[]={1,2,3,6,4,9,0};
int mid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它
for(int i=0;i!=4;++i)
{
if(a[i+1]>a[i]&&a[i+1]<a[i+2])
{
mid_value=a[i+1];
cout<<mid_value<<endl;
break;
}
else if(a[i+1]<a[i]&&a[i+1]>a[i+2])
{
mid_value=a[i+1];
cout<<mid_value<<endl;
break;
}
}//for
return 0;
}
```
# 第二章(算法分析基础) #
## 知识点 ##
### 输入规模与基本语句 ###
```
输入规模: 输入量的多少。
基本语句: 执行次数与整个算法的执行次数成正比的语句。
非递归算法分析的一般步骤:
1、确定文题的输入规模。
2、找出算法中基本语句。
3、检查基本语句的执行次数是否只依赖与输入规模。
4、建立基本语句执行次数的求和表达式。
5、用渐进符号表示这个求和表达式。
```
# 第三章（蛮力法） #
## 知识点 ##
```
蛮力法是一
种简单而直接地解决问题的方法,常常直接基于问题的描述,所以,
蛮力法也是最容易应用的方法。例如,对于给定的整数 a 和非负
整数 n, 计算 a^n的值,最直接最简单的想法就是把 1 和 a相
乘 n 次,即:a^n = a× a× ... × a n次
```
## 选择排序 ##
### 动态演示 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif">
### 伪代码 ###
```
// 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
// 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已
// 排序序列的末尾。以此类推，直到所有元素均排序完毕。
// -------------------------------------------------------------
function selection_sort(array, length) {
var i, j, min, temp;
for (i from 0 to length-1) {
min = i;
for (j from i+1 to length)
if (array[min] > array[j]) min = j;
temp = arr[min];
array[min] = array[i];
array[i] = temp;
}
}
// -------------------------------------------------------------
// 分类 排序算法
// 数据结构 数组
// 最差时间复杂度 О(n²)
// 最优时间复杂度 О(n²)
// 平均时间复杂度 О(n²)
// 最差空间复杂度
```
## 起泡排序 ##
### 动态演示 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/3/37/Bubble_sort_animation.gif" >
### 伪代码 ###
```
// 两两比较相邻记录，如果反序则交换。
// --------------------------------------------------------------
function bubble_sort (array, length) {
var i, j;
for(i from 0 to length-1){
for(j from 0 to length-1-i){
if (array[j] > array[j+1])
swap(array[j], array[j+1])
}
}
}
// --------------------------------------------------------------
// 分类 排序算法
// 数据结构 数组
// 最差时间复杂度 O(n^2)
// 最优时间复杂度 O(n)
// 平均时间复杂度 O(n^2)
// 最差空间复杂度 总共O(n)，需要辅助空间O(1)
```
# 第四章(分治法) #
## 知识点 ##
```
基本思想：
1、将一个难以解决的大问题划分成一些规模较小的子问题。
2、分别求解子问题
3、合并
```
## 归并排序 ##
### 动态演示 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif">
### 伪代码 ###
```
// 归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
// --------------------------------------------------------------
int min(int x, int y) {
return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int*));
int seg, start;
for (seg = 1; seg < len; seg += seg) {
for (start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}
// --------------------------------------------------------------
// 分类 排序算法
// 数据结构 数组
// 最差时间复杂度 \Theta(n\log n)
// 最优时间复杂度 \Theta(n)
// 平均时间复杂度 \Theta(n\log n)
// 最差空间复杂度 \Theta(n)
```
## 快速排序 ##
### 动态演示 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif">
### 伪代码 ###
```
// 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
// 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
// --------------------------------------------------------------
function quicksort(q)
var list less, pivotList, greater
if length(q) ≤ 1 {
return q
} else {
select a pivot value pivot from q
for each x in q except the pivot element
if x < pivot then add x to less
if x ≥ pivot then add x to greater
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
// --------------------------------------------------------------
// 分类 排序算法
// 数据结构 不定
// 最差时间复杂度 \Theta(n^2)
// 最优时间复杂度 \Theta(n\log n)
// 平均时间复杂度 \Theta(n\log n)
// 最差空间复杂度 根据实现的方式不同而不同
```
# 第五章(减治法) #
## 知识点 ##
```
减 治 法 ( reduce and conquer method)同样是把一个大问题划分为若
干个子问题,但是这些子问题不需要分别求解,只需求解其中的一个子问
题, 因而也无需对子问题的解进行合并。
(1) 原问题的解只存在于其中一个较小规模的子问题中;
(2) 原问题的解与其中一个较小规模的解之间存在某种对应关系。
```
## 插入排序 ##
### 动态演示 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Insertion-sort-example-300px.gif/220px-Insertion-sort-example-300px.gif">
### 伪代码 ###
```
void insertion_sort(int arr[], int len) {
int i, j;
int temp;
for (i = 1; i < len; i++) {
temp = arr[i]; //与已排序的数逐一比较，大於temp時，該數向後移
//j循环到-1时，由于[[短路求值]](http://zh.wikipedia.org/wiki/短路求值)，不会运算array[-1]
for (j = i - 1; j >= 0 && arr[j] > temp; j--)
arr[j + 1] = arr[j];
arr[j+1] = temp; //被排序数放到正确的位置
}
}
// --------------------------------------------------------------
// 分类 排序算法
// 数据结构 数组
// 最差时间复杂度 O(n^2)
// 最优时间复杂度 O(n)
// 平均时间复杂度 O(n^2)
// 最差空间复杂度 总共O(n) ，需要辅助空间O(1)
```
## 堆排序 ##
### 动态演示 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif">
### 伪代码 ###
```
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end) {
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son < end) { //若子節點指標在範圍內才做比較
if (son + 1 < end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else { //否則交換父子內容再繼續子節點和孫節點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
int i;
//初始化，i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len);
//先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
// --------------------------------------------------------------
// 分类 排序算法
// 数据结构 数组
// 最差时间复杂度 O(n \log n)
// 最优时间复杂度 O(n \log n)[1]
// 平均时间复杂度 \Theta(n \log n)
// 最差空间复杂度 O(n) total, O(1) auxiliary
```
# 第六章（动态规划法） #
## 知识点 ##
```
动态规划法将待求解问题分解成若干个相互重叠的子问题, 每个子问题对应决策过
程的一个阶段, 一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是
动态规划函数)中,将子问题的解求解一次并填入表中, 当需要再次求解此子问题时,可以
通过查表获得该子问题的解而不用再次求解, 从而避免了大量的重复计算。为了达到这
个目的, 可以用一个表来记录所有已解决的子问题的解, 这就是动态规划法的设计思想。
```
## 0/1 背包问题 ##
### 问题描述 ###
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/250px-Knapsack.svg.png">
背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？
### 实例 ###
动态规划函数:
<img src="img/03.png">
<img src="img/02.png">
有 5 个物品,其重量分别是{2, 2, 6, 5, 4}, 价值分别为{6, 3, 5, 4, 6}, 背包
的容量为 10, 求装入背包的物品和获得的最大价值。
<img src="img/01.png">
```
// 0/1 背包问题
int KnapSack(int n , int w[ ] , int v[ ])
{
for (i= 0; i < = n; i++ ) / / 初始化第 0 列
V[i][0] = 0;
for (j = 0; j < = C; j ++ ) / / 初始化第 0 行
V[0][j] = 0;
for (i= 1; i < = n; i++ ) / / 计算第 i 行 ,进行第 i次迭代
for (j= 1; j < = C; j ++ )
if (j< w[i] )
V[i] [j] = V[i - 1][j] ;
else
V[i] [j] = max( V[i - 1][j] , V[i - 1][j - w[i]] + v[i]) ;
j= C; / / 求装入背包的物品
for (i= n; i > 0; i - - )
{
if (V[i] [j] > V[i - 1][j]) {
x[i] = 1;
j = j - w[i] ;
}
else x[i] = 0;
}
return V[n][C]; / / 返回背包取得的最大价值
}
```
## 多段图最短路径问题 ##
<img src="img/4.png">
```
d(0,{1,2,3}) =
min
{
c01+d(1,{2,3})
c12+d(2,{1,3})
c23+d(3,{1,2})
}
------------------
d(1,(2,3) =
min
{
c12+d(2,{3})
c13+d(3,{2})
}
------------------
d(2,{3})=
min
{
c23+d(3,{})
}
------------------
d(3,{}) = c(3,0) = 3
```
<img src="img/05.png">
```
//多段图的最短路径
1 . 初始化: 数组 cost[n]初始化为最大值 ,数组 path[n]初始化为 - 1;
2 . for (i= n - 2; i> = 0; i - - )
2 .1 对顶点 i 的每一个邻接点 j, 根据式(6 .7)计算 cost[i];
2 .2 根据式(6 .8)计算 path[i];
3 . 输出最短路径长度 cost[0] ;
4 . 输出最短路径经过的顶点:
4 .1 i = 0;
4 .2 循环直到 path[i] = n - 1
4 .2 .1 输出 path[i];
4 .2 .2 i = path[i] ;
```
## TSP问题 ##
# 第七章（贪心法） #
## 知识点 ##
```
为了解决一个复杂的问题, 人们总是要把它分解为若干个类似的子问
题。
分治法是把一个复杂问题分解为若干个相互独立的子问题, 通过求解
子问题并将子问题的解合并得到原问题的解;
动态规划法是把一个复杂问题分解为若干个相互重叠的子问题,通过求
解子问题形成的一系列决策得到原问题的解;
而贪心法(greedy method)是把一个复杂问题分解为一系列较为简单的
局部最优选择, 每一步选择都是对当前解的一个扩展, 直到获得问题的
完整解。
贪心法的典型应用是求解最优化问题,而且对许多问题都能得
到整体最优解, 即使不能得到整体最优解, 通常也是最优解的很好近似。
```
## TSP问题 ##
## 背包问题 ##
# 第八章（回 溯 法） #
## 知识点 ##
```
解空间：就是进行穷举的搜索空间,所以, 解空间中应该包括所有的可能解。
```
## 图着色问题 ##
<img src="img/06.png">
```
1 . 将数组 color[n]初始化为 0;
2 . k = 1;
3 . while (k > = 1)
3 .1 依次考察每一种颜色 ,若顶点 k 的着色与其他顶点的着色不发生冲突 ,则转步骤 3 .2;
否则 ,搜索下一个颜色;
3 .2 若顶点已全部着色 , 则输出数组 color[n] , 返回;
3 .3 否则 ,
3 .3 .1 若顶点 k 是一个合法着色 ,则 k = k + 1, 转步骤 3 处理下一个顶点;
3 .3 .2 否则, 重置顶点 k 的着色情况 , k = k - 1 ,转步骤 3 回溯;
```
## 八皇后问题 ##
<img src="http://img.blog.csdn.net/20141025214359265?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGhjMTEwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
```
void Queue(int n)
{
for (i = 1; i< = n; i ++ ) // 初始化
x[i] = 0;
k = 1;
while (k > = 1)
{
x[k] = x[k] + 1; // 在下一列放置第 k 个皇后
while (x[k] < = n && !Place(k))
x[k] = x[k] + 1; // 搜索下一列
if (x[k] < = n && k = = n) // 得到一个解 ,输出
{
for (i = 1; i< = n; i ++ )
cout < < x[i] ;
return;
}
else if (x[k] < = n && k < n)
k = k + 1; // 放置下一个皇后
else
{
x[k] = 0; // 重置 x[k] , 回溯
k = k - 1;
}
}
}
bool Place(int k) // 考察皇后 k 放置在 x[k]列是否发生冲突
{
for (i = 1; i< k; i++ )
if (x[k] = = x[i] | | abs(k - i) = = abs(x[k] - x[i] )) return false;
return true;
}
```
# 第九章（分支限界法） #
## 知识点 ##
```
回溯法按深度优先策略遍历问题的解空间树, 在遍历过程中, 应用约
束条件、 目标函数等剪枝函数实行剪枝。
分支限界法 ( branch and boundmethod)按广度优先策略遍历问题的
解空间树, 在遍历过程中, 对已经处理的每一个结点根据限界函数估
算目标函数的可能取值,从中选取使目标函数取得极值(极大或极小)的
结点优先进行广度优先搜索, 从而不断调整搜索方向,尽快找到问题
的解。
因为限界函数常常是基于问题的目标函数而确定的,所以, 分支限界法
适用于求解最优化问题。
```
## 0/1 背包问题 ##
