Este problema es muy sencillo, simplemente hay que iterar entre todos los valores posibles para los dos coeficientes (-999 <= a <= 999 y -1000 <= b <= 1000) y comprobar cuántos números primos consecutivos permite calcular el polinomio n2 + an + b.
La primera implementación es sencilla y bastante rápida, apenas unos segundos. Pese a que es un problema con un orden de complejidad polinómico por definición (cuadrático para las posibles combinaciones de a y b más otros ciclo para comprobar los números primos), dado que los valores del programa son pequeños, se resuelve en un tiempo razonable.
Pero claro, siempre se quiere optimizar. Así que pensé "si al comprobar si un número es primo o no, puedo tenerlos ya guardados en una lista y así no tengo que calcular lo mismo una y otra vez".
Veamos la implementación, sólo cambia lo siguiente: una lista de números primos inicialmente vacía y una comprobación previa. El resto del código es igual. Sin embargo, al ejecutarlo, nos encontramos con que tarda bastante más tiempo.
¿Qué ha pasado? Fácil, que la supuesta optimización ha resultado ser peor. Con pensar 5 segundos se da uno cuenta por qué: cada vez que queremos saber si un número es primo debemos buscarlo en una lista que cada vez es más grande. Además, debemos asignar memoria y hacer diversas operaciones internas en la lista para redimensionarla al añadir un nuevo elemento. Desconozco la implementación exacta de la búsqueda en listas de Python, pero no puede ser mejor que del orden de O(log n).
Otra forma de crear esta caché de números primos es utilizar un diccionario Python, que requiere menos manejo de memoria, pero la verdad, la mejora, para las dimensiones de este problema, es mínima.
Conclusión: si optimizas, ten cuidado, no sea que lo estropees.
No hay comentarios:
Publicar un comentario