文档介绍：该【算法效率分析基础知识概论】是由【zhangkuan1439】上传分享，文档一共【38】页，该文档可以免费在线阅读，需要了解更多关于【算法效率分析基础知识概论】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2-算法效率分析基础
陆伟
CollegeofSoftwareandMicroelectronics
算法设计与分析
IntroductiontotheDesignandAnalysisofAlgorithms
12March2023
NorthwesternPolytechnicalUniversity
LectureOverview

2
算法效率的的度量
算法效率的的高低体现现在运行该该算法所需需要耗费资资源的多少少,对于计计算机来讲讲,最重要要的资源是是时间和空空间,因此,算法法效率又可可分为时间效率和空间效率。
分别用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