[Musikwiedergabe] 

PROFESSOR: Alles klar. Dies CS50 und dies das Ende der dritten Woche. So sind wir heute hier, nicht in Sanders Theater, statt in Weidner Library. In dessen Inneren sich ein Studio wie Hauser Studio bekannt, oder sagen wir Studio H, oder soll wir sagen--, wenn Sie diesen Witz genossen, es ist eigentlich aus Klassenkamerad, Mark, online, die so viel über Twitter vorgeschlagen. Nun, was ist cool zu wobei hier in einem Studio ist, dass ich durch diese Grünen Wände, einen grünen Bildschirm oder Chroma, so zu sprechen, was, dass das bedeutet, CS50 Produktions-Team, ohne mein Wissen gerade jetzt, könnte setzen mich am meisten auf der ganzen Welt, zum Guten oder zum Schlechten. 

Nun, was vor uns liegt, Problem eingestellt zwei liegt in Ihren Händen für diese Woche, aber mit Problem eingestellt drei in der kommenden Woche, Sie werden mit in Frage gestellt werden die so genannte Spiel von 15, eine alte partybevorzugung, dass Sie erinnern sich vielleicht an Empfangs wie ein Kind, das eine ganze Reihe hat von Zahlen, die gleiten kann nach oben, unten, links und rechts, und es gibt eine Lücke im Puzzle, in dem Sie kann tatsächlich schieben Sie diese Puzzleteile. Letztlich Sie dies erhalten Puzzle in einigen halb zufälliger Reihenfolge, und das Ziel ist, sortieren sie, von oben nach unten, von links nach rechts, von einem den ganzen Weg bis über 15. 

Leider ist die Umsetzung Sie werden bei der Hand haben wird sich Software sein basiert, nicht physisch. Sie tatsächlich zu haben, um zu schreiben Code, mit dem ein Student oder Benutzer Dose spielen das Spiel von 15. Und in der Tat, in den Hacker Ausgabe-Spiel von 15, Sie werden eine Herausforderung, zu implementieren, nicht nur das Abspielen von dieser alten Schule Spiel, sondern die Lösung der es, die Umsetzung Gott-Modus, so zu sprechen, die tatsächlich löst das Rätsel der menschlichen, indem sie sie mit Hinweis, nach dem Hinweis, nach dem Hinweis. Also mehr dazu nächste Woche. Aber das ist, was vor uns liegt. 

Für den Moment erinnern, dass Anfang der Woche wir hatten diese Cliffhanger, wenn man so will, wobei das Beste, was wir taten, Sortier weise war eine obere Schranke von Big O n zum Quadrat. Mit anderen Worten, Bubble-Sort, Selection Sort, Insertion Sort, alle von ihnen, während verschiedene bei der Umsetzung, in ein n übertragen quadriert Lauf Zeit im schlimmsten Fall. Und wir gehen davon aus, dass in der Regel die sehr schlechtesten Fall für die Sortierung ist eine, die Ihre Eingaben vollständig nach hinten. Und in der Tat, es hat durchaus ein paar Schritte auf jeden dieser Algorithmen zu implementieren. 

Jetzt am Ende der Klasse Rückruf verglichen wir Bubble-Sort gegen Auswahl sort gegen einen anderen dass wir aufgerufen merge sort zu der Zeit, und ich schlage vor, dass es unter Vorteil einer Lektion von Woche Null, teile und herrsche. Und irgendwie zu erreichen eine Art von logarithmischer Laufzeit letztendlich, anstatt etwas das ist rein quadratisch. Und es ist nicht ganz logarithmisch, es ist ein bisschen mehr als das. Aber wenn man von der Klasse erinnern, es war viel, viel schneller. Werfen wir einen Blick auf, wo wir aufgehört haben. 

Bubble-Sort gegen Auswahl Art gegen merge sort. Jetzt sind sie alle laufen, in Theoretisch gleichzeitig. Die CPU mit der gleichen Geschwindigkeit läuft. Aber man kann fühlen, wie langweilig diese wird sehr schnell gehen, um zu werden, und wie schnell, wenn wir zu injizieren ein bisschen Woche Null-Algorithmen, können wir Dinge zu beschleunigen. 

So Marke Art sieht toll aus. Wie können wir es nutzen, um Zahlen schneller zu sortieren. Nun lassen Sie uns denken Sie zurück um eine Zutat, die wir musste zurück in Woche null, dass der Suche nach jemandem in einem Telefonbuch, und daran erinnern, dass die Pseudocode, die wir vorgeschlagen, , über die wir finden können jemanden wie Mike Smith, sah ein wenig so etwas wie dieses. 

Nun werfen Sie einen Blick in bestimmten in Zeile 7 und 8 sowie 10 und 11, wonach Schleife induzieren, wobei wir gehalten gehen wieder und wieder zurück zu Zeile 3, und wieder. Aber es stellt sich heraus, dass wir sehen können Dieser Algorithmus, hier in Pseudocode, ein wenig mehr ganzheitlich. In der Tat, was ich suche bei hier auf dem Bildschirm, ist ein Algorithmus zum Suchen Mike Smith bei einigen Reihe von Seiten. Und in der Tat, könnten wir dies zu vereinfachen Algorithmus in den Zeilen 7 und 8, und 10 und 11, nur sagen, dass dies, , die ich hier in gelb dargestellt. In anderen Worten, wenn Mike Smith ist zuvor in dem Buch, wir nicht brauchen, um Schritt angeben Schritt jetzt, wie man sucht ihn. Wir müssen nicht angeben, zurück zu Zeile 3 zu gehen, Warum gehen wir nicht nur statt, sagen, allgemeiner, Suche nach Mike in der linke Hälfte des Buches. 

Umgekehrt, wenn Mike tatsächlich später im Buch, warum machen wir nicht nur zitieren unquote Suche Mike in der rechten Hälfte des Buches. Mit anderen Worten, warum wir nicht einfach Art von Punt, um uns zu sagen, Suche nach Mike in diesem Untergruppe des Buches, und lassen Sie es zu unserem bestehenden Algorithmus, um uns zu sagen, wie man für Mike in suchen dass linke Hälfte des Buches. Mit anderen Worten, unsere Algorithmus arbeitet, ob es ein Telefonbuch von dieser Dicke davon Dicke oder eine beliebige Dicke auch immer. So können wir rekursiv definieren diesen Algorithmus. Mit anderen Worten, auf der Bildschirm hier, ist ein Algorithmus, für die Suche nach Mike Smith zwischen den Seiten eines Telefonbuch. So in Zeile 7 und 10, lassen Sie uns nur sagen, genau das zu. Und ich verwende diesen Begriff ein Moment vor, und in der Tat, Rekursion ist das Schlagwort für jetzt, und es ist dieser Prozess von etwas zyklischen tun, indem irgendwie Verwendung von Code, die Sie bereits haben, und wieder aufrufen, wieder und wieder. Jetzt wird es wichtig sein, dass wir irgendwie unten out und nicht unendlich lang tun. Sonst werden wir zu gehen haben in der Tat eine Endlosschleife. Aber lassen Sie uns sehen, ob wir diese Idee zu leihen einer Rekursion, wieder etwas zu tun und immer wieder zu lösen das Sortierproblem über merge Sortieren, umso effizienter. 

