Eficiencia algorítmica

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."[1]

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."[2]

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
${\displaystyle O(1)\,}$	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.
${\displaystyle O(\log n)\,}$	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.
${\displaystyle O(n)\,}$	lineal	Buscar un elemento específico en una lista desordenada o en un árbol degenerado (peor caso).
${\displaystyle O(n\log n)\,}$	loglinear o quasilinear	Ejecutar una transformada rápida de Fourier; heapsort, quicksort (caso mejor y promedio), o merge sort
${\displaystyle O(n^{2})\,}$	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).
${\displaystyle O(c^{n}),\;c>1}$	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

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.

• quicksort El primer algoritmo de ordenación con un orden de ${\displaystyle O(n\log n)\,}$.
• heapsort Otro algoritmo de rápida ejecución.
• Búsqueda binaria Búsqueda en una tabla ordenada
• Algoritmo de Boyer-Moore para búsqueda de cadenas Buscar una cadena dentro de otra.

• David May FRS un Científico de la Computación Británico, actualmente Profesor de Ciencias de la Computación en la Universidad de Bristol además de ser fundador y CTO de XMOS Semiconductor, cree que la confianza en la Ley de Moore para resolver ineficiencias es uno de los problemas que existen. Él ha avanzado en una 'alternativa' a la ley de Moore (la ley de May), expresada como sigue:[7]

  La eficiencia del software se divide a la mitad cada 18 meses compensando la ley de Moore

  Continua expresando

  En sistemas ubicuos, dividiendo a la mitad el número de instrucciones ejecutadas se puede duplicar la vida de la batería y los grandes conjuntos de datos brindan grandes oportunidades para mejores softwares y algoritmos: Reducir el número de operaciones de N x N a N x log(N) tiene un efecto dramático para un N grande... para N = 30 billones, este cambio es equivalente a 50 años de mejoras tecnológicas

• El creador de Software Adam N. Roseenburge en su blog "The failure of the Digital computer", describió el estado actual de la programación como cercano al "Software event horizon"(Horizonte de eventos del Software), (aludiendo al ficticio "shoe event horizon"(horizonte del evento zapato o horizonte del zapato) descrito por Douglas Adams en su libro Hitchhiker's Guide to the Galaxy[8]).

Él estima que ha habido un factor de 70dB en pérdida de productividad o ""99.99999%, en su capacidad para funcionar correctamente"", desde los 1980—"Cuando Arthur C. Clarke comparó el estado de la computación en el 2001 a la computadora HAL en su libro 2001: A Space Odyssey, señaló cuan increíblemente pequeñas y poderosas computadoras había, pero cuan decepcionante se había vuelto la programación".

• Conrad Weisert brinda ejemplos, algunos de los cuales fueron publicados en el ACM SIGPLAN (Special Interest Group on Programming Languages (Grupo con interés especial en los lenguajes de programación)). Nótese en diciembre de 1995 en: "Atrocious Programming Thrives"[9]
• Marc Andreessen cofundador de Netscape es citado en "Mavericks at Work" (ISBN 0-06-077961-6) diciendo "Cinco programadores geniales pueden completamente superar a 1000 programadores mediocres."

Las siguientes competiciones dan admisión para los mejores algoritmos basados en algunos criterios arbitrarios decididos por los jueces:-

• Wired[10]

• Análisis de algoritmos - como determinar los recursos necesitados por un algoritmo
• Algoritmos de búsqueda binaria— una técnica simple y eficiente para búsqueda en arrays ordenados
• Benchmark— un método para medir la ejecución comparativa de los tiempos de ejecución para casos definidos
• Caso mejor, caso peor y caso average— Consideraciones para estimar los tiempos de ejecución en los tres casos
• Tabla de saltos— una técnica para reducir la longitud del camino de las instrucciones, el tamaño del código de máquina, (y usualmente el uso de memoria)
• Optimización del compilador— optimización referente al compilador
• Teoría de la complejidad computacional
• Indexado de Bases de datos— una estructura de datos que mejora la velocidad de recuperación de datos en una tabla de base de datos
• Codificación entrópica— Codificar los datos de manera eficiente usando la frecuencia de ocurrencia de cadenas como un criterio para sustitución
• Computación verde— una migración hacia tecnologías más 'verdes' consumiendo menos recursos
• Algoritmo de Huffman— un algoritmo para la codificación eficiente de datos
• Localidad de referencia— para evitar que el cache de la CPU se retrase por el acceso a memoria no local
• Manejo de Memoria
• Optimización
• Análisis de rendimiento— métodos para medir el rendimiento real de un algoritmo en tiempo de ejecución
• Computación en tiempo real— más ejemplos de aplicaciones que son dependientes del tiempo de manera crítica
• Análisis del tiempo de ejecución— estimación del tiempo esperado de ejecución y de la escalabilidad de los algoritmos
• Super-threading
• Ejecución especulativa o Ejecución impaciente
• Código con hilos— similar al método de tabla virtual o tabla de ramas

• Animation of the Boyer-Moore algorithm (Applet Java)
• "How algorithms shape our world". A TED Talk by Kevin Slavin.
• Misconceptions about algorithmic efficiency in high-schools