[Παίζει μουσική] DAVID MALAN: Εντάξει. Εντάξει, να καλωσορίσω πίσω. Έτσι, αυτή είναι η Εβδομάδα 4, η αρχή Εκτιμώντας ήδη. Και θα θυμάστε ότι την περασμένη εβδομάδα, βάζουμε κωδικοποιεί μέρος μόνο για λίγο και αρχίσαμε να μιλάμε λίγο περισσότερο υψηλού επιπέδου, για τα πράγματα όπως αναζήτηση και την ταξινόμηση, η οποία όμως κάπως απλές ιδέες, είναι αντιπροσωπευτικό μιας κατηγορίας προβλημάτων θα αρχίσετε να λύσει ιδιαίτερα όπως μπορείτε να αρχίσετε να σκέφτεστε για τις τελικές έργα και ενδιαφέρουσες λύσεις που ίσως χρειαστεί να προβλήματα του πραγματικού κόσμου. Τώρα είδος φούσκα ήταν ένα από τα απλούστερα τέτοιων αλγορίθμων, και εργάστηκε από την κατοχή αυτών των μικρών αριθμών σε μια λίστα ή σε είδος σειρά φούσκα δρόμο τους μέχρι την κορυφή, και η μεγάλους αριθμούς κινηθεί το δρόμο τους προς τα κάτω για να το τέλος του εν λόγω καταλόγου. 

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

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

Έτσι, n τετράγωνο. Και ποια ήταν n; 

ΚΟΙΝΟ: Αριθμός στοιχείων. 

DAVID MALAN: Έτσι n ήταν η αριθμό στοιχείων. Και έτσι θα κάνουμε αυτό συχνά. Κάθε φορά που θέλουμε να μιλήσουμε για το μέγεθος ενός προβλήματος ή το μέγεθος της εισόδου, ή το ποσό του χρόνου που χρειάζεται για την παραγωγή προϊόντος, απλά θα γενικευμένη ό, τι η είσοδος είναι το κ. Έτσι, πίσω στην Εβδομάδα 0, ο αριθμός σελίδων στον τηλεφωνικό κατάλογο ήταν n. Ο αριθμός των φοιτητών στην αίθουσα ήταν Ν. Έτσι κι εδώ, είμαστε μετά αυτό το μοτίβο. 

Τώρα n τετράγωνο δεν είναι ιδιαίτερα γρήγορα, έτσι προσπαθήσαμε να κάνουμε κάτι καλύτερο. Και γι 'αυτό κοίταξε σε μια-δυο άλλους αλγορίθμους, μεταξύ των οποίων ήταν είδος επιλογής. Έτσι, το είδος επιλογής ήταν λίγο διαφορετική. Ήταν σχεδόν απλούστερο, τολμώ να πω, σύμφωνα με την οποία άρχισα κατά την έναρξη της κατάλογο των εθελοντών μας και εγώ μόλις και πάλι και ξανά και ξανά πέρασε ο κατάλογος, το μάδημα το μικρότερο στοιχείο σε μια στιγμή και τη θέση του ή της στην αρχή της λίστας. 

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

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

Έτσι, τα θέματα αυτά να συμβούν στον πραγματικό κόσμο. Μόλις λίγα χρόνια πριν, όταν ένα ορισμένο γερουσιαστής έτρεχε για τον Πρόεδρο, Eric Schmidt, κατά τη στιγμή ο διευθύνων σύμβουλος της Google, είχε πράγματι τη δυνατότητα να του πάρει συνέντευξη. Και σκεφτήκαμε να μοιραστούμε αυτό το YouTube κλιπ για σας εδώ, αν θα μπορούσαμε να γυρίσουμε up ο όγκος. 

[PLAYBACK VIDEO] 

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

[Γέλια] 

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

[Γέλια] -Εσείς νομίζετε ότι αστειεύομαι; Είναι ακριβώς εδώ. Ποιος είναι ο πιο αποτελεσματικός τρόπος για να ταξινομήσετε ένα εκατομμύριο δύο-bit ακεραίων; 

[Γέλια] 

-Λοιπόν, εεε - 

-Συγγνώμη. Ίσως θα έπρεπε - 

-Όχι, όχι, όχι, όχι, όχι. 

-Αυτό δεν είναι ένα - OK. 

-Νομίζω ότι το είδος των φυσαλίδων θα να είναι ο λάθος τρόπος να πάει. 

[Γέλια] 

[Επευφημίες και χειροκροτήματα] 

-Έλα, ο οποίος είπε αυτό; OK. 

[PLAYBACK VIDEO END] 

DAVID MALAN: Έτσι εκεί το έχετε. Έτσι αρχίσαμε να ποσοτικοποιηθούν αυτές τρέξιμο φορές, να το πω έτσι, με κάτι ονομάζεται ασυμπτωτική σημειογραφία, το οποίο είναι αναφέρομαι μόνο στο είδος μας της στροφής τα στραβά μάτια σε αυτές τις μικρότερες διαστάσεις και μόνο κοιτάζοντας το χρόνο λειτουργίας, η απόδοση αυτών των αλγορίθμων, καθώς το n παίρνει πραγματικά μεγάλη την πάροδο του χρόνου. Και γι 'αυτό παρουσιάζει μεγάλο O. Και η μεγάλη O αντιπροσώπευε κάτι που νομίζαμε της ως άνω όριο. Και στην πραγματικότητα, Barry, μπορούμε να μειώσουμε από το μικρόφωνο λίγο; 

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

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

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

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

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

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

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

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

OK, γραμμική αναζήτηση. Και στη χειρότερη περίπτωση, όπου είναι η στοιχείο που ψάχνουν για το πότε εφαρμογής της γραμμικής αναζήτησης; 

OK, στη χειρότερη περίπτωση, δεν είναι καν εκεί. Ή στη δεύτερη χειρότερη περίπτωση, είναι όλο το δρόμο στο τέλος, το οποίο είναι συν ή πλην ενός σταδίου διαφορά. Έτσι, στο τέλος της ημέρας, μπορούμε να πούμε ότι είναι γραμμική. Big O Ν θα είναι γραμμική αναζήτηση, γιατί στη χειρότερη περίπτωση, η στοιχείο που δεν είναι ακόμα εκεί ή είναι όλο το δρόμο στο τέλος. 

Λοιπόν, μεγάλη O της καταγραφής των n. Εμείς δεν μιλάμε με μεγάλη λεπτομέρεια σχετικά με αυτό, αλλά έχουμε δει αυτό πριν. Τι τρέχει στο λεγόμενο λογαριθμική χρόνο, στη χειρότερη περίπτωση; 

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

Big O 1. Έτσι, θα μπορούσαμε μεγάλη O 2, μεγάλη O 3. Οποτεδήποτε θέλετε απλά ένα σταθερό αριθμό, έχουμε ακριβώς το είδος του απλά απλοποίηση ότι τόσο μεγάλη O 1. Ακόμα κι αν ρεαλιστικά, παίρνει 2 ή ακόμα και 100 μέτρα, αν είναι ένα σταθερό αριθμό βημάτων, απλά λέμε μεγάλα O 1. Τι είναι ένας αλγόριθμος που είναι σε μεγάλες O 1; 

