[Musik spielt] 

DAVID J. MALAN: Alles klar. Also zurück zu begrüßen. Dies ist CS50 und das ist das Ende der dritten Woche. 

So in den vergangenen Wochen erinnern, wir haben die Ausgaben ziemlich viel Zeit auf C, über die Programmierung, auf Syntax. Und es ist ganz normal, wenn Sie immer noch kämpfen mit Problem Set 2 zu sein Mit dem Kopf gegen die Wand. Es ist kryptisch aussehende Fehlermeldungen und Fehler, die Sie kann nicht ganz jagen. Denn, seien Sie versichert, dass in nur einem wenigen Wochen werden Sie blicken zurück auf Dinge wie Caesar, und [? V-Genair,?] vielleicht sogar Knacken und erkennen, wie weit Sie gekommen sind in einem kurzen Zeitraum. Also, wenn das ein Trost ist, hängen dort jetzt. 

Heute jedoch, beginnen wir, den Übergang Dinge zu höheren Niveau. Und wir beginnen, für selbstverständlich halten, dass Sie Jungs wissen, wie man programmiert, oder zumindest die Anfänge dass Komfort. Und wir beginnen zu überlegen, wie wir gehen über die Gestaltung von Programmen mehr effektiv. Wie können wir über die Optimierung unterwegs Effizienz unserer Algorithmen und Regel Lösung mehr interessante Probleme. Und ab zu nehmen für selbstverständlich, dass, wenn wir wollten, könnten wir codieren bis jede der Beispiele, die wir im Auge haben. Also heute haben wir nicht die Tastatur berühren für jede Form von Code. Es wird viel höheren Niveau zu sein, und letztlich über Problemlösung. 

Also, um zu diesem Punkt zu gelangen, lassen Sie mich schlagen daß die folgenden sieben Rechtecke stellen sieben Türen, hinter das sind eine ganze Reihe von Zahlen, von denen ist die Nummer 50. Lassen Sie mich zu projizieren diese auf diese Bildschirm auch hier. Und schlagen vor, dass wir einen Freiwilligen brauchen helfen, mir eine Zahl vor das Internet hier zu sehen. Komm up, in dem rosa. In Ordnung. Wie ist dein Name? 

JENNIFER: [unverständlich] 

DAVID J. MALAN: Wie bitte? 

JENNIFER: Jennifer. 

DAVID J. MALAN: Jennifer. Alles klar, Jennifer. Schön, Sie kennen zu lernen. Komm up. Also diese hier sind sieben Türen, und was Ich möchte, dass du für uns hier zu tun, vor alle Ihre Klassenkameraden, wird uns finden Sie die Nummer 50. Um eine Zahl zu finden, können Sie einen Blick hinter jeder dieser Türen durch einfaches Antippen auf eine der Türen, und wird ihre Zahl zu offenbaren. Und lassen Sie uns sehen, wie schnell Sie So finden Sie uns die Anzahl, 50. 

15. 16. 50. Schön gemacht. In Ordnung. Applaus für Jennifer. 

[Applaus] 

In Ordnung. Also, was war Ihre Strategie für Finden Sie die Nummer 50? 

JENNIFER: Äh, ich dachte, vielleicht, wenn - [Unverständlich] 

DAVID J. MALAN: Oh. Geben Sie ihm eine Sekunde. So war Ihre Strategie für Finden Sie die Nummer 50? 

JENNIFER: Also ich erst am Anfang beginnen, um zu sehen, was die erste Zahl war, und dann dachte ich, vielleicht, wenn sie sortiert sind, werde ich einfach weiter Klopfen höher? 

DAVID J. MALAN: OK. Und wir scheinen gefunden zu haben dass der Fall zu sein. Obwohl wir schälen die Schichten nur ein wenig, und Sie gehen wollen vor und zeigen die anderen Türen könnten Sie gewählt haben? 

JENNIFER: Oh, mein Lieber. 

DAVID J. MALAN: Ah. 

JENNIFER: Also ich einfach nur Glück. 

DAVID J. MALAN: So haben Sie Glück. In Ordnung. Also nicht schlecht. Aber das ist eine interessante Einsicht, nicht wahr? Wenn Sie angenommen, und du hast bekommen, in der Tat, ein bisschen Glück gibt. Aber wenn man davon ausgegangen, dass die Zahlen waren sortiert, können Sie genauere , wie beeinflusst, dass Ihr Verhalten? 

JENNIFER: Also, wenn sie sortiert wurden, habe ich dachte, vielleicht kleinsten bis zum größten. 

DAVID J. MALAN: OK. 

JENNIFER: Oder wenn dies endete als wirklich groß, dann größten bis zum kleinsten. 

DAVID J. MALAN: OK. So der größten zur kleinsten, oder kleinsten zum größten. Aber lassen Sie mich schlagen, nehme an, Sie hatten Pech bekommen, und nehme an, dass sie wurden in der Tat nicht, sortiert, wie viele diese Türen können Sie mussten peek hinter in diesem schlimmsten Fall? 

JENNIFER: Alle von ihnen. 

DAVID J. MALAN: Alle von ihnen. Also lasst verallgemeinern, dass n. Es geschieht bis 7 sein, aber wir mehr im Allgemeinen sagen, es gibt n die Türen auf Bildschirm hier. Also im schlimmsten Fall, müsste man 7, hinter Türen oder n Türen schauen. Und so ist wirklich, es ist ein bisschen von Glück heute, aber es ist wirklich eine lineare Algorithmus der Art, obwohl Sie waren irgendwie übersprungen herum. Ist das fair? 

JENNIFER: Ja. 

DAVID J. MALAN: Nun, lassen Sie mich sehen, ob Ihr Strategie ändert sich, wenn ich uns zu bewegen Unser zweites Beispiel hier mit 7 verschiedene Türen. Gleiche Zahlen, aber diese Zeit, die sie sortiert werden. Was ist Ihre Strategie hier sein wird, versuchen, legte aus dem Kopf, was die anderen Zahlen waren - 

JENNIFER: OK. 

DAVID J. MALAN: - früher? 

JENNIFER: Beginnen wir mit dem ersten. 

DAVID J. MALAN: Alles klar. Beginnen Sie mit dem ersten. 4. Jetzt, wo du gehen, und warum? 

JENNIFER: 4 ist wirklich klein. Also, wenn sie sind vielleicht kleinste Art bis zum größten, sollte es doppelt so groß, und -. 

DAVID J. MALAN: OK. Mal sehen, was Sie denken? 

JENNIFER: Probieren Sie die letzte. Nizza. 

DAVID J. MALAN: Sehr schön gemacht. In Ordnung. 

[Applaus] 

DAVID J. MALAN: OK. Sie sind also tatsächlich tun dies schrecklich, weil man tut es sehr gut. Was uns nicht machen bestimmte Punkte. So wollen wir versuchen, ein Rollback hier. 

JENNIFER: OK. 

DAVID J. MALAN: Sehr gut getan, dennoch. So begann am Anfang, Sie sah, dass es 4 war, dann bewegt bis zum Ende. Aber nehmen Sie nicht das Glück dort, und nehme 50 war woanders. Was Ihre dritte Schritt gewesen sein? 

JENNIFER: Zurück an den Anfang. 

DAVID J. MALAN: Zurück an den Anfang. OK, so würden Sie berührt haben diese Tür, die 8 war. In Ordnung. Also das ist nicht 50. Wo würden Sie schaute nächste sein? 

JENNIFER: Wenn ich nicht wissen, dass sie sortiert. 

DAVID J. MALAN: Richtig. Nun, wenn Sie wissen, hat wurden sie sortiert - 

JENNIFER: Oh, wusste, ja. 

DAVID J. MALAN: - aber du hast nicht wissen, wo 50 war noch? 

JENNIFER: Just keep going. 

DAVID J. MALAN: Alles klar. OK. Keep going. OK, dass ich arbeiten kann. 

JENNIFER: OK. 

DAVID J. MALAN: Nun, wenn Sie nur gehen, um weiterzumachen, was ist Ihre Algorithmus Dezentralisierung in gesichert. 

