Unidad 2 - emilioone05/Analisis_Algoritmos_utpl GitHub Wiki
Unidad 2: Análisis de Algoritmos y Notación Asintótica
📌 Índice
- Notación Asintótica
- Factores que Afectan el Tiempo de Ejecución
- Ejemplo Ilustrativo
- Taller en Clase
- Notación para el "Orden de"
- Notación Asintótica Condicional
📘 1. Notación Asintótica
La notación asintótica describe cómo crece el tiempo o el uso de memoria de un algoritmo conforme aumenta el tamaño de la entrada n
.
Tipos principales:
Símbolo | Nombre | Significado |
---|---|---|
O | Big-O | Límite superior (peor caso) |
Ω | Omega | Límite inferior (mejor caso) |
Θ | Theta | Límite ajustado (caso promedio) |
Sirve para comparar la eficiencia de algoritmos sin depender del hardware o lenguaje específico.
🧠 2. Factores que Afectan el Tiempo de Ejecución
- Velocidad del procesador (CPU)
- Lenguaje de programación y su compilador/intérprete
- Calidad del código y optimizaciones
- Tamaño y forma de los datos de entrada
🧮 3. Ejemplo Ilustrativo
Supón la función: f(n) = 3n² + 2n + 1
Cuando n
es grande, los términos menos significativos se ignoran:
➡️ O(n²)
🧪 4. Taller en Clase
Ejercicios realizados en clase para practicar la identificación y aplicación de notación asintótica.
✅ Revisa tus respuestas y reflexiona sobre los casos mejor, peor y promedio.
(Imagen eliminada por irrelevante)
🧾 5. Notación para el "Orden de"
La notación asintótica se usa para describir el comportamiento de una función cuando n
tiende a infinito.
Ideal para análisis de algoritmos y comparación de su rendimiento.
Ejemplos:
- O(n²):
f(n) = 3n² + 2n + 1
- Ω(n):
f(n) = 2n + 5
- Θ(n):
f(n) = 5n + 3
⚖️ 6. Notación Asintótica Condicional
Algunos algoritmos cambian de comportamiento según condiciones específicas.
Ejemplo: QuickSort
Caso | Complejidad |
---|---|
Mejor caso | Ω(n) |
Peor caso | O(n²) |
Promedio | Θ(n log n) |
Útil cuando la eficiencia depende de factores como el tipo de entrada o la estrategia de pivote.