Алгоритмы (теория/практика): Часть 3. Сложность алгоритмов

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

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

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

Предположим, что мы имеем массив чисел от 0 до 7. Также предположим, что наш массив отсортирован – это условие очень важно, в противном случае двоичный поиск будет нереализуем.

Искомое значение: 6. Поехали.

0 1 2 3 4 5 6 7

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

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

• 1 шаг. На выходе мы получаем два подмассива – 0123 и 4567. Теперь очень важное действие, мы смотрим, в каком из подмассивов находится наше значение? Очевидно, что \(3\lt6\). Значит, во втором. Отбрасываем первый массив и выполняем ту же самую процедуру уже с нашим подмассивом.
• 2 шаг. Делим, получаем 45 и 67. Отбрасываем первый, идём дальше.
• 3 шаг. 6 и 7. Два массива из одного элемента – это тоже массивы. Отбрасываем второй и продолжаем поиск (команды выполняются компьютером, ему не все так очевидно, как нам.)
• 4 шаг. У нас есть 1 массив, состоящий из 1 элемента. Сравниваем и находим нужное значение.

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

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

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

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

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

Например, если у нас есть массив из 8 элементов, то количество сравнений будет равно 4. Массиву из 16 элементов уже потребуется 5 сравнений. И эта зависимость как раз и выражается функцией, что носит название «вычислительная сложность». В дальнейшем будет обозначать её как \(f\left( n \right)\), где \(n\)-размер входных данных.

Модель RAM (Random Access Memory)

Для простоты и однозначности определения такой «элементарной операции» будем использовать модель RAM. То есть, как известно, время исполнения одних и тех же алгоритмов на разных машинах может очень сильно разниться, что совсем нам не подходит. Поэтому мы будем работать с абстрактной RAM-машиной (машина с произвольным доступом к памяти), которая обладает бесконечной памятью, состоящей из ячеек, имеющих свой уникальный адрес, и работает следующим образом:

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

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

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

Давайте сначала рассмотрим именно их, а уже потом будем сравнивать на примере реальных алгоритмов. Согласны? Ну а куда же вы денетесь.

\(\Theta\)-обозначения

Буква читается как «тета». При помощи данного обозначения можно охарактеризовать асимптотически точную оценку сложности алгоритма. Что я имею в виду? Запись \(f\left( n \right)=\Theta (g\left( n \right))\) означает, что существуют положительные константы \({ c }_{ 1 }\), \({ c }_{ 2 }\) и \({ n }_{ 0 }\) такие, что

Самое время немного снизить скорость и разобрать всё, что мы сейчас узнали. Запись выше означает, что мы можем найти такую функцию \(g\left( n \right)\), которая бы ограничивала нашу функцию \(f\left( n \right)\) сверху и снизу для всех \(n\ge { n }_{ 0 }\).

Допустим, некоторый алгоритм работает с вычислительной сложностью \({ n }^{ 2 }-3\). Предположим, что асимптотической оценкой может служить функция \({ n }^{ 2 }\) (пока просто предполагаем, я научу находить правильную оценку). Есть ли такие константы? Ну, \({ c }_{ 2 }\), очевидно есть:

\({ c }_{ 1 }\) тоже есть. Например, \(\dfrac { 1 }{ 2 }\).

Запись \(n>2\) означает, что константа \({ n }_{ 0 }=3\). \({ n }_{ 0 }\) – целое число, справа от которого на графике \(f\left( n \right)\) всегда лежит между \({ c }_{ 1 }g\left( n \right)\) и \({ c }_{ 2 }g\left( n \right)\).

Так вот, если такое условие выполняется, то мы можем с полной уверенностью заявить, что \(g\left( n \right)\) является асимптотически точной оценкой функции \(f\left( n \right)\). В нашем случае \({ n }^{ 2 }\) является асимптотически точной оценкой \({ n }^{ 2 }-3\), или это можно записать так:

Справедливый вопрос – а почему нельзя за \(g\left( n \right)\) взять просто \({ n }^{ 2 }-3\)? На самом деле можно, но не имеет смысла. И об этом я тоже расскажу. Всё по порядку.

Примечание: \(\Theta (g\left( n \right))\) обозначает множество функций, поэтому можно также писать \(f\left( n \right)\in\Theta (g\left( n \right))\). В какой-то степени это даже правильнее, но мы при работе будем использовать знак равенства.

\(O\)-обозначения и \(\Omega\)-обозначения

«О» большое и «Омега» большое.

Теперь, после того, как мы познакомились с \(\Theta\)-обозначения, добавим к нему еще два. Итак,
Запись \(f\left( n \right)=O (g\left( n \right))\) означает, что существуют положительные константы \(c\) и \({ n }_{ 0 }\) такие, что