JENNIFER: Das linear -. 

DAVID J. MALAN: Es ist eine Art linear. Aber lassen Sie mich schlagen, lassen mich setzen auf der Stelle. Lassen Sie mich die Seite aktualisieren. gleiche Anzahl, gleiche Anordnung, gleichen Türen. Aber denken Sie zurück an diesem ersten Tag in Klasse, wenn wir ein Telefonbuch zerriss in halb, irgendwie, und was war unsere Strategie gibt? 

JENNIFER: Beginnen Sie an der Mitte. 

DAVID J. MALAN: OK. So in der Mitte starten. Also lassen Sie uns fortfahren und zu simulieren, dass. Beginnen Sie an der Mitte durch enthüllt die Tür. So stieg die Zahl 16. So was wäre der starke Mann getan haben, die rissen das Telefonbuch in der Hälfte, , um zur nächsten Vermutung bekommen? 

JENNIFER: Gehe hin in dieser Hälfte. 

DAVID J. MALAN: Und warum auf der rechten Seite? 

JENNIFER: Wenn sie eine Art kleinsten bis zum größten, dann 50 sein sollte an diesem Ende. 

DAVID J. MALAN: Good. Völlig vernünftig. So wie ein Telefonbuch, das Sie gehen rechts nach links entgegengesetzt, aber hier ist der Schlüssel zum Mitnehmen. Sie können jetzt wegwerfen, oder abreißen, Hälfte dieses Problem, so dass Sie nicht mit 7 Türen, aber wirklich mit nur 3. Welches ist etwa die Hälfte der Größe des Problems. In Ordnung. So, jetzt das, was man haben getan, nachdem Sie rechts gehen? 

JENNIFER: So 16 ist immer noch ziemlich klein, bezogen auf 50, vielleicht werde ich versuchen, wie, dieser. 

DAVID J. MALAN: Alles klar. 42. Alles klar, also jetzt, was ist Ihre Instinkt sage? 

JENNIFER: Ich kann wegwerfen dies und dann einfach - 

DAVID J. MALAN: OK. Gut, können Sie wegwerfen die linke Hälfte da. 

JENNIFER: - Pick this one. 

DAVID J. MALAN: Und das Recht. 

JENNIFER: Ja. 

DAVID J. MALAN: Also auch wenn es schwer um vielleicht zu sehen, wenn es nur 7 Türen, darüber nachzudenken, jetzt, Die Konsistenz des Algorithmus, den Sie gerade angelegt. In dem vorherigen Fall, haben Sie Glück, das war toll. Aber du hast mit einem heuristischen, Würde ich sagen. Sie verwendeten Art von Ihren Instinkten und es zu wissen, sortiert, wenn sie hübsch ist am Anfang klein, natürlich, wir haben musst mehr nach rechts gehen. Aber in einem gewissen Sinne, du hast Glück, weil vielleicht war die Zahl 100, und vielleicht 50 war mehr in der Mitte. Vielleicht 50 war sogar hier. 

Aber was du getan hast ein wenig anders dieses Mal war, hast du die gleiche Sache wieder und wieder. Und ich würde behaupten, dass das, was Sie gerade hat, wenn auch durch das Telefon beeinflusst Buch ist beispielsweise etwas viel mehr algorithmischen und viel weniger spezielle verkleidet. Viel weniger instinktiv. Also am Ende des Tages, wie würde Sie beschreiben die Effizienz der ersten Algorithmus, wo Sie ging von links nach rechts, gegen die zweite Algorithmus hier? 

JENNIFER: Das sollte man, wie, vielleicht Halbierung der Zeit, oder sogar noch mehr, ja. 

DAVID J. MALAN: OK, vielleicht sogar mehr. Lassen Sie schieben ein wenig härter auf die. Was wirklich, wenn wir dies auch weiterhin Logik, wir definitiv halbiert die Laufzeit mit diesem zweiten Algorithmus durch Wegwerfen Hälfte der Zahlen, aber was wir tun, auf der nächsten Iteration, wenn Jennifer enthüllt die zweite Zahl? 

Wir halbieren die Zahl der Türen wieder. Und dann, was haben wir getan, dass nach, wenn gab es mehrere Türen, um mit zu spielen? Wir würden halbieren, und wieder, und wieder, und wieder. Und das war genau wie euch alle Stehen bei der ersten Woche Klasse, die Hälfte von euch sitzen, halb der Sie sitzen, die Hälfte von euch Hinsetzen, bis ein einsamer Seele stand. Und wir sagten, dass die Laufzeit der Damit war die Anzahl der Schritte, es dauerte in der Größenordnung dessen, was? 

Sprecher 1: [unverständlich] 

DAVID J. MALAN: So log Basis 2 n, oder einfach nur einfacher, von n einloggen. So etwas logarithmisch. Und die Kurve nicht eine gerade Linie dass nur noch schlimmer und schlimmer, es war diese interessante Kurve, die nicht bekommen so schlecht über die Zeit. Lassen Sie uns also an dieser Idee halten. Lasst uns danken Jennifer. Vielen Dank für Ihr Kommen etwas. Und eine Sekunde. Keine Schreibtischlampen heute, aber wir Sie haben CS50 Stress-Bälle. 

JENNIFER: Yay. 

DAVID J. MALAN: All right, hier. Danke für die Entstehung der der Stress hier. In Ordnung. Also lasst uns sehen, ob wir nicht jetzt formalisieren diese ein bisschen mehr. Also noch einmal, war das, was wir gerade getan im Wesentlichen das Gleiche wie wir in dieser ersten Woche. Aber anstatt Ende mit nur ein lineares Algorithmus, die wir dargestellt früher als dieser Geraden, wobei, wenn wir eine weitere Tür zu setzen auf der Bildschirm, dann würde Jennifer mussten schauen, potentiell, hinter eine weitere Tür. Wenn wir zwei weitere Türen setzen, könnte sie haben zu schauen hinter zwei Türen mehr. 

Und so gab es diese lineare Beziehung zwischen der Größe der Problem auf, sagen wir, der x-Achse und die Menge an Zeit, die zum Lösung auf der y. Aber das Bild, das ich bis Anspielung wurde früher war diese grüne Linie. Grün bewusst, weil es fühlte sich besser. In der Theorie, den Algorithmus, wenn wir es getan haben mit dem Telefonbuch, wenn wir es getan haben mit euch zählen einander, und im zweiten Fall, wenn nur Jennifer tat es hier oben, war es irgendwie grundlegend besser. Denn es war nicht nur doppelt so schnell. Es war nicht sogar viermal so schnell. Es war völlig davon abhängig, was die Größe der Eingabe war, wie viele Schritte, die sie letztlich nahm. 

Und so einfache Idee, dass wir alle nahmen selbstverständlich mit dem Telefonbuch, in ähnlicher Weise angewendet werden, so etwas wie dies. Und dies könnte eher beiläufig sein bekannt als, wie Sie vielleicht vorstellen, teile und herrsche. Nicht anders als das, was wir taten, natürlich, mit dem Telefonbuch. 

Aber der Pseudocode, Rückruf, war diese. So werden wir nicht wieder tun, aber erinnern dass erste Woche stand uns alle bis und dann die Hälfte von euch hingesetzt, die Hälfte Sie setzte sich, saß die Hälfte von euch nach unten. Das Algorithmus wurde in eine umgesetzt Bit eines Betrugs Weise, daß es wurde nicht nur einer der mich zählen, grundsätzlich effizienter. In diesem Fall war ich die Nutzung eine sekundäre Ressource. Sortieren von verschiedenen CPUs, mehreren Gehirnen, mehrere intelligente Menschen in der Zimmer halfen mir aus etwas zu bekommen linear etwas logarithmisch, von etwas rot, etwas grün. 

