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

David J. Malan: Αυτό είναι CS50. Και αυτό είναι η αρχή των τριών εβδομάδων. Έτσι έχουμε ένα πολύ συναρπαστικό τα πράγματα να καλύψουμε σήμερα. Πολλές ευκαιρίες για εθελοντές επάνω στη σκηνή. Και τελικά, σήμερα είναι όχι για κωδικό καθόλου. Αλλά είναι για τις ιδέες, και πρόκειται για αλγορίθμους, και μάλιστα φέρνοντας πίσω μερικά από τα τα διδάγματα που αντλήθηκαν από την εβδομάδα μηδέν, όπου ανάκληση, εμείς εισήγαγε αυτό το τερατούργημα. Και δανεισμού έμπνευση από αυτό, για να ξεκινήσει να λύσει ολοένα και πιο πολύπλοκα αλγοριθμικά προβλήματα. Αλλά πρώτα, μερικές ανακοινώσεις. Έτσι, ένα, αν θέλετε να γίνετε μέλος Το προσωπικό και τους συμμαθητές CS50 κατά το γεύμα αυτή την Παρασκευή, τόσο εδώ όσο και στην Cambridge, και στο New Haven, παρακαλώ επισκεφθείτε την μαθήματος ιστοσελίδα, όπου μπορείτε να βρείτε μια διεύθυνση URL. Διάλεξη αυτή την Τετάρτη θα Δεν είναι εδώ ο Sanders. Θα είναι μόνο online, έτσι συντονιστείτε στην ιστοσελίδα του CS50, είτε εδώ στο Κέιμπριτζ ή New Haven, καθώς και. 

Και τότε το πρόβλημα που δύο είναι ήδη στα χέρια σας. Εάν δεν έχετε καταδυθεί ακόμα, επιτρέψτε μου να προσφέρει την έντονα διατυπωμένη πρόταση ότι, ειδικά τώρα, όπως το πρόβλημα θέτει εκ των προτέρων, αν πραγματικά θέλουμε να ξεκινήσουμε τώρα, εάν δεν ανακατεύομαι λίγο για το Σαββατοκύριακο ή πριν κατά την πρώτη τους βγαίνουν Παρασκευή, γιατί θα διαπιστώνουν ότι δεν είναι κατ 'ανάγκην επιμηκύνεται ή πιο προκλητική ανά se. Νομίζω ότι θα βρείτε ότι, σε Γενικά, τείνουν να λάβουν περίπου περίπου ίδιο χρονικό διάστημα. Αλλά αυτό εξαρτάται ασφαλώς για το μαθητή, και εξαρτάται από τη νοοτροπία με την οποία μπορείτε να την προσεγγίσουμε. Αλλά πάντα, θα πάμε να οδηγεί σε κάποιο τοίχο, και θα πάμε για να χτυπήσει κάποια bug, και είστε ακριβώς δεν πρόκειται να είναι σε θέση να ξεπεράσω κάποια στιγμή. Και είναι εξαιρετικά πολύτιμη για να είναι σε θέση να βήμα μακριά, να επιστρέψει την επόμενη μέρα, πάει στο γραφείο ώρες, μετά σε CS50 Συζήτηση ή τα παρόμοια, για να πάρει πραγματικά αποκλεισμένο. Έτσι κρατήστε αυτό κατά νου. Έναρξη το νωρίτερο δυνατό είναι το καλύτερο πράγμα που μπορείτε να κάνετε. Έτσι, εδώ είναι όπου ξεκινήσαμε η τάξη, πάνω στην εβδομάδα μηδέν. Και μπορούμε να πάρουμε έναν εθελοντή εδώ για να με βοηθήσει να βρω μικρόφωνα; ΕΝΤΆΞΕΙ. Όρθιος ήδη. Έλα επάνω. Υποθέτω ότι αυτό είναι το πώς πρόκειται να λειτουργήσει. Ποιο είναι το όνομά σου? ALAN ESTRADA: Alan Estrada. David J. Malan: Alan Estrada. Έλα επάνω. Χάρηκα για τη γνωριμία. ALAN ESTRADA: Χαίρω πολύ. David J. Malan: Και ήσουν εδώ μαζί μας στην εβδομάδα μηδέν, φυσικά. ALAN ESTRADA: ήμουν. Ήμουν. 

David J. Malan: Έτσι θα μπορούσε να πάτε μπροστά και να βρει για μας ο Mike Smith, όσο πιο γρήγορα μπορείτε; Όσο πιο γρήγορα μπορείτε. Κυριολεκτικά σχίσιμο του προβλήματος στη μέση, όπως το χρειάζεστε. 

ALAN ESTRADA: Um. David J. Malan: Κυριολεκτικά σχίσιμο του προβλήματος στο μισό. 

ALAN ESTRADA: Αχ. Mm. Πολύ καλά. 

David J. Malan: OK. Καλή. Ευχαριστώ. ALAN ESTRADA: Πολύ καλή. ΕΝΤΆΞΕΙ. 

David J. Malan: Και έτσι τώρα, έχετε μειώνονται στο μισό του μεγέθους του προβλήματος. Τώρα, είμαστε κάτω σε ένα τρίμηνο. Είσαι δίνοντας προσοχή στην ποια πλευρά είμαστε κρατώντας; 

[Γέλια] 

ALAN ESTRADA: Ναι, έχω think-- 

David J. Malan: Ποια ενότητα είμαστε μέσα; ALAN ESTRADA: Εξατμίσεις, έτσι. 

David J. Malan: OK. Αλλά ο Mike Smith, ο οποίος θα να είναι μετά Εξατμίσεις. So-- 

[Γέλια] 

Εντάξει. ALAN ESTRADA: Όταν ψάχνουμε; David J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. David J. Malan: Τώρα, είμαστε σε χειρουργική. Τώρα, οι γιατροί. Now-- 

