Eficiencia algorítmica
En ciencias de la computación , la eficiencia algorítmica es una propiedad de un algoritmo que se relaciona con la cantidad de recursos computacionales utilizados por el algoritmo. Se debe analizar un algoritmo para determinar su uso de recursos, y la eficiencia de un algoritmo se puede medir en función del uso de diferentes recursos. La eficiencia algorítmica puede considerarse análoga a la productividad de la ingeniería para un proceso continuo o repetido.
Para lograr la máxima eficiencia, deseamos minimizar el uso de recursos. Sin embargo, diferentes recursos, como la complejidad del tiempo y el espacio , no se pueden comparar directamente, por lo que cuál de los dos algoritmos se considera más eficiente a menudo depende de qué medida de eficiencia se considere más importante.
Por ejemplo, la clasificación de burbujas y la clasificación de tiempo son algoritmos para ordenar una lista de elementos de menor a mayor. La clasificación de burbujas ordena la lista en el tiempo proporcional al número de elementos al cuadrado ( ver la notación Big O ), pero solo requiere una pequeña cantidad de memoria adicional que es constante con respecto a la longitud de la lista ( ). Timsort ordena la lista en el tiempo linealmente (proporcional a una cantidad multiplicada por su logaritmo) en la longitud de la lista ( ), pero tiene un requisito de espacio lineal en la longitud de la lista (). Si se deben ordenar listas grandes a alta velocidad para una aplicación determinada, timsort es una mejor opción; sin embargo, si es más importante minimizar la huella de memoria de la clasificación, la clasificación de burbujas es una mejor opción.
La importancia de la eficiencia con respecto al tiempo fue enfatizada por Ada Lovelace en 1843 como aplicada al motor analítico mecánico de Charles Babbage :
"En casi todos los cálculos es posible una gran variedad de arreglos para la sucesión de los procesos, y varias consideraciones deben influir en las selecciones entre ellos para los propósitos de un motor de cálculo. Un objeto esencial es elegir el arreglo que tenderá a reducirse a un mínimo del tiempo necesario para completar el cálculo " [1]
Las primeras computadoras electrónicas estaban severamente limitadas tanto por la velocidad de las operaciones como por la cantidad de memoria disponible. En algunos casos se advirtió que había una compensación espacio-tiempo , por la cual una tarea podía manejarse usando un algoritmo rápido que usaba bastante memoria de trabajo, o usando un algoritmo más lento que usaba muy poca memoria de trabajo. . La compensación de la ingeniería fue entonces utilizar el algoritmo más rápido que cabría en la memoria disponible.