- 1、本文档共39页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法性能分析与度量 算法的时间复杂度 大O表示法:若存在两个正的常数c和n0,对于任意n≥n0,都有T(n) ≤ c×f(n),则称T(n)=O(f(n)) * n0 问题规模n 执行次数 n0之前的情况无关紧要 T(n) c×f(n) 表示当问题规模充分大时 在渐进意义下的阶 算法性能分析与度量 算法的时间复杂度 大O表示法:若存在两个正的常数c和n0,对于任意n≥n0,都有T(n) ≤ c×f(n),则称T(n)=O(f(n)) 例1:T(n) = 3n+2 当n≥2时,3n+2 ≤ 3n+n = 4n 因此T(n)=O(n) * 算法性能分析与度量 算法的时间复杂度 大O表示法:若存在两个正的常数c和n0,对于任意n≥n0,都有T(n) ≤ c×f(n),则称T(n)=O(f(n)) 例2:T(n) = 10n2+4n+2 当n≥2时,10n2+4n+2 ≤ 10n2+5n 又有当n≥5时,10n2+5n ≤ 10n2+n2 = 11n2 因此T(n)=O(n2) * 算法性能分析与度量 算法的时间复杂度 大O表示法:若存在两个正的常数c和n0,对于任意n≥n0,都有T(n) ≤ c×f(n),则称T(n)=O(f(n)) 作业:求解T(n) = amnm+am-1nm-1+ ??? a2n2+a1n+a0,并给出证明过程 * 算法性能分析与度量 算法的时间复杂度 T(n)=O(f(n)) 若存在两个正的常数c和n0,对于任意n≥n0,都有T(n) ≤ c×f(n),则称T(n)=O(f(n)) 给出算法复杂度的上界,不可能比c*f(n)更大 例:T(n) = 6*2n+n2 当n≥4时,6*2n+n2 ≤ 6*2n+2n = 7*2n 因此T(n)=O(2n) * 算法性能分析与度量 算法的时间复杂度 T(n)=Ω(f(n)) 若存在c 0,和正整数n0≥1,使得当n≥n0时,有T(n)≥c*f(n)成立。 给出算法复杂度的下界,不可能比c*f(n)更小 例: T(n)=3n3+2n2,取c=3,n0=1,f(n)=n3,则当 n≥n0(=1)时,有3n3+2n2≥3n3,∴T(n)=Ω(n3) * 算法性能分析与度量 算法的时间复杂度 T(n)=?(f(n)) 若存在c1,c20,和正整数n0≥1,使得当n≥n0时,总有 T(n)≤c1*f(n)且T(n)≥c2*f(n)成立,即T(n)=O(f(n))与T(n)=Ω(f(n))都成立。 给出了算法时间复杂度的上界和下界 e.g.T(n)= 3n3+2n2,c1=5,取c2=3,n0=1,f(n)=n3,则当n≥n0(=1)时,有3n3+2n2≤5n3及3n3+2n2≥3n3(无穷多个),∴T(n)= ? (n3) * 算法性能分析与度量 算法的时间复杂度 常见的时间复杂度 Ο(1)≤Ο(log2n) ≤Ο(n) ≤Ο(nlog2n) ≤Ο(n2) ≤Ο(n3) ≤…≤Ο(2n) ≤Ο(n!) * T(n) n 0 2n n3 n n2 logn 算法性能分析与度量 算法的空间复杂度 指算法在执行过程中所需最大存储空间 空间复杂性的渐进分析 * S(n)=O(f(n)) O(log2n) ?= O(log3n) O(2n) ?= O(3n) 狭义上,信息是符号的排列的顺序(来自wiki) 一般指数据、消息中所包含的意义(来自wiki) * 狭义上,信息是符号的排列的顺序(来自wiki) 一般指数据、消息中所包含的意义(来自wiki) * 狭义上,信息是符号的排列的顺序(来自wiki) 一般指数据、消息中所包含的意义(来自wiki) * 狭义上,信息是符号的排列的顺序(来自wiki) 一般指数据、消息中所包含的意义(来自wiki) * 令m=kn+r,假设x是(m,n)的公约数,则x也可以被r整除,因此也是(n,r)的公约数 反之有假设x是(n,r)的公约数,x也是(m,n)的公约数。因此是等价的 * 令m=kn+r,假设x是(m,n)的公约数,则x也可以被r整除,因此也是(n,r)的公约数 反之有假设x是(n,r)的公约数,x也是(m,n)的公约数。因此是等价的 * * 数据结构 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 课程说明 课程编号授课学时:32学时(1至16周,2学时/周) 课程分类:选修 答疑地点:计算机楼532,每周1次(周一上午) 考核形式: 期末笔试80%+平时成绩20% 期末考试实行开卷方式 作业: 从布置作业起,到下一次课前两天(周日23:00) 电子版,提交到教务处网站上的课程中心 文件命名肖迪),文件格式(.pdf、.doc、.do
您可能关注的文档
- 收房时要先看开发商的“三书一证一表”解读.doc
- 收费人员岗前培训应知应会手册4正文解读.doc
- 收费系统收费文明服务管理标准解读.docx
- 数的顺序和组成解读.pptx
- 数电chapter9解读.ppt
- 数电复习要点解读.ppt
- 数电实验报告实验二利用MSI设计组合逻辑电路解读.docx
- 数据仓库1解读.ppt
- 数据仓库解决方案概述解读.ppt
- 数据仓库实验二解读.docx
- 《GB/Z 44363-2024致热性 医疗器械热原试验的原理和方法》.pdf
- GB/T 16716.6-2024包装与环境 第6部分:有机循环.pdf
- 中国国家标准 GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 《GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统》.pdf
- GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 中国国家标准 GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 44305.2-2024塑料 增塑聚氯乙烯(PVC-P)模塑和挤塑材料 第2部分:试样制备和性能测定.pdf
- 《GB/T 44315-2024科技馆展品设计通用要求》.pdf
- GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 39560.9-2024电子电气产品中某些物质的测定 第9 部分:气相色谱-质谱法(GC-MS)测定聚合物中的六溴环十二烷.pdf
最近下载
- 理财教材《小狗钱钱》.pdf
- 护理品管圈问题解决型之提高慢性肾功能不全患者饮食指导知晓率.pptx VIP
- 复旦投毒案林森浩(详细的参考资料整理).docx
- Axure RP原型设计图解微课视频教程(Web+App)(刘刚)PPT全套完整教学课件.pptx
- 2024年国家电网招聘之财务会计类题库附参考答案(轻巧夺冠).docx
- 1精益管理倡导者培训.pptx
- 整本书阅读 《朝花夕拾》(同步课件) 七年级语文上册(统编版2024).pptx
- 2024-2029年中国房地产投资行业发展分析及投资风险预警与发展策略研究报告.docx
- 文旅融合背景下的文化遗产活化措施.pptx VIP
- 非物质文化遗产活化策略PPT.pptx VIP
文档评论(0)