1 00:00:00,000 --> 00:00:11,100 >> [Musik spielt] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Alles klar. 3 00:00:11,490 --> 00:00:12,170 Also zurück zu begrüßen. 4 00:00:12,170 --> 00:00:15,180 Dies ist CS50 und das ist das Ende der dritten Woche. 5 00:00:15,180 --> 00:00:17,770 >> So in den vergangenen Wochen erinnern, wir haben die Ausgaben ziemlich viel 6 00:00:17,770 --> 00:00:20,820 Zeit auf C, über die Programmierung, auf Syntax. 7 00:00:20,820 --> 00:00:24,680 Und es ist ganz normal, wenn Sie immer noch kämpfen mit Problem Set 2 zu sein 8 00:00:24,680 --> 00:00:25,950 Mit dem Kopf gegen die Wand. 9 00:00:25,950 --> 00:00:28,310 Es ist kryptisch aussehende Fehlermeldungen und Fehler, die Sie 10 00:00:28,310 --> 00:00:29,220 kann nicht ganz jagen. 11 00:00:29,220 --> 00:00:32,310 Denn, seien Sie versichert, dass in nur einem wenigen Wochen werden Sie blicken zurück auf 12 00:00:32,310 --> 00:00:35,930 Dinge wie Caesar, und [? V-Genair,?] vielleicht sogar Knacken und 13 00:00:35,930 --> 00:00:40,050 erkennen, wie weit Sie gekommen sind in einem kurzen Zeitraum. 14 00:00:40,050 --> 00:00:43,670 Also, wenn das ein Trost ist, hängen dort jetzt. 15 00:00:43,670 --> 00:00:46,610 >> Heute jedoch, beginnen wir, den Übergang Dinge zu höheren Niveau. 16 00:00:46,610 --> 00:00:49,820 Und wir beginnen, für selbstverständlich halten, dass Sie Jungs wissen, wie man programmiert, oder 17 00:00:49,820 --> 00:00:52,090 zumindest die Anfänge dass Komfort. 18 00:00:52,090 --> 00:00:56,520 Und wir beginnen zu überlegen, wie wir gehen über die Gestaltung von Programmen mehr 19 00:00:56,520 --> 00:00:57,440 effektiv. 20 00:00:57,440 --> 00:01:01,090 Wie können wir über die Optimierung unterwegs Effizienz unserer Algorithmen und 21 00:01:01,090 --> 00:01:03,110 Regel Lösung mehr interessante Probleme. 22 00:01:03,110 --> 00:01:06,850 Und ab zu nehmen für selbstverständlich, dass, wenn wir wollten, könnten wir codieren bis jede 23 00:01:06,850 --> 00:01:08,350 der Beispiele, die wir im Auge haben. 24 00:01:08,350 --> 00:01:11,430 Also heute haben wir nicht die Tastatur berühren für jede Form von Code. 25 00:01:11,430 --> 00:01:15,150 Es wird viel höheren Niveau zu sein, und letztlich über Problemlösung. 26 00:01:15,150 --> 00:01:20,490 >> Also, um zu diesem Punkt zu gelangen, lassen Sie mich schlagen daß die folgenden sieben 27 00:01:20,490 --> 00:01:24,290 Rechtecke stellen sieben Türen, hinter das sind eine ganze Reihe von 28 00:01:24,290 --> 00:01:26,340 Zahlen, von denen ist die Nummer 50. 29 00:01:26,340 --> 00:01:30,470 Lassen Sie mich zu projizieren diese auf diese Bildschirm auch hier. 30 00:01:30,470 --> 00:01:36,770 Und schlagen vor, dass wir einen Freiwilligen brauchen helfen, mir eine Zahl vor 31 00:01:36,770 --> 00:01:38,140 das Internet hier zu sehen. 32 00:01:38,140 --> 00:01:40,755 Komm up, in dem rosa. 33 00:01:40,755 --> 00:01:43,050 In Ordnung. 34 00:01:43,050 --> 00:01:43,930 Wie ist dein Name? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [unverständlich] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Wie bitte? 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 Alles klar, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Schön, Sie kennen zu lernen. 41 00:01:47,630 --> 00:01:48,370 Komm up. 42 00:01:48,370 --> 00:01:52,430 Also diese hier sind sieben Türen, und was Ich möchte, dass du für uns hier zu tun, 43 00:01:52,430 --> 00:01:56,560 vor alle Ihre Klassenkameraden, wird uns finden Sie die Nummer 50. 44 00:01:56,560 --> 00:02:00,860 Um eine Zahl zu finden, können Sie einen Blick hinter jeder dieser Türen durch einfaches Antippen 45 00:02:00,860 --> 00:02:03,030 auf eine der Türen, und wird ihre Zahl zu offenbaren. 46 00:02:03,030 --> 00:02:06,080 Und lassen Sie uns sehen, wie schnell Sie So finden Sie uns die Anzahl, 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 Schön gemacht. 54 00:02:17,350 --> 00:02:18,040 In Ordnung. 55 00:02:18,040 --> 00:02:19,906 Applaus für Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applaus] 57 00:02:21,530 --> 00:02:22,320 >> In Ordnung. 58 00:02:22,320 --> 00:02:25,254 Also, was war Ihre Strategie für Finden Sie die Nummer 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Äh, ich dachte, vielleicht, wenn - 60 00:02:27,222 --> 00:02:27,714 [Unverständlich] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Geben Sie ihm eine Sekunde. 63 00:02:29,630 --> 00:02:32,420 So war Ihre Strategie für Finden Sie die Nummer 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Also ich erst am Anfang beginnen, um zu sehen, was die erste Zahl 65 00:02:34,760 --> 00:02:38,590 war, und dann dachte ich, vielleicht, wenn sie sortiert sind, werde ich einfach weiter 66 00:02:38,590 --> 00:02:39,970 Klopfen höher? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 Und wir scheinen gefunden zu haben dass der Fall zu sein. 69 00:02:42,910 --> 00:02:45,670 Obwohl wir schälen die Schichten nur ein wenig, und Sie gehen wollen 70 00:02:45,670 --> 00:02:47,640 vor und zeigen die anderen Türen könnten Sie gewählt haben? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, mein Lieber. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Also ich einfach nur Glück. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: So haben Sie Glück. 76 00:02:55,270 --> 00:02:55,710 In Ordnung. 77 00:02:55,710 --> 00:02:56,795 Also nicht schlecht. 78 00:02:56,795 --> 00:02:58,750 Aber das ist eine interessante Einsicht, nicht wahr? 79 00:02:58,750 --> 00:03:01,870 Wenn Sie angenommen, und du hast bekommen, in der Tat, ein bisschen Glück gibt. 80 00:03:01,870 --> 00:03:05,350 Aber wenn man davon ausgegangen, dass die Zahlen waren sortiert, können Sie genauere 81 00:03:05,350 --> 00:03:08,750 , wie beeinflusst, dass Ihr Verhalten? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Also, wenn sie sortiert wurden, habe ich dachte, vielleicht kleinsten bis zum größten. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Oder wenn dies endete als wirklich groß, dann größten bis zum kleinsten. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 So der größten zur kleinsten, oder kleinsten zum größten. 87 00:03:18,170 --> 00:03:21,990 Aber lassen Sie mich schlagen, nehme an, Sie hatten Pech bekommen, und nehme an, dass sie 88 00:03:21,990 --> 00:03:26,840 wurden in der Tat nicht, sortiert, wie viele diese Türen können Sie mussten peek 89 00:03:26,840 --> 00:03:28,590 hinter in diesem schlimmsten Fall? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Alle von ihnen. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Alle von ihnen. 92 00:03:30,420 --> 00:03:31,740 Also lasst verallgemeinern, dass n. 93 00:03:31,740 --> 00:03:34,790 Es geschieht bis 7 sein, aber wir mehr im Allgemeinen sagen, es gibt n die Türen auf 94 00:03:34,790 --> 00:03:35,650 Bildschirm hier. 95 00:03:35,650 --> 00:03:40,110 Also im schlimmsten Fall, müsste man 7, hinter Türen oder n Türen schauen. 96 00:03:40,110 --> 00:03:44,140 Und so ist wirklich, es ist ein bisschen von Glück heute, aber es ist wirklich eine lineare 97 00:03:44,140 --> 00:03:46,440 Algorithmus der Art, obwohl Sie waren irgendwie übersprungen herum. 98 00:03:46,440 --> 00:03:47,080 Ist das fair? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ja. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Nun, lassen Sie mich sehen, ob Ihr Strategie ändert sich, wenn ich uns zu bewegen 101 00:03:50,000 --> 00:03:52,190 Unser zweites Beispiel hier mit 7 verschiedene Türen. 102 00:03:52,190 --> 00:03:55,240 Gleiche Zahlen, aber diese Zeit, die sie sortiert werden. 103 00:03:55,240 --> 00:03:58,350 Was ist Ihre Strategie hier sein wird, versuchen, legte aus dem Kopf, was 104 00:03:58,350 --> 00:03:59,310 die anderen Zahlen waren - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - früher? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Beginnen wir mit dem ersten. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Alles klar. 109 00:04:03,540 --> 00:04:05,190 Beginnen Sie mit dem ersten. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Jetzt, wo du gehen, und warum? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 ist wirklich klein. 113 00:04:10,040 --> 00:04:12,500 Also, wenn sie sind vielleicht kleinste Art bis zum größten, sollte es 114 00:04:12,500 --> 00:04:13,290 doppelt so groß, und -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Mal sehen, was Sie denken? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Probieren Sie die letzte. 118 00:04:19,050 --> 00:04:19,500 Nizza. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Sehr schön gemacht. 120 00:04:20,880 --> 00:04:21,860 In Ordnung. 121 00:04:21,860 --> 00:04:23,010 >> [Applaus] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Sie sind also tatsächlich tun dies schrecklich, weil man 124 00:04:26,790 --> 00:04:27,700 tut es sehr gut. 125 00:04:27,700 --> 00:04:31,150 Was uns nicht machen bestimmte Punkte. 126 00:04:31,150 --> 00:04:32,565 So wollen wir versuchen, ein Rollback hier. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Sehr gut getan, dennoch. 129 00:04:35,980 --> 00:04:39,060 So begann am Anfang, Sie sah, dass es 4 war, dann 130 00:04:39,060 --> 00:04:40,240 bewegt bis zum Ende. 131 00:04:40,240 --> 00:04:42,320 Aber nehmen Sie nicht das Glück dort, und nehme 50 132 00:04:42,320 --> 00:04:42,890 war woanders. 133 00:04:42,890 --> 00:04:46,190 Was Ihre dritte Schritt gewesen sein? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Zurück an den Anfang. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Zurück an den Anfang. 136 00:04:48,320 --> 00:04:51,320 OK, so würden Sie berührt haben diese Tür, die 8 war. 137 00:04:51,320 --> 00:04:51,660 In Ordnung. 138 00:04:51,660 --> 00:04:52,650 Also das ist nicht 50. 139 00:04:52,650 --> 00:04:55,380 Wo würden Sie schaute nächste sein? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Wenn ich nicht wissen, dass sie sortiert. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Richtig. 142 00:04:57,005 --> 00:04:58,490 Nun, wenn Sie wissen, hat wurden sie sortiert - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, wusste, ja. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - aber du hast nicht wissen, wo 50 war noch? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Just keep going. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Alles klar. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Keep going. 149 00:05:03,800 --> 00:05:05,270 OK, dass ich arbeiten kann. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Nun, wenn Sie nur gehen, um weiterzumachen, was ist Ihre 152 00:05:07,210 --> 00:05:09,680 Algorithmus Dezentralisierung in gesichert. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Das linear -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: Es ist eine Art linear. 155 00:05:11,820 --> 00:05:13,480 Aber lassen Sie mich schlagen, lassen mich setzen auf der Stelle. 156 00:05:13,480 --> 00:05:14,900 Lassen Sie mich die Seite aktualisieren. 157 00:05:14,900 --> 00:05:17,120 gleiche Anzahl, gleiche Anordnung, gleichen Türen. 158 00:05:17,120 --> 00:05:21,350 Aber denken Sie zurück an diesem ersten Tag in Klasse, wenn wir ein Telefonbuch zerriss in 159 00:05:21,350 --> 00:05:25,480 halb, irgendwie, und was war unsere Strategie gibt? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Beginnen Sie an der Mitte. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 So in der Mitte starten. 163 00:05:27,610 --> 00:05:28,790 Also lassen Sie uns fortfahren und zu simulieren, dass. 164 00:05:28,790 --> 00:05:30,720 Beginnen Sie an der Mitte durch enthüllt die Tür. 165 00:05:30,720 --> 00:05:31,660 So stieg die Zahl 16. 166 00:05:31,660 --> 00:05:35,290 So was wäre der starke Mann getan haben, die rissen das Telefonbuch in der Hälfte, 167 00:05:35,290 --> 00:05:38,450 , um zur nächsten Vermutung bekommen? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Gehe hin in dieser Hälfte. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: Und warum auf der rechten Seite? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Wenn sie eine Art kleinsten bis zum größten, dann 50 sein sollte 171 00:05:43,900 --> 00:05:44,720 an diesem Ende. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Good. 173 00:05:44,920 --> 00:05:45,390 Völlig vernünftig. 174 00:05:45,390 --> 00:05:48,380 So wie ein Telefonbuch, das Sie gehen rechts nach links entgegengesetzt, aber hier 175 00:05:48,380 --> 00:05:49,500 ist der Schlüssel zum Mitnehmen. 176 00:05:49,500 --> 00:05:53,930 Sie können jetzt wegwerfen, oder abreißen, Hälfte dieses Problem, so dass Sie nicht 177 00:05:53,930 --> 00:05:55,970 mit 7 Türen, aber wirklich mit nur 3. 178 00:05:55,970 --> 00:05:57,870 Welches ist etwa die Hälfte der Größe des Problems. 179 00:05:57,870 --> 00:05:58,350 In Ordnung. 180 00:05:58,350 --> 00:06:01,890 So, jetzt das, was man haben getan, nachdem Sie rechts gehen? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: So 16 ist immer noch ziemlich klein, bezogen auf 50, vielleicht werde ich versuchen, 182 00:06:05,870 --> 00:06:06,700 wie, dieser. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Alles klar. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Alles klar, also jetzt, was ist Ihre Instinkt sage? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Ich kann wegwerfen dies und dann einfach - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Gut, können Sie wegwerfen die linke Hälfte da. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - Pick this one. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: Und das Recht. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ja. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Also auch wenn es schwer um vielleicht zu sehen, wenn es nur 193 00:06:17,820 --> 00:06:21,320 7 Türen, darüber nachzudenken, jetzt, Die Konsistenz des 194 00:06:21,320 --> 00:06:22,620 Algorithmus, den Sie gerade angelegt. 195 00:06:22,620 --> 00:06:24,510 In dem vorherigen Fall, haben Sie Glück, das war toll. 196 00:06:24,510 --> 00:06:26,540 Aber du hast mit einem heuristischen, Würde ich sagen. 197 00:06:26,540 --> 00:06:29,150 Sie verwendeten Art von Ihren Instinkten und es zu wissen, sortiert, wenn sie hübsch ist 198 00:06:29,150 --> 00:06:31,600 am Anfang klein, natürlich, wir haben musst mehr nach rechts gehen. 199 00:06:31,600 --> 00:06:34,990 Aber in einem gewissen Sinne, du hast Glück, weil vielleicht war die Zahl 100, 200 00:06:34,990 --> 00:06:36,220 und vielleicht 50 war mehr in der Mitte. 201 00:06:36,220 --> 00:06:37,910 Vielleicht 50 war sogar hier. 202 00:06:37,910 --> 00:06:40,960 >> Aber was du getan hast ein wenig anders dieses Mal war, hast du die gleiche Sache 203 00:06:40,960 --> 00:06:42,150 wieder und wieder. 204 00:06:42,150 --> 00:06:45,310 Und ich würde behaupten, dass das, was Sie gerade hat, wenn auch durch das Telefon beeinflusst 205 00:06:45,310 --> 00:06:48,100 Buch ist beispielsweise etwas viel mehr algorithmischen und viel 206 00:06:48,100 --> 00:06:49,930 weniger spezielle verkleidet. 207 00:06:49,930 --> 00:06:51,620 Viel weniger instinktiv. 208 00:06:51,620 --> 00:06:57,160 Also am Ende des Tages, wie würde Sie beschreiben die Effizienz der 209 00:06:57,160 --> 00:07:00,530 ersten Algorithmus, wo Sie ging von links nach rechts, gegen die 210 00:07:00,530 --> 00:07:03,430 zweite Algorithmus hier? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Das sollte man, wie, vielleicht Halbierung der Zeit, oder sogar noch mehr, ja. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, vielleicht sogar mehr. 213 00:07:07,320 --> 00:07:10,150 Lassen Sie schieben ein wenig härter auf die. 214 00:07:10,150 --> 00:07:13,030 Was wirklich, wenn wir dies auch weiterhin Logik, wir definitiv halbiert die 215 00:07:13,030 --> 00:07:15,830 Laufzeit mit diesem zweiten Algorithmus durch Wegwerfen Hälfte der 216 00:07:15,830 --> 00:07:18,470 Zahlen, aber was wir tun, auf der nächsten Iteration, wenn Jennifer enthüllt 217 00:07:18,470 --> 00:07:20,615 die zweite Zahl? 218 00:07:20,615 --> 00:07:22,830 >> Wir halbieren die Zahl der Türen wieder. 219 00:07:22,830 --> 00:07:25,270 Und dann, was haben wir getan, dass nach, wenn gab es mehrere Türen, um mit zu spielen? 220 00:07:25,270 --> 00:07:27,520 Wir würden halbieren, und wieder, und wieder, und wieder. 221 00:07:27,520 --> 00:07:30,420 Und das war genau wie euch alle Stehen bei der ersten Woche 222 00:07:30,420 --> 00:07:33,000 Klasse, die Hälfte von euch sitzen, halb der Sie sitzen, die Hälfte von euch 223 00:07:33,000 --> 00:07:35,440 Hinsetzen, bis ein einsamer Seele stand. 224 00:07:35,440 --> 00:07:39,050 Und wir sagten, dass die Laufzeit der Damit war die Anzahl der Schritte, es dauerte 225 00:07:39,050 --> 00:07:40,430 in der Größenordnung dessen, was? 226 00:07:40,430 --> 00:07:41,230 >> Sprecher 1: [unverständlich] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: So log Basis 2 n, oder einfach nur einfacher, von n einloggen. 228 00:07:43,970 --> 00:07:45,060 So etwas logarithmisch. 229 00:07:45,060 --> 00:07:48,380 Und die Kurve nicht eine gerade Linie dass nur noch schlimmer und schlimmer, es war 230 00:07:48,380 --> 00:07:52,490 diese interessante Kurve, die nicht bekommen so schlecht über die Zeit. 231 00:07:52,490 --> 00:07:53,910 Lassen Sie uns also an dieser Idee halten. 232 00:07:53,910 --> 00:07:54,690 Lasst uns danken Jennifer. 233 00:07:54,690 --> 00:07:56,150 Vielen Dank für Ihr Kommen etwas. 234 00:07:56,150 --> 00:07:57,400 Und eine Sekunde. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Keine Schreibtischlampen heute, aber wir Sie haben CS50 Stress-Bälle. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: All right, hier. 239 00:08:04,410 --> 00:08:06,545 Danke für die Entstehung der der Stress hier. 240 00:08:06,545 --> 00:08:07,350 In Ordnung. 241 00:08:07,350 --> 00:08:10,620 Also lasst uns sehen, ob wir nicht jetzt formalisieren diese ein bisschen mehr. 242 00:08:10,620 --> 00:08:14,820 Also noch einmal, war das, was wir gerade getan im Wesentlichen das Gleiche wie wir 243 00:08:14,820 --> 00:08:16,660 in dieser ersten Woche. 244 00:08:16,660 --> 00:08:23,780 Aber anstatt Ende mit nur ein lineares Algorithmus, die wir dargestellt 245 00:08:23,780 --> 00:08:27,210 früher als dieser Geraden, wobei, wenn wir eine weitere Tür zu setzen auf 246 00:08:27,210 --> 00:08:29,610 der Bildschirm, dann würde Jennifer mussten schauen, potentiell, 247 00:08:29,610 --> 00:08:30,600 hinter eine weitere Tür. 248 00:08:30,600 --> 00:08:33,490 Wenn wir zwei weitere Türen setzen, könnte sie haben zu schauen hinter zwei Türen mehr. 249 00:08:33,490 --> 00:08:35,990 >> Und so gab es diese lineare Beziehung zwischen der Größe der 250 00:08:35,990 --> 00:08:39,059 Problem auf, sagen wir, der x-Achse und die Menge an Zeit, die zum 251 00:08:39,059 --> 00:08:40,440 Lösung auf der y. 252 00:08:40,440 --> 00:08:43,330 Aber das Bild, das ich bis Anspielung wurde früher war diese grüne Linie. 253 00:08:43,330 --> 00:08:45,970 Grün bewusst, weil es fühlte sich besser. 254 00:08:45,970 --> 00:08:49,790 In der Theorie, den Algorithmus, wenn wir es getan haben mit dem Telefonbuch, wenn wir es getan haben 255 00:08:49,790 --> 00:08:52,420 mit euch zählen einander, und im zweiten Fall, wenn nur Jennifer 256 00:08:52,420 --> 00:08:55,250 tat es hier oben, war es irgendwie grundlegend besser. 257 00:08:55,250 --> 00:08:57,180 Denn es war nicht nur doppelt so schnell. 258 00:08:57,180 --> 00:08:58,870 Es war nicht sogar viermal so schnell. 259 00:08:58,870 --> 00:09:03,290 Es war völlig davon abhängig, was die Größe der Eingabe war, wie viele 260 00:09:03,290 --> 00:09:05,220 Schritte, die sie letztlich nahm. 261 00:09:05,220 --> 00:09:08,040 >> Und so einfache Idee, dass wir alle nahmen selbstverständlich mit dem Telefonbuch, 262 00:09:08,040 --> 00:09:10,200 in ähnlicher Weise angewendet werden, so etwas wie dies. 263 00:09:10,200 --> 00:09:12,380 Und dies könnte eher beiläufig sein bekannt als, wie Sie vielleicht 264 00:09:12,380 --> 00:09:13,940 vorstellen, teile und herrsche. 265 00:09:13,940 --> 00:09:16,390 Nicht anders als das, was wir taten, natürlich, mit dem Telefonbuch. 266 00:09:16,390 --> 00:09:18,300 >> Aber der Pseudocode, Rückruf, war diese. 267 00:09:18,300 --> 00:09:21,800 So werden wir nicht wieder tun, aber erinnern dass erste Woche stand uns alle bis 268 00:09:21,800 --> 00:09:25,140 und dann die Hälfte von euch hingesetzt, die Hälfte Sie setzte sich, saß die Hälfte von euch nach unten. 269 00:09:25,140 --> 00:09:29,280 Das Algorithmus wurde in eine umgesetzt Bit eines Betrugs Weise, daß es 270 00:09:29,280 --> 00:09:32,870 wurde nicht nur einer der mich zählen, grundsätzlich effizienter. 271 00:09:32,870 --> 00:09:35,830 In diesem Fall war ich die Nutzung eine sekundäre Ressource. 272 00:09:35,830 --> 00:09:39,470 Sortieren von verschiedenen CPUs, mehreren Gehirnen, mehrere intelligente Menschen in der 273 00:09:39,470 --> 00:09:42,740 Zimmer halfen mir aus etwas zu bekommen linear etwas 274 00:09:42,740 --> 00:09:45,190 logarithmisch, von etwas rot, etwas grün. 275 00:09:45,190 --> 00:09:48,650 >> Aber in diesem Fall kann allein Jennifer grundsätzlich auf die Verbesserung der 276 00:09:48,650 --> 00:09:52,370 Performance ihres ersten Algorithmus, wieder nur daran denke ein wenig härter. 277 00:09:52,370 --> 00:09:56,650 Und jetzt, wenn es darum geht, Zeit zu implementieren diese Dinge, herauszufinden, 278 00:09:56,650 --> 00:10:00,670 was Codezeilen können Sie schreiben, wie dass man sie wiederholen und 279 00:10:00,670 --> 00:10:03,350 wieder und wieder, irgendwie in einem Looping Mode. 280 00:10:03,350 --> 00:10:06,370 Weil du wirst doch nicht um das haben Luxus, wie Jennifer tat zunächst, um 281 00:10:06,370 --> 00:10:10,460 nur eine ganze Reihe von ifs und sagen, hmm wenn diese erste Zahl ist 4, 282 00:10:10,460 --> 00:10:11,800 Lassen Sie mich zu springen den ganzen Weg bis zum Ende. 283 00:10:11,800 --> 00:10:14,180 Ooh, wenn diese Zahl ist zu groß, lassen Sie mich willkürlich zurück bewegen 284 00:10:14,180 --> 00:10:15,220 zu dem zweiten Element. 285 00:10:15,220 --> 00:10:18,210 Du wirst feststellen, dass es geht um eine Menge sein schwerer zu formalisieren, was wir Menschen 286 00:10:18,210 --> 00:10:21,270 nehmen für so sehr vernünftig gewährt Heuristiken, aber ein Computer ist nur 287 00:10:21,270 --> 00:10:23,260 zu tun, was Sie sagen, es zu tun. 288 00:10:23,260 --> 00:10:25,280 >> Nun, das hat eine sehr interessante Auswirkungen. 289 00:10:25,280 --> 00:10:29,950 Dieses Diagramm ist eine Art soll von sortieren überwältigen visuell, aber beachten, wo 290 00:10:29,950 --> 00:10:32,230 die gerade Linie in diesem Diagramm? 291 00:10:32,230 --> 00:10:35,330 Wo ist die lineare Kurve dass wir n nennen? 292 00:10:35,330 --> 00:10:37,580 Nun, es ist eine Art in Richtung der Unterseite dieses Bild, nicht wahr? 293 00:10:37,580 --> 00:10:40,500 Also alles, was wir getan haben, ist, wir haben eine Art aus der x-Achse und das vergrößerte 294 00:10:40,500 --> 00:10:44,780 y-Achse, um zu versuchen, um ein Gefühl von dem, was sich andere Arten von Kurven aussehen. 295 00:10:44,780 --> 00:10:47,760 >> Und die Besonderheiten der mathematischen Ausdrücke heute nicht so wichtig 296 00:10:47,760 --> 00:10:52,440 viel, aber feststellen, dass es eine Menge von Algorithmen, die viel schlimmer sind als 297 00:10:52,440 --> 00:10:53,470 etwas, das linear ist. 298 00:10:53,470 --> 00:10:55,410 Tatsächlich sieht n gewürfelt ziemlich schlecht. 299 00:10:55,410 --> 00:10:58,400 2 zum n sieht ziemlich schlecht. n squared sieht ziemlich schlecht. 300 00:10:58,400 --> 00:11:01,630 Und wir werden sehen, was einige von denen vielleicht in Wirklichkeit heute. 301 00:11:01,630 --> 00:11:05,430 Und log n nicht so schlecht fühlen, aber besser als n log Basis 2 n. 302 00:11:05,430 --> 00:11:08,080 Aber Sie wissen, wäre es auch gewesen sein mehr erstaunlich, wenn Jennifer, oder wenn wir, 303 00:11:08,080 --> 00:11:12,910 dass erste Woche hatte mit zu kommen etwas, das Protokoll der log von n ist. 304 00:11:12,910 --> 00:11:15,880 >> Also mit anderen Worten, es ist das ganze Reihe von Lösungsmöglichkeiten 305 00:11:15,880 --> 00:11:18,570 Probleme, aber auch hier, Bekanntmachung was passieren wird. 306 00:11:18,570 --> 00:11:22,910 Als ich herausfand, Zoom, der von diesen Kurven wird sich als die absolute sein 307 00:11:22,910 --> 00:11:26,630 Schlimmste die, die auf dem Bildschirm jetzt? 308 00:11:26,630 --> 00:11:28,680 So n cubed sieht ziemlich schlecht im Moment. 309 00:11:28,680 --> 00:11:32,470 Aber wenn wir Verkleinern und sehen Sie mehr von der x und die y-Achse, die gehen, um ist 310 00:11:32,470 --> 00:11:34,550 dominieren letztlich? 311 00:11:34,550 --> 00:11:37,120 So ist es tatsächlich stellt sich heraus, dass die 2 bis n, und Sie können diese aus nur durch die Abbildung 312 00:11:37,120 --> 00:11:39,990 Einstecken in irgendeiner immer größeren Zahlen, und du wirst sehen, dass die 2 bis 313 00:11:39,990 --> 00:11:42,070 n der Tat immer größer viel schneller. 314 00:11:42,070 --> 00:11:45,530 Wenn wir wirklich Verkleinern, eine 2 bis die n-Algorithmus absolut scheiße. 315 00:11:45,530 --> 00:11:48,170 Ich meine, das wird dauern ziemlich viel Zeit für die 316 00:11:48,170 --> 00:11:49,460 Computer durch Kundenabwanderung. 317 00:11:49,460 --> 00:11:52,500 >> Aber du wirst im Laufe der Zeit zu sehen, vor allem mit zukünftigen Problem Sätze und sogar 318 00:11:52,500 --> 00:11:55,600 Abschlussarbeiten sind Ihre Daten Satz bekommt große, alles klar? 319 00:11:55,600 --> 00:11:58,300 Schon in der ersten Version von Facebook, wenn die Anzahl von Freunden, und 320 00:11:58,300 --> 00:12:01,840 Zahl der registrierten Nutzer haben große, Sie können es in der Telefon sortieren und 321 00:12:01,840 --> 00:12:05,530 Umsetzung etwas mit lineare Suche, oder ein sehr einfaches Sortieren 322 00:12:05,530 --> 00:12:07,030 Algorithmus, wie wir heute sehen. 323 00:12:07,030 --> 00:12:09,280 Sie müssen anfangen, härter und härter zu diesen Problemen. 324 00:12:09,280 --> 00:12:12,070 Und die Art von Problemen zu Orten wie Facebook und Google und Microsoft, 325 00:12:12,070 --> 00:12:16,350 und andere arbeiten auf genau diese Art von Big Data Art von Fragen 326 00:12:16,350 --> 00:12:18,530 zunehmend in diesen Tagen. 327 00:12:18,530 --> 00:12:18,900 >> In Ordnung. 328 00:12:18,900 --> 00:12:23,800 So Jennifer Erfolg in dieser zweiten Algorithmus, ehrlich gesagt, hat sie erstaunlich 329 00:12:23,800 --> 00:12:26,110 auch das erste Mal, aber wir schreibe es als Glück, so dass wir 330 00:12:26,110 --> 00:12:27,000 können diesen Punkt zu machen. 331 00:12:27,000 --> 00:12:30,970 Im zweiten Fall, sie eine Hebelwirkung Algorithmus wiederholt und 332 00:12:30,970 --> 00:12:34,670 wieder, aber sie hielten es für selbstverständlich ein bestimmte Annahme, dass es uns erlaubt 333 00:12:34,670 --> 00:12:39,370 sie, aber sie ausgebeutet einige Details der zweite Mal, dass sie nicht über die 334 00:12:39,370 --> 00:12:39,840 erste Zeit. 335 00:12:39,840 --> 00:12:41,800 Welches war was? 336 00:12:41,800 --> 00:12:43,050 >> Dass die Liste sortiert wurde. 337 00:12:43,050 --> 00:12:46,350 Also, sobald die Liste sortiert wurde, wir behaupten, dass Jennifer Lage zu tun war 338 00:12:46,350 --> 00:12:47,480 grundsätzlich besser. 339 00:12:47,480 --> 00:12:51,450 7 Türen, ja, das ist nicht so interessant, aber vermute, es sind wir 7 Millionen Türen. 340 00:12:51,450 --> 00:12:54,080 Anmelden von n ist definitiv zu viel, viel durchführen 341 00:12:54,080 --> 00:12:55,610 schneller auf lange Sicht. 342 00:12:55,610 --> 00:12:58,880 Aber sie musste die haben Türen für sie sortiert. 343 00:12:58,880 --> 00:13:02,320 Nun nahm ich mir die Freiheit, das zu tun im Voraus auf dem Computer-Bildschirm 344 00:13:02,320 --> 00:13:05,160 hier, aber denke, dass Jennifer musste, dass selbst tun? 345 00:13:05,160 --> 00:13:10,120 Angenommen, dass die Türen in Frage repräsentiert Daten in einer Datenbank, oder 346 00:13:10,120 --> 00:13:14,260 Freunde für Facebook registriert ist, oder Jede Web-Seiten im Internet, die 347 00:13:14,260 --> 00:13:16,880 verschiedenen Websites Möglicherweise müssen zum Index oder Suche vorbei. 348 00:13:16,880 --> 00:13:20,940 >> Angenommen, Sie haben gerade einen Rohdaten gesetzt und es wurde Ihnen überlassen, oder 349 00:13:20,940 --> 00:13:23,010 Jennifer zu tun, dass die Sortierung? 350 00:13:23,010 --> 00:13:26,950 Dass vielmehr erfordert, dass wir antworten die Frage, na ja, wie viel Zeit 351 00:13:26,950 --> 00:13:31,080 genommen hätte Jennifer oder auch mich, , diese Zahlen im Voraus so sortieren 352 00:13:31,080 --> 00:13:32,680 , sie könne das auszunutzen? 353 00:13:32,680 --> 00:13:32,880 Right? 354 00:13:32,880 --> 00:13:36,620 Da die Implikation, ist natürlich wenn es dauert eine ganze Weile zu sortieren 355 00:13:36,620 --> 00:13:40,800 die Zahlen, wer zum Teufel kümmert, dass Sie kann eine Zahl wie 50 so schnell zu finden, 356 00:13:40,800 --> 00:13:44,850 wie in Jennifers Fall, wenn wir mehr als überfordert die Menge der gesamten Zeit 357 00:13:44,850 --> 00:13:46,920 es dauerte ordnen Dinge im Voraus? 358 00:13:46,920 --> 00:13:49,320 >> Also mal sehen, ob wir nicht die malen das Bild hier. 359 00:13:49,320 --> 00:13:51,370 Ich habe eine ganze Menge mehr Stress Bälle, ob das hilft 360 00:13:51,370 --> 00:13:52,270 das Eis brechen hier. 361 00:13:52,270 --> 00:13:55,690 Und wenn es Ihnen nichts ausmacht, wir müssen sieben Freiwilligen - 362 00:13:55,690 --> 00:13:57,060 auf, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 So haben wir nicht zu verbringen auf dem Schreibtisch-Lampen, wie es scheint. 365 00:13:59,250 --> 00:13:59,690 In Ordnung. 366 00:13:59,690 --> 00:14:01,530 So wie sie Ihnen etwa zwei vor. 367 00:14:01,530 --> 00:14:04,160 Wie wäre es mit Ihnen beiden Jungs im Rücken. 368 00:14:04,160 --> 00:14:04,870 Also das ist vier. 369 00:14:04,870 --> 00:14:09,890 Wie wäre es mit Ihnen vor fünf, sechs und sieben. 370 00:14:09,890 --> 00:14:10,320 Genau dort. 371 00:14:10,320 --> 00:14:13,260 Ihr Freund freundlichst darauf hin, so erhalten Sie den Preis. 372 00:14:13,260 --> 00:14:13,700 >> In Ordnung. 373 00:14:13,700 --> 00:14:14,410 Komm up. 374 00:14:14,410 --> 00:14:17,120 Und warum haben wir nicht Sie Jungs kommen auf hier. 375 00:14:17,120 --> 00:14:18,960 Ich werde Ihnen jeweils eine Nummer. 376 00:14:18,960 --> 00:14:22,150 Und gehen Sie vor und arrangieren sich identisch zu dem, was 377 00:14:22,150 --> 00:14:25,180 dargestellt auf dem Bildschirm. 378 00:14:25,180 --> 00:14:26,530 >> [Zwischenschaltung VOICES] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 In Ordnung. 382 00:14:32,180 --> 00:14:32,750 Nun, hier gehen wir. 383 00:14:32,750 --> 00:14:34,180 Nummer fünf. 384 00:14:34,180 --> 00:14:35,136 Nummer sechs. 385 00:14:35,136 --> 00:14:37,770 Eine, zwei, drei, vier, fünf, sechs, sieben. 386 00:14:37,770 --> 00:14:39,410 Oh, das ist peinlich. 387 00:14:39,410 --> 00:14:41,210 >> Sprecher 2: Ich werde einfach ein -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Good deal. 389 00:14:41,900 --> 00:14:43,130 In Ordnung. 390 00:14:43,130 --> 00:14:44,611 Vielen Dank für Ihre Teilnahme. 391 00:14:44,611 --> 00:14:47,200 >> [Applaus] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 In Ordnung. 394 00:14:48,860 --> 00:14:51,970 So haben wir vier, zwei, sechs, eins, drei, sieben, fünf. 395 00:14:51,970 --> 00:14:56,010 Perfekt, so dass wir sieben Freiwillige hier, die sind in der Breite gleich der 396 00:14:56,010 --> 00:14:57,430 Array, das wir spielen mit der früheren. 397 00:14:57,430 --> 00:14:59,470 Und ich wählte sieben Gründen das wird nur 398 00:14:59,470 --> 00:15:00,840 bequem in ein wenig. 399 00:15:00,840 --> 00:15:04,400 Und ich werde zum ersten schlagen vor, dass sortieren wir diese sieben Freiwilligen. 400 00:15:04,400 --> 00:15:06,786 Wenn Sie möchten, zuerst, hallo zu sagen though. 401 00:15:06,786 --> 00:15:08,970 Da dies wird eine sein umständlich mehrere Minuten. 402 00:15:08,970 --> 00:15:10,370 Stellen Sie sich vor. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hallo, ich bin Gnade. 404 00:15:10,980 --> 00:15:14,190 Ich bin im zweiten Jahr in Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Hallo. 406 00:15:14,620 --> 00:15:15,620 Ich bin Branson. 407 00:15:15,620 --> 00:15:16,920 Ich bin ein Neuling in der Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hallo. 410 00:15:20,230 --> 00:15:21,040 Ich bin Gabe. 411 00:15:21,040 --> 00:15:22,300 Ich bin ein Junior in Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Ich bin Neil. 414 00:15:25,980 --> 00:15:29,090 Ich bin ein Neuling in Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Ich bin Jason. 416 00:15:29,550 --> 00:15:32,816 Ich bin ein Neuling in Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Ich bin Mike. 418 00:15:33,700 --> 00:15:37,360 Ich bin ein Neuling in Grays. 419 00:15:37,360 --> 00:15:37,990 >> Jess: Ich bin Jess. 420 00:15:37,990 --> 00:15:40,313 Ich bin im zweiten Jahr in Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excellent. 422 00:15:41,300 --> 00:15:41,850 In Ordnung. 423 00:15:41,850 --> 00:15:44,190 Nun, ich danke Ihnen für alle unsere Freiwillige hier so weit. 424 00:15:44,190 --> 00:15:47,110 Und die Herausforderung bei der Hand jetzt los ist zu sein, um von diesen Jungs zu sortieren, aber dann 425 00:15:47,110 --> 00:15:50,250 wir gehen zu müssen, ein wenig zu denken hart, wie effizient wir eigentlich 426 00:15:50,250 --> 00:15:51,110 sortiert sie. 427 00:15:51,110 --> 00:15:52,580 Also lassen Sie uns zuerst dieses zu versuchen. 428 00:15:52,580 --> 00:15:55,970 Ihr könnt sehen einander die Zahlen nur, indem um die Ecken. 429 00:15:55,970 --> 00:15:59,380 Gehen Sie voran und nehmen Sie ein paar Sekunden, und sort euch von der kleinsten auf dem 430 00:15:59,380 --> 00:16:01,240 links nach größte auf der rechten Seite. 431 00:16:01,240 --> 00:16:02,490 Gehen. 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 Gut. 435 00:16:08,030 --> 00:16:09,370 Das war wirklich verdammt schnell. 436 00:16:09,370 --> 00:16:14,040 Jetzt hier jemand, was der Algorithmus dass diese Jungs angewendet? 437 00:16:14,040 --> 00:16:14,900 >> Sprecher 1: kleinste bis größte. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Kleinste bis größte ist wirklich von der Art Ziel, aber ich bin mir nicht sicher, dass es 440 00:16:18,070 --> 00:16:18,890 wirklich ein Algorithmus. 441 00:16:18,890 --> 00:16:21,810 Kleinste bis größte nicht sagen mich Schritt für Schritt, was zu tun ist. 442 00:16:21,810 --> 00:16:22,833 Ja? 443 00:16:22,833 --> 00:16:24,083 >> Sprecher 1: [unverständlich] 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 Also, wenn Sie sehen, eine Person weniger als Ihre Zahl ist, dann bewegen, um 447 00:16:28,920 --> 00:16:29,680 das Recht von ihnen. 448 00:16:29,680 --> 00:16:32,800 Also das ist jetzt immer mehr expressive, mehr wie ein Algorithmus, da Sie 449 00:16:32,800 --> 00:16:35,410 sagen kann, wenn diese, dass dann. 450 00:16:35,410 --> 00:16:37,050 So haben wir eine Art von Bedingungskonstrukt. 451 00:16:37,050 --> 00:16:39,700 Und diese Jungs schien, dass ein paar tun mal, weil einige von euch ein wenig bewegt 452 00:16:39,700 --> 00:16:40,420 eines Abstands. 453 00:16:40,420 --> 00:16:43,410 So gab es vermutlich eine Art Looping geht in ihren Köpfen. 454 00:16:43,410 --> 00:16:44,610 >> Aber lassen Sie uns versuchen, dass zu formalisieren. 455 00:16:44,610 --> 00:16:47,540 Wenn euch könnte zurückgesetzt dieser Anordnung. 456 00:16:47,540 --> 00:16:50,650 Mal sehen, ob wir nicht formalisiert diesen ein bit, und dann die Frage stellen, nur 457 00:16:50,650 --> 00:16:51,580 Wie effizient ist das? 458 00:16:51,580 --> 00:16:54,220 Natürlich, wenn wir dies tun, langsamer, es geht um das Gefühl, als gut von 459 00:16:54,220 --> 00:16:57,210 ein Algorithmus, aber wir sehen, ob wir setzen unsere Finger über die genauen Schritte. 460 00:16:57,210 --> 00:16:58,670 >> So ihr beiden Jungs sind vier und zwei. 461 00:16:58,670 --> 00:17:01,020 Oder Sie richtig oder falsch um? 462 00:17:01,020 --> 00:17:01,900 Offensichtlich falsche. 463 00:17:01,900 --> 00:17:02,710 Also haben wir getauscht. 464 00:17:02,710 --> 00:17:05,170 Jetzt werde ich beiseite bewegen und sagen, vier bis sechs. 465 00:17:05,170 --> 00:17:06,240 Sind Sie richtig oder falsch? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Richtig. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Richtig. 468 00:17:07,180 --> 00:17:08,300 Sechs und eins? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Tauschen. 471 00:17:09,630 --> 00:17:10,490 Also das ist zwei-Swaps. 472 00:17:10,490 --> 00:17:11,710 Sechs und drei? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Tauschen. 475 00:17:13,000 --> 00:17:13,930 Sechs und sieben? 476 00:17:13,930 --> 00:17:14,630 Sieht gut aus. 477 00:17:14,630 --> 00:17:15,396 Sieben und fünf? 478 00:17:15,396 --> 00:17:16,150 >> Jess: [unverständlich] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, tauschen. 480 00:17:17,089 --> 00:17:19,770 Und sortiert. 481 00:17:19,770 --> 00:17:19,980 In Ordnung. 482 00:17:19,980 --> 00:17:21,440 So offensichtlich nicht, oder? 483 00:17:21,440 --> 00:17:22,470 Also es war mehr los. 484 00:17:22,470 --> 00:17:24,920 Aber in der Tat, diese Jungs, auch nur instinktiv. 485 00:17:24,920 --> 00:17:25,450 Bewegung gehalten. 486 00:17:25,450 --> 00:17:27,710 Sie haben nicht nur zu stoppen, wenn sie korrigiert ein Problem. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 Tatsächlich bin ich zu haben, um die gleiche Sache zu tun. 489 00:17:29,390 --> 00:17:32,720 Ich werde zu haben, um der Rücklauf wieder sortieren zu Beginn dieses Problems 490 00:17:32,720 --> 00:17:35,630 oder der Anfang dieser Reihe Leute, lasst uns rufen Sie diese. 491 00:17:35,630 --> 00:17:38,366 >> Und nun, was sollte mein Algorithmus im zweiten Durchgang sein? 492 00:17:38,366 --> 00:17:39,220 >> Sprecher 1: Die gleiche Sache. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Dasselbe. 494 00:17:39,940 --> 00:17:41,460 Und dies, fange ich an, gerne, nicht wahr? 495 00:17:41,460 --> 00:17:44,720 Sobald Du selbst tun die gleiche Sache immer und immer wieder, das ist 496 00:17:44,720 --> 00:17:47,890 immer mehr wie ein Algorithmus, und weniger menschlicher Instinkt. 497 00:17:47,890 --> 00:17:48,680 >> So, jetzt, hier gehen wir wieder. 498 00:17:48,680 --> 00:17:49,870 Zwei und vier? 499 00:17:49,870 --> 00:17:50,220 Nr. 500 00:17:50,220 --> 00:17:51,050 Vier und ein? 501 00:17:51,050 --> 00:17:53,380 Ah, es war in der Tat einige Arbeit noch getan werden muss. 502 00:17:53,380 --> 00:17:53,620 Für und drei? 503 00:17:53,620 --> 00:17:54,572 Gut. 504 00:17:54,572 --> 00:17:56,000 Vier und sechs? 505 00:17:56,000 --> 00:17:58,380 Sechs und fünf? 506 00:17:58,380 --> 00:17:59,470 Sechs und sieben? 507 00:17:59,470 --> 00:18:00,970 OK, jetzt, fertig. 508 00:18:00,970 --> 00:18:01,550 OK, nein. 509 00:18:01,550 --> 00:18:02,710 Ich muss zurück. 510 00:18:02,710 --> 00:18:05,130 >> So, jetzt wieder, wir tun dies ein wenig mehr bewusst. 511 00:18:05,130 --> 00:18:08,700 Und jetzt gibt es nur ein Gehirn Ausführung dieses Algorithmus. 512 00:18:08,700 --> 00:18:10,290 Eine CPU, wenn man so will. 513 00:18:10,290 --> 00:18:13,090 Und ehrlich gesagt, das ist die einzige Ressource, werden wir den Zugang zu haben. 514 00:18:13,090 --> 00:18:16,280 Und sobald wir zurück zu einer Tastatur und haben so etwas wie C in unserem 515 00:18:16,280 --> 00:18:19,600 Verfügung, wir nur ein Programm schreiben das kann eine Sache zu einer Zeit zu tun. 516 00:18:19,600 --> 00:18:22,900 Während, diese Jungs vor einem Augenblick, wir Leveraged ihre kollektive Intelligenz 517 00:18:22,900 --> 00:18:24,180 wie Sie Jungs haben in Woche null. 518 00:18:24,180 --> 00:18:24,980 Also lasst uns weiter machen. 519 00:18:24,980 --> 00:18:26,260 >> Zwei und eins. 520 00:18:26,260 --> 00:18:26,945 Zwei und drei. 521 00:18:26,945 --> 00:18:27,460 Drei und vier. 522 00:18:27,460 --> 00:18:28,310 Vier und fünf. 523 00:18:28,310 --> 00:18:28,620 Fünf und sechs. 524 00:18:28,620 --> 00:18:30,510 Sechs und sieben. 525 00:18:30,510 --> 00:18:31,880 Fertig? 526 00:18:31,880 --> 00:18:34,560 Also ich bin, aber lass mich spielen Advokat des Teufels. 527 00:18:34,560 --> 00:18:37,950 Muss ich, die Art von Computer, die gerade einen Pass durch diese Anordnung von 528 00:18:37,950 --> 00:18:40,225 Menschen, wissen, dass ich fertig bin? 529 00:18:40,225 --> 00:18:40,670 >> Sprecher 1: No 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Warum? 531 00:18:41,050 --> 00:18:46,900 Was müsste ich tun, um Schluss entscheidend, dass ich fertig bin? 532 00:18:46,900 --> 00:18:48,230 Wahrscheinlich einer mehr weiter. 533 00:18:48,230 --> 00:18:48,430 Right? 534 00:18:48,430 --> 00:18:51,760 Weil alles, was ich wissen von diesem früheren Pass ist, dass ich einen Fehler korrigiert. 535 00:18:51,760 --> 00:18:53,920 Und das bedeutet, vielleicht gibt es noch ein weiterer Fehler 536 00:18:53,920 --> 00:18:54,840 dass ich korrigieren müssen. 537 00:18:54,840 --> 00:18:58,680 Ich kann also nur durch Zurückspulen sicher und dann überprüft, 01.59, und zwei 538 00:18:58,680 --> 00:19:00,940 drei, drei und vier, vier und fünf, fünf und sechs, sechs und sieben. 539 00:19:00,940 --> 00:19:02,510 OK, jetzt habe ich keine Arbeit. 540 00:19:02,510 --> 00:19:05,990 >> Ich kann sicherlich daran erinnern, dass ich nicht tat arbeiten mit so etwas wie einer variablen, 541 00:19:05,990 --> 00:19:06,975 wie ein int. 542 00:19:06,975 --> 00:19:12,490 Nennen Sie es, Swaps und Swaps, wenn 0 ist, wenn ich hier erhalten, und es begann bei 0, dann 543 00:19:12,490 --> 00:19:15,520 Ich wäre einfach dumm, um weiterzumachen hin und her und erneut prüfen, und 544 00:19:15,520 --> 00:19:16,450 wieder und wieder, nicht wahr? 545 00:19:16,450 --> 00:19:18,450 Weil man in einigen stecken Art Endlosschleife. 546 00:19:18,450 --> 00:19:21,250 Also, sobald es 0 Swaps, Wir können behaupten, dass diese 547 00:19:21,250 --> 00:19:23,810 Algorithmus ist in der Tat abgeschlossen. 548 00:19:23,810 --> 00:19:25,400 >> Nun, lasst uns einen Namen zu diesem Thema. 549 00:19:25,400 --> 00:19:28,930 Der Algorithmus, den ich schlagen wir nur implementiert ist etwas namens bubble 550 00:19:28,930 --> 00:19:32,800 Art, die als solche in dem Sinne bekannt, dass die Zahlen, die größer sind Art 551 00:19:32,800 --> 00:19:37,990 Blase ihren Weg bis an die Spitze, oder bis bis zum Ende der Reihe von Zahlen. 552 00:19:37,990 --> 00:19:40,270 Aber wie effizient war dieser Algorithmus? 553 00:19:40,270 --> 00:19:44,600 Wie viele Schritte habe ich körperlich müssen nehmen, zum Beispiel, um diese zu sortieren 554 00:19:44,600 --> 00:19:45,850 sieben Menschen? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Vier bis fünf? 557 00:19:49,550 --> 00:19:51,420 OK, zu viel ist letztlich gehen, um die Antwort sein. 558 00:19:51,420 --> 00:19:54,960 Aber selbst dann, die bestimmte Anzahl ist nicht so interessant. 559 00:19:54,960 --> 00:19:56,670 Lasst verallgemeinern es als n. 560 00:19:56,670 --> 00:20:00,520 Also, wenn ich n Menschen hier oben, und sie waren, irgendwie, in zufälliger Reihenfolge auf das 561 00:20:00,520 --> 00:20:02,180 Anfang, in diesem ursprünglichen Reihenfolge. 562 00:20:02,180 --> 00:20:04,910 Nun, wie viele Schritte ich haben auf dem ersten Pass zu nehmen? 563 00:20:04,910 --> 00:20:09,810 Es war eine, zwei, drei, vier, fünf, sechs, und sie sind sieben Personen, so 564 00:20:09,810 --> 00:20:13,670 das ist sieben, sechs -, so, das ist n minus eins tritt die erste Zeit. 565 00:20:13,670 --> 00:20:16,280 >> Nun, wie viele Schritte ich haben zu nehmen, wenn ich zurückgespult? 566 00:20:16,280 --> 00:20:19,310 Nun, wir könnten tatsächlich verdoppeln, wenn wir wollten, aber jetzt bin ich 567 00:20:19,310 --> 00:20:22,300 gerade sagen, alles in Ordnung, andere n minus 1. 568 00:20:22,300 --> 00:20:25,240 Also das n minus 1 wird erhalten ärgerlich, um zu verfolgen, also lasst uns 569 00:20:25,240 --> 00:20:26,400 nur aufrunden leicht. 570 00:20:26,400 --> 00:20:27,770 So 2n Schritte. 571 00:20:27,770 --> 00:20:29,310 So 14 Stufen, geben oder nehmen. 572 00:20:29,310 --> 00:20:31,930 >> Wie oft habe ich ein Schritt das nächste Mal? 573 00:20:31,930 --> 00:20:33,740 Nun, es ist 3n. 574 00:20:33,740 --> 00:20:34,510 wirklich. 575 00:20:34,510 --> 00:20:37,920 Und nun, im schlimmsten Fall, für Beispielsweise würde, wie viele Male habe ich 576 00:20:37,920 --> 00:20:41,730 hin und her, hin und her gegangen, Ausführung dieses Algorithmus, Swapping 577 00:20:41,730 --> 00:20:44,620 Menschen bei jedem Durchgang, etwa? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Es ist eigentlich n squared, nicht wahr? 580 00:20:50,010 --> 00:20:53,000 >> Denn im schlimmsten Fall können Sie Art denken über das intuitiv, 581 00:20:53,000 --> 00:20:54,800 auch wenn es vielleicht ein wenig wenig Zeit zu sinken in. 582 00:20:54,800 --> 00:20:57,590 Im schlimmsten Fall, was würden diese sieben Menschen aussah, in 583 00:20:57,590 --> 00:21:00,230 Bedingungen der Vereinbarung ihrer Zahlen? 584 00:21:00,230 --> 00:21:01,460 Ganz hinten, richtig? 585 00:21:01,460 --> 00:21:02,815 Und nur um zu simulieren, dass was war noch mal Ihr Name? 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 OK, Mike, können Sie einfach mit mir über hier nur eine Sekunde? 589 00:21:08,100 --> 00:21:08,880 Eigentlich nicht. 590 00:21:08,880 --> 00:21:10,150 Leider Mike, lass uns Rücklauf. 591 00:21:10,150 --> 00:21:10,910 Was ist Ihr Name? 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 OK, Neil, du kommst mit mich, wenn es Ihnen nichts ausmacht. 595 00:21:13,750 --> 00:21:17,150 Also werde ich vorschlagen, nur für Einfachheit, dass Neil ist jetzt in seinem 596 00:21:17,150 --> 00:21:18,510 ungünstigsten Fall. 597 00:21:18,510 --> 00:21:20,720 Aber daran erinnern, wie ich umgesetzt mein Algorithmus. 598 00:21:20,720 --> 00:21:24,530 Ich vergleiche, Vergleichen, vergleichen, Vergleichen, vergleichen, oh. 599 00:21:24,530 --> 00:21:26,640 Nun sind diese Jungs sind out Ordnung, so dass ich zu beheben. 600 00:21:26,640 --> 00:21:27,980 Also Jungs tauschen. 601 00:21:27,980 --> 00:21:31,630 Aber nun zu prüfen, wie weit Neil hat gehen müssen? 602 00:21:31,630 --> 00:21:32,690 Es ist etwa n. 603 00:21:32,690 --> 00:21:33,570 Sie wissen, es ist nicht wirklich n. 604 00:21:33,570 --> 00:21:36,040 Es ist wie, n minus 1, aber ich bin immer verärgert die Verfolgung des kleinen 605 00:21:36,040 --> 00:21:37,550 Zahl, so lasst uns einfach nennen es n. 606 00:21:37,550 --> 00:21:42,860 >> Also, wenn Neil bewegt sich einen Schritt maximal jeweils Zeit, und Neil einem Schritt zu verschieben 607 00:21:42,860 --> 00:21:46,580 Ich habe diese wirklich mühsame Pass machen hin und her, das ist etwa 608 00:21:46,580 --> 00:21:52,080 Dabei n Schritten, insgesamt n Mal, denn es geht um mich 609 00:21:52,080 --> 00:21:55,820 dass viele Schritte, um Neil alle der Weg dorthin, wo er hingehört. 610 00:21:55,820 --> 00:21:58,620 Geschweige denn jeder andere, wenn euch waren alle falsch bestellt als gut. 611 00:21:58,620 --> 00:22:01,100 >> So nennen wir bubble sort n Quadrat. 612 00:22:01,100 --> 00:22:04,860 Die Laufzeit dieses Algorithmus, der Leistung dieses Algorithmus die 613 00:22:04,860 --> 00:22:07,120 Effizienz dieses Algorithmus, werden wir nur beschreiben mehr 614 00:22:07,120 --> 00:22:08,800 allgemein als n straffte. 615 00:22:08,800 --> 00:22:11,650 Welches ist nett, weil ich tun konnte, die Dasselbe Beispiel mit acht Personen, neun 616 00:22:11,650 --> 00:22:15,450 Menschen, eine Million Menschen, und dass Antwort ist nicht zu ändern. 617 00:22:15,450 --> 00:22:18,870 >> Also, wenn euch nichts dagegen hätte, lasst setzen Sie, wo Sie begonnen. 618 00:22:18,870 --> 00:22:22,510 Und lassen Sie uns versuchen, zwei andere Ansätze und sehen, ob wir nicht grundsätzlich tun können 619 00:22:22,510 --> 00:22:23,820 besser als diese. 620 00:22:23,820 --> 00:22:27,130 Also dieser Zeit, ich werde vorschlagen eine Art von anderen Algorithmus. 621 00:22:27,130 --> 00:22:29,950 Das war sehr klug von uns beim letzten Mal, und euch zu Recht die haben 622 00:22:29,950 --> 00:22:32,470 Recht Instinkte nur irgendwie Auslagern paarweise. 623 00:22:32,470 --> 00:22:36,500 Aber wenn ich wirklich wollte, um diesen Ansatz einfach, und mein Ziel ist es, sich zu bewegen 624 00:22:36,500 --> 00:22:39,800 all die kleinen Zahlen auf diese Weise, und schieben alle den großen Zahlen, 625 00:22:39,800 --> 00:22:43,030 Weise, warum ich nicht einfach zu tun, dass in der naivsten Weise möglich und sehen, ob ich 626 00:22:43,030 --> 00:22:45,730 besser machen können als das, was ein recht komplexen Algorithmus? 627 00:22:45,730 --> 00:22:46,620 >> Also mal sehen. 628 00:22:46,620 --> 00:22:48,940 Vier ist eine ziemlich kleine Zahl, also bin ich werde dich dort zu lassen Moment. 629 00:22:48,940 --> 00:22:50,610 Ooh, ist die Nummer zwei sogar noch besser. 630 00:22:50,610 --> 00:22:52,230 So können Sie einfach Schritt vorwärts für einen Moment? 631 00:22:52,230 --> 00:22:55,670 Dies ist mein derzeitiger kleinste nummeriert Kandidat, und ich werde daran zu erinnern, 632 00:22:55,670 --> 00:22:57,000 dass mit, wie, eine Variable. 633 00:22:57,000 --> 00:22:57,930 Aber ich werde immer mal. 634 00:22:57,930 --> 00:22:59,890 Gibt es jemanden, dessen Zahl ist kleiner? 635 00:22:59,890 --> 00:23:00,460 Sechs, nein. 636 00:23:00,460 --> 00:23:01,390 Oh, da ist Neil wieder. 637 00:23:01,390 --> 00:23:04,050 >> Also werde ich Ihnen zurückschieben Art konzeptuell. 638 00:23:04,050 --> 00:23:05,120 Neil wird vorwärts zu kommen. 639 00:23:05,120 --> 00:23:08,440 Und nun, die Variable, die ich benutze, um verfolgen, wer hat den kleinsten 640 00:23:08,440 --> 00:23:11,390 Zahl wird aktualisiert, um enthalten Neil Standort. 641 00:23:11,390 --> 00:23:12,110 Naja, mal sehen. 642 00:23:12,110 --> 00:23:13,960 Drei, sieben, fünf. 643 00:23:13,960 --> 00:23:15,590 OK, ich weiß, Neil war das kleinste. 644 00:23:15,590 --> 00:23:18,110 Was ist die einfachste Sache für mich jetzt zu tun? 645 00:23:18,110 --> 00:23:21,410 Ich werde nicht meine Zeit verschwenden, indem nur Einleiten Neil einer Stelle auf der linken Seite. 646 00:23:21,410 --> 00:23:25,350 Warum kann ich nicht einfach setzen Neil wo er gehört, ist das natürlich wo? 647 00:23:25,350 --> 00:23:26,160 >> Den ganzen Weg am Anfang. 648 00:23:26,160 --> 00:23:27,720 So Neil, mit mir zu kommen. 649 00:23:27,720 --> 00:23:28,910 Und was war noch mal Ihr Name? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Gnade. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Gnade. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 So Anmut, leider bist du Art in den Weg. 654 00:23:32,490 --> 00:23:34,290 So, wie wir dieses Problem lösen? 655 00:23:34,290 --> 00:23:34,490 Right? 656 00:23:34,490 --> 00:23:37,500 Wenn dies ein Array ist, gibt es nur sieben Standorten. 657 00:23:37,500 --> 00:23:40,830 Daran erinnern, dass mit Rob, sprachen wir über erklärt Altersstufen, und wir hatten nur ein 658 00:23:40,830 --> 00:23:41,740 endliche Anzahl von Alters? 659 00:23:41,740 --> 00:23:42,535 Gleiche Idee hier. 660 00:23:42,535 --> 00:23:44,300 Wir haben nur eine endliche Anzahl von ints. 661 00:23:44,300 --> 00:23:47,590 Anmut ist eine Art in unserer Übrigens, so wie wir das Problem beheben? 662 00:23:47,590 --> 00:23:49,555 >> Der einfachste Weg ist wie, Anmut, sorry. 663 00:23:49,555 --> 00:23:51,870 Du gehst zu müssen, gehen über so können wir es machen Platz. 664 00:23:51,870 --> 00:23:55,290 Nun, wenn Sie darüber nachdenken, vielleicht wir machten das Problem noch schlimmer. 665 00:23:55,290 --> 00:23:58,510 Und vielleicht haben wir, denn was ist, wenn Anmut waren an der richtigen Stelle? 666 00:23:58,510 --> 00:24:01,730 Aber wir wissen, dass sie nicht, denn sonst wäre sie gewesen, 667 00:24:01,730 --> 00:24:03,980 stehend nach vorne statt Neil in dieser Zeit, nicht wahr? 668 00:24:03,980 --> 00:24:05,550 Wir haben bereits überprüft ihre Nummer aus. 669 00:24:05,550 --> 00:24:05,770 >> In Ordnung. 670 00:24:05,770 --> 00:24:09,110 So, jetzt ist Neil an der richtigen Stelle, und Ich kann eine leichte Optimierung. 671 00:24:09,110 --> 00:24:11,740 Für den nächsten Minuten werde ich zu ignorieren Neil alle zusammen, um nicht 672 00:24:11,740 --> 00:24:15,280 seine Zeit verschwenden, oder versehentlich tauschen ihn an der falschen Stelle. 673 00:24:15,280 --> 00:24:17,805 So, jetzt, wie finde ich die nächste Element, das kleinste ist? 674 00:24:17,805 --> 00:24:18,480 Zwei. 675 00:24:18,480 --> 00:24:20,225 Das ist eine ziemlich gute Zahl, wenn Sie wollen nach vorne zu treten und 676 00:24:20,225 --> 00:24:21,100 Ich werde dich erinnern. 677 00:24:21,100 --> 00:24:21,980 Six, nicht gut. 678 00:24:21,980 --> 00:24:24,820 Vier, drei, sieben, fünf, nicht gut. 679 00:24:24,820 --> 00:24:26,800 Lassen Sie mich also bewegen Sie Ihren richtigen Stelle. 680 00:24:26,800 --> 00:24:28,470 Und wir hatten Glück diesmal. 681 00:24:28,470 --> 00:24:31,350 >> Nun, ich werde diese ignorieren zwei Jungs, und jetzt führen Sie einen mehr 682 00:24:31,350 --> 00:24:32,260 durchlaufen diese. 683 00:24:32,260 --> 00:24:33,490 Six, dass eine ziemlich kleine Anzahl. 684 00:24:33,490 --> 00:24:34,300 Komm nach vorn. 685 00:24:34,300 --> 00:24:35,220 Oh, sorry. 686 00:24:35,220 --> 00:24:37,640 Grace Zahl ist besser, so Schritt vorwärts auf. 687 00:24:37,640 --> 00:24:38,260 Four. 688 00:24:38,260 --> 00:24:39,120 Sorry, Gnade. 689 00:24:39,120 --> 00:24:39,950 Gehe wieder zurück. 690 00:24:39,950 --> 00:24:41,550 Nummer drei ist besser. 691 00:24:41,550 --> 00:24:42,290 Seven. 692 00:24:42,290 --> 00:24:42,720 Five. 693 00:24:42,720 --> 00:24:43,550 Und jetzt, was ist Ihr Name? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Also Jason ist nun der kleinste Element habe ich ausgewählt. 697 00:24:47,050 --> 00:24:49,160 Wo ist er hin? 698 00:24:49,160 --> 00:24:50,380 Also, wo ist sechs. 699 00:24:50,380 --> 00:24:51,210 Und Ihr Name ist wieder? 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 ist im Weg. 703 00:24:53,220 --> 00:24:54,640 Was ist die einfachste Sache zu tun? 704 00:24:54,640 --> 00:24:58,390 Tauschen Sie diese beiden Jungs und weiter. 705 00:24:58,390 --> 00:24:59,020 So, jetzt wollen wir mal sehen. 706 00:24:59,020 --> 00:25:00,170 Wer ist der kleinste? 707 00:25:00,170 --> 00:25:01,030 Four. 708 00:25:01,030 --> 00:25:01,990 Lassen Sie mich nur eine Art Cheat. 709 00:25:01,990 --> 00:25:03,090 Five wird der kleinste sein. 710 00:25:03,090 --> 00:25:05,220 Ich finde nächsten, wenn Sie zu Schritt wollen nach vorn, was muss ich tun, um mit 711 00:25:05,220 --> 00:25:06,820 diese Jungs, mit Gabe? 712 00:25:06,820 --> 00:25:08,450 Tauschen Sie es erneut. 713 00:25:08,450 --> 00:25:10,740 So, jetzt noch etwas nicht in Ordnung. 714 00:25:10,740 --> 00:25:14,140 Ich fand die kleinste Gabe sein, so Ich knallen ihn aus, bewegen Sie sich über Jungs. 715 00:25:14,140 --> 00:25:15,190 Und fertig. 716 00:25:15,190 --> 00:25:17,200 >> So Antwort ist die gleiche. 717 00:25:17,200 --> 00:25:18,600 Das Ergebnis ist das gleiche. 718 00:25:18,600 --> 00:25:22,730 Welche dieser beiden Algorithmen ist besser? 719 00:25:22,730 --> 00:25:23,500 Die zweite, hörte ich. 720 00:25:23,500 --> 00:25:24,252 Warum? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Es ist n Schritten [unverständlich]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Es ist n Schritte bei den meisten. 723 00:25:27,600 --> 00:25:28,490 Interessante. 724 00:25:28,490 --> 00:25:30,610 So ist es eigentlich? 725 00:25:30,610 --> 00:25:33,630 Wie kam ich finde die kleinste Element? 726 00:25:33,630 --> 00:25:37,060 Wie viele Schritte musste ich nehmen die finden das kleinste Element? 727 00:25:37,060 --> 00:25:39,220 Ich hatte einen Blick den ganzen Weg am Ende, nicht wahr? 728 00:25:39,220 --> 00:25:41,530 Da in diesem schlimmsten Fall, was wenn Neil waren hier? 729 00:25:41,530 --> 00:25:45,700 So einfach finden Sie das kleinste Element nimmt mich n Schritte, oder n minus 1. 730 00:25:45,700 --> 00:25:46,100 Aber OK. 731 00:25:46,100 --> 00:25:46,980 So beheben Neil. 732 00:25:46,980 --> 00:25:48,740 Denken Sie daran, dass Sie eine Minute oder so vor. 733 00:25:48,740 --> 00:25:51,680 >> Aber wie finde ich die nächste kleinste Element? 734 00:25:51,680 --> 00:25:54,830 Es ist n minus 1 oder n minus 2 wirklich, von der Anzahl der Schritte. 735 00:25:54,830 --> 00:25:55,440 So OK. 736 00:25:55,440 --> 00:25:57,390 Also habe ich minus 2 N. 737 00:25:57,390 --> 00:25:57,600 In Ordnung. 738 00:25:57,600 --> 00:25:59,130 Also das fühlt sich ein wenig besser. 739 00:25:59,130 --> 00:25:59,730 In Ordnung. 740 00:25:59,730 --> 00:26:03,270 Wie viele Schritte das nächste Mal auf Platz drei zu finden? 741 00:26:03,270 --> 00:26:04,420 So n minus 4. 742 00:26:04,420 --> 00:26:07,670 So ist es ab, eine weniger Schritt bei jeder Iteration. 743 00:26:07,670 --> 00:26:08,740 Also das fühlt sich besser, nicht wahr? 744 00:26:08,740 --> 00:26:13,450 Wenn letzte Mal war es etwa n mal n, diesmal ist es n minus 1 plus n minus 745 00:26:13,450 --> 00:26:16,500 2, plus n minus 3, plus n minus 4, Punkt, Punkt, Punkt. 746 00:26:16,500 --> 00:26:18,750 Aber wenn Sie sich erinnern, von Ihrem High-School- Lehrbücher, die kleine Cheat 747 00:26:18,750 --> 00:26:24,380 Blech auf der Rückseite, die Formeln hat, wenn Sie summieren sich diese Reihe von Zahlen, 748 00:26:24,380 --> 00:26:31,280 was ist die Gesamtzahl der Schritte zu sein, dass ich hier nehmen? 749 00:26:31,280 --> 00:26:36,580 >> Dies ist einer von denen, wie, n minus 1, n mal, geteilt durch 2. 750 00:26:36,580 --> 00:26:39,040 Also lassen Sie mich sehen, ob ich ziehen kann dies für einen Moment. 751 00:26:39,040 --> 00:26:42,230 Und wieder, ich bin Art der Rundung einige Zahlen nur um unser Leben einfacher, 752 00:26:42,230 --> 00:26:47,830 aber soweit ich mich erinnere, ist es so etwas wie, wenn Ich n minus 1 Dinge, dann n minus 753 00:26:47,830 --> 00:26:53,570 2, dann n minus 3, es ist etwa etwas mehr als 2, und wenn ich 754 00:26:53,570 --> 00:26:55,510 multiplizieren Sie diese aus, ist das tatsächlich n Platz. 755 00:26:55,510 --> 00:26:58,940 Das fühlt sich nicht so gut. n minus n über 2. 756 00:26:58,940 --> 00:27:00,350 >> Aber hier ist das Ding. 757 00:27:00,350 --> 00:27:03,720 In der Informatik, wenn die Probleme anfangen, sich interessant ist, wenn n 758 00:27:03,720 --> 00:27:04,700 wird wirklich groß. 759 00:27:04,700 --> 00:27:08,110 Und wenn n wirklich groß wird, welche der diese Werte wird alle dominieren 760 00:27:08,110 --> 00:27:09,750 von den anderen? 761 00:27:09,750 --> 00:27:10,990 Es ist eine Art des n squared, nicht wahr? 762 00:27:10,990 --> 00:27:13,340 Ja, dividiert durch 2 ist ziemlich gut. 763 00:27:13,340 --> 00:27:16,740 Aber wenn du über Milliarden sprechen Stücke von Daten oder Billionen von 764 00:27:16,740 --> 00:27:18,700 Stücke von Daten, OK, so Sie sind doppelt so schnell. 765 00:27:18,700 --> 00:27:22,440 Aber wer kümmert sich wirklich, wenn diese große Zahl, wenn dieser Faktor ist, was bekommt 766 00:27:22,440 --> 00:27:23,040 größer und größer. 767 00:27:23,040 --> 00:27:25,990 Und sicher, es macht mehr ein Unterschied, als dieser Kerl. 768 00:27:25,990 --> 00:27:29,120 Also auch wenn ihr Jungs haben Recht, die zweite Algorithmus, nennen wir es 769 00:27:29,120 --> 00:27:32,970 Auswahl Art ist, in der realen Welt, ein etwas schneller potentiell, denn ich bin 770 00:27:32,970 --> 00:27:35,360 nehmen immer weniger Schritte jeder Zeit. 771 00:27:35,360 --> 00:27:37,340 >> Es ist nicht wirklich grundlegend schneller. 772 00:27:37,340 --> 00:27:41,430 Denn wenn wir tatsächlich spielen dies für große Werte von n, am Ende 773 00:27:41,430 --> 00:27:44,750 der Tag, für n groß genug, ist es immer noch sich fühlen, ziemlich langsam. 774 00:27:44,750 --> 00:27:46,770 Nun, lassen Sie mich ein letzten Pass auf, dass. 775 00:27:46,770 --> 00:27:48,920 Das ist, was ich nennen würde Auswahl sortieren. 776 00:27:48,920 --> 00:27:51,040 Könnt ihr euch zurück ein letztes Mal? 777 00:27:51,040 --> 00:27:53,550 Und in diesem letzten Fall, ich werde etwas vorschlagen 778 00:27:53,550 --> 00:27:54,970 genannt insertion sort. 779 00:27:54,970 --> 00:27:57,470 Insertion sort ist, konzeptionell, ein bisschen anders. 780 00:27:57,470 --> 00:28:00,980 >> Anstatt sich hin und her und Auswahl der kleinste Element, ich bin 781 00:28:00,980 --> 00:28:05,030 gerade dabei, mit jedem von ihnen umzugehen Jungs, wie ich sie begegnen, und setzen Sie 782 00:28:05,030 --> 00:28:06,850 sie in ihren richtigen Platz. 783 00:28:06,850 --> 00:28:10,160 Also ich bin gerade dabei, mit der Gnade zu starten, und ich sehe, dass sie die Nummer vier ist. 784 00:28:10,160 --> 00:28:11,720 Woher kommt Nummer vier gehören? 785 00:28:11,720 --> 00:28:14,940 Ich habe noch nicht begonnen Sortierung nichts, so Gnade bekommt Recht dort zu bleiben. 786 00:28:14,940 --> 00:28:18,355 Und jetzt werde ich Anspruch, wenn du könntest einen Schritt nach rechts, diese 787 00:28:18,355 --> 00:28:21,650 meine sortierten Liste, dies ist mein unsortiert verbleibenden Liste. 788 00:28:21,650 --> 00:28:23,260 So, jetzt werde ich zum nächsten gehen, und was ist Ihr Name? 789 00:28:23,260 --> 00:28:23,700 >> Branson: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 So Branson ist Nummer zwei. 792 00:28:25,375 --> 00:28:27,490 Also werde ich Ihnen nehmen für einen Moment. 793 00:28:27,490 --> 00:28:30,940 Und jetzt, wo Sie hingehören in diesem Array? 794 00:28:30,940 --> 00:28:32,360 Also auf der rechten Seite von Grace. 795 00:28:32,360 --> 00:28:35,670 Also noch einmal, wir sind Art der Herstellung Anmut tun eine Menge Arbeit hier. 796 00:28:35,670 --> 00:28:37,290 Wo setzen wir Sie? 797 00:28:37,290 --> 00:28:40,120 So werden wir Sie zu der Folie links, und legen Sie es Branson. 798 00:28:40,120 --> 00:28:41,680 Aber jetzt habe ich behaupten, dass Sie Kerle sind fertig. 799 00:28:41,680 --> 00:28:43,240 Aber beachten Sie, ich bin nicht mit zusätzlichen Platz. 800 00:28:43,240 --> 00:28:45,130 Es ist immer noch 2 Elemente hier 5 hier. 801 00:28:45,130 --> 00:28:47,910 Insgesamt Array-Größe ist 7, also bin ich nicht betrügen, alles in Ordnung? 802 00:28:47,910 --> 00:28:51,950 >> So, jetzt haben wir mit Gabe hier die Nummer sechs, wo gehörst du? 803 00:28:51,950 --> 00:28:52,650 Sie haben wieder Glück. 804 00:28:52,650 --> 00:28:53,820 So erhalten Sie nach rechts dort zu bleiben. 805 00:28:53,820 --> 00:28:57,210 Man braucht nur einen leichten Schritt nach rechts nur deutlich machen, dass Sie sortiert sind. 806 00:28:57,210 --> 00:29:00,520 Und jetzt haben wir wieder Neil, Anzahl ein, wo soll man gehen? 807 00:29:00,520 --> 00:29:03,540 Und jetzt, wo wir beginnen werde, das zu sehen Dieser Algorithmus, wenn auf den ersten 808 00:29:03,540 --> 00:29:05,950 Blick, fühlt sich ziemlich smart, beobachten was zu geschehen. 809 00:29:05,950 --> 00:29:07,370 Wenn man einen Schritt vorwärts. 810 00:29:07,370 --> 00:29:09,260 >> Wo wollen wir Neil setzen? 811 00:29:09,260 --> 00:29:11,830 So offensichtlich hier, so wie bekommen wir Neil dort? 812 00:29:11,830 --> 00:29:12,970 Lassen Sie uns diesen Schritt-für-Schritt. 813 00:29:12,970 --> 00:29:15,620 Gabe, wo Sie brauchen, um zu gehen? 814 00:29:15,620 --> 00:29:19,590 Yep, so nehmen Sie einen großen Schritt, oder zwei halbe Schritte, um 815 00:29:19,590 --> 00:29:20,820 einen Schritt drüben. 816 00:29:20,820 --> 00:29:21,750 Anmut, wohin du gehst? 817 00:29:21,750 --> 00:29:22,510 Gut. 818 00:29:22,510 --> 00:29:23,500 Also ein weiterer Schritt. 819 00:29:23,500 --> 00:29:24,960 Und schließlich Branson? 820 00:29:24,960 --> 00:29:25,460 Ein weiterer Schritt. 821 00:29:25,460 --> 00:29:27,190 Und jetzt können wir Neil in Position gebracht. 822 00:29:27,190 --> 00:29:28,440 >> So, jetzt, weiterhin diese Logik. 823 00:29:28,440 --> 00:29:32,420 Auch wenn wir nicht verschieben Neil über und über und über, um ihn legte 824 00:29:32,420 --> 00:29:36,420 wo er geht im schlimmsten Fall die nächste Zahl, die wir stoßen könnten konnte 825 00:29:36,420 --> 00:29:42,220 werden die Zahl, sagen wir, hat es einige Null ist, dann werden wir alle zu verschieben 826 00:29:42,220 --> 00:29:42,730 diese Jungs. 827 00:29:42,730 --> 00:29:44,950 Angenommen, es gibt eine Reihe, negativ ein, dann müssen wir verschieben 828 00:29:44,950 --> 00:29:46,080 all diese Jungs. 829 00:29:46,080 --> 00:29:48,500 Also wir sind wirklich nur irgendwie Spiegeln das Problem herum, so dass wir 830 00:29:48,500 --> 00:29:52,620 Übertragung der Kosten von der Auswahlverfahren so das Einsetzen 831 00:29:52,620 --> 00:29:56,930 Prozess, so dass Sie Jungs hatten gerade auf rund minus n etwas bewegen 832 00:29:56,930 --> 00:29:57,940 Anzahl der Schritte. 833 00:29:57,940 --> 00:30:01,200 Und diese Zahl der Schritte ist nur noch zu erhöhen, wie ich mehr Nummern wählen, 834 00:30:01,200 --> 00:30:04,730 wenn ich zu halten schubsen euch Rücken-und Rückseite, und zurück. 835 00:30:04,730 --> 00:30:08,320 >> So die traurige Sache ist jetzt all diese Algorithmen sind n quadriert. 836 00:30:08,320 --> 00:30:10,570 Lassen Sie uns fortfahren und diese dank Jungs, und visualisieren diese ein bisschen 837 00:30:10,570 --> 00:30:11,090 anders. 838 00:30:11,090 --> 00:30:12,312 Sehr gut gemacht. 839 00:30:12,312 --> 00:30:14,120 >> [Applaus] 840 00:30:14,120 --> 00:30:15,030 >> In Ordnung. 841 00:30:15,030 --> 00:30:16,280 Dort gehen Sie. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Vielen Dank für die - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [unverständlich] halten die Zahlen. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Nein, Sie können halten die Zahlen als gut. 846 00:30:21,990 --> 00:30:23,440 In Ordnung. 847 00:30:23,440 --> 00:30:24,100 Schön gemacht. 848 00:30:24,100 --> 00:30:25,300 In Ordnung. 849 00:30:25,300 --> 00:30:30,510 Also lasst uns sehen, ob wir jetzt nicht zusammenfassen können schneller und mehr visuell, 850 00:30:30,510 --> 00:30:33,410 genau das, was gerade passiert ist hier wie folgt. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Ich werde weitermachen und ziehen Sie Firefox. 853 00:30:38,770 --> 00:30:41,310 Wir verknüpfen diese Demonstration Auf dem Kurs auf der Website. 854 00:30:41,310 --> 00:30:43,870 Java ist ein bisschen ärgerlich zu bekommen arbeiten in einigen Browsern in diesen Tagen. 855 00:30:43,870 --> 00:30:46,760 Also, wenn Sie mit diesem zu Hause nicht spielen, erkennen, müssen Sie möglicherweise Firefox nutzen 856 00:30:46,760 --> 00:30:47,990 um es arbeiten. 857 00:30:47,990 --> 00:30:50,440 Und was ich damit zu tun Demonstration ist die folgende. 858 00:30:50,440 --> 00:30:54,875 >> Am Boden habe ich eine ganze Reihe von Menü-Optionen, einschließlich einer Start-und einer 859 00:30:54,875 --> 00:30:55,840 Stopp-Taste. 860 00:30:55,840 --> 00:30:59,450 Auch als beiseite, es scheint eine sein Fehler in diesen Programmen, wobei Sie 861 00:30:59,450 --> 00:31:03,720 kann nicht wirklich sehen, die Start-oder Stopp Taste, wenn Sie halten Befehl oder Alt 862 00:31:03,720 --> 00:31:06,560 Plus-und Zoom-in, die neugierig zeigt Ihnen weitere Schaltflächen. 863 00:31:06,560 --> 00:31:09,090 Also nur, wenn Sie spielen FYI mit diesem zu Hause. 864 00:31:09,090 --> 00:31:12,870 Jetzt werde ich zu Beginn in nur einem Klick Moment, nach Angabe einer Verzögerung von 865 00:31:12,870 --> 00:31:16,810 wie, 200 Millisekunden hier, nur so können wir sehen, was passiert. 866 00:31:16,810 --> 00:31:20,180 >> Also ich behaupte, dass dies eine Visualisierung der erste Algorithmus 867 00:31:20,180 --> 00:31:23,730 diese Jungs haben, bubble sort, wobei tauschten wir Menschen paarweise. 868 00:31:23,730 --> 00:31:27,490 Der Schlüssel zu dieser Einsicht Visualisierung ist, dass die Höhe der Balken 869 00:31:27,490 --> 00:31:30,510 stellt die Größe der Zahl. 870 00:31:30,510 --> 00:31:32,210 Also das größer der Balken, desto Je größer die Zahl. 871 00:31:32,210 --> 00:31:33,680 Kürzer der Balken, je kleiner die Anzahl. 872 00:31:33,680 --> 00:31:38,630 Und wenn Sie feststellen, wir durchmachen Die erste Iteration des Algorithmus, 873 00:31:38,630 --> 00:31:42,620 Swapping große und kleine Zahlen, so dass die geringe Zahl an erster Stelle und 874 00:31:42,620 --> 00:31:44,280 die große Zahl geht nach rechts. 875 00:31:44,280 --> 00:31:48,770 >> Und sobald wir das Ende des Feldes zu bekommen viele mehr Zahlen als sieben sind wir 876 00:31:48,770 --> 00:31:49,900 werde gehen zurück an den Anfang. 877 00:31:49,900 --> 00:31:51,140 Und diese erwarten. 878 00:31:51,140 --> 00:31:54,860 Ganz links, ist, dass kleine Kerl los auf die Seite wechseln, und das 879 00:31:54,860 --> 00:31:56,010 Prozess wiederholt. 880 00:31:56,010 --> 00:31:59,450 Nun ist diese Visualisierung schnell bekommt langweilig, so lassen Sie mich gehen Sie vor und stoppen 881 00:31:59,450 --> 00:32:04,170 es, die Verzögerung etwas viel schneller, nur um jetzt bekommen, ein Gefühl für 882 00:32:04,170 --> 00:32:05,060 Dieser Algorithmus. 883 00:32:05,060 --> 00:32:07,840 >> Also obwohl ich raste es auf, ist dies wie mein Prozessor Upgrade, Kauf 884 00:32:07,840 --> 00:32:08,580 einen neuen Computer. 885 00:32:08,580 --> 00:32:12,980 Ich habe nicht grundlegend verändert meine Algorithmus, aber man kann in der Tat mehr sehen 886 00:32:12,980 --> 00:32:16,800 Deutlicher als mit den Menschen, dass die große Zahlen sprudeln bis an die Spitze, 887 00:32:16,800 --> 00:32:20,900 und die kleinen Zahlen sprudeln bis auf den Boden. 888 00:32:20,900 --> 00:32:22,390 Und jetzt diese Sache hier sortiert. 889 00:32:22,390 --> 00:32:25,260 Und so nebenbei, auf den Plätzen, gibt es nur einige Buchhaltung dort 890 00:32:25,260 --> 00:32:28,010 Sie zählen, wie viele Vergleiche, oder wie viele Swaps 891 00:32:28,010 --> 00:32:28,950 tatsächlich getan. 892 00:32:28,950 --> 00:32:30,750 >> Nun, lasst uns versuchen, eine die andere, die wir gesehen haben. 893 00:32:30,750 --> 00:32:37,116 Lassen Sie mich auf Bubble-Sort klicken Sie hier, und lassen Sie mich wählen, und diese ganze Web-Seite 894 00:32:37,116 --> 00:32:38,936 ist ein wenig buggy. 895 00:32:38,936 --> 00:32:41,155 Lassen Sie übernehmen das Risiko und führen Sie es erneut. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Dort gehen wir. 898 00:32:45,030 --> 00:32:47,180 So lasst uns Auswahl sortieren. 899 00:32:47,180 --> 00:32:49,140 Ich weiß nicht, warum das Menü erscheint da drüben. 900 00:32:49,140 --> 00:32:54,070 Lasst uns vergrößern, um das zu beheben bug, ändern Sie dies in 50. 901 00:32:54,070 --> 00:32:56,020 Ah, wir tatsächlich tun die viel schneller. 902 00:32:56,020 --> 00:32:59,160 Fünf Millisekunden oder so, und tauschen. 903 00:32:59,160 --> 00:33:00,470 >> Das ist also Auswahl sortieren. 904 00:33:00,470 --> 00:33:03,070 Also noch einmal, über das, was wir denken, tat mit den Menschen hier oben. 905 00:33:03,070 --> 00:33:08,490 Wir gingen durch die Anordnung und Auswahl das kleinste Element wieder 906 00:33:08,490 --> 00:33:09,250 und wieder, und wieder. 907 00:33:09,250 --> 00:33:11,110 Jetzt habe ich behaupten, dass war immer noch ziemlich schlecht. 908 00:33:11,110 --> 00:33:15,010 Es war immer noch n squared, geben oder nehmen, aber es war, in der realen Welt, ein bisschen 909 00:33:15,010 --> 00:33:18,280 schneller, weil ich in der Tat nahm etwas weniger Schritte jeder Zeit. 910 00:33:18,280 --> 00:33:19,800 Aber wir reden nur was? 911 00:33:19,800 --> 00:33:21,830 Vielleicht 40 oder so Bars hier? 912 00:33:21,830 --> 00:33:23,200 Wir reden hier nicht 40 Millionen. 913 00:33:23,200 --> 00:33:27,430 So ist es nicht ganz mir klar, dass war in der Tat eine erhebliche Verstärkung. 914 00:33:27,430 --> 00:33:32,530 >> Lassen Sie mich nun zurück und ändern unseren dritten Algorithmus, der wurde wählen 915 00:33:32,530 --> 00:33:33,180 insertion sort. 916 00:33:33,180 --> 00:33:36,380 Und jetzt ist es wirklich buggy, weil die Menü sollte wirklich nicht sein da unten. 917 00:33:36,380 --> 00:33:40,840 So, jetzt werden wir wieder hier oben scrollen und starten Sie diesen Algorithmus. 918 00:33:40,840 --> 00:33:43,270 Whoop, starten und stoppen. 919 00:33:43,270 --> 00:33:47,160 Also das eine Art hat ein hübsches Muster zu, wobei wir wieder 920 00:33:47,160 --> 00:33:50,240 Einsetzen der Menschen, oder in In diesem Fall die Stäbe in 921 00:33:50,240 --> 00:33:52,620 ihren geeigneten Platz. 922 00:33:52,620 --> 00:33:55,430 Und es ist schon getan, bevor Ich drehte mich um. 923 00:33:55,430 --> 00:33:58,940 Aber auch dieser in der Theorie, noch n quadriert. 924 00:33:58,940 --> 00:34:01,430 >> Also lasst uns sehen, ob wir nicht fassen diese wie folgt. 925 00:34:01,430 --> 00:34:04,750 Ich werde weitermachen und nur, um uns eine Art gemeinsame Art zu reden 926 00:34:04,750 --> 00:34:08,489 über diese Dinge, möchte ich mich vorstellen nur ein bisschen Notation hier. 927 00:34:08,489 --> 00:34:12,480 Sie sind im Begriff, etwas zu sehen als große O, denn es ist buchstäblich ein großes 928 00:34:12,480 --> 00:34:16,320 O. Und dies ist ein Weg, dass ein Computer Wissenschaftler oder ein Mathematiker benutzt sogar 929 00:34:16,320 --> 00:34:19,230 die Laufzeit beschreiben einiger Algorithmus. 930 00:34:19,230 --> 00:34:21,400 Wie viele Stufen hat es tatsächlich? 931 00:34:21,400 --> 00:34:25,080 >> Jetzt werde ich mich mit Verlegenheit meine Handschrift hier in nur einem Augenblick. 932 00:34:25,080 --> 00:34:29,020 Aber lassen Sie mich gehen und sagen, dass Dies wird große O hier sein. 933 00:34:29,020 --> 00:34:33,610 Und lassen Sie mich Ihnen eine andere Symbol, ein Kapital Omega. 934 00:34:33,610 --> 00:34:37,080 Omega wird das Gegenteil sein, Wesentlichen von großen O. in der Erwägung big O 935 00:34:37,080 --> 00:34:40,790 Mittel, im schlimmsten Fall, wie viel Zeit könnten einige Algorithmus zu nehmen, in 936 00:34:40,790 --> 00:34:43,480 Abhängigkeit von n, wird Omega zu gehen sein, wie viel Zeit könnte es 937 00:34:43,480 --> 00:34:45,409 nehmen im besten Fall. 938 00:34:45,409 --> 00:34:48,090 Und wir werden sehen, was wir unter besten Fall in nur einem Augenblick. 939 00:34:48,090 --> 00:34:49,940 >> Also fangen wir etwas einfach. 940 00:34:49,940 --> 00:34:54,719 Lassen Sie mich mit einer linearen Suche zu starten. 941 00:34:54,719 --> 00:34:55,679 Also nicht sorting. 942 00:34:55,679 --> 00:34:58,000 Wir nennen diese lineare Suche. 943 00:34:58,000 --> 00:35:01,140 Und jetzt, machen ein wenig Tabelle raus. 944 00:35:01,140 --> 00:35:06,600 Und jetzt, im Fall der linearen Suche, im schlimmsten Fall, wie viele Schritte ist 945 00:35:06,600 --> 00:35:11,770 es geht um mich zu treffen, um eine zu finden Anzahl der Willkür? 946 00:35:11,770 --> 00:35:14,540 Und es gibt n insgesamt Türen oder n Gesamtzahlen. 947 00:35:14,540 --> 00:35:15,940 Worst case. 948 00:35:15,940 --> 00:35:18,800 Wie viele Schritte ich gehen zu müssen, ergreifen, um die Zahl 50 in einem Array finden 949 00:35:18,800 --> 00:35:20,830 von n Türen? 950 00:35:20,830 --> 00:35:21,410 Und warum? 951 00:35:21,410 --> 00:35:23,680 Da könnte es die ganze Weg über auf das Ende. 952 00:35:23,680 --> 00:35:27,120 So viel wie Jennifer angetroffen, die Nummer 50 war den ganzen Weg über, so in 953 00:35:27,120 --> 00:35:30,760 im schlimmsten Fall lineare Suche ist groß O von n, wir sagen. 954 00:35:30,760 --> 00:35:33,430 >> Was ist mit dem besten Fall wenn Sie wirklich Glück haben? 955 00:35:33,430 --> 00:35:36,200 Es ist gerade dabei, einen Schritt zu tun, oder eine konstante Anzahl von Schritten. 956 00:35:36,200 --> 00:35:37,830 Also werden wir, dass 1 zu beschreiben. 957 00:35:37,830 --> 00:35:39,010 Also das ist ziemlich gut. 958 00:35:39,010 --> 00:35:41,210 Was nun, wenn wir etwas mag binäre Suche? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 So binäre Suche im schlimmsten Fall hat, wie viel Zeit? 961 00:35:47,846 --> 00:35:49,250 >> [Zwischenschaltung VOICES] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Also eigentlich habe ich gehört, dass es in ein paar Plätze. 963 00:35:51,310 --> 00:35:56,390 So ist es tatsächlich einloggen n, geben oder nehmen, denn wie wir teilen die Liste in zwei Hälften 964 00:35:56,390 --> 00:36:00,730 wieder und wieder, und wieder, sind wir in der Lage um letztlich der Wert, 965 00:36:00,730 --> 00:36:04,750 wenn es da ist, aber es gibt einen Haken. 966 00:36:04,750 --> 00:36:08,590 Was ist in der Annahme, dass wir zu haben nehmen für gewährt für binäre Suche? 967 00:36:08,590 --> 00:36:09,700 Es muss sortiert werden. 968 00:36:09,700 --> 00:36:12,770 Es ist nicht sortiert ist, können Sie spalten das Ding in Hälfte wieder und wieder, und Sie 969 00:36:12,770 --> 00:36:15,490 können gehen Sie nach links, und Sie können gehen Sie nach rechts und Sie gehen links und rechts, aber du bist 970 00:36:15,490 --> 00:36:18,070 nicht, um das Element zu finden, wenn die Liste nicht sortiert ist, weil 971 00:36:18,070 --> 00:36:18,790 Sie könnten verpassen. 972 00:36:18,790 --> 00:36:22,120 Weil Ihre Heuristik für den Gang links oder rechts wird fehlerhaft, wenn es sein 973 00:36:22,120 --> 00:36:23,420 Tat nicht sortiert. 974 00:36:23,420 --> 00:36:26,110 So gibt es eine Art von versteckten Kosten um mit so etwas wie dies. 975 00:36:26,110 --> 00:36:29,250 >> Lassen Sie uns nun in unsere Sortier gehen Algorithmen nicht auf der Suche - 976 00:36:29,250 --> 00:36:31,140 oh, eigentlich wollen wir in dieser leeren gehen. 977 00:36:31,140 --> 00:36:33,190 Binäre Suche im besten Fall? 978 00:36:33,190 --> 00:36:36,290 Es ist auch ein, wenn es passiert, nur um genau in der Mitte des Arrays oder 979 00:36:36,290 --> 00:36:37,810 in der Mitte des Telefonbuchs. 980 00:36:37,810 --> 00:36:39,710 Jetzt lasst uns bubble sort. 981 00:36:39,710 --> 00:36:42,570 Also noch einmal, jetzt betreten wir die Sorten, die nicht durchsucht. 982 00:36:42,570 --> 00:36:47,220 >> Im schlimmsten Fall hat, wie viele Schritte, die wir Anspruch bubble sort wird dauern? 983 00:36:47,220 --> 00:36:48,410 n straffte. 984 00:36:48,410 --> 00:36:49,200 Also ich werde das machen. 985 00:36:49,200 --> 00:36:51,710 Ooh, sieht meine Handschrift noch schlimmer wenn es projiziert, dass groß. 986 00:36:51,710 --> 00:36:52,510 In Ordnung. 987 00:36:52,510 --> 00:36:53,570 Also das ist n Quadrat. 988 00:36:53,570 --> 00:36:59,460 Und im besten Fall von Bubble Sort, wie viele Schritte wird es dauern? 989 00:36:59,460 --> 00:37:00,980 1, hörte ich. 990 00:37:00,980 --> 00:37:01,760 >> Sprecher 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, hörte ich. 992 00:37:03,286 --> 00:37:04,200 >> Sprecher 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, hörte ich. 994 00:37:05,010 --> 00:37:06,670 Höre ich 3? 995 00:37:06,670 --> 00:37:07,080 In Ordnung. 996 00:37:07,080 --> 00:37:11,390 Also ich habe gehört, 1, n, 2, aber wir holen Neben wenigstens der erste der 997 00:37:11,390 --> 00:37:12,330 Anregungen, 1. 998 00:37:12,330 --> 00:37:15,370 Es ist kein schlechter Instinkt, weil es Art folgt hier ein Muster. 999 00:37:15,370 --> 00:37:19,670 Aber wenn es dauert nur 1 Schritt, wie in der Welt könnte ich behaupten, dass die Liste 1000 00:37:19,670 --> 00:37:22,900 sortiert ist, denn wenn ich nur ich darf 1 Schritt, wie viele Elemente nehmen 1001 00:37:22,900 --> 00:37:25,230 konnte ich tatsächlich überprüfen um sicher zu sein? 1002 00:37:25,230 --> 00:37:28,270 Nun, nur 1, was bedeutet, es gibt n minus 1 Elemente das könnte aus 1003 00:37:28,270 --> 00:37:31,310 Ordnung, und ich werde einfach auf den Glauben nach Blick auf ein Element, dass die 1004 00:37:31,310 --> 00:37:31,850 Sache sortiert ist. 1005 00:37:31,850 --> 00:37:33,930 Also 1 ist hier nicht zu korrigieren. 1006 00:37:33,930 --> 00:37:35,710 So minimal, wie viele muss ich schauen? 1007 00:37:35,710 --> 00:37:36,680 >> [Zwischenschaltung VOICES] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n minus 1, oder wirklich, n, da muss ich bei jedem Blick 1009 00:37:40,160 --> 00:37:42,190 Element, um sicherzustellen, dass es ist nicht in Ordnung. 1010 00:37:42,190 --> 00:37:44,750 Aber noch einmal, wir von unserer Welle sortieren Hände an den kleineren Zahlen und 1011 00:37:44,750 --> 00:37:47,100 davon ausgehen, dass, wenn n groß wird, sind sie uninteressant sowieso. 1012 00:37:47,100 --> 00:37:48,380 Also das ist, bubble sort. 1013 00:37:48,380 --> 00:37:49,830 Und jetzt lasst uns diese letzten zwei. 1014 00:37:49,830 --> 00:37:53,520 Auswahl sortieren und dann werden wir tun insertion sort. 1015 00:37:53,520 --> 00:37:57,160 Und dann werden wir blow your Köpfe mit etwas viel 1016 00:37:57,160 --> 00:37:58,926 besser als alle diese. 1017 00:37:58,926 --> 00:38:00,410 In Ordnung. 1018 00:38:00,410 --> 00:38:04,700 >> Was ist der schlimmste Fall läuft Zeitpunkt der Auswahl sortieren? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n Quadrat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n Platz, ich hörte. 1021 00:38:06,710 --> 00:38:09,790 Aber warum n straffte, intuitiv? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Weil wir es einfach getan. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Weil wir es einfach getan. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Gute Antwort. 1026 00:38:13,380 --> 00:38:16,660 Aber intuitiv, warum ist die Auswahl sort n squared? 1027 00:38:16,660 --> 00:38:18,980 Was haben wir zu tun haben, immer und immer wieder? 1028 00:38:18,980 --> 00:38:22,570 Wir hatten zu halten Scannen durch, sind Sie die kleinste, Sie sind der 1029 00:38:22,570 --> 00:38:24,020 kleinste, Sie sind die kleinste. 1030 00:38:24,020 --> 00:38:27,480 Und selbstverständlich waren wir in der Lage, n nehmen Schritte, dann n minus 1, dann n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Aber wenn Sie Art fügen sie die alle auf, oder nehmen Sie es auf den Glauben, dass ich aufgenommen 1032 00:38:30,700 --> 00:38:34,810 ihnen im Voraus, erhalten wir etwa n Quadrat minus einigen kleineren Zahlen. 1033 00:38:34,810 --> 00:38:36,730 So werde ich nennen diese n Quadrat. 1034 00:38:36,730 --> 00:38:39,530 Aber mit der Auswahl in der besten Art Fall, wie viele Schritte ist es 1035 00:38:39,530 --> 00:38:40,632 werde mir nehmen? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [unverständlich] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Es ist leider noch n squared, nicht wahr? 1038 00:38:44,350 --> 00:38:49,590 Denn wenn ich die Auswahl des kleinsten Element, und wir hatten sieben Leute hier, 1039 00:38:49,590 --> 00:38:53,280 Ich weiß nur, sobald ich auf die sehr Ende, dass ich die kleinsten gefunden 1040 00:38:53,280 --> 00:38:55,670 Nummer, wo immer er oder sie gewesen sein mag. 1041 00:38:55,670 --> 00:38:58,820 Aber wie finde ich den nächsten kleinste Zahl? 1042 00:38:58,820 --> 00:39:00,160 Ich habe einen anderen Pass zu tun. 1043 00:39:00,160 --> 00:39:04,810 Also im besten Fall, was ist das Eingang zur Auswahl sortieren? 1044 00:39:04,810 --> 00:39:07,830 Es ist eine Art Liste bereits, die Nummer eins, Nummer zwei, Nummer drei, Nummer vier. 1045 00:39:07,830 --> 00:39:08,600 Aber ich bin ein Computer. 1046 00:39:08,600 --> 00:39:10,190 Ich kann nur auf einen Blick Sache zu einer Zeit. 1047 00:39:10,190 --> 00:39:12,465 Ich kann nicht irgendwie einen Schritt zurück wie ein Mensch und sagen: 1048 00:39:12,465 --> 00:39:14,030 ooh, das sieht richtig. 1049 00:39:14,030 --> 00:39:17,580 >> Ich kann nur entscheiden Korrektheit in Auswahl sortieren, indem Sie die 1050 00:39:17,580 --> 00:39:18,370 wenigsten. 1051 00:39:18,370 --> 00:39:21,390 Aber selbst wenn ich die Nummer eins erste, wenn ich weiß gar nichts anderes über 1052 00:39:21,390 --> 00:39:24,460 die anderen Zahlen, die ich nicht tun, alles, was ich wissen, dass ich schon immer ein Array übergeben 1053 00:39:24,460 --> 00:39:27,930 oder ein Satz von Türen, dahinter Zahlen, der einzige Weg, ich weiß, dass man 1054 00:39:27,930 --> 00:39:28,680 war der kleinste? 1055 00:39:28,680 --> 00:39:32,440 Wenn ich den ganzen Weg hierher und zu realisieren, verdammt, war man in der Tat die kleinste. 1056 00:39:32,440 --> 00:39:34,870 >> Aber wie kann ich dann feststellen, dass zwei ist die nächste kleinste? 1057 00:39:34,870 --> 00:39:38,350 Durch die gleiche Ineffizienz wieder und wieder. 1058 00:39:38,350 --> 00:39:42,210 So endlich, mit Insertion Sort, wie im schlimmsten Fall 1059 00:39:42,210 --> 00:39:44,990 hatten wir sagen, es führt? 1060 00:39:44,990 --> 00:39:49,100 Auch sie ist n Quadrat. 1061 00:39:49,100 --> 00:39:53,020 Und wie wäre es mit dem besten Fall? 1062 00:39:53,020 --> 00:39:56,282 Wir werden, dass als Cliffhanger zu verlassen. 1063 00:39:56,282 --> 00:40:00,090 Wir werden in diesem blank nächsten Zeit zu füllen, aber lassen Sie mich zuerst vor, dass wir 1064 00:40:00,090 --> 00:40:02,620 grundsätzlich besser als alle diese, alles in Ordnung? 1065 00:40:02,620 --> 00:40:05,220 >> Also für sich selbst zu denken, was Einsetzen Art los zu sein. 1066 00:40:05,220 --> 00:40:06,910 Nun, das war nicht sehr dramatisch, weil ich bin der einzige, 1067 00:40:06,910 --> 00:40:08,970 das sah die Änderung. 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 Hier haben wir also eine etwas verschiedenen Demonstration. 1071 00:40:12,615 --> 00:40:16,580 Wenn ich vergrößern hier, sehen Sie, dass auf der linken Seite haben wir bubble sort, in der 1072 00:40:16,580 --> 00:40:20,740 Mitte Auswahl sortieren wir haben, und auf Ganz rechts, haben wir etwas, was wir 1073 00:40:20,740 --> 00:40:23,380 haben noch nicht sah genannt Mergesort. 1074 00:40:23,380 --> 00:40:26,080 Aber bedenken Sie, was wir waren denn hier so weit heute. 1075 00:40:26,080 --> 00:40:29,200 Wenn Jennifer erste kam auf die Bühne, Wir gingen durch die Anordnung von Zahlen 1076 00:40:29,200 --> 00:40:33,750 wieder und wieder, mit linearer Suche, und wir haben lineare Laufzeit, große O 1077 00:40:33,750 --> 00:40:35,100 von n, so zu sprechen. 1078 00:40:35,100 --> 00:40:41,000 >> Wenn wir nun die erste Woche Klasse, wenn wir teilen und zu erobern, 1079 00:40:41,000 --> 00:40:43,740 und wir hatten das Telefonbuch Reißen, und Jennifer, und wir gemeinsam 1080 00:40:43,740 --> 00:40:47,500 genutzt, dass wichtige Erkenntnis, die war wiederholen sich immer und immer wieder durch 1081 00:40:47,500 --> 00:40:50,930 irgendwie wegwerfen, wegwerfen, Wegwerfen, die Hälfte des Problems, oder 1082 00:40:50,930 --> 00:40:55,320 Im Allgemeinen teilt ein Problem in der Hälfte, und dann Behandeln des kleineres Stück 1083 00:40:55,320 --> 00:40:59,630 das Problem als konzeptionell gleichwertig zum anderen, wir irgendwie tat 1084 00:40:59,630 --> 00:41:00,910 grundsätzlich besser. 1085 00:41:00,910 --> 00:41:04,720 Aber mit bubble sort, mit Auswahl Art, mit Insertion Sort, wir haben können 1086 00:41:04,720 --> 00:41:06,560 keine solchen Einsichten, die Jennifer tat. 1087 00:41:06,560 --> 00:41:10,220 Wir ziemlich genau ging zurück und weiter eine ganze Reihe von Zeiten, und wir 1088 00:41:10,220 --> 00:41:12,650 gezwickt Dinge ein wenig, Swapping in dieser Reihenfolge, vielleicht 1089 00:41:12,650 --> 00:41:13,730 Einfügen oder Auswählen. 1090 00:41:13,730 --> 00:41:16,950 Aber am Ende des Tages habe ich eine Menge umständlich zu Fuß hin und her. 1091 00:41:16,950 --> 00:41:21,160 Wir haben nicht wirklich etwas nutzen Smart wie Jennifer mochte Dividieren 1092 00:41:21,160 --> 00:41:22,040 und erobern. 1093 00:41:22,040 --> 00:41:25,620 >> So verschmelzen Art hingegen, die wir wird erst nächste Woche sehen, es geht 1094 00:41:25,620 --> 00:41:29,540 zu nutzen, dass zentrale Idee, indem der Eingang, und dann zu halbieren, und dann 1095 00:41:29,540 --> 00:41:30,580 halbieren und dann halbieren. 1096 00:41:30,580 --> 00:41:34,590 Und bei jeder Iteration der Schleife, Sortieren der linken Hälfte und der rechte 1097 00:41:34,590 --> 00:41:38,200 Hälfte, dann die linke Hälfte der linken Hälfte, und die rechte Hälfte des linken, dann 1098 00:41:38,200 --> 00:41:40,990 die linke Hälfte der rechten Hälfte, und die rechte Hälfte der rechten Hälfte. 1099 00:41:40,990 --> 00:41:42,840 Und immer und immer wieder wiederholen. 1100 00:41:42,840 --> 00:41:46,170 >> So wirst du dies visuell zu sehen, aber diese ist das, was erwartet uns nächste Woche. 1101 00:41:46,170 --> 00:41:49,760 Und überhaupt, wenn wir denken, ein wenig etwas härter an einem solchen Problem. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Wir haben n auf der linken Quadrat, n Quadrat in der Mitte, und n 1104 00:41:57,970 --> 00:41:59,400 einloggen n auf der rechten Seite. 1105 00:41:59,400 --> 00:42:00,590 Also es ist dein richtiger Cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Wir informieren Sie am Montag zu sehen. 1107 00:42:02,040 --> 00:42:05,163 >> [Applaus]