inplace_merge：是什麼導致N * log（N）與N-1的複雜性？

Question

根據inplace_merge的C++文檔，如果使用內部緩衝區，則算法的複雜度爲「線性比較（N-1）」，否則爲NlogN（其中N是範圍[first，last）中的數字元素））「。內部緩衝區是什麼意思以及導致O（N-1）與O（NlogN）的複雜性的原因是什麼？

Answer 1

內部緩衝區只是一個由足夠大小的庫分配的緩衝區，用於在合併發生時保留合併的輸出（在合併完成後將其複製回原始範圍）。如果使用這個額外的空間，合併可以在線性時間完成。如果它不能或不使用一個單獨的緩衝區來存儲輸出，那麼該操作會降級到運行時的通用排序O(n log n)。

Answer 2

爲了擴展對方的回答（或多個）：

• 至少在的libstdC++和的libC++，「內部緩衝液」是通過調用std::get_temporary_buffer，在STL晦澀但標準程序提供。這個例程已經在C++ 17中被棄用了，基本上是因爲它很混亂和笨。有關詳細信息，請參見this question，或者閱讀Stephan T. Lavavej's original deprecation proposal。

• 在libstdC++中，get_temporary_buffer是作爲對operator new的調用而實現的。 (Source)

• 在libC++中，get_temporary_buffer被實現爲對operator new的調用。 (Source)

• 我不知道inplace_merge在MSVC的標準庫中是否使用get_temporary_buffer，但我敢打賭，它確實有錢。

• 在MSVC中，it has been reported表示get_temporary_buffer實現爲調用operator new。

您可以通過在全局命名空間覆蓋operator new編寫一個程序來observe this call to operator new firsthand：

#include <algorithm> 
#include <cstdio> 
#include <cstdlib> 

void *operator new(size_t nbytes, const std::nothrow_t&) noexcept 
{ 
    puts("hello from operator new!"); 
    return malloc(nbytes); 
} 

int main() 
{ 
    int a[32] = { 
     1,1,1,2,3,4,4,5,5,5,5,6,6,8,9,9, 
     1,1,2,3,3,3,4,4,5,5,7,8,9,9,9,9, 
    }; 
    std::inplace_merge(&a[0], &a[16], &a[32]); // "hello from operator new!" 
    (void)a; 
} 

TL; DR： 「內部緩衝區」 是通過調用operator new在堆上分配。實施不是需要撥打operator new，但實際上他們都這樣做。遠離inplace_merge，如果你看重你的堆。