Also gebe ich dir Art zusammenzuführen. Lass uns einen Blick darauf werfen. So, hier ist Pseudocode, mit was wir umsetzen Sortierung, Verwendung dieses Algorithmus namens merge sort. Und es ist ganz einfach dieses. Am Eingang von n Elementen, mit anderen Worten, wenn Sie bei n Elementen und Zahlen und Briefe oder was auch immer der Eingang, wenn Sie n-Elemente, wenn gegeben, n kleiner als 2 ist, nur zurückkehren. Recht? Weil, wenn n kleiner als 2, das heißt bedeutet, dass meine Liste von Elementen entweder der Größe 0 oder 1 und in diesen beiden Fällen trivial, die Liste bereits sortiert. Wenn es keine Liste, es sortiert. Und wenn es eine Liste der Länge 1, es ist offensichtlich sortiert. So der Algorithmus muss nur wirklich etwas Interessantes, wenn wir zwei oder mehr haben, Elemente, die uns gegeben. Also schauen wir uns an die Magie dann. Else sortieren Sie die linke Hälfte der Elemente, Dann sortieren Sie die rechte Hälfte der Elemente, dann verschmelzen die sortierten Hälften. Und was ist eine Art Geist Biegen hier, ist, dass ich nicht wirklich scheinen Sie gesagt haben, alles nur noch, nicht wahr? Alles, was ich gesagt habe, ist, da eine Liste der n Elementen, sortieren Sie die linke Hälfte, dann die rechte Hälfte, dann verschmelzen die sortierten Hälften, aber wo ist der tatsächliche Geheimrezept? Wo ist der Algorithmus? Nun stellt sich heraus, dass diese beiden Linien ersten, sortieren linke Hälfte der Elemente, und Sortier rechten Hälfte der Elemente, sind rekursive Aufrufe, so zu sprechen. 

Denn an diesem Zeitpunkt muss ich ein Algorithmus, mit dem sortieren eine ganze Reihe von Elementen? Ja. Es ist hier richtig. Es ist hier auf dem Bildschirm, und also kann ich die gleiche Satz von Schritten verwenden auf die linke Hälfte zu sortieren, wie ich kann die rechte Hälfte. Und in der Tat, wieder und wieder. So irgendwie, und wir werden in Kürze dies zu sehen, die Magie des Mergesort wird in diesem sehr endgültige eingebettete Linie, die Zusammenführung der sortierten Hälften. Und das scheint recht intuitiv. Sie nehmen zwei Hälften, und du, irgendwie, verschmelzen sie zusammen, und wir werden das sehen konkret in einem Augenblick. 

Aber dies ist eine vollständige Algorithmus. Und lassen Sie uns genau, warum sehen. Nun nehme an, dass wir diese gleichen gegebenen acht Elemente hier auf dem Bildschirm, ein durch acht, aber sie sind in scheinbar zufälliger Reihenfolge. Und das Ziel bei der Hand ist um diese Elemente zu sortieren. Nun, wie kann ich gehen, tun es mit wieder Mergesort, nach dieser Pseudocode? Und wieder, Raufaser dies in Ihren Geist, nur für einen Augenblick. Der erste Fall ist ziemlich trivial, wenn es weniger als 2, nur zurückkehren, gibt es keine Arbeit zu tun. Also eigentlich gibt es nur drei Schritte, um wirklich im Auge zu behalten. Wieder und wieder, ich bin gehen zu wollen, haben auf die linke Hälfte zu sortieren, sortieren Sie die rechte Hälfte, und dann, wenn ihre beiden Hälften werden sortiert, Ich möchte sie miteinander verschmelzen in eine sortierte Liste. So sollte man das im Hinterkopf. 

Also hier ist die ursprüngliche Liste. Lassen Sie behandeln Sie dies als ein Array, als wir begannen, in der zweiten Woche, die eine ist zusammenhängenden Speicherblock. In diesem Fall mit acht Zahlen, Zurück, um zurück zurück. Und lassen Sie uns jetzt merge sort anzuwenden. Deshalb möchte ich zunächst zu sortieren die linke Hälfte dieser Liste, und lassen Sie uns daher konzentrieren sich auf die 4, 8, 6 und 2. 

Nun, wie soll ich mich gehen Sortieren einer Liste von Größe 4? Nun, ich muss jetzt prüfen, Sortieren der links von der linken Hälfte. Auch hier lassen Sie uns Rücklauf nur für einen Augenblick. Wenn die Pseudocode ist dies, und ich bin angesichts acht Elementen, 8 ist offensichtlich grßer als oder gleich 2 ist. Also mit dem ersten Fall keine Anwendung findet. So zu acht Elemente, die ich zuerst zu sortieren, sortieren Sie die linke Hälfte der Elemente, dann habe ich die rechte Hälfte zu sortieren, dann verschmelzen I die beiden sortierten Hälften, die jeweils der Größe 4. OK. 

Aber wenn Sie gerade mir gesagt, sortieren die linke Hälfte, die jetzt von der Größe 4, wie kann ich die linke Hälfte sortieren? Nun, wenn ich eine Eingabe von vier Elementen, Ich zum ersten Mal mit der linken sortieren zwei, dann die zwei rechten, und dann habe ich sie zusammen verschmelzen. Also noch einmal, wird es ein wenig ein Geist Biegen Sie hier, Spiel, weil Sie, Art, müssen erinnern, wo Sie in der Geschichte sind, aber am Ende des Tages, gegeben beliebige Anzahl von Elementen, möchten Sie zuerst die Sortier linke Hälfte, dann die rechte Hälfte, dann verschmelzen sie zusammen. Lassen Sie uns beginnen, um genau das zu tun. Hier ist die Eingabe von acht Elementen. Jetzt sind wir auf der linken Hälfte der Suche hier. Wie kann ich vier Elemente sortieren? Nun, ich zuerst sortieren Sie die linke Hälfte. Nun, wie ich die linke Hälfte sortieren? Nun, ich habe zwei Elemente gegeben. Lassen Sie uns also zu sortieren diese beiden Elemente. 2 grßer oder gleich 2, versteht sich. So dass erste Fall keine Anwendung findet. 

So habe ich nun auf die linke sortieren die Hälfte dieser beiden Elemente. Die linke Hälfte, natürlich, ist nur 4. So, wie ich eine Liste mit einem Element zu sortieren? Nun, dass spezielle Basisfall bis oben, so zu sprechen, gilt. 1 kleiner als 2 ist, und meine Liste ist in der Tat der Größe 1. Also habe ich einfach zurück. Ich weiß gar nichts zu tun. Und in der Tat, bei dem, was ich sehen getan, 4 bereits sortiert. Wie ich schon teilweise erfolgreich hier. 

Jetzt, scheint ziemlich blöd Anspruch, aber es ist wahr. 4 ist eine Liste der Größe 1. Es ist bereits sortiert. Das ist die linke Hälfte. Jetzt habe ich die rechte Hälfte zu sortieren. Ihr Eingang ist ein Element, 8 In ähnlicher Weise bereits sortiert. Dumm auch, aber wieder, Dieses Grundprinzip wird, damit wir jetzt aufbauen Am Anfang dieser erfolgreich. 4 sortiert, 8 wird sortiert, jetzt was war das letzte Schritt? Dabei wird die dritte und letzte Schritt, jedes Zeit, die Sie sortieren bist eine Liste, Rückruf, war, um die beiden Hälften zusammenzuführen, die linke und die rechte. Lassen Sie uns also genau das tun. Meine linke Hälfte ist natürlich, 4. Meine rechte Hälfte ist 8. 

Also lassen Sie uns dies tun. Zuerst werde ich zu vergeben einige zusätzlichen Speicher, dass ich hier zu vertreten, als nur eine sekundäre Array, das ist groß genug, um dies zu passen. Aber können Sie sich vorstellen, die sich dieses Rechteck die gesamte Länge, wenn wir brauchen mehr später. Wie kann ich 4 nehmen und 8, und Zusammenführen diese beiden Listen der Größe 1 zusammen? Auch hier ist ziemlich einfach. 4 kommt zuerst, dann kommt 8. Weil, wenn ich will, um die Sortier linke Hälfte, dann die rechte Hälfte, und dann mischen Sie die beiden Hälften zusammen, in sortierter Reihenfolge, 4 kommt zuerst, dann kommt 8. 

So scheinen wir werden Fortschritte machen, auch aber ich habe keine tatsächliche Arbeit geleistet. Aber denken Sie daran, wo wir in der Geschichte sind. Wir hatten ursprünglich dauerte acht Elementen. Wir sortiert die linke Hälfte, die 4 ist. Dann sortiert man die linke Hälfte der linken Hälfte, die 2 war. Und es geht los. Wir sind mit diesem Schritt getan. 

Wenn wir also nach habe die linke Hälfte von 2, jetzt sind wir müssen die rechte Hälfte von 2 sortieren. Also die rechte Hälfte von 2 ist Diese beiden Werte sind hier, 6 und 2. Also lassen Sie uns nun eine Eingabe von Größe 2, und sortieren Sie die linke Hälfte, und dann die rechte Hälfte, und dann verschmelzen sie zusammen. Nun, wie kann ich eine Liste der Größe zu sortieren 1, die nur die Nummer 6? Ich bin bereits getan. Diese Liste der Größe 1 ist sortiert. 

Wie kann ich eine andere Liste zu sortieren Größe 1, die sogenannte rechte Hälfte. Nun, es ist auch bereits sortiert. Die Nummer 2 ist allein. So, jetzt habe ich zwei Hälften, links und Recht, ich brauche, um sie miteinander zu verschmelzen. Lassen Sie mich etwas mehr Platz gebe mich. Und legte 2 in es, dann 6 in es, wodurch Sortieren Sie diese Liste, links und rechts, und miteinander verschmelzenden es letztlich. So bin ich in etwas besserer Verfassung. Ich bin noch nicht fertig, weil klar 4, 8, 2, 6 nicht die letzte Bestellung, die ich will. Aber ich habe jetzt zwei Listen von Größe 2, dass haben beide jeweils sortiert. So, jetzt, wenn Sie in Ihrem Kopf zu zurückspulen Auge, wo haben, dass uns das? Ich begann mit acht Elementen, dann habe ich schnitzte es auf der linken Hälfte der 4, dann die linke Hälfte von 2, und dann die rechte Hälfte von 2 ist, Ich beendete damit die Sortierung der linken Hälfte 2 und die rechte Hälfte von 2, so was ist der dritte und letzte Schritt hier? Ich muss miteinander verschmelzen zwei Listen der Größe 2. Also lassen Sie uns weitermachen. Und auf dem Bildschirm hier, geben mir etwas zusätzlicher Speicher, obwohl technisch, bemerken, dass ich erhielt eine ganze Reihe von Leerzeichen bis oben Dort. Wenn ich will vor allem sein effiziente Raum weise, Ich konnte einfach in Bewegung der Elemente hin und her, oben und unten. Aber nur für visuelle Klarheit, Ich werde es unten legte, die Dinge schön und sauber zu halten. 

Also habe ich zwei Listen der Größe 2 erhielt. Die erste Liste hat 4 und 8. Die zweite Liste besteht aus 2 und 6. Lassen Sie uns zusammenführen diejenigen, zusammen in sortierter Reihenfolge. 2 natürlich zuerst kommt, dann 4, dann 6, dann 8. Und jetzt scheinen wir bekommen irgendwo interessant. Jetzt habe ich nach der Hälfte der Liste, und zufälligerweise ist es alle geraden Zahlen, sondern dass ist in der Tat nur ein Zufall. Und ich habe jetzt die linke sortiert halb, so dass es 2, 4, 6 und 8. Nichts ist in Ordnung. Das fühlt sich an wie Fortschritte. 

Jetzt fühlt es sich wie ich habe für immer jetzt sprechen, so was noch zu, wenn dies zu sehen Algorithmus ist tatsächlich effizienter. Aber wir durchmachen es super methodisch. Ein Computer natürlich wäre es, das zu tun. Also, wo sind wir? Wir begannen mit acht Elementen. Ich sortierte die linke Hälfte des 4. Ich scheine damit fertig werden. So, jetzt ist der nächste Schritt, um sortieren Sie die rechte Hälfte des 4. Und dieser Teil wir gehen können durch ein wenig mehr schnell, wenn auch du bist Willkommen zu zurückspulen oder Pause, nur denken, durch sie an Ihrem eigenen Tempo, aber was Wir haben jetzt eine Gelegenheit, tun genau das gleiche Algorithmus auf vier unterschiedliche Nummern. 

