[Powered by Google Translate] [Del 3 - Mer komfortabelt] [Rob Bowden - Harvard University] [Dette er CS50. - CS50.TV] Så det første spørsmålet er merkelig formulert. GDB lar deg "feilsøke" et program, men mer spesifikt, hva betyr det lar deg gjøre? Jeg skal svare på det, og jeg vet ikke hva som egentlig forventet, så jeg gjetter det er noe langs linjene av den lar deg trinn for trinn gå gjennom programmet, samhandle med det, endre variabler, gjør alle disse tingene - utgangspunktet helt kontroll utførelsen av et program og inspisere enhver del av gjennomføringen av programmet. Så disse funksjonene lar deg feilsøke ting. Okay. Hvorfor krever binære søk som en matrise skal sorteres? Hvem ønsker å svare på det? [Student] Fordi det fungerer ikke hvis det ikke er sortert. >> Ja. [Latter] Hvis det ikke er sortert, så det er umulig å dele den i to og vet at alt til venstre er mindre og alt til høyre er større enn den midterste verdien. Så det må sorteres. Okay. Hvorfor er boble sortere i O n squared? Er det noen som først ønsker å gi en svært rask høyt nivå oversikt over hva boble slags er? [Student] Du i utgangspunktet gå gjennom hvert element, og du sjekker de første elementene. Hvis de er ute av der du kan utveksle dem, så du sjekke de neste få elementer og så videre. Når du kommer til slutten, så vet du at det største elementet er plassert på slutten, så du ignorere at en da du holder på å gå gjennom, og hver gang du må sjekke en mindre element før du gjør noen endringer. >> Ja. Det kalles boble slags fordi hvis du snur tabellen på sin side så det er opp og ned, vertikal, deretter de store verdier vil synke til bunnen og de små verdier vil boble opp til toppen. Det er hvordan den fikk navnet sitt. Og ja, du bare gå gjennom. Du fortsetter gjennom matrisen, bytte ut større verdi å få de største verdier til bunnen. Hvorfor er det O av n squared? Først ønsker alle å si hvorfor det er O n squared? [Student] Fordi for hver kjøring går det n ganger. Du kan bare være sikker på at du har tatt den største elementet hele veien ned, så må du gjenta at så mange elementer. >> Ja. Så husk hva big O betyr og hva store Omega betyr. Den store O er som øvre grense på hvor sakte det kan faktisk kjøre. Så ved å si det er O n kvadrat, er det ikke O av n eller annet det ville være i stand til å kjøre i lineær tid, men det er O n cubed fordi det er avgrenset av O av n cubed. Hvis det er avgrenset av O av n kvadrat, så det er avgrenset også av n cubed. Så det er n kvadrat, og i absolutt verste fall kan det ikke gjøre det bedre enn n squared, som er hvorfor det er O av n squared. Så for å se svak matematikk på hvordan det kommer ut til å være n squared, hvis vi har fem ting i vår liste, første gang hvor mange bytter vi kunne potensielt trenger å gjøre for å få dette? La oss faktisk bare - Hvor mange swapper vi nødt til å gjøre i den første kjøring av boble sortere gjennom array? [Student] n - 1. >> Ja. Hvis det er 5 elementer, vi kommer til å trenge å gjøre n - 1. Så på den andre hvor mange swapper vi nødt til å gjøre? [Student] n - 2. >> Ja. Og den tredje kommer til å være n - 3, og deretter for enkelhets skal jeg skrive de to siste som da vi kommer til å trenge å gjøre 2 swapper og 1 swap. Jeg antar det siste kan eller ikke kan faktisk trenger å skje. Er det en swap? Jeg vet ikke. Så disse er den samlede swaps eller i det minste sammenligninger du har å gjøre. Selv om du ikke bytte, du fortsatt trenger å sammenligne verdiene. Så det er n - 1 sammenligninger i første løp gjennom matrisen. Hvis du omorganisere disse tingene, la oss faktisk gjøre det seks ting så ting stable opp pent, og så skal jeg gjøre 3, 2, 1. Så bare omorganisere disse summene, ønsker vi å se hvor mange sammenligninger vi gjør i hele algoritmen. Så hvis vi tar disse gutta her nede, så vi er fortsatt bare summere men mange sammenligninger det var. Men hvis vi oppsummere disse, og vi oppsummere disse, og vi oppsummere disse, det er fortsatt det samme problemet. Vi bare oppsummere de enkelte grupper. Så nå er vi summere 3 n-tallet. Det er ikke bare 3 n-tallet. Det er alltid kommer til å være n / 2 n-tallet. Så her har vi tilfeldigvis har seks. Hvis vi hadde 10 ting, så vi kunne gjøre denne grupperingen for 5 forskjellige par ting og ender opp med n + n + n + n + n. Slik at du alltid kommer til å få n / 2 n-tallet, og så dette vil vi skrive det ut til n squared / 2. Og så selv om det er den faktoren av halvparten, som skjer for å komme i grunn av det faktum at gjennom hver iterasjon over matrisen sammenligner vi 1 mindre så det er hvordan vi får over 2, men det er fortsatt n squared. Vi bryr oss ikke om den konstante faktoren av en halv. Så mye stor O ting som dette er avhengig av bare slags gjøre denne typen matematikk, gjør aritmetiske summer og geometriske rekker ting, men de fleste av dem i dette kurset er ganske grei. Okay. Hvorfor er innsetting sortere i Omega av n? Hva betyr omega? [To studenter snakker samtidig - uforståelige] >> Ja. Omega du kan tenke på som nedre grense. Så uansett hvor effektiv din innsetting sortere algoritmen er, uavhengig av listen som er vedtatt i, har det alltid å sammenligne minst n ting eller det må iterere over n ting. Hvorfor er det? [Student] Fordi hvis listen er allerede sortert, deretter gjennom den første iterasjon du kan bare garantere at den aller første elementet er den minste, og den andre iterasjon du kan bare garantere de to første er fordi du ikke vet at resten av listen er sortert. >> Ja. Hvis du passerer i en helt sortert liste, i det minste du har å gå over alle elementene å se at ingenting trenger å bli flyttet rundt. Så passerer over listen og si oh, er dette allerede sortert, det er umulig for deg å vite det er sortert før du sjekker hvert element å se at de er i sortert rekkefølge. Så den nedre grensen på innsetting sort er Omega n. Hva er det verste tilfellet kjøretiden flette slag, verste fall være store O igjen? Så i verste fall, hvordan merge slags kjøre? [Student] N log n. >> Ja. De raskeste generelle sortering algoritmer er n log n. Du kan ikke gjøre det bedre. Det finnes spesielle tilfeller, og hvis vi har tid i dag - men vi sannsynligvis won't - Vi kunne se en som gjør det bedre enn n log n. Men i det generelle tilfellet, kan du ikke gjøre det bedre enn n log n. Og flette slags skjer for å være den du bør vite for dette kurset som er n log n. Og så vil vi faktisk være å implementere det i dag. Og til slutt, i mer enn tre setninger, hvordan valg slags arbeid? Ønsker noen å svare på, og jeg vil telle setninger fordi hvis du går over 3 - Husker noen valg slags? Utvalg sorter er vanligvis ganske lett å huske akkurat fra navnet. Du bare iterere over tabellen, finne hva den største verdien er eller minste - den rekkefølgen du sortere i. Så la oss si at vi sortering fra minste til største. Du iterere over rekken, på jakt etter uansett minimum element er, Velg den, og så bare bytte den alt som er i første omgang. Og så i andre omgang over array, se etter minimum element igjen, Velg den, og deretter bytte den med hva som er i andre posisjon. Så vi er bare å velge og vrake minimumsverdiene og sette dem inn i fronten av matrisen før det er sortert. Spørsmål om det? Disse uunngåelig vises i skjemaene du må fylle ut når du sender inn pset. De er i utgangspunktet svar på disse. Ok, så nå koding problemer. Jeg har allerede sendt ut via e-post - Var det noen som ikke får det e? Okay. Jeg har allerede sendt ut via e-post plassen som vi skal bruke, og hvis du klikker på navnet mitt - så jeg tror jeg kommer til å være på bunnen på grunn av den bakover r - men hvis du klikker på navnet mitt vil du se to revisjoner. Revisjon 1 kommer til å bli jeg allerede kopiert og limt inn koden i Spaces for søket ting du er nødt til å gjennomføre. Og Revisjon 2 vil være den slags ting som vi gjennomfører etter det. Så du kan klikke på min Revisjon 1 og jobbe derfra. Og nå ønsker vi å implementere binære søk. Ønsker noen å bare gi en pseudokode høyt nivå forklaring av hva vi nødt til å gjøre for søk? Ja. [Student] Du bare ta midten av tabellen og se om det du leter etter er mindre enn det eller mer enn det. Og hvis det er mindre, kan du gå til den halvparten som er mindre, og hvis det er mer, kan du gå til den halvparten som er mer og gjenta deg at før du bare får én ting. [Bowden] Yeah. Legg merke til at våre tall utvalg er allerede sortert, og så det betyr at vi kan dra nytte av det, og vi kunne først sjekke, okay, jeg ser for nummer 50. Så jeg kan gå inn i midten. Midten er vanskelig å definere når det er en enda rekke ting, men la oss bare si at vi vil alltid avkorte til midten. Så her har vi 8 ting, så midt ville være 16. Jeg leter etter 50, så 50 er større enn 16. Så nå kan jeg i utgangspunktet behandle min matrisen som disse elementene. Jeg kan kaste bort alt fra 16 over. Nå er min matrise er bare disse 4 elementene, og jeg gjentar. Så da jeg ønsker å finne midten igjen, som er tenkt å være 42. 42 er mindre enn 50, så jeg kan kaste bort disse to elementene. Dette er min gjenværende array. Jeg kommer til å finne midten igjen. Jeg antar 50 var et dårlig eksempel fordi jeg var alltid kaste bort ting til venstre, men på samme måte hvis jeg ser etter noe og det er mindre enn elementet jeg for øyeblikket ser på, så jeg kommer til å kaste bort alt til høyre. Så nå må vi gjennomføre det. Legg merke til at vi trenger å passere i størrelse. Vi kan også ikke trenger å hardkode størrelse. Så hvis vi bli kvitt det # define - Okay. Hvordan kan jeg pent finne ut hva størrelsen på tallene matrise for tiden er? Hvor mange elementer er i tallene array? [Student] Numbers, braketter,. Lengden? [Bowden] Det finnes ikke i C. Trenger. Lengde. Arrays har egenskaper, så det er ingen lengde tilhører arrays det vil bare gi deg imidlertid lenge det skjer for å være. [Student] Se hvor mye minne den har, og dividere med hvor mye - >> Ja. Så hvordan kan vi se hvor mye minne den har? >> [Student] sizeof. >> Ja, sizeof. Sizeof er operatør som kommer til å returnere størrelsen på tallene matrisen. Og det kommer til å bli uansett hvor mange heltall det er tider på størrelse med et heltall siden det er hvor mye minne det er faktisk å ta opp. Så hvis jeg vil at antall ting i rekken, så jeg kommer til å ønske å dele av størrelsen på et heltall. Okay. Så det lar meg passere i størrelse her. Hvorfor trenger jeg å passere i størrelse i det hele tatt? Hvorfor kan jeg ikke bare gjøre opp her int size = sizeof (høystakken) / sizeof (int)? Hvorfor dette ikke fungerer? [Student] Det er ikke en global variabel. [Bowden] Haystack eksisterer og vi kjører i tall som høystakken, og dette er en slags forvarsel om hva som kommer. Ja. [Student] Haystack er bare referansen til det, så det ville gå tilbake hvor stor den referansen er. Ja. Jeg tviler på forelesning som du har sett stabelen ennå virkelig, ikke sant? Vi har nettopp snakket om det. Så stabelen er der alle variabler kommer til å bli lagret. Noe minne som er tildelt for lokale variabler kommer i bunken, og hver funksjon får sin egen plass på stakken, er sin egen stack frame hva det heter. Så main har sin stack ramme, og innsiden av det kommer til å eksistere dette tall array, og det kommer til å være av størrelse sizeof (tall). Det kommer til å ha størrelse med tall delt på størrelsen av elementer, men at alle liv innenfor hoved stack ramme. Når vi kaller søk, får sin søken egen stack frame, sin egen plass til å lagre alle sine lokale variabler. Men disse argumentene - så høystakken er ikke en kopi av hele denne gruppen. Vi har ikke passere i hele matrisen som en kopi i søk. Den passerer bare en referanse til denne matrisen. Så søk kan få tilgang til disse tallene gjennom denne referansen. Det er fortsatt tilgang til ting som lever inne i main stack frame, men innerst inne, når vi kommer til pekere, bør som snart, dette er hva pekere er. Pekere er bare referanser til ting, og du kan bruke pekere tilgang til ting som er i andre ting "stable rammer. Så selv om tallene er lokale for main, kan vi fortsatt få tilgang til det gjennom denne pekeren. Men siden det er bare en peker, og det er bare en referanse, sizeof (høystakken) returnerer bare størrelsen av referansen selv. Den går ikke tilbake størrelsen på ting det er å peke på. Den går ikke tilbake den faktiske størrelsen på tall. Og slik at dette ikke kommer til å fungere som vi vil ha det til. Spørsmål om det? Pekere vil bli gått inn i betydelig mer blodig detalj i ukene som kommer. Og dette er grunnen til at mange ting som du ser, de fleste søk ting eller sortere ting, de er nesten alle kommer til å trenge å ta den faktiske størrelsen på matrisen, fordi i C, har vi ingen anelse om hva størrelsen på matrisen er. Du må manuelt gi det i. Og du kan ikke manuelt passere i hele matrisen fordi du er bare passerer i referansen og det kan ikke få størrelsen fra referansen. Okay. Så nå ønsker vi å gjennomføre det ble forklart før. Du kan jobbe på det for et øyeblikk, og du trenger ikke å bekymre deg for å få alt perfekt 100% arbeider. Bare skrive opp en halv pseudokode for hvordan du tror det skal fungere. Okay. Du trenger ikke å være helt ferdig med dette ennå. Men føles noen komfortabel med hva de har så langt, som noe vi kan jobbe med sammen? Ønsker noen å frivillig? Eller jeg vil tilfeldig plukke. Det trenger ikke å være rett ved andre tiltak, men noe vi kan endre til et fungerende stat. [Student] Sure. >> Ok. Så kan du lagre revisjon ved å klikke på den lille ikonet Lagre. Du ramya, ikke sant? >> [Student] Yeah. >> [Bowden] Okay. Så nå kan jeg vise revisjon og alle kan trekke opp revisjonen. Og her har vi - Ok. Så ramya gikk med den rekursive løsningen, som er definitivt en gyldig løsning. Det er to måter du kan gjøre dette problemet. Du kan enten gjøre det iterativt eller rekursivt. De fleste problemer du opplever som kan gjøres rekursivt kan også gjøres iterativt. Så her har vi gjort det rekursivt. Ønsker noen å definere hva det vil si å lage en funksjon rekursiv? [Student] Når du har en funksjon kalle seg og deretter kalle seg før det kommer ut med ekte og sann. >> Ja. En rekursiv funksjon er bare en funksjon som kaller seg. Det er tre store ting som en rekursiv funksjon må ha. Den første er åpenbart, kaller det selv. Den andre er base case. Så på et tidspunkt funksjonen må slutte å kalle seg selv, og det er hva base case er for. Så her vet vi at vi skal slutte, bør vi gi opp i våre søk når start lik slutt - og vi vil gå over hva det betyr. Men til slutt, det siste som er viktig for rekursive funksjoner: funksjonene eller annen måte må nærme seg base case. Som hvis du ikke faktisk oppdaterer noe når du gjør det andre rekursive kall, hvis du bokstavelig talt bare kalle funksjonen igjen med de samme argumentene og ingen globale variabler er endret eller noe, du vil aldri nå base case, i så fall det er ille. Det vil være en uendelig rekursjon og en stack overflow. Men her ser vi at oppdateringen skjer siden vi oppdaterer starte + end / 2, Vi oppdaterer slutten argumentet her, vi oppdaterer start argument her. Så i alle rekursive samtaler er vi oppdaterer noe. Okay. Vil du lede oss gjennom løsningen? >> Ja. Jeg bruker SearchHelp slik at hver gang jeg gjør denne funksjonen ringe Jeg har starten av hvor jeg ser etter i rekken og slutten hvor jeg ser tabellen. På hvert trinn der det er å si det er midt element, som er start + slutt / 2, er at lik det vi leter etter? Og hvis det er, så vi fant det, og jeg antar at blir sendt opp nivåer av rekursjon. Og hvis det ikke er sant, så sjekker vi om det midterste verdien i matrisen er for stor, i hvilket tilfelle vi se på venstre halvdel av matrisen ved å gå fra start til midten indeksen. Og ellers gjør vi slutten halvparten. [Bowden] Okay. Det høres bra ut. Ok, så et par ting, og faktisk er dette en meget høyt nivå ting at du aldri trenger å vite for dette kurset, men det er sant. Rekursive funksjoner, vil du alltid høre at de er en dårlig deal fordi hvis du rekursivt kaller deg for mange ganger, får du stack overflow siden, som jeg sa tidligere, får hver sin funksjon egen stack ramme. Så hver samtale av den rekursive funksjonen får sin egen stack ramme. Så hvis du gjør 1000 rekursive samtaler, får du 1000 stabel rammer, og raskt du føre til å ha for mange stabel rammer og ting bare bryte. Så det er derfor rekursive funksjoner er generelt dårlig. Men det er en fin undergruppe av rekursive funksjoner kalles tail-rekursive funksjoner, og dette skjer for å være et eksempel på en der om kompilatoren merknader dette og det skal, tror jeg - i Clang hvis du passerer det-O2 flagget så det vil merke dette er halen rekursive og gjøre ting bra. Det vil gjenbruke samme stack ramme igjen og igjen for hver rekursiv samtale. Og så siden du bruker den samme stabelen ramme, trenger du ikke å bekymre deg for noensinne stable overfylte, og på samme tid, som du sa før, der når du kommer tilbake sant, så det må returnere opp alle disse stabel rammer og den 10. kallet til SearchHelp har å gå tilbake til det 9., har å gå tilbake til det 8.. Så det trenger ikke å skje når funksjonene er halen rekursiv. Og så hva gjør denne funksjonen halen rekursive er varsel om at for en gitt samtale til SearchHelp den rekursive kall som det gjør er hva det tilbake. Så i den første samtalen til SearchHelp, vi enten umiddelbart return false, umiddelbart returnere true, eller vi gjør en rekursiv kall til SearchHelp der hva vi er tilbake er hva det ringes tilbake. Og vi kunne ikke gjøre dette hvis vi gjorde noe sånt int x = SearchHelp, retur x * 2, bare noen tilfeldige endringer. Så nå denne rekursive kall, denne int x = SearchHelp rekursiv samtale, ikke lenger hale rekursiv fordi det faktisk ikke å returnere tilbake til en tidligere stabel rammen slik at den forrige kallet til funksjonen Deretter kan gjøre noe med returverdi. Så dette er ikke hale rekursiv, men hva vi hadde før er pent halen rekursiv. Ja. [Student] Burde ikke andre base case kontrolleres første fordi det kan være en situasjon der når du passerer det argumentet du har start = slutt, men de er nålen verdi. Spørsmålet ble ikke kan vi kjøre inn i saken der slutten er nålen verdi eller start = slutt, riktig, start = slutt og du har faktisk ikke sjekket den aktuelle verdi ennå, deretter starte + end / 2 er bare kommer til å være den samme verdi. Men vi har allerede returnert falsk og vi vil aldri sjekket verdien. Så i det minste, i den første samtalen, hvis størrelse er 0, så vi ønsker å gå tilbake falske. Men hvis størrelsen er 1, så start ikke kommer til å like enden, og vi vil i det minste sjekke det ett element. Men jeg tror du har rett i at vi kan ende opp i en sak hvor begynner + end / 2, oppstart ender opp med å bli det samme som start + slutt / 2, men vi har aldri faktisk sjekket dette elementet. Så hvis vi først sjekke er midt element verdien vi leter etter, så kan vi umiddelbart returnere true. Else hvis de er like, så er det ingen vits i å fortsette siden vi bare kommer til å oppdatere til en sak hvor vi er på en enkelt-element array. Hvis det eneste element er ikke den vi leter etter, så alt er galt. Ja. [Student] Saken er at siden størrelsen er faktisk større enn antall av elementer i matrisen, Det er allerede en offset - >> Så vil størrelse - [Student] Si hvis matrisen var størrelse 0, så SearchHelp vil faktisk sjekke høystakk av 0 på den første ring. Matrisen har størrelse 0, så 0 er - >> Ja. Det er en annen ting som - det kan være bra. La oss tenke. Så hvis matrisen hadde 10 elementer og den mellomste vi kommer til å sjekke er indeks 5, så vi sjekker 5, og la oss si at verdien er mindre. Så vi kaster bort alt fra 5 og oppover. Så starter + end / 2 kommer til å bli vår nye end, så ja, det er alltid kommer til å bo utover slutten av tabellen. Hvis det er en sak dersom det var partall eller oddetall, så ville vi sjekke, sier, 4, men vi er fortsatt kaster bort - Så ja, er slutt alltid kommer til å være utenfor selve enden av tabellen. Så de elementene vi fokuserer på, er slutten alltid kommer til å være den etter det. Og så hvis start gjør stadig like enden, er vi i en rekke størrelse 0. Den andre tingen jeg tenkte er at vi oppdaterer start skal starte + end / 2, så dette er tilfelle at jeg har problemer med, hvor skal + end / 2 er elementet vi sjekker. La oss si at vi hadde denne 10-element array. Uansett. Så starter + end / 2 kommer til å være noe som dette, og hvis det er ikke verdien, sier vi vil oppdatere. Verdien er større, så vi ønsker å se på denne halvdelen av tabellen. Så hvordan vi oppdaterer start, skal vi oppdatere start nå være dette elementet. Men dette kan likevel fungere, eller i det minste, kan du gjøre start + slutt / 2 + 1. [Student] Du trenger ikke å være start + slutt [hørbar] >> Ja. Vi har allerede sjekket dette elementet og vet at det er ikke den vi leter etter. Slik at vi ikke trenger å oppdatere start til å være dette elementet. Vi kan bare hoppe over det og oppdatere begynne å være dette elementet. Og er det noen gang en sak, la oss si at dette var slutten, så da starter ville være dette, start + end / 2 ville være dette, start + slutt - Ja, jeg tror det kan ende opp i uendelig rekursjon. La oss si det er bare et utvalg av størrelse 2 eller en rekke størrelse 1. Jeg tror dette vil fungere. Så nå er starten at element og slutten er en utover det. Så element som vi kommer til å sjekke er denne, og når vi oppdaterer start, skal vi oppdatere start til å være 0 + 1/2, som kommer til å ende oss tilbake med start blir dette elementet. Så vi sjekker den samme element igjen og igjen. Så dette er tilfelle der hver rekursiv samtale må faktisk oppdatere noe. Så vi trenger å gjøre start + slutt / 2 + 1, ellers er det en sak der vi ikke egentlig oppdaterer start. Alle se det? Okay. Har noen spørsmål om denne løsningen eller flere kommentarer? Okay. Er det noen som har en iterativ løsning som vi alle kan se på? Har vi alle gjøre det rekursivt? Eller også jeg antar at hvis du åpnet hennes, så du kan ha overstyres det gamle. Betyr det automatisk lagre? Jeg er ikke positivt. Er det noen som har iterativ? Vi kan gå gjennom det sammen hvis ikke. Ideen er kommer til å være den samme. Iterativ løsning. Vi kommer til å ønske å utgangspunktet gjøre det samme ideen der vi ønsker å holde styr på den nye enden av tabellen og den nye starten av tabellen og gjøre det om og om igjen. Og hvis det vi holder styr på som starten og slutten noensinne møtes, da vi ikke fant den, og vi kan return false. Så hvordan gjør jeg det? Alle som har forslag eller kode for meg å trekke opp? [Student] Gjør en stund loop. >> Ja. Du kommer til å ønske å gjøre en loop. Visste du har koden jeg kunne trekke opp, eller hva skulle du foreslå? [Student] Jeg tror det. >> Greit. Dette gjør ting enklere. Hva var navnet ditt? [Student] Lucas. Revisjon 1. Okay. Low er det vi kalte starte før. Opp er ikke helt hva vi kalte slutten før. Egentlig er slutt nå i matrisen. Det er et element vi bør vurdere. Så lav er 0, er opp størrelsen av matrisen - 1, og nå er vi looping, og vi sjekker - Jeg antar du kan gå gjennom den. Hva var din tenkning gjennom dette? Lede oss gjennom koden din. [Student] Sure. Se på høystakken verdi i midten og sammenlign det med nål. Så hvis det er større enn nål ditt, så du vil - oh, faktisk, bør det være bakover. Du kommer til å ønske å kaste bort den høyre halvdelen, og så ja, det burde være slik. [Bowden] Så dette bør være mindre? Er det det du sa? >> [Student] Yeah. [Bowden] Okay. Mindre. Så hvis det vi ser på er mindre enn hva vi ønsker, så ja, vi ønsker å kaste bort den venstre halvdelen, som betyr at vi oppdaterer alt vi vurderer ved å flytte lav til høyre for matrisen. Dette ser bra ut. Jeg tror det har det samme problemet som vi sa på den forrige, der hvis lav er 0 og opp er 1, deretter lav + opp / 2 kommer til å sette opp til å bli det samme igjen. Og selv om det ikke er tilfelle, er det fortsatt mer effektiv i det minste å bare kaste bort elementet vi bare så på som vi vet er galt. Så lav + opp / 2 + 1 - >> [student] Det burde være den andre veien. [Bowden] Eller denne skal være - 1 og den andre en bør være + 1. [Student] Og det bør være en dobbel likhetstegn. >> [Bowden] Yeah. [Student] Yeah. Okay. Og til slutt, nå som vi har denne + 1 - 1 ting, er det - det kan ikke være - er det noen gang mulig for lav til å ende opp med en høyere verdi enn opp? Jeg tror den eneste måten som kan skje - Er det mulig? >> [Student] Jeg vet ikke. Men hvis det blir avkortet og da får minus at 1 og deretter - >> Ja. [Student] Det ville muligens bli søl opp. Jeg tror det skal være bra bare fordi for det å ende opp lavere de måtte være lik, tror jeg. Men hvis de er like, så vi ville ikke ha gjort det mens loop til å begynne med og vi ville bare ha returnert verdien. Så jeg tror vi bra nå. Legg merke til at selv om dette problemet er ikke lenger rekursive samme type ideer gjelder hvor vi kan se hvordan dette så lett gir seg til en rekursiv løsning av det faktum at vi bare oppdatering av indeksene igjen og igjen, vi gjør problemet mindre og mindre, fokuserer vi på en undergruppe av tabellen. [Student] Hvis lav er 0 og opp er en, ville de begge være 0 + 1/2, noe som ville gå til 0, og da ville være + 1, ville man være - en. [Student] Hvor er vi sjekker likestilling? Som hvis den midterste er faktisk nål? Vi er ikke tiden gjør det? Oh! Hvis det er - Ja. Vi kan ikke bare gjøre testen her nede fordi la oss si den første midten - [Student] Det er faktisk liker ikke kaste bort den bundne. Så hvis du kaster bort bundet, må du sjekke det første eller hva. Ah. Ja. >> [Student] Yeah. Så nå har vi kastet bort den vi i dag sett på, noe som betyr at vi nå må også ha if (høystakken [(lav + opp) / 2] == p), så kan vi returnere true. Og om jeg legger andre eller bare hvis, det betyr bokstavelig talt det samme fordi dette ville ha returnert sant. Så jeg skal sette else if, men det spiller ingen rolle. Så annet hvis dette, ellers dette, og dette er en vanlig ting jeg gjør der selv om det er tilfelle der alt er bra her, som lav aldri kan være større enn opp, er det ikke verdt resonnement om hvorvidt det er sant. Så du kan like godt si mens lav er mindre enn eller lik eller mens lav er mindre enn så hvis de noen gang likt eller lav skjer til å passere, så kan vi bryte ut av denne loopen. Spørsmål, bekymringer, kommentarer? Okay. Dette ser bra ut. Nå ønsker vi å gjøre slag. Hvis vi går til min andre revisjon, ser vi de samme tallene, men nå er de ikke lenger i sortert rekkefølge. Og vi ønsker å implementere Sorter etter en algoritme O n log n. Så hvilken algoritme tror du vi bør iverksette her? >> [Student] Merge sort. [Bowden] Yeah. Flette sort er O (n log n), så det er det vi kommer til å gjøre. Og problemet kommer til å bli ganske lik, der det gir lett seg en rekursiv løsning. Vi kan også komme opp med en iterativ løsning hvis vi vil, men rekursjon vil være lettere her, og vi skal gjøre rekursjon. Jeg tror vi vil gå gjennom flette slag først, selv om det er en nydelig video på Merge slags allerede. [Latter] Så flette slags det er - jeg kaster bort så mye av dette papiret. Å, det er bare en igjen. Så flette. Oh, 1, 3, 5. Okay. Merge tar to separate arrays. Individuelt de to arrayene er begge sorteres. Så denne matrise, 1, 3, 5, sortert. Denne matrise, 0, 2, 4, sortert. Nå hva fusjonere bør gjøre er å kombinere dem i en enkelt rekke som selv sortert. Så vi ønsker en rekke størrelse 6 som kommer til å ha disse elementene innsiden av det i sortert rekkefølge. Og så kan vi dra nytte av det faktum at disse to arrays er sortert å gjøre dette i lineær tid, lineær tid mening hvis denne tabellen er størrelse x og dette er størrelsen y, deretter den totale algoritme bør være O (x + y). Okay. Så forslag. [Student] Kan vi starte fra venstre? Så du vil sette 0 ned først og deretter 1 og deretter her du er på 2. Så det er litt som du har en fane som skal flytte til høyre. >> [Bowden] Yeah. For begge disse arrays hvis vi bare fokusere på den venstre element. Fordi begge arrays er sortert, vet vi at disse to elementene er de minste elementene i enten array. Så det betyr at en av de to elementene må være det minste elementet i vår fusjonerte array. Det bare så skjer at den minste er en på rett denne gangen. Så vi tar 0, sett den på venstre fordi 0 er mindre enn 1, så ta 0, sette det inn i vår første posisjon, og da vi oppdatere denne å nå fokusere på det første elementet. Og nå har vi gjenta. Så nå er vi sammenligne to og en. 1 er mindre, så vi får sett 1. Vi oppdaterer denne pekeren til å peke til denne fyren. Nå gjør vi det igjen, så to. Dette vil oppdatere, sammenligne disse to, tre. Dette oppdaterer, deretter 4 og 5. Så det er flettingen. Det bør være ganske åpenbart at det er lineær tid siden vi bare gå over hvert element gang. Og det er den største skritt for å implementere fusjonere slags gjør dette. Og det er ikke så vanskelig. Et par ting å bekymre seg er la oss si at vi ble sammenslåing 1, 2, 3, 4, 5, 6. I dette tilfellet ender vi opp i situasjonen der dette kommer til å bli mindre, så vi oppdaterer denne pekeren, er dette en kommer til å være mindre, oppdatere denne, dette er mindre, og nå må du kjenne når du faktisk har kjørt ut av elementer for å sammenligne med. Siden vi allerede har brukt hele denne array, alt i denne matrisen er nå bare satt inn her. Så hvis vi noen gang får det punktet hvor en av våre arrays er helt fusjonert allerede, så vi bare ta alle elementene i den andre rekke og sette dem inn i slutten av tabellen. Så vi kan bare sette 4, 5, 6. Okay. Det er én ting å se opp for. Implementering som bør være trinn 1. Flett sortere da basert på det, det er to trinn, to dumme trinn. La oss bare gi denne tabellen. Så flette slag, er trinn 1 til rekursivt bryte rekken i halvdeler. Så dele denne tabellen i halvdeler. Vi har nå 4, 15, 16, 50 og 8, 23, 42, 108. Og nå gjør vi det igjen, og vi delt disse inn halvdeler. Jeg vil bare gjøre det på denne siden. SO 4, 15 og 16, 50. Vi ville gjøre det samme over her. Og nå har vi delt det inn i halvdeler igjen. Og vi har 4, 15, 16, 50. Så det er vår base case. Når arrays er av størrelse 1, så vi stoppe med delingen i halvdeler. Nå hva gjør vi med dette? Vi ender opp dette vil også brytes ned i 8, 23, 42, og 108. Så nå som vi er på dette punktet, nå trinn to av fletting slag er bare å flette par til listene. Så vi ønsker å slå sammen disse. Vi bare ringe flette. Vi vet fusjonere vil returnere disse i sortert rekkefølge. 4, 15. Nå ønsker vi å flette disse, og som vil returnere en liste med de i sortert rekkefølge, 16, 50. Vi fletter dem - jeg kan ikke skrive - 8, 23 og 42, 108. Så vi har fusjonert par gang. Nå er vi bare slå igjen. Legg merke til at hver av disse listene er sortert i seg selv, og da kan vi bare slå sammen disse listene for å få en liste over størrelse 4 som er sortert og slå sammen disse to listene for å få en liste over størrelse 4 som er sortert. Og til slutt, kan vi slå de to lister over størrelsen 4 for å få en liste over størrelsen 8 som er sortert. Så for å se at dette er generelle n log n, vi allerede så at flettingen er lineær, så når vi har å gjøre med sammenslåing disse, så som den totale kostnaden for flettingen for disse to listene er bare 2 fordi - Eller vel, det er O av n, men n her er bare disse to elementene, så det er to. Og disse to vil være 2, og disse to vil være 2, og disse to vil være 2, så over alle de fusjonerer som vi trenger å gjøre, ender vi opp med å gjøre n. Som 2 + 2 + 2 + 2 er 8, som er n, slik at kostnaden for sammenslåing i dette settet er n. Og så det samme her. Vi vil slå sammen disse to, da disse to, og individuelt denne sammenslåingen vil ta fire operasjoner, Dette fusjonere vil ta fire operasjoner, men nok en gang, mellom alle disse, vi ender opp sammenslåing n totalt ting, og så dette trinnet tar n. Og så hvert nivå tar n elementer blir slått sammen. Og hvor mange nivåer er det? På hvert nivå, vokser vår rekke av størrelse 2. Her våre arrays er av størrelse 1, her er de på størrelse 2, her er de i størrelse 4, og til slutt, de er av størrelse 8. Så siden det er en dobling, er det kommer til å være totalt log n av disse nivåene. Så med log n nivåer, hvert enkelt nivå tar n samlede virksomhet, vi får en n log n algoritme. Spørsmål? Har folk allerede gjort fremskritt på hvordan å gjennomføre dette? Er det noen som allerede er i en tilstand hvor jeg kan bare trekke opp koden sin? Jeg kan gi et minutt. Dette kommer til å bli lenger. Jeg anbefaler går igjen - Du trenger ikke å gjøre rekursjon for flettingen fordi å gjøre rekursjon for flettingen, du nødt til å passere en haug med forskjellige størrelser. Du kan, men det er irriterende. Men rekursjon for sortering seg selv er ganske enkelt. Du bare bokstavelig ringe slag på venstre halvdel, sortere på høyre halvdel. Okay. Alle som har noe jeg kan trekke opp ennå? Ellers vil jeg gi et minutt. Okay. Alle som har noe vi kan jobbe med? Ellers får vi bare jobbe med dette og deretter utvide derfra. Alle som har mer enn dette at jeg kan trekke opp? [Student] Yeah. Du kan trekke opp mine. >> Greit. Ja! [Student] Det var mange forhold. >> Å, skyte. Kan du - [Student] Jeg må lagre det. >> Ja. Så vi gjorde gjøre flettingen separat. Oh, men det er ikke så ille. Okay. Så slags er i seg selv bare å ringe mergeSortHelp. Forklare oss hva mergeSortHelp gjør. [Student] MergeSortHelp ganske gjør mye de to hovedtrinn, som er å sortere hver halvdel av matrisen, og deretter å slå dem begge. [Bowden] Ok, så gi meg et sekund. Jeg tror dette - >> [student] Jeg trenger å - Ja. Jeg mangler noe. I merge, innser jeg at jeg må opprette en ny matrise fordi jeg ikke kunne gjøre det på plass. >> Ja. Du kan ikke. Korrigere. [Student] Så jeg oppretter en ny matrise. Jeg glemte på slutten av fusjonerer til re-endre. Okay. Vi trenger en ny rekke. I flette slag, er dette nesten alltid sant. Del av kostnaden for en bedre algoritme tidsmessig er nesten alltid ønsker å bruke litt mer minne. Så her, uansett hvordan du gjør flette sortere, du ville uunngåelig trenger å bruke litt ekstra minne. Han eller hun opprettet en ny array. Og så sier du på slutten vi bare trenger å kopiere ny rekke i den opprinnelige matrisen. [Student] Jeg tror det, ja. Jeg vet ikke om det fungerer i forhold til å telle ved henvisning eller hva - Ja, det vil fungere. >> [Student] Okay. Visste du prøve å kjøre dette? >> [Student] Nei, ikke ennå. >> Ok. Prøve å kjøre den, og så skal jeg snakke om det for et sekund. [Student] Jeg trenger å ha alle funksjoner prototyper og alt, ikke sant? Funksjonstastene prototyper. Å, du mener som - Ja. Sorter kaller mergeSortHelp. Så for at sortere å ringe mergeSortHelp, må mergeSortHelp enten er definert før sorter eller vi trenger bare en prototype. Bare kopier og lim det. Og på samme måte, er mergeSortHelp ringer flette, men flettingen ikke er definert ennå, så vi kan bare la mergeSortHelp vite at det er det flette kommer til å se ut, og det er det. Så mergeSortHelp. Vi har et problem her hvor vi har ingen base case. MergeSortHelp er rekursiv, så noen rekursiv funksjon kommer til å trenge noen form for base case å vite når du skal stoppe rekursivt å kalle seg selv. Hva er vår base case kommer til å bli her? Ja. [Student] Hvis størrelsen er en? >> [Bowden] Ja. Så som vi så der, vi stoppet splitting arrays når vi fikk inn matriser av størrelse 1, som uunngåelig er sortert seg selv. Så hvis størrelsen er lik 1, vet vi matrisen er allerede sortert, så vi kan bare gå tilbake. Legg merke til at er ugyldig, slik at vi ikke kommer tilbake noe spesielt, vi bare tilbake. Okay. Så det er vår base case. Jeg tror vår base case kan også være hvis vi måtte være en sammenslåing en rekke størrelse 0, vi sannsynligvis vil stoppe på et tidspunkt, så vi kan bare si størrelse mindre enn 2 eller mindre enn eller lik 1 slik at dette vil fungere for enhver matrise nå. Okay. Så det er vår base case. Nå trenger du ønsker å lede oss gjennom flettingen? Hva gjør alle disse tilfellene betyr? Her oppe, vi bare gjør det samme idé, - [Student] Jeg trenger å være bestått størrelse med alle mergeSortHelp samtaler. Jeg har lagt størrelse som en ekstra primære og det er ikke der, som størrelse / 2. [Bowden] Oh, størrelse / 2, størrelse / 2. >> [Student] Ja, og også i den ovenfor fungerer så godt. [Bowden] Her? >> [Student] Bare størrelse. >> [Bowden] Oh. , Størrelse? >> [Student] Yeah. [Bowden] Okay. La meg tenke et sekund. Kjøre vi inn i en sak? Vi er alltid behandle venstre som 0. >> [Student] Nei Det er også galt. Unnskyld. Det bør være start. Ja. [Bowden] Okay. Jeg liker det bedre. Og slutten. Okay. Så nå vil du lede oss gjennom flettingen? >> [Student] Okay. Jeg bare vandre gjennom denne nye utvalget som jeg har laget. Dens størrelse er størrelsen av den del av matrisen som vi ønsker å være sortert og prøver å finne elementet som jeg skal legge i det nye utvalget trinn. Så for å gjøre det, først skal jeg sjekke om den venstre halvdelen av tabellen fortsetter å ha noen flere elementer, og hvis det ikke gjør det, så du går ned til det andre tilstand, som bare sier okay, det må være i riktig array, og vi vil sette det i dagens indeks newArray. Og så ellers, jeg sjekke om høyre side av tabellen er også ferdig, i så fall bare jeg satt i venstre. Det kan faktisk ikke være nødvendig. Jeg er ikke sikker. Men uansett, de to andre sjekk hvilke av de to er mindre i venstre eller høyre. Og også i hvert enkelt tilfelle, jeg økes hvilken plassholder jeg øke. [Bowden] Okay. Det ser bra ut. Har noen kommentarer eller bekymringer eller spørsmål? Så de fire sakene som vi må ta ting i bare å være - eller det ser ut som fem - men vi må vurdere om den venstre tabellen har gått tom for ting vi trenger å fusjonere, om retten utvalg har gått tom for ting vi trenger å fusjonere - Jeg peker på noe. Så om den venstre tabellen har gått tom for ting eller rett matrisen har gått tom for ting. De er to tilfeller. Vi trenger også trivielle tilfelle av hvorvidt den venstre ting er mindre enn det rette. Så vi ønsker å velge den venstre tingen. De er de tilfeller. Så dette var rett, så det er det. Array igjen. Det er 1, 2, 3. Okay. Så ja, de er de fire tingene vi kanskje vil gjøre. Og vi vil ikke gå over en iterativ løsning. Jeg vil ikke anbefale - Flette sorter er et eksempel på en funksjon som er både ikke hale rekursive det er ikke lett å gjøre det halen rekursive men også det er ikke veldig lett å gjøre det iterativ. Dette er veldig enkelt. Denne implementasjonen av fletting slag, flette, uansett hva du gjør, du kommer til å bygge flettingen. Så flette slag bygget på toppen av Merge rekursivt er bare disse tre linjene. Iterativt, er det mer irriterende og vanskeligere å tenke på. Men merker at det ikke er halen rekursive siden mergeSortHelp - når den kaller seg selv - det fortsatt behov for å gjøre ting etter dette rekursive kallet returnerer. Så denne bunken rammen må fortsette å eksistere selv etter ringer dette. Og så når du ringer dette må stabelen rammen fortsette å eksistere fordi selv etter at samtalen, vi trenger fortsatt å fusjonere. Og det er nontrivial å gjøre denne halen rekursiv. Spørsmål? OK. Så kommer tilbake for å sortere - oh, det er to ting jeg vil vise. Okay. Går tilbake til å sortere, vil vi gjøre dette raskt. Eller søk. Slag? Sorter. Ja. Går tilbake til begynnelsen av slag. Vi ønsker å lage en algoritme som sorterer tabellen ved hjelp av en algoritme i O n. Så hvordan er dette mulig? Har noen noen form for - Jeg antydet før på - Hvis vi er i ferd med å forbedre seg n log n til O av n, Vi har forbedret vår algoritme tidsmessig, noe som betyr hva vi kommer til å trenge å gjøre for å gjøre opp for det? [Student] Space. >> Ja. Vi kommer til å bruke mer plass. Og ikke engang bare mer plass, er det eksponentielt mer plass. Så jeg tror denne typen algoritme er pseudo noe, pseudo polynom - pseudo - Jeg kan ikke huske. Pseudo noe. Men det er fordi vi trenger å bruke så mye plass at dette er oppnåelig, men ikke realistisk. Og hvordan oppnår vi dette? Vi kan oppnå dette dersom vi garantere at en bestemt element i matrisen er under en viss størrelse. Så la oss bare si at størrelsen er 200, noe element i en matrise er under størrelse 200. Og dette er faktisk veldig realistisk. Du kan veldig lett ha en matrise som du vet alt i det kommer til å være mindre enn et antall. Som hvis du har noen helt enormt vektor eller noe men du vet alt kommer til å være mellom 0 og 5, så det kommer til å være betydelig raskere å gjøre dette. Og den bundne på noen av elementene er 5, så dette bundet, som er hvor mye minne du skal bruke. Så det bundne er 200. I teorien er det alltid en bundet siden et heltall kan bare være opp til 4 milliarder kroner, men det er urealistisk siden da vi skulle bruke plass i størrelsesorden 4 milliarder kroner. Så det er urealistisk. Men her vil vi si vår grense er 200. Kunsten å gjøre det i O av n er vi foreta en ny array kalt tellinger av størrelse BUNDET. Så egentlig er dette en snarvei for - jeg faktisk ikke vet om Clang gjør dette. Men i GCC i det minste - jeg antar Clang gjør det også - Dette vil bare starte hele array å være 0s. Så hvis jeg ikke ønsker å gjøre det, så jeg kunne separat gjøre for (int i = 0; i > Ok. Jeg innså en annen ting når vi skulle gjennom. Jeg tror problemet var i Lucas 'og trolig hver eneste vi har sett. Jeg glemte helt. Det eneste jeg ønsket å kommentere er at når du arbeider med ting som indekser, du aldri virkelig se dette når du skriver en for løkke, men teknisk, når du arbeider med disse indeksene, du bør stort sett alltid forholde seg til usignerte heltall. Grunnen til dette er når du arbeider med signerte heltall, så hvis du har 2 signert heltall og du legger dem sammen og de ender opp for stor, så du ender opp med et negativt tall. Så det er hva heltallsoverflyt er. Hvis jeg legger 2 milliarder og 1 milliard, ender jeg opp med negativ 1 milliard. Det er hvordan heltall arbeider på datamaskiner. Så problemet med å bruke - Det er fint bortsett fra hvis lav skjer for å være 2 milliarder og opp skjer for å være 1 milliard, så dette kommer til å være negativ 1 milliard og deretter skal vi dele det med 2 og ender opp med negativ 500 millioner. Så dette er bare et problem hvis du tilfeldigvis være å søke gjennom en rekke milliarder av ting. Men hvis lav + opp skjer med overløp, så det er et problem. Så snart vi gjør dem usignert, deretter 2 milliarder pluss 1 milliard er 3 milliarder kroner. 3000000000 delt på 2 er 1,5 milliarder kroner. Så så snart de er usignerte, alt er perfekt. Og så det er også et problem når du skriver din for looper, og faktisk, det sannsynligvis det automatisk. Det vil faktisk bare kjefte på deg. Så hvis dette tallet er for stor til å være i akkurat et heltall, men det ville passe i en usignert heltall, det vil kjefte på deg, så det er derfor du aldri virkelig kjøre inn i saken. Du kan se at en indeks aldri kommer til å være negativ, og så når du gjentar i en matrise, du kan nesten alltid si usignert int i, men du egentlig ikke må. Ting kommer til å jobbe ganske mye like bra. Okay. [Hvisker] Hva er klokka? Den siste tingen jeg ønsket å vise - og jeg vil bare gjøre det virkelig rask. Du vet hvordan vi har # define slik at vi kan # define MAX som 5 eller noe? La oss ikke gjøre MAX. # Define BUNDET som 200. Det er hva vi gjorde før. Som definerer en konstant, som bare kommer til å bli kopiert og limt inn uansett hvor vi måtte skrive bundet. Så vi kan faktisk gjøre mer med # definerer. Vi kan # definere funksjoner. De er egentlig ikke fungerer, men vi vil kalle dem funksjoner. Et eksempel kan være noe sånt som MAX (x, y) er definert som (x > Ideelt sett 14. Problemet er at hvordan hasj definerer arbeid, husk det er en bokstavelig kopiere og lime på stort sett alt, så hva dette kommer til å bli tolket som er 3 mindre enn 1 pluss 6, 2 ganger 1 pluss 6, 2 ganger 3. Så på grunn av dette nesten alltid du bryte alt i parentes. Enhver variabel du nesten alltid bryte i parentes. Det er tilfeller der du ikke trenger å, som jeg vet at jeg ikke trenger å gjøre det her fordi mindre enn det som er stort sett alltid bare kommer til å fungere, selv om det kanskje ikke engang være sant. Hvis det er noe latterlig som DOUBLE_MAX (1 == 2), så det kommer til å bli erstattet med tre mindre enn 1 er lik lik 2, og så så det kommer til å gjøre 3 mindre enn 1, betyr det lik 2, som er ikke hva vi ønsker. Så for å unngå eventuelle operatorpresedens problemer, alltid brytes i parentes. Okay. Og det er det, 5:30. Hvis du har noen spørsmål om pset, gi oss beskjed. Det skal være moro, og hackeren utgaven også er mye mer realistisk enn hacker utgave av fjorårets, så vi håper at mange av dere prøver. Fjorårets var veldig overveldende. [CS50.TV]