《第1章 算法概述-3.14》由会员分享，可在线阅读，更多相关《第1章 算法概述-3.14（52页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析,第1章 算法概述,2017/11/21,算法设计与分析 第1章 算法概论,2,第1章 算法概述,理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C+语言描述算法的方法。,2017/11/21,算法设计与分析 第1章 算法概论,3,算法(Algorithm) 1.1 算法与程序,算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有零个或者多个外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：
2、算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,2017/11/21,算法设计与分析 第1章 算法概论,4,程序(Program),程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,2017/11/21,算法设计与分析 第1章 算法概论,5,问题求解(Problem Solving),理解问题,精确解或近似解选择数据结构算法设计策略,设计算法,2017/11/21,算法
3、设计与分析 第1章 算法概论,6,1.2 算法复杂性分析,算法复杂性 = 算法所需要的计算机资源算法的时间复杂性；算法的空间复杂性。,C = F( N, I, A),算法复杂性,函数,算法要解问题的规模,算法的输入,算法本身,一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I) 。通常让A隐含在复杂性函数名中。,2017/11/21,算法设计与分析 第1章 算法概论,7,设一台抽象计算机提供的元运算有k种，分别记作：O1, O2,Ok ，设这些元运算每执行一次所需时间分别为t1,t2,tk，设算法A中使用Oi的次数为ei, i=1,k，记作ei=ei
4、(N, I)，则得到：,精确，但不具备可操作性！,不能准确地计算算法的具体执行时间；不可能对规模为N的每一种合法输入I都去统计其具体执行次数ei。,将复杂性函数具体化,2017/11/21,算法设计与分析 第1章 算法概论,8,解决方法,最坏情况、最好情况和平均情况下的时间复杂性。其中：DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到TMax(N)的合法输入；I是DN中使T(N, I)达到TMin(N)的合法输入；P(I)是在算法的应用中出现输入I的概率。,2017/11/21,算法设计与分析 第1章 算法概论,9,算法的时间复杂性分析,（1）最坏情况下的时间复杂性 Tmax
5、(n) = max T(I) | size(I)=n （2）最好情况下的时间复杂性 Tmin(n) = min T(I) | size(I)=n （3）平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实例I出现的概率。,2017/11/21,算法设计与分析 第1章 算法概论,10,举例：顺序查找,templateint seqSearch(Type *a, int n, Type k) for (int i=0;in;i+) if (ai=k) return i; return -1;,查找51,2017/11/21,算法设计与分析 第1章 算法概论,11,
6、与机器无关的时间效率分析,（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 0，则f(n)=O(nm)。,2017/11/21,算法设计与分析 第1章 算法概论,19,关于渐近上界记号O的举例,因为对所有n1有3n4n，所以有3n=O(n)；因为当n1时有n+10241025n，所以有n+1024=O(n)；因为当n10时有2n2+11n-103n2，所以有2n2+11n-
7、10=O(n2)；因为对所有n1有n2n3，所以有n2=O(n3)。,2017/11/21,算法设计与分析 第1章 算法概论,20,渐近上界记号O的运算规则,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) ；O(cf(n) = O(f(n) ；g(n)= O(f(n) O(f(n)+O(g(n) = O(f(n) 。,2017/11/21,算法设计与分析 第1章 算法概论,21,渐近上界记号O的运算规则,证明： O(f(n)+O(g(n) = O(maxf(n),g
8、(n) ；,证明：对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n) c1f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。则对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .,2017/
9、11/21,算法设计与分析 第1章 算法概论,22,渐近下界记号,f(n)的增长至少象g(n)那样快，表示解一个特定问题的任何算法的时间下界。f(n)的阶是(g(n) ，当且仅当g(n)的阶是O(f(n) 。,2017/11/21,算法设计与分析 第1章 算法概论,23,关于渐近下界记号的结论,记号可以看作是n的函数的集合。(g(n)表示所有增长阶数不低于g(n) 函数的集合，它用以表示一个算法运行时间的下界。称一个算法具有(g(n)的运行时间，是指当n足够大时，该算法的实际运行至少需要g(n)的某个常数倍的时间量。与大O记号类似，对于给定的f，可有无数个g与之对应。例如，f(n)=10n2+
10、4n+2，g可以是：n2, n1, n1/2, 。应当选择最接近的函数g，即f的最大下界。,定理：如果f(n)=amnm+ am-1nm-1 + a1n+a0是m次多项式，且am0，则f(n)=(nm)。,2017/11/21,算法设计与分析 第1章 算法概论,24,关于渐近下界记号的结论,的定义的优点是与O的定义对称，缺点是当f(N)对自然数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画出f(N)的下界。,比如当时，如果按上述定义，只能得到f(N)=(1)，这是一个平凡的下界，对算法分析没有什么价值。,2017/11/21,算法设计与分析 第1章 算法概论,25,2. 渐近分析的记号,（3）非紧上界记号o o(g(n) = f(n) | 对于任何正常数c0，存在正数和n0 0使得对所有n n0有：0 f(n)0，存在正数和n0 0使得对所有n n0有：0 cg(n) f(n) 等价于 f(n) / g(n) ，as n。f(n) (g(n) g(n) o (f(n),2017/11/21,算法设计与分析 第1章 算法概论,26,2. 渐近分析的记号,（5）紧渐近界记号 (g(n) = f(n) | 存在正常数c1,c2和n0使得对所有n n0有：c1g(n) f(n) c2g(n) ,
