SEMANA_05_B1 - meruiz22/Analisis-de-Algoritmos GitHub Wiki
Caracterización de los tiempos de ejecución
La caracterización de los tiempos de ejecución es cómo medimos cuánto tiempo tarda un algoritmo en resolver un problema, dependiendo del tamaño de la entrada. Por ejemplo, buscar un número en una lista pequeña es rápido, pero en una lista grande puede tardar más. Usamos notaciones como Big O para el peor caso, Omega (Ω) para el mejor, y Theta (Θ) cuando el tiempo es similar en todos los casos.
Notación Omega (Ω)
La notación Omega (Ω) muestra el mínimo tiempo que un algoritmo necesita, como cuando encuentras algo al principio de una lista, que toma un paso constante: Ω(1).
Es útil para garantizar que un algoritmo siempre tomará al menos cierto tiempo.
Ejemplos:
- Búsqueda lineal:
Ω(1)→ si el elemento está en la primera posición. - Ordenamiento por mezcla (merge sort):
Ω(n log n)→ el algoritmo nunca será más rápido que esto.
Notación Theta (Θ)
La notación Theta (Θ) se usa cuando el tiempo de un algoritmo es el mismo en el mejor y peor caso. Por ejemplo, el ordenamiento por mezcla siempre toma Θ(n log n).
Es una medida ajustada que indica que el tiempo de ejecución está acotado superior e inferiormente por la misma función.
Notación asintótica condicional
Este término no es común en análisis de algoritmos. Probablemente sea un error de interpretación y se refiere a alguna de las notaciones estándar (O, Ω, Θ). Si se tiene un contexto adicional, se podría precisar mejor.
Nota detallada
El análisis de algoritmos es un campo esencial en informática que se enfoca en evaluar la eficiencia de los algoritmos en términos de tiempo y espacio.
La caracterización de los tiempos de ejecución se refiere específicamente al análisis de la complejidad temporal, que describe cómo el tiempo de ejecución de un algoritmo varía con el tamaño de la entrada (n).
Este análisis permite:
- Comparar algoritmos.
- Predecir su rendimiento.
- Garantizar su escalabilidad en sistemas reales.
Análisis según el caso
| Tipo de caso | Descripción | Ejemplo |
|---|---|---|
| Mejor caso | Tiempo mínimo. Cuando el problema se resuelve con el mínimo de pasos. | Buscar en la primera posición. |
| Peor caso | Tiempo máximo. El escenario más costoso. | Buscar en la última posición. |
| Caso promedio | Tiempo esperado si las entradas son aleatorias. | Buscar en cualquier posición. |
Diferencias entre notaciones
| Notación | Significado | Indica |
|---|---|---|
O(g(n)) |
Cota superior | Peor caso |
Ω(g(n)) |
Cota inferior | Mejor caso |
Θ(g(n)) |
Cota ajustada superior e inferior | Tiempo igual en todos los casos |