Есть ли более эффективный способ умножения полиномов?

Question

Вот мой метод умножения двух полиномов вида 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);
}

Answer 1

Вот как я мог бы реализовать эту функцию

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]

Answer 2

Возможно, что делает этот алгоритм медленным, так это создание n^2 объектов TermImp. В C++ это не должно быть проблемой, потому что вы создадите объект в стеке и передадите по значению. Насколько я понимаю, в Java у вас нет этой опции: вы должны принять накладные расходы на создание объекта, а затем перейти по ссылке.

Кажется неэффективным, что вы создаете новый объект каждый раз, когда умножаете термин. Не могли бы вы просто устранить это?

Вы могли бы рассмотреть возможность изменения метода addTerm для принятия коэффициента и показателя степени в качестве аргументов double/int.

Алгоритм все равно будет O(n^2) для больших n, но он все равно должен значительно ускориться.

Другой вещью, которую вы могли бы рассмотреть, было бы использование цикла for, а не итераторов, потому что итераторы также включают создание новых объектов... хотя O(n) не так критично.

Answer 3

У вас есть одна серьезная неэффективность: вы храните термины в неупорядоченном списке. Вы должны изменить свой код так, чтобы в term.get(n) возвращался термин с x^n. Тогда вам не нужно будет искать переменную термина в вашем методе addTerm.

Для этого вам нужно будет обновить весь код, который изменяет термины, чтобы поддерживать порядок в порядке.

Сам метод умножения выглядит эффективным, я не думаю, что его можно оптимизировать намного больше.