¿Por qué la teoría de la complejidad computacional es un campo importante y cuáles son algunos sistemas / productos interesantes que se crean a partir de ella?

En informática, el análisis de algoritmos es la determinación de la cantidad de tiempo, almacenamiento y / u otros recursos necesarios para ejecutarlos. Por lo general, esto implica determinar una función que relaciona la longitud de la entrada de un algoritmo con el número de pasos que toma (su complejidad de tiempo) o el número de ubicaciones de almacenamiento que usa (su complejidad de espacio). Se dice que un algoritmo es eficiente cuando los valores de esta función son pequeños. Dado que las diferentes entradas de la misma longitud pueden hacer que el algoritmo tenga un comportamiento diferente, la función que describe su rendimiento suele ser un límite superior del rendimiento real, determinado a partir de las entradas del algoritmo en el peor de los casos.

El término “análisis de algoritmos” fue acuñado por Donald Knuth.

El análisis de algoritmos es una parte importante de una teoría de la complejidad computacional más amplia, que proporciona estimaciones teóricas de los recursos necesarios para cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones proporcionan una idea de las direcciones razonables de búsqueda de algoritmos eficientes.

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. La notación Big O, la notación Big-omega y la notación Big-theta se utilizan para este fin. Por ejemplo, se dice que la búsqueda binaria se ejecuta en varios pasos proporcionales al logaritmo de la longitud de la lista ordenada que se busca, o en O (log (n)), coloquialmente “en tiempo logarítmico”. Por lo general, se utilizan estimaciones asintóticas porque diferentes implementaciones del mismo algoritmo pueden diferir en eficiencia. Sin embargo, las eficiencias de dos implementaciones “razonables” de un algoritmo dado están relacionadas por un factor multiplicativo constante llamado constante oculta .

Las medidas exactas (no asintóticas) de eficiencia a veces se pueden calcular, pero generalmente requieren ciertas suposiciones sobre la implementación particular del algoritmo, llamado modelo de cálculo. Un modelo de cálculo puede definirse en términos de una computadora abstracta, por ejemplo, una máquina de Turing, y / o postulando que ciertas operaciones se ejecutan en unidades de tiempo. Por ejemplo, si la lista ordenada a la que aplicamos la búsqueda binaria tiene n elementos, y podemos garantizar que cada búsqueda de un elemento en la lista se puede hacer en unidades de tiempo, entonces, como máximo, se necesitan log2 n + 1 unidades de tiempo para regresar una respuesta.