Чет про программирование / асимптотика

широко применяемое приближение

√

n! ≈ 2πn (ne )n.

Paul Bachmann в 1894 г. ввел очень удобное обозначение O (читается "o большое") для использования в приближенных формулах, до сих пор этот формализм применяется во многих математических дисциплинах, в том числе и при анализе алгоритмов.

Определение 1. Неотрицательная функция f(n) не превосходит по порядку функцию g(n) (используем запись f(n) = O(g(n)) ), если существуют положительные константы N и c такие, что f(n) ≤ c g(n)

для любого n ≥ N.

В этом случае функция g(n) является асимптотически верхней оценкой функции f(n)1. Часто встречающемуся выражению "трудоёмкость (сложность) алгоритма есть или равна O(g(n))" придаётся именно такой смысл. Это означает, что для некоторой постоянной c алгоритм на произвольном входе размерности n заканчивает работу не более, чем через c g(n) элементарных операций для всех достаточно больших n. В частности, трудоёмкость O(1) означает, что время работы соответствующего алгоритма не зависит от размерности входа и не превосходит некоторой константы. Алгоритм с трудоёмкостью O(n), где n — размерность входа, называют линейным. Алгоритм сложности O(nc) называется полиномиальным. Алгоритм, сложность которого есть O(2 nc ), называется

экспоненциальным. Здесь c — положительная константа.

Записи с символом O дают верхнюю оценку скорости роста функции, но, вообще говоря, не дают точный порядок роста. Например, если время работы алгоритма есть O(n2), это не означает, что это же время не может составлять O(n). Для нижних оценок применяется другая запись с символом Ω (читается "омега большое").

1 С точностью до константы.

11

Определение 2. Неотрицательная функция f(n) не меньше по порядку функции g(n) (используем запись f(n) = Ω(g(n)) ), если существуют положительные константы N и c такие, что f(n) ≥ c g(n) для любого n ≥ N.

В этом случае функция g(n) является асимптотически нижней оценкой функции f(n). И наконец, чтобы точно указать порядок роста функции f(n), не давая точных значений констант, применяется запись с символом Θ (читается "тэта большое").

Определение 3. Неотрицательная функция f(n) асимптотически равна функции g(n) (используем запись f(n) = Θ(g(n)) ), если существуют положительные константы N, c1, c2 такие, что выполняются неравенства c1 g(n) ≤ f(n) ≤ c2 g(n) для всех n ≥ N.

Запись f(n) = Θ(g(n)) включает в себя две асимптотические оценки: верхнюю и нижнюю. Таким образом, начиная с некоторого N рост функции f(n) полностью соответствует росту функции g(n). В дальнейшем выражению "сложность алгоритма есть Θ(g(n))" будем придавать именно этот смысл.

Отметим, что для функции многих переменных f(n1, . . . , nk) символ

Λ(f(n1, . . . , nk)), Λ {O, Ω, Θ} определяется подобным же образом. Записи с асимптотическими обозначениями O, Ω, Θ очень удобны

и часто употребляются в уравнениях, но при этом требуют некоторой осторожности. Дело в том, что используемый знак "=" — это не равенство в обычном смысле, а несимметричное (!) отношение включения подмножеств " ". В этом случае с формальной точки зрения запись O(g(n)) необходимо рассматривать как множество неотрицательных функций f(n), не превосходящих по порядку функцию g(n), а функцию f(n) — как одноэлементное множество. Таким образом, запись f(n) = O(g(n)) означает запись f(n) O(g(n)), запись O(n) = O(n2)

означает O(n) O(n2) и т. д. В случае арифметических операций над

12

такими множествами функций X, Y и функцией f(n) множества X +Y ,

X Y , f X определяются следующим естественным образом:

X + Y = {x + y | x X & y Y },

X Y = {x y | x X & y Y },

f X = {f x | x X}.

Аналогично следует трактовать Λ-записи в общем случае, когда Λ

{O, Ω, Θ}. Используя введенные определения асимптотических обозначений, легко доказать справедливость свойств, сформулированных в следующем утверждении.

Теорема 1. Пусть f(n), g(n), h(n) — неотрицательные функции и

Λ{O, Ω, Θ}. Тогда

(i)f(n) = Λ(f(n)) (рефлексивность);

(ii)если f(n) = Λ(g(n)) и g(n) = Λ(h(n)), то f(n) = Λ(h(n)) (транзитивность);

(iii)f(n) = O(g(n)) g(n) = Ω(f(n)) (обращение);

(iv)f(n) = Θ(g(n)) g(n) = Θ(f(n)) (симметричность);

