Govornik: U redu, ovo je CS50. To je kraj tjedna tri, a ako niste iskoristili već, Znam da će biti ručak ovaj petak, kao i obično, u kojoj možete uživati ​​dobar razgovor i hrane na Vatra i led s nekim od CS50-a osoblje i kolege. Krenite na ovaj URL ovdje. 

Sada možete sjetiti, ili ste svibanj uskoro biti upoznati s, te stvari ovdje, što daju se na kraju semestra za mnoge klase. Takozvani ispit plava knjiga, u kojoj pišete svoje odgovore na ispitima. Sada imam ovdje 26, kao plava knjiga, na svakom od njih je napisano ime, preko Z. A Doista imena su tako jednostavno, do Z. A jedan od ciljevi pri ruci danas koja će se nastaviti, što smo započeli u ponedjeljak, što nije toliko gleda na kodu, ali stvarno gleda na ideje i rješenja problema. Jedan od ciljeva i obećanja o ovom tečaju je da vas naučiti da razmišljaju više Pažljivo, više sustavno, i učinkovitije rješavanje problema. I doista, što možemo učiniti da se uistinu čak i bez dodirivanja liniju koda. Dakle, imam par slonova do danas ovdje, narančaste i plave, ako smo mogli dobiti jedan volonter, Možda iz dalje natrag nego inače. Kako bi bilo tamo, dođi ovamo. Cilj je što će biti s pomoći uz administraciju ovaj ispit ovdje. Koje je tvoje ime? 

PUBLIKA: Mary Beth. Govornik: Mary Beth, dođi gore. Dopustite mi da se mikrofon ovdje za vas. Drago mi je. 

PUBLIKA: Drago mi. Govornik: U redu, tako da imam Ovdje plava knjiga od A do Z, i ja ću se pretvarati da Imam jedan od studenata, i oni dolaze u pomalo slučajno Na kraju tri sata ispita blok pa oni završiti u nekim polu-nasumično ovako. Sada je vaš posao u samo nekoliko trenutaka ide da be-- to je zapravo kako su to predao krajem klase, najvjerojatnije. Vaš posao sada će biti, sasvim jednostavno, riješiti ove plave knjige za nas od A do Z. 

PUBLIKA: Oh, to je će potrajati zauvijek. 

Zvučnik: I mi ćemo gledati kao što ste to učinili, nema pritiska. PUBLIKA: Ne, nema pritiska ili bilo što. 

Zvučnik: I za zabavu, ajmo dići timer. 

PUBLIKA: Toliko zabavno, jako zabavno. 

Govornik: Ja mogu držati mikrofon za vas. U redu, upravo smo udvostručili svoju brzinu. Dakle, u međuvremenu, neka mi predstavljati ono što je će biti pitanje za Mary Beth je ono što ona radi, kako je ona ide o rješavanju ovoga? A u stvari, možda nećete imati ikada razmišljali o nečemu tako jednostavno kao kada pokupiti do 26 knjiga kao što je ovaj, koji nemaju prirodni naredio da se njima. Što je proces da ste zapravo koriste? Je li to pravedno slučajni samo branje prvi vidite i stavljajući ga na njegovo mjesto? Da li prvo premjestiti svoje ruke oko traže onda traže B? Da li se pogledati na Par ih uz bok i samo reći, čekaj malo, ovo nije u redu, a onda mijenjati redoslijed? Vidjeli smo već u ponedjeljak da postoji više načina u kojem možemo to učiniti, a Doista kako smo blizu kraja ovdje, Ja bih se na znanje, možda od onoga što je Mary Beth se radi. Imamo nekoliko pilota Čini se, veći, tri manja. 

PUBLIKA: Ja sam ih naručivanje kad nađem dva slova Znam da su zajedno u nizu, Ja ih staviti zajedno, tako da ne znam morati brinuti o održavanju Staza za čitav red knjiga. To je samo, o, prvo, Imam tu hrpu ovdje. Govornik: Dakle, gotovo kao puzzle komada koji imaju pravo na oblik podudaraju se jedni s drugima. PUBLIKA: Prilično mnogo, da. Govornik: U redu, izvrsno. I sada je svaki od tih piloti navodno je izdvojiti? 

PUBLIKA: Da. 

Govornik: U redu, kroz Z. Sve Dobro, čestitam, ti si to učinio. Imate svoj izbor. Plavi? U redu, hvala ti za to. Tako je Mary Beth nije predlaže ono što joj je pristup bio, ali ono što je još jedan pristup koji će vas moglo ići oko sortiranja te stvari? Što biste vi učinili? Rekord pobijediti bi bilo jednu minutu i 50-ak sekundi, plus one Zaboravio sam brojati. Što biste vi učinili? Da? PUBLIKA: Uzmi snop. Počnite od početka. Provjerite svoje radove. A ako vrhu jednog je veća nego, možda, oni su, Dno je jedan veća, a zatim ih prebaciti. 

Govornik: U redu, tako da počevši na vrhu i na dnu, a zatim raditi svoj put unutra kao što je to, zamjene ih? U redu, tako da malo slična u duhu na bubble vrste, ali odabiru krajnosti Ne susjedna parova. No, kratko je u tome da postoji sigurno hrpa različitih načina mogli smo to učinili, i iskreno, mislim da ti vrsta usvojio par pristupe, zar ne? Vi napravili svojevrsno četiri sortiranost pilota, a a zatim ih učinkovito spojene zajedno. I to je, pretpostavljam, još jedan Tehnika uopce. Nisi ga tretiraju kao jednu veliku hrpu, li podijeliti problem u četiri četvorci, ako hoćete, i onda nekako ih spojio na kraju. 

Tako ćemo razmotriti, u konačnici, Kako inače bismo mogli to učiniti. Formalizirali smo ideju bubble sort posljednji put, i mjehurića svojevrsni Podsjetimo je algoritam koji smo vizualizirati s osam od svojih kolega ovdje, naizgled nasumično razvrstani po prvi put. I mi smo tada odlučili parovima, ako dva elementa su izvan reda, jednostavno ih zamijeniti. Dakle, četiri, a dva su očito preko reda, pa ta dva kolege uključen pozicije. A onda ćemo ponoviti s četiri i šest, zatim šest i osam, na svakoj iteraciji, pomicanjem u desno. 

