Эффективность алгоритма зависит от количества времени, памяти и других ресурсов, необходимых для его выполнения. Эффективность измеряется с помощью асимптотических обозначений. Алгоритм может иметь разную производительность для разных типов входных данных. С увеличением размера входных данных производительность изменится. Изучение изменения производительности алгоритма с изменением порядка размера входных данных определяется как асимптотический анализ.
Термин «асимптота» происходит от др.-греч. ἀσύμπτωτος и обозначает в упрощенном виде прямую, которая неограниченно приближается к бесконечной кривой, но не пересекает ее. Таким образом, асимптотический анализ — это метод описания предельного поведения чего-либо, в данном случае алгоритмов.
Асимптотические обозначения
Асимптотические обозначения — это математические обозначения, используемые для описания времени выполнения алгоритма, когда входные данные стремятся к определенному или ограничивающему значению.
Например, в сортировке пузырьком, когда входной массив уже отсортирован, время, затраченное алгоритмом для сортировки, является линейным — это лучший случай. Однако, когда входной массив находится в обратном состоянии (задом наперед), алгоритм занимает максимальное время (квадратичное) для сортировки элементов — это худший случай. Когда входной массив не отсортирован и не находится в обратном порядке, тогда требуется среднее время для выполнения сортировки. Эти продолжительности обозначаются с помощью асимптотических обозначений.
Существуют главным образом три асимптотических обозначения:
Big-O нотация
Omega нотация
Theta нотация
Big-O нотация (O нотация)
Нотация большого O обозначает верхнюю границу времени выполнения алгоритма. Таким образом, она указывает на сложность алгоритма в худшем случае.
Big-O дает верхнюю границу функции
|
1 2 |
O(g(n)) = { f(n): существуют положительные константы c и n0 такие, что 0 ≤ f(n) ≤ cg(n) для всех n ≥ n0 } |
Это выражение может быть описано как функция f(n) принадлежит множеству O(g(n)), если существует положительная константа c, такая что функция находится между 0 и cg(n) для достаточно больших значений n.
Для любого значения n время выполнения алгоритма не превышает времени, указанного в O(g(n)).
Поскольку нотация дает время выполнения алгоритма в худшем случае, она широко используется для анализа алгоритма, поскольку наихудший сценарий всегда всех интересует.
Omega нотация (Ω-нотация)
Омега нотация — представляет нижнюю границу времени выполнения алгоритма. Таким образом, она указывает на сложность алгоритма в лучшем случае.
Omega дает нижнюю границу функции
|
1 2 |
Ω(g(n)) = { f(n): существуют положительные константы c и n0 такие что 0 ≤ cg(n) ≤ f(n) для всех all n ≥ n0 } |
Это выражение может быть описано как функция f(n) принадлежит множеству Ω(g(n)), если существует положительная константа c, такая что функция находится выше cg(n) для достаточно больших значений n.
Для любого значения n минимальное время, необходимое для выполнения алгоритма, определяется нижней границей Omega Ω(g(n)).
Theta нотация (Θ-нотация)
Theta-нотация (Θ-нотация) ограничивает функцию сверху и снизу. Поскольку она представляет верхнюю и нижнюю границы времени выполнения алгоритма, то используется для анализа среднего случая сложности алгоритма.
Theta ограничивает функцию константными множителями
Для функции g(n), Θ(g(n)) определяется следующим образом:
|
1 2 |
Θ(g(n)) = { f(n): существуют положительные константы c1, c2 и n0 такие что 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) для всех n ≥ n0 } |
Следующее выражение может быть описано как функция f(n) принадлежит множеству Θ(g(n)), если существуют положительные константы c1 и c2, такие что функция находится между c1g(n) и c2g(n) при достаточно больших n.
Если функция f(n) находится где-то между c1g(n) и c2g(n) для всех n ≥ n0, то говорят, что f(n) имеет асимптотически точную границу.
Оценить статью:
Загрузка...