¿Cuál es la complejidad espacial del algoritmo?
La complejidad espacial de los algoritmos recursivos generales es O(n), porque la información devuelta se almacena en cada recursión. La calidad de un algoritmo se mide principalmente desde dos aspectos: el tiempo de ejecución del algoritmo y el espacio de almacenamiento requerido.
El espacio de almacenamiento ocupado por el algoritmo en la memoria de la computadora incluye tres aspectos: el espacio de almacenamiento ocupado por el algoritmo en sí, el espacio de almacenamiento ocupado por los datos de entrada y salida del algoritmo y el espacio de almacenamiento temporal. ocupado por el algoritmo cuando se está ejecutando. El espacio de almacenamiento ocupado por los datos de entrada y salida del algoritmo está determinado por el problema a resolver y lo pasa la función que llama a través de la tabla de parámetros.
No cambia con este algoritmo. El espacio de almacenamiento ocupado por el algoritmo de almacenamiento en sí es proporcional a la duración de la escritura del algoritmo. Para comprimir el espacio de almacenamiento en esta área, se debe escribir un algoritmo más corto. El espacio de almacenamiento temporal ocupado por el algoritmo varía de un algoritmo a otro. Algunos algoritmos solo necesitan ocupar una pequeña cantidad de unidades de trabajo temporales y no cambian con el tamaño del problema.
A este algoritmo lo llamamos algoritmo "en vivo", que es un algoritmo que ahorra espacio de almacenamiento. El número de unidades de trabajo temporales que algunos algoritmos deben ocupar está relacionado con la escala de resolución de problemas n, y aumenta con el aumento de n. Cuando n es mayor, se ocuparán más unidades de almacenamiento, como los algoritmos de clasificación rápida y clasificación por fusión. .