[Powered by Google Translate] [Abschnitt 3 - komfortabler]
[Rob Bowden - Harvard University]
>> [Dies ist CS50. - CS50.TV]
>> Die erste Frage ist seltsam formuliert.
GDB können Sie "debuggen" ein Programm, aber, genauer gesagt, was macht es können Sie tun?
Ich werde antworten, dass ein, und ich weiß nicht, was genau erwartet,
so ich vermute, es ist etwas entlang der Linien von ihm können Sie Schritt für Schritt
Spaziergang durch das Programm, mit ihm interagieren, Variablen zu ändern, all diese Dinge tun -
grundsätzlich vollständig steuern die Ausführung eines Programms
und überprüfen Sie beliebige Teil der Ausführung des Programms.
Also diese Funktionen können Sie debuggen Dinge.
Okay.
Warum binäre Suche verlangen, dass ein Array sortiert werden?
Wer will darauf antworten?
[Schüler] Weil es nicht funktionieren, wenn es nicht sortiert ist. >> Ja. [Gelächter]
Wenn es nicht sortiert ist, dann ist es unmöglich, sie in zwei Hälften geteilt
und wissen, dass alles, was auf der linken Seite ist weniger und alles auf der rechten Seite
größer ist als der mittlere Wert.
So ist es sortiert werden muss.
Okay.
Warum ist Bubble Sort in O n squared?
Hat jemand wollen zunächst einen sehr schnellen Überblick auf hoher Ebene von dem, was Bubble Sort geben?
[Schüler] Sie haben grundsätzlich durch jedes Element gehen und prüfen Sie die ersten paar Elemente.
Wenn sie aus dem Sie tauschen sie sind, dann überprüfen Sie die nächsten Elemente und so weiter.
Wenn Sie das Ende erreichen, dann wissen Sie, dass das größte Element am Ende platziert wird,
so dass Sie ignorieren, dass ein dann los durch zu halten,
und jedes Mal, wenn Sie zu einem weniger Element zu überprüfen, bis Sie keine Änderungen vornehmen. >> Ja.
Es heißt bubble sort, denn wenn Sie das Array-Flip auf die Seite, sodass es bis und ab, vertikal,
dann die großen Werte werden auf den Boden sinken und die kleinen Werte Blase bis an die Spitze.
So ist es zu seinem Namen kam.
Und ja, man muss nur durchlaufen.
Sie halten durch das Array gehen, tauschen den größeren Wert
die größten Werte auf den Grund gehen.
>> Warum ist es O n squared?
Zuerst hat jemand sagen wollen, warum es O n Quadrat ist?
[Schüler] Da für jeden Durchlauf es n-mal geht.
Sie können nur sicher sein, dass Sie genommen haben das größte Element den ganzen Weg hinunter,
dann müssen Sie, dass für so viele Elemente wiederholen. >> Ja.
So im Hinterkopf behalten, was große O bedeutet und welche große Omega Mittel.
The big O ist wie die oberen, wie langsam es tatsächlich laufen gebunden.
So dass es entweder das durch O von n quadrierten, ist es nicht von n O oder aber es wäre in der Lage zu laufen
in linearer Zeit, aber es ist von n O cubed
weil sie von O n cubed begrenzt.
Wenn es durch O n squared begrenzt ist, dann ist es auch n cubed begrenzt.
So ist es n quadriert und in der absoluten schlimmsten Fall kann es nicht besser als n squared,
weshalb es O von n Quadrat ist.
So leichte Mathematik, wie es kommt, dass n Quadrat zu sehen,
wenn wir fünf Dinge in unserer Liste haben, zum ersten Mal, wie viele Swaps könnten wir möglicherweise benötigen, um
um sich das? Lasst uns eigentlich nur -
Wie viele Swaps werden wir gehen zu müssen, in der ersten Auflage von bubble sort durch das Array zu machen?
[Schüler] n - 1. >> Ja.
>> Wenn es 5 Elemente sind, wir gehen zu müssen, machen n - 1.
Dann auf dem zweiten ein, wie viele Swaps werden wir machen müssen?
[Schüler] n - 2. >> Ja.
Und die dritte wird n - 3, und dann für die Bequemlichkeit ich die letzten beiden schreib
Als dann werden wir brauchen, um 2-Swaps und 1 swap machen.
Ich denke, das letzte kann oder auch nicht wirklich brauchen, um passieren.
Ist es ein Swap? Ich weiß nicht.
So sind die Gesamtbeträge der Swaps oder zumindest Vergleiche die Sie machen müssen.
Auch wenn Sie nicht tauschen kann, müssen Sie noch die Werte vergleichen.
So gibt es n - 1 Vergleiche in dem ersten Lauf durch den Array.
Wenn Sie diese Dinge neu zu ordnen, lasst uns tatsächlich machen es sechs Dinge so Dinge stapeln sich schön,
und dann werde ich tun, 3, 2, 1.
Also einfach neu anordnen diese Summen wollen wir sehen, wie viele Vergleiche machen wir
im gesamten Algorithmus.
Also, wenn wir bringen diese Jungs hier unten,
dann sind wir gerade noch Summierung jedoch viele Vergleiche dort waren.
Aber wenn wir summieren diese und fassen wir diese und fassen wir diese,
es ist immer noch das gleiche Problem. Wir fassen diese speziellen Gruppen.
>> So jetzt sind wir Summierung 3 n der. Es ist nicht nur 3 n der.
Es ist immer zu n / 2 n der sein.
Also hier haben wir gerade 6 haben.
Wenn wir 10 Dinge hatte, dann könnten wir diese Gruppierung für 5 verschiedene Paare von Dingen zu tun
und am Ende mit n + n + n + n + n.
Sie sind also immer zu n / 2 n die zu bekommen, und so ist dies werden wir es jot aus n squared / 2.
Und obwohl es der Faktor der Hälfte, die zu kommen passiert
wegen der Tatsache, dass durch jede Iteration über die Anordnung es 1 weniger vergleiche
so das ist, wie wir das über 2 bekommen, aber es ist immer noch n Quadrat.
Wir reden nicht über den konstanten Faktor von einer halben kümmern.
So viele große O Sachen wie diese stützt sich auf nur eine Art, dies zu tun Art von Mathematik,
Rechnen Summen und geometrischen Reihe stuff,
aber die meisten von ihnen in diesem Kurs sind ziemlich eindeutig.
Okay.
Warum ist Insertion Sort in Omega der n? Was bedeutet omega bedeuten?
[Zwei Studenten sprechen auf einmal - unverständlich] >> Ja.
Omega Sie können als die untere Grenze zu denken.
>> Also egal, wie effizient Ihre Insertion Sort-Algorithmus ist,
unabhängig von der Liste, die im vergangen ist, es muss immer mindestens n Dinge zu vergleichen
oder es muss über n Dinge durchlaufen.
Warum ist das so?
[Schüler] Denn wenn die Liste bereits sortiert ist, dann durch die erste Iteration
Sie können nur garantieren, dass das erste Element, das wenigste ist,
und die zweite Iteration können Sie garantieren nur die ersten beiden sind
weil Sie nicht wissen, dass der Rest der Liste sortiert ist. >> Ja.
Wenn Sie in einem komplett sortierte Liste, passieren zumindest müssen Sie gehen über alle Elemente
zu sehen, dass nichts zu bewegt werden.
So Überfahren der Liste und sagen oh, dies bereits sortiert ist,
es ist unmöglich zu wissen, es sortiert ist, bis Sie jedes Element überprüfen
um zu sehen, dass sie in sortierter Reihenfolge sind.
So das untere am insertion sort gebunden ist Omega von n.
Was ist der schlimmste Fall Laufzeit von Mergesort,
worst case ist big O wieder?
So im schlimmsten Fall, wie kommt Mergesort laufen?
[Schüler] N log n. >> Ja.
Die schnellsten allgemeinen Sortieralgorithmen sind n log n. Sie können es nicht besser.
>> Es gibt spezielle Fälle, und wenn wir Zeit haben heute - aber wir werden wahrscheinlich willst nicht -
konnten wir sehen ein, die besser als n log n tut.
Aber im allgemeinen Fall, können Sie nicht besser als n log n.
Und Mergesort passiert das, das Sie für diesen Kurs, n log n wissen sollte.
Und so werden wir tatsächlich zur Umsetzung dieser heute.
Und schließlich, in nicht mehr als drei Sätze, wie funktioniert Auswahl Art Arbeit?
Hat jemand beantworten wollen, und ich werde Ihre Sätze zählen
denn wenn Sie über 3 gehen -
Erinnert sich noch jemand Auswahl Art?
Selection Art ist in der Regel recht einfach, nur aus dem Namen zu erinnern.
Sie haben über das Array durchlaufen, zu finden, was der größte Wert ist oder kleinsten -
was um Sie Sortier in.
Also lasst uns sagen, dass wir vom kleinsten bis zum größten Sortierung.
Sie über das Array, auf der Suche nach was auch immer das kleinste Element ist,
wählen Sie es aus, und dann einfach tauschen Sie ihn, was in den ersten Platz.
Und dann auf dem zweiten Durchlauf über die Anordnung, für die minimale Element noch einmal anzusehen,
wählen Sie es aus, und dann tauschen sie mit dem, was in der zweiten Position.
So sind wir nur Auswahlchristentum die minimalen Werte
und Einfügen von ihnen in die vor dem Array, bis sie sortiert ist.
Fragen dazu?
>> Diese unvermeidlich in den Formularen, die Sie ausfüllen müssen, wenn Sie die Einreichung des pset sind angezeigt.
Das sind im Wesentlichen die Antworten auf diese.
Okay, jetzt Codierung Probleme.
I already sent sich über e-mail - Hat jemand nicht bekommen, dass E-Mail? Okay.
I already sent out über E-Mail den Raum, dass wir gehen zu verwenden,
und wenn Sie auf meinen Namen - ich denke, ich werde auf dem Boden sein
wegen der hinten r - aber wenn Sie auf meinen Namen sehen Sie 2 Revisionen.
Revision 1 wird ich schon kopiert und eingefügt werden Sie den Code in Spaces
für die Suche, was Sie gehen zu müssen, zu implementieren.
Und Revision 2 wird die Art, was wir nach, dass umzusetzen.
So können Sie auf meiner Revision 1 klicken und arbeiten von dort aus.
Und jetzt wollen wir binäre Suche zu implementieren.
>> Hat jemand will geben nur einen Pseudo-High-Level-Erklärung
von dem, was wir gehen zu müssen, für die Suche zu tun? Yeah.
[Schüler] Sie einfach die Mitte des Arrays und sehen, ob was Sie suchen
ist kleiner als die oder mehr.
Und wenn es weniger ist, müssen Sie die Hälfte, die weniger ist zu gehen,
und wenn es mehr ist, gehen Sie zu der Hälfte, die mehr ist und Sie das wiederholen, bis bekommst du nur eine Sache.
[Bowden] Yeah.
Beachten Sie, dass unsere Zahlen Array bereits sortiert ist,
und so, dass bedeutet, dass wir das auszunutzen und wir konnten zuerst überprüfen,
Okay, ich bin für die Nummer 50 suchen.
So kann ich in die Mitte gehen.
Mittelschicht ist schwer zu definieren, wenn es eine gerade Anzahl von Dingen ist,
aber lasst uns einfach sagen, dass wir immer in der Mitte abgeschnitten.
Also hier haben wir 8 Dinge, so in der Mitte würde 16 sein.
Ich bin für 50 suchen, so 50 ist größer als 16 ist.
So jetzt kann ich im Grunde behandle meine Array dieser Elemente.
Ich kann alles wegwerfen, was aus 16 vorbei.
Jetzt ist mein Array ist gerade diese 4 Elemente, und ich wiederhole.
Also habe ich die Mitte wieder finden wollen, ist das werde 42 sein.
42 weniger als 50, so kann ich wegwerfen diese beiden Elemente.
Dies ist meine restlichen Array.
Ich werde in der Mitte wieder zu finden.
Ich denke, 50 war ein schlechtes Beispiel, weil ich immer wegwerfen Dinge auf der linken Seite
aber aus dem gleichen Maß, wenn ich mich für etwas
und es ist weniger als das Element Ich suche derzeit an,
dann werde ich alles wegwerfen, was auf der rechten Seite.
So, jetzt müssen wir, dass zu implementieren.
Beachten Sie, dass wir in der Größe übergeben müssen.
Wir können auch nicht zu hart-Code Größe benötigen.
Wenn wir also los, dass Sie # define -
Okay.
Wie kann ich schön herauszufinden, was die Größe der Zahlen-Arrays aktuell ist?
>> Wie viele Elemente sind in den Zahlen-Array?
[Schüler] Numbers, Konsolen,. Länge?
[Bowden], dass nicht in C existiert
Benötigen. Länge.
Arrays haben keine Eigenschaften, so dass es keine length-Eigenschaft des Arrays
das wird Ihnen nur wie lange es passiert zu sein.
[Schüler] Sehen Sie, wie viel Speicher hat und dividieren, um wie viel - >> Ja.
Wie können wir also sehen, wie viel Speicher sie hat? >> [Schüler] Sizeof. >> Ja, sizeof.
Sizeof ist der Betreiber, die gehen, um die Größe der Zahlen Array zurück ist.
Und das wird aber viele ganze Zahlen sein gibt es Zeiten, die Größe eines Integer
denn das ist, wie viel Speicher es ist tatsächlich die Aufnahme.
Also, wenn ich die Anzahl der Dinge im Array möchten,
dann bin ich gehen zu wollen, die von der Größe eines Integer teilen.
Okay. Also das lässt mich in die grösse hier passieren.
Warum brauche ich in der Größe überhaupt passieren?
Warum kann ich nicht einfach tun, hier int size = sizeof (Heuhaufen) / sizeof (int)?
Warum funktioniert das nicht?
[Schüler] Es ist nicht eine globale Variable.
[Bowden] Haystack existiert und wir in Zahlen vorbei, wie Heuhaufen,
und dies ist eine Art Vorahnung von dem, was noch kommen wird. Yeah.
[Schüler] Haystack ist nur der Verweis darauf, so wäre das Ergebnis, wie groß, dass Referenz ist.
Yeah.
Ich bezweifle, dass in der Vorlesung, dass Sie den Stapel noch nicht wirklich, richtig gesehen?
Wir haben gerade darüber gesprochen.
So der Stapel ist, wo alle Ihre Variablen gehen, um gespeichert werden.
>> Jede Erinnerung, die für lokale Variablen zugeordnet ist im Stapel gehen,
und jede Funktion bekommt seinen eigenen Platz auf dem Stack, ist seine eigene Stack-Frame, was es heißt.
So Haupt hat seinen Stack-Frame und nach innen von ihm wird diesen Zahlen Array vorhanden,
und es wird von der Größe sizeof (Zahlen) sein.
Es wird auf die Größe der Zahlen nach der Größe der Elemente unterteilt haben,
sondern dass alle Leben in Main Stack-Frame.
Wenn wir suchen nennen, bekommt Suche eigene Stack-Frame,
seinen eigenen Raum zu speichern alle ihre lokalen Variablen.
Aber diese Argumente - so Heuhaufen ist nicht eine Kopie dieser gesamte Array.
Wir glauben nicht an das gesamte Array als Kopie Suche übergeben.
Es ist einfach eine Referenz auf dieses Array.
So suchen können diese Zahlen durch diesen Verweis zugreifen.
Es ist immer noch Zugriff auf die Dinge, die in der Haupt-Stack-Frame zu leben,
aber im Grunde, wenn wir Hinweise erhalten, sollten die bald sein,
dies ist, was Zeiger sind.
Zeiger sind nur Verweise auf Dinge, und Sie können Zeiger zu verwenden, um die Dinge zugreifen
, die in anderen Dingen 'Stack-Frames.
Also auch wenn Zahlen ist lokal zu main, können wir immer noch darauf zugreifen über diesen Zeiger.
Aber da es nur ein Zeiger und es ist nur eine Referenz,
sizeof (Heuhaufen) gibt nur die Größe der Referenz selbst.
Es gibt nicht die Größe der Sache, die es zu zeigen ist.
Es gibt nicht die tatsächliche Größe der Zahlen.
Und so ist dies nicht zur Arbeit zu gehen, wie wir es wollen.
>> Fragen dazu?
Pointers werden in deutlich mehr blutigen Details werden in Wochen weg zu kommen.
Und das ist, warum viele Dinge, die Sie sehen, die meisten suchen Dinge oder sort Dinge,
sie fast alle gehen zu müssen, um die tatsächliche Größe des Arrays zu nehmen,
denn in C, wir haben keine Ahnung, was die Größe des Arrays ist.
Sie müssen manuell weitergeben in.
Und Sie können nicht manuell in das gesamte Array durchlaufen, da Sie nur auf der Durchreise sind in der Referenzwährung
und es kann nicht die Größe aus der Referenz.
Okay.
So, jetzt wollen wir das umsetzen, was erklärt wurde, vor.
Darauf können Sie sich für eine Minute zu arbeiten,
und Sie müssen nicht darum, alles perfekt 100% arbeiten zu kümmern.
Schreiben Sie einfach bis die Hälfte Pseudocode, wie Sie denken, es sollte funktionieren.
Okay.
Keine Notwendigkeit, komplett mit dies noch getan werden.
Aber hat jemand wohl fühlen mit dem, was sie bisher,
wie etwas können wir mit zusammen?
Will jemand sich freiwillig? Oder ich werde nach dem Zufallsprinzip auswählen.
Es muss nicht nach rechts durch eine Maßnahme, sondern etwas, das wir in einen funktionierenden Zustand zu ändern können.
[Schüler] Sure. >> Okay.
So können Sie die Revision durch Klick auf das kleine Symbol Speichern.
Du bist Ramya, nicht wahr? >> [Schüler] Yeah. >> [Bowden] Okay.
So jetzt kann ich sehen Sie Ihre Revision und jeder kann nach oben ziehen die Revision.
Und hier haben wir - Okay.
So Ramya ging mit der rekursive Lösung, das ist definitiv eine gültige Lösung.
Es gibt zwei Möglichkeiten, wie Sie dieses Problem tun kann.
Sie können es entweder iterativ oder rekursiv.
Die meisten Probleme, die das kann rekursiv geschehen kann auch iterativ erfolgen.
Also hier haben wir es geschafft rekursiv.
>> Hat jemand wollen definieren, was es zu machen eine Funktion rekursiv bedeutet?
[Schüler] Wenn Sie eine Funktion haben, nennt sich
und rufen Sie dann selbst, bis es aus mit echten und wahren. >> Ja.
Eine rekursive Funktion ist nur eine Funktion, die sich selbst aufruft.
Es gibt drei große Dinge, die eine rekursive Funktion haben muss.
Die erste ist offensichtlich, nennt es sich.
Die zweite ist die Base-Case.
So an einem gewissen Punkt die Funktion muss aufhören, sich selbst,
und das ist, was die Base-Case ist für.
Also hier wissen wir, dass wir aufhören sollten, sollten wir in unserer Suche
bei Beginn Ende gleich - und wir gehen über das, was das bedeutet.
Aber schließlich, die letzte Sache, die wichtig für rekursive Funktionen ist:
Die Funktionen müssen irgendwie nähern sich dem Basisfall.
Wie, wenn du nicht wirklich aktualisiert nichts, wenn Sie den zweiten rekursiven Aufruf zu machen,
wenn Sie buchstäblich nur den Aufruf der Funktion wieder mit den gleichen Argumenten
und keine globalen Variablen geändert haben oder so etwas,
Sie erreichen nie die Base-Case, in welchem ​​Fall das ist schlecht.
Es wird eine unendliche Rekursion und ein Stack-Überlauf sein.
Aber hier sehen wir, dass das Update geschieht, da wir die Aktualisierung beginnen, werden + Ende / 2,
wir aktualisieren das Ende Argument hier, wir aktualisieren die Start-Argument hier.
So in allen rekursiven Aufrufen aktualisieren wir etwas. Okay.
Wollen Sie uns durch Ihre Lösung gehen? >> Sure.
Ich bin mit SearchHelp, so dass jedes Mal wenn ich diese Funktion Anruf
Ich habe den Start, wo ich in dem Array suchen und das Ende
wo ich freue mich auf das Array.
>> Bei jedem Schritt, wo es zu sagen, es ist das mittlere Element, das Start ist + Ende / 2 ist,
ist, dass gleich was wir suchen?
Und wenn ja, dann fanden wir es, und ich denke, das wird sich die Ebenen der Rekursion übergeben.
Und wenn das nicht wahr ist, dann werden wir prüfen, ob es mittleren Wert des Arrays zu groß ist,
In diesem Fall betrachten wir die linke Hälfte des Feldes, indem Sie von Anfang bis Mitte index.
Und sonst tun wir das Ende Hälfte.
[Bowden] Okay.
Das hört sich gut an.
Okay, so ein paar Dinge, und tatsächlich ist dies ein sehr hohem Niveau, was
dass Sie nie brauchen, um für diesen Kurs wissen, aber es ist wahr.
Rekursive Funktionen, hört man immer, dass sie ein schlechtes Geschäft sind
denn wenn man rekursiv nennen sich zu oft, erhalten Sie Stack-Überlauf
denn, wie ich schon sagte, bekommt jeder Funktion eine eigene Stack-Frame.
So dass jeder Aufruf der rekursiven Funktion bekommt seinen eigenen Stack-Frame.
Also, wenn Sie 1.000 rekursive Anrufe tätigen, erhalten Sie 1.000 Stack-Frames,
und schnell Sie zu viele Stack-Frames und die Dinge einfach zu brechen führen.
Also das ist, warum rekursive Funktionen in der Regel schlecht sind.
Aber es ist ein schöner Teil der rekursive Funktionen aufgerufen tail-rekursive Funktionen,
und dies geschieht, ein Beispiel für eine, wo, wenn der Kompilierer bemerkt dies
und es sollte, denke ich - in Clang wenn Sie weitergeben the-O2-Flag
dann wird es bemerken, ist dies endrekursiv und die Dinge gut.
>> Es wird Wiederverwendung der gleichen Stapelrahmen immer wieder für jeden rekursiven Aufruf.
Und so, da Sie mit dem gleichen Stack-Frame sind, brauchen Sie keine Sorgen zu machen
immer stapeln überfüllt, und zur gleichen Zeit, wie Sie vorhin sagten,
wo, wenn Sie true zurückgeben, dann muss es zurück bis alle diese Stack-Frames
und die 10. Aufruf SearchHelp muss dem neunten zurückzukehren, muss dem achten zurückzukehren.
Also das muss nicht passieren, wenn Funktionen endrekursiv sind.
Und so was macht diese Funktion endrekursiv ist bekannt, dass für einen bestimmten Aufruf SearchHelp
der rekursive Aufruf, dass es macht, was es ist zurück.
So in dem ersten Aufruf SearchHelp wir entweder sofort false zurück,
sofort wieder wahr, oder wir machen eine rekursive Aufruf SearchHelp
wo das, was wir wieder ist, was das Gespräch wird zurückkehren.
Und wir konnten das nicht tun, wenn wir so etwas wie int x = SearchHelp, return x * 2 tat,
nur einige zufällige Veränderung.
>> So jetzt dieses rekursiven Aufruf, diese int x = SearchHelp rekursiven Aufruf,
ist nicht mehr endrekursiv, weil es tatsächlich zur Rücksendung haben
zurück zu einer früheren Stapelrahmen so dass diese vorherigen Aufruf der Funktion
kann dann etwas mit dem Rückgabewert.
Das ist also nicht endrekursiv, aber was wir vorher hatten ist schön endrekursiv. Yeah.
[Schüler] Sollte nicht das zweite Base Case zunächst überprüft werden
weil es könnte eine Situation sein, wo, wenn Sie es das Argument übergeben
Sie start = Ende, aber sie sind die Nadel Wert.
Die Frage wurde können wir nicht in die Falle laufen, wo Ende ist die Nadel-Wert
oder starten = Ende, angemessen, start = Ende
und Sie haben nicht wirklich, dass die besonderen Wert überprüft noch,
dann starten + Ende / 2 ist gerade dabei, den gleichen Wert.
Aber wir haben schon wieder falsch und wir eigentlich nie den Wert überprüft.
So zumindest in dem ersten Aufruf, wenn die Größe 0 ist, dann wollen wir false zurück.
Aber wenn Größe 1 ist, dann Start wird nicht gleich Ende
und wir zumindest überprüfen die ein Element.
Aber ich glaube, Sie haben Recht, dass wir am Ende in einem Fall, wo + Ende / 2 starten,
Start landet das gleiche wie Start + Ende / 2,
aber wir nie wirklich das Element überprüft.
>> Also, wenn wir zuerst überprüfen, ist das mittlere Element der Wert, die wir suchen,
dann können wir sofort wieder wahr.
Else, wenn sie gleich sind, dann hat es keinen Sinn in der Weiterbildung
da wir gerade dabei, in einem Fall, wo wir sind auf einer Single-Element-Array zu aktualisieren.
Wenn das einzelne Element ist nicht das, was wir suchen,
dann ist alles falsch. Yeah.
[Schüler] Die Sache ist, dass, da Größe ist tatsächlich größer als die Anzahl der Elemente in dem Array,
gibt es bereits ein Offset - >> So wird Größe -
[Student] Sprich, wenn das Array war Größe 0, dann ist die SearchHelp tatsächlich überprüfen Heuhaufen 0
beim ersten Anruf.
Das Array hat die Größe 0, so dass die 0 ist - >> Ja.
Es ist eine andere Sache, dass - es könnte gut sein. Lasst uns denken.
Also, wenn das Array mit 10 Elementen und in der Mitte ein wir überprüfen, sind die Index-5,
so dass wir die Überprüfung 5, und sagen wir, dass der Wert geringer ist.
So wir werfen alles weg 5 weiter.
So starten + Ende / 2 wird unsere neue Ende,
so yeah, es ist immer zu über das Ende des Arrays bleiben.
Wenn es eine Falle ist, wenn es gerade oder ungerade war, dann würden wir überprüfen, sagen, 4,
aber wir sind immer noch wegwerfen -
Also ja, ist das Ende immer zu über das eigentliche Ende des Arrays sein.
So die Elemente konzentrieren wir uns auf, wird Ende immer zu der ein danach.
Und so, wenn startet immer gleich Ende, wir sind in einem Array der Größe 0.
>> Die andere Sache, die ich dachte, ist, dass wir die Aktualisierung Start zu Start + Ende / 2,
so ist dies der Fall, dass ich Probleme mit, wo + Ende / 2 beginnen
ist das Element, wir überprüfen.
Sagen wir, wir hatten diese 10-Element-Array. Wie auch immer.
So starten + Ende / 2 wird so etwas wie dieses sein,
und wenn das nicht der Wert, sagen wir aktualisieren möchten.
Der Wert ist größer, so wollen wir an dieser Hälfte des Array.
So wie wir die Aktualisierung starten, wir aktualisieren Start nun dieses Element sein.
Aber das kann noch arbeiten, oder zumindest, können Sie beginnen zu tun + Ende / 2 + 1.
[Schüler] Sie brauchen nicht zu + Ende beginnen [unverständlich] >> Ja.
Wir haben bereits dieses Element geprüft und weiß, es ist nicht das, was wir suchen.
So brauchen wir nicht, um den Start zu aktualisieren, um dieses Element zu sein.
Wir können es gerade auslässt und zu aktualisieren beginnen dieses Element sein.
Und gibt es überhaupt ein Fall, sagen wir mal, dass dieses Ende waren,
so starten Sie dann wäre dies, starten + Ende / 2 wäre dies,
Start + Ende - Ja, ich denke, es kann am Ende in Endlosschleife.
Lassen Sie uns sagen, es ist nur ein Array der Größe 2 oder ein Array der Größe 1. Ich denke, das wird funktionieren.
So aktuell ist Anfang dieses Element und am Ende ein dahinter ist.
So das Element, dass wir gehen, um zu überprüfen ist dies ein,
und dann, wenn wir Update starten, wir aktualisieren Start in 0 + 1/2 sein,
was wird uns am Ende wieder mit Beginn ist dieses Element.
>> Also werden wir prüfen das gleiche Element immer und immer wieder.
So dies der Fall ist, wo jeder rekursive Aufruf tatsächlich aktualisieren muss etwas.
Also müssen wir, um den Start + Ende / 2 + 1, sonst tun es ist ein Fall
wo wir eigentlich nicht die Aktualisierung starten.
Jeder sehen?
Okay.
Hat jemand Fragen zu dieser Lösung oder mehr Kommentare?
Okay. Hat jemand eine iterative Lösung, dass wir alle sehen?
Haben wir alle tun es rekursiv?
Oder auch ich denke, wenn man ihr eröffnet, dann haben Sie vielleicht überschrieben Ihrer vorherigen.
Ist es automatisch zu speichern? Ich bin nicht positiv.
Hat jemand iterativen?
Wir können durch sie gehen zusammen, wenn nicht.
Die Idee wird die gleiche sein.
Iterative Lösung.
Wir gehen zu wollen, im Grunde tun die gleiche Idee
wo wir wollen den Überblick über das neue Ende des Arrays und den Neubeginn des Arrays zu halten
und das tun immer und immer wieder.
Und wenn das, was wir als die Verfolgung von Anfang und Ende je kreuzen,
dann haben wir es nicht finden, und wir können false zurück.
Also, wie kann ich das tun? Wer noch Anregungen oder Code für mich nach oben zu ziehen?
[Schüler] Führen Sie eine while-Schleife. >> Ja.
Sie gehen zu wollen, um eine Schleife zu tun.
>> Haben Sie Code konnte ich nach oben ziehen, oder was wolltest du vorschlagen?
[Schüler] Ich denke schon. >> Alles klar. Das macht die Sache einfacher. Was war Ihr Name?
[Schüler] Lucas.
Revision 1. Okay.
Niedrig ist, was wir beginnen, bevor genannt.
Up ist nicht ganz das, was wir am Ende als zuvor.
Eigentlich ist Ende nun innerhalb des Arrays. Es ist ein Element, das wir berücksichtigen sollten.
So niedrig ist 0, bis die Größe des Arrays - 1,
und jetzt sind wir eine Schleife, und wir werden prüfen -
Ich denke, man kann durch sie hindurchgehen.
Was war Ihr Denken durch das? Gehen Sie uns durch Ihren Code.
[Schüler] Sure. Schauen Sie sich die Heuhaufen Wert in der Mitte und vergleichen Sie es mit Nadel.
Also, wenn es größer als die Nadel ist, dann wollen Sie - oh, tatsächlich, das sollte rückwärts.
Sie gehen zu wollen, werfen die rechte Hälfte, und so ja, das sollte der Weg sein.
[Bowden] So sollte dies weniger? Ist das, was du gesagt hast? >> [Schüler] Yeah.
[Bowden] Okay. Weniger.
Also, wenn das, was wir suchen, ist kleiner als das, was wir wollen,
dann ja, wollen wir wegwerfen die linke Hälfte,
was bedeutet, wir aktualisieren alles, was wir erwägen
durch Bewegen günstig rechts von der Anordnung.
Das sieht gut aus.
Ich denke, es hat das gleiche Problem, dass wir auf dem vorherigen sagte
wo, wenn niedrig ist 0 und bis 1 ist, dann low + up / 2 wird eingerichtet, um die gleiche Sache wieder.
>> Und selbst wenn das nicht der Fall ist, ist es noch effizienter zumindest
nur wegwerfen das Element wir sahen, an dem wir wissen, ist falsch.
So low + up / 2 + 1 - >> [Schüler] Das sollte das anders sein.
[Bowden] Oder diese sollte - 1 und der andere sollte + 1 sein.
[Schüler] Und es sollte eine doppelte sein Gleichheitszeichen. >> [Bowden] Yeah.
[Schüler] Yeah.
Okay.
Und schließlich, jetzt, da wir dieses + 1 - 1 Sache,
ist es - könnte es nicht sein - ist es überhaupt möglich für niedrige bis zum Ende mit einem Wert größer als up?
Ich denke, der einzige Weg, die passieren können - Ist es möglich? >> [Schüler] Ich weiß es nicht.
Aber wenn er abgeschnitten wird und dann bekommt minus dass 1 und dann - >> Ja.
[Schüler] Es wäre möglicherweise durcheinander.
Ich denke, es sollte gut sein, nur weil
für sie enden bis unteren müssten sie gleich sein, denke ich.
Aber wenn sie gleich sind, dann würden wir nicht die while-Schleife zu beginnen getan haben
und wir würden den Wert zurückgekehrt. Also ich denke, wir sind jetzt gut.
Beachten Sie, dass, obwohl dieses Problem ist nicht mehr rekursiv,
die gleiche Art von Ideen gelten, wo wir sehen können, wie diese so leicht eignet sich
eine rekursive Lösung durch die Tatsache, dass wir nur die Aktualisierung der Indizes immer und immer wieder,
wir machen das Problem kleiner, sind wir auf eine Teilmenge des Arrays konzentrieren.
[Schüler] Wenn niedrig ist 0 und bis 1 ist, würden sie beide 0 + 1/2, die auf 0 gehen würde,
und dann würde + 1 sein, würde man - 1.
[Student] Wo werden wir die Überprüfung Gleichheit?
Wie, wenn die mittlere ist eigentlich Nadel?
Wir sind nicht gerade tun? Oh!
Wenn es ist -
Ja. Wir können nicht einfach machen Sie den Test hier unten, weil wir die ersten mittleren sagen -
[Schüler] Es ist eigentlich wie nicht wegwerfen gebunden.
Also, wenn Sie entfernt das gebundene, müssen Sie es zuerst oder was auch immer.
Ah. Yeah. >> [Schüler] Yeah.
So, jetzt haben wir entfernt die, die wir derzeit sah geworfen,
das heißt, wir müssen jetzt auch
if (haystack [(low + up) / 2] == Nadel), dann können wir wieder wahr.
Und ob ich sonst oder nur, wenn ausgedrückt, bedeutet es wörtlich dasselbe
denn dies würde true zurückgegeben haben.
Also werde ich andere zu stellen, wenn, aber es spielt keine Rolle.
>> So else if diesem, sonst dieses, und das ist eine gemeinsame Sache, die ich tun
wo auch wenn es der Fall, wo alles ist gut hier,
wie niedrige nie sein kann größer als oben, ist es nicht wert Argumentation darüber, ob das wahr ist.
So können Sie genauso gut sagen, während niedrig ist kleiner oder gleich
oder während niedrig ist weniger als
so dass, wenn sie jemals gleich oder niedriger sind passiert zu passieren,
dann können wir brechen aus dieser Schleife.
Fragen, Anliegen, Anregungen?
Okay. Das sieht gut aus.
Jetzt wollen wir dergleichen zu tun.
Wenn wir zu meinem zweiten Revision gehen, sehen wir die gleichen Zahlen,
aber jetzt sind sie nicht mehr in sortierter Reihenfolge.
Und wir wollen sort Umsetzung mit einem beliebigen Algorithmus in O n log n.
So, welcher Algorithmus denkst du, wir sollten hier zu implementieren? >> [Schüler] Merge sort.
[Bowden] Yeah. Mergesort ist O (n log n), so dass das, was wir tun werden.
Und das Problem wird sich ziemlich ähnlich,
wo es leicht eignet sich für eine rekursive Lösung.
Wir können auch kommen mit einem iterativen Lösung, wenn wir wollen,
aber Rekursion wird einfacher sein hier, und wir sollten Rekursion zu tun.
Ich denke, wir werden durch Mergesort erste gehen,
obwohl es eine schöne Video-on-Mergesort bereits. [Gelächter]
So Mergesort gibt es - ich bin es leid verschwenden so viel von diesem Papier.
Oh, es gibt nur eine links.
So verschmelzen.
Oh, 1, 3, 5.
Okay.
Merge dauert zwei separate Arrays.
Individuell diese beiden Arrays werden sowohl sortiert.
So dieses Array, 1, 3, 5, sortiert. Dieses Array, 0, 2, 4, sortiert.
Nun, was merge tun sollten, ist zu kombinieren sie zu einem einzigen Array, das sich von selbst geregelt ist.
So wollen wir ein Array der Größe 6, die gehen, um diese Elemente im Inneren lassen will
in sortierter Reihenfolge.
>> Und so können wir die Tatsache zunutze, dass diese beiden Arrays sortiert nehmen
dies in linearer Zeit zu tun,
linearer Zeit Sinn, wenn diese Anordnung ist die Größe x, und dies ist die Größe y,
dann ist der gesamte Algorithmus sollte O (x + y) sein. Okay.
So Vorschläge.
[Schüler] Könnten wir von links beginnen?
So finden Sie die 0 zuerst hinunter und dann die 1 gesetzt und dann hier bist du an der 2.
Also ist es eine Art, wie Sie eine Registerkarte, die nach rechts bewegt hat. >> [Bowden] Yeah.
Für diese beiden Arrays wenn wir nur auf der äußersten linken Element fokussieren.
Da beide Arrays sortiert sind, wissen wir, dass diese 2 Elemente
sind die kleinsten Elemente in jedem Array.
Das heißt also, dass 1 dieser 2 Elemente müssen das kleinste Element in unserer fusionierten Array sein.
Es passiert einfach so, dass die kleinste der auf der rechten Seite dieser Zeit ist.
Also nehmen wir 0, legen Sie sie auf der linken, da 0 kleiner als 1,
so nehmen 0, legen Sie sie in unserer ersten Position, und dann aktualisieren wir diese
Bisher auf dem ersten Element zu konzentrieren.
Und jetzt haben wir wiederholen.
So, jetzt vergleichen wir 2 und 1. 1 kleiner, so dass wir 1 einzufügen.
Wir aktualisieren diese Zeiger auf diesen Kerl zu zeigen.
Jetzt haben wir es wieder tun, so 2. Dies wird zu aktualisieren, zu vergleichen diese 2, 3.
Diese Updates, dann 4 und 5.
So das ist fusionieren.
>> Es sollte ziemlich offensichtlich, dass es die lineare Zeit ist, da wir über jedes Element nur einmal gehen.
Und das ist der größte Schritt zur Umsetzung Mergesort ist, dies zu tun.
Und es ist nicht so schwer.
Ein paar Dinge zu kümmern ist sagen wir, wir wurden Zusammenlegung 1, 2, 3, 4, 5, 6.
In diesem Fall werden wir am Ende in dem Fall, wenn diese eine werde kleiner sein wird,
dann werden wir diesen Zeiger zu aktualisieren, dieser wird kleiner sein, aktualisieren Sie diese,
dieses ist kleiner, und jetzt haben Sie zu erkennen,
wenn man eigentlich laufen aus Elementen zu vergleichen mit.
Da haben wir schon das gesamte Array verwendet,
alles in diesem Array ist nun gerade in hier eingefügt.
Also, wenn wir jemals in dem Punkt, wo einer unserer Arrays komplett zusammengeführt wird bereits ausgeführt,
dann haben wir nur nehmen alle Elemente der anderen Anordnung und legen Sie sie in das Ende des Arrays.
So können wir einfach legen Sie 4, 5, 6. Okay.
Das ist eine Sache, die Sie achten sollten.
Umsetzung das sollte Schritt 1 sein.
Merge dann sortieren basierend auf, dass es 2 Stufen, 2 dumme Schritte.
Lasst uns einfach geben diesem Array.
So Mergesort ist Schritt 1 rekursiv zu brechen das Array in zwei Hälften.
So unterteilt dieses Array in zwei Hälften.
Wir haben jetzt 4, 15, 16, 50 und 8, 23, 42, 108.
Und jetzt haben wir es wieder tun und wir teilen diese in zwei Hälften.
Ich werde es einfach tun auf dieser Seite.
Also 4, 15 und 16, 50.
Wir würden die gleiche Sache immer tun.
Und jetzt haben wir spaltete es in zwei Hälften wieder.
Und wir haben 4, 15, 16, 50.
Also das ist unsere Basis Fall.
Nachdem die Arrays der Größe 1 sind, dann werden wir mit der Aufspaltung zu stoppen in zwei Hälften.
>> Nun, was haben wir damit zu tun?
Wir landen wird dies auch brechen in 8, 23, 42 und 108.
So, jetzt, dass wir an diesem Punkt sind, jetzt Schritt zwei Mergesort ist nur Zusammenlegung Paaren zu den Listen.
So wollen wir diese zusammenführen. Wir rufen zu verschmelzen.
Wir wissen merge werden diese in sortierter Reihenfolge zurück.
4, 15.
Jetzt wollen wir diese zusammenführen, und das wird eine Liste mit den in sortierter Reihenfolge zurück,
16, 50.
Wir verschmelzen die - ich kann nicht schreiben - 8, 23 und 42, 108.
So haben wir fusionierten Paaren einmal.
Jetzt müssen wir nur wieder zusammenführen.
Beachten Sie, dass jede dieser Listen sortiert ist an sich
und dann können wir nur verschmelzen diese Listen, um eine Liste der Größe 4, sortiert zu bekommen
und Zusammenführen dieser beiden Listen eine Liste der Größe 4, die sortiert erhalten.
Und schließlich können wir mischen Sie die beiden Listen der Größe 4 zu einer Liste der Größe 8, sortiert zu bekommen.
So zu sehen, dass diese allgemeine n log n ist, haben wir bereits gesehen, dass Merge-linear ist,
so, wenn wir mit dem Zusammenführen dieser zu tun haben, so wie die Gesamtkosten der Zusammenführung
für diese beiden Listen ist nur 2, weil -
Oder gut, es ist O n, aber n ist hier nur diese 2 Elemente, so dass es 2.
Und diese 2 2 sein und diese 2 2 sein und diese 2 2 sein,
so über alle geht, dass wir tun müssen, landen wir tun, n.
Wie 2 + 2 + 2 + 2 ist 8, das N ist,
so dass die Kosten der Zusammenführung in dieser Reihe ist n.
Und dann das Gleiche hier.
Wir verschmelzen diese 2, dann diese 2 und individuell diese Zusammenführung wird vier Operationen zu nehmen,
Diese Zusammenführung dauert vier Operationen, aber noch einmal, zwischen all diesen
landen wir Verschmelzung n insgesamt Dinge, und so dass dieser Schritt erfolgt n.
Und so jede Ebene hat n Elemente verschmolzen.
>> Und wie viele gibt es?
Auf jeder Ebene, wächst unser Angebot nach Größe 2.
Hier unsere Arrays der Größe 1 sind, hier sind sie der Größe 2 sind, hier sind sie der Größe 4,
und schließlich sind sie der Größe 8.
Zumal es verdoppelt wird, wird es auch insgesamt log n dieser Ebenen liegen.
Also mit log n Ebenen, wobei jede einzelne Ebene unter n insgesamt Operationen,
bekommen wir eine n log n Algorithmus.
Haben Sie Fragen?
Haben Menschen, die bereits Fortschritte gemacht, wie dies zu implementieren?
Ist jemand bereits in einem Zustand, wo ich nur ziehen kann ihren Code?
Ich kann eine Minute.
Dieser wird länger sein.
Ich empfehle wiederkehren -
Sie haben noch die Rekursion für Merge tun
weil die Rekursion für Merge tun, sind Sie gehen zu müssen, eine Reihe von verschiedenen Größen passieren.
Man kann, aber es ist ärgerlich.
Aber Rekursion für sort selbst ist recht einfach.
Sie haben buchstäblich nennen sort auf der linken Hälfte, sort auf der rechten Hälfte. Okay.
Wer noch etwas, das ich ziehen kann noch?
Oder ich gebe eine Minute.
Okay.
Wer noch etwas mit denen wir arbeiten können?
Oder aber wir müssen einfach damit arbeiten und erweitern Sie dann von dort aus.
>> Wer noch mehr als dies, dass ich nach oben ziehen?
[Schüler] Yeah. Sie können Pull-up-Mine. >> Alles klar.
Ja!
[Schüler] Es gab eine Menge von Bedingungen. >> Oh, schießen. Können Sie -
[Schüler] Ich habe sie zu retten. >> Ja.
Also taten wir tun, die Zusammenführung getrennt.
Oh, aber es ist nicht so schlimm.
Okay.
So sort ist selbst nur anrufen mergeSortHelp.
Erklären Sie uns, was mergeSortHelp tut.
[Schüler] MergeSortHelp ziemlich viel kostet die beiden wichtigsten Schritte,
das ist es, jede Hälfte des Arrays zu sortieren und dann für beide von ihnen zu verschmelzen.
[Bowden] Okay, so geben Sie mir eine Sekunde.
Ich denke, das - >> [Schüler] Ich muss -
Yeah. Ich bin etwas fehlt.
In merge, merke ich, dass ich um ein neues Array erstellen müssen
denn ich konnte es nicht an Ort und Stelle. >> Ja. Sie kann es nicht. Zu korrigieren.
[Schüler] So erstelle ich ein neues Array.
Ich habe am Ende verschmelzen zu re-ändern.
Okay. Wir brauchen ein neues Array.
In Mergesort ist dies fast immer der Fall.
Teil der Kosten eines besseren Algorithmus zeitlich
ist fast immer braucht ein bisschen mehr Speicher zu verwenden.
Also hier verschmelzen, egal wie Sie sortieren,
Sie würde unweigerlich müssen einige zusätzliche Speicher zu verwenden.
Er oder sie erstellt ein neues Array.
Und dann sagst du am Ende müssen wir nur noch neue Array in das ursprüngliche Array kopieren.
[Schüler] Ich denke schon, ja.
Ich weiß nicht, ob das funktioniert in Bezug auf das Zählen von Referenz-oder was auch immer -
Ja, wird es funktionieren. >> [Schüler] Okay.
Haben Sie versucht, läuft das? >> [Schüler] Nein, noch nicht. >> Okay.
Versuchen Sie es, und dann werde ich darüber für eine Sekunde sprechen.
[Schüler] Ich brauche, um alle Funktionsprototypen und alles haben, obwohl, nicht wahr?
Die Funktionsprototypen. Oh, du meinst wie - Ja.
Sortieren ruft mergeSortHelp.
>> Also, um für die Sortierung zu mergeSortHelp aufrufen, müssen mergeSortHelp entweder definiert haben
vor sortieren oder brauchen wir nur den Prototypen. Kopieren Sie einfach und fügen Sie diese.
Und ähnlich wird mergeSortHelp Aufruf verschmelzen,
aber merge wurde noch nicht festgelegt, so können wir lass mergeSortHelp wissen
, dass das ist, was zusammenführen wird aussehen, und das ist, dass.
So mergeSortHelp.
Wir haben ein Problem hier, wo wir keine Basis Fall haben.
MergeSortHelp rekursiv ist, so dass jede rekursive Funktion
wird irgendeine Art von base case müssen wissen, wann man aufhören rekursiven Aufruf selber.
Was ist unsere Basis bei gehen, hier zu sein? Yeah.
[Schüler] Wenn die Größe 1? >> [Bowden] Ja.
So wie wir genau dort sahen, hielten wir Splitting-Arrays
sobald wir in Arrays der Größe 1, die unweigerlich selbst sortiert werden.
Also, wenn Größe gleich 1 ist, wissen wir das Array bereits sortiert ist,
so können wir nur zurück.
>> Beachten Sie, das ist nichtig, so dass wir nicht wieder etwas Besonderes, wir zurückkehren.
Okay. Damit ist unser Basis-Szenario.
Ich denke, unsere base case könnte auch sein, wenn wir sein Verschmelzung ein Array der Größe 0 passieren,
Wir wollen wahrscheinlich irgendwann aufhören,
So können wir einfach sagen Größe von weniger als 2 oder weniger als oder gleich 1 ist
so dass dies auch bei jedem Array jetzt funktionieren.
Okay.
Damit ist unser Basis-Szenario.
Jetzt wollen Sie uns durch Zusammenführung gehen?
Was haben alle diese Fälle bedeuten?
Hier oben, wir sind nur die gleiche Idee, die -
[Schüler] Ich brauche zu vorbei Größe mit allen mergeSortHelp Anrufe.
Ich fügte hinzu, groß wie eine zusätzliche primäre und es ist nicht da, wie Größe / 2.
[Bowden] Oh, Größe / 2, Größe / 2. >> [Schüler] Ja, und auch in der obigen Funktion als gut.
[Bowden] Hier? >> [Student] Just Größe. >> [Bowden] Oh. Größe, Größe? >> [Schüler] Yeah.
[Bowden] Okay.
Lassen Sie mich für eine Sekunde denken.
Haben wir in ein Problem laufen?
Wir sind immer auf der Behandlung der linken als 0. >> [Schüler] Nr.
Das ist auch falsch. Entschuldigung. Es sollte Anfang sein. Yeah.
[Bowden] Okay. Ich mag, dass besser.
Und Ende. Okay.
So, jetzt wollen Sie uns durch Zusammenführung gehen? >> [Schüler] Okay.
Ich bin nur zu Fuß durch dieses neue Array, das ich erstellt habe.
Seine Größe ist die Größe des Teils des Arrays, die wir sortiert werden soll
und zu versuchen, das Element, dass ich in das neue Array Schritt gesetzt zu finden.
So zu tun, erste ich Prüfen, ob die linke Hälfte des Feldes weiterhin mehr Elemente haben,
und wenn es das nicht tut, dann gehen Sie auf dieser else-Bedingung, die nur sagt
okay, muss es in die richtige Array sein, und wir werden, dass in der aktuellen Index newArray setzen.
>> Und dann nichts anderes, ich überprüfen, ob die rechte Seite des Arrays auch abgeschlossen ist,
in welchem ​​Fall ich gerade auf der linken Seite.
Das könnte eigentlich nicht notwendig sein. Ich bin nicht sicher.
Aber trotzdem sind die beiden anderen, welche der beiden kleineren in der linken oder der rechten Seite.
Und auch in jedem Fall bin ich Inkrementieren je nachdem Platzhalter I erhöhen.
[Bowden] Okay.
Das sieht gut aus.
Hat jemand Anmerkungen oder Bedenken oder Fragen?
So sind die vier Fälle, dass wir die Dinge in einfach nur mitbringen müssen - oder es sieht aus wie fünf -
aber wir haben zu prüfen, ob die linke Array von Dingen, die wir brauchen, um Mischlauf,
ob das Recht Array von Dingen, die wir brauchen, um Mischlauf -
Ich freue mich auf nichts zeigt.
Also, ob das linke Array aus der Dinge laufen oder das Recht Array aus der Dinge laufen.
Das sind zwei Fälle.
Wir benötigen auch die trivialen Fall, ob der linke was kleiner ist als der Richtige.
Dann wollen wir die linke Sache wählen.
Das sind die Fälle.
Das war also richtig, so ist das also.
Array gelassen. Es ist 1, 2, 3. Okay. Also ja, das sind die vier Dinge, die wir tun wollen könnte.
Und wir werden nicht über eine iterative Lösung gehen.
Ich würde nicht empfehlen -
Mergesort ist ein Beispiel für eine Funktion, die beide nicht endrekursiv ist,
es ist nicht leicht zu machen endrekursiv,
sondern auch es ist nicht sehr einfach zu machen, iterativ.
Dies ist sehr einfach.
Diese Implementierung von Mergesort,
verschmelzen, egal was du tust, wirst du merge bauen.
>> So Mergesort auf der Oberseite des Merge gebaut rekursiv ist nur diese drei Linien.
Iterativ, ist es lästig und schwierig zu denken.
Aber beachten Sie, dass es nicht endrekursiv seit mergeSortHelp - wenn es selbst nennt -
es muss noch die Dinge nach dieser rekursiven Aufruf kehrt zu tun.
Also das Stack-Frame muss weiterhin auch nach dem Aufruf dieser existieren.
Und dann, wenn Sie diese aufrufen, muss der Stack-Frame weiter bestehen
denn auch nach diesem Anruf, müssen wir noch zu fusionieren.
Und es ist nicht trivial, um diese endrekursiv.
Haben Sie Fragen?
Gut.
So gehen zurück zu sortieren - oh, es gibt zwei Dinge, die ich zeigen wollen. Okay.
Gehen wir zurück zu sortieren, werden wir dies schnell zu tun.
Oder suchen. Sortieren? Sortieren. Yeah.
Gehen wir zurück zu den Anfängen der sort.
Wir wollen einen Algorithmus, der Art der Array mit einem beliebigen Algorithmus erstellen
O in der n.
Also, wie ist das möglich? Hat jemand eine Art von -
Ich deutete vorher an -
Wenn wir etwa von n log n bis O n zu verbessern,
wir unseren Algorithmus zeitlich verbessert,
was bedeutet, was sollen wir tun müssen, um Make-up für die damit?
[Schüler] Space. >> Ja. Wir gehen zu sein mit mehr Platz.
Und auch nicht nur mehr Platz, ist es exponentiell mehr Platz.
Also ich denke, diese Art von Algorithmus ist pseudo etwas, pseudo Polynom -
pseudo - ich kann mich nicht erinnern. Pseudo etwas.
Aber es ist, weil wir so viel Platz benötigen
dass dies erreichbar ist, jedoch nicht realistisch.
>> Und wie wollen wir das erreichen?
Wir erreichen dies, wenn wir garantieren, dass ein bestimmtes Element im Array
unter einer bestimmten Größe.
Also lasst uns einfach sagen, dass Größe 200,
jedes Element in einer Anordnung unterhalb Größe 200.
Und das ist eigentlich sehr realistisch.
Sie können sehr leicht ein Array, dass Sie alles wissen, in sie
wird auf weniger als eine bestimmte Anzahl.
Wie, wenn Sie etwas absolut riesig vector oder so etwas haben
aber du weißt alles wird zwischen 0 und 5 liegen,
dann wird es zu deutlich schneller, dies zu tun.
Und das gebundene auf einem der Elemente 5 ist,
so dass diese gebundene, das heißt, wie viel Speicher du gehst zu verwenden.
So ist die Grenze ist 200.
In der Theorie gibt es immer ein gebundenes da eine ganze Zahl kann nur bis zu 4 Milliarden,
aber das ist seitdem wir würden den Weltraum unrealistisch
in der Größenordnung von 4 Milliarden Euro. Also das ist unrealistisch.
Aber hier werden wir unsere gebundenen sagen, ist 200.
Der Trick, um es zu tun in O von n ist, dass wir einen weiteren Array namens zählt der Größe GEBUNDEN.
Also eigentlich ist dies eine Abkürzung für - ich eigentlich nicht weiß, ob Clang tut dies.
Aber in GCC zumindest - ich bin davon Clang tut es auch -
dies nur initialisiert das gesamte Array zu sein 0s.
Also, wenn ich nicht will, das zu tun, dann könnte ich separat zu tun (int i = 0;
i <BOUND; i + +) und zählt [i] = 0;
So, jetzt ist alles auf 0 initialisiert.
Ich über meine Array durchlaufen,
und was ich mache ist, dass ich das Zählen der Anzahl der einzelnen - LET'S GO hier unten.
Wir haben 4, 15, 16, 50, 8, 23, 42, 108.
Was ich zähle die Anzahl der Vorkommen jedes dieser Elemente.
Lasst uns tatsächlich ein paar mehr hinzuzufügen hier mit einigen Wiederholungen.
So wird der Wert wir hier haben, ist der Wert, werde Array [i].
So val konnte 4 oder 8 oder was auch immer.
Und jetzt bin ich zählen, wie viele dieser Wert ich gesehen habe,
so zählt [val] + +;
Nachdem dies geschehen ist, wird Zählungen werden etwas wie 0001 zu sehen.
Lasst uns zählt [val] - Bound + 1.
>> Nun, das ist nur für die Tatsache, dass wir von 0 beginnend ausmachen.
Also, wenn 200 wird unsere größte Zahl sein,
dann von 0 bis 200 ist 201 Sachen.
So zählt, werde es wie 00.001 aussehen, weil wir eine 4 haben.
Dann haben wir 0001, wo wir eine 1 in der 8. Index der Anzahl musst.
Wir werden eine 2 in der 23. Index der Zählung haben.
Wir werden eine 2 in der 42. Index der Zählung haben.
So können wir zählen.
So num_of_item = counts [i].
Und so, wenn num_of_item 2 ist, dass heißt, wir wollen 2 von der Anzahl i einfügen
in unsere sortierten Array.
Also müssen wir verfolgen, wie weit sind wir in das Array zu halten.
So index = 0.
Array - Ich werde nur schreiben.
Counts -
array [index + +] = i;
Ist das, was ich will? Ich denke, dass ist es, was ich will.
Ja, das sieht gut aus. Okay.
So wird jeder verstehen, was der Zweck meiner zählt Array ist?
Es wird das Zählen der Anzahl des Auftretens von jeder dieser Zahlen.
Dann bin ich Iteration über die zählt Array
und der i-ten Position in der Zählungen array
die Anzahl von i ist, die in meinem sortierten Array erscheinen soll.
Deshalb zählt der 4 wird 1 sein
und zählt von 8 wird 1 sein wird Grafen von 23 werde 2 sein.
Also das ist, wie viele von ihnen, dass ich in meiner sortierten Array einfügen möchten.
Dann habe ich nur tun.
Ich bin Einfügen num_of_item i ist in meinen sortierten Array.
>> Haben Sie Fragen?
Und so wieder, das ist die lineare Zeit, da wir gerade durchlaufen werden über dieses eine Mal,
aber es ist auch in dem, was passiert, diese Anzahl um die linear,
und so ist es hängt stark auf, was Ihre gebunden ist.
Mit einem Satz von 200, das ist nicht so schlimm.
Wenn Ihr gebundenen wird 10.000 sein, dann ist das ein wenig schlechter,
aber wenn Ihr gebundenen wird auf 4 Milliarden, das ist völlig unrealistisch
und das Array zu haben, um der Größe 4 Mrd., was unrealistisch ist.
So basta. Haben Sie Fragen?
[Unverständlich Student Response] >> Okay.
Ich erkannte eine andere Sache, wenn wir durch gingen.
Ich denke, das Problem war in Lucas 'und wahrscheinlich jeder einzelne wir gesehen haben.
Ich habe ganz vergessen.
Das einzige, was ich wollte zu kommentieren ist, dass wenn man mit Dingen wie Indizes zu tun haben,
Sie nie wirklich sehen, wenn Sie schriftlich eine suchen Schleife
aber technisch immer dann, wenn Sie mit diesen Indizes zu tun haben,
Sie sollten so ziemlich immer mit Ganzzahlen umzugehen.
Der Grund dafür ist, wenn Sie mit Ganzzahlen zu tun haben,
so, wenn Sie 2 Ganzzahlen mit Vorzeichen und fügen Sie sie zusammen
und sie zu groß zu beenden, dann am Ende mit einer negativen Zahl.
Also das ist, was Integer-Überlauf ist.
>> Wenn ich 2 Milliarden Euro und 1 Mrd. hinzuzufügen, habe ich am Ende mit negativen 1 Milliarde.
Das ist, wie ganze Zahlen auf Computern zu arbeiten.
Also das Problem bei der Verwendung -
Das ist in Ordnung, außer, wenn niedrige passiert 2 Milliarden und bis zufällig 1 Milliarde,
dann wird negativ sein 1 Mrd. und dann werden wir zu teilen, dass durch 2
und am Ende mit negativen 500 Millionen Euro.
So ist dies nur ein Problem, wenn Sie über ein Array zu suchen passieren
Milliarden von Dingen.
Aber wenn low + up passiert Überlauf, dann ist das ein Problem.
Sobald wir sie unsigned machen, dann 2 Milliarden plus 1 Mrd. 3 Milliarden Euro.
3 Milliarden geteilt durch 2 ist 1,5 Milliarden Euro.
So, sobald sie unsigned bist, ist alles perfekt.
Und damit ist auch ein Problem, wenn Sie Ihren sind für Schleifen,
und tatsächlich, ist es wahrscheinlich tut es automatisch.
Es wird eigentlich nur auf dich schreien.
Also, wenn diese Zahl ist zu groß, um in nur einer Zahl sein, aber es wäre in einem unsigned integer passen,
es wird dich anschreien, so das ist, warum Sie nie wirklich in das Thema laufen.
Sie können sehen, dass ein Index wird nie negativ sein,
und so, wenn Sie über ein Array durchlaufen,
Sie können fast immer sagen, unsigned int i, aber nicht wirklich zu.
Die Dinge werden sich ziemlich genau so gut funktionieren.
Okay. [Flüstert] Wie spät ist es?
Das letzte was ich wollte zeigen - und ich werde es einfach tun wirklich schnell.
Du weißt, wie wir # define damit wir # definieren MAX als 5 oder so etwas?
Lasst uns nicht MAX. # Define gebunden als 200. Das ist das, was wir vorher taten.
Das definiert eine Konstante, die gerade dabei ist, kopiert und eingefügt werden
wo immer wir zu schreiben GEBUNDEN.
>> So können wir tatsächlich mehr mit # definiert.
Wir können # define Funktionen.
Sie sind nicht wirklich funktioniert, aber wir nennen sie Funktionen.
Ein Beispiel wäre etwas wie MAX (x, y) wird als (?: X x <y y) definiert. Okay.
So sollten Sie auf ternäre Operator Syntax zu gewöhnen,
aber x kleiner als y? Zurück y, andernfalls kehren x.
So können Sie sehen, können Sie diesen eine separate Funktion zu machen,
und die Funktion könnte wie bool MAX dauert 2 Argumente, return this.
Dies ist eines der gebräuchlichsten Ich sehe, wie dies getan. Wir nennen sie Makros.
Dies ist ein Makro.
Dies ist nur die Syntax für sie.
Sie können ein Makro schreiben, zu tun, was Sie wollen.
Sie sehen oft Makros für das Debuggen printfs and stuff.
So eine Art von printf, gibt es spezielle Konstanten in C wie Unterstrich LINE unterstreichen,
2 unterstreicht LINE unterstreichen,
und es gibt auch ich glaube 2 unterstreicht FUNC. Das könnte es sein. So etwas Ähnliches.
Diese Dinge werden mit dem Namen der Funktion ersetzt werden
oder die Nummer der Zeile, die Sie sich gerade befinden.
Häufig, schreiben Sie mit dem Debuggen printfs, dass hier unten habe ich dann einfach schreiben konnte
DEBUG und es wird die Nummer der Zeile und Funktion, dass ich in sein passieren drucken
dass sie diesen Debug-Anweisung angetroffen.
Und Sie können auch ausdrucken andere Dinge.
So ein Sache, die Sie achten sollten ist, wenn ich # define DOUBLE_MAX passieren
so etwas wie 2 * y und 2 * x.
Also für welchen Gründen auch immer, passieren Sie, dass eine Menge zu tun.
So machen es zu einem Makro.
Dies ist tatsächlich gebrochen.
Ich würde es durch etwas wie DOUBLE_MAX (3, 6) nennen.
Also, was soll zurückgegeben werden?
[Schüler] 12.
Ja, Sie sollten 12 zurückgeführt werden, und 12 zurückgegeben.
3 wird für x ersetzt, wird 6 für y ersetzt, und wir kehren 2 * 6, die 12 ist.
Nun was ist das? Was sollte zurückgegeben werden?
[Schüler] 14. >> Idealfall 14.
Das Problem ist, dass, wie Hash definiert Arbeit, denken Sie daran, es ist eine wörtliche Kopie und Paste
der so ziemlich alles, so was, das wird so ausgelegt werden
3 ist weniger als 1 plus 6, 2 mal 1 plus 6, 2 mal 3.
>> So aus diesem Grund fast immer wickeln alles in Klammern.
Jede Variable, die Sie fast immer in Klammern wickeln.
Es gibt Fälle, wo man nicht haben, um, wie ich weiß, dass ich nicht brauchen, um das hier tun
da weniger als ist so ziemlich immer nur zur Arbeit gehen,
obwohl dies vielleicht nicht einmal wahr sein.
Wenn es etwas lächerlich wie DOUBLE_MAX (1 == 2),
dann ist das jetzt mit 3 weniger als 1 ersetzt zu bekommen ist gleich gleich 2,
und so dann wird es zu tun 3 kleiner als 1, bedeutet das gleich 2,
das ist nicht das, was wir wollen.
Um also keine Operatorvorrang Probleme zu vermeiden,
immer in Klammern zu wickeln.
Okay. Und das ist alles, 5:30.
Wenn Sie Fragen zum pset haben, lassen Sie es uns wissen.
Es soll Spaß machen, und die Hacker-Edition ist auch viel realistischer
als der Hacker-Ausgabe des vergangenen Jahres, so hoffen wir, dass viele von Ihnen es zu versuchen.
Im vergangenen Jahr war sehr überwältigend.
>> [CS50.TV]