L03 · D&C I — Mergesort & Master Theorem

Τι θα δούμε

Στα L01 και L02 μάθαμε να αποτιμούμε και να συγκρίνουμε αλγορίθμους. Από εδώ και πέρα αλλάζουμε ερώτηση: πώς σχεδιάζουμε έναν καλό αλγόριθμο από το μηδέν;

Αυτή η διάλεξη είναι η πρώτη τεχνική σχεδίασης του μαθήματος. Στόχοι:

1. Να καταλάβουμε το «διαίρει και κυρίευε» ως σχήμα — όχι έναν αλγόριθμο, αλλά μια ολόκληρη οικογένεια αλγορίθμων που χτίζονται με τον ίδιο τρόπο.
2. Να δούμε το αστέρι της οικογένειας, τη συγχωνευτική ταξινόμηση (mergesort), και να αποδείξουμε ότι τρέχει σε $O(n\log n)$ — με τέσσερις διαφορετικούς τρόπους, γιατί καθένας διδάσκει μια χρήσιμη τεχνική.
3. Να βγάλουμε ένα γενικό εργαλείο, το Master Theorem, που λύνει μια ολόκληρη οικογένεια αναδρομικών σχέσεων χωρίς απόδειξη από την αρχή.
4. Να δούμε, με τον πύργο του Hanoi, ότι το σχήμα D&C από μόνο του δεν εγγυάται γρήγορο αλγόριθμο.

Γρήγορη υπενθύμιση από το L02

Όλη η διάλεξη μιλάει για χρόνους εκτέλεσης, οπότε ας ξανασυμφωνήσουμε στη γλώσσα. Από το L02:

• $T(n)=O(f(n))$ — άνω φράγμα: η $T$ δεν αυξάνεται γρηγορότερα από την $f$.
• $T(n)=\Omega (f(n))$ — κάτω φράγμα: δεν αυξάνεται πιο αργά.
• $T(n)=\Theta (f(n))$ — ακριβές φράγμα: ίδιος ρυθμός, και από τις δύο μεριές.

Και η κλίμακα πολυπλοκοτήτων, που θα χρησιμοποιήσουμε διαρκώς:

$1\prec \log n\prec n\prec n\log n\prec n^2\prec n^3\prec \cdots \prec 2^n\prec n!$

Όσα είναι αριστερά (πολυωνυμικά) είναι «καλά»· όσα είναι δεξιά (εκθετικά) είναι «κακά». Κράτα ειδικά στο μυαλό σου τη θέση του $n\log n$ — ανάμεσα στο γραμμικό και στο τετραγωνικό. Εκεί ζει η mergesort.

Ζέσταμα: το μέγιστο ενός πίνακα

Πριν επιτεθούμε στο σύνθετο πρόβλημα της ταξινόμησης, ένα μίνι πρόβλημα για να ξαναβρούμε τον ρυθμό της ανάλυσης. Δοθέντος πίνακα $a_1,a_2,\dots ,a_n$, βρες το μέγιστο στοιχείο.

Η πιο φυσική ιδέα: κράτα έναν «τρέχοντα νικητή» και διέτρεξε τον πίνακα μία φορά.

Πόσες συγκρίσεις; Ακριβώς $n-1$ — μία για κάθε στοιχείο πέρα από το πρώτο, ανεξάρτητα από την είσοδο. Άρα $\Theta (n)$.

Υπάρχει και μια δεύτερη ιδέα: σάρωσε τα γειτονικά ζευγάρια κι αντάλλασσε ώστε το μεγαλύτερο να «σπρώχνεται» προς το τέλος· στο τέλος, το $a_n$ είναι το μέγιστο. Πάλι $n-1$ συγκρίσεις, πάλι $\Theta (n)$.

Το πρόβλημα: ταξινόμηση

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

Γιατί ξοδεύουμε ολόκληρη διάλεξη στην ταξινόμηση; Γιατί είναι παντού. Οι προφανείς χρήσεις — μια αλφαβητική λίστα, μια playlist, αρχεία ταξινομημένα κατά ημερομηνία — είναι μόνο η αρχή. Το πραγματικό κέρδος είναι ότι μια ταξινομημένη λίστα ξεκλειδώνει δεκάδες άλλα προβλήματα:

