[Powered by Google Translate] [Avsnitt 3 - Mer Bekväm] [Rob Bowden - Harvarduniversitetet] [Detta är CS50. - CS50.TV] Så den första frågan konstigt formulerad. GDB kan du "felsöka" ett program, men mer specifikt, vad kan du göra? Jag svarar att en, och jag vet inte exakt vad som förväntas, så jag gissar att det är något i stil med det kan du steg för steg gå igenom programmet, interagera med, ändra variabler, göra alla dessa saker - princip helt styra exekvering av ett program och inspektera varje given del av genomförandet av programmet. Så dessa funktioner kan du felsöka saker. Okej. Varför kräver binär sökning som en array sorteras? Vem vill svara på det? [Eleven] Eftersom det inte fungerar om det inte sorteras. >> Ja. [Skratt] Om det inte sorteras, då är det omöjligt att dela den på mitten och vet att allt till vänster är mindre och allt till höger är större än det mittersta värdet. Så det måste sorteras. Okej. Varför är bubbla typ i O n kvadrat? Vill någon först ge en mycket snabb hög nivå översikt över vad bubbla sortera är? [Eleven] Du princip gå igenom varje element och du kolla de första delarna. Om de är ute var du byta dem, kan du kontrollera de närmaste delarna och så vidare. När du når slutet, då vet du att det största elementet är placerat i slutet, så du ignorerar att en då du håller på att gå igenom, och varje gång du måste kolla en mindre del tills du gör några ändringar. >> Ja. Det kallas bubbla Sortera eftersom om du vänder matrisen på sidan så det är upp och ner, vertikal, då de stora värdena kommer att sjunka till botten och de små värdena kommer att bubbla upp till toppen. Det är hur det fick sitt namn. Och ja, du går bara igenom. Du fortsätter att gå igenom arrayen, byta ut större värde att få de största värdena till botten. Varför är det O n kvadrat? Först, inte vill att någon ska säga varför det är O n kvadrat? [Elev] Eftersom för varje körning går n gånger. Du kan bara vara säker på att du har tagit den största delen hela vägen ner, då måste man upprepa det så många delar. >> Ja. Så kom ihåg vad Big O betyder och vilka stora Omega innebär. Den stora O är som den övre gränsen på hur långsamt det kan faktiskt köra. Så genom att säga att det är O n kvadrat, är det inte O n annars skulle kunna köra i linjär tid, men det är O n kubik eftersom den begränsas av O n kubik. Om det är avgränsas av O n kvadrat, då är det avgränsas också av n kubik. Så det är n kvadrat, och i absolut värsta fall inte kan göra bättre än n kvadrat, vilket är varför det är O n kvadrat. Så för att se lätt matematik på hur det kommer sig vara n kvadrat, om vi har fem saker i vår lista, första gången hur många swappar kunde vi behöver eventuellt göra för att få det? Låt oss faktiskt bara - Hur många swappar ska vi behöva göra i den första körningen av bubbla sortera arrayen? [Eleven] n - 1. >> Ja. Om det finns 5 delar, kommer vi att behöva göra n - 1. Sedan den andra en hur många swappar ska vi behöva göra? [Eleven] n - 2. >> Ja. Och den tredje kommer att vara n - 3 och därefter för enkelhetens jag kommer att skriva de två sista som då vi kommer att behöva göra 2 swappar och 1 swap. Jag antar den sista eller inte kan faktiskt behöva hända. Är det en swap? Jag vet inte. Så dessa är de totala mängderna av swappar eller åtminstone jämförelser du måste göra. Även om du inte byta, måste du ändå jämföra värdena. Så det finns n - 1 jämförelser i den första körningen genom uppsättningen. Om du ordna dessa saker, låt oss faktiskt göra det sex saker så saker stack upp snyggt, och då ska jag göra 3, 2, 1. Så bara ordna dessa summor vill vi se hur många jämförelser vi gör i hela algoritmen. Så om vi tar de här killarna här nere, då vi fortfarande bara summera hur många jämförelser fanns. Men om vi summerar dessa och vi summerar dessa och vi summerar dessa, det är fortfarande samma problem. Vi summerar bara just dessa grupper. Så nu är vi summera 3 ns. Det är inte bara 3 ns. Det kommer alltid att vara n / 2 ns. Så här har vi råkar ha 6. Om vi ​​hade 10 saker vi kunde göra detta gruppering för 5 olika par saker och sluta med n + n + n + n + n. Så att du alltid kommer att få n / 2 ns, och så detta kommer vi krafsa ut det till n kvadrat / 2. Och så även om det är faktorn halv, som råkar komma i grund av det faktum att genom varje iteration över arrayen vi jämför 1 mindre så det är hur vi får över 2, men det är fortfarande n kvadrat. Vi bryr oss inte om den konstanta faktorn för en halv. Så många Big O sånt här förlitar sig på bara typ att göra denna typ av matematik, gör aritmetiska summor och geometriska serier grejer, men de flesta av dem i denna kurs är ganska enkelt. Okej. Varför är införandet Sortera i Omega n? Vad betyder omega? [Två studenter talar på en gång - obegripliga] >> yeah. Omega du kan tänka på som nedre gräns. Så oavsett hur effektiv din insättning Sortera algoritm är, oavsett den lista som har passerat i, har det alltid jämföra minst n ting eller det måste iterera över n saker. Varför det? [Eleven] För om listan redan sorteras, sedan genom den första iterationen Du kan bara garantera att den allra första elementet är minst, och den andra iterationen kan endast garantera de första två är eftersom du inte vet att resten av listan är sorterad. >> Ja. Om du skickar i en helt sorterad lista, åtminstone du måste gå över alla element att se att ingenting behöver flyttas runt. Så passerar över listan och säger åh, detta redan sorteras, det är omöjligt för dig att veta att det är sorterade tills du kontrollera varje del att se till att de är i sorterad ordning. Så nedre gräns för insättning typ är Omega n. Vad är det värsta fallet gångtid sammanslagning sortera, värsta fall är Big O igen? Så i värsta fall, hur merge sort kör? [Eleven] n log n. >> Ja. De snabbaste generella sortering algoritmer är n log n. Du kan inte göra bättre. Det finns särskilda fall, och om vi har tid i dag - men vi förmodligen won't - kunde vi se en som gör bättre än n log n. Men i det allmänna fallet kan du inte bättre än n log n. Och sammanfoga Sortera råkar vara den du bör veta för denna kurs som är n log n. Och så kommer vi faktiskt genomföra det i dag. Och slutligen, i högst tre meningar, hur fungerar val Sortera? Vill någon svara, och jag ska räkna dina meningar för om du går över 3 - Minns någon val Sortera? Val Sortera är oftast ganska lätt att komma ihåg bara från namnet. Du bara iterera över arrayen, hitta vad det största värdet är eller minsta - vilken ordning du sorterar i. Så låt oss säga att vi sorterar från minsta till största. Du iterera över arrayen, söker oavsett minsta elementet är, markera den och sedan bara byta den allt som finns i första hand. Och sedan på den andra passerar över arrayen, leta efter minsta elementet igen, markera den och sedan byta den med vad som finns i det andra läget. Så vi bara plocka och välja de lägsta värdena och föra in dem i den främre delen av matrisen tills den sorteras. Frågor på det? Dessa visas oundvikligen i de former som du måste fylla i när du skickar in pset. De är i stort sett svaren på dem. Okej, så nu kodning problem. Jag skickade redan ut över e-post - Var det någon inte få att e-post? Okej. Jag skickade redan ut över e-post det utrymme som vi kommer att använda, och om du klickar på mitt namn - så jag tror jag kommer att vara i botten på grund av den bakåt R - men om du klickar på mitt namn ser du 2 revideringar. Revidering 1 kommer att jag redan kopieras och klistras in koden i Spaces för sökningen sak du kommer att behöva genomföra. Och revision 2 kommer att vara den typ sak som vi genomför efter det. Så du kan klicka på min Revision 1 och arbeta därifrån. Och nu vill vi genomföra binär sökning. Vill någon att bara ge en pseudokod hög nivå förklaring av vad vi kommer att behöva göra för sökning? Ja. [Eleven] Du tar bara mitten av matris och se om det du letar efter är mindre än eller mer än så. Och om det är mindre, går du till hälften är mindre, och om det är mer, går du till halv som är mer och du upprepa det tills du får bara en sak. [Bowden] Ja. Observera att våra nummer array redan sorteras, och så det betyder att vi kan dra nytta av detta och vi kan först kontrollera, Okej, jag letar efter numret 50. Så jag kan gå in i mitten. Mitten är svårt att definiera när det är ett jämnt antal saker, men låt oss bara säga att vi alltid kommer trunkera till mitten. Så här har vi 8 saker, så i mitten skulle vara 16. Jag letar efter 50, så 50 är större än 16. Så nu kan jag i princip behandla min array som dessa element. Jag kan kasta bort allt från 16 över. Nu är min matris är bara dessa 4 element, och jag upprepar. Så då vill jag hitta mitten igen, vilket kommer att bli 42. 42 är mindre än 50, så jag kan kasta bort dessa två element. Detta är min återstående matris. Jag ska hitta mitten igen. Jag antar att 50 var ett dåligt exempel eftersom jag var alltid kasta bort saker till vänster, men samma åtgärd, om jag letar efter något och det är mindre än elementet jag för närvarande är ute på, då ska jag kasta bort allt till höger. Så nu måste vi genomföra det. Observera att vi måste gå i storlek. Vi kan inte heller behöver hård-kod storlek. Så om vi bli av med den # define - Okej. Hur kan jag räkna fint ut vad storleken på siffrorna arrayen närvarande är? Hur många element är i siffrorna arrayen? [Studerande] Siffror, konsoler,. Längd? [Bowden] som inte finns i C. Behöver. Längd. Arrayer inte har egenskaper, så det finns ingen längd egendom matriser som bara kommer att ge dig hur lång tid det råkar vara. [Elev] Se hur mycket minne den har och dividera med hur mycket - >> Ja. Så hur kan vi se hur mycket minne den har? >> [Elev] sizeof. >> Ja, sizeof. Sizeof är den operatör som kommer att returnera storleken på siffrorna arrayen. Och det kommer att bli men många heltal finns det tillfällen storleken av ett heltal eftersom det är hur mycket minne det faktiskt tar upp. Så om jag vill ha många saker i matrisen, då ska jag vill dela av storleken på ett heltal. Okej. Så det låter mig passera i storlek här. Varför måste jag passera i storlek alls? Varför kan jag inte bara göra här uppe int size = sizeof (höstack) / sizeof (int)? Varför fungerar det inte? [Elev] Det är inte en global variabel. [Bowden] Haystack finns och vi passerar i antal som höstack, och detta är lite av en föraning om vad som komma skall. Ja. [Elev] Haystack är bara hänvisa till det, så det skulle återvända hur stor en sådan hänvisning. Ja. Jag tvivlar på föreläsning som du har sett stapeln ännu inte riktigt, eller hur? Vi har just talat om det. Så stack är där alla dina variabler kommer att lagras. Varje minne som är tilldelade för lokala variabler går i stacken, och varje funktion får sitt eget utrymme på stacken, är sin egen stack ram vad det kallas. Så stora har sin stack ram och inuti det kommer att finnas här siffrorna array, och det kommer att vara av storlek sizeof (tal). Det kommer att ha storlek med siffror uppdelade efter storlek av element, men att alla bor inom huvud stack ram. När vi kallar sökning, får söka sin egen stack ram, sitt eget utrymme för att lagra alla sina lokala variabler. Men dessa argument - så höstack är inte en kopia av hela denna uppsättning. Vi klarar inte i hela arrayen som en kopia i sökning. Det går bara en referens till den arrayen. Så sökning kan komma åt dessa siffror genom denna referens. Det är fortfarande komma åt saker som lever inne i huvud stack ram, men i grunden, när vi kommer till pekare, vilket bör vara snart, detta är vad pekare är. Pekare är bara referenser till saker, och du kan använda pekare att komma åt saker som är i annat "stack ramar. Så även om siffrorna är lokal till viktigaste, kan vi komma åt den genom denna pekare. Men eftersom det är bara en pekare och det är bara en referens, sizeof (höstack) returnerar bara storleken på själva referensen. Det returnerar inte storleken på sak det pekar på. Det returnerar inte den faktiska storleken på tal. Och så detta kommer inte att fungera som vi vill. Frågor på det? Pekare kommer att vara borta i betydligt mera blodig detalj i veckor framöver. Och det är därför en massa saker som du ser, det mesta sökning eller saker sortera, de är nästan alla kommer att behöva ta den verkliga storleken av arrayen, eftersom C har vi ingen aning om vad storleken på arrayen är. Du måste manuellt föra in den Och du kan inte manuellt gå i hela arrayen eftersom du bara passerar i referens och det kan inte få storleken från referensvärdet. Okej. Så nu vill vi genomföra det förklarades tidigare. Du kan arbeta på det under en minut, och du behöver inte oroa dig för att få allt perfekt 100% arbetar. Bara skriva upp halv pseudokod för hur du tror att det ska fungera. Okej. Du behöver vara helt klar med detta ännu. Men känner någon bekväm med vad de har än så länge, som något vi kan arbeta med tillsammans? Vill någon att volontär? Eller jag kommer slumpmässigt välja. Det behöver inte vara rätt av varje åtgärd, men något vi kan ändra till ett fungerande tillstånd. [Elev] Visst. >> Okej. Så kan du spara en översyn genom att klicka på den lilla ikonen Spara. Du Ramya, eller hur? >> [Elev] Ja. >> [Bowden] Okej. Så nu kan jag se din revision och alla kan dra upp översynen. Och här har vi - Okej. Så Ramya gick med rekursiva lösningen, som är definitivt en giltig lösning. Det finns två sätt att göra detta problem. Du kan antingen göra det iterativt eller rekursivt. De flesta problem du stöter på som kan göras rekursivt kan också göras iterativt. Så här har vi gjort det rekursivt. Vill någon att definiera vad det innebär att göra en funktion rekursiv? [Elev] När du har en funktion kallar sig och sedan kalla sig tills den kommer ut med sann och äkta. >> Ja. En rekursiv funktion är bara en funktion som kallar sig. Det finns tre stora saker som en rekursiv funktion måste ha. Den första är naturligtvis kallar det själv. Den andra är basfallet. Så någon gång funktionen måste sluta kalla sig, och det är vad basfallet är till för. Så här vet vi att vi måste sluta, måste vi ge upp i vårt sökande När börjar lika slut - och vi ska gå igenom vad det betyder. Men slutligen, det sista som är viktigt för rekursiva funktioner: funktionerna måste på något sätt närma sig basfallet. Som om du inte är egentligen uppdaterar något när du gör den andra rekursiva anropet, om du bokstavligen bara anropa funktionen igen med samma argument och inga globala variabler har förändrats eller något, du kommer aldrig att nå basfallet, i vilket fall som är dåligt. Det kommer att bli en oändlig rekursion och stackspill. Men här ser vi att uppdateringen sker eftersom vi uppdaterar start + slut / 2, Vi uppdaterar slut argumentet här, vi håller på att uppdatera start argumentet här. Så i alla rekursiva anrop som vi uppdaterar något. Okej. Vill du gå oss genom din lösning? >> Visst. Jag använder SearchHelp så att varje gång jag gör detta funktionsanrop Jag har i början av där jag söker i arrayen och slutet av där jag ser arrayen. Vid varje steg där det säger att det är i mitten delen, som är start + slut / 2, är att lika det vi letar efter? Och om det är så vi fann det, och jag antar att får gått upp nivåerna av rekursion. Och om det är inte sant, vi kontrollera om det mittersta värdet i matrisen är för stor, i vilket fall vi tittar på den vänstra halvan av uppsättningen genom att gå från start till mitten index. Och annars gör vi slut halv. [Bowden] Okej. Det låter bra. Okej, så ett par saker, och faktiskt, är detta en mycket hög nivå sak att du aldrig behöver veta för denna kurs, men det är sant. Rekursiva funktioner hör du alltid att de är en dålig affär för om du rekursivt kallar dig för många gånger får du spill Sedan, som jag sa tidigare, får varje funktion sin egen stack ram. Så varje samtal av rekursiv funktion får sin egen stack ram. Så om du gör 1.000 rekursiva anrop får du 1.000 stack ramar, och snabbt du leder att ha alltför många stack ramar och saker bara bryta. Så det är därför rekursiva funktioner är i allmänhet dåliga. Men det är en fin del av rekursiva funktioner kallas svans-rekursiva funktioner, och detta råkar vara ett exempel på en där om kompilatorn märker detta och det bör, tror jag - i klang om du klarar det-O2 flaggan så kommer det att märka att detta är svansen rekursiv och göra saker bra. Det kommer att återanvända samma stackram om och om igen för varje rekursivt anrop. Och så eftersom du använder samma stack ram, behöver du inte oroa dig för någonsin stack överfyllda, och på samma gång, som du sa tidigare, där en gång du kommer tillbaka sant, då måste återvända upp alla dessa stack ramar och den 10: e samtalet till SearchHelp måste återvända till 9 måste återvända till 8th. Så det behöver inte ske när funktioner är svansen rekursiv. Och så vad gör denna funktion svans rekursiv är notera att för en given samtal till searchHelp den rekursiva samtal som det gör är vad det återvänder. Så i det första samtalet till SearchHelp vi antingen omedelbart returnera false, omedelbart återlämna sant, eller vi gör ett rekursivt anrop till SearchHelp där vad vi återvänder är vad det samtalet återvänder. Och vi kunde inte göra detta om vi gjorde något liknande int x = SearchHelp, retur x * 2, bara några slumpmässig förändring. Så nu denna rekursivt anrop, denna int x = SearchHelp rekursivt anrop, är inte längre svans rekursiv eftersom det faktiskt inte måste återvända tillbaka till en tidigare stack ram så att den tidigare anrop till funktionen kan sedan göra något med returvärdet. Så detta är inte svans rekursiv, men vad vi hade innan är snyggt svans rekursiv. Ja. [Elev] Borde inte det andra basfallet kontrolleras först eftersom det kan vara en situation där när du passerar det argumentet ni start = slut, men de är nålen värdet. Frågan var inte vi kan stöta på vid slutet är nålen värdet eller starta = slut, lämpligt, start = slut och du inte har faktiskt kontrollerat att särskilt värde ännu, börja + END / 2 bara kommer att vara samma värde. Men vi har redan återvänt falska och vi aldrig kontrollerat värde. Så åtminstone i första samtalet, om storleken är 0, då vi vill returnera false. Men om storlek är 1, så börjar inte kommer att lika slut, och vi ska åtminstone kolla en del. Men jag tror att ni har rätt i att vi kan hamna i ett fall där start + slut / 2, start slutar vara detsamma som start + slut / 2, men vi aldrig kontrollerat det elementet. Så om vi först kontrollera är den mellersta delen det värde vi letar efter, då kan vi genast returnera sant. Annars om de är lika, så finns det ingen mening med att fortsätta eftersom vi bara kommer att uppdatera till ett fall där vi är på en enda faktor matris. Om det enda element inte den vi letar efter, då allting är fel. Ja. [Elev] Saken är att eftersom storlek är faktiskt större än antalet element i arrayen, Det finns redan en förskjutning - >> Så kommer storlek - [Elev] Säg om arrayen var storlek 0, då SearchHelp kommer faktiskt kontrollera höstack av 0 på första samtalet. Matrisen har storlek 0, så 0 är - >> Ja. Det finns en annan sak som - det kan vara bra. Låt oss tänka. Så om arrayen hade 10 element och den mittersta vi ska kontrollera är index 5 så vi kontrollerar 5, och låt oss säga att värdet är mindre. Så vi kastar allt ifrån 5 och framåt. Så börja + END / 2 kommer att bli vår nya ände, så ja, det kommer alltid att bo utanför slutet av arrayen. Om det är ett ärende om det var jämnt eller udda, då skulle vi kontrollera, säger, 4, men vi är fortfarande kastar bort - Så ja, är slut kommer alltid att vara utom själva slutet av arrayen. Så de delar som vi fokuserar på är slut kommer alltid att vara en efter det. Och så om start gör någonsin lika ändamål, är vi i en rad storlek 0. Det andra jag tänkte är att vi uppdaterar börjar bli start + slut / 2, så detta är det så att jag har problem med, där start + slut / 2 är elementet vi kontroll. Låt oss säga att vi hade denna 10-elementet array. Oavsett. Så börja + END / 2 kommer att bli något liknande den här, och om det inte är värdet, säger vi vill uppdatera. Värdet är större, så vi vill titta på denna halva uppsättningen. Så hur vi uppdaterar start, vi uppdaterar start nu detta element. Men det kan fortfarande fungera, eller åtminstone, kan du göra start + slut / 2 + 1. [Elev] Du inte behöver börja + slut [ohörbart] >> Ja. Vi har redan kontrollerat detta element och vet att det inte är en vi letar efter. Så vi behöver inte uppdatera börjar bli detta element. Vi kan bara hoppa över det och uppdatera börjar bli detta element. Och är det någonsin ett fall, låt oss säga att detta var slutet, så börja skulle vara så här, börja + slut / 2 skulle vara så här, start + slut - Ja, jag tror att det kan hamna i oändlig rekursion. Låt oss säga att det är bara en rad storlek 2 eller en rad storlek 1. Jag tror att detta kommer att fungera. Så nu är början att element och slutet är 1 bortom det. Så element som vi kommer att kontrollera detta är, och sedan när vi uppdaterar start, vi uppdaterar börjar bli 0 + 1/2, som kommer att sluta oss tillbaka med start är detta element. Så vi kontrollerar samma element om och om igen. Så detta är fallet där varje rekursivt anrop måste faktiskt update något. Så vi måste göra start + slut / 2 + 1, annars finns det ett fall där vi inte faktiskt uppdaterar start. Alla ser det? Okej. Har någon frågor om denna lösning eller fler kommentarer? Okej. Har någon en iterativ lösning som vi alla kan titta på? Gjorde vi allt rekursivt? Eller också jag antar att om du öppnat hennes, så du kan ha åsidosatt din tidigare en. Sparar den automatiskt? Jag är inte positiv. Har någon iterativ? Vi kan gå igenom det tillsammans om inte. Tanken kommer att vara densamma. Iterativ lösning. Vi kommer att vilja princip göra samma idé där vi vill hålla reda på den nya änden av arrayen och den nya början av uppsättningen och göra det om och om igen. Och om vad vi håller koll på som start och slut någonsin skär, då vi inte hitta det och vi kan returnera false. Så hur gör jag det? Någon har förslag eller kod för mig att dra upp? [Elev] Gör en while-slinga. >> Ja. Du kommer att vilja göra en loop. Hade du kod jag kunde dra upp, eller vad skulle du föreslå? [Elev] Jag tror det. >> Okej. Det gör saker och ting lättare. Vad var ditt namn? [Eleven] Lucas. Revidering 1. Okej. Låg är vad vi kallade starta innan. Up är inte riktigt vad vi kallade slutet innan. Egentligen är slut nu inom matrisen. Det är en del som vi bör tänka på. Så låg är 0, upp är storleken på uppsättningen - 1, och nu är vi looping, och vi kontrollerar - Jag antar att du kan gå igenom den. Vad var ditt tänkande genom detta? Guida oss genom din kod. [Elev] Visst. Titta på höstacken värdet i mitten och jämför med nål. Så om det är större än din nål, då du vill - Åh, faktiskt, bör det vara bakåt. Du kommer att vilja kasta bort den högra, och så ja, bör det vara vägen. [Bowden] Så detta bör vara mindre? Är det vad du sa? >> [Elev] Ja. [Bowden] Okej. Mindre. Så om det vi tittar på är mindre än vad vi vill, då ja, vi vill kasta bort den vänstra halvan, vilket innebär att vi uppdaterar allt vi funderar genom att flytta låg till höger om gruppen. Detta ser bra ut. Jag tror att det har samma fråga som vi sade på den tidigare, där om låga är 0 och uppåt är 1, då låg + upp / 2 kommer att inrättas för att vara samma sak igen. Och även om det inte är fallet, är det fortfarande mer effektivt åtminstone att bara kasta bort elementet tittade vi bara på som vi vet är fel. Så låg + upp / 2 + 1 - >> [elev] Det borde vara tvärtom. [Bowden] Eller detta bör vara - 1 och den andra bör vara + 1. [Elev] och det bör finnas en dubbel likhetstecken. >> [Bowden] Ja. [Eleven] Ja. Okej. Och slutligen, nu när vi har det + 1 - 1 sak, är det - det kanske inte - är det någonsin möjligt för låg för att sluta med ett värde större än upp? Jag tror att det enda sättet som kan hända - Är det möjligt? >> [Elev] Jag vet inte. Men om det blir stympad och sedan blir minus att 1 och sedan - >> Ja. [Elev] Det skulle möjligen bli förstörd. Jag tycker att det borde vara bra bara för att för att det ska hamna lägre de skulle behöva vara lika, tror jag. Men om de är lika, så skulle vi inte ha gjort while-slingan till att börja med och vi bara skulle ha återvänt värdet. Så jag tror att vi är bra nu. Lägg märke till att även om detta problem inte längre rekursiv, samma typ av idéer gäller där vi kan se hur detta så lätt lämpar sig till en rekursiv lösning av det faktum att vi bara ska uppdatera indexen om och om igen, vi gör problemet mindre och mindre, vi fokuserar på en delmängd av matrisen. [Elev] Om låg är 0 och uppåt är 1, skulle de båda vara 0 + 1/2, vilket skulle gå till 0, och då en vara + 1, skulle en vara - 1. [Elev] Vart ska vi kontrollera jämlikhet? Som om den mittersta faktiskt nål? Vi är inte närvarande gör det? Oh! Om it's - Ja. Vi kan inte bara göra testet här nere eftersom låt oss säga de första mellersta - [Elev] Det är faktiskt gillar inte kasta bort den bundna. Så om du kasta bort den bundna, måste du kolla upp det först eller vad som helst. Ah. Ja. >> [Elev] Ja. Så nu har vi kastat bort den vi nu tittat på, vilket innebär att vi nu måste även ha if (höstack [(lågt + upp) / 2] == nål), då kan vi återvända sant. Och om jag sätter annan eller bara om, betyder det bokstavligen samma sak eftersom detta skulle ha återvänt sant. Så jag sätter annat om, men det spelar ingen roll. Så annanstans om detta, annars detta, och det är en vanlig sak jag gör där även om det är fallet där allt är bra här, som låg aldrig kan vara större än upp, det är inte värt att resonemang om huruvida det är sant. Så du kan lika gärna säga när låg är mindre än eller lika med eller när låga är mindre än så om de någonsin lika eller låg råkar missa, då kan vi bryta denna slinga. Frågor, frågor, kommentarer? Okej. Detta ser bra ut. Nu vill vi göra slag. Om vi ​​går till min andra översynen ser vi samma siffror, men nu är de inte längre i sorterad ordning. Och vi vill genomföra Sortera använda någon algoritm i O n log n. Så vilken algoritm tror du att vi bör genomföra här? >> [Elev] Merge sort. [Bowden] Ja. Merge Sortera är O (n log n), så det är vad vi ska göra. Och problemet kommer att vara ganska lika, där det lämpar lätt sig en rekursiv lösning. Vi kan också komma med en iterativ lösning om vi vill, men rekursion blir lättare här och vi bör göra rekursion. Jag antar att vi kommer att gå igenom sammanslagning Sortera först, även om det finns en härlig video på Merge Sortera redan. [Skratt] Så sammanfoga Sortera finns - jag slösa så mycket av detta papper. Åh, det finns bara en kvar. Så samman. O, 1, 3, 5. Okej. Sammanfoga tar två separata matriser. Individuellt dessa två arrayer båda sorteras. Så denna array, 1, 3, 5, sorteras. Denna matris, 0, 2, 4, sorteras. Nu vad sammanslagning bör göra är att kombinera dem till en enda array som själv sorteras. Så vi vill ha en rad storlek 6 som kommer att ha dessa element inuti det i sorterad ordning. Och så kan vi dra nytta av det faktum att dessa två matriser sorteras att göra detta i linjär tid, linjär tid betydelse om denna array är storlek x och detta är storleken y, då den totala algoritmen bör vara O (x + y). Okej. Så förslag. [Elev] Kan vi börja från vänster? Så du lägga 0 ner först och sedan 1 och sedan här du är på 2. Så det är ungefär som att du har en flik som rör sig åt höger. >> [Bowden] Ja. För båda dessa matriser om vi bara fokuserar på den vänstra delen. Eftersom båda uppsättningarna är sorterade vet vi att dessa 2 delar är de minsta elementen i endera matrisen. Så det betyder att 1 av dessa 2 element måste vara det minsta elementet i vår sammanslagna array. Det råkar vara så att den minsta är den på rätt den här gången. Så vi tar 0, sätt in den på vänster eftersom 0 är mindre än 1, så ta 0, sätt in det i vår första position, och sedan vi uppdatera denna att nu fokusera på det första elementet. Och nu har vi upprepa. Så nu vi jämför 2 och 1. 1 är mindre, så vi sätter 1. Vi uppdaterar denna pekare att peka på den här killen. Nu gör vi det igen, så 2. Detta kommer att uppdatera, jämföra dessa 2, 3. Då uppdateras, sedan 4 och 5. Så det är kopplingen. Det borde vara ganska uppenbart att det är linjär tid eftersom vi bara gå över varje element en gång. Och det är det största steget att genomföra sammanslagning Sortera gör detta. Och det är inte så svårt. Ett par saker att oroa sig är låt oss säga att vi var sammanslagning 1, 2, 3, 4, 5, 6. I det här fallet hamnar vi i det scenario där denna kommer att bli mindre, då vi uppdaterar denna pekare, detta en kommer att bli mindre, uppdatera, detta en är mindre och nu måste du erkänna när du faktiskt har slut på element att jämföra med. Eftersom vi redan har använt det hela matrisen, allt i denna array är nu bara in i här. Så om vi kör någonsin på den punkt där en av våra matriser är helt samman redan, då tar vi bara alla delar av den andra gruppen och infoga dem i slutet av arrayen. Så vi kan bara sätta in 4, 5, 6. Okej. Det är en sak att se upp för. Genomförandet av det borde vara steg 1. Sammanfoga sortera sedan utifrån det, det är 2 steg, 2 dumma steg. Låt oss bara ge denna array. Så sammanfoga sortering, är steg 1 att rekursivt bryta arrayen i halvor. Så dela denna array i halvor. Vi har nu 4, 15, 16, 50 och 8, 23, 42, 108. Och nu gör vi det igen och vi dela dem i halvor. Jag ska bara göra det på den här sidan. Så 4, 15 och 16, 50. Vi skulle göra samma sak här. Och nu har vi dela den i halvor igen. Och vi har 4, 15, 16, 50. Så det är vår bas fallet. När matriserna är av storlek 1, då vi sluta med en uppdelning i två hälfter. Vad gör vi med det här? Vi avslutar upp detta också kommer att bryta ner till 8, 23, 42, och 108. Så nu när vi är på denna punkt, nu steg två i merge sort är bara samman par till listorna. Så vi vill sammanfoga dessa. Vi kallar bara samman. Vi vet att sammanslagningen kommer att återvända dessa i sorterad ordning. 4, 15. Nu vill vi slå samman dessa, och det kommer tillbaka en lista med de i sorterad ordning, 16, 50. Vi samman dem - jag kan inte skriva - 8, 23 och 42, 108. Så vi har gått samman par en gång. Nu har vi samman bara igen. Observera att var och en av dessa listor sorteras i sig, och då kan vi bara slå samman dessa listor för att få en lista med storlek 4, som sorteras och slå samman dessa två listor för att få en lista över storlek 4 som är sorterad. Och slutligen, kan vi slå ihop de två listor med storlek 4 för att få en lista med storlek 8 som sorteras. Så för att se att detta är totalt n log n såg vi redan att sammanfogningen är linjär, så när vi har att göra med sammanslagningen dessa, så som den totala kostnaden för sammanslagning för dessa två listor är bara 2 eftersom - Eller ja, det är O n, men n här är bara dessa 2 faktorer, så det är 2. Och dessa 2 blir 2 och dessa 2 blir 2 och dessa 2 blir 2, så över alla de övergår vi behöver göra, hamnar vi gör n. Liksom 2 + 2 + 2 + 2 är 8, vilket är n, så kostnaden för sammanslagning i denna uppsättning är n. Och sedan samma sak här. Vi kommer sammanfoga dessa 2, då dessa 2 och individuellt denna sammanslagning kommer att ta fyra operationer, denna sammanslagning kommer att ta fyra operationer, men återigen, mellan alla dessa, hamnar vi sammanslagning n TOTALA saker, och så detta steg tar n. Och så varje nivå tar n element slagits samman. Och hur många nivåer finns det? På varje nivå, växer vår uppsättning av storlek 2. Här våra matriser är av storlek 1, här är de i storlek 2, här är de i storlek 4, och slutligen, de är storlek 8. Så eftersom det fördubbling, finns det kommer att bli totalt log n dessa nivåer. Så med log n nivåer, varje nivå med n total verksamhet, vi får en n log n algoritm. Frågor? Har människor gjort redan framsteg på hur man ska genomföra det här? Är det någon som redan i ett tillstånd där jag kan bara dra upp sin kod? Jag kan ge en minut. Den här kommer att bli längre. Jag rekommenderar starkt återkommande - Du behöver inte göra rekursion för sammanfogningen eftersom att göra rekursion för sammanfogningen, du kommer att behöva passera ett gäng olika storlekar. Du kan, men det är irriterande. Men rekursion för typ själv är ganska enkelt. Du bara bokstavligen ringa Sortera på vänster halv, sortera på höger halva. Okej. Någon har något jag kan dra upp ännu? Eller så ska jag ge en minut. Okej. Någon har något vi kan arbeta med? Eller så kommer vi bara arbeta med detta och expandera sedan därifrån. Någon har mer än detta som jag kan dra upp? [Eleven] Ja. Du kan dra upp mig. >> Okej. Ja! [Elev] Det fanns en hel del villkor. >> Åh, skjuta. Kan du - [Elev] Jag har att spara den. >> Ja. Så vi gjorde kopplingen separat. Åh, men det är inte så illa. Okej. Så Sortera själv bara ringa mergeSortHelp. Förklara för oss vad mergeSortHelp gör. [Eleven] MergeSortHelp ganska gör mycket de två viktigaste stegen, vilket är att sortera varje halva av gruppen och sedan sammanfoga dem båda. [Bowden] Okej, så ge mig en sekund. Jag tror att detta - >> [elev] Jag behöver - Ja. Jag saknar något. I samman, inser jag att jag måste skapa en ny array eftersom jag inte kunde göra det på plats. >> Ja. Du kan inte. Rätta. [Elev] Så jag skapar en ny array. Jag glömde i slutet av samman till nytt förändras. Okej. Vi behöver en ny array. I sammanslagning sortera, är det nästan alltid sant. En del av kostnaderna för en bättre algoritm tidsmässigt är nästan alltid behöva använda lite mer minne. Så här, oavsett hur du gör ihop sortera, du skulle oundvikligen behöva använda lite extra minne. Han eller hon skapade en ny array. Och då säger du i slutet vi bara behöver kopiera ny array i den ursprungliga arrayen. [Elev] Jag tror det, ja. Jag vet inte om det fungerar när det gäller att räkna med hänvisning eller något annat - Ja, kommer det att fungera. >> [Elev] Okej. Har du försökt köra det här? >> [Elev] Nej, inte än. >> Okej. Försök att köra den och sedan ska jag prata om det för en sekund. [Elev] Jag behöver ha alla funktioner prototyper och allt, men hur? Funktionen prototyper. Du menar som - Ja. Sortera kallar mergeSortHelp. Så för att sortera att kalla mergeSortHelp måste mergeSortHelp antingen har definierats innan sortera eller behöver vi bara en prototyp. Bara kopiera och klistra in det. Och på samma sätt är mergeSortHelp ringer samman, men sammanfogning inte har definierats ännu, så vi kan bara låta mergeSortHelp veta att det är vad samman kommer att se ut, och det är det. Så mergeSortHelp. Vi har en fråga här där vi inte har någon basfall. MergeSortHelp är rekursiv, så någon rekursiv funktion kommer att behöva någon form av basfallet att veta när du ska sluta rekursivt kallar sig. Vad är vår bas fall kommer att vara här? Ja. [Eleven] Om storleken är 1? >> [Bowden] Ja. Så som vi såg där, vi slutade dela arrayer när vi fått in matriser av storlek 1, vilket oundvikligen är sorterade själva. Så om storlek är lika med 1, vet vi matrisen redan sorteras, så att vi kan bara gå tillbaka. Notera att det är ogiltigt, så att vi inte returnera något särskilt, återvänder vi bara. Okej. Så det är vår bas fallet. Jag antar att vår bas fall också skulle kunna vara om vi råkar sammanslagning en rad storlek 0, Vi vill nog stanna vid något tillfälle, så vi kan bara säga storlek mindre än 2 eller mindre än eller lika med 1 så att detta kommer att fungera för alla matris nu. Okej. Så det är vår bas fallet. Nu vill du gå oss genom sammanslagning? Vad gör alla dessa fall menar? Här uppe, vi gör precis samma idé, - [Elev] Jag måste passera storlek med alla mergeSortHelp samtal. Jag lade storlek som en ytterligare primär och det är inte där, liksom storlek / 2. [Bowden] Åh, storlek / 2, storlek / 2. >> [Studenten] Ja, och även i ovanstående funktion. [Bowden] Här? >> [Elev] Bara storlek. >> [Bowden] Oh. Storlek, storlek? >> [Elev] Ja. [Bowden] Okej. Låt mig tänka för en sekund. Kör vi på en fråga? Vi är alltid behandla vänster som 0. >> [Eleven] Nej Det är fel också. Ursäkta. Det bör vara början. Ja. [Bowden] Okej. Jag gillar det bättre. Och slut. Okej. Så nu vill du gå oss genom sammanslagning? >> [Elev] Okej. Jag bara gå igenom det nya array som jag har skapat. Dess storlek är storleken på den del av matrisen som vi vill ska sorteras och försöker hitta element som jag skulle sätta i den nya arrayen steget. Så för att göra det först jag kontrollera om den vänstra halvan av matrisen fortsätter att ha några fler element, och om det inte gör det, då du gå ner till den andra tillstånd, som bara säger okej, det måste vara i rätt mängd, och vi ska sätta det i den nuvarande index newArray. Och sedan annars jag kontrollera om den högra sidan av matrisen också klar, i vilket fall jag satte bara i vänster. Det kanske inte egentligen behövas. Jag är inte säker. Men hur som helst, de andra två kontroll som av två är mindre i vänster eller höger. Och även i varje enskilt fall, jag uppräkning beroende platshållare jag öka. [Bowden] Okej. Det ser bra ut. Har någon synpunkter eller funderingar eller frågor? Så de fyra fall som vi måste ta saker i att bara vara - eller det ser ut som fem - men vi måste överväga om den vänstra matrisen har slut på saker vi måste gå samman, om rätten arrayen har slut på saker vi måste slå samman - Jag pekar på ingenting. Så om den vänstra matrisen har slut på saker eller rätt arrayen har slut på saker. Det är två fall. Vi behöver också det triviala fallet om den vänstra sak är mindre än den rätta. Då vi vill välja den vänstra sak. Det är fallen. Så detta var rätt, så det är det. Array vänster. Det är 1, 2, 3. Okej. Så ja, det är de fyra saker vi kanske vill göra. Och vi kommer inte att gå över en iterativ lösning. Jag skulle inte rekommendera - Merge sortera är ett exempel på en funktion som är både inte svans rekursiv, det är inte lätt att göra det svans rekursiv, men även det är inte lätt att göra det iterativa. Detta är mycket enkelt. Denna implementering av sammanslagning sortera, samman, oavsett vad du gör, du kommer att bygga merge. Så sammanfoga Sortera byggd ovanpå Merge rekursivt bara dessa tre linjer. Iterativt, det är mer irriterande och svårare att tänka på. Men notera att det inte är svansen rekursivt sedan mergeSortHelp - när det kallar sig - Det behöver fortfarande göra saker efter detta rekursivt anrop avkastning. Så denna stack ram måste fortsätta att existera även efter kräver detta. Och sedan när du ringer detta måste stackram fortsätta att existera eftersom även efter det samtalet, måste vi ändå att gå samman. Och det är triviala att göra denna svans rekursiv. Frågor? Okej. Så gå tillbaka att sortera - Åh, det är två saker jag vill visa. Okej. Gå tillbaka för att sortera, vi gör det snabbt. Eller sök. Sortera? Sortera. Ja. Gå tillbaka till början av slag. Vi vill skapa en algoritm som sorterar arrayen med någon algoritm i O n. Så hur är detta möjligt? Har någon någon form av - Jag antydde tidigare på - Om vi ​​ska förbättras från n log n till O n, Vi har förbättrat vår algoritm tidsmässigt, vilket innebär vad vi kommer att behöva göra för att kompensera för det? [Elev] Space. >> Ja. Vi kommer att använda mer utrymme. Och inte ens bara mer utrymme, det är exponentiellt mer utrymme. Så jag tror att denna typ av algoritm är pseudo något, pseudo polynom - pseudo - Jag kan inte minnas. Pseudo något. Men det är för att vi måste använda så mycket utrymme att detta är möjligt, men inte realistiskt. Och hur uppnår vi detta? Vi kan uppnå detta om vi garanterar att en viss element i arrayen är under en viss storlek. Så låt oss bara säga att storleken är 200, alla element i en array är under storlek 200. Och detta är faktiskt mycket realistiskt. Du kan enkelt få en array som du vet allt i den kommer att vara mindre än ett visst antal. Precis som om du har några absolut massiva vektor eller något men du vet allt kommer att vara mellan 0 och 5, då det kommer att vara betydligt snabbare att göra detta. Och den bundna på något av elementen är 5, så detta bundna, det vill säga hur mycket minne du kommer att använda. Så bundna är 200. I teorin finns det alltid en bunden eftersom ett heltal kan bara vara upp till 4 miljarder, men det är orealistiskt sedan vi skulle använda utrymme i storleksordningen 4 miljarder. Så det är orealistiskt. Men här ska vi säga vår gräns är 200. Tricket att göra det i O n är att vi gör ett annat array med namnet räkningar av storlek bunden. Så egentligen är det en genväg för - jag faktiskt vet inte om klang gör detta. Men i GCC åtminstone - jag antar klang gör det också - Detta kommer bara initiera hela gruppen att vara 0s. Så om jag inte vill göra det, då kunde jag separat göra for (int i = 0; I > Okej. Jag insåg en annan sak när vi går igenom. Jag tror att problemet var i Lucas och förmodligen varenda en som vi har sett. Jag glömde helt. Det enda jag ville kommentera är att när du arbetar med saker som index, du aldrig riktigt se det när du skriver en for-slinga, men tekniskt, när du arbetar med dessa index, bör du ganska mycket alltid hantera heltal utan tecken. Anledningen till detta är när du arbetar med signerade heltal, så om du har 2 signerade heltal och du lägger ihop dem och de hamnar för stor, då du sluta med ett negativt tal. Så det är vad heltalsspill är. Om jag lägger 2 miljarder och 1 miljard avslutar jag med negativ 1 miljard. Det är så heltal fungerar på datorer. Så problemet med att använda - Det är bra förutom om låg råkar vara 2 miljarder och upp råkar vara 1 miljard då detta kommer att vara negativ 1 miljard och då ska vi dela den med 2 och sluta med negativ 500 miljoner. Så detta är bara en fråga om du råkar vara att söka igenom en array av miljarder saker. Men om låg + upp händer att svämma över, så det är ett problem. Så snart vi gör dem osignerad, sedan 2 miljarder plus 1 miljard 3 miljarder. 3 miljarder delat med 2 är 1,5 miljarder euro. Så snart som de är osignerad, är allt perfekt. Och så det är också en fråga när du skriver din för loopar, och faktiskt, det gör det nog det automatiskt. Det kommer faktiskt bara skrika på dig. Så om detta antal är för stor för att vara i bara ett heltal, men det skulle passa i ett heltal utan tecken, det kommer skrika på dig, så det är därför du aldrig verkligen köra i frågan. Du kan se att ett index aldrig kommer att bli negativt, och så när du iterera över en array, Du kan nästan alltid säga unsigned int i, men du egentligen inte behöver. Saker kommer att arbeta ganska mycket lika bra. Okej. [Viskar] Vad är klockan? Det sista jag ville visa - och jag ska bara göra det riktigt snabbt. Du vet hur vi # har definierar så att vi kan # define MAX som 5 eller något? Låt oss inte göra MAX. # Define bundna som 200. Det är vad vi gjorde innan. Som definierar en konstant, som just kommer att kopieras och klistras varhelst vi råkar skriva bunden. Så vi kan faktiskt göra mer med # definierar. Vi kan # define funktioner. De är inte riktigt fungerar, men vi kallar dem fungerar. Ett exempel skulle vara något som MAX (x, y) definieras som (x > Helst 14. Frågan är hur hash definierar arbetet, kom ihåg att det är en bokstavlig kopiera och klistra in av ganska mycket allt, så vad detta kommer att tolkas som är 3 färre än 1 plus 6, 2 gånger 1 plus 6, 2 gånger 3. Så av denna anledning du nästan alltid packa allt i parentes. Varje variabel som du nästan alltid packa inom parentes. Det finns fall där man inte behöver, som jag vet att jag inte behöver göra det här eftersom mindre än är ganska mycket alltid bara kommer att fungera, även om det kanske inte ens är sant. Om det är något löjligt som DOUBLE_MAX (1 == 2), då det kommer att bli ersatt med 3 mindre än 1 lika lika 2, och så då det kommer att göra 3 mindre än 1, betyder det lika 2, vilket är inte vad vi vill ha. Så för att undvika eventuella operatorprioritet problem, alltid svepa inom parentes. Okej. Och det är det, 5:30. Om du har några frågor om pset, låt oss veta. Det ska vara kul, och hacker upplagan är också betydligt mer realistisk än hackare upplagan av förra årets, så vi hoppas att många av er prova. Förra årets var mycket överväldigande. [CS50.TV]