Antes de leer este post, puedes necesitar leer la introducción I aqui.
Notación asintótica
La notación asintótica, es una notación matemática formal que nos permite expresar las cotas bajo las que se encuentra el costo de cierto algoritmo, donde el costo puede ser en tiempo de ejecución, espacio requerido de almacenamiento, entre otros. Básicamente podemos acotar un algoritmo superiormente (O), inferiormente (Ω), y exactamente (Θ).
En el orden de (O)
Para explicar este concepto, imaginemos que tenemos una función cualquiera: t(n)=
Antes de continuar, es necesario introducir el concepto del principio de invarianza, que dice que la razón de los tiempos de ejecución de dos implementaciones diferentes de un mismo algoritmo, siempre está acotada por encima y por debajo por constantes predeterminadas, donde las constantes pueden depender de las implementaciones de un algoritmo, pero no del tamaño del ejemplar en el que usaremos el algoritmo.
Ahora contemplemos otra función f(n)=
t(n) ≤ c f(n), siempre que n ≥
Ahora para entender esto, tomaremos las funciones definidas anteriormente, t(n)=
t(n)=
≤Â
≤ 6
≤ 6 f(n)            (4)
En la Ec.(2) sustituimos el término más grande, entonces obviamente, el valor original de t(n), se vuelve menor que la nueva expresión. En la Ec.3 solo sumamos los términos y en Ec. 4, sustituimos
Ahora, ya hemos dicho que t(n) puede representar cualquier unidad de costo, ya sean microsegundos, bits, años, etc. esto dependiendo de lo que estemos midiendo en nuestro algoritmo (después veremos la forma de obtener t(n)), pero por poner un ejemplo, diremos que nuestro algoritmo ejemplo tarda
Para denotar matemáticamente «en el orden de», se utiliza el simbolo «big O», también conocida como «O grandota». Por lo que es correcto expresar: t(n) ϵ O(f(n)), en nuestro ejemplo: (
Bitacoras.com
septiembre 26, 2012 at 11:48 amInformación Bitacoras.com…
Valora en Bitacoras.com: Antes de leer este post, puedes necesitar leer la introducción I aqui. Notación asintótica La notación asintótica, es una notación matemática formal que nos permite expresar las cotas bajo las que se encuentra el costo……