• Δυαδική αναζήτηση σε $O(\log n)$ αντί για $O(n)$ — όπως είδαμε στο L01.
• Μεσαίο στοιχείο σε $O(1)$, ακραίες τιμές στις άκρες, διπλότυπα σε ένα γραμμικό πέρασμα (τα ίσα στοιχεία στέκονται πλέον δίπλα-δίπλα).
• Πλησιέστερο ζευγάρι αριθμών: σε ταξινομημένη λίστα είναι κάποιο γειτονικό ζευγάρι — $O(n)$.

Και αμέτρητα προβλήματα χρησιμοποιούν την ταξινόμηση ως κρυφό υποπρόβλημα: συμπίεση δεδομένων (Huffman, L12), γραφικά, υπολογιστική βιολογία, ο αλγόριθμος Kruskal για ελάχιστα συνδετικά δέντρα (L09) που απαιτεί ταξινομημένες ακμές.

Πρώτη προσπάθεια: bubble & insertion sort

Πριν δούμε το «έξυπνο» mergesort, ας δούμε τι μας δίνει η πιο αφελής σκέψη — δύο κλασικοί απλοί αλγόριθμοι.

Πριν δούμε γιατί, ας τη νιώσουμε. Πατώντας ▶ τρέχεις και τους τρεις αλγορίθμους στον ίδιο πίνακα 10 στοιχείων· κάθε αλγόριθμος έχει τον δικό του μετρητή συγκρίσεων, και βλέπεις πόσο γρηγορότερα γεμίζει ο της mergesort. Άλλαξε σε «Αντίστροφος» για να δεις τη χειρότερη είσοδο της insertion (όπου ισοφαρίζει την bubble) και σε «Σχεδόν ταξινομημένος» για τη βέλτιστη (όπου η insertion γίνεται σχεδόν γραμμική):

Δύο πράγματα να προσέξεις. Η bubble sort είναι ανεπηρέαστη: 45 συγκρίσεις και στις τρεις περιπτώσεις, γιατί ο εξωτερικός βρόχος δεν «βλέπει» τι έγινε μέσα. Η insertion sort είναι έξυπνη: για σχεδόν-ταξινομημένη είσοδο τελειώνει σε πολύ λιγότερες συγκρίσεις. Αλλά καμιά από τις δύο δεν είναι κοντά στη mergesort όταν η είσοδος είναι τυχαία ή αντίστροφη — και η απόσταση ανοίγει όσο μεγαλώνει το $n$, ακριβώς όπως λέει το $n^2$ vs $n\log n$.

Η μεγάλη ιδέα: διαίρει και κυρίευε

Πρέπει να σπάσουμε το φράγμα του $\Theta (n^2)$. Από πού πιάνεται κανείς; Από μια πολύ ανθρώπινη ιδέα.

Divide et impera!

Σχόλιο

(λατινικό: «διαίρει και βασίλευε»)

Η τεχνική διαίρει και κυρίευε (D&C) βασίζεται σε τρία βήματα:

1. Διαίρει τα δεδομένα σε μικρότερα υποπροβλήματα χωρίς κοινά στοιχεία (ξένα μεταξύ τους).
2. Κυρίευσε κάθε υποπρόβλημα ξεχωριστά και αναδρομικά — εφαρμόζοντας ξανά τον ίδιο αλγόριθμο.
3. Συνδύασε τις επιμέρους λύσεις σε λύση του αρχικού προβλήματος.

Γιατί δουλεύει: είναι επαγωγή μεταμφιεσμένη

Η D&C δεν είναι ένα κόλπο που «τυχαίνει» να δουλεύει — είναι επαγωγική κατασκευή της λύσης. Για να σχεδιάσεις έναν τέτοιο αλγόριθμο, αρκεί (και χρειάζεται) να ξέρεις δύο πράγματα:

1. Βάση: πώς λύνεται το πρόβλημα για πολύ μικρή, σταθερή είσοδο — π.χ. $n=1$.
2. Επαγωγικό βήμα: πώς συνδυάζονται οι ορθές λύσεις των μικρότερων υποπροβλημάτων σε μία ορθή λύση για όλη την είσοδο.

Συγχωνευτική ταξινόμηση: η ιδέα

Ας ντύσουμε την αναλογία της στοίβας με γραπτά σε αλγόριθμο. Πώς ταξινομούμε με D&C;

