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

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

Skillfactory.ru

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

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

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

Skillfactory.ru

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

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

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

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

  • Ο нотация;
  • Ω нотация;
  • θ нотация.

Нотация «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.}

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

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

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

Читайте нас в TelegramVK и Яндекс.Дзен

Предыдущая статьяРегулярные выражения в Python: необходимый запас знаний
Следующая статьяСтруктуры данных: «жадные» алгоритмы