Εξήγηση της Χρονικής και Χωρικής Πολυπλοκότητας ενός Αλγορίθμου
Φανταστείτε δύο προγράμματα που κάνουν ακριβώς την ίδια δουλειά. Αν τροφοδοτήσετε το καθένα με χίλιες εγγραφές, δεν θα μπορείτε να τις ξεχωρίσετε. Αν τροφοδοτήσετε όμως με ένα δισεκατομμύριο, το ένα θα τελειώσει πριν αφήσετε το πλήκτρο Enter, ενώ το άλλο θα εξακολουθεί να εργάζεται την επόμενη Τρίτη.
Ίδιος φορητός υπολογιστής. Ίδια δεδομένα. Αυτό που τα διαφοροποιεί είναι η χρονική πολυπλοκότητα, η οποία είναι απλώς ένα όνομα για το πόσο γρήγορα αυξάνεται το φόρτο εργασίας ενός αλγορίθμου καθώς του δίνετε περισσότερα δεδομένα.
Θα δούμε τι σημαίνει στην πραγματικότητα ο όρος, πώς τον καταγράφει η σημειογραφία Big O, πώς να τον υπολογίσουμε από ένα πραγματικό κομμάτι κώδικα και πού υπεισέρχεται η πολυπλοκότητα του χώρου. Έπειτα, στο τέλος, ένα σημείο όπου όλα αυτά σταματούν να είναι εργασία για το σπίτι και αρχίζουν να κοστίζουν πραγματικά χρήματα: τα έξυπνα συμβόλαια.
Τι είναι η Χρονική Πολυπλοκότητα ενός Αλγορίθμου;
Ξεχάστε τα δευτερόλεπτα για μια στιγμή. Η χρονική πολυπλοκότητα μετράει τα βήματα. Συγκρίσεις, αναθέσεις, λίγη αριθμητική εδώ κι εκεί, και γράφετε το σύνολο ως συνάρτηση του n, που είναι το μέγεθος εισόδου.
Ιδού η πιο βαρετή λειτουργία που μπορεί κανείς να φανταστεί:
python def print_all(items): για στοιχείο στα στοιχεία: print(item)
Δέκα αντικείμενα; Δέκα ταξίδια στον βρόχο. Δέκα χιλιάδες; Δέκα χιλιάδες ταξίδια.
Το έργο ανεβαίνει σε ευθεία γραμμή δίπλα στην είσοδο, επομένως το ονομάζουμε O(n).
Τώρα, ίσως κάθε ταξίδι κοστίζει πραγματικά τρεις μικρές επεμβάσεις αντί για μία. Εντάξει, αυτό είναι 3 πένες. Κανείς δεν νοιάζεται, ειλικρινά, επειδή ο διπλασιασμός της λίστας διπλασιάζει και την εργασία, και αυτή η καμπύλη ανάπτυξης είναι το κομμάτι που θέλουμε. Ο ακριβής αριθμός παραλείπεται επίτηδες.
Αυτός είναι επίσης ο λόγος για τον οποίο κάθε μάθημα DSA και οι μισές συνεντεύξεις προγραμματισμού που υπάρχουν επικρίνουν την πολυπλοκότητα του χρόνου. Αν μπορείτε να υπολογίσετε την πολυπλοκότητα ενός αλγορίθμου κοιτάζοντάς τον, μπορείτε να μαντέψετε πώς θα συμπεριφερθεί σε δεδομένα εισόδου που δεν έχετε προλάβει ποτέ να δοκιμάσετε. Τα οποία, στην παραγωγή, είναι τα περισσότερα δεδομένα.
Γιατί ο χρόνος εκτέλεσης δεν είναι ένα κακό μέτρο ενός αλγορίθμου
Γιατί λοιπόν να μην το εκτελέσετε απλώς με ένα χρονόμετρο; Πολλοί άνθρωποι το κάνουν, και το καταλαβαίνω. Το πρόβλημα είναι ότι ο χρόνος εκτέλεσης παρασύρει ένα σωρό πράγματα με τα οποία ο αλγόριθμός σας δεν έχει καμία σχέση:
- Υλικό. Ο πεντάχρονος φορητός υπολογιστής μου και ένα ολοκαίνουργιο cloud box θα σας δώσουν εντελώς διαφορετικούς αριθμούς για το ίδιο σενάριο.
- Γλώσσα προγραμματισμού. Γράψτε τον ίδιο βρόχο σε C και σε Python και μπορεί να δείτε ένα κενό 10× ή και περισσότερο.
- Φόρτωση συστήματος. Κάποιο πρόγραμμα ενημέρωσης παρασκηνίου ενεργοποιείται, ο συλλέκτης απορριμμάτων ξυπνάει, η προσωρινή μνήμη είναι κρύα. Το αποτέλεσμά σας μετακινείται.
- Όποια και αν είναι η είσοδος που τυχαίνει να έχετε πιάσει. Μια ταξινόμηση που πετάει σε σχεδόν ταξινομημένα δεδομένα μπορεί να ανιχνεύσει σε ανακατεμένα δεδομένα.
Ένα χρονόμετρο σας δίνει μία διαδρομή σε ένα κουτί με μία μόνο εισαγωγή. Ρωτήστε το για 100 φορές τα δεδομένα και δεν θα πάρει τίποτα.
Ο αριθμός των βημάτων δεν κυμαίνεται. Ίδιος αλγόριθμος, ίδια δεδομένα εισόδου, και έχετε τον ίδιο αριθμό βημάτων, είτε πρόκειται για Rust σε διακομιστή rack είτε για JavaScript στο τηλέφωνο κάποιου. Γι' αυτό η χρονική πολυπλοκότητα είναι μια δίκαιη μάχη μεταξύ δύο λύσεων πριν κάνετε benchmarking για κάτι. Θα έκανα benchmarking και μετά, για ό,τι αξίζει. Είναι απλώς ένα διαφορετικό ερώτημα.
Το Μεγάλο Ο και άλλες ασυμπτωτικές σημειογραφίες εξηγούνται
Τα σχολικά βιβλία το ονομάζουν αυτό ασυμπτωτική σημειογραφία, η οποία ακούγεται χειρότερη από ό,τι είναι. Αφήνετε το n να γίνει τεράστιο και σταματάτε να νοιάζεστε για τα μικρά πράγματα, έτσι οι σταθεροί πολλαπλασιαστές και οι μικροσκοπικές εισροές παραλείπονται και μόνο η καμπύλη ανάπτυξης επιβιώνει. Υπάρχουν τρεις από αυτές που αξίζει να γνωρίζετε:
| Σημειογραφία | Τι περιγράφει | Απλή έννοια | Παράδειγμα |
|---|---|---|---|
| Μεγάλο Ο, Ο(f(n)) | Ανω όριο | Ο αλγόριθμος δεν αναπτύσσεται ταχύτερα από το f(n) | Η γραμμική αναζήτηση είναι O(n) |
| Μεγάλο Ωμέγα, Ω(f(n)) | Κάτω όριο | Ο αλγόριθμος χρειάζεται τουλάχιστον f(n) έργο | Οποιαδήποτε συγκριτική ταξινόμηση είναι Ω(n log n) |
| Μεγάλο Θήτα, Θ(f(n)) | Σφιχτά συνδεδεμένο | Τα άνω και κάτω όρια ταιριάζουν | Η ταξινόμηση συγχώνευσης είναι Θ(n log n) |
Στην πράξη, θα ακούσετε τη σημειογραφία Big O περίπου στο 95% των περιπτώσεων. Ορίζει ένα ανώτερο όριο, που σημαίνει ότι ο χρόνος εκτέλεσης δεν θα αυξηθεί ταχύτερα από τον ρυθμό μέσα στις παρενθέσεις. Στην πρώτη μου αξιολόγηση κώδικα σε μια πραγματική δουλειά, ένας έμπειρος προγραμματιστής έγραψε "O(n²), παρακαλώ διορθώστε" δίπλα σε έναν ένθετο βρόχο, και αυτό που εννοούσε ήταν ότι η χειρότερη δυνατή χρονική πολυπλοκότητα ήταν τετραγωνική και η λίστα επρόκειτο να γίνει πολύ μεγαλύτερη.
Τα Ωμέγα και Θήτα παρακολουθούν κυρίως πανεπιστημιακά μαθήματα ανάλυσης αλγορίθμων και δεν νομίζω ότι έχω πληκτρολογήσει κανένα από τα δύο στη δουλειά εδώ και χρόνια. Το Μεγάλο Ο κερδίζει επειδή απαντά σε αυτό που πραγματικά ρωτούν οι άνθρωποι σε μια συνάντηση, δηλαδή "πόσο χειρότερα γίνονται τα πράγματα αν τριπλασιαστεί η κίνηση;"
Υπάρχει μια τεχνική λεπτομέρεια που με μπέρδεψε για λίγο. Δεδομένου ότι το Μεγάλο Ο είναι μόνο ένα ανώτατο όριο, μια συνάρτηση O(n) είναι επίσης O(n²), αυστηρά μιλώντας, με τον ίδιο τρόπο που ένα άτομο 1,5 μέτρων είναι "κάτω από 7 πόδια". Αληθινό και άχρηστο. Όλοι αναφέρουν το πιο αυστηρό όριο που μπορούν να δικαιολογήσουν και θα κάνω το ίδιο.
Κοινές κλάσεις χρονικής πολυπλοκότητας με παραδείγματα
Δεν υπάρχουν τόσες πολλές κλάσεις που θα δείτε σε πραγματικό κώδικα, ίσως επτά αν υπολογίσετε και τις τρομακτικές. Αυτό είναι περίπου το κόστος της καθεμίας με n = 1.000:
| Τάξη | Ονομα | Τυπικό παράδειγμα | Πράξεις σε n = 1.000 |
|---|---|---|---|
| Ο(1) | Συνεχής | Ευρετήριο πίνακα, αναζήτηση πίνακα κατακερματισμού | 1 |
| O(log n) | Λογαριθμική | Δυαδική αναζήτηση | ~10 |
| Επί) | Γραμμικός | Σάρωση λίστας | 1.000 |
| O(n log n) | Γραμμικός | Συγχώνευση ταξινόμησης, γρήγορη ταξινόμηση (μέσος όρος) | ~10.000 |
| Ο(n²) | Τετραγωνικός | Ένθετοι βρόχοι, ταξινόμηση με φυσαλίδες | 1.000.000 |
| Ο(2ⁿ) | Εκθετικός | Αφελής αναδρομική Fibonacci | Περισσότερο από άτομα στο σύμπαν |
| Επί!) | Παραγοντικό | Περιοδεύων πωλητής ωμής βίας | Ακόμα μεγαλύτερο |
O(1): Σταθερός Χρόνος
Είτε το Python dict σας έχει δέκα κλειδιά είτε δέκα εκατομμύρια, η εξαγωγή ενός με κλειδί κοστίζει περίπου το ίδιο, όπως και η ανάγνωση στοιχείων[5] από μια λίστα. Αυτή η επιπεδότητα είναι όλο το νόημα του σταθερού χρόνου.
O(log n): Λογαριθμικός Χρόνος
Θεωρώ ότι αυτοί είναι οι αλγόριθμοι «μαντέψτε τον αριθμό μεταξύ 1 και 100», όπου κάθε εικασία αποκλείει τα μισά από όσα έχουν απομείνει. Η δυαδική αναζήτηση κάνει ακριβώς αυτό σε μια ταξινομημένη λίστα:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 ενώ lo <= hi: mid = (lo + hi) // 2 αν arr[mid] == target: επιστρέφει mid αν arr[mid] < target: lo = mid + 1 αλλιώς: hi = mid - 1 επιστρέφει -1
Με ένα δισεκατομμύριο ταξινομημένα αντικείμενα χρειάζονται περίπου 30 συγκρίσεις, ενώ αν τα ψάξεις ένα προς ένα θα μπορούσες να πάρεις ολόκληρο το δισεκατομμύριο, και ποτέ δεν σταμάτησα να το βρίσκω αστείο.
O(n) και O(n log n)
Ένας γραμμικός αλγόριθμος επισκέπτεται κάθε στοιχείο έναν καθορισμένο αριθμό φορών, όπως θα κάνατε αν ψάχνατε για τον μεγαλύτερο αριθμό σε μια στήλη υπολογιστικού φύλλου με το μάτι. Το O(n log n) είναι το σπίτι της αξιοπρεπούς ταξινόμησης. Η ταξινόμηση με συγχώνευση διαιρεί τη λίστα σε μεμονωμένα στοιχεία (log n επίπεδα διαίρεσης) και στη συνέχεια κάνει ένα γραμμικό πέρασμα ανά επίπεδο κατά τη συγχώνευση, έτσι ώστε ο χρόνος εκτέλεσης να παραμένει σταθερός ανεξάρτητα από το αν τα δεδομένα φτάσουν ταξινομημένα ή κωδικοποιημένα.
O(n²) και χειρότερα
Ο τετραγωνικός κώδικας σχεδόν πάντα έχει έναν βρόχο μέσα σε έναν άλλο βρόχο, όπως αυτός ο έλεγχος διπλότυπου που συγκρίνει κάθε ζεύγος:
Η ορολογία python has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
Η εκθετική και η παραγοντική ανάπτυξη είναι χειρότερες κατά πολύ. Η αναδρομική εξίσωση Fibonacci, όπως αναγράφεται στο βιβλίο, συνεχίζει να λύνει τα ίδια υποπροβλήματα ξανά και ξανά, επομένως κάθε +1 στο n διπλασιάζει περίπου την εργασία. Στο n = 20 δεν θα το προσέξετε. Στο n = 60 μπορείτε να πάτε να μαγειρέψετε δείπνο, να το φάτε, να πλύνετε τα πιάτα και πάλι να μην είναι έτοιμο.
Πώς να υπολογίσετε την πολυπλοκότητα χρόνου βήμα προς βήμα
Σχεδόν ποτέ δεν χρειάζεσαι επίσημη απόδειξη για να υπολογίσεις την πολυπλοκότητα χρόνου. Διαβάζω αυτή τη λίστα στο μυαλό μου και καλύπτει το μεγαλύτερο μέρος του κώδικα που βλέπω:
- Ορίστε το n. Αποφασίστε ποιο είναι το μέγεθος εισόδου: το μήκος μιας λίστας, ο αριθμός των κόμβων σε ένα γράφημα, ο αριθμός των ψηφίων σε έναν αριθμό.
- Μετρήστε την εργασία σε κάθε γραμμή. Απλές δηλώσεις (αναθέσεις, συγκρίσεις, αριθμητική) κοστίζουν O(1).
- Προσθέστε διαδοχικά μπλοκ. Δύο βρόχοι ο ένας μετά τον άλλον, ο καθένας πάνω από n, δίνουν n + n = 2n.
- Πολλαπλασιάστε τα ένθετα μπλοκ. Ένας βρόχος πάνω από n μέσα σε έναν άλλο βρόχο πάνω από n δίνει n × n = n².
- Σταθερές πτώσης. Το 2n γίνεται n και το 500 γίνεται 1.
- Κρατήστε μόνο τον κυρίαρχο όρο. Στο n² + n, το μέρος n² επισκιάζει το υπόλοιπο καθώς το n αυξάνεται.
Γρήγορα δούλεψε. Ο υπολογισμός σου βγαίνει T(n) = 3n² + 5n + 2. Βάλε και ένα εκατομμύριο: 3n² είναι τρία τρισεκατομμύρια, 5n είναι πέντε εκατομμύρια. Σφάλμα στρογγυλοποίησης. Πες το O(n²), τελείωσε.
Οι βρόχοι που παραλείπουν αντί να κάνουν ένα βήμα παραπέρα είναι πιο ύπουλοι:
python def count_halvings(n): steps = 0 ενώ n > 1: n //= 2 steps += 1 return steps
Κάθε πέρασμα κόβει το n στη μέση, οπότε αυτός ο βρόχος while εγκαταλείπει μετά από περίπου log₂(n) γύρους. Η οποία είναι ουσιαστικά ολόκληρη η απάντηση στο ερώτημα "πότε η χρονική πολυπλοκότητα είναι O(log n);" Αν ό,τι απομένει συρρικνώνεται κατά έναν σταθερό παράγοντα σε κάθε βήμα, είστε εκεί.
Η αναδρομή χρειάζεται ένα ακόμη εργαλείο, μια αναδρομή. Η ταξινόμηση συγχώνευσης εκτελεί δύο εργασίες μισού μεγέθους και στη συνέχεια μια συγχώνευση, οπότε T(n) = 2T(n/2) + n. Το κύριο θεώρημα είναι ένα απλό παράδειγμα αναδρομής για αναδρομές αυτού του σχήματος, και για αυτήν εδώ βγάζει O(n log n).
Και ένας εμπειρικός κανόνας από τον ανταγωνιστικό προγραμματισμό στον οποίο βασίζομαι πολύ: μια κανονική μηχανή εκτελεί περίπου 10⁸ απλές λειτουργίες το δευτερόλεπτο. Πολύ πρόχειρο, αλλά είναι αρκετό για να ελέγξετε λογικά την χρονική πολυπλοκότητα μιας λύσης πριν πατήσετε υποβολή. Με n στα 10⁵, το O(n²) είναι περίπου 10¹⁰ λειτουργίες, άρα έχετε χρονικό όριο. Το O(n log n) είναι κάτω από 2 εκατομμύρια. Τα καταφέρνει.
Ανάλυση της Χειρότερης, της Καλύτερης και της Μέσης Περίπτωσης
Αν εισάγετε στον ίδιο αλγόριθμο διαφορετικά δεδομένα εισόδου, η ποσότητα εργασίας μπορεί να μεταβληθεί δραματικά. Η γραμμική αναζήτηση το δείχνει αυτό όμορφα:
- Στην καλύτερη περίπτωση: αυτό που θέλετε είναι να κάθεται ακριβώς μπροστά. Μία σύγκριση και είστε έξω.
- Στη χειρότερη περίπτωση: είναι στο τέλος ή δεν υπάρχει καθόλου. Αυτές είναι συγκρίσεις.
- Μέση περίπτωση: αν μπορούσε να είναι οπουδήποτε με ίσες πιθανότητες, θα ελέγχατε γύρω στο n/2 κατά μέσο όρο. Παραμένει O(n), σημειώστε.
Ρωτήστε έναν προγραμματιστή για την «πολυπλοκότητα» κάποιου πράγματος και σχεδόν πάντα θα σας δώσει την πολυπλοκότητα του χρόνου στη χειρότερη περίπτωση, επειδή αυτός ο αριθμός είναι μια υπόσχεση γύρω από την οποία μπορείτε να σχεδιάσετε.
Ας υποθέσουμε ότι το API σας χειρίζεται ένα αίτημα σε O(n) στη χειρότερη περίπτωση. Τέλεια, τώρα ξέρετε πώς συμπεριφέρεται το πιο αργό αίτημα και είστε επίσης καλυμμένοι όταν κάποιος σας στείλει άχρηστα μηνύματα επίτηδες. Οι άνθρωποι το κάνουν σίγουρα αυτό: αν ένας εισβολέας καταλάβει ποια κλειδιά προκαλούν τη σύγκρουση του πίνακα κατακερματισμού σας, αυτά είναι τα μόνα κλειδιά που θα βλέπετε για λίγο καιρό.
Αξίζει να εξετάσουμε τη μέση περίπτωση όταν το κακό σενάριο σπάνια εμφανίζεται. Η γρήγορη ταξινόμηση είναι το παιδί-αφίσα εδώ, με μέσο όρο O(n log n) αλλά ολισθαίνει στο O(n²) αν επιλέξετε αφελώς pivots σε δεδομένα που έχουν ήδη ταξινομηθεί. Οι τυπικές βιβλιοθήκες το παρακάμπτουν αυτό με τυχαίους pivots ή μεταβαίνοντας σε διαφορετικό αλγόριθμο ταξινόμησης όταν η αναδρομή φτάσει σε ύποπτα μεγάλο βάθος.
Τι είναι η Πολυπλοκότητα του Διαστήματος και ο Βοηθητικός Χώρος;
Η μνήμη είναι ο άλλος λογαριασμός που καταβάλλει ένας αλγόριθμος. Η πολυπλοκότητα του χώρου παρακολουθεί πόση από αυτήν χρειάζεστε καθώς το μέγεθος της εισόδου αυξάνεται και την γράφετε με την ίδια σημειογραφία Big O όπως ο χρόνος.
Μέρος αυτής της μνήμης είναι η ίδια η είσοδος, την οποία πληρώνετε ανεξάρτητα από το τι κάνετε με αυτήν. Το μέρος που ελέγχετε στην πραγματικότητα ονομάζεται βοηθητικός χώρος, που σημαίνει τα επιπλέον στοιχεία που διαθέτει ο κώδικάς σας ενώ λειτουργεί, όπως προσωρινές μεταβλητές και νέους πίνακες, καθώς και τη στοίβα κλήσεων που κανείς δεν θυμάται μέχρι να τους "δαγκώσει".
Μερικές γρήγορες περιπτώσεις:
- Η εναλλαγή δύο μεταβλητών χρειάζεται μερικές θέσεις ανεξάρτητα από οτιδήποτε άλλο, επομένως είναι βοηθητικός χώρος O(1).
- Η αντιγραφή μιας λίστας n στοιχείων σε μια νέα λίστα σας κοστίζει O(n) επιπλέον μνήμη.
- Η επαναλαμβανόμενη δημιουργία n επιπέδων σε βάθος αφήνει n πλαίσια στη στοίβα, η οποία είναι χώρος O(n) παρόλο που δεν δημιουργήσατε ποτέ πίνακα.
Είδα έναν νεότερο προγραμματιστή να χάνει ένα απόγευμα εξαιτίας αυτού του τελευταίου. Η αναδρομική τους συνάρτηση φαινόταν σαν να μην χρησιμοποιούσε καθόλου μνήμη, αλλά κάθε ημιτελής κλήση ήταν παρκαρισμένη στη στοίβα περιμένοντας να επιστρέψουν οι βαθύτερες, και σε μια μεγάλη είσοδο ολόκληρο το σύστημα τερματίστηκε με υπερχείλιση στοίβας.
Πολλές φορές η βελτιστοποίηση γίνεται απλώς με ανταλλαγή μνήμης με χρόνο ή αντίστροφα. Η απομνημόνευση αποθηκεύει στην προσωρινή μνήμη τα αποτελέσματα που έχετε ήδη υπολογίσει, γεγονός που μειώνει τον αφελή Fibonacci από O(2ⁿ) σε O(n) χρόνο με αντάλλαγμα O(n) μνήμη. Οι πίνακες κατακερματισμού σας αγοράζουν μέσο όρο αναζητήσεων O(1) δαπανώντας χώρο σε buckets. Σε έναν διακομιστή με 64 GB RAM, αυτή η ανταλλαγή είναι συνήθως αυτονόητη, αλλά σε έναν μικροελεγκτή ή μέσα σε ένα έξυπνο συμβόλαιο θα το σκεφτόσασταν δύο φορές.
Χρονική και χωρική πολυπλοκότητα κοινών δομών δεδομένων
Η επιλογή της σωστής δομής δεδομένων συνήθως υπερτερεί της μικρορύθμισης ό,τι υπάρχει μέσα στον βρόχο σας. Μέσο κόστος για αυτά που θα βρείτε στις περισσότερες περιπτώσεις:
| Δομή δεδομένων | Πρόσβαση | Ερευνα | Εισάγω | Διαγράφω | Χώρος |
|---|---|---|---|---|---|
| Παράταξη | Ο(1) | Επί) | Επί) | Επί) | Επί) |
| Συνδεδεμένη λίστα | Επί) | Επί) | Ο(1) | Ο(1) | Επί) |
| Πίνακας κατακερματισμού | δ/υ | Ο(1) | Ο(1) | Ο(1) | Επί) |
| Ισορροπημένο δυαδικό δέντρο αναζήτησης | O(log n) | O(log n) | O(log n) | O(log n) | Επί) |
| Δυαδική σωρός | O(1) για ελάχιστο/μέγιστο | Επί) | O(log n) | O(log n) | Επί) |
Δύο υποσημειώσεις. Οι εισαγωγές και οι διαγραφές σε συνδεδεμένες λίστες είναι O(1) μόνο εάν ήδη κρατάτε τον κόμβο. Και ένας πίνακας κατακερματισμού μπορεί να βυθιστεί στο O(n) όταν συγκρούονται πολλά κλειδιά.
Οι αλγόριθμοι ταξινόμησης ποικίλλουν εξίσου:
| Αλγόριθμος ταξινόμησης | Καλύτερος | Μέσος | Κατισχύω | Βοηθητικός χώρος |
|---|---|---|---|---|
| Ταξινόμηση με φυσαλίδες | Επί) | Ο(n²) | Ο(n²) | Ο(1) |
| Ταξινόμηση συγχώνευσης | O(n log n) | O(n log n) | O(n log n) | Επί) |
| Γρήγορη ταξινόμηση | O(n log n) | O(n log n) | Ο(n²) | O(log n) |
| Ταξινόμηση σωρού | O(n log n) | O(n log n) | O(n log n) | Ο(1) |
Η ταξινόμηση με συγχώνευση είναι προβλέψιμη αλλά απαιτεί επιπλέον μνήμη. Η ταξινόμηση σε σωρό ταξινομεί στη θέση της και διατηρεί την ίδια χειρότερη περίπτωση. Η γρήγορη ταξινόμηση, παρά το πιο άσχημο όριο, τείνει να κερδίζει στην πράξη.
Χρονική Πολυπλοκότητα στο Blockchain και τα Έξυπνα Συμβόλαια
Εδώ είναι που γίνεται διασκεδαστικό. Στον δικό σας διακομιστή, ένας πρόχειρος αλγόριθμος σπαταλάει CPU και ίσως ενοχλεί έναν χρήστη. Στο Ethereum ή σε οποιαδήποτε αλυσίδα EVM, σπαταλά χρήματα. Κάθε κωδικός λειτουργίας που εκτελεί ένα έξυπνο συμβόλαιο κοστίζει καύσιμο, πληρωμένο στο εγγενές νόμισμα της αλυσίδας, επομένως ο αριθμός των λειτουργιών σας εμφανίζεται ως γραμμή στον λογαριασμό κάποιου. Η πολυπλοκότητα σε κακή χρονική στιγμή, με άλλα λόγια, έχει ένα κόστος.
Ας υποθέσουμε ότι έχετε ένα συμβόλαιο που επαναλαμβάνεται σε κάθε κάτοχο token για να καταβάλει ανταμοιβές. O(n), και το αέριο πλησιάζει σιγά σιγά με κάθε νέο κάτοχο. Την ημέρα της κυκλοφορίας κανείς δεν το προσέχει.
Στη συνέχεια, η λίστα κατόχων συνεχίζει να μεγαλώνει. Κάποια μέρα, η πληρωμή χρειάζεται περισσότερο αέριο από το όριο αερίου του μπλοκ, το οποίο είναι το ανώτατο όριο στην ποσότητα αερίου που μπορεί να χωρέσει ένα μόνο μπλοκ. Μετά από αυτό, η συναλλαγή δεν μπορεί να ολοκληρωθεί. Όχι «είναι αργή». Απλώς δεν πετυχαίνει ποτέ, και όποια κεφάλαια περίμεναν πίσω από αυτή τη λειτουργία ουσιαστικά κολλάνε. Οι ελεγκτές κατατάσσουν απεριόριστους βρόχους όπως αυτόν στην κατηγορία άρνησης υπηρεσίας, και είναι δίκαιο.
Οι λύσεις είναι η πολυπλοκότητα, απλή και ξεκάθαρη:
- Χωρίστε την εργασία σε παρτίδες σταθερού μεγέθους σε διάφορες συναλλαγές.
- Γυρίστε το ανάποδα, ώστε κάθε χρήστης να διεκδικήσει τη δική του ανταμοιβή. Κάθε κλήση είναι O(1).
- Αντικαταστήστε τον βρόχο με μια απόδειξη Merkle.
Λατρεύω τις αποδείξεις Merkle ως παράδειγμα του γιατί το log n έχει τόσο μεγάλη σημασία στην αλυσίδα. Ένα δέντρο Merkle κατακερματίζει ένα μεγάλο σωρό δεδομένων σε ένα μόνο root hash.
Για να αποδείξετε ότι μια καταχώρηση ανήκει σε ένα σύνολο n, χρειάζεστε περίπου log₂(n) hashes. Για ένα εκατομμύριο καταχωρήσεις αυτό είναι περίπου 20. Όχι ένα εκατομμύριο. Τα Airdrops βασίζονται σε αυτό, και τα light Bitcoin wallets χρησιμοποιούν το ίδιο κόλπο για να επιβεβαιώσουν μια συναλλαγή χωρίς να κατεβάσουν ολόκληρο το μπλοκ.
Εκτός αλυσίδας, η ίδια συμφωνία. Φανταστείτε ένα backend πληρωμών που αντιστοιχίζει κάθε εισερχόμενη συναλλαγή blockchain με ένα τιμολόγιο σαρώνοντας κάθε ανοιχτή. O(n) ανά πληρωμή, και γίνεται πιο αργό καθώς το κατάστημα μεγαλώνει. Τοποθετήστε τα τιμολόγια σε έναν χάρτη κατακερματισμού με κλειδί διεύθυνσης ή ταυτότητας και κάθε αντιστοίχιση είναι O(1). Και αν προτιμάτε να μην κατασκευάσετε και να επιμεληθείτε μόνοι σας αυτές τις υδραυλικές εγκαταστάσεις, μια πύλη κρυπτοπληρωμής όπως το Plisio το κάνει για εσάς.
