时间复杂度的几种计算方法

Computer Knowledge and Technology 电脑知识与技术 本栏目责任编辑：唐一东人工智能及识别技术 第 7 卷第 19 期 (2011 年 7 月) 时间复杂度的几种计算方法 刘怀愚，朱昌杰，李璟 （淮北师范大学 计算机科学与技术学院，安徽 淮北 235000） 摘要：算法的时间复杂度是反映算法优劣的重要指标，是《数据结构》的重要理论基础，是学习和教学过程中贯穿始终的主要线索。 但是由于概念的抽象和计算方法的繁琐，使算法时间复杂度成为最难理解和掌握的问题之一。 在总结教学经验的基础上，该文提出 几种常用的时间复杂度计算方法，使对该的教学和学习变得系统和简单。 关键词：数据结构；时间复杂度；渐进时间复杂度；迭代法 中图分类号：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 un- derstand 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 算法的执行时间和语句频度 在已证明算法正确性的前提下，评价算法的好坏主要是关注算法在时间和空间上性能的优劣。 算法时间性能的是通过计 算算法时间复杂度实现的，其关键就是计算算法的执行时间。 一个算法的执行时间，就是算法中每条语句的执行时间的总和。 但是 在算法实际运行过程中，每次执行所耗费的时间会受到诸如问题规模、输入特性和具体硬件环境等各种外界因素的影响，想得到一 个绝对准确的执行时间是几乎不可能的。 为此，在进行算法执行时间的计算时一般都忽略硬件及环境因素，并且假设每次执行时硬 件条件和环境条件都是完全一致的，每条语句执行一次所需的时间均是单位时间 [1]。 算法中一条语句的执行时间取决于该语句的执行次数和执行一次所需的时间。 语句执行次数被称为语句频度，执行一次的时 间被假设为单位时间，因此算法的执行时间就可以看作是该算法中所有语句的语句频度之和 [2]。 1.2 算法时间复杂度和渐进时间复杂度 算法时间复杂度的本质是算法的执行时间，也就是算法中所有语句的频度之和。 语句频度就是语句的执行次数，它与算法求解 问题的规模大小息息相关。 假设对于给定的算法，目前问题规模为 n，则语句频度可以示成一个关于问题规模的函数 T(n)，那么算 法时间复杂度也就可以用 T(n)表示，其含义是算法在输入规模为 n 时的运行时间。 当问题规模很大时，精确的计算 T(n)是很难实现而且也是没有必要的。对于算法时间性能的分析无需非要得到时间复杂度 T(n) 的精确值，它的变化趋势和规律也能清楚地反映算法的时间耗费。 基于此，引入了渐进时间复杂度作为时间性能分析的依据，它的 含义就是：在问题规模 n 趋于无穷大时算法时间复杂度 T(n)的渐进上界，即函数 T(n)的数量级(阶) [3]。 算法时间复杂度和渐进算法时间复杂度在实际的算法分析过程中是不予区分的， 渐进时间复杂度可以简称为时间复杂度，记 为 T(n)=O(f(n))。 其中， “O”表示取数量级(阶)； 函数 f(n)是 T(n)的同数量级(阶)函数，即 (C 为不为零的常数)。 它一般是算法中最大的语句频度，是最内层循环语句 的执行次数。 按数量级递增排列，常见的时间复杂度有：常数阶 O(1)，对数阶 O(log2n)，线性阶 O(n)，线性对数阶 O(nlog2n),平方阶 O(n2)，立方阶 O(n3)，…，k 次方阶 O(nk)，指数阶 O(2n)。 随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2 算法时间复杂度的计算方法 收稿日期：2011-05-11 作者简介：刘怀愚（1979-），男，安徽淮北人，工学硕士，讲师，研究方向：模式识别；朱昌杰（1963-），男，安徽怀宁人，教授，硕士生导 师，研究方向：信息管理；李璟（1979-），女，安徽省亳州人，硕士，讲师，研究方向：模式识别。 E-mail: eduf@cccc.net.cn http://www.dnzs.net.cn Tel:+86-551-5690963 5690964 ISSN 1009-3044 Computer Knowledge and Technology 电脑知识与技术 Vol.7, No.19, July 2011. 4636 Mountplorer 铅笔 Mountplorer 椭圆形 Mountplorer 线条 Computer Knowledge and Technology 电脑知识与技术 人工智能及识别技术本栏目责任编辑：唐一东 第 7 卷第 19 期 (2011 年 7 月) 在算法时间复杂度的计算中，最关键的是得出算法中最多的执行次数。 很容易看出，算法中最内层循环体语句往往具有最大的 语句频度，在计算过程中主要对它们进行分析和计算。 目前，常用的时间复杂度计算方法可以归纳为如下几种。 2.1 求和法 当算法中语句的执行次数与某一变量有直接关系，而该变量的变化起止范围又较为明确，则可以利用求和公式得出最大的语 句频度 f(n)，再对其取数量级(阶)即可。 例 1 有算法如下： ① for(i=1;i<=n;i++) ② for(j=1;j<=n;j++) ③ ++x; 解：以上算法中频度最大的是语句③，它的执行次数跟循环变量 i 和 j 有直接关系，因此其频度可以通过求和公式求得： 所以，该算法的时间复杂度为平方阶，记作 T(n)=O(n2)。 例 2 有一算法如下： ① for(i=1;i<=n;i++) ② for(j=1;j<=i;j++) ③ for(k=1;k<=j;k++) ④ ++x; 解：以上算法中频度最大的是语句④，其频度可以通过求和公式求得： 所以，该算法的时间复杂度为立方阶，记作 T(n)=O(n3)。 例 3 有如下算法： ① y=0; ② while((y+1)2<=n) ③ x++; 解：算法中频度最大的应该是语句③，它的执行次数与 y 有关，已知 y 初值为 0，当(y+1)2>n 时循环终止，则 y 的最大取值应该为 n姨 -1。 所以语句③的频度可以通过求和公式得到： 所以，该算法的时间复杂度记作 2.2 假设法 在某些较为复杂的算法中，循环结构的循环次数很难直接看出，特别是当循环次数与循环体中的某些语句执行有联系时，语句 频度的计算变得比较困难。 此时，可以先假设循环执行次数为 k 次，再对算法进行分析，根据循环终止条件求出语句频度 f(n)，最后 求出 T(n)。 例 4 有一算法如下： x=91;y=100; while(y>0) if(x>100) {x-=10; y--;} else x++; 解：假设 while 循环的循环体执行 k 次，可以发现： k=1 时，x=92，y=100 k=2 时，x=93，y=100 k=3 时，x=94，y=100 … k=10 时，x=101，y=100 k=11 时，x=91，y=99 … k=22 时，x=91，y=98 … 由分析可知，每循环 11 次，y 的值发生一次变化，y 需共变化 100 次。 所以，f(n)=100*11=1100。 则该算法的执行时间是一个与问 题规模 n 无关的常数，它不随着问题规模 n 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。 因此， 4637 Mountplorer 线条 Computer Knowledge and Technology 电脑知识与技术 本栏目责任编辑：唐一东人工智能及识别技术 第 7 卷第 19 期 (2011 年 7 月) 该算法的时间复杂度为常数阶，记作 T(n)=O(1)。 例 5 有如下算法： i=s=0； while(s设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计