计算的本质与如何寻找最好的算法

这篇博客的题目和写作动机都来自于吴军博士的《计算之魂》，我只是在此梳理下自己的理解，同时这篇文章所讲内容就像书中引言所讲的那种，偏向于“道”的层次，有种学生时期做题到一定程度之后，慢慢有了一定的比较玄的所谓的题感的意思。吴军博士在书中将这种感觉称为一个程序员对计算的“品味”，对于已经站在门槛上有了感觉但是说不清的程序员来讲，会有种醍醐灌顶的感觉。

博客篇幅有限，先梳理下计算的本质与如何提高算法性能。

计算的本质

什么是计算机

计算机科学史专家们认为，最早的计算机是中国的算盘，虽然同时期的希腊也有自己的算盘，但是希腊的算盘并没有被史学家们认为是计算机，而只是辅助计算的工具。

二者的差别在于哪里呢？古希腊的算盘实际上是使用一些小石珠或者铜珠在计算过程中帮忙计数的，也就是它有存储功能，但是计算这个功能还是靠人动脑筋的，这种计算过程和用纸笔算没有区别，因此它只是辅助计算工具。而中国的算盘不一样，中国的算盘是靠一套珠算口诀来操作的，而不是心算，在中国，真正会打算盘的人，都不用动脑筋心算的，也就是说，使用中国算盘，人提供的只是机械动能，而不是头脑的运算能力。

从算盘的设计和使用上可以看出构成计算机的三个要素，计算单元，存储单元，再加上控制它的指令序列。没有指令序列，计算机就不完整，中国和希腊的算盘差异就在这里。任何能计算，有存储能力，受指令控制的机器都可以被算作计算机。

机械计算机，布尔代数和开关电路

算盘的指令存储和执行很简单，但还是由人来完成的，并且学会这门技艺并不简单，因此，人们自然会去想要发明不需要训练也能使用的机器。

1642年，法国数学家布莱兹帕斯卡发明了最早的机械计算机，它可以进行加减法，使用者只要拨动有刻度的旋钮，然后摇动操纵杆，就可以完成计算，相比算盘，帕斯卡机械计算机的优点在于使用者不需要训练，但是不足之处在于，计算之前输入数据太慢，导致整个计算过程太慢。

这个其实反映了计算机发展过程中一直存在的一个大问题，就是数据输入和输出的速度远远跟不上计算的速度。

后面也有巴贝奇和阿达制造出了能进行微积分运算的机械计算机，也是通过齿轮的转动来实现的。

巴贝奇和阿达的想法非常好，即采用程序控制物理运动实现计算，这其实就是计算机的本质。不过他们在实现想法的时候陷入了一个误区，那就是用复杂方法解决复杂问题，随着需要计算的精度越来越高，他们的机械计算机的设计也越来越复杂，超过了人类思考的极限与制造工艺的极限。

带领大家走出死胡同的是英国数学家乔治·布尔，美国科学家克劳德·香农和德国工程师康德拉·楚泽。

布尔的贡献在于通过二进制将算数和简单的数理逻辑统一了起来，并且为大家提供了一个工具，即布尔代数。楚泽通过自己的实践证明了，布尔代数可以实现任何的十进制计算，并实现复杂的控制逻辑。香农则从理论上指出任何逻辑控制和计算都和开关电路等价，奠定了今天数字电路设计的基础。

香农没有像巴贝奇那样，试图靠设计更复杂的计算机来解决更复杂的计算问题，而是在看到分析仪都到死胡同的时候，退回到计算这个问题的本源，开始用简单的方法解决复杂的问题。

香农发现，加减乘除各种运算都可以用很多个基本的逻辑电路搭建出来，就如同用乐高积木搭建出一个复杂的房子一样，也就是说，香农在布尔代数和算术运算之间搭起了一座桥梁，这算桥梁就是逻辑电路。

香农的电路设计思想可以被总结为“模块化”和“等价性”。

所谓的模块化就是用少量简单的模块搭建出各种复杂的功能，这是今天计算机行业的核心指导思想，比如超算。所以很多学者讲，超算其实从计算机科学的角度看，水平并没有什么突破，更多的是工程上的成就。

