文档介绍：2-算法效率分析基础陆伟CollegeofSoftwareandMicroelectronics算法设计与分析IntroductiontotheDesignandAnalysisofAlgorithms*. ,对于计算机来讲,最重要的资源是时间和空间,因此,算法效率又可分为时间效率和空间效率。分别用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)。3算法效率的度量计算机存储容量的发展使得算法空间复杂性已经不再是关注的重点,但时间复杂性仍然十分重要。因此,我们后续也将主要讨论算法的时间复杂性,但是所讨论的方法对于空间复杂性分析也是适用的。根据T=T(N,I)的概念,它应该是算法在一台“抽象的计算机”上运行所需要的时间。4算法效率的度量设该“抽象的计算机”所提供的元运算有k种,分别记为O1,O2,…,Ok,又设每执行一次这些元运算所耗费的时间分别为t1,t2,…,tk。对于给定算法A,统计其执行过程中用到的元运算Oi的次数,记为ei,i=1,2,…,k。ei=ei(N,I)。其中,ti是与N和I无关的常数。5算法效率的度量我们不可能对规模为N的每一种合法输入I都去统计ei(N,I),i=1,2,…,k。关于摊销效率6函数的渐进的界函数的渐进的界设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)表示常数函数7函数的渐进的界8函数的渐进的界函数渐进的界的基本性质(1)设f和g是定义域为自然数集N上的函数:(1)若,c为大于0的常数,那么f(n)=Θ(g(n))(2)若,那么f(n)=o(g(n))(3)若,那么f(n)=ω(g(n))9函数的渐进的界函数渐进的界的基本性质(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))10