Verificamos de forma exhaustivamente cada reseñas en nuestro espacio con el objetivo de enseñarte en todo momento información veraz y actual.
Solución:
Para responder a su pregunta, si tiene un algoritmo transversal para recorrer la lista que asigna un solo puntero para hacerlo, se considera que los algoritmos transversales tienen una complejidad de espacio O (1). Además, digamos que el algoritmo transversal no necesita 1 sino 1000 punteros, la complejidad del espacio aún se considera O(1).
Sin embargo, digamos que por alguna razón el algoritmo necesita asignar punteros ‘N’ cuando recorre una lista de tamaño N, es decir, necesita asignar 3 punteros para recorrer una lista de 3 elementos, 10 punteros para una lista de 10 elementos, 1000 punteros para una lista de 1000 elementos y así sucesivamente, entonces se considera que el algoritmo tiene una complejidad espacial de O(N). Esto es true incluso cuando ‘N’ es muy pequeño, por ejemplo, N=1.
Para resumir los dos ejemplos anteriores, O(1) denota un uso constante del espacio: el algoritmo asigna el mismo número de punteros independientemente del tamaño de la lista. Por el contrario, O(N) denota un uso del espacio lineal: el uso del espacio del algoritmo crece con respecto al tamaño de entrada.
Si para ti ha resultado de provecho este post, sería de mucha ayuda si lo compartes con más seniors de este modo nos ayudas a dar difusión a nuestra información.