算法分析小结

目前常用的算法分析思路有以下几种

• 迭代法
• 穷举搜索法
• 动态规划
• 贪心算法
• 回溯法
• 分治算法
• 递归

1.迭代法

是一种不断用旧值递推新值的过程，分精确迭代和近视迭代。是用来求方程和方程组近似根的方法。

• 确定迭代变量：迭代变量一般就是要求解的问题的解，利用迭代递推公式可以不断地由旧值递推出新值。根据问题的不同，迭代变量可以是一个，也可以是多个。确定迭代变量，通常还要根据迭代递推关系给出迭代变量的初始值，这一点也很重要。
• 确定迭代递推关系：迭代递推关系是根据旧值计算新值的关系或公式，这是迭代法实现的关键，如果不能确定迭代关系，则无法用迭代法实现算法。
• 确定迭代终止条件：迭代终止条件是控制迭代过程退出的关键条件。迭代不可能无休止地进行，必须设置迭代终止条件，在适当的时候退出迭代。迭代终止条件一般有三种假设：其一是迭代变量已经求得问题的精确值；其二是迭代变量无法得到精确值，但是某个迭代的值的精度已经满足要求；其三是指定明确的迭代计算次数。迭代算法的具体实现，可根据问题的类型选择迭代终止条件。一般情况下，为了防止迭代关系在某个区间上发散（不收敛）使得算法进入死循环，都会把第三个条件作为异常退出条件和其他迭代终止条件配合使用，也就是说，即使无法得到符合条件的解，只要迭代计算次数达到某个限制值，也退出迭代过程。

2.穷举搜索法

或者叫蛮力法。对可能的解的众多候选按照某种顺序逐一枚举和检验。典型的问题如选择排序和冒泡排序。

案例：背包问题

给定n个重量为 w1,w2,…,wn,定价为 v1,v2,…,vn 的物品，和一个沉重为W的背包，求这些物品中一个最有价值的子集，且能装入包中。

思路:

• 利用递归进行遍历求出各个的可能性
• 将遍历出的结果存入int[] back = new int[N],进行缓存
• 没存入一个back[]数组,进行遍历,将符合的题目要求allWigth[总的重量]<=W的,存入到Map中
• String表示背包情况. Integer表示总价值
• 在存入的Map的所有数据中,遍历出最大的Integer,也就是最大的价值
• 根据Integer值,遍历出对应的String,就是背包的情况

  3.动态规划DP

DP通常基于一个递推公式及一个(或多个)初始状态，当前子问题解由上一次子问题解推出。

状态
状态转移方程
递推关系

动态规划算法的关键在于解决冗余，以空间换时间的技术，需要存储过程中的各种状态。可以看着是分治算法+解决冗余

使用动态规划算法的问题的特征是子问题的重叠性，否则动态规划算法不具备优势

基本步骤

1. 划分问题
2. 选择状态
3. 确定决策并写出状态转移方程
4. 写出规划方程

案例：青蛙跳台阶问题

题目: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

思路： 它每次只能跳一阶或者两阶台阶；那么它跳到第n阶台阶就有两种情况，从第n-1阶台阶一次跳一阶；或者从n-2阶台阶一次跳两阶；那么依次类推，只要保留跳到n-1和n-2的情况就可以算出跳到n的次数青蛙在面对n个台阶时的解决方案数是f(n)，那么我们知道f(n) = f(n – 1) + f(n – 2)。其中的f(n – 1)与f(n – 2)就是两个子问题的最优解，此时我们可以理解成一个问题的最优解包含了其子问题的最优解，那么这个时候这种问题具有了最优子结构性质。

状态定义：dp为一个一维数组，dp[i]代表数列第i个数字
转移方程：dp[i+1] = dp[i] + dp[i-1]

4.贪心算法

不追求最优解，只找到满意解。每一步都选择局部最优解，最终得到的就是最优解

NP完全问题

• 概念 在超多项式时间内解决的问题是不易处理的问题。以难解著称的问题，比如旅行商问题和集合覆盖问题，人们普遍认为这些问题，不可能编写出可快速解决的算法。
• 所以针对NP完全问题，我们无法给出快速求取精确解的算法。所以我们一般用近似算法来解决此类问题，获取一个近似解。
  近似算法优劣的两个标准：
  1.速度有多快
  2.得到的近似解和最优解接近程度

案例：旅行商问题

题目:一个旅行商要前往5个不同的城市，同时确保行程最短。如何计算最短的行程。5个城市有120种组合。这是一个阶乘问题，随着城市数目的增加，运行时间增长非常快。无法快速解出。

思路: 先随便找一个城市作为起点城市，然后每次都选剩余城市中距离当前城市最近的一个城市，直到选择完毕。

5.回溯法

也叫 试探法。 是一种选优搜索法，按照选优条件搜索，当搜索到某一步，发现原先选择并不优或达不到目标，就退回重新选择。

一般步骤

1. 针对问题，定义解空间（ 这时候解空间是一个集合，且包含我们要找的最优解）
2. 组织解空间，确定易于搜索的解空间结构，通常组织成树结构 或 图结构
3. 深度优先搜索解空间，搜索过程中用剪枝函数避免无效搜索

回溯法求解问题时，一般是一边建树，一边遍历该树；且采用非递归方法。

案例：八皇后问题

8x8的国际象棋棋盘上放置8个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。任意2个皇后都不能处于同一个 横线，纵线，斜线上。

分析

1. 任意2个皇后不能同一行，也就是每个皇后占据一行，通用的，每个皇后也要占据一列
2. 一个斜线上也只有一个皇后

思路：类似深度优先搜索。如果当前结点可行，就搜索当前结点的一个子结点，反之，就回溯，搜索当前结点的子结点。递归所生成的树是一棵深度优先搜索树，叶子结点是那些不合法的结点(换句话说，就是无法向下递归的结点)和答案结点。

6.分治算法

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，各个击破，分而治之。

分治算法常用递归实现

1） 问题缩小的小规模可以很容易解决
2) 问题可以分解为规模较小相同问题
3） 子问题的解可以合并为该问题的解
4） 各个子问题相互独立，(如果这条不满足,转为动态规划求解）

分治法的步骤：

1. 分解
2. 解决
3. 合并

7.递归

递归是一种设计和描述算法的有力工具。 递归算法执行过程分 递推 和 回归 两个阶段

在 递推 阶段，将大的问题分解成小的问题
在 回归 阶段，获得最简单问题的解后，逐级返回，依次得到稍微复杂情况的解，知道获得最终的结果

1） 确定递归公式
2） 确定边界条件

递归运行效率较低，因为有函数调用的开销，递归多次也可能造成栈溢出。

案例：汉诺塔问题
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

思路：求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。
实现这个算法可以简单分为三个步骤：
（1） 把n-1个盘子由A 移到 B；
（2） 把第n个盘子由 A移到 C；
（3） 把n-1个盘子由B 移到 C；
从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：
（1）中间的一步是把最大的一个盘子由A移到C上去；
（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上