第2章算法分析 算法分析的概念 @算法效率的度量 @检验一个算法分析 @Bg-Oh分析法的限制
第2章 算法分析 算法分析的概念 算法效率的度量 检验一个算法分析 Big-Oh分析法的限制
评价算法好坏的标准 ◆执行算法所耗费的时间,即效率问题。 ◆执行算法所耗费的存储空间,主要考虑辅助的存储空 间 ◆算法应易于理解具有可读性,易于编码,易于调试等。 ◆健壮性,即当输入一些非法数据时,算法也应做出适 当的反映或进行处理
评价算法好坏的标准 执行算法所耗费的时间，即效率问题。 执行算法所耗费的存储空间，主要考虑辅助的存储空 间。 算法应易于理解,具有可读性，易于编码，易于调试等。 健壮性，即当输入一些非法数据时，算法也应做出适 当的反映或进行处理
算法分析的概念 ◆算法所花费的运行时间取决于它所处理的数 据输入量。 ◆算法的运行时间是数据输入量的一个函数。 ◆而确切的函数值依赖于许多因素。 ◆对于一个给定计算机上的给定程序,可以在 图中描绘出运行时间的函数
算法分析的概念 算法所花费的运行时间取决于它所处理的数 据输入量。 算法的运行时间是数据输入量的一个函数。 而确切的函数值依赖于许多因素。 对于一个给定计算机上的给定程序，可以在 图中描绘出运行时间的函数
算法分析中的时间函数图解 ◆图中给出了四个程序的运行时间图,这些曲线代表了在算法 分析中遇到的四个函数:线性函数、O( NlogN)、二次方 函数、立方函数,输入规模N从1至100,运行时间为0至10 亳秒。 线性 线性 0.8 O NIogND O(NIOgN 平方 0.6 平方 互万 4 0.4 0.2 1020304o50607o8o90100 12345678910 输入规模(M) 输入规模(N)(单位为千) 图2-1小规模输入时的运行时间 图2-2中规模输入时的运行时间
图中给出了四个程序的运行时间图，这些曲线代表了在算法 分析中遇到的四个函数：线性函数、O（NlogN）、二次方 函数、立方函数，输入规模N从1至100，运行时间为0至10 毫秒。 算法分析中的时间函数图解 图2-1 小规模输入时的运行时间 图2-2 中规模输入时的运行时间
◆这些曲线最显著的特征就是当数据输入量较大时,平方 算法和立方算法无法与其他算法竞争。 ◆下表所示的是以增长率的增长次序来排列这些算法运行 时间的函数。 函数 名称 函数 名称 常数 NIOgN NlOgN 0g 对数 N 平方 0g 平方对数 N 立方 N 线性 n 指数
这些曲线最显著的特征就是当数据输入量较大时，平方 算法和立方算法无法与其他算法竞争。 下表所示的是以增长率的增长次序来排列这些算法运行 时间的函数。 函数 名称 函数 名称 c 常数 NlogN NlogN logN 对数 N² 平方 log ²N 平方对数 N³ 立方 N 线性 2ⁿ 指数