1. Понятие сложности
Многие алгоритмы легко объяснить и понять, но есть и весьма сложные для понимания. Однако, когда специалисты рассуждают о сложности алгоритмов, они обычно имеют в виду нечто иное. Когда алгоритм реализован в виде программы и программа запускается на выполнение, она расходует вычислительные ресурсы, важнейшими из которых являются процессорное время и оперативная память. Именно эти два параметра и характеризуют сложность алгоритма в общепринятом ныне понимании – время и память, расходуемые на решение задачи. Они называются сложностью по времени (временнóй сложностью) и сложностью по памяти (объемной или емкостной сложностью).
Развитие технологии привело к тому, что память стала дешевой и компактной. Как правило, она не является критическим ресурсом – ее вполне достаточно для решения задачи. Поэтому чаще всего под анализом сложности алгоритма понимают исследование его временной сложности. Далее под сложностью будем понимать именно временную сложность, ее еще называют трудоемкостью алгоритма.
В каких единицах измерять сложность алгоритмов? Понятно, что обычные единицы измерения времени (секунды и т.д.) здесь не подходят – одна и та же программа при одних и тех же входных данных на разных компьютерах будет выполняться, вообще говоря, разное время. Обычно сложность алгоритма измеряют числом выполняемых элементарных операций. Однако далеко не всегда ясно, какие операции следует считать элементарными. Кроме того, разные операции требуют для своего выполнения разного времени, да и перевод операций, используемых в описании алгоритма, в операции, используемые в компьютере – дело очень неоднозначное, зависящее от таких, например, факторов, как свойства компилятора и квалификация программиста. Поэтому утверждение, что такой-то алгоритм при таких-то входных данных требует 150000000 операций, фактически не несет информации о реальном времени вычислений. На самом деле задача анализа сложности алгоритма состоит в исследовании того, как меняется время работы при увеличении объема входных данных. Оно, конечно, растет, но с какой скоростью?
Тут же возникает вопрос – а как измеряется объем входных данных? Рассмотрим, например, алгоритм, который складывает n чисел х1, х2, ... , хn. Вот он:
Sum:=0;
for i:=1 to n do
Sum:=Sum + x[i]
Если числа не слишком велики и сумма может быть вычислена с использованием стандартной операции сложения, то можно измерять объем входных данных просто числом слагаемых. Считая элементарной операцией сложение, приходим к выводу, что трудоемкость алгоритма равна n. Если же складываются очень большие числа, то для сложения нужно использовать специальные программы и объем входных данных правильнее измерять суммарной длиной представления слагаемых (например, в битах). Эта мера в любом случае более точная, но с ней и сложнее работать, а иногда эта точность излишняя. Обычно у задачи есть какой-нибудь естественный параметр, характеризующий объем входных данных, как число слагаемых в этом примере, и сложность оценивается по отношению к этому параметру.
Однако при одном и том же значении параметра разные наборы входных данных могут обрабатываться разное время. Рассмотрим, например, алгоритм последовательного поиска. Он ищет элемент z в массиве x, состоящем из n элементов, просматривая последовательно все элементы массива. Результатом поиска является значение переменной k – оно равно n + 1,
если искомый элемент не найден, в противном случае k = i, если z = x[i].
k:=n+1;
for i:=1 to n do
if z=x[i] then
k:=i;
break
Представительной операцией можно считать сравнение if. Число выполняемых сравнений в худшем случае будет равно n, а в лучшем 1. Но допустим, что массив х представляет собой перестановку чисел 1, 2, ... , n, что все перестановки равновероятны и что искомый элемент обязательно находится в массиве, т.е. представляет собой целое число между 1 и n. Тогда в среднем будет выполняться сравнений. Это две наиболее распространенные меры сложности – трудоемкость в худшем случае и трудоемкость в среднем. Иногда они различаются гораздо сильнее, чем в этом примере.
2. Асимтотические оценки
Полезно иметь оценку сложности того или иного алгоритма, но еще важнее то, что с помощью таких оценок можно сравнивать друг с другом разные алгоритмы для решения одной задачи. Допустим, для некоторой задачи имеется два алгоритма, трудоемкость одного из них оценивается как 2n2, а другого – как 100n. Предположим, что эти формулы достаточно точно отражают время работы алгоритмов (что на самом деле бывает редко). Тогда ясно, что при небольшой длине входа (именно, при n < 50) предпочтительнее использовать первый алгоритм, а при большой – второй. Но при малой длине входа время работы каждого из двух алгоритмов будет невелико, так что, может быть, мы практически ничего не потеряем, если и здесь будем пользоваться вторым алгоритмом. Этот пример призван помочь понять, почему при анализе сложности алгоритмов главное внимание уделяется асимптотическому поведению сложности, т.е. поведению при больших длинах входа.
При асимптотическом оценивании функций используются следующие понятия.
Функция f(n) по порядку не превосходит функцию g(n), если существует такая константа c > 0 и такое n0, что при всех n > n0 выполняется неравенство f(n) ≤ cg(n). Это записывается так: f(n) = O(g(n)) (читается: f(n) есть О большое от g(n)).
Последний способ записи нельзя считать очень удачным – слишком необычным образом используется здесь знак равенства. Нельзя, например, переставить части равенства и написать O(g(n)) = f(n). Тем не менее, традиционно сложилось именно такое употребление символа О. Иногда, впрочем, считают, что O(g(n)) – это множество всех функций, по порядку не превосходящих функцию g(n). Тогда можно писать и это уже вполне согласуется с обычной математической символикой. К сожалению, так поступают редко.
Функция f(n) имеет тот же порядок, что и функция g(n), если f(n) = O(g(n)) и g(n) = O(f(n)). Это записывается так: f(n) = Θ(g(n)) (читается: f(n) есть тэта от g(n)).
Например, 10n2 = O(n2), 10n2 = Θ (n2), n2 = O(n3), но n2 ≠ Θ(n3),
При анализе сложности алгоритмов обычно оценки трудоемкости выполняют с точностью до порядка, отбрасывая слагаемые меньших порядков и постоянные множители. Например, если для какого-то алгоритма получена верхняя оценка числа операций 3n2 + 4n + 2, то говорят, что трудоемкость этого алгоритма есть O(n2).
Функции, часто встречающиеся при анализе алгоритмов:
- log n (логарифмическое время),
- n (линейное время),
- n log n,
- n2 (квадратичное время),
- 2n (экспоненциальное время).
Первые четыре функции имеют невысокую скорость роста и алгоритмы, время работы которых оценивается этими функциями, можно считать быстродействующими. Скорость роста экспоненциальной функции иногда характеризуют как «взрывную». Для сравнения допустим, что имеются алгоритмы, трудоемкость которых (число операций) достаточно точно отражается этими функциями. Пусть эти алгоритмы выполняются на компьютере, работающем со скоростью 1012 операций в секунду. При длине входа n ≤ 100000 алгоритмы, скорость работы которых оценивается первыми четырьмя функциями, получат ответ за ничтожные доли секунды. Для алгоритма с трудоемкостью 2n время работы оценивается следующим образом:
- n = 50 ≈ 19 минут,
- n = 60 ≈ 320 часов,
- n = 70 ≈ 37 лет.
Существуют ситуации, когда постоянный коэффициент при порядковой функции следует учитывать. Это бывает, когда сравниваются разные алгоритмы для одной задачи, причем оцениваются они относительно одних и тех же представительных операций. Рассмотрим, например, задачу нахождения наименьшего элемента в последовательности х1, х2, ... , хn. Она решается просто:
min:=x[1];
for i:=2 to n do
if x[i]<min then min:=x[i]
Этот алгоритм использует n – 1 сравнение. Столько же потребуется для поиска наибольшего элемента. Допустим теперь, что нам нужно найти и тот, и другой. Можно найти сначала минимум, а потом максимум, затратив всего 2 n – 2 сравнений. Можно поступить лучше: разобьем наш массив на последовательные пары (считаем для простоты, что n четно, n = 2k) и сравним элементы в каждой паре, т.е. х1 и х2, х3 и х4, ..., х2k–1 и х2k. Если элемент, стоящий на нечетном месте, больше элемента, стоящего на четном, поменяем их местами. После этого наименьшй элемент будет стоять на нечетном месте, наибольший – на четном и для нахождения каждого из них достаточно выполнить сравнений.
for i:=1 to k do
if x[2i-1] > x[2i] then обменять x[2i-1] и x[2i];
min:= x[1];
for i:=2 to k do
if x[2i-1]<min then min:= x[2i-1];
max:= x[2];
for i:=2 to k do
if x[2i]>max then max:= x[2i]
Общее число сравнений будет . Таким образом, оба алгоритма выполняются за линейное время, но различие в коэффициентах показывает, что второй работает быстрее.
3. Примеры
Рассмотрим несколько примеров анализа трудоемкости алгоритмов.
3.1. Вычисление чисел Каталана
Число Каталана задается формулой
.
Эти числа возникают при решении разнообразных комбинаторных задач. В частности, равно числу способов триангулировать выпуклый n-угольник, т.е. разбить его диагоналями на треугольники. На рисунке 1 показано несколько способов триангулировать шестиугольник (всего их ).
SHAPE \* MERGEFORMAT
| 2 |
| 1 |
| 3 |
| 5 |
| 4 |
| 6 |
| 5 |
| 4 |
| 6 |
| 1 |
| 2 |
| 2 |
| 1 |
| 3 |
| 5 |
| 4 |
| 6 |
| 5 |
| 4 |
| 6 |
| 1 |
| 2 |
Рис. 1.
Для вычисления чисел Каталана удобно пользоваться равенством
при . Это дает рекурсивный алгоритм вычисления с учетом того, что . Обозначим через число арифметических действий, которые придется произвести для вычисления с использованием этой формулы. Из формулы видно, что
при . Кроме того, . Отсюда получаем .
3.2. Сортировка
Задача сортировки применительно к числовому массиву состоит в том, чтобы выстроить элементы массива в неубывающем порядке: x[1] ≤ x[2] ≤ … ≤ x[n]. Алгоритмы сортировки подробно будут рассматриваться в одной из следующих лекций, здесь рассмотрим один из простейших таких алгоритмов – сортировку с помощью выбора. В этом алгоритме мы сначала добиваемся того, чтобы на первом месте в массиве оказался наименьший элемент. Для этого первый элемент сравнивается поочередно со всеми остальными, если какой-то элемент оказывается меньше первого, производится обмен. Затем точно так же устанавливается на свое место второй по величине элемент и т.д.
for i:=1 to n-1 do
for k:=i+1 to n do
if x[i]>x[k] then обменять x[i] и x[k]
Оценим число проверок if (число обменов будет, во всяком случае, не больше). При фиксированном i внутренний цикл повторяется n – i раз, значит, общее число повторений будет (n – 1) + (n –2) + … + 2 + 1 = . Следовательно, трудоемкость этого алгоритма есть Θ(n2).
3.3. Бинарный поиск
Последовательный поиск находит элемент в произвольном массиве длины n за время O(n). Если массив упорядочен : x[1] < x[2] < … < x[n], то возможен существенно более быстрый поиск. Можно сначала сравнить искомый элемент z со средним элементом массива, т.е. с x[k], где . Если z = x[k], то задача решена. Если z < x[k], то поиск следует продолжать среди элементов x[1] , x[2], …, x[k – 1], а если z > x[k], то среди элементов x[k + 1] , x[k + 2], …, x[n]. В любом случае область поиска сужается примерно вдвое. После следующего сравнения она уменьшится еще вдвое и т.д.
В каждый момент работы этого алгоритма мы будем иметь дело с некоторым отрезком исходного массива. Введем переменные s и t, указывающие начало и конец этого отрезка. Это значит, что в текущий момент рассматривается отрезок x[s] , x[s + 1], …, x[t]. Результатом работы алгоритма является значение переменной k: если , то x[k] = z, если же k = 0, то элемент z в массиве отсутствует.
s:=1;
t:=n;
while s≤t do
k:= (s+t) div 2;
if z=x[k] then break;
if z<x[k]
then t:=k-1
else s:=k+1;
if s>t then k:=0
Для анализа трудоемкости этого алгоритма исследуем число повторений (в худшем случае) цикла while. Для упрощения анализа предположим, что n имеет вид n = 2m – 1. После первого повторения цикла, если z не был найден, размер области поиска становится равным , т.е. опять является числом того же вида – степень двойки минус единица. После i повторений, если z все еще не найден, в области поиска останется 2m–i – 1 элементов. Значит, после m –1 повторения останется один элемент, т.е. будет s = t. После этого цикл повторится еще один раз и работа будет закончена. Таким образом, общее число повторений цикла равно
m = log2 (n + 1) + 1.
Нетрудно показать, что в общем случае (когда n произвольное) число повторений будет равно ближайшему целому сверху к числу log2 (n + 1) + 1. Следовательно, трудоемкость бинарного поиска оценивается как O(log n). Это существенно лучше, чем линейная трудоемкость последовательного поиска.
3.4. Генерирование подмножеств
Допустим, нам нужно получить все подмножества некоторого конечного множества, одно за другим, без пропусков и повторений. Такое может понадобиться для разных целей, один пример приводится ниже. Для определенности, пусть базовое множество есть . Удобным способом представления подмножеств в этом и многих других случаях является характеристический вектор (характеристический массив), который для подмножества определяется как , где для
Двоичный набор h можно рассматривать как двоичное n-разрядное представление целого числа . Таким образом генерирование подмножеств сводится к генерированию таких чисел. Последняя решается очень просто – в качестве первого числа берется 0, а каждое следующее получается из предыдущего прибавлением 1. Алгоритм, прибавляющий 1, действует следующим образом: просматриваются элементы массива h, начиная с последнего; все встречающиеся единицы заменяются нулями; как только встретится нуль, он заменяется единицей и работа прекращается.
i:=n;
while (i>0) and (h[i]=1) do
h[i]:=0;
i:=i-1;
if i>0 then h[i]:=1
Значение i = 0 по окончании работы алгоритма сигнализирует о том, что данное подмножество – последнее ( для всех i , что соответствует всему множеству А). Теперь, взяв в качестве начального массив, состоящий из одних нулей (соответствует пустому множеству), и применяя последовательно 2n – 1 раз описанный выше алгоритм, найдем все подмножества множества A.
Для оценки трудоемкости этого алгоритма заметим, что если цикл while выполняется t раз, то общее время работы алгоритма ограничено сверху величиной вида , где а и b – некоторые константы. Величина t зависит от обрабатываемого массива, оценим среднее ее значение. Пусть – суммарное число повторений цикла (для получения всех подмножеств). Цикл выполняется не менее одного раза для всех векторов h с , число которых равно , второй раз он выполняется для векторов с , их число равно , и т.д. Получаем
.
Для получения всех подмножеств алгоритм применяется 2n – 1 раз. Таким образом, на одно подмножество в среднем приходится повторение цикла. Иначе говоря, среднее время, затрачиваемое на получение одного подмножества, не зависит от n.
3.5. Подмножество с заданной суммой
Рассмотрим следующую задачу. Дано множество положительных целых чисел A = {a1, a2, … , an} и число b. Требуется выяснить, имеется ли в множестве A такое подмножество, сумма элементов которого равна b?
Эта задача – представитель обширного класса так называемых неподдающихся задач. Для этих задач не удается найти алгоритм решения, существенно более быстрый, чем перебор всех вариантов, а число таких вариантов быстро растет с увеличением длины входа. Существует теория, цель которой – доказать, что дело не в нашем неумении строить эффективные алгоритмы, а в объективной сложности подобных задач. Пока эта цель не достигнута, но на этом пути получено немало интересных результатов, делающих такое предположение весьма правдоподобным.
Перебор вариантов в данном случае организовать нетрудно, если воспользоваться изложенным выше алгоритмом генерирования всех подмножеств данного множества. Этот алгоритм, как было показано, тратит 2n представительных операций на порождение всех подмножеств. Для каждого из них еще требуется подсчитать сумму его элементов и сравнить ее с числом b. Получается общая оценка трудоемкости O(n2n).
4. Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, 2000. – 382 с.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2001. – 955 с.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 476 с.