数据结构概述

数据结构与算法基础

第三部分：算法及效率度量算法、算法的特性算法好坏的评价标准算法的性能度量方法渐进时间困难度渐进空间困难度主要内容算法：对特定问题的求解过程的描述，是指令的有限序列，也就是为解决某一具体问题而实行的具有有限的操作步骤。程序是算法的实现，计算机依据程序逐步执行算法，实现对问题的求解。定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。算法五个特性：输入有0个或多个输入输出有一个或多个输出（处理结果）确定性每步定义都是精确、无歧义的有穷性算法应在执行有穷步后结束有效性每一条运算应足够基本能被执行算法的特性常用的设计方法：穷举法贪心法分治法回溯法动态规划法裁剪与分枝界限法并行算法算法的分类事例学习：选择排序问题明确问题：非递减排序解决方案：逐个选择最小数据算法框架：

for(inti=0;i<n-1;i++){//n-1趟

从a[i]检查到a[n-1];

若最小的整数在a[k],交换a[i]与a[k];

}细化程序：程序SelectSort

算法设计过程

自顶向下，逐步求精

voidselectSort(inta[],constintn){//对n个整数a[0],a[1],…,a[n-1],按非递减依次排序for(inti=0;i<n-1;i++){intk=i;//从a[i]检查到a[n-1],找最小的整数,在a[k]for(intj=i+1;j<n;j++) if(a[j]<a[k])k=j; //k指示当前找到的最小整数inttemp=a[i];a[i]=a[k];a[k]=temp;//交换a[i]与a[k]}} 正确性（Correntness）满足具体问题的需求，对于典型的、苛刻的一组输入数据得到正确的结果可读性（Readability）有利于阅读者对程序的理解健壮性（Robustness）容错处理效率（Efficiency）效率和低存储需求评价算法优劣的基本标准intsign(intx){inty;if(x>0)y=1;elseif(x=0)y=0;elsey=-1;returny;}第一个层次程序不包含语法错误intsign(intx){inty;if(x>1)y=1;elseif(x==0)y=0;elsey=-1;returny;}其次个层次输入100输出1输入0输出0输入－100输出－1intsign(intx){inty;if(x>=1)y=1;elseif(x==0)y=0;elsey=-1;returny;}第三个层次输入100输出1输入1输出1输入0输出0输入-1输出-1输入-100输出-1intsign(intx){inty;if(x>0)y=1;elseif(x==0)y=0;elsey=-1;

if(x==0x1234)y=0;returny;}第四个层次全部可能的输入解决同一个问题存在多种算法，如何评估各种算法的好坏？运行算法所须要的计算机资源——时间和空间评价一个算法的优劣的重要依据看执行该算法的程序占用多少计算机资源程序所用算法运行时所要花费的时间代价程序中运用的数据结构占用的空间代价如何评价？算法的后期测试：试验方法、仿真方法算法的事前估计：分析的方法算法效率的度量试验的方法：接受实际数据测试程序的执行时间；仿真的方法：模拟数据进行测试；在算法中的某些部位插装时间函数time()或者clock()测定算法完成某一功能所花费的时间。接受开发工具供应的时间测量工具profile算法的后期测试依次搜寻(SequenialSearch)行intseqsearch(inta[],constintn, constintx)//a[0],…,a[n-1]1{2inti=0;3while(i<n&&a[i]!=x)4i++;5if(i==n)return-1;6returni;7}

插装clock()的计时程序voidTimeSearch(){//在0..1000中搜寻0,10,…,90,100,200,…,1000inta[1001],n[20];for(intj=0;j<=1000;j++)a[j]=j;//a[1]=1,a[2]=2,…for(j=0;j<10;j++){ n[j]=10*j;//n[0]=0,n[1]=10,n[2]=20n[j+10]=100*(j+1);}//n[10]=100,n[11]=200,n[12]=300...printf("%12s%12s%12s\n","n","500000","1");

for

(j=0;j<20;j++){

clock_t

start,stop; start=clock();

longcount=500000;

while(count--)

int

k=seqsearch(a,1001,n[j]);

stop=clock();

doublerunTime=stop–start;

printf(“%12d%12d%12.6f\n”,n[j],runTime,

double(runTime)/500000);

}

}程序测试结果输出程序在计算机上运行所需时间的影响因素算法本身选用的策略问题的规模规模越大，消耗时间越多书写程序的语言语言越高级，消耗时间越多编译产生的机器代码质量机器执行指令的速度为便于比较算法本身的优劣应解除其它影响算法效率的因素希望软件执行时间可预料算法分析感爱好的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随着规模增长的值是可预料的。算法的事前估计希望了解软件执行时间的变更趋势与问题规模之间的关系，用确定的规模数据作为输入时程序所需的基本操作的次数来描述时间效率忽视微小环节完成一个基本操作所须要的时间应当与具体的被操作数无关算法的困难性分析例以迭代方式求累加和的函数行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

