[Powered by Google Translate] [Pjesa 3 - më të rehatshme]
[Rob Bowden - Universiteti i Harvardit]
>> [Kjo është CS50. - CS50.TV]
>> Pra, pyetja e parë është e formuluara cuditerisht.
Gdb ju lejon "debug" një program, por, më konkretisht, çfarë e bën atë të ju lejojnë të bëni?
Unë do të përgjigjem se një, dhe unë nuk e di se çfarë pritet saktësisht,
kështu që unë jam guessing kjo është diçka që përgjatë vijave të saj ju lejon të hap pas hapi
ecin përmes programit, të ndërveprojnë me të, variablave ndryshim, bëni të gjitha këto gjëra -
në thelb plotësisht të kontrolluar ekzekutimin e një programi
dhe të inspektojë çdo pjesë të caktuar të ekzekutimit të programit.
Pra, këto karakteristika të ju lejojnë të korrigjoj gjërat.
Rregull.
Pse nuk kërkoni binare kërkojnë që një grup të ndahen?
Kush dëshiron të përgjigjet se?
[Student] Për shkak se ajo nuk punon në qoftë se ajo nuk është e renditura. Po >>. [Qeshura]
Nëse kjo nuk është e renditura, atëherë kjo është e pamundur për të ndarë atë në gjysmën e
dhe e di se çdo gjë në të majtë është më pak dhe çdo gjë në të djathtë
është më e madhe se vlera e mesme.
Pra, ajo duhet të zgjidhet.
Rregull.
Pse është lloj flluskë në O n katror?
A ka dikush të parë duan të japin një pasqyrë shumë të shpejtë të nivelit të lartë të asaj lloj flluskë është?
[Student] Ju në thelb të shkoni nëpër çdo element dhe ju shikoni elementet e para.
Nëse ata janë nga ku bie në ujdi ato, atëherë ju shikoni elementet e ardhshme dhe kështu me radhë.
Kur të keni arritur në fund, atëherë ju e dini se elementi më i madh është vendosur në fund,
kështu që ju injorojnë se një, atëherë ju mbani në duke kaluar,
dhe çdo herë që ju duhet të kontrolloni një element pak derisa ju të bëni asnjë ndryshim. Po >>.
Ajo që quhet lloj flluskë sepse në qoftë se ju rrokullisje array në anën e saj kështu që është lart dhe poshtë, vertikale,
atëherë vlerat e mëdha do të fundoset në fund dhe vlerat e vogla do të flluskë deri në krye.
Kjo është se si ajo mori emrin e tij.
Dhe vërtet, ju thjesht të shkojnë përmes.
Ju mbani duke shkuar nëpër rrjet, shkëmbejnë vlerën më të madhe
për të marrë vlerat më të mëdha në fund.
>> Pse është ajo O n katror?
Së pari, nuk dua të them dikush se pse kjo është O n katror?
[Student] Sepse per cdo afat herë ajo shkon n.
Ju vetëm mund të jetë i sigurt që ju keni marrë elementi më i madh të gjithë rrugën poshtë,
atëherë ju duhet të përsëris se për aq shumë elemente. Po >>.
Pra, mbani në mend se çfarë do të thotë i madh o dhe çfarë do të thotë të mëdha Omega.
O i madh është si pjesën e sipërme të detyruar se si i ngadalshëm kjo në fakt mund të kandidojë.
Pra, duke thënë: Ø e n katror, ​​ajo nuk është O n apo tjetër ajo do të jetë në gjendje për të kandiduar
në kohë lineare, por kjo është e n o cubed
sepse ajo kufizohet nga O n cubed.
Nëse është e kufizohet nga O n katror, ​​atëherë ajo kufizohet edhe nga n cubed.
Pra, kjo është n katror, ​​dhe në rastin më të keq absolute ajo nuk mund ta bëjë më mirë se n katror,
cila është pse ajo është O i N katror.
Pra, për të parë se si matematikë të vogël del të jetë n katror,
në qoftë se ne kemi pesë gjëra në listën tonë, për herë të parë se sa këmbime mund të kemi potencialisht duhet të bëjnë
në mënyrë që të marrë këtë? Le të vërtetë vetëm -
Sa këmbime jemi ne do të duhet të bëjë në afat të parë të lloj flluskë nëpër rrjet?
[Student] n - 1. Po >>.
>> Nëse ka 5 elemente, ne do të duhet të bëjnë n - 1.
Pastaj në një të dytë sa këmbime jemi ne do të duhet të bëjë?
[Studenti n] - 2. Po >>.
Dhe e treta do të jetë n - 3, dhe pastaj për komoditetin që unë do të shkruaj dy vitet e fundit
si atëherë ne do të duhet të bëjë këmbime 2 dhe 1 Swap.
I guess i fundit mund ose nuk mund të vërtetë duhet të ndodhë.
A është kjo një shkëmbim? Nuk e di.
Pra, këto janë shumat totale të këmbime ose së paku krahasimet që ju keni për të bërë.
Edhe nëse ju nuk keni të bie në ujdi, ju ende nevojë për të krahasuar vlerat.
Pra, ka n - 1 krahasime në afat parë nëpërmjet vektorit.
Në qoftë se ju korrigjoj këto gjëra, le të bëjë në fakt atë gjashtë gjëra kaq gjëra të lart grumbulloj bukur,
dhe pastaj unë do të bëj 3, 2, 1.
Pra, vetëm këto shuma rearranging, ne duam të shohim se sa kemi bërë krahasime
në algorithm tërë.
Pra, nëse kemi sjellë këta njerëz këtu poshtë,
atëherë ne jemi ende vetëm përmbledhje krahasime megjithatë shumë atje ishin.
Por në qoftë se ne të përmbledhur këto dhe të përmbledhur këto dhe kemi përmbledhur këto,
është ende të njëjtin problem. Ne vetëm të përmbledhur ato grupe të veçanta.
>> Kështu që tani që ne jemi mbledhur së 3 n. Kjo nuk është vetëm 3 të n.
Ajo gjithmonë do të jetë n / 2 të n.
Pra, këtu kemi të ndodhë që të ketë 6.
Nëse do të kishim 10 gjërat, atëherë ne mund të bëjmë këtë grupim për 5 çifte të ndryshme të gjërave
dhe përfundojnë me n + n + n + n + n.
Pra, ju jeni gjithmonë do të merrni n / 2 e N, dhe kështu kjo ne do të shënoj atë për n katror / 2.
Dhe kështu edhe pse kjo është faktor i gjysmës së, gjë që ndodh për të ardhur në
për shkak të faktit se nëpërmjet çdo ripërsëritje mbi array krahasojmë 1 më pak
kështu që kjo është se si ne të merrni më shumë se 2, por ajo është ende n katror.
Ne nuk e kujdesit në lidhje me faktor të vazhdueshëm të një gjysmë.
Pra, një shumë gjëra të mëdha O si kjo mbështetet në vetëm një lloj të bërë këtë lloj të matematikë,
bërë shuma aritmetike dhe gjeometrike sende seri,
por shumica e tyre në këtë kurs janë goxha të thjeshtë.
Rregull.
Pse është lloj futje në Omega e n? Çfarë do të thotë omega?
[Dy studentë duke folur në një herë - pakuptueshëm] Yeah >>.
Omega ju mund të mendoni si të ulët detyruar.
>> Pra nuk ka rëndësi se sa të efektshme lloj futje juaj algoritmi është,
pavarësisht nga lista që është miratuar në, ajo gjithmonë ka për të krahasuar të paktën n gjërat
ose ajo ka për të iterate mbi gjërat n.
Pse është kjo?
[Student] Sepse nëse lista është renditur tashmë, pastaj përmes përsëritje parë
ju mund të garantojë se elementi i parë është pak,
dhe përsëritje e dytë që ju vetëm mund të garantojë dy të parët janë
sepse ju nuk e dini se pjesa tjetër e listës është renditur. Po >>.
Në qoftë se ju të kalojë në një listë të renditura plotësisht, të paktën ju keni për të shkuar mbi të gjitha elementet e
për të parë se asgjë nuk ka nevojë për të lëvizur rreth.
Kështu kalon mbi listën dhe duke thënë, oh, kjo është tashmë e renditura,
është e pamundur për ju të dini është e renditura derisa ju të kontrolloni çdo element
për të parë se ata janë në mënyrë renditura.
Kështu ulët i detyruar në lloj futje është i Omega n.
Çfarë është rasti më i keq drejtimin koha e lloj bashkojë,
Rasti më i keq qenë O mëdha përsëri?
Pra, në rastin më të keq, si e bën lloj bashkojë të drejtuar?
[Student] N log n. Po >>.
Më të shpejtë algoritme përgjithshme rradhitje janë n log n. Ju nuk mund të bëjmë më mirë.
>> Ka raste të veçanta, dhe në qoftë se ne kemi kohë sot - por ne ndoshta won't -
ne mund të shohim atë që bën më mirë se n log n.
Por në rastin e përgjithshëm, ju nuk mund të bëni më mirë se n log n.
Dhe të shkrihej lloj ndodh të jetë një që ju duhet të dini për këtë kurs që është n log n.
Dhe kështu që ne do të jetë në fakt zbatimin që sot.
Dhe së fundi, në jo më shumë se tre fjali, si e bën punën e përzgjedhjes renditjes?
A dikush dëshiron të përgjigjem, dhe unë do të llogariten dënimet tuaja
sepse në qoftë se ju shkoni mbi 3 -
A ka dikush kujtohet lloj përzgjedhje?
Lloj Zgjedhja është zakonisht shumë e lehtë për të kujtuar vetëm nga emri.
Ju vetëm iterate mbi array, të gjejnë çfarëdo vlera më e madhe është ose më i vogël -
çfarëdo mënyrë që ju jeni klasifikim in
Pra, le të thonë se ne jemi zgjidhja nga më i vogli tek më i madh.
Ju iterate mbi array, duke kërkuar për çfarëdo elementi minimal është,
përzgjidhe at, dhe pastaj vetëm shkëmbim atë çka është në vendin e parë.
Dhe pastaj në kalimin e dytë mbi vektorit, po për të elementit minimale përsëri,
zgjidhni atë, dhe pastaj të bie në ujdi me atë që është në pozitën e dytë.
Pra, ne jemi vetëm picking dhe duke zgjedhur vlerat minimale
dhe futur ato në frontin e vektorit deri sa ajo është e renditura.
Pyetjet për këtë?
>> Këto shfaqen në mënyrë të pashmangshme në format që ju duhet të plotësoni kur ju jeni dorëzimin e pset.
Ata janë në thelb të përgjigjet atyre.
Mirë, kështu që tani coding probleme.
Unë tashmë e dërguar nga mbi email - A nuk merrni atë dikush email? Rregull.
Unë tashmë dërguar email mbi hapësirën që ne jemi duke shkuar për të përdorur,
dhe në qoftë se ju klikoni mbi emrin tim - kështu që unë mendoj se jam do të jetë në fund
për shkak të r prapa - por nëse ju klikoni në emrin tim ju do të shihni 2 rishikime.
Rishikimi 1 do të jetë I kopjuar dhe tashmë ngjit kodin në Spaces
për gjë kërkimit ju jeni do të duhet të zbatojnë.
Rishikimi dhe 2 do të jetë gjëja lloj që ne zbatimin e pas kësaj.
Kështu që ju mund të klikoni mbi Revision time 1 dhe punojnë nga atje.
Dhe tani ne duam të zbatojë kërkimin binar.
>> A ka dikush duan të japin vetëm një shpjegim pseudokod të nivelit të lartë
të asaj që ne do të duhet të bëni për kërkim? Po.
[Student] Ju vetëm të marrë mes të grup dhe të shohim nëse ajo që ju jeni duke kërkuar për
është më pak se që ose më shumë se që.
Dhe në qoftë se kjo është pak, ju shkoni në gjysmën e që është më pak,
dhe në qoftë se kjo është më shumë, ju shkoni në gjysmën që është më shumë dhe ju përsëris se deri sa ju të merrni vetëm një gjë.
[Bowden] Yeah.
Vini re se array numrat ynë është renditur tashmë,
dhe kështu që do të thotë që ne të mund të përfitojnë nga kjo dhe ne mund të kontrolloni të parë,
rregull, unë jam duke kërkuar për numrin 50.
Kështu që unë mund të shkojnë në mes.
Mesme është e vështirë të përcaktojë kur është një numër edhe më të gjëra,
por le të them vetëm ne do të shkurtoj gjithmonë në mes.
Pra, këtu kemi 8 gjëra, kështu që mesme do të jetë 16.
Unë jam duke kërkuar për 50, 50 kështu që është më i madh se 16.
Kështu që tani unë mund të trajtojë në thelb koleksion time si këto elemente.
Unë mund të hedhin larg çdo gjë nga 16 gjatë.
Tani array im është vetëm këto 4 elemente, dhe unë përsëris.
Pra, atëherë unë dua të gjeni mesme përsëri, e cila do të jetë 42.
42 është më pak se 50, kështu që unë mund të hedhin larg këto dy elemente.
Ky është im array mbetur.
Unë jam duke shkuar për të gjetur e mesme përsëri.
I guess 50 ishte një shembull i keq, sepse unë kam qenë gjithmonë gjëra të hedhur larg në të majtë,
por në të njëjtën masë, në qoftë se unë jam duke kërkuar për diçka
dhe kjo është më pak se elementi Unë jam duke kërkuar në,
atëherë unë jam duke shkuar për të hedhur larg çdo gjë në të djathtë.
Pra, tani ne kemi nevojë për të zbatuar atë.
Vini re se ne kemi nevojë për të kaluar në madhësi.
Ne nuk mund të duhet për të vështirë-koduar madhësi.
Pra, nëse ne të hequr qafe se # define -
Rregull.
Si mund ta kuptoj mirë se çfarë madhësia e array numrat aktualisht është?
>> Sa elemente janë në grup numrat?
[Student] Numrat, kllapa,. Gjatësi?
[Bowden] Kjo nuk ekziston në C.
Nevojë. Gjatësi.
Vargjeve nuk kanë prona, kështu që nuk ka pronë gjatësia e vargjeve
që thjesht do të ju jap kohë megjithatë ndodh që të jetë.
[Student] Shih se sa memorie ka dhe ndani me sa - Po. >>
Pra, si mund të shohim sa memorie ka? >> [Student] sizeof. Po >>, sizeof.
Sizeof është operatori që do të kthehen në madhësinë e grup numrash.
Dhe kjo do të jetë integers megjithatë shumë herë nuk janë të madhësisë së një numër i plotë
pasi që është sa memorie është e vërtetë duke marrë deri.
Pra, nëse unë dua numrin e gjërave në grup,
atëherë unë jam duke shkuar për të dëshironi të ndani me madhësinë e një numër të plotë.
Rregull. Kështu që lejon mua të kalojnë në madhësi këtu.
Pse duhet të kalojë në madhësi në të gjitha?
Pse nuk mund ta bëjë vetëm deri këtu madhësia int = sizeof (Kashtë) / sizeof (int)?
Pse nuk është kjo punë?
[Student] Kjo nuk është një ndryshore globale.
[Bowden] Kashtë ekziston dhe ne jemi duke kaluar në numër si kashtë,
dhe kjo është lloj i një paralajmërim i asaj që do të vijnë. Po.
[Student] Kashtë është vetëm referencë për atë, kështu që ajo do të kthehet sa e madhe që është referencë.
Po.
Unë dyshoj në leksionin që e keni parë ende rafte me të vërtetë, e drejtë?
Ne kemi folur vetëm në lidhje me të.
Pra rafte është vendi ku të gjitha variablave tuaja do të ruhen.
>> Çdo kujtesës që është ndarë për variablat lokale që po ndodh në rafte,
dhe çdo funksion merr hapësirën e vet në rafte, kornizë vet rafte është ajo që është quajtur.
Pra kryesor ka kuadrin e saj rafte, dhe në brendësi të tij do të ekzistojë në këtë koleksion numrat,
dhe ajo do të jetë e madhësisë sizeof (numra).
Ajo do të ketë madhësinë e numrave të ndarë nga madhësia e elementeve,
por që gjithë jetën brenda kornizës kryesore e rafte.
Kur ne e quajmë kërko, kërko merr vet kuadrin e saj rafte,
Hapësira e vet për të ruajtur të gjitha variablave të saj lokale.
Por këto argumente - kështu Kashtë nuk është një kopje e këtij grup të tërë.
Ne nuk kalojnë në rrjet të tërë si një kopje në kërkim.
Ajo vetëm kalon një referencë për këtë koleksion.
Pra, kërkoni mund të hyni në këto numra nëpër këtë referencë.
Është ende qasjen gjërat që jetojnë në brendësi të kornizës kryesore të rafte,
por në thelb, kur ne të merrni për pointers, e cila duhet të jetë së shpejti,
kjo është ajo që pointers janë.
Pointers janë vetëm referenca të gjëra, dhe ju mund të përdorni pointers për të hyrë në gjërat
që janë në korniza gjëra të tjera 'rafte.
Pra, edhe pse numri është lokal me kryesor, ne ende mund të hyni në atë nëpërmjet këtij treguesin.
Por, pasi ajo është vetëm një tregues dhe kjo është vetëm një referencë,
sizeof (Kashtë) vetëm e kthen madhësinë e referencës vetë.
Ajo nuk kthehet në madhësinë e gjë është e treguar për të.
Ajo nuk kthehet madhësinë aktuale të numrave.
Dhe kështu që kjo nuk do të punojë si ne duam që ajo të.
>> Pyetjet për këtë?
Pointers do të shkuar në detaje në mënyrë të konsiderueshme më shumë gjakosur në javët që do të vijnë.
Dhe kjo është arsyeja pse shumë gjëra që ju shikoni, gjërat më të kërkimit apo gjërat lloj,
ata janë pothuajse të gjithë do të duhet të marrë madhësinë aktuale të array,
sepse në C, ne nuk kemi ide se çfarë madhësia e array është.
Ju duhet të dorë të kalojë atë in
Dhe ju nuk mund të kalojë dorë në rrjet të gjithë, sepse ju jeni vetëm duke kaluar në referencë
dhe ajo nuk mund të marrë përmasat nga referencë.
Rregull.
Pra, tani ne duam të zbatojë atë që është shpjeguar më parë.
Ju mund të punojnë në atë për një minutë,
dhe ju nuk duhet të shqetësohen për marrjen e çdo gjë të përkryer 100% të punës.
Vetëm shkruani deri pseudokod gjysmë për mënyrën se si ju mendoni se duhet të punojnë.
Rregull.
Nuk ka nevojë për të bërë plotësisht me këtë ende.
Por ka dikush të ndjehen rehat me atë që ata kanë deri më tani,
si diçka që ne mund të punojnë me të së bashku?
A ka dikush doni te vullnetar? Ose unë do të marr rastësisht.
Ajo nuk duhet të jetë e drejtë nga ndonjë masë, por diçka që ne mund të modifikoj në një shtet të punës.
[Student] Sure. Mirë >>.
Kështu që ju mund të ruani rishikimin duke klikuar në ikonën e vogël Save.
Ju jeni Ramya, apo jo? >> [Student] Yeah. >> [Bowden] Okay.
Deri tani unë mund të shikoni tuaj rishikimin dhe secili mund të tërheqë deri rishikim.
Dhe këtu kemi - Mirë.
Kështu Ramya shkoi me zgjidhjen gjithkund rekursive, i cili është padyshim një zgjidhje të vlefshme.
Ka dy mënyra që ju mund të bëni këtë problem.
Ju mund ta bëni atë apo iteratively Recursively.
Shumica e problemeve që ju hasni që mund të bëhet Recursively mund të bëhet edhe iteratively.
Kështu që këtu ne kemi bërë atë Recursively.
>> Ka dikush doni të përcaktuar se çfarë do të thotë për të bërë një funksion recursive?
[Student] Kur ju keni një funksion quajnë veten
dhe pastaj e quajnë veten deri sa ajo vjen me të vërteta dhe të vërtetë. Po >>.
Një funksion recursive është vetëm një funksion i cili e quan veten.
Ka tri gjëra të mëdha që një funksion recursive duhet të ketë.
E para është padyshim, që e quan veten.
E dyta është rasti bazë.
Pra, në disa pika funksioni ka nevojë për të ndaluar e quan veten,
dhe kjo është ajo që ndodh është për bazë.
Kështu që këtu ne e dimë se ne duhet të ndalet, ne duhet të heqim dorë në kërkimin tonë
kur fillimi është e barabartë me fund - dhe ne do të shkojnë mbi atë që thotë.
Por në fund, gjëja e fundit që është e rëndësishme për funksionet gjithkund rekursive:
funksionet duhet disi qasen çështjen bazë.
Ashtu si në qoftë se ju nuk jeni në të vërtetë përditësimin asgjë kur ju bëni thirrje rekursive dytë,
në qoftë se ju jeni fjalë për fjalë vetëm duke e quajtur funksion përsëri me të njëjtat argumente
dhe nuk variabla globale kanë ndryshuar apo ndonjë gjë,
ju kurrë nuk do të arrijë çështjen bazë, në të cilin rast se është e keqe.
Ajo do të jetë një recursion pafund dhe një pirg del nga shtrati.
Por këtu ne shohim se update po ndodh pasi ne jemi përditësimin fillojnë + fund / 2,
ne jemi përditësimin argumentin fund këtu, ne jemi përditësimin argumentin filloni këtu.
Pra, në të gjitha thirrjet gjithkund rekursive ne jemi përditësimin diçka. Rregull.
A doni të ecni ne nëpërmjet zgjidhjes tuaj? Sigurisht >>.
Unë jam duke përdorur SearchHelp kështu që çdo herë që unë të bëjë këtë thirrje funksion
Unë kam fillimin e ku unë jam duke kërkuar për në rrjet dhe në fund
se ku unë jam duke kërkuar array.
>> Në çdo hap ku është thënë se është element mesme, e cila është fillimi fundi + / 2,
është se e barabartë me atë që ne jemi duke kërkuar për?
Dhe në qoftë se ajo është, atëherë kemi gjetur atë, dhe unë mendoj se merr kaluar deri nivelet e recursion.
Dhe në qoftë se nuk është e vërtetë, atëherë ne kontrolloni nëse se vlera e mesme e grup është shumë i madh,
rast në të cilin ne e shohim në gjysmën e majtë të array duke shkuar nga fillimi në indeksin e mesme.
Dhe ndryshe bëjmë gjysmën fund.
[Bowden] Okay.
Ide e mirë.
Mirë, kështu që një çift gjërat, dhe në fakt, kjo është një gjë shumë e nivelit të lartë
që ju kurrë nuk do të duhet të dini për këtë kurs, por kjo është e vërtetë.
Funksionet gjithkund rekursive, ju gjithmonë dëgjuar se ata janë një marrëveshje e keqe
sepse nëse ju telefononi Recursively veten shumë herë, ju merrni overflow stack
pasi, siç kam thënë më parë, çdo funksion merr vet kuadrin e saj rafte.
Kështu që çdo thirrje të funksionit rekursiv merr vet kuadrin e saj rafte.
Pra, nëse ju të bëni thirrje 1.000 gjithkund rekursive, që ju të merrni 1.000 korniza rafte,
dhe shpejt ju të çojë për të pasur korniza shumë rafte dhe gjëra vetëm thyer.
Pra, kjo është arsyeja pse funksionet gjithkund rekursive në përgjithësi janë të këqija.
Por nuk është një subset e bukur e funksioneve gjithkund rekursive gjithkund rekursive quajtur bisht-funksionet,
dhe kjo ndodh të jetë një shembull i një ku në qoftë se përpiluesit e vëren këtë
dhe kjo duhet, unë mendoj se - në qoftë se ju të kalojë tingëllimë atë-O2 flamur
atëherë ajo do të vini re kjo është bishti rekursive dhe të bëjë gjëra të mira.
>> Ajo do të ripërdorimin kornizë njëjtin rafte mbi dhe pa pushim për çdo thirrje rekursive.
Dhe kështu që ju jeni duke përdorur të njëjtën kornizë rafte, ju nuk keni nevojë për t'u shqetësuar rreth
ndonjëherë rafte tejmbushur, dhe në të njëjtën kohë, si ju tha më parë,
ku sapo ju të ktheheni e vërtetë, atëherë ajo duhet të kthehet deri të gjitha këto korniza rafte
dhe thirrja për 10 SearchHelp duhet të kthehet në 9, duhet të kthehen në 8.
Kështu që nuk ka nevojë të ndodhë kur funksionet gjithkund rekursive janë bisht.
Dhe kështu ajo që e bën këtë funksion recursive bishti është njoftimi që për çdo thirrje të dhënë për searchHelp
thirrja rekursive që është bërë është ajo që po kthehen.
Pra, në thirrjen e parë në SearchHelp, ne ose kthehen menjëherë të rreme,
kthehen menjëherë e vërtetë, apo kemi bërë një thirrje rekursive për SearchHelp
ku ajo që ne jemi duke u kthyer është ajo që thirrja është kthyer.
Dhe ne nuk mund ta bëjë këtë në qoftë se ne e bëmë diçka si int x = SearchHelp, kthimit x * 2,
vetëm disa ndryshime të rastit.
>> Deri tani kjo thirrje rekursive, kjo int x = thirrje SearchHelp rekursive,
nuk është më bisht recursive sepse ai në fakt nuk duhet të kthehet
përsëri në një kornizë pirg në mënyrë që të mëparshme se thirrja e mëparshme në funksion
pastaj mund të bëjë diçka me vlerë e kthimit.
Pra, kjo nuk është bishti rekursive, por ajo që ne kishim para është bukur bisht rekursive. Po.
[Student] nuk duhet të jetë rasti i dytë bazë kontrollohet parë
sepse nuk mund të jetë një situatë ku, kur ju të kalojë atë argumentin
ju keni filluar = fund, por ato janë vlera gjilpërë.
Pyetja nuk ishte ne mund të kandidojë në rastin kur në fund është vlera gjilpërë
ose të fillojnë = fund, të përshtatshme, të fillojë = fund
dhe ju nuk keni kontrolluar të vërtetë atë vlerë të veçantë ende,
pastaj të fillojë + fund / 2 është vetëm do të jetë vlera e njëjtë.
Por ne kemi kthyer tashmë rreme dhe ne kurrë nuk kontrollohen në fakt vlerën.
Pra, të paktën, në thirrjen e parë, në qoftë se madhësia është 0, atëherë ne duam të kthehen rreme.
Por në qoftë se madhësia është 1, atëherë nuk do të fillojë deri në fund të barabartë,
dhe ne do të të paktën të kontrolluar elementin një.
Por unë mendoj se ju jeni të drejtë në atë që ne mund të përfundojë në një rast kur fillojnë + fund / 2,
Fillimi përfundon duke qenë të njëjta si fillim + fund / 2,
por kurrë nuk kemi kontrolluar të vërtetë atë element.
>> Pra, në qoftë se ne së pari të kontrolloni është elementi mesme vlera ne jemi duke kërkuar për të,
atëherë ne mund të kthehen menjëherë vërtetë.
Tjetër në qoftë se ata janë të barabartë, atëherë nuk ka asnjë pikë për të vazhduar
pasi ne jemi vetëm duke shkuar për të rinovuar në një rast ku ne jemi në një grup të vetëm element.
Në qoftë se elementi i vetëm nuk është një ne jemi duke kërkuar për të,
atëherë çdo gjë është e gabuar. Po.
[Student] Gjë është se që nga madhësia është në të vërtetë më i madh se numri i elementeve në array,
ka tashmë një kompensuar - >> Pra do size -
[Student] Thuaj, nëse array ishte madhësia 0, atëherë SearchHelp të vërtetë do të kontrollojë kashtë e 0
në thirrjen e parë.
Grup ka madhësi 0, kështu që është 0 - >> Yeah.
Nuk është një tjetër gjë që - kjo mund të jetë e mirë. Le të mendojmë.
Pra, nëse array kishte 10 elemente dhe një e mesme ne jemi duke shkuar për të kontrolluar është indeksi 5,
kështu që ne jemi duke kontrolluar 5, dhe le të thonë se vlera është më pak.
Pra, ne jemi duke hedhur çdo gjë larg nga 5 e tutje.
Pra, fillojë në fund + / 2 do të jetë fundi ynë i ri,
Pra, vërtet, ajo është gjithmonë do të qëndrojë edhe pas përfundimit të vektorit.
Në qoftë se kjo është një rast në qoftë se ajo ishte edhe apo i rastësishëm, atëherë ne do të kontrolloni, të themi, 4,
por ne jemi ende duke hedhur larg -
Pra, vërtet, në fund është gjithmonë do të jetë edhe pas përfundimit aktual të vektorit.
Pra, elementet ne jemi duke u përqëndruar në, në fund është gjithmonë do të jetë njëri pas kësaj.
Dhe kështu që nëse fillimi bën kurrë fund të barabartë, ne jemi në një grup të madhësisë 0.
>> Gjë tjetër që unë isha duke menduar është që ne jemi përditësimin fillojnë të fillojnë + fund / 2,
kështu që ky është rasti që unë jam i pasur probleme me të, kur fillojnë + fund / 2
është elementi ne jemi të kontrolluar.
Le të thonë se kemi pasur këtë koleksion 10-element. Çfarëdo.
Pra, fillojë në fund + / 2 do të jetë diçka si ky,
dhe në qoftë se nuk është vlera, thonë se ne duam për të rinovuar.
Vlera është më e madhe, kështu që ne duam të shikojmë në këtë gjysmën e vektorit.
Deri sa ne jemi përditësimin fillim, ne jemi përditësimin fillim të tani do të jetë ky element.
Por kjo ende mund të punojnë, ose në shumë pak, ju mund të bëni të fillojë në fund + / 2 + 1.
[Student] Ju nuk duhet të fillojë në fund + [padëgjueshme] >> Yeah.
Ne kemi kontrolluar tashmë këtë element dhe e di se nuk është një ne jemi duke kërkuar për të.
Pra, ne nuk kemi nevojë për të rinovuar të fillojë të jetë në këtë element.
Ne vetëm mund të kaloni atë dhe përditësimin e të fillojë të jetë në këtë element.
Dhe a ka kurrë një rast, le të themi, se ky ishte fundi,
kështu që pastaj të fillojë do të jetë ky, të fillojnë + fund / 2 do të jetë kjo,
fillojnë + fund - Po, unë mendoj se mund të përfundojë deri në recursion pafund.
Le të thonë se kjo është vetëm një grup të madhësisë 2 ose një grup të madhësisë 1. Unë mendoj se kjo do të punojnë.
Pra, aktualisht, fillimi është se elementi dhe në fund është 1 përtej tij.
Pra, element që ne jemi duke shkuar për të kontrolluar është kjo një,
dhe pastaj kur ne update fillim, ne jemi përditësimin fillojë të jetë 0 + 1/2,
e cila do të përfundojë të na kthehet me fillimin qenë ky element.
>> Pra, ne jemi të kontrolluar elementin njëjta pa pushim.
Pra, ky është rasti ku çdo thirrje rekursive duhet të vërtetë të rinovuar diçka.
Pra, ne duhet të bëjmë fillimin + fund / 2 + 1, ose tjetër ka një rast
ku ne nuk jeni në të vërtetë fillimin përditësimin.
Gjithkush shihni se?
Rregull.
A ka ndokush pyetje për këtë zgjidhje ose komente asnjë më shumë?
Rregull. Does anyone kanë një përsëritës zgjidhje që ne të gjithë mund të shikojnë?
A ne të gjithë bëjmë atë Recursively?
Ose edhe unë mendoj se në qoftë se ju hap hers, atëherë ju mund të keni të parandalohet një tuaj të mëparshëm.
E bën atë automatikisht të shpëtuar? Unë nuk jam pozitive.
Does anyone kanë përsëritës?
Ne mund të ecin nëpër atë së bashku, nëse jo.
Ideja do të jetë e njëjtë.
Përsëritës zgjidhje.
Ne do të duan të bëjnë në thelb të njëjtën ide
ku ne duam të mbajnë gjurmët e përfundimit të ri të grup dhe fillimin e ri të array
dhe të bëjë atë mbi dhe mbi.
Dhe në qoftë se ajo që ne jemi mbajtja e si fillim dhe në fund gjithnjë ndërpritet,
atëherë ne nuk kemi gjetur atë dhe ne mund të kthehet rreme.
Pra, si mund ta bëni këtë? Dikush ka sugjerime ose kod për mua për të tërhequr deri?
[Student] A një lak kohë. Po >>.
Ju do të dëshironi të bëni një lak.
>> A keni kodin unë mund të tërheqë deri, ose çfarë u keni shkuar për të sugjeruar?
[Student] Unë mendoj kështu. >> All drejtë. Kjo e bën gjërat më të lehtë. Cili ishte emri juaj?
[Student] Lucas.
Rishikimi 1. Rregull.
Ulët është ajo që ne e quajti filluar më parë.
Up nuk është mjaft atë që quhet fundi parë.
Në fakt, në fund tani është në rrjet. Është një element që duhet marrë parasysh.
Aq i ulët është 0, lart është madhësia e grup - 1,
dhe tani ne jemi looping, dhe ne jemi të kontrolluar -
I guess ju mund të ecin nëpër atë.
Cili ishte menduarit tuaj nëpërmjet këtë? Ecni ne nëpërmjet kodit tuaj.
[Student] Sure. Shikoni në vlerën e kashtë në mes dhe të krahasojnë atë me gjilpërë.
Pra, në qoftë se ajo është më e madhe se gjilpërë tuaj, atëherë ju doni të - oh, në të vërtetë, që duhet të jetë prapa.
Ju jeni do të duan të hedhin larg gjysmën e drejtë, dhe kështu vërtet, që duhet të jetë rruga.
[Bowden] Pra, kjo duhet të jetë më pak? Është se ajo që keni thënë? >> [Student] Yeah.
[Bowden] Okay. Më pak.
Pra, në qoftë se ajo që ne jemi duke kërkuar në është më i vogël se ajo që ne duam,
atëherë vërtet, ne duam që të hedhin larg gjysmën e majtë,
që do të thotë ne jemi përditësimin çdo gjë që ne jemi duke marrë parasysh
duke lëvizur në të djathtë të ulët të vektorit.
Kjo duket e mirë.
Unë mendoj se kjo ka të njëjtën çështje që ne tha në një mëparshme,
ku nëse i ulët është 0 dhe lart është 1, atëherë të ulët + up / 2 do të jetë ngritur për të njëjtën gjë përsëri.
>> Dhe edhe në qoftë se nuk është rasti, ajo është ende më efikase në shumë pak
të vetëm hedhin larg elementin ne vetëm shikuar në të cilën ne e dimë është e gabuar.
Në mënyrë të ulët + up / 2 + 1 - >> [Student] Kjo duhet të jetë mënyra të tjera.
[Bowden] Apo kjo duhet të jetë - 1 dhe një tjetër duhet të jetë + 1.
[Student] Dhe nuk duhet të jetë një shenjë të dyfishtë barabartë. >> [Bowden] Yeah.
[Student] Yeah.
Rregull.
Dhe së fundi, tani që ne kemi këtë + 1-1 gjë,
është ajo - ai nuk mund të jetë - është gjithnjë e mundur për të ulët të përfundojnë me një vlerë më të madhe se deri?
Unë mendoj se mënyra e vetme që mund të ndodhë - është e mundur? >> [Student] Unë nuk e di.
Por në qoftë se ajo merr cunguar dhe pastaj merr minus se 1 dhe pastaj - >> Yeah.
[Student] Ajo ndoshta do të merrni messed up.
Unë mendoj se kjo duhet të jetë e mirë vetëm për shkak se
që ajo të përfundojë më të ulët se ata do të duhet të jenë të barabartë, unë mendoj.
Por në qoftë se ata janë të barabartë, atëherë ne nuk do të kishte bërë lak, ndërsa për të filluar me
dhe ne vetëm do të kthyer vlerën. Kështu që unë mendoj se ne jemi të mirë tani.
Vini re se edhe pse ky problem nuk është më rekursive,
njëjtin lloj e ideve të aplikojnë ku ne mund të shohim se si kjo kaq lehtë jep veten
për një zgjidhje rekursiv nga fakti se ne jemi vetëm përditësimin e indekseve pa pushim,
ne jemi duke e bërë problem vogla dhe të vogla, ne jemi duke u përqëndruar në një mesin e array.
[Student] Nëse i ulët është 0 dhe lart është 1, ata do të jenë të dyja 0 + 1/2, i cili do të shkojë në 0,
dhe pastaj do të jetë një + 1, një do të jetë - 1.
[Student] Ku jemi ne kontrollimin e barazisë?
Ashtu si në qoftë se një e mesme është në të vërtetë gjilpërë?
Ne nuk jemi duke bërë atë? Oh!
Nëse it's -
Po. Ne nuk mund të bëjë testin këtu poshtë, sepse le të themi e mesme parë -
[Student] Është fakt si nuk e hedhin larg lidhur.
Pra, nëse ju hedh larg lidhur, ju duhet për të kontrolluar atë para apo çfarëdo.
Ah. Po. >> [Student] Yeah.
Pra, tani ne kemi hedhur larg atë që ne aktualisht shikuar në,
që do të thotë që ne tani duhet të ketë gjithashtu
në qoftë se (Kashtë [(Ulët + deri) / 2] == gjilpërë), atëherë ne mund të kthehen vërtetë.
Dhe nëse kam vënë tjetër ose vetëm në qoftë se, kjo do të thotë fjalë për fjalë të njëjtën gjë
sepse kjo do të janë kthyer vërtetë.
Kështu që unë do të vënë tjetër në qoftë se, por kjo nuk ka rëndësi.
>> Pra, nëse kjo tjetër, tjetër këtë, dhe kjo është një gjë e zakonshme të bëj
ku edhe nëse ajo është rasti ku çdo gjë është e mirë këtu,
si të ulët nuk mund të jetë më e madhe se lart, kjo nuk është arsyetim vlen rreth asaj nëse kjo është e vërtetë.
Kështu që ju mund edhe të thonë, ndërsa të ulët është më pak se ose e barabartë me
ose derisa të ulët është më pak se
kështu që nëse ata janë të barabartë apo të ulët ndonjëherë ndodh që të kalojë deri,
atëherë ne mund të shpërthejë nga ky lak.
Pyetje, shqetësime, komente?
Rregull. Kjo duket e mirë.
Tani ne duam të bëjmë lloj.
Nëse ne do të shkojmë për rishikimin e dytë, ne shohim këto shifra të njëjta,
por tani ata nuk janë më në mënyrë renditura.
Dhe ne duam të zbatojë përdorimin e ndonjë lloj algoritmi në të O n log n.
Kështu që algoritmi mendoni ju se ne duhet të zbatojë këtu? >> [Student] lloj Merge.
[Bowden] Yeah. Merge lloj është O (n log n), kështu që kjo është ajo që ne jemi duke shkuar për të bërë.
Dhe problemi do të jetë shumë e ngjashme,
ku të lehtë jep veten për një zgjidhje gjithkund rekursive.
Ne gjithashtu mund të dalë me një zgjidhje përsëritës nëse duam,
por recursion do të jetë më e lehtë këtu dhe ne duhet të bëjmë recursion.
I guess ne do të ecim nëpër lloj bashkojë të parë,
edhe pse nuk është një video e bukur në lloj Merge tashmë. [Qeshura]
Pra bashkojë lloj ka - Unë jam humbur aq shumë i këtij punimi.
Oh, ka vetëm një të majtë.
Pra bashkohen.
Oh, 1, 3, 5.
Rregull.
Merge merr dy vargjeve të veçanta.
Individualisht këto dy vargjeve të dyja janë të renditura.
Pra, ky grup, 1, 3, 5, të renditura. Ky grup, 0, 2, 4, renditura.
Tani çfarë bashkojë duhet të bëni është të kombinohen ato në një rrjet të vetëm që është vetë renditura.
Pra, ne duam një rrjet të madhësisë 6 që do të kenë këto elemente në brendësi të saj
në mënyrë renditura.
>> Dhe kështu që ne mund të përfitojnë nga fakti se këto dy vargjeve janë të renditura
për të bërë këtë në kohë lineare,
Kuptimi lineare Ora nëse ky grup është x madhësi dhe kjo është y madhësia,
atëherë algoritmi i përgjithshëm duhet të jetë O (x + y). Rregull.
Pra sugjerime.
[Student] A mund të fillojnë nga e majta?
Kështu që ju do të vënë poshtë 0 të parë dhe pastaj 1 dhe atëherë këtu ju jeni në 2.
Pra, kjo është lloj i si ju keni një skedë që është duke lëvizur në të djathtë. >> [Bowden] Yeah.
Për të dyja këto vargjeve nëse ne vetëm të përqëndrohet në elementin pari nga e majta.
Sepse të dy vargjeve janë të renditura, ne e dimë se këto 2 elemente
janë elementet më të vogla në secilin grup.
Kështu që do të thotë se 1 nga ata 2 elemente duhet të jenë element i vogël në rrjet tonë bashkuar.
Kjo ndodh pikërisht kështu që i vogël është ai në kohën e duhur këtë.
Pra, ne kemi marrë 0, futur atë në të majtë, sepse është më pak se 0 1,
kështu që të marrë 0, futur atë në pozitën tonë të parë, dhe pastaj ne update këtë
tani përqëndrohet në elementin e parë.
Dhe tani ne përsërisim.
Deri tani ne krahasojmë 2 dhe 1. 1 është më i vogël, kështu që ne do të futni 1.
Ne update këtë tregues të tregojnë për këtë djalë.
Tani ne bëjmë atë përsëri, kështu që 2. Kjo do të update, krahasuar këto 2, 3.
Kjo përditësime, pastaj 4 dhe 5.
Kështu që është bashkojë.
>> Ajo duhet të jetë goxha e qartë se kjo është koha lineare që ne vetëm të shkojnë nëpër çdo element herë.
Dhe kjo është hapi më i madh në zbatimin lloj bashkojë është duke bërë këtë.
Dhe kjo nuk është se e vështirë.
Një disa gjëra për t'u shqetësuar rreth është le të themi se janë shkrirja 1, 2, 3, 4, 5, 6.
Në këtë rast ne fund deri në skenar ku kjo është e do të jetë më i vogël,
pastaj ne update këtë tregues, kjo do të jetë më i vogël, update this,
kjo është më e vogël, dhe tani ju duhet të njohin
kur ju keni të vërtetë të drejtuar nga elementë të krahasuar me të.
Që nga viti ne kemi përdorur tashmë këtë koleksion të tërë,
çdo gjë në këtë grup tani është futur vetëm në këtu.
Pra, në qoftë se ne ndonjëherë të kandidojë në pikën ku një prej vargjeve tona është shkrirë plotësisht tashmë,
atëherë ne vetëm të marrë të gjitha elementet e vektorit tjetër dhe futur ato në fund të vektorit.
Pra, ne vetëm mund të futni 4, 5, 6. Rregull.
Kjo është një gjë për të parë për të.
Zbatimin që duhet të jetë hapi i 1.
Merge lloj pastaj në bazë të kësaj, ajo është 2 hapa, 2 hapa pa kuptim.
Le të japim këtë koleksion.
Pra bashkojë lloj, hap 1 është që të Recursively të thyer grup në gjysmave.
Ndarë kështu këtë grup në gjysmave.
Ne tani kemi 4, 15, 16, 50 dhe 8, 23, 42, 108.
Dhe tani ne e bëjmë atë përsëri dhe ne ndarë këto në gjysmave.
Unë vetëm do të bëni atë në këtë anë.
Kështu 4, 15 dhe 16, 50.
Ne do të bëjmë të njëjtën gjë gjatë këtu.
Dhe tani ne ndarë atë në gjysmave përsëri.
Dhe ne kemi 4, 15, 16, 50.
Kështu që është rasti ynë bazë.
Pasi vargjeve janë të madhësisë 1, atëherë kemi të ndaluar me ndarjen në pjesë.
>> Tani çfarë bëjmë ne me këtë?
Ne deri në fund kjo do të prishen në 8, 23, 42, dhe 108.
Pra, tani që ne jemi në këtë pikë, tani hap dy lloj bashkojë është vetëm bashkimi palë të listave.
Pra, ne duam që të bashkojë këto. Ne vetëm thirrje të bashkohen.
Ne e dimë se do të kthehet bashkojë këto në mënyrë renditura.
4, 15.
Tani ne duam të bashkojë këto, dhe se do të kthehet një listë me ato në mënyrë renditura,
16, 50.
Ne bashkojë ata - Unë nuk mund të shkruaj - 8, 23 dhe 42, 108.
Pra, ne kemi çifte shkrirë njëherë.
Tani ne vetëm të bashkohen përsëri.
Vini re se secili prej këtyre listave është renditur në vetvete,
dhe pastaj ne vetëm mund të bashkojë këto lista për të marrë një listë të madhësisë 4, i cili është renditur
dhe të shkrihej këto dy lista të merrni një listë të madhësisë 4 që është renditura.
Dhe në fund, ne mund të bashkojë këto dy lista të madhësisë 4 të merrni një listë të madhësisë 8 që është renditura.
Pra, për të parë se kjo është e përgjithshme n log n, ne tashmë e pa se bashkojë është linear,
kështu që kur ne jemi që kanë të bëjnë me bashkimin këto, kështu si koston e përgjithshme të bashkohen
për këto dy listave është vetëm 2 sepse -
Ose mirë, kjo është O n, por n këtu është vetëm këto 2 elemente, kështu që është 2.
Dhe këto 2 do të jetë 2 dhe këto 2 do të jetë 2 dhe këto 2 do të jetë 2,
kështu nëpër të gjitha bashkon që ne duhet të bëjmë, ne deri në fund duke bërë n.
Si 2 + 2 + 2 + 2 është 8, e cila është n,
kështu që kostoja e bashkimit në këtë grup është n.
Dhe pastaj e njëjta gjë këtu.
Ne do të bashkojë këto 2, atëherë këto 2, dhe individualisht ky bashkojë do të marrin katër operacione,
kjo do të bashkojë katër operacionet, por edhe një herë, në mes të gjitha këto,
deri ne fund bashkimin n gjërat totale, dhe kështu ky hap i merr n.
Dhe kështu çdo nivel merr elemente n duke u shkrirë.
>> Dhe sa nivelet janë atje?
Në çdo nivel, array ynë rritet me madhësinë e 2.
Këtu vargjeve tona janë të një madhësie 1, këtu ata janë të madhësisë 2, këtu ata janë të madhësisë 4,
dhe më në fund, ata janë të madhësisë 8.
Kështu që ajo është dyfishuar, nuk do të jetë një total prej log n nga këto nivele.
Pra, me log n nivele, secili nivel individual marrë n operacionet në total,
ne kemi marrë një log n n algorithm.
Pyetje?
Kanë njerëzit tashmë e bërë përparim në mënyrën se si për të zbatuar këtë?
Është dikush tashmë në një shtet ku unë mund vetëm të tërheqë deri kodin e tyre?
Unë mund të jap një minutë.
Ky i fundit do të jetë më e gjatë.
I highly recommend përsëritet -
Ju nuk keni për të bërë recursion për bashkimin
sepse për të bërë recursion për bashkimin, ju jeni do të duhet të kalojë një bandë e madhësive të ndryshme.
Ju mund, por kjo është i bezdisshëm.
Por për recursion lloj vetë është shumë e lehtë.
Ju vetëm fjalë thirrje lloj në gjysmën e majtë, në gjysmën lloj djathtë. Rregull.
Çdokush keni ndonjë gjë që unë mund të tërheqë deri akoma?
Ose tjetër unë do të jap një minutë.
Rregull.
Çdokush ka diçka që ne mund të punojnë me të?
Apo tjetër ne do të punojnë vetëm me këtë dhe pastaj të zgjerohet nga atje.
>> Çdokush kanë më shumë se kjo që unë mund të tërheqë deri?
[Student] Yeah. Ju mund të tërheqë deri minave. >> All drejtë.
Po!
[Student] Ka qenë një shumë të kushteve. >> Oh, xhiruar. Mund të ju -
[Student] Unë duhet të ruani atë. Po >>.
Pra, ne e bëmë të bëjë bashkim veçmas.
Oh, por kjo nuk është edhe aq keq.
Rregull.
Kështu renditjes në vetvete është vetëm duke e quajtur mergeSortHelp.
Na shpjegojë se çfarë mergeSortHelp bën.
[Student] MergeSortHelp pretty much bën dy hapa kryesorë,
e cila është për të zgjidhur çdo gjysmën e grup dhe pastaj të bashkojë dy prej tyre.
[Bowden] Mirë, kështu që jepni një të dytë.
Unë mendoj se kjo - >> [Student] Unë kam nevojë për të -
Po. Unë jam humbur diçka.
Në bashkimin, e kuptoj se kam nevojë për të krijuar një grup të ri
sepse unë nuk mund të bëjë atë në vend. Po >>. Ju nuk mundeni. Korrigjuar.
[Student] Kështu që unë krijuar një koleksion të ri.
I harruar në fund të bashkohen për të ri-ndryshuar.
Rregull. Ne kemi nevojë për një koleksion të ri.
Në lloj të bashkojë, kjo është pothuajse gjithmonë e vërtetë.
Pjesë e kostos së një algoritmi të mirë kohë i mençur
është pothuajse gjithmonë kanë nevojë për të përdorur memorie pak më shumë.
Kështu që këtu, pa marrë parasysh se si ju bëni bashkojë lloj,
ju do të duhet të përdorni në mënyrë të pashmangshme disa memorie ekstra.
Ai ose ajo ka krijuar një koleksion të ri.
Dhe pastaj ju thoni në fund, ne vetëm duhet të kopjoni koleksion të ri në rrjet origjinal.
[Student] Unë mendoj kështu, yeah.
Unë nuk e di nëse që punon në drejtim të numëruar duke iu referuar apo çfarëdo -
Po, ajo do të punojë. >> [Student] Okay.
A ju provoni drejtimin kjo? >> [Student] Jo, jo ende. Mirë >>.
Provoni drejtimin e tij, dhe pastaj unë do të flas në lidhje me atë për një të dytë.
[Student] Unë duhet të ketë të gjitha prototypes funksion dhe gjithçka, edhe pse, apo jo?
Të prototypes funksion. Oh, ju do të thotë si - Po.
Rendit është duke bërë thirrje mergeSortHelp.
>> Pra, në mënyrë për të thirrur lloj mergeSortHelp, mergeSortHelp duhet ose janë përcaktuar
para lloj ose ne duhet vetëm prototip. Thjesht kopjoni dhe ngjisni këtë.
Dhe në mënyrë të ngjashme, mergeSortHelp është duke bërë thirrje shkrihen,
por bashkojë nuk është përcaktuar ende, kështu që ne mund vetëm le mergeSortHelp e di
se kjo është ajo që do të bashkojë të duken si, dhe kjo është se.
Pra mergeSortHelp.
Ne kemi një problem këtu ku kemi asnjë rast bazë.
MergeSortHelp është recursive, kështu që çdo funksion recursive
do të ketë nevojë për një lloj të rastit bazë të dinë se kur do të ndalet Recursively quan veten.
Çfarë është rasti ynë bazë do të jetë këtu? Po.
[Student] Nëse madhësia është 1? >> [Bowden] Po.
Pra, si e pamë të drejtë atje, ne ndaluam vargjeve ndarjen
sapo kemi marrë në vargjeve të madhësisë 1, i cili në mënyrë të pashmangshme janë të renditura veten.
Pra, nëse madhësia e barabartë me 1, ne e dimë array është renditur tashmë,
kështu që ne vetëm mund të kthehen.
>> Vini re se kjo është e pavlefshme, kështu që ne nuk do të kthehen asgjë të veçantë, ne vetëm të kthehen.
Rregull. Pra, kjo është rasti ynë bazë.
I guess rastin tonë bazë mund të jetë edhe në qoftë se ne të ndodhë të bashkimit një rrjet të madhësisë 0,
ne ndoshta doni të ndaluar në një pikë,
kështu që ne mund të them vetëm madhësinë më pak se 2 ose më pak se ose e barabartë me 1
kështu që kjo do të punojë për çdo grup tani.
Rregull.
Pra, kjo është rasti ynë bazë.
Tani ju doni të ecni ne nëpërmjet bashkimin?
Çfarë do të thotë të gjitha këto raste?
Deri këtu, ne jemi vetëm duke bërë të njëjtën ide, -
[Student] Unë duhet të kalojnë madhësinë me të gjitha thirrjet mergeSortHelp.
Kam shtuar madhësinë si një paraprake shtesë dhe kjo nuk është atje, si madhësi / 2.
[Bowden] Oh, madhësia / 2, madhësia / 2. >> [Student] Yeah, dhe gjithashtu në funksionin e mësipërm si.
[Bowden] Ketu? >> [Student] Vetëm size. >> [Bowden] Oh. Size, madhësia? >> [Student] Yeah.
[Bowden] Okay.
Më lejoni të mendoj për një të dytë.
A kemi drejtuar në një çështje?
Ne jemi gjithmonë trajtimin e lënë si 0. >> [Student] Nr
Kjo është gabim shumë. Më vjen keq. Ajo duhet të jetë fillimi. Po.
[Bowden] Okay. Më pëlqen më mirë.
Dhe në fund. Rregull.
Kështu që tani ju doni të ecni ne nëpërmjet bashkimin? >> [Student] Okay.
Unë jam vetëm duke ecur nëpër këtë grup të ri që unë kam krijuar.
Madhësia e saj është madhësia e pjesës së grup që ne duam të jenë të renditura sipas
dhe duke u përpjekur për të gjetur element që unë duhet të vënë në hapin array ri.
Pra, për të bërë këtë, së pari unë jam duke kontrolluar nëse gjysma e majtë të array vazhdon të ketë elemente të ndonjë më shumë,
dhe në qoftë se nuk e bën, atëherë ju shkoni poshtë në atë gjendje tjetër, i cili sapo thotë
rregull, ajo duhet të jetë në rrjet të drejtë, dhe ne do të vendos se në indeksin aktual të newArray.
>> Dhe pastaj ndryshe, unë jam duke kontrolluar nëse pala e drejta e array është përfunduar edhe,
në të cilin rast unë vetëm vënë në të majtë.
Kjo nuk mund të vërtetë të jetë e nevojshme. Nuk jam i sigurt.
Por, gjithsesi, të tjera dy kontrolloni se cili prej dy janë më të vogla në të majtë apo të djathtë.
Dhe në secilin rast, unë jam i bën rritjen cilado placeholder I ardhura.
[Bowden] Okay.
Që duket e mirë.
Ka njeri të ketë komente ose pyetje ose shqetësime?
Pra katër raste që kemi për të sjellë gjërat në vetëm duke qenë - ose ajo që duket si pesë -
por ne duhet të marrin në konsideratë nëse array majtë është drejtuar nga gjërat që ne duhet të shkrihen,
nëse array drejtë është drejtuar nga gjërat që ne duhet të bashkojë -
Unë jam vënë në asgjë.
Pra, nëse array majtë është drejtuar nga gjëra apo array drejtë është drejtuar nga gjëra.
Këto janë dy raste.
Ne gjithashtu duhet rastin parëndësishëm e nëse gjëja e majtë është më pak se gjëja e duhur.
Atëherë ne duam të zgjedhin gjënë e majtë.
Ata janë raste.
Pra, kjo ishte e drejtë, kështu që kjo është ajo.
Array majtë. Ajo është 1, 2, 3. Rregull. Pra, vërtet, këto janë katër gjëra që ne mund të dëshironi të bëni.
Dhe ne nuk do të shkoj për një përsëritës zgjidhje.
Unë nuk do të rekomandojë -
Merge lloj është një shembull i një funksion që është edhe mos bisht rekursive,
kjo nuk është e lehtë për ta bërë atë bisht rekursive,
por edhe kjo nuk është shumë e lehtë për ta bërë atë përsëritës.
Kjo është shumë e lehtë.
Ky lloj zbatimi i bashkojë,
bashkojë, pa marrë parasysh atë që ju bëni, ju do të jeni për të ndërtuar bashkohen.
>> Pra bashkojë lloj ndërtuar në majë të bashkohen Recursively është vetëm këto tri linja.
Iteratively, ajo është më shumë i bezdisshëm dhe më të vështirë për të menduar.
Por vini re se kjo nuk është bishti rekursive që mergeSortHelp - kur e quan veten -
ajo ende ka nevojë për të bërë gjëra, pasi ky kthim thirrjes gjithkund rekursive.
Pra, kjo kornizë rafte duhet të vazhdojë të ekzistojë edhe pas kësaj thirrje.
Dhe pastaj kur ju telefononi këtë, korniza rafte duhet të vazhdojë të ekzistojë
sepse edhe pas kësaj telefonate, ne ende nevojë për të bashkojë.
Dhe kjo është jo banale për të bërë këtë bisht rekursive.
Pyetje?
Dakord.
Pra, duke shkuar prapa për të zgjidhur - oh, ka dy gjëra që unë dua për të treguar. Rregull.
Going back to lloj, ne do të bëjmë këtë shpejt.
Ose search. Rendit? Rendit. Po.
Going back to fillimet e lloji.
Ne duam të krijojmë një algoritmi që llojet rrjet duke përdorur ndonjë algorithm
O në të n.
Pra, si është kjo e mundur? A ka dikush ndonjë lloj -
I la të kuptohej më parë në -
Nëse ne jemi gati për të përmirësuar nga n log n për O n,
ne kemi përmirësuar algorithm tonë kohë i mençur,
që do të thotë se çfarë jemi ne do të duhet të bëni për të bërë për këtë?
[Student] hapësirë. Po >>. Ne jemi duke shkuar për të përdorur më shumë hapësirë.
Dhe jo edhe vetëm më shumë hapësirë, kjo është hapësirë ​​në mënyrë eksponenciale më shumë.
Kështu që unë mendoj se kjo lloj algoritmi është diçka pseudo, pseudo polynom -
pseudo - Unë nuk mund të kujtohet. Diçka pseudo.
Por kjo është për shkak se ne kemi nevojë që të përdorin hapësirën aq shumë
se kjo është e arritshme, por jo realiste.
>> Dhe si nuk kemi arritur këtë?
Ne mund të arrijmë këtë nëse kemi të garantuar se çdo element i veçantë në rrjet
është nën një madhësi të caktuar.
Pra, le të them vetëm se madhësia është 200,
çdo element në një grup është nën madhësia 200.
Dhe kjo në fakt është shumë realiste.
Ju mund shumë lehtë të ketë një rrjet që ju e dini çdo gjë në të
do të jetë më pak se një numër.
Ashtu si në qoftë se ju keni disa vektor absolutisht masiv apo diçka
por ju e dini çdo gjë do të jetë midis 0 dhe 5,
atëherë ajo do të jetë dukshëm më të shpejtë për të bërë këtë.
Dhe lidhur në ndonjë prej elementeve është 5,
kështu që kjo detyruar, që është sa memorie ju jeni do të jetë duke përdorur.
Pra detyruar është 200.
Në teori nuk është gjithmonë një i detyruar që një numër i plotë mund të jetë vetëm deri në 4 miliardë,
por kjo është joreale që atëherë ne do të jetë duke përdorur hapësirë
në mënyrë të 4 miliardë. Pra, kjo është joreale.
Por këtu ne do të themi lidhur ynë është 200.
Mashtrim për të bërë atë në të O n është që ne të bëjë një tjetër grup të quajtur akuza të madhësisë lidhur.
Pra në fakt, kjo është një shkurtore për - Unë në fakt nuk e di nëse tingëllimë e bën këtë.
Por në GCC, në shumë pak - tingëllimë Jam duke supozuar e bën atë shumë -
kjo thjesht do të nisja array gjithë të jenë 0s.
Pra, nëse unë nuk dua të bëj këtë, atëherë unë mund të bëj për vete (int i = 0;
i <LIDHUR; i + +) dhe akuza [i] = 0;
Deri tani çdo gjë është nisur në 0.
Unë iterate mbi array tim,
dhe atë që unë jam duke bërë është që unë jam duke numëruar numrin e njëri - Le të shkojnë poshtë këtu.
Ne kemi 4, 15, 16, 50, 8, 23, 42, 108.
Ajo që unë jam duke numëruar është numri i dukurive të secilit prej këtyre elementeve.
Le të vërtetë të shtoni një çift shumë në këtu me disa përsërit.
Pra, vlera e kemi këtu, vlera e që do të jetë array [i].
Pra, mund të jetë val 4 apo 8 apo çfarëdo.
Dhe tani unë jam duke numëruar se sa i atij vlerën që unë kam parë,
kështu akuza [val] + +;
Pas kësaj është bërë, akuza do të shikojmë diçka si 0001.
Le të bëjmë akuza [val] - BOUND + 1.
>> Tani që është vetëm për të llogari për faktin se ne jemi duke filluar nga 0.
Pra, nëse 200 do të jetë numri ynë më i madh,
pastaj 0-200 është 201 gjëra.
Pra akuza, ajo do të duket si 00.001, sepse ne kemi një 4.
Atëherë ne do të kemi 0001 ku ne do të kemi një 1 në indeksin e 8 e numërimit.
Ne do të kemi një 2 në indeksin e 23-të numërimit.
Ne do të kemi një 2 në indeksin e 42-numërimin.
Kështu që ne mund të përdorni numërimin.
Pra num_of_item = numëron [i].
Dhe kështu që nëse num_of_item është 2, që do të thotë që ne duam të futur 2 e numrit i
në grup tonë të renditura.
Pra, ne kemi nevojë për të mbajtur gjurmët e sa larg jemi në grup.
Pra, indeksi = 0.
Array - Unë vetëm do të shkruaj atë.
Pikat -
array [Indeksi + +] = i;
Është se ajo që unë dua? Unë mendoj se kjo është ajo që unë dua.
Po, kjo duket e mirë. Rregull.
Pra, ka të gjithë e kuptojnë se çfarë qëllimi i im është akuza grup?
Ajo është duke numëruar numrin e dukurive të secilit prej këtyre numrave.
Atëherë unë jam iterating mbi këtë koleksion akuza,
dhe pozita ith në rrjet akuza
është numri i kam e që duhet të paraqiten në grup tim renditura.
Kjo është arsyeja pse akuza e 4 do të jetë 1
dhe akuza të 8 do të jetë 1, akuza për 23 do të jetë 2.
Pra, kjo është se si shumë prej tyre unë dua për të futur në rrjet tim renditura.
Atëherë unë vetëm të bëjë këtë.
Unë jam futur num_of_item unë është në rrjet tim renditura.
>> Pyetje?
Dhe kështu përsëri, kjo është koha lineare pasi ne jemi vetëm iterating mbi këtë herë,
por gjithashtu edhe në atë linear ky numër ndodh që të jetë,
dhe kështu që shumë varet nga ajo detyruar juaj.
Me një kufi të 200, që nuk është edhe aq keq.
Nëse detyruar juaj do të jetë 10.000, atëherë kjo është pak keq,
por në qoftë se lidhur juaj do të jetë 4 miliardë dollarë, që është tërësisht joreale
dhe ky grup do të duhet të jetë e madhësisë 4 miliardë, e cila është joreale.
Pra, kjo është se. Pyetje?
[Përgjigja e padëgjueshme Student] >> Okay.
Kam kuptuar një gjë tjetër, kur ne ishim duke kaluar.
Unë mendoj se problemi ishte në të Lukas dhe ndoshta çdo një të vetme kemi parë.
Unë plotësisht harruar.
E vetmja gjë që kam kërkuar për të komentuar në është se kur ju jeni që kanë të bëjnë me gjëra të tilla si indekse,
ju kurrë nuk e shohin këtë të vërtetë, kur ju jeni duke shkruar një për lak,
por teknikisht, kur ju jeni që kanë të bëjnë me këto indekse,
ju duhet të pretty much gjithmonë të merren me integers panënshkruara.
Arsyeja për këtë është kur ju jeni që kanë të bëjnë me integers nënshkruara,
kështu që nëse ju keni 2 integers nënshkruar dhe ju shtoni ato së bashku
dhe ata përfundojnë shumë i madh, atëherë ju përfundojnë me një numër negativ.
Pra, kjo është ajo që del nga shtrati është numër i plotë.
>> Nëse unë shtoni 2000000000 dhe 1000000000, unë deri në fund me 1 miliard negativ.
Kjo është se si integers punojnë në kompjuter.
Pra, problemi me përdorimin e -
Kjo është në rregull, përveç nëse ndodh të jetë i ulët 2 miliardë dhe deri ndodh të jetë 1 miliard,
atëherë kjo do të jetë 1 miliard negative dhe pastaj ne jemi duke shkuar për të ndarë që nga 2
dhe përfundojnë me 500 milionë negativ.
Pra, kjo është vetëm një çështje, nëse ju ndodh që të jetë në kërkim përmes një sërë
prej miliarda gjërave.
Por nëse ndodh + ulët deri të fryhen, atëherë kjo është një problem.
Sapo kemi bërë ato unsigned, pastaj 2 miliardë plus 1 miliard është 3 miliard dollarë.
3 miliardë ndarë nga 2 është 1.5 miliard dollarë.
Pra, sa më shpejt që ata janë të panënshkruara, çdo gjë është e përsosur.
Dhe kështu kjo është gjithashtu një çështje kur ju jeni shkrim tuaja për sythe,
dhe në fakt, kjo ndoshta e bën atë automatikisht.
Kjo në fakt do vetëm bërtasin në ju.
Pra, nëse ky numër është shumë e madhe që të jetë në një numër të plotë vetëm, por kjo do të përshtatet në një numër të plotë panënshkruar,
ajo do të bërtas me ju, kështu që kjo është arsyeja pse nuk ju drejtuar të vërtetë në këtë çështje.
Ju mund të shihni se një indeks kurrë nuk do të jetë negative,
dhe kështu kur ju jeni iterating mbi një rrjet,
ju mund të pothuajse gjithmonë thonë unsigned int i, por ju nuk duhet të vërtetë kanë për të.
Gjërat po shkojnë të punojnë goxha shumë po aq mirë.
Rregull. [Pëshpërit] Sa është ora?
Gjëja e fundit që kam kërkuar për të treguar - dhe unë vetëm do të bëjë atë me të vërtetë të shpejtë.
Ju e dini se si ne kemi # define kështu që ne mund të përcaktojë # MAX si 5 apo diçka?
Le të mos bëjmë MAX. # Define obligohemi si 200. Kjo është ajo që ne e bëmë më parë.
Që përcakton një konstante, e cila është vetëm do të kopjohet dhe ngjit
kudo që të ndodhë për të shkruar lidhur.
>> Pra, ne në fakt mund të bëjë më shumë me # përcakton.
Ne mund të përcaktojë funksionet #.
Ata nuk janë me të vërtetë funksionon, por ne do të thërrasë ato funksione.
Një shembull do të jetë diçka si MAX (x, y) është definuar si (x <y y:? X). Rregull.
Kështu që ju duhet të merrni përdorur për të sintaksës operator tresh,
por është më pak se x y? Kthehu y, x kthehen tjetër.
Kështu që ju mund të shihni që ju mund të bëni këtë një funksion të veçantë,
dhe funksioni mund të jetë si bool MAX merr 2 argumente, kthehet këtë.
Kjo është një nga ato më të zakonshme unë shoh bërë si kjo. Ne i quajmë ato macros.
Kjo është një makro.
Kjo është vetëm sintaksë për të.
Ju mund të shkruani një makro për të bërë çdo gjë që ju dëshironi.
Ju shpesh shohim macros për debugging printfs dhe sende.
Pra, një lloj i printf, nuk janë konstante të veçanta në C si underscore LINE nënvizojnë,
2 nënvizon LINE nënvizojnë,
dhe ka edhe mendoj 2 nënvizon funk. Kjo mund të jetë ajo. Diçka të tillë.
Këto gjëra do të zëvendësohet me emrin e funksionit
ose numrin e linjës që ju jeni në.
Shpesh, ju shkruani printfs debugging që këtu poshtë atëherë unë mund të shkruani vetëm
Korrigjoj dhe ajo do të shtypura numrin e linjës dhe funksionin që unë të ndodhë të jetë në
se ajo ka hasur atë deklaratë korrigjoj.
Dhe ju gjithashtu mund të shkruar gjëra të tjera.
Pra, një gjë që ju duhet të shikojnë për të është në qoftë se unë të ndodhë për # define DOUBLE_MAX
si diçka si 2 * y dhe 2 * x.
Pra, për arsye çfarëdo, ju ndodh për ta bërë këtë shumë.
Kështu që e bëjnë atë një makro.
Kjo është thyer në të vërtetë.
Unë do ta quaja atë duke bërë diçka të tillë DOUBLE_MAX (3, 6).
Pra, çfarë duhet të kthehen?
[Student] 12.
Po, 12 duhet të kthehen, dhe 12 është kthyer.
3 merr zëvendësohet për x, 6 merr zëvendësohet për y, dhe ne kthim 2 * 6, e cila është 12.
Tani çfarë në lidhje me këtë? Çfarë duhet të kthehen?
[Student] 14. Idealisht >>, 14.
Çështja është se si hash përcakton punën, mos harroni se kjo është një kopje e saktë dhe paste
çdo gjë shumë e shumë, kështu që çfarë kjo do të interpretohet si
është 3 më pak se 1 plus 6, 2 herë 1 plus 6, 2 herë 3.
>> Pra, për këtë arsye ju pothuajse gjithmonë të përfundojë çdo gjë në kllapa.
Çdo ndryshore ju pothuajse gjithmonë të përfundojë në kllapa.
Ka raste ku ju nuk keni për të, ashtu si unë e di se unë nuk duhet të bëni se këtu
sepse më pak se është shumë e shumë të gjithmonë vetëm të shkojnë në punë,
edhe pse kjo mund të mos jetë edhe e vërtetë.
Nëse ka diçka qesharake si DOUBLE_MAX (1 == 2),
atëherë kjo do të merrni zëvendësohet me 3 më pak se 1 barabartë barabartë me 2,
dhe kështu, atëherë kjo do të bëjë 3 më pak se 1, bën që 2 të barabartë,
e cila nuk është ajo që ne duam.
Kështu që në mënyrë për të parandaluar ndonjë problem operatorit përparësi,
gjithmonë të përfundojë në kllapa.
Rregull. Dhe kjo është ajo, 05:30.
Nëse keni ndonjë pyetje në pset, le të na njohin.
Ajo duhet të jetë kënaqësi, dhe edicioni hacker gjithashtu është shumë më realiste
se edicionin e hacker të vitit të kaluar, kështu që ne shpresojmë se shumë prej jush të përpiqen atë.
Vitin e kaluar ishte shumë e madhe.
>> [CS50.TV]