第1章算法概述

关于本课程l课程目的：计算机算法设计与分析导引¡以算法设计为主，介绍算法设计的主要方法和基本思以算法设计为主，介绍算法设计的主要方法和基本思想；并简要介绍算法分析概念想；并简要介绍算法分析概念¡不是程序设计课，也不是数学课不是程序设计课，也不是数学课l授课形式：上课+作业/实验+期末考试l参考资料：¡Web资源 , , …¡图书资源 , …1第1章 算法概述l本章知识要点：¡1.1 算法与程序¡1.2 算法与数据结构¡1.3 表达算法的抽象机制¡1.4 描述算法与算法设计¡1.5 算法分析的基本原则¡1.6 算法复杂性分析¡C++程序语言描述算法l计划授课时间：4课时21.1 算法与程序l算法：是满足下述性质的指令序列¡输入输入：有零个或多个外部量作为算法的输入 ¡输出输出：算法产生至少一个量作为输出 ¡确定性确定性：组成算法的每条指令清晰、无歧义 ¡有限性有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限l程序：¡程序是算法用某种程序设计语言的具体实现¡程序可以不满足算法的性质程序可以不满足算法的性质(4)即有限性即有限性¡例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。

操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现该子程序得到输出结果后便终止31.2 算法与数据结构l描述算法可以有多种方式¡自然语言方式、表格方式、图示形式等¡本书将采用C++与自然语言与自然语言相结合的方式l算法与数据结构的关系¡不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；¡反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础l算法＋数据结构＝程序算法＋数据结构＝程序41.3 表达算法的抽象机制1.从机器语言到高级语言的抽象¡高级程序设计语言的主要好处是：1)高级语言更接近算法语言，易学、易掌握易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；2)高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可可读性好，可维护性强，可靠性高靠性高；3)高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高可植性好、重用率高；4)把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。

51.3 表达算法的抽象机制2.抽象数据类型¡抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算¡抽象数据类型带给算法设计的好处有：1)算法顶层设计与底层实现分离顶层设计与底层实现分离；2)算法设计与数据结构设计隔开，允许数据结构自由选择；3)数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；4)用抽象数据类型表述的算法具有很好的可维护性可维护性；5)算法自然呈现模块化模块化；6)为自顶向下逐步求精自顶向下逐步求精和模块化模块化提供有效途径和工具；7)算法结构清晰结构清晰，层次分明层次分明，便于算法正确性的证明正确性的证明和复复杂性的分析杂性的分析61.4 描述算法与算法设计l描述算法可以有多种方式，如自然语言方式、图形表格方式等在这里，我们将采用C++语言语言来描述算法¡C++语言的优点是类型丰富、语句精炼，具有面向对象面向对象和面向过程面向过程的双重优点¡用C++来描述算法可使整个算法结构紧凑、可读性强¡在课程中，有时为了更好地阐明算法的思路，我们还采用C++与自然语言相结合的方式来描述算法¡算法设计方法主要有：分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。

71.4 描述算法与算法设计l问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法81.5 算法分析的基本原则1.正确性正确性¡定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的¡正确性证明的内容：l方法的方法的正确性证明——算法思路的正确性证明一系列与算法的工作对象有关的引理、定理以及公式l程序的程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作¡程序正确性证明的方法：l大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证l小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等91.5 算法分析的基本原则2.工作量工作量——时间复杂性分析¡计量工作量的标准: 对于给定问题，该算法所执行的基本运算的次数¡基本运算的选择：根据问题选择适当的基本运算101.5 算法分析的基本原则3.占用空间占用空间——空间复杂性分析¡两种占用：l存储程序和输入数据的空间l存储中间结果或操作单元所占用空间——额外空间¡影响空间的主要因素：l存储程序的空间一般是常数(和输入规模无关)l输入数据空间为输入规模O(n)¡空间复杂性考虑的是额外空间的大小¡如果额外空间相对于输入规模是常数，称为原地工作的算法。

111.5 算法分析的基本原则4.简单性简单性¡含义：算法简单，程序结构简单¡好处：l容易验证正确性l便于程序调试¡简单的算法效率不一定高要在保证一定效率的前提下力求得到简单的算法3n+1问题问题While(n>1) if (odd(n)) n=3n+1; else n=n/2;在最坏情况下，该算法的计算时间下界为Ω(logn). 但其计算时间上界至今未知即该算法是否在有限时间内结束？日本学者米田信夫验证了1013内的自然数这就是Collatz猜想121.5 算法分析的基本原则5.最优性最优性¡含义：指求解某类问题中效率最高的算法 ¡两种最优性l最坏情况最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法l平均情况平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法 ¡寻找最优算法的途径 (以最坏情况下的最优性为例)l设计算法A，求W(n)。

相当于对问题给出最坏情况下的一个上界l寻找函数F(n)，使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算 相当于对问题给出最坏情况下所需基本运算次数的一个下界l如果W(n)=F(n)，则A是最优的l如果W(n)>F(n)，A不是最优的或者F(n)的下界过低•改进A或设计新算法A’使得W’(n)F(n)•重复以上两步，最终得到W’(n) = F’(n)为止131.5 算法分析的基本原则¡例：在n个不同的数中找最大的数¡基本运算：比较¡算法：Find Max¡输入：数组L，项数 n 1 1¡输出：L中的最大项MAX1)MAX←L(1); i←2;2)while i≤n do3)if MAX

¡结论：Find Max算法是最优算法141.6 算法复杂性分析l算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)l一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 通常，让A隐含在复杂性函数名当中）算法复杂性 = 算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)其中n是问题的规模（输入大小）151.6 算法复杂性分析l以上分别是最坏情况下、最好情况下和平均情况下的时间复杂性l其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到TMax(N)的合法输入；I-是DN中使T(N, I-)达到TMin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率16算法的时间复杂性算法的时间复杂性l（1）最坏情况最坏情况下的时间复杂性l Tmax(n) = max{ T(I) | size(I)=n }l（2）最好情况最好情况下的时间复杂性l Tmin(n) = min{ T(I) | size(I)=n }l（3）平均情况平均情况下的时间复杂性l Tavg(n) =l 其中I是问题的规模为n的实例，p(I)是实例I出现的概率。

