算法效率的度量 算法效率——用依据该算法编制的程序在计算机上执行 所消耗的时间来度量。 通常有两种衡量算法效率的方法: 1、事后统计——利用计算机内记时功能,不同算法的程序 可以用一组或多组相同的统计数据区分。 缺点:①必须先运行依据算法编制的程序。 ②所得时间统计量依赖于硬件、软件等环境因素,掩盖 算法本身的优劣
算法效率的度量 算法效率——用依据该算法编制的程序在计算机上执行 所消耗的时间来度量。 通常有两种衡量算法效率的方法: 1、事后统计——利用计算机内记时功能，不同算法的程序 可以用一组或多组相同的统计数据区分。 缺点：必须先运行依据算法编制的程序。 所得时间统计量依赖于硬件、软件等环境因素，掩盖 算法本身的优劣
算法效率的度量 2、事前分析估计——个高级语言程序在计算机上运行所 消耗的时间取决于: ①依据的算法选用何种策略 ②问题的规模 ③程序语言 ④编译程序产生机器代码质量 ⑤机器执行指令速度
算法效率的度量 2、事前分析估计——一个高级语言程序在计算机上运行所 消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度
算法效率的度量 同一个算法用不同的语言、不同的编译程序、在 不同的计算机上运行,效率均不同,—所以使用 绝对时间单位衡量算法效率不合适 一个特定算法的“运行工作量”的大小,只依赖 于问题的规模(通常用整数量η表示),或者说, 它是问题规模的函数
算法效率的度量 同一个算法用不同的语言、不同的编译程序、在 不同的计算机上运行，效率均不同，——所以使用 绝对时间单位衡量算法效率不合适。 一个特定算法的“运行工作量”的大小，只依赖 于问题的规模（通常用整数量n表示），或者说， 它是问题规模的函数