1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Παίζει μουσική] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. Malan: Αυτό είναι CS50. 5 00:00:12,550 --> 00:00:14,612 Και αυτό είναι η αρχή των τριών εβδομάδων. 6 00:00:14,612 --> 00:00:16,820 Έτσι έχουμε ένα πολύ συναρπαστικό τα πράγματα να καλύψουμε σήμερα. 7 00:00:16,820 --> 00:00:20,160 Πολλές ευκαιρίες για εθελοντές επάνω στη σκηνή. 8 00:00:20,160 --> 00:00:22,780 Και τελικά, σήμερα είναι όχι για κωδικό καθόλου. 9 00:00:22,780 --> 00:00:24,820 Αλλά είναι για τις ιδέες, και πρόκειται για αλγορίθμους, 10 00:00:24,820 --> 00:00:28,420 και μάλιστα φέρνοντας πίσω μερικά από τα τα διδάγματα που αντλήθηκαν από την εβδομάδα μηδέν, 11 00:00:28,420 --> 00:00:31,910 όπου ανάκληση, εμείς εισήγαγε αυτό το τερατούργημα. 12 00:00:31,910 --> 00:00:33,880 Και δανεισμού έμπνευση από αυτό, για να ξεκινήσει 13 00:00:33,880 --> 00:00:36,879 να λύσει ολοένα και πιο πολύπλοκα αλγοριθμικά προβλήματα. 14 00:00:36,879 --> 00:00:38,420 Αλλά πρώτα, μερικές ανακοινώσεις. 15 00:00:38,420 --> 00:00:42,020 Έτσι, ένα, αν θέλετε να γίνετε μέλος Το προσωπικό και τους συμμαθητές CS50 κατά το γεύμα 16 00:00:42,020 --> 00:00:44,670 αυτή την Παρασκευή, τόσο εδώ όσο και στην Cambridge, και στο New Haven, 17 00:00:44,670 --> 00:00:48,060 παρακαλώ επισκεφθείτε την μαθήματος ιστοσελίδα, όπου μπορείτε να βρείτε μια διεύθυνση URL. 18 00:00:48,060 --> 00:00:50,390 Διάλεξη αυτή την Τετάρτη θα Δεν είναι εδώ ο Sanders. 19 00:00:50,390 --> 00:00:53,610 Θα είναι μόνο online, έτσι συντονιστείτε στην ιστοσελίδα του CS50, 20 00:00:53,610 --> 00:00:55,850 είτε εδώ στο Κέιμπριτζ ή New Haven, καθώς και. 21 00:00:55,850 --> 00:00:58,110 >> Και τότε το πρόβλημα που δύο είναι ήδη στα χέρια σας. 22 00:00:58,110 --> 00:01:03,067 Εάν δεν έχετε καταδυθεί ακόμα, επιτρέψτε μου να προσφέρει την έντονα διατυπωμένη πρόταση 23 00:01:03,067 --> 00:01:05,150 ότι, ειδικά τώρα, όπως το πρόβλημα θέτει εκ των προτέρων, 24 00:01:05,150 --> 00:01:08,669 αν πραγματικά θέλουμε να ξεκινήσουμε τώρα, εάν δεν ανακατεύομαι λίγο για το Σαββατοκύριακο ή πριν 25 00:01:08,669 --> 00:01:10,710 κατά την πρώτη τους βγαίνουν Παρασκευή, γιατί θα 26 00:01:10,710 --> 00:01:14,380 διαπιστώνουν ότι δεν είναι κατ 'ανάγκην επιμηκύνεται ή πιο προκλητική ανά 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Νομίζω ότι θα βρείτε ότι, σε Γενικά, τείνουν να λάβουν περίπου 29 00:01:17,575 --> 00:01:18,892 περίπου ίδιο χρονικό διάστημα. 30 00:01:18,892 --> 00:01:20,850 Αλλά αυτό εξαρτάται ασφαλώς για το μαθητή, και 31 00:01:20,850 --> 00:01:22,880 εξαρτάται από τη νοοτροπία με την οποία μπορείτε να την προσεγγίσουμε. 32 00:01:22,880 --> 00:01:24,910 Αλλά πάντα, θα πάμε να οδηγεί σε κάποιο τοίχο, 33 00:01:24,910 --> 00:01:26,350 και θα πάμε για να χτυπήσει κάποια bug, και είστε ακριβώς 34 00:01:26,350 --> 00:01:27,950 δεν πρόκειται να είναι σε θέση να ξεπεράσω κάποια στιγμή. 35 00:01:27,950 --> 00:01:31,380 Και είναι εξαιρετικά πολύτιμη για να είναι σε θέση να βήμα μακριά, να επιστρέψει την επόμενη μέρα, 36 00:01:31,380 --> 00:01:35,286 πάει στο γραφείο ώρες, μετά σε CS50 Συζήτηση ή τα παρόμοια, για να πάρει πραγματικά αποκλεισμένο. 37 00:01:35,286 --> 00:01:36,160 Έτσι κρατήστε αυτό κατά νου. 38 00:01:36,160 --> 00:01:40,830 Έναρξη το νωρίτερο δυνατό είναι το καλύτερο πράγμα που μπορείτε να κάνετε. 39 00:01:40,830 --> 00:01:44,160 Έτσι, εδώ είναι όπου ξεκινήσαμε η τάξη, πάνω στην εβδομάδα μηδέν. 40 00:01:44,160 --> 00:01:47,441 Και μπορούμε να πάρουμε έναν εθελοντή εδώ για να με βοηθήσει να βρω μικρόφωνα; 41 00:01:47,441 --> 00:01:47,940 ΕΝΤΆΞΕΙ. 42 00:01:47,940 --> 00:01:48,900 Όρθιος ήδη. 43 00:01:48,900 --> 00:01:50,080 Έλα επάνω. 44 00:01:50,080 --> 00:01:53,707 Υποθέτω ότι αυτό είναι το πώς πρόκειται να λειτουργήσει. 45 00:01:53,707 --> 00:01:54,415 Ποιο είναι το όνομά σου? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 David J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Έλα επάνω. 49 00:01:57,910 --> 00:01:58,619 Χάρηκα για τη γνωριμία. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Χαίρω πολύ. 51 00:01:59,910 --> 00:02:02,772 David J. Malan: Και ήσουν εδώ μαζί μας στην εβδομάδα μηδέν, φυσικά. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: ήμουν. 53 00:02:03,028 --> 00:02:03,160 Ήμουν. 54 00:02:03,160 --> 00:02:05,868 >> David J. Malan: Έτσι θα μπορούσε να πάτε μπροστά και να βρει για μας ο Mike Smith, 55 00:02:05,868 --> 00:02:08,639 όσο πιο γρήγορα μπορείτε; 56 00:02:08,639 --> 00:02:10,639 Όσο πιο γρήγορα μπορείτε. 57 00:02:10,639 --> 00:02:13,756 Κυριολεκτικά σχίσιμο του προβλήματος στη μέση, όπως το χρειάζεστε. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 David J. Malan: Κυριολεκτικά σχίσιμο του προβλήματος στο μισό. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Αχ. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Πολύ καλά. 64 00:02:23,300 --> 00:02:23,700 >> David J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Καλή. 66 00:02:24,200 --> 00:02:24,701 Ευχαριστώ. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Πολύ καλή. 68 00:02:25,700 --> 00:02:26,210 ΕΝΤΆΞΕΙ. 69 00:02:26,210 --> 00:02:27,610 >> David J. Malan: Και έτσι τώρα, έχετε μειώνονται 70 00:02:27,610 --> 00:02:29,320 στο μισό του μεγέθους του προβλήματος. 71 00:02:29,320 --> 00:02:31,267 Τώρα, είμαστε κάτω σε ένα τρίμηνο. 72 00:02:31,267 --> 00:02:33,475 Είσαι δίνοντας προσοχή στην ποια πλευρά είμαστε κρατώντας; 73 00:02:33,475 --> 00:02:34,405 >> [Γέλια] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ναι, έχω think-- 75 00:02:35,970 --> 00:02:37,594 >> David J. Malan: Ποια ενότητα είμαστε μέσα; 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Εξατμίσεις, έτσι. 77 00:02:39,150 --> 00:02:39,941 >> David J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Αλλά ο Mike Smith, ο οποίος θα να είναι μετά Εξατμίσεις. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Γέλια] 81 00:02:48,180 --> 00:02:48,742 >> Εντάξει. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Όταν ψάχνουμε; 83 00:02:50,200 --> 00:02:52,049 David J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 David J. Malan: Τώρα, είμαστε σε χειρουργική. 86 00:02:54,760 --> 00:02:57,840 Τώρα, οι γιατροί. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- ας πάει με το πραγματικό. 89 00:02:59,856 --> 00:03:00,370 Ρεάλ. 90 00:03:00,370 --> 00:03:00,970 >> David J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 ΕΝΤΆΞΕΙ. 92 00:03:01,470 --> 00:03:03,700 Αν χρειάζεστε Ρεάλ. 93 00:03:03,700 --> 00:03:05,250 Τώρα, προς ποια κατεύθυνση είναι ο Mike Smith; 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Με αυτό τον τρόπο. 95 00:03:06,250 --> 00:03:07,333 >> David J. Malan: Ποιος ο δρόμος; 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Περιμένετε. 97 00:03:08,240 --> 00:03:08,790 Μ is-- σωστά; 98 00:03:08,790 --> 00:03:09,110 Ξεκινήσαμε with-- 99 00:03:09,110 --> 00:03:10,090 >> David J. Malan: Ναι. 100 00:03:10,090 --> 00:03:10,650 Είναι αριστερά. 101 00:03:10,650 --> 00:03:11,430 Το δικαιωμα σου. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ναι. 103 00:03:11,710 --> 00:03:13,126 >> David J. Malan: Λοιπόν Μάικ εδώ. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Τι; 105 00:03:13,990 --> 00:03:14,665 >> [Γέλια] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Κακό παράδειγμα, παιδιά. 108 00:03:18,330 --> 00:03:18,830 Λυπάμαι. 109 00:03:18,830 --> 00:03:21,610 David J. Malan: Αυτό θα διδάξει μπορείτε να άλμα από την καρέκλα σας. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Αχ. 111 00:03:22,318 --> 00:03:22,890 Ω. 112 00:03:22,890 --> 00:03:23,390 Σε έπιασα. 113 00:03:23,390 --> 00:03:24,670 Σε έπιασα. 114 00:03:24,670 --> 00:03:25,170 Ω. 115 00:03:25,170 --> 00:03:25,669 Ω. 116 00:03:25,669 --> 00:03:26,812 Αυτό is-- Εντάξει, έχεις. 117 00:03:26,812 --> 00:03:27,520 Σμιθ εδώ; 118 00:03:27,520 --> 00:03:28,894 >> David J. Malan: Smith, σας ευχαριστώ. 119 00:03:28,894 --> 00:03:30,535 Γι 'αυτό θα συνεχίσει να αναζητά μέχρι Σμιθ; 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ω, ναι. 121 00:03:30,790 --> 00:03:31,340 ΟΧΙ ΟΧΙ ΟΧΙ. 122 00:03:31,340 --> 00:03:31,600 Ωχ όχι. 123 00:03:31,600 --> 00:03:31,940 Αυτο ειναι δικο μου. 124 00:03:31,940 --> 00:03:32,580 >> David J. Malan: Ω, έχεις Σμιθ. 125 00:03:32,580 --> 00:03:33,415 ΕΝΤΆΞΕΙ. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ναι, έχω Smith πήρε ακριβώς εδώ. 127 00:03:34,040 --> 00:03:34,700 Συγγνώμη, παιδιά. 128 00:03:34,700 --> 00:03:35,860 Νόμιζα ότι θα Michael-- έψαχναν για τον Michael. 129 00:03:35,860 --> 00:03:36,550 Λυπάμαι. 130 00:03:36,550 --> 00:03:37,550 >> David J. Malan: Είναι εντάξει. 131 00:03:37,550 --> 00:03:39,950 Εντάξει, τώρα είμαστε σε Paccini και Υιοί. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini και γιους. 133 00:03:41,242 --> 00:03:43,158 David J. Malan: Μόνο εσείς και εγώ είμαστε μέσα σε αυτό. 134 00:03:43,158 --> 00:03:44,050 ΕΝΤΆΞΕΙ. 135 00:03:44,050 --> 00:03:45,130 Βρείτε μας Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Σμιθ. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> David J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Είμαστε στην έρευνα για τα σκουπίδια. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Χάλια. 141 00:03:48,644 --> 00:03:50,096 Ω. 142 00:03:50,096 --> 00:03:52,480 Αυτό πρόκειται να πάρει λίγο χρόνο. 143 00:03:52,480 --> 00:03:54,340 >> [Γέλια] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 David J. Malan: Παπούτσια. 146 00:03:56,720 --> 00:03:58,080 Είμαστε στα παπούτσια. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Τώρα είμαστε gonna-- 148 00:04:00,210 --> 00:04:01,105 >> David J. Malan: Νίκαια. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Γέλια] 151 00:04:03,620 --> 00:04:05,440 Ω, αυτό είναι μεγάλη. 152 00:04:05,440 --> 00:04:06,910 [Γέλια] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> David J. Malan: Είναι εντάξει. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Ω, αυτό είναι καλό. 156 00:04:11,365 --> 00:04:14,425 Δεν νομίζω ότι θα πάω να έχουν ΠΣΑΤ φίλοι μετά από αυτό. 157 00:04:14,425 --> 00:04:15,300 David J. Malan: Καλή. 158 00:04:15,300 --> 00:04:16,078 Σπόρτινγκ. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Εμ, Λ, Μ, Ν, Ο, Π 161 00:04:18,668 --> 00:04:19,459 David J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Ας δάκρυ αυτό στο μισό. 163 00:04:21,600 --> 00:04:22,270 Είναι εντάξει. 164 00:04:22,270 --> 00:04:25,606 Αυτό τελειώνει καλά ούτως ή άλλως, γιατί ο Mike Smith δεν θα είναι στις κίτρινες σελίδες. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> David J. Malan: Όχι, είναι εντάξει. 167 00:04:27,140 --> 00:04:28,930 Αλλά ας προσποιούνται όπως αυτός είναι σε αυτή τη σελίδα. 168 00:04:28,930 --> 00:04:33,260 Μέχρι τώρα, έχετε αποσβεστούν το πρόβλημα κάτω σε μία σελίδα, και βρήκαμε Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Ζητωκραυγάζει] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Εντάξει ευχαριστώ. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 ΕΝΤΆΞΕΙ. 174 00:04:41,200 --> 00:04:43,646 Αυτό ήταν εξαιρετικό. 175 00:04:43,646 --> 00:04:45,954 Αλλά ακόμα πιο γρήγορα ήταν από τη γραμμική αναζήτηση, 176 00:04:45,954 --> 00:04:47,870 όπου θα ξεκινούν από το αρχή του βιβλίου, 177 00:04:47,870 --> 00:04:51,210 και κινούμαστε δρόμο μας από αριστερά προς τα δεξιά, τελικά αναζητούν Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Και έτσι, αν ο τηλεφωνικός κατάλογος είχε ίσως 1.000 σελίδες, 179 00:04:53,540 --> 00:04:56,300 ίσως θα έχουν λάβει μας 10 ή έτσι τα δάκρυα της σελίδας. 180 00:04:56,300 --> 00:04:59,380 >> Αλλά μπορεί να έχετε μόχλευση άγγιξε μια υπόθεση 181 00:04:59,380 --> 00:05:03,602 κατά τη διάρκεια όλα αυτά, πράγμα που σημαίνει ότι το βιβλίο τηλέφωνο εκ των προτέρων ήταν αυτό; 182 00:05:03,602 --> 00:05:04,310 Κοινό: Ταξινόμηση. 183 00:05:04,310 --> 00:05:05,000 David J. Malan: Είναι ταξινομημένο. 184 00:05:05,000 --> 00:05:05,160 Σωστά; 185 00:05:05,160 --> 00:05:07,909 Είναι ταξινομημένα αλφαβητικά, έτσι ότι όλα αυτά τα ονόματα και τους αριθμούς 186 00:05:07,909 --> 00:05:11,230 κατατάσσονται από το Α έως το Ζ, καθώς και με αλφαβητική σειρά στο μεταξύ. 187 00:05:11,230 --> 00:05:13,100 Αλλά σήμερα, μπορούμε τώρα να ζητήσει το ερώτημα, καθώς, 188 00:05:13,100 --> 00:05:16,170 πώς έκανε Verizon ή το τηλέφωνο Η εταιρεία θα μπει σε αυτή την κατάσταση; 189 00:05:16,170 --> 00:05:19,560 >> Επειδή είναι ένα πράγμα για τη μόχλευση η υπόθεση αυτή, και ως εκ τούτου, 190 00:05:19,560 --> 00:05:22,570 λύσει ένα πρόβλημα με ένα αλγόριθμος πιο αποτελεσματικά. 191 00:05:22,570 --> 00:05:24,900 Αλλά δεν μπορούμε ποτέ πραγματικά Έγινε στην εβδομάδα μηδέν, και, 192 00:05:24,900 --> 00:05:27,790 πόσο κόστισε Verizon ή κάποιος άλλος 193 00:05:27,790 --> 00:05:29,620 για να πάρει αυτό το βιβλίο τηλέφωνο σε ταξινομημένη σειρά; 194 00:05:29,620 --> 00:05:29,780 >> Σωστά; 195 00:05:29,780 --> 00:05:31,529 Δεν έχει σημασία αν κοιτώντας ψηλά Mike Smith 196 00:05:31,529 --> 00:05:35,190 είναι εξαιρετικά γρήγορη, αν έχετε ένα παίρνει χρόνο για να ταξινομήσετε τις σελίδες αρχικά. 197 00:05:35,190 --> 00:05:35,690 Σωστά; 198 00:05:35,690 --> 00:05:38,620 Θα μπορούσαμε απλώς να κοσκινίσει μέσα από μια τυχαιοποιημένη τηλεφωνικό κατάλογο, 199 00:05:38,620 --> 00:05:40,690 αν πρόκειται να είναι σούπερ ακριβό για να το λύσουμε. 200 00:05:40,690 --> 00:05:42,350 Έτσι, αν θέλουμε να έχουμε ένα άλλο εθελοντή. 201 00:05:42,350 --> 00:05:46,350 Ας ρίξουμε μια ματιά εδώ στο πώς μπορούμε might-- έλα up-- πώς 202 00:05:46,350 --> 00:05:48,100 θα μπορούσαμε να πάμε για τη διαλογή αυτών. 203 00:05:48,100 --> 00:05:51,990 >> Και αν μπορούσε πραγματικά Ιορδανία ελάτε μαζί μας εδώ στη σκηνή. 204 00:05:51,990 --> 00:05:55,100 Έλα για μια στιγμή. 205 00:05:55,100 --> 00:05:56,359 Ποιο είναι το όνομά σου? 206 00:05:56,359 --> 00:05:57,150 ΚΑΡΟΛΙΝΑ: Caroline. 207 00:05:57,150 --> 00:05:58,691 David J. Malan: Caroline, έλα επάνω. 208 00:05:58,691 --> 00:06:02,070 Και θα πρέπει να ενταχθεί από εμένα και την Ιορδανία εδώ. 209 00:06:02,070 --> 00:06:03,800 Caroline, σας ευχαριστώ. 210 00:06:03,800 --> 00:06:04,300 Εντάξει. 211 00:06:04,300 --> 00:06:08,330 Έτσι, αυτό που έχουμε εδώ Η Caroline είναι 26 μπλε βιβλία 212 00:06:08,330 --> 00:06:10,747 ότι FAS χρησιμοποιεί για να διαχειριστεί ορισμένες τελικές εξετάσεις. 213 00:06:10,747 --> 00:06:13,330 Αυτά είναι ολοένα πιο δύσκολο να βρεθεί, αλλά αυτό που έχουμε κάνει εκ των προτέρων 214 00:06:13,330 --> 00:06:15,800 είναι ότι έχουμε βάλει το όνομα κάποιου στο μπροστινό μέρος του καθενός από αυτά, 215 00:06:15,800 --> 00:06:18,133 αλλά έχουμε κρατήσει από το απλό Στη συνέχεια κατάσβεση πλήρη ονόματα. 216 00:06:18,133 --> 00:06:22,720 Γι 'αυτό και θα θέσει το πρόσωπο με το όνομα L, D, J, Β, σε όλη τη διαδρομή A έως Z, 217 00:06:22,720 --> 00:06:24,090 αλλά είναι σε τυχαία σειρά. 218 00:06:24,090 --> 00:06:26,890 Και έτσι αν ήταν, μιλώντας σας διαδρομή μέσα από το πρόβλημα με εσάς 219 00:06:26,890 --> 00:06:31,620 κάνετε, μπορεί να προχωρήσει και να ταξινομήσετε αυτά για μας, από το Α έως το Ω 220 00:06:31,620 --> 00:06:34,070 >> Κοινό: Εντάξει, έτσι είναι σαν L, η μέση. 221 00:06:34,070 --> 00:06:35,050 C έχει αρχίσει. 222 00:06:35,050 --> 00:06:42,410 Β Ι Β Λ πριν, Q. 223 00:06:42,410 --> 00:06:45,140 >> David J. Malan: Κρατήστε ότι σκέφτηκε για ένα δευτερόλεπτο. 224 00:06:45,140 --> 00:06:48,910 Διότι αλλιώς, αυτό είναι μόνο ενδιαφέρουσες για εσάς, εμένα, και την Ιορδανία. 225 00:06:48,910 --> 00:06:49,724 Εκεί πάμε. 226 00:06:49,724 --> 00:06:50,640 Κοινό: [δεν ακούγεται]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 David J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Τι κάνεις? 230 00:06:59,310 --> 00:07:01,730 >> ΚΑΡΟΛΙΝΑ: M έρχεται μετά O. 231 00:07:01,730 --> 00:07:02,564 >> David J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 David J. Malan: O, Καλή. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: Ε 235 00:07:04,970 --> 00:07:06,730 >> David J. Malan: Ε, ΣΤ Ναι. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, Τ, U, V. Έτσι Φαίνεται σαν να είστε making-- συνεχίσω. 238 00:07:10,689 --> 00:07:12,730 Μοιάζει κάνεις ένα μεγάλο σωρό εδώ, 239 00:07:12,730 --> 00:07:13,910 και το είδος της ένα μεγάλο σωρό εκεί πέρα. 240 00:07:13,910 --> 00:07:16,230 Έτσι, το πρώτο εξάμηνο του αλφαβήτου, δεύτερο εξάμηνο του αλφαβήτου. 241 00:07:16,230 --> 00:07:16,460 ΕΝΤΆΞΕΙ. 242 00:07:16,460 --> 00:07:16,960 Καλή. 243 00:07:16,960 --> 00:07:19,680 Είδος διάσπαση του προβλήματος σε δύο. 244 00:07:19,680 --> 00:07:21,771 Μ, Ν, Ξ Ναι. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: Κ 246 00:07:22,270 --> 00:07:22,980 David J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 Κ Έτσι είστε το είδος της επιλογής τους ένα μετά το άλλο, 248 00:07:25,070 --> 00:07:27,620 τοποθετώντας την είτε αριστερά είτε δεξιά, ή Ζ πηγαίνει στο πάτωμα. 249 00:07:27,620 --> 00:07:28,012 ΕΝΤΆΞΕΙ. 250 00:07:28,012 --> 00:07:29,190 >> ΚΑΡΟΛΙΝΑ: Z πηγαίνει στο πάτωμα. 251 00:07:29,190 --> 00:07:29,360 >> David J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y πηγαίνει στο πάτωμα. 253 00:07:30,920 --> 00:07:31,735 Τώρα μπορούμε να βάλουμε φυλακή 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: Γ 255 00:07:32,409 --> 00:07:33,700 David J. Malan: G πηγαίνει αριστερά. 256 00:07:33,700 --> 00:07:36,017 S δεν πάει καλά. 257 00:07:36,017 --> 00:07:37,642 Εντάξει, Α πηγαίνει όλος ο τρόπος αριστερά. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> David J. Malan: Τώρα, καλό. 260 00:07:39,873 --> 00:07:43,260 Έχουμε Α, Β, Γ W πηγαίνει εκεί κάτω. 261 00:07:43,260 --> 00:07:45,566 Εντάξει, T. 262 00:07:45,566 --> 00:07:46,611 >> ΚΑΡΟΛΙΝΑ: Η, Θ, Ι 263 00:07:46,611 --> 00:07:47,860 David J. Malan: Η, Θ, Ι Καλό. 264 00:07:47,860 --> 00:07:49,160 ΚΑΡΟΛΙΝΑ: Στο κέντρο, είμαι gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Έτσι τώρα, θα πάμε σε είδος από τη συγχώνευση των διαφόρων αυτών σωρούς. 267 00:07:52,375 --> 00:08:00,730 Έτσι A έως C, τότε βλέπω D, και Ε και F, και G, και Η, Θ και της Νίκαιας. 268 00:08:00,730 --> 00:08:05,540 J, Κ και στη συνέχεια, αυτό είναι σωρός ανάποδα, αλλά αυτό είναι εντάξει. 269 00:08:05,540 --> 00:08:06,040 Σίγουρα. 270 00:08:06,040 --> 00:08:07,240 Μπορούμε να κόψετε μερικές γωνίες. 271 00:08:07,240 --> 00:08:07,950 ΕΝΤΆΞΕΙ. 272 00:08:07,950 --> 00:08:10,530 Και τότε χρειαζόμαστε W, Χ, Υ, Ζ 273 00:08:10,530 --> 00:08:11,250 >> ΚΑΡΟΛΙΝΑ: Ναι. 274 00:08:11,250 --> 00:08:11,880 >> David J. Malan: Εξαιρετική. 275 00:08:11,880 --> 00:08:14,122 Έτσι, ένα μεγάλο ευχαριστώ σε Caroline για τη διαλογή αυτών. 276 00:08:14,122 --> 00:08:15,030 >> [Ζητωκραυγάζει] 277 00:08:15,030 --> 00:08:17,287 >> Ευχαριστώ. 278 00:08:17,287 --> 00:08:18,120 Ευχαριστώ πολύ. 279 00:08:18,120 --> 00:08:22,910 Έτσι τώρα ας αναλογιστούμε για μια στιγμή πώς Caroline πήγε για να κάνει ότι, 280 00:08:22,910 --> 00:08:26,040 και τι ακριβώς ήταν σε θέση to-- πώς μπορούμε 281 00:08:26,040 --> 00:08:28,409 ήταν σε θέση να λύσει αυτό πρόβλημα όταν ήμασταν 282 00:08:28,409 --> 00:08:29,950 δίνεται μια ολόκληρη δέσμη των τυχαίων εισόδων. 283 00:08:29,950 --> 00:08:31,610 >> Λοιπόν, φαίνεται σαν να υπάρχει Ήταν ένα κομμάτι από ένα σύστημα; 284 00:08:31,610 --> 00:08:32,110 Δεξιά. 285 00:08:32,110 --> 00:08:34,495 Έτσι, τις προηγούμενες επιστολές στο αλφάβητο, που 286 00:08:34,495 --> 00:08:37,120 Ήταν βάζοντας προς τα αριστερά, και η αργότερα τα γράμματα του αλφαβήτου, 287 00:08:37,120 --> 00:08:38,270 που έβαζε στο δεξί. 288 00:08:38,270 --> 00:08:40,500 Και μόλις βρήκε μερικοί εγγύς γράμματα, αυτά 289 00:08:40,500 --> 00:08:43,124 ότι πηγαίνετε δεξιά δίπλα στο άλλο, ότι θα τα βάλετε σε τάξη. 290 00:08:43,124 --> 00:08:46,750 Και γι 'αυτό το είδος είχε αυτά τα μικρά σωρούς των ταξινομημένων εισροών που συμβαίνουν. 291 00:08:46,750 --> 00:08:50,540 >> Και έτσι αυτό είναι αρκετά όπως αυτό οι περισσότεροι από εμάς τους ανθρώπους θα κάνουμε. 292 00:08:50,540 --> 00:08:53,530 Θα είδος κοσκινίσει μέσω αυτού, και είχαμε το είδος της έχουν μηχανισμό. 293 00:08:53,530 --> 00:08:56,930 Αλλά μπορεί να είναι δύσκολο να γράψω προς τα κάτω σε ένα τύπο per se. 294 00:08:56,930 --> 00:08:59,010 Ένιωσα λίγο πιο οργανική από αυτό. 295 00:08:59,010 --> 00:09:02,560 Ας δούμε αν μπορούμε τώρα δεσμευμένο το πρόβλημα με λιγότερες εισροές. 296 00:09:02,560 --> 00:09:05,170 >> Αντί για 26, ας να κάνουμε κάτι πολύ λιγότερα 297 00:09:05,170 --> 00:09:09,890 με μόνο να πω, επτά, πίσω Αυτές οι πόρτες, να το πω έτσι. 298 00:09:09,890 --> 00:09:11,300 Είναι μόλις επτά αριθμούς εκεί; 299 00:09:11,300 --> 00:09:15,240 Και αν ο στόχος τώρα το χέρι είναι να βρούμε μια τιμή, 300 00:09:15,240 --> 00:09:17,850 ας δούμε πόσο αποτελεσματικά μπορούμε να το κάνουμε αυτό. 301 00:09:17,850 --> 00:09:22,460 Και ας δούμε αν μπορούμε τώρα να αρχίσει να εφαρμόζεται κάποιους αριθμούς, 302 00:09:22,460 --> 00:09:26,310 ή κάποιες φόρμουλες με τις οποίες για να περιγράψει η απόδοση του τηλεφώνου βιβλίο μας 303 00:09:26,310 --> 00:09:31,060 αλγόριθμο, ο αλγόριθμος μας βιβλίο εξετάσεις, και γενικότερα, την εύρεση πληροφοριών. 304 00:09:31,060 --> 00:09:34,770 >> Έτσι, για αυτό, επιτρέψτε μου να πάει μπροστά, και στην οθόνη αφής εδώ, 305 00:09:34,770 --> 00:09:41,100 θέσει ένα web browser που έχει ακριβώς αυτά τα επτά πόρτες. 306 00:09:41,100 --> 00:09:46,670 Και αν θα μπορούσαμε να πάρουμε ένα άλλο εθελοντικά να έρθει για πάνω από εδώ, 307 00:09:46,670 --> 00:09:48,480 Έχω βάλει αυτές τις ίδιες πόρτες εδώ. 308 00:09:48,480 --> 00:09:49,170 Γρήγορη εθελοντή. 309 00:09:49,170 --> 00:09:51,130 >> Τα Αυτή ένα-- demos πρόκειται σε μια ταχύτερη και πιο γρήγορα τώρα. 310 00:09:51,130 --> 00:09:51,600 Ελάτε κάτω. 311 00:09:51,600 --> 00:09:52,308 Ποιο είναι το όνομά σου? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> David J. Malan: Trevor; 314 00:09:53,998 --> 00:09:55,770 Εντάξει, Trevor, έλα κάτω. 315 00:09:55,770 --> 00:09:59,212 Έτσι, Trevor έχει προσφερθεί εθελοντικά εδώ για να κάνει ένα παρόμοιο πρόβλημα, αλλά αυτό που είναι 316 00:09:59,212 --> 00:10:02,170 στενότερο πεδίο εφαρμογής, και ότι πρόκειται να επιτρέψουμε να προσπαθήσουμε να επισημοποιήσει τώρα 317 00:10:02,170 --> 00:10:03,970 η διαδικασία για τη διαλογή αυτών των αριθμών. 318 00:10:03,970 --> 00:10:05,500 >> Έτσι Trevor, ωραίο να σας γνωρίσουμε. 319 00:10:05,500 --> 00:10:08,720 Έτσι, εδώ είναι μια σειρά, έτσι ώστε να μιλούν, μια λίστα με επτά πόρτες. 320 00:10:08,720 --> 00:10:10,327 Προχωρήστε και θα μας βρείτε στον αριθμό 50. 321 00:10:10,327 --> 00:10:12,410 Και στη συνέχεια, μετά το γεγονός, να μας πει πώς το βρήκατε. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Σε περίπτωση που be-- εντάξει. 324 00:10:20,040 --> 00:10:21,945 Ναι, αυτή είναι η μία εδώ; 325 00:10:21,945 --> 00:10:24,680 Ωχ. 326 00:10:24,680 --> 00:10:25,560 ΕΝΤΆΞΕΙ. 327 00:10:25,560 --> 00:10:26,680 Μπορείτε κλικ ότι ένα. 328 00:10:26,680 --> 00:10:28,690 Καλή. 329 00:10:28,690 --> 00:10:29,780 >> Και καλό. 330 00:10:29,780 --> 00:10:30,970 Τώρα που πατήσατε το ένα. 331 00:10:30,970 --> 00:10:34,060 Και επιτρέψτε μου να σας δώσω το μικρόφωνο, έτσι ώστε να μπορείτε να έχετε ακριβώς σε μια στιγμή. 332 00:10:34,060 --> 00:10:37,000 Προχωρήστε και κάντε κλικ στο κουμπί διπλανής πόρτας που σκοπεύετε. 333 00:10:37,000 --> 00:10:39,812 Ναι ωραία. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Μπορώ να αποεπιλέξτε μια πόρτα; 335 00:10:41,020 --> 00:10:42,620 David J. Malan: Όχι, δεν μπορείτε να αποεπιλέξτε. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Αυτό. 338 00:10:43,974 --> 00:10:45,640 David J. Malan: Πού θέλετε να πάτε; 339 00:10:45,640 --> 00:10:46,410 Ποιο από όλα? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Εκείνο το ένα. 341 00:10:47,230 --> 00:10:48,042 >> David J. Malan: Όχι. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Αυτό. 344 00:10:48,735 --> 00:10:49,020 >> David J. Malan: Ναι. 345 00:10:49,020 --> 00:10:49,700 Αυτό ήταν καλό. 346 00:10:49,700 --> 00:10:50,380 Εντάξει. 347 00:10:50,380 --> 00:10:53,900 Λοιπόν, τι ήταν αλγόριθμο ή διαδικασία για να γίνει αυτό, Τρέβορ; 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Πήγα μέσω πόρτες μέχρι να βρεθεί μια 50. 349 00:10:56,149 --> 00:10:56,940 David J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Εξαιρετική αλγόριθμο. 351 00:10:58,150 --> 00:10:59,540 Έτσι, αυτό είναι εντάξει. 352 00:10:59,540 --> 00:11:03,120 Διότι στην πραγματικότητα, αν μπορώ να αποκαλύψει ό, τι είναι πίσω από αυτές τις άλλες δύο πόρτες, τι 353 00:11:03,120 --> 00:11:06,954 θα βρούμε εδώ είναι ότι έχουμε μόνο τυχαία είσοδο. 354 00:11:06,954 --> 00:11:08,870 Οπότε αυτό ήταν στην πραγματικότητα καθώς καλή όσο θα μπορούσε να πάρει. 355 00:11:08,870 --> 00:11:12,509 Και στην πραγματικότητα, έχεις καλύτερη από ό, τι εξαντλητικά αναζήτηση ολόκληρου του πίνακα, 356 00:11:12,509 --> 00:11:15,300 επειδή θα έχουν πραγματικά άτυχος αν είχε χτυπήσει τον αριθμό 357 00:11:15,300 --> 00:11:16,604 50 κατά την τελευταία πόρτα. 358 00:11:16,604 --> 00:11:18,520 Αλλά τι θα γινόταν αν αντ 'αυτού Σας έδωσα μια υπόθεση. 359 00:11:18,520 --> 00:11:20,630 Ας υποθέσουμε ότι το είδος όλους Αυτές οι πόρτες γύρω, 360 00:11:20,630 --> 00:11:23,500 έτσι ώστε να έχετε το αριθμοί ταξινομούνται αυτή τη φορά, 361 00:11:23,500 --> 00:11:29,730 αλλά αυτή τη φορά είναι πραγματικά α different-- αυτή τη φορά, 362 00:11:29,730 --> 00:11:32,640 αυτό είναι πραγματικά ταξινομηθεί για εσάς. 363 00:11:32,640 --> 00:11:35,380 Και τώρα ο στόχος στο χέρι είναι να χτυπήσει τον αριθμό 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> David J. Malan: Τι είναι αλγόριθμος σας πρόκειται να είναι; 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Λοιπόν, αν είναι διαλογή, είναι είτε πηγαίνοντας 367 00:11:39,628 --> 00:11:42,710 να be-- αν το μεγαλύτερο στο μεγαλύτερο, φθίνουσα, αυτό θα είναι το πρώτο, 368 00:11:42,710 --> 00:11:44,751 ή αν πρόκειται για το αντίθετο, θα είναι η τελευταία. 369 00:11:44,751 --> 00:11:48,897 Γι 'αυτό θα πρέπει ακριβώς να αξιοποιήσει αυτήν την πόρτα, και τότε απλά πατήστε το τελευταίο πόρτα. 370 00:11:48,897 --> 00:11:49,980 David J. Malan: Εξαιρετική. 371 00:11:49,980 --> 00:11:50,270 Εντάξει. 372 00:11:50,270 --> 00:11:51,150 Έτσι βρήκαμε τον αριθμό 50. 373 00:11:51,150 --> 00:11:52,970 Έτσι, το συντομότερο ξέρατε είχαν διευθετηθεί, θα 374 00:11:52,970 --> 00:11:55,040 ήταν σε θέση να αξιοποιήσουν αυτή την υπόθεση. 375 00:11:55,040 --> 00:11:57,040 Έτσι είναι πάρα πολύ σαν Το παράδειγμα του τηλεφωνικού καταλόγου. 376 00:11:57,040 --> 00:11:59,540 Από τη στιγμή που έχετε, ακόμη και με ένα μικρό πρόβλημα όπως αυτό, 377 00:11:59,540 --> 00:12:02,380 εισόδους σας προ-ταξινόμηση, μπορούμε στην πραγματικότητα βρείτε την τιμή αμφισβητήσιμα 378 00:12:02,380 --> 00:12:03,130 πιο αποτελεσματικά. 379 00:12:03,130 --> 00:12:05,800 >> Και εγώ δεν σας αν ήταν πω ταξινομημένο μικρές προς μεγάλες, ή μεγάλες σε μικρές, 380 00:12:05,800 --> 00:12:08,080 και γι 'αυτό ήταν πολύ λογικό για να ξεκινήσει σε ένα άκρο ή το άλλο 381 00:12:08,080 --> 00:12:09,750 να βρείτε πραγματικά ότι η τιμή-στόχος. 382 00:12:09,750 --> 00:12:11,400 Έτσι, ευχαριστώ σε Trevor, καθώς και. 383 00:12:11,400 --> 00:12:13,260 Και εγώ θα propose-- όμορφα γίνεται. 384 00:12:13,260 --> 00:12:16,960 Έχουμε ένα μικρό κλιπ, στην πραγματικότητα, ότι είναι μεταξύ των αγαπημένων μας στιγμές στην CS50, 385 00:12:16,960 --> 00:12:19,700 σύμφωνα με την οποία μερικές φορές αυτά τα demos Δεν πηγαίνουν αρκετά σύμφωνα με το σχέδιο. 386 00:12:19,700 --> 00:12:22,050 Και πράγματι αυτή τη στιγμή, τράβηξε το λάθος τύπο διασύνδεσης 387 00:12:22,050 --> 00:12:23,508 με το οποίο να χρησιμοποιήσετε την οθόνη αφής. 388 00:12:23,508 --> 00:12:24,660 Έτσι, αυτό ήταν δικό μου λάθος εκεί. 389 00:12:24,660 --> 00:12:26,600 >> Έτσι, αυτό θα κάνει για του επόμενου έτους κλιπ ως 390 00:12:26,600 --> 00:12:28,570 γιατί ήμουν κάνετε κλικ στις δικές μου οθόνη. 391 00:12:28,570 --> 00:12:31,390 Αλλά ας ρίξουμε μια γρήγορη ματιά σε ό, τι συνέβη πέρυσι 392 00:12:31,390 --> 00:12:34,770 με τον Jay, ο οποίος ήρθε, πολύ όπως Trevor εδώ, εθελοντικά, 393 00:12:34,770 --> 00:12:39,380 και σε αυτό το σύντομο κλιπ, θα δείτε πώς αυτό το ίδιο το demo δεν έκανε αρκετά 394 00:12:39,380 --> 00:12:41,074 αποκαλύψει τα ίδια διδάγματα. 395 00:12:41,074 --> 00:12:41,740 [ΑΝΑΠΑΡΑΓΩΓΗ] 396 00:12:41,740 --> 00:12:45,360 -Όλες Θέλω να κάνω τώρα είναι να να βρει για μένα, αλλά και για εμάς, 397 00:12:45,360 --> 00:12:51,674 Πραγματικά, ο αριθμός 50 ένα βήμα τη φορά. 398 00:12:51,674 --> 00:12:52,450 >> -τον Αριθμό 50; 399 00:12:52,450 --> 00:12:53,190 >> -τον Αριθμό 50. 400 00:12:53,190 --> 00:12:55,356 Και μπορείτε να αποκαλύψει τι είναι πίσω από κάθε μία από αυτές τις πόρτες 401 00:12:55,356 --> 00:12:58,540 απλά αγγίζοντας το με ένα δάχτυλο. 402 00:12:58,540 --> 00:13:00,910 Ανάθεμα. 403 00:13:00,910 --> 00:13:02,870 >> [Γέλια] 404 00:13:02,870 --> 00:13:03,806 >> [Σταματήσετε την αναπαραγωγή] 405 00:13:03,806 --> 00:13:05,430 David J. Malan: Μέχρι που πήγε πολύ καλά. 406 00:13:05,430 --> 00:13:06,796 Αυτά ήταν τα αδιαχώριστα πόρτες. 407 00:13:06,796 --> 00:13:08,670 Και Jay, φυσικά, βρήκα όλα πολύ γρήγορα. 408 00:13:08,670 --> 00:13:12,910 Trevor έκανε πολύ καλύτερη δουλειά σε όρους μιας διδακτός στιγμή, 409 00:13:12,910 --> 00:13:15,850 να το πω έτσι, φέτος στο περισσότερο χρόνο για να το βρείτε. 410 00:13:15,850 --> 00:13:17,950 Φυσικά, τότε δώσαμε Jay μια δεύτερη ευκαιρία, 411 00:13:17,950 --> 00:13:20,320 σύμφωνα με την οποία θα διευθετηθεί τις πόρτες, ακριβώς όπως κάναμε για τον Trevor, 412 00:13:20,320 --> 00:13:22,300 και Trevor έκανε σούπερ καλά αυτή τη φορά. 413 00:13:22,300 --> 00:13:26,124 Αλλά Jay έκανε το μισό τόσο γρήγορα. 414 00:13:26,124 --> 00:13:26,790 [ΑΝΑΠΑΡΑΓΩΓΗ] 415 00:13:26,790 --> 00:13:29,650 -Το Στόχος τώρα είναι να επίσης βρείτε μας στον αριθμό 50, 416 00:13:29,650 --> 00:13:33,030 αλλά να το κάνει αλγοριθμικά, και πείτε μας πώς θα πάμε για αυτό. 417 00:13:33,030 --> 00:13:33,660 >> -ΕΝΤΆΞΕΙ. 418 00:13:33,660 --> 00:13:35,604 >> -Και Αν το βρείτε, θα κρατήσει την ταινία. 419 00:13:35,604 --> 00:13:37,228 Αν δεν το βρείτε, να το δώσει πίσω. 420 00:13:37,228 --> 00:13:38,044 >> -Άνδρας. 421 00:13:38,044 --> 00:13:38,860 >> -ΟΗ! 422 00:13:38,860 --> 00:13:40,800 >> - [Δεν ακούγεται] OK. 423 00:13:40,800 --> 00:13:46,236 Έτσι, Πάω να ελέγξει τα άκρα πρώτα να προσδιορίσετε αν there's-- Αχ. 424 00:13:46,236 --> 00:13:48,646 >> [Χειροκρότημα] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [Σταματήσετε την αναπαραγωγή] 427 00:13:55,729 --> 00:13:56,520 David J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Έτσι, η διαλογή των θυρών με σαφήνεια οδηγεί σε μεγαλύτερη αποτελεσματικότητα. 429 00:13:59,760 --> 00:14:01,680 Και έτσι, δύο φορές πιο γρήγορα είναι αυτό που εννοούσα εκεί. 430 00:14:01,680 --> 00:14:03,270 Και έτσι Jay τυχεροί και τις δύο φορές. 431 00:14:03,270 --> 00:14:06,685 Και, επίσης, πήρε τυχερός στην τελευταία έτος, παρήγγειλα ορισμένους δίσκους Blu-ray 432 00:14:06,685 --> 00:14:07,560 να δίνουν στην πραγματικότητα. 433 00:14:07,560 --> 00:14:09,768 Λυπάμαι φέτος, δεν είχε την ίδια, Trevor. 434 00:14:09,768 --> 00:14:11,540 Αλλά ακόμη καλύτερα ήταν πριν από μερικά χρόνια. 435 00:14:11,540 --> 00:14:14,820 Και κάποιοι από εσάς ίσως γνωρίζετε αυτό τους συναδέλφους, Sean, ο οποίος όταν ήταν σε CS50, 436 00:14:14,820 --> 00:14:17,780 αμφισβητήθηκε με την ακριβή ίδιο πρόβλημα, αν και σε SD, 437 00:14:17,780 --> 00:14:19,360 όπως θα δείτε σύντομα, πίσω στην ημέρα. 438 00:14:19,360 --> 00:14:22,622 Και θα διαπιστώσετε ότι όχι μόνο αυτός πάρει λίγο περισσότερο από ό, τι Jay, 439 00:14:22,622 --> 00:14:25,580 λίγο περισσότερο από ό, τι Trevor, ήταν στην πραγματικότητα αυτή την υπέροχη ευκαιρία 440 00:14:25,580 --> 00:14:29,820 να συμμετέχουν σχεδόν όλοι στην πλήθος a la τιμή είναι σωστή, ενθαρρύνοντας 441 00:14:29,820 --> 00:14:31,889 αυτόν να βρείτε τον αριθμό που ζητούσαν. 442 00:14:31,889 --> 00:14:32,930 Ας. ρίξτε μια γρήγορη ματιά. 443 00:14:32,930 --> 00:14:33,320 >> [ΑΝΑΠΑΡΑΓΩΓΗ] 444 00:14:33,320 --> 00:14:33,820 >> -ΕΝΤΆΞΕΙ. 445 00:14:33,820 --> 00:14:36,680 Έτσι, το έργο σας εδώ, Σον, είναι το εξής. 446 00:14:36,680 --> 00:14:40,860 Έχω κρυμμένο πίσω από αυτά πόρτες ο αριθμός επτά. 447 00:14:40,860 --> 00:14:45,120 Αλλά κρυμμένο σε ορισμένες από αυτές τις πόρτες καθώς είναι άλλες αρνητικούς αριθμούς. 448 00:14:45,120 --> 00:14:47,500 Και ο στόχος σας είναι να σκεφτεί της κορυφαίας σειράς αριθμών 449 00:14:47,500 --> 00:14:50,390 ως απλά έναν πίνακα, ή απλά ακολουθία κομμάτια χαρτιού 450 00:14:50,390 --> 00:14:51,510 με αριθμούς πίσω τους. 451 00:14:51,510 --> 00:14:55,540 Και ο στόχος σας είναι, χρησιμοποιώντας μόνο την κορυφή σειρά εδώ, βρες μου τον αριθμό επτά. 452 00:14:55,540 --> 00:14:58,570 Και στη συνέχεια πρόκειται να κριτικάρω πώς μπορείτε να κάνετε για αυτό. 453 00:14:58,570 --> 00:14:59,070 -Εντάξει. 454 00:14:59,070 --> 00:15:00,850 -Βρείτε Μας τον αριθμό επτά, παρακαλώ. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Κανένα. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Πέντε, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Γέλια] 461 00:15:24,770 --> 00:15:25,910 >> Δεν είναι μια ερώτηση τεχνάσματος. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Ένα. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Γέλια] 466 00:15:34,695 --> 00:15:37,861 Σε αυτό το σημείο, το σκορ σου δεν είναι πολύ καλά, έτσι ίσως και να συνεχίσω. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Τρεις. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Γέλια] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Συνέχισε. 473 00:15:47,774 --> 00:15:50,690 Ειλικρινά, δεν μπορώ να βοηθήσει, αλλά αναρωτιέμαι τι είστε καν να το σκεφτούμε, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Γέλια] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Μόνο η επάνω σειρά, έτσι έχεις τρία αριστερά. 477 00:15:55,020 --> 00:15:56,200 Έτσι, βρείτε μου επτά. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Γέλια] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Επτά. 484 00:16:26,946 --> 00:16:28,780 >> [Χειροκρότημα] 485 00:16:28,780 --> 00:16:29,426 >> Εντάξει. 486 00:16:29,426 --> 00:16:30,360 >> [Σταματήσετε την αναπαραγωγή] 487 00:16:30,360 --> 00:16:31,840 >> David J. Malan: έτσι θα μπορούσαμε να Παρακολουθήστε αυτά όλη μέρα. 488 00:16:31,840 --> 00:16:34,090 Και φυσικά, ορισμένες από τις demos φετινή ίσως 489 00:16:34,090 --> 00:16:36,330 τώρα θα καταλήξουν στην επόμενη βίντεο έτους, καθώς και. 490 00:16:36,330 --> 00:16:39,040 Έτσι τώρα ας πραγματικότητα επικεντρωθεί στις αλγορίθμους 491 00:16:39,040 --> 00:16:42,140 εδώ, και να δούμε αν δεν μπορούμε να τώρα αρχίζουν να επισημοποιήσει 492 00:16:42,140 --> 00:16:46,650 πώς μπορούμε να πάμε για να πάρει τα δεδομένα μας σε αυτή την κατάσταση ότι είναι ταξινομημένο, 493 00:16:46,650 --> 00:16:50,054 έτσι ώστε, τελικά, μπορούμε πραγματικά να αναζήτηση πιο αποτελεσματικά. 494 00:16:50,054 --> 00:16:52,470 Και ακόμα κι αν θα πάμε να χρησιμοποιήσει αρκετά μικρά σύνολα δεδομένων, 495 00:16:52,470 --> 00:16:54,511 όπως το έχουμε οκτώ αριθμούς έχουμε εδώ στο διοικητικό συμβούλιο, 496 00:16:54,511 --> 00:16:58,230 τελικά, θα μπορούσαν να εφαρμοστούν αυτές οι ίδιες ιδέες 1.000 εισόδους, ένα εκατομμύριο εισόδους, 497 00:16:58,230 --> 00:17:02,100 4000000000 εισόδους, επειδή οι αλγόριθμοι πρόκειται να είναι ουσιαστικά η ίδια. 498 00:17:02,100 --> 00:17:05,359 >> Και έτσι αυτή είναι η τελευταία μας ευκαιρία στους εθελοντές σήμερα, 499 00:17:05,359 --> 00:17:09,790 αλλά ίσως το σημαντικότερο ρόλο ενός, για τα οποία χρειαζόμαστε οκτώ εθελοντές 500 00:17:09,790 --> 00:17:12,960 για να καταλήξει και να περπατήσετε μαζί μας μέσω της διαδικασία της διαλογής τι θα είναι σύντομα 501 00:17:12,960 --> 00:17:15,212 είναι σε αυτά τα περίπτερα μουσική εδώ. 502 00:17:15,212 --> 00:17:16,170 Επιτρέψτε μου να ξεκινήσω πάλι εδώ. 503 00:17:16,170 --> 00:17:19,692 >> Έτσι, ένα στην turquoise-- πράσινο είναι αυτό; 504 00:17:19,692 --> 00:17:21,130 Είσαι διάπραξη; 505 00:17:21,130 --> 00:17:21,630 Δύο. 506 00:17:21,630 --> 00:17:23,069 Ελάτε κάτω. 507 00:17:23,069 --> 00:17:23,569 ΕΝΤΆΞΕΙ. 508 00:17:23,569 --> 00:17:24,420 Τρεις. 509 00:17:24,420 --> 00:17:25,400 Τέσσερις. 510 00:17:25,400 --> 00:17:27,247 Ας me-- Εντάξει, πέντε. 511 00:17:27,247 --> 00:17:28,830 Είσαι που διορίζεται από το φίλο σας. 512 00:17:28,830 --> 00:17:31,340 Έξι, επτά, οκτώ. 513 00:17:31,340 --> 00:17:32,130 Έλα επάνω. 514 00:17:32,130 --> 00:17:32,630 Εντάξει. 515 00:17:32,630 --> 00:17:33,190 Ευχαριστω παρα πολυ. 516 00:17:33,190 --> 00:17:33,689 Έλα επάνω. 517 00:17:33,689 --> 00:17:34,790 Έλα επάνω. 518 00:17:34,790 --> 00:17:35,330 >> Εντάξει. 519 00:17:35,330 --> 00:17:38,890 Έτσι, αυτό που here-- και αυτό έχει είναι μια από τις πιο δύσκολη αυτά, 520 00:17:38,890 --> 00:17:42,390 δεδομένου ότι αυτό θα πρέπει να έχετε χιούμορ Θέλω μόνο για ένα μικρό κομμάτι του χρόνου. 521 00:17:42,390 --> 00:17:43,442 Θα πρέπει να είναι το νούμερο ένα. 522 00:17:43,442 --> 00:17:44,150 Ποιο είναι το όνομά σου? 523 00:17:44,150 --> 00:17:44,610 >> Ανάν Ανάν. 524 00:17:44,610 --> 00:17:45,526 >> David J. Malan: Ανάν. 525 00:17:45,526 --> 00:17:46,092 Δαβίδ. 526 00:17:46,092 --> 00:17:46,800 Ποιο είναι το όνομά σου? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> David J. Malan: Ιωσήφ, είσαι νούμερο δύο. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, το νούμερο τρία. 530 00:17:52,260 --> 00:17:53,722 Stefan, νούμερο τέσσερα. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 David J. Malan: Cynthia, νούμερο πέντε. 533 00:17:57,548 --> 00:17:58,452 [Δεν ακούγεται] 534 00:17:58,452 --> 00:17:59,618 David J. Malan: [δεν ακούγεται]. 535 00:17:59,618 --> 00:18:00,391 Ο David, τον αριθμό έξι. 536 00:18:00,391 --> 00:18:00,890 ΜΑΤ: Ματ. 537 00:18:00,890 --> 00:18:02,160 David J. Malan: αριθμός Ματ επτά. 538 00:18:02,160 --> 00:18:02,850 Και; 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> David J. Malan: Waverly, νούμερο οκτώ. 541 00:18:04,470 --> 00:18:04,970 Εντάξει. 542 00:18:04,970 --> 00:18:06,510 Αν could-- κραυγών. 543 00:18:06,510 --> 00:18:08,820 Εάν όλα, όπως σας πρώτη πρόκληση, εκεί 544 00:18:08,820 --> 00:18:10,820 είναι οκτώ περίπτερα μουσική εδώ που αντιμετωπίζει το κοινό. 545 00:18:10,820 --> 00:18:14,200 Αν θα μπορούσατε να βάλετε τους αριθμούς σας αυτοί μουσική στέκεται κατά τέτοιο τρόπο 546 00:18:14,200 --> 00:18:16,560 ότι είναι ευθυγραμμισμένο με το ίδιους αριθμούς στον πίνακα. 547 00:18:16,560 --> 00:18:19,560 Έτσι κάνετε τον εαυτό σας να μοιάζει ότι από βάζοντας τους αριθμούς σας σε αυτά μουσικής 548 00:18:19,560 --> 00:18:21,960 στέκεται εδώ. 549 00:18:21,960 --> 00:18:25,980 Εξαιρετική μέχρι στιγμής. 550 00:18:25,980 --> 00:18:26,600 >> Εξαιρετική. 551 00:18:26,600 --> 00:18:26,890 ΕΝΤΆΞΕΙ. 552 00:18:26,890 --> 00:18:29,556 Έτσι τώρα, θα πάμε να ζητήσουμε την ερώτηση σε λίγες διαφορετικούς τρόπους. 553 00:18:29,556 --> 00:18:31,610 Πώς μπορούμε να πάμε για τη διαλογή αυτοί οι λαοί εδώ; 554 00:18:31,610 --> 00:18:34,500 Επειδή είχαμε μερικές προσεγγίσεις νωρίτερα, σύμφωνα με την οποία ήμασταν 555 00:18:34,500 --> 00:18:36,360 το είδος των αποφάσεων δύο διαφορετικούς κάδους. 556 00:18:36,360 --> 00:18:38,842 Και τότε θα ήταν σε γενικές γραμμές συναρμολογώντας τα πράγματα μαζί. 557 00:18:38,842 --> 00:18:41,050 Μόλις είδαμε δύο αριθμούς ότι ανήκε από κοινού, 558 00:18:41,050 --> 00:18:41,975 τα βάζουμε μαζί. 559 00:18:41,975 --> 00:18:43,350 Δύο επιστολές που ανήκουν μαζί. 560 00:18:43,350 --> 00:18:45,058 >> Αλλά ας δούμε αν μπορούμε δεν μπορεί να επισημοποιήσει αυτή, 561 00:18:45,058 --> 00:18:48,044 έτσι ώστε να έχουμε τελικά κάποια ψευδο-κώδικα που θα, 562 00:18:48,044 --> 00:18:49,710 με το οποίο μπορείτε να λύσετε αυτά τα προβλήματα. 563 00:18:49,710 --> 00:18:51,870 Έτσι τώρα, ψάχνω έξω σε αυτούς τους αριθμούς εδώ. 564 00:18:51,870 --> 00:18:55,030 Και βλέπω ένα σωρό λάθη. 565 00:18:55,030 --> 00:18:57,750 Τελικά, θέλω ένα για το αριστερά και οκτώ στα δεξιά. 566 00:18:57,750 --> 00:19:00,650 >> Και έτσι κοιτάζω αυτά τα δύο, τέσσερα και δύο. 567 00:19:00,650 --> 00:19:02,930 Και ποιο είναι το πρόβλημα, προφανώς; 568 00:19:02,930 --> 00:19:04,261 Ναι. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Δύο προφανώς έρχεται πριν τέσσερα, ώστε να γνωρίζετε τι; 571 00:19:07,160 --> 00:19:10,210 Επιτρέψτε μου πρώτα να λάβει μια άπληστη προσέγγιση, αν θέλετε, μοιάζει πολύ με το πρόβλημα 572 00:19:10,210 --> 00:19:13,790 που ένα-- αν θυμάστε από το Standard Edition του προβλήματος Set One, 573 00:19:13,790 --> 00:19:16,820 όπου μόλις τοπικά λύσει το πρόβλημα ότι είναι σωστό εδώ μπροστά μου 574 00:19:16,820 --> 00:19:17,690 και να δούμε πού μας οδηγεί. 575 00:19:17,690 --> 00:19:17,870 >> ΕΝΤΆΞΕΙ. 576 00:19:17,870 --> 00:19:20,161 Έτσι, δύο και τέσσερα, επιτρέψτε μου να πάω μπροστά και μόνο μπορείτε να ανταλλάσσετε δύο. 577 00:19:20,161 --> 00:19:22,400 Αν φυσικά να μετακινήσετε τον εαυτό σας και το χαρτί σας, 578 00:19:22,400 --> 00:19:25,040 Μου φαίνεται να έχουν πάρει το λίστα σε καλύτερη κατάσταση. 579 00:19:25,040 --> 00:19:26,330 >> Τώρα, είναι καλή. 580 00:19:26,330 --> 00:19:28,480 Πάω να προχωρήσουμε, τεσσάρων και έξι, φαίνεται καλό. 581 00:19:28,480 --> 00:19:29,110 Δεν είναι πρόβλημα. 582 00:19:29,110 --> 00:19:30,440 Έξι και οκτώ, εντάξει. 583 00:19:30,440 --> 00:19:31,860 Οκτώ και ένα άλλο πρόβλημα. 584 00:19:31,860 --> 00:19:34,750 Γιατί ό, τι είναι αληθινό περίπου οκτώ και ένα; 585 00:19:34,750 --> 00:19:36,990 Ένας έρχεται πριν από οκτώ, και ναι, τι πρέπει να κάνουμε; 586 00:19:36,990 --> 00:19:38,090 Ας ανταλλάξουν αυτά τα δύο. 587 00:19:38,090 --> 00:19:39,316 Ένα και οκτώ. 588 00:19:39,316 --> 00:19:40,690 Και τώρα, πάω να συνεχίσω. 589 00:19:40,690 --> 00:19:42,030 Πάω να κρατήσει το βλέμμα στραμμένο. 590 00:19:42,030 --> 00:19:42,840 Και ας δούμε τι θα συμβεί. 591 00:19:42,840 --> 00:19:44,680 Οκτώ και τρία, από Φυσικά, εκτός λειτουργίας. 592 00:19:44,680 --> 00:19:45,815 Ας swap. 593 00:19:45,815 --> 00:19:46,940 Οκτώ και επτά, φυσικά. 594 00:19:46,940 --> 00:19:47,481 Εκτός λειτουργίας. 595 00:19:47,481 --> 00:19:48,280 Ας swap. 596 00:19:48,280 --> 00:19:49,940 Οκτώ και πέντε, φυσικά, ας swap. 597 00:19:49,940 --> 00:19:50,560 Εντάξει. 598 00:19:50,560 --> 00:19:51,880 Λίστα ταξινομούνται. 599 00:19:51,880 --> 00:19:53,060 ναι; 600 00:19:53,060 --> 00:19:54,280 >> Εντάξει, προφανώς όχι. 601 00:19:54,280 --> 00:19:55,860 Αλλά είναι λίγο καλύτερα, έτσι δεν είναι; 602 00:19:55,860 --> 00:19:57,270 Επειδή ειδοποίηση τι συνέβη. 603 00:19:57,270 --> 00:20:01,749 Κάθε φορά που πραγματοποιείται μια ανταλλαγή, μια μικρότερη Αριθμός είδους percolated με αυτόν τον τρόπο, 604 00:20:01,749 --> 00:20:03,790 και ένα μεγαλύτερο αριθμό φιλτραριστεί με αυτόν τον τρόπο, ή θα 605 00:20:03,790 --> 00:20:06,880 αρχίσουμε να λέμε διοχετεύεται προς το αριστερά ή διοχετεύεται προς τα δεξιά. 606 00:20:06,880 --> 00:20:10,080 >> Τώρα, αυτό δεν είναι αρκετό, γιατί στην καλύτερη περίπτωση, ο αριθμός μπορεί να 607 00:20:10,080 --> 00:20:11,990 έχουν μετακινηθεί ένα σημείο προς τα εμπρός, ή στη χειρότερη περίπτωση, 608 00:20:11,990 --> 00:20:13,880 ένας αριθμός μπορεί να έχει μετακόμισε περαιτέρω ένα σημείο. 609 00:20:13,880 --> 00:20:16,369 Έτσι, ξέρετε τι, αυτό το είδος του λειτούργησε αρκετά καλά μέχρι τώρα. 610 00:20:16,369 --> 00:20:17,410 Επιτρέψτε μου να το δοκιμάσω ξανά. 611 00:20:17,410 --> 00:20:18,880 Δύο και τέσσερα, είναι ΟΚ. 612 00:20:18,880 --> 00:20:20,180 Τεσσάρων και έξι, είναι ΟΚ. 613 00:20:20,180 --> 00:20:21,790 Έξι και ένα, εκτός λειτουργίας. 614 00:20:21,790 --> 00:20:23,007 Ας εσάς τους δύο να ανταλλάξουν. 615 00:20:23,007 --> 00:20:25,840 Και τώρα, παρατηρήστε το πρόβλημα της αρχίζουν να πάρετε μια λίγο καλύτερη και πάλι. 616 00:20:25,840 --> 00:20:27,006 Έξι και τρεις, εκτός λειτουργίας. 617 00:20:27,006 --> 00:20:28,100 Ας εσείς οι δύο να ανταλλάξουν. 618 00:20:28,100 --> 00:20:29,730 Έξι και επτά, είστε καλοί. 619 00:20:29,730 --> 00:20:32,230 Επτά και πέντε, φυσικά, από τη διαταγή. 620 00:20:32,230 --> 00:20:33,920 Επτά και οκτώ, με τη σειρά. 621 00:20:33,920 --> 00:20:36,470 Και τώρα, ίσως χρειαστεί να το κάνετε αυτό μερικές φορές. 622 00:20:36,470 --> 00:20:39,830 Και στην πραγματικότητα, σκέφτονται για τον εαυτό σας ίσως πόσες φορές το μέγιστο 623 00:20:39,830 --> 00:20:41,330 μπορεί να έχω με τα πόδια πέρα ​​δώθε; 624 00:20:41,330 --> 00:20:42,390 >> Θα επανέλθω στο θέμα αυτό. 625 00:20:42,390 --> 00:20:43,700 Έτσι, δύο και τέσσερις είναι ακόμα εντάξει. 626 00:20:43,700 --> 00:20:44,940 Τέσσερις και μία, nope. 627 00:20:44,940 --> 00:20:45,747 Έτσι, ας swap. 628 00:20:45,747 --> 00:20:47,830 Και πάλι, παρατηρήσετε οπτικά ένα είναι το είδος των φυσαλίδων 629 00:20:47,830 --> 00:20:49,163 προς τα αριστερά, όπου θα πρέπει να είναι. 630 00:20:49,163 --> 00:20:50,010 Τέσσερις και τρεις swap. 631 00:20:50,010 --> 00:20:51,330 Τεσσάρων και έξι. 632 00:20:51,330 --> 00:20:53,100 Έξι και πέντε νομισμάτων. 633 00:20:53,100 --> 00:20:53,959 Έξι και επτά. 634 00:20:53,959 --> 00:20:55,000 Επτά και οκτώ είναι καλές. 635 00:20:55,000 --> 00:20:55,500 >> Καλή. 636 00:20:55,500 --> 00:20:58,460 Είμαστε πάρει ακόμα καλύτερα. 637 00:20:58,460 --> 00:20:59,130 Ας δούμε λοιπόν. 638 00:20:59,130 --> 00:21:00,940 Τώρα, έχουμε δύο και το ένα. 639 00:21:00,940 --> 00:21:02,520 Φυσικά, να ανταλλάξουν. 640 00:21:02,520 --> 00:21:07,520 Δύο και τρία, τρία και τέσσερα, τέσσερα και πέντε, έξι και επτά, επτά και οκτώ. 641 00:21:07,520 --> 00:21:08,020 Καλή. 642 00:21:08,020 --> 00:21:08,730 Και ξέρετε τι; 643 00:21:08,730 --> 00:21:11,190 Επειδή έκανα μια αλλαγή εκεί, επιτρέψτε μου να κάνω μια επιταγή λογική. 644 00:21:11,190 --> 00:21:13,023 Επιτρέψτε μου να πάνε όλα το δρόμο πίσω στην αρχή. 645 00:21:13,023 --> 00:21:13,680 ΕΝΤΆΞΕΙ. 646 00:21:13,680 --> 00:21:14,750 Ένα, two-- yup, βλέπεις; 647 00:21:14,750 --> 00:21:15,870 Κάτι δεν πήγαινε καλά. 648 00:21:15,870 --> 00:21:18,420 Τρία, τέσσερα, πέντε, έξι, επτά, οκτώ. 649 00:21:18,420 --> 00:21:21,920 Και σε αυτό το τελευταίο πέρασμα, είναι μπορείτε άνετα με την επιχειρηση μου 650 00:21:21,920 --> 00:21:23,830 ισχυριζόμενος ότι είναι ταξινομημένο; 651 00:21:23,830 --> 00:21:24,330 ΕΝΤΆΞΕΙ. 652 00:21:24,330 --> 00:21:25,880 Οπτικά, αυτό είναι απολύτως αληθές. 653 00:21:25,880 --> 00:21:28,410 Αλλά λειτουργικά, τι είχε μόλις συμβεί 654 00:21:28,410 --> 00:21:31,870 σε αυτό το τελευταίο πέρασμα που σας επιτρέπει να επιβεβαιώσει ότι ο κατάλογος αυτός είναι πράγματι 655 00:21:31,870 --> 00:21:32,660 ταξινόμηση; 656 00:21:32,660 --> 00:21:34,477 >> Τι έκανα ή όχι αυτό το τελευταίο πέρασμα; 657 00:21:34,477 --> 00:21:35,810 Κοινό: Δεν υπήρξαν αλλαγές. 658 00:21:35,810 --> 00:21:36,120 David J. Malan: Συγνώμη; 659 00:21:36,120 --> 00:21:37,070 Κοινό: Δεν υπάρχουν αλλαγές. 660 00:21:37,070 --> 00:21:38,653 David J. Malan: Δεν υπήρξαν αλλαγές. 661 00:21:38,653 --> 00:21:41,947 Έτσι, θα ήταν ανόητο εκ μέρους μου να κάνει ξανά το ίδιο αλγόριθμο 662 00:21:41,947 --> 00:21:43,780 αν δεν είχα κάνει καμία αλλάζει την πρώτη φορά. 663 00:21:43,780 --> 00:21:45,160 Και η κατάσταση δεν έχει αλλάξει. 664 00:21:45,160 --> 00:21:47,576 Σίγουρα, δεν είμαι πρόκειται να κάνει Οποιεσδήποτε αλλαγές για δεύτερη φορά. 665 00:21:47,576 --> 00:21:49,820 Και ναι, είναι ασφαλές τώρα να πω, κατάλογος ταξινομείται. 666 00:21:49,820 --> 00:21:52,069 >> Και πράγματι, αυτό είναι τώρα Κάτι που θα σε γενικές γραμμές 667 00:21:52,069 --> 00:21:56,900 κλήση bubble sort, σύμφωνα με την οποία κατά ζεύγη, να διορθώσετε λάθη ξανά, 668 00:21:56,900 --> 00:22:00,210 και ξανά, και ξανά, και θα συνεχίστε εμπρός και πίσω, 669 00:22:00,210 --> 00:22:03,370 και εμπρός και πίσω, μέχρι να δεν κάνουν τέτοια swaps, σε ποιο σημείο 670 00:22:03,370 --> 00:22:07,089 μπορείτε να είστε σίγουροι, ναι, τελείωσε τον καθορισμό όλα τα λάθη. 671 00:22:07,089 --> 00:22:08,630 Ας επαναφορά και δοκιμάστε μια άλλη προσέγγιση. 672 00:22:08,630 --> 00:22:11,590 Αν εσείς μπορούσατε να πάτε πίσω στο η σειρά που ήταν πριν από ένα χρόνο, 673 00:22:11,590 --> 00:22:13,780 που έμοιαζε με αυτό. 674 00:22:13,780 --> 00:22:17,640 Τώρα, ας ρίξουμε μια προσέγγιση η λίγο περισσότερο σαν το βιβλίο εξετάσεις, 675 00:22:17,640 --> 00:22:21,122 σύμφωνα με την οποία ήμασταν συνεχώς επιλέγοντας το γράμμα του αλφαβήτου 676 00:22:21,122 --> 00:22:22,830 ότι το είδος ήθελε για να ασχοληθεί με την επόμενη. 677 00:22:22,830 --> 00:22:26,420 Ίσως ήταν ένα υψηλό επιστολή, όπως Α, ή ένα χαμηλό γράμμα Ζ 678 00:22:26,420 --> 00:22:28,170 >> Έτσι, ο καθένας είναι πίσω με αυτή τη σειρά. 679 00:22:28,170 --> 00:22:29,800 Και τώρα επιτρέψτε μου να το κάνουμε αυτό. 680 00:22:29,800 --> 00:22:34,880 Ας δούμε Ξέρω ότι έχω οκτώ αριθμούς εδώ. 681 00:22:34,880 --> 00:22:37,410 Πάω να πάει μπροστά και να απλά επιλέγουν συνειδητά 682 00:22:37,410 --> 00:22:38,520 τα μικρότερα στοιχεία. 683 00:22:38,520 --> 00:22:38,760 Σωστά; 684 00:22:38,760 --> 00:22:39,801 Αυτό φαίνεται πολύ έξυπνο. 685 00:22:39,801 --> 00:22:42,560 Γιατί δεν μπορώ να βρω το μικρότερο στοιχείο, βάλτε εκεί που ανήκει, 686 00:22:42,560 --> 00:22:45,280 στη συνέχεια να πάρει το επόμενο μικρότερο στοιχείο, βάλτε το οποίο ανήκει, και επαναλάβετε. 687 00:22:45,280 --> 00:22:46,820 >> Επειδή διαισθητικά, ότι θα πρέπει να εργαστεί πάρα πολύ. 688 00:22:46,820 --> 00:22:48,441 Έτσι τέσσερις, αυτό είναι ένα πολύ μικρό αριθμό. 689 00:22:48,441 --> 00:22:49,940 Πάω να θυμόμαστε από πού είναι αυτό. 690 00:22:49,940 --> 00:22:50,523 Περίμενε ένα λεπτό. 691 00:22:50,523 --> 00:22:51,577 Δύο είναι μικρότερη. 692 00:22:51,577 --> 00:22:53,910 Επιτρέψτε μου τώρα να θυμηθείτε πού τα δύο είναι, και να ξεχάσουμε τέσσερα. 693 00:22:53,910 --> 00:22:55,050 Θα αναφερθώ σε αυτό αργότερα. 694 00:22:55,050 --> 00:22:56,460 Έξι, δεν ενδιαφέρομαι. 695 00:22:56,460 --> 00:22:57,810 Οκτώ, δεν είμαι ενδιαφέρει. 696 00:22:57,810 --> 00:22:59,780 Το ένα είναι το νέο μου μικρό αριθμό. 697 00:22:59,780 --> 00:23:01,470 Έτσι, Πάω να θυμηθείτε πού το ένα είναι. 698 00:23:01,470 --> 00:23:02,534 Τρεις, δεν με ενδιαφέρει. 699 00:23:02,534 --> 00:23:03,450 Επτά, δεν με ενδιαφέρει. 700 00:23:03,450 --> 00:23:04,530 Πέντε, δεν με ενδιαφέρει. 701 00:23:04,530 --> 00:23:07,390 >> Έτσι, χωρίς να πέσουν το στάδιο του τρέχοντος έτους, 702 00:23:07,390 --> 00:23:09,890 Πάω να αρπάξει τον αριθμό ένα-- και ποιο ήταν το όνομά σας και πάλι; 703 00:23:09,890 --> 00:23:10,150 >> Ανάν Ανάν. 704 00:23:10,150 --> 00:23:11,220 >> David J. Malan: Ανάν. 705 00:23:11,220 --> 00:23:13,540 Και αν θα μπορούσατε να μου ενταχθούν στο η αρχή της λίστας, 706 00:23:13,540 --> 00:23:14,870 ας σας βάλει όπου ανήκετε. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- τι είναι το όνομά σου; 708 00:23:16,080 --> 00:23:16,650 >> ΣΤΕΦΑΝ: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> David J. Malan: Stefan είναι στο δρόμο. 710 00:23:18,191 --> 00:23:23,490 Έτσι, πριν λύνει αυτό Stefan πρόβλημα, τι πρέπει να κάνουμε; 711 00:23:23,490 --> 00:23:25,412 Τι θα κάνουμε με τον Stefan; 712 00:23:25,412 --> 00:23:27,269 >> Κοινό: [δεν ακούγεται]. 713 00:23:27,269 --> 00:23:28,060 David J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Έτσι θα μπορούσαμε να το κάνουμε αυτό. 715 00:23:28,850 --> 00:23:31,730 Θα μπορούσαμε είδος πάρει Stefan και του τέσσερα, και βάλτε την σε μια μεταβλητή 716 00:23:31,730 --> 00:23:33,530 και κρατήστε το για να κάποια ποσότητα χρόνου, 717 00:23:33,530 --> 00:23:35,220 καθιστώντας έτσι χώρο για το νούμερο ένα. 718 00:23:35,220 --> 00:23:36,280 Και αυτό δεν είναι κακό. 719 00:23:36,280 --> 00:23:39,270 Θα μπορούσα να προτείνω, γιατί να μην το κάνουμε εμείς απλά βάλτε Stefan εδώ; 720 00:23:39,270 --> 00:23:41,610 Γιατί αυτό παραβιάζει ένα από τις ιδέες που ξεκινήσαμε 721 00:23:41,610 --> 00:23:44,830 μιλάμε για τελευταία φορά, την περασμένη εβδομάδα; 722 00:23:44,830 --> 00:23:45,330 Ναι; 723 00:23:45,330 --> 00:23:45,740 >> Κοινό: [δεν ακούγεται]. 724 00:23:45,740 --> 00:23:46,860 >> David J. Malan: Δεν υπάρχει ευρετήριο για αυτό. 725 00:23:46,860 --> 00:23:49,735 Αν νομίζετε ότι αυτό, πράγματι, ως σειρά, αυτό είναι σαν αρνητικό, 726 00:23:49,735 --> 00:23:52,900 οπότε δεν υπάρχει μνήμη πραγματικότητα εδώ, αν αυτό είναι πράγματι ένας πίνακας, 727 00:23:52,900 --> 00:23:55,090 όπως δηλώσαμε την περασμένη εβδομάδα στη διάλεξη. 728 00:23:55,090 --> 00:23:56,250 Γι 'αυτό και δεν πρέπει να το κάνουμε αυτό. 729 00:23:56,250 --> 00:23:57,340 Θα μπορούσαμε να το αποθηκεύσετε σε μια μεταβλητή. 730 00:23:57,340 --> 00:23:57,820 >> Ή ξέρεις τι; 731 00:23:57,820 --> 00:23:59,153 Άκουσα κάποιον άλλο να το προτείνω. 732 00:23:59,153 --> 00:24:01,020 Τι άλλο θα μπορούσαμε να κάνουμε με τον Stefan; 733 00:24:01,020 --> 00:24:03,770 Γιατί δεν μπορούμε απλά να τον εκδιώξει και τον έβαλε πάνω στο οποίο ήταν νούμερο ένα. 734 00:24:03,770 --> 00:24:05,170 Έτσι, αν θέλετε να πάτε εκεί. 735 00:24:05,170 --> 00:24:07,300 Και πράγματι, αυτή είναι μια πολύ καλή λύση. 736 00:24:07,300 --> 00:24:10,480 Τώρα από τη μία πλευρά, έχω το είδος της έκανε το πρόβλημα χειρότερο. 737 00:24:10,480 --> 00:24:13,650 Τέσσερις είναι τώρα πιο μακριά από όπου θα πρέπει να είναι. 738 00:24:13,650 --> 00:24:14,900 Θα πρέπει να είναι προς αυτή ενός δεύτερου. 739 00:24:14,900 --> 00:24:16,100 >> Αλλά ξέρετε τι; 740 00:24:16,100 --> 00:24:17,630 Αυτό θα μπορούσε να ήταν κακή τύχη. 741 00:24:17,630 --> 00:24:18,822 Ίσως αριθμός οκτώ ήταν εδώ. 742 00:24:18,822 --> 00:24:20,530 Και έτσι, ίσως θα έχουν πάρει τυχερός, 743 00:24:20,530 --> 00:24:22,460 και ωθείται από οκτώ πιο κοντά στο τέλος. 744 00:24:22,460 --> 00:24:24,710 Έτσι, στο τέλος της ημέρας, το είδος των μέσων όρων όλων των έξω. 745 00:24:24,710 --> 00:24:26,085 Δεν χρειάζεται να νοιάζονται για τέσσερις. 746 00:24:26,085 --> 00:24:29,400 Το μόνο που νοιάζει τώρα είναι επιλέγοντας το μικρότερο στοιχείο. 747 00:24:29,400 --> 00:24:32,030 >> Και τώρα, τι Πάω να κάνουμε είναι να ξεχάσουμε το νούμερο ένα 748 00:24:32,030 --> 00:24:35,160 μόνιμα, γιατί ξέρω ότι η κατάλογος πίσω μου τώρα ταξινομημένο. 749 00:24:35,160 --> 00:24:36,720 Έτσι λίστα μου ήταν προηγουμένως μέγεθος οκτώ. 750 00:24:36,720 --> 00:24:37,720 Τώρα, αυτό είναι το μέγεθος των επτά. 751 00:24:37,720 --> 00:24:40,340 Έτσι, το πρόβλημά μου είναι να πάρει μικρότερες, αν και γραμμικά. 752 00:24:40,340 --> 00:24:43,022 Έτσι τώρα, θα πάω για να επιλέξετε το τρέχουσα μικρότερο στοιχείο, δύο. 753 00:24:43,022 --> 00:24:46,520 Έξι, οκτώ, τέσσερα, τρία, επτά, πέντε ετών. 754 00:24:46,520 --> 00:24:47,770 Αυτό ήταν το μικρότερο στοιχείο. 755 00:24:47,770 --> 00:24:49,416 Λοιπόν, τι θα πάω να κάνω with-- ό, τι ήταν το όνομά σας και πάλι; 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> David J. Malan: Joseph; 758 00:24:50,085 --> 00:24:52,000 Εμείς πάμε για να αφήσει στη θέση του Ιωσήφ. 759 00:24:52,000 --> 00:24:54,842 Τώρα, είμαι πρόκειται να προσποιηθώ ότι αυτοί οι τύποι are-- καλά, 760 00:24:54,842 --> 00:24:56,550 Ξέρω ότι αυτά τα δύο είναι ήδη ταξινομημένο. 761 00:24:56,550 --> 00:24:58,424 Ας εστιάσουμε τώρα για το υπόλοιπο της λίστας. 762 00:24:58,424 --> 00:25:00,080 Έξι είναι η τρέχουσα μικρότερο. 763 00:25:00,080 --> 00:25:01,190 Οκτώ είναι μεγαλύτερη. 764 00:25:01,190 --> 00:25:02,970 Τέσσερις είναι τώρα η τρέχουσα μικρότερο. 765 00:25:02,970 --> 00:25:04,762 Τρεις είναι τώρα η τρέχουσα μικρότερο. 766 00:25:04,762 --> 00:25:07,720 Και έτσι τώρα, πάω να επιλέξει τρεις, που is-- τι είναι και πάλι το όνομά σας; 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 David J. Malan: Serena, αν θα μπορούσατε πιάσε τον αριθμό και το swap του δικού σας with-- 769 00:25:10,620 --> 00:25:11,550 KALSANG: Kalsang. 770 00:25:11,550 --> 00:25:12,940 David J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Έλα πίσω, και είμαστε πρόκειται να ανταλλάξουν αυτά τα δύο. 772 00:25:15,220 --> 00:25:17,360 Και τώρα, ας βάλουμε αυτό στον αυτόματο πιλότο. 773 00:25:17,360 --> 00:25:21,589 Πάω να πάει και αφήστε το να σας παιδιά για να επιλέξετε το επόμενο μικρότερο στοιχεία. 774 00:25:21,589 --> 00:25:22,380 Dun, Dun, Dun, Dun. 775 00:25:22,380 --> 00:25:24,560 Αριθμός τέσσερα, τι πρέπει να κάνετε; 776 00:25:24,560 --> 00:25:26,261 Εξαιρετική. 777 00:25:26,261 --> 00:25:27,760 Τώρα, είμαι πρόκειται να κάνει άλλο ένα πέρασμα. 778 00:25:27,760 --> 00:25:28,590 Dun, Dun, Dun, Dun. 779 00:25:28,590 --> 00:25:31,465 Βλέπω πέντε είναι το αμέσως μικρότερο. 780 00:25:31,465 --> 00:25:32,840 Τώρα, είμαι πρόκειται να λάβει μια άλλη μπάλα. 781 00:25:32,840 --> 00:25:33,631 Dun, Dun, Dun, Dun. 782 00:25:33,631 --> 00:25:34,880 Έξι είναι το μικρότερο. 783 00:25:34,880 --> 00:25:35,520 Καλή. 784 00:25:35,520 --> 00:25:36,585 Επτά είναι το μικρότερο. 785 00:25:36,585 --> 00:25:37,085 Καμία αλλαγή. 786 00:25:37,085 --> 00:25:38,630 Οκτώ είναι το μικρότερο. 787 00:25:38,630 --> 00:25:39,170 Έγινε. 788 00:25:39,170 --> 00:25:43,900 >> Έτσι, αυτό που έχουμε κάνει ακριβώς με επαναληπτικά επιλέγοντας ένα στοιχείο μετά την άλλη 789 00:25:43,900 --> 00:25:47,230 έχει υλοποιήσει κάτι που είμαστε πρόκειται να επισημοποιηθεί ως ένα είδος επιλογής. 790 00:25:47,230 --> 00:25:49,120 Και αυτό είναι ίσως ακόμα απλούστερο να εξηγηθεί, 791 00:25:49,120 --> 00:25:51,310 από το γεγονός ότι κυριολεκτικά όλα όσα θέλετε να κάνετε είναι να κρατήσει μόνο 792 00:25:51,310 --> 00:25:54,700 πηγαίνοντας μπρος και πίσω στη λίστα την επιλογή, το επόμενο μικρότερο στοιχείο, 793 00:25:54,700 --> 00:25:55,720 μέχρι να τελειώσετε. 794 00:25:55,720 --> 00:25:58,650 >> Γι 'αυτό είναι ακόμα πιο απλή, ίσως διαισθητικά, από το τελευταίο. 795 00:25:58,650 --> 00:26:00,020 Ας δοκιμάσουμε μια τελευταία πρόταση. 796 00:26:00,020 --> 00:26:03,060 Εάν εσείς οι ίδιοι θα μπορούσαν να επαναφέρετε στις ακόλουθες θέσεις 797 00:26:03,060 --> 00:26:08,600 μία τελευταία φορά, ας δούμε αν δεν μπορούμε να τώρα να επισημοποιήσει μια άλλη προσέγγιση. 798 00:26:08,600 --> 00:26:12,857 Στην πραγματικότητα, θα ήταν κάποιος από εκεί ήθελα να προτείνω 799 00:26:12,857 --> 00:26:14,440 Πώς αλλιώς θα μπορούσαμε να το κάνουμε αυτό; 800 00:26:14,440 --> 00:26:17,439 Χωρίς να πετάξει έξω τσιτάτο ή είδος των απαντήσεων που είναι ήδη γνωστές, 801 00:26:17,439 --> 00:26:19,689 μόνο διαισθητικά, τι θα μπορούσαμε να κάνουμε; 802 00:26:19,689 --> 00:26:21,635 >> Κοινό: [δεν ακούγεται]. 803 00:26:21,635 --> 00:26:22,510 David J. Malan: Ναι. 804 00:26:22,510 --> 00:26:24,620 Έτσι, υπάρχει κάποια μεγάλη διαίσθηση εκεί. 805 00:26:24,620 --> 00:26:28,020 Τα καλά πράγματα φαίνεται να συμβαίνει μέχρι σήμερα στην επιστήμη των υπολογιστών, όταν χωρίζουμε 806 00:26:28,020 --> 00:26:30,832 και να κατακτήσει το πρόβλημα της διαίρεσης στη μέση και το μισό και το μισό. 807 00:26:30,832 --> 00:26:32,540 Και έτσι πράγματι, εμείς θα μπορούσε να αρχίσει να το κάνουμε αυτό. 808 00:26:32,540 --> 00:26:35,754 Και στην πραγματικότητα, αυτό πρόκειται να είναι, θα Βλέπετε, ένα από τα καλύτερα λύσεις μας ακόμα. 809 00:26:35,754 --> 00:26:37,420 Αλλά ας επανέλθω στο θέμα αυτό πριν από καιρό. 810 00:26:37,420 --> 00:26:40,500 Στην πραγματικότητα, θα πάμε να κάνουμε ότι λίγο αργότερα αυτή την εβδομάδα. 811 00:26:40,500 --> 00:26:42,180 Τι άλλο θα μπορούσαμε να κάνουμε για να λύσουμε αυτό; 812 00:26:42,180 --> 00:26:44,647 Έτσι, ο καθένας εδώ είναι φαινομενικά τυχαία σειρά. 813 00:26:44,647 --> 00:26:45,230 Ξέρεις τι? 814 00:26:45,230 --> 00:26:48,320 Αντί να πάει μπροστά και πίσω, εμπρός και πίσω, εμπρός και πίσω 815 00:26:48,320 --> 00:26:50,624 κάθε φορά, αυτό το αισθάνεται σαν Κάνω πολύ περπάτημα. 816 00:26:50,624 --> 00:26:52,790 Γιατί δεν μπορώ απλά ξεκινούν από η αρχή της λίστας, 817 00:26:52,790 --> 00:26:54,960 και απλά βάλτε τέσσερα όπου ανήκει; 818 00:26:54,960 --> 00:26:59,680 Επιτρέψτε μου λοιπόν να υποθέσουμε προς στιγμήν ότι λίστα μου είναι μόνο αυτό το πρώτο στοιχείο. 819 00:26:59,680 --> 00:27:04,937 Είναι τέσσερις ταξινομημένο σε αυτή τη χρονική στιγμή, αν όλα νοιάζει είναι πάντα εδώ; 820 00:27:04,937 --> 00:27:06,520 Αυτό είναι το είδος της κοινότοπα αληθινό, έτσι δεν είναι; 821 00:27:06,520 --> 00:27:10,000 Όπως και ο κατάλογος που περιέχει έναν αριθμό, και ότι ο αριθμός τέσσερα είναι προφανώς ταξινομημένο. 822 00:27:10,000 --> 00:27:13,070 >> Έτσι, επιτρέψτε μου να ορίζουν ότι ο κατάλογος αυτός είναι ταξινομημένο. 823 00:27:13,070 --> 00:27:15,090 Αλλά τώρα έχω το υπόλοιπο αυτής της λίστας. 824 00:27:15,090 --> 00:27:17,240 Μέχρι τώρα, έχω συναντήσει δύο. 825 00:27:17,240 --> 00:27:21,690 Πού δύο προφανώς ανήκουν σε σχέση με τέσσερα; 826 00:27:21,690 --> 00:27:22,580 Πριν από τέσσερα. 827 00:27:22,580 --> 00:27:23,862 Λοιπόν, τι μπορώ να κάνω εδώ; 828 00:27:23,862 --> 00:27:24,820 Ποιο είναι το όνομά σας και πάλι; 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> David J. Malan: Ιωσήφ, αν θα μπορούσατε να βήμα πίσω 831 00:27:26,030 --> 00:27:27,790 για μια στιγμή με τον αριθμό σας. 832 00:27:27,790 --> 00:27:31,130 Και τώρα τι πρέπει να κάνει ο Stefan εδώ; 833 00:27:31,130 --> 00:27:33,720 Ας αλλάξει τον Stefan εδώ. 834 00:27:33,720 --> 00:27:35,520 Και τώρα, ας Ιωσήφ έρθει εδώ. 835 00:27:35,520 --> 00:27:39,660 Και τώρα, επιτρέψτε μου να ισχυρίζονται ότι Όλα εδώ είναι ταξινομημένο. 836 00:27:39,660 --> 00:27:42,474 Έτσι, παρόμοιο αποτέλεσμα, αλλά μια ριζικά διαφορετική προσέγγιση. 837 00:27:42,474 --> 00:27:44,140 Δεν έχω καν εξεταστεί τι υπάρχει εκεί κάτω. 838 00:27:44,140 --> 00:27:46,310 Απλά συνεχίσετε να παίρνετε τα στοιχεία δεδομένου ότι είμαστε παρέδωσε σε μένα, 839 00:27:46,310 --> 00:27:47,240 και την αντιμετώπισή τους. 840 00:27:47,240 --> 00:27:48,330 >> Έτσι τώρα, βλέπω τον αριθμό έξι. 841 00:27:48,330 --> 00:27:51,110 Πού αριθμός έξι ανήκουν; 842 00:27:51,110 --> 00:27:53,250 Έχουμε δύο, τέσσερις, έξι. 843 00:27:53,250 --> 00:27:54,800 Ακριβώς, όπου αυτή είναι τώρα. 844 00:27:54,800 --> 00:27:57,750 Ας αφήσουμε αυτό από μόνο του, και τώρα ισχυρίζονται ότι αυτό το μέρος της λίστας 845 00:27:57,750 --> 00:27:58,772 Τώρα ταξινομημένο. 846 00:27:58,772 --> 00:28:01,230 Και έτσι, αυτό αισθάνεται θεμελιωδώς διαφορετικό από το γεγονός ότι είμαι μόνο 847 00:28:01,230 --> 00:28:05,230 κινείται μέσα στη λίστα εδώ γραμμικά, και είμαι ποτέ διπλασιασμό πίσω. 848 00:28:05,230 --> 00:28:05,730 Ναι. 849 00:28:05,730 --> 00:28:06,230 Εντάξει. 850 00:28:06,230 --> 00:28:08,190 Έτσι, οκτώ, όπου ανήκετε; 851 00:28:08,190 --> 00:28:08,730 Ακριβώς εδώ. 852 00:28:08,730 --> 00:28:09,310 Τέλεια. 853 00:28:09,310 --> 00:28:10,210 Μέχρι τώρα, ένα. 854 00:28:10,210 --> 00:28:10,900 Ωχ. 855 00:28:10,900 --> 00:28:13,010 Αυτό αισθάνεται σαν να είναι πρόκειται να είναι ακριβό. 856 00:28:13,010 --> 00:28:15,690 Τώρα, κατά το προηγούμενο αλγόριθμο, Απλά αντάλλαξαν ανθρώπους. 857 00:28:15,690 --> 00:28:18,648 Γι 'αυτό και θα μπορούσε να τον βάλει σε όλη τη διαδρομή σε η αρχή, αλλά στη συνέχεια μετακόμισε Ιωσήφ. 858 00:28:18,648 --> 00:28:21,450 Αλλά αν προχωρήσουμε Ιωσήφ, τώρα τι πρόκειται να είναι λάθος; 859 00:28:21,450 --> 00:28:24,250 >> Τώρα, έχω το είδος του undone-- έχω ένα βήμα προς τα εμπρός και, στη συνέχεια, 860 00:28:24,250 --> 00:28:26,300 ένα βήμα πίσω, γιατί τώρα Ιωσήφ θα είναι εκτός λειτουργίας. 861 00:28:26,300 --> 00:28:26,830 Ας το κάνουμε αυτό. 862 00:28:26,830 --> 00:28:29,150 Αν θα μπορούσατε να πάρετε το νούμερο ένα και βήμα πίσω για μια στιγμή. 863 00:28:29,150 --> 00:28:30,490 Πώς μπορούμε να put-- τι Ήταν το όνομά σας και πάλι; 864 00:28:30,490 --> 00:28:31,130 >> Ανάν Ανάν. 865 00:28:31,130 --> 00:28:32,610 >> David J. Malan: Ανάν στη θέση του; 866 00:28:32,610 --> 00:28:36,091 Τι πρέπει να γίνει με σεβασμό σε δύο, τέσσερα, έξι, οκτώ; 867 00:28:36,091 --> 00:28:37,570 Όλοι πρέπει να αλλάξει. 868 00:28:37,570 --> 00:28:42,590 Έτσι, εάν οκτώ θα ήθελα να μετατοπίσει πρώτη, στη συνέχεια, έξι, στη συνέχεια, τέσσερα, στη συνέχεια δύο. 869 00:28:42,590 --> 00:28:45,380 Και τότε Ανάν, αν θέλετε ήθελε να έρθει εδώ, καλά. 870 00:28:45,380 --> 00:28:47,760 Αλλά εδώ, έχουμε μόνο είδος κατέβαλε τιμή 871 00:28:47,760 --> 00:28:49,510 σε διαφορετικό σημείο στον αλγόριθμο. 872 00:28:49,510 --> 00:28:52,550 Λαμβάνοντας υπόψη ότι την τελευταία φορά με την επιλογή είδος, ακόμη και bubble sort, 873 00:28:52,550 --> 00:28:54,700 Περπατάω πίσω και εμπρός, εμπρός και πίσω, 874 00:28:54,700 --> 00:28:58,360 η οποία είναι σίγουρα προσθέτοντας χρόνο-σοφός, και κυριολεκτικά σταδιακά. 875 00:28:58,360 --> 00:29:00,660 >> Εισαγωγή είδος, κατά την πρώτη ματιά, μοιάζει να είναι 876 00:29:00,660 --> 00:29:05,150 σούπερ εξυπνότερα, ότι είμαι μόνο καθιστώντας την αργή, σταδιακή πρόοδο, 877 00:29:05,150 --> 00:29:07,120 αλλά εγώ δεν πρόκειται αυτό το πέρα ​​δώθε. 878 00:29:07,120 --> 00:29:09,410 Αλλά εάν κάποιος είναι πράγματι εκτός λειτουργίας, προειδοποίηση 879 00:29:09,410 --> 00:29:10,840 το σύνολο των εργασιών που απλά έπρεπε να κάνουμε. 880 00:29:10,840 --> 00:29:14,750 Έπρεπε να προχωρήσουμε μισό της λίστας απλά για να κάνει χώρο για το νούμερο ένα. 881 00:29:14,750 --> 00:29:16,790 Έτσι είναι το ίδιο ποσό της εργασίας έτσι στιγμής 882 00:29:16,790 --> 00:29:18,690 αισθάνεται, απλά ένα διαφορετικό είδος της εργασίας. 883 00:29:18,690 --> 00:29:19,370 >> Ας συνεχίσουμε. 884 00:29:19,370 --> 00:29:22,657 Μέχρι τώρα γνωρίζουμε ότι ο καθένας μεταξύ ενός και οκτώ ταξινομούνται. 885 00:29:22,657 --> 00:29:23,740 Εδώ, έχω το νούμερο τρία. 886 00:29:23,740 --> 00:29:25,864 Αν σας αρέσει να πάρει νούμερο τρία, ένα βήμα πίσω. 887 00:29:25,864 --> 00:29:28,260 Και τι εσείς πρέπει να κάνετε; 888 00:29:28,260 --> 00:29:28,760 Ναι. 889 00:29:28,760 --> 00:29:33,070 Έτσι, αυτό είναι άλλο ένα, δύο, τρία βήματα. 890 00:29:33,070 --> 00:29:36,010 Τρεις μονάδες του χρόνου που απλά κοστίζουν μένα, έτσι ώστε τρεις μπορούν τώρα να χωρέσουν. 891 00:29:36,010 --> 00:29:37,460 Τέλος, επτά. 892 00:29:37,460 --> 00:29:39,730 >> Ας πάμε μπροστά και να έχουν θα κάνουμε ένα βήμα πίσω. 893 00:29:39,730 --> 00:29:42,780 Αυτό είναι μόνο για να μας κοστίσει μία μονάδα του χρόνου, αλλά αυτό είναι εντάξει. 894 00:29:42,780 --> 00:29:44,170 Και τώρα, πέντε πρόκειται να να είναι λίγο πιο ακριβό. 895 00:29:44,170 --> 00:29:45,340 Αν θέλετε να βήμα πίσω. 896 00:29:45,340 --> 00:29:48,380 Πρέπει να προχωρήσουμε οκτώ, και επτά και έξι. 897 00:29:48,380 --> 00:29:50,749 Και τότε όλοι πλέον διευθετηθεί. 898 00:29:50,749 --> 00:29:52,290 Έτσι, ένα μεγάλο χέρι για να τους εθελοντές μας εδώ. 899 00:29:52,290 --> 00:29:53,554 Ευχαριστω παρα πολυ. 900 00:29:53,554 --> 00:29:56,220 >> [Χειροκρότημα] 901 00:29:56,220 --> 00:29:56,860 >> Σας ευχαριστώ όλους. 902 00:29:56,860 --> 00:29:57,520 Σας ευχαριστώ όλους. 903 00:29:57,520 --> 00:30:02,940 Ας δούμε τώρα πόσο δαπανηρή όλα αυτά ήταν. 904 00:30:02,940 --> 00:30:06,210 Ας εξετάσουμε ίσως η απλούστερη από αυτά, το είδος φούσκα. 905 00:30:06,210 --> 00:30:09,950 Και λέω πιο απλή, μόνο και μόνο επειδή μπορείτε να το λύσει λαίμαργα από μόνο 906 00:30:09,950 --> 00:30:11,660 διορθώσετε το πρόβλημα ζεύγη εδώ. 907 00:30:11,660 --> 00:30:13,720 Στερεώστε το πρόβλημα ζεύγη Εδώ, ξανά και ξανά 908 00:30:13,720 --> 00:30:17,680 και ξανά, επαναλαμβάνοντας όσες φορές χρειάζεται πραγματικά. 909 00:30:17,680 --> 00:30:21,050 >> Έτσι αποδεικνύεται ότι με ένα είδος φούσκα, καλά, 910 00:30:21,050 --> 00:30:25,820 πόσα βήματα πρέπει να κάνω αναλάβει το πρώτο πέρασμα του συγκεκριμένου αλγορίθμου; 911 00:30:25,820 --> 00:30:30,850 Θα ήθελα να take-- ας see-- μία, δύο, τρία, τέσσερα, πέντε, έξι, επτά. 912 00:30:30,850 --> 00:30:32,190 Και υπάρχουν οκτώ στοιχεία εδώ. 913 00:30:32,190 --> 00:30:35,280 Έτσι είναι σαν ν μείον 1 βήματα για να να πάρει από την αρχή της λίστας 914 00:30:35,280 --> 00:30:36,380 στο τέλος της λίστας. 915 00:30:36,380 --> 00:30:41,350 >> Αλλά με ταξινόμηση με επιλογή, να υπενθυμίσω ότι είμαι επιλέγοντας ξανά και ξανά τα στοιχεία 916 00:30:41,350 --> 00:30:44,590 και πάλι αυτό είναι μικρότερο, Είμαι το θέτει σε εφαρμογή, 917 00:30:44,590 --> 00:30:46,616 αλλά στη συνέχεια δεν είμαι κοιτάζοντας πίσω μου και πάλι. 918 00:30:46,616 --> 00:30:49,490 Έτσι, νομίζω ότι είναι λίγο πιο σαφής τότε η πρώτη φορά, θα ήθελα να 919 00:30:49,490 --> 00:30:52,680 πρέπει να λάβει όλα τα n μείον 1 βήματα για να βρείτε το μικρότερο στοιχείο. 920 00:30:52,680 --> 00:30:55,920 Στη συνέχεια, τα έβαλα στη θέση του, και εγώ εκδιώξει όποιος ήταν εδώ προηγουμένως. 921 00:30:55,920 --> 00:30:57,500 >> Αλλά τότε δεν έχω να συνεχίσετε να ψάχνετε σε αυτό το στοιχείο, 922 00:30:57,500 --> 00:30:59,040 γιατί ξέρω ότι είναι ήδη το μικρότερο. 923 00:30:59,040 --> 00:31:01,581 Έτσι τώρα, μπορώ να το δω σε μόλις επτά στοιχεία, στη συνέχεια, έξι στοιχεία, 924 00:31:01,581 --> 00:31:03,290 τότε πέντε στοιχεία, στη συνέχεια, τέσσερα στοιχεία. 925 00:31:03,290 --> 00:31:06,900 Και έτσι μαθηματικά, αν το n είναι ο αριθμός των στοιχείων ή αριθμών 926 00:31:06,900 --> 00:31:11,990 ότι ξεκινήσαμε με, μπορείτε να φανταστείτε ότι αυτό είναι το ίδιο όπως n μείον 1, 927 00:31:11,990 --> 00:31:14,250 συν n μείον 2 βήματα, συν η πλην 3 βήματα, 928 00:31:14,250 --> 00:31:16,780 συν n μείον 4 βήματα, όλη η διαδρομή προς ένα μόνο βήμα. 929 00:31:16,780 --> 00:31:18,160 Και είμαι στο τελευταίο πρόσωπο μου. 930 00:31:18,160 --> 00:31:20,650 >> Και αν θυμηθούμε ότι πολλοί Στατιστικά του βιβλία ή βιβλία μαθηματικών 931 00:31:20,650 --> 00:31:24,730 έχουν τους τύπους αυτούς για την hardcover πίσω ή μπροστά τους, 932 00:31:24,730 --> 00:31:27,690 αποδεικνύεται ότι αυτή τη σειρά μπορεί να εκφραστεί πιο απλά 933 00:31:27,690 --> 00:31:28,857 δεδομένου ότι οι χρόνοι n n μείον 1 σε 2. 934 00:31:28,857 --> 00:31:31,273 Και αυτό είναι καλό, αν αυτό δεν είναι στην πρώτη γραμμή του μυαλού σας. 935 00:31:31,273 --> 00:31:32,420 Αλλά αυτό είναι όντως αλήθεια. 936 00:31:32,420 --> 00:31:34,449 Αυτό είναι απλά ένας απλούστερος τρόπος της γραφής του. 937 00:31:34,449 --> 00:31:36,240 Και στη συνέχεια, αν νομίζετε ότι πίσω στο σχολείο βαθμού, 938 00:31:36,240 --> 00:31:38,698 όταν μόλις αρχίσει τον πολλαπλασιασμό τα πράγματα, αυτό φυσικά, 939 00:31:38,698 --> 00:31:41,820 είναι ακριβώς n τετράγωνο μείον ν διαιρείται δια 2. 940 00:31:41,820 --> 00:31:44,772 Όλα τα έχω κάνει είναι να επεκτείνουν οι εκφράσεις εκεί. 941 00:31:44,772 --> 00:31:46,730 Και γι 'αυτό ας ξαναγράψουμε αυτό λίγο διαφορετικά. 942 00:31:46,730 --> 00:31:49,780 Αυτό είναι n τετράγωνο διαιρείται δια 2 μείον n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Έτσι και πάλι, είμαι ακριβώς το είδος της εφαρμογής κάποια αριθμητική κυβερνά εκεί. 944 00:31:53,270 --> 00:31:57,140 Να σημειωθεί όμως ότι τώρα το μεγαλύτερο όρος σε αυτή την έκφραση, να το πω έτσι, 945 00:31:57,140 --> 00:31:58,540 είναι ότι n τετράγωνο. 946 00:31:58,540 --> 00:32:02,910 Ναι λοιπόν, είναι ν τετράγωνο διαιρούμενο με 2 μείον n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Αλλά γενικά, αν η είναι πρόκειται να είναι μια μεγάλη αξία, 948 00:32:05,080 --> 00:32:08,740 Πάω να ισχυριστεί ότι n τετράγωνο πρόκειται να είναι ο κυρίαρχος παράγοντας. 949 00:32:08,740 --> 00:32:10,490 Είναι ακριβώς πρόκειται να είναι μια μεγαλύτερη συμβολή 950 00:32:10,490 --> 00:32:12,877 με τον αριθμό των βημάτων από n / 2. 951 00:32:12,877 --> 00:32:13,960 Λοιπόν, τι εννοώ με αυτό; 952 00:32:13,960 --> 00:32:16,795 Ας δοκιμάσουμε ένα απλό παράδειγμα, ακόμη και αν και τα μαθηματικά παίρνει λίγο μεγάλο. 953 00:32:16,795 --> 00:32:20,210 >> Έτσι, ας υποθέσουμε ότι είχαμε 1 εκατομμύριο άνθρωποι στη σκηνή, ή 1 εκατομμύριο πράγματα 954 00:32:20,210 --> 00:32:21,320 ότι θέλουμε να λύσουμε. 955 00:32:21,320 --> 00:32:23,730 Ας συνδέσετε ένα εκατομμύριο σε αυτό ακριβώς το τύπο 956 00:32:23,730 --> 00:32:27,230 για να δείτε πόσα βήματα που χρειάζεται συνολική για να ταξινομήσετε ένα εκατομμύριο στοιχεία, χρησιμοποιώντας για παράδειγμα, 957 00:32:27,230 --> 00:32:28,560 ταξινόμηση με επιλογή. 958 00:32:28,560 --> 00:32:30,760 >> Έτσι θα είχαμε τον ίδιο τύπο όπως και πριν. 959 00:32:30,760 --> 00:32:34,120 Θα συνδέσετε ένα εκατομμύριο, έτσι ώστε να πάρω ένα εκατομμύριο τετράγωνο διαιρείται με 2, 960 00:32:34,120 --> 00:32:35,990 μείον ένα εκατομμύριο διαιρείται δια 2. 961 00:32:35,990 --> 00:32:40,180 Αν κάνω ότι τα μαθηματικά των προτέρων Εδώ, έχουμε 500 δισεκατομμύρια 962 00:32:40,180 --> 00:32:47,460 μείον 500.000, το οποίο μας δίνει 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 το οποίο είναι αρκετά μεγάλο καταριέται. 964 00:32:49,270 --> 00:32:54,370 >> Στην πραγματικότητα, αν συγκρίνουμε τώρα 499 δισεκατομμύρια, 999 εκατομμύρια, 965 00:32:54,370 --> 00:33:01,210 500.000 έναντι αρχικής αξίας μας, 500 δισεκατομμύρια, είναι τόσο βλασφημία κοντά. 966 00:33:01,210 --> 00:33:06,850 Σωστά; n τετράγωνο διαιρείται δια 2 δίνει ΕΜΕΙΣ-- ή μάλλον, ν τετράγωνο διαιρείται δια 2 967 00:33:06,850 --> 00:33:08,370 Μας έδωσαν 500 δισεκατομμύρια. 968 00:33:08,370 --> 00:33:13,510 Αυτό είναι αρκετά καταριέται κοντά σε 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 το οποίο είναι δηλαδή αφαίρεση off 500.000, ή γενικότερα, αφαιρώντας off 970 00:33:17,970 --> 00:33:20,010 n τετράγωνο, δεν είναι πραγματικά μια μεγάλη διαπραγμάτευση. 971 00:33:20,010 --> 00:33:22,490 Ο κ τετράγωνο που καθιστά αυτές τις αριθμοί μεγαλώνουν πολύ γρήγορα. 972 00:33:22,490 --> 00:33:25,790 >> Τώρα, αυτό είναι σημαντικό μόνο στο βαθμό όπως εμείς, ως επιστήμονες της πληροφορικής, 973 00:33:25,790 --> 00:33:29,350 γενικά δεν πρόκειται να νοιάζονται τόσο πολύ για τις αποχρώσεις αυτών των τύπων 974 00:33:29,350 --> 00:33:31,400 και ακριβώς ποια είναι η ακριβείς απαντήσεις είναι. 975 00:33:31,400 --> 00:33:33,390 Εμείς ενδιαφερόμαστε μόνο αυτό, ξέρετε τι; 976 00:33:33,390 --> 00:33:37,810 Στο τέλος της ημέρας, ο τύπος αυτός είναι της τάξης του n τετράγωνο. 977 00:33:37,810 --> 00:33:39,350 >> Ναι, είμαστε διαιρώντας με 2 εκεί. 978 00:33:39,350 --> 00:33:41,360 Ναι, είμαστε αφαιρώντας off n μείον 2. 979 00:33:41,360 --> 00:33:46,860 Αλλά στο τέλος της ημέρας, ο όρος ότι μας πληγώνει και μας κοστίζει πολύ 980 00:33:46,860 --> 00:33:48,995 πολλά βήματα είναι ότι το τετράγωνο όρος. 981 00:33:48,995 --> 00:33:51,370 Και έτσι ό, τι ένας επιστήμονας υπολογιστών πρόκειται να κάνουν γενικά 982 00:33:51,370 --> 00:33:54,160 έχει αγνοήσει όλα αυτά μικρότερα όρους ώστε, 983 00:33:54,160 --> 00:33:56,900 και απλά κοιτάξτε εκείνο που συμβάλλει τα μέγιστα στην κόστους. 984 00:33:56,900 --> 00:34:00,530 >> Και αυτό είναι καλό, επειδή μπορούμε τώρα μιλούν σε πολύ μεγαλύτερη γενικότητα 985 00:34:00,530 --> 00:34:02,470 σχετικά με αλγορίθμους και να τους συγκρίνετε. 986 00:34:02,470 --> 00:34:04,550 Και το γεγονός ότι είμαι χρησιμοποιώντας αυτό το O είναι σκόπιμη. 987 00:34:04,550 --> 00:34:06,680 Όταν λέω με τη σειρά του, είμαι ειδικά 988 00:34:06,680 --> 00:34:09,560 αναφέρεται σε κάτι που ονομάζεται μεγάλο O. Και η μεγάλη O 989 00:34:09,560 --> 00:34:14,090 είναι ένας συμβολισμός ότι ένας υπολογιστής επιστήμονας χρησιμοποιεί για να περιγράψει 990 00:34:14,090 --> 00:34:16,710 ένα άνω όριο για κάτι. 991 00:34:16,710 --> 00:34:21,150 >> Έτσι, αν σας πω ότι ένας αλγόριθμος είναι σε μεγάλο Ο Ν τετράγωνο, 992 00:34:21,150 --> 00:34:23,380 όπως πρότεινα απλά μια πριν από λίγο, ότι μέσα 993 00:34:23,380 --> 00:34:27,710 ότι από την άποψη της λειτουργίας του το χρόνο ή την αποτελεσματικότητά του, 994 00:34:27,710 --> 00:34:30,090 παίρνει με τη σειρά Ν τετράγωνο βήματα. 995 00:34:30,090 --> 00:34:31,420 Ίσως περισσότερο, ίσως και λιγότερο. 996 00:34:31,420 --> 00:34:33,435 Αλλά είναι της τάξης του n στο τετράγωνο. 997 00:34:33,435 --> 00:34:34,560 Και αυτό είναι το ανώτερο όριο. 998 00:34:34,560 --> 00:34:36,530 Δεν πρόκειται να είναι πιο επώδυνη από ό, τι αυτό. 999 00:34:36,530 --> 00:34:40,800 Δεν πρόκειται να είναι n στον κύβο, ή 2 στο n, ή κάτι πολύ μεγαλύτερο. 1000 00:34:40,800 --> 00:34:43,800 Αυτό είναι ένα άνω φράγμα σχετικά με ό, τι αυτό είναι το κόστος. 1001 00:34:43,800 --> 00:34:46,150 Έτσι, δεδομένου ότι, ας να εξετάσει μερικά μόνο παραδείγματα. 1002 00:34:46,150 --> 00:34:49,820 Και αυτό είναι μόνο μια πεπερασμένη λίστα των πολύ συχνές φορές τρέχει 1003 00:34:49,820 --> 00:34:52,870 για αλγορίθμους που είναι γραφτό να γίνει ενδεικτικά ορισμένα πράγματα που έχουμε 1004 00:34:52,870 --> 00:34:53,600 ήδη δει. 1005 00:34:53,600 --> 00:34:58,060 >> Έτσι, για παράδειγμα, στην περίπτωση της ταξινόμηση με επιλογή, τι είμαι υποστηρίζοντας εδώ 1006 00:34:58,060 --> 00:35:02,250 είναι σε λειτουργία αυτό το είδος της επιλογής ο χρόνος είναι της τάξης του n στο τετράγωνο. 1007 00:35:02,250 --> 00:35:06,260 Στη χειρότερη περίπτωση, Πάω να έχουν ένα σωρό τυχαίων αριθμών εδώ. 1008 00:35:06,260 --> 00:35:08,600 Και όπως είδαμε μαθηματικά, αν συνεχίσουμε με τα πόδια 1009 00:35:08,600 --> 00:35:11,310 μέσα στη λίστα, μέσω της λίστα, επιλέγοντας την επόμενη μικρότερη 1010 00:35:11,310 --> 00:35:14,410 στοιχείο ξανά και ξανά, αν μου στην πραγματικότητα γράψετε όλα τα βήματα 1011 00:35:14,410 --> 00:35:18,750 Παίρνω όπως είχα προτείνει formulaically πριν, είναι της τάξης του n στο τετράγωνο 1012 00:35:18,750 --> 00:35:20,370 βήματα που παίρνω. 1013 00:35:20,370 --> 00:35:24,520 >> Και αποδεικνύεται ότι φούσκα είδος και την εισαγωγή του είδους 1014 00:35:24,520 --> 00:35:27,370 είναι εξίσου αργή στη χειρότερη περίπτωση. 1015 00:35:27,370 --> 00:35:32,040 Σκεφτείτε, για παράδειγμα, ταξινόμηση με εισαγωγή, η τελευταία αλγόριθμος ασχοληθήκαμε με, 1016 00:35:32,040 --> 00:35:35,500 η οποία μας είχε εξετάσει το στοιχείο, και στη συνέχεια τοποθετήστε εκεί όπου ανήκει. 1017 00:35:35,500 --> 00:35:38,720 Και τότε κοίταξε το επόμενο στοιχείο, και εισάγεται εκεί όπου ανήκει. 1018 00:35:38,720 --> 00:35:40,990 >> Έτσι, θεωρούν το καλύτερο δυνατό σενάριο. 1019 00:35:40,990 --> 00:35:45,590 Ας υποθέσουμε ότι είχα εθελοντές μου παρατάξει κυριολεκτικά σαν αυτό, ένα από οκτώ, 1020 00:35:45,590 --> 00:35:47,440 ήδη διευθετηθεί. 1021 00:35:47,440 --> 00:35:51,300 Πόσα βήματα είναι είδος εισαγωγής πρόκειται να λάβει για να ταξινομήσετε τα οκτώ άτομα, 1022 00:35:51,300 --> 00:35:55,640 όταν φθάνουν στη σκηνή μοιάζοντας με αυτό; 1023 00:35:55,640 --> 00:35:57,410 >> Οκτώ άνθρωποι έχουν ήδη διευθετηθεί. 1024 00:35:57,410 --> 00:35:58,760 Και μπορώ να χρησιμοποιήσω το είδος εισαγωγής. 1025 00:35:58,760 --> 00:36:02,180 Η τελευταία των αλγορίθμων. 1026 00:36:02,180 --> 00:36:03,640 Λοιπόν, ας ενεργοποιηθούν εκ νέου πραγματικά γρήγορα. 1027 00:36:03,640 --> 00:36:05,504 Έτσι, αν αρχίσω εδώ, βλέπω ένα. 1028 00:36:05,504 --> 00:36:06,420 Πού μπορεί κανείς να ανήκει; 1029 00:36:06,420 --> 00:36:07,730 Ανήκει εδώ. 1030 00:36:07,730 --> 00:36:08,330 Βλέπω δύο. 1031 00:36:08,330 --> 00:36:09,660 Πού δύο ανήκουν; 1032 00:36:09,660 --> 00:36:10,260 Ακριβώς εδώ. 1033 00:36:10,260 --> 00:36:10,900 Βλέπω τρεις. 1034 00:36:10,900 --> 00:36:11,920 Πού τρεις ανήκουν; 1035 00:36:11,920 --> 00:36:12,480 Ακριβώς εδώ. 1036 00:36:12,480 --> 00:36:13,100 >> Βλέπω τέσσερα. 1037 00:36:13,100 --> 00:36:13,600 Ακριβώς εδώ. 1038 00:36:13,600 --> 00:36:15,660 Πέντε, έξι, επτά, οκτώ. 1039 00:36:15,660 --> 00:36:17,320 Δεν υπάρχει κανένας λόγος να επαναλαμβάνομαι. 1040 00:36:17,320 --> 00:36:21,260 Και ναι, πόσα βήματα είναι ότι από την άποψη της ν? 1041 00:36:21,260 --> 00:36:23,870 Είναι της τάξης του n βήματα, έτσι δεν είναι; n μείον 1. 1042 00:36:23,870 --> 00:36:27,567 Αλλά πήρα μια γραμμική σειρά της βήματα, και τώρα είμαι γίνει. 1043 00:36:27,567 --> 00:36:28,900 Έτσι, αυτό είναι η καλύτερη περίπτωση, όμως. 1044 00:36:28,900 --> 00:36:29,983 Τι γίνεται με την χειρότερη περίπτωση; 1045 00:36:29,983 --> 00:36:32,730 Τι οκτώ ήταν εκεί, και επτά ήταν εκεί κάτω, 1046 00:36:32,730 --> 00:36:35,840 και ένα και δύο ήταν εδώ, έτσι ότι ο κατάλογος ήταν πραγματικά αντιστραφεί; 1047 00:36:35,840 --> 00:36:38,300 >> Λοιπόν, τι θα συμβεί πράγματι αν αυτό είναι ο αριθμός; 1048 00:36:38,300 --> 00:36:41,300 Και εμείς θα κάνουμε μόνο μερικά παραδείγματα. 1049 00:36:41,300 --> 00:36:49,300 Τι θα συμβεί αν, πράγματι, ο αριθμός οκτώ είναι εδώ, και οι number-- κραυγών. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Τι κι αν, πράγματι, ο αριθμός οκτώ είναι όλος ο τρόπος εδώ, 1052 00:36:56,430 --> 00:36:57,790 και είμαι με τη χρήση ταξινόμησης εισαγωγή; 1053 00:36:57,790 --> 00:36:58,290 >> ΕΝΤΆΞΕΙ. 1054 00:36:58,290 --> 00:37:00,280 Ισχυρίζομαι αυτή τη στιγμή είναι στη θέση του. 1055 00:37:00,280 --> 00:37:03,152 Αλλά τώρα, seven-- πού επτά πάει; 1056 00:37:03,152 --> 00:37:04,360 Φυσικά, πηγαίνει εδώ. 1057 00:37:04,360 --> 00:37:06,760 Γι 'αυτό πρέπει να κινηθεί πάνω από οκτώ ένα μέρος. 1058 00:37:06,760 --> 00:37:08,554 Τώρα έξι, πού θα πάει; 1059 00:37:08,554 --> 00:37:09,220 Καλά, εντάξει. 1060 00:37:09,220 --> 00:37:13,150 Τώρα, έχω να κινηθεί πάνω από οκτώ ένα μέρος, και επτά πάνω από ένα μέρος, 1061 00:37:13,150 --> 00:37:14,440 και στη συνέχεια να γδούπος κάτω των έξι. 1062 00:37:14,440 --> 00:37:16,870 >> Έτσι, η πρώτη φορά, το κόστος Θέλω ένα βήμα για να διορθώσει τα πράγματα, 1063 00:37:16,870 --> 00:37:18,570 Στη συνέχεια μου κόστισε δύο βήματα για να διορθωθούν τα πράγματα. 1064 00:37:18,570 --> 00:37:20,370 Πόσα βήματα είναι πρόκειται να λάβει για να καθορίσει 1065 00:37:20,370 --> 00:37:22,720 πράγματα που πρέπει να βάλει πέντε στη σωστή θέση; 1066 00:37:22,720 --> 00:37:23,340 Τρεις. 1067 00:37:23,340 --> 00:37:29,520 Επειδή τώρα έχω να κινούνται το ένα, δύο, τρία. 1068 00:37:29,520 --> 00:37:32,430 Πόσα βήματα είναι αυτό που πρόκειται να πάρει να βάλει τέσσερα στη σωστή θέση; 1069 00:37:32,430 --> 00:37:36,040 4 συν 5 συν 6, 7 συν. 1070 00:37:36,040 --> 00:37:40,260 >> Και έτσι είναι πανομοιότυπη με αυτό που περιγράφεται για το είδος επιλογής. 1071 00:37:40,260 --> 00:37:42,130 Έχουμε αυτή τη σειρά αυτό είναι απλά αυξάνεται. 1072 00:37:42,130 --> 00:37:45,650 1 συν 2 συν 3 συν 4, ή αντιστρόφως, 7 συν 6 1073 00:37:45,650 --> 00:37:52,610 συν 5 συν 4 προσθέτει για τη σημερινή σκοπούς της τάξης των n τετράγωνο. 1074 00:37:52,610 --> 00:37:57,640 >> Επιτρέψτε μου λοιπόν να ορίζουν, επίσης, ότι bubble sort είναι επίσης n τετράγωνο. 1075 00:37:57,640 --> 00:38:01,340 Επειδή με bubble sort, κάθε φορά που πάω μέσα στη λίστα, 1076 00:38:01,340 --> 00:38:03,100 Παίρνω περίπου πόσα βήματα; 1077 00:38:03,100 --> 00:38:06,260 Κάθε φορά που κυριολεκτικά με τα πόδια από εκεί εκεί; 1078 00:38:06,260 --> 00:38:07,960 Περίπου n βήματα. 1079 00:38:07,960 --> 00:38:12,650 Αλλά πόσες φορές μπορεί να έχω πρέπει να περάσουν από τη λίστα; 1080 00:38:12,650 --> 00:38:13,920 >> Λοιπόν, περίπου n χρόνο. 1081 00:38:13,920 --> 00:38:15,680 Ίσως n μείον 1, αλλά περίπου φορές n. 1082 00:38:15,680 --> 00:38:16,430 Καλά, γιατί συμβαίνει αυτό; 1083 00:38:16,430 --> 00:38:19,560 Λοιπόν, με το bubble sort, εάν ξεκινάμε με bubble sort, 1084 00:38:19,560 --> 00:38:23,570 με τον κατάλογο με τον χειρότερο δυνατό κατάσταση, η οποία πάλι είναι εντελώς 1085 00:38:23,570 --> 00:38:25,550 προς τα πίσω, τι πρόκειται να συμβεί; 1086 00:38:25,550 --> 00:38:28,830 Θα περάσουν από τη λίστα, και τον αριθμό ένα ανήκει σε όλη τη διαδρομή εκεί. 1087 00:38:28,830 --> 00:38:33,280 >> Αλλά με bubble sort, κάνει πόσο μακριά προχωρήσουμε στην πρώτη μου πέρασμα από τη λίστα; 1088 00:38:33,280 --> 00:38:36,620 Πόσα σημεία δεν είχε πάρει πιο κοντά στη σωστή θέση; 1089 00:38:36,620 --> 00:38:37,240 Μόνο ένα. 1090 00:38:37,240 --> 00:38:40,281 Έτσι, αν το είδος του λόγου μέσα από αυτό, κάθε φορά μέσα από αυτόν τον αλγόριθμο, 1091 00:38:40,281 --> 00:38:41,880 Λαμβάνοντας περίπου n βήματα του Δαβίδ. 1092 00:38:41,880 --> 00:38:44,940 Αλλά πόσες κάρτες στη λίστα είναι αυτό 1093 00:38:44,940 --> 00:38:49,060 πρόκειται να λάβει για ένα έως φούσκα προς τα αριστερά, όπου ανήκει; 1094 00:38:49,060 --> 00:38:51,840 >> Πήρε να κινηθεί όπως, n χώρους με αυτόν τον τρόπο. 1095 00:38:51,840 --> 00:38:57,960 Έτσι απλά για να κάνουν την ταξινόμηση της λίστας, Θα πρέπει να περπατήσετε πέρα ​​δώθε n φορές. 1096 00:38:57,960 --> 00:39:01,540 Και κάθε φορά, είμαι κοιτάζοντας n στοιχεία. 1097 00:39:01,540 --> 00:39:05,410 Έτσι, κάνουμε τα πράγματα n n φορές η σειρά των n τετράγωνο. 1098 00:39:05,410 --> 00:39:07,220 >> Τώρα, θα δούμε σε μερικά των σορτς ότι 1099 00:39:07,220 --> 00:39:10,440 Τα ενσωματωμένα στο επόμενο πρόβλημα του CS50 που, μια άλλη προσέγγιση σε αυτά, 1100 00:39:10,440 --> 00:39:13,490 αλλά για τώρα, ας εξετάσουμε κάποιες άλλες φορές το τρέξιμο, 1101 00:39:13,490 --> 00:39:16,840 ειδικά εάν οι διαλογής αυτά λαμβάνουν λίγο χρόνο για να βυθιστεί σε. 1102 00:39:16,840 --> 00:39:21,790 Τι είναι ένας αλγόριθμος που έχουμε ήδη δει ότι αναλαμβάνει την σειρά των βημάτων n; 1103 00:39:21,790 --> 00:39:27,560 >> Τι θα πρέπει να λάβει μια γραμμική σειρά βήματα που έχουμε δει μέχρι τώρα; 1104 00:39:27,560 --> 00:39:29,350 Τι είναι αυτό? 1105 00:39:29,350 --> 00:39:30,480 Η αναζήτηση τηλεφωνικό κατάλογο. 1106 00:39:30,480 --> 00:39:31,390 Ο πρώτος αλγόριθμος. 1107 00:39:31,390 --> 00:39:31,560 Σωστά; 1108 00:39:31,560 --> 00:39:33,650 Πού είμαστε γραμμικά ψάχνουν για Mike Smith; 1109 00:39:33,650 --> 00:39:34,150 Πράγματι. 1110 00:39:34,150 --> 00:39:37,180 Από την εβδομάδα μηδέν, όταν άρχισα γυρίζοντας μία σελίδα τη φορά, 1111 00:39:37,180 --> 00:39:40,095 και μου είπε ακόμη ότι ήταν το είδος ενός αλγορίθμου γραμμικής συναίσθημα, 1112 00:39:40,095 --> 00:39:42,720 και είχαμε αυτή την εικόνα για το Διοικητικό Συμβούλιο με την ευθεία κόκκινη γραμμή 1113 00:39:42,720 --> 00:39:44,678 και την ευθεία κίτρινο γραμμή, αυτές ήταν πράγματι 1114 00:39:44,678 --> 00:39:46,810 αλγόριθμους που είναι σε μεγάλο Ο Ν. 1115 00:39:46,810 --> 00:39:50,680 >> Διότι για να βρείτε Mike Smith σε ένα τηλέφωνο το βιβλίο του Ν σελίδες, στη χειρότερη περίπτωση, 1116 00:39:50,680 --> 00:39:52,422 θα μπορούσε να μου πάρει n βήματα. 1117 00:39:52,422 --> 00:39:53,630 Τι γίνεται με τη λήψη παρουσιών; 1118 00:39:53,630 --> 00:39:55,790 Ενα δυο τρια ΤΕΣΣΕΡΑ πεντε εξι. 1119 00:39:55,790 --> 00:39:59,420 Τι είναι ο χρόνος εκτέλεσης αυτού αλγόριθμος για τη λήψη παρουσιών; 1120 00:39:59,420 --> 00:40:03,070 Big O του n, επειδή θεωρητικά I Πρέπει να επισημάνω όλοι στην αίθουσα. 1121 00:40:03,070 --> 00:40:05,861 >> Τώρα, ως ένα μέρος, τι γίνεται με το άλλα βελτιστοποίησης από την εβδομάδα το μηδέν; 1122 00:40:05,861 --> 00:40:08,117 Δύο, τέσσερις, έξι, οκτώ, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Ένας επιστήμονας υπολογιστών θα συνειδητοποιούν, περιμένετε ένα λεπτό, 1124 00:40:10,200 --> 00:40:12,320 ότι είναι της τάξης των n διαιρείται με δύο βήματα. 1125 00:40:12,320 --> 00:40:12,820 Σωστά; 1126 00:40:12,820 --> 00:40:14,444 Επειδή κάνω δύο ανθρώπους σε μια στιγμή. 1127 00:40:14,444 --> 00:40:17,015 Αλλά θα πάμε να αγνοήσει αυτές οι χαμηλότερες όρους ώστε, 1128 00:40:17,015 --> 00:40:19,140 και είμαστε ακριβώς πρόκειται να πετάτε τη διαίρεση δια 2, 1129 00:40:19,140 --> 00:40:21,830 και απλώς να πω, μεγάλη O Ν για την εν λόγω αλγόριθμος, καθώς και. 1130 00:40:21,830 --> 00:40:22,760 >> Τι λέτε για αυτό? 1131 00:40:22,760 --> 00:40:26,170 Θα υπερπηδήσει ορισμένα από αυτά, αλλά τι Ήταν ένας αλγόριθμος που ήταν καταγραφής των n; 1132 00:40:26,170 --> 00:40:29,900 Αυτό πήρε περίπου log n βήματα; 1133 00:40:29,900 --> 00:40:30,870 Το διαίρει και βασίλευε. 1134 00:40:30,870 --> 00:40:31,369 Ακριβώς. 1135 00:40:31,369 --> 00:40:33,900 Όπως και το παράδειγμα τηλεφωνικό κατάλογο εβδομάδα μηδέν και νωρίτερα σήμερα, 1136 00:40:33,900 --> 00:40:36,191 όπου χωρίζεται το πρόβλημα ξανά και ξανά και ξανά. 1137 00:40:36,191 --> 00:40:39,070 Εμείς επέστησε στο διοικητικό συμβούλιο εβδομάδα μηδέν ως ένα καμπύλο πράσινη γραμμή, 1138 00:40:39,070 --> 00:40:41,460 και είπαμε ότι την ημέρα ήταν μια λογαριθμική αλγόριθμος. 1139 00:40:41,460 --> 00:40:44,970 >> Και πράγματι, ο αριθμός των βημάτων που απαιτείται για την εκτέλεση διαίρει και βασίλευε, 1140 00:40:44,970 --> 00:40:48,610 ή δυαδική αναζήτηση, όπως θα αρχίσουμε χαρακτηρίζοντάς, όπως στον τηλεφωνικό κατάλογο, 1141 00:40:48,610 --> 00:40:50,680 είναι της τάξης του log και τα βήματα. 1142 00:40:50,680 --> 00:40:52,470 Και αυτό είναι ένα κομμάτι από ένα παράξενο μία. 1143 00:40:52,470 --> 00:40:54,910 >> Τι φέρνει ένα βήμα, ή πιο συγκεκριμένα 1144 00:40:54,910 --> 00:40:56,240 ένας σταθερός αριθμός βήματα; 1145 00:40:56,240 --> 00:40:58,865 Ίσως είναι δύο, ίσως είναι τρεις, αλλά ένας επιστήμονας υπολογιστών μόνο 1146 00:40:58,865 --> 00:41:01,423 απλοποιεί τόσο μεγάλο O 1, μερικοί σταθερό αριθμό βημάτων. 1147 00:41:01,423 --> 00:41:04,256 Τι είναι κάτι που θα μπορούσε να κάνει ότι παίρνει ένα σταθερό αριθμό βημάτων; 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Τι είναι ο χρόνος εκτέλεσης του παλαμάκια; 1150 00:41:10,930 --> 00:41:11,920 Σταθερά χρόνου. 1151 00:41:11,920 --> 00:41:12,420 Σωστά; 1152 00:41:12,420 --> 00:41:15,490 Όπως, τι είναι ο χρόνος εκτέλεσης της κάνει κάτι που διαρκεί μόλις ένα 1153 00:41:15,490 --> 00:41:18,570 λειτουργία, όπως εκτύπωση F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Αυτό θα μπορούσε να ειπωθεί ότι είναι σταθερά χρόνου, εκτός μικρότερη γωνία με την περίπτωση εκτύπωσης F, 1155 00:41:24,110 --> 00:41:28,260 Τι θα μπορούσε ο χρόνος τρέχει της εκτύπωσης F πραγματικά είναι; 1156 00:41:28,260 --> 00:41:28,790 Και γιατι? 1157 00:41:28,790 --> 00:41:30,550 Τι είναι n μετρήσεων στην περίπτωση αυτή; 1158 00:41:30,550 --> 00:41:32,251 >> Κοινό: [δεν ακούγεται]. 1159 00:41:32,251 --> 00:41:33,250 David J. Malan: Ακριβώς. 1160 00:41:33,250 --> 00:41:34,900 Ο αριθμός των χαρακτήρων που θέλετε να εκτυπώσετε. 1161 00:41:34,900 --> 00:41:36,191 Έτσι είναι πολύ περιβάλλοντος. 1162 00:41:36,191 --> 00:41:39,910 Σήμερα, έχουμε εστιάζοντας πολύ για γράμματα και αριθμούς εδώ στο διοικητικό συμβούλιο. 1163 00:41:39,910 --> 00:41:43,540 Αλλά θα μπορούσε επίσης να είναι χαρακτήρες σε μια πραγματική σειρά. 1164 00:41:43,540 --> 00:41:46,420 Έτσι αποδεικνύεται ότι υπάρχει μια άλλη μέτρο που θα αρχίσουν να νοιάζονται για, 1165 00:41:46,420 --> 00:41:48,530 και αυτό είναι το αντίθετο των μεγάλων O, να το πω έτσι. 1166 00:41:48,530 --> 00:41:50,120 >> Αυτό είναι το ωμέγα σημειογραφία. 1167 00:41:50,120 --> 00:41:53,380 Λαμβάνοντας υπόψη ότι η μεγάλη O σημαίνει ό, τι είναι, η άνω όριο για το χρόνο λειτουργίας σας; 1168 00:41:53,380 --> 00:41:55,580 Στο μέγιστο βαθμό, πόσο χρόνο θα μπορούσε να πάρει κάτι; 1169 00:41:55,580 --> 00:41:59,250 Omega-- συγγνώμη αυτό εξακολουθεί να βγαίνει up-- είναι το αντίθετο από αυτό, 1170 00:41:59,250 --> 00:42:02,960 σύμφωνα με την οποία είναι ένα κάτω φράγμα για το χρονικό διάστημα κάτι που θα μπορούσε να λάβει. 1171 00:42:02,960 --> 00:42:10,480 >> So. Για παράδειγμα, τι είναι ένας αλγόριθμος ότι παίρνει πάντα ν τετράγωνο βήματα; 1172 00:42:10,480 --> 00:42:15,600 Λοιπόν, ένας από τους αλγορίθμους που έχουμε δει Σήμερα, στην πραγματικότητα, μπορεί να είναι ότι, καθώς και. 1173 00:42:15,600 --> 00:42:16,720 Επιλογή είδους. 1174 00:42:16,720 --> 00:42:18,270 Επιλογή του είδους είναι αρκετά χαζός. 1175 00:42:18,270 --> 00:42:21,760 Ακόμη και αν η algorithm-- συγγνώμη, ακόμη και αν ο πίνακας είναι ήδη ταξινομημένο, 1176 00:42:21,760 --> 00:42:24,150 ταξινόμηση με επιλογή πρόκειται να να τηρούν το περπάτημα μέσα από τη λίστα 1177 00:42:24,150 --> 00:42:28,907 για να βεβαιωθείτε ότι έχει το μικρότερο στοιχείο ξανά και ξανά και ξανά. 1178 00:42:28,907 --> 00:42:31,740 Και ακόμα κι αν οι άνθρωποι στην Γνωρίζουμε ότι το κοινό, περιμένετε ένα λεπτό, 1179 00:42:31,740 --> 00:42:33,948 έχετε ήδη περάσει το μικρότερο στοιχείο, ο υπολογιστής 1180 00:42:33,948 --> 00:42:37,300 δεν ξέρει ότι μέχρι να φαίνεται σε όλη τη διαδρομή μέσα από τη λίστα. 1181 00:42:37,300 --> 00:42:40,240 Ομοίως, ένα κάτω φράγμα ότι θα μπορούσαν επίσης να ληφθούν υπόψη 1182 00:42:40,240 --> 00:42:42,000 μπορεί να είναι γραμμικό χρόνο. 1183 00:42:42,000 --> 00:42:48,260 >> Πόσος χρόνος χρειάζεται για να Ταξινόμηση n στοιχεία με τον καλύτερο 1184 00:42:48,260 --> 00:42:52,420 περίπτωση χρησιμοποιώντας κάτι σαν φούσκα είδος; 1185 00:42:52,420 --> 00:42:54,280 Ας υποθέσουμε λίστα σας είναι ήδη ταξινομημένο. 1186 00:42:54,280 --> 00:42:56,696 Είπαμε bubble sort παίρνει η σειρά των βημάτων n τετράγωνο. 1187 00:42:56,696 --> 00:42:59,640 Αλλά τι εάν είναι ήδη ταξινομημένο; 1188 00:42:59,640 --> 00:43:02,310 Τι γίνεται αν έχετε συνειδητοποιήσει μετά ένα πέρασμα από τη συστοιχία 1189 00:43:02,310 --> 00:43:03,540 ότι έχετε κάνει καμία swaps; 1190 00:43:03,540 --> 00:43:05,970 Μήπως θα πρέπει να συνεχίσει να κάνει περισσότερα περάσματα; 1191 00:43:05,970 --> 00:43:06,470 >> Κανένα. 1192 00:43:06,470 --> 00:43:10,340 Έτσι, ένα κάτω φράγμα για bubble sort θα μπορούσε να ειπωθεί ότι είναι γραμμική. 1193 00:43:10,340 --> 00:43:11,830 Ωμέγα του ν. 1194 00:43:11,830 --> 00:43:14,450 Και μπορούμε να εξετάσουμε άλλοι από αυτούς, καθώς και. 1195 00:43:14,450 --> 00:43:17,990 Έτσι, ας ρίξουμε μια γρήγορη ματιά σε μόλις ένα οπτικοποίηση εδώ 1196 00:43:17,990 --> 00:43:20,790 για να δούμε πώς αυτές διακρίνουν τους εαυτούς τους. 1197 00:43:20,790 --> 00:43:24,592 Πάω να πάει κάτω σε αυτό εδώ σελίδα που είναι διαθέσιμη στην ιστοσελίδα του C50, 1198 00:43:24,592 --> 00:43:27,550 αλλά θα είναι ένας πόνος για να πάρει εργασίας, δεδομένου ότι χρησιμοποιεί μια τεχνολογία που ονομάζεται 1199 00:43:27,550 --> 00:43:30,560 Βοηθητικές εφαρμογές Java, η οποία είναι μια σε μεγάλο βαθμό δεν υποστηρίζεται αυτές τις μέρες, 1200 00:43:30,560 --> 00:43:32,730 τουλάχιστον από το Chrome και ορισμένα άλλα. 1201 00:43:32,730 --> 00:43:37,070 >> Και επιτρέψτε μου να πάει μπροστά και να επιταχύνει τη και να εξηγήσει τι συμβαίνει. 1202 00:43:37,070 --> 00:43:40,840 Αυτό είναι μια απόδειξη της φούσκας είδος, ο πρώτος αλγόριθμος κοιτάξαμε. 1203 00:43:40,840 --> 00:43:43,950 Και είναι μια απεικόνιση από το ότι κάθε αυτών των ράβδων αντιπροσωπεύει έναν αριθμό. 1204 00:43:43,950 --> 00:43:45,710 Όσο μεγαλύτερη είναι η γραμμή, ο μεγαλύτερος αριθμός. 1205 00:43:45,710 --> 00:43:47,520 Όσο μικρότερη είναι η γραμμή, όσο μικρότερος είναι ο αριθμός. 1206 00:43:47,520 --> 00:43:50,353 Και τι μπορείτε να δείτε οπτικά, ακόμη και αν αυτό πρόκειται σούπερ γρήγορο, 1207 00:43:50,353 --> 00:43:53,699 είναι ότι η κόκκινη γραμμή είναι σαν κι εμένα, περπάτημα πέρα ​​δώθε τον καθορισμό των προβλημάτων. 1208 00:43:53,699 --> 00:43:56,740 Μπορείτε να δείτε ότι οι μεγαλύτερες στοιχεία πράγματι αναβλύζει προς τα δεξιά, 1209 00:43:56,740 --> 00:43:59,650 και τα μικρότερα στοιχεία Οι αναβλύζει προς τα αριστερά. 1210 00:43:59,650 --> 00:44:01,870 Και εδώ κάτω, αν θέλουμε πραγματικά εξετάσουμε πιο προσεκτικά, 1211 00:44:01,870 --> 00:44:04,330 μπορούμε πραγματικά να μετρήσει το αριθμός των συγκρίσεων και ανταλλαγές 1212 00:44:04,330 --> 00:44:05,350 ότι γίνονταν. 1213 00:44:05,350 --> 00:44:07,360 >> Αλλά αντ 'αυτού, ας ρίξουμε μια ματιά στο δεύτερο αλγόριθμο 1214 00:44:07,360 --> 00:44:11,240 κοιτάξαμε νωρίτερα με μας εθελοντές, ταξινόμηση με επιλογή. 1215 00:44:11,240 --> 00:44:13,500 Οπτικά, έχει ένα πολύ διαφορετικό αποτέλεσμα. 1216 00:44:13,500 --> 00:44:16,820 Αλλά είναι, και πάλι, πολύ έξυπνο, σε ότι θα συνεχίσουμε να επιλέγετε το επόμενο μικρότερο 1217 00:44:16,820 --> 00:44:18,660 στοιχείο, και πήραμε λίγο τυχερός. 1218 00:44:18,660 --> 00:44:20,110 Αυτό αισθάνθηκε θεμελιωδώς πιο γρήγορα. 1219 00:44:20,110 --> 00:44:22,840 Αλλά αν έτρεξε αυτό ξανά και ξανά και πάλι με πολλές εισόδους, 1220 00:44:22,840 --> 00:44:26,680 θα δείτε ότι είναι πράγματι ακόμα σε μεγάλο O Ν τετράγωνο. 1221 00:44:26,680 --> 00:44:29,920 >> Ας κάνουμε ένα τελευταίο Εδώ, ταξινόμηση με εισαγωγή, 1222 00:44:29,920 --> 00:44:33,180 η οποία ήταν η τρίτη αλγόριθμος κοιτάξαμε και ανάκληση 1223 00:44:33,180 --> 00:44:36,700 ότι αυτό ασχολείται με το στοιχεία όπως τα συναντά, 1224 00:44:36,700 --> 00:44:39,290 αλλά τότε ίσως βάρδιες πράγματα για να κάνει το χώρο, 1225 00:44:39,290 --> 00:44:41,660 εισάγοντας τα στοιχεία εκεί που ανήκουν. 1226 00:44:41,660 --> 00:44:45,330 >> Και αυτό τελειώνει πολύ να δίνει το τελικό αποτέλεσμα. Τώρα και οι τρεις από αυτούς 1227 00:44:45,330 --> 00:44:46,490 αισθάνθηκα πολύ γρήγορα. 1228 00:44:46,490 --> 00:44:48,740 Και πράγματι, εγώ τους έτρεξε σε μια πολύ καλή κλιπ. 1229 00:44:48,740 --> 00:44:52,510 Αλλά ουσιαστικά, είναι όλα αρκετά φρικτό, για να είμαι ειλικρινής. 1230 00:44:52,510 --> 00:44:56,960 Όλες αυτές οι αλγόριθμοι μέχρι στιγμής που εκτελούνται σε μεγάλες O Ν τετράγωνο 1231 00:44:56,960 --> 00:44:59,270 λαμβάνει αρκετά ένα κομμάτι της χρόνο για να τρέξει στο τέλος. 1232 00:44:59,270 --> 00:45:01,920 >> Και πράγματι, μπορούμε να δούμε και να αισθάνονται αυτό το τέλος 1233 00:45:01,920 --> 00:45:04,090 αν έχω σηκώσει αυτό το τρίτο και τελευταίο demo. 1234 00:45:04,090 --> 00:45:05,840 Αυτό είναι ένα άλλο απεικόνισης που πρόκειται 1235 00:45:05,840 --> 00:45:08,500 να δείξει bubble sort στα αριστερά, ταξινόμηση με επιλογή στη μέση, 1236 00:45:08,500 --> 00:45:13,410 και κάτι, ως ένας από μας χέρι εγείρει νωρίτερα πρότεινε, 1237 00:45:13,410 --> 00:45:15,020 ταξινόμηση με συγχώνευση στα δεξιά. 1238 00:45:15,020 --> 00:45:16,937 Μια διαίρει και βασίλευε στρατηγικής στα δεξιά. 1239 00:45:16,937 --> 00:45:19,520 Και αυτό είναι, στην πραγματικότητα, αυτό που είμαστε πρόκειται να εξετάσουμε την Τετάρτη. 1240 00:45:19,520 --> 00:45:21,990 Αλλά ας το χρόνο αυτά να λειτουργούν παράλληλα. 1241 00:45:21,990 --> 00:45:26,765 Είναι περίπου ο ίδιος αριθμός στοιχεία, όλα τρέχουν ταυτόχρονα. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs επιλογή Ταξινόμηση vs ταξινόμηση με συγχώνευση. 1244 00:45:34,440 --> 00:45:36,760 >> Τώρα, από όπου και αν όλα τα ρέοντα θεωρητικά ταυτόχρονα. 1245 00:45:36,760 --> 00:45:39,830 Η CPU τρέχει σε την ίδια ταχύτητα, αλλά θα 1246 00:45:39,830 --> 00:45:44,014 μπορεί να αισθανθεί πόσο βαρετή είναι πολύ γρήγορα θα γίνει, 1247 00:45:44,014 --> 00:45:45,930 και πόσο γρήγορα όταν θα εισφέρει ένα κομμάτι της εβδομάδας 1248 00:45:45,930 --> 00:45:49,330 αλγόριθμοι μπορούν να το μηδέν θα επιταχυνθούν τα πράγματα. 1249 00:45:49,330 --> 00:45:51,760 >> Και τώρα ας συγκρίνουμε αυτά σε μια τελευταία μορφή. 1250 00:45:51,760 --> 00:45:55,710 Πάω να πάει μπροστά στην ιστοσελίδα CS50, όπου 1251 00:45:55,710 --> 00:45:59,020 έχουμε αυτό το τελευταίο σύνδεσμο για σήμερα, όπου κάποιος στο διαδίκτυο 1252 00:45:59,020 --> 00:46:03,960 Παρακαλούνται βάλει μαζί ένα βίντεο που συλλαμβάνει τι διαφορετικό διαλογής 1253 00:46:03,960 --> 00:46:07,510 αλγόριθμοι ακούγεται. 1254 00:46:07,510 --> 00:46:09,577 Αυτό είναι το είδος εισαγωγής. 1255 00:46:09,577 --> 00:46:12,072 >> [Beeping] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Σύμφωνα με την οποία θέλετε να εφαρμόσετε μια συχνότητα με βάση το ύψος της ράβδου bar. 1258 00:46:16,850 --> 00:46:19,826 Αυτό είναι bubble sort. 1259 00:46:19,826 --> 00:46:21,822 >> [Στραβωμένος να χτυπάει] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Προσεχώς is-- έρχονται μέχρι την επόμενη is-- ταξινόμηση με επιλογή, 1262 00:46:45,774 --> 00:46:48,820 όπου και πάλι, είμαστε επιλέγοντας Το επόμενο μικρότερο στοιχείο, 1263 00:46:48,820 --> 00:46:51,820 και μπορούμε να δούμε την αυξανόμενη από αριστερά προς τα δεξιά. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Ταξινόμηση με συγχώνευση, έτσι νικητής μας πολύ σήμερα. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Παρατηρήστε πώς είναι τα πράγματα διαιρώντας σε [δεν ακούγεται] μισά και τέταρτα. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome είδος, το οποίο δεν έχουμε μίλησε για, και δημιουργεί οπτικά 1270 00:47:21,660 --> 00:47:24,450 και audally ένα κομμάτι από ένα διαφορετικό σχήμα και ήχο. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Πηγαίνοντας πίσω και εμπρός, καθαρισμού πράγματα. 1273 00:47:30,160 --> 00:47:32,230 Επίσης, ελέγξτε έξω heapsort στην ιστοσελίδα του άντρα. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Και αυτό είναι όλο. 1276 00:47:36,810 --> 00:47:38,210 Θα σας δούμε την επόμενη φορά. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing ΚΑΙ ΜΟΥΣΙΚΗ] 1279 00:47:48,334 --> 00:50:24,839