数据结构课程PPT第1章绪论讲述.ppt

  1. 1、本文档共99页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构课程PPT第1章绪论讲述

在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少;基本运算次数越多,其运行时间也就相对地越多。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作:     T(n)=O(f(n)) 记号“O”读作“大O”,它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。“O”的形式定义为: 若f(n)是正整数n的一个函数,则T(n)=O(f(n))表示存在一个正的常数M,使得当n≥n0时都满足: |T(n)|≤M|f(n)| 也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时算法的时间性能。 例如,T(n)=3n2-5n+10000=O(n2) 本质上讲,是一种最高数量级的比较 一个没有循环的算法的基本运算次数与问题规模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!) 思考题:   为什么要进行算法的时间复杂度分析? 例1.4 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #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) 例1.5  分析以下算法的时间复杂度。 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); } 基本语句或基本操作 解:该算法的基本操作是语句s++,其频度: T(n)= =O(n3) 则该算法的时间复杂度为O(n3)。 例1.6  分析以下算法的时间复杂度。 void func(int n) { int i=0,s=0; while (sn) { i++; s=s+i; } } 基本语句 解:对于while循环语句,设执行的次数为m,i从0开始递增1,直到m为止,有: s=0+1+2+…+(m-1)=m(m-1)/2, 并满足s=m(m-1)/2n,则有m< 。 T(n)=O( ) 所以,该算法的时间复杂度为O( )。 例1.7 有如下算法: void fun(int a[],int n,int k) //数组a共有n个元素 { int i; if (k==n-1) for (i=0;in;i++)   //n次 printf(%d\n,a[i]); else { for (i=k;in;i++)  //n-k次 a[i]=a[i]+i*i; fun(a,n,k+1); } } 调用上述算法的语句为fun(a,n,0),求其时间复杂度。 解:设fun(a,n,0)的时间复杂度为T(n),则fun(a,n,k)的执行时间为T1(n,k),由fun()算法可知: T1(n,k)=n 当k=n-1时 T1(n,k)= (n-k)+T1(n,k+1) 其他情况 则 T

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档