Aber in diesem Fall kann allein Jennifer grundsätzlich auf die Verbesserung der Performance ihres ersten Algorithmus, wieder nur daran denke ein wenig härter. Und jetzt, wenn es darum geht, Zeit zu implementieren diese Dinge, herauszufinden, was Codezeilen können Sie schreiben, wie dass man sie wiederholen und wieder und wieder, irgendwie in einem Looping Mode. Weil du wirst doch nicht um das haben Luxus, wie Jennifer tat zunächst, um nur eine ganze Reihe von ifs und sagen, hmm wenn diese erste Zahl ist 4, Lassen Sie mich zu springen den ganzen Weg bis zum Ende. Ooh, wenn diese Zahl ist zu groß, lassen Sie mich willkürlich zurück bewegen zu dem zweiten Element. Du wirst feststellen, dass es geht um eine Menge sein schwerer zu formalisieren, was wir Menschen nehmen für so sehr vernünftig gewährt Heuristiken, aber ein Computer ist nur zu tun, was Sie sagen, es zu tun. 

Nun, das hat eine sehr interessante Auswirkungen. Dieses Diagramm ist eine Art soll von sortieren überwältigen visuell, aber beachten, wo die gerade Linie in diesem Diagramm? Wo ist die lineare Kurve dass wir n nennen? Nun, es ist eine Art in Richtung der Unterseite dieses Bild, nicht wahr? Also alles, was wir getan haben, ist, wir haben eine Art aus der x-Achse und das vergrößerte y-Achse, um zu versuchen, um ein Gefühl von dem, was sich andere Arten von Kurven aussehen. 

Und die Besonderheiten der mathematischen Ausdrücke heute nicht so wichtig viel, aber feststellen, dass es eine Menge von Algorithmen, die viel schlimmer sind als etwas, das linear ist. Tatsächlich sieht n gewürfelt ziemlich schlecht. 2 zum n sieht ziemlich schlecht. n squared sieht ziemlich schlecht. Und wir werden sehen, was einige von denen vielleicht in Wirklichkeit heute. Und log n nicht so schlecht fühlen, aber besser als n log Basis 2 n. Aber Sie wissen, wäre es auch gewesen sein mehr erstaunlich, wenn Jennifer, oder wenn wir, dass erste Woche hatte mit zu kommen etwas, das Protokoll der log von n ist. 

Also mit anderen Worten, es ist das ganze Reihe von Lösungsmöglichkeiten Probleme, aber auch hier, Bekanntmachung was passieren wird. Als ich herausfand, Zoom, der von diesen Kurven wird sich als die absolute sein Schlimmste die, die auf dem Bildschirm jetzt? So n cubed sieht ziemlich schlecht im Moment. Aber wenn wir Verkleinern und sehen Sie mehr von der x und die y-Achse, die gehen, um ist dominieren letztlich? So ist es tatsächlich stellt sich heraus, dass die 2 bis n, und Sie können diese aus nur durch die Abbildung Einstecken in irgendeiner immer größeren Zahlen, und du wirst sehen, dass die 2 bis n der Tat immer größer viel schneller. Wenn wir wirklich Verkleinern, eine 2 bis die n-Algorithmus absolut scheiße. Ich meine, das wird dauern ziemlich viel Zeit für die Computer durch Kundenabwanderung. 

Aber du wirst im Laufe der Zeit zu sehen, vor allem mit zukünftigen Problem Sätze und sogar Abschlussarbeiten sind Ihre Daten Satz bekommt große, alles klar? Schon in der ersten Version von Facebook, wenn die Anzahl von Freunden, und Zahl der registrierten Nutzer haben große, Sie können es in der Telefon sortieren und Umsetzung etwas mit lineare Suche, oder ein sehr einfaches Sortieren Algorithmus, wie wir heute sehen. Sie müssen anfangen, härter und härter zu diesen Problemen. Und die Art von Problemen zu Orten wie Facebook und Google und Microsoft, und andere arbeiten auf genau diese Art von Big Data Art von Fragen zunehmend in diesen Tagen. 

In Ordnung. So Jennifer Erfolg in dieser zweiten Algorithmus, ehrlich gesagt, hat sie erstaunlich auch das erste Mal, aber wir schreibe es als Glück, so dass wir können diesen Punkt zu machen. Im zweiten Fall, sie eine Hebelwirkung Algorithmus wiederholt und wieder, aber sie hielten es für selbstverständlich ein bestimmte Annahme, dass es uns erlaubt sie, aber sie ausgebeutet einige Details der zweite Mal, dass sie nicht über die erste Zeit. Welches war was? 

Dass die Liste sortiert wurde. Also, sobald die Liste sortiert wurde, wir behaupten, dass Jennifer Lage zu tun war grundsätzlich besser. 7 Türen, ja, das ist nicht so interessant, aber vermute, es sind wir 7 Millionen Türen. Anmelden von n ist definitiv zu viel, viel durchführen schneller auf lange Sicht. Aber sie musste die haben Türen für sie sortiert. Nun nahm ich mir die Freiheit, das zu tun im Voraus auf dem Computer-Bildschirm hier, aber denke, dass Jennifer musste, dass selbst tun? Angenommen, dass die Türen in Frage repräsentiert Daten in einer Datenbank, oder Freunde für Facebook registriert ist, oder Jede Web-Seiten im Internet, die verschiedenen Websites Möglicherweise müssen zum Index oder Suche vorbei. 

Angenommen, Sie haben gerade einen Rohdaten gesetzt und es wurde Ihnen überlassen, oder Jennifer zu tun, dass die Sortierung? Dass vielmehr erfordert, dass wir antworten die Frage, na ja, wie viel Zeit genommen hätte Jennifer oder auch mich, , diese Zahlen im Voraus so sortieren , sie könne das auszunutzen? Right? Da die Implikation, ist natürlich wenn es dauert eine ganze Weile zu sortieren die Zahlen, wer zum Teufel kümmert, dass Sie kann eine Zahl wie 50 so schnell zu finden, wie in Jennifers Fall, wenn wir mehr als überfordert die Menge der gesamten Zeit es dauerte ordnen Dinge im Voraus? 

Also mal sehen, ob wir nicht die malen das Bild hier. Ich habe eine ganze Menge mehr Stress Bälle, ob das hilft das Eis brechen hier. Und wenn es Ihnen nichts ausmacht, wir müssen sieben Freiwilligen - auf, OK. Wow. So haben wir nicht zu verbringen auf dem Schreibtisch-Lampen, wie es scheint. In Ordnung. So wie sie Ihnen etwa zwei vor. Wie wäre es mit Ihnen beiden Jungs im Rücken. Also das ist vier. Wie wäre es mit Ihnen vor fünf, sechs und sieben. Genau dort. Ihr Freund freundlichst darauf hin, so erhalten Sie den Preis. 

In Ordnung. Komm up. Und warum haben wir nicht Sie Jungs kommen auf hier. Ich werde Ihnen jeweils eine Nummer. Und gehen Sie vor und arrangieren sich identisch zu dem, was dargestellt auf dem Bildschirm. 

[Zwischenschaltung VOICES] 

DAVID J. MALAN: Oop, sorry. Bug. In Ordnung. Nun, hier gehen wir. Nummer fünf. Nummer sechs. Eine, zwei, drei, vier, fünf, sechs, sieben. Oh, das ist peinlich. 

Sprecher 2: Ich werde einfach ein -. 

DAVID J. MALAN: Good deal. In Ordnung. Vielen Dank für Ihre Teilnahme. 

[Applaus] 

OK. In Ordnung. So haben wir vier, zwei, sechs, eins, drei, sieben, fünf. Perfekt, so dass wir sieben Freiwillige hier, die sind in der Breite gleich der Array, das wir spielen mit der früheren. Und ich wählte sieben Gründen das wird nur bequem in ein wenig. Und ich werde zum ersten schlagen vor, dass sortieren wir diese sieben Freiwilligen. Wenn Sie möchten, zuerst, hallo zu sagen though. Da dies wird eine sein umständlich mehrere Minuten. Stellen Sie sich vor. 

GRACE: Hallo, ich bin Gnade. Ich bin im zweiten Jahr in Leverett House. 

Branson: Hallo. Ich bin Branson. Ich bin ein Neuling in der Weld. 

GABE: Hallo. Ich bin Gabe. Ich bin ein Junior in Cabot. 

