《数据结构》算法分析.ppt

2.9.3 常数阶 事实上无论n为多少，上面的两段代码就是3次和12次执行的差异。 这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。 注意：不管这个常数是多少，都记作O(1)；单纯的分支结构，其时间复杂度也是O(1)。 2.9.4 线性阶 线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常要确定某个特定语句某个语句集的运行次数。 因此，我们要分析算法的时复杂度，关键就是要分析循环结构的运行情况。 时间复杂度是多少？ 2.9.5 对数阶 时间复杂度是多少？ 2.9.6 平方阶 时间复杂度是多少？ 2.9.6 平方阶 时间复杂度是多少？ 循环时间复杂度等于循环体的复杂度乘以该循环运行的次数。 2.9.6 平方阶 时间复杂度是多少？ 2.9.6 平方阶 时间复杂度是多少？ 2.9.6 平方阶 时间复杂度是多少？ 2.9.6 平方阶 时间复杂度是多少 ？ 2.10 常见的时间复杂度 常用的时间复杂度所耗费的时间从小到大依次是： O(1)O(㏒n)O(n)O(n㏒n)O(n2)O(n3) O(2n)O(n!)O(nn) 2.11 最坏情况与平均情况 最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。 平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。 一般在没有特殊说明的情况下，都是指最坏时间复杂度。 2.12 算法空间复杂度 算法的空间复杂度通过计算算法所需的存储空间实现。 算法空间复杂度的计算公式记作：S(n)=O(f(n))。 其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。 例 1：{++x;} 将++x看成是基本操作，则语句频度为1，其时间复杂度为O(1)，即常数阶。 例2：for(int i=1;i=1000;i++) {++x;} 将++x看成是基本操作，则语句频度为1000，其时间复杂度仍为O(1)，即常数阶。 例3：for(i=1;i=n;++i) {++x;} 语句频度为n，其时间复杂度为：O(n) 例４：for(i=1;i=n;++i) 　　　　 for(j=1;j=n;++j) {++x;} 语句频度为n2 ，其时间复杂度为：O(n2) 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)　　　　　　　　 例５：for(i=2;i=n;++i) for(j=2;j=i-1;++j) {++x; } 语句频度为1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2 )/ 2 ∴时间复杂度为O(n2)，表示为：T(n)=O(n2) 第二章习题 1.1下面程序的时间复杂度为_____。 for(i=1，im；i++) for(j=0；jn；j++) A[i][j]=I＊j; A.O(m2) B.O(n2) C.O(m＊n) D.O(m+n) 1.2下列程序的时间复杂度为 X=n; /*n1*/ y=0; while((x=(y+1)*(y+1)) y=y+1; A.O(n) B.O( ) C.O(1) D.O(n2) 1.3下列程序的时间复杂度为 int i=1; while(i=n) i=i*2; A.O(n2 ) B.O(log2n) C.O( ) D.O(n) 答案： C B B 复习 1.算法与程序的区别？ 2. 算法的特性及其评价标准？ 3.什么是算法的时间复杂度？ 4.怎样计算算法的时间复杂度？ To be continued… 第2章 算法 复习 1、什么是数据结构？ 2、本课程主要研究什么？ 3、什么是数据的逻辑结构和物理结构？ 4、数据的逻辑结构有哪几种？存储结构有哪两种形式？ 5、逻辑结构与物理结构间的关系？ 数据结构主要研究什么？ 数据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的课程。 数据的逻辑结构 数据的存储结构 数据的操作(算法)：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链