>> [Predvaja glasba]
>> Profesor: V redu.
To je CS50 in to je Konec tritedenskega.
Tako da smo danes tu, ne v Sanders Gledališče, namesto v Weidner knjižnici.
Znotraj katerega je studio znan kot Hauser Studio,
ali pa bomo rekli, Studio H, ali se smo say-- če ste uživali to šala,
to je pravzaprav od sošolec, Mark, online,
ki je predlagal kar prek Twitterja.
Zdaj, kaj je kul da je tukaj v studiu
je, da sem obkrožena s ti zeleno stene, zelen zaslon ali chromakey,
tako rekoč, kar pomeni, da CS50 je produkcijska ekipa, nevede, da me
zdaj, bi bilo dajanje Najbolj me kjerkoli na svetu,
za boljše ali slabše.
>> Zdaj, kaj je pred nami, problem določiti dve je v vaših rokah za ta teden,
vendar s problemom nastavljena tri ta prihajajoči teden,
vas bo izpodbijala z tako imenovana igra 15,
stara uslugo stranka, ki boste morda odpoklic prejema
kot otrok, ki ima cel kup številk, ki se lahko drsijo gor, dol,
levo in desno, in tam je ena vrzel v sestavljanki, v kateri ste
lahko dejansko slide teh kosov sestavljanke.
Konec koncev ste prejeli to puzzle v neki napol naključnem vrstnem redu,
in je cilj ga rešiti, vrha do dna,
leve proti desni, od enega vse tja do 15.
>> Na žalost, izvajanje boste imeli pri roki
se bo programska oprema temelji, ne fizično.
Ste dejansko dogaja, da imajo za pisanje koda, s katero študent ali uporabnik lahko
igrajo igro 15.
In v resnici, v hacker izdaja igri 15,
boste izziv za izvajanje, ne samo igranje te stare šole
Igra, ampak Reševanje nje, izvajanje način boga,
tako rekoč, da dejansko rešuje uganko za človeka,
tako da jim s pridihom, po namigu, po navdihu.
Torej, več o tem naslednji teden.
Ampak to je tisto, kar je pred nami.
>> Za zdaj opozarjajo, da je v začetku tega tedna smo imeli to Cliffhanger, če hočete,
pri čemer je najboljše, kar so počeli sortiranje pametno je bila zgornja meja velik o n
kvadrat.
Z drugimi besedami, bubble razvrščanje, Izbor vrste, vstavljanje razvrščanje,
vsi od njih, so različni pri njihovem izvajanju,
prenesena v N kvadrat teče čas v zelo najslabšem primeru.
In smo na splošno predpostavljamo, da zelo najslabšem primeru za sortiranje
je tista, ki vaše vhodi so popolnoma nazaj.
In res, je trajalo kar nekaj korakov izvajati vsako od teh algoritmov.
>> Zdaj pa na samem koncu razreda odpoklic, smo primerjali mehurček vrste
proti izbora vrste proti eni drugi da smo poklicali zlivanjem v času,
in predlagam, da se ob Prednost lekcijo iz tedna
nič, deli in vladaj.
In nekako doseči nekakšno logaritemsko čas teče na koncu,
namesto nečesa to je zgolj kvadratna.
In to ni čisto logaritmična, to je malo več kot to.
Ampak, če se spomnimo iz razreda, je bilo veliko, veliko hitreje.
Oglejmo si oglejte kjer smo končali.
>> Bubble vrsta versus izbor nekako v primerjavi z zlivanjem.
Zdaj pa oni vse teče, v Teorija, istočasno.
CPU teče z enako hitrostjo.
Ampak lahko začutite, kako dolgočasno je to se zelo hitro dogaja, da postanejo
in kako hitro, ko smo injicirali malo algoritmov Tedensko Zero je,
bomo lahko pospešili stvari.
>> Torej znamka nekako izgleda neverjetno.
Kako ga lahko izkoristite, da hitreje razvrstiti številke.
No dajmo razmišljati nazaj za sestavino, da smo
moral nazaj v ničelno tednu, to je išče nekoga v imeniku,
in opozarjajo, da je psevdokoda da smo predlagali,
prek katerega bomo lahko ugotovili, nekdo kot Mike Smith,
pogledal malo kaj takega.
>> Zdaj pa si oglejte še zlasti na liniji 7 in 8, ter 10 in 11,
ki povzročijo, da se zanka, pri čemer smo ohranili vrača v vrstico 3 znova in znova,
in spet.
Vendar se je izkazalo, da smo si lahko ogledajo Ta algoritem, tukaj v psevdokoda,
malo bolj celostno.
V bistvu, kaj iščem na tukaj na zaslonu,
je algoritem za iskanje Mike Smith med nekaterimi niza strani.
In res, da bi lahko to poenostavili Algoritem v teh vrsticah 7 in 8,
10 in 11, da samo to povem, ki sem predstavljena tukaj v rumeno.
Z drugimi besedami, če Mike Smith je že v knjigi,
nam ni treba navesti korak za korakom, zdaj, kako iti ga našli.
Nimamo navesti da se vrnete na liniji 3,
Zakaj ne bi samo namesto, recimo, bolj splošno,
iskanje Mike v leva polovica knjige.
>> Nasprotno pa, če je Mike dejansko kasneje v knjigi,
zakaj ne bomo samo citiram konec citata iskanje za mikrofon desni polovici knjige.
Z drugimi besedami, zakaj ne bomo samo nekako punt, da sami pravijo,
iskanje Mike v tem podmnožica knjige,
in pustite, da naše obstoječe algoritem, da nam pove
kako iskati za mikrofon da je leva polovica knjige.
Z drugimi besedami, naši Algoritem deluje ali je
telefonski imenik te debeline, od tega debelina, ali katere koli debeline whatsoever.
Tako smo lahko rekurzivno opredeliti ta algoritem.
Z drugimi besedami, na Zaslon tukaj, je algoritem
za iskanje Mike Smith Med straneh telefonskega imenika.
Torej, v skladu 7 in 10, dajmo samo reči točno to.
In uporabljam ta izraz trenutek nazaj, in res, rekurzija
je buzzword za zdaj, in to je ta proces
delaš nekaj cikličnega jih nekako s pomočjo kode, ki jo že imate,
in ga ponovno kliče, in znova in znova.
Zdaj se dogaja, da je pomembno da smo nekako dno
ven, in ne to, da neskončno dolgo.
V nasprotnem primeru bomo imajo res neskončno zanko.
Ampak poglejmo, če lahko sposodim to idejo iz rekurzije, spet delaš nekaj
in znova in znova, rešiti problem sortiranje preko spajanja
razvrščanje, toliko bolj učinkovito.
>> Zato sem vam zlivanjem.
Oglejmo pogled.
Torej, tukaj je psevdokoda, s ki bi ga lahko izvaja sortiranje,
uporabo tega algoritem imenovan zlivanjem.
In to je zelo preprosto je to.
Na vhodu n elementov, z drugimi besedami, če ste
glede n elementi in številke in črke ali karkoli je vhod,
če si dal n elementi, če n je najmanj 2, samo vrnitev.
Prav?
Ker če je n manj kot 2, da pomeni, da je moj seznam elementov
je eden od velikosti 0 ali 1, in v obeh nepomembnih primerih
seznam je že urejeno.
Če ne obstaja seznam, je to urejeno.
In če je seznam dolžine 1, to je očitno razporejene.
Torej algoritem potrebuje le res kaj zanimivega,
Če imamo dva ali več elementi, ki nam.
Zato si oglejmo čarobno takrat.
Else razvrstiti levo polovico elementov, nato razvrstite desni polovici elementov,
spojite razvrščeni polovic.
In kaj je nekako uma upogibanje tukaj, je, da sem v resnici ne
Zdi se, da ti je povedal karkoli samo še, kajne?
Vse sem rekel je, glede na seznam n elementi, razvrstiti levo polovico,
nato desno polovico, nato združiti razvrščeni polovic,
kje pa je dejanska skrivnost omako?
Kje je algoritem?
No, izkaže se, da teh dveh vrsticah Prvi, sortiranje levo polovico elementov,
in nekako desno polovico elementov, so rekurzivne klice, tako rekoč.
>> Konec koncev, na to točka v času, moram
algoritem, s katerim bi razvrstiti cel kup elementov?
Da.
To je prav tukaj.
To je prav tukaj na zaslonu, in tako da sem lahko uporabite isti niz korakov
razvrstiti levo polovico, kot sem lahko desno polovico.
In res, spet in spet.
Torej, tako ali drugače, in bomo kmalu glej to čarobno zlivanjem
je vdelana s tem, da zelo končni črta, ki združuje urejen polovic.
In da se zdi precej intuitivno.
Vzameš dve polovici, in vas, nekako, jih združiti skupaj,
in bomo videli konkretno v trenutku.
>> Ampak to je popolna algoritem.
In poglejmo, zakaj točno.
No, domnevam, da smo zaradi teh istih osem elementi tukaj na zaslonu, ena
skozi osem, ampak oni v navidezno naključnem vrstnem redu.
In cilj pri roki, je razvrstiti te elemente.
No, kako se lahko lotim to počne s pomočjo, še enkrat,
zlivanjem, glede na to psevdokoda?
In spet, Okorio to tvoj um, samo za trenutek.
Prvi primer je precej nepomembno, če je manj kot 2,
pravkar vrnil, ni dela, da je treba storiti.
Torej res obstaja le tri koraki, da bo res v mislih.
Spet in spet sem dogaja, da želijo imeti
razvrstiti levo polovico, razvrstiti desno polovico,
in nato enkrat na njihovo Polovici so razporejene,
Hočem, da jih združi skupaj v eno sortirane seznamu.
Tako da se vodijo v mislih.
>> Torej, tukaj je prvotni seznam.
Oglejmo obravnava to kot matrika, kot smo začeli
v dveh tednih, ki je sosednje blok pomnilnika.
V tem primeru, ki vsebuje osem številke, back to back to back.
In kaj je zdaj uporabljajo zlivanjem.
Tako sem najprej želeli razvrstiti leva polovica tega seznama
In da zato, osredotočajo na 4, 8, 6, in 2.
>> Zdaj, kako naj grem o sortiranje seznam velikosti 4?
No, moram premisliti sortiranje levi levi polovici.
Še enkrat, kaj je nazaj za trenutek.
Če psevdokoda je to, in sem dal osem elementov,
8 je seveda večja od ali enak 2.
Torej s prvi primer ne velja.
Torej, da razvrstite osem elementov, sem najprej razvrstiti levo polovico elementov,
Nato sem razvrstiti desno polovico, nato pa sem se združita dve razporejene polovici, vsaka velikosti 4.
V REDU.
>> Ampak, če ste pravkar mi je povedal, razvrstite leva polovica, ki je sedaj velikosti 4,
kako razvrstiti levo polovico?
No, če Imam vložek iz štirih elementov,
Sem najprej razvrstiti levo dva, nato desno dva,
in potem sem jih združi skupaj.
Torej spet postane nekoliko iz uma upogibanje igre tukaj,
ker tebe, vrsta, moral spomnite, kje ste v zgodbi,
vendar ob koncu dneva, dati poljubno število elementov,
boste najprej želeli razvrstite levo polovico, nato desno polovico,
nato pa jih združiti skupaj.
Začnimo storiti točno to.
Tukaj je vhod iz osmih elementov.
Zdaj smo iskali na levi polovici tukaj.
Kako rešiti štiri elemente?
Pa sem levo polovico najprej razvrstiti.
Zdaj kako razvrstiti levo polovico?
No, jaz sem dobila dva elementa.
Torej, kaj je rešiti teh dveh elementov.
2 je večja ali enak 2, seveda.
Tako da prvi primer ne velja.
>> Tako da sem zdaj razvrstiti levo polovica teh dveh elementov.
Levo polovico, seveda, je le 4.
Torej, kako razvrstiti seznam en element?
No sedaj, da je posebna osnovna do vrha, tako rekoč, velja.
1 je manj kot 2, in moj Seznam je seveda od velikosti 1.
Torej sem vrnil.
Jaz ne delam ničesar.
In res, poglej, kaj sem storiti, 4 je že urejeno.
Tako kot sem že delno uspešna tukaj.
>> Zdaj, ko se zdi nekako neumno zahtevati, vendar je res.
4 je seznam velikosti 1.
To je že urejeno.
Da je leva polovica.
Zdaj sem desno polovico razvrstiti.
Moj vložek je eden od elementov, 8 podobno že urejeno.
Neumna, preveč, ampak spet, To osnovno načelo
se dogaja, da nam omogočajo, da sedaj gradijo poleg tega uspešno.
4 razporejene, 8 je razvrščen, zdaj kaj je bilo to zadnji korak?
Torej, tretji in zadnji korak, vsaka ko boste sortiranje seznamu, odpoklic,
je bil združiti dve polovici, levo in desno.
Torej, kaj je naredil točno to.
Moja leva polovica je, seveda, 4.
Moja desna polovica je 8.
>> Torej, kaj je to.
Najprej bom dodeliti nekateri dodatni spomin,
da bom predstavljajo tu, le kot sekundarni array,
ki je dovolj velika, da ustreza to.
Ampak si lahko predstavljate razširitev da pravokotnik po celotni dolžini,
če bomo potrebovali več kasneje.
Kako naj vzamem 4 in 8, in združitev ti dve seznami velikosti 1 skupaj?
Tudi tu je precej preprosta.
4. na prvem mestu, potem pa pride 8.
Ker če želim, da razvrstite levo polovico, nato desno polovico,
in nato združiti teh dveh polovic skupaj, v urejenih namenom,
4. na prvem mestu, potem pa pride 8.
>> Tako se zdi, da je treba doseči napredek, čeprav čeprav nisem storil nobenega dejanskega dela.
Ampak ne pozabite, kje smo v zgodbi.
Smo sprva vzel osem elementov.
Razporejene smo levi polovici, ki je 4.
Potem smo razporejene levo polovico levega pol, ki je bil 2.
In gremo.
Mi smo storili s tem korakom.
>> Torej, če smo razporejene levo polovico 2, zdaj smo
morali razvrstiti desni polovici 2.
Torej je pravica pol 2 je ti dve vrednosti tukaj, 6 in 2.
Torej, kaj je zdaj traja vhod velikosti 2, in razvrstiti levo polovico, nato pa
desno polovico, in nato jih združiti skupaj.
No, kako razvrstiti seznam velikosti 1, ki vsebuje samo številko 6?
Jaz sem že naredil.
Ta seznam velikosti 1 razporejene.
>> Kako rešiti še en seznam velikost 1, tako imenovani desno polovico.
No to, preveč, je že urejeno.
Številka 2 je sam.
Torej, zdaj imam dve polovici, levo in Dobro, moram, da jih združi skupaj.
Naj sam dal nekaj dodatnega prostora.
In dal 2 v tam, Nato 6 tja, s čimer
sortiranje ta seznam, levo in desno, in ga združujejo, na koncu.
Torej sem v nekoliko boljši formi.
Ne bom storil, ker je jasno 4, 8, 2, 6 ni končni vrstni red, ki ga želim.
Ampak zdaj imam dva seznama velikosti 2, ki sta, v tem zaporedju, so razporejene.
Torej, zdaj, če ste nazaj v tvoj um je oko, kjer je, ki nas pusti?
Začel sem z osem elementov, potem sem ga whittled navzdol na levi polovici 4,
potem levi polovici 2 in nato desno polovico 2,
Končal sem zato, sortiranje levo pol 2 in desno polovico od 2,
Torej, kaj je tretji in zadnji korak tukaj?
Moram skupaj združiti dva seznama velikosti 2.
Torej, gremo naprej.
In na zaslonu Daj me nekateri dodatni pomnilnik,
čeprav tehnično, opazili, da sem imam cel kup prazen prostor do vrha
tam.
Če želim biti še posebej učinkovite prostor pametno,
Jaz lahko samo začnejo premikati elemente naprej in nazaj, zgoraj in spodaj.
Ampak samo za vizualno jasnosti, Jaz grem, da ga spodaj,
da se stvari lepo in čisto.
>> Torej imam dva seznama velikosti 2.
Prvi seznam je 4 in 8.
Drugi seznam je 2 in 6.
Oglejmo združiti tiste, skupaj v urejenem zaporedju.
2, seveda, na prvem mestu, potem 4, potem 6, nato pa 8.
In zdaj se zdi, da se pridobivanje nekje zanimivo.
Zdaj sem razporejene polovica seznam, in po naključju, saj je
vse sode številke, ampak da je, seveda, zgolj naključje.
In zdaj so razporejene levo pol, tako, da je 2, 4, 6 in 8.
Nič ni v okvari.
Da se počuti kot napredek.
>> Zdaj se počuti, kot da sem imel govoril večno sedaj,
Torej, kaj se bo pokazalo, če je to algoritem je pravzaprav bolj učinkovito.
Ampak gremo skozi je super metodično.
Računalnik seveda bi to naredil tako.
Torej, kje smo?
Začeli smo z osmimi elementi.
I razporejene levi polovici 4.
Zdi se mi, da je treba opraviti s tem.
Torej, zdaj naslednji korak je, da razvrstiti desni polovici 4.
In ta del lahko gremo skozi malo bolj
hitro, čeprav ste dobrodošli nazaj ali pavza, samo
mislim skozi njo na svoj tempo, ampak kaj
imamo zdaj priložnost, da se narediti točno isto algoritem na štirih
različne številke.
>> Torej, gremo naprej in se osredotočiti na desna polovica, ki smo tukaj.
Leva polovica da desno polovico, in zdaj
leva polovica levi polovica tega desni polovici,
in kako razvrstiti seznam velikosti 1 vsebuje samo številko 1?
To je že storila.
Kako naj storijo enako za seznam z velikostjo 1, ki vsebuje samo 7?
To je že storila.
Tretji korak za to pol potem je združevanje teh dveh elementov
v nov seznam velikosti 2, 1 in 7.
Ne zdi, da so storili vse, da je precej zanimivo delo.
Poglejmo, kaj se zgodi naslednje.
Pravkar sem razporejene na levi polovici Desna polovica mojega prvotnega vhoda.
Zdaj pa razvrstiti pravico pol, ki vsebuje 5 in 3.
Poglejmo še enkrat poglej na levi strani pol, razporejene, z desno polovico, razporejene,
in združitev teh dveh skupaj, v nekaj dodatnega prostora,
3 na prvem mestu, potem pa pride 5.
In tako zdaj smo razporejene levi polovici desni polovici
prvotnega problema, Desna polovica desni polovici
prvotnega problema.
Kaj je tretji in zadnji korak?
No, da se združijo teh dveh polovic skupaj.
Zato mi dovolite, omisliti nekaj dodaten prostor, toda spet sem
bi lahko z uporabo tega rezervnega prostora do vrha.
Ampak bomo obdržati preprosto vizualno.
Dovolite mi, da se združijo v zdaj 1, in nato 3, nato pa 5, nato 7.
S tem me je pustil zdaj z desno polovico originalnega problema
ki je popolnoma urejeno.
>> Torej, kaj ostane?
Počutim se, kot da sem obdržati pravijo iste stvari znova in znova,
ampak to je odbojni od Dejstvo, da smo s pomočjo rekurzijo.
Postopek uporabe Algoritem znova in znova,
na manjše podskupine prvotna problem.
Torej sem sedaj levi razporejene polovico prvotnega problema.
Imam pravico urejen polovico prvotnega problema.
Kaj je tretji in zadnji korak?
Oh, to je združitev.
Torej, kaj je to.
Oglejmo dodeliti nekatere dodatne spomin, ampak moj bog, smo
bi ga kjerkoli zdaj.
Imamo toliko prostora na voljo za nas, ampak bomo to bo enostavno.
Namesto da bi šel nazaj in tja s svojo izvorno spomin,
kaj je samo to vizualno tukaj spodaj,
do konca gor združitvijo levo polovico in desno polovico.
>> Torej z združitvijo, kaj moram storiti?
Želim, da bi elemente v redu.
Tako je videti na levi polovici, Vidim, da je prva številka je 2.
Gledam desni polovici, Vidim prvo številko
1, tako da je očitno, ki številka ne želim, da izderi
in dal najprej v moji končni seznam?
Seveda 1.
Zdaj pa bi rad vprašal to isto vprašanje.
Na levi polovici, sem imel Še vedno imam številko 2.
Na desni polovici, Imam številko 3.
Kateri želim izbrati?
Seveda, številka 2 In zdaj opazili kandidate
so 4 na levi, 3 na desni strani.
Poglejmo, seveda, izberite 3.
Zdaj kandidati so 4 na levo, 5 na desni strani.
Mi, seveda izbere 4.
6 na levi strani, 5 na desni strani.
Mi, seveda izbere 5.
6 na levi strani, 7 na desni strani.
Bomo izbrali 6, nato pa smo izbrati 7, nato pa smo izbrali 8.
Voila.
>> Tako veliko število besed, kasneje smo so razporejene ta seznam osmih elementov
v seznamu enega do osem, da se povečuje z vsakim korakom,
ampak koliko časa si da nas bo, da to storim.
No Sem namenoma Laid stvari slikovno
tukaj, tako da lahko nekako videti ali cenijo delitev
pri osvajanju, ki se je dogajalo.
>> Pravzaprav, če se ozremo na sedmini, Sem pustil vse te pikčastih črt
V imetnikov mestu, lahko, vrsta, glej v obratnem vrstnem redu,
če ste nekako se ozremo v Zgodovina sedaj, moj prvotni seznam
je seveda velikosti 8.
In potem že prej, sem bil ki se ukvarjajo z dvema seznamov velikosti 4,
in nato štiri liste velikosti 2, in nato osem seznami velikosti 1.
>> Torej, kaj je to, vrsta, vas spominja?
No, dejansko je katerakoli algoritmi, ki smo jih
pogledal tako daleč, kjer smo razkorak, in razkorak, in razkorak,
da ima stvari še enkrat, in spet kaže v tej splošni ideji.
In tako je nekaj logaritemsko dogaja.
In to ni čisto log n, vendar tam je logaritemsko komponenta
s tem, kar smo pravkar končali.
>> Zdaj pa razmisli, kako je v resnici.
Torej log n, spet je bil veliko časa teče,
ko smo naredili nekaj podobnega dvojiško iskanje, kot smo zdaj pravijo,
razkorak in vladaj strategije prek katere smo ugotovili, Mike Smith.
Zdaj tehnično.
To je dnevnik lokaciji 2 n, celo čeprav v večini matematike razrede,
10 je običajno osnova, ki jo prevzemajo.
Ampak računalniški znanstveniki skoraj vedno razmišljati in govoriti v smislu osnove 2,
tako da smo na splošno samo reči dnevnik n, namesto log baze 2 n,
ampak oni so natanko eno in Enako v svetu računalniku
znanost in kot prahi, tam je konstanten faktor
Razlika med njima, tako da je nepotreben vseeno, za več formalnih razlogov.
>> Ampak za zdaj, kaj nam je mar o je ta primer.
Torej naj ne izkaže z zgledom, temveč na vsaj uporabite zgled številk
pri roki kot preverjanje razumnosti, če hočete.
Torej prej formula je log baza 2 n, ampak kaj je n v tem primeru.
Imel sem n originalne številke, ali 8 od prvotne številko posebej.
Zdaj je že malo medtem, ampak sem precej
prepričani, da je log baza 2 vrednosti 8 je 3,
in seveda, kar je lepo, pa, da je da 3 je ravno kolikokrat
da lahko razdelite seznam dolžine 8 znova in znova,
in spet, dokler ste zapustili sezname samo velikosti 1.
Prav?
8 gre do 4, gre 2, gre za 1, in to je
odražajo točno to picture smo imeli pred nekaj trenutki.
Torej malo sanity check, kje logaritem dejansko gre.
>> Torej, zdaj je kaj tukaj vpleten? n.
Tako opazili, da se vsak Tokrat sem razdelila seznam,
čeprav v obratnem vrstnem redu v zgodovini tukaj, sem bil še vedno počne n stvari.
Ta korak je združitev potrebna, da Dotaknem vsak od številk,
da se ga potisnite njeno primerno lokacijo.
Torej, čeprav je višina tega diagram je z velikostjo log n n ali 3,
Natančneje, z drugimi besedami, Naredil sem tri divizije tukaj.
Koliko dela sem naredil horizontalno ob tem grafikonu vsakič?
>> No, sem n korake delati, ker če sem
dobil štiri elemente in štiri elemente, in moram, da jih združi skupaj.
Moram iti skozi te štiri in te štiri,
nazadnje, da jih združi nazaj na osem elementov.
Če nasprotno Imam osem prstov tukaj, kar jaz ne, in osem
fingers-- sorry-- če sem dobil štiri prste tukaj,
ki sem ga naredil, štiri prste sem, ki sem jo naredil,
potem je to isto na primer kot prej, če naredim
imajo osem prstov, čeprav v skupaj, kar sem lahko, vrsta, storite.
Ne morem točno tukaj storiti, potem sem lahko zagotovo
združitev vseh teh seznamov velikosti 1 skupaj.
Ampak jaz zagotovo morali pogledati v vsakem elementu natanko enkrat.
Torej je višina tega procesa je log n, širina tega procesa, tako rekoč
je n, torej tisto, kar se zdi, da imajo, navsezadnje, je
teče čas velikosti n krat log n.
>> Z drugimi besedami, smo razdelili seznam, log n-krat,
ampak vsakič, ko smo naredili, da smo imeli na dotik vsak od elementov
da bi se ju združi vse skupaj, kar
je n korak, tako da imamo n krat log n, ali kot bi računalniški znanstvenik reči,
asimptotično, ki bi bila velika beseda
opisati zgornji vezan na čas teče,
smo se izvajajo v Big O log n časa, tako rekoč.
>> Zdaj je to pomembno, ker spomniti, kaj so tekoči časi
z mehurček vrste in izbor razvrščanje in vstavljanje razvrščanje,
in še nekaj drugih, ki obstajajo, n kvadrat je bilo, kje smo bili na.
In lahko, vrsta, videti tukaj.
Če je n kvadrat očitno n-krat n, ampak tukaj smo n-krat log n,
in smo že vedeli iz tedna nič, da log n, logaritemsko,
je boljše kot nekaj, kar linearno.
Konec koncev, se spomni sliko z rdečo in rumeno
in zelene črte, da smo pripravili, The zelena logaritemsko linija je bila precej nižja.
In zato je veliko bolje in hitreje od ravne rumenimi in rdečimi črtami,
n-krat log n je namreč bolje, kot n-krat n ali n kvadrat.
>> Tako se zdi, da imajo Identificirali algoritem spajanje
vrste, ki teče v veliko krajši čas, in res,
to je zato, v začetku tega tedna, ko se smo videli, da je tekmovanje med mehurček
razvrščanje, izbira vrste in združiti razvrščanje, urejanje z zlivanjem res, res zmagal.
In res, nismo še počakati za mehurček vrste in izbire vrste
končati.
>> Sedaj vzemimo eno drugo točno na to, od nekoliko bolj
formalni vidik, samo v primeru to odmeva bolje
od tega višjo razpravo ravni.
Torej, tukaj je algoritem znova.
Naj vprašam sebe, kaj čas teče
je to algoritmi različne korake?
Naj ga razdelite na prvi primera in v drugem primeru.
IF in ELSE V primeru IF, Če je n manj kot 2, samo vrnitev.
Počutim se kot konstantni čas.
To je, nekako tako kot dveh korakih, Če je n manj kot 2, nato vrne.
Ampak kot smo rekli v ponedeljek, konstanten čas, ali pa velik o po 1,
lahko dva koraka, tri koraki, celo 1.000 korakov.
Kar je pomembno, je, da je konstantno število korakov.
Torej rumeno poudarjena psevdokoda tukaj teče v, imenovali jo bomo,
konstantna čas.
Torej bolj formalno in bomo to-- to
bo obseg, v katerem smo formalizira ta pravico now-- T n,
čas problem teče da je n somethings kot vhod,
enako velik o enega, ČE je n manj kot 2.
Torej je odvisna od tega.
Torej, da bo jasno, če je n manj kot 2, imamo zelo kratek seznam, nato pa
čas teče, T n, kjer je n 1 ali 0, v tem posebnem primeru,
to je le, da bo konstantna čas.
To se dogaja, da imajo eno korak, dva koraka, karkoli.
To je določeno število korakov.
>> Torej mora sočno del zagotovo v drugi primer v psevdokoda.
Primer drugega.
Razvrsti leva polovica elementov, nekako desno polovica elementov, spajanje Urejeni polovic.
Kako dolgo traja vsak od teh korakov trajalo?
No, če je tek Čas je, da n elemente razvrstiti
je, dajmo ga pokličete zelo generično, T n,
nato sortiranje levo polovica elementov
je, nekako, kot bi rekli, T n deliti z 2,
in podobno razvrščanje desni polovici elementov je, nekako, kot bi rekli,
T n razdeljena 2 in nato združitvijo razvrščeni polovic.
No, če imam nekaj število elementov tod
kot štiri, in nekaj več elementov tod kot štiri,
in moram združiti vsaki od teh štirih V, in vsak od teh štirje, eno
Po drugi strani, tako da končno imam osem elementov.
Zdi se mi, da je to velik o n korakov?
Če imam n prste in vsak od jih je treba združiti v mestu,
to je tako kot drugi n korakih.
>> Torej res formulaically, bomo lahko to izraziti,
čeprav malo strašljivo na prvi pogled, vendar pa je nekaj
da zajame točno to logiko.
Čas teče, T n, če je n je večja ali enaka 2.
V tem primeru, v primeru drugega, je T n deliti z 2, plus T N deliti z 2,
plus velik o n, nekateri linearna število korakov,
morda ravno n, morda 2 krat n, ampak to je približno, da bi n.
Tako da, preveč, je, kako smo lahko formulaically izraziti to.
Zdaj pa ne bi vedel, če tega ste jo zabeležili v tvoji glavi,
ali ga poiščete v nazaj učbenika, ki
morda malo goljufija stanja na koncu,
ampak to je, seveda, bo da nam veliko o n log n,
ker je ponovitev da ste tukaj videli na zaslonu,
če ste dejansko to storil, da bodo z neskončno število primerov,
ali ste to storili formulaically, bi si vidim, da je to, ker to formulo
sama rekurzivno, s t n čez nekaj na desni strani,
in t N nad na levi strani, to lahko dejansko se je izrazil, navsezadnje,
tako velika go n log n.
Če ni prepričan, da je Globa za zdaj, samo
sprejeti na veri, da je to, res, kaj to ponovitev vodi,
ampak to je samo malo bolj za matematični pristop k iščejo
ob zlivanjem teče na podlagi svoje psevdokoda sam.
>> Zdaj pa si malo odzračevalni od vseh, da
in vzemite si na nekateri nekdanji senator, ki je
Morda poglej malo pozna, ki je sedel z Googlovim Ericom
Schmidt, pred nekaj časa za razgovor na odru, pred cel kup
ljudi, ki govori o koncu tema, ki je zelo zdaj pozna.
Oglejmo pogled.
>> Eric Schmidt: Zdaj Senator, ste tukaj na Googlu,
in mi je všeč, da razmišljajo od predsedstvo kot razgovor za službo.
Zdaj je težko dobiti službo kot predsednik.
Predsednik Obama: Right.
Eric Schmidt: In vi ste naredili [neslišno] zdaj.
Prav tako je težko dobiti službo pri Googlu.
Predsednik Obama: Right.
>> Eric Schmidt: Imamo vprašanja, in naprošamo naše kandidatov vprašanja,
in to je eden od Larry Schwimmer.
>> Predsednik Obama: OK.
>> Eric Schmidt: Kaj?
Mislita, da sem hecam?
To je prav tukaj.
Kaj je najbolj učinkovit način za razvrstiti milijon 32 bitnih celih števil?
>> Predsednik Obama: Well--
Eric Schmidt: Včasih, Mogoče mi je žal, maybe--
Predsednik Obama: Ne, ne, ne, ne, ne, jaz think--
Eric Schmidt: To ni it--
Predsednik Obama: I mislim, mislim, da je mehurček
nekako bi bila napačna pot.
Eric Schmidt je: Pridi.
Kdo mu je to povedal?
V REDU.
Nisem storil računalništvo on--
>> Predsednik Obama: Smo jih dobil svoje vohune tam.
Profesor: V redu.
Pustimo za nami zdaj Teoretični svet algoritmov
v asimptotskega analizo Pogodbe, in se vrniti v nekaterih temah
od tedna nič in ena, in na začetku odstraniti nekaj koles za usposabljanje,
če hočete.
Tako da boste zares razumeli v končni fazi od tal navzgor, kar je
dogaja pod pokrovom, ko vas pisanje, sestavljanje in izvajanje programov.
Spomnimo se zlasti, da je bila ta prvi program C smo pogledal,
kanonični, preprost program z menoj, relativno gledano,
pri čemer se natisne, Hello World.
In opozarjajo, da sem rekel, proces da je izvorna koda gre skozi
je točno to.
Vzameš svojo izvorno kodo, mimo je skozi prevajalnik, kot Jek,
in ven pride objektno kodo, ki morda videti takole ničel in enic
da CPU računalnika, centralno procesna enota ali možganov,
končno razume.
>> Izkazalo se je, da je, da je malo pretirano poenostavljanje,
da smo zdaj v Položaj narazen draži
razumeti, kaj je res bilo dogaja pod pokrovom
vsakič, ko zaženete Jek, ali bolj na splošno,
vsakič, ko bo program, uporabo Znamka in CF 50 IDE.
Še posebej, stvari, kot so To je prva ustvarila,
ko ste prvič pripravijo svoj program.
Z drugimi besedami, ko vas vzemite izvorno kodo
in ga prevesti, kaj je prva se jih dobi na izhodu Jek
je nekaj, kar je znano kot assemblerju.
In v resnici, je videti natanko tako kot je ta.
>> Sem tekel ukaz v ukazni vrstici prej.
Jek Dash prestolnice s hello.c, in to ustvaril datoteko
za mene imenovanih hello.s, znotraj katerega so bili natančno
te vsebine, in malo več Zgoraj in malo bolj spodaj,
vendar sem dal juiciest informacije tukaj na zaslonu.
In če pogledate pozorno, boste videli, vsaj nekaj seznanjeni s ključnimi besedami.
Imamo glavni na vrhu.
Imamo printf navzdol po sredini.
In imamo tudi zdravo svet poševnica nazaj n v narekovajih spodaj navzdol.
>> In vse ostalo tukaj je navodila zelo nizki ravni
da CPU računalnika razume.
CPU navodila, ki se premikajo spomin okoli, da obremenitve strune iz spomina,
in končno, print stvari na zaslonu.
Zdaj, kaj se zgodi, čeprav po ta skupščina koda se generira?
Konec koncev, kaj ne, res, še vedno ustvarjajo objektno kodo.
Toda koraki, ki imajo res se dogaja pod pokrovom
poglej malo več, kot je ta.
Izvorna koda postane montažo kodo, ki nato postane objekt številka,
in operativne besede so tukaj, da se ko zbere svojo izvorno kodo,
ven pride montažo kodo in nato ko si sestavite svoj sklop kodo,
ven pride objektno kodo.
>> Zdaj Jek je super prefinjen, kot veliko prevajalniki,
in to ne vse od teh korakov skupaj, in to ne nujno
izhod katerokoli vmesno datoteke, ki jih lahko tudi vidite.
Samo sestavlja stvari, ki je splošni izraz, ki
opisuje ta celoten proces.
Ampak, če si zares želite da je zlasti tam
veliko več dogaja tudi tam.
>> Ampak kaj je razmisliti tudi zdaj, da tudi da je super preprost program, hello.c,
imenuje funkcija.
Pozval printf.
Ampak nisem napisal printf, res, ki prihaja s c, če se tako izrazim.
To je funkcija odpoklic, ki je prijavljeni v standardnem io.h, ki
Datoteka je glava, ki je tema, da bomo dejansko
potopite v večjo globino pred dolgo.
Ampak datoteka glave je običajno spremlja
s kodno dokumentacije, izvorne kode datoteko, tako podobno kot obstaja standardni io.h.
>> Včasih nazaj, je nekdo, ali nekoga, tudi napisal
datoteka imenuje standardni io.c, v ki dejansko opredelitve,
ali izvedbe printf, in grozde drugih funkcij,
dejansko napisal.
Torej, glede na to, če menimo, da je ob tukaj na levo, hello.c, da ko
zbrani, nam daje hello.s, četudi Zvoka ne moti varčevanje v mestu
smo lahko videli, in da je montaža koda dobi sestavljeni v hello.o, ki
je res, privzeto ime saj vsakič, ko zbere vir
kodo v kodi, vendar niso povsem pripravljen, da ga še izvršiti,
ker drugi korak se mora zgoditi, in ima
je dogajalo v zadnjih nekaj tednov, morda nevede za vas.
>> Natančneje nekje v CS50 IDE, in to,
preveč, bo malo poenostavljanje za trenutek,
je, ali je bila na času, datoteka z imenom standardni io.c,
da nekdo prevedena v Standardne io.s ali enakovredno,
da je potem nekdo sestavil v standardni io.o,
ali pa se izkaže v nekoliko drugačen datoteka
oblika, ki ima lahko drugačen datoteka končnico v celoti,
ampak v teoriji in konceptualno, točno ti koraki se je moralo zgoditi v neki obliki.
Se pravi, da je zdaj ko pišem program,
hello.c, da samo pravi, zdravo svet, in jaz sem z uporabo kode nekoga drugega
kot printf, ki je bila Nekoč Čas, v datoteko imenovano standardno io.c,
potem nekako moram, da mi vzamejo kodi, moji ničel in enic,
in te osebe objekt zakonika ali ničel in enic,
in jih nekako povezati v eno končno datoteko, ki se imenuje zdravo, da
ima vse ničle in tisti iz moje glavno funkcijo,
in vse ničle in tisti, za printf.
>> In res, da je prejšnji postopek imenovana, ki povezuje vaše objektno kodo.
Katerega izhod je izvršljiva datoteka.
Torej, v pravičnosti v spodnjem konec dneva, nič
se je spremenilo od enega tedna, ko smo prvič začeli pripravo programov.
Dejansko, vse to je dogaja pod pokrovom motorja,
zdaj pa smo v položaju, kjer bomo lahko dejansko
draži narazen teh različnih korakov.
In res, na koncu dneva, smo še vedno
Z leve ničel in enic, ki je pravzaprav velik segue zdaj
drugemu zmožnostjo C, da smo niso imeli vzvoda najverjetneje
do datuma, ki je znana kot operaterji bitni.
Z drugimi besedami, tako daleč, kadarkoli smo jih ukvarjal s podatki v C ali spremenljivke v C,
smo imeli stvari, kot so črke in boje in ins
in hrepeni in dvojice in podobno, vendar vsi od teh so vsaj osem bitov.
Mi smo še nikoli ni bila sposobna manipulacijo posameznih bitov,
četudi posamezni bit, smo Veš, lahko predstavlja 0 in 1.
Zdaj se je izkazalo, da je v C, si lahko dobite dostop do posameznih bitov,
če veste sintakse, s katerimi bi dobili na njih.
>> Torej, vzemimo si oglejte na operaterje bitni.
Torej, na sliki tukaj je nekaj znakov, ki smo, vrsta, vrsta, videl prej.
Vidim 'in' znak, vertikalni bar, in še nekateri drugi, kot tudi,
in opozarjajo, da ampersand 'znak je nekaj, kar smo videli prej.
Logični IN operator, kjer imate dva izmed njih skupaj, ali logični ALI
operater, kjer vas imajo dve navpični palici.
Bitni operaterji, ki bomo glej delujejo na bitih posamično,
Samo uporabite eno 'znak, A single navpična vrstica je strešica simbol
pride zraven, malo Tilda, in nato levo
nosilec levi nosilec, ali Pravica nosilec desno držalo.
Vsak od njih ima različne pomene.
>> V resnici pa si oglejte.
Pojdimo stara šola danes in uporaba zaslon na dotik iz minulih dni,
znan kot belo ploščo.
In ta beli svet se dogaja, da nam omogočajo
izraziti nekaj dokaj preprostih simbolov, oziroma nekaj dokaj enostavne formule,
da bomo lahko potem na koncu vzvod, da bi
dostop do posameznika bitov znotraj programa C.
Z drugimi besedami, kaj je to.
Poglejmo najprej pogovor za moment okoli ampersand,
ki je bitni IN operater.
Z drugimi besedami, to je operater, ki omogoča
mi je, da imajo spremenljivke LEVI tipično in spremenljivi desna,
ali posamezna vrednost, da če smo IN jih skupaj, mi daje končni rezultat.
Torej, kaj mislim?
Če je v programu, morate spremenljivko da shranjuje eno od teh vrednosti,
ali pa naj bo enostavno, in samo izpišite ničel in enic posamično,
tukaj je, kako upravljavec ampersand deluje.
0 ampersand 0 se bo enaka 0.
Zdaj, zakaj je to?
>> To je zelo podoben Logični izrazi,
da smo doslej razpravljali.
Če menite, da po vsem, da je 0 false, 0 je napačna, napačna in lažna
je, kot smo razpravljali logično, tudi napačne.
Tako smo dobili 0 tudi tukaj.
Če ste vzeli 0 'in' znak 1, dobro, da je preveč,
se bo 0, ker za to levi izraz bi bilo res ali 1,
da bi morali biti pravi in ​​resnični.
Ampak tukaj imamo false in res, ali 0 in 1.
Zdaj pa še enkrat, če imamo 1 'znak 0, da je tudi se bo 0,
in če imamo 1 'znak 1, Končno pa imamo 1 bit.
Torej, z drugimi besedami, ne delaš kaj zanimivega s tem operaterjem
samo še to ampersand operater.
To je bitni IN operater.
Ampak to so sestavine preko katerega lahko storimo
zanimivih stvari, kot bomo kmalu videli.
>> Zdaj pa si oglejmo le enotni navpična vrstica tukaj na desni strani.
Če imam 0, bit in jaz OR je z, bitni
Operator OR, druga 0 bit, da se dogaja, da mi 0.
Če vzamem 0 malo in ali pa ga z A 1 bit, potem pa grem, da bi dobili 1.
In dejansko samo jasnost, naj gredo nazaj,
tako da moji navpične palice niso zamenjali za 1 je.
Naj znova vse moj 1 je malo bolj
jasno, da bomo dostavo glej če imajo 1 ali 0, da se dogaja, da je 1,
in če imam 1 ali 1, da, Tudi se dogaja, da se 1.
Tako lahko vidite, je logično, da je OR Operater se obnaša zelo različno.
To mi daje 0 ali 0 mi daje 0, vendar vsaka druga kombinacija mi daje 1.
Dokler imam eno 1 v formula, rezultat se bo 1.
>> V nasprotju z AND Upravljavec, ampersand,
samo, če imam dva 1 je v enačba, pa sem dejansko dobil 1 out.
Zdaj je nekaj drugega Operaterji, kot dobro.
Eden od njih je malo bolj vključeni.
Torej, mi gredo naprej in izbrisati to, da sprostite nekaj prostora.
In dajmo si oglejte na strešica simbol, samo za trenutek.
To je tipično Znak lahko vnesete
na tipkovnici skladiščenju Shift in nato pa eno izmed številk na vrhu vašega ZDA
tipkovnico.
>> Torej, to je izključna ALI operater, ekskluzivni OR.
Torej smo pravkar videli upravljavec ali.
To je ekskluzivni OR operator.
Kakšna je pravzaprav razlika?
No, kaj je samo pogled na formulo, in to uporabi kot sestavine v končni fazi.
0 XOR 0.
Jaz bom rekel, je vedno 0.
To je definicija XOR.
0 XOR 1 se bo 1.
1 XOR 0 se bo 1, in 1 XOR 1 se bo?
Narobe?
Ali desno?
Ne vem.
0.
Zdaj, kaj se dogaja tukaj?
No, pomislite na ime tega operaterja.
Ekskluzivni OR, tako kot ime, vrsta, kaže,
Odgovor je le bo A 1, če so vhodi izključujeta,
izključno drugačna.
Torej, tukaj so vhodi so Isto tako je izhod 0.
Tukaj vložki so Isto tako je izhod 0.
Tu so rezultati različni, so ekskluzivni in tako proizvodnja je 1.
Tako da je zelo podobna IN, je zelo podobna,
oziroma je zelo podoben ALI, vendar le v ekskluzivni način.
Tole ni več 1, saj imamo dva 1-jev,
in ne izključno, samo eden od njih.
V redu.
Kaj pa drugi?
No tilda, medtem, je pravzaprav lepo in preprosto, na srečo.
In to je enočlenska subjekt, kar pomeni,
to je uporabljena le en vhod, en operand, tako rekoč.
Ni na levi in ​​desni.
Z drugimi besedami, če ste vzeli tildo za 0, bo odgovor nasprotno.
In če ste vzeli vijuga od 1, je Odgovor bo nasprotno.
Torej tilda subjekt način negira bit,
ali flipping malo od 0 do 1, ali 1 do 0.
>> In da nam ostane na koncu s samo dvema končnih subjektov,
tako imenovani levi premik, in tako imenovana pravica operater premik.
Oglejmo si oglejte, kako se ti delo.
Leve operater premik, napisano z dvema kotnih oklepajih kot je ta,
deluje na naslednji način.
Če je moj vložek, ali moj operand, na levi Operator premik je preprosto 1.
In potem sem povedal, računalnik na levo premik, ki 1, pravijo sedem krajev,
Rezultat je, kot da I da to 1, in ga premakniti
sedem krajev več na levo in ga privzeto,
bomo domnevati, da prostor na desni strani
se bo oblazinjena z ničlami.
Z drugimi besedami, 1 levo premik 7 se dogaja da smo dobili mi, da 1, čemur sledi 1, 2, 3,
4, 5, 6, 7 ničle.
Torej, na nek način, to vam omogoča, da sprejme majhno število kot 1,
in jasno, da je veliko še veliko večja na ta način,
vendar smo dejansko videli bolj pameten pristopi k njej
Namesto tega, kot tudi,
>> V redu.
To je to za tri teden.
Vam bomo videli naslednjič.
To je CS50.
>> [Predvaja glasba]
>> SPEAKER 1: Bil je na malico bar jedo vroče polnilom kupo.
On je vse imel čez obraz.
On je nosil čokolado kot brado
SPEAKER 2: Kaj počneš?
SPEAKER 3: Hmmm?
Kaj?
>> SPEAKER 2: Ali ste pravkar double dip?
Vi dvojni kratki čip.
SPEAKER 3: Oprostite.
SPEAKER 2: Ti kratki čip, si vzel grižljaj, in si spet kratki.
SPEAKER 3:
SPEAKER 2: Torej, to je kot dajanje vaše celotno desno usta v dip.
Naslednjič, ko ste vzeli čip, Samo zamoči enkrat, in ga na koncu.
>> SPEAKER 3: Veš kaj, Dan?
Vi pomočimo način, ki ga želite potopiti.
Bom pomočimo tako da sem želite potopiti.