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

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

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

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

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

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

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}$ εξαρτάται από τις λεπτομέρειες υλοποίησης και τη μηχανή, γι' αυτό τον πετάμε κι εκείνον.

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

Ο λογάριθμος εδώ είναι με βάση $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$ λεπτά. Ο εκθετικός δεν τελειώνει ποτέ με οποιαδήποτε πρακτική έννοια.

Γραμμική εναντίον λογαριθμικής

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

Μέγεθος πίνακα100

Θέση του ζητούμενου73

Η δυαδική αναζήτηση προϋποθέτει ταξινομημένο πίνακα. Αν πρέπει πρώτα να ταξινομήσεις, πληρώνεις και το κόστος της ταξινόμησης.

Συγκρίσεις για αυτή τη θέση

Σειριακή, O(n)73

χειρότερη περίπτωση: 100

Δυαδική, O(log n)6

χειρότερη περίπτωση: 7

Και η μνήμη

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

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση