Понятие об оценке эффективности алгоритмов и программ

С.Н.Дроздов

Комбинаторные задачи
и элементы теории вычислительной сложности

Министерство образования российской федерации

Таганрогский государственный радиотехнический университет

С.Н.Дроздов

Комбинаторные задачи
и элементы теории вычислительной сложности

Учебное пособие

Таганрог 2000

УДК 681.142.2

С.Н.Дроздов. Комбинаторные задачи и элементы теории вычислительной сложности: Учебное пособие. Таганрог: Изд-во ТРТУ, 2000. 62с.

В пособии рассмотрено понятие комбинаторной задачи, приведены примеры таких задач, основные методы их решения и оценки эффективности алгоритмов. Рассмотрены основные понятия теории вычислительной сложности и приведены в кратком изложении основные результаты теории. Рассмотрены приемы доказательства NP-полноты и примеры NP-полных задач. Предназначено для студентов, изучающих курс «Структуры и алгоритмы обработки данных», а также для специалистов, разрабатывающих алгоритмы и программы решения дискретных задач.

Табл. 11. Библиогр.: 9 назв.

Печатается по решению редакционно-издательского совета Таганрогского государственного радиотехнического университета.

Рецензенты:

В.П.Карелин, зав.кафедрой управления и информационных систем
Таганрогского института управления и экономики,
доктор технических наук, профессор;

Д.С.Святов, главный специалист
Южно-Российского регионального кадастрового центра «Земля»;

С.А.Гитис, заведующий отделом
системного программного обеспечения ГИС
Южно-Российского регионального кадастрового центра «Земля».

© Таганрогский государственный радиотехнический университет, 2000

© Дроздов С.Н., 2000

ВВЕДЕНИЕ

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

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

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

При разработке пособия автор использовал книги, перечисленные в списке литературы. Некоторые примеры также позаимствованы из этих книг.

Методы решения комбинаторных задач

Понятие об оценке эффективности алгоритмов и программ

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

Возможны два подхода к оценке эффективности программ: эмпирический (экспериментальный) и теоретический. Экспериментальный подход заключается в тестировании программы на разнообразных примерах и получении статистических оценок эффективности. Преимущество этого подхода заключается в получении предельно конкретных, числовых результатов, например: «Программа работает от 5 до 10 секунд для массива из 10000 чисел». Недостаток – в невозможности разделить влияние очень разных факторов, от которых может зависеть время работы программы. К таким факторам относятся: качество алгоритма, качество программирования, эффективность используемого компилятора, производительность процессора, объем имеющегося ОЗУ, конфигурация операционной системы, размер обрабатываемого массива данных, конкретные значения данных и т.п. В результате бывает очень трудно применить полученные оценки, если изменился хотя бы один из факторов.

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

Теоретические оценки производительности чаще всего выражаются в виде оценок скорости роста времени работы алгоритма в зависимости от числа элементов обрабатываемого массива данных «с точностью до O-большого». Что это такое?

Дадим определение. Пусть f(n) и g(n) – вещественные функции целочисленного аргумента. Говорят, что f(n) = O(g(n)) (читается: «f(n) есть O-большое от g(n)»), если существуют такое вещественное число C > 0 и такое целое N, что для всех n > N имеет место: |f(n)/g(n)| < C. Другими словами, при n ® ¥ функция f(n) растет «не быстрее», чем g(n), а вернее сказать, если и быстрее, то отношение этих функций остается ограниченным, а не стремится к бесконечности.[1]

Что дает использование O-большого для построения оценок? Допустим, f(n) – некоторая сложная, может быть даже не вполне точно известная функция, выражающая время работы алгоритма как функцию размерности задачи. Если мы сумеем подобрать подходящую более простую функцию g(n) и докажем, что f(n) = O(g(n)), то такая оценка будет не слишком точна, но будет достаточно хорошо показывать, как ведет себя алгоритм при увеличении размерности задачи.

Говорят, например: «Данный алгоритм имеет оценку O(n²)». Это означает, что при увеличении размера массива данных n, к примеру, в 10 раз, время работы алгоритма возрастает примерно в 102= 100 раз. При этом следует различать оценки максимального времени Tмакс(n) (т.е. для случая самых неудачных для этого алгоритма данных) и среднего времени Tср(n) (т.е. математического ожидания времени работы для случайного набора данных). Величину Tмакс(n) называют также вычислительной сложностью алгоритма.

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

Весьма полезным свойством оценок «до O-большого» является возможность значительного упрощения выражений без потери правильности оценки. В частности:

· Если f(n) = O(k×g(n)), где k – ненулевая константа, то f(n) = O(g(n)) (т.е. постоянный множитель можно отбрасывать).

· Если f(n) = O(g₁(n)+g₂(n)) и g₂(n)/g₁(n) ® 0, то f(n) = O(g₁(n)) (т.е. можно оставлять только главный член выражения).

Отметим ради строгости, что запись O(g(n)) на самом деле означает не конкретную функцию, а множество всех функций, растущих не быстрее, чем g(n). В записи «f(n) = O(g(n))» было бы логичнее использовать не знак равенства, а знак принадлежности «Î», однако общепринята запись с равенством. Нельзя, однако, читать это: «f(n) равно O-большому от g(n)», правильно «есть O-большое».

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

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

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

· Если в алгоритме предусматривается разложение задачи размерности n на k подзадач размерности n-1, затем разложение каждой из подзадач на k подзадач размерности n-2 и т.д., то алгоритм будет иметь экспоненциальную оценку O(kⁿ).

· Если в задаче требуется найти некоторый элемент из множества мощности n и на каждом шаге алгоритма удается сократить множество поиска вдвое, то алгоритм будет иметь логарифмическую оценку O(log₂(n)). Заметим кстати, что в оценках типа O-большое основание логарифма не играет роли (поскольку логарифмы по разным основаниям различаются лишь постоянным множителем), поэтому обычно пишут просто O(log(n)).

· Несколько более сложный, но важный случай: если каждый шаг алгоритма сводится к однократному просмотру множества из n элементов и затем повторению такого же шага для каждой из двух половин этого множества (т.е. T(n) = n + 2T(n/2)), то такой алгоритм имеет оценку O(n×log(n)).

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