c++ - std::sort() 和 std::sort_heap() 的内存复杂度是多少？

Question

如标题 - std::sort() 和 std::sort_heap() 的内存复杂度是多少？ (后者需要 std::make_heap() 所以我也想知道它的内存复杂度。)

我尝试在这些网站上搜索:http://www.cplusplus.com/reference/ http://en.cppreference.com/w/但要么我错过了，要么他们只提到了时间复杂度。上述函数的内存复杂性是否在任何地方指定(在 C++ 标准或其他文档中)？或者这可能取决于实现？

Answer 1

对于 std::sort() 我在 Cboard 上找到了一个答案，它几乎是这样说的:

Quality of implementation issue. Different implementations use memory more effectively than other implementations. Beyond that, the standard allows specializations for std::sort for different iterators categories allowing the implementation to choose between a few different options so long as the complexity (time) matches the requirements. The complexity given is not even time, but numbers of comparisons. The implementation could perform N³ swap operations.

std::sort 的大多数实现的内存开销与递归的深度和每个递归级别存储在堆栈上的局部变量的数量有关。 std::sort 的 HP/Microsoft STL 实现使用 Quicksort 直到/除非它检测到递归级别变得太深，在这种情况下它会切换到堆排序。如果尺寸较小，例如 32 或更小，则使用 Insertionsort。

您可以在维基百科中看到算法的比较 page并估计内存复杂度。

同样，我怀疑其他两种算法属于同一种情况。