Πολυπλοκότητα αλγορίθμων
Πόσο μεγαλώνει ο χρόνος όταν μεγαλώνουν τα δεδομένα: log n, n, n².
45 λεπτά
Στο σχολικό βιβλίο: Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ Β΄ Λυκείου, §2.2
Θα μάθεις να
- Να μετράς τα βασικά βήματα ενός αλγορίθμου ως συνάρτηση του μεγέθους της εισόδου.
- Να απλοποιείς ένα πλήθος βημάτων στον συμβολισμό O, κρατώντας τον κυρίαρχο όρο.
- Να συγκρίνεις τις τάξεις O(1), O(log n), O(n) και O(n²) για μεγάλα n.
- Να προβλέπεις πώς αλλάζει ο χρόνος εκτέλεσης όταν πολλαπλασιάζεται το μέγεθος της εισόδου.
Γιατί δεν μετράμε δευτερόλεπτα
Ένα πρόβλημα μπορεί να είναι επιλύσιμο και να είναι πρακτικά άχρηστο: αν η λύση του χρειάζεται περισσότερο χρόνο από την ηλικία του σύμπαντος, η ύπαρξή της δεν βοηθά κανέναν. Η πολυπλοκότητα (complexity) μετρά πόσους πόρους χρειάζεται ένας αλγόριθμος, κυρίως χρόνο και μνήμη.
Τα δευτερόλεπτα δεν είναι καλή μονάδα. Το ίδιο πρόγραμμα τρέχει σε ένα παλιό λάπτοπ δέκα φορές πιο αργά απ' ό,τι σε έναν καινούργιο εξυπηρετητή, και ο αλγόριθμος δεν άλλαξε. Γι' αυτό μετράμε βασικά βήματα (συγκρίσεις, προσθέσεις, αναθέσεις) ως συνάρτηση του μεγέθους της εισόδου, που το συμβολίζουμε .
Μέτρηση βημάτων
Τρεις αλγόριθμοι πάνω σε μια λίστα στοιχείων:
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. Ο αριθμός των ζευγών είναι ακριβώς : για δέκα φορές περισσότερα στοιχεία, περίπου εκατό φορές περισσότερα βήματα.
Ο συμβολισμός O
Δεν μας ενδιαφέρει ο ακριβής αριθμός βημάτων, αλλά πώς μεγαλώνει όταν μεγαλώνει το . Ο συμβολισμός («κεφαλαίο όμικρον», big-O) κρατά μόνο αυτό, με δύο κανόνες:
- Κρατάμε τον όρο που μεγαλώνει γρηγορότερα και πετάμε τους υπόλοιπους.
- Πετάμε τους σταθερούς συντελεστές.
Για , ο όρος είναι και ο μόλις . Ο δεύτερος δεν αλλάζει την εικόνα, γι' αυτό τον πετάμε. Ο συντελεστής εξαρτάται από τις λεπτομέρειες υλοποίησης και τη μηχανή, γι' αυτό τον πετάμε κι εκείνον.
Οι βασικές τάξεις
| Τάξη | Όνομα | Τυπικό παράδειγμα | |||
|---|---|---|---|---|---|
| σταθερή | πρόσβαση σε στοιχείο πίνακα με τη θέση του | ||||
| λογαριθμική | δυαδική αναζήτηση σε ταξινομημένο πίνακα | ||||
| γραμμική | σειριακή αναζήτηση, άθροισμα στοιχείων | ||||
| — | γρήγορες ταξινομήσεις, π.χ. με συγχώνευση | ||||
| τετραγωνική | ταξινόμηση φυσαλίδας, σύγκριση όλων των ζευγών | ||||
| εκθετική | δοκιμή όλων των υποσυνόλων | αριθμός με ψηφία |
Ο λογάριθμος εδώ είναι με βάση : είναι το πόσες φορές μπορείς να κόψεις το στη μέση μέχρι να μείνει . Αφού , είναι , και αφού , είναι .
Σε έναν υπολογιστή που κάνει βήματα το δευτερόλεπτο, για : ο γραμμικός αλγόριθμος τελειώνει σε ένα χιλιοστό του δευτερολέπτου, ο τετραγωνικός σε δευτερόλεπτα, δηλαδή περίπου λεπτά. Ο εκθετικός δεν τελειώνει ποτέ με οποιαδήποτε πρακτική έννοια.
Και η μνήμη
Με τον ίδιο συμβολισμό μετράμε και τη χωρική πολυπλοκότητα, δηλαδή πόση επιπλέον μνήμη χρειάζεται ένας αλγόριθμος. Η συνάρτηση total χρησιμοποιεί μία μεταβλητή όσο μεγάλη κι αν είναι η λίστα, άρα χώρο. Ένας αλγόριθμος που φτιάχνει αντίγραφο της λίστας χρειάζεται χώρο. Συχνά κερδίζεις χρόνο ξοδεύοντας μνήμη, και το ανάποδο.
Παραδείγματα
Παράδειγμα 1
Ένας αλγόριθμος κάνει βήματα. Ποια είναι η τάξη του;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Ο κυρίαρχος όρος είναι ο : για δίνει , ενώ ο δίνει και ο μένει .
Πετάμε τους μικρότερους όρους: μένει .
Πετάμε τη σταθερά : η τάξη είναι .
Παράδειγμα 2
Ένα πρόγραμμα χρειάζεται δευτερόλεπτα για . Πόσο χρειάζεται για ; Πόσο θα χρειαζόταν αν ήταν ;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Το τετραπλασιάζεται.
Για ο χρόνος πολλαπλασιάζεται επί : δευτερόλεπτα.
Για ο χρόνος πολλαπλασιάζεται επί : δευτερόλεπτα.
Η διαφορά μεγαλώνει με το . Για , δηλαδή χίλιες φορές το αρχικό, ο γραμμικός θα χρειαζόταν δευτερόλεπτα και ο τετραγωνικός , πάνω από τρεις εβδομάδες.
Παράδειγμα 3
Πόσες συγκρίσεις χρειάζεται στη χειρότερη περίπτωση η δυαδική αναζήτηση σε ταξινομημένο πίνακα ενός εκατομμυρίου στοιχείων;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Κάθε σύγκριση κόβει το διάστημα στη μέση. Μετά από συγκρίσεις απομένουν περίπου στοιχεία.
Ψάχνουμε το μικρότερο ώστε να ξεπερνά το . Είναι και .
Χρειάζονται συγκρίσεις. Η σειριακή αναζήτηση θα χρειαζόταν στη χειρότερη περίπτωση , πενήντα χιλιάδες φορές περισσότερες.
Παράδειγμα 4
Ποια είναι η τάξη του βρόχου: «όσο το n είναι μεγαλύτερο του 1, κάνε n = n // 2 και μέτρα ένα βήμα»;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Κάθε επανάληψη κόβει το n στη μέση. Από περνά στο , , …, , .
Για χρειάζονται επαναλήψεις. Για , μία παραπάνω.
Η τάξη είναι . Όποτε ένας βρόχος διαιρεί το μέγεθος του προβλήματος με σταθερό αριθμό σε κάθε γύρο, αντί να το μειώνει κατά σταθερό αριθμό, η τάξη είναι λογαριθμική.
Πολλαπλή επιλογή
Ασκήσεις
Γράψε την τάξη πολυπλοκότητας για βήματα.
Τα κατάφερες;
- Να μετράς τα βασικά βήματα ενός αλγορίθμου ως συνάρτηση του μεγέθους της εισόδου.
- Να απλοποιείς ένα πλήθος βημάτων στον συμβολισμό O, κρατώντας τον κυρίαρχο όρο.
- Να συγκρίνεις τις τάξεις O(1), O(log n), O(n) και O(n²) για μεγάλα n.
- Να προβλέπεις πώς αλλάζει ο χρόνος εκτέλεσης όταν πολλαπλασιάζεται το μέγεθος της εισόδου.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.