SPRECHER: In Ordnung, das ist CS50. Dies ist das Ende der dritten Woche und wenn Sie nutzen bereits genommen haben, wissen, dass es Mittagessen an diesem Freitag wie üblich, wo Sie gutes Gespräch genießen können und Essen am Feuer und Eis mit einigen der CS50 Personal und Klassenkameraden. Kopf dieser URL hier. 

Jetzt können Sie sich erinnern, oder Sie bald kennen werden, diese Dinge hier, die sind am Ende gegeben des Semesters für viele Klassen. So genannte Prüfung blauen Bücher, in denen Sie schreiben Ihre Antworten auf Prüfungen. Jetzt habe ich hier 26, so blaue Bücher, auf jeden von ihnen ein Name, A bis Z. geschrieben und in der Tat die Namen sind so einfach, A bis Z. Und einer der die Ziele bei der Hand heute sein wird das fortsetzen, was begannen wir am Montag, was nicht so viel Blick auf Code, aber wirklich Blick auf Ideen und Problemlösungen. Eines der Ziele und Versprechungen des Kurses ist es, Sie zu lehren, mehr denken vorsichtig, mehr methodisch, und Probleme effizienter zu lösen. Und in der Tat, können wir das wirklich tun ohne auch nur zu berühren eine Zeile Code. So habe ich ein paar Elefanten bis heute hier, orange und blau, wenn wir einen Freiwilligen zu bekommen, vielleicht von weiter hinten als üblich. Wie wäre es recht, kommen auf Sie. Das Ziel davon wird zu sein Hilfe und verwalten diese Prüfung hier. Wie heißen Sie? 

ZIELGRUPPE: Mary Beth. SPRECHER: Mary Beth, komm auf. Lassen Sie mich das Mikrofon für Sie da. Freut mich, dich kennenzulernen. 

ZIELGRUPPE: Nice to meet you. SPRECHER: In Ordnung, so habe ich hier blaue Bücher von A bis Z, und ich werde das tun, Ich habe eine der Schülerinnen, und sie sind in etwas zufällig kommen am Ende der drei Stunden Prüfungsblock, so dass sie schließlich in einige semi-zufälliger Reihenfolge wie diese. Jetzt ist Ihre Aufgabe in nur einem Augenblick wird zu BE-- dies ist tatsächlich, wie sie bekommen in am Ende des einge die Klasse, die meisten wahrscheinlich. Ihre Aufgabe jetzt sein wird, ganz einfach, um diese blauen Bücher für uns sortieren von A bis Z. 

ZIELGRUPPE: Oh, das ist für immer zu nehmen. 

SPRECHER: Und wir werden sehen wie Sie dies tun, keinen Druck. ZIELGRUPPE: Nein, kein Druck oder nichts. 

SPRECHER: Und für Spaß, lassen wir einen Timer. 

ZIELGRUPPE: So viel Spaß, so viel Spaß. 

SPRECHER: Ich kann das Mikrofon für Sie zu halten. Alles klar, haben wir gerade verdoppelt Geschwindigkeit. So in der Zwischenzeit lassen Sie mich darstellen, was werde die Frage nach Mary Beth sein ist das, was sie tun, wie ist sie über die Lösung dieses hin? Und in der Tat, haben Sie möglicherweise nicht jemals über etwas gedacht so einfach, wie wenn Sie holen bis 26 Bücher wie dieses, die haben einen natürlichen Bestellung zu ihnen. Was das Verfahren dass Sie tatsächlich nutzen? Ist es ziemlich zufällig gerade Kommissionierung der erste Sie sehen und legt es an seiner Stelle? Haben Sie zuerst Ihre Hände bewegen Suche nach einem dann auf der Suche nach B? Haben Sie einen Blick auf eine nehmen Paar von nebeneinander und einfach sagen, warten Sie eine Minute, dieses ist nicht richtig, und dann tauschen die Reihenfolge? Wir sahen bereits am Montag, dass es eine Reihe von Möglichkeiten, in dem wir dies tun, und in der Tat, wie wir am Ende hier, Ich möchte darauf hinweisen, vielleicht nehmen von dem, was Mary Beth tut. Wir haben ein paar Pfähle so scheint es, ein größer eins, drei kleinere. 

ZIELGRUPPE: Ich bestelle sie wenn ich zwei Buchstaben dass ich weiß, sind zusammen in einer Sequenz, Ich legte sie zusammen, so dass ich nicht müssen über das Halten Sorgen Spur von einer ganzen Reihe von Pfund. Es ist nur, oh, A ist die erste, Ich habe diesen Stapel hier. SPRECHER: So, fast wie Ein Puzzle-Stücke, die haben die richtige Form, um passen miteinander. ZIELGRUPPE: Ziemlich viel, ja. SPRECHER: OK, ausgezeichnet. Und nun jede dieser Pfähle vermutlich sortiert? 

ZIELGRUPPE: Ja. 

SPRECHER: In Ordnung, A bis Z. Alle Recht herzlichen Glückwunsch, du hast es geschafft. Sie haben Ihre Wahl. Blue? Alles klar, vielen Dank dafür. So Mary Beth hat vorschlagen was ihr Ansatz war, aber was ist ein weiterer Ansatz, wie Sie könnte über das Sortieren, diese Dinge gehen? Was hätten Sie getan? Der Rekord zu schlagen gewesen wäre, einer Minute und 50 Sekunden oder so, und die, die ich vergessen zu zählen. Was hätten Sie getan? Ja? ZIELGRUPPE: Nehmen Sie den Stapel. Starten Sie von Anfang an. Überprüfen Sie Ihre Papiere. Und wenn der oberste höher ist als, vielleicht sind sie, die untere ist höher, dann schalten Sie sie. 

SPRECHER: OK, also ab an der Oberseite und der Unterseite, und dann arbeiten Sie Ihren Weg nach innen so, Tausch? OK, so ein wenig ähnlich im Geist zu Bubble-Sort, Aber die Wahl der Extreme nicht die benachbarten Paare. Aber die Rede kurzer Sinn ist, dass es sicherlich eine Reihe von verschiedenen Möglichkeiten, wir könnten dies tun, und ehrlich gesagt, ich glaube, Sie Art von angenommen ein paar Ansätze, oder? Sie haben Art vier sortierten Haufen, und dann effektiv zusammengeführt sie zusammen. Und das ist, wage zu behaupten, ein anderer Technik überhaupt. Sie nicht behandeln es als einen großen Haufen, Sie das Problem aufgeteilt in vier Quads, wenn man will, und dann irgendwie verschmolzen sie am Ende. 

So betrachten wir letztlich Wie sonst könnten wir das tun. Wir formalisiert den Begriff von Bubble-Sort letzten Mal, und Bubble-Sort Rückruf war ein Algorithmus, die wir visualisiert mit acht von Ihren Klassenkameraden hier oben, scheinbar zufällig auf den ersten sortiert. Und wir dann beschlossen, paarweise, wenn zwei Elemente sind nicht in Ordnung, einfach tauschen sie. So vier und zwei offensichtlich nicht in Ordnung, so die beiden Klassenkameraden Schaltstellungen. Und dann wiederholt man mit vier bis sechs, dann sechs und acht, bei jeder Iteration, Bewegen nach rechts. 

