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

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，从stl_tempbuf.h分配的。这将调用get_temporary_buffer，最终调用新的。如果抛出一个异常，异常会被捕获，并且缓冲区为NULL - 这是“内存不足”的情况。在这种情况下，合并与__merge_without_buffer一起工作，即O（N lg N）。由于合并排序的递归深度为O（lg N），所以在“传统”mergesort（带缓冲区）的情况下获得O（N lg N），而在没有缓冲区的版本中获得O（N lg N lg N） 。