Τι είναι η αποσβεσμένη ανάλυση, χρησιμοποιώντας ως παράδειγμα την αλλαγή μεγέθους δυναμικού πίνακα;

Question

Accepted Answer

**Αποσβεσμένη ανάλυση** μετρά το **μέσο κόστος ανά λειτουργία σε μια ακολουθία**, ακόμη και όταν οι επιμέρους λειτουργίες περιστασιακά κοστίζουν πολύ περισσότερο. Εξηγεί γιατί το `append` ενός δυναμικού πίνακα είναι "**O(1) amortized**" παρά τις περιστασιακές αλλαγές μεγέθους O(n).

## Το παράδειγμα του δυναμικού πίνακα

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

```text
Appending into a doubling array (cap shown):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- copies at 1,2,4,8,16...
```

## Τα μαθηματικά

```text
To insert n elements, total copy work =
  1 + 2 + 4 + ... + n  ≈  2n   (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # almost always O(1); rarely O(n) during a resize
```

| Λειτουργία | Χειρότερη περίπτωση | Αποσβεσμένη |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## Γιατί διπλασιασμός (όχι +1)

Το μεγάλωμα κατά ένα **σταθερό ποσό** θα ενεργοποιούσε μια αντιγραφή σε κάθε εισαγωγή, δίνοντας O(n) αποσβεσμένη. Η πολλαπλασιαστική αύξηση είναι αυτή που διαδίδει το κόστος.

## Γιατί είναι σημαντικό

Η αποσβεσμένη ανάλυση δίνει μια ίσια και ρεαλιστική εικόνα της απόδοσης — χωρίς αυτήν, θα φοβόσασταν λανθασμένα ότι κάθε `append` ή εισαγωγή hash-table είναι O(n).

Επίσης, δικαιολογεί έναν βασικό κανόνα σχεδίασης: **μεγάλωμα της χωρητικότητας πολλαπλασιαστικά**, το οποίο είναι η βάση των δυναμικών πινάκων, πινάκων hash και string builders παντού.