程序员都应该精通的六种算法，你会了吗

对于一名优秀的程序员来说，面对一个项目的需求的时候，一定会在脑海里浮现出最适合解决这个问题的方法是什么，选对了算法，就会起到事半功倍的效果，反之，则可能会使程序运行效率低下，还容易出bug。因此，熟悉掌握常用的算法，是对于一个优秀程序员最基本的要求。

那么，常用的算法都有哪些呢？一般来讲，在我们日常工作中涉及到的算法，通常分为以下几个类型：分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。

一、分治算法

分治算法，顾名思义，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治算法一般分为三个部分：分解问题、解决问题、合并解。

分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立，求出来的解可以合并为该问题的解的情况。

典型例子比如求解一个无序数组中的最大值，即可以采用分治算法，示例如下：

def pidAndConquer(arr,leftIndex,rightIndex):

if(rightIndex==leftIndex+1 || rightIndex==leftIndex){

return Mathmax(arr[leftIndex],arr[rightIndex]);

}

int mid=(leftIndex+rightIndex)/2;

int leftMax=pidAndConquer(arr,leftIndex,mid);

int rightMax=pidAndConquer(arr,mid,rightIndex);

return Mathmax(leftMax,rightMax);

二、贪心算法

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法的基本思路是把问题分成若干个子问题，然后对每个子问题求解，得到子问题的局部最优解，最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少，更大的用途在于平衡算法效率和最终结果应用，类似于：反正就走这么多步，肯定给你一个值，至于是不是最优的，那我就管不了了。就好像去菜市场买几样菜，可以经过反复比价之后再买，或者是看到有卖的不管三七二十一先买了，总之最终结果是菜能买回来，但搞不好多花了几块钱。

典型例子比如部分背包问题：有n个物体，第i个物体的重量为Wi，价值为Vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。

贪心策略就是，每次都先拿性价比高的，判断不超过C。

三、迭代算法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性 *** 作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。最终得到问题的结果。

迭代算法适用于那些每步输入参数变量一定，前值可以作为下一步输入参数的问题。

典型例子比如说，用迭代算法计算斐波那契数列。

四、枚举算法

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。

枚举算法适用于候选答案数量一定的情况。

典型例子包括鸡钱问题，有公鸡5，母鸡3，三小鸡1，求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下：

五、回溯算法

回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置，那么下一个皇后的位置便被限制住了，下一个皇后需要一直找直到找到安全位置，如果没有找到，那么便要回溯到上一个皇后，那么上一个皇后的位置就要改变，这样一直递归直到所有的情况都被举出。

六、动态规划算法

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划算法适用于当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响，即无后效性的问题。

典型例子比如说背包问题，给定背包容量及物品重量和价值，要求背包装的物品价值最大。

分治，顾名思义，分而治之;把一个父运算，分解成几个子运算，常见算法如归并排序。用函数T来表示运算的时间的话，父运算T(n)=T(n/k)+C。

具体的也记不太清楚了，如果是我做这题，我会用归并把数组排序，排完序，最大最小自然就出来了。

标准归并算法C++描述，具体思想网上有很多资料自己去看

/归并算法/

#include<iostream>

typedef int keytype;

void merge(keytype ,int,int,int);

void merge_sort(keytype ,int,int);

int main()

{

using namespace std;

keytype a[11]={1,5,8,4,6,3,8,1,3,8,2};

merge_sort(a,0,9);

for(int i=0;i<11;++i)

cout<<a[i]<<" ";

return 0;

}

void merge_sort(keytype a,int low,int up)

{

int q=0;

if(low<up)

{

q=(low+up)/2;

merge_sort(a,low,q);

merge_sort(a,q+1,up);

merge(a,low,q,up);

}

}

void merge(keytype a,int low,int mid,int up)

{

int len1=mid-low+1;

int len2=up-mid;

keytype L=new keytype[len1+1];//栈内存效率更高

keytype R=new keytype[len2+1];

for(int i=0;i<len1;++i)

L[i]=a[low+i];

for(int i=0;i<len2;++i)

R[i]=a[mid+i+1];

L[len1]=R[len2]=32767;

int i=0,j=0;

for(int k=low;k<=up;++k)

{

if(L[i]<=R[j])

{

a[k]=L[i];

++i;

}

else

{

a[k]=R[j];

++j;

}

}

delete[] L;

delete[] R;

}

