Por lo general, la complejidad del espacio es mucho más fácil de calcular que la complejidad del tiempo. Pero si tiene una idea acerca del cálculo de la complejidad del tiempo, puede aplicar exactamente las mismas reglas para la complejidad del espacio.
Aproximadamente, ¿cómo se calcula la complejidad del tiempo? Usted calcula la cantidad de operaciones que realiza su programa. ¿Qué tiene de diferente la complejidad del espacio? Calcula el número de operaciones de asignación. Eso es.
Pero en muchos casos la asignación es bastante fácil, solo asigna algunas matrices al comienzo de su código, justo después de la entrada.
- ¿Qué algoritmo se pregunta en la entrevista de Google?
- ¿Por qué mi código solo pasa números pequeños y no los grandes (con respecto a subconjuntos no divisibles)?
- Si podemos ordenar datos usando SQL, ¿por qué necesitamos estudiar diferentes algoritmos de ordenación?
- ¿Cuál es el mejor algoritmo para implementar la función next_permutation sin STL?
- Cómo implementar la ordenación de inserción recursiva usando una lista vinculada
También aquí hay un truco, la complejidad del espacio nunca es mayor que la complejidad del tiempo, porque, según mi definición aproximada, la complejidad del tiempo es el número de todas las operaciones que realiza su programa y la complejidad del espacio es el número de operaciones de asignación que realiza su programa. Estas operaciones forman un subconjunto en el conjunto de todas las operaciones.
Por ejemplo, si mantiene un vector y agrega elementos [math] n [/ math] a su final, la complejidad temporal de esto es [math] O (n) [/ math]. (¿Puede probar esto?) Según la observación en el párrafo anterior, la complejidad espacial del algoritmo también es O (n). Pero el vector final contiene elementos [math] \ Omega (n) [/ math] y, por lo tanto, la complejidad del espacio es [math] \ Theta (n) [/ math]
