Есть ли разница между «на месте» и «пространственной сложностью O (1)» или они означают одно и то же?

Question

Делать на месте и сложность пространства O (1) означает разные вещи? Если да, может кто-то объяснить разницу?

Answer 1

Пространственная сложность O (1) является более сильным требованием, чем на месте, поскольку O (1) подразумевает, что изменения выполняются на месте, но не наоборот.

Вы можете создать алгоритм на месте, который имеет пространственную сложность выше O (1). Например, рекурсивный алгоритм перехвата Heapsort на месте, но его рекурсивная реализация без оптимизации хвостового вызова имеет сложность пространства O (log N).