>> [Muzikavimo]
Davidas Malan: Gerai.
Gerai, pasveikinti atgal.
Taigi tai yra 4 savaitė, pradžia jo, jau.
Ir jums priminti, kad praėjusią savaitę, mes įdėti kodą skirta tik šiek tiek
ir mes pradėjome kalbėti šiek tiek daugiau aukšto lygio, apie tokius dalykus kaip
paieškos ir rūšiavimo, kuris nors šiek tiek paprastų idėjų, yra
atstovas problemų klasei jūs pradėsite spręsti ypač
kaip jums pradėti galvoti apie galutinį projektai ir įdomių sprendimų jūs
gali tekti realaus pasaulio problemas.
Dabar burbulas tarsi buvo vienas iš paprasčiausių tokie algoritmai, ir tai
dirbo turėdami šiuos mažus numerius sąraše arba masyvo rūšies
burbulas savo kelią į viršų, ir didelis skaičius perkelti savo kelią žemyn
Šio sąrašo pabaigoje.
>> Ir priminti, kad mes galime vizualizuoti burbulas rūšiuoti mažai
kažkas panašaus į tai.
Taigi leiskite man eiti į priekį ir spustelėkite Pradėti.
Aš iš anksto pasirinkti burbulas rūšiuoti.
Ir jei jūs prisimenate, kad aukštesni mėlyna linijos sudaro didelis skaičius, mažas
mėlynos linijos sudaro nedidelis skaičius, kaip mes pereiti per tai vėl ir vėl, ir
vėl, lyginant dvi juostas viena šalia kitas raudonai, mes ketiname apsikeitimo
didžiausias ir mažiausias jei jie yra ne iš eilės.
>> Taigi, tai bus eiti ir eiti ir eiti įjungtas, ir jūs pamatysite, kad didesnis
elementai yra padaryti savo kelią į sugebėjimus ir mažesni elementai
padaryti savo kelią į kairę.
Bet mes pradėjo kiekybiškai efektyvumas,
kokybė šį algoritmą.
Ir mes pasakėme, kad blogiausia atveju šis algoritmas buvo
maždaug kiek žingsnių?
>> Taigi n kvadratu.
Ir tai, kas buvo n?
>> Auditorija: Elementų skaičius.
>> Davidas Malan: Taigi n buvo skaičius elementų.
Ir taip mes padarysime tai dažnai.
Bet kuriuo metu mes norime kalbėti apie dydį problema arba dydžio
įėjimas, arba kiek laiko užtrunka gaminti produkciją, mes tiesiog
apibendrintas kokia indėlis yra kaip n.
Taigi atgal į savaitę 0, skaičius puslapiai telefonų knygoje buvo n.
Studentų skaičius patalpoje buvo n.
Taigi čia taip pat, mes po kad modelis.
>> Dabar n kvadratu ne itin greitai, todėl mes bandėme padaryti geriau.
Ir taip mes pažvelgė porą kiti algoritmai, tarp kurių
buvo pasirinkimas rūšiuoti.
Taigi atranka tarsi buvo šiek tiek kitoks.
Tai buvo beveik paprasčiau, drįstu pasakyti, kai aš pradėjau prie pradžios
sąrašas iš mūsų savanorių, ir aš tiesiog dar kartą ir vėl ir vėl išgyveno
sąrašas, skynimas iš mažiausių elementas metu ir išleisti jį arba
ją prie sąrašo pradžioje.
>> Tačiau tai taip pat, kai mes pradėjome galvoti per matematikos ir didesnio
paveikslėlį, pagalvojau apie tai, kiek kartų Aš buvau ketinate pirmyn ir atgal ir atgal
ir atgal, mes pasakėme, blogiausiu atveju, pasirinkimas rūšiuoti, taip pat buvo ką?
n kvadratu.
Dabar realiame pasaulyje, ji gali iš tikrųjų šiek tiek greičiau.
Nes vėl, aš neturėjau išlaikyti atsitraukia kartą aš surūšiuoti
smulkiausi elementai.
Bet jei mes galvojame apie labai didelis n ir jei tarsi daryti iš matematikos kaip
Aš ant lentos, su n kvadratu atėmus kažkas, visa kita
be to, n kvadratu, kartą n bus tikrai didelis, nėra
tikrai nesvarbu kiek.
Taigi, kaip kompiuterių specialistų, mes rūšiuoti užmerkti akis į mažesnius
veiksniai ir sutelkti dėmesį tik į veiksnys išraiška, kuri ketina padaryti
Didžiausias skirtumas.
>> Na, galiausiai, mes pažvelgė ne įterpimo rūšiuoti.
Ir tai nuotaika buvo panaši į, bet o ne eiti per keletą kartų ir
pasirinkite mažiausią elementą vieną kartą, aš vietoj paėmė ranką, kad aš
buvo nagrinėjamas, ir aš nusprendžiau, visi Gerai, jūs priklausote čia.
Tada aš persikėlė į kitą elementą ir nusprendė, kad jis arba
ji priklausė čia.
Ir tada aš persikėlė ir.
Ir aš gali tam, pakeliui, perkelti šie vaikinai siekiant
padaryti vietos jiems.
Taigi, tai buvo tarsi psichikos atstatymo Atrankos rūšiuoti, kad mes
vadinama įterpimo rūšiuoti.
>> Taigi šios temos pasitaiko realiame pasaulyje.
Vos prieš kelerius metus, kai tam tikros senatorius buvo paleisti į prezidentus,
Ericas Schmidtas, tuo metu, kai generalinis direktorius "Google", iš tikrųjų turėjo galimybę
apklausti jį.
Ir mes manome, kad mes norime pasidalinti šia YouTube klipas jums čia, jei galėtume riesti
apimtis.
>> [VIDEO PLAYBACK]
>> -Dabar, senatorius, jūs čia "Google" ir man patinka galvoti apie pirmininkavimo
kaip darbo interviu.
>> [Juokas]
>> -Dabar tai sunku gauti kaip prezidentas darbas.
Ir jūs ketinate per sąstingis dabar.
Taip pat sunku gauti "Google" darbą.
Mes turime klausimus ir mes klausiame mūsų kandidatai klausimai.
Ir tai vienas iš Larry Schwimmer.
>> [Juokas]
-Vaikinai manau, kad aš juokauju?
Tai čia.
Kas yra efektyviausias būdas rūšiuoti milijono dviejų bitų sveikųjų skaičių?
>> [Juokas]
>> -Na, na -
>> -I 'm sorry.
Gal mes turėtume -
>> -Ne, ne, ne, ne, ne.
>> -Tai ne -
Gerai.
>> -Manau, kad burbulas tarsi būtų būti neteisingas kelias.
>> [Juokas]
>> [Giedras ir plojimai]
>> -Nagi, kas jam šį?
Gerai.
>> [PABAIGA VIDEO PLAYBACK]
>> Davidas Malan: Taigi jūs turite jį.
Taigi mes pradėjome kiekybiškai tai veikia kartų, taip sakant, su kažkuo
vadinamas asymptotic žymėjimas, kuris yra tik nuoroda į mūsų rūšies tekinimo
aklas akis tiems mažesnių veiksnių ir tik žiūri į važiavimo laikas,
Šių algoritmų efektyvumą, kaip n bus tikrai didelis laikui bėgant.
Ir taip mes pristatėme didelis O. ir didelis O atstovaujama kažkas, kad mes manome, kad
AS viršutinė riba.
Ir iš tiesų, Barry, mes galime sumažinti nei mikrofono truputį?
>> Manėme, kad tai yra viršutinė riba.
Taigi didelis O nuo n kvadratu, reiškia, kad Blogiausiu atveju, kažkas panašaus
pasirinkimas rūšiuoti užtruktų n kvadratu veiksmus.
Ar kažkas panašaus įterpimo rūšiuoti būtų n kvadratu žingsniai.
Dabar kažką panašaus budas rūšiuoti, kas blogiausiu atveju?
Atsižvelgiant į tai, masyvas, kas blogiausia galimas scenarijus, kad jūs galite rasti
sau susiduria su?
>> Tai visiškai atgal, tiesa?
Nes jei tai visiškai atgal, jūs turite padaryti visai daug darbo.
Nes jei jūs esate visiškai atgal, jūs ketinate rasti
didžiausias elementas čia, nors ji priklauso ten.
Taigi jūs ketinate pasakyti, gerai, bent tai laiko momentas, jūs priklausote čia
todėl jūs palikti jį ramybėje.
>> Tada jūs suprasite, oh, velnias, ir aš turiu perkelti šį šiek tiek mažesnis elementas
jus į kairę.
Tada aš turiu daryti, kad vėl ir vėl ir vėl.
Ir jei aš vaikščiojo pirmyn ir atgal, jūs būtų tarsi jaučia veikimą
kad algoritmas, nes nuolat esu shuffling visi kiti žemyn
masyvas, kad paliktume jį.
Štai blogiausiu atveju.
>> Priešingai -
ir tai buvo Įspūdingos filmą paskutinį kartą -
sakėme, kad įterpimo rūšiuoti buvo, ką Omega?
Kas geriausiu atveju veikia laikas įterpimo rūšiuoti?
Taigi, tai tikrai n.
Tai buvo tuščias, kad mes palikome ant lentos paskutinį kartą.
>> Ir tai omega n, nes kodėl?
Na, labai geriausiu atveju kas įterpimo rūšiuoti bus įteiktas?
Na, sąrašas, kurį visiškai rūšiuojami jau minimalus darbo padaryti.
Bet kas, tvarkingas apie įterpimo rūšiuoti yra tas, kad jis prasideda čia ir
nusprendžia, oi, jūs numeris viena, jūs priklausote čia.
O, kas laimės.
>> Jūs numeris du.
Jūs taip pat priklauso šiai.
Numeris trys, dar geriau, Jūs priklausote čia.
Kai tik jis gauna į pabaigos sąrašas, už įterpimo Rūšiuoti anketa Pseudocode
kad mes vaikščioti per žodžiu paskutinį kartą, tai daroma.
Bet pasirinkimas rūšiuoti, priešingai, nuolat tai daryti, ką?
>> Nuolat vyksta per sąrašą vėl ir vėl ir vėl.
Kadangi pagrindinė įžvalga buvo tik kai jūs pažvelgė visą kelią iki
pabaigoje sąrašo galite būti tikri, kad elementas pasirinkote buvo
Iš tiesų šiuo metu mažiausias elementas.
Taigi tai skiriasi psichikos modeliai pabaiga iki duoda keletą labai realaus pasaulio
skirtumai mums, taip pat šių teoriniai asimptotiniai skirtumai.
>> Taigi tiesiog Priminti tada, Didelės O n langeliais, mes matėme keletą tokių
algoritmai iki šiol.
Didelės O n?
Kas yra algoritmas, kuris galėtų būti laikomas didelis O n?
Blogiausiu atveju, ji trunka linijinis pakopų skaičius.
>> Gerai, linijiniai paieška.
O blogiausiu atveju, jei yra elementas jūs ieškote, kai
taikant linijinį ieškoti?
>> Gerai, blogiausiu atveju, tai net ne ten.
Arba antrąja blogiausiu atveju, tai visi galų gale būdas, kuris yra
plius ar minus-vienas žingsnis skirtumas.
Tad dienos pabaigoje, mes galime pasakyti, kad linijinė.
Didelės O n būtų tiesinis paieška, nes blogiausiu atveju,
elementas net ne ten, ar tai visi pabaigoje būdas.
>> Na, didelis O iš žurnalo n.
Mes ne kalbėti labai išsamiai apie tai, bet mes matėme anksčiau.
Ką veikia vadinamasis logaritminė laikas, blogiausiu atveju?
>> Taip, taip, dvejetainis paieškos.
Ir dvejetainis paieškos blogiausiu atveju gali turėti elementą kažkur
viduryje, ar kažkur viduje masyvo.
Bet jūs tik rasti jį, kai jūs padalinti sąrašą per pusę, į
pusė, per pusę, per pusę.
Ir tada voila, tai ten.
Arba vėl, blogiausiu atveju, tai net ne ten.
Bet jūs nežinote, kad jo ten nėra kol tarsi pasiekti, kad paskutinis
apačios dauguma elementų perpus ir perpus ir perpus.
>> Didelės O 1.
Taigi, mes galime didelis O 2, didelis O 3.
Anytime norite tik pastovų skaičių, mes tiesiog rūšiuoti tik supaprastinti
kad didelis O 1.
Nors jei realiai, tai trunka 2 ar net 100 laiptelius, jei tai
pastovus pakopų skaičius, mes tiesiog pasakyti didelis O 1.
Kas yra algoritmas, kuris yra didelių O 1?
>> PUBLIKA: Ieškoti ilgį iš kintamąjį.
>> Davidas Malan: Ieškoti ilgis kintamasis?
>> Auditorija: Ne, ilgis jei jis jau rūšiuojamos.
>> Davidas Malan: Geras.
Gerai, kad rasti kažką ilgis jei tos kažką ilgis, kaip
masyvas, yra saugomi tam tikru kintamuoju.
Kadangi jūs galite tik skaityti kintamąjį, arba spausdinti kintamąjį, arba
tiesiog paprastai gauti tą kintamąjį.
Ir voila, kad mano pastovus laiką.
>> Priešingai, manau, į nulio.
Prisiminkite pirmą savaitę C skambinti tik printf ir spausdinimas
kažkas ekrane yra neabejotinai pastovus laikas, nes ji tik mano
kai procesoriaus ciklų skaičius, kurį rodo kad ekrane tekstą.
Arba laukti - Ar ji?
Kaip kitaip galėtume modeliuoti atlikimas printf?
Ar kas nors norėtų nesutikti, kad gal tai tikrai ne pastovus laikas?
Kokia prasme gali printf bėga laikas, iš tikrųjų spausdinimo juostelė
ekranas, būti kažkas išskyrus pastovus.
>> Auditorija: [nesigirdi].
>> Davidas Malan: Taip.
Taigi tai priklauso nuo mūsų perspektyvos.
Jei mes iš tikrųjų galvoti apie indėlio printf kaip eilutę, ir
Todėl mes įvertinti, kad dydis įėjimas jo ilgis - todėl galime skambinti
kad ilgis n, taip pat -
be abejo, printf pati Didelės O n nes jis ketina imtis jums n žingsnius
spausdinti kiekvieną iš tų n ženklai, greičiausiai.
Bent tiek, kad mes manome, kad gal tai naudojant už kilpos
po gaubtu.
>> Bet mes turime pažvelgti, kad Kodas Norėdami suprasti geriau.
Ir iš tiesų, kai vaikinai pradeda analizuoti savo algoritmus, jums
tiesiog padaryti tik tai.
Rūšiuoti akies obuolio jūsų kodas ir manau, apie - viskas gerai, aš turiu šį kilpa
čia arba aš turiu įdėtos kilpos čia tai ketinate daryti n dalykų n kartų,
ir jūs galite rūšiuoti priežasties savo kelią per kodą, net jei tai
Pseudocode, o ne tikrasis kodas.
>> Taigi, ką apie omega n kvadratu?
Koks buvo algoritmas, kad geriausias atveju, vis dar buvo n kvadratu žingsniai?
Taip?
>> Auditorija: [nesigirdi].
>> Davidas Malan: Taigi pasirinkimas rūšiuoti.
Kadangi šios problemos realiai sumažėtų į tai, kad vėl, aš nežinau,
Radau dabartinė mažiausių iki Aš patikrinti visus prakeiktus elementai.
Taigi, omega, tarkim, n, mes tiesiog atėjo su vienu.
Įtraukiama rūšiuoti.
Jei sąrašas atsitinka būti rūšiuojami jau, geriausiu atveju mes tiesiog
padaryti vieną praeiti pro jį, tuo momentu mes tikrai.
Ir tada, kad galima teigti, yra linijinė, tikrai.
>> Ką apie omega 1?
Kas, geriausiu atveju, gali trukti pastovus pakopų skaičius?
Taigi linijinis paieškos, jei jūs tiesiog gauti pasisekė ir elementas jūs ieškote
yra į dešinę nuo sąrašo pradžios, jei tai, kur jūs pradedate savo
linijinis Sankryþos šio sąrašo.
>> Ir tai yra tiesa numeris dalykų.
Pavyzdžiui, net dvejetainis paieška omega 1.
Nes ką daryti, jei jums tikrai adyti pasisekė ir pliaukštelėti-DAB viduryje
Jūsų masyvas skaičius jūs ieškote?
Taigi jūs galite gauti pasisekė ten, taip pat.
>> Tai vienas, galiausiai, omega n log n.
Taigi n log n, mes nelabai kalbėti apie dar, bet -
>> Auditorija: Sujungti rūšiuoti?
>> Davidas Malan: suliejimas rūšiuoti.
Tai buvo paskutinį kartą Įspūdingos filmą, kur mes pasiūlėme, o mes parodėme
vizualiai, kad yra algoritmai.
Ir sujungti tarsi tik vienas toks algoritmas, kuris iš esmės yra greičiau
nei kai kurie iš šių kitų vaikinų.
Tiesą sakant, sujungti trumpas yra ne tik geriausiu atveju n log n, blogiausiu
Byla N log n.
Ir kai jūs turite šį sutapimas Omega ir didelis O yra tas pats?
Mes iš tikrųjų gali apibūdinti, kad tai, kas vadinama teta, nors tai
šiek tiek rečiau.
Bet tai tik reiškia, dvi ribas, šiuo atveju yra tas pats.
>> Taigi sujungti rūšiuoti, ką tai tikrai skliautais mums?
Na, prisimenu motyvaciją.
Leiskite traukti dar vieną animaciją, kad mes ne pažvelgti paskutinį kartą.
Tai vienas, pati idėja, tačiau tai šiek tiek didesnis.
Ir aš ruošiuosi eiti į priekį ir pabrėžti Pirmasis - mes turime įterpimo rūšiuoti
viršuje, kairėje, tada pasirinkimas rūšiuoti, burbulas rūšiuoti, kitų rūšių pora -
korpuso ir greitai - kad mes ne kalbėjo apie, ir krūva ir sujungti rūšiuoti.
>> Taigi, bent pabandyti sutelkti savo akis trijų geriausių į kairę, tada į
sujungti rūšiuoti, kai aš spustelėkite tai žalia rodyklė.
Bet aš tegul juos visus paleisti, tiesiog jums įvairovę jausmą,
algoritmai, kurie egzistuoja pasaulyje.
Aš ruošiuosi leisti Šios įsibėgėjimo vos kelias sekundes.
Ir jei jums sutelkti savo akis - pasirinkti algoritmas, sutelkti dėmesį į jį tik
s - jums pradėti rodyti modelis, kad tai įgyvendinti.
>> Sujungti rūšiuoti, pranešime, yra padaryta.
Heap rūšiuoti, greitai rūšiuoti, kriauklių -
todėl atrodo, kad mes pristatė tris blogiausia algoritmai praėjusią savaitę.
Bet tai gerai, kad mes čia šiandien pažvelgti suliejimo rūšiuoti, kuris yra vienas iš
tuo lengviau tie yra pažvelgti, net nors ji tikriausiai bus lenkimo jūsų protas
tik truputį.
Čia mes matome, kiek daug pasirinkimas rūšiuoti sucks.
>> Tačiau atvirkštinė pusė, tai tikrai lengva įgyvendinti.
Ir gal P Set 3, tai viena iš algoritmai Jūs pasirinkote įgyvendinti
už standartinę versiją.
Puikiai gerai, puikiai teisinga.
>> Bet vėl, kaip n tampa didelis, jei nuspręsti įgyvendinti greičiau algoritmą
kaip sujungti rūšiuoti, šansai yra didesni ir Didesnės sąnaudos, jūsų kodas yra tik
ketina paleisti greičiau.
Jūsų svetainė ketina dirbti geriau.
Jūsų vartotojai bus laimingesni.
Ir taip yra šie poveikiai faktiškai suteikiant
mums kai giliau minties.
>> Taigi galime pažvelgti, kas sujungti išvaizdą rūšiuoti yra iš tikrųjų visi apie.
The cool dalykas yra tai, kad sujungti rūšiuoti yra tik tai.
Tai, vėlgi, ką mes vadinami Pseudocode, Pseudocode būtybė
Lietuvių-kaip sintaksė.
Ir paprastumas yra rūšiuoti įspūdingi.
>> Taigi ant įvesties n elementų - taip, kad tiesiog reiškia, štai masyvas.
Jis gavo n dalykų į jį.
Tai viskas, ką sakote ten.
>> Jei n yra mažesnis nei 2, grįžti.
Taigi, tai tik nereikšmingas atvejis.
Jei n yra mažesnis nei 2, tada, žinoma, ji yra 1 arba 0, tokiu atveju dalykas
jau surūšiuotus arba neegzistuoja, tad tiesiog grįžti.
Nėra nieko daryti.
Štai paprastas bylą roviau.
>> Kitur, mes turime tris veiksmus.
Rūšiuoti kairėje pusėje, elementų, rūšiavimo Dešinė pusė iš elementų,
ir tada sujungti surūšiuoti puses.
Kas įdomu, kad čia yra Aš tipo punting, tiesa?
Yra rūšies apskrito apibrėžimo šį algoritmą.
Kokia prasme tai algoritmo raiškos apskritas?
>> Auditorija: [nesigirdi].
>> Davidas Malan: Taip, mano rūšiavimo algoritmas, du jos žingsniai yra "rūšiuoti
kažkas. "Ir taip, kad kyla klausimas, gerai, ką aš ketinate naudoti
rūšiuoti kairę pusę ir į dešinę pusę?
Ir grožis čia yra tai, kad nors Vėlgi, tai yra proto-lenkimo
dalis potencialiai, galite naudoti tą patį algoritmas rūšiuoti kairę pusę.
>> Bet palauk.
Kai jūs pasakojo rūšiuoti kairė pusė, kas yra du
veiksmai bus toliau?
Mes rūšiuoti kairę pusę kairėje pusėje, ir dešinėje
pusė kairėje pusėje.
Velnias, kaip man sutvarkyti tuos du pusės arba ketvirčiai, o dabar?
>> Bet tai gerai.
Mes turime rūšiavimo algoritmą čia.
Ir nors jums gali nerimauti ne pirmas tai rūšies begalinis
kilpa, tai ciklas, kad niekada ketina baigti - ji ketina
baigsis tada, kai kas atsitiks?
Kai n yra mažiau nei 2.
Kuris galiausiai nutiks, nes jei jūs nuolat perpus sumažinti ir
perpus sumažinti per pusę sumažinti šias puses, be abejo, galų gale jūs ketinate baigti
iki vos 1 arba 0 elementus.
Kuriuo šis algoritmas sako viskas.
>> Taigi reali magija tai algoritmas atrodo,
kad galutinis žingsnis, sujungimo.
Tai paprasta idėja tiesiog sujungti du dalykų, tai, kas galiausiai bus
leisti mums rūšiuoti masyvas, tarkim, aštuonis elementus.
Taigi turiu aštuonis daugiau streso kamuoliukus iki čia aštuonių popieriaus lapų, ir vienas
"Google" Stiklas -
kuris man išsaugoti.
>> [Juokas]
>> Davidas Malan: Jei mes galime imtis aštuonių savanoriai, ir pažiūrėkime, jei mes galime
žaisti šį, ir todėl.
Oho, Gerai.
Kompiuterių mokslas vis įdomus.
Gerai.
Taigi, kaip apie jus tris, Didžiausias ranka ten.
Keturi iš nugaros.
Ir kaip apie mes padarysime jus trys šios eilutės?
Ant priekinės keturis.
Taigi jūs aštuoneri, ateiti iki.
>> [Juokas]
>> Davidas Malan: Aš iš tikrųjų nežinote, kas tai yra.
Ar tai stresas kamuoliukai?
Stalo lempos?
Medžiaga?
Interneto?
>> Gerai.
Taigi atėjo iki.
Kas norėtų -
nuolat artėja.
Pažiūrėkime.
Ir tai kelia jums vietoje -
esate vietoje vienos.
Uh-Oh, wait a minute.
1, 2, 3, 4, 5, 6, 7 - O, gerai.
Gerai, mes geri.
Gerai, kad kiekvienas turi savo vietą, bet ne "Google" stiklo.
Leiskite man į eilę Šie padidintos.
Koks tavo vardas?
>> MICHELLE: Michelle.
>> Davidas Malan: Michelle?
Gerai, jums atrodys Geek, jei tai Gerai.
Na, aš taip pat manau, tik akimirką.
Viskas gerai, laukimo.
Mes jau bando sugalvoti naudojimo atveju "Google Stiklas ir mes
maniau, kad būtų smagu tiesiog tai, kai žmonės ant scenos.
Mes įrašysime pasaulį iš savo perspektyvos.
Gerai.
Ne tikriausiai, ką "Google paskirtį.
Gerai, jei jūs neprieštaraujate dėvėti ir ateinančius nepatogios minučių,
kad būtų nuostabu.
>> Gerai, kad mes turime čia masyvas elementai, ir kad masyvo, pagal
popieriaus gabaliukų šių žmonių " rankas, šiuo metu nerūšiuotos.
>> MICHELLE: O, kad taip keistai.
>> Davidas Malan: Tai gana daug atsitiktinai.
Ir tik akimirką, mes ketiname bandyti įgyvendinti sujungti rūšiuoti kartu
ir pamatyti, kur tas raktas įžvalga.
Ir triukas čia suliejimo rūšiuoti yra kažkas, kad mes ne prielaida dar.
Mes iš tikrųjų reikia šiek tiek papildomos vietos.
Taigi, kas bus ypač įdomu tai, kad šie
vaikinai ketinate judėti mažai tiek, nes aš ruošiuosi daryti prielaidą, kad
ten papildomai masyvas erdvėje, pasakyti, tiesiai už jų.
>> Taigi, jei jie už savo kėdę, tai antrinė masyvo.
Jei jie sėdi čia, tai pagrindinis masyvo.
Bet tai išteklių, kad mes turime nenaudoja finansinio sverto iki šiol su burbulas
rūšiuoti, su atrankos rūšiuoti, su prierašu rūšiuoti.
Prisiminkite, praeitą savaitę, visi tik rūšies išmaišytos vietoje.
Jie nebuvo naudoti bet kokią papildomą atmintį.
Mes padarėme vietos žmones judančių žmonių aplink.
>> Taigi tai yra pagrindinis įžvalgos, taip pat.
Yra tai kompromisas, apskritai į kompiuterių mokslas, išteklius.
Jei norite pagreitinti kažką kaip laiko, jūs ketinate
turi mokėti kainą.
Ir vienas iš šių kainų yra labai dažnai erdvė, atminties kiekis ar sunku
diske, kad jūs naudojate.
Arba, tiesą sakant, suma programuotojas metu.
Kiek laiko užtrunka jums, žmogaus, realiai įgyvendinti šiek tiek daugiau
sudėtingas algoritmas.
Bet šiandien, kompromisas yra laikas ir erdvė.
>> Taigi, jei jus vaikinai gali tiesiog telpa jūsų numerius, mes galime pamatyti, kad esate
iš tiesų suderinti 4, 2, 6, 1, 3, 7, 8.
Puikus.
Taigi, aš ruošiuosi pabandyti muzikinės dalykų, jei jus vaikinai gali tik
sekti mano pavyzdžiu čia.
>> Taigi, aš ketina įgyvendinti, visų pirma, Pirmasis žingsnis pseudocode, kuris yra
į įvesties n elementų, jei n mažiau nei 2, tada grįžti.
Akivaizdu, kad nėra taikoma, todėl mes judėti pirmyn.
Taigi rūšiuoti kairėje pusėje, elementai.
Taigi, tai reiškia aš norėčiau sutelkti dėmesį mano dėmesys tik į tai metu
Keturi vaikinai čia.
Viskas gerai, ką aš kitą daryti?
>> Auditorija: Rūšiuoti kairę pusę.
>> Davidas Malan: Taigi, dabar turiu sutvarkyti kairė pusė šių vaikinai.
Nes vėl prisiimti sau į tikslas rūšiuoti kairę pusę.
Kaip tai padaryti?
Tiesiog sekite instrukcijas, net nors mes darome jį dar kartą.
Taigi rūšiuoti kairę pusę.
Dabar aš rūšiavimo šiuos du vaikinai.
Kas toliau?
>> Auditorija: Rūšiuoti kairę pusę.
>> Davidas Malan: Rūšiuoti kairę pusę.
Taigi, dabar jų, ši vieta čia yra 1 dydžio sąrašą.
Ir kas tavo vardas?
>> PRINCESS DAISY: princesė Daisy.
>> Davidas Malan: princesė Daisy yra čia.
Ir taip ji jau rūšiuojamos, nes sąrašas dydžio 1.
Ką man kitą daryti?
Gerai, negrąžinti, nes šis sąrašas yra 1 dydis, kuris yra mažiau nei 2.
Tada kas sekantis žingsnis?
Ir dabar jūs turite rūšies Atsitraukia savo mintis.
>> Rūšiuoti teisingą pusę, kuri yra -
koks tavo vardas?
>> LINDA: Linda.
>> Davidas Malan: Linda.
Ir taip, tai ką mes darome dabar, turime 1 dydžio sąrašą?
>> Auditorija: Atgal.
>> Davidas Malan: Atsargiai.
Mes vėl pirmas, o dabar trečioji žingsnis - ir jei aš tipo vaizduoti jį
apimantis dvi vietas dabar, dabar aš turi sujungti šiuos du elementus.
Taigi, dabar, deja, elementai yra ne iš eilės.
Bet tai kur sujungimo procesas pradeda gauti įtikinamos.
>> Taigi, jei jus vaikinai gali atsistoti tik momentas, aš ruošiuosi reikia tavęs, kad
momentas, stiprindamas už savo kėdės.
O jei Linda, nes 2 yra mažesnis nei 4, kodėl gi ne
Jūs ateiti aplink pirmas?
Ten pasilikti.
Taigi Linda, jūs ateiti aplink pirmas.
>> Dabar iš tikrųjų jei tai tik matrica mes galime tiesiog perkelti ją realiu laiku
iš šios kėdės šioje vietoje.
Taigi, įsivaizduokite, kad paėmė pastovus pakopų skaičius 1.
O dabar -
bet mes turime padėti jums pirmoji vieta čia.
>> Ir dabar, jei gali ateiti aplink, kaip gerai, kad mes ketiname
būti vietoje dviejų.
Ir nors tai jaučiasi tai atsižvelgiant į laiką, kas malonu dabar
kad kairė pusė kairėje pusėje, dabar rūšiuojamos.
Taigi, kas buvo kitas žingsnis, jei mes dabar atgal toliau į istoriją?
>> Auditorija: Dešinė pusė.
>> Davidas Malan: Rūšiuoti tinkamą pusę.
Taigi jus vaikinai tai padaryti, taip pat.
Taigi, jei galite atsistoti tik akimirką?
Ir kas yra jūsų vardas?
>> JESS: Jess.
>> Davidas Malan: Jess.
Gerai, kad Jess dabar į kairę pusę dešinėje pusėje.
Ir taip ji dydžio 1 sąrašas.
Ji akivaizdžiai surūšiuoti.
Ir tavo vardas?
>> MICHELLE: Michelle.
>> Davidas Malan: Michelle akivaizdžiai dydžio 1 sąrašas.
Ji jau sutvarkyti.
Taigi dabar magija atsitiks, jungimosi procesą.
Taigi, kas vyksta atėjai, pirmas?
Akivaizdu Michelle.
Taigi, jei galite ateiti aplink atgal.
Erdvė mes turime rasti jai dabar Iškart už šios kėdę.
Ir dabar, jei galėtumėte grįžti, taip pat, dabar mes turime, turi būti aišku, du
pusės, kiekvienas dydis 2 -
ir tik vaizdavimas meilės, jei galėtų šiek tiek erdvėje -
vienas kairėje pusė čia vienas Dešinė pusė čia.
>> Atsukti toliau istorija.
Kas žingsnis yra šalia?
>> Auditorija: Sujungti.
>> Davidas Malan: Taigi dabar mes turime sujungti.
Taigi Gerai, kad dabar, laimei, mes tiesiog atlaisvinti keturis kėdės.
Taigi mes naudojame dvigubai daugiau atminties, bet mes galime suteikti flip-flop'e tarp
dvi matricas.
Taigi, kuris skaičius yra atėjai, pirmas?
Taigi Michelle, žinoma.
Taigi ateiti aplink ir imtis Jūsų vieta čia.
Ir tada numeris 2 yra akivaizdžiai kitą, todėl jūs ateiti čia.
Numeris 4 numeris 6.
Ir vėl, nors ten Šiek tiek pėsčiųjų dalyvauja,
tikrai, tai gali įvykti akimirksniu, perkeldami vieną -
Gerai, gerai grojo.
>> [Juokas]
>> Davidas Malan: O dabar mes gana geros formos.
Kairėje pusėje, visą įvesties jau rūšiuojamos.
Gerai, kad šie vaikinai buvo iš mano privalumas -
kaip ji galų gale visus ant merginos į kairę ir visi ant dešinės berniukai?
>> Gerai, kad vaikinai "eilė dabar.
Taigi aš ne vaikščioti jus per šiuos veiksmus.
Mes pamatyti, jei mes galime iš naujo pats Pseudocode.
Jei norite eiti į priekį ir atsistoti, ir vaikinai, leiskite man duoti jums mikrofono.
Žr jeigu jūs galite ne atkartoti tai, ką mes tiesiog padarė čia
kitas galas sąrašo.
Kas turi kalbėti pirma, remiantis algoritmas?
Taigi, paaiškinti, ką darai prieš jums jokių pėdų judesius.
>> GARSIAKALBIS 1: Gerai, kad jau Esu kairę pusę
kairėje pusėje, vėl grįšiu.
Teisė?
>> Davidas Malan: Geras.
>> GARSIAKALBIS 1: Ir tada -
>> Davidas Malan: Kas daro mic eiti toliau?
>> GARSIAKALBIS 1 Kitas skaičius.
>> SPEAKER 2: Taigi, aš į dešinę pusę iš kairėje pusėje
kairė pusė, ir aš grįžti.
>> Davidas Malan: Geras.
Grįšite.
Taigi dabar kas kitas už jus du?
>> SPEAKER 2: Mes norime pamatyti, kas yra mažesnis.
>> Davidas Malan: Būtent.
Mes norime sujungti.
Erdvė mes ketiname naudoti sujungti jūs į, nors jie
Akivaizdu, surūšiuoti jau mes ketiname laikytis tos pačios algoritmą.
Taigi, kas eina atgal pirmiausia?
Taigi 3, tada 7.
Ir dabar mikrofono eina šių vaikinai, gerai?
>> GARSIAKALBIS 3: Taigi, aš į dešinę pusę į kairę pusę, o mano n yra mažesnis nei
1, todėl aš tik ketina perduoti -
>> Davidas Malan: Geras.
>> GARSIAKALBIS 4 Aš teisė pusė Dešinė pusė iš dešinės pusės, ir aš
taip pat vienas asmuo, todėl aš ketina grįžti.
Taigi dabar mes sulieti.
>> GARSIAKALBIS 3: Taigi mes einame atgal.
>> Davidas Malan: Taigi jūs einate į nugarą.
Taigi 5 eina, tada 8.
Ir dabar auditorijos, kuri yra žingsnis turime dabar atsukti
atgal į mūsų protus?
>> Auditorija: Sujungti.
>> Davidas Malan: sujungimas kairėje pusėje, ir dešinėje pusė pradinio kairę pusę.
Taigi dabar -
ir tiesiog padaryti tai aišku, padaryti šiek tiek vietos
tarp jūsų du vaikinai.
Taigi dabar, kad yra du sąrašai, kairę ir dešinę.
Taigi, kaip mes dabar sujungti jus vaikinai į priekinė sėdynių eilė naujo?
>> 3 eina pirma.
Tada 5, žinoma.
Tada 7, o dabar 8.
Gerai, dabar mes esame?
>> Auditorija: Neatlikta.
>> Davidas Malan: Ne padaryti, nes be abejo, yra vienas žingsnis liko.
Bet vėl, todėl aš naudoju tai žargonas kaip "atsukti savo mintis",
tai todėl, kad tikrai kas vyksta.
Mes ketiname per visus šiuos veiksmus, bet mes tarsi pristabdę
momentas, nardymas giliau į algoritmas, pristabdę for a moment,
nardymas giliau į algoritmą ir dabar mes turime rūšiuoti atsukti mūsų
protus ir atšaukti visų šių sluoksnių kad mes tarsi užlaikomas.
>> Taigi dabar mes turime du sąrašus dydžio 4.
Jei vaikinai galėtų atsistoti paskutinį kartą ir padaryti daug diske čia
aiškiai nurodyti, kad tai yra kairėje pusė originalus,
Dešinė pusė iš originalo.
Kas pirmas skaičius, kad mes reikia traukti į nugarą?
Michelle, žinoma.
>> Taigi, mes įdėti Michelle čia.
Ir kas yra skaičius 2?
Numeris 2 ateina atgal taip pat.
Numeris 3?
Puikus.
Numeris 4 numeris 5 numeris 6 numeris 7 ir skaičius 8.
>> Gerai, kad ji jautėsi kaip daug žingsnių, tikrai.
Bet dabar pažiūrėkime, jei mes negalime patvirtinti tarsi intuityviai, kad šis
algoritmas iš esmės, ypač n bus tikrai didelis, kaip matėme
su animacija, yra iš esmės greičiau.
Taigi galiu reikalauti šį algoritmą, kad blogiausia atveju ir net geriausiu atveju,
yra didelis O n kartų log n.
Tai yra, ten kai šis aspektas algoritmas, kuris trunka n žingsnių, tačiau
yra ir kitas aspektas kažkur kad iteracija, kad apsisukimo, kad
trunka log n žingsnių.
Mes galime įdėti mūsų pirštu, ką tie du skaičiai omenyje?
Na, kur -
where'd mikrofono eiti?
>> GARSIAKALBIS 1: Ar prisijungti, kad n nesilaikantiems mus į dvi -
padalijus iš dviejų, iš esmės.
>> Davidas Malan: Būtent.
Bet kuriuo metu mes matome, bet algoritmas taigi kas ten buvo tai modelis
dalijimas, dalijimas, dalijant.
Ir tai paprastai sumažinama į kažką, kad
logaritminė, prisijunkite bazė 2.
Bet tai tikrai galėjo būti bet kas, bet prisijungti bazę 2.
>> Dabar ką apie n?
Matau, kad mes tipo suskirstyti jus vaikinai - suskirstyti jus, padalintas jums,
suskirstyti jus, padalintas jums.
Kur atėjo galas iš?
>> Taigi tai sujungti.
Kadangi apie tai galvoti.
Jei sujungti aštuonis žmones, kai pusė iš jų yra keturių rinkinys
ir kita pusė yra vienas nustatyti iš keturių, kaip tu
apie tai sujungti?
Na, vaikinai padarė gana intuityviai.
>> Bet jei aš, o ne tai padarė šiek tiek daugiau metodiškai, aš galėjo nurodė
kairiausias asmuo pirmą kartą su mano kairę Kita vertus, nurodė kairiausias asmeniui
tos su mano dešinėje pusėje, ir tik vėliau perėjau
sąrašas, nurodant bent mažiausio elemento kiekvieną kartą, juda mano pirštu per ir
per kiek reikia visą sąrašą.
Bet kas svarbiausia apie tai sujungti procesas yra aš Palyginus šias poras
elementų.
Iš dešinės pusės ir iš kairės pusė, aš nė karto atsitraukia.
>> Taigi sujungti pati imasi ne daugiau kaip n žingsnių.
Ir kiek kartų padarė Turiu padaryti, kad sujungus?
Na, ne daugiau nei n, ir mes tiesiog pamatė, kad su galutiniu suliejimo.
Ir todėl, jei jūs ką nors, kad mano log n žingsnių n kartų, arba atvirkščiai,
jis ketina duoti mums n kartų log n.
>> Ir kodėl tai yra geriau?
Na, jei mes jau žinome, kad žurnalą n yra geriau nei n - tiesa?
Mes matėme dvejetainėje paiešką, telefono knyga Pavyzdžiui, log n tikrai buvo
geriau nei tiesinis.
Taigi, tai reiškia n kartų log n yra tikrai geriau nei n kartų kitą
n AKA n kvadratu.
Ir tai, ką mes galiausiai jaustis.
>> Taigi didelis audringi plojimai, jei galėtume, šių vaikinai.
>> [Plojimai]
>> Davidas Malan: Ir jūsų atsisveikinimo dovanos - galite išsaugoti numerius,
jei norėtumėte.
Ir tavo atsisveikinimo dovana, kaip įprasta.
Oh, ir mes atsiųsime Jums filmuota medžiaga Michelle.
Ačiū.
Gerai.
Padėti sau streso kamuolys.
>> Ir leiskite man atsigriebti, tuo tarpu, mūsų draugas Robas Bowden ir pasiūlyti
šiek tiek kitoks požiūris į tai, nes jūs galite galvoti apie tai
veiksmai vyksta šiek tiek kitaip.
Tiesą sakant, steigti, kas Rob apie parodyti mums, daroma prielaida, kad mes
jau padaryta dalijant sudaro didelis sąrašas į aštuonias mažų sąrašus,
kiekvieno dydžio 1.
>> Taigi, mes keičiasi pseudocode truputį tik rūšiuoti gauti ne
pagrindinė idėja, kaip sujungti darbus.
Bet važiavimo laikas, ką jis apie tai dar
bus tas pats.
Ir vėl steigti čia yra tai, kad jis prasidėjo aštuonių sąrašus dydis 1.
Taigi jūs praleidote dalį, kur jis iš tikrųjų padaryta log n, log n, log n
dalijant iš įvesties.
>> [VIDEO PLAYBACK]
>> -Štai ir viskas už žingsnio.
Dėl antro žingsnio, pakartotinai sujungti porų sąrašus.
>> Davidas Malan: Hm.
Tik garso artėja iš mano kompiuterio.
Pabandykime dar kartą.
>> -Tiesiog savavališkai pasirinkti, kuris - dabar mes turime keturis sąrašus.
Sužinokite anksčiau.
>> Davidas Malan: Čia mes eiti.
>> -Sujungimas 108 ir 15 straipsnius, mes galų su sąrašas 15 108.
Sujungus 50 ir 4, mes baigti su 4, 50.
Sujungimas 8 ir 42 straipsnius, mes baigti su 8, 42.
Ir sujungti 23 ir 16 straipsniuose, mes baigti su 16, 23.
>> Dabar visi mūsų sąrašuose yra 2 dydžio.
Atkreipkite dėmesį, kad kiekviena keturi sąrašai yra rūšiuojama.
Taigi, mes galime pradėti sujungti porų sąrašus dar kartą.
Sujungus 15 ir 108 4 ir 50, mes pirmiausia reikia 4, tada 15, tada
50, tada 108.
Sujungimas 8, 42 ir 16, 23, mes pirmiausia reikia 8, tada 16, tada 23,
tada 42.
>> Taigi dabar mes turime tik du sąrašus dydžio 4, iš kurių kiekvienas yra rūšiuojama.
Taigi dabar mes sujungti šiuos du sąrašus.
Pirma, mes imame 4, tada mes 8, tada mes priimsime 15, tada 16, tada
23, tada 42, tada 50, tada 108.
>> [PABAIGA VIDEO PLAYBACK]
>> Davidas Malan: Vėlgi, pranešimas, jis niekada palietė tam tikrą taurę daugiau nei vieną kartą
po priekį už jos ribų.
Taigi jis niekada kartoti.
Taigi, jis visada juda į šoną, ir tai, kur mes turime mūsų n.
>> Kodėl gi ne leiskite man atsigriebti vieną animaciją kad mes matėme anksčiau, bet šį kartą
skirta tik suliejimo rūšiuoti.
Leiskite man eiti į priekį ir priartinti ir apie tai čia.
Pirmiausia leiskite man pasirinkti atsitiktinę įvestį, paaštrins, ir jūs galite rūšiuoti pamatyti
ką mes paėmė už suteiktas, anksčiau, sujungti tarsi iš tikrųjų daro.
>> Taigi, pastebėsite, kad jūs gaunate šias puses arba šie ketvirčiais arba jų aštuonių iš
problema, kad visi staiga pradėti imtis geros formos.
Ir galiausiai, kaip matote ne labai pabaiga, kad bam
viskas sujungta kartu.
>> Taigi tai yra tik trijų skirtingų įgauna tą pačią idėją.
Bet svarbiausia įžvalga, kaip ir atskirties ir užkariauti pačioje pirmoje klasėje,
buvo ta, kad mes nusprendėme kažkaip padalinti į kažką didelis, į problema
kažkas tarsi identiški dvasia, bet mažesni ir mažesni ir mažesni
ir mažesnis.
>> Dabar dar vienas įdomus būdas rūšiuoti mano, apie tai, nors tai nėra
norėčiau duoti jums tą patį intuityvus supratimas, yra
taip animacija.
Taigi tai yra vaizdo įdėti ką nors kartu kad susijęs skiriasi
garsai, turintys įvairių operacijų įterpimo rūšiuoti, už suliejimo rūšiuoti, ir
dėl kitų pora.
Taigi vienu metu, aš ketina hit Atkurti.
Tai apie minučių ilgio.
Ir net jei jūs vis dar galite pamatyti modeliai vyksta, šiuo metu galite
taip pat išgirsti, kaip šie algoritmai atlieka skirtingai ir
šiek tiek skirtingi modeliai.
>> Tai įterpimo rūšiuoti.
>> [TONES PLAYING]
>> Davidas Malan: Jis vėl bando įterpti kiekvieną elementą
į kur jis priklauso.
Tai burbulas rūšiuoti.
>> [TONES PLAYING]
>> Davidas Malan: Ir jūs galite rūšiuoti jaustis kaip santykinai mažai dirbti jis daro
ant kiekvieno žingsnio.
Tai, ką Monotoniška skamba.
>> [TONES PLAYING]
>> Davidas Malan: Tai pasirinkimas rūšiuoti, kur mes pasirinkite elementą norime pagal
išgyvena vėl ir vėl ir vėl ir pradėti jį iš pradžių.
>> [TONES PLAYING]
>> Davidas Malan: tai sujungti rūšiuoti, kuris tikrai galite pradėti jaustis.
>> [TONES PLAYING]
>> [Juokas]
>> Davidas Malan: Kažkas vadinamas gnome rūšiuoti, kurį mes ne pažvelgė.
>> [TONES PLAYING]
>> Davidas Malan: Taigi leiskite man pamatyti, kad dabar, išsiblaškęs, kaip jums tikiuosi, yra iš
muzikos, jei aš galiu slydimo mažai tiek matematikos čia.
Taigi, čia yra ketvirtas būdas, kad mes galime galvoti apie tai, ką reiškia šie
funkcijas, kurios bus greičiau nei tie, kad mes matėme anksčiau.
Ir jei jūs dar tuo metu iš matematika fone, jūs
iš tikrųjų žino, galbūt jau, kad jūs gali slap terminą nuo šio metodo -
būtent rekursija, funkcija kad kažkaip save vadina.
>> Ir vėl priminti, kad suliejimo rūšiuoti Pseudocode buvo pakartotinė ta prasme,
kad vienas iš Merge sort žingsnius buvo paraginti rūšiuoti -
tai yra pati.
Bet, laimei, nes mes nuolat raginama rūšiuoti, arba sujungti rūšiuoti,
Tiksliau, į mažesnes ir mažesnių sąrašas, mes galiausiai
dugną dėka ką mes vadiname bazinį scenarijų, sunkiai koduojamų atvejis,
sakė, kad jei sąrašas yra mažas, mažiau nei 2 Tokiu atveju, tiesiog grįžti iš karto.
Jei mes ne turėti, kad ypatingas atvejis, algoritmas niekada iš apačios,
ir jūs iš tikrųjų gauti į begalinis ciklas tikrai amžinai.
>> Bet tarkime, kad mes norėjome dabar įdėti keletas patarimų, tai numeriai, vėlgi, naudojant n
kaip įėjimo dydžio.
Ir aš norėjau paklausti, kas bendras laikas dalyvauja
veikia suliejimo rūšiuoti?
Ar apskritai kas jos sąnaudos metu?
>> Na tai gana lengva pamatuoti.
Jei n yra mažesnis nei 2 metu dalyvauja rūšiavimo n elementų,
kur n yra 2, yra 0.
Kadangi mes tiesiog grįžti.
Nėra nuveikti.
Dabar tikriausiai, o gal tai vienas žingsnis ar du žingsniai išsiaiškinti sumą
dirbti, bet tai pakankamai arti 0, kad Aš tik ketina pasakyti "ne" darbas
būtinas, jei sąrašas yra toks mažas, būti neįdomu.
>> Tačiau šis atvejis įdomus.
Rekursywny byla buvo filialas Pseudocode tai sakė kitur, tarsi
kairė pusė, rūšiuoti teisė pusę, sujungti dvi dalis.
Dabar kodėl ši išraiška atstovauja tai sąskaita?
Na, T n tiesiog reiškia, laikas rūšiuoti n elementų.
Ir tada dešinėje pusėje lygybės ženklą ten, n T suskirstyti
pagal 2 nuoroda į kokia kaina?
Rūšiavimas kairę pusę.
Kitas T n dalijamas iš 2 matyt, nuoroda į išlaidų
rūšiuoti tinkamą pusę.
>> Ir tada plius n?
Ar sujungus.
Nes jei jūs turite du sąrašus, vienas iš dydis n per 2 ir kitas dydis n
per 2, turite iš esmės paliesti kiekvienas iš šių elementų, kaip Rob
palietė kiekvieną puodeliai, ir tik kaip pažymėjome kiekviename
savanoriai scenoje.
Taigi n yra sujungti sąskaita.
>> Dabar, deja, ši formulė taip pat pati pakartotinė.
Taigi, jei uždavė klausimą, jei n yra, tarkim, 16, jei yra 16 žmonių scenoje
arba 16 puodeliai vaizdo, kiek iš viso žingsniai užtrunka juos surūšiuoti
su suliejimo rūšiuoti?
Tai iš tikrųjų nėra akivaizdu, atsakymas, nes dabar jūs turite rūšiuoti
rekursyviai atsakyti į šį formulę.
>> Bet tai gerai, nes leiskite man pasiūlyti kad mes atlikite šiuos veiksmus.
Šiuo metu dalyvauja rūšiuoti 16 žmonių arba 16 puodeliai ketina atstovauti
paprastai kaip T 16.
Bet tai lygu pagal mūsų Ankstesnis formulė, 2 kartus suma
laiko užtrunka rūšiuoti 8 puodeliai plius 16.
Ir vėl, plius 16 yra laikas sujungti, ir du kartus T 8 yra
laikas rūšiuoti kairę pusę ir į dešinę pusę.
>> Bet vėl, tai nėra pakankamai.
Mes turime pasinerti giliau.
Tai reiškia, kad mes turime atsakyti klausimas, kas tai yra "T 8?
Na T 8 yra tik 2 kartų T 4 plius 8.
Na, kas T 4?
T 4 yra tik 2 kartus t 2 plius 4.
Na, kas T 2?
T 2 "yra vos 2 kartus T 1 plius 2.
>> Ir vėl mes natūra gauti įstrigo šio ciklo.
Bet tai apie pataikyti, kad vadinamasis bazinį scenarijų.
Nes tai, kas yra T 1, tai mes reikalauti?
0.
Taigi dabar, pagaliau, galime dirbti atgal.
>> Jei T 1 yra 0, aš dabar gali eiti atgal dar vieną išsirikiuoti šis vaikinas čia, ir aš galiu
prijunkite 0, kai t 1.
Taigi, tai reiškia, kad ji yra lygi 2 kartus nulis, kitaip žinomas kaip 0, plius 2.
Ir kad visa išraiška 2.
>> Dabar, jei aš su 2 T, kurio atsakymas yra 2, prijunkite jį prie vidurio linijos, T
4, kuris suteikia man 2 kartus 2 plius 4, todėl 8.
Jei aš tada prijungti 8 iki ankstesnio linija, kuri suteikia man 2 kartus 8, 16.
Ir jei mes tęskite, kad su 24, pridedant 16, mes pagaliau gauti
vertė 64.
>> Dabar, kad ir pati tarsi kalba nieko n žymėjimą,
Didelės O, omega, kad mes buvo kalbama apie.
Tačiau paaiškėja, kad 64 yra iš tiesų 16, įėjimas, dydis,
prisijungti 16 2 bazę.
Ir jei tai yra šiek tiek susipažinę, tiesiog prisiminkite, ir jis bus grįžti
jums galų gale.
Jei tai žurnalas bazė 2, tai kaip 2 pakeltas, kas suteikia jums 16?
O, tai 4, todėl 16 kartų 4.
>> Ir vėl, tai ne baisi, jei tai yra tarsi miglotos atminties dabar.
Bet dabar, imtis tikėjimo kad 16 log 16 vertė yra 64.
Ir taip iš tiesų, su šia paprasta sveiko proto patikrinti, mes patvirtino -
bet neįrodė oficialiai -
kad veikimo laikas suliejimą rūšiuoti yra iš tiesų n log n.
>> Taigi nėra blogai.
Tai tikrai geriau nei algoritmai mes matėme iki šiol, ir
tai todėl, kad mes pagausėtų, viena, technika vadinama rekursija.
Bet įdomesnis nei, kad sąvoka dalijant ir užkariauja.
Vėlgi, tikrai savaitę 0 stuff, kad net ir dabar yra pasikartojimo
daugiau įtikinamų būdu.
>> Dabar įdomus mažai pratimų, jei jūs niekada tai padarė - ir jūs tikriausiai
neturės, nes tarsi normalu žmonių neturi galvoti kaip tai padaryti.
Bet jei aš einu į google.com ir, jei Noriu sužinoti ką nors apie
rekursija, Enter.
>> [Juokas]
[Daugiau juokas]
Davidas Malan: Blogas pokštas lėtai plisti.
[Juokas]
Davidas Malan: Tik tuo atveju, tai ten.
Aš ne aiškiai tai negerai, ir ten pokštas.
Gerai.
Paaiškinti žmonėms, šalia tavęs, jei ji ne visai paspaudėte tik dar.
Bet rekursija, apskritai, reiškia su funkcija telefono proceso
pati, ar apskritai dalijant problema į kažką, kad gali būti
išspręsta dalimis sprendžiant identiškas atstovas problemos.
>> Na, tegul perjungti pavaras tik akimirką.
Mes norėtume užbaigti dėl tam tikrų cliffhangers, todėl galime pradėti kurti
etapas, keletą minučių, dėl labai paprastą idėją -
kad keičiant du elementus, tiesa?
Visi šie algoritmai mes jau kalbame apie pastaruosius porą
paskaitos įtraukti kai kurie rūšiuoti Swapping.
Šiandien ji buvo regimos juos gauti iki iš savo kėdės ir
vaikščioti aplink, bet kodu, mes norėtume tiesiog elementą iš vieno masyvo
ir pop jį į kitą.
>> Taigi, kaip mes eiti apie tai daro?
Na, leiskite man eiti į priekį ir rašyti Trumpa programa čia.
Aš ruošiuosi eiti į priekį ir daryti tai kaip toliau.
Tegul tai vadina -
ką mes norime paraginti šį vieną?
>> Tiesą sakant, ne.
Leiskite man atgal.
Aš nenoriu to daryti Įspūdingos filmą dar.
Tai bus sugadinti įdomus.
Leiskite tai padaryti vietoj.
>> Tarkime, kad aš noriu rašyti mažai programa ir kad dabar apima ši
idėja rekursijos.
I rūšies gavo prieš save ten.
Aš ruošiuosi atlikite šiuos veiksmus.
>> Pirma, greitai apima standartinės io.h, taip pat iš cs50.h. apima
Ir tada aš ruošiuosi eiti į priekį ir paskelbti int main negaliojančiu
įprastu būdu.
Supratau, aš misnamed failą, todėl leiskite man tiesiog pridėkite. c Papildomo čia taip
kad mes galime sudaryti tinkamai.
Pradėti šią funkciją išjungti.
>> Ir funkcija noriu rašyti, gana tiesiog, yra vienas, kad prašo
vartotojas už skaičių ir tada išauga iki visi įmonių tarpusavio, kad numeriai
skaičius ir, tarkim, 0.
Taigi, pirmiausia aš ruošiuosi eiti į priekį ir paskelbti int n.
Tada aš nukopijuoti tam tikrą kodą, kad mes naudojame tam tikrą laiką.
Nors kažkas yra tiesa.
Aš sugrįšiu į tą, akimirką.
>> Ką norite daryti?
Noriu pasakyti printf teigiamas sveikasis skaičius prašom.
Ir tada aš ruošiuosi pasakyti n gauna gauti int.
Taigi dar kartą, kai Standartiniai kodas kad mes naudojamas anksčiau.
Ir aš ruošiuosi tai padaryti o n yra mažesnis nei 1.
Taigi tai bus užtikrinta, kad vartotojo suteikia man teigiamą sveikąjį skaičių.
>> Ir dabar aš ruošiuosi daryti toliau.
Noriu pridėti visus numerius nuo 1 iki ir n-arba 0 ir n
analogiškai, jei norite gauti bendrą sumą.
Taigi didelis sigma simbolis kad jums gali prisiminti.
Taigi, aš ruošiuosi tai padaryti pirmą skambučiams funkcija vadinama sigma,
perduoti ją į n, ir tada aš ruošiuosi pasakyti printf, atsakymas yra teisę ten.
>> Taigi trumpai tariant, man ir int nuo naudotojo.
Aš užtikrinti, kad ji yra teigiamas.
Aš pareiškiu, kintamasis vadinamas atsakymas tipas int ir laikyti jį grąžinti
vertė sigma, einančios n kaip įvestį.
Ir tada aš atsispausdinti šį atsakymą.
>> Deja, nors sigma skamba kaip kažkas, kad gali būti
math.h failas, jo deklaracija, tai tikrai ne.
Taigi, kad viskas OK.
Galiu įgyvendinti šį save.
Aš ruošiuosi įgyvendinti funkcija vadinama sigma, ir ji ketina imtis
parametras -
galime tik jį vadiname m, tiesiog todėl skiriasi.
Ir tada čia aš ruošiuosi pasakyti, Na, jei m yra mažesnis nei 1 - tai
labai neįdomu programą.
Taigi, aš ruošiuosi eiti į priekį ir nedelsiant grąžinti 0.
Jis tiesiog nėra prasmės pridėti iki visų tarp 1 ir M Jei m numeriai
pati 0 arba neigiamas.
>> Ir tada aš ruošiuosi eiti į priekį ir tai labai iteracijų.
Aš ruošiuosi padaryti šį senosios mokyklos rūšiuoti, ir aš ruošiuosi eiti į priekį
ir pasakyti, kad aš ruošiuosi deklaruoti sumą 0.
Tada aš ruošiuosi už linijos int -
ir leiskite man tai padaryti geriau atitiktų mūsų paskirstymo kodas, todėl jūs turite kopiją
namuose. int i gauna 1 m iki i yra mažesnė arba lygi m.
i plius plius.
Ir tada viduje tai už linijos -
Mes beveik ten -
suma gauna sumą, taip pat 1.
Ir tada aš ruošiuosi grįžti sumą.
>> Taigi aš tai greitai, visai tiesa.
Bet vėl, pagrindinė funkcija yra gana paprasta, grindžiamas kodą mes
parašyta iki šiol.
Naudoja dvigubą kilpą gauti teigiami int nuo naudotojo.
Tada aš praeiti int į naują funkciją vadinama sigma, vadindami jį, vėlgi, n.
Ir aš laikyti sugrįžimo vertę, atsakymas iš juodosios dėžės metu
žinomas kaip sigma, kad kintamasis vadinamas atsakymas.
Tada aš spausdinti.
>> Jei mes dabar tęsti istoriją, kaip yra sigma įgyvendinti?
Siūlau įgyvendinti taip.
Pirma, šiek tiek Klaidų tikrinimas įsitikinti, kad vartotojo nėra
Messing su manimi ir einančios kai neigiamas arba 0 vertė.
Tada aš pareiškiu, kintamasis vadinamas Apibendrinant ir nustatykite 0.
>> Ir dabar aš pradedu judėti iš I lygus 1 visą kelią iki ir įskaitant m,
nes noriu įtraukti visus skaičiai nuo vieno iki m imtinai.
Ir viduje tai už linijos, aš tiesiog padaryti suma gauna kokia ji yra dabar, plius
I vertė.
Plius i vertė.
>> Kaip panaikinti, jei nemačiau tai anksčiau, yra keletas sintaksinis cukrus
šios eilutės.
Galiu perrašyti kaip plius lygus i, tik sutaupyti sau keletą klavišų
ir atrodo šiek tiek aušintuvas.
Bet tai ir viskas.
Tai funkciškai tas pats.
>> Deja, šis kodas ųjų nesiruošia sudaryti dar.
Jei aš paleisti, kad sigma 0, kaip am Aš ketina gauti sušuko?
Kas ji ketina nepatinka?
>> Auditorija: [nesigirdi].
>> Davidas Malan: Taip, aš nedeklaravo iki viršuje, dešinėje funkcija?
C rūšies kvailas, nes jis tik ką pasakyti tai padaryti, ir jūs
turite tai padaryti tokia tvarka.
Ir todėl, jei aš paspauskite Enter čia, aš ruošiuosi gauti apie sigma įspėjimas numanoma
deklaracija.
>> O ne problema.
Galiu eiti į viršų, ir aš galiu sako, viskas gerai, palauk.
Sigma yra funkcija, kuri grąžina int ir tikisi,
int kaip pirkimo, kabliataškiu.
Ar galėčiau įdėti visą funkciją virš pagrindinis, bet apskritai, aš
rekomenduojame prieš tai, nes tai malonu visada pagrindinis viršuje tt
galite pasinerti teisę ir žinoti, ką programa daro skaitant pagrindinė sritis.
>> Taigi dabar leiskite man išvalyti ekraną.
Perdarytas sigma 0.
Viskas atrodo patikrinti.
Leiskite man paleisti sigma 0.
Teigiamas kita.
Aš duosiu jam numerį 3 keep it simple.
Taigi, kad turėtų duoti man 3 plius 2 plius 1, taigi 6.
Įveskite, ir iš tiesų aš gausiu 6.
>> Galiu padaryti kažką daugiau -
50, 12, 75.
Tiesiog kaip liestinė, aš ruošiuosi daryti kažką juokinga kaip tikrai didelis
skaičius, O, kad faktiškai dirbo -
eh, aš nemanau, kad tai tiesa.
Pažiūrėkime.
Leiskite tikrai netvarka su juo.
>> Tai problema.
Kas vyksta?
Kodas nėra taip blogai.
Jis vis dar tiesinis.
Švilpimas yra geras poveikis, nors.
Kas vyksta?
>> Nežinote jei aš girdėjau jį.
Taigi paaiškėja, - ir tai kaip panaikinti.
Tai ne core idėja rekursijos.
Pasirodo, nes aš bandau sudaro tokį didelį skaičių, dauguma
greičiausiai jis bus klaidingai sprendimu C kaip nėra teigiamas skaičius,
bet neigiamas skaičius.
>> Mes ne kalbėjo apie tai, bet jis Pasirodo, yra neigiami skaičiai
į be pasaulio su teigiamais skaičiais.
Ir būdus, kuriais galite sudaro neigiamą skaičių
iš esmės yra, jūs naudojate vieną Specialusis tiek nurodyti
teigiami per neigiamas.
Tai šiek tiek sudėtingesnis nei, kad bet tai pagrindinė idėja.
>> Taigi, deja, jei C painu vieną iš tų tikrųjų reiškia bitai,
Oh, tai yra neigiamas skaičius, mano kilpa Čia, pavyzdžiui, iš tikrųjų niekada
ketina nutraukti.
Taigi, jei aš iš tikrųjų buvo spausdinti kažką vėl ir vėl, mes norėtume
pamatyti visą partiją.
Bet vėl, tai be taško.
Tai tikrai tiesiog tarsi intelektinės smalsumas, kad mes ateis
atgal į ilgainiui.
Bet dabar, tai yra teisinga įgyvendinimas, jei mes manome, kad
vartotojo teiks Ints kad tilptų Ints.
>> Bet aš teigia, kad šis kodas, tiesą sakant, gali būti padaryta tiek daug paprastai.
Jei po ranka tikslas praeiti kelios kaip m, pridėti visi
numeriai tarp jo ir 1 arba atvirkščiai nuo 1 ir, galiu reikalauti
kad galiu pasiskolinti šią idėją, kad sujungti rūšiuoti turėjo buvo atsižvelgiant problemų
tokio dydžio ir dalinant į kažką mažesnio.
Gal ir ne pusė, bet mažesnis, tačiau tipiniai pats.
Pati idėja, bet mažesnė problema.
>> Taigi, aš iš tikrųjų - leiskite man išsaugoti šį failą su kitu versijos numerį.
Mes vadiname šią versiją 1 vietoj 0.
Ir galiu reikalauti, kad aš iš tikrųjų galite reimplement šią rūšies
proto-lenkimo būdu.
>> Aš ruošiuosi palikti dalį jai pačiai.
Aš ruošiuosi pasakyti, jei m yra mažiau nei ar net lygi 0 -
Aš tiesiog bus mažai daugiau analinis šį kartą
su mano klaidų tikrinimas -
Aš ruošiuosi eiti į priekį ir grįžti 0.
Tai savavališkai.
Aš tiesiog nuspręsti, ar vartotojo man duoda neigiamą skaičių, aš
grįžti 0, ir jie turėjo skaityti dokumentacija labiau.
>> Kita -
pastebėsite, ką aš ruošiuosi daryti.
Kita aš grįžti m plius -
kas yra sigma M?
Na, sigma iš m plius m ± 1, plius minus m 2 plius minus 3 m.
Aš nenoriu rašyti visi, kad iš.
Kodėl ne aš tiesiog kamuolio išmušimas iš rankų?
Rekursyviai vadina save su šiek tiek mažesnė problema, kabliataškis,
ir vadina jį dieną?
>> Teisė?
Dabar čia taip pat galite jaustis ar nerimauti kad tai yra begalinis ciklas, kad aš
skatina, kai aš įgyvendinant sigma iškvietus sigma.
Bet tai visiškai gerai, nes aš maniau priekį pridėta į kurias eilutes?
>> Auditorija: [nesigirdi].
>> Davidas Malan: 23 už, 26 kuri mano, jei sąlyga.
Nes tai, kas yra malonu apie atimtis čia, nes aš nuolat
dalijamos sigma mažesnių problemų, mažesnių problemų, mažesnių - tai ne
pusė dydžio.
Tai tik kūdikis žingsnis mažesnis, bet tai gerai.
Nes, galų gale, mes dirbti mūsų kelią žemyn iki 1 arba 0.
Ir kai mes paspauskite 0, sigma nėra ketinate skambinti save daugiau.
Ji ketina nedelsiant grąžinti 0.
>> Taigi poveikis, jei tarsi vėjas tai iki savo mintis, yra įtraukti m plius
m, atėmus 1, plius minus 2 m, plius m atėmus 3, plius taškas, taškas, taškas, m, atėmus
m, galiausiai suteikia jums 0, ir poveikis yra galiausiai pridėti visus
šie dalykai kartu.
Taigi, mes turime ne, su rekursija, išspręsti problemą, kad mes
negalėjo išspręsti anksčiau.
Iš tiesų, portalo 0 to, ir kiekvienas problema iki šiol buvo išsprendžiamas
tik su naudojate kilpomis arba kai kilpos arba panašių stato.
>> Bet rekursija, aš Manyti, suteikia mums kitaip galvoti apie
problemos, kurią, jei mes galime imtis problema, padalinkite jį nuo kažko
šiek tiek didelis, į kažką šiek tiek mažesnis, galiu reikalauti, kad mes galime ją išspręsti
galbūt šiek tiek daugiau elegantiškai požiūriu konstrukcijos, su mažiau kodą,
o gal net spręsti problemas, kad būtų būti sunkiau, nes mes galų gale
pamatyti, sprendžiant grynai keletą kartų.
>> Bet Įspūdingos filmą, kad aš nori palikti mums buvo tai.
Leiskite man eiti į priekį ir atidaryti iki failą iš -
Tiesą sakant, leiskite man eiti ir tai padaryti labai greitai.
Leiskite man eiti į priekį ir pasiūlyti taip.
Tarp šiandienos kodas yra šį failą čia.
Tai vienas čia noswap.
>> Taigi tai yra kvailas mažai programa, kuri Aš plakta kuri teigia, kad daryti
taip.
Iš esmės, ji pirmą kartą pareiškia, LC vadinamas x ir priskiria jį
vertė 1.
Tada jis pareiškia, int y ir jam priskiria reikšmę 2.
Tada jis spausdina, ką x ir y yra.
Tada ji sako, Swapping, dot dot dot.
>> Tada ji teigia būti raginama funkciją vadinama swap, einančios į x ir
m, idėja yra tai, kad tikiuosi x ir y sugrįš
skirtingi, priešingai.
Tada ji teigia pavertė!
su šauktuku.
Tada jis spausdina x ir y.
>> Tačiau paaiškėja, kad tai labai paprastas demonstravimo žemyn
čia iš tikrųjų yra klaidų.
Nors aš skelbiantis laikinas kintama ir laikinai išleisti į
tai, tada aš perskirstymo vertė b -
kurie jaučiasi suprantama, nes aš išgelbėti iš TEMP kopiją.
Tada aš atnaujinti b, lygios kokia buvo temp.
Šis lukštais žaidimas juda rūšiuoti į B And B į naudojant šį
vidutinio Žmogus, vadinamas temperatūros jaučiasi visiškai pagrįsta.
>> Bet aš teigia, kad kai aš paleisti šį kodas, kaip aš tai padaryti dabar -
leiskite man eiti į priekį ir įklijuokite jį čia.
Aš vadinu tai noswap.c.
Ir kaip rodo pavadinimas, tai nėra bus teisinga programa.
Padaryti noswap. / Ne sukeisti.
x 1, y 2, Swapping, pavertė.
x 1, y 2.
Tai yra iš esmės neteisinga, net nors tai atrodo puikiai
protingas man.
Ir yra priežastis, bet mes ne ketina atskleisti priežastis, tik dar.
>> Nes dabar antrą Įspūdingos filmą norėjau palikti jus su tai,
paskelbimas rūšių apie kuponų kodų.
Mūsų naujovės pavėluotą dienų šiemet jau išprovokavo ne trivialus skaičius
klausimų, kuris buvo nėra mūsų tikslas.
Šių kuponų kodų ketinimą, kurią, jei jūs problemos dalis
nustatyti anksti, todėl gauti papildomą dieną, buvo tikrai padėti vaikinai padėti
sau pradėti anksti, rūšiuoti apie kurį skatinamųjų jums.
Padeda mums platinti apkrovą visoje Darbo laikas geriau todėl, kad
Tai tarsi laimi.
>> Deja, manau, kad mano instrukcijas nebuvo iki šiol labai aiškiai, todėl
Grįžau šį savaitgalį, ir atnaujinamas didesnėje, drąsiau tekstu spec
paaiškinti, kulkos, kaip šie.
Ir tik pasakyti, kad tai daugiau viešai, pagal Numatytieji, problemų rinkiniai dėl ketvirtadienis
vidurdienį, už mokymo programas.
Jei pradėsite anksti, apdailos dalis problema nustatyti iki trečiadienio 12:00
PM dalį, kuri susijusi su kuponu kodas, idėja yra, kad jūs galite išplėsti
Jūsų terminas P, nustatytos iki penktadienio.
Tai reiškia, kad nukando maža dalis P nustatyti, palyginti su tai, kas paprastai yra
didesne problema, ir jums pirkti sau papildomą dieną.
Vėlgi, tai bus jums galvoti apie problema rinkinys, paleidžiama jums į
darbo valandomis anksčiau.
Bet kuponas problema vis dar reikia, net jei jūs neturite pateikti jį.
>> Bet dar priverstinai tai.
(ETAPAS "WHISPER) Ir tie žmonės palieka pradžioje yra gonna gailėtis.
Kaip ir ant balkono žmonės.
Atsiprašau iš anksto į žmonių su dėl priežasčių, kurios bus balkonas
aišku, vos akimirką.
>> Taigi, mums pasisekė, kad vienas iš CS50 buvęs galvos mokymo bičiulių ne
įmonė vadinama dropbox.com.
Jie labai dosniai paaukojo kuponas čia tai daug vietos,
kuri yra sudaryti iš Įprasti 2 GB.
Taigi, ką aš maniau, mes galėtų padaryti apie tai Paskutinė pastaba yra padaryti iš dovanų tiek,
, pagal kurį tik akimirką, mes atskleisti nugalėtojas, o kas kuponą
kodas, tada galite eiti į savo Interneto svetainę, įveskite jį, ir voila, gauti
daug daugiau ZMI vietos jūsų prietaisas ir savo asmeninius failus.
>> Ir pirmasis, kurie norėtų dalyvauti Šiame piešinyje?
Gerai, kad dabar tampa dar smagiau.
Asmuo, kuris gauna šį 25 gigabaitų kuponas - kuris yra daug
patrauklesni nei vėlai dienų dabar, galbūt -
yra tas, kuris sėdi ant sėdynės pagalvėlės, žemiau kurios yra
kad kuponas.
Dabar galite žiūrėti po jūsų sėdynės pagalvėlės.
>> [VIDEO PLAYBACK]
>> -Vienas, du, trys.
>> [Rėkia]
>> -Jūs gaunate automobilį!
Jūs gaunate automobilį!
>> Davidas Malan: Pamatysime Jūs trečiadienį.
>> -Jūs gaunate automobilį!
Jūs gaunate automobilį!
>> Davidas Malan: Balkonas žmonės, ateik žemyn čia į priekį,
kur mes turime priedai.
>> -Kiekvienas gauna automobilį!
Kiekvienas gauna automobilį!
>> [PABAIGA VIDEO PLAYBACK]
>> Narrator: Kitame CS50 -
>> GARSIAKALBIS 5: Oh my GOSH Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh -
>> [Ukelele vaidina]