ΟΜΙΛΗΤΗΣ: Εντάξει, αυτό είναι CS50. Αυτό είναι το τέλος των τριών εβδομάδων, και εάν που δεν έχουν επωφεληθεί ήδη, γνωρίζουν ότι θα υπάρξει γεύμα αυτή την Παρασκευή ως συνήθως, όπου μπορείτε να απολαύσετε καλή κουβέντα και το φαγητό στο Fire and Ice με μερικά από τα CS50 του το προσωπικό και τους συμμαθητές. Επικεφαλής σε αυτή τη διεύθυνση URL εδώ. 

Τώρα μπορείτε να ανακαλέσετε ή να σας μπορεί σύντομα να εξοικειωθούν με, αυτά τα πράγματα εδώ, η οποία δίνονται στο τέλος του εξαμήνου για πολλές κατηγορίες. Λεγόμενη εξετάσεις μπλε βιβλία, στο οποίο γράψετε τις απαντήσεις σας σε εξετάσεις. Τώρα έχω εδώ 26, όπως μπλε βιβλία, για καθένα από αυτά είναι γραμμένο ένα όνομα, A έως το Z. Και Πράγματι, τα ονόματα είναι τόσο απλό, A μέσω Z. Και ένα από οι στόχοι στο χέρι σήμερα πρόκειται να είναι η συνέχιση της ξεκινήσαμε τη Δευτέρα, η οποία δεν είναι τόσα πολλά κοιτάζοντας τον κωδικό, αλλά πραγματικά κοιτάζοντας τις ιδέες και την επίλυση προβλημάτων. Ένας από τους στόχους και υποσχέσεις του μαθήματος είναι να σας διδάξει να σκέφτονται περισσότερο προσεκτικά, πιο μεθοδικά, και να λύσει τα προβλήματα πιο αποτελεσματικά. Και πράγματι, μπορούμε να το κάνουμε αυτό πραγματικά χωρίς καν να αγγίξει ούτε μια γραμμή κώδικα. Έτσι έχω ένα ζευγάρι των ελεφάντων εδώ σήμερα, πορτοκαλί και μπλε, αν θα μπορούσαμε να πάρουμε έναν εθελοντή, ίσως από το πιο πίσω από ό, τι συνήθως. Πόσο περίπου εκεί, έλα κάτω. Ο στόχος της οποίας πρόκειται να είναι σε βοηθήσει συν τη διαχείριση αυτού του εξετάσεις εδώ. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Μαίρη Μπεθ. ΟΜΙΛΗΤΗΣ: Μαίρη Μπεθ, έλα επάνω. Επιτρέψτε μου να πάρει το μικρόφωνο εδώ για εσάς. Χαίρω πολύ. 

ΚΟΙΝΟ: Χαίρω πολύ. ΟΜΙΛΗΤΗΣ: Εντάξει, έτσι έχω Εδώ μπλε βιβλία Α έως το Ω, και Πάω να προσποιηθώ ότι Έχω ένας από τους μαθητές, και έρχονται σε κάπως τυχαία στο τέλος του τρεις ώρες μπλοκ εξετάσεις, έτσι ώστε όπου και αν καταλήξουν σε κάποια ημι-τυχαία σειρά, όπως αυτό. Τώρα η δουλειά σας σε μια στιγμή θα να είναι-- αυτό είναι στην πραγματικότητα το πώς παίρνουν γύρισε σε κατά το τέλος της η τάξη, το πιο πιθανό. Η δουλειά σου τώρα πρόκειται να είναι, αρκετά Με απλά λόγια, για να ταξινομήσετε αυτά τα μπλε βιβλία για εμάς από το Α έως το Z. 

ΚΟΙΝΟ: Ω, αυτό είναι πρόκειται να πάρει για πάντα. 

ΟΜΙΛΗΤΗΣ: Και εμείς θα παρακολουθήσουν όπως μπορείτε να το κάνετε αυτό, δεν υπάρχει πίεση. ΚΟΙΝΟ: Όχι, δεν υπάρχει πίεση ή οτιδήποτε άλλο. 

ΟΜΙΛΗΤΗΣ: Και για τη διασκέδαση, ας βάλουμε ένα χρονόμετρο. 

ΚΟΙΝΟ: So much fun, τόσο πολλή διασκέδαση. 

ΟΜΙΛΗΤΗΣ: Μπορώ να κρατήσει το μικρόφωνο για σας. Εντάξει, έχουμε μόλις διπλασίασε την ταχύτητα μας. Έτσι, εν τω μεταξύ, επιτρέψτε μου να δημιουργήσει ό, τι είναι πρόκειται να είναι η ερώτηση για Μαίρη Μπεθ είναι τι κάνει αυτή, πώς είναι Πάει για την επίλυση αυτό; Και στην πραγματικότητα, δεν θα μπορούσε να έχει ποτέ σκεφτεί κάτι τόσο απλό, όπως όταν επιλέγετε μέχρι 26 βιβλία σαν αυτό, τα οποία έχουν μια φυσική παραγγελία για να τους. Ποια είναι η διαδικασία ότι μπορείτε πραγματικά να χρησιμοποιήσετε; Είναι μάλλον τυχαία ακριβώς να πάρει το πρώτο που βλέπετε και βάζοντας στη θέση του; Μήπως πρώτα να μετακινήσετε τα χέρια σας γύρω από ψάχνει για μια συνέχεια ψάχνει για B; Μην παίρνετε μια ματιά σε ένα ζεύγος τους δίπλα-δίπλα και απλώς να πω, περιμένετε ένα λεπτό, αυτό Δεν είναι σωστό, και στη συνέχεια να ανταλλάξουν τη σειρά; Είδαμε ήδη τη Δευτέρα ότι υπάρχει ένας αριθμός τρόπων στο οποίο μπορούμε να το κάνουμε αυτό, και Πράγματι, καθώς πλησιάζει το τέλος εδώ, Θα ήθελα να λάβει γνώση ίσως από ό, τι Μαίρη Μπεθ κάνει. Έχουμε μερικά σωρούς φαίνεται, ένα μεγαλύτερο από ένα, τρία μικρότερα. 

ΚΟΙΝΟ: Είμαι τους παραγγελία όταν βρω δύο γράμματα Ξέρω ότι είναι μαζί σε μια σειρά, Τους έβαλα μαζί έτσι ώστε να μπορώ να μην κάνω πρέπει να ανησυχείτε για τη διατήρηση κομμάτι μιας ολόκληρης σειράς βιβλίων. Είναι απλά, ω, Α είναι η πρώτη, Έχω αυτό το stack εδώ. ΟΜΙΛΗΤΗΣ: Έτσι, σχεδόν σαν ένα τα κομμάτια του παζλ, ότι έχει το σωστό σχήμα για να ταιριάζουν με το άλλο. ΚΟΙΝΟ: Λίγο πολύ, ναι. ΟΜΙΛΗΤΗΣ: Εντάξει, εξαιρετική. Και τώρα κάθε μία από αυτές σωρούς είναι προφανώς ταξινομούνται; 

ΚΟΙΝΟ: Ναι. 

ΟΜΙΛΗΤΗΣ: Εντάξει, A έως Z. Όλα δεξιά, συγχαρητήρια, τα κατάφερες. Έχετε την επιλογή σας. Blue; Εντάξει, σας ευχαριστώ για αυτό. Έτσι, Μαίρη Μπεθ είχε προτείνει ποια είναι η προσέγγισή της ήταν, αλλά αυτό είναι μια άλλη προσέγγιση το πώς θα θα μπορούσε να πάει για διαλογή αυτά τα πράγματα; Τι θα κάνατε; Το ρεκόρ για να νικήσει θα ήταν ένα λεπτό και 50 δευτερόλεπτα ή έτσι, συν αυτά που ξέχασα να μετρήσει. Τι θα κάνατε; Ναι; ΚΟΙΝΟ: Πάρτε τη στοίβα. Ξεκινήστε από την αρχή. Ελέγξτε τα χαρτιά σας. Και αν η κορυφή ενός είναι υψηλότερη ό, τι, ίσως, είναι, το κάτω μέρος είναι ένα υψηλότερη, τότε ανάβουν. 

ΟΜΙΛΗΤΗΣ: Εντάξει, έτσι ξεκινώντας στην κορυφή και τον πυθμένα, και, στη συνέχεια, τον τρόπο εργασίας σας προς τα μέσα έτσι, την εναλλαγή τους; Εντάξει, έτσι είναι λίγο παρόμοια στο πνεύμα με bubble sort, αλλά η επιλογή των άκρων Δεν τα γειτονικά ζεύγη. Αλλά η μικρή του είναι ότι δεν υπάρχει σίγουρα ένα σωρό διαφορετικούς τρόπους θα μπορούσαμε να το κάνουμε αυτό, και Ειλικρινά, νομίζω ότι εσύ το είδος της υιοθέτησε ένα ζευγάρι προσεγγίσεις, σωστά; Κάνατε το είδος των τεσσάρων ταξινομημένων σωρούς, και στη συνέχεια να συγχωνευθεί μαζί αποτελεσματικά. Και αυτό είναι, τολμούσα να πω, ένα άλλο τεχνική εντελώς. Δεν το αντιμετωπίζουν ως ένα μεγάλο σωρό, θα διαιρεθεί το πρόβλημα σε τέσσερα τετράκλινα, αν θέλετε, και στη συνέχεια με κάποιο τρόπο συγχωνεύθηκε τους στο τέλος. 

