1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPRECHER: In Ordnung, das ist CS50. 3 00:00:14,910 --> 00:00:19,020 Dies ist das Ende der dritten Woche und wenn Sie nutzen bereits genommen haben, 4 00:00:19,020 --> 00:00:21,790 wissen, dass es Mittagessen an diesem Freitag wie üblich, wo 5 00:00:21,790 --> 00:00:25,430 Sie gutes Gespräch genießen können und Essen am Feuer und Eis 6 00:00:25,430 --> 00:00:27,980 mit einigen der CS50 Personal und Klassenkameraden. 7 00:00:27,980 --> 00:00:30,170 Kopf dieser URL hier. 8 00:00:30,170 --> 00:00:33,420 >> Jetzt können Sie sich erinnern, oder Sie bald kennen werden, 9 00:00:33,420 --> 00:00:35,970 diese Dinge hier, die sind am Ende gegeben 10 00:00:35,970 --> 00:00:37,850 des Semesters für viele Klassen. 11 00:00:37,850 --> 00:00:40,870 So genannte Prüfung blauen Bücher, in denen Sie schreiben Ihre Antworten auf Prüfungen. 12 00:00:40,870 --> 00:00:44,240 Jetzt habe ich hier 26, so blaue Bücher, auf jeden von ihnen 13 00:00:44,240 --> 00:00:47,580 ein Name, A bis Z. geschrieben und in der Tat die Namen sind so einfach, A 14 00:00:47,580 --> 00:00:50,490 bis Z. Und einer der die Ziele bei der Hand heute 15 00:00:50,490 --> 00:00:53,910 sein wird das fortsetzen, was begannen wir am Montag, was nicht 16 00:00:53,910 --> 00:00:57,830 so viel Blick auf Code, aber wirklich Blick auf Ideen und Problemlösungen. 17 00:00:57,830 --> 00:01:00,170 Eines der Ziele und Versprechungen des Kurses 18 00:01:00,170 --> 00:01:02,985 ist es, Sie zu lehren, mehr denken vorsichtig, mehr methodisch, 19 00:01:02,985 --> 00:01:05,400 und Probleme effizienter zu lösen. 20 00:01:05,400 --> 00:01:09,526 Und in der Tat, können wir das wirklich tun ohne auch nur zu berühren eine Zeile Code. 21 00:01:09,526 --> 00:01:12,150 So habe ich ein paar Elefanten bis heute hier, orange und blau, 22 00:01:12,150 --> 00:01:15,780 wenn wir einen Freiwilligen zu bekommen, vielleicht von weiter hinten als üblich. 23 00:01:15,780 --> 00:01:18,070 Wie wäre es recht, kommen auf Sie. 24 00:01:18,070 --> 00:01:24,180 Das Ziel davon wird zu sein Hilfe und verwalten diese Prüfung hier. 25 00:01:24,180 --> 00:01:24,935 Wie heißen Sie? 26 00:01:24,935 --> 00:01:25,768 >> ZIELGRUPPE: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPRECHER: Mary Beth, komm auf. 28 00:01:27,560 --> 00:01:29,560 Lassen Sie mich das Mikrofon für Sie da. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Freut mich, dich kennenzulernen. 31 00:01:32,880 --> 00:01:34,005 >> ZIELGRUPPE: Nice to meet you. 32 00:01:34,005 --> 00:01:36,790 SPRECHER: In Ordnung, so habe ich hier blaue Bücher von A bis Z, 33 00:01:36,790 --> 00:01:41,680 und ich werde das tun, Ich habe eine der Schülerinnen, 34 00:01:41,680 --> 00:01:45,770 und sie sind in etwas zufällig kommen am Ende der drei Stunden Prüfungsblock, 35 00:01:45,770 --> 00:01:49,400 so dass sie schließlich in einige semi-zufälliger Reihenfolge wie diese. 36 00:01:49,400 --> 00:01:54,510 Jetzt ist Ihre Aufgabe in nur einem Augenblick wird zu BE-- dies ist tatsächlich, wie sie bekommen 37 00:01:54,510 --> 00:01:56,820 in am Ende des einge die Klasse, die meisten wahrscheinlich. 38 00:01:56,820 --> 00:02:01,120 Ihre Aufgabe jetzt sein wird, ganz einfach, um diese blauen Bücher für uns sortieren 39 00:02:01,120 --> 00:02:05,220 von A bis Z. 40 00:02:05,220 --> 00:02:08,400 >> ZIELGRUPPE: Oh, das ist für immer zu nehmen. 41 00:02:08,400 --> 00:02:13,747 >> SPRECHER: Und wir werden sehen wie Sie dies tun, keinen Druck. 42 00:02:13,747 --> 00:02:15,330 ZIELGRUPPE: Nein, kein Druck oder nichts. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPRECHER: Und für Spaß, lassen wir einen Timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> ZIELGRUPPE: So viel Spaß, so viel Spaß. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPRECHER: Ich kann das Mikrofon für Sie zu halten. 49 00:02:38,574 --> 00:02:40,240 Alles klar, haben wir gerade verdoppelt Geschwindigkeit. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 So in der Zwischenzeit lassen Sie mich darstellen, was werde die Frage nach Mary Beth sein 52 00:02:49,060 --> 00:02:51,540 ist das, was sie tun, wie ist sie über die Lösung dieses hin? 53 00:02:51,540 --> 00:02:54,040 Und in der Tat, haben Sie möglicherweise nicht jemals über etwas gedacht 54 00:02:54,040 --> 00:02:57,440 so einfach, wie wenn Sie holen bis 26 Bücher wie dieses, 55 00:02:57,440 --> 00:02:59,350 die haben einen natürlichen Bestellung zu ihnen. 56 00:02:59,350 --> 00:03:01,335 Was das Verfahren dass Sie tatsächlich nutzen? 57 00:03:01,335 --> 00:03:03,770 Ist es ziemlich zufällig gerade Kommissionierung der erste Sie sehen 58 00:03:03,770 --> 00:03:05,250 und legt es an seiner Stelle? 59 00:03:05,250 --> 00:03:09,680 Haben Sie zuerst Ihre Hände bewegen Suche nach einem dann auf der Suche nach B? 60 00:03:09,680 --> 00:03:11,722 Haben Sie einen Blick auf eine nehmen Paar von nebeneinander 61 00:03:11,722 --> 00:03:14,680 und einfach sagen, warten Sie eine Minute, dieses ist nicht richtig, und dann tauschen die Reihenfolge? 62 00:03:14,680 --> 00:03:16,960 Wir sahen bereits am Montag, dass es eine Reihe von Möglichkeiten, 63 00:03:16,960 --> 00:03:22,140 in dem wir dies tun, und in der Tat, wie wir am Ende hier, 64 00:03:22,140 --> 00:03:26,360 Ich möchte darauf hinweisen, vielleicht nehmen von dem, was Mary Beth tut. 65 00:03:26,360 --> 00:03:30,040 Wir haben ein paar Pfähle so scheint es, ein größer eins, drei kleinere. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> ZIELGRUPPE: Ich bestelle sie wenn ich zwei Buchstaben 68 00:03:36,415 --> 00:03:39,540 dass ich weiß, sind zusammen in einer Sequenz, Ich legte sie zusammen, so dass ich nicht 69 00:03:39,540 --> 00:03:42,915 müssen über das Halten Sorgen Spur von einer ganzen Reihe von Pfund. 70 00:03:42,915 --> 00:03:45,706 Es ist nur, oh, A ist die erste, Ich habe diesen Stapel hier. 71 00:03:45,706 --> 00:03:47,580 SPRECHER: So, fast wie Ein Puzzle-Stücke, die 72 00:03:47,580 --> 00:03:49,860 haben die richtige Form, um passen miteinander. 73 00:03:49,860 --> 00:03:51,026 ZIELGRUPPE: Ziemlich viel, ja. 74 00:03:51,026 --> 00:03:55,320 SPRECHER: OK, ausgezeichnet. 75 00:03:55,320 --> 00:03:59,850 Und nun jede dieser Pfähle vermutlich sortiert? 76 00:03:59,850 --> 00:04:00,990 >> ZIELGRUPPE: Ja. 77 00:04:00,990 --> 00:04:09,900 >> SPRECHER: In Ordnung, A bis Z. Alle Recht herzlichen Glückwunsch, du hast es geschafft. 78 00:04:09,900 --> 00:04:11,461 Sie haben Ihre Wahl. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Alles klar, vielen Dank dafür. 81 00:04:13,530 --> 00:04:16,679 So Mary Beth hat vorschlagen was ihr Ansatz war, 82 00:04:16,679 --> 00:04:19,720 aber was ist ein weiterer Ansatz, wie Sie könnte über das Sortieren, diese Dinge gehen? 83 00:04:19,720 --> 00:04:21,130 Was hätten Sie getan? 84 00:04:21,130 --> 00:04:24,060 Der Rekord zu schlagen gewesen wäre, einer Minute und 50 Sekunden oder so, 85 00:04:24,060 --> 00:04:26,039 und die, die ich vergessen zu zählen. 86 00:04:26,039 --> 00:04:27,080 Was hätten Sie getan? 87 00:04:27,080 --> 00:04:27,579 Ja? 88 00:04:27,579 --> 00:04:28,735 ZIELGRUPPE: Nehmen Sie den Stapel. 89 00:04:28,735 --> 00:04:29,776 Starten Sie von Anfang an. 90 00:04:29,776 --> 00:04:32,284 Überprüfen Sie Ihre Papiere. 91 00:04:32,284 --> 00:04:36,586 Und wenn der oberste höher ist als, vielleicht sind sie, 92 00:04:36,586 --> 00:04:38,980 die untere ist höher, dann schalten Sie sie. 93 00:04:38,980 --> 00:04:41,300 >> SPRECHER: OK, also ab an der Oberseite und der Unterseite, 94 00:04:41,300 --> 00:04:43,716 und dann arbeiten Sie Ihren Weg nach innen so, Tausch? 95 00:04:43,716 --> 00:04:46,580 OK, so ein wenig ähnlich im Geist zu Bubble-Sort, 96 00:04:46,580 --> 00:04:49,160 Aber die Wahl der Extreme nicht die benachbarten Paare. 97 00:04:49,160 --> 00:04:52,080 Aber die Rede kurzer Sinn ist, dass es sicherlich eine Reihe von verschiedenen Möglichkeiten, 98 00:04:52,080 --> 00:04:54,210 wir könnten dies tun, und ehrlich gesagt, ich glaube, Sie Art von 99 00:04:54,210 --> 00:04:55,700 angenommen ein paar Ansätze, oder? 100 00:04:55,700 --> 00:05:00,567 Sie haben Art vier sortierten Haufen, und dann effektiv zusammengeführt sie zusammen. 101 00:05:00,567 --> 00:05:02,650 Und das ist, wage zu behaupten, ein anderer Technik überhaupt. 102 00:05:02,650 --> 00:05:06,950 Sie nicht behandeln es als einen großen Haufen, Sie das Problem aufgeteilt in vier Quads, 103 00:05:06,950 --> 00:05:09,820 wenn man will, und dann irgendwie verschmolzen sie am Ende. 104 00:05:09,820 --> 00:05:13,410 >> So betrachten wir letztlich Wie sonst könnten wir das tun. 105 00:05:13,410 --> 00:05:15,860 Wir formalisiert den Begriff von Bubble-Sort letzten Mal, 106 00:05:15,860 --> 00:05:18,780 und Bubble-Sort Rückruf war ein Algorithmus, die wir visualisiert 107 00:05:18,780 --> 00:05:22,640 mit acht von Ihren Klassenkameraden hier oben, scheinbar zufällig auf den ersten sortiert. 108 00:05:22,640 --> 00:05:26,110 Und wir dann beschlossen, paarweise, wenn zwei Elemente sind nicht in Ordnung, 109 00:05:26,110 --> 00:05:26,950 einfach tauschen sie. 110 00:05:26,950 --> 00:05:28,930 So vier und zwei offensichtlich nicht in Ordnung, 111 00:05:28,930 --> 00:05:31,080 so die beiden Klassenkameraden Schaltstellungen. 112 00:05:31,080 --> 00:05:35,390 Und dann wiederholt man mit vier bis sechs, dann sechs und acht, bei jeder Iteration, 113 00:05:35,390 --> 00:05:36,980 Bewegen nach rechts. 114 00:05:36,980 --> 00:05:42,590 >> So gegeben acht Personen, wie viele paarweise Vergleiche habe ich getan, beim Gehen von 115 00:05:42,590 --> 00:05:45,220 In einer solchen Iteration von links nach rechts? 116 00:05:45,220 --> 00:05:48,410 Wie viele Vergleiche? 117 00:05:48,410 --> 00:05:49,197 Sieben, oder? 118 00:05:49,197 --> 00:05:51,405 Denn wenn es acht Personen, aber Sie haben das Paar 119 00:05:51,405 --> 00:05:53,880 sie und halten Sie in Bewegung einen Sprung nach rechts, 120 00:05:53,880 --> 00:05:56,060 du wirst doch nicht um acht haben Vergleiche, da kann man nicht vergleichen 121 00:05:56,060 --> 00:05:59,226 ein Element mit sich selbst, oder es würde nur sinnlos, so dass Sie sieben haben. 122 00:05:59,226 --> 00:06:01,290 Oder allgemeiner, wenn wir haben n Personen, die wir 123 00:06:01,290 --> 00:06:04,300 tun n minus 1 Vergleiche mit Bubble-Sort. 124 00:06:04,300 --> 00:06:08,150 >> Also lassen Sie uns jetzt überlegen, wie gut oder schlechte Blase Art tatsächlich war, und versuchen 125 00:06:08,150 --> 00:06:13,570 Wortschatz, um uns mit zu geben Algorithmen, die Kritik wie diese, 126 00:06:13,570 --> 00:06:14,430 und bald unsere eigenen. 127 00:06:14,430 --> 00:06:16,970 So im ersten Durchgang durch Blasensortierung, die erstmals 128 00:06:16,970 --> 00:06:20,909 Ich ging von links nach rechts über die Bühne, nahm mich n minus 1 Vergleiche. 129 00:06:20,909 --> 00:06:22,950 Und das wird mein Maßeinheit, oder? 130 00:06:22,950 --> 00:06:26,170 Ich war irgendwie reden und Bummeln, etwas schnell, etwas langsam, 131 00:06:26,170 --> 00:06:29,300 so Zählen meine Anzahl von Sekunden ist nicht besonders zu sagen, 132 00:06:29,300 --> 00:06:32,260 aber Zählen der Anzahl von Operationen, die ich am Montag getan hat, 133 00:06:32,260 --> 00:06:35,900 Vergleich von zwei Menschen, das fühlt sich wie eine schöne Maßeinheit. 134 00:06:35,900 --> 00:06:40,980 >> So n minus 1 Schritte das erste Mal, aber was dann passiert danach? 135 00:06:40,980 --> 00:06:46,610 Was ist die eine auf den Kopf von einem Durchgang durch eine ansonsten unsortierten Liste? 136 00:06:46,610 --> 00:06:49,840 Was können Sie mir über das Element , die den ganzen Weg über da war? 137 00:06:49,840 --> 00:06:51,300 Ja? 138 00:06:51,300 --> 00:06:52,870 Das war die größte Element, oder? 139 00:06:52,870 --> 00:06:55,710 Nummer acht, obwohl sie hier begann, jedes Mal wenn ich 140 00:06:55,710 --> 00:06:57,860 verglichen sie gegen ein Nachbar, hielt sie 141 00:06:57,860 --> 00:07:00,480 sprudeln rechts Seite der Liste. 142 00:07:00,480 --> 00:07:02,710 Und in der Tat, das ist, wo der Algorithmus erhält seinen Namen. 143 00:07:02,710 --> 00:07:07,630 >> Nun von dieser Logik, wie viele Vergleiche muss ich auf dem zweiten Mal machen 144 00:07:07,630 --> 00:07:09,800 Ich mache diesen Pass von links nach rechts? 145 00:07:09,800 --> 00:07:10,730 n minus 2, oder? 146 00:07:10,730 --> 00:07:14,297 Es wäre nur verschwenden meine Zeit, wenn ich halten den Vergleich acht gegen jemanden 147 00:07:14,297 --> 00:07:16,630 sonst, weil wir bereits wissen, sie war an der richtigen Stelle. 148 00:07:16,630 --> 00:07:19,760 Also das ist ein bisschen ein Optimierung, so dass der nächste Pass 149 00:07:19,760 --> 00:07:23,899 sein wird, plus n minus zwei Schritten, wobei n die Anzahl der Personen. 150 00:07:23,899 --> 00:07:26,940 Jetzt können Sie Art von extrapolieren, auch wenn Sie nicht gerade ein Computerwissenschaftler, 151 00:07:26,940 --> 00:07:27,680 wie das endet. 152 00:07:27,680 --> 00:07:31,259 Am Ende dieses Algorithmus, vermutlich Sie nur einen Vergleich links haben. 153 00:07:31,259 --> 00:07:33,800 Sie müssen die Art der Fixierung Anfang der Liste bei zwei 154 00:07:33,800 --> 00:07:36,540 und eins sind in Ordnung und sollte eins und zwei ist, 155 00:07:36,540 --> 00:07:40,330 so dass diese Talsohle bei plus 1 abschließenden Vergleich. 156 00:07:40,330 --> 00:07:44,500 >> Jetzt ist der Punkt, Punkt, Punkt Art von Wellen, es ist Hände auf einige der Details saftiger, 157 00:07:44,500 --> 00:07:46,452 aber lasst uns einfach weitermachen und zu vereinfachen. 158 00:07:46,452 --> 00:07:48,660 Wenn Sie von hohen erinnern Schule, ehrlich gesagt, eine Menge von euch 159 00:07:48,660 --> 00:07:50,340 hatte Mathe Bücher, die hatte ein wenig Spickzettel 160 00:07:50,340 --> 00:07:52,550 an der Frontabdeckung oder der Rückseite, die Sie zeigte 161 00:07:52,550 --> 00:07:56,400 Welche Serie Summen wie dies letztlich bis zu hinzugefügt. 162 00:07:56,400 --> 00:07:59,600 Im allgemeinen Fall, wenn Sie eine Variable wie n, und zwar diese, 163 00:07:59,600 --> 00:08:01,634 wenn man sich sah Ihre alten Schule Mathebuch, 164 00:08:01,634 --> 00:08:04,050 Sie, dass dieser tatsächlich sehen würde fügt bis zu dieser Summe hier, 165 00:08:04,050 --> 00:08:07,970 n mal n minus 1 Alle durch 2 geteilt. 166 00:08:07,970 --> 00:08:11,172 So jetzt lassen Sie mich nur vor, dies wahr ist, so auf einen Sprung des Glaubens, 167 00:08:11,172 --> 00:08:12,880 das ist, was ist das Fazit bis zu, und wir konnten 168 00:08:12,880 --> 00:08:14,341 beweisen, dass in einem allgemeinen Fall. 169 00:08:14,341 --> 00:08:15,590 Aber jetzt wollen wir erweitern dies. 170 00:08:15,590 --> 00:08:19,920 Lassen Sie uns also multiplizieren dies aus, so ist das n quadriert, minus n, die alle durch 2 geteilt. 171 00:08:19,920 --> 00:08:23,200 Das ist wirklich n quadriert, dividiert durch 2 minus n als 2, 172 00:08:23,200 --> 00:08:25,010 so, das ist alles schön und interessant. 173 00:08:25,010 --> 00:08:27,060 Aber was passiert, wenn wir Plug-In einen Wert? 174 00:08:27,060 --> 00:08:29,724 Angenommen, ich hatte nicht acht Menschen, aber sagen, eine Million. 175 00:08:29,724 --> 00:08:31,890 Und eine Million, nur weil es ist eine ziemlich große Zahl, 176 00:08:31,890 --> 00:08:34,039 wir stecken, die in und sehen was passiert. 177 00:08:34,039 --> 00:08:39,039 Also, wenn ich eine Million Plug in dieser Formel Ich werde zu einer Million quadriert, 178 00:08:39,039 --> 00:08:42,868 dividiert durch 2 minus ein Millionen, geteilt durch 2 ist. 179 00:08:42,868 --> 00:08:44,159 Nun, was das ist, werde gleich? 180 00:08:44,159 --> 00:08:47,354 So 500 Milliarden, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 Und wenn ich tatsächlich tun dass Mathematik aus, dass Mittel 182 00:08:49,270 --> 00:08:53,920 dass die Sortierung eine Million Menschen mit dem Bubble-Sort 183 00:08:53,920 --> 00:09:01,800 könnte mir nehmen 499999500000 Schritte oder Vergleiche am Ende, 184 00:09:01,800 --> 00:09:02,900 wir sind nur zu extrapolieren. 185 00:09:02,900 --> 00:09:06,860 >> Das fühlt sich ziemlich langsam, aber ehrlich gesagt Messen von einem bestimmten Eingang 186 00:09:06,860 --> 00:09:09,160 wie dieser, ist gar nicht so aufschlussreich. 187 00:09:09,160 --> 00:09:14,050 Aber in der Tat darauf hin, dass es sich als n wird größer und größer, diesen Algorithmus 188 00:09:14,050 --> 00:09:16,280 Art fühlt sich schlechter und schlimmer noch, oder Sie wirklich 189 00:09:16,280 --> 00:09:20,450 starten, um den Schmerz fühlen, dass Potenzierung, quadriert, dass n, 190 00:09:20,450 --> 00:09:21,770 das summiert sich ziemlich schnell. 191 00:09:21,770 --> 00:09:25,340 Und dieses Detail ist nicht verloren auf Menschen in der Tat 192 00:09:25,340 --> 00:09:29,640 vor einigen Jahren ein gewisser Senator, war Wahlkampf, setzte sich für ein Interview 193 00:09:29,640 --> 00:09:32,180 mit Googles Eric Schmidt, CEO an der Zeit, 194 00:09:32,180 --> 00:09:36,380 und wurde mit einer Frage herausgefordert ähnlich wie wir heute erkunden. 195 00:09:36,380 --> 00:09:38,468 Lassen Sie uns einen Blick. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO PLAYBACK] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Hier sind Sie Bei Google, und Ich mag 198 00:09:48,560 --> 00:09:53,382 um der Präsidentschaft denken als Job-Interview. 199 00:09:53,382 --> 00:09:56,434 Jetzt ist es schwer zu bekommen ein Job als Präsident, 200 00:09:56,434 --> 00:09:58,100 und Sie durch die Strapazen gehen jetzt sind. 201 00:09:58,100 --> 00:10:01,860 Es ist auch schwer, einen Job zu Google zu bekommen. 202 00:10:01,860 --> 00:10:05,490 Wir haben Fragen, und wir Fragen Sie unsere Kandidaten Fragen, 203 00:10:05,490 --> 00:10:09,770 und dieses ist von Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- euch denken, ich bin Scherz, es ist hier richtig. 205 00:10:14,760 --> 00:10:17,930 Was ist die effizienteste Art, sortieren eine Million 32-Bit-Ganzzahlen? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Ich Sorry, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nein, nein, nein. 210 00:10:27,400 --> 00:10:30,700 Ich denke, die Bubble-Sort wäre der falsche Weg zu gehen. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Komm, Der ihm das gesagt? 213 00:10:38,180 --> 00:10:40,590 Ich sah nicht, Computer Wissenschaft in den Hintergrund. 214 00:10:40,590 --> 00:10:42,130 >> -We've Haben unsere Spione dort. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Fragen wir eine andere Interview-Frage. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO PLAYBACK] 218 00:10:49,300 --> 00:10:52,290 >> SPRECHER: So reden konkrete Zahlen aber, 219 00:10:52,290 --> 00:10:53,890 wird nicht alles sein, was nützlich ist. 220 00:10:53,890 --> 00:10:56,810 Es ist nicht eine Lektion fürs Leben, dass Blase Art, da eine Million Eingänge, 221 00:10:56,810 --> 00:10:58,590 vielleicht nehmen so viele wie 500 Milliarden Schritten. 222 00:10:58,590 --> 00:11:01,120 Man kann nicht wirklich verallgemeinern auch effektiv aus, dass 223 00:11:01,120 --> 00:11:03,560 und gute Design-Entscheidungen wenn die Programme schreiben. 224 00:11:03,560 --> 00:11:07,070 Also konzentrieren wir uns aber auf, wie wir könnten dieses Ergebnis zu vereinfachen. 225 00:11:07,070 --> 00:11:11,780 >> Also ich habe hier in gelb hervorgehoben das Ergebnis der n Quadrat dividiert durch 2, 226 00:11:11,780 --> 00:11:14,330 so eine Million Quadrat geteilt durch 2, und 227 00:11:14,330 --> 00:11:16,710 Ich habe hervorgehoben welche die ultimative Antwort war 228 00:11:16,710 --> 00:11:20,180 wenn wir subtrahiert aus n durch 2 geteilt. 229 00:11:20,180 --> 00:11:24,850 Und die Behauptung, ich werde jetzt zu machen ist, wer zum Teufel kümmert es, wenn Sie subtrahieren aus 230 00:11:24,850 --> 00:11:30,060 ein wenig alt n mehr als 2, wenn die erste Teil dieser Formel ist so viel größer? 231 00:11:30,060 --> 00:11:33,910 Es dominiert die anderen Ausdruck, n Quadrat dividiert durch 2 232 00:11:33,910 --> 00:11:37,510 ist so viel größer, deutlich, wie n groß wird wie eine Million, 233 00:11:37,510 --> 00:11:41,450 das ist es wirklich ein großer Unterschied zu das Ende des Tages zwischen 500 Milliarden 234 00:11:41,450 --> 00:11:45,730 und 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Nicht wirklich. 236 00:11:46,349 --> 00:11:48,640 Und so, was wir zu gehen tun, wie Informatiker ist 237 00:11:48,640 --> 00:11:53,270 diese Terme niedrigerer Ordnung zu ignorieren und nehmen und so etwas wirklich 238 00:11:53,270 --> 00:11:56,050 nur zu vereinfachen, um die Begriff, das geht an die Materie. 239 00:11:56,050 --> 00:12:00,315 Die größeren unsere Datensätze zu erhalten, desto größer unsere Datenbanken zu erhalten, die mehr Web-Seiten 240 00:12:00,315 --> 00:12:02,690 wir müssen, die mehr suchen Freunde haben Sie auf Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Als n größer wird, sind wir wirklich gehen, um über die größte Sorgfalt 242 00:12:07,340 --> 00:12:11,560 Term in einer solchen Analyse unsere Algorithmen Leistung. 243 00:12:11,560 --> 00:12:16,230 Und ich werde sagen, wissen Sie was, Bubble-Sort ist in der Größenordnung von Big O, 244 00:12:16,230 --> 00:12:18,060 in der Größenordnung von n quadriert. 245 00:12:18,060 --> 00:12:20,090 Es ist nicht genau n Quadrat, wie wir gesehen haben, 246 00:12:20,090 --> 00:12:22,060 aber wer kümmert sich wirklich über diese kleineren Begriffe, 247 00:12:22,060 --> 00:12:24,390 und ehrlich gesagt, die wirklich kümmert es, wenn wir durch 2 teilen? 248 00:12:24,390 --> 00:12:25,870 Das ist nur ein konstanter Faktor. 249 00:12:25,870 --> 00:12:29,480 Und ist 500 Milliarden gegenüber 250 Milliarden wirklich so große Sache? 250 00:12:29,480 --> 00:12:32,190 Ich konnte es einfach ein Jahr warten, lass meinen Laptop wörtlich 251 00:12:32,190 --> 00:12:34,810 bekommen doppelt so schnell in Hardware, und diese Art von Unterschied 252 00:12:34,810 --> 00:12:36,650 nur geht weg natürlich über die Zeit. 253 00:12:36,650 --> 00:12:39,300 >> Was uns wichtig ist der Ausdruck, der Teil 254 00:12:39,300 --> 00:12:42,489 des Ausdrucks, die gehen zu variieren als unseren Input wird größer und größer. 255 00:12:42,489 --> 00:12:45,280 Und zwar in der realen Welt, das ist, was immer geschieht, 256 00:12:45,280 --> 00:12:48,330 ist die Eingänge, um unsere Probleme und Algorithmen werden immer größer. 257 00:12:48,330 --> 00:12:53,470 So groß, O wird sich die Schreibweise zu sein, die asymptotische Notation, dass wir nur 258 00:12:53,470 --> 00:12:57,160 Verwendung als Computerwissenschaftler, um zu beschreiben die Leistung oder die Laufzeit, 259 00:12:57,160 --> 00:12:58,130 eines Algorithmus. 260 00:12:58,130 --> 00:13:00,800 So dass wir Algorithmen vergleichen auf verschiedenen Computern geschrieben 261 00:13:00,800 --> 00:13:04,170 von verschiedenen Personen, unter Verwendung einige grundlegend ähnliche metrische 262 00:13:04,170 --> 00:13:07,557 wie die Anzahl der Vergleiche sind Sie machen, oder vielleicht die Anzahl der Swaps 263 00:13:07,557 --> 00:13:08,140 du machst. 264 00:13:08,140 --> 00:13:11,910 >> Was wir nicht gehen Zahl ist die Menge an Zeit, 265 00:13:11,910 --> 00:13:13,981 daß am Taktläuft an der Wand der Regel. 266 00:13:13,981 --> 00:13:16,230 Was wir nicht zu sorgen , ist, wie viel Speicher 267 00:13:16,230 --> 00:13:17,820 Sie sind heute bei dest, obwohl das 268 00:13:17,820 --> 00:13:19,370 eine andere Ressource, die wir vielleicht zu messen. 269 00:13:19,370 --> 00:13:23,610 Wir werden versuchen, unsere Analysen stützen nur auf die Grundfunktionen, die, die, 270 00:13:23,610 --> 00:13:25,930 ehrlich gesagt, dass Sie visuell sehen kann. 271 00:13:25,930 --> 00:13:30,700 Also mit so etwas wie Big O von n quadriert, ich behaupten, dass O von n im Quadrat 272 00:13:30,700 --> 00:13:35,820 eine obere auf der sogenannten gebundenen Laufzeit von Bubble-Sort. 273 00:13:35,820 --> 00:13:38,820 Mit anderen Worten, wenn man wollte behaupten, dass es 274 00:13:38,820 --> 00:13:41,370 Diese obere Grenze, wie viele Schritte ein Algorithmus aussehen könnte, 275 00:13:41,370 --> 00:13:46,240 es wird in der großen O von n sein in diesem Fall wird quadriert, eine obere Grenze. 276 00:13:46,240 --> 00:13:49,710 >> Was ist, wenn ich stattdessen die ändern Geschichte, nicht über Blasen Art sein, 277 00:13:49,710 --> 00:13:50,910 aber über diese obere Schranke. 278 00:13:50,910 --> 00:13:54,030 Können Sie eines Algorithmus denken dass wir an sah schon 279 00:13:54,030 --> 00:13:59,530 dessen obere Grenze maximalen Maß der Zeit oder Operationen, 280 00:13:59,530 --> 00:14:04,300 würde gesagt, begrenzt werden durch N, eine lineare Funktion, 281 00:14:04,300 --> 00:14:07,260 nicht eine quadratische eine, die gebogene ist? 282 00:14:07,260 --> 00:14:10,780 Was ist ein Algorithmus, der findet immer nicht mehr 283 00:14:10,780 --> 00:14:12,860 als wie n Schritten, oder 2n Schritten oder 3n Schritte? 284 00:14:12,860 --> 00:14:13,360 Ja? 285 00:14:13,360 --> 00:14:15,030 >> ZIELGRUPPE: Das Finden der größte Zahl in einer Liste? 286 00:14:15,030 --> 00:14:16,930 >> SPRECHER: Perfect, finden die größte Zahl in einer Liste. 287 00:14:16,930 --> 00:14:18,940 Wenn ich eine Liste der genannten Menschen, zum Beispiel 288 00:14:18,940 --> 00:14:21,440 jeder, der im Besitz einer Reihe, Was ist die maximale Anzahl 289 00:14:21,440 --> 00:14:23,770 von Schritten sollte es mir zu nehmen, eine ziemlich intelligente Person, 290 00:14:23,770 --> 00:14:27,530 , die größte Person in dieser Liste? 291 00:14:27,530 --> 00:14:28,100 n, oder? 292 00:14:28,100 --> 00:14:31,320 Da im schlimmsten Fall, bei dem könnte der größte Wert sein? 293 00:14:31,320 --> 00:14:32,700 Recht, den ganzen Weg am Ende. 294 00:14:32,700 --> 00:14:34,575 So im schlimmsten Fall Obergrenze, könnte ich 295 00:14:34,575 --> 00:14:36,450 haben, den ganzen Weg zu gehen hier und werden wie, 296 00:14:36,450 --> 00:14:39,170 oh, hier ist Nummer acht, oder was auch immer das Wert ist. 297 00:14:39,170 --> 00:14:41,330 Nun wäre es einfach nur dumm sein wenn ich in Gang gehalten, oder? 298 00:14:41,330 --> 00:14:43,840 Auf der Suche nach mehr und mehr Elemente wenn der letzte von ihnen ist dort? 299 00:14:43,840 --> 00:14:45,340 So sicher ist n eine obere Schranke. 300 00:14:45,340 --> 00:14:47,420 Ich brauche nicht zu nehmen mehr Stufen als die. 301 00:14:47,420 --> 00:14:51,580 >> So was, wenn ich stattdessen vorgeschlagen, dass Es gibt Algorithmen, die in dieser Welt, die 302 00:14:51,580 --> 00:14:57,750 haben eine Laufzeit, die ist von Big O log n begrenzt, melden Sie n? 303 00:14:57,750 --> 00:15:00,390 Wo haben wir gesehen das? 304 00:15:00,390 --> 00:15:00,890 Ja? 305 00:15:00,890 --> 00:15:03,309 >> ZIELGRUPPE: Im Telefonbuch Problem? 306 00:15:03,309 --> 00:15:04,850 SPRECHER: Wie der Telefonbuch Problem. 307 00:15:04,850 --> 00:15:07,754 Was war das Maß dafür, wie viel Zeit oder wie viele Tränen es 308 00:15:07,754 --> 00:15:10,170 Hat mich jemand wie zu finden Mike Smith im Telefonbuch? 309 00:15:10,170 --> 00:15:13,212 Wir behauptete, es sei log n, und auch wenn es nicht vertraut oder es ist 310 00:15:13,212 --> 00:15:15,170 ein wenig verschwommen, was ein Logarithmus oder Exponent war, 311 00:15:15,170 --> 00:15:17,650 nur daran erinnern, dass log n bezieht sich allgemein auf das Verfahren, 312 00:15:17,650 --> 00:15:20,790 in diesem Fall der Unterteilung etwas in der Hälfte wieder, und wieder, 313 00:15:20,790 --> 00:15:25,790 und wieder und wieder, so daß er wird immer kleiner, wie Sie das tun. 314 00:15:25,790 --> 00:15:28,470 >> So melden Sie sich von n bezieht sich, klar, zum Telefonbuch beispielsweise, 315 00:15:28,470 --> 00:15:32,662 binäre Suche in der Theorie, wenn wir hatte die virtuellen Türen auf dem Brett, 316 00:15:32,662 --> 00:15:34,370 oder wenn Sean war Suche nach etwas. 317 00:15:34,370 --> 00:15:37,374 Wenn er binäre Suche benutzt hatte, log n wäre, wie viel die Obergrenze 318 00:15:37,374 --> 00:15:38,040 Zeit, die dauert. 319 00:15:38,040 --> 00:15:44,027 Aber diese Algorithmen, die in lief n ausgegangen, welche Schlüsseldetailprotokoll? 320 00:15:44,027 --> 00:15:45,360 Dass die Liste sortiert wurde, richtig? 321 00:15:45,360 --> 00:15:47,789 Ihr Algorithmus ist falsch, wenn Ihre Eingabe ist nicht sortiert, 322 00:15:47,789 --> 00:15:49,830 und doch, die Sie verwenden so etwas wie binäre Suche 323 00:15:49,830 --> 00:15:51,704 weil Sie vielleicht springen direkt über dem Element 324 00:15:51,704 --> 00:15:53,600 ohne zu merken, es ist in der Tat gibt. 325 00:15:53,600 --> 00:15:55,600 >> Nun, was könnte dies bedeuten, groß O von einem? 326 00:15:55,600 --> 00:15:59,117 Dies bedeutet nicht, dass Ihr Algorithmus nimmt einen und nur einen Schritt, 327 00:15:59,117 --> 00:16:01,200 es bedeutet nur, es dauert ein konstante Anzahl von Schritten. 328 00:16:01,200 --> 00:16:04,060 Vielleicht ist es ein, vielleicht ist es 10, vielleicht ist es 1000, 329 00:16:04,060 --> 00:16:07,750 aber es ist unabhängig von das Ausmaß des Problems. 330 00:16:07,750 --> 00:16:10,850 Egal wie groß n ist, eine konstante Zeit-Algorithmus 331 00:16:10,850 --> 00:16:12,747 nimmt immer die gleiche Anzahl von Schritten. 332 00:16:12,747 --> 00:16:15,080 Also, was könnte ein Algorithmus sein wir über oder einfach nur geredet haben 333 00:16:15,080 --> 00:16:20,418 intuitiv, dass zu Ihnen kommt, dass läuft immer in sogenannten konstanten Zeit? 334 00:16:20,418 --> 00:16:20,918 Ja? 335 00:16:20,918 --> 00:16:22,001 >> ZIELGRUPPE: In zwei Zahlen. 336 00:16:22,001 --> 00:16:25,320 SPRECHER: In zwei Zahlen, 2 plus 2 gleich 4, fertig. 337 00:16:25,320 --> 00:16:27,227 So dass funktionieren könnte, was sonst? 338 00:16:27,227 --> 00:16:28,560 Wie wäre es mit mehr realen Welt, ja? 339 00:16:28,560 --> 00:16:30,686 >> ZIELGRUPPE: Das Finden der erste, was in einer Liste. 340 00:16:30,686 --> 00:16:32,810 SPRECHER: Das Finden der ersten Element in einer Liste, sicher. 341 00:16:32,810 --> 00:16:34,540 Wir haben tatsächlich gesprochen etwa bereits Arrays 342 00:16:34,540 --> 00:16:36,540 Wie sehen Sie das bekommen das erste Element in einem Array, 343 00:16:36,540 --> 00:16:40,465 unabhängig davon, wie lange der Array im C-Code? 344 00:16:40,465 --> 00:16:43,090 Sie ebenso wie die Konsole verwenden Null-Notation, bam, du bist da. 345 00:16:43,090 --> 00:16:46,120 Und in der Tat Arrays, nebenbei, Unterstützung etwas allgemein bekannt 346 00:16:46,120 --> 00:16:49,240 wahlfreiem Zugriff, Random Access Gedächtnis, weil man buchstäblich 347 00:16:49,240 --> 00:16:50,284 springen, um an einem Ort. 348 00:16:50,284 --> 00:16:52,700 Wir können diese noch einfacher machen können wir zu Woche Null Rücklauf 349 00:16:52,700 --> 00:16:53,900 als wir Scratch. 350 00:16:53,900 --> 00:16:59,707 Wie viel Zeit haben Sie für das nehmen sagen Block im Scratch ausführen? 351 00:16:59,707 --> 00:17:00,790 Nur konstante Zeit, oder? 352 00:17:00,790 --> 00:17:03,960 Sagen Sie etwas, sagen etwas, ist es egal, 353 00:17:03,960 --> 00:17:07,359 wie groß Kratzer Welt ist, ist es immer würde die gleiche Menge an Zeit, 354 00:17:07,359 --> 00:17:08,490 einfach zu sagen, so etwas. 355 00:17:08,490 --> 00:17:11,089 >> Also das ist, konstante Zeit, aber was ist die Kehrseite? 356 00:17:11,089 --> 00:17:13,030 Ob das obere Grenzen, was ist, wenn wir wollen, 357 00:17:13,030 --> 00:17:17,089 um die unteren Grenzen beschreiben unserer Algorithmen Laufzeit? 358 00:17:17,089 --> 00:17:19,852 Fast ein best case möglicherweise, wenn man will, 359 00:17:19,852 --> 00:17:23,060 obwohl diese Begriffe könnten am besten anwenden Fällen schlimmsten Fällen durchschnittlich Fällen mehr 360 00:17:23,060 --> 00:17:26,359 in der Regel, aber lasst uns einfach konzentrieren auf Untergrenzen im Allgemeinen. 361 00:17:26,359 --> 00:17:31,920 Was ist ein Algorithmus, der hat eine von n Stufen tiefer gebunden, 362 00:17:31,920 --> 00:17:33,350 oder 2n Schritten oder 3n Schritte? 363 00:17:33,350 --> 00:17:36,241 Einen Faktor von n Schritten, das ist seine untere Grenze. 364 00:17:36,241 --> 00:17:36,740 Ja? 365 00:17:36,740 --> 00:17:37,910 >> ZIELGRUPPE: Bubble Sort? 366 00:17:37,910 --> 00:17:41,610 >> SPRECHER: Bubble Sort nimmt Sie minimal n Schritten, warum? 367 00:17:41,610 --> 00:17:42,279 Warum ist das so? 368 00:17:42,279 --> 00:17:45,320 Warum sollte das Start zu Ihnen kommen intuitiv, auch wenn es nicht gerade 369 00:17:45,320 --> 00:17:46,530 noch nicht? 370 00:17:46,530 --> 00:17:47,030 Ja? 371 00:17:47,030 --> 00:17:47,990 >> ZIELGRUPPE: [unverständlich]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPRECHER: Genau. 374 00:17:52,360 --> 00:17:55,810 In der bestmöglichen Szenario Blasensortierung, und eine Menge von Algorithmen, 375 00:17:55,810 --> 00:17:58,769 wenn ich Hand, die Sie acht Personen die bereits sortiert sind, 376 00:17:58,769 --> 00:18:00,560 es wäre töricht für Sie, der Algorithmus, 377 00:18:00,560 --> 00:18:02,202 hin und her gehen mehr als einmal, oder? 378 00:18:02,202 --> 00:18:04,285 Denn sobald Sie gehen einmal durch die Liste, 379 00:18:04,285 --> 00:18:08,090 Sie sollten erkennen, oh, ich habe keine Swaps, wird diese Liste sortiert, Ausfahrt. 380 00:18:08,090 --> 00:18:09,700 Aber das wird dir n Schritte zu unternehmen. 381 00:18:09,700 --> 00:18:12,033 >> Und umgekehrt, was ist ein weiterer Art des Denkens über sie? 382 00:18:12,033 --> 00:18:15,240 Bubble-Sort ist eine Omega, sozusagen von N, 383 00:18:15,240 --> 00:18:19,050 denn wenn man sich freuen weniger als n Elemente, was 384 00:18:19,050 --> 00:18:23,009 ist die Grundfrage gibt? 385 00:18:23,009 --> 00:18:24,550 Sie wissen nicht, ob es sortiert, rechts. 386 00:18:24,550 --> 00:18:26,800 Wir Menschen Macht Blick auf acht Menschen und wie sein, oh, es sortiert, 387 00:18:26,800 --> 00:18:28,430 das hat mich n Schritte nicht zu nehmen, aber es tat. 388 00:18:28,430 --> 00:18:30,810 Ihre Augen, auch wenn Sie Art von haben eine große Sichtfeld, 389 00:18:30,810 --> 00:18:33,184 Sie schaute auf acht Elemente, Sie schaute auf acht Personen, 390 00:18:33,184 --> 00:18:34,610 das ist acht Schritte effektiv. 391 00:18:34,610 --> 00:18:38,612 Und nur, wenn ich durch das ganze Liste zu tun ich merke, ja, sortiert. 392 00:18:38,612 --> 00:18:41,320 Wenn ich halbwegs denken aufhören, alle richtig, es ist ziemlich so weit sortiert, 393 00:18:41,320 --> 00:18:42,520 Wie stehen die Chancen es ist nicht sortiert? 394 00:18:42,520 --> 00:18:44,186 Dass Algorithmen, nicht korrekt zu sein. 395 00:18:44,186 --> 00:18:46,250 Vielleicht schneller, aber nicht korrekt. 396 00:18:46,250 --> 00:18:48,500 >> So, jetzt haben wir einen Weg der Beschreibung eines Untergrenzen, 397 00:18:48,500 --> 00:18:49,710 und was ist mit konstanter Zeit? 398 00:18:49,710 --> 00:18:54,565 Was ist ein Algorithmus, der eine niedrigere hat auf seiner Laufzeit von einem Satz? 399 00:18:54,565 --> 00:18:58,350 1 Schritt, 2 Schritte, 10 Schritte, aber konstant, unabhängig von n ist, 400 00:18:58,350 --> 00:18:59,310 Die Größe des Eingangs? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Ja, auf der Rückseite. 403 00:19:04,600 --> 00:19:05,309 >> ZIELGRUPPE: Printf? 404 00:19:05,309 --> 00:19:06,183 SPRECHER: Was ist das? 405 00:19:06,183 --> 00:19:07,184 ZIELGRUPPE: Printf? 406 00:19:07,184 --> 00:19:07,850 SPRECHER: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, sicher. 408 00:19:08,400 --> 00:19:10,720 So dauert es eine feste Anzahl von Schritten. 409 00:19:10,720 --> 00:19:13,170 Und ich sollte jetzt, dass now-- wir über C-Code im Gespräch 410 00:19:13,170 --> 00:19:16,040 und nicht kratzen, etwas, wie gesagt, mit printf, 411 00:19:16,040 --> 00:19:17,710 wir sollten vorsichtig sein, um zu bekommen. 412 00:19:17,710 --> 00:19:21,090 Da printf dauert Eingang, es ist eine Zeichenfolge, 413 00:19:21,090 --> 00:19:23,220 Saiten und technisch haben Länge. 414 00:19:23,220 --> 00:19:25,530 Also, wenn wir jetzt abholen wollen auf Sie, wenn Sie nichts dagegen haben, 415 00:19:25,530 --> 00:19:29,430 technisch könnte man argumentieren, dass printf dauert eine variable Länge Input, 416 00:19:29,430 --> 00:19:32,270 und sicher, es könnte länger dauern Zeit, um einen String so lange drucken, 417 00:19:32,270 --> 00:19:33,560 als dieser lang. 418 00:19:33,560 --> 00:19:36,570 >> So was, wenn wir nur die betrachten Sortieren und Suchen Beispiele? 419 00:19:36,570 --> 00:19:40,450 Was ist mit Mike Smith im Telefon Buch oder binäre Suche allgemein? 420 00:19:40,450 --> 00:19:42,220 Im besten Fall könnte was passieren? 421 00:19:42,220 --> 00:19:45,577 Ich öffne das Telefonbuch und, bam, es gibt Mike Smith Nummer. 422 00:19:45,577 --> 00:19:46,660 Ich kann ihn sofort anrufen. 423 00:19:46,660 --> 00:19:49,390 >> Machte einen Schritt, vielleicht zwei Schritte, aber eine konstante Anzahl von Schritten, 424 00:19:49,390 --> 00:19:50,230 wenn ich hatte Glück. 425 00:19:50,230 --> 00:19:52,570 Und ehrlich gesagt, haben wir gesehen, auf Ihre Klassenkameradin Montag 426 00:19:52,570 --> 00:19:54,710 ganz schön Glück zweimal in Folge. 427 00:19:54,710 --> 00:19:57,050 Und das war in der Tat konstant Mal in ein Untergrenzen 428 00:19:57,050 --> 00:20:01,280 auf dem Algorithmus in Frage für die Suche die Zahl 50 hinter den geschlossen 429 00:20:01,280 --> 00:20:01,830 Türen. 430 00:20:01,830 --> 00:20:06,400 >> Jetzt, als zur Seite, wenn Sie feststellen, dass sowohl große O, die obere Grenze, 431 00:20:06,400 --> 00:20:09,310 und Omega, der Untergrenze, sind ein in der gleichen, dass 432 00:20:09,310 --> 00:20:11,830 ist die gleiche Formel, Klammern, können Sie auch 433 00:20:11,830 --> 00:20:15,170 sagen, nur um Phantasie zu sein, dass etwas in Theta 434 00:20:15,170 --> 00:20:18,270 n oder Theta von einem anderen Wert. 435 00:20:18,270 --> 00:20:20,661 Das bedeutet nur, wenn große O und O sind die gleichen. 436 00:20:20,661 --> 00:20:21,910 Was ist nun mit Auswahl sortieren? 437 00:20:21,910 --> 00:20:23,400 Lassen Sie uns diese neue Wortschatz. 438 00:20:23,400 --> 00:20:27,407 Bei der Auswahl sortieren, was waren wir wieder zu tun, und wieder, und wieder? 439 00:20:27,407 --> 00:20:29,990 Ich wurde durch hin und her die Liste, auf der Suche nach wem? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Die kleinste Zahl. 442 00:20:34,730 --> 00:20:37,560 >> Also, wie viele Schritte, wie viele Vergleiche habe ich 443 00:20:37,560 --> 00:20:43,250 müssen, um herauszufinden, machen die das kleinste Element in der Liste war? 444 00:20:43,250 --> 00:20:44,437 n minus 1, oder? 445 00:20:44,437 --> 00:20:47,770 Denn wenn ich nur mit der, die ich bin starten gegeben und ich beginne ihn oder sie zu vergleichen, 446 00:20:47,770 --> 00:20:49,519 dann ihn oder sie, er oder sie, ihn oder sie, ich 447 00:20:49,519 --> 00:20:52,010 kann nur paaren Elemente zusammen n minus 1 mal. 448 00:20:52,010 --> 00:20:55,630 So ähnlich Auswahl Art nimmt n minus 1 Schritte zum ersten Mal. 449 00:20:55,630 --> 00:20:59,540 >> Wie viele Schritte braucht es, mich zu finden Sie das zweitkleinste Element? 450 00:20:59,540 --> 00:21:02,920 n minus 2, denn ich bin als dumm wenn ich auch in Zukunft auf die gleichen Leute 451 00:21:02,920 --> 00:21:06,280 wieder, wenn ich ihn schon ausgewählt oder sie und legte sie in ihre Schranken. 452 00:21:06,280 --> 00:21:09,270 Und den dritten Schritt, n minus 3, dann n minus 4. 453 00:21:09,270 --> 00:21:11,020 Wir haben dieses Muster gesehen vor, und zwar 454 00:21:11,020 --> 00:21:13,460 Auswahl Art ähnlich eine obere Schranke 455 00:21:13,460 --> 00:21:16,210 n im Quadrat, wenn wir tun, bis diese Summe. 456 00:21:16,210 --> 00:21:19,790 Was ist ihre untere Grenze, die Auswahl sortieren? 457 00:21:19,790 --> 00:21:25,350 Minimal, wie viel Zeit Muss Auswahl Art zu nehmen, wie wir es am Montag festgelegt? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Schlagen zwei Möglichkeiten. 460 00:21:30,490 --> 00:21:32,360 Vielleicht ist es n, wie zuvor. 461 00:21:32,360 --> 00:21:35,040 Vielleicht ist es n quadriert, wie es ist jetzt als die obere Grenze. 462 00:21:35,040 --> 00:21:35,874 >> ZIELGRUPPE: n quadriert. 463 00:21:35,874 --> 00:21:36,664 SPRECHER: n quadriert. 464 00:21:36,664 --> 00:21:37,368 Warum? 465 00:21:37,368 --> 00:21:40,060 >> ZIELGRUPPE: Weil Sie zu definieren [unverständlich]. 466 00:21:40,060 --> 00:21:41,510 >> SPRECHER: Genau. 467 00:21:41,510 --> 00:21:45,077 Zumindest, als ich festgelegten Auswahl Art es war ziemlich naiv, weiterzumachen, 468 00:21:45,077 --> 00:21:46,160 finden Sie das kleinste Element. 469 00:21:46,160 --> 00:21:47,770 Gehen wieder finden das kleinste Element. 470 00:21:47,770 --> 00:21:49,490 Gehen wieder finden das kleinste Element. 471 00:21:49,490 --> 00:21:51,700 Es gibt keine Art von Optimierung gibt, die 472 00:21:51,700 --> 00:21:54,350 vielleicht lassen Sie mich nach Abbruch nur n oder so Schritten. 473 00:21:54,350 --> 00:21:57,080 Also ja, die Auswahl Sortieren, Omega von n im Quadrat. 474 00:21:57,080 --> 00:22:00,667 >> Was ist mit Insertion Sort, wo ich wer ich war gegeben, und ihn dann fallen ließ ich 475 00:22:00,667 --> 00:22:01,750 oder sie in der richtigen Stelle? 476 00:22:01,750 --> 00:22:04,958 Dann ging ich in die zweite Person, plumpste ihm oder ihr an der richtigen Stelle. 477 00:22:04,958 --> 00:22:07,910 Dann wird die nächste Person, plumpste ihn oder sie in der richtigen Stelle. 478 00:22:07,910 --> 00:22:10,537 Beachten Sie, dass dies sehr Linear sozusagen. 479 00:22:10,537 --> 00:22:12,620 Ich bin eine gerade Linie, ich bin nicht hin und her gehen, 480 00:22:12,620 --> 00:22:16,080 Ich habe noch nie im Rückblick wirklich, aber was passiert, wenn ich ihn einfügen 481 00:22:16,080 --> 00:22:20,302 oder sie in den Anfang die Liste, wie wir am Montag getan hat? 482 00:22:20,302 --> 00:22:21,010 Was ist los? 483 00:22:21,010 --> 00:22:21,510 Ja? 484 00:22:21,510 --> 00:22:23,122 ZIELGRUPPE: [unverständlich]. 485 00:22:23,122 --> 00:22:24,830 SPRECHER: Ja, das war der Haken, oder? 486 00:22:24,830 --> 00:22:26,746 Sie könnten von erinnern Ihre Klassenkameraden, wenn sie 487 00:22:26,746 --> 00:22:29,670 machten jede Bewegung mit ihre Füße, das war eine Operation. 488 00:22:29,670 --> 00:22:33,610 Also, wenn es hier drei Personen und die neue Person gehörte Weise dort, 489 00:22:33,610 --> 00:22:37,360 auf einer langen Etappe wie diese, sicher, er oder sie nur bis zum Ende gehen könnte. 490 00:22:37,360 --> 00:22:40,074 Aber wenn wir über ein Denken Computer und ein Feld von Speicher, 491 00:22:40,074 --> 00:22:41,990 Diese Leute werden shuffle über zu haben, 492 00:22:41,990 --> 00:22:43,260 um Platz für diese Person zu machen. 493 00:22:43,260 --> 00:22:46,930 Und so, dass n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings ist nur irgendwie geschieht hinter mir, nicht vor mir 495 00:22:50,660 --> 00:22:52,710 wie vorher, in einem gewissen Sinn. 499 00:22:52,557 --> 00:22:54,640 Nun als zur Seite, und als Sie können Online-gesehen haben 500 00:22:54,640 --> 00:22:57,699 wenn Sie stochern zu starten Art, es gibt so viele verschiedene, 501 00:22:57,699 --> 00:22:59,490 gibt, von denen einige besser als andere. 502 00:22:59,490 --> 00:23:02,200 Tatsächlich ist eine bogosort das ist eine Art von Spaß zu schauen. 503 00:23:02,200 --> 00:23:06,650 Bogosort nimmt eine Reihe von Zahlen oder sagen ein Deck von Karten, 504 00:23:06,650 --> 00:23:09,870 zufällig mischt sie, und prüft, ob sie sortiert. 505 00:23:09,870 --> 00:23:12,130 Und wenn nicht, tut es wieder. 506 00:23:12,130 --> 00:23:14,140 Und wenn nicht, tut es wieder. 507 00:23:14,140 --> 00:23:15,440 Wenn nicht, tut es wieder. 508 00:23:15,440 --> 00:23:17,060 Unglaublich dumm. 509 00:23:17,060 --> 00:23:19,520 >> Und in der Tat, wenn Sie lesen, wie der Wikipedia-Artikel, 510 00:23:19,520 --> 00:23:21,200 sein Spitzname ist dumm Sorte. 511 00:23:21,200 --> 00:23:25,180 Es wird schließlich arbeiten, hoffentlich genügend Zeit, 512 00:23:25,180 --> 00:23:28,240 aber Zeit könnte einige Zeit dauern. 513 00:23:28,240 --> 00:23:31,650 Also, wenn ich könnte, lassen Sie uns die Dinge Geschwindigkeit aus Mary Beth Beispiel zuvor, 514 00:23:31,650 --> 00:23:35,150 indem er ein paar weitere Elemente, aber zwei weitere Prozessoren. 515 00:23:35,150 --> 00:23:37,100 Zwei Menschen, wenn Sie hätte nichts dagegen, mich Beitritt. 516 00:23:37,100 --> 00:23:40,972 Wie etwa 1 hier, und Lassen Sie uns go-- niemanden dort? 517 00:23:40,972 --> 00:23:41,722 Niemand da? 518 00:23:41,722 --> 00:23:42,221 Ok. 519 00:23:42,221 --> 00:23:44,190 Sie mit der schwarzen T-Shirt, ja, kommen auf Sie. 520 00:23:44,190 --> 00:23:45,000 Alles in Ordnung, was ist Ihr Name? 521 00:23:45,000 --> 00:23:45,720 >> ZIELGRUPPE: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPRECHER: Was ist das? 523 00:23:46,100 --> 00:23:46,766 >> ZIELGRUPPE: Peter. 524 00:23:46,766 --> 00:23:49,450 SPRECHER: Peter, David, schön, Sie zu treffen. 525 00:23:49,450 --> 00:23:53,670 Alles in Ordnung, wir haben Peter hier, wenn Sie wollen hier auf den Tisch kommen. 526 00:23:53,670 --> 00:23:54,550 Und was ist Ihr Name? 527 00:23:54,550 --> 00:23:55,216 >> ZIELGRUPPE: Elena. 528 00:23:55,216 --> 00:23:55,970 SPRECHER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, schön, Sie zu treffen. 530 00:23:57,030 --> 00:23:58,060 Elena treffen Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Und wir brauchen Andrew bis auch hier, bitte. 533 00:24:02,290 --> 00:24:06,107 Und Ihre Herausforderung wird zu sein, ein Kartenspiel zu sortieren. 534 00:24:06,107 --> 00:24:08,190 Und wenn nicht vertraut, Liege Karten letztlich sollte 535 00:24:08,190 --> 00:24:11,064 ein wenig so etwas wie sortiert werden dieses, wo wir die Clubs zu tun, dann 536 00:24:11,064 --> 00:24:13,660 die Spaten, dann die Herzen und Diamanten, von ACE als eine, 537 00:24:13,660 --> 00:24:15,570 den ganzen Weg bis zum König. 538 00:24:15,570 --> 00:24:20,890 >> Die Karten werde ich Ihnen gehen, um 52 in Menge. 539 00:24:20,890 --> 00:24:23,160 Wir gehen mit ähnlich Zeit, die Sie, in nur einem Augenblick. 540 00:24:23,160 --> 00:24:26,410 Wir werden Andrew werfen auf dem Bildschirm hier, 541 00:24:26,410 --> 00:24:28,170 so zu beobachten, wie Sie dies tun. 542 00:24:28,170 --> 00:24:31,070 Und so, daß alles umso sichtbarer, 543 00:24:31,070 --> 00:24:33,490 das sind die Karten, die ich auf Amazon bekam. 544 00:24:33,490 --> 00:24:42,861 So sind sie bereits nach dem Zufallsprinzip sortiert, und wir werden Ihnen Zeit. 545 00:24:42,861 --> 00:24:44,610 Und wir sind zu gehen keep it real diese Zeit, 546 00:24:44,610 --> 00:24:47,820 so werden wir versuchen, Sie unter Druck weil sonst diese erhalten mühsam 547 00:24:47,820 --> 00:24:48,460 schnell. 548 00:24:48,460 --> 00:24:53,860 Wenn Sie fortfahren könnte zu sortieren 52 Elemente miteinander über einige Mittel, jetzt. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Und wieder, wie wir sehen diese Jungs tun, was am Ende 551 00:25:07,180 --> 00:25:10,200 wird sich eine offensichtliche produzieren Ergebnis, denken Sie wirklich 552 00:25:10,200 --> 00:25:12,962 wie sie jeder tut es, wie Sie es beschreiben. 553 00:25:12,962 --> 00:25:15,045 Da wiederum sind alle Prozesse, Algorithmen 554 00:25:15,045 --> 00:25:17,090 dass wir für so einen Menschen gewährt. 555 00:25:17,090 --> 00:25:22,349 Aber wahrscheinlich lange gehabt haben Intuition, lange bevor Sie selbst 556 00:25:22,349 --> 00:25:24,390 dachte über die Einnahme ein Informatik Klasse, die Sie 557 00:25:24,390 --> 00:25:27,223 könnte die Intuition mit gehabt haben was zu Problemen wie diese zu lösen. 558 00:25:27,223 --> 00:25:29,560 Aber sobald Sie erkennen, Die Muster und beginnen 559 00:25:29,560 --> 00:25:32,407 um die Schritte, mit denen formalisieren Sie diese Probleme zu lösen, 560 00:25:32,407 --> 00:25:35,490 Sie werden feststellen, dass Sie viel zu lösen interessanter und viel komplexer 561 00:25:35,490 --> 00:25:39,190 Probleme schnell. 562 00:25:39,190 --> 00:25:42,351 So jemand aus dem Publikum, was ist mindestens ein Element des Algorithmus 563 00:25:42,351 --> 00:25:43,350 dass sie mit hier sind? 564 00:25:43,350 --> 00:25:44,275 >> ZIELGRUPPE: [unverständlich] 565 00:25:44,275 --> 00:25:45,150 SPRECHER: Was ist das? 566 00:25:45,150 --> 00:25:47,062 ZIELGRUPPE: Mit dem Anzug. 567 00:25:47,062 --> 00:25:47,770 SPRECHER: Mit dem Anzug. 568 00:25:47,770 --> 00:25:50,630 Also zuerst sie Clustering werden alle Diamanten zusammen 569 00:25:50,630 --> 00:25:52,560 es scheint, alle der Herzen zusammen wie es scheint, 570 00:25:52,560 --> 00:25:56,520 und so weiter, ohne Respekt für die Zahlen auf den Karten. 571 00:25:56,520 --> 00:26:00,900 Und jetzt erscheinen sie, zum Beispiel, von Nummer werden sortiert sie. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Sehr gut. 574 00:26:08,910 --> 00:26:12,370 >> Alles klar, so was ist zu gehen der letzte Schritt sein, dann hier? 575 00:26:12,370 --> 00:26:16,950 Einmal haben wir vier sortierten Anzüge, was wollen wir zu den vier Pfählen tun müssen 576 00:26:16,950 --> 00:26:20,059 um eines zu erreichen sortiert Deck, ganz einfach? 577 00:26:20,059 --> 00:26:21,350 Also müssen wir sie wieder zusammenzuführen. 578 00:26:21,350 --> 00:26:25,160 >> So gibt es eine interessante Idee, die wieder, wage zu behaupten, ist sehr intuitiv, auch 579 00:26:25,160 --> 00:26:28,140 wenn Sie vielleicht nie geschlagen haben diese Art von Etikett auf sie. 580 00:26:28,140 --> 00:26:31,900 Dieser Grundgedanke des Teilens das Problem nicht in der Hälfte dieser Zeit, 581 00:26:31,900 --> 00:26:33,410 aber zumindest in vier Teile. 582 00:26:33,410 --> 00:26:36,810 Lösung ziemlich grundsätzlich identisch Probleme 583 00:26:36,810 --> 00:26:40,480 isoliert von einander, und dann die Zusammenführung der Ergebnisse. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Und, ausgezeichnet, getan. 586 00:26:50,140 --> 00:26:52,140 Alles klar, ein großer runder Applaus, wenn wir könnten. 587 00:26:52,140 --> 00:26:56,480 >> [Applaus] 588 00:26:56,480 --> 00:26:59,740 >> SPRECHER: Ich habe keine Ahnung, was Sie zu tun mit diesen, aber hier gehen Sie. 589 00:26:59,740 --> 00:27:01,690 Vielen Dank. 590 00:27:01,690 --> 00:27:04,660 Also mal sehen, nur zwei Minuten und acht Sekunden 591 00:27:04,660 --> 00:27:07,490 Wenn Sie möchten, dass Ihre Freunde herauszufordern. 592 00:27:07,490 --> 00:27:12,160 Was ist dann zu gehen Seien Sie ein Mitnehmen von diesem 593 00:27:12,160 --> 00:27:13,830 dass wir in der Regel mehr nutzen können? 594 00:27:13,830 --> 00:27:16,080 Nun, denken Sie zurück an Diese Reihe von Zahlen, 595 00:27:16,080 --> 00:27:19,060 und denke, jetzt zurück auf einige der Pseudocode, die wir in der Vergangenheit geschrieben, 596 00:27:19,060 --> 00:27:22,080 und dies war der Pseudocode für Lösung des Telefonbuch Problem. 597 00:27:22,080 --> 00:27:25,150 Wobei ich in Pseudocode aufgezählt eine methodisch 598 00:27:25,150 --> 00:27:28,400 zu beschreiben, wie ich eine sehr intuitive menschliche Algorithmus der Unterteilung der Telefon 599 00:27:28,400 --> 00:27:31,650 Buch in zwei Hälften, wiederholen, wiederholen, wiederholen, bis ich jemanden wie Mike Smith, 600 00:27:31,650 --> 00:27:33,790 wenn er tatsächlich im Telefonbuch. 601 00:27:33,790 --> 00:27:37,610 >> Aber ich Art von verwendet, was ich nennen ein sehr iterativen Ansatz hier 602 00:27:37,610 --> 00:27:42,160 insbesondere Ankündigung Linie 8 und Linie 11. 603 00:27:42,160 --> 00:27:46,750 Das sind Hinweise auf eine iterative Ansatz, eine Looping-Ansatz, 604 00:27:46,750 --> 00:27:49,040 denn das ist genau das Verhalten, das sie auslösen. 605 00:27:49,040 --> 00:27:52,910 Diese Linien beide sagen, gehen Sie zu Linie drei, und Sie können Art 606 00:27:52,910 --> 00:27:55,140 denken, dass in Ihrem geistigen Auge als eine Schleife. 607 00:27:55,140 --> 00:27:59,080 Es sagt dir, zurück bis zum Schritt drei und wiederholen, wieder und wieder, 608 00:27:59,080 --> 00:28:00,010 und wieder. 609 00:28:00,010 --> 00:28:04,410 >> Aber was, wenn wir eine Schlüsselidee nutzen hier, dass wir nicht das letzte Mal, 610 00:28:04,410 --> 00:28:10,280 und zu vereinfachen, und die Linie 8 Linie 11 und ihre Nachbarn 611 00:28:10,280 --> 00:28:12,840 als nur dies, in gelb. 612 00:28:12,840 --> 00:28:16,480 Es ist nicht grundsätzlich zu verkürzen Der Pseudocode sehr, 613 00:28:16,480 --> 00:28:20,530 aber es ist grundlegend verändern die Natur meiner Algorithmus. 614 00:28:20,530 --> 00:28:24,220 Was ich jetzt sage, in Schritt 7, in Schritt 10, 615 00:28:24,220 --> 00:28:29,140 ist es für Mike zu suchen in genau der gleichen Weise, 616 00:28:29,140 --> 00:28:31,580 aber nur in der linken Hälfte oder die rechte Hälfte. 617 00:28:31,580 --> 00:28:33,420 >> In anderen Worten, wenn Ich gehe von einem Schritt, 618 00:28:33,420 --> 00:28:36,150 abholen Telefonbuch, offen für Mitte von Telefonbuch, Blick auf Namen, 619 00:28:36,150 --> 00:28:39,010 wenn Smith ist unter Namen, rufen Mike, sonst 620 00:28:39,010 --> 00:28:44,340 wenn Smith ist früher im Buch Schritt sieben Suche nach Mike in der linken Hälfte des Buches. 621 00:28:44,340 --> 00:28:47,130 Aber diese Art von Gefühl, es ließ mich hängen, oder? 622 00:28:47,130 --> 00:28:49,240 In gelb, ist ein Unterricht, aber wie kann ich 623 00:28:49,240 --> 00:28:51,870 Suche nach Mike in der linken Hälfte des Telefonbuchs? 624 00:28:51,870 --> 00:28:54,210 Wo muss ich eine Algorithmus, mit dem ich 625 00:28:54,210 --> 00:28:57,100 kann für jemanden wie Mike Smith zu suchen? 626 00:28:57,100 --> 00:28:58,980 Nun, es ist starrte uns ins Gesicht. 627 00:28:58,980 --> 00:29:03,090 Ich kann buchstäblich mit dem exakt gleichen Programm effektiv gehen bis an die Spitze 628 00:29:03,090 --> 00:29:06,490 wieder und wieder Lauf die gleichen Codezeilen. 629 00:29:06,490 --> 00:29:10,610 >> Also auch wenn dies fühlen wie ein bisschen eine zyklische Definition 630 00:29:10,610 --> 00:29:13,480 wo Sie die Beantwortung jemand ist Frage einfach so zu fragen, 631 00:29:13,480 --> 00:29:15,990 die gleiche Frage wieder, wie, warum, warum, warum? 632 00:29:15,990 --> 00:29:21,580 Die Realität ist, weil wir hart codiert haben ein paar spezielle Linien, Schritt 4, 633 00:29:21,580 --> 00:29:25,320 was ein, wenn und Schritt 12 wird die ist tatsächlich ein weiterer Zweig, 634 00:29:25,320 --> 00:29:30,120 denn wir haben diese Notlösungen, Dieser Algorithmus wird beendet, wenn wir 635 00:29:30,120 --> 00:29:32,050 Mike zu finden, oder wenn wir es nicht tun. 636 00:29:32,050 --> 00:29:36,810 Aber in Schritt 7 und 10 jetzt haben wir was wir einen rekursiven Algorithmus nennen. 637 00:29:36,810 --> 00:29:40,420 Und Rekursion ist in der Tat eine mächtige Idee das ist ein wenig Geist Biegen auf den ersten, 638 00:29:40,420 --> 00:29:42,500 dass wir nun wie folgt anzuwenden. 639 00:29:42,500 --> 00:29:46,600 >> Mergesort wird die letzte Art sein, dass wir uns, zumindest in der Klasse formal. 640 00:29:46,600 --> 00:29:50,040 Und es grundlegend anders ist aus diesen letzten drei, und sicherlich 641 00:29:50,040 --> 00:29:52,140 letzten vier, wenn wir gehören bogosort. 642 00:29:52,140 --> 00:29:54,810 Hier ist der Pseudocode für Merge-Sort. 643 00:29:54,810 --> 00:30:00,170 Wenn am Eingang von n Elementen, so gegeben ein Array der Größe n ist, wenn n kleiner als 2 ist, 644 00:30:00,170 --> 00:30:01,040 zurück. 645 00:30:01,040 --> 00:30:03,610 Also warum habe ich, dass Vernunft prüfen Sie zuerst? 646 00:30:03,610 --> 00:30:09,477 Was ist die Implikation, wenn ich Hand, die Sie ein Feld, dessen Länge n kleiner als 2? 647 00:30:09,477 --> 00:30:11,060 Es ist bereits sortiert, offensichtlich, nicht wahr? 648 00:30:11,060 --> 00:30:13,640 Da die Liste entweder ein Element, das trivial ist 649 00:30:13,640 --> 00:30:15,180 geordnet, weil es das einzige, was es gibt. 650 00:30:15,180 --> 00:30:18,138 Oder ist es von der Größe Null, was bedeutet, gibt es nichts zu sortieren, so von der Natur 651 00:30:18,138 --> 00:30:18,720 sie sortiert. 652 00:30:18,720 --> 00:30:20,410 Es gibt einfach nichts falsch gibt. 653 00:30:20,410 --> 00:30:22,310 Also das ist unsere sogenannte Basisfall. 654 00:30:22,310 --> 00:30:24,440 >> Das ist im Geiste zu dem, was wir mit Mike tat. 655 00:30:24,440 --> 00:30:26,023 Wenn Mike im Telefonbuch, rufen Sie ihn. 656 00:30:26,023 --> 00:30:27,740 Wenn er nicht da ist, aufzugeben. 657 00:30:27,740 --> 00:30:31,240 Es ist eine so genannte Basisfall, um sicherzustellen, dass Dieser Algorithmus am Ende des Tages 658 00:30:31,240 --> 00:30:33,540 unter bestimmten Umständen zu stoppen. 659 00:30:33,540 --> 00:30:37,890 >> Aber hier ist der Sprung des Glaubens jetzt, sonst, sortieren Sie die linke Hälfte der Elemente, 660 00:30:37,890 --> 00:30:39,740 dann sortieren Sie die richtige die Hälfte der Elemente, 661 00:30:39,740 --> 00:30:41,189 und dann verschmelzen die sortierten Hälften. 662 00:30:41,189 --> 00:30:43,230 Und hier, wo es sich anfühlt wie wir ausklinken. 663 00:30:43,230 --> 00:30:46,900 Ich habe Sie aufgefordert, zu sortieren n Elemente, und ich bin 664 00:30:46,900 --> 00:30:50,712 sagen, OK, tun Sie es durch die Sortierung Die linke und die Sortierung der rechten Seite. 665 00:30:50,712 --> 00:30:52,420 Aber ich sage, eine andere Sache, und das 666 00:30:52,420 --> 00:30:55,530 ist das zentrale Thema scheint es in der Anschauung so weit, 667 00:30:55,530 --> 00:30:57,380 da ist dieser dritte Schritt der Zusammenführung. 668 00:30:57,380 --> 00:31:00,430 Welches, obwohl es scheint so dumm im Geist, 669 00:31:00,430 --> 00:31:02,320 wie einfach Dinge zusammenführen zusammen scheint 670 00:31:02,320 --> 00:31:05,380 für einen entscheidenden Schritt in Richtung der sein Zusammenbau von zwei Probleme, die 671 00:31:05,380 --> 00:31:07,330 wurden schließlich in zwei Hälften geteilt. 672 00:31:07,330 --> 00:31:12,090 >> So verschmelzen Art, lassen Sie uns das tun, wenn du Humor mich, mit einer weiteren Demonstration, 673 00:31:12,090 --> 00:31:14,730 gerade so, dass wir einige Zahlen zu arbeiten. 674 00:31:14,730 --> 00:31:19,470 Kann ich tauschen acht Stress Bälle für acht Personen? 675 00:31:19,470 --> 00:31:29,320 Alle Rechte, wie über Sie drei, vier Sie in diesem Abschnitt, fünf, sechs, und lassen Sie uns 676 00:31:29,320 --> 00:31:30,720 Sie 7, 8, kommen Sie auf. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ja OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, dort gehen wir, plus 1. 680 00:31:38,640 --> 00:31:39,150 Ausgezeichnet. 681 00:31:39,150 --> 00:31:42,000 Alle Rechte an kommen, lassen Sie uns schnell geben Ihnen Zahlen. 682 00:31:42,000 --> 00:31:50,800 Nummer zwei, Nummer drei, Nummer vier, Nummer fünf, sechs, sieben und acht. 683 00:31:50,800 --> 00:31:52,140 Ich habe acht richtig diese Zeit. 684 00:31:52,140 --> 00:31:56,390 >> OK, so gehen Sie vor, wenn Sie könnten, und Lassen Sie uns in der ursprünglichen Reihenfolge zu sortieren 685 00:31:56,390 --> 00:31:59,810 dass wir gestern die aussahen, wie diese, wenn Sie nichts dagegen haben. 686 00:31:59,810 --> 00:32:03,620 Und lass es uns tun vor dem Tisch. 687 00:32:03,620 --> 00:32:06,510 Alles in Ordnung, so verschmelzen Sorte. 688 00:32:06,510 --> 00:32:08,820 Dies ist, wo es geht um irgendwie interessant zu erhalten, 689 00:32:08,820 --> 00:32:12,800 weil ich zu sein scheinen mich geben so viel weniger Informationen heute. 690 00:32:12,800 --> 00:32:15,149 >> So verschmelzen Art zunächst am Eingang von n Elementen, 691 00:32:15,149 --> 00:32:18,440 und ist offensichtlich nicht kleiner als zwei ist, ist es acht, so habe ich etwas mehr Arbeit zu tun. 692 00:32:18,440 --> 00:32:21,140 So, jetzt haben wir mental als Klasse sind jetzt in der else-Zweig, 693 00:32:21,140 --> 00:32:22,540 was bedeutet, drei Schritte. 694 00:32:22,540 --> 00:32:25,017 Zuerst habe ich, um die Sortier linke Hälfte der Elemente. 695 00:32:25,017 --> 00:32:26,350 So, wie ich über das tun dies gehen? 696 00:32:26,350 --> 00:32:28,950 Nun, ich werde Art von hier geistig teilen die Liste, 697 00:32:28,950 --> 00:32:30,700 Sie nicht zu haben, körperlich zu bewegen, und ich bin 698 00:32:30,700 --> 00:32:33,180 gehen, sich nur auf das konzentrieren, linke Hälfte der Elemente hier. 699 00:32:33,180 --> 00:32:36,770 So, wie ich über die Sortierung gehen eine Liste jetzt von der Größe vier? 700 00:32:36,770 --> 00:32:38,730 Was ist mein Algorithmus? 701 00:32:38,730 --> 00:32:42,580 Zuerst habe ich überprüfen, ist n weniger als zwei, nein, so dass ich zu der else-Block gehen wieder. 702 00:32:42,580 --> 00:32:43,900 Sortieren linke Hälfte der Elemente. 703 00:32:43,900 --> 00:32:45,608 >> So, jetzt wieder, mental, und dies ist, wo 704 00:32:45,608 --> 00:32:49,550 Sie, eine Menge sammeln müssen, Geistesgeschichte, wenn man so will. 705 00:32:49,550 --> 00:32:51,940 Jetzt bin ich die Sortierung der linken Hälfte der linken Hälfte. 706 00:32:51,940 --> 00:32:57,000 Alles klar, so jetzt meine gleichen Merge rufe ich Sortieralgorithmus ist n weniger als zwei? 707 00:32:57,000 --> 00:33:00,590 Nein, es ist zwei, so dass ich zu sortieren die linke Hälfte, und die rechte Hälfte. 708 00:33:00,590 --> 00:33:02,042 Also hier gehen wir, sortieren Sie die linke Hälfte. 709 00:33:02,042 --> 00:33:03,750 Warum gehst du nicht einfach einen Schritt weiter. 710 00:33:03,750 --> 00:33:04,415 Wie heißen Sie? 711 00:33:04,415 --> 00:33:04,860 >> ZIELGRUPPE: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPRECHER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan hat vorgetreten. 714 00:33:06,040 --> 00:33:06,748 >> ZIELGRUPPE: Darren. 715 00:33:06,748 --> 00:33:09,000 SPRECHER: Darren, fertig. 716 00:33:09,000 --> 00:33:10,090 Haben Sie Darren oder Dan sagen? 717 00:33:10,090 --> 00:33:10,550 >> ZIELGRUPPE: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPRECHER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren hat trat nach vorne und er nun sortiert. 720 00:33:14,422 --> 00:33:16,130 Und das ist fast ein albern Anspruch, oder? 721 00:33:16,130 --> 00:33:18,862 Ich weiß nicht wirklich zu sein scheinen erreichen nichts, aber lassen Sie uns gehen. 722 00:33:18,862 --> 00:33:20,820 Nun lassen Sie mich die richtige Art Hälfte der Elemente. 723 00:33:20,820 --> 00:33:21,200 Wie heißen Sie? 724 00:33:21,200 --> 00:33:21,690 >> ZIELGRUPPE: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPRECHER: Luke. 726 00:33:22,273 --> 00:33:23,400 Komm, Schritt nach vorn. 727 00:33:23,400 --> 00:33:25,640 Getan, habe ich Luke sortiert. 728 00:33:25,640 --> 00:33:28,570 Die linke Hälfte ist nun sortiert und die rechte Hälfte ist nun sortiert, 729 00:33:28,570 --> 00:33:30,770 aber wieder, es gibt hier ein wichtiger Schritt. 730 00:33:30,770 --> 00:33:32,940 Was muss ich nächstes tun müssen? 731 00:33:32,940 --> 00:33:33,941 Verschmelzen die sortierten Hälften. 732 00:33:33,941 --> 00:33:36,648 Jetzt werden wir einfach nur jeder in dieser Art und Weise hin und her, 733 00:33:36,648 --> 00:33:38,620 weil ich irgendwie müssen einige Kratzer Raum. 734 00:33:38,620 --> 00:33:40,411 Es ist fast wie diese Jungs sind auf einem Tisch, 735 00:33:40,411 --> 00:33:42,460 und ich brauche etwas Platz sie bewegen sich auf. 736 00:33:42,460 --> 00:33:44,170 Also werde ich zu fusionieren Sie Kerle suchen 737 00:33:44,170 --> 00:33:45,960 an der linken Hälfte und der rechten Hälfte. 738 00:33:45,960 --> 00:33:48,740 Und die offensichtlich kommt zuerst, linke Hälfte oder rechte Hälfte? 739 00:33:48,740 --> 00:33:52,710 So rechte Hälfte, so lassen Sie uns nun über Luke hier in die ursprüngliche Position Darrens. 740 00:33:52,710 --> 00:33:57,640 Und jetzt, ihre linke Hälfte in fusionieren, Darren geht um genau dort zu bewegen. 741 00:33:57,640 --> 00:33:59,750 >> So fühlt sich an wie fast eine Blase Art-Effekt, 742 00:33:59,750 --> 00:34:02,482 aber meine Grundalgorithmus sehr dieses Mal anders. 743 00:34:02,482 --> 00:34:04,815 Aber jetzt ist, wo die Dinge ein wenig ärgerlich, weil Sie 744 00:34:04,815 --> 00:34:06,810 müssen geistig zurückspulen wo habe ich aufhören. 745 00:34:06,810 --> 00:34:09,893 Ich habe gerade fusionierte die sortierten Hälften, das heißt ich bin, wo in meinem Algorithmus? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Ich muss die rechte Hälfte zu sortieren, oder? 748 00:34:13,770 --> 00:34:15,910 >> Wenn Sie zurückspulen, wörtlich auf dem Video, werden Sie 749 00:34:15,910 --> 00:34:18,339 sehen, dass wir das bekommen Punkt von Luke und Darren 750 00:34:18,339 --> 00:34:21,370 durch die Sortierung der linken Hälfte der linken Hälfte. 751 00:34:21,370 --> 00:34:23,430 Dann zusammengeführt, die wir sortierten Hälften, die 752 00:34:23,430 --> 00:34:27,941 bedeutet, dass der nächste Schritt ist die Art rechte Hälfte der linken Hälfte. 753 00:34:27,941 --> 00:34:29,649 Alles klar, also lassen Sie uns tun dies schneller. 754 00:34:29,649 --> 00:34:33,282 Alle Rechte, sechs, ich werde Anspruch Sie werden nun sortiert, kommen Sie nach vorne. 755 00:34:33,282 --> 00:34:33,990 Wie heißen Sie? 756 00:34:33,990 --> 00:34:34,589 >> ZIELGRUPPE: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPRECHER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano ist nun sortiert. 759 00:34:36,010 --> 00:34:36,450 Und was ist Ihr Name? 760 00:34:36,450 --> 00:34:37,080 >> ZIELGRUPPE: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPRECHER: Alex ist nun sortiert. 762 00:34:38,379 --> 00:34:40,750 Linke Hälfte, rechte Hälfte, was ist der letzte Schritt? 763 00:34:40,750 --> 00:34:41,250 Zusammenführen. 764 00:34:41,250 --> 00:34:44,310 Ziemlich trivial, also bin ich werde in sechs zusammenzuführen, 765 00:34:44,310 --> 00:34:46,930 einen Schritt zurück, acht, einen Schritt zurück. 766 00:34:46,930 --> 00:34:49,530 Und jetzt merken, das ist eine sinnvolle Gerichte zum Mitnehmen, was 767 00:34:49,530 --> 00:34:53,930 jetzt wahr ist über die linke Hälfte der Liste, unabhängig davon, wie wir begonnen? 768 00:34:53,930 --> 00:34:55,090 Es wird sortiert. 769 00:34:55,090 --> 00:34:57,750 >> Jetzt ist es nicht sortiert Der große Plan der Dinge, 770 00:34:57,750 --> 00:35:00,250 aber es wird unabhängig sortiert von der anderen Hälfte. 771 00:35:00,250 --> 00:35:04,100 Nun, was ich Schritt auf, wenn ich halten Zurückspulen, wie die Geschichte begann? 772 00:35:04,100 --> 00:35:05,680 Jetzt muss ich die rechte Hälfte zu sortieren. 773 00:35:05,680 --> 00:35:07,630 So, jetzt zurück zu wir der Anfang der Geschichte, 774 00:35:07,630 --> 00:35:08,921 und lassen Sie uns dies schneller. 775 00:35:08,921 --> 00:35:11,320 Also werde ich, um die Sortier rechte Hälfte der gesamten Liste. 776 00:35:11,320 --> 00:35:13,060 Was ist der nächste Schritt? 777 00:35:13,060 --> 00:35:15,840 Sortieren Sie die linke Hälfte der rechten Hälfte. 778 00:35:15,840 --> 00:35:18,715 Sortieren Sie die linke Hälfte des linken Hälfte der rechten Hälfte. 779 00:35:18,715 --> 00:35:19,590 Und was ist Ihr Name? 780 00:35:19,590 --> 00:35:20,230 >> ZIELGRUPPE: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPRECHER: Omar Schritt vorwärts getan. 782 00:35:21,970 --> 00:35:22,860 Linke Hälfte wird sortiert. 783 00:35:22,860 --> 00:35:23,330 Und was ist Ihr Name? 784 00:35:23,330 --> 00:35:23,820 >> ZIELGRUPPE: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPRECHER: Chris, einen Schritt vorwärts, Sie sind jetzt sortiert. 786 00:35:25,620 --> 00:35:27,010 Was ist der entscheidende Schritt ist jetzt? 787 00:35:27,010 --> 00:35:27,510 Zusammenführen. 788 00:35:27,510 --> 00:35:30,509 Also man geht, um an Ort und Stelle zusammen hier, wenn Sie einen Schritt zurück machen, 789 00:35:30,509 --> 00:35:32,930 und drei zu gehen einen Schritt zurück, zu verschmelzen. 790 00:35:32,930 --> 00:35:38,080 So ist die linke Hälfte des rechte Hälfte ist nun sortiert. 791 00:35:38,080 --> 00:35:41,747 Ehrlich gesagt, fühlt sich dieser Algorithmus wie wir verschwenden Weise mehr Zeit als zuvor, 792 00:35:41,747 --> 00:35:44,830 aber wenn wir taten dies in Echtzeit, werden wir sehen, was die Imbissbuden sein wird. 793 00:35:44,830 --> 00:35:47,970 Jetzt bin ich hier, direkt Hälfte der rechten Hälfte, 794 00:35:47,970 --> 00:35:50,170 lassen Sie mich gehen Sie vor und sortieren die linke Hälfte. 795 00:35:50,170 --> 00:35:51,482 Schritt nach vorn, was ist Ihr Name? 796 00:35:51,482 --> 00:35:52,190 ZIELGRUPPE: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPRECHER: Ramsey ist nun sortiert. 798 00:35:53,210 --> 00:35:53,570 Wie heißen Sie? 799 00:35:53,570 --> 00:35:54,200 >> ZIELGRUPPE: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPRECHER: Marina wird nun als geordnet Nun, wenn Sie einen Schritt nach vorne machen. 801 00:35:57,033 --> 00:36:00,690 Schlüsselschritt ist hier nun zusammenführen, ich bin werde von meinen beiden Listen pflücken, 802 00:36:00,690 --> 00:36:01,720 links und rechts. 803 00:36:01,720 --> 00:36:05,150 Fünf wird sich zuerst kommt, und sieben als nächstes kommen. 804 00:36:05,150 --> 00:36:06,410 Und wieder, das ist gewollt. 805 00:36:06,410 --> 00:36:08,535 Die Tatsache, dass sie unter Schritte nach vorn und wieder zurück 806 00:36:08,535 --> 00:36:12,997 soll darstellen, dass wir nicht tun Sie diesen Algorithmus in Ort so leicht 807 00:36:12,997 --> 00:36:15,830 als Bubble-Sort und Selection Sort, und Insertion Sort, wo wir nur 808 00:36:15,830 --> 00:36:16,960 gehalten tauschen Menschen. 809 00:36:16,960 --> 00:36:19,940 Ich muss buchstäblich eine Art von Grund auf Papier, in dem 810 00:36:19,940 --> 00:36:21,827 , diese Leute setzen während ich die Zusammenführung, 811 00:36:21,827 --> 00:36:23,410 und dann kann ich sie wieder in Kraft gesetzt. 812 00:36:23,410 --> 00:36:27,260 Und das ist der Schlüssel, weil ich mit ein neue Ressource, Raum, nicht nur Zeit. 813 00:36:27,260 --> 00:36:28,270 >> OK, das ist erstaunlich. 814 00:36:28,270 --> 00:36:32,050 Linke Hälfte wird sortiert, rechte Hälfte ist sortiert, jetzt, dass die Schlüsselvereinigungsschritt. 815 00:36:32,050 --> 00:36:33,450 Wie werde ich diese zusammenführen? 816 00:36:33,450 --> 00:36:35,470 Also, wenn Sie folgen meiner links und rechts, 817 00:36:35,470 --> 00:36:38,930 Ich werde meine linke Hand darauf auf der linken Hälfte, meine rechte Hand 818 00:36:38,930 --> 00:36:42,680 auf der rechten Hälfte, und jetzt muss ich Schritt für Schritt entscheiden, wen sie in zusammenzuführen. 819 00:36:42,680 --> 00:36:44,650 Die offensichtlich kommt zuerst? 820 00:36:44,650 --> 00:36:45,150 Nummer eins. 821 00:36:45,150 --> 00:36:47,327 Also komm hier, hier ist unsere Notizblock. 822 00:36:47,327 --> 00:36:49,910 So, jetzt die Nummer eins, und Kündigungsfrist was ich mit meiner rechten Hand zu tun, 823 00:36:49,910 --> 00:36:54,152 Ich werde meiner rechten Hand eine Bewegung Schritt über zu Punkt Nummer drei, 824 00:36:54,152 --> 00:36:55,860 und jetzt habe ich zu machen die gleiche Entscheidung. 825 00:36:55,860 --> 00:36:58,387 Und tatsächlich stehen direkt im vor Luke hier, wenn Sie könnten, 826 00:36:58,387 --> 00:36:59,720 denn dies ist unsere Notizblock. 827 00:36:59,720 --> 00:37:00,610 Also, wer kommt als nächstes? 828 00:37:00,610 --> 00:37:05,000 Wir haben Luke mit Nummer zwei oder Chris mit Nummer drei. 829 00:37:05,000 --> 00:37:07,460 Offensichtlich Luke, die Anzahl zwei, so dass Sie hierher kommen. 830 00:37:07,460 --> 00:37:11,270 >> Aber meine linke Hand nun an gehen erhöht, um bei Darren verweisen, 831 00:37:11,270 --> 00:37:15,160 und hier ist der Schlüssel wegnehmen mit Verschmelzung, werde ich weiter machen, 832 00:37:15,160 --> 00:37:17,340 Selbstverständlich, wenn Sie so freundlich von der Logik. 833 00:37:17,340 --> 00:37:19,670 Aber meine Hände sind nie gehen, rückwärts zu gehen, 834 00:37:19,670 --> 00:37:23,861 das heißt ich bin immer nur zu bewegen links mit meiner Vereinigungsprozess, 835 00:37:23,861 --> 00:37:26,360 und das wird Schlüssel zu sein unsere Analyse in nur einem Augenblick. 836 00:37:26,360 --> 00:37:27,859 >> So, jetzt wollen wir beenden diese rasch. 837 00:37:27,859 --> 00:37:31,650 So kommt nächsten drei, dann vier nächstes kommt, 838 00:37:31,650 --> 00:37:38,750 und jetzt fünf als nächstes kommt, dann sechs, und sieben, und dann schließlich acht. 839 00:37:38,750 --> 00:37:42,960 Fühlt sich an wie der langsamste Algorithmus noch nicht, aber nicht, wenn wir tatsächlich 840 00:37:42,960 --> 00:37:45,510 führen Sie es auf die gleiche Art der Taktgeschwindigkeit, so zu 841 00:37:45,510 --> 00:37:48,106 sprechen, mit dem gleichen tickende Uhr wie zuvor. 842 00:37:48,106 --> 00:37:48,605 Warum? 843 00:37:48,605 --> 00:37:51,100 Nun, lassen Sie uns einen Blick auf das Endergebnis. 844 00:37:51,100 --> 00:37:56,990 >> Gehen wir zurück hier, lassen Sie mich ziehen Sie sich einen Demo-visuell 845 00:37:56,990 --> 00:37:59,030 von dem, was wir gerade getan. 846 00:37:59,030 --> 00:38:06,110 Zoomen Sie hier, auf diese Seite hier, erzählt Firefox 847 00:38:06,110 --> 00:38:08,200 dass wir in die Warteschlange möchte in dieser Box, lassen Sie uns 848 00:38:08,200 --> 00:38:11,260 sagen Blase Art, mit der wir sind jetzt gut vertraut, 849 00:38:11,260 --> 00:38:14,130 Auswahl Art, die eine andere ist recht einfach eine, 850 00:38:14,130 --> 00:38:18,250 und jetzt heute Mergesort, die Höhepunkt am Ende wird unser sein. 851 00:38:18,250 --> 00:38:21,530 Der Grund, es hat so viel mehr hier mit Menschen und mich verbal ist, 852 00:38:21,530 --> 00:38:23,480 offensichtlich, ich erkläre jeden Schritt. 853 00:38:23,480 --> 00:38:26,920 Aber wenn man einfach führen Sie diese, viel wie wir Bubble-Sort und Auswahl 854 00:38:26,920 --> 00:38:30,890 Art nicht nur optisch, Uhr wie viel effizienter 855 00:38:30,890 --> 00:38:33,330 Diese Hebelwirkung von Teilung und Eroberung 856 00:38:33,330 --> 00:38:39,150 können, wenn sie einem Datensatz, der angewendet werden nicht einmal Größe acht, aber noch viel, 857 00:38:39,150 --> 00:38:39,970 viel größer. 858 00:38:39,970 --> 00:38:44,585 Ich gebe Ihnen von Mergesort, Seiten Seite mit diesen anderen Algorithmen. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Das wird schmerzhaft zu bekommen schnell, und das Ende 861 00:38:58,530 --> 00:39:00,890 ist nicht besonders klimatische, sie nur am Ende sortiert. 862 00:39:00,890 --> 00:39:05,280 Aber der Schlüssel ist, dass wegnehmen Schauen Sie, wie viel schneller Mergesort 863 00:39:05,280 --> 00:39:08,110 war, es sei denn, Sie denken, ich bin nur irgendwie durcheinander mit Ihnen. 864 00:39:08,110 --> 00:39:13,100 Wenn wir diese ein letztes Mal, Lassen Sie uns diese neu zu laden, gehen wir zurück 865 00:39:13,100 --> 00:39:14,960 und wählen Sie Bubble-Sort, und nur zum Spaß, 866 00:39:14,960 --> 00:39:17,330 wählen wir Insertion Art, nur für eine gute Maßnahme. 867 00:39:17,330 --> 00:39:20,020 Und dieses Mal wieder, lassen Sie uns wählen Sie Merge-Sort und lassen Sie uns 868 00:39:20,020 --> 00:39:21,595 tatsächlich ausgeführt werden diese nebeneinander. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Und es ist nicht, in der Tat, ein Zufall. 871 00:39:26,930 --> 00:39:31,140 Was ich getan wirksam ist, ich habe unterteilt meine Eingabe in der Mitte, wieder, 872 00:39:31,140 --> 00:39:32,240 und wieder und wieder. 873 00:39:32,240 --> 00:39:35,590 Und es gibt nur so viele Male, können Sie teilen Sie Ihre Eingabe in zwei Hälften, links 874 00:39:35,590 --> 00:39:36,240 und rechts. 875 00:39:36,240 --> 00:39:39,425 Was ist die Formel, die wir sehen immer das beschreibt die Teilung in zwei Hälften 876 00:39:39,425 --> 00:39:41,050 wieder und wieder, und wieder, und wieder? 877 00:39:41,050 --> 00:39:41,890 >> ZIELGRUPPE: Melden n. 878 00:39:41,890 --> 00:39:42,760 >> SPRECHER: Melden n. 879 00:39:42,760 --> 00:39:46,300 Aber dann gibt es einen weiteren wichtigen Schritt, Dieser Algorithmus ist nicht log n Schritte. 880 00:39:46,300 --> 00:39:48,992 Wenn es nur log n Schritte, wir in der gleichen Problem 881 00:39:48,992 --> 00:39:51,200 wie vorher, wo wir nicht sicher, alles sortiert. 882 00:39:51,200 --> 00:39:54,480 Sie müssen minimal bei n Elementen suchen sicher sein, n Elemente sortiert, 883 00:39:54,480 --> 00:39:55,950 ansonsten ist es ein Sprung des Glaubens. 884 00:39:55,950 --> 00:39:59,810 >> Es ist also minimal log n Schritte, aber was ist mit diesem Schlüssel Verschmelzung Schritt 885 00:39:59,810 --> 00:40:04,370 wo ich meine linke Hälfte zusammengelegt und rechts Hälfte und ging über die Bühne? 886 00:40:04,370 --> 00:40:06,980 Wie viele Schritte ist, dass zu fusionieren? 887 00:40:06,980 --> 00:40:10,150 Es ist n, aber ich habe nicht nur verschmelzen die letzte Zeit. 888 00:40:10,150 --> 00:40:15,089 Auf jedem dieser verschachtelt Anrufe auf jeder dieser verschachtelten Zusammenführungen, habe ich noch sortiert. 889 00:40:15,089 --> 00:40:18,380 Ich fusionierte diese beiden Jungs, dann sind diese beiden Jungs, dann sind diese beiden Jungs und so weiter. 890 00:40:18,380 --> 00:40:19,955 >> Also habe ich Verschmelzung wieder und wieder. 891 00:40:19,955 --> 00:40:20,580 Wie oft? 892 00:40:20,580 --> 00:40:23,510 Also jedes Mal, ich teilte die Liste in der Hälfte, habe ich eine Zusammenführung. 893 00:40:23,510 --> 00:40:25,460 Teilen Sie die Liste in der Mitte, machen eine Zusammenführung. 894 00:40:25,460 --> 00:40:28,570 Also, wenn Division der Liste können Protokoll n-mal durchgeführt werden, 895 00:40:28,570 --> 00:40:33,880 und die Zusammenführung statt n letztlich Schritte, was man nun die obere sein 896 00:40:33,880 --> 00:40:37,000 auf der Lauf gebunden Zeit des Algorithmus? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Und in der Tat ist das, was wir hier erreicht. 899 00:40:40,560 --> 00:40:44,650 So das Gefühl, das Sie sehen, wenn visuell diese drei Dinge laufen Seite an Seite 900 00:40:44,650 --> 00:40:47,930 ist n gegen n Quadrat gegen n log n quadriert. 901 00:40:47,930 --> 00:40:51,010 Die sich grundlegend werden wir sehen, nicht nur heute sondern auch in Zukunft, 902 00:40:51,010 --> 00:40:52,760 ist viel, viel schneller. 903 00:40:52,760 --> 00:40:56,010 Ein Applaus für diese Jungs, Ich werde sie mit Stress-Bälle belohnen. 904 00:40:56,010 --> 00:41:00,260 Lassen Sie uns heute hier zu vertagen, und Wir werden uns am Montag sehen. 905 00:41:00,260 --> 00:41:02,255