Предыдущая часть: “Структуры данных: основы алгоритмов”
Асимптотический анализ алгоритма — это определение математических границ/рамок его производительности во время выполнения, позволяющее очень легко находить время работы алгоритма в лучшем, среднем и худшем случае.
Асимптотический анализ связан 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 принципов создания производительных веб-приложений
Читайте нас в Telegram, VK и Яндекс.Дзен
