# Πολυπλοκότητα αλγορίθμων

> Πόσο μεγαλώνει ο χρόνος όταν μεγαλώνουν τα δεδομένα: log n, n, n².

Πληροφορική, Β΄ Λυκείου. https://www.akademio.gr/el/lyk-b/informatics/algorithm-complexity

## Τι θα μάθεις

- Να μετράς τα βασικά βήματα ενός αλγορίθμου ως συνάρτηση του μεγέθους της εισόδου.
- Να απλοποιείς ένα πλήθος βημάτων στον συμβολισμό O, κρατώντας τον κυρίαρχο όρο.
- Να συγκρίνεις τις τάξεις O(1), O(log n), O(n) και O(n²) για μεγάλα n.
- Να προβλέπεις πώς αλλάζει ο χρόνος εκτέλεσης όταν πολλαπλασιάζεται το μέγεθος της εισόδου.

## Γιατί δεν μετράμε δευτερόλεπτα

Ένα πρόβλημα μπορεί να είναι επιλύσιμο και να είναι **πρακτικά** άχρηστο: αν η λύση του χρειάζεται περισσότερο χρόνο από την ηλικία του σύμπαντος, η ύπαρξή της δεν βοηθά κανέναν. Η **πολυπλοκότητα** (complexity) μετρά πόσους πόρους χρειάζεται ένας αλγόριθμος, κυρίως χρόνο και μνήμη.

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

## Μέτρηση βημάτων

Τρεις αλγόριθμοι πάνω σε μια λίστα $n$ στοιχείων:

```python
def first(items):
    return items[0]  # ένα βήμα, όσο μεγάλη κι αν είναι η λίστα

def total(items):
    s = 0
    for x in items:  # n επαναλήψεις, μία πρόσθεση η καθεμία
        s += x
    return s

def count_pairs(n):
    steps = 0
    for i in range(n):
        for j in range(i + 1, n):  # κάθε ζεύγος συγκρίνεται μία φορά
            steps += 1
    return steps

for n in [10, 100, 1000]:
    print(n, count_pairs(n))
```

Το πρόγραμμα τυπώνει `10 45`, `100 4950` και `1000 499500`. Ο αριθμός των ζευγών είναι ακριβώς $\frac{n(n-1)}{2}$: για δέκα φορές περισσότερα στοιχεία, περίπου **εκατό** φορές περισσότερα βήματα.

## Ο συμβολισμός O

Δεν μας ενδιαφέρει ο ακριβής αριθμός βημάτων, αλλά **πώς μεγαλώνει** όταν μεγαλώνει το $n$. Ο συμβολισμός $O$ («κεφαλαίο όμικρον», big-O) κρατά μόνο αυτό, με δύο κανόνες:

1. **Κρατάμε τον όρο που μεγαλώνει γρηγορότερα** και πετάμε τους υπόλοιπους.
2. **Πετάμε τους σταθερούς συντελεστές.**

$$
\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n \quad \longrightarrow \quad O(n^2)
$$

Για $n = 10^6$, ο όρος $\frac{1}{2}n^2$ είναι $5 \cdot 10^{11}$ και ο $\frac{1}{2}n$ μόλις $5 \cdot 10^5$. Ο δεύτερος δεν αλλάζει την εικόνα, γι' αυτό τον πετάμε. Ο συντελεστής $\frac{1}{2}$ εξαρτάται από τις λεπτομέρειες υλοποίησης και τη μηχανή, γι' αυτό τον πετάμε κι εκείνον.

## Οι βασικές τάξεις

