2010-2011-2《算法分析》ppt-6时空均衡

时空均衡基本思想对输入进行处理，来节省时间对存储结构进行处理，来节省时间对应问题：计数排序、字符串匹配散列法，以B树作索引先看例子例1Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程110)2()1(11)(nnnnFnFnF例1Fibonacci数列第n个Fibonacci数可递归地计算如下：intfibonacci(intn){if(n=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}时间复杂度：O(2n)空间复杂度：?例1Fibonacci数列非递归算法：intfibonacci(intn){intk,x,y,z;if(n=1)return1;x=1;y=1;for(k=1;k=n;k++){z=x+y;x=y;y=z;}returnz;}时间复杂度：O(n)空间复杂度：O(1)例2整数划分问题11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq求q(10,10)?q(10,10)=1+q(10,9)=1+q(10,8)+q(1,9)=1+q(10,8)+q(1,1)=2+q(10,8)=2+q(10,7)+q(2,8)=2+q(10,7)+q(2,2)=2+q(10,6)+q(3,7)+q(2,2)=2+q(10,5)+q(4,6)+q(3,3)+q(2,2)=2+q(10,5)+q(4,6)+q(3,3)+1+q(2,1)=3+q(10,5)+q(4,6)+q(3,3)+q(2,1)=4+q(10,5)+q(4,4)+1+q(3,2)=4+q(10,5)+q(4,4)+q(3,1)+q(1,2)=4+q(10,5)+q(4,4)+q(3,1)+q(1,1).......例2整数划分问题12345678910n111111111112122331415161718191101m空间换时间计数排序对每个元素，计算列表中比它小的元素个数。按个数大小为下标，存入到表中。元素列表：623184961947其他比它小个数314502排序193147628496字符串匹配字符串匹配问题：给定一个n个字符组成的串，称为文本T，一个m(=n)个字符组成的串，称为模式M，问：是否在文本中存在一个子串S，使得S=M？比如：T=abcd,M=bc显然，T的子串有{Ø,a,b,c,d,ab,bc,cd,abc,bcd,abcd}其中有一个子串是M.字符串匹配的蛮力法T=NOBODYNOTICEDHIMM=NOT匹配过程：移动+比较，每次向右移动一位新方法1、暴力法，O(n2)2、Horspool算法，O(n)3、Boyer-Moore算法，O(n)Horspool算法T=t0,t1,…,tk(=C),…,tn-1…M=BARBER移动：从左到右比较：从右到左Horspool算法Horspool算法1、如果在模式中没有当前比较的文本的元素（设为c），那么，可以移动模式长度后再重新开始比较。2、如果在模式中存在当前比较的文本的元素（设为c），但是不是模式的最后一个字符，那么，可以移动到把模式中最右边c，和文本中的c对齐。Horspool算法3、如果c正好是模式的最后一个字符，但是在模式的其他m-1个字符中不包含c，那么，可以移动模式长度后再重新开始比较。4、如果c正好是模式的最后一个字符，但是在模式的其他m-1个字符中也包含c，那么，可以移动到把模式中最右边c，和文本中的c对齐。。Horspool算法如何计算移动的距离？模式的长度T(c)=模式前m-1个字符中最右边的c到模式最后一个字符的距离c不包含在模式的前m-1个字符中。其他情况c是文本中的元素和模式“BARBER”对应的移动距离字符cABCDEF…R…Z_移动距离t(c)42661663666程序ShiftTable(P[0…m-1]){intTable[0…size-1],j;for(j=1;jsize;j++)Talble=m;for(j=1;j=m-2;j++)Table[P[j]]=m-1-j;returnTable;}HorspoolMatching(P[0…m-1],T[0…n-1]){ShiftTalble(P[0…m-1]);j=m-1;while(j=n-1){k=0;while(k=m-1&&P[m-1-k]==T[j-k]k=k+1;if(k==m)returnj-m+1;elsej=j+Table[T[j]];}return–1;}Boyer-Moore算法和Horspool算法的区别在：1、当第一次比较就不一样，那么处理方法和Horspool一样2、当已经有几个比较相同了，中间有一个比较不同，那么处理方法和Horspool就不一样了Boyer-Moore算法已经有几个相同了，碰到一个不同。1、坏符号移动：d1=max{t(c)-k,1}，文本2、好后缀移动：d2={suff(k)不在模式中的第二次出现，移动距离为模式长度。或者，suff(k)在模式中的第二次出现，分两种情况，1）suff(k)不出现在前缀中，suff(k)和第二次出现的位置差2）suff(k)出现在前缀中，suff(k)和前缀出现的位置差散列表基本思想：根据元素的值和位置的函数关系，利用此函数得到元素的存放位置。设存放的是一维数组，H[0…m-1]K=h(K),K是元素的值，h(K)是它存放的地址，这里可以是数组的下标。比如：h(K)=Kmodm散列函数要求1、分布均匀2、容易计算冲突解决方法1、开散列P204图7.5查找效率分析：负载因子：a=n/m,n是元素数量，m是单元个数。查找成功：S=1+a/2,不成功：U=a冲突解决方法2、闭散列：P205图7.6查找成功：S=[1+1/(1-a)]/2,不成功：U=[1+1/(1-a)2]/2会出现聚类现象：双散列重散列问题给你n个整数，请按从大到小的顺序输出其中前m大的数。每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。对每组测试数据按从大到小的顺序输出前m大的数。B树1972年由R.Bayer和E.McGreight发明，应用于结构化数据的组织中。特点：1、每个叶子可能包含若干个元素。2、所有叶子的元素是排好序的。3、父结点包含元素和指针，元素是由叶子结点的第一个元素构成。P209图7.8