乘以多项式/简化类似的术语

我几乎完成了一项家庭作业任务，乘以多项式并且必须简化它的相似术语，并且按照从最高级到最低级的顺序。 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

乘以多项式/简化类似的术语

回答

相关问题