Métodos para disminuir la complejidad de algoritmos.
Estoy intentando programar una función que tome un número entero no negativo y devuelva una lista de pares de números enteros no negativos cuyos valores, al ser elevados al cuadrado, suman el número dado.
Ejemplos:
5 -> [ [1, 2] ]
25 -> [ [0, 5], [3, 4] ]
325 -> [ [1, 18], [6, 17], [10, 15] ]
Mi solución funciona en un entorno de desarrollo integrado (IDE), pero cuando lo envío a codewars, recibo el código de salida de error 139: FATAL ERROR: invalid table size Allocation failed – JavaScript heap out of memory. La documentación de codewars indica que esto se debe a un algoritmo ineficiente.
Inicialmente, mi solución contenía un bucle anidado que causaba un largo tiempo de ejecución, pero desde entonces he refactorizado mi código para eliminarlo. A pesar de esta reducción de complejidad, sigo obteniendo el mismo error.
¿Alguna sugerencia sobre cómo puedo disminuir aún más la complejidad?
const allSquaredPairs = (n) => {
// Obtener un array de todos los números entre 0 y la raíz cuadrada de n
let possibleNums = Array(n)
.fill()
.map((_, i) => {
if ((i + 1) ** 2 <= n) return i + 1; // Solo números menores que la raíz cuadrada de n
})
.filter(n => n!=undefined)
possibleNums = [0, ...possibleNums];
const matchingPairs = [];
while (possibleNums.length){
const num1 = possibleNums[0];
const num2 = possibleNums[possibleNums.length-1];
const sum = num1 ** 2 + num2 ** 2
if (sum === n) matchingPairs.push([num1, num2]);
if (sum > n ) possibleNums.pop()
else possibleNums.shift()
}
return matchingPairs;
};
console.log(allSquaredPairs(25));
davy.ai
Una posible forma de disminuir aún más la complejidad de esta función es utilizar una técnica de doble puntero para iterar a través de los posibles valores de las parejas. En este enfoque, podemos comenzar con los valores más pequeños y más grandes del arreglo possibleNums y verificar la suma de sus cuadrados. Si la suma es mayor que el número objetivo, movemos el puntero derecho hacia la izquierda; de lo contrario, movemos el puntero izquierdo hacia la derecha. De esta manera, podemos evitar iterar a través de todas las combinaciones posibles y reducir la complejidad temporal a O(sqrt(n)). Aquí hay una posible implementación de este enfoque:
Esta versión de la función debería tener una complejidad temporal mucho más baja y debería ser capaz de manejar entradas más grandes sin quedarse sin memoria. Si aún encuentras problemas, puedes considerar dividir la entrada en fragmentos más pequeños y procesar cada fragmento por separado.