Асимптотическая оценка вычислительной сложности

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

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

limnT(N)=limn(с (N2-N))=с N2

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

В общем виде, время выполнения любого алгоритма можно представить следующим образом:

T(N)cf(N)

При изучении свойств и сравнении алгоритмов можно отбросить константный множитель, поскольку при достаточно больших N именно порядок роста функции f(N) является определяющим фактором. Это легко объяснить на примере. Предположим имеется 2 альтернативных алгоритма, при этом первый имеет квадратичный порядок роста, а второй - описывается линейной функцией. Также допустим, что реализация первого алгоритма близка к оптимальной, а программа выполняется на современном компьютере. В то же время, реализация второго алгоритма далека от блестящей и выполняется на устаревшем компьютере. Такой дисбаланс внешних условий можно смоделировать при помощи разницы в константных множителях (пусть, c1=2, а c2=50). При небольших N, например, при 5 данных, время выполнения первого алгоритма будет меньшим времени второго:

T1(N=5)= c1N2=225=50

T2(N=5)= c2N=505=250

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

T1(N=20)= c1N2=2400=800

T2(N=20)= c2N=5020=1000

T1(N=50)= c1N2=22500=5000

T2(N=50)= c2N=5050=2500

T1(N=100)= c1N2=210000=20000

T2(N=100)= c2N=50100=5000

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

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

-оценка представляет собой сравнение с бесконечным множеством функций с одинаковым порядком роста g(N), отличающихся на константный множитель. Функция f(N) принадлежит множеству (g(N)), если имеются такие константы c1 и c2, которые при достаточно больших N сверху и снизу ограничивают функцию, описывающую скорость анализируемого алгоритма. Таким образом, выполняется следующее соотношение:

c1g(N)cf(N)c2g(N)

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

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

• линейная O(N) (время пропорционально увеличению данных);
• квадратичная O(N²);
• полиномиальная сложность O(N^M), в частности, кубическая O(N³);
• экспоненциальная сложность O(2^N);
• факториальная сложность O(N!);
• логаримфическая сложность O(log(N)) (подразумевают логарифм по основанию 2);
• линейно-логарифмическая сложность O(N * log(N)) ;
• константная вычислительная сложность O(1) (время не зависит от количества данных).

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

O(1)O(logN)O(N)O(NlogN)O(N2)O(NM)O(2N)O(N!)

Вычислительную сложность разрабатываемых алгоритмов следует максимально ограничивать, насколько это является возможным. Соотношение между данными оценками можно ощутить, представив количество выполненных инструкций на конкретных примерах, скажем при N=5, 10, 25, 100 и 500 (положим, что константные коэффициенты одинаковы для упрощения понимания). При таком объеме данных получим следующие показатели:

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

Если программа относится к научно-исследовательским, предельно допустимой сложностью является полиномиальная, в частности, кубическая O(N3). Алгоритмы с более высокой вычислительной сложностью имеют применение только для малых значений N, в противном случае задачи не имеют компьютерного решения с достижимыми вычислительными затратами.

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