Ποια είναι η ασυμπτωτική πολυπλοκότητα των λειτουργιών με την κλάση std::vector σε C++;

Ανάλυση της ασυμπτωτικής πολυπλοκότητας για τις βασικές λειτουργίες με std::vector:

Λειτουργία	Μέσος χρόνος	Χρόνος χειρότερης περίπτωσης
Πρόσβαση σε στοιχείο ([], at)	O(1)	O(1)
Εισαγωγή/διαγραφή στο τέλος	O(1)	O(N)
Εισαγωγή/διαγραφή στην αρχή/μέσο	O(N)	O(N)
Απόκτηση μεγέθους (size)	O(1)	O(1)
Αλλαγή μεγέθους (resize)	O(N)	O(N)

Επεξηγήσεις:

• O(1) (σταθερός χρόνος): Η λειτουργία εκτελείται σε σταθερό αριθμό βημάτων, ανεξάρτητα από το μέγεθος του διανύσματος.
• O(N) (γραμμικός χρόνος): Ο χρόνος εκτέλεσης της λειτουργίας είναι άμεσα ανάλογος με τον αριθμό των στοιχείων στο διάνυσμα (N).

Επιπλέον:

• Η εισαγωγή/διαγραφή στο τέλος μπορεί να απαιτήσει O(N) στη χειρότερη περίπτωση λόγω επαναπρογραμματισμού μνήμης (realloc), όταν η τρέχουσα χωρητικότητα δεν επαρκεί. Κατά την επαναπρογραμματισμό, δημιουργείται ένας νέος μεγαλύτερος buffer και αντιγράφονται όλα τα υπάρχοντα στοιχεία σε αυτόν. Χάρη στη στρατηγική κατανομής μνήμης (συνήθως διπλασιασμός της χωρητικότητας), ο μέσος χρόνος εισαγωγής/διαγραφής στο τέλος είναι O(1).
• Η εισαγωγή/διαγραφή στη μέση απαιτεί μετατόπιση όλων των επόμενων στοιχείων, που διαρκεί O(N) χρόνο.

Παράδειγμα επαναπρογραμματισμού κατά το push_back:

// Υποθέτουμε ότι το διάνυσμα έχει χωρητικότητα 4 και είναι γεμάτο
std::vector<int> vec = {1, 2, 3, 4}; // Χωρητικότητα = 4, Μέγεθος = 4

// Η προσθήκη ενός νέου στοιχείου απαιτεί επαναπρογραμματισμό
vec.push_back(5); // Πιθανώς η χωρητικότητα να γίνει 8 και όλα τα στοιχεία να αντιγραφούν

// Η λειτουργία push_back σε αυτή την περίπτωση πήρε O(N) χρόνο,
// όπου N είναι ο αριθμός των στοιχείων πριν από τον επαναπρογραμματισμό.