[Παίζει μουσική] David J. MALAN: Εντάξει. Έτσι καλωσορίσω πίσω. Αυτό είναι CS50, και το είναι το τέλος της τρίτης εβδομάδας. Έτσι, υπενθυμίζουν τις τελευταίες αρκετές εβδομάδες, έχουμε δαπανήσει αρκετά ένα κομμάτι της φορά στο C, σχετικά με τον προγραμματισμό, για τη σύνταξη. Και αυτό είναι απολύτως φυσιολογικό, εάν είστε ακόμα αγωνίζεται με Set Πρόβλημα 2, να χτυπάς το κεφάλι σου στον τοίχο. Είναι αινιγματικός εμφάνιση μηνυμάτων σφάλματος και τα σφάλματα που δεν μπορώ να κυνηγήσει. Γιατί, να είστε σίγουροι, ότι μέσα σε μόλις ένα χρόνο λίγες εβδομάδες θα δούμε και πάλι στο πράγματα όπως Καίσαρα, και [? V-genair,?] ίσως ακόμη και κροτίδα, και συνειδητοποιούν πόσο μακριά έχετε έρθει σε σύντομο χρονικό διάστημα. Έτσι, αν αυτό σε παρηγορεί, κολλήσει εκεί για τώρα. Σήμερα, όμως, αρχίζουμε να μετάβαση στα πράγματα υψηλότερο επίπεδο. Και θα αρχίσουμε να θεωρούμε δεδομένο ότι εσείς ξέρετε πώς να προγραμματίσετε, ή τουλάχιστον οι απαρχές της ότι το επίπεδο άνεσης. Και θα αρχίσουμε να εξετάσουμε πώς μπορούμε να πάει για το σχεδιασμό των προγραμμάτων περισσότερα αποτελεσματικά. Πώς μπορούμε να πάμε για τη βελτιστοποίηση της αποδοτικότητα των αλγορίθμων μας, και γενικά επίλυση περισσότερα ενδιαφέροντα προβλήματα. Και αρχίζουν να θεωρούν δεδομένο ότι, αν θέλαμε, θα μπορούσαμε να κωδικοποιήσει έως οποιαδήποτε από τα παραδείγματα που έχουμε στο μυαλό μας. Έτσι, σήμερα, μην αγγίζετε το πληκτρολόγιο για οποιαδήποτε μορφή κώδικα. Θα είναι πολύ υψηλότερο επίπεδο, και τελικά, για την επίλυση προβλημάτων. Έτσι για να φτάσουμε σε αυτό το σημείο, επιτρέψτε μου να προτείνω ότι οι ακόλουθες επτά ορθογώνια αντιπροσωπεύουν επτά πόρτες, πίσω το οποίο είναι ένα σωρό αριθμούς, μεταξύ των οποίων είναι ο αριθμός 50. Επιτρέψτε μου να προβάλει αυτό σε αυτό οθόνη ως εδώ καλά. Και ότι χρειαζόμαστε έναν εθελοντή για να βοηθήσει να βρείτε μου ένα νούμερο μπροστά το διαδίκτυο εδώ για να δείτε. Έλα πάνω, στο ροζ. Εντάξει. Ποιο είναι το όνομά σου; JENNIFER: [δεν ακούγεται] David J. MALAN: Συγνώμη; JENNIFER: Jennifer. David J. MALAN: Jennifer. Εντάξει, Jennifer. Χάρηκα για τη γνωριμία. Ανέβα. Έτσι, αυτά εδώ είναι επτά πόρτες, και τι Θα ήθελα να κάνετε για εμάς εδώ, μπροστά σε όλους τους συμμαθητές σας, είναι να μας βρείτε τον αριθμό, 50. Για να βρείτε έναν αριθμό, μπορείτε να κρυφοκοιτάζει πίσω οποιαδήποτε από αυτές τις πόρτες, αγγίζοντας απλώς σε μία από τις θύρες, και θα αποκαλύψει τον αριθμό του. Και ας δούμε πόσο γρήγορα μπορείτε να μας βρείτε τον αριθμό, 50. 15. 16. 50. Όμορφα γίνει. Εντάξει. Χειροκρότημα για την Jennifer. [Χειροκρότημα] Εντάξει. Λοιπόν, τι ήταν η στρατηγική σας για την βρίσκοντας τον αριθμό, 50; JENNIFER: Um, σκέφτηκα ότι ίσως, αν - [Δεν ακούγεται] David J. MALAN: Αχ. Δώστε ένα δευτερόλεπτο. Έτσι ήταν η στρατηγική σας για την βρίσκοντας τον αριθμό, 50; JENNIFER: Γι 'αυτό ακριβώς ξεκινούν από το αρχίζουμε να βλέπουμε τι ο πρώτος αριθμός ήταν, και τότε σκέφτηκα, ίσως αν από όπου και αν ταξινόμηση, εγώ θα κρατήσει μόνο αγγίζοντας ψηλά; David J. MALAN: OK. Και φαίνεται να έχουν βρει ότι για να είναι η περίπτωση. Αν, ας φλούδα πίσω τα στρώματα λίγο, και θέλετε να πάτε μπροστά και να αποκαλύψει τις άλλες πόρτες θα μπορούσατε να έχετε επιλέξει; JENNIFER: Ω, αγαπητέ. David J. MALAN: Αχ. JENNIFER: Γι 'αυτό ακριβώς στάθηκε τυχερός. David J. MALAN: Έτσι έχεις τύχη. Εντάξει. Έτσι, δεν είναι κακό. Αλλά αυτό είναι μια ενδιαφέρουσα διορατικότητα, έτσι δεν είναι; Αν υποτεθεί, και πήρες, Πράγματι, λίγο τυχερός εκεί. Αλλά αν υποτεθεί ότι οι αριθμοί ήταν ταξινόμηση, μπορείτε να είστε πιο ακριβείς ως προς τον τρόπο που επηρέασε συμπεριφορά σας; JENNIFER: Έτσι, αν είχαν διευθετηθεί, I Σκέφτηκα ότι ίσως το μικρότερο στο μεγαλύτερο. David J. MALAN: OK. JENNIFER: Ή αν αυτό κατέληξε να είναι πραγματικά μεγάλο, τότε το μεγαλύτερο προς το μικρότερο. David J. MALAN: OK. Έτσι, το μεγαλύτερο στο μικρότερο, ή το μικρότερο στο μεγαλύτερο. Αλλά επιτρέψτε μου να προτείνω, ας υποθέσουμε ότι είχατε πάρει άτυχος, και ας υποθέσουμε ότι δεν ήταν, στην πραγματικότητα, ταξινομημένο, πόσοι από οι πόρτες θα είχατε να κρυφοκοιτάζει πίσω στην χειρότερη περίπτωση; JENNIFER: Όλοι τους. David J. MALAN: Όλοι τους. Οπότε ας γενικεύσουμε ότι n. Συμβαίνει να υπάρχει 7, αλλά ας είναι πιο γενικά να πούμε για ν πόρτες για την εκεί οθόνη εδώ. Έτσι, στη χειρότερη περίπτωση, θα έχετε να κοιτάξουμε πίσω από 7 θυρών, ή n πόρτες. Και έτσι αυτό είναι πραγματικά, είναι ένα κομμάτι της τύχη σήμερα, αλλά είναι πραγματικά μια γραμμική αλγόριθμο του είδους, ακόμα κι αν ήταν το είδος των παρακάμπτοντας γύρω. Είναι αυτό δίκαιο; JENNIFER: Ναι. David J. MALAN: Λοιπόν, επιτρέψτε μου να δείτε αν σας αλλαγές στρατηγικής, αν περάσω μας Το δεύτερο παράδειγμά μας εδώ με 7 διαφορετικές πόρτες. Ίδιους αριθμούς, αλλά αυτό φορά που ταξινομούνται. Ποια είναι η στρατηγική σας εδώ θα είναι, προσπαθεί να βάλει έξω από το μυαλό σας τι οι άλλοι αριθμοί ήταν - JENNIFER: OK. David J. MALAN: - νωρίτερα; JENNIFER: Ας ξεκινήσουμε με το πρώτο. David J. MALAN: Εντάξει. Ξεκινήστε με το πρώτο. 4. Τώρα, πού θα πας, και γιατί; JENNIFER: 4 είναι πραγματικά μικρό. Έτσι, εάν είστε το είδος ίσως μικρότερο στο μεγαλύτερο, θα πρέπει είναι διπλάσιο από αυτό, και -. David J. MALAN: OK. Ας δούμε, ποια η γνώμη σας; JENNIFER: Δοκιμάστε το τελευταίο. Νίκαια. David J. MALAN: Πολύ όμορφα γίνεται. Εντάξει. [Χειροκρότημα] David J. MALAN: OK. Έτσι, είστε πραγματικά κάνει αυτό Σκληρό, επειδή είστε κάνει πολύ καλά. Που μας αφήνει σε θέση να κάνει ορισμένα σημεία. Έτσι, ας προσπαθήσουμε να επαναφέρετε εδώ. JENNIFER: OK. David J. MALAN: Πολύ καλά γίνει, παρ 'όλα αυτά. Έτσι ξεκίνησε στις αρχές, είδατε ότι ήταν 4, τότε μεταφέρθηκε στο τέλος. Αλλά ας υποθέσουμε ότι δεν έχετε πάρει τυχερός εκεί, και ας υποθέσουμε ότι 50 ήταν κάπου αλλού. Ποια τρίτο βήμα σας έχουν; JENNIFER: Πήγαινε πίσω στην αρχή. David J. MALAN: Πήγαινε πίσω στην αρχή. Εντάξει, έτσι θα έχετε αγγίξει αυτή η πόρτα, η οποία ήταν 8. Εντάξει. Έτσι, αυτό δεν είναι 50. Πού θα έχετε εξετάσει το επόμενο βήμα; JENNIFER: Αν δεν είχα γνωρίζουν ότι ταξινομημένο. David J. MALAN: Σωστό. Λοιπόν, αν ξέρατε είχαν ταξινόμηση - JENNIFER: Αχ, δεν ξέρω, ναι. David J. MALAN: - αλλά δεν το έκανε ξέρετε όπου το 50 ήταν ακόμα; JENNIFER: Απλά συνεχίζω. David J. MALAN: Εντάξει. OK. Συνεχίστε. Εντάξει, ότι μπορώ να συνεργαστώ μαζί της. JENNIFER: OK. David J. MALAN: Τώρα, αν είστε απλά Θα συνεχίσουμε, τι σας αλγορίθμου έχουν ανατεθεί υποστηρίζεται σε. JENNIFER: Η γραμμική -. David J. MALAN: Είναι το είδος της γραμμικής. Αλλά επιτρέψτε μου να προτείνω, ας με έβαλε επί τόπου. Επιτρέψτε μου να ανανεώσετε τη σελίδα. ίδιο αριθμό, ίδια διάταξη, ίδιες πόρτες. Αλλά σκεφτείτε πίσω σε εκείνη την πρώτη ημέρα τάξη όταν έσκισε ένα βιβλίο τηλέφωνο εξάμηνο, είδος, και ό, τι ήταν στρατηγική μας εκεί; JENNIFER: Έναρξη στη μέση. David J. MALAN: OK. Έτσι, ξεκινούν στη μέση. Οπότε ας πάμε μπροστά και να μιμηθεί αυτό. Ξεκινήστε στη μέση από αποκαλύπτοντας την πόρτα. Έτσι, ο αριθμός 16. Λοιπόν, τι θα το ισχυρό άντρα έχουν κάνει, που έσκισε τον τηλεφωνικό κατάλογο στη μέση, για να φτάσουμε στην επόμενη εικασία; JENNIFER: Πηγαίνετε σε αυτό το μισό. David J. MALAN: Και γιατί προς τα δεξιά; JENNIFER: Αν ήταν είδος του μικρότερου στο μεγαλύτερο, τότε θα πρέπει να είναι 50 στο άκρο αυτό. David J. MALAN: Good. Απόλυτα λογικό. Έτσι, όπως ένα τηλεφωνικό κατάλογο, πηγαίνετε στο δεξιά, σε αντίθεση προς τα αριστερά, αλλά εδώ είναι το κλειδί σε πακέτο. Μπορείτε τώρα να πετάξουν, ή αποσπώμενο, το ήμισυ αυτού του προβλήματος, αφήνοντας σας δεν με 7 θύρες, αλλά πραγματικά με μόλις 3. Ποιο είναι περίπου το μισό από το το μέγεθος του προβλήματος. Εντάξει. Και τώρα τι θα είχατε γίνεται μετά πάτε καλά; JENNIFER: Μέχρι 16 εξακολουθεί να είναι αρκετά μικρή, σε σχέση με το 50, οπότε ίσως θα προσπαθήσω, όπως, αυτό. David J. MALAN: Εντάξει. 42. Εντάξει, τώρα τι σας ένστικτο σας λέει; JENNIFER: Μπορώ να πετάξετε αυτό και στη συνέχεια απλά - David J. MALAN: OK. Καλό, μπορείτε να πετάξετε το αριστερό μισό εκεί. JENNIFER: - να πάρει αυτό το ένα. David J. MALAN: Και το δικαίωμα. JENNIFER: Ναι. David J. MALAN: Έτσι, ακόμα κι αν είναι δύσκολο για να δούμε ίσως, όταν υπάρχει μόνο 7 πόρτες, σκέφτομαι, τώρα, η συνοχή της αλγόριθμος που μόλις εφαρμοστεί. Στην προηγούμενη περίπτωση, κάνατε πάρετε τυχεροί, η οποία ήταν μεγάλη. Αλλά κάνατε χρησιμοποιήσετε μια ευρετική, Θα ήθελα να πω. Θα χρησιμοποιηθεί το είδος των ένστικτό σας, και γνωρίζοντας την ταξινόμηση, αν είναι αρκετά μικρό στην αρχή, προφανώς, έχουμε Πρέπει να πάει πιο δεξιά. Αλλά κατά κάποιο τρόπο, έχεις τυχερός, γιατί ίσως αυτό ήταν ο αριθμός 100, και ίσως 50 ήταν περισσότερο στη μέση. Ίσως 50 ήταν ακόμη εδώ. Αλλά αυτό που έκανε λίγο διαφορετικά αυτή τη φορά ήταν, θα έκανε το ίδιο πράγμα ξανά και ξανά. Και θα έλεγα ότι αυτό που μόλις έκανε, αν και επηρεάζονται από το τηλέφωνο book παράδειγμα, είναι κάτι πολύ πιο αλγοριθμική, και πολύ λιγότερο ειδικό κάλυκα. Πολύ λιγότερο ενστικτώδης. Έτσι, στο τέλος της ημέρας, πώς θα θα περιγράφουν την αποτελεσματικότητα της πρώτο αλγόριθμο, όπου πήγε αριστερά προς τα δεξιά, σε σχέση με το δεύτερος αλγόριθμος εδώ; JENNIFER: αυτό θα πρέπει, όπως, ίσως μείωση κατά το ήμισυ του χρόνου, ή ακόμη περισσότερο, ναι. David J. MALAN: Εντάξει, ίσως ακόμη περισσότερο. Ας πιέσουμε λίγο πιο δύσκολο σε αυτό. Αυτό που πραγματικά, αν συνεχίσουμε αυτή λογική, είμαστε κατά το ήμισυ σίγουρα η χρόνου λειτουργίας με αυτή τη δεύτερη αλγόριθμο ρίχνοντας το μισό του αριθμούς, αλλά τι κάναμε εμείς για την επόμενη επανάληψης, όταν η Jennifer αποκάλυψε Ο δεύτερος αριθμός; Εμείς κατά το ήμισυ τον αριθμό των θυρών και πάλι. Και μετά τι κάναμε εμείς μετά από αυτό, αν υπήρχαν περισσότερες πόρτες για να παίξει με; Εμείς θα τους μειωθεί κατά το ήμισυ, και πάλι, και ξανά, και ξανά. Και αυτό ήταν ακριβώς όπως εσείς όλα όρθιος κατά την πρώτη εβδομάδα του τάξη, οι μισοί από εσάς που κάθεστε κάτω, το ήμισυ σας που κάθεστε κάτω, οι μισοί από εσάς κάθεται κάτω, έως ότου ένας μοναχικός η ψυχή στεκόταν. Και είπαμε ότι ο χρόνος εκτέλεσης του ότι, ο αριθμός των βημάτων που χρειάστηκε ήταν με τη σειρά της, τι; ΟΜΙΛΗΤΗΣ 1: [δεν ακούγεται] David J. MALAN: Έτσι βάσης log 2 n, ή απλά πιο απλά, συνδεθείτε του n. Έτσι, κάτι λογαριθμική. Και η γραφική παράσταση δεν ήταν μια ευθεία γραμμή αυτό ακριβώς γινόταν όλο και χειρότερη, ήταν αυτό το ενδιαφέρον καμπύλη που δεν να πάρει τόσο άσχημα την πάροδο του χρόνου. Οπότε ας παραμείνουμε σε αυτή την ιδέα. Ας ευχαριστήσουμε Jennifer. Ευχαριστώ πολύ που ήρθατε πάνω. Και, ένα sec. Δεν λάμπες γραφείου σήμερα, αλλά εμείς έχουν CS50 μπάλες άγχος. JENNIFER: Yay. David J. MALAN: Εντάξει, εδώ. Σας ευχαριστούμε για τη θεμελίωση το άγχος μέχρι εδώ. Εντάξει. Έτσι, ας δούμε αν μπορούμε όχι τώρα επισημοποιήσει αυτό το λίγο περισσότερο. Έτσι και πάλι, αυτό που μόλις έκανε ήταν ουσιαστικά το ίδιο πράγμα, όπως κάναμε σε αυτή την πρώτη εβδομάδα. Αλλά αντί να τελειώνουν με ένα γραμμικό αλγόριθμος, το οποίο απεικονίζεται στο παρελθόν, όπως αυτή ευθεία γραμμή, σύμφωνα με την οποία, αν βάλουμε ένα ακόμη πόρτα η οθόνη, τότε η Jennifer θα έπρεπε να εξετάσει, ενδεχομένως, πίσω από το ένα περισσότερα πόρτα. Αν βάλουμε δύο πόρτες, θα μπορούσε να έχει να κοιτάξουμε πίσω από δύο πόρτες. Και έτσι, δεν υπήρχε αυτή η γραμμική σχέση μεταξύ του μεγέθους του πρόβλημα, ας πούμε, το x-άξονα, και το ποσό του χρόνου που χρειάζεται για να λύσει την y. Αλλά η εικόνα που αναφερόταν στην Νωρίτερα ήταν αυτή η πράσινη γραμμή. Πράσινο σκόπιμα, γιατί αυτό ακριβώς αισθάνθηκε καλύτερα. Στη θεωρία, ο αλγόριθμος, όταν κάναμε με τον τηλεφωνικό κατάλογο, όταν κάναμε μαζί σας μετράει ο ένας τον άλλον, και στη δεύτερη περίπτωση, όταν Jennifer μόνο έκανε μέχρι εδώ, ήταν ένα είδος θεμελιωδώς καλύτερα. Επειδή δεν ήταν μόνο δύο φορές πιο γρήγορα. Δεν ήταν ακόμα και τέσσερις φορές πιο γρήγορα. Ήταν εξαρτάται εξ ολοκλήρου από ό, τι η μέγεθος της εισόδου ήταν, ως προς το πόσα μέτρα που τελικά πήρε. Και έτσι αυτή η απλή ιδέα ότι όλοι πήραν δεδομένο με τον τηλεφωνικό κατάλογο, μπορεί παρομοίως να εφαρμοστεί σε κάτι σαν αυτό. Και αυτό θα μπορούσε να είναι πιο άνετα γνωστή ως, όπως μπορείτε να φανταστείτε, διαίρει και βασίλευε. Δεν σε αντίθεση με ό, τι κάναμε, φυσικά, με τον τηλεφωνικό κατάλογο. Αλλά ο ψευδοκώδικας, ανάκληση, ήταν αυτό. Έτσι, δεν θα το κάνουμε αυτό και πάλι, αλλά υπενθυμίζουν ότι η πρώτη εβδομάδα, όλοι μας σηκώθηκε και στη συνέχεια μισό από εσάς κάθισε, το ήμισυ των που κάθισε, οι μισοί από εσάς κάθισε. Ότι ο αλγόριθμος υλοποιήθηκε σε ένα bit του τρόπο εξαπάτησης, σε αυτό, Δεν ήταν μόνο ένας από εμένα καταμέτρηση, ριζικά, πιο αποτελεσματικά. Σε αυτή την περίπτωση, ήμουν μόχλευση μια δευτερεύουσα πόρο. Ταξινόμηση της, πολλαπλές CPUs, πολλαπλές μυαλά, πολλαπλές έξυπνοι άνθρωποι στην δωμάτιο ήταν βοήθειά μου από κάτι γραμμική σε κάτι λογαριθμική, από κάτι κόκκινο σε πράσινο κάτι. Αλλά στην περίπτωση αυτή, η Jennifer μπορεί μόνη της βελτιώσει ουσιαστικά μετά το απόδοση του πρώτου αλγορίθμου της από, και πάλι, απλά να σκεφτόμαστε λίγο πιο δύσκολο. Και τώρα, όταν έρχεται η ώρα για την εφαρμογή αυτά τα πράγματα, υπολογίζοντας Τι γραμμές κώδικα μπορείτε να γράψετε τέτοια ότι μπορείτε να τα επαναλάβω και πάλι, και πάλι, και πάλι, είδος σε ένα looping μόδας. Επειδή εσείς δεν πρόκειται να έχει το πολυτελείας, όπως η Jennifer έκανε σε πρώτη φάση, να απλά έχουν ένα σωρό ifs και να πω, Χμμ, αν αυτό πρώτος αριθμός είναι 4, επιτρέψτε μου να πηδήξει σε όλη τη διαδρομή μέχρι το τέλος. Ooh, εάν ο αριθμός αυτός είναι πολύ μεγάλο, επιτρέψτε μου να προχωρήσω αυθαίρετα πίσω με το δεύτερο στοιχείο. Θα διαπιστώσετε ότι πρόκειται να είναι ένα πολύ πιο δύσκολο να επισημοποιήσει ό, τι εμείς οι άνθρωποι θεωρούμε δεδομένο ως πολύ λογικές heuristics, αλλά ένας υπολογιστής είναι μόνο Θα κάνουμε ό, τι πει να το κάνει. Τώρα αυτό έχει πολύ ενδιαφέρον επιπτώσεις. Το γράφημα αυτό είναι το είδος της γραφτό να ταξινομήσετε του συντρίψει οπτικά, αλλά η ανακοίνωση, όπου είναι η ευθεία γραμμή σε αυτό το γράφημα; Πού είναι η γραμμική γραφική παράσταση που ονομάζουμε ν? Λοιπόν, αυτό είναι το είδος του προς τον πυθμένα από αυτή την εικόνα, έτσι δεν είναι; Έτσι, το μόνο που έχω κάνει είναι ότι έχουμε το είδος της μεγεθυνθεί έξω στο χ-άξονα και τον y-άξονα για να προσπαθήσετε να πάρετε μια αίσθηση του τι άλλα είδη καμπύλες μοιάζουν. Και οι ιδιαιτερότητες των μαθηματικών εκφράσεις σήμερα δεν θα έχει σημασία τόσο πολύ, αλλά παρατηρήσετε ότι υπάρχει μια πολύ αλγόριθμους που είναι πολύ χειρότερη από ό, τι κάτι που είναι γραμμική. Πράγματι, n κύβους φαίνεται αρκετά άσχημα. 2 του Ν φαίνεται αρκετά άσχημα. n τετράγωνο φαίνεται αρκετά άσχημα. Και θα δούμε τι μερικά από αυτά μπορεί να είναι στην πραγματικότητα σήμερα. Και log n δεν αισθάνεται τόσο άσχημα, αλλά καλύτερα από ό, τι η είναι log βάσης 2 του Ν. Αλλά ξέρετε, θα ήταν ακόμη πιο εκπληκτικό, αν Jennifer, ή αν, ότι η πρώτη εβδομάδα, είχε έρθει με κάτι που είναι ημερολόγιο της καταγραφής των n. Έτσι με άλλα λόγια, υπάρχει όλο αυτό το εύρος των πιθανών λύσεων για την προβλήματα, αλλά ακόμη και εδώ, ανακοίνωση τι πρόκειται να συμβεί. Όταν σμίκρυνση, ποια από αυτές τις καμπύλες πρόκειται να αποδείξει ότι είναι ο απόλυτος χειρότερα από αυτά που εμφανίζονται στην οθόνη τώρα; Έτσι, n κύβους φαίνεται αρκετά κακό αυτή τη στιγμή. Αλλά αν σμίκρυνση και να δείτε περισσότερα από τα x και η y-άξονα, ο οποίος πρόκειται να κυριαρχήσει τελικά; Έτσι αποδεικνύεται πράγματι ότι η 2 n, και μπορείτε να το καταλάβουν αυτό μόνο από συνδέσετε σε κάποια πιο μεγάλη αριθμούς, και θα δείτε ότι 2 η n, πράγματι, μεγαλώνει πολύ πιο γρήγορα. Αν θέλουμε πραγματικά σμίκρυνση, μια 2 η n αλγόριθμος είναι τελείως χάλια. Θέλω να πω ότι αυτό πρόκειται να λάβει αρκετά ένα κομμάτι του χρόνου για την υπολογιστή και να βγάλεις μέσα. Αλλά θα δείτε την πάροδο του χρόνου, ειδικά με τις μελλοντικές σειρές πρόβλημα και ακόμη τελικών σχεδίων, είναι τα δεδομένα σας που παίρνει μεγάλες, εντάξει; Ακόμη και στην πρώτη έκδοση του Facebook, καθώς ο αριθμός των φίλων, και το αριθμός των εγγεγραμμένων χρηστών πήρε μεγάλες, μπορείτε να ταξινομήσετε από το τηλέφωνο και να εφαρμόσουν κάτι με γραμμική αναζήτηση, ή μια πολύ απλή διαλογή αλγόριθμο, όπως θα δούμε σήμερα. Θα πρέπει να αρχίσουμε να σκεφτόμαστε πιο δύσκολο και πιο δύσκολο για τα προβλήματα αυτά. Και τα είδη των προβλημάτων μέρη όπως Facebook και Google, και η Microsoft, και άλλοι δουλέψουμε είναι ακριβώς αυτά είδος μεγάλου είδους δεδομένων των ερωτήσεων ολοένα και περισσότερο αυτές τις μέρες. Εντάξει. Έτσι, η επιτυχία της Jennifer σε αυτό το δεύτερο αλγόριθμο, ειλικρινά, έκανε εκπληκτικά και η πρώτη φορά, αλλά ας γράψετε όπως τύχη, έτσι ώστε να μπορεί να κάνει αυτό το σημείο. Στη δεύτερη περίπτωση, που θα αξιοποιηθούν αλγόριθμο που επαναλαμβάνονται ξανά και και πάλι, αλλά πήρε ως δεδομένο ένα ορισμένες παραδοχή ότι επιτρέψαμε της, αλλά εκμεταλλεύονται κάποιες λεπτομέρειες το δεύτερη φορά ότι δεν έχει την πρώτη φορά. Ποιο ήταν αυτό; Ότι ο κατάλογος ήταν ταξινομημένο. Έτσι, μόλις ο κατάλογος με ταξινόμηση, έχουμε ισχυρίζονται ότι η Jennifer ήταν σε θέση να κάνει θεμελιωδώς καλύτερα. 7 πόρτες, ναι, δεν είναι και τόσο ενδιαφέρον, αλλά ας υποθέσουμε ότι είμαστε 7 εκατομμύρια πόρτες. Σύνδεση του n είναι σίγουρα πρόκειται να εκτελέσει πολύ, πολύ γρηγορότερα σε μακροπρόθεσμη βάση. Αλλά έπρεπε να έχει το πόρτες ταξινόμηση γι 'αυτήν. Τώρα, πήρα το θάρρος να το κάνουμε αυτό εκ των προτέρων στην οθόνη του υπολογιστή εδώ, αλλά ας υποθέσουμε ότι η Jennifer είχε να κάνει ότι τον εαυτό της; Ας υποθέσουμε ότι οι πόρτες εν λόγω εκπροσωπούνται τα δεδομένα σε μια βάση δεδομένων, ή φίλους εγγραφεί για το Facebook, ή οποιεσδήποτε ιστοσελίδες στο διαδίκτυο που διάφορες ιστοσελίδες μπορεί να χρειαστεί στο δείκτη ή την αναζήτηση πάνω. Ας υποθέσουμε ότι είχατε μόνο μια πρωτογενή δεδομένα που και αυτό έμεινε σε εσάς, ή για να Jennifer να το κάνουμε αυτό διαλογής; Αυτό, μάλλον, απαιτεί να απαντάμε το ερώτημα, καλά, πόσο χρόνο θα έχουν λάβει Jennifer, ή ακόμα και εγώ, για να ταξινομήσετε τους αριθμούς των προτέρων, ώστε ότι θα μπορούσε να επωφεληθεί από αυτό; Σωστά; Επειδή η επίπτωση, φυσικά, είναι και αν μου πάρει πολύ λίγο χρόνο για να ταξινομήσετε οι αριθμοί, ποιος στο καλό νοιάζεται σας ότι μπορείτε να βρείτε μια σειρά όπως 50 τόσο γρήγορα, όπως στην περίπτωση της Jennifer, αν έχουμε περισσότερο από κυριεύσει το ποσό του συνολικού χρόνου πήρε από τη διαλογή τα πράγματα εκ των προτέρων; Έτσι, ας δούμε αν δεν μπορούμε να το ζωγραφίσει την εικόνα εδώ. Έχω ένα σωρό περισσότερο άγχος μπάλες, αν αυτό βοηθάει να σπάσει τον πάγο εδώ. Και αν δεν θα με πείραζε, θα Πρέπει επτά εθελοντές - στο, OK. Wow. Έτσι, δεν έχουμε να δαπανήσει για λάμπες γραφείου, φαίνεται. Εντάξει. Έτσι, σχετικά με το πώς εσείς οι δύο μπροστά. Τι θα λέγατε εσείς οι δύο άντρες στην πλάτη. Έτσι ώστε να είναι τέσσερις. Πώς για σας μπροστά πέντε, έξι και επτά. Ακριβώς εκεί. Του φίλου σας μπορείτε επισημαίνοντας, έτσι μπορείτε να πάρετε το βραβείο. Εντάξει. Ανέβα. Και γιατί δεν έχετε παιδιά έρχονται για πάνω από εδώ. Πάω να σας δώσω σε κάθε έναν αριθμό. Και πάει μπροστά και να οργανώσει τον εαυτό σας πανομοιότυπα με ό, τι είναι απεικονίζεται στην οθόνη. [Παρεμβάλλοντας VOICES] David J. MALAN: Oop, συγγνώμη. Bug. Εντάξει. Λοιπόν, εδώ είμαστε. Αριθμός πέντε. Αριθμό έξι. Ένα, δύο, τρία, τέσσερα, πέντε, έξι, επτά. Ω, αυτό είναι περίεργο. ΟΜΙΛΗΤΗΣ 2: Θα πάρει μόνο ένα -. David J. MALAN: Good deal. Εντάξει. Σας ευχαριστούμε για τη συμμετοχή σας. [Χειροκρότημα] OK. Εντάξει. Έτσι έχουμε τέσσερις, δύο, έξι, ένα, τρία, επτά, πέντε. Τέλεια έτσι έχουμε επτά εθελοντές εδώ οι οποίοι είναι ίση σε πλάτος με το σειρά που παίζουμε με την προηγούμενη. Και επέλεξα επτά για λόγους που θα είναι ακριβώς βολικό σε λίγο. Και Πάω να προτείνει, πρώτον, ότι ταξινομούμε αυτά τα επτά εθελοντές. Αν θέλετε, πρώτη, να πω γεια όμως. Δεδομένου ότι αυτό πρόκειται να είναι ένα αδέξιο αρκετά λεπτά. Συστηθείτε. GRACE: Γεια σου, είμαι Γκρέις. Είμαι δευτεροετής φοιτητής στο Leverett Βουλή. BRANSON: Hi. Είμαι Branson. Είμαι πρωτοετής στο Weld. GABE: Hi. Είμαι Gabe. Είμαι μια junior στο Cabot. NEIL: Είμαι Neil. Είμαι πρωτοετής στο Matthews. ΙΑΣΩΝ: Είμαι Jason. Είμαι πρωτοετής στο Greenough. MIKE: Είμαι Mike. Είμαι πρωτοετής στο Grays. JESS: Είμαι Jess. Είμαι δευτεροετής φοιτητής στο Leverett. David J. MALAN: Excellent. Εντάξει. Λοιπόν, σας ευχαριστώ σε όλους μας εθελοντές εδώ μέχρι στιγμής. Και η πρόκληση αυτή τη στιγμή είναι τώρα σε εξέλιξη να είναι να ταξινομήσετε από αυτά τα παιδιά, αλλά στη συνέχεια θα πάμε να πρέπει να σκεφτείτε λίγο σκληρά για το πόσο αποτελεσματικά μπορούμε πραγματικά ταξινόμηση τους. Έτσι, ας προσπαθήσουμε πρώτα αυτό. Εσείς μπορείτε να δείτε τους αριθμούς του άλλου απλά με την τοποθέτηση γύρω από τις γωνίες. Προχωρήστε και να διαρκέσει μερικά δευτερόλεπτα, και Ταξινόμηση ίδιοι από το μικρότερο σχετικά με την αριστερά στο μεγαλύτερο δεξιά. Go. OK. Καλό. Αυτό ήταν πραγματικά καταριέται γρήγορα. Τώρα κάποιος εδώ, τι ήταν ο αλγόριθμος ότι αυτοί οι τύποι που εφαρμόζονται; ΟΜΙΛΗΤΗΣ 1: Τουλάχιστον στο μέγιστο. David J. MALAN: OK. Τουλάχιστον στο μέγιστο είναι πραγματικά ταξινομήσετε του στόχος, αλλά δεν είμαι βέβαιος ότι είναι πραγματικά ένας αλγόριθμος. Τουλάχιστον σε μεγαλύτερο δεν λέει μου βήμα-βήμα τι πρέπει να κάνουμε. Ναι; ΟΜΙΛΗΤΗΣ 1: [δεν ακούγεται] David J. MALAN: OK. Έτσι, αν δείτε ένα πρόσωπο μικρότερο από τον αριθμό σας, στη συνέχεια να προχωρήσουμε σε η δεξιά τους. Έτσι ώστε να είναι πλέον όλο και πιο εκφραστική, περισσότερο σαν έναν αλγόριθμο, γιατί μπορούμε να πούμε, αν αυτό, στη συνέχεια, ότι. Έτσι έχουμε κάποιο είδος όρους κατασκεύασμα. Και αυτά τα παιδιά φαίνεται να το κάνει αυτό μερικές φορές, επειδή κάποιοι από εσάς μετακινηθεί λίγο μιας αποστάσεως. Έτσι, δεν υπήρχε προφανώς κάποιο είδος looping συμβαίνει στο μυαλό τους. Αλλά ας προσπαθήσουμε να επισημοποιηθεί αυτό. Αν εσείς θα μπορούσε να επαναφέρει πίσω σε αυτή τη συμφωνία. Ας δούμε αν δεν μπορούμε να επισημοποιήσει αυτή την bit, και στη συνέχεια να ζητήσει από την ερώτηση, απλά πόσο αποτελεσματική είναι αυτό; Φυσικά, όταν το κάνουμε αυτό πιο αργά, πρόκειται να αισθάνονται τόσο καλή ένας αλγόριθμος, αλλά ας δούμε αν μπορούμε να βάλτε τα δάχτυλά μας για τα ακριβή βήματα. Έτσι οι δύο τύποι είναι τέσσερις και δύο. Ή μπορείτε σωστές ή λάθος σειρά; Προφανώς λανθασμένη. Γι 'αυτό και αντάλλαξαν. Τώρα είμαι πρόκειται να παραμερίστε εδώ και να πω, τέσσερις σε έξι. Είσαι σωστή ή λάθος; GABE: Σωστό. David J. MALAN: Σωστό. Έξι και μία; Όχι. Swap. Έτσι ώστε είναι δύο swaps. Έξι και τα τρία; Όχι. Swap. Έξι και επτά; Φαίνεται καλό. Επτά και πέντε; JESS: [δεν ακούγεται] David J. MALAN: OK, swap. Και ταξινομημένο. Εντάξει. Έτσι δεν είναι, προφανώς, έτσι δεν είναι; Υπήρχε, λοιπόν, περισσότερο σε εξέλιξη. Αλλά, πράγματι, αυτά τα παιδιά, ακόμα και μόνο ενστικτωδώς. συνέχισε να κινείται. Δεν έκανε ακριβώς να σταματήσει, από τη στιγμή που διορθωθεί ένα πρόβλημα. Έτσι. Πράγματι, είμαι πρόκειται να έχουν να κάνουν το ίδιο πράγμα. Πάω να πρέπει να λύσουμε από πίσω προς τα πίσω στην αρχή αυτού του προβλήματος, ή η αρχή αυτού του συστοιχία ανθρώπους, ας αρχίσουμε καλώντας τους. Και τώρα τι θα πρέπει αλγόριθμο μου στο δεύτερο πέρασμα είναι; ΟΜΙΛΗΤΗΣ 1: Το ίδιο πράγμα. David J. MALAN: Το ίδιο πράγμα. Και αυτό, αρχίζω να αρέσει, έτσι δεν είναι; Μόλις μπορείτε να βρείτε τον εαυτό σας να κάνει το ίδιο πράγμα ξανά και ξανά, αυτό είναι όλο και περισσότερο σαν ένα αλγόριθμο, και λιγότερο ανθρώπινο ένστικτο. Έτσι τώρα, εδώ πηγαίνουμε πάλι. Δύο και τέσσερα; Όχι. Τέσσερα και ένα; Αχ, υπήρξε πράγματι κάποια λειτουργούν ακόμη να γίνουν πολλά. Για και τρεις; Καλό. Τέσσερις και έξι; Έξι και πέντε; Έξι και επτά; Εντάξει, τώρα, γίνει. Εντάξει, όχι. Πρέπει να πάω πίσω. Έτσι τώρα, και πάλι, το κάνουμε αυτό λίγο πιο συνειδητά. Και τώρα, υπάρχει μόνο έναν εγκέφαλο εκτέλεση αυτού του αλγορίθμου. Μία CPU, αν θέλετε. Και ειλικρινά, αυτός είναι ο μόνος πόρος θα πάμε να έχουν πρόσβαση. Και όταν εμείς πάμε πίσω σε ένα πληκτρολόγιο και να έχουν κάτι σαν C σε μας διάθεση, γράφουμε μόνο ένα πρόγραμμα ότι μπορεί να κάνει ένα πράγμα τη φορά. Ότι, αυτά τα παιδιά πριν από λίγο, εμείς μόχλευση συλλογική ευφυΐα τους όπως σ 'εσάς στην εβδομάδα μηδέν. Ας συνεχίσουμε να το κάνουμε αυτό. Δύο και μία. Δύο και τρία. Τρία και τέσσερα. Τέσσερα και πέντε. Πέντε και έξι. Έξι και επτά. Έγινε; Είμαι, λοιπόν, αλλά επιτρέψτε μου να παίζουν συνήγορο του διαβόλου. Do I, το είδος του υπολογιστή που μόλις έκανε ένα πέρασμα μέσα από αυτή τη σειρά των οι άνθρωποι, ξέρουν ότι είμαι γίνει; ΟΜΙΛΗΤΗΣ 1: Όχι. David J. MALAN: ναι, γιατί; Τι θα πρέπει να κάνω για να συμπέρασμα αποφασιστικά ότι έχω κάνει; Πιθανώς ένα ακόμη περάσει. Σωστά; Επειδή το μόνο που ξέρω από την προηγούμενη pass είναι ότι έχω διορθωθεί ένα λάθος. Και αυτό σημαίνει, ίσως υπάρχει ακόμα ένα άλλο λάθος ότι πρέπει να διορθωθεί. Γι 'αυτό να είστε σίγουροι από κουρδίζεται, και τότε τον έλεγχο, ένα έως δύο, δύο και τρία, τρία και τέσσερα, τέσσερα και πέντε, πέντε και έξι, έξι και επτά. Εντάξει, τώρα έκανα καμία εργασία. Μπορώ σίγουρα να θυμάστε ότι έκανα κανένα συνεργαστεί με κάτι σαν μια μεταβλητή, όπως έναν int. Καλέστε swaps, και αν swaps είναι 0 αφού την έχω πάρετε εδώ, και που άρχισε στο 0, τότε Θα ήθελα απλά να είναι ανόητο να συνεχίζω εμπρός και πίσω, τον έλεγχο και πάλι, και ξανά και ξανά, έτσι δεν είναι; Επειδή έχετε κολλήσει σε ορισμένες είδος άπειρο βρόχο. Έτσι, το συντομότερο υπάρχει 0 swaps, μπορούμε να ισχυριστούμε ότι αυτή η αλγόριθμος είναι πράγματι πλήρης. Τώρα, ας βάλουμε ένα όνομα για το θέμα αυτό. Ο αλγόριθμος που προτείνουμε μόνο εφαρμοστεί είναι κάτι που ονομάζεται φυσαλίδα Ταξινόμηση, που είναι γνωστή ως τέτοια κατά την έννοια ότι οι αριθμοί που είναι μεγαλύτερα του είδους του φούσκα δρόμο τους προς την κορυφή, ή μέχρι στο τέλος της συστοιχίας των αριθμών. Αλλά πόσο αποτελεσματική ήταν ο αλγόριθμος αυτός; Πόσα βήματα εγώ φυσικά πρέπει να να λάβει, για παράδειγμα, για να ταξινομήσετε αυτά επτά ανθρώπους; Τέσσερις με πέντε; OK, πάρα πολλά είναι τελικά πρόκειται να είναι η απάντηση. Αλλά ακόμα και τότε, ο συγκεκριμένος αριθμός δεν είναι τόσο ενδιαφέρουσα. Ας το γενικεύσουμε ως n. Έτσι, αν είχα n ανθρώπους εδώ, και ήταν, είδος, σε τυχαία σειρά στο αρχή, σε αυτή την αρχική σειρά. Λοιπόν, πόσα βήματα δεν έχω να αναλάβει το πρώτο πέρασμα; Ήταν ένα, δύο, τρία, τέσσερα, πέντε, έξι, και είναι επτά άτομα, έτσι ώστε αυτό είναι επτά, έξι -, έτσι ώστε να είναι n μείον ένα βήματα την πρώτη φορά. Τώρα, πόσα βήματα δεν έχω να ληφθούν όταν rewound; Λοιπόν, θα μπορούσε πραγματικά να διπλασιαστεί ότι εάν θέλαμε πραγματικά, αλλά για τώρα, είμαι ακριβώς πρόκειται να πω, εντάξει, Ένας άλλος N μείον 1. Έτσι, το n μείον 1 πρόκειται να πάρει ενοχλητικό να παρακολουθείτε, οπότε ας απλά στρογγυλοποιεί προς τα πάνω ελαφρά. Έτσι 2n βήματα. Μέχρι 14 βήματα, ή να δώσει. Πόσες φορές δεν έχω λάβει ένα βήμα προς την επόμενη φορά; Λοιπόν, αυτό είναι 3η. πραγματικά. Και τώρα, στη χειρότερη περίπτωση, για παράδειγμα, πόσες φορές θα έχω πάει εμπρός και πίσω, εμπρός και πίσω, εκτελεί αυτόν τον αλγόριθμο, ανταλλάσσοντας οι άνθρωποι σε κάθε πέρασμα, περίπου; Είναι πραγματικά n τετράγωνο, έτσι δεν είναι; Επειδή στη χειρότερη περίπτωση, μπορείτε να το είδος της σκεφτούμε αυτό διαισθητικά, έστω και αν θα μπορούσε να πάρει λίγο λίγο χρόνο για να βυθίζουν μέσα Στη χειρότερη περίπτωση, αυτό θα ήταν αυτά επτά άνθρωποι έχουν έμοιαζε, σε όρους της συμφωνίας του αριθμού τους; Εντελώς προς τα πίσω, έτσι δεν είναι; Και ακριβώς για να προσομοιώσει ότι, Τι ήταν το όνομά σας και πάλι; MIKE: Mike. David J. MALAN: Mike; Εντάξει, Mike, μπορείτε να συμμετάσχετε με μόλις πάνω από εδώ μόνο για ένα λεπτό; Στην πραγματικότητα, όχι. Δυστυχώς Mike, rewind ας. Ποιο είναι το όνομά σας και πάλι; NEIL: Neil. David J. MALAN: Neil. Εντάξει, Neil, θα έρθει με μένα, αν δεν σας πειράζει. Έτσι, Πάω να προτείνω, μόνο για απλότητα, ότι ο Neil είναι τώρα στο δικό του χειρότερη δυνατή περίπτωση. Αλλά θυμηθούμε πώς θα εφαρμοστεί αλγόριθμο μου. Είμαι σύγκριση, η σύγκριση, η σύγκριση, συγκρίνοντας, συγκρίνοντας, oh. Τώρα, αυτοί οι τύποι είναι έξω της τάξης, έτσι μπορώ να διορθώσω. Έτσι ανταλλάξουν εσείς. Αλλά σκεφτείτε τώρα, πόσο πιο μακριά Neil δεν πρέπει να πάει; Είναι περίπου n. Ξέρεις, δεν είναι στην πραγματικότητα n. Είναι σαν, n μείον 1, αλλά είμαι πάρει ενοχλημένος κομμάτι διατήρηση του μικρού αριθμό, οπότε ας το ονομάσουμε n. Έτσι, αν Neil κινείται ένα βήμα μέγιστο κάθε το χρόνο, και να προχωρήσουμε ένα βήμα Neil, Έχω να κάνω αυτό το πραγματικά κουραστική pass εμπρός και πίσω, αυτό είναι κατά προσέγγιση τρόπο αυτό, n βήματα, συνολικά n φορές, επειδή πρόκειται να με πάρει ότι πολλά βήματα για να πάρετε Neil όλα ο τρόπος για να όπου ανήκει. Πόσο μάλλον όλοι οι άλλοι αν εσείς ήταν όλα λανθασμένη εντολή, καθώς και. Έτσι, ας την ονομάσουμε είδος φούσκα n τετράγωνο. Ο χρόνος εκτέλεσης αυτού του αλγορίθμου, η απόδοση αυτού του αλγορίθμου, η απόδοση αυτού του αλγορίθμου, θα περιγράψουμε ακριβώς περισσότερο γενικά σαν Ν τετράγωνο. Ποια είναι ωραία, γιατί θα μπορούσα να κάνω το ίδιο παράδειγμα με οκτώ άτομα, εννέα άτομα, ένα εκατομμύριο άνθρωποι, και ότι απάντηση δεν πρόκειται να αλλάξει. Έτσι, αν εσείς δεν θα με πείραζε, ας επαναφέρετε σας όπου αρχίσατε. Και ας προσπαθήσουμε δύο άλλες προσεγγίσεις και δούμε αν δεν μπορούμε να κάνουμε ουσιαστικά καλύτερα από αυτό. Έτσι, αυτή τη φορά, Πάω να προτείνει ένα είδος διαφορετικό αλγόριθμο. Αυτό ήταν πολύ έξυπνο από εμάς την τελευταία φορά, και εσείς είχαν δικαίωμα να έχουν την δικαίωμα ένστικτα του ακριβώς το είδος της swapping ζεύγη. Αλλά αν πραγματικά ήθελε να προσεγγίσουμε το θέμα απλά, και ο στόχος μου είναι να προχωρήσουμε όλα τα μικρά αριθμών αυτό τον τρόπο, και ωθήσει όλα τα μεγάλα νούμερα που τρόπο, γιατί να μην το κάνω μόνο ότι η πιο αφελής δυνατό τρόπο και να δω αν μπορώ μπορεί να κάνει καλύτερα από ό, τι ήταν αρκετά σύνθετο αλγόριθμο; Ας δούμε λοιπόν. Τέσσερις είναι ένα όμορφο μικρό αριθμό, έτσι είμαι πρόκειται να σας αφήσει εκεί τη στιγμή. Ooh, νούμερο δύο είναι ακόμα καλύτερα. Έτσι, μπορεί απλά βήμα προς τα εμπρός για μια στιγμή; Αυτό είναι σήμερα μικρότερο αριθμημένα μου υποψήφιος, και πάω να θυμόμαστε ότι με την, όπως, μια μεταβλητή. Αλλά Πάω να κρατήσει τον έλεγχο. Υπάρχει κάποιος του οποίου υπάρχει αριθμός είναι μικρότερος; Έξι, ηο. Ω, υπάρχει Neil πάλι. Έτσι, Πάω να σας ωθήσει πίσω είδος εννοιολογικά. Neil θα έρθει προς τα εμπρός. Και, τώρα η μεταβλητή που είμαι με τη χρήση για την να παρακολουθείτε ποιος έχει το μικρότερο Αριθμός ενημερώνεται για να περιέχουν Θέση του Neil. Λοιπόν, ας δούμε. Τρεις, επτά, πέντε. Εντάξει, ξέρω ότι ο Neil ήταν το μικρότερο. Ποιο είναι το πιο απλό πράγμα για μένα να κάνω τώρα; Δεν πρόκειται να σπαταλήσω το χρόνο μου με απλά διοχέτευσή του Neil ένα σημείο προς τα αριστερά. Γιατί δεν έβαλα ακριβώς Neil όπου ανήκει, το οποίο είναι, φυσικά, πού; Όλος ο τρόπος κατά την έναρξη. Έτσι Neil, έλα μαζί μου. Και ποιο ήταν το όνομά σας και πάλι; GRACE: Γκρέις. David J. MALAN: Γκρέις. OK. Έτσι, Γκρέις, δυστυχώς, είστε είδος με τον τρόπο. Επομένως, πώς θα λύσουμε αυτό το πρόβλημα; Σωστά; Εάν αυτό είναι ένας πίνακας, υπάρχει μόνο επτά θέσεις. Υπενθυμίζεται ότι, με τον Rob, μιλήσαμε για δηλώνοντας τις ηλικίες, και είχαμε μόνο ένα πεπερασμένο αριθμό των ηλικιών; Ίδια ιδέα εδώ. Έχουμε μόνο έναν πεπερασμένο αριθμό ints. Γκρέις είναι το είδος της σε μας τρόπο, έτσι πώς να διορθώσετε; Ο απλούστερος τρόπος είναι παρόμοια, Χάρη, συγγνώμη. Θα πάμε να πρέπει να πάει πέρα ​​από οπότε εκεί μπορούμε να κάνουμε χώρο. Τώρα, αν το σκεφτούμε αυτό, ίσως Εμείς απλά έκανε το πρόβλημα χειρότερο. Και ίσως κάναμε, γιατί ό, τι και αν Γκρέις ήταν στο σωστό μέρος; Αλλά ξέρουμε ότι δεν είναι, γιατί διαφορετικά, ότι θα ήταν στέκεται μπροστά αντί Neil αυτή τη στιγμή, έτσι δεν είναι; Έχουμε ήδη ελέγξει τον αριθμό της έξω. Εντάξει. Έτσι τώρα, Neil είναι στο σωστό μέρος, και Μπορώ να κάνω μια μικρή βελτιστοποίησης. Για το επόμενο λεπτό, Πάω να αγνοήσει Neil όλα μαζί, έτσι ώστε να μην σπαταλήσει το χρόνο του, ή τυχαία ανταλλάξουν τον στο λάθος μέρος. Έτσι τώρα, πώς μπορώ να βρω το επόμενο στοιχείο που είναι μικρότερη; Δύο. Αυτό είναι ένα αρκετά καλό αριθμό, αν θέλετε να το βήμα προς τα εμπρός και Θα θυμάστε. Έξι, δεν είναι καλό. Τέσσερα, τρία, επτά, πέντε, δεν είναι καλό. Έτσι, επιτρέψτε μου να σας μετακινήσει σε σωστό μέρος σας. Και εμείς απλά στάθηκε τυχερός αυτή τη φορά. Τώρα, είμαι πρόκειται να αγνοήσει δύο παιδιά, και να κάνουμε τώρα ένα ακόμη να περάσει μέσα από αυτό. Έξι, ότι ένας πολύ μικρός αριθμός. Έλα προς τα εμπρός. Ω, συγγνώμη. Grace Αριθμός είναι καλύτερη, έτσι βήμα για τα εμπρός. Four. Δυστυχώς, Γκρέις. Πήγαινε πάλι πίσω. Νούμερο τρία είναι καλύτερη. Επτά. Πέντε. Και τώρα τι είναι το όνομά σας και πάλι; ΙΑΣΩΝ: Jason. David J. MALAN: Jason. Έτσι ο Ιάσονας είναι πλέον το μικρότερο στοιχείο που έχω επιλέξει. Πού θα πήγαινε; Έτσι, όταν έξι είναι. Και το όνομά σου είναι πάλι; GABE: Gabe. David J. MALAN: Gabe. Gabe είναι στο δρόμο. Ποιο είναι το πιο εύκολο πράγμα να κάνουμε; Εναλλαγή αυτά τα δύο παιδιά και να συνεχίσει. Έτσι τώρα ας δούμε. Ποιος είναι ο μικρότερος; Four. Επιτρέψτε μου ακριβώς το είδος της εξαπατήσει. Πέντε θα είναι το μικρότερο. Θεωρώ ότι το επόμενο, αν θέλετε να το βήμα προς τα εμπρός, τι πρέπει να κάνω με αυτά τα παιδιά, με Gabe; Εναλλαγή και πάλι. Έτσι τώρα, εξακολουθεί να είναι ελαφρά εκτός λειτουργίας. Βρήκα Gabe είναι το μικρότερο, οπότε Τον πεταχτεί έξω, μετακινήστε εσείς πάνω. Και κάνει. Έτσι απάντηση είναι η ίδια. Το τελικό αποτέλεσμα είναι το ίδιο. Ποια από αυτές τις δύο αλγορίθμων είναι καλύτερα; Το δεύτερο, το άκουσα. Γιατί; ΟΜΙΛΗΤΗΣ 3: Είναι n βήματα [δεν ακούγεται]. David J. MALAN: Είναι n βήματα το πολύ. Ενδιαφέρουσες. Έτσι είναι όμως; Λοιπόν, πώς μπορώ να βρω το μικρότερο στοιχείο; Πόσα βήματα εγώ πρέπει να λάβουν το να βρει το μικρότερο στοιχείο; Έριξα μια ματιά σε όλη τη διαδρομή στο τέλος, έτσι δεν είναι; Διότι στην χειρότερη περίπτωση, αυτό αν Neil ήταν εδώ; Έτσι, την εύρεση ακριβώς το μικρότερο στοιχείο μου παίρνει n βήματα, ή n μείον 1. Αλλά, εντάξει. Έτσι καθορίζουν το Neil. Να θυμάστε ότι, ένα λεπτό ή έτσι πριν. Αλλά πώς μπορώ να βρω το επόμενο μικρότερο στοιχείο; Είναι n μείον 1, ή Ν μείον 2 πραγματικά, από τον αριθμό των βημάτων. Έτσι OK. Έτσι έκανα n μείον 2. Εντάξει. Έτσι ώστε να αισθάνεται λίγο καλύτερα. Εντάξει. Πόσα βήματα την επόμενη φορά για να βρείτε τον αριθμό τρία; Έτσι, n μείον 4. Έτσι είναι φθίνουσα, ένα λιγότερο βήμα σε κάθε επανάληψη. Έτσι, αυτό δεν αισθάνεστε καλύτερα, έτσι δεν είναι; Εάν η τελευταία φορά ήταν περίπου n φορές n, αυτή τη φορά είναι n μείον 1, συν n μείον 2, καθώς και n μείον 3, καθώς και n μείον 4, τελεία, τελεία, τελεία. Αλλά αν θυμάστε από το γυμνάσιο σας εγχειρίδια, η μικρή εξαπατήσει φύλλο στο πίσω μέρος που έχει τύπους, αν μπορείτε να προσθέσετε μέχρι αυτή τη σειρά των αριθμών, ό, τι είναι ο συνολικός αριθμός των βημάτων πρόκειται να είναι ότι παίρνω εδώ; Αυτό είναι ένα από αυτά, όπως, n μείον 1, Ν φορές, διαιρείται με το 2. Έτσι, επιτρέψτε μου να δω αν μπορώ να τραβήξει αυτό για μια στιγμή. Και πάλι, είμαι το είδος του στρογγυλοποίηση ορισμένων αριθμούς μόνο για να κρατήσει τη ζωή μας απλή, αλλά από όσο θυμάμαι, είναι κάτι σαν, αν Κάνω n μείον 1 πράγματα, τότε n μείον 2, τότε n μείον 3, είναι περίπου κάτι σαν αυτό πάνω από 2, και αν πολλαπλασιάστε αυτό έξω, αυτό είναι στην πραγματικότητα πλατεία n. Αυτό δεν νιώθει πολύ καλά. n μείον n πάνω από 2. Αλλά εδώ είναι το πράγμα. Στην επιστήμη των υπολογιστών, όταν τα προβλήματα αρχίζουν να παίρνουν ενδιαφέρον είναι όταν n παίρνει πραγματικά μεγάλο. Και όταν το n παίρνει πραγματικά μεγάλο, ποια από αυτές οι αξίες πρόκειται να κυριαρχούν σε όλα από τους άλλους; Είναι το είδος του n τετράγωνο, έτσι δεν είναι; Ναι, η διαίρεση με το 2 είναι πολύ καλή. Αλλά αν μιλάμε για δισεκατομμύρια κομμάτια των δεδομένων, ή τρισεκατομμύρια κομμάτια των δεδομένων, ΕΝΤΑΞΕΙ, έτσι είστε δύο φορές πιο γρήγορα. Αλλά ποιος νοιάζεται πραγματικά εάν αυτό το μεγάλο αριθμό, Αν αυτός ο παράγοντας είναι αυτό που παίρνει όλο και μεγαλύτερες. Και σίγουρα, θα κάνει περισσότερα από διαφορά από αυτόν τον τύπο. Έτσι ακόμα κι αν εσείς δίκιο, η δεύτερος αλγόριθμος, θα την αποκαλούμε Ταξινόμηση επιλογής, είναι, στον πραγματικό κόσμο, ένα λίγο πιο γρήγορα δυνητικά, επειδή είμαι λαμβάνοντας όλο και λιγότεροι βήματα κάθε φορά. Δεν είναι πραγματικά ουσιαστικά γρηγορότερα. Γιατί αν παίζουμε πραγματικά αυτό έξω για μεγάλες τιμές του n, στο τέλος της την ημέρα, για αρκετά μεγάλο n, είναι ακόμα πρόκειται να αισθανθείτε πολύ αργή. Λοιπόν, επιτρέψτε μου να πάρει ένα τελευταίο πέρασμα σε αυτό. Αυτό είναι που εγώ θα αποκαλούσα Ταξινόμηση επιλογής. Μπορεί εσείς τον εαυτό σας επαναφέρετε για τελευταία φορά; Και στην τελευταία αυτή περίπτωση, Πάω να προτείνω κάτι ονομάζεται ταξινόμηση με εισαγωγή. Ταξινόμηση με εισαγωγή είναι, θεωρητικά, λίγο διαφορετική. Αντί να πηγαίνει πέρα ​​δώθε και επιλέγοντας το μικρότερο στοιχείο, είμαι ακριβώς πρόκειται να ασχοληθεί με κάθε μία από αυτές παιδιά, όπως εγώ τους συναντήσει, και τοποθετήστε τους σε σωστή θέση τους. Έτσι, είμαι απλώς πρόκειται να ξεκινήσει με την Γκρέις, και βλέπω ότι είναι το νούμερο τέσσερα. Πού αριθμός τέσσερα ανήκουν; Δεν έχω αρχίσει διαλογή τίποτα, ούτω και η χάρις παίρνει να μείνει εκεί. Και τώρα πάω να διεκδικήσουν, αν θα μπορούσατε κάνουμε ένα βήμα προς τα δεξιά σας, αυτό ταξινομημένη λίστα μου, αυτό είναι μου αδιαχώριστα υπόλοιπο κατάλογο. Έτσι τώρα είμαι πρόκειται να προχωρήσει το επόμενο, και τι είναι το όνομά σας και πάλι; Branson:. David J. MALAN: Branson. Έτσι Branson είναι το νούμερο δύο. Έτσι, Πάω να σας μεταφέρει έξω για μια στιγμή. Και, τώρα, όπου ανήκετε σε αυτή την σειρά; Έτσι, το δικαίωμα της Χάριτος. Έτσι και πάλι, είμαστε το είδος των αποφάσεων Γκρέις κάνει πολλή δουλειά εδώ. Πού θα βάλετε; Έτσι θα πάμε για να σύρετε με το αριστερά, και τοποθετήστε Branson εκεί. Τώρα, όμως, ισχυρίζονται ότι γίνονται εσείς. Αλλά προσέξτε, δεν είμαι με επιπλέον χώρο. Είναι ακόμα 2 στοιχεία εδώ, 5 εδώ. Συνολικό μέγεθος του πίνακα είναι 7, έτσι είμαι Δεν εξαπάτηση, εντάξει; Έτσι τώρα έχουμε, με Gabe εδώ, η νούμερο έξι, όπου ανήκετε; Έχεις τυχερός και πάλι. Έτσι, μπορείτε να πάρετε για να μείνουν εκεί. Απλώς πάρτε μια μικρή βήμα προς τη σωστή μόνο για να καταστήσει σαφές ότι είστε ταξινομημένο. Και τώρα έχουμε Neil, και πάλι τον αριθμό ένα, πού πας; Και τώρα είναι που θα αρχίσετε να βλέπετε ότι Ο αλγόριθμος αυτός, αν και σε πρώτη ματιά, αισθάνεται αρκετά έξυπνος, να παρακολουθήσετε τι πρόκειται να συμβεί. Αν θα μπορούσατε να βήμα προς τα εμπρός. Πού θέλουμε να θέσει Neil; Έτσι, προφανώς, εδώ, έτσι πώς παίρνουμε Neil εκεί; Ας κάνουμε αυτό το βήμα-βήμα. Gabe, όπου χρειάζεται να πάτε; Ναι, έτσι ώστε να λάβει ένα μεγάλο βήμα, ή δύο μισά βήματα για να κάνετε ένα βήμα εκεί. Γκρέις, όπου θα πάτε; Καλό. Έτσι, ένα ακόμη βήμα. Και τέλος, Branson; Ένα άλλο βήμα. Και τώρα μπορούμε να βάλουμε Neil στη θέση του. Έτσι τώρα, να συνεχίσει αυτή τη λογική. Ακόμα κι αν δεν είμαστε μετατόπιση Neil ξανά, και ξανά, και ξανά, να τον βάλουν όπου πηγαίνει, στη χειρότερη περίπτωση, η επόμενο αριθμό που μπορεί να συναντήσετε θα μπορούσε να είναι ο αριθμός, δηλαδή, υπήρχε ένας αριθμός μηδέν, τότε θα πάμε να μεταφερθεί το σύνολο των αυτά τα παιδιά. Ας υποθέσουμε ότι υπάρχει ένας αριθμός, αρνητική ένα, τότε θα πρέπει να στρέψουμε όλα αυτά τα παιδιά. Έτσι, είμαστε πραγματικά ακριβώς το είδος της flipping το πρόβλημα γύρω, έτσι ώστε να είμαστε μεταφέροντας το βάρος από το διαδικασία επιλογής έτσι ώστε η εισαγωγή διαδικασία, όπως ότι εσείς μόλις είχε να κινηθεί περίπου n μείον κάτι αριθμό των βημάτων. Και ο αριθμός των βημάτων που θα είναι μόνο να αυξηθεί, καθώς θα επιλέξετε περισσότερους αριθμούς, αν έχω να κρατήσει σπρώχνει εσείς πίσω, και πίσω, και πίσω. Έτσι, το λυπηρό είναι τώρα όλα αυτά αλγόριθμοι είναι n τετράγωνο. Ας πάμε μπροστά και χάρη σε αυτές παιδιά, και να απεικονίσει αυτά λίγο διαφορετικά. Πολύ καλά κάνει. [Χειροκρότημα] Εντάξει. Εκεί θα πάτε. Ευχαριστώ για - BRANSON: [δεν ακούγεται] να κρατήσει τους αριθμούς. David J. MALAN: Όχι, δεν μπορείτε κρατήσει τους αριθμούς, καθώς και. Εντάξει. Όμορφα γίνει. Εντάξει. Ας δούμε αν μπορούμε να μην μπορούν πλέον να συνοψίσουμε πιο γρήγορα και πιο οπτικά, ακριβώς ό, τι ακριβώς συνέβη εδώ ως εξής. Πάω να προχωρήσει και τραβήξτε Firefox. Θα συνδεθεί αυτή η διαδήλωση στην ιστοσελίδα του μαθήματος. Java είναι λίγο ενοχλητικό να πάρει εργασίας σε ορισμένα προγράμματα περιήγησης αυτές τις μέρες. Έτσι, αν παίζουν με αυτό στο σπίτι, συνειδητοποιούν ίσως χρειαστεί να χρησιμοποιήσετε τον Firefox να το πάρει εργασίας. Και τι Πάω να κάνω με αυτό επίδειξης είναι η ακόλουθη. Στο κάτω μέρος, έχω ένα σωρό επιλογές μενού, όπως μια αρχή και να σταματήσει το κουμπί. Επίσης, ως ένα μέρος, φαίνεται να υπάρχει μια bug σε αυτά τα προγράμματα, σύμφωνα με την οποία θα Δεν μπορούν να δουν πραγματικά την έναρξη ή διακοπή πλήκτρο, εκτός κρατάτε Command ή Alt καθώς και η μεγέθυνση, η οποία περιέργως σας δείχνει περισσότερα κουμπιά. Έτσι, απλά FYI αν παίξετε με αυτό στο σπίτι. Τώρα είμαι πρόκειται να κάντε κλικ στο Έναρξη σε μόλις ένα στιγμή, μετά καθορίζοντας μια καθυστέρηση, όπως, 200 χιλιοστά του δευτερολέπτου εδώ, απλά ώστε να μπορούμε να δούμε τι θα συμβεί. Γι 'αυτό και ισχυρίζονται ότι αυτό είναι μια οπτικοποίηση του πρώτου αλγορίθμου αυτά τα παιδιά έκαναν, το είδος φούσκα, σύμφωνα με την οποία που αντάλλαξαν οι άνθρωποι ζεύγη. Η βασική αντίληψη σε αυτή την οπτικοποίηση είναι ότι το ύψος των ράβδων αντιπροσωπεύει το μέγεθος του αριθμού. Έτσι, το ψηλότερο το μπαρ, το μεγαλύτερος είναι ο αριθμός. Shorter το μπαρ, μικρότερος ο αριθμός. Και αν παρατηρήσετε, θα πάμε μέσα Η πρώτη επανάληψη αυτού του αλγορίθμου, εναλλαγή μεγάλων και μικρών αριθμών, έτσι ώστε να ο μικρός αριθμός έρχεται πρώτη και ο μεγάλος αριθμός πηγαίνει προς τα δεξιά. Και μόλις φτάσουμε στο τέλος του πίνακα από πολλά περισσότερα από επτά αριθμούς, είμαστε πρόκειται να πάει πίσω στην αρχή. Και την πρόβλεψη αυτή. Από την άκρα αριστερά, αυτό το μικρό τύπος συμβαίνει να ανταλλάξουν με την πλευρά της, και αυτό διαδικασία επαναλαμβάνεται. Τώρα αυτή η απεικόνιση παίρνει γρήγορα βαρετό, οπότε επιτρέψτε μου να πάει μπροστά και να σταματήσει αυτό, να αλλάξετε την καθυστέρηση κάτι πολύ γρηγορότερα για να πάρει ακριβώς, τώρα μια ιδέα για Αυτός ο αλγόριθμος. Έτσι, ακόμα κι αν έχω επιτάχυνε, αυτό είναι όπως η αναβάθμιση του επεξεργαστή μου, αγοράζοντας ένα νέο υπολογιστή. Δεν έχω αλλάξει ριζικά μου αλγόριθμο, αλλά μπορείτε να δείτε πράγματι πιο σαφώς από ό, τι με τους ανθρώπους, ότι η μεγάλη αριθμοί οι bubbling μέχρι την κορυφή, και οι μικροί αριθμοί είναι ανάδευση στο κάτω μέρος. Και τώρα αυτό το πράγμα εδώ ταξινομημένο. Και ως ένα μέρος, στις πλατείες, υπάρχει μόνο μερικά τήρησης βιβλίων εκεί για να να σας βοηθήσει να μετρήσουν πόσες συγκρίσεις, ή πόσα swaps έχουν πραγματικά έχει γίνει. Λοιπόν, ας προσπαθήσουμε μια από οι άλλοι είδαμε. Επιτρέψτε μου να κάντε κλικ στο είδος φούσκα εδώ, και επιτρέψτε μου να επιλέξει, και όλη αυτή η ιστοσελίδα είναι ένα μικρό αμαξάκι. Ας δεχτούμε τον κίνδυνο και να τρέξει ξανά. Εκεί πάμε. Ας κάνουμε το είδος επιλογής. Δεν ξέρω γιατί το μενού εμφανίζεται εκεί. Ας zoom in για να καθορίσει ότι bug, το αλλάξετε σε 50. Αχ, ας κάνουν πραγματικά ότι πολύ πιο γρήγορα. Πέντε χιλιοστά του δευτερολέπτου ή έτσι, και να αρχίσει. Έτσι, αυτό είναι το είδος επιλογής. Έτσι και πάλι, σκεφτείτε τι μπορούμε έκανε με τους ανθρώπους εδώ. Πήγαμε με την σειρά και επιλέγονται το μικρότερο στοιχείο πάλι, και ξανά, και ξανά. Τώρα ισχυρίζονται ότι ήταν ακόμα αρκετά άσχημα. Ήταν ακόμα n τετράγωνο, ή να δώσει, αλλά ήταν, στον πραγματικό κόσμο, ένα κομμάτι γρηγορότερα, γιατί πράγματι, λαμβάνοντας ελαφρώς λιγότερα βήματα κάθε φορά. Αλλά μιλάμε μόνο ό, τι; Ίσως 40 ή έτσι μπαρ εδώ; Εμείς δεν μιλάμε 40 εκατ. ευρώ. Έτσι δεν είναι απόλυτα σαφές για μένα ότι Ήταν πράγματι ένα σημαντικό κέρδος. Επιτρέψτε μου τώρα να πάει πίσω και να αλλάξει σε μας τρίτη αλγόριθμος, που επιλέγει ταξινόμηση με εισαγωγή. Και τώρα είναι πραγματικά προβληματικό, διότι η menu πραγματικά δεν πρέπει να είναι εκεί κάτω. Έτσι τώρα θα μετακινηθείτε προς τα πίσω μέχρι εδώ και να αρχίσει αυτόν τον αλγόριθμο. Whoop, να αρχίσει και να σταματήσει. Έτσι, αυτό το είδος έχει ένα όμορφο σχέδιο σε αυτό, σύμφωνα με την οποία είμαστε και πάλι εισάγοντας τους ανθρώπους, ή Στην περίπτωση αυτή, τα μπαρ σε κατάλληλη θέση τους. Και αυτό έχει ήδη γίνει πριν Γύρισα γύρω. Αλλά αυτό, επίσης, στη θεωρία, εξακολουθεί ν τετράγωνο. Έτσι, ας δούμε αν δεν μπορούμε να συνοψίσουμε Αυτά ως εξής. Πάω να πάει μπροστά και μόνο για να δώσει μας ένα είδος συνηθισμένος τρόπος να μιλάμε για αυτά τα πράγματα, επιτρέψτε μου να εισαγάγει απλά ένα κομμάτι της σημειογραφίας εδώ. Είστε έτοιμοι να δείτε κάτι που ονομάζεται μεγάλο O, επειδή είναι κυριολεκτικά ένα μεγάλο Ο. Και αυτό είναι ένας τρόπος ότι ένας υπολογιστής επιστήμονας ή ένας μαθηματικός χρησιμοποιεί ακόμη και για να περιγράψει το χρόνο λειτουργίας κάποιου αλγορίθμου. Πόσα βήματα δεν είναι στην πραγματικότητα να λάβει; Τώρα είμαι πρόκειται να φέρουν σε δύσκολη θέση τον εαυτό μου με χειρόγραφό μου εδώ ακριβώς σε μια στιγμή. Αλλά επιτρέψτε μου να προχωρήσει και να πω ότι Αυτό θα είναι μεγάλη O εδώ. Και επιτρέψτε μου να εισαγάγει ένα άλλο σύμβολο, ένα ωμέγα κεφαλαίου. Omega πρόκειται να είναι το αντίθετο, κατ 'ουσίαν, των μεγάλων O. ότι η μεγάλη O μέσα, στη χειρότερη περίπτωση, πόσο χρόνο θα μπορούσε κάποια αλγόριθμος λαμβάνει, Όροι n, ωμέγα πρόκειται να είναι πόσο χρόνο θα μπορούσε να λάβει στην καλύτερη περίπτωση. Και θα δούμε τι εννοούμε με τον όρο καλύτερη περίπτωση σε μια στιγμή. Οπότε ας ξεκινήσουμε κάτι απλό. Επιτρέψτε μου να ξεκινήσω με μια γραμμική αναζήτηση. Έτσι, δεν διαλογή. Θα το ονομάσουμε γραμμική αναζήτηση. Και τώρα, κάνει μια μικρή πίνακας έξω από αυτό. Και τώρα, στην περίπτωση της γραμμικής αναζήτησης, στη χειρότερη περίπτωση, πόσα βήματα είναι αυτό θα μου πάρει για να βρεθεί μια αριθμό αυθαίρετων επιλογή; Και υπάρχει n συνολικό πόρτες ή n συνολικό αριθμό. Χειρότερη περίπτωση. Πόσα βήματα είμαι πρόκειται να πρέπει να λάβει για να βρείτε τον αριθμό 50 σε μια σειρά Ν πόρτες; Και γιατί; Επειδή θα μπορούσε να είναι όλη η τρόπο πάνω στην άκρη. Τόσο μεγάλο μέρος όπως η Jennifer συνάντησε, η αριθμός 50 ήταν σε όλη τη διαδρομή πάνω, έτσι ώστε το η χειρότερη περίπτωση γραμμική αναζήτηση είναι μεγάλη O Ν, εμείς θα πούμε. Τι γίνεται στην καλύτερη περίπτωση, αν έχετε πραγματικά τυχερός; Είναι ακριβώς πρόκειται να πάρει ένα βήμα, ή ένα σταθερό αριθμό βημάτων. Έτσι, θα σας περιγράψουμε ότι 1. Έτσι, αυτό είναι πολύ καλό. Τώρα, τι θα γινόταν αν κάναμε κάτι όπως δυαδική αναζήτηση; Έτσι, δυαδική αναζήτηση, στη χειρότερη περίπτωση, πήρε πόσο χρόνο; [Παρεμβάλλοντας VOICES] David J. MALAN: Έτσι, στην πραγματικότητα, I ακούσει σε χώρους ζευγάρι. Έτσι είναι στην πραγματικότητα συνδεθείτε n, ή να δώσει, γιατί όπως διαιρέσουμε τον κατάλογο στο μισό ξανά, και ξανά, και ξανά, είμαστε σε θέση να βρει, τελικά, η αξία, αν υπάρχει, αλλά υπάρχει μια παγίδα. Ποια είναι η υπόθεση ότι πρέπει να θεωρούμε δεδομένο για την δυαδική αναζήτηση; Θα πρέπει να διευθετηθεί. Δεν είναι ταξινομημένο, μπορείτε να χωρίσετε το πράγμα κατά το ήμισυ ξανά και ξανά, και θα μπορεί να πάει αριστερά, και μπορείτε να πάτε δεξιά, και μπορείτε να πάτε αριστερά και δεξιά, αλλά είστε δεν πρόκειται να βρούμε το στοιχείο, εάν Ο κατάλογος δεν είναι ταξινομημένη, γιατί μπορείτε να το χάσετε. Επειδή η ευρετική σας, για να πάει αριστερά ή δικαίωμα δεν πρόκειται να αποτύχουν αν είναι όντως δεν ταξινομούνται. Έτσι υπάρχει ένα είδος κρυφό κόστος για τη χρήση κάτι σαν αυτό. Τώρα, ας πάμε στην διαλογή μας αλγόριθμοι που δεν ψάχνουν - Ω, πραγματικά ας πάμε σε αυτό το κενό. Δυαδική αναζήτηση στην καλύτερη περίπτωση; Είναι επίσης 1, αν συμβαίνει να είναι ακριβώς στο πολύ μέση της συστοιχίας, ή η μέση του τηλεφωνικού καταλόγου. Τώρα ας κάνουμε το είδος φούσκα. Έτσι και πάλι, τώρα είμαστε εισέρχονται στο ταξινομεί όχι, οι έρευνες. Στη χειρότερη περίπτωση, πόσα βήματα κάναμε αξίωση είδος φούσκα πρόκειται να πάρει; n τετράγωνο. Έτσι, Πάω να επιστήσω αυτό. Ooh, χειρόγραφό μου φαίνεται ακόμα χειρότερα όταν είναι προβλέπεται ότι οι μεγάλες. Εντάξει. Έτσι ώστε να είναι n τετράγωνο. Και στην καλύτερη περίπτωση της ταξινόμησης φυσαλίδας, πόσα βήματα είναι αυτό πρόκειται να πάρει; 1, άκουσα. ΟΜΙΛΗΤΗΣ 1: n. David J. MALAN: n, άκουσα. ΟΜΙΛΗΤΗΣ 1: 2. David J. MALAN: 2, άκουσα. Ακούω 3; Εντάξει. Έτσι, έχω ακούσει 1, n, 2, αλλά ας πάρει Εκτός τουλάχιστον η πρώτη από αυτές προτάσεις, 1. Δεν είναι μια κακή ένστικτο, γιατί είδος ακολουθεί ένα πρότυπο εδώ. Αλλά αν παίρνει μόνο 1 βήμα, πώς η κόσμο θα μπορούσα να ισχυριστεί ότι ο κατάλογος είναι ταξινομημένο, γιατί αν είμαι μόνο επιτρέπεται να λάβει 1 βήμα, πόσα στοιχεία θα ήθελα πραγματικά να ελέγξετε για να βεβαιωθείτε; Λοιπόν, μόλις 1, το οποίο σημαίνει ότι υπάρχει n μείον 1 στοιχεία που θα μπορούσαν να είναι έξω από τάξη, και είμαι απλώς πρόκειται για την πίστη μετά κοιτάζοντας 1 στοιχείο ότι η πράγμα που είναι ταξινομημένο. Έτσι, 1 δεν είναι σωστό εδώ. Έτσι, ελάχιστα, πόσες έχω να δούμε; [Παρεμβάλλοντας VOICES] David J. MALAN: n μείον 1, ή πραγματικά, n, γιατί πρέπει να εξετάσουμε κάθε στοιχείο που πρέπει να βεβαιωθείτε ότι δεν είναι εκτός λειτουργίας. Αλλά και πάλι, θα ταξινομήσετε του κύματος μας τα χέρια στους μικρούς αριθμούς και υποθέσουμε ότι, καθώς το n παίρνει μεγάλες, είναι πληκτικός ούτως ή άλλως. Έτσι, αυτό είναι το είδος φούσκα. Και τώρα, ας κάνουμε αυτά τα δύο τελευταία. Ταξινόμηση Selection, και στη συνέχεια θα κάνει ταξινόμηση με εισαγωγή. Και τότε θα φυσήξει σας μυαλά με κάτι πολύ καλύτερα από όλα αυτά. Εντάξει. Ποια είναι η χειρότερη περίπτωση λειτουργίας χρόνο της επιλογής του είδους; ΟΜΙΛΗΤΗΣ 4: n τετράγωνο. David J. MALAN: n πλατεία, ακούω. Αλλά γιατί n τετράγωνο, διαισθητικά; ΟΜΙΛΗΤΗΣ 4: Γιατί το κάναμε αυτό ακριβώς. David J. MALAN: Επειδή κάναμε αυτό ακριβώς. OK. Καλή απάντηση. Αλλά διαισθητικά, γιατί είναι επιλογή Ταξινόμηση n τετράγωνο; Τι πρέπει να κάνουμε ξανά και ξανά; Έπρεπε να κρατήσει σάρωση μέσω, είναι Σας το μικρότερο, είσαι η μικρότερο, είσαι το μικρότερο. Και χορηγηθεί, ήμασταν σε θέση να λάβει n βήματα, τότε ν μείον 1, τότε το η μείον 2. Αλλά αν το είδος του προσθέτει τα όλα επάνω, ή πάρτε την πίστη ότι έχω προσθέσει τους εκ των προτέρων, έχουμε περίπου n τετράγωνο μείον ορισμένες μικρότερους αριθμούς. Έτσι, Πάω να καλέσετε αυτό n τετράγωνο. Αλλά με το είδος επιλογής με τον καλύτερο περίπτωση, πόσα βήματα είναι πρόκειται να με πάρει; ΟΜΙΛΗΤΗΣ 5: [δεν ακούγεται] David J. MALAN: Είναι, δυστυχώς, εξακολουθεί ν τετράγωνο, έτσι δεν είναι; Γιατί αν είμαι επιλέγοντας το μικρότερο στοιχείο, και είχαμε επτά άτομα εδώ, Το μόνο που ξέρω, όταν θα φτάσουμε στην τέλος, ότι έχω βρει το μικρότερο αριθμό, όπου και αυτή μπορεί να έχει. Αλλά πώς μπορώ να βρω το επόμενο μικρότερος αριθμός; Έχω να κάνω ένα άλλο πέρασμα. Έτσι, στην καλύτερη περίπτωση, ποια είναι η εισόδου για να ταξινομήσετε επιλογή; Είναι μια ήδη λίστα ταξινόμησης, νούμερο ένα, νούμερο δύο, νούμερο τρία, το νούμερο τέσσερα. Αλλά είμαι ένας υπολογιστής. Μπορώ μόνο να δούμε ένα πράγμα κάθε φορά. Δεν μπορώ να ταξινομήσετε του κάνουμε ένα βήμα πίσω σαν ένα ανθρώπινο και να πω, ooh, αυτό φαίνεται σωστό. Μπορώ να αποφανθεί μόνο ορθότητα Ταξινόμηση επιλογή με την επιλογή του μικρότερο αριθμό. Αλλά ακόμα και αν βρω νούμερο ένα πρώτο, αν δεν ξέρω τίποτα άλλο γι ' οι άλλοι αριθμοί, που εγώ δεν το κάνετε, το μόνο που μπορώ Γνωρίζω ότι έχω παραδοθεί μια σειρά ή μια σειρά από πόρτες πίσω από τις οποίες είναι αριθμούς, ο μόνος τρόπος που ξέρω ότι ένα ήταν η μικρότερη; Αν πάρω όλη τη διαδρομή εδώ και να συνειδητοποιήσουν, βλασφημία, ένα ήταν πράγματι η μικρότερη. Αλλά πώς μπορώ να διαπιστώσω στη συνέχεια ότι δύο είναι το επόμενο μικρότερο; Με τον τρόπο την ίδια αναποτελεσματικότητα ξανά και ξανά. Έτσι, τελικά, με την ταξινόμηση με εισαγωγή, πώς, στη χειρότερη περίπτωση, δεν λέμε ότι εκτελεί; Είναι πάρα πολύ είναι n τετράγωνο. Και τι γίνεται με την καλύτερη περίπτωση; Θα το αφήσουμε ως δραματική στιγμή. Θα συμπληρώσει το κενό επόμενη φορά, αλλά πρώτα επιτρέψτε μου να προτείνω να ουσιαστικά κάνει καλύτερα από ό, τι όλα αυτά, εντάξει; Έτσι σκεφτείτε για τον εαυτό σας τι εισαγωγή Ταξινόμηση πρόκειται να είναι. Λοιπόν, αυτό δεν ήταν πολύ δραματική, γιατί είμαι ο μόνος που είδε την αλλαγή. Wow. OK. Έτσι, εδώ έχουμε μια κάπως διαφορετική επίδειξη. Αν μου κάνετε ζουμ σε εδώ, θα δείτε ότι σε η αριστερά έχουμε το είδος φούσκα, στην μεσαία έχουμε είδος επιλογής, και η άκρα δεξιά, έχουμε κάτι που δεν έχουν εξεταστεί ακόμα ονομάζεται συγχώνευση είδους. Αλλά σκεφτείτε τι έχουμε πάει κάνουμε εδώ μέχρι στιγμής σήμερα. Όταν η Jennifer για πρώτη φορά στη σκηνή, περάσαμε από τη συστοιχία των αριθμών ξανά και ξανά, με γραμμική αναζήτηση, και πήραμε γραμμικό χρόνο λειτουργίας, big O ν, να το πω έτσι. Όταν εξετάζουμε τώρα την πρώτη εβδομάδα του τάξη, όταν είχαμε διαίρει και βασίλευε, και είχαμε το τηλεφωνικό δακρύρροια, και η Jennifer, και εμείς συλλογικά μόχλευση ότι η βασική αντίληψη, η οποία επρόκειτο να επαναλάβετε στον εαυτό σας ξανά και ξανά από κατά κάποιο τρόπο πετάμε, πετάμε, πετάμε, το ήμισυ του προβλήματος, ή Γενικότερα, διαιρώντας ένα πρόβλημα στο μισό, και κατεργασία στη συνέχεια το μικρότερο κομμάτι το πρόβλημα εννοιολογικά ισοδύναμο στην άλλη, κατά κάποιο τρόπο στην θεμελιωδώς καλύτερα. Αλλά με το είδος φούσκα, με την επιλογή ταξινόμησης, με το είδος εισαγωγής, έχουμε μπορεί να δεν υπάρχουν τέτοιες ιδέες ότι η Jennifer έκανε. Είμαστε λίγο πολύ απλά περπάτησε πίσω και πίσω ένα σωρό φορές, και πειραγμένο πράγματα λίγο, ανταλλάσσοντας με αυτή τη σειρά, ίσως εισαγωγή ή την επιλογή. Αλλά στο τέλος της ημέρας, έκανα πολλά αδέξια πόδια εμπρός και πίσω. Εμείς δεν το κάναμε πραγματικά κάτι μόχλευσης έξυπνος όπως η Jennifer άρεσε διαίρεση και την κατάκτηση. Έτσι συγχώνευση του είδους, αντιθέτως, το οποίο Δεν θα δούμε μέχρι την επόμενη εβδομάδα, πρόκειται για τη μόχλευση ότι βασική ιδέα διαιρώντας η είσοδος, και στη συνέχεια μείωση κατά το ήμισυ, και στη συνέχεια μείωση κατά το ήμισυ, και στη συνέχεια μείωση κατά το ήμισυ. Και για κάθε επανάληψη του εν λόγω βρόχου, διαλογή το αριστερό μισό, και το δικαίωμα μισό, τότε το αριστερό μισό του αριστερό μισό, και το δεξί μισό της αριστεράς, στη συνέχεια, το αριστερό μισό του δεξί μισό, και το δεξί μισό στο δεξί ήμισυ. Και επαναλαμβάνοντας ξανά και ξανά. Έτσι, θα δείτε αυτό οπτικά, αλλά αυτό είναι αυτό που μας περιμένει την επόμενη εβδομάδα. Και σε γενικές γραμμές, όταν σκεφτόμαστε λίγο λίγο πιο δύσκολο για οποιοδήποτε τέτοιο πρόβλημα. Έχουμε n τετράγωνο στα αριστερά, n τετράγωνο στη μέση, και Ν log n στα δεξιά. Έτσι, υπάρχει πραγματικά δραματική στιγμή σας. Θα τα πούμε τη Δευτέρα. [Χειροκρότημα]