ΚΟΙΝΟ: Η εύρεση του μήκους μιας μεταβλητής. 

DAVID MALAN: Ψάχνοντας το μήκος μιας μεταβλητής; 

ΚΟΙΝΟ: Όχι, το μήκος αν είναι ήδη ταξινομημένα. 

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

Αντίθετα, σκεφτείτε ότι πίσω σε μηδέν. Σκεφτείτε πίσω στην πρώτη εβδομάδα του C, καλώντας απλά printf και εκτύπωση κάτι στην οθόνη είναι αναμφισβήτητα σταθερό χρόνο, επειδή παίρνει μόνο κάποιο αριθμό κύκλων CPU για να δείξει ότι το κείμενο στην οθόνη. Ή περιμένετε - έτσι δεν είναι; Πώς αλλιώς θα μπορούσαμε να το μοντέλο του απόδοση της printf; Θα μπορούσε κάποιος ήθελε να διαφωνήσει, ότι ίσως δεν είναι πραγματικά σταθερό χρόνο; Με ποια λογική μπορεί να printf τρέχει χρόνο, εκτύπωση πραγματικά μια χορδή στο η οθόνη, είναι κάτι πλην σταθερή. 

ΚΟΙΝΟ: [δεν ακούγεται]. 

DAVID MALAN: Ναι. Γι 'αυτό εξαρτάται από την προοπτική μας. Αν θέλουμε πραγματικά να σκεφτούμε με τη συμβολή printf ως το string, και Συνεπώς μετράμε το μέγεθος του εν λόγω εισόδου από το μήκος του - οπότε ας την ονομάσουμε ότι το μήκος n, καθώς και - αναμφισβήτητα, printf είναι το ίδιο μεγάλη O Ν επειδή πρόκειται να σας πάρει n βήματα να εκτυπώσετε κάθε ένα από αυτά τα Ν χαρακτήρες, το πιο πιθανό. Τουλάχιστον στο βαθμό που υποθέτουμε ότι ίσως χρησιμοποιώντας ένα for loop κάτω από το καπό. 

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

Έτσι τι γίνεται με ωμέγα n τετράγωνο; Τι ήταν ένας αλγόριθμος που στην καλύτερη περίπτωση, ακόμα πήρε n τετράγωνο βήματα; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται]. 

DAVID MALAN: Μέχρι είδος επιλογής. Επειδή σε αυτό το πρόβλημα να μειωθούν πραγματικά το γεγονός ότι και πάλι, δεν ξέρω Έχω βρεθεί την τρέχουσα μικρότερο μέχρι Έχω ελέγξει όλες τις καταριέται στοιχεία. Έτσι, ωμέγα, ας πούμε, n, μόλις ήρθε με ένα. Ταξινόμηση με εισαγωγή. Εάν η λίστα συμβαίνει να διευθετηθεί ήδη, στην καλύτερη περίπτωση απλά πρέπει να κάνει ένα πέρασμα μέσα από αυτό, σημείο στο οποίο είμαστε σίγουροι. Και τότε αυτό θα μπορούσε να ειπωθεί να είναι γραμμική, αυτό είναι σίγουρο. 

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

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

Αυτό και μόνο, τέλος, ωμέγα n log n. Έτσι, n log n, δεν το κάναμε πραγματικά μιλάμε για ακόμα, αλλά - 

ΚΟΙΝΟ: Συγχώνευση είδους; 

DAVID MALAN: Συγχώνευση είδους. Αυτή ήταν η δραματική στιγμή του περασμένου χρόνου, όπου προτείναμε, και δείξαμε οπτικώς, ότι υπάρχουν αλγόριθμοι. Και να συγχωνεύσει το είδος ακριβώς ένα τέτοιο αλγόριθμο που είναι ουσιαστικά πιο γρήγορα από ό, τι μερικά από αυτά τα άλλα παιδιά. Στην πραγματικότητα, συγχώνευση βραχυκύκλωμα όχι μόνο στην καλύτερη περίπτωση n n log, στη χειρότερη περίπτωση n n log. Και όταν έχεις αυτή σύμπτωση Omega και η μεγάλη O είναι το ίδιο πράγμα; Μπορούμε να περιγράψουμε ότι στην πραγματικότητα και τι είναι ονομάζεται θήτα, αν και είναι μια λίγο λιγότερο συχνές. Αλλά αυτό σημαίνει ότι μόνο τα δύο όρια, στην περίπτωση αυτή, είναι τα ίδια. 

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

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

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

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

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

Έτσι, ας ρίξουμε μια ματιά στο τι συγχώνευση sort είναι πραγματικά όλα τα σχετικά. Το δροσερό πράγμα είναι ότι η συγχώνευση ταξινόμησης είναι μόνο αυτό. Αυτό είναι, και πάλι, αυτό που έχουμε ονομάσει ψευδοκώδικα, ψευδοκώδικα ον Αγγλικά-όπως σύνταξη. Και η απλότητα είναι είδος συναρπαστικό. 

Έτσι, στην είσοδο των n στοιχείων - έτσι ώστε να απλά σημαίνει, εδώ είναι μια σειρά. Είναι πήρε n πράγματα σε αυτό. Αυτό είναι το μόνο που λέμε εκεί. 

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

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

ΚΟΙΝΟ: [δεν ακούγεται]. 

DAVID MALAN: Ναι, ο αλγόριθμος διαλογή μου, δύο βήματα είναι "είδος κάτι. "Και έτσι που θέτει η ερώτημα, λοιπόν, τι θα πάω να χρησιμοποιήσει για να ταξινομήσετε το αριστερό μισό και το δεξί μισό; Και η ομορφιά εδώ είναι ότι ακόμη και αν και πάλι, αυτό είναι το μυαλό κάμψης μέρος δυνητικά, μπορείτε να χρησιμοποιήσετε το ίδιο αλγόριθμο για να ταξινομήσετε το αριστερό μισό. 

Αλλά περιμένετε ένα λεπτό. Όταν λένε να ταξινομήσετε αριστερό μισό, ποιες είναι οι δύο μέτρα πρόκειται να είναι το επόμενο βήμα; Θα λύσει το αριστερό μισό του αριστερό ήμισυ και το δικαίωμα το ήμισυ της αριστερό μισό. Γαμώτο, πώς μπορώ να ταξινομήσω τις δύο αυτές μισά ή τέταρτα, τώρα; 

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

Έτσι, η πραγματική μαγεία σε αυτό αλγόριθμος φαίνεται να είναι σε ότι το τελικό στάδιο, συγχώνευση. Αυτή η απλή ιδέα απλά τη συγχώνευση δύο τα πράγματα, αυτό είναι που τελικά θα για να μας επιτρέψει να λύσουμε μια σειρά από, ας πούμε, οκτώ στοιχεία. Έτσι έχω οκτώ μπάλες άγχος μέχρι εδώ, οκτώ κομμάτια χαρτί, και ένα Google Glass - την οποία έχω να κρατήσει. 

[Γέλια] 

