Архив WinRAR / Книги, блеать / Абрамов С.А. Вычислительная сложность алгоритмов (конспект лекций)

m = max{ma , mb }. Рассмотрим случай, когда ma = mb = m , тогда b > 2m−1 и общее число

битовых операций допускает оценку Ω(2m m). ab < 22m и, следовательно, результат каждого сложения имеет не превосходящую 2m битовую длину, а значит число битовых операций на каждом шаге ≤ c 2m . Поскольку число шагов < 2m , мы можем написать оценку O(2m m) . В итоге поучаем оценку TNM* (m) = Θ(2m m).

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

			T **	(m , m ) = Θ(max{m , m			}).
			Add	a b	a	b
Заметим, что это не просто переписывание оценки						через m.		Покажем, откуда следует
T **	(m , m ) = Ω(max{m , m })		. Доказательство		оценки		Ω	заключается в описание
Add	a b	a b
«неудобных» данных для алгоритма:
				m
				647a 48
			a =11...1011...1		b =10...01
				123		123
				mb		mb

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

Для алгоритма «сверхнаивного» умножения из примера допустимы следующие оценки сложности: Ω(2mb ma ) и O(2mb (ma + mb )), но в то же время, оценка Θ(2max{ma ,mb } max{ma , mb }) будет неверна.

Для алгоритма «наивного» умножения (NM) (обычное умножение столбиком) справедливы следующие оценки сложности: TNM* (m) = Θ(m2 ), TNM** (ma , mb ) = Θ(mamb ) . Они легко следуют из определения: требуется суммировать mb чисел n1, ... , nmb , где ni либо 0, либо a 2i−1 .

Обозначим si = n1 +... + ni , i =1, ... , mb . Несложно индукцией показывается, что ν(si )≤ ma + i . Прибавляем ni+1 ≠ 0 . Последние i цифр этого числа равны нулю — мы их игнорируем: si+1 = si + ni+1 .

Число битовых операций для преобразования si в si+1 не превосходит c(ma +1) . Если все цифры числа b равны 1, то число битовых операций для вычисления произведения не

меньше, чем m m . Откуда получаем оценку для сложности: T **

(m , m ) = Θ(m m ).

a b

NM

a

b

a b

Если будем

рассматривать

m = max{ma , mb } как

размер

входа, то затраты не превзойдут

c(m +1)m ,

откуда

следует оценка

для

сложности O(m2 ) .

Оценку

снизу выведем

из

T**

(m

, m )

, рассмотрев случай m = m = m затраты будут не меньше, чем m m = m2 .

NM

a

b

a

b

a b

Откуда получаем TNM* (m) = Θ(m2 ).

Для

пространственной

сложности

будут

верны

оценки:

SNM* (m) = 2m + O(1)

,

S**

(m

, m )

= m + m + O(1) .

NM

a

b

a

b

Иногда удобно иметь оценки сложности, выраженные в самих a и b. Возникает вопрос: можно ли в вышеприведённых рассуждениях заменить mamb на log a logb ? Для перехода в

оценках сверху от ν(c) к log2 c удобно такое неравенство: log2 (c +1) < 2log2 c , c ≥ 2 . Тем самым неравенства ma ≤ 2log2 a , mb ≤ 2log2 b дают нам возможность написать следующую оценку:

31

CNMT (a, b) ≤TNM** (ma , mb ) ≤ cmamb ≤ 4clog2 a log2 b CNMT (a, b) = O(log a logb)

Функция затрат в этом случае будет соответствовать сложности (т.к. размер входа — a и b). Тем самым доказано, что TNM** (a, b) = O(log a logb) . Можно ли то же самое проделать для

установления оценки Θ ? Ответ: нет, т.к. уже для a = 2k1 , b = 2k2 оценка будет линейной. Рассмотрим задачу вычисления n! следующим образом: 2 3 ; (2 3) 4 ; … ; (2 ... (n −1)) n . Докажем, что затраты допускают оценку O((nlog n)2 ).

Очевидно, что затраты не превосходят c f (n) , где f (n) = log2 2log2 3 + log2 (2 3)log2 4 +... + + log2 (2 3 ... (n −1))log2 n < log2 (2 3 ... (n −1))[log2 3 + log2 4 +... + log2 n]< log2 n!log2 n!.

Откуда следует оценка для сложности O(log2 n!), что эквивалентно, согласно формуле Стирлинга, O((nlog n)2 ).

