Поверхностная оценка вычислительной сложности

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

Ниже приведено несколько подсказок для поверхностной оценки вычислительной сложности “”на глаз” без строгого аналитического подхода.

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

2. Вычислительная сложность последовательности инструкций равна максимальной сложности входящих в нее инструкций.

T1,2,..k(N)=max(T1(N),T2(N),...,Tk(N)), k2

3. Если нет никаких специальных сведений о вероятности срабатывания условных переходов, то все возможные условные переходы, в том числе неявные (опущенные ветки else, default), следует считать равновероятными. Сложность каждого блока инструкций оценивается отдельно, а затем выбирается максимальная из них, что и становится результатом оценки для условной конструкции в целом.

4. Если инструкция находится в теле цикла, количество итераций которого зависит от N, то вычислительная сложность инструкции умножается на линейную функцию.

5. Вычислительная сложность двух циклов, зависящих от N, вложенных друг в друга, скорее всего описывается квадратичной функцией. Соответственно, вложенность из 3 уровней соответствует кубической сложности.

6. Если алгоритм разбивает набор входных данных на части, а затем обрабатывает их отдельно тем же самым алгоритмом рекурсивно - вычислительная сложность является логарифмической.

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

intfactorial ( int_x )

{

if( _x < 1 )

return0;

else if( _x == 1 )

return1;

Else

return_x * factorial( _x - 1 );

}

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

T(N)=T(N-1) +1, N>1

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

T(N)=T(N-1) +1= (T(N-2) +1)+1=((T(N-3)+1)+1)+1=N

T(N)=O(N)

Бинарный поиск

Еще одним из известных рекурсивных алгоритмов является БИНАРНЫЙ ПОИСК. Если организовать хранение данных таким образом, что пары ключ-значение хранятся в виде массива, а также изначально отсортированы по возрастанию ключей, представляется возможным существенно повысить быстродействие процедуры поиска элемента множества или отображения по сравнению с простейшим линейными поиском. Безусловно, сортировка данных занимает ощутимое время. Однако программист может столкнуться с ситуацией, когда необходимо обрабатывать уже отсортированные кем-то данные, получаемые, например, из внешнего источника - дискового файла или базы данных - в уже упорядоченном виде.

Пусть имеется заранее упорядоченное по алфавиту множество названий государств, входящих в Шенгенскую зону:

const char* constg_SchengenCountries [] = {

“Austria”

, “Belgium”

, “Czech Republic”

, “Denmark”

, “Estonia”

, “Finland”

, “France”

, “Germany”

, “Greece”

, “Hungary”

, “Iceland”

, “Italy”

, “Latvia”

, “Liechtenstein”

, “Lithuania”

, “Luxembourg”

, “Malta”

, “Netherlands”

, “Norway”

, “Poland”

, “Portugal”

, “Slovakia”

, “Slovenia”

, “Spain”

, “Sweden”

, “Switzerland”

};

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

boolisSchengenCountry ( const char* _country )

{

intminIndex = 0;

intmaxIndex = sizeof( g_SchengenCountries ) / sizeof( const char* );

while( minIndex < maxIndex )

{

intmidIndex = ( minIndex + maxIndex ) >> 1;

intcmpResult = strcmp( _country, g_SchengenCountries[ midIndex ] );

if( ! cmpResult )

return true;

else if( cmpResult < 0 )

maxIndex = midIndex;

Else

minIndex = midIndex + 1;

}

return false;

}

Предположим, происходит вызов данной функции с аргументом “Finland”. Пошаговое выполнение алгоритма бинарного поиска выглядит следующим образом:

1. На первом шаге интервал поиска составляет 26 стран от индекса 0 до индекса 25 включительно. Первое сравнение происходит со страной с индексом 13, а именно с “Liechtenstein”. По алфавиту искомая страна “Finland” идет раньше, чем “Liechtenstein”, соответственно поиск продолжается в первой половине массива.
2. На втором шаге интервал поиска составляет 13 стран от индекса 0 до индекса 12 включительно. Следующее сравнение происходит со страной с индексом 6, т.е. “France”. Искомая страна “Finland” также раньше по алфавиту, и поиск переходит в первую четверть.
3. На третьем шаге интервал поиска составляет 6 стран от индекса 0 до индекса 5 включительно. Значение, которое берется для сравнения - “Denmark” с индексом 3. На этот раз поиск будет продолжен во второй половине текущего интервала.
4. На четвертом шаге интервал поиска сужается до 2 стран от индекса 4 до индекса 5 включительно. Сравнение происходит со строкой “Finland” по индексу 5, таким образом образуется итоговый утвердительный ответ.

Вычислительная сложность данной функции оценивается как O(log N), поскольку на каждом шаге алгоритма отсекается половина неправильных результатов. Более строго это можно вывести исходя из рекуррентного соотношения:

T(N)=T(N/2)+1

Соотношение имеет указанную форму, поскольку на каждом шаге алгоритма решается аналогичная задача на вдвое меньшем объеме данных. При этом на каждом шаге дополнительно выполняется некоторая элементарная вычислительная работа, в частности, сравнение искомого ключа и ключа в середине массива, а затем выбор следующего интервала в зависимости от результата сравнения. Раскрыть данное рекуррентное соотношение с целью получения оценки вычислительной сложности можно при помощи подстановки N=2M, где M - некоторое целое число, степенью двойки которого является N. Несмотря на то, что такая подстановка несправедлива в общем случае, т.к. N не обязан являться степенью двойки в каждой задаче, такое предположение можно заложить, представив, что исходный набор данных дополняется до ближайшей степени двойки сверху ненужными значениями, например, нулями. Осуществим задуманную подстановку и начнем раскрытие рекурсии поэтапно:

T(2M)=T(2M/2)+1=T(2M-1)+1=T(2M-2)+1+1=T(2M-3)+1+1+1=...=M

T(2M)=MT(N)=log2(N)

Из логарифмической вычислительной сложности вытекает, что в худшем случае поиск интересующей страны в составе стран Шенгенской зоны потребует не более 5 сравнений строк. Худшим случаем для данного алгоритма является поиск значения, отсутствующего в наборе. 5 сравнений - это значительно лучше, чем 26 сравнений в худшем случае при линейном поиске.