Eficiencia algorítmica: tiempo y espacio

Conceptos de informática

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Introducción a la notación Big-O

  • Mide el crecimiento de tiempo y espacio según crece la entrada
  • Ejemplos: $O(n)$, $O(n^2)$, $O(\log\, n)$
  • La 'O' indica el orden de crecimiento, p. ej., O(n) = lineal
Conceptos de informática

Complejidad temporal: analogía de oficina

Un gráfico que muestra varias complejidades de notación Big O

  • $O(1)$ - tiempo constante - "Vistazo rápido" - "constante"
  • $O(\log\,n)$ - aumenta lento - "Dividir en pilas" - "logarítmica"
  • $O(n)$ - aumento lineal - "Leer documento" - "lineal"
  • $O(n\,\log\,n)$ - aumenta más rápido - "Ordenar pilas" - "linearitmica"
  • $O(n^2)$ - aumento cuadrático - "Comparar documentos" - "cuadrática"
Conceptos de informática

Complejidad espacial: analogía de oficina

Un gráfico que muestra varias complejidades de notación Big O

  • $O(1)$ - espacio constante - "Espacio en el escritorio" - "constante"
  • $O(\log\,n)$ - aumenta lento en espacio - "notas mínimas" - "logarítmica"
  • $O(n)$ - aumento lineal - "post-its" - "lineal"
  • $O(n\,\log\,n)$ - aumenta más rápido - "Pilas temporales" - "linearitmica"
  • $O(n^2)$ - aumento cuadrático de espacio - "cuadrícula de comparación" - "cuadrática"
Conceptos de informática

¡Vamos a practicar!

Conceptos de informática

Preparing Video For Download...