В этом руководстве вы узнаете, что такое асимптотические обозначения. Кроме того, вы узнаете о нотации Big-O, тета-нотации и нотации Omega.
Эффективность алгоритма зависит от количества времени, памяти и других ресурсов, необходимых для выполнения алгоритма. Эффективность измеряется с помощью асимптотических обозначений.
Алгоритм может не иметь одинаковой производительности для разных типов входных данных. С увеличением размера входа производительность изменится.
Исследование изменения производительности алгоритма с изменением порядка размера входных данных определяется как асимптотический анализ.
Асимптотические обозначения
Асимптотические обозначения - это математические обозначения, используемые для описания времени работы алгоритма, когда входные данные стремятся к определенному значению или предельному значению.
Например: в пузырьковой сортировке, когда входной массив уже отсортирован, время, затрачиваемое алгоритмом, является линейным, т.е. в лучшем случае.
Но когда входной массив находится в обратном состоянии, алгоритму требуется максимальное время (квадратичное) для сортировки элементов, т.е. в худшем случае.
Когда входной массив не отсортирован и не в обратном порядке, это занимает среднее время. Эти длительности обозначаются с помощью асимптотических обозначений.
В основном используются три асимптотических обозначения:
- Обозначение Big-O
- Обозначение омега
- Обозначение тета
Нотация Big-O (O-нотация)
Обозначение Big-O представляет верхнюю границу времени работы алгоритма. Таким образом, это дает наихудшую сложность алгоритма.
Big-O дает верхнюю границу функции
O (g (n)) = (f (n): существуют положительные константы c и n 0 такие, что 0 ≦ f (n) ≦ cg (n) для всех n ≧ n 0 )
Вышеупомянутое выражение можно описать как функцию, f(n)принадлежащую набору, O(g(n))если существует положительная константа cтакая, что она находится между 0и cg(n), для достаточно больших n.
При любом значении nвремя работы алгоритма не пересекает время, указанное в O(g(n)).
Поскольку он дает время работы алгоритма в наихудшем случае, он широко используется для анализа алгоритма, поскольку нас всегда интересует наихудший сценарий.
Обозначение Омега (Ω-обозначение)
Обозначение омега представляет собой нижнюю границу времени работы алгоритма. Таким образом, он обеспечивает наилучшую сложность алгоритма.
Омега дает нижнюю границу функции
Ω (g (n)) = (f (n): существуют положительные константы c и n 0 такие, что 0 ≦ cg (n) ≦ f (n) для всех n ≧ n 0 )
Вышеупомянутое выражение можно описать как функцию, f(n)принадлежащую множеству, Ω(g(n))если существует положительная константа cтакая, что она лежит выше cg(n), для достаточно больших n.
Для любого значения nминимальное время, необходимое алгоритму, определяется Omega Ω(g(n)).
Обозначение тета (Θ-обозначение)
Обозначение тета включает функцию сверху и снизу. Поскольку он представляет собой верхнюю и нижнюю границу времени работы алгоритма, он используется для анализа средней сложности алгоритма.
Тета ограничивает функцию в пределах постоянных факторов
Для функции g(n), Θ(g(n))задается соотношением:
Θ (g (n)) = (f (n): существуют положительные константы c 1 , c 2 и n 0 такие, что 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) для всех п ≧ п 0 )
Вышеупомянутое выражение может быть описано как функция, f(n)принадлежащая набору, Θ(g(n))если существуют положительные константы и такая, что она может быть зажата между и , для достаточно большого n.c1c2c1g(n)c2g(n)
Если функция f(n)находится где-то посередине и для всех , она называется асимптотически жесткой связью.c1g(n)c2g(n)n ≧ n0f(n)