ALAN ESTRADA: Let's- ας πάει με το πραγματικό. Ρεάλ. 

David J. Malan: Real. ΕΝΤΆΞΕΙ. Αν χρειάζεστε Ρεάλ. Τώρα, προς ποια κατεύθυνση είναι ο Mike Smith; 

ALAN ESTRADA: Με αυτό τον τρόπο. 

David J. Malan: Ποιος ο δρόμος; ALAN ESTRADA: Περιμένετε. Μ is-- σωστά; Ξεκινήσαμε with-- 

David J. Malan: Ναι. Είναι αριστερά. Το δικαιωμα σου. 

ALAN ESTRADA: Ναι. 

David J. Malan: Λοιπόν Μάικ εδώ. ALAN ESTRADA: Τι; 

[Γέλια] 

Κακό παράδειγμα, παιδιά. Λυπάμαι. David J. Malan: Αυτό θα διδάξει μπορείτε να άλμα από την καρέκλα σας. 

ALAN ESTRADA: Αχ. Ω. Σε έπιασα. Σε έπιασα. Ω. Ω. Αυτό is-- Εντάξει, έχεις. Σμιθ εδώ; 

David J. Malan: Smith, σας ευχαριστώ. Γι 'αυτό θα συνεχίσει να αναζητά μέχρι Σμιθ; 

ALAN ESTRADA: Ω, ναι. ΟΧΙ ΟΧΙ ΟΧΙ. Ωχ όχι. Αυτο ειναι δικο μου. 

David J. Malan: Ω, έχεις Σμιθ. ΕΝΤΆΞΕΙ. 

ALAN ESTRADA: Ναι, έχω Smith πήρε ακριβώς εδώ. Συγγνώμη, παιδιά. Νόμιζα ότι θα Michael-- έψαχναν για τον Michael. Λυπάμαι. 

David J. Malan: Είναι εντάξει. Εντάξει, τώρα είμαστε σε Paccini και Υιοί. 

ALAN ESTRADA: Paccini και γιους. David J. Malan: Μόνο εσείς και εγώ είμαστε μέσα σε αυτό. ΕΝΤΆΞΕΙ. Βρείτε μας Mike Smith. Σμιθ. 

ALAN ESTRADA: Smith. 

David J. Malan: Smith. Είμαστε στην έρευνα για τα σκουπίδια. ALAN ESTRADA: Χάλια. Ω. Αυτό πρόκειται να πάρει λίγο χρόνο. 

[Γέλια] David J. Malan: Παπούτσια. Είμαστε στα παπούτσια. 

ALAN ESTRADA: Τώρα είμαστε gonna-- 

David J. Malan: Νίκαια. ALAN ESTRADA: Which-- [Γέλια] Ω, αυτό είναι μεγάλη. [Γέλια] 

David J. Malan: Είναι εντάξει. 

ALAN ESTRADA: Ω, αυτό είναι καλό. Δεν νομίζω ότι θα πάω να έχουν ΠΣΑΤ φίλοι μετά από αυτό. David J. Malan: Καλή. Σπόρτινγκ. ALAN ESTRADA: Sporting. Εμ, Λ, Μ, Ν, Ο, Π David J. Malan: OK. Ας δάκρυ αυτό στο μισό. Είναι εντάξει. Αυτό τελειώνει καλά ούτως ή άλλως, γιατί ο Mike Smith δεν θα είναι στις κίτρινες σελίδες. 

ALAN ESTRADA: Aw. 

David J. Malan: Όχι, είναι εντάξει. Αλλά ας προσποιούνται όπως αυτός είναι σε αυτή τη σελίδα. Μέχρι τώρα, έχετε αποσβεστούν το πρόβλημα κάτω σε μία σελίδα, και βρήκαμε Mike Smith. 

[Ζητωκραυγάζει] Εντάξει ευχαριστώ. ΕΝΤΆΞΕΙ. Αυτό ήταν εξαιρετικό. Αλλά ακόμα πιο γρήγορα ήταν από τη γραμμική αναζήτηση, όπου θα ξεκινούν από το αρχή του βιβλίου, και κινούμαστε δρόμο μας από αριστερά προς τα δεξιά, τελικά αναζητούν Mike Smith. Και έτσι, αν ο τηλεφωνικός κατάλογος είχε ίσως 1.000 σελίδες, ίσως θα έχουν λάβει μας 10 ή έτσι τα δάκρυα της σελίδας. 

Αλλά μπορεί να έχετε μόχλευση άγγιξε μια υπόθεση κατά τη διάρκεια όλα αυτά, πράγμα που σημαίνει ότι το βιβλίο τηλέφωνο εκ των προτέρων ήταν αυτό; Κοινό: Ταξινόμηση. David J. Malan: Είναι ταξινομημένο. Σωστά; Είναι ταξινομημένα αλφαβητικά, έτσι ότι όλα αυτά τα ονόματα και τους αριθμούς κατατάσσονται από το Α έως το Ζ, καθώς και με αλφαβητική σειρά στο μεταξύ. Αλλά σήμερα, μπορούμε τώρα να ζητήσει το ερώτημα, καθώς, πώς έκανε Verizon ή το τηλέφωνο Η εταιρεία θα μπει σε αυτή την κατάσταση; 

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

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

Και αν μπορούσε πραγματικά Ιορδανία ελάτε μαζί μας εδώ στη σκηνή. Έλα για μια στιγμή. Ποιο είναι το όνομά σου? ΚΑΡΟΛΙΝΑ: Caroline. David J. Malan: Caroline, έλα επάνω. Και θα πρέπει να ενταχθεί από εμένα και την Ιορδανία εδώ. Caroline, σας ευχαριστώ. Εντάξει. Έτσι, αυτό που έχουμε εδώ Η Caroline είναι 26 μπλε βιβλία ότι FAS χρησιμοποιεί για να διαχειριστεί ορισμένες τελικές εξετάσεις. Αυτά είναι ολοένα πιο δύσκολο να βρεθεί, αλλά αυτό που έχουμε κάνει εκ των προτέρων είναι ότι έχουμε βάλει το όνομα κάποιου στο μπροστινό μέρος του καθενός από αυτά, αλλά έχουμε κρατήσει από το απλό Στη συνέχεια κατάσβεση πλήρη ονόματα. Γι 'αυτό και θα θέσει το πρόσωπο με το όνομα L, D, J, Β, σε όλη τη διαδρομή A έως Z, αλλά είναι σε τυχαία σειρά. Και έτσι αν ήταν, μιλώντας σας διαδρομή μέσα από το πρόβλημα με εσάς κάνετε, μπορεί να προχωρήσει και να ταξινομήσετε αυτά για μας, από το Α έως το Ω 

Κοινό: Εντάξει, έτσι είναι σαν L, η μέση. C έχει αρχίσει. Β Ι Β Λ πριν, Q. 

David J. Malan: Κρατήστε ότι σκέφτηκε για ένα δευτερόλεπτο. Διότι αλλιώς, αυτό είναι μόνο ενδιαφέρουσες για εσάς, εμένα, και την Ιορδανία. Εκεί πάμε. Κοινό: [δεν ακούγεται]. R. David J. Malan: OK. Τι κάνεις? 

ΚΑΡΟΛΙΝΑ: M έρχεται μετά O. 

David J. Malan: OK. 

CAROLINE: O. David J. Malan: O, Καλή. 

CAROLINE: Ε 

David J. Malan: Ε, ΣΤ Ναι. 

CAROLINE: T, U, V. 

DAVID J. Malan: V, Τ, U, V. Έτσι Φαίνεται σαν να είστε making-- συνεχίσω. Μοιάζει κάνεις ένα μεγάλο σωρό εδώ, και το είδος της ένα μεγάλο σωρό εκεί πέρα. Έτσι, το πρώτο εξάμηνο του αλφαβήτου, δεύτερο εξάμηνο του αλφαβήτου. ΕΝΤΆΞΕΙ. Καλή. Είδος διάσπαση του προβλήματος σε δύο. Μ, Ν, Ξ Ναι. CAROLINE: Κ David J. Malan: OK. Κ Έτσι είστε το είδος της επιλογής τους ένα μετά το άλλο, τοποθετώντας την είτε αριστερά είτε δεξιά, ή Ζ πηγαίνει στο πάτωμα. ΕΝΤΆΞΕΙ. 

ΚΑΡΟΛΙΝΑ: Z πηγαίνει στο πάτωμα. 

David J. Malan: OK. Y πηγαίνει στο πάτωμα. Τώρα μπορούμε να βάλουμε φυλακή 

CAROLINE: Γ David J. Malan: G πηγαίνει αριστερά. S δεν πάει καλά. Εντάξει, Α πηγαίνει όλος ο τρόπος αριστερά. 

CAROLINE: A, B, C, D. 

David J. Malan: Τώρα, καλό. Έχουμε Α, Β, Γ W πηγαίνει εκεί κάτω. Εντάξει, T. 

ΚΑΡΟΛΙΝΑ: Η, Θ, Ι David J. Malan: Η, Θ, Ι Καλό. ΚΑΡΟΛΙΝΑ: Στο κέντρο, είμαι gonna-- David J. Malan: OK. Έτσι τώρα, θα πάμε σε είδος από τη συγχώνευση των διαφόρων αυτών σωρούς. Έτσι A έως C, τότε βλέπω D, και Ε και F, και G, και Η, Θ και της Νίκαιας. J, Κ και στη συνέχεια, αυτό είναι σωρός ανάποδα, αλλά αυτό είναι εντάξει. Σίγουρα. Μπορούμε να κόψετε μερικές γωνίες. ΕΝΤΆΞΕΙ. Και τότε χρειαζόμαστε W, Χ, Υ, Ζ 

ΚΑΡΟΛΙΝΑ: Ναι. 

David J. Malan: Εξαιρετική. Έτσι, ένα μεγάλο ευχαριστώ σε Caroline για τη διαλογή αυτών. 

[Ζητωκραυγάζει] 

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

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

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

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

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

Τα Αυτή ένα-- demos πρόκειται σε μια ταχύτερη και πιο γρήγορα τώρα. Ελάτε κάτω. Ποιο είναι το όνομά σου? TREVOR: Trevor. 

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

Έτσι Trevor, ωραίο να σας γνωρίσουμε. Έτσι, εδώ είναι μια σειρά, έτσι ώστε να μιλούν, μια λίστα με επτά πόρτες. Προχωρήστε και θα μας βρείτε στον αριθμό 50. Και στη συνέχεια, μετά το γεγονός, να μας πει πώς το βρήκατε. Σε περίπτωση που be-- εντάξει. Ναι, αυτή είναι η μία εδώ; Ωχ. ΕΝΤΆΞΕΙ. Μπορείτε κλικ ότι ένα. Καλή. 

Και καλό. Τώρα που πατήσατε το ένα. Και επιτρέψτε μου να σας δώσω το μικρόφωνο, έτσι ώστε να μπορείτε να έχετε ακριβώς σε μια στιγμή. Προχωρήστε και κάντε κλικ στο κουμπί διπλανής πόρτας που σκοπεύετε. Ναι ωραία. TREVOR: Μπορώ να αποεπιλέξτε μια πόρτα; David J. Malan: Όχι, δεν μπορείτε να αποεπιλέξτε. TREVOR: OK. Αυτό. David J. Malan: Πού θέλετε να πάτε; Ποιο από όλα? 

TREVOR: Εκείνο το ένα. 

David J. Malan: Όχι. 

TREVOR: OK. Αυτό. 

