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 (e.g. complejidad temporal, complejidad espacial) no pueden ser comparadas directamente, luego, cuál de dos algoritmos es considerado más eficiente, depende de cuál medida de eficiencia se está considerando como prioridad, e.g. 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.

Note que este artículo no trata de optimización, concepto que es abordado en optimización de programas, compiladores de optimización, optimización de bucles, optimización de códigos orientados a objetos, etc. El término optimización en sí puede causar confusión, ya que todo lo que generalmente se puede hacer es en realidad una 'mejora'.

Conocimiento previo 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. Un objetivo esencial es escoger la configuración que tienda a minimizar el tiempo necesario para completar el cálculo."

Las primeras computadoras electrónicas estaban considerablemente limitadas tanto por la velocidad de procesamiento como por la cantidad de memoria disponible. En algunos casos se notó que existía una renunciación espacio-tiempo (tradeoff), por lo cual una tarea podía ser tratada usando tanto un algoritmo eficiente en cuanto a tiempo pero que utiliza gran cantidad de memoria activa como un algoritmo más lento pero que utiliza poca memoria activa. La ingeniería de 'tradeoff' fue entonces para usar el algoritmo más rápido que se acomodara en la memoria disponible.

Las computadoras modernas son mucho más rápidas que las primeras computadoras, y cuentan con cantidades muy superiores de memoria disponible (Gigabytes en vez de Kilobytes). No obstante, Donald Knuth enfatizó que la eficiencia sigue siendo un tema importante a considerar:

"En disciplinas de ingeniería establecidas, un 12% de mejoría obtenido con facilidad, nunca es considerado un resultado marginal, y creo que el mismo punto de vista prevalece para la ingeniería de software."

Introducción Un algoritmo es considerado eficiente si su consumo de recursos está en la media o por debajo de los niveles aceptables. Hablando a grandes rasgos, 'aceptable' significa: que el algoritmo corre en un tiempo razonable en una computadora dada. Desde 1950 hasta la actualidad las computadoras han tenido un avance impresionante tanto en poder computacional como en la capacidad de memoria disponible, lo que indica que los niveles aceptables de eficiencia en la actualidad hubieran sido inadmisibles 10 años atrás.