递归的把任务分解成二个子任务，merge整合函数复杂度是O(n),每次分解成两部分分别排序之后调用整合函数，很容易知道复杂度是O(n),所以算法T(n)=T(n/2)+O(n),复杂度为O(nlogn)

随机增量法较为简单，遵循增量法的一贯思路，即按照随机的顺序依次插入点集中的点，在整个过程中都要 维护并更新一个与当前点集对应的Delaunay三角剖分。考虑插入vi点的情况，由于前面插入所有的点v1,v2,,vi-1构成的DT(v1, v2,,vi-1)已经是Delaunay三角剖分，只需要考虑插入vi点后引起的变化，并作调整使得DT(v1,v2,,vi-1) U vi成为新的Delaunay三角剖分DT(v1,v2,,vi)。

(插入调整过程：首先确定vi落在哪个三角形中（或边上），然后将vi与三角形三个顶点连接起来构成三个三角形（或与共边的两个三角形的对顶点连接起来构 成四个三角形），由于新生成的边以及原来的边可能不是或不再是Delaunay边，故进行边翻转来调整使之都成为Delaunay边，从而得出DT (v1,v2,,vi)。)

其Pseudocode如下：

Algorithm IncrementalDelaunay(V)

Input: 由n个点组成的二维点集V

Output: Delaunay三角剖分DT

1add a appropriate triangle boudingbox to contain V ( such as: we can use triangle abc, a=(0, 3M), b=(-3M,-3M), c=(3M, 0), M=Max({|x1|,|x2|,|x3|,} U {|y1|,|y2|,|y3|,}))

2initialize DT(a,b,c) as triangle abc

3for i <- 1 to n

do (Insert(DT(a,b,c,v1,v2,,vi-1), vi))

4remove the boundingbox and relative triangle which cotains any vertex of triangle abc from DT(a,b,c,v1,v2,,vn) and return DT(v1,v2,,vn)

Algorithm Insert(DT(a,b,c,v1,v2,,vi-1), vi)

1find the triangle vavbvc which contains vi // FindTriangle()

2if (vi located at the interior of vavbvc)

3 then add triangle vavbvi, vbvcvi and vcvavi into DT // UpdateDT()

FlipTest(DT, va, vb, vi)

FlipTest(DT, vb, vc, vi)

FlipTest(DT, vc, va, vi)

4else if (vi located at one edge (Eg edge vavb) of vavbvc)

5 then add triangle vavivc, vivbvc, vavdvi and vivdvb into DT (here, d is the third vertex of triangle which contains edge vavb) // UpdateDT()

FlipTest(DT, va, vd, vi)

FlipTest(DT, vc, va, vi)

FlipTest(DT, vd, vb, vi)

FlipTest(DT, vb, vc, vi)

6return DT(a,b,c,v1,v2,,vi)

Algorithm FlipTest(DT(a,b,c,v1,v2,,vi), va, vb, vi)

1find the third vertex (vd) of triangle which contains edge vavb // FindThirdVertex()

2if(vi is in circumcircle of abd) // InCircle()

3 then remove edge vavb, add new edge vivd into DT // UpdateDT()

FlipTest(DT, va, vd, vi)

FlipTest(DT, vd, vb, vi)

复杂度分析

问题的规模为点集中的点的总个数n（没有重合的点），循环内的基本的 *** 作有：

1寻找插入点所在的三角形(FindTriangle())

2测试点是否在外接圆内(InCircle())

3更新三角网(UpdateDT())

4寻找共测试边的第三顶点(FindThirdVertex())

考虑最坏情况：

时间复杂度T ＝ T(addboudingbox()) + Sum(T(insert(i), i=1,2,,n)) + T(removeboundingbox)

因为addboudingbox()和removeboundingbox不随n变化，是个常量。T(addboudingbox()) = O(1), T(removeboundingbox()) = O(1)

T = Sum(T(insert(i), i=1,2,,n)) + O(1) + O(1)

考虑插入第i个的点的时间:

T(insert(i)) = T(FindTriangle(i)) + T(UpdateDT(i)) + KT(FlipTest(i)) (K为常数)

故T = Sum(T(FindTriangle(i)), i=1,2,,n) + Sum(T(UpdateTD(i)), i=1,2,,n) + KSum(T(FlipTest(i)), i=1,2,,n)

