Что означает O (1) пространство? Я понимаю, что шаги O (n) похожи на порядок вычислений, создаваемых алгоритмом/программой, но не знают, что такое O (n) пространство.
Что это означает: O (n) шагов и O (1) пространство?
Ответ 1
O (1) означает, что память, требуемая алгоритмом, является постоянной, то есть не зависит от размера ввода.
O (n) означает, что память, требуемая алгоритмом, имеет (в худшем случае) тот же порядок величины, что и размер ввода.
Edit: Добавление двух примеров:
- Bubblesort требует O (1) пространства.
- Для Mergesort требуется O (n) пространство.
Ответ 2
По существу "шаги O (n) и O (1) пространство" означают, что количество шагов, выполняемых алгоритмом, выполняется линейно (O (n)) с количеством элементов, но объем памяти, который он принимает, постоянный.