1.1. Понятие сложности алгоритма. Алгоритм решения вычислительной задачи представляет собой некую детерминированную процедуру, выполняемую над набором входных данных. В качестве оценки сложности алгоритма обычно выбирается время работы алгоритма. При разных наборах данных алгоритм может иметь различное время работы. Поэтому, под сложностью алгоритма понимается максимальное время работы для всех наборов данных из некоторого фиксированного множества. Всюду ниже в качестве множества исходных данных для алгоритма будет выступать множество чисел, которые в некоторой позиционной системе счисления (чаш,е всего двоичной) имеют длину записи не превосходяш;ую некоторого числа и. Поэтому, сложность алгоритма оценивается некоторой функцией /(и).

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

Мы будем получать оценки сложности алгоритмов в виде /(и) = = O(g(u)), т.е. определять функции с точностью до константного сомножителя, пренебрегая при этом малыми членами в выражении для g( и)

Будем использовать запись /(и) д(и) ли /(и) = O(g(u)), то есть найдется константа c > шая с некоторого и выполняется неравенство /(и) сд(и). Если одновременно выполняются неравенства /(и) д(и д(и) /(и), то будем использовать запись /(и) « д(и).

1.2. Модель вычислении. Будем считать, что числа представлены в двоичной системе счисления, а под сложностью арифметической операции будем понимать число битовых операций, необходимых для ее реализации.

Данный подход удобен по следуюш,им соображениям. Во-первых, в компьютерах данные представляются и обрабатываются в двоичном виде, а другие представления в основном используются только при вводе данных и выводе результатов. Во-вторых, перевод числа N от одного основания системы счисления к другому осуш,ествляется быстро и требует выполнения O(log N) арифметических операций (деление с остатком, умножение или сложение чисел), где log N - длина N

не влияет на вид оценки сложности). А так как переход к другому основанию является редкой операцией, то затратами на ее выполнение можно пренебречь. Наконец, битовая оценка достаточно хорошо отражает реальную сложность операций, поскольку, как правило, оценки сложности для других оснований систем счисления приводят лишь к отличиям в константном множителе функции оценки сложности.

1.3. Оценки функции сложности. При оценке сложности вычислительных задач обычно применяют методы редукции и сведения к другим задачам с известными оценками сложности. Эти методы основаны на построении некоторого алгоритма решения данной задачи, который заключается в разбиении задачи на подзадачи меньшей размерности, для решения которых может использоваться как данный, так и другие известные алгоритмы. При этом для функций сложности получатся неравенства вида

/(и) < с/

Ьд(и) + dи,

где а,Ъ, сш d - некоторые положительные константы.

/(и)

мя свойствами:

(a) /(и) и

(b) к/(и) < /(ки), k> 1.

Для получения оценок функций сложности важны две леммы.

Лемма 1. Еслг1 функции /(и) и д(и) удовлетворяют свойствам (а) и (Ь) и при некоторых константах а> 1, Ъ> О и d> О выполняется неравенство

f{n)f[- +b-g{n) + d-n,

то /(и) = 0(д(и)).

Доказательство. Так как в силу свойства (Ь)

а • /

а -

f{n)-f{n)+b-g{n)+d-n.

Отсюда получаем, что

Лемма 2. Бсл« при некоторых константах а > О, c> О d > О функция f{n) удовлетворяет условию /(1) = d и f{n) = с - /() +d-n при n> 1, то она имеет вид:

O(n), а>с,

/(n)=\ O(n log n), а = с, ,O(n°ga c), а<с.

Доказательство проведем только для случая n = а*. Имеем

f{n) = d-n-Y,[-]

так как n = а*. Отсюда получаем:

= d n

а > c,

1 - с/а

/(n) = d • n • t = d • n • log тели а = с, и

(c/a)*+i-l c-d-n с* ] }{n) = d - n - ---

с/а - 1

а* с/а - 1

= 0(с*)= O(n°ga c),

если а < с □

§ 2. Сложность арифметических операций с целыми числами

