[Παίζει μουσική] 

ΚΑΘΗΓΗΤΗΣ: Εντάξει. Αυτό είναι CS50 και αυτό είναι το τέλος τριών εβδομάδων. Έτσι, είμαστε εδώ σήμερα, δεν είναι σε Sanders Θέατρο, αντί σε Weidner Βιβλιοθήκη. Εντός του οποίου υπάρχει ένα στούντιο γνωστή ως Hauser Studio, ή ας πούμε Studio H, ή θα εμείς say-- Αν σας άρεσε αυτό το αστείο, Είναι πραγματικά από συμμαθητής του, Μαρκ, σε απευθείας σύνδεση, ο οποίος πρότεινε τόσο μέσω του Twitter. Τώρα τι είναι δροσερό για είναι εδώ σε ένα στούντιο είναι ότι είμαι περιβάλλεται από αυτές τις πράσινες τοίχοι, μια πράσινη οθόνη ή chromakey, να το πω έτσι, πράγμα που σημαίνει ότι το CS50 Η ομάδα παραγωγής, εν αγνοία μου αυτή τη στιγμή, θα μπορούσε να είναι βάζοντας με πιο οπουδήποτε στον κόσμο, προς το καλύτερο ή προς το χειρότερο. 

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

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

Προς το παρόν Υπενθυμίζουμε ότι νωρίτερα αυτή την εβδομάδα είχαμε αυτή τη δραματική στιγμή, αν θέλετε, οπότε το καλύτερο που κάναμε διαλογής σοφός ήταν ένα άνω φράγμα των μεγάλων o Ν τετράγωνο. Με άλλα λόγια, bubble sort, ταξινόμηση με επιλογή, ταξινόμηση με εισαγωγή, όλα αυτά, ενώ οι διαφορετικές κατά την εφαρμογή τους, ανατίθεται σε ένα τετράγωνο n τρέχει φορά στην πολύ χειρότερη περίπτωση. Και γενικά να υποθέσουμε ότι η ίδια η χειρότερη περίπτωση για τη διαλογή είναι αυτή που εισόδους σας είναι τελείως προς τα πίσω. Και πράγματι, χρειάστηκαν αρκετά βήματα να εφαρμόσει κάθε ένα από αυτά αλγορίθμων. 

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

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

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

Τώρα ρίξτε μια ματιά στο συγκεκριμένο στη γραμμή 7 και 8, και 10 και 11, που επάγουν αυτό το βρόχο, σύμφωνα με την οποία διατηρήσαμε πηγαίνει πίσω στη γραμμή 3 ξανά, και ξανά, και πάλι. Αλλά αποδεικνύεται ότι μπορούμε να δείτε Αυτός ο αλγόριθμος, εδώ σε ψευδοκώδικα, λίγο πιο ολιστικά. Στην πραγματικότητα, αυτό που ψάχνω στο εδώ στην οθόνη, είναι ένας αλγόριθμος για την αναζήτηση Ο Mike Smith ανάμεσα σε κάποιο σύνολο σελίδων. Και πράγματι, θα μπορούσε να απλουστευθεί αυτή αλγόριθμος σε αυτές τις γραμμές 7 και 8, και 10 και 11 να πω μόνο αυτό, την οποία έχω εδώ παρουσιάζονται με κίτρινο χρώμα. Με άλλα λόγια, αν ο Mike Smith είναι νωρίτερα στο βιβλίο, δεν χρειάζεται να καθορίσετε το βήμα από το βήμα τώρα πώς να πάει να τον βρει. Δεν έχουμε να καθορίσετε να επιστρέψει στη γραμμή 3, γιατί να μην το κάνουμε εμείς απλά αντ 'αυτού, ας πούμε, γενικότερα, αναζήτηση Mike στο αριστερό μισό του βιβλίου. 

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

