循序渐进才能学好算法

设计方法在刚开始第一篇中已经有所提及，下面几章会详细地讲解设计方法。我们要解决一个问题的时候，需要对问题进行分析，那如何通过算法来解决这个问题？适不适合用算法来解决这个问题？该使用什么样的算法来解决？怎么设计？所有我们要考虑的这些就是设计方法要做的，我称他为”设计理念“。

如上图所示，算法的设计理念其实大体分为4个部分：自然求解、大化小、推陈出新、回溯。其实说白了，所有的问题都是在求解最小化问题上。

自然求解

主要是运用计算机本身的运算能力，把一个简单且重复的过程交给了计算机来完成。递推法、递归法、穷举法都是很好的例子。

大化小

在求解一个问题时，会把这个问题分解为若干个小问题，然后对小问题进行求解的过程，这时候就会涉及到全局最优和局部最优的问题。贪心算法、分治法、动态规划、分支界限法是典型的代表。

推陈出新

对一个问题求解，利用旧求解值推算出新求解值的过程。迭代法是最符合这个理念的设计方法。

回溯就不用在这里累述了。

这一章我们先来讲讲自然求解，其实在很早之前就有这样的例子，那就是在二战时破译德军密码的图灵，当时的图灵机就是我们现在计算机的原型，可见对人类来说灾难性的大量计算面前，对于计算机来说非常的轻松。

当一个问题并没有逻辑性且无法从已知条件得出结论，那么我们可以试试穷举法，穷举法就是将所有可能的答案进行列举，然后根据问题中的条件选择合适的答案。这种方法可以获取到正确的答案，但代价就是计算消耗比较高。

举例一：在一个九宫格中放入1-9的数字，任意取出两个数字，这两个数字不能在同一行或是同一列，有多少种取法？注意数字不能有重复。

还有就是面试中经常会遇到的八皇后的问题。

1

2

3

4

5

6

7

8

9

穷举法就是从1开始到9开始列举有多少种方式。

1

1

2

3

4

5

6

7

8

9

结论：15、16、18、19

2

1

2

3

4

5

6

7

8

9

结论：24、27、26、29

3

1

2

3

4

5

6

7

8

9

结论：34、35、37、38

4

1

2

3

4

5

6

7

8

9

结论：48、49

5

1

2

3

4

5

6

7

8

9

结论：57、59

6

1

2

3

4

5

6

7

8

9

结论：67、68

从上面可以看出，一共有18种取法。由于题目中只有9个数字，我们会轻而易举的穷举出所有的方式，那如果不是9个，而是20、30、甚至上百个呢，那要穷举的数量就会非常的庞大，这个时候计算机的计算能力就会派上用场了。利用计算能力超强和速度优势，我们就可以解决一些复杂问题，比如解密，我们可以根据密码的长度和组成成分不同，进行相应的排列组合，列举出所有的可能密码组合，然后进行解密判断，最终获取正确的密码组合。

特点可以找出正确答案效率低，因为很大一部分算力都用在判断错误上。时间复杂度高，在特殊场景可能造成时间崩塌。

在现实生活中遇到问题，其实我们第一个想到的就是穷举法，会列举所有可能的场景来解决问题。穷举对于简单的问题求解还是比较直接、快速。

今天我们讲到这里，下一篇请关注其他的设计方法。