Асимптотический анализ

В этой статье вы узнаете, что такое асимптотические нотации, познакомитесь с О-нотацией, нотациями Тета и Омега.  

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

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

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

Асимптотические нотации

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

Возьмем, к примеру, сортировку пузырьком. Когда массив, который мы вводим, уже отсортирован, время выполнения алгоритма линейно — это лучший случай.

Но если массив отсортирован в обратном порядке, то время выполнения будет максимальным (квадратичное). То есть, это худший случай. 

Если входной массив не находится в этих двух состояниях, то время выполнения алгоритма среднее. Длительность выполнения алгоритма описывается асимптотическими нотациями. 

В основном используются три нотации:

• большое «О»,
• омега-нотация,
• тета-нотация.  

Большое «О»

Большое «О» — это верхняя граница скорости выполнения алгоритма. Эта нотация показывает скорость алгоритма в худшем случае.

O(g(n)) = { f(n): существуют такие константы c и n0,
            что 0 ≤ f(n) ≤ cg(n) для любых n ≥ n0 }

Это выражение — описание функции f(n). Она принадлежит множеству O(g(n)), если существует положительная константа c, при которой f(n) лежит в промежутке от 0 до cg(n) при достаточно больших n. 

Для любого n функция времени выполнения алгоритма не пересечет функцию O(g(n)).

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

Чтобы прочувствовать, что стоит за записями O(n) и O(log n), запустите блок-схему ниже. Она сравнивает две стратегии: перебор всех чисел от 1 до n по одному и многократное деление n пополам. Введите 16, затем 64 — и посмотрите, как растет число шагов в каждом случае.

n = int(input())
ops = 0
i = 1
while i <= n:
    ops = ops + 1
    i = i + 1
print("Перебор по одному:", ops, "шагов")
k = n
halvings = 0
while k > 1:
    k = k // 2
    halvings = halvings + 1
print("Деление пополам:", halvings, "шагов")

При n = 64 перебор делает 64 шага, а деление пополам — всего 6. Это и есть разница между линейной сложностью O(n) и логарифмической O(log n), которую описывают асимптотические нотации.

Омега нотация (Ω-нотация)

Омега нотация — противоположность большому «О». Она показывает нижнюю границу скорости выполнения алгоритма. Она описывает лучший случай выполнения алгоритма.

Ω(g(n)) = { f(n): существуют такие положительные константы c и n0, 
            что 0 ≤ cg(n) ≤ f(n) для всех n ≥ n0 }

Это выражение — описание функции f(n). Она лежит в множестве Ω(g(n)), если существует такая положительная константа c, при которой f(n) лежит выше cg(n) при достаточно больших n. 

Для любого n минимальное время выполнения алгоритма задается как Ω(g(n)).

Тета-нотация (Θ-нотация)

Тета-нотация объединяет в себе сразу две функции — верхнюю и нижнюю. Эта нотация отражает и верхнюю, и нижнюю границу скорости выполнения алгоритма. Именно поэтому она используется для анализа средней скорости выполнения алгоритма.

Для функции g(n) Θ(g(n)) задается следующим образом:

Θ(g(n)) = { f(n): существуют такие положительные константы c1, c2 и n0,
            что 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) для любых n ≥ n0 }

Это выражение — описание функции f(n). Она принадлежит множеству Θ(g(n)), если существуют положительные константы с1 и с2 такие, что f(n) лежит между c1g(n) и c2g(n) при достаточно больших n.