shot-deeper
时间复杂度的几种计算方法
摘要：算法的时间复杂度是反映算法优劣的重要指标，
是《数据结构
》的重要理论基础，是学习和教学过程中贯穿
始终的主要线索。但是由于概念的抽象和计
算方法的繁琐，
使算法时间复杂度成为最难理解和掌握的问题之一。在总结
教学经验的基础上，该文提出几种常用的时间复杂度计算方
法，使对该知识点
的教学和学习变得系统和简单。
关键词：数据结构；时间复杂度；
渐进时间复杂度；迭
代法
中图分类号：
TP301
文献标识码：
A
文章编
号：
1009-3044(2011)19-4636-03
Several
Calculation Methods of Time Complexity
LIU Huai-yu,
ZHU Chang-jie, LI Jing
(Schoof of Computer Science
and Technology, Huaibei
Normal
University, Huaibei 235000, China)
Abstract: Time
complexity is an important index in
algorithm in terms of reflecting the
quality of the algorithm.
Time
complexity is also an important theoretical basis
in Data
Structure, thus is regarded as
a major clue throughout learning
and
teaching process. However, due to the abstractness
of the
concept and the tedious
calculation method, time complexity of
the algorithm becomes a most difficult
issue to understand and
master. This
paper, on the basis of summing up teaching
experiences, presents several commonly
used methods for the
time complexity
with the aim of simplifying the teaching and
learning of the knowledge point in a
systematic approach.
Key words: Datastructure;
Time Complexity; Asymptotic
Time
Complexity; Iteration method
1
算法时间复杂度的基本概念
1.1
算法的执行时间和语句频度
在已证明算法正确性的前提下，评
价算法的好坏主要是
关注算法在时间和空间上性能的优劣。算法时间性能的分析
是通过计算算法时间复杂度实现的，其关键就是计算算法的
执行时间。一
个算法的执行时间，就是算法中每条语句的执
行时间的总和。但是在算法实际运行过程中
，每次执行所耗
费的时间会受到诸如问题规模、输入特性和具体硬件环境等
各种外界因素的影响，想得到一个绝对准确的执行时间是几
乎不可能的。为此
，在进行算法执行时间的计算时一般都忽
略硬件及环境因素，并且假设每次执行时硬件条
件和环境条
件都是完全一致的，每条语句执行一次所需的时间均是单位
< br>时间
[1]
。
算法中
一条语句的执行时间取决于该语句的执行次数
和执行一次所需的时间。语句执行次数被称
为语句频度，执
行一次的时间被假设为单位时间，因此算法的执行时间就可
以看作是该算法中所有语句的语句频度之和
[2]
。
1.2
算法时间复杂度和渐进时间复杂度
算法时间复杂度的本质是算法的执
行时间，也就是算法
中所有语句的频度之和。语句频度就是语句的执行次数，它
与算法求解问题的规模大小息息相关。假设对于给定的算法，
目前问题规
模为
n
，则语句频度可以表示成一个关于问题规
模的函数
T(n)
，那么算法时间复杂度也就可以用<
/p>
T(n)
表示，
其含义是算法在输入规模
为
n
时的运行时间。
当问题
规模很大时，精确的计算
T(n)
是很难实现而且也
是没有必要的。对于算法时间性能的分析无需非要得到时间
复杂度
T(n)
的精确值，它的变化趋势和规律也能清楚地反映
算法的时间耗费。基于此，引入了渐进时间复杂度作为时间
性能分析的依据，它
的含义就是：在问题规模
n
趋于无穷大
时算法时间复杂度
T(n)
的渐进上界，
即函数
T(n)
的数量级
(
阶
)
[3]
。
算法时间复杂度和渐进算法时间复
杂度在实际的算法
分析过程中是不予区分的，渐进时间复杂度可以简称为时间
复杂度，记为
T(n)=O(f(n))
。其中，
“
O
”表示取数量级
(
阶
)
；
函数<
/p>
f(n)
是
T(n)
的同数量级
(
阶
)
函数，
即
(C
为不为零的常<
/p>