Notaciones asintóticas y cómo calcularlas

En matemáticas, el análisis asintótico , también conocido como asintótica , es un método para describir el comportamiento límite de una función. En informática, el análisis asintótico de un algoritmo se refiere a definir el límite matemático de su rendimiento en tiempo de ejecución en función del tamaño de entrada. Por ejemplo, el tiempo de ejecución de una operación se calcula como f (n) , y quizás para otra operación, se calcula como g (n ² ) . Esto significa que el tiempo de ejecución de la primera operación aumentará linealmente con el aumento de n y el tiempo de ejecución de la segunda operación aumentará exponencialmente cuando naumenta De manera similar, el tiempo de ejecución de ambas operaciones será casi el mismo si n tiene un valor pequeño.

Por lo general, el análisis de un algoritmo se realiza en base a tres casos :

1. Mejor Caso (Notación Omega (Ω))
2. Caso Promedio (Notación Theta (Θ))
3. Peor caso (Notación O (O))

Todas estas notaciones se analizan a continuación en detalle:

Notación Omega (Ω):

La notación Omega(Ω) especifica el límite inferior asintótico para una función f(n). Para una función dada g(n), Ω(g(n)) se denota por:

Ω (g(n)) = {f(n): existen constantes positivas c y n ₀ tales que 0 ≤ c*g(n) ≤ f(n) para todo n ≥ n ₀ }. 

Esto significa que, f(n) = Ω(g(n)), Si hay constantes positivas n ₀ y c tales que, a la derecha de n ₀ , f(n) siempre se encuentra sobre o sobre c*g(n ).

Siga los pasos a continuación para calcular Ω para un programa:

1. Divida el programa en segmentos más pequeños.
2. Encuentre el número de operaciones realizadas para cada segmento (en términos del tamaño de entrada) asumiendo que la entrada dada es tal que el programa toma la menor cantidad de tiempo.
3. Sume todas las operaciones y simplifique, digamos que es f(n).
4. Elimine todas las constantes y elija el término de menor orden o cualquier otra función que sea siempre menor que f(n) cuando n tiende a infinito, digamos que es g(n) entonces, Omega (Ω) de f(n) es Ω(g(n)).

La notación Omega realmente no ayuda a analizar un algoritmo porque es falso evaluar un algoritmo para los mejores casos de entradas.

Notación theta (Θ):

La notación Big-Theta(Θ) especifica un límite para una función f(n). Para una función dada g(n), Θ(g(n)) se denota por:

Θ (g(n)) = {f(n): existen constantes positivas c ₁ , c ₂ y n ₀ tales que 0 ≤ c ₁ *g(n) ≤ f(n) ≤ c ₂ *g(n) para todo n ≥ n ₀ }. 

Esto significa que, f(n) = Θ(g(n)), Si hay constantes positivas n ₀ y c tales que, a la derecha de n ₀ , f(n) siempre se encuentra sobre c ₁ *g( n) y por debajo de c ₂ *g(n).

Siga los pasos a continuación para calcular Θ para un programa:

1. Divida el programa en segmentos más pequeños.
2. Encuentra todo tipo de entradas y calcula el número de operaciones que tardan en ejecutarse. Asegúrese de que los casos de entrada estén igualmente distribuidos.
3. Encuentre la suma de todos los valores calculados y divida la suma por el número total de entradas, digamos que la función de n obtenida es g(n) después de eliminar todas las constantes, luego en notación Θ, se representa como Θ(g(n) ). 

Ejemplo: en un problema de búsqueda lineal , supongamos que todos los casos están distribuidos uniformemente (incluido el caso en que la clave está ausente en la array). Entonces, suma todos los casos en los que la clave está presente en las posiciones 1, 2, 3, ……, n y no está presente, y divide la suma por n + 1.

Complejidad de tiempo de caso promedio = 

⇒ 

⇒ 

⇒ 

Dado que todos los tipos de entradas se consideran al calcular la complejidad de tiempo promedio, es uno de los mejores métodos de análisis para un algoritmo.

Grande – O Notación:

La notación Big – O (O) especifica el límite superior asintótico para una función f(n). Para una función dada g(n), O(g(n)) se denota por:

Ω (g(n)) = {f(n): existen constantes positivas c y n ₀ tales que f(n) ≤ c*g(n) para todo n ≥ n ₀ }. 

Esto significa que, f(n) = Ω(g(n)), Si hay constantes positivas n ₀ y c tales que, a la derecha de n ₀ , f(n) siempre se encuentra sobre o debajo de c*g(n ).

Siga los pasos a continuación para calcular O para un programa:

1. Divida el programa en segmentos más pequeños.
2. Encuentre el número de operaciones realizadas para cada segmento (en términos del tamaño de entrada) asumiendo que la entrada dada es tal que el programa toma el tiempo máximo, es decir, el peor de los casos.
3. Sume todas las operaciones y simplifique, digamos que es f(n).
4. Elimine todas las constantes y elija el término que tenga el orden más alto porque para n tiende a infinito, las constantes y los términos de orden más bajo en f(n) serán insignificantes, digamos que la función es g(n) , entonces, la notación O grande es O(g(n)).

Es la notación más utilizada, ya que es más fácil de calcular, ya que no hay necesidad de comprobar cada tipo de entrada como en el caso de la notación theta, además, dado que se tiene en cuenta el peor caso de entrada, da bastante el límite superior del tiempo que el programa tardará en ejecutarse.