So gegeben acht Personen, wie viele paarweise Vergleiche habe ich getan, beim Gehen von In einer solchen Iteration von links nach rechts? Wie viele Vergleiche? Sieben, oder? Denn wenn es acht Personen, aber Sie haben das Paar sie und halten Sie in Bewegung einen Sprung nach rechts, du wirst doch nicht um acht haben Vergleiche, da kann man nicht vergleichen ein Element mit sich selbst, oder es würde nur sinnlos, so dass Sie sieben haben. Oder allgemeiner, wenn wir haben n Personen, die wir tun n minus 1 Vergleiche mit Bubble-Sort. 

Also lassen Sie uns jetzt überlegen, wie gut oder schlechte Blase Art tatsächlich war, und versuchen Wortschatz, um uns mit zu geben Algorithmen, die Kritik wie diese, und bald unsere eigenen. So im ersten Durchgang durch Blasensortierung, die erstmals Ich ging von links nach rechts über die Bühne, nahm mich n minus 1 Vergleiche. Und das wird mein Maßeinheit, oder? Ich war irgendwie reden und Bummeln, etwas schnell, etwas langsam, so Zählen meine Anzahl von Sekunden ist nicht besonders zu sagen, aber Zählen der Anzahl von Operationen, die ich am Montag getan hat, Vergleich von zwei Menschen, das fühlt sich wie eine schöne Maßeinheit. 

So n minus 1 Schritte das erste Mal, aber was dann passiert danach? Was ist die eine auf den Kopf von einem Durchgang durch eine ansonsten unsortierten Liste? Was können Sie mir über das Element , die den ganzen Weg über da war? Ja? Das war die größte Element, oder? Nummer acht, obwohl sie hier begann, jedes Mal wenn ich verglichen sie gegen ein Nachbar, hielt sie sprudeln rechts Seite der Liste. Und in der Tat, das ist, wo der Algorithmus erhält seinen Namen. 

Nun von dieser Logik, wie viele Vergleiche muss ich auf dem zweiten Mal machen Ich mache diesen Pass von links nach rechts? n minus 2, oder? Es wäre nur verschwenden meine Zeit, wenn ich halten den Vergleich acht gegen jemanden sonst, weil wir bereits wissen, sie war an der richtigen Stelle. Also das ist ein bisschen ein Optimierung, so dass der nächste Pass sein wird, plus n minus zwei Schritten, wobei n die Anzahl der Personen. Jetzt können Sie Art von extrapolieren, auch wenn Sie nicht gerade ein Computerwissenschaftler, wie das endet. Am Ende dieses Algorithmus, vermutlich Sie nur einen Vergleich links haben. Sie müssen die Art der Fixierung Anfang der Liste bei zwei und eins sind in Ordnung und sollte eins und zwei ist, so dass diese Talsohle bei plus 1 abschließenden Vergleich. 

Jetzt ist der Punkt, Punkt, Punkt Art von Wellen, es ist Hände auf einige der Details saftiger, aber lasst uns einfach weitermachen und zu vereinfachen. Wenn Sie von hohen erinnern Schule, ehrlich gesagt, eine Menge von euch hatte Mathe Bücher, die hatte ein wenig Spickzettel an der Frontabdeckung oder der Rückseite, die Sie zeigte Welche Serie Summen wie dies letztlich bis zu hinzugefügt. Im allgemeinen Fall, wenn Sie eine Variable wie n, und zwar diese, wenn man sich sah Ihre alten Schule Mathebuch, Sie, dass dieser tatsächlich sehen würde fügt bis zu dieser Summe hier, n mal n minus 1 Alle durch 2 geteilt. So jetzt lassen Sie mich nur vor, dies wahr ist, so auf einen Sprung des Glaubens, das ist, was ist das Fazit bis zu, und wir konnten beweisen, dass in einem allgemeinen Fall. Aber jetzt wollen wir erweitern dies. Lassen Sie uns also multiplizieren dies aus, so ist das n quadriert, minus n, die alle durch 2 geteilt. Das ist wirklich n quadriert, dividiert durch 2 minus n als 2, so, das ist alles schön und interessant. Aber was passiert, wenn wir Plug-In einen Wert? Angenommen, ich hatte nicht acht Menschen, aber sagen, eine Million. Und eine Million, nur weil es ist eine ziemlich große Zahl, wir stecken, die in und sehen was passiert. Also, wenn ich eine Million Plug in dieser Formel Ich werde zu einer Million quadriert, dividiert durch 2 minus ein Millionen, geteilt durch 2 ist. Nun, was das ist, werde gleich? So 500 Milliarden, minus 500.000. Und wenn ich tatsächlich tun dass Mathematik aus, dass Mittel dass die Sortierung eine Million Menschen mit dem Bubble-Sort könnte mir nehmen 499999500000 Schritte oder Vergleiche am Ende, wir sind nur zu extrapolieren. 

Das fühlt sich ziemlich langsam, aber ehrlich gesagt Messen von einem bestimmten Eingang wie dieser, ist gar nicht so aufschlussreich. Aber in der Tat darauf hin, dass es sich als n wird größer und größer, diesen Algorithmus Art fühlt sich schlechter und schlimmer noch, oder Sie wirklich starten, um den Schmerz fühlen, dass Potenzierung, quadriert, dass n, das summiert sich ziemlich schnell. Und dieses Detail ist nicht verloren auf Menschen in der Tat vor einigen Jahren ein gewisser Senator, war Wahlkampf, setzte sich für ein Interview mit Googles Eric Schmidt, CEO an der Zeit, und wurde mit einer Frage herausgefordert ähnlich wie wir heute erkunden. Lassen Sie uns einen Blick. 

[VIDEO PLAYBACK] 

-Senator, Hier sind Sie Bei Google, und Ich mag um der Präsidentschaft denken als Job-Interview. Jetzt ist es schwer zu bekommen ein Job als Präsident, und Sie durch die Strapazen gehen jetzt sind. Es ist auch schwer, einen Job zu Google zu bekommen. Wir haben Fragen, und wir Fragen Sie unsere Kandidaten Fragen, und dieses ist von Larry Schwimmer. What-- euch denken, ich bin Scherz, es ist hier richtig. Was ist die effizienteste Art, sortieren eine Million 32-Bit-Ganzzahlen? 

-Well-- 

-Ich Sorry, maybe-- 

Nein, nein, nein. Ich denke, die Bubble-Sort wäre der falsche Weg zu gehen. 

-Komm, Der ihm das gesagt? Ich sah nicht, Computer Wissenschaft in den Hintergrund. 

-We've Haben unsere Spione dort. 

-OK, Fragen wir eine andere Interview-Frage. 

[END VIDEO PLAYBACK] 

SPRECHER: So reden konkrete Zahlen aber, wird nicht alles sein, was nützlich ist. Es ist nicht eine Lektion fürs Leben, dass Blase Art, da eine Million Eingänge, vielleicht nehmen so viele wie 500 Milliarden Schritten. Man kann nicht wirklich verallgemeinern auch effektiv aus, dass und gute Design-Entscheidungen wenn die Programme schreiben. Also konzentrieren wir uns aber auf, wie wir könnten dieses Ergebnis zu vereinfachen. 