Έτσι σας δίνω ταξινόμηση με συγχώνευση. Ας ρίξουμε μια ματιά. Έτσι, εδώ είναι ψευδοκώδικας, με η οποία θα μπορούσε να εφαρμόσει τη διαλογή, χρησιμοποιώντας αυτόν τον αλγόριθμο που ονομάζεται ταξινόμηση με συγχώνευση. Και είναι πολύ απλά αυτό. Την είσοδο του n στοιχεία, Με άλλα λόγια, αν είστε δεδομένο n στοιχεία και αριθμούς και γράμματα ή ό, τι η είσοδος είναι, αν δοθεί n στοιχεία, εάν n είναι μικρότερη από 2, μόλις επιστρέψει. Σωστά; Διότι εάν το η είναι μικρότερο από 2, ότι σημαίνει ότι η λίστα μου με τα στοιχεία είναι είτε 0 ή μεγέθους 1, και και στις δύο αυτές περιπτώσεις ασήμαντα, η λίστα είναι ήδη ταξινομημένο. Εάν δεν υπάρχει κατάλογος, είναι ταξινομημένο. Και αν υπάρχει μια λίστα μήκους 1, είναι προφανώς ταξινομημένο. Έτσι ο αλγόριθμος χρειάζεται μόνο να πραγματικά κάτι ενδιαφέρον, αν έχουμε δύο ή περισσότερα τα στοιχεία που μας δόθηκαν. Ας ρίξουμε μια ματιά στο μαγικό συνέχεια. Αλλιώς ταξινομήσετε το αριστερό μισό των στοιχείων, Στη συνέχεια ταξινομήσετε το δεξί μισό του στοιχείων, Στη συνέχεια συγχωνεύσει τα μισά ταξινομημένο. Και τι είναι το είδος του νου κάμψης εδώ, είναι ότι δεν μου φαίνεται να έχουν πει τίποτα ακόμα, έτσι δεν είναι; Όλα τα έχω πει είναι, δίνεται μια λίστα με n στοιχεία, να ταξινομήσετε το αριστερό μισό, Στη συνέχεια το δεξί μισό, τότε συγχώνευση των ταξινομημένο μισά, αλλά πού είναι η πραγματική μυστική συνταγή; Πού είναι ο αλγόριθμος; Λοιπόν αποδεικνύεται ότι οι δύο αυτές γραμμές Κατ 'αρχάς, το είδος αριστερό μισό του στοιχείων, και το είδος δεξί μισό του στοιχείων, είναι αναδρομικές κλήσεις, να το πω έτσι. 

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

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

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

Τώρα, πώς μπορώ να πάω για διαλογή μια λίστα με μέγεθος 4; Λοιπόν, πρέπει να εξετάσουμε τώρα διαλογή το αριστερό του αριστερού μισο. Και πάλι, ας τα πίσω για μια στιγμή. Αν ο ψευδοκώδικας είναι αυτό, και μου δίνουν οκτώ στοιχεία, 8 είναι προφανώς μεγαλύτερη από ή ίσο με 2. Έτσι, με την πρώτη περίπτωση δεν ισχύει. Έτσι για να ταξινομήσετε τα οκτώ στοιχεία, για πρώτη φορά ταξινομήσετε το αριστερό μισό του στοιχείων, τότε μπορώ να ταξινομήσω το δεξί μισό, τότε θα συγχωνευθούν οι δύο ταξινομημένων μισά, το καθένα μεγέθους 4. ΕΝΤΆΞΕΙ. 

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

Γι 'αυτό και τώρα πρέπει να ταξινομήσετε το αριστερό ένα δεύτερο από αυτά τα δύο στοιχεία. Το αριστερό μισό, φυσικά, είναι μόλις 4. Λοιπόν, πώς μπορώ να ταξινομήσετε μια λίστα ενός στοιχείου; Καλά τώρα, ότι η ειδική περίπτωση βάσης επάνω στην κορυφή, να το πω έτσι, ισχύει. 1 είναι μικρότερη από 2, και μου κατάλογος είναι πράγματι μεγέθους 1. Γι 'αυτό και μόλις επιστρέψει. Δεν κάνω τίποτα. Και πράγματι, να δούμε τι έχω γίνεται, 4 είναι ήδη ταξινομημένο. Όπως είμαι ήδη εν μέρει επιτυχής εδώ. 

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

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

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

Έτσι, αν έχουμε την ταξινόμηση αριστερό μισό του 2, τώρα είμαστε Πρέπει να λύσουμε το δεξί μισό του 2. Έτσι το δεξί μισό του 2 Αυτές οι δύο τιμές εδώ, 6 και 2. Ας ρίξουμε τώρα μια είσοδο του μεγέθους 2, και να ταξινομήσετε το αριστερό μισό, και στη συνέχεια, το δεξί μισό, και στη συνέχεια, συγχώνευσή τους μαζί. Λοιπόν, πώς μπορώ να ταξινομήσετε μια λίστα με μέγεθος 1, που περιέχει μόνο τον αριθμό 6; Είμαι ήδη γίνει. Ο εν λόγω κατάλογος μεγέθους 1 ταξινομείται. 

