>> ΟΜΙΛΗΤΗΣ 1: Γεια σε όλους!
Καλώς ήρθατε και πάλι στο τμήμα.
Τόσο ευτυχής να δει τόσα πολλά από εσάς τόσο εδώ, και όλους όσους παρακολουθούν σε απευθείας σύνδεση.
Έτσι, ως συνήθως, πίσω ευπρόσδεκτη.
Ελπίζω ότι όλοι είχαν μια υπέροχη Σαββατοκύριακο, γεμάτο ξεκούραση, χαλάρωση.
Ήταν όμορφα χθες.
Έτσι, ελπίζω να απολαύσατε την ύπαιθρο.
>> Έτσι, για πρώτη φορά δυο ανακοινώσεις.
Βαθμολόγησης.
Έτσι, οι περισσότεροι από εσάς θα έπρεπε να πάρει ένα e-mail από μένα για το Ξυστό Pset σας,
καθώς και η ταξινόμηση για το chipset 1.
Έτσι, μόνο ένα ζευγάρι πράγματα.
Να είστε βέβαιος να χρησιμοποιήσει check50 στο style50.
Αυτά εννοούνται να είναι πόρους για σας παιδιά,
για να βεβαιωθείτε ότι έχετε πάρει όπως πολλά σημεία, όπως μπορείτε να
χωρίς άσκοπα χάνοντας τους.
Έτσι, πράγματα όπως στυλ είναι πολύ σημαντικά.
Είμαστε πρόκειται να απογειωθεί για αυτό.
Μερικοί από εσάς μπορεί να έχουν ήδη παρατηρήσει ότι από το chipset σας.
Και check50 είναι μόνο ένα πραγματικά εύκολος τρόπος για να βεβαιωθείτε ότι
ότι είμαστε στην πραγματικότητα επιστρέφουν ό, τι θα πρέπει να επιστραφεί στον χρήστη,
και ότι τα πάντα λειτουργεί σωστά.
>> Στο δεύτερο σημείωμα, βεβαιωθείτε ότι σας φορτώνοντας τα πράγματα στο σωστό φάκελο.
Κάνει τη ζωή μου μόνο ένα λίγο πιο δύσκολο
αν φορτώνετε το chipset 2 σε Pset 1 γιατί όταν μπορώ να κατεβάσω τα πράγματα,
δεν κάνετε σωστή λήψη.
Και ξέρω ότι είναι λίγο ξεχαρβαλωμένος σε ένα σύστημα για να το συνηθίσετε,
αλλά απλά να είναι σούπερ προσεκτικοί, εάν μόνο για μένα,
έτσι ώστε όταν παίρνετε τα μηνύματα όπως σε δύο και είμαι ταξινόμησης.
Εάν δεν προκαλούν έχω να κοιτάξουμε όλα γύρω για το chipset σας.
Cool.
>> Ξέρω ότι είναι νωρίς, αλλά εγώ εντελώς πήγαν από τη φρουρά
από ένα δοκίμιο που είναι οφείλεται αυτή την Παρασκευή, ότι καθηγητές μου ήταν ακριβώς όπως, OH ναι.
Θυμηθείτε, έχετε ένα δοκίμιο αναμένονται την Παρασκευή.
Έτσι, ξέρω ότι κανείς δεν συμπαθεί να σκεφτούμε εξετάσεις προόδου,
αλλά η πρώτη σας κουίζ είναι στις 15 Οκτωβρίου η οποία Οκτώβριο ξεκινά αυτή την εβδομάδα.
Έτσι, θα μπορούσε να είναι νωρίτερα από ό, τι αναμενόταν είναι όλα.
Έτσι, ότι δεν είστε ρίχνονται από τη φρουρά όταν Αναφέρω ενότητα την επόμενη εβδομάδα ότι OH,
κουίζ επόμενη εβδομάδα σας, σκέφτηκα Θα σας δώσω ένα λίγο πιο
του ένα heads-up τώρα.
>> Έτσι, ορίστε το πρόβλημα σας, τον αριθμό τρία.
Πώς οι άνθρωποι έχουν διαβάσει το spec από περιέργεια;
ΟΚ.
Πήραμε ένα ζευγάρι.
Είδος κάτω από την τελευταία εβδομάδα, αλλά αυτό είναι εντάξει.
Ξέρω ότι ήταν όμορφη έξω.
Έτσι Break Out.
Σίγουρα μετά την έχετε κάνει διαβάσετε σήμερα spec σας τουλάχιστον
προσπαθήσουμε, όπως το κατέβασμα Κωδικός διανομής και λειτουργίας
όπως την πρώτη αρχική πράγμα που θα σας ζητήσω να.
Επειδή είμαστε χρησιμοποιώντας Κωδικός διανομής και μια βιβλιοθήκη
ότι έχουμε μόνο using-- --It μόνο η δεύτερη φορά που έχουμε κάνει αυτό το chipset,
τρελά πράγματα μπορούν να συμβούν με τη συσκευή σας,
και θέλετε να βρείτε ότι έξω τώρα σε σχέση με αργότερα.
>> Διότι αν είναι Πέμπτη το βράδυ ή είναι Το βράδυ της Τετάρτης και για κάποιο λόγο
η συσκευή σας δεν κάνει μόνο θέλετε να εκτελέσετε με τη βιβλιοθήκη
ή με τη διανομή κώδικα, ότι μέσα
δεν μπορείτε καν να αρχίσουν να κάνουν την κωδικοποίηση.
Επειδή δεν μπορείτε να ελέγξετε για να δείτε αν αυτό δουλεύει.
Δε θα σας να είναι σε θέση για να δούμε αν αυτό συγκεφαλαιώνει.
Θέλετε να αναλάβει τη φροντίδα εκείνων νωρίς η εβδομάδα, όταν μπορείτε ακόμα να στείλετε email μου
ή ένα από τα άλλα ΤΡ, και μπορούμε να πάρουμε εκείνα που έχουν καθοριστεί.
Επειδή αυτά είναι ζητήματα που πρόκειται να σας σταματήσει
από προβεί σε οποιαδήποτε πραγματική πρόοδο.
Δεν είναι όπως ένα σφάλμα, ότι μπορείτε να ακριβώς το είδος του να υπερπηδήσει.
Αν αντιμετωπίζετε προβλήματα με σας συσκευή ή τον κωδικό διανομής,
θέλετε πραγματικά να πάρει ότι λαμβάνονται φροντίδα του νωρίτερα παρά αργότερα.
Έτσι, ακόμα και αν δεν είστε gonna πραγματικότητα την έναρξη της κωδικοποίησης, κατεβάστε τη διανομή
κώδικα, διαβάστε το spec, βεβαιωθείτε ό, τι δουλεύει εκεί.
Εντάξει;
Εάν μπορείτε να κάνετε ακριβώς αυτό, εγώ υπόσχονται ζωή σας θα είναι ευκολότερη.
Και έτσι είστε κατά πάσα πιθανότητα θα για να το κάνετε τώρα σωστά;
ΟΚ.
Έτσι, οποιεσδήποτε ερωτήσεις εκεί;
Τυχόν υλικοτεχνική πράγματα;
Ο καθένας είναι καλό;
ΟΚ.
>> Αποποίηση ευθυνών για εκείνους της σας στην αίθουσα και στο διαδίκτυο.
Πάω να προσπαθεί να στραφούν μεταξύ του PowerPoint στη συσκευή
επειδή πρόκειται να κάνει κάποια κωδικοποίηση
σήμερα από την λαϊκή απαίτηση της ανώνυμης πρόταση δημοσκόπηση έστειλα την περασμένη εβδομάδα.
Έτσι, θα πρέπει να κάνει κάποια κωδικοποίηση.
Έτσι, αν εσείς θέλετε, επίσης, να ανάψουν τις συσκευές σας,
και θα πρέπει να έχεις ένα email από μένα, με ένα δείγμα αρχείου.
Παρακαλώ μη διστάσετε να το κάνουμε αυτό.
>> Έτσι, θα πάμε να μιλήσουμε για GDB, το οποίο είναι ένα πρόγραμμα εντοπισμού σφαλμάτων.
Δεν πρόκειται να σας βοηθήσει το είδος των καταλάβω πού
Τα πράγματα πηγαίνουν στραβά στον κώδικά σας.
Είναι πραγματικά μόνο ένας τρόπος για να ενισχύσουν μέσω του κωδικού σας, καθώς αυτό συμβαίνει,
και να είναι σε θέση να εκτυπώσετε τις μεταβλητές ή να δούμε τι πραγματικά συμβαίνει
Κάτω από το καπό στίχοι πρόγραμμα σας απλά τρέχει, είναι σαν προβληματική,
και είστε όπως, καμία ιδέα τι ακριβώς συνέβη εδώ.
Δεν ξέρω ποια γραμμή που απέτυχε σε.
Δεν ξέρω πού πήγε στραβά.
Έτσι, GDB πρόκειται να σας βοηθήσει με αυτό.
Επίσης, αν αποφασίσετε να συνεχίσει ναι, και να λάβει 61,
αυτό θα είναι πραγματικά, πραγματικά να σας Ο καλύτερος φίλος, αιτία μπορώ να σας πω
επειδή Πάω μέσα αυτής της κατηγορίας.
>> Εμείς πάμε για να δούμε σε δυαδικό αναζήτησης, η οποία αν εσείς θυμάστε
το μεγάλο παράδειγμα τηλεφωνικό κατάλογο θέαμα από την τάξη.
Θα πρέπει να εκτελεστικές ότι, και περπατώντας μέσα από αυτό λίγο περισσότερο,
και στη συνέχεια θα πάμε μέσω τεσσάρων διαφορετικά είδη, τα οποία είναι φούσκα,
Επιλογή, Εισαγωγή, και Συγχώνευση.
Cool.
Έτσι, GDB, όπως ανέφερα, είναι ένα πρόγραμμα εντοπισμού σφαλμάτων.
Και αυτά είναι το είδος του μεγάλου τα πράγματα, οι μεγάλες λειτουργίες ή εντολές
ότι μπορείτε να χρησιμοποιήσετε μέσα GDB, και εγώ θα τα πόδια σας μέσα από ένα demo του σε ένα δευτερόλεπτο.
>> Έτσι, αυτό δεν είναι μόνο πρόκειται να μείνει αφηρημένη.
Θα προσπαθήσω και να το καταστήσει ως σκυρόδεμα όσο το δυνατόν για σας παιδιά.
Έτσι, να σπάσει.
Θα είναι είτε διάλειμμα όπως, κάποιος αριθμός, ο οποίος
αντιπροσωπεύει μια γραμμή στο πρόγραμμά σας, ή μπορείτε να ονομάσετε μια λειτουργία.
Έτσι, αν σας πω σπάσει κύρια, θα σταματήσει σε κεντρικό,
και αφήστε τα πόδια σας μέσα από τη λειτουργία αυτή.
>> Ομοίως, εάν έχετε κάποια εξωτερική λειτουργούν όπως Swap ή Cube,
ότι κοιτάξαμε την περασμένη εβδομάδα.
Εάν λέτε να σπάσει ένα από αυτά, κάθε φορά που το πρόγραμμα σας χτυπά ότι,
αυτό θα σας περιμένουν να πείτε τι να κάνει.
Πριν από αυτό θα εκτελέσει ακριβώς έτσι θα μπορούσε στην πραγματικότητα βήμα μέσα στη συνάρτηση
και να δούμε τι συμβαίνει.
Έτσι, την επόμενη, προσπερνάει ακριβώς πάνω από το επόμενη γραμμή, πηγαίνει πάνω λειτουργίες.
Βήμα.
Όλα αυτά είναι λίγο αφηρημένη.
Έτσι, είμαι απλώς πρόκειται να τρέξει μέσα από αυτά, αλλά θα τα δείτε σε χρήση σε ένα δευτερόλεπτο.
>> Βήμα σε λειτουργία.
Έτσι, όπως έλεγα, όπως με Swap, θα ήταν
σας επιτρέπουν να πραγματικά σαν να είστε όπως φυσικά Μπαίνοντας μέσα,
μπορείτε να το χάος με αυτές τις μεταβλητές, εκτύπωση τι είναι, να δούμε τι συμβαίνει.
Λίστα θα κυριολεκτικά εκτύπωση από τον περιβάλλοντα κώδικα.
Έτσι, αν το είδος των ξεχάσετε όπου είστε στο πρόγραμμά σας,
ή αναρωτιέστε τι συμβαίνει γύρω από αυτό,
Αυτό θα εκτυπώσετε μόνο ένα τμήμα του αρέσει πέντε ή έξι γραμμές γύρω από αυτό.
Έτσι, μπορείτε να προσανατολιστείτε σχετικά με το πού βρίσκεστε.
>> Εκτυπώστε κάποια μεταβλητή.
Έτσι, εάν έχετε το κλειδί, όπως σε Καίσαρα, που θα εξετάσουμε.
Μπορείτε να πείτε Εκτύπωση Κλειδί σε οποιοδήποτε σημείο.
Θα σας πω ποια είναι η αξία είναι έτσι ότι, ίσως κάπου στην πορεία,
σβήσατε το κλειδί σας.
Μπορείτε πραγματικά να πω ότι επειδή μπορείτε να παρατηρήσετε πραγματικά αυτή την τιμή.
>> Στους ντόπιους, ακριβώς εκτυπώσεις από τις τοπικές μεταβλητές σας.
Έτσι, ανά πάσα στιγμή είστε μέσα σε ένα βρόχο, και απλά θέλετε να δείτε, όπως, oh.
Τι είναι το εγώ μου;
Τι είναι αυτή η βασική αξία ότι έχω προετοιμαστεί εδώ;
Ποιο είναι το μήνυμα σε αυτό το σημείο;
Θα εκτυπώσετε μόνο όλα από αυτούς, έτσι ώστε να
Δεν χρειάζεται να ατομικά λένε, Εκτύπωση Ι Εκτύπωση μηνύματος.
Εκτύπωση Key.
Και στη συνέχεια να εμφανίσετε.
Αυτό που κάνει είναι, όπως σας βήμα μέσα από το πρόγραμμα,
θα πρέπει ακριβώς να βεβαιωθείτε ότι είναι εμφανίζοντας κάποια ορισμένη μεταβλητή
σε κάθε σημείο.
Έτσι ώστε να also-- --it είναι το είδος της συντόμευσης όπου
δεν χρειάζεται να συνεχίσουμε όπως, oh.
Εκτύπωση κλειδιά ή Εκτύπωση I. Είναι απλά θα το κάνει αυτόματα για εσάς.
>> Έτσι, με αυτό, θα πάμε για να δούμε πώς θα πάει.
Πάω να προσπαθήσουμε και διακόπτη πάνω στην συσκευή μου.
Δείτε αν μπορώ να το κάνω αυτό.
Όλα.
Είμαστε ακριβώς πρόκειται να το αντιγράψει.
Δεν υπάρχει τίποτα τρελό για το laptop μου ούτως ή άλλως.
ΟΚ.
Αυτό πρέπει να είναι αυτό.
Είναι τόσο μικρό.
Ας δούμε αν μπορούμε να το κάνουμε αυτό.
>> ΟΚ.
Η Alice είναι προφανώς αγωνίζονται εδώ ακριβώς λίγο,
αλλά θα το πάρει σε ένα momento.
ΟΚ.
Είμαστε ακριβώς πρόκειται να αυξήσει αυτό.
ΟΚ.
Μπορεί ο καθένας το είδος δείτε ότι;
Ίσως λίγο;
Ξέρω ότι είναι λίγο μικρό.
Δεν μπορεί να είναι αρκετά να καταλάβω πώς να κάνει αυτό μεγαλύτερο.
Αν κάποιος ξέρει.
Ξέρει κανείς πώς να κάνει το μεγαλύτερο;
ΟΚ.
Εμείς πάμε για να κυλήσει με αυτό.
Δεν πειράζει έτσι κι αλλιώς επειδή είναι ακριβώς αυτός είναι ο κώδικας που εσείς πρέπει να
έχουν.
>> Τι είναι πιο σημαντικό είναι το τερματικό εδώ.
Και έχουμε εδώ Γιατί είναι τόσο μικρή;
Ρυθμίσεις.
Ω.
Αληθινή Ike.
Πώς είναι αυτό;
Από εκεί.
Είναι ότι καλύτερο για όλους;
ΟΚ ,.
Cool.
>> Ξέρεις, όταν είσαι σε μια CS κατηγορία τεχνικές δυσκολίες
είναι το είδος του μέρους του the-- Έτσι, ας ξεκαθαρίσουμε αυτό.
ΟΚ.
Έτσι, εδώ στο τμήμα, που είχαμε εδώ.
Καίσαρας είναι ένα εκτελέσιμο αρχείο.
Έτσι έκανα.
Έτσι, ένα πράγμα που πρέπει να συνειδητοποιήσουμε με GDB είναι ότι λειτουργεί μόνο σε εκτελέσιμα αρχεία.
Έτσι, δεν μπορείτε να εκτελέσετε σε ένα dotsy.
Θα πρέπει να κάνετε πραγματικότητα βεβαιωθείτε ότι ο κώδικας συγκεντρώνει,
και ότι μπορεί πραγματικά να τρέξει.
>> Έτσι, βεβαιωθείτε ότι αν δεν το κάνει συγκεντρώνουν, να το πάρετε για την κατάρτιση,
έτσι ώστε να μπορείτε να το είδος του τρέχει μέσα από αυτό.
Έτσι, για να ξεκινήσει η GDB, το μόνο που κάνετε, Gloria Τύπος GDB, και στη συνέχεια, μόλις η
αρχείο που θέλετε.
Πάντα ανορθογραφώ Καίσαρα.
Αλλά θέλετε να βεβαιωθείτε δεδομένου ότι είναι ένα εκτελέσιμο,
dot flash ti έτσι ώστε σημαίνει ότι θα πάμε
να τρέξει CSI θα πάμε να εκτελέσει το αρχείο αυτό είτε με το πρόγραμμα εντοπισμού σφαλμάτων.
ΟΚ.
Έτσι, το κάνετε αυτό, μπορείτε να πάρετε Αυτό το είδος της ασυναρτησίες.
Είναι ακριβώς όλα τα πράγματα για το πρόγραμμα εντοπισμού σφαλμάτων.
Δεν χρειάζεται πραγματικά να ανησυχείτε γι 'αυτό τώρα.
Και όπως βλέπετε, έχουμε αυτό ανοιχτή parens, ΑΕΠ, κοντά parens,
και ακριβώς το είδος του μοιάζει γραμμή εντολών μας, σωστά;
>> Έτσι, αυτό που θέλουμε να do-- --So, Το πρώτο πράγμα
Είναι θέλουμε να επιλέξετε ένα μέρος για να το σπάσει.
Έτσι, υπάρχει ένα bug σε αυτό το πρόγραμμα Καίσαρα
ότι έχω εισαγάγει, ότι θα πάμε για να μάθετε.
Είναι αυτό που κάνει είναι να παίρνει την είσοδο Barfoo σε όλα τα καλύμματα, και για κάποιο λόγο
αυτό δεν αλλάζει Α Αφήνει μόνο αυτό και μόνο, είναι ό, τι άλλο σωστή,
αλλά η δεύτερη επιστολή Α παραμένει αμετάβλητη.
Έτσι, θα πάμε για να προσπαθήσουμε και να καταλάβω γιατί συμβαίνει αυτό.
Έτσι, το πρώτο πράγμα που συνήθως θέλετε να κάνετε κάθε φορά που ξεκινάτε για GDB
Είναι καταλάβω πού να το σπάσει.
>> Έτσι ο Καίσαρας είναι ένα αρκετά σύντομο πρόγραμμα.
Εμείς απλά έχουμε μια λειτουργία, σωστά;
Ποια ήταν η λειτουργία μας στον Καίσαρα;
Υπάρχει μόνο μία λειτουργία, Κύρια σωστά;
Main είναι μια συνάρτηση για όλα τα προγράμματά σας.
Εάν δεν έχουν την κύρια, θα ήθελα να να είναι λίγο ανήσυχος τώρα,
αλλά ελπίζω να περάσατε Κύρια εκεί.
Έτσι, αυτό που μπορούμε να κάνουμε είναι να μπορούμε να απλά να σπάσει Κύριο, έτσι απλά.
Έτσι, λέει, εντάξει.
Θέτουμε ένα breakpoint μας εκεί.
>> Έτσι, τώρα το πράγμα που πρέπει να θυμάστε είναι Καίσαρα λαμβάνει μία εντολή δεξιά επιχείρημα της γραμμής
και δεν έχουμε κάνει ότι πουθενά ακόμα.
Έτσι, αυτό που κάνουμε είναι όταν μπορείτε πραγματικά να πάει να τρέξει
το πρόγραμμα, κάθε πρόγραμμα που είστε τρέξιμο στην GDB που χρειάζεται γραμμή εντολών
επιχειρήματα, θα πάμε στην είσοδο όταν ξεκινάτε για πρώτη φορά τη λειτουργία του.
Έτσι, στην περίπτωση αυτή, κάνουμε Τρέξτε με ένα κλειδί των τριών.
Και θα αρχίσετε πραγματικά.
>> Έτσι, αν δείτε εδώ, έχουμε Αν RC δεν είναι ίση με 2.
Έτσι, αν εσείς έχετε όλα ότι το αρχείο που έστειλα επάνω
θα δείτε ότι είναι σαν το πρώτη γραμμή κύρια λειτουργία μας, σωστά;
Είναι έλεγχο για να δούμε αν έχουμε ο σωστός αριθμός των επιχειρημάτων.
Έτσι, αν αναρωτιέστε εάν RC είναι σωστή,
μπορείτε να κάνετε κάτι σαν Εκτύπωση RC.
RC είναι δύο, η οποία είναι ό, τι περιμέναμε, σωστά;
>> Έτσι, μπορούμε να πάμε Επόμενο, και να συνεχίσει μέσα.
Έτσι, έχουμε κάποια βασικά εκεί.
Και μπορούμε να εκτυπώσετε το κλειδί μας για να βεβαιωθείτε ότι είναι σωστό.
Ενδιαφέρουσες.
Δεν είναι ακριβώς αυτό που περιμέναμε.
Έτσι, ένα πράγμα που πρέπει να συνειδητοποιήσουμε με GDB, επίσης, είναι
ότι δεν είναι πραγματικά μέχρι να χτυπήσει Στη συνέχεια, η γραμμή που μόλις είδατε
είναι πράγματι εκτελεστεί.
Έτσι, σε αυτή την περίπτωση Key δεν έχει εκχωρηθεί ακόμη.
Έτσι, Βασικά είναι κάποια αξία σκουπίδια ότι βλέπετε στο κάτω μέρος εκεί.
Αρνητική $ 120-- --It ένα δισεκατομμύριο και κάτι περίεργα πράγματα σωστά;
Δεν είναι το κλειδί που περιμέναμε.
Αλλά αν έχουμε χτυπήσει την επόμενη, και στη συνέχεια εμείς δοκιμάστε και πλήκτρο Print, είναι τρεις.
>> Όλοι βλέπουμε ότι;
Έτσι, αν έχετε κάτι ότι είστε όπως, περιμένετε.
Αυτό είναι εντελώς λάθος, και δεν ξέρω
πώς αυτό θα συμβεί, γιατί το μόνο που θέλω να κάνετε είναι να ορίσετε έναν αριθμό, μια μεταβλητή,
δοκιμάστε το χτύπημα Στη συνέχεια, προσπαθήστε να εκτυπώσετε και πάλι, και να δούμε αν αυτό λειτουργεί.
Επειδή πρόκειται μόνο για την εκτέλεση και πραγματικά εκχωρήσετε κάτι μετά
χτύπησε Επόμενο.
Έχουν νόημα για όλους;
Λέμε τώρα;
>> ΟΜΙΛΗΤΗΣ 2: Όταν τυχαία αριθμούς τι σημαίνει αυτό;
>> ΟΜΙΛΗΤΗΣ 1: Είναι απλά τυχαίο.
Είναι απλά σκουπίδια.
Είναι απλά κάτι που σας υπολογιστής θα εκχωρήσει τυχαία.
Cool.
Έτσι, τώρα μπορούμε να κινηθούμε μέσα, και έτσι Τώρα έχουμε αυτό το απλό GetString κειμένου.
Έτσι, επιτρέψτε μου να εισαγάγει τι θα συμβεί όταν χτύπησε Επόμενο εδώ.
GDB μας είδος εξαφανίζεται, σωστά;
Αυτό συμβαίνει γιατί GetString τώρα εκτέλεση, σωστά;
Έτσι, όταν είδαμε απλό κείμενο ισούται GetString, ανοιχτή parens και parens,
και χτυπάμε συνέχεια, ότι έχει πράγματι εκτελεστεί τώρα.
Έτσι, σας περιμένει για μας σε κάτι εισόδου.
>> Έτσι, θα πάμε στην είσοδο τροφίμων μας που είναι ό, τι είναι αδυναμία, όπως σας είπα
και ότι ακριβώς λέει ότι είναι τελειώσει την εκτέλεση, ότι το κλειστό
βραχίονα σημαίνει ότι είναι που εξέρχεται από την εν λόγω βρόχο.
Έτσι, μπορούμε να χτυπήσει την επόμενη, και τώρα, όπως είμαι ότι είστε όλοι εξοικειωμένοι από τον Καίσαρα,
Αυτό είναι, τι είναι αυτή η γραμμή πρόκειται να κάνει.
Είναι για Int Ι ισούται με μηδέν, Ν ισούται Strlen, απλό κείμενο, και στη συνέχεια,
Ι είναι μικρότερο από το η, I, συν, συν.
Τι είναι αυτός ο βρόχος πρόκειται να κάνει;
Ανοίξτε το μήνυμά σας.
Cool.
Οπότε, ας αρχίσει να κάνει αυτό.
>> Έτσι, θα πρέπει αυτή η κατάσταση ταιριάζουν, για πρώτη μας;
Αν πρόκειται για ένα Β, είναι απλό κείμενο I. Εμείς μπορεί να πάρει πληροφορίες για τους ντόπιους μας.
Έτσι, είναι μηδέν, και αν έξι, που περιμένουμε, και το κλειδί μας είναι τρεις.
Το μόνο που έχει νόημα, σωστά;
Αυτοί οι αριθμοί είναι όλα και τι ακριβώς πρέπει να είναι.
Έτσι, βουητό;
ΟΜΙΛΗΤΗΣ 3: Έχω τυχαίων αριθμών για το δικό μου.
ΟΜΙΛΗΤΗΣ 1: Λοιπόν, μπορούμε να --we check-- μπορούν να συνομιλήσουν για αυτό σε μια δεύτερη.
Αλλά θα πρέπει να πάρει αυτό.
Έτσι, αν έχουμε ένα κεφάλαιο Β για πρώτη μας,
Αυτή η κατάσταση πρέπει να το πιάσει, σωστά;
Έτσι, αν έχουμε χτυπήσει συνέχεια, βλέπουμε ότι αυτό το Αν εκτελεί στην πραγματικότητα.
Διότι, αν είστε μετά μαζί με τον κωδικό σας,
Αυτή η γραμμή εδώ, όπου απλού κειμένου μου αντικαθίσταται με αυτήν την αριθμητική,
εκτελεί μόνο εάν το Αν προϋπόθεση είναι η σωστή σωστά;
>> GDB είναι μόνο για να σας δείξω πράγματα που είναι πραγματικά εκτέλεσης.
Έτσι, αν η προϋπόθεση αυτή Αν δεν πληρούνται, είναι ακριβώς πρόκειται να προχωρήσετε στην επόμενη γραμμή.
Εντάξει;
Έτσι, έχουμε ότι.
Ο βραχίονας αυτός σημαίνει ότι είναι κλειστά από αυτό το βρόχο τώρα.
Έτσι, πρόκειται να ξεκινήσει και πάλι.
Ακριβώς έτσι.
Έτσι, ότι μπορούμε να πάρουμε πληροφορίες για τους ντόπιους μας εδώ,
και βλέπουμε ότι η πρώτη μας επιστολή έχει αλλάξει, σωστά;
Είναι τώρα ένα Ε, όπως θα έπρεπε να είναι.
Έτσι, μπορούμε να συνεχίσουμε.
>> Και έχουμε αυτόν τον έλεγχο.
Και αυτός ο έλεγχος θα πρέπει να λειτουργήσει, σωστά;
Είναι Α θα πρέπει να αλλάξει τρεις επιστολές προς τα εμπρός.
Αλλά αν παρατηρήσετε, θα να πάρει κάτι διαφορετικό.
Έτσι, σε αυτή την περίπτωση εδώ, είναι που αλιεύονται αυτό, και έτσι αυτή η γραμμή εκτελείται,
που τροποποίησε Β μας Όμως, σε αυτή την περίπτωση εδώ,
έχουμε ότι ακριβώς παραλείπεται, και πήγε στο [; L Siff. ?]
Έτσι, κάτι συμβαίνει εκεί.
Αυτό που σου λέει είναι ότι, γνωρίζουμε ότι θα πρέπει να πιάσει εδώ,
αλλά δεν είναι.
Μπορεί ο καθένας να δούμε τι μας το πρόβλημα είναι σε αυτή τη γραμμή;
Είναι ένα πολύ λεπτό πράγμα.
Και θα μπορούσε επίσης να εξετάσουμε τον κωδικό σας.
Είναι επίσης line-- ξεχνάμε ποια γραμμή είναι σε there-- αλλά είναι στο [δεν ακούγεται].
Ναι;
>> ΟΜΙΛΗΤΗΣ 4: Είναι στο μεγαλύτερο από σελίδα, αν μπορείτε να το διαβάσετε στο βιβλίο.
ΟΜΙΛΗΤΗΣ 1: Ακριβώς.
Έτσι, το πρόγραμμα εντοπισμού σφαλμάτων δεν θα μπορούσε να πει σας ότι, αλλά το πρόγραμμα εντοπισμού σφαλμάτων
θα μπορούσε να πιάσουμε μια γραμμή ότι ξέρετε δεν λειτουργεί.
Και μερικές φορές, όταν ειδικά αργότερα στο εξάμηνο, όταν
έχουμε να κάνουμε με ένα εκατό, ένα Εκατό λίγες γραμμές κώδικα, και σας
Δεν ξέρω πού είναι αδυναμία, Αυτό είναι ένας πολύ καλός τρόπος για να το κάνουμε.
Έτσι, βρήκαμε το σφάλμα μας.
Μπορείτε να το διορθώσετε στο αρχείο σας, και τότε θα μπορούσε να τρέξει και πάλι,
και όλα θα λειτουργούν τέλεια.
Και το μεγαλύτερο πράγμα είναι Αυτό μπορεί να φαίνεται σαν, εντάξει.
Ναι.
Cool.
Μπορείτε ήξερε τι ψάχνετε.
Έτσι, θα ήξερε τι να κάνει.
>> GDB μπορεί να είναι εξαιρετικά χρήσιμη γιατί σας μπορεί να εκτυπώσει όλα αυτά τα πράγματα που σας
δεν θα ήταν.
Είναι πολύ πιο χρήσιμο από ό, τι printf.
Πόσοι από εσάς χρησιμοποιείτε όπως δηλώσεις printf
για να καταλάβω, όπου ένα ζωύφιο, σωστά;
Έτσι, με αυτό, δεν το κάνετε πρέπει να συνεχίζω πίσω,
και τους αρέσει σχολιάζοντας Printf, ή σχολιάζοντας έξω,
και να καταλάβω τι θα πρέπει να εκτυπώσετε.
Αυτό πραγματικά σας επιτρέπει ακριβώς να βήμα μέσα, εκτυπώστε τα πράγματα
όπως περνάτε, έτσι, μπορείτε να παρατηρήσουμε πώς αλλάζουν σε πραγματικό χρόνο,
ως πρόγραμμα τρέχει.
>> Και αυτό έχει πάρει λίγο λίγο να συνηθίσει.
Θα συνιστούσα ανεπιφύλακτα ακριβώς το είδος να είναι λίγο απογοητευμένος με αυτό
για τώρα.
Εάν περάσετε μια ώρα πάνω από το την επόμενη εβδομάδα μαθαίνοντας πώς να χρησιμοποιήσετε GDB,
θα σώσει τον εαυτό σας τόσο πολύ χρόνο αργότερα.
Και κυριολεκτικά. λέμε Αυτό σε ανθρώπους κάθε χρόνο,
και θυμάμαι όταν πήρα το τάξη, ήμουν όπως, θα είμαι μια χαρά.
Όχι.
Pset 6 ήρθε και ήμουν όπως, είμαι θα μάθω
πώς να χρησιμοποιήσετε GDB επειδή εγώ δεν κάνω γνωρίζουν τι συμβαίνει εδώ.
>> Έτσι, εάν παίρνετε το χρόνο έτσι χρησιμοποιήσετε σε μικρότερα προγράμματα
ότι θα πάμε να είναι που εργάζονται σε, όπως την εργασία
μέσα από κάτι σαν Visionare, όπως αυτό.
Ή αν θέλετε επιπλέον πρακτική, είμαι βέβαιος Θα μπορούσα να καταλήξουμε σε προγράμματα λάθη,
για σας για να διορθώσετε αν θέλετε.
>> Αλλά αν απλά χρειάζεται κάποιο χρόνο για να πάρει που χρησιμοποιούνται σε αυτό, απλά παίζουν με αυτό,
θα σας εξυπηρετήσει πολύ καλά.
Και αυτό είναι πραγματικά ένα από τα αυτά τα πράγματα που απλά
Πρέπει να δοκιμάσετε, και να πάρετε τα χέρια σας βρώμικα με, προτού να καταλάβουν πραγματικά.
Πραγματικά μόνο αυτό κατανοητό φορά Έπρεπε να διορθώσετε τα πράγματα με αυτό,
και αυτό είναι πολύ καλύτερο να έχουμε μια ιδέα του πώς να debug νωρίτερα παρά αργότερα.
ΟΚ.
Cool.
Ξέρω ότι είναι κάτι σαν μια πορεία σύγκρουσης στην GDB,
και εγώ σίγουρα θα εργαστούμε για να πάρει αυτά να φαίνονται μεγαλύτερα επόμενη φορά.
Cool.
>> Έτσι, αν πάμε πίσω στο PowerPoint μας.
Είναι αυτό πρόκειται να λειτουργήσει;
AWH.
Ναι.
ΟΚ.
Έτσι, αν ποτέ χρειαστείτε κάποιο από εκείνους πάλι, υπάρχει η λίστα.
Έτσι δυαδική αναζήτηση, που ο καθένας θυμάται το μεγάλο θέαμα του Δαβίδ
αντιγραφή τηλέφωνο βιβλία στο μισό.
Εγώ δεν πραγματικά να πάρει το τηλέφωνο βιβλία πια,
γιατί όπως όταν κάνετε πάρετε τηλέφωνο βιβλία αυτές τις μέρες;
Πραγματικά δεν ξέρω.
Η δυαδική αναζήτηση.
Υπάρχει κάποιος που θυμάται πώς εκτελέσιμο δουλεύει αναζήτησης;
Όποιος καθόλου;
Ναι;
ΟΜΙΛΗΤΗΣ 5: Ξέρετε πότε κοιτάς τα οποία τα μισά
θα ήταν σε, με βάση αυτή, και να απαλλαγούμε από το άλλο μισό.
>> ΟΜΙΛΗΤΗΣ 1 Ακριβώς.
Έτσι, δυαδική αναζήτηση, αυτό είναι το είδος της a-- --we ήθελα να καλέσω το διαίρει και βασίλευε.
Έτσι, αυτό που θα κάνουμε είναι θα δούμε στη μέση,
και θα δείτε αν ταιριάζει αυτό που ψάχνετε.
Και αν δεν το κάνει, τότε θα προσπαθήσει να καταλάβω, είναι αυτό που πηγαίνει να μείνει
το μισό ή το δεξί μισό.
Έτσι, αυτό θα μπορούσε να είναι, αν ψάχνετε σε κάτι που είναι αλφαβητικά,
βλέπετε, oh.
Μήπως Allison έρθει πριν από Μ;
Ναι.
Έτσι, θα πάμε να εξετάσουμε το πρώτο εξάμηνο.
>> Ή θα μπορούσε να είναι όπως και με τους αριθμούς.
Οτιδήποτε που μπορείτε να συγκρίνουν, να μπορούν να ταξινομηθούν.
Μπορείτε να χρησιμοποιήσετε τη δυαδική αναζήτηση για.
Έτσι, κάποιος που θυμάται αυτό γράφημα ή τι είναι αυτό;
Είναι Ασυμπτωτική Πολυπλοκότητα.
Έτσι, αυτή η γραφική παράσταση μόνο περιγράφει πόσο καιρό
Σας χρειάζεται για να λύσει ένα πρόβλημα, όπως θα αυξήσει τον αριθμό των πραγμάτων
ότι είστε χρησιμοποιώντας.
>> Έτσι, έχουμε Ν, το οποίο είναι γραμμικό χρόνο.
Εάν N πάνω από δύο, το οποίο είναι ελαφρώς καλύτερα, εξακολουθεί να αναπτύσσεται εξαιρετικά γρήγορα.
Και τότε έχουμε Είσοδος, το οποίο είναι τι θεωρούμε δυαδική αναζήτηση.
Αν παρατηρήσετε, καθώς το πρόβλημά σας παίρνει πολύ και πολύ μεγαλύτερη,
το χρόνο που χρειάζεται για να το λύσουμε δεν έχει πραγματικά αυξηθεί τόσο πολύ.
Είναι σαν συγκρίσιμη εδώ στην αρχή.
Είσαι σαν, εντάξει.
Τίποτα εδώ δεν κάνει πραγματικά έχει σημασία ποια θα χρησιμοποιήσετε,
αλλά μπορείτε να πάρετε έξω με ένα εκατομμύριο, ένα δισεκατομμύριο.
Προσπαθείς να βρείτε some-- --you're προσπαθεί να βρει μια βελόνα στα άχυρα.
>> Νομίζω ότι θέλετε αυτό το πρόβλημα.
Θέλετε αυτής της πολυπλοκότητας, δεν γραμμική, γιατί για όλους σας
ξέρετε το gonna σας να ψάχνουν μέσα κάθε ατομική βελόνα, πράγμα σανό,
προσπαθούν να ψάξουν για τη βελόνα σας.
Και αυτό δεν είναι πάρα πολύ διασκεδαστικό κατά τη γνώμη μου.
Μου αρέσει γρήγορα.
Μου αρέσει αποτελεσματική.
Και όπως εργατικοί φοιτητές σας οι τύποι είναι, ξέρετε εργάζεστε εξυπνότερα,
δεν είναι δύσκολο πράγμα τύπου, πώς θα μπορούν να κάνουν αυτές τις αλγόριθμους.
>> Έτσι, θα πάμε να περπατήσει μέσω ακριβώς ένα γρήγορο παράδειγμα.
Νομίζω ότι τα παιδιά θα πρέπει να έχουν ένα χέρι σε δυαδική αναζήτηση,
αλλά σε περίπτωση που κάποιος είναι λίγο fuzzy, θέλουν να την ενισχύσει,
θα πάμε να φύγουμε μέσα από ένα παράδειγμα εδώ.
Έτσι, ψάχνουμε για το αν η σειρά περιέχει επτά.
>> Έτσι, το πρώτο πράγμα που κάνουμε είναι εξετάσουμε στη μέση, δεξιά;
Και επίσης, θα πάμε να κωδικοποίησης Δυαδική αναζήτηση σε μόλις ένα δευτερόλεπτο.
Έτσι, πρόκειται να είναι διασκέδαση.
Έτσι κοιτάξουμε το Μέση λίγο συστοιχίες 3.
Μήπως 3 ισούται με 7;
Δεν το κάνει.
Είναι έξι.
Έτσι, είναι μικρότερη από ή μεγαλύτερο από επτά;
Λιγότερο από.
Ναι.
Νίκαια παιδιά δουλειά.
Αισθάνομαι πως θα έπρεπε να έχουν καραμέλα γιατί
θέλουν να το ρίξει έξω στις αυλές.
Είναι αυτό που εγώ είμαι πρόκειται να κάνει την επόμενη εβδομάδα.
Θα σας κρατήσει παιδιά απότομη.
>> Έτσι, πετάμε ότι πρώτο εξάμηνο, σωστά;
ήταν λιγότερο από ό, τι.
γνωρίζουμε ότι τα πάντα σε αυτή την αριστερή πλευρά
πρόκειται να είναι μικρότερη από ό, τι είμαστε πραγματικά αναζητούν.
Έτσι, δεν υπάρχει καμία ανάγκη να να δώσουν προσοχή σε αυτό.
Απλά ξεχάστε το.
Έτσι, τώρα θα δούμε στο δεξί μας χέρι, και να κοιτάξουμε τη μέση εκεί πέρα,
και τώρα είναι εννέα.
Έτσι, 9 is-- --Everyone;
Μεγαλύτερη από ό, τι είμαστε αναζητούν, σωστά;
Έτσι, θα πάμε να ρίξει μακριά τα πάντα προς τα δεξιά.
Όπως αυτό.
Τώρα, το μόνο που μας μένει είναι μία.
Έτσι ελέγχουμε, είναι αυτό τι ψάχνουμε; είναι.
Βρήκαμε αυτό που θέλαμε.
Έτσι τελειώσαμε.
Διγραμμική αναζήτησης.
>> Και αν παρατηρήσετε, θα είχε επτά εισόδους εκεί.
Το μόνο που μας πήρε σαν τρεις φορές, αλλά αν κάνεις σαν ένα δισεκατομμύριο,
εσείς ξέρετε πόσα βήματα που θα να λάβει εάν είχαμε τέσσερα δισεκατομμύρια πράγματα;
Οποιαδήποτε εικασίες;
Είναι 32.
32 βήματα για να βρείτε κάτι σε τέσσερα δισεκατομμύρια
στοιχείο του πίνακα, λόγω των αρμοδιοτήτων των δύο.
Έτσι, δύο είναι 32, είναι σε τέσσερα δισεκατομμύρια.
>> Έτσι, πολύ τρελό πώς είστε ακόμα μέσα σαν ένα σχετικά μικρό αριθμό των βημάτων
να βρείτε κάτι στο τέσσερα δισεκατομμύρια στοιχεία.
Έτσι, σε αυτό το σημείωμα, είμαστε πρόκειται να κωδικοποιήσει αυτό
έτσι εσείς μπορείτε πραγματικότητα είδος δούμε πώς αυτό λειτουργεί.
Εντάξει, έτσι εσείς μπορεί να κωδικοποιήσει.
Πάω να σας παιδιά ας μιλήσουμε για λίγο.
Γνωρίστε τους ανθρώπους γύρω σας, η οποία είναι τι κάποιος ήθελε από την τελευταία ενότητα.
>> Έτσι, να γνωρίσουν τους ανθρώπους γύρω σας.
Συζήτηση για λίγο.
Και το μόνο που θέλω από σένα ρε παιδιά τώρα είναι απλά
προσπαθήστε να δημιουργήσετε ένα περίγραμμα του ψευδοκώδικα.
Εντάξει;
Πω πω.
Το μόνο που θέλω από σας παιδιά είναι είστε ακριβώς πρόκειται να συμπληρώσετε σε αυτό, ενώ την περίπτωση.
Γι 'αυτό και έχουν θέσει αυτά τα ανώτερα και κάτω όρια που
αντιπροσωπεύουν την αρχή και το τέλος της σειράς μας.
Και θα έχετε την ευκαιρία να πραγματικά βρόχο μέσα και να καταλάβω
τι κάνουμε σε αυτό το βρόχο while.
>> Έτσι, αν μπορείτε να υπολογίσετε out-- έχω ένας υπαινιγμός there-- ποιες είναι οι περιπτώσεις
ότι έχουμε εδώ;
Έτσι, εάν θέλετε να καταλάβω το περιπτώσεις, θα ψευδοκώδικα εκείνες
και στη συνέχεια θα κωδικοποιήσει τους πραγματικότητα.
Και αυτό πρόκειται να είναι, εγώ πιστεύω, ελπίζω ότι θα
να είναι λίγο πιο εύκολο από ό, τι θα περιμένατε.
Επειδή δεν είναι ότι μεγάλο μέρος του κώδικα, στην πραγματικότητα, η οποία είναι πραγματικά δροσερό.
>> MM-hm;
>> Φοιτητής: [δεν ακούγεται];
Διδάσκων: Ναι.
Υπήρχε κάτι να βρεθεί στη μέση.
>> Φοιτητής: Έτσι μπορούμε να χρησιμοποιήσουμε.
ΟΚ.
>> Διδάσκων: Τέλεια.
Έτσι, αυτό είναι το πρώτο πράγμα που πρέπει να κάνουμε.
Έτσι, βρείτε τη μέση.
Μεγάλη.
Έτσι έχετε μια ιδέα για το πώς θα μπορούσαμε να πραγματικά να βρει τη μέση με κωδικό;
>> Φοιτητής: Ναι.
n πάνω από 2;
Διδάσκων: Έτσι n πάνω από 2.
Έτσι, ένα πράγμα που πρέπει να θυμάστε είναι ότι άνω και κάτω όρια σας αλλάζουν.
Κρατάμε ασφυκτικά το μέρος της συστοιχίας ψάχνουμε να.
Έτσι n πάνω από 2 θα λειτουργήσει μόνο για το πρώτο πράγμα που κάνουμε.
Έτσι, λαμβάνοντας άνω και κάτω υπόψη, πώς θα μπορούσε να παίρνουμε ότι μεσαίο στοιχείο;
Επειδή θέλουμε την μέση μεταξύ των άνω και κάτω, σωστά;
MM-hm;
>> Φοιτητής: [δεν ακούγεται].
>> Διδάσκων: Έτσι έχουμε κάποια μέση.
Και αυτό θα είναι ανώτερο συνδυασμό με τις χαμηλότερες πάνω από 2.
Awesome.
Εκεί πάμε.
Μια γραμμή προς τα κάτω.
Εσείς είστε στο δρόμο σας.
Έτσι, τώρα που έχουμε μας μεσαίο, τι θέλουμε να κάνουμε;
Ακριβώς σε γενικές γραμμές.
Δεν χρειάζεται να το κωδικοποιήσει.
Ναι.
Φοιτητής: [δεν ακούγεται];
Διδάσκων: Έτσι είναι συν επειδή είστε εύρεση του μέσου όρου μεταξύ των δύο
από αυτούς.
Έτσι, αν σκεφτείτε τους ως είδος της αύξησης από τις πλευρές,
σκέφτομαι καθώς πλησιάζετε η μέση, θέλετε έτσι.
Έτσι, αν ήταν και στις δύο πλευρές του μέση, και έχουμε σαν 5 και 7.
Όταν τα προσθέσετε μαζί σας να πάρει 12, διαιρείτε με το 2, είναι 6.
>> Μερικές φορές είναι δύσκολο να εξηγήσει γιατί ότι λειτουργεί,
αλλά εάν εργάζεστε μέσω ένα παράδειγμα, μερικές φορές,
αυτό θα σας βοηθήσει να καταλάβω αν θα πρέπει να είναι συν ή μείον.
Ναι.
>> Φοιτητής: [δεν ακούγεται] ακριβώς στη μέση
αν είχαν μια περίπτωση όπου υπάρχει μια πολύ μικρότερους αριθμούς
και σαν ένας μεγάλος αριθμός;
>> Διδάσκων: Έτσι, το μόνο που χρειάζεστε είναι το μέσον της συστοιχίας.
Έτσι, αν είχατε μια δέσμη των μικρών αριθμών και στη συνέχεια ένα πραγματικά μεγάλο αριθμό
Στο τέλος, δεν έχει σημασία.
Το μόνο που έχει σημασία είναι ότι από όπου και αν ταξινομηθεί, απλά
θέλουμε να δούμε τη μέση του η συστοιχία γιατί είστε ακόμα
τεμαχισμό πρόβλημα σας στο μισό.
Cool.
Έτσι, τώρα που έχουμε το μεσαίο, τι κάνουμε το επόμενο βήμα;
>> Φοιτητής: Σύγκριση.
Διδάσκων: Η συγκρίνετε.
Έτσι συγκρίνετε μέση για να value_wanted.
Cool.
Έτσι βλέπετε εδώ έχουμε Η τιμή αυτή θέλουμε εδώ.
Θυμηθείτε ότι αυτό είναι ένας πίνακας.
Έτσι μέση αναφέρεται στο ευρετήριο.
Έτσι, θέλουμε να κάνουμε τις αξίες της μέσης.
Μην ξεχνάτε, αν θέλετε να συγκρίνουν, διπλά ίσων.
Μπορείτε να το κάνετε μόνο ισούται είστε ακριβώς πρόκειται να τις μεταβιβάσει εκ νέου,
και στη συνέχεια, φυσικά, είναι πρόκειται να είναι η τιμή που θέλετε.
Έτσι δεν το κάνουμε αυτό.
>> Έτσι θα πάμε να δούμε αν οι τιμές στη μέση
είναι ίση με την αξία που θέλουμε.
Μην ξεχάσετε τιράντες σας.
Dropbox θα πρέπει να πάει μακριά.
Οπότε τι κάνουμε σε αυτή την περίπτωση;
Αν είναι αυτό που θέλουμε να επιστρέψουν;
Προσπαθούμε να πω.
>> Φοιτητής: Εκτυπώστε μακριά.
>> Διδάσκων: Λοιπόν, εμείς Δεν θέλετε να εκτυπώσετε.
Έτσι, αυτό είναι μια bool εδώ, έτσι ώστε να θέλουν να επιστρέψουν αληθείς ή ψευδείς.
Εμείς λέμε, είναι αυτός ο αριθμός μια [? RRA; ?] Έτσι, αν αυτό είναι,
εμείς απλά επιστρέψει αλήθεια.
Αν μπορώ να συλλαβίσω αλήθεια.
>> Φοιτητής: Γιατί δεν θα σας επιστρέψει το μηδέν;
Διδάσκων: Έτσι, θα μπορούσατε επιστρέφει μηδέν, αν ήθελε.
Αλλά στην περίπτωση αυτή, επειδή λειτουργία μας επιστρέφει μια bool,
θα πρέπει να επιστρέψει είτε αληθείς ή ψευδείς.
Φοιτητής: Όταν είσαι λέγοντας boolean έκφραση,
μπορείτε να το ρυθμίσετε ψευδής;
Όπως και αν θέλω να πω, αν αυτή η προϋπόθεση δεν πληρούται, όπως είναι άνω ισούται με ψευδείς.
Θα το καταλάβετε αν απλά βάλει ψεύτικες από την άλλη πλευρά;
Διδάσκων: Ναι.
Έτσι, στην πραγματικότητα, εάν είστε ποτέ να κάνει κάτι
όπως είναι ανώτερο ή είναι χαμηλότερη, ότι επιστρέφει true ή false
και αυτό είναι πραγματικά κακό στυλ ας πούμε ισούται ισούται αλήθεια ή ισοτίμων
ισούται με ψευδείς.
Θέλετε να χρησιμοποιήσετε αυτό το αποτέλεσμα όπως η ίδια η επιταγή σας.
Δεν είναι αυτό που ήθελα.
Αυτό είναι ό, τι ήθελα.
Έτσι, στην περίπτωση του ζητάς περίπου κάτι σαν να σώσει αυτό το c.
>> Έτσι, αν έχουμε int main (void) και κάτι σαν αυτό.
Και έχετε, αν είναι ανώτερο κάποιας εισόδου και είστε
ρωτά εάν μπορείτε να το κάνετε κάτι σαν αυτό;
Σωστά;
ΣΠΟΥΔΑΣΤΩΝ: Προσπαθούσα να το κάνει [δεν ακούγεται].
Διότι, αν it's--
Διδάσκων: Δεξιά.
Έτσι θέλετε αυτό να είναι ψευδής, σωστά;
Φοιτητής: Ναι.
Διδάσκων: Έτσι, σε αυτή την περίπτωση θα θέλουν να εκτελέσει αν δεν είναι αλήθεια.
Έτσι, το δροσερό πράγμα που κάνετε εκεί είναι αυτό.
Έτσι θυμηθείτε θαυμαστικό σημείο αναιρεί τα πράγματα;
Λέει [δεν ακούγεται] δεν σημαίνει.
Έτσι, αν κοιτάξουμε μόνο αυτό το μέρος εδώ, τότε θα
λένε ότι αποτιμάται σε ψευδείς, όπως θέλετε να.
Δεν είναι ψευδείς είναι αληθινό αυτό που σημαίνει ότι αυτή θα εκτελέσει.
Μήπως αυτό έχει νόημα;
Φοιτητής: Ναι.
Διδάσκων: Awesome.
ΟΚ.
Έτσι, θα μπορούσαμε απλά να επιστρέψει αλήθεια σε αυτή την περίπτωση.
Έτσι τώρα έχουμε δύο άλλα περιπτώσεις σε αυτή την περίπτωση.
Ποιες είναι οι δύο άλλες υποθέσεις μας;
Ας το κάνουμε έτσι.
Ας αρχίσουμε λοιπόν με άλλο αν οι τιμές στη μέση
είναι μικρότερη από την τιμή που θέλουμε.
Έτσι αξία μας στη μέση είναι λιγότερο από την τιμή που ψάχνουμε.
>> Έτσι, η οποία δεσμεύεται να κάνετε πιστεύω ότι θέλετε να ενημερώσετε;
Πάνω ή κάτω;
Άνω;
Έτσι ποια πλευρά της συστοιχίας θα πάμε να εξετάσουμε;
>> ΜΑΘΗΤΗ: Το χαμηλότερο.
>> Διδάσκων: Εμείς θα πάμε να ψάχνει στα αριστερά.
Έτσι, άλλο αν λίγη αξία είναι μικρότερη.
Έτσι μέση αξία σας εδώ είναι μικρότερη από ό, τι θέλουμε.
Έτσι θέλουμε να λάβει η δεξιά πλευρά του πίνακα μας.
Έτσι θα πάμε να ενημερώσετε κάτω φράγμα μας.
Έτσι θα επανεκχώρηση κάτω μας.
Και τι νομίζετε ότι πρέπει να είναι μικρότερη;
ΜΑΘΗΤΗ: Η μέση τιμή;
Διδάσκων: Έτσι, η μέση value--
Φοιτητής: Συν 1.
Διδάσκων: --plus 1.
Μπορεί κάποιος να μου πει γιατί έχουμε ότι συν 1;
>> Φοιτητής: [? Δεν υπάρχει τιμή;] είναι πιο ίσο με αυτό.
>> Διδάσκων: Δεξιά.
Επειδή γνωρίζουμε ήδη ότι Μέση τιμή μας δεν είναι ίση με
αυτό και θέλουμε να την αποκλείσει από όλες τις μεταγενέστερες αναζητήσεις.
Εάν ξεχάσετε ότι συν 1, αυτό θα ήθελα βρόχο επ 'αόριστον.
Και θα πρέπει ακριβώς να αλιεύονται σε μια άπειρο βρόχο και στη συνέχεια θα segfault
και τα πράγματα πάνε άσχημα.
Έτσι, πάντα να βεβαιωθείτε ότι δεν είστε συμπεριλαμβανομένης της αξίας που μόλις
κοίταξε.
Έτσι φροντίζουμε ώστε με ένα συν 1.
>> Έτσι τώρα έχουμε την τελευταία μας κατάσταση που πάντα μου για λόγους ασφαλείας
μπορείτε να δείτε εδώ, αλλιώς εάν η αξία σε η μεσαία είναι μεγαλύτερη από την αξία
θέλουμε.
Αυτό σημαίνει ότι θέλουμε το αριστερό μισό χέρι.
Έτσι που το ένα θα πάμε να ενημερώσετε;
Άνω.
Και αυτό είναι ένα από αυτό θα ισούται;
Μέση μείον 1, διότι, Φυσικά, θέλουμε
για να βεβαιωθείτε ότι δεν είμαστε κοιτάζοντας και πάλι σε αυτή τη μεσαία τιμή.
Και τότε την έχουμε.
Έτσι μπράβο.
Αυτό είναι το μόνο δυαδική αναζήτηση είναι.
Δεν είναι τόσο κακό, σωστά;
Είναι σαν 10 γραμμές κώδικα με άσπρο διάστημα.
Έτσι, πολύ ισχυρή, πολύ χρήσιμο, θα σας να το χρησιμοποιεί σε μια από τις μετέπειτα psets σας.
Ίσως δεν είναι αυτό, αλλά αργότερα.
Έτσι μαθαίνουν.
Love it.
Θα σας φέρονται καλά.
Έτσι κάνει κάποιος που έχει κάποια ερωτήσεις σχετικά με δυαδική αναζήτηση;
Ναι.
>> Φοιτητής: Πειράζει αν n σας είναι άρτιο ή περιττό;
>> Διδάσκων: Όχι.
Επειδή το ρίχνει στη μέση, όπως ένας int, θα περικόψει μόνο.
Έτσι θα μείνει έναν ακέραιο και θα τελικά να ταξινομήσετε μέσω όλων.
Έτσι, δεν έχετε να ανησυχείτε για αυτό.
Όλοι καλό;
Awesome.
Cool.
Έτσι, εσείς πήρε αυτό.
Προβολή διαφανειών.
Έτσι όπως μιλούσαμε για, ξέρω David αναφέρθηκε runtimes πολυπλοκότητα.
>> Έτσι, στην καλύτερη περίπτωση, είναι ακριβώς ένα, το οποίο ονομάζουμε σταθερό χρόνο.
Μπορεί κάποιος να μου πει γιατί αυτό θα μπορούσε να είναι;
Τι είδους σενάριο θα ήταν αυτό συνεπάγεται;
MM-HM.
>> Φοιτητής: [δεν ακούγεται] first--
Διδάσκων: Έτσι, η μέση είναι η το πρώτο στοιχείο που θα έρθει να, έτσι δεν είναι;
Έτσι, είτε μια σειρά ενός ή ό, τι ψάχνουμε μόνο
συμβαίνει να είναι σκαμπίλι χωματίδα στη μέση.
Έτσι, αυτό είναι το καλύτερο περίπτωσή μας.
Μπορείτε να πάρετε σε πραγματικά προβλήματα, πιθανόν να μην πρόκειται να φτάσουν [δεν ακούγεται] ότι συχνά.
Τι γίνεται χειρότερη περίπτωση μας;
Χειρότερη περίπτωση μας είναι log n.
Και αυτό έχει να κάνει με το σύνολο αρμοδιότητες των δύο πράγμα που μίλησα.
>> Έτσι, στη χειρότερη περίπτωση, αυτό θα σήμαινε ότι θα έπρεπε να κόψουν τον πίνακα κάτω
έως ότου ήταν ένα στοιχείο του ενός.
Έτσι θα έπρεπε να το τεμαχίσει κάτω στο μισό όπως πολλές φορές έχουμε ενδεχομένως θα μπορούσε.
Γι 'αυτό είναι log n, επειδή μπορείτε απλά να κρατήσει τη διαίρεση δια δύο.
Έτσι υποθέσεις, πράγματα που Πρέπει να γνωρίζει αν είστε ποτέ
πρόκειται να χρησιμοποιήσετε μια δυαδική αναζήτηση.
Τα στοιχεία σας θα πρέπει να ταξινομηθούν.
Θα πρέπει να διευθετηθεί επειδή αυτός είναι ο μόνος τρόπος που
μπορεί να ξέρει εάν είστε σε θέση να ρίξει έξω το μισό από αυτό.
>> Αν είχε αυτή την μπερδεμένες τσάντα των αριθμών και λέτε,
Εντάξει, Πάω να ελέγξτε το μεσαίο καθώς και ο αριθμός Ψάχνω για
είναι μικρότερη από εκείνη, είμαι απλώς πρόκειται σε αυθαίρετα ρίξει έξω κατά το ήμισυ.
Δεν θα ξέρετε αν σας οι αριθμοί σε αυτό το άλλο μισό.
Η λίστα σας θα πρέπει να διευθετηθεί.
Όπως επίσης, αυτό μπορεί να είναι προχωρά λίγο,
αλλά θα πρέπει να έχουν τυχαία πρόσβαση.
Θα πρέπει να είναι σε θέση να απλά πηγαίνετε σε αυτό το μεσαίο στοιχείο.
Αν έχετε να διασχίσει μέσα από κάτι
ή σας παίρνει επιπλέον μέτρα για να φτάσουμε σε αυτό το μεσαίο στοιχείο,
Δεν είναι log n πια γιατί μπορείτε να προσθέσετε περισσότερη δουλειά σε αυτό.
Και αυτό θα κάνει μια μικρή περισσότερο νόημα σε δύο εβδομάδες,
αλλά εγώ ακριβώς το είδος της ήθελε να προλογίσει, σας παιδιά δίνουν μια ιδέα του τι είναι
να έρθει.
Αλλά αυτά είναι τα δύο σημαντικές υποθέσεις
ότι χρειάζεστε για ένα δυαδικό λίστα.
Βεβαιωθείτε ότι είναι ταξινομημένο.
Αυτό είναι το μεγάλο για εσείς τώρα.
Και για να μπορέσουμε να προχωρήσουμε σε το υπόλοιπο του είδους μας.
Έτσι, τέσσερις sorts-- φούσκα, εισαγωγή, επιλογή, και συγχώνευση.
Είναι όλοι το είδος της δροσερό.
Αν εσείς αποφασίσετε να πάρετε CS 124, θα μάθετε για όλα τα είδη των ειδών.
Και αν είστε ένας ανεμιστήρας XKCD, υπάρχει είναι ένα πραγματικά δροσερό κόμικ περίπου
όπως πραγματικά αναποτελεσματική είδη, τα οποία θα συνιστούμε να πρόκειται να δούμε.
Ένας από αυτούς είναι σαν πανικού είδος, το οποίο Είναι σαν, OH όχι, επιστρέφουν τυχαία σειρά.
Διακοπή λειτουργίας του συστήματος.
Αφήστε το.
Έτσι geeky χιούμορ είναι πάντα καλό.
>> Έτσι κάνει κάποιος που θυμάται είδος του όπως ακριβώς μια γενική ιδέα
του πώς λειτουργεί bubble sort.
Θυμάστε;
>> Φοιτητής: Ναι.
>> Διδάσκων: Πηγαίνετε για αυτό.
>> Φοιτητής: Έτσι θα πάμε μέσα και αν αυτή είναι μεγαλύτερη, τότε θα ανταλλάξουν τα δύο.
>> Διδάσκων: MM-HM.
Ακριβώς.
Έτσι απλά διέτρεξε.
Μπορείτε να ελέγξετε δύο αριθμούς.
Αν η μία πριν είναι μεγαλύτερο από τη μία μετά,
μπορείτε απλά να τους ανταλλάξουν έτσι ώστε σε Με τον τρόπο αυτό το σύνολο των υψηλότερων αριθμών
φούσκα επάνω προς το τέλος της λίστας και όλα τα χαμηλότερα νούμερα φούσκα κάτω.
>> Μήπως σας δείξω παιδιά το δροσερό εφέ ήχου διαλογής βίντεο;
Είναι το είδος της δροσερό.
Έτσι, όπως δήλωσε ο Robert ακριβώς, τον αλγόριθμο ότι μόλις βήμα από τη λίστα,
εναλλαγή των γειτονικών τιμών αν δεν είναι σε τάξη.
Και τότε απλά να το επαναλαμβάνω, μέχρι να μην κάνουν καμία swaps.
Έτσι, δεν είναι κακό, σωστά;
Έτσι, έχουμε μόνο ένα γρήγορο παράδειγμα εδώ.
Έτσι, αυτό πρόκειται να ταξινομήσετε τους σε αύξουσα σειρά.
Έτσι, όταν περνάμε από την πρώτη ώρα, κοιτάμε μέσα από οκτώ
και έξι είναι προφανώς δεν προκειμένου, εμείς τους swap.
>> Έτσι κοιτάξουμε το επόμενο.
Οκτώ και τέσσερα όχι σε σειρά.
Ανταλλάξτε τους.
Και στη συνέχεια, οκτώ και δύο, τους swap.
Εκεί πάμε.
Έτσι, μετά το πρώτο πέρασμα σας, γνωρίζουν ότι μεγαλύτερο αριθμό σας
πρόκειται να είναι σε όλη τη διαδρομή στην κορυφή επειδή είναι ακριβώς
πρόκειται να είναι συνεχώς μεγαλύτερο από οτιδήποτε άλλο
και αυτό ακριβώς πρόκειται να φούσκα μέχρι όλη τη διαδρομή μέχρι το τέλος εκεί.
Μήπως αυτό έχει νόημα για όλους;
Cool.
>> Μέχρι τότε κοιτάμε το δεύτερο πέρασμα μας.
Έξι και τέσσερις, διακόπτη.
Έξι και δύο, διακόπτη.
Και τώρα έχουμε μερικά πράγματα σε τάξη.
Έτσι, για κάθε πέρασμα που εμείς κάνουν μέσω ολόκληρη τη λίστα μας,
γνωρίζουμε ότι, όπως ότι πολλοί αριθμοί στο τέλος θα έχουν ταξινομηθεί.
Έτσι, κάνουμε ένα τρίτο πέρασμα, το οποίο είναι ένα swap.
Και στη συνέχεια στο τέταρτο μας περάσει, έχουμε μηδενική υποδοχές.
Και έτσι ξέρουμε ότι μας σειρά έχει ταξινομηθεί.
>> Και αυτό είναι το μεγάλο πράγμα με το bubble sort.
Γνωρίζουμε ότι όταν εμείς έχουν μηδενική swaps, ότι
σημαίνει ότι τα πάντα είναι, σε πλήρη τάξη.
Είναι το είδος του πώς θα ελέγξετε.
Έτσι, είμαστε επίσης πρόκειται να κωδικοποιήσει φούσκα είδος το οποίο, επίσης, δεν είναι τόσο άσχημα.
Κανένα από αυτά δεν είναι τόσο άσχημα.
Ξέρω ότι μπορεί να φαίνεται λίγο τρομακτικό.
Ξέρω ότι όταν πήρα η τάξη, ακόμα και όταν
δίδασκε στην τάξη για η πρώτη φορά πέρυσι,
Ήμουν σαν, πώς μπορώ να το κάνω αυτό;
Είναι λογικό στη θεωρία, αλλά πώς το κάνουμε πραγματικότητα αυτό;
Γι 'αυτό θέλω επίσης να περπατήσετε μέσω κώδικα με σας παιδιά εδώ.
Έτσι έχω μια ψευδοκώδικα για σας παιδιά αυτή τη φορά.
Έτσι ακριβώς αυτό στο νου, όπως είμαστε έτοιμοι για τη μετάβαση πάνω.
Έτσι έχουμε κάποιο μετρητή που παρακολουθεί τις ανταλλαγές μας,
γιατί πρέπει να βεβαιωθείτε ότι είμαστε έλεγχο αυτό.
Και έχουμε επαναλάβει ολόκληρη τη συστοιχία όπως ακριβώς έκανε με αυτό το παράδειγμα.
Εάν το στοιχείο πριν είναι μεγαλύτερο από το στοιχείο μετά όπου είμαστε σε,
εμείς τους ανταλλάξουν και θα αυξήσετε μας μετρητή επειδή το συντομότερο ανταλλάξουν,
θέλουμε να αφήσουμε πάγκο μας γνωρίζουμε ότι.
Υπάρχουν ερωτήσεις;
Κάτι φαίνεται αστείο εδώ.
Φοιτητής: Έχετε ρυθμίσετε το μετρητή στο μηδέν κάθε φορά που θα περάσει μέσα από το βρόχο;
Μην κρατάτε πρόκειται πίσω στο μηδέν κάθε φορά;
Διδάσκων: Όχι απαραίτητα.
Έτσι, αυτό που συμβαίνει είναι περνάμε εδώ.
Έτσι κάνει, ενώ, θυμηθείτε, αυτό θα εκτελέσει μία φορά χωρίς να αποτύχει.
Έτσι, πρόκειται να οριστεί η μετρητή ίση με μηδέν,
τότε πρόκειται για διαδοχικές προσεγγίσεις μέσα.
Όπως Επαναλαμβάνει, θα ενημερώσει μετρητή.
Όπως ενημερώνει πάγκο, όταν το κάνει, όταν έχει φτάσει στο τέλος του πίνακα,
εάν η λίστα μας δεν έχει ταξινομηθεί, μετρητής θα έχουν ενημερωθεί.
>> Άρα, λοιπόν, ελέγχει την κατάσταση και λέει, εντάξει, είναι σε αντίθεση μεγαλύτερη από το μηδέν.
Αν είναι, να το κάνει ξανά.
Θέλετε να επαναφέρετε έτσι ώστε όταν περνούν, μετρητής είναι ίση με το μηδέν.
Αν πάτε μέσω ταξινομημένο συστοιχία, τίποτα δεν αλλάζει,
αυτό αποτύχει, και σας επιστρέφει την ταξινομημένη λίστα.
Μήπως αυτό έχει νόημα;
Φοιτητής: Θα μπορούσε σε λίγο.
Διδάσκων: Εντάξει.
Αν υπάρχει οποιαδήποτε άλλη ερώτημα που έρχεται.
Ναι.
>> Φοιτητής: Τι θα η λειτουργία είναι για την εναλλαγή των στοιχείων;
>> Διδάσκων: Έτσι μπορούμε πραγματικά να γράψω ότι αν θα πάμε προς τα δεξιά τώρα.
Cool.
Έτσι, σε αυτό το σημείωμα, η Alison πρόκειται για να αλλάξετε και πάλι πίσω στη συσκευή.
Είναι πρόκειται να είναι διασκέδαση.
Και έχουμε ωραία μας bubble sort πράγμα εδώ.
Γι 'αυτό και ήδη έκανε ποδήλατο μέσω της συστοιχίας.
Έχουμε swaps μας ότι είναι ίσες με το μηδέν.
Έτσι θέλουμε να ανταλλάξουν παρακείμενες στοιχεία αν είναι εκτός λειτουργίας.
Έτσι, το πρώτο πράγμα που πρέπει να δεν είναι διέτρεξε τη σειρά μας.
>> Λοιπόν, πώς νομίζετε ότι θα μπορούσαμε διέτρεξε τη σειρά μας;
Έχουμε και για i ισούται με 0.
Θέλουμε i να είναι λιγότερο από n μείον 1 μείον k.
Και θα εξηγήσω ότι σε ένα δευτερόλεπτο.
Έτσι, αυτό είναι μια βελτιστοποίηση εδώ όπου, θυμάμαι πώς είπα μετά από κάθε πέρασμα
μέσω του πίνακα που γνωρίζουν ότι όποια και αν είναι on--
>> Έτσι, μετά από ένα πέρασμα μας γνωρίζουν ότι αυτό είναι ταξινομημένο.
Μετά από δύο περάσματα γνωρίζουμε ότι όλα αυτά είναι ταξινομημένο.
Μετά από τρία περάσματα εμείς γνωρίζουμε ότι είναι ταξινομημένο.
Έτσι, με τον τρόπο είμαι επανάληψη μέσω της συστοιχίας εδώ,
είναι ότι είναι φροντίζοντας μόνο για να πάει μέσα από αυτό που ξέρουμε είναι αδιαχώριστα.
Εντάξει;
Αυτό είναι απλά μια βελτιστοποίηση.
Θα μπορούσατε να γράψετε αφελώς μόνο επανάληψη μέσα από τα πάντα,
θα χρειαστούμε περισσότερο χρόνο.
Με αυτή την τέσσερα βρόχου είναι απλά ένα ωραίο βελτιστοποίηση
γιατί γνωρίζουμε ότι μετά από κάθε πλήρη επανάληψη μέσω της συστοιχίας εδώ,
όπως κάθε πλήρη βρόχο εδώ, γνωρίζουμε ότι ένα ή περισσότερα από αυτά τα στοιχεία
θα ταξινομηθούν στο τέλος.
>> Έτσι δεν χρειάζεται να ανησυχείτε για εκείνους.
Μήπως αυτό έχει νόημα για όλους;
Αυτό το δροσερό μικρό κόλπο;
Έτσι, στην περίπτωση αυτή, αν είμαστε επανάληψη μέσα,
ξέρουμε ότι θέλουμε να ελέγξουμε αν συστοιχία n και n + 1 είναι σε τάξη.
ΟΚ.
Έτσι, εδώ είναι ο ψευδοκώδικας.
Θέλουμε να ελέγξετε αν συστοιχία n και n + 1 είναι σε τάξη.
Λοιπόν, τι θα μπορούσε να έχουμε εκεί;
Είναι πρόκειται να είναι κάποια αίρεση.
Θα είναι μια περίπτωση.
>> Φοιτητής: Αν συστοιχία n είναι λιγότερο από συστοιχία n + 1.
Διδάσκων: MM-HM.
Λοιπόν, μικρότερη ή μεγαλύτερη από ό, τι.
Φοιτητής: Μεγαλύτερη από ό, τι.
Στη συνέχεια θέλουμε να τους swap.
Ακριβώς.
Έτσι τώρα έχουμε μπει ποια είναι η μηχανισμό για την εναλλαγή τους;
Έτσι περάσαμε από αυτό για λίγο, ένα είδος λειτουργία εναλλαγής περασμένη εβδομάδα.
Θυμάται κανείς πώς λειτούργησε;
Έτσι, δεν μπορούμε απλά να τους εκχωρήσετε εκ νέου, σωστά;
Επειδή ένας από αυτούς θα χαθείτε.
Αν είπαμε Α είναι ίσο προς B και, στη συνέχεια, Β είναι ίσο με Α, όλα μια ξαφνική και τα δύο
είναι ακριβώς ίσο με το Β
>> Έτσι, αυτό που έχουμε να κάνουμε είναι να έχουν μια προσωρινή μεταβλητή που είναι
πρόκειται να κρατήσει ένα από τα δικά μας, ενώ είμαστε στη διαδικασία της swapping.
Έτσι, αυτό που έχουμε είναι ότι θα έχουμε κάποια int θερμοκρασία είναι ίση to-- μπορείτε να ορίσετε
σε όποιο από τα δύο θέλετε, απλά βεβαιωθείτε ότι μπορείτε να παρακολουθείτε it--
οπότε σε αυτή την περίπτωση, Πάω να την αναθέτει σε σειρά n + 1.
Έτσι, αυτό πρόκειται να κρατήσει οτιδήποτε αξία είναι σε αυτή τη δεύτερη κατηγορία
ότι ψάχνουμε σε.
>> Και τότε μπορούμε να κάνουμε είναι να μπορούμε να πάμε μπροστά και επανεκχώρηση σειρά n + 1,
γιατί εμείς ξέρουμε έχουν τιμή που είναι αποθηκευμένη.
Αυτό είναι επίσης ένα από τα μεγάλα things-- Δεν ξέρω αν κάποιος από εσάς
είχε προβλήματα όπου και αν αλλάξετε δύο γραμμές του κώδικα ξαφνικά τα πράγματα εργάστηκε.
Παραγγελία είναι πολύ σημαντικό στο CS.
Έτσι, βεβαιωθείτε ότι έχετε το διάγραμμα τα πράγματα, αν είναι δυνατόν
ως προς το τι πραγματικά συμβαίνει.
Έτσι τώρα θα πάμε να επανεκχώρηση σειρά n + 1,
γιατί εμείς ξέρουμε έχουν τιμή που είναι αποθηκευμένη.
>> Και μπορούμε να εκχωρήσετε ότι σε συστοιχία Ν ή στην περίπτωση αυτή συστοιχία i.
Πάρα πολλές μεταβλητές.
ΟΚ.
Έτσι τώρα έχουμε εκ νέου σειρά i συν 1 να ισούται με ό, τι είναι στην σειρά i.
Και τώρα μπορούμε να πάμε πίσω και εκχωρήσετε σειρά i για τι;
Όποιος;
>> Φοιτητής: 10.
>> Διδάσκων: 10.
Ακριβώς.
Και ένα τελευταίο πράγμα.
Αν έχουμε άλλαζε τώρα, τι πρέπει να κάνουμε;
Ποιο είναι το ένα πράγμα ότι πρόκειται να μας πείτε
αν τερματίσει ποτέ αυτό το πρόγραμμα;
Τι μας λέει ότι εμείς έχουν μια ταξινομημένη λίστα;
Αν δεν εκτελέσετε καμία swaps, σωστά;
Αν swaps είναι ίση με μηδέν στο τέλος του αυτό.
Έτσι, κάθε φορά που κάνετε μια συμφωνία ανταλλαγής, όπως εμείς έκανε ακριβώς εδώ, θέλουμε να ενημερώσετε swaps.
Και ξέρω ότι υπήρχε μια ερώτηση νωρίτερα μπορεί να σας για
χρησιμοποιήστε μηδέν ή ένα αντί του αληθείς ή ψευδείς.
Και αυτό είναι που κάνει αυτό εδώ.
Έτσι, αυτό λέει ότι αν δεν swaps.
Έτσι, αν οι ανταλλαγές είναι μηδέν, η οποία is-- πάντα να πάρει τις αλήθειες μου και falses μου μπερδεύονται.
Θέλουμε να αξιολογήσουμε στην αλήθεια και δεν είναι.
Έτσι, αν είναι μηδέν, τότε είναι ψευδής.
Αν το αναιρεί με ένα [? Έκρηξη;] γίνεται αλήθεια.
Μέχρι τότε αυτή η γραμμή εκτελεί.
>> Αλήθειες και ψευδείς και μηδενικά και αυτοί να τρελαθώ.
Απλά, αν σιγά-σιγά τα πόδια μέσα από αυτό θα κάνει αίσθηση.
Αλλά αυτό είναι λίγο αυτό κομμάτι του κώδικα εδώ κάνει.
Έτσι, αυτό ελέγχει για να δει έχουμε κάνει οποιεσδήποτε ανταλλαγές.
Έτσι, αν είναι οτιδήποτε εκτός από μηδέν, αυτό πρόκειται να είναι ψευδή
και το όλο πράγμα είναι πρόκειται να εκτελέσει ξανά.
Cool;
>> Φοιτητής: Τι κάνει διάλειμμα κάνουμε;
>> Διδάσκων: Διάλειμμα μόνο που ξεσπά από το βρόχο.
Έτσι, στην περίπτωση αυτή, θα απλά ήθελε να τερματίσει το πρόγραμμα
και θα κάνατε ακριβώς έχουν ταξινομηθεί λίστα σας.
Φοιτητής: Amazing.
Διδάσκων: Λυπάμαι;
Φοιτητής: Επειδή στο παρελθόν έχουμε η έγγραφη 1 πάνω από γραπτή μηδέν
για να παρουσιάσει ότι αν ότι θα λειτουργήσει ή όχι.
>> Διδάσκων: Ναι.
Έτσι, μπορείτε να επιστρέψετε το μηδέν ή 1.
Σε αυτήν την περίπτωση, επειδή δεν είμαστε στην πραγματικότητα να κάνει τίποτα με τη λειτουργία,
θέλουμε απλώς να σπάσει.
Εμείς δεν ενδιαφέρονται πραγματικά γι 'αυτό.
Φρένων είναι επίσης καλό, αν αυτό είναι που χρησιμοποιείται για το σπάσιμο έξω
από τέσσερις βρόχους ή καταστάσεις που δεν θέλετε να κρατήσετε εκτέλεσης.
Θα σας μεταφέρει ακριβώς έξω από αυτούς.
Είναι ένα κομμάτι από ένα πράγμα απόχρωση.
Νιώθω σαν να υπάρχει πολλή χέρι κυματισμό,
όπως θα μάθετε για αυτό σύντομα.
>> Αλλά θα μάθετε για αυτό σύντομα.
Υπόσχομαι.
ΟΚ.
Έτσι κάνει ο καθένας να πάρει bubble sort;
Δεν είναι πάρα πολύ κακό.
Διέτρεξε, ανταλλαγής πράγματα χρησιμοποιώντας ένα μεταβλητή temp, και είμαστε έτοιμοι εκεί;
Cool.
Awesome.
ΟΚ.
Επιστροφή στο PowerPoint.
Οποιεσδήποτε ερωτήσεις γενικά σχετικά με αυτά μέχρι στιγμής;
Cool.
MM-HM.
>> Φοιτητής: [δεν ακούγεται] int main συνήθως.
Έχετε να έχει αυτό για αυτό;
>> Διδάσκων: Έτσι ήμασταν απλώς αναζητούν ακριβώς στην πραγματική αλγόριθμος διαλογής.
Αν είχε μέσα σαν ένα μεγαλύτερο πρόγραμμα,
θα έχετε μια int main κάπου.
Ανάλογα με το πού μπορείτε χρησιμοποιήσετε αυτόν τον αλγόριθμο,
θα καθορίσει τι είναι επιστρέφονται από αυτό.
Αλλά για την περίπτωση μας, είμαστε απολύτως κοιτάζοντας πώς το κάνει αυτό πραγματικότητα
επαναλαμβάνεται σε μια σειρά.
Γι 'αυτό μην ανησυχείτε γι' αυτό.
>> Έτσι μιλούσαμε για καλύτερη περίπτωση και στη χειρότερη περίπτωση σενάρια για δυαδική αναζήτηση.
Γι 'αυτό είναι επίσης σημαντικό να κάνουμε ότι για κάθε ένα από τα είδη μας.
Λοιπόν, τι νομίζεις ότι είναι η χειρότερη περίπτωση εκτέλεσης του bubble sort;
Εσείς θυμάστε;
>> Φοιτητής: Ν μείον 1.
Διδάσκων: Ν μείον 1.
Έτσι, αυτό σημαίνει ότι υπάρχουν n μείον 1 συγκρίσεις.
Έτσι, ένα πράγμα που πρέπει να συνειδητοποιήσουμε είναι ότι για την πρώτη επανάληψη,
περνάμε, συγκρίνουμε αυτά two-- έτσι ώστε να είναι 1.
Αυτά τα δύο, τρία, τέσσερα.
Έτσι, μετά από μία επανάληψη μας ήδη έχουν τέσσερις συγκρίσεις.
Όταν μιλώ για το χρόνο εκτέλεσης και Ν.
Ν αντιπροσωπεύει τον αριθμό των συγκρίσεων ως συνάρτηση του πόσα στοιχεία
έχουμε.
Εντάξει;
>> Έτσι περνάμε, έχουμε τέσσερα.
Την επόμενη φορά που θα ξέρουμε ότι δεν κάνουμε πρέπει να φροντίσει γι 'αυτό.
Θα συγκρίνουμε αυτά τα δύο, αυτά τα δύο, αυτά τα δύο,
και αν δεν είχαμε αυτή την βελτιστοποίηση με τέσσερις βρόχο που έγραψα,
θα πρέπει να συγκρίνει εδώ ούτως ή άλλως.
Έτσι, θα πρέπει να τρέχει μέσα από τη συστοιχία
και να κάνουν συγκρίσεις n n φορές, επειδή κάθε φορά που
τρέχει μέσα από αυτό να ξεκαθαρίσουμε ένα πράγμα.
>> Και κάθε φορά που τρέχει μέσα η σειρά, κάνουμε n συγκρίσεις.
Έτσι εκτέλεσης μας για αυτό είναι στην πραγματικότητα n τετράγωνο, το οποίο
είναι πολύ χειρότερη σε μας συνδεθείτε τέλος γιατί αυτό
σημαίνει ότι αν είχαμε τέσσερις δισεκατομμύρια στοιχεία, είναι
πρόκειται να μας πάρει τέσσερα δισεκατομμύρια τετράγωνο αντί για 32.
Έτσι, δεν είναι η καλύτερη χρόνου εκτέλεσης, αλλά για κάποια πράγματα,
Ξέρετε, αν είστε μέσα ένα συγκεκριμένο εύρος των στοιχείων
bubble sort μπορεί να είναι μια χαρά για να χρησιμοποιήσει.
>> ΟΚ.
Και τώρα τι είναι το καλύτερο χρόνο εκτέλεσης υπόθεση;
ΜΑΘΗΤΗ: Μηδέν;
Ή 1;
>> Διδάσκων: Μέχρι 1 θα είναι μία σύγκριση.
Δεξιά.
>> Φοιτητής: Ν μείον 1;
>> Διδάσκων: Λοιπόν, ναι.
Έτσι n μείον 1.
Κάθε φορά που έχετε μια ιδέα, όπως n μείον 1, έχουμε την τάση να το ρίξετε λίγο έξω
και απλά λέμε n επειδή έχετε να συγκρίνετε καθένα από these-- κάθε ζεύγος.
Έτσι, θα ήταν ν μείον 1, το οποίο εμείς θα ήθελα απλώς να πω είναι περίπου n.
Όταν έχεις να κάνεις με το χρόνο εκτέλεσης, τα πάντα είναι σε προσεγγίζει.
Εφ 'όσον ο εκθέτης είναι σωστό, είστε αρκετά καλός.
>> Αυτό είναι το πώς θα ασχοληθεί με το θέμα.
Έτσι, ότι η καλύτερη περίπτωση είναι n, η οποία σημαίνει ότι η λίστα έχει ήδη ταξινομηθεί,
και το μόνο που κάνουμε είναι να τρέχει μέσα και βεβαιωθείτε ότι είναι ταξινομημένο.
Cool.
Εντάξει.
Έτσι, όπως μπορείτε να δείτε εδώ, εμείς απλά έχουν κάποια πιο γραφικές παραστάσεις.
Έτσι n στο τετράγωνο.
Διασκέδαση.
Πολύ χειρότερη από ό, τι n όπως βλέπουμε, και πολύ, πολύ χειρότερα από ό, τι καταγραφής 2n.
Και στη συνέχεια, μπορείτε επίσης να πάρετε σε κορμούς log.
Και παίρνετε 124, μπορείτε να πάρετε σε σαν αστέρι ημερολόγιο, το οποίο είναι σαν τρελός.
Έτσι, αν σας ενδιαφέρει, αναζήτηση καταγραφής αστέρων.
Είναι το είδος της διασκέδασης.
Έτσι έχουμε αυτό το μεγάλο διάγραμμα.
Ακριβώς τα κεφάλια επάνω, αυτή η υπέροχο διάγραμμα για να έχουν
για την ενδιάμεση σας, γιατί εμείς καιρό να σας ρωτήσω αυτά λεπταίνει.
Έτσι, μόλις heads-up, έχουν αυτό στο σας ενδιάμεση σε ωραίο σκονάκι σας
εκεί.
Έτσι, εμείς απλά κοίταξε bubble sort.
Χειρότερη περίπτωση, n στο τετράγωνο, καλύτερη περίπτωση, n.
Και θα πάμε να δούμε τους άλλους.
>> Και όπως μπορείτε να δείτε, το μόνο αυτό που πραγματικά κάνει καλά
είναι η συγχώνευση του είδους, το οποίο θα μπει γιατί.
Έτσι θα πάμε για να πάει να το επόμενο here-- είδος επιλογής.
Θυμάται κανείς πώς επιλογή είδους εργαστεί;
Πηγαίνετε για αυτό.
>> Φοιτητής: Βασικά περνούν μια τάξη και να δημιουργήσετε μια νέα λίστα.
Και ακριβώς όπως είστε βάζοντας στοιχεία σε, τους βάλει στη σωστή θέση
στη νέα λίστα.
>> Διδάσκων: Έτσι ώστε ήχοι περισσότερο σαν είδος εισαγωγής.
Αλλά είσαι πολύ κοντά.
Είναι πολύ παρόμοια.
Ακόμη και εγώ τους πάρει μπερδεύονται μερικές φορές.
Πριν από αυτή την ενότητα ήμουν όπως, περιμένετε.
ΟΚ.
Έτσι, ό, τι θέλετε να κάνουμε είναι είδος επιλογής,
ο τρόπος που μπορείτε να σκεφτείτε γι 'αυτό και τον τρόπο
Κάνω ότι μπορώ να προσπαθήσουμε να μην πάρει τα μπέρδεψαν, είναι ότι περνά από
και επιλέγει το μικρότερο αριθμό και
βάζει ότι στην αρχή της λίστας σας.
Είναι αυτό swaps με αυτό το πρώτο σημείο.
Στην πραγματικότητα έχουμε ένα παράδειγμα για μένα.
Awesome.
Έτσι απλά ένας τρόπος για να σκεφτώ it-- επιλογή Ταξινόμηση, επιλέξτε τη μικρότερη τιμή.
Και θα πάμε να τρέχει μέσα από ένα παράδειγμα
που πιστεύω ότι θα βοηθήσει, διότι Νομίζω visuals πάντα να βοηθήσει.
Ξεκινάμε λοιπόν με κάτι ότι είναι εντελώς άνευ διαλογής.
Κόκκινο θα είναι αδιαχώριστα, πράσινο θα είναι ταξινομημένο.
Θα κάνει όλα νόημα σε μια δεύτερη.
>> Έτσι περνάμε και έχουμε επαναλάβει από την αρχή μέχρι το τέλος.
Και λέμε, εντάξει, είναι 2 μικρότερο αριθμό μας.
Έτσι θα πάμε για να πάρει 2 και θα πάμε να κινηθεί προς τα εμπρός του πίνακα μας
γιατί είναι η μικρότερος αριθμός που έχουμε.
Έτσι, αυτό είναι ό, τι αυτό που κάνει εδώ.
Είναι ακριβώς πρόκειται να ανταλλάξουν αυτά τα δύο.
Έτσι τώρα έχουμε ένα ταξινομημένο μέρος και ένα μέρος χωρίς διαλογή.
Και τι είναι καλό να θυμόμαστε σχετικά με το είδος επιλογής
είναι ότι είμαστε μόνο επιλογή από τη μη ταξινομημένα μέρος.
>> Η ταξινομημένη μέρος που μόλις αφήσει μόνο του.
MM-hm;
>> Φοιτητής: Πώς ξέρουμε τι είναι η μικρότερη χωρίς συγκρίνοντάς
σε κάθε άλλη τιμή στη συστοιχία.
Διδάσκων: Κάνει το συγκρίνουμε.
Μας αρέσει αυτό παραλείπεται.
Αυτό είναι μόνο γενικές συνολικά.
Ναι.
Όταν γράφουμε τον κώδικα είμαι βέβαιος ότι θα είστε περισσότερο ικανοποιημένοι.
Αλλά μπορείτε να αποθηκεύσετε αυτό το πρώτο στοιχείο ως το μικρότερο.
Μπορείτε να συγκρίνετε και να σας πω, εντάξει, είναι μικρότερο;
Ναι.
Κρατήστε αυτό.
Εδώ είναι το μικρότερο;
Όχι;
>> Αυτό είναι το μικρότερο σας, επανεκχώρηση αυτό με την αξία σας.
Και θα είναι πολύ πιο ευτυχισμένοι όταν περνάμε από τον κώδικα.
Έτσι περνάμε, εμείς το swap, έτσι ώστε, στη συνέχεια, εξετάζουμε σε αυτό το τμήμα αδιαχώριστα.
Έτσι θα πάμε να επιλέξετε τρεις έξω.
Εμείς πάμε για να το βάλετε πάνω σε το τέλος του ταξινομημένο τμήμα μας.
Και είμαστε ακριβώς πρόκειται να συνεχίσει να κάνει ότι, το κάνουμε αυτό, και να το κάνουμε αυτό.
Έτσι, αυτό είναι το είδος μας ψευδοκώδικα εδώ.
Θα το κωδικοποιήσει έως εδώ σε ένα δευτερόλεπτο.
Αλλά ακριβώς κάτι για να περπατήσει μέσα σε ένα υψηλό επίπεδο.
Θα πάμε για να πάει από i ισούται με 0 έως n μείον 2.
Αυτό είναι ένα άλλο βελτιστοποίησης.
Μην ανησυχείτε πάρα πολύ για αυτό.
Έτσι, όπως μπορείτε έλεγαν.
Όπως έλεγε ο Ιακώβ, πώς μπορούμε να να παρακολουθείτε ό, τι ελάχιστο μας είναι;
Πώς το ξέρουμε;
Πρέπει να συγκρίνουμε τα πάντα στη λίστα μας.
>> Έτσι ελάχιστο ισούται με i.
Είναι ακριβώς λέει σε αυτή την περίπτωση ο δείκτης της ελάχιστης αξίας μας.
Άρα, λοιπόν, πρόκειται να επαναλάβει μέσω και πηγαίνει από j ισούται με i + 1.
Έτσι, γνωρίζουμε ήδη ότι αυτό είναι το πρώτο μας στοιχείο.
Δεν χρειάζεται να το συγκρίνουμε με το ίδιο.
Ξεκινούμε λοιπόν ότι σε σύγκριση με την επόμενη μία η οποία είναι ο λόγος για αυτό είναι i συν 1 έως n
μείον 1, η οποία είναι η άκρο της συστοιχίας εκεί.
Και είπαμε, αν συστοιχία σε j είναι μικρότερη από συστοιχία min,
τότε εμείς επανεκχώρηση όπου ελάχιστους δείκτες μας είναι.
>> Και αν min δεν είναι ίση με Ι, όπως στο οποίο ήμασταν πίσω εδώ.
Έτσι, όπως όταν κάναμε για πρώτη φορά αυτό το ένα.
Σε αυτήν την περίπτωση, θα ξεκινούν μηδέν, θα καταλήξει να είναι δύο.
Έτσι, δεν θα min ίση i ​​στο τέλος.
Αυτό μας επιτρέπει να γνωρίζουμε ότι εμείς πρέπει να τους swap.
Νιώθω σαν ένα συγκεκριμένο παράδειγμα θα βοηθήσει πολύ περισσότερο από αυτό.
Γι 'αυτό θα κωδικοποιήσει αυτό επάνω με σας παιδιά τώρα και νομίζω ότι θα είναι καλύτερα.
>> Των ειδών τείνουν να λειτουργεί με αυτόν τον τρόπο ότι είναι συχνά καλύτερο απλά για να τους δει.
Έτσι, αυτό που θέλουμε να κάνουμε είναι θέλουμε πρώτα το μικρότερο
στοιχείο στη θέση του στον πίνακα.
Ακριβώς ό, τι έλεγε ο Ιακώβ.
Θα πρέπει να αποθηκεύσετε ότι κατά κάποιο τρόπο.
Έτσι θα πάμε για να ξεκινήσει εδώ επανάληψη επί της συστοιχίας.
Εμείς πάμε για να πω ότι είναι μας πρώτη απλά για να αρχίσει με.
Έτσι θέλουμε να έχουμε int μικρότερο είναι ίσο με το array στο i.
>> Έτσι, ένα πράγμα που πρέπει να παρατηρήσετε, κάθε χρόνο αυτό βρόχο εκτελεί,
αρχίζουμε ένα βήμα πιο πέρα.
Όταν αρχίσουμε να κοιτάμε αυτό.
Την επόμενη φορά που διέτρεξε, ξεκινάμε σε αυτό
και μικρότερη τιμή μας ανάθεση.
Έτσι είναι πολύ παρόμοια με bubble sort όπου γνωρίζουμε ότι μετά από ένα πέρασμα,
Το τελευταίο αυτό στοιχείο είναι ταξινομημένο.
Με το είδος επιλογής, είναι ακριβώς το αντίθετο.
>> Σε κάθε πέρασμα, γνωρίζουμε ότι το πρώτο είναι ταξινομημένο.
Μετά το δεύτερο πέρασμα, η δεύτερη θα είναι ταξινομημένο.
Και όπως είδατε με τα παραδείγματα διαφάνεια, ταξινομημένο τμήμα μας απλά συνεχίζει να αυξάνεται.
Έτσι, θέτοντας μικρότερο από το δικό μας σε συστοιχίες i, όλα είναι να κάνει
περιορίζει το τι ψάχνουμε σε, έτσι ώστε
να ελαχιστοποιηθεί ο αριθμός των συγκρίσεων που κάνουμε.
Μήπως αυτό έχει νόημα για όλους;
Μήπως χρειάζεστε εμένα να τρέχει μέσα από αυτό και πάλι πιο αργή ή σε διαφορετικές λέξεις;
Είμαι στην ευχάριστη θέση να.
ΟΚ.
>> Έτσι είμαστε η αποθήκευση αξία σε αυτό το σημείο,
αλλά θέλουμε επίσης να αποθηκεύσετε το δείκτη.
Έτσι θα πάμε να αποθηκεύσετε το θέση του μικρότερου
ένα, το οποίο είναι ακριβώς πρόκειται να είναι i.
Έτσι τώρα ο Ιακώβ είναι ικανοποιημένοι.
Έχουμε πράγματα που αποθηκεύονται.
Και τώρα πρέπει να κοιτάξουμε μέσα ο υποστεί διαλογή μέρος της συστοιχίας.
Έτσι, στην περίπτωση αυτή, θα είναι αδιαχώριστα μας.
Αυτό είναι i.
ΟΚ.
>> Έτσι, αυτό που πάμε να κάνουμε πρόκειται να είναι για έναν βρόχο.
Όποτε χρειάζεται να επαναλαμβάνεται σε μια σειρά,
το μυαλό σας θα μπορούσε να πάει σε ένα βρόχο.
Έτσι, για κάποιο int k equals-- τι νομίζουμε
k θα ισούται με για να αρχίσει με;
Αυτό είναι αυτό που θέσαμε ως μικρότερο μας αξία και θέλουμε να το συγκρίνουμε.
Τι θέλουμε να το συγκρίνουμε με;
Είναι πρόκειται να είναι αυτό το επόμενο, σωστά;
Έτσι θέλουμε k να προετοιμαστεί Ι συν 1 για να ξεκινήσει.
>> Και θέλουμε k σε αυτή την περίπτωση ήδη έχουν μέγεθος αποθηκεύονται εδώ,
Οπότε μπορούμε απλά να χρησιμοποιήσετε το μέγεθος.
Μέγεθος είναι το μέγεθος της συστοιχίας.
Και εμείς απλά θέλουμε να ενημερώσετε k κατά ένα κάθε φορά.
Cool.
Έτσι τώρα πρέπει να βρούμε το μικρότερο στοιχείο εδώ.
Έτσι, αν έχουμε διέτρεξε, εμείς θέλω να πω, αν συστοιχία σε k
είναι μικρότερη από ό, τι μικρότερο value-- μας Αυτό είναι όπου είμαστε πραγματικά
την παρακολούθηση του τι είναι το μικρότερο here--
Στη συνέχεια θέλουμε να επανεκχώρηση τι μικρότερη τιμή μας είναι.
>> Αυτό σημαίνει ότι, OH, είμαστε επανάληψη από εδώ.
Όποια και αν είναι η τιμή εδώ είναι όχι μικρότερο πράγμα μας.
Εμείς δεν το θέλουμε.
Θέλουμε να τις μεταβιβάσει εκ νέου.
Έτσι, αν είμαστε αυτή η ανακατανομή, τι κάνουμε νομίζετε ότι θα μπορούσε να είναι σε αυτόν τον κώδικα εδώ;
Θέλουμε να επανεκχώρηση μικρότερο και θέση.
Έτσι, αυτό είναι το μικρότερο τώρα;
Φοιτητής: Array k.
Διδάσκων: Array k.
Και ποια είναι η θέση τώρα;
Τι είναι οι δείκτες μικρότερη τιμή μας;
Είναι ακριβώς k.
Έτσι, σειρά K, K, τους ταιριάζει.
Έτσι θελήσαμε να εκχωρήσετε εκ νέου ότι.
Και στη συνέχεια, αφού βρήκαμε μικρότερο μας, έτσι ώστε στο τέλος αυτού του βρόχου για
εδώ έχουμε βρει τι μικρότερο μας αξίας είναι, γι 'αυτό ακριβώς το swap.
Σε αυτή την περίπτωση, όπως λένε μας μικρότερη τιμή είναι εδώ.
Αυτή είναι η μικρότερη τιμή μας.
>> Εμείς απλά θέλουμε να ανταλλάξουν εδώ, το οποίο είναι τι η λειτουργία εναλλαγής στο κάτω μέρος
έκανε, το οποίο μόλις έγραψε μαζί πριν από ένα-δυο λεπτά.
Γι 'αυτό πρέπει να εξετάσουμε εξοικειωμένοι.
Και τότε θα επαναλάβει μόνο μέσα μέχρι να φτάσει σε όλη τη διαδρομή
στο τέλος, πράγμα που σημαίνει ότι θα έχουν μηδενική στοιχεία που δεν έχουν υποστεί διαλογή
και ό, τι άλλο έχει ταξινομηθεί.
Νόημα;
Λίγο πιο συγκεκριμένα;
Η βοήθεια κώδικα;
>> Φοιτητής: Για ένα μέγεθος, που ποτέ δεν πραγματικά να καθορίσει ή να το αλλάξετε,
πώς το ξέρετε;
>> Διδάσκων: Έτσι, ένα πράγμα που πρέπει να παρατηρήσετε εδώ είναι το μέγεθος int.
Έτσι λέμε σε αυτό το είδος sort-- είναι μια λειτουργία σε αυτό case-- είναι
είδος επιλογής, έχει περάσει σε με τη λειτουργία.
Έτσι, αν δεν είχε περάσει στο, θα κάνουμε κάτι
όπως και με το μήκος της συστοιχίας ή θα διέτρεξε
για να βρείτε το μήκος.
Αλλά επειδή έχει περάσει σε, μπορούμε να το χρησιμοποιήσουμε μόνο.
Μπορείτε απλά να υποθέσουμε ότι ο χρήστης Σας έδωσε ένα έγκυρο μέγεθος που
στην πραγματικότητα αντιπροσωπεύει ένα μέγεθος του πίνακα σας.
Cool;
>> Αν εσείς έχετε οποιοδήποτε πρόβλημα με αυτά ή θέλετε περισσότερες πρακτικές κωδικοποίησης είδη
για τη δική σας, θα πρέπει πηγαίνετε στο study.cs50.
Είναι ένα εργαλείο.
Έχουν Ένας ελεγκτής που μπορείτε πραγματικά να γράψετε.
Κάνουν ψευδοκώδικα.
Έχουν περισσότερα βίντεο και διαφάνειες συμπεριλαμβανομένων εκείνων που χρησιμοποιούν εδώ.
Έτσι, εάν αισθάνεστε ακόμα ένα λίγο ασαφής, δοκιμάστε αυτό έξω.
Όπως πάντα, έρχονται να μου μιλήσει, πάρα πολύ.
Ερώτηση;
>> Φοιτητής: Θέλετε να πείτε το μέγεθος ορίζεται προηγουμένως;
Διδάσκων: Ναι.
Μέγεθος προηγουμένως ορίζεται μέχρι εδώ στη δήλωση της συνάρτησης.
Έτσι θα υποθέσουμε ότι είναι ήδη περάσει στην από τον χρήστη, καθώς και για λόγους απλότητας,
θα πάμε να υποθέσουμε ότι η χρήστης μας έδωσε το σωστό μέγεθος.
Cool.
Έτσι, αυτό είναι το είδος επιλογής.
Παιδιά, ξέρω ότι μαθαίνουμε πολλά σήμερα.
Είναι ένα πυκνό στοιχεία για ενότητα.
Έτσι, με αυτό, πρόκειται να πάει στο είδος εισαγωγής.
>> ΟΚ.
Έτσι, πριν ότι έχουμε να κάνουμε ανάλυση runtime μας εδώ.
Έτσι, στην καλύτερη περίπτωση, χορηγείται από τότε που σας έδειξα
Ο πίνακας που ήδη το είδος του έδωσε μακριά.
Αλλά το καλύτερο runtime περίπτωση, τι νομίζουμε;
Όλα ταξινομημένο.
Ν τετράγωνο.
Όποιος έχει μια εξήγηση για τους οποίους νομίζετε;
>> Φοιτητής: Είσαι σύγκριση through--
Διδάσκων: Δεξιά.
Είσαι συγκρίνοντας μέσα.
Σε κάθε επανάληψη, μολονότι είμαστε Decrementing αυτό με ένα,
είστε ακόμα ψάχνουν μέσα τα πάντα για να βρει το μικρότερο.
Έτσι, ακόμη και αν μικρότερη αξία σας είναι εδώ στην αρχή,
είστε ακόμα σύγκριση εναντίον οτιδήποτε άλλο
για να βεβαιωθείτε ότι είναι το μικρότερο πράγμα.
Έτσι, θα καταλήξετε σε λειτουργία μέσω περίπου n τετράγωνο φορές.
Εντάξει.
Και ποια είναι η χειρότερη περίπτωση;
Επίσης n τετράγωνο επειδή θα πάμε να κάνει την ίδια διαδικασία.
Έτσι, στην περίπτωση αυτή, η επιλογή είδος έχει κάτι
ότι καλούμε και αναμενόμενη αυτονομία.
Έτσι, σε άλλους, εμείς απλά ξέρω τα άνω και κάτω όρια.
Ανάλογα με το πόσο τρελό μας κατάλογος είναι ή πώς είναι αδιαχώριστα,
διαφέρουν μεταξύ Ν ή Ν τετράγωνο.
Δεν ξέρουμε.
>> Αλλά επειδή το είδος επιλογής έχει την ίδια χειρότερη και την καλύτερη περίπτωση, ότι μας λέει ότι
δεν έχει σημασία τι είδος της εισόδου μας έχουν, είτε πρόκειται για εντελώς
διαλογή ή εντελώς αντίστροφη ταξινομημένο, είναι
πρόκειται να λάβει το ίδιο χρονικό διάστημα.
Έτσι, στην περίπτωση αυτή, αν θυμάστε από το τραπέζι μας,
είχε πραγματικά μια αξία που Αυτά τα δύο είδη δεν έχουν,
η οποία είναι αναμενόμενη αυτονομία.
Έτσι, γνωρίζουμε ότι κάθε φορά τρέξουμε είδος επιλογής,
είναι εγγυημένο για να εκτελέσετε μια n τετράγωνο του χρόνου.
Δεν υπάρχει μεταβλητότητα εκεί.
Είναι ακριβώς αναμενόταν.
Και, πάλι, αν θέλετε να μάθετε περισσότερο, να λάβει CS 124 στην Άνοιξη.
Εντάξει.
Έχουμε δει αυτό το ένα.
Cool.
Έτσι, η εισαγωγή του είδους.
Και είμαι κατά πάσα πιθανότητα θα να χαράξει μέσα από αυτό.
Δεν θα έχω εσείς να κωδικοποιήσει.
Θα περπατήσετε μέσα από αυτό.
Έτσι, ταξινόμηση με εισαγωγή είναι είδος παρόμοιων με το είδος επιλογής
από το γεγονός ότι έχουμε τόσο μια μη ταξινομημένα και ταξινομημένο μέρος της συστοιχίας.
>> Αλλά αυτό που είναι διαφορετικό είναι ότι καθώς περνάμε από το ένα προς ένα,
μπορούμε απλά να πάρουν ανεξάρτητα από τον αριθμό Είναι δίπλα σε αδιαχώριστα μας,
και σωστά το τακτοποιήσουμε σε ταξινομημένο πίνακα μας.
Θα κάνει περισσότερο νόημα με ένα παράδειγμα.
Έτσι, ό, τι ξεκινά ως αδιαχώριστα, ακριβώς όπως με το είδος επιλογής.
Και θα πάμε να ξεκαθαρίσουμε το θέμα σε αύξουσα σειρά όπως έχουμε ήδη.
Έτσι, στο πρώτο μας πέρασμα παίρνουμε την πρώτη τιμή
και λέμε, εντάξει, είσαι τώρα σε μια λίστα από τον εαυτό σας.
>> Επειδή είστε σε μια λίστα από τον εαυτό σας, είστε ταξινομημένο.
Συγχαρητήρια για την ύπαρξη η πρώτο στοιχείο σε αυτή τη συστοιχία.
Είστε ήδη διευθετηθεί όλα μόνοι σας.
Έτσι τώρα έχουμε ένα ταξινομημένο και χωρίς διαλογή συστοιχία.
Μέχρι τώρα έχουμε λάβει την πρώτη.
Τι συμβαίνει μεταξύ εδώ και εδώ είναι που λέμε,
Εντάξει, θα πάμε να δούμε το πρώτο αξία των μη ταξινομημένα σειρά μας
και θα πάμε να τον εισάγετε στο της σωστή θέση στην ταξινομημένο πίνακα.
>> Έτσι, αυτό που κάνουμε είναι να παίρνουμε 5 και λέμε, εντάξει, 5 είναι μεγαλύτερη από 3,
γι 'αυτό ακριβώς το τοποθετήσετε σωστά το δικαίωμα αυτό.
Είμαστε καλά.
Μέχρι τότε πάμε στο επόμενο ένα μας.
Και παίρνουμε 2.
Εμείς λέμε, εντάξει, 2 είναι λιγότερο από 3, οπότε ξέρουμε ότι
πρέπει να είναι κατά το μπροστά του καταλόγου μας τώρα.
Έτσι, αυτό που κάνουμε είναι να ωθήσει 3 και 5 προς τα κάτω και κινούμαστε 2 σε εκείνη την πρώτη υποδοχή.
Έτσι είμαστε απλά εισάγοντας η σωστή θέση που πρέπει να είναι.
>> Στη συνέχεια, εξετάζουμε μας επόμενο, και λέμε 6.
Εντάξει, 6 είναι μεγαλύτερη από ό, τι πάντα σε ταξινομημένη σειρά μας,
γι 'αυτό ακριβώς την ετικέτα για να το τέλος.
Και τότε θα δούμε 4.
4 είναι μικρότερο από 6, είναι λιγότερο από 5 αλλά είναι μεγαλύτερη από 3.
Έτσι, εμείς απλά τοποθετήστε το δικαίωμα σε η μέση μεταξύ 3 και 5.
Έτσι, για να κάνουν ότι λίγο λίγο πιο συγκεκριμένα,
εδώ είναι το είδος του ιδέα για το τι συνέβη.
Έτσι, για κάθε αδιαχώριστα στοιχείο, εμείς προσδιοριστεί ο τόπος όπου το ταξινομημένο τμήμα
είναι.
>> Έτσι, έχοντας κατά νου την διαλογή και χωρίς διαλογή,
πρέπει να διασχίσουμε μέσα και εικόνα πού ταιριάζει στον ταξινομημένο πίνακα.
Και εμείς το τοποθετήσετε με τη μετατόπιση του στοιχεία προς τα δεξιά του προς τα κάτω.
Και τότε θα κρατήσει μόνο επανάληψη μέσα μέχρι να
έχουν μια εντελώς ταξινομημένη λίστα όπου αδιαχώριστα είναι τώρα μηδέν
και ταξινομημένα καταλαμβάνει το σύνολό της λίστας μας.
Έτσι, και πάλι, για να κάνει τα πράγματα ακόμα Πιο συγκεκριμένα, έχουμε ψευδοκώδικα.
>> Έτσι, βασικά για το i είναι ίσο με 0 έως n μείον 1,
αυτό είναι ακριβώς το μήκος του πίνακα μας.
Έχουμε κάποιο στοιχείο που είναι ίσο με η πρώτη συστοιχία ή οι πρώτοι δείκτες.
Θέτουμε ι ίση με εκείνη.
Έτσι, ενώ το j είναι μεγαλύτερη από μηδέν και η συστοιχία, j μείον 1
είναι μεγαλύτερο από το στοιχείο, οπότε το μόνο που κάνει
είναι να διασφαλίσουμε ότι ι σας αντιπροσωπεύει πραγματικά
ο υποστεί διαλογή τμήμα της συστοιχίας.
>> Έτσι, ενώ δεν υπάρχει ακόμα πράγματα να ταξινομήσετε και ι μείον ένα is-- τι
είναι το στοιχείο της;
J ποτέ δεν ορίστηκε εδώ.
Είναι το είδος των ενοχλητικό.
ΟΚ.
Anyways.
Έτσι, j μείον 1, έχετε τον έλεγχο το στοιχείο πριν.
Λέτε, εντάξει, είναι το στοιχείο πριν από όπου κι αν am-- ας
πραγματικά συντάξει αυτό έξω.
Ας πούμε ότι αυτό είναι όπως και για το δεύτερο πέρασμα μας.
Έτσι, εγώ πρόκειται να είναι ίση σε 1, η οποία είναι εδώ.
>> Έτσι Ι πρόκειται να είναι ίση προς 1.
Αυτό θα είναι 2, 4, 5, 6, 7.
Εντάξει.
Έτσι, το στοιχείο μας σε αυτή την περίπτωση θα είναι ίση με 4.
Και έχουμε κάποια j που είναι πρόκειται να είναι ίση προς 1.
Ω, j είναι Decrementing.
Αυτό είναι ό, τι είναι.
Έτσι, j είναι ίσο με i, οπότε τι είναι αυτό λέει είναι ότι καθώς προχωρούμε προς τα εμπρός,
είμαστε απλώς να διασφαλίσουμε ότι δεν είμαστε πάνω
ευρετηρίαση με αυτόν τον τρόπο όταν προσπαθούμε να τοποθετήσετε τα πράγματα σε ταξινομημένη λίστα μας.
>> Έτσι, όταν j είναι ίσο με το 1 στην περίπτωση αυτή και συστοιχία ι μείον ένα-- έτσι συστοιχία ι μείον 1
είναι 2 σε αυτή case-- αν αυτό είναι μεγαλύτερο από το στοιχείο,
τότε όλα αυτά που κάνει αλλάζει τα πράγματα προς τα κάτω.
Έτσι, στην περίπτωση αυτή, σειρά j μείον ένα θα είναι συστοιχία μηδέν, η οποία είναι 2.
2 δεν είναι μεγαλύτερο από 4, έτσι αυτό δεν εκτελεί.
Έτσι, η στροφή δεν κινείται προς τα κάτω.
Αυτό που κάνει εδώ είναι ακριβώς κινείται ταξινομημένο πίνακα σας κάτω.
Σε αυτήν την περίπτωση, πράγματι, μπορούμε θα μπορούσε να do-- ας κάνουμε αυτό 3.
Έτσι, αν είμαστε να περπατήσετε μέσα με Αυτό το παράδειγμα, είμαστε τώρα εδώ.
Αυτό είναι ταξινομημένο.
Αυτό είναι αδιαχώριστα.
Cool;
Έτσι, i είναι ίσο με 2, έτσι στοιχείο μας είναι ίση με 3.
Και ι μας είναι ίση με 2.
Έτσι κοιτάξουμε μέσα και εμείς πω, εντάξει, είναι συστοιχία ι μείον ένα
μεγαλύτερο από το στοιχείο ότι ψάχνουμε σε;
Και η απάντηση είναι ναι, σωστά;
4 είναι μεγαλύτερη από 3 και j είναι 2, έτσι ώστε αυτός ο κώδικας εκτελεί.
>> Και τώρα τι κάνουμε μια σειρά σε 2, έτσι ακριβώς εδώ, εμείς τους swap.
Γι 'αυτό και μόνο να πω, εντάξει, συστοιχία σε 2 τώρα πρόκειται να είναι 3.
Και j πρόκειται να ισούται j μείον 1, η οποία είναι 1.
Αυτό είναι τρομερό, αλλά εσείς να πάρετε την ιδέα.
J είναι πλέον ίσο με 1.
Και συστοιχία ι είναι ακριβώς πρόκειται να είναι ίσο με το στοιχείο μας, η οποία ήταν 4.
Έσβησα κάτι που δεν θα πρέπει να έχουν ή miswrote κάτι,
αλλά εσείς παίρνετε την ιδέα.
>> Θα προχωρήσουμε σε n.
Και στη συνέχεια, αν αυτό ήταν, θα ήταν βρόχο και πάλι και θα πω, εντάξει, j είναι 1 τώρα.
Και συστοιχία ι μείον 1 είναι τώρα 2.
Είναι λιγότερο από 2 στοιχείο μας;
Όχι;
Αυτό σημαίνει ότι έχουμε εισάγεται το στοιχείο αυτό
στο σωστό σημείο σε ταξινομημένη σειρά μας.
Στη συνέχεια, μπορούμε να πάρουμε αυτό και λέμε, Εντάξει, ταξινομημένο πίνακα μας είναι εδώ.
Και θα πάρει τον αριθμό αυτό 6 και να όπως, εντάξει, είναι 6 λιγότερο από αυτόν τον αριθμό;
Όχι;
Cool.
Είμαστε μια χαρά.
>> Κάν 'το και πάλι.
Λέμε 7.
7 είναι μικρότερο από το τέλος των ταξινομημένο πίνακα μας;
Όχι.
Έτσι, είμαστε μια χαρά.
Έτσι, αυτό θα πρέπει να διευθετηθεί.
Βασικά όλα αυτά κάνει είναι αυτό που λέει αφομοίωσης
το πρώτο στοιχείο του αδιαχώριστα σειρά σας,
καταλάβω πού πηγαίνει σε ταξινομημένη σειρά σας.
Και αυτό διαρκεί μόνο φροντίδα των swaps για να το κάνουμε αυτό.
Είσαι βασικά ακριβώς swapping μέχρι να είναι στο σωστό σημείο.
Η οπτική εικόνα είναι ότι είστε κινείται πάντα κάτω από αυτό.
>> Έτσι είναι σαν μισό bubble sort-esque.
Αναχώρηση μελέτη 50.
Θα ήθελα να συστήσω ιδιαίτερα προσπαθώντας να κωδικοποιήσει αυτό για τη δική σας.
Εάν έχετε οποιαδήποτε προβλήματα ή αν θέλετε να δείτε δείγμα κώδικα για ένα είδος εισαγωγής,
παρακαλώ επιτρέψτε μου να ξέρω.
Είμαι πάντα γύρω.
Έτσι χειρότερη περίπτωση εκτέλεσης και καλύτερο χρόνο εκτέλεσης υπόθεση.
Όπως μπορείτε τύπος είδε από το τραπέζι έχω ήδη που έδειξε, είναι τόσο ν τετράγωνο και ν.
>> Έτσι, το είδος του πηγαίνει μακριά από αυτό που μιλήσαμε σχετικά με τα προηγούμενα είδη μας, χειρότερο
περίπτωση εκτέλεσης είναι ότι εάν είναι εντελώς άνευ διαλογής,
πρέπει να συγκρίνουμε όλες αυτές τις n φορές.
Εμείς κάνουμε ένα σωρό των συγκρίσεων γιατί αν είναι σε αντίστροφη σειρά,
θα πάμε να πούμε, εντάξει, αυτό είναι το ίδιο, αυτό είναι καλό,
και αυτό θα πρέπει να συγκρίνονται κατά το πρώτο να κινηθεί πίσω.
Και όπως έχουμε προς το τέλος της ουράς, έχουμε
να συγκρίνουν, να συγκρίνουν, και συγκρίνετε με τα πάντα.
>> Έτσι καταλήγει να είναι περίπου n στο τετράγωνο.
Αν αυτό είναι σωστό, τότε πω, εντάξει, 2, είσαι καλός.
3, είστε σε σύγκριση με το 2.
Είσαι καλή.
4, μπορείτε απλά να συγκριθεί με την ουρά.
Είσαι καλή.
6, σε σύγκριση με την ουρά, είσαι μια χαρά.
Έτσι, για κάθε σημείο αν είναι ήδη διαλογή, έχετε κάνει μια σύγκριση.
Έτσι είναι ακριβώς n.
Και επειδή έχουμε μια καλύτερη εκτέλεσης υπόθεση Ν και χειρότερη περίπτωση εκτέλεσης του ν
τετράγωνο, δεν έχουμε καμία αναμενόμενο χρόνο εκτέλεσης.
>> Εξαρτάται μόνο από το χάος της λίστας μας εκεί.
Και πάλι, ένα άλλο γραφική παράσταση και ένα άλλο τραπέζι.
Έτσι, οι διαφορές μεταξύ των ειδών.
Είμαι ακριβώς πρόκειται να αεράκι μέσα, εγώ Νιώθουμε σαν να έχουμε μιλήσει εκτενώς
για το πώς κάθε είδους της ποικίλλει και συνδέουν μεταξύ τους.
Έτσι Ταξινόμηση με συγχώνευση είναι η τελευταία Θα σας κουράσω με τα παιδιά.
Έχουμε μια όμορφη πολύχρωμη εικόνα.
Έτσι συγχώνευση είδος είναι ένα αναδρομικό αλγόριθμο.
Έτσι, εσείς δεν ξέρετε τι μια αναδρομική συνάρτηση είναι;
>> Όποιος θέλει να πει;
Θέλετε να δοκιμάσετε;
Έτσι, μια αναδρομική συνάρτηση είναι απλά μια συνάρτηση που καλεί τον εαυτό της.
Έτσι, αν εσείς είστε εξοικειωμένοι με την ακολουθία Fibonacci,
ότι κρίνονται αναδρομικές επειδή παίρνετε τα δύο προηγούμενα
και να τα προσθέσετε μαζί να πάρετε επόμενη σας.
Έτσι αναδρομικές, πάντα σκέφτομαι της αναδρομής ως σαν μια σπείρα
έτσι είστε σαν σπειροειδώς προς τα κάτω σε αυτό.
Αλλά αυτό είναι μόνο μια λειτουργία που αυτοαποκαλείται.
>> Και, πραγματικά, πραγματικά γρήγορα μπορώ μπορεί να σας δείξει τι μοιάζει.
Έτσι αναδρομικό εδώ, αν κοιτάξουμε, αυτό είναι το αναδρομικό τρόπο για να συνοψίσω πάνω από μια συστοιχία.
Έτσι, το μόνο που κάνουμε είναι έχουμε άθροισμα λειτουργία
ποσό που παίρνει ένα μέγεθος και μια σειρά.
Και αν παρατηρήσετε, το μέγεθος μειώνεται κατά μία ημέρα κάθε φορά.
Και το μόνο που κάνει είναι αν το x είναι ίσο με zero-- οπότε αν το μέγεθος του πίνακα
είναι ίσο με zero-- επιστρέφει μηδέν.
>> Διαφορετικά, το οποίο συνοψίζει αυτό τελευταίο στοιχείο της συστοιχίας,
και, στη συνέχεια, λαμβάνει ένα ποσό της το υπόλοιπο της συστοιχίας.
Έτσι, αυτό είναι ακριβώς αυτό χωρίς να χαλάσει σε όλο και μικρότερα προβλήματα.
Μεγάλη ιστορία σύντομη, αναδρομή, συνάρτηση που καλεί τον εαυτό της.
Αν αυτό είναι το μόνο που έχεις έξω από αυτό, αυτό είναι μια αναδρομική συνάρτηση είναι.
Εάν πάρετε 51, θα πάρει πολύ, πολύ άνετα με αναδρομή.
Είναι πραγματικά δροσερό.
Έκανε νόημα σε παρόμοια Τρεις ένα βράδυ έξω.
Και ήμουν όπως, γιατί ποτέ δεν μπορώ να χρησιμοποιήσω αυτό;
>> Έτσι, για τη συγχώνευση του είδους, βασικά τι πρόκειται να κάνουμε είναι ότι είναι
πρόκειται να το σπάσει και να σπάσει προς τα κάτω μέχρι να είναι απλώς και μόνο στοιχεία.
Τα επιμέρους στοιχεία είναι εύκολο να ταξινομήσετε.
Βλέπουμε ότι.
Εάν έχετε ένα στοιχείο, είναι θεωρείται ήδη ταξινομημένο.
Έτσι, σε μια είσοδο του n στοιχεία, εάν το η είναι μικρότερο από 2,
μόλις επιστρέψει διότι αυτό σημαίνει είναι είτε 0 ή 1, όπως έχουμε δει.
Αυτοί θεωρούνται ταξινομημένα στοιχεία.
>> Διαφορετικά θα σπάσει κατά το ήμισυ.
Διαχωρίστε το πρώτο εξάμηνο, να ταξινομήσετε τη δεύτερη μισό, και στη συνέχεια να τα συγχωνεύσει μαζί.
Γιατί λέγεται συγχώνευση ταξινόμησης.
Έτσι έχουμε εδώ εμείς θα λύσουμε αυτά.
Έτσι, κρατάμε την κατοχή τους έως ότου το μέγεθος του πίνακα είναι 1.
Έτσι, όταν είναι 1, μπορούμε απλά να επιστρέψει γιατί αυτό είναι ένα ταξινομημένο πίνακα,
και αυτό είναι μια ταξινομημένη σειρά, και αυτό είναι ένα ταξινομημένο πίνακα, είμαστε όλοι ταξινομημένο.
Και τότε τι κάνουμε εμείς ξεκινήστε τη συγχώνευσή τους μαζί.
>> Έτσι, ο τρόπος που μπορείτε να σκεφτείτε συγχώνευση είναι
απλά βγάλτε τη μικρότερη αριθμός κάθε μία από τις συστοιχίες υπο
και μόλις το προσαρτήσει στο προέκυψε σειρά.
Έτσι, αν κοιτάξετε εδώ, όταν έχουμε Αυτά τα σύνολα που έχουμε 4, 6, και 1.
Όταν θέλουμε να συγχωνεύσει αυτά, κοιτάξουμε αυτές τις δύο πρώτες
και λέμε, εντάξει, 1 είναι μικρότερη, πηγαίνει προς τα εμπρός.
4 και 6, δεν υπάρχει τίποτα για να συγκρίνετε να, ακριβώς την ετικέτα για να το τέλος.
>> Όταν έχουμε συνδυάσει αυτά τα δύο, εμείς απλά να λάβει το μικρότερο από αυτά τα δύο,
έτσι είναι 1.
Και τώρα παίρνουμε το μικρότερου από τα δύο, οπότε 2.
Μικρότερα από αυτά τα δύο, 3.
Μικρότερα από αυτά τα δύο, 4, 5, 6.
Έτσι, είστε ακριβώς το τράβηγμα από αυτά.
Και επειδή έχω έχουν ταξινομηθεί προηγουμένως,
έχετε μόνο ένα σύγκριση κάθε χρόνο εκεί.
Έτσι, περισσότερο κώδικα εδώ, ακριβώς εκπροσώπηση.
Έτσι, μπορείτε να ξεκινήσετε στη μέση και μπορείτε είδος αριστερό και το δεξί
και, στη συνέχεια, μπορείτε απλά να συγχωνεύσει εκείνους.
>> Και δεν έχουμε κώδικα για συγχώνευση εδώ.
Αλλά, και πάλι, αν πάτε στην μελέτη, το 50, θα είναι εκεί.
Διαφορετικά έρθει να μου μιλήσει εάν είστε ακόμα σε σύγχυση.
Έτσι, δροσερό πράγμα εδώ είναι ότι η καλύτερη περίπτωση, χειρότερη περίπτωση, και αναμενόμενη αυτονομία
είναι όλα στο αρχείο καταγραφής n, η οποία είναι πολύ καλύτερη από ό, τι έχουμε
δει για το υπόλοιπο του είδους μας.
Έχουμε δει ν τετράγωνο και τι πραγματικά
πάρετε εδώ είναι n log n, η οποία είναι μεγάλη.
>> Κοιτάξτε πόσο καλύτερα ότι είναι.
Μια τέτοια ωραία καμπύλη.
Έτσι, πολύ πιο αποδοτική.
Αν ποτέ δυνατόν, τη χρήση συγχώνευση είδος.
Θα σας εξοικονομήσει χρόνο.
Κατόπιν πάλι, όπως είπαμε, εάν είστε κάτω σε αυτή τη χαμηλότερη περιοχή,
δεν κάνουν ότι μεγάλη διαφορά.
Μπορείτε να πάρετε μέχρι και χιλιάδες και χιλιάδες των εισροών,
σίγουρα θέλετε ένα πιο αποδοτικό αλγόριθμο.
Και, πάλι, υπέροχο τραπέζι μας όλων τα είδη που σας παιδιά έμαθαν σήμερα.
>> Έτσι ξέρω ότι αυτό είναι ένα πυκνό ημέρα.
Αυτό δεν είναι κατ 'ανάγκη θα για να σας βοηθήσει με το chipset σας.
Αλλά εγώ απλά θέλω να κάνω μια δήλωση αποποίησης ότι η ενότητα δεν είναι μόνο για psets.
Όλο αυτό το υλικό είναι δίκαιη παιχνίδι για εξετάσεις προόδου σας.
Και επίσης, αν το κάνετε να συνεχίσει με το CS, αυτά είναι πραγματικά σημαντικές βασικές αρχές
ότι θα πρέπει να γνωρίζουν.
Έτσι, μερικές ημέρες θα είναι ένα λίγο περισσότερη βοήθεια το chipset,
αλλά μερικές εβδομάδες θα είναι πολύ πιο πραγματικό περιεχόμενο
Αυτό μπορεί να μην φαίνεται σούπερ χρήσιμη σε σας τώρα,
αλλά υπόσχομαι αν συνεχίσετε και στο εξής θα είναι πολύ, πολύ χρήσιμη.
>> Έτσι, αυτό είναι για την ενότητα.
Κάτω στο σύρμα.
Το έκανα μέσα σε ένα λεπτό.
Αλλά εκεί θα πάτε.
Και θα έχω ντόνατς ή καραμέλα.
Υπάρχει κάποιος αλλεργικός σε οτιδήποτε, από τον τρόπο;
Τα αυγά και το γάλα.
Έτσι, ντόνατς είναι ένα όχι;
ΟΚ.
Εντάξει.
Σοκολάτα δεν είναι;
Starburst.
Αστρικές εκρήξεις είναι καλό.
ΟΚ.
Εμείς πάμε για να έχουν StarBurst την επόμενη εβδομάδα στη συνέχεια.
Αυτό είναι ό, τι θα πάρω.
Εσείς έχετε μια υπέροχη εβδομάδα.
Διαβάστε spec σας.
>> Επιτρέψτε μου να ξέρω αν έχετε οποιεσδήποτε ερωτήσεις.
Pset δύο βαθμούς θα πρέπει να είναι έξω για να σας μέχρι την Πέμπτη.
Εάν έχετε οποιεσδήποτε ερωτήσεις για το πώς θα βαθμολογούνται σε κάτι
ή γιατί θα βαθμολογούνται σε κάτι ο τρόπος που έκανε, παρακαλώ στείλτε μου, έλα να μου μιλήσεις.
Είμαι λίγο τρελός αυτό εβδομάδα, αλλά υπόσχομαι
Θα εξακολουθούν να απαντήσω μέσα σε 24 ώρες.
Έτσι έχουμε μια μεγάλη εβδομάδα, ο καθένας.
Καλή τύχη για το chipset σας.