PRESENTACIÓN EINSTEIN

1.2. Notación asintótica

ayuda a simplificar la complejidad temporal, es decir, permite definir el tiempo máximo y mínimo que necesitará un algoritmo durante su ejecución, ya que un algoritmo o programa puede tardar más tiempo en ejecutarse o puede tardar menos tiempo

"Es un lenguaje que permite conocer la tasa de crecimiento de un algoritmo, es decir, permite analizar el tiempo de ejecución de un algoritmo cuando se aumentan las entradas para el algoritmo. Las notaciones que se revisarán son Big O, Litte o, Big Ω, Little ω y Big-θ."

Notación asintótica

Orden de crecimiento

Permite identificar el crecimiento de ejecución de un algoritmo o programa, es decir, permite identificar la eficiencia de un algoritmo. Para estudiar la eficiencia asintótica de los algoritmos, se deben asignar entradas lo suficientemente grandes para calcular el orden de crecimiento del tiempo, por lo tanto, se debe analizar cómo aumenta el tiempo de ejecución de un algoritmo con el tamaño de entradas justo en su límite.

Notación asintótica y orden de crecimiento

Las asíntotas son funciones que pasan muy cerca una de otra, pero nunca se cruzan como se muestra en la Figura .Por lo tanto, con la notación asintótica se busca establecer límites en su tiempo de ejecución, conforme su orden de crecimiento aumenta cuando más valores grandes de entrada se le asignan al algoritmo.El orden de crecimiento puede ser constante (1), lineal (n) o polinomial (log n) y exponencial (nn).

Big – O

La notación asintótica de límite superior Big-O se emplea para buscar un orden de crecimiento que siempre es mayor o igual que la complejidad temporal de un algoritmo T(n).Big O tiene un crecimiento mayor o igual a la complejidad del tiempo, pero también se debe multiplicar por una constante, por lo tanto, se representa como: T(n) =O(g(n)) g(n) x c > T(n) La complejidad temporal se representa como T(n), donde T es el tiempo y n es el tamaño de los datos.

Little-O

La notación asintótica de límite superior Little-O se emplea para buscar un orden de crecimiento que siempre es mayor que la complejidad temporal de un algoritmo T(n).Little O tiene un crecimiento mayor a la complejidad del tiempo, pero también se debe multiplicar por una constante, por lo tanto, se representa como: T(n) = o(g(n)) g(n) x c > T(n)

Ejemplo de grafica para big-o y litle-o

El punto n0 es el punto donde se comienza a cumplir con la regla en caso de que la complejidad temporal sea menor a la gráfica de crecimiento, como se muestra en la Figura.

Big Ω ( Big Omega )

La notación asintótica de límite inferior Big-Ω se emplea para buscar un orden de crecimiento que siempre es menor o igual que la complejidad temporal de un algoritmo T(n).Big Ω tiene un crecimiento menor o igual a la complejidad del tiempo, pero también se debe multiplicar por una constante, por lo tanto, se representa como: T(n) = Ω (g(n)) g(n) x c < T(n)

Representación grafica de Big Ω

Little ω ( Little omega)

La notación asintótica de límite inferior Little-ω se emplea para buscar un orden de crecimiento que siempre es menor que la complejidad temporal de un algoritmo T(n).Little ω tiene un crecimiento menor a la complejidad del tiempo, pero también se debe multiplicar por una constante, por lo tanto, se representa como: T(n) = ω (g(n)) g(n) x c < T(n)

representación grafica de Little ω

Big-θ

La notación asintótica de límite inferior Big-θ se emplea para buscar un orden de crecimiento que siempre es mayor o igual y menor o igual que la complejidad temporal de un algoritmo T(n).Big-θ tiene un crecimiento mayor o igual y menor o igual a la complejidad del tiempo, pero también se debe multiplicar por una constante, por lo tanto, se representa como: T(n) = θ (g(n)) g(n) x c1 < T(n) g(n) x c2 > T(n)

representación grafica de Big-θ

Lorem ipsum dolor

Consectetur adipiscing elit

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore. Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt.

• Lorem ipsum dolor sit amet.
• Consectetur adipiscing elit.
• Sed do eiusmod tempor incididunt ut.
• Labore et dolore magna aliqua.

Lorem ipsum dolor sit