Los fabricantes de computadoras están frecuentemente lanzando nuevos modelos, normalmente con mejor rendimiento. El costo de mejorar el software puede ser bastante caro, por ello en muchos casos la forma más simple y barata de alcanzar un mejor rendimiento es comprar una computadora con mejor rendimiento de por sí.

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 (i.e. la cantidad de datos a ser procesados); además podrían depender de la forma en que los datos están organizados (e.g. 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.

Análisis Teórico En el estudio teórico de un algoritmo, lo normal es estimar su complejidad de forma asintótica, i.e. usar notación O grande para representar la complejidad de un algoritmo como una función que depende del tamaño de la entrada n, esto es generalmente acertado cuando n es lo suficientemente grande, pero para n pequeños podría ser erróneo (e.g. bubble sort puede ser más rápido que quicksort cuando solo unos pocos valores deben ser ordenados).

Algunos ejemplos de notación de O grande incluyen:

Notación Nombre Ejemplos constante Determinar si un número es par o impar. Usar una tabla de consulta que asocia constante/tamaño. Usar una función hash para obtener un elemento. logarítmico Buscar un elemento específico en un array utilizando un árbol binario de búsqueda o un árbol de búsqueda balanceado, así como todas las operaciones en un Heap binomial. lineal Buscar un elemento específico en una lista desordenada o en un árbol degenerado (peor caso). loglinear o quasilinear Ejecutar una transformada rápida de Fourier; heapsort, quicksort (caso mejor y promedio), o merge sort cuadrático Multiplicar dos números de n dígitos por un algoritmo simple. bubble sort (caso peor o implementación sencilla), Shell sort, quicksort (caso peor). exponencial Encontrar la solución exacta al problema del viajante utilizando programación dinámica. Determinar si dos sentencias lógicas son equivalentes utilizando una búsqueda por fuerza bruta

Benchmarking: midiendo la eficiencia Benchmarks (desc. estándar de comparación, cota de referencia, punto de referencia, conjunto de procedimientos para avaluar el rendimiento de un ordenador) son usados para realizar comparaciones entre programas en competencia o para probar versiones nuevas de software que se quiera liberar, y sirve como indicador relativo para medir la eficiencia de un algoritmo. Si un nuevo algoritmo de ordenación es implementado, por ejemplo puede ser comparado con su predecesor para asegurar su eficiencia al menos con los datos conocidos o recopilados por este último, teniendo en cuenta claro las mejoras funcionales del nuevo algoritmo. Los benchmarks pueden ser utilizados por los clientes para comparar varios productos de diferentes proveedores con el objetivo de estimar cuál producto satisface sus necesidades en términos de eficiencia.

Algunos benchmarks prestan servicios para producir comparaciones detalladas sobre la velocidad relativa de varios lenguajes compilados e interpretados, por ejemplo, The Computer Language Benchmarks Game compara la eficiencia entre una gran variedad de lenguajes sobre la implementación de problemas típicos de programación.

Detalles de implementación Los detalles de implementación también tienen un efecto sobre la eficiencia, como la elección de un lenguaje de programación, o la forma en que el algoritmo está actualmente implementado, o la elección de un compilador para un lenguaje particular, incluso el sistema operativo que se está usando. En algunos casos un lenguaje interpretado pudiera ser mucho más lento que uno compilado.

Existen otros factores que pueden afectar la eficiencia temporal y espacial, y que pueden estar fuera del control del programador, entre estos están: granularidad de los datos, recolector de basura, paralelismo a nivel de instrucción, y llamadas a subprocesos.Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.

Algunos procesadores tienen la capacidad de procesado vectorial, lo que permite que una instrucción se capaz de operar sobre varios datos; puede ser fácil o no para un programador o un compilador usar estas herramientas. Los algoritmos diseñados para ser procesados de forma secuencial necesitarían ser completamente rediseñados para hacer uso del procesamiento en paralelo.

Otro detalle de implementación importante referente a los procesadores aparece cuando estos implementan una instrucción de forma diferente, o sea que una instrucción que es relativamente rápida en algunos modelos podría ser más lenta en otros, esto hace difícil el trabajo para un compilador guiado a la optimización.

Medidas del uso de recursos

Las medidas de eficiencia son normalmente expresadas en función del tamaño de la entrada n.

Las dos medidas más comunes son: Complejidad temporal: cuanto se demora un algoritmo en terminar. Complejidad espacial: cuanta memoria operativa (RAM usualmente) es requerida por el algoritmo. Esto tiene dos apartados, la cantidad de memoria que necesita el código y la cantidad que necesitan los datos sobre los que opera el algoritmo.

Para computadoras cuya energía es por batería (e.g. laptops), o para grandes cálculos (e.g. supercomputadoras) otras medidas también son de interés: Consumo directo de energía: energía requerida por la computadora. Consumo indirecto de energía: energía requerida para el enfriamiento, la iluminación, etc.

En algunos casos otras medidas podrían ser relevantes: Capacidad de transmisión: el ancho de banda puede llegar a ser un factor limitante. La compresión de datos es utilizada para reducir la cantidad de datos a transmitir. Espacio externo: cantidad de espacio requerido en disco o algún otro dispositivo externo; esto podría ser solo una necesidad temporal, o sea solo se requiere dicho espacio mientras está corriendo e algoritmo o podría ser una necesidad a largo plazo para futuras referencias. Tiempo de respuesta: Esto es particularmente relevante en tiempo real para una aplicación cuando el sistema de la computadora debe responder de forma rápida a los eventos externos.

Complejidad temporal

Teoría

Para analizar un algoritmo generalmente se usa la complejidad temporal para obtener un estimado del tiempo de ejecución expresado en función del tamaño de la entrada. El resultado es típicamente expresado en notación O grande. Esto suele ser útil para comparar algoritmos, especialmente cuando se necesita procesar una gran cantidad de datos. Estimaciones más detalladas se requieren para comparar algoritmos que procesan pequeñas cantidades de datos (de todas formas en estos casos el tiempo no debería ser un problema). Algoritmos implementados para usar procesamiento paralelo de los datos son mucho más difíciles de analizar.

En la práctica

Se utilizan benchmarks para medir el uso de un algoritmo. Muchos lenguajes de programación presentan funciones para medir el tiempo de uso del procesador. En casos de algoritmos que se ejecutan en un tiempo considerablemente largo, dicho tiempo pudiera resultar de interés. El resultado es generalmente un promedio de los resultados de varias pruebas consecutivas aplicadas sobre el objetivo.

Este tipo de pruebas son altamente sensibles a configuraciones de hardware y existe la posibilidad de que otros programas se estén ejecutando al mismo tiempo en un ambiente capaz de procesar varias tareas a la vez.

Dichas pruebas también dependen intrínsecamente del lenguaje de programación, el compilador y las opciones del compilador, lo que implica que dos algoritmos que se comparan deberán estar implementados bajo las mismas condiciones.

Complejidad espacial