El análisis de algoritmos es una parte importante de la Teoría de
complejidad computacional más amplia, que provee estimaciones teóricas para los
recursos que necesita cualquier algoritmo que resuelva un problema
computacional dado. Estas estimaciones resultan ser bastante útiles en la
búsqueda de algoritmos eficientes.
A la hora de realizar un análisis teórico de algoritmos es común calcular
su complejidad en un sentido asintótico, es decir, para un tamaño de entrada
suficientemente grande. La cota superior asintótica, y las notaciones omega (cota
inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la
búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a
un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico".
Normalmente las estimaciones asintóticas se utilizan porque diferentes
implementaciones del mismo algoritmo no tienen porque tener la misma
eficiencia. No obstante la eficiencia de dos implementaciones
"razonables" cualesquiera de un algoritmo dado están relacionadas por
una constante multiplicativa llamada constante oculta.
La medida exacta (no asintótica) de la eficiencia a veces puede ser
computada pero para ello suele hacer falta aceptar supuestos acerca de la
implementación concreta del algoritmo, llamada modelo de computación. Un modelo
de computación puede definirse en términos de un ordenador abstracto, como la
Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una
unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una
búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda
binaria puede realizarse en un tiempo unitario, entonces se requieren como
mucho log2 N + 1 unidades de tiempo para devolver una respuesta.
Las medidas exactas de eficiencia son útiles para quienes verdaderamente
implementan y usan algoritmos, porque tienen más precisión y así les permite
saber cuanto tiempo pueden suponer que tomará la ejecución. Para algunas
personas, como los desarrolladores de videojuegos, una constante oculta puede
significar la diferencia entre éxito y fracaso.
Las estimaciones de tiempo dependen de cómo definamos un paso. Para que
el análisis tenga sentido, debemos garantizar que el tiempo requerido para
realizar un paso esté acotado superiormente por una constante. Hay que
mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con
que la suma de dos números se hace en un paso. Este supuesto puede no estar
garantizado en ciertos contextos. Si por ejemplo los números involucrados en la
computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la
adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo
que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para
hacerlo con enteros de 1000 dígitos).
No hay comentarios:
Publicar un comentario