C++ 标准模板库中 std::sort 的空间复杂度是多少？

Question

我一直以为它的空间复杂度是O(1)，但是我在网上查了一下，它在不同阶段使用了不同的排序算法，这让我很困惑，std::sort 的空间复杂度到底是多少，它们什么时候不同？

Answer 1

std::sort

的“空间复杂度”没有定义。但是，不允许动态分配内存（仅允许

ExecutionPolicy

重载抛出

std::bad_alloc

）。所以它唯一占用的空间是堆栈空间。无论实现需要多少，它都可以被允许。

sort

倾向于作为快速排序的某种变体来实现，因此倾向于递归地实现，因此平均可能会使用 O(log(n)) 次调用。