My deep learning

Обозначения в анализе алгоритмов

Теги: algorithms  time-complexity 

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

O-большое

Для функции, зависящей от длины \(n\) входных данных утверждается:

\(T(n) = O(f(n))\) тогда и только тогда, когда существуют положительные константы \(c\) и \(n_{0}\), такие что справедливо неравенство \(T(n) \leq c \times f(n)\) для всех \(n \geq n_{0}\). Иными словами, \(T(n)\) ограничена сверху функцией, кратной функции \(f(n)\)

O большое

Важно: \(c\) и \(n_{0}\) не зависят от \(n\)

\(\Omega\)-большое

\(\Omega\) имеет тот же смысл, что и \(O\), только функция, кратная \(f(n)\) ограничивает \(T(n)\) снизу. Таким образом, две нотации реализуют наихудший и наилучший случаи. \(T(n) = \Omega(f(n))\) тогда и только тогда, когда существуют положительные константы \(c\) и \(n_{0}\), такие что справедливо неравенство \(T(n) \geq c \times f(n)\) для всех \(n \geq n_{0}\).

Омега большое

\(\Theta\)-большое

\(T(n) = \Theta(f(n))\) тогда и только тогда, когда существуют положительные константы \(c_{1}\), \(c_{2}\) и \(n_{0}\), такие что справедливо неравенство \(c_{1} \times f(n) \leq T(n) \geq c_{2} \times f(n)\) для всех \(n \geq n_{0}\)

o, \(\omega\), \(\theta\)-малые

Малые нотации соответствуют большим, но при условии строго неравенества.

Также читайте про временную сложность в машинном обуче6нии и про базовые принципы временной сложности

Поделиться статьей

Все статьи с тегом algorithms

Этот проект поддерживается KonstantinKlepikov