Also lassen Sie uns gehen Sie vor, und konzentrieren sich auf die rechte Hälfte, die wir hier sind. Die linke Hälfte, dass rechte Hälfte, und jetzt die linke Hälfte des linken die Hälfte dieser rechte Hälfte, und wie kann ich eine Liste der Größe zu sortieren 1 enthält nur die Nummer 1? Ist schon erledigt. Wie kann ich das gleiche für eine Liste zu tun der Größe 1, nur 7 enthalten? Ist schon erledigt. Schritt drei für dieses Halb dann ist, diese beiden Elemente verschmelzen in eine neue Liste von Größe 2, 1 und 7. Scheinen Sie nicht, alles getan haben, dass viel interessante Arbeit. Mal sehen, was als nächstes passiert. Ich habe nach der linken Hälfte des rechte Hälfte meines ursprünglichen Eingang. Lassen Sie uns nun zu sortieren das Recht Hälfte, die 5 und 3 enthält. Versuche es noch auf der linken Seite sehen Hälfte, sortiert, rechte Hälfte, sortiert, und verschmelzen diese beiden zusammen, in etwas zusätzlichen Platz, 3 kommt zuerst, dann kommt 5. Und jetzt haben wir sortiert haben die linke Hälfte der rechten Hälfte des ursprünglichen Problems und die rechte Hälfte der rechten Hälfte des ursprünglichen Problems. Was ist die dritte und letzte Stufe? Nun, diese beiden Hälften miteinander verschmelzen. So möchte ich mich etwas zu bekommen mehr Platz, aber, wieder, ich könnte mit diesem Ersatzraum bis oben. Aber wir halten es einfach visuell. Lassen Sie mich jetzt in 1 zusammenzuführen, und dann 3 und dann 5, dann mit 7. Dabei ließ mich jetzt mit dem rechte Hälfte des ursprünglichen Problems das ist perfekt sortiert. 

Also, was bleibt? Ich fühle mich wie ich immer wieder sagen, die elben Dinge wieder und wieder, aber das ist repräsentativ für die Tatsache, dass wir mit Rekursion. Das Verfahren der Verwendung eines Algorithmus wieder und wieder, auf kleinere Teilmengen das ursprüngliche Problem. So dass ich jetzt eine linke sortiert die Hälfte des ursprünglichen Problems. Ich habe ein Recht sortierten Halb des ursprünglichen Problems. Was ist der dritte und letzte Schritt? Oh, es ist Zusammenführen. Also lassen Sie uns tun. Lassen Sie uns einige zusätzliche zuzuweisen Speicher, aber mein Gott, wir könnte es jetzt überall setzen. Wir haben so viel Platz zur Verfügung zu uns, aber wir werden es einfach halten. Anstatt sich zurück und her mit unserem ursprünglichen Speicher, lassen Sie uns einfach tun optisch nach unten hier unten, zu Ende zu bringen Zusammenlegung der linke Hälfte und die rechte Hälfte. 

So durch die Zusammenführung, was muss ich tun? Ich möchte die Elemente, um zu nehmen. So suchen Sie in der linken Hälfte, Ich sehe die erste Zahl 2. Ich schaue auf die rechte Hälfte, Ich sehe die erste Zahl 1 ist, so offensichtlich die Zahl will ich auszureißen, und an erster Stelle in meinem letzten Liste? Natürlich 1. Jetzt möchte ich die gleiche Frage stellen. Auf der linken Hälfte, habe ich immer noch die Nummer 2. Auf der rechten Hälfte, Ich habe die Nummer 3 bekam. Welcher will ich wählen? Natürlich Nummer 2 und Jetzt bemerken Sie die Kandidaten 4 sind auf der linken Seite, 3 auf der rechten Seite. Lassen Sie uns, natürlich, wählen Sie 3. Jetzt sind die Kandidaten sind 4 auf der linke, 5 auf der rechten Seite. Wir natürlich wählen 4. 6 links, 5 auf der rechten Seite. Wir natürlich wählen 5. 6 links, 7 auf der rechten Seite. Wir wählen 6, und dann werden wir Wählen Sie 7, und dann wählen wir 8. Voila. 

So eine große Anzahl von Wörtern später, haben wir haben diese Liste der acht Elemente sortiert in eine Liste von eins bis acht, dass die zunehmende bei jedem Schritt, aber wie viel Zeit haben es dauern uns, das zu tun. Nun, ich habe absichtlich laid Dinge bildlich Hier, so dass wir Art sehen oder schätzen die Teilung erobern das ist geschehen. 

In der Tat, wenn man sich im Zuge zurückblicken, Ich habe alle diese gestrichelten Linien links in Platzhaltern, können Sie, Art finden, in umgekehrter Reihenfolge, wenn Sie Art von Blick zurück in Geschichte nun, meine ursprünglichen Liste ist natürlich der Größe 8. Und dann zuvor, war ich Umgang mit zwei Listen von Größe 4, und dann vier Listen von Größe 2, und dann acht Listen der Größe 1. 

Was bedeutet dies, Art, erinnern Sie an? Nun, in der Tat, jeder die Algorithmen wir haben sah bisher, wo wir Kluft, und dividieren, und dividieren, halten wieder mit Dingen, und wieder, führt zu diesem allgemeinen Gedanken. Und so gibt es etwas logarithmische hier los ist. Und es ist nicht ganz log n, aber es gibt eine logarithmische Komponente zu dem, was wir gerade getan haben. 

Betrachten wir nun, wie das eigentlich ist. So melden Sie sich von n, war wieder eine tolle Laufzeit, als wir so etwas wie binäre Suche, wie wir jetzt nennen es, die Teile und Herrsche-Strategie , über die wir gefunden Mike Smith. Nun technisch. Das ist log Basis 2 n, auch wenn auch in den meisten Mathematikunterricht, 10 ist in der Regel die Basis, die Sie übernehmen. Aber Informatiker fast immer zu denken und zu sprechen im Hinblick auf die Basis 2, so dass wir in der Regel nur Protokoll sagen n anstelle von log Basis 2 von N, aber sie sind genau ein und die elben in der Welt der Computer Wissenschaft und Nebenbei es gibt einen konstanten Faktor Unterschied zwischen den beiden, so dass es Moot trotzdem, für mehr formalen Gründen. 

Aber für jetzt, was wir kümmern etwa ist dieses Beispiel. Lassen Sie uns also nicht mit gutem Beispiel zu beweisen, aber bei wenigstens einem Beispiel der Nummern bei der Hand als eine Plausibilitätsprüfung, wenn man so will. So zuvor war die Formel log Basis 2 N, aber was n in diesem Fall. Ich hatte n Original-Nummern oder 8 der ursprünglichen Zahl spezifisch. Nun es ist schon ein wenig während, aber ich bin ziemlich Sie sicher, dass Log-Basis 2 des Wertes 8 3, und in der Tat, was ist schön daran ist, daß 3 ist genau die Anzahl von Malen dass Sie eine Liste zu teilen der Länge 8 wieder und wieder, und immer wieder, bis Sie sind links mit Listen von nur Größe 1. Recht? 8 geht bis 4, geht in 2, auf 1 geht, und das ist reflektiert genau das Bild hatten wir eben noch. So ein wenig geistige Gesundheit zu überprüfen, wo der Logarithmus tatsächlich beteiligt. 