Έτσι, ας αναλογιστούμε, τελικά, πώς αλλιώς θα μπορούσαμε να το κάνουμε αυτό. Εμείς τυποποίησε την έννοια του bubble sort τελευταία φορά, και bubble sort ανάκληση ήταν μια αλγόριθμο που οπτικοποιείται με οκτώ από τους συμμαθητές σας μέχρι εδώ, φαινομενικά τυχαία κατατάσσονται στην πρώτη. Και στη συνέχεια αποφάσισε κατά ζεύγη, εάν δύο στοιχεία που είναι εκτός λειτουργίας, απλά να τους swap. Έτσι, τέσσερις και δύο είναι προφανώς εκτός λειτουργίας, έτσι ώστε αυτές οι δύο συμμαθητές θέσεις μεταγωγής. Και τότε θα επαναληφθεί με τέσσερα και έξι, στη συνέχεια, έξι και οκτώ, σε κάθε επανάληψη, κινείται προς τα δεξιά. 

Έτσι, δίνεται οκτώ άτομα, πόσα ζεύγη συγκρίσεις έκανα, ενώ το περπάτημα από αριστερά προς τα δεξιά σε μία τέτοια επανάληψη; Πόσες συγκρίσεις; Επτά, σωστά; Διότι, αν υπάρχουν οκτώ ανθρώπους, αλλά έχετε το ζεύγος τους και να σας κρατήσει κινείται ένα hop προς τα δεξιά, δεν πρόκειται να έχει οκτώ συγκρίσεις, επειδή δεν μπορείτε να συγκρίνετε ένα στοιχείο ενάντια στο ίδιο, ή θα ήταν απλά είναι άχρηστη, έτσι ώστε να έχουν επτά. Ή πιο γενικά, αν έχουμε n άτομα, εμείς κάνει n μείον 1 συγκρίσεις με bubble sort. 

Ας εξετάσουμε τώρα το πόσο καλή ή κακή bubble sort πραγματικά ήταν, και προσπαθήστε για να δώσουμε στον εαυτό μας λεξιλόγιο με η οποία σε αλγόριθμους κριτική, όπως αυτή, και σύντομα τη δική μας. Έτσι, το πρώτο πέρασμα μέσω bubble sort, η πρώτη φορά Περπάτησα από αριστερά προς τα δεξιά κατά μήκος της στάδιο, με n μείον 1 συγκρίσεις πήρε. Και αυτό πρόκειται να μου μονάδα μέτρησης, σωστά; Ήμουν είδος μιλάμε και περίπατο, κάπως γρήγορα, κάπως αργά, έτσι μετρώντας τον αριθμό μου από δευτερόλεπτα δεν είναι ιδιαίτερα εύγλωττο, αλλά μετρώντας τον αριθμό των επιχειρήσεις που έκανα τη Δευτέρα, συγκρίνοντας τα δύο άτομα, που αισθάνεται σαν ένα ωραίο μονάδα μέτρησης. 

Έτσι n μείον 1 βήματα την πρώτη φορά, αλλά τότε τι συνέβη μετά από αυτό; Ποιο είναι το ένα ανάποδα από ένα πέρασμα μέσω μιας κατά τα άλλα μη ταξινομημένα λίστα; Τι μπορείτε να μου πείτε σχετικά με το στοιχείο ο οποίος ήταν σε όλη τη διαδρομή πάνω από εκεί; Ναι; Αυτό ήταν το μεγαλύτερο στοιχείο, σωστά; Αριθμός οκτώ, ακόμη κι αν ξεκίνησε εδώ, κάθε φορά που σε σύγκριση με την κατά ένας γείτονας, συνέχισε αναβλύζει προς τα δεξιά πλευρά της λίστας. Και πράγματι, αυτό είναι όπου ο αλγόριθμος παίρνει το όνομά του. 

Τώρα, με αυτή τη λογική, πόσες συγκρίσεις πρέπει να κάνω για δεύτερη φορά Κάνω αυτό το πέρασμα από τα αριστερά προς τα δεξιά; n μείον 2, σωστά; Θα ήταν απλώς να χάνω τον χρόνο μου, αν μου κρατήσει σύγκριση οκτώ εναντίον κάποιου αλλιώς γιατί γνωρίζουμε ήδη ήταν στο σωστό μέρος. Έτσι, αυτό είναι ένα κομμάτι από ένα βελτιστοποίησης, έτσι ώστε το επόμενο πέρασμα πρόκειται να είναι συν η πλην δύο στάδια, όπου n είναι ο αριθμός των ανθρώπων. Τώρα μπορείτε να το είδος της προεκτείνουν, ακόμη αν δεν είστε ένας επιστήμονας υπολογιστών, πώς τελειώνει. Στο τέλος αυτού του αλγορίθμου, πιθανώς έχετε μόνο μία σύγκριση αριστερά. Θα πρέπει να καθορίσει το είδος της η ξεκινώντας από τη λίστα στην περίπτωση δύο και ένα είναι εκτός λειτουργίας και θα πρέπει να είναι ένα και δύο, έτσι ώστε αυτό να κατεβαίνουν από την συν 1 τελικό σύγκριση. 

Τώρα η τελεία, τελεία, τελεία είδος των κυμάτων είναι τα χέρια σε μερικά από τα πιο ζουμερό λεπτομέρειες, αλλά ας πάμε μπροστά και να απλοποιηθεί. Αν θυμάστε από την υψηλή σχολείο, ειλικρινά, πολλοί από εσάς είχαν βιβλία μαθηματικών που είχε ένα μικρό σκονάκι στο μπροστινό κάλυμμα ή ο πίσω κάλυμμα που σας έδειξα αθροίσεις ποια σειρά, όπως Αυτό τελικά προστίθεται μέχρι. Στη γενική περίπτωση, εάν έχετε μια μεταβλητή, όπως n, και μάλιστα αυτό, αν κοίταξε σας παλιό σχολείο μαθηματικά βιβλίο, θα δείτε ότι αυτό στην πραγματικότητα προσθέτει μέχρι και το ποσό αυτό εδώ, n φορές n μείον 1 όλα διαιρείται δια 2. Έτσι, για τώρα επιτρέψτε μου να ορίζουν Αυτό είναι αλήθεια, έτσι για ένα άλμα της πίστης, αυτό είναι που συνοψίζει αυτό μέχρι, και θα μπορούσαμε να αποδεικνύουν ότι σε μια πιο γενική περίπτωση. Αλλά τώρα ας επεκτείνουν αυτό. Έτσι, ας πολλαπλασιάσουμε αυτό έξω, έτσι ώστε να είναι n τετράγωνο, μείον n, όλα διαιρείται δια 2. Αυτό είναι πραγματικά n τετράγωνο, διαιρείται δια 2, μείον n πάνω από 2, έτσι ώστε να είναι όλα ωραία και ενδιαφέρουσα. Αλλά τι θα συμβεί αν plug-in αξίας; Ας υποθέσουμε ότι δεν είχα οκτώ ανθρώπους, αλλά να πω ένα εκατομμύριο. Και ένα εκατομμύριο μόνο και μόνο επειδή Είναι ένα αρκετά μεγάλο αριθμό, ας συνδέσετε αυτό και να δούμε τι θα συμβεί. Έτσι, εάν συνδέσετε ένα εκατομμύριο σε αυτό το τύπο Πάω να πάρει ένα εκατομμύριο τετράγωνο, διαιρείται δια 2, μείον εκατομμύρια, διαιρούμενο με το 2. Τώρα τι που πρόκειται να ισούται; Έτσι, τα 500 δισεκατομμύρια, μείον 500.000. Και αν μπορώ πραγματικά να κάνουμε ότι τα μαθηματικά, αυτό σημαίνει ότι ότι η διαλογή ένα εκατομμύριο οι άνθρωποι με το είδος φούσκα θα μπορούσε να μου πάρει 499999500000 βήματα ή συγκρίσεις στο τέλος, είμαστε απλά παρέκταση. 

Αυτό αισθάνεται αρκετά αργή, αλλά ειλικρινά μετρώντας μία συγκεκριμένη είσοδο όπως αυτό, δεν είναι όλα αυτά που λέει. Αλλά πράγματι δεν δείχνουν ότι n γίνεται όλο και μεγαλύτερο, αυτός ο αλγόριθμος το είδος του αισθάνεται χειρότερα και χειρότερα, ή πραγματικά αρχίζουν να αισθάνονται τον πόνο του ότι ύψωση σε δύναμη, ώστε ν τετράγωνο, η οποία προσθέτει επάνω αρκετά γρήγορα. Και αυτή η λεπτομέρεια δεν είναι χάνεται στους ανθρώπους, στην πραγματικότητα, πριν από μερικά χρόνια ένα ορισμένο γερουσιαστής ο οποίος ήταν εκστρατεία, κάθισε για μια συνέντευξη με τον Eric της Google Schmidt, Διευθύνων Σύμβουλος εκείνη την εποχή, και είχε προσβληθεί με μια ερώτηση σαν ερευνούμε σήμερα. Ας ρίξουμε μια ματιά. 

[VIDEO PLAYBACK] 

-Senator, Είστε εδώ στο Google, και μου αρέσει να σκεφτούμε την προεδρία ως μια συνέντευξη για δουλειά. Τώρα, είναι δύσκολο να πάρει μια δουλειά ως πρόεδρος, και θα πάμε μέσα από τις ακαμψίες τώρα. Είναι επίσης δύσκολο να βρουν μια θέση εργασίας στην Google. Έχουμε ερωτήματα, και εμείς ζητήσει από τους υποψήφιους ερωτήσεις μας, και αυτό είναι ένα από Larry Schwimmer. Τι-- εσείς ότι είμαι αστειεύεστε, είναι ακριβώς εδώ. Ποια είναι η πιο αποτελεσματικός τρόπος για να ταξινομήσετε ένα εκατομμύριο ακεραίων 32-bit; 

-Well-- 

-Συγγνώμη, Maybe-- 

Όχι, όχι, όχι. Νομίζω ότι το είδος φούσκα θα ήταν ο λάθος τρόπος να πάει. 

Έλα, που τον είπε αυτό; Δεν είδα τον υπολογιστή επιστήμης στο παρασκήνιο σας. 

-We've Πήρε κατασκόπους μας εκεί. 

