L04 · D&C II — Inversions, Dominant Colour & Karatsuba

Τι θα δούμε

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

Εδώ θα κάνουμε κάτι πιο διδακτικό: θα πάρουμε το ίδιο ακριβώς σχήμα και θα δούμε ότι λύνει τρία προβλήματα που, με την πρώτη ματιά, δεν έχουν καμία σχέση μεταξύ τους.

1. Μέτρηση αντιστροφών σε έναν πίνακα — από $O(n^2)$ πέφτουμε σε $O(n\log n)$.
2. Κυρίαρχο χρώμα σε μια σκακιέρα — από $O(n^4)$ πέφτουμε σε $O(n^2\log n)$.
3. Πολλαπλασιασμός τεράστιων αριθμών — από $O(n^2)$ πέφτουμε σε $O(n^{1.585})$, με τον αλγόριθμο Karatsuba.

Και στις τρεις περιπτώσεις η δύσκολη δουλειά δεν είναι το σπάσιμο και δεν είναι η αναδρομή — αυτά είναι μηχανικά. Η δύσκολη δουλειά είναι το βήμα συνδυασμού: πώς ενώνω τις λύσεις των κομματιών γρήγορα. Σε κάθε πρόβλημα θα ψάξουμε ένα έξυπνο, φθηνό combine — κι αυτό είναι όλο το παιχνίδι.

Το εργαλείο: Master Theorem σε μία ματιά

Επειδή θα το χρησιμοποιήσουμε τρεις φορές σήμερα, ας το ξαναστήσουμε γρήγορα. Από το L03: αν ένας αναδρομικός αλγόριθμος έχει χρόνο

τότε η λύση δίνεται από μία απλή σύγκριση:

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

Ζέσταμα: πέντε αναδρομές

Πριν προχωρήσουμε, λύσε νοερά τις παρακάτω — είναι το είδος της «προθέρμανσης» που εμφανίζεται και στην εξέταση:

• $T(n)=T(n-1)+2$ — όχι Master Theorem (το πρόβλημα μικραίνει κατά σταθερά, όχι σε λόγο $n/b$). Τηλεσκόπιο → $\Theta (n)$.
• $T(n)=2T(n-1)+1$ — όχι Master Theorem. Ξεδιπλώνεται σε $\Theta (2^n)$ — όπως ο πύργος του Hanoi.
• $T(n)=3T(n/4)+n$ — εδώ ναι: $a=3,b=4,d=1$. Αφού ${\log }_{4}3\approx 0.79<1$, περίπτωση 1 → $T(n)=O(n)$.
• $T(n)=T(n/3)+T(2n/3)+cn$ — όχι Master Theorem (άνισος διαχωρισμός — δεν υπάρχει κοινό $b$). Με δέντρο αναδρομής → $\Theta (n\log n)$.
• $T(n)=T(\sqrt{n})+\log n$ — όχι Master Theorem. Με αλλαγή μεταβλητής $n=2^m$ → $\Theta (\log n\cdot \log \log n)$.

Πρόβλημα 1 · Μέτρηση Αντιστροφών

Νιώσε: τι μετράμε, στ' αλήθεια

Φαντάσου ότι εσύ κι ένας φίλος ακούσατε τα ίδια πέντε τραγούδια και το καθένα το βαθμολογήσατε. Εσύ τα κατατάσσεις 1ο, 2ο, 3ο, 4ο, 5ο. Ο φίλος σου τα βάζει σε άλλη σειρά. Πόσο μοιάζουν τα γούστα σας;

Ένας πολύ φυσικός τρόπος να το μετρήσεις: κοίτα κάθε ζευγάρι τραγουδιών και ρώτα «το βάλαμε στην ίδια σχετική σειρά ή ανάποδα;». Κάθε ζευγάρι που το βάλατε ανάποδα είναι μία διαφωνία. Μηδέν διαφωνίες σημαίνει πανομοιότυπο γούστο· πολλές διαφωνίες σημαίνει εντελώς αντίθετο.

