什么是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 上找到了答案，其中几乎写着：

\n\n

\n

实施质量问题。不同的实现比其他实现更有效地使用内存。除此之外，该标准还允许专业化std::sort不同的迭代器类别进行专门化，允许实现在几个不同的选项之间进行选择，只要复杂性（时间）符合要求即可。给出的复杂性甚至不是时间，而是比较的次数。该实现可以执行 N\xc2\xb3 交换操作。

\n

\n\n

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

\n\n

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

\n\n

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

\n