¿Qué significa O (1) space? Entiendo que O (n) pasos es como el orden de magnitud de los cálculos que realiza un algoritmo/programa, pero no sé cuál es el espacio de O (n).¿Qué significa esto: O (n) pasos y O (1) espacio?
O (1) espacio significa que la memoria requerida por el algoritmo es constante, es decir, no depende del tamaño de la entrada.
O (n) espacio significa que la memoria requerida por el algoritmo tiene (en el peor de los casos) el mismo orden de magnitud que el tamaño de la entrada.
Editar: Adición de dos ejemplos:
Esencialmente "O (n) pasos y O (1) espacio" significa que el número de pasos que realiza el algoritmo escala linealmente (O (n)) con el número de elementos, pero la cantidad de memoria toma es constante.
entonces, básicamente, una llamada recursiva normalmente sería el espacio O (n) y un proceso iterativo sería O (1) ya que no está esperando que finalice una llamada recursiva (s)? – Devoted
Se agregaron dos ejemplos comunes. Bueno, en realidad no se pueden encontrar reglas generales sobre complejidades de algoritmos recursivos vs iterativos (pero probablemente sea difícil, si no imposible, que un algoritmo recursivo tenga O (1) complejidad de espacio). – 3lectrologos
si su llamada recursiva usó nuevas variables cada vez que se llamó, entonces sí sería O (n) espacio. Si su proceso iterativo instanciara nuevas variables en un bucle sin soltarlas, también lo haría O (n). Todo depende de cómo diseñe y codifique el algoritmo. – Nikhil