Πώς μπορώ να ταξινομήσω μια άλλη λίστα μέγεθος 1, το λεγόμενο δεξιό μισό. Καλά, επίσης, είναι ήδη ταξινομημένο. Ο αριθμός 2 είναι μόνη της. Έτσι τώρα έχω δύο μισά, αριστερά και σωστά, θα πρέπει να τα συγχωνεύσει μαζί. Επιτρέψτε μου να δώσω στον εαυτό μου κάποια επιπλέον χώρο. Και τίθεται 2 εκεί, Στη συνέχεια 6 εκεί, έτσι διαλογή του εν λόγω καταλόγου, αριστερά και δεξιά, και τη συγχώνευση, σε τελική ανάλυση. Έτσι, είμαι σε ελαφρώς καλύτερη κατάσταση. Δεν είμαι κάνει, γιατί προφανώς 4, 8, 2, 6 δεν είναι η τελική κατάταξη που θέλω. Αλλά έχω τώρα δύο καταλόγους του μεγέθους 2, ότι και οι δύο, αντίστοιχα, έχουν διευθετηθεί. Έτσι τώρα, αν πίσω στο μυαλό σας μάτι, πού αυτός μας αφήνει; Ξεκίνησα με οκτώ στοιχεία, τότε αποσβεστούν τα κάτω στο αριστερό μισό του 4, τότε το αριστερό μισό του 2, και Στη συνέχεια το δεξί μισό του 2, Τελείωσα, ως εκ τούτου, τη διαλογή στην αριστερή εξάμηνο του 2, και το δεξί μισό του 2, ναι, ποιο είναι το τρίτο και τελευταίο στάδιο εδώ; Έχω να συγχωνευθούν δύο καταλόγους του μεγέθους 2. Ας πάμε μπροστά. Και στην οθόνη εδώ, να δώσει Θέλω κάποια πρόσθετη μνήμη, αν και τεχνικά, παρατηρώ ότι έχω πήρε ένα σωρό κενό επάνω στην κορυφή εκεί. Αν θέλω να είναι ιδιαίτερα αποδοτική χώρο σοφός, Θα μπορούσα απλά να αρχίσει να κινείται τα στοιχεία εμπρός και πίσω, πάνω και κάτω. Αλλά ακριβώς για οπτική ευκρίνεια, Πάω να το βάλετε κάτω κάτω, για να κρατήσει τα πράγματα ωραία και καθαρή. 

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

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

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

Οπότε τι μένει; Νιώθω σαν να κρατήσει λέγοντας ότι η ίδια πράγματα ξανά και ξανά, αλλά αυτό είναι αντανακλαστική του γεγονός ότι χρησιμοποιούμε αναδρομή. Η διαδικασία χρησιμοποιώντας ένα αλγόριθμο ξανά, και ξανά, σε μικρότερα υποσύνολα το αρχικό πρόβλημα. Γι 'αυτό και τώρα έχουν μια αριστερή ταξινομημένο το μισό του αρχικού προβλήματος. Έχω το δικαίωμα ταξινομημένη εξάμηνο του αρχικού προβλήματος. Τι είναι το τρίτο και τελευταίο στάδιο; Ω, αυτό είναι που συγχωνεύονται. Ας το κάνουμε αυτό. Ας διαθέσει κάποια πρόσθετα μνήμη, αλλά ο Θεός μου, θα μπορούσε να τεθεί οπουδήποτε τώρα. Έχουμε στη διάθεσή μας τόσο πολύ χώρο για εμάς, αλλά εμείς θα το κρατήσουμε απλό. Αντί να πάει πίσω και να εμπρός με την αρχική μνήμη μας, ας το κάνουμε οπτικά εδώ κάτω κάτω, να τελειώσει συγχώνευση των αριστερό μισό και το δεξί μισό. 

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

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

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

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

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

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

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