Dakle, dao osam osoba, koliko parovima usporedbe sam napravio dok hodaju od lijeva na desno u jednom takvom iteraciji? Koliko usporedbe? Sedam, zar ne? Jer ako postoji osam ljudi, ali imate par ih i držati se kreće jedan hop na desno, nećeš imati osam usporedbe, jer se ne može usporediti Element protiv sebe, ili bi samo biti besmisleno, tako da imate sedam. Ili općenitije, ako se imamo n ljudi, mi to n minus 1 usporedbe s bubble vrste. 

Tako ćemo razmotriti sada koliko dobro ili loše mjehur svojevrsni je zapravo bio, i pokušati kako bi sebi dati vokabular s koji se kritiku algoritmima kao što je ovaj, i ubrzo naše. Dakle, na prvom prolazu kroz mjehurić sortirati, prvi put Hodao sam s lijeva na desno preko stage, uzeo me n minus 1 usporedbe. I to će biti moj jedinica mjere, zar ne? Ja je vrsta govori i šetnje, Nešto brzo, nešto sporo, pa računajući moj broj sekundi nije posebno reći, ali brojanjem Operacije koje sam učinio u ponedjeljak, Uspoređujući dvije osobe, da se osjeća kao lijep jedinicu mjere. 

Dakle, n minus 1 korake prvi put, ali ono što se tada dogodilo nakon toga? Što je jedan naopako jednom prolazu kroz inače nerazvrstani popisu? Što mi možete reći o elementu koji je bio skroz tamo? Da? To je bio najveći elementa, zar ne? Broj osam, iako ona počelo ovdje, svaki put sam je u odnosu prema susjed, ona je zadržao mjehurića do desne na desnoj strani popisa. I doista, to je mjesto gdje algoritam dobiva svoje ime. 

Sada po toj logici, koliko usporedbe Trebam napraviti na drugi put Ja bi tu loptu s lijeva na desno? n minus 2, zar ne? To bi samo biti gubit svoje vrijeme, ako sam zadržati uspoređujući osam protiv nekoga drugo, jer smo već znali je bio na pravom mjestu. Dakle, to je malo optimizacije, tako da sljedeći propusnica će biti plus n minus dva koraka, gdje je n je broj osoba. Sada možete vrsta zaključivati, Ako niste računalni znanstvenik, kako to završava. Na kraju ovog algoritma, vjerojatno imaš samo jednu usporedbu napustio. Morate vrsta popraviti početku popisa u slučaju dva i jedan su od reda i trebao bi biti jedan i dva, tako da je ovo s dna se na plus 1 konačni usporedbu. 

Sada točka, točka, točkica vrsta valova je Ruke na neke od juicier detaljima, ali neka je samo ići naprijed i pojednostaviti. Ako se sjećate iz visokih Škola, iskreno, puno vas imali matematičkih knjiga koje su imale Malo Cheat Sheet na naslovnici ili stražnji poklopac koji vam je pokazao ono serije summations poput To u konačnici zbrajaju se. U općem slučaju, ako imate promjenjiva kao n, i zaista ovo, ako ste gledali na svoje stara škola matematike knjiga, vidjeli biste da je to zapravo dodaje do tog iznosa ovdje, n puta n minus 1 sve podijeljeno s 2. Dakle, za sada neka mi samo propisuje to je istina, pa na skok vjere, to je ono što ovaj sažima do, a što smo mogli dokazati da je u općenitijem slučaju. No, sada ćemo proširiti ovo. Tako ćemo umnožiti ovo, tako da je n na kvadrat, minus nje, sve podijeljeno s 2. To je stvarno n kvadrat, podijeli s 2, minus n nad 2, tako da je sve lijepo i zanimljivo. Ali što se događa ako smo Sada plug-in vrijednosti? Pretpostavimo da nisam imao osam ljudi, ali kažu milijun. I samo zato milijuna to je prilično velik broj, ajmo plug da je u i vidjeti što će se dogoditi. Dakle, ako sam čep milijuna u toj formuli Ja ću dobiti milijun na kvadrat, podijeljeno sa 2, minus milijuna, podijeljeno s 2. Sad što se to događa na jednak? Dakle, 500 milijardi, minus 500.000. A ako sam zapravo učiniti da je matematika, to znači da razvrstavanje milijun ljudi s bubble vrste možda mi se 499999500000 koraka ili usporedbe na kraju, mi smo samo extrapolating. 

To se osjeća prilično sporo, ali iskreno mjerenje jedan određeni input ovako, nije sve što govori. Ali doista ne upućuju na to da kao n dobiva sve veći i veći, ovaj algoritam vrsta osjeća još gore i još gore, ili ste stvarno početi osjećati bol koja potenciranje, da n na kvadrat, koji dodaje se prilično brzo. I ovaj detalj nije izgubio na ljude, u stvari Prije nekoliko godina sigurno senator koji je bio kampanja, sjeo za intervju s Googleovog Erica Schmidt, izvršni direktor u to vrijeme, i bio je izazvan s pitanjem baš kao i mi danas istražuju. Idemo pogledati. 

[Video reprodukciju] 

-Senator, Ti si ovdje u Googleu, a ja volim razmišljati predsjedništva kao intervju za posao. Sada, to je teško dobiti posao kao predsjednik, i ti si idući kroz surovost sada. Također je teško dobiti posao u Googleu. Imamo pitanja, a mi pitajte naši kandidati pitanja, a to je jedna od Larry Schwimmer. Što-- ste vi mislite da sam šalite, to je upravo ovdje. Što je najučinkovitiji način da se sortirati milijun 32-bitnih cijelih brojeva? 

-Well-- 

Žao mi je, maybe-- 

Ne, ne, ne. Mislim da je mjehurić vrsta bio bi pogrešan način da ide. 

Hajde, tko ga je to rekao? Nisam vidio računalo Znanost u pozadinu. 

-Imamo Naše špijune tamo. 

-OK, Pitajmo drugačije Intervju pitanje. 

[END video reprodukciju] 

Zvučnik: Dakle govorimo o specifični brojevi ipak, ne će biti sve što je korisno. To nije život lekcija koju mjehur sortirati, dao milijun ulaza, možda se čak 500 milijardi korake. Vi stvarno ne mogu generalizirati previše učinkovito toga i donositi dobre odluke o dizajnu prilikom pisanja programa. Tako ćemo se usredotočiti iako o tome bismo mogli pojednostaviti ovaj rezultat. 

