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

《对滚动数组算法的时间空间分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、dle的情况概率基本可以忽略，可飢略认为每个（11,m）长度的匹配来自t、一、的概率相同，均为1/3。所以可应用如下方程式求出所需代价，前两种情况为在第一行或第一列时，只有一种方法可以走。n+f（n-l，m），m=l;f（n，m）=jm+f（n，m-l），n=l;nm+（f（n,m-l）+f（n-1，m-1）+f（n-l，m））/3，m〉1ANDn>l;1•对f（n，m）〉f（n，m-l），玎11，111）〉1*（11-1，111）的证明：

3、f(n，m)=nm+(f(n，m-1)+f(n-1，m-1)+

4、f(n-1，m))/3，n>1ANDm〉1(1)If(n，m+1)=n(m+1)+(f(n，m)+f(n-1，m)+f(n-1，m+1))/3，n>1ANDm>1(2)n+f(n-l,m)，m=l;f(n,m)=-1ANDm〉1********************************,m^ij******************

5、*************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，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)每行的第二列值大于第一列值Fori->[2,n]Fori->[2,m)f(i，j+1)-f

6、(i，j)=i+(f(i-1，j+1)+f(i，j)-f(i，j-1))/3求f（i，j+l）-f（i，j^t,已求得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）,n=l;nm+（f（n，m-1）+f（n-1，m-1）+f（n-1，m））/3，m〉1ANDn〉l;个个个个个个个个个个个个个个个个个个

7、个个个个个个个个个个个个个个之门JI_j-^x*jAfJI个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个—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

8、)/3

9、裂，分裂时总共的1/3守恒但n-x的x会逐渐增大，而m（n-x）逐渐减少，直到遇到n-x=l处时，只向*-分裂，进行放缩后加上m列的花销mn/3+mn/（3A2）+...+mn/（3An）即可得到：f(n-l,m)/3