算法设计与分析 课件 第一章 绪论1.4.1 时间复杂度分析

计算机算法设计与分析第一章概述1.4.1算法的效率分析目的评估算法体现算法运行时所需要消耗的计算机资源占用CPU的计算时间量称为时间复杂度占用内存的存储空间量称为空间复杂度算法复杂度分析一般采用事前分析方式而是不事后统计法算法的效率分析算法的时间复杂度T和空间复杂度S的函数：T=T(N,I)S=S(N,I)N表示问题规模，I表示算法输入在实际应用中，关注时间效率多于空间效率。算法时间复杂度分析评估算法时间复杂度，应尽量做到客观反映算法的本质特征和属性。所以，算法时间复杂度分析应该要有一个不依赖于计算机硬件配置、问题规模和输入实例的抽象表示。算法时间复杂度分析假设在一台抽象的计算机上提供了k种元运算O1，O2，…，Ok，每个元运算执行的时间分别为t1，t2，...，tk。元运算通常指的是算法中最基本的操作步骤，一个元运算可以是基本的算术运算（如加法、减法、乘法、除法）、比较操作、赋值操作、数组访问或迭代循环等。算法时间复杂度分析T(N，I)表示算法在这台抽象计算机上运行所需要的的时间，设，在算法中

元运算Oi被调用的次数为ei，ei=ei(N,I)，因此，T(N,I)一般化的表示：算法时间复杂度分析为消除公式中ti表示的元运算执行的具体时间，不妨假设所有的元运算都在一个单位时间内完成或者将ti抽象表示为一条执行语句或表达式所用时间，则计算T(N,I)的工作就变为统计计算语句的频度，从而简化复杂度的求解。例1.4插入排序问题时间复杂度计算

算法：插入排序（升序排序）

输入：数组元素array，元素个数n

输出：升序的数组元素arrayInsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移动元素6 j

j–17 end8 array[j+1]

key9

endend当输入数据为1,2,3,4,5时，语句2、3、8被执行4次，语句5、6被执行0次。当输入数据为5,4,3,2,1时，语句2、3、8被执行4次，语句5、6被执行10次。算法时间复杂度分析对同一个算法，运行不同的输入实例时，算法语句执行的次数差异明显。实际上，在统计时间复杂度时，我们不可能对规模N的每一种合法输入都去统计各个算法语句执行的次数，这时就需要对输入实例做一个合理简化，即将输入实例进行特化。算法时间复杂度分析（1）最坏情况下的时间复杂度：IN是规模为N的合法输入集合，I*是IN中使T(N,I)达到Tmax(N)的合法输入。最坏情况下的时间复杂度就是将所有的合法输入实例中最坏的那个输入实例I*找出来，统计在输入实例I*时算法语句执行的次数来评估算法时间复杂度。算法时间复杂度分析（2）最好情况下的时间复杂度：I'是IN中使T(N,I)达到Tmin(N)的合法输入，将所有的合法输入实例中最好的那个输入实例I'找出来，统计在输入实例I'时算法语句执行的次数来评估算法时间复杂度。算法时间复杂度分析（3）平均情况下的时间复杂度：P(I)是算法应用中出现输入实例I的概率，全部合法输入实例的概率总和为1。平均时间复杂度是用每一个输入实例出现的概率，计算其数学期望。在分析算法时间复杂度的时候，往往关注的是最坏情况下算法的时间复杂度。例1.4插入排序问题时间复杂度计算

算法：插入排序（升序排序）

输入：数组元素array，元素个数n

输出：升序的数组元素arrayInsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移动元素6 j

j–17 end8 array[j+1]

key9

endend语句2,3,8分别执行N-1次语句5,6执行的次数分为1,2,3，...，N-1次