河池学院：《数据结构》课程电子教案（PPT教学课件）第1章 绪论 1.3 算法分析 1.4 数据结构的目标

算法分析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

1）计算算法频度T（n）假设算法的问题规模为n，例如对10个整数排序，问题规模为n就是10。算法频度是问题规模n的函数，用T(n)表示。算法执行时间大致等于原操作所需的时间XT(n)，也就是说T(n)与算法的执行时间成正比。为此用T（n)表示算法的执行时间。比较不同算法的T（n）大小得出算法执行时间的好坏。6/56

假设算法的问题规模为n，例如对10个整数排序，问题规模为n就是10。 算法频度是问题规模n的函数，用T(n)表示。 算法执行时间大致等于原操作所需的时间×T(n)，也就是说T(n)与算 法的执行时间成正比。为此用T(n)表示算法的执行时间。比较不同算 法的T(n)大小得出算法执行时间的好坏。 6/56

【例1.9】求两个n阶方阵的相加C=A+B的算法如下，求T(n)。执行次数void matrixadd(int][] A,int[][] B,int[j[] C,int n)n+11/语句①for (int i=o;i<n;i++)1语句②n(n+1)for(intj=o;j<n;j++)1语句?n2C[i][]=A[i][j]+B[i][j];7T(n)=n+1+n(n+1)+n2=2n2+2n+1。7/56

void matrixadd(int[][] A,int[][] B,int[][] C,int n) { for (int i=0;i<n;i++) //语句① for (int j=0;j<n;j++) //语句② C[i][j]=A[i][j]+B[i][j]; //语句③ } 【例1.9】求两个n阶方阵的相加C=A+B的算法如下，求T(n)。 执行次数 n+1 n(n+1) n 2 T(n)=n+1+n(n+1)+n 2 =2n 2+2n+1。 7/56

2）什么是算法时间复杂度算法中执行时间T(n)是问题规模n的某个函数f(n），记作：T(n) = o(f(n))执行时间cf(n)(T(n)ne8/56

算法中执行时间T(n)是问题规模n的某个函数f(n)，记作： T(n) = O(f(n)) cf(n) T(n) n0 n 执行时间 8/56

“0”的形式定义为：T(n）=o(f(n））表示存在一个正的常数，使得当n≥ng时都满足：IT(n) /≤clf(n) f(n)是T(n)的上界这种上界可能很多，通常取最接近的上界，即紧凑上界大致情况：T(n)1imf(n)n-009/56

“O”的形式定义为： T(n) = O(f(n))表示存在一个正的常数c，使得当n≥n0时都满足： |T(n)|≤c|f(n)| f(n)是T(n)的上界 这种上界可能很多，通常取最接 近的上界，即紧凑上界 大致情况： lim n→∞ T(n) f(n) = c 9/56

本质上讲，是一种T(n）提示最高数量级的比较也就是只求出T（n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。10/56

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化 T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。 本质上讲，是一种T(n) 提示 最高数量级的比较 10/56