| Τάξη          | Όνομα       | Τυπικό παράδειγμα                              | $n = 10$     | $n = 1000$         | $n = 10^6$                  |
| ------------- | ----------- | ---------------------------------------------- | ------------ | ------------------ | --------------------------- |
| $O(1)$        | σταθερή     | πρόσβαση σε στοιχείο πίνακα με τη θέση του     | $1$          | $1$                | $1$                         |
| $O(\log n)$   | λογαριθμική | δυαδική αναζήτηση σε ταξινομημένο πίνακα       | $\approx 3$  | $\approx 10$       | $\approx 20$                |
| $O(n)$        | γραμμική    | σειριακή αναζήτηση, άθροισμα στοιχείων         | $10$         | $1000$             | $10^6$                      |
| $O(n \log n)$ | —           | γρήγορες ταξινομήσεις, π.χ. με συγχώνευση      | $\approx 33$ | $\approx 10^4$     | $\approx 2 \cdot 10^7$      |
| $O(n^2)$      | τετραγωνική | ταξινόμηση φυσαλίδας, σύγκριση όλων των ζευγών | $100$        | $10^6$             | $10^{12}$                   |
| $O(2^n)$      | εκθετική    | δοκιμή όλων των υποσυνόλων                     | $1024$       | $\approx 10^{301}$ | αριθμός με $301\,030$ ψηφία |

Ο λογάριθμος εδώ είναι με βάση $2$: $\log_2 n$ είναι το πόσες φορές μπορείς να κόψεις το $n$ στη μέση μέχρι να μείνει $1$. Αφού $2^{10} = 1024$, είναι $\log_2 1000 \approx 10$, και αφού $2^{20} \approx 10^6$, είναι $\log_2 10^6 \approx 20$.

Σε έναν υπολογιστή που κάνει $10^9$ βήματα το δευτερόλεπτο, για $n = 10^6$: ο γραμμικός αλγόριθμος τελειώνει σε ένα χιλιοστό του δευτερολέπτου, ο τετραγωνικός σε $1000$ δευτερόλεπτα, δηλαδή περίπου $17$ λεπτά. Ο εκθετικός δεν τελειώνει ποτέ με οποιαδήποτε πρακτική έννοια.

> **Κλειδί**
>
> **Η τάξη λέει τι γίνεται όταν διπλασιάζεται η είσοδος.**
>
> - $O(1)$: ο χρόνος **δεν αλλάζει**.
> - $O(\log n)$: προστίθεται **ένα** βήμα.
> - $O(n)$: ο χρόνος **διπλασιάζεται**.
> - $O(n^2)$: ο χρόνος **τετραπλασιάζεται**.
> - $O(2^n)$: ο χρόνος **υψώνεται στο τετράγωνο**.
>
> Γι' αυτό ένας καλύτερος αλγόριθμος κερδίζει πάντα, για αρκετά μεγάλο $n$, έναν γρηγορότερο υπολογιστή.

*Διαδραστικό στη σελίδα: Γραμμική εναντίον λογαριθμικής*

> **Πρόσεχε**
>
> **Το O μιλά για μεγάλα n και συνήθως για τη χειρότερη περίπτωση.**
>
> Για δέκα στοιχεία, ένας αλγόριθμος $O(n^2)$ με απλά βήματα μπορεί να είναι πιο γρήγορος από έναν $O(n \log n)$ με πολύπλοκα. Και η σειριακή αναζήτηση βρίσκει το ζητούμενο με την πρώτη σύγκριση αν τύχει να είναι πρώτο· η τάξη $O(n)$ αφορά το χειρότερο σενάριο, όταν είναι τελευταίο ή λείπει.

## Και η μνήμη

Με τον ίδιο συμβολισμό μετράμε και τη **χωρική** πολυπλοκότητα, δηλαδή πόση επιπλέον μνήμη χρειάζεται ένας αλγόριθμος. Η συνάρτηση `total` χρησιμοποιεί μία μεταβλητή όσο μεγάλη κι αν είναι η λίστα, άρα $O(1)$ χώρο. Ένας αλγόριθμος που φτιάχνει αντίγραφο της λίστας χρειάζεται $O(n)$ χώρο. Συχνά κερδίζεις χρόνο ξοδεύοντας μνήμη, και το ανάποδο.

> **Θυμήσου**
>
> - Μετράμε **βήματα**, όχι δευτερόλεπτα.
> - Κρατάμε τον **κυρίαρχο όρο**, πετάμε σταθερές.
> - Σειρά από τη γρηγορότερη: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$.
> - Δύο εμφωλευμένες επαναλήψεις πάνω στα ίδια δεδομένα είναι συνήθως $O(n^2)$.

## Παραδείγματα

### Παράδειγμα 1: Ένας αλγόριθμος κάνει \$3n^2 + 50n + 7\$ βήματα. Ποια είναι η τάξη του;

1. **Ο κυρίαρχος όρος** είναι ο $3n^2$: για $n = 1000$ δίνει $3 \cdot 10^6$, ενώ ο $50n$ δίνει $5 \cdot 10^4$ και ο $7$ μένει $7$.
2. **Πετάμε τους μικρότερους όρους:** μένει $3n^2$.
3. **Πετάμε τη σταθερά $3$:** η τάξη είναι $O(n^2)$.

### Παράδειγμα 2: Ένα πρόγραμμα \$O(n^2)\$ χρειάζεται \$2\$ δευτερόλεπτα για \$n = 1000\$. Πόσο χρειάζεται για \$n = 4000\$; Πόσο θα χρειαζόταν αν ήταν \$O(n)\$;

1. **Το $n$ τετραπλασιάζεται.**
2. **Για $O(n^2)$** ο χρόνος πολλαπλασιάζεται επί $4^2 = 16$: $2 \cdot 16 = 32$ δευτερόλεπτα.
3. **Για $O(n)$** ο χρόνος πολλαπλασιάζεται επί $4$: $2 \cdot 4 = 8$ δευτερόλεπτα.
4. **Η διαφορά μεγαλώνει με το $n$.** Για $n = 10^6$, δηλαδή χίλιες φορές το αρχικό, ο γραμμικός θα χρειαζόταν $2000$ δευτερόλεπτα και ο τετραγωνικός $2 \cdot 10^6$, πάνω από τρεις εβδομάδες.

### Παράδειγμα 3: Πόσες συγκρίσεις χρειάζεται στη χειρότερη περίπτωση η δυαδική αναζήτηση σε ταξινομημένο πίνακα ενός εκατομμυρίου στοιχείων;

1. **Κάθε σύγκριση κόβει το διάστημα στη μέση.** Μετά από $k$ συγκρίσεις απομένουν περίπου $\frac{10^6}{2^k}$ στοιχεία.
2. **Ψάχνουμε το μικρότερο $k$ ώστε $2^k$ να ξεπερνά το $10^6$.** Είναι $2^{19} = 524\,288$ και $2^{20} = 1\,048\,576$.
3. **Χρειάζονται $20$ συγκρίσεις.** Η σειριακή αναζήτηση θα χρειαζόταν στη χειρότερη περίπτωση $10^6$, πενήντα χιλιάδες φορές περισσότερες.

### Παράδειγμα 4: Ποια είναι η τάξη του βρόχου: «όσο το n είναι μεγαλύτερο του 1, κάνε n = n // 2 και μέτρα ένα βήμα»;

1. **Κάθε επανάληψη κόβει το n στη μέση.** Από $1024$ περνά στο $512$, $256$, …, $2$, $1$.
2. **Για $n = 1024 = 2^{10}$** χρειάζονται $10$ επαναλήψεις. Για $n = 2048$, μία παραπάνω.
3. **Η τάξη είναι $O(\log n)$.** Όποτε ένας βρόχος διαιρεί το μέγεθος του προβλήματος με σταθερό αριθμό σε κάθε γύρο, αντί να το μειώνει κατά σταθερό αριθμό, η τάξη είναι λογαριθμική.

## Ερωτήσεις

1. Γιατί η πολυπλοκότητα μετριέται σε βήματα και όχι σε δευτερόλεπτα;
   - γιατί τα δευτερόλεπτα εξαρτώνται από τη μηχανή, ενώ τα βήματα μόνο από τον αλγόριθμο και την είσοδο
   - γιατί τα βήματα μετριούνται πιο εύκολα με χρονόμετρο από τα κλάσματα του δευτερολέπτου
   - γιατί όλοι οι υπολογιστές κάνουν ένα βήμα το δευτερόλεπτο, άρα τα δύο μέτρα ταυτίζονται
   - γιατί ο χρόνος εκτέλεσης δεν έχει σημασία στην πράξη, αφού οι υπολογιστές είναι πια γρήγοροι
2. Ποια είναι η τάξη ενός αλγορίθμου που κάνει $5n + 2n^2 + 100$ βήματα;
   - $O(n^2)$
   - $O(n)$
   - $O(2n^2)$
   - $O(100)$
3. Ένας αλγόριθμος $O(n^2)$ τρέχει με διπλάσια είσοδο. Ο χρόνος του γίνεται περίπου:
   - τετραπλάσιος
   - διπλάσιος
   - ίδιος
   - δεκαπλάσιος
4. Αν διπλασιαστεί ο ταξινομημένος πίνακας, οι συγκρίσεις της δυαδικής αναζήτησης στη χειρότερη περίπτωση:
   - αυξάνονται κατά μία
   - διπλασιάζονται
   - μένουν ίδιες
   - τετραπλασιάζονται
5. Δύο εμφωλευμένες επαναλήψεις, καθεμία από $1$ έως $n$, με μία πράξη στο εσωτερικό. Ποια είναι η τάξη;
   - $O(n^2)$
   - $O(2n)$
   - $O(n)$
   - $O(\log n)$
6. Για $n = 10^6$, πόσα βήματα κάνει περίπου ένας αλγόριθμος $O(n^2)$;
   - $10^{12}$
   - $2 \cdot 10^6$
   - $10^8$
   - $20$
7. Ποια σειρά είναι από τη γρηγορότερη προς την πιο αργή τάξη, για μεγάλα $n$;
   - $O(1)$, $O(\log n)$, $O(n)$, $O(n^2)$
   - $O(1)$, $O(n)$, $O(\log n)$, $O(n^2)$
   - $O(\log n)$, $O(1)$, $O(n)$, $O(n^2)$
   - $O(1)$, $O(\log n)$, $O(n^2)$, $O(n)$
8. Για πίνακα $8$ στοιχείων, ένας απλός αλγόριθμος $O(n^2)$ τελείωσε πιο γρήγορα από έναν πολύπλοκο $O(n \log n)$. Τι συμπεραίνουμε;
   - τίποτα γενικό· το O περιγράφει τη συμπεριφορά για μεγάλα $n$
   - ότι ο $O(n^2)$ είναι καλύτερος αλγόριθμος
   - ότι η ανάλυση πολυπλοκότητας είναι λάθος
   - ότι ο υπολογιστής ήταν πολύ γρήγορος για να φανεί η διαφορά
9. Ποια λειτουργία είναι $O(1)$;
   - η ανάγνωση του στοιχείου στη θέση $500$ ενός πίνακα
   - η εύρεση του μεγαλύτερου στοιχείου ενός πίνακα
   - η εκτύπωση όλων των στοιχείων ενός πίνακα
   - η δυαδική αναζήτηση ενός στοιχείου
10. Ένας αλγόριθμος δοκιμάζει όλα τα υποσύνολα ενός συνόλου $n$ στοιχείων. Τι γίνεται αν προστεθεί ένα στοιχείο;
   - ο χρόνος διπλασιάζεται
   - ο χρόνος αυξάνεται κατά ένα βήμα
   - ο χρόνος τετραπλασιάζεται
   - ο χρόνος μένει ίδιος

## Ασκήσεις

1. Γράψε την τάξη πολυπλοκότητας για $4n + 9$ βήματα.
2. Πόσα ζεύγη συγκρίνει η count_pairs για $n = 20$;
3. Ένα πρόγραμμα $O(n^2)$ ταξινομεί $5000$ ονόματα σε $3$ δευτερόλεπτα.
   α) Περίπου πόσο θα χρειαστεί για $15\,000$ ονόματα;
   β) Και αν ήταν $O(n)$;
4. Σε ταξινομημένο πίνακα γίνεται δυαδική αναζήτηση.
   α) Πόσες συγκρίσεις χρειάζονται στη χειρότερη περίπτωση για $1000$ στοιχεία;
   β) Πόσες για $4000$ στοιχεία;
   γ) Ποια είναι η τάξη της;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/lyk-b/informatics/algorithm-complexity