Tako sam istaknuo u žuto ovdje Rezultat n kvadrat, podijeljeno s 2, tako milijuna na kvadrat podijeljen 2, i Ja sam istaknuo ono što konačni odgovor bio Jednom smo oduzima off n podijeljena 2. A tvrdnja da ću napraviti sada je, koji kritički briga ako oduzmete off Malo stara nje više od 2, kada je prvi dio ove formule je tako puno veći? Dominira drugi Izraz, n kvadrat, podijeljeno s 2 toliko je mnogo veći, jasno, kao što je nje dobiva velika kao milijun, da je tamo stvarno velika razlika u kraj dana između 500 milijardi i 499.999.500.000? Ne baš. I tako što ćemo učiniti što je računalni znanstvenici ignoriraju one niže pojmove reda i uzeti nešto poput ovog i stvarno samo ga pojednostaviti kako bi Pojam koji će važno. Veće naše skupine podataka dobiti, veći naše baze podataka dobili, više web stranica moramo tražiti, više prijateljima imate na Facebooku. 

Kao nje dobiva veći, mi smo stvarno će se brinuti o veličini termina u svakoj takvoj analizi naša izvedba algoritama. A ja ću reći, znate što, Bubble sorta je po nalogu velikog O, po nalogu n na kvadrat. To nije točno n kvadrat, kao što smo vidjeli, ali tko stvarno brine o tim manjim uvjetima, i iskreno, tko je zapravo brine ako podijelimo s 2? To je samo konstantan faktor. I 500 milijardi u odnosu na 250 milijardi stvarno da je veliki posao? Mogao sam samo čekati jedne godine, neka moj laptop doslovno dobili dva puta brže u hardver, i da je na neki način razlika samo ide dalje, naravno, tijekom vremena. 

Ono što mi je stalo je izraz, dio izraza koji će se razlikovati kao što je naš ulaz dobiva veći i veći. I doista, u stvarnom svijetu, to je ono što se događa sve više je ulaze na naše probleme i algoritmi su sve veći. Tako veliki O će biti zapis, asimptotsko zapis, koji smo upravo koristiti kao računalni znanstvenici opisati performanse, ili trčanje vremena, algoritma. Tako da možemo usporediti algoritme na različitim računalima pisanim od strane različitih ljudi, pomoću Neki osnovi slična metrički poput broja usporedbe ste izrade, ili možda broj swaps radite. 

Ono što mi se ne ide na Broj je količina vremena koji prolazi na sat na zidu obično. Ono što nećemo brinuti o je koliko memorije koristite danas na Barem, iako je to još jedan resurs možemo izmjeriti. Mi ćemo pokušati temeljiti naše analize o samo osnovnim operacijama, one, iskreno, da možete vidjeti najviše vizualno. Dakle, nešto poput velikog O n kvadrat, ja tvrdim da je O n na kvadrat gornja granica na tzv trajanju od mjehurića vrste. Drugim riječima, ako vas Htio tvrde da postoji ova gornja granica koliko koraci algoritma moglo potrajati, to će biti u velikoj O n kvadrat u ovom slučaju, gornja granica. 

Što ako umjesto promijeniti Priča se da nije riječ o balonu vrste, ali o tome gornju granicu. Možete li se sjetiti algoritma koje smo gledali na već čija je gornja granica, maksimalna mjerenje vremena ili operacija, bi se reći da je omeđeno N, linearna funkcija, Ne kvadratne onaj koji je zaobljen? Što je algoritam koji uvijek ne traje više nego kao n koraka, ili 2n koraka, ili 3n koraka? Da? 

PUBLIKA: Pronalaženje Najveći broj u popisu? 

Govornik: Savršen, pronalaženje Najveći broj u popisu. Ako sam dao popis ljudi za primjer, svaki od koga se drži broj, što je najveći broj koraka da me treba poduzeti, razumno pametna osoba, pronaći najveći osobu u tom popisu? nje, zar ne? Budući da je u najgorem slučaju, gdje je možda najveća vrijednost biti? Točno, skroz na kraju. Dakle, u najgorem slučaju gornju granicu, mogao bih moram ići do kraja ovamo i biti poput, Oh, ovdje je broj osam, ili što god da je vrijednost. Sada bi samo biti glup ako sam zadržao ide, zar ne? U potrazi za sve više i više elemenata Ako je posljednji od njih je tamo? Pa sigurno, n gornju granicu. Ne treba uzeti više koraka od toga. 

Pa što ako se umjesto toga sam predložio da postoje algoritmi u ovom svijetu koji imati vrijeme rada koji je omeđen velikim O iz log n, prijavite n? Gdje smo prije vidjeli ovo? Da? 

PUBLIKA: U problemu telefonski imenik? Zvučnik: Kao problem imenika. Što je mjerilo koliko koliko vremena i koliko suze IT Trebalo mi je naći nekoga poput Mike Smith je u telefonskom imeniku? Tvrdili smo da je log n, a čak i ako nisu upoznati ili je to malo mutno što logaritam ili eksponent bio, Samo zapamtite da log n općenito se odnosi na proces U tom slučaju, dijeljenja nešto na pola opet, i opet, i opet, i opet, kao da je to dobiva sve više mali kao što učiniti. 

Dakle, prijavite n odnosi, sigurno, do telefonskog imenika, primjerice, na binarnom potrazi u teoriji, kada smo imali virtualne vrata na brodu, ili kad je Sean je u potrazi za nečim. Ako je koristio binarni pretraživanje, prijavite n će biti gornja granica na koliko Vrijeme koje traje. Ali ti algoritmi koja su bila u log n pretpostaviti što ključni detalj? Taj popis je sortirano, zar ne? Vaš algoritam nije u redu, ako Vaš komentar se ne sortira se, a ipak budete koristili nešto poput binarnog pretraživanja jer možda skočiti Pravo nad elementa ne shvaćajući da je doista postoji. 

Sad što bi to značilo, veliki O jedne od njih? To ne znači da je vaš algoritma ima jedan i samo jedan korak, To samo znači da je potrebno konstanta broj koraka. Možda je to 1, možda je 10, možda je 1.000, ali to je neovisan o veličina problema. Bez obzira koliko je velika n, konstanta vrijeme algoritam Uvijek ima isti broj koraka. Dakle, ono što bi moglo biti algoritam smo razgovarali o tome ili samo intuitivno da dolazi k vama da uvijek radi u tzv stalnom vrijeme? Da? 

