评估 粗略(快速)的评估: 称为“餐巾纸背面计算”或“信封背面 计算” 确定影响问题的主要参数 推导出一个与问题的参数的有关的公式 选择参数值,由该公式得出一个评估解
评估 • 粗略（快速）的评估： • 称为“餐巾纸背面计算”或“信封背面 计算” – 确定影响问题的主要参数 – 推导出一个与问题的参数的有关的公式 – 选择参数值，由该公式得出一个评估解
评估示例 要存放100万页书籍需要多少图书馆书 估算 1英寸高的书由多少页 书架的宽度 书架的层数
评估示例 要存放100万页书籍需要多少图书馆书 架? 估算: – 1英寸高的书由多少页 – 书架的宽度 – 书架的层数
第三章算法分析
第三章 算法分析
如何测算算法的效率? 程序实现来测量 渐近算法分析 影响程序运行时间有很多因素 由于影响运行时间的主要因素是输入的规模, 因此常将执行算法所需时间T表示成T(m) 算法的增长率是指当输入的值(规模)增长时,算 法代价的增长速度
如何测算算法的效率? 1. 程序实现来测量 2. 渐近算法分析 影响程序运行时间有很多因素: 由于影响运行时间的主要因素是输入的规模， 因此常将执行算法所需时间T表示成T(n) 算法的增长率是指当输入的值（规模）增长时，算 法代价的增长速度
增长率示例 例1. Find largest value int largest(int array[l, int n) int currlarge =0;// Largest value seen for(int i=l; i<n; 1++)// For each val A(array[currlarge] array[]) currlarge i Remember pos return curr⊥arge; / Return largest
增长率示例 例 1. // Find largest value int largest(int array[], int n) { int currlarge = 0; // Largest value seen for (int i=1; i<n; i++) // For each val 若 (array[currlarge] < array[i]) currlarge = i; // Remember pos return currlarge; // Return largest }