>> [Musiikkia]
>> PROFESSORI: Selvﾃ､.
Tﾃ､mﾃ､ on CS50 ja tﾃ､mﾃ､ on viikon lopussa kolme.
Joten olemme tﾃ､ﾃ､llﾃ､ tﾃ､nﾃ､ﾃ､n, eikﾃ､ Sanders Teatteri, sen sijaan Weidner kirjasto.
Jonka sisﾃ､llﾃ､ on studio tunnetaan Hauser Studio,
tai sanokaamme Studio H, tai on me say-- jos olet nauttinut ettﾃ､ vitsi,
se on todella maasta luokkatoveri, Mark, verkossa,
joka ehdotti niin paljon Twitterin kautta.
Nyt mitﾃ､ viileﾃ､ noin tﾃ､ﾃ､llﾃ､ studiossa
on ettﾃ､ olen ympﾃ､rﾃｶi Vihreiden seinﾃ､t, green screen tai chromakey,
niin sanoakseni, mikﾃ､ tarkoittaa, ettﾃ､ CS50: n tuotanto joukkue, tietﾃ､mﾃ､ttﾃ､ minulle
nyt voisi olla laskemisesta minua eniten kaikkialla maailmassa,
parempaan tai huonompaan.
>> Nyt mitﾃ､ on edessﾃ､, Harjoitus kaksi on teidﾃ､n kﾃ､sissﾃ､nne Tﾃ､llﾃ､ viikolla
mutta Harjoitus kolme tulevalla viikolla,
teidﾃ､t haastetaan kanssa ns peli 15,
vanhan puolueen puolesta, ettﾃ､ saatat muistaa saaneen
kuin lapsi, joka on koko joukko numeroita, jotka voivat liukua ylﾃｶs, alas,
vasemmalle ja oikealle, ja siellﾃ､ on yksi aukko sisﾃ､llﾃ､ palapeli, johon voit
voi todella liukua ne palapelin palaset.
Lopulta saat tﾃ､mﾃ､n palapeli joissakin semi satunnaisessa jﾃ､rjestyksessﾃ､,
ja tavoitteena on lajitella, ylhﾃ､ﾃ､ltﾃ､ alas,
vasemmalta oikealle, yhdestﾃ､ koko matkan lﾃ､pi 15.
>> Valitettavasti tﾃ､ytﾃ､ntﾃｶﾃｶnpano sinulla on kﾃ､sillﾃ､
tulee olemaan ohjelmisto pohjainen, ei fyysisesti.
Olet todella tﾃ､ytyy kirjoittaa koodia, jotka opiskelija tai kﾃ､yttﾃ､jﾃ､ voi
pelata peliﾃ､ 15.
Ja itse asiassa hakkeri painos peli 15,
sinun on haaste toteuttaa, ei vain pelaaminen tﾃ､mﾃ､n vanhan koulun
peli, vaan ratkaiseminen siitﾃ､, tﾃ､ytﾃ､ntﾃｶﾃｶnpanon jumala tilassa
niin sanoakseni, ettﾃ､ todella ratkaisee palapeli ihmisen,
tarjoamalla heille vihje, jﾃ､lkeen vihje, kun vihje.
Niin siitﾃ､ lisﾃ､ﾃ､ ensi viikolla.
Mutta se, mitﾃ､ on edessﾃ､.
>> Nyt muistaa, ettﾃ､ aiemmin tﾃ､llﾃ､ viikolla meillﾃ､ oli jﾃ､nnitysnﾃ､ytelmﾃ､, jos haluatte,
jolloin paras teemme lajittelu viisas oli ylﾃ､rajana Big O n
potenssiin.
Toisin sanoen, kuplalajittelu, valinta lajitella, lisﾃ､yslajittelun,
ne kaikki, kun taas eri niiden tﾃ､ytﾃ､ntﾃｶﾃｶnpanossa,
siirretty osaksi n potenssiin kﾃ､ynnissﾃ､ aika hyvin pahimmassa tapauksessa.
Ja me yleensﾃ､ olettaa, ettﾃ､ hyvin pahimmassa tapauksessa lajitteluun
on yksi ettﾃ､ tuloa ovat tﾃ､ysin taaksepﾃ､in.
Ja todellakin, se kesti aivan muutaman askeleen toteuttaa jokainen nﾃ､istﾃ､ algoritmeja.
>> Nyt aivan lopussa luokan Recall, vertasimme kuplalajittelu
vastaan 窶銀久alinta lajitella vastaan 窶銀及ksi muu ettﾃ､ kutsuimme yhdistﾃ､ﾃ､ lajitella tuolloin,
ja ehdotan, ettﾃ､ se ottaa etuna oppitunti viikossa
nolla, hajota ja hallitse.
Ja jotenkin saavuttaa jonkinlaista logaritminen kﾃ､yntiaika lopulta,
sijasta jotain se on puhtaasti asteen.
Ja se ei ole aivan logaritminen, se on hieman enemmﾃ､n.
Mutta jos muistatte luokasta, se oli paljon, paljon nopeammin.
Katsotaanpa katsomaan mihin jﾃ､imme.
>> Kuplalajittelu vs. valinta lajitella vs. Yhdistﾃ､misen lajitella.
Nyt he kaikki kﾃ､ynnissﾃ､, vuonna Teoriassa samaan aikaan.
CPU on kﾃ､ynnissﾃ､ samalla nopeudella.
Mutta voit tuntea kuinka tylsﾃ､ﾃ､ tﾃ､mﾃ､ on hyvin nopeasti tulossa,
ja kuinka nopeasti, kun pistﾃ､ﾃ､ hiukan viikon nolla algoritmit,
voimme nopeuttaa asioita.
>> Joten merkki lajitella nﾃ､yttﾃ､ﾃ､ hﾃ､mmﾃ､styttﾃ､vﾃ､n.
Miten voimme hyﾃｶdyntﾃ､ﾃ､ sitﾃ､, jotta lajitella numeroita nopeammin.
No katsotaanpa muistelen ainesosaa ettﾃ､ me
oli takaisin viikolla nolla, ettﾃ､ etsivﾃ､t joku puhelinluettelosta,
ja muistuttaa, ettﾃ､ pseudokoodilla ettﾃ､ ehdotimme,
jonka kautta voimme lﾃｶytﾃ､ﾃ､ joku kuten Mike Smith,
nﾃ､ytti vﾃ､hﾃ､n jotain tﾃ､llaista.
>> Nyt katsomaan erityisesti rivillﾃ､ 7 ja 8, ja 10 ja 11,
joka aiheuttaa ettﾃ､ silmukka, jolloin pidimme menee takaisin linja 3 uudestaan, ja uudestaan,
ja uudelleen.
Mutta kﾃ､y ilmi, ettﾃ､ voimme katsella tﾃ､mﾃ､ algoritmi, tﾃ､ﾃ､llﾃ､ pseudokoodilla,
hieman kokonaisvaltaisemmin.
Itse asiassa, mitﾃ､ etsin klo tﾃ､ﾃ､llﾃ､ ruudulla,
on algoritmi etsii Mike Smith joukossa joitakin joukko sivuja.
Ja todellakin, voisimme yksinkertaistaa tﾃ､mﾃ､ algoritmi ne rivit 7 ja 8,
ja 10 ja 11 vain sanoa, jonka olen esitetﾃ､ﾃ､n tﾃ､ssﾃ､ keltaisella.
Toisin sanoen, jos Mike Smith on aiemmin kirja,
meidﾃ､n ei tarvitse mﾃ､ﾃ､rittﾃ､ﾃ､ vaiheessa askeleelta nyt miten edetﾃ､ lﾃｶytﾃ､ﾃ､ hﾃ､net.
Meillﾃ､ ei tarvitse mﾃ､ﾃ､ritellﾃ､ palata linja 3,
Miksi emme vain sen sijaan, sanoa yleisemmin,
etsi Mike vasen puoli kirjan.
>> Toisaalta, jos Mike on todella myﾃｶhemmin kirjan,
miksi emme vain lainata lainaus haku Mike oikeassa puoliskossa kirjan.
Toisin sanoen, miksi emme vain tavallaan punt itsellemme sanomalla,
etsi Mike tﾃ､ssﾃ､ osajoukko kirjan,
ja jﾃ､ttﾃ､ﾃ､ sen nykyisiﾃ､ algoritmi kertoa meille
miten etsiﾃ､ Mike ettﾃ､ vasen puoli kirjan.
Toisin sanoen, meidﾃ､n algoritmi toimii onko se
puhelinluettelo tﾃ､mﾃ､n paksuus, tﾃ､mﾃ､n paksuus, tai paksuus lainkaan.
Joten voimme rekursiivisesti mﾃ､ﾃ､ritellﾃ､ tﾃ､mﾃ､ algoritmi.
Toisin sanoen, on nﾃ､yttﾃｶ tﾃ､ﾃ､llﾃ､, on algoritmi
etsimiseen Mike Smith keskuudessa sivut puhelinluettelosta.
Joten rivi 7 ja 10, katsotaanpa vain sanoa juuri sitﾃ､.
Ja kﾃ､ytﾃ､n tﾃ､tﾃ､ termiﾃ､ hetki sitten, ja todellakin, rekursio
on muotisana nyt, ja se on tﾃ､mﾃ､n prosessin
tehdﾃ､ jotain syklistﾃ､ jotenkin koodia kﾃ､yttﾃ､mﾃ､llﾃ､ ettﾃ､ sinulla jo on,
ja kutsuen sitﾃ､ uudelleen, ja uudestaan, ja uudestaan.
Nyt se tulee olemaan tﾃ､rkeﾃ､ ettﾃ､ me jotenkin pohja
pois, ja ﾃ､lﾃ､ tee sitﾃ､ ﾃ､ﾃ､rettﾃｶmﾃ､n pitkﾃ､.
Muuten aiomme on todellakin pﾃ､ﾃ､ttymﾃ､ttﾃｶmﾃ､ﾃ､n silmukkaan.
Mutta katsotaan jos voimme lainata tﾃ､tﾃ､ ajatusta rekursiivisen, tehdﾃ､ jotain uudelleen
ja uudestaan 窶銀桔a uudestaan, ratkaista lajittelu ongelma kautta yhdistﾃ､misen
lajitella, kaikki tehokkaammin.
>> Joten annan sinulle yhdistﾃ､ﾃ､ lajitella.
Katsotaanpa katsomaan.
Joten tﾃ､ssﾃ､ on pseudokoodilla, kanssa jotka voisimme toteuttaa lajittelu,
Kﾃ､yttﾃ､mﾃ､llﾃ､ tﾃ､tﾃ､ algoritmia kutsutaan yhdistﾃ､misen lajitella.
Ja se on yksinkertaisesti tﾃ､mﾃ､.
Syﾃｶtteellﾃ､ n alkion, Toisin sanoen, jos olet
annettuja n elementtejﾃ､ ja numeroita ja kirjaimia tai mikﾃ､ tulo on,
jos olet antanut n elementtiﾃ､, jos n on pienempi kuin 2, palaa.
Oikea?
Koska jos n on pienempi kuin 2, ettﾃ､ tarkoittaa, ettﾃ､ minun luettelo elementtien
on joko kokoa 0 tai 1, ja sekﾃ､ nﾃ､issﾃ､ triviaaleja tapauksissa
luettelo on jo jﾃ､rjestetty.
Jos ei ole luettelossa, se on jﾃ､rjestetty.
Ja jos on lista pituus 1, se on tietenkin jﾃ､rjestetty.
Joten algoritmi tarvitsee vain todella jotain mielenkiintoista,
jos meillﾃ､ on kaksi tai useampia elementtejﾃ､ meille annettu.
Joten katsokaamme taika sitten.
Else jﾃ､rjestellﾃ､ vasemmalla puolella elementtejﾃ､, sitten lajitella oikealla puolella elementtejﾃ､,
sitten yhdistﾃ､ﾃ､ lajiteltu puolikkaat.
Ja mikﾃ､ on tavallaan mielen taivutus tﾃ､ﾃ､llﾃ､, on ettﾃ､ en ole oikeastaan
nﾃ､yttﾃ､vﾃ､t mﾃ､ﾃ､rﾃ､nnyt mitﾃ､ﾃ､n ihan vielﾃ､, eikﾃｶ?
Kaikki Olen sanonut on, annetaan luettelo n elementtiﾃ､, lajitella vasen puoli,
sitten oikea puoli, sitten yhdistﾃ､ﾃ､ lajiteltu puolikkaat,
mutta missﾃ､ on todellinen salainen kastike?
Missﾃ､ algoritmi?
No nﾃ､yttﾃ､ﾃ､ siltﾃ､, 窶銀菊ttﾃ､ nﾃ､mﾃ､ kaksi riviﾃ､ ensimmﾃ､inen, erﾃ､ﾃ､nlainen vasen puoli elementtejﾃ､,
ja tavallaan oikea puoli elementtejﾃ､, ovat rekursiokutsua, niin sanoakseni.
>> Onhan tﾃ､ssﾃ､ vaiheessa, minulla on
algoritmi, jolla voidaan lajitella koko joukko tekijﾃｶitﾃ､?
Kyllﾃ､.
Se on tﾃ､ﾃ､llﾃ､.
Se on tﾃ､ﾃ､llﾃ､ ruudulla, ja joten voin kﾃ､yttﾃ､ﾃ､, ettﾃ､ samoja vaiheita
lajitella vasen puoli, kuin voin oikea puoli.
Ja todellakin, uudestaan, ja uudestaan.
Joten tavalla tai toisella, ja me pian nﾃ､hdﾃ､ tﾃ､mﾃ､n, taika yhdistﾃ､misen sort
on upotettu ettﾃ､ hyvin lopullisessa linja, yhdistﾃ､mﾃ､llﾃ､ lajitellut puoliskot.
Ja joka tuntuu melko intuitiivinen.
Otat kaksi puoliskoa, ja te, jotenkin, yhdistﾃ､ﾃ､ ne yhteen,
ja nﾃ､emme tﾃ､mﾃ､n konkreettisesti hetki.
>> Mutta tﾃ､mﾃ､ on tﾃ､ydellinen algoritmi.
Ja nyt nﾃ､hdﾃ､ tarkalleen miksi.
No olettaa, ettﾃ､ meille annetaan nﾃ､mﾃ､ samat kahdeksan elementtejﾃ､ tﾃ､ssﾃ､ ruudulla, yksi
kautta kahdeksan, mutta ne ovat nﾃ､ennﾃ､isen satunnaisessa jﾃ､rjestyksessﾃ､.
Ja tavoite kﾃ､sillﾃ､ on lajitella nﾃ､mﾃ､ elementit.
No miten voin mennﾃ､ noin tekee sen avulla, jﾃ､lleen,
yhdistﾃ､ﾃ､ lajitella, kuten per tﾃ､mﾃ､ pseudokoodina?
Ja vielﾃ､, ingrain tﾃ､mﾃ､ mielesi, vain hetken.
Ensimmﾃ､inen tapaus on melko triviaali, jos se on vﾃ､hemmﾃ､n kuin 2,
vain palata, ei ole tehtﾃ､vﾃ､ﾃ､.
Joten oikeastaan 窶銀虐iellﾃ､ on vain kolme toimet todella pitﾃ､ﾃ､ mielessﾃ､.
Jﾃ､lleen ja jﾃ､lleen, olen menossa haluavat olla
lajitella vasen puoli, lajitella oikea puoli,
ja sitten kun niiden kaksi puolikasta lajitellaan,
Haluan yhdistﾃ､ﾃ､ ne yhteen yhdeksi lajiteltu lista.
Niin pitﾃ､ﾃ､ tﾃ､mﾃ､ mielessﾃ､.
>> Joten tﾃ､ssﾃ､ alkuperﾃ､isen luettelon.
Katsotaanpa kﾃ､sittelemﾃ､ﾃ､n tﾃ､tﾃ､ array, kun aloimme
viikolla kaksi, joka on yhtenﾃ､inen alue muistia.
Tﾃ､ssﾃ､ tapauksessa, joka sisﾃ､ltﾃ､ﾃ､ kahdeksan numeroita, takaisin takaisin takaisin.
Ja lﾃ､hdetﾃ､ﾃ､n nyt sovelletaan yhdistﾃ､misen lajitella.
Joten Haluan ensin lajitella vasen puoli tﾃ､mﾃ､n luettelon,
ja nyt, siksi, keskittyvﾃ､t 4, 8, 6, ja 2.
>> Nyt miten voin mennﾃ､ noin lajittelun luettelo koko 4?
No minun tﾃ､ytyy nyt harkita lajittelu vasemmalla vasemmalla puolella.
Jﾃ､lleen, nyt kelata vain hetken.
Jos pseudokoodi on tﾃ､mﾃ､, ja olen antanut kahdeksan elementtejﾃ､,
8 on ilmeisesti suurempi kuin tai yhtﾃ､ suuri kuin 2.
Joten ensimmﾃ､inen tapaus ei koske.
Joten lajitella kahdeksan elementtejﾃ､, haluan ensin lajitella vasemmalla puolella elementtejﾃ､,
sitten lajitella oikea puoli, sitten yhdistﾃ､ﾃ､ kaksi lajitellut puolikkaat, kukin koko 4.
OK.
>> Mutta jos olet juuri kertonut minulle, lajitella vasen puoli, joka on nyt on koko 4,
miten voin lajitella vasen puoli?
No jos minulla on tuloon neljﾃ､ elementtiﾃ､,
Haluan ensin lajitella vasemmalle kaksi, sitten oikea kaksi,
ja sitten yhdistﾃ､ﾃ､ ne yhteen.
Niin uudelleen, se tulee hieman of mielen taivutus peli tﾃ､ﾃ､llﾃ､,
koska te, tavallaan, on muistaa missﾃ､ olet tarina,
mutta loppujen lopuksi, antanut mitﾃ､ﾃ､n useita tekijﾃｶitﾃ､,
ensin haluat lajitella vasen puoli, sitten oikea puoli,
sitten yhdistﾃ､ﾃ､ ne yhteen.
Aloitetaan juuri siihen.
Tﾃ､ssﾃ､ panos kahdeksan elementtejﾃ､.
Nyt me tarkastelemme vasen puoli tﾃ､ﾃ､llﾃ､.
Miten lajitella neljﾃ､ elementtiﾃ､?
No ensin lajitella vasemmalle puolen.
Nyt miten voin lajitella vasen puoli?
No Olen saanut kaksi elementtiﾃ､.
Joten jﾃ､rjestﾃ､ﾃ､ kaksi elementtiﾃ､.
2 on suurempi tai vastaa 2, tietenkin.
Niin ettﾃ､ ensimmﾃ､inen tapaus ei koske.
>> Joten minulla on nyt lajitella vasemmalle puolet nﾃ､istﾃ､ kahdesta elementistﾃ､.
Vasen puoli, tietenkin, on vain 4.
Joten miten voin lajitella luettelon yhden elementin?
No nyt, ettﾃ､ erityistﾃ､ perustapaus ylﾃｶs, niin sanotusti, sovelletaan.
1 on pienempi kuin 2, ja minun luettelo on todellakin koko 1.
Joten en juuri palata.
En tee mitﾃ､ﾃ､n.
Ja todellakin, katso mitﾃ､ olen tehty, 4 on jo jﾃ､rjestetty.
Kuten olen jo osittain onnistunut tﾃ､ssﾃ､.
>> Nyt nﾃ､yttﾃ､ﾃ､ typerﾃ､ﾃ､ vaatia, mutta se on totta.
4 on luettelo koko 1.
Se on jo jﾃ､rjestetty.
Se vasen puoli.
Nyt minﾃ､ lajitella oikea puoli.
Minun panos on yksi elementti, 8 Samoin jo jﾃ､rjestetty.
Tyhmﾃ､, liian, mutta jﾃ､lleen, tﾃ､mﾃ､ perusperiaate
aikoo jotta voimme nyt rakentaa pﾃ､ﾃ､lle tﾃ､mﾃ､n onnistuneesti.
4 lajiteltu, 8 lajitellaan, nyt mikﾃ､ oli viimeinen askel?
Niin kolmas ja viimeinen vaihe, mikﾃ､ tahansa kerran olet lajittelun lista, muistaa,
oli yhdistﾃ､ﾃ､ kaksi puolikasta, vasemmalle ja oikealle.
Joten juuri siihen.
Minun vasen puoli on tietenkin, 4.
Minun oikea puoli on 8.
>> Joten tehdﾃ､ﾃ､n tﾃ､mﾃ､.
Ensinnﾃ､kin aion jakaa jotkut lisﾃ､muistia,
ettﾃ､ minﾃ､ tﾃ､ﾃ､llﾃ､ edustan, koska vain toissijainen array,
joka on iso mahtuakseen tﾃ､hﾃ､n.
Mutta voit kuvitella jatkamisesta ettﾃ､ suorakulmion koko pituudeltaan,
jos tarvitsemme lisﾃ､ﾃ､ myﾃｶhemmin.
Miten otan 4 ja 8, ja yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi luetteloa koko 1 yhdessﾃ､?
Tﾃ､ssﾃ､kin melko yksinkertainen.
4 tulee ensin, sitten tulee 8.
Koska jos haluan lajitella vasen puoli, sitten oikea puoli,
ja sitten yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi puolikasta yhdessﾃ､, lajiteltu jﾃ､rjestyksessﾃ､,
4 tulee ensin, sitten tulee 8.
>> Joten nﾃ､ytﾃ､mme edistyy, vaikka vaikka en ole tehnyt mitﾃ､ﾃ､n varsinaista tyﾃｶtﾃ､.
Mutta muista missﾃ､ olemme tarina.
Olemme alunperin kesti kahdeksan elementtejﾃ､.
Olemme jﾃ､rjestetty vasen puoli, joka on 4.
Sitten lajitellaan vasen puoli vasemman puolen, mikﾃ､ oli 2.
Ja tﾃ､ssﾃ､ sitﾃ､ mennﾃ､ﾃ､n.
Olemme tehneet tﾃ､mﾃ､n askeleen.
>> Joten jos olemme lajiteltu vasen puoli 2, nyt meillﾃ､
on lajitella oikea puoli 2.
Joten oikea puoli 2 on nﾃ､mﾃ､ kaksi arvoa tﾃ､ﾃ､llﾃ､, 6 ja 2.
Joten nyt ottaa panos koko 2, ja lajitella vasen puoli, ja sitten
oikea puoli, ja sitten yhdistﾃ､ﾃ､ ne yhteen.
No miten voin lajitella luettelon koko 1, joka sisﾃ､ltﾃ､ﾃ､ vain numero 6?
Olen jo tehnyt.
Ettﾃ､ luettelo koko 1 lajitellaan.
>> Miten lajitella toinen luettelo koko 1, niin sanottu oikea puoli.
No sekin on jo jﾃ､rjestetty.
Numero 2 on yksin.
Joten nyt minulla on kaksi puoliskoa, vasemmalle ja oikea, minun tﾃ､ytyy yhdistﾃ､ﾃ､ ne yhteen.
Annan itselleni ylimﾃ､ﾃ､rﾃ､istﾃ､ tilaa.
Ja laittaa 2 siellﾃ､, sitten 6 siellﾃ､, mikﾃ､
lajittelu ettﾃ､ luettelo, vasen ja oikea, ja yhdistﾃ､mﾃ､llﾃ､ se yhteen, lopulta.
Joten olen hieman paremmassa kunnossa.
En ole tehnyt, koska selvﾃ､sti 4, 8, 2, 6 ei ole lopullinen tilaus, ettﾃ､ haluan.
Mutta Minulla on nyt kaksi luetteloa koko 2, ettﾃ､ ovat molemmat vastaavasti on lajiteltu.
Joten nyt jos taaksepﾃ､in sielusi silmﾃ､, mistﾃ､ se jﾃ､ttﾃ､ﾃ､ meidﾃ､t?
Aloitin kahdeksan elementtejﾃ､, niin minﾃ､ supistetaan se alas vasemmalla puolella 4,
sitten vasen puoli 2, ja sitten oikea puoli 2,
Lopetin, siis, lajittelu vasen puolet 2, ja oikea puoli 2,
niin mitﾃ､ kolmas ja viimeinen vaihe tﾃ､ssﾃ､?
Minun tﾃ､ytyy yhdistﾃ､ﾃ､ yhdessﾃ､ kaksi luetteloa koko 2.
Joten mene eteenpﾃ､in.
Ja ruudulla tﾃ､ﾃ､llﾃ､, antaa minulle lisﾃ､muistia,
vaikka teknisesti, huomaa, ettﾃ､ olen sai koko joukko tyhjﾃ､ tila ylﾃｶs
siellﾃ､.
Jos haluan olla erityisen tehokkaasti tilaa viisas,
Voisin vain alkaa liikkuvat osat edestakaisin, ylhﾃ､ﾃ､llﾃ､ ja alhaalla.
Mutta vain visuaalinen selkeys, Aion laittaa se alas alla,
pitﾃ､ﾃ､ asiat mukava ja puhdas.
>> Joten minulla kaksi luetteloa koko 2.
Ensimmﾃ､inen luettelo on 4 ja 8.
Toisessa luettelossa on 2 ja 6.
Katsotaanpa yhdistﾃ､ﾃ､ ne yhdessﾃ､ lajiteltu jﾃ､rjestyksessﾃ､.
2, tietenkin, tulee ensin, sitten 4, sitten 6, sitten 8.
Ja nyt me nﾃ､yttﾃ､vﾃ､t saada jonnekin mielenkiintoinen.
Nyt olen lajiteltu puolet luetella, ja sattumalta, se on
kaikki parilliset numerot, mutta ettﾃ､ on todellakin vain sattumaa.
Ja nyt on lajiteltu vasen puoli, ettﾃ､ se on 2, 4, 6, ja 8.
Mikﾃ､ﾃ､n ei ole epﾃ､kunnossa.
Joka tuntuu edistystﾃ､.
>> Nyt tuntuu kuin olisin puhuneet ikuisesti nyt,
niin mitﾃ､ jﾃ､ﾃ､ nﾃ､htﾃ､vﾃ､ksi, jos tﾃ､mﾃ､ algoritmi on todellakin tehokkaampi.
Mutta olemme menossa lﾃ､pi se erittﾃ､in jﾃ､rjestelmﾃ､llisesti.
Tietokone, tietenkin, tekisi sen niin.
Missﾃ､ siis olemme?
Aloitimme kahdeksan elementtejﾃ､.
Olen lajiteltu vasemmalla puolella 4.
Nﾃ､ytﾃ､n tehdﾃ､ sen kanssa.
Joten nyt seuraava askel on lajitella oikea puoli 4.
Ja tﾃ､mﾃ､ osa voimme mennﾃ､ lﾃ､pi hieman enemmﾃ､n
nopeasti, vaikka olet Tervetuloa kelata tai pysﾃ､yttﾃ､ﾃ､, vain
ajatella sen lﾃ､pi omaan tahtiin, mutta mitﾃ､
meillﾃ､ nyt on tilaisuus tehdﾃ､ tﾃ､smﾃ､lleen samaa algoritmia neljﾃ､ﾃ､n
eri numeroille.
>> Joten mene eteenpﾃ､in, ja keskitytﾃ､ﾃ､n oikea puoli, jotka olemme tﾃ､ﾃ､llﾃ､.
Vasen puoli on, ettﾃ､ oikea puoli, ja nyt
vasen puoli vasemman puolet oikea puoli,
ja miten lajitella luettelon koko 1, joka sisﾃ､lsi vain numero 1?
Se on jo tehty.
Miten teen sama lista koon 1, joka sisﾃ､ltﾃ､ﾃ､ vain 7?
Se on jo tehty.
Vaihe kolme tﾃ､hﾃ､n puoli sitten on yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi tekijﾃ､ﾃ､
uuteen luettelo koko 2, 1 ja 7.
Eivﾃ､t nﾃ､ytﾃ､ tehneen kaikki ettﾃ､ paljon mielenkiintoista tyﾃｶtﾃ､.
Katsotaan, mitﾃ､ tapahtuu seuraavaksi.
Olen juuri jﾃ､rjestetty vasemmalla puolella oikea puoli minun alkuperﾃ､inen panos.
Nyt lajitella oikealla puoli, joka sisﾃ､ltﾃ､ﾃ､ 5 ja 3.
Katsotaanpa jﾃ､lleen katsoa vasemmalle puoli, lajiteltu, oikea puoli, lajiteltu,
ja yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi yhdessﾃ､, johonkin lisﾃ､tilaa,
3 tulee ensin, sitten tulee 5.
Ja nyt olemme lajiteltu vasemmalla puolella oikea puoli
alkuperﾃ､isen ongelman, ja oikea puoli oikea puoli
alkuperﾃ､isen ongelman.
Mikﾃ､ on kolmas ja viimeinen vaihe?
Hyvin yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi puolikasta yhteen.
Joten haluan saada itselleni lisﾃ､tilaa, mutta, jﾃ､lleen, minﾃ､
saattaa kﾃ､yttﾃ､ﾃ､, ettﾃ､ vapaata tilaa ylﾃｶs.
Mutta aiomme pitﾃ､ﾃ､ se yksinkertainen visuaalisesti.
Saanen sulautuvat nyt 1, ja sitten 3, ja sitten 5, ja sitten 7.
Mikﾃ､ jﾃ､ttﾃ､ﾃ､ minua nyt oikeus puolet alkuperﾃ､isestﾃ､ ongelmasta
joka on tﾃ､ydellisesti lajitellaan.
>> Niin mitﾃ､ jﾃ､ﾃ､ jﾃ､ljelle?
Tunnen pitﾃ､ﾃ､ sanoa samat asiat uudestaan, ja uudestaan,
mutta se kuvastaa Se, ettﾃ､ kﾃ､ytﾃ､mme rekursion.
Prosessi kﾃ､yttﾃ､ﾃ､ algoritmi uudestaan, ja uudestaan,
pienempiin osajoukot alkuperﾃ､iseen ongelmaan.
Joten minulla on nyt vasemmalle lajiteltu puolet alkuperﾃ､isestﾃ､ ongelmasta.
Minulla on oikeus lajitellut puoli alkuperﾃ､isen ongelman.
Mikﾃ､ on kolmas ja viimeinen vaihe?
Voi, se on sulautuvat.
Joten tehdﾃ､.
Katsotaanpa jakaa joitakin uusia muisti, mutta luoja, me
voisi laittaa sen minne nyt.
Meillﾃ､ on niin paljon tilaa meille, mutta me pitﾃ､ﾃ､ se yksinkertainen.
Sijaan menee takaisin ja esiin ja alkuperﾃ､istﾃ､ muistia,
Haluan vain tehdﾃ､ se visuaalisesti tﾃ､ﾃ､llﾃ､ alla,
loppuun asti sulautuvien vasen puoli ja oikea puoli.
>> Joten yhdistﾃ､mﾃ､llﾃ､, mitﾃ､ minun pitﾃ､ﾃ､ tehdﾃ､?
Haluan ottaa elementtejﾃ､ jﾃ､rjestyksessﾃ､.
Joten etsit vasen puoli, Nﾃ､en ensimmﾃ､inen numero on 2.
Katson oikea puoli, Nﾃ､en ensimmﾃ､inen numero
on 1, niin ilmeisesti joka numero Haluanko nyppiﾃ､ pois,
ja laittaa ensimmﾃ､inen minun lopullisen luettelon?
Tietenkin, 1.
Nyt haluan kysyﾃ､ saman kysymyksen.
Vasemmalla puolella, olen silti saanut numero 2.
Oikealla puoliskolla, Minulla numero 3.
Kumpi minﾃ､ haluan valita?
Tietenkin, numero 2 ja nyt huomaa ehdokkaat
4 vasemmalla, 3 oikealla.
Katsotaanpa, tietenkin, valitse 3.
Nyt ehdokkaat ovat 4 vasemmalla, 5 oikealla.
Me tietenkin valita 4.
6 vasemmalla, 5 oikealla.
Me tietenkin valita 5.
6 vasemmalla, 7 oikealla.
Valitsemme 6, ja sitten me valita 7, ja sitten pﾃ､ﾃ､tﾃ､mme 8.
Voila.
>> Joten valtava mﾃ､ﾃ､rﾃ､ sanoja myﾃｶhemmin, me ovat lajiteltu tﾃ､mﾃ､ lista kahdeksan toiminnallisuutta
listaan 窶銀及hden kautta kahdeksan, joka on kasvaa jokaisessa vaiheessa,
mutta kuinka paljon aikaa ja teki se vie meidﾃ､t siihen.
No Olen tarkoituksella laid asioita kuvallisesti
tﾃ､ﾃ､llﾃ､, jotta voimme tavallaan nﾃ､hdﾃ､ tai arvostaa divisioona
valloittavat ettﾃ､ on tapahtunut.
>> Todellakin jos muistella vanavedessﾃ､, Olen jﾃ､ttﾃ､nyt kaikki nﾃ､mﾃ､ pisteviivoilla
paikallaan haltijoille, voit, sellainen, katso, pﾃ､invastaisessa jﾃ､rjestyksessﾃ､,
jos sellainen muistella historia nyt, minun alkuperﾃ､inen lista
on, tietenkin, koon 8.
Ja sitten aikaisemmin, olin kﾃ､sittelevﾃ､t kaksi luetteloa koko 4,
ja sitten neljﾃ､ luettelot koko 2, ja sitten kahdeksan luettelot koko 1.
>> Mitﾃ､ tﾃ､mﾃ､, sellainen, muistuttaa teitﾃ､?
Hyvin, itse asiassa, mitﾃ､ tahansa algoritmit olemme
Katsoin toistaiseksi jossa jakaa, ja jakaa, ja jakaa,
pitﾃ､ﾃ､ ottaa asioita uudelleen, ja jﾃ､lleen, johtaa tﾃ､mﾃ､ yleinen ajatus.
Ja niin siellﾃ､ on jotain logaritminen tekeillﾃ､.
Ja se ei ole aivan loki n, mutta siellﾃ､ on logaritminen komponentti
mitﾃ､ olemme juuri tehneet.
>> Nyt pohtia, miten se todella on.
Joten log n, taas oli suuri kﾃ､yntiaika,
kun teimme jotain binﾃ､ﾃ､rihakupuu, kuten me nyt kutsumme sitﾃ､,
hajota ja hallitse strategia jonka kautta lﾃｶysimme Mike Smith.
Nyt teknisesti.
Se on log pohja 2 n, jopa vaikka useimmissa matematiikka luokissa,
10 on yleensﾃ､ pohja ettﾃ､ oletat.
Mutta tietotekniikan tutkijoita lﾃ､hes aina ajatella ja puhutaan pohja 2,
joten me yleensﾃ､ vain sanoa loki n, sen sijaan, ettﾃ､ tukin pohjaan 2 n,
mutta ne ovat tﾃ､smﾃ､lleen yksi ja Sama maailmassa tietokone
tiede, ja syrjﾃ､ﾃ､n, on jatkuva tekijﾃ､
Ero nﾃ､iden kahden vﾃ､lillﾃ､, joten se on kiistanalainen joka tapauksessa, enemmﾃ､n muodollista syistﾃ､.
>> Mutta nyt, mitﾃ､ me vﾃ､litﾃ､mme Tietoja on tﾃ､ssﾃ､ esimerkissﾃ､.
Joten ei osoittaa esimerkkiﾃ､, mutta Ainakin kﾃ､yttﾃ､ﾃ､ esimerkiksi numeroita
kﾃ､sillﾃ､ jﾃ､rki tarkistaa, jos haluatte.
Joten aiemmin kaava oli log pohja 2 n, mutta mikﾃ､ on n tﾃ､ssﾃ､ asiassa.
Minulla oli n alkuperﾃ､inen numeroita tai 8 Alkuperﾃ､isen numero erityisesti.
Nyt se on ollut hieman vaikka, mutta olen melko
Varmista, ettﾃ､ log pohja 2 arvo 8 on 3,
ja todellakin, mitﾃ､ kiva siitﾃ､ on ettﾃ､ 3 on juuri monta kertaa
ettﾃ､ voit jakaa lista pituuden 8 uudestaan, ja uudestaan,
ja uudelleen, kunnes olet jﾃ､ﾃ､nyt luettelot vain koko 1.
Oikea?
8 menee 4, menee 2, menee 1, ja se on
heijastava nimenomaan kyseisen kuva meillﾃ､ oli vain hetki sitten.
Niin vﾃ､hﾃ､n jﾃ､rki tarkistaa, missﾃ､ logaritmi on todella mukana.
>> Joten nyt, mitﾃ､ muuta on mukana tﾃ､ssﾃ､? n.
Niin huomaa, ettﾃ､ jokainen kerta kun jakaa luettelon,
vaikkakin kﾃ､ﾃ､nteisessﾃ､ jﾃ､rjestyksessﾃ､ historiassa tﾃ､ﾃ､llﾃ､, olin vielﾃ､ tekemﾃ､ssﾃ､ n asioita.
Ettﾃ､ sulautuvan vaihe edellytti, ettﾃ､ Kosketan jokainen numeroita,
jotta tyﾃｶnnﾃ､ se sen sopivaan paikkaan.
Joten vaikka korkeus tﾃ､mﾃ､n kaavio on koko lokin n n tai 3,
Erityisesti, toisin sanoen, Tein kolme divisioonaa tﾃ､ﾃ､llﾃ､.
Kuinka paljon tyﾃｶtﾃ､ minﾃ､ tein vaakasuunnassa pitkin tﾃ､mﾃ､ kaavio joka kerta?
>> No, tein n vaiheet tyﾃｶtﾃ､, koska jos olen
sai neljﾃ､ elementit ja neljﾃ､ elementtiﾃ､, ja minun tﾃ､ytyy yhdistﾃ､ﾃ､ ne yhteen.
Minun tﾃ､ytyy mennﾃ､ lﾃ､pi nﾃ､mﾃ､ neljﾃ､ ja nﾃ､mﾃ､ neljﾃ､,
lopulta yhdistﾃ､ﾃ､ ne takaisin kahdeksan elementtejﾃ､.
Jos pﾃ､invastoin Minulla kahdeksan sormea tﾃ､nne, jota en ole, ja kahdeksan
fingers-- sorry--, jos olen sai neljﾃ､ sormea 窶銀逆ﾃ､nne,
jota en, neljﾃ､ sormea tﾃ､nne, jota en,
niin se sama Esimerkiksi kuten ennenkin, jos en
on kahdeksan sormea 窶銀久aikka yhteensﾃ､, jota voin, sellainen, do.
Voin tarkalleen tehdﾃ､ tﾃ､ﾃ､llﾃ､, Sitten voin varmasti
yhdistﾃ､ﾃ､ kaikki nﾃ､mﾃ､ luettelot on koko 1 yhdessﾃ､.
Mutta en todellakaan tarvitse katsoa kunkin alkion tasan kerran.
Joten korkeus tﾃ､mﾃ､ prosessi on loki n, leveys tﾃ､mﾃ､n prosessin, niin sanoakseni,
on n, niin mitﾃ､ me nﾃ､ytﾃ､mme on, lopulta, on
ajoaika koko n kertaa log n.
>> Toisin sanoen, jaoimme lista, log n kertaa,
mutta joka kerta teimme ettﾃ､ meillﾃ､ oli koskettaa jokainen elementtien
jotta yhdistﾃ､ﾃ､ ne kaikki yhdessﾃ､, jotka
oli n kappaletta askel, joten meillﾃ､ on n kertaa log n, tai tietojenkﾃ､sittelytieteessﾃ､ sanoisi,
asymptoottisesti, joka olisi iso sana
kuvaamaan ylempﾃ､ﾃ､n sidottu aika,
meillﾃ､ on kﾃ､ynnissﾃ､ iso O log n aikaa, niin sanoakseni.
>> Nyt tﾃ､mﾃ､ on merkittﾃ､vﾃ､, koska muistaa, mitﾃ､ kﾃ､ynnissﾃ､ ajat olivat
kupla lajitella, ja valinta lajitella, ja lisﾃ､yslajittelun,
ja jopa muutamia muita olemassa, n potenssiin oli kun olimme.
Ja voit, tavallaan, katso tﾃ､ﾃ､llﾃ､.
Jos n potenssiin on selvﾃ､sti n kertaa n, mutta tﾃ､ﾃ､llﾃ､ meillﾃ､ on n kertaa log n,
ja tiedﾃ､mme jo viikko nolla, ettﾃ､ log n, logaritminen,
on parempi kuin jotain lineaarinen.
Onhan muistaa kuva kanssa punainen ja keltainen
ja vihreﾃ､t viivat ettﾃ､ me kiinnitti, vihreﾃ､ logaritminen linja oli paljon pienempi.
Ja siksi, paljon paremmin ja nopeammin kuin suora keltainen ja punainen linjat,
n kertaa log n on todellakin parempi kuin n kertaa n, tai n neliﾃｶ.
>> Joten meillﾃ､ nﾃ､yttﾃ､ﾃ､ tunnistettu algoritmi yhdistﾃ､misen
lajitella, joka toimii paljon lyhyemmﾃ､n ajan, ja todellakin,
siksi, aiemmin tﾃ､llﾃ､ viikolla, kun nﾃ､imme ettﾃ､ kilpailun vﾃ､lillﾃ､ kupla
lajitella, valinta lajitella, ja yhdistﾃ､ﾃ､ lajitella, yhdistﾃ､minen lajitella todella, todella voitti.
Ja todellakin, emme edes odota varten kuplalajittelu ja valinta lajitella
saada valmiiksi.
>> Nyt ottaa yksi muu syﾃｶttﾃｶ tﾃ､ssﾃ､, mistﾃ､ hieman
muodollinen nﾃ､kﾃｶkulmasta, vain tapauksessa tﾃ､mﾃ､ resonoi paremmin
kuin tﾃ､mﾃ､n korkeamman tason keskustelu.
Joten tﾃ､ssﾃ､ on algoritmi uudelleen.
Katsotaanpa kysyﾃ､ itseltﾃ､mme, mitﾃ､ kﾃ､yntiaika
on tﾃ､mﾃ､n algoritmit eri vaiheet?
Katsotaanpa se jaetaan ensimmﾃ､iseen tapaus ja toisessa tapauksessa.
IF ja muu IF tapauksessa, Jos N on pienempi kuin 2, palaa.
Tuntuu vakio aikaa.
Se on, tavallaan, kuten kahdessa vaiheessa, Jos n on pienempi kuin 2, palaa sitten.
Mutta kuten sanoi maanantaina, vakio aikaa, tai Big O 1,
voi olla kahdessa vaiheessa, kolme vaiheet, jopa 1000 askelta.
Tﾃ､rkeintﾃ､ on, ettﾃ､ se on jatkuva useita vaiheita.
Joten keltainen korostettu pseudokoodina tﾃ､ﾃ､llﾃ､ toimii, me kutsumme sitﾃ､,
vakio aikaa.
Joten enemmﾃ､n virallisesti, ja aiomme to-- tﾃ､mﾃ､
on se, missﾃ､ mﾃ､ﾃ､rin me virallistaa tﾃ､mﾃ､n oikeuden now-- T n,
ajoaika ongelma joka vie n somethings syﾃｶtteenﾃ､
Yhtﾃ､ suuri O yhden, Jos n on pienempi kuin 2.
Joten on edellytyksenﾃ､, ettﾃ､.
Joten olla selkeﾃ､, jos n on pienempi kuin 2, meillﾃ､ on hyvin lyhyt lista, sitten
ajoaika, T, n, missﾃ､ n on 1 tai 0, tﾃ､ssﾃ､ hyvin erityinen tapaus,
se vain tulee olemaan vakio aikaa.
Se tulee ottaa yksi vaihe, kaksi vaihetta riippumatta.
Se on kiinteﾃ､ useita vaiheita.
>> Niin mehukas osa on varmasti vuonna Toisessa tapauksessa vuonna pseudokoodina.
ELSE tapaus.
Lajittele vasemmalla puolella elementtejﾃ､, lajitella oikea puolet elementtejﾃ､, yhdistﾃ､ﾃ､ lajiteltu puolikkaat.
Kuinka kauan kukin nﾃ､istﾃ､ askeleensa?
No, jos kﾃ､ynnissﾃ､ aika lajitella n elementtiﾃ､
on, kutsukaamme sitﾃ､ hyvin yleisesti, T, n,
sitten lajittelu vasen puolet elementit
on, tavallaan, kuin sanoisi, T n jaettuna 2,
ja samoin lajittelu oikea puoli elementtejﾃ､ on, sellainen, kuin sanoisi,
T n jaettu 2, ja sitten yhdistﾃ､mﾃ､llﾃ､ lajiteltu puolikkaat.
No jos minulla joitakin alkioiden lukumﾃ､ﾃ､rﾃ､ tﾃ､ﾃ､llﾃ､,
kuten neljﾃ､, ja jotkut numero elementtejﾃ､ tﾃ､ﾃ､llﾃ､, kuten neljﾃ､,
ja minun tﾃ､ytyy yhdistﾃ､ﾃ､ kuhunkin neljﾃ､ﾃ､n vuonna, ja jokainen nﾃ､istﾃ､ neljﾃ､, yksi
toisensa jﾃ､lkeen siten, ettﾃ､ lopulta minulla on kahdeksan elementtejﾃ､.
Tuntuu, ettﾃ､ on iso o n vaiheet?
Jos Minulla n sormien ja kukin ne on tarkoitus sisﾃ､llyttﾃ､ﾃ､ paikalleen,
se on kuin toinen n vaiheet.
>> Joten todellakin formulaically, Voimme ilmaista tﾃ､mﾃ､n,
vaikkakin hieman pelottavan aluksi silmﾃ､yksellﾃ､, mutta se on jotain
ettﾃ､ kaappaa juuri tﾃ､tﾃ､ logiikkaa.
Juokseva aika, T, n, jos n on suurempi tai yhtﾃ､ suuri kuin 2.
Tﾃ､ssﾃ､ tapauksessa, MUUTEN tapauksessa on T n jaettuna 2, sekﾃ､ T N jaettuna 2,
plus Big O n, jotkut lineaarinen useita vaiheita,
ehkﾃ､ tﾃ､smﾃ､lleen n, ehkﾃ､ 2 kertaa n, mutta se on karkeasti, jotta n.
Niin ettﾃ､ myﾃｶs, miten voimme ilmaista tﾃ､mﾃ､ formulaically.
Nyt et tiedﾃ､ tﾃ､tﾃ､, ellei olet tallentanut sen mielessﾃ､si,
tai etsiﾃ､ se takana oppikirja, joka
saattaa olla hieman huijata arkki lopussa,
mutta tﾃ､mﾃ､ on todellakin menossa antaa meille iso O n log n,
koska toistumisen ettﾃ､ nﾃ､ette tﾃ､ﾃ､llﾃ､ ruudulla,
jos todella teki sen ulos, kanssa ﾃ､ﾃ､retﾃｶn mﾃ､ﾃ､rﾃ､ esimerkkejﾃ､,
tai teit sen formulaically, olisit nﾃ､hdﾃ､, ettﾃ､ tﾃ､mﾃ､, koska tﾃ､mﾃ､ kaava
itsessﾃ､ﾃ､n on rekursiivinen, jossa t n yli jotain oikealla,
ja t N yli vasemmalla, tﾃ､mﾃ､ voi todella ilmaistava, lopulta,
niin suuri irti n log n.
Jos ei vakuuttunut, ettﾃ､ on hieno nyt, vain
ottaa uskossa, ettﾃ､ se on todellakin, mitﾃ､ se toistuminen johtaa,
mutta tﾃ､mﾃ､ on vain hieman enemmﾃ､n matemaattinen lﾃ､hestymistapa nﾃ､kﾃｶinen
klo ajoaika yhdistﾃ､misen sort perustuvat sen pseudokoodilla yksin.
>> Nyt kestﾃ､ﾃ､ vﾃ､hﾃ､n hengﾃ､hdystauon kaiken tﾃ､mﾃ､n,
ja katsomaan tiettyjﾃ､ entinen senaattori, joka
saattaa nﾃ､yttﾃ､ﾃ､ hieman tuttu, joka istui Googlen Eric
Schmidt, jokin aika sitten, haastatteluun lavalla, edessﾃ､ koko joukko
ihmiset, puhuvat lopulta noin aihe, joka on aika nyt tuttu.
Katsotaanpa katsomaan.
>> Eric Schmidt: Nyt senaattori, olet tﾃ､ﾃ､llﾃ､ Googlessa,
ja haluan ajatella puheenjohtajuudesta tyﾃｶhaastattelu.
Nyt on vaikea saada tyﾃｶtﾃ､ presidenttinﾃ､.
Presidentti Obama: Oikea.
Eric Schmidt: Ja olet aikoo tehdﾃ､ [kuulumattomiin] nyt.
On myﾃｶs vaikea saada tyﾃｶtﾃ､ Google.
Presidentti Obama: Oikea.
>> Eric Schmidt: Meillﾃ､ on kysymyksiﾃ､, ja pyydﾃ､mme ehdokkaita kysymyksiﾃ､,
ja tﾃ､mﾃ､ yksi on Larry Schwimmer.
>> Presidentti Obama: OK.
>> Eric Schmidt: Mitﾃ､?
Te ajatella olen tosissasi?
Se on tﾃ､ﾃ､llﾃ､.
Mikﾃ､ on tehokkain tapa lajitella miljoona 32 bittisiﾃ､ kokonaislukuja?
>> Presidentti Obama: Well--
Eric Schmidt: Joskus ehkﾃ､ olen pahoillani, maybe--
Presidentti Obama: Ei, ei, ei, ei, ei, minﾃ､ think--
Eric Schmidt: Se ei ole it--
Presidentti Obama: I ajatella, mielestﾃ､ni kupla
lajitella olisi vﾃ､ﾃ､rﾃ､ tapa edetﾃ､.
Eric Schmidt: Tule.
Jotka kertoivat hﾃ､nelle tﾃ､mﾃ､n?
OK.
En tietojenkﾃ､sittelytieteen on--
>> Presidentti Obama: Olemme saimme vakoojia siellﾃ､.
PROFESSORI: Selvﾃ､.
Jﾃ､tetﾃ､ﾃ､n taaksemme nyt teoreettinen maailma algoritmien
vuonna asymptoottinen analyysi sen, ja palata joitakin aiheita
viikosta nolla ja yksi, ja alku poistaa joitakin apupyﾃｶrﾃ､t,
jos haluatte.
Niin ettﾃ､ te todella ymmﾃ､rtﾃ､ﾃ､ lopulta maasta ylﾃｶs, mitﾃ､
meneillﾃ､ﾃ､n alla huppu, kun kirjoittaa, kﾃ､ﾃ､ntﾃ､ﾃ､, ja suorittaa ohjelmia.
Recall erityisesti, ettﾃ､ tﾃ､mﾃ､ oli ensimmﾃ､inen C-ohjelma me katsoimme,
Canonical, yksinkertainen ohjelma tapaisena suhteellisesti
jolloin se tulostaa, Hello World.
Ja muistaa, ettﾃ､ minﾃ､ sanoin, prosessi ettﾃ､ lﾃ､hdekoodi menee lﾃ､pi
on juuri tﾃ､mﾃ､.
Otat lﾃ､hdekoodia, siirtﾃ､ﾃ､ se lﾃ､pi kﾃ､ﾃ､ntﾃ､jﾃ､, kuten kalahtaa,
ja ulos tulee kohdekoodin, ettﾃ､ voisi nﾃ､yttﾃ､ﾃ､ tﾃ､ltﾃ､, nollia ja ykkﾃｶsiﾃ､
ettﾃ､ tietokoneen prosessoria, keskeinen kﾃ､sittely-yksikﾃｶn tai aivoissa,
lopulta ymmﾃ､rtﾃ､ﾃ､.
>> On kﾃ､ynyt ilmi, ettﾃ､ se on vﾃ､hﾃ､n yksinkertaistamista,
ettﾃ､ olemme nyt kanta kiusanhenki toisistaan
ymmﾃ､rtﾃ､ﾃ､, mitﾃ､ on todella ollut meneillﾃ､ﾃ､n alla huppu
aina kﾃ､yttﾃ､ﾃ､ Sointi, tai yleisemmin,
aina kun teet ohjelmaa, kﾃ､yttﾃ､mﾃ､llﾃ､ Tee ja CF 50 IDE.
Erityisesti tavaraa kuten tﾃ､mﾃ､ on ensin luotu,
kun ensin kﾃ､ﾃ､ntﾃ､ﾃ､ ohjelma.
Toisin sanoen, kun ota lﾃ､hdekoodi
ja kﾃ､ﾃ､ntﾃ､ﾃ､ se, mikﾃ､ on ensimmﾃ､inen on ulostulevien kalahtaa
on jotain tunnetaan kokoonpano koodi.
Ja itse asiassa se nﾃ､yttﾃ､ﾃ､ tﾃ､smﾃ､lleen samalta kuin tﾃ､mﾃ､.
>> Juoksin komento komentoriviltﾃ､ aikaisemmin.
Kalahtaa viiva pﾃ､ﾃ､oma s hello.c, ja tﾃ､mﾃ､ loi tiedosto
minulle kutsutaan hello.s, jonka sisﾃ､llﾃ､ olivat tﾃ､smﾃ､lleen
nﾃ､itﾃ､ pitoisuuksia, ja hieman enemmﾃ､n ylﾃ､puolella ja hieman alle,
mutta olen koonnut juiciest tietoa tﾃ､ﾃ､ltﾃ､ ruudulla.
Ja jos katsot tarkkaan, nﾃ､et ainakin muutamia tuttuja avainsanoja.
Olemme tﾃ､rkein ylhﾃ､ﾃ､llﾃ､.
Olemme printf alas keskellﾃ､.
Ja meillﾃ､ on myﾃｶs Hello World kenoviiva n lainausmerkkeihin alhaalla.
>> Ja kaikki muu tﾃ､ﾃ､llﾃ､ on hyvin alhainen ohjeet
ettﾃ､ tietokoneen prosessoria ymmﾃ､rtﾃ､ﾃ､.
CPU ohjeet, jotka liikkuvat muisti ympﾃ､ri, jonka painon jouset muistista,
ja lopulta, tulostaa asiat nﾃ､ytﾃｶltﾃ､.
Nyt mitﾃ､ tapahtuu vaikka jﾃ､lkeen tﾃ､mﾃ､ kokoonpano koodi luodaan?
Lopulta teet, todellakin, silti tuottaa kohdekoodilla.
Mutta toimenpiteet, jotka ovat todella jatkunut alla huppu
nﾃ､yttﾃ､ﾃ､ hieman enemmﾃ､n kuin tﾃ､mﾃ､.
Lﾃ､hdekoodi tulee kokoonpano koodi, joka sitten tulee kohdekoodin,
ja operatiiviset sanat tﾃ､ssﾃ､ on ettﾃ､, kun kﾃ､ﾃ､nnﾃ､t lﾃ､hdekoodin,
ulos tulee kokoonpano koodi, ja sitten kun Kokoa kokoonpano koodi,
ulos tulee kohdekoodilla.
>> Nyt kalahtaa on erittﾃ､in hienostunut, kuten paljon kerﾃ､ﾃ､jiﾃ､,
ja se tekee kaikki nﾃ､mﾃ､ vaiheet yhdessﾃ､, ja se ei vﾃ､lttﾃ､mﾃ､ttﾃ､
ulostulo vﾃ､livaiheen tiedostoja, jotka voit jopa nﾃ､hdﾃ､.
Se vain kokoaa asioita, joka on yleinen termi, joka
kuvaa tﾃ､tﾃ､ koko prosessia.
Mutta jos todella haluat olla erityisesti siellﾃ､
paljon enemmﾃ､n tekeillﾃ､ myﾃｶs siellﾃ､.
>> Mutta katsotaanpa myﾃｶs katsovat nyt, ettﾃ､ jopa ettﾃ､ super yksinkertainen ohjelma, hello.c,
kutsutaan toimintoa.
Se kutsutaan printf.
Mutta en kirjoita printf, todellakin, mukana C, niin sanoakseni.
Se on toiminto muistaa, joka on ilmoitettu standardin io.h, joka
on header-tiedosto, joka on aihe me oikeastaan
sukeltaa perusteellisemmin ennen pitkﾃ､ﾃ､.
Mutta otsikkotiedosto on tyypillisesti mukana
koodilla tiedoston, lﾃ､hdekooditiedostoa, joten paljon kuin on olemassa standardi io.h.
>> Joskus sitten, joku, tai jonkun, myﾃｶs kirjoitti
tiedosto nimeltﾃ､ standardi io.c, vuonna jonka todellinen mﾃ､ﾃ､ritelmﾃ､t,
tai toteutukset printf, ja rypﾃ､leterttuja muita toimintoja,
todella kirjoitettu.
Niin sillﾃ､, jos me harkita tﾃ､ﾃ､llﾃ､ vasemmalla, hello.c, ettﾃ､ kun
koottu, antaa meille hello.s, vaikka Kalahtaa ei vaivaudu sﾃ､ﾃ､stﾃｶ paikka
voimme nﾃ､hdﾃ､ sen, ja ettﾃ､ assembly saa kootaan hello.o, joka
on todellakin oletusnimi annetaan aina kﾃ､ﾃ､nnﾃ､t lﾃ､hde
koodi kohdekoodi, mutta eivﾃ､t aivan valmis suorittamaan sitﾃ､ vielﾃ､,
koska toinen vaihe pitﾃ､ﾃ､ tapahtua, ja on
on tapahtunut muutaman viime viikkoa, ehkﾃ､ tietﾃ､mﾃ､ttﾃ､ﾃ､n sinua.
>> Erityisesti jonnekin vuonna CS50 IDE, ja tﾃ､mﾃ､,
Myﾃｶs, on vﾃ､hﾃ､n yksinkertaistava hetkeksi,
siellﾃ､ on, tai oli upon a time, tiedosto nimeltﾃ､ standardi io.c,
ettﾃ､ joku kﾃ､ﾃ､nnetty standardi io.s tai vastaava,
ettﾃ､ joku sitten koottu standardiin io.o,
tai se kﾃ､ﾃ､ntyy ulos hieman erilainen tiedosto
muodossa, joka voi olla erilainen tiedostopﾃ､ﾃ､te kokonaan,
mutta teoriassa ja kﾃ､sitteellisesti, tﾃ､smﾃ､lleen nﾃ､mﾃ､ toimenpiteet tﾃ､ytyi tapahtua jossain muodossa.
Joka on sanoa, ettﾃ､ nyt kun olen kirjallisesti ohjelma,
hello.c, ettﾃ､ vain sanoo, Hello World, ja olen kﾃ､yttﾃ､en jonkun toisen koodi
kuten printf, joka oli aikoinaan pﾃ､ﾃ､llﾃ､ aika, tiedostossa nimeltﾃ､ standardi io.c,
sitten jotenkin minun on otettava minun kohdekoodi, minun nollia ja ykkﾃｶsiﾃ､,
ja ettﾃ､ henkilﾃｶn esine koodi tai nollia ja ykkﾃｶsiﾃ､,
ja jotenkin yhdistﾃ､ﾃ､ ne yksi lopullinen tiedosto, nimeltﾃ､ﾃ､n Hei, ettﾃ､
on kaikki nollia ja niistﾃ､ minun pﾃ､ﾃ､tehtﾃ､vﾃ､,
ja kaikki nollia ja ne, printf.
>> Ja todellakin, ettﾃ､ viime prosessi on nimeltﾃ､ﾃ､n, liitﾃ､t kohdekoodilla.
Jonka lﾃ､htﾃｶ on suoritettava tiedosto.
Joten tasapuolisuuden on pﾃ､ivﾃ､n pﾃ､ﾃ､tteeksi, ei mitﾃ､ﾃ､n
on muuttunut viikolla yksi, kun aloitti kokoamiseen ohjelmia.
Itse asiassa tﾃ､mﾃ､ kaikki on ollut tapahtuu alla huppu,
mutta nyt olemme asemassa jossa voimme todella
tease lisﾃ､ksi nﾃ､mﾃ､ eri vaiheet.
Ja itse asiassa lopussa pﾃ､ivﾃ､, olemme yhﾃ､
jﾃ､ﾃ､ nollia ja ykkﾃｶsiﾃ､, joka on todella suuri segue nyt
Toinen ominaisuus C, ettﾃ､ olemme ole tarvinnut hyﾃｶdyntﾃ､ﾃ､ todennﾃ､kﾃｶisesti
Tﾃ､hﾃ､n mennessﾃ､ tunnetaan bittioperaatioiden.
Toisin sanoen, toistaiseksi, milloin olemme Puhuttiin tietojen C tai muuttujiin C,
meillﾃ､ on ollut asioita, kuten merkkiﾃ､ ja kellukkeet ja laajennukset
ja pitkﾃ､t ja kaksinkertaistuu ja vastaavat, mutta kaikki nﾃ､mﾃ､ ovat vﾃ､hintﾃ､ﾃ､n kahdeksan bittiﾃ､.
Emme ole koskaan vielﾃ､ ole voinut manipuloida yksittﾃ､isiﾃ､ bittejﾃ､,
vaikka yksittﾃ､isen vﾃ､hﾃ､n, me tietﾃ､ﾃ､, voi edustaa 0 ja 1.
Nyt nﾃ､yttﾃ､ﾃ､ siltﾃ､, 窶銀菊ttﾃ､ C, sinua voi pﾃ､ﾃ､stﾃ､ kﾃ､siksi yksittﾃ､isiﾃ､ bittejﾃ､,
jos tiedﾃ､t syntaksin, jolla saada niitﾃ､.
>> Joten katsomaan klo bittioperaatioiden.
Joten Kuvassa on muutamia symboleja, olemme, tavallaan, tavallaan, ennen nﾃ､hty.
Nﾃ､en et-merkki, pystysuora baari, ja jotkut muut samoin,
ja muistuttavat, ettﾃ､ et-merkki et-merkki on jotain olemme nﾃ､hneet aiemmin.
Looginen AND-operaattori, jossa sinulla on kaksi niistﾃ､ yhdessﾃ､ tai looginen TAI
operaattori, jossa on kaksi pystypalkkia.
Bittioperaatioiden, joka kﾃ､ymme katso toimivat bittiﾃ､ erikseen,
vain kﾃ､yttﾃ､ﾃ､ yksi et-merkki, yksi pystysuora palkki, sirkumfleksi symboli
tulee seuraavaksi, pieni tilde, ja sitten vasemmalle
kannatin vasen kannatin, tai oikea kannatin oikea kiinnike.
Kukin nﾃ､istﾃ､ on eri merkitykset.
>> Itse asiassa, nyt katsomaan.
Mennﾃ､ﾃ､n vanhan koulun tﾃ､nﾃ､ﾃ､n, ja kﾃ､yttﾃｶ kosketusnﾃ､yttﾃｶ menneiden,
tunnetaan valkoinen levy.
Ja tﾃ､mﾃ､ valkoinen lauta aikoo antaa meille
ilmaista joitakin melko yksinkertaisia 窶銀虐ymboleita, tai pikemminkin joitakin melko yksinkertaisia 窶銀橘aavoja,
ettﾃ､ voimme lopulta vipuvaikutus, jotta
pﾃ､ﾃ､syn yksittﾃ､isiﾃ､ bittiﾃ､ C-ohjelma.
Toisin sanoen, tehdﾃ､ﾃ､n tﾃ､mﾃ､.
Katsotaanpa ensin puhua varten hetki et-merkki,
joka on peiton ja Operaattori.
Toisin sanoen, tﾃ､mﾃ､ on operaattori, jonka avulla
minulle on vasen muuttuja tyypillisesti, ja oikea muuttuja,
tai yksittﾃ､inen arvo, ettﾃ､ jos me ja ne yhteen, antaa minulle lopputulokseen.
Joten mitﾃ､ minﾃ､ tarkoitan?
Jos ohjelma, sinulla on muuttuva ettﾃ､ tallentaa yhden nﾃ､istﾃ､ arvoista,
tai katsotaanpa pitﾃ､ﾃ､ asiat yksinkertaisina, ja vain kirjoittaa nollia ja ykkﾃｶsiﾃ､ erikseen,
tﾃ､ssﾃ､ miten -merkki operaattori toimii.
0 Ampersand 0 tulee yhtﾃ､ 0.
Nyt Miksi?
>> Se on hyvin samankaltainen Boolen operaattoreilla,
ettﾃ､ olemme keskustelleet tﾃ､hﾃ､n asti.
Jos luulet onhan 0 on vﾃ､ﾃ､rﾃ､, 0 on vﾃ､ﾃ､rﾃ､, vﾃ､ﾃ､rﾃ､ ja vﾃ､ﾃ､riﾃ､
on, kuten olemme keskustelleet loogisesti, myﾃｶs vﾃ､ﾃ､rﾃ､.
Jotta saamme 0 myﾃｶs tﾃ､ﾃ､llﾃ､.
Jos otat 0 ampersand 1, hyvin, ettﾃ､ myﾃｶs
tulee olemaan 0, koska tﾃ､mﾃ､ vasen ilmaisun olevan totta tai 1,
sen pitﾃ､isi olla totta ja totta.
Mutta tﾃ､ssﾃ､ meillﾃ､ on vﾃ､ﾃ､rﾃ､ ja totta, tai 0 ja 1.
Nyt uudelleen, jos meillﾃ､ on 1 ampersand 0, sekin tulee olemaan 0,
ja jos meillﾃ､ on 1 et-merkki 1, Lopuksi meillﾃ､ on 1 bit.
Eli toisin sanoen, me emme tee mitﾃ､ﾃ､n mielenkiintoista tﾃ､mﾃ､n operaattorin
vain vielﾃ､, tﾃ､mﾃ､ Ampersand operaattori.
Se peiton ja Operaattori.
Mutta nﾃ､mﾃ､ ovat ainekset jonka kautta voimme tehdﾃ､
mielenkiintoisia asioita, kuten tulemme pian nﾃ､hdﾃ､.
>> Nyt katsokaamme vain yhden pystyviiva tﾃ､nne oikealla.
Jos minulla on 0 vﾃ､hﾃ､n ja minﾃ､ TAI se, bittivastineen
OR operaattori, toinen 0 bit, joka tulee antamaan minulle 0.
Jos otan 0 vﾃ､hﾃ､n ja OR sen 1 vﾃ､hﾃ､n, niin aion saada 1.
Ja itse asiassa, vain selkeys, anna minun mennﾃ､ takaisin,
niin ettﾃ､ minun pystypalkki ei erehtynyt 1: n.
Saanen uusia koko minun 1 on hieman enemmﾃ､n
selvﾃ､sti, jotta voimme ensi nﾃ､hdﾃ､, jos en on 1 tai 0, joka tulee olemaan 1,
ja jos minulla on 1 tai 1 ettﾃ､, Myﾃｶs tulee olemaan 1.
Voit siis nﾃ､hdﾃ､ loogisesti ettﾃ､ TAI operaattori kﾃ､yttﾃ､ytyy hyvin eri tavalla.
Tﾃ､mﾃ､ antaa minulle 0 tai 0 antaa minulle 0, mutta joka toinen yhdistelmﾃ､ antaa minulle 1.
Niin kauan kuin minulla on yksi 1 kaava, tulos tulee olemaan 1.
>> Toisin JA operaattori, et-merkki,
vain jos minulla on kaksi 1: n yhtﾃ､lﾃｶ, voin itse saada 1 ulos.
Nyt on olemassa muutamia muita toimijat samoin.
Yksi niistﾃ､ on hieman enemmﾃ､n mukana.
Joten anna minun mennﾃ､ eteenpﾃ､in ja poistaa tﾃ､mﾃ､ vapauttaa levytilaa.
Ja lﾃ､hdetﾃ､ﾃ､n katsomaan caret symboli, vain hetken.
Tﾃ､mﾃ､ on tyypillisesti merkki voit kirjoittaa
nﾃ､ppﾃ､imistﾃｶn SHIFT ja sitten yksi numerot huipulla oman US
nﾃ､ppﾃ､imistﾃｶ.
>> Joten tﾃ､mﾃ､ on yksinomainen OR operaattori, eksklusiivinen TAI.
Joten me vain nﾃ､imme tai toiminnanharjoittaja.
Tﾃ､mﾃ､ on eksklusiivinen OR operaattori.
Mitﾃ､ oikeastaan 窶銀菊roa?
No katsotaanpa katsokaa kaava, ja kﾃ､yttﾃ､ﾃ､ tﾃ､tﾃ､ ainesosina lopulta.
0 XOR 0.
Aion sanoa on aina 0.
Se mﾃ､ﾃ､ritelmﾃ､ XOR.
0 XOR 1 tulee olemaan 1.
1 XOR 0 tulee olemaan 1, ja 1 XOR 1 tulee olemaan?
Vﾃ､ﾃ､rﾃ､ssﾃ､?
Tai oikea?
Minﾃ､ en tiedﾃ､.
0.
Nyt mitﾃ､ on tekeillﾃ､?
No ajattele Nimi tﾃ､mﾃ､n operaattorin.
Eksklusiivinen OR, jotta nimi, ehdottaa,
vastaus on vain olemaan 1 jos tulot ovat yksin,
yksinomaan eri.
Joten tﾃ､ssﾃ､ tulot ovat sama, joten tuotos on 0.
Tﾃ､ssﾃ､ tulot ovat sama, joten tuotos on 0.
Tﾃ､ssﾃ､ ovat lﾃ､hdﾃｶt ovat erilaisia, ne ovat yksin, ja niin lﾃ､htﾃｶ on 1.
Joten se on hyvin samankaltainen Ja se on hyvin samankaltainen,
tai pikemminkin se on hyvin samankaltainen TAI, mutta vain yksinomainen tavalla.
Tﾃ､mﾃ､ ei ole enﾃ､ﾃ､ 1, koska meillﾃ､ on kaksi 1 n,
ja ei yksinomaan, vain yksi niistﾃ､.
Selvﾃ､.
Entﾃ､ muut?
No tilde puolestaan 窶銀黍n todella mukava ja yksinkertainen, onneksi.
Ja tﾃ､mﾃ､ on unary operaattorin, joka tarkoittaa
se on sovellettu ainoastaan 窶銀及hteen tulo, yksi operandi, niin sanoakseni.
Ei vasemmalle ja oikealle.
Toisin sanoen, jos otat tilde of 0, vastaus on pﾃ､invastainen.
Ja jos otat tilde 1, vastaus tulee olemaan pﾃ､invastainen.
Joten tilde operaattori on tapa tyhjﾃ､ksi hieman,
tai kﾃ､ﾃ､nnetﾃ､ﾃ､n verran 0-1 tai 1-0.
>> Ja ettﾃ､ jﾃ､ttﾃ､ﾃ､ meidﾃ､t vihdoin vain kaksi viimeistﾃ､ toimijoiden,
ns vasemmalla muutos, ja ns oikealla shift operaattori.
Katsotaanpa katsomaan miten nﾃ､mﾃ､ tyﾃｶssﾃ､.
Vasemmalle siirtyminen operaattori, kirjallinen kaksi kulmakiinnikkeet niin,
toimii seuraavasti.
Jos minun panos, tai minun operandi, vasemmalle shift operaattori on yksinkertaisesti 1.
Ja minﾃ､ sitten kertoa tietokoneen vasen shift ettﾃ､ 1, sanovat seitsemﾃ､n paikkoja,
tulos on kuin olisin ottaa tﾃ､mﾃ､n 1, ja siirrﾃ､ se
seitsemﾃ､n paikkoja yli vasemmalle, ja oletuksena,
aiomme olettaa, ettﾃ､ tilaa oikealle
aiotaan nollilla.
Toisin sanoen, 1 vasen muutos 7 on menossa antaa minulle, ettﾃ､ 1, jonka jﾃ､lkeen 1, 2, 3,
4, 5, 6, 7 nollia.
Joten tavallaan, sen avulla voit ottaa pieni mﾃ､ﾃ､rﾃ､ kuten 1,
ja selvﾃ､sti on paljon paljon, paljon suurempi tﾃ､llﾃ､ tavalla,
mutta me todella tulee nﾃ､hdﾃ､ viisaampi lﾃ､hestymistapoja se
sen sijaan, samoin,
>> Selvﾃ､.
Se on siinﾃ､ viikolla kolme.
Tulemme nﾃ､kemﾃ､ﾃ､n ensi kerralla.
Tﾃ､mﾃ､ oli CS50.
>> [Musiikkia]
>> SPEAKER 1: Hﾃ､n oli vﾃ､lipala baari syﾃｶminen kuuma tuhertaa jﾃ､ﾃ､telﾃｶannos.
Hﾃ､nellﾃ､ oli se koko hﾃ､nen kasvonsa.
Hﾃ､n on pﾃ､ﾃ､llﾃ､ﾃ､n, ettﾃ､ suklaa kuten parta
SPEAKER 2: Mitﾃ､ sinﾃ､ teet?
SPEAKER 3: Hmmm?
Mitﾃ､?
>> SPEAKER 2: Oletko juuri double dip?
Voit kaksinkertainen kastetaan siru.
SPEAKER 3: Anteeksi.
SPEAKER 2: Sinﾃ､ kastettu siru, sinﾃ､ otti purra, ja te kastetaan uudelleen.
SPEAKER 3:
SPEAKER 2: Niin, ettﾃ､ kuin laittaisi koko suu aivan dip.
Seuraavan kerran otat siru, vain kasta se kerran, ja lopettaa sen.
>> SPEAKER 3: Tiedﾃ､tkﾃｶ mitﾃ､, Dan?
Voit pulahtaa tavalla haluat pulahtaa.
Minﾃ､ dip tapa, ettﾃ､ haluan notkahdus.