模块化的思想是的计算机产业和其他工业相比有很大的不同，一般的工业产品有大量形状和功能各不相同的组成部分，但是在计算机产品种，常常是大量相同模块的重复，这就是IT行业能够快速发展，适用范围广泛以及摩尔定律能够成立的重要原因。

计算机和IT产品容易通过模块化实现的一个重要原因是等价性，即再复杂的计算都可以等价成很多的加减乘除运算，再进而等价成开关电路的逻辑运算。

图灵机：计算的本质是机械运动

在20世纪30年代中期，图灵就开始思考下面三个非常根本的问题：

1. 数学问题是否都有明确的答案
2. 如果有明确答案，是否可以通过有限的计算得到答案
3. 对于那些有可能在有限步骤计算出来的数学问题，是否有一种假想的机器，它不断运动，最后当它停下来的时候，这个数学问题就解决了

图灵在读了冯诺依曼的《量子力学的数学基础》后很受启发，他认为人的意识是基于不确定性原理的，但是计算则基于机械运动（电子运动可以被认为是等价于机械运动）。今天我们知道，前者是不确定性，后者是确定性，它们都是这个世界固有的特性。

图灵很懂得在边界里做事情，他把注意力放到了那些能够通过机械运动解决的问题，即可计算的问题上。

那什么问题是可计算的呢？图灵从著名的数学家希尔伯特那里得到了启发，希尔伯特一直在思考这样的三个问题：

1. 数学是完备的吗？所谓完备性，就是说对于任何一个命题，要么可以证明它是对的，要么可以证明它是错的。
2. 数学是一致的吗？所谓一致性，就是说一个命题不能既是真的，又是假的。
3. 数学是可判定的吗？所谓可判定性，就是说一个具体的问题，你能否判断它是否有答案。

希尔伯特的三个问题从本质上划定了数学的边界，因为数学只能解决那些在数学上是完备的问题，而数学的一致性保证它没有似是而非的答案。当然这三个问题希尔伯特也没有答案，后来的哥德尔的理论告诉我们，世界上有很多问题我们无法判断其对错，因此其不是数学问题。

对比希尔伯特和图灵的三个问题可以看出，前者关心的是一个问题是否是数学问题，如果是，能否判断其有答案，而后者关心的是，如果一个问题已经是数学问题了，能否在有限的步骤种找到答案。

图灵也不知道自己问题的答案，所以他把精力放在了那些能够在有限步骤内计算出来的数学问题上，为此，他设计了一种被后世称为图灵机的数学模型，这个模型的定义一共有四条：

1. 要有一条无限长的被分成一个个格子的纸带，每个格子记录着符号或数字。
2. 有一个读写头，可以在纸带上左右移动，它停在那里就可以改变哪里的符号或数字
3. 有一套规则表，根据图灵机的当前状态和读写头所指格子中的符号或数字，人们查表后就知道下一步该做什么，当然完成这一步操作后，图灵机也进入了新的状态。
4. 图灵机的状态需要记录在一个地方，即寄存器种。图灵机的状态数量是有限的，其中一个特殊状态是停机，一旦进入这个状态，则表明计算完成。

图灵机和有限状态机都是计算模型，用于描述和理解计算过程。但是，它们的能力和使用场景有显著的区别。

相同点：

都是抽象的计算模型，用于理解和描述计算过程。
都有一个定义良好的状态集合，可以根据输入从一个状态转移到另一个状态。
不同点：

计算能力：有限状态机只能执行有限的计算，而图灵机能执行任何可以由算法表述的计算，包括那些不能被有限状态机完成的计算。这是因为图灵机有无限的存储空间，而有限状态机的存储空间是有限的。
存储：有限状态机没有存储能力，或者说它的存储能力被限制在有限的状态中。图灵机则有一个无限的纸带或存储空间，它可以在这个纸带上写入或读取信息。
应用场景：由于其计算能力的限制，有限状态机通常用于设计简单的系统，如电梯控制系统，交通灯控制系统等。而图灵机则是用来描述和设计更复杂的计算任务，如编程语言，操作系统等。

怎样寻找最好的算法

例题：总和最大区间问题

给定一个实数序列，设计一个最有效的算法，找到一个总和最大的区间。

