Complejidad de algoritmo

Qué es la complejidad de un algoritmo
Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos 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 conotra, para conocer cómo se comportarán cuando las implementemos, especialmente al atacar problemas "grandes".
La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo se considerafarragoso.
Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto difícilde entender.
Análisis de algoritmos

El Análisis de algoritmos es una parte importante de una Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
Concepto de Complejidad dealgoritmos.

El análisis de algoritmo es una parte muy importante de la ciencia de la computación, de modo que la medida de la eficiencia de u algoritmo será uno de los factores fundamentales. Por consiguiente es importante poder analizar los requisitos de tiempo y espacio de u algoritmo para ver si existe dentro de limites aceptables. Es difícil realizar un análisis simple de un algoritmo que determinela cantidad exacta de tiempo requerida para ejecutarlo. La primera complicación es que la cantidad exacta de tiempo dependerá de la implementación del algoritmo y de la maquina en que se ejecuta. El análisis normalmente debe ser independiente del lenguaje o maquina que se utilice para implementar el algoritmo. El análisis del algoritmo tratará de obtener el orden de magnitud de tiempo requeridopara la ejecución del mismo y cada algoritmo tendrá un coste computacional diferente. La eficiencia es un criterio que se debe utilizar cuando se selecciona un algoritmo y su implementación. Existe al menos tres dificultades fundamentales que son los siguientes:

¿Cómo se codifican los algoritmos?
¿Que computadoras utilizara?
¿Qué datos debe utilizar el programa?

El análisis del aeficiencia debe ser independiente de las implementación especificas de la computadora y de los datos específicos que se manipulan. Pero las consideraciones de eficiencia fundamentales son: el tiempo y el espacio. La complejidad del espacio de un programa es la cantidad de memoria que se necesita para ejecutar hasta la compleción (terminación). La complejidad de el tiempo de un programa es la cantidad detiempo de computadora que se necesita para ejecutar hasta la compleción al considerar estos dos aspectos podremos tener la medida exacta de tiempo y espacio del cual necesitamos para realizar u buen análisis de algoritmos.

Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

Aritmética de lanotación O.

La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de los algoritmos.

Tipos de análisis de la Notación O

Peor caso (usualmente)
T(n) = Tiempo máximo necesario para un problema de tamaño n.

Caso medio (a veces)
T(n) = Tiempo esperado para un problema cualquiera de tamaño n.
* Requiere establecer una distribución estadística

Mejor...