David J. Malan: Ναι. Αυτό ήταν καλό. Εντάξει. Λοιπόν, τι ήταν αλγόριθμο ή διαδικασία για να γίνει αυτό, Τρέβορ; 

TREVOR: Πήγα μέσω πόρτες μέχρι να βρεθεί μια 50. David J. Malan: OK. Εξαιρετική αλγόριθμο. Έτσι, αυτό είναι εντάξει. Διότι στην πραγματικότητα, αν μπορώ να αποκαλύψει ό, τι είναι πίσω από αυτές τις άλλες δύο πόρτες, τι θα βρούμε εδώ είναι ότι έχουμε μόνο τυχαία είσοδο. Οπότε αυτό ήταν στην πραγματικότητα καθώς καλή όσο θα μπορούσε να πάρει. Και στην πραγματικότητα, έχεις καλύτερη από ό, τι εξαντλητικά αναζήτηση ολόκληρου του πίνακα, επειδή θα έχουν πραγματικά άτυχος αν είχε χτυπήσει τον αριθμό 50 κατά την τελευταία πόρτα. Αλλά τι θα γινόταν αν αντ 'αυτού Σας έδωσα μια υπόθεση. Ας υποθέσουμε ότι το είδος όλους Αυτές οι πόρτες γύρω, έτσι ώστε να έχετε το αριθμοί ταξινομούνται αυτή τη φορά, αλλά αυτή τη φορά είναι πραγματικά α different-- αυτή τη φορά, αυτό είναι πραγματικά ταξινομηθεί για εσάς. Και τώρα ο στόχος στο χέρι είναι να χτυπήσει τον αριθμό 50. 

TREVOR: OK. 

David J. Malan: Τι είναι αλγόριθμος σας πρόκειται να είναι; 

TREVOR: Λοιπόν, αν είναι διαλογή, είναι είτε πηγαίνοντας να be-- αν το μεγαλύτερο στο μεγαλύτερο, φθίνουσα, αυτό θα είναι το πρώτο, ή αν πρόκειται για το αντίθετο, θα είναι η τελευταία. Γι 'αυτό θα πρέπει ακριβώς να αξιοποιήσει αυτήν την πόρτα, και τότε απλά πατήστε το τελευταίο πόρτα. David J. Malan: Εξαιρετική. Εντάξει. Έτσι βρήκαμε τον αριθμό 50. Έτσι, το συντομότερο ξέρατε είχαν διευθετηθεί, θα ήταν σε θέση να αξιοποιήσουν αυτή την υπόθεση. Έτσι είναι πάρα πολύ σαν Το παράδειγμα του τηλεφωνικού καταλόγου. Από τη στιγμή που έχετε, ακόμη και με ένα μικρό πρόβλημα όπως αυτό, εισόδους σας προ-ταξινόμηση, μπορούμε στην πραγματικότητα βρείτε την τιμή αμφισβητήσιμα πιο αποτελεσματικά. 

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

Έτσι, αυτό θα κάνει για του επόμενου έτους κλιπ ως γιατί ήμουν κάνετε κλικ στις δικές μου οθόνη. Αλλά ας ρίξουμε μια γρήγορη ματιά σε ό, τι συνέβη πέρυσι με τον Jay, ο οποίος ήρθε, πολύ όπως Trevor εδώ, εθελοντικά, και σε αυτό το σύντομο κλιπ, θα δείτε πώς αυτό το ίδιο το demo δεν έκανε αρκετά αποκαλύψει τα ίδια διδάγματα. [ΑΝΑΠΑΡΑΓΩΓΗ] -Όλες Θέλω να κάνω τώρα είναι να να βρει για μένα, αλλά και για εμάς, Πραγματικά, ο αριθμός 50 ένα βήμα τη φορά. 

-τον Αριθμό 50; 

-τον Αριθμό 50. Και μπορείτε να αποκαλύψει τι είναι πίσω από κάθε μία από αυτές τις πόρτες απλά αγγίζοντας το με ένα δάχτυλο. Ανάθεμα. 

[Γέλια] 

[Σταματήσετε την αναπαραγωγή] David J. Malan: Μέχρι που πήγε πολύ καλά. Αυτά ήταν τα αδιαχώριστα πόρτες. Και Jay, φυσικά, βρήκα όλα πολύ γρήγορα. Trevor έκανε πολύ καλύτερη δουλειά σε όρους μιας διδακτός στιγμή, να το πω έτσι, φέτος στο περισσότερο χρόνο για να το βρείτε. Φυσικά, τότε δώσαμε Jay μια δεύτερη ευκαιρία, σύμφωνα με την οποία θα διευθετηθεί τις πόρτες, ακριβώς όπως κάναμε για τον Trevor, και Trevor έκανε σούπερ καλά αυτή τη φορά. Αλλά Jay έκανε το μισό τόσο γρήγορα. [ΑΝΑΠΑΡΑΓΩΓΗ] -Το Στόχος τώρα είναι να επίσης βρείτε μας στον αριθμό 50, αλλά να το κάνει αλγοριθμικά, και πείτε μας πώς θα πάμε για αυτό. 

-ΕΝΤΆΞΕΙ. 

-Και Αν το βρείτε, θα κρατήσει την ταινία. Αν δεν το βρείτε, να το δώσει πίσω. 

-Άνδρας. 

-ΟΗ! 

- [Δεν ακούγεται] OK. Έτσι, Πάω να ελέγξει τα άκρα πρώτα να προσδιορίσετε αν there's-- Αχ. 

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

