数据结构与算法 课件 第一章绪论.ppt

渐近时间复杂度考查增长函数时，只关心增长函数表达式中的主项，并且不再考虑主项的系数表达式的主项使用记号O来表示例1.4中增长函数表示为O(n)例1.5中增长函数表示为O(n2)这称为渐近时间复杂度，也称为算法的阶定义定义1-2称（复杂度）函数T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常数c0与n0，当nn0时有T(n)≤cf(n)T1(n)=(n+1)/2=O(n2)T2(n)=3n2+4n+5=O(n3)当然T1(n)=O(n2)，T2(n)=O(n3)也是对的，但一般取最低阶表示T(n)=O(f(n))说明T(n)的阶不大于f(n)的阶定义定义1-3称（复杂度）函数T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常数c0与n0，当nn0时有T(n)≥cf(n)T1(n)=(n+1)/2=Ω(n)T2(n)=3n2+4n+5=Ω(n2)当然T1(n)=Ω(1)，T2(n)=Ω(n)，T2(n)=Ω(nlogn)也都是对的，同样地，取它们之中的最高阶T(n)=Ω(f(n))说明T(n)的阶不小于f(n)的阶大O表示法和大Ω表示法使我们能够描述某一算法的上限（如果能找到某一类输入下开销最大的函数）和下限（如果能找到某一类输入下开销最小的函数）当上、下限相等时，可用Θ表示法。如果一种算法既是O(f(n))，又是Ω(f(n))，则称其是Θ(f(n))的若增长函数不随算法问题规模变化，则增长函数称为O(1)阶，或称常数复杂度与问题规模成正比的问题求解算法称为线性操作许多算法具有log2n对数复杂度其他的算法有n的某次幂的多项式复杂度，如O(n2)或O(n3)更坏的算法是指数复杂度，n是指数，如O(2n)一些增长函数的渐近时间复杂增长函数阶时间复杂度T(n)=17O(1)常数T(n)=20n-4O(n)线性T(n)=12nlogn+100nO(nlogn)线性对数T(n)=3n2+5n-2O(n2)多项式（平方）T(n)=2n+18n2+3nO(2n)指数示例?上述程序的时间复杂度是（）A．O(log2n) B．O(n)C．O(nlog2n) D．O(n2)解：答案是B程序段intx=m;while(x1){ x=x/2;}其中m1，则时间复杂度为（）A．O(logm) B．O(m2)C．O(m1/2) D．O(m1/3)解：答案是A?若处理器速度增长10倍??算法时间复杂度提升前最大问题规模提升后最大问题规模A1O(n)s110s1A2O(n2)s23.16s2A3O(n3)s32.15s3A4O(2n)s4s4+3.3除了要评判算法的时间复杂度外，算法在运行过程中临时占用的空间大小也要考虑，这称为空间复杂度。一般地，空间复杂度也表示为问题规模的一个函数。考虑空间存储量时，算法代码占用的空间、算法中初始数据占用的存储空间，都不包含在内第三节算法设计策略简介算法可以分为多种不同的类型，每种类型都有特定的应用场景和解决问题的方法设计算法时，可以配合采用一些设计策略，使得算法的实现更方便设计策略有时也可以称为设计方法，是指在解决特定问题时所采用的一类方法算法分为递推法、迭代法、递归法、贪心法、分治法、动态规划法等递推法递推法是一种直接求解的算法设计策略，利用问题本身所具有的一种递推关系进行求解。找到问题本身的递推关系是问题求解的前提递推法的思想是，根据递推关系，能从已求得的问题规模为1,2,…,i-1的一系列解，构造出问题规模为i的解。求解规模为i的解时，有时可能仅需规模为1,2,…,i-1的系列解中的一部分，而不是全部示例由递推公式可计算出数列的第三项，为2再由第二项和第三项，得到第四项的值3再由第三项和第四项，得到第五项的值5以此类推得到数列的前10项为：1,1,2,3,5,8,13,21,34,55程序迭代法是一种直接求解的方法，往往需要建立迭代关系式即根据前一个值推出下一个值的公式初始时设定初始值（原值），然后根据迭代关系式和原值，求出新值，并用新值替代原值迭代过程不能无限进行下去或者设定一个迭代次数，当达到这个次数时迭代过程停止或者设定一个结束条件，当满足这个条件时，迭代过程停止程序递归法贪心法贪心算法也称贪婪算法，这是一种通过每一步选择局部最优解来达到整体最优解的算法，适用于求某些最优解问题求解过程中，一步一步地进行，根据当前的情况选择最优的可能实际上，这个最优是在当前条件下的最优，称为局部最优第四章构造哈夫曼树的过程采用了贪心