So, jetzt ist das, was andere hier beteiligt? n. So bemerken, dass jeder Zeit, die ich teilen die Liste, wenn auch in umgekehrter Reihenfolge in der Geschichte hier war ich noch zu tun n Dinge. Das Vereinigungsschritt erforderlich, dass Ich berühre jede eine der Zahlen, um es in schieben seinen geeigneten Platz. Also auch wenn die Höhe dieses Diagramm der Größe log n von n oder 3, Insbesondere wird in anderen Worten Ich habe drei Divisionen hier. Wie viel Arbeit habe ich horizontal zu tun entlang dieser Tabelle jedes Mal? 

Nun, ich habe n Schritte arbeiten, weil, wenn ich bekam vier Elemente und die vier Elemente, und ich brauche, um sie miteinander zu verschmelzen. Ich brauche, um durch zu gehen diese vier, und diese vier, schließlich, sie zu verschmelzen zurück in acht Elementen. Wenn umgekehrt habe ich acht Finger bekam hier, die ich nicht tun, und acht fingers-- sorry-- wenn ich bekam vier Finger hier, was ich tue, vier Finger hier, was ich tue, dann ist das die gleiche Beispiel wie zuvor, wenn ich es tue haben acht Finger zwar in Gesamt, was ich kann, Art, zu tun. Ich kann hier genau das zu tun, dann kann ich mit Sicherheit Zusammenführen all dieser Listen der Größe 1 zusammen. Aber ich sicherlich zu schauen an jedem Element genau einmal. So dass die Höhe dieses Verfahrens ist log n, die Breite dieses Prozesses sozusagen n ist, so dass das, was wir scheinen zu haben, ist es letztendlich, Laufzeit der Größe n mal log n. 

Mit anderen Worten, teilten wir die Liste, log n-mal, aber jedes Mal, wenn wir das täten, wir hatten jede eines der Elemente zu berühren um sie zu verschmelzen alle zusammen, die wurde Schritt n, also müssen wir das n-fache log n, oder als ein Computerwissenschaftler würden sagen, asymptotisch, die würde das große Wort beschreiben die Ober auf einer Laufzeit gebunden, wir in einem großen o laufen log n Mal so zu sprechen. 

Nun ist dies von Bedeutung, da daran erinnern, was die Laufzeiten waren mit Bubble-Sort, und Auswahl sortieren und Insertion Sort, und sogar ein paar andere, die vorhanden sind, n quadriert war, wo wir waren. Und Sie können, Art, finden Sie diese hier. Wenn n quadriert ist offensichtlich n-mal n, aber hier haben wir n mal log n, und wir von Woche wissen bereits, Null ist, das log n die logarithmische, ist etwas besser als linear. Schließlich erinnern, das Bild mit der roten und der gelben und die grünen Linien, die wir zogen, die grüne logarithmischen Linie war viel geringer. Und daher viel besser und schneller als die geraden gelben und roten Linien, n mal log n ist in der Tat besser als n mal n oder n quadriert. 

So scheinen wir haben identifiziert einen Algorithmus merge Art, die in viel läuft Kürzere Zeit, und in der Tat, das ist, warum, zu Beginn dieser Woche, wenn Wir sahen, dass Wettbewerb zwischen Luftblase Sortieren, Auswahl sortieren und zusammenführen Sortieren, Mergesort wirklich, wirklich gewonnen. Und in der Tat, wir haben nicht einmal warten, für Bubble-Sort und Auswahl sort beenden. 

Werfen wir nun einen weiteren Pass in diesem, von einem etwas mehr formalen Perspektive, nur in Fall schwingt das besser als dieser höheren Ebene diskutiert. Also hier ist der Algorithmus noch einmal. Fragen wir uns, Was die Laufzeit ist dieser Algorithmen verschiedene Schritte? Lassen Sie uns teilen sie in der ersten Gehäuse und das zweite Gehäuse. Der IF und der andere in der ZF-Fall Falls n kleiner als 2 ist, nur zurückkehren. Fühlt konstante Zeit. Es ist, Art von, wie zwei Schritte, Falls n kleiner als 2 ist, dann zurückzukehren. Aber wie wir am Montag sagte, konstante Zeit oder große o von 1, können zwei Schritte, drei sein Schritte, auch 1000 Schritte. Was zählt, ist, dass es eine konstante Anzahl von Schritten. Also die gelb markierten Pseudo Hier läuft, wir nennen es, konstante Zeit. Also mehr formal, und wir zu-- gehende wird das Ausmaß sein, die wir Formalisierung dieses Recht now-- T n, die Laufzeit eines Problems das dauert n Somethings als Eingang, gleich große o von einem, Falls n kleiner als 2 ist. Es ist also davon abhängig, dass. So klar zu sein, falls n kleiner ist 2, haben wir eine sehr kurze Liste, dann die Laufzeit T n, wobei n 1 oder 0 sind, in diesem speziellen Fall, ist es nur geht, um konstante Zeit. Das wird man nehmen Schritt, zwei Schritte, was auch immer. Es ist eine feste Anzahl von Schritten. 

Also die saftigen Teil sicherlich in sein der andere Fall, in dem Pseudocode. Die ELSE Fall. Sortieren linken Hälfte der Elemente, sortieren rechts die Hälfte der Elemente, zusammenführen sortierten Hälften. Wie lange dauert jeder dieser Schritte zu unternehmen? Nun, wenn die Lauf Zeit, um n Elemente zu sortieren ist, nennen wir es sehr generisch, T N, dann die Sortierung der linken Hälfte der Elemente ist, Art von, wie zu sagen, T n durch 2 geteilt, und in ähnlicher Weise die Sortierung der rechten Hälfte von Elementen ist, Art von, wie zu sagen, T n 2 geteilt und dann Zusammenführen der sortierten Hälften. Nun, wenn ich habe einige Anzahl der Elemente hier wie vier, und eine bestimmte Anzahl von Elementen Sie hier, wie vier, und ich habe zu jedem dieser vier zusammenführen in, und jede dieser vier, eins nach dem anderen, so dass schließlich habe ich acht Elementen. Es fühlt sich an wie das ist große o n Schritte? Wenn ich n Fingern und jeder bekam sie muss in Ort zusammengeführt werden, das ist wie ein anderes n Schritte. 

