Complegidad algoritmica


ANALISIS Y COMPLEJIDAD ALGORITMICA
“Controlar la complejidad es la esencia de la programación.”
- Brian Kernigan
INTRODUCCIÓN
Los programas constan de algoritmos y estructuras de datos.
Un buen programa es una combinación apropiada de ambos. Elegir e implementar una estructura de datos es tan importante como los algoritmos que manipulan los datos.
La forma de enfrentar un problemageneralmente esta determinada por la naturaleza del problema que se pretende resolver.
Esta situación nos lleva a pensar que una de las cosas más importantes a tomar en cuenta al momento de resolver un problema usando un computador, es seleccionar y/o diseñar algoritmos eficientes.
Al ser este un estudio acerca de algoritmos, lo primero que nos interesa es saber a que nos referimos por estapalabra. Viéndolo desde una perspectiva simple, un algoritmo son los pasos a seguir para llegar a un resultado.
Si lo queremos expresar de una manera más formal, un algoritmo es una conjunto ordenado de pasos que permiten resolver un problema. A la ciencia que se encarga del estudio de los algoritmos, así como de su categorización e implementación, se le conoce como Algoritmia.

Los valores quepuede procesar un algoritmo (con lo que pretendemos alimentar el programa) se les conoce como datos de entrada, mientras que alos resultados se les conoce como  datos de salida.

Para que podamos considerar un algoritmo como correcto, debe cumplir que para cualquier entrada válida, se debe obtener como salida la respuesta correcta. El algoritmo no sólo es incorrecto cuando no nos proporciona larespuesta esperada, sino también cuando no devuelve respuesta alguna. Esto puede llegar a suceder cuando el algoritmo queda en un ciclo sin poder salir, o cuando termina su ejecución tempranamente por problemas al procesar la entrada.
1.1. COMPLEJIDAD DE UN ALGORITMO.
Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintospuntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas.
Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán, cuando las implementemos, especialmente al atacar problemas "grandes"(es decir que procesen una gran cantidad de datos, quegeneralmente se denotara como N).

La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto fundamental para todos los programadores, sin embargo, a menudo se desconoce por completo. Muchos cursos, libros y autores eluden el tema porque a menudo se considera confuso, complejo y recargado de elementos superfluos.
Esto no es necesariamente cierto.La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal(matematico). La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todas las personas tienen y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto demasiado difícil deentenderni de implementar.

Entender la complejidad de un algoritmo es muy importante porque a la hora de resolver muchos problemas, normalmente utilizamos algoritmos que ya estan diseñados, por lo tanto saber valorar su complejidad puede ayudarnos a conocer cómo se va a comportar el algoritmo e incluso a escoger uno u otro, dependiendo de cual consideremos mas conveniente de acuerdo con la situaciónque tengamos que resolver en un determinado momento.

Para resolver cierto problema, podemos obtener más de un algoritmo propio, por supuesto que lo solucione, pero... ¿Cual de ellos es el mejor? Sería conveniente poder aplicar algún tipo de "puntuación" a los algoritmos, y que cuanta más puntuación tenga un algoritmo, supondremos que es el mejor. Eso es en cierto modo, lo que llamaremos...