java - 乘以多项式/简化同类项

Question

我几乎完成了一项家庭作业，该作业要求多项式相乘并且必须简化同类项并按从高到低的顺序排列。这 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;

}

Answer 1

多项式相乘等于convolving他们的系数。不需要单独的“简化”阶段。

卷积是 O(N^2) 时间复杂度(假设两个多项式的长度都是 N)。如果 N 真的很大，可能值得考虑“快速卷积”，它通过 FFT 将卷积转换为逐元素乘法。这是 O(N log N)，尽管实际上缓存问题可能会要了你的命。