Асимптотический анализ оценки сложности алгоритмов

Для заданного алгоритма точное определение величины может быть сложно или вообще невозможно, так как:

1. Количество операторов, выполняемых алгоритмом при решении данной задачи различно в зависимости от того, какая алгоритмическая модель применяется при реализации алгоритма.

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

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

Определение.1 Пусть и – функции, определенные на некотором бесконечном множестве значений аргумента,.

Говорят, что имеет верхний порядок роста при и записывают, если.

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

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

Определение.2 Говорят, что алгоритм имеет эффективность (т.е. асимптотическую временную сложность в худшем случае) или порядка, если для него.

Пример 1. Предположим, известна точно временная сложность. Покажем, что. Согласно определению 1, выбирая и, получаем.

Неравенство верно т.к., например, – убывающая функция натурального аргумента и имеет наибольшее значение при.

Таким образом,.

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

Это оправдано, так как функция большей степени, чем константа, определяет относительное увеличение размера задачи, решаемой данным алгоритмом при увеличении ресурса времени. (см. далее пример 2 и замечание 1).

Однако, при сравнении времени работы различных алгоритмов над задачами небольшого размера n константы могут играть важную роль (см. пример 3).

Пример 2. Предположим, известны точно временные сложности алгоритмов, решающих некоторую задачу.

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

Например,.

Аналогично находится максимальный размер задачи из условия.

Таким образом, за счет десятикратного увеличения времени работы (или 10-кратного повышения быстродействия компьютера) при использовании алгоритма максимальный размер решаемой задачи увеличивается в раз.

Алгоритм

Временная сложность

Эффективность

max объём задачи решаемой за

max объём задачи

Увеличение max объема

Дата добавления: 2014-01-04