內存使用對算法複雜性的影響

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） 。