Αν αριθμήσουμε τα τραγούδια με τη δική σου σειρά ως $1,2,3,4,5$, τότε η κατάταξη του φίλου σου γίνεται μια μετάθεση αυτών των αριθμών — και κάθε «διαφωνία» γίνεται ακριβώς ένα ζευγάρι αριθμών που εμφανίζονται ανάποδα μέσα στον πίνακα. Αυτό το ζευγάρι έχει ένα όνομα: αντιστροφή.

Παράδειγμα. Στον πίνακα $[1,3,5,2,4]$ οι αντιστροφές είναι:

• $(3,2)$ — το $3$ βρίσκεται πριν από το $2$, αλλά είναι μεγαλύτερο.
• $(5,2)$ — όμοια.
• $(5,4)$ — όμοια.

Σύνολο: 3 αντιστροφές.

Γιατί μας νοιάζει στην πράξη

Η μέτρηση αντιστροφών είναι το πρότυπο μέτρο ομοιότητας δύο κατατάξεων:

• Συστήματα συστάσεων (Netflix, Spotify): «βρες χρήστες με γούστο σαν το δικό σου» σημαίνει «βρες κατατάξεις με λίγες αντιστροφές ως προς τη δική σου».
• Θεωρία ψηφοφορίας — η απόσταση Kendall tau ανάμεσα σε δύο προτιμήσεις είναι ακριβώς ο αριθμός αντιστροφών.
• Μηχανές αναζήτησης — πόσο άλλαξε η σειρά των αποτελεσμάτων μετά από μια αλλαγή στον αλγόριθμο κατάταξης.

Η αφελής λύση: $\Theta (n^2)$

Ο ορισμός σχεδόν γράφει μόνος του τον πρώτο αλγόριθμο — εξέτασε κάθε δυνατό ζευγάρι.

Σωστό, αλλά αργό. Για $n=10^6$ στοιχεία μιλάμε για $\sim 10^{12}$ ελέγχους — πρακτικά αδύνατο. Χρειαζόμαστε κάτι ουσιαστικά γρηγορότερο.

Η ιδέα D&C: τρία είδη αντιστροφών

Εφαρμόζουμε το σχήμα του L03. Σπάμε τον πίνακα στη μέση, σε ένα αριστερό μισό $A_1$ κι ένα δεξί $A_2$. Τώρα κάθε αντιστροφή — κάθε ζευγάρι θέσεων $(i,j)$ — ανήκει υποχρεωτικά σε ένα ακριβώς από τρία είδη, ανάλογα με το πού πέφτουν οι δύο θέσεις:

• ① μέσα στο $A_1$: και οι δύο θέσεις στο αριστερό μισό.
• ② μέσα στο $A_2$: και οι δύο θέσεις στο δεξί μισό.
• ③ μικτές: μία θέση στο $A_1$, μία στο $A_2$.

Δες το να συμβαίνει σε έναν πραγματικό πίνακα. Πάτα Επόμενο και θα διατρέξεις και τα 28 δυνατά ζευγάρια — κάθε ένα θα προσγειωθεί σε ακριβώς ένα από τα τρία είδη, και οι τρεις μετρητές θα κρατούν παράλληλα τα δικά τους ποσά:

Η διάσπαση είναι ακριβής: κάθε ζευγάρι έπεσε σε ένα και μόνο ένα κουτί, και τα τρία κουτιά αθροισμένα δίνουν ΟΛΕΣ τις αντιστροφές. Άρα:

Τα δύο πρώτα είδη είναι δωρεάν: είναι ακριβώς το ίδιο πρόβλημα σε μικρότερη είσοδο, οπότε τα αναλαμβάνει η αναδρομή. Όλο το βάρος πέφτει στο τρίτο: πώς μετράμε τις μικτές αντιστροφές γρήγορα;

Το κλειδί: μικτές αντιστροφές σε γραμμικό χρόνο

