数据结构导论(全国高职高专计算机系列精品教材)配学习指导书

本书特色

《数据结构导论》：全国高职高专计算机系列精品教材

节选

相关资料

插图：对于一个问题可以有多种算法，如将在第5章介绍的排序有多达8种算法。那么如何来衡量哪种算法*有效？或者优于目前已知的算法呢？人们一般从两个方面来衡量。一个是时间效率，即算法处理数据时所花费的时间，用时间复杂度来表示；一个是空间效率，即算法所需求的存储量的大小，用空间复杂度来表示。但二者往往有冲突，不能同时兼顾，一般取时间效率，时间效率被认为更重要一些。1.时间复杂度分析对于解决同一个问题的算法，执行时间短的显然比执行时间长的时间效率高，即执行时间短的算法比执行时间长的算法时间复杂度要低。那么算法执行时间的长短如何度量呢？一种方法是编制一个程序实现这个算法，然后输入不同的数据运行这个程序，测定该程序运行的时间被称为事后统计法。这种方法的缺陷非常明显：一是必须编制程序和运行程序，非常耗费时间，也比较麻烦；二是受到的约束条件比较多，比如运行程序的计算机软硬件条件、使用的编程语言等，这些有时会掩盖算法本身的优劣。另一种方法是分析算法运行的时间，称为事前分析法。它不上机运行依算法编制的程序，而是分析影响算法执行时间的各种因素，从而估算出算法执行的时间。其中，一个*重要的因素是输入算法的数据量（称为问题规模）。例如，一个查找单词的算法，在100个单词中查找某个单词与在工。万个单词中查找某个单词所花费的时间肯定是不同的.因此，一个算法的执行时间T可被表示为问题规模n的一个函数T（n）。除了问题规模以外，实现算法的程序设计语言、源程序编译后产生的机器代码的质量、机器执行指令的速度等都会影响算法的执行时间。因此，不可能将T（n）表达为算法实际执行的时间。一般用算法中语句被执行的次数来表示算法的时间效率（算法的时间复杂度）。可用下面的例子来说明。