L02 · Ασυμπτωτική Ανάλυση

Η ερώτηση που θέλουμε να απαντήσουμε

Πώς επηρεάζεται η απόδοση ενός αλγόριθμου όταν ο όγκος των δεδομένων που λαμβάνει αυξάνεται;

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

Γιατί δεν αρκούν οι σταθερές

Αυτό το παράδειγμα είναι ο λόγος που η ασυμπτωτική ανάλυση αγνοεί σταθερές. Αν η μία μέτρηση είναι $100n$ και η άλλη $n^2$, η σταθερά 100 είναι ασήμαντη μπροστά στη διαφορά «γραμμικό vs τετραγωνικό».

Οπτική σύγκριση συναρτήσεων

Πριν τους τυπικούς ορισμούς, ας νιώσουμε πώς συμπεριφέρονται οι κλασικές κλάσεις πολυπλοκότητας. Άναψε και σβήσε συναρτήσεις, και σύρε το εύρος του $n$ — δες πόσο γρήγορα ξεφεύγει η εκθετική και πόσο «πέφτει» η λογαριθμική:

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

Ο ορισμός — μια μηχανή με δύο κουμπιά

Πριν δούμε τα σύμβολα, ας στήσουμε τη μηχανική. Για να πούμε «T(n) ∈ O(f(n))» χρειαζόμαστε να βρούμε δύο πράγματα:

• μια σταθερά $c>0$ — το μέγεθος του «καπακιού» που βάζουμε πάνω από την $f$, δηλαδή η ευθεία $c\cdot f(n)$ που χρησιμοποιούμε σαν άνω φράγμα.
• ένα κατώφλι $n_0$ — από ποιο $n$ και μετά μας ενδιαφέρει· τα πρώτα $n<n_0$ τα αγνοούμε.

Αν υπάρχει ζευγάρι $(c,n_0)$ τέτοιο ώστε για ΚΑΘΕ $n\ge n_0$ να ισχύει $T(n)\le c\cdot f(n)$, λέμε ότι η T φράσσεται ασυμπτωτικά από την $c\cdot f$ — ή ισοδύναμα ότι T ∈ O(f). Μπορεί στις πρώτες τιμές η T να ξεπερνά την $c\cdot f$· δεν μας πειράζει, αρκεί από κάποιο σημείο και μετά να σταματάει να το κάνει.

Δοκίμασε τη μηχανή. Παρακάτω η ίδια $T(n)=3n^2-100n+6$ δοκιμάζεται σε τρεις διαφορετικές $f$. Σύρε το $c$ και δες πότε εμφανίζεται η πράσινη ζώνη (η περιοχή από το $n_0$ και πέρα όπου η μπλε καμπύλη μένει κάτω από την πορτοκαλί) — και πότε όχι:

Τι να προσέξεις σε κάθε tab:

• Σφιχτό φράγμα — $f=n^2$. Με $c=3$ η ανισότητα ισχύει αμέσως, από $n_0=1$. Αν ρίξεις το $c$ κάτω από 3, ξαφνικά δεν υπάρχει κανένα $n_0$ — όσο δεξιά κι αν σύρεις, η μπλε ξαναπερνά την πορτοκαλί.
• Χαλαρό φράγμα — $f=n^3$. Εδώ ΟΠΟΙΟΔΗΠΟΤΕ θετικό $c$ δουλεύει. Όσο μικρότερο το $c$, τόσο πιο δεξιά μετακινείται το $n_0$ — αλλά πάντα υπάρχει.
• Αδύνατο φράγμα — $f=n$. Όσο μεγάλο $c$ κι αν διαλέξεις, η τετραγωνική T τρώει τη γραμμική $c\cdot n$ τελικά. Δεν υπάρχει κανένα $n_0$. Αυτή είναι η εικόνα του «$T\notin O(n)$».

Τώρα ο τυπικός ορισμός — όλα τα παραπάνω σε συμπυκνωμένη μαθηματική γραφή. Έστω $f,T:\mathbb{N}\to {\mathbb{R}}^{+}$:

Δύο αντίστοιχοι ορισμοί για κάτω και ακριβές φράγμα:

Σε καθημερινή γλώσσα:

• $T\in O(f)$ — η T δεν αυξάνεται γρηγορότερα από την $f$. Άνω φράγμα.
• $T\in \Omega (f)$ — η T δεν αυξάνεται πιο αργά από την $f$. Κάτω φράγμα.
• $T\in \Theta (f)$ — η T αυξάνεται στον ίδιο ρυθμό με την $f$ (μέχρι σταθερά).

Οι τρεις περιπτώσεις, αλγεβρικά

Η εικόνα από το playground αξίζει και μια γρήγορη γραπτή απόδειξη — αυτή ακριβώς θα γράψεις στο εξεταστικό.

Η ιεραρχία πολυπλοκοτήτων — από σταθερό έως παραγοντικό

Οι κλάσεις που θα συναντάμε ξανά και ξανά, σε αυξανόμενο ρυθμό αύξησης:

Αυτή είναι ασυμπτωτική σειρά. Για μικρά $n$ τα νούμερα είναι κοντινά και η σειρά μπορεί να μην έχει «κλειδώσει» ακόμα. Δοκίμασε:

Δύο πράγματα ζητάμε από αυτό:

1. Σύρε το $n$ προς τα δεξιά. Από $n\approx 5$ και πέρα η σειρά κλειδώνει και μένει σταθερή για πάντα. Η μπάρα του $n!$ ρουφάει όλο τον χώρο γιατί ο ${\log }_2(n!)$ είναι τάξεις μεγέθους μεγαλύτερος από οποιαδήποτε πολυωνυμική έκφραση.
2. Σύρε το $n$ προς τα αριστερά. Στο $n=3$ ή $4$ θα δεις «παράδοξα»: το $n^2$ μπορεί να είναι μεγαλύτερο από το $2^n$, ή το $n!$ μικρότερο από το $n^2$. Η ασυμπτωτική σειρά δεν διεκδικεί τίποτα για τόσο μικρά $n$ — και ακριβώς για αυτό ο ορισμός έχει το $n_0$ μέσα του.

Wheat and chessboard — γιατί το εκθετικό είναι «καταστροφή»

Αυτό είναι το $2^n$ σε δράση. Αν ένας αλγόριθμος είναι $O(2^n)$, αρκεί να αυξήσεις το $n$ κατά 1 για να διπλασιαστεί ο χρόνος εκτέλεσης.

Η «πικρή πραγματικότητα»: γιατί δεν μας σώζουν οι ταχύτεροι υπολογιστές

Μια έντονη παρανόηση είναι ότι «οι αλγόριθμοι δεν έχουν τόση σημασία γιατί οι υπολογιστές γίνονται όλο και ταχύτεροι». Ας το ελέγξουμε με αριθμούς. Παρακάτω, κάθε γραμμή ξεκινά από ένα ρεαλιστικό «τώρα» (περίπου ό,τι χωράει σε 1 δευτερόλεπτο σε ένα μηχάνημα του 2025). Σύρε το $k$ από 1× ως 10⁹× και δες πόσο πιο μεγάλο πρόβλημα μπορείς να λύσεις στον ίδιο χρόνο:

Τι παρατηρείς:

• Για γραμμικό αλγόριθμο, 1000× μηχάνημα = 1000× μεγαλύτερη είσοδος. Πολλαπλασιαστικό κέρδος.
• Για $O(n^2)$, το κέρδος είναι $\sqrt{k}$· για $O(n^3)$, $\sqrt[3]{k}$. Όσο μεγαλύτερος ο εκθέτης, τόσο μικρότερο το κέρδος — αλλά παραμένει πολλαπλασιαστικό.
• Για εκθετικό $O(2^n)$ το κέρδος γίνεται αθροιστικό: $n_{\text{νεˊο}}=n+{\log }_{2}k$. 1000× μηχάνημα = +10 στοιχεία. Ένα δισεκατομμύριο φορές ταχύτερο μηχάνημα = +30 στοιχεία.
• Για $O(n!)$ ακόμη και ένα δισεκατομμύριο φορές πιο γρήγορο μηχάνημα ξεκολλάει την είσοδο κατά λίγες μόνο μονάδες.

Ιδιότητες των τάξεων μεγέθους

Έστω $f,f_1,f_2:\mathbb{N}\to {\mathbb{R}}^{+}$. Όλα τα παρακάτω αποδεικνύονται κατευθείαν από τον ορισμό:

1. $f(n)\in O(f(n))$ — κάθε συνάρτηση «κυριαρχείται από τον εαυτό της».
2. $f(n)\in \Theta (f(n))$ — και «είναι ίσης τάξης με τον εαυτό της».
3. $O(c\cdot f(n))=O(f(n))$ — οι σταθεροί συντελεστές απορροφώνται.
4. $O(f(n)+f(n))=O(f(n))$ — διπλασιάζοντας μια συνάρτηση δεν αλλάζει τάξη.
5. $O(f_1(n)+f_2(n))=O(\max \{f_1(n),f_2(n)\})$ — σε άθροισμα μετράει ο κυρίαρχος όρος.
6. $O(f_1(n))\cdot O(f_2(n))=O(f_1(n)\cdot f_2(n))$ — οι τάξεις πολλαπλασιάζονται.