-εντάξει, Ας ζητήσει μια διαφορετική Συνέντευξη ερώτημα. 

[ΤΕΛΟΣ VIDEO PLAYBACK] 

ΟΜΙΛΗΤΗΣ: Οπότε μιλάμε για συγκεκριμένους αριθμούς όμως, δεν πρόκειται να είναι όλα αυτά χρήσιμα. Δεν είναι ένα μάθημα ζωής που φούσκα ταξινόμησης, δίνεται ένα εκατομμύριο εισόδους, μπορεί να πάρει όσο 500 δισεκατομμύρια βήματα. Δεν μπορεί πραγματικά να γενικεύσουμε πολύ αποτελεσματικά από ότι και να κάνει καλές αποφάσεις σχεδιασμού κατά τη σύνταξη των προγραμμάτων. Ας επικεντρωθούμε όμως στο πώς θα μπορούσε να απλοποιήσει αυτό το αποτέλεσμα. 

Έτσι έχω επισημαίνονται με κίτρινο χρώμα εδώ το αποτέλεσμα του n τετράγωνο διαιρείται με 2, έτσι, ένα εκατομμύριο τετράγωνο διαιρείται με 2, και έπειτα Έχω υπογράμμισε τι η τελική απάντηση ήταν τη στιγμή που θα αφαιρεθεί από n διαιρείται δια 2. Και ο ισχυρισμός Πάω να κάνει τώρα είναι, ποιος στο διάολο νοιάζεται αν αφαιρούμε λίγο παλιό n πάνω από 2, όταν η πρώτη μέρος αυτού του τύπου είναι πολύ μεγαλύτερο; Δεσπόζει το άλλο διάρκειας, n τετράγωνο χωρίζεται από 2 είναι πολύ μεγαλύτερο, με σαφήνεια, όπως n παίρνει μεγάλες σαν ένα εκατομμύριο, ότι είναι πραγματικά υπάρχει μια μεγάλη διαφορά στο το τέλος της ημέρας μεταξύ 500 δισεκατομμύρια και 499 999 500 000; Όχι πραγματικά. Και έτσι αυτό που πρόκειται να κάνουμε ως επιστήμονες υπολογιστών είναι αγνοεί τις χαμηλότερες όρους τάξης και να λάβει κάτι τέτοιο και πραγματικά απλά για να απλουστευθεί η όρος που πρόκειται να έχει σημασία. Τα μεγαλύτερα σύνολα δεδομένων μας πάρει, το μεγαλύτερο βάσεις δεδομένων μας πάρει, οι περισσότερες ιστοσελίδες πρέπει να ψάξουμε, το πιο φίλους έχεις στο Facebook. 

Καθώς το n μεγαλώνει, είμαστε πραγματικά πρόκειται να νοιάζονται για το μεγαλύτερο όρος σε κάθε τέτοια ανάλυση απόδοση των αλγορίθμων μας. Και Πάω να πω, ξέρετε τι, φούσκα είδος είναι της τάξεως των μεγάλων O, της τάξεως των Ν τετράγωνο. Δεν είναι ακριβώς n τετράγωνο, όπως έχουμε δει, αλλά ποιος νοιάζεται πραγματικά για τα μικρότερα αυτά όρων, και ειλικρινά, που πραγματικά νοιάζεται αν διαιρέσουμε με 2; Αυτό είναι απλά ένα σταθερό παράγοντα. Και είναι 500 δισεκατομμύρια, έναντι 250 δισεκατομμύρια πραγματικά ότι οι μεγάλες από μια συμφωνία; Θα μπορούσα απλά περιμένετε από ένα χρόνο, αφήστε το laptop μου κυριολεκτικά πάρει δύο φορές πιο γρήγορα σε hardware, και αυτό το είδος της διαφοράς Απλά πηγαίνει μακριά φυσικά την πάροδο του χρόνου. 

Αυτό που μας νοιάζει είναι η έκφραση, το τμήμα της έκφρασης, που πρόκειται να ποικίλουν ως συμβολή μας γίνεται όλο και μεγαλύτερο. Και πράγματι, στον πραγματικό κόσμο, αυτό είναι που συμβαίνει όλο και περισσότερο είναι οι είσοδοι για τα προβλήματά μας και αλγόριθμοι παίρνουν μεγαλύτερα. Τόσο μεγάλη O πρόκειται να είναι ο συμβολισμός, το ασυμπτωτικό συμβολισμό, ότι εμείς απλά χρησιμοποιήσετε ως επιστήμονες ηλεκτρονικών υπολογιστών για να περιγράψει η απόδοση, ή ο χρόνος τρέχει, ενός αλγορίθμου. Έτσι ώστε να μπορούμε να συγκρίνουμε αλγορίθμους σε διαφορετικούς υπολογιστές γραπτή από διαφορετικούς ανθρώπους, με τη χρήση μερικά βασικά παρόμοια μετρικό όπως τον αριθμό των συγκρίσεων είστε αποφάσεων, ή ίσως και τον αριθμό των swaps έχετε κάνει. 

Αυτό που δεν πρόκειται να καταμέτρηση είναι η ποσότητα του χρόνου που περνά στο ρολόι στον τοίχο τυπικά. Αυτό που δεν πρόκειται να ανησυχείτε περίπου είναι πόση μνήμη που χρησιμοποιείτε σήμερα σε τουλάχιστον, αν αυτό είναι άλλος πόρος που μπορεί να μετρηθεί. Εμείς πάμε για να προσπαθήσουμε να βασίζουν τις αναλύσεις μας σε μόνο τις βασικές λειτουργίες, εκείνοι, ειλικρινά, που μπορείτε να δείτε πιο οπτικά. Έτσι, με κάτι σαν μεγάλη O από n τετράγωνο, εγώ ισχυρίζομαι ότι από O n τετράγωνο είναι ένα άνω όριο για τη λεγόμενη χρόνο της bubble sort τρέξιμο. Με άλλα λόγια, αν ήθελε να ισχυρίζονται ότι δεν υπάρχει αυτό το ανώτατο όριο για το πόσες στάδια ένας αλγόριθμος θα μπορούσε να λάβει, πρόκειται να είναι το μεγάλο O των n τετράγωνο σε αυτή την περίπτωση, ένα άνω όριο. 

Τι θα συμβεί αν, αντί να αλλάξει η η ιστορία να μην είναι για το bubble sort, αλλά για αυτό το άνω φράγμα. Μπορείτε να σκεφτείτε έναν αλγόριθμο ότι έχουμε εξετάσει ήδη των οποίων άνω όριο, κατ 'ανώτατο όριο μέτρηση του χρόνου ή επιχειρήσεις, θα είπε να οριοθετείται από n, μια γραμμική συνάρτηση, δεν είναι μια τετραγωνική ένα καμπύλο; Τι είναι ένας αλγόριθμος που παίρνει πάντα περισσότερο από ό, τι σαν βήματα n, ή 2n βήματα ή τα βήματα 3η; Ναι; 

ΚΟΙΝΟ: Η εξεύρεση της μεγαλύτερο αριθμό σε μια λίστα; 

ΟΜΙΛΗΤΗΣ: Perfect, βρίσκοντας ο μεγαλύτερος αριθμός σε έναν κατάλογο. Αν είμαι δοθεί μια λίστα άνθρωποι, για παράδειγμα, καθένα από τα οποία κρατάει έναν αριθμό, τι είναι ο μέγιστος αριθμός των βημάτων που πρέπει να με πάρει, ένα αρκετά έξυπνο άτομο, για να βρείτε το μεγαλύτερο πρόσωπο στον εν λόγω κατάλογο; n, σωστά; Επειδή στη χειρότερη περίπτωση, όπου ίσως η μεγαλύτερη αξία είναι; Δεξιά, όλος ο τρόπος στο τέλος. Έτσι, στη χειρότερη περίπτωση άνω όριο, θα μπορούσα πρέπει να πάει όλος ο τρόπος εδώ και να είναι όπως, Ω, εδώ είναι ο αριθμός οκτώ, ή ό, τι η τιμή είναι. Τώρα αυτό θα ήταν απλά ανόητο αν συνεχίζαμε, σωστά; Ψάχνετε για όλο και περισσότερα στοιχεία εάν η τελευταία από αυτές είναι πάνω εκεί; Έτσι, σίγουρα, n είναι ένα άνω όριο. Δεν πρέπει να πάρετε περισσότερα βήματα από αυτό. 

Έτσι, ό, τι και αν αντ 'αυτού πρότεινε ότι υπάρχουν αλγόριθμοι σε αυτόν τον κόσμο ότι έχουν ένα χρόνο λειτουργίας που είναι οριοθετείται από μεγάλη O του log n, log n; Πού έχουμε ξαναδεί κάτι τέτοιο; Ναι; 

ΚΟΙΝΟ: Στο πρόβλημα τηλεφωνικό κατάλογο; ΟΜΙΛΗΤΗΣ: Όπως και το πρόβλημα του τηλεφωνικού καταλόγου. Ποιο ήταν το μέτρο του πόσο πολύ χρόνο ή πόσα δάκρυα είναι πήρε να βρω κάποιον σαν Mike Smith στον τηλεφωνικό κατάλογο; Εμείς ισχυρίστηκε ότι ήταν log n, και ακόμα και αν δεν είναι εξοικειωμένοι ή είναι λίγο θολό, τι ένα λογάριθμος ή εκφραστής ήταν, απλά να θυμάστε ότι log n αναφέρεται γενικά στην διαδικασία, στην περίπτωση αυτή, από τη διαίρεση κάτι το ήμισυ και πάλι, και πάλι, και ξανά, και ξανά, έτσι ώστε να γίνεται όλο και πιο μικρά, όπως το κάνετε αυτό. 

Έτσι log ν αναφέρεται, βέβαια, για παράδειγμα τηλεφωνικό κατάλογο, σε δυαδική αναζήτηση στη θεωρία, όταν εμείς είχε τις εικονικές πόρτες της στο διοικητικό συμβούλιο, ή όταν ο Sean ήταν ψάχνουν για κάτι. Αν είχε χρησιμοποιηθεί δυαδική αναζήτηση, log n θα είναι το ανώτατο όριο για το πόσο χρόνο που χρειάζεται. Αλλά αυτοί οι αλγόριθμοι που έτρεξε σε log n υποτίθεται τι κλειδί λεπτομέρεια; Αυτός ο κατάλογος ήταν ταξινομημένο, σωστά; Αλγόριθμο σας είναι λάθος, αν εισόδου σας δεν είναι ταξινομημένο, και όμως είστε με τη χρήση κάτι σαν δυαδική αναζήτηση επειδή μπορεί να πηδήσει ακριβώς πάνω από το στοιχείο χωρίς να συνειδητοποιούν ότι είναι πράγματι εκεί. 

Τώρα τι μπορεί να σημαίνει αυτό, μεγάλη O ενός; Αυτό δεν σημαίνει ότι ο αλγόριθμος σας διαρκεί ένα και μόνο ένα βήμα, αυτό σημαίνει απλώς παίρνει μια σταθερό αριθμό βημάτων. Ίσως είναι 1, ίσως είναι 10, ίσως είναι 1.000, αλλά είναι ανεξάρτητο από το μέγεθος του προβλήματος. Δεν έχει σημασία πόσο μεγάλο είναι n, ένα σταθερό αλγόριθμο λαμβάνει πάντοτε τον ίδιο αριθμό βημάτων. Λοιπόν, τι θα μπορούσε να είναι ένας αλγόριθμος έχουμε μιλήσει ή απλά διαισθητικά ότι έρχεται σε σας ότι τρέχει πάντα στο λεγόμενο σταθερό χρόνο; Ναι; 

ΚΟΙΝΟ: Προσθέστε δύο αριθμούς. ΟΜΙΛΗΤΗΣ: Προσθέστε δύο αριθμούς, 2 συν 2 ισούται με 4, γίνεται. Έτσι, ότι θα μπορούσε να λειτουργήσει, τι άλλο; Τι θα λέγατε για πιο πραγματικό κόσμο, ναι; 

ΚΟΙΝΟ: Η εξεύρεση της το πρώτο πράγμα που σε μια λίστα. ΟΜΙΛΗΤΗΣ: Ψάχνοντας το πρώτο στοιχείο σε μια λίστα, σίγουρα. Έχουμε πράγματι να μιλάμε σχετικά με συστοιχίες ήδη, πώς μπορείτε να πάρετε κατά τη πρώτο στοιχείο σε μία συστοιχία, Δεν έχει σημασία πόσο καιρό η πίνακας είναι σε κώδικα C; Μπορείτε απλά να χρησιμοποιήσετε σαν τον βραχίονα μηδέν σημειογραφία, μπαμ, είστε εκεί. Και πράγματι συστοιχίες, όπως ένα μέρος, κάτι υποστήριξης γενικά γνωστό ως τυχαίας προσπέλασης, τυχαίας προσπέλασης μνήμη, επειδή μπορείτε κυριολεκτικά μεταβείτε σε οποιαδήποτε θέση. Μπορούμε να το κάνουμε αυτό ακόμα πιο απλά μπορούμε να rewind στην εβδομάδα μηδέν όταν κάναμε Scratch. Πόσο χρόνο θα πάρει για την λένε μπλοκ σε Scratch να εκτελέσει; Απλά συνεχή φορά, σωστά; Πες κάτι, πες κάτι, δεν έχει σημασία πόσο μεγάλο γρατσουνιές κόσμο είναι, είναι πάντα πρόκειται να λάβει το ίδιο χρονικό διάστημα απλά να πω κάτι. 

Έτσι, αυτό είναι το σταθερό χρόνο, αλλά ποια είναι η άλλη πλευρά; Αν αυτό ήταν ανώτερο φράγματα, τι αν θέλουμε για να περιγράψει τα χαμηλότερα όρια των αλγορίθμων μας τρέχει χρόνο; Σχεδόν μια καλύτερη περίπτωση ενδεχομένως, αν θέλετε, αν οι όροι αυτοί θα μπορούσαν να εφαρμοστούν με τον καλύτερο περιπτώσεις, χειρότερες περιπτώσεις, κατά μέσο όρο περισσότερες περιπτώσεις γενικά, αλλά ας επικεντρωθούμε σε χαμηλότερα όρια γενικότερα. Τι είναι ένας αλγόριθμος που έχει ένα κατώτερο όριο των βημάτων n, ή 2n βήματα ή τα βήματα 3η; Μερικά παράγοντας των βημάτων n, αυτό είναι χαμηλότερο όριό του. Ναι; 

ΚΟΙΝΟ: Bubble sort; 

ΟΜΙΛΗΤΗΣ: Bubble sort χρειάζεται σας βήματα ελάχιστα n, γιατί; Γιατί συμβαίνει αυτό; Γιατί θα πρέπει η αρχή να έρθει σε σας διαισθητικά, ακόμη και αν δεν το κάνει μόνο ακόμα; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται]. ΟΜΙΛΗΤΗΣ: Ακριβώς. Με τον καλύτερο δυνατό σενάριο bubble sort, και πολλοί αλγόριθμοι, αν έχετε παραδώσει οκτώ άτομα που έχουν ήδη ταξινομηθεί, θα ήταν ανόητο για σας, ο αλγόριθμος, για να πάει μπροστά και πίσω περισσότερο από μία φορά, σωστά; Επειδή το συντομότερο με τα πόδια μέσα από τη λίστα μια φορά, θα πρέπει να συνειδητοποιήσουν, oh, έκανα κανένα swaps, αυτή η λίστα είναι ταξινομημένη, την έξοδο. Αλλά αυτό δεν πρόκειται να σας πάρει n βήματα. 

Και αντιστρόφως, τι άλλο τρόπος σκέψης σχετικά με αυτό; Bubble sort είναι ένα ωμέγα, να το πω έτσι, του n, γιατί αν κοιτάξετε λιγότερα από n στοιχεία, τι είναι το βασικό θέμα εκεί; Δεν ξέρω αν αυτό είναι ταξινομημένα, σωστά. Εμείς οι άνθρωποι θα μπορούσε ματιά σε οκτώ ανθρώπους και να είναι όπως, OH, αυτό είναι ταξινομημένα, ότι δεν με n βήματα πάρει, αλλά το έκανε. Τα μάτια σας, ακόμα κι αν το είδος της έχει ένα μεγάλο οπτικό πεδίο, Σας κοίταξε οκτώ στοιχεία, κοίταξε σε οκτώ ανθρώπους, ότι είναι οκτώ βήματα αποτελεσματικά. Και μόνο αν πάω με τα πόδια μέσα από το σύνολο του να κάνουμε λίστα Αντιλαμβάνομαι, ναι, ταξινομούνται. Αν μπορώ να σταματήσω στα μισά του δρόμου σκέψης, όλα Εντάξει, αυτό είναι αρκετά ταξινομηθεί μέχρι στιγμής, ποιες είναι οι πιθανότητες δεν είναι ταξινομημένα; Αυτό δεν αλγόριθμοι πρόκειται να είναι σωστό. Θα μπορούσε να είναι πιο γρήγορα, αλλά λανθασμένη. 

Μέχρι τώρα έχουμε έναν τρόπο περιγράφει ένα κατώτερα όρια, και τι γίνεται με σταθερό χρόνο; Τι είναι ένας αλγόριθμος που έχει ένα χαμηλότερο δεσμεύεται για το χρόνο λειτουργίας του ενός; 1 βήμα, 2 στάδια, 10 βήματα, αλλά σταθερή, ανεξάρτητα από Ν, το μέγεθος της εισόδου; Ναι, στο πίσω μέρος. 

ΚΟΙΝΟ: printf; ΟΜΙΛΗΤΗΣ: Τι είναι αυτό; ΚΟΙΝΟ: printf; ΟΜΙΛΗΤΗΣ: printf. Εντάξει, σίγουρα. Γι 'αυτό χρειάζεται ένα σταθερό αριθμό βημάτων. Και εγώ πρέπει να now-- τώρα ότι μιλάμε για κώδικα C και δεν Scratch, κάτι όπως για παράδειγμα, με την printf, θα πρέπει να αρχίσουμε να πάρει προσεκτικοί. Επειδή printf δεν λαμβάνει εισόδου, είναι ένα string, και έγχορδα δεν είναι τεχνικώς έχουν μήκος. Έτσι, αν θέλουμε τώρα να πάρει σε σας, αν δεν σας πειράζει, τεχνικά θα μπορούσε να ισχυριστεί ότι η printf έχει λάβει μια μεταβλητή εισόδου μήκους, και σίγουρα θα μπορούσε να διαρκέσει περισσότερο χρόνο για να τυπώσει μια συμβολοσειρά αυτό το διάστημα, από αυτή τη μακρά. 

Έτσι, ό, τι και αν λάβουμε υπόψη μόνο η διαλογή και ψάχνουν παραδείγματα; Τι γίνεται με τον Mike Smith στο τηλέφωνο βιβλίο, ή δυαδική αναζήτηση γενικότερα; Στην καλύτερη περίπτωση, τι θα μπορούσε να συμβεί; Ανοίγω το βιβλίο του τηλεφώνου και, μπαμ, υπάρχει αριθμός Mike Smith. Μπορώ να τον καλέσετε αμέσως. 

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

