[Powered by Google Translate] [Artikel 3 - meer gemaklik]
[Rob Bowden - Harvard Universiteit]
>> [Hierdie is CS50. - CS50.TV]
>> Dus is die eerste vraag is vreemd geformuleer.
GDB kan jy "debug" 'n program, maar, meer spesifiek, wat beteken dit laat jy doen?
Ek sal antwoord dat 'n mens, en ek weet nie wat presies verwag,
so ek vermoed dit is iets langs die lyne van dit kan jou stap vir stap
wandel deur die program, met dit, verandering veranderlikes, al hierdie dinge doen -
basies heeltemal beheer oor die uitvoering van 'n program
en inspekteer enige gegewe deel van die uitvoering van die program.
So daardie funksies laat jy ontfout dinge.
Okay.
Waarom binêre soek vereis dat 'n skikking gesorteer word?
Wie wil om te beantwoord?
[Student] Omdat dit nie werk as dit nie gesorteer. >> Ja. [Lag]
As dit nie gesorteer, dan is dit onmoontlik om dit te verdeel in die helfte
en weet dat alles aan die linkerkant is minder en alles aan die regterkant
is groter as die middelste waarde.
So dit moet gesorteer.
Okay.
Hoekom is borrel soort in die O van n kwadraat?
Is daar iemand wil eers 'n baie vinnige hoë-vlak oorsig te gee van wat borrel soort is?
[Student] Jy het basies gaan deur elke element en jy kyk na die eerste paar elemente.
As hulle uit waar jy ruil, dan moet jy gaan die volgende paar elemente en so aan.
Wanneer jy aan die einde, dan weet jy dat die grootste element is aan die einde geplaas,
sodat jy ignoreer dat 'n mens dan hou jy gaan deur,
en elke keer as jy het een minder element om seker te maak totdat jy geen veranderinge maak. >> Ja.
Dit is genoem borrel soort, want as jy draai die reeks op sy kant so dit is op en af, vertikale,
dan is die groot waardes sal sink na die bodem en die klein waardes sal borrel op die top.
Dit is hoe dit sy naam gekry het.
En ja, jy gaan net deur.
Jy hou gaan deur middel van die skikking, die uitruiling van die groter waarde
die grootste waardes te kry aan die onderkant.
>> Hoekom is dit O van n kwadraat?
Eerstens, nie almal wil om te sê waarom dit is O van n kwadraat?
[Student] Omdat dit gaan vir elke lopie n keer.
Jy kan net seker wees dat jy die grootste element al die pad af,
dan het jy om dit te herhaal soveel elemente. >> Ja.
So in gedagte hou wat die groot O beteken en watter groot Omega beteken.
Die Big O is soos die bogrens op hoe stadig dit kan eintlik loop.
Dus, deur te sê dit is O van n kwadraat, dit is nie O van n of anders dit sal in staat wees om uit te voer
in lineêre tyd, maar dit is O van n blokkies gesny
want dit word begrens deur O van n blokkies gesny.
As dit begrens deur O van n kwadraat, dan is dit is ook begrens deur n blokkies gesny.
So is dit N vierkantig en in die absolute ergste geval kan dit nie beter doen as n kwadraat,
wat is die rede waarom dit is O N kwadraat.
So effense wiskunde te sien hoe dit kom uit n-kwadraat,
as ons vyf dinge in ons lys vir die eerste keer hoeveel swaps ons kan potensieel nodig het om te maak
om dit te kry? Kom ons eintlik net -
Hoeveel swaps gaan ons te maak in die eerste lopie van die soort van borrel deur die skikking?
[Student] n - 1. >> Ja.
>> As daar is 5 elemente, gaan ons 'n te maak - 1.
Dan op die tweede een hoeveel swaps gaan ons maak?
[Student] n - 2. >> Ja.
En die derde is gaan 'n - 3, en dan vir die gerief Ek sal die laaste twee
as dan gaan ons moet 2 swaps en 1 swap te maak.
Ek dink die laaste een mag of mag eintlik nie nodig het om te gebeur.
Is dit 'n ruil? Ek weet nie.
So dit is die totale bedrae van swaps of ten minste vergelykings wat jy moet maak.
Selfs as jy nie ruil nie, jy nog steeds nodig om die waardes te vergelyk.
So daar is n - 1 vergelykings in die eerste lopie deur die skikking.
As jy hierdie dinge herrangskik, laat ons eintlik maak dit ses dinge so dinge stapels mooi,
en dan sal ek doen 3, 2, 1.
Dus net herrangskikking van hierdie somme, ons wil om te sien hoeveel vergelykings maak ons
in die hele algoritme.
So as ons bring hierdie ouens hier,
dan is ons net nog n opsomming egter baie vergelykings daar was.
Maar as ons som hierdie en ons som hierdie en ons som hierdie,
dit is nog steeds dieselfde probleem. Ons het net som daardie bepaalde groepe.
>> So nou het ons n opsomming 3 n. Dit is nie net 3 n.
Dit is altyd gaan wees n / 2 n.
So hier is ons gebeur het 6.
As ons 10 dinge, dan kan ons hierdie groepering vir 5 verskillende pare van dinge doen
en eindig met 'n + n + n + n + n.
Sodat jy altyd gaan n / 2 n te kry, en so dit sal ons skryf dit uit na n kwadraat / 2.
En so selfs al is dit die faktor van 1/2, wat gebeur om in te kom
as gevolg van die feit dat ons deur middel van elke iterasie oor die skikking vergelyk 1 minder
so dit is hoe kry ons die meer as 2, maar dit is nog steeds N kwadraat.
Ons gee nie om oor die konstante faktor van 'n half.
So het 'n baie van die groot O stuff soos hierdie is afhanklik van net soort van doen hierdie soort van wiskunde,
rekenkundige somme en meetkundige reeks dinge te doen,
maar die meeste van hulle in hierdie kursus is redelik eenvoudig.
Okay.
Hoekom is invoeging soort in die Omega van n? Wat beteken omega beteken?
[Twee studente praat in 'n keer - onverstaanbaar] >> Ja.
Omega jy kan dink as die ondergrens.
>> So maak nie saak hoe doeltreffend jou invoeging soort algoritme is,
ongeag van die lys wat in geslaag is, het dit altyd ten minste N dinge te vergelyk
of dit 'om oor n dinge te itereer.
Hoekom is dit?
[Student] Want as die lys is reeds gesorteer is, dan deur die eerste iterasie
jy kan net waarborg dat die heel eerste element is die minste,
en die tweede iterasie jy kan net waarborg die eerste twee
want jy weet nie wat die res van die lys is gesorteer. >> Ja.
As jy slaag in 'n heeltemal gesorteerde lys, op die heel minste wat jy het om te gaan oor al die elemente
om te sien dat niks rondgeskuif moet word.
So wat oor die lys en sê: O, dit is reeds gesorteer,
dit is onmoontlik om te weet dit is gesorteer totdat jy kyk elke element
om te sien dat hulle in gesorteer einde.
So het die laer gebind op die invoeging soort is Omega van n.
Wat is die ergste geval loop die tyd van merge soort,
ergste geval weer groot O?
Dus, in die ergste geval scenario, hoe merge soort loop?
[Student] N log n. >> Ja.
Die vinnigste algemene sorteer-algoritmes is n log n. Jy kan nie beter doen.
>> Daar is spesiale gevalle, en as ons vandag tyd - maar ons waarskynlik won't -
ons kon sien die een wat nie beter is as n log n.
Maar in die algemene geval, kan jy nie beter doen as n log n.
En voeg soort gebeur met die een wat jy moet weet vir hierdie kursus is n log n.
En so sal ons eintlik die uitvoering van dit vandag.
En ten slotte, in nie meer as drie sinne, hoe werk seleksie soort?
Iemand wil om te antwoord, en ek sal jou sinne tel
want as jy gaan oor 3 -
Nie almal onthou seleksie soort?
Seleksie soort is gewoonlik redelik maklik om te onthou net van die naam.
Jy moet net itereer oor die skikking, wat ook al die grootste waarde is of die kleinste -
watter volgorde jy sorteer.
So laat ons sê ons sorteer van die kleinste tot die grootste.
Jy itereer oor die skikking, soek vir alles wat die minimum element is,
kies dit, en dan net ruil dit alles is in die eerste plek.
En dan op die tweede verby die skikking, kyk weer vir die minimum element,
kies, en dan ruil dit met wat in die tweede posisie is.
So ons is net pluk en die keuse van die minimum waardes
en die invoeging van hulle in die voorkant van die skikking totdat dit gesorteer is.
Vrae oor wat?
>> Hierdie onvermydelik verskyn in die vorms wat jy hoef in te vul wanneer jy die indiening van die pset.
Dit is basies die antwoorde op hierdie.
Okay, so nou kodering probleme.
Ek het reeds uitgestuur via e-pos - Het iemand nie die e-pos kry nie? Okay.
Ek het reeds uitgestuur via e-pos die ruimte wat ons gaan gebruik,
en as jy kliek op my naam - so ek dink ek gaan om aan die onderkant te wees
as gevolg van die agteruit r - maar as jy kliek op my naam wat jy sal sien 2 hersienings.
Hersiening 1 gaan ek reeds die kode in Ruimtes gekopieer en geplak
vir die soektog ding wat jy gaan hê om te implementeer.
En Hersiening 2 die soort ding wat ons implementeer daarna sal wees.
So kan jy kliek op my Hersiening 1 en werk van daar af.
En nou wil ons binêre soektog te implementeer.
>> Is daar iemand wil net 'n pseudokode hoë-vlak verduideliking gee
van wat ons gaan hê om te doen vir die soektog? Ja.
[Student] Jy moet net die middel van die skikking en sien as wat jy op soek na
is minder as of meer as dit.
En as dit is minder, gaan jy na die helfte minder,
en as dit meer is, jy gaan aan die helfte van wat meer en jy dit asseblief herhaal totdat jy net een ding.
[Bowden] Ja.
Let daarop dat ons getalle skikking reeds gesorteer,
en so dit beteken dat ons voordeel kan neem van daardie en ons kon eers,
okay, ek is op soek vir die nommer 50.
Sodat ek kan gaan in die middel.
Middel is moeilik om te definieer wanneer dit is 'n ewe getal van die dinge,
maar laat ons net sê ons altyd sal afgeknot na die middel.
So hier is ons het 8 dinge, sodat die middel sou wees 16.
Ek is op soek na 50, so 50 is groter as 16.
So nou kan ek basies my array behandel as hierdie elemente.
Ek kan weggooi alles vanaf 16 oor.
Nou is my array net hierdie 4 elemente, en ek herhaal.
So dan wil ek die middel weer te vind, wat sal wees 42.
42 is minder as 50, so ek kan weggooi hierdie twee elemente.
Dit is my oorblywende verskeidenheid.
Ek gaan om die middel te weer te vind.
Ek dink 50 was 'n slegte voorbeeld, want ek was altyd weg te gooi dinge aan die linkerkant,
maar deur die dieselfde mate as ek is op soek na iets
en dit is minder as die element ek op die oomblik is op soek na,
dan gaan ek alles weg te gooi na regs.
So nou het ons nodig het om te implementeer.
Let daarop dat ons nodig het om te slaag in grootte.
Ons kan ook nie hoef te hard-kode grootte.
So as ons ontslae raak van daardie # define -
Okay.
Hoe kan ek mooi uit te vind wat die grootte van die getalle verskeidenheid tans?
>> Hoeveel elemente in die getalle verskeidenheid?
[Student] Getalle, tussen hakies, lengte?
[Bowden] Dit beteken nie bestaan ​​in C.
Nodig het. Lengte.
Skikkings nie het eienskappe, so daar is geen lengte eiendom van skikkings
wat gee jou net hoe lank dit gebeur om te wees.
[Student] Kyk hoeveel geheue het en verdeel deur hoeveel >> Ja.
So hoe kan ons sien hoeveel geheue het dit? >> [Student] sizeof. >> Ja, sizeof.
Sizeof is die operateur wat gaan om terug te keer die grootte van die getalle skikking.
En wat gaan egter baie heelgetalle is daar keer die grootte van 'n heelgetal
want dit is hoeveel geheue wat dit werklik neem.
So as ek wil hê dat die aantal van die dinge wat in die skikking,
dan gaan ek wil te verdeel deur die grootte van 'n heelgetal.
Okay. So dit laat my in grootte hier.
Hoekom het ek nodig om te slaag in grootte op alle?
Hoekom kan ek nie doen net hier int grootte = sizeof (hooiberg) / sizeof (int)?
Waarom dit nie werk nie?
[Student] Dit is nie 'n globale veranderlike.
[Bowden] Hooi bestaan ​​en ons is wat in getalle as hooiberg,
en dit is 'n soort van 'n voorafskaduwing van wat om te kom. Ja.
[Student] Hooi net is die verwysing na dit, so dit sou terugkeer hoe groot die verwysing is.
Ja.
Ek twyfel in die lesing dat jy die stapel het gesien het nie regtig nie, reg?
Ons het nou net gepraat oor dit.
So die stapel is waar al jou veranderlikes gaan word gestoor.
>> Enige geheue wat vir plaaslike veranderlikes toegeken gaan in die stapel,
en elke funksie kry sy eie ruimte op die stapel, sy eie stapel raam is wat dit genoem word.
So hoof het sy stapel raam, en die binnekant van dit gaan hierdie getalle skikking te bestaan,
en dit gaan van grootte sizeof (getalle) te wees.
Dit gaan om die grootte van getalle gedeel deur die grootte van die elemente te hê,
maar dat alle lewe binne hoof se stapel raam.
Wanneer ons 'n beroep soek, soek kry sy eie stapel raam,
sy eie ruimte al van sy plaaslike veranderlikes te stoor.
Maar hierdie argumente - so hooiberg is nie 'n afskrif van hierdie hele skikking.
Ons slaag nie in die hele verskeidenheid as 'n afskrif in die soektog.
Dit gaan net 'n verwysing na daardie skikking.
So soek kan toegang tot hierdie getalle deur middel van hierdie verwysing.
Dit is nog steeds toegang tot die dinge wat leef binnekant van die hoof se stapel raam,
maar basies, wanneer kry ons verwysings, moet wat binnekort,
dit is wat wysers is.
Pointers is slegs verwysings na dinge, en jy kan gebruik wenke om dinge om toegang te verkry tot
wat in ander dinge stapel rame.
So selfs al getalle plaaslike to main, ons kan nog steeds toegang tot dit deur middel van hierdie wyser.
Maar aangesien dit is net 'n wyser en dit is net 'n verwysing,
sizeof (hooiberg) terugkeer net die grootte van die verwysing self.
Dit kom nie terug nie die grootte van die ding wat dit verwys na.
Dit kom nie terug nie die werklike grootte van getalle.
En so het dit is nie van plan om te werk as ons dit wil.
>> Vrae oor wat?
Pointers gegaan sal word in aansienlik meer gorie detail in die weke om te kom.
En dit is die rede waarom 'n baie van die dinge wat jy sien, die meeste soek dinge of soort dinge,
hulle byna almal nodig om die werklike grootte van die skikking te neem,
want in C, ons het geen idee wat die grootte van die skikking is.
Jy moet met die hand te slaag.
En jy kan met die hand nie slaag in die hele skikking omdat jy net wat in die verwysing
en dit kan nie die grootte van die verwysing.
Okay.
So nou het ons wil uit te voer wat voorheen verduidelik.
Jy kan werk op dit vir 'n minuut,
en jy hoef nie te bekommer oor om alles perfek 100% werk.
Net te skryf aan die helfte pseudokode vir hoe jy dink dit moet werk.
Okay.
Nie nodig om heeltemal klaar is met hierdie nog.
Maar nie almal voel gemaklik met wat hulle het so ver,
soos iets wat ons kan werk met mekaar?
Is daar iemand wil vrywillige werk doen? Of ek sal lukraak kies.
Dit hoef nie te wees reg deur enige maatreël, maar iets wat ons kan verander in 'n werkende toestand.
[Student] Sure. >> Goed.
So kan jy die hersiening red deur te kliek op die klein ikoon Stoor.
Jy Ramya, reg? >> [Student] Ja. >> [Bowden] Goed.
So nou kan ek jou hersiening sien en almal kan trek die hersiening.
En hier het ons - Okay.
So Ramya het met die rekursiewe oplossing, en dit is beslis 'n geldige oplossing.
Daar is twee maniere waarop jy hierdie probleem kan doen.
Jy kan dit doen iteratief of rekursief.
Die meeste probleme wat jy teëkom wat kan rekursief gedoen word, kan ook iteratief gedoen word.
So hier is ons het dit gedoen rekursief.
>> Iemand wil te definieer wat dit beteken om 'n funksie te maak rekursiewe?
[Student] Wanneer jy 'n funksie noem homself
en dan bel self totdat dit kom uit met ware en ware. >> Ja.
'N rekursiewe funksie is net 'n funksie wat self noem.
Daar is drie groot dinge wat 'n rekursiewe funksie moet.
Die eerste is natuurlik, dit self noem.
Die tweede is die basis-geval.
So op 'n sekere punt van die funksie moet om te stop roeping self,
en dit is wat die basis-geval is.
So hier is ons weet dat ons moet ophou, moet ons in ons soektog
wanneer begin gelyk aan einde en ons sal gaan oor wat dit beteken.
Maar uiteindelik, die laaste ding wat belangrik is vir rekursiewe funksies:
die funksies moet op een of ander manier benader die basis-geval.
Hou as jy eintlik nie enigiets afhangende van wanneer jy die tweede rekursiewe oproep,
as jy net letterlik die roeping van die funksie weer met dieselfde argumente
en geen globale veranderlikes het verander of enigiets nie,
jy sal nooit die basis bereik geval, in welke geval dit is erg.
Dit sal 'n oneindige rekursie en 'n stack overflow wees.
Maar hier sien ons dat die update gebeur aangesien ons opdatering + einde / 2 begin,
ons die opdatering van die einde argument hier, ons begin argument opdatering hier.
So ons in alle rekursiewe oproepe word opgedateer iets. Okay.
Wil jy ons om te loop deur jou oplossing? >> Sure.
Ek gebruik SearchHelp so dat elke keer as ek maak hierdie funksie oproep
Ek het die begin van waar ek kyk in die skikking en die einde
van waar ek is op soek na die skikking.
>> By elke stap waar dit sê dit is die middelste element, wat die einde van die begin + / 2,
is dit gelyk aan die wat ons soek?
En as dit is, dan het ons gevind dat dit, en ek dink dit kry geslaag om die vlakke van rekursie.
En as dit is nie waar nie, dan moet ons kyk of daardie middelste waarde van die skikking is te groot,
in welke geval ons kyk na die linker helfte van die skikking deur te gaan van die begin tot die middel-indeks.
En anders kan ons doen die einde 1/2.
[Bowden] Goed.
Dit klink goed.
Okay, so 'n paar dinge, en dit is eintlik 'n baie hoë vlak ding
dat jy sal nooit nodig om vir hierdie kursus te weet, maar dit is waar.
Rekursiewe funksies, jy hoor altyd dat hulle 'n slegte deal
want as jy rekursief noem jouself te veel keer, kry jy stack overflow
want soos ek gesê het, elke funksie kry sy eie stapel raam.
So elke oproep van die rekursiewe funksie kry sy eie stapel raam.
So as jy 1000 rekursiewe oproepe maak, kry jy 1000 stapel rame,
en vinnig lei tot te veel stapel rame en dinge net breek.
So dit is waarom rekursiewe funksies is oor die algemeen sleg.
Maar daar is 'n mooi subset van rekursiewe funksies genoem stert-rekursiewe funksies,
en dit gebeur met 'n voorbeeld van een waar as die samesteller kennisgewings
en dit sal, dink ek - kletteren as jy slaag die O2 vlag
dan sal dit sien dit is 'n stert rekursiewe en maak goeie dinge.
>> Dit sal hergebruik in dieselfde stapel raam oor en oor weer vir elke rekursiewe oproep.
En so aangesien jy met behulp van dieselfde stapel raam, het jy nie hoef te bekommer oor
ooit stapel oorloop, en op dieselfde tyd, soos jy sê,
waar wanneer jy terugkeer waar is, dan is dit om terug te keer al van hierdie stapel rame
en die 10de oproep tot SearchHelp het om terug te keer na die 9de, het om terug te keer na die 8ste.
Sodat nie nodig om te gebeur wanneer funksies stert rekursiewe.
En wat maak hierdie funksie stert rekursiewe kennis dat vir enige gegewe oproep tot searchHelp
die rekursiewe oproep wat dit maak wat dit terugkeer.
So in die eerste oproep te SearchHelp ons óf onmiddellik return false,
onmiddellik return true, of ons maak 'n rekursiewe oproep SearchHelp
waar wat ons terugkeer, is wat dit oproep terugkeer.
En ons kan dit nie doen as ons iets gedoen het soos int x = SearchHelp, terugkeer x * 2,
net 'n paar random verandering.
>> So nou hierdie rekursiewe oproep, hierdie int x = SearchHelp rekursiewe oproep,
is nie langer stert rekursiewe omdat dit eintlik nie om terug te keer
terug na 'n vorige stapel raam so dat vorige oproep na die funksie
kan dan iets te doen met die terugkeer waarde.
Dit is dus nie stert rekursiewe, maar wat ons gehad het voordat mooi stert rekursiewe. Ja.
[Student] Moet nie die tweede basis geval eerste nagegaan word
want daar kan 'n situasie wees waar wanneer jy dit die argument
jy begin = einde, maar dit is die naald waarde.
Die vraag is wat ons kan nie uitgevoer word nie in die geval waar die einde is die naald waarde
of = einde begin, toepaslik, begin = einde
en jy het eintlik nie daardie spesifieke waarde nagegaan nie,
+ einde / 2 begin is net gaan om dieselfde waarde te wees.
Maar ons het reeds teruggekeer vals en ons nooit werklik die waarde nagegaan.
Dus, op die heel minste, in die eerste oproep, indien grootte is 0, dan het ons wil om terug te keer vals.
Maar as die grootte is 1, dan begin is nie van plan om op gelyke einde,
en ons sal ten minste check die een element.
Maar ek dink jy is reg in die sin dat ons kan eindig in 'n geval waar + einde / 2 begin,
begin eindig die dieselfde as die einde van die begin + / 2,
maar ons het nooit eintlik daardie element nagegaan.
>> So as ons eers die middelste element die waarde wat ons is op soek na,
dan kan ons dadelik terug waar.
Anders as hulle gelyk is, dan is daar geen punt in die voortsetting van
aangesien ons net gaan om te werk aan 'n geval waar ons is op 'n enkel-element skikking.
As dit enkele element is nie die een wat ons soek,
dan is alles verkeerd. Ja.
[Student] Die ding is dat sedert die grootte is eintlik groter is as die aantal elemente in die skikking,
daar is reeds 'n offset - >> So sal grootte -
[Student] Sê indien die skikking was grootte 0, dan sal die SearchHelp eintlik gaan hooiberg van 0
op die eerste oproep.
Die skikking het grootte 0, sodat die 0 - >> Ja.
Daar is 'n ander ding wat dit dalk goed wees. Kom ons dink.
So as die skikking het 10 elemente en die middelste een wat ons gaan om te kyk indeks 5,
sodat ons nagaan 5, en laat ons sê dat die waarde is minder.
So ons gooi alles weg van 5 af.
So begin + einde / 2 gaan ons nuwe einde wees nie,
so ja, dit is altyd gaan om te bly buite die einde van die skikking.
As dit is 'n geval as dit was ewe of onewe is, dan sal ons gaan, sê, 4,
maar ons is nog steeds weg te gooi -
So ja, die einde is altyd iets te wees as die werklike einde van die skikking.
Sodat die elemente wat ons fokus op die einde is altyd iets aan die een na.
En so, as begin doen ooit gelyke einde, ons is in 'n verskeidenheid van grootte 0.
>> Die ander ding wat ek kon dink is dat ons begin word opgedateer word begin + einde / 2,
so is dit die geval dat ek die moeilikheid is met, waar begin + einde / 2
is die element wat ons nagaan.
Kom ons sê ons het hierdie 10-element array. Wat ook al.
So begin + einde / 2 gaan om iets soos hierdie een te wees,
en as dit nie is die waarde, sê ons wil werk.
Die waarde is groter, so ons wil om te kyk na die helfte van die skikking.
So, hoe ons begin jy die opdatering van ons opdatering van begin tot nou toe word hierdie element.
Maar dit kan nog steeds werk, of op die heel minste, kan jy doen begin + einde / 2 + 1.
[Student] Jy hoef nie te wees nie + einde begin [onhoorbaar] >> Ja.
Ons het reeds hierdie element nagegaan en weet dit is nie die een wat ons soek.
So ons hoef nie begin te werk om hierdie element te wees.
Ons kan nie net slaan dit en werk begin om hierdie element te wees.
En is daar ooit 'n geval, laat ons sê, dat hierdie einde,
so dan begin sou wees, begin + einde / 2 sou wees,
+ einde begin - Ja, ek dink dit kan eindig in oneindige rekursie.
Kom ons sê dit is net 'n verskeidenheid van grootte 2 of 'n verskeidenheid van grootte 1. Ek dink dit sal werk.
So op die oomblik, begin is dat die element en die einde is 1 verder as dit.
So is die element dat ons gaan om te kyk, is hierdie een,
en dan wanneer ons begin werk, is ons opdatering van begin tot 0 + 1/2,
wat gaan ons weer begin om hierdie element te beëindig.
>> So ons is die kontrolering van dieselfde element oor en oor weer.
So, dit is die geval waar elke rekursiewe oproep moet eintlik iets werk.
So moet ons die einde van die begin + / 2 + 1, of anders om te doen, daar is 'n saak
waar ons eintlik nie die opdatering begin.
Almal sien dat?
Okay.
Is daar iemand vrae oor hierdie oplossing of meer kommentaar?
Okay. Is daar iemand 'n het iteratiewe oplossing wat ons almal kan kyk?
Het ons almal dit doen rekursief?
Of ek ook dink as jy oopgemaak hare, dan is jy dalk oorskryf jou vorige een.
Is dit outomaties te stoor? Ek is nie positief nie.
Is daar iemand iteratiewe het?
Ons kan wandel deur dit saam indien nie.
Die idee is om dieselfde te wees.
Iteratiewe oplossing.
Ons gaan om te wil basies dieselfde idee
waar ons wil die spoor van die die nuwe einde van die skikking en die nuwe begin van die skikking te hou
en doen dit oor en oor.
En as wat ons dop as die begin en die einde ooit sny,
dan het ons nie dit vind en ons kan terugkeer vals.
So, hoe doen ek dit? Enigeen het voorstelle of-kode vir my om te trek?
[Student] Doen 'n while lus. >> Ja.
Jy gaan om te wil 'n lus om te doen.
>> Het jy 'n kode wat ek kon trek, of wat is jy gaan om voor te stel?
[Student] Ek dink nie so nie. >> Alle regte. Dit maak dinge makliker. Wat is jou naam?
[Student] Lucas.
Hersiening 1. Okay.
Laag is wat ons geroep het begin voor.
UP is nie heeltemal wat ons geroep einde voor.
Eintlik, die einde is nou in die skikking. Dit is 'n element wat ons in ag moet neem.
So laag is 0, is die grootte van die skikking - 1,
en nou is ons herhaling, en ons monitor -
Ek dink jy kan wandel deur dit.
Wat was jou denke deur middel van hierdie? Loop ons deur jou kode.
[Student] Sure. Kyk na die hooiberg waarde in die middel en dit vergelyk met die naald.
So as dit is groter as die naald, dan is jy om - oh, eintlik, wat agteruit wees.
Jy gaan wil die regter helfte weg te gooi, en so ja, wat die pad moet wees.
[Bowden] So dit moet minder wees? Is dit wat jy sê? >> [Student] Ja.
[Bowden] Goed. Minder.
So as wat ons is op soek na is kleiner as wat ons wil hê,
dan ja, ons wil die linker helfte weg te gooi,
wat beteken dat ons alles wat ons oorweeg word opgedateer
deur die beweging van laag na die reg van die skikking.
Dit lyk goed.
Ek dink dit het dieselfde probleem wat ons het op die vorige een,
waar as laag is 0 en is 1, dan lae + up / 2 gaan te stel om dieselfde ding weer.
>> En selfs as dit nie die geval is nie, is dit steeds meer doeltreffende op die heel minste
om net weggooi die element wat ons net kyk wat ons weet verkeerd is.
So laag + up / 2 + 1 - >> [student] Dit moet die ander kant wees.
[Bowden] Of moet wees - 1 en die ander een moet wees + 1.
[Student] En daar moet 'n dubbel gelykaanteken. >> [Bowden] Ja.
[Student] Ja.
Okay.
En ten slotte, nou dat ons hierdie + 1 - 1 ding,
is dit - is dit dalk nie - is dit ooit moontlik vir lae om te eindig met 'n waarde groter as up?
Ek dink die enigste manier wat kan gebeur - is dit moontlik? >> [Student] Ek weet nie.
Maar as dit afgeknotte en dan kry minus 1 en dan - >> Ja.
[Student] Dit sou moontlik deurmekaar raak.
Ek dink dit moet goed wees net omdat
want dit laer aan die einde wat hulle wil hê om gelyk te wees, dink ek.
Maar as hulle gelyk is, dan sou ons nie gedoen het die while lus om te begin met
en ons sou net teruggekeer het om die waarde. So ek dink ons ​​is nou goed.
Let daarop dat selfs al is hierdie probleem is nie langer rekursiewe,
dieselfde soort idees is van toepassing waar ons kan sien hoe dit so maklik leen hom
tot 'n rekursiewe oplossing deur die feit dat ons net die opdatering van die indekse oor en oor weer,
maak ons ​​die probleem kleiner en kleiner, is ons fokus op 'n subset van die skikking.
[Student] As laag is 0 en 1 is, sou hulle albei 0 + 1/2, wat sal gaan na 0,
en dan sou 'n mens + 1, sou 'n mens te wees - 1.
[Student] Waar is ons nagaan gelykheid?
Graag as die middelste een is eintlik naald?
Ons ervaar tans nie om dit te doen? Oh!
As it's -
Ja. Ons kan nie net doen die toets hier onder omdat laat ons sê die eerste middel -
[Student] Dit is eintlik nie weggooi nie die gebonde.
So as jy weggooi gebonde, moet jy dit die eerste of wat ookal gaan.
Ah. Ja. >> [Student] Ja.
So nou het ons die een wat ons tans kyk na weggegooi,
wat beteken dat ons moet nou ook
if (hooiberg [(lae + up) / 2] == naald), dan kan ons terug waar.
En of ek anders of net as dit beteken letterlik die dieselfde ding
want dit sou teruggekeer het waar.
So ek sal anders sit as nie, maar dit maak nie saak.
>> So anders as hierdie, anders, en dit is 'n algemene ding wat ek doen
waar selfs al is dit die geval waar alles is goed hier,
soos lae kan nooit groter wees as op, dit is nie die moeite werd redenasie oor die vraag of dit waar is.
So jy kan net sowel sê terwyl lae is minder as of gelyk aan
of terwyl lae is minder as
so as wat hulle ooit gelyk of lae gebeur om te slaag,
dan kan ons breek uit van die lus.
Vrae, kommentaar?
Okay. Dit lyk goed.
Nou wil ons soort te doen.
As ons gaan na my tweede hersiening, sien ons hierdie getalle,
maar nou is hulle nie meer in gesorteer einde.
En ons wil soort uit te voer met behulp van 'n algoritme in O van n log n.
So watter algoritme dink jy moet ons hier te implementeer? >> [Student] Merge soort.
[Bowden] Ja. Merge soort is O (n log n), so dit is wat ons gaan doen.
En die probleem is redelik soortgelyk gaan wees,
waar dit leen homself maklik tot 'n rekursiewe oplossing.
Ons kan ook kom met 'n iteratiewe oplossing as ons wil,
maar rekursie sal makliker wees om hier en ons moet doen rekursie.
Ek dink ons ​​sal wandel deur merge soort,
alhoewel daar 'n pragtige video op merge soort reeds. [Lag]
So saamsmelt soort daar is - ek mors so baie van hierdie vraestel.
O, daar is net een links.
So saam te smelt.
O, 1, 3, 5.
Okay.
Merge neem twee afsonderlike skikkings.
Individueel dié twee skikkings is albei gesorteer.
So hierdie skikking, 1, 3, 5, gesorteer. Hierdie skikking, 0, 2, 4, gesorteer.
Nou wat merge moet doen is kombineer hulle in 'n skikking wat op sigself gesorteer.
Daarom wil ons 'n verskeidenheid van grootte 6 wat gaan om hierdie elemente te binnekant van dit
gesorteer einde.
>> En so sal ons kan neem voordeel van die feit dat hierdie twee skikkings word gesorteer
om dit te doen in lineêre tyd,
lineêre tyd betekenis as hierdie verskeidenheid is grootte x en hierdie grootte y,
dan is die totale algoritme O (x + y) moet wees. Okay.
So voorstelle.
[Student] Kan ons begin van die linkerkant?
Sodat jy die 0 eers sit en dan die 1 sit en dan is jy hier by die 2.
So dit is soort van soos jy het 'n blad wat na regs beweeg. >> [Bowden] Ja.
Vir beide van hierdie skikkings as ons net fokus op die linker element.
Omdat beide skikkings word gesorteer, ons weet dat hierdie 2 elemente
is die kleinste elemente in óf skikking.
So dit beteken dat 1 van die 2 elemente moet die kleinste element in ons saamgesmelte skikking.
Dit gebeur net so dat die kleinste is die een aan die regterkant van hierdie tyd.
So neem ons 0, plaas dit op die linkerkant, want 0 is minder as 1,
so neem 0, plaas dit in ons eerste posisie, en dan ons hierdie
nou fokus op die eerste element.
En nou is ons herhaal.
So nou het ons vergelyk 2 en 1. 1 is kleiner, dus sal ons voeg 1.
Ons werk hierdie wyser om te verwys na hierdie man.
Nou het ons dit weer doen, so 2. Dit sal werk, vergelyk hierdie 2, 3.
Hierdie updates, dan 4 en 5.
So dit is merge.
>> Dit moet redelik voor die hand liggend dat dit is 'n lineêre tyd want ons gaan net weer oor elke element.
En dit is die grootste stap na die implementering van merge soort dit doen.
En dit is nie so moeilik nie.
'N paar dinge om oor bekommerd te wees nie, is Kom ons sê ons 1, 2, 3, 4, 5, 6 is die samesmelting.
In hierdie geval het ons beland in die scenario waar hierdie een gaan kleiner wees,
dan werk ons ​​hierdie pointer, hierdie een gaan om kleiner te wees, werk,
hierdie een is kleiner, en nou het jy om te erken
wanneer jy eintlik het hardloop uit van die elemente met mekaar te vergelyk.
Aangesien ons reeds gebruik om hierdie hele skikking,
alles in die skikking is nou net hier ingevoeg in.
So as ons ooit hardloop in die punt waar een van ons skikkings reeds heeltemal saamgesmelt,
dan het ons net al die elemente van die ander skikking en plaas dit in die einde van die skikking.
Sodat ons kan voeg net 4, 5, 6. Okay.
Dit is een ding om te kyk uit vir.
Die uitvoering van die stap 1 moet wees.
Merge dan sorteer gebaseer op die, dit is 2 stappe, 2 dom stappe.
Kom ons gee hierdie verskeidenheid.
So saamsmelt soort, stap 1 is om die skikking te rekursief te breek in twee helftes.
Hierdie skikking so verdeel in twee helftes.
Ons het nou 4, 15, 16, 50 en 8, 23, 42, 108.
En nou het ons doen dit weer en ons verdeel in twee helftes.
Ek sal doen dit net op hierdie kant.
So 4, 15 en 16, 50.
Ons sal dieselfde ding doen hier.
En nou het ons verdeel dit weer in die helfte.
En ons het 4, 15, 16, 50.
So dit is ons basis geval.
Sodra die skikkings van grootte 1, dan moet ons ophou met die splitsing in twee helftes.
>> Wat doen ons nou met hierdie?
Ons eindig dit ook in 8, 23, 42, en 108 sal breek.
So nou dat ons op hierdie punt, nou stap twee van merge soort net samesmelting pare aan die lyste.
So ons wil dit om saam te smelt. Ons roep saam te smelt.
Ons weet merge hierdie in gesorteer orde sal terugkeer.
4, 15.
Nou wil ons dit om saam te smelt, en dit sal 'n lys met dié in gesorteer orde terugkeer,
16, 50.
Ons saamsmelt diegene - Ek kan nie skryf nie - 8, 23 en 42, 108.
So ons het saamgesmelte pare weer.
Nou het ons net weer saam te smelt.
Let daarop dat elk van hierdie lyste word gesorteer op sigself,
en dan kan ons net saamsmelt hierdie lyste om 'n lys te kry van grootte 4 wat is gesorteer
en hierdie twee lyste saam te smelt om 'n lys te kry van grootte 4 wat is gesorteer.
En laastens, kan ons saam te smelt die twee lyste van grootte 4 'n lys te kry van grootte 8 wat is gesorteer.
So om te sien dat dit is 'n algehele n log n, het ons reeds gesien dat merge is lineêre,
sodat wanneer ons te doen het met die samesmelting hierdie, so soos die totale koste van die merge
vir hierdie twee lyste is net 2 omdat -
Of goed, dit is O van n, maar n hier is net hierdie 2 elemente, so dit is 2.
En dit 2 sal wees 2 en die 2 sal wees 2 en die 2 sal wees 2,
so oor al die smelt wat ons nodig het om te doen, het ons uiteindelik doen n.
Soos 2 + 2 + 2 + 2 is 8, wat 'n
sodat die koste van die samesmelting in hierdie stel is n.
En dan dieselfde ding hier.
Ons sal hulle saamsmelt 2, dan is hierdie 2 en individueel hierdie kombinering sal vier operasies,
hierdie merge sal vier operasies, maar weer, tussen al hierdie,
ons uiteindelik samesmelting n totale dinge, en so hierdie stap neem n.
En so elke vlak neem n elemente saamgevoeg.
>> En hoeveel vlakke is daar?
Op elke vlak, ons verskeidenheid groei deur die grootte 2.
Hier om ons skikkings van grootte 1, hier is hulle van grootte 2, hulle is hier van grootte 4,
en uiteindelik, hulle is van grootte 8.
So aangesien dit verdubbel, is daar 'n totaal van log n van hierdie vlakke gaan wees.
So met die log n vlakke, elke individuele vlak wat 'n totale bedrywighede,
ons kry 'n log n algoritme.
Vrae?
Het mense reeds vordering gemaak oor hoe om dit te implementeer?
Is iemand reeds in 'n staat waar ek kan net trek hulle kode?
Ek kan gee 'n minuut.
Hierdie een gaan meer.
Ek raai terugkeer -
Jy hoef nie rekursie te doen vir merge
omdat rekursie vir merge te doen, jy gaan te hê om 'n klomp van verskillende groottes te slaag.
Jy kan, maar dit is irriterende.
Maar rekursie vir soort self is redelik maklik.
Jy moet net letterlik bel soort op die linker helfte, sorteer op die regter helfte. Okay.
Enigiemand enigiets wat ek nog kan trek?
Of anders sal ek gee 'n minuut.
Okay.
Iemand het iets wat ons kan werk met?
Of anders het ons sal net werk met hierdie en dan van daar af uit te brei.
>> Iemand het meer as dit nie, dat ek kan trek?
[Student] Ja. Jy kan trek op my. >> Alle regte.
Ja!
[Student] Daar was 'n baie voorwaardes. >> O, skiet. Kan jy -
[Student] Ek het om dit te red. >> Ja.
So ons het die kombinering doen afsonderlik.
Ag, maar dit is nie so sleg nie.
Okay.
So soort is self bel net mergeSortHelp.
Verduidelik vir ons wat mergeSortHelp doen.
[Studente] MergeSortHelp mooi nie veel die twee hoof stappe,
wat elke helfte van die skikking te sorteer en dan albei van hulle om saam te smelt.
[Bowden] Okay, so gee my 'n tweede.
Ek dink dat dit - >> [student] Ek moet -
Ja. Ek mis iets.
In merge, ek besef dat ek nodig het om te skep 'n nuwe skikking
want ek kon nie dit doen in die plek. >> Ja. Jy kan nie. Korrigeer.
[Student] So het ek 'n nuwe skikking.
Ek het vergeet om by die einde van saamsmelt weer verander.
Okay. Ons moet 'n nuwe skikking.
In merge soort, dit is amper altyd waar nie.
Deel van die koste van 'n beter algoritme tyd-wyse
is byna altyd nodig om 'n bietjie meer geheue te gebruik.
So hier is, maak nie saak hoe jy dit doen saamsmelt soort,
jy sou onvermydelik 'n paar ekstra geheue te gebruik.
Hy of sy het 'n nuwe skikking.
En dan sê jy aan die einde moet ons net nuwe skikking in die oorspronklike skikking te kopieer.
[Student] Ek dink so, ja.
Ek weet nie of dit werk in terme van tel deur verwysing of wat ook al -
Ja, sal dit werk. >> [Student] Goed.
Het jy probeer om hierdie? >> [Student] Nee, nog nie. >> Goed.
Probeer om dit, en dan sal ek praat oor dit vir 'n tweede.
[Student] Ek nodig het om al die funksies wat prototipes en alles te hê, al is, reg?
Die funksie prototipes. O, jy bedoel soos - Ja.
Sorteer roep mergeSortHelp.
>> So ten einde vir die soort mergeSortHelp te roep, moet óf mergeSortHelp gewees het gedefinieer
voor soort of moet ons net die prototipe. Net kopieer en plak dat.
En insgelyks, is mergeSortHelp roep saamsmelt,
maar merge nie is nog nie gedefinieer, sodat ons kan net laat mergeSortHelp weet
dat dit is wat saamsmelt gaan lyk, en dit is dit.
So mergeSortHelp.
Ons het 'n probleem hier waar ons het geen basis geval.
MergeSortHelp rekursiewe, so 'n rekursiewe funksie
gaan om 'n soort van die basis-geval nodig om te weet wanneer om te stop rekursief roep self.
Wat is ons basis geval gaan hier? Ja.
[Student] As die grootte is 1? >> [Bowden] Ja.
Dus, net soos ons gesien het net daar, het ons gestop splitsing skikkings
sodra ons het in skikkings van grootte 1, wat onvermydelik is gesorteer self.
So as grootte is gelyk aan 1, weet ons die skikking reeds gesorteer is,
sodat ons kan net terugkeer.
>> Let daarop dat is nietig, sodat ons terugkeer nie iets besonder, het ons net terug te keer.
Okay. So dit is ons basis geval.
Ek dink ons ​​basis geval ook kan wees as ons gebeur word die samesmelting van 'n verskeidenheid van grootte 0,
ons waarskynlik wil om te stop op 'n sekere punt,
sodat ons kan net sê grootte minder as 2 of minder as of gelyk aan 1
sodat dit sal werk vir enige skikking nou.
Okay.
So dit is ons basis geval.
Nou wil jy ons om te wandel deur merge?
Wat doen al hierdie gevalle beteken?
Hier, ons is net doen dieselfde idee, die -
[Student] Ek moet verby grootte met al die mergeSortHelp oproepe.
Ek bygevoeg grootte as 'n addisionele primêre en dit is nie daar nie, soos grootte / 2.
[Bowden] O, grootte / 2, grootte / 2. >> [Student] Ja, en ook in die bogenoemde funksie sowel.
[Bowden] hier? >> [Student] Net grootte. >> [Bowden] Oh. Grootte, grootte? >> [Student] Ja.
[Bowden] Goed.
Laat my dink vir 'n tweede.
Loop ons nie in 'n probleem?
Ons is altyd op die behandeling van die linkerkant as 0. >> [Student] No
Wat verkeerd is. Jammer. Dit moet begin. Ja.
[Bowden] Goed. Ek hou van wat 'n beter.
En einde. Okay.
So nou wil jy ons om te wandel deur merge? >> [Student] Goed.
Ek net loop deur hierdie nuwe skikking wat ek gemaak het.
Sy grootte is die grootte van die gedeelte van die skikking wat ons wil word gesorteer
en probeer om die element te vind dat ek moet sit in die nuwe skikking stap.
So om dit te doen, in die eerste ek nagaan indien die linker helfte van die skikking steeds meer elemente te hê,
en as dit nie, dan gaan jy af na wat anders toestand, wat net sê
okay, moet dit in die regte array, en ons sal in die huidige indeks van newArray.
>> En dan anders, ek nagaan of die regterkant van die skikking is ook klaar,
in welke geval ek net sit aan die linkerkant.
Dit kan eintlik nie nodig nie. Ek is nie seker nie.
Maar in elk geval, die ander twee tjek watter een van die twee is kleiner in die linker-of die regterkant.
En ook in elke geval, ek verhoog van wat ookal place holder Ek inkrementeer.
[Bowden] Goed.
Dit lyk goed.
Is daar iemand het kommentaar of kommer of vrae?
Toe is die vier gevalle dat ons dinge te bring in net '- of dit lyk soos vyf -
maar ons het om te oorweeg of die linker-skikking het hardloop uit van die dinge wat ons nodig het om saam te smelt,
of die regte skikking het hardloop uit van die dinge wat ons nodig het om saam te smelt -
Ek wys niks.
So of die linker-skikking van die dinge loop uit of die regte array het hardloop uit van die dinge.
Dit is twee gevalle.
Ons moet ook die triviale geval van of die linker ding is minder as die regte ding.
Dan wil ons die linker ding om te kies.
Dit is die gevalle.
So dit was reg nie, maar dit is dit.
Array verlaat. Dit is 1, 2, 3. Okay. So ja, wat is die vier dinge wat ons dalk wil om dit te doen.
En ons sal nie gaan oor 'n iteratiewe oplossing.
Ek sou nie aanbeveel -
Merge soort is 'n voorbeeld van 'n funksie wat beide nie die stert rekursiewe,
dit is nie maklik om te maak dit stert rekursiewe,
maar ook dit is nie baie maklik om te maak dit iteratiewe.
Dit is baie maklik.
Hierdie implementering van merge soort,
saam te smelt, maak nie saak wat jy doen nie, jy gaan saamsmelt te bou.
>> So soort wat gebou is op die top van merge saamsmelt rekursief is net hierdie drie lyne.
Iteratief, dit is meer irriterende en meer moeilik om oor na te dink.
Maar let op dat dit nie stert rekursiewe sedert mergeSortHelp - wanneer dit oproepe self -
dit moet nog dinge om te doen nadat hierdie rekursiewe oproep opbrengste.
So hierdie stapel moet voortgaan om te bestaan, selfs nadat noem hierdie.
En dan wanneer jy noem dit, moet die stapel raam voortgaan om te bestaan
want selfs na daardie oproep, het ons nog nodig het om saam te smelt.
En dit is triviaal hierdie stert rekursiewe te maak.
Vrae?
Alles reg.
So gaan terug om te sorteer - oh, daar is twee dinge wat ek wil om te wys. Okay.
Terug te gaan na soort, sal ons doen dit vinnig.
Of search. Sorteer? Sorteer. Ja.
Terug te gaan na die begin van die soort.
Ons wil 'n algoritme wat die skikking vorme met behulp van 'n algoritme te skep
O van n.
So, hoe is dit moontlik? Is daar iemand enige soort van -
Ek terloops voor op -
As ons oor te verbeter van n log n O van n,
ons verbeter ons algoritme tyd-wyse,
wat beteken wat gaan ons nodig het om te doen om te vergoed vir wat?
[Student] Space. >> Ja. Ons gaan om te word deur gebruik te maak van meer ruimte.
En selfs nie net meer ruimte, dit is eksponensieel meer ruimte.
So ek dink hierdie tipe van die algoritme is pseudo iets pseudo polynom -
pseudo - Ek kan nie onthou nie. Pseudo iets.
Maar dit is omdat ons soveel ruimte nodig het om te gebruik
dat dit haalbaar is, maar nie realisties.
>> En hoe kry ons dit?
Ons dit kan bereik as ons waarborg dat 'n bepaalde element in die skikking
is onder 'n sekere grootte.
So laat ons net sê dat die grootte is 200,
'n element in 'n skikking is onder grootte 200.
En dit is eintlik baie realisties.
Kan jy baie maklik 'n skikking wat jy weet alles wat daarin
gaan minder wees as sommige nommer.
Soos as jy het 'n paar absoluut massiewe vektor of iets
maar jy weet alles gaan wees tussen 0 en 5,
dan is dit gaan te wees beduidend vinniger om dit te doen.
En die gebonde op enige van die elemente is 5,
sodat dit gebonde, dit is hoeveel geheue wat jy gaan word met behulp van.
Sodat die gebonde is 200.
In teorie is daar altyd 'n gebonde sedert kan slegs 'n heelgetal wees tot 4 miljard,
maar dit is onrealisties want dan sou ons gebruik word om ruimte
op die einde van 4 miljard. So dit is onrealisties.
Maar hier sal ons sê ons gebonde is 200.
Die truuk om dit te doen in die O van n is dat ons nog 'n skikking met die naam tellings van grootte gebind.
So dit is eintlik 'n kortpad vir - Ek weet eintlik nie of kletteren doen dit.
Maar in die GCC op die heel minste, ek veronderstelling kletteren doen dit ook -
dit sal net die hele verskeidenheid inisialiseer 0e te wees.
So as ek nie wil hê om dit te doen, dan kon ek afsonderlik doen vir (int i = 0;
i <gebind; i + +) en tel [i] = 0;
So nou alles geïnisialiseer tot 0.
Ek oor my array itereer
en wat ek doen is ek die getal van elke is toe - Kom ons gaan hier neer.
Ons het 4, 15, 16, 50, 8, 23, 42, 108.
Wat ek toe, is die aantal voorkomste van elk van hierdie elemente.
Kom ons eintlik nog 'n paar byvoeg hier met 'n paar herhalings.
Dus is die waarde wat ons hier het, is die waarde van daardie gaan wees array [i].
So val kan wees 4 of 8 of wat ook al.
En nou is ek tel hoeveel van daardie waarde wat ek gesien het,
so tel [val] + +;
Nadat dit gedoen is, is tellings gaan om iets te lyk soos 0001.
Kom ons doen tellings [val] - gebonde + 1.
>> Nou is dit net vir die feit dat ons vanaf 0 tot verantwoording.
So as 200 gaan ons grootste getal wees,
dan 0 tot 200 201 dinge.
So tel, sal dit lyk soos 00.001, want ons het 'n 4.
Dan sal ons 0001 waar ons sal moet 'n 1 in die 8ste indeks van die telling.
Ons sal 'n 2 in die 23ste indeks van die telling.
Ons sal 'n 2 in die 42ste-indeks van die telling.
Sodat ons kan reken.
So num_of_item = tellings [i].
En so, as num_of_item is 2, wat beteken dat ons wil te voeg 2 van die aantal i
in ons gesorteer skikking.
Sodat ons nodig het om tred te hou van hoe ver ons is in die skikking.
So index = 0.
Array - ek sal net dit skryf.
Tel -
array [index + +] = i;
Is dit wat ek wil? Ek dink dit is wat ek wil hê.
Ja, dit lyk goed. Okay.
So het almal verstaan ​​wat die doel van my tel array is?
Dit is die tel van die aantal voorkomste van elk van hierdie getalle.
Dan is ek iterating oor wat tel skikking,
en die met posisie in die tellings skikking
is die aantal i is wat moet verskyn in my gesorteer array.
Dit is die rede waarom aanklagte van 4 gaan wees 1
en tellings van 8 gaan wees 1, tellings van 23 gaan wees 2.
So dit is hoe baie van hulle ek wil in te voeg in my gesorteer skikking.
Toe het ek net doen.
Ek invoeging num_of_item i in my gesorteer verskeidenheid.
>> Vrae?
En so weer, dit is lineêr tyd sedert ons is net iterating oor hierdie een keer,
maar dit is ook lineêre in wat hierdie getal gebeur om te wees,
en so is dit hang swaar op wat jou gebonde is.
Met 'n gebonde 200, dit is nie so sleg nie.
As jou gebonde gaan wees 10.000, dan is dit 'n bietjie erger,
maar as jou gebonde gaan wees 4 miljard, wat is heeltemal onrealisties
en hierdie skikking gaan hê om van grootte 4 miljard, wat is onrealisties.
So dit is dit. Vrae?
[Onhoorbaar student reaksie] >> Goed.
Ek het besef 'n ander ding, wanneer ons gaan deur.
Ek dink die probleem was in Lucas se en waarskynlik elke enkele een wat ons gesien het.
Ek het heeltemal vergeet.
Die enigste ding wat ek wou om kommentaar te lewer op, is dat wanneer jy te doen het met dinge soos indekse,
jy nooit regtig sien dit wanneer jy die skryf van 'n for-lus,
maar tegnies, wanneer jy te doen het met hierdie indekse,
jy moet pretty much altyd hanteer unsigned heelgetalle.
Die rede hiervoor is wanneer jy met onderteken heelgetalle,
so as jy 2 onderteken heelgetalle en jy voeg hulle saam
en hulle uiteindelik te groot is, dan beland jy met 'n negatiewe getal.
So dit is wat integriteit overflow is.
>> As ek voeg 2 miljard en 1 miljard, Ek eindig met 'n negatiewe 1 miljard.
Dit is hoe heelgetalle werk op rekenaars.
Dus is die probleem met die gebruik van -
Dit is goed behalwe as lae gebeur met 2 miljard en gebeur met 1 miljard,
dan is dit gaan om negatief te wees 1 miljard en dan gaan ons te verdeel deur 2
en eindig met 'n negatiewe 500 miljoen.
So dit is net 'n probleem as jy toevallig op soek deur middel van 'n skikking
van miljarde van dinge.
Maar as lae + up laat aanstroom het gebeur, dan is dit 'n probleem.
So gou as wat ons maak hulle unsigned, dan 2 miljard plus 1 miljard is 3 miljard.
3 miljard gedeel deur 2 is 1,5 miljard.
So gou as wat hulle is unsigned, alles is perfek.
En so het dit is ook 'n probleem wanneer jy skryf jou vir loops,
en eintlik is dit nie waarskynlik is dit outomaties.
Dit sal net eintlik skreeu op jou.
So as hierdie nommer is te groot om in net 'n heelgetal, maar dit sou pas in 'n ongetekende heelgetal,
dit sal gil op jou, so dis hoekom jy nooit werklik loop in die kwessie.
Jy kan sien dat 'n indeks nooit gaan om negatief te wees,
en so wanneer jy iterating oor 'n skikking,
kan jy byna altyd sê unsigned int i, maar jy het nie regtig aan.
Dinge gaan pretty much werk net so goed.
Okay. [Fluister] Hoe laat is dit?
Die laaste ding wat ek wou om te wys - en ek sal doen dit net regtig vinnig.
Jy weet hoe ons # definieer sodat ons kan # MAX definieer as 5 of iets?
Laat ons nie doen MAX. # Define gebind as 200. Dit is wat ons gedoen het voor.
Wat definieer 'n konstante, wat net gaan om te gekopieer en geplak word
waar ons gebeur te skryf GEBONDE.
>> Sodat ons kan eintlik meer doen met # definieer.
Ons kan definieer # funksies.
Hulle is nie regtig funksies, maar ons sal hulle noem funksies.
'N voorbeeld sou wees iets soos MAX (x, y) word gedefinieer as (x <y y: x). Okay.
So jy moet gewoond raak aan drieledige operateur sintaksis,
maar is x minder as y? Terug y, anders x terugkeer.
Sodat jy kan sien jy kan hierdie 'n aparte funksie,
en die funksie kan wees soos Bool MAX 2 argumente, terugkeer.
Dit is een van die mees algemene wat ek sien soos hierdie. Ons noem hulle macros.
Dit is 'n makro.
Dit is net die sintaksis vir dit.
Jy kan skryf 'n makro om te doen wat jy wil.
Sien jy gereeld macros vir die ontfouting van printfs en stuff.
So 'n tipe van printf, is daar spesiale konstantes in C soos onderstreping LINE onderstreping,
2 beklemtoon LINE onderstreep,
en daar is ook Ek dink 2 beklemtoon funk. Wat dit kan wees nie. Iets soos dit.
Hierdie dinge sal vervang word met die naam van die funksie
of die getal van die lyn wat jy op.
Jy skryf gereeld, die ontfouting van printfs dat hier af Ek kon net skryf dan
Ontfout en dit sal die lyn en die funksie wat ek toevallig in print
dat dit teëgekom dat DEBUG verklaring.
En jy kan ook ander dinge druk.
Sodat die een ding wat jy moet kyk uit vir as ek toevallig om te definieer # DOUBLE_MAX
as iets soos 2 * y en 2 * x.
Dus, vir watter rede ookal, jy gebeur dat 'n baie om te doen.
So maak dit 'n makro.
Dit is eintlik gebreek.
Ek noem dit deur om iets te doen soos DOUBLE_MAX (3, 6).
So, wat moet teruggestuur word?
[Student] 12.
Ja, moet 12 teruggestuur word, en 12 terugbesorg word.
3 kry vir x vervang, kry 6 vervang vir y, en ons terugkeer 2 * 6, wat is 12.
Nou wat oor hierdie? Wat moet teruggestuur word?
[Student] 14. >> Ideaal, 14.
Die probleem is dat hoe hash definieer werk, onthou dit is 'n letterlike kopieer en plak
pretty much alles, so wat hierdie gaan vertolk word as
is 3 minder as 1 plus 6, 2 keer 1 plus 6, 2 keer 3.
>> Dus, om hierdie rede wat jy byna altyd draai alles in hakies.
Enige veranderlike wat jy byna altyd draai in hakies.
Daar is gevalle waar jy nie hoef te, soos ek weet dat ek nie nodig het nie wat om hier te doen nie
omdat minder as is pretty much altyd net gaan om te werk,
alhoewel dit kan selfs nie waar wees nie.
As daar iets is belaglik soos DOUBLE_MAX (1 == 2),
dan wat gaan om te vervang met 3 minder as 1 is gelyk aan gelyk is aan 2,
en so dan is dit gaan te doen 3 minder as 1, dat gelyke 2,
wat is nie wat ons wil hê.
Dus, ten einde enige operateur voorrang probleme te voorkom,
draai altyd in hakies.
Okay. En dit is dit, 05:30.
As jy enige vrae oor die pset, laat ons weet.
Dit moet pret wees, en die hacker uitgawe is ook baie meer realistiese
as die hacker uitgawe van verlede jaar se, so ons hoop dat baie van julle probeer om dit.
Verlede jaar was baie oorweldigend.
>> [CS50.TV]