[Σταματήσετε την αναπαραγωγή] David J. Malan: OK. Έτσι, η διαλογή των θυρών με σαφήνεια οδηγεί σε μεγαλύτερη αποτελεσματικότητα. Και έτσι, δύο φορές πιο γρήγορα είναι αυτό που εννοούσα εκεί. Και έτσι Jay τυχεροί και τις δύο φορές. Και, επίσης, πήρε τυχερός στην τελευταία έτος, παρήγγειλα ορισμένους δίσκους Blu-ray να δίνουν στην πραγματικότητα. Λυπάμαι φέτος, δεν είχε την ίδια, Trevor. Αλλά ακόμη καλύτερα ήταν πριν από μερικά χρόνια. Και κάποιοι από εσάς ίσως γνωρίζετε αυτό τους συναδέλφους, Sean, ο οποίος όταν ήταν σε CS50, αμφισβητήθηκε με την ακριβή ίδιο πρόβλημα, αν και σε SD, όπως θα δείτε σύντομα, πίσω στην ημέρα. Και θα διαπιστώσετε ότι όχι μόνο αυτός πάρει λίγο περισσότερο από ό, τι Jay, λίγο περισσότερο από ό, τι Trevor, ήταν στην πραγματικότητα αυτή την υπέροχη ευκαιρία να συμμετέχουν σχεδόν όλοι στην πλήθος a la τιμή είναι σωστή, ενθαρρύνοντας αυτόν να βρείτε τον αριθμό που ζητούσαν. Ας. ρίξτε μια γρήγορη ματιά. 

[ΑΝΑΠΑΡΑΓΩΓΗ] 

-ΕΝΤΆΞΕΙ. Έτσι, το έργο σας εδώ, Σον, είναι το εξής. Έχω κρυμμένο πίσω από αυτά πόρτες ο αριθμός επτά. Αλλά κρυμμένο σε ορισμένες από αυτές τις πόρτες καθώς είναι άλλες αρνητικούς αριθμούς. Και ο στόχος σας είναι να σκεφτεί της κορυφαίας σειράς αριθμών ως απλά έναν πίνακα, ή απλά ακολουθία κομμάτια χαρτιού με αριθμούς πίσω τους. Και ο στόχος σας είναι, χρησιμοποιώντας μόνο την κορυφή σειρά εδώ, βρες μου τον αριθμό επτά. Και στη συνέχεια πρόκειται να κριτικάρω πώς μπορείτε να κάνετε για αυτό. -Εντάξει. -Βρείτε Μας τον αριθμό επτά, παρακαλώ. Κανένα. Πέντε, 19, 13. 

[Γέλια] 

Δεν είναι μια ερώτηση τεχνάσματος. Ένα. 

[Γέλια] Σε αυτό το σημείο, το σκορ σου δεν είναι πολύ καλά, έτσι ίσως και να συνεχίσω. Τρεις. 

[Γέλια] 

Συνέχισε. Ειλικρινά, δεν μπορώ να βοηθήσει, αλλά αναρωτιέμαι τι είστε καν να το σκεφτούμε, so-- 

[Γέλια] Μόνο η επάνω σειρά, έτσι έχεις τρία αριστερά. Έτσι, βρείτε μου επτά. 

[Γέλια] 17. Επτά. 

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

Εντάξει. 

[Σταματήσετε την αναπαραγωγή] 

David J. Malan: έτσι θα μπορούσαμε να Παρακολουθήστε αυτά όλη μέρα. Και φυσικά, ορισμένες από τις demos φετινή ίσως τώρα θα καταλήξουν στην επόμενη βίντεο έτους, καθώς και. Έτσι τώρα ας πραγματικότητα επικεντρωθεί στις αλγορίθμους εδώ, και να δούμε αν δεν μπορούμε να τώρα αρχίζουν να επισημοποιήσει πώς μπορούμε να πάμε για να πάρει τα δεδομένα μας σε αυτή την κατάσταση ότι είναι ταξινομημένο, έτσι ώστε, τελικά, μπορούμε πραγματικά να αναζήτηση πιο αποτελεσματικά. Και ακόμα κι αν θα πάμε να χρησιμοποιήσει αρκετά μικρά σύνολα δεδομένων, όπως το έχουμε οκτώ αριθμούς έχουμε εδώ στο διοικητικό συμβούλιο, τελικά, θα μπορούσαν να εφαρμοστούν αυτές οι ίδιες ιδέες 1.000 εισόδους, ένα εκατομμύριο εισόδους, 4000000000 εισόδους, επειδή οι αλγόριθμοι πρόκειται να είναι ουσιαστικά η ίδια. 

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

Έτσι, ένα στην turquoise-- πράσινο είναι αυτό; Είσαι διάπραξη; Δύο. Ελάτε κάτω. ΕΝΤΆΞΕΙ. Τρεις. Τέσσερις. Ας me-- Εντάξει, πέντε. Είσαι που διορίζεται από το φίλο σας. Έξι, επτά, οκτώ. Έλα επάνω. Εντάξει. Ευχαριστω παρα πολυ. Έλα επάνω. Έλα επάνω. 

Εντάξει. Έτσι, αυτό που here-- και αυτό έχει είναι μια από τις πιο δύσκολη αυτά, δεδομένου ότι αυτό θα πρέπει να έχετε χιούμορ Θέλω μόνο για ένα μικρό κομμάτι του χρόνου. Θα πρέπει να είναι το νούμερο ένα. Ποιο είναι το όνομά σου? 

Ανάν Ανάν. 

David J. Malan: Ανάν. Δαβίδ. Ποιο είναι το όνομά σου? 

JOSEPH: Joseph. 

David J. Malan: Ιωσήφ, είσαι νούμερο δύο. 

SERENA: Serena, το νούμερο τρία. Stefan, νούμερο τέσσερα. CYNTHIA: Cynthia. David J. Malan: Cynthia, νούμερο πέντε. [Δεν ακούγεται] David J. Malan: [δεν ακούγεται]. Ο David, τον αριθμό έξι. ΜΑΤ: Ματ. David J. Malan: αριθμός Ματ επτά. Και; 

WAVERLY: Waverly. 