NEIL: Ich bin Neil. Ich bin ein Neuling in Matthews. 

JASON: Ich bin Jason. Ich bin ein Neuling in Greenough. 

MIKE: Ich bin Mike. Ich bin ein Neuling in Grays. 

Jess: Ich bin Jess. Ich bin im zweiten Jahr in Leverett. 

DAVID J. MALAN: Excellent. In Ordnung. Nun, ich danke Ihnen für alle unsere Freiwillige hier so weit. Und die Herausforderung bei der Hand jetzt los ist zu sein, um von diesen Jungs zu sortieren, aber dann wir gehen zu müssen, ein wenig zu denken hart, wie effizient wir eigentlich sortiert sie. Also lassen Sie uns zuerst dieses zu versuchen. Ihr könnt sehen einander die Zahlen nur, indem um die Ecken. Gehen Sie voran und nehmen Sie ein paar Sekunden, und sort euch von der kleinsten auf dem links nach größte auf der rechten Seite. Gehen. 

OK. Gut. Das war wirklich verdammt schnell. Jetzt hier jemand, was der Algorithmus dass diese Jungs angewendet? 

Sprecher 1: kleinste bis größte. 

DAVID J. MALAN: OK. Kleinste bis größte ist wirklich von der Art Ziel, aber ich bin mir nicht sicher, dass es wirklich ein Algorithmus. Kleinste bis größte nicht sagen mich Schritt für Schritt, was zu tun ist. Ja? 

Sprecher 1: [unverständlich] 

DAVID J. MALAN: OK. Also, wenn Sie sehen, eine Person weniger als Ihre Zahl ist, dann bewegen, um das Recht von ihnen. Also das ist jetzt immer mehr expressive, mehr wie ein Algorithmus, da Sie sagen kann, wenn diese, dass dann. So haben wir eine Art von Bedingungskonstrukt. Und diese Jungs schien, dass ein paar tun mal, weil einige von euch ein wenig bewegt eines Abstands. So gab es vermutlich eine Art Looping geht in ihren Köpfen. 

Aber lassen Sie uns versuchen, dass zu formalisieren. Wenn euch könnte zurückgesetzt dieser Anordnung. Mal sehen, ob wir nicht formalisiert diesen ein bit, und dann die Frage stellen, nur Wie effizient ist das? Natürlich, wenn wir dies tun, langsamer, es geht um das Gefühl, als gut von ein Algorithmus, aber wir sehen, ob wir setzen unsere Finger über die genauen Schritte. 

So ihr beiden Jungs sind vier und zwei. Oder Sie richtig oder falsch um? Offensichtlich falsche. Also haben wir getauscht. Jetzt werde ich beiseite bewegen und sagen, vier bis sechs. Sind Sie richtig oder falsch? 

GABE: Richtig. 

DAVID J. MALAN: Richtig. Sechs und eins? Nope. Tauschen. Also das ist zwei-Swaps. Sechs und drei? Nope. Tauschen. Sechs und sieben? Sieht gut aus. Sieben und fünf? 

Jess: [unverständlich] 

DAVID J. MALAN: OK, tauschen. Und sortiert. In Ordnung. So offensichtlich nicht, oder? Also es war mehr los. Aber in der Tat, diese Jungs, auch nur instinktiv. Bewegung gehalten. Sie haben nicht nur zu stoppen, wenn sie korrigiert ein Problem. So. Tatsächlich bin ich zu haben, um die gleiche Sache zu tun. Ich werde zu haben, um der Rücklauf wieder sortieren zu Beginn dieses Problems oder der Anfang dieser Reihe Leute, lasst uns rufen Sie diese. 

Und nun, was sollte mein Algorithmus im zweiten Durchgang sein? 

Sprecher 1: Die gleiche Sache. 

DAVID J. MALAN: Dasselbe. Und dies, fange ich an, gerne, nicht wahr? Sobald Du selbst tun die gleiche Sache immer und immer wieder, das ist immer mehr wie ein Algorithmus, und weniger menschlicher Instinkt. 

So, jetzt, hier gehen wir wieder. Zwei und vier? Nr. Vier und ein? Ah, es war in der Tat einige Arbeit noch getan werden muss. Für und drei? Gut. Vier und sechs? Sechs und fünf? Sechs und sieben? OK, jetzt, fertig. OK, nein. Ich muss zurück. 

So, jetzt wieder, wir tun dies ein wenig mehr bewusst. Und jetzt gibt es nur ein Gehirn Ausführung dieses Algorithmus. Eine CPU, wenn man so will. Und ehrlich gesagt, das ist die einzige Ressource, werden wir den Zugang zu haben. Und sobald wir zurück zu einer Tastatur und haben so etwas wie C in unserem Verfügung, wir nur ein Programm schreiben das kann eine Sache zu einer Zeit zu tun. Während, diese Jungs vor einem Augenblick, wir Leveraged ihre kollektive Intelligenz wie Sie Jungs haben in Woche null. Also lasst uns weiter machen. 

Zwei und eins. Zwei und drei. Drei und vier. Vier und fünf. Fünf und sechs. Sechs und sieben. Fertig? Also ich bin, aber lass mich spielen Advokat des Teufels. Muss ich, die Art von Computer, die gerade einen Pass durch diese Anordnung von Menschen, wissen, dass ich fertig bin? 

Sprecher 1: No 

DAVID J. MALAN: Warum? Was müsste ich tun, um Schluss entscheidend, dass ich fertig bin? Wahrscheinlich einer mehr weiter. Right? Weil alles, was ich wissen von diesem früheren Pass ist, dass ich einen Fehler korrigiert. Und das bedeutet, vielleicht gibt es noch ein weiterer Fehler dass ich korrigieren müssen. Ich kann also nur durch Zurückspulen sicher und dann überprüft, 01.59, und zwei drei, drei und vier, vier und fünf, fünf und sechs, sechs und sieben. OK, jetzt habe ich keine Arbeit. 

Ich kann sicherlich daran erinnern, dass ich nicht tat arbeiten mit so etwas wie einer variablen, wie ein int. Nennen Sie es, Swaps und Swaps, wenn 0 ist, wenn ich hier erhalten, und es begann bei 0, dann Ich wäre einfach dumm, um weiterzumachen hin und her und erneut prüfen, und wieder und wieder, nicht wahr? Weil man in einigen stecken Art Endlosschleife. Also, sobald es 0 Swaps, Wir können behaupten, dass diese Algorithmus ist in der Tat abgeschlossen. 

Nun, lasst uns einen Namen zu diesem Thema. Der Algorithmus, den ich schlagen wir nur implementiert ist etwas namens bubble Art, die als solche in dem Sinne bekannt, dass die Zahlen, die größer sind Art Blase ihren Weg bis an die Spitze, oder bis bis zum Ende der Reihe von Zahlen. Aber wie effizient war dieser Algorithmus? Wie viele Schritte habe ich körperlich müssen nehmen, zum Beispiel, um diese zu sortieren sieben Menschen? 

Vier bis fünf? OK, zu viel ist letztlich gehen, um die Antwort sein. Aber selbst dann, die bestimmte Anzahl ist nicht so interessant. Lasst verallgemeinern es als n. Also, wenn ich n Menschen hier oben, und sie waren, irgendwie, in zufälliger Reihenfolge auf das Anfang, in diesem ursprünglichen Reihenfolge. Nun, wie viele Schritte ich haben auf dem ersten Pass zu nehmen? Es war eine, zwei, drei, vier, fünf, sechs, und sie sind sieben Personen, so das ist sieben, sechs -, so, das ist n minus eins tritt die erste Zeit. 

Nun, wie viele Schritte ich haben zu nehmen, wenn ich zurückgespult? Nun, wir könnten tatsächlich verdoppeln, wenn wir wollten, aber jetzt bin ich gerade sagen, alles in Ordnung, andere n minus 1. Also das n minus 1 wird erhalten ärgerlich, um zu verfolgen, also lasst uns nur aufrunden leicht. So 2n Schritte. So 14 Stufen, geben oder nehmen. 