Also ich habe hier in gelb hervorgehoben das Ergebnis der n Quadrat dividiert durch 2, so eine Million Quadrat geteilt durch 2, und Ich habe hervorgehoben welche die ultimative Antwort war wenn wir subtrahiert aus n durch 2 geteilt. Und die Behauptung, ich werde jetzt zu machen ist, wer zum Teufel kümmert es, wenn Sie subtrahieren aus ein wenig alt n mehr als 2, wenn die erste Teil dieser Formel ist so viel größer? Es dominiert die anderen Ausdruck, n Quadrat dividiert durch 2 ist so viel größer, deutlich, wie n groß wird wie eine Million, das ist es wirklich ein großer Unterschied zu das Ende des Tages zwischen 500 Milliarden und 499.999.500.000? Nicht wirklich. Und so, was wir zu gehen tun, wie Informatiker ist diese Terme niedrigerer Ordnung zu ignorieren und nehmen und so etwas wirklich nur zu vereinfachen, um die Begriff, das geht an die Materie. Die größeren unsere Datensätze zu erhalten, desto größer unsere Datenbanken zu erhalten, die mehr Web-Seiten wir müssen, die mehr suchen Freunde haben Sie auf Facebook. 

Als n größer wird, sind wir wirklich gehen, um über die größte Sorgfalt Term in einer solchen Analyse unsere Algorithmen Leistung. Und ich werde sagen, wissen Sie was, Bubble-Sort ist in der Größenordnung von Big O, in der Größenordnung von n quadriert. Es ist nicht genau n Quadrat, wie wir gesehen haben, aber wer kümmert sich wirklich über diese kleineren Begriffe, und ehrlich gesagt, die wirklich kümmert es, wenn wir durch 2 teilen? Das ist nur ein konstanter Faktor. Und ist 500 Milliarden gegenüber 250 Milliarden wirklich so große Sache? Ich konnte es einfach ein Jahr warten, lass meinen Laptop wörtlich bekommen doppelt so schnell in Hardware, und diese Art von Unterschied nur geht weg natürlich über die Zeit. 

Was uns wichtig ist der Ausdruck, der Teil des Ausdrucks, die gehen zu variieren als unseren Input wird größer und größer. Und zwar in der realen Welt, das ist, was immer geschieht, ist die Eingänge, um unsere Probleme und Algorithmen werden immer größer. So groß, O wird sich die Schreibweise zu sein, die asymptotische Notation, dass wir nur Verwendung als Computerwissenschaftler, um zu beschreiben die Leistung oder die Laufzeit, eines Algorithmus. So dass wir Algorithmen vergleichen auf verschiedenen Computern geschrieben von verschiedenen Personen, unter Verwendung einige grundlegend ähnliche metrische wie die Anzahl der Vergleiche sind Sie machen, oder vielleicht die Anzahl der Swaps du machst. 

Was wir nicht gehen Zahl ist die Menge an Zeit, daß am Taktläuft an der Wand der Regel. Was wir nicht zu sorgen , ist, wie viel Speicher Sie sind heute bei dest, obwohl das eine andere Ressource, die wir vielleicht zu messen. Wir werden versuchen, unsere Analysen stützen nur auf die Grundfunktionen, die, die, ehrlich gesagt, dass Sie visuell sehen kann. Also mit so etwas wie Big O von n quadriert, ich behaupten, dass O von n im Quadrat eine obere auf der sogenannten gebundenen Laufzeit von Bubble-Sort. Mit anderen Worten, wenn man wollte behaupten, dass es Diese obere Grenze, wie viele Schritte ein Algorithmus aussehen könnte, es wird in der großen O von n sein in diesem Fall wird quadriert, eine obere Grenze. 

Was ist, wenn ich stattdessen die ändern Geschichte, nicht über Blasen Art sein, aber über diese obere Schranke. Können Sie eines Algorithmus denken dass wir an sah schon dessen obere Grenze maximalen Maß der Zeit oder Operationen, würde gesagt, begrenzt werden durch N, eine lineare Funktion, nicht eine quadratische eine, die gebogene ist? Was ist ein Algorithmus, der findet immer nicht mehr als wie n Schritten, oder 2n Schritten oder 3n Schritte? Ja? 

ZIELGRUPPE: Das Finden der größte Zahl in einer Liste? 

SPRECHER: Perfect, finden die größte Zahl in einer Liste. Wenn ich eine Liste der genannten Menschen, zum Beispiel jeder, der im Besitz einer Reihe, Was ist die maximale Anzahl von Schritten sollte es mir zu nehmen, eine ziemlich intelligente Person, , die größte Person in dieser Liste? n, oder? Da im schlimmsten Fall, bei dem könnte der größte Wert sein? Recht, den ganzen Weg am Ende. So im schlimmsten Fall Obergrenze, könnte ich haben, den ganzen Weg zu gehen hier und werden wie, oh, hier ist Nummer acht, oder was auch immer das Wert ist. Nun wäre es einfach nur dumm sein wenn ich in Gang gehalten, oder? Auf der Suche nach mehr und mehr Elemente wenn der letzte von ihnen ist dort? So sicher ist n eine obere Schranke. Ich brauche nicht zu nehmen mehr Stufen als die. 

So was, wenn ich stattdessen vorgeschlagen, dass Es gibt Algorithmen, die in dieser Welt, die haben eine Laufzeit, die ist von Big O log n begrenzt, melden Sie n? Wo haben wir gesehen das? Ja? 

ZIELGRUPPE: Im Telefonbuch Problem? SPRECHER: Wie der Telefonbuch Problem. Was war das Maß dafür, wie viel Zeit oder wie viele Tränen es Hat mich jemand wie zu finden Mike Smith im Telefonbuch? Wir behauptete, es sei log n, und auch wenn es nicht vertraut oder es ist ein wenig verschwommen, was ein Logarithmus oder Exponent war, nur daran erinnern, dass log n bezieht sich allgemein auf das Verfahren, in diesem Fall der Unterteilung etwas in der Hälfte wieder, und wieder, und wieder und wieder, so daß er wird immer kleiner, wie Sie das tun. 

So melden Sie sich von n bezieht sich, klar, zum Telefonbuch beispielsweise, binäre Suche in der Theorie, wenn wir hatte die virtuellen Türen auf dem Brett, oder wenn Sean war Suche nach etwas. Wenn er binäre Suche benutzt hatte, log n wäre, wie viel die Obergrenze Zeit, die dauert. Aber diese Algorithmen, die in lief n ausgegangen, welche Schlüsseldetailprotokoll? Dass die Liste sortiert wurde, richtig? Ihr Algorithmus ist falsch, wenn Ihre Eingabe ist nicht sortiert, und doch, die Sie verwenden so etwas wie binäre Suche weil Sie vielleicht springen direkt über dem Element ohne zu merken, es ist in der Tat gibt. 

Nun, was könnte dies bedeuten, groß O von einem? Dies bedeutet nicht, dass Ihr Algorithmus nimmt einen und nur einen Schritt, es bedeutet nur, es dauert ein konstante Anzahl von Schritten. Vielleicht ist es ein, vielleicht ist es 10, vielleicht ist es 1000, aber es ist unabhängig von das Ausmaß des Problems. Egal wie groß n ist, eine konstante Zeit-Algorithmus nimmt immer die gleiche Anzahl von Schritten. Also, was könnte ein Algorithmus sein wir über oder einfach nur geredet haben intuitiv, dass zu Ihnen kommt, dass läuft immer in sogenannten konstanten Zeit? Ja? 