David J. Malan: Waverly, νούμερο οκτώ. Εντάξει. Αν could-- κραυγών. Εάν όλα, όπως σας πρώτη πρόκληση, εκεί είναι οκτώ περίπτερα μουσική εδώ που αντιμετωπίζει το κοινό. Αν θα μπορούσατε να βάλετε τους αριθμούς σας αυτοί μουσική στέκεται κατά τέτοιο τρόπο ότι είναι ευθυγραμμισμένο με το ίδιους αριθμούς στον πίνακα. Έτσι κάνετε τον εαυτό σας να μοιάζει ότι από βάζοντας τους αριθμούς σας σε αυτά μουσικής στέκεται εδώ. Εξαιρετική μέχρι στιγμής. 

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

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

Και έτσι κοιτάζω αυτά τα δύο, τέσσερα και δύο. Και ποιο είναι το πρόβλημα, προφανώς; Ναι. So. Δύο προφανώς έρχεται πριν τέσσερα, ώστε να γνωρίζετε τι; Επιτρέψτε μου πρώτα να λάβει μια άπληστη προσέγγιση, αν θέλετε, μοιάζει πολύ με το πρόβλημα που ένα-- αν θυμάστε από το Standard Edition του προβλήματος Set One, όπου μόλις τοπικά λύσει το πρόβλημα ότι είναι σωστό εδώ μπροστά μου και να δούμε πού μας οδηγεί. 

ΕΝΤΆΞΕΙ. Έτσι, δύο και τέσσερα, επιτρέψτε μου να πάω μπροστά και μόνο μπορείτε να ανταλλάσσετε δύο. Αν φυσικά να μετακινήσετε τον εαυτό σας και το χαρτί σας, Μου φαίνεται να έχουν πάρει το λίστα σε καλύτερη κατάσταση. 

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

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

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

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

Καλή. Είμαστε πάρει ακόμα καλύτερα. Ας δούμε λοιπόν. Τώρα, έχουμε δύο και το ένα. Φυσικά, να ανταλλάξουν. Δύο και τρία, τρία και τέσσερα, τέσσερα και πέντε, έξι και επτά, επτά και οκτώ. Καλή. Και ξέρετε τι; Επειδή έκανα μια αλλαγή εκεί, επιτρέψτε μου να κάνω μια επιταγή λογική. Επιτρέψτε μου να πάνε όλα το δρόμο πίσω στην αρχή. ΕΝΤΆΞΕΙ. Ένα, two-- yup, βλέπεις; Κάτι δεν πήγαινε καλά. Τρία, τέσσερα, πέντε, έξι, επτά, οκτώ. Και σε αυτό το τελευταίο πέρασμα, είναι μπορείτε άνετα με την επιχειρηση μου ισχυριζόμενος ότι είναι ταξινομημένο; ΕΝΤΆΞΕΙ. Οπτικά, αυτό είναι απολύτως αληθές. Αλλά λειτουργικά, τι είχε μόλις συμβεί σε αυτό το τελευταίο πέρασμα που σας επιτρέπει να επιβεβαιώσει ότι ο κατάλογος αυτός είναι πράγματι ταξινόμηση; 

Τι έκανα ή όχι αυτό το τελευταίο πέρασμα; Κοινό: Δεν υπήρξαν αλλαγές. David J. Malan: Συγνώμη; Κοινό: Δεν υπάρχουν αλλαγές. David J. Malan: Δεν υπήρξαν αλλαγές. Έτσι, θα ήταν ανόητο εκ μέρους μου να κάνει ξανά το ίδιο αλγόριθμο αν δεν είχα κάνει καμία αλλάζει την πρώτη φορά. Και η κατάσταση δεν έχει αλλάξει. Σίγουρα, δεν είμαι πρόκειται να κάνει Οποιεσδήποτε αλλαγές για δεύτερη φορά. Και ναι, είναι ασφαλές τώρα να πω, κατάλογος ταξινομείται. 

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

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

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

Έτσι, χωρίς να πέσουν το στάδιο του τρέχοντος έτους, Πάω να αρπάξει τον αριθμό ένα-- και ποιο ήταν το όνομά σας και πάλι; 

Ανάν Ανάν. 

David J. Malan: Ανάν. Και αν θα μπορούσατε να μου ενταχθούν στο η αρχή της λίστας, ας σας βάλει όπου ανήκετε. Unfortunately-- τι είναι το όνομά σου; 

ΣΤΕΦΑΝ: Stefan. 

David J. Malan: Stefan είναι στο δρόμο. Έτσι, πριν λύνει αυτό Stefan πρόβλημα, τι πρέπει να κάνουμε; Τι θα κάνουμε με τον Stefan; 

Κοινό: [δεν ακούγεται]. David J. Malan: OK. Έτσι θα μπορούσαμε να το κάνουμε αυτό. Θα μπορούσαμε είδος πάρει Stefan και του τέσσερα, και βάλτε την σε μια μεταβλητή και κρατήστε το για να κάποια ποσότητα χρόνου, καθιστώντας έτσι χώρο για το νούμερο ένα. Και αυτό δεν είναι κακό. Θα μπορούσα να προτείνω, γιατί να μην το κάνουμε εμείς απλά βάλτε Stefan εδώ; Γιατί αυτό παραβιάζει ένα από τις ιδέες που ξεκινήσαμε μιλάμε για τελευταία φορά, την περασμένη εβδομάδα; Ναι; 

Κοινό: [δεν ακούγεται]. 

David J. Malan: Δεν υπάρχει ευρετήριο για αυτό. Αν νομίζετε ότι αυτό, πράγματι, ως σειρά, αυτό είναι σαν αρνητικό, οπότε δεν υπάρχει μνήμη πραγματικότητα εδώ, αν αυτό είναι πράγματι ένας πίνακας, όπως δηλώσαμε την περασμένη εβδομάδα στη διάλεξη. Γι 'αυτό και δεν πρέπει να το κάνουμε αυτό. Θα μπορούσαμε να το αποθηκεύσετε σε μια μεταβλητή. 

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

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

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

