算法设计

什么是算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性。
有穷性、确定性、可行性、输入、输出。

算法的复杂度

算法的时间复杂度分析：主要是分析算法的运行时间，即算法执行所需要的基本操作数。不同规模的输入所需要的基本操作数是不相同。在算法分析中，可以建立以输入规模n为自变量的函数T（n）来表示算法的时间复杂度。
即使对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同，根据不同的输入，将算法的时间复杂度分析分为：最佳情况、最坏情况、平均情况。

• 渐进符号：以输入规模n为自变量建立的时间复杂度实际上还是较复杂的，例如：an2+bn+c，不仅与输入规模有关，还与系数a、b和c有关。此时可以对该函数做进一步的抽像，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的低价项和高阶项的系数，仅考虑n2。
  当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。

  常数级 o(n)、线性级、对数级、平方级o(n2)。
  O(1)，O(logn) ，O(n)，O(nlogn)，O(n2)

递归

递归是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用办法。递归有两个基本要素。
边界条件，即确定递归何时终止，也称为递归出口。
递归模式，即大问题是如何分解为小问题的，也称为递归体。

递归算法的时间复杂度分析方法：
将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直到得到一个求和表达式，得到结果。

分治法

分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分为治之。如果规模为n的问题可分解成k个子问题，1<k<=n，这些子问题互相独立且与原问题相同。 分治法产生的子问题往往是原问题的较小模式，这就是为递归技术提供了方便。
一般来说， 分治算法在每一层递归上都有3个步骤。
1. 分解：将原问题分解成一系列子问题。
2. 求解：递归地求解各子问题。若子问题足够小则直接求解。
3. 合并：将子问题的解合并成原问题的解。

凡是涉及到分组解决的都是分治法，例如归并排序算法完全依照上述 分治算法的3个步骤进行。
1. 分解：将n个元素分成各含n/2个元素的子序列。
2. 求解：用归并排序对2个子序列递归的排序。
3. 合并：合并两个已经排好序的子序列以得到排序结果。

动态规划法

• 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
  若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
• 然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，在需要时在找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否利用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
• 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。当然，最优解可能会有多个，动态规划法能找出其中的一个最优解。

贪心法

和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题上的策略是仅根据当前已有的信息进行选择，而一旦做出了选择，不管将来什么结果，这个选择都不会变。换而言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的的近似最优解。

-贪心法问题一般具备两个重要的性质：
1. 最优子结构：当一个问题的最优解包含其子问题的最优解时，此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
2. 贪心法选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心法选择性质也是贪心法的一个难点。

回溯法

有“通用的解题法”之称，可以系统的搜索一个问题的所有解或任一解。在包含所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树，搜索任一节点时，总是先判断该节点是否肯定不包含问题的解，如果不包含，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯，否则进行该子树，继续按深度优选的策略进行搜索。

可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外一个分支，重复次步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层。一般用于解决迷宫类的问题。

分支限界法

原理：
在分支限界法中，每个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时间为止。

与回溯法的区别：
1. 求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
2. 以广度优先或最小耗费（最大收益）优先的方式搜索解空间树。

从活结点表中选择下一个扩展结点的类型：
队列式（FIFO）分支限界法：按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。
优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点称为当前扩展结点。