Estoy trabajando para resolver un problema de algoritmo cuyo indicador es este:
"Dada una cadena s, encuentre la longitud de la subcadena más larga sin repetir caracteres".
Tengo dos soluciones aceptadas que se muestran a continuación:
function lengthOfLongestSubstring(s: string): number { let longestStr = ''; let maxLength = 0; for (let i = 0; i < s.length; i += 1) { //solution 1 if (longestStr.split('').includes(s[i])) { longestStr = longestStr.slice(longestStr.split('').indexOf(s[i]) + 1); } longestStr += s[i]; if (longestStr.length > maxLength) {maxLength = longestStr.length} // solution 2 longestStr += s[i]; if(longestStr.indexOf(s[i]) !== longestStr.length - 1) { longestStr = longestStr.slice(longestStr.indexOf(s[i]) + 1) } if (longestStr.length > maxLength) {maxLength = longestStr.length} } return maxLength;}
La diferencia entre las dos soluciones es si introducir este código antes o después de las declaraciones if.
longestStr += s[i];La única diferencia en el código que contribuiría a la complejidad de tiempo/espacio es el código dentro de las declaraciones if respectivas.
La solución 1 tiene un rendimiento mucho mejor: 214 ms, 44,9 MB
Solución 2 significativamente peor: 607ms, 47MB
Solución 1: De acuerdo con el tiempo de ejecución del método string.Split, el método .split tiene una complejidad de tiempo O(n). El método .includes debe tener O(n) ya que se repite una vez.
Solución 2: De acuerdo con ¿Cuál es la complejidad de tiempo de array.indexOf de javascript? , .indexOf tiene O(n). .length es un método accesible dentro de todos los objetos Javascript enumerables (matrices), y la búsqueda en una matriz es O (1).
A menos que mis complejidades de tiempo anteriores sean incorrectas, parece que la solución 2 tomaría menos tiempo. Sin embargo, es todo lo contrario.
Por favor, ayúdame a entender, gracias.
Estás bien. La solución 1 debería funcionar mucho peor. Y lo hace, al menos según mis pruebas:
function lengthOfLongestSubstring(s) { let longestStr = '' let maxLength = 0 for (let i = 0; i < s.length; i += 1) { //solution 1 if (longestStr.split('').includes(s[i])) { longestStr = longestStr.slice( longestStr.split('').indexOf(s[i]) + 1 ) } longestStr += s[i] if (longestStr.length > maxLength) { maxLength = longestStr.length } } return maxLength } function lengthOfLongestSubstring2(s) { let longestStr = '' let maxLength = 0 for (let i = 0; i < s.length; i += 1) { // solution 2 longestStr += s[i] if (longestStr.indexOf(s[i]) !== longestStr.length - 1) { longestStr = longestStr.slice(longestStr.indexOf(s[i]) + 1) } if (longestStr.length > maxLength) { maxLength = longestStr.length } } return maxLength } let s1 = '' const slen = 1000000 const letters = 'abcdeghijklmnop' for (let i = 0; i < slen; i++) { s1 = s1 + letters[Math.random() * letters.length] } console.time('solution1') console.log(lengthOfLongestSubstring(s1)) console.timeEnd('solution1') console.time('solution2') console.log(lengthOfLongestSubstring2(s1)) console.timeEnd('solution2') // result: solution 1: 1.484s, solution 2: 317ms¿Ves lo mismo?