Notación asintótica 1. Flashcards
Aprender sobre la notación asintótica. Crecimiento de tiempos de ejecución de un programa, constante, lineal, logarítmico (12 cards)
Notación O (O Grande - Big-O)
Representa la cota superior del tiempo de ejecución en el peor caso. Describe el tiempo máximo que puede tomar un algoritmo. Ejemplo: En la búsqueda binaria, la complejidad en el peor caso es
𝑂(log2𝑛)
Notación Ω (Omega Grande)
Representa la cota inferior del tiempo de ejecución en el mejor caso. Describe el tiempo mínimo que puede tomar un algoritmo. Ejemplo: En la búsqueda lineal, el mejor caso es Ω(1) si el elemento buscado está en la primera posición.
Notación Θ (Theta Grande)
Representa la cota ajustada del tiempo de ejecución en el caso promedio o general. Indica que el tiempo de ejecución es tanto 𝑂(𝑓(𝑛)) como Ω(𝑓(𝑛))
. Ejemplo: La búsqueda binaria tiene una complejidad de Θ(log2𝑛) en el promedio.
Cálculo de log2𝑛
El logaritmo en base 2 de un número 𝑛 indica cuántas veces necesitas dividir n por 2 para llegar a 1. Ejemplo:
log2 8 = 3 porque 2°3 = 8.
Crecimiento de tiempo de ejecución de búsqueda binaria.
La notación 𝑂(log2𝑛) para la búsqueda binaria indica que el tiempo de ejecución crece logarítmicamente en función del tamaño del array 𝑛. En el peor caso, con un array de 8 elementos, toma como máximo 3 pasos.
Tiempo de Ejecución en el Mejor Caso de búsqueda lineal.
En el mejor caso, la búsqueda lineal puede tomar solo 1 paso si el elemento buscado está en la primera posición. Esto se describe con Ω(1), indicando que el tiempo de ejecución es constante en el mejor escenario.
Comparación de Algoritmos O(n°2) vs O(n)
En el peor de los casos, un algoritmo con complejidad O(n°2) puede ser más lento que uno con complejidad
𝑂(𝑛) cuando el tamaño del input es suficientemente grande. Sin embargo, para inputs muy pequeños, O(n°2) puede ser más rápido.
Análisis asintótico.
Concepto matemático
que refiere al estudio del comportamiento de
las funciones cuando los inputs tienden al
infinito o algún otro valor limite.
¿Cómo medir si un algoritmo es eficiente?
Para medir la eficiencia de un algoritmo la
matematica y las ciencias de la computacion
idearon conceptos para medir la complejidad
Asintotica de un algoritmo.
Para describir esto se usa la notación Big-O
notation.
En si lo que se mide es como el tiempo de
ejecución de un programa crece de manera
asintótica, es decir a medida que los valores inputs se acercan al infinito
Notación en Big-O de un algoritmo de crecimiento lineal.
O(n) Un algoritmo de crecimiento lineal es un tipo de algoritmo cuya complejidad temporal aumenta linealmente con respecto al tamaño de la entrada. En términos más técnicos, si el tamaño de la entrada es “n”, el tiempo de ejecución del algoritmo es proporcional a “n”.
Notación en Big-O de un algoritmo constante.
O(1) Un algoritmo de tiempo constante es aquel cuyo tiempo de ejecución no depende del tamaño de la entrada. En otras palabras, el tiempo de ejecución del algoritmo permanece constante independientemente del tamaño de la entrada.