Λοιπόν, έκανα n βήματα λειτουργήσει, γιατί αν έχω πήρε τέσσερα στοιχεία και τα τέσσερα στοιχεία, και εγώ πρέπει να τα συγχωνεύσει μαζί. Θα πρέπει να περάσουν από αυτά τα τέσσερα και αυτά τα τέσσερα, τελικά να τα συγχωνεύσει πίσω σε οκτώ στοιχεία. Αν αντιθέτως έχω οκτώ δάχτυλα εδώ, το οποίο εγώ δεν κάνω, και οκτώ fingers-- sorry-- αν έχω πήρε τέσσερα δάχτυλα πάνω από εδώ, που το κάνω, τέσσερα δάχτυλα εδώ, το οποίο κάνω, τότε αυτό είναι το ίδιο παράδειγμα όπως και πριν, αν το κάνω έχει οκτώ δάχτυλα αν και σε Συνολικά, τα οποία μπορώ, το είδος του, το κάνουν. Μπορώ να κάνω ακριβώς εδώ, τότε σίγουρα μπορεί να συγχωνεύσει όλες αυτές τις λίστες μεγέθους 1 μαζί. Αλλά σίγουρα πρέπει να εξετάσουμε σε κάθε στοιχείο ακριβώς μια φορά. Έτσι, το ύψος αυτής της διαδικασίας είναι log n, το πλάτος αυτής της διαδικασίας, να το πω έτσι, είναι n, οπότε αυτό που φαίνεται να έχει, τελικά, είναι ένας χρόνος τρέχει μεγέθους n log n φορές. 

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

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

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

Τώρα ας ρίξουμε άλλο ένα πέρασμα σε αυτό, από μια ελαφρώς πιο επίσημη άποψη, μόνο στην περίπτωση, αυτό αντηχεί καλύτερα από αυτό το υψηλότερο επίπεδο συζήτησης. Έτσι, εδώ είναι και πάλι ο αλγόριθμος. Ας αναρωτηθούμε, ό, τι ο χρόνος τρέχει Είναι αυτή η Αλγόριθμοι διάφορα βήματα; Ας το χωρίσουμε σε πρώτη περίπτωση και η δεύτερη περίπτωση. Η ΕΠΕΥ και ο άλλος στην περίπτωση κατά την οποία, Εάν n είναι μικρότερη από 2, μόλις επιστρέψει. Αίσθηση σαν χρονική σταθερά. Είναι, είδος, σαν δύο στάδια, Εάν n είναι μικρότερη από 2, στη συνέχεια επιστρέφουν. Αλλά, όπως είπαμε, τη Δευτέρα, σταθερά χρόνου, ή μεγάλα o 1, μπορεί να είναι δύο βήματα, τρεις βήματα, ακόμη και 1.000 βήματα. Αυτό που έχει σημασία είναι ότι είναι ένα σταθερό αριθμό βημάτων. Έτσι το κίτρινο τόνισε ψευδοκώδικα εδώ τρέχει σε, θα το ονομάσουμε, σταθερά χρόνου. Έτσι, πιο επίσημα, και θα πάμε to-- αυτό θα είναι η έκταση στην οποία θα επισημοποιήσει αυτό το δικαίωμα now-- Τ Ν, ο χρόνος εκτέλεσης ενός προβλήματος ότι χρειάζεται ν Κάτι σαν είσοδο, ισούται με μεγάλα o του ενός, Εάν n είναι μικρότερη από 2. Έτσι είναι προϋπόθεση για αυτό. Έτσι για να είναι σαφές, αν το n είναι μικρότερο από 2, έχουμε μια πολύ μικρή λίστα, στη συνέχεια, ο χρόνος τρέχει, Τ n, όπου n είναι 1 ή 0, σε αυτή την πολύ ειδική περίπτωση, είναι ακριβώς πρόκειται να είναι σταθερά χρόνου. Είναι πρόκειται να πάρει ένα βήμα, δύο βήματα, οτιδήποτε. Είναι ένα σταθερό αριθμό βημάτων. 

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

