《第一章 算法分析.ppt》由会员分享，可在线阅读，更多相关《第一章 算法分析.ppt（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第第1 1章章 算法分析算法分析21世纪高等院校规划教材 返回总目录返回总目录返回总目录返回总目录 算法分析算法分析n n关于算法关于算法n n算法复杂度（算法复杂度（Big-OBig-O）1.2006关于算法关于算法n n是解决问题（problems）的有限步骤程序n n利用算法可以实现顺序查找1.2006数组元素相加的算法数组元素相加的算法 n n将将数数组组中中每每个个元元素素相相加加后后返返回回总总和和。实实现现该该算算法法的的程程序序段如下所示：段如下所示：执行次数执行次数 int int sum(sum(int arrint arr,intint n)n)intint i,tot
2、al=0;i,total=0;1 1 for(i=0;in;i+)for(i=0;in;i+)n+1 n+1 total+=total+=arrarri;i;n n return total;return total;1 1 上述程序段中语句的执行次数总和为上述程序段中语句的执行次数总和为1+1+n+1+n+1=2n+3n+1+n+1=2n+3。1.2006矩阵相乘的算法矩阵相乘的算法 void void mulmul(intint a,a,intint b,b,intint c,c,intint n)n)执行次数执行次数 IntiInti,j,k,sum;1,j,k,sum;1 for(i=
3、0;in;i+)n+1 for(i=0;in;i+)n+1 for(j=0;jn;j+)n(n+1)for(j=0;jn;j+)n(n+1)sum=0;nsum=0;n2 2 for(k=0;kn;k+)nfor(k=0;kn;k+)n2 2(n+1)(n+1)sum=sum+aik*bkj;nsum=sum+aik*bkj;n3 3 cij=sum;ncij=sum;n2 2 1.2006折半查找的算法折半查找的算法intint search(search(intint data,data,intint target,target,intint n)n)intint i,mid,lower=
4、0,upper=n-1;i,mid,lower=0,upper=n-1;mid=(lower+upper)/2;mid=(lower+upper)/2;while(lowerupper)while(lower target)if(datamid target)upper=mid-1;upper=mid-1;1.2006折半查找的算法（续）折半查找的算法（续）elseelse lower=mid+1;lower=mid+1;mid=(lower+upper)/2;mid=(lower+upper)/2;1.2006斐波那契数列（递归的程序段）斐波那契数列（递归的程序段）int Fibonacci
5、int Fibonacci(intint n)n)if(n=0)if(n=0)return 0;return 0;else else if(n=1)if(n=1)return 1;return 1;else else return(return(FibonacciFibonacci(n-1)+(n-1)+FibonacciFibonacci(n-2);(n-2);1.2006斐波那契数列（非递归的斐波那契数列（非递归的程序段）程序段）int Fibonacciint Fibonacci(intint n)n)intint prev1,prev2,item,i;prev1,prev2,item,
6、i;if(n=0)if(n=0)return 0;return 0;elseelse if(n=1)if(n=1)return 1;return 1;else else prev2=0;prev2=0;prev1=1;prev1=1;for(i=2;i=n;i+)for(i=2;i=n;i+)item=prev1+prev2;item=prev1+prev2;prev2=prev1;prev2=prev1;prev1=item;prev1=item;return item;return item;1.2006顺序查找顺序查找的算法的算法intint search(search(intint d
7、ata,data,intint target,target,intint n)n)intint i;i;for(i=0;in;i+)for(i=0;innn0 0时时都都满满足足f(n)cg(n)f(n)cg(n)，则则f(n)=O(g(n)f(n)=O(g(n)n n数数组组元元素素的的Big-OBig-O为为O(n)O(n)，起起泡泡排排序序为为O(nO(n2 2)，而而矩矩阵阵乘乘法法为为O(nO(n3 3)，顺顺序序查查找找为为O(n)O(n)，折折半半查查找找为为O(O(lognlogn)，而而斐斐波波那那契契数数列列若若以以递递归归处处理则为理则为O(2O(2n/2n/2)，若以非递归方式处理则为若以非递归方式处理则为O(n)O(n)1.2006 图图 使用递归方式的斐波那契数列的示意图使用递归方式的斐波那契数列的示意图 1.2006