第1周绪论第5讲-算法分析基础.pdf

《第1周绪论第5讲-算法分析基础.pdf》由会员分享，可在线阅读，更多相关《第1周绪论第5讲-算法分析基础.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分析算法分析算法占用的资源占用的资源 CPU时间时间 内存空间内存空间 时间性能分析时间性能分析 空间性能分析空间性能分析 一个算法是由控制结构一个算法是由控制结构（顺序顺序、分支和循环三种分支和循环三种）和和原原操操 作作（指固有数据类型的操作指固有数据类型的操作，如如+、- -、*、/、+和和-等等）构成构成 的的。算法执行时间算法执行时间取决于两者的综合效果取决于两者的综合效果。 一个算法的基本构成：一个算法的基本构成： 控制语句控制语句1 原操作原操作 控制语句控制语句n 原操作原操作 控制语句控制语句2 原操作原操作 例如：例如： void fun(int a,int n) int

2、i; for (i=0;in;i+) ai=2*i; for (i=0;in;i+) printf(%d, ai); printf(n); 原操作原操作 算法分析方式：算法分析方式： 事后分析统计方法事后分析统计方法：编写算法对应程序，统计其执行时间。：编写算法对应程序，统计其执行时间。 编写程序的编写程序的语言不同语言不同 执行程序的执行程序的环境不同环境不同 其他其他因素因素 事前估算分析方法事前估算分析方法：撇开上述因素，认为算法的执行时间是问：撇开上述因素，认为算法的执行时间是问 题规模题规模n的函数。的函数。 所以不能用绝对执行所以不能用绝对执行 时间进行比较。时间进行比较。 求求出

3、算法所有原操作的执行次数（也称为出算法所有原操作的执行次数（也称为频度频度） ，它是，它是问题规问题规 模模n的函数，用的函数，用T(n)表示。表示。 算法算法执行时间执行时间大致大致 = 原原操作所需操作所需的的时间时间T(n)。所以。所以T(n)与与算算 法的执行时间法的执行时间成正比成正比 。为此用。为此用T(n)表示算法的执行时间。表示算法的执行时间。 比较比较不同算法的不同算法的T(n)大小得出算法执行时间的好坏。大小得出算法执行时间的好坏。 用于表示求解问题大小的正整数，如n个记录排序 分析算法的执行时间分析算法的执行时间 #define MAX 20/定义最大的方阶定义最大的方阶

4、 void matrixadd(int n,intAMAXMAX,int BMAXMAX, int CMAXMAX) int i,j; for (i=0;in;i+)/ for (j=0;jn;j+)/ Cij=Aij+Bij;/ 【例例1- -4】求两个求两个n阶方阵的相加阶方阵的相加C=A+B的算法如下的算法如下，分析其分析其 时间复杂度时间复杂度。 #define MAX 20/定义最大的方阶定义最大的方阶 void matrixadd(int n,intAMAXMAX, int BMAXMAX, int CMAXMAX) int i,j; for (i=0;in;i+)/ for (j