Έτσι πράγματι formulaically, μπορούμε να εκφράσουμε αυτό, αν και λίγο τρομακτικά στην αρχή ματιά, αλλά είναι κάτι ότι αποτυπώνει ακριβώς αυτή τη λογική. Ο χρόνος τρέχει, Τ Ν, αν το n είναι μεγαλύτερο από ή ίσο με 2. Σε αυτή την περίπτωση, η υπόθεση άλλο, είναι Τ Ν διαιρούμενο με 2, συν Τ Ν διαιρείται με 2, συν μεγάλες o Ν, μερικοί γραμμική αριθμό των βημάτων, ίσως ακριβώς n, ίσως και 2 φορές n, αλλά είναι κατά προσέγγιση, προκειμένου ν. Έτσι ώστε, επίσης, είναι το πώς μπορούμε να εκφράσουν αυτό formulaically. Τώρα δεν θα το γνωρίζουν αυτό, εκτός αν έχετε εγγραφεί στο μυαλό σας, ή να το αναζητήσετε στο πίσω του ένα βιβλίο, ότι θα μπορούσε να έχει μια μικρή εξαπατήσει φύλλο στο τέλος, αλλά αυτό είναι, πράγματι, πρόκειται να μας δίνουν μια μεγάλη o του n log n, επειδή η υποτροπή που που βλέπετε εδώ στην οθόνη, αν πραγματικά το έκανε έξω, με ένας άπειρος αριθμός παραδειγμάτων, ή το κάνατε formulaically, θα κάνατε δείτε ότι αυτό, γιατί αυτόν τον τύπο η ίδια έχει επαναληπτικό, με τόνους n πάνω από κάτι σχετικά με το δικαίωμα, και t των Ν πάνω στο αριστερό, αυτό μπορεί πράγματι να εκφράζεται, εν τέλει, τόσο μεγάλη πάει n log n. Εάν δεν πεισθεί, ότι είναι πρόστιμο για τώρα, απλά αναλάβει την πίστη, ότι είναι, πράγματι, τι επανάληψη οδηγεί, αλλά αυτό είναι μόνο ένα κομμάτι περισσότερο από ένα μαθηματική προσέγγιση προκειμένου να διερευνηθεί κατά το χρόνο λειτουργίας της συγχώνευσης είδους με βάση ψευδοκώδικας της και μόνο. 

Τώρα, ας ρίξουμε ένα κομμάτι από ένα ανάσα από όλα αυτά, και να ρίξετε μια ματιά σε ένα ορισμένους πρώην γερουσιαστής, ο οποίος μπορεί να μοιάζει λίγο γνωστά, ο οποίος κάθισε με τον Eric της Google Schmidt, πριν από λίγο καιρό, για μια συνέντευξη στη σκηνή, μπροστά σε ένα σωρό των ανθρώπων, μιλάμε τελικά για ένα θέμα, αυτό είναι αρκετά γνωστό πια. Ας ρίξουμε μια ματιά. 

Eric Schmidt: Τώρα γερουσιαστής, είστε εδώ στη Google, και μου αρέσει να σκέφτομαι το της προεδρίας ως μια συνέντευξη για δουλειά. Τώρα είναι δύσκολο να βρουν μια θέση εργασίας ως πρόεδρος. Πρόεδρος Ομπάμα: Σωστά. Eric Schmidt: Και είσαι πρόκειται να κάνει [δεν ακούγεται] τώρα. Είναι επίσης δύσκολο να βρουν μια θέση εργασίας στην Google. Πρόεδρος Ομπάμα: Σωστά. 

Eric Schmidt: Έχουμε ερωτήσεις, και ζητάμε από τους υποψηφίους στις ερωτήσεις μας, και αυτό είναι από Larry Schwimmer. 

Πρόεδρος Ομπάμα: OK. 

Eric Schmidt: Τι; Εσείς νομίζετε ότι αστειεύομαι; Είναι ακριβώς εδώ. Ποιος είναι ο πιο αποτελεσματικός τρόπος για να ταξινομήσετε μια ακέραιοι εκατομμύρια 32 bit; 

Πρόεδρος Ομπάμα: Well-- Eric Schmidt: Μερικές φορές, ίσως Λυπάμαι, maybe-- Πρόεδρος Ομπάμα: Όχι, όχι, Όχι, όχι, όχι, εγώ think-- Eric Schmidt: Αυτό δεν είναι it-- Πρόεδρος Ομπάμα: Ι σκέφτομαι, νομίζω ότι η φούσκα του είδους θα είναι ο λάθος τρόπος να πάει. Eric Schmidt: Έλα. Ποιος τον είπε αυτό; ΕΝΤΆΞΕΙ. Δεν είχα την επιστήμη των υπολογιστών on-- 

