[Glazbom] DAVID J. Malan: Ovo je CS50. I ovo je početak tjedna tri. Dakle, imamo puno uzbudljivije stvari za pokrivanje danas. Puno mogućnosti za volontira na pozornicu. I na kraju, danas je Ne radi se o koda na sve. No, riječ je o idejama, a riječ je o algoritmima, i zapravo vraćaju neke od Što smo naučili iz tjedna nula, pri čemu Podsjetimo, mi uveo ovu monstruoznost. I zaduživanje inspiracija toga, za početak riješiti sve sofisticiraniji Problemi algoritamski. Ali prvo, nekoliko obavijesti. Dakle, jedan, ako želite da se pridruže Osoblje i kolege CS50 je na ručak ovog petka, i ovdje iu Cambridge, au New Havenu, posjetite tečaj je web stranice, gdje URL može naći. Predavanje će se ove srijede ne mora biti ovdje u Sandersa. To će biti samo online, tako da naštimati na CS50 web stranici, je li ovdje u Cambridgeu ili New Haven, kao dobro. A onda je problem postaviti dva već je u vašim rukama. Ako niste ronili još, dopustite mi ponuditi snažno sastavljeno prijedlog da, pogotovo sada, kao što je problem postavlja unaprijed, vi stvarno želite početi sada, ako ne i praćakati malo na vikend ili prije kada su se prvi put izaći na Petkom, jer ćete da oni nisu nužno sve više i više izazovan po sebi. Mislim da ćete naći da je u Općenito, oni imaju tendenciju da se grubo oko istom vremenu. No, to svakako ovisi na student, i to ovisi o razmišljanje s kojima ste ga približiti. Ali uvijek, ti ​​ćeš pokrenuti protiv nekog zida, a ti ćeš pogoditi neki bug, a ti si samo neće biti u mogućnosti dobiti preko nje u nekom trenutku. I to je iznimno važno biti u mogućnosti korak dalje, vratiti sljedeći dan, ići radnog vremena, post o CS50 Raspravite ili slično, da se zapravo dobiti deblokiran. Pa imajte to na umu. Počevši najranije moguće, je najbolja stvar koju možete učiniti. Dakle, ovdje gdje smo počeli klasa, više u tjednu nula. I možemo dobiti volonter ovdje da mi pomogne pronaći mikrofone? U REDU. Stojeći već. Dođi gore. Pogodite koji je kako to ide na posao. Kako se zoveš? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Dođi gore. Drago mi je. ALAN ESTRADA: Lijepo da zadovolji vas. DAVID J. Malan: A ti si ovdje s nama u tjednu nula, naravno. ALAN ESTRADA: bio sam. Bio sam. DAVID J. Malan: Pa mogao si otići naprijed i pronaći za nas Mike Smith, kao brz kao možete? Kao brz kao možete. Doslovno suzenje problem na pola kao što je potrebno. ALAN ESTRADA: Hm. DAVID J. Malan: Doslovno suzenje problem na pola. ALAN ESTRADA: Oh. Mm. Jako dobro. DAVID J. Malan: U redu. Dobra. Hvala. ALAN ESTRADA: Vrlo dobro. U REDU. DAVID J. Malan: I tako sada, ste ga reducirane pola veličine problema. Sada smo dolje na četvrtine. Jeste li plaćati pozornost na kojoj strani smo čuvanje? [Smijeha] ALAN ESTRADA: Da, ja think-- DAVID J. Malan: Što poglavlje smo u? ALAN ESTRADA: auspusi, tako. DAVID J. Malan: U redu. Ali Mike Smith ide da se nakon ispušne cijevi. So-- [Smijeha] U redu. ALAN ESTRADA: Gdje se gleda? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Sada smo u kirurška. Sada, liječnici. Now-- ALAN ESTRADA: Let's- idemo s Real. Nekretnine. DAVID J. Malan: Real. U REDU. Ako trebate pravi. Sada, na koji način je Mike Smith? ALAN ESTRADA: Ovaj način. DAVID J. Malan: Na koji način? ALAN ESTRADA: Čekaj. M is-- pravo? Počeli smo with-- DAVID J. Malan: Da. Oni lijevo. Vaše pravo. ALAN ESTRADA: Da. DAVID J. Malan: Pa Mike je ovdje. ALAN ESTRADA: Što? [Smijeha] Loš primjer, dečki. Oprostite. DAVID J. Malan: To će učiti da skok iz svog naslonjača. ALAN ESTRADA: Oh. Oh. Te imam. Te imam. Oh. Oh. Ovo is-- redu, ja ti imam. Smith je ovdje? DAVID J. Malan: Smith, hvala. Dakle, ja ću držati obličje gore Smith? ALAN ESTRADA: O, da. Ne ne ne. O ne. To je moje. DAVID J. Malan: Oh, imaš Smith. U REDU. ALAN ESTRADA: Da, dobio Smith ovdje. Žao nam je, momci. Mislio sam Michael-- smo su u potrazi za Michaela. Oprostite. DAVID J. Malan: To je u redu. U redu, sada smo u Paccini i sinovi. ALAN ESTRADA: Paccini i sinovi. DAVID J. Malan: Samo vi i ja se u ovo. U REDU. Pronađite nas Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. Malan: Smith. Mi smo u R za smeće. ALAN ESTRADA: Glupost. Oh. Ovo će potrajati. [Smijeha] DAVID J. Malan: Cipele. Mi smo u cipele. ALAN ESTRADA: Sad smo gonna-- DAVID J. Malan: Lijepo. ALAN ESTRADA: Which-- [Smijeha] Oh, ovo je super. [Smijeha] DAVID J. Malan: To je u redu. ALAN ESTRADA: Oh, to je dobro. Ne mislim da ću imaju PSAT prijatelja nakon ovog. DAVID J. Malan: Dobro. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. Malan: U redu. Tako ćemo suzu to na pola. Uredu je. To završava loše u svakom slučaju, jer je Mike Smith neće biti u žute stranice. ALAN ESTRADA: Ah. DAVID J. Malan: Ne, to je u redu. Ali neka je pretvarati se kao on je na ovoj stranici. Tako sada ste whittled problem dolje na jednoj stranici, a pronašli smo Mike Smith. [Pljeskati] OK hvala. U REDU. To je izvanredno. Ali to je još brži nego linearno pretraživanje, u kojoj smo početi na početku knjige, i mi premjestiti naš put s lijeva na desno, vremenom u potrazi za Mike Smith. I tako, ako je telefonski imenik je možda 1.000 stranica, možda bi uzeti nas 10-ak stranica suze. Ali možda ste utjecati dotaknuo pretpostavku u sve to, što će reći da je telefonski imenik unaprijed je što? PUBLIKA: Poredano. DAVID J. Malan: To je riješeno. Pravo? To je razvrstani po abecednom redu, tako da da su svi od tih imena i brojeva su razvrstani iz A-a na Z-a, a po abecednom između. Ali danas, mi sada pitati pitanje, dobro, kako je bio Verizon ili telefon Tvrtka je ući u to stanje? Budući da je jedna stvar utjecati Ta pretpostavka, i stoga, rješavanje problema s Algoritam učinkovitije. Ali mi nikada stvarno pitao u tjednu nula, dobro, koliko je to učinio troškova Verizon ili netko drugi da biste dobili taj telefonski imenik u sortiranog bi? Pravo? Nije važno ako gleda gore Mike Smith je super brzo, ako Vam je potrebno godine sortirati stranice početku. Pravo? Možda i samo prosijati kroz slučajnom telefonskom imeniku, ako će biti super skupo to riješiti. Dakle, ako možemo imati još jedan volonter. Idemo uzeti pogledati ovdje kako smo might-- hajde up-- tome bismo mogli ići o razvrstavanju tih. A ako Jordan moze pridružite nam se ovdje na pozornici. Hajde se samo na trenutak. Kako se zoveš? CAROLINE: Caroline. DAVID J. Malan: Caroline, dođi gore. A vi ćete se pridružiti po meni i Jordana ovdje. Caroline, hvala. U redu. Pa što imamo ovdje Caroline je 26 plave knjige da FAS koristi za administriranje određene završne ispite. To su sve teško naći, ali ono što smo učinili u unaprijed je da smo stavili nečije ime Na prednjoj strani svakog od njih, ali smo zadržao je jednostavan, zatim stavljanjem van puna imena. Tako bismo staviti osobu s imenom L, D, J, B, skroz A do Z, ali oni su u slučajnim redoslijedom. I tako, ako bi, u razgovoru svoj blog put kroz problem kao i vi to učiniti, možete ići naprijed i sortirati to za nas, od A do Z. PUBLIKA: OK, L je kao, srednji. C je početak. B. J prije L. B, P DAVID J. Malan: Držite da Mislio za jednu sekundu. Jer inače, to je samo zanimljivo ti, ja i Jordanu. Idemo tamo. PUBLIKA: [nečujan]. R. DAVID J. Malan: U redu. Što radiš? CAROLINE: M dolazi nakon O. DAVID J. Malan: U redu. CAROLINE: O. DAVID J. Malan: O, dobro. CAROLINE: E. DAVID J. Malan: E, F. Da. CAROLINE: T, U, V DAVID J. Malan: V, T, U, V, tako da Izgleda kao da ste making-- zadržati ide. Izgleda radite velika hrpa ovdje, i vrsta velikog hrpu tamo. Tako je prva polovica abecede, Druga polovica abecede. U REDU. Dobra. Vrsta cijepanje problem na dva dijela. M, N, X. Da. CAROLINE: K. DAVID J. Malan: U redu. K. Znači vrsta odabira ih jedan za drugim, stavljajući ga bilo lijevo ili desno, ili Z događa na podu. U REDU. CAROLINE: Z događa na podu. DAVID J. Malan: U redu. Y se događa na podu. Sada možemo staviti X. CAROLINE: G. DAVID J. Malan: G ide lijevo. S ide dobro. U redu, A ide sve na putu utakmice. CAROLINE: A, B, C, D. DAVID J. Malan: Sada, dobro. Imamo A, B, C W događa tamo dolje. U redu, T. CAROLINE: H, I, J DAVID J. Malan: H, I, J dobro. CAROLINE: U centru, ja sam gonna-- DAVID J. Malan: U redu. Tako sada, idemo u naturi od spojiti ove različite hrpe. Tako A do C, onda vidim D i E i F i G i H i I. Nice. J, K. A onda, ovo je gomila naopako, ali to je u redu. Naravno. Možemo smanjiti neke ugla. U REDU. I onda moramo W, X, Y, Z. CAROLINE: Da. DAVID J. Malan: Izvrsno. Dakle, velika hvala Caroline za razvrstavanje tih. [Pljeskati] Hvala. Puno hvala. Dakle, sada ćemo razmotriti trenutak Kako je Caroline, prošao zemljom čineći to, i što točno smo mogli su to-- kako smo bili u mogućnosti riješiti to problem kada smo bili samo dati cijela hrpa slučajnih ulaza. Pa, izgleda da postoji je malo sustava tamo? Tako je. Dakle ranijim pismima u pismu, ona je stavljanje na lijevo, a kasnije slova abecede, ona je stavljala u desno. I čim je pronašao neki proksimalnih pisma, one koji ide tik jedna do druge, ona bi stavio one u red. I tako smo nekako imali ove male gomile sortiranog ulaza događa. I tako to je vrlo slično onome što većina nas ljudi će učiniti. Mi bi vrsta prosijati kroz njega, i mi bismo vrsta imaju mehanizam. Ali, to bi moglo biti teško napisati je dolje u formuli po sebi. Ona osjeća malo više organski od toga. Dakle, neka je vidjeti ako mi može sada vezan problem s manje ulaza. Umjesto 26, neka je nešto daleko manje sa samo reći, sedam, iza ta vrata, da tako kažemo. Postoje samo sedam brojeva? A ako je cilj sada Ruka je pronaći vrijednost, da vidimo kako učinkovito možemo ići o događaj ovaj. I neka je vidjeti ako mi može sada početi primjenjivati ​​neke brojeve, ili neke formule s kojima se opisuju učinkovitost našeg telefonskog imenika Algoritam, naš ispit Knjiga algoritam, i općenito, pronalaženje informacija. Pa za to, neka mi ići naprijed i na zaslonu osjetljivom na dodir ovdje, dići web preglednik koji ima upravo ovih sedam vrata. A ako smo mogli dobiti još jedan dobrovoljno doći ovamo, Ja sam stavio ove iste vrata ovamo. Brzo volonter. Ovaj one-- demo idu za brže i brže sada. Dođi dolje. Kako se zoveš? Trevor: Trevor. DAVID J. Malan: Trevor? U redu, Trevor, hajde dolje. Dakle, Trevor je volontirala ovdje da napraviti sličan problem, ali onaj koji je uša u djelokrugu, te da će kako bi nam omogućiti da pokušati formalizirati sada postupak za razvrstavanje tih brojeva. Dakle Trevor, lijepo da zadovolji vas. Dakle ovdje je niz, tako da govori, popis sedam vrata. Idi naprijed i pronaći nam broj 50. I onda, nakon toga, recite nam kako ste ga pronašli. Ukoliko be-- redu. Da, to je jedan ovdje? Uh oh. U REDU. Vi kliknuli da je jedan. Dobra. I dobro. Sada ste kliknuli da je jedan. I neka mi vam dati mikrofon, tako da ga imate u samo trenutak. Idi naprijed i kliknite na pokraj vrata koja namjeravate. Da dobro. Trevor: Mogu li poništite vrata? DAVID J. Malan: Ne, ne mogu poništite. Trevor: U redu. Ovaj. DAVID J. Malan: Kamo želite ići? Koji? Trevor: To je jedan. DAVID J. Malan: Ne Trevor: U redu. Ovaj. DAVID J. Malan: Da. To je dobro. U redu. Dakle, ono što je tvoj algoritam ili Postupak za to, Trevor? Trevor: Upravo sam prošao kroz vrata dok nisam pronašao 50. DAVID J. Malan: U redu. Izvrsna algoritam. Dakle, to je u redu. Jer zapravo, ako sam otkriti što je iza tih dvaju drugih vrata, što ćemo ovdje naći je da imamo samo slučajni ulaz. Tako da je zapravo kao dobri kao što ste mogli dobiti. A u stvari, imaš bolji od iscrpno traži cijeli niz, jer to bi bilo stvarno nesretni ako su hit broj 50 u zadnji vratima. Ali što ako smo umjesto dao pretpostavku. Pretpostavimo da vrsta sve ta vrata širom, tako da imate Brojevi razvrstani ovaj put, ali ovaj put to je zapravo different-- ovaj put, to je zapravo izdvojiti za vas. I sada je cilj pri ruci je pogoditi broj 50. Trevor: U redu. DAVID J. Malan: Što je algoritam će biti? Trevor: Pa, ako je to razvrstani, to je bilo ide da be-- ako najveći do najvećih, spušta, to će biti prvi, ili ako je suprotno, to će biti posljednja. Pa samo ću iskoristiti ovu vrata, a onda samo dodirnite posljednja vrata. DAVID J. Malan: Izvrsno. U redu. Tako smo otkrili broj 50. Dakle, čim je znao su razvrstani smo bili u mogućnosti iskoristiti ovu pretpostavku. Dakle, oni su previše poput telefonski imenik primjer. Čim imate, čak i sa mali problem kao što je ovaj, Vaši unosi unaprijed razvrstani, možemo zapravo pronaći vrijednost nedvojbeno učinkovitije. I nisam ti ako je to reći razvrstani male do velike ili velike za male, i tako da je vrlo razumna započeti na jednom kraju ili drugi zapravo pronaći tu ciljanu vrijednost. Dakle zahvaliti Trevor kao dobro. A ja ću propose-- lijepo učinili. Imamo malo isječak, zapravo, da je jedan je od naših najdražih trenutaka u CS50, pri čemu se ponekad ove demonstracije ne sasvim ide prema planu. I doista upravo sada, ja izvukao krivi sučelje s kojima se koristiti zaslon osjetljiv na dodir. Tako da je moja krivnja postoji. Dakle, to će učiniti za iduće godine isječak kao zašto sam se klikom na vlastitom zaslonu. Ali neka je uzeti brzo pogledati na ono što se dogodilo prošle godine s Jay, koji je došao do, mnogo kao Trevor ovdje dobrovoljno, iu ovom kratkom isječku, vidjet ćete kako je taj isti demo nije sasvim otkrivaju iste lekcije naučene. [VIDEO PLAYBACK] -Sve Što želim da učinite je naći za mene, i za nas, zapravo, broj 50 korak po korak. -Ponuditelj Broj 50? -Ponuditelj Broj 50. A možete otkriti što je iza svakog od tih vrata jednostavnim dodirom s prstom. Prokletstvo. [Smijeha] [END PLAYBACK] DAVID J. Malan: Tako da je otišao vrlo dobro. Oni su bili Nesortirani vrata. I Jay, naravno, sve to pronašao prebrzo. Trevor nije puno bolji posao u smislu nastavnu trenutku da se tako izrazim, ove godine u traje dulje da biste ga pronašli. Naravno, onda mi je dao Jay drugu priliku, pri čemu smo razvrstani vrata, baš kao što smo učinili za Trevora, i Trevor nije super i ovaj put. Ali Jay je to učinio upola brže. [VIDEO PLAYBACK] -Ponuditelj Cilj sada je također Pronađite nas na broj 50, ali to algoritamski i recite nam kako idete o tome. -U REDU. -I Ako ga pronaći, što bi film. Ako ne pronađete, možete ga vratiti. -Man. Oh! - [Nečujan] OK. Tako ću provjeriti krajeve Prvo, ako there's-- odrediti Oh. [PLJESAK] [END PLAYBACK] DAVID J. Malan: U redu. Dakle, sortiranje vrata jasno dovodi do veće učinkovitosti. I tako, dva puta brže je ono što sam mislio tamo. I tako je Jay posrećilo oba puta. I on je također imao sreće u da je prošle godine, naredio sam neke Blu-ray diskova zapravo dati. Žao mi je ove godine, što nisu imali isti, Trevor. Ali još bolje je prije nekoliko godina. A neki od vas možda znaju kolega, Sean, koji je kad je bio u CS50, bio izazvan s točno isti problem, iako u SD, kao što ćete uskoro vidjeti, natrag u dan. I vidjet ćete da ne samo da je potrebno malo više vremena nego što Jay, malo duže nego što Trevor, bilo je zapravo ovo izvrsna prilika angažirati gotovo svi u Publika la cjena ispravna, poticanje ga naći broj smo tražili. Idemo. uzeti brzo pogledati. [VIDEO PLAYBACK] -U REDU. Dakle, vaš zadatak ovdje, Sean, je sljedeći. Ja sam skriven iza njih Vrata broj sedam. No, tucked daleko u nekim od tih vrata kao i druge negativne brojeve. I vaš cilj je da mislite ove gornjem retku brojeva samo kao niz, ili samo Slijed papirica s brojevima iza njih. I vaš cilj je, samo pomoću vrh Niz ovdje, pronašli mi broj sedam. I onda se ide na kritike Kako idete o tome radi. -U redu. -Find Nam broj sedam, molim. Ne. Pet, 19, 13. [Smijeha] To nije trik pitanje. Jedna. [Smijeha] U ovom trenutku, vaš rezultat nije vrlo dobro, pa možda i zadržati ide. Tri. [Smijeha] Idi na. Iskreno, ja ne mogu pomoći, ali pitam ono što čak i razmišljati o, so-- [Smijeha] Samo prvi red, pa imaš tri lijevo. Tako me naći sedam. [Smijeha] 17. Sedam. [PLJESAK] U redu. [END PLAYBACK] DAVID J. Malan: Tako smo mogli Pogledajte ove povazdan. I naravno, neke ovogodišnje demonstracije možda Sada će završiti u sljedeća Ovogodišnji videa, kao dobro. Pa sada neka je zapravo usredotočiti na algoritme ovdje, i vidjeti ako ne možemo sada početi formalizirati kako možemo ići o uzimajući naše podatke u takvom stanju da je to riješeno, tako da je u konačnici, možemo zapravo to učinkovitije tražiti. I iako ćemo koristiti relativno male skupove podataka, kao osam brojeva mi ima ovdje na brodu, u konačnici ti isti ideje mogu prijaviti 1.000 ulaza, milijun ulaza, 4 milijarde ulaza, jer su algoritmi će biti u osnovi isti. I tako je to naša zadnja prilika za volontere danas, ali možda najviše uključeni jedan, za što nam je potrebno osam volontera da se i nas provesti kroz proces sortiranja što će uskoro biti na ovim glazbe stoji ovdje. Pocnimo ovdje. Dakle, jedna u zelenom turquoise-- je to? Jeste li počinio? Dva. Dođi dolje. U REDU. Tri. Četiri. Neka me-- redu, pet. Vi ste se imenuje svog prijatelja. Šest, sedam i osam. Dođi gore. U redu. Hvala vam puno. Dođi gore. Dođi gore. U redu. Dakle, ono što mi here-- i to ima je među one više nespretan, jer to će zahtijevati da humor ja za samo malo vremena. Ti ćeš biti broj jedan. Kako se zoveš? Annan: Annan. DAVID J. Malan: Annan. David. Kako se zoveš? JOSEPH: Josip. DAVID J. Malan: Josip, ti si broj dva. SERENA: Serena, broj tri. Stefan, broj četiri. Cynthia: Cynthia. DAVID J. Malan: Cynthia, broj pet. [Nečujan] DAVID J. Malan: [nečujan]. David broj šest. Matt: Matt. DAVID J. Malan: Mattov broj sedam. I? WAVERLY: Waverly. DAVID J. Malan: Waverly, broj osam. U redu. Ako could-- Ups. Ako vas sve, kao svoj Prvi izazov, postoji osam glazbene tribine Ovdje pred publiku. Ako bi mogao staviti brojeve na ovi glazbe stoji na takav način da se postroje sa Isti brojevi na brodu. Tako bi i sami izgledaju kao da su od stavljajući svoje brojeve na ovim glazbe stoji ovdje. Izvrsna dosad. Izvrsno. U REDU. Tako sada, idemo pitati pitanje u nekoliko različitih načina. Kako možemo ići o razvrstavanju ti ljudi ovdje? Budući da smo imali nekoliko pristupa ranije, pri čemu smo vrsta izrade dva različita kante. A onda smo općenito komad stvari zajedno. Čim smo vidjeli dva broja koji su pripadali zajedno, smo ih zajedno. Dva slova koja idu zajedno. Ali neka je vidjeti ako mi ne može formalizirati to, tako da smo u konačnici imati neki pseudo-kod hoćete, s kojima možete riješiti te probleme. Pa sad, ja sam u potrazi na tim brojevima ovdje. I vidim hrpu pogrešaka. Na kraju, želim jedan na lijevo i osam na desnoj strani. I tako gledam ove dvije, četiri i dva. I u čemu je problem, očito? Da. So. Dva očito dolazi prije četiri, tako da znate što? Dopustite mi prvo uzeti pohlepni pristup, ako će, baš kao i problema postaviti one-- ako se sjećate iz Standard Edition problema postaviti jednu, gdje sam samo lokalno riješiti problem to je upravo ovdje ispred mene i vidjeti kamo će me vodi. U REDU. Dakle, dva i četiri, pustite me naprijed i samo zamijeniti vas dvoje. Ako može fizički pomicati sebe i vaš rad, Izgleda da sam stečen popis u boljem stanju. Sada, oni su dobri. Idem dalje, četiri i šest, izgleda dobro. Nije problem. Šest i osam, u redu. Osam i jedan, drugi problem. Jer ono što je istina o osam i jedan? Jedan dolazi prije osam, pa što da radimo? Idemo mijenjati ove dvije. Od jedne do osam. I sada, ja ću nastaviti. Idem da gleda naprijed. I da vidimo što se događa. Osam i tri, od Naravno, iz reda. Idemo zamjenu. Osam i sedam, naravno. Iz reda. Idemo zamjenu. Osam i pet, naravno, neka zamjena. U redu. Popis je sortiran. Da? U redu, očito nije. Ali, to je malo bolje, zar ne? Zbog obavijesti što se dogodilo. Svaki put smo izvršili zamjenu, a manji Broj vrsta procjednim na taj način, i veći broj procjednim na ovaj način, ili ćemo početi govoriti u mjehurićima na lijevo ili u obliku mjehurića na desnoj strani. Sada, to nije dovoljno, jer u najboljem broj možda su se preselili jedan spot naprijed, ili u najgorem slučaju, broj može imati dalje preselio prvo mjesto. Pa znate što, ova vrsta od radio prilično dobro do sada. Dopustite mi samo probati ponovno. Dva i četiri, oni su u redu. Četiri i šest, oni su u redu. Šest i jedan, iz reda. Tako ćemo vas dvije zamijeniti. A sada, primijetiti problem je počinju da se malo bolje opet. Šest i tri, iz reda. Ajmo vas dvojica zamijene. Šest i sedam, ti si dobar. Sedam i pet, naravno, iz reda. Sedam i osam, u redu. I sad, ja možda trebati učiniti još nekoliko puta. A u stvari, mislim za sebe možda koliko puta maksimalno Možda sam prošetati natrag i naprijed? Mi ćemo se vratiti na to. Dakle, dva i četiri su još uvijek u redu. Četiri i jedan, nope. Dakle, neka je swap. I opet, primijetit vizualno jedna je vrsta mjehurića lijevo, gdje bi trebao biti. Četiri i tri zamjena. Četiri i šest. Šest i pet zamjena. Šest i sedam. Sedam i osam su dobri. Dobra. Mi dobivamo još bolji. Tako ćemo vidjeti. Sada imamo dva i jedan. Naravno, zamjenu. Dva i tri, tri i četiri, a četiri pet, šest i sedam, sedam i osam. Dobra. I znate što? Zato sam napravio jednu promjenu postoji, neka mi učiniti jednu duševne ček. Dopustite mi da ide sve na putu natrag na početak. U REDU. Jedan, two-- Yup, vidjet? Nešto nije bilo u redu. Tri, četiri, pet, šest, sedam, osam. I u ovom posljednjem prolazu, su li zadovoljni s mojim sada tvrdeći da razvrstava? U REDU. Vizualno, to je apsolutno točno. No, ono što funkcionalno nije također samo dogodilo u tom zadnjem prolazu koji vam omogućuje potvrditi da je ovaj popis je zaista razvrstani? Što sam učiniti ili ne učiniti ovo posljednje točno? PUBLIKA: Nije bilo promjena. DAVID J. Malan: Žao nam je? PUBLIKA: Nema promjena. DAVID J. Malan: nije bilo promjena. Dakle, to bi bilo glupo od mene učiniti da isti algoritam ponovno ako nisam napraviti bilo mijenja prvi put. A država nije promijenilo. Sigurno neću napraviti Sve promjene po drugi put. I tako, to je sigurno sada reći, Popis je sortiran. I doista, ovo je sad nešto što ćemo općenito Poziv bubble sort, pri čemu parovima, opet ispraviti pogreške, i opet, i opet, i ti zadržati ide natrag i naprijed, i natrag i naprijed, dok ne ne pravimo takve zamjene, u kojem trenutku možete biti sigurni, da, ja završio popravljajući sve pogreške. Idemo resetirati i probati drugi pristup. Ako ti dečki mogli vratiti u redoslijed ste bili prije nekoliko trenutaka, koji je izgledao ovako. Sada, neka je uzeti pristupu malo više poput ispita knjige, gdje smo bili stalno odabirom slovo abecede da smo vrsta htjeli baviti sljedeći. Možda je to bila visoka pismo, Poput, ili niskim slova Z. Dakle, svi su još u tom cilju. I sada neka mi to učiniti. Pogledajmo znam imam osam brojeva ovdje. Ja ću ići naprijed i Samo namjerno odabrali najmanji elementi. Pravo? To se čini intuitivno previše. Zašto ne mogu naći najmanji Element, stavite ga gdje mu je i mjesto, onda se sljedeći najmanji element, stavio je gdje mu je i mjesto, a samo ponoviti. Jer intuitivno, koja bi trebala raditi previše. Dakle četiri, to je prilično mali broj. Idem se sjetiti gdje je to. Čekaj malo. Dva manja. Dopustite mi sada sjetiti gdje dva je, i zaboraviti o četiri. Mi ćemo se bave kasnije. Šest, ne zanima me. Osam, nisam zainteresiran. Jedan je moj novi mali broj. Zato ću se sjetiti gdje se nalazi. Tri, ne zanima. Sedam, nije zainteresiran. Pet, ne zanima. Dakle, bez pada off pozornica ove godine, Idem zgrabite broj one-- i što je vaše ime ponovo? Annan: Annan. DAVID J. Malan: Annan. A ako bi mogao mi se pridružiti na početak popisa, neka vas staviti gdje ti je mjesto. Unfortunately-- što je vaše ime? STEFAN: Stefan. DAVID J. Malan: Stefan je na putu. Dakle, prije nego što je Stefan rješava taj Problem, što nam je činiti? Što ćemo učiniti s Stefan? PUBLIKA: [nečujan]. DAVID J. Malan: U redu. Tako smo mogli učiniti. Mogli bismo vrsta uzeti Stefana i njegovog četiri, i samo ga stavite u varijablu i držite na njemu za neki iznos vremena, time prostor za broj jedan. I to nije loše. Mogao bih predložiti, zašto ne upravo smo stavili Stefana ovdje? Zašto bi to krši jedno od ideja smo počeli govori o posljednjem vremenu, prošli tjedan? Da? PUBLIKA: [nečujan]. DAVID J. Malan: Nema indeks za to. Ako mislite da je to, doista, kao niz, ovo je kao negativne jedan, tako da nema memorije zapravo ovdje ako je to doista niz, kao što smo proglasili prošlog tjedna u predavanju. Dakle, mi ne bi trebali to učiniti. Možemo ga pohraniti u varijablu. Ili znaš što? Čuo sam netko drugi to sugeriraju. Što još možemo učiniti s Stefan? Zašto ne bismo jednostavno ga iseliti i stavite ga tamo gdje je broj jedan. Dakle, ako želite ići tamo. I doista, ovo je prilično dobro rješenje. Sada, s jedne strane, imam vrsta od samog problema gore. Četiri je sada dalje odakle bi trebao biti. To bi trebao biti prema Vezni. Ali znate što? To je mogla biti loša sreća. Možda broj osam bio ovdje. I tako, možda bismo dobivši sretni, i gurnula osam bliže kraju. Tako je na kraju krajeva, To je vrsta sve prosjeci van. Ne trebate brinuti oko četiri. Sve mi je stalo sada je odabirom najmanji element. A sada, što ću učiniti je zaboraviti broj jedan stalno, jer znam da Popis iza mene je sada riješeno. Dakle, moj popis je prethodno veličine osam. Sada, to je veličine sedam. Dakle, moj problem je dobivanje manja, iako linearno. Pa sad, ja idem za odabir trenutna najmanji element, dva. Šest, osam, četiri, tri, sedam, pet. To je najmanji element. Pa što ću učiniti with-- što je vaše ime ponovo? JOSEPH: Josip. DAVID J. Malan: Josip? Idemo ostaviti Josipa na mjestu. Sada ću se pretvarati da su ti dečki are-- dobro, Znam da ove dvije već razvrstani. Idemo sada usredotočiti na Ostatak popisa. Šest je trenutno najmanji. Osam je veći. Četiri je sada trenutni najmanji. Tri je sada trenutni najmanji. I tako sada, ja ću odabrati tri, tko is-- što je vaše ime ponovo? SERENA: Serena. DAVID J. Malan: Serena, ako bi zgrabite svoj broj i swap with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Dođi natrag, a mi smo će zamijeniti one dvije. I sada, neka je stavi ovo na autopilotu. Ja ću ići i prepustiti vama odaberite sljedeći najmanji elementi. Dun, mrk, mrk, mrk. Broj četiri, što bi trebalo učiniti? Izvrsno. Sada ću napraviti još sredinu. Dun, mrk, mrk, mrk. Vidim pet je sljedeći najmanji. Sada ću uzeti još sredinu. Dun, mrk, mrk, mrk. Šest je najmanji. Dobra. Sedam je najmanji. Bez promjena. Osam je najmanji. Gotovo. Dakle, ono što smo upravo učinio iterativno odabira jednog elementa za drugim se provesti nešto što smo će formalizirati kao izbor vrste. I to je možda čak i jednostavnije objasniti, u koji doslovno sve vas želim se samo zadržati ide natrag i naprijed kroz popis odabira, sljedeći najmanji element, dok ste učinili. Dakle, to je još jednostavnije, možda intuitivno, nego prošle. Pokušajmo jedan zadnji. Ako vi sami mogli poništiti u sljedećim položajima posljednji put, neka je vidjeti ako ne možemo Sada formalizirati jedan drugi pristup. U stvari, netko bi tamo bih predložiti kako drugačije možemo ići o događaj ovaj? Bez bacanje iz poštapalice ili vrsta odgovora koji su već poznati, Samo intuitivno, što možemo učiniti? PUBLIKA: [nečujan]. DAVID J. Malan: Da. Dakle, postoji neka velika intuicija tamo. Dobre stvari čini se dogoditi do sada u računalnoj znanosti, kada podijelimo i osvojiti problem dijeljenja je na pola i pola-pola. I tako doista smo mogla početi raditi. A u stvari, to će biti, ćemo vidi, jedan od naših najboljih rješenja još. Ali neka se vratiti na to prije dugo. U stvari, idemo raditi da malo kasnije ovog tjedna. Što drugo bi moglo radimo riješiti ovo? Dakle, svatko je ovdje u naizgled nasumičnim redoslijedom. Znaš što? Umjesto ići naprijed i natrag, natrag i naprijed, natrag i naprijed svaki put, to se osjeća kao Radim puno hodanja. Zašto ne bih jednostavno početi na početak popisa, i samo staviti četiri gdje pripada? Pa neka mi pretpostavljamo na trenutak da moj popis je samo to prvi element. Je četiri razvrstani u ovom trenutku u vremenu, ako sve što je stalo je sve tu? To je vrsta trivijalno istinito, zar ne? Kao popisa koji sadrži jedan broj, a da broj četiri je očito razvrstani. Pa neka mi samo propisuje da je ovaj popis je sortiran. Ali sada imam ostatak ovog popisa. Pa sad, sam susret dva. Gdje se dvoje očito pripada s obzirom na četiri? Prije četiri. Pa što mogu učiniti ovdje? Kako se zoveš opet? JOSEPH: Josip. DAVID J. Malan: Josip, ako bi mogao korak natrag samo na trenutak sa svojim brojem. A sada ono što bi trebalo Stefan učiniti ovdje? Idemo pomak Stefana ovdje. A sada, neka dođe Josip ovdje. A sada, dopustite mi tvrde da ovdje sve je riješeno. Dakle, slično kao rezultat, ali bitno drugačiji pristup. Nisam ni gledao što je tamo dolje. Ja samo držati uzimajući elemente kao oni predao meni, i nositi se s njima. Pa sad, vidim broj šest. Odakle broj šest pripada? Imamo dvije, četiri, šest. Točno gdje je ona sada. Tako ćemo ostaviti na miru, a sad tvrde da je ovaj dio popisa sada je riješeno. I tako, to se osjeća bitno razlikuje po tome što sam upravo kreće kroz popis ovdje linearno, a ja nikada neću udvostručenje natrag. Da. U redu. Dakle osam, gdje si ti? Upravo ovdje. Savršeno. Tako sada, jedan. Uh oh. To se osjeća kao da je će biti skuplji. Sada, u prethodnom algoritmu, Upravo sam zamijenio ljude. Tako sam mogao ga skroz na početak, ali onda se preselio Josipa. Ali ako sam premjestiti Josipa, sada ono će biti u redu? Sada, ja sam nekako undone-- imam uzeti jedan korak naprijed i zatim jedan korak natrag, jer sada Josip će biti iz reda. Tako ćemo to učiniti. Ako bi mogao preuzeti broj jedan i korak natrag za samo trenutak. Kako možemo put-- ono je svoje ime ponovno? Annan: Annan. DAVID J. Malan: Annan u mjestu? Ono što treba da se desi u odnosu za dvije, četiri, šest, osam i? Svi oni trebaju pomaknuti. Dakle, ako osam bih pomak Prvo, zatim šest, zatim četiri, zatim dva. A onda Annan, ako želite željeli doći ovdje, dobro. Ali ovdje, upravo smo vrsta platio cijenu na drugom mjestu u algoritmu. Dok zadnji put s izborom sortirati, pa čak i mjehur vrsta, Hodam natrag naprijed, natrag i naprijed, što svakako se zbroje Vremenski gledano, i doslovno postupno. Ubacivanje vrsta, na prvi pogled, izgleda kao da je super pametniji, u to sam samo što sporo, inkrementalni napredak, ali neću to natrag i naprijed. Ali ako je netko doista iz reda, obavijesti sve djelo samo sam morao učiniti. Morao sam da se presele pola popisa samo da bi se napravilo mjesta za broj jedan. Tako da je isti iznos rada do sada je osjeća, samo drugačiji tip posla. Idemo dalje. Dakle, sada znamo da su svi od jedne do osam su razvrstani. Evo, ja imam broj tri. Ako želite pokupiti broj tri, korak natrag jedan. A što vi trebate učiniti? Yep. Dakle, to je još jedan, dva, tri koraka. Tri jedinice vremena koji samo koštaju mene, tako da tri može sada stati. Konačno, sedam. Idemo naprijed i imati što se korak unatrag. To je samo ide da nas košta jedna jedinica vremena, ali to je u redu. A sada, pet će biti malo skuplji. Ako želite korak natrag. Moramo premjestiti osam, i sedam, a šest. A onda su svi sada riješeno. Tako velika ruka našim volonterima ovdje. Hvala vam puno. [PLJESAK] Hvala svima. Hvala svima. Pa da vidimo sad koliko skupi sve to bilo. Razmotrimo možda Najjednostavniji od njih, mjehur vrsta. A ja kažem najjednostavnije, samo zato možete ga riješiti pohlepno tako jednostavno popraviti u parovima problem ovdje. Fix u parovima problema Ovdje, opet i opet i opet, ponavlja onoliko puta koliko je zapravo potrebno. Tako ispada da je sa mjehurić vrsta, dobro, koliko koraka moram preuzeti Prvi prolaz tog algoritma? Možda take-- idemo see-- jedan, dva, tri, četiri, pet, šest, sedam. I tu je osam elemenata ovdje. Dakle, to je kao n minus 1 koraka do dobiti od početka popisa na kraju liste. Ali odabira vrste, podsjetiti da sam i opet odabirom elemenata i opet to je najmanja, Ja sam stavljajući ga na mjesto, ali onda nisam gleda iza mene opet. Dakle, mislim da je malo jasnije Tada je prvi put, mogao bih moraju poduzeti sve n minus 1 korake pronaći najmanji element. Onda sam ih staviti na mjesto, a ja deložirati tko je bio ovdje prije. Ali onda ja ne moram zadržati gledajući tog elementa, jer znam da je Već najmanji. Pa sad, ja mogu gledati na samo sedam elementi, zatim šest elementi, onda pet elemenata, zatim četiri elementa. I tako matematički, ako je n broj elemenata ili brojeva da smo započeli s, što možete zamisliti da je to isto kao n minus 1, plus n minus 2 koraka, plus n minus 3 koraka, plus minus N 4 koraka, sve Način dolje samo jednom koraku. I ja sam na moj zadnji osobi. A ako se sjetiti da je puno od statistike knjige ili matematičke knjige imaju one formule na Tvrdi leđa ili ispred njih, ispada da ove serije može se izraziti jednostavnije kao n puta n minus 1 preko 2. I to je u redu, ako to nije na čelu vašeg uma. No, to je zaista istina. To je samo jednostavniji način pisanja. A onda ako mislite natrag na osnovnoj školi, kada samo početi množenjem stvari, taj naravno, samo je n kvadrat minus n podijeljena 2. Sve što sam učinio je proširiti izrazi tamo. I tako ćemo prepisati ovu malo drugačije. To je n kvadrat podijeljen 2 minus n / 2. Pa opet, ja sam samo vrsta primjene neki aritmetički pravila postoje. Ali primijetite da sada najveći izraz u ovom izrazu, da se tako izrazim, je da n na kvadrat. Pa da, to je n kvadrat podijeljen 2, minus n / 2. Ali općenito, ako je n će biti velika vrijednost, Idem tvrde da n na kvadrat će biti dominantan čimbenik. To samo će biti veći doprinos broju koraka od N / 2. Dakle, što mi znači ova? Pokušajmo jednostavan primjer, čak iako math dobiva malo velika. Dakle, pretpostavimo da smo imali 1 milijuna ljudi na pozornici, ili 1 milijun stvari da želimo sortirati. Idemo plug milijun u točno toj formuli vidjeti koliko koraka je potrebno ukupno sortirati milijuna elemente pomoću recimo, Izbor vrsta. Tako ćemo imati istu formulu kao i prije. Ja bih plug milijuna, tako da sam se milijuna kvadrat podijeljeno sa 2, minus milijuna podijeljena 2. Ako ja tu matematiku unaprijed Ovdje imamo 500 milijardi minus 500.000, što daje nam 499999500000, što je prilično darn velika. U stvari, ako usporedite sada 499.000.000.000, 999 milijuna, 500.000 protiv naše izvorne vrijednosti, 500 milijardi, to je tako prokleto blizu. Pravo? n na kvadrat podijeljen 2 daje us-- odnosno, n na kvadrat podijeljen 2 dao nam 500 milijardi. To je prilično darn blizu na 499,999,500,000, što znači oduzimanjem off 500.000, ili općenitije, oduzimanjem off n na kvadrat, nije stvarno velika stvar. N na kvadrat čini to brojevi rastu jako brzo. Sada, ovo je važno samo ukoliko kao i mi, kao i računalnih znanstvenika, općenito neće brinuti toliko o nijansama tih formula i upravo ono što Točni odgovori su. Mi se brinemo samo to, znate što? Na kraju krajeva, ovaj formula je na red od n kvadrata. Da, mi smo dijeljenjem s 2 unutra. Da, mi smo oduzimanjem off n minus 2. Ali na kraju dana, pojam da nas stvarno boli i košta nas puno koraka je da trg pojam. I tako ono što računalni znanstvenik će općenito napraviti je ignorirati sve one manji pojmovi reda, i samo pogledajte onaj koji doprinosi najviše cijeni. I to je lijepo, jer možemo sada govoriti u mnogo većoj općenitosti o algoritmima, a može ih usporediti. A činjenica da sam Korištenjem ovog O je namjerno. Kada kažem na red od, ja sam konkretno koji se odnosi na nešto pozvao veliki O. I veliko O je zapis da računalo Znanstvenik koristi za opisivanje gornju granicu na nešto. Dakle, ako ti kažeš da je algoritam je u velikoj O n na kvadrat, kao što sam predložio samo Prije trenutak, to znači da u smislu njegovog trčanja Vrijeme i njegova učinkovitost, to traje na red n na kvadrat korake. Možda i više, možda i manje. Ali to je na red n na kvadrat. I to je gornja granica. To neće biti bolniji od toga. To neće biti n kubu ili 2 do n, ili nešto mnogo veće. Ovo je gornja granica na što god to je trošak. Pa s obzirom da je, neka je razmotriti samo nekoliko primjera. A to je samo konačni popis vrlo česte trčanje puta za algoritme koji je trebao biti ilustracije nekih stvari koje smo već vidjeli. Tako na primjer, u slučaju Izbor vrsta, što sam tvrdio ovdje je da je izbor sortirati je trčanje Vrijeme je na red od n na kvadrat. U najgorem slučaju, ja ću imati cijela hrpa slučajnih brojeva ovdje. A kao što smo vidjeli matematički, ako sam držati hodanje kroz popis, kroz Popis, odabirom sljedeći najmanji i opet je element, ako sam zapravo napiši sve korake Vodim kao što sam predložio formulaically prije, to je po nalogu n na kvadrat koraka koje uzimam. I ispada da mjehur sortiranje i umetanje sortiranje su jednako spori u najgorem slučaju. Razmislite, na primjer, umetanje vrsta, vrlo zadnji algoritam možemo rješavati, koji nas je, pogledajte elementa, a zatim ga umetnite gdje mu je i mjesto. A onda smo pogledali sljedećeg elementa, i umetnut gdje mu je i mjesto. Dakle, razmislite najbolji mogući scenarij. Pretpostavimo da je moja volonteri redati doslovce ovako, jedan do osam, već riješeno. Koliko koraka je umetanje vrsta će potrajati sortiranje osam osoba, ako stignu na pozornici izgleda ovako? Osam ljudi već riješeno. I ja koristiti za umetanje vrsta. Taj posljednji od algoritama. Pa, neka je reenact jako brzo. Dakle, ako počnem ovdje, vidim jedan. Gdje je jedan pripada? Spada ovdje. Vidim dva. Gdje se dvojica pripadaju? Upravo ovdje. Vidim tri. Gdje tri pripada? Upravo ovdje. Vidim četiri. Upravo ovdje. Pet, šest, sedam, osam. Nema razloga da se ponavljam. I tako, koliko koraka da je u pogledu n? To je na red n koraka, zar ne? n minus 1. Ali sam uzeo linearni niz koraka, a sada sam učinio. Tako da je najbolji slučaj, ipak. Što o najgorem slučaju? Ono osam su tamo, a sedam su tamo dolje, i jedan i dva su ovdje, tako da da je popis zaista bili preokrenuti? Pa, što će se dogoditi, istina ako je to broj? I mi ćemo učiniti samo par primjera. Što ako, doista, broj osam je ovdje, a number-- Ups. Pa što ako je, doista, broj osam je sve ovdje, i ja sam koristeći umetanje vrsta? U REDU. Ja tvrdim u ovom trenutku to je na mjestu. Ali sada, seven-- gdje se sedam ići? Naravno, to ide ovdje. Pa moram premjestiti osam nad jednom mjestu. Sada šest, gdje to ide? Pa, u redu. Sada moram premjestiti osam više mjesto, a sedam više mjesta, a onda sam pasti dolje šest. Dakle, prvi put, to trošak ja jedan korak popraviti stvari, onda me koštalo dva koraka popraviti stvari. Koliko koraka je to događa da se popraviti stvari koje treba staviti pet na pravom mjestu? Tri. Jer sada moram premjestiti jedan, dva, tri. Koliko koraka je da će potrajati staviti četiri na pravom mjestu? 4 plus 5, plus 6, plus 7. I tako je matematički istovjetan ono što je opisano za odabir vrste. Imamo ovu seriju to je samo raste. 1 plus 2 plus 3 plus 4, ili obratno, 7 plus 6 plus 5 plus 4 dodaje se za današnje svrhe na red n na kvadrat. Pa neka mi propisuje da previše mjehurić sorta je također na n na kvadrat. Jer mjehurića vrste, svaki Vrijeme idem kroz popis, Vodim otprilike koliko koraka? Svaki put kad sam doslovno hoda od tamo do tamo? Oko n koraka. Ali koliko puta sam možda morate proći kroz popis? Pa, otprilike nje vrijeme. Možda n minus 1, ali otprilike n puta. Pa, zašto je to tako? Pa, s bubble sort, ako možemo početi s bubble sort, s popisa u najgore moguće Situacija, što je opet posve unatrag, što će se dogoditi? Idem kroz popis, i broj on pripada sve tamo. No, s bubble sort, koliko se jedan premjestiti na moj prvi proći kroz popis? Koliko mrlje on doći bliže ispravnom mjestu? Samo jedan. Dakle, ako ste vrsta razlog kroz to, svaki put kroz ovaj algoritam, Davidovi uzimanje otprilike n koraka. No, koliko prolazi kroz popis je to uzeti za jedan balon u lijevo, gdje joj je i mjesto? On je dobio da se presele poput, n prostori ovaj način. Tako je samo napraviti sortiranje popisa, Moram prošetati natrag i naprijed n puta. I svaki put, ja sam gledajući n elemenata. Dakle, to n stvari n puta na redoslijed n na kvadrat. Sada ćemo vidjeti u nekim od gaćice koje su ugrađeni u CS50 je sljedeći problem postaviti, drugi pristup na njih, ali za sada, neka je samo uzeti u obzir neke druge trčanje puta, pogotovo ako su one sortiranje potrajati malo vremena da sjedne. Što je algoritam smo već vidjeli koji vodi na red n koraka? Što treba uzeti linearnu broj od koraka koje smo do sada vidjeli? Što je to? Potraga telefonski imenik. Prvi algoritam. Pravo? Gdje smo linearno u potrazi za Mike Smith? Doista. Iz tjedna nula, kad sam počeo okreće jednu stranicu u isto vrijeme, pa čak i sam rekao da je to neka vrsta linearnog osjećaj algoritma, i imali smo tu sliku o ploča s ravnom crvene linije i ravno žuta linije, oni su doista algoritmi koji su u velikom O n. Budući da pronađete Mike Smith u telefonu Knjiga od n stranica, u najgorem slučaju, Možda me n korake poduzeti. Što je uzimanje pohađanje? Jedan dva tri četiri pet šest. Što je vrijeme rada ove algoritam za uzimanje pohađanje? Big O n, jer u teoriji sam moraju ukazati svima u sobi. Sada kao stranu, što je Drugi optimizacija iz tjedna nula? Dvije, četiri, šest, osam, 10, 12. Računalni znanstvenik shvatiti, pričekajte minutu, to je na red n podijeljena u dva koraka. Pravo? Jer ja radim dvoje ljudi u isto vrijeme. Ali ćemo zanemariti oni niži pojmovi reda, i samo ćemo se odbaciti razdijelite po 2, i samo reći veliko O n za taj algoritam kao dobro. Što je s ovim? Mi ćemo preskočiti neke od njih, ali ono je algoritam koji je log n? To je otprilike prijavite n koraka? Podijeli pa vladaj. Točno. Poput telefonski imenik, primjerice u tjedan nula i ranije danas, gdje smo podijeljeni problem opet i opet i opet. To nacrtao smo na brodu u tjednu nula kao zakrivljena zelene linije, i rekao mi da je dan logaritamska algoritam. I doista, broj IT koraka potrebno izvršiti podijeli pa vladaj, ili binarno traženje kako ćemo početi nazvavši ga, kao u telefonskom imeniku, je na red i zapisnik koraka. A to je malo čudan jedan. Ono traje jedan korak, ili još specifičnije konstantan broj koraka? Možda je to dvoje, možda je to tri, ali računalni znanstvenik jednostavno To pojednostavljuje kao veliki O 1, neki konstantni broj koraka. Što je nešto što bi mogao učiniti da ima konstantan broj koraka? Što je vrijeme rada klicati? Stalna vrijeme. Pravo? Kao što je vrijeme rada radi ništa da traje samo jedan rad, kao što su ispis F Hello World. To bi se moglo reći da je vremenska konstanta, osim manje kutak slučaju s ispisa F, Ono što se može prikazivati ​​vrijeme tiska F zapravo biti? I zašto? Što je n mjerenje u tom slučaju? PUBLIKA: [nečujan]. DAVID J. Malan: Točno. Broj znakova želimo ispisati. Dakle, to je vrlo kontekstu. Danas smo bili s naglaskom puno na slova i brojeve ovdje na brodu. Ali to također može biti likovi u stvarnom nizu. Tako ispada postoji još jedan mjera koja će se početi brinuti o, a to je suprotno velikog O, da tako kažemo. To je omega zapis. Dok veliki O znači što je gornja granica na trčanja vrijeme? Maksimalno, koliko vremena Možda se nešto poduzeti? Omega-- žao to čuva dolaze up-- je suprotno od toga, pri čemu je donja granica na količinu vremena nešto može potrajati. So. Na primjer, ono što je algoritam koja se uvijek nje kvadratnom korake? Pa, jedan od algoritama smo vidjeli Danas, u stvari, može biti da je kao dobro. Sortirati Izbor. Izbor vrsta je prilično glupo. Čak i ako je algorithm-- žao, čak ako je polje već razvrstani, Izbor vrsta će Produæite kroz popis kako bi bili sigurni da ima najmanji Element opet i opet i opet. A čak i ako se ljudi u Publika zna da, pričekajte minutu, već prošlo najmanji element, računalo ne zna da je do izgleda sve na putu kroz popis. Slično tome, donju granicu koja može se također uzeti u obzir Možda linearno vrijeme. Koliko vremena je potrebno da sortirati n elementi u najbolji Slučaj korištenjem nešto poput mjehurića vrste? Pretpostavimo vaš popis je već riješeno. Rekli smo mjehurić vrsta preuzima redoslijed n na kvadrat korake. Ali što ako je već razvrstani? Što ako ste shvatili nakon jedan prolaz kroz niz da ste napravili nema zamjene? Da li je potrebno da bi što više prolazi? Ne. Dakle donju granicu mjehurić vrste moglo bi se reći da je linearna. Omega n. I možemo gledati na drugi od njih kao dobro. Tako ćemo uzeti brzo pogledati na samo vizualizacija ovdje vidjeti kako oni se razlikuju. Ja ću ići ovdje u ovo stranica koja je dostupna na web stranici C50, ali to će biti bol da se radi, jer koristi tehnologiju pod nazivom Java apleti, što je uglavnom nepodržan ovih dana, najmanje Chrome i nekih drugih. I neka mi ići naprijed i ubrzati taj i objasniti što se događa. To je demonstracija mjehura vrsta, prvi algoritam smo pogledali. I to je vizualizacija, što je svaki tih šipki predstavlja broj. Veći bar, veći broj. Manji bar, Što je manji broj. A što možete vidjeti vizualno, čak iako je to ide super brzo, je da je crvena traka je poput mene, hodanje natrag i naprijed popravljanja problema. Možete vidjeti da su veći elementi su doista mjehurića gore desno, i manji elementi su mjehurića gore lijevo. I ovdje, ako zapravo pobliže, zapravo možemo brojati Broj usporedbe i zamjene koje su napravili. No, umjesto toga, pogledajmo u drugom algoritmu Gledali smo ranije s našim volonteri, izbor vrste. Vizualno ima vrlo različit učinak. No, to je, opet, vrlo intuitivno, u da držimo odabirom sljedeći najmanji Element, a dobili smo malo sreće. To osjetio bitno brže. Ali ako mi ran to opet i opet a opet s puno ulaza, vidjeli bismo da je doista još uvijek u velikoj O n na kvadrat. Idemo napraviti jedan posljednji Ovdje, umetanje vrsta, koji je bio treći algoritam Gledali smo, i opoziva da je ovo jedan se bavi Elementi kao što ih susreće, ali onda možda smjene više stvari kako bi napravili mjesta, umetanje elemenata gdje pripadaju. I to također završava dajući Konačni rezultat. Sada su sve tri od njih Osjećao se vrlo brzo. I doista, trčao sam ih u prilično dobrom isječak. Ali bitno, oni su svi prilično strašno, da budem iskren. Sve ove algoritama do sada koji rade u velikim O n na kvadrat potrajati vrlo malo vrijeme za trčanje na kraju. I doista, možemo vidjeti i osjetiti to na kraju ako sam podići ovaj treći i konačni demo. Ovo je još jedna vizualizacija koja se događa pokazati mjehurić vrsta na lijevoj strani, Izbor vrsta u sredini, i nešto, kao jedan od naših ruka podiže ranije predložili, spajanje vrsta na desnoj strani. Podijeli pa vladaj Strategija na desnoj strani. I to je, zapravo, ono što smo ide pogledati u srijedu. Ali neka vremena ove izvoditi paralelno. To je otprilike isti broj Elementi, sve radi istovremeno. Bubble sort vs izbor sortirati vs spajanje vrste. Sada, svi oni prikazuju teoretski istovremeno. CPU radi na ista brzina, ali Možete osjetiti kako je to dosadno vrlo brzo će postati, i koliko brzo kada smo se uvelo malo tjedna Algoritmi Zero-a mogu ćemo ubrzati. A sada ćemo usporediti te u jednom prošlom obliku. Idem samo naprijed na CS50 web stranice, gdje imamo konačnu link za danas, gdje je netko na internetu Ljubazno sastaviti video koji bilježi ono drugačiji sortiranje Algoritmi zvučati. To je umetanje vrsta. [Bip] Čime ste primjeni učestalost na temelju visine bar bar. To je balon vrsta. [Deformiran bip] Dolazi do sljedećeg is-- dolaze pokraj is-- odabir vrsta, gdje opet smo odabir sljedeći najmanji element, i možemo vidjeti da raste s lijeva na desno. Spoji vrsta, naš pobjednik do sada i danas. Obavijest o tome kako je to dijeljenjem stvari u [nečujan] polovice i četvrtine. Gnome vrsta, koje nemamo govorio o, i stvara vizualno i audally malo različitih oblika i zvuka. Ide naprijed i natrag, čišćenje stvari. Također provjerite heapsort na ovog tipa web stranice. I to je to. Mi ćemo vas vidjeti sljedeći put. [Whooshing i glazba]