您好, 访客   登录/注册

浅谈算法及算法评价

来源:用户上传      作者:

  【摘 要】在计算机领域,一个算法实质上是针对所处理问题的需要,在数据的逻辑结构和存储结构的基础上施加的一种运算。对算法要进行评价、改进,从而设计出更好的算法。
  【关键词】 算法 算法评价
  
  一、算法
  算法是指为解决给定问题而需施行的有穷操作过程的描述。在计算机科学中,算法则是描述计算机解决给定问题的操作过程。描述一个算法可以采用文字叙述,也可以采用传统流程图、N-S图或PAD图,但要在计算机上实现,则最终必须采用一种程序设计语言编写为程序。算法的意义非常类似于处方、过程、方法和规程。
  通常,一个算法必须具备以下五个重要特性:
  1. 有穷性
  有始有终是算法最基本的特征。一个算法必须在它所涉及的每一种情形下,都能在执行有穷步操作之后结束。有的运算过程,操作步骤看似有限,但不能保证它在动态环境下实际执行次数的有穷性。因此,判断一个算法的有穷性应对算法所涉及的各种情形作动态分析,从而作出判断。看下面两个例子:
  例1 一个非算法的计数过程
  (1)开始
  (2)n←0
  (3)n←n+1
  (4)重复(3)
  (5)结束
  粗一看,这个过程仅有五个步骤,是有穷的,但事实上,该过程一开始,就永不休止。因而在动态执行中它并不具备有穷性,它不是一个算法。当然,只要对上述过程稍加修改,限定其计数之上限,即可使之成为一个算法,这就是下面的例2。
  2. 确定性
  算法的每一步操作,其顺序和内容都必须确切定义,而不得有任何歧义性。
  3. 数据输入
  一个算法有n(n≥0)个初始数据的输入。
  4. 数据输出
  算法是用来解决给定问题的,所以,一个算法必须将人们所关心的信息输出。也就是说,一个算法必须有一个或多个有效信息的输出,它是同输入数据有某种特定关系的信息。
  5. 可行性
  一个算法的任何一步操作都必须是可行的,即必须是可以付诸实施并能具体实现的基本操作。也就是说,每步操作均能由计算机(或人们用纸和笔)操作有限次即可完成。
  二、算法评价
  对于解决同一个问题,往往能够编写出许多不同的算法。进行算法评价的目的,既在于从解决同一问题的不同算法中选择出较为合适的一种,也在于知道如何对现有算法进行改进,从而有可能设计出更好的算法。一般从以下六个方面对算法进行评价。
  1. 正确性
  正确性是设计和评价一个算法的首要条件,如果一个算法不正确,则不能完成或不能较好地完成所要求的任务,其他方面也就无从谈起。一个正确的算法是指在合理的数据输入下,能够在有限的运行时间内得出正确的结果。通过采用各种典型的输入数据上机反复调试算法,使得算法中的每段代码都被测试过,若发现错误及时修正,最终可以验证出算法的正确性。
  2. 健壮性
  健壮性是指一个算法对不合理(又称不正确、非法、错误等)数据输入的反应和处理能力。一个好的算法应该能够识别出错误数据并进行相应的处理。对错误数据的处理一般包括打印出错误信息、调用错误处理程序、返回标识错误的特定信息、中止程序运行等。
  3. 可读性
  可读性是指一个算法供人们阅读的方便程度。一个可读性好的算法,应该符合结构化和模块化程序设计的思想,应该对其中的每个功能模块、重要数据类型或语句加以注释,应该建立有相应的文档,对整个算法的功能、结构、使用及有关事项进行说明。
  4. 简单性
  简单性是指一个算法所采用的数据结构和方法的简单程度。如对数组进行查找时,采用顺序查找的方法比采用二分查找的方法要简单;对数据进行排序时,采用简单选择排序的方法比采用堆排序或快速排序的方法要简单,对文件进行输入输出时,使用提取和插入操作符比使用成员函数要简单,把一批数据组织成线性结构比组织成树或图结构要简单。但最简单的算法往往不是最有效的,即可能需要占用较长的运行时间和较多的内存空间。而算法的简单性便于用户编写、分析和调试,对于处理少量数据的情况还是适用的,若要处理大量的数据,则算法的有效性(即占用较少的运行时间和内存空间)比简单性更重要。
  5. 时间复杂度
  时间复杂度又称计算复杂度,它是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间,它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异,它是由机器本身硬软件环境决定的,与算法无关,所以我们只讨论影响运行时间的另一个因素――算法中进行简单操作的次数。
  不管一个算法是简单还是复杂,最终都是被分解成简单操作来具体执行的,因此,每个算法都对应着一定的简单操作的次数。显然,在一个算法中,进行简单操作的次数越少,其运行时间也就相对地越少;次数越多,其运行时间也就相对地越多。所以,通常把算法中包含简单操作次数的多少叫做算法的时间复杂度,用它来衡量一个算法的运行时间性能或称计算性能。
  在一个算法中,最好情况的时间复杂度最容易求出,但它通常没有多大的实际意义,因为数据一般都是随意分布的,出现最好情况分布的概率极小。最差情况的时间复杂度也容易求出,它比最好情况有实际意义,通过它可以估计到算法运行时所需要的相对最长时间,并且能够使用户知道如何设法改变数据的排列次序,尽量避免或减少最差情况的发生。平均情况下的时间复杂度的计算要困难一些,因为它往往需要概率统计等方面的数学知识,有时还需要经过严格的理论推导才能求出,但平均情况的时间复杂度最有实际意义,它确切地反映了运行一个算法的平均快慢程度,通常就用它来表示一个算法的时间复杂度。
  6. 空间复杂度
  空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间、算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题所决定的,是通过参数表由调用函数传递而来,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地”进行的,是节省存储的算法,有的算法需要占用的临时工作单元数与解决问题的规模有关。
  分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。
  对于一个算法,其时间复杂度和空间复杂度往往是相互影响的,当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
  
  【参考文献】
  [1]数据结构. 电子科技大学出版社, 1994.
  [2]数据结构实用教程(c/c++描述). 清华大学出版社,2001.

转载注明来源:https://www.xzbu.com/9/view-9572000.htm