算法分析中时间复杂度验证及实现.pdf

算法分析中时间复杂度验证及实现

(师范学院,物理系,物理学专业温远通)
(学号:2000124103)

内容提要:在数据结构算法分析中,常常会涉及到算法的时间复杂度问题。学生对这个
问题的掌握,多数是停留在针对一个特定算法大 O 的计算,而难以深入理解其含义。本文试
图以程序运行机制为基础,介绍了时间复杂度的含义及其算法,并在程序实现方面进行了初
步探讨。在实现方面,借助计算机程序,把算法消耗的时间、程序的执行时间和渐进时间复
杂度的变化直观地显示出来,从而有助于学生弄清它们之间的区别和联系,更加透彻地理解
算法时间复杂度的含义。
关键词:代价;效益;增长率;时间复杂度;贪心算法;二分法检索
教师点评:算法分析中的时间复杂度是学生学习中的难点。本课题旨在通过形象的方法
给出比较直观的解释。温远通同学本学期才开始学习与此课题有关的“数据结构”课程,故
此课题对他来说具有一定的难度。他经过自己的刻苦学习和实践,设计了一个既能看到典型
程度运行步骤、又能分析出与时间复杂度有关的参数的状况的软件,并较好的实现了该软件。
在此设计实现工作过程中,温远通同学表现出较强的自学能力,能够独立解决相应的问题、
进行科学的探索和实践。(点评教师:胡建民,高级工程师)

计算机要解决某个问题,或者是说要完成某一项任务,可以有不同的解决方案,也就是
算法。当问题被准确定义后,从数学角度讲,可以把问题看作相应输入量的函数;因此,我
们就可以研究这些解决问题的方法,这就是算法的分析。求解同一个问题,可以有不同的算
法,要评价这些算法的好坏,算法所耗费的时间是一个关键的因素。而算法的时间耗费是该
算法所求解问题规模 n 的函数,可以记为 T(n);这就是算法的时间复杂度(plexity)。
当问题的规模 n 趋向无穷大时,就把时间复杂度 T(n)的数量级(数量阶)称为算法的渐进时
间复杂度。

一、算法的代价
算法(algorithm)可以定义为解决问题的一种方法或者一个过程。如果将问题看作函数,
那么算法就能把输入转化为输出。
算法分析(algorithm analysis)就是估量一个算法或者一个实现该算法的计算机程序效率
的方法;它还可以度量一个问题的内在复杂程度。通过它可以清楚地看到在解决同一个问题
时不同算法在效率上的差异。
一个问题可以有多种算法,一个给定的算法解决一个特定的问题(如,计算一个特殊函
数)。知道一个问题多种解法的优点在于不同的解法可能对问题的几个特定变量更有效,或
者对同一个问题的不同输入更有效。例如,有的排序算法适合于节点元素数目较少的序列,
有的算法适合于节点元素数目较多的序列,而有的算法则适合于可变长度的字符串。
既然一个问题有多种解法,那么用计算机程序实现算法时就有两个必须考虑的核心目
标,而它们有时是互相冲突的。一是希望设计一个容易理解、容易编码和调试的算法;二是
希望该算法能有效利用计算机资源。在理想情况下,达到这两个目标的程序可以说是“完美
的”。然而事实并非如此,不同的算法解决问题的效率不同,也就是说不同的算法对同一系
统的开销是不一样的,我们称之为算法的代价不同。算法的开销中有时间方面的开销和空间
方面的开销,相应称为算法的时间代价和空间代价。要比较两种算法的效率,一种办法就是
使用源程序分别实现这两种算法,然后输入适当的数据运行,测算两个程序各自的开销。但
是这个方法并不尽如人意。
第一,编写两个程序,测算两种算法将花费较多的时间和精力,而我们至多只需要保留
其中之一。
第二,仅凭实验来比较两种算法,很有可能因为一个程序比另一个“写得好”,而使得
算法的真正质量没有得到很好的体现。
第三,测试数据的选择可能对其中的一个算法有利。第四,我们可能会发现即使是较好
1
的那种算法也超出了预算的开销,这意味着不得不再重复一遍这样的过程——寻找一种新的
算法,再编写一个程序实现它。
另一种办法可以解决所有这些问题,我们称之为渐近算法分析(asymptotic algorithm),简
称算法分析(algorithm analysis)。它可以估算出当问题规模变大时,一种算法及实现它的程序
的效率和开销。
值得注意的是,算法分析时,如果是有关时间开销的问题,要注意所研究的时间代价是
最佳、最差还是平均情况。因为对于某些算法,即使问题规模相同,如果输入数据不同,其
时间开销也不同。如要从一个n元一维数组中找出一个给定的K(假设该数组中有且仅有一个
元素值为K)。顺序检索法将从第一个元素开始,依次检索每一个元素,直到找到K为止。一
旦找到了K,算法也就完成了。