Τώρα, ως ένα μέρος, αν ανακαλύψετε ότι τόσο μεγάλη O, το άνω όριο, και το ωμέγα, το κατώτερο όριο, είναι ένα με τον ίδιο, ότι είναι η ίδια φόρμουλα σε παρενθέσεις, μπορείτε επίσης να λένε, απλά να είναι φανταχτερό, ότι κάτι είναι σε θήτα από Ν ή θήτα από κάποια άλλη τιμή. Αυτό απλά σημαίνει ότι όταν μεγάλη O και ωμέγα είναι τα ίδια. Τώρα τι γίνεται με το είδος επιλογής; Ας χρησιμοποιήσουμε αυτό το νέο λεξιλόγιο. Σε τέτοια επιλογή, ό, τι ήμασταν κάνει ξανά, και ξανά, και ξανά; Ήμουν πηγαινοέρχονται μέσα η λίστα, ψάχνει για ποιον; Ο μικρότερος αριθμός. 

Έτσι, πόσα βήματα, πώς πολλές συγκρίσεις έκανα πρέπει να κάνουν ώστε να καταλάβω ποιος το μικρότερο στοιχείο στη λίστα ήταν; n μείον 1, σωστά; Διότι αν εγώ μόλις ξεκινήσει με τη μία είμαι δίνεται και αρχίζω να τον ή την σύγκριση, Στη συνέχεια το άτομό του, τον ή της, αυτόν ή αυτήν, I μπορεί να αντιστοιχιστεί μόνο στοιχεία μαζί n μείον 1 φορές. Έτσι, η επιλογή γίνεται είδος ομοίως n μείον 1 βήματα την πρώτη φορά. 

Πόσα βήματα μου πάρει να βρείτε το δεύτερο μικρότερο στοιχείο; n μείον 2, επειδή είμαι είσαι άλαλος αν συνεχίσετε να ψάχνετε στα ίδια άτομα και πάλι, αν έχω ήδη τον επιλεγμένο ή της και να τους βάλει στη θέση τους. Και το τρίτο βήμα, n μείον 3, τότε το η μείον 4. Έχουμε δει αυτό το μοτίβο πριν, και μάλιστα Η επιλογή του είδους ομοίως έχει ένα άνω φράγμα από n τετράγωνο αν κάνουμε μέχρι αυτό το άθροισμα. Τι είναι το κάτω όριο, το είδος της επιλογής; Ελάχιστα, πόσο επιλογής must χρόνο ταξινόμησης λάβει, όπως την ορίσαμε τη Δευτέρα; Προτείνει δύο επιλογές. Ίσως είναι n, όπως και πριν. Ίσως αυτό είναι n τετράγωνο, όπως είναι τώρα ως το ανώτερο όριο. 

ΚΟΙΝΟ: n τετράγωνο. ΟΜΙΛΗΤΗΣ: n τετράγωνο. Γιατί; 

ΚΟΙΝΟ: Επειδή έχετε να καθορίσει [δεν ακούγεται]. 

ΟΜΙΛΗΤΗΣ: Ακριβώς. Τουλάχιστον όπως ορίζεται είδος επιλογής ήταν αρκετά αφελής, συνεχίζω, βρείτε το μικρότερο στοιχείο. Πήγαινε πάλι, βρείτε το μικρότερο στοιχείο. Πήγαινε πάλι, βρείτε το μικρότερο στοιχείο. Δεν υπάρχει κανένα είδος βελτιστοποίηση εκεί που θα μπορούσε να επιτρέψτε μου να εγκαταλείψετε μετά ακριβώς n ή έτσι τα βήματα. Έτσι, πράγματι, η επιλογή είδος, το ωμέγα n τετράγωνο. 

Τι γίνεται με το είδος εισαγωγής, όπου πήρα που μου δόθηκε, και στη συνέχεια θα τον plopped ή της στο σωστό μέρος; Στη συνέχεια, θα προχωρήσει στο δεύτερο πρόσωπο, αυτόν ή αυτήν plopped στο σωστό μέρος. Στη συνέχεια, το επόμενο πρόσωπο, plopped αυτόν ή αυτήν στο σωστό μέρος. Σημειώστε ότι αυτό είναι πολύ γραμμική, να το πω έτσι. Είμαι μια ευθεία γραμμή, είμαι δεν πηγαίνει πέρα ​​δώθε, Δεν έχω κοιτάζοντας πίσω στην πραγματικότητα, αλλά τι συμβαίνει όταν τον τοποθετήσετε ή της μέσα από την έναρξη της ο κατάλογος όπως κάναμε τη Δευτέρα; Τι συμβαίνει; Ναι; ΚΟΙΝΟ: [δεν ακούγεται]. ΟΜΙΛΗΤΗΣ: Ναι, ότι ήταν η σύλληψη, έτσι δεν είναι; Θα θυμάστε ίσως από συμμαθητές σας, εάν είχαν προβεί σε οποιαδήποτε κίνηση με πόδια τους, ότι ήταν μια πράξη. Έτσι, αν υπήρχαν τρεις άνθρωποι εδώ και το νέο πρόσωπο ανήκε τρόπο εκεί, σε μια μεγάλη σκηνή, όπως αυτή, βέβαια, ο ίδιος ή θα μπορούσε απλά να πάει μέχρι το τέλος. Αλλά αν σκεφτόμαστε ένα υπολογιστής και μια συστοιχία μνήμης, αυτοί οι άνθρωποι θα να χρειαστεί να ανακατέψετε πάνω για να κάνει χώρο για το εν λόγω πρόσωπο. Και έτσι ώστε n μείον 1 shufflings, n μείον 2 shufflings, n μείον 3 shufflings είναι ακριβώς το είδος της συμβαίνει πίσω μου, όχι μπροστά μου όπως και πριν, κατά κάποιο τρόπο. Τώρα, ως ένα μέρος, και ως μπορεί να έχετε δει σε απευθείας σύνδεση αν ξεκινήσετε σπρώχνει γύρω για είδη, υπάρχουν τόσα πολλά διαφορετικά μέρη εκεί έξω, μερικοί από αυτούς καλύτερα από άλλα. Πράγματι, bogosort είναι ένα αυτό είναι το είδος της διασκέδασης να κοιτάζω προς τα πάνω. Bogosort παίρνει ένα σύνολο από αριθμούς ή να πω μια τράπουλα, τους ανακατεύει, και ελέγχους αν είναι ταξινομημένα. Και αν όχι, το κάνει ξανά. Και αν όχι, το κάνει ξανά. Αν όχι, θα το κάνει ξανά. Απίστευτα ηλίθια. 

Και πράγματι, αν μπορείτε να διαβάσετε όπως το άρθρο της Wikipedia, ψευδώνυμο του είναι ηλίθιο είδος. Είναι τελικά θα λειτουργήσει, ελπίζουμε, αρκετό χρόνο, αλλά αυτή η ποσότητα του χρόνου θα μπορούσε να πάρει αρκετό χρόνο. Έτσι, αν θα μπορούσα να, ας τα πράγματα ταχύτητας up από το παράδειγμα Μαίρη Μπεθ νωρίτερα, έχοντας λίγα περισσότερα στοιχεία, αλλά δύο περισσότερους επεξεργαστές. Δύο άνθρωποι, αν Δεν θα με πείραζε να συνεργαστούν μαζί μου. Πόσο περίπου 1 εδώ, και ας go-- κανείς εκεί; Κανείς εκεί πέρα; OK. Μπορείτε με το μαύρο shirt, ναι, έλα κάτω. Εντάξει, αυτό είναι το όνομά σου; 

ΚΟΙΝΟ: Peter. 

ΟΜΙΛΗΤΗΣ: Τι είναι αυτό; 

ΚΟΙΝΟ: Peter. ΟΜΙΛΗΤΗΣ: Peter, David, χαίρομαι που σε γνωρίζω. Εντάξει, έχουμε Peter εδώ, αν θέλουν να έρθουν στο τραπέζι εδώ. Και τι είναι το όνομά σας; 

ΚΟΙΝΟ: Έλενα. ΟΜΙΛΗΤΗΣ: Έλενα. Εντάξει, ωραίο να σας γνωρίσουμε. Έλενα συναντήστε τον Πίτερ. Peter, Έλενα. Και θα πρέπει Andrew μέχρι εδώ καλά, παρακαλώ. Και πρόκληση σας θα να είναι να ταξινομήσετε μια τράπουλα. Και αν δεν είναι εξοικειωμένοι, κατάστρωμα των καρτών θα πρέπει τελικά να ταξινομηθούν λίγο κάτι σαν Αυτό που θα κάνουμε τα σωματεία, τότε τα φτυάρια, τότε οι καρδιές και διαμάντια, από άσσο ως ένα, σε όλη τη διαδρομή μέχρι το βασιλιά. 

Οι κάρτες Πάω να σας δώσω πρόκειται να είναι 52 σε ποσότητα. Εμείς πάμε για να ομοίως χρόνο σας, ακριβώς σε μια στιγμή. Εμείς πάμε για να ρίξει Andrew επάνω στην οθόνη εδώ, έτσι ώστε να παρακολουθήσουν το κάνετε αυτό. Και έτσι ώστε όλα αυτά είναι το πιο ορατό, αυτά είναι τα χαρτιά που πήρα για την Amazon. Έτσι είναι ήδη τυχαία ταξινομούνται, και θα πάμε να έχετε χρόνο. Και θα πάμε να κρατήσει το πραγματικό αυτή τη φορά, έτσι θα πάμε να προσπαθήσουμε να σε πιέσω γιατί αλλιώς αυτό θα πάρει κουραστικό γρήγορα. Αν θα μπορούσε να προχωρήσει για να ταξινομήσετε 52 στοιχεία μαζί με κάποια μέσα, τώρα. 