1. Βάση. Πίνακας με ένα στοιχείο είναι ήδη ταξινομημένος — τον επιστρέφουμε ως έχει.
2. Αλλιώς: διαίρεσε τον πίνακα στη μέση· ταξινόμησε αναδρομικά καθένα από τα δύο μισά· συγχώνευσε τις δύο ταξινομημένες λίστες σε μία.

Όλο το βάρος της σκέψης είναι: «αν ξέρω να συγχωνεύω δύο ταξινομημένες λίστες, τότε ξέρω να ταξινομώ τα πάντα» — η αναδρομή αναλαμβάνει το υπόλοιπο. Πριν γράψουμε γραμμή ψευδοκώδικα, πάτα Επόμενο και δες το να συμβαίνει — πρώτα η φάση Διαίρει μέχρι τους πίνακες ενός στοιχείου, μετά η φάση Συγχώνευσε προς τα πάνω:

Πρόσεξε αυτό που μετράει το «Δουλειά συγχώνευσης ανά επίπεδο»: κάθε επίπεδο συγχώνευσης κοστίζει περίπου $n$ πράξεις, και τα επίπεδα είναι λίγα — όσα και τα μισαρίσματα μέχρι το 1. Κράτα το· είναι ολόκληρη η απόδειξη του $O(n\log n)$ σε μία εικόνα.

Η συγχώνευση δύο ταξινομημένων πινάκων

Είδαμε ότι η mergesort στηρίζεται όλη πάνω σε μία πράξη: τη συγχώνευση. Ας τη χτίσουμε προσεκτικά — είναι το «επαγωγικό βήμα» του αλγορίθμου.

Σκέψου δύο ουρές στο supermarket που πρέπει να γίνουν μία ταξινομημένη ουρά: κρατάς δύο δείκτες $i$ και $j$, έναν στην αρχή κάθε ουράς, κοιτάς τα δύο πρώτα στοιχεία, παίρνεις το μικρότερο και προχωράς τον αντίστοιχο δείκτη. Επανάληψη, μέχρι να αδειάσουν και οι δύο ουρές. Πάτα Επόμενο και δες ακριβώς αυτό να συμβαίνει — ή πέρασε σε «Δοκίμασε εσύ» για να διαλέξεις μόνος σου ποια μεριά να τραβήξεις:

Δύο παρατηρήσεις που θα μας χρησιμεύσουν αμέσως μετά: (1) κάθε βήμα προχωρά ακριβώς έναν δείκτη, οπότε ο συνολικός αριθμός βημάτων είναι το πολύ $m+n$· (2) η συγχώνευση εκμεταλλεύεται το ότι οι δύο είσοδοι είναι ήδη ταξινομημένες — το μικρότερο στοιχείο που δεν έχει γραφτεί ακόμα είναι σίγουρα κάποιο από τα δύο «πάνω-πάνω».

Ο αλγόριθμος mergesort

Με τη συγχώνευση έτοιμη, ο πλήρης αλγόριθμος είναι σχεδόν τετριμμένος — γι' αυτό άλλωστε δουλεύει το D&C: μόλις λύσεις το «επαγωγικό βήμα», ο αλγόριθμος γράφεται μόνος του.

Το δέντρο αναδρομής

Πριν αποδείξουμε τυπικά ότι $T(n)=O(n\log n)$, ας δούμε πού πάει η δουλειά. Ζωγραφίζουμε το δέντρο αναδρομής: η ρίζα είναι η αρχική κλήση, και κάθε κλήση κρεμάει από κάτω τις δύο αναδρομικές κλήσεις της. Για $n=8$:

Το κλειδί είναι μία παρατήρηση: κάθε επίπεδο του δέντρου κάνει συνολικά $n$ συγκρίσεις. Γιατί;

• Στο επίπεδο 1 έχουμε 2 υποπροβλήματα μεγέθους $n/2$. Η συγχώνευση καθενός κοστίζει $n/2$ → σύνολο $n$.
• Στο επίπεδο 2 έχουμε 4 υποπροβλήματα μεγέθους $n/4$, κόστος $n/4$ το καθένα → σύνολο $n$.
• Σε γενικό επίπεδο $k$ έχουμε $2^k$ υποπροβλήματα μεγέθους $n/2^k$ → σύνολο πάλι $n$.

