方括号乘法 [英] 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屋！