Wie oft habe ich ein Schritt das nächste Mal? Nun, es ist 3n. wirklich. Und nun, im schlimmsten Fall, für Beispielsweise würde, wie viele Male habe ich hin und her, hin und her gegangen, Ausführung dieses Algorithmus, Swapping Menschen bei jedem Durchgang, etwa? Es ist eigentlich n squared, nicht wahr? 

Denn im schlimmsten Fall können Sie Art denken über das intuitiv, auch wenn es vielleicht ein wenig wenig Zeit zu sinken in. Im schlimmsten Fall, was würden diese sieben Menschen aussah, in Bedingungen der Vereinbarung ihrer Zahlen? Ganz hinten, richtig? Und nur um zu simulieren, dass was war noch mal Ihr Name? 

MIKE: Mike. 

DAVID J. MALAN: Mike? OK, Mike, können Sie einfach mit mir über hier nur eine Sekunde? Eigentlich nicht. Leider Mike, lass uns Rücklauf. Was ist Ihr Name? 

NEIL: Neil. 

DAVID J. MALAN: Neil. OK, Neil, du kommst mit mich, wenn es Ihnen nichts ausmacht. Also werde ich vorschlagen, nur für Einfachheit, dass Neil ist jetzt in seinem ungünstigsten Fall. Aber daran erinnern, wie ich umgesetzt mein Algorithmus. Ich vergleiche, Vergleichen, vergleichen, Vergleichen, vergleichen, oh. Nun sind diese Jungs sind out Ordnung, so dass ich zu beheben. Also Jungs tauschen. Aber nun zu prüfen, wie weit Neil hat gehen müssen? Es ist etwa n. Sie wissen, es ist nicht wirklich n. Es ist wie, n minus 1, aber ich bin immer verärgert die Verfolgung des kleinen Zahl, so lasst uns einfach nennen es n. 

Also, wenn Neil bewegt sich einen Schritt maximal jeweils Zeit, und Neil einem Schritt zu verschieben Ich habe diese wirklich mühsame Pass machen hin und her, das ist etwa Dabei n Schritten, insgesamt n Mal, denn es geht um mich dass viele Schritte, um Neil alle der Weg dorthin, wo er hingehört. Geschweige denn jeder andere, wenn euch waren alle falsch bestellt als gut. 

So nennen wir bubble sort n Quadrat. Die Laufzeit dieses Algorithmus, der Leistung dieses Algorithmus die Effizienz dieses Algorithmus, werden wir nur beschreiben mehr allgemein als n straffte. Welches ist nett, weil ich tun konnte, die Dasselbe Beispiel mit acht Personen, neun Menschen, eine Million Menschen, und dass Antwort ist nicht zu ändern. 

Also, wenn euch nichts dagegen hätte, lasst setzen Sie, wo Sie begonnen. Und lassen Sie uns versuchen, zwei andere Ansätze und sehen, ob wir nicht grundsätzlich tun können besser als diese. Also dieser Zeit, ich werde vorschlagen eine Art von anderen Algorithmus. Das war sehr klug von uns beim letzten Mal, und euch zu Recht die haben Recht Instinkte nur irgendwie Auslagern paarweise. Aber wenn ich wirklich wollte, um diesen Ansatz einfach, und mein Ziel ist es, sich zu bewegen all die kleinen Zahlen auf diese Weise, und schieben alle den großen Zahlen, Weise, warum ich nicht einfach zu tun, dass in der naivsten Weise möglich und sehen, ob ich besser machen können als das, was ein recht komplexen Algorithmus? 

Also mal sehen. Vier ist eine ziemlich kleine Zahl, also bin ich werde dich dort zu lassen Moment. Ooh, ist die Nummer zwei sogar noch besser. So können Sie einfach Schritt vorwärts für einen Moment? Dies ist mein derzeitiger kleinste nummeriert Kandidat, und ich werde daran zu erinnern, dass mit, wie, eine Variable. Aber ich werde immer mal. Gibt es jemanden, dessen Zahl ist kleiner? Sechs, nein. Oh, da ist Neil wieder. 

Also werde ich Ihnen zurückschieben Art konzeptuell. Neil wird vorwärts zu kommen. Und nun, die Variable, die ich benutze, um verfolgen, wer hat den kleinsten Zahl wird aktualisiert, um enthalten Neil Standort. Naja, mal sehen. Drei, sieben, fünf. OK, ich weiß, Neil war das kleinste. Was ist die einfachste Sache für mich jetzt zu tun? Ich werde nicht meine Zeit verschwenden, indem nur Einleiten Neil einer Stelle auf der linken Seite. Warum kann ich nicht einfach setzen Neil wo er gehört, ist das natürlich wo? 

Den ganzen Weg am Anfang. So Neil, mit mir zu kommen. Und was war noch mal Ihr Name? 

GRACE: Gnade. 

DAVID J. MALAN: Gnade. OK. So Anmut, leider bist du Art in den Weg. So, wie wir dieses Problem lösen? Right? Wenn dies ein Array ist, gibt es nur sieben Standorten. Daran erinnern, dass mit Rob, sprachen wir über erklärt Altersstufen, und wir hatten nur ein endliche Anzahl von Alters? Gleiche Idee hier. Wir haben nur eine endliche Anzahl von ints. Anmut ist eine Art in unserer Übrigens, so wie wir das Problem beheben? 

Der einfachste Weg ist wie, Anmut, sorry. Du gehst zu müssen, gehen über so können wir es machen Platz. Nun, wenn Sie darüber nachdenken, vielleicht wir machten das Problem noch schlimmer. Und vielleicht haben wir, denn was ist, wenn Anmut waren an der richtigen Stelle? Aber wir wissen, dass sie nicht, denn sonst wäre sie gewesen, stehend nach vorne statt Neil in dieser Zeit, nicht wahr? Wir haben bereits überprüft ihre Nummer aus. 

In Ordnung. So, jetzt ist Neil an der richtigen Stelle, und Ich kann eine leichte Optimierung. Für den nächsten Minuten werde ich zu ignorieren Neil alle zusammen, um nicht seine Zeit verschwenden, oder versehentlich tauschen ihn an der falschen Stelle. So, jetzt, wie finde ich die nächste Element, das kleinste ist? Zwei. Das ist eine ziemlich gute Zahl, wenn Sie wollen nach vorne zu treten und Ich werde dich erinnern. Six, nicht gut. Vier, drei, sieben, fünf, nicht gut. Lassen Sie mich also bewegen Sie Ihren richtigen Stelle. Und wir hatten Glück diesmal. 

Nun, ich werde diese ignorieren zwei Jungs, und jetzt führen Sie einen mehr durchlaufen diese. Six, dass eine ziemlich kleine Anzahl. Komm nach vorn. Oh, sorry. Grace Zahl ist besser, so Schritt vorwärts auf. Four. Sorry, Gnade. Gehe wieder zurück. Nummer drei ist besser. Seven. Five. Und jetzt, was ist Ihr Name? 

JASON: Jason. 

DAVID J. MALAN: Jason. Also Jason ist nun der kleinste Element habe ich ausgewählt. Wo ist er hin? Also, wo ist sechs. Und Ihr Name ist wieder? 

GABE: Gabe. 

DAVID J. MALAN: Gabe. Gabe ist im Weg. Was ist die einfachste Sache zu tun? Tauschen Sie diese beiden Jungs und weiter. So, jetzt wollen wir mal sehen. Wer ist der kleinste? Four. Lassen Sie mich nur eine Art Cheat. Five wird der kleinste sein. Ich finde nächsten, wenn Sie zu Schritt wollen nach vorn, was muss ich tun, um mit diese Jungs, mit Gabe? Tauschen Sie es erneut. So, jetzt noch etwas nicht in Ordnung. Ich fand die kleinste Gabe sein, so Ich knallen ihn aus, bewegen Sie sich über Jungs. Und fertig. 

So Antwort ist die gleiche. Das Ergebnis ist das gleiche. Welche dieser beiden Algorithmen ist besser? Die zweite, hörte ich. Warum? 

SPEAKER 3: Es ist n Schritten [unverständlich]. 

DAVID J. MALAN: Es ist n Schritte bei den meisten. Interessante. So ist es eigentlich? Wie kam ich finde die kleinste Element? Wie viele Schritte musste ich nehmen die finden das kleinste Element? Ich hatte einen Blick den ganzen Weg am Ende, nicht wahr? Da in diesem schlimmsten Fall, was wenn Neil waren hier? So einfach finden Sie das kleinste Element nimmt mich n Schritte, oder n minus 1. Aber OK. So beheben Neil. Denken Sie daran, dass Sie eine Minute oder so vor. 

Aber wie finde ich die nächste kleinste Element? Es ist n minus 1 oder n minus 2 wirklich, von der Anzahl der Schritte. So OK. Also habe ich minus 2 N. In Ordnung. Also das fühlt sich ein wenig besser. In Ordnung. Wie viele Schritte das nächste Mal auf Platz drei zu finden? So n minus 4. So ist es ab, eine weniger Schritt bei jeder Iteration. Also das fühlt sich besser, nicht wahr? Wenn letzte Mal war es etwa n mal n, diesmal ist es n minus 1 plus n minus 2, plus n minus 3, plus n minus 4, Punkt, Punkt, Punkt. Aber wenn Sie sich erinnern, von Ihrem High-School- Lehrbücher, die kleine Cheat Blech auf der Rückseite, die Formeln hat, wenn Sie summieren sich diese Reihe von Zahlen, was ist die Gesamtzahl der Schritte zu sein, dass ich hier nehmen? 

Dies ist einer von denen, wie, n minus 1, n mal, geteilt durch 2. Also lassen Sie mich sehen, ob ich ziehen kann dies für einen Moment. Und wieder, ich bin Art der Rundung einige Zahlen nur um unser Leben einfacher, aber soweit ich mich erinnere, ist es so etwas wie, wenn Ich n minus 1 Dinge, dann n minus 2, dann n minus 3, es ist etwa etwas mehr als 2, und wenn ich multiplizieren Sie diese aus, ist das tatsächlich n Platz. Das fühlt sich nicht so gut. n minus n über 2. 

Aber hier ist das Ding. In der Informatik, wenn die Probleme anfangen, sich interessant ist, wenn n wird wirklich groß. Und wenn n wirklich groß wird, welche der diese Werte wird alle dominieren von den anderen? Es ist eine Art des n squared, nicht wahr? Ja, dividiert durch 2 ist ziemlich gut. Aber wenn du über Milliarden sprechen Stücke von Daten oder Billionen von Stücke von Daten, OK, so Sie sind doppelt so schnell. Aber wer kümmert sich wirklich, wenn diese große Zahl, wenn dieser Faktor ist, was bekommt größer und größer. Und sicher, es macht mehr ein Unterschied, als dieser Kerl. Also auch wenn ihr Jungs haben Recht, die zweite Algorithmus, nennen wir es Auswahl Art ist, in der realen Welt, ein etwas schneller potentiell, denn ich bin nehmen immer weniger Schritte jeder Zeit. 

Es ist nicht wirklich grundlegend schneller. Denn wenn wir tatsächlich spielen dies für große Werte von n, am Ende der Tag, für n groß genug, ist es immer noch sich fühlen, ziemlich langsam. Nun, lassen Sie mich ein letzten Pass auf, dass. Das ist, was ich nennen würde Auswahl sortieren. Könnt ihr euch zurück ein letztes Mal? Und in diesem letzten Fall, ich werde etwas vorschlagen genannt insertion sort. Insertion sort ist, konzeptionell, ein bisschen anders. 

Anstatt sich hin und her und Auswahl der kleinste Element, ich bin gerade dabei, mit jedem von ihnen umzugehen Jungs, wie ich sie begegnen, und setzen Sie sie in ihren richtigen Platz. Also ich bin gerade dabei, mit der Gnade zu starten, und ich sehe, dass sie die Nummer vier ist. Woher kommt Nummer vier gehören? Ich habe noch nicht begonnen Sortierung nichts, so Gnade bekommt Recht dort zu bleiben. Und jetzt werde ich Anspruch, wenn du könntest einen Schritt nach rechts, diese meine sortierten Liste, dies ist mein unsortiert verbleibenden Liste. So, jetzt werde ich zum nächsten gehen, und was ist Ihr Name? 

Branson: Branson. 

DAVID J. MALAN: Branson. So Branson ist Nummer zwei. Also werde ich Ihnen nehmen für einen Moment. Und jetzt, wo Sie hingehören in diesem Array? Also auf der rechten Seite von Grace. Also noch einmal, wir sind Art der Herstellung Anmut tun eine Menge Arbeit hier. Wo setzen wir Sie? So werden wir Sie zu der Folie links, und legen Sie es Branson. Aber jetzt habe ich behaupten, dass Sie Kerle sind fertig. Aber beachten Sie, ich bin nicht mit zusätzlichen Platz. Es ist immer noch 2 Elemente hier 5 hier. Insgesamt Array-Größe ist 7, also bin ich nicht betrügen, alles in Ordnung? 

So, jetzt haben wir mit Gabe hier die Nummer sechs, wo gehörst du? Sie haben wieder Glück. So erhalten Sie nach rechts dort zu bleiben. Man braucht nur einen leichten Schritt nach rechts nur deutlich machen, dass Sie sortiert sind. Und jetzt haben wir wieder Neil, Anzahl ein, wo soll man gehen? Und jetzt, wo wir beginnen werde, das zu sehen Dieser Algorithmus, wenn auf den ersten Blick, fühlt sich ziemlich smart, beobachten was zu geschehen. Wenn man einen Schritt vorwärts. 

Wo wollen wir Neil setzen? So offensichtlich hier, so wie bekommen wir Neil dort? Lassen Sie uns diesen Schritt-für-Schritt. Gabe, wo Sie brauchen, um zu gehen? Yep, so nehmen Sie einen großen Schritt, oder zwei halbe Schritte, um einen Schritt drüben. Anmut, wohin du gehst? Gut. Also ein weiterer Schritt. Und schließlich Branson? Ein weiterer Schritt. Und jetzt können wir Neil in Position gebracht. 

So, jetzt, weiterhin diese Logik. Auch wenn wir nicht verschieben Neil über und über und über, um ihn legte wo er geht im schlimmsten Fall die nächste Zahl, die wir stoßen könnten konnte werden die Zahl, sagen wir, hat es einige Null ist, dann werden wir alle zu verschieben diese Jungs. Angenommen, es gibt eine Reihe, negativ ein, dann müssen wir verschieben all diese Jungs. Also wir sind wirklich nur irgendwie Spiegeln das Problem herum, so dass wir Übertragung der Kosten von der Auswahlverfahren so das Einsetzen Prozess, so dass Sie Jungs hatten gerade auf rund minus n etwas bewegen Anzahl der Schritte. Und diese Zahl der Schritte ist nur noch zu erhöhen, wie ich mehr Nummern wählen, wenn ich zu halten schubsen euch Rücken-und Rückseite, und zurück. 

So die traurige Sache ist jetzt all diese Algorithmen sind n quadriert. Lassen Sie uns fortfahren und diese dank Jungs, und visualisieren diese ein bisschen anders. Sehr gut gemacht. 

[Applaus] 

In Ordnung. Dort gehen Sie. Vielen Dank für die - 

Branson: [unverständlich] halten die Zahlen. 

DAVID J. MALAN: Nein, Sie können halten die Zahlen als gut. In Ordnung. Schön gemacht. In Ordnung. Also lasst uns sehen, ob wir jetzt nicht zusammenfassen können schneller und mehr visuell, genau das, was gerade passiert ist hier wie folgt. Ich werde weitermachen und ziehen Sie Firefox. Wir verknüpfen diese Demonstration Auf dem Kurs auf der Website. Java ist ein bisschen ärgerlich zu bekommen arbeiten in einigen Browsern in diesen Tagen. Also, wenn Sie mit diesem zu Hause nicht spielen, erkennen, müssen Sie möglicherweise Firefox nutzen um es arbeiten. Und was ich damit zu tun Demonstration ist die folgende. 

