算法效率分析基础精品资料ppt课件.ppt

《算法效率分析基础精品资料ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2-算法效率分析基础陆伟CollegeofSoftwareandMicroelectronics算法设计与分析IntroductiontotheDesignandAnalysisofAlgorithms08August2021NorthwesternPolytechnicalUniversity横氢唱特采每潦淤故目毅堕泛最痞觉肃济勇寞合养苔绿徘非苫嫌捻捻叼薄2-算法效率分析基础CIS550-Database&InfoSystemsLectureOverview1.算法效率的度量2.函数的渐进的界3.算法的基本复杂性类型4. 算法复杂性分析的基本方法5.非递归算法的复杂性分析6.递归算法的复

2、杂性分析7.递归算法与非递归算法比较8.经验分析方法9.算法可视化2藏设敌挑彰裁臃箔涎蒋愈呵雨咬砚扒嘛要冷饯思没溉驶团摆捏惮降伊瘦狈2-算法效率分析基础CIS550-Database&InfoSystems算法效率的度量算法效率的高低体现在运行该算法所需要耗费资源的多少，对于计算机来讲，最重要的资源是时间和空间，因此，算法效率又可分为时间效率和空间效率。分别用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、)。3睫预钧台痘仑谬诽粗剿饲迂替纬瑶骏狗照嫩躁锁练烙陕扒供钾气尉杰费共2-算法效率分析基础CIS550-Database&InfoSystems算法效率的度量计算机存储容量的发展使得算法空间复杂性已经不再是关注的重点，但时间复杂性仍然十分重要。因此，我们后续也将主要讨论算法的时间复杂性，但是所讨论的方法对于空间复杂性分析也是适用的。根据T=T(N,I)的概念，它应该是算法在一台“抽象的计算机”上运行所需要的时间。4云椒避障试午洲栋辞飞渭瓦刷洗换前斯舰钙寂骆凌徐肢蛋抨巾邻枢疲焰改2-算法效率分析基础CIS550-Database&InfoSystems算法效率的度量设该“抽象的计算机”所提供

4、的元运算有k种，分别记为O1,O2,…,Ok，又设每执行一次这些元运算所耗费的时间分别为t1,t2,…,tk。对于给定算法A，统计其执行过程中用到的元运算Oi的次数，记为ei，i=1,2,…,k。ei=ei(N,I)。其中，ti是与N和I无关的常数。5仲层籍肘畴症尹羊贬铂挽羊唁疽鸭配纽洗透晓革嗽亚吴厌桩拴砂纬淤鲜异2-算法效率分析基础CIS550-Database&InfoSystems算法效率的度量我们不可能对规模为N的每一种合法输入I都去统计ei(N,I)，i=1,2,…,k。关于摊销效率6垢秒遁惦鸳憎醇叭诌睡计笔淋劣静歌最假喳牟撇官躲蔽诽森外灭袱居肛冷2-算法效率分析基础CIS550

5、-Database&InfoSystems函数的渐进的界函数的渐进的界设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)

6、敌乾凳哄曲决僻盎舅矿三作我停坞描舟锥茨髓诬崭寡峨缔佑摆蜡2-算法效率分析基础CIS550-Database&InfoSystems函数的渐进的界8嫩聚谈猪沦狰酬丁诬贷辨透均荧喳吐革臀皑惭谁宪品搪皿掀檬撮荧鸿撅酉2-算法效率分析基础CIS550-Database&InfoSystems函数的渐进的界函数渐进的界的基本性质（1）设f和g是定义域为自然数集N上的函数：（1）若，c为大于0的常数，那么f(n)=Θ(g(n))（2）若，那么f(n)=o(g(n))（3）若，那么f(n)=ω(g(n))9邑谈册总曝击知爽赣嗓读谊铁弱薪娥辜宵磐检荧仰冻嘘镰棚格窖枉弄畅压2-算法效率分析基础CIS550-

7、Database&InfoSystems函数的渐进的界函数渐进的界的基本性质（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)