方括号乘法 [英] Brackets multiplication
问题描述
我需要将多项式的数组系数设为标准形式,因此我需要将长括号的序列相乘:
I need to have in array coefficients of polynomial in normal form, so I need to multiply long sequence of brackets:
(x-1)(x-2)(x-3)...(x-n).
(x-1)(x-2)(x-3)...(x-n).
我该如何在最佳的时间复杂度下做到这一点?
How can I do it in best possible time complexity?
推荐答案
我怀疑算法的复杂度要好于O(n ^ 2).具有给定根[1..n]的多项式系数可以通过 Vieta定理表示,其中每个系数都是根乘积的复数和.这是相当有效的Delphi示例(改编自某些Fortran数值库).
对于n = 3,它会产生[-6、11,-6、1]个系数:
I doubt that algorithm exists with complexity better than O(n^2). Coefficients of polynom with given roots [1..n] can be expressed through Vieta's theorem, where every coefficient is complex sum of root products. This is rather effective Delphi example (adapted from some Fortran numerical library).
For n =3 it produces [-6, 11, -6, 1] coefficients:
(x-1)*(x-2)*(x-3)= x ^ 3-6 * x ^ 2 + 11 * x-6
procedure CalcPolyCoeff(const N: Integer; var Coeff: TArray<Integer>);
var
i, k: Integer;
begin
if N = 0 then
Exit;
SetLength(Coeff, N + 1);
Coeff[0] := -1;
Coeff[1] := 1;
for k := 2 to N do begin
Coeff[k] := 1;
for i := k - 2 downto 0 do
Coeff[i + 1] := Coeff[i] - k * Coeff[i + 1];
Coeff[0] := -k * Coeff[0];
end;
这篇关于方括号乘法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!