c++ - 内存使用对算法复杂性的影响

Question

我正在阅读 Nicolai Josuttis 关于 C++STL 算法的书。对于stable_sort()等很多算法，他提到如果有足够的内存可用，算法的复杂度为n * log(n)，否则为n * log(n) * log(n)。我的问题是内存使用如何影响复杂性？STL 如何检测到这种情况？

Answer 1

查看 gcc 的 STL，您会inplace_merge在stl_algo.h. 这是合并排序的传统合并实现，O(N)，使用与输入大小相同的缓冲区。这个缓冲区是通过_Temporary_buffer, from分配的stl_tempbuf.h。这会调用get_temporary_buffer，最终会调用 new。如果抛出异常，异常会被捕获，并且缓冲区为 NULL - 这是“内存不足”的情况。在这种情况下，合并与 一起工作__merge_without_buffer，即 O(N lg N)。由于归并排序的递归深度是 O(lg N)，所以在“传统”归并排序（有缓冲区）的情况下，你得到 O(N lg N)，在没有缓冲区的版本中得到 O(N lg N lg N) .