算法的完美

时间:2012-03-19 | 分类:学习园地,网络文摘 | 浏览:2268 | 评论:0 | 发表评论

  考虑一个问题:将一个具有n个元素的数组向左循环移动i个位置。有许多应用程序会调用这个问题的算法,例如在文本编辑器中移动行的操作,磁盘整理时交换两个不同大小的相邻内存块等。所以,这个问题的算法要求有较高的时间和空间性能。
 
  可以通过下面的方法解决这个问题:先将数组中的前i个元素存放在一个临时数组中,再将余下的n-i个元素左移i个位置,最后将前i个元素从临时数组复制回原数组中后面的位置。但是这个算法使用了i个额外的存储单元,使得空间性能降低。
 
   还有一个方法可以解决这个问题:先设计一个函数将数组向左循环移动一个位置,然后再调用该算法i次,显然,这个算法的时间性能不好。
 
   要在有限的资源中解决这个问题,似乎很困难。现在我们换一个角度看这个问题:将这个问题看作是把数组ab转换成数组ba(a代表数组的前i个元素,b代表数组中余下的n-i个元素),先将a逆置得到arb,再将b逆置得到arbr,最后将整个arbr逆置得到(arbr)r=ba。设Reverse函数执行将数组元素逆置的操作,对abcdefgh向左循环移动3个位置的过程如下: 
  Reverse(0, i-1); //得到cbadefgh 
  Reverse(i, n-1); //得到cbahgfed 
  Reverse(0, n-1); //得到defghabc
 
   其原理可以用一个简单的游戏来理解:将两手的掌心对着自己,左手在右手上面,可以实现将一个具有10 个元素的数组向左循环移动5位,如图1-12所示。 
 
 
  该算法在时间和空间上都很有效,并且是这么简短和简单,想出错都很难。Brian Kernighan在Software Tools in Pascal中使用了这个算法在文本编辑器中移动各行。     作为一个规律,一个好的算法是反复努力和重新修正的结果,即使足够幸运地得到了一个貌似完美的算法思想,我们也应该尝试着改进它。

 

标签: , ,
本文链接: 算法的完美
版权所有: 破博客, 转载请注明本文出处。

发表评论

您的昵称: *

您的邮箱: * (显示gravatar头像)

联系方式: