递归&Master公式

评价一个算法的优劣，时间复杂度应该是最重要的指标，时间复杂度不止可以判断两个算法计算起来用时更短，甚至可以区分这个算法是否是计算机可以解决的。但是如何估计一个算法的时间复杂度有时也不是那么显而易见的，例如递归算法的时间复杂度，其中涉及到系统的压栈和弹栈时间，需要用到本文介绍主项公式来辅助求解。

从算法的时间复杂度说起

我们都知道，虽然时间复杂度这一指标以时间为名，但并不是一个时间单位，其本质是样本量的增长对计算时间的影响。任何一个算法都要有输入和输出，不管输入的数据是一组数还是对象（这不是算法所关心的），所输入的数据的数量称为样本量（n），随着样本量的增长计算时间也会相应的增长，这很好理解；但是，常数级的算法即便样本量增加，计算时间也不会发生变化（听起来似乎不可思议），而线性时间复杂度的算法计算时间的增长和样本量的增长是同等规模的，O(N²)的算法样本量增长9倍，计算时间就要增长99倍……（以此类推）

时间复杂度通常主要由次数和常数项两部分构成，而其中最重要的指标还是最高项的次数，即便常数项较小，但只要最高项的次数高于其他算法，那么该算法随着样本量的增大计算时间总会超过其他算法（将时间复杂度的函数图像画出来就一目明了）。而当两个算法的最高次相同时，就可以通过比较常数项来判断谁的计算时间更长，例如位运算和加减乘除运算都是常数级的时间复杂度，但是位运算的常数项更小，因此许多算法中的x/2通常写作x>>1，2^x通常写作1<<x。

P问题和NP问题

P&NP问题作为千禧年七大数学难题之首，其实质就是在讨论算法的时间复杂度问题，即便是云计算已经如此普及的今天，对于计算机而言一个非多项式复杂度的算法也需要耗费大量的时间，这正是我们如此看重算法时间复杂度的原因（真的等不起）。关于多项式级复杂度，主要包括O(1),O(log(n)),O(n^a)等几种，与之相对的非多项式级复杂度有O(a^n)和O(n!)，这也是P&NP问题的划分标准。

时间复杂度上的差别使得我们在求解这两类问题时的思路截然不同，对于P问题，我们其实可以明确的确定一系列计算步骤来将输入数据一步步转化为输出数据，这也是我们在学习算法过程中最主要练习的部分；但是NP问题，我们不一定能够将其转化为多项式的过程将其解决的。虽然如此，但是NP问题有一个重要的特点，就是我们可以在多项式的时间内验证问题的一个解，因此就可以用递归算法来尝试求解，只要这个算法的样本量有限，就一定能在有限时间内解决这个问题。

递归

学递归的时候老师说，任何递归算法都可以改成非递归的版本，因为递归的实质是系统帮你把分一步计算结果压栈，之后再弹栈，系统方法栈不仅可以将中间结果压栈，同时可以将每一步方法中的参数压栈，功能十分强大。但是，我们在日常学习算法和思考问题的时候总是习惯于从条件到结果的顺序依赖关系，即遇到一个问题时我们习惯于用解决P问题的方式去思考，一旦遇到NP问题就会显得有些束手无策，因此我们要通过学习递归函数的构建来训练如何用计算机的逻辑来思考问题，这也是算法能力很重要的一部分。

写一个递归函数，我们首先要考虑的是递归的终止条件，也叫base case，即样本量一旦小到什么程度，我们就能够用多项式级的算法来解决该问题；确定了终止条件，接下来考虑每一步递归过程中的依赖关系，即最初始的样本量是如何依赖下一级的样本量来得到最终结果的，依赖关系也确定之后，就可以输入初始值开始求解。

这里以著名的汉诺塔问题为例，样本量为n的问题从初始杆借助辅助杆移动到终止杆上。我们将问题抽象一下，我们将前n-1个圆盘看做整体，那么一次递归过程可以分为三个步骤：

1. 将前n-1个圆盘移动到辅助杆上
2. 将第n个圆盘移动到最终杆上
3. 将前n-1个圆盘移动到最终杆上

通过上述三个步骤，我们可以得出，递归的终止条件是当n-1=1时，即剩余的圆盘可以通过一步操作进行移动，就没有必要再对该过程进行划分；而依赖关系则是每一次递归时，n-1这个整体逐渐减小，而三个杆又分别作为源头，目的地和辅助空间进行圆盘的移动，即第一个步骤中辅助杆作为最终n-1个圆盘要到达的“终止杆”，原本的终止杆作为了子过程的辅助杆，而第三步中n-1个圆盘所在的辅助杆成为了子过程中圆盘移动的“初始杆” ，原本父过程中的初始杆成为了“辅助杆”，如下表所示：