Αν μετρούσαμε τις μικτές μία-μία, θα ξαναπέφταμε στο $\Theta (n^2)$ — δεν θα κερδίζαμε τίποτα. Χρειαζόμαστε ένα κόλπο. Και το κόλπο κρύβεται σε μία απαίτηση:

Γιατί δουλεύει αυτό; Σάρωσε τα δύο ταξινομημένα μισά με δύο δείκτες, $i$ πάνω από το αριστερό και $j$ πάνω από το δεξί, και κάθε φορά κατέβαζε στο αποτέλεσμα το μικρότερο από τα δύο μπροστινά στοιχεία. Παρατήρησε τι σημαίνει το να «κερδίσει» το δεξί:

Αν το μπροστινό στοιχείο του δεξιού μισού είναι μικρότερο από το μπροστινό του αριστερού, τότε — επειδή το αριστερό μισό είναι ταξινομημένο — είναι μικρότερο και από όλα τα υπόλοιπα στοιχεία του αριστερού. Καθένα τους είναι μεγαλύτερο και βρίσκεται σε προγενέστερη θέση: καθένα τους σχηματίζει μία μικτή αντιστροφή με αυτό το δεξί στοιχείο.

Αν στο αριστερό μισό μένουν $k$ στοιχεία, αυτό το ένα δεξί στοιχείο προσθέτει $k$ αντιστροφές με μία πράξη — όχι με $k$ ελέγχους. Εκεί ακριβώς εξαφανίζεται ο τετραγωνικός χρόνος.

Πάτα Επόμενο και δες το να συμβαίνει. Πρόσεξε ειδικά τις στιγμές που ανάβουν κόκκινα στοιχεία στο αριστερό μισό — εκεί μετριέται μια ολόκληρη παρτίδα αντιστροφών μονομιάς:

Ο αλγόριθμος

Πρώτα το βήμα συνδυασμού — η merge-and-count. Είναι η merge της mergesort με μία μόνο επιπλέον γραμμή.

Με τη merge-and-count έτοιμη, ο πλήρης αλγόριθμος είναι σχεδόν τετριμμένος — ακριβώς η mergesort, που τυχαίνει να μετράει και αντιστροφές στην πορεία.

Πολυπλοκότητα

Δύο αναδρομικές κλήσεις σε μισό μέγεθος, συν μια γραμμική συγχώνευση:

$T(n)=2T(n/2)+O(n)$

Αυτή είναι η ίδια ακριβώς αναδρομή με τη mergesort. Master Theorem με $a=2,b=2,d=1$: αφού ${\log }_{2}2=1=d$, είμαστε στην περίπτωση 2:

$T(n)=O(n\log n)$

Από $\Theta (n^2)$ σε $O(n\log n)$ — και ουσιαστικά δωρεάν, αφού ο αλγόριθμος δεν είναι παρά η mergesort με μία γραμμή παραπάνω.

Πρόβλημα 2 · Κυρίαρχο Χρώμα

Νιώσε: ποιος έχει την απόλυτη πλειοψηφία

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

Το ίδιο πρόβλημα, ντυμένο σαν σκακιέρα:

Παραδείγματα. Σε σκακιέρα $4\times 4$ (16 πλακίδια): 9 κόκκινα → το κόκκινο είναι κυρίαρχο, αφού $9>8$. Αλλά 8 κόκκινα → όχι κυρίαρχο, γιατί $8\ngtr 8$ — η ανισότητα είναι αυστηρή.

Η αφελής λύση: $O(n^4)$

Αφού δεν ξέρουμε ποια χρώματα να ψάξουμε, ας τα δοκιμάσουμε όλα. Για κάθε ένα από τα $n^2$ πλακίδια, πάρε το χρώμα του ως υποψήφιο και μέτρησε σε ολόκληρη τη σκακιέρα πόσες φορές εμφανίζεται — αυτό είναι ένα πέρασμα $O(n^2)$. Αν κάποιο ξεπεράσει το $n^2/2$, το βρήκαμε.

Σωστό, αλλά πολύ αργό. Για μια σκακιέρα $1000\times 1000$ μιλάμε για $10^{12}$ πράξεις.

