第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ⁿ 指数
算法效率的度量 算法效率——用依据该算法编制的程序在计算机上执行 所消耗的时间来度量。 通常有两种衡量算法效率的方法: 1、事后统计——利用计算机内记时功能,不同算法的程序 可以用一组或多组相同的统计数据区分。 缺点:①必须先运行依据算法编制的程序。 ②所得时间统计量依赖于硬件、软件等环境因素,掩盖 算法本身的优劣
算法效率的度量 算法效率——用依据该算法编制的程序在计算机上执行 所消耗的时间来度量。 通常有两种衡量算法效率的方法: 1、事后统计——利用计算机内记时功能，不同算法的程序 可以用一组或多组相同的统计数据区分。 缺点：必须先运行依据算法编制的程序。 所得时间统计量依赖于硬件、软件等环境因素，掩盖 算法本身的优劣
算法效率的度量 2、事前分析估计——个高级语言程序在计算机上运行所 消耗的时间取决于: ①依据的算法选用何种策略 ②问题的规模 ③程序语言 ④编译程序产生机器代码质量 ⑤机器执行指令速度
算法效率的度量 2、事前分析估计——一个高级语言程序在计算机上运行所 消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度
算法效率的度量 同一个算法用不同的语言、不同的编译程序、在 不同的计算机上运行,效率均不同,—所以使用 绝对时间单位衡量算法效率不合适 一个特定算法的“运行工作量”的大小,只依赖 于问题的规模(通常用整数量η表示),或者说, 它是问题规模的函数
算法效率的度量 同一个算法用不同的语言、不同的编译程序、在 不同的计算机上运行，效率均不同，——所以使用 绝对时间单位衡量算法效率不合适。 一个特定算法的“运行工作量”的大小，只依赖 于问题的规模（通常用整数量n表示），或者说， 它是问题规模的函数
计算累加和程序 程序步数计算工作表格 次执行所执行程序 程序语句 需程序步数频度步数 0 float s =0.0: for( int i=0; i<n; i++)1 n+1n+1 s+= a[; return s, 0 10 总程序步数2n+3
计算累加和程序 程序步数计算工作表格 程 序 语 句 一次执行所 需程序步数 执行 频度 程序 步数 { 0 1 0 float s = 0.0; 1 1 1 for ( int i=0; i<n; i++ ) 1 n+1 n+1 s += a[i]; 1 n n return s; 1 1 1 } 0 1 0 总程序步数 2n+3
算法效率的度量 一般情况下,算法中基本操作重复执行的次数是问题 规模n的某个函数,算法的时间量度记作 T(n=o(f(n) 称作算法的渐近时间复杂度,简称时间复杂度。 表示随着问题规模η的增长,算法执行时间的增长率 和f(n)的增长率相同
算法效率的度量 一般情况下，算法中基本操作重复执行的次数是问题 规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)) 称作算法的渐近时间复杂度，简称时间复杂度。 表示随着问题规模 n 的增长，算法执行时间的增长率 和 f(n) 的增长率相同