注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小木舟的博客

笔墨生活随想,记录似水年华。

 
 
 

日志

 
 

扫描算法  

2010-05-12 00:52:50|  分类: 编程学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

《编程珠玑(第2版)》第八章,算法设计技术。

1.  问题描述

问题来自一维的模式识别,问题的输入是具有n个浮点数的向量x,输出是输入向量的任何连续子向量的最大和。例如,如果输入向量包含下面10个元素:

31

-41

59

26

-53

58

97

-93

-23

84

那么该程序的输出为x[2..6]的总和,即187。当所有数都是正数时,问题很容易解决,此时最大的子向量就是整个输入向量。当输入中含有负数时麻烦就来了:是否应该包含某个负数并期望旁边的整数会弥补它呢?

2.  简单算法

完成该任务的浅显程序就是对所有满足0<=i<=j<n的(i,j)整数对进行迭代。对每个整数对,程序都要计算x[ij]的总和,并检验总和是否大于迄今为止的最大总和。该算法的伪代码如下所示:

maxsofar = 0

for i = [0,n)

     for j = [i,n)

         sum = 0

         for k = [i,j]

              sum += x[k]

              /* sum is sum of x[i..j] */

              maxsofar = max(maxsofar, sum)

     这段代码简洁、直观并且易于理解。不幸的是,程序的运行速度也很慢。

3.  两个平方算法

有两个算法可以明显地提高第一个算法的速度,其中一个是比较明显可想的,而另外一个则不那么明显,它们的时间复杂度都是平方时间(对于输入规模n来说,需要执行O(n^2 )步)。

可以注意到,x[i..j]的总和与前面已计算出的总和(x[i..j-1]的总和)密切相关。利用这一关系即可得到算法。伪码如下:

maxsofar = 0

for i = [0,n)

     sum = 0

     for j = [i,n)

         sum += x[j]

         /* sum is sum of x[i..j] */

          maxsofar = max(maxsofar, sum)

     另一个平方算法是通过访问在外循环执行之前就已构建的数据结构的方式在内循环中计算总和。cumarr中的第i个元素包含x[0..i]中各个数的累加和,所以x[i..j]中各个数的总和可以通过计算cumarr[j]-cumarr[i-1]得到。从而得到如下所示的伪码:

cumarr[-1] = 0

for i = [0,n)

     cumarr[i] = cumarr[i-1] + x[i]

maxsofar = 0

for i = [0,n)

     for j = [i,n)

     sum = cumarr[j] - cumarr[i-1]

     /* sum is sum of x[i..j] */

     maxsofar = max(maxsofar, sum)

4.  扫描算法

我们现在采用操作数组的最简单的算法:从数组最左端(元素x[0])开始扫描,一直到最右端(元素x[n-1])为止,并记下所遇到的最大总和子向量。最大总和的初始值设为0。假设我们已经解决了x[0..i-1]的问题,那么如何将其拓展为包含x[i]的问题呢?我们使用类似于分治法的原理:前i个元素中,最大总和子数组要么在前i-1个元素中(我们将其存储在maxsofar),要么其结束位置为i(我们将其存储在maxendinghere中)。

 

maxsofar

 

maxendinghere

                                                                                        i

   

我们不从头开始计算结束位置为i的最大子向量,而是利用结束位置为i-1的最大子向量进行计算。这样得到如下所示的算法伪码:

maxsofar = 0

maxendinghere = 0

for i = [0,n)

  /* invariant: maxendinghere and maxsofar are accurate for x[0..i-1] */

  maxendinghere = max(maxendinghere + x[i], 0)

  maxsofar = max(maxsofar,maxendinghere)

     理解这个程序的关键在于变量maxendinghere。在循环中的第一个赋值语句之前,maxendinghere是结束位置为i-1的最大子向量的和;赋值语句将其修改为结束位置为i的最大子向量的和。若加上x[i]之后结果依然为正值,则该赋值语句使maxendinghere增加x[i];若加上x[i]之后结果为负值,该赋值语句就将maxendinghere重新设为0(因为结束位置为i的最大子向量现在为空向量)。该代码比较复杂,但十分简短,运行起来也很快:其运行速度为On,因此我们称之为线性算法。

  评论这张
 
阅读(1174)| 评论(0)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017