搜索
对滚动数组求解转换方案进行的分析经过观察发现，该动态规划方程只需要保存数组的三行即可求出最小费用的答案，但是构造一个转化方案却很费时间。应用滚动数组可极大地节省空间（O(m),m为源串的长度），但如果需要构造一个转换方案则因缺少必要的信息而进行了重复计算损失了时间。分析附带的滚动数组算法没有做一些常数上的优化（比如对滚动数组操作时进行mod3加法以取代复制，保存多行构造所需的数组信息等），但能说明问题的复杂度。由于数学基础不足，首先做了以下的假设：由于输入的各种处理条件的代价是随机的，并且两个串出现twiddle的情况概率基本可以忽略，可粗略认为每个（n,m）长度的匹配来自↑、←、↖的概率相同，均为1/3。所以可应用如下方程式求出所需代价，前两种情况为在第一行或第一列时，只有一种方法可以走。n+f(n-1,m),m=1;f(n,m)=m+f(n,m-1),n=1;nm+(f(n,m-1)+f(n-1,m-1)+f(n-1,m))/3,m1ANDn1;1.对f(n,m)f(n,m-1)，f(n,m)f(n-1,m)的证明：f(n,m)=nm+(f(n,m-1)+f(n-1,m-1)+f(n-1,m))/3,n1ANDm1(1)f(n,m+1)=n(m+1)+(f(n,m)+f(n-1,m)+f(n-1,m+1))/3,n1ANDm1(2)n+f(n-1,m),m=1;f(n,m)=m+f(n,m-1),n=1;(2)-(1):f(n,m+1)-f(n,m)=n+(f(n-1,m+1)-f(n-1,m-1)+f(n,m)-f(n,m-1))/3,n1ANDm1********************************数组共n行，m列*******************************0+++++++++++++由边界情况的公式得结论：数组的首行与首列单调递增对第二列进行分析：第二行：f(2,2)=2*2+(f(1,1)+f(1,2)+f(2,1))/32+f(1,1)=f(2,1);假设第n行成立（n=2）,即f(n,2)f(n,1)则f(n+1,2)=(n+1)2+(f(n+1,1)+f(n,2)+f(n,1))/3(n+1)2+f(n,1)f(n+1,1)∴每行的第二列值大于第一列值Fori-[2,n]Fori-[2,m)f(i,j+1)-f(i,j)=i+(f(i-1,j+1)-f(i-1,j-1)+f(i,j)-f(i,j-1))/3求f(i,j+1)-f(i,j)时，已求得i-1行单调递增，且f(i,j)f(i,j-1)∴f(i,j+1)-f(i,j)0∴数组每行均单调递增∴f(n,m)f(n,m-1)∴同理可得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-1),n=1;nm+(f(n,m-1)+f(n-1,m-1)+f(n-1,m))/3,m1ANDn1;********************************数组共n行，m列*******************************←↖↑1）f(n-1,m)f(n-1,m-1)，（已证）f(n,m-1)f(n-1,m-1)，（已证）∴f(n,m)nm+f(n-1,m-1);2）f(n-1,m)/3f(n-1,m-1)/3+mn/3+mn/(3^2)+…+mn/(3^n)=f(n-1,m-1)/3+mn((1-1/(3^n))/3/(1-1/3))f(n-1,m-1)/3+mn/2f(n,m-1)/3f(n-1,m-1)/3+mn/3+mn/(3^2)+…+mn/(3^m)=f(n-1,m-1)/3+mn((1-1/(3^m))/3/(1-1/3))f(n-1,m-1)/3+mn/2∴f(n,m)2nm+f(n-1,m-1);对2）的一点说明：由于(n-1,m)处有1/3概率←↖↑走：←方向生成f(n-1,m-1)；↖方向生成f(n-2,m-1)f(n-1,m-1)；↑方向生成f(n-2,m)且f(n-2,m)向左转变的最大值都不会超过f(n-2,m-1)，因为他会向三个方向分裂，分裂时总共的1/3守恒但n-x的x会逐渐增大，而m(n-x)逐渐减少，直到遇到n-x=1处时，只向←分裂，进行放缩后加上m列的花销mn/3+mn/(3^2)+…+mn/(3^n)即可得到：f(n-1,m)/3f(n-1,m-1)/3+mn/3+mn/(3^2)+…+mn/(3^n)进一步放缩得到：f(n-1,m)/3(n-1,m-1)/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+n-m)/2),n=m;f(n,m)=k(nm+(n-1)(m-1)+…+(m-n+1)1+(m-n)(1+m-n)/2),nm;k(3nm^2-m^3-3mn+3m^2-2m+3n+3n^2),n=m;f(n,m)=k(3mn^2-n^3-3mn+3n^2-2n+3m+3m^2),nm;Θ(max(m,n)*min(m,n)^2),min(m,n)与max(m,n)接近∴f(n,m)=Θ(max(m,n)^2),min(m,n)max(m,n)3.对KILL操作的不准确分析：作此假设：KILL操作将在1-m间等概率地发生1)n=m时mCost=k/m(∑(3n*i^2-i^3-3n*i-3i^2-2i+3n+3n^2)/6)i=1m1/m∑(3n*i^2-i^3-3n*i-3i^2-2i+3n+3n^2)i=1=3n+3n^2+(m+1)(2m+1)(n+1)/2-(3n+2)(m+1)/2-(m(m+1)^2)/4Θ(nm^2),m与n接近∴f(n,m)=Θ(n^2),mn2)nm时nmCost=k/m(∑(3n*i^2-i^3-3n*i-3i^2-2i+3n+3n^2)/6+∑(3i*n^2-n^3-3i*n+3n^2-2n+3ii=1i=n+1+3i^2)/6)nm1/m(∑(3n*i^2-i^3-3n*i-3i^2-2i+3n+3n^2)+∑(3i*n^2-n^3-3i*n+3n^2-2n+3ii=1i=n+1+3i^2))=1/m(3n^3+3n^2+(n(2n+1)(n+1)^2)/2-n(3n+2)(n+1)/2-((n^2)(n+1)^2)/4+(m-n)(3n^2-n^3-2n)+3(n^2-n+1)(m+n+1)(m-n)/2+(m(m+1)(2m+1)-n(n+1)(2n+1))/2)≈1/m(m^3+3/2(m^2)(n^2)+3mn^2+5n^2+1/4(n^4)-5/2(n^3)-mn^3-2mn)Θ(mn^2),n与m接近∴f(n,m)=Θ(m^2),nm∴综上所述，源字符串长度为m-1，目标串长度为n-1的随即情况下，滚动数组算法所需的时间复杂度为Θ(max(m,n)*min(m,n)^2),min(m,n)与max(m,n)接近f(n,m)=Θ(max(m,n)^2),min(m,n)max(m,n)空间复杂度为O(m)