第四课：算法效率的度量和存储空间需求

第四课

本课主题： 算法效率的度量和存储空间需求

教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用

教学重点： 渐近时间复杂度的意义与作用及计算方法

教学难点： 渐近时间复杂度的意义

授课内容：

一、算法效率的度量

算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：

1、事后统计的方法。

缺点：不利于较大范围内的算法比较。（异地，异时，异境）

2、事前分析估算的方法。

综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。

从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）

T(n)=O(f(n))

上示表示