|
第四课 本课主题 算法效率的度量和存储空间需求 教学目的 掌握算法的渐近时间复杂度和空间复杂度的意义与作用 教学重点 渐近时间复杂度的意义与作用及计算方法 教学难点 渐近时间复杂度的意义 授课内容 一算法效率的度量 算法执行的时间是算法优劣和问题规模的函数评价一个算法的优劣可以在相同的规模下考察算法执行时间的长短来进行判断而一个程序的执行时间通常有两种方法 事后统计的方法 缺点不利于较大范围内的算法比较（异地异时异境） 事前分析估算的方法 程序在计算机上运行所需时间的影响因素 算法本身选用的策略 问题的规模 规模越大消耗时间越多 书写程序的语言 语言越高级消耗时间越多 编译产生的机器代码质量 机器执行指令的速度 综上所述为便于比较算法本身的优劣应排除其它影响算法效率的因素 从算法中选取一种对于所研究的问题来说是基本操作的原操作以该基本操作重复执行的次数作为算法的时间量度（原操作在所有该问题的算法中都相同） T(n)= |
