Así que tengo este código aquí y solo estoy tratando de entender la complejidad del tiempo y el espacio.
para la complejidad del tiempo, creo que es O (n ^ 2) porque está pasando como máximo n - 1 bucles en el bucle while y pasará n veces en el bucle for, por lo que será O (n (n-1)) ) que es O (n ^ 2) y la complejidad del espacio creo que es O (n) porque es un espacio lineal.
No sé si estoy en lo cierto, pero si estoy equivocado, ¿alguien puede corregir mi pensamiento? Gracias por adelantado.
// Write your code here let visited = new Array(s.length).fill(false); let count = 0; for (let i = 0; i < s.length; i++) { let j = i + 1; visited[i] = true; while (j < s.length && s[j] === s[i] && !visited[j]) { visited[j] = true; count++; j++; } } return count;Esto es O(n) en complejidad de tiempo, porque:
while (j < s.length && s[j] === s[i] && !visited[j]) { Para que esta condición se cumpla, visited[j] debe ser falso, y cuando se cumple, entonces haces
visited[j] = true; Entonces, esa línea anterior solo puede ejecutarse tantas veces como elementos haya en la matriz visited . Si el ciclo while se ejecuta hasta el final de la primera iteración externa (cuando i es 0), nunca se ejecutará en ninguna de las otras iteraciones externas. Si el ciclo while se ejecuta a la mitad de la visited de la primera iteración y a la otra mitad de la segunda iteración, nunca se ejecutará para el resto de las iteraciones externas. Entonces, esta parte del código:
while (j < s.length && s[j] === s[i] && !visited[j]) { visited[j] = true; count++; j++; } nunca se ejecutará más tiempo que el total de veces visited.length .
El bucle exterior es, por supuesto, O(n) . Entonces, obtienes
outer loop: O(n) + inner loop: O(n) when summed over all iterations of the outer loop = O(n)