是否存在乘法多項式的更有效方法？

這裏是我的方法乘以an*x^n + an-1*x^n-1 + ... + a1*x + a0形式的兩個多項式。每個Term對象有兩個字段：double coefficient和int power。 Polynomial通過將術語存儲在ArrayList<Term>中來表示多項式。這個乘法的當前實現是O（n^2）。任何想法或提示如何使其更快？是否存在乘法多項式的更有效方法？

public Polynomial multiply(Polynomial P2) { 
    PolynomialImp result = new PolynomialImp(); 
    for (Term currentThisTerm : this.terms) 
    { 
     for (Term currentP2Term : ((PolynomialImp) P2).terms) 
     { 
      result.addTerm(new TermImp(currentThisTerm.getCoefficient()*currentP2Term.getCoefficient(), currentThisTerm.getExponent() + currentP2Term.getExponent())); 
     } 
    } 
    //Sort polynomial in decreasing exponent order 
    return result.sort(); 
}

下面是如果需要的話addTerm方法：

private void addTerm(Term nextTerm) 
{ 
    for (int i = 0; i < this.terms.size(); i++) 
    { 
     if (this.terms.get(i).getExponent() == nextTerm.getExponent()) 
     { 
      //Add the coefficients if the current term has the same exponent as a term that is already in the polynomial. 
      //This preserves the sorting of the polynomial except during multiply. 
      this.terms.set(i, new TermImp(this.terms.get(i).getCoefficient() + nextTerm.getCoefficient(), this.terms.get(i).getExponent())); 
      return; 
     } 
    } 
    //Avoid adding zeros to the polynomial. 
    if (nextTerm.getCoefficient() != 0) 
     this.terms.add(nextTerm); 
}

來源

2012-10-04 crzrcn

我會使用'double []'數組與每個權力的係數。這仍然是O（n^2）來執行乘法。你確定你需要它更快？ –

我不需要它更快，但我想我可能會嘗試學習和咯咯。 – crzrcn

多項式乘法是O（n^2），除非您使用FFT – gtgaxiola

你有一個重大的低效：您存放在什麼似乎是一個無序列表中的詞語。你應該修改你的代碼，以便terms.get（n）返回x^n這個詞。然後，您不需要在addTerm方法中搜索術語變量。

要做到這一點，您必須更新修改條款的所有代碼以保持條款的有序性。

乘法本身看起來很有效率，我不認爲它可以進行更多的優化。

來源

2012-10-04 16:33:49

這是怎麼了，我可能實現此功能的

public class Polynomial { 
    private final double[] coeff; 

    public Polynomial(double... coeff) { 
     this.coeff = coeff; 
    } 

    @Override 
    public String toString() { 
     return Arrays.toString(coeff); 
    } 

    public Polynomial multiply(Polynomial polynomial) { 
     int totalLength = coeff.length + polynomial.coeff.length - 1; 
     double[] result = new double[totalLength]; 
     for (int i = 0; i < coeff.length; i++) 
      for (int j = 0; j < polynomial.coeff.length; j++) { 
       result[i + j] += coeff[i] * polynomial.coeff[j]; 
      } 
     return new Polynomial(result); 
    } 

    public static void main(String... args) { 
     Polynomial p1 = new Polynomial(1, 2, 3); 
     System.out.println(p1 + "^2 =" + p1.multiply(p1)); 
     Polynomial p2 = new Polynomial(3, -1, -1); 
     System.out.println(p1 + "*" + p2 + "=" + p1.multiply(p2)); 
    } 
}

打印

[1.0, 2.0, 3.0]^2 =[1.0, 4.0, 10.0, 12.0, 9.0] 
[1.0, 2.0, 3.0]*[3.0, -1.0, -1.0]=[3.0, 5.0, 6.0, -5.0, -3.0]

來源

2012-10-04 16:39:16

我知道這是答案發布後很長一段時間，但我可以證實，這就像一個魅力！ – intboolstring

也許，什麼使這個算法慢創造N^2個TermImp對象。在C++中，這不應該成爲問題，因爲您可以在堆棧上創建對象並按值傳遞。我的理解是，在Java中，你沒有這個選項：你必須接受創建一個對象的開銷，然後通過引用傳遞。

您每次增加一個詞時都會創建一個新對象，這似乎效率低下。你難道不能消除它嗎？

你可以考慮改變addTerm方法來接受一個係數和一個指數作爲double/int參數。

該算法對於大n仍然是O（n^2），但它仍然應該加速很多。

你可以考慮的另一件事是使用for循環而不是迭代器，因爲迭代器還涉及到創建新對象......雖然O（n）並不那麼重要。

來源

2012-10-04 16:48:29 Dughall

是否存在乘法多項式的更有效方法？

回答

相關問題