Am Boden habe ich eine ganze Reihe von Menü-Optionen, einschließlich einer Start-und einer Stopp-Taste. Auch als beiseite, es scheint eine sein Fehler in diesen Programmen, wobei Sie kann nicht wirklich sehen, die Start-oder Stopp Taste, wenn Sie halten Befehl oder Alt Plus-und Zoom-in, die neugierig zeigt Ihnen weitere Schaltflächen. Also nur, wenn Sie spielen FYI mit diesem zu Hause. Jetzt werde ich zu Beginn in nur einem Klick Moment, nach Angabe einer Verzögerung von wie, 200 Millisekunden hier, nur so können wir sehen, was passiert. 

Also ich behaupte, dass dies eine Visualisierung der erste Algorithmus diese Jungs haben, bubble sort, wobei tauschten wir Menschen paarweise. Der Schlüssel zu dieser Einsicht Visualisierung ist, dass die Höhe der Balken stellt die Größe der Zahl. Also das größer der Balken, desto Je größer die Zahl. Kürzer der Balken, je kleiner die Anzahl. Und wenn Sie feststellen, wir durchmachen Die erste Iteration des Algorithmus, Swapping große und kleine Zahlen, so dass die geringe Zahl an erster Stelle und die große Zahl geht nach rechts. 

Und sobald wir das Ende des Feldes zu bekommen viele mehr Zahlen als sieben sind wir werde gehen zurück an den Anfang. Und diese erwarten. Ganz links, ist, dass kleine Kerl los auf die Seite wechseln, und das Prozess wiederholt. Nun ist diese Visualisierung schnell bekommt langweilig, so lassen Sie mich gehen Sie vor und stoppen es, die Verzögerung etwas viel schneller, nur um jetzt bekommen, ein Gefühl für Dieser Algorithmus. 

Also obwohl ich raste es auf, ist dies wie mein Prozessor Upgrade, Kauf einen neuen Computer. Ich habe nicht grundlegend verändert meine Algorithmus, aber man kann in der Tat mehr sehen Deutlicher als mit den Menschen, dass die große Zahlen sprudeln bis an die Spitze, und die kleinen Zahlen sprudeln bis auf den Boden. Und jetzt diese Sache hier sortiert. Und so nebenbei, auf den Plätzen, gibt es nur einige Buchhaltung dort Sie zählen, wie viele Vergleiche, oder wie viele Swaps tatsächlich getan. 

Nun, lasst uns versuchen, eine die andere, die wir gesehen haben. Lassen Sie mich auf Bubble-Sort klicken Sie hier, und lassen Sie mich wählen, und diese ganze Web-Seite ist ein wenig buggy. Lassen Sie übernehmen das Risiko und führen Sie es erneut. Dort gehen wir. So lasst uns Auswahl sortieren. Ich weiß nicht, warum das Menü erscheint da drüben. Lasst uns vergrößern, um das zu beheben bug, ändern Sie dies in 50. Ah, wir tatsächlich tun die viel schneller. Fünf Millisekunden oder so, und tauschen. 

Das ist also Auswahl sortieren. Also noch einmal, über das, was wir denken, tat mit den Menschen hier oben. Wir gingen durch die Anordnung und Auswahl das kleinste Element wieder und wieder, und wieder. Jetzt habe ich behaupten, dass war immer noch ziemlich schlecht. Es war immer noch n squared, geben oder nehmen, aber es war, in der realen Welt, ein bisschen schneller, weil ich in der Tat nahm etwas weniger Schritte jeder Zeit. Aber wir reden nur was? Vielleicht 40 oder so Bars hier? Wir reden hier nicht 40 Millionen. So ist es nicht ganz mir klar, dass war in der Tat eine erhebliche Verstärkung. 

Lassen Sie mich nun zurück und ändern unseren dritten Algorithmus, der wurde wählen insertion sort. Und jetzt ist es wirklich buggy, weil die Menü sollte wirklich nicht sein da unten. So, jetzt werden wir wieder hier oben scrollen und starten Sie diesen Algorithmus. Whoop, starten und stoppen. Also das eine Art hat ein hübsches Muster zu, wobei wir wieder Einsetzen der Menschen, oder in In diesem Fall die Stäbe in ihren geeigneten Platz. Und es ist schon getan, bevor Ich drehte mich um. Aber auch dieser in der Theorie, noch n quadriert. 

Also lasst uns sehen, ob wir nicht fassen diese wie folgt. Ich werde weitermachen und nur, um uns eine Art gemeinsame Art zu reden über diese Dinge, möchte ich mich vorstellen nur ein bisschen Notation hier. Sie sind im Begriff, etwas zu sehen als große O, denn es ist buchstäblich ein großes O. Und dies ist ein Weg, dass ein Computer Wissenschaftler oder ein Mathematiker benutzt sogar die Laufzeit beschreiben einiger Algorithmus. Wie viele Stufen hat es tatsächlich? 

Jetzt werde ich mich mit Verlegenheit meine Handschrift hier in nur einem Augenblick. Aber lassen Sie mich gehen und sagen, dass Dies wird große O hier sein. Und lassen Sie mich Ihnen eine andere Symbol, ein Kapital Omega. Omega wird das Gegenteil sein, Wesentlichen von großen O. in der Erwägung big O Mittel, im schlimmsten Fall, wie viel Zeit könnten einige Algorithmus zu nehmen, in Abhängigkeit von n, wird Omega zu gehen sein, wie viel Zeit könnte es nehmen im besten Fall. Und wir werden sehen, was wir unter besten Fall in nur einem Augenblick. 

Also fangen wir etwas einfach. Lassen Sie mich mit einer linearen Suche zu starten. Also nicht sorting. Wir nennen diese lineare Suche. Und jetzt, machen ein wenig Tabelle raus. Und jetzt, im Fall der linearen Suche, im schlimmsten Fall, wie viele Schritte ist es geht um mich zu treffen, um eine zu finden Anzahl der Willkür? Und es gibt n insgesamt Türen oder n Gesamtzahlen. Worst case. Wie viele Schritte ich gehen zu müssen, ergreifen, um die Zahl 50 in einem Array finden von n Türen? Und warum? Da könnte es die ganze Weg über auf das Ende. So viel wie Jennifer angetroffen, die Nummer 50 war den ganzen Weg über, so in im schlimmsten Fall lineare Suche ist groß O von n, wir sagen. 

Was ist mit dem besten Fall wenn Sie wirklich Glück haben? Es ist gerade dabei, einen Schritt zu tun, oder eine konstante Anzahl von Schritten. Also werden wir, dass 1 zu beschreiben. Also das ist ziemlich gut. Was nun, wenn wir etwas mag binäre Suche? So binäre Suche im schlimmsten Fall hat, wie viel Zeit? 

[Zwischenschaltung VOICES] 

DAVID J. MALAN: Also eigentlich habe ich gehört, dass es in ein paar Plätze. So ist es tatsächlich einloggen n, geben oder nehmen, denn wie wir teilen die Liste in zwei Hälften wieder und wieder, und wieder, sind wir in der Lage um letztlich der Wert, wenn es da ist, aber es gibt einen Haken. Was ist in der Annahme, dass wir zu haben nehmen für gewährt für binäre Suche? Es muss sortiert werden. Es ist nicht sortiert ist, können Sie spalten das Ding in Hälfte wieder und wieder, und Sie können gehen Sie nach links, und Sie können gehen Sie nach rechts und Sie gehen links und rechts, aber du bist nicht, um das Element zu finden, wenn die Liste nicht sortiert ist, weil Sie könnten verpassen. Weil Ihre Heuristik für den Gang links oder rechts wird fehlerhaft, wenn es sein Tat nicht sortiert. So gibt es eine Art von versteckten Kosten um mit so etwas wie dies. 

Lassen Sie uns nun in unsere Sortier gehen Algorithmen nicht auf der Suche - oh, eigentlich wollen wir in dieser leeren gehen. Binäre Suche im besten Fall? Es ist auch ein, wenn es passiert, nur um genau in der Mitte des Arrays oder in der Mitte des Telefonbuchs. Jetzt lasst uns bubble sort. Also noch einmal, jetzt betreten wir die Sorten, die nicht durchsucht. 

