摘要：本文将讲解计算机科学中的算法（algorithm），从算法是什么，到使用C语言展示好的算法与坏的算法的例子，目的是让大家对算法有一个清晰的了解。

一 算法与程序的区别

算法是一种抽象的描述，是计算机使用的，对于可解决问题的解法的描述。其特点是对于任何的输入都会返回正确的解，且必须有终点，即必须结束。

而程序，则是对计算机语言的记录。其根据输入的不同而可能会返回错误的解，或因为错误的输入而陷入死循环，永远不会停止。

二 好的算法与坏的算法

好的算法，应该能够适应多种可能出现的输入情况，而且在设计时要考虑到计算时间，运行内存占用等等。好的算法的正确性应该能够被验证与证明。

坏的算法，则可能在编写过程中，无法解析算法的下一步动作，也可能是在试着运行的时候，发生bug，或是不知为何运行缓慢，抑或是不知是否还能继续运行。

三 例题 求最大收益方法

现有一支股票，如何购买股票与卖出股票才能获得最大收益？股票收益如下图所示，这张图展示了同一支股票在十二个月份中的不同价格。

[uploadedimage:17891136]

3.1
我们首先将抽象问题进行简化与定义。既然要获得最大收益，那我们应该在低价时买入，并在高价时卖出，我们的收益就是高价减去低价的钱。没有人会高价买入，低价卖出，这不就是赔本买卖了吗。所以求最大收益问题即求两个时期的股票价格所相差的最大值。

现在，定义问题中的变量：

int sp[n] 这个数组用于存放股票不同时期的价格，n代表月份，例如sp[0]为89年12月的股票价格，而sp[10]为90年十月的股票价格。

在i的时候买入股票并在j的时候卖出股票，也即在i月份买入股票的花费为sp[i]，在j月份卖出股票所获得的钱为sp[j]，我们通过炒股所得到的利益是两个月份的股票价格相减，即sp[j]-sp[i]，我们的问题也即求sp[j]-sp[i]的最大值，max{sp[j]-sp[i]|0<=i<j<n}。

请注意，这里的i要小于j，因为我们只能先买了股票才能再去卖股票，如果我们没有买的话，那就没有要卖的东西。

3.2
现有两种方法

方法A：固定买的时机
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
求所得利益，即sp[j]-sp[i]，记录最大值并进行更新检查

用自然语言描述就是，假设我们在1月份买入股票，之后用2月到11月股票的价格去减买入股票所花的钱，所获得的10个值里面最大的值就是我们获得的最大利益。然后进入循环，继续假设我们在2月份买入，假设在3月份，假设在4月份......

方法B：固定卖的时机
for(j=1;j<n;j++)
for(i=0;i<j;i++)
求所得利益，即sp[j]-sp[i]，记录最大值并进行更新检查

用自然语言描述就是，假设我们在10月将股票卖出，之后用卖股票赚的钱去减89年12月到90年9月这十个月的股票的价格，所获得的10个值里面最大的值就是我们获得的最大利益。然后进入循环，继续假设我们在11月卖出......

3.3
方法A

请思考，以下算法是否高效。

最大收益(sp[],n){
mxp=0;//收益最大值
for(i=0;i<n-1;i++){
for(j=i+1;j<n;j++){
d=sp[j]-sp[i];//出售后的所得收益
if(d>mxp)
mxp=d;//更新最大收益的记录
}
}
return mxp;
}

在以上的算法当中，i被固定的话，sp[i]也随之确定，如果要获取到最大的收益，那么sp[j]一定是i月份以后的最大值，那么是否有必要每一次循环都计算一次sp[j]-sp[i]？

方法A的改良

最大收益(sp[],n){
mxp=0;//收益最大值
for(i=0;i<n-1;i++){
mxsp=sp[i];
for(j=i+1;j<n;j++){//i以后股票的最大价格mxsp
if(sp[j]>mxsp)
mxsp=sp[j];
}
d=mxsp-sp[i];//减运算放在第二层for循环外
if(d>mxp)//比较运算也放在第二层for循环外
mxp=d;
}
return mxp;
}

