●●●●● ●●●● ●●0 ●●● ●●●● 3)工作数据集的选择 ●编制能够反映算法在最好、平均、最坏情况下工作的数据 配置。然后使用这些数据配置运行算法,以了解算法的性 能 编制测试数据是程序测试与算法分析中的关键技术之一。 作为算法分析的数据集:反映算法的典型特征 作为程序正确性及性能测试的数据集:测试程序的对错,反映对性 能指标产生影响的方面,如边界值 2021/2/20
2021/2/20 3）工作数据集的选择 ⚫ 编制能够反映算法在最好、平均、最坏情况下工作的数据 配置。然后使用这些数据配置运行算法，以了解算法的性 能。 编制测试数据是程序测试与算法分析中的关键技术之一。 ·作为算法分析的数据集：反映算法的典型特征 ·作为程序正确性及性能测试的数据集：测试程序的对错，反映对性 能指标产生影响的方面,如边界值
●●●●● ●●●● ●●0 3.如何进行算法分析? ●●●● 对算法进行全面分析,可分两个阶段进行: 事前分析:求算法的一个时间空间限界函数,即通过对算 法的“理论”分析,得出关于算法时间和空间 特性 的特征函数(O、Ω)—与计算机物理软硬 件没有直接关系 事后测试:将算法编制成程序后实际放到计算机上运行, 收集其执行时间和空间占用等统计资料,进行 分析判断——直接与物理实现有关。 2021/2/20
2021/2/20 3. 如何进行算法分析？ 对算法进行全面分析，可分两个阶段进行： ⚫事前分析：求算法的一个时间/空间限界函数，即通过对算 法的“理论”分析，得出关于算法时间和空间 特性 的特征函数（Ο、Ω）——与计算机物理软硬 件没有直接关系。 ⚫事后测试：将算法编制成程序后实际放到计算机上运行， 收集其执行时间和空间占用等统计资料，进行 分析判断——直接与物理实现有关
●●●●● ●●●● ●●0 ●●● 1)事前分析 ●●●● ●目的:试图得出关于算法特性的一种形式描 述,以“理论上”衡量算法的“好坏” ●如何给出反映算法特性的描述? 统计算法中各种运算的执行情况,包括: 引用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。 算法的执行时间=∑千 2021/2/20
2021/2/20 1）事前分析 ⚫ 目的：试图得出关于算法特性的一种形式描 述，以“理论上”衡量算法的“好坏”。 ⚫ 如何给出反映算法特性的描述？ 统计算法中各种运算的执行情况，包括： ➢ 引用了哪些运算 ➢ 每种运算被执行的次数 ➢ 该种运算执行一次所花费的时间等。 算法的执行时间=∑fi *t i
●●●●● ●●●● ●频率计数 ●●0 ●●● ●●●● 频率计数:算法中语句或运算的执行次数 例: X←X+ y for i←-1 to n do for i←1 to n do X←X+y forj←1 to n do repeat X←X十 repeat repeat 分析 (a):X←Xy执行了1次 b):X←X+y执行了n次 (c):XXy执行了n2次 2021/2/20
2021/2/20 ⚫ 频率计数 频率计数：算法中语句或运算的执行次数。 例： x←x+y for i ←1 to n do for i ←1 to n do x ← x + y for j ←1 to n do repeat x ← x +y repeat repeat (a) (b) (c) 分析： (a)： x←x+y执行了1次 (b)： x←x+y执行了n次 (c)： x←x+y执行了n 2次
●●●●● ●●●● ●●0 ●●● ●●●● 条语句在整个程序运行时实际执行时间 频率计数*每执行一次该语句所需的时间 在事前分析中,只限于确定与所使用的机器及其他环境因 素无关的频率计数,依此建立一种理论上分析模型。 2021/2/20
2021/2/20 一条语句在整个程序运行时实际执行时间= 频率计数 * 每执行一次该语句所需的时间 ⚫ 在事前分析中，只限于确定与所使用的机器及其他环境因 素无关的频率计数，依此建立一种理论上分析模型