Programación en C++‎ > ‎Apuntes C++‎ > ‎Algoritmos‎ > ‎

La notación Big-O

Esta entrada no tiene que ver con programación directamente, pero me parece interesante hacer una referencia de todas formas.

Cuando trabajamos con algoritmos, normalmente nos interesa el rendimiento de éste. Nos interesa saber, por ejemplo, de qué forma se comporta el algoritmo dada una cantidad determinada de datos a procesar. Científicos en computación emplean una forma de categorizar y comparar los algoritmos, de tal suerte que se pueda categorizar de forma rápida el rendimiento de un algoritmo. Esta forma de medir se llama la Notación Gran O: Big-O Notation (BON).

Esta notación expresa la ejecución de un algoritmo dado un parámetro de entrada (i.e. el tamaño de datos a procesar). La notación normalmente es O(n). Por ejemplo, si la ejecución crece linealmente con el número de elementos (dado n elementos el proceso aumenta en n complejidad, entonces el algoritmo es O(n). Si el algoritmo es independiente de la cantidad de datos a procesar, entonce el algoritmo es O(1). A continuación presento una tabla con los valores típicos de complejidad, así como su notación.

TipoNotaciónSignificado
ConstanteO(1)La ejecución es independiente del número de elementos a procesar.
LogarítmicaO(log(n))La ejecución crece logarítmicamente con respecto al número de elementos a procesar.
LinealO(n)La ejecución crece linealmente, con el mismo factor, conforme crece el número de elementos a procesar.
N Log NO(n * log(n))La ejecución crece como un producto de complejidad lineal y logarítmica.
CuadráticaO(n2)La ejecución crece de forma cuadrática con respecto al número de elementos a procesar.

Por supuesto, esta notación tiene sus pormenores. Cuando se calculan, es difícil que el resultado de ejecución coincida plenamente con alguna de estas fórmulas, pero normalmente se les considera buenas aproximaciones. También es importante hacer notar que esta notación oculta (en algunos casos) algunos factores con exponentes pequeños. En particular, no importa cuánto tiempo toma un algoritmo. Cualesquiera dos algoritmos lineales son considerados igualmente aceptables bajo esta medida. Hay incluso algunas situaciones en las que la constante oculta es tan larga en un algoritmo lineal que inclusive un algoritmo exponencial con una constante más pequeña es preferible en la práctica. Por ende, no se debe considerar como regla de oro esta notación, sino más bien como guía.

Para ejemplificar mejor el significado de la notación, a continuación presento una tabla donde se lista el tipo de complejidad, seguido del número de elementos a procesar, lo cuál nos da la salida deseada.

TipoNotación1251050100 1000
ConstanteO(1)1111111
LogarítmicaO(log(n))12346710
LinealO(n)12510501001,000
N Log NO(n * log(n))14154030070010,000
CuadráticaO(n2)14251002,50010,0001,000,000

Como se puede ver, dado un número de elementos a procesar pequeño, los resultados no cambian mucho (y aquí es donde los factores escondidos tendrían mucha importancia). Pero conforme éstos se incrementan, sí que cambia el resultado.

Para finalizar, solo apuntar que algunos algoritmos se consideran como amortizados, lo cuál quiere decir que las operaciones a largo plazo funcionan como se describe en la notación. Es decir, dado un proceso que lleve 20 minutos, posiblemente dentro de los primeros 5 minutos el algoritmo no se comporte como describe la notación, pero pasado este tiempo el resultado se empieza a estabilizar. De hecho, algunos algoritmos implementados en la librería estándar de C++ actúan de esta forma.

Comments