Και πάλι, όπως θα δούμε σε αυτά παιδιά κάνουν ό, τι, στο τέλος πρόκειται να παραχθεί μια προφανή αποτέλεσμα, σκεφτείτε πραγματικά πώς είστε καθένα να κάνει, πώς θα μπορούσε να το περιγράψει. Επειδή πάλι, αυτές είναι όλες οι διαδικασίες, οι αλγόριθμοι ότι παίρνουμε ως δεδομένο ως άνθρωπο. Αλλά ίσως έχετε καιρό διαίσθηση, πολύ πριν ακόμη σκεφτεί τη λήψη ενός επιστήμη των υπολογιστών τάξη σας θα μπορούσε να είχε την διαίσθηση με το οποίο για την επίλυση προβλημάτων όπως αυτό. Αλλά τη στιγμή που θα αναγνωρίζουν τα σχέδια και να αρχίσει να επισημοποιήσει τα βήματα με τα οποία είστε επίλυση των προβλημάτων αυτών, θα διαπιστώσετε ότι μπορείτε να λύσετε πολλά πιο ενδιαφέρουσα και πολύ πιο περίπλοκη προβλήματα γρήγορα. Έτσι, κάποιος από το ακροατήριο, τι είναι τουλάχιστον ένα στοιχείο του αλγορίθμου ότι χρησιμοποιούν εδώ; 

ΚΟΙΝΟ: [δεν ακούγεται] ΟΜΙΛΗΤΗΣ: Τι είναι αυτό; ΚΟΙΝΟ: Με κοστούμι. ΟΜΙΛΗΤΗΣ: Με κοστούμι. Έτσι, η πρώτη που συσπειρώνονται όλα τα διαμάντια μαζί φαίνεται, όλα τα καρδιές μαζί, φαίνεται, και ούτω καθεξής, χωρίς σεβασμό για τους αριθμούς στις κάρτες. Και τώρα εμφανίζονται, για παράδειγμα, να τους διαλογή με αριθμό. Πολύ καλό. 

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

Έτσι, υπάρχει μια ενδιαφέρουσα ιδέα ότι και πάλι, daresay, είναι πολύ διαισθητική, ακόμη και αν θα μπορούσαν ποτέ να έχουν χαστούκισε αυτό το είδος της ετικέτας για αυτό. Αυτή η θεμελιώδης έννοια της διαίρεσης το πρόβλημα δεν στο μισό αυτού του χρόνου, αλλά τουλάχιστον σε τέσσερα κομμάτια. Επίλυση λίγο πολύ ουσιαστικά πανομοιότυπα προβλήματα σε απομόνωση μεταξύ τους, και στη συνέχεια τη συγχώνευση των αποτελεσμάτων. Και, εξαιρετική, κάνει. Εντάξει, μια μεγάλη στρογγυλή χειροκροτήματα, αν μπορούσαμε. 

[Χειροκρότημα] 

ΟΜΙΛΗΤΗΣ: Δεν έχω καμία ιδέα για το τι θα κάνει με αυτά, αλλά εδώ θα πάτε. Σας ευχαριστώ πολύ. Ας δούμε, λοιπόν, δύο λεπτά και οκτώ δευτερόλεπτα, αν θέλετε να προκαλέσετε τους φίλους σας. Τι, λοιπόν, πρόκειται να είναι ένα πάρει μακριά από αυτό ότι μπορούμε να αξιοποιήσουν γενικότερα; Λοιπόν, σκεφτείτε ότι πίσω σε αυτή η σειρά των αριθμών, και ότι πίσω τώρα σε ορισμένα από τα pseudocode έχουμε γράψει και στο παρελθόν, και αυτή ήταν η ψευδοκώδικα για την επίλυση του προβλήματος του τηλεφωνικού καταλόγου. Όπου σε ψευδοκώδικα I απαρίθμησε έναν πιο μεθοδικό τρόπο που περιγράφει πώς έκανα ένα πολύ έξυπνο ανθρώπινη αλγόριθμο της διαίρεσης του τηλεφώνου βιβλίο στη μέση, επανάληψη, επαναλαμβάνω, επαναλαμβάνω, μέχρι να βρω κάποιον σαν τον Mike Smith, αν είναι όντως στον τηλεφωνικό κατάλογο. 

Αλλά το είδος του χρησιμοποίησε αυτό θα καλέσω ένα πολύ επαναληπτική προσέγγιση εδώ, ειδικότερα ανακοίνωση της γραμμής 8 και η γραμμή 11. Αυτά είναι ενδείξεις μιας επαναληπτικής προσέγγιση, μια προσέγγιση looping, γιατί αυτό είναι ακριβώς η συμπεριφορά που επιφέρουν. Οι γραμμές και οι δύο λένε πηγαίνετε στο γραμμή τρία, και μπορείτε να το είδος της σκεφτείτε ότι σας μάτι, ως ένας βρόχος. Θα σας λέει να πάει πίσω μέχρι και το βήμα τρεις και επαναλάβετε ξανά και ξανά, και πάλι. 

Αλλά τι θα γινόταν αν εμείς αξιοποιήσουμε μία βασική ιδέα εδώ που κάναμε δεν είναι η τελευταία φορά, και την απλούστευση της γραμμής 8 και γραμμή 11 και τους γείτονές τους , όπως ακριβώς αυτό, σε κίτρινο. Δεν είναι ουσιαστικά συντόμευση η pseudocode πολύ, αλλά είναι θεμελιωδώς αλλαγή η φύση του αλγόριθμου μου. Αυτό που είμαι τώρα λέγοντας στο βήμα 7, στο βήμα 10, είναι να ψάξει για Mike με τον ίδιο ακριβώς τρόπο, αλλά μόνο στην αριστερή το μισό ή το δεξί μισό. 

Έτσι με άλλα λόγια, εάν Ξεκινώ από το πρώτο βήμα, σηκώστε τηλεφωνικό κατάλογο, ανοιχτό σε μέση του τηλεφωνικού καταλόγου, να δούμε τα ονόματα, αν Smith είναι μεταξύ Το όνομά του, καλέστε Mike, αλλιώς αν Smith είναι νωρίτερα στο βιβλίο, βήμα επτά αναζήτηση για Mike στο αριστερό μισό του βιβλίου. Αλλά αυτό το είδος του αισθάνεται όπως αυτό είναι μου αφήνοντας κρέμονται, σωστά; Σε κίτρινο, είναι ένα διδασκαλίας, αλλά πώς μπορώ να κάνω αναζήτηση για Mike στο αριστερό το ήμισυ του τηλεφωνικού καταλόγου; Πού μπορώ να έχουν μια αλγόριθμο με τον οποίο θα να ψάξετε για κάποιον σαν τον Mike Smith; Λοιπόν, αυτό είναι μας κοιτάζει επίμονα στο πρόσωπο. I κυριολεκτικά να χρησιμοποιούν την ίδια ακριβώς πρόγραμμα εφαρμόζεται αποτελεσματικά ανεβαίνοντας στην κορυφή ξανά και εκ νέου λειτουργία οι ίδιες γραμμές κώδικα. 

Έτσι, ακόμη και αν αυτό θα πρέπει να αισθάνονται σαν ένα κομμάτι από ένα κυκλικό ορισμό Όπου και αν απάντηση είναι κάποιος ερώτηση ακριβώς το είδος της ερώτησης το ίδιο ερώτημα και πάλι, όπως γιατί, γιατί, γιατί; Η πραγματικότητα είναι, γιατί έχουμε σκληρά κωδικοποιημένους ένα ζευγάρι από ειδικές γραμμές, βαθμίδα 4, το οποίο είναι ένα, αν και το βήμα 12, το οποίο Είναι ουσιαστικά ένα άλλο υποκατάστημα, γιατί έχουμε αυτά τα μέτρα προσωρινή λύση, Ο αλγόριθμος αυτός θα τερματίσει αν βρείτε Mike, ή αν δεν το κάνουμε. Αλλά στο βήμα 7 και 10 τώρα, έχουμε τι θα καλέσετε έναν αναδρομικό αλγόριθμο. Και αναδρομή είναι πράγματι μια ισχυρή ιδέα Αυτό είναι λίγο μυαλό κάμψης στην πρώτη, ότι μπορούμε τώρα να εφαρμόζονται ως εξής. 

Συγχώνευση του είδους θα είναι το τελευταίο είδος, ότι κοιτάξουμε, τουλάχιστον στην κατηγορία επίσημα. Και είναι θεμελιωδώς διαφορετική από αυτά τα τρία τελευταία, και σίγουρα τελευταία τέσσερα αν συμπεριλάβουμε bogosort. Εδώ είναι η ψευδοκώδικα για τη συγχώνευση ταξινόμησης. Κατά την είσοδο των n στοιχείων, δεδομένης μια σειρά μεγέθους n, αν το η είναι μικρότερο από 2, επιστροφή. Έτσι, γιατί έχω ότι λογικότητα ελέγξτε πρώτα; Ποια είναι η επίπτωση αν το χέρι σας μια συστοιχία των οποίων το μήκος η είναι μικρότερη από 2; Είναι ήδη ταξινομηθεί, προφανώς, σωστά; Επειδή ο κατάλογος είτε έχει ένα στοιχείο, το οποίο είναι κοινότοπα ταξινομούνται γιατί είναι το μόνο πράγμα εκεί. Ή, είναι του μεγέθους που σημαίνει μηδέν δεν υπάρχει τίποτα για να ταξινομήσετε, τόσο από τη φύση αυτό είναι ταξινομημένο. Δεν υπάρχει απολύτως τίποτα λάθος εκεί. Έτσι, αυτό είναι το λεγόμενο βασικό σενάριο μας. 

Αυτό είναι παρόμοιο σε πνεύμα σε ό, τι κάναμε με τον Mike. Αν Mike στο βιβλίο του τηλεφώνου, να τον καλέσει. Αν δεν είναι εκεί, να τα παρατήσουμε. Είναι το λεγόμενο βασικό σενάριο, για να βεβαιωθείτε ότι ο αλγόριθμος αυτός, στο τέλος της ημέρας θα σταματήσει σε ορισμένες περιπτώσεις. 

