乘以多項式/簡化類似的術語

我幾乎完成了一項家庭作業任務，乘以多項式並且必須簡化它的相似術語，並且按照從最高級到最低級的順序。 2條語句也已經排序。我的程序完美運行，但得到結果需要很長時間（比如在我的機器上運行2分鐘），而我用來提交它的網站顯示超出了時間限制。對於實際的乘法（這裏沒有顯示），它需要很少的時間，但類似術語的組合需要一段時間。它發生在1個鏈表具有2條語句相結合，即：乘以多項式/簡化類似的術語

2 2 2 1 1 1 //means 2x^2 + 2x + x 
* 
3 2 5 1 1 0 //means 3x^2 + 5x + 1

，我把它變成2 2 2 1 1 1 3 2 5 1 1 0進行處理。

任何人都知道我怎麼能加快這一點？謝謝。

public MyLinkedList add(MyLinkedList combinedList) { 
    MyLinkedList tempCombinedList = new MyLinkedList(); 
    MyLinkedList resultList = new MyLinkedList(); 
    //check highest power now that its sorted. 
    tempCombinedList=null; 
    tempCombinedList = new MyLinkedList(); 
    int highestPower=0; 

    //we need to find highest power 
    for(int l=2;l<=combinedList.size();l=l+2) { 
     if((Integer)combinedList.get(l)>highestPower) { 
      highestPower=(Integer)combinedList.get(l); 
      System.out.println("highest power is "+highestPower); 
     } 
    } 

    int tempAddition=0;  
    while(highestPower!=-1) { 
     for(int z=2;z<=combinedList.size();z=z+2) { 
      if((Integer)combinedList.get(z)==highestPower) { 
       tempAddition=tempAddition+(Integer)combinedList.get(z-1); 
      } 
     } 
     if((tempAddition!=0)) { //we arent allowed to have a 0 coefficient in there.... 
      resultList.add(tempAddition); 
      resultList.add(highestPower); 
     } 
     else if(((tempAddition==0)&&(highestPower==0))) { //unless the exponent is 0 too 
      resultList.add(tempAddition); 
      resultList.add(highestPower); 
     } 
     tempAddition=0; //clear the variable for the next roud 
     highestPower--; //go down in power and check again. 
     } 
return resultList; 

}

來源

2011-02-18 jfisk

你的標題說「添加」，但你的第一句話說「乘」。這是什麼？ – 2011-02-18 19:55:32

放入一些System.out.println（System.currentTimeMillis（）），並計算出花費的時間。 – mellamokb 2011-02-18 19:57:05

您的代碼看起來像您正在使用具有交替因子和指數的列表。這可能不是您的性能問題的原因，但會使代碼難以閱讀 - 除了您的投射。

使用一類像

class Monomial implements Comparable<Monom> { 
    private int exponent; 
    private int factor; 

    // TODO: get methods, constructor 

    public int compareTo(Monomial other) { 
     return this.exponent - other.exponent; 
    } 

    public Monomial times(Monomial other) { 
     // here your multiplication code 
    } 


}

，然後你可以有一個List<Monomial>，而不是你的整數列表。首先，這使得你的代碼更具可讀性，其次，你現在可以（在乘法之後）簡單地對你的列表進行排序，所以你以後不必一次又一次地瀏覽整個列表。

然後，因爲您始終使用.get(i)訪問您的列表，請不要使用鏈接列表，請使用ArrayList（或類似結構）。（對於一個鏈表，你爲每個訪問必須遍歷列表來獲取你想要的元素，而不是數組列表。）或者，使用Iterator（或增強for循環）而不是索引訪問。

其實，如果你排序（並簡化）乘以之前的因素，你已經可以乘他們在正確的順序，所以你真的沒有事後簡化。作爲一個例子，它是

(2x^2 + 3x + 0) * (3x^2 + 5x + 1) 
= (2*2) * x^4 + 
    (2*5 + 3*3) * x^3 + 
    (2*1 + 3*5 + 0*3) * x^2 + 
    (3*1 + 0*5) * x^1 + 
    (0*1) * x^0 
= 4 * x^4 + 19 * x^3 + 17 * x^2 + 3 * x

（你獲得的方案：在每一行從所述第一多項式的因素向下排序，從所述第二多項式向上的那些）。

（如果你願意的話，你可以在開頭已經放棄了0項）。

來源

2011-02-18 20:44:34

乘以多項式相當於它們的係數convolving。不應該有任何需要單獨的「簡化」階段。

卷積是O（N^2）時間複雜度（假設兩個多項式長度Ñ）。如果N確實很大，則可能值得考慮「快速卷積」，其通過FFT將卷積轉換爲元素方式的乘法。這是O（N日誌N），雖然緩存問題可能會在實踐中殺死你。

來源

2011-02-18 20:05:51

乘以多項式/簡化類似的術語

回答

相關問題