Η λύση D&C: $O(n^2\log n)$

Διαίρει. Σπάσε τη σκακιέρα σε 4 υποσκακιέρες $\frac{n}{2}\times \frac{n}{2}$ — τα τέσσερα τεταρτημόρια.

Κυρίευσε. Κάλεσε αναδρομικά τον εαυτό σου σε καθεμία. Κάθε υποσκακιέρα γυρίζει πίσω έναν υποψήφιο: το δικό της κυρίαρχο χρώμα (ή «κανένα»).

Συνδύασε. Εδώ είναι όλη η ουσία — και στηρίζεται σε μία παρατήρηση:

Η παρατήρηση ακούγεται «προφανής» — δεν είναι. Λέει κάτι πολύ συγκεκριμένο: ένα χρώμα δεν μπορεί να έχει διάσπαρτη πλειοψηφία σε όλη τη σκακιέρα χωρίς να συγκεντρώνεται κάπου. Πριν την αποδείξουμε με μολύβι, παίξε με τους τέσσερις slider — καθένας ανεβάζει πόσες φορές εμφανίζεται το κόκκινο σε ένα τεταρτημόριο, κλειδωμένο στο «όχι κυρίαρχο εδώ» (δηλαδή το πολύ $\frac{1}{2}(\frac{n}{2}{)}^2$). Σπρώξε τους όλους στο μέγιστο και κοίτα το συνολικό μετρητή:

Τι μόλις είδες: όσο και να σπρώξεις τους τέσσερις slider, το σύνολο δεν φτάνει ποτέ το $n^2/2+1$. Επομένως αν το $c$ ήταν κυρίαρχο στη μεγάλη σκακιέρα (δηλαδή $>n^2/2$ εμφανίσεις), τότε δεν γίνεται να μην κυριαρχεί σε τουλάχιστον ένα τεταρτημόριο. Σε μαθηματικά:

— το αριστερό μέρος είναι το «πάνω όριο αν δεν κυριαρχεί πουθενά», το δεξί είναι το «κατώφλι κυριαρχίας»: ίσα. Άρα αν θέλεις αυστηρά $>n^2/2$, τουλάχιστον ένας slider πρέπει να σπάσει το όριο — δηλαδή να κυριαρχήσει σε κάποιο τεταρτημόριο. $■$

Η συνέπεια είναι καθοριστική: οι μόνοι πιθανοί υποψήφιοι για κυρίαρχο της μεγάλης σκακιέρας είναι τα (το πολύ) 4 χρώματα που γυρίζουν οι 4 αναδρομικές κλήσεις. Δεν χρειάζεται να σκεφτούμε κανένα άλλο.

Δες τον αλγόριθμο να τρέχει

Στη σκακιέρα παρακάτω, διάλεξε ένα από τα τρία σενάρια (ή πάτα «Ζωγράφισε» και φτιάξε δικό σου χρωματισμό), και πάτα Επόμενο για να σπάσει σε 4 τεταρτημόρια, να βγάλει αναδρομικά τους ≤ 4 υποψήφιους, να μετρήσει το καθένα σε ολόκληρη τη σκακιέρα, και να εκδώσει ετυμηγορία. Πρόσεξε ότι στο σενάριο «Σφιχτό 8 vs 8», 8 κόκκινα δεν είναι κυρίαρχα — η ανισότητα είναι αυστηρά μεγαλύτερο, όχι μεγαλύτερο-ή-ίσο:

Για κάθε ένα από αυτά τα (το πολύ) 4 χρώματα, μετράμε σε ολόκληρη τη σκακιέρα πόσες φορές εμφανίζεται — ένα πέρασμα $O(n^2)$ το καθένα. Τέσσερα περάσματα → $O(4n^2)=O(n^2)$ συνολικός χρόνος συνδυασμού.

Πολυπλοκότητα

Τέσσερις αναδρομικές κλήσεις σε σκακιέρες μισής πλευράς, συν ένα combine $O(n^2)$:

$T(n)=4T(n/2)+O(n^2)$