2.1. Сложение и вьгаитание. Прежде всего заметим, что стандартные школьные алгоритмы сложения и вычитания чисел столбиком, очевидно, имеют оценку сложности O(log Nвде N - большее из двух чисел. Это минимальная возможная оценка сложности (напомним.

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

и M алгоритмы умножения столбиком и деления углом дают оценку O(log N log M). Поэтому для функций оценки сложности умножения n

n < /(n) < O(n2).

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

n 1/N

отбрасыванием более младших разрядов.

M(n) n

чисел, D(n щи деления с остатком 2n-paзpяднoгo числа на тое число, S(n) - сложность операции возведения в квадрат ото числа и Д(п) - сложность операции обращения n

Теорема. В предположении, что функции M(n), D(n), S(n) R(n) удовлетворяют условиям (a) и (b), справедливо утверждение:

M(n) « D(n) « S(n) « R(n).

Доказательство. В самом деле, M (n) S(n), так как в силу тождества

AB = i((A + B)2 -В2)

справедлива оценка M(n) < 3S(n) + 4n. Делению на 2 соответствует операция сдвига.

Аналогично, S(n) R(n), так как в силу равенства

N2 =

N N +1

получаем оценку S(n) 3R(n) + 2n. Здесь следует сделать следующее важное замечание. Данное равенство выполняется для точных зна-

1 /N

приближенными значениями. Поэтому для исправления возможных ошибок в младших разрядах в алгоритме необходимо предусмотреть специальные процедуры их уточнения. Включение таких процедур в целом не влияет на оценку сложности (подробнее см. в [2]).

Для доказательства оценки R(u) M(и) воспользуемся итерационным методом Ньютона для вычисления значения обратного. Он заключается в вычислении последовательности итераций х(0), x(1),... ... ,x(i),... по формуле

х(г + 1)=2x({) - Nx(i)2.

Данная последовательность действительно сходится к 1/N, так как если x{i) = {1 - 5), то

х{г + 1) = 2х(г) - Мх{г) = 1 (1 1 (1 5)2 = 1 (1 2).

Поэтому при выборе начального значения ж(0) так, что S < {а это

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

log и

знаков.

Отсюда вытекает оценка

R(u) < R

- 2M(и) + 2и.

В силу леммы 1, получаем R(u) < M(и).

Из цепочки неравенств M(и) < S(u) < R(u) < M(и) теперь вытекает эквивалентность этих трех функций.

Докажем, что R{n) -< D{n). Из равенства = следует, что D(u) M(и) + R(u) R(u). Наконец, в силу очевидной оценки R(u) D(u ю эквивалентность. □

Рассмотрим теперь вопрос об оценке сложности операции умножения.

Оценку, меньшую 0(и2), наиболее просто можно получить, применяя рекурсивный алгоритм, основанный на разбиении чисел на два слагаемых. Очень удобная версия этого алгоритма была предложена в работах Карацубы и Офмана (1962). Его суть заключается в

рекурсивном повторении следуюш,его шага. Пусть и два и-раз-рядных числа. Разобьем их на два слагаемых (для простоты считаем, что и = 2к)

A = 2kAi + Ao, B = 2k Bi + Bo.

Тогда

AB = (2k Ai + Ao)(2k Bi + Bo) = 22k AiBi + 2k (Ao Bi + AiBo) + AoBo = = (2k + 2k)AiBi + 2k(AoBi + AiBo - AoBo - AiBi) + (2k + 1)AoBo = = (22k + 2k)AiBi + 2k(Ao - Ai)(Bi - Bo) + (2k + -V)AoBo.

Topoe количество сложений, вычитаний и переносов. Поэтому для сложности данного алгоритма умножения справедлива оценка

/ (и)=3/

+ си, с> О,

откуда, по лемме 2, получаем M(и) < /(и) = O(u°g2 вде log2 3 = = 1,Ъ8Ъ...

Заметим, что этот алгоритм иначе можно интерпретировать как способ вычисления в точке x=2k значения многочлена, равного произведению двух многочленов U(x) = xAi + Ao ш V(x) = xBi + Bo. В более общем случае, подобный рекурсивный алгоритм, основанный на разбиении чисел на r слагаемых и сведении задачи умножения чисел к задачам умножения и вычисления значений многочленов, дает оценку M(и) = O(u1+°gr+i что здесь logr+1 2 О r ж.

Наиболее эффективным в настоящее время является алгоритм Шенхаге-Штрассена (1970), дающий оценку M(и) = O(u log и х X log log и) (подробнее см. [2]). Помимо разбиения чисел на слагаемые он использует технику быстрого преобразования Фурье и модульную арифметику, которые будут рассмотрены ниже.

2.3. Возведение в степень. В заключение приведем оценку сложности операции возведения в степень. Для вычисления степени Na

а ai2 = (... (ak-i2 + ak-2 )2 + ... + ai)2 + ao.