2. 2. 算法算法分析分析p 算法（算法（Algorithm）是对特定问题求解步骤是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。指令表示一个或多个操作。1数据结构12算法分析课件2数据结构12算法分析课件3数据结构12算法分析课件Step1：寻找鸡蛋。分钟后仍没找到，打电话给老婆，终于找到。寻找鸡蛋。分钟后仍没找到，打电话给老婆，终于找到。Step2：洗鸡蛋。洗鸡蛋。Step3：打鸡蛋。轻轻磕，用力磕，用大力磕。打鸡蛋。轻轻磕，用力磕，用大力磕。Step4：清理操作台上的鸡蛋清。清理操作台上的鸡蛋清。Step 5：清理碗中的鸡蛋壳。用筷子夹，用勺子舀，用手抓，成功了：清理碗中的鸡蛋壳。用筷子夹，用勺子舀，用手抓，成功了（现在知道为什么要洗鸡蛋了吧）。（现在知道为什么要洗鸡蛋了吧）。Step6：搅拌。清理脸上、手上和衣服上的鸡蛋清。搅拌。清理脸上、手上和衣服上的鸡蛋清。Step 7：发现碗中的鸡蛋没剩下多少，又拿出两枚，重复：发现碗中的鸡蛋没剩下多少，又拿出两枚，重复Step 8：打火，打不着。还是打不着。怎么打也打不着。打火，打不着。还是打不着。怎么打也打不着。Step 9：打电话问老婆。打电话问老婆。Step 10：拧开气阀，终于打着了。拧开气阀，终于打着了。Step 11：擦红花油，简单处理脸部灼伤。擦红花油，简单处理脸部灼伤。Step 12：放油。放油。Step 13：倒掉红花油，重新放入花生油。哎，一字之差！倒掉红花油，重新放入花生油。哎，一字之差！Step 14：等待油热，并幻想老婆吃鸡蛋时被表扬。等待油热，并幻想老婆吃鸡蛋时被表扬。Step 15：救火，扇子扇，水泼，火越烧越大。救火，扇子扇，水泼，火越烧越大。Step 16：在浓烟中爬着去找电话。在浓烟中爬着去找电话。Step 17：在电话旁思考火警电话是、还是。在电话旁思考火警电话是、还是。4 4数据结构12算法分析课件haha()/*only a joke,do nothing.*/ main()printf(请稍等请稍等.您将知道世界的未日您将知道世界的未日.); while(1) haha(); 算法的五个重要的特性：算法的五个重要的特性： (1) 有穷性：有穷性：在有穷步之后结束，每一步都在有穷步之后结束，每一步都在有穷时间内完成。在有穷时间内完成。5数据结构12算法分析课件算法的五个重要的特性：算法的五个重要的特性： (1) 有穷性：有穷性：在有穷步之后结束，每一步都在有穷步之后结束，每一步都在有穷时间内完成。在有穷时间内完成。(2) 确定性：确定性：每一条指令必须有明确的含义，每一条指令必须有明确的含义，算法只有唯一的一条执行路径。算法只有唯一的一条执行路径。 (3) 可行性：可行性：可通过基本运算有限次执行来实现。可通过基本运算有限次执行来实现。6数据结构12算法分析课件p 输入：输入：有有0个或多个输入；个或多个输入；p 输出：输出：有一个或多个输出；有一个或多个输出；getsum(int num)int i,sum=0; for(i=1;i=num;i+) sum+=i; 算法的五个重要的特性：算法的五个重要的特性： 无输出的算法没有任何意义无输出的算法没有任何意义 ! !7数据结构12算法分析课件p 确定性：确定性：算法中每一条指令必须有确切的含义，读者理算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在相同的条件下，算法对于相同的输入解时不会产生二义性。在相同的条件下，算法对于相同的输入只能得出相同的输出。只能得出相同的输出。p下面代码有何问题？下面代码有何问题？float average(int *a,int num) /* num为数组为数组a元素个数元素个数 */ int i;double sum=0; for(i=0;ib) if(ac) return a; else return c; else if(bc) return b; else return c; / *无需额外存储空间，只需无需额外存储空间，只需两次比较两次比较 */max(int a3)int c,int i; c=a0; for(i=1;ic) c=ai; return c; /* 需要两个额外的存储空间，两次需要两个额外的存储空间，两次比较，至少一次赋值比较，至少一次赋值 */* 共需共需5个整型数空间个整型数空间 */ 求求100个整数中最大个整数中最大者者同上的算法难写，难读同上的算法难写，难读max(int a100)int c,int i; c=a0; for(i=1;ic) c=ai; return c; /* 共需共需102个整型数空间个整型数空间 */ 效率与存储量分析效率与存储量分析22数据结构12算法分析课件算算法法分分析析（Algorithm Analysis）：对对算算法法所所需需要要的的计计算机资源算机资源时间时间和和空间空间进行估算。进行估算。 时间复杂性（时间复杂性（Time Complexity） 空间复杂性（空间复杂性（Space Complexity）算法分析算法分析23数据结构12算法分析课件同一问题可以采用多种算法实现。如何比较同一问题可以采用多种算法实现。如何比较算法执行效率？算法执行效率？ 算法选用的策略算法选用的策略算法选用的策略算法选用的策略问题的规模：求解的输入量问题的规模：求解的输入量问题的规模：求解的输入量问题的规模：求解的输入量采用的程序语言采用的程序语言采用的程序语言采用的程序语言编译程序的好坏编译程序的好坏编译程序的好坏编译程序的好坏机器执行速度机器执行速度机器执行速度机器执行速度 因此，使用因此，使用因此，使用因此，使用绝对时间单位绝对时间单位绝对时间单位绝对时间单位衡量算法的效率不合适衡量算法的效率不合适衡量算法的效率不合适衡量算法的效率不合适24数据结构12算法分析课件问题规模：问题规模：输入量的多少输入量的多少基基本本语语句句（程程序序步步）：被被视视为为算算法法基基本本运运算算的的一一般是般是最深层循环内的语句。最深层循环内的语句。for (i=1; i=n; i+) for (j=1; j=n; j+) x+;问题规模：问题规模：n基本语句：基本语句：x+算法分析算法分析25数据结构12算法分析课件 在在一一个个算算法法中中, ,进进行行基基本本运运算算的的次次数数越越少少, ,其其运运行行时时间间也也就就相相对对地地越越少少；基基本本运运算算次次数数越越多多, ,其其运运行行时时间也就相对地越多。间也就相对地越多。 所所以以, ,通通常常把把算算法法中中包包含含基基本本运运算算次次数数的的多多少少称称为为算算法法的的时时间间复复杂杂度度, ,也也就就是是说说, ,一一个个算算法法的的时时间间复复杂杂度是指该算法的基本运算次数度是指该算法的基本运算次数。 算法中算法中基本运算次数基本运算次数T(n)是问题规模是问题规模n的某个函数的某个函数f(n),记作记作： T(n)=O(f(n)26数据结构12算法分析课件定定理理：若若A(n)=amnm+am-1nm-1+a1n+a0是是一一个个m次多项式，则次多项式，则A(n)=O(nm)。说明：说明：在计算算法时间复杂度时，可以在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数忽略所有低次幂和最高次幂的系数。算法分析算法分析算法分析算法分析大大O符号符号27数据结构12算法分析课件算法的时间复杂度一个没有循环的算法的基本运算次一个没有循环的算法的基本运算次数与问题规模无关：数与问题规模无关： O（1）常数阶）常数阶一个只有一重循环的算法的基本运一个只有一重循环的算法的基本运算次数与问题规模呈线性增大关系：算次数与问题规模呈线性增大关系： O（n）线性阶）线性阶28数据结构12算法分析课件算法的时间复杂度O(1) O(log2(n)O(n)(n2)O(n3)O(2n)29数据结构12算法分析课件 例例： 求求两两个个n阶阶方方阵阵的的相相加加C=A+B的的算算法法如如下下,分析其时间复杂度。分析其时间复杂度。 #define MAX 20 /*定义最大的方阶定义最大的方阶*/ void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)for (j=0;jn;j+) Cij=Aij+Bij; 30数据结构12算法分析课件 该该算算法法中中的的基基本本运运算算是是两两重重循循环环中中最最深深层层的的语语句句Cij=Aij+Bij,分析它的频度分析它的频度,即即： T(n)= =O(n2)31数据结构12算法分析课件例：例： 分析以下算法的时间复杂度。分析以下算法的时间复杂度。 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=1 & change; -i)change=FALSE;for(j=0; jaj+1)aj ai+1; change = TRUE35数据结构12算法分析课件分析：分析：输入集合升序：基本操作次数为输入集合升序：基本操作次数为0输入集合逆序：操作次数为：输入集合逆序：操作次数为：n(n-1)/2T(n)= =4 =O(n2)36数据结构12算法分析课件分析下面语句的时间复杂度：分析下面语句的时间复杂度：i=1; while(i=n)i = i*2;分析：分析：设语句设语句i = i*2的语句频度为的语句频度为f(n)，则有，则有2 f（n）=n，即，即f（n）=log2n，所以该程，所以该程序段的时间复杂度序段的时间复杂度T（n）= O(log2n)。37数据结构12算法分析课件分析下面语句的执行次数：分析下面语句的执行次数：i=0; s=0; n=100;doi = i+1;s = s+10*iwhile(NOT(in) AND (sn);分析：分析：该程序段中，循环语句的执行次数为该程序段中，循环语句的执行次数为4（这时（这时i = 4，s = 100），），do循环中先执循环中先执行循环体，后判断条件，直到条件为真时行循环体，后判断条件，直到条件为真时退出循环。退出循环。38数据结构12算法分析课件算法空间复杂度度量算法空间复杂度度量一个算法一般占用三部分存贮空间一个算法一般占用三部分存贮空间算法本身占用算法本身占用输入、输出数据占用：输入、输出数据占用：算法运行中临时占用空间（可变部分）算法运行中临时占用空间（可变部分）算法的空间性能以一个算法运行过程中算法的空间性能以一个算法运行过程中临时占用临时占用的存储空间作为度量标准的存储空间作为度量标准算法空间复杂度，记作算法空间复杂度，记作S(n)=O(f(n)S(n)=O(f(n)时间和空间相互之间有一种制约关系，时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。何者为重需视具体情况而定。39数据结构12算法分析课件算法空间复杂度度量算法空间复杂度度量若额外空间相对于输入数据量来说是常若额外空间相对于输入数据量来说是常数，则称此算法为数，则称此算法为原地工作原地工作。40数据结构12算法分析课件基本操作的实现：基本操作的实现： 本书约定：本书约定：常量的定义：常量的定义： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2数据元素类型约定为：数据元素类型约定为：ElemType typedef int Status; /函数类型，函数结果状态代码函数类型，函数结果状态代码 4141数据结构12算法分析课件练习：练习：1、有下列运行时间函数有下列运行时间函数,分别写出相应的大分别写出相应的大O表示的运算表示的运算时间。时间。(1) T1 (n)=1000; (2) T2 (n)=n2 +1000n;(3) T3(n)= 3n3+100n2+n+1;2、分析下面语句的时间复杂度：、分析下面语句的时间复杂度：(1)for(i=1;i=n;i+) (2) i=1;k=0;for(j=1;j=i;j+) while(i=n-1)s+;k+=10*i;i+;42数据结构12算法分析课件解答：解答：2、分析下面语句的时间复杂度：、分析下面语句的时间复杂度：(1)for(i=1;i=n;i+) (2) i=1;k=0;for(j=1;j=i;j+) while(i=n-1)s+;k+=10*i;i+;(1)：n*(1+2+(n+1)=O（n2)(2)：i=1：语句执行一次；：语句执行一次；k=0：语句执行：语句执行1次次 n=1：循环不满足，不执行：循环不满足，不执行 n=2：循环执行一次：循环执行一次 总的执行次数：总的执行次数：1+1+2*（n-1），），O(n)43数据结构12算法分析课件