我一直认为空间复杂度是 O(1) 但我在网上看它在不同阶段使用不同的排序算法这让我很困惑，std::sort 的空间复杂度到底是什么，它们什么时候不同？
最佳答案
std::sort的“空间复杂度”没有定义。但是，不允许动态分配内存(因为不允许抛出 std::bad_alloc 除非您的类型在复制/移动时这样做)。所以它唯一可以占用的空间是堆栈空间。并且它允许占用任何实现的愿望。sort倾向于作为快速排序的某种变体来实现，因此倾向于递归实现，因此它可能平均使用 O(log(n)) 调用。
关于c++ - C++ 标准模板库中 std::sort 的空间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68146330/