Оценка вычислительной сложности алгоритма

Сложность алгоритма по памяти

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

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

Спрос на компьютерную память велик, поэтому и важен вопрос, какие данные необходимо хранить, а также эффективные способы хранения. Проиллюстрируем сказанное на примере. Предположим, что производится запись вещественного числа из сегмента [-10,10], имеющего один десятичный знак после запятой. При записи вещественного числа большинство компьютеров потратит от 4 до 8 байтов памяти. Однако если предварительно умножить число на 10, то для хранения полученного целого числа из сегмента [-100,100] потребуется всего 1 байт.

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

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

 

Подсчет вычислительной сложности алгоритма состоит из двух основных шагов:

Шаг 1. Выбор значимой операции или группы операций.

Шаг 2. Определение, какие из выбранных операций содержатся в теле алгоритма, а какие составляют накладные расходы или уходят на регистрацию и учет данных.

В качестве значимых часто (но не обязательно) выступают операции двух типов:

• Сравнение,
• Арифметические операции.

Арифметические операции разбиваются на две группы:

• Аддитивные,
• мультипликативные.

Аддитивные операторы (сложения) включают сложение, вычитание, увеличение и уменьшение счетчика.

Мультипликативные операторы (умножения) включают умножение, деление, взятие остатка по модулю.

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

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