Creo que aquí tienes conceptos confusos. Formalmente, la complejidad se define en términos de ejecutar un Algoritmo. Entonces, un algoritmo es más complejo cuando usa más recursos (tiempo y / o almacenamiento adicional) La complejidad de un Algoritmo, por lo tanto, un programa, es independiente de ser óptimo. Muchos algoritmos no óptimos tienen una complejidad muy alta. Puede imaginarse fácilmente haciendo un algoritmo de búsqueda con complejidad de tiempo cuadrático. Comprobar la complejidad del tiempo – Wikipedia
Así que creo que se pregunta si el conjunto de algoritmos óptimos es infinito. En otras palabras, si la cantidad de programas óptimos (no redundantes en su definición) es infinita.
Yo diría que sí , la cantidad de algoritmos óptimos es infinita porque hay un conjunto infinito de idiomas. La descripción de la máquina de Turing define un idioma, por lo que si cambia el idioma debe cambiar necesariamente la descripción de la máquina de Turing. Por lo tanto, necesariamente necesita al menos una máquina de Turing por idioma.
- ¿Cuál es el código MATLAB para realizar el algoritmo AntNet?
- ¿Por qué el algoritmo de búsqueda binaria no es adecuado para usar en una tabla con punteros?
- ¿Cómo funciona un árbol de expansión y cómo lo configuro?
- ¿Qué es mejor para la programación competitiva, la introducción del MIT a los algoritmos o los tutoriales de TopCoder?
- ¿Cuáles son algunos ejemplos bien conocidos donde se usa la programación dinámica?
Aclarando un poco más, algoritmos-> idiomas es una relación de muchos a uno . Por lo tanto, un idioma puede tener muchas máquinas de Turing, pero una máquina de Turing solo tendrá un idioma. Además, un idioma puede tener muchos algoritmos óptimos en términos de complejidad formal.
