[Glazba svira] DAVID Malan: U redu. U redu, dobrodošao natrag. Dakle, ovo je 4. tjedan, početak tome, već. A vi ćete se prisjetiti da je prošlog tjedna, stavili smo kodirati stranu za samo malo i počeli smo razgovarati malo više na visokoj razini, o stvarima kao što su pretraživanje i sortiranje, koji iako Nešto jednostavne ideje, su Predstavnik jedne klase problema ćete početi rješavati posebno kao što počnete razmišljati o finalu projekti i zanimljivi rješenja što Možda ćete morati stvarnim problemima. Sada bubble sortiranje bio je jedan od najjednostavnijih takve algoritme, i to radio tako da te male brojeve s popisa ili u niz vrste mjehurić svoj put do vrha, a Veliki broj presele svoj put do kraj tog popisa. I podsjetiti da smo mogli vizualizirati bubble sortiranje malo nešto poput ovoga. Zato mi dopustite da ići naprijed i kliknite Start. Ja sam odabrao mjehurić vrsta. A ako se prisjetiti da je jači plava linije predstavljaju velike brojeve, male plave linije predstavljaju male brojeve, kao ćemo proći kroz to opet i opet i opet, uspoređujući dvije prečke jedni pored drugi u crvenom, idemo na swap Najveći i najmanji, ako oni su izvan funkcije. Dakle, to će ići na i ići na i otići na, i vidjet ćete da je veći elementi su čineći njihovu putu u pravo, a manji elementi čineći svoj put s lijeve strane. No, počeli smo kvantificirati učinkovitost, Kvaliteta ovog algoritma. A mi je rekao da je u najgorem slučaj, ovaj algoritam je otprilike koliko koraka? Dakle, n kvadrat. A što je n? PUBLIKA: Broj elemenata. DAVID Malan: Tako je n broj elemenata. I tako ćemo to često. Svaki put kada želimo govoriti o veličini nekog problema ili veličini ulazna, odnosno iznos od vrijeme koje je potrebno za izradu izlaza, mi ćemo jednostavno generalizirati god Ulaz je, kao n. Dakle, natrag u tjednu 0, broj stranice u imeniku je n. Broj studenata u sobi je n. Dakle, ovdje je, također, da smo nakon da je uzorak. Sada n kvadrat nije osobito brzo, tako da smo pokušali učiniti bolje. I tako smo gledali na nekoliko drugi algoritama, među kojima Izbor su neka vrsta. Dakle, izbor je svojevrsni malo drugačiji. Bilo je gotovo jednostavnije, usudio bih se reći, gdje sam započeo na početku Popis naših volontera, a ja samo jednom i opet i opet otišao do Popis, čupanje najmanji Element na vrijeme i da ga stavite ili ju na početku popisa. Ali to je, kada smo počeli razmišljati kroz matematiku i veći Slika, razmišljao koliko puta Htjela sam natrag i naprijed i natrag i naprijed, rekli smo u najgorem slučaju, Izbor sortiranje, također, bio je ono? n kvadrat. Sada u stvarnom svijetu, to bi moglo zapravo biti marginalno brži. Jer opet, nisam morati držati zaostaje kada sam razvrstani najmanji elementi. No, ako mislimo o vrlo velikom n, i ako vrsta napraviti iz matematike kao Ja sam na brodu, s n kvadrat minus nešto, sve ostalo osim n kvadrat, jednom n dobiva stvarno velik, ne stvarno obzira koliko. Dakle, kao računalnih znanstvenika, mi vrsta zažmiriti na manji čimbenici i usredotočiti se samo na faktor u izraz koji će napraviti Najveća razlika. Pa, na kraju, tražili smo kod unosa vrste. I to je bila slična u duhu, ali nego proći kroz iterativno i odaberite najmanji element na jednu Vrijeme, umjesto da sam uzeo ruku da sam riješeno, a ja sam odlučio, sve Dobro, vi pripadate ovdje. Onda sam se preselio na sljedeći elementa i odlučio da on ili ona je pripadala ovdje. A onda sam se preselio na i na. I ja bi se, usput, pomak te tipove kako bi se napravite mjesta za njih. Znači, to je neka vrsta mentalnih preokret od odabira vrste, koje smo naziva unosa vrsta. Dakle, ove teme koje se javljaju u stvarnom svijetu. Samo prije nekoliko godina, kada je izvjesno Senator je bio u utrci za predsjednika, Eric Schmidt, u to vrijeme predsjednik Uprave Google, zapravo imali priliku da ga intervjuirati. I mislili smo da ćemo podijeliti ovaj YouTube clip za vas ovdje, ako smo mogli okrenuti prema gore volumen. [Video reprodukciju] -Sada, senatore, da ste ovdje na Googleu, a ja volim misliti predsjedništva kao intervju za posao. [Smijeh] -Sada je teško dobiti posao kao predsjednika. A što prolaziš rigors sada. Također je teško dobiti posao u Googleu. Imamo pitanja i tražimo naši kandidati pitanja. I to je jedna od Larry Schwimmer. [Smijeh] -Vi mislite da se šalim? To je upravo ovdje. Što je najučinkovitiji način da se sortirati milijun dvije bitne cijele brojeve? [Smijeh] -Pa, uh - -Žao mi je. Možda smo trebali - -Ne, ne, ne, ne, ne. -To nije - OK. -Mislim da bi neka vrsta balon biti krivi način da ide. [Smijeh] [Navijanje i PLJESAK] -Ma daj, koji je rekao mu ovo? OK. [END video reprodukciju] DAVID Malan: Tako da ste ga imati. Tako smo počeli kvantificirati te trčanje puta, da tako kažem, s nešto zove asimptotska zapis, što je Samo se odnosi na naše vrste okreće slijep na one manje čimbenika i Samo gleda u vrijeme rada, obavljanje tih algoritama, kao n dobiva stvarno veliki tijekom vremena. I tako smo uveli veliki O. i veliki O- predstavljao nešto što smo mislili kao gornja granica. I zapravo, Barry, možemo sniziti od mic malo? Mislili smo da je to gornja granica. Tako veliko O od n na kvadrat znači da je u najgorem slučaju, nešto poput Izbor svojevrsni bi potrajati n kvadratna korake. Ili nešto poput umetanja vrstom bi n kvadratna koraka. Sada za nešto poput umetanja sortiranje, što je najgori slučaj? S obzirom na niz, što je najgore mogući scenarij koji bi mogli naći se suočavaju s? To je potpuno unatrag, zar ne? Jer ako je to potpuno unatrag, što morate učiniti puno posla. Jer, ako ste potpuno unatrag, ti si idući u nađi Najveći elementa ovdje, iako ona pripada tamo dolje. Tako ćeš reći, ok, na ovaj trenutak u vremenu, da pripadam ovdje, tako da ga ostavi na miru. Tada ćete shvatiti, oh, damn, ja moram premjestiti ovaj nešto manji element lijevo od vas. Onda moram to ponoviti i opet i opet. A ako sam išao naprijed i natrag, što bi vrsta osjetiti izvedbu da je algoritam, jer stalno sam ja miješanje svima ostalima dolje Niz kako bi napravili mjesta za njega. Dakle, to je najgori slučaj. Za razliku od toga - a to je roman u zadnji put - mi je rekao da je uneseni sortiranje bio omega što? Što je najbolje slučaj trčanje vrijeme umetanja vrste? Dakle, to je zapravo n. To je bio prazan da smo napustili Na brodu zadnji put. I to je omega n, jer zašto? Pa, u najboljem slučaju, ono što je sortiranje umetanjem će se predati? Pa, popis koji je potpuno razvrstani Već, minimalni rad učiniti. No, ono što je uredno o tome kakve umetanja je da zato što počinje ovdje i odluči, oh, ti si broj jedan, da pripadam ovdje. Oh, što je sreća. Ti si broj dva. Također pripadam ovdje. Broj tri, čak i bolje, da pripadam ovdje. Čim stigne do kraja Popis, po utiskivanja za sortiranje je pseudocode kako smo hodali kroz verbalno Posljednji put, to je učinjeno. No, izbor sortiranje, za razliku od, držati što radiš? Zadržao ide kroz popis opet i opet i opet. Zbog Ključni uvid bilo je samo nakon što ste gledali sve do kraj popisa možete biti sigurni Element koji ste odabrali je Doista trenutno najmanji element. Tako su ti različitih mentalnih modela kraj se donosi neke vrlo stvarnom svijetu razlike za nas, kao i ovi teorijski asimptotske razlike. Dakle, samo da ponovim, dakle, velika O n kvadrat, vidjeli smo nekoliko takvih Algoritmi do sada. Big O n? Što je algoritam koji bi može reći da je velika O n? U najgorem slučaju, to traje linearni niz koraka. OK, linearno pretraživanje. A u najgorem slučaju, gdje je Element ste u potrazi za kada primjenom linearne pretragu? OK, u najgorem slučaju, to nije ni tamo. Ili u drugom najgorem slučaju, to je sve na kraju, što je plus-minus ili jedan korak razlika. Tako da je na kraju dana, možemo reći da je linearno. Big O n će biti linearna pretragu, jer u najgorem slučaju, Element je ni tamo ili je sve na kraju. Pa, big O log n. Nismo razgovarali u detalje o tome ovo, ali mi smo to vidjeli. Ono što radi u tzv logaritamska Vrijeme, u najgorem slučaju? Da, tako binarno pretraživanje. I binarna pretraga u najgorem slučaju Možda ima element negdje u Srednji, ili negdje unutar polja. No, samo ga pronašli kada vas podijelite popis na pola, u polovice, na pola, na pola. I onda voila, to je tamo. Ili opet, najgorem slučaju, to nije ni tamo. Ali vi ne znate da to ne postoji dok ne dođete do vrsta koje traju bottom-ina elemenata tako da se prepolovi i prepolovi i prepoloviti. Big O od 1. Tako smo mogli big O od 2, velikim O iz tri. Bilo da želite samo stalan broj, mi samo vrsta samo pojednostaviti da kao veliki O iz jednog. Iako ako je realno, to traje 2 ili čak 100 koraka, ako je konstantna broj koraka, mi samo reći veliko O od 1. Što je algoritam koji je u velikoj O iz jedne? PUBLIKA: Pronalaženje duljinu varijable. DAVID Malan: Pronalaženje duljina varijable? PUBLIKA: Ne, duljina ako je već riješeno. DAVID Malan: Dobro. U redu, tako pronalaženju dužine nešto ako je duljina tog nečega, kao što su polje, pohranjena u nekom varijablu. Zato što jednostavno možete pročitati varijablu, ili ispisati varijablu, ili samo općenito pristup toj varijabli. I voila, koji se stalno vrijeme. Nasuprot tome, mislim natrag na očekivanoj razini. Prisjetite se u prvom tjednu C, zove samo printf i ispis nešto na ekranu je nedvojbeno stalno vrijeme, jer to traje samo Neki broj CPU ciklusa pokazati da je tekst na zaslonu. Ili čekati - zar ne? Kako bi inače mogli smo modelirati izvedba printf? Bi li netko sviđa kako se ne slažu, da je možda je to zapravo i nije konstantna vrijeme? U kojem smislu printf možda je trčanje Vrijeme, zapravo ispisuje string na screen, biti nešto osim konstantna. PUBLIKA: [nečujno]. DAVID Malan: Da. Pa to ovisi o našoj perspektive. Ako mi zapravo mislimo na ulazu u printf kao string, i Stoga smo izmjeriti veličinu koja ulazna po dužini - pa nazovimo da je duljina n, kao i - nedvojbeno, printf je sama po sebi velika O n jer će vas odvesti n koraka ispisati iz svake od tih n likovi, najvjerojatnije. Barem u tolikoj mjeri da pretpostavljamo da možda je korištenjem for petlje ispod poklopca motora. No, trebali bismo gledati u to kodirati razumjeti bolje. I doista, kad vi počnete Analizirajući svoje algoritme, vi ćete doslovno učiniti upravo to. Vrsta od očne jabučice svoj broj i mislim o - u redu, ja imam ovu petlju Ovdje ili ja imamo ugniježđeni petlje ovdje, da će učiniti stvari n n puta, , a možete sortirati razuma svoj put kroz kod, čak i ako je pseudocode a ne stvarni broj. Zato što o omega na kvadrat od n? Što je algoritam koji je u najboljem slučaj, još uvijek je n kvadratna koraka? Da? PUBLIKA: [nečujno]. DAVID Malan: Pa neka vrsta odabira. Budući da u tom problemu zapravo smanjuje na činjenicu da je opet, ne znam Ja sam pronašao struje dok najmanji Provjerio sam sve prokleto elemente. Dakle, omega, kažu, n, mi Samo je došao gore sa jednim. Ubacivanje sortiranje. Ako se dogodi da se popis razvrstani već, u najboljem slučaju imamo samo napraviti jednu loptu kroz njega, U tom trenutku smo sigurni. A onda je to moglo biti, rekao je biti linearno, sigurno. Što je omega od 1? Ono, u najboljem slučaju, mogao potrajati konstantna broj koraka? Dakle, linearno pretraživanje, ako baš posreći a element koji tražite Nalazi se u početku popisa, ako je to gdje ste počinju svoj Linearni obuhvaćanje tog popisa. A to vrijedi i za Broj stvari. Na primjer, čak i binarna Nova je omega jedan. Jer što ako se stvarno prokleto sretni i ukus-stručnjak u sredini svoje polje je broj što tražite? Tako možete dobiti sretan tamo, kao dobro. To je jedan, na kraju, omega n log n. Dakle, n log n, mi zapravo nije govoriti o još, ali - PUBLIKA: Spoji vrsta? DAVID Malan: Spajanje sortiranje. To je roman u zadnje vrijeme, gdje smo predložili, a mi pokazali vizualno, da postoje algoritmi. A spajanje kakve samo jedan takav algoritam koji je iz temelja brži nego neki od ovih momaka. U stvari, spajanje kratko je ne samo u Najbolji slučaj n log n, u najgorem Slučaj n log n. A kad imate ovu podudarnost Omega i velikih O biti ista stvar? Mi zapravo mogu opisati kao da je ono što je zove theta, iako je malo rjeđi. No, to samo znači dvije granice, u ovom slučaju, su isti. Dakle spojiti neku, što to Stvarno svode se na za nas? Pa, sjećam motivaciju. Dopustite mi podići još jednu animaciju taj nismo pogledajte zadnje vrijeme. Ovo je jedna, ista ideja, ali to je malo veći. I ja ću ići naprijed i istaknuti Prvi - imamo unosa vrsta na gore lijevo, a zatim odabir sortiranje, bubble sortiranje, nekoliko drugih vrsta - ljuske i brzo - da nismo razgovarali o, i gomila i spajanje vrsta. Tako barem pokušati usredotočiti svoje oči na prva tri mjesta na lijevoj strani, a zatim spojiti neku kad kliknem ova zelena strelica. Ali ja ću sve od njih pokrenuti, samo da daje vam osjećaj raznolikosti algoritmi koji postoje u svijetu. Ja ću pustiti ovu utrku za samo nekoliko sekundi. A ako se usredotočite vaše oči - pick Algoritam, usredotočiti na to za samo sekundi - vi ćete početi vidjeti uzorak koji se to provodi. Spoji sortiranje, obavijest, učinjeno je. Skupi sortiranje, brzo sortirati, školjke - pa se čini uveli smo tri Najgore algoritama prošli tjedan. Ali to je dobro da smo danas ovdje da se , pogledajte spajanja vrste, što je jedan od one su lakše je gledati, čak i iako to vjerojatno će saviti svoje mišljenje Samo malo. Ovdje možemo vidjeti koliko je Izbor svojevrsni sranje. No, na drugoj strani, to je stvarno lako provesti. A možda je za P Set 3, to je jedna od Algoritmi ste izabrali za provedbu za standardnom izdanju. Savršeno u redu, posve točna. Ali opet, kao n dobiva veliki, ako odlučite provesti brži algoritam kao svojevrsno pismo, izgledi su u veće i veće ulaza, tvoj broj je samo ide na trčanje brže. Vaša web stranica će raditi bolje. Vaši korisnici će biti sretniji. I tako su ti učinci da zapravo daje nas neki dublji mislili. Tako ćemo pogledati što spajanje svojevrsni je zapravo riječ. Super stvar je da spajanje svojevrsni je upravo to. To je, opet, ono što smo pozvani pseudocode, biće pseudocode Engleski poput sintakse. A jednostavnost je vrsta fascinantno. Tako se na ulaz od n elemenata - tako da samo znači, ovdje je niz. To je dobio n stvari u njemu. To je sve što govoriš postoji. Ako n je manje od 2, vratiti. Dakle, to je samo trivijalno slučaj. Ako je n manji od 2, a zatim je očito da je 1 ili 0, u kojem slučaju je stvar je već riješeno ili nepostojeće, pa samo se vratiti. Nema se što učiniti. Dakle, to je jednostavan slučaj trgati off. Inače, imamo tri koraka. Sortiranje lijevu polovicu elemenata, sortiranja Desna polovina od elemenata, a zatim spojiti sortirane polovice. Ono što je zanimljivo je da je Nekako sam punting, zar ne? Postoji vrsta kružnog definiciji na ovaj algoritam. U kojem je smislu ovaj algoritam je definicija kružne? PUBLIKA: [nečujno]. DAVID Malan: Da, moj algoritam za sortiranje, dvojica njegovih koraka "svojevrsni nešto. "A, tako da moli Pitanje, dakle, ono što ću koristiti sortirati lijevu polovicu , a desna polovica? A ljepota je u tome što, iako opet, to je um-savijanje dio potencijalno, možete koristiti isti algoritam za sortiranje lijevu polovicu. Ali čekaj malo. Kad ste rekli da razriješi lijeva polovica, što su dvije koraka će biti sljedeći? Mi ćemo sortirati lijevu polovicu lijeva polovica i pravo polovica lijeve polovice. Dovraga, kako mogu sortirati i one dvije polovice ili četvrtine, sada? Ali to je u redu. Imamo sortiranja algoritam ovdje. I iako možda brinite, na Prvi je to vrsta beskonačnog petlje, to je ciklus koji nikada nije ide do kraja - to je idući u završiti nakon što se događa? Kada n je manje od 2. Što na kraju će se dogoditi, jer ako bi se prepoloviti, a prepoloviti u prepoloviti te polovice, sigurno na kraju ti si idući u kraj sa samo 1 ili 0 elemenata. U tom trenutku, ovaj algoritam kaže da ste učinili. Dakle, prava čarolija u ovom Algoritam se čini da se u da je konačni korak, spajanjem. Ta jednostavna ideja jednostavno spajanje dvaju stvari, to je ono što se događa u konačnici kako bi se omogućilo nam da sortirati niz, recimo, osam elemenata. Dakle, imam još osam stres loptice do Ovdje, osam komada papira, i jedan Google Glass - što sam mogao zadržati. [Smijeh] DAVID Malan: Ako smo mogli potrajati osam volonteri, pa da vidimo možemo li igrati ovu out, tako da. Wow, OK. Računarstvo je sve zabavno. U redu. Dakle, o tome što tri, Najveći ruku gore. Četiri u leđa. A što ćemo vam napraviti tri u ovom nizu? I četiri u prednjem. Dakle, osam, daj se. [Smijeh] DAVID Malan: Ja sam zapravo ne znam što je to. Je li to stres loptice? U stolna lampa? Materijal? Internet? OK. Pa hajde gore. Tko bi htio - zadržati dolaze. Idemo vidjeti. A to vas stavlja u položaj - ti si u jednom mjestu. Uh-oh, čekaj malo. 1, 2, 3, 4, 5, 6, 7 - O, dobro. Dobro, dobro smo. U redu, tako da svatko ima sjedište, ali ne na Google Glass. Dopustite mi da na red ovih gore. Koje je tvoje ime? MICHELLE: Michelle. DAVID Malan: Michelle? U redu, ti izgledati geek, ako je to u redu. Pa, ja također, pretpostavljam, samo na trenutak. U redu, čekanja. Pokušali smo doći do koristite slučaj za Google Glass, a mi mislio da će to biti zabavno samo raditi ovo kad su ljudi na pozornici. Mi ćemo snimiti svijet iz njihove perspektive. U redu. Nije vjerojatno ono što Google namjerava. U redu, ako vam ne smeta nosio ovo idućih nespretan minuta, to bi bilo divno. U redu, tako da ovdje imamo niz elementi, te da niz, kao i po papirići u tih ljudi ' Ruke, trenutno nesortirani. MICHELLE: Oh, to je tako čudno. DAVID Malan: To je prilično slučajna. I u samo nekoliko trenutaka, idemo pokušati provesti spojiti neku zajedno i vidjeti gdje je taj ključni uvid. A trik ovdje s udruživanjem vrste je nešto što nismo još uvijek pretpostavlja. Mi zapravo treba neki Dodatni prostor. Dakle, što će biti posebno Zanimljivo je o tome da su ti Dečki će se kretati malo bitni, jer ću pretpostaviti da postoji dodatni niz prostora, recimo, odmah iza njih. Dakle, ako ste iza svog stolca, to je sekundarna polja. Ako oni sjede ovdje, to je Primarni polja. No, to je resurs koji imamo Nije iskoristio dosad s mjehur sortiranje, uz izbor sorte, s umetanja vrste. Sjetite se prošlog tjedna, svi samo vrsta miješaju u mjestu. Oni nisu koristili nikakvu dodatnu memoriju. Mi smo napravili mjesta za osobe koje kretanje ljudi oko sebe. Dakle, ovo je ključni uvid, previše. Tu je ova trgovina-off, u cjelini u računalne znanosti, resursa. Ako želite ubrzati nešto kao što su vrijeme, ti ćeš morati platiti cijenu. A jedna od tih cijena je vrlo često prostor, količina memorije ili tvrdog prostor na disku koji koristite. Ili, iskreno, iznos programer vremena. Koliko je vremena potrebno vam, ljudi, se zapravo provesti neke više komplicirano algoritam. Ali za danas, trade-off je vrijeme i prostor. Dakle, ako ti dečki samo mogao držati do svoje brojeva, tako možemo vidjeti da ste doista podudaranje 4, 2, 6, 1, 3, 7, 8. Izvrsno. Pa ću pokušati orkestrirati stvari, ako dečki mogu jednostavno slijedite moj vodstvo ovdje. Tako ću provesti, prvo, Prvi korak u pseudocode, što je na ulaz od n elemenata, ako je N manji od 2, a zatim se vratiti. Očito, to ne primjenjuju, tako da možemo krenuti dalje. Dakle, sortirati lijevu polovicu elemenata. Dakle, to znači da ću se usredotočiti moju pozornost samo na trenutak na njih Četiri dečki ovdje. U redu, što trebam učiniti iduće? PUBLIKA: Sortiranje lijevu polovicu. DAVID Malan: Pa sad moram sortirati lijeva polovica od tih momaka. Jer opet, preuzeti na sebe u Cilj je riješiti lijevu polovicu. Kako ćete to učiniti? Samo slijedite upute, čak i iako mi to opet. Dakle, sortirati lijevu polovicu. Sada sam sortiranja ove dvije dečki. Što je sljedeće? PUBLIKA: Sortiranje lijevu polovicu. DAVID Malan: Sortiranje lijevu polovicu. Pa sad ti, ovo sjedalo ovdje, je popis veličine 1. I ono zoveš? PRINCEZA DAISY: Princeza Daisy. DAVID Malan: Princeza Daisy je ovdje. I tako je već riješeno, jer je Popis je veličine 1. Što trebam učiniti iduće? OK, vratite, jer to je popis od veličina 1, što je manje od 2. Nakon što je sljedeći korak? A sada morate vrsta backtrack u vašem umu. Sortiranje desnu polovicu, što je - kako se ti zoveš? LINDA: Linda. DAVID Malan: Linda. I tako što ćemo sada da imamo popis veličine 1? PUBLIKA: Povratak. DAVID Malan: Oprezno. Vraćamo prva, a sada treći korak - a ako Nekako sam se prikazuju prema ušle dva mjesta sada, sada sam morati spojiti ta dva elementa. Tako sada, nažalost, elementi su izvan funkcije. No, to je mjesto gdje proces pripajanja počinje da se uvjerljiv. Dakle, ako ti dečki mogli ustati za jednostavno Trenutak, idem da vam je potrebno, u Trenutak, na korak iza stolica. A ako Linda, jer je 2 manji od četiri, zašto ne li navratiti prvi? Ostani tamo. Dakle, Linda, što navratiti na prvom mjestu. Sada je u stvarnosti i ako je samo niz samo smo je mogli kretati u stvarnom vremenu od ove stolice na tom mjestu. Pa zamislite da je neki stalni Broj koraka 1. A sada - ali moramo vas staviti u prvo mjesto ovdje. I sad ako bi mogao navratiti, kao dobro, idemo na biti u mjestu dva. I iako se osjeća kao da je uzimajući neko vrijeme, ono što je lijepo sad je da je lijeva polovica lijeva polovica je sada riješeno. Dakle, što je sljedeći korak, ako mi sada premotati dalje u priči? PUBLIKA: desna polovica. DAVID Malan: Sortiranje desnu polovicu. Dakle, što vi imate za to, kao dobro. Dakle, ako mogu ustati samo na trenutak? A kako se ti zoveš? JESS: Jess. DAVID Malan: Jess. U redu, tako da Jess je sada lijevo polovica desnoj polovici. I tako je ona lista veličine 1. Očito je riješeno. I zoveš? MICHELLE: Michelle. DAVID Malan: Michelle je očito Popis veličine 1. Već je riješeno. Tako sada magija se događa, Proces spajanja. Dakle, tko će biti na prvom mjestu? Očito Michelle. Dakle, ako bi mogao navratiti vratiti. Prostor imamo na raspolaganju za nju sada je odmah iza tog stolca ovdje. A sad, ako bi se mogla vratiti kao dobro, mi sada imamo, da bude jasno, dva polovice, od kojih je svaki veličine 2 - i samo za prikaz miloga, ako mogao bi malo prostora - jedan lijevo polovice ovdje, jedan Desna polovina ovdje. Rewind dalje u priči. Koji je sljedeći korak? PUBLIKA: pisma. DAVID Malan: Sada moramo spojiti. Pa OK, tako da sada, srećom, možemo Samo oslobodio četiri stolice. Tako smo se i dvostruko više memorije, ali možemo dati flip-flopping između dva polja. Dakle koji broj je na prvom mjestu? Dakle Michelle, očito. Dakle navratiti i uzeti svoje mjesto ovdje. I tada se broj 2 je očito Sljedeći, tako da ovdje dolaze. Broj 4, broj 6. I opet, iako postoji Malo šetnje su uključeni, Stvarno, to bi se moglo dogoditi odmah, pomicanjem jedan - OK, dobro igrao. [Smijeh] DAVID Malan: I sad smo u prilično dobrom stanju. Lijeva polovica cijeli Ulaz je sada riješeno. U redu, tako da su ti dečki imali Prednost moje - kako se to završiti sve djevojke na lijevo i svi dječaci na desnoj strani? U redu, tako da dečki 'Okrenimo se sada. Dakle, neću vas kroz ti koraci. Mi ćemo vidjeti ako mi može ponovo isto pseudocode. Ako želite ići naprijed i stand up, a vi, dopustite mi da vam mikrofon. Vidi ako ne može ponoviti ono samo mi je ovdje na drugi kraj popisa. Tko treba govoriti prvi, temelji na algoritmu? Dakle objasniti što ste radili prije nego što bi bilo stopala pokrete. ZVUČNI 1: U redu, tako da od Ja sam lijeva polovica lijeva polovica, vraćam. Točno? DAVID Malan: Dobro. ZVUČNI 1: A onda - DAVID Malan: Tko mic ići dalje? ZVUČNI 1: Sljedeći broj. ZVUČNI 2: Dakle, ja sam desna polovica na lijevoj polovici lijeva polovica, a ja sam se vratiti. DAVID Malan: Dobro. Vraćate. Pa sad što je sljedeći za vas dvoje? ZVUČNI 2: Želimo vidjeti tko je manja. DAVID Malan: Točno. Želimo spojiti. Prostor ćemo koristiti za spajanje ste u, iako su Očito je već riješeno, idemo slijediti isti algoritam. Pa tko ide natrag prva? Pa je 3, a zatim 7. I sad ide mic s tim dečkima, OK? ZVUČNI 3: Tako sam desnu polovinu lijeva polovica, i moje n je manje od 1, tako da sam samo ću proći - DAVID Malan: Dobro. ZVUČNI 4: Ja sam desnu polovinu desnu polovinu desnoj polovici, a ja sam Također jedna osoba, tako da sam će se vratiti. Dakle, sada smo spojiti. ZVUČNI 3: Tako smo se vratiti. DAVID Malan: Znači li ići u leđa. Dakle, 5 ide prvi, a zatim 8. A sada publike, što je korak moramo sada premotati natrag u našim glavama? PUBLIKA: pisma. DAVID Malan: Spajanje lijeve i desne polovice polovice izvornog lijeve polovice. Pa sada - i samo da se to jasno, napraviti malo prostora između vas dvojica. Dakle, sada kada je na dva popisa, lijevo i desno. Pa kako ćemo sada spojiti li dečki u prednji red sjedala opet? 3. ide prvi. Zatim 5, očito. Zatim 7, 8 i sad. U redu, a sada smo? PUBLIKA: Nije učinjeno. DAVID Malan: Nije učinjeno, jer je Očito, postoji jedan korak preostalo. Ali opet, razlog sam koristeći ovaj žargonu kao "unatrag u vašem umu," to je zato što je stvarno što se događa. Idemo kroz svih ovih koraka, ali mi smo vrsta zaustavio Trenutak, ronjenje dublje u Algoritam, zastavši na trenutak, ronjenje dublje u algoritmu, a Sada moramo vrsta unatrag u našoj umovi i poništavanje svih tih slojeva da smo vrsta stavili na čekanje. Tako sada imamo dvije liste veličine 4. Ako ti dečki mogu ustati posljednji put i napraviti malo prostora ovdje jasno da je to lijeva polovica izvornika, Desna polovina od izvornika. Tko je prvi broj koji smo trebaju povući u leđa? Michelle, naravno. Tako smo stavili Michelle ovdje. A tko ima broj 2? Broj 2 dolazi na leđa kao dobro. Broj 3? Izvrsno. Broj 4, broj 5, broj 6, broj 7, i broj 8. U redu, tako da se osjeća kao puno koraka, sigurno. No, sada ćemo vidjeti, ako ne možemo potvrditi vrsta intuitivno da je to Algoritam temelja, posebice n dobiva stvarno velik, kao što smo vidjeli s animacije, je bitno brži. Dakle, ja tvrdim ovaj algoritam, u najgorem slučaj, a čak iu najboljem slučaju, je velika O n puta log n. To je, tu je neki aspekt ove algoritam koji se n korake, ali postoji još jedan aspekt negdje u da iteracija, da petlje, da traje log n korake. Možemo li staviti prst na ono što naš onima dva broja se odnosi? Pa, gdje je - otkud mic ide? ZVUČNI 1: Biste prijavite se n nas nego što se u dvije - podijeli s dva, u biti. DAVID Malan: Točno. Svaki put smo vidjeli u bilo kojoj algoritma time sada, tu je bio takav obrazac podjele, podjele, podjele. I to je obično smanjuje za nešto što je logaritamska, prijavite baza 2. Ali, to stvarno može biti bilo što, ali prijaviti bazu 2. Sada što je n? Vidim da smo vrsta te podijeliti Dečki - ti podijeljene, te podijeliti, ti podijeljene, te podijeljeni. Gdje je kraj dolaze iz? Tako da je spajanjem. Jer misle o tome. Kada spojite osam ljudi zajedno, pri čemu polovica njih su set od četiri , a druga polovica su drugi set od četiri, kako idete radi o spajanju? Pa, vi to učinio prilično intuitivno. Ali, ako sam to učinio umjesto da malo više metodički, možda sam ukazao na Lijevi osoba prvi put s moje lijeve strane S druge strane, istaknuo je na lijevom osobi Od toga polovicu s moje desne strane, i Samo naknadno prošetao Popis, pokazujući na najmanji element svaki put, kreće moj prst preko i više po potrebi tijekom popisa. No, ono što je ključno za ovo spajanje Proces je sam usporedbom tih para elemenata. S desne polovice i od lijeva polovice, nikada neću još zaostaje. Znači spajanje sama izvodi ne više od n koraka. I koliko puta sam imala za to spajanje? Pa, ne više od n, a mi samo vidio da je s konačnim spajanja. I tako, ako to učinite nešto što traje log n koraka n puta, ili obratno, to će nam dati n puta log n. I zašto je ovo bolje? Pa, ako već znate da je zapisnik n je bolji od n - zar ne? Vidjeli smo u binarnom pretraživanje, telefonski imenik Primjer, log n je svakako bolje nego linearno. Dakle, to znači da je n puta log n Definitivno bolje od n puta drugi n, n AKA kvadrat. I to je ono što mi u konačnici osjećam. Tako veliki aplauz, ako se smo mogli, za ove dečke. [PLJESAK] DAVID Malan: A svoje oproštajne darove - možete zadržati brojeve, Ako biste željeli. I vaš oproštajni dar, kao i obično. Oh, a mi ćemo vam poslati snimke, Michelle. Hvala Vam. U redu. Posluži se stres loptu. I neka mi povucite prema gore, u međuvremenu, naš prijatelj Rob Bowden ponuditi nešto drugačiji pogled na ovo, jer možete misliti o tim Koraci se dešavaju u nešto drugačiji način. U stvari, set-up za ono što Rob je o da nam pokaže pretpostavlja da imamo već učinjeno parcelacija veliki popis u osam malih popisima, svaki od veličine 1. Dakle, mi smo promjenom pseudocode Malo samo da vrsta dobiti na Temeljna je ideja o tome kako spajanjem djela. No, vrijeme rada što on je o to učiniti još će biti isti. I opet, set-up je da je on počeo s osam lista veličine 1. Dakle, što ste propustili dio gdje je on zapravo učinio log N, N, log log n dijeljenjem ulazu. [Video reprodukciju] -To je to za korak jedan. Za drugi korak, više puta spajanje parova liste. DAVID Malan: Hm. Samo zvuk dolazi iz moje računalo. Pokušajmo to opet. -Samo svojevoljno izabrati koje - Sada imamo četiri liste. Saznajte prije. DAVID Malan: Tu smo. Stapanje-108 i 15, možemo završiti s popisa 15, 108. Spajanje 50 i 4, mi završiti s 4, 50. Spajanje 8 i 42, što završiti s 8, 42. I spajanjem 23 i 16, što završiti s 16, 23. Sada svi naši su popisi veličine 2. Primijetiti da je svaki od četiri lista je riješeno. Dakle, možemo početi spajanjem para popisima ponovno. Spajanje 15 i 108 i 4 i 50, što Prvi uzeti 4, a zatim 15, a zatim 50, a zatim 108. Spajanje 8, 42 i 16, 23, prvo se 8, a zatim 16, zatim 23, zatim 42. Tako sada imamo samo dvije liste veličine 4, od kojih je riješeno. Dakle, sada smo spojiti te dvije liste. Prvo, uzmemo 4, a zatim smo se 8, onda ćemo uzeti 15, zatim 16, a zatim 23, a zatim 42, zatim 50, a zatim 108. [END video reprodukciju] DAVID Malan: Opet, obavijest, on nikada dotakla dao šalicu više od jedan put nakon što napreduje dalje od njega. Dakle, on nikada ponoviti. Dakle, on je uvijek kreće na stranu, i to je mjesto gdje smo dobili naše n. Zašto ne pustiti mene podići jednu animaciju da smo ranije vidjeli, ali ovaj put fokusiranje samo na pisma vrste. Dopustite mi da ide naprijed i zumiranje u ovo ovdje. Prvo neka mi odabrati slučajan ulaz, uveličati ovu, a možete sortirati mjesta vide ono što mi je uzeo zdravo za gotovo, ranije, sortiranje pisama zapravo radi. Dakle, primijetite da ste dobili ove polovice ili ove četvrtine ili to osmina problem koji sve odjednom počnete uzimati dobru formu. I onda napokon, vidite, na samom kraju da bam, sve spojene zajedno. Dakle, ovo su samo tri različita se na istu ideju. No, ključni uvid, baš kao razdjelnice i osvojiti već u prvom razredu, bilo da smo odlučili da na neki način podijeliti Problem u nešto veliko, u nešto vrsta identične u duhu, , ali manji i manji i manji i manji. Sada još jedan zabavan način da se sortirati think o njima, iako to nije će vam dati isti intuitivno razumijevanje, je sljedeće animacije. Dakle, ovo je video netko staviti zajedno koji povezuje različite zvukovi s različitih poslovnih aktivnosti umetanja sortiranje, za udruživanjem vrste, i za par drugih. Dakle, u ovom trenutku, ja ću pogoditi Play. To je oko minutu. I iako još uvijek možete vidjeti obrasci događa, ovaj put možete Također čuti kako ti algoritmi su obavljanje drugačije i Nešto različitih uzoraka. To je neka vrsta umetanja. [Tonova igraju] DAVID Malan: Ponovno se pokušava za umetanje svaki element u kojoj je zaposlen. To je neka vrsta balon. [Tonova igraju] DAVID Malan: I vi možete sortirati dodira Kako relativno malo rade to radi na svakom koraku. To je ono što zvuči kao dosadu. [Tonova igraju] DAVID Malan: Ovo je neka vrsta odabira, gdje smo odabrali element želimo by prolazi kroz opet i opet i opet i nalazi se na početku. [Tonova igraju] DAVID Malan: Ovo je neka vrsta pisma, koje zaista možete početi osjećati. [Tonova igraju] [Smijeh] DAVID Malan: Nešto što se zove gnome sortiranje, koji nismo gledali. [Tonova igraju] DAVID Malan: Pa da vidim, sada, rastresena kao što su nadamo strane glazba, ako ja mogu skliznuti malo Malo matematike ovdje. Dakle, postoji četvrti put da možemo razmišljati o tome što to znači to funkcije koje će se brže od onih koje smo vidjeli prije. A ako ste došli na tečaj iz matematike pozadini, što zapravo zna možda već da može slap mandat na tom tehnikom - Naime rekurzija, funkcija nekako se zove. A opet, sjećam da spajanje vrsta pseudocode je rekurzivna u smislu da je jedan od Spoji sortirati o koracima je nazvati neku - to je, sama po sebi. No, srećom, jer mi je zadržao zove vrsta, ili spojiti vrsta, Naime, na sve manji i manji i manji popis, na kraju smo dno zahvaljujući tome što ćemo nazvati osnovni scenarij, tvrdi kodirani slučaj da rekao, ako popis je mali, manji od 2 u tom slučaju, jednostavno odmah vratiti. Ako nismo imali taj poseban slučaj, Algoritam nikad i dno, a vi bi doista dobili u klapa doista zauvijek. No, pretpostavimo da smo htjeli sada staviti neke brojeve na to, opet, pomoću n kao veličina ulaza. I htjela sam vas pitati, što je ukupno vrijeme koji su uključeni u radi spajanja vrsta? Ili općenitije, ono što je Trošak njega na vrijeme? Pa to je prilično lako izmjeriti da. Ako n je manje od 2, vrijeme potrebno u razvrstavanje n elemenata, gdje n je 2, 0 je. Budući da smo upravo vratili. Nema posla koji treba obaviti. Sada vjerojatno, možda je to jedan korak ili dva koraka shvatiti količinu rade, ali to je dovoljno blizu da je 0 Samo ću reći nema posla potreban ako popis je tako mali biti nezanimljiv. No, ovaj slučaj je zanimljiv. Rekurzivna slučaj bio grana pseudocode da je rekao drugdje, svojevrsni lijeva polovica, sortiranje pravo polovice, spojiti dvije polovice. Sad zašto se ovaj izraz predstavlja taj trošak? Pa, T n samo znači Vrijeme za sortiranje n elemenata. A onda na desnoj strani znak jednakosti tamo, T n podijeljeni by 2 se odnosi na troškove čega? Sortiranje lijevu polovicu. Druga T n dijelimo s 2 je vjerojatno se odnosi na trošak za sortirati desnu polovicu. A onda plus n? Je spajanjem. Jer, ako imate dvije liste, jednu od Veličina n više od 2, a drugi veličine n više od 2, morate biti dotaknuti svaki od tih elemenata, baš kao Rob dotakla svaki od šalice, i samo kao što je ukazao na svakom od Volonteri na pozornici. Tako je n trošak spajanja. Sada, nažalost, ova formula Također je sama rekurzivna. Dakle, ako se postavi pitanje, ako je n, recimo, 16, ako ima 16 ljudi na pozornici ili 16 šalica u videu, koliko je ukupno koraka je potrebno da ih sortirati udruži s vrstom? To je zapravo nije očigledan odgovor, jer sada morate izdvojiti od rekurzivno odgovoriti na ovu formulu. Ali to je u redu, jer neka mi predloži da ćemo učiniti sljedeće. Vrijeme koji su uključeni za sortiranje ili 16 ljudi 16 šalice će biti predstavljeni općenito, kao T od 16 godina. Ali to jednako, prema našim prethodnu formulu, 2 puta iznos Vrijeme koje je potrebno za sortiranje 8 šalice plus 16. I opet, plus 16 je vrijeme za spajanja, i dva puta T je od 8. Vrijeme za sortiranje lijevu polovicu i desnu polovicu. Ali opet, to nije dovoljno. Mi moramo zaroniti u dublje. To znači da ćemo morati odgovarati Pitanje, što je T od 8? Pa T od 8 je samo 2 T puta od 4 plus osam. Pa, ono što je T od 4? T od 4. je samo 2 puta T od 2 plus četiri. Pa, ono što je T od 2? T od 2 je samo 2 puta T od 1 plus dva. I opet, mi smo vrsta dobivanja zaglavi u ovom ciklusu. No, to je oko pogoditi da je tzv. osnovni scenarij. Jer ono što je od 1. T, nije tvrdimo? 0. Dakle, sada je konačno, možemo raditi unatrag. Ako T od 1 je 0, ja sada mogu ići natrag gore jedan poredati prema ovom čovjeku ovdje, a ja mogu priključite 0 za T iz jedne. Dakle, to znači da je jednaka dva puta nula, inače poznat kao 0, plus dva. I tako da je cijeli izraz je 2. Sada, ako sam uzeti T od 2, čiji odgovor je 2, uključite ga u srednjoj liniji, T od 4, to mi daje dva puta 2 plus 4, pa 8. Ako sam tada priključiti 8 do prethodna linije, to mi daje 2 puta 8, 16. A ako smo tada i dalje da s 24, dodavanjem u 16., napokon smo dobili vrijednost 64. Sada kada je i sama vrsta govori ništa za n zapis, O veliki, omega kojeg smo pričali. No, ispada da je doista 64 16, veličina ulaz, prijavite bazu dvije od 16 godina. A ako je to nešto nepoznato, samo mislim vratiti, i to ću se vratiti da vas na kraju. Ako je ovo dnevnik baza 2, to je kao 2 podigli na ono što vam daje 16? Oh, to je 4, tako da je 16 puta 4. I opet, to nije velika stvar, ako to svojevrsni je maglovita sjećanja sada. Ali za sada, uzeti na vjeri da 16 log 16 je 64. I tako je doista, s ovom jednostavnom zdravom razumu provjerili smo potvrdili - ali ne dokazuje službeno - da je vrijeme rada spajanja svojevrsni je doista n log n. Dakle, nije loše. To je svakako bolje nego Algoritmi koje smo vidjeli do sada, i to je zato što smo iskoristio, jedan, Tehnika se zove rekurzija. No, zanimljivije od toga, da je pojam podjele i osvajati. Opet, doista tjedna 0 stvari koje i sada se ponavlja u više uvjerljiv način. Sada zabavno malo vježbe, ako ste Nikad to učinio - i vjerojatno Ne bi, jer je svojevrsni normalno ljudi ne misle da to učinite. Ali ako idem na google.com, a ako Želim naučiti nešto o rekurzija, Enter. [Smijeh] [VIŠE Smijeh] DAVID Malan: loša šala polako širi. [Smijeh] DAVID Malan: Samo u slučaju, da je ona tu. Nisam to piše u krivu, a tu je šala. U redu. Objasnite to ljudi pored vas, ako to nije dosta kliknuo samo još. No, rekurzija, općenito, odnosi se na proces funkcije poziva sama, ili općenitije, dijeljenjem Problem u nešto što može biti riješiti parče rješavanjem identični predstavnička problemi. Pa, neka je promjena stupnjeva prijenosa samo na trenutak. Mi smo željeli završiti na određenim cliffhangers, pa krenimo za postavljanje faza, za nekoliko minuta, na vrlo jednostavnom idejom - da je od zamjene dva elementa, zar ne? Sve ove algoritama smo bili govori o posljednjih nekoliko Predavanja uključuju neke vrsta zamjene. Danas je vizualizirano od strane uzimajući ih up iz svojih stolica i šetnju, ali u kodu, mi bismo samo uzeti jedan element iz jednog polja i buć ga u drugu. Pa kako ćemo ići oko radiš ovo? Pa, neka mi ići naprijed i pisati Program brzo ovdje. Ja ću ići naprijed i učiniti ovo što je sljedeće. Nazovimo to - Što želimo nazvati ovo? Zapravo, nije. Dopustite mi premotati. Ne želim to učiniti Još alpinista. To će pokvariti zabavu. Učinimo to, umjesto. Pretpostavimo da želim napisati nešto Program obuhvaća i da je sada to Ideja rekurzije. Nekako sam dobio ispred sebe ima. Ja ću učiniti sljedeće. Prvo, brzi su od standardnog io.h, kao i uključuju mjesta cs50.h. A onda ću ići naprijed i proglasiti int main prazninu na uobičajeni način. I shvatio sam elek-tro konvulzivna datoteku, tako da neka mi samo dodati. C produljenje ovdje tako da možemo prevesti ga ispravno. Započnite ovu funkciju off. A funkcija želim pisati, sasvim Jednostavno, to je jedna pita Korisnik za broj, a zatim zbraja svi brojevi između da broj i, recimo, 0. Dakle, prvo ću ići naprijed i proglasiti int n. Tada sam kopirati neki kod koji upotrijebili smo za neko vrijeme. Dok je nešto istinito. Ja ću se vratiti na to u trenutku. Što želim učiniti? Želim reći printf pozitivno cijeli molimo. A onda ću se kažu n dobiva se int. Pa opet, neki predloženi broj koje smo koristili prije. I ja ću to učiniti a n je manje od 1. Dakle, to će osigurati da korisnik mi daje pozitivan cijeli broj. A sada ću učiniti sljedeće. Želim zbrojiti sve brojeve između 1 i i n ili 0, i n, ravnopravno, kako bi dobili ukupnu sumu. Tako veliko sigma simbol da je možda podsjetiti. Dakle, ja ću to učiniti prvi poziv Funkcija se zove Sigma, to prolazi u n, a onda ću se printf kažu, odgovor je ovdje. Dakle, ukratko, sam doći i int od korisnika. Ja bi to pozitivno. Izjavljujem varijablu odgovor Tip int i trgovina u njoj povratak Vrijednost sigma, prolazeći u n kao ulaz. A onda sam isprintati taj odgovor. Nažalost, iako zvuči sigma kao nešto što bi moglo biti u math.h file, njegova izjava, to zapravo nije. Dakle, to je u redu. Ja mogu provesti ovaj ja osobno. Idem implementirati funkciju pod nazivom sigma, i to će potrajati parametar - Nazovimo to m, samo tako da je drugačije. I onda se ovdje, ja ću reći, i, ako je m je manji od 1 - to je vrlo nezanimljivih programa. Dakle, ja ću ići naprijed i odmah vratiti 0.. To jednostavno nema smisla da zbrojimo sve su brojevi između 1 i m ako m Sam je 0 ili negativan. A onda ću ići naprijed i to vrlo iterativno. Ja ću učiniti ovu vrstu stare škole, i ja ću ići naprijed i reći da ću se proglasiti iznos biti 0. Tada ću imati za petlju int - i neka mi to učiniti da bude jednak Raspodjela broj, tako da imate kopiju kod kuće. int i dobiva jedan na do i manji od ili jednak m. i plus plus. A onda unutar ove for petlje - skoro smo stigli - Zbroj dobiva iznos plus jedan. A onda ću se vratiti svotu. Pa sam to učinio brzo, doduše dosta. Ali opet, glavna funkcija je lijepa jednostavno, na temelju koda smo napisano do sada. Koristi dual loop dobiti pozitivno int od korisnika. I onda prođe taj int na novu funkciju zove Sigma, nazivajući ga, opet, n. I sam pohraniti povratnu vrijednost, odgovor iz crne kutije trenutačno poznat kao sigma, u varijabla zove odgovor. Onda sam ga ispisati. Ako mi sada nastaviti priču, Kako se provodi sigma? Predlažem provesti na sljedeći način. Prvo, malo provjeru pogrešaka kako bi bili sigurni da korisnik nije petljaju sa mnom i prolazi u Neki negativna ili 0 vrijednosti. Tada sam proglasiti varijablu pod nazivom Ukratko i postavite na 0. I sad sam se početi kretati od ja jednaka 1 pa sve do i uključujući m, jer želim uključiti sve brojeva od jedan do m, uključivo. A unutar toga za petlju, ja samo to Zbroj dobiva ono što je sada, plus vrijednost i. Plus vrijednost i. Kao na stranu, ako niste vidjeli ovo prije, ima nekih sintaktička šećera za ovu liniju. Ja mogu napisati to kao plus ja jednako, samo da ste sebi nekoliko pritisaka tipke i gledati malo hladnije. Ali to je sve. To je funkcionalno ista stvar. Nažalost, ovaj broj je Ne ide sastaviti još. Ako sam pokrenuti bi sigma 0, kako sam Ja ću dobiti vikao na? Što će se ne sviđa? PUBLIKA: [nečujno]. DAVID Malan: Da, nisam proglasi Funkcija do vrha, zar ne? C je glupo, u smislu da je samo čini ono što vam reći što učiniti, a vi moraju to učiniti u tom redoslijedu. I tako, ako sam pogodio Unesite ovdje, ja ću dobili upozorenje o sigma implicitno Deklaracija. Oh, nije problem. I može ići do vrha, a mogu kažu, sve u redu, čekaj malo. Sigma je funkcija koja vraća int a očekuje int kao ulazni, zarez. Ili sam mogao staviti cijeli funkciju Glavni iznad, ali općenito, ja bih Preporučujem protiv toga, jer je lijepo je uvijek imati glavni na vrhu tako možete roniti u pravu i znaju što Program radi čitajući glavna prvi. Pa sad neka mi jasan zaslon. Remake sigma 0. Sve se čini da provjerite. Dopustite mi da vodim sigma 0. Pozitivno me. Ja ću mu dati broj 3 da bi to jednostavno. Tako da bi mi dati 3 plus 2 plus 1, tako 6. Enter, i doista sam se šest. Ja mogu učiniti nešto veći - 50, 12, 75. Baš kao tangentu, ja ću to učiniti nešto smiješno kao što je stvarno velik broj, Oh, kako je zapravo razrađen - eh, ja ne mislim da je u pravu. Idemo vidjeti. Idemo jako igrati s njim. To je problem. Što se zbiva? Broj nije tako loše. To je još uvijek linearno. Zviždanje je dobar učinak, iako. Što se zbiva? Ne siguran ako sam to čuo. Tako ispada - a ovo kao na stranu. To nije jezgra Ideja rekurzije. Ispada, jer sam pokušavao predstavlja takav veliki broj, većina Vjerojatno je se pogrešno tumači C Ne kao pozitivan broj, , ali negativni broj. Nismo razgovarali o tome, ali to Ispada postoje negativni brojevi u svijetu osim do pozitivnih brojeva. A način na koji možete predstavljaju negativan broj bitno je, koristite jedan Posebna malo naznačiti pozitivni tijekom negativna. To je malo složeniji od toga, ali to je osnovna ideja. Dakle, nažalost, ako je C je zbunjujuće jedan od tih bitova što zapravo znači, Oh, to je negativni broj, moj petlje Ovdje, na primjer, je zapravo nikad nije će se prekinuti. Dakle, ako sam zapravo ispisuje nešto opet i opet, mi bismo vidim puno. Ali opet, to je osim točke. To je zapravo samo vrsta intelektualnu znatiželju da ćemo doći natrag na kraju. Ali za sada, ovo je točno Provedba ako pretpostavimo da Korisnik će osigurati Ints da stane u roku Ints. No ja tvrdim da je to broj, iskreno, može učiniti puno više jednostavno. Ako je cilj na ruku je da se broj m kao i dodati mu sve brojevi između njega i 1, ili obrnuto između 1 i to, ja tvrdim da ja mogu posuditi ovu ideju da spajanje sortiranje imala, koji je vodeći problem ove veličine i dijeljenjem u nešto manjoj. Možda nije ni upola, ali manji, ali reprezentativno isti. Sve ideje, ali manji problem. Dakle, ja sam zapravo - neka mi spremiti ovu datoteku s različitim brojem verzije. Zvat ćemo ovu verziju 1 umjesto 0. A ja tvrdim da sam zapravo mogu reimplement to u ovom vrstom um-savijanje način. Ja ću ostaviti dio nje same. Ja ću reći, ako m je manje od ili čak jednak 0 - Samo ću se malo više analni ovaj put s mojim provjere pogreške - Ja ću ići naprijed i povratak 0. To je proizvoljna. Ja sam samo jednostavno odlučivanje, ako korisnik mi daje negativan broj, ja sam vraća 0, i oni bi trebali imati čitanje Dokumentacija pobliže. Drugo - primjetiti ono što ću učiniti. Inače ću se vratiti M PLUS - Što je sigma od m? Pa, sigma m od plus minus 1 m, plus minus 2 m, plus minus 3 m. Ne želim pisati sve to van. Zašto ne ja samo punt? Rekurzivno sebe nazivaju s nešto manji problem, zarez, i pozvati ga na dan? Točno? Sada i ovdje, možda ćete osjetiti ili brinuti da je beskonačna petlja koja sam izaziva, pri čemu sam provedbi Sigma pozivom sigma. Ali to je savršeno u redu, jer sam Mislio uoči dodao koji linije? PUBLIKA: [nečujno]. David Malan: 23 do 26 godina, koji Ako je moj uvjet. Jer ono što je lijepo o Oduzimanje ovdje, jer sam držati Predaja Sigma manji problemi, manja Problemi, manja - to nije upola manji. To je samo korak beba manja, ali to je u redu. Jer na kraju, mi ćemo raditi naš put prema dolje do 1 ili 0.. A kad smo pogodak 0, sigma nije će se zvati više. To će se odmah vratiti 0.. Tako je učinak, ako je ovo vrsta vjetra u vašem umu, je dodati M PLUS m minus 1, plus minus 2 m, plus minus m 3, plus točka, točka, točka, m minus m, na kraju dajući vam 0, a Učinak je u konačnici dodati sve ove stvari zajedno. Pa nismo, s rekurzije, riješiti problem koji smo nije mogao riješiti prije. Doista, verzija 0 toga, i svaka Problem do danas, je rješiva sa samo pomoću za petlje ili dok se petlje ili slični konstrukti. No, rekurzija, usuđujem se reći, daje nam drugačiji način razmišljanja o problemima, pri čemu ako se može uzeti Problem, podijelite ga s nečim Veliki nešto u nešto nešto manja, ja tvrdim da možemo to riješiti možda malo više elegantno u smislu od dizajna, s manje koda, a možda čak i riješiti probleme koji bi biti teže, jer ćemo na kraju vidi, rješavanje čisto iterativno. No, roman u koji sam učinio žele nas ostaviti na bilo to. Dopustite mi da ide naprijed i otvorite up file od - Zapravo, pusti me i to učiniti vrlo brzo. Dopustite mi da ide naprijed i predlaže sljedeće. Među današnjem kod je ovu sliku ovdje. Ova ovdje, noswap. Dakle, ovo je glupo malo program koji I šlag gore koji tvrdi da to učinite sljedeće. U glavnom, najprije izjavljuje int x pozvao i dodjeljuje vrijednost od 1. Tada je riječ int y i dodjeljuje joj vrijednost 2. Zatim ga ispisuje ono xiy je. Tada je, kaže, zamjene, dot dot dot. Onda ona tvrdi da se zove funkciju pozvao zamjenu, prolazeći u X i godina, ideja je da se nadamo xiy će se vratiti drugačija, suprotno. Tada je tvrditi zamijenili! s uskličnikom. Zatim ga ispisuje xiy. No, ispostavilo se da je to vrlo jednostavna demonstracija prema dolje Ovdje je zapravo lud. Iako sam privremenu promjenjiva i privremeno stavljanje u to, onda ću reassigning vrijednost b - koji osjeća razumno, jer sam spremiti kopiju na temp. Tada sam ažurirati b za jednake sve što je u temp. Ova vrsta oklopa igara kreće u B i b u koristeći ovaj srednje-čovjek zove temp osjeća savršeno razumno. Ali ja tvrdim da kad sam pokrenuti ovu broj, kao što ću učiniti sada - neka mi ići naprijed i zalijepite ga ovdje. Nazvat ću ovo noswap.c. I kao što ime sugerira, to nije će se odgovarajući program. Provjerite noswap. / Nema swapa. x je 1, y je 2, zamjene, zamijeniti. x je 1, y je 2. To je temeljno pogrešno, čak i iako ovo izgleda savršeno razumno mene. I tu je razlog, ali nismo će otkriti razlog samo još. Za sada u drugom Cliffhanger sam htjela vas ostaviti s je ovo, Najava vrsta na kupon kodovi. Naša inovacija s kasnim dana ove godine izazvalo je ne-beznačajan broj pitanja, što je Nije nam namjera. Namjera ovih kupon kodovi, pri čemu ako ne dio problema postavljen početkom, čime se dobiva dodatni dan, je stvarno pomoći ti dečki pomoći sami početi rano, vrsta od strane vas poticanje. Pomaže nam distribuirati opterećenje diljem Radno vrijeme bolje, tako da je to je vrsta win-win. Nažalost, mislim da moje upute nisu bili, do danas, vrlo jasno, tako da Vratio sam se ovaj vikend i ažurira spec. u većim, hrabriji teksta na objasni metke poput ovih. I samo da ga još što reći javno, prema Zadane, problem setovi su zbog četvrtak u podne, po nastavnom planu. Ako ste početi rano, završni dio Problem postavljena do srijede u 12:00 PM, dio koji se odnosi na kupon broj, ideja je da se može produljiti Rok za vaš P postavljena sve do petka. To je, odgrizao maleni dio P postavljena u odnosu na ono što je obično Veći je problem, a ti kupi se dodatni dan. Opet, to dobiva razmišljanja o Problem set, dobiva na vas Radno vrijeme prije. No, problem je još uvijek kupon potrebno, čak i ako ne pošaljete. No, više je to uvjerljivo. (STAGE WHISPER) I ti ljudi odlazi već ćeš se požaliti. Kao što su ljudi na balkonu. Unaprijed se ispričavam na narod na balkon iz razloga koji će biti jasno je u samo trenutak. Dakle, mi smo sretni da imaju jednu od CS50 je bivši šef nastavne novaci u Tvrtka se zove dropbox.com. Oni su vrlo velikodušno donirao kupon ovdje za ovu puno prostora, što je gore od Uobičajeni 2 gigabajta. Dakle, ono što sam mislio da će to učiniti na ovom Konačna napomena je to malo podijela, kojom se u samo trenutak, otkrit ćemo dobitnik, a tko ima kupon kod koji onda možete ići na njihove Web stranica, upišite ga u, i voila, dobili puno više prostora za svoje Dropbox aparata i za vaše osobne datoteke. I prvi, koji su željeli sudjelovati na ovom crtežu? OK, sad, što ga čini još više zabave. Osoba koja prima te 25-gigabajt kupon kod - što je daleko uvjerljiviji od kasne Sada dana, možda - je onaj koji sjedi na vrhu sjedala, ispod kojeg se nalazi da je kupon. Sada možete pogledati ispod Vaš sjedala. [Video reprodukciju] -Jedan, dva, tri. [SCREAMING] -Dobivate auto! Možete dobiti auto! DAVID Malan: Vidjet ćemo što je u srijedu. -Dobivate auto! Možete dobiti auto! Možete dobiti auto! Možete dobiti auto! Možete dobiti auto! DAVID Malan: Balkon ljudi, dolaze ovdje dolje na prednji, gdje smo dodataka. -Svatko dobiva auto! Svatko dobiva auto! [END video reprodukciju] Narator: Na sljedećem CS50 - ZVUČNI 5: O, moj bože bože bože bože bože bože bože bože bože bože - [UKELELE PLAYS]