Τα υποπροβλήματα πληθαίνουν, αλλά ταυτόχρονα μικραίνουν στον ίδιο ρυθμό — οπότε το γινόμενο μένει σταθερό. Και πόσα επίπεδα υπάρχουν; Όσα τα μισαρίσματα του $n$ μέχρι το 1, δηλαδή ${\log }_{2}n$. Άρα:

Αυτή είναι η διαίσθηση. Τώρα ας τη μετατρέψουμε σε αυστηρή απόδειξη — και μάλιστα με τέσσερις τρόπους.

Η αναδρομική σχέση της mergesort

Ορίζουμε $T(n)$ ως την πολυπλοκότητα της mergesort για είσοδο μεγέθους $n$. Διαβάζοντας τον ψευδοκώδικα:

Σε λόγια: για $n=1$ καμία σύγκριση· για $n>1$, το κόστος του αριστερού μισού συν του δεξιού μισού συν $n$ για τη συγχώνευση.

Στόχος: να δείξουμε ότι $T(n)=O(n\log n)$. Θα το κάνουμε τέσσερις φορές, με διαφορετική τεχνική κάθε φορά — κάθε τεχνική επιστρέφει σε άλλες αναδρομικές σχέσεις παρακάτω στο μάθημα.

Απόδειξη #1 — διαίρεση με n (τηλεσκόπιο)

Υποθέτουμε ότι το $n$ είναι δύναμη του 2, οπότε δεν χρειάζονται πατώματα/οροφές και η σχέση γίνεται καθαρά:

Το τέχνασμα: διαιρούμε και τα δύο μέλη με $n$.

Αν θέσουμε $U(n)=T(n)/n$, η σχέση απλοποιείται σε κάτι πανεύκολο:

Εφαρμόζοντας την ίδια ταυτότητα ξανά και ξανά, οι όροι τηλεσκοπούν:

Όταν φτάσουμε στο $U(1)=T(1)/1=0$, μένει $U(n)={\log }_{2}n$, άρα:

Απόδειξη #2 — επαγωγή στον διπλασιασμό

Επαγωγή πάνω στο $n$ (πάλι με $n=2^k$). Θέλουμε να δείξουμε $T(n)=n\log n$.

Βάση. $T(1)=0=1\cdot \log 1$. ✓

Επαγωγική υπόθεση. Έστω ότι ισχύει $T(n)=n\log n$.

Επαγωγικό βήμα. Δείχνουμε ότι ισχύει και για τον διπλάσιο $2n$:

Χρησιμοποιήσαμε $\log 2=1$ (με $\log ={\log }_2$) και την ταυτότητα $\log a+\log b=\log (ab)$. $■$

Απόδειξη #3 — πολλαπλασιασμός γραμμών

Πιο γενική εκδοχή του τηλεσκοπίου, που δουλεύει για οποιαδήποτε σταθερά $c>0$: αν $T(n)\le 2T(n/2)+cn$, τότε $T(n)\le cn\log n$.

Πώς. Γράφουμε τη σχέση επανειλημμένα, πολλαπλασιάζοντας κάθε γραμμή με $2^{k-1}$, ώστε οι μεσαίοι όροι να ταιριάξουν:

Προσθέτουμε όλες τις γραμμές. Κάθε όρος της μορφής $2^{j}T(n/2^j)$ εμφανίζεται μία φορά αριστερά και μία δεξιά — τηλεσκοπεί — και μένει:

Για $n=2^k$ (άρα $k={\log }_{2}n$) και $T(1)=0$:

Άρα $T(n)=O(n\log n)$. $■$

Απόδειξη #4 — η γενική περίπτωση (με οροφές)

Οι τρεις πρώτες αποδείξεις υπέθεσαν $n=2^k$. Τι γίνεται αν το $n$ είναι οποιοσδήποτε αριθμός (π.χ. 100, 1000, 13.547);

Θεώρημα. Για τη σχέση

ισχύει $T(n)\le n\lceil \log n\rceil$.

Απόδειξη με ισχυρή επαγωγή στο $n$.

Βάση ($n=1$): $T(1)=0\le 1\cdot \lceil \log 1\rceil =0$. ✓

