¿Existe un algoritmo para la optimización de la complejidad del tiempo / espacio de los algoritmos?

9

En la década de 1950 se inventaron varios métodos para la minimización de circuitos para funciones booleanas . ¿Existe una extensión de esos métodos o algo similar para optimizar el tiempo o la complejidad espacial de los algoritmos?

Por ejemplo, una implementación de clasificación de burbujas como entrada para dicho algoritmo produciría una implementación de un algoritmo de clasificación con una complejidad de tiempo más cercana aO(norteIniciar sesión⁡norte).

algorithms turing-machines time-complexity optimization space-complexity Optimizador
fuente
1
¡¡Vete!! Los profesionales de CS ganamos la vida enseñando algoritmos sofisticados, ¡su sugerencia nos dejaría sin trabajo!
vonbrand
Bueno ... ¿qué esperas de la IA entonces?
Optimizador
El ordenamiento de burbujas no es una función booleana. Peor aún, ¡no todos los algoritmos de clasificación son equivalentes! Por ejemplo, algunos no son estables.
Yuval Filmus
Tienes toda la razón, pero el tipo de burbuja y el "buen tipo" es solo un ejemplo de lo que veo como entrada y salida, no nos concentremos en los detalles.
Optimizador
@YuvalFilmus seguramente devolver una matriz ordenada no es más fácil que devolver verdadero o falso
vonbrand

Respuestas:

11

Consulte el teorema de aceleración de Blum (sí, este artículo es poco informativo; consulte un libro sobre teoría de la complejidad). Básicamente dice que hay programas para los que hay un programa que hace el mismo trabajo que es más rápido por cualquier margen especificado para casi todos los datos de entrada.

Según el teorema de Rice , es imposible saber si dos programas dados hacen el mismo trabajo.

Sí, para algunas nociones muy restringidas de "programa", dado un ejemplo, se puede construir el "mejor programa posible" para el trabajo. Clases importantes, incluso. Pero muy lejos de cualquier cosa que sea capaz de expresar bubbleort.

vonbrand
fuente