performance - 术语 O(1) 空间和不使用额外空间的含义

Question

这让我有点困惑。当约束如下时，我解决给定问题的方法应该是什么:

1) 不使用额外空间: 例如:如果我想对给定的数组进行排序，我几乎没有办法做到这一点。 冒泡排序，不断交换(只是循环，没有递归)。我相信这据说是在不使用额外空间的情况下。如果我使用递归对元素进行排序会怎样。是和“不使用额外空间”一样，还是使用的栈算在算法的空间复杂度中？

2) 在 O(1) 空间中: O(1) 空间是什么意思？它是否意味着恒定的空间。现在，如果它是常量空间，那么请评论以下情况:

a) 如果我在第三个变量的帮助下交换冒泡排序。它不是一个额外的空间吗，它不依赖于输入的大小，所以它在常量空间中。

b) 此外，如果我使用应用于自然数的计数排序，它实际上并不需要与总数成比例的空间量，我们是否认为它在常量空间 O(1) 中。

如有不同，请说明。谢谢

Answer 1

根据 Fortnow & Homer (2003) ,

The space complexity of the computation is [...] taken to be the amount of space used on the work tapes.

排序算法至少都是 O(n) 空间，因为它需要空间来存储所有输入(无论是在内存上还是在磁盘上)。因此，即使是冒泡排序，空间复杂度也是O(n)。

然而，有时候，我们对整体空间复杂度不感兴趣(尤其是在上面的例子中)，而是想知道算法使用的额外空间。对于冒泡排序，我们可以说它使用恒定量的附加空间。

递归是一种非常特殊的情况，我们必须考虑堆栈。我们递归的时候是在存储状态，我们根据输入多次调用递归函数。由于递归层数取决于输入大小，空间复杂度必须考虑堆栈空间的使用。

我不确定 O(1) 空间算法是否常见，但循环查找算法就是这样的例子之一。该算法本身仅将空间用于恰好 2 个“指针”。被查找循环的函数使用的额外空间应单独计算。

在计数排序的情况下，空间复杂度取决于输入 n 的大小(计数)和最大输入值 k。 2个参数相互独立，因此空间复杂度为 O(n + k)。使用的额外空间可以定义为 O(k)。