PUBLIKA: Dodaj dva broja. Zvučnik: Dodaj dva broja, 2 plus 2 jednako 4, učinjeno. Tako da bi mogli raditi, što drugo? Kako bi bilo više stvarnom svijetu, zar ne? 

PUBLIKA: Pronalaženje Prva stvar na popisu. Zvučnik: Pronalaženje prvi element u listi, sigurno. Mi smo zapravo razgovarali O polja već, Kako ste dobili na Prvi element u nizu, bez obzira koliko dugo Niz je u C-kod? Vi samo koristiti kao nosač nula zapis, bam, ti si tamo. I zaista, polja, što je po strani, Podrška nešto općenito poznato kao slučajni pristup, s izravnim pristupom memorije, jer možete doslovno skok na bilo kojem mjestu. Možemo to učiniti još više jednostavno možemo natrag u tjedan nula kad smo nule. Koliko vremena je trebalo za kažu blok u Scratch izvršiti? Samo konstanta vrijeme, zar ne? Reci nešto, kažu nešto, to nije važno Koliko je velika Ogrebotine svijet, to je uvijek trajat će istu količinu vremena jednostavno nešto reći. 

Dakle, to je konstanta vrijeme, ali ono što je naličje? Ako je to gornja granice, što ako želimo opisati donje granice od naših algoritama vrijeme rada? Gotovo najboljem slucaju potencijalno, ako hoćete, iako ti pojmovi mogu primijeniti na najbolji Kućišta, najgorem slučaju, prosjek slučajevi više općenito, ali neka je samo usredotočiti na donje granice općenito. Što je algoritam koji ima donju granicu od n koraka, ili 2n koraka, ili 3n koraka? Neki faktor od n koraka, To joj je donju granicu. Da? 

PUBLIKA: Bubble svojevrsni? 

Zvučnik: Bubble svojevrsni traje što minimalno n koraka, zašto? Zašto je to tako? Zašto bi to početak doći do vas intuitivno, čak ni ako to ne samo još? Da? 

PUBLIKA: [nečujan]. Govornik: Točno. U najboljem mogućem scenariju mjehurić sortirati, a puno algoritama, Ako sam ruku vam osam osoba koji već su razvrstani, bilo bi glupo za vas, algoritam, ići naprijed i natrag više od jednom, zar ne? Jer čim prošetati kroz popis jednom, trebate shvatiti, oh, ja se nisam swapovi, ovaj popis se sortira, izlaz. No, to će vas n korake poduzeti. 

A s druge strane, ono što je još jedan način razmišljanja o tome? Bubble sorta je Omega, da se tako izrazim, n, jer ako pogledate manje od n elemenata, što je temeljno pitanje postoji? Ne znam je li to razvrstani, zar ne. Mi ljudi možda pogledao osam ljudi i biti poput, oh, to je riješeno, da me n koraka nije uzeo, ali je to učinio. Tvoje oči, iako ste ljubazni od imati veliki vidno polje, ste gledali na osam elemenata, ste gledali na osam ljudi, to je osam koraka učinkovito. I samo ako sam prošetati kroz cijeli Popis ne shvaćam, da, razvrstani. Ako sam stati na pola puta razmišljam, sve U redu, to je do sada prilično razvrstani, kakvi su izgledi da nije poredani? To algoritmi neće biti točna. Mogao bi biti brži, ali netočna. 

Tako sada imamo način Opisujući nižu granicu, a što je sa stalnim vremena? Što je algoritam koji ima manji dužni na svom trajanju od jedne? 1 korak, 2 koraka, 10 koraka, ali konstanta, neovisno od N, veličina ulaz? Da, u leđima. 

PUBLIKA: printf? Zvučnika: Što je to? PUBLIKA: printf? Govornik: printf. U redu, sigurno. Dakle, to traje određeni broj koraka. I ja bi trebao now-- sada da pričamo o C kod a ne grebanje, nešto kao što je recimo, s printf, trebamo početi dobiti oprezni. Zbog printf uzima ulaz, to je niz, i gudače tehnički nemaju duljinu. Dakle, ako mi sada žele pokupiti na vas, ako vam ne smeta, tehnički možemo tvrditi da printf uzima varijabilne duljine ulaz, a sigurno bi to moglo potrajati više Vrijeme ispisati niz tako dugo, nego ovako dugo. 

Pa što ako uzmemo u obzir samo sortiranje i pretraživanje primjere? Što je Mike Smith u telefonu Knjiga ili binarno pretraživanje općenito? U najboljem slučaju, što bi se moglo dogoditi? Ja otvoriti telefonski imenik i, bam, Tu je Mike Smith broj. Ja ga mogu nazvati odmah. 

Uzeo jedan korak, možda dva koraka, ali konstantan broj koraka ako mi se posrećilo. I iskreno, vidjeli smo na Ponedjeljak vaša kolegica dobiti prilično sretan dva puta za redom. I to je doista konstantna put u donje granice na algoritam u pitanju za pronalaženje broj 50 iza onih zatvoren Vrata. 

Sada, kao što je na stranu, ako otkrijete da su i veliki O, gornja granica, i omega, donju granicu, su jedan te isti, da je ista formula zagrade, također možete kažu, samo da bude fancy, da nešto nije u theta n i nagiba neke druge vrijednosti. To samo znači kada se velika O i omega su isti. Što o odabiru vrste sad? Iskoristimo ovaj novi vokabular. U odabiru vrste, što smo radi opet, i opet, i opet? Htjela sam natrag i naprijed kroz Popis, u potrazi za koga? Najmanji broj. 

Pa koliko koraka, kako mnogi usporedbe zar ne morati učiniti kako bi se shvatiti tko najmanji element na popisu je bio? n minus 1, zar ne? Jer ako mi samo početi s koje sam dao i ja početi njega ili nju usporedbe, onda njemu ili njoj, on ili nju, njega ili nju, ja mogu samo upariti elemente zajedno n minus 1 puta. Dakle, izbor svojevrsni sličan traje n minus 1 korake prvi put. 