DAVID MALAN: Αν θα μπορούσαμε να πάρουμε οκτώ εθελοντές, και ας δούμε αν μπορούμε να παίξετε αυτό έξω, έτσι. Πω πω, εντάξει. Η επιστήμη υπολογιστών είναι να πάρει τη διασκέδαση. Εντάξει. Πώς, λοιπόν, για εσάς τους τρεις, μεγαλύτερο χέρι μέχρι εκεί. Τέσσερις στο πίσω μέρος. Και σχετικά με το πώς θα κάνετε τρεις σε αυτή τη σειρά; Και τέσσερα στο μέτωπο. Έτσι, μπορείτε οκτώ, έλα πάνω. 

[Γέλια] 

DAVID MALAN: Είμαι πραγματικά δεν είναι σίγουρος τι είναι. Είναι οι μπάλες άγχος; Οι λάμπες γραφείου; Το υλικό; Το διαδίκτυο; 

OK. Έτσι, έλα επάνω. Ποιος θα ήθελε - εφεύρουν. Ας δούμε. Και αυτό σας βάζει στην θέση - είστε σε θέση ένα. Ωχ, περιμένετε ένα λεπτό. 1, 2, 3, 4, 5, 6, 7 - Α, ωραία. Εντάξει, είμαστε καλά. Εντάξει, έτσι ώστε όλοι να έχουν ένα κάθισμα, αλλά όχι για το γυαλί Google. Επιτρέψτε μου να περιμένω στην ουρά αυτά τα επάνω. Ποιο είναι το όνομά σου; 

MICHELLE: Michelle. 

DAVID MALAN: Michelle; Εντάξει, μπορείτε να πάρετε για να μοιάσει ο Έλληνας, αν αυτό είναι εντάξει. Λοιπόν, να κάνω εγώ, υποθέτω, για μια στιγμή. Εντάξει, σε κατάσταση αναμονής. Έχουμε προσπαθήσει να καταλήξει σε μια περίπτωση χρήσης για το Google Glass, και σκέφτηκα ότι θα ήταν διασκεδαστικό απλά για να κάνουμε αυτό, όταν οι άνθρωποι είναι στη σκηνή. Εμείς θα καταγράψει τον κόσμο από την πλευρά τους. Εντάξει. Δεν είναι ίσως ό, τι Google προορίζεται. Εντάξει, αν δεν σας πειράζει φορώντας Αυτό για τα επόμενα αδέξιο λεπτά, Αυτό θα ήταν υπέροχο. 

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

MICHELLE: Ω, αυτό είναι τόσο περίεργο. 

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

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

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

Έτσι, αν εσείς θα μπορούσε απλά να κρατήσει ψηλά σας αριθμών, ώστε να μπορούμε να δούμε ότι είστε πράγματι ταιριάζουν 4, 2, 6, 1, 3, 7, 8. Εξαιρετικό. Έτσι, Πάω να προσπαθήσουμε να ενορχηστρώσει τα πράγματα, αν εσείς μπορείτε απλά να ακολουθήσουν το παράδειγμά μου εδώ. 

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

ΚΟΙΝΟ: Ταξινομήστε το αριστερό μισό. 

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

ΚΟΙΝΟ: Ταξινομήστε το αριστερό μισό. 

DAVID MALAN: Ταξινομήστε το αριστερό μισό. Μέχρι τώρα αυτά, αυτή η θέση εδώ, είναι μια λίστα μεγέθους 1. Και τι είναι το όνομά σας και πάλι; 

PRINCESS DAISY: Πριγκίπισσα Μαργαρίτα. 

DAVID MALAN: Princess Daisy είναι εδώ. Και έτσι αυτή είναι ήδη ταξινομημένα, γιατί η λίστα έχει μέγεθος 1. Τι μπορώ να κάνω το επόμενο; OK, επιστροφή, γιατί ο κατάλογος είναι μεγέθους 1, η οποία είναι μικρότερη από 2. Τότε ποιο είναι το επόμενο βήμα; Και τώρα θα πρέπει να το είδος της υπαναχωρήσει στο μυαλό σας. 

Ταξινομήσετε το δεξί μισό, το οποίο είναι - ποιο είναι το όνομά σου; 

LINDA: Linda. 

DAVID MALAN: Linda. Και έτσι αυτό που κάνουμε τώρα που έχουμε μια λίστα με μέγεθος 1; 

Κοινό: Return. 

DAVID MALAN: Προσεκτική. Επιστρέφουμε πρώτη, και τώρα η τρίτη βήμα - και αν το είδος αυτό απεικονίζουν με αγκαλιάζει τις δύο έδρες που τώρα, τώρα Πρέπει να συγχωνεύσει αυτά τα δύο στοιχεία. Μέχρι τώρα, δυστυχώς, τα στοιχεία είναι εκτός λειτουργίας. Αλλά αυτό είναι όπου η διαδικασία συγχώνευσης αρχίζει να παίρνει συναρπαστικό. 

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

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

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

ΚΟΙΝΟ: Δεξί μισό. 

DAVID MALAN: Ταξινομήστε το δεξί μισό. Έτσι, εσείς έχετε να το κάνετε αυτό, όπως καλά. Έτσι, αν μπορούσε να σταθεί για μια στιγμή; Και ποιο είναι το όνομά σου; 

JESS: Jess. 

DAVID MALAN: Jess. ΕΝΤΑΞΕΙ, έτσι Jess είναι τώρα η αριστερά το ήμισυ της δεξί μισό. Και έτσι αυτή είναι μια λίστα με μέγεθος 1. Έχει προφανώς ταξινόμηση. Και το όνομά σας και πάλι; 

MICHELLE: Michelle. 

DAVID MALAN: Michelle είναι προφανώς μια λίστα με μέγεθος 1. Έχει ήδη ταξινομημένα. Έτσι τώρα η μαγεία συμβαίνει, η διαδικασία συγχώνευσης. Έτσι, ο οποίος πρόκειται να έρθει πρώτος; Προφανώς Michelle. Έτσι, αν μπορούσε να έρθει από πίσω. Ο χώρος που έχουμε στη διάθεσή μας γι 'αυτήν τώρα Είναι ακριβώς πίσω από αυτήν την καρέκλα εδώ. Και τώρα, αν θα μπορούσε να έρθει πίσω, καθώς, έχουμε τώρα, να είναι σαφής, δύο μισά, κάθε μεγέθους 2 - και μόνο για το καλό απεικόνιση του, αν θα μπορούσε να κάνει λίγο χώρο - ένα άφησε μισό εδώ, ένα δεξιό μισό εδώ. 

Rewind περαιτέρω στην ιστορία. Ποια βήμα είναι το επόμενο βήμα; 

Κοινό: Συγχώνευση. 

DAVID MALAN: Έτσι τώρα έχουμε να συγχωνευθούν. Έτσι, OK, έτσι και τώρα, ευτυχώς, μόλις ελευθερωθεί τέσσερις καρέκλες. Έτσι έχουμε χρησιμοποιήσει διπλάσια μνήμη, αλλά μπορούμε να δώσουμε flip-flopping μεταξύ οι δύο συστοιχίες. Έτσι, ο αριθμός των οποίων είναι να έρθει πρώτος; Έτσι, Michelle, προφανώς. Έτσι, έρχονται γύρω και να τη θέση σας εδώ. Και τότε ο αριθμός 2 είναι προφανώς επόμενη, έτσι ώστε να έρθει εδώ. Number 4, αριθμός 6. Και πάλι, ακόμα κι αν υπάρχει μια λίγο περπάτημα που εμπλέκονται, Πραγματικά, αυτές θα μπορούσε να συμβεί αμέσως, μετακινώντας ένα - Εντάξει, καλά έπαιξε. 