ZIELGRUPPE: In zwei Zahlen. SPRECHER: In zwei Zahlen, 2 plus 2 gleich 4, fertig. So dass funktionieren könnte, was sonst? Wie wäre es mit mehr realen Welt, ja? 

ZIELGRUPPE: Das Finden der erste, was in einer Liste. SPRECHER: Das Finden der ersten Element in einer Liste, sicher. Wir haben tatsächlich gesprochen etwa bereits Arrays Wie sehen Sie das bekommen das erste Element in einem Array, unabhängig davon, wie lange der Array im C-Code? Sie ebenso wie die Konsole verwenden Null-Notation, bam, du bist da. Und in der Tat Arrays, nebenbei, Unterstützung etwas allgemein bekannt wahlfreiem Zugriff, Random Access Gedächtnis, weil man buchstäblich springen, um an einem Ort. Wir können diese noch einfacher machen können wir zu Woche Null Rücklauf als wir Scratch. Wie viel Zeit haben Sie für das nehmen sagen Block im Scratch ausführen? Nur konstante Zeit, oder? Sagen Sie etwas, sagen etwas, ist es egal, wie groß Kratzer Welt ist, ist es immer würde die gleiche Menge an Zeit, einfach zu sagen, so etwas. 

Also das ist, konstante Zeit, aber was ist die Kehrseite? Ob das obere Grenzen, was ist, wenn wir wollen, um die unteren Grenzen beschreiben unserer Algorithmen Laufzeit? Fast ein best case möglicherweise, wenn man will, obwohl diese Begriffe könnten am besten anwenden Fällen schlimmsten Fällen durchschnittlich Fällen mehr in der Regel, aber lasst uns einfach konzentrieren auf Untergrenzen im Allgemeinen. Was ist ein Algorithmus, der hat eine von n Stufen tiefer gebunden, oder 2n Schritten oder 3n Schritte? Einen Faktor von n Schritten, das ist seine untere Grenze. Ja? 

ZIELGRUPPE: Bubble Sort? 

SPRECHER: Bubble Sort nimmt Sie minimal n Schritten, warum? Warum ist das so? Warum sollte das Start zu Ihnen kommen intuitiv, auch wenn es nicht gerade noch nicht? Ja? 

ZIELGRUPPE: [unverständlich]. SPRECHER: Genau. In der bestmöglichen Szenario Blasensortierung, und eine Menge von Algorithmen, wenn ich Hand, die Sie acht Personen die bereits sortiert sind, es wäre töricht für Sie, der Algorithmus, hin und her gehen mehr als einmal, oder? Denn sobald Sie gehen einmal durch die Liste, Sie sollten erkennen, oh, ich habe keine Swaps, wird diese Liste sortiert, Ausfahrt. Aber das wird dir n Schritte zu unternehmen. 

Und umgekehrt, was ist ein weiterer Art des Denkens über sie? Bubble-Sort ist eine Omega, sozusagen von N, denn wenn man sich freuen weniger als n Elemente, was ist die Grundfrage gibt? Sie wissen nicht, ob es sortiert, rechts. Wir Menschen Macht Blick auf acht Menschen und wie sein, oh, es sortiert, das hat mich n Schritte nicht zu nehmen, aber es tat. Ihre Augen, auch wenn Sie Art von haben eine große Sichtfeld, Sie schaute auf acht Elemente, Sie schaute auf acht Personen, das ist acht Schritte effektiv. Und nur, wenn ich durch das ganze Liste zu tun ich merke, ja, sortiert. Wenn ich halbwegs denken aufhören, alle richtig, es ist ziemlich so weit sortiert, Wie stehen die Chancen es ist nicht sortiert? Dass Algorithmen, nicht korrekt zu sein. Vielleicht schneller, aber nicht korrekt. 

So, jetzt haben wir einen Weg der Beschreibung eines Untergrenzen, und was ist mit konstanter Zeit? Was ist ein Algorithmus, der eine niedrigere hat auf seiner Laufzeit von einem Satz? 1 Schritt, 2 Schritte, 10 Schritte, aber konstant, unabhängig von n ist, Die Größe des Eingangs? Ja, auf der Rückseite. 

ZIELGRUPPE: Printf? SPRECHER: Was ist das? ZIELGRUPPE: Printf? SPRECHER: Printf. OK, sicher. So dauert es eine feste Anzahl von Schritten. Und ich sollte jetzt, dass now-- wir über C-Code im Gespräch und nicht kratzen, etwas, wie gesagt, mit printf, wir sollten vorsichtig sein, um zu bekommen. Da printf dauert Eingang, es ist eine Zeichenfolge, Saiten und technisch haben Länge. Also, wenn wir jetzt abholen wollen auf Sie, wenn Sie nichts dagegen haben, technisch könnte man argumentieren, dass printf dauert eine variable Länge Input, und sicher, es könnte länger dauern Zeit, um einen String so lange drucken, als dieser lang. 

So was, wenn wir nur die betrachten Sortieren und Suchen Beispiele? Was ist mit Mike Smith im Telefon Buch oder binäre Suche allgemein? Im besten Fall könnte was passieren? Ich öffne das Telefonbuch und, bam, es gibt Mike Smith Nummer. Ich kann ihn sofort anrufen. 

Machte einen Schritt, vielleicht zwei Schritte, aber eine konstante Anzahl von Schritten, wenn ich hatte Glück. Und ehrlich gesagt, haben wir gesehen, auf Ihre Klassenkameradin Montag ganz schön Glück zweimal in Folge. Und das war in der Tat konstant Mal in ein Untergrenzen auf dem Algorithmus in Frage für die Suche die Zahl 50 hinter den geschlossen Türen. 

Jetzt, als zur Seite, wenn Sie feststellen, dass sowohl große O, die obere Grenze, und Omega, der Untergrenze, sind ein in der gleichen, dass ist die gleiche Formel, Klammern, können Sie auch sagen, nur um Phantasie zu sein, dass etwas in Theta n oder Theta von einem anderen Wert. Das bedeutet nur, wenn große O und O sind die gleichen. Was ist nun mit Auswahl sortieren? Lassen Sie uns diese neue Wortschatz. Bei der Auswahl sortieren, was waren wir wieder zu tun, und wieder, und wieder? Ich wurde durch hin und her die Liste, auf der Suche nach wem? Die kleinste Zahl. 

Also, wie viele Schritte, wie viele Vergleiche habe ich müssen, um herauszufinden, machen die das kleinste Element in der Liste war? n minus 1, oder? Denn wenn ich nur mit der, die ich bin starten gegeben und ich beginne ihn oder sie zu vergleichen, dann ihn oder sie, er oder sie, ihn oder sie, ich kann nur paaren Elemente zusammen n minus 1 mal. So ähnlich Auswahl Art nimmt n minus 1 Schritte zum ersten Mal. 

