趣学算法【第一章：算法之美】感悟（上）

14天阅读挑战赛

前言

努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！

1、什么是算法，为什么要学习？

其实算法是一个比较模糊的概念，简单来说，算法就是将解决一件事的方法罗列下来。但是我们不光要学习算法，更应该学习好的算法。在职场中好的程序员往往注重数据结构与算法，长期学习算法的他们写出的业务代码总是高性能低消耗且高内聚低耦合的。相反若一个一点算法思维都没有的同学去写业务代码的话如果逻辑稍微复杂一点可能就会写出损耗巨大的代码且耦合度高。因此我们应当学习算法，学习好的算法。

2、在问题中思考如何算法选型与设计

将趣学算法书中的例子来作为参考：

1．问题分析

拿新出生的1对小兔子分析。
第1个月，小兔子①没有繁殖能力，所以还是1对。
第2个月，小兔子①进入成熟期，仍然是1对。
第3个月，兔子①生了1对小兔子②，于是这个月共有2(1+1=2）对兔子
第4个月，兔子①又生了1对小兔子③，因此共有3(1+2=3）对兔子。
第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤，因此共有5(2+3=5)对兔子。
第6个月，兔子①②③各生下了1对小兔子，新生的3对兔子加上原有的5对兔子，这个月共有8(3+5=8）对兔子。

---

为了更直观分析整个过程，书中还有图示：

其实很明显这就是一个斐波拉契数列。不难得出递归表达式：

以此我们就可以写出一段求解的代码了

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

---

回到最初的问题，什么是好的算法？

---

自然应当是消耗资源低的且是正确的，现在我们就来分析分析。
对于递归我们可以使用递归树进行分析

很明显我们可以看出其复杂度为2^n，是一个指数级的爆炸式增长的算法。

---

而对于爆炸增量函数
可能光说本质并不能意识到到底是多大，那么就用书中一个例子来演示一下：

—棋盘的麦子
有一个古老的传说，一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令:“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来，国王一看是个穷小子，想要反悔，说:“除了女儿，你要什么都可以。”小伙子说:“好吧，我只要一棋盘的麦子。您在第1个格子里放1粒麦子，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，以此类推，每一个格子里麦子的粒数都是前一格子里麦子粒数的两倍。把这64个格子放满了就行，我就要这么多。”国王听后哈哈大笑，觉得小伙子的要求很容易满足，满口答应。结果发现，把全国的麦子都拿来，也填不完这64个格子…国王无奈，只好把女儿嫁给了这个小伙子。

棋盘上的64个格子究竟需要放多少粒麦子?
在书中的比喻足以震撼

因此那么这可能就并不是这个算法的最优解了。在下一篇文章我们就来继续分析一下怎样去优化一个如此复杂度的算法。