Por Lizandro Ramírez.
Estos ejercicios que presentaremos a continuación se fundamentan en la estrategia Slinding Windows. Esta se aplica a problemas donde sea necesario recorrer una lista de elementos en donde tengas que buscar o calcular algo a partir de sub arreglos con elementos consecutivos de un tamaño k elementos.
Dado un arreglo, encuentra el promedio de todos los sub arreglos de tamaño k.
Input: arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]; k= 5
Output: [ 2.2, 2.8, 2.4, 3.6, 2.8]
Este problema puede tener varias soluciones posibles que pueden ser validas, en esta introducción tomaremos dos soluciones posibles, una solución que no sigue ninguna estrategia en particular que le llamaremos fuerza bruta (FB) y otra solución que si sigue una estrategia en este caso Sliding Windows (SW). Con estas dos estrategias vamos a resaltar la importancia de tener un plan a seguir bien pensado para resolver este tipo de problemas.
Estrategia de Fuerza Bruta:
La primera idea que nos llega a la mente para resolver este problema, es usar ciclos anidados. El primer ciclo recorre los elementos del arreglo desde el índice 0 hasta (tamaño del arreglo - k)+1. El ciclo anidado recorre los elementos con una relación de k, haciendo las operaciones correspondientes para obtener el promedio.
let promSubKFB = (arr, k) => {
let len = arr.length,
sum,
operaciones = 0,
prom = [];
for (let i = 0; i < len - k + 1; ++i) {
sum = 0;
for (let j = 0; j < k; ++j) {
sum += arr[i + j];
operaciones++;
}
prom.push(sum / k);
}
console.log("n-k:", len - 5, "Operaciones:", operaciones);
return prom;
};Esta estrategia nos arroja que para un n = 9 tendremos 25 operaciones, para el escenario de pruebas anterior, claramente la O(n*m) es la big O que representa esta solución donde m representa él (tamaño del arreglo -k) y m el tamaño del sub arreglo k. En definitiva se puede decir que es un O(n²) algo que no resulta ser una solución muy eficiente.
En la siguiente solución implementamos la estrategia de sliding windows, esta estrategia busca eliminar el ciclo interno de la solución presentada por fuerza bruta. La idea principal se basa en ir sacando el último elemento de la ventana y agregando el siguiente, solo hay que tener en consideración los índices de los elementos a sacar cuando el arreglo ha recorrido el tamaño de k en adelante.
El centro de la estrategia esta en esta parte del código, en donde se realiza la salida de un elemento desde que i alcanza el valor de k:
En la solución usando la estrategia de sliding windows podemos notar que las operaciones se reducen a 5, siendo mucho menos operaciones que sin usar una estrategia. Los dos algoritmos llegan al mismo resultado pero su eficiencia es muy distinta. La big O de este algoritmo con la estrategia de Sliding Windows es O(n).
En esta parte del proyecto es bueno aprender a usar las herramientas de debugger para visual studio code así pueden ver paso a paso como trabajan estos dos algoritmos.