Koliko koraka to me odvesti naći drugi najmanji element? n minus 2, jer sam bio glup ako sam stalno gleda na istim ljudima opet, ako već sam ga odabrali ili nju, te ih staviti na svoje mjesto. I treći korak, n minus 3, a zatim n minus 4. Vidjeli smo ovaj uzorak prije, i doista Izbor svojevrsni sličan ima gornju granicu n na kvadrat, ako mi se da zbrajanja. Koja je njegova donja granica, izbor svojevrsni? Minimalno, koliko je vremena potrebno za odabir Sortiranje se, kao što smo to definirano u ponedjeljak? Predložiti dvije mogućnosti. Možda je to nje, kao i prije. Možda je n je kvadrat, što je njemu sada je kao gornja granica. 

PUBLIKA: n na kvadrat. Zvučnika: n na kvadrat. Zašto? 

PUBLIKA: Zato što imate definirati [nečujan]. 

Govornik: Točno. Barem dok sam definira odabir vrsta to je prilično naivno, zadržati ide, naći najmanji element. Idi opet, naći najmanji element. Idi opet, naći najmanji element. Nema vrsta optimizacija tamo da možda neka mi se prekinuti nakon samo n-ak koraka. Dakle, doista, izbor sortirati, omega n na kvadrat. 

Što je umetanje vrsta, gdje sam uzeo koji sam dobio, a onda sam ga ubacio ili joj na pravom mjestu? Onda sam nastavio s drugom osobom, njega ili nju ubacio na pravom mjestu. Zatim sljedeća osoba, ubacio njemu ili njoj na pravom mjestu. Uočite da je ovo vrlo linearno, da se tako izrazim. Ja sam ravna crta, ja sam ne ide natrag i naprijed, Nikad nisam gleda unatrag stvarno, ali što se događa kad sam ga umetnite ili joj se u početku Popis kao što smo učinili u ponedjeljak? Što se događa? Da? PUBLIKA: [nečujan]. Zvučnik: Da, da bio ulov, zar ne? Možda ćete se sjetiti iz Vaši kolege, ako su su stvaranje bilo koji pokret s nogama, da je operacija. Dakle, ako je bilo troje ljudi ovdje i nova osoba pripadala put tamo, na dugom pozornici kao što je ovaj, je li, on ili je ona samo može ići do samog kraja. Ali, ako razmišljamo o Računalo i niz sjećanja, ti ljudi idu imati na shuffle preko kako bi napravili mjesta za tu osobu. I tako da n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings je samo neka vrsta događa iza mene, a ne ispred mene kao i prije, u nekom smislu. Sada kao na stranu, a kao ste mogli vidjeti na internetu ako počnete čeprka po o vrste, postoji toliko različitih one vani, neki od njih bolji od drugih. Doista, bogosort jedan to je vrsta zabave potražiti. Bogosort ima niz brojevi ili kažu špil karata, slučajno ih u slučajnom, a provjerava da li oni razvrstani. A ako ne, opet nema ga. A ako ne, opet nema ga. Ako ne, opet nema ga. Nevjerojatno glupo. 

I doista, ako ste pročitali kao što je Wikipedia članak, njegov nadimak je glup neka vrsta. To će na kraju raditi, nadamo se, dati dovoljno vremena, , ali da je količina vremena mogao potrajati duže vrijeme. Dakle, ako sam mogao, ajmo ubrzati stvari gore od Mary Beth je primjer ranije, tako da još nekoliko elemenata, ali još dva procesora. Dvoje ljudi, ako vas Ne bi mi smetalo mi se pridružio. Kako oko 1 ovamo, i ajmo go-- nikoga tamo? Nitko tamo? U redu. Vi s crnom košulju, da, dođi ovamo. U redu, kako se zoveš? 

PUBLIKA: Petar. 

Zvučnika: Što je to? 

PUBLIKA: Petar. Govornik: Peter David, lijepo da zadovolji vas. U redu, imamo Petra ovdje, ako vas žele doći na stol ovamo. A kako se ti zoveš? 

PUBLIKA: Elena. Govornik: Elena. U redu, lijepo da zadovolji vas. Elena susret Petra. Petar, Elena. A mi ćemo morati Andriju Ovdje, kao i, molim te. I vaš izazov ide se razvrstati špil karata. A ako nisu upoznati, paluba kartica bi trebala u konačnici biti razvrstani malo nešto slično to gdje ćemo napraviti klubova, a zatim Pik, a zatim su srca i dijamanti, od asa kao jedan, pa sve do kralja. 

Kartice ću vam dati će biti 52 u količini. Idemo na sličan način Vrijeme vam, u samo trenutak. Idemo baciti Andriju Na zaslonu se ovdje, kako bi se gledati kao što ste to učinili. Tako da je sve to je sve više vidljiv, To su kartice dobio sam na Amazonu. Dakle, oni su već nasumično razvrstani, a mi ćemo vam vrijeme. A mi idemo u držati ga u realnom ovaj put, pa ćemo pokušati prisiliti jer bi u suprotnom to će dobiti zamorno brzo. Ako bi mogao nastaviti sortirati 52 elementi zajedno preko nekih sredstava, odmah. 

I opet, kao što smo to gledati radite što u konačnici će proizvoditi očito Rezultat, razmišljati o uistinu kako oni to rade jedni, Kako biste mogli opisati. Zbog toga ponovno su Svi procesi, algoritmi koje uzimamo zdravo za gotovo, kao čovjeka. No, vjerojatno ste dugo imali intuicija, dugo prije nego što čak i mislili o preuzimanju informatika klasa vam možda su imali intuiciju s koji je za rješavanje problema kao što je ovaj. No, nakon što prepoznaju obrasci i početi formalizirati korake s kojima ti si rješavanju tih problema, vidjet ćete da možete riješiti mnogo zanimljivije i još mnogo složeniji problemi brzo. Dakle netko iz publike, što je barem jedan element algoritma da oni koriste ovdje? 

PUBLIKA: [nečujan] Zvučnika: Što je to? PUBLIKA: Do odijelu. Zvučnik: Do odijelu. Dakle, prvo su grupiranje sve od dijamanata zajedno čini se, sve srca zajedno čini se, i tako dalje, bez poštovanja za brojeve na karticama. I sada se pojavljuju, primjerice, treba ih sortiranje po broju. Vrlo dobro. 

