Ποια είναι η χρονική πολυπλοκότητα της διαγραφής στοιχείων από ένα διάνυσμα στην χειρότερη περίπτωση;

Στην χειρότερη περίπτωση, η διαγραφή στοιχείων από ένα vector (std::vector στην C++) έχει χρονική πολυπλοκότητα O(n), όπου n είναι ο αριθμός των στοιχείων στο vector μετά τη θέση διαγραφής. Αυτό οφείλεται στο γεγονός ότι, μετά τη διαγραφή των στοιχείων, όλα τα επόμενα στοιχεία πρέπει να μετακινηθούν προς τα αριστερά για να γεμίσουν το κενό.

Για παράδειγμα, αν διαγράψουμε ένα στοιχείο στην αρχή του vector, όλα τα άλλα στοιχεία πρέπει να μετακινηθούν μία θέση μπροστά, που απαιτεί O(n) λειτουργίες.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // διαγραφή του πρώτου στοιχείου
// όλα τα στοιχεία μετακινούνται μία θέση προς τα αριστερά

Αν διαγραφεί ένα στοιχείο στο τέλος, δεν απαιτείται μετακίνηση, και η λειτουργία θα είναι πιο κοντά σε O(1). Αλλά στη χειρότερη περίπτωση — O(n).