插入的複雜性

Question

我有一個排序的向量， 什麼是更好的： 使用lower_bound並插入元素在它的位置在向量中。 或只需將元素push_back到vector中，並在sort（）需要時對其進行排序？

Answer 1

對於一次執行的單個操作，使用lower_bound和insert更便宜。 lower_bound是O(log(n))和insert將是（最差和平均情況）O(n)，給出最終複雜度O(n)。

如果您不需要進行排序，直到你完成插入之後的載體，它會便宜很多，只進行排序，因爲所有的push_back旨意是O(1)*O(n) = O(n)和最終排序將是O(n*log(n))，給你最終的複雜性爲O(n*log(n))，而多重lower_bound + insert會給你一個複雜的O(n)*O(n) = O(n**2)。

如果您需要在整個插入過程中排序的元素，哪一個更便宜，這將非常依賴於您的使用模式（您需要多久分配一次元素）。通常情況下，您只需要在施工過程結束時進行排序的元素，這就是爲什麼最終排序可能是工具帶中非常強大的工具。如果這不是您的使用模式，您可能希望至少考慮使用關聯容器，如multi_set或multi_map。