>> [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!
>> 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]