Επαγωγική υπόθεση. Η σχέση ισχύει για κάθε $k=1,2,\dots ,n-1$.

Επαγωγικό βήμα. Θέτουμε $n_1=\lfloor n/2\rfloor$ και $n_2=\lceil n/2\rceil$. Ισχύει $n_1+n_2=n$ και $n_1\le n_2$.

Δικαιολόγηση του $(\star )$. Από τον ορισμό της οροφής, $n\le 2^{\lceil \log n\rceil }$, άρα:

Παίρνοντας λογάριθμο, $\log n_2\le \lceil \log n\rceil -1$· και επειδή το δεξί μέλος είναι ακέραιος, ισχύει και με οροφή: $\lceil \log n_2\rceil \le \lceil \log n\rceil -1$. $■$

Γιατί «στη μέση»; Και τι μετράει πραγματικά για την πολυπλοκότητα;

Τώρα μπορούμε να απαντήσουμε στην ερώτηση που αφήσαμε ανοιχτή — και μάλιστα να την επεκτείνουμε. Δύο διαφορετικά «λάθος» διαχωρίσματα:

• Αναλογικός αλλά άνισος, π.χ. 60/40 ή 90/10. Το ένα κομμάτι είναι μεγαλύτερο, αλλά είναι πάντα σταθερό ποσοστό του γονικού.
• Σταθερό κομμάτι, π.χ. «$n-2$ και $2$». Το μικρό κομμάτι έχει σταθερό μέγεθος, ανεξάρτητο από το $n$.

Η διαίσθηση που μετράει είναι το βάθος του δέντρου αναδρομής — γιατί η δουλειά ανά επίπεδο μένει $\sim n$ έτσι κι αλλιώς (τα κομμάτια καλύπτουν όλη την είσοδο), οπότε το συνολικό κόστος είναι «βάθος × $n$». Δοκίμασε και τα δύο και πρόσεξε το σχήμα του δέντρου:

Ο σταθερός διαχωρισμός γεννά μια καμπύλη — ένα μακρόστενο δέντρο όπου κάθε επίπεδο μειώνεται μόνο κατά $c$ — άρα χρειάζεται $n/c$ επίπεδα. Πολλαπλασίασε με τα $n$ ανά επίπεδο και βγαίνει $\Theta (n^2)$. Είναι ακριβώς το ίδιο πρόβλημα με την bubble sort, χωρίς καμιά βελτίωση.

Με μαθηματικά: για διαχωρισμό «$n-2$ και $2$» η αναδρομή γίνεται $T(n)=T(n-2)+\Theta (n)$, και ξεδιπλώνοντας: $T(n)=\Theta (n)+\Theta (n-2)+\Theta (n-4)+\cdots =\Theta (n^2)$ Για διαχωρισμό $1/3-2/3$ (που είναι αναλογικός, απλώς όχι ισόρροπος) η αναδρομή είναι $T(n)=T(n/3)+T(2n/3)+cn$. Το βαθύτερο μονοπάτι ακολουθεί το μεγάλο κομμάτι: $n\to \frac{2}{3}n\to (\frac{2}{3}{)}^{2}n\to \dots$, φτάνει στο 1 σε ${\log }_{3/2}n$ βήματα — ακόμη λογαριθμικό. Κάθε επίπεδο πάλι $cn$ → $T(n)=O(n\log n)$, ίδια τάξη με την ισόρροπη mergesort.

Όταν το D&C ΔΕΝ είναι γρήγορο: ο πύργος του Hanoi

Μέχρι τώρα το D&C φαίνεται μαγικό. Ένα διάσημο παράδειγμα δείχνει ότι δεν είναι — το σχήμα από μόνο του δεν εγγυάται τίποτα.

Πρόβλημα. Υπάρχουν 3 στύλοι (A, B, C) και $n$ δίσκοι στοιβαγμένοι στον στύλο A σε κωνική μορφή (μεγάλος κάτω, μικρός πάνω). Θέλουμε να τους μεταφέρουμε όλους στον C, με κανόνες: (1) μετακινούμε έναν δίσκο κάθε φορά, (2) παίρνουμε πάντα τον κορυφαίο δίσκο ενός στύλου, (3) ποτέ δεν βάζουμε δίσκο πάνω σε μικρότερό του.

