算法效率分析基础知识概论(PPT 38页).ppt

2-算法效率分析基础 陆伟 College of Software and Microelectronics 算法设计与分析 Introduction to the Design and Analysis of Algorithms * Northwestern Polytechnical University Lecture Overview 1. 算法效率的度量 2. 函数的渐进的界 3. 算法的基本复杂性类型 4.?算法复杂性分析的基本方法 5. 非递归算法的复杂性分析 6. 递归算法的复杂性分析 7. 递归算法与非递归算法比较 8. 经验分析方法 9. 算法可视化 * 算法效率的度量 算法效率的高低体现在运行该算法所需要耗费资源的多少，对于计算机来讲，最重要的资源是时间和空间，因此，算法效率又可分为时间效率和空间效率。 分别用N，I和A表示要解决问题的规模、算法的输入和算法本身，用C表示复杂性，那么，应该有C = F(N, I, A)。如果吧时间复杂性与空间复杂性分开，分别用T和S表示，则T = F(N, I, A)，S = F(N, I, A)。 T = T(N, I)，S = S(N, I)。 * 算法效率的度量 计算机存储容量的发展使得算法空间复杂性已经不再是关注的重点，但时间复杂性仍然十分重要。因此，我们后续也将主要讨论算法的时间复杂性，但是所讨论的方法对于空间复杂性分析也是适用的。 根据T = T(N, I)的概念，它应该是算法在一台“抽象的计算机”上运行所需要的时间。 * 算法效率的度量 设该“抽象的计算机”所提供的元运算有k种，分别记为O1,O2,…,Ok，又设每执行一次这些元运算所耗费的时间分别为t1,t2,…,tk。对于给定算法A，统计其执行过程中用到的元运算Oi的次数，记为ei，i=1,2,…,k。ei = ei (N, I)。 其中，ti是与N和I无关的常数。 * 算法效率的度量 我们不可能对规模为N的每一种合法输入I都去统计ei(N, I)，i=1,2,…,k。 关于摊销效率 * 函数的渐进的界 函数的渐进的界 设f 和g 是定义域为自然数集N上的函数 (1) f(n)=O(g(n)) 若存在正数c和n0使得对一切n≥n0有0≤f(n)≤cg(n) (2) f(n)= Ω(g(n)) 若存在正数c和n0使得对一切n≥n0有0≤cg(n)≤ f(n) (3) f(n)=o(g(n)) 对任意正数c存在n0使得对一切n≥n0有0≤f(n)cg(n) (4) f(n)=ω(g(n)) 对任意正数c存在n0使得对一切n≥n0有0≤cg(n)f(n) (5) f(n)=Θ(g(n)) ? f(n)=O(g(n)) 且f(n)=Ω(g(n)) (6) O(1)表示常数函数 * 函数的渐进的界 * 函数的渐进的界 函数渐进的界的基本性质（1） 设f 和g 是定义域为自然数集N上的函数： （1）若 ，c为大于0的常数，那么 f(n)=Θ(g(n)) （2）若 ，那么 f(n)=o(g(n)) （3）若 ，那么 f(n)=ω(g(n)) * 函数的渐进的界 函数渐进的界的基本性质（2） 设f , g, h 是定义域为自然数集N上的函数： （1）如果f =O(g)且g=O(h)，那么f =O(h). （2）如果 f =Ω(g)且g=Ω(h)，那么f =Ω(h). （3）如果f =Θ(g)和g=Θ(h)，那么f =Θ(h). (4) O(f(n))+O(g(n)) = O(max{f(n),g(n)}) (5) O(f(n))+O(g(n)) = O(f(n)+g(n)) (6) O(f(n))*O(g(n)) = O(f(n)*g(n)) * 函数的渐进的界 函数渐进的界的基本性质（3） 设f , g, h 是定义域为自然数集N上的函数，若对某个其它的函数h, 我们有f =O(h)和g=O(h)，那么 f + g = O(h). 假设f 和g是定义域为自然数集合的函数，且满足g=O(f)，那么 f +g=Θ(f). * 函数的渐进的界 例： 多项式函数f(n)=a0+a1n+a2n2+…+adnd，其中ad≠0，证明f(n)= Θ(nd)。 证明 。 证明logan=Θ(logbn)。 对于b1和α0，logbn=o(nα)，nα=o(bn)。 n!=o(nn)，n!= ω(2n)，log(n!)= Θ(nlogn) * 算法的基本复杂性类型 * 算法复杂