(@例说明执行频度 X=X+ y 2. for i=1 to n do x=x+ y repeat 3. for j=1 to n do f。orj=1 to n do X=X+ y repeat repeat
例 说明执行频度 1. x=x+ y; 2. for i=1 to n do x=x+ y repeat 3. for i=1 to n do for j=1 to n do x=x+ y repeat repeat 1 n n 2
2)计算的约定(续) 从计算时间上,运算的分类 时间囿界于常数的运算: 基本算术运算,如整数的加、减、乘、除 ·字符运算 赋值运算 ·过程调用等 特点:尽管每种运算的执行时间不同,但 般只花一个固定量的时间(单位时间)就可完 成
2）计算的约定（续） •从计算时间上，运算的分类： ➢时间囿界于常数的运算： ·基本算术运算，如整数的加、减、乘、除 ·字符运算 ·赋值运算 ·过程调用等 特点：尽管每种运算的执行时间不同，但一 般只花一个固定量的时间（单位时间）就可完 成
2)计算的约定(续) 其他运算: ·字符串操作:与字符串中字符的数量成正比 记录操作:与记录的属性数、属性类型等有关 特点:运算时间无定量 如何分析非时间囿界于常数的运算:分解成 若干时间囿界于常数的运算。 如:T str ing Length (String)*t char
2）计算的约定（续） ➢ 其他运算： ·字符串操作：与字符串中字符的数量成正比 ·记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量 如何分析非时间囿界于常数的运算：分解成 若干时间囿界于常数的运算。 如：Tstring = Length（String）* tchar
( 3)工作数据集的选择 编制能够反映算法在最好、平均、最坏情况下工作的 数据配置。然后使用这些数据配置运行算法,以了 解算法的性能。 ·测试数据集的生成在目前算法证明与程序正确性证 明没有取得理论上的突破性进展的情况下,是程序 测试与算法分析中的关键技术之一。 ·作为算法分析的数据集:典型特征 作为程序性能测试的数据集:对执行指标产生影响的性质
3）工作数据集的选择 编制能够反映算法在最好、平均、最坏情况下工作的 数据配置。然后使用这些数据配置运行算法，以了 解算法的性能。 • 测试数据集的生成在目前算法证明与程序正确性证 明没有取得理论上的突破性进展的情况下，是程序 测试与算法分析中的关键技术之一。 ·作为算法分析的数据集：典型特征 ·作为程序性能测试的数据集：对执行指标产生影响的性质
( 3.如何进行算法分析 对算法进行全面分析,可分两个阶段进行 事前分析:就算法本身,通过对其执行性能的理论分析, 得出关于算法特性—时间和空间的一个特征 函数(O、Q)—与计算机物理软硬件没有 直接关系。 °事后测试:将算法编制成程序后实际放到计算机上运行, 收集其执行时间和空间占用等统计资料,进行 分析判断直接与物理实现有关
3. 如何进行算法分析？ 对算法进行全面分析，可分两个阶段进行： 事前分析：就算法本身，通过对其执行性能的理论分析， 得出关于算法特性——时间和空间的一个特征 函数（Ο、Ω）——与计算机物理软硬件没有 直接关系。 •事后测试：将算法编制成程序后实际放到计算机上运行， 收集其执行时间和空间占用等统计资料，进行 分析判断——直接与物理实现有关