乘以多项式/简化类似的术语
我几乎完成了一项家庭作业任务,乘以多项式并且必须简化它的相似术语,并且按照从*到最低级的顺序。 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;
}
您的代码看起来像您正在使用具有交替因子和指数的列表。这可能不是您的性能问题的原因,但会使代码难以阅读 - 除了您的投射。
使用一类像
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项)。
乘以多项式相当于它们的系数convolving。不应该有任何需要单独的“简化”阶段。
卷积是O(N^2)时间复杂度(假设两个多项式长度Ñ)。如果N确实很大,则可能值得考虑“快速卷积”,其通过FFT将卷积转换为元素方式的乘法。这是O(N日志N),虽然缓存问题可能会在实践中杀死你。
你的标题说“添加”,但你的第一句话说“乘”。这是什么? – 2011-02-18 19:55:32
放入一些System.out.println(System.currentTimeMillis()),并计算出花费的时间。 – mellamokb 2011-02-18 19:57:05