算法之旅（1）——认识算法

从今天开始，我将用100期的内容讲解各种计算机领域常用的算法和思路，以及优化方法，主要覆盖图论、模式匹配、快速查找、概率统计、聚/分类、神经网络、分布式算法等。这些内容会有部分概念有重叠，不过总体来说不会漏下重要的内容。今天我们先讲第一讲，认识算法。

算法在很多程序员朋友眼里显得非常神秘，总觉得这种东西很高深，都是要数学大牛才能掌握的东西，其实不然，算法是就是指计算的逻辑和步骤，我们现在说到的算法其实主要是指电子计算机的计算逻辑。我们研究算法的目的也非常简单，那就是希望通过高效率，高准确率的运算逻辑让计算机代替我们人类进行数据处理。

在大量的高级语言和工程框架成型后，我们现在使用成型的算法非常简单。

String a = s.trim();

只要我们用这样一个语句，就可以把s这个字符串左右两端所有的空格都去掉，至于怎么做的，效率高不高我们一般也不会去关心，除非我们发现它在工作中给我们带来了执行效率方面的困扰。

面向对象的封装确实已经屏蔽掉了很多的计算细节，这给我们带来了使用的方便，但是同时也在一定程度上扼杀了高效率程序诞生的环境——当然了，现在的CPU资源一般来说还是足够让我们霍霍的。

对于现在的计算机来说，不管是RISC还是CISC指令集，他们在数据处理上都还是图灵机的模型，那就是存储和指令。或者我们只认为计算机只做两件事，一个就是把某个地址的数据放到哪里去，一个就是把某个地址的数据进行计算，真的就这么简单。关于这个过程，我还是要做一些简单的讲解。

1、进制

我们都知道电子计算机里面的计数都是使用二进制的，这也是没办法的事情，因为第一代电子计算机都是使用二稳态器件来做介质的——真空管，正向导通反向截止，也就是说，每一个计算机最小的技术单位只有两个状态，不是0，就是1。不够怎么办，那就再来一个真空管，再多表示一位喽，以此类推。

人类用十进制原因就是因为人类有10根手指，如果当初人类诞生的时候就是两只手，一手一根手指，那么现在很庆幸，计算机和人类有了统一的进制——二进制，而且毫无违和感。

2、存储

学过汇编语言的同学可能不会陌生，汇编语言都是型如这种

mov 35, 10000000b

这种就几乎是计算机最简单的一个动作了，把一个地方的数据搬移到另一个地方去，比如从CPU寄存器到内存。再小的单位恐怕已没有任何计算层面的意义。

如果再搬移一次，那就还要重新对CPU发一次指令。这样的一次不可再分的指令就是我们粗略地度量计算成本的最小单位。

例如同样一个算法，有的人写出来需要10亿个单位，有的人写出来需要3000万个单位，显然后者效率要高得多。

3、计算

计算机里的计算是一种非常接近人类运算认知的计算方式，什么意思呢——人类首先认识加法，用加法定义减法，用加法定义乘法，用减法定义除法，在用这些去定义乘方开方，微分积分等复杂运算。除非在一些特殊领域，计算单元经过了特殊的优化，可能会有其它的实现方式，否则通用计算机是没有捷径可走的。

使用与、或、与非、或非这些计算单元的计算机，也是用二稳态原件的性质来模拟在二进制状态下的加减进位退位过程完成最简单的加法器，然后再在高层计算机语言中封装成为更为复杂的运算，这就是现在计算机计算的基本原理。不管计算多复杂，请记住，底层肯定还是这些小的与、或单元在那里做电源小铡刀似的开闭动作来做一次一次的加法叠加实现的。

4、I/O

说到I/O，理论上只要是从CPU进行数据出入都应该算I/O操作，只不过现在计算机运算速度很快了，在大多数情况下这种I/O都会被忽略不计。而我们平时说的I/O太大影响效率通常指的是磁盘I/O。

现在主流的机械磁盘在有缓存的情况下和内存的存储效率还是要差至少2到3个数量级，所以一旦由于算法写得不够考究，触发了不必要的磁盘I/O操作，那就会让计算效率大打折扣。这些技巧在我们未来的分享中也会逐渐系统性地进行讲解。

5、算法

最后我们总结一下，说一说算法。

我们所说的算法，就是指一种计算逻辑和步骤，我们通过程序告诉计算机应该定义什么样的存储单元，通过什么逻辑和步骤进行相应的计算最后得到结果，这个就是算法的全部。在这其一我们要考虑的是逻辑正确性；其二考虑的是“时间复杂度”——其中也包括随着数据量增加产生的I/O边界效应。