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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, .

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

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