Понятие вычислительной сложности

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

Существует несколько факторов, влияющих на время, необходимое для выполнение программы:

1. Объем входных данных.
2. Уровень оптимизации кода компилятором.
3. Производительность компьютерной системы.
4. Вычислительная сложность алгоритма

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

Фактор №2 имеет медленную тенденцию к улучшению, средства автоматизации постепенно совершенствуются с годами. Переход на новую версию компилятора либо на совсем другой компилятор, реализующий более удачную стратегию низкоуровневой оптимизации программного кода, может улучшить производительность программ в 1.5-5 раз.

Проблемы с фактором №3 могут быть решены приобретением более дорогого и совершенного компьютера. Аппаратные технологии постоянно развиваются. За счет перехода на более производительный процессор, более быструю оперативную память, другую архитектуру кэш-памяти и других подобных аппаратных улучшений, можно повысить производительность элементарных вычислительных инструкций в 10-100 раз. Следует отметить, что в конкретный момент времени всегда имеется конечный предел производительности компьютеров, доступных на рынке, кроме того, наиболее мощные компьютеры будут иметь самую высокую стоимость.

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

Учитывая степень влияния свойств алгоритмов на итоговое быстродействие программ, очевидна необходимость в понимании характеристик их быстродействия. Простейшим способом достижения такого понимания является измерение. Одним из базовых путей измерения времени выполнения программ (или их фрагментом) является использование функции clock() из стандартной библиотеки языка C. Данная функция возвращает количество некоторых условных единиц процессорного времени, прошедших момента запуска процесса. Чаще всего в качестве такой единицы используются миллисекунды. Абсолютное значение, возвращаемое этой функцией, говорит мало о чем, для измерения времени выполнения нужно использовать разницу между двумя значениями. Для перевода измеренного интервала в секунды, разницу между двумя значениями, возвращенными функцией clock, следует поделить на константу CLOCKS_PER_SEC:

#include <ctime>

#include <iostream>

intmain ()

{

// Фиксируем начальный момент времени

clock_t clock1 = clock();

// Некоторый программный код, решающий интересующую задачу

// …

// Фиксируем конечный момент времени

clock_t clock2 = clock();

// Пересчитываем зафиксированный временной интервал в секундах

doubletimeInSec = ( ( double) ( clock2 - clock1 ) / ( double) CLOCKS_PER_SEC );

std::cout << “Time: “ << timeInSec << “ sec” << std::endl;

}

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

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

Аналитический подход должен исключать из рассмотрения факторы, не связанные с сутью реализуемых алгоритмов (свойства компьютерной системы и особенности работы компилятора). Соответственно рассуждение строится на предположении, что все элементарные выражения и инструкции выполняются за некоторое условное одинаковое единичное время. Целью анализа свойств алгоритма является оценка ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ - зависимости между количеством элементарных инструкций, выполняющихся алгоритмом на некотором идеализированном компьютере, от объема поданных входных данных.

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

voidbubbleSort ( int* _pData, int_N )

{

for( inti = 0; i < _N - 1; i++ ) // (1)

for( intj = _N - 1; j > i; j-- ) // (2)

if( _pData[ j - 1 ] > _pData[ j ] ) // (3)

{

inttemp = _pData[ j - 1 ]; // (4)

_pData[ j - 1 ] = _pData[ j ]; // (5)

_pData[ j ] = temp; // (6)

}

}

Время выполнения алгоритма зависит от количества выполняемых элементарных инструкций, что можно оценить аналитически. Внешний цикл (1-6) выполняется ровно N - 1 раз. Внутренний цикл (2-6) выполняется N - 1 раз на первой итерации внешнего цикла, затем N - 2 на второй итерации, и количество его запусков уменьшается на единицу с каждой новой итерацией. При анализе условия (3-6) в худшем случае, когда массив изначально отсортирован в обратном порядке, результат проверки (3) будет справедливым каждый раз, что запустит последовательность элементарных инструкций (4-6). Таким образом, общее время выполнения пузырьковой сортировки определяется следующей зависимостью:

T(N)=( N-1 )T3-6+(N-2)T3-6+(N-3)T3-6+... +T3-6

Раскрыв скобки и упростив данный ряд, получим:

T(N)=T3-6(( N-1 )+(N-2)+(N-3) + ... +1)=T3-6 (N-1)1+(N-1)2=T3-6 0,5( N2-N )

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

T(N)=с (N2-N)

где с - некоторый константный множитель.

В лучшем случае, когда исходный массив уже отсортирован в нужном порядке, характер зависимости принципиально не изменится. В такой удачной ситуации блок (4-6) не будет выполнен ни разу, и время будет определяться количеством сравнений при выполнении условия (3). Это заметно уменьшит значение константного множителя с, но не повлияет на форму зависимости.

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

intfind ( const IntegerVector & _v, int _value )

{

intp = 0; // 1

while ( p < _v.m_nUsed ) // 2

{ // 3

if( _v.m_pData[ p ] == _value ) // 4

returnp; // 5

++p; // 6

}

return-1; // 7

}

Строки (1) и (7) выполняются не более 1 раза, соответственно их можно исключить из рассмотрения. Худшим случаем для данного алгоритма является отсутствие искомого значения в последовательности. Цикл (2-6) в худшем случае выполнится N раз, где N - длина последовательности. Тело цикла состоит из элементарных инструкций, при чем условие (4) в худшем случае никогда не выполнится. Лучший случай - это обнаружение искомого значения при первом же сравнении. В среднем функция будет выполнять N/2 итераций основного цикла.

T(N)=с N

Соответственно, вычислительная сложность данной функции характеризуется как линейная, что вытекает из количества итераций основного цикла. В связи с этим фактом, описанный алгоритм часто называют алгоритмом ЛИНЕЙНОГО ПОИСКА (linear search),