5、=0;jn;j+)/ Cij=Aij+Bij; / 解：解：除变量定义语句外，除变量定义语句外， 该算法包括该算法包括3个可执行语句个可执行语句 、和。、和。 频度为频度为n+1，循环体执行，循环体执行n次次 频度为频度为n(n+1) 频度为频度为n2 所有语句频度之和为：所有语句频度之和为： T(n) = n+1+n(n+1)+n2 = 2n2+2n+1 算法中执行时间算法中执行时间T(n)是问题规模是问题规模n的某个函数的某个函数f(n)，记作：记作： T(n) = O(f(n) 算法算法的执行时间用时间复杂度来表示的执行时间用时间复杂度来表示 记号记号“O”读读作作“大大O”，它表示随问

6、题规模它表示随问题规模n的增大算法执行的增大算法执行 时间的增长率和时间的增长率和f(n)的的增长率增长率相同相同。 趋势分析趋势分析 T(n) n f(n) “O”的的形式定义形式定义为为：T(n) = O(f(n)表示存在一个正的常数表示存在一个正的常数M， 使得当使得当nn0时都满足：时都满足： |T(n)|M|f(n)| f(n)是是T(n)的的上界上界 这种上界可能很多，通常取最这种上界可能很多，通常取最 接近的上界，即接近的上界，即紧凑上界紧凑上界 大致情况：大致情况： lim n T(n) f(n) = M 也就是只求出也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样的最

7、高阶，忽略其低阶项和常系数，这样 既可简化既可简化T(n)的计算，又能比较客观地反映出当的计算，又能比较客观地反映出当n很大时算法的很大时算法的 时间性时间性能能。 本质上讲，是本质上讲，是一一种种T(n) 最高最高数量级的比较数量级的比较 例如例如 ：T(n) = 2n2+2n+1 = O(n2) 一个没有循环的算法的执行时间与问题规模一个没有循环的算法的执行时间与问题规模n无关，记作无关，记作O(1)，也称作，也称作常常 数阶数阶。 一个只有一重循环的算法的执行时间与问题规模一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，的增长呈线性增大关系， 记作记作O(n)，也称，也

8、称线性阶线性阶。 其余常用的算法时间复杂度还有其余常用的算法时间复杂度还有平方阶平方阶O(n2)、立方阶立方阶O(n3)、对数阶对数阶 O(log2n)、指数阶指数阶O(2n)等。等。 一般地：一般地： 各种不同算法时间复杂度的比较关系如下：各种不同算法时间复杂度的比较关系如下： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!) 算法时间性能比较：算法时间性能比较：假如假如求同一问题有两个算法：求同一问题有两个算法：A和和B，如，如 果算法果算法A的平均时间的平均时间复杂度为复杂度为O(n)，而算法，而算法B的平均时间的平均时间复杂度为复杂度为 O(n

9、2)。 一般情况下一般情况下，认为，认为算法算法A的时间性能好比算法的时间性能好比算法B。 指数指数阶：阶： NP问题问题 多项式多项式阶：阶： P问题问题 NP = P？是目前计算机？是目前计算机 科学的难题之一科学的难题之一 算法中的算法中的基本操作基本操作一般是最深层循环内的一般是最深层循环内的原操作原操作。 算法算法执行时间执行时间大致大致 = 基本基本操作所需操作所需的的时间时间 其其运算运算次数次数。 简化简化的算法时间复杂度分析的算法时间复杂度分析 在算法分析时，计算在算法分析时，计算T(n)时仅仅考虑基本操作的运算次数。时仅仅考虑基本操作的运算次数。 转化转化 #define

10、MAX 20/定义最大的方阶定义最大的方阶 void matrixadd(int n,intAMAXMAX,int BMAXMAX, int CMAXMAX) int i,j; for (i=0;in;i+) for (j=0;jn;j+) Cij=Aij+Bij; 【例例1- -4】求两个求两个n阶方阵的相加阶方阵的相加C=A+B的算法如下的算法如下，分析其分析其 时间复杂度时间复杂度。 基本操作 解 ：解 ： 该 算 法 中 的 基 本 操 作 是 两 重 循 环 中 最 深 层 的 语 句该 算 法 中 的 基 本 操 作 是 两 重 循 环 中 最 深 层 的 语 句 Cij=Aij+

11、Bij，分析它的频度分析它的频度，即：即： T(n) = = O(n2) 1 0 2 1 0 1 0 1 0 *11 n i n i n i n j n nnnn 这种简化的时间复杂度分析方法得到的这种简化的时间复杂度分析方法得到的结果相同结果相同，但分析，但分析 过程更简单。过程更简单。 思考题思考题 下列下列程序段的时间复杂度是程序段的时间复杂度是。 A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2) count=0; for(k=1;k=n;k*=2) for(j=1;j=n;j+) count+; 说明：本题为说明：本题为2014年年全国考研题全国考研题 基本操作 v

12、oid func(int n) int i=0,s=0; while (sn) i+; s=s+i; 基本操作基本操作 【例例1- -5】分析分析以下算法的时间复杂度以下算法的时间复杂度。 解：解：对于对于while循环语句，设执行的次数为循环语句，设执行的次数为m，变量，变量i从从0 开始递增开始递增1，直到，直到m为止，有为止，有： 循环结束：循环结束：s=m(m+1)/2n，或者，或者m(m+1)/2+k=n 。 n T(n)=m=O( ) n所以，该算法的时间复杂度为所以，该算法的时间复杂度为O( )。 则：则： 用于修正的常量用于修正的常量 8n+1- -8k m= - -1+ 2

13、空间空间复杂复杂度度：用于量度一：用于量度一个算法在运行过程中个算法在运行过程中临时占用的临时占用的存储空存储空 间间大小。大小。 一般一般也作为问题规模也作为问题规模n的的函数函数，采用数量级形式描述，采用数量级形式描述，记记作：作： S(n) = O(g(n) 若一个算法的空间复杂度为若一个算法的空间复杂度为O(1)，则称此算法为，则称此算法为原地工作原地工作或或就就 地工作算法地工作算法。 为什么空间复杂度分析只考虑为什么空间复杂度分析只考虑临时占用临时占用的的存储空间？存储空间？ maxfun() max() max(b,n) int max(int a,int n) int i, m

14、axi=0; for (i=1;iamaxi) maxi=i; return amaxi; void maxfun() int b=1,2,3,4,5,n=5; printf(Max=%dn,max(b,n); 如果如果max函数中再考虑形参函数中再考虑形参a的空间，就的空间，就 重复累计了执行整个算法所需的空间。重复累计了执行整个算法所需的空间。 max算法算法的的空间复杂度为空间复杂度为O(1) maxfun算法中为算法中为b数组分配了相应的内数组分配了相应的内 存空间，其空间复杂度为存空间，其空间复杂度为O(n) 【例例1- -6】 分析如下算法的分析如下算法的空间复杂度。空间复杂度。 解：解：算法算法中中临时分配的变量个数临时分配的变量个数与问题规模与问题规模n无关，所以空间无关，所以空间 复杂度均为复杂度均为O(1)。 int fun(int n) int i, j, k, s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; return(s); 临时占用的临时占用的 存储空间：存储空间： 函数体内分函数体内分 配的空间配的空间 本讲完本讲完