1 00:00:00,000 --> 00:00:11,100 >> [Παίζει μουσική] 2 00:00:11,100 --> 00:00:11,490 >> David J. MALAN: Εντάξει. 3 00:00:11,490 --> 00:00:12,170 Έτσι καλωσορίσω πίσω. 4 00:00:12,170 --> 00:00:15,180 Αυτό είναι CS50, και το είναι το τέλος της τρίτης εβδομάδας. 5 00:00:15,180 --> 00:00:17,770 >> Έτσι, υπενθυμίζουν τις τελευταίες αρκετές εβδομάδες, έχουμε δαπανήσει αρκετά ένα κομμάτι της 6 00:00:17,770 --> 00:00:20,820 φορά στο C, σχετικά με τον προγραμματισμό, για τη σύνταξη. 7 00:00:20,820 --> 00:00:24,680 Και αυτό είναι απολύτως φυσιολογικό, εάν είστε ακόμα αγωνίζεται με Set Πρόβλημα 2, να 8 00:00:24,680 --> 00:00:25,950 χτυπάς το κεφάλι σου στον τοίχο. 9 00:00:25,950 --> 00:00:28,310 Είναι αινιγματικός εμφάνιση μηνυμάτων σφάλματος και τα σφάλματα που 10 00:00:28,310 --> 00:00:29,220 δεν μπορώ να κυνηγήσει. 11 00:00:29,220 --> 00:00:32,310 Γιατί, να είστε σίγουροι, ότι μέσα σε μόλις ένα χρόνο λίγες εβδομάδες θα δούμε και πάλι στο 12 00:00:32,310 --> 00:00:35,930 πράγματα όπως Καίσαρα, και [? V-genair,?] ίσως ακόμη και κροτίδα, και 13 00:00:35,930 --> 00:00:40,050 συνειδητοποιούν πόσο μακριά έχετε έρθει σε σύντομο χρονικό διάστημα. 14 00:00:40,050 --> 00:00:43,670 Έτσι, αν αυτό σε παρηγορεί, κολλήσει εκεί για τώρα. 15 00:00:43,670 --> 00:00:46,610 >> Σήμερα, όμως, αρχίζουμε να μετάβαση στα πράγματα υψηλότερο επίπεδο. 16 00:00:46,610 --> 00:00:49,820 Και θα αρχίσουμε να θεωρούμε δεδομένο ότι εσείς ξέρετε πώς να προγραμματίσετε, ή 17 00:00:49,820 --> 00:00:52,090 τουλάχιστον οι απαρχές της ότι το επίπεδο άνεσης. 18 00:00:52,090 --> 00:00:56,520 Και θα αρχίσουμε να εξετάσουμε πώς μπορούμε να πάει για το σχεδιασμό των προγραμμάτων περισσότερα 19 00:00:56,520 --> 00:00:57,440 αποτελεσματικά. 20 00:00:57,440 --> 00:01:01,090 Πώς μπορούμε να πάμε για τη βελτιστοποίηση της αποδοτικότητα των αλγορίθμων μας, και 21 00:01:01,090 --> 00:01:03,110 γενικά επίλυση περισσότερα ενδιαφέροντα προβλήματα. 22 00:01:03,110 --> 00:01:06,850 Και αρχίζουν να θεωρούν δεδομένο ότι, αν θέλαμε, θα μπορούσαμε να κωδικοποιήσει έως οποιαδήποτε 23 00:01:06,850 --> 00:01:08,350 από τα παραδείγματα που έχουμε στο μυαλό μας. 24 00:01:08,350 --> 00:01:11,430 Έτσι, σήμερα, μην αγγίζετε το πληκτρολόγιο για οποιαδήποτε μορφή κώδικα. 25 00:01:11,430 --> 00:01:15,150 Θα είναι πολύ υψηλότερο επίπεδο, και τελικά, για την επίλυση προβλημάτων. 26 00:01:15,150 --> 00:01:20,490 >> Έτσι για να φτάσουμε σε αυτό το σημείο, επιτρέψτε μου να προτείνω ότι οι ακόλουθες επτά 27 00:01:20,490 --> 00:01:24,290 ορθογώνια αντιπροσωπεύουν επτά πόρτες, πίσω το οποίο είναι ένα σωρό 28 00:01:24,290 --> 00:01:26,340 αριθμούς, μεταξύ των οποίων είναι ο αριθμός 50. 29 00:01:26,340 --> 00:01:30,470 Επιτρέψτε μου να προβάλει αυτό σε αυτό οθόνη ως εδώ καλά. 30 00:01:30,470 --> 00:01:36,770 Και ότι χρειαζόμαστε έναν εθελοντή για να βοηθήσει να βρείτε μου ένα νούμερο μπροστά 31 00:01:36,770 --> 00:01:38,140 το διαδίκτυο εδώ για να δείτε. 32 00:01:38,140 --> 00:01:40,755 Έλα πάνω, στο ροζ. 33 00:01:40,755 --> 00:01:43,050 Εντάξει. 34 00:01:43,050 --> 00:01:43,930 Ποιο είναι το όνομά σου; 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [δεν ακούγεται] 36 00:01:44,850 --> 00:01:45,170 >> David J. MALAN: Συγνώμη; 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> David J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Εντάξει, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Χάρηκα για τη γνωριμία. 41 00:01:47,630 --> 00:01:48,370 Ανέβα. 42 00:01:48,370 --> 00:01:52,430 Έτσι, αυτά εδώ είναι επτά πόρτες, και τι Θα ήθελα να κάνετε για εμάς εδώ, 43 00:01:52,430 --> 00:01:56,560 μπροστά σε όλους τους συμμαθητές σας, είναι να μας βρείτε τον αριθμό, 50. 44 00:01:56,560 --> 00:02:00,860 Για να βρείτε έναν αριθμό, μπορείτε να κρυφοκοιτάζει πίσω οποιαδήποτε από αυτές τις πόρτες, αγγίζοντας απλώς 45 00:02:00,860 --> 00:02:03,030 σε μία από τις θύρες, και θα αποκαλύψει τον αριθμό του. 46 00:02:03,030 --> 00:02:06,080 Και ας δούμε πόσο γρήγορα μπορείτε να μας βρείτε τον αριθμό, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Όμορφα γίνει. 54 00:02:17,350 --> 00:02:18,040 Εντάξει. 55 00:02:18,040 --> 00:02:19,906 Χειροκρότημα για την Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Χειροκρότημα] 57 00:02:21,530 --> 00:02:22,320 >> Εντάξει. 58 00:02:22,320 --> 00:02:25,254 Λοιπόν, τι ήταν η στρατηγική σας για την βρίσκοντας τον αριθμό, 50; 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, σκέφτηκα ότι ίσως, αν - 60 00:02:27,222 --> 00:02:27,714 [Δεν ακούγεται] 61 00:02:27,714 --> 00:02:28,206 >> David J. MALAN: Αχ. 62 00:02:28,206 --> 00:02:29,630 Δώστε ένα δευτερόλεπτο. 63 00:02:29,630 --> 00:02:32,420 Έτσι ήταν η στρατηγική σας για την βρίσκοντας τον αριθμό, 50; 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Γι 'αυτό ακριβώς ξεκινούν από το αρχίζουμε να βλέπουμε τι ο πρώτος αριθμός 65 00:02:34,760 --> 00:02:38,590 ήταν, και τότε σκέφτηκα, ίσως αν από όπου και αν ταξινόμηση, εγώ θα κρατήσει μόνο 66 00:02:38,590 --> 00:02:39,970 αγγίζοντας ψηλά; 67 00:02:39,970 --> 00:02:40,140 >> David J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 Και φαίνεται να έχουν βρει ότι για να είναι η περίπτωση. 69 00:02:42,910 --> 00:02:45,670 Αν, ας φλούδα πίσω τα στρώματα λίγο, και θέλετε να πάτε 70 00:02:45,670 --> 00:02:47,640 μπροστά και να αποκαλύψει τις άλλες πόρτες θα μπορούσατε να έχετε επιλέξει; 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Ω, αγαπητέ. 73 00:02:51,712 --> 00:02:53,128 >> David J. MALAN: Αχ. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Γι 'αυτό ακριβώς στάθηκε τυχερός. 75 00:02:54,280 --> 00:02:55,270 >> David J. MALAN: Έτσι έχεις τύχη. 76 00:02:55,270 --> 00:02:55,710 Εντάξει. 77 00:02:55,710 --> 00:02:56,795 Έτσι, δεν είναι κακό. 78 00:02:56,795 --> 00:02:58,750 Αλλά αυτό είναι μια ενδιαφέρουσα διορατικότητα, έτσι δεν είναι; 79 00:02:58,750 --> 00:03:01,870 Αν υποτεθεί, και πήρες, Πράγματι, λίγο τυχερός εκεί. 80 00:03:01,870 --> 00:03:05,350 Αλλά αν υποτεθεί ότι οι αριθμοί ήταν ταξινόμηση, μπορείτε να είστε πιο ακριβείς 81 00:03:05,350 --> 00:03:08,750 ως προς τον τρόπο που επηρέασε συμπεριφορά σας; 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Έτσι, αν είχαν διευθετηθεί, I Σκέφτηκα ότι ίσως το μικρότερο στο μεγαλύτερο. 83 00:03:11,715 --> 00:03:11,970 >> David J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Ή αν αυτό κατέληξε να είναι πραγματικά μεγάλο, τότε το μεγαλύτερο προς το μικρότερο. 85 00:03:15,260 --> 00:03:15,540 >> David J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Έτσι, το μεγαλύτερο στο μικρότερο, ή το μικρότερο στο μεγαλύτερο. 87 00:03:18,170 --> 00:03:21,990 Αλλά επιτρέψτε μου να προτείνω, ας υποθέσουμε ότι είχατε πάρει άτυχος, και ας υποθέσουμε ότι 88 00:03:21,990 --> 00:03:26,840 δεν ήταν, στην πραγματικότητα, ταξινομημένο, πόσοι από οι πόρτες θα είχατε να κρυφοκοιτάζει 89 00:03:26,840 --> 00:03:28,590 πίσω στην χειρότερη περίπτωση; 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Όλοι τους. 91 00:03:29,860 --> 00:03:30,420 >> David J. MALAN: Όλοι τους. 92 00:03:30,420 --> 00:03:31,740 Οπότε ας γενικεύσουμε ότι n. 93 00:03:31,740 --> 00:03:34,790 Συμβαίνει να υπάρχει 7, αλλά ας είναι πιο γενικά να πούμε για ν πόρτες για την εκεί 94 00:03:34,790 --> 00:03:35,650 οθόνη εδώ. 95 00:03:35,650 --> 00:03:40,110 Έτσι, στη χειρότερη περίπτωση, θα έχετε να κοιτάξουμε πίσω από 7 θυρών, ή n πόρτες. 96 00:03:40,110 --> 00:03:44,140 Και έτσι αυτό είναι πραγματικά, είναι ένα κομμάτι της τύχη σήμερα, αλλά είναι πραγματικά μια γραμμική 97 00:03:44,140 --> 00:03:46,440 αλγόριθμο του είδους, ακόμα κι αν ήταν το είδος των παρακάμπτοντας γύρω. 98 00:03:46,440 --> 00:03:47,080 Είναι αυτό δίκαιο; 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ναι. 100 00:03:47,500 --> 00:03:50,000 >> David J. MALAN: Λοιπόν, επιτρέψτε μου να δείτε αν σας αλλαγές στρατηγικής, αν περάσω μας 101 00:03:50,000 --> 00:03:52,190 Το δεύτερο παράδειγμά μας εδώ με 7 διαφορετικές πόρτες. 102 00:03:52,190 --> 00:03:55,240 Ίδιους αριθμούς, αλλά αυτό φορά που ταξινομούνται. 103 00:03:55,240 --> 00:03:58,350 Ποια είναι η στρατηγική σας εδώ θα είναι, προσπαθεί να βάλει έξω από το μυαλό σας τι 104 00:03:58,350 --> 00:03:59,310 οι άλλοι αριθμοί ήταν - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> David J. MALAN: - νωρίτερα; 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Ας ξεκινήσουμε με το πρώτο. 108 00:04:03,180 --> 00:04:03,540 >> David J. MALAN: Εντάξει. 109 00:04:03,540 --> 00:04:05,190 Ξεκινήστε με το πρώτο. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Τώρα, πού θα πας, και γιατί; 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 είναι πραγματικά μικρό. 113 00:04:10,040 --> 00:04:12,500 Έτσι, εάν είστε το είδος ίσως μικρότερο στο μεγαλύτερο, θα πρέπει 114 00:04:12,500 --> 00:04:13,290 είναι διπλάσιο από αυτό, και -. 115 00:04:13,290 --> 00:04:13,670 >> David J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Ας δούμε, ποια η γνώμη σας; 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Δοκιμάστε το τελευταίο. 118 00:04:19,050 --> 00:04:19,500 Νίκαια. 119 00:04:19,500 --> 00:04:20,880 >> David J. MALAN: Πολύ όμορφα γίνεται. 120 00:04:20,880 --> 00:04:21,860 Εντάξει. 121 00:04:21,860 --> 00:04:23,010 >> [Χειροκρότημα] 122 00:04:23,010 --> 00:04:24,310 >> David J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Έτσι, είστε πραγματικά κάνει αυτό Σκληρό, επειδή είστε 124 00:04:26,790 --> 00:04:27,700 κάνει πολύ καλά. 125 00:04:27,700 --> 00:04:31,150 Που μας αφήνει σε θέση να κάνει ορισμένα σημεία. 126 00:04:31,150 --> 00:04:32,565 Έτσι, ας προσπαθήσουμε να επαναφέρετε εδώ. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> David J. MALAN: Πολύ καλά γίνει, παρ 'όλα αυτά. 129 00:04:35,980 --> 00:04:39,060 Έτσι ξεκίνησε στις αρχές, είδατε ότι ήταν 4, τότε 130 00:04:39,060 --> 00:04:40,240 μεταφέρθηκε στο τέλος. 131 00:04:40,240 --> 00:04:42,320 Αλλά ας υποθέσουμε ότι δεν έχετε πάρει τυχερός εκεί, και ας υποθέσουμε ότι 50 132 00:04:42,320 --> 00:04:42,890 ήταν κάπου αλλού. 133 00:04:42,890 --> 00:04:46,190 Ποια τρίτο βήμα σας έχουν; 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Πήγαινε πίσω στην αρχή. 135 00:04:47,680 --> 00:04:48,320 >> David J. MALAN: Πήγαινε πίσω στην αρχή. 136 00:04:48,320 --> 00:04:51,320 Εντάξει, έτσι θα έχετε αγγίξει αυτή η πόρτα, η οποία ήταν 8. 137 00:04:51,320 --> 00:04:51,660 Εντάξει. 138 00:04:51,660 --> 00:04:52,650 Έτσι, αυτό δεν είναι 50. 139 00:04:52,650 --> 00:04:55,380 Πού θα έχετε εξετάσει το επόμενο βήμα; 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Αν δεν είχα γνωρίζουν ότι ταξινομημένο. 141 00:04:56,720 --> 00:04:57,005 >> David J. MALAN: Σωστό. 142 00:04:57,005 --> 00:04:58,490 Λοιπόν, αν ξέρατε είχαν ταξινόμηση - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Αχ, δεν ξέρω, ναι. 144 00:04:58,700 --> 00:05:00,910 >> David J. MALAN: - αλλά δεν το έκανε ξέρετε όπου το 50 ήταν ακόμα; 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Απλά συνεχίζω. 146 00:05:01,785 --> 00:05:02,130 >> David J. MALAN: Εντάξει. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Συνεχίστε. 149 00:05:03,800 --> 00:05:05,270 Εντάξει, ότι μπορώ να συνεργαστώ μαζί της. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> David J. MALAN: Τώρα, αν είστε απλά Θα συνεχίσουμε, τι σας 152 00:05:07,210 --> 00:05:09,680 αλγορίθμου έχουν ανατεθεί υποστηρίζεται σε. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Η γραμμική -. 154 00:05:10,740 --> 00:05:11,820 >> David J. MALAN: Είναι το είδος της γραμμικής. 155 00:05:11,820 --> 00:05:13,480 Αλλά επιτρέψτε μου να προτείνω, ας με έβαλε επί τόπου. 156 00:05:13,480 --> 00:05:14,900 Επιτρέψτε μου να ανανεώσετε τη σελίδα. 157 00:05:14,900 --> 00:05:17,120 ίδιο αριθμό, ίδια διάταξη, ίδιες πόρτες. 158 00:05:17,120 --> 00:05:21,350 Αλλά σκεφτείτε πίσω σε εκείνη την πρώτη ημέρα τάξη όταν έσκισε ένα βιβλίο τηλέφωνο 159 00:05:21,350 --> 00:05:25,480 εξάμηνο, είδος, και ό, τι ήταν στρατηγική μας εκεί; 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Έναρξη στη μέση. 161 00:05:26,450 --> 00:05:26,690 >> David J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Έτσι, ξεκινούν στη μέση. 163 00:05:27,610 --> 00:05:28,790 Οπότε ας πάμε μπροστά και να μιμηθεί αυτό. 164 00:05:28,790 --> 00:05:30,720 Ξεκινήστε στη μέση από αποκαλύπτοντας την πόρτα. 165 00:05:30,720 --> 00:05:31,660 Έτσι, ο αριθμός 16. 166 00:05:31,660 --> 00:05:35,290 Λοιπόν, τι θα το ισχυρό άντρα έχουν κάνει, που έσκισε τον τηλεφωνικό κατάλογο στη μέση, 167 00:05:35,290 --> 00:05:38,450 για να φτάσουμε στην επόμενη εικασία; 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Πηγαίνετε σε αυτό το μισό. 169 00:05:39,400 --> 00:05:41,700 >> David J. MALAN: Και γιατί προς τα δεξιά; 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Αν ήταν είδος του μικρότερου στο μεγαλύτερο, τότε θα πρέπει να είναι 50 171 00:05:43,900 --> 00:05:44,720 στο άκρο αυτό. 172 00:05:44,720 --> 00:05:44,920 >> David J. MALAN: Good. 173 00:05:44,920 --> 00:05:45,390 Απόλυτα λογικό. 174 00:05:45,390 --> 00:05:48,380 Έτσι, όπως ένα τηλεφωνικό κατάλογο, πηγαίνετε στο δεξιά, σε αντίθεση προς τα αριστερά, αλλά εδώ 175 00:05:48,380 --> 00:05:49,500 είναι το κλειδί σε πακέτο. 176 00:05:49,500 --> 00:05:53,930 Μπορείτε τώρα να πετάξουν, ή αποσπώμενο, το ήμισυ αυτού του προβλήματος, αφήνοντας σας δεν 177 00:05:53,930 --> 00:05:55,970 με 7 θύρες, αλλά πραγματικά με μόλις 3. 178 00:05:55,970 --> 00:05:57,870 Ποιο είναι περίπου το μισό από το το μέγεθος του προβλήματος. 179 00:05:57,870 --> 00:05:58,350 Εντάξει. 180 00:05:58,350 --> 00:06:01,890 Και τώρα τι θα είχατε γίνεται μετά πάτε καλά; 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Μέχρι 16 εξακολουθεί να είναι αρκετά μικρή, σε σχέση με το 50, οπότε ίσως θα προσπαθήσω, 182 00:06:05,870 --> 00:06:06,700 όπως, αυτό. 183 00:06:06,700 --> 00:06:07,890 >> David J. MALAN: Εντάξει. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Εντάξει, τώρα τι σας ένστικτο σας λέει; 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Μπορώ να πετάξετε αυτό και στη συνέχεια απλά - 187 00:06:12,100 --> 00:06:12,360 >> David J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Καλό, μπορείτε να πετάξετε το αριστερό μισό εκεί. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - να πάρει αυτό το ένα. 190 00:06:14,890 --> 00:06:15,530 >> David J. MALAN: Και το δικαίωμα. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ναι. 192 00:06:15,760 --> 00:06:17,820 >> David J. MALAN: Έτσι, ακόμα κι αν είναι δύσκολο για να δούμε ίσως, όταν υπάρχει μόνο 193 00:06:17,820 --> 00:06:21,320 7 πόρτες, σκέφτομαι, τώρα, η συνοχή της 194 00:06:21,320 --> 00:06:22,620 αλγόριθμος που μόλις εφαρμοστεί. 195 00:06:22,620 --> 00:06:24,510 Στην προηγούμενη περίπτωση, κάνατε πάρετε τυχεροί, η οποία ήταν μεγάλη. 196 00:06:24,510 --> 00:06:26,540 Αλλά κάνατε χρησιμοποιήσετε μια ευρετική, Θα ήθελα να πω. 197 00:06:26,540 --> 00:06:29,150 Θα χρησιμοποιηθεί το είδος των ένστικτό σας, και γνωρίζοντας την ταξινόμηση, αν είναι αρκετά 198 00:06:29,150 --> 00:06:31,600 μικρό στην αρχή, προφανώς, έχουμε Πρέπει να πάει πιο δεξιά. 199 00:06:31,600 --> 00:06:34,990 Αλλά κατά κάποιο τρόπο, έχεις τυχερός, γιατί ίσως αυτό ήταν ο αριθμός 100, 200 00:06:34,990 --> 00:06:36,220 και ίσως 50 ήταν περισσότερο στη μέση. 201 00:06:36,220 --> 00:06:37,910 Ίσως 50 ήταν ακόμη εδώ. 202 00:06:37,910 --> 00:06:40,960 >> Αλλά αυτό που έκανε λίγο διαφορετικά αυτή τη φορά ήταν, θα έκανε το ίδιο πράγμα 203 00:06:40,960 --> 00:06:42,150 ξανά και ξανά. 204 00:06:42,150 --> 00:06:45,310 Και θα έλεγα ότι αυτό που μόλις έκανε, αν και επηρεάζονται από το τηλέφωνο 205 00:06:45,310 --> 00:06:48,100 book παράδειγμα, είναι κάτι πολύ πιο αλγοριθμική, και πολύ 206 00:06:48,100 --> 00:06:49,930 λιγότερο ειδικό κάλυκα. 207 00:06:49,930 --> 00:06:51,620 Πολύ λιγότερο ενστικτώδης. 208 00:06:51,620 --> 00:06:57,160 Έτσι, στο τέλος της ημέρας, πώς θα θα περιγράφουν την αποτελεσματικότητα της 209 00:06:57,160 --> 00:07:00,530 πρώτο αλγόριθμο, όπου πήγε αριστερά προς τα δεξιά, σε σχέση με το 210 00:07:00,530 --> 00:07:03,430 δεύτερος αλγόριθμος εδώ; 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: αυτό θα πρέπει, όπως, ίσως μείωση κατά το ήμισυ του χρόνου, ή ακόμη περισσότερο, ναι. 212 00:07:06,460 --> 00:07:07,320 >> David J. MALAN: Εντάξει, ίσως ακόμη περισσότερο. 213 00:07:07,320 --> 00:07:10,150 Ας πιέσουμε λίγο πιο δύσκολο σε αυτό. 214 00:07:10,150 --> 00:07:13,030 Αυτό που πραγματικά, αν συνεχίσουμε αυτή λογική, είμαστε κατά το ήμισυ σίγουρα η 215 00:07:13,030 --> 00:07:15,830 χρόνου λειτουργίας με αυτή τη δεύτερη αλγόριθμο ρίχνοντας το μισό του 216 00:07:15,830 --> 00:07:18,470 αριθμούς, αλλά τι κάναμε εμείς για την επόμενη επανάληψης, όταν η Jennifer αποκάλυψε 217 00:07:18,470 --> 00:07:20,615 Ο δεύτερος αριθμός; 218 00:07:20,615 --> 00:07:22,830 >> Εμείς κατά το ήμισυ τον αριθμό των θυρών και πάλι. 219 00:07:22,830 --> 00:07:25,270 Και μετά τι κάναμε εμείς μετά από αυτό, αν υπήρχαν περισσότερες πόρτες για να παίξει με; 220 00:07:25,270 --> 00:07:27,520 Εμείς θα τους μειωθεί κατά το ήμισυ, και πάλι, και ξανά, και ξανά. 221 00:07:27,520 --> 00:07:30,420 Και αυτό ήταν ακριβώς όπως εσείς όλα όρθιος κατά την πρώτη εβδομάδα του 222 00:07:30,420 --> 00:07:33,000 τάξη, οι μισοί από εσάς που κάθεστε κάτω, το ήμισυ σας που κάθεστε κάτω, οι μισοί από εσάς 223 00:07:33,000 --> 00:07:35,440 κάθεται κάτω, έως ότου ένας μοναχικός η ψυχή στεκόταν. 224 00:07:35,440 --> 00:07:39,050 Και είπαμε ότι ο χρόνος εκτέλεσης του ότι, ο αριθμός των βημάτων που χρειάστηκε ήταν 225 00:07:39,050 --> 00:07:40,430 με τη σειρά της, τι; 226 00:07:40,430 --> 00:07:41,230 >> ΟΜΙΛΗΤΗΣ 1: [δεν ακούγεται] 227 00:07:41,230 --> 00:07:43,970 >> David J. MALAN: Έτσι βάσης log 2 n, ή απλά πιο απλά, συνδεθείτε του n. 228 00:07:43,970 --> 00:07:45,060 Έτσι, κάτι λογαριθμική. 229 00:07:45,060 --> 00:07:48,380 Και η γραφική παράσταση δεν ήταν μια ευθεία γραμμή αυτό ακριβώς γινόταν όλο και χειρότερη, ήταν 230 00:07:48,380 --> 00:07:52,490 αυτό το ενδιαφέρον καμπύλη που δεν να πάρει τόσο άσχημα την πάροδο του χρόνου. 231 00:07:52,490 --> 00:07:53,910 Οπότε ας παραμείνουμε σε αυτή την ιδέα. 232 00:07:53,910 --> 00:07:54,690 Ας ευχαριστήσουμε Jennifer. 233 00:07:54,690 --> 00:07:56,150 Ευχαριστώ πολύ που ήρθατε πάνω. 234 00:07:56,150 --> 00:07:57,400 Και, ένα sec. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Δεν λάμπες γραφείου σήμερα, αλλά εμείς έχουν CS50 μπάλες άγχος. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> David J. MALAN: Εντάξει, εδώ. 239 00:08:04,410 --> 00:08:06,545 Σας ευχαριστούμε για τη θεμελίωση το άγχος μέχρι εδώ. 240 00:08:06,545 --> 00:08:07,350 Εντάξει. 241 00:08:07,350 --> 00:08:10,620 Έτσι, ας δούμε αν μπορούμε όχι τώρα επισημοποιήσει αυτό το λίγο περισσότερο. 242 00:08:10,620 --> 00:08:14,820 Έτσι και πάλι, αυτό που μόλις έκανε ήταν ουσιαστικά το ίδιο πράγμα, όπως κάναμε 243 00:08:14,820 --> 00:08:16,660 σε αυτή την πρώτη εβδομάδα. 244 00:08:16,660 --> 00:08:23,780 Αλλά αντί να τελειώνουν με ένα γραμμικό αλγόριθμος, το οποίο απεικονίζεται 245 00:08:23,780 --> 00:08:27,210 στο παρελθόν, όπως αυτή ευθεία γραμμή, σύμφωνα με την οποία, αν βάλουμε ένα ακόμη πόρτα 246 00:08:27,210 --> 00:08:29,610 η οθόνη, τότε η Jennifer θα έπρεπε να εξετάσει, ενδεχομένως, 247 00:08:29,610 --> 00:08:30,600 πίσω από το ένα περισσότερα πόρτα. 248 00:08:30,600 --> 00:08:33,490 Αν βάλουμε δύο πόρτες, θα μπορούσε να έχει να κοιτάξουμε πίσω από δύο πόρτες. 249 00:08:33,490 --> 00:08:35,990 >> Και έτσι, δεν υπήρχε αυτή η γραμμική σχέση μεταξύ του μεγέθους του 250 00:08:35,990 --> 00:08:39,059 πρόβλημα, ας πούμε, το x-άξονα, και το ποσό του χρόνου που χρειάζεται για να 251 00:08:39,059 --> 00:08:40,440 λύσει την y. 252 00:08:40,440 --> 00:08:43,330 Αλλά η εικόνα που αναφερόταν στην Νωρίτερα ήταν αυτή η πράσινη γραμμή. 253 00:08:43,330 --> 00:08:45,970 Πράσινο σκόπιμα, γιατί αυτό ακριβώς αισθάνθηκε καλύτερα. 254 00:08:45,970 --> 00:08:49,790 Στη θεωρία, ο αλγόριθμος, όταν κάναμε με τον τηλεφωνικό κατάλογο, όταν κάναμε 255 00:08:49,790 --> 00:08:52,420 μαζί σας μετράει ο ένας τον άλλον, και στη δεύτερη περίπτωση, όταν Jennifer μόνο 256 00:08:52,420 --> 00:08:55,250 έκανε μέχρι εδώ, ήταν ένα είδος θεμελιωδώς καλύτερα. 257 00:08:55,250 --> 00:08:57,180 Επειδή δεν ήταν μόνο δύο φορές πιο γρήγορα. 258 00:08:57,180 --> 00:08:58,870 Δεν ήταν ακόμα και τέσσερις φορές πιο γρήγορα. 259 00:08:58,870 --> 00:09:03,290 Ήταν εξαρτάται εξ ολοκλήρου από ό, τι η μέγεθος της εισόδου ήταν, ως προς το πόσα 260 00:09:03,290 --> 00:09:05,220 μέτρα που τελικά πήρε. 261 00:09:05,220 --> 00:09:08,040 >> Και έτσι αυτή η απλή ιδέα ότι όλοι πήραν δεδομένο με τον τηλεφωνικό κατάλογο, 262 00:09:08,040 --> 00:09:10,200 μπορεί παρομοίως να εφαρμοστεί σε κάτι σαν αυτό. 263 00:09:10,200 --> 00:09:12,380 Και αυτό θα μπορούσε να είναι πιο άνετα γνωστή ως, όπως μπορείτε να 264 00:09:12,380 --> 00:09:13,940 φανταστείτε, διαίρει και βασίλευε. 265 00:09:13,940 --> 00:09:16,390 Δεν σε αντίθεση με ό, τι κάναμε, φυσικά, με τον τηλεφωνικό κατάλογο. 266 00:09:16,390 --> 00:09:18,300 >> Αλλά ο ψευδοκώδικας, ανάκληση, ήταν αυτό. 267 00:09:18,300 --> 00:09:21,800 Έτσι, δεν θα το κάνουμε αυτό και πάλι, αλλά υπενθυμίζουν ότι η πρώτη εβδομάδα, όλοι μας σηκώθηκε 268 00:09:21,800 --> 00:09:25,140 και στη συνέχεια μισό από εσάς κάθισε, το ήμισυ των που κάθισε, οι μισοί από εσάς κάθισε. 269 00:09:25,140 --> 00:09:29,280 Ότι ο αλγόριθμος υλοποιήθηκε σε ένα bit του τρόπο εξαπάτησης, σε αυτό, 270 00:09:29,280 --> 00:09:32,870 Δεν ήταν μόνο ένας από εμένα καταμέτρηση, ριζικά, πιο αποτελεσματικά. 271 00:09:32,870 --> 00:09:35,830 Σε αυτή την περίπτωση, ήμουν μόχλευση μια δευτερεύουσα πόρο. 272 00:09:35,830 --> 00:09:39,470 Ταξινόμηση της, πολλαπλές CPUs, πολλαπλές μυαλά, πολλαπλές έξυπνοι άνθρωποι στην 273 00:09:39,470 --> 00:09:42,740 δωμάτιο ήταν βοήθειά μου από κάτι γραμμική σε κάτι 274 00:09:42,740 --> 00:09:45,190 λογαριθμική, από κάτι κόκκινο σε πράσινο κάτι. 275 00:09:45,190 --> 00:09:48,650 >> Αλλά στην περίπτωση αυτή, η Jennifer μπορεί μόνη της βελτιώσει ουσιαστικά μετά το 276 00:09:48,650 --> 00:09:52,370 απόδοση του πρώτου αλγορίθμου της από, και πάλι, απλά να σκεφτόμαστε λίγο πιο δύσκολο. 277 00:09:52,370 --> 00:09:56,650 Και τώρα, όταν έρχεται η ώρα για την εφαρμογή αυτά τα πράγματα, υπολογίζοντας 278 00:09:56,650 --> 00:10:00,670 Τι γραμμές κώδικα μπορείτε να γράψετε τέτοια ότι μπορείτε να τα επαναλάβω και πάλι, και 279 00:10:00,670 --> 00:10:03,350 πάλι, και πάλι, είδος σε ένα looping μόδας. 280 00:10:03,350 --> 00:10:06,370 Επειδή εσείς δεν πρόκειται να έχει το πολυτελείας, όπως η Jennifer έκανε σε πρώτη φάση, να 281 00:10:06,370 --> 00:10:10,460 απλά έχουν ένα σωρό ifs και να πω, Χμμ, αν αυτό πρώτος αριθμός είναι 4, 282 00:10:10,460 --> 00:10:11,800 επιτρέψτε μου να πηδήξει σε όλη τη διαδρομή μέχρι το τέλος. 283 00:10:11,800 --> 00:10:14,180 Ooh, εάν ο αριθμός αυτός είναι πολύ μεγάλο, επιτρέψτε μου να προχωρήσω αυθαίρετα πίσω 284 00:10:14,180 --> 00:10:15,220 με το δεύτερο στοιχείο. 285 00:10:15,220 --> 00:10:18,210 Θα διαπιστώσετε ότι πρόκειται να είναι ένα πολύ πιο δύσκολο να επισημοποιήσει ό, τι εμείς οι άνθρωποι 286 00:10:18,210 --> 00:10:21,270 θεωρούμε δεδομένο ως πολύ λογικές heuristics, αλλά ένας υπολογιστής είναι μόνο 287 00:10:21,270 --> 00:10:23,260 Θα κάνουμε ό, τι πει να το κάνει. 288 00:10:23,260 --> 00:10:25,280 >> Τώρα αυτό έχει πολύ ενδιαφέρον επιπτώσεις. 289 00:10:25,280 --> 00:10:29,950 Το γράφημα αυτό είναι το είδος της γραφτό να ταξινομήσετε του συντρίψει οπτικά, αλλά η ανακοίνωση, όπου 290 00:10:29,950 --> 00:10:32,230 είναι η ευθεία γραμμή σε αυτό το γράφημα; 291 00:10:32,230 --> 00:10:35,330 Πού είναι η γραμμική γραφική παράσταση που ονομάζουμε ν? 292 00:10:35,330 --> 00:10:37,580 Λοιπόν, αυτό είναι το είδος του προς τον πυθμένα από αυτή την εικόνα, έτσι δεν είναι; 293 00:10:37,580 --> 00:10:40,500 Έτσι, το μόνο που έχω κάνει είναι ότι έχουμε το είδος της μεγεθυνθεί έξω στο χ-άξονα και τον 294 00:10:40,500 --> 00:10:44,780 y-άξονα για να προσπαθήσετε να πάρετε μια αίσθηση του τι άλλα είδη καμπύλες μοιάζουν. 295 00:10:44,780 --> 00:10:47,760 >> Και οι ιδιαιτερότητες των μαθηματικών εκφράσεις σήμερα δεν θα έχει σημασία τόσο 296 00:10:47,760 --> 00:10:52,440 πολύ, αλλά παρατηρήσετε ότι υπάρχει μια πολύ αλγόριθμους που είναι πολύ χειρότερη από ό, τι 297 00:10:52,440 --> 00:10:53,470 κάτι που είναι γραμμική. 298 00:10:53,470 --> 00:10:55,410 Πράγματι, n κύβους φαίνεται αρκετά άσχημα. 299 00:10:55,410 --> 00:10:58,400 2 του Ν φαίνεται αρκετά άσχημα. n τετράγωνο φαίνεται αρκετά άσχημα. 300 00:10:58,400 --> 00:11:01,630 Και θα δούμε τι μερικά από αυτά μπορεί να είναι στην πραγματικότητα σήμερα. 301 00:11:01,630 --> 00:11:05,430 Και log n δεν αισθάνεται τόσο άσχημα, αλλά καλύτερα από ό, τι η είναι log βάσης 2 του Ν. 302 00:11:05,430 --> 00:11:08,080 Αλλά ξέρετε, θα ήταν ακόμη πιο εκπληκτικό, αν Jennifer, ή αν, 303 00:11:08,080 --> 00:11:12,910 ότι η πρώτη εβδομάδα, είχε έρθει με κάτι που είναι ημερολόγιο της καταγραφής των n. 304 00:11:12,910 --> 00:11:15,880 >> Έτσι με άλλα λόγια, υπάρχει όλο αυτό το εύρος των πιθανών λύσεων για την 305 00:11:15,880 --> 00:11:18,570 προβλήματα, αλλά ακόμη και εδώ, ανακοίνωση τι πρόκειται να συμβεί. 306 00:11:18,570 --> 00:11:22,910 Όταν σμίκρυνση, ποια από αυτές τις καμπύλες πρόκειται να αποδείξει ότι είναι ο απόλυτος 307 00:11:22,910 --> 00:11:26,630 χειρότερα από αυτά που εμφανίζονται στην οθόνη τώρα; 308 00:11:26,630 --> 00:11:28,680 Έτσι, n κύβους φαίνεται αρκετά κακό αυτή τη στιγμή. 309 00:11:28,680 --> 00:11:32,470 Αλλά αν σμίκρυνση και να δείτε περισσότερα από τα x και η y-άξονα, ο οποίος πρόκειται να 310 00:11:32,470 --> 00:11:34,550 κυριαρχήσει τελικά; 311 00:11:34,550 --> 00:11:37,120 Έτσι αποδεικνύεται πράγματι ότι η 2 n, και μπορείτε να το καταλάβουν αυτό μόνο από 312 00:11:37,120 --> 00:11:39,990 συνδέσετε σε κάποια πιο μεγάλη αριθμούς, και θα δείτε ότι 2 η 313 00:11:39,990 --> 00:11:42,070 n, πράγματι, μεγαλώνει πολύ πιο γρήγορα. 314 00:11:42,070 --> 00:11:45,530 Αν θέλουμε πραγματικά σμίκρυνση, μια 2 η n αλγόριθμος είναι τελείως χάλια. 315 00:11:45,530 --> 00:11:48,170 Θέλω να πω ότι αυτό πρόκειται να λάβει αρκετά ένα κομμάτι του χρόνου για την 316 00:11:48,170 --> 00:11:49,460 υπολογιστή και να βγάλεις μέσα. 317 00:11:49,460 --> 00:11:52,500 >> Αλλά θα δείτε την πάροδο του χρόνου, ειδικά με τις μελλοντικές σειρές πρόβλημα και ακόμη 318 00:11:52,500 --> 00:11:55,600 τελικών σχεδίων, είναι τα δεδομένα σας που παίρνει μεγάλες, εντάξει; 319 00:11:55,600 --> 00:11:58,300 Ακόμη και στην πρώτη έκδοση του Facebook, καθώς ο αριθμός των φίλων, και το 320 00:11:58,300 --> 00:12:01,840 αριθμός των εγγεγραμμένων χρηστών πήρε μεγάλες, μπορείτε να ταξινομήσετε από το τηλέφωνο και να 321 00:12:01,840 --> 00:12:05,530 εφαρμόσουν κάτι με γραμμική αναζήτηση, ή μια πολύ απλή διαλογή 322 00:12:05,530 --> 00:12:07,030 αλγόριθμο, όπως θα δούμε σήμερα. 323 00:12:07,030 --> 00:12:09,280 Θα πρέπει να αρχίσουμε να σκεφτόμαστε πιο δύσκολο και πιο δύσκολο για τα προβλήματα αυτά. 324 00:12:09,280 --> 00:12:12,070 Και τα είδη των προβλημάτων μέρη όπως Facebook και Google, και η Microsoft, 325 00:12:12,070 --> 00:12:16,350 και άλλοι δουλέψουμε είναι ακριβώς αυτά είδος μεγάλου είδους δεδομένων των ερωτήσεων 326 00:12:16,350 --> 00:12:18,530 ολοένα και περισσότερο αυτές τις μέρες. 327 00:12:18,530 --> 00:12:18,900 >> Εντάξει. 328 00:12:18,900 --> 00:12:23,800 Έτσι, η επιτυχία της Jennifer σε αυτό το δεύτερο αλγόριθμο, ειλικρινά, έκανε εκπληκτικά 329 00:12:23,800 --> 00:12:26,110 και η πρώτη φορά, αλλά ας γράψετε όπως τύχη, έτσι ώστε να 330 00:12:26,110 --> 00:12:27,000 μπορεί να κάνει αυτό το σημείο. 331 00:12:27,000 --> 00:12:30,970 Στη δεύτερη περίπτωση, που θα αξιοποιηθούν αλγόριθμο που επαναλαμβάνονται ξανά και 332 00:12:30,970 --> 00:12:34,670 και πάλι, αλλά πήρε ως δεδομένο ένα ορισμένες παραδοχή ότι επιτρέψαμε 333 00:12:34,670 --> 00:12:39,370 της, αλλά εκμεταλλεύονται κάποιες λεπτομέρειες το δεύτερη φορά ότι δεν έχει την 334 00:12:39,370 --> 00:12:39,840 πρώτη φορά. 335 00:12:39,840 --> 00:12:41,800 Ποιο ήταν αυτό; 336 00:12:41,800 --> 00:12:43,050 >> Ότι ο κατάλογος ήταν ταξινομημένο. 337 00:12:43,050 --> 00:12:46,350 Έτσι, μόλις ο κατάλογος με ταξινόμηση, έχουμε ισχυρίζονται ότι η Jennifer ήταν σε θέση να κάνει 338 00:12:46,350 --> 00:12:47,480 θεμελιωδώς καλύτερα. 339 00:12:47,480 --> 00:12:51,450 7 πόρτες, ναι, δεν είναι και τόσο ενδιαφέρον, αλλά ας υποθέσουμε ότι είμαστε 7 εκατομμύρια πόρτες. 340 00:12:51,450 --> 00:12:54,080 Σύνδεση του n είναι σίγουρα πρόκειται να εκτελέσει πολύ, πολύ 341 00:12:54,080 --> 00:12:55,610 γρηγορότερα σε μακροπρόθεσμη βάση. 342 00:12:55,610 --> 00:12:58,880 Αλλά έπρεπε να έχει το πόρτες ταξινόμηση γι 'αυτήν. 343 00:12:58,880 --> 00:13:02,320 Τώρα, πήρα το θάρρος να το κάνουμε αυτό εκ των προτέρων στην οθόνη του υπολογιστή 344 00:13:02,320 --> 00:13:05,160 εδώ, αλλά ας υποθέσουμε ότι η Jennifer είχε να κάνει ότι τον εαυτό της; 345 00:13:05,160 --> 00:13:10,120 Ας υποθέσουμε ότι οι πόρτες εν λόγω εκπροσωπούνται τα δεδομένα σε μια βάση δεδομένων, ή 346 00:13:10,120 --> 00:13:14,260 φίλους εγγραφεί για το Facebook, ή οποιεσδήποτε ιστοσελίδες στο διαδίκτυο που 347 00:13:14,260 --> 00:13:16,880 διάφορες ιστοσελίδες μπορεί να χρειαστεί στο δείκτη ή την αναζήτηση πάνω. 348 00:13:16,880 --> 00:13:20,940 >> Ας υποθέσουμε ότι είχατε μόνο μια πρωτογενή δεδομένα που και αυτό έμεινε σε εσάς, ή για να 349 00:13:20,940 --> 00:13:23,010 Jennifer να το κάνουμε αυτό διαλογής; 350 00:13:23,010 --> 00:13:26,950 Αυτό, μάλλον, απαιτεί να απαντάμε το ερώτημα, καλά, πόσο χρόνο 351 00:13:26,950 --> 00:13:31,080 θα έχουν λάβει Jennifer, ή ακόμα και εγώ, για να ταξινομήσετε τους αριθμούς των προτέρων, ώστε 352 00:13:31,080 --> 00:13:32,680 ότι θα μπορούσε να επωφεληθεί από αυτό; 353 00:13:32,680 --> 00:13:32,880 Σωστά; 354 00:13:32,880 --> 00:13:36,620 Επειδή η επίπτωση, φυσικά, είναι και αν μου πάρει πολύ λίγο χρόνο για να ταξινομήσετε 355 00:13:36,620 --> 00:13:40,800 οι αριθμοί, ποιος στο καλό νοιάζεται σας ότι μπορείτε να βρείτε μια σειρά όπως 50 τόσο γρήγορα, 356 00:13:40,800 --> 00:13:44,850 όπως στην περίπτωση της Jennifer, αν έχουμε περισσότερο από κυριεύσει το ποσό του συνολικού χρόνου 357 00:13:44,850 --> 00:13:46,920 πήρε από τη διαλογή τα πράγματα εκ των προτέρων; 358 00:13:46,920 --> 00:13:49,320 >> Έτσι, ας δούμε αν δεν μπορούμε να το ζωγραφίσει την εικόνα εδώ. 359 00:13:49,320 --> 00:13:51,370 Έχω ένα σωρό περισσότερο άγχος μπάλες, αν αυτό βοηθάει 360 00:13:51,370 --> 00:13:52,270 να σπάσει τον πάγο εδώ. 361 00:13:52,270 --> 00:13:55,690 Και αν δεν θα με πείραζε, θα Πρέπει επτά εθελοντές - 362 00:13:55,690 --> 00:13:57,060 στο, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Έτσι, δεν έχουμε να δαπανήσει για λάμπες γραφείου, φαίνεται. 365 00:13:59,250 --> 00:13:59,690 Εντάξει. 366 00:13:59,690 --> 00:14:01,530 Έτσι, σχετικά με το πώς εσείς οι δύο μπροστά. 367 00:14:01,530 --> 00:14:04,160 Τι θα λέγατε εσείς οι δύο άντρες στην πλάτη. 368 00:14:04,160 --> 00:14:04,870 Έτσι ώστε να είναι τέσσερις. 369 00:14:04,870 --> 00:14:09,890 Πώς για σας μπροστά πέντε, έξι και επτά. 370 00:14:09,890 --> 00:14:10,320 Ακριβώς εκεί. 371 00:14:10,320 --> 00:14:13,260 Του φίλου σας μπορείτε επισημαίνοντας, έτσι μπορείτε να πάρετε το βραβείο. 372 00:14:13,260 --> 00:14:13,700 >> Εντάξει. 373 00:14:13,700 --> 00:14:14,410 Ανέβα. 374 00:14:14,410 --> 00:14:17,120 Και γιατί δεν έχετε παιδιά έρχονται για πάνω από εδώ. 375 00:14:17,120 --> 00:14:18,960 Πάω να σας δώσω σε κάθε έναν αριθμό. 376 00:14:18,960 --> 00:14:22,150 Και πάει μπροστά και να οργανώσει τον εαυτό σας πανομοιότυπα με ό, τι είναι 377 00:14:22,150 --> 00:14:25,180 απεικονίζεται στην οθόνη. 378 00:14:25,180 --> 00:14:26,530 >> [Παρεμβάλλοντας VOICES] 379 00:14:26,530 --> 00:14:28,160 >> David J. MALAN: Oop, συγγνώμη. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Εντάξει. 382 00:14:32,180 --> 00:14:32,750 Λοιπόν, εδώ είμαστε. 383 00:14:32,750 --> 00:14:34,180 Αριθμός πέντε. 384 00:14:34,180 --> 00:14:35,136 Αριθμό έξι. 385 00:14:35,136 --> 00:14:37,770 Ένα, δύο, τρία, τέσσερα, πέντε, έξι, επτά. 386 00:14:37,770 --> 00:14:39,410 Ω, αυτό είναι περίεργο. 387 00:14:39,410 --> 00:14:41,210 >> ΟΜΙΛΗΤΗΣ 2: Θα πάρει μόνο ένα -. 388 00:14:41,210 --> 00:14:41,900 >> David J. MALAN: Good deal. 389 00:14:41,900 --> 00:14:43,130 Εντάξει. 390 00:14:43,130 --> 00:14:44,611 Σας ευχαριστούμε για τη συμμετοχή σας. 391 00:14:44,611 --> 00:14:47,200 >> [Χειροκρότημα] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Εντάξει. 394 00:14:48,860 --> 00:14:51,970 Έτσι έχουμε τέσσερις, δύο, έξι, ένα, τρία, επτά, πέντε. 395 00:14:51,970 --> 00:14:56,010 Τέλεια έτσι έχουμε επτά εθελοντές εδώ οι οποίοι είναι ίση σε πλάτος με το 396 00:14:56,010 --> 00:14:57,430 σειρά που παίζουμε με την προηγούμενη. 397 00:14:57,430 --> 00:14:59,470 Και επέλεξα επτά για λόγους που θα είναι ακριβώς 398 00:14:59,470 --> 00:15:00,840 βολικό σε λίγο. 399 00:15:00,840 --> 00:15:04,400 Και Πάω να προτείνει, πρώτον, ότι ταξινομούμε αυτά τα επτά εθελοντές. 400 00:15:04,400 --> 00:15:06,786 Αν θέλετε, πρώτη, να πω γεια όμως. 401 00:15:06,786 --> 00:15:08,970 Δεδομένου ότι αυτό πρόκειται να είναι ένα αδέξιο αρκετά λεπτά. 402 00:15:08,970 --> 00:15:10,370 Συστηθείτε. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Γεια σου, είμαι Γκρέις. 404 00:15:10,980 --> 00:15:14,190 Είμαι δευτεροετής φοιτητής στο Leverett Βουλή. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Είμαι Branson. 407 00:15:15,620 --> 00:15:16,920 Είμαι πρωτοετής στο Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hi. 410 00:15:20,230 --> 00:15:21,040 Είμαι Gabe. 411 00:15:21,040 --> 00:15:22,300 Είμαι μια junior στο Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Είμαι Neil. 414 00:15:25,980 --> 00:15:29,090 Είμαι πρωτοετής στο Matthews. 415 00:15:29,090 --> 00:15:29,550 >> ΙΑΣΩΝ: Είμαι Jason. 416 00:15:29,550 --> 00:15:32,816 Είμαι πρωτοετής στο Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Είμαι Mike. 418 00:15:33,700 --> 00:15:37,360 Είμαι πρωτοετής στο Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Είμαι Jess. 420 00:15:37,990 --> 00:15:40,313 Είμαι δευτεροετής φοιτητής στο Leverett. 421 00:15:40,313 --> 00:15:41,300 >> David J. MALAN: Excellent. 422 00:15:41,300 --> 00:15:41,850 Εντάξει. 423 00:15:41,850 --> 00:15:44,190 Λοιπόν, σας ευχαριστώ σε όλους μας εθελοντές εδώ μέχρι στιγμής. 424 00:15:44,190 --> 00:15:47,110 Και η πρόκληση αυτή τη στιγμή είναι τώρα σε εξέλιξη να είναι να ταξινομήσετε από αυτά τα παιδιά, αλλά στη συνέχεια 425 00:15:47,110 --> 00:15:50,250 θα πάμε να πρέπει να σκεφτείτε λίγο σκληρά για το πόσο αποτελεσματικά μπορούμε πραγματικά 426 00:15:50,250 --> 00:15:51,110 ταξινόμηση τους. 427 00:15:51,110 --> 00:15:52,580 Έτσι, ας προσπαθήσουμε πρώτα αυτό. 428 00:15:52,580 --> 00:15:55,970 Εσείς μπορείτε να δείτε τους αριθμούς του άλλου απλά με την τοποθέτηση γύρω από τις γωνίες. 429 00:15:55,970 --> 00:15:59,380 Προχωρήστε και να διαρκέσει μερικά δευτερόλεπτα, και Ταξινόμηση ίδιοι από το μικρότερο σχετικά με την 430 00:15:59,380 --> 00:16:01,240 αριστερά στο μεγαλύτερο δεξιά. 431 00:16:01,240 --> 00:16:02,490 Go. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Καλό. 435 00:16:08,030 --> 00:16:09,370 Αυτό ήταν πραγματικά καταριέται γρήγορα. 436 00:16:09,370 --> 00:16:14,040 Τώρα κάποιος εδώ, τι ήταν ο αλγόριθμος ότι αυτοί οι τύποι που εφαρμόζονται; 437 00:16:14,040 --> 00:16:14,900 >> ΟΜΙΛΗΤΗΣ 1: Τουλάχιστον στο μέγιστο. 438 00:16:14,900 --> 00:16:15,000 >> David J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Τουλάχιστον στο μέγιστο είναι πραγματικά ταξινομήσετε του στόχος, αλλά δεν είμαι βέβαιος ότι είναι 440 00:16:18,070 --> 00:16:18,890 πραγματικά ένας αλγόριθμος. 441 00:16:18,890 --> 00:16:21,810 Τουλάχιστον σε μεγαλύτερο δεν λέει μου βήμα-βήμα τι πρέπει να κάνουμε. 442 00:16:21,810 --> 00:16:22,833 Ναι; 443 00:16:22,833 --> 00:16:24,083 >> ΟΜΙΛΗΤΗΣ 1: [δεν ακούγεται] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> David J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Έτσι, αν δείτε ένα πρόσωπο μικρότερο από τον αριθμό σας, στη συνέχεια να προχωρήσουμε σε 447 00:16:28,920 --> 00:16:29,680 η δεξιά τους. 448 00:16:29,680 --> 00:16:32,800 Έτσι ώστε να είναι πλέον όλο και πιο εκφραστική, περισσότερο σαν έναν αλγόριθμο, γιατί 449 00:16:32,800 --> 00:16:35,410 μπορούμε να πούμε, αν αυτό, στη συνέχεια, ότι. 450 00:16:35,410 --> 00:16:37,050 Έτσι έχουμε κάποιο είδος όρους κατασκεύασμα. 451 00:16:37,050 --> 00:16:39,700 Και αυτά τα παιδιά φαίνεται να το κάνει αυτό μερικές φορές, επειδή κάποιοι από εσάς μετακινηθεί λίγο 452 00:16:39,700 --> 00:16:40,420 μιας αποστάσεως. 453 00:16:40,420 --> 00:16:43,410 Έτσι, δεν υπήρχε προφανώς κάποιο είδος looping συμβαίνει στο μυαλό τους. 454 00:16:43,410 --> 00:16:44,610 >> Αλλά ας προσπαθήσουμε να επισημοποιηθεί αυτό. 455 00:16:44,610 --> 00:16:47,540 Αν εσείς θα μπορούσε να επαναφέρει πίσω σε αυτή τη συμφωνία. 456 00:16:47,540 --> 00:16:50,650 Ας δούμε αν δεν μπορούμε να επισημοποιήσει αυτή την bit, και στη συνέχεια να ζητήσει από την ερώτηση, απλά 457 00:16:50,650 --> 00:16:51,580 πόσο αποτελεσματική είναι αυτό; 458 00:16:51,580 --> 00:16:54,220 Φυσικά, όταν το κάνουμε αυτό πιο αργά, πρόκειται να αισθάνονται τόσο καλή 459 00:16:54,220 --> 00:16:57,210 ένας αλγόριθμος, αλλά ας δούμε αν μπορούμε να βάλτε τα δάχτυλά μας για τα ακριβή βήματα. 460 00:16:57,210 --> 00:16:58,670 >> Έτσι οι δύο τύποι είναι τέσσερις και δύο. 461 00:16:58,670 --> 00:17:01,020 Ή μπορείτε σωστές ή λάθος σειρά; 462 00:17:01,020 --> 00:17:01,900 Προφανώς λανθασμένη. 463 00:17:01,900 --> 00:17:02,710 Γι 'αυτό και αντάλλαξαν. 464 00:17:02,710 --> 00:17:05,170 Τώρα είμαι πρόκειται να παραμερίστε εδώ και να πω, τέσσερις σε έξι. 465 00:17:05,170 --> 00:17:06,240 Είσαι σωστή ή λάθος; 466 00:17:06,240 --> 00:17:06,599 >> GABE: Σωστό. 467 00:17:06,599 --> 00:17:07,180 >> David J. MALAN: Σωστό. 468 00:17:07,180 --> 00:17:08,300 Έξι και μία; 469 00:17:08,300 --> 00:17:08,609 Όχι. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Έτσι ώστε είναι δύο swaps. 472 00:17:10,490 --> 00:17:11,710 Έξι και τα τρία; 473 00:17:11,710 --> 00:17:11,980 Όχι. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Έξι και επτά; 476 00:17:13,930 --> 00:17:14,630 Φαίνεται καλό. 477 00:17:14,630 --> 00:17:15,396 Επτά και πέντε; 478 00:17:15,396 --> 00:17:16,150 >> JESS: [δεν ακούγεται] 479 00:17:16,150 --> 00:17:17,089 >> David J. MALAN: OK, swap. 480 00:17:17,089 --> 00:17:19,770 Και ταξινομημένο. 481 00:17:19,770 --> 00:17:19,980 Εντάξει. 482 00:17:19,980 --> 00:17:21,440 Έτσι δεν είναι, προφανώς, έτσι δεν είναι; 483 00:17:21,440 --> 00:17:22,470 Υπήρχε, λοιπόν, περισσότερο σε εξέλιξη. 484 00:17:22,470 --> 00:17:24,920 Αλλά, πράγματι, αυτά τα παιδιά, ακόμα και μόνο ενστικτωδώς. 485 00:17:24,920 --> 00:17:25,450 συνέχισε να κινείται. 486 00:17:25,450 --> 00:17:27,710 Δεν έκανε ακριβώς να σταματήσει, από τη στιγμή που διορθωθεί ένα πρόβλημα. 487 00:17:27,710 --> 00:17:27,839 Έτσι. 488 00:17:27,839 --> 00:17:29,390 Πράγματι, είμαι πρόκειται να έχουν να κάνουν το ίδιο πράγμα. 489 00:17:29,390 --> 00:17:32,720 Πάω να πρέπει να λύσουμε από πίσω προς τα πίσω στην αρχή αυτού του προβλήματος, 490 00:17:32,720 --> 00:17:35,630 ή η αρχή αυτού του συστοιχία ανθρώπους, ας αρχίσουμε καλώντας τους. 491 00:17:35,630 --> 00:17:38,366 >> Και τώρα τι θα πρέπει αλγόριθμο μου στο δεύτερο πέρασμα είναι; 492 00:17:38,366 --> 00:17:39,220 >> ΟΜΙΛΗΤΗΣ 1: Το ίδιο πράγμα. 493 00:17:39,220 --> 00:17:39,940 >> David J. MALAN: Το ίδιο πράγμα. 494 00:17:39,940 --> 00:17:41,460 Και αυτό, αρχίζω να αρέσει, έτσι δεν είναι; 495 00:17:41,460 --> 00:17:44,720 Μόλις μπορείτε να βρείτε τον εαυτό σας να κάνει το ίδιο πράγμα ξανά και ξανά, αυτό είναι 496 00:17:44,720 --> 00:17:47,890 όλο και περισσότερο σαν ένα αλγόριθμο, και λιγότερο ανθρώπινο ένστικτο. 497 00:17:47,890 --> 00:17:48,680 >> Έτσι τώρα, εδώ πηγαίνουμε πάλι. 498 00:17:48,680 --> 00:17:49,870 Δύο και τέσσερα; 499 00:17:49,870 --> 00:17:50,220 Όχι. 500 00:17:50,220 --> 00:17:51,050 Τέσσερα και ένα; 501 00:17:51,050 --> 00:17:53,380 Αχ, υπήρξε πράγματι κάποια λειτουργούν ακόμη να γίνουν πολλά. 502 00:17:53,380 --> 00:17:53,620 Για και τρεις; 503 00:17:53,620 --> 00:17:54,572 Καλό. 504 00:17:54,572 --> 00:17:56,000 Τέσσερις και έξι; 505 00:17:56,000 --> 00:17:58,380 Έξι και πέντε; 506 00:17:58,380 --> 00:17:59,470 Έξι και επτά; 507 00:17:59,470 --> 00:18:00,970 Εντάξει, τώρα, γίνει. 508 00:18:00,970 --> 00:18:01,550 Εντάξει, όχι. 509 00:18:01,550 --> 00:18:02,710 Πρέπει να πάω πίσω. 510 00:18:02,710 --> 00:18:05,130 >> Έτσι τώρα, και πάλι, το κάνουμε αυτό λίγο πιο συνειδητά. 511 00:18:05,130 --> 00:18:08,700 Και τώρα, υπάρχει μόνο έναν εγκέφαλο εκτέλεση αυτού του αλγορίθμου. 512 00:18:08,700 --> 00:18:10,290 Μία CPU, αν θέλετε. 513 00:18:10,290 --> 00:18:13,090 Και ειλικρινά, αυτός είναι ο μόνος πόρος θα πάμε να έχουν πρόσβαση. 514 00:18:13,090 --> 00:18:16,280 Και όταν εμείς πάμε πίσω σε ένα πληκτρολόγιο και να έχουν κάτι σαν C σε μας 515 00:18:16,280 --> 00:18:19,600 διάθεση, γράφουμε μόνο ένα πρόγραμμα ότι μπορεί να κάνει ένα πράγμα τη φορά. 516 00:18:19,600 --> 00:18:22,900 Ότι, αυτά τα παιδιά πριν από λίγο, εμείς μόχλευση συλλογική ευφυΐα τους 517 00:18:22,900 --> 00:18:24,180 όπως σ 'εσάς στην εβδομάδα μηδέν. 518 00:18:24,180 --> 00:18:24,980 Ας συνεχίσουμε να το κάνουμε αυτό. 519 00:18:24,980 --> 00:18:26,260 >> Δύο και μία. 520 00:18:26,260 --> 00:18:26,945 Δύο και τρία. 521 00:18:26,945 --> 00:18:27,460 Τρία και τέσσερα. 522 00:18:27,460 --> 00:18:28,310 Τέσσερα και πέντε. 523 00:18:28,310 --> 00:18:28,620 Πέντε και έξι. 524 00:18:28,620 --> 00:18:30,510 Έξι και επτά. 525 00:18:30,510 --> 00:18:31,880 Έγινε; 526 00:18:31,880 --> 00:18:34,560 Είμαι, λοιπόν, αλλά επιτρέψτε μου να παίζουν συνήγορο του διαβόλου. 527 00:18:34,560 --> 00:18:37,950 Do I, το είδος του υπολογιστή που μόλις έκανε ένα πέρασμα μέσα από αυτή τη σειρά των 528 00:18:37,950 --> 00:18:40,225 οι άνθρωποι, ξέρουν ότι είμαι γίνει; 529 00:18:40,225 --> 00:18:40,670 >> ΟΜΙΛΗΤΗΣ 1: Όχι. 530 00:18:40,670 --> 00:18:41,050 >> David J. MALAN: ναι, γιατί; 531 00:18:41,050 --> 00:18:46,900 Τι θα πρέπει να κάνω για να συμπέρασμα αποφασιστικά ότι έχω κάνει; 532 00:18:46,900 --> 00:18:48,230 Πιθανώς ένα ακόμη περάσει. 533 00:18:48,230 --> 00:18:48,430 Σωστά; 534 00:18:48,430 --> 00:18:51,760 Επειδή το μόνο που ξέρω από την προηγούμενη pass είναι ότι έχω διορθωθεί ένα λάθος. 535 00:18:51,760 --> 00:18:53,920 Και αυτό σημαίνει, ίσως υπάρχει ακόμα ένα άλλο λάθος 536 00:18:53,920 --> 00:18:54,840 ότι πρέπει να διορθωθεί. 537 00:18:54,840 --> 00:18:58,680 Γι 'αυτό να είστε σίγουροι από κουρδίζεται, και τότε τον έλεγχο, ένα έως δύο, δύο και 538 00:18:58,680 --> 00:19:00,940 τρία, τρία και τέσσερα, τέσσερα και πέντε, πέντε και έξι, έξι και επτά. 539 00:19:00,940 --> 00:19:02,510 Εντάξει, τώρα έκανα καμία εργασία. 540 00:19:02,510 --> 00:19:05,990 >> Μπορώ σίγουρα να θυμάστε ότι έκανα κανένα συνεργαστεί με κάτι σαν μια μεταβλητή, 541 00:19:05,990 --> 00:19:06,975 όπως έναν int. 542 00:19:06,975 --> 00:19:12,490 Καλέστε swaps, και αν swaps είναι 0 αφού την έχω πάρετε εδώ, και που άρχισε στο 0, τότε 543 00:19:12,490 --> 00:19:15,520 Θα ήθελα απλά να είναι ανόητο να συνεχίζω εμπρός και πίσω, τον έλεγχο και πάλι, και 544 00:19:15,520 --> 00:19:16,450 ξανά και ξανά, έτσι δεν είναι; 545 00:19:16,450 --> 00:19:18,450 Επειδή έχετε κολλήσει σε ορισμένες είδος άπειρο βρόχο. 546 00:19:18,450 --> 00:19:21,250 Έτσι, το συντομότερο υπάρχει 0 swaps, μπορούμε να ισχυριστούμε ότι αυτή η 547 00:19:21,250 --> 00:19:23,810 αλγόριθμος είναι πράγματι πλήρης. 548 00:19:23,810 --> 00:19:25,400 >> Τώρα, ας βάλουμε ένα όνομα για το θέμα αυτό. 549 00:19:25,400 --> 00:19:28,930 Ο αλγόριθμος που προτείνουμε μόνο εφαρμοστεί είναι κάτι που ονομάζεται φυσαλίδα 550 00:19:28,930 --> 00:19:32,800 Ταξινόμηση, που είναι γνωστή ως τέτοια κατά την έννοια ότι οι αριθμοί που είναι μεγαλύτερα του είδους του 551 00:19:32,800 --> 00:19:37,990 φούσκα δρόμο τους προς την κορυφή, ή μέχρι στο τέλος της συστοιχίας των αριθμών. 552 00:19:37,990 --> 00:19:40,270 Αλλά πόσο αποτελεσματική ήταν ο αλγόριθμος αυτός; 553 00:19:40,270 --> 00:19:44,600 Πόσα βήματα εγώ φυσικά πρέπει να να λάβει, για παράδειγμα, για να ταξινομήσετε αυτά 554 00:19:44,600 --> 00:19:45,850 επτά ανθρώπους; 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Τέσσερις με πέντε; 557 00:19:49,550 --> 00:19:51,420 OK, πάρα πολλά είναι τελικά πρόκειται να είναι η απάντηση. 558 00:19:51,420 --> 00:19:54,960 Αλλά ακόμα και τότε, ο συγκεκριμένος αριθμός δεν είναι τόσο ενδιαφέρουσα. 559 00:19:54,960 --> 00:19:56,670 Ας το γενικεύσουμε ως n. 560 00:19:56,670 --> 00:20:00,520 Έτσι, αν είχα n ανθρώπους εδώ, και ήταν, είδος, σε τυχαία σειρά στο 561 00:20:00,520 --> 00:20:02,180 αρχή, σε αυτή την αρχική σειρά. 562 00:20:02,180 --> 00:20:04,910 Λοιπόν, πόσα βήματα δεν έχω να αναλάβει το πρώτο πέρασμα; 563 00:20:04,910 --> 00:20:09,810 Ήταν ένα, δύο, τρία, τέσσερα, πέντε, έξι, και είναι επτά άτομα, έτσι ώστε 564 00:20:09,810 --> 00:20:13,670 αυτό είναι επτά, έξι -, έτσι ώστε να είναι n μείον ένα βήματα την πρώτη φορά. 565 00:20:13,670 --> 00:20:16,280 >> Τώρα, πόσα βήματα δεν έχω να ληφθούν όταν rewound; 566 00:20:16,280 --> 00:20:19,310 Λοιπόν, θα μπορούσε πραγματικά να διπλασιαστεί ότι εάν θέλαμε πραγματικά, αλλά για τώρα, είμαι 567 00:20:19,310 --> 00:20:22,300 ακριβώς πρόκειται να πω, εντάξει, Ένας άλλος N μείον 1. 568 00:20:22,300 --> 00:20:25,240 Έτσι, το n μείον 1 πρόκειται να πάρει ενοχλητικό να παρακολουθείτε, οπότε ας 569 00:20:25,240 --> 00:20:26,400 απλά στρογγυλοποιεί προς τα πάνω ελαφρά. 570 00:20:26,400 --> 00:20:27,770 Έτσι 2n βήματα. 571 00:20:27,770 --> 00:20:29,310 Μέχρι 14 βήματα, ή να δώσει. 572 00:20:29,310 --> 00:20:31,930 >> Πόσες φορές δεν έχω λάβει ένα βήμα προς την επόμενη φορά; 573 00:20:31,930 --> 00:20:33,740 Λοιπόν, αυτό είναι 3η. 574 00:20:33,740 --> 00:20:34,510 πραγματικά. 575 00:20:34,510 --> 00:20:37,920 Και τώρα, στη χειρότερη περίπτωση, για παράδειγμα, πόσες φορές θα έχω 576 00:20:37,920 --> 00:20:41,730 πάει εμπρός και πίσω, εμπρός και πίσω, εκτελεί αυτόν τον αλγόριθμο, ανταλλάσσοντας 577 00:20:41,730 --> 00:20:44,620 οι άνθρωποι σε κάθε πέρασμα, περίπου; 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Είναι πραγματικά n τετράγωνο, έτσι δεν είναι; 580 00:20:50,010 --> 00:20:53,000 >> Επειδή στη χειρότερη περίπτωση, μπορείτε να το είδος της σκεφτούμε αυτό διαισθητικά, 581 00:20:53,000 --> 00:20:54,800 έστω και αν θα μπορούσε να πάρει λίγο λίγο χρόνο για να βυθίζουν μέσα 582 00:20:54,800 --> 00:20:57,590 Στη χειρότερη περίπτωση, αυτό θα ήταν αυτά επτά άνθρωποι έχουν έμοιαζε, σε 583 00:20:57,590 --> 00:21:00,230 όρους της συμφωνίας του αριθμού τους; 584 00:21:00,230 --> 00:21:01,460 Εντελώς προς τα πίσω, έτσι δεν είναι; 585 00:21:01,460 --> 00:21:02,815 Και ακριβώς για να προσομοιώσει ότι, Τι ήταν το όνομά σας και πάλι; 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> David J. MALAN: Mike; 588 00:21:03,640 --> 00:21:08,100 Εντάξει, Mike, μπορείτε να συμμετάσχετε με μόλις πάνω από εδώ μόνο για ένα λεπτό; 589 00:21:08,100 --> 00:21:08,880 Στην πραγματικότητα, όχι. 590 00:21:08,880 --> 00:21:10,150 Δυστυχώς Mike, rewind ας. 591 00:21:10,150 --> 00:21:10,910 Ποιο είναι το όνομά σας και πάλι; 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> David J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 Εντάξει, Neil, θα έρθει με μένα, αν δεν σας πειράζει. 595 00:21:13,750 --> 00:21:17,150 Έτσι, Πάω να προτείνω, μόνο για απλότητα, ότι ο Neil είναι τώρα στο δικό του 596 00:21:17,150 --> 00:21:18,510 χειρότερη δυνατή περίπτωση. 597 00:21:18,510 --> 00:21:20,720 Αλλά θυμηθούμε πώς θα εφαρμοστεί αλγόριθμο μου. 598 00:21:20,720 --> 00:21:24,530 Είμαι σύγκριση, η σύγκριση, η σύγκριση, συγκρίνοντας, συγκρίνοντας, oh. 599 00:21:24,530 --> 00:21:26,640 Τώρα, αυτοί οι τύποι είναι έξω της τάξης, έτσι μπορώ να διορθώσω. 600 00:21:26,640 --> 00:21:27,980 Έτσι ανταλλάξουν εσείς. 601 00:21:27,980 --> 00:21:31,630 Αλλά σκεφτείτε τώρα, πόσο πιο μακριά Neil δεν πρέπει να πάει; 602 00:21:31,630 --> 00:21:32,690 Είναι περίπου n. 603 00:21:32,690 --> 00:21:33,570 Ξέρεις, δεν είναι στην πραγματικότητα n. 604 00:21:33,570 --> 00:21:36,040 Είναι σαν, n μείον 1, αλλά είμαι πάρει ενοχλημένος κομμάτι διατήρηση του μικρού 605 00:21:36,040 --> 00:21:37,550 αριθμό, οπότε ας το ονομάσουμε n. 606 00:21:37,550 --> 00:21:42,860 >> Έτσι, αν Neil κινείται ένα βήμα μέγιστο κάθε το χρόνο, και να προχωρήσουμε ένα βήμα Neil, 607 00:21:42,860 --> 00:21:46,580 Έχω να κάνω αυτό το πραγματικά κουραστική pass εμπρός και πίσω, αυτό είναι κατά προσέγγιση 608 00:21:46,580 --> 00:21:52,080 τρόπο αυτό, n βήματα, συνολικά n φορές, επειδή πρόκειται να με πάρει 609 00:21:52,080 --> 00:21:55,820 ότι πολλά βήματα για να πάρετε Neil όλα ο τρόπος για να όπου ανήκει. 610 00:21:55,820 --> 00:21:58,620 Πόσο μάλλον όλοι οι άλλοι αν εσείς ήταν όλα λανθασμένη εντολή, καθώς και. 611 00:21:58,620 --> 00:22:01,100 >> Έτσι, ας την ονομάσουμε είδος φούσκα n τετράγωνο. 612 00:22:01,100 --> 00:22:04,860 Ο χρόνος εκτέλεσης αυτού του αλγορίθμου, η απόδοση αυτού του αλγορίθμου, η 613 00:22:04,860 --> 00:22:07,120 απόδοση αυτού του αλγορίθμου, θα περιγράψουμε ακριβώς περισσότερο 614 00:22:07,120 --> 00:22:08,800 γενικά σαν Ν τετράγωνο. 615 00:22:08,800 --> 00:22:11,650 Ποια είναι ωραία, γιατί θα μπορούσα να κάνω το ίδιο παράδειγμα με οκτώ άτομα, εννέα 616 00:22:11,650 --> 00:22:15,450 άτομα, ένα εκατομμύριο άνθρωποι, και ότι απάντηση δεν πρόκειται να αλλάξει. 617 00:22:15,450 --> 00:22:18,870 >> Έτσι, αν εσείς δεν θα με πείραζε, ας επαναφέρετε σας όπου αρχίσατε. 618 00:22:18,870 --> 00:22:22,510 Και ας προσπαθήσουμε δύο άλλες προσεγγίσεις και δούμε αν δεν μπορούμε να κάνουμε ουσιαστικά 619 00:22:22,510 --> 00:22:23,820 καλύτερα από αυτό. 620 00:22:23,820 --> 00:22:27,130 Έτσι, αυτή τη φορά, Πάω να προτείνει ένα είδος διαφορετικό αλγόριθμο. 621 00:22:27,130 --> 00:22:29,950 Αυτό ήταν πολύ έξυπνο από εμάς την τελευταία φορά, και εσείς είχαν δικαίωμα να έχουν την 622 00:22:29,950 --> 00:22:32,470 δικαίωμα ένστικτα του ακριβώς το είδος της swapping ζεύγη. 623 00:22:32,470 --> 00:22:36,500 Αλλά αν πραγματικά ήθελε να προσεγγίσουμε το θέμα απλά, και ο στόχος μου είναι να προχωρήσουμε 624 00:22:36,500 --> 00:22:39,800 όλα τα μικρά αριθμών αυτό τον τρόπο, και ωθήσει όλα τα μεγάλα νούμερα που 625 00:22:39,800 --> 00:22:43,030 τρόπο, γιατί να μην το κάνω μόνο ότι η πιο αφελής δυνατό τρόπο και να δω αν μπορώ 626 00:22:43,030 --> 00:22:45,730 μπορεί να κάνει καλύτερα από ό, τι ήταν αρκετά σύνθετο αλγόριθμο; 627 00:22:45,730 --> 00:22:46,620 >> Ας δούμε λοιπόν. 628 00:22:46,620 --> 00:22:48,940 Τέσσερις είναι ένα όμορφο μικρό αριθμό, έτσι είμαι πρόκειται να σας αφήσει εκεί τη στιγμή. 629 00:22:48,940 --> 00:22:50,610 Ooh, νούμερο δύο είναι ακόμα καλύτερα. 630 00:22:50,610 --> 00:22:52,230 Έτσι, μπορεί απλά βήμα προς τα εμπρός για μια στιγμή; 631 00:22:52,230 --> 00:22:55,670 Αυτό είναι σήμερα μικρότερο αριθμημένα μου υποψήφιος, και πάω να θυμόμαστε 632 00:22:55,670 --> 00:22:57,000 ότι με την, όπως, μια μεταβλητή. 633 00:22:57,000 --> 00:22:57,930 Αλλά Πάω να κρατήσει τον έλεγχο. 634 00:22:57,930 --> 00:22:59,890 Υπάρχει κάποιος του οποίου υπάρχει αριθμός είναι μικρότερος; 635 00:22:59,890 --> 00:23:00,460 Έξι, ηο. 636 00:23:00,460 --> 00:23:01,390 Ω, υπάρχει Neil πάλι. 637 00:23:01,390 --> 00:23:04,050 >> Έτσι, Πάω να σας ωθήσει πίσω είδος εννοιολογικά. 638 00:23:04,050 --> 00:23:05,120 Neil θα έρθει προς τα εμπρός. 639 00:23:05,120 --> 00:23:08,440 Και, τώρα η μεταβλητή που είμαι με τη χρήση για την να παρακολουθείτε ποιος έχει το μικρότερο 640 00:23:08,440 --> 00:23:11,390 Αριθμός ενημερώνεται για να περιέχουν Θέση του Neil. 641 00:23:11,390 --> 00:23:12,110 Λοιπόν, ας δούμε. 642 00:23:12,110 --> 00:23:13,960 Τρεις, επτά, πέντε. 643 00:23:13,960 --> 00:23:15,590 Εντάξει, ξέρω ότι ο Neil ήταν το μικρότερο. 644 00:23:15,590 --> 00:23:18,110 Ποιο είναι το πιο απλό πράγμα για μένα να κάνω τώρα; 645 00:23:18,110 --> 00:23:21,410 Δεν πρόκειται να σπαταλήσω το χρόνο μου με απλά διοχέτευσή του Neil ένα σημείο προς τα αριστερά. 646 00:23:21,410 --> 00:23:25,350 Γιατί δεν έβαλα ακριβώς Neil όπου ανήκει, το οποίο είναι, φυσικά, πού; 647 00:23:25,350 --> 00:23:26,160 >> Όλος ο τρόπος κατά την έναρξη. 648 00:23:26,160 --> 00:23:27,720 Έτσι Neil, έλα μαζί μου. 649 00:23:27,720 --> 00:23:28,910 Και ποιο ήταν το όνομά σας και πάλι; 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Γκρέις. 651 00:23:29,310 --> 00:23:29,710 >> David J. MALAN: Γκρέις. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Έτσι, Γκρέις, δυστυχώς, είστε είδος με τον τρόπο. 654 00:23:32,490 --> 00:23:34,290 Επομένως, πώς θα λύσουμε αυτό το πρόβλημα; 655 00:23:34,290 --> 00:23:34,490 Σωστά; 656 00:23:34,490 --> 00:23:37,500 Εάν αυτό είναι ένας πίνακας, υπάρχει μόνο επτά θέσεις. 657 00:23:37,500 --> 00:23:40,830 Υπενθυμίζεται ότι, με τον Rob, μιλήσαμε για δηλώνοντας τις ηλικίες, και είχαμε μόνο ένα 658 00:23:40,830 --> 00:23:41,740 πεπερασμένο αριθμό των ηλικιών; 659 00:23:41,740 --> 00:23:42,535 Ίδια ιδέα εδώ. 660 00:23:42,535 --> 00:23:44,300 Έχουμε μόνο έναν πεπερασμένο αριθμό ints. 661 00:23:44,300 --> 00:23:47,590 Γκρέις είναι το είδος της σε μας τρόπο, έτσι πώς να διορθώσετε; 662 00:23:47,590 --> 00:23:49,555 >> Ο απλούστερος τρόπος είναι παρόμοια, Χάρη, συγγνώμη. 663 00:23:49,555 --> 00:23:51,870 Θα πάμε να πρέπει να πάει πέρα ​​από οπότε εκεί μπορούμε να κάνουμε χώρο. 664 00:23:51,870 --> 00:23:55,290 Τώρα, αν το σκεφτούμε αυτό, ίσως Εμείς απλά έκανε το πρόβλημα χειρότερο. 665 00:23:55,290 --> 00:23:58,510 Και ίσως κάναμε, γιατί ό, τι και αν Γκρέις ήταν στο σωστό μέρος; 666 00:23:58,510 --> 00:24:01,730 Αλλά ξέρουμε ότι δεν είναι, γιατί διαφορετικά, ότι θα ήταν 667 00:24:01,730 --> 00:24:03,980 στέκεται μπροστά αντί Neil αυτή τη στιγμή, έτσι δεν είναι; 668 00:24:03,980 --> 00:24:05,550 Έχουμε ήδη ελέγξει τον αριθμό της έξω. 669 00:24:05,550 --> 00:24:05,770 >> Εντάξει. 670 00:24:05,770 --> 00:24:09,110 Έτσι τώρα, Neil είναι στο σωστό μέρος, και Μπορώ να κάνω μια μικρή βελτιστοποίησης. 671 00:24:09,110 --> 00:24:11,740 Για το επόμενο λεπτό, Πάω να αγνοήσει Neil όλα μαζί, έτσι ώστε να μην 672 00:24:11,740 --> 00:24:15,280 σπαταλήσει το χρόνο του, ή τυχαία ανταλλάξουν τον στο λάθος μέρος. 673 00:24:15,280 --> 00:24:17,805 Έτσι τώρα, πώς μπορώ να βρω το επόμενο στοιχείο που είναι μικρότερη; 674 00:24:17,805 --> 00:24:18,480 Δύο. 675 00:24:18,480 --> 00:24:20,225 Αυτό είναι ένα αρκετά καλό αριθμό, αν θέλετε να το βήμα προς τα εμπρός και 676 00:24:20,225 --> 00:24:21,100 Θα θυμάστε. 677 00:24:21,100 --> 00:24:21,980 Έξι, δεν είναι καλό. 678 00:24:21,980 --> 00:24:24,820 Τέσσερα, τρία, επτά, πέντε, δεν είναι καλό. 679 00:24:24,820 --> 00:24:26,800 Έτσι, επιτρέψτε μου να σας μετακινήσει σε σωστό μέρος σας. 680 00:24:26,800 --> 00:24:28,470 Και εμείς απλά στάθηκε τυχερός αυτή τη φορά. 681 00:24:28,470 --> 00:24:31,350 >> Τώρα, είμαι πρόκειται να αγνοήσει δύο παιδιά, και να κάνουμε τώρα ένα ακόμη 682 00:24:31,350 --> 00:24:32,260 να περάσει μέσα από αυτό. 683 00:24:32,260 --> 00:24:33,490 Έξι, ότι ένας πολύ μικρός αριθμός. 684 00:24:33,490 --> 00:24:34,300 Έλα προς τα εμπρός. 685 00:24:34,300 --> 00:24:35,220 Ω, συγγνώμη. 686 00:24:35,220 --> 00:24:37,640 Grace Αριθμός είναι καλύτερη, έτσι βήμα για τα εμπρός. 687 00:24:37,640 --> 00:24:38,260 Four. 688 00:24:38,260 --> 00:24:39,120 Δυστυχώς, Γκρέις. 689 00:24:39,120 --> 00:24:39,950 Πήγαινε πάλι πίσω. 690 00:24:39,950 --> 00:24:41,550 Νούμερο τρία είναι καλύτερη. 691 00:24:41,550 --> 00:24:42,290 Επτά. 692 00:24:42,290 --> 00:24:42,720 Πέντε. 693 00:24:42,720 --> 00:24:43,550 Και τώρα τι είναι το όνομά σας και πάλι; 694 00:24:43,550 --> 00:24:44,000 >> ΙΑΣΩΝ: Jason. 695 00:24:44,000 --> 00:24:44,420 >> David J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Έτσι ο Ιάσονας είναι πλέον το μικρότερο στοιχείο που έχω επιλέξει. 697 00:24:47,050 --> 00:24:49,160 Πού θα πήγαινε; 698 00:24:49,160 --> 00:24:50,380 Έτσι, όταν έξι είναι. 699 00:24:50,380 --> 00:24:51,210 Και το όνομά σου είναι πάλι; 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> David J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe είναι στο δρόμο. 703 00:24:53,220 --> 00:24:54,640 Ποιο είναι το πιο εύκολο πράγμα να κάνουμε; 704 00:24:54,640 --> 00:24:58,390 Εναλλαγή αυτά τα δύο παιδιά και να συνεχίσει. 705 00:24:58,390 --> 00:24:59,020 Έτσι τώρα ας δούμε. 706 00:24:59,020 --> 00:25:00,170 Ποιος είναι ο μικρότερος; 707 00:25:00,170 --> 00:25:01,030 Four. 708 00:25:01,030 --> 00:25:01,990 Επιτρέψτε μου ακριβώς το είδος της εξαπατήσει. 709 00:25:01,990 --> 00:25:03,090 Πέντε θα είναι το μικρότερο. 710 00:25:03,090 --> 00:25:05,220 Θεωρώ ότι το επόμενο, αν θέλετε να το βήμα προς τα εμπρός, τι πρέπει να κάνω με 711 00:25:05,220 --> 00:25:06,820 αυτά τα παιδιά, με Gabe; 712 00:25:06,820 --> 00:25:08,450 Εναλλαγή και πάλι. 713 00:25:08,450 --> 00:25:10,740 Έτσι τώρα, εξακολουθεί να είναι ελαφρά εκτός λειτουργίας. 714 00:25:10,740 --> 00:25:14,140 Βρήκα Gabe είναι το μικρότερο, οπότε Τον πεταχτεί έξω, μετακινήστε εσείς πάνω. 715 00:25:14,140 --> 00:25:15,190 Και κάνει. 716 00:25:15,190 --> 00:25:17,200 >> Έτσι απάντηση είναι η ίδια. 717 00:25:17,200 --> 00:25:18,600 Το τελικό αποτέλεσμα είναι το ίδιο. 718 00:25:18,600 --> 00:25:22,730 Ποια από αυτές τις δύο αλγορίθμων είναι καλύτερα; 719 00:25:22,730 --> 00:25:23,500 Το δεύτερο, το άκουσα. 720 00:25:23,500 --> 00:25:24,252 Γιατί; 721 00:25:24,252 --> 00:25:25,900 >> ΟΜΙΛΗΤΗΣ 3: Είναι n βήματα [δεν ακούγεται]. 722 00:25:25,900 --> 00:25:27,600 >> David J. MALAN: Είναι n βήματα το πολύ. 723 00:25:27,600 --> 00:25:28,490 Ενδιαφέρουσες. 724 00:25:28,490 --> 00:25:30,610 Έτσι είναι όμως; 725 00:25:30,610 --> 00:25:33,630 Λοιπόν, πώς μπορώ να βρω το μικρότερο στοιχείο; 726 00:25:33,630 --> 00:25:37,060 Πόσα βήματα εγώ πρέπει να λάβουν το να βρει το μικρότερο στοιχείο; 727 00:25:37,060 --> 00:25:39,220 Έριξα μια ματιά σε όλη τη διαδρομή στο τέλος, έτσι δεν είναι; 728 00:25:39,220 --> 00:25:41,530 Διότι στην χειρότερη περίπτωση, αυτό αν Neil ήταν εδώ; 729 00:25:41,530 --> 00:25:45,700 Έτσι, την εύρεση ακριβώς το μικρότερο στοιχείο μου παίρνει n βήματα, ή n μείον 1. 730 00:25:45,700 --> 00:25:46,100 Αλλά, εντάξει. 731 00:25:46,100 --> 00:25:46,980 Έτσι καθορίζουν το Neil. 732 00:25:46,980 --> 00:25:48,740 Να θυμάστε ότι, ένα λεπτό ή έτσι πριν. 733 00:25:48,740 --> 00:25:51,680 >> Αλλά πώς μπορώ να βρω το επόμενο μικρότερο στοιχείο; 734 00:25:51,680 --> 00:25:54,830 Είναι n μείον 1, ή Ν μείον 2 πραγματικά, από τον αριθμό των βημάτων. 735 00:25:54,830 --> 00:25:55,440 Έτσι OK. 736 00:25:55,440 --> 00:25:57,390 Έτσι έκανα n μείον 2. 737 00:25:57,390 --> 00:25:57,600 Εντάξει. 738 00:25:57,600 --> 00:25:59,130 Έτσι ώστε να αισθάνεται λίγο καλύτερα. 739 00:25:59,130 --> 00:25:59,730 Εντάξει. 740 00:25:59,730 --> 00:26:03,270 Πόσα βήματα την επόμενη φορά για να βρείτε τον αριθμό τρία; 741 00:26:03,270 --> 00:26:04,420 Έτσι, n μείον 4. 742 00:26:04,420 --> 00:26:07,670 Έτσι είναι φθίνουσα, ένα λιγότερο βήμα σε κάθε επανάληψη. 743 00:26:07,670 --> 00:26:08,740 Έτσι, αυτό δεν αισθάνεστε καλύτερα, έτσι δεν είναι; 744 00:26:08,740 --> 00:26:13,450 Εάν η τελευταία φορά ήταν περίπου n φορές n, αυτή τη φορά είναι n μείον 1, συν n μείον 745 00:26:13,450 --> 00:26:16,500 2, καθώς και n μείον 3, καθώς και n μείον 4, τελεία, τελεία, τελεία. 746 00:26:16,500 --> 00:26:18,750 Αλλά αν θυμάστε από το γυμνάσιο σας εγχειρίδια, η μικρή εξαπατήσει 747 00:26:18,750 --> 00:26:24,380 φύλλο στο πίσω μέρος που έχει τύπους, αν μπορείτε να προσθέσετε μέχρι αυτή τη σειρά των αριθμών, 748 00:26:24,380 --> 00:26:31,280 ό, τι είναι ο συνολικός αριθμός των βημάτων πρόκειται να είναι ότι παίρνω εδώ; 749 00:26:31,280 --> 00:26:36,580 >> Αυτό είναι ένα από αυτά, όπως, n μείον 1, Ν φορές, διαιρείται με το 2. 750 00:26:36,580 --> 00:26:39,040 Έτσι, επιτρέψτε μου να δω αν μπορώ να τραβήξει αυτό για μια στιγμή. 751 00:26:39,040 --> 00:26:42,230 Και πάλι, είμαι το είδος του στρογγυλοποίηση ορισμένων αριθμούς μόνο για να κρατήσει τη ζωή μας απλή, 752 00:26:42,230 --> 00:26:47,830 αλλά από όσο θυμάμαι, είναι κάτι σαν, αν Κάνω n μείον 1 πράγματα, τότε n μείον 753 00:26:47,830 --> 00:26:53,570 2, τότε n μείον 3, είναι περίπου κάτι σαν αυτό πάνω από 2, και αν 754 00:26:53,570 --> 00:26:55,510 πολλαπλασιάστε αυτό έξω, αυτό είναι στην πραγματικότητα πλατεία n. 755 00:26:55,510 --> 00:26:58,940 Αυτό δεν νιώθει πολύ καλά. n μείον n πάνω από 2. 756 00:26:58,940 --> 00:27:00,350 >> Αλλά εδώ είναι το πράγμα. 757 00:27:00,350 --> 00:27:03,720 Στην επιστήμη των υπολογιστών, όταν τα προβλήματα αρχίζουν να παίρνουν ενδιαφέρον είναι όταν n 758 00:27:03,720 --> 00:27:04,700 παίρνει πραγματικά μεγάλο. 759 00:27:04,700 --> 00:27:08,110 Και όταν το n παίρνει πραγματικά μεγάλο, ποια από αυτές οι αξίες πρόκειται να κυριαρχούν σε όλα 760 00:27:08,110 --> 00:27:09,750 από τους άλλους; 761 00:27:09,750 --> 00:27:10,990 Είναι το είδος του n τετράγωνο, έτσι δεν είναι; 762 00:27:10,990 --> 00:27:13,340 Ναι, η διαίρεση με το 2 είναι πολύ καλή. 763 00:27:13,340 --> 00:27:16,740 Αλλά αν μιλάμε για δισεκατομμύρια κομμάτια των δεδομένων, ή τρισεκατομμύρια 764 00:27:16,740 --> 00:27:18,700 κομμάτια των δεδομένων, ΕΝΤΑΞΕΙ, έτσι είστε δύο φορές πιο γρήγορα. 765 00:27:18,700 --> 00:27:22,440 Αλλά ποιος νοιάζεται πραγματικά εάν αυτό το μεγάλο αριθμό, Αν αυτός ο παράγοντας είναι αυτό που παίρνει 766 00:27:22,440 --> 00:27:23,040 όλο και μεγαλύτερες. 767 00:27:23,040 --> 00:27:25,990 Και σίγουρα, θα κάνει περισσότερα από διαφορά από αυτόν τον τύπο. 768 00:27:25,990 --> 00:27:29,120 Έτσι ακόμα κι αν εσείς δίκιο, η δεύτερος αλγόριθμος, θα την αποκαλούμε 769 00:27:29,120 --> 00:27:32,970 Ταξινόμηση επιλογής, είναι, στον πραγματικό κόσμο, ένα λίγο πιο γρήγορα δυνητικά, επειδή είμαι 770 00:27:32,970 --> 00:27:35,360 λαμβάνοντας όλο και λιγότεροι βήματα κάθε φορά. 771 00:27:35,360 --> 00:27:37,340 >> Δεν είναι πραγματικά ουσιαστικά γρηγορότερα. 772 00:27:37,340 --> 00:27:41,430 Γιατί αν παίζουμε πραγματικά αυτό έξω για μεγάλες τιμές του n, στο τέλος της 773 00:27:41,430 --> 00:27:44,750 την ημέρα, για αρκετά μεγάλο n, είναι ακόμα πρόκειται να αισθανθείτε πολύ αργή. 774 00:27:44,750 --> 00:27:46,770 Λοιπόν, επιτρέψτε μου να πάρει ένα τελευταίο πέρασμα σε αυτό. 775 00:27:46,770 --> 00:27:48,920 Αυτό είναι που εγώ θα αποκαλούσα Ταξινόμηση επιλογής. 776 00:27:48,920 --> 00:27:51,040 Μπορεί εσείς τον εαυτό σας επαναφέρετε για τελευταία φορά; 777 00:27:51,040 --> 00:27:53,550 Και στην τελευταία αυτή περίπτωση, Πάω να προτείνω κάτι 778 00:27:53,550 --> 00:27:54,970 ονομάζεται ταξινόμηση με εισαγωγή. 779 00:27:54,970 --> 00:27:57,470 Ταξινόμηση με εισαγωγή είναι, θεωρητικά, λίγο διαφορετική. 780 00:27:57,470 --> 00:28:00,980 >> Αντί να πηγαίνει πέρα ​​δώθε και επιλέγοντας το μικρότερο στοιχείο, είμαι 781 00:28:00,980 --> 00:28:05,030 ακριβώς πρόκειται να ασχοληθεί με κάθε μία από αυτές παιδιά, όπως εγώ τους συναντήσει, και τοποθετήστε 782 00:28:05,030 --> 00:28:06,850 τους σε σωστή θέση τους. 783 00:28:06,850 --> 00:28:10,160 Έτσι, είμαι απλώς πρόκειται να ξεκινήσει με την Γκρέις, και βλέπω ότι είναι το νούμερο τέσσερα. 784 00:28:10,160 --> 00:28:11,720 Πού αριθμός τέσσερα ανήκουν; 785 00:28:11,720 --> 00:28:14,940 Δεν έχω αρχίσει διαλογή τίποτα, ούτω και η χάρις παίρνει να μείνει εκεί. 786 00:28:14,940 --> 00:28:18,355 Και τώρα πάω να διεκδικήσουν, αν θα μπορούσατε κάνουμε ένα βήμα προς τα δεξιά σας, αυτό 787 00:28:18,355 --> 00:28:21,650 ταξινομημένη λίστα μου, αυτό είναι μου αδιαχώριστα υπόλοιπο κατάλογο. 788 00:28:21,650 --> 00:28:23,260 Έτσι τώρα είμαι πρόκειται να προχωρήσει το επόμενο, και τι είναι το όνομά σας και πάλι; 789 00:28:23,260 --> 00:28:23,700 >> Branson:. 790 00:28:23,700 --> 00:28:24,150 >> David J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Έτσι Branson είναι το νούμερο δύο. 792 00:28:25,375 --> 00:28:27,490 Έτσι, Πάω να σας μεταφέρει έξω για μια στιγμή. 793 00:28:27,490 --> 00:28:30,940 Και, τώρα, όπου ανήκετε σε αυτή την σειρά; 794 00:28:30,940 --> 00:28:32,360 Έτσι, το δικαίωμα της Χάριτος. 795 00:28:32,360 --> 00:28:35,670 Έτσι και πάλι, είμαστε το είδος των αποφάσεων Γκρέις κάνει πολλή δουλειά εδώ. 796 00:28:35,670 --> 00:28:37,290 Πού θα βάλετε; 797 00:28:37,290 --> 00:28:40,120 Έτσι θα πάμε για να σύρετε με το αριστερά, και τοποθετήστε Branson εκεί. 798 00:28:40,120 --> 00:28:41,680 Τώρα, όμως, ισχυρίζονται ότι γίνονται εσείς. 799 00:28:41,680 --> 00:28:43,240 Αλλά προσέξτε, δεν είμαι με επιπλέον χώρο. 800 00:28:43,240 --> 00:28:45,130 Είναι ακόμα 2 στοιχεία εδώ, 5 εδώ. 801 00:28:45,130 --> 00:28:47,910 Συνολικό μέγεθος του πίνακα είναι 7, έτσι είμαι Δεν εξαπάτηση, εντάξει; 802 00:28:47,910 --> 00:28:51,950 >> Έτσι τώρα έχουμε, με Gabe εδώ, η νούμερο έξι, όπου ανήκετε; 803 00:28:51,950 --> 00:28:52,650 Έχεις τυχερός και πάλι. 804 00:28:52,650 --> 00:28:53,820 Έτσι, μπορείτε να πάρετε για να μείνουν εκεί. 805 00:28:53,820 --> 00:28:57,210 Απλώς πάρτε μια μικρή βήμα προς τη σωστή μόνο για να καταστήσει σαφές ότι είστε ταξινομημένο. 806 00:28:57,210 --> 00:29:00,520 Και τώρα έχουμε Neil, και πάλι τον αριθμό ένα, πού πας; 807 00:29:00,520 --> 00:29:03,540 Και τώρα είναι που θα αρχίσετε να βλέπετε ότι Ο αλγόριθμος αυτός, αν και σε πρώτη 808 00:29:03,540 --> 00:29:05,950 ματιά, αισθάνεται αρκετά έξυπνος, να παρακολουθήσετε τι πρόκειται να συμβεί. 809 00:29:05,950 --> 00:29:07,370 Αν θα μπορούσατε να βήμα προς τα εμπρός. 810 00:29:07,370 --> 00:29:09,260 >> Πού θέλουμε να θέσει Neil; 811 00:29:09,260 --> 00:29:11,830 Έτσι, προφανώς, εδώ, έτσι πώς παίρνουμε Neil εκεί; 812 00:29:11,830 --> 00:29:12,970 Ας κάνουμε αυτό το βήμα-βήμα. 813 00:29:12,970 --> 00:29:15,620 Gabe, όπου χρειάζεται να πάτε; 814 00:29:15,620 --> 00:29:19,590 Ναι, έτσι ώστε να λάβει ένα μεγάλο βήμα, ή δύο μισά βήματα για να κάνετε 815 00:29:19,590 --> 00:29:20,820 ένα βήμα εκεί. 816 00:29:20,820 --> 00:29:21,750 Γκρέις, όπου θα πάτε; 817 00:29:21,750 --> 00:29:22,510 Καλό. 818 00:29:22,510 --> 00:29:23,500 Έτσι, ένα ακόμη βήμα. 819 00:29:23,500 --> 00:29:24,960 Και τέλος, Branson; 820 00:29:24,960 --> 00:29:25,460 Ένα άλλο βήμα. 821 00:29:25,460 --> 00:29:27,190 Και τώρα μπορούμε να βάλουμε Neil στη θέση του. 822 00:29:27,190 --> 00:29:28,440 >> Έτσι τώρα, να συνεχίσει αυτή τη λογική. 823 00:29:28,440 --> 00:29:32,420 Ακόμα κι αν δεν είμαστε μετατόπιση Neil ξανά, και ξανά, και ξανά, να τον βάλουν 824 00:29:32,420 --> 00:29:36,420 όπου πηγαίνει, στη χειρότερη περίπτωση, η επόμενο αριθμό που μπορεί να συναντήσετε θα μπορούσε να 825 00:29:36,420 --> 00:29:42,220 είναι ο αριθμός, δηλαδή, υπήρχε ένας αριθμός μηδέν, τότε θα πάμε να μεταφερθεί το σύνολο των 826 00:29:42,220 --> 00:29:42,730 αυτά τα παιδιά. 827 00:29:42,730 --> 00:29:44,950 Ας υποθέσουμε ότι υπάρχει ένας αριθμός, αρνητική ένα, τότε θα πρέπει να στρέψουμε 828 00:29:44,950 --> 00:29:46,080 όλα αυτά τα παιδιά. 829 00:29:46,080 --> 00:29:48,500 Έτσι, είμαστε πραγματικά ακριβώς το είδος της flipping το πρόβλημα γύρω, έτσι ώστε να είμαστε 830 00:29:48,500 --> 00:29:52,620 μεταφέροντας το βάρος από το διαδικασία επιλογής έτσι ώστε η εισαγωγή 831 00:29:52,620 --> 00:29:56,930 διαδικασία, όπως ότι εσείς μόλις είχε να κινηθεί περίπου n μείον κάτι 832 00:29:56,930 --> 00:29:57,940 αριθμό των βημάτων. 833 00:29:57,940 --> 00:30:01,200 Και ο αριθμός των βημάτων που θα είναι μόνο να αυξηθεί, καθώς θα επιλέξετε περισσότερους αριθμούς, 834 00:30:01,200 --> 00:30:04,730 αν έχω να κρατήσει σπρώχνει εσείς πίσω, και πίσω, και πίσω. 835 00:30:04,730 --> 00:30:08,320 >> Έτσι, το λυπηρό είναι τώρα όλα αυτά αλγόριθμοι είναι n τετράγωνο. 836 00:30:08,320 --> 00:30:10,570 Ας πάμε μπροστά και χάρη σε αυτές παιδιά, και να απεικονίσει αυτά λίγο 837 00:30:10,570 --> 00:30:11,090 διαφορετικά. 838 00:30:11,090 --> 00:30:12,312 Πολύ καλά κάνει. 839 00:30:12,312 --> 00:30:14,120 >> [Χειροκρότημα] 840 00:30:14,120 --> 00:30:15,030 >> Εντάξει. 841 00:30:15,030 --> 00:30:16,280 Εκεί θα πάτε. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Ευχαριστώ για - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [δεν ακούγεται] να κρατήσει τους αριθμούς. 845 00:30:19,190 --> 00:30:21,990 >> David J. MALAN: Όχι, δεν μπορείτε κρατήσει τους αριθμούς, καθώς και. 846 00:30:21,990 --> 00:30:23,440 Εντάξει. 847 00:30:23,440 --> 00:30:24,100 Όμορφα γίνει. 848 00:30:24,100 --> 00:30:25,300 Εντάξει. 849 00:30:25,300 --> 00:30:30,510 Ας δούμε αν μπορούμε να μην μπορούν πλέον να συνοψίσουμε πιο γρήγορα και πιο οπτικά, 850 00:30:30,510 --> 00:30:33,410 ακριβώς ό, τι ακριβώς συνέβη εδώ ως εξής. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Πάω να προχωρήσει και τραβήξτε Firefox. 853 00:30:38,770 --> 00:30:41,310 Θα συνδεθεί αυτή η διαδήλωση στην ιστοσελίδα του μαθήματος. 854 00:30:41,310 --> 00:30:43,870 Java είναι λίγο ενοχλητικό να πάρει εργασίας σε ορισμένα προγράμματα περιήγησης αυτές τις μέρες. 855 00:30:43,870 --> 00:30:46,760 Έτσι, αν παίζουν με αυτό στο σπίτι, συνειδητοποιούν ίσως χρειαστεί να χρησιμοποιήσετε τον Firefox 856 00:30:46,760 --> 00:30:47,990 να το πάρει εργασίας. 857 00:30:47,990 --> 00:30:50,440 Και τι Πάω να κάνω με αυτό επίδειξης είναι η ακόλουθη. 858 00:30:50,440 --> 00:30:54,875 >> Στο κάτω μέρος, έχω ένα σωρό επιλογές μενού, όπως μια αρχή και 859 00:30:54,875 --> 00:30:55,840 να σταματήσει το κουμπί. 860 00:30:55,840 --> 00:30:59,450 Επίσης, ως ένα μέρος, φαίνεται να υπάρχει μια bug σε αυτά τα προγράμματα, σύμφωνα με την οποία θα 861 00:30:59,450 --> 00:31:03,720 Δεν μπορούν να δουν πραγματικά την έναρξη ή διακοπή πλήκτρο, εκτός κρατάτε Command ή Alt 862 00:31:03,720 --> 00:31:06,560 καθώς και η μεγέθυνση, η οποία περιέργως σας δείχνει περισσότερα κουμπιά. 863 00:31:06,560 --> 00:31:09,090 Έτσι, απλά FYI αν παίξετε με αυτό στο σπίτι. 864 00:31:09,090 --> 00:31:12,870 Τώρα είμαι πρόκειται να κάντε κλικ στο Έναρξη σε μόλις ένα στιγμή, μετά καθορίζοντας μια καθυστέρηση, 865 00:31:12,870 --> 00:31:16,810 όπως, 200 χιλιοστά του δευτερολέπτου εδώ, απλά ώστε να μπορούμε να δούμε τι θα συμβεί. 866 00:31:16,810 --> 00:31:20,180 >> Γι 'αυτό και ισχυρίζονται ότι αυτό είναι μια οπτικοποίηση του πρώτου αλγορίθμου 867 00:31:20,180 --> 00:31:23,730 αυτά τα παιδιά έκαναν, το είδος φούσκα, σύμφωνα με την οποία που αντάλλαξαν οι άνθρωποι ζεύγη. 868 00:31:23,730 --> 00:31:27,490 Η βασική αντίληψη σε αυτή την οπτικοποίηση είναι ότι το ύψος των ράβδων 869 00:31:27,490 --> 00:31:30,510 αντιπροσωπεύει το μέγεθος του αριθμού. 870 00:31:30,510 --> 00:31:32,210 Έτσι, το ψηλότερο το μπαρ, το μεγαλύτερος είναι ο αριθμός. 871 00:31:32,210 --> 00:31:33,680 Shorter το μπαρ, μικρότερος ο αριθμός. 872 00:31:33,680 --> 00:31:38,630 Και αν παρατηρήσετε, θα πάμε μέσα Η πρώτη επανάληψη αυτού του αλγορίθμου, 873 00:31:38,630 --> 00:31:42,620 εναλλαγή μεγάλων και μικρών αριθμών, έτσι ώστε να ο μικρός αριθμός έρχεται πρώτη και 874 00:31:42,620 --> 00:31:44,280 ο μεγάλος αριθμός πηγαίνει προς τα δεξιά. 875 00:31:44,280 --> 00:31:48,770 >> Και μόλις φτάσουμε στο τέλος του πίνακα από πολλά περισσότερα από επτά αριθμούς, είμαστε 876 00:31:48,770 --> 00:31:49,900 πρόκειται να πάει πίσω στην αρχή. 877 00:31:49,900 --> 00:31:51,140 Και την πρόβλεψη αυτή. 878 00:31:51,140 --> 00:31:54,860 Από την άκρα αριστερά, αυτό το μικρό τύπος συμβαίνει να ανταλλάξουν με την πλευρά της, και αυτό 879 00:31:54,860 --> 00:31:56,010 διαδικασία επαναλαμβάνεται. 880 00:31:56,010 --> 00:31:59,450 Τώρα αυτή η απεικόνιση παίρνει γρήγορα βαρετό, οπότε επιτρέψτε μου να πάει μπροστά και να σταματήσει 881 00:31:59,450 --> 00:32:04,170 αυτό, να αλλάξετε την καθυστέρηση κάτι πολύ γρηγορότερα για να πάρει ακριβώς, τώρα μια ιδέα για 882 00:32:04,170 --> 00:32:05,060 Αυτός ο αλγόριθμος. 883 00:32:05,060 --> 00:32:07,840 >> Έτσι, ακόμα κι αν έχω επιτάχυνε, αυτό είναι όπως η αναβάθμιση του επεξεργαστή μου, αγοράζοντας 884 00:32:07,840 --> 00:32:08,580 ένα νέο υπολογιστή. 885 00:32:08,580 --> 00:32:12,980 Δεν έχω αλλάξει ριζικά μου αλγόριθμο, αλλά μπορείτε να δείτε πράγματι πιο 886 00:32:12,980 --> 00:32:16,800 σαφώς από ό, τι με τους ανθρώπους, ότι η μεγάλη αριθμοί οι bubbling μέχρι την κορυφή, 887 00:32:16,800 --> 00:32:20,900 και οι μικροί αριθμοί είναι ανάδευση στο κάτω μέρος. 888 00:32:20,900 --> 00:32:22,390 Και τώρα αυτό το πράγμα εδώ ταξινομημένο. 889 00:32:22,390 --> 00:32:25,260 Και ως ένα μέρος, στις πλατείες, υπάρχει μόνο μερικά τήρησης βιβλίων εκεί για να 890 00:32:25,260 --> 00:32:28,010 να σας βοηθήσει να μετρήσουν πόσες συγκρίσεις, ή πόσα swaps έχουν 891 00:32:28,010 --> 00:32:28,950 πραγματικά έχει γίνει. 892 00:32:28,950 --> 00:32:30,750 >> Λοιπόν, ας προσπαθήσουμε μια από οι άλλοι είδαμε. 893 00:32:30,750 --> 00:32:37,116 Επιτρέψτε μου να κάντε κλικ στο είδος φούσκα εδώ, και επιτρέψτε μου να επιλέξει, και όλη αυτή η ιστοσελίδα 894 00:32:37,116 --> 00:32:38,936 είναι ένα μικρό αμαξάκι. 895 00:32:38,936 --> 00:32:41,155 Ας δεχτούμε τον κίνδυνο και να τρέξει ξανά. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Εκεί πάμε. 898 00:32:45,030 --> 00:32:47,180 Ας κάνουμε το είδος επιλογής. 899 00:32:47,180 --> 00:32:49,140 Δεν ξέρω γιατί το μενού εμφανίζεται εκεί. 900 00:32:49,140 --> 00:32:54,070 Ας zoom in για να καθορίσει ότι bug, το αλλάξετε σε 50. 901 00:32:54,070 --> 00:32:56,020 Αχ, ας κάνουν πραγματικά ότι πολύ πιο γρήγορα. 902 00:32:56,020 --> 00:32:59,160 Πέντε χιλιοστά του δευτερολέπτου ή έτσι, και να αρχίσει. 903 00:32:59,160 --> 00:33:00,470 >> Έτσι, αυτό είναι το είδος επιλογής. 904 00:33:00,470 --> 00:33:03,070 Έτσι και πάλι, σκεφτείτε τι μπορούμε έκανε με τους ανθρώπους εδώ. 905 00:33:03,070 --> 00:33:08,490 Πήγαμε με την σειρά και επιλέγονται το μικρότερο στοιχείο πάλι, 906 00:33:08,490 --> 00:33:09,250 και ξανά, και ξανά. 907 00:33:09,250 --> 00:33:11,110 Τώρα ισχυρίζονται ότι ήταν ακόμα αρκετά άσχημα. 908 00:33:11,110 --> 00:33:15,010 Ήταν ακόμα n τετράγωνο, ή να δώσει, αλλά ήταν, στον πραγματικό κόσμο, ένα κομμάτι 909 00:33:15,010 --> 00:33:18,280 γρηγορότερα, γιατί πράγματι, λαμβάνοντας ελαφρώς λιγότερα βήματα κάθε φορά. 910 00:33:18,280 --> 00:33:19,800 Αλλά μιλάμε μόνο ό, τι; 911 00:33:19,800 --> 00:33:21,830 Ίσως 40 ή έτσι μπαρ εδώ; 912 00:33:21,830 --> 00:33:23,200 Εμείς δεν μιλάμε 40 εκατ. ευρώ. 913 00:33:23,200 --> 00:33:27,430 Έτσι δεν είναι απόλυτα σαφές για μένα ότι Ήταν πράγματι ένα σημαντικό κέρδος. 914 00:33:27,430 --> 00:33:32,530 >> Επιτρέψτε μου τώρα να πάει πίσω και να αλλάξει σε μας τρίτη αλγόριθμος, που επιλέγει 915 00:33:32,530 --> 00:33:33,180 ταξινόμηση με εισαγωγή. 916 00:33:33,180 --> 00:33:36,380 Και τώρα είναι πραγματικά προβληματικό, διότι η menu πραγματικά δεν πρέπει να είναι εκεί κάτω. 917 00:33:36,380 --> 00:33:40,840 Έτσι τώρα θα μετακινηθείτε προς τα πίσω μέχρι εδώ και να αρχίσει αυτόν τον αλγόριθμο. 918 00:33:40,840 --> 00:33:43,270 Whoop, να αρχίσει και να σταματήσει. 919 00:33:43,270 --> 00:33:47,160 Έτσι, αυτό το είδος έχει ένα όμορφο σχέδιο σε αυτό, σύμφωνα με την οποία είμαστε και πάλι 920 00:33:47,160 --> 00:33:50,240 εισάγοντας τους ανθρώπους, ή Στην περίπτωση αυτή, τα μπαρ σε 921 00:33:50,240 --> 00:33:52,620 κατάλληλη θέση τους. 922 00:33:52,620 --> 00:33:55,430 Και αυτό έχει ήδη γίνει πριν Γύρισα γύρω. 923 00:33:55,430 --> 00:33:58,940 Αλλά αυτό, επίσης, στη θεωρία, εξακολουθεί ν τετράγωνο. 924 00:33:58,940 --> 00:34:01,430 >> Έτσι, ας δούμε αν δεν μπορούμε να συνοψίσουμε Αυτά ως εξής. 925 00:34:01,430 --> 00:34:04,750 Πάω να πάει μπροστά και μόνο για να δώσει μας ένα είδος συνηθισμένος τρόπος να μιλάμε 926 00:34:04,750 --> 00:34:08,489 για αυτά τα πράγματα, επιτρέψτε μου να εισαγάγει απλά ένα κομμάτι της σημειογραφίας εδώ. 927 00:34:08,489 --> 00:34:12,480 Είστε έτοιμοι να δείτε κάτι που ονομάζεται μεγάλο O, επειδή είναι κυριολεκτικά ένα μεγάλο 928 00:34:12,480 --> 00:34:16,320 Ο. Και αυτό είναι ένας τρόπος ότι ένας υπολογιστής επιστήμονας ή ένας μαθηματικός χρησιμοποιεί ακόμη και 929 00:34:16,320 --> 00:34:19,230 για να περιγράψει το χρόνο λειτουργίας κάποιου αλγορίθμου. 930 00:34:19,230 --> 00:34:21,400 Πόσα βήματα δεν είναι στην πραγματικότητα να λάβει; 931 00:34:21,400 --> 00:34:25,080 >> Τώρα είμαι πρόκειται να φέρουν σε δύσκολη θέση τον εαυτό μου με χειρόγραφό μου εδώ ακριβώς σε μια στιγμή. 932 00:34:25,080 --> 00:34:29,020 Αλλά επιτρέψτε μου να προχωρήσει και να πω ότι Αυτό θα είναι μεγάλη O εδώ. 933 00:34:29,020 --> 00:34:33,610 Και επιτρέψτε μου να εισαγάγει ένα άλλο σύμβολο, ένα ωμέγα κεφαλαίου. 934 00:34:33,610 --> 00:34:37,080 Omega πρόκειται να είναι το αντίθετο, κατ 'ουσίαν, των μεγάλων O. ότι η μεγάλη O 935 00:34:37,080 --> 00:34:40,790 μέσα, στη χειρότερη περίπτωση, πόσο χρόνο θα μπορούσε κάποια αλγόριθμος λαμβάνει, 936 00:34:40,790 --> 00:34:43,480 Όροι n, ωμέγα πρόκειται να είναι πόσο χρόνο θα μπορούσε να 937 00:34:43,480 --> 00:34:45,409 λάβει στην καλύτερη περίπτωση. 938 00:34:45,409 --> 00:34:48,090 Και θα δούμε τι εννοούμε με τον όρο καλύτερη περίπτωση σε μια στιγμή. 939 00:34:48,090 --> 00:34:49,940 >> Οπότε ας ξεκινήσουμε κάτι απλό. 940 00:34:49,940 --> 00:34:54,719 Επιτρέψτε μου να ξεκινήσω με μια γραμμική αναζήτηση. 941 00:34:54,719 --> 00:34:55,679 Έτσι, δεν διαλογή. 942 00:34:55,679 --> 00:34:58,000 Θα το ονομάσουμε γραμμική αναζήτηση. 943 00:34:58,000 --> 00:35:01,140 Και τώρα, κάνει μια μικρή πίνακας έξω από αυτό. 944 00:35:01,140 --> 00:35:06,600 Και τώρα, στην περίπτωση της γραμμικής αναζήτησης, στη χειρότερη περίπτωση, πόσα βήματα είναι 945 00:35:06,600 --> 00:35:11,770 αυτό θα μου πάρει για να βρεθεί μια αριθμό αυθαίρετων επιλογή; 946 00:35:11,770 --> 00:35:14,540 Και υπάρχει n συνολικό πόρτες ή n συνολικό αριθμό. 947 00:35:14,540 --> 00:35:15,940 Χειρότερη περίπτωση. 948 00:35:15,940 --> 00:35:18,800 Πόσα βήματα είμαι πρόκειται να πρέπει να λάβει για να βρείτε τον αριθμό 50 σε μια σειρά 949 00:35:18,800 --> 00:35:20,830 Ν πόρτες; 950 00:35:20,830 --> 00:35:21,410 Και γιατί; 951 00:35:21,410 --> 00:35:23,680 Επειδή θα μπορούσε να είναι όλη η τρόπο πάνω στην άκρη. 952 00:35:23,680 --> 00:35:27,120 Τόσο μεγάλο μέρος όπως η Jennifer συνάντησε, η αριθμός 50 ήταν σε όλη τη διαδρομή πάνω, έτσι ώστε το 953 00:35:27,120 --> 00:35:30,760 η χειρότερη περίπτωση γραμμική αναζήτηση είναι μεγάλη O Ν, εμείς θα πούμε. 954 00:35:30,760 --> 00:35:33,430 >> Τι γίνεται στην καλύτερη περίπτωση, αν έχετε πραγματικά τυχερός; 955 00:35:33,430 --> 00:35:36,200 Είναι ακριβώς πρόκειται να πάρει ένα βήμα, ή ένα σταθερό αριθμό βημάτων. 956 00:35:36,200 --> 00:35:37,830 Έτσι, θα σας περιγράψουμε ότι 1. 957 00:35:37,830 --> 00:35:39,010 Έτσι, αυτό είναι πολύ καλό. 958 00:35:39,010 --> 00:35:41,210 Τώρα, τι θα γινόταν αν κάναμε κάτι όπως δυαδική αναζήτηση; 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Έτσι, δυαδική αναζήτηση, στη χειρότερη περίπτωση, πήρε πόσο χρόνο; 961 00:35:47,846 --> 00:35:49,250 >> [Παρεμβάλλοντας VOICES] 962 00:35:49,250 --> 00:35:51,310 >> David J. MALAN: Έτσι, στην πραγματικότητα, I ακούσει σε χώρους ζευγάρι. 963 00:35:51,310 --> 00:35:56,390 Έτσι είναι στην πραγματικότητα συνδεθείτε n, ή να δώσει, γιατί όπως διαιρέσουμε τον κατάλογο στο μισό 964 00:35:56,390 --> 00:36:00,730 ξανά, και ξανά, και ξανά, είμαστε σε θέση να βρει, τελικά, η αξία, 965 00:36:00,730 --> 00:36:04,750 αν υπάρχει, αλλά υπάρχει μια παγίδα. 966 00:36:04,750 --> 00:36:08,590 Ποια είναι η υπόθεση ότι πρέπει να θεωρούμε δεδομένο για την δυαδική αναζήτηση; 967 00:36:08,590 --> 00:36:09,700 Θα πρέπει να διευθετηθεί. 968 00:36:09,700 --> 00:36:12,770 Δεν είναι ταξινομημένο, μπορείτε να χωρίσετε το πράγμα κατά το ήμισυ ξανά και ξανά, και θα 969 00:36:12,770 --> 00:36:15,490 μπορεί να πάει αριστερά, και μπορείτε να πάτε δεξιά, και μπορείτε να πάτε αριστερά και δεξιά, αλλά είστε 970 00:36:15,490 --> 00:36:18,070 δεν πρόκειται να βρούμε το στοιχείο, εάν Ο κατάλογος δεν είναι ταξινομημένη, γιατί 971 00:36:18,070 --> 00:36:18,790 μπορείτε να το χάσετε. 972 00:36:18,790 --> 00:36:22,120 Επειδή η ευρετική σας, για να πάει αριστερά ή δικαίωμα δεν πρόκειται να αποτύχουν αν είναι 973 00:36:22,120 --> 00:36:23,420 όντως δεν ταξινομούνται. 974 00:36:23,420 --> 00:36:26,110 Έτσι υπάρχει ένα είδος κρυφό κόστος για τη χρήση κάτι σαν αυτό. 975 00:36:26,110 --> 00:36:29,250 >> Τώρα, ας πάμε στην διαλογή μας αλγόριθμοι που δεν ψάχνουν - 976 00:36:29,250 --> 00:36:31,140 Ω, πραγματικά ας πάμε σε αυτό το κενό. 977 00:36:31,140 --> 00:36:33,190 Δυαδική αναζήτηση στην καλύτερη περίπτωση; 978 00:36:33,190 --> 00:36:36,290 Είναι επίσης 1, αν συμβαίνει να είναι ακριβώς στο πολύ μέση της συστοιχίας, ή 979 00:36:36,290 --> 00:36:37,810 η μέση του τηλεφωνικού καταλόγου. 980 00:36:37,810 --> 00:36:39,710 Τώρα ας κάνουμε το είδος φούσκα. 981 00:36:39,710 --> 00:36:42,570 Έτσι και πάλι, τώρα είμαστε εισέρχονται στο ταξινομεί όχι, οι έρευνες. 982 00:36:42,570 --> 00:36:47,220 >> Στη χειρότερη περίπτωση, πόσα βήματα κάναμε αξίωση είδος φούσκα πρόκειται να πάρει; 983 00:36:47,220 --> 00:36:48,410 n τετράγωνο. 984 00:36:48,410 --> 00:36:49,200 Έτσι, Πάω να επιστήσω αυτό. 985 00:36:49,200 --> 00:36:51,710 Ooh, χειρόγραφό μου φαίνεται ακόμα χειρότερα όταν είναι προβλέπεται ότι οι μεγάλες. 986 00:36:51,710 --> 00:36:52,510 Εντάξει. 987 00:36:52,510 --> 00:36:53,570 Έτσι ώστε να είναι n τετράγωνο. 988 00:36:53,570 --> 00:36:59,460 Και στην καλύτερη περίπτωση της ταξινόμησης φυσαλίδας, πόσα βήματα είναι αυτό πρόκειται να πάρει; 989 00:36:59,460 --> 00:37:00,980 1, άκουσα. 990 00:37:00,980 --> 00:37:01,760 >> ΟΜΙΛΗΤΗΣ 1: n. 991 00:37:01,760 --> 00:37:03,286 >> David J. MALAN: n, άκουσα. 992 00:37:03,286 --> 00:37:04,200 >> ΟΜΙΛΗΤΗΣ 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> David J. MALAN: 2, άκουσα. 994 00:37:05,010 --> 00:37:06,670 Ακούω 3; 995 00:37:06,670 --> 00:37:07,080 Εντάξει. 996 00:37:07,080 --> 00:37:11,390 Έτσι, έχω ακούσει 1, n, 2, αλλά ας πάρει Εκτός τουλάχιστον η πρώτη από αυτές 997 00:37:11,390 --> 00:37:12,330 προτάσεις, 1. 998 00:37:12,330 --> 00:37:15,370 Δεν είναι μια κακή ένστικτο, γιατί είδος ακολουθεί ένα πρότυπο εδώ. 999 00:37:15,370 --> 00:37:19,670 Αλλά αν παίρνει μόνο 1 βήμα, πώς η κόσμο θα μπορούσα να ισχυριστεί ότι ο κατάλογος 1000 00:37:19,670 --> 00:37:22,900 είναι ταξινομημένο, γιατί αν είμαι μόνο επιτρέπεται να λάβει 1 βήμα, πόσα στοιχεία 1001 00:37:22,900 --> 00:37:25,230 θα ήθελα πραγματικά να ελέγξετε για να βεβαιωθείτε; 1002 00:37:25,230 --> 00:37:28,270 Λοιπόν, μόλις 1, το οποίο σημαίνει ότι υπάρχει n μείον 1 στοιχεία που θα μπορούσαν να είναι έξω από 1003 00:37:28,270 --> 00:37:31,310 τάξη, και είμαι απλώς πρόκειται για την πίστη μετά κοιτάζοντας 1 στοιχείο ότι η 1004 00:37:31,310 --> 00:37:31,850 πράγμα που είναι ταξινομημένο. 1005 00:37:31,850 --> 00:37:33,930 Έτσι, 1 δεν είναι σωστό εδώ. 1006 00:37:33,930 --> 00:37:35,710 Έτσι, ελάχιστα, πόσες έχω να δούμε; 1007 00:37:35,710 --> 00:37:36,680 >> [Παρεμβάλλοντας VOICES] 1008 00:37:36,680 --> 00:37:40,160 >> David J. MALAN: n μείον 1, ή πραγματικά, n, γιατί πρέπει να εξετάσουμε κάθε 1009 00:37:40,160 --> 00:37:42,190 στοιχείο που πρέπει να βεβαιωθείτε ότι δεν είναι εκτός λειτουργίας. 1010 00:37:42,190 --> 00:37:44,750 Αλλά και πάλι, θα ταξινομήσετε του κύματος μας τα χέρια στους μικρούς αριθμούς και 1011 00:37:44,750 --> 00:37:47,100 υποθέσουμε ότι, καθώς το n παίρνει μεγάλες, είναι πληκτικός ούτως ή άλλως. 1012 00:37:47,100 --> 00:37:48,380 Έτσι, αυτό είναι το είδος φούσκα. 1013 00:37:48,380 --> 00:37:49,830 Και τώρα, ας κάνουμε αυτά τα δύο τελευταία. 1014 00:37:49,830 --> 00:37:53,520 Ταξινόμηση Selection, και στη συνέχεια θα κάνει ταξινόμηση με εισαγωγή. 1015 00:37:53,520 --> 00:37:57,160 Και τότε θα φυσήξει σας μυαλά με κάτι πολύ 1016 00:37:57,160 --> 00:37:58,926 καλύτερα από όλα αυτά. 1017 00:37:58,926 --> 00:38:00,410 Εντάξει. 1018 00:38:00,410 --> 00:38:04,700 >> Ποια είναι η χειρότερη περίπτωση λειτουργίας χρόνο της επιλογής του είδους; 1019 00:38:04,700 --> 00:38:05,680 >> ΟΜΙΛΗΤΗΣ 4: n τετράγωνο. 1020 00:38:05,680 --> 00:38:06,710 >> David J. MALAN: n πλατεία, ακούω. 1021 00:38:06,710 --> 00:38:09,790 Αλλά γιατί n τετράγωνο, διαισθητικά; 1022 00:38:09,790 --> 00:38:11,170 >> ΟΜΙΛΗΤΗΣ 4: Γιατί το κάναμε αυτό ακριβώς. 1023 00:38:11,170 --> 00:38:12,260 >> David J. MALAN: Επειδή κάναμε αυτό ακριβώς. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Καλή απάντηση. 1026 00:38:13,380 --> 00:38:16,660 Αλλά διαισθητικά, γιατί είναι επιλογή Ταξινόμηση n τετράγωνο; 1027 00:38:16,660 --> 00:38:18,980 Τι πρέπει να κάνουμε ξανά και ξανά; 1028 00:38:18,980 --> 00:38:22,570 Έπρεπε να κρατήσει σάρωση μέσω, είναι Σας το μικρότερο, είσαι η 1029 00:38:22,570 --> 00:38:24,020 μικρότερο, είσαι το μικρότερο. 1030 00:38:24,020 --> 00:38:27,480 Και χορηγηθεί, ήμασταν σε θέση να λάβει n βήματα, τότε ν μείον 1, τότε το η μείον 2. 1031 00:38:27,480 --> 00:38:30,700 Αλλά αν το είδος του προσθέτει τα όλα επάνω, ή πάρτε την πίστη ότι έχω προσθέσει 1032 00:38:30,700 --> 00:38:34,810 τους εκ των προτέρων, έχουμε περίπου n τετράγωνο μείον ορισμένες μικρότερους αριθμούς. 1033 00:38:34,810 --> 00:38:36,730 Έτσι, Πάω να καλέσετε αυτό n τετράγωνο. 1034 00:38:36,730 --> 00:38:39,530 Αλλά με το είδος επιλογής με τον καλύτερο περίπτωση, πόσα βήματα είναι 1035 00:38:39,530 --> 00:38:40,632 πρόκειται να με πάρει; 1036 00:38:40,632 --> 00:38:41,840 >> ΟΜΙΛΗΤΗΣ 5: [δεν ακούγεται] 1037 00:38:41,840 --> 00:38:44,350 >> David J. MALAN: Είναι, δυστυχώς, εξακολουθεί ν τετράγωνο, έτσι δεν είναι; 1038 00:38:44,350 --> 00:38:49,590 Γιατί αν είμαι επιλέγοντας το μικρότερο στοιχείο, και είχαμε επτά άτομα εδώ, 1039 00:38:49,590 --> 00:38:53,280 Το μόνο που ξέρω, όταν θα φτάσουμε στην τέλος, ότι έχω βρει το μικρότερο 1040 00:38:53,280 --> 00:38:55,670 αριθμό, όπου και αυτή μπορεί να έχει. 1041 00:38:55,670 --> 00:38:58,820 Αλλά πώς μπορώ να βρω το επόμενο μικρότερος αριθμός; 1042 00:38:58,820 --> 00:39:00,160 Έχω να κάνω ένα άλλο πέρασμα. 1043 00:39:00,160 --> 00:39:04,810 Έτσι, στην καλύτερη περίπτωση, ποια είναι η εισόδου για να ταξινομήσετε επιλογή; 1044 00:39:04,810 --> 00:39:07,830 Είναι μια ήδη λίστα ταξινόμησης, νούμερο ένα, νούμερο δύο, νούμερο τρία, το νούμερο τέσσερα. 1045 00:39:07,830 --> 00:39:08,600 Αλλά είμαι ένας υπολογιστής. 1046 00:39:08,600 --> 00:39:10,190 Μπορώ μόνο να δούμε ένα πράγμα κάθε φορά. 1047 00:39:10,190 --> 00:39:12,465 Δεν μπορώ να ταξινομήσετε του κάνουμε ένα βήμα πίσω σαν ένα ανθρώπινο και να πω, 1048 00:39:12,465 --> 00:39:14,030 ooh, αυτό φαίνεται σωστό. 1049 00:39:14,030 --> 00:39:17,580 >> Μπορώ να αποφανθεί μόνο ορθότητα Ταξινόμηση επιλογή με την επιλογή του 1050 00:39:17,580 --> 00:39:18,370 μικρότερο αριθμό. 1051 00:39:18,370 --> 00:39:21,390 Αλλά ακόμα και αν βρω νούμερο ένα πρώτο, αν δεν ξέρω τίποτα άλλο γι ' 1052 00:39:21,390 --> 00:39:24,460 οι άλλοι αριθμοί, που εγώ δεν το κάνετε, το μόνο που μπορώ Γνωρίζω ότι έχω παραδοθεί μια σειρά 1053 00:39:24,460 --> 00:39:27,930 ή μια σειρά από πόρτες πίσω από τις οποίες είναι αριθμούς, ο μόνος τρόπος που ξέρω ότι ένα 1054 00:39:27,930 --> 00:39:28,680 ήταν η μικρότερη; 1055 00:39:28,680 --> 00:39:32,440 Αν πάρω όλη τη διαδρομή εδώ και να συνειδητοποιήσουν, βλασφημία, ένα ήταν πράγματι η μικρότερη. 1056 00:39:32,440 --> 00:39:34,870 >> Αλλά πώς μπορώ να διαπιστώσω στη συνέχεια ότι δύο είναι το επόμενο μικρότερο; 1057 00:39:34,870 --> 00:39:38,350 Με τον τρόπο την ίδια αναποτελεσματικότητα ξανά και ξανά. 1058 00:39:38,350 --> 00:39:42,210 Έτσι, τελικά, με την ταξινόμηση με εισαγωγή, πώς, στη χειρότερη περίπτωση, 1059 00:39:42,210 --> 00:39:44,990 δεν λέμε ότι εκτελεί; 1060 00:39:44,990 --> 00:39:49,100 Είναι πάρα πολύ είναι n τετράγωνο. 1061 00:39:49,100 --> 00:39:53,020 Και τι γίνεται με την καλύτερη περίπτωση; 1062 00:39:53,020 --> 00:39:56,282 Θα το αφήσουμε ως δραματική στιγμή. 1063 00:39:56,282 --> 00:40:00,090 Θα συμπληρώσει το κενό επόμενη φορά, αλλά πρώτα επιτρέψτε μου να προτείνω να 1064 00:40:00,090 --> 00:40:02,620 ουσιαστικά κάνει καλύτερα από ό, τι όλα αυτά, εντάξει; 1065 00:40:02,620 --> 00:40:05,220 >> Έτσι σκεφτείτε για τον εαυτό σας τι εισαγωγή Ταξινόμηση πρόκειται να είναι. 1066 00:40:05,220 --> 00:40:06,910 Λοιπόν, αυτό δεν ήταν πολύ δραματική, γιατί είμαι ο μόνος 1067 00:40:06,910 --> 00:40:08,970 που είδε την αλλαγή. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Έτσι, εδώ έχουμε μια κάπως διαφορετική επίδειξη. 1071 00:40:12,615 --> 00:40:16,580 Αν μου κάνετε ζουμ σε εδώ, θα δείτε ότι σε η αριστερά έχουμε το είδος φούσκα, στην 1072 00:40:16,580 --> 00:40:20,740 μεσαία έχουμε είδος επιλογής, και η άκρα δεξιά, έχουμε κάτι που 1073 00:40:20,740 --> 00:40:23,380 δεν έχουν εξεταστεί ακόμα ονομάζεται συγχώνευση είδους. 1074 00:40:23,380 --> 00:40:26,080 Αλλά σκεφτείτε τι έχουμε πάει κάνουμε εδώ μέχρι στιγμής σήμερα. 1075 00:40:26,080 --> 00:40:29,200 Όταν η Jennifer για πρώτη φορά στη σκηνή, περάσαμε από τη συστοιχία των αριθμών 1076 00:40:29,200 --> 00:40:33,750 ξανά και ξανά, με γραμμική αναζήτηση, και πήραμε γραμμικό χρόνο λειτουργίας, big O 1077 00:40:33,750 --> 00:40:35,100 ν, να το πω έτσι. 1078 00:40:35,100 --> 00:40:41,000 >> Όταν εξετάζουμε τώρα την πρώτη εβδομάδα του τάξη, όταν είχαμε διαίρει και βασίλευε, 1079 00:40:41,000 --> 00:40:43,740 και είχαμε το τηλεφωνικό δακρύρροια, και η Jennifer, και εμείς συλλογικά 1080 00:40:43,740 --> 00:40:47,500 μόχλευση ότι η βασική αντίληψη, η οποία επρόκειτο να επαναλάβετε στον εαυτό σας ξανά και ξανά από 1081 00:40:47,500 --> 00:40:50,930 κατά κάποιο τρόπο πετάμε, πετάμε, πετάμε, το ήμισυ του προβλήματος, ή 1082 00:40:50,930 --> 00:40:55,320 Γενικότερα, διαιρώντας ένα πρόβλημα στο μισό, και κατεργασία στη συνέχεια το μικρότερο κομμάτι 1083 00:40:55,320 --> 00:40:59,630 το πρόβλημα εννοιολογικά ισοδύναμο στην άλλη, κατά κάποιο τρόπο στην 1084 00:40:59,630 --> 00:41:00,910 θεμελιωδώς καλύτερα. 1085 00:41:00,910 --> 00:41:04,720 Αλλά με το είδος φούσκα, με την επιλογή ταξινόμησης, με το είδος εισαγωγής, έχουμε μπορεί να 1086 00:41:04,720 --> 00:41:06,560 δεν υπάρχουν τέτοιες ιδέες ότι η Jennifer έκανε. 1087 00:41:06,560 --> 00:41:10,220 Είμαστε λίγο πολύ απλά περπάτησε πίσω και πίσω ένα σωρό φορές, και 1088 00:41:10,220 --> 00:41:12,650 πειραγμένο πράγματα λίγο, ανταλλάσσοντας με αυτή τη σειρά, ίσως 1089 00:41:12,650 --> 00:41:13,730 εισαγωγή ή την επιλογή. 1090 00:41:13,730 --> 00:41:16,950 Αλλά στο τέλος της ημέρας, έκανα πολλά αδέξια πόδια εμπρός και πίσω. 1091 00:41:16,950 --> 00:41:21,160 Εμείς δεν το κάναμε πραγματικά κάτι μόχλευσης έξυπνος όπως η Jennifer άρεσε διαίρεση 1092 00:41:21,160 --> 00:41:22,040 και την κατάκτηση. 1093 00:41:22,040 --> 00:41:25,620 >> Έτσι συγχώνευση του είδους, αντιθέτως, το οποίο Δεν θα δούμε μέχρι την επόμενη εβδομάδα, πρόκειται 1094 00:41:25,620 --> 00:41:29,540 για τη μόχλευση ότι βασική ιδέα διαιρώντας η είσοδος, και στη συνέχεια μείωση κατά το ήμισυ, και στη συνέχεια 1095 00:41:29,540 --> 00:41:30,580 μείωση κατά το ήμισυ, και στη συνέχεια μείωση κατά το ήμισυ. 1096 00:41:30,580 --> 00:41:34,590 Και για κάθε επανάληψη του εν λόγω βρόχου, διαλογή το αριστερό μισό, και το δικαίωμα 1097 00:41:34,590 --> 00:41:38,200 μισό, τότε το αριστερό μισό του αριστερό μισό, και το δεξί μισό της αριστεράς, στη συνέχεια, 1098 00:41:38,200 --> 00:41:40,990 το αριστερό μισό του δεξί μισό, και το δεξί μισό στο δεξί ήμισυ. 1099 00:41:40,990 --> 00:41:42,840 Και επαναλαμβάνοντας ξανά και ξανά. 1100 00:41:42,840 --> 00:41:46,170 >> Έτσι, θα δείτε αυτό οπτικά, αλλά αυτό είναι αυτό που μας περιμένει την επόμενη εβδομάδα. 1101 00:41:46,170 --> 00:41:49,760 Και σε γενικές γραμμές, όταν σκεφτόμαστε λίγο λίγο πιο δύσκολο για οποιοδήποτε τέτοιο πρόβλημα. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Έχουμε n τετράγωνο στα αριστερά, n τετράγωνο στη μέση, και Ν 1104 00:41:57,970 --> 00:41:59,400 log n στα δεξιά. 1105 00:41:59,400 --> 00:42:00,590 Έτσι, υπάρχει πραγματικά δραματική στιγμή σας. 1106 00:42:00,590 --> 00:42:02,040 Θα τα πούμε τη Δευτέρα. 1107 00:42:02,040 --> 00:42:05,163 >> [Χειροκρότημα]