Big-O

Enconté mediante Reddit un post en Stack Overflow que explica en términos sencillos en qué consiste la notación “Big-O”, utilizada para representar la complejidad de un algoritmo.

Traduzco solo una parte del post aquí, les recomiendo leer el post completo si es que te encuentras en duda o necesitas repasar en qué consiste esta notación.

La notación Big-O es una representación relativa de la complejidad de un algoritmo.

Hay algunas palabras importantes deliberadamente elejidas en esta oración:

  • relativa: únicamente puedes comparar manzanas con manzanas. No puedes comparar un algoritmo que hace multiplicación aritmética con uno que ordena una lista de enteros. No obstante, [comparar] dos algoritmos que hacen operaciones aritmeticas (uno multiplicación y otro suma) te dirá algo significativo.
  • representación: Big-O (en su forma más simple) reduce la comparación entre algoritmos a una única variable. Esa variable es elegida basandose en observaciones y supuestos. Por ejemplo, [los] algoritmos para ordenar son típicamente comparados en base a operaciones de comparación (comparar dos nodos para determinar su orden relativo). Esto asume que comparar es costoso. ¿Pero qué si comparar es barato e intercambiar costoso? Cambia la comparación; y
  • complejidad: si me toma un segundo ordenar 10.000 elementos, ¿cuánto me llevará ordenar un millón? La complejidad, en esta instancia, es una medida relativa de algo más.

Continuar leyendo en Stack Overflow…

This entry was posted in Programacion. Bookmark the permalink.