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

Question

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

Answer 1

看一下gcc的STL，你会在stl_algo.h中找到inplace_merge。这是合并排序的传统合并实现，O(N)，使用与输入相同大小的缓冲区。此缓冲区是从stl_tempbuf.h通过_Temporary_buffer分配的。这会调用get_temporary_buffer，它最终会调用新的。如果抛出异常，异常就会被捕获，缓冲区为空--这就是“内存不足”的情况。在这种情况下，合并适用于__merge_without_buffer，它是O(N lg N)。由于合并排序的递归深度是O(lg N)，因此在“传统”合并排序(有缓冲区)的情况下得到O(N lg N)，在没有缓冲区的版本中得到O(N lg N lg N)。