¿Por qué estudiar la teoría de la complejidad?

Question

Soy un aficionado en el estudio de los algoritmos. Por un tiempo, he tenido una pregunta incendiada, por qué ¿Estudiamos la teoría de la complejidad en la informática? La razón por la que pregunto es porque los algoritmos con mejor complejidad asintótica no siempre son más rápidos con fines prácticos, de hecho, pueden ser absurdamente más lentos. ¿Por qué no desarrollar una teoría que mejor se adapte a las necesidades prácticas de la investigación científica y la industria?

Como ejemplo, se sabe que el desarrollo de un algoritmo para determinar un juego de ajedrez perfecto se puede realizar en $ o (1) $ , como el número de legal Los juegos de ajedrez en una cuadrícula de 8 × 8 están limitados desde arriba. Sin embargo, he escuchado que este algoritmo tardaría más de la edad del universo para terminar. Esto plantea la pregunta, ¿por qué la teoría de la complejidad? Me parece que el campo es fundamentalmente defectuoso, y los científicos informáticos deben estar usando un mejor enfoque para el estudio de los algoritmos.

(Nota: mis sinceras disculpas a los investigadores en el campo. ☻)

Answer 1

Esta no es una pregunta simple, y no debe esperar una respuesta simple. Hay una gama de preguntas similares en este espacio: ¿Por qué estudiamos el tiempo de funcionamiento asintótico? ¿Por qué usamos el análisis de tiempo de funcionamiento asintótico para analizar algoritmos? ¿Por qué estudiamos la teoría de la complejidad? Cada uno de ellos tiene múltiples respuestas; No hay una sola razón por la que lo hacemos, y diferentes personas pueden tener diferentes razones.

El análisis de tiempo de funcionamiento asintótico tiene ventajas y desventajas. Ha identificado con precisión una de las desventajas: un buen tiempo de funcionamiento asintótico no garantiza un buen tiempo de funcionamiento en la práctica. Pero si se enfoca en una sola ventaja o desventaja, no va a obtener la imagen completa de las fortalezas y debilidades de ese estilo de análisis. Algunas de las ventajas son que el análisis es relativamente manejable, no es específico para una arquitectura en particular, proporciona información útil sobre escalabilidad, y al menos parte del tiempo que tiene un poder predictivo útil para identificar cuellos de botella algorítmica. Por ejemplo, la diferencia entre un $ o (n ^ 2) $ algoritmo de tiempo y un $ o (n \ log n ) $ El algoritmo de tiempo a menudo puede ser significativo, incluso si estamos ignorando los factores constantes. Algunas de las desventajas son que los factores constantes pueden ser importantes, los efectos de la jerarquía de memoria y la memoria pueden ser muy importantes, ya que se ignoran el análisis de tiempo de funcionamiento asintótico, y (como cualquier métrico) que optimiza únicamente el tiempo de funcionamiento asintótico puede llevar a resultados absurdos de poco práctico Utilidad (consulte algoritmos galácticos y la ley de Goodhart ).

Creo que también es útil examinar la alternativa. Le animo a explorar la alternativa al análisis de tiempo de funcionamiento asintótico y trabajar a través de lo que se propuso en su lugar. Si no intenta encontrar una propuesta concreta, es fácil asumir que no puede ser tan difícil encontrar algo mejor ... pero cuando se ve obligado a comprometerse con algo específico, es posible que descubra que es Más desafiante de lo que anticipado. Por ejemplo, lo aliento a que se familiarice con el análisis de Knuth de algoritmo que corre el tiempo en MIX en su Serie TAOCP. Allí hace un análisis de tiempo de ejecución concreto, sin asintóticos, teniendo en cuenta los factores constantes. Si te obliga a trabajar a través de los detalles de eso, descubrirá rápidamente las desventajas de que: es super-tedioso, muy específico para una arquitectura de computadora en particular, y, a menudo, no es mucho más esclarecedor.

Podríamos discutir de manera similar cada uno de los otros temas: por ejemplo, por qué o por qué no estudiar la teoría de la complejidad, y encontrarías que también tienen matices.

También quiero resaltar para usted que la comunidad teórica y algoritmos es una amplia, con una gama de diferentes estilos de trabajo. Parece que lo está reduciendo en una sola pila, pero hay un espectro de trabajo: parte de eso es súper teórica y lejana de la práctica, algunos de ellos son altamente prácticos y motivados por problemas concretos y pueden tener un impacto inmediato, y Hay una gama de trabajo en varios puntos entre esos extremos. Creo que es importante comprender que hay algún trabajo en la comunidad de teoría que es de gran relevancia práctica o ha tenido un gran impacto, al igual que hay un trabajo mucho más teórico y no motivado por un impacto a corto plazo.

Desde que solicitó marcos teóricos que se centran en satisfacer las necesidades de la industria, también podría estar interesado en la > Word Ram modelo, algoritmos ajustes en caché , y el Memoria externa paralela modelo.

Le animo encarecidamente que lea los siguientes recursos, ya que están estrechamente relacionados con su pregunta: ¿Por qué el tiempo polinomial se llama " eficiente "? , Explicando la relevancia de la complejidad asintótica de los algoritmos a la práctica de diseñar algoritmos , Justificación para descuidar los factores constantes en BIG O .