Учебники

Структуры данных – асимптотический анализ

Асимптотический анализ алгоритма относится к определению математического ограничения / формирования его производительности во время выполнения. Используя асимптотический анализ, мы можем очень хорошо заключить наилучший, средний и худший сценарии алгоритма.

Асимптотический анализ связан с входными данными, т. Е. Если нет входных данных для алгоритма, считается, что он работает в постоянное время. Кроме «входных» все остальные факторы считаются постоянными.

Асимптотический анализ относится к вычислению времени выполнения любой операции в математических единицах вычисления. Например, время выполнения одной операции вычисляется как f (n) и может быть для другой операции оно вычисляется как g (n 2 ). Это означает, что время выполнения первой операции будет линейно увеличиваться с увеличением n, а время выполнения второй операции будет увеличиваться экспоненциально при увеличении n . Точно так же время выполнения обеих операций будет почти одинаковым, если n значительно мало.

Обычно время, требуемое алгоритмом, подразделяется на три типа:

  • Лучший вариант – минимальное время, необходимое для выполнения программы.

  • Средний случай – среднее время, необходимое для выполнения программы.

  • В худшем случае – максимальное время, необходимое для выполнения программы.

Лучший вариант – минимальное время, необходимое для выполнения программы.

Средний случай – среднее время, необходимое для выполнения программы.

В худшем случае – максимальное время, необходимое для выполнения программы.

Асимптотические обозначения

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

  • Ο Обозначение
  • Обозначение
  • θ нотация

Большая О Нотация, Ο

Обозначение Ο (n) является формальным способом выражения верхней границы времени выполнения алгоритма. Он измеряет сложность времени наихудшего случая или наибольшее время, которое алгоритм может занять для завершения.

Обозначение Big O

Например, для функции f (n)

Ο( f (n)) = { g (n) : there exists c > 0 and n 0 such that f (n) ≤ c. g (n) for all n > n 0 . }

Нотация Омега, Ом

Обозначение Ω (n) является формальным способом выражения нижней границы времени работы алгоритма. Он измеряет наилучшую временную сложность или лучшее время, которое алгоритм может занять для завершения.

Нотация Омега

Например, для функции f (n)

Ω( f (n)) ≥ { g (n) : there exists c > 0 and n 0 such that g (n) ≤ c. f (n) for all n > n 0 . }

Тета-нотация, θ

Обозначение θ (n) является формальным способом выражения как нижней, так и верхней границы времени выполнения алгоритма. Это представляется следующим образом –

Тэта нотация

θ( f (n)) = { g (n) if and only if g (n) =  Ο( f (n)) and g (n) = Ω( f (n)) for all n > n 0 . }

Распространенные асимптотические обозначения

Ниже приведен список некоторых распространенных асимптотических обозначений –