Also ja formelhaft, wir können dies zum Ausdruck bringen, wenn auch ein wenig beängstigend auf den ersten Blick, aber es ist etwas dass fängt genau diese Logik. Die Laufzeit T n, falls n größer als oder gleich 2 ist. In diesem Fall wird der ELSE Fall ist T n geteilt durch 2 plus T von n geteilt durch 2, plus große o n, einige lineare Reihe von Schritten, vielleicht genau n, vielleicht 2 mal n, aber es ist etwa, um von n. So dass auch das ist, wie wir können, Ausdruck dieses formelhaft. Jetzt würden Sie nicht, es sei denn Sie es in Ihrem Kopf aufgenommen haben, oder schauen Sie in die Rücken eines Lehrbuch, dass könnte ein wenig haben Spickzettel am Ende, aber dies ist in der Tat werde geben uns eine große o n log n, weil die Rezidiv DASS Sie hier zu sehen auf dem Bildschirm, wenn Sie tatsächlich tat es aus, mit eine unendliche Anzahl von Beispielen oder Sie können es formelhaft taten, würden Sie sehen, dass dies, weil dieser Formel selbst ist rekursiv, mit t n mehr als etwas auf der rechten Seite, und t n über auf der linken, so kann tatsächlich ausgedrückt werden letztendlich so groß los n log n. Wenn nicht überzeugt, das ist, Geldstrafe für jetzt, nehmen auf den Glauben, dass das ist, ja, was das Wiederauftreten zu, aber das ist nur ein bisschen mehr von einem mathematischen Ansatz zu suchen an der Laufzeit merge sort auf der Grundlage ihrer Pseudo allein. 

Lassen Sie uns jetzt ein bisschen ein Verschnaufpause von all dem, und schauen Sie sich ein bestimmter ehemaliger Senator, der könnte ein wenig bekannt vor, , die sich mit Googles Eric saß Schmidt, vor einiger Zeit für ein Interview auf der Bühne, vor einem ganzen Bündel Menschen letztlich sprechen ein Thema, das ist ziemlich jetzt vertraut. Lass uns einen Blick darauf werfen. 

Eric Schmidt: Jetzt Senator, du bist hier bei Google, und Ich mag an die denken, Präsidentschaft, wie ein Vorstellungsgespräch. Jetzt ist es schwer, einen Job als Präsident zu bekommen. PRÄSIDENT OBAMA: Richtig. Eric Schmidt: Und du bist jetzt tun [unverständlich]. Es ist auch schwer, einen Job bei Google zu bekommen. PRÄSIDENT OBAMA: Richtig. 

Eric Schmidt: Wir haben Fragen, und wir bitten unsere Kandidaten Fragen, und dieses ist von Larry Schwimmer. 

PRÄSIDENT OBAMA: OK. 

Eric Schmidt: Was? Ihr Jungs denken, ich bin verrückt? Es ist hier richtig. Was ist die effizienteste Art, sortieren eine Million 32-Bit-Ganzzahlen? 

PRÄSIDENT OBAMA: Well-- Eric Schmidt: Manchmal vielleicht tut mir leid, maybe-- PRÄSIDENT OBAMA: Nein, nein, nein, nein, nein, ich think-- Eric Schmidt: Das ist nicht es-- PRÄSIDENT OBAMA: I denke, denke ich, die Blase Art wäre der falsche Weg zu gehen. Eric Schmidt: Komm schon. Die ihm das gesagt? OK. Ich hatte nicht den Computerwissenschaften an-- 

PRÄSIDENT OBAMA: Wir haben haben unsere Spione dort. PROFESSOR: Alles klar. Lassen Sie uns hinter uns lassen jetzt die theoretische Welt der Algorithmen in der asymptotischen Analysis , sowie auf einige Themen zurück von Woche Null und Eins und Start einige Stützräder zu entfernen, wenn du möchtest. So dass Sie wirklich verstehen, schließlich von Grund auf, was ist geht unter der Haube, wenn Sie Schreiben, Kompilieren und Ausführen von Programmen. Daran erinnern, insbesondere, dass dies die erste C-Programm sahen wir uns an, eine kanonische, einfaches Programm von Art, relativ gesehen, wobei, er druckt, Hallo Welt. Und daran erinnern, dass ich gesagt habe, das Verfahren dass Quellcode durchläuft Genau diese. Sie übernehmen Ihr Quellcode, übergeben sie durch einen Compiler, wie Clang, und heraus kommt Objekt-Code, dass könnte wie folgt, Nullen und Einsen zu suchen dass die CPU des Computers, Zentral Verarbeitungseinheit oder des Gehirns, letztendlich versteht. 

Es stellt sich heraus, daß das ein wenig eine zu starke Vereinfachung, dass wir jetzt in eine Stellung auseinander zu necken um zu verstehen, was wirklich war geht unter der Haube jedes Mal wenn Sie laufen Klappern oder allgemeiner, jedes Mal, wenn Sie ein Programm zu machen, mit Make und CF-50 IDE. Insbesondere solche Sachen wird diese zunächst erzeugt wird, wenn Sie zuerst Ihr Programm kompilieren. Mit anderen Worten, wenn man nehmen Sie Ihre Source-Code und kompilieren Sie es, was ist zuerst von Clang ausgegeben ist etwas, als Assembler-Code bekannt. Und in der Tat sieht es genau so. 

Ich lief ein Befehl an die Befehlszeile früher. Clang dash Kapital s hello.c, und dies erzeugt eine Datei für mich genannt hello.s, innerhalb dessen waren genau diese Inhalte, und ein wenig mehr oberhalb und etwas unterhalb, aber ich habe die saftigsten setzen Informationen hier auf dem Bildschirm. Und wenn Sie genau hinsehen, werden Sie sehen, zumindest ein paar vertraute Keywords. Wir haben Haupt oben. Wir haben in der Mitte printf. Und wir haben auch hallo Welt Backslash n in Anführungszeichen unten. 

Und alles andere hier ist sehr gering Anleitungen Level daß die CPU des Computers versteht. CPU-Anweisungen, die Speicher zu verschieben um, dass Last Strings aus dem Speicher, und schließlich, drucken Dinge auf dem Bildschirm. Nun, was passiert, wenn nach Dieses Assemblercode generiert? Letztlich, die Sie tun, in der Tat, noch generieren Objektcode. Aber die Schritte, die wirklich nun schon unter der Haube schauen ein wenig mehr davon. Quellcode wird Assembler-Code, die dann zur Objektcode, und hier die operative Worte sind, dass, wenn Sie Ihren Quellcode zu kompilieren, heraus kommt Assembler-Code, und dann wenn Sie Ihren Assembler-Code zusammenzubauen, heraus kommt Objektcode. 