171.6 算法复杂性分析l函数的渐进性态与渐进表达式：一般来说，当N单调增加且趋于∞时，T(N)也将单调增加趋于∞l对于T(N)，如果存在函数T'(N)，使得当N→ ∞使有(T(N)-T'(N))/T(N) →0，那么我们就说T'(N)是T(N)当N→ ∞时的渐进性态l在数学上，T'(N)是T(N)当N→ ∞时的渐进表达式l例如：3N2+4NlogN+7与3N218算法渐近复杂性算法渐近复杂性lT(n)  , as n ;l(T(n) - t(n) )/ T(n) 0 ，as n;lt(n)是T(n)的渐近性态，为算法的渐近复杂性l在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项它比T(n) 简单191.6 算法复杂性分析l算法复杂性在渐近意义下的阶：¡渐近意义下的记号：O、Ω、θ、o、ω¡设f(N)和g(N)是定义在正数集上的正函数20渐近分析的记号渐近分析的记号l在下面的讨论中，对所有n，f(n)  0，g(n)  0l（1）渐近上界记号渐近上界记号OlO(g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0  f(n)  cg(n) }l（2）渐近下界记号渐近下界记号  l (g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n)  f(n) }21O渐近例子渐近例子1.F(N)=3N2.F(N)=N+10243.F(N)=2N2+11N-104.F(N)=N2O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有：0  f(n)  cg(n) }22l（3）非紧上界记号非紧上界记号o lo(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n n0有：0  f(n)

l（4）非紧下界记号非紧下界记号  l (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n n0有：0  cg(n) < f(n) }l等价于 f(n) / g(n)  ，as nlf(n)   (g(n))  g(n)  o (f(n)) 23l（5）紧渐近界记号紧渐近界记号  l (g(n)) = { f(n) | 存在正常数c1,c2和n0使得对所有n n0有：c1g(n)  f(n)  c2g(n) }l 定理定理1：：  (g(n)) = O (g(n))   (g(n)) 24渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义lf(n)= (g(n))的确切意义是：f(n)  (g(n))l一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的某个函数l例如：2n2 + 3n + 1 = 2n2 + (n) 表示l 2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某个函数l等式和不等式中渐近记号O,o, 和的意义是类似的。

25渐近分析中函数比较渐近分析中函数比较lf(n)= O(g(n))  a  b;lf(n)= (g(n))  a  b;lf(n)= (g(n))  a = b;lf(n)= o(g(n))  a < b;lf(n)= (g(n))  a > b.26渐近分析记号的若干性质渐近分析记号的若干性质l（（1）传递性：）传递性：lf(n)= (g(n))， g(n)= (h(n))  f(n)= (h(n))；lf(n)= O(g(n))， g(n)= O (h(n))  f(n)= O (h(n))；lf(n)= (g(n))， g(n)=  (h(n))  f(n)= (h(n))；lf(n)= o(g(n))， g(n)= o(h(n))  f(n)= o(h(n))；lf(n)= (g(n))， g(n)=  (h(n))  f(n)=  (h(n))；27l（（2）反身性：）反身性：lf(n)= (f(n))；lf(n)= O(f(n))；lf(n)= (f(n)).l（（3）对称性：）对称性：lf(n)= (g(n))  g(n)=  (f(n)) .l（（4）互对称性：）互对称性：lf(n)= O(g(n))  g(n)=  (f(n)) ；lf(n)= o(g(n))  g(n)=  (f(n)) ；28l（（5）算术运算：）算术运算：lO(f(n))+O(g(n)) = O(max{f(n),g(n)}) ；lO(f(n))+O(g(n)) = O(f(n)+g(n)) ；lO(f(n))*O(g(n)) = O(f(n)*g(n)) ；lO(cf(n)) = O(f(n)) ；lg(n)= O(f(n))  O(f(n))+O(g(n)) = O(f(n)) 。

29l规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明：证明：l对于任意f1(n)  O(f(n)) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n)  c1f(n) l类似地，对于任意g1(n)  O(g(n)) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n)  c2g(n) l令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} l则对所有的 n  n3，有lf1(n) +g1(n)  c1f(n) + c2g(n)  c3f(n) + c3g(n)= c3(f(n) + g(n))  c32 max{f(n),g(n)} = 2c3h(n) = O(max{f(n),g(n)}) .30算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数l（（1）单调函数）单调函数l单调递增：m  n  f(m)  f(n) ;l单调递减：m  n  f(m)  f(n);l严格单调递增：m < n  f(m) < f(n);l严格单调递减：m < n  f(m) > f(n).l（（2）取整函数）取整函数l  x  ：不大于x的最大整数；l  x  ：不小于x的最小整数。

