Capítulo 1. Algoritmos y Complejidad Temporal

¿Qué es un algoritmo?

Básicamente, un algoritmo es un conjunto finito de instrucciones ordenadas. Transforman datos de entrada en datos de salida resolviendo algún problema en particular.

Con salida correcta queremos decir que, ante una determinada entrada válida, se genere un resultado esperado.

Es independiente del lenguaje de programación. Cuando lo trasladamos a un lenguaje en particular, estamos generando un programa.

Vamos a considerar dos tipos distintos de complejidad para el análisis de algoritmos:

• Temporal: Medida de eficiencia o de tiempo.
• Espacial: Cuánto me ocupa la resolución del algoritmo.

No nos ocuparemos en el curso de la complejidad espacial, pero es importante tenerla en cuenta cuando se dispone de recursos limitados.

Complejidad Temporal

Podemos organizar la Complejidad Temporal en dos categorías:

• Teórica: Podemos hacer un análisis previo a la ejecución.
• Real: Tenemos dependencia del hardware, recursos, etc.

Centraremos nuestra atención sobre la Complejidad Temporal Teórica. De aquí en adelante nos referiremos a ella simplemente como complejidad temporal.

Para realizar el análisis del costo de un algoritmo debemos tener en cuenta:

• La cantidad de datos de entrada (tamaño de la entrada).
• Análisis de las operaciones elementales (suma, asignación, comparación, etc).
• Análisis de casos (mejor, promedio, peor).

En general, el costo de un algoritmo dependerá del tamaño de la entrada y por ello resulta conveniente definirlo como una función de n donde n representará el tamaño de la entrada.

Utilizaremos O(n) para expresar la función del costo de un algoritmo:

Dependiendo del tamaño de la entrada tendremos los siguientes costos (ordenados de menor a mayor costo):

• O(c) - Constante. Es independiente de los datos de entrada. En general las operaciones elementales tienen un costo constante (suma, asignación, comparación).
• O(log n) - Logarítmica. 
• O(n) - Lineal. La cantidad de operaciones crece linealmente con la cantidad de elementos de entrada.
• O(n*log n)
• O(n²) ... O(n^x) - Polinomiales.

También están aquellas que no son aplicables para un algoritmo:

• O(xⁿ)
• O(n!)

En el próximo capítulo aplicaremos estos conceptos a métodos recursivos.

Fuentes: 

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.