🔝算法学习 【第一周】Ⅱ

一、前言

在上一期博客中我们学习了有关算法复杂性的知识，本期博客我们将通过两个例子去学习一下算法的设计和改进知识。

有些时候解决一个问题，并不是所有的算法都可以，我们需要分析问题对比各种算法然后选择最优算法，在很多编程比赛中就对此有明确的要求，选手需要使用最优算法，尽量把算法复杂性降到最低。

废话不多说，我们开始今天的学习！

二、一棋盘的麦子

这个故事相比大家并不陌生，在高中学习数学的时候老师可能提到过。

故事大致是，传说有个勇敢的小伙子救了国王女儿，然后国王答应将女儿嫁给他，但发现他是一个穷小子，便反悔说除了女儿其他的要求随便提，然后小伙子就说他只需要一棋盘的麦子，在第一个格子里面放1粒麦子，第2个格子里面放2粒麦子，在第3个格子里面放4粒麦子，依次类推，每个格子里面的麦子的粒数都是前一格的两倍，放满64格就行，国王觉得很简单，但最后发现把全国的麦子都拿出来也填不满64个格子，最后只好将女儿嫁给了这个小伙子。

这个故事体现了指数爆炸的情况，我们将其解析成数学问题就是：

棋盘上的64个格子究竟需要放多少粒麦子？

分析可知：S=1+2¹+2²+2³+…+2⁶³

等号两边乘以2，然后再用乘以2的式子减去原始式子得：

S=2⁶⁴-1=18446744073709551615

上网查资料可知，每粒麦子平均重量约41.9毫克，那么总共大概7729000亿千克，这个数字非常夸张。

这样的函数也被称为爆炸增量函数，如果算法的时间复杂度也是这种爆炸增量函数，那么随着未知数的增加，程序就会宕机，无法正常工作，这是我们在选择算法时必须要注意的问题。

常见的算法时间复杂度有以下几类：

1. 常数阶

   也就是算法运算次数是一个常数，其时间复杂度就是O(1)。

2. 多项式阶

   很多算法的时间复杂度都是多项式阶，但我们一般表示时间复杂度时只看多项式的最高项，所以一般时间复杂度就是O(n)、O(n²)、O(n³)等。

3. 指数阶

   绝大部分指数阶的算法运行效率极差，我们在选择算法时就需要避免出现指数阶的时间复杂度，比如O(2ⁿ)、O(n!)、O(nⁿ)等。

4. 对数阶

   对数阶的算法运行效率比较高，比如O($logn$)、O($nlogn$)等。

我们在设计算法时也需要注意算法复杂度增量问题，避免出现爆炸级增量。

三、神奇的兔子数列

这个例子也是一个经典的数学题目。

假设第1个月有1对初生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去，那么，由1对初生兔子开始，12个月之后会有多少对兔子。

这个问题也就是求解斐波那契数列。

我们不难发现，这个兔子数列有一个很明显的特点，那就是从第三个月开始，当月兔子数=上月兔子数+当月新生兔子数，而当月新生兔子数正好又等于上上月的兔子数，也就是当月兔子数=上月兔子数+上上月兔子数。

抽象成递归表达式就是：

如果我们要针对这个问题设计一个算法的话，那肯定选择递归算法。

int Fib1(int n){
	if(n==1||n==2)
	return 1;
	return Fib1(n-1)+Fib1(n-2);
}

当我们写出一个算法之后，我们就需要考虑它的复杂度了，看看它属于哪种算法。

我们分析出该算法的时间复杂度和表达式的关系可以写成：

我们求出斐波那契数列的通项公式：

由于T(n)>=F(n)，所以我们的这个算法是一个指数阶算法，也就是我们常说的暴力递归方法。

指数阶算法是我们需要避免的，所以接下来我们将考虑一下如果将算法进行改进优化，让其复杂度降低。

除了开头两项之外，我们可以发现斐波那契数列中的每一项都是前两项之和，如果记录前两项的值，则只需要一次加法运算就可以得到当前项的值。

int Fib2(int n){
	int *F=new int[n+1];	//定义一个长度为n+1的数组
	// 数组前两项,n=1和n=2
	F[1]=1;
	F[2]=1;
	// n>2
	for(int i=3;i<=n;i++)
		F[i]=F[i-1]+F[i-2];
	return F[n];
}

上述算法的时间复杂度很明显就是O(n)，而且我们将时间复杂度从指数阶降到了多项式阶，效率得到了大大提高。

在上述算法中我们使用了一个辅助数组记录中间结果，其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本就不需要记录，所以我们还可以将算法进行优化改进一下，采用迭代法进行改进。

int Fib3(int n){
	if(n==1||n==2)
		return 1;
	int s1=1;
	int s2=1;
	for(int i=3;i<=n;i++){
		int tmp=s1+s2;
		s1=s2;
		s2=tmp;
	}
	return s2;
}

在这个算法中哦我们使用了几个辅助变量进行迭代，时间复杂度为O(n)，但空间复杂度从之前的O(n)降到了现在的O(1)。

斐波那契数列的时间复杂度还可以通过矩阵乘法降低到对数阶，这个我没有看懂所以在这里也不敢介绍，感兴趣的朋友可以去网上查阅一下，还是比较复杂的，但可以从中学到很多。

四、最后我想说

斐波那契数列的算法设计也是一道经典的编程题目，在很多的刷题网站上面都有，有各种各样的解法，大家可以去看看。

我们学习算法要学习数据结构和算法策略，这两个方向时相互独立的，对于同一个数据对象上不同的问题，就会用到不同的算法策略，一般来说我们在大学里面本科阶段也就学习了数据结构，有关算法策略涉及的很少，所以后面我会继续学习这本书然后更新有关算法策略的知识，谢谢支持！