算法分析1.3算法的设计目标1.3.1正确性。可使用性。可读性。健壮性。高时间性能与低存储量需求。1/56
正确性。 可使用性。 可读性。 健壮性。 高时间性能与低存储量需求。 1/56
CPU时间时间性能分析分析算法占用的资源内存空间空间性能分析算法分析目的：分析算法的时空效率以便改进算法性能。2/56
分析算法占用的资源 CPU时间 内存空间 时间性能分析 空间性能分析 2/56
算法时间性能分析1.3.2算法分析方式：编写算法对应程序，统计其执行时间。事后分析统计方法：编写程序的语言不同所以不能用绝对执行执行程序的环境不同时间进行比较。其他因素事前估算分析方法：撒开上述因素，认为算法的执行时间是问题规模n的函数。3/56
事后分析统计方法：编写算法对应程序，统计其执行时间。 编写程序的语言不同 执行程序的环境不同 其他因素 事前估算分析方法：撇开上述因素，认为算法的执行时间是问题规 模n的函数。 ✓ 所以不能用绝对执行 时间进行比较。 3/56
1.分析算法的时间复杂度一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作，如+、-、*、／、++和--等）构成的。算法执行时间取决于两者的综合效果。一个算法的基本构成：控制语句1控制语句2控制语句n原操作原操作原操作4/56
一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有 数据类型的操作，如+、-、 * 、/、++和-等）构成的。算法执行时间取决 于两者的综合效果。 一个算法的基本构成： 控制语句1 原操作 控制语句n 原操作 控制语句2 . 原操作 1. 分析算法的时间复杂度 4/56
double solve(int m,int n,double [j[l a)1int s = o;顺序结构if(m != n)分支结构throw new Exception("m!=n"):循环结构for(int i = O; i<m; i++)+= a[i]i];顺序结构return $原操作算法的执行时间取决于控制结构和原操作的综合效果。在一个算法中，执行原操作的次数越少，其执行时间也就相对地越少：执行原操作次数越多，其执行时间也就相对地越多。算法中所有原操作的执行次数称为算法频度，这样一个算法的执行时间可以由算法频度来计量。5/56
int s = 0; if (m != n) throw new Exception("m!=n"); for (int i = 0; i<m; i++) s += a[i][i]; return s; double solve(int m,int n,double [][] a) { 顺序结构 循环结构 分支结构 顺序结构 } 原操作 算法的执行时间取决于控制结构和原操作的综合效果。 在一个算法中，执行原操作的次数越少，其执行时间也就相对地越少；执行 原操作次数越多，其执行时间也就相对地越多。 算法中所有原操作的执行次数称为算法频度，这样一个算法的执行时间可以 由算法频度来计量。 5/56