算法真有那么神秘？

05-08

很多人认为，算法是数学的内容，学起来特别麻烦。我们不能认为这种观点是错误的。但是我们也知道，软件是一种复合的技术，如果一个人只知道算法，但是不能用编程语言很好地实现，那么再优秀的算法也不能发挥作用。
有一次，一个人问我：“你写的都是小儿科的东西，几十行代码就能搞定，能不能整一点高深的算法?”
我反问他什么是他所理解的高深的算法，他答复说：“像遗传算法、蚁群算法之类的。”于是我给了他一个遗传算法求解0-1背包问题的例子，并告诉他，这也就是几十行代码的算法，怎么理解成是高深的算法?他刚开始不承认这是遗传算法，直到我给了他Denis Cormier公开在北卡罗来纳州立大学服务器上的遗传算法的源代码后，他才相信他一直认为深不可测的遗传算法的原理原来是这么简单。
还有一个人直言“用三个水桶等分8升水”之类的问题根本就称不上算法，他认为像“阿法狗”那样的人工智能才算是算法。我告诉他计算机下棋的基本理论就是博弈树，或者再加一个专家系统。但是他认为博弈树也是很高深的算法，于是我给了他一个井字棋游戏，并告诉他，这就是博弈树搜索算法，非常智能，你绝对战胜不了它（因为井字棋游戏很简单，这个算法会把所有的状态都搜索完）。我相信他一定很震惊，因为这个算法也不超过100行代码。
对于上面提到的例子，我觉得主要原因在于大家对算法的理解有差异，很多人对算法的理解太片面，很多人觉得只有名字里包含“XX算法”之类的东西才是算法。而我认为算法的本质是解决问题，只要是能解决问题的代码就是算法。
一个人只有有了很好的计算机知识和数学知识，才能在算法的学习上不断进步。不管算法都么简单，都要自己亲手实践，只有不断认识错误、不断发现错误，才能不断提高自己的编程能力，不断提高自己的业务水平。
其实任何算法都有自己的应用环境和应用场景，没有算法可以适用于所有的场景。这一点希望大家明白。同时，我们也要清楚复杂的算法都是由普通的算法构成的，没有普通的算法就没有复杂的算法可言，所以复杂变简单，由大化小，这就是算法分治递归的基本思想。
我们可以下面一个数组查找的函数说起。一句一句讲起，首先我们开始从最简单的函数构造开始：

1. int find(int array[], int length, int value)
2. {
3. int index = 0;
4. return index;
5. }

复制代码

这里看到，查找函数只是一个普通的函数，那么首先需要判断的就是参数的合法性：

<div align="left">1. static void test1() </div><div align="left">2. { </div><div align="left">3. int array[10] = {0}; </div><div align="left">4. assert(FALSE == find(NULL, 10, 10)); </div><div align="left">5. assert(FALSE == find(array, 0, 10)); </div><div align="left">6. } </div>

复制代码

这里可以看到，我们没有判断参数的合法性，那么原来的查找函数应该怎么修改呢?

<div align="left">1. int find(int array[], int length, int value) </div><div align="left">2. { </div><div align="left">3. if(NULL == array || 0 == length) </div><div align="left">4. return FALSE; </div><div align="left">5. </div><div align="left">6. int index = 0; </div><div align="left">7. return index; </div><div align="left">8. } </div>

复制代码

看到上面的代码，说明我们的已经对入口参数进行判断了。那么下面就要开始写代码了。

<div align="left">1. int find(int array[], int length, int value) </div><div align="left">2. { </div><div align="left">3. if(NULL == array || 0 == length) </div><div align="left">4. return FALSE; </div><div align="left">5. </div><div align="left">6. int index = 0; </div><div align="left">7. for(; index < length; index++){ </div><div align="left">8. if(value == array[index]) </div><div align="left">9. return index; </div><div align="left">10. } </div><div align="left">11. </div><div align="left">12. return FALSE; </div><div align="left">13. } </div>

复制代码

上面的代码已经接近完整了，那么测试用例又该怎么编写呢?

<div align="left">1. static void test2() </div><div align="left">2. { </div><div align="left">3. int array[10] = {1, 2}; </div><div align="left">4. assert(0 == find(array, 10, 1)); </div><div align="left">5. assert(FALSE == find(array, 10, 10)); </div><div align="left">6. } </div>

复制代码

运行完所有的测试用例后，我们看看对原来的代码有没有什么可以优化的地方。其实，我们可以把数组转变成指针。

<div align="left">1. int find(int array[], int length, int value) </div><div align="left">2. { </div><div align="left">3. if(NULL == array || 0 == length) </div><div align="left">4. return FALSE; </div><div align="left">5. </div><div align="left">6. int* start = array; </div><div align="left">7. int* end = array + length; </div><div align="left">8. while(start < end){ </div><div align="left">9. if(value == *start) </div><div align="left">10. return ((int)start - (int)array)/(sizeof(int)); </div><div align="left">11. start ++; </div><div align="left">12. } </div><div align="left">13. </div><div align="left">14. return FALSE; </div><div align="left">15. } </div>

复制代码

如果上面的代码参数必须是通用的数据类型呢?

<div align="left">1. template<typename type> </div><div align="left">2. int find(type array[], int length, type value) </div><div align="left">3. { </div><div align="left">4. if(NULL == array || 0 == length) </div><div align="left">5. return FALSE; </div><div align="left">6. </div><div align="left">7. type* start = array; </div><div align="left">8. type* end = array + length; </div><div align="left">9. while(start < end){ </div><div align="left">10. if(value == *start) </div><div align="left">11. return ((int)start - (int)array)/(sizeof(type)); </div><div align="left">12. start ++; </div><div align="left">13. } </div><div align="left">14. </div><div align="left">15. return FALSE; </div><div align="left">16. } </div>

复制代码

此时，测试用例是不是也需要重新修改呢?

<div align="left">1. static void test1() </div><div align="left">2. { </div><div align="left">3. int array[10] = {0}; </div><div align="left">4. assert(FALSE == find<int>(NULL, 10, 10)); </div><div align="left">5. assert(FALSE == find<int>(array, 0, 10)); </div><div align="left">6. } </div><div align="left">7. </div><div align="left">8. static void test2() </div><div align="left">9. { </div><div align="left">10. int array[10] = {1, 2}; </div><div align="left">11. assert(0 == find<int>(array, 10, 1)); </div><div align="left">12. assert(FALSE == find<int>(array, 10, 10)); </div><div align="left">13. } </div>

复制代码

最后，我们总结一下：
（1）我们的算法需要测试用例的验证
（2）任何的优化都要建立在测试的基础之上
（3）测试和代码的编写要同步进行
（4）算法的成功运行时一步一步进行得，每一步的成功必须确立在原有的成功之上。
相关阅读：

果然很神秘

上一篇：4G已成过去时 5G时代来临
下一篇：LTE常见干扰频谱图大盘点

射频专业培训教程推荐