Análisis de algoritmos

En el análisis teórico de algoritmos, es común estimar su complejidad en el sentido asintótico, es decir, estimar la función de complejidad para entradas arbitrariamente grandes. El término «análisis de algoritmos» fue acuñado por Donald Knuth.

El análisis de algoritmos es una parte importante de la teoría de la complejidad computacional, que proporciona una estimación teórica de los recursos necesarios de un algoritmo para resolver un problema computacional específico. La mayoría de los algoritmos están diseñados para trabajar con entradas de longitud arbitraria. El análisis de algoritmos es la determinación de la cantidad de recursos de tiempo y espacio necesarios para ejecutarlo.

Por lo general, la eficiencia o el tiempo de ejecución de un algoritmo se establece como una función que relaciona la longitud de entrada con el número de pasos, conocido como complejidad de tiempo o volumen de memoria, conocido como complejidad de espacio .

Complejidad Algorítmica.

¿De qué hablamos cuando hablamos de complejidad? Resulta evidente que el tiempo real requerido por una computadora para la ejecución de algoritmo es directamente proporcional al número de operaciones básicas que la computadora debe realizar en su ejecución. Medir por lo tanto el tiempo real de ejecución equivale a medir el número de operaciones elementales realizadas. Desde ahora supondremos que todas las operaciones básicas se ejecutan en una unidad de tiempo. Por esta razón se suele llamar tiempo de ejecución no al tiempo real físico, sino al número de operaciones elementales realizadas. Otro de los factores importantes, en ocasiones decisivo, para comparar algoritmos es la cantidad de memoria del computador requerida para almacenar los datos durante el proceso. La cantidad de memoria utilizada durante el proceso se suele llamar espacio requerido por el algoritmo.
Al no ser única la manera de representar un algoritmo mediante un programa, y al no ser único el computador en el cual se ejecutará, resulta que la medida del tiempo será variable dependiendo fundamentalmente de los siguientes factores:

  • 1) El lenguaje de programación elegido
  • 2) El programa que representa
  • 3) El computador que lo ejecuta

Por eso surge la necesidad de medir el tiempo requerido por un algoritmo independientemente de su representación y del computador que lo ejecute.

El análisis de algoritmos se encarga del estudio del tiempo y espacio requerido por un algoritmo para su ejecución. Ambos parámetros pueden ser estudiados con respecto al peor caso (también conocido como caso general) o respecto al caso probabilístico (o caso esperado).

En Ciencias de la Computación, el término eficiencia algorítmica es usado para describir aquellas propiedades de los algoritmos que están relacionadas con la cantidad de recursos utilizados por el algoritmo. Un algoritmo debe ser analizado para determinar el uso de los recursos que realiza. La eficiencia algorítmica puede ser vista como análogo a la ingeniería de productividad de un proceso repetitivo o continuo.
Con el objetivo de lograr una eficiencia máxima se quiere minimizar el uso de recursos. Sin embargo, varias medidas (complejidad temporal, complejidad espacial) no pueden ser comparadas directamente, luego, cual de dos algoritmos es considerado más eficiente, depende de cual medida de eficiencia se está considerando como prioridad; por ejemplo la prioridad podría ser obtener la salida del algoritmo lo más rápido posible, o que minimice el uso de la memoria, o alguna otra medida particular.
Una diferencia significativa entre el análisis de complejidad de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.
La importancia de la eficiencia con respecto a la complejidad temporal fue enfatizada por Ada Lovelace en 1843 como resultado de su trabajo con el motor analítico mecánico de Charles Babbage: «En casi todo cómputo son posibles una gran variedad de configuraciones para la sucesión de un proceso, y varias consideraciones pueden influir en la selección de estas según el propósito de un motor de cálculos. Una objetivo esencial es escoger la configuración que tienda a minimizar el tiempo necesario para completar el cálculo.»

Existen muchas maneras para medir la cantidad de recursos utilizados por un algoritmo: las dos medidas más comunes son la complejidad temporal y espacial; otras medidas a tener en cuenta podrían ser la velocidad de transmisión, uso temporal del disco duro, así como uso del mismo a largo plazo, consumo de energía, tiempo de respuesta ante los cambios externos, etc. Muchas de estas medidas dependen del tamaño de la entrada del algoritmo ( Ej. la cantidad de datos a ser procesados); además podrían depender de la forma en que los datos están organizados (Ej. algoritmos de ordenación necesitan hacer muy poco en datos que ya están ordenados o que están ordenados de forma inversa).
En la práctica existen otros factores que pueden afectar la eficiencia de un algoritmo, tales como la necesidad de cierta precisión y/o veracidad. La forma en que un algoritmo es implementado también puede tener un efecto de peso en su eficiencia, muchos de los aspectos asociados a la implementación se vinculan a problemas de optimización.

Necesidad de análisis

La necesidad de analizar algoritmos surge como necesidad de eficiencia, es decir elegir un mejor algoritmo para un problema particular, ya que un problema computacional puede resolverse mediante diferentes algoritmos.

Al considerar un algoritmo para un problema específico, podemos comenzar a desarrollar el reconocimiento de patrones de modo que la ayuda de este algoritmo pueda resolver tipos similares de problemas.

Los algoritmos a menudo son bastante diferentes entre sí, aunque el objetivo de estos algoritmos es el mismo. Por ejemplo, sabemos que un conjunto de números se puede ordenar usando diferentes algoritmos. El número de comparaciones realizadas por un algoritmo puede variar con otros para la misma entrada. Por lo tanto, la complejidad temporal de esos algoritmos puede diferir. Al mismo tiempo, necesitamos calcular el espacio de memoria requerido por cada algoritmo.

El análisis del algoritmo es el proceso de analizar la capacidad de resolución de problemas del algoritmo en términos del tiempo y el tamaño requeridos (el tamaño de la memoria para el almacenamiento durante la implementación). Sin embargo, la principal preocupación del análisis de algoritmos es el tiempo o rendimiento requerido. En general, realizamos los siguientes tipos de análisis:

  • El peor de los casos: el número máximo de pasos dados en cualquier instancia de tamaño N.
  • El mejor caso : el número mínimo de pasos dados en cualquier instancia de tamaño N.
  • El caso promedio : un número promedio de pasos dados en cualquier instancia de tamaño N.
  • El amortizado : una secuencia de operaciones aplicadas a la entrada de tamaño promediada en el tiempo.

Para resolver un problema, debemos tener en cuenta el tiempo y la complejidad del espacio, ya que el programa puede ejecutarse en un sistema donde la memoria es limitada pero hay suficiente espacio disponible o viceversa. En este contexto, si comparamos el ordenamiento de burbuja y el de fusión. El ordenamiento de burbuja no requiere memoria adicional, pero el ordenameinto por fusión requiere espacio adicional. Aunque la complejidad temporal del ordenamiento de burbuja es mayor en comparación con el ordenamiento de fusión, es posible que necesitemos aplicar el ordenamiento de burbuja si el programa necesita ejecutarse en un entorno, donde la memoria es muy limitada.

Para medir el consumo de recursos de un algoritmo, se utilizan diferentes estrategias