Классические алгоритмы полиномиальной арифметики и их сложность.

Границы времени вычислений для операций над полиномами обычно даются в виде функций от степеней и длин норм полиномов.

Определение 1.2.6. Пусть — полиномиальное уравнение от одной переменной с целыми коэффициентами. (Если коэффициенты являются рациональными числами, то мы прежде всего превратим их в целые, домножив каждый из них на наименьшее общее кратное знаменателей.) Максимальная норма (или норма с нижним индексом ) полинома — это суммарная норма (или норма с нижним индексом 1) — это и евклидова норма — это Нетрадиционно при временном анализе алгоритмов, имеющих на входе полиномы, используются только две первые нормы, в то время как евклидова норма используется в доказательстве теорем общего вида. Из определения следует, что , где — степень полинома поэтому

Пусть Два полинома с целыми коэффициентами степеней тип соответственно. Мы хотим получить ограничения в виде функций степеней шипи длин времен, требуемых для вычисления обладающих свойством делимости где степень полинома (предполагая, конечно, что ).

Давайте вычислим, пользуясь описанным выше представлением полиномов, функцию времени вычислений для программы PSUM, выполняющей сложение полиномов (polynomial summation); эта программа берет в качестве входа полиномы и возвращает их сумму в виде нового списка, [Более точно, — это длина нового списка, представляющего ] Прежде всего мы видим, что должно быть выполнено не более сложений коэффициентов. Затем напомним, что для любых двух длинных целых чисел имеем . В нашем случае в худшей возможной ситуации коэффициенты полинома все будут равны [максимальному коэффициенту полинома в то время как коэффициенты полинома все будут равны [максимальному коэффициенту полинома таким образом, одно сложение коэффициентов выполняется за время . Поскольку имеется не более сложений коэффициентов, легко видеть, что функция времени вычислений этой программы равна

В качестве упражнения читателю мы оставляем доказательство того, что время, необходимое для вычисления произведения равно

Более того, если — делитель, — частное, то последнее выражение ограничивает время, необходимое для выполнения обычного алгоритма деления полиномов с целыми коэффициентами. (Алгоритмы полиномиального деления будут представлены в следующих главах.)