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

正确性。 可使用性。 可读性。 健壮性。 高时间性能与低存储量需求。 1/56

分析算法占用的资源 CPU时间 内存空间 时间性能分析 空间性能分析 2/56

 事后分析统计方法：编写算法对应程序，统计其执行时间。 编写程序的语言不同 执行程序的环境不同 其他因素  事前估算分析方法：撇开上述因素，认为算法的执行时间是问题规 模n的函数。 ✓ 所以不能用绝对执行 时间进行比较。 3/56

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有 数据类型的操作，如+、-、 * 、/、++和-等）构成的。算法执行时间取决 于两者的综合效果。 一个算法的基本构成： 控制语句1 原操作 控制语句n 原操作 控制语句2 . 原操作 1. 分析算法的时间复杂度 4/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

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

算法中执行时间T(n)是问题规模n的某个函数f(n)，记作： T(n) = O(f(n)) cf(n) T(n) n0 n 执行时间 8/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)的计算，又能比较客观地反映出当n很大时算法的时间性能。 本质上讲，是一种T(n) 提示 最高数量级的比较 10/56