Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования(Понятие и свойства алгоритма).pdf

• быть простым для понимания, перевода в программный код и отладки;
• эффективно использовать вычислительные ресурсы и выполняться по возможности быстро.^[9]

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

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

Таким образом, будем различать временную T(n) и пространственную V(n) сложности алгоритма. Чаще при рассмотрении оценок сложности используется только временная сложность.

Временная сложность алгоритма определяется количеством входных данных. Для простоты входные данные представляются параметром n. Этот параметр пропорционален величине обрабатываемого набора данных и может обозначать:

• размер массива или файла при сортировке или поиске;
• степень полинома;
• количество символов в строке;
• другую абстрактную меру объема рассматриваемой задачи.^[10]

Параметр n используется для выражения ресурсных требований программ и оценки времени их выполнения с использованием математических формул. Обычно говорят, что временная сложность алгоритма имеет порядок T(n) от входных данных размера n. Точно определить величину T(n) на практике представляется довольно трудно. Поэтому прибегают к асимптотическим отношениям с использованием O-символики.

Например, если число тактов (действий), необходимое для работы алгоритма, выражается как 1,5n2 + 7n·log n + 3n + 4, то это алгоритм, для которого T(n) имеет порядок O(n2). Фактически, порядок представляет собой показатель старшей степени многочлена.

---

При использовании обозначения O(.), имеют в виду не точное время исполнения, а только его предел сверху — верхнюю асимптотическую границу. Если, например, алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Для примера приведем числа, иллюстрирующие скорость роста для нескольких функций, которые часто используются при оценке временной сложности алгоритмов (табл. 3).

Таблица 3

Скорость роста часто используемых функций оценки

временной сложности алгоритмов

n	log n	n∙log n	n2
1	0	0	1
16	4	64	256
256	8	2 048	65 536
4 096	12	49 152	16 777 216
65 536	16	1 048 565	4 294 967 296
1 048 476	20	20 969 520	1 099 301 922 576
16775616	24	402 614 784	281 421 292 179 456

Если считать, что числа соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы O(log n) потребуется 20 микросекунд, а алгоритму со временем работы O(n2) — более 12 дней.^[11]

Если операция выполняется за фиксированное число шагов, не зависящее от количества данных, то принято писать O(1). Следует обратить внимание, что основание логарифма здесь не пишется. Причина этого весьма проста. Пусть есть O(log₂n). Но log₂n = log₃n/log₃2, а log₃2, как и любую константу, символ О() не учитывает. Таким образом, O(log₂n) = O(log₃n). К любому основанию можно перейти аналогично, а значит, и писать его не имеет смысла. Практически время выполнения алгоритма зависит не только от количества входных данных, но и от их значений, например, время работы некоторых алгоритмов сортировки значительно сокращается, если первоначально данные частично упорядочены, тогда как другие методы оказываются нечувствительными к этому свойству. Чтобы учитывать этот факт, полностью сохраняя при этом возможность анализировать алгоритмы независимо от данных, различают:

– максимальную сложность T_max (n), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего;

---

– среднюю сложность T_mid (n) – сложность алгоритма в среднем;

– минимальную сложность T_min (n) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего. ^[12]

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

1) время выполнения операций присваивания, чтения, записи обычно имеют порядок O(1). Исключением являются операторы присваивания, в которых операнды представляют собой массивы или вызовы функций;

2) время выполнения последовательности операций совпадает с наибольшим временем выполнения операции в данной последовательности (правило сумм: если T₁(n) имеет порядок O(f(n)), а T₂(n) – порядок O(g(n)), то T₁(n) + T₂(n) имеет порядок O(max(f(n), g(n)) );

3) время выполнения конструкции ветвления (if-then-else) состоит из времени вычисления логического выражения (обычно имеет порядок O(1) ) и наибольшего из времени, необходимого для выполнения операций, исполняемых при истинном значении логического выражения и при ложном значении логического выражения;

