1、计算机算法设计与分析（第2版）,王晓东 编著电子工业出版社,第1章 算法概述,学习要点: 理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C+语言描述算法的方法。,算法(Algorithm),算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,程序(Program),程序是算法用某种程序设计
2、语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,问题求解(Problem Solving),理解问题,精确解或近似解选择数据结构算法设计策略,设计算法,算法复杂性分析,算法复杂性 = 算法所需要的计算机资源(量)算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。 （通信带宽）,算法的时间复杂性,（1）最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(
3、I)=n （2）最好情况下的时间复杂性 Tmin(n) = min T(I) | size(I)=n （3）平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。,算法渐近复杂性,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）渐近上界记号OO(g(n) = f(n) | 存在正常数
4、c和n0使得对所有n n0有：0 f(n) cg(n) （2）渐近下界记号 (g(n) = f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n) f(n) ,（3）非紧上界记号o o(g(n) = f(n) | 对于任何正常数c0，存在正数和n0 0使得对所有n n0有：0 f(n)0，存在正数和n0 0使得对所有n n0有：0 cg(n) 0; p(n) = (nd); f(n) = O(nk) f(n)多项式有界； f(n) = O(1) f(n) c; k d p(n) = O(nk) ;k d p(n) = (nk) ;k d p(n) = o(nk) ;k 0: a0
5、=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a1 an为单调递增函数; a1 nb = o(an),ex 1+x;|x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,（5）对数函数 log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0,|x| 1 for x -1,for any a 0, , logbn = o(na),（6）
6、阶乘函数Stirlings approximation,算法分析中常见的复杂性函数,小规模数据,中等规模数据,用c+描述算法,（1）选择语句：（1.1) if 语句：（1.2) ？语句：,if (expression) statement;else statement;,exp1?exp2:exp3 y= x9 ? 100:200; 等价于： if (x9) y=100; else y=200;,（1.3) switch语句：,switch (expression) case 1: statement sequence; break; case 2: statement sequence; b
7、reak; default: statement sequence; ,（2）迭代语句：,（2.1) for 循环： for (init;condition;inc) statement;（2.2) while 循环： while (condition) statement;（2.3) do-while 循环： do statement; while (condition);,（3）跳转语句：,（3.1) return语句： return expression;（3.2) goto语句： goto label; label:,（4）函数：,例：,return-type function nam
8、e(para-list) body of the function ,int max(int x,int y) return xy?x:y; ,（5）模板template ：,template Type max(Type x,Type y) return xy?x:y; int i=max(1,2)；double x=max(1.0,2.0)；,（6）动态存储分配：,（6.1）运算符new ：运算符new用于动态存储分配。 new返回一个指向所分配空间的指针。例：int x；y=new int；y=10；也可将上述各语句作适当合并如下：int y=new int；y=10；或 int y=ne
9、w int(10)；或 int y；y=new int(10)；,（6.2）一维数组 ：,为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。例：float x=new floatn；创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。然后可用x0，x1，xn-1来访问每个数组元素。,（6.3）运算符delete ：,当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运算符delete来释放由new分配的空间。例：delete y；delete x；分别释放分配
10、给y的空间和分配给一维数组x的空间。,（6.4）动态二维数组 ：,创建类型为Type的动态工作数组，这个数组有rows行和cols列。,template void Make2DArray(Type* ,当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放空间后将x置为0，以防继续访问已被释放的空间。,template void Delete2DArray(Type* ,算法分析方法,例：顺序搜索算法,templateint seqSearch(Type *a, int n, Type k) for(in
11、t i=0;in;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）在平均情况下，假设： (a) 搜索成功的概率为p ( 0 p 1 )； (b) 在数组的每个位置i ( 0 i n )搜索成功的概率相同，均为 p/n。,算法分析的基本法则,非递归算法：（1）for / while 循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语
12、句if语句计算时间和else语句计算时间的较大者。,templatevoid insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 / c7 n-1 ,在最好情况下，ti=1, for 1 i n;在最坏情况下，ti i+1, for 1 i n;,对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，由此可见，Tmax(n)= (n2),最优算法,问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。,递归算法复杂性分析,int factorial(int n) if (n = 0) return 1; return n*factorial(n-1); ,课后作业,习题 1-7，1-8，1-10。,
