何谓算法

何谓算法

之前反复说过，要处理的数据越大，算法和数据结构的选择对速度的影响也就越大。首先看个简单的例子。假设要从数据中使用线性查找（Linear Search），从头开始依次查找所需数据，那么如果有1000条数据，那就需要反复查找数据直至找到为止，这个算法最多要进行1000次查找。对于n条数据要进行n次搜索，因此称为O(n)算法。

而“二分查找”（binary search）算法能在log n次之内查找n条数据，是O(log n)算法。使用二分查找，1000条数据最多只需10次就能查找完。

这个“最大查找次数”可以大致判断计算次数，称为复杂度。一般来说，复杂度越低，算法就越快。

n=1000时，O(n)的最大查找次数为1000，而O(log n)为10，计算次数差距为990。n再大些会怎样呢？若是100万条数据，O(n)需要100万次，而O(log n)只需20次。即使是1000万条，O(log n)也只需24次。很明显，与O(n)相比，O(log n)更能承受数据量的增加。

请以大规模数据为前提思考一下。数据量较小时，即使使用O(n)这种简单算法，计算量也不会太大，因此没什么太大问题。但随着数据量的增加，算法选择的差异就越来越大。在数据搜索处理中，使用线性查找的话，数据量增大到1000条、100万条、1000万条时……显然会成为瓶颈。而解决该瓶颈的方法就是选择复杂度更低的查找算法，这也是不言而喻的。

讲述Hatena的服务之前，首先了解一下算法的基本思路吧。

“算法”是什么？重新来考虑一下。根据《アルゴリズムイントロダクション 改訂2版 第1巻 数学的基礎とデータ構造》^[1]（近代科学社、2007年），算法（algorithm）就是明确定义的（well-defined）、以某个值或值的集合为输入（input）、以某个值或值的集合为输出（output）的计算步骤。

——引用自《アルゴリズムイントロダクション 改訂２版 第１巻 数学的基礎とデータ構造》（Thomas H.Cormen/Charles E.Leiserson/Ronald L. Rivest/Clifford Stein著、浅野哲夫/岩野和生/梅尾博司/山下雅史/和田幸一译，近代科学社，2007年）第5页

输入适当的值，通过明确定义的计算步骤得到输出值，这就是算法。将要查找的数据和被查找的数据作为输入进行查找，得到要查找的数据所在的位置，这就是“查找算法”。

 

狭义算法和广义算法

算法这个词具有狭义和广义两种含义，用途很广泛。

从数据库提取记录进行适当处理后输出成报表，对于这种平时随手就能写出的程序，也可以说“用的是什么算法？”这时提问者想知道的应该是处理（domain logic）的流程。这就是算法的广义含义。

而算法的狭义含义，大多是指“针对明确定义的计算问题，执行已定义的计算步骤”。因此，市面上的算法书并不是讲述业务应用程序的处理逻辑，而是讲述排序、搜索、散列等计算问题的解法的。

第7章的内容就是狭义的算法。

——计算机资源有限，工程师的通用语言

CPU、内存等计算机资源是有限的，因此学习算法十分重要。对于必须解决的问题，如何利用有限的资源解决掉，这种思考方式也是必须学习的。

而且，与设计模式同样，算法也是工程师们的通用语言。要用“使用散列就能解决了”这种语言来沟通，双方都需要正确理解散列算法是什么。

学习算法显而易见的好处就是，理解算法后就（可能）可以解决新的问题。

例如学习贝叶斯过滤器（Bayesian Filter）之后，就可以编写数据自动分类之类的程序。利用该算法可以编写垃圾邮件过滤器。

有了能用几MB的容量保存几亿条数据的数据结构，就能轻松发布由于过大而很难发布的程序。如前一阵子发布的Google日文输入法^[2]就用LOUDS这种数据结构将字典数据压缩到50MB左右，这样就能发布巨大的字典。

而且如前所述，面对大规模数据时，算法特性会对应用程序的性能产生巨大影响。学习算法对于把握这种感觉也很有帮助。

为什么算法知识是必要的？

— 计算机资源有限

— 工程师们的通用语言

— 理解算法后（也许）可以解决新问题

 

本文节选自《大规模WEB服务开发技术》一书

图书详细信息:http://blog.chinaunix.net/space.php?uid=13164110&do=blog&id=2211482