挨个考虑：

FindTriangle(i)是要找出包含第i个点的三角形，由欧拉公式知道，平面图的面数F是O(n), n为顶点数，故此时总的三角形数是O(i)的。所以问题相当于在O(i)个记录中查找目标记录，如果不借助特殊的数据结构，按照一般顺序查找，需要O (i)的时间。

T(FindTriangle(i)) = O(i),故：Sum(T(FindTriangle(i)), i=1,2,,n) = O(nn)

UpdateTD(i)是更新三角网数据结构，插入和删除三角形到当前的三角网是个常量 *** 作，因为已经知道插入和删除的位置。

T(UpdateDT(i)) = O(1),故：Sum(T(UpdateTD(i)), i=1,2,,n) = O(n)

FlipTest(i)比较复杂些，是个递归过程。细分为：T(FlipTest(i)) = T(FindThirdVertex(i)) + T(InCircle(i)) + T(UpdateDT(i)) + 2T(FlipTest(j))。(这里，用j来区分不同的深度)

因为InCircle(i)是测试点是否在外接圆内，是个常量 *** 作，不随点数变化而变化。故T(InCircle(i)) = O(1), 又T(UpdateDT(i) = O(1)(见上)

FindThirdVertex(i)是查找目标点，在O(i)个记录中查找目标记录，如果不借助特殊的数据结构，按照一般顺序查找需要O(i)的时间。T(FindThirdVertex(i)) = O(i)

剩下的是递归调用FlipTest的过程，不过还好，因为FlipTest的递归深度只有常数级(设为K)。正比于点在三角网中的度数(degree)。故FlipTest(i)最多调用的次数为22,,2 = K',还是常数。

故T(FlipTest(i)) = O(i) + O(1) + O(1) + K'(O(i) + O(1) + O(1)) = O(i) + O(1) + O(1)

Sum(T(FlipTest(i)), i=1,2,,n) = O(nn) + O(n) + O(n)

综上，最坏情况下算法总时间复杂度 T = O(nn) + O(n) + K(O(nn) + O(n) + O(n)) + O(1) + O(1) = O(nn)

其中，关键的 *** 作是FindTriangle()和FindThirdVertex()，都是nn次的。

在网上很多资料说随机增量法是O(nlogn)的，但是分析下来，却是O(nn)的。后来看到别人的实 现，原来是用的别的数据结构来存储三角网，减少了FindTriangle()和FindThirdVertex()的复杂度。使得某次查找三角形和共边 三角形的第三顶点能在O(logn)，而非O(n)的时间内实现。这样，总的查找的时间为 O(log1)+O(log2)+,+O(logn) = O(nlogn)。程序=算法+数据结构，看来一点没错。

比如说用DAG，Quad-edge等，都能达到O(nlogn)的复杂度。

分治法（Divide and Conquer）

据说是现在实际表现最好的。

#include<iostream>// 引入错误

using namespace std;

int MIN,MAX;

double Min,Max;

template<typename T>

void minmax (T A[10],int low,int high,T &min,T &max)

{

    T max1,min1,max2,min2;

    if(high == low) // 增加相等时候判断

    {

        min = A[high];

        max = A[high];

    }

    else if (high-low==1)// 具体 *** 作错误

    {

        min = A[high] < A[low]  A[high]:A[low];

        max = A[high] > A[low]  A[high]:A[low];

    }

    else

    {   int mid;

        mid=(low+high)/2;

        minmax (A,low,mid,min1,max1);

        minmax (A,mid+1,high,min2,max2);

        min = min1 < min2  min1:min2;//  *** 作错误与 *** 作遗漏

        max = max1 > max2  max1:max2;

    }

}

int main()

{

    int A1[8]={1,2,5,6,8,10,32,56};

    minmax (A1,0,7,MIN,MAX);

    cout<<"min="<<MIN<<"   max="<<MAX<<endl;

    double A2[8]={11,22,32,46,53,102,935,836};

    minmax (A2,0,7,Min,Max);

    cout<<"min="<<Min<<"   max="<<Max<<endl;

    return 0;

}

修改代码如上，楼主有些语法用错了，然后就是逻辑判断考虑不周全。

运行结果如下：

邮局选址问题