>> [Predvajanja glasbe]
DAVID Malan V redu.
Vse je v redu, dobrodošli nazaj.
Torej, to je 4 teden, začetek Pogodbe, že.
In ti boš spomnil, da je prejšnji teden, smo se kodo namenjen le malo
in smo začeli govoriti malo več na visoki ravni, o stvareh, kot
iskanje in razvrščanje, ki je, čeprav Nekoliko preproste ideje, so
Predstavnik vrsti problemov boste začeli zlasti reševanje
kot ste začeli razmišljati o končni projekti in zanimive rešitve si
morda morali resničnih problemov.
Zdaj mehurček vrste je bil eden od najpreprostejših taki algoritmi, in
delo, ki ga ob teh majhnih številkah na seznamu ali v matrično vrste
mehurček svojo pot do vrha in velike številke premakniti svojo pot navzdol
Konec tega seznama.
>> In opozarjajo, da bi lahko vizualizirati bubble sort malo
kaj takega.
Naj gredo naprej in kliknite Start.
Sem predizbere mehurček vrste.
In če se spomnite, da je višji modra črte predstavljajo velike številke, mala
modre črte predstavljajo majhno število, kot gremo skozi to spet in
spet primerjavo dveh palic drug poleg druga v rdeči barvi, bomo zamenjali
Največji in najmanjši če so v okvari.
>> Tako da bo ta šel naprej in naprej in iti naprej, in videli boste, da večja
Elementi so svojo pot do desno in manjše elementi
ki svojo pot na levo.
Vendar pa smo začeli količinsko učinkovitosti,
Kakovost tega algoritma.
In mi je rekel, da je v najslabšem primeru ta algoritem je
približno koliko korakov?
>> Torej n kvadrat.
In kaj je bilo n?
>> PUBLIKA: Število elementov.
>> DAVID Malan: Tako je n število elementov.
In zato bomo to pogosto.
Vsak čas želimo govoriti o velikosti o problemu ali velikost
vložek, ali koliko časa traja za izdelavo izhod, bova
posplošena karkoli Vhod je, kot n.
Torej nazaj v tednu 0, število strani V telefonskem imeniku je n.
Število študentov V sobi je bil n.
Torej tudi tu bomo po da vzorec.
>> Zdaj n kvadrat ni posebej hitro, zato smo poskušali narediti bolje.
In tako smo si ogledali nekaj drugi algoritmi, med katerimi
so izbor sort.
Torej, izbira sort je malo drugačna.
Bilo je skoraj enostavnejša, upam si reči, s katerim sem začel na začetku
seznam naših prostovoljcev in sem spet in spet in spet šla skozi
Seznam, skubljenje od najmanjše element naenkrat in ga dajanje ali
jo na začetku seznama.
>> Ampak tudi to, ko smo začeli razmišljati s pomočjo matematike in večjo
slika, pomislili kolikokrat Nameraval sem nazaj in naprej in nazaj
in tja, smo rekli v najslabšem primeru, izbira sort, preveč, je bilo kaj?
n kvadrat.
Zdaj v resničnem svetu, bi bilo dejansko nekoliko hitreje.
Ker še enkrat, nisem imel, da nazadovanja, ko sem razporejene
najmanjši elementi.
Ampak, če razmišljamo o zelo velikem n, in Če nekako storiti math kot
Jaz sem na krovu, pri čemer n kvadrat minus nekaj, vse ostalo
poleg n kvadrat, enkrat n postane zelo velik, ne
res toliko pomembno.
Tako kot računalniški znanstveniki, smo nekako zamižijo na eno oko, da manjša
dejavniki in se osredotočiti le na faktor v izraz, ki se dogaja, da
Največja razlika.
>> No, na koncu smo pogledal ob vstavitvi vrste.
In to je bila podobna v duhu, ampak namesto skozi ponavljajočim in
izberite najmanjši element enega na Tokrat sem namesto da bi vzel v roke, da sem
bila obravnavana, in sem se odločil, vse Dobro, ti spadaš sem.
Potem sem se preselil na naslednji element in se odločil, da je on ali
je pripadal tukaj.
In potem sem se preselil naprej in naprej.
In mislim, da bi lahko, na poti, premik te fante, da bi
naredimo prostor za njih.
Tako da je bil neke vrste mentalnega preobrata od izbire vrste, ki smo
imenovano vstavljanja vrste.
>> Torej te teme, da se pojavijo v resničnem svetu.
Še pred nekaj leti, ko nekateri senator je kandidiral za predsednika,
Eric Schmidt je v času uprave Google, dejansko možnost
z njim razgovor.
In smo mislili delili YouTube Posnetek zate, če bi lahko zavihati
volumen.
>> [Predvajanje videa]
>> -Zdaj, senator, da ste tukaj na Googlu, in mi je všeč, da razmišljajo o predsedovanju
kot razgovor za službo.
>> [SMEH]
>> -Zdaj je težko dobiti delo kot predsednik.
In greste skozi mrzlica zdaj.
Prav tako je težko dobiti službo pri Googlu.
Imamo vprašanja in vprašamo Naši kandidati vprašanja.
In to je eden od Larry Schwimmer.
>> [SMEH]
-Mislite, da se hecam?
To je tukaj.
Kaj je najbolj učinkovit način za razvrstite milijon dva-bitnih števil?
>> [SMEH]
>> No, uh -
>> -Oprosti.
Morda bi se morali -
>> -Ne, ne, ne, ne, ne.
>> -To ni -
OK.
>> Mislim, bubble sort bi biti napačna pot.
>> [SMEH]
>> [Vzklikati in aplavz]
>> Daj no, kdo mu je to povedal?
OK.
>> [END predvajanje videa]
>> DAVID Malan: Torej, tam ga imate.
Tako smo začeli količinsko ti teče krat, tako rekoč, z nečim
imenovano asimptotska zapis, ki je se sklicujejo le na naš nekakšen preobrat
slepo oko na tiste manjše dejavnikov in samo gledaš časa teče,
Izvajanje teh algoritmov, kot n postane zelo velik daljšem časovnem obdobju.
In tako smo uvedli veliko O. In Big O predstavlja nekaj, kar smo mislili
od kot zgornja meja.
In dejansko, Barry, lahko znižamo kot mic malo bit?
>> Mi smo se to je zgornja meja.
Tako velik O izmed n kvadratov pomeni, da v najslabšem primeru nekaj podobnega
Izbor vrste bi potrebovali n kvadratov korake.
Ali nekaj takega vstavljanja vrste bi n kvadrat korakov.
Zdaj pa nekaj podobnega vstavljanje sort, kar je bilo v najslabšem primeru?
Glede na to, matrika, kaj je najhujše Možen scenarij, da bi našli
sami soočajo s številnimi partnerji?
>> To je povsem nazaj, kajne?
Ker če je popolnoma nazaj, moraš narediti cel kup dela.
Ker če ste popolnoma nazaj, boste našli
Največji dejavnik tukaj, čeprav spada tja.
Torej boste rekli, v redu, v Ta trenutek v času, spadaš sem,
tako da ga pusti pri miru.
>> Potem se zavedaš, oh, prekleto, moram premaknil nekoliko manjši element za
levo od tebe.
Potem moram storiti, da znova in znova in znova.
In če sem šel naprej in nazaj, si bi nekako občutek uspešnosti
da algoritem, saj nenehno sem shuffling vsem ostalim določa
matrika da bi naredili prostor za to.
Tako da je v najslabšem primeru.
>> Nasprotno -
in to je bil Alpinista zadnji čas -
smo rekli, da je vključitev neke je omega česa?
Kaj je najboljši primer tek Čas vstavljanja vrste?
Torej je dejansko n.
To je bil prazen, da smo zapustili na krovu zadnjič.
>> In to je omega n, ker zakaj?
No, v zelo najboljšem primeru, kaj je vstavljanje sort bodo predali?
No, Seznam, ki je v celoti urejeno že minimalna delo narediti.
Toda kaj je boljšega pri vstavljanja vrste je, da zato, ker Tu se začne in
odloči, oh, ti si številka ena, spadaš sem.
Oh, kakšna sreča.
>> Ti si številka dve.
Prav tako spadajo sem.
Tretjič, še bolje spadaš sem.
Takoj, ko pride do konca psevdokoda Seznam Per vstavitve razvrstite v
da smo šli skozi verbalno zadnji čas, je to storjeno.
Ampak izbira sort, nasprotno, redno počne kaj?
>> Bo ohranil skozi seznam spet in spet in spet.
Ker je bil ključni vpogled le ko ste pogledal vse do
konec seznama, ste lahko prepričani, da je element izbrano
res trenutno najmanjši element.
Torej ti različni modeli duševno konec up prinaša nekaj zelo resničnega sveta
razlike za nas, kot tudi ti teoretične asimptotske razlike.
>> Torej, samo da Rekapitulacija, nato pa velik O n kvadrat, smo videli nekaj tak
Algoritmi tako daleč.
Big O n?
Kaj je algoritem, ki bi lahko je dejal, da je velik O n?
V najslabšem primeru je potrebno linearna več korakov.
>> OK, linearno iskanje.
In v najslabšem primeru, če je element iščeš, ko
uporabi linearno iskanje?
>> OK, v najslabšem primeru, sploh ni tam.
Ali v drugem najslabšem primeru, to je vse poti na koncu, ki je
plus ali minus razlika enem koraku.
Torej, na koncu dneva lahko rečemo, da je linearna.
Big O n bi bilo linearno iskanje, ker v najslabšem primeru
element sploh ni tam ali pa je vse poti na koncu.
>> No, veliki O log n.
Nismo govorili zelo podrobno o to, ampak to smo že videli prej.
Kaj deluje v tako imenovanih logaritemsko Čas, v najslabšem primeru?
>> Ja, tako binarno iskanje.
In binarno iskanje v najslabšem primeru morda element nekje v
srednji ali nekje znotraj polja.
Ampak ti samo zdi, ko vas razdeli seznam na pol, pri
pol, na pol, na pol.
In potem voila, da je tam.
Ali pa še enkrat, v najslabšem primeru, sploh ni tam.
Vendar ne veste, da to ni tam dokler si nekako doseči, da je zadnja
spodaj je večina elementov po prepolovitev in prepolovitev in prepolovili.
>> Big O od 1.
Tako smo lahko velik O višini 2, velik O 3.
Kadarkoli le konstantno število, smo le nekako le poenostaviti
da je velik O 1.
Čeprav če realno, je potrebno 2 ali celo 100 korakov, če je
konstantno število korakov, smo pravkar rekel veliki O od 1.
Kaj je algoritem, ki je v veliki O 1?
>> PUBLIKA: Iskanje dolžino v spremenljivko.
>> DAVID Malan: Iskanje Dolžina spremenljivke?
>> PUBLIKA: Ne, dolžina če je to že urejeno.
>> DAVID Malan: Dobro.
OK, tako da iskanje dolžino nekaj če dolžina tistega nekaj, kot
matrika, ki je shranjena v nekaterih spremenljivko.
Saj lahko samo prebrati spremenljivko ali natisniti spremenljivko, ali
samo na splošno dostop do te spremenljivke.
In voila, da se stalno čas.
>> Nasprotno, mislim nazaj na praske.
Misli nazaj v prvem tednu C kliče samo printf in tiskanje
nekaj, na zaslonu je nedvomno Časovna konstanta, saj traja le
nekateri število CPE prikazati da je besedilo na zaslonu.
Ali pa počakajte - to počne?
Kako drugače bi lahko modelirati uspešnost printf?
Bi kdo rad, da se ne strinjam, da je Mogoče to ni ravno konstanten čas?
V kakšnem smislu bi lahko printf teče čas, pravzaprav tiskanje niz na
zaslon, je nekaj razen konstantna.
>> PUBLIKA: [neslišno].
>> DAVID Malan: Ja.
Torej je odvisno od naše perspektive.
Če smo dejansko razmišljati o vlaganju v printf kot string, in
Zato smo merjenje velikosti, ki Vhod po svoji dolžini - tako recimo
da dolžina n, kot tudi -
verjetno, printf je sam velik O n saj se dogaja, da vas n korakov bo
natisniti vsako od teh n znakov, najverjetneje.
Vsaj do te mere, da prevzame da morda to je z uporabo zanke for
Pod pokrovom.
>> Vendar pa bi morali gledati, da kodo razumeti bolje.
In res, ko vi začnete analizira svoje algoritme, boste
dobesedno ne samo to.
Nekako zrkla svojo kodo, in mislim, O - vse v redu, imam to zanko
tukaj ali imam ugnezdene zanke tukaj da bo storil n stvari n-krat,
in lahko razvrstite razuma svojo pot s kodo, tudi če je
psevdokoda in ne dejanska koda.
>> Torej, kaj pa omega n kvadrat?
Kaj je algoritem, ki v najboljšem primer, še vedno je n kvadrat koraki?
Ja?
>> PUBLIKA: [neslišno].
>> DAVID Malan: Torej, izbira sort.
Ker v tem problemu res zmanjša na dejstvo, da spet ne vem
Našel sem trenutno najmanjši dokler Preveril sem vse darn elemente.
Torej omega, recimo, n smo pravkar prišel gor z eno.
Vstavitev vrste.
Če je seznam zgodi, da je treba sortirati že, v najboljšem primeru imamo samo
da en skozi to, na kateri točki smo prepričani.
Potem, da bi se omenjeni da je linearna, zagotovo.
>> Kaj pa omega od 1?
Katere, v najboljšem primeru, lahko traja nespremenjeno število korakov?
Torej linearno iskanje, če si le srečo in element iščete
je takoj na začetku seznama, če je to, če ste se začne vaše
Linearni prečkanje navedenega seznama.
>> In to velja za število stvari.
Na primer, čeprav binarni Iskanje je omega 1.
Ker kaj pa če dobiš res darn srečo in zadah-DAB v sredini
tvoj array je številka iščete?
Tako da boste lahko srečni tam, kot dobro.
>> Ta je, nenazadnje, omega n log n.
Torej n log n, nismo zares govorimo o še, ampak -
>> PUBLIKA: zlivanjem?
>> DAVID Malan: zlivanjem.
To je bil Alpinista zadnjega časa, kjer smo predlagali, in smo pokazali,
vidno, da so algoritmi.
In združiti vrste samo ena taka algoritem, ki je bistveno hitrejša
kot nekateri od teh drugih fantov.
Dejstvo je, zliti kratki ne le Najboljši primer n log n, v najslabšem
Primer n log n.
In ko imate to naključje omega in velik O počutje isto stvar?
Mi lahko dejansko opiše kot tisto, kar je imenuje theta, čeprav je
Malo manj pogosti.
Ampak to samo pomeni dve meje, V tem primeru so enake.
>> Torej zlivanjem, kaj to Res omejijo na za nas?
No, spomnim motivacijo.
Dovolite mi, dvigni drugo animacijo, da nismo pogled na zadnjem času.
Ta je, enako zamisel, vendar to je malo večji.
In jaz grem naprej in poudariti Prvi - imamo vstavljanja vrste na
zgoraj levo, nato pa izbor sort, bubble sort, nekaj drugih vrst -
lupine in hitro - da se nismo pogovarjali o, in kup in zlivanjem.
>> Torej vsaj poskusiti, da se osredotoči na svoje oči Najboljši trije na levo in nato
zlivanjem ko kliknem ta zelena puščica.
Ampak bom pustil vse od njih teče, samo da bi vam občutek raznolikosti
algoritmi, ki obstajajo na svetu.
Bom pustil ta tek le za nekaj sekund.
In če se osredotočite vaše oči - izberite algoritem, osredotočiti na to, za samo
sekund - boste začeli videvati vzorec, ki ga je izvajati.
>> Merge sort, obvestilo, je končano.
Heap sort, hitro urejanje, lupini -
Tako se zdi, smo uvedli tri Najhujši algoritmi prejšnji teden.
Ampak to je dobro, da smo danes tukaj poglej zlivanjem, ki je eden od
Lažje tisti je, da pogledamo, čeprav čeprav bo verjetno bend svoj um
Samo malo.
Tu lahko vidimo, koliko Izbor vrste zanič.
>> Ampak na flip strani, je zelo preprosto izvajati.
In morda za P Set 3, ki je eden od algoritmi ste se odločili za izvedbo
Za standardni različici.
Popolnoma v redu, popolnoma pravilna.
>> Ampak spet, kot n postane velik, če odločijo za izvajanje hitrejši algoritem
všeč zlivanjem, odds so v večji in Večje vhodi, vaša koda je le
tekoč teči hitreje.
Vaša spletna stran bo delovala bolje.
Vaši uporabniki se bodo srečnejši.
In tako so ti učinki dejansko daje
nam nekaj globlje mislil.
>> Torej, vzemimo si oglejte, kaj spajanje vrsta je pravzaprav vse okoli.
Kul stvar je, da se združi razvrščanja je samo to.
To je, še enkrat, kaj smo se imenuje psevdokoda, psevdokoda bitje
Angleško-podobno skladnjo.
In preprostost nekako zanimivo.
>> Torej, na vhodu n elementov - tako, da pomeni le, tukaj je polje.
Ima n stvari v njem.
To je vse kar si rekel tam.
>> Če je n manj kot 2, vrne.
Torej to je samo nepomembna zadeva.
Če je n manj kot 2, potem seveda to 1 ali 0, pri čemer stvar
je že razporejene ali ga sploh ni, tako da samo vrniti.
Ni nič narediti.
Tako da je preprost primer, da drobovja off.
>> Drugje, imamo tri korake.
Razvrstite levo polovico elementov, razvrščanja desna polovica elementov,
in nato združiti razvrščena polovici.
Zanimivo tukaj je, da Nekako sem punting, kajne?
Tam je nekako krožno definicijo na ta algoritem.
V kakšnem smislu je to algoritem je definicija krožna?
>> PUBLIKA: [neslišno].
>> DAVID Malan: Ja, moj sortiranje algoritem, dveh njegovih korakov "neke
nekaj podobnega. "In tako, da Zastavlja Vprašanje, no, kaj bom uporabila
razvrstiti levo polovico in desna polovica?
In lepota tukaj je, da čeprav še enkrat, to je um-upogibni
del potencialno lahko uporabite isto algoritem za razvrščanje levo polovico.
>> Toda počakaj malo.
Ko ste povedali, da razvrstite leva polovica, kar sta dva
korake bo naslednji?
Bomo razvrstite levo polovico levo polovico in desno
polovica levo polovico.
Prekleto, kako rešiti ta dva polovice ali četrtine, zdaj?
>> Ampak to je v redu.
Imamo razvrščanja algoritem tukaj.
In čeprav boste morda skrbi, Prvi je to nekako neskončno
zanke, da je cikel, ki je nikoli bo na koncu - da se bo
na koncu enkrat, kaj se zgodi?
Ko je n manj kot 2.
Ki sčasoma se bo zgodilo, ker če boste obdržali prepolovi in
prepolovitev v prepolovitev te polčasih, zagotovo sčasoma boš do konca
s samo 1 ali 0 elementov.
Tedaj je ta algoritem pravi, da ste končali.
>> Torej resnično čarobno v tem Algoritem Zdi se, da
da je zadnji korak, ki združuje.
Ta preprosta ideja, samo združitev dveh Stvari, da je tisto, kar je v končni fazi bo
nam omogočajo, da razvrstite niz, recimo, osem elementov.
Torej imam osem več stresa Jajca Tu je osem koščke in eno
Google Glass -
ki lahko obdržim.
>> [SMEH]
>> DAVID Malan: Če bi lahko traja osem prostovoljci, in da vidimo, če lahko
igrati to ven, tako.
Wow, OK.
Računalništvo postaja zabavno.
Vse je v redu.
Torej, kaj pa vi trije, Največji roko gor.
Štiri zadaj.
Kaj pa vam bomo narediti trije v tej vrsti?
In štiri v ospredju.
Torej si osem, pridi gor.
>> [SMEH]
>> DAVID Malan: Jaz sem pravzaprav Ne vem, kaj je.
Je obremenilne kroglice?
Mizi svetilke?
Material?
Internet?
>> OK.
Torej, pridi gor.
Kdo bi rad -
naprej prihajajo.
Poglejmo.
In to vas postavlja v mestu -
ste v eni lokaciji.
Uh, počakaj malo.
1, 2, 3, 4, 5, 6, 7 - Dobro.
Vse je v redu, smo dobri.
Vse je v redu, tako da vsi imajo sedež, vendar ne na Google Glass.
Dovolite mi, da čakalne vrste te gor.
Kako ti je ime?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Vse je v redu, boste dobili izgledal geek, če je to v redu.
No, jaz tudi mislim, le za trenutek.
Vse je v redu, v pripravljenosti.
Smo bili poskuša dohiteti primera uporabe za Google Glass, in smo
mislil, da bi bilo zabavno, da pač to, ko so ljudje na odru.
Snemali bomo svet iz njihove perspektive.
Vse je v redu.
Ni verjetno, kaj Google je bilo predvideno.
Vse je v redu, če vas ne moti nošenja to v naslednjih neugodnih minut
da bi bilo čudovito.
>> Vse je v redu, tako da imamo tu niz elemente, in da matrike, kot na
Lističe v te ljudi ' Roke, ki je trenutno nesortirani.
>> MICHELLE: Oh, to je tako čudno.
>> DAVID Malan: To je precej naključno.
In čez nekaj trenutkov, da bomo poskušali izvajati zlivanjem skupaj
in videli, kje je ključ uvid je.
In Trik z zlivanjem je nekaj, kar še nismo prevzel.
Smo dejansko potrebovali nekaj dodaten prostor.
Torej, kaj se dogaja, še posebej Zanimivo je to, da so ti
Fantje se bodo za premikanje malo bit, ker bom za domnevo, da
tam je dodatno polje prostora, recimo, takoj za njimi.
>> Torej, če si za svojega predsednika, To je sekundarna polje.
Če jih tukaj sedijo, da je primarno polje.
Ampak to je vir, ki ga imamo Ne vzvodom doslej z mehurčkom
vrsta z izbiro vrste, z vstavljanja vrste.
Spomnimo, prejšnji teden, vsi le nekako premešan v mestu.
Niso uporabljajte dodatnega pomnilnika.
Smo naredili prostor za ljudi, ki jih premikanje ljudi okoli.
>> Tako da je to ključno spoznanje, preveč.
Tam je to kompromis, na splošno v računalništva, sredstev.
Če želite pospešiti nekaj kot čas, boste
morali plačati ceno.
In eden od teh cen zelo pogosto prostor, količino pomnilnika ali trdega
prostora na disku, ki ga uporabljate.
Ali pa, odkrito povedano, znesek časa programer.
Koliko časa vam bo, človek, dejansko izvajanje nekaterih bolj
zapleten algoritem.
Ampak za danes, kompromis je čas in prostor.
>> Torej, če bi vidva Dvigni številke, tako da bomo lahko videli, da ste
dejansko ujemanje 4, 2, 6, 1, 3, 7, 8.
Odlično.
Torej bom poskusil orkester stvari, lahko, če vidva
sledite mi tukaj.
>> Torej bom izvajala, prvič, Prvi korak psevdokoda, ki je
o vnosu n elementov, če je n manj kot 2 in spet.
Očitno je, da ne uporabljata tako da gremo naprej.
Torej razvrstite levo polovico elementov.
Torej to pomeni, da bom osredotočil moja pozornost za trenutek na to
Štirje fantje tukaj.
V redu, kaj moram storiti naslednji?
>> PUBLIKA: Razvrstite levo polovico.
>> DAVID Malan: Torej, zdaj moram rešiti leva polovica od teh fantov.
Ker je spet prevzel nase v Cilj je, da razvrstite levo polovico.
Kako si to naredil?
Preprosto sledite navodilom, čeprav čeprav smo to počeli še enkrat.
Torej razvrstite levo polovico.
Zdaj sem razvrščanje teh dveh fantov.
Kaj sledi?
>> PUBLIKA: Razvrstite levo polovico.
>> DAVID Malan: Razvrščanje levo polovico.
Torej, zdaj ti, ta stol tukaj je seznam velikosti 1.
In kaj ti je že ime?
>> PRINCESS DAISY: Princesa Daisy.
>> DAVID Malan: Princesa Daisy je tukaj.
In tako se je že urejeno, ker Seznam je velikosti 1.
Kaj moram storiti naslednji?
OK, vrniti, ker ta seznam je velikost 1, ki je manjša od 2.
Potem, kaj je naslednji korak?
In zdaj moraš nekako Vrniti v tvoji glavi.
>> Razvrstite desne polovice, ki je -
Kako ti je ime?
>> LINDA: Linda.
>> DAVID Malan: Linda.
In kaj naj storimo zdaj, imamo seznam velikosti 1?
>> PUBLIKA: Nazaj.
>> DAVID Malan: Previdno.
Vračamo prvi, zdaj tretja korak - in če sem nekako ga opisujejo z
zajema dva sedeža zdaj, zdaj sem ima združevanje teh dveh elementov.
Torej, zdaj žal, elementi so v okvari.
Ampak to je, če proces združevanja začne, da se prepričljivi.
>> Torej, če bi vi stand up za samo Trenutek, bom te potrebujem, v
Trenutek, da stopite na stol.
In če Linda, ker 2 je manjše od 4, zakaj ne
ste prišli okoli prvi?
Ostanite tam.
Torej Linda, prideš okoli prvi.
>> Zdaj v resnici, če je le niz smo jo lahko samo premaknete v realnem času
iz tega stola na tem mestu.
Torej, si predstavljajte, da je nekaj konstanta število korakov 1.
In zdaj -
vendar vas moramo postaviti v Na prvem mestu so tukaj.
>> In zdaj, če bi prišel okoli, kot tudi, da bomo
v mestu dveh.
In čeprav se to zdi, kot da je pri čemer nekaj časa, kaj je zdaj lepo je
da leva polovica leva polovica je sedaj urejeno.
Torej, kaj je naslednji korak, če bomo zdaj še nazaj v zgodbi?
>> PUBLIKA: Pravica pol.
>> DAVID Malan: Razvrščanje desne polovice.
Torej vidva to morali storiti, kot dobro.
Torej, če bi lahko vstane za trenutek?
In kako ti je ime?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, Jess je zdaj levo polovici desni polovici.
In tako da je seznam velikosti 1.
Ona je očitno razporejene.
In tvoje ime?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle je očitno Seznam velikosti 1.
Ona je že urejeno.
Torej, zdaj se zgodi čarovnija, Postopek združevanja.
Torej, kdo bo prvi prišel?
Očitno Michelle.
Torej, če bi lahko prišel od zadaj.
Prostor imamo na razpolago za njo zdaj je takoj za tem stolu tukaj.
In zdaj, če bi lahko prišel nazaj, kot tudi, imamo zdaj, da bo jasno, dva
polovičke, vsaka velikosti 2 -
in samo zavoljo upodobitev je, če bi lahko malo prostora -
eden levo polovico tu ena desna polovica tukaj.
>> Še previti v zgodbi.
Kaj je naslednji korak?
>> PUBLIKA: Merge.
>> DAVID Malan: Zdaj moramo združiti.
Torej OK, zdaj, na srečo smo pravkar sprostila štiri stole.
Tako smo dvakrat uporablja toliko pomnilnika, vendar lahko damo flip-flopping med
dveh nizov.
Torej, katera številka je na prvem mestu?
Torej Michelle, seveda.
Tako da pridejo okoli in se vaš sedež tukaj.
In potem številka 2, je očitno naslednji, tako da boste prišli sem.
Številka 4, številka 6.
In še enkrat, čeprav je Malo hoje sodeluje,
res, bi to lahko zgodi v trenutku, s premikanjem enega -
V redu, dobro igral.
>> [SMEH]
>> DAVID Malan: In zdaj smo je v dobrem stanju.
Levo polovico celotnega Vhod je sedaj urejeno.
Vse je v redu, tako da so ti ljudje imeli Prednost mojega -
kako se je na koncu vse punce na levo in vsi fantje na desni strani?
>> OK, torej 'fantje pa zdaj.
Torej vas ne bo sprehod skozi ti koraki.
Bomo videli, če bomo lahko znova Enako psevdokoda.
Če želite, da gredo naprej in stand up, in vi, mi vam mic.
Glej, če ne morete ponoviti, kar smo pravkar naredil tukaj na
Drugi konec seznama.
Kdo mora govoriti najprej ki temelji na algoritmu?
Torej, razloži, kaj delaš, preden kar koli stopala gibe.
>> SPEAKER 1: V redu, torej od leta Sem levo polovico
levo polovico, se bom vrnil.
Kajne?
>> DAVID Malan: Dobro.
>> SPEAKER 1: In potem -
>> DAVID Malan: Komu mic iti naprej?
>> SPEAKER 1: Naslednja številka.
>> ZVOČNIK 2: Torej, jaz sem desna polovica na levi polovici
levo polovico, in se bom vrnil.
>> DAVID Malan: Dobro.
Vrnete.
Torej, zdaj, kaj je naslednje na vrsti za vaju?
>> ZVOČNIK 2: Želimo videti, kdo je manjši.
>> DAVID Malan: Točno tako.
Želimo, da se združijo.
Prostor bomo uporabili za spajanje , čeprav oni so si v
očitno že razporejene, bomo da sledijo isti algoritem.
Torej, kdo gre v prvi nazaj?
Torej 3, nato 7.
In zdaj mic gre s temi fanti, OK?
>> ZVOČNIK 3: Zato sem desno polovico levo polovico in moj je n manj kot
1, tako da sem šele tekoč prehod -
>> DAVID Malan: Dobro.
>> ZVOČNIK 4: Sem prav polovica desno polovico desne polovice, in sem
tudi ena oseba, zato sem vrača.
Torej, zdaj smo spojiti.
>> ZVOČNIK 3: Torej gremo nazaj.
>> DAVID Malan: Torej, greš v hrbet.
Torej 5 gre, potem 8.
In zdaj občinstvo, ki je korak moramo sedaj nazaj
nazaj v naših glavah?
>> PUBLIKA: Merge.
>> DAVID Malan: Združitev levo in desno polovico polovico začetne levo polovico.
Torej, zdaj -
in samo, da bi to jasno, narediti malo prostora
med vami dva fanta.
Torej sedaj, da je na dveh seznamih, levo in desno.
Torej, kako bomo zdaj spajanju fantje v prednja vrsta sedežev spet?
>> 3. gre prvi.
Potem 5, seveda.
Potem 7. in 8. sedaj.
OK, zdaj smo?
>> PUBLIKA: Ni storiti.
>> DAVID Malan: Ni storiti, ker Očitno je, da je ostala korak.
Ampak še enkrat, zato sem z uporabo tega žargon, kot je "previjanju v tvoji glavi,"
to je zato, ker je to res kaj se dogaja.
Gremo skozi vse te korake, vendar smo nekako premori za
Trenutek, potapljanje globlje algoritem, premori za trenutek,
potapljanje globlje v algoritem, in Zdaj moramo nekako previjanju v našem
možgane in razveljaviti vse te plasti da smo nekako na čakanju.
>> Torej, zdaj imamo dva seznama velikosti 4.
Če bi vidva stand up še zadnjič in da malo prostora tukaj
jasno, da je to levo polovica original,
desna polovica od originala.
Kdo je prva številka, ki smo morali potegniti v zadnji?
Michelle, seveda.
>> Tako da smo dal Michelle tukaj.
In kdo ima številko 2?
Številka 2 prihaja na hrbtni strani, kot dobro.
Številka 3?
Odlično.
Številka 4, številka 5, številka 6, številka 7 in številka 8.
>> OK, tako da se mu je zdelo, kot veliko korakov, zagotovo.
Zdaj pa da vidimo, če ne moremo potrditi, nekako intuitivno, da je to
algoritem bistveno, zlasti n postane zelo velik, kot smo videli
z animacijami, je bistveno hitreje.
Torej Trdim ta algoritem, v najslabšem primera in tudi v najboljšem primeru
je velik O n-krat log n.
To pomeni, da je nekaj vidik tega algoritem, ki bo n korake, vendar
obstaja še en vidik nekje da ponovitev, da se zanka, ki
je log n korakih.
Lahko vam bo naš prst na tisto, ki dve številki se nanaša?
No, če -
kam mic iti?
>> SPEAKER 1: Bi se bo n nas razpada na dva dela -
delimo z dve, v bistvu.
>> DAVID Malan: Točno tako.
Vsak čas bomo videli v nobenem algoritmu s tem sedaj je bilo to vzorec
tako, tako, tako.
In to je običajno zmanjša za nekaj, kar je
logaritemska osnova dnevnik 2.
Vendar pa bi res lahko karkoli, pa se prijavite osnove 2.
>> Zdaj kaj pa n?
Vidim, da smo nekako ti razdeljeni Fantje - ti razdeljen, razdeljen vas,
ti deli, razdeljeni vas.
Kje pa konec prišel?
>> Torej je združevanje.
Ker razmišljam o tem.
Ko se združi osem ljudi skupaj, pri čemer polovica jih je sklop štirih
, druga polovica pa so drugi Komplet štirih, kako si šel
o tem združevanje?
No, vidva to storila precej intuitivno.
>> Ampak, če sem to storil namesto malo več metodično, morda sem opozoril na
skrajno levo oseba najprej moja leva roko, opozoril na skrajno levo osebe
od tega polovica s svojo desno roko, in šele nato šel skozi
Seznam, ki kaže na najmanjši element vsakič, premikanje moj prst in čez
po potrebi po seznamu.
Ampak kaj je ključna za to združitev Postopek je jaz primerjavi teh parov
elementov.
Na desni polovici in z leve pol, jaz niti enkrat nazadovanja.
>> Torej sama spajanje je ob ne več kot n korakov.
In kolikokrat si moram storiti, da bi bila združitev?
No, ne več kot n, in smo pravkar videl, da s končnim spajanje.
In tako, če narediš nekaj, kar traja log n korakih n-krat, ali obratno,
to se dogaja, da nam n-krat log n.
>> In zakaj je to bolje?
No, če smo že vedeli, da je dnevnik n je bolje kot n - kajne?
Videli smo v binarnem iskanju, telefonski imenik Na primer, log n je definitivno
bolje kot linearna.
To pomeni n-krat log n definitivno boljše kot n-krat drugo
n, AKA n kvadrat.
In to je tisto, kar na koncu občutek.
>> Tako velik aplavz, če smo lahko za te fante.
>> [APLAVZ]
>> DAVID Malan: In tvoji Razdjeljak darila - lahko obdržali število,
če bi želeli.
In tvoj slovo darilo, kot ponavadi.
Oh, in smo vam bo poslal posnetkov, Michelle.
Hvala.
Vse je v redu.
Pomagaj si na stres žogo.
>> In mi potegnite navzgor, v tem času, naš prijatelj Rob Bowden, da ponudijo
nekoliko drugačen pogled na to, saj si lahko misliš o teh
koraki dogaja v nekoliko drugačen način.
V resnici, set-up za to, kar je približno Rob da nam pokaže, predpostavlja, da smo jih
že storili tako sestavljajo velik seznam na osem manjših seznamov,
vsaka od velikosti 1.
>> Torej smo spreminja psevdokoda malo samo da nekako priti na
Osnovna ideja o tem, kako združuje dela.
Toda čas kaj teče on je na tem, da je še vedno
bo enaka.
In spet, set-up tukaj je, da je on začeli z osmimi sezname velikosti 1.
Torej ste zamudili del, kjer se je dejansko opravljeno log n, log n, log n
delitvijo na vhodu.
>> [Predvajanje videa]
>> -To je to za en korak je.
Za drugi korak, večkrat združi pare seznamov.
>> DAVID Malan: Hm.
Samo zvok prihaja iz mojega računalnika.
Dajmo še enkrat poskusiti.
>> -Samo samovoljno izbirati, katere - Zdaj imamo štiri sezname.
Naučite prej.
>> DAVID Malan: Takole.
>> Združitev-108 in 15, smo na koncu s seznama 15, 108.
Združitev 50 in 4, smo končajo s 4, 50.
Združitev 8 in 42, smo končajo z 8, 42.
In združitvijo 23 in 16, smo na koncu z 16., 23..
>> Zdaj vsi naši seznami velikosti 2.
Opazili, da vsak štirje seznami so razvrščeni.
Torej lahko začnemo združitvijo parov seznamov znova.
Združitev 15 in 108 ter 4 in 50, smo najprej vzeti 4, nato 15, nato
50, nato 108.
Združitev 8, 42 in 16, 23, moramo najprej sprejeti 8, nato 16, nato 23,
nato 42.
>> Torej, zdaj imamo samo dve sezname velikosti 4, od katerih je vsak razporejene.
Torej, zdaj imamo združevanje teh dveh seznamov.
Najprej smo vzeli 4, nato pa vzamemo 8, potem smo vzeli 15, nato 16, nato
23, nato 42, nato 50, nato 108.
>> [END predvajanje videa]
>> DAVID Malan: Spet obvestilo, nikoli dotaknila določeno posodo več kot enkrat
Po napreduje zunaj njega.
Torej še nikoli ponoviti.
Torej, on je vedno gibljejo na strani in to je, če imava n.
>> Zakaj ne pustite me dvigni eno animacijo da smo videli zgoraj, vendar tokrat
osredotoča le na zlivanjem.
Dovolite mi, da gredo naprej in povečavo V zvezi s tem tukaj.
Najprej naj izberejo naključno vhod, poveličevati to, in si lahko nekako videti
kar je samoumevno, prej, zlivanjem dejansko počne.
>> Tako opazili, da ste dobili te polčasih ali te četrtine ali ti osmine
Problem, ki naenkrat začnete jemati dobri formi.
In potem na koncu, boste videli na Zelo konec, da bam,
vse je združila skupaj.
>> Torej so to le trije različni je na isti zamisli.
Ampak ključno spoznanje, tako kot ločnice in vladaj v prvi razred,
je bil, da smo se odločili, da nekako razdeliti problem v nekaj velikega, v
kar nekako enaka v duhu ampak manjši in manjši in manjši
in manjši.
>> Zdaj pa še en zabaven način, da nekako mislim, o njih, čeprav to ni
bo dal enako intuitivno razumevanje, je
naslednja animacija.
Torej je ta video je nekdo dal skupaj , ki so povezana različna
zvoki z različnimi postopki za vstavljanje sort, za urejanje z zlivanjem, in
za nekaj drugih.
Torej, v tem trenutku, bom udaril Play.
To je približno dolg minuto.
In čeprav še vedno lahko vidite Vzorci se dogaja, tem času lahko
tudi slišati, kako so ti algoritmi opravljanju drugače in z
Nekoliko različni vzorci.
>> To je vstavljanje vrste.
>> [TONES IGRANJE]
>> DAVID Malan: Spet se poskuša vstaviti vsak element
na mesto, kamor spada.
To je bubble sort.
>> [TONES IGRANJE]
>> DAVID Malan: In lahko nekako počutim kako relativno malo delo, ki ga počne
za vsak korak.
To je tisto, kar tediousness sliši.
>> [TONES IGRANJE]
>> DAVID Malan: To je izbor sort, kjer izberete element, ki ga želimo
skozi znova in znova in znova in dajanje na začetku.
>> [TONES IGRANJE]
>> DAVID Malan: To je združiti vrste, ki lahko zares začutite.
>> [TONES IGRANJE]
>> [SMEH]
>> DAVID Malan: Nekaj ​​se imenuje gnome sort, ki jih nismo pogledal.
>> [TONES IGRANJE]
>> DAVID Malan: Torej, da vidim, zdaj, raztresen, kot si upamo so jih
glasbo, če bom lahko porinil malo malo matematike tukaj.
Torej je Četrti način, da bomo lahko pomislite, kaj to pomeni, da ti
naloge, ki se hitreje od tistih, , ki smo jih videli prej.
In če ste prihajajo v času od matematika ozadje, si
pravzaprav vem, morda je že, da si Lahko slap izraz na to tehniko -
sicer rekurzija, funkcija da se nekako kliče.
>> In spet opozoriti, da zlivanjem psevdokoda je rekurzivna v smislu
da je eden od korakov zlivanjem je je, da pokličete vrste -
da je sama.
Ampak na srečo, ker smo ohranili kliče vrste ali zlivanjem,
Natančneje, v manjši in manjši in manjši seznam, bomo na koncu
dno, hvala za tisto, kar imenujemo osnovna, težko kodiran primeru, da
omenjeni če seznam je majhna, manj kot 2 v tem primeru le vrnil takoj.
Če ne bi imeli to poseben primer, Algoritem bi nikoli dno ven,
in ti bi dejansko dobili v neskončna zanka resnično večno.
>> Recimo, da želimo, da sedaj dajo nekatere številke o tem, še enkrat, z uporabo n
kot je velikost vnosa.
In sem te hotel vprašati, kaj je Skupni čas sodeluje pri
teče zlivanjem?
Ali bolj na splošno, kaj je stroški pa v času?
>> No, to je precej težko izmeriti, da.
Če je n manj kot 2, ki je vpletena čas V sortiranje n elementov,
kjer je n 2, je 0.
Ker smo pravkar vrnil.
Ni treba kaj postoriti.
Zdaj verjetno, morda je še korak ali dva korake, da ugotovimo količino
delo, ampak to je dovolj blizu 0, da Jaz sem samo reči, no delo
potrebna, če je seznam tako majhen ne zanimajo.
>> Ampak v tem primeru je zanimivo.
Rekurzivni primer je podružnica psevdokoda tem je dejal še, neke
leva polovica razvrstite desno pol, združila dve polovici.
Zdaj zakaj se ta izraz predstavljati, da je račun?
No, T n pomeni le Čas je, da razvrstite n elementov.
In nato na desni strani enačaj tam, T n razdelimo
po 2 se nanaša na stroške za kaj?
Razvrščanje levo polovico.
Drugi T n deljeno z 2 je domnevno nanašajo na stroške
razvrstite desno polovico.
>> In potem plus n?
Se združujejo.
Ker če imate dva seznama, eden od velikost n več kot 2 in drugega velikosti n
več kot 2, moraš v bistvu dotik vsak od teh elementov, tako kot Rob
dotakne vsakega od skodelic, in samo kot smo poudarili na vsaki
Prostovoljci na odru.
Torej je n stroške združevanja.
>> Zdaj žal, ta formula je tudi sama rekurzivno.
Torej, če je vprašal, če je n, recimo, 16, če je 16 ljudi na odru
ali 16 skodelic v videu, koliko skupaj koraki traja, da jih razvrstite
z zlivanjem?
To je pravzaprav ni očiten odgovor, ker zdaj moraš nekako
rekurzivno odgovoriti na to formulo.
>> Ampak to je v redu, ker mi predlagamo da bomo naslednje.
Čas je izbral rešiti 16 ljudi, ali 16 skodelic se bo predstavljal
splošno kot T 16.
Ampak to je enako, glede na naše Predhodna formula, 2-krat znesek
Čas, ki je potreben za razvrščanje 8 skodelice plus 16.
In spet, plus 16 je čas, da se združijo, in dvakrat T 8 je
Čas je, da razvrstite levo polovico in desno polovico.
>> Toda tudi to ni dovolj.
Moramo, da se potopite globlje.
To pomeni, da moramo odgovoriti Vprašanje, kaj je T 8?
No T 8 je samo 2 Časovni T 4 plus 8.
No, kaj je T 4?
T 4 je le 2-krat T 2 plus 4.
No, kaj je T 2?
T 2 je le 2-krat T 1 plus 2.
>> In spet smo nekako dobili zaljubljen v tem ciklusu.
Ampak to je približno zadeti, da tako imenovani osnovni primer.
Ker kaj je T 1, ni trdimo?
0.
Zdaj končno lahko delamo nazaj.
>> Če T 1 je 0, lahko zdaj iti nazaj gor en poravnati s tem tipom sem in sem lahko
plug 0 za t 1.
Torej to pomeni, da je enaka 2 krat nič, sicer znan kot 0, plus 2.
In da celo izraz je 2.
>> Zdaj, če vzamem t 2, katerega odgovor je 2, ga priključite na srednjo črto, T
od 4, ki mi daje 2-krat 2 plus 4, tako 8.
Če sem nato priključite 8. do prejšnja linija, ki mi daje 2 krat 8, 16.
In če potem še, da se z 24, tako da v 16., smo končno dobili
vrednost 64.
>> Zdaj, samo po sebi nekako govori nič do n zapisu
velik O, omega, da smo jih je govoril.
Ampak se je izkazalo, da je 64 dejansko 16, velikost vhodu
log osnovo 2 16.
In če je to malo poznajo, samo pomislim nazaj, in to bom prišel nazaj
da vas na koncu.
Če je to osnova dnevnik 2, je kot 2. postavljeno na kaj vam daje 16?
Oh, to je 4, tako da je 16-krat 4.
>> In spet, to ni nič takega, če je to je neke vrste meglenem spominu zdaj.
Ampak za zdaj, da na veri da je 16 dnevnik 16 64.
In tako res, s to preprosto duševno zdravje preveriti, smo potrdili -
vendar ne dokazano formalno -
da čas teče spajanje vrsta je res n log n.
>> Torej ni slabo.
To je vsekakor bolje kot algoritmi smo videli doslej, in
to je zato, ker smo vzvodom, ena, tehniko, imenovano rekurzija.
Še bolj zanimivo kot to, da Pojem delitve in osvajanje.
Še enkrat, zares teden 0 stvari, ki tudi zdaj se ponovilo
bolj prepričljiv način.
>> Zdaj zabavno malo vaje, če ste nikoli naredil to - in verjetno
ne bi bilo, ker nekako normalno ljudje ne mislijo, da to storijo.
Ampak, če grem na google.com in, če je Želim, da se naučijo nekaj o
rekurzija, Enter.
>> [SMEH]
[Več smeha]
DAVID Malan: Bad šala počasi širi.
[SMEH]
DAVID Malan: Samo v primeru, da je tam.
Nisem urok narobe, in tam je šala.
Vse je v redu.
Pojasnite, da ljudje poleg vas, če to je precej ni kliknil samo še.
Ampak rekurzija, bolj na splošno, se nanaša s procesom funkcijo kliče
sam, ali bolj na splošno, tako problem v nekaj, kar je lahko
rešiti po kosih z reševanjem enaki reprezentativnih težave.
>> No, pa prestavljanje le za trenutek.
Radi bi na koncu o nekaterih cliffhangers, zato začnimo, da nastavite
faza, za nekaj minut, na zelo preprosto idejo -
da z zamenjavo dveh elementov, kajne?
Vseh teh algoritmov smo bili govorimo o zadnjih nekaj
predavanja vključujejo nekatere neke vrste zamenjavo.
Danes je vizualizirali z njihovo pridobivanje največ iz svojih stolov in
sprehod okoli, ampak v kodi, bi mi vzemite element iz enega niza
Pasti in ga v drugo.
>> Torej, kako bomo šli o tem?
No, naj gredo naprej in pisati Hitro program najdete tukaj.
Jaz grem naprej in to to kot sledi.
Recimo to -
Kaj hočemo, da pokličete to?
>> Pravzaprav ne.
Dovolite mi nazaj.
Ne želim storiti, da Alpinista še ni.
To bo pokvaril zabavo.
Naredimo to namesto tega.
>> Recimo, da želim napisati malo Program in da zdaj zajema ta
Ideja rekurzije.
Nekako sem dobil pred sebe tam.
Jaz bom naredil naslednje.
>> Prvič, hitro vključujejo standardne io.h, kot tudi vključujejo v cs50.h.
In potem bom šel naprej in razglasi int main praznino
na običajen način.
Sem spoznal, da sem misnamed datoteko, tako da Naj samo dodati. podaljšanje c tukaj, tako da
, ki ga lahko pripravijo pravilno.
Začeti to funkcijo izklopite.
>> In funkcija želim pisati, precej Preprosto povedano, je tista, ki prosi
Uporabnik za številne in nato sešteje vse številke, ki med
število in, recimo, 0.
Torej, najprej bom šel naprej in razglasi int n.
Potem sem kopirati nekaj kode, ki uporabili smo za nekaj časa.
Medtem ko je nekaj res.
Vrnil se bom na to v trenutku.
>> Kaj hočem narediti?
Hočem reči printf pozitiven celo prosim.
In potem bom pravijo n dobi dobil int.
Torej še enkrat, nekateri boilerplate koda , ki smo jih uporabljali prej.
In jaz bom to naredil medtem ko je n manj kot 1.
Tako se s tem zagotovi, da uporabnik mi daje pozitivno celo število.
>> In zdaj bom naredil naslednje.
Želim, da dodate do vseh številk med 1 in in n, ali 0 in n,
ekvivalentno, da bi dobili skupno vsoto.
Tako velik simbol sigma da boste morda spomni.
Torej bom to naredil tako, da najprej kliče Funkcija Sigma,
njegovo posredovanje v n, nato pa bom pravijo printf, odgovor je tam.
>> Torej na kratko, dobim in int od uporabnika.
Jaz se zagotovi, da je pozitivna.
Izjavljam spremenljivko z imenom odgovor tip int in trgovina v njej povratek
Vrednost sigma, ki poteka v n kot vhod.
In potem sem izpisal tak odgovor.
>> Na žalost, čeprav sigma sliši kot nekaj, kar bi lahko v
math.h datoteke, njena izjava, da je dejansko ni.
Tako, da je v redu.
Ne morem izvajati to sam.
Grem izvajati funkcijo imenovano sigma, in to bo trajalo
parameter -
kaj je samo call it m, samo tako da je drugačen.
In potem je tu gor, bom rekel, in, če je m manj kot 1 - to je
zelo nezanimiv program.
Tako da sem šel naprej in takoj vrne 0..
To preprosto nima smisla sešteti vse številke od 1 do m, če m
sam 0 ali negativna.
>> In potem bom šel naprej in to zelo iterativno.
Jaz bom naredil to vrsto old-school, in jaz grem naprej
in rekel, da bom razglasi znesek za 0.
Potem bom še za zanke int -
in mi to storiti za doseganje naših distribucija kodo, tako da boste imeli kopijo
doma. int i dobi 1 na do i je manjša ali enaka m.
i plus plus.
In potem notranjost ta zanka -
smo skoraj tam -
vsota dobi vsoto plus 1.
In potem se bom vrnil vsoto.
>> Zato sem to storil hitro, čisto res.
Ampak še enkrat, katerega glavna funkcija je precej preprosta, temelji na kodi, ki smo jih
doslej napisal.
Uporablja dvojno zanko, da bi dobili pozitiven int od uporabnika.
Nato sem mimo tega int na novo funkcijo imenovane sigma, ga kliče, še enkrat, n.
In jaz shranjevanje vrne vrednost, odgovor od sedaj črne skrinjice
znan kot sigma v variabilni imenovano odgovor.
Potem sem ga natisnete.
>> Če bomo zdaj še zgodbo, kako se sigma izvaja?
Predlagam, da izvaja takole.
Najprej malo napak in zagotoviti, da uporabnik ni
zajebavam z mano in poteka v nekatera negativna ali 0 vrednost.
Potem sem se razglasi spremenljivko sešteje in jo nastavite na 0.
>> In zdaj sem začel premikati iz i je enak 1. vse tja do vključno m,
ker želim, da se vključijo vsi številke od ena do m, vključno.
In znotraj tega za zanke, sem naredil Vsota dobi vse, kar je sedaj, plus
Vrednost i.
Plus vrednost i.
>> Kot prahi, če se niste videli tega prej, obstaja nekaj skladenjsko sladkorja
Za te vrstice.
To lahko znova kot plus enako i, samo, da sam prihranite nekaj tipkanja
in pogledati malo hladnejše.
Ampak to je vse.
To je funkcionalno enako.
>> Žal pa ta oznaka je ne bo še prevesti.
Če sem teči, da sigma 0, kako am Jaz bom dobil nadrla?
Kaj se to dogaja, da ni všeč?
>> PUBLIKA: [neslišno].
>> DAVID Malan: Ja, ni prijavil Funkcija up top, kajne?
C je malo butast, ampak samo v tem, da ne, kaj ti povem, da narediti, in ti
to storiti v tem vrstnem redu.
In tako, če sem udaril Enter tukaj, bom dobili opozorilo o sigma implicitna
deklaracija.
>> Oh, ni problema.
Lahko grem do vrha in sem lahko rekli, v redu, počakaj malo.
Sigma je funkcija, ki vrne int in pričakuje, da bo
int kot vstopni, podpičjem.
Ali lahko dam celotno funkcijo nad glavno, ampak na splošno, jaz bi
odsvetujemo, da zato, ker je lepo, da imajo vedno glavni na vrhu tako
lahko potopite v desno in vedo, kaj Program počne z branjem glavni prvi.
>> Torej, zdaj mi počistite zaslon.
Remake sigma 0.
Vse se zdi, da preverite.
Dovolite mi, da teče sigma 0.
Pozitivna med.
Dal bom številko 3. naj bo enostavno.
Tako, da mi je dal 3 plus 2 plus 1, torej 6.
Vnesti, in res sem dobil 6.
>> Jaz lahko naredim nekaj večjega -
50, 12, 75.
Tako kot tangenta, bom naredil nekaj smešno, kot je res velika
Številka, Oh, to je dejansko delal -
eh, jaz ne mislim, da je prav.
Poglejmo.
Kaj je res igraš z njim.
>> To je težava.
Kaj se dogaja?
Koda ni tako slabo.
Še vedno linearna.
Žvižganje je dober učinek, čeprav.
Kaj se dogaja?
>> Ne vem, če sem to slišal.
Tako se izkaže - in to je kot stran.
To ni jedro Ideja rekurzije.
Izkazalo se je, ker sem poskušal predstavljajo tako veliko število, najbolj
verjetno je, da bi razlagala s C kot ne pozitivnim predznakom,
ampak negativno število.
>> Nismo govorili o tem, vendar je Izkazalo se je, da so negativne številke
v svetu, poleg do pozitivnih številk.
In sredstva, s katerimi lahko predstavljajo negativno število
v bistvu je, da uporabite enega poseben bit, ki označuje
pozitivna nad negativno.
To je malo bolj zapleten kot to, ampak to je osnovna ideja.
>> Torej, žal, če C je zmedeno eno teh bitov so dejansko pomeni,
oh, to je negativno število, moja zanka Tukaj, na primer, je dejansko še
bo prekine.
Torej, če bi bil dejansko tiskanje nekaj znova in znova, bi se
glej cel kup.
Toda tudi to je poleg točke.
To je res samo nekakšna intelektualna radovednost, da bomo prišli
nazaj na koncu.
Toda za zdaj, to je pravilno Izvajanje če predpostavimo, da
Uporabnik bo ints , ki se prilegajo v ints.
>> Vendar trdim, da je ta koda, odkrito povedano, bi lahko naredili toliko bolj preprosto.
Če je cilj na roki, je, da se število kot m in seštejejo vsi
številke med njim in 1 ali obratno med 1 in, Trdim
da si lahko sposodim to idejo, da se združijo sortiranje imel, ki je bil ob težave
te velikosti in deljenjem v nekaj manjši.
Mogoče ne pol, ampak manjši, vendar reprezentativno enako.
Enako zamisel, vendar manjši problem.
>> Tako da sem pravzaprav - naj shraniti to datoteko z drugačno številko različice.
Poklicali bomo to različico 1 namesto 0.
In trdim, da sem lahko dejansko reimplement to v tovrstne
um-upogibni način.
>> Bom pustil del njega samega.
Jaz bom rekel, če m je manj od ali celo enaka 0 -
Grem, da se malo več anal tokrat
z mojo napako preverjanje -
Jaz grem naprej in vrne 0..
To je poljubna.
Jaz sem samo preprosto odloči, če uporabnik mi daje negativno število, sem
vračanje 0, in bi moral prebrati Dokumentacija bolj.
>> Drugega -
opazili, kaj bom naredil.
Sicer se bom vrnil m plus -
kaj je sigma od m?
No, sigma o m plus minus 1 m, plus minus m 2, plus minus 3 m.
Ne želim napisati vse to ven.
Zakaj ne bi jaz samo punt?
Rekurzivno sam klic z nekoliko manjši problem, podpičje,
in za danes?
>> Kajne?
Zdaj tudi tu, bi lahko počutite ali skrbi da je to neskončno zanko, da sem
indukcije, pri čemer sem izvajanjem sigma ga kliče sigma.
Ampak to je popolnoma v redu, ker sem Mislil naprej dodal, katere vrstice?
>> PUBLIKA: [neslišno].
>> DAVID Malan: 23 do 26, ki če je moj pogoj.
Ker tisto, kar je lepo o odštevanje tukaj, ker sem naprej
Izročitev sigma manjše težave, manjša Težave, manjši - to ni
pol velikosti.
Saj je samo otrok korak manjši, ampak to je v redu.
Ker na koncu, bomo delo naša pot navzdol na 1 ali 0.
In ko smo zadeli 0, sigma ni dogaja, da se več poklical.
To se dogaja, da takoj vrne 0..
>> Torej učinek, če nekako veter to v tvoji glavi, je dodati m plus
m minus 1, plus minus m 2, plus minus m 3, plus pika, dot, pika, m minus
m, na koncu vam daje 0 in Učinek je na koncu dodati vse
te stvari skupaj.
Torej nimamo, z rekurzijo, rešiti problem, ki smo
ne more rešiti prej.
Dejansko verzija 0 tega, in vsak problem danes je bil rešljiv
s samo uporabo for zanke ali pa zanke ali podobne konstrukcije.
>> Ampak rekurzija, upam si reči, daje nam drugačen način razmišljanja o
Težave, s katerimi se lahko, če vzamemo problem, ga razdelite od nečesa
nekoliko velik v nekaj nekoliko manjši, Trdim, da ga bomo lahko rešili
morda malo bolj elegantno v smislu zasnove, z manj kode,
in morda celo rešili težave, ki bi bo težje, saj bomo sčasoma
glej, reševanje zgolj iterativno.
>> Ampak Alpinista, da sem storil želimo, da nas pustite bilo to.
Dovolite mi, da gredo naprej in odprite do datotek od -
pravzaprav, naj gredo in to storiti zelo hitro.
Dovolite mi, da gredo naprej in predlagati Naslednji.
Med današnjim koda je ta datoteka tukaj.
Ta tukaj, noswap.
>> Torej, to je neumno malo program, ki Sem podžigal, ki trdi, da ne
Naslednji.
V glavnem, najprej razglasi int imenuje x in ga dodeli
vrednost 1.
Potem pa izjavlja, int y in dodeli to vrednost 2.
Potem se natisne kar x in y.
Potem pa pravi, zamenjavo, dot dot piko.
>> Potem pa trdi, da se kliče funkcijo imenuje zamenjavo, ki poteka v x in
y, ideja, ki je, upajmo x in y bo ponovno
drugačen, nasprotno.
Potem pa trdijo, zamenjali!
s klicajem.
Potem se natisne x in y.
>> Ampak se je izkazalo, da je to zelo preprosta predstavitev navzdol
Tu je pravzaprav vozičkom.
Čeprav sem o razglasitvi začasne spremenljiva in začasno dajanje v
jo, nato pa sem prerazporeditev vrednost b -
ki se počuti smiselno, ker sem shrani kopijo v temp.
Potem sem posodobiti b, da enako kar je bilo v temp.
Ta vrsta shell igro gibljejo v B in B v s tem
middle-man imenovano temp počuti popolnoma razumljiva.
>> Vendar trdim, da ko sem teči ta kodo, kot bom pa zdaj -
Naj gredo naprej in ga prilepite tukaj.
Poklical bom to noswap.c.
Kot ime pove, da to ni bo pravilen program.
Naredite noswap. / Ne swap.
x 1, y 2, zamenjavo, zamenjali.
x je 1, je y 2.
To je popolnoma narobe, čeprav čeprav se to zdi povsem
smiselno, da me.
In tu je razlog, vendar nismo bo razkrila razlog samo še.
>> Za zdaj drugi Cliffhanger sem hotel da greš s to,
Napoved vrst na kod kuponov.
Naša inovacija poznih dneh letos je izzvala nepomembno število
vprašanj, kar je bilo ni naš namen.
Namen teh kod kuponov, pri čemer, če vam del problema
nastavite zgodaj, tako dobili dodaten dan, je res, da bi vi pomagali
sami začeli zgodaj, vrste stranskih vas incentivizing.
Pomaga nam distribucijo tovora čez Uradne ure bolje, tako da
to je nekako win-win.
>> Na žalost, mislim, da mojim navodilom niso bili do sedaj zelo jasno, da
Ta vikend sem se vrnil in posodobljene spec v večji, drznejši besedilo k
razložiti naboje kot ti.
In samo to povedati javnosti bolj po privzete, problem sprejemnikov so posledica četrtek
opoldne po predmetniku.
Če začnete zgodaj, zaključna dela Problem, ki ga je v sredo ob 12:00
PM, del, ki se nanaša na obrestno mero koda, ideja je, da lahko podaljša
poteče rok za P nastavite do petka.
To je malo off majhen del P relativne glede na to, kar je značilno
večji problem, kupite sami dodaten dan.
Spet vam pride razmišljanje o Problem set, vam do gets
govorilne ure prej.
Ampak koda problem kupon še zahteva, da tudi če ga ne predloži.
>> Ampak bolj prepričljivo je to.
(ODER WHISPER) In ti ljudje zapuščajo zgodaj so žal boš.
Ker so ljudje na balkonu.
Se opravičujem vnaprej ljudska pesem o balkon iz razlogov, ki bodo
jasno, čez nekaj trenutkov.
>> Tako da smo srečni, da imajo enega CS50 je nekdanji vodja poučevanje tovariši na
podjetje, imenovano dropbox.com.
Imajo zelo velikodušno podaril kupon koda tukaj za to toliko prostora,
ki je odvisno od Običajni 2 gigabajta.
Torej, kaj sem mislil, da bi naredil o tem Končna ocena je narediti nekaj v zibelko,
pri čemer vsak trenutek, bomo razkriti zmagovalec in kdo ima kupon
kodo, ki jo lahko nato iti na svoje Spletna stran, ga vnesite v, in voila, dobil
veliko več Dropbox prostor za vaš aparata in vaših osebnih datotek.
>> In prvi, ki bi želeli sodelovati v tej risbi?
OK, zdaj je še bolj zabavno.
Oseba, ki prejme ta 25-GB kupon koda - ki je daleč
bolj prepričljiv kot prepozno Zdaj dni, morda -
je tisti, ki sedi na vrhu sedežne blazine, pod katerimi so
da je koda kupona.
Sedaj lahko ogledate spodaj vaše sedežne blazine.
>> [Predvajanje videa]
>> -Ena, dva, tri.
>> [Kričanje]
>> Si dobil avto!
Dobiš avto!
>> DAVID Malan: Bomo videli ste v sredo.
>> Si dobil avto!
Dobiš avto!
>> DAVID Malan: Balkon ljudje, pridite dol s čela
kjer imamo statistov.
>> -Vsak dobi avto!
Vsakdo dobi svoj avto!
>> [END predvajanje videa]
>> Pripovedovalec: Na naslednjem CS50 -
>> ZVOČNIK 5: O moj bog bog bog bog bog bog bog bog bog bog -
>> [UKELELE Predvaja]