Matemática Discreta I · T7
Complejidad de algoritmos
Tema 07 · Johnsonbaugh, 6.ª ed., §4.3 y §7.3 · Epp, cap. 11
Dos algoritmos resuelven el mismo problema; uno lo hace en segundos y el otro tardaría años. La complejidad explica por qué sin ejecutar nada: es el estudio de cómo crece el costo de un algoritmo con el tamaño de la entrada. La sección 1 fija la notación ([1.1](#p-7-1)–[1.3](#p-7-3)); la sección 2 da las reglas para analizar código real ([2.1](#p-7-4)–[2.2](#p-7-5)); la sección 3 aplica todo a los algoritmos canónicos y a la decisión de diseño ([3.1](#p-7-6)–[3.3](#p-7-8)). La idea es de la década de 1960 (Knuth, «The Art of Computer Programming», 1968, fijó la notación; Hartmanis y Stearns habían formalizado las clases de complejidad en 1965) y es el vocabulario con el que la profesión compara soluciones. Esta guía sigue §4.3 de Johnsonbaugh (análisis de algoritmos y notación asintótica) y §7.3 (recurrencias), con las páginas citadas punto a punto.
- Versión
- 1.0
- Publicada
- Páginas
- 21 + 15 del solucionario
- Formato
- PDF · A4
- Enlace
( Contenido ) Temas
- costo temporal
- peor caso
- cota superior
- cotas Ω y Θ
- jerarquía de crecimiento
- análisis de bucles
- condicionales
- búsqueda binaria
- ordenación
- escalabilidad