Im schlimmsten Fall hat, wie viele Schritte, die wir Anspruch bubble sort wird dauern? n straffte. Also ich werde das machen. Ooh, sieht meine Handschrift noch schlimmer wenn es projiziert, dass groß. In Ordnung. Also das ist n Quadrat. Und im besten Fall von Bubble Sort, wie viele Schritte wird es dauern? 1, hörte ich. 

Sprecher 1: n. 

DAVID J. MALAN: n, hörte ich. 

Sprecher 1: 2. 

DAVID J. MALAN: 2, hörte ich. Höre ich 3? In Ordnung. Also ich habe gehört, 1, n, 2, aber wir holen Neben wenigstens der erste der Anregungen, 1. Es ist kein schlechter Instinkt, weil es Art folgt hier ein Muster. Aber wenn es dauert nur 1 Schritt, wie in der Welt könnte ich behaupten, dass die Liste sortiert ist, denn wenn ich nur ich darf 1 Schritt, wie viele Elemente nehmen konnte ich tatsächlich überprüfen um sicher zu sein? Nun, nur 1, was bedeutet, es gibt n minus 1 Elemente das könnte aus Ordnung, und ich werde einfach auf den Glauben nach Blick auf ein Element, dass die Sache sortiert ist. Also 1 ist hier nicht zu korrigieren. So minimal, wie viele muss ich schauen? 

[Zwischenschaltung VOICES] 

DAVID J. MALAN: n minus 1, oder wirklich, n, da muss ich bei jedem Blick Element, um sicherzustellen, dass es ist nicht in Ordnung. Aber noch einmal, wir von unserer Welle sortieren Hände an den kleineren Zahlen und davon ausgehen, dass, wenn n groß wird, sind sie uninteressant sowieso. Also das ist, bubble sort. Und jetzt lasst uns diese letzten zwei. Auswahl sortieren und dann werden wir tun insertion sort. Und dann werden wir blow your Köpfe mit etwas viel besser als alle diese. In Ordnung. 

Was ist der schlimmste Fall läuft Zeitpunkt der Auswahl sortieren? 

SPEAKER 4: n Quadrat. 

DAVID J. MALAN: n Platz, ich hörte. Aber warum n straffte, intuitiv? 

SPEAKER 4: Weil wir es einfach getan. 

DAVID J. MALAN: Weil wir es einfach getan. OK. Gute Antwort. Aber intuitiv, warum ist die Auswahl sort n squared? Was haben wir zu tun haben, immer und immer wieder? Wir hatten zu halten Scannen durch, sind Sie die kleinste, Sie sind der kleinste, Sie sind die kleinste. Und selbstverständlich waren wir in der Lage, n nehmen Schritte, dann n minus 1, dann n minus 2. Aber wenn Sie Art fügen sie die alle auf, oder nehmen Sie es auf den Glauben, dass ich aufgenommen ihnen im Voraus, erhalten wir etwa n Quadrat minus einigen kleineren Zahlen. So werde ich nennen diese n Quadrat. Aber mit der Auswahl in der besten Art Fall, wie viele Schritte ist es werde mir nehmen? 

SPEAKER 5: [unverständlich] 

DAVID J. MALAN: Es ist leider noch n squared, nicht wahr? Denn wenn ich die Auswahl des kleinsten Element, und wir hatten sieben Leute hier, Ich weiß nur, sobald ich auf die sehr Ende, dass ich die kleinsten gefunden Nummer, wo immer er oder sie gewesen sein mag. Aber wie finde ich den nächsten kleinste Zahl? Ich habe einen anderen Pass zu tun. Also im besten Fall, was ist das Eingang zur Auswahl sortieren? Es ist eine Art Liste bereits, die Nummer eins, Nummer zwei, Nummer drei, Nummer vier. Aber ich bin ein Computer. Ich kann nur auf einen Blick Sache zu einer Zeit. Ich kann nicht irgendwie einen Schritt zurück wie ein Mensch und sagen: ooh, das sieht richtig. 

Ich kann nur entscheiden Korrektheit in Auswahl sortieren, indem Sie die wenigsten. Aber selbst wenn ich die Nummer eins erste, wenn ich weiß gar nichts anderes über die anderen Zahlen, die ich nicht tun, alles, was ich wissen, dass ich schon immer ein Array übergeben oder ein Satz von Türen, dahinter Zahlen, der einzige Weg, ich weiß, dass man war der kleinste? Wenn ich den ganzen Weg hierher und zu realisieren, verdammt, war man in der Tat die kleinste. 

Aber wie kann ich dann feststellen, dass zwei ist die nächste kleinste? Durch die gleiche Ineffizienz wieder und wieder. So endlich, mit Insertion Sort, wie im schlimmsten Fall hatten wir sagen, es führt? Auch sie ist n Quadrat. Und wie wäre es mit dem besten Fall? Wir werden, dass als Cliffhanger zu verlassen. Wir werden in diesem blank nächsten Zeit zu füllen, aber lassen Sie mich zuerst vor, dass wir grundsätzlich besser als alle diese, alles in Ordnung? 

Also für sich selbst zu denken, was Einsetzen Art los zu sein. Nun, das war nicht sehr dramatisch, weil ich bin der einzige, das sah die Änderung. Wow. OK. Hier haben wir also eine etwas verschiedenen Demonstration. Wenn ich vergrößern hier, sehen Sie, dass auf der linken Seite haben wir bubble sort, in der Mitte Auswahl sortieren wir haben, und auf Ganz rechts, haben wir etwas, was wir haben noch nicht sah genannt Mergesort. Aber bedenken Sie, was wir waren denn hier so weit heute. Wenn Jennifer erste kam auf die Bühne, Wir gingen durch die Anordnung von Zahlen wieder und wieder, mit linearer Suche, und wir haben lineare Laufzeit, große O von n, so zu sprechen. 

Wenn wir nun die erste Woche Klasse, wenn wir teilen und zu erobern, und wir hatten das Telefonbuch Reißen, und Jennifer, und wir gemeinsam genutzt, dass wichtige Erkenntnis, die war wiederholen sich immer und immer wieder durch irgendwie wegwerfen, wegwerfen, Wegwerfen, die Hälfte des Problems, oder Im Allgemeinen teilt ein Problem in der Hälfte, und dann Behandeln des kleineres Stück das Problem als konzeptionell gleichwertig zum anderen, wir irgendwie tat grundsätzlich besser. Aber mit bubble sort, mit Auswahl Art, mit Insertion Sort, wir haben können keine solchen Einsichten, die Jennifer tat. Wir ziemlich genau ging zurück und weiter eine ganze Reihe von Zeiten, und wir gezwickt Dinge ein wenig, Swapping in dieser Reihenfolge, vielleicht Einfügen oder Auswählen. Aber am Ende des Tages habe ich eine Menge umständlich zu Fuß hin und her. Wir haben nicht wirklich etwas nutzen Smart wie Jennifer mochte Dividieren und erobern. 

So verschmelzen Art hingegen, die wir wird erst nächste Woche sehen, es geht zu nutzen, dass zentrale Idee, indem der Eingang, und dann zu halbieren, und dann halbieren und dann halbieren. Und bei jeder Iteration der Schleife, Sortieren der linken Hälfte und der rechte Hälfte, dann die linke Hälfte der linken Hälfte, und die rechte Hälfte des linken, dann die linke Hälfte der rechten Hälfte, und die rechte Hälfte der rechten Hälfte. Und immer und immer wieder wiederholen. 

So wirst du dies visuell zu sehen, aber diese ist das, was erwartet uns nächste Woche. Und überhaupt, wenn wir denken, ein wenig etwas härter an einem solchen Problem. Wir haben n auf der linken Quadrat, n Quadrat in der Mitte, und n einloggen n auf der rechten Seite. Also es ist dein richtiger Cliffhanger. Wir informieren Sie am Montag zu sehen. 

[Applaus]