Complejidad en el espacio

Complejidad Espacial

Es la memoria que utiliza un programa para su ejecucion.
Lo que implica que la eficiencia, en memoria de un algoritmo
lo indica la cantidad de espacios requeridos para ejecutarlo
es decir, el espacio en memoria que ocupan todas las variables
propias del algoritmo.




EJEMPLO

Algoritmo de busqueda en arboles.

---funcion busqueda_arboles(problema (entra aki raiz))
---devuelve solucion/fallo
---inicializa arbol de busqueda con estado inicial
---ciclo hacer (ciclo do)
---si no hay candidatos para para expandir(si no existe el nodo fallo)
---entonces devolver fallo
++---en otro caso escoger nodo para expandir ( (insquiera ponen los menores y a la derecha los mayores si es mayor o menos a la raiz es para donde se va)si el que queremos expandir es mayo a la derecha si no a la izquierda)
---el nodo es el objetivo
---entonces devolver solucion
---en otro caso expandir nodo [si hay se regresa ++]



Simulación

==RESULTADOS OBTENIDOS==

Depth Nodes Time(tiempo) Memory (espacio)
0 1 1 millisecond 100 bytes
2 111 .1 seconds 11 kilobytes
9 11,111 11 seconds 1 megabyte
6 10^6 18 minutes 111 megabyte
8 10^8 31 hours 11 gigabytes
10 10^10 128 days 1 terabyte
12 10^12 35 years 111 terabytes




==Nota==
Factor de ramificacion-> 10 nodos sucesores p/cada uno como maximo
profundidad del arbol-> infinito