computer science - science - ¿Qué significa esto: O(n) pasos y O(1) espacio?

computer science salary

Question

¿Qué significa O (1) espacio? Entiendo que los pasos O (n) son como el orden de magnitud de los cálculos que realiza un algoritmo / programa, pero no sé qué es el espacio O (n).

Answer 1

El espacio O (1) 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.

Edición : Añadiendo dos ejemplos:

• Bubblesort requiere O (1) espacio.
• Mergesort requiere O (n) espacio.

Answer 2

Esencialmente, "O (n) pasos y O (1) espacio" significaría que el número de pasos que realiza el algoritmo realiza una escala lineal (O (n)) con el número de elementos, pero la cantidad de memoria que toma es constante.