1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Musikwiedergabe] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. MALAN: Dies ist CS50. 5 00:00:12,550 --> 00:00:14,612 Und dies ist der Beginn der dritten Woche. 6 00:00:14,612 --> 00:00:16,820 Also haben wir viele spannende bekam Dinge heute zu decken. 7 00:00:16,820 --> 00:00:20,160 Viele Möglichkeiten für Freiwillige auf die Bühne. 8 00:00:20,160 --> 00:00:22,780 Und letztlich ist heute nicht um Code überhaupt. 9 00:00:22,780 --> 00:00:24,820 Aber es geht um Ideen und es geht darum, Algorithmen, 10 00:00:24,820 --> 00:00:28,420 und tatsächlich bringt wieder einige die Lehren aus der Woche Null gelernt, 11 00:00:28,420 --> 00:00:31,910 bei dem Rückruf, wir führte diese Monstrosität. 12 00:00:31,910 --> 00:00:33,880 Und aufgenommene Kredite Inspiration davon zu starten 13 00:00:33,880 --> 00:00:36,879 zu lösen immer ausgefeilteren Probleme algorithmisch. 14 00:00:36,879 --> 00:00:38,420 Doch zunächst ein paar Ankündigungen. 15 00:00:38,420 --> 00:00:42,020 So einen, wenn Sie möchten, um beizutreten Mitarbeiter CS50 und Klassenkameraden beim Mittagessen 16 00:00:42,020 --> 00:00:44,670 an diesem Freitag, sowohl hier als auch in Cambridge, und in New Haven, 17 00:00:44,670 --> 00:00:48,060 besuchen Sie bitte den Kurs der Website, auf eine URL gefunden werden kann. 18 00:00:48,060 --> 00:00:50,390 Vortrag an diesem Mittwoch wird hier nicht Sanders sein. 19 00:00:50,390 --> 00:00:53,610 Es wird nur online sein, also tune in am CS50-Website, 20 00:00:53,610 --> 00:00:55,850 ob hier in Cambridge oder New Haven als gut. 21 00:00:55,850 --> 00:00:58,110 >> Und dann Problem stellte zwei ist bereits in Ihren Händen. 22 00:00:58,110 --> 00:01:03,067 Wenn Sie sich noch nicht getaucht haben, lassen Sie mich die scharf formulierte Anregung bieten 23 00:01:03,067 --> 00:01:05,150 , dass, vor allem jetzt, da das Problem setzt voraus, 24 00:01:05,150 --> 00:01:08,669 Sie wirklich wollen, jetzt zu beginnen, wenn nicht plantschen ein wenig am Wochenende oder vor 25 00:01:08,669 --> 00:01:10,710 wenn sie zuerst gehen auf Freitags, weil man sonst 26 00:01:10,710 --> 00:01:14,380 finden, dass sie nicht unbedingt immer länger oder schwieriger pro 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Ich glaube, Sie werden feststellen, dass, in Generell neigen sie dazu, grob zu nehmen 29 00:01:17,575 --> 00:01:18,892 rund um dieselbe Zeit. 30 00:01:18,892 --> 00:01:20,850 Aber es hängt auf der Student, und es 31 00:01:20,850 --> 00:01:22,880 ist abhängig von der Denkweise , mit denen man sich ihr nähert. 32 00:01:22,880 --> 00:01:24,910 Aber immer, Sie gehen up gegen einen Wand zu laufen, 33 00:01:24,910 --> 00:01:26,350 und Sie gehen zu treffen sind einige Fehler, und du bist nur 34 00:01:26,350 --> 00:01:27,950 nicht in der Lage zu sein, get over it an einem gewissen Punkt. 35 00:01:27,950 --> 00:01:31,380 Und es ist äußerst wertvoll, um in der Lage sein, um Schritt weg, kommen am nächsten Tag zurück, 36 00:01:31,380 --> 00:01:35,286 gehen Sie zu Bürozeiten, senden Sie am CS50 Diskutieren oder dergleichen, um tatsächlich entsperrt. 37 00:01:35,286 --> 00:01:36,160 So sollte man das im Hinterkopf. 38 00:01:36,160 --> 00:01:40,830 Ab frühestmöglich ist das Beste, was Sie tun können. 39 00:01:40,830 --> 00:01:44,160 Also hier ist, wo wir angefangen haben die Klasse, über in Woche null. 40 00:01:44,160 --> 00:01:47,441 Und wir können eine freiwillige erhalten hier zu helfen, mich Mikrofone finden? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Aufstehen bereits. 43 00:01:48,900 --> 00:01:50,080 Komm auf. 44 00:01:50,080 --> 00:01:53,707 Denke, das ist, wie es geht, um zu arbeiten. 45 00:01:53,707 --> 00:01:54,415 Wie heißen Sie? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 David J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Komm auf. 49 00:01:57,910 --> 00:01:58,619 Nett, dich zu treffen. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Nice to meet you. 51 00:01:59,910 --> 00:02:02,772 David J. MALAN: Und waren Sie hier bei uns in Woche null, natürlich. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: ich war. 53 00:02:03,028 --> 00:02:03,160 Ich war. 54 00:02:03,160 --> 00:02:05,868 >> David J. MALAN: So könnten Sie gehen vor und finden für uns Mike Smith, 55 00:02:05,868 --> 00:02:08,639 so schnell wie möglich? 56 00:02:08,639 --> 00:02:10,639 So schnell, wie Sie können. 57 00:02:10,639 --> 00:02:13,756 Buchstäblich zerreißen das Problem in zwei Hälften, wie Sie benötigen, um. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Ähm. 59 00:02:15,130 --> 00:02:17,380 David J. MALAN: Buchstäblich Reißen, das Problem in zwei Hälften. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Sehr gut. 64 00:02:23,300 --> 00:02:23,700 >> David J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Gut. 66 00:02:24,200 --> 00:02:24,701 Danke. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Sehr gut. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> David J. MALAN: Und nun, Sie beschnitten haben sich 70 00:02:27,610 --> 00:02:29,320 auf die Hälfte der Größe des Problems. 71 00:02:29,320 --> 00:02:31,267 Nun, wir sind bis zu einem Viertel. 72 00:02:31,267 --> 00:02:33,475 Werden Sie aufgepasst auf welcher Seite wir halten? 73 00:02:33,475 --> 00:02:34,405 >> [Lacht] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ja, ich think-- 75 00:02:35,970 --> 00:02:37,594 >> David J. MALAN: Welche Abschnitt sind wir? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Schalldämpfer, so. 77 00:02:39,150 --> 00:02:39,941 >> David J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Aber Mike Smith geht nach Schalldämpfer sein. 79 00:02:42,810 --> 00:02:44,130 Also-- 80 00:02:44,130 --> 00:02:48,180 >> [Lacht] 81 00:02:48,180 --> 00:02:48,742 >> Gut. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Wo sollen wir suchen? 83 00:02:50,200 --> 00:02:52,049 David J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 David J. MALAN: Nun, wir sind in der chirurgischen. 86 00:02:54,760 --> 00:02:57,840 Nun, die Ärzte. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- wir mit echten gehen. 89 00:02:59,856 --> 00:03:00,370 Echt. 90 00:03:00,370 --> 00:03:00,970 >> David J. MALAN: Real. 91 00:03:00,970 --> 00:03:01,470 OK. 92 00:03:01,470 --> 00:03:03,700 Wenn Sie Real. 93 00:03:03,700 --> 00:03:05,250 Nun, der Weg ist Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Auf diese Weise. 95 00:03:06,250 --> 00:03:07,333 >> David J. MALAN: Welche Methode? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Warten. 97 00:03:08,240 --> 00:03:08,790 M ist-- oder? 98 00:03:08,790 --> 00:03:09,110 Wir begannen mit-- 99 00:03:09,110 --> 00:03:10,090 >> David J. MALAN: Ja. 100 00:03:10,090 --> 00:03:10,650 Sie verließ. 101 00:03:10,650 --> 00:03:11,430 Ihr Recht. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ja. 103 00:03:11,710 --> 00:03:13,126 >> David J. MALAN: So Mikes hier. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Was? 105 00:03:13,990 --> 00:03:14,665 >> [Lacht] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Schlechtes Beispiel, Jungs. 108 00:03:18,330 --> 00:03:18,830 Es tut uns leid. 109 00:03:18,830 --> 00:03:21,610 David J. MALAN: Dies wird lehren Sie von Ihrem Stuhl zu springen. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Ich habe dich. 113 00:03:23,390 --> 00:03:24,670 Ich habe dich. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Dies ist-- OK, ich habe Sie. 117 00:03:26,812 --> 00:03:27,520 Smith hier richtig? 118 00:03:27,520 --> 00:03:28,894 >> David J. MALAN: Smith, ich danke Ihnen. 119 00:03:28,894 --> 00:03:30,535 Also werde ich auch in Zukunft bis Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, ja. 121 00:03:30,790 --> 00:03:31,340 Nein nein Nein. 122 00:03:31,340 --> 00:03:31,600 Oh nein. 123 00:03:31,600 --> 00:03:31,940 Das gehört mir. 124 00:03:31,940 --> 00:03:32,580 >> David J. MALAN: Oh, Smith habe Sie. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ja, ich bekam Smith hier richtig. 127 00:03:34,040 --> 00:03:34,700 Tut mir leid, Leute. 128 00:03:34,700 --> 00:03:35,860 Ich dachte, wir Michael-- wurden für Michael suchen. 129 00:03:35,860 --> 00:03:36,550 Es tut uns leid. 130 00:03:36,550 --> 00:03:37,550 >> David J. MALAN: Es ist OK. 131 00:03:37,550 --> 00:03:39,950 In Ordnung, jetzt sind wir in Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini und Söhne. 133 00:03:41,242 --> 00:03:43,158 David J. MALAN: Nur Sie und ich sind in zu diesem Thema. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Finden Sie uns Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Schmied. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> David J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Wir sind in der R für Müll. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Rubbish. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Das wird eine Weile dauern. 143 00:03:52,480 --> 00:03:54,340 >> [Lacht] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 David J. MALAN: Schuhe. 146 00:03:56,720 --> 00:03:58,080 Wir sind in den Schuhen. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Jetzt sind wir gonna-- 148 00:04:00,210 --> 00:04:01,105 >> David J. MALAN: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Lacht] 151 00:04:03,620 --> 00:04:05,440 Oh, das ist großartig. 152 00:04:05,440 --> 00:04:06,910 [Lacht] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> David J. MALAN: Es ist OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, das ist gut. 156 00:04:11,365 --> 00:04:14,425 Ich glaube nicht, ich bin zu gehen haben PSAT Freunde danach. 157 00:04:14,425 --> 00:04:15,300 David J. MALAN: Good. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Ähm, L, M, N, O, P 161 00:04:18,668 --> 00:04:19,459 David J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Lassen Sie uns also reißen diese in zwei Hälften. 163 00:04:21,600 --> 00:04:22,270 Es ist in Ordnung. 164 00:04:22,270 --> 00:04:25,606 Damit endet schlecht trotzdem, weil Mike Smith wird nicht in den Gelben Seiten zu sein. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> David J. MALAN: Nein, es ist OK. 167 00:04:27,140 --> 00:04:28,930 Aber lassen Sie uns so tun, wie er ist auf dieser Seite. 168 00:04:28,930 --> 00:04:33,260 So, jetzt, das Problem nach unten beschnitten habe zu einer Seite, und wir fanden, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [CHEERING] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK danke. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 Das war außergewöhnlich. 175 00:04:43,646 --> 00:04:45,954 Aber es war immer noch schneller als lineare Suche, 176 00:04:45,954 --> 00:04:47,870 wobei Wir starten am Anfang des Buches, 177 00:04:47,870 --> 00:04:51,210 und wir uns auf den Weg von links nach rechts zu bewegen, schließlich auf der Suche nach Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Und so, wenn das Telefonbuch hatte vielleicht 1.000 Seiten, 179 00:04:53,540 --> 00:04:56,300 vielleicht wäre es genommen haben uns 10 oder so page Tränen. 180 00:04:56,300 --> 00:04:59,380 >> Sie können aber genutzt haben berührt eine Annahme 181 00:04:59,380 --> 00:05:03,602 während all das, was zu sagen ist, , dass das Telefonbuch im Vorfeld war das, was? 182 00:05:03,602 --> 00:05:04,310 ZIELGRUPPE: Sortiert. 183 00:05:04,310 --> 00:05:05,000 David J. MALAN: Es sortiert. 184 00:05:05,000 --> 00:05:05,160 Recht? 185 00:05:05,160 --> 00:05:07,909 Es ist alphabetisch sortiert, so daß alle diese Namen und Nummern 186 00:05:07,909 --> 00:05:11,230 werden aus dem A ist, um die sortierten Z ist, und alphabetisch dazwischen. 187 00:05:11,230 --> 00:05:13,100 Aber heute haben wir nun fragen, die Frage, na ja, 188 00:05:13,100 --> 00:05:16,170 Wie hat Verizon oder das Telefon Unternehmen bekommen es in diesem Zustand? 189 00:05:16,170 --> 00:05:19,560 >> Denn es ist eine Sache, zu nutzen, Diese Annahme und deshalb 190 00:05:19,560 --> 00:05:22,570 ein Problem mit einem zu lösen Algorithmus effizienter. 191 00:05:22,570 --> 00:05:24,900 Aber wir haben nie wirklich in Woche null gebeten, nun ja, 192 00:05:24,900 --> 00:05:27,790 wie viel hat es gekostet Verizon oder jemand anderes 193 00:05:27,790 --> 00:05:29,620 , dass die Telefonbuch in sortierter Reihenfolge zu bekommen? 194 00:05:29,620 --> 00:05:29,780 >> Recht? 195 00:05:29,780 --> 00:05:31,529 Es spielt keine Rolle, wenn Nachschlagen Mike Smith 196 00:05:31,529 --> 00:05:35,190 ist super schnell, wenn es dauert Ihnen ein Jahr, um die Seiten zunächst zu sortieren. 197 00:05:35,190 --> 00:05:35,690 Recht? 198 00:05:35,690 --> 00:05:38,620 Genauso gut könnte man nur zu sichten durch eine randomisierte Telefonbuch, 199 00:05:38,620 --> 00:05:40,690 wenn es geht Super zu sein teuer, um sie zu sortieren. 200 00:05:40,690 --> 00:05:42,350 Also, wenn wir einen anderen Freiwilligen haben. 201 00:05:42,350 --> 00:05:46,350 Lassen Sie uns einen Blick hier an wie wir might-- komm up-- how 202 00:05:46,350 --> 00:05:48,100 wir könnten zu sortieren diese gehen. 203 00:05:48,100 --> 00:05:51,990 >> Und wenn Jordan konnte tatsächlich besuchen Sie uns hier oben auf der Bühne. 204 00:05:51,990 --> 00:05:55,100 Kommen Sie für einen Moment. 205 00:05:55,100 --> 00:05:56,359 Wie heißen Sie? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 David J. MALAN: Caroline, komm herauf. 208 00:05:58,691 --> 00:06:02,070 Und Sie verbunden sein werde von mir und Jordanien hier. 209 00:06:02,070 --> 00:06:03,800 Caroline, ich danke Ihnen. 210 00:06:03,800 --> 00:06:04,300 Gut. 211 00:06:04,300 --> 00:06:08,330 Also, was wir hier für haben Caroline ist 26 blaue Bücher 212 00:06:08,330 --> 00:06:10,747 dass FAS verwendet, um zu verwalten bestimmte Abschlussprüfungen. 213 00:06:10,747 --> 00:06:13,330 Diese sind immer hart zu finden, aber was wir vorher getan haben 214 00:06:13,330 --> 00:06:15,800 ist, dass wir jemand den Namen setzen auf der Vorderseite von jedem von diesen, 215 00:06:15,800 --> 00:06:18,133 aber wir haben es einfach durch gehalten dann setzen Sie die vollständigen Namen. 216 00:06:18,133 --> 00:06:22,720 So würden wir die Person mit dem Namen setzen L, D, J, B, den ganzen Weg von A bis Z, 217 00:06:22,720 --> 00:06:24,090 aber sie sind in zufälliger Reihenfolge. 218 00:06:24,090 --> 00:06:26,890 Und so, wenn Sie möchten, sprechen Sie Ihre Weg durch das Problem wie du 219 00:06:26,890 --> 00:06:31,620 es tun, können Sie weitermachen und sortieren diese für uns, von A bis Z. 220 00:06:31,620 --> 00:06:34,070 >> ZIELGRUPPE: OK, so dass L ist wie die Mitte. 221 00:06:34,070 --> 00:06:35,050 C beginnt. 222 00:06:35,050 --> 00:06:42,410 B. J, bevor L. B, F: 223 00:06:42,410 --> 00:06:45,140 >> David J. MALAN: Halten Sie, dass dachte für eine Sekunde. 224 00:06:45,140 --> 00:06:48,910 Denn sonst ist dies nur Sie interessiert, dann mich, und Jordanien. 225 00:06:48,910 --> 00:06:49,724 Da gehen wir. 226 00:06:49,724 --> 00:06:50,640 ZIELGRUPPE: [unverständlich]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 David J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 Was tust du? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M kommt nach O. 231 00:07:01,730 --> 00:07:02,564 >> David J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 David J. MALAN: O, gut. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> David J. MALAN: E, F. Ja. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> David J. MALAN: V, T, U, V. So ist es sieht aus wie du bist making-- weiterzumachen. 238 00:07:10,689 --> 00:07:12,730 Es sieht aus wie Sie machen Ein großer Haufen hierher, 239 00:07:12,730 --> 00:07:13,910 und Art von einem großen Haufen drüben. 240 00:07:13,910 --> 00:07:16,230 So ist die erste Hälfte des Alphabets, zweiten Hälfte des Alphabets. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Gut. 243 00:07:16,960 --> 00:07:19,680 Art der Aufteilung des Problems in zwei. 244 00:07:19,680 --> 00:07:21,771 M, N, X Ja. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 David J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Sie sind also Art von Auswahl sie nacheinander, 248 00:07:25,070 --> 00:07:27,620 setzen sie entweder links oder rechts, oder Z ist los auf dem Boden. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z ist los auf dem Boden. 251 00:07:29,190 --> 00:07:29,360 >> David J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y wird auf dem Boden. 253 00:07:30,920 --> 00:07:31,735 Jetzt können wir X. setzen 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 David J. MALAN: G los gelassen. 256 00:07:33,700 --> 00:07:36,017 S geht rechts. 257 00:07:36,017 --> 00:07:37,642 In Ordnung, A ist den ganzen Weg nach links. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> David J. MALAN: Nun gut. 260 00:07:39,873 --> 00:07:43,260 Wir haben bekommen, B, C W ist da unten los. 261 00:07:43,260 --> 00:07:45,566 In Ordnung, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. MALAN: H, I, J. Gut. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: In der Mitte, ich gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 So, jetzt sind wir zu Art gehen der verschmelzen diese verschiedenen Pfählen. 267 00:07:52,375 --> 00:08:00,730 So A bis C, dann sehe ich D und E und F und G und H und I. Nizza. 268 00:08:00,730 --> 00:08:05,540 J, K, und dann wird dieser Haufen auf den Kopf, aber das ist OK. 269 00:08:05,540 --> 00:08:06,040 Sicher. 270 00:08:06,040 --> 00:08:07,240 Wir können einige Ecken schneiden. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 Und dann müssen wir W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Ja. 274 00:08:11,250 --> 00:08:11,880 >> David J. MALAN: Ausgezeichnet. 275 00:08:11,880 --> 00:08:14,122 Also ein großes Dankeschön an Caroline zum Sortieren dieser. 276 00:08:14,122 --> 00:08:15,030 >> [CHEERING] 277 00:08:15,030 --> 00:08:17,287 >> Danke. 278 00:08:17,287 --> 00:08:18,120 Danke sehr. 279 00:08:18,120 --> 00:08:22,910 So, jetzt betrachten einen Moment lassen wie Caroline ging zu tun, 280 00:08:22,910 --> 00:08:26,040 und was genau wir waren in der Lage, wie wir zu-- 281 00:08:26,040 --> 00:08:28,409 waren in der Lage zu lösen, dass Problem, wenn wir gerade waren 282 00:08:28,409 --> 00:08:29,950 bei einer ganzen Reihe von zufälligen Eingaben. 283 00:08:29,950 --> 00:08:31,610 >> Nun, es sieht aus wie es war ein bisschen wie ein System gibt es? 284 00:08:31,610 --> 00:08:32,110 Recht. 285 00:08:32,110 --> 00:08:34,495 Also die früheren Briefe im Alphabet, sie 286 00:08:34,495 --> 00:08:37,120 war Putting nach links, und die später Buchstaben im Alphabet, 287 00:08:37,120 --> 00:08:38,270 sie wurde in den rechten setzen. 288 00:08:38,270 --> 00:08:40,500 Und sobald sie gefunden einige proximalen Buchstaben, diejenigen, 289 00:08:40,500 --> 00:08:43,124 daß nach rechts nebeneinander, sie würde die in Ordnung zu bringen. 290 00:08:43,124 --> 00:08:46,750 Und so haben wir Art von dieser kleinen hatten Haufen von sortierten Eingänge auftritt. 291 00:08:46,750 --> 00:08:50,540 >> Und das ist also ganz wie, was die meisten von uns Menschen tun würde. 292 00:08:50,540 --> 00:08:53,530 Wir würden eine Art durchforsten sie, und wir würden uns Art einen Mechanismus. 293 00:08:53,530 --> 00:08:56,930 Aber es könnte schwierig sein, zu schreiben it down in einer Formel an sich. 294 00:08:56,930 --> 00:08:59,010 Es fühlte sich ein wenig mehr organische als das. 295 00:08:59,010 --> 00:09:02,560 Also mal sehen, wenn wir können jetzt gebunden das Problem mit weniger Eingängen. 296 00:09:02,560 --> 00:09:05,170 >> Statt 26, lassen Sie uns tun Sie etwas weit weniger 297 00:09:05,170 --> 00:09:09,890 mit nur sagen, sieben, hinter Diese Türen, sozusagen. 298 00:09:09,890 --> 00:09:11,300 Gibt es nur sieben Nummern? 299 00:09:11,300 --> 00:09:15,240 Und wenn das Ziel nun bei Hand ist, um einen Wert zu finden, 300 00:09:15,240 --> 00:09:17,850 mal sehen, wie effizient können wir dabei vorgehen. 301 00:09:17,850 --> 00:09:22,460 Und lassen Sie uns, wenn wir können jetzt sehen, beginnen, einige Zahlen gelten, 302 00:09:22,460 --> 00:09:26,310 oder einige Formeln, mit denen zu beschreiben, die Effizienz unserer Telefonbuch 303 00:09:26,310 --> 00:09:31,060 Algorithmus unserer Prüfung Buch-Algorithmus, und allgemeiner, der Suche nach Informationen. 304 00:09:31,060 --> 00:09:34,770 >> Also, für dieses, lassen Sie mich los, und auf dem Touchscreen hier, 305 00:09:34,770 --> 00:09:41,100 legte einen Web-Browser, hat genau diese sieben Türen. 306 00:09:41,100 --> 00:09:46,670 Und wenn wir einen anderen zu gelangen freiwillig zu über hierher kommen, 307 00:09:46,670 --> 00:09:48,480 Ich habe die gleichen Türen hierher setzen. 308 00:09:48,480 --> 00:09:49,170 Schnell Freiwilligen. 309 00:09:49,170 --> 00:09:51,130 >> Diese one-- Demos gehen ein schneller und schneller jetzt. 310 00:09:51,130 --> 00:09:51,600 Komm runter. 311 00:09:51,600 --> 00:09:52,308 Wie heißen Sie? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> David J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 In Ordnung, Trevor, komm nach unten. 315 00:09:55,770 --> 00:09:59,212 So Trevor hat hier, um sich freiwillig tun ein ähnliches Problem, aber eine, die ist 316 00:09:59,212 --> 00:10:02,170 weniger umfangreich, und das wird , damit wir versuchen nun zu formalisieren 317 00:10:02,170 --> 00:10:03,970 der Prozess zum Sortieren dieser Zahlen. 318 00:10:03,970 --> 00:10:05,500 >> So Trevor, schön dich zu treffen. 319 00:10:05,500 --> 00:10:08,720 Also hier ist ein Array, so zu zu sprechen, eine Liste der sieben Türen. 320 00:10:08,720 --> 00:10:10,327 Gehen Sie weiter und finden Sie uns die Nummer 50. 321 00:10:10,327 --> 00:10:12,410 Und dann, nachdem die Tatsache, Erklären Sie uns, wie Sie es gefunden. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Sollte be-- alles in Ordnung. 324 00:10:20,040 --> 00:10:21,945 Ja, das ist das hier? 325 00:10:21,945 --> 00:10:24,680 UH Oh. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Sie geklickt haben, dass man. 328 00:10:26,680 --> 00:10:28,690 Gut. 329 00:10:28,690 --> 00:10:29,780 >> Und gut. 330 00:10:29,780 --> 00:10:30,970 Jetzt klickten Sie, dass man. 331 00:10:30,970 --> 00:10:34,060 Und lassen Sie mich Ihnen das Mikrofon, so dass Sie es in nur einem Augenblick. 332 00:10:34,060 --> 00:10:37,000 Gehen Sie weiter und klicken Sie auf die nebenan, die Sie beabsichtigen. 333 00:10:37,000 --> 00:10:39,812 Ja gut. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Kann ich unclick einer Tür? 335 00:10:41,020 --> 00:10:42,620 David J. MALAN: Nein, Sie unclick können. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Dieses hier. 338 00:10:43,974 --> 00:10:45,640 David J. MALAN: Wo wollen Sie hin? 339 00:10:45,640 --> 00:10:46,410 Welcher? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Dass man. 341 00:10:47,230 --> 00:10:48,042 >> David J. MALAN: Nein 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Dieses hier. 344 00:10:48,735 --> 00:10:49,020 >> David J. MALAN: Ja. 345 00:10:49,020 --> 00:10:49,700 Das war gut. 346 00:10:49,700 --> 00:10:50,380 Gut. 347 00:10:50,380 --> 00:10:53,900 Also, was war Ihr Algorithmus oder Verfahren, dies zu tun, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Ich ging durch Türen bis ich eine 50. 349 00:10:56,149 --> 00:10:56,940 David J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Excellent-Algorithmus. 351 00:10:58,150 --> 00:10:59,540 So ist das in Ordnung. 352 00:10:59,540 --> 00:11:03,120 Denn in der Tat, wenn ich zeigen, was ist hinter den beiden anderen Türen, was 353 00:11:03,120 --> 00:11:06,954 wir hier finden, ist, dass wir haben nur zufällige Eingabe. 354 00:11:06,954 --> 00:11:08,870 Das war also tatsächlich als gut, wie Sie bekommen konnte. 355 00:11:08,870 --> 00:11:12,509 Und in der Tat, Sie haben besser als erschöpfend Suche das gesamte Array, 356 00:11:12,509 --> 00:11:15,300 denn es wäre wirklich gewesen sein Pech, wenn Sie die Anzahl getroffen hatte 357 00:11:15,300 --> 00:11:16,604 50 im letzten Tür. 358 00:11:16,604 --> 00:11:18,520 Aber was, wenn wir statt hat Ihnen eine Annahme. 359 00:11:18,520 --> 00:11:20,630 Angenommen, ich Art alle diese Türen herum, 360 00:11:20,630 --> 00:11:23,500 so dass Sie die Nummern sortiert diese Zeit, 361 00:11:23,500 --> 00:11:29,730 aber dieses Mal ist es eigentlich a different-- dieses Mal, 362 00:11:29,730 --> 00:11:32,640 es ist eigentlich für Sie sortiert. 363 00:11:32,640 --> 00:11:35,380 Und jetzt das Ziel bei der Hand ist es, die Nummer 50 treffen. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> David J. MALAN: Was ist Ihr Algorithmus sein wird? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Nun, wenn es sortiert, dann ist es entweder gehen 367 00:11:39,628 --> 00:11:42,710 um be-- wenn größten bis zum größten, absteigend, es wird der erste sein, 368 00:11:42,710 --> 00:11:44,751 oder ob es im Gegenteil, es wird die letzte sein. 369 00:11:44,751 --> 00:11:48,897 Also werde ich tippen Sie einfach auf diese Tür, und dann tippen Sie einfach auf die letzte Tür. 370 00:11:48,897 --> 00:11:49,980 David J. MALAN: Ausgezeichnet. 371 00:11:49,980 --> 00:11:50,270 Gut. 372 00:11:50,270 --> 00:11:51,150 So fanden wir die Zahl 50. 373 00:11:51,150 --> 00:11:52,970 So, sobald Sie wusste, sie sortiert wurden, werden wir 374 00:11:52,970 --> 00:11:55,040 konnten diese Annahme zu nutzen. 375 00:11:55,040 --> 00:11:57,040 So dass sie zu viel wie das Telefonbuch Beispiel. 376 00:11:57,040 --> 00:11:59,540 Sobald Sie auch mit haben ein kleines Problem wie dieses, 377 00:11:59,540 --> 00:12:02,380 Ihre Eingaben vorsortiert, können wir tatsächlich den Wert wohl finden 378 00:12:02,380 --> 00:12:03,130 effizienter. 379 00:12:03,130 --> 00:12:05,800 >> Und ich wollte nicht sagen, ob es sortiert klein bis groß oder groß bis klein, 380 00:12:05,800 --> 00:12:08,080 und so war es sehr angemessen an einem Ende oder dem anderen starten 381 00:12:08,080 --> 00:12:09,750 tatsächlich feststellen, dass Sollwert. 382 00:12:09,750 --> 00:12:11,400 Also danke an Trevor auch. 383 00:12:11,400 --> 00:12:13,260 Und ich werde schön gemacht propose--. 384 00:12:13,260 --> 00:12:16,960 Wir haben einen kleinen Clip, eigentlich, daß gehört zu unseren Lieblingsmomente in CS50, 385 00:12:16,960 --> 00:12:19,700 wobei manchmal diese Demos nicht ganz nach Plan. 386 00:12:19,700 --> 00:12:22,050 Und in der Tat gerade jetzt, ich die falsche Schnittstelle gezogen 387 00:12:22,050 --> 00:12:23,508 , mit denen Sie den Touchscreen verwenden. 388 00:12:23,508 --> 00:12:24,660 Das war also meine Schuld gibt. 389 00:12:24,660 --> 00:12:26,600 >> So wird dies für zu machen im nächsten Jahr Clip als 390 00:12:26,600 --> 00:12:28,570 , warum ich Sie auf meiner eigenen Bildschirm. 391 00:12:28,570 --> 00:12:31,390 Aber lassen Sie uns einen kurzen Blick auf das, was im letzten Jahr geschehen ist 392 00:12:31,390 --> 00:12:34,770 mit Jay, der kam, viel wie Trevor hier, freiwillig, 393 00:12:34,770 --> 00:12:39,380 und in diesem kurzen Clip, sehen Sie, wie diese gleichen Demo nicht ganz 394 00:12:39,380 --> 00:12:41,074 offenbaren die gleichen Erfahrungen. 395 00:12:41,074 --> 00:12:41,740 [VIDEO PLAYBACK] 396 00:12:41,740 --> 00:12:45,360 -Alle Ich möchte Sie zu tun ist jetzt für mich zu finden, und für uns, 397 00:12:45,360 --> 00:12:51,674 wirklich, die Zahl 50 ein Schritt auf einmal. 398 00:12:51,674 --> 00:12:52,450 >> -Die Zahl 50? 399 00:12:52,450 --> 00:12:53,190 >> -Die Zahl 50. 400 00:12:53,190 --> 00:12:55,356 Und man kann zeigen, was ist Hinter jeder dieser Türen 401 00:12:55,356 --> 00:12:58,540 einfach durch Berühren mit einem Finger. 402 00:12:58,540 --> 00:13:00,910 Verdammt. 403 00:13:00,910 --> 00:13:02,870 >> [Lacht] 404 00:13:02,870 --> 00:13:03,806 >> [END PLAYBACK] 405 00:13:03,806 --> 00:13:05,430 David J. MALAN: Also, die sehr gut ging. 406 00:13:05,430 --> 00:13:06,796 Das waren die unsortierten Türen. 407 00:13:06,796 --> 00:13:08,670 Jay und, natürlich, fand es viel zu schnell. 408 00:13:08,670 --> 00:13:12,910 Trevor hat eine viel bessere Arbeit in Bezug auf ein Aha-Erlebnis, 409 00:13:12,910 --> 00:13:15,850 so zu sagen, in diesem Jahr in länger dauert, sie zu finden. 410 00:13:15,850 --> 00:13:17,950 Natürlich, dann gaben wir Jay eine zweite Chance, 411 00:13:17,950 --> 00:13:20,320 wobei wir nach die Türen, genauso wie wir für Trevor hat, 412 00:13:20,320 --> 00:13:22,300 und Trevor war super gut diese Zeit. 413 00:13:22,300 --> 00:13:26,124 Aber Jay habe es halb so schnell. 414 00:13:26,124 --> 00:13:26,790 [VIDEO PLAYBACK] 415 00:13:26,790 --> 00:13:29,650 -Das Ziel ist es nun auch finden Sie uns die Nummer 50, 416 00:13:29,650 --> 00:13:33,030 aber tun Sie es algorithmisch und Erklären Sie uns, wie Sie über sie gehst. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -Und Wenn Sie es finden, halten Sie den Film. 419 00:13:35,604 --> 00:13:37,228 Wenn Sie es nicht finden, geben Sie zurück. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Unverständlich] OK. 423 00:13:40,800 --> 00:13:46,236 Also werde ich, um die Enden zu überprüfen zuerst, wenn there's-- um festzustellen, Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applaus] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END PLAYBACK] 427 00:13:55,729 --> 00:13:56,520 David J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 So sortieren Türen deutlich führt zu einer höheren Effizienz. 429 00:13:59,760 --> 00:14:01,680 Und so doppelt so schnell ist das, was ich da gedacht. 430 00:14:01,680 --> 00:14:03,270 Und so Jay hatte Glück beide Male. 431 00:14:03,270 --> 00:14:06,685 Und er hat auch das Glück in diesem letzten Jahr bestellte ich einige Blu-ray Discs 432 00:14:06,685 --> 00:14:07,560 tatsächlich zu geben. 433 00:14:07,560 --> 00:14:09,768 Es tut mir leid wir dieses Jahr hatte nicht die gleichen, Trevor. 434 00:14:09,768 --> 00:14:11,540 Aber noch besser war ein paar Jahre zurück. 435 00:14:11,540 --> 00:14:14,820 Und einige von euch vielleicht wissen Kerl, Sean, der, als er in CS50 war, 436 00:14:14,820 --> 00:14:17,780 wurde mit der genauen fochten gleiche Problem, wenn auch in SD, 437 00:14:17,780 --> 00:14:19,360 wie Sie bald sehen werden, wieder in den Tag. 438 00:14:19,360 --> 00:14:22,622 Und Sie werden feststellen, dass nicht nur er ein wenig länger als Jay zu nehmen, 439 00:14:22,622 --> 00:14:25,580 ein wenig länger als Trevor war es eigentlich diese wunderbare Gelegenheit 440 00:14:25,580 --> 00:14:29,820 zu fast jeder in der Eingriffs Zuschauer A-la-Preis ist, die Förderung 441 00:14:29,820 --> 00:14:31,889 ihm, die Zahl, die wir suchten zu finden. 442 00:14:31,889 --> 00:14:32,930 Lasst uns. wir einen kurzen Blick. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO PLAYBACK] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 So Ihre Aufgabe hier, Sean, ist die folgende. 446 00:14:36,680 --> 00:14:40,860 Ich habe hinter diesen verborgen Türen die Zahl Sieben. 447 00:14:40,860 --> 00:14:45,120 Aber versteckt in einige dieser Türen sowie auch andere negative Zahlen. 448 00:14:45,120 --> 00:14:47,500 Und Ihr Ziel ist zu denken, der oberen Reihe von Zahlen 449 00:14:47,500 --> 00:14:50,390 nur als ein Array, oder einfach nur Sequenz von Papierstücken 450 00:14:50,390 --> 00:14:51,510 mit Zahlen hinter ihnen. 451 00:14:51,510 --> 00:14:55,540 Und Ihr Ziel ist, nur mit dem Top- Array hier finden mir die Nummer sieben. 452 00:14:55,540 --> 00:14:58,570 Und wir werden dann werde Kritik wie Sie es tun. 453 00:14:58,570 --> 00:14:59,070 -Gut. 454 00:14:59,070 --> 00:15:00,850 -Finden Uns die Nummer sieben, bitte. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nein. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Fünf, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Lacht] 461 00:15:24,770 --> 00:15:25,910 >> Es ist nicht eine Fangfrage. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Ein. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Lacht] 466 00:15:34,695 --> 00:15:37,861 An diesem Punkt ist die Punktzahl nicht sehr gut, so dass Sie könnte genauso gut weiterzumachen. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Drei. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Lacht] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Mach weiter. 473 00:15:47,774 --> 00:15:50,690 Ehrlich gesagt, kann ich nicht helfen, aber frage mich, was du überhaupt darüber nachzudenken, SO- 474 00:15:50,690 --> 00:15:51,959 >> [Lacht] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Nur die obere Reihe, so Sie haben drei links bekam. 477 00:15:55,020 --> 00:15:56,200 So finden Sie mich sieben. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Lacht] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Sieben. 484 00:16:26,946 --> 00:16:28,780 >> [Applaus] 485 00:16:28,780 --> 00:16:29,426 >> Gut. 486 00:16:29,426 --> 00:16:30,360 >> [END PLAYBACK] 487 00:16:30,360 --> 00:16:31,840 >> David J. MALAN: so konnten wir Sehen Sie diese den ganzen Tag lang. 488 00:16:31,840 --> 00:16:34,090 Und natürlich einige diesjährigen Demos vielleicht 489 00:16:34,090 --> 00:16:36,330 wird nun am Ende in der nächsten jährigen Video. 490 00:16:36,330 --> 00:16:39,040 So, jetzt wollen wir eigentlich konzentrieren sich auf die Algorithmen 491 00:16:39,040 --> 00:16:42,140 hier, und sehen, ob wir nicht jetzt damit beginnen, zu formalisieren 492 00:16:42,140 --> 00:16:46,650 wie wir darum unsere Daten gehen in diesen Zustand, dass es sortiert, 493 00:16:46,650 --> 00:16:50,054 so dass letztlich, können wir tatsächlich suchen sie effizienter. 494 00:16:50,054 --> 00:16:52,470 Und auch wenn wir gehen um relativ kleine Datenmengen zu verwenden, 495 00:16:52,470 --> 00:16:54,511 wie die acht Zahlen, die wir habe hier auf dem Brett, 496 00:16:54,511 --> 00:16:58,230 letztlich dieselben Ideen gelten könnten 1000 Eingänge, eine Million Eingängen 497 00:16:58,230 --> 00:17:02,100 4 Milliarden Eingänge weil die Algorithmen gehen, um im wesentlichen der gleiche sein. 498 00:17:02,100 --> 00:17:05,359 >> Und dies ist unsere letzte Gelegenheit für die Freiwilligen heute 499 00:17:05,359 --> 00:17:09,790 aber vielleicht die Beteiligten ein, für die wir acht Freiwillige 500 00:17:09,790 --> 00:17:12,960 zu kommen und gehen uns durch die Prozess des Sortierens, was bald 501 00:17:12,960 --> 00:17:15,212 werden auf diese Musik steht hier. 502 00:17:15,212 --> 00:17:16,170 Lassen Sie mich hier starten. 503 00:17:16,170 --> 00:17:19,692 >> So eine in der turquoise-- grün ist das? 504 00:17:19,692 --> 00:17:21,130 Sind Sie zu begehen? 505 00:17:21,130 --> 00:17:21,630 Zwei. 506 00:17:21,630 --> 00:17:23,069 Komm runter. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Drei. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Lassen Sie mich- OK, fünf. 511 00:17:27,247 --> 00:17:28,830 Sie sind von Ihrem Freund nominiert. 512 00:17:28,830 --> 00:17:31,340 Sechs, sieben und acht. 513 00:17:31,340 --> 00:17:32,130 Komm auf. 514 00:17:32,130 --> 00:17:32,630 Gut. 515 00:17:32,630 --> 00:17:33,190 Vielen Dank. 516 00:17:33,190 --> 00:17:33,689 Komm auf. 517 00:17:33,689 --> 00:17:34,790 Komm auf. 518 00:17:34,790 --> 00:17:35,330 >> Gut. 519 00:17:35,330 --> 00:17:38,890 Also, was wir hier-- und dies haben gehört zu den mehr umständlich diejenigen, 520 00:17:38,890 --> 00:17:42,390 da dies Humor verlangen, dass Sie mich nur ein wenig Zeit. 521 00:17:42,390 --> 00:17:43,442 Sie müssen die Nummer eins sein. 522 00:17:43,442 --> 00:17:44,150 Wie heißen Sie? 523 00:17:44,150 --> 00:17:44,610 >> Annan Annan. 524 00:17:44,610 --> 00:17:45,526 >> David J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Wie heißen Sie? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> David J. MALAN: Joseph, Sie sind die Nummer zwei. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, Nummer drei. 530 00:17:52,260 --> 00:17:53,722 Stefan, Nummer vier. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 David J. MALAN: Cynthia, Nummer fünf. 533 00:17:57,548 --> 00:17:58,452 [Unverständlich] 534 00:17:58,452 --> 00:17:59,618 David J. MALAN: [unverständlich]. 535 00:17:59,618 --> 00:18:00,391 David, Nummer sechs. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 David J. MALAN: Matts Nummer sieben. 538 00:18:02,160 --> 00:18:02,850 Und? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> David J. MALAN: Waverly, Nummer acht. 541 00:18:04,470 --> 00:18:04,970 Gut. 542 00:18:04,970 --> 00:18:06,510 Wenn Sie could-- hoppla. 543 00:18:06,510 --> 00:18:08,820 Wenn Sie allen, wie Ihre erste Herausforderung besteht 544 00:18:08,820 --> 00:18:10,820 acht Notenständer hier dem Publikum zugewandt. 545 00:18:10,820 --> 00:18:14,200 Wenn Sie Ihre Zahlen auf setzen könnte Diese Musik steht in der Weise 546 00:18:14,200 --> 00:18:16,560 dass sie eine Linie mit der gleichen Zahlen auf dem Brett. 547 00:18:16,560 --> 00:18:19,560 Also macht euch so aussehen durch setzen Sie Ihre Zahlen auf diese Musik 548 00:18:19,560 --> 00:18:21,960 steht hier. 549 00:18:21,960 --> 00:18:25,980 Ausgezeichnete so weit. 550 00:18:25,980 --> 00:18:26,600 >> Ausgezeichnet. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 So, jetzt werden wir die Fragen Frage in ein paar verschiedene Möglichkeiten. 553 00:18:29,556 --> 00:18:31,610 Wie können wir über das Sortieren gehen diese Leute hier? 554 00:18:31,610 --> 00:18:34,500 Denn wir hatten ein paar Ansätze zuvor, wobei wir waren 555 00:18:34,500 --> 00:18:36,360 Art der Herstellung von zwei verschiedenen Eimern. 556 00:18:36,360 --> 00:18:38,842 Und dann waren wir in der Regel Setzen Dinge zusammen. 557 00:18:38,842 --> 00:18:41,050 Sobald wir zwei Zahlen sah, dass zusammengehörten, 558 00:18:41,050 --> 00:18:41,975 wir sie zusammen. 559 00:18:41,975 --> 00:18:43,350 Zwei Briefe, die zusammengehören. 560 00:18:43,350 --> 00:18:45,058 >> Aber lassen Sie uns, wenn wir sehen kann nicht formalisieren diese, 561 00:18:45,058 --> 00:18:48,044 so dass wir letztlich einige Pseudocode man so will, 562 00:18:48,044 --> 00:18:49,710 mit denen Sie diese Probleme lösen. 563 00:18:49,710 --> 00:18:51,870 So, jetzt bin ich auf der Suche auf diese Zahlen hier. 564 00:18:51,870 --> 00:18:55,030 Und ich sehe eine ganze Reihe von Fehlern. 565 00:18:55,030 --> 00:18:57,750 Letztlich möchte ich eine auf die links und acht auf der rechten Seite. 566 00:18:57,750 --> 00:19:00,650 >> Und so sehe ich auf diese beiden, vier bzw. zwei. 567 00:19:00,650 --> 00:19:02,930 Und was ist das Problem offensichtlich? 568 00:19:02,930 --> 00:19:04,261 Ja. 569 00:19:04,261 --> 00:19:04,760 Also. 570 00:19:04,760 --> 00:19:07,160 Zwei offensichtlich geht vor vier, so dass Sie wissen, was? 571 00:19:07,160 --> 00:19:10,210 Lassen Sie mich zunächst einen gierigen Ansatz, wenn man so will, ähnlich wie Problem 572 00:19:10,210 --> 00:19:13,790 gesetzt one--, wenn Sie an die erinnern, Standard Edition von Problem Set One, 573 00:19:13,790 --> 00:19:16,820 wo ich gerade vor Ort das Problem zu lösen das ist genau hier vor mir 574 00:19:16,820 --> 00:19:17,690 und sehen, wohin es mich führt. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Also zwei und vier, lass mich gehen voran und gerade tauschen Sie zwei. 577 00:19:20,161 --> 00:19:22,400 Wenn Sie körperlich bewegen kann euch selbst und eure Papier, 578 00:19:22,400 --> 00:19:25,040 Ich scheine das bekommen haben, Liste in einem besseren Zustand. 579 00:19:25,040 --> 00:19:26,330 >> Nun, sie sind gut. 580 00:19:26,330 --> 00:19:28,480 Ich werde weiterziehen, vier und sechs, sieht gut aus. 581 00:19:28,480 --> 00:19:29,110 Kein Problem. 582 00:19:29,110 --> 00:19:30,440 Sechs und acht, OK. 583 00:19:30,440 --> 00:19:31,860 Acht und ein anderes Problem. 584 00:19:31,860 --> 00:19:34,750 Denn was ist wahr, etwa acht und eine? 585 00:19:34,750 --> 00:19:36,990 Man kommt vor acht, und so was sollen wir tun? 586 00:19:36,990 --> 00:19:38,090 Lassen Sie uns tauschen diese beiden. 587 00:19:38,090 --> 00:19:39,316 Einem und acht. 588 00:19:39,316 --> 00:19:40,690 Und nun, ich werde weitermachen. 589 00:19:40,690 --> 00:19:42,030 Ich werde auch in Zukunft vor uns. 590 00:19:42,030 --> 00:19:42,840 Und lassen Sie uns sehen, was passiert. 591 00:19:42,840 --> 00:19:44,680 Acht und drei, von Natürlich nicht in Ordnung. 592 00:19:44,680 --> 00:19:45,815 Lassen Sie uns tauschen. 593 00:19:45,815 --> 00:19:46,940 Acht und sieben, natürlich. 594 00:19:46,940 --> 00:19:47,481 Außer Betrieb. 595 00:19:47,481 --> 00:19:48,280 Lassen Sie uns tauschen. 596 00:19:48,280 --> 00:19:49,940 Acht und fünf natürlich Lassen Sie uns tauschen. 597 00:19:49,940 --> 00:19:50,560 Gut. 598 00:19:50,560 --> 00:19:51,880 Liste sortiert ist. 599 00:19:51,880 --> 00:19:53,060 ja? 600 00:19:53,060 --> 00:19:54,280 >> OK, offensichtlich nicht. 601 00:19:54,280 --> 00:19:55,860 Aber es ist ein wenig besser, nicht wahr? 602 00:19:55,860 --> 00:19:57,270 Weil Hinweis, was passiert ist. 603 00:19:57,270 --> 00:20:01,749 Jedes Mal, wenn eine Swap, führten wir ein kleineres Anzahl Art versickert so, 604 00:20:01,749 --> 00:20:03,790 und eine größere Anzahl versickert auf diese Weise, oder wir 605 00:20:03,790 --> 00:20:06,880 beginnen die sprach zu den sprudelte nach links oder nach rechts geleitet. 606 00:20:06,880 --> 00:20:10,080 >> Nun, es ist nicht genug, denn im besten Fall eine Reihe könnte 607 00:20:10,080 --> 00:20:11,990 haben eine Stelle verschoben nach vorn, oder im schlimmsten Fall, 608 00:20:11,990 --> 00:20:13,880 einige haben könnte bewegt eine Stelle weiter. 609 00:20:13,880 --> 00:20:16,369 Damit Sie wissen, was diese Art der funktionierte ziemlich gut so weit. 610 00:20:16,369 --> 00:20:17,410 Lassen Sie mich nur versuchen Sie es erneut. 611 00:20:17,410 --> 00:20:18,880 Zwei und vier, sie sind OK. 612 00:20:18,880 --> 00:20:20,180 Vier und sechs, sie sind OK. 613 00:20:20,180 --> 00:20:21,790 Sechs und eine, in der richtigen Reihenfolge. 614 00:20:21,790 --> 00:20:23,007 Also lassen Sie uns tauschen Sie zwei. 615 00:20:23,007 --> 00:20:25,840 Und nun, bemerken das Problem der beginnen, wieder ein wenig besser. 616 00:20:25,840 --> 00:20:27,006 Sechs und drei, nicht in Ordnung. 617 00:20:27,006 --> 00:20:28,100 Lassen Sie uns tauschen Sie zwei. 618 00:20:28,100 --> 00:20:29,730 Sechs und sieben, du bist gut. 619 00:20:29,730 --> 00:20:32,230 Sieben und fünf, natürlich, nicht in Ordnung. 620 00:20:32,230 --> 00:20:33,920 Sieben und acht, in Ordnung. 621 00:20:33,920 --> 00:20:36,470 Und jetzt, könnte ich brauchen, tun dies noch ein paar Mal. 622 00:20:36,470 --> 00:20:39,830 Und in der Tat, ich denke für euch selbst vielleicht, wie oft maximal 623 00:20:39,830 --> 00:20:41,330 vielleicht habe ich hin und her zu gehen? 624 00:20:41,330 --> 00:20:42,390 >> Wir werden darauf zurückkommen. 625 00:20:42,390 --> 00:20:43,700 Also zwei und vier sind noch OK. 626 00:20:43,700 --> 00:20:44,940 Vier und eine, nein. 627 00:20:44,940 --> 00:20:45,747 Also, lassen Sie Swap. 628 00:20:45,747 --> 00:20:47,830 Und wieder feststellen, optisch man ist Art von Blasenbildung 629 00:20:47,830 --> 00:20:49,163 nach links, wo es sein sollte. 630 00:20:49,163 --> 00:20:50,010 Vier und drei Swap. 631 00:20:50,010 --> 00:20:51,330 Vier und sechs. 632 00:20:51,330 --> 00:20:53,100 Sechs und Fünf-Swap. 633 00:20:53,100 --> 00:20:53,959 Sechs und sieben. 634 00:20:53,959 --> 00:20:55,000 Sieben und acht sind gut. 635 00:20:55,000 --> 00:20:55,500 >> Gut. 636 00:20:55,500 --> 00:20:58,460 Wir sind immer noch besser. 637 00:20:58,460 --> 00:20:59,130 Also mal sehen. 638 00:20:59,130 --> 00:21:00,940 Jetzt haben wir zwei und eins. 639 00:21:00,940 --> 00:21:02,520 Natürlich tauschen. 640 00:21:02,520 --> 00:21:07,520 Zwei und drei, drei und vier, vier und fünf, sechs und sieben, sieben und acht. 641 00:21:07,520 --> 00:21:08,020 Gut. 642 00:21:08,020 --> 00:21:08,730 Und wissen Sie was? 643 00:21:08,730 --> 00:21:11,190 Weil ich eine Änderung gibt, lassen Sie mich eine Plausibilitätsprüfung zu tun. 644 00:21:11,190 --> 00:21:13,023 Lassen Sie mich den ganzen Weg gehen zurück zum Anfang. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 One, two-- yup, sehen? 647 00:21:14,750 --> 00:21:15,870 Irgendetwas stimmte nicht. 648 00:21:15,870 --> 00:21:18,420 Drei, vier, fünf, sechs, sieben, acht. 649 00:21:18,420 --> 00:21:21,920 Und in dieser letzten Pass, sind Sie sind komfortabel mit meinem jetzt 650 00:21:21,920 --> 00:21:23,830 behauptete, es wird sortiert? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Optisch, das ist absolut wahr. 653 00:21:25,880 --> 00:21:28,410 Aber funktional, was haben auch nur zufällig 654 00:21:28,410 --> 00:21:31,870 in diesem letzten Durchgang, das Ihnen erlaubt , um zu bestätigen, dass diese Liste ist in der Tat 655 00:21:31,870 --> 00:21:32,660 sortiert? 656 00:21:32,660 --> 00:21:34,477 >> Was habe ich getan oder nicht tun, diese letzte Pass? 657 00:21:34,477 --> 00:21:35,810 Publikum: Es gab keine Veränderungen. 658 00:21:35,810 --> 00:21:36,120 David J. MALAN: Es tut uns leid? 659 00:21:36,120 --> 00:21:37,070 ZIELGRUPPE: Keine Änderungen. 660 00:21:37,070 --> 00:21:38,653 David J. MALAN: Es gab keine Veränderungen. 661 00:21:38,653 --> 00:21:41,947 So wäre es dumm von mir, Tun Sie das gleiche Algorithmus wieder 662 00:21:41,947 --> 00:21:43,780 wenn ich nicht machen jeden ändert sich die erste Zeit. 663 00:21:43,780 --> 00:21:45,160 Und der Zustand nicht geändert hat. 664 00:21:45,160 --> 00:21:47,576 Sicherlich werde ich nicht zu machen beliebige ändert das zweite Mal. 665 00:21:47,576 --> 00:21:49,820 Und so ist es jetzt sicher zu sagen, ist die Liste sortiert. 666 00:21:49,820 --> 00:21:52,069 >> Und in der Tat ist dies nun etwas, dass wir in der Regel 667 00:21:52,069 --> 00:21:56,900 Call Bubble Sort, wobei paarweise, Sie Fehler wieder zu korrigieren, 668 00:21:56,900 --> 00:22:00,210 und wieder, und wieder, und Sie fahren Sie hin und her, 669 00:22:00,210 --> 00:22:03,370 und hin und her, bis Sie machen keine solchen Swaps, an welcher Stelle 670 00:22:03,370 --> 00:22:07,089 Sie können sicher sein, yeah, I fertig zur Festsetzung alle Fehler. 671 00:22:07,089 --> 00:22:08,630 Lassen Sie uns zurückzusetzen, und versuchen Sie einen anderen Ansatz. 672 00:22:08,630 --> 00:22:11,590 Wenn euch könnte in zurück die Reihenfolge vor einem Augenblick waren, 673 00:22:11,590 --> 00:22:13,780 die so ausgesehen. 674 00:22:13,780 --> 00:22:17,640 Nun, lassen Sie uns einen Ansatz ein wenig mehr wie die Prüfung Buch 675 00:22:17,640 --> 00:22:21,122 wobei wir ständig waren Auswahl der Buchstabe des Alphabets 676 00:22:21,122 --> 00:22:22,830 dass wir irgendwie wollte mit weiter beschäftigen. 677 00:22:22,830 --> 00:22:26,420 Vielleicht war es ein Hoch Brief, wie A, oder einem niedrigen Buchstaben Z. 678 00:22:26,420 --> 00:22:28,170 >> So dass jeder ist wieder in dieser Reihenfolge. 679 00:22:28,170 --> 00:22:29,800 Und jetzt lassen Sie mich dies zu tun. 680 00:22:29,800 --> 00:22:34,880 Mal sehen, ich weiß, ich habe acht Zahlen hier. 681 00:22:34,880 --> 00:22:37,410 Ich werde weitermachen und nur bewusst wählen 682 00:22:37,410 --> 00:22:38,520 die kleinsten Elemente. 683 00:22:38,520 --> 00:22:38,760 Recht? 684 00:22:38,760 --> 00:22:39,801 Dies scheint auch intuitiv. 685 00:22:39,801 --> 00:22:42,560 Warum kann ich nicht das kleinste finden Element, setzte es, wo es gehört, 686 00:22:42,560 --> 00:22:45,280 dann die nächste kleinste Element, setzen es, wo es hingehört, und einfach zu wiederholen. 687 00:22:45,280 --> 00:22:46,820 >> Weil intuitiv, das auch funktionieren sollte. 688 00:22:46,820 --> 00:22:48,441 So vier, das ist eine ziemlich kleine Zahl. 689 00:22:48,441 --> 00:22:49,940 Ich werde daran erinnern, wo das ist. 690 00:22:49,940 --> 00:22:50,523 Warte eine Minute. 691 00:22:50,523 --> 00:22:51,577 Zwei ist kleiner. 692 00:22:51,577 --> 00:22:53,910 Lassen Sie mich daran erinnern, wo zwei ist, und vergessen Sie vier. 693 00:22:53,910 --> 00:22:55,050 Wir beginnen mit, dass später. 694 00:22:55,050 --> 00:22:56,460 Sechs, ich bin nicht daran interessiert. 695 00:22:56,460 --> 00:22:57,810 Acht, ich bin nicht daran interessiert. 696 00:22:57,810 --> 00:22:59,780 Eines ist meine neue kleine Zahl. 697 00:22:59,780 --> 00:23:01,470 Also werde ich zu erinnern, wo man ist. 698 00:23:01,470 --> 00:23:02,534 Drei, nicht interessiert. 699 00:23:02,534 --> 00:23:03,450 Seven, nicht interessiert. 700 00:23:03,450 --> 00:23:04,530 Fünf, nicht interessiert. 701 00:23:04,530 --> 00:23:07,390 >> Also, ohne herunterzufallen die Bühne in diesem Jahr, 702 00:23:07,390 --> 00:23:09,890 Ich werde Nummer greifen one-- und was war Ihr Name? 703 00:23:09,890 --> 00:23:10,150 >> Annan Annan. 704 00:23:10,150 --> 00:23:11,220 >> David J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 Und wenn könnten Sie mir bei beitreten der Anfang der Liste, 706 00:23:13,540 --> 00:23:14,870 sagen wir Ihnen, wo Sie hingehören. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- was ist Ihr Name? 708 00:23:16,080 --> 00:23:16,650 >> Stefan: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> David J. MALAN: Stefan im Weg ist. 710 00:23:18,191 --> 00:23:23,490 Also, bevor Stefan löst dieses Problem Problem, was sollen wir tun? 711 00:23:23,490 --> 00:23:25,412 Was machen wir mit Stefan? 712 00:23:25,412 --> 00:23:27,269 >> ZIELGRUPPE: [unverständlich]. 713 00:23:27,269 --> 00:23:28,060 David J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 So konnten wir das tun. 715 00:23:28,850 --> 00:23:31,730 Wir könnten eine Art nehmen Stefan und seine vier, und nur ihn in einer Variablen 716 00:23:31,730 --> 00:23:33,530 und halten Sie auf, um es für eine gewisse Menge an Zeit, 717 00:23:33,530 --> 00:23:35,220 wodurch Raum für die Nummer eins. 718 00:23:35,220 --> 00:23:36,280 Und das ist nicht schlecht. 719 00:23:36,280 --> 00:23:39,270 Ich könnte vorschlagen, warum nicht wir haben gerade Stefan hier? 720 00:23:39,270 --> 00:23:41,610 Warum könnte dies verletzen einem der Ideen, die wir begonnen 721 00:23:41,610 --> 00:23:44,830 reden über das letzte Mal, letzte Woche? 722 00:23:44,830 --> 00:23:45,330 Ja? 723 00:23:45,330 --> 00:23:45,740 >> ZIELGRUPPE: [unverständlich]. 724 00:23:45,740 --> 00:23:46,860 >> David J. MALAN: Es gibt keinen Index für sie. 725 00:23:46,860 --> 00:23:49,735 Wenn Sie denken, dies in der Tat als Array, das ist wie negative, 726 00:23:49,735 --> 00:23:52,900 so gibt es keine Speicher tatsächlich Falls dies tatsächlich ein Array, 727 00:23:52,900 --> 00:23:55,090 wie wir es in der vergangenen Woche erklärt, in der Vorlesung. 728 00:23:55,090 --> 00:23:56,250 Also sollten wir nicht tun. 729 00:23:56,250 --> 00:23:57,340 Wir könnten sie in einer Variablen speichern. 730 00:23:57,340 --> 00:23:57,820 >> Oder wissen Sie was? 731 00:23:57,820 --> 00:23:59,153 Ich hörte jemanden schlage es. 732 00:23:59,153 --> 00:24:01,020 Was können wir tun, mit Stefan? 733 00:24:01,020 --> 00:24:03,770 Warum gehen wir nicht ihn einfach zu vertreiben und legte ihn auf, wo die Nummer eins war. 734 00:24:03,770 --> 00:24:05,170 Also, wenn Sie dort gehen wollen. 735 00:24:05,170 --> 00:24:07,300 Und in der Tat ist dies ein ziemlich gute Lösung. 736 00:24:07,300 --> 00:24:10,480 Jetzt auf der einen Seite, ich habe Art der machte das Problem noch schlimmer. 737 00:24:10,480 --> 00:24:13,650 Vier ist jetzt weiter weg von wo es sein sollte. 738 00:24:13,650 --> 00:24:14,900 Es sollte zu dieser Hälfte. 739 00:24:14,900 --> 00:24:16,100 >> Aber wissen Sie was? 740 00:24:16,100 --> 00:24:17,630 Das hätte Pech haben. 741 00:24:17,630 --> 00:24:18,822 Vielleicht Nummer acht war hier. 742 00:24:18,822 --> 00:24:20,530 Und so, vielleicht würden wir Glück haben bekommen, 743 00:24:20,530 --> 00:24:22,460 und schob acht näher zum Ende. 744 00:24:22,460 --> 00:24:24,710 So dass am Ende des Tages, es irgendwie alle mittelt. 745 00:24:24,710 --> 00:24:26,085 Wir brauchen nicht zu etwa vier kümmern. 746 00:24:26,085 --> 00:24:29,400 Mich interessiert im Augenblick Auswahl der kleinste Element. 747 00:24:29,400 --> 00:24:32,030 >> Und nun, was ich zu gehen zu tun ist über die Nummer eins vergessen 748 00:24:32,030 --> 00:24:35,160 dauerhaft, weil ich weiß, die Liste hinter mir ist nun sortiert. 749 00:24:35,160 --> 00:24:36,720 So war meine Liste zuvor Größe acht. 750 00:24:36,720 --> 00:24:37,720 Jetzt ist es an der Größe sieben. 751 00:24:37,720 --> 00:24:40,340 Also mein Problem ist, kleiner, wenn auch linear. 752 00:24:40,340 --> 00:24:43,022 So, jetzt werde ich die wählen Strom kleinste Element, zwei. 753 00:24:43,022 --> 00:24:46,520 Sechs, acht, vier, drei, sieben, fünf. 754 00:24:46,520 --> 00:24:47,770 Das war das kleinste Element. 755 00:24:47,770 --> 00:24:49,416 Also, was soll ich nur tun mit-- Was war Ihr Name? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> David J. MALAN: Joseph? 758 00:24:50,085 --> 00:24:52,000 Wir werden Joseph an ihrem Platz bleiben. 759 00:24:52,000 --> 00:24:54,842 Nun, ich werde so tun, dass diese Jungs sind-- auch, 760 00:24:54,842 --> 00:24:56,550 Ich weiß, daß diese beiden bereits sortiert. 761 00:24:56,550 --> 00:24:58,424 Lassen Sie uns jetzt konzentrieren sich auf die Rest der Liste. 762 00:24:58,424 --> 00:25:00,080 Six ist der aktuelle kleinste. 763 00:25:00,080 --> 00:25:01,190 Acht ist größer. 764 00:25:01,190 --> 00:25:02,970 Vier ist jetzt der aktuelle kleinste. 765 00:25:02,970 --> 00:25:04,762 Drei ist jetzt der aktuelle kleinste. 766 00:25:04,762 --> 00:25:07,720 Und nun, ich werde drei auszuwählen, die ist--, was wiederum heißt du? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 David J. MALAN: Serena, wenn du könntest Schnappen Sie sich Ihre Nummer und Swap mit-- 769 00:25:10,620 --> 00:25:11,550 Kelsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 David J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Komm zurück, und wir sind gehen, um diese beiden zu tauschen. 772 00:25:15,220 --> 00:25:17,360 Und jetzt lassen wir diese auf Autopilot. 773 00:25:17,360 --> 00:25:21,589 Ich werde gehen und überlassen es euch auf die nächste kleinste Elemente auszuwählen. 774 00:25:21,589 --> 00:25:22,380 Dun dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Nummer vier, was sollte man tun? 776 00:25:24,560 --> 00:25:26,261 Ausgezeichnet. 777 00:25:26,261 --> 00:25:27,760 Nun, ich werde einen anderen Pass zu machen. 778 00:25:27,760 --> 00:25:28,590 Dun dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Ich sehe fünf ist die nächste kleinste. 780 00:25:31,465 --> 00:25:32,840 Nun, ich werde wieder einen einzigen Pass ab. 781 00:25:32,840 --> 00:25:33,631 Dun dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Sechs am kleinsten ist. 783 00:25:34,880 --> 00:25:35,520 Gut. 784 00:25:35,520 --> 00:25:36,585 Sieben am kleinsten ist. 785 00:25:36,585 --> 00:25:37,085 Kein Wechselgeld. 786 00:25:37,085 --> 00:25:38,630 Acht am geringsten ist. 787 00:25:38,630 --> 00:25:39,170 Fertig. 788 00:25:39,170 --> 00:25:43,900 >> Also, was wir gerade durch iteratives getan Auswählen eines Elements nach dem anderen 789 00:25:43,900 --> 00:25:47,230 ist etwas, das wir umsetzen gehen, um als Auswahl Art zu formalisieren. 790 00:25:47,230 --> 00:25:49,120 Und es ist vielleicht sogar einfacher zu erklären, 791 00:25:49,120 --> 00:25:51,310 im wahrsten Sinne des Wortes, dass alles, was Sie tun möchte, ist einfach weiter 792 00:25:51,310 --> 00:25:54,700 hin und her durch die Liste Auswahl, die nächste kleinste Element, 793 00:25:54,700 --> 00:25:55,720 , bis Sie fertig sind. 794 00:25:55,720 --> 00:25:58,650 >> So ist es sogar noch einfacher, vielleicht intuitiv, als im letzten. 795 00:25:58,650 --> 00:26:00,020 Lassen Sie uns versuchen eine letzte. 796 00:26:00,020 --> 00:26:03,060 Wenn euch könnte euch selbst zurückzusetzen in die folgenden Positionen 797 00:26:03,060 --> 00:26:08,600 ein letztes Mal, mal sehen, ob wir nicht Jetzt formalisieren einen anderen Ansatz. 798 00:26:08,600 --> 00:26:12,857 In der Tat, jemand würde da draußen gerne vorschlagen 799 00:26:12,857 --> 00:26:14,440 Wie sonst könnten wir dabei vorgehen? 800 00:26:14,440 --> 00:26:17,439 Ohne das Werfen aus Schlagwörtern oder sort der Antworten, die bereits bekannt sind, 801 00:26:17,439 --> 00:26:19,689 nur intuitiv, was können wir tun? 802 00:26:19,689 --> 00:26:21,635 >> ZIELGRUPPE: [unverständlich]. 803 00:26:21,635 --> 00:26:22,510 David J. MALAN: Ja. 804 00:26:22,510 --> 00:26:24,620 So gibt es einige große Intuition gibt. 805 00:26:24,620 --> 00:26:28,020 Gute Dinge scheinen bisher geschehen in der Informatik, als wir zu teilen 806 00:26:28,020 --> 00:26:30,832 und erobere das Problem der Teilung es halb und halb und halb. 807 00:26:30,832 --> 00:26:32,540 Und so in der Tat, wir beginnen konnte, das zu tun. 808 00:26:32,540 --> 00:26:35,754 Und in der Tat, das wird sein, werden wir sehen eine unserer besten Lösungen vor. 809 00:26:35,754 --> 00:26:37,420 Aber lassen Sie uns zurückkommen, bevor lang. 810 00:26:37,420 --> 00:26:40,500 In der Tat, wir werden tun, dass ein wenig später in dieser Woche. 811 00:26:40,500 --> 00:26:42,180 Was könnten wir tun, um dieses Problem zu lösen? 812 00:26:42,180 --> 00:26:44,647 So dass jeder hier in scheinbar zufälliger Reihenfolge. 813 00:26:44,647 --> 00:26:45,230 Weißt du was? 814 00:26:45,230 --> 00:26:48,320 Anstatt hin und her, hin und her, hin und her, 815 00:26:48,320 --> 00:26:50,624 jedes Mal, fühlt sich das wie Ich mache eine Menge zu Fuß. 816 00:26:50,624 --> 00:26:52,790 Warum kann ich nicht gerade am Start der Anfang der Liste, 817 00:26:52,790 --> 00:26:54,960 und hat gerade vier, wo es hingehört? 818 00:26:54,960 --> 00:26:59,680 Also lassen Sie mich für den Moment annehmen, dass meiner Liste ist nur das erste Element. 819 00:26:59,680 --> 00:27:04,937 Wird vier in diesem Moment in der Zeit sortiert, wenn alle mich interessiert, ist hier alles? 820 00:27:04,937 --> 00:27:06,520 Dies ist eine Art trivialerweise richtig, oder? 821 00:27:06,520 --> 00:27:10,000 Wie die Liste, die eine Nummer und dass die Nummer vier ist natürlich sortiert. 822 00:27:10,000 --> 00:27:13,070 >> Also lassen Sie mich nur vor, dass diese Liste sortiert ist. 823 00:27:13,070 --> 00:27:15,090 Aber jetzt habe ich den Rest dieser Liste. 824 00:27:15,090 --> 00:27:17,240 So, jetzt, begegne ich zwei. 825 00:27:17,240 --> 00:27:21,690 Woher kommt zwei offensichtlich gehören in Bezug auf vier? 826 00:27:21,690 --> 00:27:22,580 Vor vier. 827 00:27:22,580 --> 00:27:23,862 Also, was kann ich hier machen? 828 00:27:23,862 --> 00:27:24,820 Was ist dein Name nochmal? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> David J. MALAN: Joseph, wenn Sie zurücktreten konnte 831 00:27:26,030 --> 00:27:27,790 für einen Moment mit Ihrer Nummer. 832 00:27:27,790 --> 00:27:31,130 Und nun, was soll Stefan hier? 833 00:27:31,130 --> 00:27:33,720 Lassen Sie uns zu verlagern Stefan hier. 834 00:27:33,720 --> 00:27:35,520 Und nun lassen Sie Joseph kommen hier rein. 835 00:27:35,520 --> 00:27:39,660 Und jetzt lassen Sie mich behaupten, hier ist alles sortiert. 836 00:27:39,660 --> 00:27:42,474 So ähnliches Ergebnis, sondern eine grundlegend anderen Ansatz. 837 00:27:42,474 --> 00:27:44,140 Ich habe nicht einmal sah was da unten ist. 838 00:27:44,140 --> 00:27:46,310 Ich habe gerade halten, die die Elemente wie sie mir übergeben, 839 00:27:46,310 --> 00:27:47,240 und mit ihnen umzugehen. 840 00:27:47,240 --> 00:27:48,330 >> So, jetzt sehe ich die Nummer sechs. 841 00:27:48,330 --> 00:27:51,110 Wo steht die Nummer sechs gehören? 842 00:27:51,110 --> 00:27:53,250 Wir haben zwei, vier, sechs. 843 00:27:53,250 --> 00:27:54,800 Genau dort, wo sie im Augenblick. 844 00:27:54,800 --> 00:27:57,750 Also lassen wir das allein, und jetzt behaupten, dass dieser Teil der Liste 845 00:27:57,750 --> 00:27:58,772 wird nun sortiert. 846 00:27:58,772 --> 00:28:01,230 Und so fühlt sich dieser grundlegend dadurch gekennzeichnet, dass unterschiedliche ich bin einfach 847 00:28:01,230 --> 00:28:05,230 Bewegen sich hier durch die Liste linear, und ich werde nie wieder zu verdoppeln. 848 00:28:05,230 --> 00:28:05,730 Ja. 849 00:28:05,730 --> 00:28:06,230 Gut. 850 00:28:06,230 --> 00:28:08,190 So acht, wo gehören Sie? 851 00:28:08,190 --> 00:28:08,730 Genau hier. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 So, jetzt, ein. 854 00:28:10,210 --> 00:28:10,900 UH Oh. 855 00:28:10,900 --> 00:28:13,010 Das fühlt sich an wie es ist wird teuer. 856 00:28:13,010 --> 00:28:15,690 Jetzt im vorherigen Algorithmus Ich habe gerade vertauscht Personen. 857 00:28:15,690 --> 00:28:18,648 So könnte ich ihn legte den ganzen Weg der Anfang, aber dann zog Joseph. 858 00:28:18,648 --> 00:28:21,450 Aber wenn ich Joseph bewegen, jetzt was los ist, falsch sein? 859 00:28:21,450 --> 00:28:24,250 >> Art undone-- Ich habe jetzt, ich habe genommen einen Schritt nach vorn und dann 860 00:28:24,250 --> 00:28:26,300 einen Schritt zurück, denn jetzt Joseph wäre nicht in Ordnung zu sein. 861 00:28:26,300 --> 00:28:26,830 Also lassen Sie uns dies tun. 862 00:28:26,830 --> 00:28:29,150 Wenn Sie könnten die Nummer eins zu nehmen und Schritt zurück für einen Moment. 863 00:28:29,150 --> 00:28:30,490 Wie können wir das, was put-- war Ihr Name? 864 00:28:30,490 --> 00:28:31,130 >> Annan Annan. 865 00:28:31,130 --> 00:28:32,610 >> David J. MALAN: Annan vorhanden? 866 00:28:32,610 --> 00:28:36,091 Was muss sich in Bezug passieren zwei, vier, sechs und acht? 867 00:28:36,091 --> 00:28:37,570 Sie alle brauchen, um zu verschieben. 868 00:28:37,570 --> 00:28:42,590 Also, wenn acht möchten verschieben zuerst, dann sechs, dann vier, dann zwei. 869 00:28:42,590 --> 00:28:45,380 Und dann Annan, wenn Sie möchten, gerne hierher in, gut. 870 00:28:45,380 --> 00:28:47,760 Aber hier, nur haben wir einen Preis Art von bezahlten 871 00:28:47,760 --> 00:28:49,510 an einem anderen Punkt in dem Algorithmus. 872 00:28:49,510 --> 00:28:52,550 Der Erwägung, dass das letzte Mal mit einer Auswahl Art und sogar Bubble Sort, 873 00:28:52,550 --> 00:28:54,700 Ich gehe zurück zu Fuß und her, hin und her, 874 00:28:54,700 --> 00:28:58,360 die sicherlich Addition wird zeitlich und buchstäblich schrittweise. 875 00:28:58,360 --> 00:29:00,660 >> Insertion Sort, auf den ersten Blick sieht wie es ist 876 00:29:00,660 --> 00:29:05,150 Super-intelligenter, dass ich bin einfach schleppend, inkrementelle Fortschritte, 877 00:29:05,150 --> 00:29:07,120 aber ich bin nicht hin und her gehen diese. 878 00:29:07,120 --> 00:29:09,410 Aber wenn jemand in der Tat außer Betrieb, Ankündigung 879 00:29:09,410 --> 00:29:10,840 alle von der Arbeit musste ich einfach zu tun. 880 00:29:10,840 --> 00:29:14,750 Ich musste die Hälfte der Liste zu verschieben nur, um Platz für die Nummer eins zu machen. 881 00:29:14,750 --> 00:29:16,790 So ist es die gleiche Menge Arbeit so weit es 882 00:29:16,790 --> 00:29:18,690 fühlt sich, nur eine andere Art von Arbeit. 883 00:29:18,690 --> 00:29:19,370 >> Lass uns weitermachen. 884 00:29:19,370 --> 00:29:22,657 So, jetzt wissen wir, dass jeder zwischen einem und acht werden sortiert. 885 00:29:22,657 --> 00:29:23,740 Hier habe ich die Nummer drei. 886 00:29:23,740 --> 00:29:25,864 Wenn Sie zu holen mögen Nummer drei, Schritt zurück ein. 887 00:29:25,864 --> 00:29:28,260 Und was euch tun müssen? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Also das ist eine andere ein, zwei, drei Schritte. 890 00:29:33,070 --> 00:29:36,010 Drei Zeiteinheiten, die nur kosten mir, so dass drei können jetzt passen. 891 00:29:36,010 --> 00:29:37,460 Schließlich sieben. 892 00:29:37,460 --> 00:29:39,730 >> Lassen Sie uns gehen Sie voran und haben Sie einen Schritt zurück. 893 00:29:39,730 --> 00:29:42,780 Dies ist nur zu uns kosten eine Einheit von Zeit, aber das ist OK. 894 00:29:42,780 --> 00:29:44,170 Und nun, fünf geht um ein wenig teurer. 895 00:29:44,170 --> 00:29:45,340 Wenn Sie möchten, einen Schritt zurück. 896 00:29:45,340 --> 00:29:48,380 Wir müssen uns bewegen, acht, und sieben und sechs. 897 00:29:48,380 --> 00:29:50,749 Und dann jeder ist jetzt sortiert. 898 00:29:50,749 --> 00:29:52,290 So eine große Hand, um unsere Freiwilligen hier. 899 00:29:52,290 --> 00:29:53,554 Vielen Dank. 900 00:29:53,554 --> 00:29:56,220 >> [Applaus] 901 00:29:56,220 --> 00:29:56,860 >> Danke euch allen. 902 00:29:56,860 --> 00:29:57,520 Danke euch allen. 903 00:29:57,520 --> 00:30:02,940 Also lassen Sie uns jetzt, wie zu sehen teuer das alles war. 904 00:30:02,940 --> 00:30:06,210 Betrachten wir vielleicht die einfachste davon, Bubble-Sort. 905 00:30:06,210 --> 00:30:09,950 Und ich sage einfachsten, nur, weil Sie können es gierig von nur lösen 906 00:30:09,950 --> 00:30:11,660 befestigen Sie den paarweisen Problem hier. 907 00:30:11,660 --> 00:30:13,720 Befestigen Sie den paarweisen Problem Hier wieder 908 00:30:13,720 --> 00:30:17,680 wieder, wiederkehr so ​​viele Male, wie Sie tatsächlich benötigen, um. 909 00:30:17,680 --> 00:30:21,050 >> So stellt sich heraus, dass mit einem Bubble-Sort, na ja, 910 00:30:21,050 --> 00:30:25,820 wie viele Schritte muss ich zu übernehmen der erste Durchgang dieses Algorithmus? 911 00:30:25,820 --> 00:30:30,850 Ich könnte take-- wir see-- ein, zwei, drei, vier, fünf, sechs, sieben. 912 00:30:30,850 --> 00:30:32,190 Und es gibt acht Elemente hier. 913 00:30:32,190 --> 00:30:35,280 So ist es wie n minus 1 vor, um erhalten aus dem Anfang der Liste 914 00:30:35,280 --> 00:30:36,380 an das Ende der Liste. 915 00:30:36,380 --> 00:30:41,350 >> Aber mit Selection Sort, daran erinnern, dass ich Auswahl der Elemente wieder und wieder 916 00:30:41,350 --> 00:30:44,590 wieder, dass der kleinste, Ich stelle es fest, 917 00:30:44,590 --> 00:30:46,616 aber dann bin ich nicht Blick hinter mich wieder. 918 00:30:46,616 --> 00:30:49,490 Also ich denke, es ist ein wenig mehr klar, dann, dass das erste Mal, ich könnte 919 00:30:49,490 --> 00:30:52,680 müssen alle n minus 1 Schritte zu unternehmen, um das kleinste Element zu finden. 920 00:30:52,680 --> 00:30:55,920 Dann legte ich sie an ihrem Platz, und ich zu vertreiben, wer zuvor war hier. 921 00:30:55,920 --> 00:30:57,500 >> Aber dann weiß ich nicht zu haben, auch in Zukunft auf diesem Element, 922 00:30:57,500 --> 00:30:59,040 weil ich weiß, es ist bereits die kleinste. 923 00:30:59,040 --> 00:31:01,581 So, jetzt kann ich bei nur sieben suchen Elemente, dann sechs Elemente, 924 00:31:01,581 --> 00:31:03,290 dann fünf Elemente, dann vier Elemente. 925 00:31:03,290 --> 00:31:06,900 Und so mathematisch wenn n die Anzahl von Elementen oder Zahlen 926 00:31:06,900 --> 00:31:11,990 dass wir mit gestartet wird, können Sie sich vorstellen dass dies dasselbe wie n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 Stufen, plus n minus 3 Stufen, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 Schritte, die ganze bis hinunter zu nur einem Schritt. 929 00:31:16,780 --> 00:31:18,160 Und ich bin auf meinem letzten Person. 930 00:31:18,160 --> 00:31:20,650 >> Und wenn Sie sich erinnern, dass viele der Statistik Bücher oder mathematische Bücher 931 00:31:20,650 --> 00:31:24,730 haben diese Formeln auf dem Hardcover Rücken oder vor ihnen, 932 00:31:24,730 --> 00:31:27,690 es stellt sich heraus, dass dieser Serie kann einfacher ausgedrückt werden 933 00:31:27,690 --> 00:31:28,857 als n mal n minus 1 mehr als 2. 934 00:31:28,857 --> 00:31:31,273 Und es ist in Ordnung, wenn das nicht an der Spitze Ihres Geistes. 935 00:31:31,273 --> 00:31:32,420 Aber das ist wohl wahr. 936 00:31:32,420 --> 00:31:34,449 Das ist nur ein einfacher Weg, es zu schreiben. 937 00:31:34,449 --> 00:31:36,240 Und dann, wenn Sie denken zurück zur Grundschule, 938 00:31:36,240 --> 00:31:38,698 wenn Sie gerade beginnen Multiplikation Dinge, in diesem Fall natürlich, 939 00:31:38,698 --> 00:31:41,820 wird nur n Quadrat minus n dividiert durch 2. 940 00:31:41,820 --> 00:31:44,772 Alles, was ich getan habe, ist zu erweitern die Ausdrücke gibt. 941 00:31:44,772 --> 00:31:46,730 Und so lassen Sie uns dies umschreiben ein wenig anders. 942 00:31:46,730 --> 00:31:49,780 Das ist n Quadrat geteilt durch 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Also noch einmal, ich bin nur Art von Anwendung einige Rechenregeln gibt. 944 00:31:53,270 --> 00:31:57,140 Aber jetzt feststellen, dass der größte Begriff in diesem Ausdruck sozusagen 945 00:31:57,140 --> 00:31:58,540 ist, dass n quadriert. 946 00:31:58,540 --> 00:32:02,910 Also ja, es ist n squared dividiert durch 2 minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Aber in der Regel, wenn n wird ein großer Wert sein, 948 00:32:05,080 --> 00:32:08,740 Ich werde behaupten, dass n quadriert wird sich der dominierende Faktor sein. 949 00:32:08,740 --> 00:32:10,490 Es ist nur los zu sein einen größeren Beitrag 950 00:32:10,490 --> 00:32:12,877 um die Anzahl von Schritten als n / 2 ist. 951 00:32:12,877 --> 00:32:13,960 Also, was kann ich damit? 952 00:32:13,960 --> 00:32:16,795 Versuchen wir ein einfaches Beispiel, auch obwohl die Mathematik ein wenig groß. 953 00:32:16,795 --> 00:32:20,210 >> So nehme an wir hatten 1 Million Menschen auf der Bühne, oder 1 Million Dinge 954 00:32:20,210 --> 00:32:21,320 , dass wir wollen, um zu sortieren. 955 00:32:21,320 --> 00:32:23,730 Lassen Sie uns stecken Sie ein Millionen in genau dieser Formel 956 00:32:23,730 --> 00:32:27,230 um zu sehen, wie viele Schritte es braucht insgesamt eine Million Elemente zu sortieren mit sagen wir, 957 00:32:27,230 --> 00:32:28,560 Auswahl sort. 958 00:32:28,560 --> 00:32:30,760 >> So würden wir die gleiche Formel wie zuvor. 959 00:32:30,760 --> 00:32:34,120 Ich würde eine Million stecken, so dass ich Million Quadrat geteilt durch 2, 960 00:32:34,120 --> 00:32:35,990 minus Million geteilt durch 2. 961 00:32:35,990 --> 00:32:40,180 Wenn ich das tue, Mathematik im Voraus Hier haben wir 500 Milliarden 962 00:32:40,180 --> 00:32:47,460 minus 500.000, die gibt uns 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 Das ist verdammt groß. 964 00:32:49,270 --> 00:32:54,370 >> In der Tat, wenn Sie jetzt vergleichen 499 Milliarden, 999 Millionen, 965 00:32:54,370 --> 00:33:01,210 500.000 gegenüber unseren ursprünglichen Wert, 500 Milliarden, es ist so verdammt nah. 966 00:33:01,210 --> 00:33:06,850 Recht? n squared von 2 gibt aufgeteilt us-- oder vielmehr n Quadrat geteilt durch 2 967 00:33:06,850 --> 00:33:08,370 gab uns 500 Milliarden. 968 00:33:08,370 --> 00:33:13,510 Das ist verdammt nah um 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 was zu sagen, Subtraktion off 500.000 ist, oder allgemeiner Subtrahieren 970 00:33:17,970 --> 00:33:20,010 n quadriert, nicht wirklich eine große Sache. 971 00:33:20,010 --> 00:33:22,490 Die n quadriert macht diese Zahlen wachsen wirklich schnell. 972 00:33:22,490 --> 00:33:25,790 >> Nun, dies ist nur insofern von Bedeutung, wie wir als Informatiker, 973 00:33:25,790 --> 00:33:29,350 werden in der Regel nicht zu so viel Pflege über die Feinheiten dieser Formeln 974 00:33:29,350 --> 00:33:31,400 und genau das, was die präzise Antworten gibt. 975 00:33:31,400 --> 00:33:33,390 Wir kümmern uns nur das, weißt du was? 976 00:33:33,390 --> 00:33:37,810 Am Ende des Tages, diese Formel liegt in der Grßenordnung von n quadriert. 977 00:33:37,810 --> 00:33:39,350 >> Ja, wir sind um 2 Teilungs drin. 978 00:33:39,350 --> 00:33:41,360 Ja, wir Subtraktion off n minus 2. 979 00:33:41,360 --> 00:33:46,860 Aber am Ende des Tages wird der Begriff dass wirklich weh tut uns und kostet uns 980 00:33:46,860 --> 00:33:48,995 viele Stufen ist, dass quadratische tigen. 981 00:33:48,995 --> 00:33:51,370 Und was ein Informatiker wird sich in der Regel zu tun 982 00:33:51,370 --> 00:33:54,160 wird ignoriert alle, kleiner Auftrag AGB, 983 00:33:54,160 --> 00:33:56,900 und nur an der einen Blick, trägt am meisten zu den Kosten. 984 00:33:56,900 --> 00:34:00,530 >> Und das ist schön, weil wir können, jetzt in viel größerer Allgemeinheit sprechen 985 00:34:00,530 --> 00:34:02,470 über Algorithmen und sie zu vergleichen. 986 00:34:02,470 --> 00:34:04,550 Und die Tatsache, dass ich Verwendung dieser O ist gewollt. 987 00:34:04,550 --> 00:34:06,680 Als ich in der Größenordnung sagen von, ich bin speziell 988 00:34:06,680 --> 00:34:09,560 auf etwas beziehen genannten großen O. und Big O 989 00:34:09,560 --> 00:34:14,090 ist eine Notation, die einen Computer Wissenschaftler verwendet, um zu beschreiben 990 00:34:14,090 --> 00:34:16,710 eine obere an etwas gebunden. 991 00:34:16,710 --> 00:34:21,150 >> Also, wenn Sie sagen, dass ein Algorithmus ist in den großen O n quadriert, 992 00:34:21,150 --> 00:34:23,380 wie ich vorgeschlagen, nur eine Moment vor, dass Mittel 993 00:34:23,380 --> 00:34:27,710 dass in Bezug auf seine Lauf Zeit oder Effizienz, 994 00:34:27,710 --> 00:34:30,090 Es dauert in der Grßenordnung n quadriert Schritte. 995 00:34:30,090 --> 00:34:31,420 Vielleicht mehr, vielleicht weniger. 996 00:34:31,420 --> 00:34:33,435 Aber es ist in der Größenordnung von n quadriert. 997 00:34:33,435 --> 00:34:34,560 Und das ist die Obergrenze. 998 00:34:34,560 --> 00:34:36,530 Es wird nicht zu sein schmerzhafter als das. 999 00:34:36,530 --> 00:34:40,800 Es wird nicht n Würfel geschnitten zu sein, oder 2 zu der n, oder etwas viel größer. 1000 00:34:40,800 --> 00:34:43,800 Dies ist eine obere Schranke auf, was das kosten wird. 1001 00:34:43,800 --> 00:34:46,150 Also da, lassen Sie uns Sehen Sie sich nur ein paar Beispiele. 1002 00:34:46,150 --> 00:34:49,820 Und dies ist nur eine endliche Liste der sehr häufige Laufzeiten 1003 00:34:49,820 --> 00:34:52,870 für Algorithmen, die bedeutete, ist zu sein beispielhaft für einige Dinge, die wir 1004 00:34:52,870 --> 00:34:53,600 schon gesehen. 1005 00:34:53,600 --> 00:34:58,060 >> So zum Beispiel im Fall von Selection Sort, was ich hier behaupten, 1006 00:34:58,060 --> 00:35:02,250 ist das ist Selection Sort Lauf Es ist in der Größenordnung von n quadriert. 1007 00:35:02,250 --> 00:35:06,260 Im schlimmsten Fall, werde ich haben eine ganze Reihe von Zufallszahlen hier. 1008 00:35:06,260 --> 00:35:08,600 Und wie wir mathematisch gesehen, wenn ich halten zu Fuß 1009 00:35:08,600 --> 00:35:11,310 durch die Liste, durch die Liste, die Auswahl der nächstkleinere 1010 00:35:11,310 --> 00:35:14,410 Element wieder und wieder, wenn ich eigentlich notieren alle Schritte 1011 00:35:14,410 --> 00:35:18,750 Ich nehme, wie ich vorgeschlagen formel vor, dann ist es in der Größenordnung von n squared 1012 00:35:18,750 --> 00:35:20,370 Schritte, die ich nehme. 1013 00:35:20,370 --> 00:35:24,520 >> Und es stellt sich heraus, dass die Blase Art und Insertion Sort 1014 00:35:24,520 --> 00:35:27,370 sind genauso langsam im schlimmsten Fall. 1015 00:35:27,370 --> 00:35:32,040 Betrachten wir zum Beispiel Insertionsort, der letzte Algorithmus, den wir behandelt, 1016 00:35:32,040 --> 00:35:35,500 die hatten uns auf dem Element suchen, und dann legen Sie sie, wo es hingehört. 1017 00:35:35,500 --> 00:35:38,720 Und dann haben wir uns das nächste Element, und steckte ihn, wo es hingehört. 1018 00:35:38,720 --> 00:35:40,990 >> So betrachten die bestmögliche Szenario. 1019 00:35:40,990 --> 00:35:45,590 Angenommen, ich hatte meine Probanden antreten buchstäblich wie dieses, ein bis acht, 1020 00:35:45,590 --> 00:35:47,440 bereits sortiert. 1021 00:35:47,440 --> 00:35:51,300 Wie viele Schritte ist Insertion Sort dauern bis acht Personen sortieren, 1022 00:35:51,300 --> 00:35:55,640 wenn sie auf der Bühne zu gelangen so aussieht? 1023 00:35:55,640 --> 00:35:57,410 >> Acht Menschen bereits sortiert. 1024 00:35:57,410 --> 00:35:58,760 Und ich verwende Insertion Sort. 1025 00:35:58,760 --> 00:36:02,180 Das letzte der Algorithmen. 1026 00:36:02,180 --> 00:36:03,640 Nun, lassen Sie nachspielen wirklich schnell. 1027 00:36:03,640 --> 00:36:05,504 Also, wenn ich hier starten, sehe ich ein. 1028 00:36:05,504 --> 00:36:06,420 Wo findet man gehören? 1029 00:36:06,420 --> 00:36:07,730 Es gehört hier richtig. 1030 00:36:07,730 --> 00:36:08,330 Ich sehe zwei. 1031 00:36:08,330 --> 00:36:09,660 Wo kommt beiden gehören? 1032 00:36:09,660 --> 00:36:10,260 Genau hier. 1033 00:36:10,260 --> 00:36:10,900 Ich sehe drei. 1034 00:36:10,900 --> 00:36:11,920 Wo kommt drei gehören? 1035 00:36:11,920 --> 00:36:12,480 Genau hier. 1036 00:36:12,480 --> 00:36:13,100 >> Ich sehe vier. 1037 00:36:13,100 --> 00:36:13,600 Genau hier. 1038 00:36:13,600 --> 00:36:15,660 Fünf, sechs, sieben, acht. 1039 00:36:15,660 --> 00:36:17,320 Es gibt keinen Grund, mich zu wiederholen. 1040 00:36:17,320 --> 00:36:21,260 Und so, wie viele Schritte ist, dass in Bezug auf die n? 1041 00:36:21,260 --> 00:36:23,870 Es ist in der Größenordnung von n Schritte, nicht wahr? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Aber ich nahm einen linearen Nummer von Schritten, und jetzt bin ich fertig. 1043 00:36:27,567 --> 00:36:28,900 Also das ist der beste Fall, though. 1044 00:36:28,900 --> 00:36:29,983 Was ist mit dem schlimmsten Fall? 1045 00:36:29,983 --> 00:36:32,730 Welche acht waren dort, und sieben waren dort unten, 1046 00:36:32,730 --> 00:36:35,840 und eins und zwei waren hier, so dass die Liste wurden wirklich umgekehrt? 1047 00:36:35,840 --> 00:36:38,300 >> Nun, was tatsächlich geschieht, wenn dies die Zahl? 1048 00:36:38,300 --> 00:36:41,300 Und wir werden nur ein paar Beispiele zu tun. 1049 00:36:41,300 --> 00:36:49,300 Was ist, wenn in der Tat die Nummer acht ist hier, und die number-- hoppla. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 So was, wenn, ja, die Zahl acht ist den ganzen Weg hierher, 1052 00:36:56,430 --> 00:36:57,790 und ich bin mit Insertion Sort? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Ich behaupte, im Moment ist es an Ort und Stelle. 1055 00:37:00,280 --> 00:37:03,152 Aber jetzt, wo kommt seven-- sieben gehen? 1056 00:37:03,152 --> 00:37:04,360 Selbstverständlich geht es hier. 1057 00:37:04,360 --> 00:37:06,760 So habe ich mehr als ein Platz acht. 1058 00:37:06,760 --> 00:37:08,554 Jetzt sechs, wo geht es hin? 1059 00:37:08,554 --> 00:37:09,220 Nun, alles in Ordnung. 1060 00:37:09,220 --> 00:37:13,150 Nun, ich muss mehr als acht bewegen ein Ort, sieben mehr als einem Ort, 1061 00:37:13,150 --> 00:37:14,440 und dann plop ich mich sechs. 1062 00:37:14,440 --> 00:37:16,870 >> Also das erste Mal, es Kosten mich noch einen Schritt, um Dinge zu reparieren, 1063 00:37:16,870 --> 00:37:18,570 dann kostet mich zwei Schritte, um Dinge zu reparieren. 1064 00:37:18,570 --> 00:37:20,370 Wie viele Schritte ist es zu ergreifen, um zu beheben 1065 00:37:20,370 --> 00:37:22,720 Dinge zu fünf an der richtigen Stelle zu setzen? 1066 00:37:22,720 --> 00:37:23,340 Drei. 1067 00:37:23,340 --> 00:37:29,520 Denn jetzt habe ich bewegen ein, zwei, drei. 1068 00:37:29,520 --> 00:37:32,430 Wie viele Schritte wird es zu nehmen vier an der richtigen Stelle zu setzen? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6 plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> Und so ist es mathematisch identisch was wir für die Auswahl Art beschrieben. 1071 00:37:40,260 --> 00:37:42,130 Wir haben diese Serie das ist nur zu. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, oder umgekehrt, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 summiert sich für die heutige Zwecke in der Größenordnung von n quadriert. 1074 00:37:52,610 --> 00:37:57,640 >> Also lassen Sie mich auch, dass vor, Bubble-Sort ist auch in n quadriert. 1075 00:37:57,640 --> 00:38:01,340 Denn mit Bubble-Sort, jede Mal, wenn ich durch die Liste, 1076 00:38:01,340 --> 00:38:03,100 Ich nehme etwa, wie viele Schritte? 1077 00:38:03,100 --> 00:38:06,260 Jedes Mal, wenn ich buchstäblich zu Fuß von dort nach da? 1078 00:38:06,260 --> 00:38:07,960 Etwa n Schritte. 1079 00:38:07,960 --> 00:38:12,650 Aber wie oft ich könnte brauchen, um durch die Liste zu gehen? 1080 00:38:12,650 --> 00:38:13,920 >> Nun, etwa n Zeit. 1081 00:38:13,920 --> 00:38:15,680 Vielleicht n minus 1, aber in etwa n mal. 1082 00:38:15,680 --> 00:38:16,430 Nun, warum ist das so? 1083 00:38:16,430 --> 00:38:19,560 Nun, mit Bubble-Sort, wenn beginnen wir mit Bubble-Sort, 1084 00:38:19,560 --> 00:38:23,570 mit der Liste im schlimmsten Situation, die wiederum völlig 1085 00:38:23,570 --> 00:38:25,550 rückwärts, was passieren wird? 1086 00:38:25,550 --> 00:38:28,830 Ich gehe durch die Liste, und die Anzahl man gehört ganz drüben. 1087 00:38:28,830 --> 00:38:33,280 >> Aber mit Bubble-Sort, wie weit geht man bewegen an meinem ersten Durchlauf durch die Liste? 1088 00:38:33,280 --> 00:38:36,620 Wie viele Flecken bekommt er näher an der richtigen Stelle? 1089 00:38:36,620 --> 00:38:37,240 Nur einer. 1090 00:38:37,240 --> 00:38:40,281 Also, wenn Sie Art von Grund durch diese, jedes Mal, wenn durch diesen Algorithmus, 1091 00:38:40,281 --> 00:38:41,880 Davids unter etwa n Stufen. 1092 00:38:41,880 --> 00:38:44,940 Aber wie viele Pässe durch die Liste, ist es 1093 00:38:44,940 --> 00:38:49,060 gehen, um für ein bis Blase nehmen nach links, wo sie hingehört? 1094 00:38:49,060 --> 00:38:51,840 >> Er hat sich wie bewegen, n Bereiche auf diese Weise. 1095 00:38:51,840 --> 00:38:57,960 Also, nur um die Sortierung der Liste zu tun, Ich habe hin und her zu gehen n-mal. 1096 00:38:57,960 --> 00:39:01,540 Und jedes Mal, ich bin Blick auf n-Elemente. 1097 00:39:01,540 --> 00:39:05,410 So zu tun n Dinge, n-mal auf die Reihenfolge der n quadriert. 1098 00:39:05,410 --> 00:39:07,220 >> Nun, wir werden sehen, in einigen der Shorts, 1099 00:39:07,220 --> 00:39:10,440 sind in CS50 nächste Problem eingebettet gesetzt, einen anderen Ansatz zu diesen, 1100 00:39:10,440 --> 00:39:13,490 aber für jetzt, lass uns einfach betrachten einige andere Laufzeiten, 1101 00:39:13,490 --> 00:39:16,840 vor allem, wenn die Sortier diejenigen zu nehmen ein wenig Zeit zu sinken. 1102 00:39:16,840 --> 00:39:21,790 Was ist ein Algorithmus, die wir bereits gesehen haben das dauert in der Größenordnung von n Schritten? 1103 00:39:21,790 --> 00:39:27,560 >> Was soll eine lineare Reihe nehmen von Schritten, die wir bisher gesehen? 1104 00:39:27,560 --> 00:39:29,350 Was ist das? 1105 00:39:29,350 --> 00:39:30,480 Das Telefonbuch suchen. 1106 00:39:30,480 --> 00:39:31,390 Der erste Algorithmus. 1107 00:39:31,390 --> 00:39:31,560 Recht? 1108 00:39:31,560 --> 00:39:33,650 Wo wir sind linear Suche nach Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Tatsächlich. 1110 00:39:34,150 --> 00:39:37,180 Von Woche null, als ich anfing, Drehen einer Seite zu einer Zeit, 1111 00:39:37,180 --> 00:39:40,095 und ich habe sogar gesagt, dass es Art einer linearen Gefühl Algorithmus 1112 00:39:40,095 --> 00:39:42,720 und wir hatten das Bild auf die Board mit dem gerade rote Linie 1113 00:39:42,720 --> 00:39:44,678 und der gerade Gelb Linie, denen der Tat waren 1114 00:39:44,678 --> 00:39:46,810 Algorithmen, die in den großen O n sind. 1115 00:39:46,810 --> 00:39:50,680 >> Da Mike Smith in einem Telefon zu finden Buch der n-Seiten, im schlimmsten Fall, 1116 00:39:50,680 --> 00:39:52,422 könnte mich n Schritte zu unternehmen. 1117 00:39:52,422 --> 00:39:53,630 Was ist unter Teilnahme? 1118 00:39:53,630 --> 00:39:55,790 Eins zwei drei vier fünf sechs. 1119 00:39:55,790 --> 00:39:59,420 Was die Laufzeit diese Algorithmus, um die Anwesenheit? 1120 00:39:59,420 --> 00:40:03,070 Big O n, denn in der Theorie I muss jeder im Raum zu zeigen. 1121 00:40:03,070 --> 00:40:05,861 >> Jetzt als beiseite, was ist mit der weitere Optimierung von Woche Null? 1122 00:40:05,861 --> 00:40:08,117 Zwei, vier, sechs, acht, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Ein Informatiker würde zu realisieren, warten Sie eine Minute, 1124 00:40:10,200 --> 00:40:12,320 das ist in der Größenordnung von n von zwei Schritte unterteilt. 1125 00:40:12,320 --> 00:40:12,820 Recht? 1126 00:40:12,820 --> 00:40:14,444 Da mache ich zwei Personen auf einmal. 1127 00:40:14,444 --> 00:40:17,015 Aber wir werden ignoriert jene Terme niedrigerer Ordnung, 1128 00:40:17,015 --> 00:40:19,140 und wir sind gerade dabei, wegwerfen, die durch 2, 1129 00:40:19,140 --> 00:40:21,830 und nur sagen, große O n für diesen Algorithmus als auch. 1130 00:40:21,830 --> 00:40:22,760 >> Was ist mit diesem? 1131 00:40:22,760 --> 00:40:26,170 Wir werden übersprungen einige von ihnen, aber was war ein Algorithmus, der log n war? 1132 00:40:26,170 --> 00:40:29,900 Das dauerte etwa log n Schritte? 1133 00:40:29,900 --> 00:40:30,870 Die Teile und herrsche. 1134 00:40:30,870 --> 00:40:31,369 Genau. 1135 00:40:31,369 --> 00:40:33,900 Wie das Telefonbuch Beispiel in Woche Null und heute früh, 1136 00:40:33,900 --> 00:40:36,191 wo wir unterteilt das Problem wieder und wieder und wieder. 1137 00:40:36,191 --> 00:40:39,070 Wir zogen es auf dem Brett in der Woche Null als eine gekrümmte grüne Linie, 1138 00:40:39,070 --> 00:40:41,460 und wir sagten, dass Tag war es einen logarithmischen Algorithmus. 1139 00:40:41,460 --> 00:40:44,970 >> Und in der Tat ist die Anzahl der Schritte, die sie braucht, um divide durchzuführen und zu erobern, 1140 00:40:44,970 --> 00:40:48,610 oder binäre Suche, wie wir beginnen nannte es, wie im Telefonbuch, 1141 00:40:48,610 --> 00:40:50,680 liegt in der Grßenordnung von log und Stufen. 1142 00:40:50,680 --> 00:40:52,470 Und das ist ein bisschen wie ein sonderbares. 1143 00:40:52,470 --> 00:40:54,910 >> Was bringt einen Schritt, oder insbesondere 1144 00:40:54,910 --> 00:40:56,240 eine konstante Anzahl von Schritten? 1145 00:40:56,240 --> 00:40:58,865 Vielleicht ist es zwei, vielleicht ist es drei, aber ein Informatiker nur 1146 00:40:58,865 --> 00:41:01,423 vereinfacht es so groß O von 1, einige konstante Anzahl von Schritten. 1147 00:41:01,423 --> 00:41:04,256 Was ist etwas, was Sie tun könnten nimmt eine konstante Anzahl von Schritten? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Was ist die Laufzeit klatschen? 1150 00:41:10,930 --> 00:41:11,920 Konstante Zeit. 1151 00:41:11,920 --> 00:41:12,420 Recht? 1152 00:41:12,420 --> 00:41:15,490 Wie, was ist die Laufzeit alles, was nur einem statt tun 1153 00:41:15,490 --> 00:41:18,570 Betrieb, wie zu drucken F Hallo Welt. 1154 00:41:18,570 --> 00:41:24,110 Das könnte die konstante Zeit sein werden, es sei denn, weniger Ecke Fall mit Druck F, 1155 00:41:24,110 --> 00:41:28,260 Was könnten die Laufzeit Druck F eigentlich sein? 1156 00:41:28,260 --> 00:41:28,790 Und warum? 1157 00:41:28,790 --> 00:41:30,550 Was ist n Mess in diesem Fall? 1158 00:41:30,550 --> 00:41:32,251 >> ZIELGRUPPE: [unverständlich]. 1159 00:41:32,251 --> 00:41:33,250 David J. MALAN: Genau. 1160 00:41:33,250 --> 00:41:34,900 Die Anzahl der Zeichen Wir drucken möchten. 1161 00:41:34,900 --> 00:41:36,191 Es ist also sehr kontextabhängig. 1162 00:41:36,191 --> 00:41:39,910 Heute, wir haben konzentriert eine Menge auf Buchstaben und Zahlen hier auf dem Brett. 1163 00:41:39,910 --> 00:41:43,540 Aber es könnte auch sein, Zeichen in einer tatsächlichen String. 1164 00:41:43,540 --> 00:41:46,420 So stellt sich heraus gibt es eine andere Maßnahme, die beginnen wird die Sorge um, 1165 00:41:46,420 --> 00:41:48,530 und das ist das Gegenteil von Big O, so zu sprechen. 1166 00:41:48,530 --> 00:41:50,120 >> Das Omega-Notation. 1167 00:41:50,120 --> 00:41:53,380 Wohingegen große O bedeutet, was ist, die Ober auf Ihrer Laufzeit gebunden? 1168 00:41:53,380 --> 00:41:55,580 Maximal, wie viel Zeit könnte etwas dauern? 1169 00:41:55,580 --> 00:41:59,250 Omega-- leid, dies kommt immer up-- ist das Gegenteil von dem, 1170 00:41:59,250 --> 00:42:02,960 wobei es ein tiefer auf das gebundene Höhe der Zeit etwas könnten. 1171 00:42:02,960 --> 00:42:10,480 >> Also. zum Beispiel, was ist ein Algorithmus das dauert immer n quadriert Schritte? 1172 00:42:10,480 --> 00:42:15,600 Nun, einer der Algorithmen, die wir gesehen haben Heute, in der Tat könnte das so gut sein. 1173 00:42:15,600 --> 00:42:16,720 Selection Art. 1174 00:42:16,720 --> 00:42:18,270 Selection Art ist ziemlich dumm. 1175 00:42:18,270 --> 00:42:21,760 Selbst wenn die algorithm-- leid, auch wenn das Array bereits sortiert ist, 1176 00:42:21,760 --> 00:42:24,150 Auswahl Sortierung zu gehen halten zu Fuß durch die Liste 1177 00:42:24,150 --> 00:42:28,907 um sicherzustellen, dass es die kleinste Element immer wieder und wieder. 1178 00:42:28,907 --> 00:42:31,740 Und auch wenn man Menschen in der Publikum wissen, dass, warten Sie eine Minute, 1179 00:42:31,740 --> 00:42:33,948 Sie bereits die kleinste Element, das Computer 1180 00:42:33,948 --> 00:42:37,300 nicht weiß, dass, bis es sieht den ganzen Weg durch die Liste. 1181 00:42:37,300 --> 00:42:40,240 Ebenso ist eine geringere, dass gebunden kann auch berücksichtigt werden, 1182 00:42:40,240 --> 00:42:42,000 könnte lineare Zeit. 1183 00:42:42,000 --> 00:42:48,260 >> Wie lange dauert es zu ergreifen, sort n Elemente in der besten 1184 00:42:48,260 --> 00:42:52,420 Fall mit so etwas wie Bubble-Sort? 1185 00:42:52,420 --> 00:42:54,280 Nehmen wir an, Ihre Liste bereits sortiert ist. 1186 00:42:54,280 --> 00:42:56,696 Wir haben gesagt, Bubble-Sort nimmt die Reihenfolge der Schritte n quadriert. 1187 00:42:56,696 --> 00:42:59,640 Aber was, wenn es bereits sortiert? 1188 00:42:59,640 --> 00:43:02,310 Was, wenn Sie nach dem erkennen, einem Durchgang durch das Array 1189 00:43:02,310 --> 00:43:03,540 dass Sie keine Swaps gemacht haben? 1190 00:43:03,540 --> 00:43:05,970 Müssen Sie halten Sie macht mehr Durchläufe? 1191 00:43:05,970 --> 00:43:06,470 >> Nein. 1192 00:43:06,470 --> 00:43:10,340 So eine untere Schranke für Bubble-Sort gebunden könnte die linear ist. 1193 00:43:10,340 --> 00:43:11,830 Omega von n. 1194 00:43:11,830 --> 00:43:14,450 Und wir können betrachten andere von ihnen als gut. 1195 00:43:14,450 --> 00:43:17,990 Werfen wir also einen Blick bei nur einer Visualisierung hier 1196 00:43:17,990 --> 00:43:20,790 zu sehen, wie diese selbst zu unterscheiden. 1197 00:43:20,790 --> 00:43:24,592 Ich werde hier unten in diese zu gelangen Seite, die auf C50-Website verfügbar ist, 1198 00:43:24,592 --> 00:43:27,550 aber es wird ein Schmerz zusammen, um zu bekommen, da er verwendet eine Technologie namens 1199 00:43:27,550 --> 00:43:30,560 Java-Applets, die a weitgehend nicht unterstützte in diesen Tagen, 1200 00:43:30,560 --> 00:43:32,730 zumindest von Chrom und bestimmte andere. 1201 00:43:32,730 --> 00:43:37,070 >> Und lassen Sie mich gehen Sie vor und beschleunigen diese und erklären, was vor sich geht. 1202 00:43:37,070 --> 00:43:40,840 Dies ist eine Demonstration von Blasen Art, der erste Algorithmus sahen wir uns an. 1203 00:43:40,840 --> 00:43:43,950 Und es ist eine Visualisierung, daß jedes dieser Stäbe eine Zahl. 1204 00:43:43,950 --> 00:43:45,710 Je größer der Balken, Je größer die Zahl. 1205 00:43:45,710 --> 00:43:47,520 Je kleiner der Bar, je kleiner die Zahl ist. 1206 00:43:47,520 --> 00:43:50,353 Und was Sie visuell sehen kann, auch aber das wird super schnell, 1207 00:43:50,353 --> 00:43:53,699 ist, dass der rote Balken ist wie ich, zu Fuß hin und her, Behebung von Problemen. 1208 00:43:53,699 --> 00:43:56,740 Sie können, dass die größere Elemente zu sehen tatsächlich sprudeln nach rechts, 1209 00:43:56,740 --> 00:43:59,650 und die kleineren Elemente sind an den linken sprudeln. 1210 00:43:59,650 --> 00:44:01,870 Und hier unten, wenn wir tatsächlich näher betrachten, 1211 00:44:01,870 --> 00:44:04,330 können wir tatsächlich zählen die Anzahl der Vergleiche und Swaps 1212 00:44:04,330 --> 00:44:05,350 dass gemacht wurden. 1213 00:44:05,350 --> 00:44:07,360 >> Aber anstatt, lassen Sie uns beim zweiten Algorithmus 1214 00:44:07,360 --> 00:44:11,240 betrachteten wir früher mit unseren Freiwillige, die Auswahl sortieren. 1215 00:44:11,240 --> 00:44:13,500 Optisch hat sie ein sehr unterschiedliche Wirkung. 1216 00:44:13,500 --> 00:44:16,820 Aber es ist wiederum sehr intuitiv, in dass wir halten die Auswahl des nächsten kleinsten 1217 00:44:16,820 --> 00:44:18,660 Element, und wir haben ein wenig Glück. 1218 00:44:18,660 --> 00:44:20,110 Das fühlte sich grundsätzlich schneller. 1219 00:44:20,110 --> 00:44:22,840 Wenn wir aber lief das immer wieder und immer wieder mit vielen Eingängen, 1220 00:44:22,840 --> 00:44:26,680 würden wir sehen, dass es in der Tat noch in großen O n quadriert. 1221 00:44:26,680 --> 00:44:29,920 >> Lassen Sie uns eine letzte hier, Insertion Sort, 1222 00:44:29,920 --> 00:44:33,180 wobei der dritte Algorithmus sahen wir uns an, und Rückruf 1223 00:44:33,180 --> 00:44:36,700 dass dies eine befasst sich mit der Elemente, wie es ihnen begegnet, 1224 00:44:36,700 --> 00:44:39,290 aber dann ist es vielleicht Verschiebungen Dinge immer um Platz zu machen, 1225 00:44:39,290 --> 00:44:41,660 Einfügen von Elementen, wo sie hingehören. 1226 00:44:41,660 --> 00:44:45,330 >> Und auch dies endet geben die Endergebnis. Nun sind alle drei von denen, 1227 00:44:45,330 --> 00:44:46,490 fühlte sich ziemlich schnell. 1228 00:44:46,490 --> 00:44:48,740 Und in der Tat, ich lief davon an einem ziemlich gut Clip. 1229 00:44:48,740 --> 00:44:52,510 Aber im Grunde sind sie alle ziemlich schrecklich, um ehrlich zu sein. 1230 00:44:52,510 --> 00:44:56,960 Alle diese Algorithmen bisher dass Lauf in großen O n quadriert 1231 00:44:56,960 --> 00:44:59,270 nehmen ziemlich viel Zeit, um am Ende laufen. 1232 00:44:59,270 --> 00:45:01,920 >> Und in der Tat, können wir sehen, und denken, dass dies schließlich 1233 00:45:01,920 --> 00:45:04,090 wenn ich nach oben ziehen diese dritte und letzte Demo. 1234 00:45:04,090 --> 00:45:05,840 Dies ist ein weiterer Visualisierung Das wird 1235 00:45:05,840 --> 00:45:08,500 zu Bubble Sort auf der linken Seite zeigen, Auswahl Art in der Mitte, 1236 00:45:08,500 --> 00:45:13,410 und etwas, als eine unserer Hand hebt früher vorgeschlagen, 1237 00:45:13,410 --> 00:45:15,020 Mergesort auf der rechten Seite. 1238 00:45:15,020 --> 00:45:16,937 A Teile und Herrsche Strategie auf der rechten Seite. 1239 00:45:16,937 --> 00:45:19,520 Und das ist in der Tat, was wir werde am Mittwoch zu suchen. 1240 00:45:19,520 --> 00:45:21,990 Aber lassen Sie uns Zeit, um diese parallel laufen. 1241 00:45:21,990 --> 00:45:26,765 Es ist etwa die gleiche Anzahl von Elemente, die alle laufen zur gleichen Zeit. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble-Sort vs Auswahl Art vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Nun, sie alle laufen in der Theorie zur gleichen Zeit. 1245 00:45:36,760 --> 00:45:39,830 Die CPU läuft an mit der gleichen Geschwindigkeit, aber man 1246 00:45:39,830 --> 00:45:44,014 fühlen kann, wie langweilig das ist sehr schnell los zu werden, 1247 00:45:44,014 --> 00:45:45,930 und wie schnell, wenn Wir spritzen ein wenig Woche 1248 00:45:45,930 --> 00:45:49,330 Algorithmen, die Null kann wir Dinge zu beschleunigen. 1249 00:45:49,330 --> 00:45:51,760 >> Und jetzt vergleichen lassen diese in eine letzte Form. 1250 00:45:51,760 --> 00:45:55,710 Ich werde weitermachen In den CS50-Website, wo 1251 00:45:55,710 --> 00:45:59,020 Wir haben dieses letzte Glied für heute, wo jemand auf dem Internet 1252 00:45:59,020 --> 00:46:03,960 kindly zusammen ein Video, erfasst, was verschiedene Sortier 1253 00:46:03,960 --> 00:46:07,510 Algorithmen klingen. 1254 00:46:07,510 --> 00:46:09,577 Dies ist Insertion Sort. 1255 00:46:09,577 --> 00:46:12,072 >> [PIEPTON] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Wobei Sie Anlegen einer Frequenz sind auf der Grundlage der Höhe des Balkens bar. 1258 00:46:16,850 --> 00:46:19,826 Dies ist Bubble Sort. 1259 00:46:19,826 --> 00:46:21,822 >> [WARPED PIEPTON] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Termine der nächsten ist-- kommen up next ist-- Selection Sort, 1262 00:46:45,774 --> 00:46:48,820 wo wieder, wir Auswählen der nächste kleinste Element, 1263 00:46:48,820 --> 00:46:51,820 und wir können sehen, es wächst von links nach rechts. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, unser Favorit bisher noch heute. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Beachten Sie, wie es teilenden Dinge in [unverständlich] die Hälfte und Viertel. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome sortiert, das haben wir nicht darüber gesprochen, und schafft optisch 1270 00:47:21,660 --> 00:47:24,450 und audally ein bisschen ein unterschiedliche Form und Ton. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Hin und her, Reinigung Dinge. 1273 00:47:30,160 --> 00:47:32,230 Sie können auch Heapsort auf der Internetseite dieses Kerls. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Und das ist es. 1276 00:47:36,810 --> 00:47:38,210 Wir werden Sie sehen, das nächste Mal. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing UND MUSIK] 1279 00:47:48,334 --> 00:50:24,839