2算法的时间复杂性

《2算法的时间复杂性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.算法的时间复杂性分析基础2.1影响问题求解时间的因素A：算法n：问题的规模I：输入数据复杂性的形式化表示T(A,n,I)对于特定算法，时间复杂性为：T(n,I)2.1时间复杂性函数T(N,I)是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2,..,Ok；设这些元运算每执行一次所需要的时间分别为t1,t2,..,tk。对于给定的算法A，用到元运算Oi的次数为ei，i=1,2,..,k，很明显，对于每一个i，ei是n和I的函数，即ei=ei(n,I)。那么有：其中ti，i=1,2,..,k,是与N,I无关的常数。先看一个实例：改进冒

2、泡如排序算法的基本步骤如下：fori←1ton-1do{flag←1forj←1ton-idoifa[j]

3、法输入中统计相应的ei,i=1,2,…,k，评价时间复杂性。一般只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，井分别记为：W(n)=max{T(n，I)},I∈DnB(n)=min{T(n，I)},I∈DnA(n)＝∑P(I)T(n，I)I∈DnDn是规模为n的合法输入的集合，P(I)是在算法的应用中出现输入I的概率。最具有可操作性和实际价值的是最坏情况下的时间复杂性。我们对算法的时间复杂性分析的兴趣主要将放在W(n)上。没有特殊说明时，T(n)一般指的就是W(n)。对于同一类问题，采用这类算法的基本运算次数作为算法的运算时间。例如：“汉诺塔”算法的基本运

4、算是圆盘的移动；比较排序算法，用算法所用的比较次数作为该类算法的运算时间；矩阵相乘：基本运算是两个数的相乘；树的搜索：基本运算是节点的访问；图的算法：节点和边的运算。2.2.1算法时间复杂性计量2.2.2时间复杂性的计算规则分析时间复杂性渐近阶的8条规则：规则1：赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等，只需要1个单位时间。规则2条件语句"ifCthenS1elseS2"需要Tc+max(Ts1，Ts2)的时间，其中Tc是计算条件表达式C需要的时间，而Ts1和Ts2分别是执行语句S1和S2需要的时间。规则3选择语句"Case A  a1:S1;a2:S2;…;am:Sm

5、; end"，需要max(Ts1,Ts2，…，Tsm)的时间，其中Tsi是执行语句Si所需要的时间，i=l,2,…,m。规则4访问一个数组的单个分量或一个记录的单个域，只需要1个单位时间。规则5执行一个for循环语句需要的时间等于执行该循环体所需要的时间乘上循环的次数。规则6执行一个while循环语句“whileCdoS”，需要的时间等于(计算条件表达式C的时间+执行循环S体的时间)*循环的次数。规则6与规则5不同，循环次数是隐含的。例如，b_search函数中的while循环语句。按规则(1)-(4)，while(notfound)and(U≥=L){m←(U+L)div2ifc=A

6、[m]thenfound←trueelseifc>A[m]thenL←I+1elseU←m-1}规则7对于break语句。为了便于表达从循环体的中途跳转到循环体的结束,引入break语句。在时间复杂性分析时可以假设它不需要任何额外的时间。规则8对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。如果过程(或函数)出现直接或间接的递归调用，则根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到

7、递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。经验和技巧是非常重要的BUILD-MAX-HEAP(A)1heap-size[A]←length[A]2fori←⌊length[A]/2⌋downto1n/2次3doMAX-HEAPIFY(A,i)归结到分析MAX-HEAPIFY(A,i)的时间例：建最大堆算法的复杂性分析MAX-HEAPIFY(A,i)1l←LEFT(i)2r←RIGHT(i)3ifl≤heap-si