算法设计与分析 课件 1.2.2-算法分析准则 - 时间复杂度.pptx

信息工程大学算法设计与分析算法分析—时间复杂度国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

如何度量如何表示计算步骤一二三

算法……程序电脑运行环境编程语言编译器……

思考： 执行算法的实际时间？ 实现算法指令（语句）条数？ 实现算法程序的循环次数？通常用：算法所使用的一种或几种“基本操作”的执行次数来度量。基本操作－解决某一问题的算法中，处于基本关键地位，执行次数足以反映算法效率的操作。如：有哪些信誉好的足球投注网站数组元素的“比较操作”；多项式计算中的“乘法操作”和“加法操作”。

基本操作：比较运算 给变量赋值 跟踪对象引用 函数或方法调用数组元素访问 从函数或方法中返回算术运算（加、减、乘、除等）

测试单选题：算法的时间复杂度分析，主要针对（）； A：循环 B：所有指令 C：基本操作

算法的“工作量”与问题的输入规模、具体的输入有关。问题的输入有多少种？每种(类)输入出现的概率及其所需要的处理时间（基本操作的执行次数）？输入n是多少？

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

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

测试单选题：最常使用的时间复杂度是（） A：平均时间复杂度 B：最坏时间复杂度