AlgorithmSummary2017

第一章
1．算法的形式化表示
	算法是一个四元组（Q、I、Ω、f ）
	Q是一个集合，表示计算的状态
I是Q的一个子集，表示计算的输入
Ω 是Q的一个子集，表示计算的输出 
f是Q到它自身的一个映射，表示计算的规则
2．算法设计的步骤
 理解问题——分析精确解或近似解——选择数据结构和算法设计策略——设计算法——证明正确性——设计程序
3．算法时间复杂度的分类、O的定义
	时间复杂度的分类：
	按数量级递增排列，常见的时间复杂度有：
常数阶O(1), 注意：1仅仅表示常数的意思；
对数阶O(log2n),
线性阶O(n),
线性对数阶O(nlog2n),
平方阶O(n2)，
立方阶O(n3),...，
k次方阶O(nk),
指数阶O(2n) 。

一般地，对于足够大的n，常用的时间复杂性存在以下顺序： 
O(1)< O(logn)< O(n)< O(n*logn)<O(n2)<O(n3)…
<O(2n)<O(3n)<…<O(n!) 
按照渐近阶从低到高的顺序排列以下表达式：
      4n2；  logn；  3n； 20n；  2； n2/3；   n！
	    2      logn  n2/3  20n   4n2  3n   n！

	渐进上界记号O定义：渐进性态的几个记号O、Ω 、θ如果存在两个正的常数c,n0  使得当n>n0时，有 T(n) ≤ c f(n) 称T(n)是O(f(n))的。f(n)是T(n)增长率的上界。如果存在两个正的常数c,n0  使得当n>n0 时，有T(n) ≥ c f(n) 称T(n)是Ω(f(n))的。f(n)是T(n)增长率的下界。如果  T(n) =O(f(n)) 且  T(n) =Ω(f(n)) 则 T(n) = θ(f(n)

4．算法的性质
有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
　确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
　可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
　输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
　输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量
第二章
1．	贪心法的定义
指的是从对问题的某一初始解出发,一步一步的攀登给定的目标,尽可能快地去逼近更好的解。当达到某一步,不能再攀登时,算法便终止。
2．	贪心法的特点、基本要素 （包括其定义）
贪心法的特点：
贪心算法总是做出在当前看来是最好的选择,它并不是从总体最优上加以考虑,他所作出的选择只是在某种意义上的局部最优选择。能够得到的解不一定是最优解。
基本要素及其定义：
（1）	贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
（2）	最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
3．	单源最短路径、最优装载、分数背包问题（算法）、活动安排（算法包括证明）
单源最短路径：
【问题】给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题
【方法】	
1、算法基本思想
		Dijkstra算法是解单源最短路径问题的贪心算法。
基本思想:设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
		初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
     Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

问题描述:
输入带权有向图G=(V，E)， V={1，2，…，n}，顶点V1是源
C[i][j]表示边(i,j)的权
dist[i]表示从源到顶点v1的最短特殊路径长度
prev[i]表示从源到顶点i的最短路径上i的前一个顶点
算法描述：
基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。
S[i]—源点到i顶点的最短路径是否找到
	初始化：
for(i=1;i<=n;i++)
   {s[i]=0;dist[i]=c[v1][i];}
S[v1]=1,dist[v1]=0;
	每次从V-S中取出具有最短特殊路长度的顶点u，并将u添  加到S中
for(num=2;num<=n;num++)
  {从dist[2]到dist[n]选取一顶点u且满足s[u]=0,使     dist[u]=min{dist[2],dist[3],…,dist[n]};
    s[u]=1;
}
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中后，同时对数组dist作必要的修改。
for(j=1;j<=n;j++)
{
  if(s[j]==0&&c[u][j]<maxint)
   { newdist=dist[u]+c[u][j];
     if(newdist< dist[j]) 
      {dist[j]=newdist;prev[j]=u;}
    }
 }
整个过程执行n-1次

最优装载：
【问题】有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
【方法】对最优装载问题进行形式化描述

	用一个向量（x1,x2,x3,…,xn）,表示装的个数多少？
	约束条件：xi    ∈{ 0,1 }        
 
	目标函数： 
1、算法描述
•	最优装载问题可用贪心算法求解。
•	采用重量最轻者先装的贪心选择策略
•	可产生最优装载问题的最优解。 

template<class Type>
void Loading(int x[],  Type w[], Type c, int n)
{
        int *t = new int [n+1];
        Sort(w, t, n);
        for (int i = 1; i <= n; i++) x[i] = 0;
        for (int i = 1; i <= n && w[t[i]] <= c; i++) 
             {x[t[i]] = 1; c -= w[t[i]];}
}
2、贪心选择性质
  	可以证明最优装载问题具有贪心选择性质。 
3、最优子结构性质
	最优装载问题具有最优子结构性质。
		由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。
		算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。
分数背包问题（算法）：



活动安排（算法包括证明）：
    设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。
   若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

第三章
1．	递归与分治的基本思想	
分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归的基本思想：直接或间接地调用自身，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
2．	分治的基本步骤、特点 
基本步骤：
（1）	分解：将原问题分解成若干个规模较小互相独立与原问题形式相同的子问题；
（2）	解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 
（3）	合并：将各个子问题的解合并为原问题的解。
特点：
	（1）该问题的规模缩小到一定的程度就可以容易地解决； 
      （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 
      （3）利用该问题分解出的子问题的解可以合并为该问题的解； 
  （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题
3．	分治复杂度函数递归方程的推导（过程、结论）
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
 
通过迭代法求得递归方程的解：
 
求出该算法时间复杂度函数：
O(logn)

4．	二分搜索（算法）、快速排序和归并排序的排序过程及其时间复杂度、大整数乘法
二分搜索（算法）：
#include <stdio.h>
int binarySearch(int a[], const int& x, int n)
{
    int left=0, right=n-1;
    while (left <= right)
    {
        int middle = (left+right)/2;
        if (x==a[middle])
        {
            return middle;
        }
        if (x > a[middle])
        {
            left = middle+1;
        }
        else
        {
            right = middle-1;
        }
    }
    return -1;
}
 
int main()
{
    int a[] = {1,2,5,7,8,10};
    printf("%d\n",binarySearch(a,8,6));
    return 0;
}
复杂度分析：
每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。
快速排序过程以及其时间复杂度：
在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。 
　　/ /使用快速排序方法对a[ 0 :n- 1 ]排序 
　　从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点 
　　把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点 
　　递归地使用快速排序方法对left 进行排序 
　　递归地使用快速排序方法对right 进行排序 
　　所得结果为l e f t + m i d d l e + r i g h t  
　　考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。 
　　把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。 
程序14-6 快速排序
template<class T> 
　　void QuickSort(T*a, int n) 
　　{// 对a[0:n-1] 进行快速排序 
　　{// 要求a[n] 必需有最大关键值 
　　quickSort(a, 0, n-1); 
　　template<class T> 
　　void quickSort(T a[], int l, int r) 
　　{// 排序a [ l : r ]， a[r+1] 有大值 
　　if (l >= r) return; 
　　int i = l, // 从左至右的游标 
　　j = r + 1; // 从右到左的游标 
　　T pivot = a[l]; 
　　// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换 
　　while (true) { 
　　do {// 在左侧寻找>= pivot 的元素 
　　i = i + 1; 
　　} while (a < pivot); 
　　do {// 在右侧寻找<= pivot 的元素 
　　j = j - 1; 
　　} while (a[j] > pivot); 
　　if (i >= j) break; // 未发现交换对象 
　　Swap(a, a[j]); 
　　} 
　　// 设置p i v o t 
　　a[l] = a[j]; 
　　a[j] = pivot; 
　　quickSort(a, l, j-1); // 对左段排序 
　　quickSort(a, j+1, r); // 对右段排序 
　　}
归并排序过程以及其时间复杂度：
归并是指将若干个已排好序的部分合并成一个有序的部分
#include<stdio.h>
//将有二个有序子数组a[begin...mid]和a[mid+1...end]合并。
void MergeArray(int a[],int begin,int mid,int end,int temp[])
{
	int i=begin,j=mid+1;
	int m=mid,n=end;
	int k=0;

	while(i<=m && j<=n)
	{
		if(a[i]<=a[j])
			temp[k++]=a[i++];
		else
			temp[k++]=a[j++];
	}
	while(i<=m)
		temp[k++]=a[i++];
	while(j<=n)
		temp[k++]=a[j++];
	
	//把temp数组中的结果装回a数组
	for(i=0;i<k;i++)   
		a[begin+i]=temp[i];
}

void mergesort(int a[],int begin,int end,int temp[])
{
	if(begin<end)
	{
		int mid = (begin+end)/2;
		mergesort(a,begin,mid,temp);   //左边有序
		mergesort(a,mid+1,end,temp);   //右边有序
		MergeArray(a,begin,mid,end,temp); //将左右两边有序的数组合并
	}
}
int main()
{
	int num[10]={2,5,9,3,6,1,0,7,4,8};
	int temp[10];
	mergesort(num,0,9,temp);
	for(int i=0;i<10;i++)
	{
		printf("%d",num[i]);
	}
	printf("\n");
}

归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。

大整数乘法：







第四章
1．	动态规划的基本思想、基本步骤 、基本要素
动态规划的基本思想：
基本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一个子问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
动态规划基本步骤：
（1）分析最优解的性质，并刻画其结构特征。 
（2）递归地定义最优值。 
（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 
（4）根据计算最优值时得到的信息，构造一个最优解。
动态规划基本要素：
（1）最优子结构
（2）重叠子问题
（3）备忘录方法
2．	投资问题（算法）、0-1背包问题、最长公共子序列（算法）、矩阵连乘
投资问题（算法）：



0-1背包问题：


最长公共子序列（算法）：


矩阵连乘：







第五章
1．	回溯法的基本思想
基本思想:按照深度优先策略，从根结点出发搜索解空间。算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。如果满足进入该子树，继续按深度优先的策略搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法
2．	回溯法解题步骤 
1、	确定问题的解空间：应用回溯法时，首先应明确定义问题的解的空间。问题的解空间应至少包含问题的一个解。
2、	确定结点的扩展规则
3、	搜索解空间：从开始结点出发，以深度优先的方式搜索整个解空间。
3．	0-1背包问题、n后问题、图的M着色
0-1背包问题：
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？
#include<stdio.h>
int c=30;    //背包容量
int n=3;    //对象数目
int w[]={20,15,15};  //对象重量数组
int v[]={40,25,25};  //对象收益数组
int cw;   //当前背包重量
int cv;   //当前背包价值
int bestv;//迄今最大的收益
int X[n];  //记录在树中的移动路径,为1的时候表示选择该组数据，为0的表示不选择该组数据

void getBest(int i)
{
    if(i>=n)//递归结束的判定条件
    {
        if(cv>bestv)
            bestv=cv;

        return;
    }
    if(cw+w[i]<=c)//进入该节点的右孩子（值为1的孩子）
    {
        X[i]=1;
        cw+=w[i];
        cv+=v[i];
        getBest(i+1);
        cw-=w[i];//此处回溯
        cv-=v[i];
    }

    X[i]=0;//进入该节点的右孩子（值为0的孩子）
    getBest(i+1);
}

int main()
{

    getBest(0);
    printf("%d",bestv);

    return 0;
}
n后问题：
		Eightqueen( )
{  x[1]=1; k=1;
   do { if(x[k]<=8)
           { die=0
              for (i=1; i<k; i++)
                { if (x[i]=x[k]) { die=1; break }
                   if (x[k]-x[i])=abs(k-i)) { die=1; break }
                 } 
              if(die=1) x[k]=x[k]+1 else{k=k+1; x[k]=1}
            } 
           else { x[k]=1; k=k-1;  x[k]=x[k]+1; }
       } while(k<=8  and k>0)
    if(k>8) output x[i]..x[8]  else output no solve
 }

图的M着色：
mcoloring( )
{  x[1]=1; k=1;
   do { if(x[k]<=m)
           { die=0
              for (i=1; i<k; i++)
                if (x[i]=x[k] and c[i][k]=1) { die=1; break }
              if(die=1) x[k]=x[k]+1 else{k=k+1; x[k]=1}
            } 
           else { x[k]=1; k=k-1;  x[k]=x[k]+1; }
       } while(k<=n  and k>0)
    if(k>n) output x[i]..x[n]  else output no solve
 }

第六章
1.	分支限界法与回溯法的比较
（1）	求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解
（2）	搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 

2.	常见的两种分支限界法
（1）队列式(FIFO)分支限界法
    按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 
（2）优先队列式分支限界法
    按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
3.	0-1背包问题、装载问题
0-1背包问题：
   首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。
在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。
算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。
上界函数：
while (i <= n && w[i] <= cleft)       // n表示物品总数，cleft为剩余空间
      {
         cleft -= w[i];                            //w[i]表示i所占空间
         b += p[i];                                 //p[i]表示i的价值
         i++;
      }
if (i <= n) b += p[i] / w[i] * cleft;    // 装填剩余容量装满背包
return b;                                       //b为上界函数

while (i != n+1) {// 非叶结点
      // 检查当前扩展结点的左儿子结点
      Typew wt = cw + w[i];
      if (wt <= c) {// 左儿子结点为可行结点
         if (cp+p[i] > bestp) bestp = cp+p[i];
         AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);}
         up = Bound(i+1);
      // 检查当前扩展结点的右儿子结点
      if (up >= bestp) // 右子树可能含最优解
           AddLiveNode(up, cp, cw, false, i+1);
         //   取下一个扩展节点（略）
}
装载问题：