Что это значит: O (n) шагов и O (1) пробел?

Question

Что означает O (1) пробел? Я понимаю, что O (n) шагов - это порядок вычислений, которые выполняет алгоритм / программа, но я не знаю, что такое пространство O (n).

Answer 1

O (1) пробел означает, что память, требуемая алгоритмом, является постоянной, то есть не зависит от размера ввода.

O (n) пробел означает, что память, требуемая алгоритмом, имеет(в худшем случае) того же порядка, что и размер ввода.

Редактировать : Добавление двух примеров:

• Bubblesort требует O (1) пробел.
• Для слияния требуется O (n) пробел.

Answer 2

По существу, «O (n) шагов и O (1) пробел» будет означать, что количество шагов, которые алгоритм выполняет, масштабируется линейно (O (n)) с количеством элементов, но объем памяти, который он принимает, является постоянным .