(v)f(n) = Θ(g(n)) (f(n) = O(g(n)) & f(n) = Ω(g(n)) (эквивалентность);

(vi)Λ(Λ(f(n))) = Λ(f(n)) (идемпотентность);

(vii)арифметические операции:

Λ(f(n)) Λ(g(n)) = Λ(f(n) g(n)), f(n) Λ(g(n)) = Λ(f(n) g(n)),

Λ(f(n)) + Λ(g(n)) = Λ(f(n) + g(n)) = Λ(max{f(n), g(n)}),

cΛ(f(n)) = Λ(cf(n)) = Λ(f(n)), если c — положительная константа.

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

13

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

Пример 1.

∑n

(i) f(n) = Θ(n2), где f(n) = c1n + c2 i + c3.

i=1

Действительно, используя теорему 1 и формулу суммы арифметической прогрессии, получаем f(n) = O(n) + c2(n2 + n)/2 + O(1) = O(n) +

O(n2)+O(n)+O(1) = O(max{n, n2}) = O(n2). Очевидно, f(n) ≥ c2 n2/2 .

Поэтому f(n) = Ω(n2). Таким образом, f(n) = Θ(n2).

√

(ii) c n ≠ O( n).

В самом деле, пусть найдутся положительные константы c′ и N такие, что c n ≤ c′√n для всех n ≥ N. Тогда n ≤ (c′/c) 2 для всех достаточно больших n, пришли к очевидному противоречию.

(iii) c nm ≠ Ω(nk), где k > m.

Доказывается аналогично (ii).

(iv) O(n) + c12 n+c2 + c3 = O(2n).

Следует из теоремы 1 и неравенства 2 n ≥ n.

(v) Hn = ln n + Θ(1) = Θ(ln n), 2 где

Hn = ∑n 1i .3

i=1

Для асимптотических оценок гармонических чисел Hn воспользуемся аппроксимациями интеграла произвольной интегрируемой убывающей функции f(x) с помощью конечных сумм:

n+1		n	n
∫			∫
	f(x) dx ≤ i=m f(i) ≤			f(x) dx.
m		∑	m−1

2 ln n — натуральный логарифм.

3 Конечные суммы Hn известны как гармонические числа.

14

Функция f(x) = 1/x убывает на интервале (1, +∞). Следовательно, ln(n + 1) − ln 2 = n∫+1dxx ≤ ∑n 1i ≤ ∫n dxx = ln n.

2i=2 1

Поэтому Hn = ln n + O(1) и Hn ≥ ln n + 1 − ln 2 = ln n + Ω(1). Таким образом, Hn = ln n + Θ(1) = Θ(ln n).

Отметим, что аналогичные сравнения интеграла и конечной суммы

для произвольной возрастающей функции приводят к неравенствам

n	n	n+1
∫		∫
	f(x) dx ≤ i=m f(i) ≤		f(x) dx.
m 1	∑	m
−

Такие оценки используются в нижеприведенных примерах (vi) и (viii).

(vi) ln(n!) = Θ(n ln n).

Действительно, ln(n!) =			n
			i=1 ln i. Отсюда очевидно, ln(n!) ≤ n ln n =
O(n ln n).	Для	доказательства нижней оценки воспользуемся сравнени-
			∑

ем интеграла и конечной суммы функции ln x, возрастающей и положительной на интервале (1, +∞). Имеем

n	n			n
	1
∑
i=2 ln i ≥	∫	ln x dx = x ln x − x		1 = n ln n − n + 1 = Ω(n ln n).

Следовательно, ln(n!) = Θ(n ln n).

Заметим, что более точные верхнюю и нижнюю оценки величин n!

и ln(n!) можно получить из формулы Стирлинга n! = √2 π n (ne )n(1 + Θ(1/n)).

(vii) lg(n!) = Θ(n lg n)4.

Непосредственно следует из примера (vi) и равенства lg(n!) = lg e ln(n!).

	n
(viii)	∑i	n2		n2
	i ln i =		ln n −		+ O(n ln n) = O(n2 ln n).
		2		4
	=1

4 lg n — двоичный логарифм.

15

Действительно, поскольку f(x) = x ln x — возрастающая функция, как и в примере (v), получаем следующие неравенства:

n−1

n

x2

x2

n

∫

i=2 i ln i ≤

x ln x dx =

ln x −

2 =

2

4

∑

2

n

2

n

2

2

n

2

=

ln n −

− ln 4 + 1 ≤

n

ln n −

.

2

4

2

4

Осталось заметить, что

n

n−1

i ln i = n ln n +

i ln i.

=1

i=2

i∑

∑

∑n=c

(ix)lg i = Ω(n lg n)5.

i=1

Доказательство требуемой нижней оценки проведём с помощью метода разбиения суммы на части. Для n ≥ 2c имеем6

n=c	n=2c−1				n=c
∑		∑		lg i +	i=∑
lg i =							lg i ≥
i=1			i=1		n=2c
≥		n=c		lg i ≥	n=c		lg n/2c ≥
			n=2c		i= n=2c
	i=∑				∑
≥ ( n/c − n/2c + 1 ) ( lg(n/2c) − 1 ) ≥
		n
≥			( lg n − lg(2c) − 1 ) =
		2c
=	Ω(n) Ω( lg n) = Ω(n lg n).

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

5 x — наибольшее целое число, не превосходящее x;

x — наименьшее целое число, не меньшее x.

6 Здесь использованы неравенства x − 1 < x ≤ x ≤ x < x + 1: 7 Константа c в определении O(g(n)).

16

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

3.Алгоритм нахождения n-факториального представления числа

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

Определение 4. n-факториальным представлением целого неотрицательного числа m называется последовательность целых чисел

(d0, d1, . . . , dn−1) такая, что 0 ≤ di ≤ i при i = 0, 1, . . . , n − 1 и

m = dn−1(n − 1)! + dn−2(n − 2)! + . . . + d00!.

Из курса алгебры известно, что для произвольного целого неотрицательного числа m < n! существует8 n-факториальное представление числа m, причём единственное. Рассмотрим следующую задачу: пусть задано значение n, а m может быть любым целым неотрицательным числом, не превосходящим n!, требуется найти n-факториальное представление числа m. Эта задача легко решается c помощью простого алгоритма. Неформально опишем его по шагам.

Шаг 0. Полагаем d0 = 0 и q0 = m.

Шаг 1. Делим q0 на 2, находим остаток от деления d1 и частное от деления q1 = q0/2 . При этом имеем 0 ≤ d1 < 2.

8 Последовательность (d0; d1; : : : ; dn−1) является записью числа m относительно

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

17

Переходим к следующему шагу. К шагу i ≥ 1 будут определены числа d0, d1, . . . , di−1 и q0, q1, . . . , qi−1.

Шаг i. Делим qi−1 на i + 1, полагаем di — остаток от деления и qi = qi−1/(i + 1) . При этом имеем 0 ≤ di < i + 1.

Шаг n − 1. На заключительном шаге находим остаток dn−1 от деления qn−2 на n и частное qn−1 = qn−2/n .

Нетрудно доказать, что последовательность (d0, d1, . . . , dn−1), вычисленная посредством этого алгоритма, является n-факториальным представлением числа m. Заметим, что пошаговый процесс можно закончить, как только будет выполнено равенство qi = 0, все оставшиеся числа qj при j > i будут также равны 0. Кроме того, можно отказаться от массива из элементов qi, достаточно на каждом шаге записывать требуемое значение элемента qi в единственную переменную q. Таким образом, приходим к следующей программной реализации.

Алгоритм F Decomp(n, m) нахождения n-факториального представления числа m < n!

i := 0; d0 := 0; q := m;

while q > 0 do begin

i := i + 1;

di := q mod i; q := q/i

end;

i := i + 1;

while i < n do di := 0.

Чему равна сложность T (n) алгоритма F Decomp(n, m) нахождения n-факториального представления для произвольного числа m < n! ?

18

Оценим время работы алгоритма. Введем следующие обозначения:

•c1 — число элементарных операций, выполняющихся за одну итерацию первого while-цикла;

•c2 — число элементарных операций, выполняющихся за одну итерацию второго while-цикла;

•c3 — число элементарных операций, выполняющихся при инициализации переменных, вне обоих while-циклов;

•n1 — число итераций первого while-цикла;

•n2 — число итераций второго while-цикла.

Тогда время работы алгоритма F Decomp(n, m) равно c1n1 + 1 + c2n2 + 1 + c3, причём константы c1, c2, c3 не зависят от n, а числа n1, n2 определяются в зависимости от m и n1 + n2 = n − 1. Наибольшее число операций будет выполняться для такого числа m, когда di > 0 для любого i > 0. Поэтому в худшем случае (по времени работы алгоритма) n1 = n − 1, n2 = 0 и T (n) = c1(n − 1) + 2 + c3 = Θ(n). Причём и в лучшем случае время работы алгоритма F Decomp(n, m) есть Θ(n), так как выполняется равенство n1 + n2 = n − 1.

При определении n-факториального представления числа m иногда ограничиваются последовательностью (d0, d1, . . . , dk), для которой dk ≠ 0 и dk+1 = . . . = dn−1 = 0 при m > 0 (k = 0, если m = 0). В этом случае в алгоритме F Decomp необходимо отказаться от последнего while-цикла, в котором присваивается нулевое значение оставшимся членам последовательности di. Однако это не улучшит сложность

алгоритма, поскольку можно выбрать такое число m, что di > 0 для

n∑−1

всех i, например, m = i!. Таким образом, сложность алгоритма

i=1

F Decomp(n, m) есть Θ(n).

19

Глава 2 Генерация комбинаторных объектов

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

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

При рассмотрении класса комбинаторных объектов предполагается, что все его объекты имеют некоторую одинаковую количественную меру, предварительно заданную целочисленным параметром (или набором целочисленных параметров), который передается на вход алгоритма генерации. Нас прежде всего будет интересовать время работы алгоритма, требующееся для порождения всего класса объектов, как функция от размерности входных данных. Мы будем стремиться получить асимптотически наилучший алгоритм генерации. В частности, в некоторых алгоритмах можно порождать множество всех требуемых объектов за время, пропорциональное его мощности (при этом, естественно, не учитывается время для вывода на печать самого комбинаторного объекта). В этом случае алгоритм имеет сложность O(k), где k — число порождаемых объектов. Такой алгоритм генерации комби-

20