Пример. Пусть имеются числа a1, ... , an > 0 , которые перемножаются наивным способом:

a1a2 , (a1a2 )a3 , … , (a1 ... an−1)an . Обозначим суммарную битовую длину через

n

M = ∑ν(ai ) . Докажем, что битовая сложность такого алгоритма допускает оценку

i=1

O(M 2 ).

Проведём доказательство, предполагая, что ai ≠1 (если есть единицы, то оценка тем более верна). Очевидно, что затраты алгоритма не превзойдут c F(a1, ... , an ) , где

F(a1, ... , an ) = log2 a1 log2 a2 + log2 (a1a2 )log2 a3 +... + log2 (a1 ... an−1 )log2 an ≤

≤ log2 (a1a2...an−1 )[log2 a2 +... + log2 an ]≤ (log2 a1 + log2 a2 +... + log2 an )2 ≤ {log2 ai ≤ν(ai )}≤ ≤ (ν(a1) +ν(a2 ) +... +ν(an ))2 = M 2 .

Деление с остатком.

Пусть даны два числа a ≥ b >1 . Покажем, что для алгоритма «наивного» деления (ND) (деление столбиком) имеют место следующие оценки:

TND* (m) = Θ(m2 ), TND** (ma , mb ) = Θ((ma − mb +1)mb ).

На каждое вычитание уходит c(mb +1) , количество вычитаний не превосходит (ma − mb +1),

откуда получаем T**	(m , m ) = O((m − m +1)m ) (единицей пренебречь нельзя, т.к. вполне
ND	a	b	a	b	b
возможно, что ma = mb , и выражение под знаком O превратится в нуль).
Что касается нижней оценки, то можно					рассмотреть числа a = 2ma −1 и b = 2mb −1 , для
которых алгоритму потребуется (ma − mb +1)mb операций, что доказывает оценку снизу. Это
даёт возможность написать оценку через Θ .
Что касается оценки TND*		(m) = O(m2 ), то она следует из того, что m2 ≥ mamb ≥ (ma − mb +1)mb .
Для доказательства	нижней		оценки,	рассмотрим a = 2m −1 и b = 2 m2 , которые являются

самыми неудобными для алгоритма. Это позволяет написать нижнюю оценку, что завершает доказательство оценки TND* (m) = Θ(m2 ).

Когда a и b рассматриваются в качестве размера входа, то битовая сложность допускает оценку O((log a − logb + a)logb) O(log a logb). Если брать только a, то O(log2 a).

32

Пример. Пусть на входе имеется n и k ≥ 2 . Требуется перевести n из двоичной системы счисления к системе с основанием k. Покажем, что битовая сложность такого алгоритма допускает оценку O(log2 n).

n в k-ичной записи формируется из остатков от деления чисел q0 , ... , qt , t = logk n +1

на k, где q0 = n , qi = qki−1 , i =1, ... , t . Все qi ≤ n , и общие затраты на всех шагах

допускают оценку O(log nlog klogk n) , log2 k logk n = log2 n O(log2		n).
14243123
затратына	число
одномшаге	шагов (t)

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

Исследуем алгоритм Евклида на битовую сложность. На входе два числа: a0 ≥ a1 > 0 . Ранее было сказано, что величина a0 не сильно влияет на алгебраическую сложность, т.к. после первого же деления с остатком получим число, меньшее a1 . Но в случае битовой сложности это не так. Если в качестве размера входа взять a1 , то сложность будет бесконечной. Чтобы получить информативную оценку битов можно в качестве размера входа взять a0 или m =ν(a0 ) . Возьмём m , тогда можно показать, что для битовой сложности алгоритма

Евклида имеет место оценка O(m2 ). Доказательство этого факта не очень сложное: очевидно, что затраты алгоритма не превзойдут величины

n

c ∑(ν(ai−1 )−ν(ai )+1)ν(ai ).

i=1

Здесь под знаком суммы написана битовая сложность деления ai−1 на ai , причём число шагов алгоритма Евклида равно n. Функция ν(ai ) с ростом i убывает, поэтому мы можем написать следующую оценку:

n	n
c ∑(ν(ai−1 )−ν(ai )+1)ν(ai )≤ cnν(a0 )+ cν(a0 )∑(ν(ai−1 )−ν(ai ))
	{
i=1	≥ν (a ) i=1
	1

дальше эта сумма вычисляется легко:

cnν(a0 )+ cν(a0 )(ν(a0 )−ν(an ))≤ cν(a0 )(n +ν(a0 )).

Всё хорошо, но в оценку влезло n. Но n — это число шагов алгоритма Евклида и, как было получено ранее, является величиной логарифмической: n ≤ 2log2 a1 +1 n ≤ 2log2 a0 +1 ,

откуда следует заявленная оценка O(m2 ).

Т.к. эта оценка является верхней, то можно перейти к оценке через a0 : O(log2 a0 ). Эта оценка

получена на базе алгоритма «наивного» деления и возникает вопрос: если использовать более эффективный алгоритм деления, можно ли уменьшить оценку? Оказывается, что это не так, и оценка точная. Для доказательства достаточно положить a0 = Fn ; a1 = Fn−1 , и

затраты алгоритма будут примерно равны log22 a0 , т.к. для чисел Фибоначчи каким бы не был алгоритм деления, он будет эквивалентен вычитанию.

Более того, можно доказать теорему о нижней границе класса алгоритмов Евклида (отличающихся алгоритмом деления) и показать, что она равна log22 a0 .

33

Модулярная арифметика.

Все вычисления производятся по модулю некоторого числа.

Определение. Число a сравнимо с b по модулю k, если число k делит разность (a −b).

Обозначение: a ≡ b(mod k).

Утверждение.

(i)Отношение сравнимости по модулю k является отношением эквивалентности.

(ii)Если a1 ≡ b1(mod k), a2 ≡ b2 (mod k), то

a1 + a2 ≡ b1 + b2 (mod k ), a1 − a2 ≡ b1 −b2 (mod k ), a1a2 ≡ b1b2 (mod k).

(iii)Каждое число a сравнимо по модулю k с одним и только одним числом из множества {0, 1, ... , k −1}.

Отношение эквивалентности разбивает множество целых чисел на непересекающиеся классы, причём количество этих классов равно k. Возьмём по одному представителю из каждого класса: {a0 , a1, ... , ak −1} — полная система вычетов по модулю k. Система

	I = {0, 1, ... , k −1}		k		k
		— каноническая система вычетов. S = −		, ... , −1, 0, 1, ... ,				—
			2			2

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

кольцом вычетов по модулю k. При этом вычеты называются изображениями. При сложении складываем изображения, если остаёмся в рамках канонической системы, то всё в порядке, если получаем число ≥ k , то вычитаем k. Противоположный a элемент определяется как k − a . Поэтому для битовых затрат операций сложения и вычитания имеем оценку O(m) ,

где m =ν(k) .

Если для умножения используем алгоритм «наивное» умножения, то затраты допускают оценку O(m2 ).

Если k — простое, то Zk является полем, если k не является простым, то Zk — это кольцо с делителями нуля.

Сосредоточимся на случае k = p — простое число. Покажем, откуда следует существование обратного элемента. Рассмотрим каноническую систему вычетов: {0, 1, ... , p −1} . Из

расширенного алгоритма Евклида следует, что найдутся такие целые s и t, что будет верно sp + ta =1 ta ≡1(mod p) . Следовательно, t будет обратным к a. Но t является целым и,

возможно, не входит в систему. Было показано, что t < p , и t может быть отрицательным.

Поэтому, если t ≥ 0 , то всё в порядке и t входит в рассматриваемую систему вычетов. Если t < 0 , то прибавим p и попадём в рамки системы (ещё не более одной операции). Затраты на каждом шаге расширенного алгоритма Евклида для перехода от si−1 к si и от ti−1 к ti

сравнимы с затратами на деление с остатком. Но расширенный алгоритм Евклида позволяет вычислять только t и не тратить операции на вычисление s. Но для O(log2 p)это не имеет значения.

Пример. a = 5 , p =13

2 13 + (−5) 5 =1 для числа 5 обратным будет (−5) добавим 13 и получим (−5) +13 = 8 и имеет место сравнение 8 5 ≡1(mod 13) .

34

Как следует из расширенного алгоритма Евклида, обращать можно не только по простому модулю, лишь бы a и p были взаимно простые.

Теорема (малая теорема Ферма). Пусть p — простое, u — целое, u ≠ 0 u p−1 ≡1(mod p) ,

при условии, что p не делит u.

Условие p — простое является существенным: Например, u = 5 , p = 6 55 ≡/ 1(mod 6) . Так что расширенный алгоритм Евклида в этом плане лучше.

Проблемой является распознавание простоты числа такое, чтоб его сложность была полиноминально ограниченной: O(md ), m =ν(n) или, что то же самое, O(logd n). Можно попробовать зацепиться за малую теорему Ферма: u p ≡ u(mod p) p — простое. Т.е. можно

для возведения в степень воспользоваться бинарным алгоритмом возведения в степень, но для сокращения затрат брать результат по модулю. Далее проверить условия теоремы и дать ответ. Но такой алгоритм, вообще говоря, неверный, т.к. существуют составные числа Кармайкла (бесконечно много), которые не ловятся таким алгоритмом.

Тем не менее, в 2002 году три индийских математика — Агравал, Кайал и Саксена — разработали алгоритм определения простоты числа с полиномиальной сложностью. Этот алгоритм базируется на следующем утверждении:

Утверждение. Пусть u, n N , u n (взаимно простые). Тогда n является простым, если и только если (x −u)n ≡ xn −u(mod n) .

Доказательство. Необходимость. Пусть n — простое и, для определённости, нечётное (для

n = 2 проверяется непосредственно). Сравним коэффициенты при степенях xk для 1 < k < n . В правой части очевидно все коэффициенты равны нулю, а в правой из формулы бинома

Ньютона получаем (−1)k Cnk an−k . Т.к. для числа сочетаний верно Cnk ≡ 0(mod n) (см. задачу 42), то получаем, что (−1)k Cnk an−k ≡ 0(mod n) , т.е. коэффициенты в левой и правой части сравнимы с нулём по модулю n. Для k = n доказывать нечего, проверим свободный член: надо показать, что (−u)n ≡ −u(mod n) , но это следует непосредственно из малой теоремы Ферма.

Достаточность докажем от противного. Пусть n — составное, тогда найдётся такое q, которое будет являться делителем n. Рассмотрим ещё k такое, что qk ещё делит n, а qk +1 уже нет. Рассмотрим число сочетаний из n по q:

Cq = n[(n −1) ... (n − q +1)]

n q!

Ни один из множителей в квадратных скобках не может делиться на q. В итоге после сокращения должно получиться целое число, которое на qk уже не делится (т.к. одно q из знаменателя сократится с n). qk un−q , и коэффициент в правой части (−1)n−q un−qCnq xq не

сравним с нулём по модулю n, что противоречит утверждению. Полученное противоречие завершает доказательство.

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

Итак, получаем следующий способ определения простоты числа: возьмём u =1 , раскроем скобки и посчитаем остаток от деления на n. Но после раскрытия скобок получим n +1 слагаемое, и нужно будет поработать со всеми ими. Откуда для сложности алгоритма будет верна оценка Ω(n), а n ≈ 2m и всё хорошо, но сложность экспоненциальная.

35

Посмотрим, что предлагают авторы. Рассмотрим сравнение: (x −u)n	≡ xn −u(mod xr −1, n),
которое означает следующее: (x −u)n − xn + u = Q(x)(xr −1)+ S(x) и	все коэффициенты
делятся на n.

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

Во-первых, r берётся не «с потолка», а совершенно конкретным, допуская оценку r = O(m6 ). Во-вторых, u тоже не является произвольным. Авторы показывают, что достаточно проверить сравнительно небольшой набор, допускающий оценку O(m r )~ m4 . Тогда, если

использовать эти r и u, то по необходимому и достаточному условию можно распознать простоту числа, и сложность будет полиномиальной.

36

Об одном классе рекуррентных соотношений («разделяй и властвуй»)

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

Для начала рассмотрим «игрушечный» алгоритм построения множества Vn , содержащего все

положительные целые числа, десятичные записи которых таковы, что сумма их цифр равна n. V1 ={1} . Упростим задачу, рассматривая только такие цифры, десятичные записи которых

состоят только из единиц и двоек: V2 ={11, 2} , V3 ={111, 21,12}. Задача ставится следующим образом: дано n, и надо построить Vn .

Множество Vn можно разделить на 2 непересекающихся подмножеств: на конце чисел

первого подмножества стоят единицы, на конце цифр второго — двойки. Если откинуть последнюю цифру, то получим Vn−1 и Vn−2 ( n > 2 ). Тем самым получаем алгоритм

построения Vn : к числам из Vn−1 нужно приписать «1», к числам из Vn−2 — «2» и объединить полученные множества.

Обозначим через vn количество элементов в Vn , тогда v1 =1, v2 = 2 , vn = vn−1 + vn−2 . Замечаем, что vn совпадает с (n +1) -м числом Фибоначчи, т.е. vn = vn−1 + vn−2 = Fn+1 .

Попробуем определить y(n) — число операций над числами (приписывание «1» или «2»). Для y(n) мы можем написать следующее рекуррентное соотношение:

y(n) = y(n −1) + y(n − 2) + Fn + Fn−1

14243

Fn+1

y(n) − y(n −1) − y(n − 2) = Fn+1 , причём y(1) = y(2) = 0

Обозначим затраты на объединение двух множеств через z(n) и, аналогично, получим для z(n) следующее рекуррентное соотношение:

z(n) − z(n −1) − z(n − 2) =1,

(*)

z(1) = z(2) = 0 (предполагаем, что V1 и V2 нам даны).

Непосредственно видно, что −1 является частным решением соотношения (*). Частные решения можно угадывать, но можно воспользоваться специальным методом их нахождения, который очень сильно похож на метод нахождения частных решений линейных дифференциальных уравнений с постоянными коэффициентами. Суть метода заключается в следующем: рассмотрим однородное рекуррентное соотношение

ad y(n) + ad −1 y(n −1) +... + a0 y(n − d) = 0

Составим по нему характеристическое уравнение, которое имеет вид: ad λd + ad −1λd −1 +... + a0 = 0 ,

которое, в свою очередь, будет иметь корни λ1, λ2 , ... , λk (включая комплексные) с

k

кратностями m1, m2 , ... , mk ( ∑mi = d ). Аналогично дифференциальным уравнениям, в

i=1

случае простого корня (кратность единица) будем иметь просто константу, в случае кратного

37

корня появляется многочлен (в общем случае, константу тоже можно рассматривать как многочлен нулевой степени). Итого, общее решение однородного рекуррентного соотношения будет иметь вид:

∑k (Ci,0 + Ci,1n +... + Ci,mi −1nmi −1 )λin

i=1

Рассмотрим теперь неоднородное рекуррентное соотношение. Когда в правой части стоит квазиполином (выражение вида p(n)µn , где p(n) — полином) или сумма квазиполиномов,

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

уравнения. Пусть среди корней характеристического уравнения µ встречается l раз, тогда частным решением будет квазиполином q(n)µn , где deg q(n) = l + deg p(n) .

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

Таким образом, для (*) характеристическим уравнением будет следующее:

λ2 − λ −1 = 0

корнями которого будут λ1 = 1+2 5 =φ и λ2 = 1−2 5 =φ~ . Исходя из этого, получаем, что

общем решение однородного рекуррентного соотношения будет иметь вид:

C1φn +C2φ~n

В правой части стоит «1», но никто не мешает рассматривать её как 1n , т.е. она является квазиполиномом ( µ =1 ; p(n) =1 ). 1 не встречается среди корней характеристического

уравнения, поэтому частное решение можно искать в виде константы, откуда получаем, что −1 будет являться частным решением (*). Общее решение неоднородного соотношение будет складываться из общего решения однородного и частного решения неоднородного:

z(n) = C1φn + C2φ~n −1

Из начальных условий ( z(1) = z(2) = 0 ), находим константы: C1 = 15 , C2 = − 15 . Таким образом z(n) = 15 (φn −φ~n )−1 = 15 φn +O(1) . Можно выписать более простую (и более грубую) оценку: z(n) = Θ(φn ).

Обратимся к соотношению для y(n) : очевидно, что − φ1 =φ~ и по формуле Бене получаем,

что правая часть Fn+1 = C1φn + C2φ~n , где C1 и C2 — полиномы нулевой степени, т.е. имеет

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

частным решением следующего вида: p1(n)φn + p2 (n)φ~n , где p1(n) и p2 (n) — полиномы 1-й степени.

Общее решение неоднородного соотношения будет иметь вид:

y(n) = C φn + C φ~n + p			(n)φn + p	(n)φ~n = q	(n)φn + q	(n)φ~n ,
1	2	1	2	1	2
			38

где q1(n) и q2 (n) — полиномы, имеющие первую степень. Их можно найти, но в данном случае это не нужно, т.к. нам нужна оценка для y(n) . Для y(n) будет верна следующая оценка: y(n) = Θ(nφn ). Если нужны более точные оценки, то их можно вычислить, найдя точные представления для q1(n) и q2 (n) .

Отметим, что представленный алгоритм вычисления Vn не является эффективным. Действительно, Vn вычисляется, исходя из Vn−1 и Vn−2 . Vn−1 , в свою очередь, вычисляется, исходя из Vn−2 и Vn−3 . Но Vn−2 и в том и в другом случае будут вычисляться независимо (уж

такой алгоритм). Поэтому напрашивается следующая модернизация: нужно вычислять множества парами: (Vn , Vn−1 ), (Vn−1, Vn−2 ), …, где Vn−1 просто переходит. Тогда, для числа

операций над числами получим такое соотношение:

y* (n) − y* (n −1) = Fn+1 y* (1) = 0

Характеристическое уравнение такого соотношения будет уравнением первой степени, имеющее единственный корень λ =1 y* (n) = Θ(φn ).

Для числа объединений получаем следующее рекуррентное соотношение:

z* (n) − z* (n −1) =1 z* (n) = n − 2 z* (1) = 0

Рассмотрим ещё более «неприятную» рекурсию:

Yn =U (Yn−1, Yn−2 , ... , Yn−k )

Сколько раз при обращении к Yn нужно будет обратиться к U ? Возникает такое рекуррентное соотношение:

y(n) − y(n −1) −... − y(n − k) =1 y(0) =... = y(k −1) = 0

потому что можно считать, что Y0 , Y1, ... , Yk −1 нам известны.

Чтобы разобраться, как решение будет себя вести, надо исследовать характеристическое уравнение:

λk −λk −1 −... − λ −1 = 0

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

корня верно 1 < λk < 2 , причём при k → ∞ λk → 2 . Таким образом, когда k → ∞ для сложности получаем оценку Θ(2n ).

Стратегия «разделяй и властвуй» заключается в следующем: пусть имеется задача, размер входа равен n; разбиваем исходную задачу на несколько подзадач, размеры хода которых

будут меньше n (если c задач, то размеры входа nc с соответствующим округлением). В

случае размера входа n = 0 или n =1, предполагаем, что решение задачи известно.

Обратимся к какому-нибудь известному алгоритму, чтобы увидеть, как всё это работает. Для примера рассмотрим алгоритм сортировки слияниями (MS = merged sort): пусть дан массив

39

x , ... , x	n	, разделяем его на две части длинами	n			и	n			, упорядочиваем полученные части
1				2				2

(применяя алгоритм рекурсивно) и сливаем. Если длина массива равна 1, то ничего делать не надо.

Если мы попробуем исследовать сложность (в худшем случае) этого алгоритма по числу сравнений, то

0, n =1

n

n

TMS (n) ≤

+T

+ n −1 , n >1

T

MS

MS

2

{

2

на слияние

Пока не знаем, что равенство достигается, поэтому ставим ≤.

Разные книги по-разному показывают, как работать с этим соотношением. Мы сведём его к рекуррентному соотношению с постоянными коэффициентами.

Предложение. Пусть функция f : N → R такая, что

u, n =1
	n		n
f (n) ≤						+ϕ(n), n >1,
v f			+ w f	2
	2

где u, v, w — целые неотрицательные числа и v, w не равны нулю одновременно, функция ϕ : N → R неотрицательная и неубывающая. Тогда f (n) ≤ t( log2 n ), где t(n) — решение рекуррентного уравнения

u, k = 0

t(k) = ( )

(v + w) t(k −1) +ϕ 2k , k > 0

	u, n =1
Доказательство: Введём		n		n
	F(n) =
	vF			+ wF	2		+ϕ(n),
		2

«=»). Можно доказать, что F(n) является неубывающей, т.е.

n ≥ 2 F(n) ≥ F(n −1)

Доказательство этого факта проведём по индукции: для n = 2

n >1 (то же, что и f (n) , но с

(*)

имеем:

F}(1)

F(2) = (v + w) u +ϕ(2) ≥ u = F(1)

123

≠0

Если неравенство (*) выполнено для 2,3,…, n −1, то

n

n −1

n

n −1

≥1

n >

≥

2

≥1, n >

≥

2

2

2

n

n

+ϕ(n)

n −1

n −1

+ϕ(n −1) = F(n −1)

F(n) = vF

+ wF

≥ vF

+ wF

2

2

2

2

14243

не убывает

Аналогично доказывается индукцией, что

f (n) ≤ F(n)

f (n) ≤ F(n) ≤ F(2 log2 n ).

F(2k )

u, k = 0

= (v + w)F(2k−1 )

+ϕ(2k ), k ≥1

40