[Powered by Google Translate] [Sectie 3 - Meer Comfortabele]
[Rob Bowden - Harvard University]
>> [Dit is CS50. - CS50.TV]
>> Dus de eerste vraag is vreemd geformuleerd.
GDB kunt u "debuggen" een programma, maar, meer in het bijzonder, wat doet het laten doen?
Ik zal antwoorden dat, en ik weet niet wat er precies verwacht,
dus ik denk dat het iets in de trant van het laat je stap voor stap
lopen door het programma, interactie met het, verandering variabelen, doe al deze dingen -
wezen volledige controle uitvoering van een programma
en inspecteren elk onderdeel van de uitvoering van het programma.
Dus die functies kunt u debuggen dingen.
Oke.
Waarom heeft binair zoeken voor dat een array gesorteerd?
Wie wil antwoord op geven?
[Student] Omdat het niet werkt als het niet gesorteerd. >> Ja. [Gelach]
Als het niet gesorteerd, dan is het onmogelijk om het in tweeën
en weet dat alles aan de linkerkant is minder en alles op de juiste
groter is dan de gemiddelde waarde.
Dus het moet worden gesorteerd.
Oke.
Waarom is bubble sort in O n kwadraat?
Is er iemand die wil eerst een zeer snelle high-level overzicht van wat bubble sort is geven?
[Student] Je eigenlijk gaan door elk element en u de eerste paar elementen.
Als ze uit waar je ruilen, dan u de komende elementen en ga zo maar door.
Als u het einde bereikt, dan weet je dat het grootste element wordt geplaatst aan het einde,
dus je negeren dat men dan blijf je doormaakt,
en elke keer moet je een minder element controleren totdat u geen wijzigingen. >> Ja.
Het heet bubble sort, want als je de array draait op zijn kant dus het is op en neer, verticaal,
dan is de grote waarden zal zinken naar de bodem en de kleine waarden wil borrelen naar de top.
Dat is hoe het zijn naam kreeg.
En ja, je gewoon doorlopen.
Je blijft gaan door de array, het omwisselen van de hogere waarde
de grootste waarden op de bodem.
>> Waarom is het O van n kwadraat?
Ten eerste, wil iemand zeggen waarom het O van n kwadraat?
[Student] Want voor elke run het n keer gaat.
U kunt alleen zeker van zijn dat je hebt genomen het grootste element helemaal naar beneden,
dan moet je dat herhalen voor zo veel elementen. >> Ja.
Dus hou in gedachten wat grote O betekent en wat grote Omega betekent.
De grote O is als de bovengrens op hoe traag het daadwerkelijk kan draaien.
Dus door te zeggen dat de O van n kwadraat, is het niet O van n of anders zou het te kunnen draaien
in lineaire tijd, maar het is O van n blokjes
omdat het begrensd door O n blokjes.
Als het begrensd door O van n kwadraat, dan is het ook begrensd door n blokjes.
Zodat het N kwadraat en in het ergste geval kan niet beter dan n kwadraat,
dat is waarom het is O van n in het kwadraat.
Dus om lichte wiskunde zien hoe het komt te zijn n kwadraat,
als we vijf dingen in onze lijst, de eerste keer hoeveel swaps kunnen we mogelijk moeten maken
om dit te krijgen? Laten we eigenlijk alleen maar -
Hoeveel swaps gaan we moeten in de eerste run van bubble sort maken door middel van de array?
[Student] n - 1. >> Ja.
>> Als er 5 elementen, gaan we nodig hebben om n te maken - 1.
Dan op de tweede hoeveel swaps gaan we moeten maken?
[Student] n - 2. >> Ja.
En de derde gaat worden n - 3, en dan voor het gemak zal ik schrijven de laatste twee
want dan gaan we nodig hebben om 2 swaps en 1 swap te maken.
Ik denk dat de laatste al dan niet echt nodig te gebeuren.
Is het een swap? Ik weet het niet.
Dus dit zijn de totale bedragen van de swaps of op zijn minst vergelijkingen die je moet maken.
Zelfs als je niet ruilen, moet je nog steeds de waarden te vergelijken.
Er zijn n - 1 vergelijkingen in de eerste run door de array.
Als u herschikken deze dingen, laten we in feite maakt het zes dingen dus dingen goed stapelen,
en dan doe ik 3, 2, 1.
Dus gewoon herschikken deze bedragen, willen we zien hoeveel vergelijkingen maken we
in het hele algoritme.
Dus als wij brengen deze jongens hier beneden,
dan zijn we nog maar optellen hoeveel vergelijkingen er waren.
Als we deze som en we optellen deze en we de som daarvan,
het is nog steeds hetzelfde probleem. We vatten deze specifieke groepen.
>> Dus nu zijn we optellen van 3 n's. Het is niet alleen 3 n's.
Het is altijd gaat worden n / 2 n's.
Dus hier zijn we toevallig 6 hebben.
Als we 10 dingen, dan kunnen we dit doen groepering voor 5 verschillende paren van de dingen
en eindigen met n + n + n + n + n.
Dus je zal altijd n / 2 n's te krijgen, en dus dit zullen we noteren het uit tot n kwadraat / 2.
En dus zelfs al is het de factor van de helft, die toevallig om binnen te komen
vanwege het feit dat door elke iteratie over de array vergelijken we een minder
dus dat is hoe we de meer dan 2, maar het is nog steeds n in het kwadraat.
We geven niet om de constante factor van een half.
Dus een veel grote O dingen zoals dit is gebaseerd op gewoon een soort van het doen van dit soort wiskunde,
uitvoeren van rekenkundige bewerkingen bedragen en geometrische reeks dingen,
maar de meeste van hen in deze cursus zijn vrij eenvoudig.
Oke.
Waarom is insertion sort in Omega van n? Wat betekent omega bedoel je?
[Twee studenten spreken in een keer - onverstaanbaar] >> Ja.
Omega kunt u denken aan de ondergrens.
>> Dus het maakt niet uit hoe efficiënt uw insertion sort-algoritme is,
ongeacht de lijst die wordt doorgegeven in, het heeft altijd te vergelijken ten minste n dingen
of het moet itereren over n dingen.
Hoe komt dat?
[Student] Want als de lijst is al gesorteerd, vervolgens door de eerste iteratie
kunt u alleen garanderen dat het eerste element is het minst,
en de tweede iteratie kun je alleen garanderen dat de eerste twee zijn
omdat je niet weet dat de rest van de lijst is gesorteerd. >> Ja.
Als u slaagt in een volledig gesorteerde lijst, op zijn minst moet je gaan over alle elementen
zien dat er niets moet worden verplaatst.
Dus die over de lijst en zegt oh, dit al gesorteerd,
is het onmogelijk voor u om te weten dat het gesorteerd totdat u de elk element
zien dat ze in gesorteerde volgorde.
Dus de ondergrens op insertion sort is Omega van n.
Wat is het ergste geval looptijd van merge sort,
ergste geval groot zijn O weer?
Dus in het ergste geval, hoe merge sort lopen?
[Student] N log n. >> Ja.
De snelste algemene sorteren algoritmen n log n. Je kunt niet beter doen.
>> Er zijn speciale gevallen, en als we tijd hebben vandaag - maar we zullen dat niet waarschijnlijk -
we konden zien een die het beter doet dan n log n.
Maar in het algemene geval, kun je niet beter doen dan n log n.
En samenvoegen sorteren gebeurt er met degene die je moet weten voor deze cursus, dat is n log n.
En dus zullen we daadwerkelijk uitvoering van dat vandaag de dag.
En tenslotte, in niet meer dan drie zinnen, hoe werkt selectie sorteren werk?
Heeft iemand wilt antwoorden, en Ik tel je zinnen
want als je meer dan 3 -
Heeft iemand herinner selectie sorteren?
Selectie soort is meestal vrij gemakkelijk te onthouden alleen uit de naam.
Je hoeft alleen itereren over de array, vinden wat de grootste waarde is of kleinste -
welke volgorde u sorteren inch
Dus laten we zeggen dat we het sorteren van klein naar groot.
U itereren over de array, op zoek naar wat de minimale element is,
selecteert u deze, en dan gewoon ruilen wat er in de eerste plaats.
En vervolgens op de tweede doorgang over de array, nogmaals naar het minimum element,
te selecteren, en dan ruilen met wat er in de tweede positie.
Dus we zijn gewoon plukken en het kiezen van de minimumwaarden
en ze te plaatsen in de voorkant van de array totdat het valt.
Vragen over zeggen?
>> Deze onvermijdelijk verschijnen in de formulieren die u moet invullen wanneer u het indienen van de PSET.
Dat zijn in principe de antwoorden op deze.
Oke, dus nu codering problemen.
Ik heb al verstuurd via e-mail - Heeft iemand niet dat e-mail? Oke.
Ik heb al verstuurd via e-mail de ruimte die we gaan gebruiken,
en als je klikt op mijn naam - dus ik denk dat ik ga op de bodem
als gevolg van de naar achteren r - maar als u klikt op mijn naam zie je 2 revisies.
Revisie 1 gaat al I worden gekopieerd en geplakt van de code in Spaces
voor het zoeken wat je gaat te hebben om uit te voeren.
En Revisie 2 zal het soort ding dat wij implementeren na dat.
Je kunt dus klik op mijn Herziening 1 en werk vanaf daar.
En nu willen we binaire zoekopdracht uit te voeren.
>> Wil iemand geef een pseudocode op hoog niveau uitleg
van wat we zullen moeten doen voor zoeken? Ja.
[Student] Je neemt gewoon het midden van de array en zien of wat je zoekt
kleiner is dan of meer dan dat.
En als het minder, ga je naar de helft die het minder,
en als het meer is, ga je naar de helft die meer en u dat herhalen totdat u gewoon een ding.
[Bowden] Ja.
Merk op dat onze array numbers al gesorteerd,
en dus dat betekent dat we kunnen profiteren van dat en we konden eerst controleren,
oke, ik ben op zoek naar het nummer 50.
Dus ik kan gaan in het midden.
Midden is moeilijk te definiëren als het een even aantal dingen,
maar laten we gewoon zeggen dat we altijd afkappen tot het midden.
Hier hebben we dus 8 dingen, zodat het midden zou zijn 16.
Ik zoek 50, dus 50 groter is dan 16.
Dus nu kan ik mijn array in principe te behandelen als deze elementen.
Ik kan weggooien alles van 16 over.
Nu is mijn array is alleen deze 4 elementen, en ik herhaal.
Dus dan wil ik naar het midden terug te vinden, is die zal worden 42.
42 is minder dan 50, dus ik kan weggooien deze twee elementen.
Dit is mijn resterende array.
Ik ga naar het midden terug te vinden.
Ik denk dat 50 was een slecht voorbeeld, want ik was altijd weg te gooien dingen naar links,
maar door dezelfde maatregel, als ik ben op zoek naar iets
en het is minder dan het element Ik ben momenteel op zoek naar,
dan ga ik weg te gooien alles naar rechts.
Dus nu moeten we dat implementeren.
Merk op dat we moeten gaan in grootte.
We kunnen ook niet nodig om hard-code grootte.
Dus als we te ontdoen van die # define -
Oke.
Hoe kan ik mooi erachter te komen wat de grootte van de array numbers op dit moment is?
>> Hoeveel elementen zijn in de aantallen array?
[Student] Numbers, beugels,. Lengte?
[Bowden] Dat bestaat niet in C.
Nodig hebben. Lengte.
Arrays niet eigenschappen hebben, dus er is geen eigenschap length van arrays
die net geeft je hoe lang het ook mag zijn.
[Student] Zie hoeveel geheugen het heeft en delen door hoeveel - >> Ja.
Dus hoe kunnen we zien hoeveel geheugen het heeft? >> [Student] sizeof. >> Ja, sizeof.
Sizeof is de exploitant dat gaat om de grootte van de array numbers terug te keren.
En dat gaat worden hoeveel getallen er zijn momenten van de grootte van een geheel getal
want dat is hoeveel geheugen het eigenlijk neemt op.
Dus als ik het aantal dingen in de array wilt,
dan ga ik te willen delen door de grootte van een geheel getal.
Oke. Dus dat laat me hier voorbij in grootte.
Waarom moet ik gaan in grootte op alle?
Waarom kan ik niet gewoon doen hier int size = sizeof (hooiberg) / sizeof (int)?
Waarom werkt dit niet?
[Student] Het is niet een globale variabele.
[Bowden] Hooiberg bestaat en we passeren in aantallen als hooiberg,
en dit is een soort van een voorafschaduwing van wat komen gaat. Ja.
[Student] Hooiberg is alleen de verwijzing naar het, dus het zou terugkeren hoe groot die verwijzing.
Ja.
Ik betwijfel in collegezaal dat u de stapel nog niet gezien echt, toch?
We hebben net gesproken over het.
Zodat de stapel waar al de variabelen zullen worden opgeslagen.
>> Elk geheugen dat is toegewezen voor lokale variabelen gaat in de stapel,
en elke functie krijgt zijn eigen ruimte op de stack, zijn eigen stack frame is hoe het heet.
Dus de belangrijkste heeft zijn stack frame, en de binnenkant van het gaat om deze array numbers bestaan,
en het gaat om de omvang van sizeof (nummers).
Het gaat om de grootte van getallen gedeeld door grootte van de elementen,
maar dat alle levens binnen stack belangrijkste frame van.
Als we een zoekmachine noemen, zoeken krijgt zijn eigen stack frame,
een eigen ruimte om al zijn lokale variabelen op te slaan.
Maar deze argumenten - dus hooiberg is geen kopie van deze hele array.
Wij geven in het gehele array als een kopie in zoeken.
Het gaat gewoon een verwijzing naar die array.
Dus zoek gaat naar deze nummers via deze referentie.
Het is nog steeds de toegang tot de dingen die leven in de stack belangrijkste's frame,
maar in principe, als we in pointers, die moet binnenkort,
dit is wat pointers zijn.
Pointers zijn gewoon verwijzingen naar dingen, en kunt u gebruik maken pointers om dingen te openen
die in andere dingen 'stapelen frames.
Dus ook al nummers zich lokaal op de belangrijkste, kunnen we nog steeds toegang tot het via deze pointer.
Maar omdat het is gewoon een pointer en het is gewoon een referentie,
sizeof (hooiberg) geeft alleen de grootte van de verwijzing zelf.
Het maakt niet terug van de grootte van het ding het is te wijzen op.
Het maakt niet terug de werkelijke grootte van de nummers.
En dus dit is niet van plan om te werken als we willen dat het.
>> Vragen over zeggen?
Pointers zal worden ingegaan in significant meer bloederige details in de komende weken.
En dit is de reden waarom veel van de dingen die je ziet, de meeste zoeken dingen of soort dingen,
ze bijna allemaal gaat nodig hebben om de werkelijke grootte van de array te nemen,
omdat in C, we hebben geen idee wat de grootte van de array is.
U moet handmatig doorgeven inch
En je kunt niet handmatig geschieden in het hele array omdat je op doorreis in de referentie-
en het kan de grootte niet te krijgen van de referentie.
Oke.
Dus nu willen we voeren wat werd uitgelegd.
Je kunt werken op het voor een minuut,
en je hoeft geen zorgen te maken over het krijgen van alles perfect 100% werken.
Schrijf gewoon de half pseudocode voor hoe je denkt dat het zou moeten werken.
Oke.
Geen behoefte om volledig gedaan met deze nog niet.
Maar heeft iemand zich gerust voelen met wat ze hebben tot nu toe,
als iets dat we kunnen werken met elkaar?
Is er iemand die als vrijwilliger willen werken? Of ik zal willekeurig kiezen.
Het hoeft niet gelijk te hebben door een maatregel, maar iets wat we kunnen veranderen in een werkende staat.
[Student] Tuurlijk. >> Oke.
Zo kunt u de herziening besparen door te klikken op het kleine pictogram Opslaan.
Je hebt Ramya, toch? >> [Student] Ja. >> [Bowden] Oke.
Dus nu kan ik bekijk uw revisie en iedereen kan trek de herziening.
En hier hebben we - Oke.
Dus Ramya ging met de recursieve oplossing, dat is zeker een geldige oplossing.
Er zijn twee manieren waarop u kunt dit probleem te doen.
U kunt dit doen iteratief of recursief.
De meeste problemen die je tegenkomt die recursief kan worden gedaan kan ook iteratief worden gedaan.
Dus hier hebben we het gedaan recursief.
>> Heeft iemand wilt definiëren wat het betekent om een ​​functie recursief?
[Student] Wanneer u een functie hebben noemen zich
en dan noemen zichzelf totdat het uit met echte en ware. >> Ja.
Een recursieve functie is gewoon een functie die zichzelf aanroept.
Er zijn drie grote dingen die een recursieve functie moet hebben.
De eerste is natuurlijk, het noemt zichzelf.
De tweede is het nulalternatief.
Dus op een gegeven moment de functie moet stoppen die zichzelf,
en dat is wat het nulalternatief is voor.
Dus hier zijn we weten dat we moeten stoppen, moeten we opgeven in onze zoektocht
als de start-end is gelijk aan - en we zullen zien wat dat betekent.
Maar uiteindelijk, het laatste ding dat belangrijk is voor recursieve functies:
de functies moeten een of andere manier benaderen het nulalternatief.
Net als je niet echt iets updaten wanneer u de tweede recursieve aanroep,
als je letterlijk het aanroepen van de functie opnieuw met dezelfde argumenten
en er geen globale variabelen zijn veranderd of wat dan ook,
zul je nooit bereiken van de base case, in welk geval dat is slecht.
Het zal een oneindige recursie en een stack overflow te zijn.
Maar hier zien we dat de update is gebeurt omdat we een update start + end / 2,
we updaten het einde argument hier, we het begin argument hier bijwerken.
Dus in alle recursieve oproepen we updaten iets. Oke.
Wilt u ons lopen door uw oplossing? >> Tuurlijk.
Ik gebruik SearchHelp zodat elke keer als ik deze functie oproep
Ik heb het begin van waar ik ben op zoek naar in de array en het einde
van waar ik ben op zoek de array.
>> Bij elke stap waar het zegt dat het is het midden element, dat begin + einde / 2,
is dat gelijk aan wat we zoeken?
En als het is, dan hebben we het gevonden, en ik denk dat dat wordt doorgegeven van de niveaus van recursie.
En als dat niet waar is, dan kunnen we kijken of dat middelste waarde van de array is te groot,
waarbij we kijken naar de linkerkant van de matrix door te gaan van start tot het midden index.
En anders doen we het einde helft.
[Bowden] Oke.
Klinkt goed.
Oke, dus een paar dingen, en eigenlijk is dit een zeer hoog niveau wat
dat zul je nooit moet weten voor deze cursus, maar het is waar.
Recursieve functies, hoort u altijd dat ze een slechte deal
want als je recursief noemt jezelf te vaak, krijg je stack overflow
omdat, zoals ik al eerder zei, elke functie krijgt zijn eigen stack frame.
Dus elke oproep van de recursieve functie krijgt zijn eigen stack frame.
Dus als je 1000 recursieve oproepen, krijg je 1.000 stack frames,
en snel je leiden tot het hebben te veel stack frames en dingen die er gewoon breken.
Dus dat is waarom recursieve functies zijn over het algemeen slecht.
Maar er is een mooi deel van recursieve functies genoemd staart-recursieve functies,
en dit gebeurt te zijn een voorbeeld van een waar als de compiler merkt dit
en het zou moeten, denk ik - in Clang als je langs het de-O2 vlag
dan zal het opvallen dat is staart recursieve en maken dingen goed.
>> Het zal opnieuw dezelfde stack frame over en weer voor elke recursieve aanroep.
En dus omdat je met dezelfde stack frame, hoeft u zich geen zorgen te maken over
ever stapel overlopen, en tegelijkertijd, zoals je gezegd
waar als je eenmaal true retourneren, dan heeft om terug te keren tot al deze stack frames
en de 10e oproep SearchHelp moet terugkeren naar de 9 moet terugkeren naar de 8e.
Dus dat hoeft niet te gebeuren wanneer functies zijn staart recursief.
En dus wat maakt deze functie staart recursieve is bericht dat voor een bepaald gesprek naar searchHelp
de recursieve aanroep die het maakt is wat het is terug te keren.
Dus in de eerste oproep tot SearchHelp, we ofwel onmiddellijk return false,
onmiddellijk terug true of we een recursieve aanroep van SearchHelp
waar wat we terugkeren is wat dat gesprek is terug te keren.
En we konden dit niet doen als we dat iets als int x = SearchHelp, return x * 2,
slechts enkele willekeurige verandering.
>> Dus nu deze recursieve aanroep, dit int x = SearchHelp recursieve aanroep,
is niet langer staart recursieve omdat het eigenlijk hoeft om terug te keren
terug naar een vorige stack frame zodat dat eerdere aanroep van de functie
kan dan iets doen met de return waarde.
Dit is dus niet de staart recursieve, maar wat we hadden voordat is mooi staart recursief. Ja.
[Student] Moet het tweede honk geval eerst worden gecontroleerd
want er kan een situatie zijn waar wanneer u doorgeven het argument
je hebt start = einde, maar ze zijn de naald waarde.
De vraag werd kunnen we niet lopen in het geval dat einde is de naald waarde
of start = einde, op de juiste wijze, start = einde
en je hebt niet echt gecontroleerd of bepaalde waarde nog niet,
dan beginnen + einde / 2 is gewoon op dezelfde waarde zijn.
Maar we hebben al weer vals, en we nooit echt gecontroleerd de waarde.
Dus op zijn minst in de eerste oproep, als de grootte gelijk is aan 0, dan willen we return false.
Maar als grootte is 1, dan start is niet van plan om gelijk einde,
en we zullen in ieder geval controleer dan de een element.
Maar ik denk dat je gelijk hebt in dat we kunnen eindigen in een geval waar te beginnen + einde / 2,
start eindigt als dezelfde als de beginpositie + einde / 2,
maar we hebben nooit echt gecontroleerd dat element.
>> Dus als we eerst het middelste element van de waarde die we zoeken,
dan kunnen we onmiddellijk terug waar.
Anders als ze gelijk zijn, dan is er geen enkel punt in voortdurende
omdat we gaan gewoon om te updaten naar een zaak waar we zijn op een single-element array.
Als dat enkel element is niet degene die we zoeken,
dan is alles verkeerd. Ja.
[Student] Het is dat aangezien maat is eigenlijk groter dan het aantal elementen in de array,
Er is al een offset - >> Zo zal size -
[Student] Zeg als de array was maat 0, dan is de SearchHelp ook daadwerkelijk controleren hooiberg van 0
op het eerste gesprek.
De array heeft grootte 0, dus de 0 is - >> Ja.
Er is nog een ding dat - het zou goed zijn. Laten we denken.
Dus als de array heeft 10 elementen en de middelste we gaan om te controleren is index 5,
dus we zijn het controleren van 5, en laten we zeggen dat de waarde lager is.
Dus we gooien alles uit de buurt van 5 verder.
Dus begin + einde / 2 gaat onze nieuwe einde zijn,
dus ja, het is altijd gaan om te verblijven na het einde van de array.
Als het een geval als het even of oneven, dan zouden we controleren, zegt, 4,
maar we zijn nog steeds weg te gooien -
Dus ja, is uiteindelijk altijd zal zijn dan het werkelijke einde van de array.
Dus de elementen richten we ons op, wordt uiteindelijk altijd naar de een na dat.
En dus als start doet ooit gelijk einde, we zijn in een array van grootte 0.
>> Het andere wat ik zat te denken is dat we beginnen met het bijwerken te starten + einde / 2,
dus dit is het geval dat ik heb problemen met, in voorkomend start + end / 2
is het element dat we het controleren.
Laten we zeggen dat we hadden deze 10-element array. Het zal wel.
Dus begin + einde / 2 gaat iets als dit een zijn,
en als dat niet de waarde, zeggen dat we willen werken.
De waarde is groter, dus we kijken naar deze helft van de array.
Dus hoe we beginnen met updaten, we updaten start nu dit element.
Maar dit kan nog steeds werken, of op zijn minst, wat je kunt doen begin + einde / 2 + 1.
[Student] Je hoeft niet te + einde te beginnen [onverstaanbaar] >> Ja.
We hebben al gekeken dit element en weet dat het niet degene die we zoeken.
Dus we hoeven niet te beginnen bij te werken om dit element te zijn.
We kunnen gewoon overslaan en bij te werken beginnen om dit element te zijn.
En is er ooit een geval, laten we zeggen, dat dit zou eindigen,
dus dan beginnen zou dit, start + end / 2 zou zijn dit,
begin + einde - Ja, ik denk dat het kan eindigen in oneindige recursie.
Laten we zeggen dat het is gewoon een array van grootte 2 of een array van grootte 1. Ik denk dat dit zal werken.
Dus op dit moment, begin is dat element en het einde is 1 daarbuiten.
Dus het element dat we gaan om te controleren is deze,
en toen we begin te werken, werken we beginnen te zijn 0 + 1/2,
die gaat ons uiteindelijk terug met start wordt dit element.
>> Dus we controleren hetzelfde element over en weer.
Dus dit is het geval wanneer elke recursieve aanroep moet daadwerkelijk bij te werken iets.
Dus moeten we begin + einde / 2 + 1, of anders te doen is er een geval
waar we eigenlijk niet updaten start.
Iedereen ziet dat?
Oke.
Heeft iemand vragen over deze oplossing of een ander commentaar?
Oke. Heeft iemand een hebben iteratieve oplossing die we allemaal kunnen kijken?
Hebben we allemaal recursief doen?
Of ook ik denk dat als je geopend van haar, dan kun je misschien overschreven hebt je vorige.
Is het automatisch opslaan? Ik ben niet positief.
Heeft iemand hebben iteratieve?
We kunnen samen wandelen door het zo niet.
Het idee zal hetzelfde.
Iteratieve oplossing.
We gaan willen in principe doen hetzelfde idee
waar we willen muziekstuk van de nieuwe einde van de array en de nieuwe start van de array te houden
en dat doen over en voorbij.
En als wat we het bijhouden van als het begin en het einde ooit kruisen,
dan hebben we het niet vinden en we kunnen terugkeren vals.
Dus hoe doe ik dat? Iedereen heeft suggesties of code voor mij op te trekken?
[Student] Doe een while-lus. >> Ja.
Je gaat te willen om een ​​lus te doen.
>> Had je code die ik kon trekken, of wat was je van plan om te suggereren?
[Student] Ik denk het wel. >> Oke. Dit maakt het makkelijker. Wat was je naam?
[Student] Lucas.
Herziening 1. Oke.
Low is wat wij genoemd starten voor.
Up is niet helemaal wat we noemden einde voor.
Eigenlijk einde nu in de array. Het is een element dat we moeten overwegen.
Zo laag is 0, tot de grootte van de matrix - 1,
en nu zijn we een lus, en we controleren -
Ik denk dat je kunt er doorheen.
Wat was je denken door dit? Loop met ons op via uw code.
[Student] Tuurlijk. Kijk naar de hooiberg waarde in het midden en vergelijk het met de naald.
Dus als het groter is dan de naald, dan wil je - oh, eigenlijk, dat moet naar achteren zijn.
Je gaat te willen om weg te gooien de rechter helft, en zo ja, dat moet het zo zijn.
[Bowden] Dus dit moet minder zijn? Is dat wat je zei? >> [Student] Ja.
[Bowden] Oke. Minder.
Dus als wat we zoeken naar kleiner is dan wat we willen,
dan ja, we willen om weg te gooien de linker helft,
wat betekent dat we zijn alles wat we overwegen het bijwerken
door het bewegen van laag naar rechts van de array.
Dit ziet er goed uit.
Ik denk dat het hetzelfde probleem dat we al op de vorige,
waar als laag is 0 en up is 1, dan lage + omhoog / 2 gaat opzetten om hetzelfde weer.
>> En zelfs als dat niet het geval is nog efficiënter althans
om gewoon weg te gooien het element dat we keek alleen maar naar waar we weten dat het verkeerd is.
Dus lage + omhoog / 2 + 1 - >> [student] Dat moet de andere kant op te zijn.
[Bowden] Of dit moet - 1 en de andere moet + 1.
[Student] En er moet een dubbel is-teken. >> [Bowden] Ja.
[Student] Ja.
Oke.
En tot slot, nu hebben we dit + 1 - 1 ding,
is het - het is misschien niet - is het ooit mogelijk voor lage om te eindigen met een waarde groter dan op?
Ik denk dat de enige manier waarop dat kan gebeuren - Is het mogelijk? >> [Student] Ik weet het niet.
Maar als het wordt afgekapt en dan krijgt minus die 1 en vervolgens - >> Ja.
[Student] Het zou eventueel krijgen messed up.
Ik denk dat het zou goed moeten zijn maar omdat
voor het naar uiteindelijk lager zouden ze gelijk zijn, denk ik.
Maar als ze gelijk zijn, dan zouden we niet hebben gedaan de while-lus om te beginnen met
en we zouden zijn teruggekeerd van de waarde. Dus ik denk dat we nu goed.
Merk op dat hoewel dit probleem niet langer recursief,
het zelfde soort ideeën toe te passen, waar we kunnen zien hoe dit zo gemakkelijk leent zich
een recursieve oplossing door het feit dat we nog maar net de indexen updaten over en weer,
we maken het probleem kleiner en kleiner, we focussen op een deel van de array.
[Student] Als laag is 0 en up 1 is, zouden zij beide 0 + 1/2, die naar 0,
en men zou + 1, zou men - 1.
[Student] Waar gaan we controleren gelijkheid?
Net als de middelste eigenlijk naald?
We zijn op dit moment niet om dat te doen? Oh!
Als het is -
Ja. We kunnen niet gewoon de test hier beneden, want laten we zeggen dat de eerste midden -
[Student] Het is eigenlijk net als niet weggooien het gebonden.
Dus als je weggooien gebonden, je moet het eerst controleren of wat dan ook.
Ah. Ja. >> [Student] Ja.
Dus nu hebben we weggegooid degene die we op dit moment gekeken naar,
wat betekent dat we nu moeten ook
if (hooiberg [(laag + up) / 2] == naald), dan kunnen we return true.
En of ik anders of gewoon als, het betekent letterlijk hetzelfde
omdat dit zou zijn teruggekeerd waar.
Dus ik zal anders gezet of, maar het maakt niet uit.
>> Dus anders als dit, anders deze, en dit is een veel voorkomende wat ik doe
waar zelfs indien dit het geval is waar alles is hier goed,
zoals lage kan nooit groter zijn dan op, het is niet de moeite waard redenering over de vraag of dat waar is.
Dus je kan net zo goed zeggen, terwijl een lage kleiner is dan of gelijk is aan
of terwijl laag kleiner is dan
dus als ze ooit gelijk of lage gebeurt om te laten liggen,
dan kunnen we doorbreken van deze lus.
Vragen, zorgen, opmerkingen?
Oke. Dit ziet er goed uit.
Nu willen we sorteren doen.
Als we naar mijn tweede herziening, zien we deze zelfde nummers,
maar nu zijn ze niet meer in gesorteerde volgorde.
En we willen sorteren implementeren met behulp van een algoritme in O n log n.
Dus welke algoritme denk je dat we hier moeten voeren? >> [Student] Merge soort.
[Bowden] Ja. Samenvoegen soort is O (n log n), dus dat is wat we gaan doen.
En het probleem zal zijn redelijk vergelijkbaar,
wanneer leent zich gemakkelijk een recursieve oplossing.
We kunnen ook komen met een iteratieve oplossing als we willen,
maar recursie zal gemakkelijker zijn hier en we moeten doen recursie.
Ik denk dat we eerst lopen door merge sort,
hoewel er is een mooie video op merge sort reeds. [Gelach]
Dus samenvoegen soort zijn er - ik ben het verspillen van zoveel van deze paper.
Oh, er is maar een over.
Dus samen te voegen.
O, 1, 3, 5.
Oke.
Merge neemt twee afzonderlijke arrays.
Individueel deze twee arrays beide gesorteerd.
Dus array, 1, 3, 5, gesorteerd. Deze array, 0, 2, 4, gesorteerd.
Nu, wat samenvoegen moet doen is deze combineren in een enkele array die zelf gesorteerd.
Dus we willen een array van maat 6 dat gaat deze elementen hebben de binnenkant van het
in gesorteerde volgorde.
>> En dus kunnen we profiteren van het feit dat deze twee arrays zijn gesorteerd
om dit te doen in de lineaire tijd,
lineaire tijd betekenis als deze array is een maat XS en dit is maat y,
dan is de totale algoritme moet O (x + y). Oke.
Dus suggesties.
[Student] Kunnen we beginnen van links?
Dus je zet de 0 naar beneden en vervolgens de 1 en vervolgens hier ben je op de 2.
Dus het is een soort heb je een tabblad dat beweegt naar rechts. >> [Bowden] Ja.
Voor beide arrays als we gewoon focussen op de meest linkse element.
Omdat beide arrays worden gesorteerd, weten we dat deze 2 elementen
de kleinste elementen in beide array.
Dus dat betekent dat 1 van deze 2 elementen moeten het kleinste element in onze samengevoegde array.
Het is gewoon zo gebeurt het dat de kleinste is de een aan de rechter deze keer.
Dus we nemen 0, plaatst u deze op de linker omdat 0 kleiner is dan 1,
dus neem 0, plaatst u deze in de eerste plaats, en dan gaan we updaten
tot nu concentreren op het eerste element.
En nu zijn we herhalen.
Dus nu vergelijken we 2 en 1. 1 kleiner is, dus we zullen plaatsen 1.
We updaten deze pointer om te wijzen op deze kerel.
Nu gaan we het weer doen, dus 2. Dit zal werken, vergelijk deze 2, 3.
Deze updates, vervolgens 4 en 5.
Dus dat is merge.
>> Het moet vrij duidelijk dat het lineaire tijd geleden dat we maar een keer naar de overkant van elk element.
En dat is de grootste stap voor de uitvoering merge sort dit doet.
En het is niet zo moeilijk.
Een paar dingen zorgen te maken over is laten we zeggen dat we 1, 2, 3, 4, 5, 6 samenvoegen.
In dit geval eindigen in het scenario waarin deze zal kleiner,
dan kunnen we deze pointer updaten, deze gaat worden kleiner, updaten,
Deze is kleiner, en nu heb je te herkennen
als je daadwerkelijk hebt opraken van de elementen te vergelijken met.
Omdat we al gebruik gemaakt van deze hele array,
alles in deze reeks wordt nu gewoon ingevoegd in hier.
Dus als we ooit in het punt waar een van onze arrays volledig is al samengevoegd,
dan kunnen we gewoon alle elementen van de andere array en steek ze in het einde van de array.
Dus we kunnen gewoon plaats 4, 5, 6. Oke.
Dat is een ding om op te letten.
Uitvoering van dat moet stap 1 zijn.
Samenvoegen vervolgens sorteren op basis van dat, het is 2 stappen, 2 domme stappen.
Laten we geven deze array.
Dus samenvoegen sorteren, stap 1 is om de array recursief te breken in twee helften.
Dus splitsen deze array in twee helften.
We hebben nu 4, 15, 16, 50 en 8, 23, 42, 108.
En nu doen we het weer en we splitsen deze in twee helften.
Ik doe het gewoon aan deze kant.
Dus 4, 15 en 16, 50.
Wij zouden hetzelfde doen hier.
En nu hebben we splitsen in twee helften weer.
En we hebben 4, 15, 16, 50.
Dus dat is ons basisscenario.
Zodra de arrays zijn van maat 1, dan stoppen we met de splitsing in twee helften.
>> Nu wat doen we hiermee?
We uiteindelijk zal dit ook worden onderverdeeld in 8, 23, 42 en 108.
Dus nu dat we op dit punt, nu stap twee van merge sort is gewoon paren samen te voegen aan de lijsten.
Dus willen we deze samen te voegen. We noemen samen te voegen.
We weten merge zullen deze terugkeren in gesorteerde volgorde.
4, 15.
Nu willen we deze samenvoegen, en dat zal een lijst terug met die in gesorteerde volgorde,
16, 50.
We samenvoegen die - ik kan niet schrijven - 8, 23 en 42, 108.
Dus we hebben samengevoegd paren een keer.
Nu zijn we gewoon weer samen te voegen.
Merk op dat elk van deze lijsten gesorteerd op zichzelf
en dan kunnen we gewoon samenvoegen deze lijsten om een ​​lijst van grootte 4, die wordt gesorteerd te krijgen
en samenvoegen van deze twee lijsten om een ​​lijst met maat 4 dat wordt gesorteerd te krijgen.
En tot slot, kunnen we samenvoegen die twee lijsten van grootte 4 om een ​​lijst met maat 8 die wordt gesorteerd te krijgen.
Dus om te zien dat dit is over het algemeen n log n, zagen we al dat samenvoegen lineair is,
dus als we te maken hebben met het samenvoegen van deze, dus als de totale kosten van de fusie
voor deze twee lijsten is slechts 2 omdat -
Of wel, het is o van n, maar n is vaak precies deze 2 elementen, dus het is 2.
En deze 2 zal 2 en deze 2 zal 2 en deze 2 een 2,
dus in alle van de samenvoegingen die we moeten doen, we uiteindelijk doen n.
Zoals 2 + 2 + 2 + 2 8, dat n,
zodat de kosten van het samenvoegen van in deze set is n.
En dan is het hetzelfde hier.
We zullen samenvoegen van deze 2, dan zijn deze 2, en individueel deze samenvoeging zal vier operaties,
deze samenvoeging zal vier operaties, maar nogmaals, tussen al deze,
we uiteindelijk samen te voegen n totaal dingen, en dus deze stap neemt n.
En zo elk level duurt n elementen worden samengevoegd.
>> En hoeveel levels zijn er?
Op elk niveau, ons aanbod groeit met maat 2.
Hier onze arrays zijn van maat 1, hier zijn ze van grootte 2, hier zijn ze van maat 4,
en tot slot, ze zijn van maat 8.
Dus aangezien verdubbelt, er zullen in totaal n log van deze niveaus.
Dus met log n niveaus, elk individueel niveau rekening n totale bedrijfsactiviteiten,
krijgen we een n log n algoritme.
Vragen?
Al mensen hebben vooruitgang geboekt over hoe dit te implementeren?
Is er iemand al in een staat waar ik kan gewoon omhoog trekken hun code?
Ik kan een minuut.
Deze gaat langer.
I highly recommend terugkomen -
Je hoeft niet te recursie doen voor samenvoegen
want om recursie voor samenvoegen doen, je gaat te hebben om een ​​aantal verschillende maten passeren.
Dat kan, maar het is vervelend.
Maar recursie voor soort zelf is vrij eenvoudig.
Je hoeft alleen letterlijk belt sorteren op de linker helft, sorteren op rechter helft. Oke.
Iedereen heeft iets wat ik kan nog omhoog te trekken?
Of anders geef ik een minuut.
Oke.
Iedereen heeft iets dat we kunnen samenwerken?
Of we zullen gewoon werken met deze uit en vouw vervolgens vanaf daar.
>> Iedereen heeft meer dan dit dat ik kan trekken?
[Student] Ja. U kunt trekken mijne. >> Oke.
Ja!
[Student] Er waren een heleboel voorwaarden. >> Oh, schieten. Kunt u -
[Student] Ik heb het op te slaan. >> Ja.
Dus we hebben afzonderlijk doen de samenvoeging.
Oh, maar het is niet zo slecht.
Oke.
Dus soort is zelf alleen maar bellen mergeSortHelp.
Leg ons uit wat mergeSortHelp doet.
[Student] MergeSortHelp vrij doet veel van de twee belangrijke stappen:
die elk de helft van de array vervolgens sorteren en beide samenvoegen.
[Bowden] Oke, dus geef me een seconde.
Ik denk dat dit - >> [student] Ik moet -
Ja. Ik mis iets.
In samenvoegen, realiseer ik me dat ik nodig om een ​​nieuwe array te maken
want ik kon het niet op zijn plaats. >> Ja. Dat kan niet. Te corrigeren.
[Student] Dus ik maak een nieuwe array.
Ik vergat aan het einde van samenvoegen om opnieuw te veranderen.
Oke. We hebben een nieuwe array.
In merge sort, is dit bijna altijd het geval.
Deel van de kosten van een beter algoritme qua tijd
is bijna altijd om een ​​beetje meer geheugen te gebruiken.
Dus hier, maakt niet uit hoe je het doet samenvoegen sorteren,
je zou onvermijdelijk moet u een aantal extra geheugen te gebruiken.
Hij of zij een nieuwe array.
En dan zeg je aan het eind we hoeven alleen maar nieuwe array te kopiëren naar de oorspronkelijke array.
[Student] Ik denk het wel, ja.
Ik weet niet of dat werkt op het gebied van het tellen door middel van verwijzing of wat dan ook -
Ja, dan werkt het. >> [Student] Oke.
Heb je geprobeerd het uitvoeren van deze? >> [Student] Nee, nog niet. >> Oke.
Probeer het dan, en dan zal ik over te praten voor een tweede.
[Student] Ik moet al de functie prototypes en alles hebben, toch?
De functie prototypes. Oh, je bedoelt zoals - Ja.
Sorteer roept mergeSortHelp.
>> Dus om te sorteren mergeSortHelp bellen, moet mergeSortHelp ofwel reeds zijn gedefinieerd
voordat sorteren of hoeven we alleen maar het prototype. Kopieer en plak deze.
En evenzo is mergeSortHelp roept samen te voegen,
maar samenvoegen is nog niet gedefinieerd, dus we kunnen gewoon laten mergeSortHelp weten
dat dat is wat samen te voegen gaat uitzien, en dat is dat.
Dus mergeSortHelp.
We hebben een probleem hier, waar we geen base case.
MergeSortHelp recursieve is, dus elke recursieve functie
gaat een soort van base case moet weten wanneer te stoppen recursief die zichzelf.
Wat is ons basisscenario gaan worden hier? Ja.
[Student] Als het formaat is 1? >> [Bowden] Ja.
Dus, zoals we zagen daar, stopten we splitsen arrays
toen we eenmaal in arrays van maat 1, die onvermijdelijk zijn gesorteerd zelf.
Dus als de grootte gelijk is aan 1, we weten dat de array al gesorteerd,
dus we kunnen gewoon terug.
>> Merk op dat is leegte, zodat we niet terug niets bijzonder, we zijn net terug.
Oke. Dus dat is ons basisscenario.
Ik denk dat ons basisscenario kan ook als we toevallig samengaan van een array van grootte 0,
we waarschijnlijk willen stoppen op een bepaald punt,
zodat we zeggen van minder dan 2 of minder dan of gelijk aan 1
zodat dit nu voor welke array.
Oke.
Dus dat is ons basisscenario.
Nu wil je ons lopen door merge?
Wat betekenen al deze gevallen betekenen?
Hier boven, we gewoon doen hetzelfde idee, de -
[Student] Ik moet passeren grootte met alle mergeSortHelp oproepen.
Ik voegde formaat als een bijkomende primaire en het is er niet, zoals grootte / 2.
[Bowden] Oh, de grootte / 2, size / 2. >> [Student] Ja, en ook in de bovenstaande functie.
[Bowden] hier? >> [Student] op het juiste formaat. >> [Bowden] Oh. Maat, maat? >> [Student] Ja.
[Bowden] Oke.
Laat me denken voor een tweede.
Hebben we tegenkomen een probleem?
We zijn altijd op de behandeling van de linker als 0. >> [Student] Nee.
Dat is verkeerd ook. Sorry. Het moet start. Ja.
[Bowden] Oke. Ik vind dat beter.
En einde. Oke.
Dus nu wil je ons lopen door merge? >> [Student] Oke.
Ik ben gewoon wandelen door deze nieuwe array die ik heb gemaakt.
Het is de grootte van het deel van de array die we willen worden gesorteerd
en proberen om het element en die ik moet in de nieuwe array stap vinden.
Dus om dat te doen, eerst ben ik controleren of de linkerhelft van de array blijft nog meer elementen,
en als het niet zo is, dan moet je naar beneden naar die andere voorwaarde, die gewoon zegt
oke, moet het in de juiste array, en we zullen dat zet in de huidige index van newArray.
>> En anders ik controleren of de rechterzijde van de array wordt ook beëindigd,
in welk geval ik net in de linker.
Dat zou eigenlijk nodig. Ik weet het niet zeker.
Maar goed, de andere twee controle welke van de twee zijn kleiner in de linker-of de rechterkant.
En ook in elk geval, ik ben het verhogen afhankelijk van welke tijdelijke aanduiding I verhogen.
[Bowden] Oke.
Dat ziet er goed uit.
Heeft iemand opmerkingen of vragen hebt of vragen?
Dus de vier gevallen die we hebben om dingen te brengen alleen maar - of het lijkt op vijf -
maar we moeten overwegen of de linker-array leeg is van dingen die we nodig hebben om te fuseren,
de vraag of de rechter array leeg is van dingen die we nodig hebben om te fuseren -
Ik wees naar niets.
Dus of de linker-array op is van de dingen of de rechter array leeg is van de dingen.
Dat zijn twee gevallen.
We moeten ook de triviale geval van de vraag of de linker ding is kleiner dan het juiste ding.
Dan willen we aan de linkerkant iets te kiezen.
Dat zijn de gevallen.
Dus dit was goed, dus dat is dat.
Array vertrokken. Het is 1, 2, 3. Oke. Dus ja, dat zijn de vier dingen die we zouden willen doen.
En we zullen niet gaan over een iteratieve oplossing.
Ik zou niet aanraden -
Merge sort is een voorbeeld van een functie die zowel niet staart recursieve,
het is niet gemakkelijk om het staart recursieve,
maar ook het is niet erg makkelijk te maken iteratieve.
Dit is erg gemakkelijk.
Deze implementatie van merge sort,
samenvoegen, maakt niet uit wat je doet, je gaat samenvoegen bouwen.
>> Dus samenvoegen sorteren gebouwd op de top van de merge recursief is gewoon deze drie lijnen.
Iteratief, het is meer vervelend en moeilijker om na te denken over.
Maar let erop dat het niet de staart recursieve sinds mergeSortHelp - wanneer het noemt zichzelf -
Het moet nog dingen te doen na deze recursieve aanroep terug.
Dus dit stack frame moet blijven bestaan, zelfs na het aanroepen van deze.
En dan, als je dit noemen, moet de stack frame blijven bestaan
want zelfs na dat gesprek, we moeten nog steeds om te fuseren.
En het is niet-triviaal om deze staart recursieve.
Vragen?
Oke.
Dus terug te gaan naar sorteren - oh, er zijn twee dingen die ik wil laten zien. Oke.
Terug te gaan naar soort, zullen we dit snel doen.
Of zoek. Sorteer? Sorteren. Ja.
Terug te gaan naar het begin van de soort.
We willen een algoritme dat sorteert de array met behulp van een algoritme te creëren
in O n.
Dus hoe is dit mogelijk? Heeft iemand enig soort van -
Ik zinspeelde eerder bij -
Als we op het punt om te verbeteren van n log n N en O van n,
we hebben ons algoritme qua tijd,
wat betekent dat wat gaan we moeten doen om goed te maken dat?
[Student] Space. >> Ja. We gaan gebruik maken van meer ruimte.
En zelfs niet alleen meer ruimte, het is exponentieel meer ruimte.
Dus ik denk dat dit soort algoritme is pseudo iets, pseudo polynoom -
pseudo - Ik kan me niet herinneren. Pseudo iets.
Maar het is, want we moeten zo veel ruimte te gebruiken
dat dit haalbaar is, maar niet realistisch.
>> En hoe gaan we dat bereiken?
We kunnen bereiken als we garantie dat een bepaald element in de array
lager is dan een bepaalde grootte.
Dus laten we gewoon zeggen dat de grootte is 200,
elk element in een array is dan maat 200.
En dit is eigenlijk heel realistisch.
U kunt heel gemakkelijk een array die u alles te weten in het
zal minder dan een getal.
Net als je wat echt enorm vector of iets
maar je weet dat alles zal worden tussen 0 en 5,
dan is het gaat worden aanzienlijk sneller om dit te doen.
En de gebonden op een van de elementen 5,
dus dit gebonden, dat is hoeveel geheugen je gaat gebruiken.
Dus het gebonden is 200.
In theorie is er altijd een gebonden omdat een integer kan alleen tot 4 miljard
maar dat is niet realistisch sindsdien zouden we gebruik van de ruimte
in de orde van 4 miljard. Dus dat is niet realistisch.
Maar hier zullen we zeggen dat onze gebonden is 200.
De truc om het te doen in O van n is maken we nog een array met de naam tellingen van grootte GEBONDEN.
Dus eigenlijk is dit een snelkoppeling voor - ik eigenlijk weet niet of Clang dit doet.
Maar in GCC op zijn minst - Ik ben ervan uitgaande dat Clang doet het ook -
Dit zal alleen initialiseren van de hele array te 0s.
Dus als ik niet wil om dat te doen, dan kon ik apart doen for (int i = 0;
i <BOUND; i + +) en telt [i] = 0;
Dus nu alles wordt geïnitialiseerd op 0.
Ik itereren over mijn array,
en wat ik doe is dat ik het nummer van elk tellen - Laten we hier naar beneden gaan.
We hebben 4, 15, 16, 50, 8, 23, 42, 108.
Wat ik reken is het aantal keren dat elk van deze elementen.
Laten we eigenlijk nog een paar toe te voegen in hier met een aantal herhalingen.
Dus de waarde die we hier hebben, wordt de waarde van die zal worden array [i].
Dus val zou kunnen zijn 4 of 8 of wat dan ook.
En nu ben ik te tellen hoeveel van die waarde die ik heb gezien,
dus telt [val] + +;
Nadat dit is gedaan, wordt tellingen gaat iets eruit 0001.
Laten we het doen telt [val] - GEBONDEN + 1.
>> Nu dat is gewoon om te corrigeren voor het feit dat we vanaf 0.
Dus als 200 gaat onze grootste getal zijn,
dan 0 tot 200 is 201 dingen.
Dus telt, zal het lijken 00001, omdat we een 4.
Dan hebben we 0001 waar we een 1 hebben in de 8e index van tellen.
We hebben een 2 in de 23e index van tellen.
We hebben een 2 in de 42e index van tellen.
Dus we kunnen gebruiken tellen.
Dus num_of_item = telt [i].
En dus als num_of_item 2 is, betekent dat we willen 2 te plaatsen van het getal i
in onze gesorteerde array.
Dus we moeten om bij te houden hoe ver we zijn in de array.
Dus index = 0.
Array - Ik zal gewoon schrijven.
Counts -
array [index + +] = i;
Is dat wat ik wil? Ik denk dat dat is wat ik wil.
Ja, dit ziet er goed uit. Oke.
Dus heeft iedereen begrijpt wat het doel van mijn tellingen array is?
Het tellen van het aantal keren dat elk van deze nummers.
Dan ben ik itereren over dat telt array,
en het ide positie in de matrix telt
is het aantal i's dat moet worden weergegeven in mijn gesorteerde array.
Daarom telt van 4 gaat op 1
en tellingen van 8 gaat worden 1 wordt tellingen van 23 zal worden 2.
Dus dat is hoe velen van hen wil ik invoegen in mijn gesorteerde array.
Tot slot heb ik dat doen.
Ik ben het invoegen van num_of_item i's in mijn gesorteerde array.
>> Vragen?
En dus nogmaals, dit is lineaire tijd geleden dat we zijn gewoon itereren over deze ene keer,
maar het is ook lineair in wat dit nummer zich bevindt,
en dus het hangt sterk af van wat je gebonden is.
Met een gebonden van 200, dat is niet zo erg.
Als je gebonden gaat worden 10.000, dan is dat een beetje erger,
maar als je gebonden gaat worden 4 miljard, dat is volkomen onrealistisch
en deze array zal moeten worden van maat 4 miljard, hetgeen niet realistisch is.
Dus dat is dat. Vragen?
[Onverstaanbaar student reactie] >> Oke.
Ik realiseerde me een ander ding toen we gaan door.
Ik denk dat het probleem was in Lucas en waarschijnlijk een ieder die we hebben gezien.
Ik ben het helemaal vergeten.
Het enige wat ik wilde commentaar geven op is dat wanneer je te maken hebt met dingen als indices,
je nooit echt zien als je aan het schrijven bent een for-lus,
maar technisch, wanneer je te maken hebt met deze indices,
moet u vrijwel altijd te gaan met gehele getallen zonder teken.
De reden hiervoor is als je te maken hebt met ondertekend integers,
dus als je 2 getekend gehele getallen en voegt u ze samen
en ze uiteindelijk te groot, dan eindig je met een negatief getal.
Dus dat is wat integer overflow is.
>> Als ik voeg 2 miljard en 1 miljard, ik eindigen met een negatieve 1 miljard.
Dat is hoe integers werken op computers.
Het probleem met het gebruik -
Dat is goed, behalve als lage toevallig 2 miljard en tot toevallig 1 miljard,
dan gaat dit als negatief 1 miljard en dan gaan we delen door 2
en eindigen met een negatieve 500 miljoen.
Dus dit is alleen een probleem als je toevallig op zoek door middel van een reeks
van miljarden dingen.
Maar als lage + tot overkomt overloop, dan is dat een probleem.
Zodra we ze niet ondertekend, dan 2 miljard plus 1 miljard 3 miljard.
3 miljard gedeeld door 2 is 1,5 miljard.
Dus zodra ze unsigned zijn, alles is perfect.
En dat is dus ook een probleem als je het schrijven van uw voor loops,
en eigenlijk, het doet waarschijnlijk automatisch.
Het zal eigenlijk alleen maar schreeuwen naar je.
Dus als dit aantal is te groot om in slechts een geheel getal, maar het zou passen in een geheel getal zonder teken,
het zal schreeuwen tegen je, dus dat is waarom je nooit echt lopen in de kwestie.
Je kunt zien dat een index nooit gaat worden negatief,
en dus als je itereren over een array,
je kunt bijna altijd zeggen unsigned int i, maar je hoeft niet echt.
Dingen gaan vrij veel werken net zo goed.
Oke. [Fluistert] Hoe laat is het?
Het laatste wat ik wilde laten zien - en ik zal het gewoon doen echt snel.
Je weet hoe we # hebben gedefinieerd, zodat we kunnen # MAX definiëren als 5 of zo?
Laten we niet doen MAX. # Define gebonden als 200. Dat is wat we eerder deden.
Dat definieert een constante, die net zal worden gekopieerd en geplakt
waar we toevallig schrijven GEBONDEN.
>> Dus we kunnen eigenlijk meer doen met # definieert.
We kunnen # define functies.
Ze zijn niet echt functies, maar we zullen noemen ze functies.
Een voorbeeld zou zoiets MAX (x, y) worden gedefinieerd als (x <y y: x). Oke.
Dus je moet wennen aan ternaire operator syntax,
maar is x kleiner dan y? Terug y, of teruggaan x.
Zodat u kunt zien kunt u deze een aparte functie maken,
en de functie zou kunnen uitzien bool MAX duurt 2 argumenten, terugsturen.
Dit is een van de meest voorkomende die ik zie gebeuren als deze. We noemen ze macro's.
Dit is een macro.
Dit is gewoon de syntax voor.
U kunt een macro om te doen wat je wilt.
Je vaak ziet macro's voor het debuggen printfs en dat soort dingen.
Dus een soort van printf, zijn er speciale constanten in C als underscore LINE onderstrepen,
2 onderstreept underscore LINE,
en er is ook denk ik 2 FUNC onderstrepingstekens. Dat zou het zijn. Zoiets.
Die dingen worden vervangen door de naam van de functie
of het nummer van de lijn die je op.
Vaak, schrijf je debuggen printfs dat hier beneden ik toen kon gewoon schrijven
DEBUG en het zal het regelnummer en de functie die ik toevallig in af te drukken
dat het dat DEBUG statement ondervonden.
En u kunt ook afdrukken andere dingen.
Dus een ding dat je moet oppassen voor is als ik toevallig # define DOUBLE_MAX
als iets als 2 * y en 2 * x.
Dus voor welke reden dan ook, je toevallig te doen dat veel.
Dus maak er een macro.
Dit is eigenlijk gebroken.
Ik zou het door het doen van iets als DOUBLE_MAX (3, 6).
Dus wat moet worden geretourneerd?
[Student] 12.
Ja, moet 12 worden geretourneerd, en 12 wordt geretourneerd.
3 wordt vervangen voor x, wordt 6 vervangen voor y, en keren we terug 2 * 6, dat is 12.
Nu hoe zit dit? Wat moet worden geretourneerd?
[Student] 14. >> Idealiter 14.
Het probleem is dat de manier waarop hash definieert werk, bedenk het is een letterlijke kopiëren en plakken
van vrijwel alles, dus wat dit gaat worden geïnterpreteerd als
is 3 minder dan 1 plus 6, 2 keer 1 plus 6, 2 keer 3.
>> Dus om deze reden je bijna altijd wikkel alles tussen haakjes.
Elke variabele die u bijna altijd wikkelen tussen haakjes.
Er zijn gevallen waarin u niet hoeft te, zoals ik weet dat ik niet hoef te doen hier, dat
omdat er minder dan vrijwel altijd gewoon naar het werk gaan,
hoewel dat misschien niet eens waar.
Als er iets is belachelijk als DOUBLE_MAX (1 == 2),
dan dat gaat om te vervangen door 3 minder dan 1 gelijk is gelijk aan 2,
en dus dan het gaat doen 3 kleiner dan 1, betekent dat gelijk aan 2,
dat is niet wat we willen.
Dus om elke exploitant voorrang problemen te voorkomen,
altijd wikkel tussen haakjes.
Oke. En dat is het, 5:30.
Als u nog vragen heeft over het PSET, laat het ons weten.
Het moet leuk zijn, en de hacker editie is ook veel realistischer
dan de hacker editie van vorig jaar, dus we hopen dat veel van jullie het te proberen.
Vorig jaar was erg overweldigend.
>> [CS50.TV]