МАТЕМАТИЧЕСКИЕ ОСНОВЫ
АНАЛИЗ СЛОЖНОСТИ И СИСТЕМА ОБОЗНАЧЕНИЙ
Специалистам в области компьютерных наук часто приходится решать задачу сравнения алгоритмов для определения того, насколько быстро они действуют или сколько памяти для них требуется. Для решения этой задачи предусмотрены два подхода. Первым из них является применение эталонных тестов — прогон реализующих алгоритмы программ на компьютере и измерение быстродействия в секундах и потребления памяти в байтах. Верно, что в конечном итоге нас действительно интересуют именно такие практические характеристики, но эталонное тестирование может оказаться неприемлемым потому, что оно слишком узко направлено, — в нем измеряется производительность конкретной программы, написанной на конкретном языке, функционирующей на конкретном компьютере с конкретным компилятором и с конкретными входными данными. К тому же на основании единственного результата, полученного с помощью эталонного тестирования, трудно предсказать, насколько успешно этот алгоритм будет действовать в случае использования другого компилятора, компьютера или набора данных.
Асимптотический анализ
Второй подход опирается на математический анализ алгоритмов, независимый от конкретной реализации и входных данных. Рассмотрим этот подход на приведенном ниже примере программы, которая вычисляет сумму последовательности чисел (листинг A. 1).
Листинг А. 1. Программа вычисления суммы последовательности чисел
function Summation(sequen се) returns сумма sum sum <— 0
for i <— 1 to Length (sequence) sum <— sum + sequence[i] return sum
Первый этап анализа состоит в том, что создается определенное абстрактное представление входных данных, позволяющее найти какой-то параметр (или параметры), который характеризует объем входных данных. В рассматриваемом примере объем входных данных можно охарактеризовать с помощью такого параметра, как длина последовательности, которая будет обозначаться как п. На втором этапе необходимо определить абстрактное представление реализации и найти какой-то критерий, отражающий продолжительность прогона алгоритма, но не привязанный к конкретному компилятору или компьютеру. Применительно к программе Summation этим критерием может служить количество строк выполняемого кода; кроме того, данный критерий может быть более детализированным и измеряющим количество сложений, присваиваний, обращений к элементам массивов, а также ветвлений, выполняемых в этом алгоритме. В любом случае будет получена характеристика общего количества шагов, выполняемых алгоритмом, как функция от объема входных данных. Обозначим эту характеристику как т(п). Если за основу берется количество строк кода, то в данном примере Т[п) =2п+2.
Если бы все программы были такими же простыми, как Summation, то область анализа алгоритмов не заслуживала бы названия научной. Но исследования в этой области существенно усложняются из-за наличия двух проблем. Первая проблема заключается в том, что редко удается найти параметр, подобный т(п), который полностью характеризует количество шагов, выполняемых в алгоритме. Вместо этого обычно можно самое большее вычислить этот показатель для наихудшего случая Tworst (п) или для среднего случая Tavg (п). А для вычисления среднего требуется, чтобы аналитик принял какие-то обоснованные предположения по распределению наборов входных данных.
Вторая проблема состоит в том, что алгоритмы обычно не поддаются точному анализу. В этом случае приходится прибегать к аппроксимации и использовать, например, такую формулировку, что быстродействие алгоритма Summation характеризуется величиной О(п). Это означает, что быстродействие алгоритма измеряется величиной, пропорциональной п, возможно, за исключением нескольких небольших значений п. Более формально это определение можно представить с помощью следующей формулы:
Т(п) равно 0(f{n)), если Т(п) < kf(n) для некоторого к, при всех п > по
Перейдя к использованию системы обозначений 0(), мы получаем возможность воспользоваться так называемым асимптотическим анализом. А в рамках этого подхода можно, например, безоговорочно утверждать, что если п асимптотически приближается к бесконечности, то алгоритм, характеризующийся показателем О(п), проявляет себя лучше по сравнению с алгоритмом О (л2), тогда как единственное число, полученное с помощью эталонного тестирования, не может служить обоснованием подобного утверждения.
Система обозначений О () позволяет создать абстрактное представление, в котором не учитываются постоянные коэффициенты, благодаря чему она становится более простой в использовании, но менее точной, чем система обозначений т[). Например, в конечном итоге алгоритм 0{п2) всегда будет считаться худшим по сравнению с алгоритмом О(п), но если бы эти два алгоритма характеризовались значениями Т(л2+1) и Т( 100л+1000), то фактически алгоритм 0{п2) был бы лучше при л<110.
Несмотря на этот недостаток, асимптотический анализ представляет собой инструментальное средство, наиболее широко используемое для анализа алгоритмов. Этот метод можно считать достаточно точным, поскольку в процессе анализа создается абстрактное представление и для точного количества операций (поскольку игнорируется постоянный коэффициент к), и для точного содержимого входных данных (поскольку рассматривается исключительно их объем л); благодаря этому анализ становится осуществимым с помощью математических методов. Система обозначений О () представляет собой хороший компромисс между точностью и простотой анализа.