[Musik spielt] DAVID MALAN: Alles klar. Alles klar, willkommen zurück. Also das ist Woche 4, der Anfang davon bereits. Und Sie werden sich erinnern, dass letzte Woche, haben wir codieren beiseite für nur ein wenig und wir kamen ins Gespräch ein wenig mehr High-Level, über Dinge wie Such-und Sortierfunktionen, die zwar etwas einfachen Ideen sind Vertreter einer Klasse von Problemen Sie werden beginnen, besonders lösen wie Sie anfangen, darüber nachzudenken Finale Projekte und interessante Lösungen, die Sie könnte zu Problemen der realen Welt haben. Jetzt bubble sort war eine der einfachsten solche Algorithmen, und es arbeitete, indem er diese kleinen Zahlen in einer Liste oder eines Arrays Art Blase ihren Weg bis an die Spitze, und die große Zahlen bewegen ihren Weg nach unten, um das Ende dieser Liste. Und daran erinnern, dass wir visualisieren Bubble-Sort ein wenig etwas wie dieses. Also lassen Sie mich gehen Sie vor und klicken Sie auf Start. Ich habe bubble sort vorausgewählt. Und wenn Sie sich erinnern, dass der größere blau Linien stellen große Zahlen, kleine blauen Linien stellen kleine Zahlen, wie wir gehen durch diese wieder und wieder und wieder, den Vergleich von zwei Stangen nebeneinander andere in rot, wir gehen an den Swap- größte und die kleinste, wenn sie sind nicht in Ordnung. So wird dies gehen und gehen und gehen auf, und du wirst sehen, dass die größere Elemente sind, die ihren Weg auf die rechts, und die kleineren Elemente die ihren Weg auf der linken Seite. Aber wir begannen zu quantifizieren die Effizienz, die Qualität dieses Algorithmus. Und wir sagten, dass im schlimmsten Fall hat dieser Algorithmus etwa, wie viele Schritte? So n Quadrat. Und was war n? ZUSCHAUER: Anzahl der Elemente. DAVID MALAN: So war das n Anzahl der Elemente. Und so werden wir dies oft zu tun. Jedes Mal, wenn wir wollen, um die Größe zu sprechen einer Störung oder der Größe eines oder dass der Betrag der Zeit, die zur Ausgabe produzieren, werden wir nur generalisierte whatever Der Eingang ist als n. Also zurück in Woche 0, Seiten die Zahl im Telefonbuch war n. Die Zahl der Studierenden im Zimmer war n. So auch hier, wir sind nach dass Muster. Jetzt n squared ist nicht besonders schnell, also versuchten wir es besser zu machen. Und so sahen wir uns an ein paar andere Algorithmen, unter denen Auswahl Art waren. So Auswahl Art war ein wenig anders. Es war fast einfacher, ich wage zu sagen, wobei ich begann zu Beginn des Liste unserer Freiwilligen und ich wieder und wieder und wieder ging durch die Liste, Herausreißen der kleinste Element zu einem Zeitpunkt und setzen ihn oder sie am Anfang der Liste. Aber auch dies, wenn wir begonnen zu denken, durch die Mathematik und größer Bild, dachte darüber nach, wie oft Ich war hin und her und wieder zurück und her, wobei wir im schlimmsten Fall, Auswahl Art war auch was? n straffte. Jetzt in der realen Welt, könnte es tatsächlich geringfügig schneller. Weil wieder, habe ich nicht zu halten Backtracking ich einmal sortiert hatte die kleinsten Elemente. Aber wenn wir darüber nachdenken, sehr große n, und wenn Sie irgendwie tun sich die Mathematik als Ich habe auf dem Brett, mit dem n squared minus etwas, alles andere neben dem n Quadrat, einmal n wird wirklich groß, nicht wirklich so viel aus. So wie Informatiker, wir sortieren ein Auge zudrücken, um den kleineren Faktoren und Fokus nur auf den Faktor in ein Ausdruck, der gehen, dass ist der größte Unterschied. Nun, schließlich haben wir uns bei insertion sort. Und das war im Geiste, aber anstatt zu gehen durch iterativ und Wählen Sie das kleinste Element ein zu einer Zeit, ich stattdessen nahm die Hand, dass ich behandelt wurde, und ich beschloss, alle Recht, du gehörst hier. Dann zog ich auf das nächste Element und beschlossen, dass er oder sie gehörte hier. Und dann zog ich weiter und weiter. Und ich könnte an, auf dem Weg, verschieben diese Jungs um Platz machen für sie. Das war also eine Art der geistigen Umkehr von Selection Sort, dass wir genannt insertion sort. Also diese Themen auftreten in der realen Welt. Gerade vor ein paar Jahren, wenn eine bestimmte Senator zum Präsidenten läuft, Eric Schmidt, die zum Zeitpunkt der CEO von Google, tatsächlich die Möglichkeit hatte um ihn zu interviewen. Und wir dachten, wir würden dieses YouTube teilen Clip für Sie hier, wenn wir drehen konnte das Volumen. [VIDEO PLAYBACK] -Nun, Senator, sind Sie hier bei Google, und Ich mag an der Präsidentschaft denken wie ein Vorstellungsgespräch. [Gelächter] -Jetzt ist es schwer zu bekommen ein Job als Präsident. Und du durchmachst die Strapazen jetzt. Es ist auch schwer, einen Job bei Google zu bekommen. Wir haben Fragen und wir bitten unsere Kandidaten Fragen. Und dieser ist von Larry Schwimmer. [Gelächter] -Ihr Jungs denken, ich bin verrückt? Es ist hier genau richtig. Was ist der effizienteste Weg, um sortieren eine Million zwei-Bit-Integer? [Gelächter] -Nun, äh - -Tut mir leid. Vielleicht sollten wir - -Nein, nein, nein, nein, nein. -Das ist nicht ein - OK. -Ich denke, die Art Blase würde sein der falsche Weg zu gehen. [Gelächter] [Jubel und Applaus] -Komm, der ihm sagte, dieses? OK. [END VIDEO PLAYBACK] DAVID MALAN: So dort haben Sie es. Also fingen wir an, diese läuft quantifizieren Zeiten, sozusagen, mit etwas genannt asymptotischen Notation, die ist nur mit Bezug auf unsere Art des Drehens ein Auge zudrücken, um diese kleineren Faktoren und nur Blick auf die Laufzeit, die Leistung der Algorithmen, als n wird wirklich groß über die Zeit. Und so stellten wir große O. und Big O vertreten etwas, dass wir dachten, der als Obergrenze. Und tatsächlich, Barry, können wir senken als das Mikrofon ein wenig? Wir dachten, dies ist eine obere Schranke. So groß O von n Quadrat bedeutet, dass in schlimmsten Fall etwas Auswahl sortieren würde n squared Schritte. Oder so etwas wie Insertion Sort würde n squared Schritte. Nun zu etwas wie Insertion Art, was war der schlimmste Fall? Da ein Array ist, ist, was das Schlimmste mögliches Szenario, dass Sie vielleicht finden sich konfrontiert mit? Es ist völlig nach hinten, nicht wahr? Denn wenn es ganz nach hinten, Sie haben eine ganze Menge Arbeit zu tun. Denn wenn du ganz nach hinten, Sie gehen, um die zu finden größte Element ist hier, obwohl es gehört dort unten. So wirst du sagen, alles in Ordnung, bei dieser Moment in der Zeit, du gehörst hier so dass Sie in Ruhe lassen. Dann merkt man, oh, verdammt, ich muss verschieben Sie diese etwas kleinere Element links von Ihnen. Dann muss ich das wieder tun und immer wieder. Und wenn ich hin und her ging, Sie würde irgendwie das Gefühl, die Leistung der dass Algorithmus, weil ständig bin ich schlurfenden alle anderen in der Array, um Platz für sie zu machen. Also das ist der schlimmste Fall. Im Gegensatz dazu - und dies war ein Cliffhanger letzten Mal - wir sagten, dass insertion sort war ein Omega von was? Was ist das Best-Case-Lauf Zeitpunkt der Einführung Art? Also es ist eigentlich n. Das war der Rohling, dass wir links auf dem Brett letzten Zeit. Und es ist der Omega n denn warum? Nun, in den besten Fall, was ist Insertion Sort gehen zu übergeben? Nun, eine Liste, die vollständig geordnet ist Bereits minimale Arbeit zu tun. Aber was ist ordentlich über Insertion Sort ist, weil es hier startet und entscheidet, oh, du bist die Nummer ein, du gehörst hier. Oh, was für ein Glück. Du bist die Nummer zwei. Sie gehören hierher. Nummer drei, noch besser, Sie gehören hierher. Sobald es an das Ende der Liste pro Insertion Sort ist Pseudocode dass wir durch verbal letzten Mal, hat es getan. Aber Auswahl Art dagegen gehalten zu tun, was? In Gang gehalten durch die Liste wieder und wieder und wieder. Da der Schlüssel Einblick gab es nur sobald Sie sah den ganzen Weg bis die Ende der Liste können Sie sicher sein, dass das Element, das Sie ausgewählt war Tat das derzeit kleinste Element. Also diese unterschiedlichen mentalen Modelle Ende up was einige sehr realen Welt Unterschiede für uns, sowie diese theoretischen asymptotischen Unterschiede. Also nur zur Erinnerung, dann big O von n Quadrat, haben wir ein paar solcher gesehen Algorithmen so weit. Big O von n? Was ist ein Algorithmus, der konnte gesagt werden, um große O von n sein? Im schlimmsten Fall kommt es eine lineare Reihe von Schritten. OK, lineare Suche. Und im schlimmsten Fall, wo ist die Element Sie bei der Suche Anwenden einer linearen Suche? OK, im schlimmsten Fall, es ist gar nicht da. Oder in der zweiten schlimmsten Fall ist es ganz am Ende, das ist plus oder minus ein einstufiges Unterschied. So dass am Ende des Tages, können wir sagen, es ist linear. Big O von n würde lineare Suche zu sein, denn im schlimmsten Fall die Element ist gar nicht da, oder es ist ganz am Ende. Nun, groß O von log n. Wir haben nicht im Detail reden , aber wir haben dies gesehen. Was läuft im sogenannten logarithmischen Zeit, im schlimmsten Fall? Ja, so binäre Suche. Und binäre Suche im schlimmsten Fall vielleicht das Element irgendwo in haben der Mitte oder irgendwo innerhalb des Arrays. Aber Sie finden es nur, wenn Sie teilen Sie die Liste in der Hälfte, in Hälfte, in der Mitte, in zwei Hälften. Und dann voila, es ist da. Oder auch, worst case, es ist gar nicht da. Aber Sie wissen nicht, dass es nicht da ist bis Sie irgendwie erreichen, dass im vergangenen untersten Elemente durch Halbierung und halbieren und halbieren. Big O von 1. So konnten wir große O 2, O 3 groß. Immer, wenn Sie wollen einfach nur eine konstante Anzahl, wir einfach nur vereinfachen sortieren so groß, dass O von 1. Obwohl, wenn realistisch, dauert es 2 oder sogar 100 Schritte, wenn es eine konstante Anzahl von Schritten, wir nur sagen big O von 1. Was ist ein Algorithmus, der ist in großen O von 1? ZUSCHAUER: Finden Sie die Länge einer Variablen. DAVID MALAN: Suche nach dem Länge einer Variable? ZUSCHAUER: Nein, die Länge wenn es bereits sortiert. DAVID MALAN: Good. OK, so finden die Länge von etwas wenn die Länge dieser etwas, wie ein Array ist, wird in einer Variablen gespeichert. Da kann man gerade gelesen das variable, oder drucken Sie die Variable oder nur allgemein diese Variable zugreifen. Und voila, die konstante Zeit in Anspruch nimmt. Im Gegensatz dazu, denken Sie zurück zu kratzen. Denken Sie zurück an die erste Woche des C, Aufruf nur printf und Drucken etwas auf dem Bildschirm ist wohl konstante Zeit, denn es dauert nur einige der CPU-Zyklen zu zeigen dass der Text auf dem Bildschirm. Oder warten - geht das? Wie sonst könnten wir modellieren die Leistung von printf? Würde jemand gerne einverstanden, dass vielleicht ist es nicht wirklich konstante Zeit? In welchem ​​Sinne könnte printf läuft Zeit, etwas tatsächlich ausdrucken String auf der Bildschirm, etwas zu sein andere als konstant. ZUSCHAUER: [unverständlich]. DAVID MALAN: Yeah. Es hängt also von unserer Perspektive. Wenn wir tatsächlich denken, der Eingang zum printf als die Saite, und Daher messen wir die Größe, dass Eingang durch seine Länge - so nennen wir dass Länge n sowie - wohl, printf ist selbst groß O von n denn es geht um Sie n Schritte ausdrucken jedem dieser n Zeichen, wahrscheinlich. Wenigstens soweit wir annehmen, dass vielleicht ist es mit einer for-Schleife unter der Haube. Aber wir müssten sich das an Code, um sie besser verstehen. Und in der Tat, wenn man Jungs starten Analyse der eigenen Algorithmen, werden Sie buchstäblich genau das zu tun. Sortieren der Augapfel Ihren Code und denken über - alles in Ordnung, habe ich diese Schleife hier oder ich habe eine verschachtelte Schleifen hier das wird n mal n Dinge zu tun, und Sie können von Grund sortieren Sie Ihren Weg durch den Code, auch wenn es Pseudocode und nicht eigentliche Code. Und was ist mit der omega n squared? Was war ein Algorithmus, der in der besten Fall dauerte noch n squared Schritte? Ja? ZUSCHAUER: [unverständlich]. DAVID MALAN: Also Auswahl sortieren. Da in diesem Problem wirklich reduziert der Tatsache, dass wieder, ich weiß nicht, Ich habe die aktuelle kleinsten bis gefunden Ich habe alle verdammt Elemente überprüft. So Omega von, sagen wir, n, wir kam gerade mit einem. Insertion sort. Wenn die Liste zufällig sortiert werden bereits, im besten Fall müssen wir nur zu einem Durchgang zu machen, An welchem ​​Punkt sind wir sicher. Und dann könnte man sagen, linear zu sein, das ist sicher. Was über Omega von 1? Was im besten Fall könnte dauern eine konstante Anzahl von Schritten? So lineare Suche, wenn Sie einfach Glück und das Element Sie suchen am Anfang der Liste rechts, wenn es das ist, wo Sie beginnen Ihr sind lineare Durchlaufen dieser Liste. Und dies gilt für eine Reihe von Dingen. Zum Beispiel werden auch binäre Suche ist Omega von 1. Denn was ist, wenn man wirklich verdammt Glück und Klatschenkleks in der Mitte des Ihr Array ist die Anzahl Sie suchen? So kann man mit etwas Glück gibt es, wie gut. Dieses schließlich Omega n log n. So n log n, haben wir nicht wirklich reden noch nicht, aber - ZUSCHAUER: Merge sort? DAVID MALAN: Merge sort. Das war der Cliffhanger der letzten Zeit, wo wir vorgeschlagen, und wir zeigten visuell, dass es Algorithmen. Und verschmelzen Art nur eine solche Algorithmus, der grundsätzlich schneller ist als einige dieser anderen Jungs. Tatsächlich verschmelzen kurz ist nicht nur in der besten Fall n log n, im schlimmsten Fall n log n. Und wenn Sie über diese Koinzidenz Omega und große O ist die gleiche Sache? Wir können tatsächlich beschreiben, wie das, was ist Theta genannt, obwohl es ein etwas weniger häufig. Aber das bedeutet nur, dass die beiden Grenzen, in diesem Fall sind die gleichen. Also Mergesort, was hat das wirklich einkochen, um für uns? Nun, erinnern an die Motivation. Lassen Sie mich hochziehen andere Animation, wir nicht endlich Zeit zu suchen. Dieser eine, gleiche Idee, aber es ist ein wenig größer. Und ich werde weitermachen und darauf hinweisen, ersten - wir haben Insertion Sort auf oben links, dann Auswahl sortieren Bubble-Sort, ein paar andere Sorten - Shell und schnell -, dass wir nicht gesprochen über und Heap und Mergesort. So zumindest versuchen, Ihre Augen auf konzentrieren die ersten drei auf der linken Seite und dann Mergesort wenn ich auf diese grünen Pfeil. Aber ich lasse sie alle laufen, nur um geben Ihnen ein Gefühl für die Vielfalt der Algorithmen, die in der Welt existieren. Ich werde diesen Lauf lassen nur für ein paar Sekunden. Und wenn Sie sich Ihre Augen - Pick ein Algorithmus darauf konzentrieren nur für ein Sekunden - Sie beginnen zu sehen, die Muster, dass es die Umsetzung. Merge sort, bemerken, ist getan. Heap sort, schnelle Art, Schale - so scheint es, haben wir die drei schlimmsten Algorithmen letzte Woche. Aber das ist gut, dass wir hier sind, um Blick auf Merge sort, ist das einer der die leichteren, ist zu sehen, auch obwohl es vermutlich verbiegen Ihre Meinung nur ein kleines bisschen. Hier können wir sehen, wie viel Auswahl sortieren saugt. Aber auf der anderen Seite, ist es einfach zu implementieren. Und vielleicht für P Set 3, das ist einer der Sie wählten Algorithmen zu implementieren für die Standard Edition. Vollkommen in Ordnung, vollkommen richtig. Aber noch einmal, wie n groß wird, wenn Sie wählen, um einen schnelleren Algorithmus zu implementieren mag Mergesort, stehen die Chancen in größeren und größere Eingänge, ist Ihr Code nur gehen, um schneller zu laufen. Ihre Website wird funktionieren besser. Ihre Nutzer sich glücklicher zu sein. Und so sind diese Effekte der tatsächlich geben uns einige tiefer gedacht. Werfen wir also einen Blick auf, was zu verschmelzen Art ist eigentlich alles über. Das Coole daran ist, dass fusionieren Art ist genau dies. Dies ist wiederum das, was wir als Pseudocode Pseudocode Wesen Englisch-ähnliche Syntax. Und der Einfachheit Art faszinierend. So bei der Eingabe von n Elementen - so dass bedeutet nur, hier ist ein Array. Es ist n Dinge in ihm bekam. Das ist alles, was wir sagen, es sind. Ist n kleiner als 2, zurückzukehren. Also das ist nur der Fall trivial. Wenn n kleiner als 2 ist, dann ist es offensichtlich 1 oder 0 ist, in welchem ​​Fall die Sache bereits sortiert oder nicht vorhanden, so einfach zurück. Es gibt nichts zu tun. Also das ist ein einfacher Fall zu abzupfen. Else, haben wir drei Schritte. Sortieren Sie die linke Hälfte der Elemente, sortiert die rechte Hälfte der Elemente, und dann verschmelzen die sortierten Hälften. Interessant dabei ist, dass Ich bin eine Art punting, nicht wahr? Es ist eine Art kreisförmige Definition diesem Algorithmus. In welchem ​​Sinn ist dieser Algorithmus die Definition kreisförmigen? ZUSCHAUER: [unverständlich]. DAVID MALAN: Yeah, mein Sortieralgorithmus, zwei seiner Schritte sind "sort etwas. "Und damit die bettelt Frage, na ja, was soll ich verwenden die linke Hälfte sortieren und die rechte Hälfte? Und das Schöne dabei ist, dass, obwohl wieder, das ist die knifflige Teil potenziell, können Sie gleich Algorithmus, um die linke Hälfte zu sortieren. Aber warten Sie eine Minute. Wenn man dir sagt, um die Art linke Hälfte, was sind die beiden Schritte gehen, um der nächste sein? Wir sortieren die linke Hälfte des linke Hälfte und die rechte Hälfte der linken Hälfte. Verdammt, wie sortiere ich die beiden Hälften oder Viertel, jetzt? Aber das ist OK. Wir haben einen Sortieralgorithmus hier. Und obwohl Sie vielleicht an Sorgen erste dieser Art ist von einer unendlichen Schleife, es ist ein Zyklus, der ist nie zu Ende gehen - es wird gehen endet, wenn was passiert? Wenn n kleiner als 2 ist. Die schließlich passieren wird, denn wenn Sie zu halten und die Halbierung Halbierung halbieren diese Hälften, sicherlich schließlich wirst du enden mit nur 1 oder 0 Elemente. An welchem ​​Punkt, dieser Algorithmus sagt Sie fertig sind. Also die wirkliche Magie in dieser Algorithmus scheint in sein dass letzte Schritt, Zusammenführen. Diese einfache Idee nur die Zusammenlegung zweier Dinge, das ist, was letztlich gehen uns zu erlauben, eine Reihe von sortieren, sagen wir mal, acht Elementen. Also ich habe acht weitere Stress-Bälle bis hier acht Stück Papier, und ein Google Glass - denen ich zu halten. [Gelächter] DAVID MALAN: Wenn wir nehmen acht Freiwillige, und lasst uns sehen, ob wir spielen diese aus, so. Wow, OK. Informatik wird immer Spaß. In Ordnung. So wie sie Ihnen etwa drei, größten Hand gibt. Vier in den Rücken. Und wie machen wir Sie drei in dieser Reihe? Und vier in der Front. So können Sie acht, come on up. [Gelächter] DAVID MALAN: Ich bin eigentlich nicht sicher, was es ist. Ist es die Stress-Bälle? Die Schreibtischlampen? Das Material? Das Internet? OK. So kommen auf bis. Wer möchte - immer wieder auftauchen. Mal sehen. Und das bringt Sie in Lage - Sie sind in einer Lage. Uh-oh, warten Sie eine Minute. 1, 2, 3, 4, 5, 6, 7 - oh, gut. Alles klar, wir sind gut. Alles klar, so dass jeder einen Sitz haben, aber nicht auf der Google Glass. Lassen Sie mich in die Warteschlange bis diese. Wie ist dein Name? MICHELLE: Michelle. DAVID MALAN: Michelle? Okay, erhalten Sie aussehen Der Aussenseiter, wenn es das ist OK. Nun, ich auch tun, denke ich, nur für einen Augenblick. Alles klar, Standby. Wir haben versucht, sich mit einem Use-Case für Google Glass, und wir dachte, es würde Spaß machen, genau das zu tun dies, wenn die Leute auf der Bühne sind. Wir erfassen die Welt aus ihrer Perspektive. In Ordnung. Nicht wahrscheinlich das, was Google gedacht. Gut, wenn Sie nichts dagegen haben das Tragen diese für die nächsten umständlich Minuten das wäre wunderbar. Na gut, so haben wir hier eine Reihe von Elemente, und das Array nach der Stücke von Papier in diese Leute ' Hände, ist derzeit unsortiert. MICHELLE: Oh, das ist so komisch. DAVID MALAN: Es ist ziemlich zufällig. Und in einem Moment, werden wir versuchen, zu implementieren Mergesort zusammen und sehen, wo die wichtigste Erkenntnis ist. Und der Trick mit Merge sort ist etwas, dass wir nicht noch angenommen. Tatsächlich brauchen wir einige zusätzlichen Platz. Also, was ist los als besonders Interessant dabei ist, dass diese Kerle werden sich ein wenig zu bewegen bit, weil ich gehe davon aus, dass gibt es eine zusätzliche Anordnung von Raum, sagen, direkt hinter ihnen. Also, wenn sie sind hinter ihren Stuhl, Das ist die sekundäre Array. Wenn sie hier sind sitzen, das ist das primäre Array. Aber das ist eine Ressource, die wir haben nicht so weit mit Blase genutzt Art, mit Auswahl sortieren mit Insertion Sort. Daran erinnern, letzte Woche, jeder nur Art schlurfte im Ort. Sie habe keinerlei zusätzlichen Speicher. Wir haben Platz für Menschen, die von Menschen bewegen sich um. Dies ist also eine wichtige Erkenntnis, auch. Es ist das Trade-off, in der Regel in Informatik, der Ressourcen. Wenn Sie möchten, zu beschleunigen, etwas wie die Zeit, du bist zu gehen haben, einen Preis zu zahlen. Und einer von diesen Preisen ist sehr oft Raum, die Größe des Speichers oder harten Speicherplatz, den Sie verwenden. Oder, ehrlich gesagt, die Menge der Programmierer Zeit. Wie viel Zeit es dauert, der Mensch, tatsächlich umzusetzen etwas mehr komplizierten Algorithmus. Aber für heute, den Trade-off ist Zeit und Raum. Also, wenn euch könnte nur halten Sie Ihre Zahlen, so dass wir sehen können, dass Sie tatsächlich passende 4, 2, 6, 1, 3, 7, 8. Excellent. Also werde ich versuchen, zu orchestrieren Dinge können, wenn euch nur folge meinem Blei hier. So werde ich zu implementieren, zunächst die ersten Schritt des Pseudocode, das ist am Eingang von n Elementen, wenn n weniger als 2, dann zurückzukehren. Natürlich bedeutet das nicht, gelten, so dass wir weiterziehen. So sortieren Sie die linke Hälfte der Elemente. Also das heißt, ich werde meinen Fokus Aufmerksamkeit für einen Moment auf diese vier Jungs hier. Alles klar, was ich als nächstes tun? ZUSCHAUER: Sortieren Sie die linke Hälfte. DAVID MALAN: So jetzt habe ich zu sortieren die linke Hälfte von diesen Jungs. Weil wieder, um sich dem annehmen Ziel ist es, die linke Hälfte sortieren. Wie machst du das? Folgen Sie einfach den Anweisungen, auch obwohl wir es wieder tun. So sortieren Sie die linke Hälfte. Jetzt bin ich ordnen diese beiden Jungs. Was kommt als nächstes? ZUSCHAUER: Sortieren Sie die linke Hälfte. DAVID MALAN: Sortieren Sie die linke Hälfte. So, jetzt diese, dieser Platz hier, ist eine Liste der Größe 1. Und was ist Ihr Name? PRINCESS DAISY: Princess Daisy. DAVID MALAN: Princess Daisy ist hier. Und so ist sie bereits sortiert, weil die Liste ist von Größe 1. Was muss ich als nächstes tun? OK, zurück, weil diese Liste ist der Größe 1, die weniger als 2 ist. Was ist dann der nächste Schritt? Und jetzt müssen Sie Art Backtrack in deinem Geist. Sortieren Sie die rechte Hälfte, das ist - was ist Ihr Name? LINDA: Linda. DAVID MALAN: Linda. Und was machen wir jetzt, dass haben wir eine Liste der Größe 1? ZUSCHAUER: Return. DAVID MALAN: Vorsichtig. Wir kehren erste, und jetzt das dritte Schritt - und wenn ich irgendwie zeigen sie durch umarmt die beiden Sitze jetzt, jetzt habe ich müssen diese beiden Elemente zu verschmelzen. So, jetzt leider die Elemente sind nicht in Ordnung. Aber das ist, wo die Verschmelzung Prozess beginnt sich zu überzeugend. Also, wenn euch könnte sich für nur Einen Moment, ich werde Sie brauchen, in ein Moment, um hinter den Stuhl fort. Und wenn Linda, weil 2 kleiner als 4 ist, warum nicht Sie kommen um zuerst? Bleiben Sie dort. So Linda, kommen Sie um die erste. Jetzt in der Realität, wenn es nur ein Array wir konnten nur bewegen sie in Echtzeit aus diesem Stuhl an diese Stelle. So vorstellen, dass einige konstante nahm Anzahl der Schritte 1. Und jetzt - aber wir müssen Sie setzen in die erste Stelle hier. Und jetzt, wenn Sie könnten um zu kommen, sowie, wir gehen zu sein in Position zwei. Und obwohl dies fühlt sich an wie es ist Einnahme einer Weile, was ist schön jetzt dass die linke Hälfte der linke Hälfte ist nun sortiert. Also, was war der nächste Schritt, wenn wir jetzt zurückspulen weiter in der Geschichte? ZUSCHAUER: Rechte Hälfte. DAVID MALAN: Sortieren Sie die rechte Hälfte. Also Jungs haben, dies zu tun, wie gut. Also, wenn Sie aufstehen konnte nur für einen Augenblick? Und was ist Ihr Name? Jess: Jess. DAVID MALAN: Jess. OK, so Jess ist nun die linke Hälfte der rechten Hälfte. Und so ist eine Liste der Größe 1. Sie ist offensichtlich sortiert. Und noch mal Ihr Name? MICHELLE: Michelle. DAVID MALAN: Michelle ist offensichtlich eine Liste der Größe 1. Sie ist bereits sortiert. So, jetzt die Magie passiert, die Verschmelzung Prozess. Also wer wird zuerst kommen? Offensichtlich Michelle. Also, wenn Sie kommen könnten um zurück. Der Raum, den wir zur Verfügung haben für sie jetzt befindet sich direkt hinter diesem Stuhl hier. Und jetzt, wenn Sie könnten wieder als gut, wir jetzt haben, klar zu sein, zwei Hälften, die jeweils eine Größe von 2 - und nur zur Darstellung willen, wenn Sie könnte ein wenig von einem Raum zu machen - eine linke Hälfte hier, eine rechte Hälfte hier. Spulen Sie weiter in der Geschichte. Welche Schritt geht es weiter? ZUSCHAUER: Zusammenführen. DAVID MALAN: So, jetzt haben wir zu fusionieren. So OK, so jetzt, Gott sei Dank, wir nur bis vier Stühlen befreit. Deshalb haben wir doppelt so viel Speicher, aber können wir Flip-flopping geben zwischen die beiden Arrays. So ist die Zahl an erster Stelle? Also Michelle, offensichtlich. So etwa kommen und Ihren Sitz hier. Und dann die Nummer 2 ist offensichtlich nächsten, so kommen Sie hier. Nummer 4, Nummer 6. Und wieder, obwohl es ein wenig zu Fuß beteiligt, wirklich, könnten diese sofort passieren, indem man - OK, gut gespielt. [Gelächter] DAVID MALAN: Und jetzt sind wir in ziemlich guter Form. Die linke Hälfte des gesamten Eingangs wurde nun sortiert. Alles klar, so dass diese Jungs hatten Der Vorteil my - wie kam es am Ende all die Mädchen auf die links und all die Jungs auf der rechten Seite? OK, so Jungs nun zuwenden. Also werde ich nicht gehen Sie durch diese Schritte. Wir werden sehen, ob wir erneut kann das gleiche Pseudocode. Wenn Sie möchten, gehen Sie vor und aufstehen, und euch, lassen Sie mich Ihnen das Mikrofon. Sehen Sie, wenn Sie sich nicht replizieren, was Wir haben einfach hier auf die andere Ende der Liste. Wer braucht zuerst zu sprechen, basierend auf dem Algorithmus? So erklären, was Sie tun, bevor Sie machen alle Bewegungen Fuß. Sprecher 1: Alles klar, also seit Ich bin der linken Hälfte des linke Hälfte, kehre ich. Right? DAVID MALAN: Good. Sprecher 1: Und dann - DAVID MALAN: Wer macht das Mikrofon weiter gehen? Sprecher 1: Nächste Nummer. Sprecher 2: Also ich bin die rechte Hälfte der linken Hälfte der linke Hälfte, und ich zurück. DAVID MALAN: Good. Sie kehren. So jetzt, was ist der nächste für Sie zwei? Sprecher 2: Wir wollen sehen, wer kleiner. DAVID MALAN: Genau. Wir wollen fusionieren. Der Raum, den wir gehen, um zu verwenden, um zu verschmelzen sind Sie in, obwohl sie sind offensichtlich bereits sortiert, wir gehen um den gleichen Algorithmus befolgen. Also, wer geht in erster zurück? Also 3 und dann 7. Und jetzt geht das Mikrofon zu diesen Jungs, OK? SPEAKER 3: Also ich bin die rechte Hälfte des linke und meine n kleiner als 1, so dass ich werde einfach passieren - DAVID MALAN: Good. SPEAKER 4: Ich bin die rechte Hälfte des rechten Hälfte der rechten Hälfte, und ich bin auch eine Person, also bin ich gehen, um zurückzukehren. So, jetzt haben wir zusammengeführt. SPEAKER 3: So gehen wir zurück. DAVID MALAN: Also in den Rücken gehen. Also 5 geht, dann 8. Und nun Publikum, das ist die Schritt müssen wir jetzt zurückspulen hinten, um in unseren Köpfen? ZUSCHAUER: Zusammenführen. DAVID MALAN: Zusammenführen von linken und rechten Hälfte die Hälfte der ursprünglichen linken Hälfte. So, jetzt - und gerade dies deutlich zu machen, machen ein wenig Raum zwischen Ihnen beiden Jungs. Also das ist jetzt die beiden Listen, links und rechts. So, wie wir jetzt fusionieren euch in die vordere Sitzreihe wieder? 3 beginnt. Dann 5, offensichtlich. Dann 7, 8 und jetzt. OK, und jetzt sind wir? ZUSCHAUER: Nicht getan. DAVID MALAN: Nicht getan, denn offensichtlich gibt es einen Schritt übrig. Aber noch einmal, der Grund warum ich bin mit dieser Jargon wie "Rewind in your mind," es ist, weil das ist wirklich was passiert. Wir durch alle diese Schritte gehen, aber wir sind eine Art Pause für ein Moment, tauchen tiefer in die Algorithmus, einen Moment innehalten, Tauchen tiefer in den Algorithmus und jetzt müssen wir der Rücklauf in unserem sortieren Köpfe und rückgängig all dieser Schichten dass wir irgendwie auf Eis gelegt. So, jetzt haben wir zwei Listen der Größe 4. Wenn euch aufstehen konnte ein letztes Mal und machen ein wenig Platz hier, um deutlich machen, dass diese die Linke die Hälfte des ursprünglichen, die rechte Hälfte der ursprünglichen. Wer ist die erste Zahl, die wir brauchen, um in den Rücken ziehen? Michelle, natürlich. Also haben wir Michelle hier. Und wer hat die Nummer 2? Nummer 2 kommt auf der Rückseite als auch. Nummer 3? Excellent. Number 4, Nr. 5, Nr. 6, Nummer 7 und Nummer 8. OK, so fühlte es sich wie eine Menge von Schritten, das ist sicher. Aber jetzt wollen wir sehen, ob wir nicht bestätigen können, Art intuitiv, dass diese Algorithmus grundlegend, zumal n wird wirklich groß ist, wie wir gesehen haben mit den Animationen ist grundsätzlich schneller. Also ich behaupte, diesen Algorithmus im schlimmsten Fall und auch im besten Fall ist groß O von n mal n log. Das heißt, es ist ein Aspekt dieser Algorithmus, der n Schritte unternimmt, aber gibt es einen anderen Aspekt irgendwo in dass Iteration, dass Looping, dass nimmt log n Schritte. Können wir unsere Finger auf das, was die zwei Zahlen sich beziehen? Nun, wo - wo ist das Mikrofon zu gehen? Sprecher 1: Würde die sich n sein Brechen Sie uns in zwei - Division durch zwei, im Wesentlichen. DAVID MALAN: Genau. Jedes Mal, wenn wir sehen, in jedem Algorithmus so Bis jetzt hat es schon dieses Muster von Teilen, teilen, teilen. Und es ist in der Regel reduziert etwas, das ist logarithmisch, log Basis 2. Aber es könnte wirklich alles sein, aber einloggen Basis 2. Nun, was über die n? Ich kann sehen, dass wir freundlich von Ihnen geteilt Jungs - unterteilt Sie, eingeteilt Sie, Sie unterteilt, unterteilt man. Woher kommt das Ende kommen? So ist es die Verschmelzung. Weil darüber nachdenken. Beim Zusammenführen acht Personen zusammen, wobei die Hälfte von denen ein Satz von vier und die andere Hälfte ein weiteres Satz von vier, wie Sie gehen über das Tun der Verschmelzung? Nun, habt ihr es ziemlich intuitiv. Aber wenn ich es täte stattdessen ein wenig mehr methodisch, könnte ich an hingewiesen haben die linke Person zum ersten Mal mit meinem linken Hand, zeigte auf der linken Person dieser Hälfte mit meiner rechten Hand, und nur danach ging durch die Liste zeigt auf die kleinste Element jedes Mal, bewegte meine Finger über und über, wie er in der Liste benötigt. Aber was ist Schlüssel zu dieser Verschmelzung Prozess ist, vergleiche ich diese Paare der Elemente. Von der rechten Hälfte und der linken Hälfte, ich bin nicht einmal Backtracking. Also die Zusammenführung selbst nimmt nicht mehr als n Schritte. Und wie oft hatte ich zu, dass Zusammenführen tun? Nun, nicht mehr als n, und wir sah, dass mit der endgültigen Zusammenführung. Und so, wenn Sie etwas tun, was kommt einloggen n Schritte n mal, oder umgekehrt, es geht um uns mal n log n. Und warum ist das besser? Nun, wenn wir schon wissen, dass log n ist besser als n - richtig? Wir sahen in binäre Suche, das Telefonbuch Beispielsweise war definitiv log n besser als linear. Das heißt also, mal n log n ist definitiv besser als n mal einen anderen n, n AKA Quadrat. Und das ist, was wir letztlich fühlen. So großen Applaus, wenn wir könnten, für diese Jungs. [Applaus] DAVID MALAN: Und Ihre Abschiedsgeschenke - Sie halten die Zahlen, wenn Sie möchten. Und dein Abschiedsgeschenk, wie üblich. Oh, und wir schicken Ihnen das Filmmaterial, Michelle. Vielen Dank. In Ordnung. Helfen Sie sich selbst mit einem Stress-Ball. Und lassen Sie mich nach oben ziehen, in der Zwischenzeit unser Freund Rob Bowden zu bieten etwas andere Perspektive auf das, da kann man über diese denken Schritte geschieht in einem etwas anders. In der Tat, das Set-up für das, was Rob geht um um uns zu zeigen, dass wir davon ausgegangen, bereits getan die Aufteilung der große Liste in acht kleinen Listen jeder Größe 1. So ändern wir den Pseudocode ein wenig, nur um von sich bei der sortieren Kern Vorstellung davon, wie die Zusammenführung funktioniert. Aber die Laufzeit, welche er ist etwa zu tun ist immer noch gehen, um die gleichen sein. Und wieder ist das Set-up ist hier, dass er begonnen mit acht Listen der Größe 1. Sie haben also den Teil, wo er ist vermisst tatsächlich getan der log n, log n, log n Aufteilen des Eingangssignals. [VIDEO PLAYBACK] -Das ist es für einen Schritt. Für Schritt zwei, wiederholt verschmelze Paare von Listen. DAVID MALAN: Hm. Nur Audio kommt aus meinem Computer. Lassen Sie uns noch einmal versuchen. -Just beliebig wählen, welche - jetzt haben wir vier Listen. Lernen vor. DAVID MALAN: Dort gehen wir. Merging-108 und 15 landen wir mit der Liste 15, 108. Zusammenführen von 50 und 4, wir am Ende mit 4, 50. Zusammenführen von 8 und 42, wir am Ende mit 8, 42. Und Zusammenführen 23 und 16, wir am Ende mit 16, 23. Nun sind alle unsere Listen sind der Größe 2. Beachten Sie, dass jede der vier Listen sortiert ist. So können wir anfangen Verschmelzung Paare von Listen wieder. Zusammenführen von 15 und 108 und 4 und 50, wir nehmen Sie zuerst die 4, dann die 15, dann die 50, dann die 108. Zusammenführen von 8, 42 und 16, 23, wir zunächst die 8, dann die 16, dann die 23, dann ist die 42. So, jetzt haben wir nur zwei Listen der Größe 4, von denen jede sortiert. So, jetzt haben wir verschmelzen diese beiden Listen. Erstens haben wir die 4 nehmen, dann nehmen wir die 8, dann nehmen wir die 15, dann 16, dann 23, dann 42, dann 50, dann 108. [END VIDEO PLAYBACK] DAVID MALAN: Wieder Ankündigung, er nie berührt einen bestimmten Tasse mehr als einmal nach dem Vorrücken darüber hinaus. Also ist er nie wiederholen. Also ist er immer in Bewegung zur Seite, und das ist, wo wir unsere n einsehen. Warum lassen Sie nicht mich hochzuziehen eine Animation dass wir früher gesehen, aber dieses Mal sich nur auf Merge sort. Lassen Sie mich gehen Sie vor und vergrößern Auf diesem hier. Zunächst lassen Sie mich wählen einen zufälligen Eingang, vergrößern dies, und Sie können von zu sehen sortieren was wir für selbstverständlich hielt, früher, Mergesort tatsächlich tut. So bemerken, dass Sie diese Hälften erhalten oder diese Viertel oder Achtel der diese Problem, dass alle von einer plötzlichen beginnen, gut in Form zu nehmen. Und dann endlich, sehen Sie auf ganz am Ende, dass bam, alles zusammengeführt. So sind nur drei verschiedene nimmt auf der gleichen Idee. Aber die wichtigste Erkenntnis, wie divide und in der ersten Klasse zu erobern, war, dass wir irgendwie teilen beschlossen das Problem in etwas Großes, in etwas Art identisch im Geiste, aber kleiner und kleiner und kleiner. Nun noch eine unterhaltsame Art und Weise zu denken sortieren über diese, obwohl es nicht gehen, um Ihnen die gleiche intuitive Verständnis ist Die folgende Animation. Also das ist ein Video jemand zusammen dass damit verbundenen unterschiedlichen Klänge mit den verschiedenen Operationen Insertion Sort, Merge für Art und ein paar andere. So in einem Moment, werde ich spielen getroffen. Es geht darum, eine Minute lang. Und auch wenn man noch die Muster geschieht, dieser Zeit können Sie auch hören, wie diese Algorithmen sind Durchführen anders und mit etwas verschiedenen Mustern. Dies ist Insertion Sort. [TÖNE SPIELT] DAVID MALAN: Es wird wieder versuchen um jedes Element einfügen in, wo es hingehört. Dies ist bubble sort. [TÖNE SPIELT] DAVID MALAN: Und Sie können von Gefühl sortieren wie relativ wenig Arbeit es tut auf jedem Schritt. Dies ist, was Langeweile klingt. [TÖNE SPIELT] DAVID MALAN: Dies ist Selection Sort, wo wir wählen Sie das Element wollen wir durch Durchlaufen wieder und wieder und wieder und legt es am Anfang. [TÖNE SPIELT] DAVID MALAN: Dies ist Mergesort, die Sie kann wirklich beginnen zu fühlen. [TÖNE SPIELT] [Gelächter] DAVID MALAN: Etwas namens gnome Art, die wir nicht geschaut haben. [TÖNE SPIELT] DAVID MALAN: So lassen Sie mich sehen, jetzt, abgelenkt, wie Sie hoffentlich durch die Musik, wenn ich ein wenig rutschen etwas Mathe hier. Also gibt es eine vierte Möglichkeit, dass wir darüber nachzudenken, was es bedeutet, diese Funktionen schneller als diejenigen sein dass wir noch nie gesehen. Und wenn Sie auf dem Golfplatz aus ein Mathematik-Hintergrund, Sie tatsächlich vielleicht schon wissen, dass Sie kann eine Laufzeit über diese Technik zu schlagen - nämlich Rekursion eine Funktion das nennt sich irgendwie. Und wieder daran erinnern, dass Merge sort Pseudocode war in dem Sinne, rekursiv dass eine Zusammenführung Art der Schritte war zu sortieren nennen - das heißt, sich. Aber zum Glück, weil wir immer Aufruf sortieren oder Mergesort, Insbesondere für ein kleiner und kleinere Liste, wir schließlich Talsohle dank dem, was wir nennen eine Basis Fall die hart codierte Fall, dass sagte, wenn die Liste ist klein, weniger als 2 in diesem Fall nur sofort zurück. Wenn wir nicht haben, dass spezielle Fall der Algorithmus würde nie Talsohle, und Sie würden in der Tat in eine bekommen Endlosschleife wirklich immer. Aber nehmen wir an, dass wir jetzt stellen wollte einige Zahlen dazu, wieder mit n wenn die Größe des Eingangs. Und ich wollte Sie fragen, was ist die gesamte Zeit beteiligt Mergevorgang Art? Oder allgemeiner, was ist die Kosten für die es in der Zeit? Nun, es ist ziemlich einfach, dass zu messen. Wenn n kleiner als 2 ist, involviert die Zeit Sortierung in n Elemente, wenn n 2 ist, 0 ist. Weil wir gerade zurück. Es gibt keine Arbeit getan werden. Nun wohl, vielleicht ist es einen Schritt oder zwei Schritte, um herauszufinden, die Menge der arbeiten, aber es ist nahe genug, um 0, dass Ich werde einfach sagen, keine Arbeit erforderlich, wenn die Liste ist so klein zu uninteressant. Aber dieser Fall ist interessant. Die rekursive Fall war der Zweig der der Pseudocode, anderes sagte, sortieren die linke Hälfte, sortieren das Recht Hälfte, verschmelzen die beiden Hälften. Nun, warum tut dies Ausdruck stellen, dass die Kosten? Nun, T von n bedeutet nur die Zeit, um n Elemente zu sortieren. Und dann auf der rechten Seite des Gleichheitszeichen gibt, teilte die T von n von 2 ist auf die Kosten, was bezogen? Sortieren der linken Hälfte. Die andere T von n geteilt durch 2 ist vermutlich mit Bezug auf die Kosten für sortieren die rechte Hälfte. Und dann die plus n? Ist die Verschmelzung. Denn wenn Sie haben zwei Listen, eine der Größe n mehr als 2 und eine andere Größe n über 2, müssen Sie im Wesentlichen berühren jedes dieser Elemente, so wie Rob berührt jede der Schalen, und nur wie wir bereits an jedem der Freiwillige auf der Bühne. So n ist der Aufwand der Zusammenführung. Jetzt leider diese Formel ist auch selbst rekursiv. Also, wenn die Frage gestellt, wenn n, sagen wir, 16, wenn es 16 Leute auf der Bühne oder 16 Tassen in dem Video, wie viele insgesamt Schritte braucht es, um sie zu sortieren mit Merge sort? Es ist eigentlich nicht eine offensichtliche Antwort, denn jetzt haben Sie von sortieren rekursiv beantworten diese Formel. Aber das ist OK, weil mich schlagen was wir tun, die folgenden. Der Zeitaufwand, um 16 Personen zu sortieren oder 16 Tassen wird vertreten sein allgemein als T von 16 Jahren. Aber das entspricht nach unserer vorherige Formel, 2-fache der Menge Zeit, die es braucht, um zu sortieren 8 Tassen plus 16. Und wieder ist die Zeit plus 16 zu verschmelzen, und die zwei Zeiten T von 8 ist die Zeit, um linke Hälfte und rechte Hälfte sortieren. Aber auch dies ist nicht genug. Wir müssen in tiefer tauchen. Das heißt, wir müssen die Antwort Frage, was ist T von 8? Nun T von 8 ist nur 2 Zeiten T von 4 und 8. Nun, was ist T von 4? T 4 ist nur 2 mal T von 2 plus 4. Nun, was ist T von 2? T 2 ist nur 2 mal T von 1 plus 2 sein. Und wieder sind wir irgendwie immer stecken in diesem Zyklus. Aber es ist darüber zu treffen, dass sogenannte Base-Case. Denn was ist T von 1, haben wir behaupten? 0. So, jetzt endlich können wir rückwärts arbeiten. Wenn T von 1 0 ist, kann ich jetzt gehen zurück bis eine Die Linie die diesen Kerl hier, und ich kann Stecker in 0 für T 1. Das heißt also, es gleich 2 mal Null, anders als 0, plus 2 bekannt. Und damit ganze Ausdruck 2 ist. Nun, wenn ich den T 2, dessen Antwort 2 ist, stecken Sie es in der mittleren Linie, T von 4, das gibt mir 2 mal 2 plus 4, 8 so. Wenn ich dann stecken in 8 zum vorherigen Linie, das gibt mir 2 mal 8, 16. Und wenn wir dann weiter, dass mit dem 24, indem in 16, bekommen wir endlich ein Wert von 64. Nun, an und für sich eine Art spricht nichts der n-Notation, die big O, das Omega, dass wir worden reden. Aber es stellt sich heraus, dass 64 tatsächlich 16, die Größe des Eingangssignals, einloggen Basis 2 von 16 Jahren. Und wenn dies ist ein wenig ungewohnt, nur denken Sie zurück, und es wird wieder kommen Sie schließlich. Wenn dies Logbase 2, es ist wie 2 angehoben, um das, was gibt Ihnen 16? Oh, das ist 4, so ist es 16 mal 4. Und wieder ist es keine große Sache, wenn diese ist eine Art verschwommene Erinnerung jetzt. Aber jetzt, auf den Glauben nehmen dass 16 log 16 64. Und so in der Tat, mit diesem einfachen Vernunft , überprüfen wir bestätigt haben - aber nicht bewiesen formal - dass die Laufzeit von Merge Art ist in der Tat n n einloggen. Also nicht schlecht. Es ist definitiv besser als die Algorithmen, die wir bisher gesehen haben, und es ist, weil wir genutzt haben, ein, eine Technik namens Rekursion. Aber viel interessanter als das, dass Begriff der Teilung und Eroberung. Auch wirklich Woche 0 Zeug, dass auch jetzt wird in einer wiederkehrenden mehr überzeugende Art und Weise. Nun wird ein Spaß wenig Übung, wenn Sie nie getan - und Sie wahrscheinlich wäre nicht zu haben, denn irgendwie normale Leute nicht denken, dies zu tun. Aber wenn ich gehe zu google.com und wenn Ich möchte etwas erfahren Rekursion, Enter. [Gelächter] [Mehr Gelächter] DAVID MALAN: Bad Witz langsam ausbreitet. [Gelächter] DAVID MALAN: Nur für den Fall, es ist da. Ich wusste nicht buchstabieren es falsch, und es ist der Witz. In Ordnung. Erklären Sie es den Menschen neben dir, wenn Es hat nicht ganz geklickt nur noch. Aber Rekursion, allgemein bezeichnet der Prozess einer Funktion, Aufrufen selbst, oder allgemeiner, eine Teilung Problem in etwas, das kann stückweise durch Lösen identisch gelöst Vertreter Probleme. Nun, lasst Wechselräder nur für einen Augenblick. Wir möchten auf bestimmte Cliffhanger enden, also lasst uns beginnen, um die Bühne, für einige Minuten, auf eine sehr einfache Idee - dass der Vertauschung zweier Elemente, nicht wahr? All diese Algorithmen, die wir waren reden über die letzten paar Vorträge beinhalten einige Art von Austausch. Heute wurde es von ihnen immer sichtbar aus ihrem Sessel und herumlaufen, aber im Code, würden wir nehmen Sie einfach ein Element aus einem Array und plop es in eine andere. So, wie wir dabei vorgehen? Nun, lasst mich weitermachen und schreiben ein schnelles Programm hier. Ich werde weitermachen und tun diese wie folgt. Nennen wir diese - Was wollen wir, dieses zu nennen? Eigentlich nicht. Lassen Sie mich zurückzuspulen. Ich möchte nicht, das zu tun Cliffhanger noch. Es wird den Spaß verderben. Lassen Sie uns diese statt. Angenommen, dass ich ein wenig schreiben wollen Programm und das umfasst heute diese Idee der Rekursion. Ich irgendwie bekam vor mir da. Ich werde folgendes tun. Erstens gehören eine schnelle Standard-io.h, sowie eine Include von cs50.h. Und dann werde ich weitermachen und erklären int main nichtig in der üblichen Weise. Ich erkannte, ich habe die Datei falsch benannt, so lassen Sie mich einfach ein. c Erweiterung hier so dass wir es richtig zu kompilieren. Starten Sie diese Funktion ausschalten. Und die Funktion, die ich schreiben möchte, ganz Einfach ausgedrückt, ist derjenige, der fragt, Benutzer für eine Reihe und dann summiert sich alle Zahlen zwischen dem Anzahl und, sagen wir, 0. Also zuerst werde ich weitermachen und erklären, int n. Dann kopiere ich einige Code, dass wir haben für eine Weile benutzt. Während etwas wahr ist. Ich komme zurück auf das in einem Moment. Was will ich tun? Ich möchte sagen, printf positive integer bitte. Und dann bin ich zu gehen sagen n bekommt bekommen int. Also noch einmal, einige Textvorschlag Code dass wir vor verwendet. Und ich werde, dies zu tun während n kleiner als 1 ist. So wird dies zu gewährleisten, dass der Benutzer gibt mir eine positive ganze Zahl ist. Und jetzt werde ich folgendes tun. Ich möchte hinzufügen, bis alle Zahlen zwischen 1 und und n oder 0 ist und n, äquivalent zu bekommen die Gesamtsumme. Die große Sigma-Symbol Sie erinnern sich vielleicht an. Also werde ich dies durch erste Berufung zu tun eine Funktion aufgerufen sigma, Übergabe in n, und dann bin ich zu gehen printf sagen, die Antwort ist recht. Also kurz gesagt, ich bekomme und int von dem Benutzer. Ich stelle sicher, es ist positiv. Ich erkläre, eine Variable namens Antwort Typ int und speichern es in die Rückkehr Wert von sigma, übergibt n als Eingabe. Und dann drucke ich diese Antwort. Leider, obwohl sigma klingt wie etwas, das in sein könnten die math.h Datei, seine Erklärung, es ist eigentlich nicht. Also das ist OK. Ich kann das selbst implementieren. Ich werde eine Funktion namens implementieren sigma, und es geht um eine nehmen Parameter - wir nennen es einfach m, nur so ist es anders. Und dann hier, werde ich sagen, gut, wenn m kleiner als 1 ist - dies ist ein sehr uninteressant Programm. Also werde ich weitermachen und sofort 0 zurück. Es macht einfach keinen Sinn, addieren Sie alle Die Zahlen zwischen 1 und m, wenn m selbst 0 oder negativ ist. Und dann werde ich weitermachen und tun dies sehr iterativ. Ich werde diese Art der alten Schule zu tun, und ich werde weitermachen und sagen, dass ich zu gehen deklarieren eine Summe 0 sein. Dann werde ich zu haben eine for-Schleife von int - und lass es mich tun, um unser Spiel Verteilung Code, so dass Sie eine Kopie zu Hause. int i bekommt 1 auf bis zu i kleiner oder gleich m ist. i plus plus. Und dann innerhalb dieser for-Schleife - wir sind fast da - Summe bekommt Summe plus 1. Und dann werde ich die Summe zurück. Also tat ich dies schnell, ganz zugegebenermaßen. Aber nochmals, die Hauptfunktion ziemlich unkompliziert, basierte auf Code, den wir haben geschrieben so weit. Verwendet die Dual-Schleife, um eine positive bekommen int von dem Benutzer. Ich habe dann passieren, dass int auf eine neue Funktion genannt sigma, ruft sie, wieder n. Und ich speichern den Rückgabewert, die Antwort von der Blackbox derzeit bekannt als sigma, in einer variablen genannt Antwort. Dann habe ich ausdrucken. Wenn wir nun die Geschichte weiter, wie ist Sigma umgesetzt? Ich schlage vor, wie folgt zu implementieren. Zuerst ein wenig Fehlerprüfung um sicherzustellen, dass der Benutzer nicht ist Messing mit mir und Weitergabe in einige negativ oder 0-Wert. Dann erkläre ich eine Variable namens Zusammenfassend und auf 0 setzen. Und jetzt habe ich beginnen sich zu bewegen von i gleich 1 den ganzen Weg bis einschließlich m, denn ich will alles umfassen Zahlen von eins bis m, inklusive. Und innerhalb dieser for-Schleife, ich habe gerade zu tun Summe bekommt, was es jetzt ist, zuzüglich der Wert von i. Zuzüglich des Wertes der i. Nebenbei, wenn Sie noch nicht gesehen vor, es gibt einige syntaktische Zucker für diese Leitung. Ich kann umschreiben dies als Plus gleich i, nur um mich retten ein paar Tastenanschläge und sehen ein bisschen kühler. Aber das ist alles. Es ist funktionell dasselbe. Leider ist dieser Kodex noch nicht zu kompilieren. Wenn ich make ausführe sigma 0, wie am Ich werde bei Get schrie? Was es wird nicht dabei? ZUSCHAUER: [unverständlich]. DAVID MALAN: Yeah, ich habe nicht erklären die Funktion up top, right? C ist ziemlich blöd, dass es nur macht, was Sie sagen, zu tun, und Sie haben, um es in dieser Reihenfolge zu tun. Und so, wenn ich hier eingeben schlagen, werde ich erhalten eine Warnung über Sigma impliziten Erklärung. Oh, kein Problem. Ich kann gehen bis an die Spitze, und ich kann sagen, alles in Ordnung, warten Sie eine Minute. Sigma ist eine Funktion, kehrt ein int und erwartet ein int als Eingabe Semikolon. Oder ich könnte die ganze Funktion setzen über Haupt-, aber im Allgemeinen würde ich raten, dass, weil es schön, um immer über Haupt an der Spitze so Sie können eintauchen und wissen, was ein Programms durch das Lesen wichtigsten ersten tun. So, jetzt lassen Sie mich klar auf den Bildschirm. Remake sigma 0. Alles scheint zu überprüfen. Lassen Sie mich laufen sigma 0. Positive unter. Ich gebe es die Anzahl 3 es einfach zu halten. Also das sollte mir 3 zzgl. 2 plus 1, also 6. Geben Sie, und zwar bekomme ich 6. Ich kann etwas tun, größer - 50, 12, 75. Gerade als Tangente, werde ich tun etwas Lächerliches wie eine wirklich große Anzahl, Oh, die tatsächlich geklappt - eh, ich glaube nicht, das ist richtig. Mal sehen. Lasst uns wirklich damit herum. Das ist ein Problem. Was ist da los? Der Code ist nicht so schlimm. Es ist immer noch linear. Pfeifen ist eine gute Wirkung, though. Was ist da los? Nicht sicher, ob ich es hörte. So stellt sich heraus - und dies ist als ein beiseite. Dies ist nicht der Kern der Idee der Rekursion. Es stellt sich heraus, weil ich versuche, mich stellen so eine große Zahl, die meisten wahrscheinlich ist es falsch interpretiert durch C als nicht positive Zahl ist, aber negative Zahl ist. Wir haben nicht darüber gesprochen, aber es stellt sich heraus, es gibt negative Zahlen in der Welt zusätzlich auf positive Zahlen. Und die Mittel, mit denen Sie negativen Zahlen darstellen im Wesentlichen ist, verwenden Sie einen spezielles Bit, um anzuzeigen, positiv in negativ. Es ist ein wenig komplizierter als das, aber das ist die Grundidee. Also leider, wenn C ist verwirrend einer dieser Bits als eigentlich bedeutet, oh, das ist eine negative Zahl, meine Schleife hier, zum Beispiel, ist eigentlich nie gehen, um zu beenden. Also, wenn ich tatsächlich etwas Druck wieder und wieder, würden wir sehen eine ganze Menge. Aber auch dies ist neben dem Punkt. Das ist wirklich nur eine Art intellektuelle Neugier, dass wir kommen zurück, um schließlich. Aber jetzt, ist dies eine richtige Umsetzung, wenn wir annehmen, dass die Benutzer stellen ints die passen in ints. Aber ich behaupte, dass dieser Code, ehrlich gesagt, könnte so viel einfacher durchgeführt werden. Wenn das Ziel bei der Hand ist, um eine Zahl zu wie m und summieren sich alle der Zahlen zwischen ihr und 1, oder umgekehrt zwischen 1 und es behaupte ich, dass ich ausleihen kann diese Idee, dass fusionieren Art hatte, die nahm ein Problem dieser Größe und Dividieren es in etwas kleiner. Vielleicht nicht die Hälfte, aber auch kleinere, aber repräsentativ gleich. Gleiche Idee, aber ein kleineres Problem. Also ich bin eigentlich - lassen Sie mich diese Datei speichern eine andere Versionsnummer. Wir nennen diese Version 1 statt 0. Und ich behaupte, dass ich eigentlich reimplementieren dies in dieser Art von irreen Weg. Ich werde ein Teil davon allein zu lassen. Ich werde sagen, wenn m kleiner als oder gleich 0 - Ich werde einfach ein wenig sein mehr anal diesmal mit meinem Fehlerprüfung - Ich werde weitermachen und 0 zurück. Das ist beliebig. Ich bin einfach nur entscheiden, wenn der Benutzer gibt mir eine negative Zahl, ich bin Rückkehr 0, und sie sollten gelesen die Dokumentation näher. Else - bemerken, was ich tun werde. Else Ich werde m plus zurückkehren - was ist der Sigma-m? Nun, sigma von m plus m minus 1, zzgl. m minus 2 plus minus 3 m. Ich will nicht, all das heraus zu schreiben. Warum ich nicht einfach Kahn? Rekursiv nenne mich mit einem leicht kleineres Problem, Semikolon, und nennen es einen Tag? Right? Nun, auch hier könnte man glauben, oder sich Sorgen dass dies eine Endlosschleife, dass ich induzieren, wobei ich bin der Umsetzung sigma sigma von Berufung. Aber das ist völlig in Ordnung, weil ich Gedanken voraus, die eine zusätzliche Linien? ZUSCHAUER: [unverständlich]. DAVID MALAN: 23 bis 26, die ist mein wenn Bedingung. Denn was ist schön, über die Subtraktion hier, weil ich halten Übergabe sigma kleinere Probleme, kleinere Probleme, kleiner - es ist nicht halb so groß. Es ist nur ein kleiner Schritt Baby, aber das ist OK. Denn schließlich werden wir arbeiten unseren Weg bis zu 1 oder 0 ist. Und wenn wir 0 schlagen, ist sigma nicht gehen, um sich nicht mehr aufrufen. Es wird sofort 0 zurück. Also der Effekt, wenn Sie diese Art von Wind sich in Ihrem Geist, ist es m plus hinzufügen m minus 1 plus minus 2 m sowie m minus 3 plus Punkt, Punkt, Punkt, m minus m, schließlich geben Sie 0 und die Effekt ist letztlich alle hinzufügen diese Dinge zusammen. So haben wir nicht, mit Rekursion löste das Problem, dass wir konnte nicht vor zu lösen. Tatsächlich Version 0 von dieser, und jedes Problem bisher war lösbar mit nur mit for-Schleifen oder während Schleifen oder ähnliche Konstrukte. Aber Rekursion, ich wage zu behaupten, gibt uns eine andere Art des Denkens über Probleme, wobei, wenn wir können eine Problem, teilen Sie es von etwas etwas groß in etwas etwas kleiner, behaupte ich, dass wir es lösen können vielleicht ein wenig mehr elegant in Bezug des Entwurfs, mit weniger Code, und vielleicht sogar Probleme zu lösen, das wäre schwieriger sein, als wir werden schließlich sehen, die Lösung rein iterativ. Aber der Cliffhanger, dass ich wollen uns verlassen auf war. Lassen Sie mich gehen Sie vor und öffnen bis eine Datei aus - tatsächlich, lass mich gehen und tun dies wirklich schnell. Lassen Sie mich gehen Sie vor und schlagen der folgende. Unter heutigen Code ist diese Datei hier. Dieser hier, NOSWAP. Also das ist ein dummes kleines Programm, dass Ich peitschte, dass Ansprüche zu tun der folgende. In main, es zuerst erklärt ein int namens x und ordnet sie der Wert von 1. Dann erklärt sie ein int y und weist sie den Wert 2. Dann druckt, was x und y. Dann sagt er, Tauschen, Punkt Punkt Punkt. Dann behauptet, sein Aufruf einer Funktion Swap genannt, vorbei in x und y, die Idee davon, dass hoffentlich x und y kommen wieder anders, im Gegenteil. Dann behaupten vertauscht! mit einem Ausrufezeichen. Dann druckt x und y. Aber es stellt sich heraus, dass dies sehr einfache Demonstration unten hier ist wirklich buggy. Auch wenn ich über die Vereinbarkeit eines temporären variabel und vorübergehend in ein Putting es, dann bin ich Umwidmung a der Wert von b - das fühlt sich vernünftig, weil ich Gespeicherte eine Kopie in ein Temp. Dann aktualisiere ich b gleich Was auch immer in Temp. Diese Art von Shell Spiel bewegen ein in b und b in eine durch diese Mitte-Mann namens Temp fühlt durchaus sinnvoll. Aber ich behaupten, dass, wenn ich das laufen Code, wie ich jetzt tun - lassen Sie mich gehen Sie vor und fügen Sie ihn hier. Ich rufe diese noswap.c. Und wie der Name schon sagt, ist dies nicht gehen, um eine richtige Programm sein. Machen NOSWAP. / No Swap. x 1 ist, y 2, Tauschen, getauscht. x 1 ist, y 2. Dies ist grundsätzlich falsch, auch obwohl dies scheint perfekt mir vernünftig. Und es gibt einen Grund, aber wir sind nicht gehen, um die Ursache nur noch offenbaren. Denn nun ist die zweite Cliffhanger ich wollte Ihnen überlassen ist, eine Ankündigung von Arten auf Gutscheincodes. Unser Innovation mit späten Tage in diesem Jahr provoziert eine nicht-triviale Zahl von Fragen, die war nicht unsere Absicht. Die Absicht dieser Gutscheincodes wobei wenn du Teil des Problems gesetzt früh, damit immer einen zusätzlichen Tag, war wirklich zu helfen, euch zu helfen Sie beginnen früh, sortieren der durch incentivizing Sie. Hilft uns verteilen Last auf Bürozeiten besser, so dass Es ist eine Art Win-Win. Leider denke ich, meine Anweisungen sind bisher nicht auf dem neuesten Stand, sehr klar, so Ich ging zurück an diesem Wochenende und aktualisiert die Spezifikation in größer, mutiger Text erklären Kugeln wie diese. Und nur um es öffentlich zu sagen, durch Standardmäßig Problem Sets sind aufgrund Donnerstag am Mittag, nach der Lehrplan. Wenn Sie früh beginnen, Finishing Teil das Problem bis Mittwoch um 12:00 Uhr eingestellt PM, der Teil, der einen Coupon betrifft Code, ist die Idee, dass man verlängern Ihre Frist für die P gesetzt, bis Montag. Das heißt, etwas abseits einer winzigen Teil des P gesetzt relativ zu dem, was in der Regel ist die größeres Problem, und Sie kaufen sich einen zusätzlichen Tag. Auch hier wird es Ihnen zu denken das Problem gesetzt, bekommt man zu Bürozeiten früher. Aber der Gutscheincode Problem ist immer noch erforderlich, auch wenn Sie nicht eintragen. Aber mehr zwingend ist dies. (Bühnenflüstern) Und die Leute verlassen Anfang sind gonna es bereuen. Wie sind die Leute auf dem Balkon. Ich im Voraus, um den Leuten zu entschuldigen auf der Balkon aus Gründen, die sein klar in nur einem Augenblick. Also wir haben das Glück, eine haben CS50 ehemaliger Leiter Lehre Fellows eine Firma namens dropbox.com. Sie haben sehr großzügig gespendet ein Gutschein-Code für diese hier viel Platz, was aus der üblichen 2 Gigabyte. Also, was ich dachte, wir würden auf dies zu tun letzte Anmerkung ist zu tun ein bisschen wie ein Werbegeschenk, wobei in nur einem Augenblick werden wir enthüllen, der Gewinner und wer hat einen Gutschein Code, den Sie dann in ihre gehen Website, geben Sie ihn in, und voila, erhalten eine ganze Menge mehr Platz für Ihre Dropbox Gerät und für Ihre persönlichen Dateien. Und zuerst, wer würde gerne teilnehmen in dieser Zeichnung? OK, jetzt, da macht es noch mehr Spaß. Die Person, die diese 25-Gigabyte erhält Gutschein-Code - was bei weitem nicht zwingender als der spät Tage jetzt vielleicht - ist derjenige, der auf der Oberseite sitzt ein Sitzkissen unter denen es dass Gutscheincode. Sie können jetzt unter aussehen Ihre Sitzkissen. [VIDEO PLAYBACK] -Eins, zwei, drei. [SCREAMING] -Sie erhalten ein Auto! Sie erhalten ein Auto! DAVID MALAN: Wir werden sehen Sie am Mittwoch. -Sie erhalten ein Auto! Sie erhalten ein Auto! Sie erhalten ein Auto! Sie erhalten ein Auto! Sie erhalten ein Auto! DAVID MALAN: Balkon Leute kommen hier unten an der Vorderseite, wo wir Extras. -Jeder bekommt ein Auto! Jeder bekommt ein Auto! [END VIDEO PLAYBACK] SPRECHER: Bei der nächsten CS50 - SPEAKER 5: Oh mein Gott Güte Güte Güte Güte Güte Güte Güte Güte Güte - [Ukulele gespielt]