用自然语言描述就是，假设我们1月份买入股票，我们在剩下的月份里寻找一个最大值，用赚得的钱的最大值减去我们买入股票花的钱，即是我们的最大收益。这样，就可以减少减运算与比较运算的次数，那么我们将相同的优化方法运用在方法B上。也即，假设我们在10月份卖出股票，那么只要在前面的月份当中寻找最小值，卖出股票赚的钱减去花费的钱的最小值，即是我们的最大收益。

3.4
方法B（已改良版）

最大收益(sp[],n){
mxp=0;//收益最大值
for(j=1;j<n;j++){
mnsp=sp[j];//股票到j为止的最小价格mnsp
for(i=0;i<j;i++){
if(sp[i]<mnsp)
mnsp=sp[i];
}
d=sp[j]-mnsp;
if(d>mxp)
mxp=d;
}
return mxp;
}

3.5
让我们来看一下A的运行次数

[uploadedimage:17891146]

以及B的运行次数

[uploadedimage:17891147]

两个方法的运行次数都是n2/2，因为时间复杂度只考虑数量级不考虑系数，所以两种方法的时间复杂度都是O(n2)。虽然我们采用了办法来减少计算机的运算量，但是算法整体的时间复杂度并没有减少，那么有没有办法能够减少复杂度呢？

答案是有的。让我们回到B方法的实现代码上。

最大收益(sp[],n){
mxp=0;//收益最大值
for(j=1;j<n;j++){
mnsp=sp[j];
for(i=0;i<j;i++){
if(sp[i]<mnsp)
mnsp=sp[i];
}
mnsp代表的是到j为止的最小值。假设j=k时，循环完成后，mnsp是sp[0]到sp[k-1]之间的最小值，之后j=k+1的时候，mnsp也会是sp[0]到sp[k]之间的最小值。也就是说，将到现在为止的最小值设置为msf的话，下一次循环，也即加入了新的一个月份的循环，的最小值就是msf与新的月份的sp[k]的最小值进行比较后，较小的那一个。也即，MIN[0,j]=min(MIN[0,j-1],sp[j])。

用自然语言描述这个过程，就是我们假设3月，124的时候卖出该股票，那么在循环的时候就找到了在89年12月到90年2月期间最小的股票的价格，12月的134。这个时候我们进行下一次的循环，假设在四月卖出股票，那么只需将3月的124与12月的134进行对比，更小的那一方，也即3月的124是12月到3月期间，这个循环当中的新的最小值。

用更简洁的语言描述这个过程，即现有一个装着若干球的袋子，已知里面最轻的球是3kg，现放入一个6kg的球，袋子里最轻的球是多少？显然还是3kg。那如果放入一个1kg的球呢？最轻的球就变成了1kg，因为我们将这个1与3进行了对比，更小的那一个才能荣获最轻的球的称号，以上的算法同理。

3.6
这个想法非常不错，但是它是否适用于方法A呢？我们是否可以用上一次运算中获得的最大值，来当作新的最大值呢？

答案是不可以，因为调查的范围变狭窄了。

使用本题的题干进行举例：我们如果在3月份买入股票，那么之后的几个月份当中，股票的最大值是5月份的145，当我们在4月买入股票时，我们直接去使用之前所求的最大值，5月份的145，显然是没有问题的。但是当循环继续进行，当我们在5月份买入股票时，我们已经在最贵的时候买入股票了，后面已经没有比5月还贵的了，这时我们无论什么时候卖出股票都是赔钱的。但是随着循环的继续进行，6月份买入股票呢，这时的最大值又是什么呢？7月份呢？8月份呢？

因此，这个想法并不能用在方法Ａ，因为调查范围是逐渐变小的，而不是像方法B，调查范围在逐渐增加。

3.7
高效率的算法（方法B）

最大收益(sp[],n){
mxp=0;//收益最大值
msf=sp[0];//迄今为止的最小值
for(j=1;j<n;j++){
d=sp[j]-msf;
if(d>mxp)
mxp=d;
if(sp[j]<msf)//进行最小值的更新
msf=sp[j];
}
return mxp;
}

我们看，新的算法当中的for循环减少到了一个，所以新的算法的时间复杂度为O(n)，与O(n2)相差甚远，魔法一样地减少了如此多的时间复杂度，这就是算法的神奇之处。

小说相关章节：U酱