Αλλά εδώ είναι το άλμα της πίστης τώρα, αλλιώς, ταξινομήσετε το αριστερό μισό των στοιχείων, Στη συνέχεια ταξινομήσετε το δικαίωμα ήμισυ των στοιχείων, και, στη συνέχεια, να συγχωνεύσει τα ταξινομημένα μισά. Και εδώ είναι που αισθάνεται όπως είμαστε copping έξω. Σας έχω ζητήσει να ταξινομήσετε n στοιχεία, και είμαι λέει, εντάξει, δεν είναι από τη διαλογή η αριστερά και η διαλογή του δικαιώματος. Αλλά εγώ λέω ένα άλλο πράγμα, και αυτό είναι το βασικό θέμα φαίνεται στη διαίσθηση μέχρι στιγμής, υπάρχει αυτό το τρίτο βήμα της συγχώνευσης. Που ακόμα κι αν Φαίνεται τόσο χαζή σε πνεύμα, όπως ακριβώς η συγχώνευση πράγματα μαζί, φαίνεται να είναι ένα σημαντικό βήμα προς την επανασυναρμολόγηση των δύο προβλημάτων που χωρίστηκαν τελικά στο μισό. 

Έτσι συγχώνευση είδος, ας το κάνουμε αυτό, αν θα το χιούμορ μου, με μια επιπλέον απόδειξη, ακριβώς έτσι ώστε να έχουμε κάποια αριθμούς για να εργαστεί με. Μπορώ να ανταλλάξουν οκτώ στρες μπάλες για οκτώ άτομα; Εντάξει, πώς για σας τρεις, τέσσερις σας σε αυτή την ενότητα, πέντε, έξι, και ας Δεν 7, 8, έλα επάνω. Εντάξει, ναι OK. Μείον 8, εκεί πάμε, συν 1. Εξαιρετική. Εντάξει, έλα επάνω, ας γρήγορα θα δώσει αριθμούς. Αριθμός δύο, νούμερο τρία, τέσσερα τον αριθμό, τον αριθμό πέντε, έξι, επτά, οκτώ. Έκανα οκτώ σωστά αυτή τη φορά. 

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

Έτσι συγχώνευση είδος πρώτα απ 'όλα την είσοδο των n στοιχείων, και προφανώς δεν είναι μικρότερη από δύο, είναι οκτώ, οπότε έχω κάποια δουλειά να κάνουμε. Μέχρι τώρα διανοητικά εμείς ως τάξη είναι τώρα στο υποκατάστημα άλλο, πράγμα που σημαίνει τρία βήματα. Πρώτον, πρέπει να ταξινομήσετε το αριστερό ήμισυ των στοιχείων. Λοιπόν, πώς μπορώ να το κάνουμε αυτό; Λοιπόν, θα πάω με το είδος της διανοητικά χωρίζουν τη λίστα εδώ, δεν χρειάζεται να μετακινήστε με φυσικό τρόπο, και είμαι πρόκειται να επικεντρωθεί μόνο στην αριστερό ήμισυ από τα στοιχεία εδώ. Λοιπόν, πώς μπορώ να πάω για διαλογή μια λίστα τώρα από το μέγεθος τέσσερα; Τι είναι ο αλγόριθμος μου; Πρώτα να ελέγξω είναι n λιγότερο από δύο, όχι, γι 'αυτό προχωρήστε στο μπλοκ άλλο πάλι. Ταξινόμηση αριστερό μισό των στοιχείων. 

Μέχρι τώρα πάλι, διανοητικά, και αυτό είναι όπου θα πρέπει να προκύψουν πολλά διανοητική ιστορία, αν θέλετε. Τώρα είμαι διαλογής το αριστερό ήμισυ του αριστερού ημίσεως. Εντάξει, έτσι και τώρα καλώ ίδια της συγχώνευσης μου διαλογής αλγόριθμος, είναι n λιγότερο από δύο; Όχι, δεν είναι δύο, γι 'αυτό πρέπει να ταξινομήσετε το αριστερό μισό, και το δεξί μισό. Πάμε λοιπόν, να ταξινομήσετε το αριστερό μισό. Γιατί δεν κάνουν απλά πάρτε ένα βήμα προς τα εμπρός. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Darren. 

ΟΜΙΛΗΤΗΣ: Dan. Dan έχει κάνει βήματα μπροστά. 

ΚΟΙΝΟ: Darren. ΟΜΙΛΗΤΗΣ: Darren, γίνεται. Μήπως λέτε Darren ή Dan; 

ΚΟΙΝΟ: Darren. 

ΟΜΙΛΗΤΗΣ: Darren. OK, Darren έχει ενισχυθεί προς τα εμπρός και είναι τώρα ταξινομούνται. Και αυτό είναι σχεδόν μια ανόητος ισχυρισμός, σωστά; Δεν φαίνεται πραγματικά να επιτευχθεί τίποτα, αλλά ας προχωρήσουμε. Τώρα, επιτρέψτε μου να ταξινομήσετε το δικαίωμα ήμισυ των στοιχείων. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Luke. 

ΟΜΙΛΗΤΗΣ: Luke. Έλα, βήμα προς τα εμπρός. Τέλος, έχω ταξινομούνται Λουκά. Το αριστερό μισό είναι τώρα ταξινομούνται και το δεξί μισό τώρα ταξινομούνται, αλλά και πάλι, υπάρχει ένα βασικό βήμα εδώ. Τι μπορώ να κάνω το επόμενο πρέπει να κάνουμε; Συγχώνευση τα ταξινομημένα μισά. Τώρα θα πάμε να έχουν μόνο όλοι εμπρός και πίσω με τον τρόπο αυτό, γιατί το είδος του πρέπει κάποιο διάστημα το μηδέν. Είναι σχεδόν σαν αυτά οι τύποι είναι σε ένα τραπέζι, και χρειάζομαι κάποια δωμάτια να τα μετακινήσετε γύρω από την. Έτσι, Πάω να συγχωνεύσει εσείς κοιτάζοντας στο αριστερό μισό και το δεξί μισό. Και που προφανώς έρχεται πρώτη, αριστερό μισό ή δεξιά ημίχρονο; Έτσι ακριβώς το μισό, οπότε ας προχωρήσουμε Luke πάνω εδώ στην αρχική θέση του Ντάρεν. Και τώρα να συγχωνεύσει το αριστερό μισό σε, Darren πρόκειται να προχωρήσουμε εκεί. 

Έτσι μοιάζει σχεδόν ένα φαινόμενο bubble sort, αλλά τα θεμελιώδη αλγόριθμο μου, πολύ διαφορετικά αυτή τη φορά. Αλλά τώρα είναι όπου τα πράγματα παίρνουν μια λίγο ενοχλητικό γιατί Πρέπει να rewind διανοητικά όπου άφησα off. Έχω μόλις συγχωνεύτηκαν τα ταξινομημένα μισά, πράγμα που σημαίνει ότι είμαι όπου με αλγόριθμο μου; Θα πρέπει να ταξινομήσετε το δεξί μισό, σωστά; 

Αν πίσω, κυριολεκτικά για το βίντεο, εσείς θα δείτε ότι φτάσαμε σε αυτό το σημείο του Λουκά και Darren ταξινομώντας το αριστερό ήμισυ του αριστερού ημίσεως. Στη συνέχεια συγχωνεύθηκαν εκείνες ταξινομημένα μισά, το οποίο σημαίνει ότι το επόμενο βήμα είναι το είδος της δεξί μισό του αριστερό μισό. Εντάξει, ας το κάνουμε αυτό πιο γρήγορα. Εντάξει, έξι, Πάω να διεκδικήσει μπορείτε τώρα ταξινομούνται, έλα προς τα εμπρός. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Adriano. 

ΟΜΙΛΗΤΗΣ: Adriano. Adriano τώρα ταξινομούνται. Και τι είναι το όνομά σας; 

ΚΟΙΝΟ: Alex. 

ΟΜΙΛΗΤΗΣ: Alex τώρα ταξινομούνται. Αριστερό μισό, δεξί μισό, Ποιο είναι το τελικό βήμα; Συγχώνευση. Αρκετά ασήμαντο, έτσι είμαι πρόκειται να συγχωνευθούν σε έξι, κάνουμε ένα βήμα πίσω, οκτώ, κάνουμε ένα βήμα πίσω. Και σήμερα παρατηρούμε ότι αυτό είναι ένα χρήσιμο πακέτο, τι είναι πλέον αλήθεια για το αριστερό μισό της λίστα, ανεξάρτητα από το πώς ξεκινήσαμε; Θα είναι ταξινομημένο. 

Τώρα αυτό δεν είναι ταξινομημένα σε το μεγάλο σχέδιο των πραγμάτων, αλλά είναι ταξινομημένο ανεξάρτητα από το άλλο μισό. Τώρα ποιο στάδιο είμαι στο αν κρατώ κουρδίζεται το πώς ξεκίνησε η ιστορία; Τώρα έχω να ταξινομήσετε το δεξί μισό. Μέχρι τώρα είμαστε πολύ πίσω σε η αρχή της ιστορίας, και ας το κάνουμε αυτό πιο γρήγορα. Έτσι, Πάω να ταξινομήσετε τα δεξί μισό του όλη τη λίστα. Ποιο είναι το επόμενο βήμα; Ταξινομήστε το αριστερό μισό του δεξί μισό. Ταξινομήστε το αριστερό μισό της αριστερό μισό του δεξί μισό. Και τι είναι το όνομά σας; 

ΚΟΙΝΟ: Omar. 

ΟΜΙΛΗΤΗΣ: Omar, βήμα προς τα εμπρός, γίνεται. Αριστερό μισό είναι ταξινομημένο. Και τι είναι το όνομά σας; 

ΚΟΙΝΟ: Chris. 