Wie viele Schritte braucht es, mich zu finden Sie das zweitkleinste Element? n minus 2, denn ich bin als dumm wenn ich auch in Zukunft auf die gleichen Leute wieder, wenn ich ihn schon ausgewählt oder sie und legte sie in ihre Schranken. Und den dritten Schritt, n minus 3, dann n minus 4. Wir haben dieses Muster gesehen vor, und zwar Auswahl Art ähnlich eine obere Schranke n im Quadrat, wenn wir tun, bis diese Summe. Was ist ihre untere Grenze, die Auswahl sortieren? Minimal, wie viel Zeit Muss Auswahl Art zu nehmen, wie wir es am Montag festgelegt? Schlagen zwei Möglichkeiten. Vielleicht ist es n, wie zuvor. Vielleicht ist es n quadriert, wie es ist jetzt als die obere Grenze. 

ZIELGRUPPE: n quadriert. SPRECHER: n quadriert. Warum? 

ZIELGRUPPE: Weil Sie zu definieren [unverständlich]. 

SPRECHER: Genau. Zumindest, als ich festgelegten Auswahl Art es war ziemlich naiv, weiterzumachen, finden Sie das kleinste Element. Gehen wieder finden das kleinste Element. Gehen wieder finden das kleinste Element. Es gibt keine Art von Optimierung gibt, die vielleicht lassen Sie mich nach Abbruch nur n oder so Schritten. Also ja, die Auswahl Sortieren, Omega von n im Quadrat. 

Was ist mit Insertion Sort, wo ich wer ich war gegeben, und ihn dann fallen ließ ich oder sie in der richtigen Stelle? Dann ging ich in die zweite Person, plumpste ihm oder ihr an der richtigen Stelle. Dann wird die nächste Person, plumpste ihn oder sie in der richtigen Stelle. Beachten Sie, dass dies sehr Linear sozusagen. Ich bin eine gerade Linie, ich bin nicht hin und her gehen, Ich habe noch nie im Rückblick wirklich, aber was passiert, wenn ich ihn einfügen oder sie in den Anfang die Liste, wie wir am Montag getan hat? Was ist los? Ja? ZIELGRUPPE: [unverständlich]. SPRECHER: Ja, das war der Haken, oder? Sie könnten von erinnern Ihre Klassenkameraden, wenn sie machten jede Bewegung mit ihre Füße, das war eine Operation. Also, wenn es hier drei Personen und die neue Person gehörte Weise dort, auf einer langen Etappe wie diese, sicher, er oder sie nur bis zum Ende gehen könnte. Aber wenn wir über ein Denken Computer und ein Feld von Speicher, Diese Leute werden shuffle über zu haben, um Platz für diese Person zu machen. Und so, dass n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings ist nur irgendwie geschieht hinter mir, nicht vor mir wie vorher, in einem gewissen Sinn. Nun als zur Seite, und als Sie können Online-gesehen haben wenn Sie stochern zu starten Art, es gibt so viele verschiedene, gibt, von denen einige besser als andere. Tatsächlich ist eine bogosort das ist eine Art von Spaß zu schauen. Bogosort nimmt eine Reihe von Zahlen oder sagen ein Deck von Karten, zufällig mischt sie, und prüft, ob sie sortiert. Und wenn nicht, tut es wieder. Und wenn nicht, tut es wieder. Wenn nicht, tut es wieder. Unglaublich dumm. 

Und in der Tat, wenn Sie lesen, wie der Wikipedia-Artikel, sein Spitzname ist dumm Sorte. Es wird schließlich arbeiten, hoffentlich genügend Zeit, aber Zeit könnte einige Zeit dauern. Also, wenn ich könnte, lassen Sie uns die Dinge Geschwindigkeit aus Mary Beth Beispiel zuvor, indem er ein paar weitere Elemente, aber zwei weitere Prozessoren. Zwei Menschen, wenn Sie hätte nichts dagegen, mich Beitritt. Wie etwa 1 hier, und Lassen Sie uns go-- niemanden dort? Niemand da? Ok. Sie mit der schwarzen T-Shirt, ja, kommen auf Sie. Alles in Ordnung, was ist Ihr Name? 

ZIELGRUPPE: Peter. 

SPRECHER: Was ist das? 

ZIELGRUPPE: Peter. SPRECHER: Peter, David, schön, Sie zu treffen. Alles in Ordnung, wir haben Peter hier, wenn Sie wollen hier auf den Tisch kommen. Und was ist Ihr Name? 

ZIELGRUPPE: Elena. SPRECHER: Elena. OK, schön, Sie zu treffen. Elena treffen Peter. Peter, Elena. Und wir brauchen Andrew bis auch hier, bitte. Und Ihre Herausforderung wird zu sein, ein Kartenspiel zu sortieren. Und wenn nicht vertraut, Liege Karten letztlich sollte ein wenig so etwas wie sortiert werden dieses, wo wir die Clubs zu tun, dann die Spaten, dann die Herzen und Diamanten, von ACE als eine, den ganzen Weg bis zum König. 

Die Karten werde ich Ihnen gehen, um 52 in Menge. Wir gehen mit ähnlich Zeit, die Sie, in nur einem Augenblick. Wir werden Andrew werfen auf dem Bildschirm hier, so zu beobachten, wie Sie dies tun. Und so, daß alles umso sichtbarer, das sind die Karten, die ich auf Amazon bekam. So sind sie bereits nach dem Zufallsprinzip sortiert, und wir werden Ihnen Zeit. Und wir sind zu gehen keep it real diese Zeit, so werden wir versuchen, Sie unter Druck weil sonst diese erhalten mühsam schnell. Wenn Sie fortfahren könnte zu sortieren 52 Elemente miteinander über einige Mittel, jetzt. 

Und wieder, wie wir sehen diese Jungs tun, was am Ende wird sich eine offensichtliche produzieren Ergebnis, denken Sie wirklich wie sie jeder tut es, wie Sie es beschreiben. Da wiederum sind alle Prozesse, Algorithmen dass wir für so einen Menschen gewährt. Aber wahrscheinlich lange gehabt haben Intuition, lange bevor Sie selbst dachte über die Einnahme ein Informatik Klasse, die Sie könnte die Intuition mit gehabt haben was zu Problemen wie diese zu lösen. Aber sobald Sie erkennen, Die Muster und beginnen um die Schritte, mit denen formalisieren Sie diese Probleme zu lösen, Sie werden feststellen, dass Sie viel zu lösen interessanter und viel komplexer Probleme schnell. So jemand aus dem Publikum, was ist mindestens ein Element des Algorithmus dass sie mit hier sind? 

ZIELGRUPPE: [unverständlich] SPRECHER: Was ist das? ZIELGRUPPE: Mit dem Anzug. SPRECHER: Mit dem Anzug. Also zuerst sie Clustering werden alle Diamanten zusammen es scheint, alle der Herzen zusammen wie es scheint, und so weiter, ohne Respekt für die Zahlen auf den Karten. Und jetzt erscheinen sie, zum Beispiel, von Nummer werden sortiert sie. Sehr gut. 

Alles klar, so was ist zu gehen der letzte Schritt sein, dann hier? Einmal haben wir vier sortierten Anzüge, was wollen wir zu den vier Pfählen tun müssen um eines zu erreichen sortiert Deck, ganz einfach? Also müssen wir sie wieder zusammenzuführen. 

So gibt es eine interessante Idee, die wieder, wage zu behaupten, ist sehr intuitiv, auch wenn Sie vielleicht nie geschlagen haben diese Art von Etikett auf sie. Dieser Grundgedanke des Teilens das Problem nicht in der Hälfte dieser Zeit, aber zumindest in vier Teile. Lösung ziemlich grundsätzlich identisch Probleme isoliert von einander, und dann die Zusammenführung der Ergebnisse. Und, ausgezeichnet, getan. Alles klar, ein großer runder Applaus, wenn wir könnten. 

[Applaus] 

SPRECHER: Ich habe keine Ahnung, was Sie zu tun mit diesen, aber hier gehen Sie. Vielen Dank. Also mal sehen, nur zwei Minuten und acht Sekunden Wenn Sie möchten, dass Ihre Freunde herauszufordern. Was ist dann zu gehen Seien Sie ein Mitnehmen von diesem dass wir in der Regel mehr nutzen können? Nun, denken Sie zurück an Diese Reihe von Zahlen, und denke, jetzt zurück auf einige der Pseudocode, die wir in der Vergangenheit geschrieben, und dies war der Pseudocode für Lösung des Telefonbuch Problem. Wobei ich in Pseudocode aufgezählt eine methodisch zu beschreiben, wie ich eine sehr intuitive menschliche Algorithmus der Unterteilung der Telefon Buch in zwei Hälften, wiederholen, wiederholen, wiederholen, bis ich jemanden wie Mike Smith, wenn er tatsächlich im Telefonbuch. 

Aber ich Art von verwendet, was ich nennen ein sehr iterativen Ansatz hier insbesondere Ankündigung Linie 8 und Linie 11. Das sind Hinweise auf eine iterative Ansatz, eine Looping-Ansatz, denn das ist genau das Verhalten, das sie auslösen. Diese Linien beide sagen, gehen Sie zu Linie drei, und Sie können Art denken, dass in Ihrem geistigen Auge als eine Schleife. Es sagt dir, zurück bis zum Schritt drei und wiederholen, wieder und wieder, und wieder. 

Aber was, wenn wir eine Schlüsselidee nutzen hier, dass wir nicht das letzte Mal, und zu vereinfachen, und die Linie 8 Linie 11 und ihre Nachbarn als nur dies, in gelb. Es ist nicht grundsätzlich zu verkürzen Der Pseudocode sehr, aber es ist grundlegend verändern die Natur meiner Algorithmus. Was ich jetzt sage, in Schritt 7, in Schritt 10, ist es für Mike zu suchen in genau der gleichen Weise, aber nur in der linken Hälfte oder die rechte Hälfte. 

In anderen Worten, wenn Ich gehe von einem Schritt, abholen Telefonbuch, offen für Mitte von Telefonbuch, Blick auf Namen, wenn Smith ist unter Namen, rufen Mike, sonst wenn Smith ist früher im Buch Schritt sieben Suche nach Mike in der linken Hälfte des Buches. Aber diese Art von Gefühl, es ließ mich hängen, oder? In gelb, ist ein Unterricht, aber wie kann ich Suche nach Mike in der linken Hälfte des Telefonbuchs? Wo muss ich eine Algorithmus, mit dem ich kann für jemanden wie Mike Smith zu suchen? Nun, es ist starrte uns ins Gesicht. Ich kann buchstäblich mit dem exakt gleichen Programm effektiv gehen bis an die Spitze wieder und wieder Lauf die gleichen Codezeilen. 

Also auch wenn dies fühlen wie ein bisschen eine zyklische Definition wo Sie die Beantwortung jemand ist Frage einfach so zu fragen, die gleiche Frage wieder, wie, warum, warum, warum? Die Realität ist, weil wir hart codiert haben ein paar spezielle Linien, Schritt 4, was ein, wenn und Schritt 12 wird die ist tatsächlich ein weiterer Zweig, denn wir haben diese Notlösungen, Dieser Algorithmus wird beendet, wenn wir Mike zu finden, oder wenn wir es nicht tun. Aber in Schritt 7 und 10 jetzt haben wir was wir einen rekursiven Algorithmus nennen. Und Rekursion ist in der Tat eine mächtige Idee das ist ein wenig Geist Biegen auf den ersten, dass wir nun wie folgt anzuwenden. 

Mergesort wird die letzte Art sein, dass wir uns, zumindest in der Klasse formal. Und es grundlegend anders ist aus diesen letzten drei, und sicherlich letzten vier, wenn wir gehören bogosort. Hier ist der Pseudocode für Merge-Sort. Wenn am Eingang von n Elementen, so gegeben ein Array der Größe n ist, wenn n kleiner als 2 ist, zurück. Also warum habe ich, dass Vernunft prüfen Sie zuerst? Was ist die Implikation, wenn ich Hand, die Sie ein Feld, dessen Länge n kleiner als 2? Es ist bereits sortiert, offensichtlich, nicht wahr? Da die Liste entweder ein Element, das trivial ist geordnet, weil es das einzige, was es gibt. Oder ist es von der Größe Null, was bedeutet, gibt es nichts zu sortieren, so von der Natur sie sortiert. Es gibt einfach nichts falsch gibt. Also das ist unsere sogenannte Basisfall. 

Das ist im Geiste zu dem, was wir mit Mike tat. Wenn Mike im Telefonbuch, rufen Sie ihn. Wenn er nicht da ist, aufzugeben. Es ist eine so genannte Basisfall, um sicherzustellen, dass Dieser Algorithmus am Ende des Tages unter bestimmten Umständen zu stoppen. 

Aber hier ist der Sprung des Glaubens jetzt, sonst, sortieren Sie die linke Hälfte der Elemente, dann sortieren Sie die richtige die Hälfte der Elemente, und dann verschmelzen die sortierten Hälften. Und hier, wo es sich anfühlt wie wir ausklinken. Ich habe Sie aufgefordert, zu sortieren n Elemente, und ich bin sagen, OK, tun Sie es durch die Sortierung Die linke und die Sortierung der rechten Seite. Aber ich sage, eine andere Sache, und das ist das zentrale Thema scheint es in der Anschauung so weit, da ist dieser dritte Schritt der Zusammenführung. Welches, obwohl es scheint so dumm im Geist, wie einfach Dinge zusammenführen zusammen scheint für einen entscheidenden Schritt in Richtung der sein Zusammenbau von zwei Probleme, die wurden schließlich in zwei Hälften geteilt. 

So verschmelzen Art, lassen Sie uns das tun, wenn du Humor mich, mit einer weiteren Demonstration, gerade so, dass wir einige Zahlen zu arbeiten. Kann ich tauschen acht Stress Bälle für acht Personen? Alle Rechte, wie über Sie drei, vier Sie in diesem Abschnitt, fünf, sechs, und lassen Sie uns Sie 7, 8, kommen Sie auf. OK, ja OK. Minus 8, dort gehen wir, plus 1. Ausgezeichnet. Alle Rechte an kommen, lassen Sie uns schnell geben Ihnen Zahlen. Nummer zwei, Nummer drei, Nummer vier, Nummer fünf, sechs, sieben und acht. Ich habe acht richtig diese Zeit. 

OK, so gehen Sie vor, wenn Sie könnten, und Lassen Sie uns in der ursprünglichen Reihenfolge zu sortieren dass wir gestern die aussahen, wie diese, wenn Sie nichts dagegen haben. Und lass es uns tun vor dem Tisch. Alles in Ordnung, so verschmelzen Sorte. Dies ist, wo es geht um irgendwie interessant zu erhalten, weil ich zu sein scheinen mich geben so viel weniger Informationen heute. 

So verschmelzen Art zunächst am Eingang von n Elementen, und ist offensichtlich nicht kleiner als zwei ist, ist es acht, so habe ich etwas mehr Arbeit zu tun. So, jetzt haben wir mental als Klasse sind jetzt in der else-Zweig, was bedeutet, drei Schritte. Zuerst habe ich, um die Sortier linke Hälfte der Elemente. So, wie ich über das tun dies gehen? Nun, ich werde Art von hier geistig teilen die Liste, Sie nicht zu haben, körperlich zu bewegen, und ich bin gehen, sich nur auf das konzentrieren, linke Hälfte der Elemente hier. So, wie ich über die Sortierung gehen eine Liste jetzt von der Größe vier? Was ist mein Algorithmus? Zuerst habe ich überprüfen, ist n weniger als zwei, nein, so dass ich zu der else-Block gehen wieder. Sortieren linke Hälfte der Elemente. 

So, jetzt wieder, mental, und dies ist, wo Sie, eine Menge sammeln müssen, Geistesgeschichte, wenn man so will. Jetzt bin ich die Sortierung der linken Hälfte der linken Hälfte. Alles klar, so jetzt meine gleichen Merge rufe ich Sortieralgorithmus ist n weniger als zwei? Nein, es ist zwei, so dass ich zu sortieren die linke Hälfte, und die rechte Hälfte. Also hier gehen wir, sortieren Sie die linke Hälfte. Warum gehst du nicht einfach einen Schritt weiter. Wie heißen Sie? 

ZIELGRUPPE: Darren. 

SPRECHER: Dan. Dan hat vorgetreten. 

ZIELGRUPPE: Darren. SPRECHER: Darren, fertig. Haben Sie Darren oder Dan sagen? 

ZIELGRUPPE: Darren. 

SPRECHER: Darren. OK, Darren hat trat nach vorne und er nun sortiert. Und das ist fast ein albern Anspruch, oder? Ich weiß nicht wirklich zu sein scheinen erreichen nichts, aber lassen Sie uns gehen. Nun lassen Sie mich die richtige Art Hälfte der Elemente. Wie heißen Sie? 

ZIELGRUPPE: Luke. 

SPRECHER: Luke. Komm, Schritt nach vorn. Getan, habe ich Luke sortiert. Die linke Hälfte ist nun sortiert und die rechte Hälfte ist nun sortiert, aber wieder, es gibt hier ein wichtiger Schritt. Was muss ich nächstes tun müssen? Verschmelzen die sortierten Hälften. Jetzt werden wir einfach nur jeder in dieser Art und Weise hin und her, weil ich irgendwie müssen einige Kratzer Raum. Es ist fast wie diese Jungs sind auf einem Tisch, und ich brauche etwas Platz sie bewegen sich auf. Also werde ich zu fusionieren Sie Kerle suchen an der linken Hälfte und der rechten Hälfte. Und die offensichtlich kommt zuerst, linke Hälfte oder rechte Hälfte? So rechte Hälfte, so lassen Sie uns nun über Luke hier in die ursprüngliche Position Darrens. Und jetzt, ihre linke Hälfte in fusionieren, Darren geht um genau dort zu bewegen. 

So fühlt sich an wie fast eine Blase Art-Effekt, aber meine Grundalgorithmus sehr dieses Mal anders. Aber jetzt ist, wo die Dinge ein wenig ärgerlich, weil Sie müssen geistig zurückspulen wo habe ich aufhören. Ich habe gerade fusionierte die sortierten Hälften, das heißt ich bin, wo in meinem Algorithmus? Ich muss die rechte Hälfte zu sortieren, oder? 

Wenn Sie zurückspulen, wörtlich auf dem Video, werden Sie sehen, dass wir das bekommen Punkt von Luke und Darren durch die Sortierung der linken Hälfte der linken Hälfte. Dann zusammengeführt, die wir sortierten Hälften, die bedeutet, dass der nächste Schritt ist die Art rechte Hälfte der linken Hälfte. Alles klar, also lassen Sie uns tun dies schneller. Alle Rechte, sechs, ich werde Anspruch Sie werden nun sortiert, kommen Sie nach vorne. Wie heißen Sie? 

ZIELGRUPPE: Adriano. 

SPRECHER: Adriano. Adriano ist nun sortiert. Und was ist Ihr Name? 

ZIELGRUPPE: Alex. 

SPRECHER: Alex ist nun sortiert. Linke Hälfte, rechte Hälfte, was ist der letzte Schritt? Zusammenführen. Ziemlich trivial, also bin ich werde in sechs zusammenzuführen, einen Schritt zurück, acht, einen Schritt zurück. Und jetzt merken, das ist eine sinnvolle Gerichte zum Mitnehmen, was jetzt wahr ist über die linke Hälfte der Liste, unabhängig davon, wie wir begonnen? Es wird sortiert. 

Jetzt ist es nicht sortiert Der große Plan der Dinge, aber es wird unabhängig sortiert von der anderen Hälfte. Nun, was ich Schritt auf, wenn ich halten Zurückspulen, wie die Geschichte begann? Jetzt muss ich die rechte Hälfte zu sortieren. So, jetzt zurück zu wir der Anfang der Geschichte, und lassen Sie uns dies schneller. Also werde ich, um die Sortier rechte Hälfte der gesamten Liste. Was ist der nächste Schritt? Sortieren Sie die linke Hälfte der rechten Hälfte. Sortieren Sie die linke Hälfte des linken Hälfte der rechten Hälfte. Und was ist Ihr Name? 

ZIELGRUPPE: Omar. 

SPRECHER: Omar Schritt vorwärts getan. Linke Hälfte wird sortiert. Und was ist Ihr Name? 

ZIELGRUPPE: Chris. 

SPRECHER: Chris, einen Schritt vorwärts, Sie sind jetzt sortiert. Was ist der entscheidende Schritt ist jetzt? Zusammenführen. Also man geht, um an Ort und Stelle zusammen hier, wenn Sie einen Schritt zurück machen, und drei zu gehen einen Schritt zurück, zu verschmelzen. So ist die linke Hälfte des rechte Hälfte ist nun sortiert. Ehrlich gesagt, fühlt sich dieser Algorithmus wie wir verschwenden Weise mehr Zeit als zuvor, aber wenn wir taten dies in Echtzeit, werden wir sehen, was die Imbissbuden sein wird. Jetzt bin ich hier, direkt Hälfte der rechten Hälfte, lassen Sie mich gehen Sie vor und sortieren die linke Hälfte. Schritt nach vorn, was ist Ihr Name? ZIELGRUPPE: Ramsey. SPRECHER: Ramsey ist nun sortiert. Wie heißen Sie? 

ZIELGRUPPE: Marina. 

