[Powered by Google Translate] [Afsnit 3 - Mere behagelig]
[Rob Bowden - Harvard University]
>> [Dette er CS50. - CS50.TV]
>> Så det første spørgsmål er mærkeligt formuleret.
GDB lader dig "debug" et program, men mere specifikt, hvad betyder det lade dig gøre?
Jeg vil svare, at én, og jeg ved ikke, hvad der præcist forventet,
så jeg gætte det er noget i retning af det lader dig trin for trin
gå gennem programmet, interagere med det, ændre variabler, gøre alle disse ting -
dybest set fuldstændigt styre udførelsen af ​​et program
og inspicere enhver given del af gennemførelsen af ​​programmet.
Så disse funktioner kan du debug ting.
Okay.
Hvorfor binær søgning kræver, at et array skal sorteres?
Hvem ønsker at besvare dette?
[Studerende] Da det ikke virker, hvis det ikke er sorteret. >> Yeah. [Latter]
Hvis det ikke er sorteret, så det er umuligt at splitte det på midten
og vide, at alt til venstre er mindre og alt til højre
er større end den midterste værdi.
Så det skal sorteres.
Okay.
Hvorfor er boble slags i O n kvadreret?
Er der nogen først ønsker at give en meget hurtig på højt niveau overblik over, hvad boble slags er?
[Studerende] Du dybest set gå gennem hvert element, og du tjekke de første par elementer.
Hvis de er ude, hvor du bytte dem, så du tjekke de næste par elementer og så videre.
Når du når til slutningen, så du ved, at det største element er placeret i slutningen,
så du ignorere, at man så skal du holde på går igennem,
og hver gang du er nødt til at kontrollere en mindre element indtil du foretager nogen ændringer. >> Yeah.
Det hedder boble slags, fordi hvis du spejlvende array på sin side, så det er op og ned, lodret,
så de store værdier vil synke til bunds, og de små værdier vil boble op til toppen.
Det er, hvordan det fik sit navn.
Og ja, du bare gå igennem.
Du holde ud gennem opstillingen, bytte større værdi
at få de største værdier til bunden.
>> Hvorfor er det O n kvadreret?
Først er der nogen ønsker at sige, hvorfor det er O n kvadreret?
[Studerende] Fordi for hver kørsel det går n gange.
Du kan kun være sikker på, at du har taget det største element hele vejen ned,
så er du nødt til at gentage, at så mange elementer. >> Yeah.
Så huske på, hvad big O betyder, og hvad store Omega betyder.
Den store O er ligesom den øvre grænse for, hvor langsomt det faktisk kan køre.
Så ved at sige det er O n kvadreret, er det ikke O n ellers ville være i stand til at køre
i lineær tid, men det er O n kubik
fordi den er afgrænset af O n cubed.
Hvis det er afgrænset af O n kvadreret, så er det afgrænset også af n kubik.
Så det er n kvadreret, og i den absolutte værste fald kan det ikke gøre det bedre end n kvadreret,
hvilket er hvorfor det er O i n potens.
Så for at se lidt matematik på, hvordan det kommer ud at være n kvadreret,
hvis vi har fem ting i vores liste, den første gang, hvor mange swaps kunne vi potentielt nødt til at gøre
med henblik på at få dette? Lad os faktisk bare -
Hvor mange swaps skal vi nødt til at gøre i den første kørsel af boble sortere gennem array?
[Studerende] n - 1. >> Yeah.
>> Hvis der er 5 elementer, vi vil få brug for at gøre n - 1.
Så på den anden, hvor mange swaps skal vi nødt til at gøre?
[Studerende] n - 2. >> Yeah.
Og den tredje vil være n - 3 og derefter for nemheds jeg vil skrive de sidste to
som dengang vil vi nødt til at gøre 2 swaps og 1 swap.
Jeg gætte den sidste måske eller måske ikke rent faktisk skal ske.
Er det en swap? Det ved jeg ikke.
Så dette er det samlede beløb af swaps eller i det mindste sammenligninger du har at gøre.
Selv hvis du ikke bytte, har du stadig nødt til at sammenligne værdierne.
Så der er n - 1 sammenligninger i den første kørsel gennem opstillingen.
Hvis du omarrangere disse ting, lad os rent faktisk gøre det seks ting, så tingene stak op pænt,
og så vil jeg gøre 3, 2, 1.
Så bare omarrangere disse beløb, vi ønsker at se, hvor mange sammenligninger vi gør
i hele algoritme.
Så hvis vi bringer disse fyre hernede,
så er vi stadig lige summere dog mange sammenligninger der var.
Men hvis vi opsummere disse og vi opsummere disse og vi opsummere disse,
det er stadig det samme problem. Vi har lige opsummere disse særlige grupper.
>> Så nu er vi summere 3 n er. Det er ikke bare 3 n er.
Det er altid vil være n / 2 n s.
Så her har vi tilfældigvis har 6.
Hvis vi havde 10 ting, så vi kunne gøre denne gruppering for 5 forskellige par ting
og ender med n + n + n + n + n.
Så du altid vil få n / 2 n s, og så dette vil vi notere det ud til n squared / 2.
Og så selvom det er den faktor af halvdelen, der sker for at komme i
på grund af det faktum, at ved hver iteration over arrayet vi sammenligner en mindre
så det er, hvordan vi får mere end 2, men det er stadig n potens.
Vi er ligeglade med den konstante faktor af en halv.
Så en masse af stor O ting som dette beror på bare lidt at gøre denne form for matematik,
laver aritmetiske beløb og kvotientrække kram,
men de fleste af dem i dette kursus er temmelig ligetil.
Okay.
Hvorfor er indsættelse slags i Omega n? Hvad betyder omega betyde?
[To studerende taler på én gang - uforståelige] >> Yeah.
Omega du kan tænke på som den nedre grænse.
>> Så uanset hvor effektiv din indsættelse slags algoritme er,
uanset den liste, der er gået i, det altid har at sammenligne mindst n ting
eller det skal gentage over n ting.
Hvorfor er det?
[Studerende] Fordi hvis listen allerede er sorteret, så gennem den første iteration
du kan kun garantere, at det allerførste element er mindst,
og den anden iteration du kan kun garantere de første to er
fordi du ikke ved, at resten af ​​listen er sorteret. >> Yeah.
Hvis du passerer i en helt sorteret liste, i det mindste du nødt til at gå over alle de elementer,
at se, at intet skal flyttes rundt.
Så passerer hen over listen og siger åh, dette allerede sorteret,
det er umuligt for dig at vide det er sorteret, indtil du tjekker hvert element
at se, at de er i sorteret orden.
Så den nedre grænse på indsættelse slags er Omega n.
Hvad er det værste tilfælde køretid for merge slags,
worst case er store O igen?
Så i værste fald, hvordan merge sort kører?
[Studerende] N log n. >> Yeah.
De hurtigste generelle sortering algoritmer er n log n. Du kan ikke gøre det bedre.
>> Der er særlige tilfælde, og hvis vi har tid i dag - men vi sandsynligvis won't -
vi kunne se en, der gør bedre end n log n.
Men i det generelle tilfælde, kan du ikke gøre det bedre end n log n.
Og fusionere slags sker for at være den, du skal vide for dette kursus, der er n log n.
Og så vil vi faktisk gennemføre det i dag.
Og endelig, i højst tre sætninger, hvordan virker udvælgelse sort arbejde?
Er der nogen ønsker at besvare, og jeg vil tælle dine sætninger
fordi hvis du går over 3 -
Er der nogen huske udvælgelse slags?
Selection slags er normalt temmelig nemt at huske lige fra navnet.
Du skal bare gentage over opstillingen, finde, hvad den største værdi er eller mindste -
uanset rækkefølge, du sortere i.
Så lad os sige vi sortering fra den mindste til største.
Du gentage over opstillingen, søger uanset minimum element er,
vælg det, og så bare bytte det, hvad der er i første omgang.
Og så på den anden passage over array, kigge efter den mindste element igen,
vælge den og derefter bytter den med hvad der er i den anden position.
Så vi er bare plukke og vælge de minimumsværdier
og indsætte dem i den forreste del af arrayet, indtil det sorteres.
Spørgsmål om det?
>> Disse uundgåeligt forekommer i de former du skal udfylde, når du indsender Pset.
Det er dybest set svarene på dem.
Okay, så nu kodning problemer.
Jeg har allerede sendt ud via e-mail - Har nogen ikke få denne e-mail? Okay.
Jeg har allerede sendt ud via e-mail den plads, vi skal bruge,
og hvis du klikker på mit navn - så jeg tror, ​​jeg har tænkt mig at være nederst
på grund af den baglæns r - men hvis du klikker på mit navn vil du se 2 revisioner.
Revision 1 vil blive jeg allerede kopieret og indsat koden i Spaces
for søgning ting du bliver nødt til at gennemføre.
Og Revision 2 vil være den slags ting, vi gennemfører efter det.
Så du kan klikke på min Revision 1 og arbejde derfra.
Og nu ønsker vi at implementere binær søgning.
>> Er der nogen bare ønsker at give en pseudokode højt plan forklaring
af, hvad vi er nødt til at gøre for søgning? Yeah.
[Studerende] Du skal bare tage midten af ​​arrayet og se, om det, du leder efter
er mindre end eller mere end det.
Og hvis det er mindre, skal du gå til den halvdel, der er mindre,
og hvis det er mere, du går til den halvdel, der er mere og du gentage det, indtil du bare én ting.
[Bowden] Yeah.
Bemærk, at vores numre opstilling allerede er sorteret,
og så betyder, at vi kan drage fordel af det, og vi kunne først tjekke,
okay, jeg leder efter tallet 50.
Så jeg kan gå ind i midten.
Middle er svært at definere, hvornår det er en endnu flere ting,
men lad os bare sige, vi vil altid afkorte til midten.
Så her har vi 8 ting, så den midterste ville være 16.
Jeg leder efter 50, så 50 er større end 16.
Så nu kan jeg dybest set behandle min array som disse elementer.
Jeg kan smide væk alt fra 16 over.
Nu er mit array er netop disse 4 elementer, og jeg gentager.
Så da jeg ønsker at finde i midten igen, som kommer til at være 42.
42 er mindre end 50, så jeg kan smide disse to elementer.
Dette er min resterende array.
Jeg har tænkt mig at finde midten igen.
Jeg gætter 50 var et dårligt eksempel, fordi jeg altid var at smide ting til venstre,
men ved den samme foranstaltning, hvis jeg leder efter noget
og det er mindre end det element, jeg i øjeblikket kigger på,
så jeg har tænkt mig at smide alt til højre.
Så nu er vi nødt til at gennemføre det.
Bemærk, at vi er nødt til at passere i størrelse.
Vi kan også ikke at hard-code format.
Så hvis vi slippe af med det # define -
Okay.
Hvordan kan jeg pænt regne ud, hvad størrelsen af ​​numre arrayet øjeblikket er?
>> Hvor mange elementer er i numrene array?
[Studerende] Numbers, beslag,. Længde?
[Bowden], der ikke findes i C.
Behov. Længde.
Arrays ikke har egenskaber, så der er ingen længden ejendom arrays
der vil bare give dig uanset hvor længe det sker for at være.
[Studerende] Se hvor meget hukommelse det har og dividere med hvor meget - >> Yeah.
Så hvordan kan vi se, hvor meget hukommelse det har? >> [Studerende] sizeof. >> Ja, sizeof.
Sizeof er operatør, der kommer til at returnere størrelsen af ​​numre array.
Og det kommer til at være uanset hvor mange heltal der er tidspunkter på størrelse med et heltal
da det er hvor meget hukommelse det er faktisk optage.
Så hvis jeg vil have antallet af ting i array,
så jeg har tænkt mig at vil opdele ved størrelsen af ​​et heltal.
Okay. Så det lader mig passere i størrelse her.
Hvorfor skal jeg nødt til at passere i størrelse på alle?
Hvorfor kan jeg ikke bare gøre op her int size = sizeof (høstak) / sizeof (int)?
Hvorfor er dette ikke virker?
[Studerende] Det er ikke en global variabel.
[Bowden] Haystack eksisterer, og vi passerer i antal som høstak,
og det er lidt af en forudanelse om, hvad der er at komme. Yeah.
[Studerende] Haystack er blot en henvisning til det, så det ville vende tilbage, hvor stor denne henvisning er.
Yeah.
Jeg tvivler på foredrag, som du har set stakken endnu virkelig, right?
Vi har lige talt om det.
Så stakken er hvor alle dine variabler vil blive gemt.
>> Enhver hukommelse, der er allokeret til lokale variabler går i stakken,
og hver funktion får sin egen plads på stakken, sin egen stakramme er, hvad det hedder.
Så main har sin stakramme, og inde i det vil eksistere dette tal array,
og det vil være af størrelse sizeof (tal).
Det kommer til at have størrelse af tal divideret med størrelsen af ​​elementer,
men at alle bor inden for main stak ramme.
Når vi kalder søgning, søge får sin egen stakramme,
sin egen plads til at gemme alle sine lokale variabler.
Men disse argumenter - så høstak er ikke en kopi af hele denne opstilling.
Vi videregiver ikke i hele systemet som en kopi i søgning.
Det bare passerer en henvisning til den pågældende array.
Så søg kan få adgang til disse numre gennem denne reference.
Det er stadig adgang til de ting, der lever inde i main er stakramme,
men dybest set, når vi kommer til pegepinde, som bør være snart,
dette er, hvad pegepinde er.
Pointers er blot henvisninger til ting, og du kan bruge pegepinde til at få adgang tingene
der er i andre ting "stakrammer.
Så selvom numre er lokal til vigtigste, vi kan stadig få adgang til det gennem denne pointer.
Men da det er bare en pointer, og det er bare en henvisning,
sizeof (høstak) blot returnerer størrelsen af ​​referencen selv.
Den returnerer ikke størrelsen af ​​de ting den peger mod.
Den returnerer ikke den faktiske størrelse af tal.
Og så dette ikke kommer til at virke, som vi ønsker det.
>> Spørgsmål om det?
Pointers vil være væk i betydeligt mere blodige detaljer i kommende uger.
Og det er grunden til en masse ting, som du ser, de fleste søge ting eller sortere ting,
de er næsten alle vil få brug for at tage den faktiske størrelse af array,
fordi i C, har vi ingen idé om, hvad størrelsen af ​​array er.
Du er nødt til manuelt at passere det i.
Og du kan ikke manuelt passere i hele systemet, fordi du blot passerer i referencen
og det kan ikke få den størrelse fra referencen.
Okay.
Så nu er vi ønsker at gennemføre, hvad der blev forklaret før.
Du kan arbejde på det i et minut,
og du behøver ikke at bekymre dig om at få alting perfekt 100% arbejder.
Bare skrive op den halve pseudokoden for, hvordan du mener, det burde virke.
Okay.
Ingen grund til at være helt færdig med dette endnu.
Men er der nogen føle sig godt tilpas med, hvad de har så langt,
som noget vi kan arbejde med sammen?
Er der nogen ønsker at arbejde frivilligt? Eller jeg vil tilfældigt vælge.
Det behøver ikke at være lige ved enhver foranstaltning, men noget vi kan ændre i en arbejdsgruppe tilstand.
[Studerende] Sure. >> Okay.
Så kan du spare en revision ved at klikke på det lille Gem ikonet.
Du Ramya, ikke? >> [Studerende] Yeah. >> [Bowden] Okay.
Så nu kan jeg se din revision og enhver kan trække op til revision.
Og her har vi - Okay.
Så Ramya gik med den rekursive løsning, som er absolut en gyldig løsning.
Der er to måder, du kan gøre dette problem.
Du kan enten gøre det iterativt eller rekursivt.
De fleste problemer, du støder på, der kan gøres rekursivt kan også gøres iterativt.
Så her har vi gjort det rekursivt.
>> Er der nogen ønsker at definere, hvad det vil sige at lave en funktion rekursiv?
[Studerende] Når du har en funktion kalder sig selv
og derefter kalde sig indtil det kommer ud med sand og sand. >> Yeah.
En rekursiv funktion er bare en funktion, som kalder sig selv.
Der er tre store ting, som en rekursiv funktion skal have.
Den første er selvfølgelig, det kalder sig.
Det andet er basisscenariet.
Så på et tidspunkt funktionen skal stoppe med at kalde sig selv,
og det er hvad base sag er for.
Så her ved vi, at vi skal stoppe, skal vi give op i vores søgen
når start er lig ende - og vi vil gå over, hvad det betyder.
Men endelig den sidste ting, der er vigtige for rekursive funktioner:
funktionerne eller anden måde skal henvende sig til basisscenariet.
Ligesom hvis du ikke faktisk opdaterer noget, når du gør det andet rekursivt kald,
hvis du bogstaveligt talt bare kalde funktionen igen med de samme argumenter
og ingen globale variable har ændret eller noget,
du vil aldrig nå den oprindelige sag, i hvilket tilfælde det er skidt.
Det vil være en uendelig løkke, og en stak overflow.
Men her ser vi, at opdateringen sker da vi opdaterer starte + ende / 2,
Vi opdaterer slutningen argument her, vi opdaterer start argument her.
Så i alle rekursive kald vi opdaterer noget. Okay.
Ønsker du at gå os gennem din løsning? >> Sure.
Jeg bruger SearchHelp så hver gang jeg gør dette funktionskald
Jeg har i starten af ​​hvor jeg leder efter i rækken, og enden
hvor jeg leder opstillingen.
>> På hvert trin, hvor det siger det er midt element, som er starten + ende / 2,
er, at lige til, hvad vi leder efter?
Og hvis det er, så vi fandt det, og jeg tror, ​​der bliver gået op indholdet af rekursion.
Og hvis det ikke er sandt, så kontrollerer vi, om denne midterste værdi af array er for stor,
i hvilket tilfælde ser vi på den venstre halvdel af opstillingen ved at gå fra start til midten indeks.
Og ellers gør vi i slutningen halvdel.
[Bowden] Okay.
Det lyder godt.
Okay, så et par ting, og faktisk, det er en meget højt niveau ting
at du aldrig bliver nødt til at vide for dette kursus, men det er sandt.
Rekursive funktioner, du altid hører, at de er en dårlig aftale
fordi hvis du rekursivt kalde dig selv for mange gange, får du stack overflow
siden, som jeg sagde før, hver funktion får sin egen stakramme.
Så hvert opkald af rekursive funktion får sin egen stakramme.
Så hvis du laver 1.000 rekursive kald, du får 1.000 stakrammer,
og hurtigt du fører til at have alt for mange stakrammer og ting bare bryde.
Så det er derfor rekursive funktioner er generelt dårlig.
Men der er en nice delmængde af rekursive funktioner kaldet hale-rekursive funktioner,
og dette sker for at være et eksempel på en, hvor hvis compileren opdager dette
og det burde, tror jeg - i Dunk hvis du passerer det-O2 flag
så det vil bemærke dette er halerekursive og gøre tingene godt.
>> Det vil genbruge den samme stakramme igen og igen for hver rekursivt kald.
Og så fordi du bruger den samme stakramme, behøver du ikke at bekymre dig om
nogensinde stable overfyldte, og på samme tid, som du sagde før,
hvor når du returnere sandt, så er det nødt til at returnere op alle disse stakrammer
og 10. opkald til SearchHelp skal vende tilbage til 9., er at gå tilbage til det 8..
Så det behøver ikke at ske, når funktioner er halerekursive.
Og så hvad gør denne funktion halerekursive er opmærksom på, at for en given indkaldelse til searchHelp
den rekursive kald at det gør er, hvad det er at vende tilbage.
Så i den første indkaldelse til SearchHelp, vi enten umiddelbart returnere falsk,
straks returnere sandt, eller vi laver en rekursiv opkald til SearchHelp
hvor hvad vi vender tilbage er, hvad som opkaldet er tilbage.
Og vi kunne ikke gøre det, hvis vi gjorde noget lignende int x = SearchHelp, afkast x * 2,
bare nogle tilfældige ændringer.
>> Så nu dette rekursivt kald, denne int x = SearchHelp rekursivt kald,
er ikke længere hale rekursiv fordi det faktisk behøver at vende tilbage
tilbage til en tidligere stakramme således at dette tidligere opfordring til funktionen
Derefter kan gøre noget med den returnerede værdi.
Så dette er ikke halerekursive, men hvad vi havde før, er pænt halerekursive. Yeah.
[Studerende] Bør ikke det andet hovedforslag kontrolleres først
fordi der kunne være en situation, hvor når du passerer det argumentet
De har start = ende, men de er nålen værdi.
Spørgsmålet blev ikke vi løber ind i, hvis end er nålen værdi
eller starte = ende, passende, start = ende
og du har faktisk ikke tjekket den bestemte værdi endnu,
derefter starte + ende / 2 er bare at være den samme værdi.
Men vi har allerede vendt tilbage falsk og vi faktisk aldrig tjekket værdien.
Så i det mindste i den første indkaldelse, hvis størrelse er 0, så vi ønsker at vende tilbage falsk.
Men hvis størrelse er 1, så start ikke kommer til at lige ende,
og vi vil i det mindste kontrollere det ene element.
Men jeg tror du har ret i, at vi kan ende i en sag, hvor starter + ende / 2,
starte ender med at blive det samme som start + afslutning / 2,
men vi har faktisk aldrig tjekket dette element.
>> Så hvis vi først tjekke er den midterste element den værdi, vi leder efter,
så vi straks kan returnere sandt.
Else hvis de er ens, så er der ingen grund til at fortsætte
da vi bare vil opdatere til en sag, hvor vi er på en enkelt-element array.
Hvis det enkelt element ikke er den, vi leder efter,
så alt er forkert. Yeah.
[Studerende] Sagen er, at da størrelse er faktisk større end antallet af elementer i array,
der allerede er en offset - >> Så vil størrelse -
[Studerende] Sig Hvis matrixen var størrelsen 0, er SearchHelp rent faktisk vil kontrollere høstak fra 0
på det første opkald.
Grupperingen har størrelse 0, så 0 er - >> Yeah.
Der er en anden ting, - det kunne være godt. Lad os tænke.
Så hvis opstillingen havde 10 elementer og den midterste vi vil tjekke indeks 5,
så vi tjekker 5, og lad os sige, at værdien er mindre.
Så vi smider alt væk fra 5 og fremefter.
Så start + afslutning / 2 vil være vores nye ende,
så ja, det altid vil bo ud over slutningen af ​​array.
Hvis det er en sag, hvis det var lige eller ulige, så ville vi kontrollere, siger, 4,
men vi er stadig smide væk -
Så yeah, er ende altid vil være ud over den faktiske ende af array.
Så de elementer, som vi fokuserer på, er ende altid vil være det ene efter det.
Og så hvis starten ikke nogensinde lige ende, er vi i en vifte af størrelse 0.
>> Den anden ting jeg tænkte er, vi opdaterer begynder at være starte + ende / 2,
så dette er tilfældet, at jeg har problemer med, hvor starter + ende / 2
er det element, vi tjekker.
Lad os sige, vi havde denne 10-element array. Uanset hvad.
Så start + afslutning / 2 vil være noget som dette,
og hvis det ikke er den værdi, siger, vi ønsker at opdatere.
Værdien er større, så vi ønsker at se på denne halvdel af rækken.
Så hvordan vi opdaterer start, opdaterer vi start til nu være dette element.
Men det kan stadig arbejde, eller i det mindste, du kan gøre starten + ende / 2 + 1.
[Studerende] Du behøver ikke at være starte + ende [uhørligt] >> Yeah.
Vi har allerede tjekket dette element og ved, det er ikke den, vi leder efter.
Så vi behøver ikke at opdatere begynder at være dette element.
Vi kan bare springe det over og opdatere begynde at være dette element.
Og er der overhovedet en sag, lad os sige, at dette var ende,
så derefter begynde ville være denne, start + afslutning / 2 ville være denne,
starte + ende - Ja, jeg tror, ​​det kan ende i uendelig rekursion.
Lad os sige det er bare en vifte af størrelse 2 eller en vifte af størrelse 1. Jeg tror, ​​det vil virke.
Så i øjeblikket, start er at element og ende er 1 ud over det.
Så det element, vi vil kontrollere, er denne ene,
og så når vi opdaterer start, opdaterer vi begynder at være 0 + 1/2,
der kommer til at ende os tilbage med start bliver dette element.
>> Så vi tjekker det samme element igen og igen.
Så dette er tilfældet, når hver rekursivt kald skal faktisk opdatere noget.
Så vi er nødt til at gøre starten + ende / 2 + 1, ellers er der en sag
hvor vi faktisk ikke at opdatere start.
Enhver kan se, at?
Okay.
Er der nogen der har spørgsmål om denne løsning eller nogen flere kommentarer?
Okay. Er der nogen der har en iterativ løsning, som vi alle kan se på?
Gjorde vi alle gøre det rekursivt?
Eller også jeg gætte, hvis du har åbnet hendes, så skal du måske have tilsidesat det tidligere.
Betyder det automatisk gemme? Jeg er ikke positiv.
Er der nogen der har iterativ?
Vi kan gå igennem det sammen, hvis ikke.
Tanken vil være den samme.
Iterativ løsning.
Vi vil ønsker at stort set gøre det samme idé
hvor vi ønsker at holde styr på den nye ende af rækken, og den nye begyndelse af arrayet
og gøre det igen og igen.
Og hvis, hvad vi holde styr på som starten og slutningen nogensinde skærer hinanden,
så vi ikke finde det, og vi kan returnere falsk.
Så hvordan gør jeg det? Nogen der har forslag eller kode for mig at trække op?
[Studerende] Do en while-løkke. >> Yeah.
Du kommer til at ønsker at gøre en løkke.
>> Har du have kode jeg kunne trække op, eller hvad ville du foreslå?
[Studerende] Jeg tror det. >> Okay. Det gør tingene lettere. Hvad var dit navn?
[Studerende] Lucas.
Revision 1. Okay.
Low er, hvad vi kaldte starte før.
Up er ikke helt, hvad vi kaldte ende før.
Faktisk ende er nu inden for opstillingen. Det er et element, vi bør overveje.
Så lav er 0, op er størrelsen af ​​grupperingen - 1,
og nu er vi looping, og vi tjekker -
Jeg tror, ​​du kan gå igennem det.
Hvad var dine tanker gennem dette? Gå os gennem din kode.
[Studerende] Sure. Kig på høstakken værdien i midten og sammenligne det med nål.
Så hvis det er større end din nål, så du ønsker at - oh, faktisk skulle der være baglæns.
Du vil ønsker at smide den højre halvdel, og så ja, skal der være vejen.
[Bowden] Så det bør være mindre? Er det, hvad du sagde? >> [Studerende] Yeah.
[Bowden] Okay. Mindre.
Så hvis det, vi kigger på, er mindre end det, vi ønsker,
så ja, vi ønsker at smide den venstre halvdel,
hvilket betyder, at vi opdaterer alt, hvad vi overvejer
ved at flytte lav til højre for arrayet.
Det ser godt ud.
Jeg tror, ​​det har det samme problem, som vi sagde på den foregående,
hvor hvis lav er 0 og op er 1, så lav + op / 2 vil sætte op til at være det samme igen.
>> Og selv hvis det ikke er tilfældet, er det stadig mere effektivt i det mindste
bare smide det element, vi kiggede bare på som vi ved er forkert.
Så lav + op / 2 + 1 - >> [studerende] Det burde være den anden vej.
[Bowden] Eller det skal være - 1, og den anden skal være + 1.
[Studerende] Og der bør være en dobbelt lighedstegn. >> [Bowden] Yeah.
[Studerende] Yeah.
Okay.
Og endelig, nu hvor vi har dette + 1 - 1 ting,
er det - er det måske ikke - er det stadigt muligt for lav til at ende op med en værdi større end op?
Jeg tror den eneste måde, der kan ske - Er det muligt? >> [Studerende] Jeg ved det ikke.
Men hvis det bliver afkortet, og derefter får minus, at 1 og derefter - >> Yeah.
[Studerende] Det ville muligvis få rodet op.
Jeg tror, ​​det skulle være godt kun fordi
for det til at ende lavere de skulle være lige, tror jeg.
Men hvis de er ens, så ville vi ikke have gjort det, mens løkken til at begynde med
og vi bare ville have returneret værdien. Så jeg tror, ​​vi er godt nu.
Bemærk, at selv om dette problem ikke længere rekursivt
den samme slags idéer anvendelse, når vi kan se, hvordan dette så let egner sig
til en rekursiv løsning ved, at vi bare er ved at opdatere de indeks, igen og igen,
vi gør problemet mindre og mindre, vi fokuserer på en delmængde af array.
[Studerende] Hvis lav er 0 og op er 1, ville de begge være 0 + 1/2, der ville gå til 0,
og så ville man være + 1, ville man være - 1.
[Studerende] Hvor skal vi tjekker ligestilling?
Ligesom hvis den midterste er faktisk nål?
Vi er ikke i øjeblikket gør det? Oh!
Hvis det er -
Ja. Vi kan ikke bare gøre testen ned her, fordi lad os sige det første midten -
[Studerende] Det er faktisk godt lide ikke smide den bundne.
Så hvis du smider den bundne, er du nødt til at tjekke det først, eller whatever.
Ah. Yeah. >> [Studerende] Yeah.
Så nu har vi smidt væk den, vi i øjeblikket kigget på,
hvilket betyder, at vi nu er nødt til at også have
if (høstak [(lav + op) / 2] == nål), så kan vi returnere sandt.
Og uanset om jeg sætter andre eller bare hvis det betyder bogstaveligt talt den samme ting
fordi dette ville have returneret sandt.
Så jeg vil sætte ellers hvis, men det gør ikke noget.
>> Så ellers hvis dette, ellers dette, og det er en fælles ting jeg gør
hvor selv hvis det er tilfældet, hvor alt er godt her,
ligesom lav aldrig kan være større end op, det er ikke værd at ræsonnement om, hvorvidt det er sandt.
Så du kan lige så godt sige, mens lav, er mindre end eller lig med
eller mens lav er mindre end
så hvis de nogensinde lig med eller lav sker til at gå op,
så vi kan bryde ud af denne løkke.
Spørgsmål, bekymringer, kommentarer?
Okay. Det ser godt ud.
Nu skal vi ønsker at gøre slags.
Hvis vi går til min anden revision, ser vi de samme tal,
men nu er de ikke længere er i sorteret orden.
Og vi ønsker at gennemføre sortere ved hjælp af en algoritme i O n log n.
Så hvilken algoritme tror du, vi bør gennemføre her? >> [Studerende] Flet slags.
[Bowden] Yeah. Flet slags er O (n log n), så det er hvad vi vil gøre.
Og problemet bliver temmelig ens,
hvor den let egner sig til en rekursiv løsning.
Vi kan også komme med en iterativ løsning, hvis vi vil,
men rekursion vil være lettere her, og vi bør gøre rekursion.
Jeg tror vi vil gå gennem sammenfletning slags først,
selv om der er en dejlig video på merge sort allerede. [Latter]
Så fusionere slags der er - jeg spilder så meget af dette papir.
Åh, der er kun en tilbage.
Så fusionere.
Åh, 1, 3, 5.
Okay.
Merge tager to separate arrays.
Hver af disse to arrays begge sorteres.
Så denne matrix, 1, 3, 5, sorteres. Denne matrix, 0, 2, 4, sorteres.
Nu hvad fletning skal gøre, er at kombinere dem i et enkelt array, der selv er sorteret.
Så vi ønsker en vifte af str. 6, der vil have disse elementer inde i det
i sorteret orden.
>> Og så vi kan drage fordel af det faktum, at disse to arrays sorteres
at gøre dette i lineær tid,
lineær tid betydning, hvis dette array er størrelse x, og det er størrelse y,
så den totale algoritmen skal være O (x + y). Okay.
Så forslag.
[Studerende] Kunne vi starte fra venstre?
Så du sætter 0 ned først og derefter 1 og derefter her du er på 2.
Så det er lidt ligesom du har en fane, der er flytter til højre. >> [Bowden] Yeah.
For begge disse arrays, hvis vi blot fokusere på den venstre element.
Fordi begge arrays er sorteret, vi ved, at disse 2 elementer
er de mindste elementer i hver række.
Så det betyder, at 1 af disse 2 elementer skal være det mindste element i vores fusionerede array.
Det bare så sker det, at den mindste er det en på højre denne gang.
Så vi tager 0, indsætte det på venstre, fordi 0 er mindre end 1,
så tage 0, skal du indsætte det i vores første position, og så opdaterer vi denne
til nu fokusere på det første element.
Og nu gentager vi.
Så nu vi sammenligner 2 og 1. 1 er mindre, så vi indsætter 1.
Vi opdaterer denne pegepind til at pege på den fyr.
Nu skal vi gøre det igen, så 2. Dette vil opdatere, sammenligne disse 2, 3.
Dette opdaterer, derefter 4 og 5.
Så det er merge.
>> Det burde være temmelig indlysende, at det er lineær tid siden vi bare gå på tværs af hvert element én gang.
Og det er det største skridt til at gennemføre merge sort gør dette.
Og det er ikke så svært.
Et par ting at bekymre sig om, er lad os sige, at vi var sammenlægning 1, 2, 3, 4, 5, 6.
I dette tilfælde ender vi i den situation, hvor denne ene vil være mindre,
så vi opdatere denne pointer, denne ene vil være mindre, opdatere denne,
denne ene er mindre, og nu har du nødt til at erkende
når du har faktisk løber tør for materiale til at sammenligne med.
Da vi allerede har brugt hele denne array,
alt i dette array er nu lige har indsat ind på her.
Så hvis vi nogensinde løbe ind i det punkt, hvor en af ​​vores arrays er helt flettes allerede,
så vi bare tage alle elementer i den anden array og indsætte dem i slutningen af ​​array.
Så vi kan bare indsætte 4, 5, 6. Okay.
Det er én ting at holde øje med.
Implementering, der bør være trin 1.
Flet sortere så er baseret på det, det er 2 trin, 2 dumme trin.
Lad os bare give denne array.
Så fusionere sortere, trin 1 er at rekursivt bryde array i to halvdele.
Så delt dette array i to halvdele.
Vi har nu 4, 15, 16, 50 og 8, 23, 42, 108.
Og nu gør vi det igen og vi delt dem i to halvdele.
Jeg vil bare gøre det på denne side.
Så 4, 15 og 16, 50.
Vi ville gøre det samme herovre.
Og nu vi dele det op i to halvdele igen.
Og vi har 4, 15, 16, 50.
Så det er vores base case.
Når arrays er af størrelse 1, så holder vi op med opsplitningen i to halvdele.
>> Nu hvad gør vi med det?
Vi ender dette også vil bryde ned i 8, 23, 42 og 108.
Så nu, at vi er på dette punkt, nu træde to af merge slags er bare fusionerende par til listerne.
Så vi ønsker at flette disse. Vi bare ringe fusionere.
Vi ved sammenfletning vil returnere disse i sorteret orden.
4, 15.
Nu ønsker vi at flette disse, og som vil returnere en liste med dem i sorteret orden,
16, 50..
Vi fletter dem - jeg kan ikke skrive - 8, 23 og 42, 108.
Så vi har flettede par gang.
Nu skal vi bare fusionere igen.
Bemærk, at hver af disse lister sorteres i sig selv,
og så kan vi bare flette disse lister til at få en liste over størrelse 4, som er sorteret
og flette disse to lister for at få en liste over størrelse 4, der er sorteret.
Og endelig kan vi flette de to lister over størrelse 4 for at få en liste over størrelse 8, der er sorteret.
Så for at se, at dette er samlet n log n, vi allerede har set, at fletningen er lineær,
så når vi har at gøre med sammenlægningen disse, så ligesom de samlede omkostninger i fletningen
for disse to lister er kun 2, fordi -
Eller ja, det er O n, men n her er bare disse 2 elementer, så det er 2.
Og disse 2 vil være 2, og disse 2 vil være 2, og disse 2 vil være 2,
så på tværs af alle de smelter sammen, vi skal gøre, vi ender med at gøre n..
Ligesom 2 + 2 + 2 + 2 er 8, som er N,
så omkostningerne ved sammenlægningen i dette sæt er n.
Og så det samme her.
Vi vil fusionere disse 2, da disse 2, og individuelt denne sammenfletning vil tage fire operationer,
denne sammenfletning vil tage fire operationer, men endnu en gang, mellem alle disse,
vi ender sammenlægning N Total ting, og så tager dette trin n..
Og så hvert niveau tager n elementer er slået sammen.
>> Og hvor mange niveauer er der?
På hvert niveau, vokser vores array efter størrelse 2.
Her vores arrays er af størrelse 1, her de er af størrelse 2, her de er af størrelse 4,
og endelig, de er af størrelse 8.
Så da det er en fordobling, er der vil være i alt log n af disse niveauer.
Så med log n niveauer, hvert enkelt niveau under n samlede transaktioner,
vi får en n log n algoritme.
Spørgsmål?
Har folk allerede gjort fremskridt på hvordan man gennemfører dette?
Er der nogen, der allerede er i en tilstand, hvor jeg bare kan trække op deres kode?
Jeg kan give et minut.
Denne ene vil være længere.
Jeg anbefaler stærkt tilbagevendende -
Du behøver ikke at gøre rekursion for sammenfletningen
fordi at gøre rekursion for fletningen, er du nødt til at passere en masse forskellige størrelser.
Det kan du, men det er irriterende.
Men rekursion for sort selv er temmelig let.
Du skal bare bogstaveligt kalde slags på venstre halvdel, sort på højre halvdel. Okay.
Nogen der har noget jeg kan trække op endnu?
Ellers vil jeg give et minut.
Okay.
Nogen der har noget, vi kan arbejde med?
Ellers vil vi bare arbejde med dette og derefter udvide derfra.
>> Nogen der har mere end dette, at jeg kan trække op?
[Studerende] Yeah. Du kan trække op mine. >> Okay.
Yes!
[Studerende] Der var en masse betingelser. >> Åh, skyde. Kan du -
[Studerende] Jeg er nødt til at gemme det. >> Yeah.
Så vi gjorde gøre fletningen separat.
Åh, men det er ikke så slemt.
Okay.
Så sort er selv bare ringer mergeSortHelp.
Forklar os, hvad mergeSortHelp gør.
[Studerende] MergeSortHelp temmelig meget gør de to vigtigste skridt,
nemlig at sortere hver halvdel af opstillingen og derefter at fusionere dem begge.
[Bowden] Okay, så giv mig et sekund.
Jeg tror, ​​at dette - >> [studerende] Jeg har brug for -
Yeah. Jeg mangler noget.
I fusionere, indser jeg, at jeg har brug for at oprette et nyt array
fordi jeg ikke kunne gøre det på plads. >> Ja. Du kan ikke. Ret.
[Studerende] Så jeg opretter et nyt array.
Jeg glemte i slutningen af ​​fusionere til re-skifte.
Okay. Vi har brug for et nyt array.
I sammenfletning sortere, er det næsten altid sandt.
Del af omkostningerne ved en bedre algoritme tidsmæssigt
næsten altid behøver at bruge lidt mere hukommelse.
Så her, uanset hvordan du gør flette sortere,
du ville uundgåeligt nødt til at bruge nogle ekstra hukommelse.
Han eller hun skabte et nyt array.
Og så siger du i slutningen vi bare nødt til at kopiere ny array i den oprindelige array.
[Studerende] Jeg tror så, ja.
Jeg ved ikke, om det virker i forhold til at tælle ved henvisning eller hvad -
Ja, det vil virke. >> [Studerende] Okay.
Har du prøve at køre dette? >> [Studerende] Nej, ikke endnu. >> Okay.
Prøv at køre det, og så vil jeg tale om det for et sekund.
[Studerende] Jeg har brug for at have alle de funktioner prototyper og alt, selv om, ikke?
De funktionelle prototyper. Åh, du mener ligesom - Ja.
Sorter kalder mergeSortHelp.
>> Så for at sortere at kalde mergeSortHelp skal mergeSortHelp enten er blevet defineret
før sortere eller vi bare brug for prototypen. Du skal blot kopiere og indsætte det.
Og på samme måde er mergeSortHelp ringer fusionere,
men merge er ikke blevet defineret endnu, så vi kan bare lade mergeSortHelp vide
at det er hvad fusionere kommer til at se ud, og det er det.
Så mergeSortHelp.
Vi har et problem her, hvor vi ikke har nogen base case.
MergeSortHelp er rekursiv, så enhver rekursiv funktion
vil få brug for en slags base case til at vide, hvornår de skal stoppe rekursivt kalder sig.
Hvad er vores base case vil være her? Yeah.
[Studerende] Hvis størrelsen er 1? >> [Bowden] Ja.
Så ligesom vi så lige der, stoppede vi opdele arrays
når vi fik ind arrays af størrelse 1, der uundgåeligt er sorteret sig selv.
Så hvis størrelse er lig med 1, vi kender array er allerede sorteret,
så vi kan bare vende tilbage.
>> Bemærk, at er ugyldige, så vi ikke returnere noget særligt, vi bare vende tilbage.
Okay. Så det er vores base case.
Jeg gætter vores base case kunne også være, hvis vi tilfældigvis sammenlægning et array af størrelse 0,
vi nok ønsker at stoppe på et tidspunkt,
så vi kan blot sige størrelse mindre end 2 eller mindre end eller lig med 1.
således at dette vil arbejde for enhver opstilling nu.
Okay.
Så det er vores base case.
Nu vil du gå os gennem fletningen?
Hvad har alle disse tilfælde betyder?
Heroppe, vi bare gør det samme idé, det -
[Studerende] Jeg har brug for at være forbi størrelse med alle de mergeSortHelp opkald.
Jeg tilføjede størrelse som en ekstra primær og det er ikke der, ligesom størrelse / 2.
[Bowden] Åh, størrelse / 2, størrelse / 2. >> [Studerende] Ja, og også i den ovennævnte funktion som godt.
[Bowden] Her? >> [Studerende] Just størrelse. >> [Bowden] Oh. Størrelse, størrelse? >> [Studerende] Yeah.
[Bowden] Okay.
Lad mig tænke et sekund.
Må vi løber ind i et problem?
Vi er altid at behandle venstre som 0. >> [Studerende] Nej.
Det er også forkert. Undskyld. Det bør være start. Yeah.
[Bowden] Okay. Jeg kan godt lide, at bedre.
Og ende. Okay.
Så nu vil du gå os gennem fletningen? >> [Studerende] Okay.
Jeg er bare walking gennem denne nye array, jeg har oprettet.
Dens størrelse er størrelsen af ​​den del af sættet, som vi ønsker at blive sorteret
og forsøger at finde det element, at jeg skulle lægge i det nye array-trin.
Så for at gøre det, først jeg kontrollere, hvis den venstre halvdel af arrayet fortsætter med at have nogen flere elementer,
og hvis den ikke gør det, så skal du gå ned til det andet betingelse, der bare siger
okay, skal det være i den rigtige opstilling, og vi vil sætte det i det aktuelle indeks i newArray.
>> Og så ellers, jeg tjekker hvis den rigtige side af array også er færdig,
i hvilket tilfælde jeg bare sætte i venstre.
Det er måske faktisk ikke være nødvendig. Jeg er ikke sikker.
Men alligevel, den anden to check hvilke af de to er mindre i venstre eller højre.
Og også i hvert enkelt tilfælde, jeg inkrementering uanset hvilken pladsholder jeg tilvækst.
[Bowden] Okay.
Det ser godt ud.
Er der nogen der har kommentarer eller bekymringer eller spørgsmål?
Så de fire sager, som vi er nødt til at bringe tingene i bare at være - eller det ligner fem -
men vi er nødt til at overveje, om den venstre-array er løbet tør for ting, vi skal fusionere,
hvorvidt retten arrayet er løbet tør for ting, vi skal fusionere -
Jeg peger på ingenting.
Så hvad enten venstre-array er løbet tør for ting eller det rigtige opstilling er løbet tør for ting.
Det er to sager.
Vi har også brug for trivielle tilfælde af, om den venstre ting er mindre end det rigtige.
Så vi ønsker at vælge den venstre ting.
Det er de sager.
Så det var rigtigt, så det er det.
Array tilbage. Det er 1, 2, 3. Okay. Så ja, det er de fire ting, vi måske ønsker at gøre.
Og vi vil ikke gå over en iterativ løsning.
Jeg vil ikke anbefale -
Flette art er et eksempel på en funktion, der både er ikke halerekursive,
det er ikke nemt at gøre det halerekursive,
men også det er ikke meget let at gøre det iterativ.
Dette er meget let.
Denne implementering af fletningen slags,
fusionere, uanset hvad du gør, er du nødt til at bygge merge.
>> Så fusionere slags bygget oven på fletningen rekursivt er bare disse tre linjer.
Iterativt, det er mere irriterende og vanskeligere at tænke over.
Men bemærk at det ikke er halerekursive siden mergeSortHelp - når den kalder sig selv -
det stadig nødvendigt at gøre ting efter dette rekursivt kald afkast.
Så denne stakramme skal fortsætte med at eksistere, selv efter at kalde dette.
Og så når du kalder det, skal stakrammen fortsætte med at eksistere
fordi selv efter denne samtale, vi stadig nødt til at fusionere.
Og det er nontrivial at gøre denne halerekursive.
Spørgsmål?
Ok.
Så gå tilbage til at sortere - Åh, der er to ting, jeg gerne vil vise. Okay.
Går tilbage til at sortere, vil vi gøre dette hurtigt.
Eller søg. Sorter? Sorter. Yeah.
Går tilbage til begyndelsen af ​​slags.
Vi ønsker at skabe en algoritme, der sorterer array ved hjælp af en algoritme
i O n.
Så hvordan er dette muligt? Er der nogen der har nogen form for -
Jeg antydede før på -
Hvis vi er ved at blive forbedret fra n log n til O i n,
vi har forbedret vores algoritme tidsmæssigt,
hvilket betyder hvad skal vi gøre for at gøre op for det?
[Studerende] Space. >> Yeah. Vi skal bruge mere plads.
Og ikke bare mere plads, det er eksponentielt mere plads.
Så jeg tror denne type algoritme er pseudo noget, pseudo polynom -
pseudo - Jeg kan ikke huske det. Pseudo noget.
Men det er fordi vi er nødt til at bruge så meget plads
at dette er muligt, men ikke realistisk.
>> Og hvordan opnår vi det?
Vi kan opnå dette, hvis vi garanterer, at nogen bestemt element i arrayet
er under en vis størrelse.
Så lad os bare sige, at størrelse er 200,
ethvert element i et array er under størrelse 200.
Og det er faktisk meget realistisk.
Du kan meget let få et array, som du ved alt i det
vil være mindre end et vist antal.
Ligesom hvis du har nogle absolut massiv vektor eller noget
men du ved alt kommer til at ligge mellem 0 og 5,
så det vil være betydeligt hurtigere at gøre dette.
Og det bundne på et af elementerne er 5,
så denne bundne, er, at hvor meget hukommelse, du skal bruge.
Så den bundne er 200.
I teorien er der altid en bundet eftersom et heltal kun kan være op til 4000000000,
men det er urealistisk siden da vi ville bruge plads
af størrelsesordenen 4 mia. Så det er urealistisk.
Men her vil vi sige, at vores grænse er 200.
Det trick til at gøre det i O n er vi gøre en anden array kaldet tællinger af størrelse BUNDET.
Så faktisk, det er en genvej til - jeg faktisk ikke, om Dunk gør dette.
Men i GCC i det mindste - jeg antager Dunk gør det også -
Dette vil bare initialisere hele array'et at være 0'erne.
Så hvis jeg ikke ønsker at gøre det, så kunne jeg hver gøre for (int i = 0;
i <bundet; i + +) og tæller [i] = 0;
Så nu er alt initialiseres til 0.
Jeg gentage over mit array,
og hvad jeg laver, er jeg tælle antallet af hver - Lad os gå ned her.
Vi har 4, 15, 16, 50, 8, 23, 42, 108.
Hvad jeg tælle er antallet af forekomster af hver af disse elementer.
Lad os faktisk tilføje et par mere i her med nogle gentagelser.
Så den værdi, vi har her, er værdien af ​​det vil være array [i].
Så val kunne være 4 eller 8 eller hvad.
Og nu vil jeg tælle hvor mange af denne værdi jeg har set,
så tæller [val] + +;
Når dette er gjort, er tæller kommer til at ligne 0001.
Lad os gøre tæller [val] - BUNDET + 1.
>> Nu det er bare at redegøre for det faktum, at vi starter fra 0.
Så hvis 200 bliver vores største antal,
derefter fra 0 til 200 er 201 ting.
Så tæller, vil det se ud som 00.001, da vi har en 4.
Så må vi have 0001, hvor vi vil have en 1 i det 8. indeks tæller.
Vi vil have en 2 i det 23. indeks tæller.
Vi vil have en 2 i den 42. indekset tæller.
Så vi kan bruge tæller.
Så num_of_item = tæller [i].
Og så hvis num_of_item er 2, der betyder, at vi ønsker at indsætte 2 i antallet i
i vores sorteret array.
Så vi er nødt til at holde styr på, hvor langt vi er i opstillingen.
Så index = 0..
Array - jeg vil bare skrive det.
Tæller -
array [index + +] = i;
Er det, hvad jeg vil? Jeg tror, ​​det er hvad jeg vil.
Ja, det ser godt ud. Okay.
Så gør alle forstå, hvad formålet med mit tæller array er?
Det er at tælle antallet af forekomster af hver af disse numre.
Så jeg iteration over der tæller array,
og den i'te position i tællinger matrix
er antallet af i'erne, der skal vises i min sorteret array.
Det er derfor tællinger af 4 kommer til at være 1
og tæller på 8 vil være 1, tællinger af 23 vil være 2.
Så det er hvor mange af dem jeg ønsker at indsætte i min sorteret array.
Så jeg bare gøre det.
Jeg indsætter num_of_item i'erne ind i min sorteret array.
>> Spørgsmål?
Og så igen, denne er lineær tid siden vi bare iteration over denne gang,
men det er også lineær i, hvad dette nummer sker for at være,
og så det afhænger i høj grad af, hvad din grænse er.
Med en bundet på 200, er det ikke så slemt.
Hvis din bundne vil være 10.000, så det er lidt værre,
men hvis det indbundne vil være 4 milliarder, det er helt urealistisk
og dette array er nødt til at være af størrelse 4 mia.kr., hvilket er urealistisk.
Så det er det. Spørgsmål?
[Uhørlig student svar] >> Okay.
Jeg indså en anden ting, når vi skulle igennem.
Jeg tror, ​​problemet var i Lucas 'og formentlig hver eneste vi har set.
Jeg helt glemt.
Det eneste, jeg ønskede at kommentere, er, at når du har at gøre med ting som indeks,
du aldrig virkelig se dette, når du skriver en for-løkke,
men teknisk, når du har at gøre med disse indekser,
bør du stort set altid beskæftige sig med unsigned heltal.
Grunden til dette er, når du har at gøre med signerede heltal,
så hvis du har 2 signerede heltal, og du tilføjer dem sammen
og de ender for stor, så du ender op med et negativt tal.
Så det er, hvad heltalsoverløb er.
>> Hvis jeg tilføjer 2 mia og 1 mia jeg ender med negativ 1 mia.
Det er, hvordan heltal arbejde på computere.
Så problemet med at bruge -
Det er fint, undtagen hvis lav sker for at være 2 milliarder og op sker for at være 1 mia
så dette vil være negativ 1 mia så vil vi dele dette med 2
og ender med negativ 500 mio.
Så det er kun et problem, hvis du tilfældigvis være at søge gennem et array
af milliarder af ting.
Men hvis lav + op sker med overløb, så det er et problem.
Så snart vi gør dem usigneret, så 2 milliarder plus 1 mia 3 mia.
3 milliarder divideret med 2 er 1,5 mia.
Så så snart de er unsigned, alt er perfekt.
Og så det er også et problem, når du skriver din efter sløjfer,
og faktisk er det sandsynligvis gør det automatisk.
Det vil faktisk bare råbe på dig.
Så hvis dette tal er for stor til at være i bare et heltal, men det ville passe ind i en usigneret heltal,
det vil råbe på dig, så det er derfor, du aldrig rigtig løber ind i problemet.
Du kan se, at et indeks aldrig kommer til at være negativ,
og så når du iteration over et array,
du kan næsten altid sige unsigned int i, men du behøver ikke virkelig nødt til at.
Tingene kommer til at arbejde temmelig meget lige så godt.
Okay. [Hvisker] Hvad er klokken?
Det sidste, jeg ønskede at vise - og jeg vil bare gøre det virkelig hurtig.
Du ved, hvordan vi har # define så vi # kan definere MAX som 5 eller noget?
Lad os ikke gøre MAX. # Define bundet som 200. Det er, hvad vi gjorde før.
Det definerer en konstant, som er lige til at blive kopieret og indsat
hvor vi tilfældigvis skrive BUNDET.
>> Så vi kan faktisk gøre mere med # definerer.
Vi kan # define funktioner.
De er ikke rigtig fungerer, men vi vil kalde dem funktioner.
Et eksempel ville være noget MAX (x, y) er defineret som (x <y y:? X). Okay.
Så du bør vænne sig til ternære operatør syntaks,
men er x mindre end y? Returnerer y, ellers returnerer x.
Så du kan se, kan du gøre dette til en særskilt funktion,
og funktionen kunne være som bool MAX tager 2 argumenter, returnere dette.
Dette er en af ​​de mest almindelige jeg ser gjort på denne måde. Vi kalder dem makroer.
Dette er en makro.
Dette er blot syntaksen for det.
Du kan skrive en makro til at gøre hvad du vil.
Du ofte se makroer for debugging printfs og kram.
Så en form for printf, er der specielle konstanter i C ligesom underscore LINE understregning,
2 understreger LINE understregning,
og der er også jeg tror 2 understregninger FUNC. Det kunne være det. Noget i den retning.
Disse ting vil blive erstattet med navnet på den funktion
eller nummeret på den linje, du er på.
Ofte skriver du debugging printfs der ned her kunne jeg så bare skrive
Debug og det vil udskrive linjenummer og funktion, som jeg tilfældigvis er i
at det stødte at DEBUG erklæring.
Og du kan også udskrive andre ting.
Så en ting du skal holde øje med er, hvis jeg tilfældigvis # define DOUBLE_MAX
som noget i retning af 2 * y og 2 * x.
Så uanset årsagen, sker dig at gøre det en masse.
Så gør det til en makro.
Dette er faktisk brudt.
Jeg ville kalde det ved at gøre noget lignende DOUBLE_MAX (3, 6).
Så hvad skal returneres?
[Studerende] 12.
Ja, 12 blive returneret, og 12 er returneret.
3 bliver erstattet for x, bliver 6 erstattes for y, og vi vender tilbage 2 * 6, hvilket er 12.
Nu hvad med det her? Hvad skal returneres?
[Studerende] 14. >> Ideelt 14.
Spørgsmålet er, hvordan hash definerer arbejdet, husk det er en bogstavelig kopiere og indsætte
af stort set alt, hvad så dette vil blive fortolket som
er 3 mindre end 1 plus 6, 2 gange 1 plus 6, 2 gange 3.
>> Så af denne grund du næsten altid wrap alt i parentes.
Enhver variabel, du næsten altid wrap i parentes.
Der er tilfælde, hvor du ikke behøver at, ligesom jeg ved, at jeg ikke behøver at gøre det her
fordi mindre end er temmelig meget altid bare at gå på arbejde,
selv om det måske ikke engang være sandt.
Hvis der er noget latterligt som DOUBLE_MAX (1 == 2),
så der kommer til at få erstattet med 3 mindre end 1 lig lig med 2,
og så derefter det kommer til at gøre 3 mindre end 1, betyder det lige 2,
der er ikke det, vi ønsker.
Så for at undgå eventuelle operatør forrang problemer,
altid wrap i parentes.
Okay. Og det er det, 5:30.
Hvis du har spørgsmål om Pset, så lad os det vide.
Det skal være sjovt, og hacker-udgaven også er meget mere realistisk
end hacker udgave af sidste års, så vi håber, at en masse af jer prøve det.
Sidste års var meget overvældende.
>> [CS50.TV]