JOSEPH: Joseph. 

David J. Malan: Joseph; Εμείς πάμε για να αφήσει στη θέση του Ιωσήφ. Τώρα, είμαι πρόκειται να προσποιηθώ ότι αυτοί οι τύποι are-- καλά, Ξέρω ότι αυτά τα δύο είναι ήδη ταξινομημένο. Ας εστιάσουμε τώρα για το υπόλοιπο της λίστας. Έξι είναι η τρέχουσα μικρότερο. Οκτώ είναι μεγαλύτερη. Τέσσερις είναι τώρα η τρέχουσα μικρότερο. Τρεις είναι τώρα η τρέχουσα μικρότερο. Και έτσι τώρα, πάω να επιλέξει τρεις, που is-- τι είναι και πάλι το όνομά σας; SERENA: Serena. David J. Malan: Serena, αν θα μπορούσατε πιάσε τον αριθμό και το swap του δικού σας with-- KALSANG: Kalsang. David J. Malan: Kalsang. Έλα πίσω, και είμαστε πρόκειται να ανταλλάξουν αυτά τα δύο. Και τώρα, ας βάλουμε αυτό στον αυτόματο πιλότο. Πάω να πάει και αφήστε το να σας παιδιά για να επιλέξετε το επόμενο μικρότερο στοιχεία. Dun, Dun, Dun, Dun. Αριθμός τέσσερα, τι πρέπει να κάνετε; Εξαιρετική. Τώρα, είμαι πρόκειται να κάνει άλλο ένα πέρασμα. Dun, Dun, Dun, Dun. Βλέπω πέντε είναι το αμέσως μικρότερο. Τώρα, είμαι πρόκειται να λάβει μια άλλη μπάλα. Dun, Dun, Dun, Dun. Έξι είναι το μικρότερο. Καλή. Επτά είναι το μικρότερο. Καμία αλλαγή. Οκτώ είναι το μικρότερο. Έγινε. 

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

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

Κοινό: [δεν ακούγεται]. David J. Malan: Ναι. Έτσι, υπάρχει κάποια μεγάλη διαίσθηση εκεί. Τα καλά πράγματα φαίνεται να συμβαίνει μέχρι σήμερα στην επιστήμη των υπολογιστών, όταν χωρίζουμε και να κατακτήσει το πρόβλημα της διαίρεσης στη μέση και το μισό και το μισό. Και έτσι πράγματι, εμείς θα μπορούσε να αρχίσει να το κάνουμε αυτό. Και στην πραγματικότητα, αυτό πρόκειται να είναι, θα Βλέπετε, ένα από τα καλύτερα λύσεις μας ακόμα. Αλλά ας επανέλθω στο θέμα αυτό πριν από καιρό. Στην πραγματικότητα, θα πάμε να κάνουμε ότι λίγο αργότερα αυτή την εβδομάδα. Τι άλλο θα μπορούσαμε να κάνουμε για να λύσουμε αυτό; Έτσι, ο καθένας εδώ είναι φαινομενικά τυχαία σειρά. Ξέρεις τι? Αντί να πάει μπροστά και πίσω, εμπρός και πίσω, εμπρός και πίσω κάθε φορά, αυτό το αισθάνεται σαν Κάνω πολύ περπάτημα. Γιατί δεν μπορώ απλά ξεκινούν από η αρχή της λίστας, και απλά βάλτε τέσσερα όπου ανήκει; Επιτρέψτε μου λοιπόν να υποθέσουμε προς στιγμήν ότι λίστα μου είναι μόνο αυτό το πρώτο στοιχείο. Είναι τέσσερις ταξινομημένο σε αυτή τη χρονική στιγμή, αν όλα νοιάζει είναι πάντα εδώ; Αυτό είναι το είδος της κοινότοπα αληθινό, έτσι δεν είναι; Όπως και ο κατάλογος που περιέχει έναν αριθμό, και ότι ο αριθμός τέσσερα είναι προφανώς ταξινομημένο. 

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

JOSEPH: Joseph. 

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

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

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

Ανάν Ανάν. 

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

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

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

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

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

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

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

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

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

Και αν θυμηθούμε ότι πολλοί Στατιστικά του βιβλία ή βιβλία μαθηματικών έχουν τους τύπους αυτούς για την hardcover πίσω ή μπροστά τους, αποδεικνύεται ότι αυτή τη σειρά μπορεί να εκφραστεί πιο απλά δεδομένου ότι οι χρόνοι n n μείον 1 σε 2. Και αυτό είναι καλό, αν αυτό δεν είναι στην πρώτη γραμμή του μυαλού σας. Αλλά αυτό είναι όντως αλήθεια. Αυτό είναι απλά ένας απλούστερος τρόπος της γραφής του. Και στη συνέχεια, αν νομίζετε ότι πίσω στο σχολείο βαθμού, όταν μόλις αρχίσει τον πολλαπλασιασμό τα πράγματα, αυτό φυσικά, είναι ακριβώς n τετράγωνο μείον ν διαιρείται δια 2. Όλα τα έχω κάνει είναι να επεκτείνουν οι εκφράσεις εκεί. Και γι 'αυτό ας ξαναγράψουμε αυτό λίγο διαφορετικά. Αυτό είναι n τετράγωνο διαιρείται δια 2 μείον n / 2. 

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

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

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

Έτσι θα είχαμε τον ίδιο τύπο όπως και πριν. Θα συνδέσετε ένα εκατομμύριο, έτσι ώστε να πάρω ένα εκατομμύριο τετράγωνο διαιρείται με 2, μείον ένα εκατομμύριο διαιρείται δια 2. Αν κάνω ότι τα μαθηματικά των προτέρων Εδώ, έχουμε 500 δισεκατομμύρια μείον 500.000, το οποίο μας δίνει 499.999.500.000, το οποίο είναι αρκετά μεγάλο καταριέται. 