31取整函数的若干性质取整函数的若干性质l x-1 <  x   x   x  < x+1；l  n/2  +  n/2  = n;l 对于n  0，a,b>0，有：l   n/a  /b  =  n/ab  ;l   n/a  /b  =  n/ab  ;l  a/b   (a+(b-1))/b;l  a/b   (a-(b-1))/b;l f(x)=  x  , g(x)=  x  为单调递增函数32l（（3）多项式函数）多项式函数l p(n)= a0+a1n+a2n2+…+adnd； ad>0;l p(n) = (nd);l f(n) = O(nk)  f(n)多项式有界；l f(n) = O(1)  f(n)  c;l k  d  p(n) = O(nk) ;lk  d  p(n) = (nk) ;lk > d  p(n) = o(nk) ;lk < d  p(n) = (nk) .33l（（4）指数函数）指数函数l 对于正整数m,n和实数a>0:l a0=1;l a1=a ;l a-1=1/a ;l (am)n = amn ; l(am)n = (an)m ; l aman = am+n ;l a>1  an为单调递增函数;l a>1   nb = o(an)34lex  1+x;l|x| 1  1+x  ex  1+x+x2 ;l ex = 1+x+ (x2), as x0;35l（（5）对数函数）对数函数l log n = log2n;l lg n = log10n;l ln n = logen;l logkn = (log n)kl;l log log n = log(log n);l for a>0,b>0,c>03637l|x| 1 lfor x > -1,lfor any a > 0, ,  logbn = o(na)38l（（6）阶层函数）阶层函数lStirling’s approximation 3940算法分析中常见的复杂性函数算法分析中常见的复杂性函数41小规模数据小规模数据42中等规模数据中等规模数据43用用c++描述算法描述算法44l（（1）选择语句：）选择语句：l（（1.1) if 语句：语句：l（（1.2) ？语句：？语句：l if (expression) statement;else statement; exp1?exp2:exp3 y= x>9 ? 100:200; 等价于： if (x>9) y=100; else y=200;45（（1.3) switch语句：语句：switch (expression) { case 1: statement sequence; break; case 2: statement sequence; break;  default: statement sequence; }46（（2）迭代语句：）迭代语句：l（（2.1) for 循环：循环：l for (init;condition;inc) statement;l（（2.2) while 循环：循环：l while (condition) statement;l（（2.3) do-while 循环：循环： l do{l statement;l } while (condition); 47（（3）跳转语句：）跳转语句：l（（3.1) return语句：语句：l return expression;l（（3.2) goto语句：语句： l goto label;l  l label:48（（4）函数：）函数：l例：例： return-type function name(para-list){ body of the function } int max(int x,int y) { return x>y?x:y; } 49（（5）模板）模板template ：：template Type max(Type x,Type y){ return x>y?x:y;} int i=max(1,2)；double x=max(1.0,2.0)；50（（6）动态存储分配：）动态存储分配：l（（6.1）运算符）运算符new ：：l运算符new用于动态存储分配。

lnew返回一个指向所分配空间的指针l例：int x；y=new int；y=10；l也可将上述各语句作适当合并如下：lint y=new int；y=10；l或 int y=new int(10)；l或 int y；y=new int(10)；51（（6.2）一维数组）一维数组 ：：l为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针然后用new为数组动态地分配存储空间l例：例：lfloat x=new float[n]；l创建一个大小为n的一维浮点数组运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针l然后可用x[0]，x[1]，…，x[n-1]来访问每个数组元素52（（6.3）运算符）运算符delete ：：l当动态分配的存储空间已不再需要时应及时释放所占用的空间l用运算符delete来释放由new分配的空间l例：例：ldelete y；ldelete [ ]x；l分别释放分配给y的空间和分配给一维数组x的空间53（（6.4）动态二维数组）动态二维数组 ：：l创建类型为Type的动态工作数组，这个数组有rows行和cols列。

template void Make2DArray(Type** &x,int rows, int cols){ x=new Type*[rows]; for (int i=0;ivoid Delete2DArray(Type** &x,int rows){ for (int i=0;iint seqSearch(Type *a, int n, Type k){ for(int i=0;i

57算法分析的基本法则算法分析的基本法则l非递归算法：非递归算法：l（1）for / while 循环l循环体内计算时间*循环次数；l（2）嵌套循环l循环体内计算时间*所有循环次数；l（3）顺序语句l各语句计算时间相加；l（4）if-else语句lif语句计算时间和else语句计算时间的较大者58templatevoid insertion_sort(Type *a, int n){ Type key; // cost times for (int i = 1; i < n; i++){ // c1 n key=a[i]; // c2 n-1 int j=i-1; // c3 n-1 while( j>=0 && a[j]>key ){ // c4 sum of ti a[j+1]=a[j]; // c5 sum of (ti-1) j--; // c6 sum of (ti-1) } a[j+1]=key; // c7 n-1 }}59l在最好情况下，ti=1, for 1  i

因此，l由此可见，Tmax(n)= (n2)61最优算法最优算法l问题的计算时间下界为(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法l例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法l堆排序算法是最优算法62递归算法复杂性分析递归算法复杂性分析l int factorial(int n)l {l if (n == 0) return 1; l return n*factorial(n-1);l }63精品课件精品课件！64精品课件精品课件！65HomeworklP5¡1.算法分析题 1-1,1-2,1-4,1-6,1-9¡2.算法实现题 1-1,1-3,1-4,1-566。