Структуры данных: асимптотический анализ

Предыдущая часть: “Структуры данных: основы алгоритмов”

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

Асимптотический анализ связан c входными данными: если их нет, алгоритм работает за постоянное время. Все остальные факторы, кроме входных данных, считаются постоянными.

Асимптотический анализ имеет дело с вычислением времени выполнения любой операции в математических единицах. Так, если время выполнения одной операции вычисляется как f(n), а другой — как g(n2), значит, время выполнения первой операции по мере роста n увеличивается линейно, а второй — экспоненциально. И если значение n ничтожно мало, время выполнения обеих операций почти одинаково.

Обычно выделяют три времени выполнения алгоритма:

• в лучшем случае, т. е. минимальное время, требующееся для выполнения программы;
• в среднем случае, т. е. среднее время, требующееся для выполнения программы;
• в худшем случае, т. е. максимальное время, требующееся для выполнения программы.

Асимптотические обозначения

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

• ? нотация;
• ? нотация;
• ? нотация.

Нотация «O» большое , O

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

Например, для функции f(n)

?(f(n)) = {g(n), где существует c > 0 и n0 такие, что f(n) <= c.g(n) для всех n > n0.}

Омега-нотация, ?

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

Например, для функции f(n)

?(f(n)) >= {g(n), где существует c > 0 и n0 такие, что g(n) <= c.f(n) для всех n > n0.}

Тета-нотация, ?

Обозначение ?(n) — это формальный способ определения нижней и верхней границ времени выполнения алгоритма. Выглядит она так:

?(f(n)) = {g(n) тогда и только тогда, когда g(n) = ?(f(n)) и g(n) = ?(f(n)) для всех n > n0.}

Часто встречающиеся асимптотические обозначения

Вот список самых распространенных асимптотических обозначений:

Читайте также:

• Что такое «O» большое в программировании?
• 8 показателей эффективности классификации
• 6 принципов создания производительных веб-приложений

Источник: m.vk.com

Комментарии: