[Powered by Google Translate] [Εβδομάδα 3, Συνέχεια]
>> [David J. Malan - Πανεπιστήμιο του Χάρβαρντ]
>> [Αυτό είναι CS50. - CS50.TV]
>> Εντάξει. Καλώς ήρθατε και πάλι. Αυτό είναι CS50 και αυτό είναι το τέλος της εβδομάδας 3.
>> Έτσι, για όσους δεν είναι εξοικειωμένοι, πέρυσι Χάρβαρντ ξεκίνησε αυτό που ονομάζεται το Εργαστήριο Καινοτομίας,
ή i-εργαστήριο, το οποίο είναι ένα θαυμάσιο κτήριο κατά μήκος του ποταμού στην πανεπιστημιούπολη του ΕΟΠ
η οποία είναι ανοικτή σε φοιτητές, σπουδαστές ΓΥΓ, οι μαθητές από όλα σε όλη την πανεπιστημιούπολη,
συμπεριλαμβανομένης της σχολής, και αυτό είναι ένα μέρος για να έρθει μαζί για να εργαστούν σε καινοτόμες πράγματα,
ιδιαίτερα της επιχειρηματικής πράγματα
αν και 0 ή περισσότερους φίλους που σκέφτονται να κάνουν κάτι επιχειρηματικής
είτε κατά τη διάρκεια αυτής της κατηγορίας, μετά από αυτή την κατηγορία, ή πέραν αυτού.
>> Έτσι, ένα από τα πράγματα που κάνουν πάνω από J όρος είναι αυτά τα ταξίδια,
ένα από τα οποία είναι η Νέα Υόρκη, το ένα εκ των οποίων είναι να Silicon Valley.
Το διάστημα είναι πολύ περιορισμένη, αλλά αυτό είναι μια ευκαιρία για να τρίψετε τους ώμους με MBAs
και μεταπτυχιακούς φοιτητές σε όλη την πανεπιστημιούπολη και στην πραγματικότητα περνούν το χρόνο τους στις αντίστοιχες περιοχές
κουβεντιάζοντας μέχρι ξεκινήματα, να κουβεντιάσει επάνω τους επιχειρηματίες και τα παρόμοια.
Έτσι, αν ενδιαφέρεστε, ελέγξτε έξω αυτό το URL εδώ.
Είναι επίσης διαθέσιμο στις διαφάνειες σε απευθείας σύνδεση.
>> Θα μπορούσε να μετριάσει τον ήχο σπίτι μόλις λίγο;
Αν θα θέλατε να ενωθούν μαζί μας για μεσημεριανό αυτή την Παρασκευή, 1:15 μ.μ. στο Fire & Ice, παρακαλώ κεφάλι εκεί.
Συγνώμη αν η φόρμα είναι ήδη γεμάτο από τη στιγμή που θα φτάσετε εκεί.
Αλλά εμείς θα συνεχίσουμε αυτή την παράδοση και μετά.
>> Σήμερα συνεχίζουμε τη συζήτηση υψηλότερο επίπεδο από διάφορα προβλήματα που μπορούμε να λύσουμε,
εστιάζοντας πολύ λιγότερο, σήμερα τουλάχιστον, για κώδικα και πολύ περισσότερο για τις ιδέες.
Έτσι σκέφτονται πίσω στο εβδομάδα 0, όταν έσκισε ένα βιβλίο τηλέφωνο στο μισό,
στόχος της οποίας ήταν να κάνει κάτι, ομολογουμένως, λίγο δραματικό
αλλά να στείλουν το σημείο ότι η έρευνα δεν πρέπει να είναι, κατ 'ανάγκην,
ως προφανές με την πρώτη ματιά, όπως μπορείτε να σκεφτείτε.
Και την επίλυση προβλημάτων σε γενικές γραμμές μπορεί να μην είναι πάντα κατ 'ανάγκην να είναι η καλύτερη -
Η πιο προφανής λύση δεν μπορεί κατ 'ανάγκη να είναι το καλύτερο.
Έτσι είχαμε αυτό το βιβλίο τηλέφωνο και, ειλικρινά, όλοι μας σε αυτό το δωμάτιο είχε τα ένστικτα,
κατά πάσα πιθανότητα, για να αρχίσει στη μέση, όταν ψάχνει για Mike Smith και στη συνέχεια να πάει αριστερά ή δεξιά
με βάση ό, τι γράμμα του αλφαβήτου που έτυχε να καταλήγουν σε.
>> Αλλά αυτή η απλή ιδέα ότι εμείς οι άνθρωποι έχουμε λάβει ως δεδομένο για τόσο πολύ καιρό
πραγματικά θα πρέπει να αρχίσουν να έρχονται στο προσκήνιο του μυαλού σας
επειδή τα προβλήματα παίρνουν πολύ πιο περίπλοκη από ό, τι ένα τηλεφωνικό κατάλογο,
τα ίδια απλή, λαμπρό ιδέες είναι αυτό που θα μας επιτρέψει να
να λύσει πολύ πιο πολύπλοκο και πιο ενδιαφέροντα προβλήματα,
μεταξύ των οποίων και μερικά από τα πράγματα που θεωρούμε δεδομένα ήδη αυτές τις μέρες.
Δισεκατομμύρια ιστοσελίδες εκεί έξω, ακόμη και το Google και το Bing και τα παρόμοια
είναι σε θέση να βρείτε τα πράγματα για εμάς, όπως αυτό.
Αυτό δεν συμβαίνει με τη χρήση γραμμικής αναζήτησης, αναζήτηση με όλες τις πιθανές ιστοσελίδες.
Το Facebook είναι σε θέση να σας πω ποιος όλους τους φίλους σας ή είναι φίλοι των φίλων,
και ότι επίσης μπορεί να γίνει φαινομενικά σε μια στιγμή αυτές τις μέρες
ακόμη κι αν έχουν τα εκατομμύρια των χρηστών.
>> Και έτσι πώς θα λύσει πραγματικά τα προβλήματα σε αυτό το επίπεδο, θα μειώσει τελικά
για τις ιδέες που είδαμε στην εβδομάδα 0 και λίγο περισσότερο σήμερα.
Εμείς δεν θα εκτελέσει εκ νέου αυτόν τον αλγόριθμο, αλλά θυμάμαι ότι έκανε επίσης σε αυτή την εβδομάδα 0 άσκηση
όπου όλοι είχαμε σταθεί, να λάβει τον αριθμό 1,
και στη συνέχεια είχαμε όλοι αυτο-μέτρηση με την αντιστοίχιση off, προσθέτοντας τους αριθμούς σας μαζί,
από το μισό της συμμορίας κάθισε σε κάθε επανάληψη.
Έτσι πήγαμε από 500 σπουδαστές σε 250 έως 125 και ούτω καθεξής.
Αλλά, όπως είπαμε, τη Δευτέρα, η ισχυρή ιδέα εκεί
ήταν ότι εάν διπλασίασε το μέγεθος του προβλήματος
και όλα τα παιδιά από το Δικαστήριο ή EC 10 επέστρεψε στην αίθουσα και ενώθηκαν μαζί μας,
καλά, θα μπορούσαμε να μετράνε πιθανώς όλο αυτό το σύνολο της ομάδας
με μόλις 1 πιο μεγάλο επανάληψη του βρόχου, επειδή ίσως θα ήταν μόνο διπλασιάσει το μέγεθος
ή στην περίπτωση του ΕΚ 10 λίγο περισσότερο από το διπλάσιο από το μέγεθος.
Και γι 'αυτό θα πρέπει να περάσουν λίγο περισσότερο χρόνο,
αλλά εμείς δεν θα πρέπει να δαπανήσει 400 ή 700 περισσότερα βήματα.
>> Ακριβώς για να ζωγραφίσει την εικόνα με έναν τρόπο που είναι λίγο λιγότερο αφηρημένα, ας μην έχουν όλοι σηκωθούν.
Αλλά αν όσοι από εσάς επέλεξε να καθίσει στην ορχήστρα σήμερα δεν θα με πείραζε όρθιοι,
Ας δούμε αν μπορούμε να καταλάβουμε ανάμεσά σας που το ψηλότερο άτομο είναι
κάνοντας το ίδιο είδος της συγκριτικής αλγορίθμου.
Έτσι, εάν κάθεστε στην ορχήστρα, ζητώ συγγνώμη, αλλά το βήμα 1, stand up?
βήμα 2, ζευγάρι από κοντά με κανέναν σας,
καταλάβω ποιος είναι πιο ψηλός, και καθίστε κάτω, αν είναι μικρότερες.
Στη συνέχεια επαναλάβετε.
[Φοιτητές μουρμουρίζοντας]
>> Εντάξει.
Εντάξει. Ένα μένει όρθιο. Ποιο είναι το όνομά σου; Andrew >>.
>> Andrew, που είναι το ψηλότερο άτομο στο τμήμα ορχήστρα σήμερα.
>> Συγχαρητήρια. [Χειροκροτήματα και επευφημίες] Εντάξει. Έχετε ένα κάθισμα. Έτσι βρήκαμε Andrew.
Αλλά πόσο καιρό θα με έχουν ληφθεί υπόψη, για παράδειγμα, για να βρείτε Andrew
σε αυτό το τμήμα της ορχήστρας 50 + ή έτσι οι άνθρωποι;
Θα μπορούσα να είχα πάρει μια αρκετά απλή προσέγγιση και να αρχίσει εδώ.
Και έχω 2 άτομα σηκωθούν και μπορώ να συγκρίνω τους ακριβώς,
και στη συνέχεια να λέω σε όποιον είναι ελαφρώς μικρότερη, "Εντάξει, μπορείτε να καθίσετε,"
και Πάω να θυμόμαστε ποιος είναι ο πιο ψηλός πρόσωπο ήταν.
Στη συνέχεια, επαναλαμβάνω, επαναλαμβάνω, επαναλαμβάνω, και θα κολλήσει πάνω στο ψηλότερο πρόσωπο
μέχρι να βρω κάποιον ελαφρώς ψηλότερο από αυτά, σε ποιο σημείο
η ελαφρώς μικρότερη πρόσωπο στη συνέχεια, πρέπει να καθίσουν.
Αλλά σε αυτό το αλγόριθμο σε αυτήν την ενότητα ορχήστρα, αν υπάρχει n από εσάς,
πόσα βήματα είναι ότι ο αλγόριθμος πρόκειται να πάρει; >> [Φοιτητής] N.
>> Είναι πρόκειται να πάρει n, δεξιά, διότι στη χειρότερη περίπτωση, να το πω έτσι,
το ψηλότερο άτομο είναι το τελευταίο άτομο που έχω ακριβώς από τυχαία κακή τύχη.
Έτσι, στη χειρότερη περίπτωση, ο χρόνος εκτέλεσης του αλγορίθμου είναι γραμμική, είναι n,
όπου n είναι ο συνολικός αριθμός των ατόμων στο χώρο, το μέγεθος του προβλήματος.
Τι θα γίνει με αυτόν τον αλγόριθμο;
Το γεγονός ότι όλοι σηκώθηκαν και στη συνέχεια και πάλι το ήμισυ του που κάθισε,
το ήμισυ του που κάθισε, οι μισοί από εσάς κάθισε.
Πόσα βήματα που θα πρέπει να έχουν λάβει αν υπάρχει n σου εδώ;
[Φοιτητής] Ν log n. >> Αυτό θα ήταν χειρότερα. Σύνδεση n.
>> Έτσι log n, ακόμα κι αν δεν είναι αρκετά θυμάστε τι είναι λογάριθμος,
για τώρα, απλά εκτιμώ ότι σχετίζεται με κάποιο τρόπο με αυτό και μείωση κατά το ήμισυ μείωση κατά το ήμισυ και μείωση κατά το ήμισυ.
Δεν χρειάζεται να είναι ένα παράγοντα 2. Θα μπορούσε να είναι ένας παράγοντας του 3.
Αλλά είναι αυτή η επανάληψη της ίδιας φύσεως του παράγοντα, έτσι ώστε το μέγεθος του προβλήματος ξεκινά εδώ
αλλά αμέσως μετά πηγαίνει εδώ, τότε εδώ, τότε εδώ, τότε εδώ.
Δεν παίρνετε μικρές μπουκιές από το πρόβλημα, είστε πραγματικά τεμαχισμό μακριά σε αυτό
με ένα μεγάλο μονομιάς κάθε φορά.
Έτσι, είχαμε 50 άτομα, τότε 25, τότε 12 ½ ή 13 άτομα όρθια,
τότε 6 ½ και ούτω καθεξής μέχρι που τελικά μόνο Andrew έμεινε όρθια.
Έτσι θα πάμε για να καλέσετε αυτό το αρχείο καταγραφής του n, και μπορείτε να απεικονίσει αυτό ως εξής.
Θυμηθείτε αυτή την εικόνα εδώ όπου ένας γραμμικός αλγόριθμος είναι σαν την κόκκινη γραμμή εκεί,
η κίτρινη γραμμή ήταν η καταμέτρηση από 2s αλγόριθμο που χρησιμοποιείται για τη μέτρηση φοιτητές
στο παρελθόν, αλλά σήμερα το Άγιο Δισκοπότηρο πρόκειται να παραμείνει αυτή η πράσινη γραμμή
όπου αν διπλασιαστεί ο αριθμός των ατόμων στην ενότητα ορχήστρα ή απλά είπε,
κόλαση, ας έχει ο καθένας σε ολόκληρο το δωμάτιο σταθεί, δεν είναι μια τέτοια μεγάλη υπόθεση
γιατί σχεδόν διπλασιαστεί πόσοι άνθρωποι είναι εδώ κάτω,
1 περισσότερα επανάληψη, δεν αποτελεί πρόβλημα.
>> Βρήκαμε Andrew ή όποιος συμβαίνει να είναι ψηλότερο από ό, τι Andrew
στο πατάρι ή στο μπαλκόνι.
Έτσι, αυτή την απλή ιδέα ότι πήραμε τόσο αυτονόητα σε ένα τηλεφωνικό κατάλογο,
συνειδητοποιούν ότι υπάρχουν τόσα πολλά διαφορετικά μέρη στα οποία μπορούμε να την εφαρμόσουμε.
Ακριβώς για να χαστούκι κάποια ορολογία - στην πραγματικότητα, παρά ορολογία πρώτη,
επιτρέψτε μου να πάω σε αυτή την εικόνα εδώ.
Αυτή τη στιγμή μιλήσαμε για n και n / 2 και στη συνέχεια να συνδεθείτε του n,
αλλά σίγουρα μπορούμε να καταλήξουμε σε, όπως θα κατά τη διάρκεια του εξαμήνου,
άλλου είδους μαθηματικούς τύπους για να περιγράψει αυτή τη γενική έννοια του χρόνου λειτουργίας.
Αυτά είναι έξω από το πλαίσιο για τώρα, γιατί θα δούμε σε λίγο
αλγόριθμοι ότι αυτά αντιπροσωπεύουν στην πραγματικότητα.
>> Αλλά παρατηρώ εδώ η γραμμική γραμμή n, η ευθεία γραμμή, είναι στην πραγματικότητα πολύ χαμηλή δείχνει αυτή τη στιγμή.
Αυτό είναι το είδος της μια οπτική ψευδαίσθηση το ότι εμείς απλώς να αλλάξει ό, τι ο άξονας x αντιπροσωπεύει
και ο άξονας y, και μπορούμε να κάνουμε μια ευθεία γραμμή σημείο σε οποιαδήποτε κατεύθυνση που θέλουμε.
Αλλά ο λόγος που είναι τόσο φαινομενικά επίπεδη τώρα
Είναι επειδή χρειαζόμασταν για να κάνει χώρο για αυτό το διάγραμμα για πολύ πιο αργή φορές τρέξιμο.
Προς το παρόν, γνωρίζουμε ότι υπάρχουν ορισμένες πολύ κακές αλγόριθμοι στη ζωή,
μερικά από τα οποία δεν λαμβάνουν μέτρα για ν ή, ακόμα καλύτερα, συνδεθείτε n βήματα, αλλά περισσότερο.
Έτσι, πάνω από τη γραμμή n εδώ στο κάτω μέρος υπάρχει ειδοποίηση n log n φορές,
και θα δούμε τι σημαίνει αυτό πριν από καιρό.
Πάνω απ 'αυτό είναι ν τετράγωνο, και δεν έχουμε δει κανένα n τετράγωνο αλγόριθμοι ακόμα, αλλά είμαστε έτοιμοι να.
Και αυτό φαίνεται πολύ άσχημα.
Υπάρχει 2 του ν, κάτι εκθετική, που αισθάνεται ακόμα χειρότερα.
Και όμως, περιέργως, τότε υπάρχει n κύβους, τα οποία, αν είστε το είδος των σκέφτεται το μέλλον,
αν το είδος του κάνετε τα μαθηματικά, 2 στην n πραγματικά γίνεται πολύ ίσια,
πολύ υψηλότερο από ό, τι μέχρι ν κύβο αν δείτε τους άξονες αρκετά προς τα έξω.
Έτσι, παρατηρούμε τώρα Οι άξονες αυτοί είναι αυθαίρετα 2 έως 10 στον άξονα x.
>> Και τι σημαίνει αυτό;
That σημαίνει 2 άτομα και 10 άτομα σε ένα δωμάτιο.
Αυτό είναι το μόνο μέσο x: το μέγεθος του προβλήματος, όποια και αν είναι το πλαίσιο.
Και ένα κατακόρυφο άξονα τώρα είναι ο αριθμός των δευτερολέπτων ή τον αριθμό των βημάτων -
κάποια μονάδα του χρόνου.
Να σημειωθεί όμως ότι είναι 0 - 60 και 0 έως το 10.
Αλλά αν το είδος του ζουμ έξω, όπως θα μπορούσε στο Excel ή κάποιο λογισμικό χαρτογράφησης,
και πάμε μέχρι 200.000, παρατηρήσετε ότι κάτι σαν 2 του ν
πρόκειται να συντρίψει εντελώς τις τρέχουσες περιόδους n τετράγωνο,
n κύβους, n log n - ό, τι έχουμε μιλήσει μέχρι στιγμής.
Και όμως, η σύλληψη είναι όταν αρχίσουμε να μιλάμε για πράγματα όπως το Facebook
όπου πολλοί, πολλοί, πολλοί άνθρωποι συνδέονται όλα μεταξύ τους,
έχετε n άνθρωποι, καθένας από τους οποίους θα μπορούσε να έχει όσο το n φίλους
αν ο καθένας είναι είδος του φίλος-φίλος του κόσμου,
καλά, αυτό είναι n n φορές ήδη, έτσι ώστε να είναι δυνατή n τετράγωνο φιλίες,
τουλάχιστον σε 1 κατεύθυνση, n τετράγωνο πιθανές φιλίες.
Έτσι, αυτό σημαίνει ότι ήδη ψάχνουν κοινωνικό γράφημα του Facebook, να το πω έτσι,
μπορεί να αρχίσει να εκφράζεται σε αυτά τα είδη των τύπων.
>> Θα επανέλθουμε και να κάνει αυτό πολύ πιο συγκεκριμένη,
αλλά προς το παρόν, ο στόχος για τις επόμενες πολλές εβδομάδες
πρόκειται να είναι βέβαιο ότι δεν θα πάει για την εφαρμογή αλγορίθμων ή κωδικό
που καταλήγουν λήψη όσο χρόνο κάτι τέτοιο.
Αλλά το συναρπαστικό πράγμα σχετικά με την επιστήμη υπολογιστών, αν συνεχίσει σε αυτό το πεδίο
λαμβάνοντας μαθήματα όπως CS121, CS124, δύο από τα οποία είναι θεωρητικά μαθήματα,
είναι ότι υπάρχουν πράγματι κάποια προβλήματα που υπάρχουν σε αυτόν τον κόσμο
ότι ουσιαστικά, όσο γνωρίζουμε, δεν μπορεί να λυθεί οποιαδήποτε γρηγορότερα
από ό, τι το χειρότερο από αυτά τα γραφήματα δείχνουν στην πραγματικότητα.
Έτσι, υπάρχει μια πολύ ανοικτά προβλήματα σε αυτόν τον κόσμο να κάνει πολύ καλύτερα από ό, τι οι άνθρωποι έχουν μέχρι στιγμής.
>> Ας αρχίσουμε λοιπόν με αυτό το παράδειγμα.
Είδαμε τον αγώνα Sean με αυτή την κάμερα, πολύ αδέξια στο βίντεο.
Αλλά η πραγματικότητα ήταν όταν ο Sean ήταν επιφορτισμένη με την εύρεση σε έναν πίνακα όπως αυτή, ο αριθμός 7,
Υπενθυμίζω ότι είπα ότι, "Δεν υπάρχει κάπου πίσω από αυτά τα κομμάτια χαρτιού ή λευκό πόρτες
"Ο αριθμός 7. Sean, θεωρούν ότι είναι για εμάς."
Και ήταν υπέροχα δύσκολο να παρακολουθήσουν
γιατί ήταν πραγματικά αγωνίζονται με αυτό το πρόβλημα.
Αλλά η πραγματικότητα ήταν ο Sean έκανε καθώς ο καθένας στο δωμάτιο θα μπορούσε να έχει γίνει.
Πήρε λίγο περισσότερο από ό, τι ένα τυπικό άτομο μπορεί να έχει,
αλλά υπέθεσε ότι υπήρχε κάποιο τέχνασμα σε αυτό το πρόβλημα,
υπέθεσε ότι κάτι έλειπε.
Και δεν βοηθά ότι εκατοντάδες μάτια καταπάνω του.
>> Αλλά η πραγματικότητα ήταν αν η είσοδος στο πρόβλημα είναι ένα μάτσο τυχαίων αριθμών
και σας ζητείται να βρείτε 1 τέτοιο αριθμό,
το καλύτερο που μπορείτε να κάνετε είναι γραμμική αναζήτηση.
Ξεκινήστε από τα αριστερά, μετακινήστε προς τα δεξιά, ή να ξεκινήσει στα δεξιά, μετακινηθείτε προς τα αριστερά.
Αναδρομικά, θα μπορούσαμε να σκεφτούμε, "Sean, γιατί δεν μπορείτε απλά να αρχίσετε από το άλλο άκρο;"
Λοιπόν, 7 θα μπορούσε να έχει εξίσου εύκολα εδώ τυχαία,
αλλά έβαλα επίτηδες εκεί γιατί σκέφτηκα ότι δεν πρόκειται να ξεκινήσει στο τέλος.
Γι 'αυτό το είδος των χειριστεί την κατάσταση, αλλά με τυχαία πιθανότητα 7 θα μπορούσε να ήταν οπουδήποτε.
Έτσι, ξεκινώντας από το δεξί άκρο θα μπορούσε να ήταν καλύτερη, στη συνέχεια,
αλλά τι γίνεται αν η επόμενη χρονιά θα μεταφέρετε 7 αλλού;
Αυτό δεν είναι μια εντελώς νέα λύση στο πρόβλημα -
ξεκινώντας από την 1 άκρο ή το άλλο - όταν σας δίνεται καμία άλλη υποθέσεις.
Έτσι, Sean άρχισε να ψάχνει μέσα από τους αριθμούς και είπε, "5. Αυτό δεν είναι εδώ."
Στη συνέχεια πήγε εδώ και είδα 19, στη συνέχεια, έκανε μια παύση για περίπου 20 δευτερόλεπτα,
τότε άνοιξε αυτό για 13, και στη συνέχεια έγινε φανερό
ότι δεν φαίνεται να είναι ένα πρότυπο εδώ.
Δεν ήταν 1, 2, 3, 4 ή τα παρόμοια. Υπήρχαν κενά στους αριθμούς, που δεν βοηθούν.
Και επίσης, το γεγονός ότι χρησιμοποίησα αυτά τα φτηνά κομμάτια του χαρτί για να καλύψει τους αριθμούς
Είναι πράγματι σκόπιμη, επειδή αν αφαιρεθούν όλα αυτά τα κομμάτια χαρτιού,
οι περισσότεροι από εμάς, Sean περιλαμβάνονται, κατά πάσα πιθανότητα θα έχουν μια ματιά είδος μακροσκοπικά
στο μαυροπίνακα και είπε: «Ω, 7 είναι προφανώς εκεί." Το κάναμε αμέσως.
>> Και αυτό μπορεί να είναι ο τρόπος που ο ανθρώπινος εγκέφαλος λειτουργεί σε κάποιο βαθμό,
αλλά στην πραγματικότητα, τα μάτια ή το μυαλό του ήταν πιθανώς αποκορύφωση τους αριθμούς από τα δεξιά προς τα αριστερά,
αριστερά προς τα δεξιά, μέσα στο έξω - κάτι συνέβαινε φυσιολογικά
όπως ότι αισθάνθηκε σαν να συνέβαινε αμέσως,
αλλά οι πιθανότητες είναι ακόμα και στο εσωτερικό της υπήρχε κάποια μεθοδολογία για την εύρεση 7.
Και πράγματι, τώρα που μιλάμε για πίνακες και δομές δεδομένων
και μέσα από τη μνήμη ενός υπολογιστή, το μόνο πράγμα που εμείς οι άνθρωποι μπορούμε να κάνουμε
είναι να δούμε σε επιμέρους θέσεις μνήμης 1 κάθε φορά.
>> Έτσι, κάθε άλλη θέση θα μπορούσε κάλλιστα να καλυφθούν με κάποιο κομμάτι χαρτί
επειδή δεν μπορούμε να το δούμε έτσι κι αλλιώς. Μπορούμε να κάνουμε μόνο 1 πράγμα τη φορά.
Έτσι, στην περίπτωση αυτή, στην περίπτωση του Sean, πήγαμε εδώ και στη συνέχεια πήγαμε εδώ
και στη συνέχεια πήγαμε εδώ, εδώ, εδώ, εδώ, πήρε έξυπνος από το τέλος
και ακριβώς το είδος της παραλειφθεί αυτό το ένα αυθαίρετα και βρέθηκαν 7 εκεί.
Αυτός δεν ήταν ιδιαίτερα ξεχωριστή. Είναι πάρα πολύ ήταν έξω από την τάξη.
Αλλά τελικά βρέθηκε 7.
Αλλά τώρα το πακέτο είναι πραγματικά ότι το καλύτερο που μπορείτε να κάνετε όταν δοθεί καμία πληροφορία
εκτός από τυχαία ταξινόμηση αριθμών είναι να ξεκινήσετε από την αριστερά ή να ξεκινήσετε από τα δεξιά.
Ή καλό, μπορείτε να ανοίξει τυχαία πόρτες, αλλά ακόμα και τότε τι σημαίνει να είναι τυχαία;
Λοιπόν, θα είχαμε να επισημοποιήσει με κάποιον τρόπο τι σημαίνει να ξεκινήσει εδώ,
τότε πάμε εδώ, τότε πηγαίνετε εδώ. Sean έκανε μεγάλη, και ήταν απλά διασκεδαστικό να βλέπει κανείς.
Τι θα συμβεί αν αντί να αλλάξουμε το πρόβλημα λίγο και να εμφανιστεί Sean της φετινής χρονιάς, αν θα το κάνει;
Θα μπορούσε κάποιος να είναι άνετα να ανεβαίνει στη σκηνή και την επίλυση μια ελαφρώς διαφορετική πρόβλημα
και εμφανίζονται στην κάμερα;
>> Ας πάμε πέρα ​​από την ορχήστρα, επειδή έχετε παιδιά έχουν αρκετά συμμετέχουν ήδη σήμερα.
Τι θα λέγατε σε ροζ χρώμα, το καπέλο; Έλα κάτω. Ποιο είναι το όνομά σου; >> Αλεξ. >> Αλεξ. Εντάξει.
Έτσι ο Άλεξ θα είναι Sean του τρέχοντος έτους και θα εμφανιστεί στα επόμενα χρόνια
αξίας CS50 διαλέξεις.
Alex, ωραία να σας γνωρίσουμε. >> Χαίρω πολύ.
Η πρόκληση στο χέρι για σας είναι ότι έχετε μια λίγο πιο εύκολη
υπό την έννοια ότι σας λέω τα ίδια νούμερα είναι εδώ, αλλά τώρα είναι ταξινομημένο.
Έτσι, τώρα ο στόχος σας είναι να βρείτε τον αριθμό 7.
Και στην πραγματικότητα, πρέπει να κάνουμε πραγματικά αυτό - Μπορείτε πλέον το είδος της εξαπάτησης, όπως ένας υπολογιστής δεν θα ήταν,
εξετάζοντας τι οι αριθμοί ήταν μια στιγμή πριν.
Με την κιμωλία αυτό είναι στην πραγματικότητα δεν πρόκειται να βοηθήσει τόσο πολύ,
αλλά ας προσποιηθούμε ότι δεν ξέρετε ποια είναι η αρχική σειρά είναι.
Το μόνο που ξέρω είναι ότι τώρα έχετε μια σειρά από αριθμούς ταξινόμηση
που θα μπορούσαν να έχουν κενά μεταξύ τους, και ο στόχος σας είναι να βρείτε τον αριθμό 7.
Πώς θα σας, ένα λογικό άνθρωπο, πηγαίνετε για την εύρεση του αριθμού 7;
>> Μετάβαση από χαμηλό σε υψηλό; Εντάξει >>. Μετάβαση χαμηλή προς υψηλή.
Και μην τους κόψετε. Ας σηκώσει τους ακριβώς επάνω έτσι μπορούμε να τους ξαναχρησιμοποιήσετε.
Εντάξει, έτσι 1. Περιμένετε. Πριν συνεχίσω, αυτό ήταν 1, σαφώς λάθος.
Έτσι, τι περνούσε από το μυαλό σας το επόμενο βήμα; Ποια είναι η επόμενη κίνησή σας;
Το επόμενο. Εντάξει >>. Το επόμενο. Καλή. 3, έτσι εσφαλμένη. Ποια είναι η επόμενη κίνησή σας;
Κρατήστε σε εξέλιξη. >> Εντάξει. Κρατήστε σε εξέλιξη. 5.
Έτσι να συνεχίσουμε να προχωράμε, και επιτρέψτε μου να σας δώσουν αυτό για τις επόμενες γενιές.
7. Εξαιρετική >>. Πολύ καλό. Βρέθηκε ο αριθμός 7. [Χειροκροτήματα]
Έτσι, αυτό ήταν καλό, αλλά Sean βρέθηκαν πολύ τον αριθμό 7.
Και υποστηρίζουν ότι δεν έχουν αξιοποιηθεί πραγματικά αυτή την επιπλέον πληροφορία,
το οποίο είναι ταξινομημένο ότι αυτοί οι αριθμοί.
Έτσι, μπορούμε να κάνουμε καλύτερα; Οποιεσδήποτε προτάσεις εδώ; Ναι, στο πίσω μέρος.
[Φοιτητής] Δυαδική αναζήτηση. >> Δεν έχω καμία ιδέα για το τι είναι η δυαδική αναζήτηση.
>> [Φοιτητής] Έναρξη στη μέση. Ξεκινήστε >> στη μέση. Εντάξει. Ας δούμε αν μπορούμε να φτάσουμε εκεί.
Έτσι, εάν αντί να λένε ξεκίνημα από τη μέση, να προχωρήσει και να ανοίξει την πόρτα μέση.
Υπάρχει 8 από αυτούς, έτσι θα πάμε να πρέπει να επιλέξει αυθαίρετα το ένα
ελαφρώς προς τα αριστερά ή προς τα δεξιά. Εντάξει. 7! [Χειροκροτήματα] Πολύ ωραία.
Εντάξει, αλλά όπου είχαν πάμε με αυτό;
Ας υποθέσουμε απλά για να σπάσει την ισοπαλία που είχε αρχίσει εδώ
διότι αυτό θα μπορούσε να έχει εξίσου συνέβησαν, καθώς και.
Απλά έτυχε να γνωρίζουν ότι το 7 ήταν εκεί. Έτσι, αυτό είναι 13.
Έτσι, αν είναι ταξινομημένο και εμείς μόλις ξεκίνησε στη μέση,
ποια θα ήταν η καλύτερη επόμενη κίνηση ήταν;
Πηγαίνετε το αριστερό. Και έτσι έρχεται εδώ το παράδειγμα βιβλίο τηλέφωνο και πάλι.
Αν 13 είναι εδώ και ξέρουμε ότι ο κατάλογος είναι ταξινομημένο,
τότε όλα αυτά τα κομμάτια χαρτιού χωρίς ενδιαφέρον για μας τώρα
επειδή γνωρίζουμε ήδη ότι το 7 θα πρέπει να είναι προς τα αριστερά
αν οι αριθμοί αυτοί ταξινόμηση και βρήκαμε 13.
>> Λοιπόν, τι είναι η επόμενη κίνησή σας εδώ; >> Μετάβαση προς τα αριστερά. >> Εντάξει, καλά.
Έτσι πηγαίνετε προς τα αριστερά, και - περιμένετε, hey, hey, hey. Αυτό είναι εξαπάτηση.
Έτσι βρέθηκαν 7, αλλά ό, τι ήταν ο αλγόριθμος που μόλις εφαρμοστεί;
Ξεκινήστε στη μέση. Καλή >>. Έτσι ποια είναι η λογική επέκταση της ίδιας ιδέας;
Ω, μόνο για αυτά. Ακριβώς >>. >> Γι 'αυτό και αρχίζουν εδώ. Καλή >>.
Μέχρι τώρα πήγαμε ελαφρώς προς τα αριστερά και πάλι. Είναι 3.
Αλλά το ενδιαφέρον πακέτο είναι τώρα ποια εσείς δεν πρέπει να νοιάζονται για;
Αυτά τα 2. Αυτές >> 2. Έτσι τώρα αυτό μπορεί κανείς να πάει μακριά, αυτό μπορεί κανείς να πάει μακριά.
Τώρα το πρόβλημα που τότε ήταν 8 ήταν 4 μέγεθος είναι τώρα το μέγεθος 2.
Παίρνουμε πολύ κοντά. Και πάλι, πηγαίνετε στο κέντρο αυτών των 2 στοιχείων.
>> Εντάξει. Έτσι είναι το είδος του ατυχές το γεγονός ότι τώρα είμαστε πάντα θα μείνει γιατί είμαστε στρογγυλοποίηση προς τα κάτω.
Αλλά αυτό είναι εντάξει, επειδή τώρα έχουμε ρίξει μακριά αυτό και ό, τι άλλο, αφήνοντας μας με μόνο 7.
Ας δώσουμε ένα χειροκρότημα. Βρήκαμε 7 πάλι. [Χειροκροτήματα] Εντάξει. Σίγουρα.
Περίμενε για περισσότερο μόλις 1 δευτερόλεπτο.
Ακόμη και αν η επόμενη διαδικασία είδος της πήρε λίγο περισσότερο από ό, τι θεωρήσαμε ότι θα ήταν,
Ειλικρινά, πρώτα το ένστικτό σας ήταν ο καλύτερος, έτσι δεν είναι; Βρέθηκαν 7 ακαριαία.
Αλλά θα είχαμε βρεθεί 7 πιο γρήγορα, δεν έχει σημασία τι, σε αυτό το παράδειγμα σε σχέση με αυτό το ένα
γιατί αν οι αριθμοί όλες ταξινόμηση, σαν τις σελίδες ενός βιβλίου τηλέφωνο,
μπορείτε να κόψετε το ήμισυ των πράγματι το πρόβλημα ξανά και ξανά και ξανά.
Και δεν είναι τόσο εύκολο να δει αυτό με μόλις 8 αριθμούς
σε αντίθεση με το τηλεφωνικό 1.000-σελίδα, όπου θα δείτε πραγματικά οπτικά,
αλλά σε αυτή την περίπτωση, όταν ο Sean εδώ έψαχνε για 7,
πόσα βήματα στη χειρότερη περίπτωση θα ήταν να τον πάρει; >> [Φοιτητής] 7.
7 στη χειρότερη περίπτωση. Λοιπόν, στη χειρότερη περίπτωση δεν 7 εάν υπάρχει 8 θυρών εδώ.
Θα έχουν τον 8 βήματα.
>> Έτσι, αν υπάρχει n πόρτες, θα μπορούσε να ληφθεί Sean ένα-δύο χρόνια πριν από n βήματα.
Τώρα, στην περίπτωσή σας, ο Άλεξ, δεδομένου ότι είναι ταξινομημένο αυτοί οι αριθμοί -
και μπορούμε να το είδος του να συναγάγει από αυτό που ήμασταν μέχρι τώρα σε αυτή την ιστορία -
τι είναι ο χρόνος εκτέλεσης του πιο ευφυή αλγόριθμο Άλεξ
της ξεκινώντας από τη μέση και στη συνέχεια επανάληψη;
[Φοιτητής] 3. >> Γι 'αυτό πρόκειται να είναι 3, περίπου, αν πάτε 8 - 4 2 έως 1.
Έτσι, 3 βήματα ή, γενικότερα, αυτό είναι log n και πάλι.
Κάθε φορά που είστε και μείωση κατά το ήμισυ μείωση κατά το ήμισυ και μείωση κατά το ήμισυ και μείωση κατά το ήμισυ,
αυτό είναι μια έκφραση αυτής της ιδέας του log n.
Και έτσι αυτό θα σας έχουν πάρει μόνο 3 βήματα, και μάλιστα το έκανε
μόλις ανοίξαμε τις πόρτες και μείωση κατά το ήμισυ μείωση κατά το ήμισυ,
λαμβάνοντας υπόψη ότι αυτό θα ληφθεί Sean περίπου 7 ή 8 βήματα.
Σας ευχαριστώ λοιπόν για να είναι μαζί μας φέτος. >> Σας ευχαριστούμε. Ωραία συνάντηση σας.
Σας ευχαριστούμε για την Άλεξ. Ομοίως >>. [Χειροκροτήματα]
>> Ποια είναι τότε η πραγματική επίπτωση της αυτό;
Τώρα φανταστείτε ότι δεν είναι 8 θυρών, η οποία, ειλικρινά, όλοι μας θα μπορούσε να βρει κάτι
8 θυρών πίσω αρκετά γρήγορα μόλις με σκίσιμο τα κομμάτια χαρτιού και πηγαίνοντας με τα ένστικτά μας.
Τι γίνεται όμως αν αυτό είναι ένα εκατομμύριο πόρτες; Τι και αν είναι 4 δισεκατομμύρια πόρτες;
Στην περίπτωση των 4 δισ. πόρτες, είστε πραγματικά πρόκειται να θέλουν να πάνε με τον αλγόριθμο του Alex,
δυαδική αναζήτηση, όπως θα αρχίσουμε καλώντας το ή διαίρει και βασίλευε, γενικότερα,
όπου μπορείτε κρατήσει μείωση κατά το ήμισυ και μείωση κατά το ήμισυ του προβλήματος,
γιατί αν έχετε 4 δισεκατομμύρια πόρτες, πόσες φορές μπορείτε να τεμαχίσει 4 δισ. ημίχρονο;
[Φοιτητής] 32. >> Είναι πραγματικά 32. Μπορείτε να εργαστείτε από αυτό σε ένα κομμάτι χαρτί ή στο κεφάλι σας.
Πηγαίνεις 4 δισεκατομμύρια έως 2 δισεκατομμύρια to 1 δισ. ευρώ για μισό δισεκατομμύριο, σε 250 εκατ. ευρώ, τελεία, τελεία, τελεία.
Και αν το κάνετε το math, εσείς πρόκειται να πάρει πραγματικά 32,
και αυτό αφορά στην πραγματικότητα την επιστήμη των υπολογιστών, γιατί συνήθως μετράνε σε δυνάμεις του 2.
2 έως τις 32 τυχαίνει να είναι 4 δις ευρώ.
Έτσι, υπάρχει ένα πολύ ενδιαφέρον για αυτού του είδους τις δυνάμεις του 2 στην επιστήμη των υπολογιστών.
>> Αλλά τι περίπου 8 δισεκατομμύρια; Πόσα βήματα είναι ότι θα πρέπει να ληφθούν εάν υπάρχουν 8 δισεκατομμύρια πόρτες;
[Φοιτητής] 33. Έτσι >> 33. Τι θα συμβεί αν δεν υπάρχει 16 δισεκατομμύρια πόρτες; Πόσα βήματα είναι ότι πρόκειται να πάρει;
[Φοιτητής] 34. >> 34. Θα μπορούσαμε να συνεχίσουμε το είδος αυτής της αηδίας. Αλλά αυτό είναι ένα ισχυρό πράγμα.
Μπορείτε να εισαγάγει δισεκατομμύρια περισσότερες εισόδους στο πρόβλημά σας, αλλά δεν είναι μεγάλη υπόθεση,
παίρνετε μόνο 1 επιπλέον δάγκωμα από αυτό και έτσι μας δίνει κάτι σαν δυαδική αναζήτηση
ή διαίρει και βασίλευε, γενικότερα.
Αλλά είμαι το είδος της εξαπάτησης εδώ, έτσι δεν είναι;
Στην περίπτωση του αλγορίθμου του Alex, είχε ένα πλεονέκτημα σε σχέση με τον Sean.
Ήξερε ότι αυτοί οι αριθμοί ήταν ταξινομημένο, αλλά ο Άλεξ δεν είχε να ταξινομήσετε τον εαυτό τους.
I εκ των προτέρων ήρθε στο μαυροπίνακα και το είδος των φρόντισε
ότι έβγαλα όλα έξω σε ταξινομημένη σειρά, τότε εγώ τους καλυμμένο με χαρτί.
Αλλά πόση δουλειά ήταν ότι μου πάρει;
Αν είχαμε ξεκίνησε με αυτούς τους αριθμούς σε κάποια φαινομενικά τυχαία σειρά -
σε αυτή την περίπτωση αυτές οι απλούστερες αριθμούς, 1 έως 8 εδώ -
πώς θα πάτε για την ταξινόμηση αυτών των αξιών;
Αν ήταν ένας άνθρωπος που το έργο αυτό, τι είδους διαισθητική προσέγγιση θα πάρετε
διαλογής ένα σωρό αριθμούς;
Αυτά τα πράγματα που αναφέρονται ως κομμάτια του παζλ. Ναι.
>> [Φοιτητής] θα λάβει κάθε αριθμό και συγκρίνετέ την με κάθε μία
και συνεχίστε προς τα αριστερά. >> Εντάξει, καλά.
Πάρτε λοιπόν κάθε αριθμό, συγκρίνετε το με το επόμενο να είναι,
και στη συνέχεια, μόλις συνεχίσει να κινείται κατά μήκος της λίστας, το είδος της rejiggering τα πράγματα καθώς πηγαίνετε.
Έτσι, εδώ έχουμε μια ευκαιρία για ίσως λίγα περισσότερα παιδιά να συμμετάσχουν.
Έχουμε ακόμη 8 εθελοντές που θα ήθελαν να καταλήξουμε;
Λίγο λιγότερη πίεση αφού δεν είστε ο μόνος. 1, 2, 3, 4, 5, 6, 7, 8.
Έλα κάτω. Εσείς πρόκειται να είναι οι αριθμοί 1 έως 8.
Ας δούμε αν δεν μπορούμε να κάνουμε αυτή την διαλογή για τον Άλεξ πολύ με τον ίδιο τρόπο που το έκανα εκ των προτέρων.
1, 2, 3, 4.
Προχωρήστε και αν θα κάνατε, line up στη σκηνή ανάμεσα στο περίπτερο μουσική και εγώ εδώ
με την ίδια σειρά όπως η διαφάνεια στην οθόνη.
Uh-oh.
Θα εργάζεστε στο επόμενο παράδειγμα. Περίμενε, περίμενε. Εδώ πάμε. Περιμένετε.
Το επόμενο παράδειγμα είναι τώρα. Εδώ θα πάτε. Αριθμός 8. Ελάτε επάνω.
Εντάξει. Ταξινόμηση οι ίδιοι, σύμφωνα με αυτό.
Σύρετε απλά λίγο προς την πλευρά της μουσικής στέκονται εδώ.
Έτσι, έχουμε 4, 2, 6 - να πάρει εκεί, εδώ, εκεί - 3.
Ναι. Εντάξει. Μπορείτε να πάτε εδώ. Όχι, μείνετε εκεί.
Ναι, ακριβώς εκεί. Όχι, είμαι λάθος. Ακριβώς εκεί. Εντάξει, πολύ καλό. Εντάξει.
Έτσι τώρα ας τους ταξινομήσετε σε αύξουσα σειρά.
>> Πώς μπορώ να πάω για να κάνει αυτό;
Ο αλγόριθμος που προτάθηκε πριν από λίγο ήταν γιατί δεν είμαστε απλά συγκρίνετε
οι λαοί που είναι το είδος της ένα δίπλα στο άλλο και στη συνέχεια να διορθώσετε τυχόν λάθη,
κινείται από αριστερά προς τα δεξιά.
Έτσι, εδώ έχουμε 4 και 2, προφανώς εκτός λειτουργίας. Ας αλλάζετε. Εντάξει.
Έτσι, τώρα θα πάω να κινηθεί κάτω από τη γραμμή. 4 και 6, nope. [Γέλια]
6 και 8, πολύ καλή. 8 και 1, επιτρέψτε μου να ανταλλάξουν εσείς. Εντάξει.
Έτσι, 8 και 3, αλλάξτε εσείς.
8 και 7, επιτρέψτε μου να ανταλλάξουν εσείς. 5 και 8, εξαιρετική.
Σας δίνω μια ταξινομημένη λίστα.
Εντάξει. Έτσι, δεν είναι αρκετά.
Αλλά είναι καλύτερα, επειδή οι μεγαλύτερους αριθμούς - περίπτωση στο σημείο 8 -
έχουν το είδος της διοχετεύεται επάνω από το αριστερό πάνω προς τα δεξιά.
Γι 'αυτό και πήρε 1 από τα δεξιά, αλλά αισθάνεται σαν αυτό δεν έλυσε το πρόβλημα αρκετά.
>> Λοιπόν, τι θα προτείνατε να κάνουμε το επόμενο βήμα; >> [Φοιτητής] Συνεχίστε να το κάνετε αυτό. >> Κρατάμε το κάνουμε.
Και συνειδητοποιούν, πάλι, θέτουμε τα πράγματα από απλά έχοντας όλους τους ανθρώπους
είδος οργανώσει οι ίδιοι έξυπνα με βάση αυτή την εικόνα,
αλλά τώρα πρέπει να είμαστε πολύ πιο μεθοδικά.
Πρέπει να είναι αλγοριθμική γι 'αυτό σαν να γράφουμε κώδικα -
σε αυτή την περίπτωση λεκτική ψευδοκώδικα.
Έτσι, επιτρέψτε μου να προσπαθήσω πάλι. Αυτό λειτούργησε αρκετά καλά. Δεν το λύσει.
Αλλά όταν αμφιβάλλω, απλώς προσπαθήστε και προσπαθήστε ξανά. Έτσι, 2 και 4, δεν βοηθούν πια.
4 και 6. Αχ! 6 και 1, ελαφρώς καλύτερα τώρα.
6 και 3, καλή. 6 και 7, 7 και 5, 7 και 8, καλή.
Και ξέρετε, εγώ μπορεί να αγνοήσει πιθανώς 8 τώρα επειδή είναι στο τέλος της λίστας.
Ίσως δεν έχετε να ανησυχείτε για να πάει κάποιος μπροστά του.
Αλλά ας δούμε αν αυτό είναι μια ασφαλής υπόθεση.
Τώρα είναι η λίστα - δεκάρα - δεν ταξινομημένο. Ας δοκιμάσουμε ξανά.
Έτσι 2 και 4, 4 και 1, 4 και 3.
4 και 6, καλή. 6 και 5, καλή.
6, 7, και 8, καλή. Αλλά ειδοποίηση, μπορώ μόνο να σταματήσει εδώ και τώρα να σταματήσει εδώ τώρα;
[Φοιτητής] Ναι. Ναι >>;
Τι θα συμβεί αν κάποιος από εσάς ήταν ο αριθμός 9 σε όλη τη διαδρομή πάνω από εκεί;
Θα έχουν ταξινομηθεί. Καλή >>. Θα έχουν ταξινομηθεί για πρώτη φορά γύρω.
Καλή. Ας πάμε πάλι πίσω. Είμαστε σχεδόν εκεί.
1 και 2, 2 και 3, 3 και 4, 4 και 5, 5 και 6, 6 και 7, 7 και 8.
>> Είμαι γίνει τώρα, αλλά, και πάλι, είμαι ένας υπολογιστής που μπορεί να κάνει μόνο ό, τι μου έχουν πει να κάνω,
και μόνο ανάμνηση μου τώρα είναι ότι εγώ πραγματικά έκανε ακριβώς ένα κομμάτι της εργασίας.
Κάτι άλλαξε εδώ.
Γι 'αυτό και δεν έχουν επιβεβαιωθεί οπτικά τεχνικά ή αλγοριθμικά ότι ο κατάλογος αυτός είναι πράγματι ταξινομημένο.
Έτσι, μόνο για το καλό μέτρο, ακριβώς για να είναι πρωκτικό γι 'αυτό, ας κάνουμε αυτό 1 φορά.
Έτσι 1 και 2, 2 και 3, 3 και 4. Και ξέρετε τι;
Ακριβώς για το καλό μέτρο, Πάω να παρακολουθείτε το χέρι μου αυτή τη φορά
πόσα swaps κάνω ακριβώς έτσι ότι ξέρω πόση δουλειά που έχω κάνει στην πραγματικότητα.
3 και 4, 4 και 5, 5 και 6, 6 και 7, 7 και 8. Δεν swaps.
Έτσι τώρα θα ήθελα να είναι νόμιμα ηλίθιος για να το κάνουμε αυτό και πάλι
γιατί αν το έκανα καμία δουλειά μέσα από αυτό το πέρασμα των ανθρώπων,
τότε σαφώς ότι πρόκειται να συμβεί ξανά εάν κανένα από αυτά δεν είναι τυχαία είδος της
adversarially κινείται γύρω από τον εαυτό τους. Έτσι τώρα μπορώ να σταματήσω.
Τώρα ας θέσουμε το ερώτημα, πόση δουλειά έκανε αυτό μου πάρει πραγματικά;
Πόσα βήματα δεν πάρει αυτό; >> Ν τετράγωνο.
Ναι, έτσι n τετράγωνο. Σε περίπτωση που δεν μπορείτε να πάρετε από το τετράγωνο n;
Θα πρέπει να ελέγξετε κάθε αριθμός -
Υπάρχει n αριθμούς, και θα πρέπει να ελέγξετε κάθε αριθμό με τους άλλους αριθμούς n.
Καλή. >> Έτσι είναι n τετράγωνο. Καλή >>.
>> Γι 'αυτό αισθάνεται όπως θα μπορούσε κάλλιστα να είναι n τετράγωνο, έτσι δεν είναι;
Εκεί n από αυτά τα παιδιά, 8 ειδικά σε αυτή την περίπτωση,
αλλά κάθε φορά που πήγα μέσα από αυτή τη λίστα μου συγκρίνοντας το πρώτο πρόσωπο κατά τη δεύτερη,
η δεύτερη κατά το τρίτο ξανά και ξανά και ξανά,
και όταν έφτασα στο τέλος, τι να κάνω; Μου redid.
Έτσι, αν γενικεύσουμε αυτή την εξήγηση, έχουμε n άτομα
και κάνω, προφανώς 8 βήματα, n βήματα, κάθε φορά που πάω με αυτόν τον αλγόριθμο.
Αλλά πόσες φορές στη χειρότερη περίπτωση δεν πρέπει να περάσει μέσα από αυτή τη λίστα των ανθρώπων;
[Φοιτητής] Ν φορές. Πιθανώς n >>, δεξιά, διότι στη χειρότερη περίπτωση,
τι είναι ίσως η χειρότερη περίπτωση ρύθμισης από αυτά τα παιδιά από το get-go;
Αν είστε αντιστραφεί εντελώς παραγγελία
επειδή ακριβώς ας υποθέσουμε, διανοητικά let's - Ποιο είναι το όνομά σου; >> Bowen.
Bowen. Εντάξει. Έτσι Bowen, έλα εδώ για μια στιγμή.
>> Ας υποθέσουμε ότι Bowen ήταν εδώ κατά την έναρξη του αλγορίθμου,
και δεν ξέρουμε τι όλοι οι άλλοι είναι, αλλά εδώ Bowen, σύμφωνα με αυτόν τον αλγόριθμο -
και αν θέλετε απλά να κάνετε μια βόλτα μαζί μου - πρόκειται για φούσκα επάνω, όπως έκανε και την πρώτη φορά,
όλη τη διαδρομή μέχρι το τέλος.
Αλλά ας υποθέσουμε ότι το πρόσωπο δίπλα σε Bowen ήταν ο αριθμός 7.
Πρέπει να πάω πίσω και να πάρει τον αριθμό 7, το οποίο σημαίνει ότι πρέπει να πάει όλος ο τρόπος πίσω εδώ.
Τώρα πρέπει να έχω την ίδια απόσταση με το πρόσωπο που είναι ο αριθμός 7.
Αλλά τι θα γινόταν αν τότε ο αριθμός 6 ήταν δίπλα του, καθώς;
Στη συνέχεια, πρέπει να πάω πίσω και να πάρει 6.
Έτσι, και πάλι, σε κάθε επανάληψη του βρόχου αυτό μιλάω για κάθε μία από τις n ανθρώπων,
και εγώ θα πρέπει να κάνει n αυτών βόλτες για να βεβαιωθείτε ότι είμαι τραβώντας
όλα από τα μεγαλύτερα στοιχεία και πίσω και πίσω μέχρι το τέλος της λίστας.
Έτσι, n n φορές τα πράγματα είναι ακριβώς n φορές n ή n τετράγωνο.
>> Έτσι, εδώ έχουμε ήδη έναν αλγόριθμο που δεν είναι πλέον ν, που δεν είναι πλέον log n,
είναι στην πραγματικότητα χειρότερο από οτιδήποτε έχουμε κάνει στο παρελθόν.
Έτσι Alex είδος του πήρε τυχερός στο ότι έκανα όλη τη δουλειά προφανώς μπροστά γι 'αυτήν,
όλα τα ακριβά εργασίας, έτσι ώστε θα μπορούσε να απολαύσετε σε αυτό το δυαδικό αλγόριθμο αναζήτησης,
που είναι log n του.
Αλλά αυτό είναι συμβατό με το θέμα της Δευτέρας.
Δώσαμε ένα λίγο περισσότερο χώρο, θα χρησιμοποιείται περισσότερο bits, προκειμένου να επιταχυνθεί χρόνο λειτουργίας μας.
Τόσο πολύ σαν να υπάρχει αυτό το trade-off μεταξύ του χρόνου και του χώρου,
μπορεί να υπάρχουν, επίσης, απλά να τους συμβιβασμούς μεταξύ του χρόνου που πέρασε μπροστά είδος του να πάρει τα πράγματα είναι έτοιμα να ξεκινήσουν
και εκτελεί στην πραγματικότητα έναν αλγόριθμο όπως η αναζήτηση. Ας προσπαθήσουμε ένα άλλο.
Αν εσείς δεν θα με πείραζε απλά γρήγορα αναδιάταξη εαυτό σας για να ταιριάζει με ότι και πάλι,
ας δοκιμάσουμε κάτι διαφορετικό ελαφρώς όπου δεν είναι αρκετά τόσο απλό
όπως ακριβώς διορθώσετε όλα τα λάθη ανά ζεύγος, το οποίο είναι εξαιρετικά διαισθητική.
Ας αντί να είναι λίγο πιο σκόπιμη και να το κάνετε αυτό.
Αυτό και μόνο πολύ θα ήθελα να προτείνω είναι μάλλον αρκετά έξυπνο.
>> Ας επιλέξτε το μικρότερο άτομο από τη λίστα ξανά και ξανά. Έτσι, εδώ πηγαίνουμε.
4, που είναι το μικρότερο άτομο που έχω δει έτσι μέχρι τώρα,
έτσι Πάω να θυμόμαστε διανοητικά ότι με απλά δείχνοντας σας για τώρα.
2. Ooh! Ξεχάστε τον αριθμό 4. Βρήκα μόλις το νέο μικρότερο στοιχείο σε αυτή τη λίστα.
Πάω να θυμούνται το είδος αυτό. 6, 8.
Ooh! 1. Αντίο. Έτσι, τώρα θα πάω να θυμόμαστε τον αριθμό 1.
Γνωρίζουμε ότι το 1 είναι ο μικρότερος, αλλά είμαι ο υπολογιστής. Τι γίνεται αν υπάρχει ένα 0;
Τι γίνεται αν υπάρχει ένα -1; Πρέπει να συνεχίσω.
Έτσι, 3, 7, 5, nope. Εντάξει. Έτσι, ο αριθμός 1 ήταν η μικρότερη.
Επιτρέψτε μου να σας επιλέξτε από τη λίστα - we'll πάει με αυτόν τον τρόπο -
και βάζετε αυθαίρετα στην αρχή της λίστας.
Τώρα, περιμένετε ένα λεπτό. Ι το είδος εξαπατημένοι.
Αν αυτοί οι τύποι δεν αντιπροσωπεύουν μια λίστα των 8 ατόμων, αλλά μια σειρά,
8 κομμάτια της συνεχούς μνήμης - δεν σας πειράζει βήμα πίσω για μια στιγμή;
Δεν υπάρχει πραγματικά κανένας χώρος για σας εδώ.
Επομένως, πώς θα κάνουν χώρο για - τι είναι το όνομά σας; >> Sammy. >> Sammy.
Πώς θα κάνουμε χώρο για Sammy;
>> Κινούμαστε τα n που είναι μπροστά μου. Εντάξει >>.
Έτσι, θα μπορούσαμε να μετακινήσετε τα n άτομα που είναι πριν απ 'αυτόν,
οπότε αν εσείς θέλετε να λάβει 1 σκόπιμη, δραματικό βήμα προς τα αριστερά.
Έκαναν όλα αυτά σε αρμονία, αλλά την τελευταία φορά που έγραψα κάποιο κώδικα,
δεν μπορείτε να ταξινομήσετε του κινούνται πολλά πράγματα ταυτόχρονα.
Θα μπορούσαμε να το κάνουμε με έναν βρόχο, κινείται ο καθένας μια φορά σε μια στιγμή.
Έτσι, αν εσείς δεν θα με πείραζε βήμα πίσω προς τα δεξιά,
και Sammy, εάν θα μπορούσε να βήμα πίσω, γιατί υπάρχει ακόμα κανένας χώρος για σας,
Τώρα ας κάνουμε αυτό. Πού ήταν Sammy πριν από λίγο; Ακριβώς εκεί.
Έτσι, υπάρχει ένα κενό εκεί. Έτσι, θα μπορούσε να κινηθεί σε σημείο του Sammy.
Τώρα επόμενο πρόσωπο μέχρι και τώρα το επόμενο πρόσωπο, τώρα το επόμενο πρόσωπο. Τώρα έχουμε περιθώρια για Sammy.
Τώρα, κάποιος από το κοινό - που ήταν καλή, που ήταν σωστή,
αισθάνθηκε λίγο χρονοβόρα - τι είναι πιο γρήγορα; Ναι.
[Φοιτητής] Μια νέα σειρά; >> Τι είναι αυτό; >> [Φοιτητής] Μια νέα σειρά; >> Εντάξει, καλά.
>> Έτσι, σύμφωνα με αυτό το θέμα μόλις συμβιβασμούς, γιατί δεν μπορώ να κάνω μόνο μια νέα σειρά
και στη συνέχεια θα Sammy να κολυμπάνε στο χώρο μπροστά από αυτά τα άτομα, για παράδειγμα,
και μπορούμε απλά να αρχίσει να γεμίζει μια εντελώς νέα σειρά. Αυτό επίσης θα μπορούσε να λειτουργήσει.
Αλλά δεν είμαι ενδιαφέρονται για τις δαπάνες σήμερα περισσότερο χώρο. Τι είναι μια άλλη προσέγγιση;
[Φοιτητής] Swap. Εντάξει >>. Θα μπορούσαμε να ανταλλάξουν μόνο αυτά τα 2 παιδιά. Ποιο είναι το όνομά σου;
Mario. >> Mario. Έτσι, Mario, ήσασταν σήμερα εδώ.
Sammy, μπορείτε να δημιουργήσετε αντίγραφα ασφαλείας για μια στιγμή; Mario ήταν εδώ.
Δεν έχουμε περιθώρια για σας πια, οπότε αν δεν θα με πείραζε, όπου πρόκειται να Sammy είναι,
θα βάλουμε Sammy εδώ, και τώρα θα ήθελα να υποστηρίζουν ότι αλλάζουν τη λειτουργία του Sammy ήταν πολύ πιο γρήγορα.
Κάναμε μία λειτουργία για να ανταλλάξει αυτά τα παιδιά, ή ίσως 2 για να ανταλλάξουν αυτά τα παιδιά,
αλλά δεν κάναμε 1, 2, 3, 4, έτσι ώστε αισθάνεται καλύτερα. Τώρα, περιμένετε ένα λεπτό.
Ι το είδος του κάνει το πρόβλημα χειρότερο, διότι ο αριθμός 4 ήταν το είδος του κοντά στην αρχή.
Τώρα αριθμός 4 είναι λίγο πιο κοντά προς το σκοπό αυτό, αλλά δεν είχα πραγματικά γνωρίζουν ή ενδιαφέρονται γι 'αυτό.
Έτσι, αυτό είναι απλά κακή τύχη ότι ο αριθμός 4 είναι λίγο πιο μακριά από την προκαθορισμένη του θέση.
Ας επαναλάβουμε τώρα αυτόν τον αλγόριθμο.
>> Για να ανακεφαλαιώσουμε, εφ 'όσον αυτή η ιστορία ήταν, το μόνο που έκανε ήταν με τα πόδια μέσα από τη λίστα
ψάχνει για τον αριθμό μικρότερο άτομο.
Έτσι, τώρα ας το κάνουμε πάλι. Δεν χρειάζεται να ανησυχείτε για Sammy πια.
Μπορούμε απλά να πάτε εδώ. Ooh! Αριθμός 2. Αυτός είναι ένας πολύ μικρός αριθμός.
6, 8, 4, 3, 7, 5. Εντάξει, καλά.
Και ευτυχώς, από σύμπτωση, δεν έχω να κινηθεί - >> Willie.
Willie επειδή είναι σε σωστή θέση του τώρα.
Ας κάνουμε αυτό και πάλι και να αγνοούν αυτά τα 2 παιδιά.
6. Αυτός είναι ένας πολύ μικρός αριθμός. Ooh! 8 είναι σίγουρα μεγαλύτερο.
4. Ας επικεντρωθεί στις 4. Ooh! 3 είναι ακόμα καλύτερα.
7 και 5. Λοιπόν, τι θα κάνουμε τώρα με - >> Ρότζερ. >> Roger;
Ας τον ανταλλάξουν με τον αριθμό 6.
Έτσι, εάν 6 και 3 θα ήθελα να ανταλλάξουν,
έχουμε τώρα το είδος του πάρει τυχερός σε αυτό το 6 είναι πιο κοντά στο σημείο όπου αυτή θα πρέπει να είναι,
αλλά είναι απλώς σύμπτωση εδώ. Ας πάμε τώρα εδώ.
8 είναι ένα πολύ μικρό αριθμό. Ooh! 4 είναι μικρότερη.
6, 7, 5. Τι κάνουμε τώρα; Swap >>. Ακριβώς >>.
Έτσι, τώρα ας κάνουμε αυτό το είδος της πιο γρήγορα.
8, 6, 7, 5. Πού 5 πάτε; Καλή. Εντάξει.
6, 7, 8. 6 παίρνει να μείνει εκεί που είναι. Ποιο είναι το όνομά σου; >> Rosalie.
Rosalie παίρνει να μείνει εκεί που είναι. 7 παίρνει να - Για να δούμε. 7, 8. Εντάξει.
Έτσι 7 παίρνει να μείνει εκεί που είναι. Ποιο είναι το όνομά σου; >> Amna. >> Amna.
>> Έτσι Amna παίρνει να μείνει εκεί που είναι, και ο αριθμός 8 είναι ήδη τώρα, όπου πρέπει να είναι.
Εντάξει, καλά. Αισθάνεται σαν να είμαστε δημιουργώντας απλά το έργο για τους εαυτούς μας εδώ, όμως.
Τι είναι τελικά ο χρόνος εκτέλεσης του αλγορίθμου;
Αν σκεφτούμε αυτούς τους ανθρώπους όχι ως 8, αλλά όπως n; >> Είναι n.
Είναι n βήματα, αλλά είμαστε έλεγχο κάθε φορά.
Εντάξει. Ν αλλά εσείς τον έλεγχο κάθε φορά;
Εντάξει, αλλά αν είναι n βήματα, δεν θα πρέπει να έχω τη δυνατότητα να ταξινομήσετε σας με απλά θα 1, 2, 3, 4;
Oh! Εντάξει, αυτό είναι μια μεγάλη διαφορά.
Έτσι n τετράγωνο γιατί; Τι πραγματικά συμβαίνει;
Υπάρχει n άνθρωποι σε αυτή τη λίστα, αλλά για να βρει το μικρότερο άτομο στον κατάλογο
στη χειρότερη περίπτωση, πόσα βήματα μπορώ να λάβει; >> Ν.
>> Ν, δεξιά, διότι στη χειρότερη περίπτωση, ο αριθμός 1 είναι όλος ο τρόπος εκεί,
γι 'αυτό πρέπει να πάει να πάρει αυτόν ή αυτήν.
Και στη συνέχεια, όταν τελικά συνειδητοποιούν 1 ήταν το μικρότερο, τότε είναι αρκετά γρήγορος για να τους ανταλλάξουν.
Αλλά τώρα πρέπει να ξεκινήσει από την αρχή και να δούμε για ποιον;
Η επόμενη μικρότερη προσώπου, η οποία είναι 2. Σε περίπτωση που στη χειρότερη περίπτωση είναι 2;
Ω, Θεέ μου. Είναι όλος ο τρόπος εδώ στο τέλος.
Μέχρι τώρα έχω κάνει μόνο μια άλλη n βήματα, ένα άλλο n βήματα.
Και αν έχουμε n άτομα και στη χειρότερη περίπτωση το μικρότερο άτομο είναι n βήματα,
αυτό είναι και πάλι n n φορές, και γι 'αυτό έχουν και πάλι ν τετράγωνο.
Αυτό δεν αισθάνεται και τόσο καλά.
Και στην πραγματικότητα, ακόμη και στην καλύτερη περίπτωση - ας υποθέσουμε ότι ξεκινάτε ταξινομημένο -
πόσα βήματα χρειάζεται για μένα με αυτόν τον αλγόριθμο για να ταξινομήσετε τα n άνθρωποι;
Ν τετράγωνο. >> Άκουσα ν τετράγωνο. Γιατί ν τετράγωνο;
Επειδή πρέπει ακόμα να ελέγξει κάθε φορά. Ναι >>.
Και θα πρέπει να τα ανταλλάξουν. >> Ακόμα κι αν οι άνθρωποι είναι το είδος του παντογνώστης
με την έννοια ότι οπτικά μπορούμε ακριβώς το είδος της δείτε ότι αυτό είναι ταξινομημένο,
ένας υπολογιστής δεν είναι ότι έξυπνος.
Είναι πρόκειται να δούμε εδώ και εδώ και εδώ,
αλλά αν αυτό που ψάχνει είναι το μικρότερο στοιχείο,
το μόνο που ξέρετε ότι βρήκε το μικρότερο στοιχείο από ποιο σημείο; Μόλις είστε στο τέλος.
Αλλά σε αυτό το σημείο έχετε βρεί μόνο το σήμερα μικρότερο στοιχείο.
Δεν ξέρω κατ 'ανάγκη οτιδήποτε άλλο για την κατάσταση του κόσμου.
Έτσι, θα πρέπει να πάτε ξανά και ξανά και ξανά.
>> Έτσι, αυτή τη φορά πραγματικά φαίνονται χαζή επειδή είμαι έλεγχο, εντάξει, 2, είσαι το μικρότερο,
αλλά δεν ξέρω πως στο σύνολο ακόμα.
3, 4, 5, 6, 7, 8. Εντάξει, καλά. 2 ήταν πράγματι ο μικρότερος.
Τώρα ας βρούμε την επόμενη μικρότερη. Εντάξει.
3, είστε επί του παρόντος το μικρότερο. Ας δούμε. 4, 5, 6, 7, 8. Εντάξει, πήρε και πάλι τυχερός.
3 ήταν πράγματι στο σωστό μέρος. Αλλά Πάω να συνεχίσει να κάνει αυτό ξανά και ξανά και ξανά.
Πώς μπορούμε να κάνουμε πάντα τόσο ελαφρώς καλύτερα;
Αντί να έχουμε ανθρώπους φούσκα επάνω ζεύγη από το μικρότερο στο μεγαλύτερο
και αντί να πηγαίνουν πέρα ​​δώθε μέσα από τη λίστα επιλέγοντας το μικρότερο άτομο, στη συνέχεια,
γιατί δεν εισάγουμε αυτούς τους ανθρώπους, αντί σε ένα νέο βήμα προς βήμα λίστα;
Ας προσπαθήσουμε αυτό. Τώρα, επιτρέψτε μου να καλέσετε αυτό το είδος εισαγωγής πράγμα.
Έτσι, εδώ είμαστε εδώ. Αριθμός 1. Δεν με νοιάζει για κανέναν άλλο σε αυτή τη λίστα.
Ο στόχος μου τώρα είναι να τεθεί ο αριθμός 1 στην αρχή μιας ταξινομημένη λίστα.
Και Πάω να προτείνω επειδή έχω μόνο 8 κομμάτια της μνήμης,
αυθαίρετα τώρα είμαι ο τοίχος μεταξύ δήθεν αδιαχώριστα λίστα μου,
και όποιος είναι πίσω μου Πάω να διεκδικήσει είναι ταξινομημένο.
Έτσι τώρα έχουμε τον αριθμό 1.
Θέλω να τον τοποθετήσετε σε ταξινομημένη λίστα μου, οπότε είμαι απλώς πρόκειται να κινηθεί τοίχο μου εδώ,
και τώρα υποστηρίζουν αυτή η λίστα είναι ταξινομημένη, ο κατάλογος αυτός δεν έχει υποστεί διαλογή - τουλάχιστον μέχρι στιγμής όσο γνωρίζω.
Δεν μπορώ να δω όλους τους αριθμούς ταυτόχρονα.
>> Τώρα τυχαίνει να συναντήσουν τον αριθμό 2. Τι μπορώ να κάνω μαζί του;
Σας εισάγετε τώρα στην ταξινομημένη λίστα. Αλλά παρατηρήσετε πόσο εύκολο ήταν αυτό.
Απλά πρέπει να κοιτάξουμε. Αριθμός 1 είναι εκεί. Ω, προφανώς 2 πηγαίνει προς την πλευρά του αριθμού 1.
Τώρα τι μπορώ να κάνω με 3; Σας εισάγετε στο ταξινομημένη λίστα. Αλλά αυτό ήταν εξαιρετικά εύκολο.
Αυτό είναι εξαιρετικά εύκολο, αυτό είναι εξαιρετικά εύκολο, αυτό είναι εξαιρετικά εύκολο, εξαιρετικά εύκολο, σούπερ εύκολο.
Και τώρα όλα είναι ταξινομημένο πίσω μου, και πόσα βήματα δεν πάρει αυτό;
[Φοιτητές] >> Ν. Γι 'αυτό είναι μόνο n. Είμαστε τυχεροί.
Ήταν μόνο n γιατί; >> [Φοιτητής] Επειδή ο κατάλογος ήταν ταξινομημένο.
Ο κατάλογος είναι ήδη ταξινομημένο. Γι 'αυτό και πήρε τυχερός.
Αλλά σχεδιάσαμε έναν αλγόριθμο αυτή τη φορά που εκμεταλλεύεται αυτό το είδος της τύχης,
ότι καλύτερο σενάριο, με το να μην χάνουμε περιττό χρόνο.
Έτσι έχουμε τώρα τι θα καλέσουμε τα είδη φούσκα
όπου οι άνθρωποι είδος της φούσκας μέχρι ζεύγη.
Έχουμε τώρα είδος επιλογής όπου θα κόβω από το μικρότερο άτομο ξανά και ξανά.
Και τώρα έχουμε είδος εισαγωγής όπου είδους προληπτικά βάλει τους ανθρώπους που ανήκουν
σε μια όλο και πιο ταξινομημένη λίστα.
Αν μπορούσαμε, ένα χειροκρότημα για αυτά τα παιδιά εδώ. [Χειροκροτήματα]
Ας ρίξουμε 5-λεπτά διάλειμμα μας εδώ.
Και όταν θα έρθει πίσω, θα φυσήξει όλα αυτά αλγορίθμων έξω από το νερό
με κάτι καλύτερο. Εντάξει. Ευχαριστώ πολύ. Μπορείτε να κρατήσετε τα ως αναμνηστικά.
Εντάξει. Είμαστε πίσω.
>> Και για να ανακεφαλαιώσουμε πολύ γρήγορα, είχαμε αυτά τα 3 διαφορετικές προσεγγίσεις για την ταξινόμηση,
το νόημα της οποίας ήταν να φτάσουμε στο σημείο όπου κάποιος σαν τον Άλεξ
θα μπορούσε να αναζητήσει μια λίστα με τους αριθμούς πιο γρήγορα από ό, τι κάποιος θα μπορούσε, όπως ο Sean.
Και ακόμα κι αν έχουμε τέτοια απλά παραδείγματα με 8 αριθμούς,
θα μπορούσατε να προεκτείνουν εύκολα σε 8 ιστοσελίδες, 8 δισεκατομμύρια ιστοσελίδες,
ή 800 εκατομμύρια φίλους στο Facebook.
Έτσι, αυτοί οι αλγόριθμοι μπορεί σίγουρα να κλιμακωθούν σε αυτά τα είδη των αξιών,
και οι ιδέες είναι τελικά το ίδιο.
Έτσι, το είδος φούσκα ήταν η πρώτη όπου το είδος της διοχετεύεται το μεγαλύτερο πρόσωπο
σε όλη τη διαδρομή προς τα δεξιά από την εναλλαγή τους ανθρώπους ανά ζεύγος.
Τότε είχαμε τι θα καλέσουμε είδος επιλογής όπου λίγο πιο σκόπιμα
διατηρούνται αναζητούν μέσα από τη λίστα, επιλέγοντας το μικρότερο αριθμό ξανά και ξανά και ξανά,
το λογικό αποτέλεσμα της οποίας είναι ότι ο κατάλογος είναι τελικά ταξινόμηση.
Στη συνέχεια, στο τρίτο, προσέθεσα άνθρωποι στην κατάλληλη θέση τους,
και κάναμε μια πολύ καλοσχεδιασμένη παράδειγμα το γεγονός ότι ο κατάλογος ήταν ήδη ταξινομημένο,
αλλά αυτό ήταν να στείλει το μήνυμα ότι σε περίπτωση που το είδος της εισαγωγής,
μπορείτε να πάρετε τυχεροί.
Αν οι αριθμοί που έχουν ήδη ταξινομημένο, αυτό είναι μόνο πρόκειται να σας πάρει n ενέργειες προκειμένου να επιβεβαιώσει τόσο πολύ,
λαμβάνοντας υπόψη ότι η επιλογή του είδους είστε λίγο περισσότερο όραμα σηράγγων
και δεν συνειδητοποιούν ποτέ ότι ο κατάλογος είναι ήδη ταξινομημένο.
Ας δούμε λοιπόν είδος φούσκα σε δράση εδώ.
Στο παρακάτω παράδειγμα, είμαστε έτοιμοι να δούμε κάθετες μπάρες
ύψος των οποίων αντιπροσωπεύουν οι αριθμοί, έτσι ώστε να μπορούμε να ταξινομήσετε τη διαλογή των Κοίτα να συμβεί.
Όσο μικρότερη είναι η γραμμή, τόσο μικρότερος είναι ο αριθμός? Όσο μεγαλύτερη είναι η γραμμή, τόσο μεγαλύτερος είναι ο αριθμός.
>> Και θα το παίξει σε αυτή την ταχύτητα προεπιλογή.
Είναι πρόκειται να κινηθεί λίγο γρήγορα για τώρα, αλλά το κόκκινο είναι αυτό που δείχνει 2 μπαρ
που συγκρίνονται δίπλα-δίπλα.
Και αν δείτε προσεκτικά, αυτό που συμβαίνει είναι ότι, εάν οι ράβδοι είναι εκτός λειτουργίας,
το μικρότερο μετακινείται προς τα αριστερά, το μεγαλύτερο, προς τα δεξιά,
και στη συνέχεια να κρατήσει την προώθηση.
Έτσι, αν το κάνουμε αυτό ξανά και ξανά, παρατηρούμε ότι τα μικρότερα μπαρ
πρόκειται να κρατήσει στριμώχνονται το δρόμο τους προς τα αριστερά
και τα μεγαλύτερα μπαρ θα στριμώχνονται για να κρατήσει το δρόμο τους προς τα δεξιά.
Και πράγματι, αρχίζουμε να δούμε ένα μοτίβο σε όλη τη διαδρομή στη δεξιά πλευρά
όπως είδαμε 8 και στη συνέχεια 7 τελικά αναβλύζει στην άκρη του ανθρώπινου λίστα μας.
Έτσι, αυτό πρόκειται να πάρει πολύ γρήγορα λίγο κουραστικό, οπότε επιτρέψτε μου να σταματήσει αυτό για μια στιγμή.
Επιτρέψτε μου να αλλάξετε την ταχύτητα να είναι πολύ πιο γρήγορα.
Δεν είμαι αλλάζει τον αλγόριθμο, είμαι απλώς κάνοντας την κίνηση να συμβεί γρηγορότερα.
Ακόμα είδος φούσκα, ίδιο αλγόριθμο,
αλλά τώρα μπορείτε να δείτε πολύ πιο γρήγορα από ό, τι λεκτική επίδειξη μας
ότι τα μεγαλύτερα στοιχεία πράγματι bubbling μέχρι την κορυφή.
>> Ως μέρος, αυτά τα μικρά τετράγωνα στο κάτω αριστερά και κάτω δεξιά
είναι απλώς λίγο υπενθυμίσεις για το πώς πολλές συγκρίσεις που κάνετε.
Αλλά για τώρα, μπορούμε να επικεντρωθεί στην πυραμίδα που είναι να παίρνει μορφή, και εκεί πηγαίνει.
Το μικρότερο στοιχείο είναι στα αριστερά, ο μεγαλύτερος στα δεξιά, και ό, τι άλλο στο μεταξύ.
Τώρα, ας ρίξουμε μια ματιά, αντί στο είδος επιλογής.
Πάω να προχωρήσει και να χτυπήσει στάση. Εμείς πάμε για να πάρετε μια νέα τυχαία σειρά από μπαρ.
Είδος επιλογής, ανάκληση, περνά μέσα από τη λίστα ξανά και ξανά και ξανά,
μάδημα το μικρότερο στοιχείο. Έτσι, εδώ είναι είδος επιλογής.
Φαίνεται σαν να υπάρχει λιγότερη εργασία συμβαίνει τώρα, διότι δεν είμαστε συγκρίνοντας ζεύγη
αλλά είμαστε ακριβώς το είδος του κεράσι πάρει τα μικρότερα στοιχεία από τα δεξιά προς τα αριστερά.
Αυτό πήρε πολύ λίγο χρόνο, έτσι υπάρχει μια διχοτομία ήδη.
Ακριβώς επειδή ένας αλγόριθμος λέγεται να τετράγωνο n φορά, όπως το είδος φούσκα
και σαν είδος επιλογής, αυτά είναι πραγματικά χειρότερη περίπτωση χρόνους λειτουργίας.
Για παράδειγμα, στην περίπτωση του, ας πούμε, το είδος επιλογής,
Εγώ πραγματικά είμαι επιλέγοντας το μικρότερο άτομο και τη θέση σ 'αυτόν εδώ,
τότε θα το κάνω και πάλι, τότε θα το κάνω και πάλι,
αλλά υπήρξε μια μικρή βελτιστοποίηση θα μπορούσα να κάνω.
>> Μόλις μετακόμισα εδώ τον αριθμό 1 - Sammy σε αυτή την περίπτωση -
τι δεν πρέπει να κάνω μαζί του στη συνέχεια; >> [Φοιτητής] Αφήστε τον.
Αφήστε τον, έτσι δεν είναι; Τίποτα.
Δεν χρειάζεται να μιλήσουμε ποτέ για Sammy πάλι γιατί αν είχα επιλέξει το μικρότερο στοιχείο
και τον έβαλε εδώ, γιατί ο χρόνος των αποβλήτων που καταλήγουν στο τέλος ολόκληρης της λίστας μου;
Στην επόμενη επανάληψη πραγματικά επιτρέψτε μου να κινείται μόνο με τον αριθμό 2, μόνο για τον αριθμό 3.
Έτσι, στην πραγματικότητα, εγώ δεν κάνει τα πράγματα n n φορές.
Έκανα n πράγματα, τότε n - 1 πράγματα, τότε n - 2 πράγματα, τότε n - 3 πράγματα,
τότε n - 4, τελεία, τελεία, τελεία.
Έχουμε ένα κομμάτι από μια γεωμετρική σειρά, η οποία απλά σημαίνει
είστε προσθέτοντας σταδιακά μικρότερους αριθμούς.
Δεν n + n + n + n, αλλά ν + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Και αυτό που γενικά λειτουργεί έξω για να είναι -
Πάω να χαλάσουν σκάφους μου εδώ μόνο για μια στιγμή -
που πρόκειται να λειτουργήσει έξω για να είναι κάτι σαν n (n - 1) / 2
αν έχουμε ακριβώς το είδος του εμφάνιση στο πίσω μέρος του βιβλίου μαθηματικών όπου έχετε όλα τα εξαπατήσει φύλλα
για τους τύπους.
Εάν θέλετε να προσθέσετε κάτι n + n - 1 + n - 2, λειτουργεί έξω για να είναι κάτι σαν αυτό.
Και αν εμείς ακριβώς το είδος της πολλαπλασιάστε αυτό έξω, που είναι n τετράγωνο μείον n / 2.
Συνέχισα λέγοντας n τετράγωνο, όμως, και αυτό είναι επειδή ήμουν το είδος της λήψης ενός ψυχική συντόμευση
διότι στην πραγματικότητα, n τετράγωνο μείον ν διαιρείται με 2 είναι πράγματι ο πραγματικός αριθμός των βημάτων
ότι ένας αλγόριθμος σαν είδος επιλογής θα πάρουμε αν πραγματικά υπολογίζονται μέχρι
όλες αυτές τις συγκρίσεις και όλα τα μικρά απασχολημένος δουλειά που κάναμε.
Αλλά ειλικρινά, όταν n παίρνει να είναι σαν ένα εκατομμύριο ή ένα δισεκατομμύριο, που στο καλό νοιάζεται
αν κάνετε ένα δισεκατομμύριο τετράγωνο μείον ένα δισεκατομμύριο διαιρείται με το 2;
Ένα δισεκατομμύριο τετράγωνο είναι ένας τεράστιος αριθμός.
Μπορείτε να πάρετε ένα άλλο δις μακριά από αυτό με - n. Δεν είναι μια τέτοια μεγάλη υπόθεση.
Έτσι, το μεγαλύτερο πάρει τους αριθμούς, είναι τα λιγότερο σημαντικά αυτά τα χαμηλότερα διέταξε όρους.
Ποιος νοιάζεται αν διαιρέσετε με το 2, αν μιλάμε για quadrillions τον αριθμό των βημάτων;
>> Έτσι, σε γενικές γραμμές, οι επιστήμονες ηλεκτρονικών υπολογιστών τείνουν να πετάξουν τα πάντα, αλλά το μεγαλύτερο όρος,
και εμείς ακριβώς το είδος του απλοποιήσει τον κόσμο και να πω ότι ο αλγόριθμος
πήρε περίπου τετράγωνο n βήματα. Αυτός είναι ο χρόνος εκτέλεσης ενός αλγορίθμου.
Γι 'αυτό και θα επανέλθουμε σε αυτό σε μια στιγμή με μερικές συγκεκριμένα παραδείγματα,
αλλά για τώρα, αυτό είναι το είδος της διαισθητικής κίνητρο πίσω ακριβώς απλούστευση κόσμο μας
και μιλάμε για τους σημαντικότερους όρους, αντί να εμπλακούμε σε όλα αυτά τα φανταχτερά τους τύπους.
Έτσι, αυτό ήταν το είδος επιλογής, και πήραμε λίγο τυχερός εκεί.
Ας ρίξουμε μια ματιά στο είδος εισαγωγής. Επιτρέψτε μου να προχωρήσει και να αρχίσει αυτό το ένα, καθώς και.
Τώρα παρατηρήσετε το μοτίβο που συμβαίνει είναι λίγο διαφορετικό,
και αρχίσαμε με τυχαίους αριθμούς,
αλλά αν θέλουμε πραγματικά μετράνε τον αριθμό των βημάτων στη χειρότερη περίπτωση,
αν ο κατάλογος που ξεκίνησε εντελώς με τη σωστή σειρά,
θα λάβουν μόνο n μέτρα για την επίτευξη τόσο πολύ.
>> Αλλά εάν η λίστα ήταν πραγματικά προς τα πίσω - για παράδειγμα, σε αυτή την περίπτωση εδώ -
τότε θα παρατηρήσετε πραγματικά πρέπει να κάνουμε πολλή δουλειά σε αυτή την περίπτωση.
Και αυτό πρέπει να το είδος του αισθάνεται να σας αρέσει αυτό είναι το είδος της εργασίας σκληρότερα
για να πάρει εκείνα τα μικρότερα στοιχεία προς τα αριστερά, και αυτό γιατί έχουμε άτυχος.
Η λίστα ταξινομημένο κατά λάθος από την ανάποδη.
Αντίθετα, με την εισαγωγή του είδους, αν μιμούνται ό, τι κάναμε με τους ανθρώπους μας εδώ
ξεκινώντας με ταξινόμηση όλους και στη συνέχεια να ξεκινήσει, είναι ένα πολύ καλό αλγόριθμο, έτσι δεν είναι;
Είναι ήδη, στην πραγματικότητα, με ταξινόμηση.
Ας προσπαθήσουμε να συνοψίσουμε ακριβώς πόσο χρόνο αυτά τα πράγματα που μας
εισάγοντας απλά ένα κομμάτι της αργκό ή συμβολισμό που είναι πραγματικά πολύ απλούστερο
από το είδος του fanciness προτείνει.
Αυτό το πράγμα εδώ, αυτό το μεγάλο O στην οθόνη, είναι ό, τι ένας επιστήμονας υπολογιστών θα χρησιμοποιούν γενικά
για να περιγράψει την χειρότερη περίπτωση χρόνος εκτέλεσης ενός αλγορίθμου.
>> Και πάλι, με χειρότερη περίπτωση, είναι εντελώς εξαρτάται από το πλαίσιο.
Τι εννοούμε με τον όρο χειρότερη περίπτωση εντελώς ποικίλει ανάλογα με το πρόβλημα που μιλάμε.
Αλλά στην περίπτωση της διαλογής, ποιο είναι το χειρότερο δυνατό σενάριο;
Τα πάντα είναι προς τα πίσω, γιατί αισθάνεται σαν αυτό σημαίνει πολλή δουλειά για εμάς.
Έχω καταλήξει σε μερικά από τα αλγόριθμοι που έχουμε δει μέχρι τώρα:
γραμμική αναζήτηση, δυαδική αναζήτηση, όπως με τον τηλεφωνικό κατάλογο ή τα κομμάτια χαρτιού,
τότε είδος bubble sort, ταξινόμηση επιλογή, εισαγωγή και όπως είδαμε με τους ανθρώπους μας,
και στη συνέχεια, 1 άλλο που είναι τελικά πρόκειται να συγχωνευθούν είδος που ονομάζεται.
Έτσι, σε γραμμική αναζήτηση, στη χειρότερη περίπτωση, πόσα βήματα χρειάζονται για να βρείτε τον αριθμό 7
αν υπάρχουν n πόρτες, όπως ο Sean που αντιμετωπίζουν; >> [Φοιτητής] N.
N. Έτσι θα πάμε για να γράψει μεγάλο Ο του n.
Είμαι ακριβώς πρόκειται να συμπληρώσει ορισμένα κενά. Αυτό είναι μόνο ένα πλέγμα κενά.
Όμως, στην καλύτερη περίπτωση με γραμμική αναζήτηση, 7 θα μπορούσε να έχει στην ίδια την αρχή της λίστας,
και Sean μπορεί να έχουν αρχίσει να αναζητούν στην αρχή της λίστας.
Έτσι, αν είστε με τη χρήση γραμμικής αναζήτησης και μόνο έλεγχο αριστερά προς τα δεξιά ή ίσως δεξιά προς τα αριστερά -
ότι είναι ισοδύναμο - στην καλύτερη περίπτωση πόσα βήματα θα μπορούσε γραμμική αναζήτηση,
όπως ο αλγόριθμος του Sean, να λάβει; Μόλις 1 βήμα.
>> Έτσι, Πάω να πω ότι είναι ο συμβολισμός ωμέγα.
Αυτό ακριβώς είναι ωμέγα πρωτεύουσα.
Omega είναι μόνο η σέξι τρόπος για να πούμε καλύτερη περίπτωση διάρκειας.
Έτσι στην καλύτερη περίπτωση ο χρόνος εκτέλεσης είναι ένα μοναδικό στάδιο ή σταθερό αριθμό βημάτων -
1 στην περίπτωση αυτή - αλλά στη χειρότερη περίπτωση, μεγάλες O, είναι πραγματικά n βήματα.
Και αυτό εδώ, θήτα, είμαστε στην πραγματικότητα δεν πρόκειται να δούμε τώρα.
Δεν είναι σχετικό με το συγκεκριμένο παράδειγμα.
Αλλά τώρα ας προσπαθήσουμε δυαδική αναζήτηση.
Στη χειρότερη περίπτωση με δυαδική αναζήτηση, πόσα βήματα είναι αυτό πρόκειται να λάβει για να βρείτε τον αριθμό 7
ή ό, τι ψάχνουμε; >> [Φοιτητής] Σύνδεση n.
Ακόμα πρόκειται να λάβει n log επειδή ακριβώς όπως ο Alex πήρε άτυχος
όταν εμείς πραγματικά εργάστηκαν με το πρόβλημα μεθοδικά
και αυτή δεν βρείτε τον αριθμό 7 μέχρι την τελευταία πόρτα κοίταξε,
αν και, για να είμαστε δίκαιοι, πήρε για να ρίξει μακριά ορισμένες πόρτες κατά μήκος του τρόπου,
δυαδική αναζήτηση στη χειρότερη περίπτωση έχει ένα χρόνο λειτουργίας του log n.
Και πάλι, αυτό μιλάει για αυτό διαίρεση και κατάκτηση.
Αλλά τι γίνεται στην καλύτερη περίπτωση;
Και ο Άλεξ γνώρισε πραγματικά ότι η καλύτερη περίπτωση το δικαίωμα, όταν ήρθε επάνω στη σκηνή.
Πόσα βήματα έκανε ότι λαμβάνουν σε δυαδική αναζήτηση; >> [Φοιτητής] 1.
1, μόνο και μόνο επειδή πήρε τυχερός.
Αλλά αυτό είναι εντάξει, επειδή αναφέρεται σε ωμέγα καλύτερα σενάρια,
καλύτερα τις εισροές περίπτωση, ακόμα κι αν είναι απλά τυχαία τύχη.
>> Τώρα, κι αυτό θα πάμε να ακριβώς το είδος της άδειας κενό για τώρα.
Τι θα λέγατε τώρα είδος φούσκα;
Στη χειρότερη περίπτωση με bubble sort, ο καθένας είναι σε αντίστροφη σειρά,
έτσι πρέπει να κάνουμε πολλά φυσαλίδων.
Αλλά πόσα βήματα είναι ότι πρόκειται να πάρει στη χειρότερη περίπτωση; >> [Φοιτητής] Ν τετράγωνο.
Αυτό ήταν το n τετράγωνο, γιατί αν το καλοσκεφτείς,
αν η λίστα είναι εντελώς προς τα πίσω - 8 είναι πάνω από εδώ, πάνω από 1 είναι εδώ -
ως πράγμα να αρχίσει να φούσκα, ο αριθμός 8 πρόκειται να κινηθεί με αυτό τον τρόπο, με τον τρόπο αυτό,
αυτόν τον τρόπο, με αυτόν τον τρόπο, αλλά πού είναι το νούμερο 7 στη χειρότερη περίπτωση;
Εδώ είναι ακόμα εκεί. Γι 'αυτό και πρέπει να το κάνουμε ξανά και ξανά.
Και αυτό είναι όπου έχουμε n βήματα, τότε n - 1 βήματα, τότε n - 2 βήματα.
Και αν πάρετε τη λέξη μου για αυτό - ότι αν το είδος αυτό πολλαπλασιάζονται,
αυτό είναι περίπου n τετράγωνο στο τέλος με κάποιους άλλους όρους που θα αγνοήσει απλά για τώρα -
τότε στη χειρότερη περίπτωση ταξινόμησης φυσαλίδας είναι ν τετράγωνο, ή να δώσει.
Αλλά τι γίνεται με την καλύτερη περίπτωση με τέτοια φούσκα;
Ποιο είναι το καλύτερο σενάριο; Όλοι οι αριθμοί είναι ήδη ταξινομημένο.
Και ποια ήταν η ευρετική που χρησιμοποιείται, το τέχνασμα που χρησιμοποιείται,
να συνειδητοποιήσει ότι είχα κάνει καμία εργασία και ως εκ τούτου θα μπορούσε να σταματήσει νωρίς;
[Φοιτητής] Δείτε το μια φορά. >> Δείτε το μια φορά. Αλλά αυτό που έκανα κατά μήκος του τρόπου;
Είχα την παρακολούθηση του πόσα swaps που έκανα.
Και κατάλαβα αν δεν έχω κανένα swaps υπολογίζονται στα δάχτυλά μου, τότε έχω κάνει καμία εργασία.
Σίγουρα δεν θα πρέπει να προσπαθήσουμε να κάνουμε καμία δουλειά και πάλι, έτσι μπορώ ακριβώς να σταματήσω.
>> Έτσι, στην καλύτερη περίπτωση του bubble sort, όταν η λίστα είναι ήδη ταξινομημένο,
τι θα λέγατε ότι ο συμβολισμός είναι ωμέγα, η καλύτερη περίπτωση διάρκειας;
Είναι ακριβώς n. Πρέπει να κάνουμε κάποια δουλειά, αλλά δεν έχουμε παρά να κάνουμε αξίας 1 βόλτα του έργου.
Και εδώ θα πάω να αφήσετε κενό αυτό το μέρος.
Και τώρα είδος επιλογής.
Η επιλογή του είδους είχε με το μάδημα το μικρότερο άτομο ξανά και ξανά.
Και τι να πούμε ο χρόνος εκτέλεσης του ότι ήταν;
Αυτό ήταν ν τετράγωνο στη χειρότερη περίπτωση.
Και δυστυχώς, στην καλύτερη περίπτωση είναι επίσης n τετράγωνο
επειδή δεν έχω το είδος του παντογνώστη θέα όλου του κόσμου?
Το μόνο που ξέρω από την πλήρη επανάληψη ότι έχω βρεθεί πράγματι το μικρότερο άτομο.
Έτσι, το είδος είδος της επιλογής χάλια με αυτή την έννοια,
αλλά το θετικό είναι το είδος της διαισθητική.
Είναι αρκετά εύκολο να κωδικοποιήσει έως διότι το μόνο που έχετε να κάνετε είναι να γράψετε ένα ζευγάρι των ένθετων για βρόχους,
κατά κανόνα, που περνά μέσα από ψάχνει για το μικρότερο στοιχείο
και στη συνέχεια τοποθετεί το μικρότερο στοιχείο όπου ανήκει στο τέλος της λίστας.
Έτσι, εδώ υπάρχει πρόκειται να είναι ένα trade-off.
Η ποσότητα του χρόνου που χρειάζεται για να σκεφτούν και να αναπτυχθούν πραγματικά κάτι από τη σύνταξη κώδικα
θα μπορούσε κάλλιστα να πάρει περισσότερο χρόνο, αν θέλετε μια καλύτερη αλγόριθμος και ταχύτερη απόδοση.
>> Αλλά αν πραγματικά ακριβώς το είδος του κώδικα μέχρι κάτι γρήγορο και βρώμικο
και ακριβώς το είδος του να το χαζό δυνατή ιδέα που μπορείτε να σκεφτείτε,
που θα μπορούσε να σας πάρει μερικά λεπτά για να κώδικα, αλλά με μεγάλα σύνολα δεδομένων
αλγόριθμος σας μπορεί να πάρει ώρες για να τρέξει.
Και ακόμα κι εγώ σε μεταπτυχιακό σχολείο θα κάνει μερικές φορές αυτά τα ανταλλάγματα.
Θα ήταν τρεις, ήμουν προσπαθεί να αναλύσει κάποια πολύ μεγάλο σύνολο δεδομένων
που σχετίζονται με την έρευνα για την ασφάλεια που έκανα, και είχε δαπανήσει ούτε 5 λεπτά
μικροαλλαγές το πρόγραμμά μου για να αναλύσει τα δεδομένα και να πάει για ύπνο
ή να περάσουν 8 ώρες να πάρει ακριβώς δεξιά έτσι ώστε να τρέχει αμέσως και να μην πάει για ύπνο.
Και έτσι εκεί είναι το είδος της μια συνειδητή απόφαση.
Λιγότερο χρόνο ανάπτυξης, περισσότερο ύπνο.
Εκ των υστέρων, εγώ κατά πάσα πιθανότητα δεν θα πρέπει να ενθαρρύνουν
όταν ο στόχος εδώ είναι να βελτιστοποιηθεί η ποιότητα του κώδικα,
αλλά επίσης ότι στον πραγματικό κόσμο είναι ένα πολύ λογικό trade-off.
Λιγότερο χρόνο, μικρότερη απόδοση ή το αντίστροφο.
Έτσι, εδώ έχουμε επιτέλους την ευκαιρία να μιλήσουμε για θήτα.
Theta συμβολισμός είναι κάτι που οι επιστήμονες ηλεκτρονικών υπολογιστών μπορεί να φέρει σε συνομιλία
όταν μεγάλες O και ωμέγα τυχαίνει να είναι το ίδιο.
Λέτε θήτα να στείλετε πραγματικά το μήνυμα ότι αυτό είναι ένα είδος δεσμεύεται σφιχτά.
Δεν έχει σημασία αν το σενάριο είναι καλό ή κακό, είναι n τετράγωνο.
Γι 'αυτό ακριβώς δεν έχει σημασία σε αυτές τις ιστορίες εδώ.
Εισαγωγή είδος είναι το τελευταίο εξετάσαμε,
όπου ήμουν εισάγοντας απλώς ο καθένας στο σωστό μέρος.
Στην καλύτερη περίπτωση αυτό που ήταν ο χρόνος εκτέλεσης της εισαγωγής του είδους, όπως το είδαμε εδώ;
[Φοιτητής] Η καλύτερη περίπτωση; >> Η καλύτερη περίπτωση.
>> Ήταν n γιατί στην καλύτερη περίπτωση ταξινομημένο σε όλους,
και Sammy και κανένας άλλος πραγματικά έπρεπε να κινηθεί καθόλου.
Είχαν ήδη σε σωστή θέση τους.
Έτσι ταξινόμηση με εισαγωγή στην καλύτερη περίπτωση είναι, στην περίπτωση αυτή, n.
Όμως, στη χειρότερη περίπτωση είναι το είδος του n στο τετράγωνο. Γιατί;
Αν μου λίστα των ανθρώπων είναι σε αντίστροφη σειρά,
Εγώ για πρώτη φορά με τον αριθμό 8 και θα τον τοποθετήσετε ή την στη σωστή θέση, η οποία είναι ακριβώς εδώ.
Ι το είδος της κίνησης προς την πλευρά. Αυτά τα παιδιά που έχουν υποστεί διαλογή, ή αυτή είναι ταξινομημένο.
Τώρα, όμως, τυχαίνει να βρει ποιος το επόμενο βήμα; >> [Φοιτητής] 7.
7 στην χειρότερη περίπτωση, επειδή είναι σε αντίστροφη σειρά.
>> Έτσι, εδώ είναι 7. Σε περίπτωση που δεν ανήκουν 7; Σίγουρα πίσω μου.
Αλλά τώρα 7 ανήκει στην πραγματικότητα δεν είναι ακριβώς πίσω από μένα, αλλά πίσω από τον αριθμό 8,
έτσι έχω να πω, "Με συγχωρείτε, αριθμός 8, μπορείτε σας παρακαλώ να προχωρήσουμε με αυτόν τον τρόπο
"Για να δημιουργηθεί χώρος για 7;" Τώρα έχω συναντήσει 6.
"Ω, με συγχωρείτε, τον αριθμό 8 και τον αριθμό 7, μπορείτε να μετακινηθείτε για να δημιουργηθεί χώρος για 6;"
Έτσι με άλλα λόγια, με την εισαγωγή του είδους, ακόμη και αν δεν κάνω πολύ κίνηση,
οι άνθρωποι πίσω μου κάνουν πολύ περισσότερη δουλειά, και που πήρε χρόνο να κοστίσει κάποιον.
Είναι πρόκειται να κοστίσει την ώρα του υπολογιστή.
Έτσι, στην περίπτωση της εισαγωγής του είδους που εξακολουθούν να υποφέρουν.
Αν ξεκινήσετε προσθέτοντας τον συνολικό αριθμό των βημάτων, καταλήγουμε να χτυπήσει περίπου n τετράγωνο
επειδή αυτοί οι τύποι πρέπει να δημιουργηθεί χώρος για την ανθρώπινη να εισαχθεί ξανά σε αυτόν τον κατάλογο.
Και έτσι σε αυτή την περίπτωση θήτα είναι απλώς δεν ισχύει για τη συγκεκριμένη ιστορία στο χέρι.
Αυτό είναι όλα ωραία και καλά. Έχουμε αυτά τα 3 διαφορετικοί τρόποι να μιλάμε για το χρόνο λειτουργίας.
Αλλά τι ακριβώς σημαίνει αυτό σε πραγματικούς όρους, αν πραγματικά προσπαθήσει να κωδικοποιήσει έως έναν αλγόριθμο;
>> Επιτρέψτε μου να προτείνω ότι υπάρχει ένα ακόμα καλύτερο αλγόριθμο εκεί έξω
ότι η ίδια έχει κάποια ανταλλάγματα.
Εμείς πάμε για να καλέσετε το είδος συγχώνευσης, και αυτό είναι το είδος του αυτό το μαγικό αλγόριθμο
που λειτουργεί ακριβώς γρηγορότερα με κάποιο τρόπο, και είναι τόσο εύκολο να εκφράσει, τουλάχιστον σε ψευδοκώδικα.
Η εφαρμογή αυτού του είδους συγχώνευσης αλγόριθμος πρόκειται να είναι ως εξής.
Όταν σας δίνεται n στοιχεία - αριθμούς n, n οι άνθρωποι, ό, τι - πρώτα υπάρχει μια λογική ελέγχου.
Αν το n είναι μικρότερο από 2, συγχώνευση είδος σταματά ακριβώς. Επιστρέφει, να το πω έτσι.
Γιατί θα σταματήσει αν το n είναι μικρότερο από το 2; >> [Ακούγεται ανταπόκριση των φοιτητών]
Δεξιά. Και πάλι, το η δεν είναι ο αριθμός στη λίστα, n είναι το μέγεθος του καταλόγου.
Εάν το n είναι μικρότερο από 2, αυτό σημαίνει ότι η λίστα σας είναι είτε 1,
Όπου και αν προφανώς ταξινομημένο αν είναι 1 αριθμός,
ή 0, οπότε δεν υπάρχει τίποτα για να ταξινομήσετε,
γι 'αυτό χρειαζόμαστε αυτό το είδος της υπόθεσης βάσης.
Εάν η λίστα είναι τόσο μικρή που δεν υπάρχει τίποτε άλλο να κάνεις, κυριολεκτικά δεν κάνουν τίποτα. Επιστροφή.
Διαφορετικά ταξινομήσετε το αριστερό μισό των στοιχείων, τότε ταξινομήσετε το δεξί ήμισυ από τα στοιχεία,
μετά τη συγχώνευση τα 2 ημίχρονα ταξινομημένο.
>> Αυτό το είδος του φαίνεται σαν μια μικρή εξαπατήσει το οποίο ρωτάω πώς να ταξινομήσετε τα στοιχεία
και μου λες, "Ταξινομήστε το αριστερό μισό, ταξινομήστε το δεξιό μισό."
Είμαι όπως, «Εντάξει. Πώς μπορείτε να ταξινομήσετε το αριστερό μισό;"
"Ξεχωρίστε το αριστερό μισό του αριστερό μισό, το δικαίωμα ταξινομήσετε μισό του αριστερό μισό, και στη συνέχεια να γίνει."
Είσαι το είδος του κυκλικά τον καθορισμό του τι σημαίνει να ταξινομήσετε,
αλλά αποδεικνύεται ότι είναι πραγματικά λαμπρή σε αυτή την περίπτωση.
Δεν είναι πραγματικά αυτός ο φαύλος κύκλος που δεν τελειώνει ποτέ
επειδή δεν τελειώνει όταν; >> [Φοιτητής] Όταν φθάσει το 1 πράγμα.
Όταν φθάσει το 1 πράγμα.
Έτσι, ακόμα κι αν θα μπορούσε να ξεκινήσει με 8 άτομα και λέω, "Ταξινομήστε το αριστερό ήμισυ των ατόμων αυτών,
αυτά τα 4 άτομα, "τότε λέω,« Πώς μπορείτε να ταξινομήσετε το αριστερό μισό; "
"Λοιπόν, να ταξινομήσετε τις 2 άτομα εδώ." Και τότε θα είστε όπως, «Εντάξει, εντάξει."
"Πώς μπορείτε να ταξινομήσετε το αριστερό μισό από αυτούς τους ανθρώπους;"
"Ακριβώς αυτό ταξινομήσετε 1 άτομο εδώ." Ποια είναι η λαμπρή αποκάλυψη τώρα;
Θα πρέπει να ταξινομήσετε 1 άτομο. Τέλος. Δεν έχω να κάνω οποιαδήποτε εργασία.
Αλλά τώρα έχω να ταξινομήσετε αυτό το πρόσωπο, αλλά είναι ένα μεμονωμένο άτομο, να κάνει τίποτα.
>> Έτσι, η μαγεία είναι προφανώς σε αυτό το τρίτο βήμα: τη συγχώνευση των ταξινομημένο μισά.
Έτσι συγχώνευση είδος παίρνει αυτή την λαμπρή ιδέα ότι, αν σπάσει ένα μεγάλο πρόβλημα κάτω
σε 2 μικρότερα, όμοια σε μέγεθος προβλήματα
και στη συνέχεια, ακριβώς το είδος της κόλλας οι μικρότερες λύσεις μαζί στο τέλος,
Προτείνω ότι μπορούμε να κάνουμε πολλά, πολύ καλύτερα [χτυπώντας ήχο]
από οποιοδήποτε είδος ή είδος επιλογής εισαγωγής.
Έχω πράγματι αγνοώντας ότι για μισή ώρα, αλλά εγώ πραγματικά δεν ξέρω τι συμβαίνει
έξω σήμερα. [Βουητό] [γέλια]
Ας δούμε αν μπορούμε να δούμε αυτό με μια μικρή βοήθεια από τον φίλο μας τον Rob Bowden.
Υπάρχουν 2 μεγάλα βήματα στη διαδικασία της συγχώνευσης είδος.
Κατ 'αρχάς, χωρίζεται συνεχώς τον κατάλογο των κυπέλλων στη μέση
μέχρι να έχουμε ένα σωρό λίστες με μόλις 1 φλιτζάνι σε αυτά.
Μην ανησυχείτε εάν η λίστα περιέχει περιττό αριθμό
και δεν μπορείτε να κάνετε μια απόλυτα καθαρή κοπή μεταξύ τους.
Απλά επιλέξτε αυθαίρετα ποια λίστα να περιλαμβάνει το επιπλέον φλιτζάνι μέσα
Ας χωρίσει τους καταλόγους αυτούς.
Τώρα έχουμε 2 λίστες.
Τώρα έχουμε 4 λίστες.
Τώρα έχουμε 8 λίστες με ένα μόνο φλιτζάνι σε κάθε λίστα.
Έτσι, αυτό είναι όλο για το βήμα 1.
Για το βήμα 2 θα συγχωνευθούν επανειλημμένα ζεύγη λίστες χρησιμοποιώντας τον αλγόριθμο συγχώνευσης μάθαμε πριν.
Συγχώνευση 108 και 15 καταλήγουμε με τον κατάλογο 15, 108.
Συγχώνευση 50 και 4 καταλήγουμε με 4, 50.
Συγχώνευση 8 και 42 καταλήγουμε με 8, 42.
Και τη συγχώνευση 23 και 16 καταλήγουμε με 16, 23.
Τώρα όλες τις λίστες μας είναι το μέγεθος 2.
Παρατηρήστε ότι κάθε ένα από τα 4 καταλόγων ταξινόμηση,
έτσι μπορούμε να αρχίσουμε τη συγχώνευση ζεύγη των καταλόγων και πάλι.
Συγχώνευση 15 και 108 και 4 και 50 παίρνουμε πρώτα το 4, τότε το 15,
τότε το 50, τότε το 108.
Συγχωνευόμενες 8, 42 και 16, 23 παίρνουμε πρώτα το 8, τότε το 16,
τότε το 23, τότε το 42.
Έτσι τώρα έχουμε μόλις 2 καταλόγους μεγέθους 4, καθένα από τα οποία είναι ταξινομημένο.
Έτσι τώρα έχουμε συγχωνεύσει αυτά τα 2 λίστες.
Πρώτα παίρνουμε το 4, τότε παίρνουμε το 8, τότε παίρνουμε το 15
και 16 και 23 και 42 και 50 και 108.
Και τελειώσαμε. Έχουμε τώρα μια ταξινομημένη λίστα.
>> Rob ήταν το είδος της εκμεταλλευόμενοι κάτι που δεν το έχουν πράξει ακόμη.
Προτάθηκε, αλλά εμείς δεν το κάνουμε πραγματικότητα.
Ήταν κάτι φυσικά με τα κύπελλα που προτείνει
ξόδευε κάποια πηγή εκτός από το χρόνο. >> [Φοιτητής] Space. >> Ήταν χώρο.
Το γεγονός ότι είχε αυτό το είδος της δι-επίπεδο τραπέζι όπου είχε χώρο εδώ
και το χώρο κάτω εδώ ήταν πραγματικά πράγμα που σημαίνει ότι είναι με το διπλάσιο χώρο
όπως κάθε αλγορίθμων μας μέχρι στιγμής - είδος εισαγωγής, είδος φούσκα, ή την επιλογή του είδους -
αλλά ήταν μόχλευση αυτή την επιπλέον χώρο για το είδος των πραγμάτων κίνηση εμπρός και πίσω
διατηρώντας παράλληλα τα πράγματα σε τάξη.
Και ακόμα κι αν αισθάνεται σαν να έχεις σε μια ταξινομημένη λίστα, που αισθάνθηκε σαν να πήρε λίγο χρόνο.
Στην πραγματικότητα, αυτό που έκανε ο Rob ήταν ακριβώς αυτός ο αλγόριθμος.
Πήρε πρώτα το πρόβλημα μεγέθους n, διαιρείται το σε ένα αριστερό μισό και το δεξί μισό.
Αυτό είναι όταν μετακόμισε τα κύπελλα. Στη συνέχεια, επανέλαβε ότι η διαδικασία.
Χώρισε 4 σε 2 σετ από 2 εδώ και εδώ.
Στη συνέχεια, επανέλαβε ότι η διαδικασία χωρίζεται και 2 σε 2 σετ από 1 για καθένα από αυτά τα διάφορα κύπελλα.
Και αυτό είναι όπου η λαμπρή ευκαιρία.
Σε εκείνο το σημείο στην ιστορία, ο Rob είχε 8 λίστες του μεγέθους 1,
όλα από τα οποία είχαν ήδη ταξινόμηση.
>> Και τότε τι έκανε προχωρήσει να κάνει;
Ζεύγη πήρε αυτή την ταξινομημένη λίστα και αυτή την ταξινομημένη λίστα και συγχώνευση τους.
Στη συνέχεια, πήρε το ένα και συγχώνευσε τους, τότε αυτό το ένα και συγχώνευση τους,
τότε αυτό και τους συγχωνεύονται.
Και τότε τι έκανε το επόμενο βήμα;
Στη συνέχεια εκ νέου συγχώνευσε τις μεγαλύτερες λίστες και στη συνέχεια εκ νέου συγχώνευσε τις μεγαλύτερες λίστες.
Και αν νομίζετε ότι για αυτό ακριβώς διαισθητικά για τώρα, τι πραγματικά κάνει ο ίδιος;
Ήταν διαιρώντας το πρόβλημα σε ένα δεύτερο, κατά το ήμισυ, σε ένα δεύτερο, σε ένα δεύτερο
για να πάρει αυτά τα μικρά σούπερ λίστες.
Τότε ήταν το είδος του συνδυασμού διπλό, διπλό, διπλό, διπλό.
Έτσι έκανε το διπλάσιο έργο όπως έχουμε δει μέχρι στιγμής
με οτιδήποτε συνεπάγεται διαίρει και βασίλευε, αλλά δεν είναι μεγάλη υπόθεση.
Δύο φορές όσο η εργασία δεν είναι μια τέτοια μεγάλη υπόθεση. Είναι απλά ένα σταθερό παράγοντα.
Και σαν έκφραση αριθμητική μας πριν, είμαι απλώς πρόκειται να περάσουν από σταθερούς παράγοντες
όπως φορές 2. Ποιος νοιάζεται; Αν είναι 2 δισεκατομμύρια φορές 2, που είναι ακόμα πολλά βήματα.
Έτσι, αυτή η συγχώνευση βήμα φαίνεται να είναι η βασική εικόνα.
Ας δούμε αυτό ακριβώς αριθμητικά πριν - Ω, αυτό δεν είναι για να συνεχιστεί ακόμα.
Ας δούμε αυτό μόνο αριθμητικά πραγματικά να δούμε πώς αυτό παίζει έξω.
Αυτό είναι ως επί το πλείστον μόνο κίνηση ενός μικρού φτωχού.
Ας προτείνουν αυτό.
Ο χρόνος εκτέλεσης του είδους συγχώνευση - χρειαζόμαστε μόνο έναν τρόπο να μιλάμε γι 'αυτό.
Αυτό δεν είναι μαθηματικά? Αυτό είναι ακριβώς το είδος του τρόπο συνοπτικό της εκφραζόμαστε.
Έτσι Τ αντιπροσωπεύει το χρόνο και ν αντιπροσωπεύει ό, τι; >> [Φοιτητής] Το μέγεθος του -
>> [Malan] Το μέγεθος του προβλήματος, ο αριθμός των ανθρώπων.
Έτσι είμαι υποστηρίζοντας ότι ο χρόνος εκτέλεσης να ταξινομήσετε n άνθρωποι πρόκειται να είναι 0 χρονικό διάστημα
αν το n είναι μικρότερο από 2, γιατί αν έχετε 1 φλιτζάνι ή δεν κύπελλα, δεν έχετε τίποτα να ταξινομήσετε.
Αλλά γενικότερα, Πάω να προτείνουν ότι ο χρόνος εκτέλεσης να ταξινομήσετε n στοιχεία
πρόκειται να είναι ο χρόνος που χρειάζεται για να ταξινομήσει το αριστερό μισό συν το δεξί μισό
συν - τι είναι αυτή η πρόσθετη + n; >> [Φοιτητής] είδος συγχώνευσης.
[Malan] Είναι πραγματικά συγχώνευση, γιατί αν έχετε n / 2 στοιχεία εδώ
και έχετε n / 2 στοιχεία εδώ, πόσος χρόνος χρειάζεται για να τους συγχωνεύσω;
Ακριβώς όπως ο Rob, θα πρέπει να κόβω το ένα πάνω εδώ, ίσως κόβω εδώ,
κόβω εδώ, κόβω εδώ, κόβω εδώ.
Θα πρέπει να αγγίξει κάθε ένα από τα φλιτζάνια φορά.
Και αν υπάρχει 4 φλιτζάνια συν 4 κύπελλα, αυτό είναι 8 φλιτζάνια
ή, γενικότερα, 8 κύπελλα n.
Έτσι, η συγχώνευση βήμα μπορούμε να εκφράσουμε ως n,
και αυτό περιλαμβάνει κυριολεκτικά τον αριθμό των φορών που ο Rob φυσικά άγγιξε
ένα από αυτά τα φελιζόλ κύπελλα.
Ας κάνουμε τώρα μια αυθαίρετη παράδειγμα.
Αν υπάρχει 16 φλυτζάνια, τι είναι ο χρόνος εκτέλεσης της ταξινόμησης, χρησιμοποιώντας τον αλγόριθμο του Rob, 16 κύπελλα;
Είναι 2 φορές την ποσότητα του χρόνου που χρειάζεται για να γκρουπάρετε 8 φλιτζάνια
επειδή έχουμε 8 φλιτζάνια εδώ, 8 φλιτζάνια εδώ.
Δεν ξέρω πόσο καιρό που λαμβάνει, έτσι ώστε να είμαστε γενίκευση ως T προς το παρόν.
Ποιος ξέρει τι είναι;
Αλλά τώρα μπορώ να ταξινομήσετε του αναδρομικά ή κατ 'επανάληψη ζητήσει από την ίδια ερώτηση.
Πόσο χρόνο χρειάζεται για να ταξινομήσετε 8 ποτήρια;
8 φλιτζάνια Πάω να πω παίρνει την ποσότητα του χρόνου που χρειάζεται για να ταξινομήσετε 4 φλιτζάνια συν 4 φλιτζάνια,
τότε μαζί τους συγχώνευση.
Πρόστιμο. Είμαστε εμπλακούμε σε έναν κύκλο ήδη. Πόσο καιρό παίρνει για να ταξινομήσετε 4 φλιτζάνια;
Ο χρόνος που χρειάζεται για να ταξινομήσετε 4 φλιτζάνια είναι 2 φλιτζάνια συν 2 φλιτζάνια διαλογής καθώς και η διαδικασία συγχώνευσης.
Πρόστιμο. Πόσο καιρό παίρνει για να ταξινομήσετε 2 φλιτζάνια;
2 φλυτζάνια είναι η ποσότητα του χρόνου που χρειάζεται για να γκρουπάρετε 1 φλυτζάνι συν το χρόνο που χρειάζεται για να γκρουπάρετε άλλο ένα φλιτζάνι
συν το ποσό του χρόνου που απαιτείται για τη συγχώνευση, η οποία είναι μόλις 2.
>> Πρόστιμο. Τελευταία ερώτηση. Πόσο καιρό παίρνει για να ταξινομήσετε 1 φλιτζάνι;
Εδώ είναι η βασική περίπτωση είχαμε προβλέψει ότι είχαμε χτυπήσει νωρίτερα.
Το γεγονός ότι δεν παίρνει καμία απολύτως εργασία για να ταξινομήσετε το μικρότερο από τα προβλήματα
σημαίνει ότι τώρα, το είδος του στυλ σχολείο βαθμού,
μπορούμε απλά να αρχίσει να συνδέσετε αυτούς τους αριθμούς πίσω μέσα
Τώρα ξέρουμε τι Τ 1 είναι, ώστε να μπορώ να συνδέσετε σε 0 για T από 1.
Αυτό θα μου δώσει την απάντηση του Τ 2, την οποία στη συνέχεια, να συνδέσετε ψηλά.
Αυτό θα μου δώσει T 4, το οποίο μπορώ να συνδέσετε ψηλά.
Αυτό θα μου δώσει T της 8, το οποίο μπορώ να συνδέσετε ψηλά.
Και αν εγώ πραγματικά να κάνουμε ότι μαθηματικά, συνδέοντας αυτές τις απαντήσεις,
Στη συνέχεια να πάρει T των 16 είναι 64.
Και τι κάνει 64 αντιπροσωπεύουν;
Αν Τ είναι 16, ναι, είναι 16 φορές 4.
Γι 'αυτό και ισχυρίζονται τώρα ότι ο χρόνος εκτέλεσης του αυτό το πράγμα που ονομάζεται συγχώνευση είδος -
και αυτό πρόκειται να είναι το πιο μοντέρνο από αυτά που έχουμε δει μέχρι στιγμής -
πρόκειται να ονομάζεται n log n
γιατί πόσες φορές μπορεί να χωριστεί Rob ένα σωρό φλιτζάνια στο ημίχρονο; Σύνδεση n.
Είναι το ίδιο με το παράδειγμα του τηλεφωνικού καταλόγου, είναι το ίδιο με το αυτο-μέτρηση παράδειγμα.
>> Πόσες φορές μπορεί να σας χωρίσει κάτι στη μέση;
Ωστόσο, υπάρχει αυτή η συγχώνευση βήμα.
Ίσως χρειαστεί να διαιρέσει τα κύπελλα σε μισό ξανά και ξανά και ξανά,
αλλά κάθε φορά που θα πάμε να πρέπει να συγχωνευθούν.
Και είπαμε νωρίτερα ότι η συγχώνευση n φλιτζάνια παίρνει n βήματα
γιατί πρέπει να κόβω ένα κύπελλο, κόβω ένα κύπελλο, και θα πρέπει να αγγίξει κάθε φλιτζάνι μια φορά,
ακριβώς όπως έκανε ο Rob.
Έτσι, αν κάνουμε κάτι log n φορές και κάνουμε τα πράγματα ν για κάθε μία από αυτές τις επαναλήψεις,
κάθε μία από αυτές halvings, έχουμε n log n φορές.
Έτσι, αν συνδέσετε το 16 σε αυτό το παράδειγμα, 16 φορές συνδεθείτε από 16 -
Δεν χρειάζεται να ανησυχείτε σχετικά με το γιατί αυτή είναι η περίπτωση για τώρα γιατί δεν έχω επιστήσει την βάση -
αλλά καταγραφής της βάσης 2 από 16 είναι 4, 16 φορές 4 είναι 64.
Αλλά αντίθετα, αν είχαμε χρησιμοποιήσει είδος φούσκα ή επιλογή είδος ή είδος εισαγωγής με 16 αριθμούς,
τι θα ο χρόνος εκτέλεσης ήταν αν n είναι 16;
Θα είναι 16 τετράγωνο, το οποίο είναι 256, το οποίο ακόμα και αν δεν έχουν ακολουθήσει αρκετά όλα τα μαθηματικά,
256 είναι μεγαλύτερο από 64. Αυτό είναι πραγματικά το μαγικό πακέτο εδώ.
Και συνειδητοποιούν ότι εργάζονται με αυτό σε μικρότερα παραδείγματα, όπως θα σε PSET
καθιστά πολύ πιο έξυπνο.
Αλλά τι πραγματικά σημαίνει αυτό όσον αφορά την αίσθηση αυτού του αλγορίθμου είναι η εξής:
Αν θέλουμε πραγματικά να κοιτάξουμε στο είδος συγχώνευσης εδώ - επιτρέψτε μου να το τραβήξει επάνω σε αυτό το παράθυρο εδώ -
αυτό είναι ένα ελαφρώς διαφορετικό παράδειγμα όπου έχουμε όλων των 3 αυτών των αλγορίθμων -
φούσκα, επιλογή, και η συγχώνευση - ακριβώς δίπλα-δίπλα.
>> Έχουν όλα ξεκίνησαν με τυχαία μπαρ, και αυτό είναι καλό.
Κανείς δεν έχει ένα βασικό πλεονέκτημα έναντι του άλλου.
Πάω να σε μια στιγμή κλικ σε κάθε από αυτά τα κινούμενα σχέδια - Έναρξη, Start, Start -
όσο πιο γρήγορα μπορώ έτσι ώστε, χονδρικά, όλες ξεκινούν την ίδια στιγμή,
και ας αναλογιστούμε ότι η χειρότερη περίπτωση είδος φούσκα που τρέχει ο χρόνος είναι ό, τι; >> [Φοιτητής] Ν τετράγωνο.
Ν τετράγωνο. Χειρότερη περίπτωση επιλογής του είδους που τρέχει ο χρόνος είναι; Ν τετράγωνο.
Και συγχώνευση είδος είναι προφανώς - ακόμα και αν δεν ακολουθούν αρκετά όλα τα μαθηματικά τώρα,
αυτό θα γίνει πολύ πιο έξυπνο την πάροδο του χρόνου - είναι, διεκδικούμε, n log n φορές.
Και επειδή log n είναι αυστηρά λιγότερο από μια φορά n έχουμε μεγάλους αριθμούς,
n φορές log n είναι μικρότερο από n φορές n ή n τετράγωνο.
Έτσι, αυτό που νιώθεις πραγματικά να είναι μια καλύτερη αλγόριθμος από την άποψη της διάρκειας,
n log n φορές σε αντίθεση με n τετράγωνο; Εδώ πάμε. Κάντε κλικ, κλικ, κλικ.
>> Αυτό είναι το τι σημαίνει να χρησιμοποιήσετε κάτι σαν είδος συγχώνευσης.
Έχουμε μια στιγμή. Ας δούμε τι συμβαίνει εδώ.
[Συγκρατημένα γέλια] των οποίων τα χρήματα είναι είδος φούσκα;
Εξαρτάται μάλλον από την είσοδο μερικές φορές.
Ας δούμε.
Έλα. Αισθάνεται σαν να είναι το χαμένο έδαφος. >> [Φοιτητής] Go, είδος φούσκα!
[Φοιτητές μουρμουρίζοντας]
[Malan] Ναι, ναι.
[Φοιτητές μουρμουρίζοντας] Πάμε, πάμε, πάμε!
[Όλα επευφημίες] [χειροκροτήματα]
Έτσι, τώρα τελευταία με 1, τελική demo, αν και είναι λίγο δύσκολο να τυλίξουν το μυαλό σας γύρω από τα μαθηματικά
ή το είδος της απεικόνισης εκεί, μπορείτε να ακούσετε πραγματικά τις ταχύτητες
των διαφορετικών αλγορίθμων διαφορετικά.
Πρόκειται για μια κίνηση που κάποιος ότι στην πραγματικότητα συνεργάτες ακούγεται
με τη διαδικασία της swapping και το ύψος των ράβδων.
Όπως θα δούμε εδώ, υπάρχει μερικές ακόμα αλγορίθμων ταξινόμησης εκεί έξω ότι οι λαοί έχουν σκεφτεί.
Το πρώτο θα είναι είδος εισαγωγής, και αυτό θα πετάξει μέσα
και να σας δώσει μια ακουστική αίσθηση για το πώς αυτά τα διάφορα εργασία αλγορίθμων.
Εδώ είναι είδος εισαγωγής.
[Ηλεκτρονικό μπιπ]
[Malan] Bubble sort.
[Γρηγορότερα ηλεκτρονικό μπιπ]
[Malan] είδος επιλογής.
[Γρηγορότερα ηλεκτρονικό μπιπ]
[Malan] Συγχώνευση είδος.
[Ηλεκτρονικό μπιπ]
[Χτυπάει επιβραδύνει] [γέλια]
[Malan] Gnome είδος.
[Ηλεκτρονικό μπιπ]
>> Αυτό είναι CS50. Θα σας δούμε την επόμενη εβδομάδα. [Χειροκροτήματα και επευφημίες]
>> [CS50.TV]