Οι δυναμικές συστοιχίες είναι δομές δεδομένων που αλλάζουν αυτόματα το μέγεθος όταν φτάνουν σε χωρητικότητα.

Τι Είναι το Αποσβεσμένο Κόστος;

Το αποσβεσμένο κόστος είναι το μέσο κόστος ανά λειτουργία σε μια σειρά πράξεων.

Δυναμικές λειτουργίες διάταξης

Οι κοινές λειτουργίες σε δυναμικές συστοιχίες περιλαμβάνουν την εισαγωγή, διαγραφή και αλλαγή μεγέθους. Η εισαγωγή στο τέλος είναι συνήθως η πιο συχνή λειτουργία, η οποία μπορεί να προκαλέσει αλλαγή μεγέθους όταν η χωρητικότητα υπερβαίνεται.

Υπολογισμός του Αποσβεσμένου Κόστους

Όταν εισάγεται στοιχεία, η σειρά διπλασιάζεται σε μέγεθος όταν είναι πλήρης. Το κόστος της αλλαγής μεγέθους περιλαμβάνει την αντιγραφή όλων των υπαρχόντων στοιχείων στη νέα σειρά. Αν και η αλλαγή μεγέθους είναι δαπανηρή, συμβαίνει σπάνια.

Για παράδειγμα, αν μια σειρά ξεκινά με χωρητικότητα 1, η ακολουθία του κόστους αλλαγής μεγέθους σε πολλαπλές εισαγωγικές μπορεί να συνοψιστεί ως:

  • Εισαγωγή 1 στοιχείο: κόστος 1
  • Εισαγωγή 2ου στοιχείου: αλλαγή μεγέθους (κόστος 1), συνολικό κόστος 2
  • Εισαγωγή 3ου στοιχείου: αλλαγή μεγέθους (κόστος 2), συνολικό κόστος 3
  • Εισαγωγή 4ου στοιχείου: αλλαγή μεγέθους (κόστος 4), συνολικό κόστος 4

Το συνολικό κόστος για τις εισαγωγές n είναι ανάλογο με το 2n, καθιστώντας το αποσβεσμένο κόστος ανά εισαγωγή περίπου O(1).