2时间复杂度的算法.pptVIP

递归方程： 递归方程组解的渐进阶的求法——母函数法 设关于T(n)的递归方程的解的母函数为： (1)-(2)-(3)得 (1) (2) (3) 根据G(x)的形式： 有T(n)=a2-b2 作业 1 分析算法的时间复杂性 int Horner(int coeff[], int n, const int x) {//计算n次多项式的值，coeff [ 0:n ]为多项式的系数 int value= coeff [ n ] for ( int i = 1; i = n; i++) value = value * x + coeff [ n-i ] return value } 2、有三个矩阵A , B ,C ，它们的阶分别为3×2 、 2×6、 6×1，要求计算3个矩阵的连乘：A× B × C。 a ) 统计乘法运算的次数 b ) 最少需要做几次乘法？ 3、分析折半查找（二分检索）的最坏情况下的时间复杂性，证明其达到了问题复杂度的下界。 证明下列运算规则 Ο(f)+ Ο(g)=Ο(f +g)； Ο(f)·Ο(g)= Ο(f·g)； 如果g(N)= Ο(f(N))，则Ο(f)+ Ο(g)= Ο(f)； Ο(Cf(N))= Ο(f(N))，其中C是一个正的常数； 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无关的常数。 先看一个实例： 改进冒泡如排序算法的基本步骤如下： for i ←1 to n-1 do {flag ←1 for j ←1 to n-i do if a[j]a[j+1] then {交换a[j]、a[j+1] flag ←0 /*发生了交换*/ } if flag then beak /* 没有交换，排序结束*/ } enddo 如果将if a[j]a[j+1] then {….. }当做一个元运算，花的时间为C 当输入的数据已经排好序，做了n-1次元运算； 当输入的数据是增序，则需要做n(n-1)/2次元运算。 显然，不可能对规模n的每一种合法的输入I都去统计ei(n,I),i=1,2,…,k。因此T(n,I)的表达式还得进一步简化。 只能在规模为n的某些或某类有代表性的合法输入中统计相应的ei , i=1,2,…,k，评价时间复杂性。 一般只考虑三种情况下的时间复杂性，即最坏情况、最好情况与平均情况下的时间复杂性，井分别记为： W(n) = max{ T(n，I) } , I∈Dn B(n) = min { T(n，I) }, I∈Dn A(n)＝∑P( I )T(n，I) I∈Dn Dn是规模为n的合法输入的集合，P(I)是在算法的应用中 出现输入I 的概率。 最具有可操作性和实际价值的是最坏情况下的时间复杂 性。我们对算法的时间复杂性分析的兴趣主要将放在W(n) 上。没有特殊说明时，T(n)一般指的就是W(n)。 对于同一类问题，采用这类算法的基本运算次数作为算法的运算时间。 例如： “汉诺塔”算法的基本运算是圆盘的移动； 比较排序算法，用算法所用的比较次数作为该类算法的 运算时间； 矩阵相乘：基本运算是两个数的相乘； 树的有哪些信誉好的足球投注网站：基本运算是节点的访问； 图的算法：节点与边的运算。 2.2.1算法时间复杂性计量 2.2.2 时间复杂性的计算规则 分析时间复杂性渐近阶的8条规则 ： 规则1： 赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等，只需要1个单位时间。 规则2 条件语句if C then S1 else S2需要Tc+max(Ts1，Ts2)的时间，其中Tc是计算条件表达式C需要的时间，而Ts1与T