SPRECHER: Marina wird nun als geordnet Nun, wenn Sie einen Schritt nach vorne machen. Schlüsselschritt ist hier nun zusammenführen, ich bin werde von meinen beiden Listen pflücken, links und rechts. Fünf wird sich zuerst kommt, und sieben als nächstes kommen. Und wieder, das ist gewollt. Die Tatsache, dass sie unter Schritte nach vorn und wieder zurück soll darstellen, dass wir nicht tun Sie diesen Algorithmus in Ort so leicht als Bubble-Sort und Selection Sort, und Insertion Sort, wo wir nur gehalten tauschen Menschen. Ich muss buchstäblich eine Art von Grund auf Papier, in dem , diese Leute setzen während ich die Zusammenführung, und dann kann ich sie wieder in Kraft gesetzt. Und das ist der Schlüssel, weil ich mit ein neue Ressource, Raum, nicht nur Zeit. 

OK, das ist erstaunlich. Linke Hälfte wird sortiert, rechte Hälfte ist sortiert, jetzt, dass die Schlüsselvereinigungsschritt. Wie werde ich diese zusammenführen? Also, wenn Sie folgen meiner links und rechts, Ich werde meine linke Hand darauf auf der linken Hälfte, meine rechte Hand auf der rechten Hälfte, und jetzt muss ich Schritt für Schritt entscheiden, wen sie in zusammenzuführen. Die offensichtlich kommt zuerst? Nummer eins. Also komm hier, hier ist unsere Notizblock. So, jetzt die Nummer eins, und Kündigungsfrist was ich mit meiner rechten Hand zu tun, Ich werde meiner rechten Hand eine Bewegung Schritt über zu Punkt Nummer drei, und jetzt habe ich zu machen die gleiche Entscheidung. Und tatsächlich stehen direkt im vor Luke hier, wenn Sie könnten, denn dies ist unsere Notizblock. Also, wer kommt als nächstes? Wir haben Luke mit Nummer zwei oder Chris mit Nummer drei. Offensichtlich Luke, die Anzahl zwei, so dass Sie hierher kommen. 

Aber meine linke Hand nun an gehen erhöht, um bei Darren verweisen, und hier ist der Schlüssel wegnehmen mit Verschmelzung, werde ich weiter machen, Selbstverständlich, wenn Sie so freundlich von der Logik. Aber meine Hände sind nie gehen, rückwärts zu gehen, das heißt ich bin immer nur zu bewegen links mit meiner Vereinigungsprozess, und das wird Schlüssel zu sein unsere Analyse in nur einem Augenblick. 

So, jetzt wollen wir beenden diese rasch. So kommt nächsten drei, dann vier nächstes kommt, und jetzt fünf als nächstes kommt, dann sechs, und sieben, und dann schließlich acht. Fühlt sich an wie der langsamste Algorithmus noch nicht, aber nicht, wenn wir tatsächlich führen Sie es auf die gleiche Art der Taktgeschwindigkeit, so zu sprechen, mit dem gleichen tickende Uhr wie zuvor. Warum? Nun, lassen Sie uns einen Blick auf das Endergebnis. 

Gehen wir zurück hier, lassen Sie mich ziehen Sie sich einen Demo-visuell von dem, was wir gerade getan. Zoomen Sie hier, auf diese Seite hier, erzählt Firefox dass wir in die Warteschlange möchte in dieser Box, lassen Sie uns sagen Blase Art, mit der wir sind jetzt gut vertraut, Auswahl Art, die eine andere ist recht einfach eine, und jetzt heute Mergesort, die Höhepunkt am Ende wird unser sein. Der Grund, es hat so viel mehr hier mit Menschen und mich verbal ist, offensichtlich, ich erkläre jeden Schritt. Aber wenn man einfach führen Sie diese, viel wie wir Bubble-Sort und Auswahl Art nicht nur optisch, Uhr wie viel effizienter Diese Hebelwirkung von Teilung und Eroberung können, wenn sie einem Datensatz, der angewendet werden nicht einmal Größe acht, aber noch viel, viel größer. Ich gebe Ihnen von Mergesort, Seiten Seite mit diesen anderen Algorithmen. Das wird schmerzhaft zu bekommen schnell, und das Ende ist nicht besonders klimatische, sie nur am Ende sortiert. Aber der Schlüssel ist, dass wegnehmen Schauen Sie, wie viel schneller Mergesort war, es sei denn, Sie denken, ich bin nur irgendwie durcheinander mit Ihnen. Wenn wir diese ein letztes Mal, Lassen Sie uns diese neu zu laden, gehen wir zurück und wählen Sie Bubble-Sort, und nur zum Spaß, wählen wir Insertion Art, nur für eine gute Maßnahme. Und dieses Mal wieder, lassen Sie uns wählen Sie Merge-Sort und lassen Sie uns tatsächlich ausgeführt werden diese nebeneinander. 

Und es ist nicht, in der Tat, ein Zufall. Was ich getan wirksam ist, ich habe unterteilt meine Eingabe in der Mitte, wieder, und wieder und wieder. Und es gibt nur so viele Male, können Sie teilen Sie Ihre Eingabe in zwei Hälften, links und rechts. Was ist die Formel, die wir sehen immer das beschreibt die Teilung in zwei Hälften wieder und wieder, und wieder, und wieder? 

ZIELGRUPPE: Melden n. 

SPRECHER: Melden n. Aber dann gibt es einen weiteren wichtigen Schritt, Dieser Algorithmus ist nicht log n Schritte. Wenn es nur log n Schritte, wir in der gleichen Problem wie vorher, wo wir nicht sicher, alles sortiert. Sie müssen minimal bei n Elementen suchen sicher sein, n Elemente sortiert, ansonsten ist es ein Sprung des Glaubens. 

Es ist also minimal log n Schritte, aber was ist mit diesem Schlüssel Verschmelzung Schritt wo ich meine linke Hälfte zusammengelegt und rechts Hälfte und ging über die Bühne? Wie viele Schritte ist, dass zu fusionieren? Es ist n, aber ich habe nicht nur verschmelzen die letzte Zeit. Auf jedem dieser verschachtelt Anrufe auf jeder dieser verschachtelten Zusammenführungen, habe ich noch sortiert. Ich fusionierte diese beiden Jungs, dann sind diese beiden Jungs, dann sind diese beiden Jungs und so weiter. 

Also habe ich Verschmelzung wieder und wieder. Wie oft? Also jedes Mal, ich teilte die Liste in der Hälfte, habe ich eine Zusammenführung. Teilen Sie die Liste in der Mitte, machen eine Zusammenführung. Also, wenn Division der Liste können Protokoll n-mal durchgeführt werden, und die Zusammenführung statt n letztlich Schritte, was man nun die obere sein auf der Lauf gebunden Zeit des Algorithmus? n log n. 

Und in der Tat ist das, was wir hier erreicht. So das Gefühl, das Sie sehen, wenn visuell diese drei Dinge laufen Seite an Seite ist n gegen n Quadrat gegen n log n quadriert. Die sich grundlegend werden wir sehen, nicht nur heute sondern auch in Zukunft, ist viel, viel schneller. Ein Applaus für diese Jungs, Ich werde sie mit Stress-Bälle belohnen. Lassen Sie uns heute hier zu vertagen, und Wir werden uns am Montag sehen.