[理学]数据结构第一章.ppt

第一章 绪 论 在计算机发展的初期，计算机主要用于科学计算，因此程序设计者的主要精力集中在程序设计的技巧上，而不重视数据结构。当时处理一个计算问题的一般步骤为： 例2 书目自动检索系统 例3 人机对奕问题 例4：多叉路口交通灯管理问题 (5)输出:一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 3、算法的描述方法 (1)自然语言 (2)流程图 (3)高级语言或类高级语言 4、对算法设计的要求 评价一个好的算法有以下几个标准: (1)正确性(Correctness )：算法应满足具体问题的需求。对于程序而言，“正确”一词有四层含义： 1）程序中不含语法错误。 2）程序对几组输入数据能得出满足规格说明书要求的结果。 3）程序对于精心选择的典型、苛刻而带有刁难性的输入数据能得出满足规格说明要求的结果。 目录 上页 下页 结束 4）程序对一切合法输入都能产生满足规格说明要求的结果。 (2)可读性(Readability) 算法应该清晰、容易理解。 (3)健状性(Robustness) 对于异常或者非法的数据输入，算法应该可以进行处理。 (4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。 5、对算法效率的度量 对预算法效率的度量一般有两种方法： (1)事后统计:利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。 缺点：?必须先运行依据算法编制的程序。 目录 上页 下页 结束 ?所得时间统计量依赖于硬件、软件等环境因素，掩盖了算法本身的优劣。 (2)事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于： ? 依据的算法选用何种策略 ? 问题的规模 ? 程序语言 ? 编译程序产生机器代码质量 ? 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率是不合适的。 目录 上页 下页 结束 一般情况下，撇开计算机软、硬件因素，只考虑问题的规模。算法中基本操作重复执行的次数一般是问题规模n的某个函数f(n)，可以将算法的时间量度记作： T(n)=O(f(n)) 称作算法的渐近时间复杂度，简称时间复杂度。 例１ for(i=1，i=n;++i) for(j=1;j=n;++j) { c[i][j]=0; for(k=1;k=n;++k) c[i][j]+=a[i][k]*b[k][j]; } 目录 上页 下页 结束 上面的例1由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3 　 故：时间复杂度为T(n)=O(n3) 语句的频度：是指该语句重复执行的次数。 例2，在下面三个程序段种： 1） {++x;s=0;} 2） for(i=1;i=n;++i) {++x;s+=x;} 3） for(i=1;i=n;++i) 　　　　for(j=1;j=n;++j) {++x;s+=x;} 基本操作“x增1” 的语句频度分别为１，n，n2，则这三个程序段的时间复杂度分别为: O(1)，O(n)，O(n2)，分别称为常量阶、线性阶和平方阶。 目录 上页 下页 结束 一般情况下，算法还可能呈现的时间复杂度有：对数阶O(logn)，指数阶O(n2)等。 常见的时间复杂度的关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。 当n很大时，指数时间复杂度的算法和多项式时间复杂度O(nk)的算法在所需时间上非常悬殊。 目录 上页 下页 结束 因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 例3 for(i=2;i=n;++i) for(j=2;j=i-1;++j) {++x;a[i,j]=x;} 语句频度为： 1+2+3+…+n-2=(1+n-2)×(n-2)/2 =(n-1)(n-2)/2