[Γέλια] 

DAVID MALAN: Και τώρα είμαστε σε αρκετά καλή κατάσταση. Το αριστερό ήμισυ του συνόλου εισόδου έχει πλέον ταξινομημένο. Εντάξει, έτσι ώστε αυτά τα παιδιά είχαν το πλεονέκτημα της μου - πώς να καταλήγουν όλα τα κορίτσια για την αριστερά και όλα τα αγόρια στα δεξιά; 

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

ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι ώστε από το Είμαι το αριστερό μισό της αριστερό μισό, επιστρέφω. Σωστά; 

DAVID MALAN: Good. 

ΟΜΙΛΗΤΗΣ 1: Και τότε - 

DAVID MALAN: Ποιος κάνει το μικρόφωνο πηγαίνετε στο επόμενο βήμα; 

ΟΜΙΛΗΤΗΣ 1: Επόμενη αριθμό. 

ΟΜΙΛΗΤΗΣ 2: Έτσι είμαι το δεξί μισό από το αριστερό μισό του αριστερό μισό, και θα επιστρέψω. 

DAVID MALAN: Good. Επιστρέφετε. Και τώρα τι είναι το επόμενο για εσάς τους δύο; 

ΟΜΙΛΗΤΗΣ 2: Θέλουμε να δούμε ποιος είναι μικρότερο. 

DAVID MALAN: Ακριβώς. Θέλουμε να συγχωνευθούν. Ο χώρος που πρόκειται να χρησιμοποιήσετε για τη συγχώνευση σας σε, έστω κι αν είναι προφανώς ταξινομούνται ήδη, θα πάμε να ακολουθούν τον ίδιο αλγόριθμο. Έτσι, ο οποίος πηγαίνει στην πλάτη πρώτα; Έτσι, 3, και, στη συνέχεια 7. Και τώρα το μικρόφωνο πηγαίνει σε αυτά τα παιδιά, εντάξει; 

ΟΜΙΛΗΤΗΣ 3: Έτσι είμαι το δεξί μισό της αριστερό ήμισυ, και το η μου είναι μικρότερη από ό, τι 1, οπότε είμαι απλώς πρόκειται να περάσει - 

DAVID MALAN: Good. 

ΟΜΙΛΗΤΗΣ 4: Είμαι το δεξί μισό της δεξί ήμισυ του δικαιώματος μισό, και είμαι Επίσης, ένα άτομο, έτσι είμαι πρόκειται να επιστρέψει. Έτσι τώρα έχουμε τη συγχώνευση. 

ΟΜΙΛΗΤΗΣ 3: Οπότε πάμε πίσω. 

DAVID MALAN: Έτσι, πηγαίνετε στο πίσω μέρος. Έτσι, 5 πηγαίνει πρώτα, στη συνέχεια, 8. Και τώρα το κοινό, το οποίο είναι το βήμα που έχουμε τώρα rewind πίσω στο μυαλό μας; 

Κοινό: Συγχώνευση. 

DAVID MALAN: Συγχώνευση αριστερό μισό και δεξιά το μισό του αρχικού αριστερό μισό. Έτσι τώρα - και μόνο για να γίνει αυτό σαφές, κάνει ένα μικρό κομμάτι του χώρου μεταξύ των δυο σας παιδιά. Έτσι, τώρα που είναι οι δύο λίστες, αριστερά και δεξιά. Επομένως, πώς μπορούμε πλέον να συγχωνεύονται σας παιδιά σε η πρώτη σειρά των καθισμάτων και πάλι; 

3 πηγαίνει πρώτα. Στη συνέχεια, 5, προφανώς. Στη συνέχεια, 7, 8 και τώρα. Εντάξει, και τώρα είμαστε; 

ΚΟΙΝΟ: Δεν έχει γίνει. 

DAVID MALAN: Δεν γίνεται, γιατί Προφανώς, υπάρχει ένα βήμα που απομένει. Αλλά και πάλι, ο λόγος που είμαι με τη χρήση αυτή φρασεολογία, όπως «rewind στο μυαλό σας," Είναι επειδή αυτό είναι πραγματικά τι συμβαίνει. Θα πάμε μέσα από όλα αυτά τα βήματα, αλλά είμαστε είδος σταματώντας για μια στιγμή, καταδύσεις βαθύτερα στην αλγόριθμο, σταματώντας για μια στιγμή, καταδύσεις βαθύτερα τον αλγόριθμο, και τώρα πρέπει να ταξινομήσετε του rewind σε μας μυαλό και θα ανατρέψει όλα αυτά τα στρώματα ότι έχουμε το είδος της τίθεται σε αναμονή. 

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

Έτσι βάλαμε Michelle εδώ. Και ποιος έχει τον αριθμό 2; Number 2 έρχεται στην πλάτη, καθώς και. Αριθμός 3; Εξαιρετικό. Number 4, τον αριθμό 5, τον αριθμό 6, αριθμό 7, και τον αριθμό 8. 

Εντάξει, έτσι ένιωσα σαν μια παρτίδα βημάτων, αυτό είναι σίγουρο. Αλλά τώρα ας δούμε αν δεν μπορούμε να επιβεβαιώσουμε είδος διαισθητικά ότι αυτό αλγόριθμος ουσιαστικά, ιδίως όσον n παίρνει πραγματικά μεγάλη, όπως έχουμε δει με τα κινούμενα σχέδια, είναι ριζικά πιο γρήγορα. Γι 'αυτό και υποστηρίζουν αυτόν τον αλγόριθμο, στη χειρότερη περίπτωση, ακόμα και στην καλύτερη περίπτωση, είναι μεγάλη O Ν φορές log n. Δηλαδή, υπάρχει κάποια πτυχή αυτής της αλγόριθμο που λαμβάνει n βήματα, αλλά υπάρχει και μια άλλη πτυχή κάπου στο ότι η επανάληψη, η looping, ότι λαμβάνει log n βήματα. Μπορούμε να βάλει το δάχτυλό μας για το τι αυτές δύο αριθμούς αναφέρεστε; Λοιπόν, όπου - Πώς Ξεκίνησε το μικρόφωνο πάτε; 

ΟΜΙΛΗΤΗΣ 1: Θα μπορούσε η log n είναι σπάσιμο μας σε δύο - διαιρώντας με δύο, κατ 'ουσίαν. 

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

Τώρα τι γίνεται με το n; Βλέπω ότι έχουμε το είδος της που διαιρείται παιδιά - διαιρείται σας, διαιρείται, διαιρείται σας, διαιρείται. Πού το τέλος προέρχονται από; 

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

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

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

