“就地”和“空间复杂度 O(1)”之间有区别还是它们的意思相同？

Question

就地复杂度和空间复杂度 O(1) 意味着不同的事情吗？如果是，有人可以解释其中的区别吗？

Answer 1

O(1) 的空间复杂度是比就地完成更严格的要求，因为 O(1) 意味着更改是就地完成的，而不是相反。

您可以创建空间复杂度高于 O(1) 的就地算法。例如，Heapsort的递归重新堆化算法是就地的，但其没有尾部调用优化的递归实现具有 O(log N) 的空间复杂度。