算法导论课件第三讲算法的复杂度分析与最优算法.pptVIP

Introduction to Algorithms算法导论 第一章 引论 算法的复杂度分析与最优算法 增长阶 例: sum=0; for(i=1;i=n;i++) for(j=1;j=n;j++) sum++; 增长阶 T(n)=O(n2) 算法分析的基本法则 非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环 循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。 在最好情况下，ti=1, for 1 ? i n; 在最坏情况下，ti ? i+1, for 1 ? i n; 对于输入数据a[i]=n-i,i=0,1,…,n-1，算法insertion_sort 达到其最坏情形。因此， 由此可见，Tmax(n)= ?(n2) 递归算法复杂性分析 int factorial(int n) { if (n == 0) return 1; return n*factorial(n-1); } 最优算法 问题的计算时间下界为?(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。 例如，排序问题的计算时间下界为?(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。 如何证明算法A是最优算法? 分析算法的最差情况复杂度 WA(n), 建立算法A所解决的问题的复杂度下界W[A](n) 。即对于所有规模为n的输入，证明与算法A同类的所有算法（包括已知的和未知的）的最差情况复杂度≥ W[A](n) ， If WA(n) = ?( W[A](n) )则算法A是最优算法。 例:查找最大元素 Algorithm A (顺序查找算法 ) int findMax(int[] E, int n) 1. int max; 2. max = E[0]; // Assume the first is max. 3. for (index = 1; index n; index++) 4. if (max E[index]) 5. max = E[index]; 6. return max; WA(n) 算法的基本运算是将数组中的元素两两进行比较，每个元素都至少比较一次，因此该算法的最差情况以及最佳情况和平均情况下的复杂度都一样。所以这个算法的最差情况复杂度为: WA(n) = n-1 ?Θ(n) W[A](n) 所有通过比较方式进行查找的算法构成类[A], 推导 W[A](n) 因为考虑的是这类算法的最差情况复杂度，不妨设输入数组的元素是互不相同的。 既然n元数组中的元素各不相同，所以数组的最大元素只能有一个，即其余的n?1个元素都不会是最大元素。而对于这n?1个元素中的每一个来说，要判定它不是数组的最大元素，至少得找到一个比它更大的元素，因此需要至少一次比较。所以为了找出最大元素，算法至少需要n?1次比较，即 W[A](n) = n – 1。 由 WA(n) = W[A](n), 算法 A 是最优算法. 增长阶比较 增长阶比较（n15） 补充：算法渐近复杂性分析中常用函数 （1）单调函数 单调递增：m ? n ? f(m) ? f(n) ; 单调递减：m ? n ? f(m) ? f(n); 严格单调递增：m n ? f(m) f(n); 严格单调递减：m n ? f(m) f(n). （2）取整函数 ? x ? ：不大于x的最大整数； ? x ? ：不小于x的最小整数。 取整函数的若干性质 x-1 ? x ? ? x ? ? x ? x+1； ? n/2 ? + ? n/2 ? = n; 对于n ? 0，a,b0，有： ? ? n/a ? /b ? = ? n/ab ? ; ? ? n/a ? /b ? = ? n/ab ? ; ? a/b ? ? (a+(b-1))/b; ? a/b ? ? (a-(b-1))/b; f(x)= ? x ? , g(x)= ? x ? 为单调递增函数。 （3）多项式函数 p(n)= a0+a1n+a2n2+…+adnd； ad0; p(n) = ?(nd); f(n) = O(nk) ? f(n)多项式有界； f(n) = O(1) ? f(n) ? c; k ? d ? p(n) = O(nk) ; k ? d