Python - Типы алгоритмов

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

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

Лучший случай - минимальное время, необходимое для выполнения программы.
Средний случай - Среднее время, необходимое для выполнения программы.
Худший случай - максимальное время, необходимое для выполнения программы.

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

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

Ο Обозначение
Ω Обозначение
θ Обозначение

Обозначение Big Oh,

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

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

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

Омега-обозначение, Ω

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

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

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

Обозначение тета, θ

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

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

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

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

постоянный	-	Ο (1)
логарифмический	-	Ο (журнал n)
линейный	-	Ο (п)
п войти п	-	Ο (п войти п)
квадратичный	-	Ο (п ² )
кубический	-	Ο (п ³ )
многочлен	-	п ^{Ο (1)}
экспоненциальный	-	2 ^{Ο (п)}