for(

inti=0;i<n;i++)

4

s+=a[i];

5

returns;

6

}

程序步确定方法

插入计数全局变量count

建表，列出个语句的程序步计算累加和程序

程序步数计算工作表格

语句执行的频度2n+3程序的精确步数没有实际意义，程序步数的数量级别可以反映程序的实质。n：一个特定算法的“运行工作量”的大小，只依靠于问题的规模（通常用整数量n表示）f(n):算法中基本操作的执行次数，即它是问题规模的函数。算法的渐进时间困难度，简称算法时间困难度记作：

T(n)=O(f(n))

表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。表示算法执行时间的增长的数量级。时间困难度的渐进表示法大O表示法定义当N≥N0时存在一个正的常数c和N0，使得T(n)≤cF(n),则（Big-Oh）T(N)就是O(F(n))含义：当n增大时，算法的运行时间的增长率小于等于Ｆ(n)的增长率。算法的渐进分析就是要估计，当数据规模逐步增大时资源开销f(n)的增长趋势，得到一个精确的界限比较费时费劲，也没有必要时间困难度的渐进表示法从数量级大小比较来考虑，当n增到到确定值后，对资源开销影响最大的就是n的幂次最高的项，所以运用Big-Oh表示法时不必考虑常数、系数、次要项和关系符号。O(n2)√O(2n2+2n+1)×常见的算法时间困难度：1<log2n<n<nlog2n<n2<n3<2n<3n<n!算法时间困难度的分析规则依据程序的结构分析时间困难度时间困难度的渐进表示法加法规则针对并列程序段：依次结构，if结构，switch结构T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))乘法规则针对嵌套程序段；for，while，dowhile

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))

时间困难度计算例1：x++;s=0; 用频度法分析：将x++看成是基本操作，语句频度为１ T(n)=2 算法的时间困难度：O(1)---常量阶例2:for(i=0;i<n;i++){ //执行n+1次x++;//语句频度为：ns+=x;//语句频度为：n} T(n)=2n+n+1=3n+1，则时间困难度为：O(n) 也可以这样考虑：将x自增看成是基本操作，则语句频度为：n其时间困难度为：O(n)，即时间困难度为线性阶。例3:矩阵相乘C=AxBfor(i=0;i<n;i++) //n+1for(j=0;j<n;j++){//n*(n+1)c[i][j]=0; // n2for(k=0;k<n;k++)//n2*(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}T(n)=2n3+3n2+2n+1算法的时间困难度：O(n3)计算方法1：由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3故时间困难度为T(n)=O(n3)。计算方法2：由于“乘法”运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，故时间困难度为T(n)=O(n3)。时间困难度计算1-26

例4:分析以下程序段的时间困难度 i=1;//语句频度为：１ while(i<=n) i=i*2//语句频度为：f(n) 因为：２f(n)≤n，即：f(n)≤log2n，取最大值f(n)=log2n，则该程序的时间困难度为： T(n)=1+f(n)=1+log2n=O(log2n)时间困难度计算1-27

时间困难度计算算法中基本操作重复执行的次数随问题的输入数据集不同而不同例6：在数组A[n]查找给定值K(1)i=0;(2)while(i<=n-1&&A[i]!=K)(3)i=i+1;(4)returni;最好状况的时间困难度T(n)=O(1)A[0]等于K最坏状况的时间困难度T(n)=O(n)A[n-1]等于Ｋ平均时间困难度： 全部可能的输入实例以等概率出现的状况T(n)=(1+2+...+n)/n 算法的时间困难度：O(n)1-28

时间困难度按数量递增排列及增长率一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)指数时间的关系为：O(nk)<O(2n)<O(n!)<O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上特殊悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个宏大的成就。增长率函数曲线存储空间的固定部分

程序指令代码的空间，常数、简洁变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分

尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete叮嘱动态运用的空间空间困难度的度量只考虑程序运用的可变部分空间运用状况空间困难度度量渐进的空间困难度一个算法为解决问题所用帮助存储空间的大小，只依靠于问题的规模（通常用整数量n表示），即它是问题规模的函数。算法的渐进空间困难度，简称算法空间困难度记作：

S(n)=O(f(n))

表示最坏状况下，算法所需帮助存储空间的数量是实例特性n的某个函数的数量级，表示所需存储空间增长的数量级。例解法1先计算x的幂,存于power[]中,再分别乘以相应的系数#