划分次数				递归树
n-1=3				左——>右
n-1=2		左——>中				中——>右
n-1=1	左——>右		右——>中		中——>左		左——>右

表中的递归树表示“源点——>终点”，剩余的一个杆作为辅助杆。我们发现，n层汉诺塔问题的递归树展开实际上是一棵深度为n的满二叉树，而汉诺塔的解法则是对这棵树进行中序遍历的过程（似乎我们也可以用建立二叉树的方式来解决汉诺塔问题，将其改为非递归版本有点动态规划的思路），下面是汉诺塔问题的递归代码实现：

public static class Hanoi{
	//三条轴
	int[] left;
	int[] middle;
	int[] right;
	int length;
	public Hanoi(int num) {
		length = num;
		middle = new int[length];
		right = new int[length];
		left = new int[length];
		for (int i = 0; i < left.length; i++) {
			left[i] = i + 1;
		}
	}
	/**
	 * 汉诺塔的解法入口函数
	 */
	public void result() {
		process(left, right, middle, length);
	}
	
	/**
	 * 递归求解汉诺塔的移动步骤
	 * @param from	从哪一个轴上取
	 * @param to	放到哪个轴的顶部
	 * @param help	辅助轴
	 * @param index	要移动的圆盘号
	 */
	public void process(int[] from,int[] to,int[] help,int index) {
		//base case
		if(index==1) {
			move(from, to, index);
		}else {
			//先递归移动n-1个从初始轴到辅助轴
			process(from, help, to, index - 1);
			//再移动第n个从初始轴到目的地轴
			move(from, to, index);
			//最后递归移动n-1个从辅助轴到目的地轴
			process(help, to, from, index - 1);
		}
	}
	/**
	 * 移动圆盘操作
	 * @param from
	 * @param to
	 * @param index
	 */
	public void move(int[] from,int[] to,int index) {
		to[index-1] = index;
		from[index-1] = 0;
		show();
	}
	/**
	 * 打印当前的三根轴的状态，0表示空，大于0表示第几号圆盘在该轴上
	 */
	public void show() {
		System.out.println("------------------");
		for (int i = 0; i < left.length; i++) {
			System.out.print(left[i]+" ");
		}
		System.out.println();
		for (int i = 0; i < middle.length; i++) {
			System.out.print(middle[i]+" ");
		}
		System.out.println();
		for (int i = 0; i < right.length; i++) {
			System.out.print(right[i]+" ");
		}
		System.out.println();
		System.out.println("------------------");
	}
}

最后我们来讨论一下汉诺塔问题的时间复杂度问题，观察我们的递归函数，可以发现每一次递归要对n-1规模的问题再递归两次，同时执行一次常数级的操作（挪动第n个圆盘），表达式为T(N)=2T(N-1)+O(1)，化简一下就会发现这是一个等比数列的展开，利用等比数列的求和公式最终T(N)=2^N-1,因此这是一个时间复杂度为O(2^N)的算法，印证了我们之前所说的汉诺塔问题是一个NP问题。其实观察表格中的递归树我们也可以计算，由于树中的每一个节点都代表一次对圆盘的移动操作，因此满二叉树的总结点的个数为2^N-1。

主项公式

递归行为如何分析时间复杂度，这个问题十分复杂，也并没有通式可以全部解释和涵盖，这里介绍一种最通用的情况下该如何计算，利用主项（master）公式：

T(N)=aT(N/b)+O(N^d)

1. T(N)：样本量为N的情况下递归函数的时间复杂度

2. a：划分后要处理几次子样本（即是否要对划分后的子样本再次递归该函数）

3. b：总体过程在一次递归过程中被划分为了几部分

4. d：除了调用子过程之外的操作复杂度的数量级

   这里的a，b直接通过“数代码”即可确定，即只关心一次递归行为，不用分析整个系统栈（树）的划分过程

这里有三种情况：

1. log(b,a)>d时，T(N)=O(N^log(b,a))
2. log(b,a)=d时，T(N)=O(N^d*log(N))
3. log(b,a)>d时，T(N)=O(N^d)

master公式仅仅适用于子样本的划分大小规模相等的情况，如上文中的汉诺塔问题就不能使用master公式估计时间复杂度。

---