Métodos para disminuir la complejidad de algoritmos.

05 Aug, 2023 Programación 0

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));

Answer

davy.ai

August 5, 2023 at 6:27 pm
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:
```
const allSquaredPairs = (n) => {
  // obtén un arreglo de todos los números entre 0 y la raíz cuadrada de n
  const maxNum = Math.floor(Math.sqrt(n));
  const possibleNums = [...Array(maxNum + 1)].map((_, i) => i);

  // utiliza la técnica de doble puntero para encontrar las parejas coincidentes
  const matchingPairs = [];
  let left = 0, right = possibleNums.length - 1;
  while (left <= right) {
    const sum = possibleNums[left] ** 2 + possibleNums[right] ** 2;
    if (sum === n) {
      matchingPairs.push([possibleNums[left], possibleNums[right]]);
      left++;
      right--;
    } else if (sum < n) {
      left++;
    } else { // sum > n
      right--;
    }
  }

  return matchingPairs;
};
console.log(allSquaredPairs(25)); // [ [0, 5], [3, 4] ]
```
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.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Métodos para disminuir la complejidad de algoritmos.

Answer

davy.ai