Master Theorem με $a=4,b=2,d=2$: αφού ${\log }_{2}4=2=d$, περίπτωση 2:

$T(n)=O(n^2\log n)$

Από $O(n^4)$ σε $O(n^2\log n)$ — δύο ολόκληρες τάξεις μεγέθους κέρδος.

Πρόβλημα 3 · Πολλαπλασιασμός Ακεραίων — Karatsuba

Νιώσε: πόσο κοστίζει ο πολλαπλασιασμός

Στο δημοτικό μάθαμε να πολλαπλασιάζουμε «με τη σειρά»: γράφεις τους δύο αριθμούς, πολλαπλασιάζεις ψηφίο με ψηφίο, προσθέτεις. Για μικρούς αριθμούς δεν μας απασχολεί το κόστος. Αλλά η κρυπτογραφία (π.χ. RSA) πολλαπλασιάζει αριθμούς με χιλιάδες ψηφία — αριθμούς που δεν χωράνε σε καμία int64 και αναπαρίστανται ως πίνακες ψηφίων. Εκεί το κόστος μετράει.

Ας μετρήσουμε. Με τον σχολικό τρόπο:

Το $O(n^2)$ του πολλαπλασιασμού είναι ο εχθρός μας: κάθε ψηφίο του ενός αριθμού πολλαπλασιάζεται με κάθε ψηφίο του άλλου — $n\times n$ μονοψήφιοι πολλαπλασιασμοί. Δες το στο $1357\cdot 2468$:

Η ερώτηση: μπορούμε να πολλαπλασιάσουμε πιο γρήγορα από $O(n^2)$;

Πρώτη προσπάθεια D&C — και γιατί αποτυγχάνει

Δοκιμάζουμε το σχήμα του L03. Σπάμε κάθε αριθμό στα μισά του ψηφία:

Γενικά, για $n$-ψήφιους $x$ και $y$:

$x=\alpha \cdot 10^{n/2}+\beta ,y=\gamma \cdot 10^{n/2}+\delta$

όπου $\alpha ,\beta ,\gamma ,\delta$ έχουν $n/2$ ψηφία το καθένα. Κάνοντας την πράξη:

Για να υπολογίσω το $x\cdot y$ χρειάζομαι τέσσερις πολλαπλασιασμούς μικρότερων αριθμών: $\alpha \gamma$, $\alpha \delta$, $\beta \gamma$, $\beta \delta$ — και μετά μερικές προσθέσεις και μετατοπίσεις, που κοστίζουν $O(n)$. Άρα:

$T(n)=4T(n/2)+O(n)$

Master Theorem με $a=4,b=2,d=1$: αφού ${\log }_{2}4=2>1=d$, είμαστε στην περίπτωση 3:

$T(n)=O(n^{{\log }_{2}4})=O(n^2)$

«Πληθαίνει πολύ γρήγορα» δεν είναι σχήμα λόγου — είναι αυτό που βλέπεις παρακάτω. Στα αριστερά, το δέντρο της αφελούς διάσπασης ($a=4$): κάθε κόμβος γεννά 4 παιδιά, οπότε σε κάθε επίπεδο τα υποπροβλήματα τετραπλασιάζονται. Στα δεξιά, το δέντρο που θα φτιάξουμε σε λίγο ($a=3$). Πάτα Παίξε και άσε τα δύο επίπεδα να γεμίσουν παράλληλα — στο τελευταίο επίπεδο, μεταξύ των δύο δέντρων ανοίγει ένας πραγματικά τεράστιος λόγος:

Με μία μόνο λιγότερη αναδρομική κλήση ανά κόμβο (4 → 3), το πλήθος φύλλων πέφτει από $4^{\log n}=n^2$ σε $3^{\log n}=n^{{\log }_{2}3}\approx n^{1.585}$ — και τα φύλλα κυβερνούν τη συνολική δουλειά. Όλο το ζητούμενο, λοιπόν, είναι: πώς γίνεται 3 αντί για 4;

