文本算法1概述

1、算法设计与分析晶kjhe，计算机算法设计与分析（第4版）， 电子工业ß课程方式：占总成绩的60%。期末闭卷ß成绩（作业、小和课堂考勤等）、ß实验：占总成绩的40%。第1章算法概述学习要点:· 理解算法的概念。· 理解什么是程序，程序与算法的区别和内在。· 掌握算法的计算复杂性概念。· 掌握算法渐近复杂性的数学表述。· 掌握用C+语言描述算法的方法。算法(Algorithm)ß算法是指解决问题的法或一个过程。ß算法是若干指令的有穷序列，满足性质：ß(1)输入：有外部提供的量作为算法的输入

2、。ß(2)输出：算法产生至少一个量作为输出。ß(3)确定性：组成算法的每条指令是清晰，无歧义的。ß(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序(Program)ß程序是算法用某种程序设计语言的具体实现。ß程序可以不满足算法的性质(4)。ß例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。ß操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。问题求解(Problem Solving)理解问题精确解或近似解选

3、择数据结构算法设计策略设计算法证明正确性分析算法设计程序算法复杂性分析ß算法复杂性 = 算法所需要的计算机ß算法的时间复杂性T(n)；ß算法的空间复杂性S(n)。ß其中n是问题的规模（输入大小）。算法的时间复杂性ß（1）最坏情况下的时间复杂性Tmax(n) = max T(I) | size(I)=n ßß（2）最好情况下的时间复杂性Tmin(n) = min T(I) | size(I)=n ßß（3）平均情况下的时间复杂性å p(I )T (I )Tavg(n) =ßsize( I

4、 )=nß其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。算法渐近复杂性ßt(n) -算法渐近复杂性ÞT(n) ®¥ , as n®¥ ;Þ(T(n) - t(n) )/ T(n) ®0 ，as n®¥Þt(n)是T(n)的渐近性态，为算法的渐近复杂性。Þ在数学上， t(n)是T(n)的渐近表的主项。它比T(n) 简单。，是T(n)略去低阶项留下渐近分析的记号在下面的讨论中，对所有n，f(n) ³ 0，g(n) ³ 0。（1） 渐近上

5、界记号O正常数c和n0使得对所有n³ n0有：0 £ f(n) £ cg(n) 。则称f(n) = O(g(n)表示算法运行时间的上界比如：f(n)=2*n+2=O(n) 比如：f(n)=2*n+2=O(n2)（2） 渐近下界记号W正常数c和n0使得对所有n³ n0有：0£ cg(n) £ f(n) 。则称f(n) =W (g(n)表示算法运行时间的下界比如：f(n)=2*n2+3*n+2=(n2) 比如：f(n)=2*n2+3*n+2=(n)比如：f(n)=2*n2+3*n+2=(1)ßßßß

6、ßßßßßßßßß（3）非紧上界记号oß对于任何正常数c>0，正数和n0 >0使得对所有n³n0有：0 £ f(n)<cg(n) 。则称f(n)= o(g(n) 。ß小o记号表示复杂度的上界，但是一定不等于下界。ßf(n)=2n2+3n+5=o(n3)或者f(n)=o(n4)或者f(n)=o(n5)ß（4）非紧下界记号wß对于任何正常数c>0，正数和n0 >0使得对所有n³n0有：0 £

7、 cg(n) < f(n) 。则称f(n) =w (g(n) 。ßw记号表示复杂度的下界，但是一定不等于上界。ß（5）紧渐近界记号QßQ (g(n) = f(n) |正常数c1,c2和n0使得对所有n³n0有：c1g(n) £ f(n) £ c2g(n) ß表示所有阶数与g(n)相同的函数集合ßf(n)=2n2+3n+5= Q(n2)ß定理1： Q (g(n) = O (g(n) Ç W (g(n)渐近分析记号的若干性质ß（1）传递性：ßf(n)= Q(g(n)， g(

8、n)= Q(h(n)f(n)= Q(h(n)；f(n)= O (h(n)；f(n)= W(h(n)；f(n)= o(h(n)；f(n)= w (h(n)；Þßf(n)= O(g(n)， g(n)= O (h(n) Þßf(n)= W(g(n)， g(n)= W (h(n) Þßf(n)= o(g(n)， g(n)= o(h(n)Þßf(n)= w(g(n)， g(n)= w (h(n) ÞLevel 2ß（2）反身性：ßf(n)= Q(f(n)；ßf(n)= O(f(n)；&

9、#223;f(n)= W(f(n).ß（3）对称性：ßf(n)= Q(g(n) Û g(n)= Q (f(n) .ß（4）互对称性：ßf(n)= O(g(n) Û g(n)= W (f(n) ；ßf(n)= o(g(n) Û g(n)= w (f(n) ；Level 2ß（5）算术运算：ßO(f(n)+O(g(n) = O(maxf(n),g(n) ；ßO(f(n)+O(g(n) = O(f(n)+g(n) ；ßO(f(n)*O(g(n) = O(f(n)*g(n) ；

10、23;O(cf(n) = O(f(n) ；ßg(n)= O(f(n) Þ O(f(n)+O(g(n) = O(f(n) 。Level 2算法渐近复杂性分析中常用函数ß（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）取整函数&

11、#223;ë x û ：不大于x的最大整数；ßé x ù ：不小于x的最小整数。取整函数的若干性质ßx-1 < ë x û £ x £ é x ù < x+1；ßë n/2 û + é n/2 ù = n;ß对于n ³ 0，a,b>0，有：ßé é n/a ù /b ù = é n/ab ù ;ßë

12、ë n/a û /b û = ë n/ab û ;ßé a/b ù £ (a+(b-1)/b;ßë a/b û ³ (a-(b-1)/b;ßf(x)= ë x û , g(x)= é x ù 为单调递增函数。Level 2ß（3）多项式函数ßp(n)= a0+a1n+a2n2+adnd； ad>0;ßp(n) = Q(nd);ßf(n) = O(nk) Û f(

13、n)多项式有界；ßf(n) = O(1) Û f(n) £ c;ßk ³ d Þ p(n) = O(nk) ;ßk £ d Þ p(n) = W(nk) ;ßk > d Þ p(n) = o(nk) ;ßk < d Þ p(n) = w(nk) .（4）指数函数对于正整数m,n和实数a>0:ßßa0=1;a1=a ;a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ;a>

14、;1 Þ an为单调递增函数;ßßßßßßßnba>1 ÞÞ n= o(a )bn= 0limßann®¥i= 1 + x +ex2!3!i!i=0ßex ³ 1+x;ß|x| £1 Þ 1+x £ ex £ 1+x+x2 ;ßex = 1+x+ Q(x2),as x®0;x önælimç1 += ex÷n®¥

15、èn øLevel 0ß（5）对数函数ßlog n = log2n;ßlg n = log10n;ßln n = logen;ßlogkn = (log n)kl;ßlog log n = log(log n);ßfor a>0,b>0,c>0a = blogb alogc (ab) = logc a + logcban= n logb alogba = logc alogblog bclogb (1/ a) = -logba1loga =blogbaa logb c= clogb a2

16、5ß|x| £1 Þln(1 +-L.2345xßfor x > -1, 1 +logb nlogbnßfor any a > 0, Þ log n = o(n )= lim= 0balimalog nan®¥ (2)nn®¥Level 0ß（6）阶乘函数n = 0n > 0n!= ì1ín(n - 1)!în!= 1× 2 × 3LnßStirlings approximationæ n 

17、6;n ææ 1 öön!=÷ ç1+ Qç÷÷2 nçè e ø èè n øøæ n ön11ea nn!=< <2 nç÷n12n + 112nè e øn!= o(nn )n!= w (2n )log(n!) = Q(n log n)Level 2算法分析中常见的复杂性函数小规模数据中等规模数据用c+描述算法Level 0（1）选择语句：ß（1.1

18、)if 语句：ßif (expression) statement; else statement;（1.2)？语句：ßßexp1?exp2:exp3 y= x>9 ? 100:200;if (x>9) y=100;else y=200;等价于：Level 0（1.3) switch语句：switch (expression) case 1:statement sequence; break;case 2:statement sequence; break;¼default:statement sequence;Level 0（2）迭代语句：

19、ß（2.1) for 循环：ßfor (init;condition;inc) statement;ß（2.2) while 循环：ßwhile (condition) statement;ß（2.3) do-while 循环：ßdostatement;ßß while (condition);Level 0（3）跳转语句：ß（3.1) return语句：return expression;ßß（3.2) goto语句：goto label;¼label:ß

20、3;ßLevel 0（4）函数：return-type function name(para-list)body of the functionß例：int max(int x,int y)return x>y?x:y;Level 0（5）模板template ：template <class Type> Type max(Type x,Type y)return x>y?x:y;int i=max(1,2)；double x=max(1.0,2.0)；Level 0（6）动态分配：ß（6.1）运算符new ：ß运算符new用于动

21、态分配。ßnew返回一个指向所分配空间的指针。ß例：int *x；y=new int；*y=10；ß也可将上述各语句作适当合并如下：ßint *y=new int；*y=10；ß或 int *y=new int(10)；ß或 int *y；y=new int(10)；Level 0（6.2）一维数组：ß为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x为一个float类型的指针。然后用new为数组动态地分配存储空间。ß例：ßfloat *x=new floatn；ß创建一个大小为n的一

22、维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。ß然后可用x0，x1，xn-1来每个数组元素。Level 0（6.3）运算符delete ：ß当动态分配的用的空间。空间已不再需要时应及时所占ß用运算符delete来ß例：由new分配的空间。ßdelete y；ßdelete x；分配给*y的空间和分配给一维数组x的空间。ß分别Level 0（6.4）动态二维数组：ß创建类型为Type的动态工作数组，这个数组有rows行和cols列。template <class Type>

23、;void Make2DArray(Type* &x,int rows, int cols)x=new Type*rows; for (int i=0;i<rows;i+)xi=new Typecols;Level 0ß当不再需要一个动态分配的二维数组时，可按以下步骤它所在for循环中为每一行所分配的空间。然后占用的空间。首先为行指针分配的空间。template <class Type>void Delete2DArray(Type* &x,int rows)for (int i=0;i<rows;i+) delete xi;delete x;

24、 x=0;空间后将x置为0，以防继续已被的空间。ßLevel 0算法分析方法ß例：顺序搜索算法template<class Type>int seqSearch(Type *a, int n, Type k)for(int i=0;i<n;i+)if (ai=k) return i; return -1;ß（1）Tmax(n) = max T(I) | size(I)=n =O(n)ß（2）Tmin(n) = min T(I) | size(I)=n =O(1)ß（3）在平均情况下，假设：的概率为p ( 0 £ p

25、£ 1 )；(a) 搜索ß(b) 在数组的每个位置i ( 0 £ i < n )搜索p/n。Tavg (n) =å p(I )T (I )size( I )=n的概率相同，均为ß= æ1× p + 2 × p + 3 × p +L + n × p ö + n × (1 - p)çn ÷nnnèøi + n(1 - p) = p(n + 1) + n(1 - p)n= p ån2i=1算法分析的则ß非递归算法：&

26、#223;（1）for / while 循环ß循环体内计算时间*循环次数；ß（2）嵌套循环ß循环体内计算时间*所有循环次数；ß（3）顺序语句ß各语句计算时间相加；ß（4）if-else语句ßif语句计算时间和else语句计算时间的较大者。template<class Type>void insertion_sort(Type *a, int n)Type key;for (int i = 1; i < n; i+) key=ai;int j=i-1;while( j>=0 && aj&

27、gt;key ) aj+1=aj;j-;aj+1=key;/cost c1 c2 c3 c4 c5c6times nn-1nn-11åtin-1å(t -1)i=1in-1i=1å(ti -1)i=1/c7n-1n-n-n-1(tii=T (n) = c n + c (n -1) + c (n -1) + cti + c(ti -1) + c-1) + c7 (n -1)i=i=ß在最好情况下，ti=1, for 1 £ i <n;Tmin (n) = c1n + c2 (n -1) + c3 (n -1) + c4 (n -1) + c7