Nav*_*een 4 c++ complexity-theory stl
我正在阅读关于C++ STL算法的Nicolai Josuttis一书.对于许多算法,例如stable_sort(),他提到算法的复杂性n*log(n),如果有足够的内存可用,否则它是n*log(n)*log(n).我的问题是内存使用情况如何影响复杂性？STL如何检测这种情况？
Mar*_*wis 12
纵观海湾合作委员会的STL,你会发现inplace_merge在stl_algo.h.这是合并排序的传统合并实现,使用O(N),使用与输入大小相同的缓冲区.这个缓冲区是通过_Temporary_bufferfrom 分配的stl_tempbuf.h.这会调用get_temporary_buffer,最终调用new.如果抛出异常,则会捕获异常,并且缓冲区为NULL - 这是"内存不足"的情况.在这种情况下,合并使用__merge_without_buffer,即O(N lg N).由于合并排序的递归深度为O(lg N),在"传统"mergesort(带缓冲区)的情况下得到O(N lg N),在没有缓冲区的版本中得到O(N lg N lg N) .