Το D&C το ξεκλειδώνει σε τρεις γραμμές. Παρατήρησε: για να μετακινήσεις τον μεγαλύτερο δίσκο, πρέπει πρώτα να έχεις «αδειάσει» τους $n-1$ από πάνω του στον βοηθητικό στύλο.

Δες το να δουλεύει — και κυρίως πέρασε στην καρτέλα «Δες την έκρηξη» για να καταλάβεις γιατί αυτή η όμορφη D&C σχεδίαση γεννά εκθετικό κόστος:

Πολυπλοκότητα. Έστω $T(n)$ ο αριθμός κινήσεων. Οι δύο αναδρομικές κλήσεις κοστίζουν $T(n-1)$ η καθεμία, συν 1 κίνηση για τον μεγάλο δίσκο:

Λύνοντας (ξεδιπλώνοντας τη σχέση): $T(n)=2^n-1$. (Έλεγχος: $T(1)=1$, $T(2)=3$, $T(3)=7=2^3-1$. ✓)

Το Master Theorem

Παρατήρησε ένα μοτίβο: αναδρομικές σχέσεις της μορφής $T(n)=aT(n/b)+f(n)$ προκύπτουν συνέχεια στους αλγορίθμους D&C. Αντί να τις λύνουμε από την αρχή κάθε φορά, υπάρχει ένα έτοιμο θεώρημα που τις λύνει.

Τα τρία σύμβολα: $a$ = πόσα υποπροβλήματα φτιάχνεις, $b$ = πόσες φορές μικραίνει το καθένα, $d$ = ο εκθέτης του κόστους του συνδυαστικού βήματος $f(n)=O(n^d)$. Όλη η ουσία είναι μια σύγκριση: ο εκθέτης $d$ (κόστος συνδυασμού) εναντίον του ${\log }_{b}a$ (ρυθμός που πληθαίνει το δέντρο). Ό,τι είναι μεγαλύτερο, κυριαρχεί.

Διαισθητική απόδειξη μέσω δέντρου αναδρομής

Από πού βγαίνουν οι τρεις περιπτώσεις; Ξαναγυρνάμε στο δέντρο αναδρομής. Στο επίπεδο $k$:

• υπάρχουν $a^k$ υποπροβλήματα,
• καθένα έχει μέγεθος $n/b^k$,
• καθένα απαιτεί $O((n/b^k{)}^d)$ συνδυαστική δουλειά.

Άρα η συνολική δουλειά στο επίπεδο $k$ είναι:

Όλο εξαρτάται από τον λόγο $r=a/b^d$ — πόσο αλλάζει η δουλειά από επίπεδο σε επίπεδο. Αθροίζοντας για όλα τα ${\log }_{b}n$ επίπεδα:

Αυτό είναι ένα γεωμετρικό άθροισμα, και η συμπεριφορά του εξαρτάται απόλυτα από το $r$:

• $r<1$ (ισοδύναμα $d>{\log }_{b}a$): η δουλειά φθίνει· το άθροισμα συγκλίνει σε σταθερά → η ρίζα κυριαρχεί → $O(n^d)$.
• $r=1$ (ισοδύναμα $d={\log }_{b}a$): κάθε επίπεδο ίδιο· το άθροισμα είναι ${\log }_{b}n+1$ → $O(n^d\log n)$.
• $r>1$ (ισοδύναμα $d<{\log }_{b}a$): η δουλειά αυξάνει· το άθροισμα κυριαρχείται από τον τελευταίο όρο → τα φύλλα κυριαρχούν → $O(n^{{\log }_{b}a})$.

(Για την τρίτη περίπτωση: $r^{{\log }_{b}n}=(a/b^d{)}^{{\log }_{b}n}=n^{{\log }_{b}a}/n^d$, και το $O(n^d)$ μπροστά απλοποιεί τον παρονομαστή.)

Δοκίμασέ το μόνος σου. Διάλεξε $a,b,d$ — ή πάτησε ένα έτοιμο παράδειγμα — και δες ποια περίπτωση προκύπτει και γιατί (η ράβδος δείχνει τη δουλειά ανά επίπεδο):

Εφαρμογές του Master Theorem

Τέσσερις γνωστές αναδρομές, λυμένες σε μία γραμμή η καθεμία:

Δύο πράγματα αξίζουν προσοχή. Το Master Theorem δίνει για τη mergesort το ίδιο αποτέλεσμα με τις τέσσερις αποδείξεις παραπάνω — σε μία γραμμή. Και για τον Karatsuba προβλέπει $O(n^{1.585})$, που είναι καλύτερο από το αφελές $\Theta (n^2)$ του πολλαπλασιασμού — γι' αυτό το κόλπο αξίζει, και θα το δούμε αναλυτικά στο L04.

Πότε ΔΕΝ εφαρμόζεται το Master Theorem

Το θεώρημα είναι ισχυρό αλλά όχι παντοδύναμο. Δεν καλύπτει:

1. Άνισο διαχωρισμό — π.χ. $T(n)=T(n/3)+T(2n/3)+n$. Τα κομμάτια δεν έχουν κοινό $b$. → Λύσε με δέντρο αναδρομής (το κάναμε ήδη παραπάνω: $O(n\log n)$).
2. Μη πολυωνυμικό $f(n)$ — π.χ. $T(n)=2T(n/2)+n\log n$. Το $n\log n$ δεν είναι της μορφής $n^d$. → Χρειάζεται γενικευμένη εκδοχή.
3. $a<1$ ή $b\le 1$ — δεν έχει νόημα στο μοντέλο (δεν υπάρχει «μισό υποπρόβλημα», το πρόβλημα πρέπει να μικραίνει).

Σε αυτές τις περιπτώσεις επιστρέφουμε στις τεχνικές #1–#4 — γι' αυτό αξίζει να τις ξέρεις, παρά την ύπαρξη του Master Theorem.

Είναι τελικά η mergesort η καλύτερη δυνατή;

Κλείνουμε με μια ερώτηση που ανοίξαμε στο L02: η mergesort τρέχει σε $O(n\log n)$ — μπορεί κανείς να κάνει καλύτερα;

Για ταξινόμηση που χρησιμοποιεί μόνο συγκρίσεις στοιχείων, η απάντηση είναι όχι:

Θεώρημα (κάτω φράγμα). Κάθε αλγόριθμος ταξινόμησης που βασίζεται μόνο σε συγκρίσεις απαιτεί $\Omega (n\log n)$ συγκρίσεις στη χείριστη περίπτωση.

Η απόδειξη είναι μια γεωμετρική παρατήρηση. Φαντάσου τον αλγόριθμό σου σαν ένα δέντρο απόφασης: η ρίζα είναι η πρώτη σύγκριση που θα κάνει, οι δύο ακμές είναι «ναι»/«όχι», και κάθε επόμενος εσωτερικός κόμβος είναι η επόμενη σύγκριση. Το βάθος της εκτέλεσης = ο αριθμός των συγκρίσεων που θα κάνει. Το ύψος του δέντρου = η χείριστη περίπτωση.

Δες το πραγματικά να συμβαίνει — διάλεξε μια διάταξη και φωτίζεται το μονοπάτι που πρέπει να ακολουθήσει κάθε αλγόριθμος για να την εντοπίσει:

Η ουσία σε δύο σειρές: $n!$ διαφορετικές διατάξεις πρέπει να καταλήγουν σε $n!$ διαφορετικά φύλλα· ένα δυαδικό δέντρο με $n!$ φύλλα έχει ύψος $\ge \lceil {\log }_2(n!)\rceil =\Theta (n\log n)$. Άρα η mergesort, που δίνει $O(n\log n)$ άνω φράγμα, ακουμπάει το κάτω φράγμα — είναι ασυμπτωτικά βέλτιστη.

Κλείδωσε τη γνώση

Πρώτα η σκελετική δομή της mergesort — βάλε τα βήματα στη σωστή σειρά:

Τώρα το Master Theorem — συμπλήρωσε τα κενά χωρίς να κοιτάς πίσω:

Stooge Sort(A, l, r):
  if A[l] > A[r] then Swap(A[l], A[r])
  if l + 1 > r then return
  k := ⌊(r - l + 1) / 3⌋
  Stooge Sort(A, l,     r - k)   // πρώτα 2/3
  Stooge Sort(A, l + k, r    )   // τελευταία 2/3
  Stooge Sort(A, l,     r - k)   // ξανά τα πρώτα 2/3