对滚动数组算法的时间空间分析

1、对滚动数组求解转换方案进行的分析经过观察发现，该动态规划方程只耑要保存数组的三行即可求出最小费用的答案，但是 构造一个转化方案却很费时间。应用滚动数组可极大地节省空间（o（m），m为源串的长度）， 但如果需要构造一个转换方案则因缺少必要的信息而进行了重复计算损失了时间。分析附带 的滚动数组算法没有做一些常数上的优化（比如对滚动数组操作时进行mod3加法以取代 制，保存多行构造所需的数组信息等），但能说明问题的复杂度。由于数学基础不足，首先做了以下的假设：由于输入的各种处理条件的代价是随机的，并且两个串出现twiddle的情况概率基本可 以忽略，可飢略认为每个（11,m）长度的匹配来自t、一、的

2、概率相同，均为1/3。所以 可应用如下方程式求出所需代价，前两种情况为在第一行或第一列时，只有一种方法可以走。n+f（n-l，m） ，m=l; f（n，m）= j m+f（n，m-l） ，n=l;nm+（f（n,m-l ）+f（n-1，m-1 ）+f（n-l，m）/3，m1 andn>l;1对 f（n，m）f（n，m-l），玎11，111）1*（11-1，111）的证明：| f(n，m)= nm+(f(n，m-1 )+f(n-1，m-1 )+f(n-1，m)/3，n> 1 andm1(1)i f(n，m+1 )= n(m+1 )+(f(n，m)+f(n-1，m)+f(n-1，m+1

3、 )/3，n> 1 andm> 1 (2)n+f(n-l,m) ，m=l;f(n,m)=-<m+f(n，m-l) ，n=l;(2)-(1): f(n，m+1 )-f(n,m)=n+(f(n-1，m+1 )-f(n-1，m-l)+f(n，m)-f(n，m-1 )/3，n> 1 andm1 *, m ij*0+巾边界情况的公式得结论：数组的首行与首列单调递增对第二列进行分析:第二行:f(2,2)=2*2+(f( 1,1 )+f( 1,2)+f(2,1 )/3>2+f( 1,1 )=f(2,1);假设第n行成立(n>=2)，即f(n，2)f(n，l)则 f(n+l

4、，2)=(n+1 )2+(f(n+1，1 )+f(n，2)+f(n，1 )/3(n+1 )2+f(n,l )f(n+1,1) 每行的第二列值大于第一列值for i->2,nfor i->2,m)f(i，j+1)- f(i，j)=i+(f(i-1，j+1)+f(i，j)-f(i，j-1 )/3求 f（i，j+l）-f（i，jt,已求得 i-1 行单调递增，且 f（i，j）f（i，j-l）.数组每行均单调递增.同理可得 f（n，m）f（n-1，m）2. 对f（n，m）渐进时间复杂度的求解（没有加入kill操作分析）:n+f（n-1，m），m= 1;f（n,m）= - m+f（n,m-l

5、） ,n=l;nm+（f（n，m-1 ）+f（n-1，m-1 ）+f（n-1，m）/3，m1 andnl;个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个之门 j i_ j- x*jaf ji个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个 t1) f(n-l，m)>f(n-l，m-l)，(已证)f(n,m-l)>f(n-l,m-l),(己证) f(n，m)nm+f(n-1，m-1);2) f(n-l,m)/3< f(n-1 ,m-1 )/3+mn/3+mn/(3a2)+.+mii/(3an) =f(n- l,m-l )/3+mn(l-l /(3

6、an)/3/( 1-1/3)< f(n-l,m-l)/3+mii/2f(n,m-l )/3< f(n-1，m-1 )/3+mn/3+mn/(3a2)+. .+mn/(3am) =f(n-1，m-1 )/3+mn(l-l /(3am)/3/( 1-1/3)< f(n-1 ,m-1 )/3+mn/2 f（n，m）2nm+f（n-1，m-1）;对2）的一点说明：由于（n-l，m）处有1/3概率一 t走：*-方向生成f（n-l，m-l）; 方向生成 f（n-2,m-1 ）f（n-1 ,m-1）； t方向生成f（n-2，m）且f（n-2，m）向左转变的最大值 都不会超过f（n-2，m-

7、l）,因为他会向三个方向分裂，分裂时总共的1/3守 恒但n-x的x会逐渐增大，而m（n-x）逐渐减少，直到遇到n-x=l处时， 只向*-分裂，进行放缩后加上m列的花销mn/3+mn/（3a2）+.+mn/（3an） 即可得到：f(n-l ,m)/3< f(n-l，m-1 )/3+mn/3+mn/(3a2)+. .+mn/(3an) 进一步放缩得到：f(n-1 ,m)/3<(n-l,m-l )/3+mn/2 同理可得:f(n，m-1 )/3<(n-1 ,m-1 )/3+mn/2根据1)、2)可得k(nm+(n-1 )(m-1)+. .+(n-m+1) 1 +(n-m)( 1 +

8、n-m)/2),n>=m;f(n,m)=-<k(nm+(n-l )(m-1)+. +(m-n+l)l +(m-n)( 1 +m-n)/2),n<m;k(3nma2-ma3-3mn+3ma2-2iti+3n-i-3na2) ,n>=m;f(n,m)=k(3mna2-na3-3mn+3na2-2n+3m+3ma2),n<m;0(max(m,n)*min(m,n)a2) ，min(m，n)与 max(m，n)接近 f(n,m)=、0(max(m,n)a2)，min(m，n)<max(m，n)3. 对kill操作的不准确分析：作此假没：kill操作将在1-m间等概率

9、地发生 l)n=m 时mcost=k/m( (3n*ia2-ia3-3n*i-3ia2-2i+3n+3na2)/6) i=lml/m(3n*ia2-ia3-3n*i-3ia2-2i+3n+3na2)i=l=3n+3na2+(m+l )(2m+l )(n+1 )/2-(3n+2)(m+1 )/2-(m(m+1 )a2)/40(nma2)，m 与 n 接近 f(n,m)=-<0(na2),m«n2)n<m 时nmcost=k/m( (3n*ia2-ia3-3n*i-3ia2-2i+3n+3na2)/6+ (3i*na2-na3-3i*n+3na2-2n+3ii=li=n+l+

10、3 i 八 2)/6)nml/m( (3n*ia2-ia3-3n*i-3ia2-2i+3n+3na2)+ z(3 i*n 八 2-na3-3i*n+3n 八 2-2n+3ii=li=n+l+3ia2)= l/m(3na3+3na2+(n(2n+l)(n+l)a2)/2-n(3n+2)(n+l)/2-(na2)(n+l)a2)/4+(m-n)(3na2-na3 -2n)+3(n 八 2-n+1 )(m+n+1 )(m-n)/2+(m(m+l )(2m+1 )-n(n+l )(2n+1 )/2)l/m(ma3+3/2(ma2)(na2)+3mna2+5na2+l/4(na4)-5/2(na3)-mna3-2mn) 0(mna2) ，n 与 m 接近 f(n，m)=<0(m