U redu, tako što će se biti završni korak onda ovdje? Kada imamo četiri razvrstane odijela, što trebamo učiniti na četiri pilota da bi se postigao jedan razvrstani palubu, vrlo jednostavno? Dakle, moramo ih ponovno spojiti. 

Dakle, tu je zanimljiva ideja da opet, pretpostavljam, je vrlo intuitivno i Ako ste možda nikada ne bi ošamario koja vrsta naljepnicom na njega. Ova temeljna ideja o podjeli Problem nije u pola tog vremena, ali barem na četiri dijela. Rješavanje prilično osnovi identične probleme izolacijom međusobno a zatim spajanjem rezultate. I, izvrsna, učinjeno. U redu, veliki okrugli pljesak, ako smo mogli. 

[Pljesak] 

Zvučnik: Nemam pojma što ćete učiniti s njima, ali ovdje ide. Hvala ti puno. Pa da vidimo, dvije minute i osam sekundi, Ako želite izazov svoje prijatelje. Što se onda događa da biti oduzeti to da možemo utjecati općenito? Pa, mislim natrag na ovaj niz brojeva, i prisjetim se neke od pseudocode smo zapisano u prošlosti, i to je bio pseudocode za rješavanju problema telefonskog imenika. Čime se u pseudocode I. nabrojani više metodički način opisati kako sam učinio vrlo intuitivno Ljudsko algoritam dijeljenja telefon Knjiga na pola, ponavljanje, ponavljanje, ponavljanje, dok ne nađem nekoga poput Mike Smith, ako je doista u telefonskom imeniku. 

Ali nekako se koristi ono što ću nazvati Vrlo iterativni pristup ovdje, u određenom roku linija 8 i 11 linija. Oni su dokaz iterativni pristup, petlje pristup, jer to je upravo Ponašanje koje izazivaju. Ta linija oba kažu ići Linija tri, a možete vrsta sjetiti da je u svoj mislima kao petlje. To vam govorim da se vrati do koraka tri i ponavljam opet, i opet, i opet. 

No, što ako smo iskoristiti ključnu ideju Ovdje nam nije posljednji put, i pojednostaviti linije 8 i Linija 11 i njihovi susjedi kako je upravo to, u žuto. Nije bitno skraćivanje pseudocode jako puno, ali je iz temelja se mijenja Priroda mog algoritma. Ono što sam sada rekao U koraku 7, u koraku 10, je u potrazi za Mike na isti način, ali samo u lijevo pola ili desna polovica. 

Dakle, drugim riječima, ako je Polazim od jednog koraka, pokupiti telefonski imenik, otvorena sredinom u telefonskom imeniku, pogledati imena, ako Smith je među Zove se, zovu Mike, inače ako Smith je ranije u knjizi, korak sedam tražiti Mikea u lijevoj polovici knjige. Ali ta vrsta osjeća kao to je ostavljajući me na cjedilu, zar ne? U žuto, je upute, ali kako mi je činiti tražiti Mikea u lijevo pola telefonskog imenika? Gdje moram algoritam s kojim sam možete tražiti nekoga poput Mike Smith? Pa, to je nas gleda u lice. Ja doslovno može koristiti isti Program učinkovito ide do vrha ponovno i ponovno trčanje ista linija koda. 

Dakle, iako je to trebao osjećati kao malo cikličkom definiciji gdje ste odgovoriti netko Pitanje je samo kakve pita isto pitanje opet, Na primjer, zašto, zašto, zašto? Stvarnost je, jer smo naporno smo kodirani nekoliko posebnih linija, stupanj 4, koja je, ako i korak 12, koji je učinkovito druga grana, jer imamo one hitna privremena mjera, Ovaj algoritam će raskinuti ako pronaći Mikea, ili ako to ne učinimo. No, u koraku 7 i 10. Sada imamo ono što ćemo nazvati rekurzivni algoritam. I rekurzija je doista moćan ideja to je malo um savijanje u početku, da sada možemo primijeniti na sljedeći način. 

Spoji neka vrsta će biti posljednja vrsta koja gledamo, barem u klasi formalno. A to je bitno različita od onih prošle tri, a sigurno posljednja četiri, ako uključimo bogosort. Evo pseudocode udruži- vrste. Kada je na ulazu od n elemenata, tako da s obzirom niz veličine N, ako je n manji od 2, povratak. Pa zašto moram da razum provjeriti prvi? Što je implikacija da sam na ruke niz čija duljina je n manji od 2? To je već riješeno, očito, zar ne? Zbog popis bilo je jedan element koji je trivijalno razvrstani jer je Jedino što postoji. Ili, to je od veličine nula, što znači nema ništa riješiti, pa po prirodi to je riješeno. Postoji samo postoji ništa krivo. Dakle, to je naš tzv osnovni scenarij. 

To je slično u duhu na ono što smo učinili s Mikeom. Ako Mike je u telefonskom imeniku, nazovite ga. Ako on ne postoji, odustati. To je takozvani osnovni scenarij, kako bi bili sigurni Ovaj algoritam na kraju dan zaustavit će se u određenim okolnostima. 

No, ovdje je skok vjere sada, drugo, sortirati lijevu polovicu elemenata, zatim sortirati pravo polovice elemenata a zatim spojiti sortirani polovice. I ovdje gdje se osjeća kao da smo copping van. Ja sam te pitao za sortiranje n elemenata, a ja sam govoreći, u redu, nemojte ga sortiranje napustio i sortiranje pravo. Ali ja govorim jedno druga stvar, a to je ključna tema čini u intuiciji do sada, tu je ovo treći korak spajanja. Koji iako Izgleda tako glupo u duhu, kao što je samo spojiti stvari zajedno čini biti ključan korak prema ponovno sastaviti dva problema koji podijeljeni su u konačnici na pola. 

Dakle, spajanje vrsta, učinimo to, ako ćete humor ja, s još jednom demonstracije, samo tako da imamo neke Brojevi raditi. Mogu li zamijeniti osam stres loptice za osam osoba? Dobro, o tome kako vam tri, četiri vi U ovom poglavlju, pet, šest, i neka je ne 7, 8, dođi gore. U redu, da je u redu. Minus 8, tamo idemo, plus 1. Izvrsno. Dobro došli gore, ajmo brzo vam dati brojeve. Broj dva, broj tri, broj četiri, broj pet, šest, sedam i osam. Ja sam osam ispravno ovaj put. 

