算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度_第1页
算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度_第2页
算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度_第3页
算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度_第4页
算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度_第5页
已阅读5页，还剩5页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

信息工程大学算法设计与分析算法分析—时间复杂度国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版如何度量如何表示计算步骤一二三算法……程序电脑运行环境编程语言编译器……思考：

执行算法的实际时间？

实现算法指令（语句）条数？

实现算法程序的循环次数？通常用：算法所使用的一种或几种“基本操作”的执行次数来度量。基本操作－解决某一问题的算法中，处于基本关键地位，执行次数足以反映算法效率的操作。如：搜索数组元素的“比较操作”；多项式计算中的“乘法操作”和“加法操作”。基本操作：比较运算

给变量赋值

跟踪对象引用

函数或方法调用数组元素访问

从函数或方法中返回算术运算（加、减、乘、除等）

测试单选题：算法的时间复杂度分析，主要针对（）； A：循环 B：所有指令 C：基本操作算法的“工作量”与问题的输入规模、具体的输入有关。

问题的输入有多少种？每种(类)输入出现的概率及其所需要的处理时间（基本操作的执行次数）？输入n是多少

？算法的工作量通常有“平均时间复杂度（或平均性态）”和“最坏时间复杂度(或最坏性态)”两种表示。

Dn：输入规模为n的输入集合I：一个尺寸为n的输入P(I)：输入为I出现的概率t(I)：对于I,算法做的基本操作次数平均时间复杂度：最坏时间复杂度：注:实践表明，可操作性最好、且最有实际价值的，是最坏时间复杂度。

平均时间复杂度分析步骤为： 1.确定基本操作； 2.分析不同的输入种类并确定出现概率； 3.计算每种输入执行的基本操作次数； 4.按公式计算； 5.化简函数。最坏时间复杂度分析步骤为： 1.确定基本操作； 2.分析输入的最坏情况； 3.计算最坏情况输入下执行基本操作的次数； 4.化简函数

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论