1 Resumen de Estudio 2 Unidad 43 Algoritmos de Complejidad

Apuntes

• Resumen de Estudio – Unidad 4: Algoritmos de Complejidad ❑ ¿Qué es la complejidad de un algoritmo? Es una medida del rendimiento de un algoritmo en función del tamaño de entrada (n). Se divide en: • Complejidad temporal: cuánto tiempo tarda. • Complejidad espacial: cuánto memoria usa. ❑ Notación Big O (O) Describe el peor caso del algoritmo. • O(1): Tiempo constante (acceso directo a un arreglo). • O(n): Lineal (recorrer una lista). • O(n²): Cuadrática (ejemplo: ordenamiento burbuja). • O(log n): Logarítmica (búsqueda binaria). • O(n log n): Ejemplo: Merge Sort. • O(n!): Factorial (muy lento, como permutaciones). Ignora constantes y términos menores: Ejemplo: O(2n + 100) → O(n). ❑ Otras Notaciones: • Little o (o): límite superior estricto (menos usado). • Omega (Ω): límite inferior (mejor caso). • Theta (Θ): comportamiento exacto (mejor = peor = promedio). ❑ Tipos de análisis • Peor caso (Big O): tiempo máximo. • Mejor caso (Ω): tiempo mínimo. --- • Algoritmos de tiempo polinomial Tienen complejidad O(n^k) (donde k ≥ 0). Son eficientes. Ejemplos: • Acceso a arreglo → O(1). • Búsqueda lineal → O(n). • Bubble Sort → O(n²). • Me...