根據inplace_merge的C++文檔,如果使用內部緩衝區,則算法的複雜度爲「線性比較(N-1)」,否則爲NlogN(其中N是範圍[first,last)中的數字元素))「。內部緩衝區是什麼意思以及導致O(N-1)與O(NlogN)的複雜性的原因是什麼?inplace_merge:是什麼導致N * log(N)與N-1的複雜性?
回答
內部緩衝區只是一個由足夠大小的庫分配的緩衝區,用於在合併發生時保留合併的輸出(在合併完成後將其複製回原始範圍)。如果使用這個額外的空間,合併可以在線性時間完成。如果它不能或不使用一個單獨的緩衝區來存儲輸出,那麼該操作會降級到運行時的通用排序O(n log n)
。
爲了擴展對方的回答(或多個):
至少在的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
,如果你看重你的堆。
- 1. 爲什麼pop_heap的複雜性是O(2 * log(N))?
- 2. 與log(n)相比,log(n^2)的大O是什麼?
- 3. 算法複雜度,log^k n vs n log n
- 4. 是什麼小於n是log n?
- 5. 爲什麼C++ STL映射容器O(log(n))的複雜性?
- 6. (log n)/(log(log n))的順序是什麼?
- 7. O(n * log n)工作,然後O(n^2)工作的代碼的複雜性是什麼?
- 8. 線性或者(N log n)的時間複雜度
- 9. 是log(n!)= O((log(n))^ 2)?
- 10. 時間複雜度O(N日誌(log n)的)+ N O(L)
- 11. 證明log(n!)是Ω(n log(n))
- 12. f(n)= n^log(n)複雜多項式或指數
- 13. 時間複雜度 - O(n^2)到O(n log n)搜索
- 14. 複雜度O(log(n))是否等於O(sqrt(n))?
- 15. log(n!)=Ω(n * log(n))?
- 16. 爲什麼代碼O(log n)的時間複雜度?
- 17. 爲什麼此循環返回值爲O(n log log n)而不是O(n log n)?
- 18. 複製關係:T(n/16)+ n log n
- 19. 復發T(n)= T(n - log(n))+ 1
- 20. 復發:T(n)= T(n/2)+ log N
- 21. log *(log n)是什麼意思,它代表什麼
- 22. 與複雜性爲O更好(n)的
- 23. 顯示n^2不是O(n * log(n))?
- 24. N皇后難題的最佳複雜性是什麼?
- 25. Ruby中Array.new(n,x)的複雜性是什麼?
- 26. N元樹插入和搜索的複雜性是什麼?
- 27. 爲什麼不是karatsuba O(n^2)的複雜性?
- 28. 是否有可能創建具有log(n)複雜性的ArrayList屬性的Map?
- 29. 這個算法的空間複雜度是多少(n或log(n))?
- 30. 算法與O(N /日誌(n))的複雜性
看這個答案http://stackoverflow.com/a/4375732/819272 – TemplateRex 2012-07-06 18:40:17
我看了答案,並閱讀了評論,但我覺得我的問題仍然可以更清楚地回答。 – rolloff 2012-07-11 17:07:52