Notaciones asintóticas y análisis a priori

Al diseñar un algoritmo, el análisis de la complejidad de un algoritmo es un aspecto esencial. Principalmente, la complejidad algorítmica se preocupa por su rendimiento, qué tan rápido o lento funciona.

La complejidad de un algoritmo describe la eficiencia del algoritmo en términos de la cantidad de memoria requerida para procesar los datos y el tiempo de procesamiento.

La complejidad de un algoritmo se analiza en dos perspectivas: Time y Space.

Complejidad del tiempo

Es una función que describe la cantidad de tiempo necesario para ejecutar un algoritmo en términos del tamaño de la entrada. "Tiempo" puede significar el número de accesos a memoria realizados, el número de comparaciones entre enteros, el número de veces que se ejecuta algún bucle interno o alguna otra unidad natural relacionada con la cantidad de tiempo real que tomará el algoritmo.

Complejidad espacial

Es una función que describe la cantidad de memoria que toma un algoritmo en términos del tamaño de la entrada al algoritmo. A menudo hablamos de memoria "extra" necesaria, sin contar la memoria necesaria para almacenar la entrada en sí. Nuevamente, usamos unidades naturales (pero de longitud fija) para medir esto.

La complejidad del espacio a veces se ignora porque el espacio utilizado es mínimo y / o obvio, sin embargo, a veces se convierte en un problema tan importante como el tiempo.

Notaciones asintóticas

El tiempo de ejecución de un algoritmo depende del conjunto de instrucciones, la velocidad del procesador, la velocidad de E / S del disco, etc. Por lo tanto, estimamos la eficiencia de un algoritmo de forma asintótica.

La función de tiempo de un algoritmo está representada por T(n), dónde n es el tamaño de entrada.

Se utilizan diferentes tipos de notaciones asintóticas para representar la complejidad de un algoritmo. Las siguientes notaciones asintóticas se utilizan para calcular la complejidad del tiempo de ejecución de un algoritmo.

• O - gran oh

• Ω - Gran omega

• θ - Gran theta

• o - pequeño oh

• ω - Pequeño omega

O: límite superior asintótico

'O' (Big Oh) es la notación más utilizada. Una funciónf(n) se puede representar es el orden de g(n) es decir O(g(n)), si existe un valor de entero positivo n como n₀ y una constante positiva c tal que -

$ f (n) \ leqslant cg (n) $ por $ n> n_ {0} $ en todos los casos

Por lo tanto, función g(n) es un límite superior para la función f(n), como g(n) crece más rápido que f(n).

Ejemplo

Consideremos una función dada, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Considerando $ g (n) = n ^ 3 $,

$ f (n) \ leqslant 5.g (n) $ para todos los valores de $ n> 2 $

Por tanto, la complejidad de f(n) se puede representar como $ O (g (n)) $, es decir, $ O (n ^ 3) $

Ω: límite inferior asintótico

Decimos que $ f (n) = \ Omega (g (n)) $ cuando existe constante c que $ f (n) \ geqslant cg (n) $ para todo valor suficientemente grande de n. aquínes un número entero positivo. Significa funcióng es un límite inferior para la función f; después de un cierto valor den, f nunca irá abajo g.

Ejemplo

Consideremos una función dada, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.

Considerando $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ para todos los valores de $ n> 0 $.

Por tanto, la complejidad de f(n) se puede representar como $ \ Omega (g (n)) $, es decir, $ \ Omega (n ^ 3) $

θ: Asymptotic Tight Bound

Decimos que $ f (n) = \ theta (g (n)) $ cuando existen constantes c₁ y c₂ que $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ para todos los valores suficientemente grandes de n. aquín es un número entero positivo.

Esto significa función g es un límite estrecho para la función f.

Ejemplo

Consideremos una función dada, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Considerando $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ para todos los valores grandes de n.

Por tanto, la complejidad de f(n) se puede representar como $ \ theta (g (n)) $, es decir, $ \ theta (n ^ 3) $.

O - Notación

El límite superior asintótico proporcionado por O-notationpuede o no ser asintóticamente apretado. El límite $ 2.n ^ 2 = O (n ^ 2) $ es asintóticamente ajustado, pero el límite $ 2.n = O (n ^ 2) $ no lo es.

Usamos o-notation para denotar un límite superior que no es asintóticamente apretado.

Definimos formalmente o(g(n)) (pequeño-oh de g de n) como el conjunto f(n) = o(g(n)) para cualquier constante positiva $ c> 0 $ y existe un valor $ n_ {0}> 0 $, tal que $ 0 \ leqslant f (n) \ leqslant cg (n) $.

Intuitivamente, en el o-notation, la función f(n) se vuelve insignificante en relación con g(n) como nse acerca al infinito; es decir,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$

Ejemplo

Consideremos la misma función, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Considerando $ g (n) = n ^ {4} $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$

Por tanto, la complejidad de f(n) se puede representar como $ o (g (n)) $, es decir, $ o (n ^ 4) $.

ω - Notación

Usamos ω-notationpara denotar un límite inferior que no es asintóticamente apretado. Formalmente, sin embargo, definimosω(g(n)) (pequeño omega de g de n) como el conjunto f(n) = ω(g(n)) para cualquier constante positiva C > 0 y existe un valor $ n_ {0}> 0 $, tal que $ 0 \ leqslant cg (n) <f (n) $.

Por ejemplo, $ \ frac {n ^ 2} {2} = \ omega (n) $, pero $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. La relación $ f (n) = \ omega (g (n)) $ implica que existe el siguiente límite

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$

Es decir, f(n) se vuelve arbitrariamente grande en relación con g(n) como n se acerca al infinito.

Ejemplo

Consideremos la misma función, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Considerando $ g (n) = n ^ 2 $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$

Por tanto, la complejidad de f(n) se puede representar como $ o (g (n)) $, es decir, $ \ omega (n ^ 2) $.

Análisis apriori y apostólico

Análisis a priori significa que el análisis se realiza antes de ejecutarlo en un sistema específico. Este análisis es una etapa en la que se define una función utilizando algún modelo teórico. Por lo tanto, determinamos la complejidad de tiempo y espacio de un algoritmo con solo mirar el algoritmo en lugar de ejecutarlo en un sistema en particular con una memoria, procesador y compilador diferente.

El análisis apostólico de un algoritmo significa que realizamos el análisis de un algoritmo solo después de ejecutarlo en un sistema. Depende directamente del sistema y cambia de un sistema a otro.

En una industria, no podemos realizar análisis Apostiari ya que el software generalmente está hecho para un usuario anónimo, que lo ejecuta en un sistema diferente a los presentes en la industria.

En Apriori, es la razón por la que usamos notaciones asintóticas para determinar la complejidad del tiempo y el espacio a medida que cambian de una computadora a otra; sin embargo, asintóticamente son iguales.