Στην πραγματικότητα, αν συγκρίνουμε τώρα 499 δισεκατομμύρια, 999 εκατομμύρια, 500.000 έναντι αρχικής αξίας μας, 500 δισεκατομμύρια, είναι τόσο βλασφημία κοντά. Σωστά; n τετράγωνο διαιρείται δια 2 δίνει ΕΜΕΙΣ-- ή μάλλον, ν τετράγωνο διαιρείται δια 2 Μας έδωσαν 500 δισεκατομμύρια. Αυτό είναι αρκετά καταριέται κοντά σε 499.999.500.000, το οποίο είναι δηλαδή αφαίρεση off 500.000, ή γενικότερα, αφαιρώντας off n τετράγωνο, δεν είναι πραγματικά μια μεγάλη διαπραγμάτευση. Ο κ τετράγωνο που καθιστά αυτές τις αριθμοί μεγαλώνουν πολύ γρήγορα. 

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

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

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

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

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

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

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

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

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

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

ΕΝΤΆΞΕΙ. Ισχυρίζομαι αυτή τη στιγμή είναι στη θέση του. Αλλά τώρα, seven-- πού επτά πάει; Φυσικά, πηγαίνει εδώ. Γι 'αυτό πρέπει να κινηθεί πάνω από οκτώ ένα μέρος. Τώρα έξι, πού θα πάει; Καλά, εντάξει. Τώρα, έχω να κινηθεί πάνω από οκτώ ένα μέρος, και επτά πάνω από ένα μέρος, και στη συνέχεια να γδούπος κάτω των έξι. 

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

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

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

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

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

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

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

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

Διότι για να βρείτε Mike Smith σε ένα τηλέφωνο το βιβλίο του Ν σελίδες, στη χειρότερη περίπτωση, θα μπορούσε να μου πάρει n βήματα. Τι γίνεται με τη λήψη παρουσιών; Ενα δυο τρια ΤΕΣΣΕΡΑ πεντε εξι. Τι είναι ο χρόνος εκτέλεσης αυτού αλγόριθμος για τη λήψη παρουσιών; Big O του n, επειδή θεωρητικά I Πρέπει να επισημάνω όλοι στην αίθουσα. 

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

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

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

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

Τι είναι ο χρόνος εκτέλεσης του παλαμάκια; Σταθερά χρόνου. Σωστά; Όπως, τι είναι ο χρόνος εκτέλεσης της κάνει κάτι που διαρκεί μόλις ένα λειτουργία, όπως εκτύπωση F Hello World. Αυτό θα μπορούσε να ειπωθεί ότι είναι σταθερά χρόνου, εκτός μικρότερη γωνία με την περίπτωση εκτύπωσης F, Τι θα μπορούσε ο χρόνος τρέχει της εκτύπωσης F πραγματικά είναι; Και γιατι? Τι είναι n μετρήσεων στην περίπτωση αυτή; 

Κοινό: [δεν ακούγεται]. David J. Malan: Ακριβώς. Ο αριθμός των χαρακτήρων που θέλετε να εκτυπώσετε. Έτσι είναι πολύ περιβάλλοντος. Σήμερα, έχουμε εστιάζοντας πολύ για γράμματα και αριθμούς εδώ στο διοικητικό συμβούλιο. Αλλά θα μπορούσε επίσης να είναι χαρακτήρες σε μια πραγματική σειρά. Έτσι αποδεικνύεται ότι υπάρχει μια άλλη μέτρο που θα αρχίσουν να νοιάζονται για, και αυτό είναι το αντίθετο των μεγάλων O, να το πω έτσι. 

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

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

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

Κανένα. Έτσι, ένα κάτω φράγμα για bubble sort θα μπορούσε να ειπωθεί ότι είναι γραμμική. Ωμέγα του ν. Και μπορούμε να εξετάσουμε άλλοι από αυτούς, καθώς και. Έτσι, ας ρίξουμε μια γρήγορη ματιά σε μόλις ένα οπτικοποίηση εδώ για να δούμε πώς αυτές διακρίνουν τους εαυτούς τους. Πάω να πάει κάτω σε αυτό εδώ σελίδα που είναι διαθέσιμη στην ιστοσελίδα του C50, αλλά θα είναι ένας πόνος για να πάρει εργασίας, δεδομένου ότι χρησιμοποιεί μια τεχνολογία που ονομάζεται Βοηθητικές εφαρμογές Java, η οποία είναι μια σε μεγάλο βαθμό δεν υποστηρίζεται αυτές τις μέρες, τουλάχιστον από το Chrome και ορισμένα άλλα. 

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

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

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

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

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

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

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

[Beeping] 

Σύμφωνα με την οποία θέλετε να εφαρμόσετε μια συχνότητα με βάση το ύψος της ράβδου bar. Αυτό είναι bubble sort. 

[Στραβωμένος να χτυπάει] 

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

Ταξινόμηση με συγχώνευση, έτσι νικητής μας πολύ σήμερα. Παρατηρήστε πώς είναι τα πράγματα διαιρώντας σε [δεν ακούγεται] μισά και τέταρτα. Gnome είδος, το οποίο δεν έχουμε μίλησε για, και δημιουργεί οπτικά και audally ένα κομμάτι από ένα διαφορετικό σχήμα και ήχο. Πηγαίνοντας πίσω και εμπρός, καθαρισμού πράγματα. Επίσης, ελέγξτε έξω heapsort στην ιστοσελίδα του άντρα. 

Και αυτό είναι όλο. Θα σας δούμε την επόμενη φορά. 

[Whooshing ΚΑΙ ΜΟΥΣΙΚΗ]