二分搜索
/* * 输入：n个元素的升序数组A[1...n]、x * 输出：如果x=A[j]&&1<=j<=n，则输出j，否则输出0 */int Binarysearch(int *A, int x, int n) { int low = 1, high = n, j = 0; while (low <= high && j == 0) { int mid = (int) ((low + high) / 2); if (x == A[mid])j = mid; else if (x < A[mid])high = mid - 1; else low = mid + 1; } return j;}要注意二分搜索的输入一定是一个 升序的数组，实质就是一个二叉搜索树（所以也把二分搜索的执行描述为决策树），对于一个大小为n的排序数组，算法Binarysearch执行比较的最大次数为$（）int（log_n）+1$（如果输入数组不是递增排好序的，则可在$nlog_n$内对其进行排序后再进行二分搜索）。
合并两个已排序的表
选择排序
/* * 输入：n个元素的数组A[1...n] * 输出：按非降序排列的数组A[1...n] */void SelectionSort(int *A, int n) { for (int i = 0; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { if (A[i] > A[j]) { int t = A[i]; A[i] = A[i]; A[i] = t; } } }}算法SelectionSort所需的元素比较次数为$\frac{n(n-1)}{2}$ ，（因为$n-1+n-2+n-3+…+2+1=\frac{n(n-1)}{2}$），因为每次交换需要3次赋值，所以元素的赋值次数介于0到3(n-1)之间。
插入排序
首先将第二个数与第一个数进行对比，如果第二个数比第一个数小，则将第二个数插入到第一个数之前，这样保证前两个数是有序的； 接下来将第三个数与前两个数对比，比较的思路是先将第三个数存下来（记为x），然后将第三个数与第二个数比较，如果第二个数比第三个数大，则直接将第二个数向后移动一位，如果第二个数不比第三个数大，则说明此时前三个数都是有序的，因为之前前两个数是有序的，比较到最后，将x放到第三个数比较的终止位置即可。以此类推，将后面的i个数分别其前面的i-1个数进行对比，并将其插入到第一个比其大的数前面，最后即可完成排序。
执行算法SelectionSort的元素比较次数在$n-1$到$\frac{n(n-1)}{2}$之间，元素赋值次数等于元素比较次数加上n-1.
自底向上合并排序
/* * 输入：n个元素的数组A[1...n] * 输出：按非降序排列的数组A[1...n] */void Merge(int *A, int p, int q, int r);void BottomUpSort(int *A, int n) { int t = 1; while (t < n) { int s = t, t = 2 * s, i = 0; while (i + t <= n) { Merge(A, i + 1, i + s, i + t); i = i + t; } if (i + s < n) { Merge(A, i + 1, i + s, n); } }}用算法BottomUpSort对n个元素的数组进行排序，当n为2的幂时，元素比较次数在$\frac{nlog_n}{2}$到$nlog_n-n+1$之间。执行该算法的元素赋值次数为$2nlogn$。
时间复杂性
前文提到算法InsertionSort执行的运算次数至多为$o(n^2)$， 其中c为某个适当选择的正常数。这时我们说算法InsertionSort的运行时间是$c(n^2)$，说明当排序元素的个数等于或超过某个阈值n0时，对于某个常量c，运行时间是$cn^2$，O符号描述的是一个上界但不一定是算法的实际执行时间，比如当排序一个已经排序好的数组时InsertionSort的运行时间就不是$O(n^2)$而是O(n)了。
相比于O，Ω描述的是算法执行的 下界，比如算法InsertionSort的运算时间至少是cn，则称算法InsertionSort的运行时间是Ω（n），即无论何时，当被排序的元素个数等于或超过某一个阈值n0时，对于某个常数c，算法的运行时间至少是cn。
theta描述的是一个确切界限，如果对于任意大小等于或超过某一阈值n0的输入，如果运行时间在c1g(n)和c2g(n)之间，则称算法的运行时间是$\theta(g(n))$。
o符号
O 符号给出的上界可以是“紧”的,也可以是非“紧”的。
$2n^ 2 =O ( n^ 2 ) $是渐近性紧边界
$2n = O ( n^ 2 ) $不是渐近性紧边界
o 符号就用来表示 不是渐近性紧边界 的上界
举例:$ 2 n = o ( n ) $, $！2 ^n ！= o ( n )$
直观上来说,在小 o 符号中,$ f ( n ) =o ( g ( n )) $,当 n 趋向于无穷大时, f (n ) 函数相当于 g (n )就变得不再重要了
即$\lim \limits _{n\to +\infty} \frac{f(n)}{g(n)}=0$
w符号
用类比法来讲,小 w符号相对于大 Ω符号的关系正如 o 符号相对于 O 符号的关系。
我们用小 w 符号来表示一个 渐近性非紧密的下界 。
比如：
$n^2/2=w(n )$
$\frac{n^2}{2}!=w(n^2)$
$\lim \limits_{+ \infty}\frac{f(n)}{g(n)}=\infty$
空间复杂性
我们把算法使用的空间 定义 、为:为了求解问题的实例而执行的计算步骤所需要的内存空间,它
不包括分配用来存储输入的空间（为了区分那些在整个计算过程中占用了少于输入空间的算法） 。
算法的 空间复杂性不可能超过运行时间的复杂性 ,因为每写入一个内存单元都至少需要一定的时间。所以,如果用 T (n ) 和 S (n )分别代表算法的时间复杂性和空 间复杂性,有: S ( n ) = O ( T ( n )) 。
最优算法
如果可以证明任何一个求解问题 T的算法必定是Ω ( f ( n )) ,那么我们把在 O ( f ( n )) 时间内求解问题T的任何算法都称为问题T的最优算法。
一般来说,在分析一个算法运行时间时,可以找出这样一个元运算,它的频率至少和任何其他运算的频度一样大,称这样的运算为基本运算。我们还可以放宽这个定义,把那些频度和运行时间成正比的运算包括进来。
如果一个算法本身是递归算法,那么计算这个算法运行时间的函数通常也是递归的,即是指,这个函数的定义中引用了函数自身。即便一个算法本身是非递归的,我们有时也可以用递归式来计算它的运行时间。
$\lim \limits{n \to \infty }\frac{f(n)}{g(n)}!=\infty, f(n)=O(g(n)) $
$\lim \limits {n \to +\infty}\frac{f(n)}{g(n)}!=0, f(n)=Ω(g(n)) $
$\lim \limits _{n \to +\infty }\frac{f(n)}{g(n)}=c, f(n)=\theta(g(n))$
在很多情况下我们需要使用一种具有 插入元素 和 查找最大值元素 的数据结构，这种数据结构叫做 优先队列
，如果采用普通队列，那么寻找最大元素需要搜索整个队列，开销比较大；如果使用排序数组，插入运算就需要移动很多的元素，开销也会比较大。这时候 堆就是一种 有效的实现优先队列的数据结构 。
堆的特点：
堆需要支持的几种运算：
堆上的运算
SIFT-UP
功能
当某个节点（H[i]）的值大于他的父亲节点的值时，需要通过SITF-UP将这个节点 沿着从H[i]到H[1]这条唯一的路径上移到合适的位置以形成一个合格的堆。
实现思路
将H[i]与其父亲节点H[i/2]比较，如果H[i]大于H[i/2]，则将H[i]与H[i/2]互换，直到H[i]没有父节点或者H[i]不大于H[i/2]。
代码
int SiftUp(int *H, int i) { while (true) { if (i == 1) { break;//说明当前i是根节点 } if (H[i] > H[(int) i / 2]) {//如果当前节点比父亲节点大 int t; t = H[i]; H[i] = H[(int) i / 2]; H[(int) i / 2] = t; i = i / 2; } else { break; } } return 0;}SIFT-DOWN
功能
当某个节点（H[i]，i<=(int)n/2即 非叶子节点）的值小于它的两个子节点H[2i]和H[2i+1]（如果存在的话）的最大值时，需要将SIFT-DOWN将渗到合适的位置。
实现思路
将H[i]与其两个子节点中值最大的元素比较，如果小于最大的那个节点，则将H[i]与其最大的那个子节点互换。
代码：
功能
将元素x插入到已有的堆H中
实现思路
首先将堆的大小增加1（n++），然后将x放在H[n]中，然后根据需要将H[n]中的元素x进行上移操作，直到最后形成一个合格的堆。
算法时间复杂度分析
一个大小为n的二叉堆其高度应该为（int）logn，所以将一个元素插入大小为n的堆中所需的时间复杂度为 O（logn）
代码
void insert(int *H,int x,int &n){ n++; //这里默认H开的空间够用 H[n]=x; SiftUp(H, n);//将x根据需要上移}功能
将堆H中的元素x删除
实现思路
用堆中的最后一个元素H[n]替换需要删除的元素H[i]，然后堆的大小减一（n–），然后根据需要对H[i]进行上移或者下渗直到最后形成一个合格的堆。
算法时间复杂度分析
一个大小为n的二叉堆其高度应该为（int）logn，所以从一个大小为n的堆中将一个元素删除所需的时间复杂度为 O（logn）
代码
功能
将堆H中的最大元素x删除并返回最大值。
实现思路
用堆中的最后一个元素H[n]替换需要删除的元素H[1]，然后堆的大小减一（n–），然后根据需要对H[1]进行上移或者下渗直到最后形成一个合格的堆。
算法时间复杂度分析
一个大小为n的二叉堆其高度应该为（int）logn，所以从一个大小为n的堆中将一个元素删除所需的时间复杂度为 O（logn）
代码
int DeleteMax(int *H,int &n){ int x=H[1]; Delete(H, 1, n); return x;}功能
给出一个有n个元素的数组H[1….n]，创建一个包含这些元素的堆。
实现思路
类似于分治，首先，H的叶子节点（即最下面的一层单个元素）可以认为是若干个小堆，然后我们从倒数第二层开始，将倒数第二层和倒数第一层的元素进行适当调整，使得调整之后整个二叉完全树的最后两层是若干个子堆，按照这个思路，依次向上走，最终走到第1层的时候就可以保证整个完全二叉树是一个符合要求的堆。
需要注意的是对于一个完全二叉树， 倒数第二层的最后一个元素的下标为int(n/2) ，（因为倒数第二层的最后一个节点的下标x应该满足x*2=n）.
算法时间复杂度分析
$\theta (n)$
代码
功能
利用堆对数组H[n]进行排序。
实现思路
首先将数组H[n]调整成为一个（大顶）堆，这时可以保证H[1]是数组中的最大元素，然后将H[1]与H[n]互换位置，然后再调整1——n-1为一个大顶堆，然后将H[1]与H[n-1]互换，以此类推，最后就可以保证H为一个非升序的数组。
算法复杂度分析
空间复杂度：因为本算法是在数组H原有的空间基础上进行排序的，所以空间复杂度是theta（1）。
时间复杂度：
代码
void HeapSort(int *H,int n){ makeheap(H,n); int t; for (int i = n; i >=2 ; --i) { t=H[i]; H[i]=H[1]; H[1]=t; SiftDown(H,1,i-1); }}只调用一次的递归叫做尾递归
基数排序
基数排序需要经历d次，d为所要排序数列中位数最多的数的位数，其过程是首先根据数列中数的个位的数值将所有数入0-9这10个队列，然后从0~9将元素依次出队，然后再根据十位元素的数值再次入队，然后出队，以此类推重复d次，最终即可完成排序。
对于任何的基数都可以归纳出算法，而不仅仅是以10做基数。比如可以把二进制的每四位作为一个数字，也就是用16作为基数，表的数目将和基数相等但是要保证从低位开始将数分配到表中。
整数幂
很多时候我们需要求实数x的n次方即$x^n$，按照常规做法一般会对x进行n次自乘以得到x^n，但是这是非常低效的，因为它需要$（）\theta（n）$次乘法，按照输入的大小来说它是指数级的。
一个比较高效的归纳算法是令m=int(n/2)，假设已经知道如何计算$x^m$,那么根据$x^m$次方来计算x^n次方就有两种情况：
int power(int x,int n){ if (n==0){ return 1; } int m=n/2; int y; y=power(x,n/2); y=y*y; if (n%2!=0){//如果n是奇数 y=y*x; } return y;}上述归纳法实现求$x^n$的关键部分在于采用递归不断判断n/2的奇偶性，所以我们可以采用迭代的办法，因为一个数除以2的k次方后的奇偶性由其化为二进制数的第k低位决定的（因为除法除以2就相当于二进制的左移操作），所以我们可以将n化为二进制数字dk,d(k-1)……d_0，从y=1开始，从左到右扫描二进制数字，如果当前二进制数字为0，则对应递归情况下的偶数情况即应该$y=y^2$，否则即为$y=y(y^m)^2$
假设每次乘法的时间是常数，那么这两种方法所需的运行时间都是 $\theta(log_n)$，他们对于输入大小来说都是 线性 的。
多项式求值（Horner规则）
假设有n+2个数a0,a_1,……,a_n和x序列，要对多项式 *P_n(x)=a_nx^n+a(n-1)x^(n-1)+…+a_1x**
求值，传统的办法是分别对每一个子项求值，然后再对整个式子求值，但是这种方法很低效，因为它需要n+（n-1）+（n-2）+…..+1=n(n+1)/2次乘法。
首先我们发现原式可进行如下化简（这么丑的字不是我写的…）：
3
int Horner(int *A,int n,int x){//数组A的长度为n+2，从A[0]到A[n+1]代表了a_0到a_(n+1) int p=A[n+1];//p=a_(n+1) for (int i = 1; i <=n ; ++i) { p=p*x+A[n+1-i];//p=p*x+a_(n-i) }}寻找多数元素
令A[1…n]是一个整数序列，如果该序列中的某一个数x在该序列中出现的次数多余int(n/2)，则称x为该序列的 多数元素 。
什么是分治
一个分治算法把问题实例划分为若干个子问题（一般是两个），并分别使用递归解决每个子实例，然后把这些子实例的解组合起来，得到原问题的解。
考虑这样一个问题：我们需要在序列Ａ[1….n]中找到该序列的最大值元素和最小值元素，一种直接的算法是扫描一遍Ａ序列，用两个标志位max和min分别表示最大值和最小值元素，然后扫描时根据每个元素与当前最大最小值的比较情况动态调整最大最小值直至最后找到最大最小值，代码如下：
void MaxMin(int *A,int n){ int max,min; min=max=A[0]; for (int i = 1; i <n ; ++i) { if(A[i]>max)max=A[i]; if(A[i]<min)min=A[i]; } cout<<max<<min<<endl;}显然，此种方法的元素比较次数是２ｎ－２，但是利用分治策略就可以将元素比较次数减少到(３ｎ)/2-2，具体做法：将数组分割成两半，Ａ[1…n/2]和Ａ[n/2+1…n]，在每一半中分别找到最大值和最小值，并返回这两个最小值中的最小值、这两个最大值中的最大值作为最终的最小、最大值。对应伪代码如下：
按照上述算法，设Ａ[1…n]有ｎ个元素，ｎ为２的幂，则仅用３ｎ/2-2次元素比较就可以在数组Ａ中找出最大值和最小值。
二分搜索
原理比较简单，给出代码：
int binarysearch(int *A, int low, int high, int x) {//A是已经排序过的数组,A[1....n] if (low > high)return 0; int mid = (high + low) / 2; if (x == A[mid])return mid; if (x < A[mid])return binarysearch(A, low, mid, x - 1); else return binarysearch(A, mid + 1, high, x);}算法BINARYSEARCHREC在ｎ个元素组成的数组中搜索某个元素所执行的比较次数不超过$((int)log_n)+1$，时间复杂度是Ｏ(logn)。
递归和迭代实现二分搜索算法的元素比较次数都在int(logn)+１内，但是迭代算法只需要theta(１)的空间，而递归算法由于递归深度为Ｏ(logn)，每个递归层次需要$\theta(1)$的空间，所以总的需要的空间总量是Ｏ(logn)。
归并（合并）排序
这里需要区分迭代式合并排序和递归式合并排序的区别(自行查阅资料)
主要思路是将所要排序数列看做若干个有序的小数列，因为将两个有序数列合并之后所得数列还是有序数列，所以经过不断合并，最后可将数列排为有序。
时间空间复杂度及稳定性
代码
void MSort(vector<int> v) { vector<int> h; h = v; int start, seg; for (seg = 1; seg < v.size(); seg *= 2) { int k = 0; for (start = 0; start < v.size(); start = start + seg * 2) { int end; end = start + seg; int low = start; while (low < start + seg && end < start + seg + seg && low < v.size() && end < v.size()) { if (v[low] <= v[end]) { h[k++] = v[low]; low++; } else { h[k++] = v[end]; end++; } } while (low < start + seg && low < v.size()) { h[k++] = v[low++]; } while (end < start + seg + seg && end < v.size()) { h[k++] = v[end++]; } } v = h; } show(v);}主要思路是将待排序序列分成两个小部分，然后再对两个小部分运行相同的排序方法进行递归排序，最后将两个小部分合并起来。
MergeSort（A,1,n）;
算法MergeSort对一个n个元素的数组排序所需的时间是$\theta(nlogn)$，空间是$\theta(n)$.
寻找中项和第k小元素
寻找序列A[1…n]中的第k小元素。
传统的方法是直接将A[1…n]进行排序，然后取排序后的序列的第k个即为第k小元素，但是这种方法需要Ω(nlogn)的时间，因为任何基于比较的排序过程在最坏情况下必须花费这么多时间，所以我们选择一种新的算法：
我们要在n个元素中找到第k小元素的实质是寻找第k小元素在A中的位置，所以我们可以将A划分成三个子序列A1 A2A3，其中A2为单个元素的序列，A1中的所有元素小于A2，A3中的所有元素大于A2，此时就有以下几种情况：
这样，我们就可以采用分治的思想将原来的n个元素中寻找第k小元素不断缩小范围最终找到目标元素，具体算法步骤描述如下：
SELECT 算法描述
* A1={小于 mm 的元素}; * A2={等于 mm 的元素}; * A3={大于 mm 的元素}; 6. 根据 k 的大小,判断第 k 小元素会出现在 A1,A2,A3 中的哪一个数组里,之后,或者返回第 k 小元素(mm,在 A2 中),或者在 A1 或 A3 上递归。在一个由n个元素组成的线序集合中提取第k小元素，所需的时间是$\theta(n)(T(n)<=20cn$,c是排序43个元素所需的时间)，特别地，n个元素元素的中值可以在$\theta(n)$时间找出。
需要注意的是，虽然此算法所需的时间是$\theta(n)$但是其中的倍数常量（20c）还是太大，我们会在随讲机算法的时候提出一个具有较小倍数常量的算法。
快速排序（QuickSort）
快速排序（QuickSort）是一种具有$\theta(nlogn)$时间复杂度的排序算法，相比MergeSort，QuickSort不需要辅助的存储空间，这是它的优势。
在进行快速排序算法的实现之前我们需要先实现划分算法，它是快速排序算法的基础。
什么是划分算法
设A[low…high]是一个包含n个数的序列，设x=a[low],我们希望对A中的元素进行位置调整后实现当i< new index of x时A[i]<x,当i> new index of x时A[i]>x。
实现思路
对一个指定序列A[low…high]，从A[low+1]开始向后扫描元素，如果当前元素a<=A[low]，则将a与第A[i]的元素互换位置，其中i是从low开始的，每进行一次元素的互换之前i++，最后，当A中元素扫描完毕时所有小于等于A[low]的元素都在i之前的位置（包括A[i]），所以此时只需将A[low]和A[i]的元素互换位置即可满足划分的定义，此时的i对应的就是元素A[low]的新位置.
代码实现
int Split(int *A, int low, int high) {//输入一个序列，返回A[low]对应元素的新位置 int i = low; int x = A[low]; for (int j = low + 1; j <= high; ++j) { if (A[j] <= x) { i++; if (i != j) { int t = A[i]; A[i] = A[j]; A[j] = t; } } } int t; t = A[low]; A[low] = A[i]; A[i] = t; return i;}复杂度分析
因为算法split的元素比较次数恰好是n-1，所以它的时间复杂性为$\theta(n)$.
算法思想
算法QuickSort的主要思路是利用Split算法将A[low…high]中的A[low]排列到其正确的位置A[w]，然后对子数组A[low…w-1]和子数组A[w+1…high]递归地进行排序从而产生整个排序数组。
代码实现
复杂度分析
算法QuickSort对n个元素的数组进行排序时执行的平均比较次数是$\theta(nlogn)$
什么是动态规划
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。动态规划是一种被广泛用于求解组合最优化问题的算法。
算法思想与分治法类似，也是 将待求解的问题分解为若干个子问题 （阶段），按顺序求解子阶段，
前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法的差别
适合于用动态规划法求解的问题，经分解后得到的子问题往往 不是互相独立 的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
适用的情况
能采用动态规划求解的问题的一般要具有3个性质：
最长公共子序列问题
给定两个长度为n和m的字符串A和B，确定A和B中最长公共子序列的长度。
输入A和B字符串，返回二者的最长子序列长度
int Lcs(char *A, int n, char *B, int m) {//A[0...n] B[0...m] int L[n + 1][m + 1]; for (int i = 0; i <= n; ++i) { L[i][0] = 0; } for (int j = 0; j <= m; ++j) { L[0][j] = 0; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= m; ++i) { if (A[k] == B[i])L[k][i] = L[k - 1][i - 1] + 1; else L[k][i] = L[k][i - 1] > L[k - 1][i] ? L[k][i - 1] : L[k - 1][i]; } } return L[n][m];}注意，以上算法需要的空间复杂度是$\theta(mn)$，但是因为计算表中每一项的计算仅仅需要其上一行和上一列的元素，所以对算法进行改进可以使得空间复杂度降为$\theta(min(m,n))$（准确来说是需要2min(m,n)的空间，仅仅将前一行和当前行存储下来即可）。
最长公共子序列问题的最优解能够在$\theta(mn)$时间和$\theta(min(m,n))$空间内计算得到。
矩阵链相乘
给定一个n个矩阵的序列⟨A1,A2,A3…An⟩,我们要计算他们的乘积：A1A2A3…AnA1A2A3…An，由于矩阵乘法满足结合律，加括号不会影响结果，但是不同的加括号方法，算法复杂度有很大的差别：
考虑矩阵链⟨A1,A2,A3⟩，三个矩阵规模分别为10×100、100×5、5×50：
以上两种不同的加括号方式具有10倍的差别，可见一个好的加括号方式，对计算效率有很大影响。
使用一个长度为n+1的一维数组p来记录每个矩阵的规模，其中n为矩阵下标，i的范围1~n，例如对于矩阵Ai而言，它的规模应该是p[i-1]×p[i]。由于i是从1到n取值，所以数组p的下标是从0到n。
用于存储最少乘法执行次数和最佳分段方式的结构是两个二维数组m和s，都是从1~n取值。$m[i][j]$记录矩阵链< Ai,Ai+1,…,Aj>的最少乘法执行次数 ，而s[i][j]则记录 最优质m[i][j]的分割点k。
需要注意的一点是当i=j时，$m[i][j]=m[i][i]=0$，因为一个矩阵不需要任何乘法。
假设矩阵链从Ai到Aj，有j-i+1个矩阵，我们从k处分开，将矩阵链分为Ai~Ak和Ak+1到Aj两块，那么我们可以比较容易的给出$m[i$][j]从k处分隔的公式：
在一组确定的i和j值的情况下，要使m[i][j]的值最小，我们只要在所有的k取值中（i <=k< j)，寻找一个让m[i][j]最小的值即可。
假设L为矩阵链的长度，那么L=j-i+1。当L=1时，只有一个矩阵，不需要计算。那么我们可以从L=2到n进行循环，对每个合理的i和j值的组合，遍历所有k值对应的$m[i][j]$值，将最小的一个记录下来，存储到$m[i$][j]中，并将对应的k存储到$s[i$][j]中，就得到了我们想要的结果。
/* * 输入：ms[1...n+1],ms[i]表示第i个矩阵的行数，ms[i+1]表示第i个矩阵的列数 * 输出：n个矩阵的数量乘法的最小次数 */int dp[1024][1024] = { 0 };struct Matrix { int row; int column;};int matrixChainCost(Matrix *ms, int n) { for (int scale = 2; scale <= n; scale++) { for (int i = 0; i <= n - scale; i++) { int j = i + scale - 1; dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k+1][j] + (ms[i].row*ms[k].column*ms[j].column)); } } } return dp[0][n - 1];}所有点对的最短路径问题
设G是一个有向图，其中每条边(i, j)都有一个非负的长度L[i, j]，若点i 到点j 没有边相连，则设L[i, j] = ∞.
找出每个顶点到其他所有顶点的最短路径所对应的长度。
例如：
4
则 L： 0 2 9
8 0 6
1 ∞ 0
Floyd算法（所有点对最短路径）就是每对可以联通的顶点之间总存在一个借助于其他顶点作为媒介而达到路径最短的最短路径值（这个值通过不断增添的媒介顶点而得到更新，也可能不更新——通过媒介的路径并不比其原路径更短），所有的值存储于邻接矩阵中，这是典型的动态规划思想。
值得注意的是，Floyd算法本次的状态的获取 只用到了上个阶段的状态 ，而没有用到其他阶段的状态，这就为 压缩空间 奠定了条件。
Floyd算法能够成功的关键之一就是D0(初始矩阵，即权重矩阵)的初始化，凡是不相连接的边必须其dij必须等于正无穷且dii=0(矩阵对角线上的元素！)
算法的运行时间是$\theta(n^3) $
算法的空间复杂性是$\theta(n^2)$
背包问题
设U={u1,u2,u3…un}是一个准备放入容量为C的背包中的n项物品的集合。我们要做的是从U中拿出若干物品装入背包C，要求这些物品的总体积不超过C，但是要求装入背包的物品总价值最大。
有 n 种物品，物品 i 的体积为 v[i], 价值为 p[i]. 假定所有物品的体积和价格都大于 0, 以及背包的体积为 V.
$mp[x$][y] 表示体积不超过 y 且可选前 x 种物品的情况下的最大总价值
那么原问题可表示为$ mp[n][V]$。
递归关系：
递归式解释$mp[0][y] = 0$表示体积不超过 y 且可选前 0 种物品的情况下的最大总价值，没有物品可选，所以总价值为 0$mp[x][0] = 0$表示体积不超过 0 且可选前 x 种物品的情况下的最大总价值，没有物品可选，所以总价值为 0当 v[x] > y 时，$mp[x][y] = mp[x-1][y]$因为 x 这件物品的体积已经超过所能允许的最大体积了，所以肯定不能放这件物品，那么只能在前 x-1 件物品里选了当 v[x] <= y 时，$mp[x][y]$ = $max{ mp[x-1][y] , p[x] +mp[x-1][y-v[x]]$（选中A，则其余y-v[x]应在前x-1件物品中选） }x这件物品可能放入背包也可能不放入背包，所以取前两者的最大值就好了， 这样就将前两种情况都包括进来了
/* * 输入：物品集合U={u1,u2,u3...un}，体积为s1,s2,s3...sn，价值为v1,v2,v3...vn，容量为C的背包 * 输出：满足条件的最大价值 * */int Knapsack(int *s,int *v,int C,int n){ int V[n+1][C+1];//V[i][j]表示从前i项找出的装入体积为j背包的最大值 for (int i = 0; i <=n ; ++i) { V[i][0]=0; } for (int j = 0; j <=C ; ++j) { V[0][j]=0; } for (int k = 1; k <=n ; ++k) { for (int i = 1; i <=C ; ++i) { if(s[k]<=i){ V[k][i]=max(V[k-1][i],V[k-1][i-s[k]]+v[k]); } } } return V[n][C];}背包问题的最优解可以在$\theta(nC)$时间内和$\theta(C)$空间内解得。
注意，上述算法的时间复杂性对输入不是多项式的，但是它的运行时间关于输入值是多项式的（时间复杂性+其他耗费时间），故认为它是伪多项式时间算法。
引言
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说， 不从整体最优上加以考虑 ，他所做出的仅是在某种意义上的局部最优解 。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备 无后效性，即 某个状态以后的过程不会影响以前的状态，只与当前状态有关 。 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
最短路径问题
给定一个有向图G=(V,E),s为V中一点,以s为起点,要确定从s出发到V中每一个其他顶点的距离(距离的定义是最短路径对应的长度).
算法步骤
代码
算法复杂度
算法的时间复杂度是theta(n^2)
稠(臭)图不想看，也许不考…
最小耗费生成树
设G =(V,E)是无向连通带权图，即一个网络。E中的每一条边（v,w）的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。
最小生成树最常见的题就是求解n个城市之间的修路方案问题.
Kruskal算法
算法描述
给定无向连通带权图G = (V,E),V = {1,2,…,n}。Kruskal算法构造G的最小生成树的基本思想是：
此时，已构成G的一棵最小生成树。
代码实现
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define maxn 110 //最多点个数int n, m; //点个数，边数int parent[maxn]; //父亲节点，当值为-1时表示根节点int ans; //存放最小生成树权值struct eage //边的结构体，u、v为两端点，w为边权值{ int u, v, w;}EG[5010];bool cmp(eage a, eage b) //排序调用{ return a.w < b.w;}int Find(int x) //寻找根节点，判断是否在同一棵树中的依据{ if(parent[x] == -1) return x; return Find(parent[x]);}void Kruskal() //Kruskal算法，parent能够还原一棵生成树，或者森林{ memset(parent, -1, sizeof(parent)); sort(EG+1, EG+m+1, cmp); //按权值将边从小到大排序 ans = 0; for(int i = 1; i <= m; i++) //按权值从小到大选择边 { int t1 = Find(EG[i].u), t2 = Find(EG[i].v); if(t1 != t2) //若不在同一棵树种则选择该边，合并两棵树 { ans += EG[i].w; parent[t1] = t2; } }}复杂度分析
当图的边数为e时，Kruskal算法所需的时间是O(eloge).
算法描述
设G = (V,E)是连通带权图，V = {1,2,…,n}。构造G的最小生成树,Prim算法的基本思想是：首先置S =
{1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i ∈S,j ∈V –S,且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
代码实现
复杂度分析
此算法的时间复杂度为O(n^2)
（这个写的我也看不懂了…应该是当时笔误，具体想表达什么意思猜猜吧）
当e = Ω(n^2)时，Kruskal算法比Prim算法差；
但当e = o(n^2)时，Kruskal算法比Prim算法好得多。
如果一个算法的最差时间效率属于 O ( p ( n )) ,其中 p (n ) 是问题输入规模 n 的一个多项式函数,我们说该算法能
够在多项式的时间内对问题求解 。
我们把可以在多项式时间内求解的问题称为 易解的 ,而不能在多项式时间内求解的问题则称为 难解的 。
P和NP问题
非正式地说，我们可以把那些 能够在多项式时间内求解 的问题当作计算机科学家所说的 P 集合 。
正式点，只有那些 能够回答是或否 的问题（又称判定问题）才属于 P。
P 类问题是一类能够用 确定性算法在多项式时间内求解 的 判定问题 。
这种问题类型也称为 多项式类型 。
绝大多数判定问题的一个公共特性是:
虽然在计算上对问题求解可能是困难的,但在计算上 判定一个待定解是否解决了该问题 却是简单的,并且,这种判定可以在多项式时间内完成。
一个不确定算法是一个两阶段的过程,它把一个判定问题的实例 l 作为它的输入,并进行下面的操作:
生成一个任意串 S,把它当作给定实例 l 的一个候选解,但 S也可能是完全不着边际的。
如果一个不确定算法在验证阶段的时间效率是多项式级的,我们说它是 不确定多项式类型 的算法。 NP 类问题(Non-deterministic Polynomial)是一类可以用不确定多项式算法求解的判定问题。我们把这种问题类型称为不确定多项式类。 我们说一个判定问题 D 1可以多项式地化简为一个判定问题 D 2 ,条件是存在一个函数 t 能够把 D 1 的实例转化为D 2 的实例,使得:
我们说一个判定问题 D 是 NP 完全问题,条件是:
NP 完全问题:
合取范式的可满足性问题
哈密顿回路问题
旅行商问题
NP 完全问题的定义意味着,如果我们得到了一个 NP 完全问题的多项式确定算法,就说明所有的 NP 问题都能够用一个确定算法在多项式的时间内解出,因此,P= NP.换句话说,得到了一个 NP完全问题的多项式确定性算法可以表明,对于所有类型的判定问题来说,检验待定解和在多项式时间内求解在复杂性上没有本质的差别。
这种推论使得大多数计算机科学家相信 P ≠ NP但是,到目前为止,还没有人能从数学上证明这一猜想。
概述
回溯算法是一种组织搜索的一般技术，它常常可以避免搜索所有的可能性，适用于求解那些有潜在的大量解但是有限个数的解已经检查过的问题。
3着色问题
给出一个无向图G=(V,E)，需要用三种颜色之一为V中的每个顶点着色，要求没有两个相邻的顶点有相同的颜色。
我们称没有两个邻接顶点有同样颜色的着色方案为合法的，反之成为非法的。如果不考虑合法性的要求，给出n个顶点的无向图，将其用三种颜色着色，共有n^3种不同的方法，因为每一个顶点都有三种不同的着色方案，这就构成了一颗三叉树，如图：
5
使用数组c[1…n]代表图的顶点集合，判断合法性只需判断与当前有联系的点中是否存在与之涂色相同的点即可，此处为节省时间省略该部分代码的实现。
迭代法
void ColorItre(int *c) {//c[1...n] for (int i = 1; i <= n; ++i) { c[i] = 0; } bool flag = false; int k = 1; while (k >= 1) { while (c[k] <= 2) {//从0-2对应三种涂色（实际上是 下面加一之后的1-3对应三种不同颜色） c[k] = c[k] + 1; if (c[k]为合法的){ if (k == n) {//如果k已经是最后一个点 flag = true; break; } else { k++; } } } if (flag) { break; } //如果第二个循环跳出执行到这里，则说明当前节点k试遍了三种颜色仍然没有找到合法的着色，则将k--进行回溯，注意要将c[k]置为初始值0 c[k] = 0; k--; } if (flag) { cout << 'success' << endl; } else { cout << 'no solution' << endl; }}递归法
这两种实现方式在最坏情况下生成了$O(3^n)$个节点，对于每个生成的节点，判断当前节点的合法性（合法、部分、二者都不是）需要O(n)的工作来检查，因此，最坏情况下的运行时间是$O(n3^n)$。
8皇后问题
代码见 两种不同方式解决八皇后问题，此处主要介绍算法思路。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1 或 n ≥ 4 时问题有解。
代码和着色问题代码几乎一样，这里不做过多介绍，给出参考代码：
void eight_Queens() { int c[9]; for (int i = 1; i <= 8; ++i) { c[i] = 0; } bool flag = false; int k = 1; while (k >= 1) { while (c[k] <= 7) { c[k]++; if (c[k]为合法着色){ if (k == 8) { flag = true; break; } else { k++; } } } if (flag) { break; } c[k] = 0; k--; } if (flag) { cout << 'success' << endl; } else { cout << 'no solution' << endl; }}回溯法在最坏情况下需要O（n^2）的运行时间。
但是需要注意，虽然蛮力搜索法的最坏情况也需要O（n^2）的时间，但是根据经验回溯法的有效性远远超过蛮力法。(鬼知道这是谁的经验，反正只要知道考试用蛮力法肯定会xx)
一般回溯方法
在回溯法中，解向量中每个xi都属于一个有限的线序集Xi，因此，算法最初从空向量开始，然后选择X1中最小的元素作为x1，如果（x1）是一个部分解，算法从X2中找出最小的元素作为x2继续，如果（x1，x2）是一个部分解，则从X3中找出最小元素作为x3，否则跳过x2寻找下一个。一般地，假如算法已经找到部分解（x1,x2,x3…,xj），在判断v=（x1,x2,x3…,xj,x_j+1）时有以下情况：
分支限界法
分支限界法（branch and bound method）是求解 纯整数规划 或 混合整数规划 问题的经典方法，在上世纪六十年代由Land Doig和Dakin等人提出。这种方法灵活且便于用计算机求解，目前已经成功运用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。算法基本思想如下：
各结点的界限函数bound(vi)=[downi,upi]是解决问题的关键，通常依据具体问题而定。常见的两种分支限界法是队列式分支限界法和优先队列式分支限界法，它们分别按照队列先进先出的原则和优先队列中规定的优先级选取下一个节点为扩展节点。
求解目标不同
搜索方式不同
对扩展结点的扩展方式不同
问题描述
给出一个城市的集合和一个定义在 每一对城市之间 的耗费函数，找出耗费最小的旅行。
解决思路
考虑下图所示的情况及其代价矩阵，假定起始城市为1号城市：
屏幕快照 2018-12-07 17.39.39
注意代价矩阵的特点，每条满足要求的回路在代价矩阵中的每一行每一列有且只有1个元素与之对应。据此，我们可以用贪心算法计算问题的上界：
以起始城市作为出发城市，每次从当前出发城市发出的多条边中，选择没有遍历过的最短边连接的城市，作为下一步达到城市。在这个问题中，从城市1出发，途经1→3→5→4→2→1，路径长度1+2+3+7+3=16作为上界，即最短路径长度<=16。
对于下界，一个简单的办法是直接将矩阵中每一行的最小元素相加，在这个问题中，路径长度1+3+1+3+2=10作为下界，即最短路径长度>=10。更优的计算方式是将矩阵中每一行最小的2个元素相加除以2并向上取整。因为在一条路径上，每个城市有2条邻接边：进入该城市、离开该城市。对每一步经过的城市j，从最近的上一个城市i来，再到下一个最近城市k去，即i→j→k。在这个问题中，路径长度{(1+3)+(3+6)+(1+2)+(3+4)+(2+3)}/2向上取整等于14作为下界，即最短路径长度=14。因此，以最短路径长度dist作为TSP问题目标函数，则dist的界为[14,16]。在问题求解过程中，如果1个部分解的目标函数dist下界超出此界限，则该部分解对应了死结点，可剪枝。对于1条正在生成的路径/部分解，设已经确定的顶点(已经经过/遍历的城市)集合为U=(r1,r2, …,rk)，则该部分解的目标函数的下界为(已经经过的路径的总长的2倍+从起点到最近未遍历城市的距离+从终点到最近未遍历城市的距离+进入/离开未遍历城市时各未遍历城市带来的最小路径成本)除以2并向上取整。假设正在生成的路径/部分解为1→4,U={1,4},未遍历城市={2,3,5},该部分解下界为{2*5+1+3+(3+6)+(1+2)+(2+3)}/2向上取整等于16：
屏幕快照 2018-12-07 17.40.36
概述
随机算法是一种在接受输入的同时，为了随机选择的目的，还接受一串随机比特流并且在运行过程中使用该比特流的算法(允许算法在执行过程中随机地选择下一个计算步骤)。
随机算法通常有两个 优点 ：
随机算法的 基本特征 ：对所求解问题的同一实例用同一随机算法求解两次可能得到完全不同的效果。
这两次求解所需的时间、所得到的结果可能会有相当大的差别。
随机算法的类别
随机（概率）算法大致分四类：
常用于数值问题的求解。
这类算法所得到的往往是近似解且近似解的精度随计算时间的增加而不断提高。
在许多情况下,要计算出问题的精确解是不可能的,或者没有必要,此时,用数值概率算法可以得到相当满意的解。
用于求问题的准确解。
对于许多问题来说,近似解毫无意义。
例如,一个判定问题其解为“是”或“否” ,二者必居其一, 不存在任何近似解。
又如,我们要求一个整数的因子,这样问题的解答必须是准 确的,一个整数的近似因子没有任何意义。
用蒙特卡洛算法能求得问题的一个解,但这个解未必是正确的。
求得正确解的概率依赖于算法所用的时间,算法所用的时间越多,得到正确解的概率就越高。
蒙特卡洛算法的主要缺点也在于此,即无法有效地判定所得到的解是否肯定正确。
拉斯维加斯算法不会得到不正确的解。
一旦用拉斯维加斯算法找到一个解,这个解就一定是正确 解。
但有时用拉斯维加斯算法会找不到解。
与蒙特卡洛算法类似,拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。
对于所求解问题的任一实例,用拉斯维加斯算法反复对该实例求解足够多次,可使求解失效的概率任意小。
舍伍德算法总能求得问题的一个解,且所求得的解总是正确的。
当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时,可在这个确定性算法中引入随机性,将它改造成一个舍伍德算法,消除或减少问题的好坏实例间的这种差别。
总是给出解，但是偶尔可能会产生非正确的解。然而，可以通过多次运行原算法，并且满足每次运行时的随机选择都相互独立，使产生非正确解的概率可以减到任意小。
例子
问题描述
设T[1…n]是一个长度为n的数组，当某个元素在该数组中存在的数量多于int(s/2)时称该元素为数组T的主元素（多数元素）。
求解思路
算法随机选择数组元素x,由于数组T的非主元素个数小于n/2，所以，x不为主元素的概率小于1/2。因此判定数组T的主元素存在性的算法是一个偏真1/2正确的算法。50%的错误概率是不可容忍的，利用重复调用技术将错误概率降低到任何可接受的范围内。对于任何给定的p0，算法majorityMC重复调用(向上取整)log(1/p)次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于p。算法majorityMC所需的计算时间显然是O(nlog(1/p))。
代码实现
随机化快速排序
（可能是最为流行的一种随机算法？）
首先要明确传统快速排序的流程：从待排序序列中拿出最后一个（或者第一个）作为主元，将小于它的放在它的前面，大于它的放在它的后面，这时对该主元的前一部分和后一部分再分别递归进行“划分”，最后达到有序。这种方法有一个很大的问题就是当待排序数组是一个几乎有序的序列时其复杂度会很容易达到theta(n^2)，因为如果每次都选择第一个元素或者最后一个元素作为主元进行划分，对一个几乎有序的序列，划分后的递归对象（子序列）将会一个很长一个很短，这样可能经过好多次划分后还是有一个待划分的子部分很长。解决方法是每次不选择第一个或者最后一个作为主元，而是随机产生一个从第一个到最后一个之间的随机数作为主元进行划分，这样即保留了快速排序的优越性又避免了排序几乎有序序列时的痛点。
void RandomQuickSort(int low,int high){ if(low<high){ int v=random(low,high); int t=A[low]; A[low]=A[v]; A[v]=t; Split(A[low...high],low); RandomQuickSort(low,v-1); RandomQuickSort(v+1,high); }}该算法在最坏情况下仍然是$\theta(n^2)$，但这与输入形式无关。如果最坏情况发生，那是因为用随机数选取的主元不凑巧，这个事件发生的概率是非常小的。事实上，没有一种输入的排列可以引起它的最坏情况，算法的期望运行时间是$\theta(nlogn)$.
随机化的选择算法（寻找第k小元素）
什么是选择算法：
该算法的运行时间是theta(n)(T(n)<=20cn,c是排序43个元素所需的时间)，具有一个很大的常数系数，所以就有了随机版的选择算法：
/* * 输入：n个元素的数组A[1...n]和整数k * 输出：A中的第k小元素 * */R_Select(A,1,n,k);void R_Select(int *A, int low, int high, int k) { int v = random(low, high); int x = A[v]; A1 = {a | a < x}; A2 = {a | a = x}; A3 = {a | a > x}; if (A1.len >= k)return R_Select(A, 1, A1.len, k); else if (A.len + A2.len >= k)return x; else if (A1.len + A2.len < k)return R_Select(A, 1, A3.len, k - A1.len - A2.len);}该版本的随机算法与原版本的主要不用是原版本是将序列分为若干个5元素序列分别进行排序后找到那些5元素序列中值组成的新序列的中值作为主元对元素进行划分，而随机算法是产生一个序列中的随机数（就是在待找序列中随机找了一个数）作为主元，省去了那些排序5元素数组的步骤，对于大小为n的输入，算法RandomizedSekect执行的期望比较次数小于4n，他的期望运行时间是$\theta(n)$。
可以发现该随机算法最坏情况下的运行时间也是$\theta(n)$，但是其发生最坏情况不依赖于输入，仅当产生的随机数序列很不凑巧时才会发生，而这种概率是非常小的。
联系客服
