有效的算法设计

有效的算法设计

贪心法。Dijkstra的最短路径(时间复杂度O(n2))；Prim求最小生成树邻接表存储时是O(n+e),图O(n2)；关键路径及关键活动的求法。

回溯法

分支限界法

分治法。分割、求解、合并。二分查找、归并排序、快速排序。

动态规划。Floyd-Warshall算法求解图中所有点对之间最短路径时间复杂度为O(n3)

动态规划解题的方法是一种高效率的方法，其时间复杂度通常为O(n2)，O(n3)等，可以解决相当大的信息量。（数塔在n<=100层时，可以在很短的时间内得到问题解）

适用的原则：原则为优化原则，即整体优化可以分解为若干个局部优化。

动态规划比穷举法具有较少的计算次数

递归算法需要很大的栈空间，而动态规划不需要栈空间

贪心和动态规划的差别：

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。

贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

P问题

P问题，如果它可以通过运行多项式次(即运行时间至多是输入量大小的多项式函数的一种算法获得解决），可以找到一个能在多项式的时间里解决它的算法。—-确定性问题

NP问题，虽然可以用计算机求解，但是对于任意常数k，它们不能在O(nk)时间内得到解答，可以在多项式的时间里验证一个解的问题。所有的P类问题都是NP问题。

NP完全问题，知道有效的非确定性算法，但是不知道是否存在有效的确定性算法，同时，不能证明这些问题中的任何一个不存在有效的确定性算法。这类问题称为NP完全问题。