U redu, pa ići naprijed ako bi mogao, i neka je vrsta u izvornom redoslijedu da smo imali jučer koja je izgledala ovako, ako ne bi smetalo. I neka je to učiniti ispred stola. U redu, tako spojiti vrsta. Ovo je mjesto gdje to ide da bi dobili kakav zanimljiv, jer čini mi se da se davanje sebe tako puno manje informacija i danas. 

Dakle, spajanje svojevrsni prije svega na ulazu od n elemenata, i očito nije manji od dva, to je osam, tako da imam više posla. Tako sada psihički smo kao klasa sada su u grani drugo, što znači tri koraka. Prvo, moram sortirati lijeva polovica elemenata. Pa kako mogu ići o događaj ovaj? Pa, ja ću vrsta mentalno podijelite popis ovdje, vi ne morate fizički kretati, a ja sam će se fokusirati samo na lijeva polovica elemenata ovdje. Pa kako ću ići oko sortiranja Popis je sada veličine četiri? Što je moj algoritam? Prvo sam provjeriti je n manji od dvije, ne, pa prešli na drugi blok ponovno. Sortiranje napustio polovicu elemenata. 

Tako sada opet, mentalno, i to je mjesto gdje morate prikupiti puno mentalno povijest, ako hoćete. Sada sam sortiranja lijevu polovica lijeve polovine. U redu, tako da sada zovem moj isti spajanje sortiranja algoritam, je n manje od dva? Ne, to je dva, pa moram sortirati lijeva polovica, a desna polovica. Dakle, ovdje mi ići, sortiranje lijevu polovicu. Zašto ne samo uzeti jedan korak naprijed. Koje je tvoje ime? 

PUBLIKA: Darren. 

Govornik: Dan. Dan je istupio. 

PUBLIKA: Darren. Govornik: Darren, učinjeno. Jeste li rekli Darren ili Dan? 

PUBLIKA: Darren. 

Govornik: Darren. U redu, Darren je stao prema naprijed, a on je sada riješeno. A to je gotovo besmisleno tvrdnja, zar ne? Ja stvarno ne izgleda da će postizanje ništa, ali idemo dalje. Sada neka mi sortirati pravo polovica elemenata. Koje je tvoje ime? 

PUBLIKA: Luka. 

Govornik: Luka. Hajde, korak naprijed. Gotovo sam razvrstani Luke. Lijeva polovica sada sortirati i desna polovica je sada riješeno, ali opet, tu je ključni korak ovdje. Što mi je pored trebate učiniti? Spoji sortirane polovice. Sada ćemo samo Svi natrag i naprijed na ovaj način, jer nekako je potrebno Neki brisani prostor. To je gotovo kao one Dečki su na stolu, i ja trebam malo mjesta kako bi ih se kretati dalje. Tako ću spojiti vi gledanjem na lijevoj polovici i desnu polovicu. A tko je očito na prvom mjestu, lijevo ili desno pola pola? Dakle, pravo na pola, pa krenimo Luka tijekom Ovdje se Darren je prvobitni položaj. A sada spojiti svoju lijevu polovicu, Darren će se premjestiti tamo. 

Tako se osjeća kao gotovo Učinak mjehurić sortirati, ali moj temeljni algoritam, vrlo različite ovaj put. No, sada je mjesto gdje se stvari malo neugodno zbog tebe moram premotati psihički gdje sam ugasiti. Upravo sam spojio razvrstanih polovice, što znači da sam gdje u mom algoritmu? Moram izdvojiti desnu polovicu, zar ne? 

Ako unatrag, doslovno Na videu, vi ćete vidim da smo došli do toga točka Luke i Darren sortiranje lijevi polovica lijeve polovine. Onda smo spojili one razvrstane polovice, koja znači sljedeći korak je vrsta Pravo polovica lijeve polovine. U redu, pa neka je to učiniti brže. U redu, šest, ja ću tvrditi Sada su razvrstani, dođi naprijed. Koje je tvoje ime? 

PUBLIKA: Adriano. 

Govornik: Adriano. Adriano je sada riješeno. A kako se ti zoveš? 

PUBLIKA: Alex. 

Zvučnik: Alex je sada riješeno. Lijeva polovica, desna polovica, što je završni korak? Spoji. Prilično trivijalna, pa sam će se stopiti u šest, uzeti jedan korak natrag, osam, uzeti jedan korak natrag. I sada primjetiti to je korisne takeaway, što sada je istina o lijevoj polovici Popis, neovisno o tome kako smo počeli? To je riješeno. 

Sada to nije razvrstani u Veliki shemi stvari, ali to je razvrstani neovisno druge polovice. Sad, što je korak sam ja o tome ako držim premotavanja kako je priča započela? Sada moram sortirati desnu polovicu. Dakle, sada smo put natrag u početak priče, i učinimo to brže. Tako ću sortiranje Pravo da polovica cijelog popisa. Što je sljedeći korak? Sortirati lijevu polovicu desnoj polovici. Sortirati lijevu polovicu lijeva polovica desnoj polovici. A kako se ti zoveš? 

PUBLIKA: Omar. 

Govornik: Omar, korak naprijed, učinjeno. Lijeva polovica sortira. A kako se ti zoveš? 

PUBLIKA: Chris. 

Govornik: Chris, uzeti jedan korak prema naprijed, sada su razvrstani. Ono što je ključni korak sad? Spoji. Dakle, jedan će se spojiti na svoje mjesto Ovdje, ako bi mogao uzeti jedan korak natrag, , a tri će uzeti jedan korak nazad, spojiti. Dakle, lijeva polovica desna polovica, sada je riješeno. Iskreno, ovaj algoritam se osjeća kao mi se troši daleko više vremena nego prije, ali ako je to učinio u stvarnom vremenu, mi ćemo vidjeti što su Zaključci će biti. Sada sam ovdje, zar ne polovica desnoj polovici, neka mi ići naprijed i sortiranje lijevu polovicu. Korak naprijed, kako se ti zoveš? PUBLIKA: Ramsey. Zvučnik: Ramsey sada riješeno. Koje je tvoje ime? 

PUBLIKA: Marina. 

