Algoritmos. Análisis de Complejidad Temporal

[pic 1]

[pic 2]

Un algoritmo es un conjunto de pasos o procedimientos utilizados para resolver un problema. Es un proceso bien definido que toma alguna entrada, realiza ciertas operaciones en la entrada y produce alguna salida. Los algoritmos son una parte importante de la informática y se utilizan para realizar una amplia variedad de tareas, desde cálculos simples hasta análisis de datos complejos e inteligencia artificial.

En cuanto a la complejidad de un algoritmo es una medida de cuán eficiente es el algoritmo para resolver el problema. En otras palabras, es una medida de cuánto tiempo y espacio (memoria) requiere el algoritmo para producir una solución. Cuando se habla de complejidad se hace referencia, casi todas las veces, a la complejidad temporal. No obstante, también existe otro tipo de complejidad: la espacial. La primera de ellas, determina de una forma exacta el tiempo (donde una posible unidad de medida son los segundos) de ejecución de un algoritmo. Sin embargo, la segunda de estas determina la cantidad de memoria utilizada (medida en bytes) por el algoritmo. Otros puntos a destacar en la complejidad de los algoritmos son los siguientes:

1. Notación Asintótica:

La notación asintótica, como O, Ω y Θ, se utiliza para describir el comportamiento de los algoritmos a medida que el tamaño de entrada crece. O notación proporciona un límite superior, Ω un límite inferior, y Θ representa un límite ajustado. Esta notación es crucial para expresar la eficiencia relativa de los algoritmos.

1.  Análisis de Complejidad Temporal:

El análisis temporal examina cómo el tiempo de ejecución de un algoritmo cambia con el tamaño de entrada. Los casos mejor, peor y promedio son considerados. La recurrencia y el método maestro son herramientas comunes para analizar el tiempo de ejecución en algoritmos recursivos.

1.  Análisis de Complejidad Espacial:

La complejidad espacial se refiere al uso de memoria por parte de un algoritmo. Se exploran estructuras de datos eficientes y estrategias para minimizar el uso de memoria. La optimización del espacio es crítica en aplicaciones con restricciones de memoria.

1.  Clasificación de Problemas:

Los problemas se clasifican en clases de complejidad, como P (solucionables en tiempo polinómico), NP (no deterministas polinómicos), NP-completo y NP-duro. Esta clasificación es esencial para entender la dificultad inherente de los problemas y su solubilidad algorítmica.

1. Algoritmos Cuánticos:

La computación cuántica introduce nuevos paradigmas en la complejidad de algoritmos. Algoritmos cuánticos, como el algoritmo de Shor y el algoritmo de Grover, ofrecen soluciones más eficientes para ciertos problemas, redefiniendo límites y posibilidades en la computación.

A continuación se indica el como es el ordenamiento de complejidad de los algoritmos:

[pic 3]

Mediante el análisis de algoritmos se puede determinar la complejidad de cada uno de ellos, es decir, el tiempo de ejecución que tendrá ese programa en función de la cantidad de datos de entrada. En situaciones reales este análisis permitirá elegir justificadamente un algoritmo u otro para ser desarrollado e implementar la solución más eficiente a un problema real. [pic 4]

...