Verbesserung der Laufzeit Komplexität der Einfügesortierung?

Question

Ich habe den folgenden Code geschrieben, um zu versuchen, einen Einsatz in einem sortierten Vektor in O (log n) Laufzeit auszuführen:

std::vector<int> to_insert_sort {2,3,5,6,1,1,3,2}; 

int to_insert {3}; 

std::sort(to_insert_sort.begin(), to_insert_sort.end()); //O(log n) 

auto pos = std::upper_bound(to_insert_sort.begin(), to_insert_sort.end(), 5); //O(log n) 

to_insert_sort.insert(pos, to_insert); //O(n) 

1) Ich sage, diese Operation O (log stimmt Bin n)

2) Gibt es Möglichkeiten, diesen Vorgang mit erhöhter Laufzeit-Effizienz durchzuführen?

Answer 1

1) Habe ich recht, wenn ich sage, dass diese Operation O ist (log n)?

std::sort O (n * log n)

std::upper_bound O (log n)

std::vector.insert O (n)

2) Gibt es Möglichkeiten der Durchführung dieser Operation mit erhöhter Laufzeit Effizienz?

Ja, Sie können in O (log n) einfügen, aber Sie müssen Ihre Datenstruktur ändern. Beispielsweise können Sie std::multiset<int> statt std::vector<int> verwenden.

std::multiset<int> m; 
//m<={2,3,5,6,1,1,3,2}; //O(n * log n) 
int to_insert {3}; 
m.insert(to_insert); //O(log n)