5大算法策略

算法策略和算法的区别

算法策略是面向问题的，算法是面向实现的。二者又不可分割，通过算法策略找到解决问题的算法，而不同算法求解的问题算法策略是不一样。

算法的正确性分析

一个算法是正确的，如果它对于每一个输入都是最终停止，而且产生正确的输出。
一个错误的算法包括，在某一个输入上不停止，或者对所有输入都停止，但是对某一个输入产生不正确的结果。
算法正确性的证明
证明算法对所有的输入都停止，证明对每个输入都能产生正确的结果。

算法的复杂性分析

目的：预测算法对不同输入所需要的资源量
复杂性测度：时间，空间，Ｉ/O 等，是输入大小的函数
用途：为求解一个问题选择最佳算法、最佳设备
涉及到的数学学科：离散数学，组合数学，概率论，代数

算法复杂度的度量

时间复杂度：一个算法特定输入的时间复杂性是指该算法对输入产生结果需要的原子操作或者步数
空间复杂度：一个算法特定输入的空间复杂性是指该算法对该输入结果产生结果所需要的存储空间大小，一般指内存
最坏复杂性：比如插入排序，逆序数组
最优复杂性：比如插入排序，有序数组
平均复杂性：比如插入排序，随机数组
比如一段代码
sum=0; //执行1次
for(i=1;i<=n;i++) //执行n次
for(j=1;j<=n;j++) //执行n2次
sum++; //执行n2次
本程序段的T(n)=2n2 +n+1，时间复杂度应取指数级别最高的，所以为O(n2)。

计算复杂性函数的阶

增长的阶，如果描述算法的效率，阶描述的是增长率，忽略低阶项和常系数
常用的阶 O(1), O(N),O(N平方）,O(lnN)

5大算法策略

算法策略的中心思想是用算法的基本工具循环机制或者递归机制实现算法

分治法

该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解
应用场景
求解斐波那契数列；
递归与HANOI塔问题；
二分法求方程近似解；
合并排序；
求最大值和最小值的分治算法；
快速排序；
线性时间选择；
最接近点对问题；
循环赛日程表；
大整数乘法；
棋盘覆盖；

最优化原理

问题中的状态必须满足最优化原理；
问题中的状态必须满足无后效性。
所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。
动态规划法的应用：
最长公共子序列(LCS)
最长递增子序列(LIS)
背包问题
用动态规划实现导弹拦截
最大化投资回报问题的实现
矩阵连乘
走金字塔
凸多边形最优三角剖分
双调欧几里得旅行商问题

贪心算法

在对问题求解时，总是做出在当前看来是最好的选择.一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
贪心算法应用：
最小生成树之Prim算法
最小生成树之kruskal算法
Dijkstra算法（求解最短路径)
Huffman编码
再论背包问题
钱币找零问题
活动选择问题
小船过河问题
区间覆盖问题
销售比赛

回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
数的划分
运动员最佳配对问题
解决汽车加油次数最少问题
找出n个自然数中取r个数的全排列
八皇后问题
图的着色问题
装载问题
批处理作业调度问题
再再论背包问题
最大团问题
连续邮资问题
符号三角形问题

分支限界法

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
常见的两种分支限界法：
队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
应用场景
分支限界法之装载问题
分支限界法之布线问题
分支限界法之0 1背包问题
分支限界法之旅行售货员问题