- 1、本文档共39页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构_01_引言讲述
算法性能分析与度量 算法的时间复杂度 大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
您可能关注的文档
- 数据库系统5版2016chp032讲述.pptx
- CAD11图形数据的查询与共享解读.ppt
- 数据库技术复习2014讲述.ppt
- 数据库系统UML建模案例演示讲述.ppt
- CACTI网管平台基本介绍解读.ppt
- CA6140车床输出轴___机械制造工艺与夹具课程设计解读.doc
- c++课件树和二叉树解读.ppt
- Cad2007教程(适合零基础)解读.doc
- 数据库系统与应用模拟试卷和答案讲述.doc
- CAD2010快捷键大全解读.doc
- 2025年云南省玉溪市江川县初三下月考(4月)生物试题试卷含解析.doc
- 抚顺市重点中学2025年初三下-第八次质量检测试题生物试题试卷含解析.doc
- 江苏省无锡市金星中学2024-2025学年初三第二学期第三次教学质量检测试题生物试题含解析.doc
- 四川省绵阳外国语校2024-2025学年初三下学期入学生物试题含解析.doc
- 内蒙古鄂尔多斯市康巴什新区2025年初三下学期3月模块诊断生物试题试卷含解析.doc
- 2025年江西省宁都县初三下学期第四次考试生物试题含解析.doc
- 2025年吉林省长春市南关区东北师大附中新城校区重点达标名校初三第一次模拟质量联测生物试题含解析.doc
- 山东省青岛李沧区四校联考2024-2025学年初三下学期统练(七)生物试题含解析.doc
- 2025年内蒙古自治区包头市初三3月综合测试(一)生物试题试卷含解析.doc
- 江苏省东台市第四教育联盟市级名校2025届初三下学期中考仿真考试生物试题含解析.doc
最近下载
- 办公用品订购合同范本.docx VIP
- WORD版本刻度尺-A4纸打印可用.doc
- 90nm逻辑产品Peeling缺陷的解决方案.pdf
- 神经系统的分级调节.pptx VIP
- 中建施工总平面布置图设计(69页).pdf
- 2024年公共卫生与预防医学继续教育平台“大学习”活动线上培训栏目考试题库(1392题).docx
- 北师大版(2023)必修第一册 Unit 2 Sports and Fitness单元教学设计.pdf VIP
- 2016-2023年长沙民政职业技术学院高职单招(英语/数学/语文)笔试历年参考题库含答案解析.docx
- 农业经济学-农业资金.ppt VIP
- 齐鲁医学神经系统疾病的辅助检查.ppt VIP
文档评论(0)