解决这个问题有四个不同的方法，我们复杂度从高到低来讲。前两种很容易想到，就简单介绍下，我们主要讲后两种

方法一

首先复杂度最高的就是三重循环，假设我们区间的起点和终点的索引分别是p和q，那么我们需要通过两重循环遍历所有p和q的组合，然后每种组合中，我们需要遍历p和q之间所有的数字进行加和，假设为S(p,q)，这就是$O(N^3)$

方法二

方法一种我们可以感觉到有很多重复的计算，因为如果我们知道了S(p,q),再求S(p,1+1)的时候就不需要再把所有的数加一遍了，减少了一次循环。

有的人可能会担心这种算法需要记录下所有的中间结果S(p,q)，其实我们有多种思路可以避免这个问题，

一种方案是通过前缀和的思路，先遍历一遍获取前缀和数组，然后通过双重循环比较出最大区间

另一种方案理解起来稍微复杂一点，对于每一次外层循环，即p确定情况下，我们只需要记录三个中间值：

1. 从p开始到q位置的总和S(p,q),用于计算S(p,q+1)
2. 第二个是从p开始到q为止所有总和中最大的那个值，假设为Max，有了这个值之后，如果S(p,q+1) <= Max,则Max维持不变，否则更新Max
3. 第三个需要记录的就是区间结束的位置，不妨以r来表示，如果Max更新了，相应的区间结束位置也要更新为q+1。

最后每次内层循环结束后，如果Max更新了，可以更新最后的结果。

这样一来，算法的复杂度就降低到了$O(N^2)$

方法三

我们还可以采用分治算法来解决这个问题，假设我们将序列一分为二，分成1到$\frac{k}{2}$，以及$\frac{k}{2} + 1$到k，然后对两个子序列分别求其总和最大的区间，接下来有两种情况：

1. 前后两个子序列的总和最大区间之间没有间隔，也就是说前一个子区间的综合最大区间是[p, k/2],后一个综合最大区间是[k/2 + 1, q]，如果两个区间各自的和都为正数，那么此时整个序列总和最大区间就是[p, q]，否则就选取两个子序列中大的那个。
2. 如果前后两个子序列总和最大区间之间有间隔，我们假定分别为[p1, q1], [p2, q2]，那么整个序列总和最大区间是下面三者中最大的那一个：

• [p1, q1]
• [p2, q2]
• [p1, q2]

那么为什么不能是[p1, p2],[q1, p2],[q1, q2]呢？

我们简单解释下[p1, p2]为什么不可能，这里建议大家在纸上画个数轴理解下，数轴上从左到右有五个点，分别是，p1, q1, k/2, p2, q2

因为[p1, q1]是前半段最大的，所以[p1, q1] > [p1, k/2]的，而[p1, k/2] = [p1, q1] + [q1 + 1, k/2]，所以[q1 + 1, k/2] < 0，同理，[k/2 + 1, p2 - 1] < 0，所以[q1 + 1, p2] < 0，所以[p1, p2] = [p1, q1] + [q1 + 1, p2] < [p1, q1]

那么子序列又如何求和呢？继续递归，把每个子序列当作完整的序列处理，再拆分为两个子序列就好。这种递归复杂度是$O(logk)$，每次递归的复杂度为O(k)，所以总体的复杂度降低到了$O(klogk)$

方法四

这种方法是在方法二的基础上的改进，在方法二中，我们事先设定区间的左边界p，在此条件下确定总和最大区间的右边界q，然后再改变左边界，遍历所有的可能性。

但是这种方法实际上已经在无形中找到了总和最大区间的右边界，我们从这个角度出发，寻找一下线性复杂度，即O(k)的算法，步骤如下：

1. 现在序列中找到第一个大于0的数字，如果这个数字不存在，即所有的数字都是非零既负，那么整个序列中最大的数就是要找的区间，这时算法的复杂度为O(k)。因此，我们可以不失一般性地假设第一个数字为正数（因为如果第一个数字不为正，就直接从头部删除，如此反复，直到第一个数字为正）
2. 使用类似方法2中的做法，先把左边界固定在第一个数，然后让q=2，3，5…k，计算S(1, k), 以及到目前为止最大值Maxf和达到最大值的右边界r。
3. 如果对于所有的q，都有S(1, q) >= 0，或者存在某个$q_0$，当$q>q_0$时，上述条件满足，这个情况比较简单，当扫描到最后，即q=k时，所保留的那个Maxf所对应的r就是我们要找的区间右边界。为什么呢？因为无论起点q在哪里，从r+1开始，无论有边界在哪里，都会导致区间和变小，所以右边界不可能往后延长了。这个比较好理解，因为S(p, r) 是最大的，所以任意一个S(r+ 1, m)，m取值从r+1到k，都是负的，而且这一点与p在哪里无关。

