Python - Tipos de algoritmos

Se debe analizar la eficiencia y precisión de los algoritmos para compararlos y elegir un algoritmo específico para ciertos escenarios. El proceso de realización de este análisis se denomina análisis asintótico. Se refiere a calcular el tiempo de ejecución de cualquier operación en unidades matemáticas de cálculo. Por ejemplo, el tiempo de ejecución de una operación se calcula como f (n) y puede serlo para otra operación como g (n2). Esto significa que el tiempo de ejecución de la primera operación aumentará linealmente con el aumento de ny el tiempo de ejecución de la segunda operación aumentará exponencialmente cuando n aumente. De manera similar, el tiempo de ejecución de ambas operaciones será casi el mismo si n es significativamente pequeño.

Por lo general, el tiempo requerido por un algoritmo se divide en tres tipos:

• Mejor caso: tiempo mínimo requerido para la ejecución del programa.
• Caso promedio: tiempo promedio requerido para la ejecución del programa.
• Peor caso: tiempo máximo necesario para la ejecución del programa.

Notaciones asintóticas

A continuación se muestran las notaciones asintóticas de uso común para calcular la complejidad del tiempo de ejecución de un algoritmo.

• Ο Notación
• Notación Ω
• θ Notación

Notación de Big Oh, Ο

La notación Ο (n) es la forma formal de expresar el límite superior del tiempo de ejecución de un algoritmo. Mide la complejidad del tiempo en el peor de los casos o la mayor cantidad de tiempo que un algoritmo puede tardar en completarse.

Por ejemplo, para una función f(n)

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

Notación Omega, Ω

La notación Ω (n) es la forma formal de expresar el límite inferior del tiempo de ejecución de un algoritmo. Mide la mejor complejidad del tiempo del caso o la mejor cantidad de tiempo que un algoritmo puede tardar en completarse.

Por ejemplo, para una función f(n)

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

Notación theta, θ

La notación θ (n) es la forma formal de expresar tanto el límite inferior como el límite superior del tiempo de ejecución de un algoritmo. Se representa de la siguiente manera:

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

Notaciones asintóticas comunes

A continuación se muestra una lista de algunas notaciones asintóticas comunes:

constante	-	Ο (1)
logarítmico	-	Ο (log n)
lineal	-	Ο (n)
n log n	-	Ο (n log n)
cuadrático	-	Ο (n 2 )
cúbico	-	Ο (n 3 )
polinomio	-	n Ο (1)
exponencial	-	2 Ο (n)