Πρόεδρος Ομπάμα: Έχουμε πήρε κατασκόπους μας εκεί. ΚΑΘΗΓΗΤΗΣ: Εντάξει. Ας αφήσουμε πίσω μας το τώρα θεωρητική κόσμο των αλγορίθμων στην ασυμπτωτική ανάλυση αυτών, και να επιστρέψει σε ορισμένα θέματα από την εβδομάδα μηδέν και το ένα, και της έναρξης για να αφαιρέσετε κάποιες βοηθητικές ρόδες, αν θέλετε. Έτσι ώστε να μπορείτε πραγματικά να καταλάβω τελικά από το μηδέν, τι είναι συμβαίνει κάτω από την κουκούλα, όταν γράψετε, μεταγλωττίσετε και να εκτελέσετε προγράμματα. Υπενθυμίζουμε συγκεκριμένα, ότι αυτό ήταν Το πρώτο πρόγραμμα C κοιτάξαμε, ένα κανονικό, απλό πρόγραμμα του είδους, μιλώντας σχετικά, όπου, εκτυπώνει, Hello World. Και υπενθυμίζουν ότι είπα, η διαδικασία ότι ο κώδικας πηγής περνά Είναι ακριβώς αυτό. Μπορείτε να πάρετε τον πηγαίο κώδικα σας, περάστε μέσω ενός μεταγλωττιστή, όπως Clang, και έξω έρχεται αντικειμενικού κώδικα, ότι θα μπορούσε να μοιάζει με αυτό, μηδενικά και μονάδες ότι η CPU του υπολογιστή, κεντρική μονάδα επεξεργασίας ή τον εγκέφαλο, τελικά καταλαβαίνει. 

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

Έτρεξα μια εντολή στη γραμμή εντολών νωρίτερα. Hello.c Clang παύλα κεφαλαίου της, και αυτό δημιούργησε ένα αρχείο για μένα που ονομάζεται hello.s, μέσα από τις οποίες ήταν ακριβώς αυτά τα περιεχόμενα, και λίγο πιο παραπάνω και λίγο περισσότερο κατωτέρω, αλλά έχω βάλει το juiciest πληροφορίες εδώ στην οθόνη. Και αν κοιτάξετε προσεκτικά, θα δείτε τουλάχιστον μερικά γνωστά λέξεις-κλειδιά. Έχουμε κύρια στην κορυφή. Έχουμε printf κάτω στη μέση. Και έχουμε επίσης hello world ανάστροφη κάθετο n σε εισαγωγικά ορίζονται κατωτέρω. 

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

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

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

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

Συγκεκριμένα κάπου σε CS50 IDE, και αυτό, πάρα πολύ, θα είναι ένα κομμάτι από ένα υπεραπλούστευση για μια στιγμή, υπάρχει, ή ήταν κι έναν καιρό, ένα αρχείο που ονομάζεται πρότυπο io.c, ότι κάποιος συγκεντρώνονται σε πρότυπο io.s ή το ισοδύναμο, ότι τότε κάποιος συναρμολογούνται σε τυποποιημένα io.o, ή αποδεικνύεται σε ένα ελαφρώς διαφορετικό αρχείο μορφή που μπορεί να έχει διαφορετική επέκταση αρχείου συνολικά, αλλά θεωρητικά και εννοιολογικά, ακριβώς Στα στάδια αυτά έπρεπε να συμβεί σε κάποια μορφή. Ποια είναι να πούμε, ότι τώρα όταν γράφω ένα πρόγραμμα, hello.c, ότι ακριβώς λέει, hello world, και είμαι με τη χρήση κώδικα κάποιου άλλου όπως printf, η οποία ήταν μια φορά κι έναν χρόνο, σε ένα αρχείο που ονομάζεται πρότυπο io.c, τότε με κάποιο τρόπο πρέπει να πάρω μου Κωδικός αντικειμένου, μηδενικά και μονάδες μου, και το αντικείμενο του εν λόγω προσώπου κώδικα, ή μηδενικά και αυτοί, και με κάποιο τρόπο να τα συνδέσει μεταξύ τους σε ένα τελικό αρχείο, που ονομάζεται Γεια σας, ότι έχει όλα τα μηδενικά και αυτά από την κύρια λειτουργία μου, και όλα τα μηδενικά και εκείνες για printf. 

