dha*_*ram 5 algorithm performance space-complexity
这让我有些困惑。当约束如下时，解决给定问题的方法应该是什么：
1）不使用多余的空间：例如：如果我想对给定的数组进行排序，则几乎没有办法。冒泡排序，它不断交换（只是循环，没有递归）。我相信这是不使用额外空间的。如果我使用递归对元素进行排序，那会是什么情况。是否与“不使用额外空间”相同，或者所使用的堆栈计入算法的空间复杂度？
2）在O（1）空间中：O（1）空间是什么意思？这是否意味着恒定的空间。现在，如果它是恒定空间，那么请对以下情况进行评论：
a）如果我在第三个变量的帮助下交换冒泡排序。这不是一个额外的空间，并且它不取决于输入的大小，因此它处于恒定的空间。
b）此外，如果我对自然数应用计数排序，而实际上并不需要与总数成比例的空间量，我们是否认为它在常数空间O（1）中。
如果有差异，请说明。谢谢
计算的空间复杂度 [...] 被视为工作磁带上使用的空间量。
排序算法至少都是 O(n) 空间，因为它需要空间来存储所有输入（无论是在内存上还是在磁盘上）。因此，即使是冒泡排序，空间复杂度仍然是 O(n)。
然而，有时，我们对整体空间复杂度不感兴趣（尤其是在上面的例子中），但我们想知道算法使用的额外空间。对于冒泡排序，我们可以说它使用了恒定数量的额外空间。
递归是一种非常特殊的情况，我们必须考虑堆栈。我们在递归时存储状态，我们根据输入多次调用递归函数。由于递归级别的数量取决于输入大小，因此空间复杂度必须考虑堆栈空间使用情况。
我不确定 O(1) 空间算法是否常见，但循环查找算法就是这样的例子之一。该算法本身只使用空间正好 2 个“指针”。要查找其循环的函数使用的额外空间应单独计算。
在计数排序的情况下，空间复杂度取决于输入 n（计数）的大小和最大输入值 k。这两个参数相互独立，因此空间复杂度为 O(n + k)。使用的额外空间可以定义为 O(k)。