Jetzt Clang ist super anspruchsvoll, wie eine Menge von Compilern, und alle diese Schritte tut, zusammen, und es ist nicht notwendigerweise Ausgangs jede Zwischen Dateien, die Sie auch sehen können. Es kompiliert nur Dinge, Das ist der allgemeine Begriff, beschreibt diesen gesamten Prozess. Aber wenn Sie wirklich wollen, Insbesondere ist, da ist viel mehr los dort. 

Aber lassen Sie uns auch überlegen nun, dass auch dass Super einfaches Programm, hello.c, heißt Funktion. Es fordert printf. Aber ich wollte nicht schreiben, printf, ja, das kommt mit c, so zu sprechen. Es ist eine Funktion, die Rückrufaktion ist in Standard io.h erklärte die eine Header-Datei, die ist ein Thema werden wir tatsächlich tauchen Sie ein in mehr Tiefe, bevor lang. Aber eine Header-Datei ist in der Regel begleitet durch einen Code-Datei Quellcode-Datei, so dass ähnlich wie es existiert Standard io.h 

Vor einiger Zeit, jemanden, oder someones, schrieb auch eine Datei namens Standard io.c, in die den eigentlichen Definitionen, oder Implementierungen von printf, und Trauben von anderen Funktionen, tatsächlich geschrieben. So daß bei, wenn man bedenkt, mit hier auf der linken Seite, hallo.c, dass, wenn kompiliert, gibt uns hello.s, auch wenn Clang nicht Einsparung an einem Ort, die Mühe wir können es sehen, und das Assembler-Code erhält in hello.o, montiert die ist in der Tat der Standardname gegeben, wenn Sie Quellcode zu kompilieren Code in Objektcode, sind aber nicht ganz bereit, es noch nicht ausführen, weil weiteren Schritt zu geschehen hat, und hat wurde für die letzten paar geschieht Wochen, vielleicht unbemerkt von Ihnen. 

Insbesondere irgendwo in CS50 IDE, und dies Auch wird ein bisschen eine sein Vereinfachung für einen Moment, gibt es, oder war eine Zeit, eine Datei namens Standard io.c, dass jemand in kompilierte Standard io.s oder den Gegenwert, dass jemand dann zusammengebaut in Standard-io.o, oder es stellt sich heraus in einen etwas andere Datei Format, das eine andere haben kann, Dateierweiterung zusammen, aber in der Theorie und konzeptionell genau jene Schritte in irgendeiner Form geschehen. Was bedeutet, dass nun wenn ich ein Programm schreiben, hello.c, dass, nur sagt: Hallo Welt, und ich bin mit Code jemand anderes wie printf, die einst eine war Zeit, in einer Datei namens Standard io.c, dann irgendwie muss ich meine zu nehmen Objektcode, mein Nullen und Einsen, und diese Person die Aufgabe Code oder Nullen und Einsen, und irgendwie miteinander zu verknüpfen eine letzte Datei namens hallo, daß hat alle Nullen und diejenigen aus meinem Hauptfunktion, und alle Nullen und diejenigen für printf. 

Und in der Tat ist, dass letzte Prozess genannt, die Verknüpfung Ihrer Objektcode. Dessen Ausgangs ist eine ausführbare Datei. So in Fairness, bei der am Ende des Tages, nichts seit einer Woche verändert, als wir anfing Kompilieren von Programmen. Zwar all dies wurde geschieht unter der Haube, aber jetzt sind wir in der Lage sind wo wir können tatsächlich necken auseinander diese verschiedenen Schritte. Und in der Tat am Ende des Tages, sind wir immer noch links mit Nullen und Einsen, die ist eigentlich ein großer segue jetzt zu einer anderen Funktion von C, das wir haben nicht sehr wahrscheinlich nutzen musste auf dem neuesten Stand, wie Bit-Operatoren bekannt. Mit anderen Worten, die bisher, zu jeder Zeit wir haben mit Daten, die in C oder Variablen C behandelt, wir haben Dinge wie gehabt Zeichen und schwimmt ins und sehnt sich und Doppelzimmer und dergleichen, aber all das sind mindestens acht Bits. Wir haben noch nie in der Lage sein Manipulation einzelner Bits, obwohl eines einzelnen Bits, die wir wissen, kann eine 0 und 1 repräsentieren. Jetzt stellt sich heraus, dass in C, die Sie kann der Zugriff auf einzelne Bits zu erhalten, wenn Sie wissen, die Syntax, , mit denen, um an sie heranzukommen. 

Werfen wir also einen Blick bei Bit-Operatoren. Also hier abgebildet sind ein paar Symbole, wir haben, Art, Art, gesehen. Ich sehe ein Und-Zeichen, eine vertikale bar, und einige andere als gut, und daran erinnern, dass die Kaufmanns-Und-Zeichen ist etwas, was wir gesehen haben. Die logische UND-Operator, wo Sie zwei von ihnen zusammen, oder die logische ODER Betreiber, in dem Sie habe zwei vertikale Balken. Bit-Operatoren, auf die wir siehe arbeiten auf Bits einzeln, nur ein einzelnes und-Zeichen zu verwenden, ein Einzel vertikalen Balken, der Caret-Zeichen als Nächstes kommt, den kleinen Tilde, und dann nach links Halter links Halter oder rechte Klammer rechte Klammer. Jedes von diesen unterschiedliche Bedeutungen haben. 

In der Tat, lassen Sie uns einen Blick. Lassen Sie uns gehen alte Schule heute und Verwendung ein Touch-Screen aus vergangenen Zeiten, wie eine weiße Tafel bekannt. Und das weiße Tafel wird uns erlauben, einige ziemlich einfache Symbole zum Ausdruck bringen, oder vielmehr einige recht einfache Formeln, dass wir dann letztendlich Hebelwirkung, um für den Zugriff auf einzelne Bits innerhalb eines C-Programms. Mit anderen Worten, lassen Sie uns dies tun. Sprechen wir zuerst für ein Moment über Und-Zeichen, das ist die bitweise UND-Operator. In anderen Worten, dies ist ein Operator, der erlaubt mir, eine linke Variable haben Typischerweise und eine rechte Variable oder ein einzelner Wert, dass, wenn wir UND sie zusammen, gibt mir ein Endergebnis. Also, was ich meine? Wenn in einem Programm, eine Variable müssen Sie daß speichert einen dieser Werte, oder lassen Sie es einfach halten und nur schreiben, Nullen und Einsen einzeln, hier ist, wie das kaufmännische Bediener arbeitet. 0 0 Ampersand wird zu 0 gleich. Nun, warum ist das so? 