Το έξυπνο τρικ του Karatsuba (1962)

Κοίτα ξανά τι θέλουμε από τον τύπο: τρεις ποσότητες — το $\alpha \gamma$, το $\beta \delta$, και το μεσαίο $\alpha \delta +\beta \gamma$. Αν καταφέρναμε να τις βρούμε με τρεις αντί για τέσσερις πολλαπλασιασμούς, η αναδρομή θα γινόταν $T(n)=3T(n/2)+O(n)$ — και, όπως θα δούμε, αυτό αλλάζει τα πάντα.

Το $\alpha \gamma$ και το $\beta \delta$ τα θέλουμε ούτως ή άλλως — αυτά είναι δύο από τους τρεις πολλαπλασιασμούς. Το πρόβλημα είναι το μεσαίο $\alpha \delta +\beta \gamma$, που μοιάζει να απαιτεί δύο ακόμη πολλαπλασιασμούς ($\alpha \delta$ και $\beta \gamma$ ξεχωριστά). Το κόλπο: ξεκίνα από το γινόμενο των αθροισμάτων και άσε την άλγεβρα να σου χαρίσει το μεσαίο.

Μέσα του κρύβεται ολόκληρο το μεσαίο μας. Αφαίρεσε τα δύο γινόμενα που ήδη έχουμε:

Άρα οι μόνοι τρεις πολλαπλασιασμοί που χρειαζόμαστε είναι:

και ο τελικός τύπος γίνεται:

Δες την ταυτότητα να γίνεται αριθμοί. Στο πάνω επίπεδο της αναδρομής για $1357\cdot 2468$, ο Karatsuba σπάει σε $\alpha =13,\beta =57,\gamma =24,\delta =68$, κάνει 3 πολλαπλασιασμούς ($z_1,z_2,z_3$), και τραβάει το μεσαίο ως απλή αφαίρεση. Πάτα Επόμενο και πρόσεξε τη στιγμή του ελέγχου ταυτότητας — όπου ο τύπος $\alpha \delta +\beta \gamma$ (αφελής, με 2 πολλαπλασιασμούς) γίνεται $z_3-z_1-z_2$ (μία αφαίρεση) και τα δύο νούμερα ταιριάζουν:

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

Πολυπλοκότητα

Τρεις αναδρομικές κλήσεις σε μισό μέγεθος, συν combine $O(n)$:

$T(n)=3T(n/2)+O(n)$

Master Theorem με $a=3,b=2,d=1$: είναι ${\log }_{2}3\approx 1.585>1=d$, άρα περίπτωση 3:

$T(n)=O(n^{{\log }_{2}3})=O(n^{1.585})$

Το ότι μειώσαμε τις αναδρομικές κλήσεις από 4 σε 3 δεν είναι μικρό «κούρεμα» — αλλάζει τον εκθέτη: από $n^2$ σε $n^{1.585}$. Για $n=10^4$ ψηφία, αυτό είναι περίπου $50\times$ λιγότερη δουλειά.

Τι ακολούθησε τον Karatsuba

Ο Karatsuba ήταν η πρώτη βελτίωση στο σχολικό $O(n^2)$ μετά από αιώνες — και άνοιξε ολόκληρο ερευνητικό πεδίο. Η αναζήτηση του γρηγορότερου πολλαπλασιασμού κράτησε δεκαετίες:

Το πρόβλημα έκλεισε το 2019: αποδείχθηκε ότι ο πολλαπλασιασμός γίνεται σε $O(n\log n)$ — που πιάνει το θεωρητικό κάτω φράγμα. Στην πράξη όμως, για ρεαλιστικά μεγέθη, ο Karatsuba παραμένει από τους πιο αποδοτικούς λόγω των χαμηλών σταθερών του — γι' αυτό χρησιμοποιείται σε βιβλιοθήκες όπως η GMP.

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

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

Τώρα οι τρεις κεντρικές ιδέες της διάλεξης — συμπλήρωσε τα κενά χωρίς να κοιτάς πίσω:

Μοτίβο σκέψης