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

Question

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

Answer 1

的“空间复杂度”std::sort没有定义。但是，不允许动态分配内存（因为不允许抛出异常std::bad_alloc，除非您的类型在复制/移动时抛出异常）。所以它唯一占用的空间是堆栈空间。并且它可以占用实现所需的任何时间。

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