運行時插入多組

什麼是插入一個多集的整體運行的，可以說，我要超過十億元素和插入多集，它保持了排序順序。什麼是我最糟糕的運行時間？運行時插入多組

來源

2014-01-26 AyBayBay

你的意思是複雜性？你的意思是STL multisets？請更具體一點。單線問題通常很糟糕。 –

http://en.cppreference.com/w/cpp/container/multiset/insert#Complexity – Paranaix

如果您在幾秒鐘內平均實際運行時間，那麼這取決於一件事上需要多長時間來複制/移動該對象類型這個問題不能真正回答。運行它並看看。如果你的意思是複雜性，那麼「十億」這個數字是完全不相關的（儘管它確實例如排除了在32位機器上這樣做）。 –

根據http://www.sgi.com/tech/stl/MultipleAssociativeContainer.html插入件的複雜度爲O（log n）的用於插入的單個元件;爲了插入一個長度爲N的序列，它是O（N log n）。

如果你真的想要的時間，而不是漸進的複雜性，你可以在時間它爲不同的價值觀 - 1000，10,000 - 再說了，然後從那裏計算比例的常數。實際的公式將是T = A N日誌N + C.

但是，當然，接下來您在不同的硬件上運行時間A和C的值會發生變化。

來源

2014-01-26 02:53:29 DRVic

的'+ C'部分應該是negliable（讓我們假裝是物理學家：d） – Paranaix

「實際的方程將是'T = A N日誌N + C'」 - 不一定。例如它可以是'A n log n + B n + C'，並且仍然是'O（n log n）'。一個與'n'成比例的詞是相當可能的，我猜想，因爲'n'是在multiset中創建的元素的數量，並且創建該元素（忽略找到放置位置的部分）可能會大致不變成本。正如Paranaix所說，「C」可能很小：將零元素插入多重集合所需的時間爲:-) –

N的高值限制變得可以忽略不計。但爲了計算A的值，你可以使用更小的N值，如果你不忽略C，那麼擬合會更好。 – DRVic

運行時插入多組

回答

相關問題