第1章绪论第5讲-算法分析基础.pptx

1.3 算法分析基础 ; 一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作，如+、-、*、/、++和--等）构成的。算法执行时间取决于两者的综合效果。;例如：;算法分析方式：;求出算法所有原操作的执行次数（也称为频度） ，它是问题规模n的函数，用T(n)表示。 算法执行时间大致 = 原操作所需的时间×T(n)。所以T(n)与算法的执行时间成正比 。为此用T(n)表示算法的执行时间。 比较不同算法的T(n)大小得出算法执行时间的好坏。;#define MAX 20 //定义最大的方阶 void matrixadd(int n，int A[MAX][MAX]，int B[MAX][MAX]， int C[MAX][MAX]) { int i，j; for (i=0;in;i++) //① for (j=0;jn;j++) //② C[i][j]=A[i][j]+B[i][j]; //③ };#define MAX 20 //定义最大的方阶 void matrixadd(int n，int A[MAX][MAX]， int B[MAX][MAX]， int C[MAX][MAX]) { int i，j; for (i=0;in;i++) //① for (j=0;jn;j++) //② C[i][j]=A[i][j]+B[i][j]; //③ };算法中执行时间T(n)是问题规模n的某个函数f(n)，记作： T(n) = O(f(n)); “O”的形式定义为： T(n) = O(f(n))表示存在一个正的常数M，使得当n≥n0时都满足： |T(n)|≤M|f(n)| ; 也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。 ;一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。 其余常用的算法时间复杂度还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。; 各种不同算法时间复杂度的比较关系如下： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!);算法中的基本操作一般是最深层循环内的原操作。 算法执行时间大致 = 基本操作所需的时间 ×其运算次数。 ;#define MAX 20 //定义最大的方阶 void matrixadd(int n，int A[MAX][MAX]，int B[MAX][MAX]， int C[MAX][MAX]) { int i，j; for (i=0;in;i++) for (j=0;jn;j++) C[i][j]=A[i][j]+B[i][j]; }; 　解：该算法中的基本操作是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j]，分析它的频度，即： T(n) = = O(n2);思考题 下列程序段的时间复杂度是 。;void func(int n) { int i=0，s=0; while (sn) { i++; s=s+i; } }; 解：对于while循环语句，设执行的次数为m，变量i从0开始递增1，直到m为止，有：; 空间复杂度：用于量度一个算法在运行过程中临时占用的存储空间大小。 一般也作为问题规模n的函数，采用数量级形式描述，记作： S(n) = O(g(n)) ; 【例（补充）】 分析如下算法的空间复杂度。 ;为什么空间复杂度分析只考虑临时占用的存储空间？;思考题 为什么算法的时、空分析都采用复杂度的形式表示？; ━━本讲完━━