Zvučnik: Marina sada razvrstani kao Pa, ako se uzme jedan korak naprijed. Ključni korak ovdje je sada spojiti, ja sam će se iščupati iz moje dvije liste, lijevo i desno. Pet će biti na prvom mjestu, i sedam će doći sljedeći. I opet, to je namjerno. Činjenica da se oni uzimati korake prema naprijed i natrag je značilo da predstavljaju da ne možemo učinite ovaj algoritam na mjestu tako lako kao mjehur vrste, i odabir vrste, i umetanje svojevrsni gdje smo upravo čuvaju zamjene ljude. Doslovno sam potrebna neka vrsta od ogrebotina rada u kojem staviti te ljude dok sam obaviti spajanje, i onda ja mogu ih vratiti na mjesto. I to je ključno, jer sam koristeći novi resurs, prostor, ne samo vrijeme. 

U redu, ovo je nevjerojatno. Lijeva polovica razvrstani, desna polovica je sortirani, sada se taj ključ spajanjem korak. Kako ću spojiti ovo? Dakle, ako ćete slijediti moj lijeva ruka i desna ruka, Ja ću istaknuti svoju lijevu ruku na lijevoj polovici, moja desna ruka Na desnoj polovici, a sada moram odlučiti korak po korak kojeg se stapaju u. Tko očito dolazi prvo? Broj jedan. Pa hajde ovamo, ovdje je naš notes. Tako je sada broj jedan, i obavijest Što ću učiniti s moje desne strane, Idem da se presele desnoj ruci jedan korak više do točke broj tri, i sad moram napraviti Istom odlukom. I zapravo stoje pravo u Prednji dio Luke ovdje ako bi mogao, jer ovo je naša notes. Dakle, tko dolazi sljedeći? Imamo Luka s brojem dva ili Chris s brojem tri. Očito Luka, broj dva, tako da ovdje dolaze. 

Ali mi je lijeva ruka sada će povećavati do točke na Darren, i ovdje je ključno oduzima s spajanjem, idem da bi to, Očito, ako ste ljubazni od slijede logiku. No ruke su mi nikada ići unatrag, što znači da sam samo ikada kreće se napustio s mojim pretapajuĘem procesa, a to će biti ključ Naša analiza u samo trenutak. 

Dakle, sada ćemo završiti ovo vrlo brzo. Dakle, tri dolazi sljedeći, zatim četiri dolazi sljedeći, a sada pet dolazi sljedeći, a zatim šest, i sedam godina, a onda je konačno osam. Osjeća kao najsporijim algoritma još uvijek, ali ne i ako smo zapravo pokrenuti ga na istoj vrsti brzine sata, tako da se govoriti, s istom otkucava sat kao i prije. Zašto? Pa, neka je uzme pogled na krajnji rezultat. 

Vratimo se ovamo, neka me podići demonstraciju vizualno onoga što smo upravo učinili. Povećavanje ovdje, na ovom Stranica ovdje, govori Firefox da želimo stati u red u tom okviru, ajmo kažu mjehurić vrsta, s kojom mi smo sada dobro poznato, Izbor sortirati, što je još jedan prilično jednostavan jedan, a sada današnja spajanje sorta, koja će biti naš vrhunac kraj. Razlog je to što je toliko mnogo dulje ovdje s ljudima i ja verbalno je, Očito, ja sam objašnjavajući svaki korak. Ali ako jednostavno izvršiti to, mnogo kao što smo učinili mjehur sortiranje i odabir Sortiranje ne samo vizualno, sat koliko učinkovitije to Utjecati od podjela i osvajanje može kad se odnosi na skupu koji je Nije čak veličine osam, ali čak i mnogo, puno veći. Dajem vam spojiti sortirati, rame uz strana s tim drugim sredinama. To se događa da se bolno brzo, a završetak nije osobito vrhunac, oni samo završiti razvrstani. No, ključno je da se oduzima Vidi kako je mnogo brže spajanje svojevrsni bio je, osim ako ne mislite da sam samo vrsta petljaju s vama. Ako smo to učinili posljednji put, Idemo Reload this, idemo natrag i odaberite balon vrsta, i samo za slatkiš, ajmo birati umetanje sortirati, samo za dobru mjeru. I ovaj put opet, ajmo odaberite spajanja vrsta i neka zapravo pokrenuti ove rame uz rame. 

I to nije, zapravo, slučajnost. Ono što sam uspješno učinio je da sam podijeljeni moj ulaz na pola, opet, i opet, i opet. I tu je samo toliko puta možete podijeliti svoj ulaz na polovice, lijevo i desno. Koja je formula koja držimo gledajući koji opisuje podjelu na pola opet, i opet, i opet, i opet? 

PUBLIKA: Prijavite n. 

Zvučnik: Prijavite n. Ali tu je još jedna ključni korak, Ovaj algoritam nije prijavite n koraka. Ako to su samo prijavite n koraka, mi bi se u istom problemu kao i prije, gdje ne možemo biti uvjerim da je sve riješeno. Morate minimalno pogledati n elemenata kako bi bili sigurni n elementi su razvrstani, inače je skok vjere. 

Dakle, to je minimalno dnevnik n koraka, ali Što je s tom ključnom pretapajuĘem korak gdje sam spojio moje lijeve i desne polovice polovice i hodao po pozornici? Koliko koraka je da se spojiti? To je n, ali nisam baš spojiti posljednji put. Na svakom od tih ugniježđena poziva, na svakoj od onih ugniježđena spaja, ja još uvijek razvrstani. Spojio sam ove dvije dečki, onda ova dva Dečki, a zatim su dvojica i tako dalje. 

Pa nisam spajanjem opet, i opet. Koliko puta? Dakle, svaki put kad bih podijeliti Popis na pola, ja sam pisma. Podijeljeno je popis na pola, napraviti spajanje. Dakle, ako dijeljenjem popis može biti učinjeno dnevnik n puta, i spajanje u konačnici vodi n koraka, što bi moglo biti sad gornja vezan na trčanje Vrijeme našeg algoritma? n log n. 

I doista, to je ono što ostvarili smo ovdje. Dakle, mislite da ste vidjeli vizualno kada te tri stvari pokrenuti rame uz rame je n kvadrat protiv n kvadrat od n log n. Koji je bitno vidjet ćemo, ne samo danas, ali u budućnosti, je puno, puno brže. Pljesak za ove dečke, Ja ću ih nagraditi sa stresom loptice. Idemo odgodi danas ovdje, a mi ćemo vas vidjeti u ponedjeljak.