《数据结构A》第01章.ppt

输入：算法有零个或多个输入 输出：算法至少产生一个输出 确定性：算法的每一条指令都有确切的定义，没有二义性。 能行性：算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。 有穷性：算法必须总能在执行有限步之后终止。 1.5.2 算法的时间复杂度 算法的时间复杂度 是程序运行从开始到结束所需的时间。 程序步 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。 float Sum(float list[],const int n) { //此程序的程序步数为2n＋3 float tempsum=0.0; count ++; //针对赋值语句 for (int i=0; in; i++ ){ count ++； //针对for循环语句 tempsum += list[i]; count ++; //针对赋值语句 } count ++; //针对for的最后一次执行 count ++; //针对return语句 return tempsum; } 1.5.3 渐近时间复杂度 定义:（大O记号） 设f(n)和g(n) 是定义在正整数上的正函数，如果存在两个正常数 c 和n0 ，使得当 n? n0 时，有 f(n)? c g(n) 则记作 f(n)=O(g(n))。 定理 如果 f(n)＝amnm+am-1nm-1+…+a1n+a0 是m次多项式，则 f(n)＝O(nm) 例：T(n)＝ 3.6n3 + 2.5 n2 + 2.8＝O(n3) 渐近时间复杂度 使用大O记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。渐近时间复杂度也常简称为时间复杂度。通常用O(1)表示常数计算时间，即算法只需执行有限个程序步。 关键操作 很多情况下，可以通过考察一个程序中的关键操作（关键操作被认为是一个程序步）的执行次数来计算算法的渐近时间复杂度。有时也需要同时考虑几个关键操作，以反映算法的执行时间。 例 void Mult(int a[n][n], b[n][n], c[n][n], int n) { // n?n矩阵a与b 相乘得到c。 for (int i=0;in;i++) // n+1 for(int j=0;jn;j++){ // n(n+1) c[i][j]=0; // n2 for (int k=0;kn;k++) // n2（n+1) c[i][j]+=a[i][k]*b[k][j]; // n3 } } 程序步为：2n3 +3n2 + 2n+1 c[i][j]+＝a[i][k]*b[k][j]可看成关键操作 渐近时间复杂度为：T(n)=O(n3) 算法按时间复杂度分类 多项式时间算法 O(1) O(log2 n) O(n) O(nlog2 n) O(n2) O(n3) 指数时间算法 O(2n)O(n!)O(nn) 1.5.4 最好、最坏和平均时间复杂度 例子：在一个有n个元素的数组中查找一个指定元素，某个有哪些信誉好的足球投注网站算法从第一个元素开始，一次检查一个数组元素。 上节课练习 （1）在数据结构中，从逻辑上可以把数据结构分成 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 (2)两种常用的数据结构的物理存储方式有顺序存储和______ A.线性表存储 B.散列结构存储 C.集合结构存储 D.链式存储 (3) 对于给定的n个元素,可以构造出的四种逻辑结构是 、 、 、_ __。 上节课练习 有下列二元组表示的数据结构，请指出属于何种逻辑结构。 S={D，R}；D={ a，b，c，d，e，f，g，h} ；R={d,b,d,g,d,a,b,c,g,e,g,h,e,f} 本章总结 数据结构基本概念 数据结构的分类 算法及时间复杂度计算 大连东软信息学院 张明会 2011年9月 NeuSoft 大连东软信息学