12. НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ

При разработке алгоритма для решения данной задачи основной вопрос, ответ на который нам хотелось бы знать, — это "Какова ее подлинная вычислительная сложность?". Зная теоретическую нижнюю границу для эффективности алгоритма, можно лучше оценить имеющиеся алгоритмы и определить, сколь много усилий следует тратить на поиск лучшего решения. Например, если известно, что задача трудно разрешима, можно довольствоваться эвристическими способами нахождения приближенных решений.

К сожалению, выяснить подлинную вычислительную сложность данной задачи обычно очень трудно. Для большинства практических задач, чтобы судить о качестве алгоритма, приходится полагаться на опыт. Однако иногда можно довольно точно оценить снизу число арифметических операций, требуемых для выполнения вычислений. В этой главе мы изложим некоторые важные результаты этого рода. Например, покажем, что умножение -матрицы на р-вектор требует пр умножений, а вычисление значения полинома степени требует умножений. Много дополнительных результатов о нижних оценках содержится в упражнениях. Читателю, интересующемуся нижними оценками, советуем рассматривать эти упражнения как неотъемлемую часть данной главы.

12.1. ПОЛЯ

Чтобы получить точные нижние границы, надо определить, какие операции считать основными. Для определенности будем предполагать, что все вычисления ведутся в некотором поле, таком, как поле вещественных чисел, где основные операции — сложение и умножение элементов поля.

Определение. Полем называется такая алгебраическая система что

1) она — кольцо с единицей 1 относительно умножения,

2) умножение коммутативно,

3) каждый элемент а из обладает обратным относительно умножения,

Пример 12.1. Вещественные числа с обычными операциями сложения и умножения образуют поле. Целые числа образуют кольцо, но не поле, поскольку целые числа, отличные от ±1, не имеют обратных, являющихся целыми числами. Но для простого числа целые числа по модулю образуют (конечное) поле.

Рассмотрим задачу вычисления произвольного полинома в некоторой точке Мы хотим найти алгоритм, который по значениям в качестве входов строит соответствующее значение в качестве выхода. Этот алгоритм должен работать на всех возможных значениях своих входов, принадлежащих некоторому полю. Максимальное число сложений, вычитаний и умножений, выполняемых алгоритмом, где максимум берется по всем допустимым входам, называется арифметической сложностью этого алгоритма.

Заметим, что одни полиномы степени вычислить оказывается проще, чем другие. Например, на вычисление тратится порядка операций, тогда как интуитивно мы чувствуем, что на вычисление "произвольного" полинома степени должно расходоваться линейное число операций. Поэтому алгоритм для вычисления значений, пригодный только для конкретного полинома, может работать много быстрее, чем алгоритм, применимый ко всем полиномам. Чтобы сформулировать понятие алгоритма, пригодного для целого класса задач, введем для представления входных переменных формальные переменные.

Определение. Формальной переменной над алгебраической системой называется символ, не принадлежащий множеству элементов этой системы. Пусть ) — поле и формальные переменные над Расширением поля этими переменными называется такое наименьшее коммутативное а) кольцо ), что В содержит

Заметим, что эти формальные переменные не связаны никакими тождествами. Всякий полином с коэффициентами из и "неизвестными" представляет некоторый элемент из Два полинома обозначают один и тот же элемент из если один из них можно превратить в другой с помощью аксиом коммутативного кольца. Единица в будет также единицей в

Пример 12.2. Пусть поле вещественных чисел. Тогда кольцо включает в себя х, у и все вещественные числа. Так как оно замкнуто относительно сложения, то принадлежат Так как оно замкнуто относительно умножения, то оно содержит элемент эквивалентный в силу закона дистрибутивности для кольца.