Και πράγματι, ότι η τελευταία διαδικασία είναι ονομάζεται, που συνδέει τον κωδικό σας αντικείμενο. Η έξοδος του οποίου είναι ένα εκτελέσιμο αρχείο. Έτσι, για να είμαστε δίκαιοι, κατά τη τέλος της ημέρας, τίποτα έχει αλλάξει από μία εβδομάδα, όταν θα για πρώτη φορά άρχισε την κατάρτιση προγραμμάτων. Πράγματι, όλα αυτά ήταν συμβαίνει κάτω από την κουκούλα, αλλά τώρα είμαστε σε θέση όπου μπορούμε πραγματικά πειράζω εκτός αυτών των διαφόρων σταδίων. Και πράγματι, στο τέλος της ημέρας, είμαστε ακόμα αριστερά με μηδενικά και μονάδες, οι οποίες Είναι πραγματικά μια μεγάλη segue τώρα σε μια άλλη ικανότητα C, ότι Εμείς δεν είχαμε να αξιοποιήσουν πιο πιθανό μέχρι σήμερα, γνωστό ως φορείς bitwise. Με άλλα λόγια, μέχρι σήμερα, οποτεδήποτε έχουμε ασχολήθηκε με δεδομένα σε μεταβλητές C ή σε C, είχαμε τα πράγματα όπως χαρακτήρες και άρματα και ins και λαχταρά και δίκλινα και τα παρόμοια, αλλά όλα αυτά είναι τουλάχιστον οκτώ bits. Έχουμε ποτέ δεν είναι ακόμη σε θέση να χειριστείτε μεμονωμένα κομμάτια, ακόμη και αν ένα άτομο λίγο, εμείς γνωρίζουν, μπορεί να αντιπροσωπεύει ένα 0 και 1. Τώρα αποδεικνύεται ότι σε C, που μπορούν να αποκτήσουν πρόσβαση σε μεμονωμένα κομμάτια, αν γνωρίζετε τη σύνταξη, με την οποία για να πάρει σε αυτά. 

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

Στην πραγματικότητα, ας ρίξουμε μια ματιά. Ας πάμε παλιό σχολείο σήμερα, και η χρήση μια οθόνη αφής από χτες, γνωστή ως ένα λευκό του σκάφους. Και αυτό το λευκό του σκάφους θα μας επιτρέψει να εκφράσω μερικές αρκετά απλά σύμβολα, ή μάλλον κάποιοι αρκετά απλές φόρμουλες, να μπορέσουμε στη συνέχεια, τελικά, μόχλευση, προκειμένου να έχουν πρόσβαση σε μεμονωμένες bits μέσα σε ένα πρόγραμμα C. Με άλλα λόγια, ας κάνουμε αυτό. Ας μιλήσουμε πρώτα για την στιγμή για σύμβολο, το οποίο είναι το bitwise τελεστή AND. Με άλλα λόγια, πρόκειται για ένας φορέας που να επιτρέπει Θέλω να έχουμε μια μεταβλητή αριστερά τυπικά, και μια μεταβλητή δεξιά, ή μια συγκεκριμένη τιμή, ότι αν και μαζί, μου δίνει ένα τελικό αποτέλεσμα. Λοιπόν, τι εννοώ; Εάν σε ένα πρόγραμμα, έχετε μια μεταβλητή ότι τα καταστήματα μία από αυτές τις αξίες, ή ας το κρατήσουμε απλό, και απλά γράψτε μηδέν και ατομικά, εδώ είναι το πώς λειτουργεί ο χειριστής ampersand. 0 0 εμπορικό και πρόκειται να ισούται με 0. Τώρα γιατί συμβαίνει αυτό; 

Είναι πολύ παρόμοια με Boolean εκφράσεις, ότι έχουμε συζητήσει μέχρι στιγμής. Αν νομίζετε ότι μετά από όλα, το 0 είναι ψευδείς, 0 είναι ψευδή, ψευδής και ψευδής είναι, όπως έχουμε συζητήσει λογικά, επίσης εσφαλμένη. Έτσι έχουμε το 0 ως εδώ καλά. Εάν πάρετε 0 Ampersand 1, και ότι, επίσης, πρόκειται να είναι μηδέν, επειδή γι 'αυτό έκφραση αριστερή πλευρά για να είναι αληθινό ή 1, θα πρέπει να είναι αληθινή και πραγματική. Αλλά εδώ έχουμε ψευδή και αλήθεια, ή 0 και 1. Τώρα πάλι, αν έχουμε 1 Ampersand 0, ότι, επίσης, πρόκειται να είναι 0, και αν έχουμε 1 ampersand 1, Τέλος έχουμε ένα 1 bit. Έτσι με άλλα λόγια, αν δεν κάνει κάτι ενδιαφέρον με αυτόν τον τελεστή ακριβώς ακόμα, ο φορέας αυτός Ampersand. Είναι το bitwise τελεστή AND. Αλλά αυτά είναι τα συστατικά μέσω του οποίου μπορούμε να κάνουμε ενδιαφέροντα πράγματα, όπως θα δούμε σύντομα. 

