前面小编陆陆续续讨论了一些较为常见的数据结构及其算法设计，并没有去分析到这些算法属于哪种策略的应用。接下来，小编将探讨下一些经典的算法，包括分治策略、贪心法、动态规划法、回溯算法等，并举一些常用的例子，用代码实现，加以简单分析。我们接下来先来看看何为“分治策略”。
举个例子
小编在阅读国外出版的《计算机算法》一书时，看到一个很赞的例子：“检测假硬币”，这个例子生动的展示了分治策略的方法、步骤等。笔者这里把该例子贴出来下：
“现在袋子中有16个硬币，我们知道其中的一个可能是假的。另外你知道假的硬币比真的硬币轻。你的任务是确定袋子中是否有一枚假的硬币。为了完成这个任务，你可以使用一台仪器来比较两组硬币的重量，并且告诉你那组硬币轻一些或者两组一样重。
我们可以比较硬币1和硬币2。如果硬币1比硬币2轻，那么硬币1是假的，我们也完成了任务。如果硬币2比硬币1轻，那么硬币2是假的。如果两个的重量一样，那么比较硬币3和硬币4。同样，如果其中一个硬币轻一些，就检测出一枚假硬币。如果没有，就比较硬币5和硬币6。一直这么做，可以最多通过八次比较就确定袋子中是否包括假硬币。这个过程同时找出了那枚假硬币。
另外一种做法可以使用分治策略。假设把16个硬币的实例看成是一个大实例。第一步，我们将原始问题分成两个或者更小的实例。让我们将16个硬币的问题分成两个8个硬币的问题，我们的分法是随机选择8个硬币作为第一个实例（称为A）,然后剩下的8个硬币就是第二个实例（称为B）。第二步中，我们需要确定A或B中是否有假硬币。这一步中，我们 比较硬币集合A和B的重量。如果它们的重量不同，那么一定存在假硬币，并且在那个较轻的集合中。最后，在第三步中，我们得到第二步的结论，并用它来回答原始16个硬币的问题。对于假硬币问题，第三步是很容易的。这样通过一次重量比较，就可以完成检测是否存在假硬币的任务。
现在我们假设还需要确定哪个是假硬币。我们定义“小”实例是包括2个或者3个硬币的情况。注意，如果只有一个硬币，那我们无法判断它是不是假的。所有其他的实例都是大的。对于小实例，可以通过比较1枚硬币与其他的1枚或2枚硬币，也就是最多2次比较就可以判断哪个是假硬币。
16个硬币的实例是大实例。所以它被分为了2个8个硬币的实例。比较这两个实例的 重量，我们可以判断是否存在假硬币。如果不存在，算法终止。如果存在，继续那个存在假硬币的实例。假设B是较轻的那个集合。它再进一步被分为2个4硬币的集合。称它们为B1和B2比较这两个集合。其中的一个集合一定更轻一些。如果B1更轻，假硬币就在B1中，然后B2就被分为2个2硬币的集合。称他们为B1a和B2a。比较这两个集合，我们继续处理那个更轻的集合。因为较轻的集合只有两枚硬币，它是一个小实例。比较这个集合里的两枚硬币的重量，可以确定哪个更轻。更轻的就是假硬币。”
许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或者多次的递归调用其自身以解决紧密相关的若干子问题。这其实就是我们经常讲到的分治思想。
分治法的思想
将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时都有三个步骤：
1、分解(Divide)原问题为若干子问题：这些子问题都是原问题规模较小的实例。
2、解决(Conquer)这些子问题，递归的求解各个子问题，若子问题的规模足够小，则直接求解。
3、合并(Combine/Merge)这些子问题的解为原问题的解。
分治法适用条件
1、问题的规模缩小到一定的程度就可以容易地解决；
2、问题可以分解为若干个规模较小的相同问题；
3、利用该问题分解出的子问题的解可以合并为该问题的解；
4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
其中，第2条是分治策略适用的前提条件，也是递归的基本条件；第三条是适用分治策略的关键，能否使用分治策略，完全取决于第三条。
判断分治的条件
并非所有问题都能进行分治，通常我们通过观察问题的输入来获取划分的线索，如：
（1） 一个字符串的部分仍为字符串
（2）一个集合的部分依然是集合
（3） 一棵树去除根节点分成若干子树（树的问题很多用到分治策略，只对根节点进行操作）
（4） 一个图的部分仍是一个图
相对地，我们也可以根据观察问题的输出来判断子问题的解能否组和成复杂问题的解。
分治策略的递推式
我们写一个控制抽象【一个过程，其控制流清晰，但是主要的操作需要由其它过程来定义，从而省略其详细的意义】，其中DAndC是一个函数，其初始调用是DAndC(P)，其中P是待解决的问题。
DAndC函数
Small(P)是一个布尔函数用来判断输入是否足够小可以直接解问题而不需要分割。如果是这样的，那么调用函数S。否则，问题P就被分成子问题。这些子问题P1，P2，...，Pk由递归调用DAndC来解。将k个子问题的解合并成P的解是通过函数Combine来完成的。如果P的大小是n，k个子问题的大小分别是n1，n2，...，nk，那么计算DAndC的时间可以用如下的递归等式来表示：
递归等式1
其中T(n)是对任意大小是n的输入DAndC的运行时间。若问题规模被划分的足够小，即对于某个常量c，n≤c有T(n)=O(1)，这里记g(n)是直接计算小输入所花的时间。函数D(n)是分解问题的时间，合并问题的解为原问题的解需要时间C(n)。假设把原问题分解为a个子问题，每个子问题的规模是原问题的1/b，每个子问题规模设为n/b【这里之所以是n/ b，不是n/a，是因为并非所有问题中n都是被刚好分给所有子实例，各实例之间可能存在交叉数据，例如n分成3份，每份规模n/2，则分别是0~n/2，n/4~3n/4，n/2~n】，那么，为了求解一个n/b的子问题，需要a*T(n/b)来解决a个子问题【a和b为常数，且n=b^k】。
若令f(n)=D(n)+C(n)，那么递归式为：
递归等式2
很多分治算法的复杂度都是如上的形式。
对于上述类型的递推公式，我们有以下结论来对其阶进行估计：首先我们根据f(n)的形式不同分成以下两种不同的情况其中c，d为常数：
（1）f(n)=c
（2）f(n)=c*n^d
一般情况下，有三种方法可以来求解，分别是代入法、递归树法、主定理法。这里我们主要是来看看递推求解的主定理法的一个简单的推导过程。
首先考虑f(n)=c
f(n)=c
对于情况f(n)=c*n^d
f(n)=c*n^d
其实上述结果就是Master定理，用于快速求得均等划分递归表达式的复杂度。使用上述的定理可以快速准确的求解出大多数涉及到时间复杂度求解的程序算法竞赛题。接下来我们再来看看一些利用分治法实现的经典算法，除了用主定理去分析算法的时间复杂度，还将讨论下用递推法、递归树求解时间复杂度的方法。
先分析到这里，有误请指正。
网友评论