[Musikwiedergabe] David J. MALAN: Dies ist CS50. Und dies ist der Beginn der dritten Woche. Also haben wir viele spannende bekam Dinge heute zu decken. Viele Möglichkeiten für Freiwillige auf die Bühne. Und letztlich ist heute nicht um Code überhaupt. Aber es geht um Ideen und es geht darum, Algorithmen, und tatsächlich bringt wieder einige die Lehren aus der Woche Null gelernt, bei dem Rückruf, wir führte diese Monstrosität. Und aufgenommene Kredite Inspiration davon zu starten zu lösen immer ausgefeilteren Probleme algorithmisch. Doch zunächst ein paar Ankündigungen. So einen, wenn Sie möchten, um beizutreten Mitarbeiter CS50 und Klassenkameraden beim Mittagessen an diesem Freitag, sowohl hier als auch in Cambridge, und in New Haven, besuchen Sie bitte den Kurs der Website, auf eine URL gefunden werden kann. Vortrag an diesem Mittwoch wird hier nicht Sanders sein. Es wird nur online sein, also tune in am CS50-Website, ob hier in Cambridge oder New Haven als gut. Und dann Problem stellte zwei ist bereits in Ihren Händen. Wenn Sie sich noch nicht getaucht haben, lassen Sie mich die scharf formulierte Anregung bieten , dass, vor allem jetzt, da das Problem setzt voraus, Sie wirklich wollen, jetzt zu beginnen, wenn nicht plantschen ein wenig am Wochenende oder vor wenn sie zuerst gehen auf Freitags, weil man sonst finden, dass sie nicht unbedingt immer länger oder schwieriger pro se. Ich glaube, Sie werden feststellen, dass, in Generell neigen sie dazu, grob zu nehmen rund um dieselbe Zeit. Aber es hängt auf der Student, und es ist abhängig von der Denkweise , mit denen man sich ihr nähert. Aber immer, Sie gehen up gegen einen Wand zu laufen, und Sie gehen zu treffen sind einige Fehler, und du bist nur nicht in der Lage zu sein, get over it an einem gewissen Punkt. Und es ist äußerst wertvoll, um in der Lage sein, um Schritt weg, kommen am nächsten Tag zurück, gehen Sie zu Bürozeiten, senden Sie am CS50 Diskutieren oder dergleichen, um tatsächlich entsperrt. So sollte man das im Hinterkopf. Ab frühestmöglich ist das Beste, was Sie tun können. Also hier ist, wo wir angefangen haben die Klasse, über in Woche null. Und wir können eine freiwillige erhalten hier zu helfen, mich Mikrofone finden? OK. Aufstehen bereits. Komm auf. Denke, das ist, wie es geht, um zu arbeiten. Wie heißen Sie? ALAN ESTRADA: Alan Estrada. David J. MALAN: Alan Estrada. Komm auf. Nett, dich zu treffen. ALAN ESTRADA: Nice to meet you. David J. MALAN: Und waren Sie hier bei uns in Woche null, natürlich. ALAN ESTRADA: ich war. Ich war. David J. MALAN: So könnten Sie gehen vor und finden für uns Mike Smith, so schnell wie möglich? So schnell, wie Sie können. Buchstäblich zerreißen das Problem in zwei Hälften, wie Sie benötigen, um. ALAN ESTRADA: Ähm. David J. MALAN: Buchstäblich Reißen, das Problem in zwei Hälften. ALAN ESTRADA: Oh. Mm. Sehr gut. David J. MALAN: OK. Gut. Danke. ALAN ESTRADA: Sehr gut. OK. David J. MALAN: Und nun, Sie beschnitten haben sich auf die Hälfte der Größe des Problems. Nun, wir sind bis zu einem Viertel. Werden Sie aufgepasst auf welcher Seite wir halten? [Lacht] ALAN ESTRADA: Ja, ich think-- David J. MALAN: Welche Abschnitt sind wir? ALAN ESTRADA: Schalldämpfer, so. David J. MALAN: OK. Aber Mike Smith geht nach Schalldämpfer sein. Also-- [Lacht] Gut. ALAN ESTRADA: Wo sollen wir suchen? David J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. David J. MALAN: Nun, wir sind in der chirurgischen. Nun, die Ärzte. Now-- ALAN ESTRADA: Let's- wir mit echten gehen. Echt. David J. MALAN: Real. OK. Wenn Sie Real. Nun, der Weg ist Mike Smith? ALAN ESTRADA: Auf diese Weise. David J. MALAN: Welche Methode? ALAN ESTRADA: Warten. M ist-- oder? Wir begannen mit-- David J. MALAN: Ja. Sie verließ. Ihr Recht. ALAN ESTRADA: Ja. David J. MALAN: So Mikes hier. ALAN ESTRADA: Was? [Lacht] Schlechtes Beispiel, Jungs. Es tut uns leid. David J. MALAN: Dies wird lehren Sie von Ihrem Stuhl zu springen. ALAN ESTRADA: Oh. Oh. Ich habe dich. Ich habe dich. Oh. Oh. Dies ist-- OK, ich habe Sie. Smith hier richtig? David J. MALAN: Smith, ich danke Ihnen. Also werde ich auch in Zukunft bis Smith? ALAN ESTRADA: Oh, ja. Nein nein Nein. Oh nein. Das gehört mir. David J. MALAN: Oh, Smith habe Sie. OK. ALAN ESTRADA: Ja, ich bekam Smith hier richtig. Tut mir leid, Leute. Ich dachte, wir Michael-- wurden für Michael suchen. Es tut uns leid. David J. MALAN: Es ist OK. In Ordnung, jetzt sind wir in Paccini and Sons. ALAN ESTRADA: Paccini und Söhne. David J. MALAN: Nur Sie und ich sind in zu diesem Thema. OK. Finden Sie uns Mike Smith. Schmied. ALAN ESTRADA: Smith. David J. MALAN: Smith. Wir sind in der R für Müll. ALAN ESTRADA: Rubbish. Oh. Das wird eine Weile dauern. [Lacht] David J. MALAN: Schuhe. Wir sind in den Schuhen. ALAN ESTRADA: Jetzt sind wir gonna-- David J. MALAN: Nice. ALAN ESTRADA: Which-- [Lacht] Oh, das ist großartig. [Lacht] David J. MALAN: Es ist OK. ALAN ESTRADA: Oh, das ist gut. Ich glaube nicht, ich bin zu gehen haben PSAT Freunde danach. David J. MALAN: Good. Sporting. ALAN ESTRADA: Sporting. Ähm, L, M, N, O, P David J. MALAN: OK. Lassen Sie uns also reißen diese in zwei Hälften. Es ist in Ordnung. Damit endet schlecht trotzdem, weil Mike Smith wird nicht in den Gelben Seiten zu sein. ALAN ESTRADA: Aw. David J. MALAN: Nein, es ist OK. Aber lassen Sie uns so tun, wie er ist auf dieser Seite. So, jetzt, das Problem nach unten beschnitten habe zu einer Seite, und wir fanden, Mike Smith. [CHEERING] OK danke. OK. Das war außergewöhnlich. Aber es war immer noch schneller als lineare Suche, wobei Wir starten am Anfang des Buches, und wir uns auf den Weg von links nach rechts zu bewegen, schließlich auf der Suche nach Mike Smith. Und so, wenn das Telefonbuch hatte vielleicht 1.000 Seiten, vielleicht wäre es genommen haben uns 10 oder so page Tränen. Sie können aber genutzt haben berührt eine Annahme während all das, was zu sagen ist, , dass das Telefonbuch im Vorfeld war das, was? ZIELGRUPPE: Sortiert. David J. MALAN: Es sortiert. Recht? Es ist alphabetisch sortiert, so daß alle diese Namen und Nummern werden aus dem A ist, um die sortierten Z ist, und alphabetisch dazwischen. Aber heute haben wir nun fragen, die Frage, na ja, Wie hat Verizon oder das Telefon Unternehmen bekommen es in diesem Zustand? Denn es ist eine Sache, zu nutzen, Diese Annahme und deshalb ein Problem mit einem zu lösen Algorithmus effizienter. Aber wir haben nie wirklich in Woche null gebeten, nun ja, wie viel hat es gekostet Verizon oder jemand anderes , dass die Telefonbuch in sortierter Reihenfolge zu bekommen? Recht? Es spielt keine Rolle, wenn Nachschlagen Mike Smith ist super schnell, wenn es dauert Ihnen ein Jahr, um die Seiten zunächst zu sortieren. Recht? Genauso gut könnte man nur zu sichten durch eine randomisierte Telefonbuch, wenn es geht Super zu sein teuer, um sie zu sortieren. Also, wenn wir einen anderen Freiwilligen haben. Lassen Sie uns einen Blick hier an wie wir might-- komm up-- how wir könnten zu sortieren diese gehen. Und wenn Jordan konnte tatsächlich besuchen Sie uns hier oben auf der Bühne. Kommen Sie für einen Moment. Wie heißen Sie? CAROLINE: Caroline. David J. MALAN: Caroline, komm herauf. Und Sie verbunden sein werde von mir und Jordanien hier. Caroline, ich danke Ihnen. Gut. Also, was wir hier für haben Caroline ist 26 blaue Bücher dass FAS verwendet, um zu verwalten bestimmte Abschlussprüfungen. Diese sind immer hart zu finden, aber was wir vorher getan haben ist, dass wir jemand den Namen setzen auf der Vorderseite von jedem von diesen, aber wir haben es einfach durch gehalten dann setzen Sie die vollständigen Namen. So würden wir die Person mit dem Namen setzen L, D, J, B, den ganzen Weg von A bis Z, aber sie sind in zufälliger Reihenfolge. Und so, wenn Sie möchten, sprechen Sie Ihre Weg durch das Problem wie du es tun, können Sie weitermachen und sortieren diese für uns, von A bis Z. ZIELGRUPPE: OK, so dass L ist wie die Mitte. C beginnt. B. J, bevor L. B, F: David J. MALAN: Halten Sie, dass dachte für eine Sekunde. Denn sonst ist dies nur Sie interessiert, dann mich, und Jordanien. Da gehen wir. ZIELGRUPPE: [unverständlich]. R. David J. MALAN: OK. Was tust du? CAROLINE: M kommt nach O. David J. MALAN: OK. CAROLINE: O. David J. MALAN: O, gut. CAROLINE: E. David J. MALAN: E, F. Ja. CAROLINE: T, U, V David J. MALAN: V, T, U, V. So ist es sieht aus wie du bist making-- weiterzumachen. Es sieht aus wie Sie machen Ein großer Haufen hierher, und Art von einem großen Haufen drüben. So ist die erste Hälfte des Alphabets, zweiten Hälfte des Alphabets. OK. Gut. Art der Aufteilung des Problems in zwei. M, N, X Ja. CAROLINE: K. David J. MALAN: OK. K. Sie sind also Art von Auswahl sie nacheinander, setzen sie entweder links oder rechts, oder Z ist los auf dem Boden. OK. CAROLINE: Z ist los auf dem Boden. David J. MALAN: OK. Y wird auf dem Boden. Jetzt können wir X. setzen CAROLINE: G. David J. MALAN: G los gelassen. S geht rechts. In Ordnung, A ist den ganzen Weg nach links. CAROLINE: A, B, C, D. David J. MALAN: Nun gut. Wir haben bekommen, B, C W ist da unten los. In Ordnung, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. Gut. CAROLINE: In der Mitte, ich gonna-- David J. MALAN: OK. So, jetzt sind wir zu Art gehen der verschmelzen diese verschiedenen Pfählen. So A bis C, dann sehe ich D und E und F und G und H und I. Nizza. J, K, und dann wird dieser Haufen auf den Kopf, aber das ist OK. Sicher. Wir können einige Ecken schneiden. OK. Und dann müssen wir W, X, Y, Z. CAROLINE: Ja. David J. MALAN: Ausgezeichnet. Also ein großes Dankeschön an Caroline zum Sortieren dieser. [CHEERING] Danke. Danke sehr. So, jetzt betrachten einen Moment lassen wie Caroline ging zu tun, und was genau wir waren in der Lage, wie wir zu-- waren in der Lage zu lösen, dass Problem, wenn wir gerade waren bei einer ganzen Reihe von zufälligen Eingaben. Nun, es sieht aus wie es war ein bisschen wie ein System gibt es? Recht. Also die früheren Briefe im Alphabet, sie war Putting nach links, und die später Buchstaben im Alphabet, sie wurde in den rechten setzen. Und sobald sie gefunden einige proximalen Buchstaben, diejenigen, daß nach rechts nebeneinander, sie würde die in Ordnung zu bringen. Und so haben wir Art von dieser kleinen hatten Haufen von sortierten Eingänge auftritt. Und das ist also ganz wie, was die meisten von uns Menschen tun würde. Wir würden eine Art durchforsten sie, und wir würden uns Art einen Mechanismus. Aber es könnte schwierig sein, zu schreiben it down in einer Formel an sich. Es fühlte sich ein wenig mehr organische als das. Also mal sehen, wenn wir können jetzt gebunden das Problem mit weniger Eingängen. Statt 26, lassen Sie uns tun Sie etwas weit weniger mit nur sagen, sieben, hinter Diese Türen, sozusagen. Gibt es nur sieben Nummern? Und wenn das Ziel nun bei Hand ist, um einen Wert zu finden, mal sehen, wie effizient können wir dabei vorgehen. Und lassen Sie uns, wenn wir können jetzt sehen, beginnen, einige Zahlen gelten, oder einige Formeln, mit denen zu beschreiben, die Effizienz unserer Telefonbuch Algorithmus unserer Prüfung Buch-Algorithmus, und allgemeiner, der Suche nach Informationen. Also, für dieses, lassen Sie mich los, und auf dem Touchscreen hier, legte einen Web-Browser, hat genau diese sieben Türen. Und wenn wir einen anderen zu gelangen freiwillig zu über hierher kommen, Ich habe die gleichen Türen hierher setzen. Schnell Freiwilligen. Diese one-- Demos gehen ein schneller und schneller jetzt. Komm runter. Wie heißen Sie? TREVOR: Trevor. David J. MALAN: Trevor? In Ordnung, Trevor, komm nach unten. So Trevor hat hier, um sich freiwillig tun ein ähnliches Problem, aber eine, die ist weniger umfangreich, und das wird , damit wir versuchen nun zu formalisieren der Prozess zum Sortieren dieser Zahlen. So Trevor, schön dich zu treffen. Also hier ist ein Array, so zu zu sprechen, eine Liste der sieben Türen. Gehen Sie weiter und finden Sie uns die Nummer 50. Und dann, nachdem die Tatsache, Erklären Sie uns, wie Sie es gefunden. Sollte be-- alles in Ordnung. Ja, das ist das hier? UH Oh. OK. Sie geklickt haben, dass man. Gut. Und gut. Jetzt klickten Sie, dass man. Und lassen Sie mich Ihnen das Mikrofon, so dass Sie es in nur einem Augenblick. Gehen Sie weiter und klicken Sie auf die nebenan, die Sie beabsichtigen. Ja gut. TREVOR: Kann ich unclick einer Tür? David J. MALAN: Nein, Sie unclick können. TREVOR: OK. Dieses hier. David J. MALAN: Wo wollen Sie hin? Welcher? TREVOR: Dass man. David J. MALAN: Nein TREVOR: OK. Dieses hier. David J. MALAN: Ja. Das war gut. Gut. Also, was war Ihr Algorithmus oder Verfahren, dies zu tun, Trevor? TREVOR: Ich ging durch Türen bis ich eine 50. David J. MALAN: OK. Excellent-Algorithmus. So ist das in Ordnung. Denn in der Tat, wenn ich zeigen, was ist hinter den beiden anderen Türen, was wir hier finden, ist, dass wir haben nur zufällige Eingabe. Das war also tatsächlich als gut, wie Sie bekommen konnte. Und in der Tat, Sie haben besser als erschöpfend Suche das gesamte Array, denn es wäre wirklich gewesen sein Pech, wenn Sie die Anzahl getroffen hatte 50 im letzten Tür. Aber was, wenn wir statt hat Ihnen eine Annahme. Angenommen, ich Art alle diese Türen herum, so dass Sie die Nummern sortiert diese Zeit, aber dieses Mal ist es eigentlich a different-- dieses Mal, es ist eigentlich für Sie sortiert. Und jetzt das Ziel bei der Hand ist es, die Nummer 50 treffen. TREVOR: OK. David J. MALAN: Was ist Ihr Algorithmus sein wird? TREVOR: Nun, wenn es sortiert, dann ist es entweder gehen um be-- wenn größten bis zum größten, absteigend, es wird der erste sein, oder ob es im Gegenteil, es wird die letzte sein. Also werde ich tippen Sie einfach auf diese Tür, und dann tippen Sie einfach auf die letzte Tür. David J. MALAN: Ausgezeichnet. Gut. So fanden wir die Zahl 50. So, sobald Sie wusste, sie sortiert wurden, werden wir konnten diese Annahme zu nutzen. So dass sie zu viel wie das Telefonbuch Beispiel. Sobald Sie auch mit haben ein kleines Problem wie dieses, Ihre Eingaben vorsortiert, können wir tatsächlich den Wert wohl finden effizienter. Und ich wollte nicht sagen, ob es sortiert klein bis groß oder groß bis klein, und so war es sehr angemessen an einem Ende oder dem anderen starten tatsächlich feststellen, dass Sollwert. Also danke an Trevor auch. Und ich werde schön gemacht propose--. Wir haben einen kleinen Clip, eigentlich, daß gehört zu unseren Lieblingsmomente in CS50, wobei manchmal diese Demos nicht ganz nach Plan. Und in der Tat gerade jetzt, ich die falsche Schnittstelle gezogen , mit denen Sie den Touchscreen verwenden. Das war also meine Schuld gibt. So wird dies für zu machen im nächsten Jahr Clip als , warum ich Sie auf meiner eigenen Bildschirm. Aber lassen Sie uns einen kurzen Blick auf das, was im letzten Jahr geschehen ist mit Jay, der kam, viel wie Trevor hier, freiwillig, und in diesem kurzen Clip, sehen Sie, wie diese gleichen Demo nicht ganz offenbaren die gleichen Erfahrungen. [VIDEO PLAYBACK] -Alle Ich möchte Sie zu tun ist jetzt für mich zu finden, und für uns, wirklich, die Zahl 50 ein Schritt auf einmal. -Die Zahl 50? -Die Zahl 50. Und man kann zeigen, was ist Hinter jeder dieser Türen einfach durch Berühren mit einem Finger. Verdammt. [Lacht] [END PLAYBACK] David J. MALAN: Also, die sehr gut ging. Das waren die unsortierten Türen. Jay und, natürlich, fand es viel zu schnell. Trevor hat eine viel bessere Arbeit in Bezug auf ein Aha-Erlebnis, so zu sagen, in diesem Jahr in länger dauert, sie zu finden. Natürlich, dann gaben wir Jay eine zweite Chance, wobei wir nach die Türen, genauso wie wir für Trevor hat, und Trevor war super gut diese Zeit. Aber Jay habe es halb so schnell. [VIDEO PLAYBACK] -Das Ziel ist es nun auch finden Sie uns die Nummer 50, aber tun Sie es algorithmisch und Erklären Sie uns, wie Sie über sie gehst. -OK. -Und Wenn Sie es finden, halten Sie den Film. Wenn Sie es nicht finden, geben Sie zurück. -Man. Oh! - [Unverständlich] OK. Also werde ich, um die Enden zu überprüfen zuerst, wenn there's-- um festzustellen, Oh. [Applaus] [END PLAYBACK] David J. MALAN: OK. So sortieren Türen deutlich führt zu einer höheren Effizienz. Und so doppelt so schnell ist das, was ich da gedacht. Und so Jay hatte Glück beide Male. Und er hat auch das Glück in diesem letzten Jahr bestellte ich einige Blu-ray Discs tatsächlich zu geben. Es tut mir leid wir dieses Jahr hatte nicht die gleichen, Trevor. Aber noch besser war ein paar Jahre zurück. Und einige von euch vielleicht wissen Kerl, Sean, der, als er in CS50 war, wurde mit der genauen fochten gleiche Problem, wenn auch in SD, wie Sie bald sehen werden, wieder in den Tag. Und Sie werden feststellen, dass nicht nur er ein wenig länger als Jay zu nehmen, ein wenig länger als Trevor war es eigentlich diese wunderbare Gelegenheit zu fast jeder in der Eingriffs Zuschauer A-la-Preis ist, die Förderung ihm, die Zahl, die wir suchten zu finden. Lasst uns. wir einen kurzen Blick. [VIDEO PLAYBACK] -OK. So Ihre Aufgabe hier, Sean, ist die folgende. Ich habe hinter diesen verborgen Türen die Zahl Sieben. Aber versteckt in einige dieser Türen sowie auch andere negative Zahlen. Und Ihr Ziel ist zu denken, der oberen Reihe von Zahlen nur als ein Array, oder einfach nur Sequenz von Papierstücken mit Zahlen hinter ihnen. Und Ihr Ziel ist, nur mit dem Top- Array hier finden mir die Nummer sieben. Und wir werden dann werde Kritik wie Sie es tun. -Gut. -Finden Uns die Nummer sieben, bitte. Nein. Fünf, 19, 13. [Lacht] Es ist nicht eine Fangfrage. Ein. [Lacht] An diesem Punkt ist die Punktzahl nicht sehr gut, so dass Sie könnte genauso gut weiterzumachen. Drei. [Lacht] Mach weiter. Ehrlich gesagt, kann ich nicht helfen, aber frage mich, was du überhaupt darüber nachzudenken, SO- [Lacht] Nur die obere Reihe, so Sie haben drei links bekam. So finden Sie mich sieben. [Lacht] 17. Sieben. [Applaus] Gut. [END PLAYBACK] David J. MALAN: so konnten wir Sehen Sie diese den ganzen Tag lang. Und natürlich einige diesjährigen Demos vielleicht wird nun am Ende in der nächsten jährigen Video. So, jetzt wollen wir eigentlich konzentrieren sich auf die Algorithmen hier, und sehen, ob wir nicht jetzt damit beginnen, zu formalisieren wie wir darum unsere Daten gehen in diesen Zustand, dass es sortiert, so dass letztlich, können wir tatsächlich suchen sie effizienter. Und auch wenn wir gehen um relativ kleine Datenmengen zu verwenden, wie die acht Zahlen, die wir habe hier auf dem Brett, letztlich dieselben Ideen gelten könnten 1000 Eingänge, eine Million Eingängen 4 Milliarden Eingänge weil die Algorithmen gehen, um im wesentlichen der gleiche sein. Und dies ist unsere letzte Gelegenheit für die Freiwilligen heute aber vielleicht die Beteiligten ein, für die wir acht Freiwillige zu kommen und gehen uns durch die Prozess des Sortierens, was bald werden auf diese Musik steht hier. Lassen Sie mich hier starten. So eine in der turquoise-- grün ist das? Sind Sie zu begehen? Zwei. Komm runter. OK. Drei. Four. Lassen Sie mich- OK, fünf. Sie sind von Ihrem Freund nominiert. Sechs, sieben und acht. Komm auf. Gut. Vielen Dank. Komm auf. Komm auf. Gut. Also, was wir hier-- und dies haben gehört zu den mehr umständlich diejenigen, da dies Humor verlangen, dass Sie mich nur ein wenig Zeit. Sie müssen die Nummer eins sein. Wie heißen Sie? Annan Annan. David J. MALAN: Annan. David. Wie heißen Sie? JOSEPH: Joseph. David J. MALAN: Joseph, Sie sind die Nummer zwei. SERENA: Serena, Nummer drei. Stefan, Nummer vier. CYNTHIA: Cynthia. David J. MALAN: Cynthia, Nummer fünf. [Unverständlich] David J. MALAN: [unverständlich]. David, Nummer sechs. MATT: Matt. David J. MALAN: Matts Nummer sieben. Und? WAVERLY: Waverly. David J. MALAN: Waverly, Nummer acht. Gut. Wenn Sie could-- hoppla. Wenn Sie allen, wie Ihre erste Herausforderung besteht acht Notenständer hier dem Publikum zugewandt. Wenn Sie Ihre Zahlen auf setzen könnte Diese Musik steht in der Weise dass sie eine Linie mit der gleichen Zahlen auf dem Brett. Also macht euch so aussehen durch setzen Sie Ihre Zahlen auf diese Musik steht hier. Ausgezeichnete so weit. Ausgezeichnet. OK. So, jetzt werden wir die Fragen Frage in ein paar verschiedene Möglichkeiten. Wie können wir über das Sortieren gehen diese Leute hier? Denn wir hatten ein paar Ansätze zuvor, wobei wir waren Art der Herstellung von zwei verschiedenen Eimern. Und dann waren wir in der Regel Setzen Dinge zusammen. Sobald wir zwei Zahlen sah, dass zusammengehörten, wir sie zusammen. Zwei Briefe, die zusammengehören. Aber lassen Sie uns, wenn wir sehen kann nicht formalisieren diese, so dass wir letztlich einige Pseudocode man so will, mit denen Sie diese Probleme lösen. So, jetzt bin ich auf der Suche auf diese Zahlen hier. Und ich sehe eine ganze Reihe von Fehlern. Letztlich möchte ich eine auf die links und acht auf der rechten Seite. Und so sehe ich auf diese beiden, vier bzw. zwei. Und was ist das Problem offensichtlich? Ja. Also. Zwei offensichtlich geht vor vier, so dass Sie wissen, was? Lassen Sie mich zunächst einen gierigen Ansatz, wenn man so will, ähnlich wie Problem gesetzt one--, wenn Sie an die erinnern, Standard Edition von Problem Set One, wo ich gerade vor Ort das Problem zu lösen das ist genau hier vor mir und sehen, wohin es mich führt. OK. Also zwei und vier, lass mich gehen voran und gerade tauschen Sie zwei. Wenn Sie körperlich bewegen kann euch selbst und eure Papier, Ich scheine das bekommen haben, Liste in einem besseren Zustand. Nun, sie sind gut. Ich werde weiterziehen, vier und sechs, sieht gut aus. Kein Problem. Sechs und acht, OK. Acht und ein anderes Problem. Denn was ist wahr, etwa acht und eine? Man kommt vor acht, und so was sollen wir tun? Lassen Sie uns tauschen diese beiden. Einem und acht. Und nun, ich werde weitermachen. Ich werde auch in Zukunft vor uns. Und lassen Sie uns sehen, was passiert. Acht und drei, von Natürlich nicht in Ordnung. Lassen Sie uns tauschen. Acht und sieben, natürlich. Außer Betrieb. Lassen Sie uns tauschen. Acht und fünf natürlich Lassen Sie uns tauschen. Gut. Liste sortiert ist. ja? OK, offensichtlich nicht. Aber es ist ein wenig besser, nicht wahr? Weil Hinweis, was passiert ist. Jedes Mal, wenn eine Swap, führten wir ein kleineres Anzahl Art versickert so, und eine größere Anzahl versickert auf diese Weise, oder wir beginnen die sprach zu den sprudelte nach links oder nach rechts geleitet. Nun, es ist nicht genug, denn im besten Fall eine Reihe könnte haben eine Stelle verschoben nach vorn, oder im schlimmsten Fall, einige haben könnte bewegt eine Stelle weiter. Damit Sie wissen, was diese Art der funktionierte ziemlich gut so weit. Lassen Sie mich nur versuchen Sie es erneut. Zwei und vier, sie sind OK. Vier und sechs, sie sind OK. Sechs und eine, in der richtigen Reihenfolge. Also lassen Sie uns tauschen Sie zwei. Und nun, bemerken das Problem der beginnen, wieder ein wenig besser. Sechs und drei, nicht in Ordnung. Lassen Sie uns tauschen Sie zwei. Sechs und sieben, du bist gut. Sieben und fünf, natürlich, nicht in Ordnung. Sieben und acht, in Ordnung. Und jetzt, könnte ich brauchen, tun dies noch ein paar Mal. Und in der Tat, ich denke für euch selbst vielleicht, wie oft maximal vielleicht habe ich hin und her zu gehen? Wir werden darauf zurückkommen. Also zwei und vier sind noch OK. Vier und eine, nein. Also, lassen Sie Swap. Und wieder feststellen, optisch man ist Art von Blasenbildung nach links, wo es sein sollte. Vier und drei Swap. Vier und sechs. Sechs und Fünf-Swap. Sechs und sieben. Sieben und acht sind gut. Gut. Wir sind immer noch besser. Also mal sehen. Jetzt haben wir zwei und eins. Natürlich tauschen. Zwei und drei, drei und vier, vier und fünf, sechs und sieben, sieben und acht. Gut. Und wissen Sie was? Weil ich eine Änderung gibt, lassen Sie mich eine Plausibilitätsprüfung zu tun. Lassen Sie mich den ganzen Weg gehen zurück zum Anfang. OK. One, two-- yup, sehen? Irgendetwas stimmte nicht. Drei, vier, fünf, sechs, sieben, acht. Und in dieser letzten Pass, sind Sie sind komfortabel mit meinem jetzt behauptete, es wird sortiert? OK. Optisch, das ist absolut wahr. Aber funktional, was haben auch nur zufällig in diesem letzten Durchgang, das Ihnen erlaubt , um zu bestätigen, dass diese Liste ist in der Tat sortiert? Was habe ich getan oder nicht tun, diese letzte Pass? Publikum: Es gab keine Veränderungen. David J. MALAN: Es tut uns leid? ZIELGRUPPE: Keine Änderungen. David J. MALAN: Es gab keine Veränderungen. So wäre es dumm von mir, Tun Sie das gleiche Algorithmus wieder wenn ich nicht machen jeden ändert sich die erste Zeit. Und der Zustand nicht geändert hat. Sicherlich werde ich nicht zu machen beliebige ändert das zweite Mal. Und so ist es jetzt sicher zu sagen, ist die Liste sortiert. Und in der Tat ist dies nun etwas, dass wir in der Regel Call Bubble Sort, wobei paarweise, Sie Fehler wieder zu korrigieren, und wieder, und wieder, und Sie fahren Sie hin und her, und hin und her, bis Sie machen keine solchen Swaps, an welcher Stelle Sie können sicher sein, yeah, I fertig zur Festsetzung alle Fehler. Lassen Sie uns zurückzusetzen, und versuchen Sie einen anderen Ansatz. Wenn euch könnte in zurück die Reihenfolge vor einem Augenblick waren, die so ausgesehen. Nun, lassen Sie uns einen Ansatz ein wenig mehr wie die Prüfung Buch wobei wir ständig waren Auswahl der Buchstabe des Alphabets dass wir irgendwie wollte mit weiter beschäftigen. Vielleicht war es ein Hoch Brief, wie A, oder einem niedrigen Buchstaben Z. So dass jeder ist wieder in dieser Reihenfolge. Und jetzt lassen Sie mich dies zu tun. Mal sehen, ich weiß, ich habe acht Zahlen hier. Ich werde weitermachen und nur bewusst wählen die kleinsten Elemente. Recht? Dies scheint auch intuitiv. Warum kann ich nicht das kleinste finden Element, setzte es, wo es gehört, dann die nächste kleinste Element, setzen es, wo es hingehört, und einfach zu wiederholen. Weil intuitiv, das auch funktionieren sollte. So vier, das ist eine ziemlich kleine Zahl. Ich werde daran erinnern, wo das ist. Warte eine Minute. Zwei ist kleiner. Lassen Sie mich daran erinnern, wo zwei ist, und vergessen Sie vier. Wir beginnen mit, dass später. Sechs, ich bin nicht daran interessiert. Acht, ich bin nicht daran interessiert. Eines ist meine neue kleine Zahl. Also werde ich zu erinnern, wo man ist. Drei, nicht interessiert. Seven, nicht interessiert. Fünf, nicht interessiert. Also, ohne herunterzufallen die Bühne in diesem Jahr, Ich werde Nummer greifen one-- und was war Ihr Name? Annan Annan. David J. MALAN: Annan. Und wenn könnten Sie mir bei beitreten der Anfang der Liste, sagen wir Ihnen, wo Sie hingehören. Unfortunately-- was ist Ihr Name? Stefan: Stefan. David J. MALAN: Stefan im Weg ist. Also, bevor Stefan löst dieses Problem Problem, was sollen wir tun? Was machen wir mit Stefan? ZIELGRUPPE: [unverständlich]. David J. MALAN: OK. So konnten wir das tun. Wir könnten eine Art nehmen Stefan und seine vier, und nur ihn in einer Variablen und halten Sie auf, um es für eine gewisse Menge an Zeit, wodurch Raum für die Nummer eins. Und das ist nicht schlecht. Ich könnte vorschlagen, warum nicht wir haben gerade Stefan hier? Warum könnte dies verletzen einem der Ideen, die wir begonnen reden über das letzte Mal, letzte Woche? Ja? ZIELGRUPPE: [unverständlich]. David J. MALAN: Es gibt keinen Index für sie. Wenn Sie denken, dies in der Tat als Array, das ist wie negative, so gibt es keine Speicher tatsächlich Falls dies tatsächlich ein Array, wie wir es in der vergangenen Woche erklärt, in der Vorlesung. Also sollten wir nicht tun. Wir könnten sie in einer Variablen speichern. Oder wissen Sie was? Ich hörte jemanden schlage es. Was können wir tun, mit Stefan? Warum gehen wir nicht ihn einfach zu vertreiben und legte ihn auf, wo die Nummer eins war. Also, wenn Sie dort gehen wollen. Und in der Tat ist dies ein ziemlich gute Lösung. Jetzt auf der einen Seite, ich habe Art der machte das Problem noch schlimmer. Vier ist jetzt weiter weg von wo es sein sollte. Es sollte zu dieser Hälfte. Aber wissen Sie was? Das hätte Pech haben. Vielleicht Nummer acht war hier. Und so, vielleicht würden wir Glück haben bekommen, und schob acht näher zum Ende. So dass am Ende des Tages, es irgendwie alle mittelt. Wir brauchen nicht zu etwa vier kümmern. Mich interessiert im Augenblick Auswahl der kleinste Element. Und nun, was ich zu gehen zu tun ist über die Nummer eins vergessen dauerhaft, weil ich weiß, die Liste hinter mir ist nun sortiert. So war meine Liste zuvor Größe acht. Jetzt ist es an der Größe sieben. Also mein Problem ist, kleiner, wenn auch linear. So, jetzt werde ich die wählen Strom kleinste Element, zwei. Sechs, acht, vier, drei, sieben, fünf. Das war das kleinste Element. Also, was soll ich nur tun mit-- Was war Ihr Name? JOSEPH: Joseph. David J. MALAN: Joseph? Wir werden Joseph an ihrem Platz bleiben. Nun, ich werde so tun, dass diese Jungs sind-- auch, Ich weiß, daß diese beiden bereits sortiert. Lassen Sie uns jetzt konzentrieren sich auf die Rest der Liste. Six ist der aktuelle kleinste. Acht ist größer. Vier ist jetzt der aktuelle kleinste. Drei ist jetzt der aktuelle kleinste. Und nun, ich werde drei auszuwählen, die ist--, was wiederum heißt du? SERENA: Serena. David J. MALAN: Serena, wenn du könntest Schnappen Sie sich Ihre Nummer und Swap mit-- Kelsang: Kalsang. David J. MALAN: Kalsang. Komm zurück, und wir sind gehen, um diese beiden zu tauschen. Und jetzt lassen wir diese auf Autopilot. Ich werde gehen und überlassen es euch auf die nächste kleinste Elemente auszuwählen. Dun dun, dun, dun. Nummer vier, was sollte man tun? Ausgezeichnet. Nun, ich werde einen anderen Pass zu machen. Dun dun, dun, dun. Ich sehe fünf ist die nächste kleinste. Nun, ich werde wieder einen einzigen Pass ab. Dun dun, dun, dun. Sechs am kleinsten ist. Gut. Sieben am kleinsten ist. Kein Wechselgeld. Acht am geringsten ist. Fertig. Also, was wir gerade durch iteratives getan Auswählen eines Elements nach dem anderen ist etwas, das wir umsetzen gehen, um als Auswahl Art zu formalisieren. Und es ist vielleicht sogar einfacher zu erklären, im wahrsten Sinne des Wortes, dass alles, was Sie tun möchte, ist einfach weiter hin und her durch die Liste Auswahl, die nächste kleinste Element, , bis Sie fertig sind. So ist es sogar noch einfacher, vielleicht intuitiv, als im letzten. Lassen Sie uns versuchen eine letzte. Wenn euch könnte euch selbst zurückzusetzen in die folgenden Positionen ein letztes Mal, mal sehen, ob wir nicht Jetzt formalisieren einen anderen Ansatz. In der Tat, jemand würde da draußen gerne vorschlagen Wie sonst könnten wir dabei vorgehen? Ohne das Werfen aus Schlagwörtern oder sort der Antworten, die bereits bekannt sind, nur intuitiv, was können wir tun? ZIELGRUPPE: [unverständlich]. David J. MALAN: Ja. So gibt es einige große Intuition gibt. Gute Dinge scheinen bisher geschehen in der Informatik, als wir zu teilen und erobere das Problem der Teilung es halb und halb und halb. Und so in der Tat, wir beginnen konnte, das zu tun. Und in der Tat, das wird sein, werden wir sehen eine unserer besten Lösungen vor. Aber lassen Sie uns zurückkommen, bevor lang. In der Tat, wir werden tun, dass ein wenig später in dieser Woche. Was könnten wir tun, um dieses Problem zu lösen? So dass jeder hier in scheinbar zufälliger Reihenfolge. Weißt du was? Anstatt hin und her, hin und her, hin und her, jedes Mal, fühlt sich das wie Ich mache eine Menge zu Fuß. Warum kann ich nicht gerade am Start der Anfang der Liste, und hat gerade vier, wo es hingehört? Also lassen Sie mich für den Moment annehmen, dass meiner Liste ist nur das erste Element. Wird vier in diesem Moment in der Zeit sortiert, wenn alle mich interessiert, ist hier alles? Dies ist eine Art trivialerweise richtig, oder? Wie die Liste, die eine Nummer und dass die Nummer vier ist natürlich sortiert. Also lassen Sie mich nur vor, dass diese Liste sortiert ist. Aber jetzt habe ich den Rest dieser Liste. So, jetzt, begegne ich zwei. Woher kommt zwei offensichtlich gehören in Bezug auf vier? Vor vier. Also, was kann ich hier machen? Was ist dein Name nochmal? JOSEPH: Joseph. David J. MALAN: Joseph, wenn Sie zurücktreten konnte für einen Moment mit Ihrer Nummer. Und nun, was soll Stefan hier? Lassen Sie uns zu verlagern Stefan hier. Und nun lassen Sie Joseph kommen hier rein. Und jetzt lassen Sie mich behaupten, hier ist alles sortiert. So ähnliches Ergebnis, sondern eine grundlegend anderen Ansatz. Ich habe nicht einmal sah was da unten ist. Ich habe gerade halten, die die Elemente wie sie mir übergeben, und mit ihnen umzugehen. So, jetzt sehe ich die Nummer sechs. Wo steht die Nummer sechs gehören? Wir haben zwei, vier, sechs. Genau dort, wo sie im Augenblick. Also lassen wir das allein, und jetzt behaupten, dass dieser Teil der Liste wird nun sortiert. Und so fühlt sich dieser grundlegend dadurch gekennzeichnet, dass unterschiedliche ich bin einfach Bewegen sich hier durch die Liste linear, und ich werde nie wieder zu verdoppeln. Ja. Gut. So acht, wo gehören Sie? Genau hier. Perfect. So, jetzt, ein. UH Oh. Das fühlt sich an wie es ist wird teuer. Jetzt im vorherigen Algorithmus Ich habe gerade vertauscht Personen. So könnte ich ihn legte den ganzen Weg der Anfang, aber dann zog Joseph. Aber wenn ich Joseph bewegen, jetzt was los ist, falsch sein? Art undone-- Ich habe jetzt, ich habe genommen einen Schritt nach vorn und dann einen Schritt zurück, denn jetzt Joseph wäre nicht in Ordnung zu sein. Also lassen Sie uns dies tun. Wenn Sie könnten die Nummer eins zu nehmen und Schritt zurück für einen Moment. Wie können wir das, was put-- war Ihr Name? Annan Annan. David J. MALAN: Annan vorhanden? Was muss sich in Bezug passieren zwei, vier, sechs und acht? Sie alle brauchen, um zu verschieben. Also, wenn acht möchten verschieben zuerst, dann sechs, dann vier, dann zwei. Und dann Annan, wenn Sie möchten, gerne hierher in, gut. Aber hier, nur haben wir einen Preis Art von bezahlten an einem anderen Punkt in dem Algorithmus. Der Erwägung, dass das letzte Mal mit einer Auswahl Art und sogar Bubble Sort, Ich gehe zurück zu Fuß und her, hin und her, die sicherlich Addition wird zeitlich und buchstäblich schrittweise. Insertion Sort, auf den ersten Blick sieht wie es ist Super-intelligenter, dass ich bin einfach schleppend, inkrementelle Fortschritte, aber ich bin nicht hin und her gehen diese. Aber wenn jemand in der Tat außer Betrieb, Ankündigung alle von der Arbeit musste ich einfach zu tun. Ich musste die Hälfte der Liste zu verschieben nur, um Platz für die Nummer eins zu machen. So ist es die gleiche Menge Arbeit so weit es fühlt sich, nur eine andere Art von Arbeit. Lass uns weitermachen. So, jetzt wissen wir, dass jeder zwischen einem und acht werden sortiert. Hier habe ich die Nummer drei. Wenn Sie zu holen mögen Nummer drei, Schritt zurück ein. Und was euch tun müssen? Yep. Also das ist eine andere ein, zwei, drei Schritte. Drei Zeiteinheiten, die nur kosten mir, so dass drei können jetzt passen. Schließlich sieben. Lassen Sie uns gehen Sie voran und haben Sie einen Schritt zurück. Dies ist nur zu uns kosten eine Einheit von Zeit, aber das ist OK. Und nun, fünf geht um ein wenig teurer. Wenn Sie möchten, einen Schritt zurück. Wir müssen uns bewegen, acht, und sieben und sechs. Und dann jeder ist jetzt sortiert. So eine große Hand, um unsere Freiwilligen hier. Vielen Dank. [Applaus] Danke euch allen. Danke euch allen. Also lassen Sie uns jetzt, wie zu sehen teuer das alles war. Betrachten wir vielleicht die einfachste davon, Bubble-Sort. Und ich sage einfachsten, nur, weil Sie können es gierig von nur lösen befestigen Sie den paarweisen Problem hier. Befestigen Sie den paarweisen Problem Hier wieder wieder, wiederkehr so ​​viele Male, wie Sie tatsächlich benötigen, um. So stellt sich heraus, dass mit einem Bubble-Sort, na ja, wie viele Schritte muss ich zu übernehmen der erste Durchgang dieses Algorithmus? Ich könnte take-- wir see-- ein, zwei, drei, vier, fünf, sechs, sieben. Und es gibt acht Elemente hier. So ist es wie n minus 1 vor, um erhalten aus dem Anfang der Liste an das Ende der Liste. Aber mit Selection Sort, daran erinnern, dass ich Auswahl der Elemente wieder und wieder wieder, dass der kleinste, Ich stelle es fest, aber dann bin ich nicht Blick hinter mich wieder. Also ich denke, es ist ein wenig mehr klar, dann, dass das erste Mal, ich könnte müssen alle n minus 1 Schritte zu unternehmen, um das kleinste Element zu finden. Dann legte ich sie an ihrem Platz, und ich zu vertreiben, wer zuvor war hier. Aber dann weiß ich nicht zu haben, auch in Zukunft auf diesem Element, weil ich weiß, es ist bereits die kleinste. So, jetzt kann ich bei nur sieben suchen Elemente, dann sechs Elemente, dann fünf Elemente, dann vier Elemente. Und so mathematisch wenn n die Anzahl von Elementen oder Zahlen dass wir mit gestartet wird, können Sie sich vorstellen dass dies dasselbe wie n minus 1, plus n minus 2 Stufen, plus n minus 3 Stufen, plus n minus 4 Schritte, die ganze bis hinunter zu nur einem Schritt. Und ich bin auf meinem letzten Person. Und wenn Sie sich erinnern, dass viele der Statistik Bücher oder mathematische Bücher haben diese Formeln auf dem Hardcover Rücken oder vor ihnen, es stellt sich heraus, dass dieser Serie kann einfacher ausgedrückt werden als n mal n minus 1 mehr als 2. Und es ist in Ordnung, wenn das nicht an der Spitze Ihres Geistes. Aber das ist wohl wahr. Das ist nur ein einfacher Weg, es zu schreiben. Und dann, wenn Sie denken zurück zur Grundschule, wenn Sie gerade beginnen Multiplikation Dinge, in diesem Fall natürlich, wird nur n Quadrat minus n dividiert durch 2. Alles, was ich getan habe, ist zu erweitern die Ausdrücke gibt. Und so lassen Sie uns dies umschreiben ein wenig anders. Das ist n Quadrat geteilt durch 2 minus n / 2. Also noch einmal, ich bin nur Art von Anwendung einige Rechenregeln gibt. Aber jetzt feststellen, dass der größte Begriff in diesem Ausdruck sozusagen ist, dass n quadriert. Also ja, es ist n squared dividiert durch 2 minus n / 2. Aber in der Regel, wenn n wird ein großer Wert sein, Ich werde behaupten, dass n quadriert wird sich der dominierende Faktor sein. Es ist nur los zu sein einen größeren Beitrag um die Anzahl von Schritten als n / 2 ist. Also, was kann ich damit? Versuchen wir ein einfaches Beispiel, auch obwohl die Mathematik ein wenig groß. So nehme an wir hatten 1 Million Menschen auf der Bühne, oder 1 Million Dinge , dass wir wollen, um zu sortieren. Lassen Sie uns stecken Sie ein Millionen in genau dieser Formel um zu sehen, wie viele Schritte es braucht insgesamt eine Million Elemente zu sortieren mit sagen wir, Auswahl sort. So würden wir die gleiche Formel wie zuvor. Ich würde eine Million stecken, so dass ich Million Quadrat geteilt durch 2, minus Million geteilt durch 2. Wenn ich das tue, Mathematik im Voraus Hier haben wir 500 Milliarden minus 500.000, die gibt uns 499.999.500.000, Das ist verdammt groß. In der Tat, wenn Sie jetzt vergleichen 499 Milliarden, 999 Millionen, 500.000 gegenüber unseren ursprünglichen Wert, 500 Milliarden, es ist so verdammt nah. Recht? n squared von 2 gibt aufgeteilt us-- oder vielmehr n Quadrat geteilt durch 2 gab uns 500 Milliarden. Das ist verdammt nah um 499.999.500.000, was zu sagen, Subtraktion off 500.000 ist, oder allgemeiner Subtrahieren n quadriert, nicht wirklich eine große Sache. Die n quadriert macht diese Zahlen wachsen wirklich schnell. Nun, dies ist nur insofern von Bedeutung, wie wir als Informatiker, werden in der Regel nicht zu so viel Pflege über die Feinheiten dieser Formeln und genau das, was die präzise Antworten gibt. Wir kümmern uns nur das, weißt du was? Am Ende des Tages, diese Formel liegt in der Grßenordnung von n quadriert. Ja, wir sind um 2 Teilungs drin. Ja, wir Subtraktion off n minus 2. Aber am Ende des Tages wird der Begriff dass wirklich weh tut uns und kostet uns viele Stufen ist, dass quadratische tigen. Und was ein Informatiker wird sich in der Regel zu tun wird ignoriert alle, kleiner Auftrag AGB, und nur an der einen Blick, trägt am meisten zu den Kosten. Und das ist schön, weil wir können, jetzt in viel größerer Allgemeinheit sprechen über Algorithmen und sie zu vergleichen. Und die Tatsache, dass ich Verwendung dieser O ist gewollt. Als ich in der Größenordnung sagen von, ich bin speziell auf etwas beziehen genannten großen O. und Big O ist eine Notation, die einen Computer Wissenschaftler verwendet, um zu beschreiben eine obere an etwas gebunden. Also, wenn Sie sagen, dass ein Algorithmus ist in den großen O n quadriert, wie ich vorgeschlagen, nur eine Moment vor, dass Mittel dass in Bezug auf seine Lauf Zeit oder Effizienz, Es dauert in der Grßenordnung n quadriert Schritte. Vielleicht mehr, vielleicht weniger. Aber es ist in der Größenordnung von n quadriert. Und das ist die Obergrenze. Es wird nicht zu sein schmerzhafter als das. Es wird nicht n Würfel geschnitten zu sein, oder 2 zu der n, oder etwas viel größer. Dies ist eine obere Schranke auf, was das kosten wird. Also da, lassen Sie uns Sehen Sie sich nur ein paar Beispiele. Und dies ist nur eine endliche Liste der sehr häufige Laufzeiten für Algorithmen, die bedeutete, ist zu sein beispielhaft für einige Dinge, die wir schon gesehen. So zum Beispiel im Fall von Selection Sort, was ich hier behaupten, ist das ist Selection Sort Lauf Es ist in der Größenordnung von n quadriert. Im schlimmsten Fall, werde ich haben eine ganze Reihe von Zufallszahlen hier. Und wie wir mathematisch gesehen, wenn ich halten zu Fuß durch die Liste, durch die Liste, die Auswahl der nächstkleinere Element wieder und wieder, wenn ich eigentlich notieren alle Schritte Ich nehme, wie ich vorgeschlagen formel vor, dann ist es in der Größenordnung von n squared Schritte, die ich nehme. Und es stellt sich heraus, dass die Blase Art und Insertion Sort sind genauso langsam im schlimmsten Fall. Betrachten wir zum Beispiel Insertionsort, der letzte Algorithmus, den wir behandelt, die hatten uns auf dem Element suchen, und dann legen Sie sie, wo es hingehört. Und dann haben wir uns das nächste Element, und steckte ihn, wo es hingehört. So betrachten die bestmögliche Szenario. Angenommen, ich hatte meine Probanden antreten buchstäblich wie dieses, ein bis acht, bereits sortiert. Wie viele Schritte ist Insertion Sort dauern bis acht Personen sortieren, wenn sie auf der Bühne zu gelangen so aussieht? Acht Menschen bereits sortiert. Und ich verwende Insertion Sort. Das letzte der Algorithmen. Nun, lassen Sie nachspielen wirklich schnell. Also, wenn ich hier starten, sehe ich ein. Wo findet man gehören? Es gehört hier richtig. Ich sehe zwei. Wo kommt beiden gehören? Genau hier. Ich sehe drei. Wo kommt drei gehören? Genau hier. Ich sehe vier. Genau hier. Fünf, sechs, sieben, acht. Es gibt keinen Grund, mich zu wiederholen. Und so, wie viele Schritte ist, dass in Bezug auf die n? Es ist in der Größenordnung von n Schritte, nicht wahr? n minus 1. Aber ich nahm einen linearen Nummer von Schritten, und jetzt bin ich fertig. Also das ist der beste Fall, though. Was ist mit dem schlimmsten Fall? Welche acht waren dort, und sieben waren dort unten, und eins und zwei waren hier, so dass die Liste wurden wirklich umgekehrt? Nun, was tatsächlich geschieht, wenn dies die Zahl? Und wir werden nur ein paar Beispiele zu tun. Was ist, wenn in der Tat die Nummer acht ist hier, und die number-- hoppla. So was, wenn, ja, die Zahl acht ist den ganzen Weg hierher, und ich bin mit Insertion Sort? OK. Ich behaupte, im Moment ist es an Ort und Stelle. Aber jetzt, wo kommt seven-- sieben gehen? Selbstverständlich geht es hier. So habe ich mehr als ein Platz acht. Jetzt sechs, wo geht es hin? Nun, alles in Ordnung. Nun, ich muss mehr als acht bewegen ein Ort, sieben mehr als einem Ort, und dann plop ich mich sechs. Also das erste Mal, es Kosten mich noch einen Schritt, um Dinge zu reparieren, dann kostet mich zwei Schritte, um Dinge zu reparieren. Wie viele Schritte ist es zu ergreifen, um zu beheben Dinge zu fünf an der richtigen Stelle zu setzen? Drei. Denn jetzt habe ich bewegen ein, zwei, drei. Wie viele Schritte wird es zu nehmen vier an der richtigen Stelle zu setzen? 4 plus 5, plus 6 plus 7. Und so ist es mathematisch identisch was wir für die Auswahl Art beschrieben. Wir haben diese Serie das ist nur zu. 1 plus 2 plus 3 plus 4, oder umgekehrt, 7 plus 6 plus 5 plus 4 summiert sich für die heutige Zwecke in der Größenordnung von n quadriert. Also lassen Sie mich auch, dass vor, Bubble-Sort ist auch in n quadriert. Denn mit Bubble-Sort, jede Mal, wenn ich durch die Liste, Ich nehme etwa, wie viele Schritte? Jedes Mal, wenn ich buchstäblich zu Fuß von dort nach da? Etwa n Schritte. Aber wie oft ich könnte brauchen, um durch die Liste zu gehen? Nun, etwa n Zeit. Vielleicht n minus 1, aber in etwa n mal. Nun, warum ist das so? Nun, mit Bubble-Sort, wenn beginnen wir mit Bubble-Sort, mit der Liste im schlimmsten Situation, die wiederum völlig rückwärts, was passieren wird? Ich gehe durch die Liste, und die Anzahl man gehört ganz drüben. Aber mit Bubble-Sort, wie weit geht man bewegen an meinem ersten Durchlauf durch die Liste? Wie viele Flecken bekommt er näher an der richtigen Stelle? Nur einer. Also, wenn Sie Art von Grund durch diese, jedes Mal, wenn durch diesen Algorithmus, Davids unter etwa n Stufen. Aber wie viele Pässe durch die Liste, ist es gehen, um für ein bis Blase nehmen nach links, wo sie hingehört? Er hat sich wie bewegen, n Bereiche auf diese Weise. Also, nur um die Sortierung der Liste zu tun, Ich habe hin und her zu gehen n-mal. Und jedes Mal, ich bin Blick auf n-Elemente. So zu tun n Dinge, n-mal auf die Reihenfolge der n quadriert. Nun, wir werden sehen, in einigen der Shorts, sind in CS50 nächste Problem eingebettet gesetzt, einen anderen Ansatz zu diesen, aber für jetzt, lass uns einfach betrachten einige andere Laufzeiten, vor allem, wenn die Sortier diejenigen zu nehmen ein wenig Zeit zu sinken. Was ist ein Algorithmus, die wir bereits gesehen haben das dauert in der Größenordnung von n Schritten? Was soll eine lineare Reihe nehmen von Schritten, die wir bisher gesehen? Was ist das? Das Telefonbuch suchen. Der erste Algorithmus. Recht? Wo wir sind linear Suche nach Mike Smith? Tatsächlich. Von Woche null, als ich anfing, Drehen einer Seite zu einer Zeit, und ich habe sogar gesagt, dass es Art einer linearen Gefühl Algorithmus und wir hatten das Bild auf die Board mit dem gerade rote Linie und der gerade Gelb Linie, denen der Tat waren Algorithmen, die in den großen O n sind. Da Mike Smith in einem Telefon zu finden Buch der n-Seiten, im schlimmsten Fall, könnte mich n Schritte zu unternehmen. Was ist unter Teilnahme? Eins zwei drei vier fünf sechs. Was die Laufzeit diese Algorithmus, um die Anwesenheit? Big O n, denn in der Theorie I muss jeder im Raum zu zeigen. Jetzt als beiseite, was ist mit der weitere Optimierung von Woche Null? Zwei, vier, sechs, acht, 10, 12. Ein Informatiker würde zu realisieren, warten Sie eine Minute, das ist in der Größenordnung von n von zwei Schritte unterteilt. Recht? Da mache ich zwei Personen auf einmal. Aber wir werden ignoriert jene Terme niedrigerer Ordnung, und wir sind gerade dabei, wegwerfen, die durch 2, und nur sagen, große O n für diesen Algorithmus als auch. Was ist mit diesem? Wir werden übersprungen einige von ihnen, aber was war ein Algorithmus, der log n war? Das dauerte etwa log n Schritte? Die Teile und herrsche. Genau. Wie das Telefonbuch Beispiel in Woche Null und heute früh, wo wir unterteilt das Problem wieder und wieder und wieder. Wir zogen es auf dem Brett in der Woche Null als eine gekrümmte grüne Linie, und wir sagten, dass Tag war es einen logarithmischen Algorithmus. Und in der Tat ist die Anzahl der Schritte, die sie braucht, um divide durchzuführen und zu erobern, oder binäre Suche, wie wir beginnen nannte es, wie im Telefonbuch, liegt in der Grßenordnung von log und Stufen. Und das ist ein bisschen wie ein sonderbares. Was bringt einen Schritt, oder insbesondere eine konstante Anzahl von Schritten? Vielleicht ist es zwei, vielleicht ist es drei, aber ein Informatiker nur vereinfacht es so groß O von 1, einige konstante Anzahl von Schritten. Was ist etwas, was Sie tun könnten nimmt eine konstante Anzahl von Schritten? Was ist die Laufzeit klatschen? Konstante Zeit. Recht? Wie, was ist die Laufzeit alles, was nur einem statt tun Betrieb, wie zu drucken F Hallo Welt. Das könnte die konstante Zeit sein werden, es sei denn, weniger Ecke Fall mit Druck F, Was könnten die Laufzeit Druck F eigentlich sein? Und warum? Was ist n Mess in diesem Fall? ZIELGRUPPE: [unverständlich]. David J. MALAN: Genau. Die Anzahl der Zeichen Wir drucken möchten. Es ist also sehr kontextabhängig. Heute, wir haben konzentriert eine Menge auf Buchstaben und Zahlen hier auf dem Brett. Aber es könnte auch sein, Zeichen in einer tatsächlichen String. So stellt sich heraus gibt es eine andere Maßnahme, die beginnen wird die Sorge um, und das ist das Gegenteil von Big O, so zu sprechen. Das Omega-Notation. Wohingegen große O bedeutet, was ist, die Ober auf Ihrer Laufzeit gebunden? Maximal, wie viel Zeit könnte etwas dauern? Omega-- leid, dies kommt immer up-- ist das Gegenteil von dem, wobei es ein tiefer auf das gebundene Höhe der Zeit etwas könnten. Also. zum Beispiel, was ist ein Algorithmus das dauert immer n quadriert Schritte? Nun, einer der Algorithmen, die wir gesehen haben Heute, in der Tat könnte das so gut sein. Selection Art. Selection Art ist ziemlich dumm. Selbst wenn die algorithm-- leid, auch wenn das Array bereits sortiert ist, Auswahl Sortierung zu gehen halten zu Fuß durch die Liste um sicherzustellen, dass es die kleinste Element immer wieder und wieder. Und auch wenn man Menschen in der Publikum wissen, dass, warten Sie eine Minute, Sie bereits die kleinste Element, das Computer nicht weiß, dass, bis es sieht den ganzen Weg durch die Liste. Ebenso ist eine geringere, dass gebunden kann auch berücksichtigt werden, könnte lineare Zeit. Wie lange dauert es zu ergreifen, sort n Elemente in der besten Fall mit so etwas wie Bubble-Sort? Nehmen wir an, Ihre Liste bereits sortiert ist. Wir haben gesagt, Bubble-Sort nimmt die Reihenfolge der Schritte n quadriert. Aber was, wenn es bereits sortiert? Was, wenn Sie nach dem erkennen, einem Durchgang durch das Array dass Sie keine Swaps gemacht haben? Müssen Sie halten Sie macht mehr Durchläufe? Nein. So eine untere Schranke für Bubble-Sort gebunden könnte die linear ist. Omega von n. Und wir können betrachten andere von ihnen als gut. Werfen wir also einen Blick bei nur einer Visualisierung hier zu sehen, wie diese selbst zu unterscheiden. Ich werde hier unten in diese zu gelangen Seite, die auf C50-Website verfügbar ist, aber es wird ein Schmerz zusammen, um zu bekommen, da er verwendet eine Technologie namens Java-Applets, die a weitgehend nicht unterstützte in diesen Tagen, zumindest von Chrom und bestimmte andere. Und lassen Sie mich gehen Sie vor und beschleunigen diese und erklären, was vor sich geht. Dies ist eine Demonstration von Blasen Art, der erste Algorithmus sahen wir uns an. Und es ist eine Visualisierung, daß jedes dieser Stäbe eine Zahl. Je größer der Balken, Je größer die Zahl. Je kleiner der Bar, je kleiner die Zahl ist. Und was Sie visuell sehen kann, auch aber das wird super schnell, ist, dass der rote Balken ist wie ich, zu Fuß hin und her, Behebung von Problemen. Sie können, dass die größere Elemente zu sehen tatsächlich sprudeln nach rechts, und die kleineren Elemente sind an den linken sprudeln. Und hier unten, wenn wir tatsächlich näher betrachten, können wir tatsächlich zählen die Anzahl der Vergleiche und Swaps dass gemacht wurden. Aber anstatt, lassen Sie uns beim zweiten Algorithmus betrachteten wir früher mit unseren Freiwillige, die Auswahl sortieren. Optisch hat sie ein sehr unterschiedliche Wirkung. Aber es ist wiederum sehr intuitiv, in dass wir halten die Auswahl des nächsten kleinsten Element, und wir haben ein wenig Glück. Das fühlte sich grundsätzlich schneller. Wenn wir aber lief das immer wieder und immer wieder mit vielen Eingängen, würden wir sehen, dass es in der Tat noch in großen O n quadriert. Lassen Sie uns eine letzte hier, Insertion Sort, wobei der dritte Algorithmus sahen wir uns an, und Rückruf dass dies eine befasst sich mit der Elemente, wie es ihnen begegnet, aber dann ist es vielleicht Verschiebungen Dinge immer um Platz zu machen, Einfügen von Elementen, wo sie hingehören. Und auch dies endet geben die Endergebnis. Nun sind alle drei von denen, fühlte sich ziemlich schnell. Und in der Tat, ich lief davon an einem ziemlich gut Clip. Aber im Grunde sind sie alle ziemlich schrecklich, um ehrlich zu sein. Alle diese Algorithmen bisher dass Lauf in großen O n quadriert nehmen ziemlich viel Zeit, um am Ende laufen. Und in der Tat, können wir sehen, und denken, dass dies schließlich wenn ich nach oben ziehen diese dritte und letzte Demo. Dies ist ein weiterer Visualisierung Das wird zu Bubble Sort auf der linken Seite zeigen, Auswahl Art in der Mitte, und etwas, als eine unserer Hand hebt früher vorgeschlagen, Mergesort auf der rechten Seite. A Teile und Herrsche Strategie auf der rechten Seite. Und das ist in der Tat, was wir werde am Mittwoch zu suchen. Aber lassen Sie uns Zeit, um diese parallel laufen. Es ist etwa die gleiche Anzahl von Elemente, die alle laufen zur gleichen Zeit. Bubble-Sort vs Auswahl Art vs merge sort. Nun, sie alle laufen in der Theorie zur gleichen Zeit. Die CPU läuft an mit der gleichen Geschwindigkeit, aber man fühlen kann, wie langweilig das ist sehr schnell los zu werden, und wie schnell, wenn Wir spritzen ein wenig Woche Algorithmen, die Null kann wir Dinge zu beschleunigen. Und jetzt vergleichen lassen diese in eine letzte Form. Ich werde weitermachen In den CS50-Website, wo Wir haben dieses letzte Glied für heute, wo jemand auf dem Internet kindly zusammen ein Video, erfasst, was verschiedene Sortier Algorithmen klingen. Dies ist Insertion Sort. [PIEPTON] Wobei Sie Anlegen einer Frequenz sind auf der Grundlage der Höhe des Balkens bar. Dies ist Bubble Sort. [WARPED PIEPTON] Termine der nächsten ist-- kommen up next ist-- Selection Sort, wo wieder, wir Auswählen der nächste kleinste Element, und wir können sehen, es wächst von links nach rechts. Merge sort, unser Favorit bisher noch heute. Beachten Sie, wie es teilenden Dinge in [unverständlich] die Hälfte und Viertel. Gnome sortiert, das haben wir nicht darüber gesprochen, und schafft optisch und audally ein bisschen ein unterschiedliche Form und Ton. Hin und her, Reinigung Dinge. Sie können auch Heapsort auf der Internetseite dieses Kerls. Und das ist es. Wir werden Sie sehen, das nächste Mal. [Whooshing UND MUSIK]