Τώρα, ας δούμε λίγο την ενιαία κάθετη μπάρα εδώ στα δεξιά. Αν έχω ένα bit 0 και Ι Ή με το bitwise Χειριστή ή άλλο bit 0, ότι πρόκειται να μου δώσει 0. Αν πάρω ένα bit 0 και OR με το bit 1, τότε είμαι πρόκειται να πάρει 1. Και στην πραγματικότητα, μόνο για σαφήνειας, επιτρέψτε μου να πάω πίσω, έτσι ώστε κάθετες μπάρες μου Δεν είναι λάθος για 1 '. Επιτρέψτε μου να ξαναγράψει το σύνολο του 1 μου είναι λίγο πιο σαφώς, έτσι ώστε να δούμε την επόμενη, αν έχουν 1 ή 0, αυτό πρόκειται να είναι ένα 1, και αν έχω ένα 1 ή 1 ότι, πάρα πολύ, θα είναι 1. Έτσι μπορείτε να δείτε ότι η λογική OR φορέας συμπεριφέρεται πολύ διαφορετικά. Αυτό μου δίνει 0 ή 0 0 μου δίνει, αλλά κάθε άλλος συνδυασμός μου δίνει 1. Εφ 'όσον έχω ένα 1 στην τύπο, το αποτέλεσμα θα είναι 1. 

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

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

Και αυτό μας αφήνει επιτέλους με μόλις δύο τελικούς φορείς, η λεγόμενη αριστερή στροφή, και η λεγόμενη δεξιά στροφή χειριστή. Ας ρίξουμε μια ματιά στο πώς αυτά τα εργασία. Ο χειριστής αριστερή στροφή, γραπτή με δύο αγκύλες, όπως ότι, λειτουργεί ως εξής. Εάν η είσοδος μου, ή τελεστή μου, προς τα αριστερά χειριστής αλλαγή είναι πολύ απλά 1. Και εγώ τότε πείτε στον υπολογιστή να αριστερή στροφή ότι το 1, δηλαδή επτά θέσεις, το αποτέλεσμα είναι σαν να κάνει αυτό το 1, και να το μετακινήσετε επτά θέσεις πάνω στην αριστερά, και από προεπιλογή, θα πάμε να υποθέσουμε ότι ο χώρος προς τα δεξιά πρόκειται να παραγεμισμένο με μηδενικά. Με άλλα λόγια, 1 αριστερή στροφή 7 πρόκειται να μου δώσει ότι το 1, ακολουθούμενο από 1, 2, 3, 4, 5, 6, 7 μηδενικά. Έτσι, κατά κάποιο τρόπο, αυτό σας επιτρέπει να να λάβει ένα μικρό αριθμό όπως το 1, και σαφώς αυτό κάνει πολύ πολύ, πολύ μεγαλύτερο με αυτόν τον τρόπο, αλλά είμαστε πραγματικά πρόκειται να δείτε πιο έξυπνη προσεγγίσεις για αυτό Αντ 'αυτού, καθώς και, 

Εντάξει. Αυτό είναι για τρεις εβδομάδες. Θα σας δούμε την επόμενη φορά. Αυτό ήταν CS50. 

[Παίζει μουσική] 

ΟΜΙΛΗΤΗΣ 1: Ήταν στο σνακ bar τρώγοντας ένα ζεστό φοντάν παγωτό. Εκείνος τα είχε όλα πάνω από το πρόσωπό του. Φοράει ότι η σοκολάτα σαν μια γενειάδα ΟΜΙΛΗΤΗΣ 2: Τι κάνεις; ΟΜΙΛΗΤΗΣ 3: Χμμμ; Τι? 

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

ΟΜΙΛΗΤΗΣ 3: Ξέρεις κάτι, Dan; Βυθίζετε τον τρόπο που θέλετε να βουτιά. Θα βουτιά με τον τρόπο που θέλω να βουτιά.