Es ist sehr ähnlich, Boolesche Ausdrücke, dass wir bisher diskutiert. Wenn Sie nach dem alle denken, das 0 ist false 0 false false false ist, wie wir besprochen haben logischerweise auch falsch. So bekommen wir hier 0 als auch. Wenn Sie eine 0 Und-Zeichen 1, und das auch, wird auf 0 gesetzt, weil hierfür linke Ausdruck wahr oder 1 ist, es müsste wahre und wahr zu sein. Aber hier haben wir falsch und wahr oder 0 und 1. Jetzt wieder, wenn wir 1 Und-Zeichen 0, das auch, wird zu 0, und wenn wir ein kaufmännisches Und-Zeichen 1, schließlich haben wir ein 1-Bit. Also mit anderen Worten, wir nicht tun, etwas Interessantes mit diesem Operator nur noch, diese kaufmännisches Und-Operator. Es ist die bitweise UND-Operator. Aber das sind die Zutaten , über die wir tun können, interessante Dinge, wie wir bald sehen werden. 

Jetzt schauen wir uns nur den Einzel Senkrechte Striche hier auf der rechten Seite. Wenn ich eine 0-Bit und ich Oder er mit, die bitweise OR-Operator, ein weiterer 0-Bit, das wird mir 0 zu geben. Wenn ich ein 0-Bit und OR mit zu nehmen ein 1-Bit, dann werde ich auf 1 zu bekommen. Und in der Tat, nur für Klarheit, lass mich gehen zurück, so dass meine vertikalen Balken sind nicht für 1 irrt. Lassen Sie mich alles neu schreiben mein 1 ist ein wenig mehr klar, so dass wir weiter sehen, wenn ich haben eine 1 oder 0, das wird eine 1, und wenn ich eine 1 oder 1, die, Auch wird eine 1 sein. So können Sie logisch, dass die OR sehen Operator verhält sich ganz anders. Das gibt mir 0 oder 0 gibt mir 0, aber jede andere Kombination gibt mir 1. Solange ich eine 1 in das haben Formel, wird das Ergebnis würde 1 sein. 

Im Gegensatz zu dem UND Betreiber, das Und-Zeichen, nur wenn ich zwei 1 in der Gleichung, ich tatsächlich eine 1 aus. Jetzt gibt es ein paar andere Betreiber als auch. Einer von ihnen ist ein wenig komplizierter. Also lassen Sie mich gehen Sie vor und löschen dies etwas Platz. Und lassen Sie uns einen Blick auf die Caret-Zeichen, nur für einen Augenblick. Dies ist typischerweise ein Zeichen, das Sie eingeben können auf Ihrer Tastatur die Umschalttaste gedrückt halten und dann eine der Zahlen oben auf Ihrer US Tastatur. 

Das ist also die ausschließliche OR-Operator, Exklusiv-ODER. So sahen wir nur den OR-Operator. Dies ist der Exklusiv-Oder-Operator. Was ist eigentlich der Unterschied? Nun lassen Sie uns einfach an der Formel zu suchen, und dies als Zutaten letztendlich. 0 XOR 0. Ich werde sagen, ist immer 0. Das ist die Definition von XOR. 0 XOR 1 wird zu 1 sein. 1 XOR 0 wird zu 1 sein, und 1 XOR 1 sein wird? Wrong? Oder rechts? Ich weiß es nicht. 0. Nun, was ist denn hier los? Nun denken Sie an die Name des Bedieners. Exklusiv-ODER, um die Name, Art der schlägt, die Antwort ist nur zu sein, a 1, wenn die Eingänge sind exklusiv, exklusiv anders. Also hier die Eingänge sind die gleich, so ist der Ausgang 0. Hier sind die Eingänge der gleich, so ist der Ausgang 0. Hier sind die Ausgänge sind anders, sie sind exklusiv, und so ist der Ausgang 1. So ist es sehr ähnlich Und, es ist sehr ähnlich, oder besser gesagt, es ist sehr ähnlich, OR, aber nur in einem exklusiven Art und Weise. Dieses ist nicht mehr a 1, weil wir zwei 1 ist, und nicht ausschließlich, nur einer von ihnen. Gut. Was ist mit den anderen? Nun die Tilde, mittlerweile ist wirklich schön und einfach, Gott sei Dank. Und das ist ein unärer Betreiber, was bedeutet, es ist nur einen Eingang angelegt wird, einen Operanden, so zu sprechen. Nicht an einer linken und einer rechten Seite. Mit anderen Worten, wenn Sie Tilde nehmen 0, wird die Antwort das Gegenteil sein. Und wenn Sie Tilde von 1 zu nehmen, die Antwort wird es umgekehrt sein. So ist die Tilde-Betreiber ein Weg der Negation ein bisschen, oder Spiegeln ein wenig von 0-1 oder 1-0. 

Und das lässt uns endlich mit nur zwei Abschlussbetreiber, die sogenannte Linksverschiebung und sogenannte rechte Shift-Operator. Werfen wir einen Blick auf, wie diese Arbeit. Die linke Shift-Operator, geschrieben mit zwei spitzen Klammern so, arbeitet wie folgt. Wenn meine Eingangs oder mein Operanden nach links Verschiebungs-Operator ist ganz einfach ein 1. Und ich sage dann den Computer an Verschiebung nach links, dass 1, sagen sieben Plätze, das Ergebnis ist, als ob ich nehmen, dass 1, und verschieben Sie sie sieben Stellen über den die links, und standardmäßig, werden wir davon ausgehen, dass der Raum auf der rechten wird sich mit Nullen aufgefüllt werden. Mit anderen Worten, ein Linksverschiebung 7 wird mir zu geben, dass 1, gefolgt von 1, 2, 3, 4, 5, 6, 7 Nullen. Dies in einer Weise, ermöglicht es Ihnen, nehmen Sie eine kleine Zahl wie 1, und deutlich machen es viel wesentlich, so viel größer, aber wir sind eigentlich vor sich geht, um zu sehen gescheiter Ansätze für die es statt, als auch, 

Gut. Das war es für drei Wochen. Wir werden Sie sehen, das nächste Mal. Dies war CS50. 

[Musikwiedergabe] 

Sprecher 1: Er war in der Snack- Bar Essen ein Eisbecher. Er hatte alles über sein Gesicht. Er trägt, dass Schokolade wie ein Bart Sprecher 2: Was machst du? SPEAKER 3: Hmmm? Was? 

Sprecher 2: Haben Sie gerade Double Dip? Sie tauchte den doppelten Chip. SPEAKER 3: Entschuldigung. Sprecher 2: Sie tauchten den Chips, die Sie nahm einen Bissen, und du wieder getaucht. SPEAKER 3: Sprecher 2: Also das ist, wie wenn man Ihren ganzen Mund direkt im dip. Sie das nächste Mal einen Chip zu nehmen, nur tauchen sie einmal, und beenden Sie ihn. 

SPEAKER 3: Weißt du was, Dan? Sie tauchen die Art und Weise, die Sie eintauchen möchten. Ich werde die Art und Weise, die ich will, um dip dip.