现在我们找到了右边界，但是我们还没有找到左边界，因为上述过程只是保证了，任意一个S(r+ 1, m)，m取值从r+1到k，都是负的，并没有保证此时的p一定是区间和最大的左边界。其实这个时候，我们使用逆向思维，从后往前计算运用上述三个步骤，得到的就是左边界l，及其最大值Maxb了，同理我们可以证明任意S(m, l - 1)都是负的。

上述过程其实有一点问题，即前提是如果对于所有的q，都有S(1, q) >= 0，或者存在某个$q_0$，当$q>q_0$时，如果在数组中间部分突然出现一个非常大的负数，假设为v，导致从这里开始，后续的S（1， q）都是负的，而其实区间和最大的区间在这个非常大的负数后面的区间中，上述的算法就会出错，具体表现就是我们会把左边界找到v的右边，右边界找到v的左边。

此时我们需要稍微改进我们的算法的步骤2和3

改进后的步骤：
步骤2. 先把左边界固定在一个大于0的位置，假设为p，然后让q=p,p+1,…k,计算S(p,q),以及到目前为止最大的Max和达到Max的右边界r，如果我们算到某一步S(p,q)<0时，反向计算Maxb，并确定了从1到q个数之间和最大的区间，假定为$[l_1, r_1]$，这个区间的和为$Max_1$
步骤3. 我们继续从q+1往后扫描，重复上述过程，找到第一个大于0的元素p’,开始做累加操作，直到又出现S(p’, q’)<0的情况，这个时候我们得到了第二个局部和最大的区间$[l_2, r_2]$，相应的和为$Max_2$

现在我们需要确定从头开始到q’的和最大区间了，我们只需要比较，$Max_1,Max_2, Max_1 + Max_2 + S(r_1 + 1, l_2 -1)（也就是S(l_1, r_2)）$这三个数值就行。

我们直观上可以先否定掉最后一种情况，因为如果可以跨越这个特别小的负数的话，那么我们就没必要费这么大劲了，不过我们还是要证明下

因为$[q + 1, l_2 - 1]$之间的每一个数都小于0，所以$S(q+1, l_2 - 1) \lt 0$

同时由于，$S(l_1, r_1) + S(r_1 + 1, q) = S(p, r_1) + S(r_1 + 1, q) = S(p,q) \lt 0$

结合上述两个式子可得：$Max_1 + S(r_1 + 1, l_2 - 1) = S(l_1, r_1) + S(r_1 + 1, q) + S(q + 1, l_2 -1) < 0$，也就是$S(l_1,r_2) = Max_1 + Max_2 + S(r_1 + 1, l_2 - 1) < Max_2$

步骤4. 继续采取步骤三的方法，不断向后扫描得到一个个局部和最大的区间和相应的部分和$Max_i$，比较Max和$Max_i$，决定是否更新结果。

如何建立计算机科学的感觉

在计算机科学领域，从一个能解决问题的人，上升到一个能够找到最佳解决方案的人，需要培养对计算机科学的感觉。对于这个问题，有经验的从业者一开始就大致能够判断出它一定有优于平方复杂度的解法。这样他们才会朝这个方向努力，那么这种感觉如何建立呢？

1. 首先是对一个问题边界的认识，在这道题种，我们知道至少要扫描一遍序列，因此不可能低于线性复杂度
2. 其次，在计算机科学中，优化算法的最常用的方法就是检查一种算法是否在做大量的无效计算或者重复计算。
3. 需要逆向思维，有些问题正着思考很难，但是逆向很简单，也要熟练掌握计算机的算法思维，掌握每种算法思想的本质是在做什么，什么情况下适用，比如分治思想就是和把大问题拆解成相同的规模更小的子问题。