[Glazbom] PROFESOR: U redu. To je CS50 i to je kraj tjedna tri. Tako smo danas ovdje, a ne u Sanders Kazalište, umjesto u Weidner knjižnici. Unutar kojih je studio poznat kao Hauser Studio, ili ćemo reći Studio H, ili će smo say-- ako ste uživali tu šalu, to je zapravo iz kolega, Mark, on-line, koji je sugerirao koliko putem Twittera. Sada ono što je cool o biti ovdje u studiju je da sam okružena njima zeleno Zidovi, zeleni zaslon ili chroma, da se tako izrazim, što znači da je CS50 produkcijski tim, bez znanja mi upravo sada, mogao biti stavljajući me najviše bilo gdje u svijetu, za bolje ili na gore. Sada ono što je pred nama, problem postaviti dva je u vašim rukama za ovaj tjedan, ali s problemom postaviti tri Ovog će tjedna, ćete biti izazvan s tzv igra 15, stara stranka milost da možda podsjetiti prima kao dijete koje ima cijela hrpa brojeva koji mogu slajd gore, dolje, lijevo i desno, a postoji jedan jaz unutar slagalice, u koju zapravo može kliziti one slagalice. Na kraju ćete dobiti ovo zagonetka u nekom polu slučajnim redoslijedom, a cilj je da se to riješiti, od vrha do dna, lijeva na desno, od jednog pa sve do preko 15 godina. Nažalost, provedba ćete imati pri ruci će biti softvera temelji, a ne fizički. Vi ste zapravo morati napisati kod s kojim student ili korisnik može igrati igru ​​15. A u stvari, u hakera izdanje igre od 15 godina, ćete biti izazov za provedbu, ne samo igranje ove stare škole igra, nego rješavanje nje, provedbu boga mod, da tako kažemo, da je zapravo rješava zagonetku za čovjeka, pružajući im savjet, Nakon savjet, nakon naznaka. Dakle, više o tome sljedeći tjedan. No, to je ono što se nalazi ispred. Za sada podsjećaju da je ranije ovog tjedna imali smo tu Cliffhanger, ako hoćete, pri čemu najbolje radimo sortiranje Mudar je gornja granica za velike o n kvadrat. Drugim riječima, mjehurić sortirati, izbor vrsta, umetanje vrsta, sve njih, a razlikuju u njihovoj provedbi, devolved u n na kvadrat trčanje Vrijeme u vrlo najgorem slučaju. I općenito pretpostaviti da vrlo najgori slučaj za sortiranje jedan je da vaši inputi potpuno unatrag. I doista, to je dosta koraka provesti svaki od tih algoritama. Sada je na samom kraju klase Podsjetimo, usporedili smo mjehurić vrsta protiv selekcije vrste protiv jednog drugog koje se zove pisma vrsta u to vrijeme, i predlažem da je uzimanje Prednost lekcije iz tjedna nula, podijeli pa vladaj. I nekako postizanje neke vrste logaritamska vrijeme rada u konačnici, umjesto nečega to je čisto kvadratna. I to nije sasvim logaritamska, to je malo više od toga. Ali, ako se sjećate iz razreda, bilo je mnogo, mnogo brže. Idemo pogledati gdje smo stali. Bubble sort odnosu izbor vrsta u odnosu na spajanje vrste. Sada svi oni prikazuju u teorije, istovremeno. CPU radi na istoj brzini. Ali možete osjetiti kako se to dosadno je vrlo brzo će postati, i koliko brzo, kada smo se uvelo malo algoritama tjedan Zero-a, možemo ubrzati. Dakle, oznaka vrsta izgleda nevjerojatna. Kako to možemo iskoristiti, kako bi sortirati brojeve brže. Pa neka je misliti leđa na sastojak koji se imali još u tjednu nula, onaj u potrazi za nekoga u telefonskom imeniku, i podsjetiti da je pseudokod koje smo predložili, putem koje možemo naći netko poput Mike Smith, Pogledao malo nešto ovako. Sada pogledajte osobito u liniji 7 i 8 i 10 i 11, koji potiču tu petlju, pri čemu smo zadržao povratak na liniji 3 opet, i opet, i opet. Ali ispada da možemo vidjeti Ovaj algoritam, ovdje u pseudokod, malo više holistički. U stvari, ono što tražim na ovdje na zaslonu, je algoritam za traženje Mike Smith među nekim skupom stranica. I doista, možemo pojednostaviti ovaj algoritam u tim linijama 7 i 8, i 10 i 11 na samo reći ovo, što sam ovdje predstavljen u žuto. Drugim riječima, ako Mike Smith je ranije u knjizi ne trebamo odrediti korak po korak kako sada ići ga naći. Nemamo odrediti vratiti na liniji 3, zašto ne bismo samo umjesto toga, recimo, općenitije, tražiti Mikeom u lijeva polovica knjige. Isto tako, ako je Mike zapravo kasnije u knjizi, zašto ne bismo jednostavno citirati citat pretragu za Mike u desnoj polovici knjige. Drugim riječima, zašto ne bismo jednostavno vrsta čamac za sebe kaže, tražiti Mike u ovom podskup knjige, i prepustiti našim postojećim Algoritam nam reći kako tražiti Mikea u da lijeva polovica knjige. Drugim riječima, naš algoritam radi li je telefonski knjiga ove debljine, to Debljina, ili bilo debljine god. Tako možemo rekurzivno definirati ovaj algoritam. Drugim riječima, na Zaslon ovdje je algoritam za traženje Mike Smith među stranicama telefonskog imenika. Dakle, u skladu 7 i 10, neka je samo reći upravo to. I koristim taj termin trenutak Prije, i doista, rekurzija je buzzword za sada, i to je taj proces radiš nešto ciklički nekako pomoću kôd koji već imate, a nazvavši ga opet, i opet, i opet. Sada to će biti važno da mi je nekako dno van, a ne radi to beskonačno dugo. Inače idemo na ima uistinu beskonačan petlju. Ali neka je vidjeti ako mi može posuditi tu ideju od rekurzije, opet radi nešto i opet i opet, riješiti sortiranje problema putem spajanja sortiranje, sve učinkovitije. Tako sam vam dati spojiti vrsta. Idemo pogledati. Dakle, ovdje je pseudokod, s koje smo mogli provesti razvrstavanje, koristeći ovaj algoritam se zove spajanje vrsta. I to je jednostavno to. Na ulaz n elemenata, Drugim riječima, ako ste s obzirom n elemenata i brojeve i slova ili što god da je ulaz, ako ste s obzirom n elemenata, ako n je manje od 2, jednostavno vratiti. Pravo? Jer, ako je n manji od 2, koje znači da moj popis elemenata bilo je veličine 0 ili 1, i u obje te sitnice, popis je već riješeno. Ako ne postoji popis, to je riješeno. A ako postoji popis duljine 1, to je očito razvrstani. Dakle, algoritam treba samo stvarno učiniti nešto zanimljivo, ako imamo dva ili više Elementi dao nama. Pa pogledajmo magiju tada. Inače sortirati lijevu polovicu elemenata, zatim poredati desnu polovicu elemenata, zatim spojiti sortirani polovice. A što je vrsta uma savijanje ovdje je da ja stvarno ne Čini se da su ti rekao ništa samo još, zar ne? Sve što sam rekao je, s obzirom na popis n elemenata, sortiranje lijevu polovicu, zatim pravo na pola, a zatim spojiti sortirani polovice, ali gdje je stvarna tajna umak? Gdje je algoritam? Pa ispada da ta dva reda Prvo, vrsta napustio pola elemenata, i vrsta pravu pola elemenata, su rekurzivni pozivi, da se tako izrazim. Uostalom, na ovaj točka u vremenu, moram algoritam s kojim se sortirati cijela hrpa elemenata? Da. To je upravo ovdje. To je upravo ovdje na zaslonu i tako da ja mogu koristiti taj isti skup koraka sortirati lijevu polovicu, što mogu pravo na pola. I doista, opet, i opet. Dakle, na neki način, i mi uskoro ćete vidjeti, magiju spajanje vrste koji je ugrađen u vrlo konačna linija, spajanjem razvrstanih polovice. A to se čini prilično intuitivno. Uzmeš dvije polovice, a ti, nekako spojiti ih zajedno, pa ćemo vidjeti konkretno u ovom trenutku. No, to je kompletan algoritam. I da vidimo točno zašto. Pa pretpostavimo da smo dali to ista osam elemenata ovdje na ekranu, jedan kroz osam, ali su u naizgled nasumičnim redoslijedom. A cilj je pri ruci sortirati tih elemenata. Pa kako mogu ići o radi korištenja, opet, spajanje vrsta, kao i po ovom pseudokod? I opet, okorio ovo vaš um, samo na trenutak. Prvi slučaj je lijepa trivijalna, ako je manje od 2, Samo se vrati, nema posla koji treba obaviti. Pa stvarno postoji samo tri koraci stvarno treba imati na umu. Opet, i opet, ja sam će htjeti imati sortirati lijevu polovicu, sortirati desnu polovicu, a onda nakon njihove dvije polovice su razvrstani, Želim ih spojiti zajedno u jednu sortiranog popisa. Pa imajte to na umu. Dakle ovdje je izvorni popis. Idemo tretirati kao niz, kao što smo počeli u tjedan dva, što je granični blok memorije. U tom slučaju, koja sadrži osam brojevi, natrag na leđa na leđa. I neka sada vrijede pisma vrsta. Tako sam prvi put želite sortirati lijeva polovica tog popisa, i neka je, dakle, usredotočiti na 4, 8, 6, i 2. Sada kako mogu ići o sortiranje popisa veličine 4? Pa moram sada razmotriti sortiranje lijevo od lijeve polovine. Opet, neka je natrag samo na trenutak. Ako pseudokod je to, i ja sam dao osam elemenata, 8 je očito veći od ili jednak 2. Tako je s prvi slučaj ne primjenjuje. Dakle, za sortiranje osam elemenata, sam prvi put sortirati lijevu polovicu elemenata, onda sam sortirati desnu polovicu, onda sam spojiti dvije polovice razvrstane, svaki veličine 4. U REDU. Ali, ako ste upravo mi je rekao, sortiranje lijeva polovica, koja je sada veličine 4, kako mogu sortirati utakmice polovicu? Pa, ako imam ulaz četiri elementa, Prvi put sam sortirati lijevu dva, onda pravo dva, i onda sam ih spojiti zajedno. Pa opet, to postaje malo od uma savijanje igra ovdje zato vas, vrsta, moraju sjetiti gdje ste u priči, ali na kraju dana, daje bilo koji broj elemenata, prvo se želite sortiranje lijeva polovica, onda pravo na pola, a zatim ih spojiti zajedno. Počnimo učiniti upravo to. Evo ulaz osam elemenata. Sada smo u potrazi na lijevoj polovici ovdje. Kako sortirati četiri elementa? Pa sam prvo sortirati lijevoj polovici. Sada kako mogu sortirati utakmice polovicu? Pa sam dao dva elementa. Tako ćemo razvrstati ova dva elementa. 2 je veći od ili jednak 2, naravno. Tako da prvi slučaj ne primjenjuje. Tako sam sada morati sortirati lijevu polovica tih dvaju elemenata. Lijeva polovica, naravno, samo 4. Pa kako mogu sortirati popis jednog elementa? Pa sad, da je posebna baza slučaj do vrha, da tako kažem, vrijedi. 1 manji od 2, i moj Popis je uistinu veličine 1. Dakle, samo sam se vratiti. Ja ne radim ništa. I doista, pogledajte što sam učinjeno, 4 već riješeno. Kao što sam već sam djelomično uspješna ovdje. Sada se to čini vrsta glupo zahtjevu, ali to je istina. 4 je popis veličine 1. Već je riješeno. To je lijeva polovica. Sada sam sortirati desnu polovicu. Moj ulaz je jedan element, 8 Slično tome, već riješeno. Glupo je, također, ali opet, to osnovno načelo će nam omogućiti da izgrade sada na vrhu ove uspješno. 4 razvrstani, 8. razvrstani sada što je to posljednji korak? Tako je treći i završni korak, bilo put ste sortiranja popisa, podsjetimo, je spojiti dvije polovice, lijeva i desna. Tako ćemo učiniti upravo to. Moja lijeva polovica je, naravno, 4. Moja desna polovica 8. Tako ćemo to učiniti. Prvo ću izdvojiti neke dodatne memorije, da ću ovdje predstavljam, samo kao sekundarni polje, to je dovoljno velika da stane to. Ali možete zamisliti širi da pravokutnik cijela duljina, ako nam je potrebno više kasnije. Kako sam se 4 i 8, i spajanje te dvije liste veličine 1 zajedno? Ovdje, također, vrlo jednostavna. 4. na prvom mjestu, onda dolazi 8. Jer ako želim sortiranje lijeva polovica, onda pravo na pola, a zatim spojiti te dvije polovice zajedno, u sortiranog bi, 4. na prvom mjestu, onda dolazi 8. Zato mi se čini da se napreduje, čak iako nisam učinio nikakav stvarni rad. Ali zapamtite gdje smo u priči. Mi smo izvorno je osam elemenata. Razvrstani smo lijevu polovicu, što je 4. Onda smo razvrstani lijevu polovicu lijeve polovice, što je 2. I ovdje mi ići. Mi smo učinili s tim korakom. Dakle, ako smo razvrstani ostavi pola 2, sada smo moraju sortirati pravu polovicu 2. Dakle, pravo na pola 2 je ove dvije vrijednosti ovdje, 6 i 2. Tako ćemo sada uzeti ulaz veličine 2, i sortirati lijevu polovicu, a zatim pravo na pola, a onda ih spojiti zajedno. Pa kako mogu sortirati popis veličini 1, koji sadrži samo broj 6? Ja sam već učinio. Taj popis veličine 1 je riješeno. Kako sortirati drugi popis Veličina 1, tzv desna polovica. Pa to je, također, već je riješeno. Broj 2 je sama. Tako sada imam dvije polovice, lijevo i Dobro, moram ih spojiti zajedno. Dopustite mi da si dati neki dodatni prostor. I staviti 2 tamo, zatim 6 tamo, čime sortiranje taj popis, lijevo i desno, i spajanje zajedno, u konačnici. Dakle, ja sam u malo boljoj formi. Nisam učinio, jer je očito 4, 8, 2, 6 nije konačan poredak koji želim. Ali ja sada imam dva popisa veličine 2, da su oba, odnosno, bili razvrstani. Pa sad, ako natrag u vaš um je oko, gdje je taj nas ostaviti? Počeo sam s osam elemenata, onda sam whittled ga na lijevu polovicu 4, zatim lijevu polovicu od 2, i onda pravo pola 2, Sam završio, dakle, sortiranje lijevi pola 2, a pravo pola 2, tako što je treći i posljednji korak ovdje? Moram spojiti zajedno dvije liste veličine 2. Tako ćemo ići naprijed. A na zaslonu ovdje, dati mi neke dodatne memorije, iako tehnički, primijetiti da imam dobio hrpu praznog prostora do vrha tamo. Ako želim biti posebno učinkovit prostor mudar, Samo sam mogao početi kreće elemente natrag i naprijed, gore i dolje. Ali samo za vizualne jasnoće, Idem ga staviti dolje, držati stvari lijepo i čisto. Dakle imam dva popisa veličine 2. Prvi popis je 4 i 8. Drugi popis je 2 i 6. Idemo spojiti one zajedno sortiranog bi. 2, naravno, na prvom mjestu, zatim 4, zatim 6, a zatim 8. I sada mi se čini da je dobivanje negdje zanimljiv. Sada sam razvrstani polovica popis, i slučajno, to je sve čak brojeve, ali to je, doista, samo slučajnost. I sada razvrstani lijevu polovicu, tako da je 2, 4, 6 i 8. Ništa je iz reda. To se osjeća kao napredak. Sada se osjeća kao da sam Razgovarali zauvijek sada, pa što ostaje da se vidi je li to Algoritam je, doista, učinkovitiji. Ali ćemo kroz super metodično. Računalo, dakako, Učinit će to tako. Pa gdje smo mi? Počeli smo s osam elemenata. Ja razvrstani lijevu polovicu 4. Čini mi se da se radi s tim. Tako sada sljedeći korak je sortirati pravu polovinu 4. I to je dio možemo ići kroz malo više brzo, iako ste dobrodošli natrag ili pauziranja, samo mislim kroz njega na vlastitim tempom, ali ono smo sada je prilika da se napraviti isti algoritam na četiri različiti brojevi. Tako ćemo ići naprijed, i usredotočiti se na pravo na pola, koji smo ovdje. Lijeva polovica da pravo na pola, a sada lijeva polovica lijevo polovica tog desne polovice, i kako mogu sortirati popis veličini 1 sadrži samo broj 1? Već je učinjeno. Kako sam učiniti isto za popis veličine 1 sadrži samo 7? Već je učinjeno. Korak tri za Vezni onda se spojiti ova dva elementa u novi popis veličine 2, 1 i 7. Ne čini se da su učinili sve toliko zanimljiv rad. Idemo vidjeti što će se dogoditi sljedeći. Upravo sam razvrstani lijevu polovicu Pravo pola mog izvornog unosa. Sada ćemo razvrstati pravo pola, koji sadrži 5 i 3. Idemo ponovno pogledate lijevo pola, razvrstani, desna polovica, razvrstani, i spojiti to dvoje zajedno, u neki dodatni prostor, 3 na prvom mjestu, onda dolazi 5. I tako sada smo razvrstani lijeva polovica desne polovice originalnog problema, i pravo polovice desne polovice originalnog problema. Što je treći i posljednji korak? Pa spojiti te dvije polovice zajedno. Zato mi dopustite da ja osobno dobiti neki dodatni prostor, ali, opet, sam može biti da koristite rezervni prostor do vrha. Ali ćemo zadržati to jednostavno vizualno. Dopustite mi stopiti sada 1, a zatim 3, a zatim 5, a zatim 7. Time ostavljajući me sada s desna polovica originalnog problema koji savršeno je riješeno. Dakle, ono što ostaje? Osjećam se kao da sam zadržati rekavši iste stvari opet, i opet, ali to je reflektirajuća od Činjenica da smo pomoću rekurzija. Proces korištenjem Algoritam opet, i opet, na manjim podskupova izvorni problem. Tako sam sada imaju lijeva razvrstani polovica originalnog problema. Imam pravo sortirani pol originalnog problema. Što je treći i završni korak? Oh, to je spajanje. Tako ćemo učiniti. Idemo izdvojiti neke dodatne memorije, ali Bože moj, što staviti ga bilo gdje sada. Imamo toliko prostora na raspolaganju nama, ali ćemo ga zadržati jednostavan. Umjesto ide natrag i naprijed s našim originalnim memorije, Ajmo to učiniti vizualno ovdje u nastavku, dovršiti spajanjem lijeva polovica i pravo na pola. Dakle spajanjem, što trebam učiniti? Želim uzeti elemente u redu. Dakle, gleda na lijevoj polovici, Vidim prvi broj 2. Gledam na desnoj polovici, Vidim prvi broj 1, tako očito što Broj želim iščupati, i staviti prvi u mom konačni popis? Naravno, 1. Sada želim pitati to isto pitanje. Na lijevoj polovici, sam ipak je dobio broj 2. Na desnoj polovici, Imam broj 3. Koji želim odabrati? Naravno, broj 2 Sada obavijest kandidatima su 4 na lijevo, 3 na desnoj strani. Idemo, naravno, izabrati 3. Sada kandidati su 4 na lijeva, 5 na desnoj strani. Mi, naravno, izabrati 4. 6 na lijevoj strani, 5 na desnoj strani. Mi, naravno, izaberite 5. 6 na lijevoj strani, 7. na desnoj strani. Mi izabrati 6, a onda smo izaberite 7, a zatim biramo 8. Voila. Tako veliki broj riječi kasnije smo su razvrstani ovaj popis osam elemenata u popisu jedan kroz osam, da je povećanje na svakom koraku, ali koliko je vremena nas odvesti na to. Pa imam namjerno položio stvari iz slikovno ovdje, tako da možemo vrsta vidjeti ili cijeniti podjelu u osvajanju koji je bio događa. Doista, ako se osvrnem na svjetlu, Ostavio sam sve ove iscrtanih linija u držačima mjestu, možete, vrsta, vidi, u obrnutom redoslijedu, ako vrsta osvrnuti na povijest je sada, moj originalni popis je, naravno, veličine 8. A onda je prije, bio sam bave dva lista veličine 4, a onda četiri liste veličine 2, a zatim osam popisi veličine 1. Pa što to, vrsta, podsjetiti vas na? Pa, zapravo, bilo koji od algoritmi smo pogledao do sada gdje smo podijeli i podijelite i podjela, zadržati vlasništvo stvari opet, i opet, rezultira u ovoj općoj ideji. I tako postoji nešto logaritamska događa ovdje. I to nije sasvim dnevnik n, ali tu je logaritamska komponenta na ono što smo upravo učinili. Sada ćemo razmotriti kako da se zapravo jest. Dakle, prijavite n, ponovno je velik vrijeme rada, kad smo radili nešto slično binarno pretraživanje, kao što smo sada ga zovu, podjela pa vladaj strategija putem koje smo našli Mike Smith. Sada tehnički. To je dnevnik baza 2 n, čak iako u većini math klase, 10 je obično točka koju pretpostavljamo. No, računalni znanstvenici gotovo uvijek razmišljati i razgovarati u smislu bazi 2, pa smo uglavnom samo reći dnevnik N, umjesto log baze 2 n, ali oni su upravo jedan te Isto u svijetu računala znanost, a kao usput, postoji konstantan faktor Razlika između ta dva, tako da je Ionako sporan, za više formalnih razloga. No, za sada, ono što mi je stalo o je ovaj primjer. Dakle, nemojmo se pokazati primjerom, ali u najmanje koristiti primjer brojeva pri ruci kao provjera razum, ako hoćete. Tako je prije formula je dnevnik baze 2 n, ali ono što je n u ovom slučaju. Imao sam n izvorne brojeve, ili 8 od izvornog broja posebno. Sada je bio malo dok je, ali ja sam prilično je li zapisnik baza 2 vrijednosti 8 je 3, i doista, što je lijepo o kako je da 3 je upravo broj puta koje možete podijeliti popis duljine 8 opet, i opet, i opet, sve dok ste napustili s popisima samo veličine 1. Pravo? 8 ide na 4, ide na 2, ide do 1, a to je odražava upravo to Slika imali smo samo trenutak prije. Dakle, malo razum provjeriti gdje logaritam zapravo uključeni. Pa sad, što drugo je uključen ovdje? n. Dakle, primijetite da je svaki Vrijeme sam podijeliti popis, iako u obrnutom redoslijedu u povijesti ovdje, ja još uvijek radio n stvari. To spajanjem korak zahtijeva da Dodirnem svaki od brojeva, kako bi ga gurnite u njegov odgovarajuće mjesto. Dakle, iako je visina ovog Dijagram je veličina log n n ili 3, posebno, drugim riječima, Ja sam tri divizije ovdje. Koliko posla sam učinio vodoravno uz ovaj grafikonu svaki put? Pa, ja sam n koraka raditi, jer ako imam dobio četiri elementa i četiri elementa, i moram ih spojiti zajedno. Moram proći kroz ove četiri i to četiri, konačnici ih spojiti natrag u osam elemenata. Ako s druge strane imam osam prstiju ovdje, što ja ne, a osam fingers-- sorry-- Ako sam dobio četiri prsta ovdje, što mi je činiti, četiri prsta ovdje, što mi je činiti, zatim da je ista Primjer kao i prije, ako mi je činiti ima osam prstiju iako u Ukupno, koji se mogu, vrsta, učiniti. Ja točno možete učiniti ovdje, onda ja mogu sigurno spojiti sve te liste veličine 1 zajedno. Ali ja sigurno morati gledati na svakom elementu točno jednom. Tako je visina tog procesa je zapisnik nje, širina tog procesa, da se tako izrazim, n, tako da ono što čini da, u konačnici, je trčanje vrijeme veličine n puta prijavite nje. Drugim riječima, mi podijeljeni popis, zapisnik n puta, ali svaki put smo to učinili, imali smo dotaknuti svaki od elemenata kako bi ih spojiti svi zajedno, što bio je N korak, tako da imamo n puta prijaviti nje, ili kao računalni znanstvenik će reći, asimptotski, koji će biti velika riječ opisati gornja vezan na trčanje vremena, smo prikazivati ​​u velikom o log n vrijeme, da se tako izrazim. A ovo je značajan, jer je sjetiti što su trčanje puta s mjehurića vrsta i odabir sortiranje i umetanje sortiranje, pa čak i nekoliko drugih koje postoje, n na kvadrat bio gdje smo bili na. A možete, vrsta, vidjeti ovdje. Ako je n kvadrat očito n puta nje, ali ovdje imamo n puta prijaviti nje, a mi već znamo iz tjedna nula, da je zapisnik nje je logaritamska, je bolje nego nešto linearno. Uostalom, prisjetiti sliku sa crveno i žuto i zelene crte koje zagrabiše je zelena logaritamska linija bila znatno niža. I zato, mnogo bolje i brže od ravne žute i crvene linije, n puta prijavite nje je, doista, bolje od n puta n ili n na kvadrat. Dakle, izgleda da imamo identificirati algoritam spajanje vrsta koja radi u mnogo brže vrijeme, i doista, Zato, ranije ovog tjedna, kada je Vidjeli smo da je natjecanje između mjehura sortiranje, odabir vrsta, i spajanje vrsta, spajanje vrsta stvarno, stvarno pobijedio. I doista, nismo ni čekati za mjehur vrsta i odabir vrste Završiti. Sada ćemo uzeti jednu drugu sredinu u ovom, od nešto više formalno perspektive, samo u slučaj, to bolje rezonira nego da više razine rasprave. Dakle ovdje je algoritam ponovno. Idemo se pitamo, što je trčanje vrijeme je to algoritmima različite korake? Budimo podijeliti u prvi slučaj i drugi slučaj. IF i drugo u slučaju da, Ako je n manji od 2, samo se vrati. Osjećaj konstantne vrijeme. To je, vrsta, kao i dva koraka, Ako je n manji od 2, a zatim se vratiti. No, kao što smo rekli u ponedjeljak, vremenska konstanta, ili velika o 1, mogu biti dva koraka, tri koraka, čak 1.000 koraka. Ono što je važno je da je konstantan broj koraka. Dakle žuti istaknuo pseudokod Ovdje radi u, mi ćemo ga nazvati, vremenska konstanta. Tako više formalno i idemo to-- ovo biti će u kojoj mjeri smo formalizirati to pravo now-- T n, Vrijeme rada problema koji traje n somethings kao ulaz, jednako velika o jedan, Ako je n manji od 2. Dakle, to je uvjetno na to. Dakle, da bude jasno, ako je n manji od 2, imamo vrlo kratak popis, a zatim vrijeme rada, T n, gdje je n 1 ili 0, u ovom vrlo konkretnom slučaju, to samo će biti konstantna vrijeme. To se događa da se jedan korak, dva koraka, bilo što. To je fiksni broj koraka. Tako je sočna dio mora sigurno biti u Drugi slučaj u pseudokod. JOŠ slučaj. Sortiraj lijeva polovica elemenata, sortiranje pravo pola elemenata, spajanja razvrstanih polovice. Koliko je svaki od tih koraka poduzeti? Pa, ako je pokrenut Vrijeme za sortiranje n elemenata je, nazovimo ga vrlo općenito, T n, zatim sortiranje lijevu polovina elemenata je vrsta, kao što je rekao, T n podijeljena 2, i slično sortiranja desnu polovicu elemenata je vrsta, kao što je rekao, T n podijeljen 2, a potom spajanjem sortirani polovice. Pa, ako sam dobio neke broj elemenata ovdje, kao i četiri, i neki broj elemenata ovdje, kao i četiri, i moram spojiti svaku od ove četiri u, a svaki od njih četiri u, jedan nakon druge, tako da se konačnici Imam osam elemenata. To se osjeća kao da je veliki o od n koraka? Ako imam n prste i svaki od ih mora spojiti u mjestu, to je kao da još n koraka. Dakle, istina formulaically, možemo izraziti, doduše malo scarily na prvi pogled, ali to je nešto koji bilježi upravo tu logiku. Računanje vremena, T n, ako je N je veća od ili jednaka 2. U tom slučaju, na drugome slučaju, T n podijeljen 2, plus T od N podijeljen 2, uz veliki o n, neki linearna broj koraka, možda točno n, možda 2 puta nje, ali to je otprilike, redoslijed n. Tako da je, također, kako možemo izraziti formulaically. Sada ne bi znao to, osim ako ste ga snimio u svom umu, ili ga potražiti u natrag udžbenika, koji možda malo varati list na kraju, ali to je, doista, će daju nam veliki o n log n, jer ponavljanje da vidite ovdje na zaslonu, ako stvarno to učinio prema van, beskonačan broj primjera, ili si to učinio formulaically, što bi vidjeti da je to, jer ove formule Sam je rekurzivna, s t nje zbog nečega na desnoj strani, a t n više na lijevoj strani, to može zapravo se izrazio, u konačnici, kao velika go n log n. Ako nije uvjeren, da je to u redu za sada, samo se na vjeri, da je to, zapravo, što je to povratak vodi, ali to je samo nešto više od matematički pristup u potrazi u trajanju od pisma koje vrste na temelju svojih pseudokod sama. Sada ćemo uzeti malo odušak od svega toga, i uzeti pogledati određeni bivši senator, koji je Možda izgleda malo poznato, koji je sjeo s Googleovim Ericom Schmidt, prije nekog vremena, za intervju na pozornici, ispred cijela hrpa ljudi, govori o kraju tema, to je prilično sada poznato. Idemo pogledati. Eric Schmidt: Sada senator, ti si ovdje na Googleu, i volim misliti na Predsjedništvo kao intervju za posao. Sada je teško dobiti posao kao predsjednika. Predsjednik Obama: Tako je. Eric Schmidt: A ti si učiniti [nečujan] sada. Također je teško dobiti posao u Googleu. Predsjednik Obama: Tako je. Eric Schmidt: Imamo pitanja, i tražimo naši kandidati pitanja, i to je jedan od Larry Schwimmer. Predsjednik Obama: U redu. Eric Schmidt: Što? Vi mislite Šalim? To je upravo ovdje. Koji je najučinkovitiji način za sortirati milijun 32 bitni prirodni brojevi? Predsjednik Obama: Well-- Eric Schmidt: Ponekad, možda Žao mi je, maybe-- Predsjednik Obama: Ne, ne, ne, ne, ne, ja think-- Eric Schmidt: To nije it-- Predsjednik Obama: ja mislim, mislim mjehurić sortirati bi pogrešan način da ide. Eric Schmidt: Hajde. Tko ga je to rekao? U REDU. Nisam računalo znanost on-- Predsjednik Obama: Imamo dobio naše špijune tamo. PROFESOR: U redu. Ostavimo iza nas sada teorijski svijet algoritama u asimptotske analize njihove, i vratiti se na nekim temama iz tjedna nula i jedan, i početi ukloniti neke trening kotačima, ako hoćete. Tako da stvarno razumiju u konačnici od temelja, što je događa ispod haube, kada vas napisati, sastaviti, i izvršavanje programa. Podsjetimo posebno, da je to Prvi C programa smo pogledali, kanonski, jednostavan program sorti, relativno govoreći, u kojoj, ispisuje, Hello World. I podsjetiti da je sam rekao, proces da izvorni kod prolazi kroz je upravo to. Možete uzeti izvorni kod, prolaze to kroz prevodilac, kao što su jeka, i kako dolazi objektnog koda, koji može izgledati ovako, nula i jedinica da računalo CPU, središnja procesorska jedinica ili mozga, konačnici razumije. Ispada da to je malo je pojednostavljivanje, da smo sada u Položaj zafrkavati osim razumjeti što se stvarno bio događa ispod haube svaki put kada pokrenete Jeka, ili općenitije, svaki put kad bi program, pomoću Napravite CF 50 IDE. Konkretno, takve stvari ovaj prvi je generiran, kada ste prvi sastaviti svoj program. Drugim riječima, kada se ti uzmite izvorni kod i sastaviti ga, što je prvi se reproduciraju po zveket je nešto poznato kao montaže kod. A u stvari, to izgleda upravo ovako. Ran sam naredbu na naredbenog retka ranije. Zveket DASH Capital s hello.c, a to stvorio datoteku za mene zove hello.s, unutar kojih su se upravo ti sadržaji, i malo više iznad i malo više u nastavku, ali sam stavio juiciest informacija ovdje na zaslonu. I ako malo bolje pogledate, vidjet ćete barem nekoliko poznatih riječi. Imamo glavni na vrhu. Mi smo printf dolje u sredini. I mi također imaju Hello World backslash nje u navodnike dolje. A sve ostalo ovdje je uputa vrlo niskoj razini da računalo CPU razumije. CPU upute koje se kreću memorije oko, da opterećenje žice iz memorije, i na kraju, za ispis stvari na zaslonu. Sada što se događa, iako nakon ovaj zbor broj se generira? Na kraju, vi, doista, dalje generirati objektnog koda. Ali koraci koje su stvarno događa ispod haube izgleda malo više kao što je ovaj. Izvorni kod postaje skupština koda, koji tada postaje predmet broj, a operativna riječi ovdje su da, kada sastaviti svoj izvorni kod, kako dolazi sklop kod, a zatim kad skupite svoju montaže kod, kako dolazi objektnog koda. Sada zveket je super sofisticiran, kao puno prevodiocima, i to sve od tih koraka zajedno, i to ne mora nužno Izlaz bilo intermedijer datoteke koje možete čak i vidjeti. To samo sastavlja stvari, koja je opći pojam koji opisuje cijeli taj proces. Ali ako stvarno želite Posebno se, ima puno više događa tamo. Ali neka se također uzeti u obzir da čak i sada da super jednostavan program, hello.c, naziva funkcija. To se zove printf. Ali nisam pisati printf, doista, koji dolazi s c, da se tako izrazim. To je funkcija Sjetite se da je proglasio je u standardnoj io.h, koji je zaglavlje datoteke, što je tema ćemo zapravo zaroniti u dublje prije dugo. No, zaglavlje datoteke obično popraćena po koda datoteke, izvorni kod datoteke, tako slično postoji standardna io.h. Negdje prije, netko, ili neciji, napisao datoteka se zove standardni io.c u koji su stvarni definicije, ili implementacije printf, i grozdova suhog druge funkcije, zapravo napisao. Pa s obzirom da je, ako uzmemo u obzir potrebe Ovdje na lijevoj strani, hello.c, da kada sastavio, daje nam hello.s, čak i ako Zveket ne smetaju uštedu na mjestu možemo ga vidjeti, i da je Skupština kod dobiva sklopljeni u hello.o, koji je, doista, zadani naziv dao kad god sastaviti izvora kod u objektnom kodu, ali nisu sasvim spremni da ga izvrši, ali, jer još jedan korak mora dogoditi, te ima se događa u posljednjih nekoliko tjedana, možda i bez znanja vama. Naime negdje u CS50 IDE, i to, također, će biti malo od pojednostavljivanje na trenutak, postoji, ili je bio davno, datoteka se zove standardni io.c, da je netko sastavio u Standardni io.s ili ekvivalent, da je netko tada okupio u standardnom io.o, ili ispada u malo drugačiji datoteka format koji može imati drugačiji ekstenzija datoteke uopce, ali u teoriji i konceptualno, točno one korake morao dogoditi u nekom obliku. Što će reći, da je sada kad pišem programa, hello.c, koji samo govori, halo svijet, i ja sam koristeći tuđe šifru kao printf, koji je nekada na stvaranju Vrijeme u datoteci pod nazivom standardni io.c, onda nekako moram uzeti moj Šifra objekta, moji nula i jedinica, i te osobe predmet kod, ili nula i jedinica, i nekako ih povezati zajedno u jedan konačni datoteku, pod nazivom Pozdrav, da ima sve nula i one iz mog glavne funkcije, i sve nule i one za printf. I doista, da je prošle proces zove, povezujući svoj objektnog koda. Od kojih je izlaz je izvršna datoteka. Tako je u pravednosti, u kraju dana, ništa se promijenilo od tjedan jednom, kad smo prvi počeo sastavljanju programa. Doista, sve to je događa ispod haube, ali sada smo u poziciji Gdje možemo zapravo zafrkavati osim ove različite korake. I doista, na kraju dana, još smo otišao s nula i jedinica, koje je zapravo velika prikazali sada na drugi sposobnosti C, kako nismo imali utjecati najvjerojatnije do danas, poznat kao bitovni operatori. Drugim riječima, do sada, bilo kada imamo bavila podataka u C ili varijabli u C, imali smo stvari kao što su znakova i pluta i ins i čezne i parovima i slično, ali svi oni su najmanje osam bitova. Nikada nismo još bili u mogućnosti manipulirati pojedinačne bitove, iako pojedinog malo, mi Znate, može predstavljati 0 i 1. Sada ispada da je u C, što možete dobiti pristup pojedinim bitova, ako znate sintaksu, s kojom se dobiti na njih. Tako ćemo pogledati na bitovima operatora. Dakle ovdje na slici su neke simbole koji smo, vrsta, vrsta, vidjela. Vidim ampersand, vertikalni bar, i neki drugi, kao i, i podsjetiti da ampersand ampersand je nešto što smo vidjeli prije. Logično i operatora, gdje imate Njih dvoje zajedno, ili logički ILI Operator, gdje vas imaju dvije okomite pruge. Bitovni operatori, koji ćemo vidi djeluju na bitova pojedinačno, samo koristiti jedan ampersand, A jedna okomita traka je znak za umetanje simbola dolazi sljedeći, malo tilda, a zatim otišao nosač napustio nosač, ili Pravo nosač pravo nosač. Svaki od njih ima različita značenja. U stvari, neka je pogledati. Idemo stara škola i danas, i uporaba zaslon osjetljiv na dodir od prošle, poznat kao bijela ploča. I to bijela ploča će nam omogućiti izraziti neke prilično jednostavne simbole, odnosno neke prilično jednostavne formule, kako možemo onda u konačnici poluge, kako bi pristupiti individualno bitova unutar programa C. Drugim riječima, učinimo to. Neka prvi razgovor za Trenutak oko znakom, što je bitovni AND operator. Drugim riječima, to je operator koji omogućuje ja imati varijablu lijevu tipično, varijabilna i desni, ili pojedinačna vrijednost, da ako mi i ih zajedno, daje mi konačni rezultat. Pa što mislim? Ako se u programu, imate varijablu koji sprema jedan od tih vrijednosti, ili ćemo ga zadržati jednostavan i jednostavno napisati nula i jedinica pojedinačno, evo kako operator znak za struju radi. 0 0 znak za struju će jednaka 0. Sad zašto je to tako? To je vrlo slično Boolean izrazi, da smo do sada razgovarali. Ako mislite da se nakon svega, 0 je lažna, 0 je lažna, lažna i pogrešna je, kao što smo razgovarali logično, također lažna. Tako smo dobili 0 i ovdje. Ako uzmete 0 ampersand 1, te da je, također, će biti 0, jer je za to lijevi izraz da bi bilo istinito ili 1, to bi trebao biti istinito i istinito. Ali ovdje imamo lažna i istina, ili 0 i 1. Sada opet, ako imamo 1 ampersand 0, da, također, će biti 0, a ako imamo 1 ampersand 1, napokon ćemo imati 1 bit. Dakle, drugim riječima, mi ne radimo ništa zanimljivo s ovim operatorom samo još ovo znak za struju operatora. To je bitovni AND operator. No, to su sastojci preko kojeg možemo učiniti zanimljivosti, kao što ćemo uskoro vidjeti. Sada pogledajmo samo jednom okomita traka ovdje na desnoj strani. Ako imam 0 malo i ja Ili je to sa, bitovni Operator OR, još malo 0, da će mi dati 0. Ako sam se malo i 0 ili je s A 1 malo, a onda ću dobiti 1. A u stvari, samo za Jasnoća, neka mi se vratiti, tako da mi okomite trake nisu u zabludi za 1-a. Dopustite mi prepisati sve moj 1 je malo više Jasno, kako bismo iduće vidjeti, ako ja su 1 ili 0, to će biti 1, a ako imam 1 ili 1 da, također će biti 1. Tako možete vidjeti logično da ILI Operator ponaša vrlo različito. To mi daje 0 ili 0 daje mi 0, ali svaka druga kombinacija daje mi 1. Sve dok imam jedno 1 u Formula, rezultat će biti 1. Za razliku od AND Operater je znak za struju, samo ako imam dva +1 u jednadžba, ja zapravo dobiti 1 out. Sada postoji nekoliko drugih operateri, kao dobro. Jedan od njih je malo više uključeni. Pa neka mi ići naprijed i brisanje to slobodan gore neki prostor. I neka je pogledajte znak za umetanje simbola, samo na trenutak. To je tipično lik možete upisati na vašem gospodarstvu tipkovnice Shift i zatim jedan od brojeva na vrhu vašeg SAD tipkovnice. Dakle, ovo je ekskluzivni Operator OR, ekskluzivno ILI. Tako smo upravo vidjeli operatoru ili. To je isključivo ILI operatora. Što je zapravo razlika? Pa neka je samo pogledajte formulom, i koristiti kao sastojci u konačnici. 0 XOR 0. Idem reći je uvijek 0. To je definicija XOR. 0 XOR 1 će biti 1. 1 XOR 0 će biti 1, i 1 XOR 1 će biti? Pogrešno? Ili zar ne? Ne znam. 0. Sada što se ovdje događa? Pa mislim o Naziv ovog operatora. Ekskluzivno ILI, pa kao naziv, vrsta, sugerira, odgovor će biti samo A 1, ako se ulazi su isključivi, isključivo drugačije. Dakle ovdje ulazi su Isto tako je izlaz 0. Ovdje ulazi su Isto tako je izlaz 0. Ovdje su rezultati su različiti, oni su isključivi, pa izlaz je 1. Dakle, to je vrlo slično I, to je vrlo sličan, odnosno to je vrlo slično ILI, ali samo u ekskluzivnom način. Ovo je jedna više nije 1, jer imamo dvije 1-a, a ne isključivo, samo jedan od njih. U redu. Što je s ostalima? Pa tilda, u međuvremenu, je zapravo lijepo i jednostavno, srećom. I to je predznak operater, što znači to primjenjuje samo jedan ulaz, jedan operand, da se tako izrazim. Ne lijevi i desni. Drugim riječima, ako se uzme u tilda 0, odgovor će biti upravo suprotno. A ako se uzme tilda od 1, Odgovor će biti suprotan. Dakle tilda operator način negirajući malo, ili flipping malo od 0 do 1, ili 1 do 0 ° C. I to nas ostavlja na kraju sa samo dvije završne operatora, tzv lijevi pomak, a Takozvani pravo operatora pomaka. Idemo pogledati kako ti posla. Lijeva operatora pomaka, napisao s dva kutnika kao što je to, na sljedeći način. Ako moj ulaz, ili moja operand, lijevo Operator pomak je vrlo jednostavno 1. A ja onda kažem računalo na napustio pomak da je 1, kažu sedam mjesta, rezultat je kao da sam uzeti da je 1, i premjestiti ga Sedam mjesta na za lijevo, a po defaultu, ćemo pretpostaviti da prostor na desnoj strani će biti postavljen nulama. Drugim riječima, 1 napustio pomak 7 ide se prouzročiti 1, zatim 1, 2, 3, 4, 5, 6, 7 nula. Dakle, na neki način, što vam omogućuje da se uzeti mali broj kao 1, i jasno ga učiniti mnogo mnogo, mnogo veći na ovaj način, ali mi zapravo idemo vidjeti više pametan pristupi za njega umjesto toga, kao i, U redu. To je to za tjedan dana tri. Mi ćemo vas vidjeti sljedeći put. Ovo je CS50. [Glazbom] SPEAKER 1: On je bio na marendu bar jede u kremastom sundae. On je sve to imao preko lica. On je nosio tu čokoladu kao bradom ZVUČNIK 2: Što to radiš? SPEAKER 3: Hmmm? Što? ZVUČNIK 2: Jeste li samo dvaput dip? Dvaput kratko čip. SPEAKER 3: Ispričavam se. ZVUČNIK 2: kratka ti čip, što zagrize, a ti opet kratka. SPEAKER 3: ZVUČNIK 2: Dakle, to je poput stavljanja cijela tvoja usta pravo u dip. Sljedeći put kada se čip, samo ga umočiti jednom i završiti ga. SPEAKER 3: Znate što, Dan? Možete umočiti način na koji želite umočiti. Ja ću umočiti način na koji želim dip.