Επίσης:

7. $f(n)\in O(g(n))⟺g(n)\in \Omega (f(n))$ — $O$ και $\Omega$ είναι δυϊκά.
8. $f(n)\in \Theta (g(n))⟺f(n)\in O(g(n))$ ΚΑΙ $g(n)\in O(f(n))$ — $\Theta$ θέλει και τις δύο κατευθύνσεις.
9. $f(n)\in \Theta (g(n))⟺g(n)\in \Theta (f(n))$ — το $\Theta$ είναι συμμετρικό.
10. $f(n)\in \Theta (g(n))$ και $g(n)\in \Theta (h(n))$ $\Rightarrow$ $f(n)\in \Theta (h(n))$ — μεταβατικότητα.

Είναι κάθε δύο συναρτήσεις ασυμπτωτικά συγκρίσιμες;

Όχι. Υπάρχουν συναρτήσεις που η μία δεν είναι ούτε $O$ ούτε $\Omega$ της άλλης. Ο κλασικός αντιπαραδείγμα στη βιβλιογραφία:

Σύρε τον δείκτη παρακάτω και δες πώς η g χορεύει πάνω και κάτω από τη γραμμική ευθεία f — κάθε φορά που το $\sin (n)$ ανεβαίνει η g ξεπερνά, κάθε φορά που πέφτει η g υπολείπεται:

Μοτίβο σκέψης: βρες το «καλύτερο» O

Πρακτικές ασκήσεις

Εναλλακτική προσέγγιση: οριακές σχέσεις

Η ανισότητα «$T(n)\le c\cdot f(n)$ από κάποιο $n_0$» είναι ακριβής αλλά δύσχρηστη — πρέπει να μαντέψεις $c$ και $n_0$. Πιο μηχανικά: παίρνεις το όριο του λόγου $f(n)/g(n)$ και διαβάζεις τη συμπεριφορά από αυτό. Έστω $f,g:\mathbb{N}\to {\mathbb{R}}^{+}$:

Διάλεξε ζευγάρι παρακάτω και δες το όριο να ξεδιπλώνεται. Ο πιο διδακτικός είναι ο $n^4/2^n$: για μικρά $n$ το πολυώνυμο φαίνεται να «κερδίζει» (ο λόγος ανεβαίνει!), αλλά από $n\approx 16$ το εκθετικό συντρίβει τον λόγο μέχρι το μηδέν. Αυτή είναι η εικόνα του «$f\in o(g)$»:

Οι μεσαίες περιπτώσεις (όριο 0 ή $\infty$) δίνουν τους «αυστηρά μικρότερα» συμβολισμούς:

• $\lim \to 0$ → γράφουμε $f(n)\in o(g(n))$ («μικρό-ο»). Διαβάζεται «η $f$ είναι αυστηρά μικρότερης τάξης από τη $g$».
• $\lim \to \infty$ → γράφουμε $f(n)\in \omega (g(n))$ («μικρό-ωμέγα»). Διαβάζεται «η $f$ είναι αυστηρά μεγαλύτερης τάξης».

Πιο τυπικά:

Η διαφορά «κάποιο $c$» vs «κάθε $c$» μοιάζει λεπτή στο χαρτί. Ο επόμενος πάγκος εργασίας σαρώνει 10–15 διαφορετικά $c$ και χρωματίζει καθένα πράσινο (η ανισότητα ισχύει) ή κόκκινο (δεν ισχύει):

Πρόσεξε στο tab «$g=n$ vs $f=2n$»: όσα $c\ge 0.5$ είναι πράσινα, όσα $c<0.5$ κόκκινα. Υπάρχει ζευγάρι που δουλεύει (το $c=1$ π.χ.), άρα $n\in O(2n)$. Αλλά δεν δουλεύουν όλα τα $c$ (αρκεί να ρίξεις το $c$ κάτω από $0.5$ για να σπάσει), άρα $n\notin o(2n)$. Στο δεύτερο tab («$g=n$ vs $f=n^2$») κάθε $c$ — ακόμη και $c=0,001$ — είναι πράσινο. Πλήρες «κάθε», άρα $n\in o(n^2)$.

Υπενθύμιση — Κανόνας του L'Hôpital

Πολλά από τα όρια που χρειαζόμαστε δίνουν απροσδιοριστία $\infty /\infty$ ή $0/0$. Σε αυτές τις περιπτώσεις:

Αν ${\lim }_{x\to \infty }f(x)=+\infty$ και ${\lim }_{x\to \infty }g(x)=+\infty$, και οι $f,g$ είναι παραγωγίσιμες, τότε:

${\lim }_{x\to \infty }\frac{f(x)}{g(x)}={\lim }_{x\to \infty }\frac{f^{\prime }(x)}{g^{\prime }(x)}$

Όταν η απροσδιοριστία επιμένει, εφαρμόζουμε ξανά. Το χρησιμοποιούμε αμέσως παρακάτω.

Δύο σημαντικά αποτελέσματα για τους ρυθμούς αύξησης

Στο LimitRatioPlot παραπάνω είδες τα δύο preset «$n^4/2^n$» και «$(\log n{)}^2/\sqrt{n}$» να καταρρέουν στο μηδέν. Αυτά ΔΕΝ είναι τυχαία παραδείγματα — είναι στιγμιότυπα δύο γενικών θεωρημάτων που χρησιμοποιούμε διαρκώς:

Εκθετικό κυριαρχεί πάνω σε πολυωνυμικό

Κάθε εκθετική συνάρτηση με βάση μεγαλύτερη του 1 αυξάνεται γρηγορότερα από κάθε πολυωνυμική συνάρτηση.

Τυπικά, για κάθε $a>1$ και $b\in \mathbb{R}$:

Πολυωνυμικό κυριαρχεί πάνω σε πολυλογαριθμικό

Μια συνάρτηση $f$ είναι πολυλογαριθμικά φραγμένη αν υπάρχει σταθερά $c$ με $f(n)\le {\log }^{c}n$.

Κάθε πολυωνυμική συνάρτηση αυξάνεται γρηγορότερα από κάθε πολυλογαριθμική.

Τυπικά, για $a>0,b>0$:

Η έννοια του βέλτιστου αλγορίθμου

Για ένα πρόβλημα $\Pi$ ζητάμε τον καλύτερο αλγόριθμο που το επιλύει — αυτόν με την καλύτερη πολυπλοκότητα.

Πιο τυπικά: αν κάθε αλγόριθμος που επιλύει το $\Pi$ έχει ασυμπτωτική πολυπλοκότητα $\Omega (f(n))$ — αυτό είναι κάτω φράγμα του προβλήματος — τότε ένας αλγόριθμος με πολυπλοκότητα $O(f(n))$ είναι (ασυμπτωτικά) βέλτιστος: ακουμπάει το θεωρητικό όριο.

Κλείσιμο: πολλαπλασιασμός τετραγωνικών πινάκων

Ένα εξαιρετικό παράδειγμα του γιατί η ασυμπτωτική ανάλυση είναι ζωντανό ερευνητικό αντικείμενο.

Το χάσμα $[\Omega (n^2),O(n^3)]$ είναι από τα πιο διάσημα ανοιχτά προβλήματα. Η ιστορία του:

Δεκαετίες μικρο-βελτιώσεων στον εκθέτη. Δεν ξέρουμε αν το $\Omega (n^2)$ είναι το πραγματικό κάτω φράγμα — αλλά πολλοί ερευνητές πιστεύουν ότι είναι και ότι κάποτε θα φτάσουμε εκεί.

Κλείδωσε τους ορισμούς

Πριν τα drills, μία κάρτα-μνήμης για να φύγεις από το κεφάλαιο με το σωστό «πακέτο» στο μυαλό:

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

Τώρα η ιεραρχία — βάλε τις κλάσεις στη σωστή σειρά:

begin algorithm
  arg ← -1
  for i ← 1 to n with step 1 do
    m ← i
    while m > 0 do
      m ← log(m)
    end while
    for j ← 1 to m with step 1 do
      arg ← i · i · j
    end for
  end algorithm

Algorithm 1:
  arg ← -1
  για i ← 1 έως 2n  (βήμα 1):
    για j ← i έως i²  (βήμα 1):
      arg ← CALC(j)

procedure CALC(w):
  res ← 0
  για i ← 1 έως √w  (βήμα 0.1):
    res ← res + log(i)
  return res

begin algorithm
  arg ← -1
  for i ← 1 to 2n with step 1 do
    for j ← i to i² with step 1 do
      arg ← CALC(j)
  end algorithm

procedure CALC(w)
  res ← 0
  for i ← 1 to w^0.5 with step 0.1 do
    res ← res + log(i)
  return res

Algorithm 1
  arg ← 1
  for i ← 1 to n with step 1 do
    for j ← 1 to i with step 1 do
      arg ← CALC(j)

procedure CALC(m)
  i ← 1;  s ← 1
  while s ≤ m do
    i ← i + 1
    s ← s + i
  return s

Algorithm 2
  arg ← 0
  for i ← 1 to n with step 1 do
    for j ← 1 to n with step (2·j) do
      arg ← CALC(j)

procedure CALC(m)
  s ← m
  while s ≤ (2·m) do
    s ← s + 1
  return s