ΟΜΙΛΗΤΗΣ: Chris, κάνουμε ένα βήμα προς τα εμπρός, που τώρα ταξινομούνται. Ποιο είναι το βασικό βήμα τώρα; Συγχώνευση. Έτσι, κανείς δεν πρόκειται να συγχωνευθούν σε θέση εδώ, αν θα μπορούσατε να πάρετε ένα βήμα πίσω, και τρεις πρόκειται να κάνουμε ένα βήμα πίσω, συγχώνευση. Έτσι, το αριστερό μισό της δεξί μισό, τώρα ταξινομούνται. Ειλικρινά, ο αλγόριθμος αυτός αισθάνεται σαν να σπαταλάτε τον τρόπο περισσότερο χρόνο από ό, τι πριν, αλλά αν το κάναμε αυτό σε πραγματικό χρόνο, εμείς θα δείτε τι τα φαστ φουντ πρόκειται να είναι. Τώρα είμαι εδώ, σωστά μισό του δεξιού μισού, επιτρέψτε μου να πάει μπροστά και να ταξινομήσετε το αριστερό μισό. Βήμα προς τα εμπρός, ποιο είναι το όνομά σας; ΚΟΙΝΟ: Ramsey. ΟΜΙΛΗΤΗΣ: Ramsey τώρα ταξινομούνται. Ποιο είναι το όνομά σου; 

ΚΟΙΝΟ: Μαρίνα. 

ΟΜΙΛΗΤΗΣ: Μαρίνα είναι τώρα ταξινομούνται ως καλά, αν πάρετε ένα βήμα προς τα εμπρός. Βασικά βήμα εδώ είναι τώρα συγχωνεύονται, είμαι πρόκειται να κόβω από δύο λίστες μου, αριστερά και δεξιά. Πέντε πρόκειται να έρθει πρώτα, και επτά πρόκειται να έρθει το επόμενο. Και πάλι, αυτό είναι σκόπιμη. Το γεγονός ότι παίρνετε βήματα προς τα εμπρός και πίσω έχει ως στόχο να δηλώνετε ότι δεν μπορούμε κάνει αυτόν τον αλγόριθμο στη θέση του, όπως εύκολα ως bubble sort, και το είδος επιλογής, και το είδος εισαγωγής, όπου απλά φυλάσσονται swapping ανθρώπους. I κυριολεκτικά χρειάζεται ένα είδος χαρτί το μηδέν στην οποία να θέσει αυτά τα παιδιά ενώ κάνω τη συγχώνευση, και, στη συνέχεια, μπορώ να τους βάλει στη θέση του. Και αυτό είναι το κλειδί, επειδή είμαι χρησιμοποιώντας ένα νέων πόρων, το διάστημα, όχι μόνο χρόνο. 

Εντάξει, αυτό είναι εκπληκτικό. Αριστερό μισό είναι ταξινομημένο, δεξί ήμισυ ταξινομημένο, τώρα ότι κλειδί συγχώνευση βήμα. Πώς θα πάω να συγχωνεύσει αυτό; Έτσι, αν θα ακολουθήσει μου αριστερό χέρι και το δεξί χέρι, Πάω να επισημάνω το αριστερό μου χέρι στο αριστερό μισό, μου το δεξί του χέρι στο δεξιό μισό, και τώρα έχω να αποφασίσει βήμα προς βήμα το οποίο να συγχωνευθούν σε. Ποιος προφανώς έρχεται πρώτο; Νούμερο ένα. Έτσι, έλα εδώ, εδώ είναι πρόχειρο μας. Μέχρι τώρα νούμερο ένα, και ανακοίνωση τι θα κάνω με το δεξί μου χέρι, Πάω να μετακινηθείτε προς τα δεξιά το ένα χέρι μου βήμα πάνω στο σημείο αριθμός τρία, και τώρα έχω να κάνω την ίδια απόφαση. Και πραγματικά να σταθεί σωστά σε μπροστά από Luke εδώ αν μπορούσα, γιατί αυτό είναι πρόχειρο μας. Μέχρι που έρχεται το επόμενο; Έχουμε Λουκά με αριθμό δύο ή Chris με τον αριθμό τρία. Προφανώς Λουκά, τον αριθμό δύο, έτσι ώστε να έρθει εδώ. 

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

Έτσι τώρα ας τελειώσουμε αυτό επάνω γρήγορα. Έτσι, τρία έρχεται το επόμενο, Στη συνέχεια τέσσερις έρχεται το επόμενο, και τώρα πέντε έρχεται δίπλα, στη συνέχεια, έξι, και επτά, και στη συνέχεια, τελικά οκτώ. Αίσθηση σαν το πιο αργό αλγόριθμο ακόμα, αλλά αν δεν είμαστε πραγματικά τρέξει στο ίδιο είδος από την ταχύτητα του ρολογιού, έτσι ώστε να μιλούν, με τον ίδιο ρολόι που χτυπάει όπως πριν. Γιατί; Λοιπόν, ας ρίξουμε μια δείτε το τελικό αποτέλεσμα. 

Ας πάμε πίσω εδώ, επιτρέψτε μου να τραβήξτε μια επίδειξη οπτικά του τι κάναμε. Μεγέθυνση εδώ, σε αυτό το σελίδα εδώ, λέγοντας Firefox ότι θέλουμε να περιμένω στην ουρά σε αυτό το πλαίσιο, ας λένε bubble sort, με την οποία είμαστε τώρα καλά εξοικειωμένοι, είδος επιλογής, το οποίο είναι ένα άλλο αρκετά απλή ένα, και τώρα η σημερινή συγχώνευση ταξινόμησης, η οποία θα είναι κλιμακούμενη τέλος μας. Ο λόγος που πήρε τόσο πολύ περισσότερο εδώ με τους ανθρώπους και μου προφορικά είναι, Προφανώς, είμαι εξηγώντας κάθε βήμα. Αλλά αν μπορείτε απλά να εκτελέσει αυτό, πολύ όπως κάναμε bubble sort και επιλογή ταξινόμησης όχι μόνο οπτικά, ρολόι πόσο πιο αποτελεσματικά αυτή η μόχλευση των διαίρεση και κατάκτηση μπορεί να είναι όταν εφαρμόζεται σε ένα σύνολο δεδομένων που είναι όχι ακόμη και μέγεθος οκτώ, αλλά ακόμη και πολύ, πολύ μεγαλύτερο. Σας δίνω συγχώνευση είδος, πλάι πλευρά με αυτές τις άλλες αλγόριθμους. Αυτό πρόκειται να πάρει επώδυνες γρήγορα, και η κατάληξη δεν είναι ιδιαίτερα κλιμακούμενη, το μόνο που καταλήγουν να ταξινομούνται. Αλλά το κλειδί για να πάρει είναι ότι κοίτα πόσο πιο γρήγορα συγχώνευση ταξινόμησης ήταν, αν νομίζετε ότι είμαι ακριβώς το είδος των πειράξουν μαζί σας. Αν το κάνουμε αυτό μία τελευταία φορά, ας αφήσουμε φορτώσετε αυτό, ας πάμε πίσω και επιλέξτε bubble sort, και μόνο για πλάκα, ας επιλέξουν την εισαγωγή είδος, μόνο για το καλό μέτρο. Και πάλι αυτή τη φορά, ας επιλέξετε συγχώνευση ταξινόμησης και ας λειτουργεί πραγματικά αυτά πλάι-πλάι. 

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

ΚΟΙΝΟ: Log n. 

ΟΜΙΛΗΤΗΣ: Log n. Στη συνέχεια, όμως υπάρχει ένα άλλο σημαντικό βήμα, ο αλγόριθμος αυτός δεν είναι log n βήματα. Αν ήταν μόνο log n βήματα, θα είναι στο ίδιο πρόβλημα όπως και πριν, όπου δεν μπορούμε να είμαστε ότι όλα είναι ταξινομημένα. Θα πρέπει να κοιτάξουμε ελάχιστα n στοιχεία για να είστε σίγουροι n Τα στοιχεία ταξινομούνται, αλλιώς είναι ένα άλμα πίστης. 

Έτσι είναι ελάχιστα log n βήματα, αλλά τι γίνεται με αυτό το βασικό βήμα για τη συγχώνευση όπου συγχωνεύονται αριστερό μισό και το δικαίωμά μου μισό και περπάτησε κατά μήκος της σκηνής; Πόσα βήματα είναι ότι για τη συγχώνευση; Είναι n, αλλά δεν το έκανα μόνο συγχωνεύσει την τελευταία φορά. Σε κάθε μία από αυτές τις ένθετες κλήσεις, για κάθε αυτών των ένθετων συγχωνεύσεις, ακόμα ταξινομηθεί. Θα συγχωνευθούν αυτά τα δύο παιδιά, τότε αυτά τα δύο παιδιά, τότε αυτά τα δύο παιδιά και ούτω καθεξής. 

Έτσι έκανα συγχώνευση ξανά, και ξανά. Πόσες φορές; Έτσι, κάθε φορά που διαιρείται το κατάλογος στο μισό, έκανα μια συγχώνευση. Χωρίστε τη λίστα στο μισό, κάνει μια συγχώνευση. Έτσι, αν διαιρώντας τη λίστα μπορεί να γίνει φορές log n, και η συγχώνευση παίρνει τελικά n βήματα, αυτό θα μπορούσε να είναι τώρα το ανώτερο δεσμεύεται για τη λειτουργία χρόνου του αλγορίθμου μας; n log n. 

Και πράγματι, αυτό είναι ό, τι έχουμε επιτύχει εδώ. Έτσι, η αίσθηση που βλέπετε οπτικά όταν αυτά τα τρία πράγματα που τρέχουν πλάι-πλάι είναι n τετράγωνο εναντίον n τετράγωνο εναντίον n log n. Που ουσιαστικά θα δούμε, όχι μόνο σήμερα αλλά και στο μέλλον, είναι πολύ, πολύ πιο γρήγορα. Ένα χειροκρότημα για αυτά τα παιδιά, Θα τους ανταμείψει με μπάλες άγχος. Ας διακόψουμε εδώ σήμερα, και εμείς θα δούμε τη Δευτέρα.