Вы могли догадаться, что при помощи \(O\)-обозначения мы можем описать асимптотически верхнюю границу сложности алгоритма. То есть при помощи данного обозначение можно охарактеризовать максимальную сложность алгоритма, максимальное время работы. Вкладывайте в это любой смысл, суть же, я думаю, ясна. Довольно полезно, не так ли? Это еще не все.

Теперь дальше. Запись \(f\left( n \right)=\Omega (g\left( n \right))\) означает, что существуют положительные константы \(c\) и \({ n }_{ 0 }\) такие, что

Догадались? Ну точно, \(\Omega\)-обозначение помогает нам описать асимптотически нижнюю границу. Минимальная вычислительная сложность, минимальное время, которое алгоритм гарантированно затратит на выполнение.

Давайте визуализируем всё то, что я написал до этого. На графиках я изобразил функции \({ n }^{ 2 }-3\) и \({ n }^{ 2 }\) (с соответствующими константами) для всех \(n>0\) (размер входных данных не может быть отрицательным числом).

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

Два последних обозначения, что мы рассмотрели, имеют определенные проблемы. Например, утверждение, что \({ n }^{ 2 }=O ({ n }^{ 8 })\) верное, исходя из определения O-обозначения, проверьте сами. Тем не менее, это не является точной оценкой верхней границы. Так вот, для того, чтобы показать, что данная оценка является неточной, существуют еще два обозначения.

\(o\)-обозначения и \(\omega\)-обозначения

«О» малое и «Омега» малое.

Как уже было сказано, o-обозначения используют для неточной оценки. Давайте рассмотрим чуть более формально:

Запись \(f\left( n \right)=o (g\left( n \right))\) означает, что для любой константы \(c>0\) существует константа \({ n }_{ 0 }>0\) такая,что

Главное различие \(O\)-обозначения и \(o\)-обозначения заключается в том, что в первом случае неравенство справедливо лишь для некоторой константы \(c\), во втором же – для всех \(c>0\).

Не теряем ни секунды. Запись \(f\left( n \right)=\omega (g\left( n \right))\) означает, что для любой константы \(c>0\) существует константа \({ n }_{ 0 }>0\) такая,что

То же самое, неравенство в этом случае справедливо для всех \(c>0\).

Как вы поняли, \(o\)-обозначения и \(\omega\)-обозначения характеризуют неточные верхнюю и нижнюю оценку. Ситуации, в которых нужно применять именно их, мы рассмотрим позже.

Порядок роста

Теперь давайте предположим, что есть некоторый алгоритм, который выполняется за количество шагов, описываемое следующей функцией:

При описании сложности алгоритма, нас интересует лишь то, как именно растёт время работы алгоритма при увеличении его сложности. Конечно, можно было бы взять и написать, что \(f\left( n \right) =\Theta ({ n }^{ 2 }+n)\) и по определению это было бы абсолютно верно. Тем не менее, при выборе функции, используется лишь тот член, который оказывает наибольшее влияние на рост, остальные же члены отбрасываются. Также отбрасываются и множители, которые на зависят от входных данных. Например, в записи \(2{ n }^{ 2 }\) мы с чистой совестью можем избавиться от множителя 2.

Еще раз внимательно взглянем на функцию. Можно показать, что при n, стремящимся к бесконечности:

При бесконечно больших \(n\), функция \(f\left( n \right)=n\) будет пренебрежимо мала по сравнению с \(f\left( n \right) ={ n }^{ 2 }\).

Давайте рассмотрим более доступный пример. Допустим, \(n=65536\) (с такими числами получается убедительнее). Время выполнения алгоритма в этом случае составит \({ 65536 }^{ 2 }+65536=4295032832\). Число внушительное, но если мы посмотрим, то увидим, что член \({ n }^{ 2 }\) оказывает наибольшее влияние на рост значения:

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

В свою же очередь, \({ n }^{ 2 }\) имеет наибольший порядок роста в многочлене \({ n }^{ 2 }+n\), поэтому именно его мы берём в качестве описания вычислительной сложности алгоритма.

Всё еще сомневаетесь? Хорошо, предположим, что время выполнения алгоритма задается следующей функцией:

У второго слагаемого появился серьезный шанс на победу.

Что же, выходит, всё то, что я написал, не имеет смысла? На самом деле, имеет. Увеличим \(n\) еще в 65536 раз. Дабы не утомлять вас большими числами, приведу просто соотношение:

При достаточно большом \(n\), слагаемое \({ n }^{ 2 }\) всё равно имеет больший вклад в общее время.

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

Следующая статья

Предыдущая статья