El problema : encuentre varias formas posibles desde la esquina superior izquierda hasta la esquina inferior derecha en la cuadrícula MxN mientras solo puede moverse hacia abajo o hacia la derecha.

Aquí hay dos algoritmos que he escrito. Los resultados se ven bien, pero no puedo descifrar la complejidad del tiempo y el espacio, tengo algunas conjeturas sobre cuáles podrían ser las complejidades, pero no puedo probarlas de una manera "adecuada".

Algoritmo ingenuo:

 function gridTravel(m, n) { if(m<1 || n<1) return 0; if (m === 1 || n === 1) return 1; return gridTravel(m-1, n) + gridTravel(m, n-1); }; console.log(gridTravel(10,10));

Mis conjeturas :

• Complejidad espacial - O(n+m)? La pila de llamadas más larga posible parece escalar "linealmente", por lo que, suponiendo una aproximación, sería O (n + m), pero realmente no puedo probarlo o refutarlo.
• La complejidad del tiempo es exponencial porque cada posición puede crear 2 nuevas posiciones: O (2 ^ n) u O (2 ^ n + m), no estoy seguro de cuál es más adecuado.

 m:n m-1:nm:n-1 m-2:n m-1:n-1 m-1:n-1 m:n-2

Pero nuevamente, no me siento seguro con esta explicación porque no es un árbol simétrico, simplemente lo parece al principio.

Algo ingenuo + memorización:

 seenGrids = {}; const gridTravel = (m, n) => { if(m<1 || n<1) return 0; if (m === 1 || n === 1) return 1; if (`${m}:${n}` in seenGrids || `${n}:${m}` in seenGrids) { return seenGrids[`${m}:${n}`] || seenGrids[`${n}:${m}`]; } seenGrids[`${m}:${n}`] = gridTravel(m-1, n) + gridTravel(m, n-1); return seenGrids[`${m}:${n}`]; };

Mis conjeturas:

• Espacio - O(n*m)? La pila de llamadas todavía parece ser lineal, pero ahora tenemos este objeto en crecimiento que se ve en las seenGrids que, según mi intuición, ¿debería escalar de forma cuadrática? No tengo idea de cómo probarlo o refutarlo, cuando ejecuté console.log(Object.keys(seenGrids).length) para una cuadrícula de 200x200 , obtuve 19900 , que no es ni m*n ni m+n , por lo que es lineal. o cuadrático?
• Tiempo - O(n*m)? - esto es lo más difícil para mí entenderlo. Ya no debería ser exponencial porque se omiten muchos subárboles gracias a las respuestas guardadas, pero no tengo idea de cómo derivar la complejidad del tiempo de una manera "adecuada".