[Powered by Google Translate] [3 savaitė, Tęsinys]
>> [David J. Malan - Harvardo universiteto]
>> [Tai CS50. - CS50.TV]
>> Gerai. Sveiki sugrįžę. Tai CS50 ir tai yra 3 savaitės pabaigos.
>> Tad tiems, nepažįstamas, praėjusiais metais Harvardo pradėjo tai, kas vadinama inovacijų laboratorijos,
arba i-laboratorija, kuris yra puikus pastatas per upę HBS miesteliu
, kuri yra atvira studentai, GP moksleiviams, studentams iš visos miesteliu,
įskaitant fakultetą, ir tai vieta ateiti kartu dirbti dėl novatoriškų dalykų,
ypač verslumo dalykų
jei jūs ir 0 arba daugiau draugų galvoja apie darai kažką, verslumo
arba per šią klasę, po šios klasės, ar už jos ribų.
>> Taigi vienas iš dalykų, jie daro per J laikotarpiu yra šių kelionių,
iš kurių vienas yra į Niujorką, iš kurių vienas yra Silicio slėnyje.
Erdvė yra labai ribotas, bet tai galimybė RUB pečių su magistrų
ir antrosios pakopos studijų studentų visoje miesteliu ir iš tikrųjų praleisti laiką tose atitinkamose srityse
kalbasi pradedantiesiems, kalbasi verslininkus ir pan.
Taigi, jei domina, check out šį URL adresą čia.
Jis taip pat yra skaidrių internete.
>> Mes galėtume sušvelninti namo garsą tik šiek tiek?
Jei norėtumėte prisijungti prie mūsų pietums šį penktadienį, 13:15 Fire & Ice, prašome Nukeliavę ten.
Atsiprašome, jei jau užpildyta forma iki tol, kol jūs ten.
Bet mes toliau šią tradiciją pirmyn.
>> Šiandien mes ir toliau aukštesnio lygio diskusiją įvairių problemų, kad mes galime išspręsti,
sutelkiant dėmesį daug mažiau, šiandien bent jau kodą ir daug daugiau idėjų.
Todėl manau, kad atgal į savaitę 0, kai mes sudraskė Telefonų knygos pusėje,
kurių tikslas buvo padaryti ką nors, tiesa, šiek tiek dramatiškas
bet nusiųsti tašką, kad ieško ne turite būti, būtinai
kaip akivaizdu iš pirmo žvilgsnio, kaip jūs manote.
Ir problemų sprendimo apskritai gali ne visada būti geriausias -
Akivaizdžiausias sprendimas nebūtinai gali būti geriausias.
Taigi mes turėjome šio telefono knygą ir, tiesą sakant, visiems mums šiame kambaryje turėjo instinktus,
Labiausiai tikėtina, kad pradėti viduryje, kai ieškote Mike Smith ir tada eiti į kairę arba į dešinę
remiantis kokia abėcėlės raidė mes atsitiko, kad galų gale.
>> Bet tai paprasta idėja, kad mes, žmonės ėmėsi suteikta taip ilgai
tikrai turėtų pradėti atvykti į savo proto priešakyje
nes problemos gauti daug sudėtingesnis nei telefonų knygos,
tie patys paprasti, puikus įžvalgos yra tai, ką ketinate leidžia mums
išspręsti daug sudėtingiau ir įdomiau problemas,
tarp jų keletas dalykų, mes priimame kaip savaime jau šių dienų.
Milijardus tinklalapių ten, ir dar "Google" ir "Bing" ir panašūs
gali rasti dalykų už mus, kaip kad.
Kad manimi ne vyksta naudojant linijinį paiešką, ieškoti visomis įmanomomis tinklalapių.
"Facebook" gali pasakyti, kas visi jūsų draugai arba draugų draugai,
ir kad taip pat gali būti padaryta atrodo akimirksniu šių dienų
nors jie turi milijonus vartotojų.
>> Ir taip, kaip mes iš tikrųjų spręsti problemas minėtos skalės galiausiai sumažinti
idėjas mes pažvelgė į savaitę 0 ir šiek tiek daugiau šiandien.
Mes ne iš naujo atlikti šį algoritmą, bet prisiminti, mes taip pat atliko šį pratimą savaitę 0
kur mes visi atsistoti, imtis skaičiumi 1,
ir tada mes turėjo visus skaičiavimo Kergimas išjungti kartu pridedant savo numerius,
tada pusė gaujos atsisėdo ant kiekvieno iteracijos.
Pasakyta iš 500 studentų 250-125 ir kt.
Bet kaip mes pirmadienį sakė, galinga idėja yra
buvo, kad jei mes dvigubai šios problemos dydį
ir visi vaikai iš Teisingumo Teismo arba EB 10 grįžo į kambarį ir prisijungė prie mūsų,
gerai, mes turbūt galėtų tikėtis, kad visą bendrą grupę
tik 1 didelis pasikartojančių kilpą, nes jie tik gal dvigubai dydį
ar EB 10 atveju šiek tiek daugiau nei dvigubai dydžio.
Ir todėl mes turėtume praleisti šiek tiek daugiau laiko,
bet mes nebūtume išleisti 400 ar 700 daugiau žingsnių.
>> Tik dažų šią nuotrauką taip, kad yra šiek tiek ne tokia abstrakti, tegul ne turėti visus atsistoti.
Bet jei tiems iš jūsų, kurie nusprendė posėdžiauti orkestro šiandien nebūtų proto atsistojus,
galime pamatyti, jei mes galime suprasti iš tavęs kas aukščiausias asmuo
lyginamosios algoritmas daro tos pačios rūšies.
Taigi, jei esate sėdi orkestro, mano Atsiprašome, tačiau 1 žingsnis, atsistoti;
2 etapas, pora su kuo nors šalia jūsų,
išsiaiškinti, kas yra aukštesni, ir sėdėti, jei yra trumpesnis.
Tada pakartokite.
[Studentai murmantys]
>> Gerai.
Gerai. Vienas liko stovėti. Koks tavo vardas? >> Andrew.
>> Andrew, esate aukščiausias asmuo skyriuje orkestro šiandien.
>> Sveikiname. [Plojimai ir visaip kitaip] Gerai. Patarti. Todėl mes radome Andrew.
Bet kaip ilgai jis ėmėsi mane, pavyzdžiui, rasti Andrew
Šis orkestras skyriuje 50 + arba tiek žmonių?
Aš galėjo gana paprastą požiūrį ir pradėti čia.
Ir aš 2 žmonės atsistoti ir aš tiesiog palyginti juos,
ir tada aš sakau, kas yra šiek tiek trumpesnis, "Gerai, jūs susėsti"
ir aš prisiminti, kas aukštesni asmuo buvo.
Tada aš kartoju, kartoju, kartoju, ir aš pakabinti aukščiausias asmens
kol aš rasti ką nors šiek tiek aukštesni nei jų, o tada
šiek tiek trumpesnis asmuo turi tada atsisėsti.
Bet tame skyriuje Šis orkestras algoritmas, jei n jums,
kiek žingsnių yra kad algoritmas ketina imtis? >> [Studentas] N.
>> Ji ketina imtis n, teisūs, nes blogiausiu atveju, taip sakant,
aukščiausias žmogus yra labai paskutinis žmogus, kad man tiesiog atsitiktinių nesėkme.
Taigi, blogiausiu atveju, šio algoritmo veikimo laikas yra tiesinė, tai n
kur n yra bendras skaičius žmonių erdvėje, problemos dydis.
Ką apie šį algoritmą?
Tas faktas, kad jūs visi atsistojo ir vėl pusė iš jūsų atsisėdo,
pusė iš jūsų atsisėdo, pusė iš jūsų atsisėdo.
Kiek žingsnių, kurie, jei yra n jums čia?
[Studentas] n log n. >> Tai būtų blogiau. Log n.
>> Taigi log n, net jei jūs neturite pakankamai prisiminti, ką logaritmas yra,
dabar, tiesiog vertinu tai, kad jis yra susijęs kažkaip tai perpus sumažinti ir perpus sumažinti ir perpus sumažinti.
Ji neturi būti veiksnys 2. Tai gali būti 3 kartus.
Bet tai tik tos pačios rūšies faktoriaus toks atkartojimas to, problemos dydis prasideda čia
bet tada iš karto eina čia, tai čia, tai čia, tai čia.
Jūs nesate vartojate mažas įkandimų apie problemą, jūs tikrai kapojimo toli
didelis ypu kiekvieną kartą.
Taigi mes turėjome 50 žmonių, tuomet 25, tada 12 ½ arba 13 žmonės stovi,
6 ½ ir tt kol pagaliau tiesiog Andrių neliko.
Taigi, mes ketiname skambinti, kad n log, ir galite įsivaizduoti, tai taip.
Prisiminkite šią nuotrauką čia, kur linijinis algoritmas yra tarsi raudona linija,
geltona linija skaičiavimas 2s algoritmą, kad mes naudojamas skaičiavimo studentams
praeityje, tačiau šiandien Gralis ketina likti tai žalia linija
kur, jei mes dvigubai orkestro skyriuje žmonių skaičių ar ką tik pasakė,
po velnių, tegul turi visą kambarį visiems atsistoti, ne tokia baisi
nes mes maždaug dvigubai, kiek žmonių yra čia,
1 iteracija, ne problema.
>> Mes pastebėjome, Andrew ar kas atsitinka būti aukštesni nei Andrew
antresolėje arba balkonas.
Todėl šį paprastą idėją, kad mes priėmėme labai daug dalyku, telefonų knygos,
suprasti, kad yra tiek daug įvairių vietų, kurioje mes galime taikyti jį.
Tik slap šiek tiek žargono - iš tiesų, o ne žargonu pirma,
leiskite man eiti į šioje nuotraukoje.
Dabar mes kalbėjome apie n ir n / 2 ir tada prisijunkite n,
bet mes tikrai gali sugalvoti, kaip mes per semestro metu,
kitos rūšies matematines formules apibūdinti šį bendrą sąvoką važiavimo laikas.
Tai yra iš kontekste dabar, nes mes iki kol
algoritmai, kuriuos jie iš tikrųjų atstovauja.
>> Bet pastebėsite čia, tiesinė linija n, tiesi linija, yra iš tikrųjų labai mažas nukreipta dabar.
Tai tarsi tik optinė iliuzija, kad mes tiesiog pakeisti tai, kas x ašis rodo
ir y ašis, ir mes galime padaryti tiesios linijos tašką bet kuria kryptimi norime.
Bet priežastis, kad jis toks iš pažiūros butas dabar
nes mums reikia, kad paliktume vietos šioje diagramoje daug lėčiau veikia laikais.
Dabar, žinau, kad yra keletas gana blogi gyvenime algoritmai,
kai kurie iš jų neturi imtis n veiksmus arba, dar geriau, log n veiksmus, bet daugiau.
Taigi virš linijos n čia apačioje pranešimas yra log n n kartų,
ir mes pamatyti, ką tai reiškia iki kol.
Svarbiausia, kad yra n langeliais, ir mes nematėme jokių n kvadratu algoritmai dar, bet mes apie tai.
Ir, kad atrodo tikrai neblogai.
Yra 2 n kažkas eksponentinis, kuris jaučiasi dar blogiau.
Ir vis dėlto, kaip bebūtų keista, ten n Cubed, kuri, jei esate tarsi galvoti į priekį,
jei jūs tipo padaryti matematikos, 2 n faktiškai tampa daug tiesesni,
daug didesnis nei n kubeliais, jei peržvelgsite ašių pakankamai toli iš.
Taigi pastebėti dabar Šios ašys yra savavališkai 2 10 x ašyje.
>> Ir ką tai reiškia?
Tai reiškia, kad 2 žmonėms iki 10 žmonių kambaryje.
Štai ir viskas x reiškia: problemos dydis, bet kontekstas.
Ir dabar yra vertikali ašis skaičius sekundžių ar pakopų skaičius -
kai laiko vienetas.
, Bet pastebėsite, kad tai 0 iki 60 ir 0-10.
Bet jei mes tipo zoom out, kaip jums gali "Excel" arba kai grafikas programinės įrangos,
ir mes einame iki 200.000, pastebėsite, kad kažkas kaip 2 iki n
vyksta visiškai sukrėsti n kvadrato rodymo laikus,
n kubeliais, n log n - viskas, mes kalbėjome apie iki šiol.
Ir dar laimikis, kai pradėsite kalbėti apie tokius dalykus kaip "Facebook"
kur jūs visi tarpusavyje susiję, daug, daug, daug žmonių
jūs n žmonių, iš kurių kiekvienas gali turėti tiek, kiek n draugams
jei visi tarsi Buddy Buddy pasaulyje,
gerai, kad n kartų jau taip, kad n kvadratu galimus draugystę,
bent 1 kryptimi, n kvadratu galimų draugystę.
Taigi, tai jau rodo, kad ieško "Facebook" socialinį grafiką, taip sakant,
galite pradėti, turi būti išreikštas šių formulių rūšių.
>> Mes grįžti ir padaryti tai daug konkretesni,
bet dabar, per ateinančius daugelį savaičių tikslas
bus tikrai ne eiti apie įgyvendinimo algoritmų arba kodą
kad galų gale tiek pat laiko, kaip kažką panašaus į tai.
Bet Įspūdingiausias dalykas apie kompiuterių mokslo, jei ir toliau šioje srityje
atsižvelgiant klases, pavyzdžiui, CS121, CS124, kurie abu yra teorija kursai,
yra tai, kad ten iš tikrųjų yra šiame pasaulyje egzistuoja tam tikros problemos,
, kad iš esmės, kiek mes žinome, negali būti išspręsta bet greičiau
ne blogiausias šių grafikų tikrai rodo.
Taigi čia daug atvirų problemų šiame pasaulyje, tai padaryti kur kas geriau nei žmonės iki šiol.
>> Taigi, pradėkime tada su šiuo pavyzdžiu.
Mes matėme, Sean kovą su šio fotoaparato, visi per nerangiai ant vaizdo.
Tačiau realybė buvo, kai Sean buvo pavesta rasti ant lentos, kaip šis numeris 7
priminti, kad aš sakė, kad "yra kažkur už šių popieriaus vienetų ar baltos durys
Skaičius 7. Sean, rasti tai už mus. "
Ir ji buvo nuostabiai nepatogu žiūrėti
, nes jis buvo tikrai kovoja su šia problema.
Tačiau realybė buvo Sean taip pat gerai, kaip galėjo padaryti kas nors į kambarį.
Jis užtruko šiek tiek ilgiau nei tipiškas asmuo gali turėti
bet jis manė, kad buvo tam tikras triukas su šia problema,
jis manė, kad jis kažko trūksta.
Ir tai nepadėjo, kad šimtai akis turint ant jo.
>> Tačiau realybė buvo, jei įėjimo į problemą yra atsitiktinių skaičių krūva
ir jūs paprašė rasti 1 toks,
geriausia, ką galite padaryti, yra tiesinė paieška ".
Pradėti kairėje, pasislinks į dešinę, arba pradėti dešinę, judėti į kairę.
Atgaline data, gali būti mąstymas, "Sean, kodėl ne jūs tiesiog pradėkite iš kitos pusės?
Na, 7 galėjo taip pat lengvai buvo čia atsitiktinai,
bet aš sąmoningai jį ten, nes aš raštuotas, kad jis nesiruošia pradėti pabaigoje.
Taigi I rūšies manipuliavo situaciją, bet atsitiktine atsitiktinai 7 galėjo būti bet kur.
Taigi pradedant nuo dešiniajame krašte galėjo geriau tada,
bet kas, jei kitais metais aš perkelti 7 kitur?
Tai nėra iš esmės naujas problemos sprendimas -
nuo 1 dalies pabaigoje ar kita - kai jums suteikta jokių kitų prielaidas.
Taigi Sean pradėjau ieškoti per skaičių ir jis tarė: "5. Štai čia nėra".
Tada jis nuėjo čia ir pamačiau 19, tada jis stabtelėjo apie 20 sekundžių,
tada jis pradėjo tai 13, o tada tapo aišku,
, kad neatrodo, kad būti modelis.
Tai buvo ne 1, 2, 3, 4 arba panašūs. Nebuvo spragų skaičių, nepadėjo.
Ir taip pat tai, kad aš naudojamas šių pigių popieriaus lapų padengti skaičius
iš tiesų yra sąmoningas, nes, jei aš pašalinti visus šiuos popieriaus likučių,
dauguma iš mūsų, Sean vietoje, tikriausiai pažiūrėjau tarsi makroskopiškai
lentos ir sako: "O, 7, žinoma, teisę ten." Mes tai padarė akimirksniu.
>> Ir tai gali būti žmogaus smegenys veikia tam tikru mastu,
bet iš tikrųjų, jo akys ar protas tikriausiai nuovirų skaičius iš dešinės į kairę,
kairės į dešinę, iš vidutinio, kad kažkas fiziologiškai
tokia, kad ji pajuto, kaip ji vyksta akimirksniu,
tačiau šansai yra net viduje buvo kai metodikos natūra rasti 7.
Ir iš tiesų, dabar, kad mes kalbame apie matricas ir duomenų struktūros
ir atminties viduje kompiuterio, vienintelis dalykas, mes, žmonės gali padaryti
, tai pažvelgti į atskirų atminties vietas 1 metu.
>> Taigi, kas kita vieta taip pat gali būti taikoma kai popieriaus lapo
nes mes negalime matyti jį vistiek. Mes galime padaryti tik 1 dalyką vienu metu.
Taigi šiuo atveju, Sean atveju, mes nuėjome čia ir tada mes Eime čia
ir tada mes Eime čia, čia, čia, čia, gavo protingas pabaigos
ir tiesiog rūšies praleisti šį vieną savavališkai ir rasti 7 ten.
Tai vienas nebuvo ypač ypatinga. Jis taip pat buvo ne iš eilės.
Bet jis pagaliau rado 7.
Bet dabar išsinešimui tikrai, kad geriausia, ką galite padaryti, kai jokios informacijos
išskyrus atsitiktinai surūšiuoti numerių yra pradėti iš kairės arba pradėti iš dešinės.
Ar gi, galite atsitiktinai atverti duris, tačiau net ir tada, ką tai reiškia būti atsitiktinai?
Na, mes norime kažkaip formalizuoti, ką reiškia pradėti čia,
tada eikite čia, tada eikite čia. Sean padarė puikus, ir tai buvo tiesiog smagu žiūrėti.
Ką daryti, jei vietoj mes pakeisime šią problemą šiek tiek ir auklėti šių metų Sean, jei bus?
Ar kas nors ateina ant scenos ir spręsti kiek kitokia problema
ir ant fotoaparato?
>> Eikime ne tik orkestro, nes jūs, vaikinai buvo gana dalyvauja jau šiandien.
Kaip apie rožinės spalvos, skrybėlę? Nagi žemyn. Koks yra tavo vardas? >> Alex. >> Alex. Gerai.
Taigi Alex bus šiemet Sean ir pasirodys per artimiausius kelerius metus
verta CS50 paskaitų.
Alex, nice to meet you. >> Nice to meet you too.
Po ranka jums iššūkis yra tai, kad jūs turite jį šiek tiek lengviau
aš sakau tuos pačius numerius čia, bet dabar jie yra rūšiuojami.
Taigi dabar, jūsų tikslas yra rasti skaičių 7.
Ir iš tikrųjų, mes turime tikrai padaryti tai - sukčiavimo! Galite rūšies, kaip kompiuteris,
žiūri, ką buvo metu senumo.
Su kreida tai tikrai nesiruošia padėti visiems, kad daug,
bet galime apsimesti, kad jūs nežinote, kokios originalaus masyvas.
Visi žinote, dabar, kad jūs turite surūšiuoti skaičių masyvas
tai gali turėti tarpus tarp jų, ir jūsų tikslas yra rasti skaičių 7.
Kaip jūs, protingas žmogus, eikite rasti 7?
>> Pereiti nuo mažo iki didelio? >> Gerai. Eiti mažo iki didelio.
Ir ne ašara juos išjungti. Tegul tik juos panaikinti, todėl mes galime juos pakartotinai.
Gerai, kad 1. Palaukti. Kas žinotina prieš nesustoti, kad buvo 1, akivaizdžiai neteisinga.
Taigi, kas vyksta per savo proto toliau? , Kas yra jūsų kitą žingsnį?
Kitą. >> Gerai. Kitą. Geras. 3, toks netinkamas. , Kas yra jūsų kitą žingsnį?
Laikyti vyksta. >> Gerai. Laikyti vyksta. 5.
Todėl nuolat vyksta, ir leiskite man perduoti jums tai ateinančioms kartoms.
7. >> Excellent. Labai geras. Rasta skaičių 7. [Plojimai]
Kad buvo geras, bet per Sean rado 7.
Ir esu įsitikinęs, kad jūs ne iš tikrųjų panaudojo šią informacijos dalį,
yra tai, kad šie skaičiai yra rūšiuojamos.
Taigi galime padaryti geriau? Bet kokie pasiūlymai čia? Taip, atgal.
[Studentas] Dvejetainis paieška. >> Aš neįsivaizduoju, kas dvejetainis paieškos.
>> [Studentas] Pradėti viduryje. >> Pradžia viduryje. Gerai. Taigi pažiūrėkime, jei mes galime gauti ten.
Taigi, jei vietoj jums liepė pradėti nuo vidurio, eiti į priekį ir atidaryti vidurinių durų.
Yra 8 iš jų, kad jūs ketinate turi savavališkai pasirinkti vieną
šiek tiek į kairę arba į dešinę. Gerai. 7! [Plojimai] Very nice.
Gerai, bet kur buvo mes su tuo?
Sakykime, tiesiog nutraukti lygiąsias jums čia buvo pradėta
nes tai taip pat galėjo atsitikti, taip pat.
Mes tiesiog atsitiko žinoti, kad 7 ten buvo. Taigi, tai yra 13.
Taigi, jei jie rūšiuojami ir mes ką tik pradėjo per vidurį,
kas būtų optimalus Kitas žingsnis buvo?
Eiti į kairę. Ir todėl čia ateina telefonų knygos pavyzdys dar kartą.
Jei 13 yra čia, ir mes žinome, sąrašas surūšiuotas,
tada visi iš šių popieriaus vienetų neįdomu mums dabar
nes mes jau žinome, kad 7 turi būti į kairę
jei šie skaičiai yra rūšiuojamos ir mes nustatėme 13.
>> Taigi, kas yra jūsų kitą žingsnį čia? >> Eikite į kairę. >> Gerai, gerai.
Taigi, eikite į kairę, ir - laukti, ei, ei, ei. Kad sukčiauja.
Taigi jums rasti 7, bet tai, ką mes tiesiog taikomas algoritmas?
Pradėti viduryje. >> Gerai. Taigi, kas yra logiška tą pačią sąvoką?
Oh, tik jie. >> Būtent. >> Ir aš pradėti čia. >> Gerai.
Taigi dabar mes nuėjome šiek tiek į kairę dar kartą. Tai 3.
Tačiau įdomu išsinešimui, kuris iš jų padaryti, jūs neturite rūpintis?
Tai 2. >> Tai 2. Taigi, dabar tai galima eiti toli, tai galima eiti šalin.
Dabar problema, kad buvo 8 tada dydis 4 dydis 2.
Mes gauname gana arti. Vėl eiti iš šių 2 elementų viduryje.
>> Gerai. Taigi, tai tarsi gaila, kad dabar mes visada bus paliktas, nes mes apvalinimas iki mažesnio skaičiaus.
Bet tai gerai, nes dabar mes išmetame šį toli ir visa kita, o mums vos 7.
Leiskite duoti plojimų. Mes radome 7 dar kartą. [Plojimai] Gerai. Tikrai.
Pakabinti ant tik 1 sekundę.
Net jei tai kita proceso rūšies užtruko šiek tiek ilgiau, nei mes manėme, kad būtų
tiesą sakant, jūsų instinktai buvo geriausias, tiesa? Mes radome 7 akimirksniu.
Bet mes radome 7 greičiau, nesvarbu ką, šiame pavyzdyje, palyginti su šį vieną
nes jei skaičiai yra rūšiuojami, panašiai kaip telefonų knygos puslapiuose,
jūs iš tiesų gali pjaustyti pusę problemos vėl ir vėl ir vėl.
Ir tai nėra taip paprasta, tai tik su 8 numeriais
, palyginti su 1000 puslapių telefonų knygoje, kur jūs tikrai matyti vizualiai,
bet šiuo atveju čia Sean ieškojau 7
kiek žingsnių blogiausiu atveju ji ėmėsi jį? >> [Studentas] 7.
7 blogiausiu atveju. Na, blogiausiu atveju, ne 7, jei yra čia 8 durys.
Ji ėmėsi jam 8 žingsnių.
>> Taigi, jei ten n durys, jis gali Sean prieš porą metų n veiksmus.
Dabar, jūsų atveju, Alex, atsižvelgiant į tai, kad šie skaičiai yra rūšiuojamos -
ir mes galime kildina šio tipo iš kur mes buvome iki šiol šioje istorijoje -
kas Alex racionalesnį algoritmo veikimo laikas
pradedant nuo vidurio ir tada kartoti?
[Studentas] 3. >> Taigi tai bus 3, maždaug, jei jūs einate 8-4 2-1.
Taigi 3 žingsnius arba, apskritai, tai log n vėl.
Kiekvieną kartą, kai perpus sumažinti perpus sumažinti ir perpus sumažinti ir perpus sumažinti,
kad išraiška šio log n idėjos.
Ir kad būtų imamasi tik 3 žingsniai, ir ji tai padarė
kai mes atidarėme durys perpus sumažinti ir perpus sumažinti
kadangi dėl to ėmėsi Sean apie 7 ar 8 veiksmus.
Tad ačiū už tai, kad pas mus šiais metais. >> Ačiū. Malonu buvo susipažinti.
Dėkojame, Alex. >> Taip pat. [Plojimai]
>> Tai, kas tikra potekstė?
Dabar įsivaizduokite, kad tai ne 8 durys, kurios, tiesą sakant, visi iš mūsų galėtų rasti kažką
atsilieka 8 durys gana greitai, tik popieriaus likučių ašarojimas ir vyksta su savo instinktus.
Bet kas, jei tai milijono durys? Kas, jei tai 4 mlrd. Durys?
4 mlrd durų, jūs tikrai ketinate nori eiti su Alex algoritmas,
dvejetainis paieškos, nes mes pradėsime vadiname tai, skaldyk ir valdyk, apskritai,
kur norite išsaugoti perpus sumažinti ir perpus sumažinti šią problemą,
nes jei turite 4 mlrd. Durys, kiek kartų galite pjaustyti 4 milijardus 1/2?
[Studentas] 32. >> Iš tikrųjų 32. Galite dirbti tai ant popieriaus lapo ar savo galva.
Jūs einate, kad 4 mlrd. Iki 2 mlrd. Iki 1 mlrd. Pusė milijardo iki 250 milijonų eurų, DOT, DOT, taškas.
Ir jei jūs matematikos, jūs ketinate iš tikrųjų gauti 32,
ir kad iš tikrųjų susijęs su kompiuterių mokslo, nes mes paprastai skaičiuoja galių 2.
2 iki 32 atsitinka, yra 4 mlrd.
Taigi yra daug reikšmės šių galių 2 rūšių kompiuterių mokslo.
>> Bet tai, ką apie 8 mlrd.? Kiek žingsnių, kad ketina imtis, jei yra 8 mlrd durys?
[Studentas] 33. >> Taigi 33. Ką daryti, jei 16 mlrd durys? Kiek žingsnių yra tai, kad ketinate imtis?
[Studentas] 34. >> 34. Mes galime rūšies šį znudzenia. Bet tai galingas dalykas.
Galite įvesti daugiau duomenų milijardus į savo problemą, bet, ne big deal,
jūs tiesiog gerti po 1 papildomą Užkandote iš jo ir tokiu būdu suteikia mums kažką panašaus dvejetainis paieškos
arba skaldyk ir valdyk apskritai.
Bet aš natūra apgaulės čia, tiesa?
Alex algoritmo atveju, ji turėjo prieš Sean pranašumą.
Ji žinojo, kad šie skaičiai buvo rūšiuojamos, tačiau Aleksas neturėjo juos surūšiuoti save.
Aš priėjo prie lentos ir rūšis pasirūpino iš anksto
, kad aš atkreipė juos visus iš rūšiuotų tvarka, tada aš, kuriems juos su popieriumi.
Bet, kiek darbo, kad mane suprantate?
Jei būtume prasidėjo nuo šių kai iš pažiūros atsitiktine tvarka numerių
šiuo atveju tie paprastesni numeriai, 1 iki 8 čia -
kaip mes eiti apie rūšiavimo šias vertybes?
Jei buvo žmogus, nes ši užduotis, kokios intuityvaus požiūrio imtumėtės
rūšiavimas visa krūva skaičių?
Šie dalykai buvo išdėstyti kaip puzzle. Taip.
>> [Studentas] Norėčiau imtis kiekvieną skaičių ir palyginkite jį į kiekvieną iš jų
ir nesustoti į kairę. >> Gerai, gerai.
Taigi, prieš priimdami kiekvieną numerį, palyginti ją su šalia jo,
ir tada tiesiog nuolat juda kartu sąrašą, rūšies rejiggering dalykų, kaip jūs einate.
Taigi čia mes turime gal keli žmonės galimybę įsitraukti.
Ar mes turime 8 daugiau savanorių, kurie mėgsta sugalvoti?
Šiek tiek mažiau slėgis, nes jūs ne vienintelis. 1, 2, 3, 4, 5, 6, 7, 8.
Nagi žemyn. Jus vaikinai bus numeriai nuo 1 iki 8.
Pažiūrėkime, jei mes negalime padaryti šį rūšiavimą Alex daug tokiu pačiu būdu, aš padariau jį iš anksto.
1, 2, 3, 4.
Eiti į priekį ir, jei galėtumėte, linija ant scenos tarp muzikos stovas ir man čia
ta pačia tvarka, kaip ekrane skaidrės.
Uh-oh.
Mes padėsime jums į Kitame pavyzdyje. Oi, palauk, palauk. Čia mes einame. Palaukti.
Kitas pavyzdys yra dabar. Here you go. Numeris 8. Ateiti iki.
Gerai. Rūšiuoti patys pagal.
Tik šiek tiek pastumkite į muzikos pusės čia stovėti.
Taigi, mes turime 4, 2, 6 - gauti ten, čia, tiesiai ten - 3.
Taip. Gerai. Jūs eikite čia. Ne, jūs ten pasilikti.
Taip, teisingai. Ne, aš neteisus. Teisę ten. Gerai, labai gerai. Gerai.
Taigi dabar galime juos surūšiuoti didėjimo tvarka.
>> Kaip aš galiu eiti apie tai daryti?
Algoritmas, kuris buvo pasiūlyta prieš akimirką buvo, kodėl gi ne, mes tiesiog palyginti
rūšies žmonės, kurie yra šalia vienas kito, ir tada nustatyti klaidas,
juda iš kairės į dešinę.
Taigi čia mes turime 4 ir 2, žinoma, ne iš eilės. Tegul apsikeitimo jums. Gerai.
Taigi, dabar aš ruošiuosi judėti žemyn linija. 4 ir 6, nope. [Juokas]
6 ir 8, gana gera. 8 ir 1, leiskite man apsikeitimo jums vaikinai. Gerai.
Taigi 8 ir 3, apsikeitimo jus vaikinai.
8 ir 7, leiskite man apsikeitimo jums vaikinai. 5 ir 8, puikus.
Aš duosiu jums surūšiuoti sąrašą.
Gerai. Taigi, ne gana.
Bet tai geriau, nes didesni numeriai - case 8 punkte -
buvo rūšies burbuliukų iš kairės į dešinę.
Kad aš gavau iš jų 1 teisus, bet jis jaučiasi ne visiškai išspręsti šią problemą.
>> Taigi, ką siūlytumėte mes darome toliau? >> [Studentas] Laikyti tai daro. >> Mes nuolat tai daryti.
Ir suprasti, ir vėl, mes nustatyti dalykus tiesiog visus žmones
tarsi protingai pasirūpinti, kad vaizdas,
bet dabar mes turime būti daug daugiau metodinis.
Mes turime Algorithmic apie tai, bet mes rašyti kodą -
į Šiuo atveju žodinis pseudocode.
Taigi, leiskite man tiesiog pabandyti, kad vėl. Kad dirbo gana gerai. Jis nebuvo išspręsti.
Bet kai jis abejoju, tiesiog pabandykite ir bandykite dar kartą. SO 2 ir 4, nebėra nepadėjo.
4 ir 6. Ah! 6 ir 1, šiek tiek geriau dabar.
6 ir 3, geras. 6 ir 7, 7, 5, 7 ir 8, gerai.
Ir žinote, aš galiu tikriausiai ignoruoti 8, nes dabar jis yra sąrašo pabaigoje.
Gal mes neturime nerimauti, kas nors vyksta pro jį.
Bet pažiūrėkime, jei tai saugi prielaida.
Dabar sąrašas - Damn - nėra rūšiuojamos. Pabandykime tai vėl.
SO 2 ir 4, 4 ir 1, 4 ir 3.
4 ir 6, gerai. 6 ir 5, gerai.
6, 7, 8, gerai. Tačiau pastebėkite, galiu tiesiog nustoti čia dabar ir čia sustoti dabar?
[Studentas] Taip. >> Taip?
Ką daryti, jei vienas iš jūsų buvo numeris 9 visą kelią ten?
Jis buvo išrūšiuotos. >> Gerai. Jis būtų buvęs rūšiuotas pirmą kartą aplink.
Geras. Taigi eikime atgal. Mes beveik ten.
1 ir 2, 2 ir 3, 3 ir 4, 4 ir 5, 5 ir 6, 6 ir 7, 7 ir 8.
>> Aš padaryti, bet dabar, dar kartą, aš tikiu, kompiuteris, kuris gali padaryti tik tai, ką aš negausite,
ir mano tik prisiminimas dabar yra tai, kad aš iš tikrųjų tiesiog padarė šiek tiek darbo.
Čia kažkas pasikeitė.
Todėl aš ne techniškai patvirtino vizualiai ar algoritmiškai kad šis sąrašas būtų iš tikrųjų surūšiuoti.
Taigi, tiesiog gera priemonė, tiesiog, kad būtų analinis apie tai, leiskite tai padaryti 1 daugiau laiko.
Taigi 1 ir 2, 2 ir 3, 3 ir 4. Ir žinote ką?
Tiesiog gera priemonė, aš sekti mano ranka šį kartą
kiek apsikeitimo sandoriai aš, kad tik todėl, kad aš žinau, kiek daug darbo aš iš tikrųjų padaryta.
3 ir 4 dalis, 4 ir 5, 5 ir 6, 6 ir 7, 7 ir 8. Nėra apsikeitimo sandoriai.
Taigi dabar norėčiau teisėtai idiotas tai padaryti ir vėl,
nes jei aš jokio darbo per šio žmonėms praeiti,
tada aiškiai, kad nutiks dar kartą, jei nė vienas iš jų yra tarsi atsitiktinai
adversarially juda aplink. Taigi, dabar galiu sustoti.
Dabar galime užduoti klausimą, kiek daug darbo tai iš tikrųjų imasi domėjosi?
Kiek žingsnių imtis? >> N kvadratu.
Taip, kad n kvadratu. Kur jūs gaunate n kvadrato?
Jūs turite patikrinti kiekvieną num
Yra n numeriai, ir jūs turite patikrinti kiekvieną su kitomis n skaičių.
Geras. >> Taigi tai n kvadratu. >> Gerai.
>> Todėl mano, kad jis galėtų labai gerai būti n kvadrato, tiesa?
Ten n iš šių vaikinai, 8 konkrečiai šiuo atveju,
bet kiekvieną kartą, kai aš per šį sąrašą buvo lyginant pirmasis asmuo prieš antrąjį,
prieš apdraustą trečiąjį asmenį vėl ir vėl ir vėl,
ir kai aš iki galo, ką aš galiu padaryti? Aš redid.
Taigi, jei mes apibendrinti šį paaiškinimą, mes n žmonėms
ir aš padaryti, be abejo, 8 žingsnių, n žingsnius, kiekvieną kartą, kai aš einu per šio algoritmo.
Bet kiek kartų blogiausiu atveju aš turiu eiti per šį sąrašą žmonių?
[Studentas] N kartų. >> Tikriausiai n teisūs, nes blogiausiu atveju,
kas tikriausiai blogiausiu atveju susitarimas iš šių vaikinai nuo get-go?
Jei jie visiškai priešinga tvarka
nes tik tarkime protiškai, let's - Koks tavo vardas? >> Bowen.
Bowen. Gerai. Taigi, Bowen, atėjo čia dėl vos akimirką.
>> Tarkime, kad Bowen algoritmo pradžioje čia buvo,
ir mes negalime žinoti, ką visi kiti, bet Bowen čia, pagal šio algoritmo
ir, jei norite, tiesiog pasivaikščioti su manimi vyksta burbulas iki, kaip jis pirmą kartą aplink,
visą kelią iki pabaigos.
Tačiau tarkime, kad asmuo šalia Bowen buvo numeris 7.
Turiu grįžti ir gauti 7 skaičių, o tai reiškia, aš turiu eiti visą kelią atgal čia.
Dabar turiu turėti tą patį pasivaikščioti su asmeniu, kuris yra numeris 7.
Bet kas, jei tada 6 numeris buvo šalia jo, taip pat?
Tada aš turiu grįžti ir gauti 6.
Taigi dar kartą, aš kalbu apie kiekvieną šio ciklo iteracijos n žmonių,
ir aš galėjo padaryti N šių pasivaikščiojimo įsitikinkite, kad Aš traukiant
visų didžiausių elementų atgal ir atgal ir grįžti prie sąrašo galo.
Taigi n dalykų n kartų yra tik n kartų, n arba n langeliais.
>> Taigi čia jau mes turime algoritmą, kuris nebėra n, tai nebėra log n,
tai tikrai blogiau nei ką mes padarėme anksčiau.
Taigi Alex rūšies pasisekė, kad aš darbo, matyt, iš anksto jai,
visi brangaus darbo, kad ji galėtų mėgautis šio dvejetainis paieškos algoritmas,
log n.
Bet tai yra atitikti pirmadienio tema.
Mes davėme šiek tiek daugiau vietos, daugiau bitų, siekiant paspartinti mūsų veikimo laiką.
Tiek daug, kaip ten tai kompromisas tarp laiko ir erdvės,
taip pat gali būti tiesiog nušviečia kompromisus tarp laiko praleisto priekyje rūšiuoti gauti dalykų pasiruošęs eiti
ir faktiškai vykdyti, pavyzdžiui paieškos algoritmas. Pabandykime dar vieną.
Jei jus vaikinai nebūtų proto, tiesiog greitai pertvarkyti save, kad atitiktų, kad vėl,
galime pabandyti kažką šiek tiek kitokį, kur jis yra ne visai taip paprasta
kaip tik išspręsti visas Poromis klaidų, kurios yra super intuityvus.
Tegul vietoj to turi būti šiek tiek labiau apgalvotas ir tai padaryti.
Tai irgi norėčiau pasiūlyti yra tikriausiai gana intuityvus.
>> Leiskite pasirinkti mažiausią asmenį iš sąrašo, vėl ir vėl. Taigi čia mes einame.
4, jums yra mažiausias asmuo, todėl aš mačiau iki šiol,
todėl aš protiškai prisiminti, kad tik nukreipta į jus dabar.
2. Ooh! Pamirškite apie skaičių 4. Aš ką tik nustatė naują mažiausią elementą šiame sąraše.
Aš ruošiuosi rūšies prisiminti, kad. 6, 8.
Ooh! 1. Viso gero. Taigi, dabar aš ruošiuosi prisiminti skaičių 1.
Mes žinome, kad 1 yra mažiausias, bet aš tikiu, kad kompiuteris. Ką daryti, jei ten 0?
Ką daryti, jei -1? Turiu nesustoti.
Taigi, 3, 7, 5, nope. Gerai. Taigi buvo mažiausias skaičius 1.
Leiskite man pasirinkti iš sąrašo - we'll eiti šiuo keliu -
ir padėti jums savavališkai sąrašo pradžioje.
Dabar, palauk. I rūšies apgavo.
Jei šie vaikinai atstovauja ne 8 žmonių sąrašą, tačiau masyvo,
8 gabaliukus vientisos atminties - jūs tai trauktis atgal vos akimirką?
Yra tikrai ne jums erdvė čia.
Taip, kaip mes padaryti vietos - koks tavo vardas? >> Sammy. >> Sammy.
Kaip mes vietos Sammy?
>> Mes einame n, kurie yra prieš mane. >> Gerai.
Taigi, mes galime perkelti n žmonių, kurie yra prieš jį,
todėl, jei jus vaikinai nori imtis 1 apgalvotą, dramatiškas žingsnis į kairę.
Jie visi sutartinai, bet paskutinį kartą aš parašiau tam tikrą kodą,
Jūs negalite rūšiuoti perkelti daug dalykų vienu metu.
Mes galime tai padaryti kilpą, juda visiems, vieną kartą.
Taigi, jei jus vaikinai nebūtų proto, trauktis atgal į dešinę,
ir Sammy, jei galima žengti žingsnį atgal, nes ten dar ne jums,
dabar galime tai padaryti. Kur buvo Sammy prieš akimirką? Teisę ten.
Taigi čia yra atotrūkis. Kad galėtumėte perkelti į Sammy savo vietoje.
Dabar kitas asmuo ir dabar kitas asmuo, o kitas asmuo. Dabar mes turime kambarį Sammy.
Dabar kas nors iš auditorijos - tai buvo geras, tai buvo teisingas,
ji jautėsi šiek tiek daug laiko - kas greičiau? Taip.
[Studentas] nauja matrica? >> Kas tai? >> [Studentas] nauja matrica? >> Gerai, gerai.
>> Taip nuosekliai šio tik kompromisų tema, kodėl ne aš tiesiog padaryti naują masyvą,
ir tada Sammy bus plaukiojimas erdvėje priešais šių žmonių, pavyzdžiui,
ir mes galime tiesiog pradėti pildyti naują masyvą, apskritai. Kad per daug dirbtų.
Bet aš ne domina išleisti daugiau vietos šiandien. Kas kitas požiūris?
[Studentas] swap. >> Gerai. Galėtume tiesiog apsikeitimo šių 2 vaikinai. Koks tavo vardas?
Mario. >> Mario. Taigi, Mario, šiuo metu čia.
Sammy, galite kurti atsargines kopijas vos akimirką? Mario buvo čia.
Mes neturime jums kambarį nebėra, todėl, jei tai būtų ne tai vyksta kur Sammy,
mes įdėti Sammy čia, ir dabar aš teigia, kad Sammy apsikeitimo operacija buvo daug greitesnis.
Mes padarėme 1 operaciją apsikeitimo šie vaikinai, o gal 2 apsikeitimo šie vaikinai,
bet mes ne padaryti 1, 2, 3, 4, kad jaučiasi geriau. Dabar, palauk.
I rūšies problema dar blogiau, nes numeris 4 buvo natūra arti pradžioje.
Numeris 4 yra šiek tiek priartėti prie šio tikslo, bet aš tikrai nežino, ar rūpi tai.
Taigi tai yra tiesiog nesėkme, kad numeris 4 yra šiek tiek toliau nuo jos lemta vietoje.
Taigi tegul dabar pakartoti šį algoritmą.
>> Apibendrinant galima pasakyti, kaip ilgai, kaip kad istorija buvo, visi mes darė, buvo eiti per sąrašą
ieško mažiausio numeruojama asmens.
Taigi dabar galime tai padaryti dar kartą. Mes neturime nerimauti dėl Sammy nebėra.
Mes galime tiesiog eikite čia. Ooh! Numeris 2. Tai yra gana nedaug.
6, 8, 4, 3, 7, 5. Gerai, gerai.
Ir, laimei, sutapimas, aš neturiu judėti - >> Willie.
Willie, nes jis dabar jo tinkamą vietą.
Leiskite tai padaryti ir vėl, ir nekreipti dėmesio į šiuos 2 vaikinai.
6. Tai yra gana nedaug. Ooh! 8 yra tikrai didesnis.
4. Leiskite sutelkti dėmesį į 4. Ooh! 3 yra net geriau.
7 ir 5. Taigi, ką mes darome dabar - >> Roger. >> Roger?
Tegul sukeisti jį su skaičiumi 6.
Taigi, jei 6 ir 3 norėtų sukeisti,
dabar mes tipo Dotarłeś pasisekė, kad 6 yra arčiau, kur ji turėtų būti,
bet tai tik sutapimas čia. Taigi, tegul dabar eikite čia.
8 yra gana mažas skaičius. Ooh! 4 yra mažesnis.
6, 7, 5. Ką dabar daryti? >> Sukeisti. >> Būtent.
Taigi dabar galime tai padaryti greičiau rūšiuoti.
8, 6, 7, 5. Kur gi 5 eiti? Geras. Gerai.
6, 7, 8. 6 gali likti ten, kur ji yra. Koks tavo vardas? >> Rozali.
Rozali gali likti ten, kur ji yra. 7 gauna į Pažiūrėkime. 7, 8. Gerai.
Taigi 7 gali likti ten, kur ji yra. Koks tavo vardas? >> Amna. >> Amna.
>> Taigi Amna gali likti ten, kur ji yra, ir skaičius 8 jau yra, kur jis dabar turėtų būti.
Gerai, gerai. Jaučiasi kaip mes tiesiog sukurti sau darbą čia, nors.
Tai, kas galiausiai šio algoritmo veikimo laikas?
Jei mes galvojame apie žmonių, ne kaip 8, bet kaip n? >> Tai n.
Tai n žingsniai, bet mes patikrinti kiekvieną kartą.
Gerai. N, bet jūs patikrinti kiekvieną kartą?
Gerai, bet jei jis n veiksmus, turėtų ne aš buvo galima rūšiuoti jums tiesiog 1, 2, 3, 4?
Oh! Gerai, kad yra didelis skirtumas.
Taigi n kvadrato kodėl? Kas iš tikrųjų vyksta?
Yra n žmonių šiame sąraše, bet rasti mažiausią asmuo sąraše
blogiausiu atveju, kiek žingsnių turiu imtis? >> N.
>> N, teisė, nes blogiausiu atveju, numeris 1 yra ten būdas,
taip, aš turiu eiti gauti jam ar jai.
Ir tada, kai aš pagaliau suvoks, 1 buvo mažiausias, tada ji gana greitai apsikeitimo juos.
Bet dabar aš turiu pradėti nuo pradžių ir ieškoti, kas?
Kitas mažiausias asmuo, kuris yra 2. Jeigu blogiausiu atveju yra 2?
O, Dieve. Tai visi čia būdas pabaigoje.
Todėl dabar aš tiesiog padaryti dar n žingsnių, dar n žingsnių.
Ir jei mes turime n žmonių, o blogiausiu atveju mažiausias asmuo n žingsniai,
tai vėl n times n, tad vėl buvo n kvadrato.
Tai nėra jausmas toks geras.
Ir iš tiesų, net ir geriausiu atveju - manyti, kad jie pradėti nuo surūšiuoti -
kiek žingsnių užtruks mane, naudojant šį algoritmą norite surūšiuoti šių n žmonių?
N kvadratu. >> Aš girdėjau n kvadratu. Kodėl kvadrato n?
Nes jūs vis dar turi patikrinti kiekvieną kartą. >> Taip.
Ir jūs turite apsikeitimo juos. >> Nors mes, žmonės, rūšies visažinis
ta prasme, vizualiai, kad mes galime tiesiog rūšies matyti, kad tai yra rūšiuojamos,
kompiuteris yra ne tai, kad protingas.
Ji ketina rasite čia ir čia ir čia,
bet jei tai, ką jis ieško yra mažiausias elementas,
žinote tik, kad jums rasti mažiausią elementą, ką taškas? Kai esate pabaigoje.
Bet tuo momentu jūs tik šiuo metu mažiausią elementą.
Jūs nebūtinai žinoti dar ką nors apie pasaulio būklę.
Taigi jūs turite eiti vėl ir vėl ir vėl.
>> Todėl šį kartą aš tikrai atrodo kvailas, nes aš patikrinti, gerai, 2, jūs mažiausias,
bet aš nemanau, žino, kad iš viso dar.
3, 4, 5, 6, 7, 8. Gerai, gerai. 2 iš tikrųjų buvo mažiausias.
Dabar galime rasti kitas mažiausias. Gerai.
3, jūs šiuo metu mažiausias. Pažiūrėkime. 4, 5, 6, 7, 8. Gerai, vėl pasisekė.
3 buvo tikrai tinkamoje vietoje. Bet aš ruošiuosi išlaikyti tai daryti vėl ir vėl ir vėl.
Kaip mes galime padaryti, vis tiek šiek tiek geriau?
Vietoj to, kad žmonės burbulas poravimas nuo mažiausio iki didžiausio
ir vietoj vyksta pirmyn ir atgal per sąrašo pasirinkdami tada mažiausias asmuo,
kodėl ne mes, o ne įterpti šiuos žmones į naują sąrašą žingsnis po žingsnio?
Pabandykime tai. Dabar leiskite man skambinti šis dalykas įterpimo rūšiuoti.
Taigi čia mes esame čia. Numeris 1. Man nerūpi niekam šiame sąraše.
Mano tikslas dabar yra 1 rūšiuotų sąrašą pradžioje.
Ir aš norėčiau pasiūlyti, nes turiu tik 8 gabaliukus atminties,
savavališkai dabar aš esu siena tarp mano tariamai nerūšiuotų sąrašą,
ir tiems, kurie yra už mane, aš ruošiuosi teigti, surūšiuoti.
Taigi dabar mes turime 1.
Norite įterpti jį į mano rūšiuotų sąrašą, todėl aš tik ketina perkelti savo sieną čia,
ir dabar aš tvirtina, šis sąrašas surūšiuotas, šis sąrašas nerūšiuotų - bent jau kiek aš žinau.
Aš negaliu pamatyti visus numerius iš karto.
>> Dabar aš atsitiktų susidurti skaičių 2. Ką man daryti su juo?
Įterpti į rūšiuotų sąrašą. , Bet pastebėsite, kaip lengvai, kad buvo.
Aš tiesiog ieškoti. Numeris 1 yra. O, be abejo, 2 numeriu 1 pusėje.
Dabar ką man daryti su 3? Aš įtraukti jus į išrūšiuotų sąrašą. Bet tai buvo super lengva.
Tai super lengva, tai yra super lengva, tai yra super lengva, super lengva, super lengva.
Ir dabar viskas yra rūšiuojama už mane, ir kiek žingsnių, kad imtis?
[Mokiniai] N. >> Taigi, tai tik n. Mes pasisekė.
Tai buvo tik n kodėl? >> [Studentas] Kadangi šis sąrašas buvo išrūšiuotos.
Sąrašas jau yra rūšiuojamos. Taigi, mes pasisekė.
Bet mes sukūrėme algoritmą, šį kartą,, kuri panaudoja sėkmės natūra,
kad geriausio atvejo scenarijus, ne eikvoti nereikalingo laiko.
Taigi dabar mes turime tai, ką mes vadiname burbulas rūšių
kur žmonės rūšies burbulas iki Porinis.
Dabar mes turime pasirinkimo rūšiuoti, kur mes Wyłupać mažiausias asmuo, vėl ir vėl.
Ir dabar mes turime įterpimo rūšiuoti, kur mes tarsi aktyviai įdėti žmonių, kur jie priklauso
vis rūšiuotų sąrašą.
Šių vaikinai čia jei galėtume, ar plojimų. [Plojimai]
Paimkime mūsų 5-minučių pertrauką.
Ir kai mes einame atgal, mes bus smūgis iš vandens visų šių algoritmų
kažką geresnio. Gerai. Labai ačiū. Jūs galite laikyti, kaip suvenyrus.
Gerai. Mes atgal.
>> Ir Priminti labai greitai, mes turėjome šias 3 skirtingus požiūrius rūšiavimo,
esmė, iš kurių buvo gauti iki taško, kur kažkas panašaus Alex
galite ieškoti numerių greičiau nei kažkas panašaus Sean galėtų sąrašą.
Ir nors mes turime tokių paprastų pavyzdžių su 8 numeriais,
jums gali ekstrapoliuoti lengvai 8 tinklalapius, 8 milijardų puslapių,
arba 800 mln. draugus į "Facebook".
Taigi šie algoritmai tikrai gali prisiderinti prie tų vertybių rūšių,
ir idėjos yra galų gale tas pats.
Taigi burbulas tarsi buvo pirmoji, kur mes tipo burbuliukais sudaro didžiausią asmuo
visą kelią į dešinę, keičiant žmonių poravimas.
Tada mes turėjome tai, ką mes vadiname atrankos rūšiuoti ten, kur aš šiek tiek daugiau sąmoningai
nuolat ieško per sąrašą, pasirenkant mažiausią skaičių vėl ir vėl ir vėl,
logiškai mąstant, yra tai, kad šis sąrašas būtų galiausiai surūšiuoti.
Tada trečiojoje dalyje, Aš įtraukė žmones į savo tinkamoje vietoje,
ir mes padarėme labai nenatūralu pavyzdį, kad šis sąrašas jau buvo surūšiuoti,
bet tai buvo siųsti prane ¹ im ±, kad įterpimo Rūšiuoti atveju,
galite gauti pasisekė.
Jei skaičiai jau surūšiuoti, tai tik jus n veiksmų tai patvirtinti, kiek,
o atrankos rūšiuoti esate šiek tiek daugiau Tunnel Vision
ir jūs neturite kada nors suprasti, kad sąrašas jau yra rūšiuojamos.
Taigi pažiūrėkime, burbulas rūšiuoti metu čia.
Toliau pateiktame pavyzdyje, mes apie norėdami pamatyti vertikalios juostos
, kurių aukštis sudaro numerius, kad galėtume rūšiuoti Vizualizuoti rūšiavimas atsitikti.
Kuo mažesnis baras, Kuo šis skaičius mažesnis, tuo didesnė juosta, tuo didesnis skaičius.
>> Ir mes jį žaisti nutylėjimą greičiu.
Ji ketina perkelti truputį per greitai dabar, bet raudona, ką rodo 2 barai
yra lyginami vienas šalia kito.
Ir jei jūs atidžiai stebėti, kas atsitinka, yra ta, kad, jei juostos yra ne iš eilės,
mažesnioji bus perkeltas į kairę, didesnį vienas į dešinę,
ir tada jūs nuolat didėja.
Taigi, jei mes vėl ir vėl, pastebėsite, kad mažiausi barai
ketinate laikyti pamažu virsta savo kelią į kairę
ir didžiausi barai ketinate laikyti pamažu virsta savo kelią į dešinę.
Ir iš tiesų, mes pradedame modeliui, kad matytumėte visą kelią dešinėje
tik kaip matėme 8 ir 7 ilgainiui burbuliuoja iki mūsų žmogiškosios sąrašą toli pabaigos.
Taigi, tai vyksta labai greitai gauti šiek tiek varginantis, todėl leiskite man sustabdyti tai minutėlę.
Leiskite man pakeisti greitį bus daug spartesnis.
Aš ne pakeisti algoritmą, aš tiesiog padaryti animacija įvykti greičiau.
Dar burbulas rūšiuoti, pats algoritmas,
tačiau dabar jūs galite pamatyti daug greičiau nei mūsų žodinio demonstravimo
kad didžiausi elementai iš tiesų yra burbuliuoja iki viršaus.
>> Kaip panaikinti apačioje, kairėje pusėje, šių mažai kvadratų ir apatiniame dešiniajame
yra tik šiek tiek priminimus kiek palyginimai jūs darote.
Bet dabar, mes galime sutelkti dėmesį į piramidės, kuri įgauna formą, ir ten eina.
Mažiausias elementas yra kairėje, dešinėje didžiausių ir visa kita tarp.
Dabar tegul vietoj imtis atrankoje rūšiuoti išvaizdą.
Aš ruošiuosi eiti į priekį ir paspauskite Stabdyti. Mes ketiname gauti naują atsitiktinį rinkinį barų.
Pasirinkimas rūšiuoti, išėmimą iš apyvartos, eina per sąrašą vėl ir vėl ir vėl,
skynimas mažiausias elementas. Taigi čia yra pasirinkimas rūšiuoti.
Atrodo, kad ten mažiau darbo, vyksta dabar, nes mes ne lyginant poromis
bet mes tiesiog tarsi vyšnių skynimas ir smulkiausi elementai iš dešinės į kairę.
Tai buvo labai mažai laiko, todėl dichotomija jau.
Tiesiog todėl, kad algoritmas yra nurodyta, jog n kvadratu laiko, kaip burbulas rūšiuoti
ir kaip atrankos rūšiuoti, jie yra tikrai blogiausias veikia kartus.
Pavyzdžiui, tuo atveju, tarkim, atrankos rūšiuoti,
Aš iš tikrųjų esu pasirenkant mažiausią asmuo ir pradėti jį arba ją čia,
tada aš vėl tai daro, tada aš darau jį dar kartą,
bet ten buvo šiek tiek optimizavimas galėčiau padaryti.
>> Kaip tik aš persikėlė numeris čia 1 - Sammy šiuo atveju -
ką man reikia daryti su juo po to? >> [Studentas] Palik jį.
Palik jį, tiesa? Nieko.
Man nereikia, kad kada nors vėl pasikalbėti su Sammy, nes jei aš buvo pasirinktas mažiausias elementas
ir įdėti jį čia, kodėl gaišti laiką vyksta į mano visą sąrašą?
Kitą iteracijos leiskite man iš tikrųjų judėti tik skaičius "2", tik numeris 3.
Taigi iš tikrųjų, aš buvo ne daro n daiktus n kartų.
Darau n dalykų, tada "n - 1 dalykai, tada n - 2 dalykų, tada n - 3 Things
tada "n" - 4, taškas, taškas, taškas.
Mes turime geometrine progresija, kuris tiesiog reiškia, kad tiek
norite pridėti palaipsniui mažesniais skaičiais.
Ne n + n + n + n, bet n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Ir kas, kad paprastai dirba esąs -
Aš ruošiuosi bałagan mano lenta čia tik akimirką -
kad vyksta dirbti, turi būti kažkas panašaus n (n - 1) / 2
jei mes tiesiog pažvelgti rūšies matematikos knygą, kur jūs turite visas Ruošinukai atgal
formules.
Jei jūs tiesiog pridedant kažką n + n - 1 + n - 2, jis veikia esąs kažkas panašaus į tai.
Ir jei mes tiesiog rūšies dauginti this out, tai n kvadrato atėmus n / 2.
Aš nuolat sako n kvadrato, nors, ir tai todėl, kad buvau rūšies psichikos nuorodą
nes iš tikrųjų, n kvadrato atėmus n padalinti iš 2 yra iš tikrųjų tiesa pakopų skaičius
, kad kaip atrankos rūšiuoti algoritmas užtruktų, jei mes tikrai paskaičiavo
visi šie palyginimai ir visi šiek tiek užimtas darbo, mes darome.
Bet atvirai, kai n gali būti kaip milijono ar milijardo eurų, kas gi rūpi
jei jūs darote mlrd kvadratu minus milijardą padalinti iš 2?
Mlrd kvadratu yra labai daug.
Jūs galite pasiimti kitą mlrd off - n. Tai ne tokia baisi.
Taigi didesnis skaičiai gauti, mažiau svarbūs šios mažesnės išplanuotomis sąlygos.
Who cares, jei reikia padalinti iš 2, jei jūs kalbate apie quadrillions pakopų skaičių?
>> Taigi apskritai kompiuterių mokslininkai linkę išmesti viską, bet didžiausią santykiai,
ir mes tiesiog rūšies supaprastinti pasaulį ir pasakyti, kad šis algoritmas
paėmė maždaug n kvadrato veiksmus. Štai algoritmu veikimo laikas.
Taigi, mes grįžti į šį vos akimirką su kai kuriais konkrečiais pavyzdžiais,
bet dabar, tai tarsi intuityvi motyvacija už tiesiog supaprastinti mūsų pasaulį
ir kalbėti apie svarbiausių terminų, o ne patekti į visų šių išgalvotas formules.
Kad buvo atrankos rūšiuoti, ir mes turime šiek tiek pasisekė.
Pažvelkime įterpimo rūšiuoti. Leiskite man eiti į priekį ir pradėti šį vieną, taip pat.
Dabar pastebėsite modelį, kuris manimi vyksta, yra šiek tiek kitoks,
ir mes pradėjome su atsitiktinių skaičių,
bet jei mes iš tikrųjų skaičiuoti žingsnių, blogiausiu atveju,
jei sąrašas prasidėjo visiškai teisinga tvarka,
mes tik imtis n veiksmus suvokti, kiek.
>> Bet jei sąrašas buvo faktiškai atgal - pavyzdžiui, šiuo atveju čia -
tada pastebėsite, mes iš tikrųjų turime padaryti daug daugiau darbo, šiuo atveju.
Ir ji turėtų rūšies manai, kaip tai vienas natūra dirbti sunkiau
gauti tuos mažesnius elementus į kairę, ir tai, nes mes turime nelaimingas.
Sąrašas buvo surūšiuoti netyčia atbuline eiga.
Priešingai, su prierašu rūšiuoti, jei mes imituoti tai, ką mes padarėme su mūsų žmonėms čia
rūšiuotas visiems pradedant ir tada pradėti, tai gana geras algoritmas, tiesa?
Tai jau, tiesą sakant, surūšiuoti.
Taigi, pabandykime apibendrinti, tiksliai, kiek laiko šie dalykai mums
įvedant tik šiek tiek žargono ar notacija, kas iš tikrųjų daug paprasčiau
nei fanciness tarsi rodo.
Tai, ką čia, tai didelis O ekrane yra tai, ką kompiuteris mokslininkas paprastai naudoja
apibūdinti blogiausio atvejo veikimo laikas algoritmą.
>> Dar kartą, blogiausiu atveju, tai visiškai priklauso nuo konteksto.
Ką mes vadiname blogiausiu atveju visiškai skiriasi priklausomai nuo problemos, mes kalbame apie.
Bet, rūšiavimo, kas yra blogiausias galimas scenarijus?
Viskas yra atgal, nes jis tiesiog mano, kaip tai reiškia, kad mums daug darbo.
Aš jotted keli algoritmai, kad mes matėme iki šiol:
linijinis paieška, dvejetainis paieškos kaip su telefonų knygoje arba popieriaus likučių,
burbulas rūšiuoti, atranka rūšiuoti ir įterpimo Rūšiuoti, kaip matėme su mūsų žmonėms,
ir tada 1 kita, kad galiausiai bus vadinamas sujungti rūšiuoti.
Taigi, tiesinio paiešką blogiausiu atveju, kiek žingsnių reikia, rasti skaičių 7
jei yra n durys, pavyzdžiui, Sean, su kuriomis susiduria? >> [Studentas] N.
N. Taigi, mes ketiname rašyti Big O n.
Aš tik ketina užpildyti kai kurių ruošiniai. Tai tik ruošiniai tinklelis.
Tačiau geriausiu atveju su linijiniu paieškos, 7 galėjo pačioje sąrašo pradžioje,
ir Sean galėjo pradėti žiūri sąrašo pradžioje.
Taigi, jei jūs tiesinio paieškos ir tiesiog patikrinti iš kairės į dešinę, o gal ir iš dešinės į kairę -
jie atitinka - geriausiu atveju, kiek žingsnių gali linijinis paieška
kaip Sean algoritmas imtis? Tik 1 žingsnis.
>> Taigi, aš ketina pasakyti, kad omega notacijos.
Tai tik kapitalas omega.
Omega yra tik seksualus būdas pasakyti, geriausiu atveju važiavimo laikas.
Taigi, geriausiu atveju veikimo laikas yra vienas žingsnis, ar nuolatinis pakopų skaičius -
Šiuo atveju 1 - bet blogiausiu atveju, Big O, tai tikrai n žingsnių.
Ir tai vienas čia, teta, mes iš tikrųjų nesiruošia ieškoti ne dabar.
Tai nėra susiję su šiuo konkrečiu pavyzdžiu.
Bet dabar pabandykime Dvejetainė paieška.
Blogiausiu atveju dvejetainis paieškos, kiek žingsnių jis ketina imtis, kad būtų rasti 7
bet mes ieškome? >> [Studentas] Prisijungti n.
Vis dar ketina imtis log n, nes kaip ir Alex gavo nelaimingas
kai mes iš tikrųjų dirbo per problema metodiškai
, ir ji neturėjo iki pat paskutinio duris, ji pažvelgė į skaičių 7,
nors, tiesą sakant, ji gavo išmesti tam tikras duris pakeliui,
blogiausiu atveju dvejetainis paieškos log n veikimo laiką.
Ir vėl, kad kalba tai dalijant ir užkariauti.
Bet kas apie geriausiu atveju?
Ir Alex iš tikrųjų patyrė, kad geriausiu atveju, kai ji atėjo į sceną.
Kiek žingsnių imtis dvejetainis paieškos? >> [Studentas] 1.
1, tik todėl, kad ji pasisekė.
Bet tai gerai, nes omega reiškia geriausią scenarijų,
geriausiu atveju sąnaudos, net jei tai tik atsitiktinis kvailas sėkmės.
>> Dabar tai taip pat mes ketiname tik rūšies palikite tuščią dabar.
Kaip apie dabar burbulas rūšiuoti?
Burbulas rūšiuoti, blogiausiu atveju, kiekvienas yra atvirkštine tvarka,
todėl mes turime padaryti, burbuliuoja daug.
Bet kiek žingsnių yra tai, kad ketina imtis blogiausiu atveju? >> [Studentas] N kvadratu.
Tai buvo n kvadrato, nes jei jūs manote apie tai,
jei sąrašas yra visiškai atgal - 8 yra čia, 1 per čia -
kaip dalykas pradeda burbuliuoti, numeris 8 ketina perkelti šį kelią, tokiu būdu,
tokiu būdu, tokiu būdu, bet kur yra numeris 7 blogiausiu atveju?
Čia ji vis dar ten. Taigi, mes turime tai daryti vėl ir vėl.
Ir tai, kai mes gauname n žingsnių, tada "n - 1 etapai, tada n - 2 žingsniai.
Ir jei jūs imtis savo žodį, kad jei jūs rūšies padauginkite jį iš,
Apytiksliai tai n kvadrato galų gale su kai kuriomis kitomis sąlygomis, kad mes tiesiog ignoruoti dabar -
tada blogiausiu atveju burbulas rūšiuoti yra n kvadrato, duoti ar priimti.
Bet kas apie geriausiu atveju su burbulas rūšiuoti?
Koks yra geriausias scenarijus? Visus numerius yra rūšiuojamos jau.
Ir kas buvo aš naudojamas, triukas, aš naudojamas euristinis,
suprasti, kad aš nepadarė nieko darbą ir gali nutraukti anksti?
[Studentas] Patikrinkite jį vieną kartą. >> Patikrinkite jo dar kartą. Bet ką darau pakeliui?
Sekti kiek apsikeitimo sandoriai aš padariau.
Ir aš supratau, jei aš nėra skaičiuojami apsikeitimo sandorius mano pirštus, tada aš padariau jokio darbo.
Aš tikrai neturėtų bandyti vėl ir nedirbsite jokio darbo, todėl galiu tiesiog sustoti.
>> Taigi, geriausiu atveju Bubble rūšiuoti, kai šis sąrašas jau rūšiuojamos,
ką jūs pasakytumėte, omega notacijos, geriausiu atveju veikia gyvenimą?
Tai tiesiog n. Mes turime padaryti tam tikrą darbą, bet turime tik tai padaryti 1 klaidžioti verta darbo.
Ir čia aš ruošiuosi palikite tuščią.
Ir dabar pasirinkimas rūšiuoti.
Pasirinkimas man buvo tarsi skynimas mažiausias asmuo vėl ir vėl.
Ir ką mes sakome, veikimo laikas, kad buvo?
Tai buvo n kvadrato blogiausiu atveju.
Ir, deja, geriausiu atveju jis taip pat n kvadrato
nes aš neturiu visažinis nuomone viso pasaulio Rūšiuoti pagal
Aš tik žinau, nuo visiško iteracijos, kad aš iš tikrųjų rado mažiausią asmuo.
Taigi pasirinkimas rūšiuoti rūšies sucks ta prasme,
bet aukštyn, tai tipo intuityvus.
Tai gana lengva kodą, nes viskas, ką jums reikia padaryti yra rašyti lizdinė už kilpos pora,
paprastai, kad eina per ieško mažiausio elemento
ir tada kelia mažiausią elementą, kur jis priklauso sąrašo pabaigoje.
Taigi čia taip pat bus kompromisas.
, Kiek laiko užtrunka jums galvoti ir sukurti kažką rašyti kodą
galėtų labai gerai daugiau laiko, jei norite geriau algoritmas ir geresnį efektyvumą.
>> Tačiau Jums tiesiog malonu kodas kažkas ne greitas ir purvinas
ir tiesiog rūšies stupidest idėją, jūs galite galvoti,
, kuris gali užtrukti keletą minučių kodą, tačiau su didelių duomenų rinkinių
Jūsų algoritmas gali imtis valandų paleisti.
Ir net aš kartais, kad šios aukštosios mokyklos kompromisus.
Būtų 03:00, aš bandžiau analizuoti kai kurių labai didelių duomenų rinkinį
susiję su saugumo mokslinių tyrimų, aš darau, ir jis buvo arba praleisti 5 minutes
truputį keisdami savo programą, analizuoti duomenis ir eiti miegoti
arba praleisti 8 valandas gauti tik teisę, kad jis eina iš karto, o ne eiti miegoti.
Ir taip yra per daug tai tipo sąmoningo sprendimo.
Mažiau kūrimo laikas, daugiau miego.
Žvelgiant atgal, aš tikriausiai neturėtų skatinti, kad
kai tikslas čia yra optimizuoti kodo kokybę,
tačiau per realiame pasaulyje yra labai priimtiną kompromisą.
Mažiau laiko, mažiau atlikimas arba atvirkščiai.
Taigi čia mes pagaliau gauti galimybę pasikalbėti apie teta.
Teta notacijos yra kažkas, kompiuterių mokslininkai gali auklėti pokalbis
kai didelis O ir omega atsitiktų būti tas pats.
Jūs sakote, kad teta tikrai pasiųs signalą, kad tai rūšies stora privalo.
Nesvarbu, ar scenarijus yra geras, ar blogas, tai n kvadratu.
Todėl tiesiog nėra svarbus šių istorijų čia.
Įterpimo rūšiuoti naujausia, mes pažvelgė,
kai man buvo tiesiog įterpiant visiems į tinkamą vietą.
Geriausiu atveju, tai, kas buvo įterpimo Rūšiuoti veikimo laikas kaip matėme čia?
[Studentas] geriausiu atveju? >> Geriausiu atveju.
>> N, nes geriausiu atveju visi rūšiuojami,
ir Sammy ir niekas tikrai turėjo perkelti ne visi.
Jie jau savo tinkamoje vietoje.
Taigi įterpimas rūšiuoti geriausiu atveju, šiuo atveju, n.
Bet blogiausiu atveju tai tipo n kvadrato. Kodėl?
Jei mano žmonių sąrašas yra atvirkštine tvarka,
Aš pirmą kartą pradėti su skaičiumi 8 ir įterpti jį arba ją į dešinę poziciją, kuri čia.
I rūšies judėti į šoną. Šie vaikinai yra neišrūšiuoti, jis ar ji yra rūšiuojama.
Bet dabar aš atsitikti, surasti, kas kitas? >> [Studentas] 7.
7 blogiausiu atveju, nes tai atvirkštine tvarka.
>> Taigi čia yra 7. Kur gi 7 priklauso? Tikrai už mane.
Bet dabar 7 iš tikrųjų priklauso ne iš karto už manęs, bet už 8 skaičius,
taip, aš turiu pasakyti: "Atsiprašau, numeris 8, galite perkelti šį kelią
"Kambarys 7? Dabar aš susiduria su 6.
"O, atsiprašau, skaičių 8 ir 7 numeris, galite perkelti, kad būtų vietos 6?"
Taigi, kitaip tariant, su įterpimo rūšiuoti, nors aš ne daryti daug judėti,
už manęs žmonės daro daug daugiau darbo, ir tai turi kainuoti kažkas laiką.
Tai kainuos kompiuterio laiką.
Įterpimo Rūšiuoti Taigi mes vis dar kenčia.
Jei jums pradėti pridedant bendrą žingsnių skaičių, mes galų gale pradeda maždaug n kvadrato
, nes šie vaikinai turi, kad paliktume vietos žmonių, kuriuos reikia įtraukti į tą sąrašą.
Ir todėl šiuo atveju teta yra tik ne į ypatingą istoriją po ranka.
Štai ir viskas nice and good. Mes turime šiuos 3 skirtingus būdus, kaip kalbėti apie veikimo laiką.
Bet ką tai iš tikrųjų reiškia realiai, jei mes iš tikrųjų bando koduoti algoritmą?
>> Leiskite man pasiūlyti, kad ten dar geriau algoritmas ten
, kuri pati turi tam tikrą kompromisus.
Mes ketiname jį vadiname sujungti rūšiuoti, ir tai tarsi šio stebuklingo algoritmo
kad tik veikia greičiau kažkokiu būdu, ir tai taip lengva išreikšti, bent jau pseudocode.
Merge sort šio algoritmo įgyvendinimą bus taip.
Kai jums suteikta N elementų - N numerius, n žmonių, nesvarbu - pirmiausia normalumas patikrinimas.
Jei n yra mažesnis negu 2, sujungti rūšiuoti tiesiog sustoja. Jis grįžta, taip sakant.
Kodėl gi jūs sustabdyti, jei n yra mažiau nei 2? >> [Nesigirdi studentas atsakas]
Į dešinę. Ir vėl, n nėra sąraše, n sąrašo dydis.
Jei n yra mažesnis negu 2, tai reiškia, kad jūsų sąrašas arba 1,
kur jūs akivaizdžiai rūšiuojamos, jei tai numeris 1,
arba 0, tokiu atveju nieko rūšiuoti,
todėl mes turime šį bazine rūšiuoti.
Jei sąrašas yra toks trumpas, kad ten tiesiog nieko daryti, tiesiog nereikia daryti nieko. Grįžti.
Kitaip rūšiuoti elementų yra kairėje pusėje, tada rūšiuoti elementų, dešinėje pusėje,
tada sujungti 2 surūšiuotas puses.
>> Šios rūšies atrodo šiek tiek apgauti, pagal kurį aš prašau jus, kaip rūšiuoti elementus
ir jūs man sako, "Rūšiuoti kairėje pusėje, rūšiuoti dešinėje pusėje."
Aš, pavyzdžiui, "Gerai. Kaip jūs rūšiuoti kairę pusę?"
"Rūšiuoti kairėje pusėje, kairėje pusėje, rūšiuoti kairę pusę dešinėje pusėje, ir tada padaryti."
Esate natūra pagal ciklą apibrėžti, ką tai reiškia, rūšiuoti,
tačiau paaiškėja, kad šiuo atveju tikrai puikus.
Tai nėra tikrai tai užburtas ratas, kuris niekada nesibaigia
, nes jis baigiasi, kai? >> [Studentas] Kai pasieksite 1 dalykas.
Kai jūs pasieksite 1 dalykas.
Taigi, nors jūs galite pradėti su 8 žmonių, ir aš sakau, "Rūšiuoti kairę pusę šių žmonių,
šie 4 žmonės ", tada aš sakau," Kaip jūs rūšiuoti kairę pusę? "
"Na, rūšiuoti 2 žmonės čia". Ir tada jūs, pavyzdžiui, "Gerai, puiku."
"Kaip jūs rūšiuoti kairę pusę tų žmonių?"
"Tiesiog rūšiuoti Šis 1 asmuo čia." , Kas yra puikus apreiškimas dabar?
Aš turiu rūšiuoti 1 asmeniui. Atlikta. Aš neturiu daryti bet kokį darbą.
Bet dabar aš turiu sutvarkyti šį asmenį, bet jie vienas žmogus, nieko.
>> Taigi magija, matyt, yra Šis trečiasis etapas: sujungti surūšiuoti puses.
Taigi sujungti rūšiuoti šią puikią įžvalgą, kad, jei pertraukos didelė problema žemyn
į 2 mažesnius, identiškai dydžio problemų
ir tada tiesiog rūšies klijais mažesnių sprendimai kartu pabaigoje,
Aš siūlau, kad mes galime padaryti daug, daug geriau [įsriegimo garso]
nei bet kuri atrankos rūšiuoti ar įterpimo rūšiuoti.
Aš iš tikrųjų buvo ignoruojant, kad pusvalandį, bet aš tikrai nežinau, kas vyksta
ne šiandien. [Whirring garsas] [juokas]
Taigi pažiūrėkime, jei mes galime pamatyti tai su nedidele pagalba iš mūsų draugui Rob Bowden.
Merge sort proceso Yra 2 dideli žingsniai.
Pirma, nuolat į dvi dalis padalinti puodelių sąrašą
kol mes sąrašų krūva tik su 1 puodelis jais.
Nesijaudinkite, jei sąraše yra nelyginis skaičius
ir jūs negalite padaryti visiškai nupjauti tarp jų.
Tiesiog savavališkai pasiimti, kurių sąrašas įtraukti papildomos puodelio in
Todėl galime padalinti šiuos sąrašus.
Dabar mes turime 2 sąrašus.
Dabar mes turime 4 sąrašus.
Dabar mes turime 8 sąrašus su vienu puodelio kiekvieno sąrašo.
Taip, kad jį atlikdami 1 veiksmą.
Atlikdami 2 veiksmą pakartotinai sujungti poros suliejimo algoritmas mes sužinojome prieš naudojant sąrašų.
Sujungimas 108 ir 15 mes galų gale su sąraše 15, 108.
Sujungimas 50 ir 4 mes galų gale su 4, 50.
Sujungimas 8 ir 42 mes galų gale su 8, 42.
Ir sujungti 23 ir 16 mes galų gale su 16, 23.
Dabar visi mūsų sąrašai dydis 2.
Atkreipkite dėmesį, kad kiekvienas iš 4 sąrašų yra rūšiuojamos,
, kad galėtume pradėti vėl sujungti poros sąrašų.
Sujungimas 15 ir 108 ir 4 ir 50 mes pirmiausia imasi 4, 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 2 sąrašus dydis 4, iš kurių kiekviena yra rūšiuojama.
Taigi dabar mes sujungti šias 2 sąrašus.
Pirmiausia mes 4, tada mes 8, tada mes priimsime 15
ir 16 ir 23 ir 42 ir 50 ir 108.
Ir baigsime. Dabar mes turime surūšiuoti sąrašą.
>> Robas buvo natūra pasinaudoti kažkas, kad mes dar to nepadarėte.
Buvo pasiūlyta, bet mes ne iš tikrųjų tai padaryti.
Jis daro kažką fiziškai puodeliai, tai sudaro prielaidas
jis buvo išleisti šiek tiek išteklių be laiko. >> [Studentas] erdvė. >> Tai buvo erdvė.
Tai, kad jis neturėjo šį dviejų lygių lentelę rūšiuoti, kur jis turėjo erdvę čia
ir platybių čia iš tikrųjų buvo, o tai reiškia, kad jis naudoja dvigubai daugiau erdvės,
bet mūsų algoritmų iki šiol - įterpimo rūšiuoti, burbulas rūšiuoti, ar atranka rūšiuoti
bet jis buvo sverto šį papildomą erdvę rūšies perkelti daiktus į priekį ir atgal
išlaikant dalykų, kad.
Ir nors ji mano, kaip mes turime rūšiuotų sąrašą, kad jaučiau, jis paėmė šiek tiek laiko.
Iš tikrųjų tai, ką Rob darė būtent šis algoritmas.
Jis pirmą kartą paėmė n dydžio problemą, yra padalintas į kairę pusę, ir dešinėje pusėje.
Tai, kai jis persikėlė puodeliai. Tada jis pakartojo šį procesą.
Jis padalintas 4 į 2 komplektai 2 čia ir štai čia.
Tada jis pakartojo šį procesą ir 2 padalintas į 2 komplektai 1 kiekvieno šių skirtingų puodelių.
Ir tai, kai atsiranda puiki galimybė.
Tuo pasakojimo taško, Rob turėjo 8 sąrašus 1 dydžio,
visi, kurie buvo surūšiuoti jau.
>> Taip, tada ką jis pradėti daryti?
Porinis paėmė šį surūšiuoti sąrašą ir šį surūšiuoti sąrašą ir sujungti juos.
Tada jis paėmė šį vieną ir sujungti juos, tada tai vienas ir sujungti juos,
tai jo ir sujungti juos.
Ir tada ką jis daryti toliau?
Tada jis vėl susijungė didesnes sąrašus ir tada vėl sujungė didesnių sąrašus.
Ir jei jūs manote apie tai tiesiog intuityviai dabar, ką jis iš tikrųjų daro?
Jis pasidalijo problemą per pusę, per pusę, per pusę, per pusę
siekiant gauti šiuos super mažų lapų.
Tada jis buvo natūra derinant dviviečiai, dviviečiai, dviviečiai, dviviečiai.
Taigi jis daro du kartus, kaip daug darbo, kaip mes matėme iki šiol
nieko su Skaldyk ir valdyk, bet ne big deal.
Dvigubai tiek, kiek darbas yra ne tokia baisi. Tai tik pastovus koeficientas.
Ir panašiai kaip mūsų aritmetinio išraiškos prieš, aš tik ketina kirsti pastovius veiksnius
kaip kartus 2. Who cares? , Jei tai 2 milijardai 2 kartus, kad vis dar daug žingsnių.
Taigi tai sujungti žingsnis atrodo yra pagrindinė įžvalga.
Leiskite eiti per tai tik skaitmeniniu būdu, prieš - O, tai nereiškia būti tęsiamas dar.
Leiskite eiti per šį skaitmeniškai tik iš tikrųjų pamatyti, kaip ši atlieka dėmesį.
Tai daugiausia tik šiek tiek vargšų animacija.
Leiskite pasiūlyti šią.
Veikimo laikas sujungti rūšiuoti - mes tiesiog reikia būdas kalbėti apie tai.
Tai ne matematika, tai tiesiog rūšies trumpas būdu išreikšti save.
Taigi T yra laiko ir n yra kas? >> [Studentas] dydis -
>> [Malan] problemos dydis, žmonių skaičius.
Taigi, aš teigdamas, kad laikas rūšiuoti n žmonių bus 0 suma laiko
Jei n yra mažesnis nei 2, nes jei turite 1 puodelis arba neturi puodeliai, jūs neturite ką rūšiuoti.
Bet apskritai, aš norėčiau pasiūlyti, kad važiavimo laikas rūšiuoti n elementų
bus laiko reikia rūšiuoti kairę pusę, plius Dešinė pusė
plius - kas tai yra papildomas + n? >> [Studentas] suliejimas rūšiuoti.
[Malan] Tai tikrai sujungti, nes jei n / 2 elementus čia
ir turite n / 2 elementai čia, kiek laiko tai užtruks juos sujungti?
Tiesiog kaip ir Rob, turite skinti šį vieną čia, gal skinti čia,
skinti čia, skinti čia, skinti čia.
Turite paliesti kiekvieną kaušelių kartą.
Ir jei yra 4 puodeliai plius 4 puodeliai, 8 puodeliai
arba apskritai, 8 n puodeliai.
Taigi sujungus žingsnis galime išreikšti kaip n
ir, kad pažodžiui reiškia, kiek kartų skaičių Rob fiziškai palietė
vienas iš tų polistirolas puodeliai.
Taigi tegul dabar daryti savavališkai pavyzdį.
Jei yra 16 puodeliai, kas veikimo laikas rūšiavimo, Rob algoritmą, 16 puodelio?
Tai 2 kartus laiko užtrunka rūšiuoti 8 puodelius
nes mes turime 8 puodelius, 8 puodeliai čia.
Aš nežinau, kaip ilgai, kad mano, todėl mes apibendrinant kaip T šiuo metu.
Kas žino, kas tai yra?
Bet dabar galiu rūšiuoti rekursyviai arba pakartotinai užduoti tą patį klausimą.
Kiek laiko užtrunka rūšiuoti 8 puodelius?
8 puodeliai, aš ruošiuosi pasakyti mano, kiek laiko užtrunka rūšiuoti 4 puodeliai plius 4 puodeliai,
tada sujungti juos kartu.
Bauda. Mes vis ciklo dalyje jau. Kiek tai užtruks rūšiuoti 4 puodelius?
Laiko užtrunka rūšiuoti 4 puodelius 2 puodeliai plius 2 puodeliai rūšiavimo plius jungimosi procesą.
Bauda. Kiek tai užtruks 2 puodeliai rūšiuoti?
2 puodeliai yra laiko užtrunka rūšiuoti 1 puodelis plius laiko užtrunka rūšiuoti kitą puodelį
plius kiek laiko reikia, kad sujungti, kuris yra vos už 2.
>> Bauda. Paskutinis klausimas. Kiek tai užtruks rūšiuoti 1 puodelis?
Čia yra pagrindas, kad mes prognozavo, mes norime paspausti anksčiau.
Tas faktas, kad ji nežino kokia rūšiuoti mažiausia iš problemų
reiškia, kad dabar, tarsi laipsnio mokyklos stiliumi,
mes galime tiesiog eiti pradėti prijungti šiuos numerius atgal.
Mes dabar žinome, kas T 1, kad galėčiau prijungti 0 T iš 1.
Kad duos man atsakymą į T 2, kurį aš tada gali prijungti aukščiau.
Kad duos man T iš 4, kurį galiu prijungti aukščiau.
Kad duos man T 8, kurį galiu prijungti aukščiau.
Ir jei aš iš tikrųjų, kad matematika įjungdami šių atsakymų,
Tada aš gauti T 16 yra 64.
Ir ką 64?
Jei T yra 16, taip, tai 16 kartų 4.
Taigi galiu reikalauti, kad dabar šis dalykas, vadinamas veikimo laikas sujungti rūšiuoti -
ir tai bus, ką mes matėme iki šiol fanciest
bus vadinama n log n
nes kiek kartų gali Rob padalinti visa krūva puodelių per pusę? Log n.
Tai tas pats, kaip telefonų knygos, pavyzdžiui, tai tas pats kaip savarankiškai skaičiavimo pavyzdys.
>> Kiek kartų jūs galite kažką per pusę padalinti?
Tačiau yra tai sujungti žingsnis.
Jums gali tekti padalinti puodeliai į pusę, vėl ir vėl ir vėl,
bet kiekvieną kartą, jūs ketinate reikia sujungti.
Ir mes anksčiau sakė, kad sujungti n puodeliai trunka n veiksmus
nes jūs turite skinti puodelį, skinti taurę, ir turite paliesti kiekvieną puodelį kartą,
kaip ir Rob padarė.
Taigi, jei mes darome kažką log n kartų ir ką mes darome, n dalykus apie kiekvieną iš tų iteracijų,
kiekviena iš tų halvings turime n kartų log n.
Taigi, jei mes prijungti 16 šiame pavyzdyje 16 kartų prisijungti 16 -
nereikia nerimauti, kodėl taip yra ir dabar, nes aš ne atkreipė bazę
bet žurnalo 16 2 pagrindo yra 4, 16 kartų 4 yra 64.
Tačiau priešingai,, jei būtume naudojamas burbulas rūšiavimo arba atrankos rūšiavimo arba įterpimo Rūšiuoti su 16 numerių,
kas būtų buvę, jei veikimo laikas n 16?
Būtų 16 kvadrato, kuris yra 256, kuris, net jei jūs ne visai visą matematikos
256 yra didesnis nei 64. Kad tikrai stebuklinga išsinešimui čia.
Ir suprasti, kad per šį mažesnių pavyzdžių, kaip jums ant pset
tampa daug paprastesnis.
Bet, ką tai iš tikrųjų reiškia, kalbant apie šio algoritmo jaustis yra tokia:
Jei mes iš tikrųjų pažvelgti Merge sort čia - leiskite man traukti ją šiame lange -
tai yra šiek tiek kitoks pavyzdys, kuriuo mes turime 3 visų šių algoritmų -
burbulas, atranka, ir sujungti - tik vienas šalia kito.
>> Jie visi pradėjo su atsitiktinių barų, ir tai gerai.
Niekas neturi pagrindinio pranašumo prieš kitą.
Aš ruošiuosi po akimirkos spustelėkite kiekvieną iš šių animacija - Pradėti, Pradėti, Pradėti
taip greitai, kaip aš galiu, kad, grubiai, jie visi tuo pačiu metu pradžios,
ir tegul mano, kad burbulas Rūšiuoti Blogiau atvejis važiavimo laikas yra tai, ką? >> [Studentas] N kvadratu.
N kvadratu. Atrankos Rūšiuoti blogiausiu atveju važiavimo laikas? N kvadratu.
Ir sujungti rūšiuoti, matyt, - net jei ne visiškai laikytis visų matematikos dabar
tapsite daug paprastesnis laikui bėgant - tai mes tvirtiname, kad n kartų log n.
Ir todėl, kad log n yra griežtai mažiau nei n kai turime didelius numerius,
n kartų log n yra mažesnis nei n kartų (n) arba n kvadrato.
Taigi, kas ji jaučiasi, kad iš tikrųjų būtų geriau algoritmas veikimo laiką,
n kartų log n, o ne n kvadrato? Čia mes einame. Spustelėkite, spustelėkite, spustelėkite.
>> Štai, ką reiškia naudoti kažką panašaus Merge sort.
Mes turime labai mažai laiko. Leiskite pamatyti, kas vyksta čia.
[Chuckles], kurių pinigai yra burbulas rūšiuoti?
Tai labiau priklauso nuo įėjimo kartais.
Pažiūrėkime.
Come on. Jis jaučiasi, kaip jis vejasi. >> [Studentas], burbulas rūšiuoti!
[Studentai murmantys]
[Malan] Taip, taip.
[Studentai murmantys] Eik, eik, eik!
[Visos Dopingowanie] [plojimais]
Taigi, dabar su 1 Paskutinis, galutinio demo, jei tai šiek tiek sudėtinga wrap savo mintis apie matematika
ar tarsi vizualizacija ten, jūs iš tikrųjų galite išgirsti greičius
skirtingų algoritmų skirtingai.
Tai animacija kažkas, kad faktiškai susieja skamba
keičiant proceso ir iš barų aukštį.
Kaip matysime, yra keli rūšiavimo algoritmai ten, kad žmonės galvojo apie.
Tai pirmasis bus įterpimas rūšiuoti, ir tai bus skristi per
ir duoti jums, kaip šie įvairius algoritmus darbui garsinį jausmą.
Čia yra įterpimo rūšiuoti.
[Elektroninis pypsėjimas]
[Malan] burbulas rūšiuoti.
[Greičiau elektroninis pypsėjimas]
[Malan] parinkimas rūšiuoti.
[Greičiau elektroninis pypsėjimas]
[Malan] suliejimas rūšiuoti.
[Elektroninis pypsėjimas]
[Pypsėjimas lėtina] [Juokas]
[Malan] Gnome rūšiuoti.
[Elektroninis pypsėjimas]
>> Tai CS50. Mes Pasimatysime kitą savaitę. [Plojimai ir visaip kitaip]
>> [CS50.TV]