Και γιατί είναι αυτό το καλύτερο; Λοιπόν, αν γνωρίζουμε ήδη ότι το ημερολόγιο n είναι καλύτερη από n - έτσι δεν είναι; Είδαμε σε δυαδική αναζήτηση, τον τηλεφωνικό κατάλογο παράδειγμα, log n ήταν σίγουρα καλύτερη από τη γραμμική. Έτσι, αυτό σημαίνει ότι n log n φορές είναι σίγουρα καλύτερα από ό, τι n φορές ένα άλλο n, AKA n τετράγωνο. Και αυτό είναι που τελικά αισθάνονται. 

Έτσι, μεγάλο χειροκρότημα, αν θα μπορούσαμε, για αυτά τα παιδιά. 

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

DAVID MALAN: Και τα δώρα χωρίστρα σας - μπορεί να κρατήσει τους αριθμούς, εάν θα θέλατε. Και δώρο χωρίστρα σας, ως συνήθως. Ω, και εμείς θα σας στείλουμε το υλικό, Michelle. Σας ευχαριστώ. Εντάξει. Βοηθήστε τον εαυτό σας σε μια μπάλα για το άγχος. 

Και επιτρέψτε μου να σηκώσει, εν τω μεταξύ, φίλος μας Rob Bowden να προσφέρει κάπως διαφορετική άποψη για το θέμα αυτό, δεδομένου ότι μπορείτε να σκεφτείτε αυτές τις βήματα που συμβαίνουν σε μια κάπως διαφορετικό τρόπο. Στην πραγματικότητα, το set-up για το τι Rob είναι περίπου για να μας δείξει υποθέτει ότι έχουμε έχει ήδη γίνει η διαίρεση της μεγάλη λίστα σε οκτώ μικρούς καταλόγους, κάθε μεγέθους 1. 

Έτσι, αλλάζουμε το pseudocode ένα λίγο μόνο για να ταξινομήσετε του πάρει το βασική ιδέα για το πώς η συγχώνευση έργων. Αλλά ο χρόνος εκτέλεσης του τι είναι έτοιμος να κάνει είναι ακόμα πρόκειται να είναι το ίδιο. Και πάλι, το set-up εδώ είναι ότι αυτός είναι ξεκίνησε με οκτώ καταλόγους του μεγέθους 1. Έτσι, έχετε χάσει το μέρος όπου αυτός είναι πραγματικά κάνει το log n, n log, log n διαίρεση της εισόδου. 

[PLAYBACK VIDEO] 

-Γι 'αυτό για ένα βήμα. Για το βήμα δύο, κατ 'επανάληψη συγχώνευση ζεύγη των καταλόγων. 

DAVID MALAN: Χμ. Μόνο ήχος έρχεται από τον υπολογιστή μου. Ας δοκιμάσουμε ξανά. 

-Απλά επιλέξτε αυθαίρετα η οποία - τώρα έχουμε τέσσερις λίστες. Μάθετε πριν. 

DAVID MALAN: Εκεί πάμε. 

-Συγχώνευση 108 και 15, καταλήγουμε με τον κατάλογο 15, 108. Συγχωνευόμενες 50 και 4, μπορούμε καταλήξετε με 4, 50. Συγχώνευση 8 και 42, θα καταλήξετε με 8, 42. Και τη συγχώνευση 23 και 16 ετών, καταλήγουν με 16, 23. 

Τώρα, όλες τις λίστες μας έχουν μέγεθος 2. Παρατηρήστε ότι κάθε μία από τις τέσσερις λίστες είναι ταξινομημένο. Έτσι, μπορούμε να αρχίσουμε τη συγχώνευση ζεύγη των καταλόγων και πάλι. Συγχωνευόμενες 15 και 108 και 4, και 50, έχουμε πρώτα να πάρετε το 4, τότε το 15, τότε το 50, τότε το 108. Συγχώνευση 8, 42 και 16, 23, πρέπει πρώτα να το 8, τότε το 16, τότε το 23, τότε το 42. 

Έτσι τώρα έχουμε μόλις δύο λίστες του μεγέθους 4, καθένα από τα οποία είναι ταξινομημένο. Έτσι τώρα έχουμε ενώσει τις δύο λίστες. Πρώτον, παίρνουμε το 4, τότε παίρνουμε το 8, τότε θα πάρει το 15, τότε 16, τότε 23, στη συνέχεια 42, και στη συνέχεια 50, τότε 108. 

[PLAYBACK VIDEO END] 

DAVID MALAN: Και πάλι, ανακοίνωση, ποτέ δεν άγγιξε μια δεδομένη κύπελλο περισσότερες από μία φορά μετά προχωρεί πέρα ​​από αυτό. Έτσι, ο ίδιος ποτέ δεν επαναλαμβάνεται. Έτσι, αυτός είναι πάντα σε κίνηση προς την πλευρά της, και εκεί είναι που πήραμε n μας. 

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

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

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

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

Αυτό είναι το είδος εισαγωγής. 

[ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 

DAVID MALAN: Είναι και πάλι προσπαθεί για να εισάγετε κάθε στοιχείο στην οποία ανήκει. Αυτό είναι το είδος φούσκα. 

[ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 

DAVID MALAN: Και μπορείτε να ταξινομήσετε του αίσθηση Πώς σχετικά λίγη δουλειά να κάνει σε κάθε βήμα. Αυτό είναι ό, τι μονοτονία ακούγεται. 

[ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 

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

[ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 

DAVID MALAN: Αυτό είναι το είδος συγχώνευσης, η οποία μπορείτε πραγματικά να αρχίσετε να αισθάνεστε. 

[ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 

[Γέλια] 

DAVID MALAN: Κάτι που ονομάζεται gnome ταξινόμησης, το οποίο δεν έχουμε κοίταξε. 

[ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 

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

Και πάλι, υπενθυμίζουν ότι το είδος συγχώνευσης pseudocode ήταν επαναληπτικό με την έννοια ότι ένα από τα βήματα της συγχώνευσης είδους ήταν να καλέσει είδος - δηλαδή, η ίδια. Αλλά ευτυχώς, γιατί διατηρήσαμε καλώντας το είδος, ή να συγχωνευθούν είδος, Συγκεκριμένα, για ένα όλο και μικρότερο και μικρότερη λίστα, που τελικά έφθασε στο απόγειό της χάρη σε αυτό θα καλέσουμε μία βασική περίπτωση, το hard-coded περίπτωση που είπε πως αν η λίστα είναι μικρή, μικρότερη από 2 Στην περίπτωση αυτή, μόλις επιστρέψει αμέσως. Αν δεν είχαμε αυτό το ειδική περίπτωση, η αλγόριθμος ποτέ δεν θα ανακάμπτουν, και πράγματι θα μπει σε μια άπειρο βρόχο πραγματικά για πάντα. 

Αλλά ας υποθέσουμε ότι θέλαμε να θέσει τώρα ορισμένοι αριθμοί σε αυτό, και πάλι, με τη χρήση Ν όπως το μέγεθος της εισόδου. Και ήθελα να σας ρωτήσω, τι είναι ο συνολικός χρόνος που εμπλέκονται στην τρέχει είδος συγχώνευσης; Ή, γενικότερα, τι είναι το κόστος του στο χρόνο; 

Λοιπόν, είναι αρκετά εύκολο να μετρηθεί αυτό. Εάν n είναι μικρότερη από 2, ο χρόνος που εμπλέκονται στη διαλογή n στοιχεία, όπου το η είναι 2, το η είναι 0. Επειδή ακριβώς επιστρέψει. Δεν υπάρχει δουλειά να γίνει. Τώρα, αναμφισβήτητα, ίσως είναι ένα βήμα ή δύο βήματα για να υπολογίσει το ποσό των εργασία, αλλά είναι αρκετά κοντά στο 0 που Είμαι ακριβώς πρόκειται να πω καμιά εργασία δεν απαιτείται αν ο κατάλογος είναι τόσο μικρή να πληκτικός. 

Αλλά αυτή η περίπτωση είναι ενδιαφέρουσα. Η αναδρομική περίπτωση ήταν ο κλάδος της ψευδοκώδικα που είπε άλλο, το είδος το αριστερό μισό, να ταξινομήσετε το δικαίωμα μισό, να συγχωνεύσει τα δύο μισά. Τώρα γιατί το κάνει αυτό έκφραση εκπροσωπεί το εν λόγω δαπάνη; Λοιπόν, Τ n σημαίνει ότι μόνο η χρόνο για να ταξινομήσετε n στοιχεία. Και στη συνέχεια στη δεξιά πλευρά του ίσον εκεί, το Τ n διαιρείται κατά 2 αναφέρεται στο κόστος του τι; Διαλογή το αριστερό μισό. Το άλλο Τ του n διαιρείται με 2 είναι προφανώς αναφερόμενος στο κόστος ταξινομήσετε το δεξί μισό. 

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

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

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

Αλλά και πάλι, αυτό δεν είναι αρκετό. Πρέπει να βουτήξει στα βαθιά. Αυτό σημαίνει ότι πρέπει να απαντήσει η ερώτημα, ποια είναι η T 8; Καλά T από 8 απέχει μόλις 2 φορές T 4 συν 8. Λοιπόν, ποια είναι η T 4; T 4 είναι μόλις 2 φορές T από 2 συν 4. Λοιπόν, τι είναι Τ 2; T 2 είναι μόλις 2 φορές T 1 συν 2. 

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

Αν T 1 είναι 0, μπορώ τώρα να πάει πίσω μέχρι ένα γραμμή σε αυτόν τον άνθρωπο εδώ και μπορώ να plug in για 0 ​​T 1. Έτσι, αυτό σημαίνει ότι ισούται με 2 φορές το μηδέν, αλλιώς γνωστή ως μηδέν, συν 2. Και έτσι ώστε όλη η έκφραση είναι 2. 

Τώρα, αν θα πάρει το Τ 2, του οποίου η απάντηση είναι 2, συνδέστε το στη μεσαία γραμμή, T 4, αυτό μου δίνει 2 φορές 2 συν 4, έτσι 8. Αν ήμουν στη συνέχεια, συνδέστε σε 8 με το προηγούμενο γραμμή, αυτό μου δίνει 2 φορές 8, 16. Και αν συνεχίσουμε τότε ότι με την 24, προσθέτοντας στο 16, θα έχουμε επιτέλους μια αξία 64. 

Τώρα που και αυτή η ίδια είδους μιλάει τίποτα στη σημειογραφία n, η O μεγάλος, τα ωμέγα που έχουμε μιλήσει. Αλλά αποδεικνύεται ότι το 64 είναι πράγματι 16, το μέγεθος της εισόδου, συνδεθείτε βάσης 2 από 16. Και αν αυτό είναι λίγο άγνωστη, απλά σκεφτείτε πίσω, και θα επανέλθω να σας τελικά. Αν αυτή είναι η log βάσης 2, είναι σαν 2 έθεσε στο τι σας δίνει 16; Ω, αυτό είναι 4, οπότε είναι 16 φορές 4. 

Και πάλι, δεν είναι μια μεγάλη υπόθεση, αν αυτό Είναι το είδος του ένα θολό μνήμης τώρα. Αλλά για τώρα, να αναλάβει την πίστη ότι το 16 log 16 είναι 64. Και έτσι, πράγματι, με αυτή την απλή λογική ελέγχει, έχουμε επιβεβαιώσει - αλλά δεν αποδείχθηκε επισήμως - ότι ο χρόνος εκτέλεσης της συγχώνευσης ταξινόμησης είναι πράγματι n log n. 

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

Τώρα, ένα διασκεδαστικό λίγο άσκηση, αν έχετε ποτέ δεν κάνει αυτό - και ίσως δεν θα έχει, επειδή το είδος της κανονικής οι άνθρωποι δεν σκέφτονται να το κάνουν αυτό. Αλλά αν πάω στο google.com και αν Θέλω να μάθω κάτι για αναδρομή, Enter. 

[Γέλια] [Περισσότερο γέλιο] DAVID MALAN: κακόγουστο αστείο εξαπλώνεται σιγά-σιγά. [Γέλια] DAVID MALAN: Ακριβώς σε περίπτωση, είναι εκεί. Εγώ δεν σημάνει λάθος, και υπάρχει το αστείο. Εντάξει. Εξηγήστε στο λαό δίπλα σας, αν δεν έχει αρκετά κλικ ακριβώς ακόμα. Αλλά αναδρομή, γενικότερα, αναφέρεται με τη μέθοδο της μιας συνάρτησης καλώντας μόνη της, ή, γενικότερα, τη διαίρεση πρόβλημα σε κάτι που μπορεί να είναι λυθεί αποσπασματικά με την επίλυση πανομοιότυπα προβλήματα εκπροσώπου. 

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

Επομένως, πώς θα πάει για να κάνει αυτό; Λοιπόν, επιτρέψτε μου να πάει μπροστά και να γράφουν ένα γρήγορο πρόγραμμα εδώ. Πάω να πάει μπροστά και να κάνουμε αυτό ως εξής. Ας το ονομάσουμε αυτό - τι θέλουμε να καλέσετε αυτό; 

Στην πραγματικότητα, όχι. Επιτρέψτε μου προς τα πίσω. Δεν θέλω να το κάνω αυτό Cliffhanger ακόμα. Θα χαλάσουμε τη διασκέδαση. Ας το κάνουμε αντ 'αυτού. 

Ας υποθέσουμε ότι θέλω να γράψω ένα μικρό του προγράμματος και ότι αγκαλιάζει τώρα αυτό ιδέα της αναδρομής. Ι το είδος του πήρε μπροστά από τον εαυτό μου εκεί. Πάω να κάνετε τα εξής. 

Πρώτον, μια γρήγορη περιλαμβάνουν τυποποιημένων io.h, καθώς και περιλαμβάνουν από cs50.h. Και τότε Πάω να πάει μπροστά και να κηρύξει άκυρη int main κατά τον συνήθη τρόπο. Συνειδητοποίησα ότι έχω misnamed το αρχείο, έτσι ώστε επιτρέψτε μου να προσθέσω μόνο μια επέκταση. c εδώ τόσο ότι μπορούμε να το υπολογίσουν σωστά. Ξεκινήστε αυτή τη λειτουργία. 

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

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

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

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

Δυστυχώς, ακόμη και αν σίγμα ακούγεται σαν κάτι που μπορεί να είναι σε το αρχείο math.h, δήλωση, στην πραγματικότητα δεν είναι. Έτσι, αυτό είναι εντάξει. Μπορώ να εφαρμόσει τον εαυτό μου αυτό. Πάω να εφαρμόσουν μια λειτουργία που ονομάζεται σίγμα, και πρόκειται να λάβει ένα παράμετρος - ας το ονομάσουμε m, απλά γι 'αυτό είναι διαφορετικό. Και στη συνέχεια, μέχρι εδώ, θα πάω να πω, Λοιπόν, αν το m είναι μικρότερο από 1 - αυτό είναι ένα πολύ πληκτικός πρόγραμμα. Έτσι, Πάω να προχωρήσει και επιστρέψει αμέσως 0. Απλώς δεν έχει νόημα να προσθέσουμε όλα οι αριθμοί μεταξύ 1 και m, εάν m είναι η ίδια μηδέν ή αρνητική. 

Και τότε Πάω να πάει μπροστά και να το κάνουμε αυτό πολύ επαναληπτικά. Πάω να κάνω αυτό το είδος της παλιάς σχολής, και θα πάω να προχωρήσει και να πω ότι είμαι πρόκειται να δηλώνει ένα ποσό να είναι 0. Στη συνέχεια, Πάω να έχουν βρόχο for της int - και επιτρέψτε μου να το κάνει να ταιριάζει με μας Κώδικα Διαχείρισης του Δικτύου, έτσι ώστε να έχετε ένα αντίγραφο στο σπίτι. int i παίρνει 1 μέχρι και σε Ι είναι μικρότερο ή ίσο με m. i plus plus. Και τότε μέσα από αυτό για loop - είμαστε σχεδόν εκεί - άθροισμα παίρνει ποσού συν 1. Και τότε Πάω να επιστρέψει το ποσό. 

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

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

Και τώρα αρχίζουν να κινούνται από το i ισούται 1 σε όλη τη διαδρομή μέχρι και m, γιατί θέλω να περιλαμβάνει όλα τα αριθμούς από το ένα μέχρι m, χωρίς αποκλεισμούς. Και μέσα από αυτό για το βρόχο, εγώ απλά κάνω ποσό που παίρνει ό, τι είναι τώρα, συν το τιμή του i. Πλέον η τιμή του i. 

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

Δυστυχώς, αυτός ο κώδικας του δεν πρόκειται να συγκεντρώνουν ακόμα. Αν τρέξω να sigma 0, πώς am Ι που πηγαίνει να πάρει φώναξε; Τι είναι αυτό που πηγαίνει να μην αρέσει; 

ΚΟΙΝΟ: [δεν ακούγεται]. 

DAVID MALAN: Ναι, δεν είχα δηλώσει η λειτουργία επάνω στην κορυφή, έτσι δεν είναι; C είναι ηλίθια, υπό την έννοια ότι μόνο κάνει ό, τι σας πει να κάνετε, και εσείς πρέπει να το κάνουμε με αυτή τη σειρά. Και έτσι, αν πατήσω το enter εδώ, Πάω να πάρετε μια προειδοποίηση σχετικά με σίγμα σιωπηρή δήλωση. 

Ω, δεν είναι πρόβλημα. Μπορώ να πάω μέχρι την κορυφή, και μπορώ πω, εντάξει, περιμένετε ένα λεπτό. Sigma είναι μια συνάρτηση που επιστρέφει μια int και αναμένει μια int ως είσοδο, ερωτηματικό. Ή θα μπορούσε να θέσει την όλη λειτουργία πάνω από την κύρια, αλλά σε γενικές γραμμές, θα ήθελα να συνιστά ενάντια σε αυτό, γιατί είναι ωραίο να έχουμε πάντα το κύριο στην κορυφή, έτσι Μπορείτε να μπείτε μέσα και να γνωρίζει τι είναι πρόγραμμα κάνει με την ανάγνωση κύριο πρώτα. 

Έτσι, τώρα επιτρέψτε μου να καθαρίσετε την οθόνη. Remake σίγμα 0. Όλα φαίνεται να ελέγξετε έξω. Επιτρέψτε μου να τρέξει sigma 0. Θετική μεταξύ. Θα του δώσω τον αριθμό 3 να το κρατήσετε απλό. Έτσι, αυτό θα πρέπει να μου δώσει 3 συν 2 συν 1, έτσι ώστε 6. Enter, και μάλιστα παίρνω 6. 

Μπορώ να κάνω κάτι μεγαλύτερο - 50, 12, 75. Ακριβώς όπως μια εφαπτομένη, Πάω να κάνω κάτι γελοίο σαν ένα πραγματικά μεγάλο αριθμό, Ω, που πραγματικά εργάστηκαν out - eh, δεν νομίζω ότι αυτό είναι σωστό. Ας δούμε. Ας πραγματικά με αυτό το χάλι. 

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

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

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

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

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

Έτσι είμαι πραγματικά - επιτρέψτε μου να αποθηκεύσετε αυτό το αρχείο με διαφορετικό αριθμό έκδοσης. Θα το ονομάσουμε έκδοση 1 αντί για 0. Και εγώ ισχυρίζομαι ότι μπορώ πραγματικά να Νέα υλοποίηση αυτή σε αυτό το είδος της μυαλό κάμψης τρόπο. 

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

Αλλιώς - παρατηρήσετε τι Πάω να κάνουμε. Αλλιώς εγώ είμαι πρόκειται να επιστρέψει m συν - τι είναι σίγμα του m; Λοιπόν, ΣΙΓΜΑ m συν m μείον 1, m συν πλην 2, συν m μείον 3. Δεν θέλω να γράψω όλα αυτά έξω. Γιατί δεν μπορώ απλά punt; Αναδρομικά ονομάζω τον εαυτό μου με ένα ελαφρώς μικρότερο πρόβλημα, ερωτηματικό, και να το ονομάσουμε την ημέρα; 

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

ΚΟΙΝΟ: [δεν ακούγεται]. 

DAVID MALAN: 23 έως 26, οι οποίες είναι αν η κατάστασή μου. Γιατί ό, τι είναι καλό για το αφαίρεση εδώ, γιατί έχω κρατήσει παράδοση σίγμα μικρότερα προβλήματα, μικρότερα προβλήματα, μικρότερα - δεν είναι το μισό μέγεθος. Είναι μόνο ένα μικρό βήμα μικρότερο, αλλά αυτό είναι εντάξει. Διότι τελικά, θα λειτουργήσει δρόμο μας μέχρι 1 ή 0. Και από τη στιγμή που χτύπησε 0, Sigma δεν είναι πρόκειται να αυτοαποκαλείται πια. Είναι πρόκειται να επιστρέψει αμέσως 0. 

Έτσι, το αποτέλεσμα, αν το είδος του ανέμου αυτό στο μυαλό σας, είναι να προσθέσετε m συν m μείον 1, συν πλην 2 m, συν m μείον 3, καθώς και τελεία, τελεία, τελεία, m μείον m, τελικά, δίνοντας σας 0, και η αποτέλεσμα είναι τελικά να προσθέσετε όλα αυτά τα πράγματα μαζί. Έτσι, δεν έχουμε, με αναδρομή, λυθεί το πρόβλημα που δεν θα μπορούσε να λύσει πριν. Πράγματι, 0 εκδοχή αυτή, και κάθε πρόβλημα μέχρι σήμερα, έχει επιλύσιμο με τη χρήση μόνο για βρόχους ή ενώ βρόχους ή παρόμοια κατασκευάσματα. 

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

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

Έτσι, αυτό είναι μια ηλίθια μικρό πρόγραμμα που I χτυπημένη ότι οι απαιτήσεις να κάνουν η ακόλουθη. Σε γενικές γραμμές, δηλώνει για πρώτη φορά ένα int ονομάζεται x και εκχωρεί η τιμή του 1. Στη συνέχεια, δηλώνει ένα int y και εκχωρεί την τιμή 2. Στη συνέχεια εκτυπώνει τι x και y είναι. Στη συνέχεια, λέει, εναλλαγή, dot dot dot. 

Στη συνέχεια, ισχυρίζεται ότι είναι καλώντας μια συνάρτηση ονομάζεται swap, περνώντας x και y, η ιδέα της οποίας είναι ότι ελπίζουμε x και y θα επανέλθει διαφορετικά, το αντίθετο. Στη συνέχεια, ισχυρίζονται αντάλλαξαν! με ένα θαυμαστικό. Στη συνέχεια εκτυπώνει x και y. 

Αλλά αποδεικνύεται ότι αυτή η πολύ απλή επίδειξη κάτω εδώ είναι πραγματικά λάθη. Ακόμα κι αν είμαι με την οποία μια προσωρινή μεταβλητή και προσωρινά, βάζοντας ένα σε αυτό, τότε είμαι ανακατανομή μια τιμή η της β - η οποία αισθάνεται λογικό, γιατί έχω αποθηκεύσει ένα αντίγραφο της στο temp. Τότε μπορώ να ενημερώσω το b για ίση Όποια και αν ήταν στο temp. Αυτό το είδος του παιχνιδιού κελύφους κινείται ένα σε b και Β σε ένα χρησιμοποιώντας αυτό μεσαία-man όνομα temp αισθάνεται απολύτως λογικό. 

Αλλά εγώ ισχυρίζομαι ότι όταν τρέχω κώδικα, όπως θα κάνω τώρα - επιτρέψτε μου να πάω μπροστά και να το επικολλήσετε στο εδώ. Θα πάρω αυτό το noswap.c. Και όπως υποδηλώνει το όνομα, αυτό δεν είναι πρόκειται να είναι ένα σωστό πρόγραμμα. Κάντε noswap. / Όχι swap. x είναι 1, y είναι 2, swapping, ανταλλαχθούν. το χ είναι 1, το Υ είναι 2. Αυτό είναι εντελώς λάθος, ακόμα και αν και αυτό φαίνεται απόλυτα λογικό για μένα. Και υπάρχει ένας λόγος, αλλά δεν είμαστε πρόκειται να αποκαλύψει το λόγο ακριβώς ακόμα. 

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

Δυστυχώς, νομίζω ότι τις οδηγίες μου δεν έχουν, μέχρι σήμερα, πολύ σαφής, έτσι ώστε Πήγα πίσω αυτό το Σαββατοκύριακο και να ενημερώνονται το spec σε μεγαλύτερες, πιο τολμηρή κείμενο εξηγήσει σφαίρες σαν αυτές. Και απλά για να το πω πιο κοινό, με προεπιλογή, προβλήματα οφείλονται Πέμπτη το μεσημέρι, σύμφωνα με το αναλυτικό πρόγραμμα. Αν ξεκινήσετε νωρίς, τερματίζοντας μέρος του το πρόβλημα που μέχρι την Τετάρτη στις 12:00 PM, το μέρος που σχετίζεται με ένα κουπόνι κώδικα, η ιδέα είναι ότι μπορείτε να επεκτείνετε προθεσμία σας για το P που μέχρι την Παρασκευή. Δηλαδή, δάγκωσε ένα μικρό μέρος του P που σε σχέση με ό, τι συνήθως είναι η μεγαλύτερο πρόβλημα, και να αγοράσετε τον εαυτό σας μια επιπλέον ημέρα. Και πάλι, σας παίρνει να σκεφτόμαστε το σύνολο πρόβλημα, σας παίρνει να ώρες γραφείου νωρίτερα. Αλλά το πρόβλημα κωδικό κουπονιού είναι ακόμα απαιτείται, ακόμα κι αν δεν την υποβάλει. 

Αλλά πιο συναρπαστικά είναι αυτό. (Θεατρικός μονόλογος) Και εκείνοι οι λαοί αφήνοντας νωρίς είναι θα το μετανιώσετε. Δεδομένου ότι οι λαοί στο μπαλκόνι. Ζητώ συγγνώμη εκ των προτέρων για τους λαούς για το μπαλκόνι για λόγους που θα σαφές ακριβώς σε μια στιγμή. 

Έτσι, είμαστε τυχεροί να έχουμε ένα από τα Πρώην υποτρόφων διδασκαλίας CS50 το κεφάλι σε μια εταιρεία που ονομάζεται dropbox.com. Έχουν πολύ γενναιόδωρα δώρισε κωδικό κουπονιού εδώ γι 'αυτό το πολύ χώρο, η οποία είναι πάνω από το συνήθως 2 gigabytes. Έτσι, αυτό που νόμιζα ότι θα κάνουμε σε αυτό τελευταία σημείωση είναι να κάνετε ένα κομμάτι από ένα giveaway, σύμφωνα με την οποία σε μια στιγμή, θα αποκαλύψει ο νικητής και ποιος έχει ένα κουπόνι κώδικα που τότε μπορείτε να πάτε για να τους ιστοσελίδα, πληκτρολογήστε, και voila, έχετε ένα πάρα πολύ περισσότερο χώρο για το Dropbox σας συσκευή και για τα προσωπικά σας αρχεία. 

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

[PLAYBACK VIDEO] 

Ένα, δύο, τρία. 

[Ουρλιάζει] 

-Μπορείτε να πάρετε ένα αυτοκίνητο! Μπορείτε να πάρετε ένα αυτοκίνητο! 

DAVID MALAN: Θα δούμε σας την Τετάρτη. 

-Μπορείτε να πάρετε ένα αυτοκίνητο! Μπορείτε να πάρετε ένα αυτοκίνητο! Μπορείτε να πάρετε ένα αυτοκίνητο! Μπορείτε να πάρετε ένα αυτοκίνητο! Μπορείτε να πάρετε ένα αυτοκίνητο! 

DAVID MALAN: λαοί Μπαλκόνι, έρχονται εδώ κάτω προς τα εμπρός, όπου έχουμε extras. 

-Ο καθένας παίρνει ένα αυτοκίνητο! Ο καθένας παίρνει ένα αυτοκίνητο! 

[PLAYBACK VIDEO END] 

Αφηγητής: Στο επόμενο CS50 - 

ΟΜΙΛΗΤΗΣ 5: Θεέ μου Θεέ Θεέ Θεέ Θεέ μου θεέ μου θεέ μου θεέ μου θεέ μου θεέ μου - 

[ΘΕΑΤΡΙΚΑ UKELELE]