数据结构1绪论课件.pptVIP

for (初始化语句;表达式1;表达式2) … 第一次执行的步数＝初始化语句与表达式1的程序步数之和． 后续执行的程序步数＝表达式1与表达式2的程序步数之和 if-then语句： 　if (表达式) 语句1；表达式的步数＋语句１的步数 　else 语句2；　　　　 表达式的步数＋语句２的步数 函数执行语句：一般为１ 动态存储管理语句：new，delete 为１ 转移语句：为１ 以上面所举的选择排序为例： for (int i=0; in-1; i++) { int k = i; 　for (int j=i+1; jn; j ++) if (a[j] a[k]) k = j; 　int temp=a[i]; a[i]=a[k]; a[k]=temp; } 总的执行步数＝3 /2 +9n/2-5 记作 T(n)= 3 /2 +9n/2-5，当n ∞时，T(n)/ 常数( 1 ) 故T(n)=O( ) ,称为算法的时间复杂度(time complexity). 　　　　　数量级　 程序执行的步数(频度) n n-1 n+n-1+…+2= ( +n-2)/2 ≤2(1+2+…+n-1)= -n 3(n-1) ⑵．渐进表示法 　　对有n个元素的数组，如果采用顺序查找方法，而且假设每一个元素的查找概率相等．则其查找成功的平均比较次数为： 　　T(n)=(1+2+…+n)/n=(1/n)*n*(n+1)/2=(n+1)/2=O(n) 一般而言要全面分析一个算法： 　 算法在最坏情况下的时间代价 　 算法在最好情况下的时间代价　　 　 算法在平均情况下的时间代价　　 时间复杂度的数量级有： 　O(n), O( n2 ), O(n3 ), O( 2n ), O(log2n) ,O(n*log2n ) 线性 平方阶 立方阶　指数阶　　 对数阶 按数量级递增排列，依次为： 常数阶 O(1) 对数阶 O(log2n) 线性阶 O(n) 线性对数阶 O(nlog2n) 平方阶 O(n2) 立方阶 O(n3) 指数阶 O(2n)等等。 时间复杂度主要在算法的循环程序段中： 　 单个循环　　　　 并列的循环　　　　　 嵌套并列 O(n) O(n) O(m) O(n) T(n,m)=T1(m)+T2(n) =O(max(f(n),g(m))) O(m*n) O(m) O(max(m*n,m)) =O(m*n) 3). 空间复杂度的度量 考虑渐进的空间复杂度，即用O(n)方式来表示。 算法分析例子： 1)for (int i=1; i=n; i++) for (int j=1; j=n; j++) { c[i][j] = 0.0; for ( int k = 1; k=n; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j]; } 2) for(i=1;i=n;i++) for(j=i;j=n;j++) s++; 算法分析例子： 1) for(i=1;i=n;i++) for(j=1;j=i;j++) s++; 2) x = 0; y = 0; for ( int i= 1; i=n; i++) for ( int j = 1; j =i ; j++) for ( int k = 1; k=j; k++) x = x + y; * * 程序执行的步数不正确！频度与步数应该不是一回事！ 数据结构 1．学习数据结构课的目的与内容 2．什么是数据结构 3．抽象数据类型概念 4．算法定义 5．性能分析与度量 第 1 章　绪论 1．学习本课程的目的和内容 １)介绍常用的数据结构和算法 用什么样的数据结构来描述你要解的问题： 线性表、树、图 解以上问题的数据结构已不是整型，浮点型，布尔型，双精度型（数值计算用到的数据基本类型），而是表，树，图等非数值型的数据结构及其操