4) время выполнения цикла состоит из времени вычисления условия прекращения цикла (обычно имеет порядок O(1) ) и произведения количества выполненных итераций цикла на наибольшее возможное время выполнения операций тела цикла.

5) время выполнения операции вызова процедур определяется как время выполнения вызываемой процедуры;

6) при наличии в алгоритме операции безусловного перехода, необходимо учитывать изменения последовательности операций, осуществляемых с использованием этих операции безусловного перехода.^[13]

Таблица 4

Классы сложности алгоритмов

в зависимости от функции трудоемкости

Вид f (n)	Характеристика класса алгоритмов
1	Большинство инструкций большинства функций запускается один или несколько раз. Если все инструкции программы обладают таким свойством, то время выполнения программы постоянно
log n	Такое время выполнения обычно присуще программам, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер задачи на некоторый постоянный фактор. Изменение основания не оказывает заметного влияния на изменение значения логарифма: при n = 1 000, log10n = 3, log2n ≈ 10
n	Когда время выполнения программы является линейным, это обычно значит, что каждый входной элемент подвергается небольшой обработке
n log n	Время выполнения, пропорциональное n logn, возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения
n2	Когда время выполнения алгоритма является квадратичным, он полезен для практического использования при решении относительно небольших задач. Квадратичное время выполнения обычно появляется в алгоритмах, которые обрабатывают все пары элементов данных (возможно, в цикле двойного уровня вложенности)
n3	Похожий алгоритм, который обрабатывает тройки элементов данных (наиболее часто в цикле тройного уровня вложенности), имеет кубическое время выполнения и практически применим лишь для малых задач
2n	Лишь несколько алгоритмов с экспоненциальным временем выполнения имеют практическое применение, хотя такие алгоритмы возникают естественным образом при попытках прямого решения задачи, например полного перебора[14]

---

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

• класс Р — класс детерминированных полиномиальных алгоритмов, функция трудоемкости которых определяется от входных параметров как O (n), O (n²), O (n³) и т. д. Примеры задач, решаемых за полиномиальное время: умножение матриц, сортировка массива;
• класс L — класс детерминированных алгоритмов, использующих дополнительно O (log n) памяти;
• класс NL — класс недетерминированных алгоритмов, использующих дополнительно O (log n) памяти. Класс L  NL. Пример задачи NL — нахождение пути в графе. Задачи класса NL обычно решаются за полиномиальное время;
• класс NP — класс недетерминированных полиномиальных алгоритмов. Задача о равенстве классов Р и NP является одной из самых актуальных задач теории алгоритмов. Примером задач NP являются задача о мешке и задача коммивояжера.^[15]

Два самых больших класса алгоритмов – это алгоритмы с повторением и рекурсивные алгоритмы. В основе алгоритмов с повторением лежат циклы и условные выражения; для анализа алгоритмов требуется оценить число операций, выполняемых внутри цикла, и число итераций цикла. Рекурсивные алгоритмы разбивают большую задачу на фрагменты и применяются к каждому фрагменту по отдельности. Такие алгоритмы называются иногда «разделяй и властвуй», и их использование может оказаться очень эффективным. Термин «разделяй и властвуй», применимо к информатике, популяризовал в своей книге «Алгоритмы: построение и анализ» Томас Кормен (Thomas H. Cormen). В процессе решения большой задачи путем деления ее на меньшие создаются небольшие, простые и понятные алгоритмы. Анализ рекурсивного алгоритма требует подсчета количества операций, необходимых для разбиения задачи на части, выполнения алгоритма на каждой из частей и объединения отдельных результатов для решения задачи в целом. Объединяя эту информацию и информацию о числе частей и их размере, можно вывести рекуррентное соотношение для сложности алгоритма. Полученному рекуррентному соотношению можно придать замкнутый вид, затем сравнивать результат с другими выражениями.

---

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

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

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

Глава 3. Примеры использования алгоритмов

По типу задач мы можем выделить следующие разновидности алгоритмов:

Вычислительные алгоритмы

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

---