文件名称：算法流程-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:23
集训队论文集
2.1 算法简介 Berlekamp-Massey算法可以对任意域下长度为n的数列a在O(n2)次运算内无显著额外空 间的求出它的一组基Base。 2.2 算法流程 根据定义，所有最低项为xk(k ≥ n)的多项式最小次数都恰好是它的次数，因此对于Basek(x)我 们只要选任何一个Cxk(C , 0)即可，我们不妨假设求出的每一个多项式的最低项均为1，那 么这里我们把C设为1即可。 假设我们已经求出了Basek+1(x)到Basen(x)的多项式中最小次数的一个。 考虑如何求Basek(x)。 我们考虑xBasek(x)，根据1.3，我们只要使得它的线性表示中，最小次数最大的一个多 项式的最小次数尽量小即可。 首先，由于xBasek(x)的最低项为xk+1，于是表示中一定有Basek+1(x)这一项。 考虑剩下的项，显然它们当中最大的最小次数会尽量小。 设res(x) = xBasek(x) − Basek+1(x)。我们求出pro(x) = res(x) × A(x)，根据引理1.1易 知pro(x)的k + 1到n − 1次项均为零。 考虑n次项，如果它为零，那么我们已经知道xBasek(x)，否则假设它为u。 考虑Basel(x)(l > k + 1)，如果Basel(x) × A(x)的n次项不为零，那么假设n次项为v，易 知res(x) − uv−1Basel(x)的k + 1次项到n次项均为零，由于最大的最小次数会尽量小，于是 如果存在满足条件的多项式，那么Basel(x)一定是所有满足条件的多项式中最小次数最小 的，取这样的Pl(x)，我们便可以求出xBasek(x)。假如这样的Basel(x)不存在，那么只可能 是xBasek(x)的最小次数超过了n，这样的话我们只需要任选一个最低项为xk+1次项且系数 为1的多项式即可。 知道了xBasek(x)，我们显然也就知道了Basek(x)。 利用这个方法，每一个Pk(x)均可在不超过O(n)次运算内求出，因此总运算次数为O(n)， 而需要运算的Base只有O(n)个。于是总运算次数为O(n2)。 显然这个算法除了需要存储A(x)和Base外不需要显著的额外空间。 4