>> [Tónlist spila]
DAVID Malan: Allt í lagi.
Allt í lagi, velkominn aftur.
Svo er þetta Vika 4, í upphafi þeirra, þegar.
Og þú munt minnast þess að í síðustu viku, leggjum númerið til hliðar fyrir aðeins lítill hluti
og við byrjuðum að tala smá meira hár-láréttur flötur, um hluti eins
leita og flokka, sem þó nokkuð einfalt hugmyndir, eru
fulltrúi flokki vandamálum þú verður að byrja að leysa sérstaklega
eins og þú byrjar að hugsa um endanlega verkefni og áhugaverðar lausnir sem þú
gæti þurft að raunverulegur-veröld vandamál.
Nú kúla tegund var eitt af því einfaldasta svo reiknirit, og það
unnið með því að hafa þessar litlu tölur í lista eða í array konar
kúla leið sína upp á toppinn og stór númer færa leið sína niður að
enda þeim lista.
>> Og muna að við gætum sjón kúla konar smá
eitthvað eins og this.
Svo láta mig fara á undan og smelltu á Start.
Ég hef forvalinn kúla konar.
Og ef þú manst að hærri blár línur tákna stór númer, lítið
blár línur tákna lítil númer, eins og við förum í gegnum þetta aftur og aftur og
aftur, bera saman tvær bars við hliðina á hvor annan í rauðu, við erum að fara að skipta á
Stærsta og minnsta ef þeir eru út af röð.
>> Þannig að þetta mun halda áfram og áfram og fara á, og þú munt sjá að stærri
þættir eru að gera sér leið til rétt, og smærri þættir eru
gerð þeirra vegur til vinstri.
En við byrjuðum að mæla skilvirkni, the
gæði þessa reiknirit.
Og við sögðum að í versta tilfelli, þetta reiknirit tók
u.þ.b. hversu mörg skref?
>> Svo n ferningur.
Og hvað var n?
>> Áhorfendur: Fjöldi þátta.
>> DAVID Malan: Svo n var Fjöldi þátta.
Og svo við munum gera þetta oft.
Hvenær við viljum tala um stærð um vandamál eða stærð að
inntak, eða þann tíma sem það tekur að framleiða framleiðsla, munum við bara
almenn hvað inntak er eins n.
Svo aftur í viku 0, fjölda síður í símaskránni var n.
Fjölda nemenda í herberginu var n.
Svo hér líka, við erum eftir að mynstur.
>> Nú n ferningur er ekki sérstaklega hratt, svo við reyndum að gera betur.
Og svo skoðuðum við nokkra önnur reiknirit, þar á meðal
voru val konar.
Svo raða val var svolítið öðruvísi.
Það var næstum einfaldara, ég þori að segja, þar sem ég byrjaði í upphafi sem
listi af sjálfboðaliðum okkar og ég bara aftur og aftur og aftur fór í gegnum
lista, plokkun út minnstu þáttur í einu og setja hann eða
henni í upphafi á listanum.
>> En þetta líka, þegar við byrjuðum að hugsa gegnum stærðfræði og stærri
mynd, hugsaði um hversu oft Ég var að fara fram og til baka og aftur
og fram, sagði að við í versta tilfelli, val tagi, líka, var það?
n veldi.
Nú í hinum raunverulega heimi, gæti það reyndar vera ívið hraðar.
Því aftur, gerði ég ekki að halda backtracking þegar ég hafði raðað á
Minnsta atriði.
En ef við hugsum um mjög stór n og ef þú gerir svona út stærðfræði sem
Ég gerði í stjórn, með n veldi mínus eitthvað, allt annað
auk n veldi, einu sinni n fær mjög stór, er ekki
máli eins mikið.
Svo sem tölvunarfræðingum, raða við um snúa að blindu auga til minni
þættir og einblína á þáttur í tjáning sem er að fara að gera
mesti munurinn.
>> Jæja, loksins, leit við á Innsetningarröðun.
Og þetta var svipað í anda, en frekar en að fara í gegnum iteratively og
velja minnstu þátturinn einn á tími, tók ég í staðinn höndina sem ég
var fjallað, og ég ákvað, allt rétt, tilheyrir þú hér.
Þá er ég flutti á til the næstur þáttur og ákvað að hann eða
hún átti hér.
Og þá er ég flutti á og á.
Og ég gæti til, á leiðinni, skipta þessar krakkar í því skyni að
gera pláss fyrir þá.
Svo sem var eins konar andlega viðsnúnings af tegund val sem við
kallað innsetningu konar.
>> Svo þessi mál til komið í hinum raunverulega heimi.
Fyrir nokkrum árum síðan, þegar tiltekinn Senator var í gangi fyrir forseta,
Eric Schmidt, á þeim tíma forstjóri Google, í raun hafði tækifæri
að viðtal honum.
Og við héldum að við myndum deila þessu YouTube bút fyrir þig hér, ef við gætum snúið upp
rúmmál.
>> [Vídeó spilun]
>> -Nú, Senator, ert þú hér á Google, og ég eins og til hugsa af formennsku
sem atvinnuviðtal.
>> [Hlátur]
>> -Nú er það erfitt að fá starf sem forseti.
Og þú ert að fara í gegnum rigors núna.
Það er líka erfitt að fá vinnu á Google.
Við höfum spurningar og við spyrjum frambjóðendur spurningum okkar.
Og þetta er frá Larry Schwimmer.
>> [Hlátur]
-Þið held ég að grínast?
Það er hérna.
Hvað er skilvirkasta leiðin til raða milljón tveggja bita heiltölur?
>> [Hlátur]
>> -Jæja, uh -
>> -Ég því miður.
Kannski við ættum -
>> -Nei, nei, nei, nei, nei.
>> -Það er ekki -
OK.
>> -Ég held að kúla tegund myndi vera röng leið til að fara.
>> [Hlátur]
>> [Uppörvandi og lófaklapp]
>> -Komdu, sem sagði honum þetta?
OK.
>> [END vídeó spilun]
>> DAVID Malan: Svo þar hafið þið það.
Svo byrjuðum við að mæla þetta gangi sinnum, svo að segja, með eitthvað
kallað asymptotic merki, sem er bara vísa til að flokka okkar beygja
blindur auga til þeirra smærri þáttum og aðeins að horfa á hlaupandi tíma,
árangur þessara reiknirit, eins og n fær mjög stór með tímanum.
Og svo við kynna stór O. og Big O fulltrúa eitthvað sem við héldum
af eins og efri bundið.
Og reyndar, Barry, getum við lækkað en mic svolítið?
>> Við héldum þetta er efri bundið.
Svo stór O n veldi þýðir að í versta tilfelli, eitthvað eins og
val konar myndi taka n ferhyrndir skrefum.
Eða eitthvað eins og Innsetningarröðun myndi n ferningur skref.
Nú fyrir eitthvað eins innsetningu tegund, hvað var það versta tilfelli?
Gefið fylki, hvað er það versta mögulegt atburðarás sem þú gætir fundið
sjálfur frammi?
>> Það er alveg afturábak, ekki satt?
Vegna þess að ef það er alveg aftur á bak, þú þarft að gera a heild einhver fjöldi af vinna.
Vegna þess að ef þú ert alveg aftur, þú ert að fara að finna
stærsta þáttur hér, jafnvel þótt það tilheyrir þangað.
Svo þú ert að fara að segja, allt í lagi, að minnsta þessari stundu í tíma, tilheyrir þú hér,
svo þú láta það standa.
>> Þá þér grein, ó, fjandinn, ég verð að færa þetta örlítið minni þáttur að
vinstri af þér.
Þá verð ég að gera það aftur og aftur og aftur.
Og ef ég gekk fram og til baka, þú myndi raða á finnst árangur
að reiknirit, vegna þess að stöðugt er ég uppstokkun allir aðrir niður í
array til að gera pláss fyrir það.
Svo er það versta tilfelli.
>> Með því móti -
og þetta var cliffhanger síðast -
ég sagði að innsetning konar var Ómega um hvað?
Hvað er best málið gangi tími Innsetningarröðun?
Svo það er í raun n.
Það var autt að við fórum á borð síðast.
>> Og það er Omega í n því hvers vegna?
Jæja, í besta tilfelli, hvað er innsetningu konar leið til að afhenda?
Jæja, lista sem er alveg raðað nú þegar, lítil vinna að gera.
En hvað er sniðugt um Innsetningarröðun er það vegna þess að það byrjar hér og
ákveður, ó, þú ert númer einn, tilheyrir þú hér.
Hvílíkur gæfu.
>> Þú ert númer tvö.
Þú tilheyra einnig hér.
Númer þrjú, jafnvel betra, þú tilheyrir hér.
Um leið og það fær að lok lista, Per innsetningu tagi er sauðakóðanum
sem við gengum í gegnum munnlega síðasta sinn, það er gert.
En val tagi, hins vegar hélt að gera hvað?
>> Haldið að fara í gegnum listann aftur og aftur og aftur.
Þar sem lykillinn innsýn það var aðeins þegar þú hefur skoðað alla leið til
endir á listanum getur þú verið viss að þáttur sem þú valdir var
örugglega eins lítill þáttur.
Svo þessar mismunandi andlega módel enda upp sveigjanlegur sumir mjög raunverulegur-veröld
munur fyrir okkur, eins og heilbrigður eins og þessir fræðileg aðfelluþrýstingi munur.
>> Svo bara til að ágrip, þá stór O í n ferningur, höfum við séð nokkur slík
reiknirit svona langt.
Big O n?
Hvað er reiknirit sem gæti að segja að vera stór O í n?
Í versta tilfelli, það tekur línulegt fjölda skrefum.
>> OK, línuleg leit.
Og í versta tilfelli, þar er þáttur sem þú ert að leita að þegar
beita línuleg leit?
>> OK, í versta tilfelli, það er ekki einu sinni þarna.
Eða í annarri versta tilfelli, það er alla leið á endanum, sem er
plús-eða-mínus eitt skref munur.
Svo í lok dagsins, við getum sagt að það er línuleg.
Big O n væri línuleg leit, vegna þess að í versta tilfelli,
þáttur er ekki einu sinni þar eða það er alla leið á enda.
>> Jæja, stór O log n.
Við ekki tala í smáatriðum um þetta, en við höfum séð þetta áður.
Hvað liggur í svokölluðum lógaritmískum tíma, í versta tilfelli?
>> Já, svo tvöfaldur leit.
Og tvöfaldur leita í versta tilfelli gæti hafa þáttur einhversstaðar í
miðju, eða einhvers staðar inni í array.
En þú finnur bara það þegar þú skipta lista í tvennt, í
helmingur, í tvennt, í tvennt.
Og þá voila, það er það.
Eða aftur, versta tilfelli, það er ekki einu sinni þarna.
En þú veist ekki að það er ekki þar þar til þú nærð svona að síðustu
botn-flestir þættir með helminga og helminga og helminga.
>> Big O 1..
Svo við gætum stór O 2, stór O í 3.
Hvenær sem þú vilt bara stöðugt tala, við að raða bara í bara einfalda
að eins stór O í 1.
Jafnvel þó að raunhæft, það tekur 2 eða jafnvel 100 skref, ef það er
stöðug tala af skrefum, við segjum bara stór O 1..
Hvað er reiknirit sem er í stóru O í 1?
>> Áhorfendur: Að finna lengd af breytu.
>> DAVID Malan: Finndu lengd breytu?
>> Áhorfendur: Nei, lengd ef það er þegar raðað.
>> DAVID Malan: Gott.
OK, svo að finna lengd eitthvað ef lengd að eitthvað, eins og
fylki, er geymt í sumum breytu.
Þar sem þú getur bara lesið breytu, eða prenta breytu, eða
bara almennt aðgang þá breytu.
Og voila, sem tekur stöðugum tíma.
>> Hins vegar að hugsa til baka til að klóra.
Hugsaðu til baka í fyrsta viku C, hringja bara printf og prentun
eitthvað á skjánum er að öllum líkindum stöðug tíma, vegna þess að það tekur bara
sumir tala um hringrás CPU til að sýna þessi texti á skjánum.
Eða bíddu - er það?
Hvernig annars gætum við fyrirmynd Afkoma printf?
Myndi einhver vilja vera ósammála, að kannski er það ekki í raun fasti skipti?
Í hvaða skilningi gætu printf er í gangi tíma, í raun prentun a band á
á skjánum, að vera eitthvað önnur en stöðug.
>> Áhorfendur: [inaudible].
>> DAVID Malan: Já.
Svo fer það eftir sjónarhorni okkar.
Ef við hugsum í raun um inntak til printf eins og að vera band, og
því við að mæla stærð sem inntak af lengd þess - Svo skulum kalla
að lengd n eins vel -
að öllum líkindum, printf er sjálft stór O í n því það er að fara að taka þig n stíga
að prenta út hvert þeirra n stafir, líklega.
Að minnsta kosti að því marki sem við gerum ráð fyrir að kannski það er að nota fyrir lykkja
undir hetta.
>> En við yrðum að líta á sem Kóði til að skilja það betur.
Og reyndar, þegar þið byrja greina eigin reiknirit þinn munt þú
bókstaflega að gera einmitt þetta.
Raða af auga númerið þitt og hugsa um - allt í lagi, ég hef þetta lykkju
hér eða ég hreiður lykkjur hér, það er að fara að gera N hlutina n sinnum,
og þú getur raða ástæðu leið gegnum kóðann, jafnvel ef það er
sauðakóðanum og ekki raunverulegt númer.
>> Og hvað um ómega á n veldi?
Hvað var reiknirit sem í besta málið enn tók n ferningur skref?
Já?
>> Áhorfendur: [inaudible].
>> DAVID Malan: Svo val konar.
Vegna þess að í því vandamáli raun minnkað til þess að aftur, ég veit ekki
Ég hef fundið núverandi minnstu þangað Ég hef athugað alla fjári þætti.
Sem Omega af, segja, n, við bara kom upp með eitt.
Innsetning tagi.
Ef listinn verður að vera flokkaður nú þegar, í besta tilfelli við höfum bara
að gera einn fara í gegnum það, á hver benda að við erum viss.
Og þá má segja að vera línuleg, fyrir viss.
>> Hvað um ómega af 1?
Hvað, í besta tilfelli gæti tekið stöðug nokkur skref?
Svo línuleg leit, ef þú færð bara heppinn og þáttur sem þú ert að leita
er rétt í byrjun af the listi, ef það er þar sem þú ert að byrja þína
línuleg traversal af þeim lista.
>> Og þetta er satt af ýmislegt.
Til dæmis, jafnvel tvöfaldur Leit er Omega 1..
Því hvað ef þú færð virkilega fjári heppinn og smack-DAB í miðju
array er fjöldi þú ert að leita að?
Svo þú getur fengið heppinn þar, eins og heilbrigður.
>> Þetta eitt, loksins, ómega af n log n.
Svo n log n, höfum vér ekki í raun tala um enn, en -
>> Áhorfendur: Sameina einhverskonar?
>> DAVID Malan: Mergesort.
Það var cliffhanger síðustu tíma, þar sem við lagt, og við sýndum
sjónrænt, að það eru reiknirit.
Og sameinast einhverskonar bara einn svo reiknirit sem er í grundvallaratriðum hraðar
en sumir af þessum strákum.
Í raun, sameinast stutt er ekki aðeins í Besta ræða n log n, í versta
ræða n log n.
Og þegar þú hefur þetta tilviljun Omega og stór O vera það sama?
Við getum í raun lýsa því sem það er kallast þeta, þó að það er
lítið sjaldgæfari.
En það þýðir bara tvö mörk, í þessu tilfelli, eru þau sömu.
>> Svo sameinast raða, hvað þýðir þetta virkilega sjóða niður fyrir okkur?
Jæja, muna hvatning.
Leyfðu mér að draga upp annað fjör sem við ekki að líta á síðasta tíma.
Þetta eitt, sama hugmynd, en það er lítið stærri.
Og ég ætla að fara á undan og benda á fyrst - við höfum innsetningu konar á
efst til vinstri, þá val tagi, kúla tegund, a par af öðrum toga -
skel og fljótur - að við höfum ekki talað um, og hrúga og sameina tegund.
>> Svo að minnsta kosti að reyna að einbeita augun á þrjár á vinstri og síðan
Mergesort þegar ég smelli þetta græna ör.
En ég læt þær allar hlaupa, bara til að gefa þér tilfinningu fyrir fjölbreytileika
reiknirit sem ríkir í heiminum.
Ég ætla að láta þetta hlaupa fyrir örfáum sekúndum.
Og ef þú einblína augun - Pick reiknirit, leggja áherslu á það að bara
sekúndur - þú munt byrja að sjá mynstur sem það er framkvæmd.
>> Sameina tegund, tilkynning, er gert.
Hrúga tegund, fljótur tagi, skel -
svo virðist að við kynntum þrjá versta reiknirit síðustu viku.
En það er gott að við erum hér í dag til að líta á sameiningu tagi, sem er eitt af
því auðveldara sjálfur er að líta á, jafnvel þó það líklega mun sveigja huga þinn
bara svolítið.
Hér getum við séð hversu mikið val konar sjúga.
>> En á bakhlið er það mjög auðvelt að framkvæma.
Og kannski fyrir P Set 3, sem er einn af reiknirit sem þú velur til að innleiða
fyrir venjulegt útgáfu.
Fullkomlega fínn, fullkomlega rétt.
>> En aftur, eins og n fær stór, ef þú valið að framkvæma a festa reiknirit
eins sameinast raða, eru líkurnar á stærri og stærri inntak, númer er bara
fara að hlaupa hraðar.
Vefsvæðið þitt er að fara að vinna betur.
Notendur þínir eru að fara til að vera hamingjusamari.
Og svo eru þessi áhrif í raun að gefa
okkur sumir dýpra hugsun.
>> Þannig að við skulum kíkja á hvað sameinast tegund er í raun allt um.
The kaldur hlutur er að sameina tegund er bara þetta.
Þetta er, aftur, það sem við höfum kallað sauðakóðanum, sauðakóðanum tilvera
English-eins og setningafræði.
Og einfaldleiki er konar heillandi.
>> Svo á inntak n þætti - svo sem þýðir bara, hér er fylki.
Það er got n hlutum í það.
Það er allt sem við erum að segja það.
>> Ef n er minna en 2, aftur.
Svo er það bara léttvæg mál.
Ef n er minna en 2, þá augljóslega er það 1 eða 0, en þá sem
er þegar raðað eða nonexistent, svo bara aftur.
Það er ekkert að gera.
Svo er það einfalt mál að reyta burt.
>> Annars höfum við þrjú skref.
Raða vinstri helming þætti, flokka rétt helmingur af the frumefni,
og þá sameina raðað helminga.
Hvað er áhugavert hér er að Ég er svona Punting, ekki satt?
Það er góður af hringlaga skilgreiningu þessum reiknirit.
Í hvaða skilningi er þetta reiknirit er skýring hringlaga?
>> Áhorfendur: [inaudible].
>> DAVID Malan: Já, flokkun reiknirit minn, tveir skrefum hans eru "tegund
eitthvað. "Og svo bidur spurning, vel, er það sem ég ætla að nota
að raða vinstri helming og rétt helmingur?
Og fegurð hér er að jafnvel þótt aftur, þetta er hugur-beygja
hluti hugsanlega er hægt að nota sama reiknirit til að raða vinstri helminginn.
>> En bíddu í eina mínútu.
Þegar þú ert að segja að raða vinstri helming, er það tveir
skref að fara að vera næst?
Við munum raða vinstri helmingi vinstri helmingi og rétt
helmingur af vinstri helming.
Fjandinn, hvernig raða ég þeim tveimur helminga eða fjórðunga, nú?
>> En það er allt í lagi.
Við höfum flokkun reiknirit hér.
Og jafnvel þó að þú gætir hafa áhyggjur fyrst er svona óendanlega
lykkja, er það hringrás sem er aldrei fara til enda - það er að fara að
enda þegar það gerist?
Einu sinni er n minna en 2.
Sem á endanum er að fara að gerast, því ef þú heldur helminga og
helminga í helminga þessar helminga, örugglega loksins að þú ert að fara að enda
upp með aðeins 1 eða 0 atriði.
Á hver benda, þetta reiknirit segir að þú ert búinn.
>> Þannig að raunverulegur galdur í þessu reiknirit virðist vera í
að stíga skrefið, samruna.
Það einfalda hugmynd bara sameina tvö hlutir, það er það sem er á endanum að fara
til að leyfa okkur að raða fylki af, segjum, átta þætti.
Þannig að ég hef átta fleiri streitu kúlur upp hér, átta stykki af pappír og einn
Google Glass -
sem ég fæ að halda.
>> [Hlátur]
>> DAVID Malan: Ef við gætum tekið átta sjálfboðaliðar, og við skulum sjá hvort við getum
spila þetta út, svo.
Vá, OK.
Tölvunarfræði er að fá gaman.
Allt í lagi.
Svo hvernig væri að þú þrjár, Stærsta hönd þarna.
Fjórir í bakinu.
Og hvernig væri að við munum gera þér þrjú í þessari röð?
Og fjórir í framan.
Svo þú átta, koma upp.
>> [Hlátur]
>> DAVID Malan: Ég er reyndar ekki viss hvað það er.
Er það streita kúlur?
Borðið lampar?
Efnið?
Netið?
>> OK.
Svo koma upp.
Sem langar -
halda á næstunni.
Við skulum sjá.
Og þetta setur þig í stað -
þú ert í stað einn.
Uh-ó, bíddu í eina mínútu.
1, 2, 3, 4, 5, 6, 7 - oh, good.
Allt í lagi, við erum góð.
Allt í lagi, svo allir hafa sæti, en ekki á Google Glass.
Leyfðu mér að biðröð þetta upp.
Hvað er nafn þitt?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Allt í lagi, þú færð að líta út eins og The Geek, ef það er í lagi.
Jæja, ég líka, ég geri ráð fyrir, fyrir aðeins augnablik.
Allt í lagi, í biðstöðu.
Við höfum verið að reyna að koma upp með a nota málið fyrir Google Glass, og við
hélt að það væri gaman bara að gera þetta þegar fólk er onstage.
Við munum taka heiminn frá sjónarhóli þeirra.
Allt í lagi.
Ekki líklega hvað Google ætlað.
Allt í lagi, ef þú dont 'hugur þreytandi þetta fyrir næstu óþægilega mínútur,
sem myndi vera dásamlegt.
>> Allt í lagi, þannig að við höfum hér á fjölbreytta þætti, og að array, eins og á
stykki af pappír í þessum fólkinu ' hendur, er nú óflokkað.
>> MICHELLE: Ó, það er svo skrýtið.
>> DAVID Malan: Það er ansi mikið af handahófi.
Og á aðeins augnablik, við erum að fara að reyna að innleiða Mergesort saman
og sjá hvar þessi lykill innsýn er.
Og bragð hér með sameiningu tagi er eitthvað sem við höfum ekki gert ráð fyrir enn.
Við þurfum í raun einhvers fleiri pláss.
Svo hvað er að fara að vera sérstaklega áhugavert um þetta er að þessi
krakkar eru að fara að flytja í kringum litla hluti, vegna þess að ég ætla að gera ráð fyrir að
það er auka array af plássi, segja, rétt fyrir aftan þá.
>> Svo ef þeir eru á bak við stól þeirra, það er annar array.
Ef þeir sitja hér, það er aðal array.
En þetta er auðlind sem við höfum ekki skuldsett svona langt með kúla
tegund, með tegund val, með Innsetningarröðun.
Muna síðustu viku, allir bara konar stokkuð á sínum stað.
Þeir vildu ekki nota allir viðbótar minni.
Við gerðum pláss fyrir fólk með færa fólk í kring.
>> Þannig að þetta er lykillinn innsýn líka.
Það er þetta málamiðlun, almennt í tölvunarfræði, auðlinda.
Ef þú vilt flýta eitthvað eins og tími, þú ert að fara að
að greiða verð.
Og einn af þeim verði er mjög oft rúm, the magn af minni eða harður
pláss sem þú ert að nota.
Eða, hreinskilnislega, að upphæð tíma forritari.
Hversu mikinn tíma það tekur þig, manna, til raunverulega framkvæma sumir fleiri
flókið reiknirit.
En í dag, að málamiðlun er tími og rúm.
>> Þannig að ef þú krakkar gætu bara halda upp þinn tölur svo við getum séð að þú ert
örugglega passa 4, 2, 6, 1, 3, 7, 8.
Excellent.
Þannig að ég ætla að reyna að orchestrate hlutum, ef þú krakkar geta bara
fylgja leiða minn hér.
>> Svo er ég að fara að innleiða, fyrst, Fyrsta skrefið í sauðakóðanum, sem er
á inntak n þætti, ef n er minna en 2, síðan aftur.
Vitanlega, það er ekki gilda, svo við fara.
Svo raða vinstri helming þætti.
Svo þýðir að ég ætla að einbeita mér athygli fyrir aðeins augnablik á þessum
fjórir krakkar hér.
Allt í lagi, hvað ég að gera næst?
>> Áhorfendur: Raða vinstri helminginn.
>> DAVID Malan: Svo nú þarf ég að raða vinstri helmingur þessara manna.
Því aftur, ætla til sjálfur að Markmiðið er að raða vinstri helminginn.
Hvernig gerir þú það?
Bara fylgja leiðbeiningunum, jafnvel þó að við erum að gera það aftur.
Svo raða vinstri helminginn.
Nú er ég flokkun Þessir tveir gaurar.
Hvað kemur næst?
>> Áhorfendur: Raða vinstri helminginn.
>> DAVID Malan: Raða vinstri helminginn.
Svo nú eru þetta, þetta sæti hér, er listi yfir stærð 1.
Og hvað er nafnið þitt aftur?
>> Princess Daisy: Princess Daisy.
>> DAVID Malan: Princess Daisy er hér.
Og svo hún er þegar raðað, því listinn er af stærð 1.
Hvað geri ég næst?
OK, aftur, vegna þess að þessi listi er stærð 1, sem er minna en 2.
Þá er það næsta skref?
Og nú þú ert að eins konar backtrack í huga þínum.
>> Raða rétt helming, sem er -
hvað er nafn þitt?
>> LINDA: Linda.
>> DAVID Malan: Linda.
Og svo hvað gerum við nú að Við hafa a listi af stærð 1?
>> Áhorfendur: Return.
>> DAVID Malan: Varlega.
Við aftur fyrst, og nú þriðja skref - og ef ég konar sýna það með
faðma tvö sæti nú, nú ég að sameina þessar tvær einingar.
Svo nú miður, þá þætti eru út af röð.
En það er þar sem samruna ferli byrjar að fá sannfærandi.
>> Þannig að ef þú krakkar gætu staðið upp fyrir bara stund, ég ætla að þú þarft, í
stund, að stíga á bak stólnum þínum.
Og ef Linda, því 2 er minni en 4, hví ekki
þú koma í kring fyrst?
Stay there.
Svo Linda, kemur þú í kring fyrst.
>> Nú í raun ef það er bara fylki við gátum bara færa hana í rauntíma
frá þessum stól því svæði.
Svo ímynda sér að tók stöðug nokkur skref 1..
Og nú -
en við þurfum að setja þig í í fyrsta staðsetning hér.
>> Og nú ef að þú gætir komið í kring, eins vel, við erum að fara að
vera í stað tveggja.
Og jafnvel þótt þetta er eins og það er taka a á meðan, hvað er gott núna er
að vinstri helmingur af vinstri helmingur er nú raðað.
Svo hvað var næsta skref, ef við nú baka lengra í sögunni?
>> Áhorfendur: Hægri helmingur.
>> DAVID Malan: Raða rétt helminginn.
Svo þú krakkar ert að gera þetta, eins og heilbrigður.
Svo ef þú gætir standa upp fyrir aðeins augnablik?
Og hvað er nafnið þitt?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, svo er Jess nú vinstri helmingur af hægri helming.
Og svo er hún listi af stærð 1.
Hún er augljóslega raðað.
Og nafn þitt aftur?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle er augljóslega listi af stærð 1.
Hún er þegar raðað.
Svo nú galdur gerist, samruna ferli.
Svo hver er að fara að koma fyrst?
Vitanlega Michelle.
Svo ef þú gætir komið í kring aftur.
Rýmið sem við höfum í boði fyrir hana núna er rétt á bak þessum stól hér.
Og nú ef þú gætir komið aftur eins og heilbrigður, við höfum nú að vera ljóst, tveir
helminga, hver stærð 2 -
og bara fyrir sakir lýsingu, ef þú gæti gert smá bili -
eitt eftir hálft hér, eina hægri helming hér.
>> Baka lengra í sögunni.
Hvaða skref er næst?
>> Áhorfendur: Sameina.
>> DAVID Malan: Svo nú verðum við að sameinast.
Svo allt í lagi, svo nú, sem betur fer, við bara leystur upp fjórum stólum.
Þannig að við höfum notað tvisvar eins mikið minni, en við getum gefið Flip-flopping milli
tvö fylki.
Svo sem fjöldi er að koma fyrst?
Svo Michelle, vitanlega.
Svo koma í kring og taka sætið hér.
Og þá er númer 2 augljóslega næst, svo þú kemur hingað.
Númer 4, númer 6.
Og aftur, jafnvel þó að það sé lítill hluti af gangandi ræða,
raunverulega, þetta gæti gerst í stað, með því að færa einn -
OK, vel spilað.
>> [Hlátur]
>> DAVID Malan: Og nú erum við í nokkuð góðri þjálfun.
The vinstri helmingur allra inntak hefur nú verið flokkaður.
Allt í lagi, svo þessir krakkar höfðu kostur á mínum -
hvernig var það á endanum allar stelpur á vinstri og allir strákar hægri?
>> OK, svo krakkar 'snúum.
Þannig að ég mun ekki ganga í gegnum þessum leiðbeiningum.
Við munum sjá hvort við getum sækja aftur sama sauðakóðanum.
Ef þú vilt fara á undan og standa upp, og þú krakkar, láta mig gefa þú the mic.
Sjá hvort þú getur ekki endurtaka það við gerðum bara hér á
hinum enda listanum.
Hver þarf að tala fyrst, byggt á reiknirit?
Svo útskýrt hvað þú ert að gera áður en þú gerir einhverjar fótur hreyfingar.
>> Ræðumaður 1: Allt í lagi, svo þar Ég er vinstri helmingur af
vinstri helming, aftur ég.
Ekki satt?
>> DAVID Malan: Gott.
>> Ræðumaður 1: Og svo -
>> DAVID Malan: Hver er The MIC fara næst?
>> Ræðumaður 1: Næsta númer.
>> Ræðumaður 2: Ég er rétt helmingur á vinstri hluta sem
vinstri helming, og ég aftur.
>> DAVID Malan: Gott.
Þú kemur aftur.
Svo nú er það næsta upp fyrir ykkur?
>> Ræðumaður 2: Við viljum sjá hver er minni.
>> DAVID Malan: Einmitt.
Við viljum að sameina.
Rýmið sem við erum að fara að nota til að sameina þú inn, jafnvel þó þeir séu
augljóslega raðað nú þegar, við erum að fara að fylgja sömu reiknirit.
Svo fer sem í aftur fyrst?
Sem 3, og síðan 7.
Og nú fer Mic að þessir krakkar, OK?
>> Ræðumaður 3: Ég er rétt helmingur af vinstri helming, og n mín er minna en
1, þannig að ég ætla bara að fara að fara -
>> DAVID Malan: Gott.
>> Ræðumaður 4: Ég er rétt helmingur af hægri helmingur hægri helming, og ég er
einnig einn maður, svo ég er fara til baka.
Svo nú erum við sameinast.
>> Ræðumaður 3: Svo við förum aftur.
>> DAVID Malan: Svo þú fara inn aftur.
Svo 5 fer fyrst, síðan 8.
Og nú áhorfendur, sem er stíga við verðum að nú trekkja
Til baka í huga okkar?
>> Áhorfendur: Sameina.
>> DAVID Malan: Sameina vinstri helming og hægri helmingur af upprunalegum vinstri helming.
Svo núna -
og bara til að gera þetta skýrar, gera smá pláss
milli þín tveir gaurar.
Svo nú er að það tveir listar, vinstri og hægri.
Svo hvernig gera við sameinast nú þú krakkar í framan sætaröð aftur?
>> 3. fer fyrst.
Þá 5., vitanlega.
Þá 7, og nú 8.
OK, og nú erum við?
>> Áhorfendur: Ekki gert.
>> DAVID Malan: Ekki gert, vegna þess að Vitanlega, það er eitt skref eftir.
En aftur, ástæðan ég er að nota þetta hrognamál eins og "til baka í huga þínum,"
það er vegna þess að það er í raun hvað er að gerast.
Við erum að fara í gegnum öll þessi skref, en við erum konar hlé fyrir
stund, köfun dýpra inn í reiknirit, stansa um stund,
köfun dýpra inn í reiknirit og nú verðum við að raða á baka í okkar
huga og losa öllum þessum lögum sem við höfum svona sett í bið.
>> Svo nú höfum við tvo lista af stærð 4.
Ef þú krakkar gætu staðið upp eitt síðasta skipti og gera smá pláss hér til
gera ljóst að þetta er vinstri helmingur af upprunalegu, the
hægri hluta upprunalega.
Hver er fyrsta talan sem við þarf að draga inn aftur?
Michelle, auðvitað.
>> Þannig að við setjum Michelle hér.
Og hver hefur númer 2?
Númer 2 kemur aftur eins og heilbrigður.
Númer 3?
Excellent.
Númer 4, númer 5, númer 6, númer 7, og númer 8.
>> OK, svo það var eins og a einhver fjöldi af skrefum, fyrir viss.
En nú skulum sjá hvort við getum ekki staðfest konar innsæi að þetta
reiknirit grundvallaratriðum, sérstaklega þar sem n fær mjög stór, eins og við höfum séð
með fjör, er grundvallaratriðum hraðar.
Svo ég halda þetta reiknirit, í versta málið og jafnvel í besta tilfelli,
er stór O n sinnum log n.
Það er, það er einhver þáttur um þetta reiknirit sem tekur n skrefum, en
það er annar þáttur einhversstaðar í sem endurtekning, að lykkja, sem
tekur log n skrefum.
Getum við sett fingur okkar á hvað þeir tvær tölur eru að vísa til?
Jæja, þar sem -
Hvar Mic fara?
>> Ræðumaður 1: Myndi þig n vera brjóta okkur upp í tvo -
deila með tveimur, í meginatriðum.
>> DAVID Malan: Einmitt.
Hvenær við sjáum í hvaða reiknirit svona langt, það hefur verið þetta mynstur
deila, deila, deila.
Og það er yfirleitt minnkað eitthvað sem er
lógaritmískum, skráðu þig stöð 2..
En það gæti virkilega verið nokkuð, en tengja stöð 2.
>> Nú hvað um n?
Ég get séð að við skipt konar þig krakkar - skipt þig, skipt þér,
skipt þig, skipt þig.
Hvar er endirinn koma frá?
>> Svo það er samruna.
Vegna hugsa um það.
Þegar þú sameina átta manns saman, þar helmingur af þeim eru sett af fjórum
og hinn helmingurinn eru önnur setja af fjórum, hvernig gera þú fara
um að gera að sameina?
Jæja, þið gerði það nokkuð innsæi.
>> En ef ég gerði í staðinn aðeins meira methodically, gæti ég hef bent á
að leftmost manneskja fyrst með vinstri minn hönd, benti á lengst til vinstri mann
þess hluta með hægri hendi minni, og bara síðar gekk í gegnum
lista, bendir á minnstu frumefni hvert skipti, færa fingur mína yfir og
yfir og þarf allan listann.
En hvað er lykillinn um þetta samruna aðferð er ég að bera saman þessar pör
staka.
Frá hægri hluta og frá vinstri helmingur, ég aldrei einu sinni backtracking.
>> Svo sameinast sjálft er að taka ekki meira en n skrefum.
Og hversu oft gerði ég að gera það að sameina?
Jæja, ekki meira en n, og við bara sá að með endanlegri sameiningu.
Og svo ef þú gerir eitthvað sem tekur log n skrefum n sinnum, eða öfugt,
það er að fara að gefa okkur n sinnum log n.
>> Og hvers vegna er þetta betur?
Jæja, ef við vitum nú þegar að skrá þig n er betri en n - ekki satt?
Við sáum í tvöfaldur leit, símaskrána dæmi, log n var ákveðið
betri en línulegt.
Svo það þýðir n sinnum log n er örugglega betur en n sinnum annað
n, AKA n ferningur.
Og það er það sem við teljum að lokum.
>> Svo stór umferð lófaklapp, ef við gátum, fyrir þessar krakkar.
>> [Applause]
>> DAVID Malan: og skilnaði gjafir - þú getur haldið tölur,
ef þú vilt.
Og skilnaði gjöf þín, eins og venjulega.
Ó, og við munum senda þér myndefni, Michelle.
Þakka þér.
Allt í lagi.
Hjálp sjálfur til streitu boltanum.
>> Og láta mig draga upp, í millitíðinni, vinkona Rob Bowden að bjóða
nokkuð mismunandi sýn á þetta, þar sem þú getur hugsa um þessar
skref gerast í nokkru mismunandi hátt.
Í staðreynd, the setja-upp fyrir það Rob er um til að sýna okkur ráð sem við höfum
þegar gert er að deila upp af stór listi í átta litlum listum,
hver af stærð 1.
>> Þannig að við erum að breyta því sauðakóðanum A svolítið bara til að raða í fá á
Kjarni hugmynd um hvernig sameiningu verk.
En gangi tíma hvað hann er að fara að gera er enn
að fara að vera sú sama.
Og aftur, setja upp hér er sú að hann er hafin með átta lista af stærð 1.
Svo þú hefur misst hluta þar sem hann er í raun gert að log n, log n, log n
deila um inntak.
>> [Vídeó spilun]
>> -Það er það fyrir skref eitt.
Fyrir sporinu ítrekað sameinast pör af listum.
>> DAVID Malan: Hm.
Aðeins hljóð kemur út af tölvunni minni.
Við skulum reyna þetta aftur.
>> -Bara geðþótta velja hvaða - nú höfum við fjóra lista.
Læra áður.
>> DAVID Malan: Það sem við förum.
>> -Merging 108 og 15, enda við upp með lista 15, 108.
Sameiningu 50 og 4, við endað með 4, 50.
Sameiningu 8 og 42, við endað með 8, 42.
Og sameina 23 og 16, við endar með 16, 23.
>> Nú allir listar okkar eru stærð 2.
Takið eftir að hver af fjórir listar er raðað.
Þannig að við getum byrjað að sameina pör af lista aftur.
Að sameina 15 og 108 og 4 og 50, við Fyrsta taka 4, þá 15, þá
50, þá 108.
Sameina 8, 42 og 16, 23, taka við fyrst 8, þá 16, þá 23,
þá 42..
>> Svo nú höfum við bara tveir listar stærð 4, sem hver um sig er vel flokkað.
Svo nú erum við að sameina þessar tvær listum.
Fyrst, við tökum 4, þá erum við að taka á 8, þá erum við að taka 15, þá 16, þá
23, þá 42, þá 50, þá 108.
>> [END vídeó spilun]
>> DAVID Malan: Aftur, tilkynning, aldrei hann snert á tilteknu bolla oftar en einu sinni
eftir að fara út fyrir hann.
Svo hann er aldrei endurtaka.
Svo hann er alltaf að færa til hliðar, og það er þar sem við fengum n okkar.
>> Hvers vegna ekki láta mig draga upp einn fjör sem við sáum fyrr, en í þetta skiptið
með áherslu eingöngu á sameiningu tagi.
Leyfðu mér að fara á undan og zoom í á þetta hér.
Fyrst láta mig velja af handahófi inntak, stækka þetta, og þú getur raða á sjá
hvað við tók sem sjálfsagðan hlut, fyrr, sameinast tegund er í raun að gera.
>> Svo eftir því að þú færð þessi helminga eða þessar fjórðu eða þessir áttundu hlutar sem
vandamál sem allt í einu byrja að taka góða mynd.
Og svo að lokum, að sjá þig á enda sem Bam,
allt er sameinað saman.
>> Svo þetta eru bara þrír mismunandi tekur á sömu hugmynd.
En lykillinn innsýn, rétt eins og skipta og sigra í fyrsta bekk,
var að við ákváðum að einhvern veginn skipta vandamálið í eitthvað stórt, í
eitthvað svoleiðis eins í anda, en minni og minni og minni
og minni.
>> Nú annað skemmtileg leið til að raða á hugsa um þessum, jafnvel þótt það sé ekki
fara að gefa þér sama innsæi skilningur, er
Eftirfarandi fjör.
Þannig að þetta er myndband sem einhver setti saman sem tengist mismunandi
hljóðum með mismunandi rekstri innsetning tagi, fyrir sameiningu tagi, og
fyrir a par af öðrum.
Svo í augnablikinu, ég er að fara að lemja Spila.
Það er um eina mínútu löng.
Og jafnvel þó að þú getur enn séð mynstur að gerast, í þetta sinn sem þú getur
einnig heyra hvernig þessi reiknirit eru framkvæma á annan hátt og með
nokkuð mismunandi mynstur.
>> Þetta er innsetning tagi.
>> [Tónar LEIKA]
>> DAVID Malan: Það aftur er að reyna að setja hver þáttur
inn þar sem það tilheyrir.
Þetta er kúla tegund.
>> [Tónar LEIKA]
>> DAVID Malan: Og þú getur raða á líður hversu tiltölulega lítið að vinna það er að gera
á hverju skrefi.
Þetta er það sem tediousness hljómar eins.
>> [Tónar LEIKA]
>> DAVID Malan: Þetta er val tagi, þar við að velja frumefni sem við viljum með því að
fara í gegnum aftur og aftur og aftur og setja það í upphafi.
>> [Tónar LEIKA]
>> DAVID Malan: Þetta er steypa tegund, sem þú getur í raun að byrja að líða.
>> [Tónar LEIKA]
>> [Hlátur]
>> DAVID Malan: Eitthvað sem heitir dvergur tegund, sem við höfum ekki horft á.
>> [Tónar LEIKA]
>> DAVID Malan: Svo láta mig sjá, nú, annars hugar eins og þú ert vonandi af
tónlist, ef ég get miði lítið hluti af stærðfræði hér.
Þannig að það er Fjórða leiðin sem við getum hugsa um hvað það þýðir að þetta
aðgerðir til að vera hraðari en sjálfur að við höfum séð áður.
Og ef þú ætlar að koma á námskeiðið frá A stærðfræði bakgrunnur, þú
raunverulega vita kannski nú þegar að þú getur smellu inn orð á þessari tækni -
þ.e. endurkvæmni, fall sem kallar einhvern veginn sig.
>> Og aftur, muna að Mergesort sauðakóðanum var endurkvæma í skilningi
að eitt af skrefum Mergesort skips var að hringja svona -
það er, sjálft.
En sem betur fer, vegna þess að við haldið starf tegund, eða sameina flokka,
sérstaklega á minni og minni og minni lista, loksins við
botninum þökk hvað við munum kalla grunn tilfelli, the harður-dulmáli mál sem
sagði að ef listinn er lítið, minna en 2 í því tilfelli, bara aftur strax.
Ef við ekki hafa það sérstaka mál, sem reiknirit myndi aldrei botn út,
og þú myndi örugglega fá inn í Infinite Loop sannarlega að eilífu.
>> En geri ráð fyrir að við vildum nú setja nokkrar tölur um þetta, aftur, með n
og stærð inntak.
Og ég vildi spyrja þig, hvað er heildartíminn þátt í
gangi Mergesort?
Eða almennt, hvað er kostnaður við það í tíma?
>> Jæja það er nokkuð auðvelt að mæla það.
Ef n er minna en 2, þann tíma sem í flokka n þætti,
þar sem n er 2, er 0.
Vegna þess að við aftur bara.
Það er engin vinna til að gera.
Nú öllum líkindum, kannski er það eitt skref eða tvö skref til að reikna út hversu mikið af
vinna, en það er nógu nálægt til 0 að Ég ætla bara að fara að segja engin vinna er
krafist ef listinn er svo lítill að uninteresting.
>> En þetta mál er áhugavert.
Endurkvæma Málið var útibú The sauðakóðanum sem sagt annað, flokka
vinstri helming, raða rétt helmingur, sameina tvo helminga.
Nú hvers vegna er þetta tjáning tákna sem kostnað?
Jæja, T í n þýðir bara tími til að raða n þætti.
Og þá á hægri hönd hlið af the jafngildir skilti þarna, T á n skipt
eftir 2 er vísað til kostnaðar við hvað?
Flokkun vinstri helminginn.
Hin T af n deilt með 2 er væntanlega að vísa til kostnaðar við
raða rétt helminginn.
>> Og þá plús n?
Er samruni.
Vegna þess að ef þú hefur tvo lista, einn af stærð n yfir 2 og annar af stærð n
yfir 2, þú þarft að í raun snerta hver af þessum þáttum, rétt eins og Rob
snert hvert bolla, og bara eins og við bent á hvert af
sjálfboðaliðar á sviðinu.
Svo er n kostnað af samruna.
>> Nú því miður, þetta uppskrift er einnig sjálft endurkvæma.
Svo ef spurði, ef n er, segjum, 16, ef það er 16 manns á sviðinu
eða 16 bollar í the vídeó, hversu margir alls skref tekur það að raða þeim
með sameiningu tagi?
Það er í raun ekki augljóst svar, því nú þú þarft að raða á
endurkvæmur svara þessari formúlu.
>> En það er allt í lagi, vegna þess að láta mig leggja að við gera eftirfarandi.
Tíma þátt til að raða 16 manns eða 16 bollar er að fara að vera fulltrúa
almennt T af 16.
En það jafngildir, í samræmi við okkar fyrri uppskrift, 2 sinnum sú upphæð
tíma það tekur að raða 8 bollar auk 16.
Og aftur, plús 16 er kominn tími til að sameinast, og tvisvar sinnum T á 8 er
tími til að raða vinstri helming og hægri helmingur.
>> En aftur, þetta er ekki nóg.
Við verðum að kafa í dýpri.
Þetta þýðir að við verðum að svara spurning, hvað er T af 8?
Jæja T af 8 er bara 2 sinnum T á 4 plús 8.
Jæja, hvað er T í 4?
T á 4 er bara 2 sinnum T á 2 plús 4.
Jæja, hvað er T í 2?
T af 2 er bara 2 sinnum T á 1 plús 2.
>> Og aftur, við erum konar að fá fastur í þessari lotu.
En það er um að lemja það svokallaða grunn tilfelli.
Vegna þess að það er T 1, gerði við kröfu?
0.
Svo nú loksins getum við vinna aftur á bak.
>> Ef T 1. er 0, ég get nú farið aftur upp einn lína til þennan gaur hérna, og ég get
stinga í 0 fyrir T frá 1..
Svo það þýðir að það jafngildir 2 sinnum núll, annars þekkt sem 0, auk 2.
Og svo er að allt tjáning 2..
>> Nú ef ég taka T í 2, sem svar er 2, stinga því inn í miðju línu, T
af 4, sem gefur mér 2 sinnum 2 plus 4, þannig að 8.
Ef ég stinga þá í 8 til fyrri lína, sem gefur mér 2 sinnum 8, 16.
Og ef við höldum áfram þá að með 24, að bæta í 16, fáum við loksins
gildi 64..
>> Nú þegar í sjálfu konar talar ekkert í n merki, the
stór O, the ómega sem við höfum verið að tala um.
En það kemur í ljós að 64 er örugglega 16, the stærð af the inntak,
tengja stöð 2 af 16.
Og ef þetta er svolítið framandi, bara hugsa til baka, og það mun koma aftur
til þín á endanum.
Ef þetta er að tengja stöð 2, það er eins og 2 hækkuð í það sem gefur þér 16?
Ó, það er 4, svo það er 16 sinnum 4..
>> Og aftur er það ekki máli ef þetta er tegund af hazy minni núna.
En nú, að taka á trú að 16 Log 16 er 64.
Og svo reyndar með þessari einföldu Sanity athuga, höfum við staðfest -
en ekki reynst formlega -
að keyra tími sameinast tegund er örugglega n log n.
>> Svo ekki slæmt.
Það er örugglega betra en að reiknirit sem við höfum séð hingað til, og
það er vegna þess að við höfum skuldsett, einn, tækni sem kallast endurkvæmni.
En meira áhugavert en það, sem hugmyndin að deila og sigra.
Aftur, sannarlega viku 0 efni sem jafnvel nú er endurtekin í
meira sannfærandi hátt.
>> Nú skemmtilegur lítill æfa, ef þú hefur aldrei gert þetta - og þú sennilega
myndi ekki hafa, því svona eðlilegt fólk held ekki að gera þetta.
En ef ég fer á google.com og ef Ég vil læra eitthvað um
endurkvæmni, Enter.
>> [Hlátur]
[MEIRA hlátur]
DAVID Malan: Bad brandari hægt að breiða út.
[Hlátur]
DAVID Malan: Bara ef, það er þarna.
Ég vissi ekki að stafa það rangt, og það er brandari.
Allt í lagi.
Útskýra það að fólk við hliðina á þér ef það hefur ekki alveg smellt bara ennþá.
En endurkvæmni, almennt, vísar til að vinna að virka starf
sig, eða fleiri almennt, deila með vandamál í eitthvað sem hægt er að
leyst piecemeal með því að leysa eins fulltrúa vandamál.
>> Breyting gír Jæja, við skulum fyrir aðeins augnablik.
Við eins og að enda á ákveðnum cliffhangers, þannig að við skulum byrja að setja
sviðið, í nokkrar mínútur, á mjög einfaldri hugmynd -
sem á að skipta tvo þætti, ekki satt?
Öll þessi reiknirit sem við höfum verið að tala um á síðustu tveimur
fyrirlestrar sér sumir konar skipta.
Í dag var visualized af þeim fá upp úr stólum sínum og
ganga um, en í kóða, við vildi bara taka stak úr einu fylki
og plop það í annað.
>> Svo hvernig við förum að gera þetta?
Jæja, láttu mig fara á undan og skrifa a fljótur program hér.
Ég ætla að fara á undan og gera þetta á eftirfarandi hátt.
Við skulum kalla þetta -
Hvað viljum við að kalla þetta einn?
>> Reyndar ekki.
Leyfðu mér að baka.
Ég vil ekki að gera það cliffhanger enn.
Það mun spilla gaman.
Skulum gera þetta í staðinn.
>> Segjum að ég vil skrifa smá forrit og það nær nú þetta
Hugmyndin um endurkvæmni.
Ég fékk svona á undan mér þar.
Ég ætla að gera eftirfarandi.
>> Fyrst, eru fljótleg af venjulegu io.h, og jafnframt fela í sér að cs50.h.
Og þá ætla ég að fara á undan og lýsa int helstu ógilt
á hefðbundinn hátt.
Ég sá að ég hef misnamed skrána, svo láta mig bæta bara. c eftirnafn hér svo
að við getum þýða það almennilega.
Byrja á þessum valkosti.
>> Og virka ég vil skrifa, alveg einfaldlega er, sá sem spyr
notandi fyrir a tala og þá bætir upp allar tölur á milli að
númer og segja, 0.
Svo fyrst ég ætla að fara á undan og lýsa INT n.
Þá vil ég afrita nokkur númer sem við höfum notað um tíma.
Þó eitthvað sé satt.
Ég kem aftur til að í smástund.
>> Hvað vil ég að gera?
Mig langar að segja printf jákvæð heiltala vinsamlegast.
Og þá ætla ég að segja n fær fá int.
Svo aftur, sumir boilerplate númer sem við höfum notað áður.
Og ég ætla að gera þetta á meðan n er minna en 1.
Þannig að þetta mun tryggja að notandinn gefur mér jákvæð heiltala.
>> Og nú ætla ég að gera eftirfarandi.
Mig langar að bæta upp allar tölur á milli 1 og og n, eða 0 og n,
equivalently, til að fá heildar summa.
Svo stóra Sigma tákn sem þú gætir muna.
Þannig að ég ætla að gera þetta með fyrsta starf fall kallast Sigma,
liggur það í n, og þá ætla ég að segja printf, svarið er rétt þar.
>> Svo í stuttu máli, ég fæ og int frá notandanum.
Ég tryggja að það er jákvætt.
Ég lýsi breytilega heitir svar tegund int og geyma í henni aftur
verðmæti Sigma, sem liggur í N sem inntak.
Og þá er ég að prenta út það svar.
>> Því miður, jafnvel þó að Sigma hljóð eins og eitthvað sem gæti verið í
The math.h skrá, yfirlýsing þess, það er í raun ekki.
Svo er það í lagi.
Ég get framkvæma þetta sjálfur.
Ég ætla að framkvæma aðgerð sem kallast Sigma, og það er að fara að taka
breytu -
skulum kalla bara það m, bara svo það er öðruvísi.
Og svo upp hér, ég ætla að segja, vel, ef m er minna en 1 - þetta er
mjög uninteresting program.
Þannig að ég ætla að fara á undan og strax aftur 0.
Það bara ekki skynsamleg að bæta upp alla tölurnar milli 1 og m ef m
er sjálft 0 eða neikvæð.
>> Og þá ætla ég að fara á undan og gera þetta mjög iteratively.
Ég ætla að gera þessa tegund af gamla skólanum, og ég ætla að fara á undan
og segja að ég ætla að lýsa summu til að vera 0.
Þá er ég að fara að hafa á fyrir lykkja á int -
og láta mig gera það til að passa starfsemi okkar dreifingu kóða, svo þú hafa a afrit
heima. int i fær 1 á allt að i er minna en eða jafnt og m.
ég plús plús.
Og þá inni í þessu fyrir lykkju -
við erum næstum þarna -
summan fær summan plús 1.
Og þá er ég að fara að skila summa.
>> Svo ég gerði þetta fljótt, alveg vísu.
En aftur, helsta hlutverk er nokkuð einfalt, byggt á númerið við höfum
skrifað svona langt.
Notar tvöfalda lykkju til að fá jákvæð int frá notandanum.
Ég fara þá að int til nýtt hlutverk kallað Sigma, að kalla það, aftur, n.
Og ég að geyma aftur gildi, svarið frá svarta kassanum nú
þekktur sem Sigma, í breytu kallað svar.
Þá vil ég prenta það.
>> Ef við höldum áfram nú söguna, hvernig er Sigma framkvæmd?
Ég að leggja til að framkvæma eins og hér segir.
Fyrst, smá villa-stöðva til að tryggja að notandi er ekki
Messías með mér og farið í nokkur neikvæð eða 0 virði.
Þá vil ég lýsa yfir breytu sem heitir summa og setja það í 0.
>> Og nú er ég að byrja að fara frá ég er jafnt 1 alla leið upp að og að meðtöldum m,
vegna þess að ég vil að fela alla tölur frá eitt til m, innifalið.
Og inni í þetta fyrir lykkju, ég bara summan fær hvað sem það er nú, auk
Gildi i.
Að viðbættu virði i.
>> Sem innskot, ef þú hefur ekki séð þetta áður, það er einhver nokkur dæmi um setningarleg sykur
fyrir þessari línu.
Ég get umrita þetta sem plús jafngildir i, bara til að spara mér nokkrum mínútum
og til að líta svolítið kælir.
En það er allt.
Það er virkni sama.
>> Því miður, þetta númer er ekki að fara að safna saman enn.
Ef ég hlaupa gera Sigma 0, hvernig am Ég ætla að fá öskraði á?
Hvað er það að fara að ekki eins?
>> Áhorfendur: [inaudible].
>> DAVID Malan: Já, ég vissi ekki lýsa virka upp efst, ekki satt?
C er góður af heimskur, þannig að það bara gerir það sem þú segir að hún geri, og þú
að gera það í þessari röð.
Og svo ef ég högg inn hér ætla ég að fá viðvörun um Sigma óbeina
yfirlýsingu.
>> Ó, ekki vandamál.
Ég get farið upp á toppinn, og ég get segja, allt í lagi, bíddu í eina mínútu.
Sigma er fall sem skilar int og það gerir ráð fyrir að
int sem inntak, semíkommu.
Eða ég gæti sett alla virka hér að ofan helstu, en almennt, myndi ég
mæli gegn því, vegna þess að það er gott að hafa ávallt helstu efst svo
þú getur kafa rétt í og ​​vita hvað program er að gera með því að lesa helstu fyrst.
>> Svo nú láta mig hreinsa skjáinn.
Endurgerð Sigma 0.
Allt virðist kíkja.
Leyfðu mér að hlaupa Sigma 0.
Jákvæð Inter.
Ég skal gefa það fjölda 3. að halda það einfalt.
Svo sem ætti að gefa mér 3 plús 2 plus 1, þannig að 6.
Sláðu og örugglega ég fá 6.
>> Ég get gert eitthvað stærra -
50, 12, 75.
Rétt eins snertir, ætla ég að gera eitthvað fáránlegt eins og mjög stór
númer, Ó, að raunverulega í uppnámi út -
ha, ég held ekki það er rétt.
Við skulum sjá.
Skulum raunverulega skipta með það.
>> Það er vandamál.
Hvað er að gerast?
The merkjamál er ekki svo slæmt.
Það er samt línuleg.
Whistling er góð áhrif, þó.
Hvað er að gerast?
>> Ekki viss um að ef ég heyrði það.
Svo kemur í ljós - og þetta er eins og til hliðar.
Þetta er ekki algerlega að því Hugmyndin um endurkvæmni.
Það kemur í ljós, vegna þess að ég er að reyna að tákna svo stór tala, mest
líklega það er verið að mistúlka af C sem ekki jákvæð tala,
en neikvæð tala.
>> Við höfum ekki talað um þetta, en það reynist það eru neikvæðar tölur
í heiminum í viðbót að jákvæðar tölur.
Og leið sem þú getur tákna neikvæð tala
raun er, þú nota einn sérstaka hluti til að sýna
jákvæð yfir neikvæð.
Það er lítið flóknara en það, en það er grundvallar hugmynd.
>> Svo því miður, ef C er ruglingslegt einn af þeim bitum sem í raun þýðir,
ó, þetta er neikvæð tala, lykkja mitt hér, til dæmis, er í raun aldrei
fara að segja.
Þannig að ef ég væri í raun prentun eitthvað aftur og aftur, myndum við
sjá í heild einhver fjöldi.
En aftur, þetta er að auki the benda.
Þetta er í raun bara eins konar vitsmunalegum forvitni sem við munum koma
aftur að lokum.
En nú, þetta er rétt framkvæmd ef við gerum ráð fyrir að
notandi mun veita ints að passa innan ints.
>> En ég halda því fram að þetta númer, hreinskilnislega, mætti ​​gera svo miklu meira einfaldlega.
Ef markmiðið hendi er að taka númer eins m og bæta upp allt í
tölur á henni og 1, eða öfugt á milli 1 og það, kröfu I
sem ég get fengið lánað þessa hugmynd að sameina raða átti, sem var að taka vandamál
af þessari stærð og deila honum í eitthvað minni.
Kannski ekki helminginn, en minni en representatively sama.
Sama hugmynd, en minni vandamál.
>> Þannig að ég er í raun - Leyfðu mér að spara þessa skrá með aðra útgáfu númer.
Við munum kalla þetta útgáfu 1 stað þess að 0.
Og ég halda því fram að ég get í raun reimplement þetta í þessari tegund af
hugur-beygja hátt.
>> Ég ætla að láta hluta af því einn.
Ég ætla að segja ef m er minna en eða jafnvel jafnt og 0 -
Ég ætla bara að fara að vera svolítið meira anal að þessu sinni
með stöðva villa mína -
Ég ætla að fara á undan og aftur 0.
Þetta er handahófskennt.
Ég er bara einfaldlega að ákveða hvort notandi gefur mér neikvæð tala, ég
aftur 0, og þeir ættu að hafa lesið skjölin nánar.
>> Annað -
taka eftir hvað ég ætla að gera.
Annars er ég að fara að skila m plús -
hvað er sigma m?
Jæja, sigma m plús m mínus 1, plús m mínus 2, plús m mínus 3.
Ég vil ekki að skrifa öll þessi út.
Af hverju ekki ég bara Punt?
Endurkvæmur kalla mig með örlítið minni vandamál, semíkommu,
og kalla það einn dag?
>> Ekki satt?
Nú hér líka, gætir þú fundið eða hafa áhyggjur að þetta er óendanlega lykkju sem ég er
Örvandi, þar sem ég er að innleiða Sigma með því að kalla Sigma.
En það er fullkomlega í lagi, vegna þess að ég hélt undan bætt hvaða línur?
>> Áhorfendur: [inaudible].
>> DAVID Malan: 23-26, sem er ef ástand mitt.
Vegna þess að það er gott um Frádráttur hér, því ég halda
fötlun sigma minni vandamál, minni vandamál, minni - það er ekki
helmingur the stærð.
Það er bara barn skref minni, en það er allt í lagi.
Vegna lokum munum við vinna leið okkar niður í 1 eða 0.
Og þegar við högg 0, Sigma er ekki fara að kalla sig lengur.
Það er að fara strax aftur á 0.
>> Svo áhrif, ef þú konar vindur þetta upp í huga þinn, er að bæta m plús
m mínus 1, auk m mínus 2, plús m mínus 3, auk punktur, punktur, punktur, m mínus
m, að lokum að gefa þér 0, og áhrif er að lokum að bæta öllum
þetta saman.
Þannig að við höfum ekki, með endurkvæmni, leysa vandamál sem við
gat ekki leyst áður.
Reyndar útgáfa 0 af þessu, og hvert vandamál hingað til, hefur verið leysanlegt
með bara að nota fyrir lykkjur eða á meðan lykkjur eða svipuð býr.
>> En endurkvæmni, eflaust ég, gefur okkur aðra leið til að hugsa um
vandamál, þar ef við getum tekið vandamál, skipta því frá eitthvað
nokkuð stór í eitthvað nokkuð minni, halda ég að við getum leyst það
kannski svolítið meira glæsilegur í skilmálar af hönnun, með minna númeri,
og kannski jafnvel leysa vandamál sem myndi vera erfiðara, eins og við munum að lokum
sjá, leysa eingöngu iteratively.
>> En cliffhanger sem ég gerði langar að yfirgefa okkur á var þetta.
Leyfðu mér að fara á undan og opna upp skrá úr -
reyndar, láta mig fara og gera þetta alvöru hratt.
Leyfðu mér að fara á undan og leggja eftirfarandi.
Meðal kóða dag er þetta skrá hér.
Þessi maður hér, noswap.
>> Þannig að þetta er heimskur lítill forrit sem Ég þeyttum upp þessi krafa til gera
eftirfarandi.
Í helstu, lýsir það fyrst að int heitir x og gefur það
verðmæti 1.
Þá segir það að int y og gefur það gildi 2.
Þá prentar það út hvað x og y er.
Þá segir það, skipta, punktur punktur punktur.
>> Þá segist hann vera að hringja aðgerð kallað skipti, sem liggur í x og
Y, þá hugmynd sem er að vonandi x og y mun koma aftur
öðruvísi, hið gagnstæða.
Þá kröfu skipti!
með upphrópunarmerki.
Þá prentar það út x og y.
>> En það kemur í ljós að þetta er mjög einföld sýning niður
hér er í raun þrjótur.
Jafnvel þó að ég er að lýsa yfir tímabundið breyta og tímabundið setja í
það, þá er ég reassigning að þá er gildið b -
sem finnst sanngjarnt, vegna þess að ég hef vistuð afrit af í afleysingamanneskja.
Þá er ég að uppfæra b á jafn hvað var í afleysingamanneskja.
Þessi tegund af leikur skel flytja í b-og b-inn að því að nota þetta
miðju-maður heitir afleysingamanneskja finnst fullkomlega sanngjarn.
>> En ég halda því fram að þegar ég keyra þetta kóða, eins og ég geri núna -
láta mig fara á undan og límdu hana í hér.
Ég kalla þetta noswap.c.
Og eins og nafnið gefur til kynna, þetta er ekki að fara að vera rétt program.
Gerðu noswap. / Engin skipti.
x er 1, y er 2, skipta um, skipti.
x er 1, y er 2..
Þetta er í grundvallaratriðum rangt, jafnvel þótt þetta virðist fullkomlega
sanngjarnt að mér.
Og það er ástæða, en við erum ekki fara að koma í ljós ástæðu bara ennþá.
>> Fyrir nú seinni cliffhanger ég vildi að yfirgefa þig með er þetta, sem
tilkynning af tegund á afsláttarmiða þau.
Nýsköpun okkar með seint daga á þessu ári hefur valdið a non-léttvæg númer
spurningum, sem var ekki ætlun okkar.
Ætlunin þessara afsláttarmiða númerin, þar ef þú hluti af vandamálinu
setja snemma, þannig að fá auka dag, var virkilega til að hjálpa ykkur að hjálpa
sjálfur byrja snemma, flokka af því incentivizing þig.
Hjálpar okkur að dreifa álaginu yfir skrifstofa klst betur þannig að
það er tegund af vinna-vinna.
>> Því miður, held ég leiðbeiningar mínum hafa ekki verið, hingað til, mjög skýr, svo
Ég fór aftur um helgina og uppfærð The sérstakur í stærri, bolder texta
útskýra skotum eins og þessir.
Og bara til að segja það meira opinberlega, með vanræksla, vandamál setur eru vegna Fimmtudagur
á hádegi, og á kennsluáætlun.
Ef þú byrjar snemma, klára hluta af vandamálið sett með miðvikudag klukkan 12:00
PM, sá hluti sem snýr að afsláttarmiða kóða, hugmyndin er að þú geta lengja
Frestur fyrir the P sett til föstudagsins.
Það er, hluti af örlítið hluti af P sett miðað við það sem venjulega er
stærri vandamál, og þú kaupir sjálfur auka dag.
Aftur fær það þig til að hugsa um vandamálið sett, fær þig til
skrifstofa klst fyrr.
En númer afsláttarmiða vandamálið er enn krafist, jafnvel ef þú ekki senda það.
>> En meira compellingly er þetta.
(STAGE hvísl) Og þessir gott fólk að fara snemma eru ađ sjá eftir því.
Eins eru gott fólk á svölunum.
Ég afsökunar fyrirfram að fólkinu á svalir ástæðum sem verður
hreinsa í aðeins augnablik.
>> Þannig að við erum lánsöm að hafa einn af Fyrrum CS50 er höfuð kennslu félagar á
fyrirtæki sem heitir dropbox.com.
Þeir hafa mjög ríkulega gefið sem afsláttarmiða kóða hér fyrir þennan mikið pláss,
sem er upp úr venjulega 2 gígabæta.
Svo það sem ég hélt að við myndum gera á þessu Lokastaða í huga er að gera a hluti af a uppljóstrun,
þannig að í aðeins augnablik, munum við sýna sigurvegari og hver hefur afsláttarmiða
númer sem þú getur þá farið til þeirra website, slá það í, og voila, fá
allt miklu meira Dropbox pláss fyrir þinn tæki og persónulegum skrám.
>> Og fyrst, sem langar til að taka þátt í þessa teikningu?
OK, nú gerir það enn meira gaman.
Sá sem fær þessa 25-gígabæti afsláttarmiða kóða - sem er langt
meira sannfærandi en seint dagar nú, kannski -
er sá sem situr ofan á sæti draga undir sem er
að afsláttarmiða númer.
Þú getur nú að líta undir sæti draga þinn.
>> [Vídeó spilun]
>> -Einn, tveir, þrír.
>> [Öskrandi]
>> -Þú færð bíl!
Þú færð bíl!
>> DAVID Malan: Við munum sjá þér á miðvikudag.
>> -Þú færð bíl!
Þú færð bíl!
>> DAVID Malan: Svalir fólkinu, koma niður hér að framan,
þar sem við höfum aukahlutir.
>> -Allir fær bíl!
Hjá öllum bíl!
>> [END vídeó spilun]
>> Sögumaður: Á næsta CS50 -
>> Ræðumaður 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [UKELELE Leikrit]