[Powered by Google Translate] [3. nädal, Jätkub]
>> [David J. Malan - Harvardi Ülikool]
>> [See on CS50. - CS50.TV]
>> Hea küll. Tere tulemast tagasi. See on CS50 ja see on lõpuks 3. nädal.
>> Nii neile võõras, eelmisel aastal Harvardi käivitas mida nimetatakse Innovation Lab,
või i-lab, mis on suurepärane hoone üle jõe edasi HBS ülikoolilinnak
mis on avatud kolledži üliõpilased, GAPid õpilased, üliõpilased üle kogu ülikooli,
sealhulgas õppejõud, ja see on koht, kus tulevad koos töötada uuenduslikke asju,
eriti ettevõtliku asjad
kui sina ja 0 või rohkem sõpru mõtled midagi ettevõtliku
kas sel klass, pärast seda klassi või kaugemale.
>> Nii et üks asju, mida nad teha üle J perspektiivis on need reisid,
millest üks on New Yorki, millest üks on Silicon Valley.
Kosmos on väga piiratud, kuid see on võimalus läbi käima magistriõppes
ja kraadiõppurid kogu campus ja tegelikult aega veeta nendes valdkondades
jututoas kuni alustavatel, jututoas kuni ettevõtjaid jms.
Nii et kui huvitatud, vaadake seda link siin.
Samuti on saadaval slaidid internetis.
>> Kas me pehmendama maja heli natuke?
Kui soovid meiega liituda lõuna-sel reedel, 13:15 Fire & Ice, palun pea seal.
Vabandused, kui vorm on juba täis selleks ajaks teil seal.
Aga me jätkame seda traditsiooni edasi.
>> Täna jätkame kõrgem arutelu erinevate probleemide, et saame lahendada,
keskendudes märksa vähem, vähemalt täna edasi kood ja palju ideid.
Nii et arvan, et tagasi nädal 0, kui me rebis telefoniraamatu pooleks,
mille eesmärgiks oli teha midagi küll natuke dramaatiline
kuid saata punkt, et otsing ei pea olema tingimata,
kui selge, esimesel pilgul, kui võite arvata.
Ja probleemide lahendamise üldiselt ei pruugi alati olla parim -
Kõige loogilisem lahendus ei pruugi olla parim.
Nii et meil oli see telefoniraamatust ja ausalt öeldes me kõik siin ruumis oli instinktid,
kõige tõenäolisem, et alustada keskel otsides Mike Smith ja siis minna vasakule või paremale
põhineb iganes täht me sattusin kohta.
>> Aga see lihtne idee, et meie, inimesed on iseenesestmõistetav nii kaua
tõesti peaks hakkama tulema esirinnas meelt
sest probleemid saavad palju keerulisem kui telefoniraamatust
samade lihtne, geniaalne arusaamu on see, mis hakkavad võimaldab meil
lahendada palju keerulisem ja huvitavam probleeme,
seas olid ka mõned asjad, mida me enesestmõistetavaks juba nendel päevadel.
Miljardeid veebilehti seal, ja veel Google ja Bing jms
on võimalik leida asju meile meeldib.
Seda ei juhtu, kasutades lineaarset otsing, otsimine kõigi võimalike veebilehti.
Facebook on võimalus öelda, kes kõik oma sõbrad on või sõprade sõbrad,
ja et liiga saab teha näiliselt hetkega nendel päevadel
kuigi neil on miljoneid kasutajaid.
>> Ja nii kuidas me tegelikult lahendada probleeme, mis ulatus lõppkokkuvõttes vähendada
Ideede me vaatasime nädal 0 ja veidi täna.
Me ei uuesti sooritama seda algoritmi, kuid meenutavad me ka tegime nädal 0 Selle harjutuse
kus olime kõik püsti, võtta number 1,
ja siis me pidime kõik ise kokku sidumist ära, lisades oma arvud kokku,
siis poole jõugu istus iga iteratsiooni.
Nii et me läksime 500 õpilast 250-125 ja nii edasi.
Aga kui me ütles esmaspäeval, võimas idee seal
oli see, et kui me kahekordistunud suurus, et probleem
ja kõik lapsed Kohtu või EÜ 10 tuli tuppa tagasi ja ühines meiega,
Noh, me võiks ilmselt loota, et kogu kokku grupp
vaid veel 1 suur iteratsiooni silmus, kuna need ainult võibolla kahekordistada
või EÜ 10 juhtumit natuke rohkem kui kahekordistada.
Ja nii me oleks kulutada natuke rohkem aega,
kuid me ei pea kulutama 400 või 700 rohkem samme.
>> Lihtsalt, et maalida seda pilti nii, et on natuke vähem abstraktset, ärme on kõik püsti.
Aga kui neile, kes valis istuda orkester täna ei pahanda püsti,
Vaatame, kas me saame aru teie seast, kes kõrgeim isik on
tehes sama tüüpi võrdlev algoritm.
Nii et kui sa istud orkester, minu vabandused, kuid 1. etapp, püsti;
samm 2 paari maha kedagi lähedal teile,
aru saada, kes on pikem ja istuda, kui olete lühem.
Seejärel korrake.
[Õpilased vulisev]
>> Okei.
Okei. Üks Seismise. Mis su nimi on? >> Andrew.
>> Andrew, sa oled kõrgeim isik orkestri osa täna.
>> Palju õnne. [Aplaus ja cheering] Okei. Istet. Nii leidsime Andrew.
Aga kui kaua see on võtnud mind näiteks leida Andrew
Selles orkester osa 50 + või nii inimesi?
Ma oleks võinud üsna lihtne lähenemine ja alustada siin.
Ja ma olen 2 inimest püsti ja ma lihtsalt neid võrrelda,
ja siis ma ütlen kes on veidi lühem, "Olgu, sa istuda,"
ja ma lähen mäleta kes kõrgemaks isik oli.
Siis ma kordan, kordan, kordan, ja ma kinni hoida kõrgeim inimene
kuni leian kellegi veidi pikem kui neid, kus punkt
veidi lühem inimene peab siis istuma.
Aga et algoritm selle orkestri osa, kui seal on n sind,
kui palju samme on, et algoritm aega võtab? >> [Üliõpilane] N.
>> See vőtab n, eks, sest halvimal juhul, kui nii võib öelda,
kõrgeim isik on kõige viimane inimene, et ma saan lihtsalt juhuslik ebaõnn.
Nii et halvimal juhul, sõiduaega, et algoritm on lineaarne, see on n
kus n on inimeste koguarv ruumis, suuruse probleem.
Aga see algoritm?
Asjaolu, et te kõik püsti ja siis jälle pool istusid maha,
pool istusid maha, pool istusid maha.
Mitu sammu peaks, et on võtnud, kas seal on n sa siin oled?
[Üliõpilane] N log n. >> See oleks hullem. Logi n.
>> Nii log n, isegi kui te ei mäleta, mida logaritm on,
Praegu lihtsalt aru, et see on seotud kuidagi selle poole võrra ja vähendada poole võrra ja vähendada poole võrra.
See ei pea olema 2 korda. See võib olla tegur 3.
Aga see on see kordamine samasugune tegur, nii et probleemi ulatust algab siit
aga siis kohe läheb siia, siis siia, siis siia, siis siia.
Sa ei vii väike hammustused välja probleem, sa oled tõesti tükeldamine ära seda
suure hoobiga iga kord.
Seega oli meil 50 inimest, siis 25, siis 12 ½ või 13 seisvat inimest,
siis 6 ½ ja nii edasi kuni lõpuks lihtsalt Andrew jäi seisma.
Nii et me ei kavatse helistada, et samamoodi n, ja saate visualiseerida seda järgmiselt.
Meenuta seda pilti siin, kus lineaarne algoritm on nagu punane joon seal,
kollane joon oli loendamise teel 2s algoritm, mida me kasutada lugedes üliõpilastele
minevikus, kuid täna Püha Graal läheb jätkuvalt see roheline joon
kus kui me kahekordistunud inimeste arv orkester lõik või lihtsalt ütles,
kurat, ajame igaüks kogu tuba püsti, mitte nii suur asi
sest me ligikaudu kahekordistavad kui palju inimesi on siin all,
Veel 1 iteratsiooni, pole probleemi.
>> Leidsime Andrew või kes iganes juhtub olema pikem kui Andrew
aastal mezzanine või rõdu.
Nii et see lihtne idee, et me võtsime nii palju antud telefoniraamatust
aru, et seal on nii palju erinevaid kohti, kus saame rakendada seda.
Lihtsalt laksu mõned kõnepruugis - tegelikult, mitte žargooni esimene,
Lubage mul minna seda pilti siin.
Praegu me rääkisime n ja n / 2 ja seejärel logige n,
kuid me kindlasti tulla, nagu me jooksul semestri
muud sorti matemaatiliste valemite kirjeldamiseks selle üldise mõiste sõiduaega.
Need on kontekstist välja nüüd, sest me näeme varsti
algoritme, et need tegelikult esindavad.
>> Aga märkate siin sirgjoonena n, sirge, on tegelikult väga madal osutades kohe.
See on omamoodi optiline illusioon, et me lihtsalt muuta seda, mis x telg tähistab
ja y-telg, ja saame sirge punkt igas suunas me tahame.
Aga sellepärast, et see on nii näiliselt korter nüüd
sest meil oli vaja teha ruumi selle graafik palju aeglasem töötab korda.
Praegu teame, et seal on päris halb algoritme elu,
millest mõned ei võta n samme või, veel parem, log n samme, kuid rohkem.
Nii rea peal n siin allosas teate seal on n korda log n,
ja me näeme, mida see tähendab enne pikk.
Üle et on n ruudus, ja me ei ole näinud ühtegi n ruudus algoritme, kuid me parasjagu.
Ja see näeb tõesti halb.
Seal on 2 kuni n, midagi kordades, mis tundub isegi hullem.
Ja veel, kummaliselt, siis seal on n kuubis, mis, kui sa oled omamoodi mõtlemine,
kui sa selline ei matemaatikat, 2 n tegelikult muutub palju sirgemalt,
palju kõrgemal kui n kuubis, kui te vaatate kirved piisavalt kaugele.
Nii märkate kohe need teljed on omavoliliselt 2-10 x-teljel.
>> Ja mida see tähendab?
See tähendab, et 2 inimest 10 inimest toas.
See on kõik x tähendab: suurus probleem, mis iganes kontekstis on.
Ja vertikaalteljel praegu on sekundite arvu või sammude arv -
mõned ajaühiku.
Aga teate, et see on 0-60 ja 0-10.
Aga kui me mingi zoom out, nagu te võite Exceli või mõne aktsiagraafikud tarkvara,
ja me läheme kuni 200000, märkate, et midagi 2 n
läheb täiesti uputama töötab korda n ruudus,
n kuubis, n log n - kõik me rääkisime siiani.
Ja veel saak on siis, kui hakkame rääkima asjadest nagu Facebook
kus sul on palju, palju, palju inimesi kõik omavahel seotud,
olete n inimesed, kellest igaüks võib olla nii palju kui n sõbrad
kui kõik on omamoodi semu-semu maailmas,
noh, see on n korda n juba, nii et N-ruuduline võimalik sõprus,
vähemalt 1 suunas, n ruudus võimalik sõprussuhteid.
Nii et juba näitab, et otsida Facebook sotsiaalne graafik, nii et rääkida,
saab alustada tuleb väljendada selliseid valemeid.
>> Me tuleme tagasi ja muuta see palju konkreetsem,
kuid nüüd, eesmärk järgmise mitu nädalat
läheb kindlasti mitte minna rakendamisel algoritme või kood
et lõpuks võtta nii palju aega kui midagi sellist.
Aga põnev asi arvutiteadus, kui te jätkate edasi selles valdkonnas
võttes klasside nagu CS121, CS124, mis mõlemad on teooria kursused,
et tegemist on tegelikult mõningaid probleeme, mis eksisteerivad siin maailmas
et põhimõtteliselt, nii palju kui me teame, mida ei saa lahendada kõik kiiremini
kui halvim neist graafikud tegelikult teeb.
Nii et seal on palju avatud probleemid selles maailmas teha palju parem kui inimestel on siiani.
>> Nii alustame siis selle näite.
Nägime Sean võitlevad selle kaamera, kõik liiga kohmakalt video.
Aga reaalsus oli see, kui Sean ülesanne oli leida lauale nagu see number 7,
meelde tuletada, et ma ütlesin, et "Siin on kusagil taga paberitükke või valge uksed
"Number 7. Sean, leida see meie jaoks."
Ja see oli imeliselt ebamugav vaadata
sest ta oli tõesti hädas selle probleemiga.
Aga tegelikkus oli Sean tegi samuti keegi ruumis oleks võinud teha.
Ta võttis natuke kauem kui tavaline inimene võib olla,
kuid ta oletas, et seal oli mõned trikk seda probleemi,
ta eeldada, et ta oli midagi puudu.
Ja see ei aita, et sajad silmad olid pidades alla teda.
>> Aga tegelikkus oli kui sisendi probleem on hunnik juhusliku numbrite
ja sa palutakse leida 1 selline number,
Parim, mida saate teha on lineaarne otsing.
Start vasakul, liiguta paremale, või alustada õigel, liiguta vasakule.
Tagasiulatuvalt, võiksime mõelda, "Sean, miks sa ei lihtsalt alustada teisest otsast?"
Noh, 7 oleks võinud sama hästi siin olnud juhuslikult,
kuid ma teadlikult selle sinna pani, sest ma arvasin, et ta ei kavatse alustada aasta lõpus.
Nii et ma selline manipuleerida olukorda, vaid juhuslik kokkusattumus 7 oleks võinud kuhugi.
Nii algab õige lõpp oleks võinud olla parem siis,
Aga kui järgmisel aastal ma liikuda 7 mujal?
See ei ole täiesti uus lahendus -
alates 1. lõpus või muu - kui olete andnud mingit muud eeldused.
Nii Sean hakkas otsima läbi numbrid ja ta ütles: "5. See pole siin."
Siis läks ta siin ja nägin 19, siis ta peatus umbes 20 sekundit,
siis ta avas selle eest 13, ja siis selgus,
et seal ei tundu olevat muster siin.
See ei olnud 1, 2, 3, 4 või nagu. Seal olid lüngad numbrid, mis ei aidanud.
Ja ka seda, et olen kasutanud neid odavaid paberitükke varjata numbrid
on tegelikult tahtlik, sest kui ma eemaldada kõik need paberitükid,
Enamikule meist, Sean lisada, oleks arvatavasti vaatas omamoodi makroskoopiliselt
kell tahvli juurde ja ütles: "Oh, 7 on ilmselt seal." Me tegime seda koheselt.
>> Ja mis võiks olla, kuidas inimese aju töötab mingil määral
kuid tegelikkuses ta silmad või mõistus oli ilmselt koorides numbrid paremalt vasakule,
vasakult paremale, keskele kohta välja - midagi toimub füsioloogiliselt
nii et tundus nagu see juhtus koheselt,
kuid koefitsendid on isegi sees oli mingi metoodika leidmisel 7.
Ja tõepoolest, nüüd me räägime massiivid ja andmestruktuurid
ja mälu sees arvuti, ainus asi, mida inimesed saavad teha
on vaadata individuaalse mälu kohale 1 korraga.
>> Nii et iga teine ​​asukoht võib samuti olla kaetud mõne paberitüki
sest me ei näe seda niikuinii. Me teha ainult 1 asi korraga.
Nii et antud juhul on Seani juhtum, käisime siin ja siis läksime siin
ja siis läksime siin, siin, siin, siin, sain targad lõpuks
ja just selline vahele see meelevaldselt ja leidis 7 seal.
See üks ei olnud eriti eriline. See liiga oli rikkis.
Aga ta lõpuks leidis 7.
Aga nüüd Buffee tõesti, et parim, mida saate teha, kui anta teavet
muud kui juhuslikult järjestatud numbrid on alustada vasakult või alustada paremalt.
Või kuradit, te võite juhuslikult avada uksi, kuid isegi siis mida see tähendab olla juhuslik?
Noh, me tahaks olla kuidagi vormistama mida tähendab alustada siin,
siis minna siin, siis minge siia. Sean tegi suur, ja see oli lihtsalt lõbus vaadata.
Mis siis, kui selle asemel muudame probleemi natuke ja avab tänavusel Sean, kui soovite?
Kas keegi on mugav tulevad lavale ja lahendada veidi teistsugune probleem
ja ilmuvad kaamera?
>> Lähme üle orkestri sest kutid on üsna kaasatud täna juba.
Kuidas on roosa, on müts? Tule alla. Mis su nimi on? >> Alex. >> Alex. Okei.
Nii et Alex on tänavuse Sean ja ilmuvad järgmise mitu aastat
väärtuses CS50 loenguid.
Alex, meeldiv tutvuda. >> Meeldiv kohtuda ka.
Väljakutse käepärast teile, et teil on see natuke lihtsam
aastal, et ma ütlen sulle sama numbrid on siin, kuid nad on nüüd järjestatud.
Nii et nüüd teie eesmärgiks on leida number 7.
Ja tegelikult peaksime tõesti tegema seda - sa oled selline petmine, nagu arvuti ei oleks,
vaadates mida numbrid olid hetk tagasi.
Kriidiga see tegelikult ei aita kõik, et palju,
aga oletame, et sa ei tea, mida algne massiiv on.
Kõik te teate nüüd, et teil on hulgaliselt järjestatud numbrite
millel võib olla lünki nende vahel, ja teie eesmärk on leida number 7.
Kuidas te, mõistlik inimene, minna leida number 7?
>> Mine madala kuni kõrge? >> Okei. Mine madal või kõrge.
Ja ärge rebige need ära. Lihtsalt tõstke nad üles, et saaksime neid taaskasutada.
Okei, nii et 1. Oota. Enne kui jätkame, et oli 1, selgelt vale.
Nii, mis toimub teie peast läbi järgmine? Milline on sinu järgmine käik?
Järgmise üks. >> Okei. Järgmise üks. Hea. 3, nii vale. Milline on sinu järgmine käik?
Lase edasi. >> Olgu. Lase edasi. 5.
Nii hoida läheb, ja andke mulle käe see tulevaste põlvede jaoks.
7. >> Suurepärane. Väga hea. Leitud number 7. [Aplaus]
Nii et oli hea, kuid Sean liiga leitud number 7.
Ja ma väita, et sa ei ole tõesti ära selle täiendava osa teabest,
mis on see, et need numbrid on järjestatud.
Nii et me saame teha paremini? Kõik ettepanekud siia? Jah, tagasi.
[Üliõpilane] Binary otsing. >> Ma ei tea, mida Kahendotsingupuu on.
>> [Üliõpilane] Start keskel. >> Alusta keskel. Okei. Nii et vaatame, kas saame seal.
Nii et kui selle asemel sulle öeldakse algus keskelt, edasi minna ja avada keset uks.
Seal on 8 neist, et sa lähed on suvaliselt valida üks
veidi vasakule või paremale. Okei. 7! [Aplaus] Väga kena.
Okei, aga kus me siis seda?
Oletame lihtsalt, et murda viik sa hakkasid siin
sest et võrdselt oleks võinud juhtuda ka.
Me lihtsalt juhtus tean, et 7 oli seal. Nii et see on 13.
Nii et kui nad järjestatud ja me lihtsalt hakkas keset,
milline oleks optimaalne järgmine käik on olnud?
Mine vasakule. Ja nii siin tuleb telefoniraamat näiteks uuesti.
Kui 13 on siin ja me teame nimekirja sorteeritakse,
siis kõik need paberitükid on ebahuvitav meile nüüd
sest me juba teame, et 7 tuleb vasakule
Kui need numbrid on järjestatud ja leidsime 13.
>> Mis su järgmine käik siin? >> Mine vasakule. >> Olgu, hästi.
Nii et mine vasakule, ja - oota, hei, hei, hei. See on petmine.
Nii et sa leidsid 7, kuid mis oli algoritm me lihtsalt rakendada?
Alusta keskel. >> Hea. Mis siis loogiline jätk, et sama mõte?
Oh, just need. >> Täpselt. >> Nii et ma hakkan siin. >> Hea.
Nii et nüüd me läksime veidi vasakule uuesti. See on 3.
Aga huvitav Buffee nüüd on Millist sa ei pea hooli?
Need 2. >> Need 2. Nüüd see võib ära minna, see võib ära minna.
Nüüd probleem, et oli 8 siis oli suurus 4 nüüd on suurus 2.
Me saame üsna lähedal. Jällegi minna keset neid 2 elementi.
>> Okei. Nii et see on omamoodi kahju, et nüüd oleme alati läheb vasakule, sest me oleme allapoole.
Aga sellest pole midagi, sest nüüd me viskame selle ära ja kõik muu, jättes meile vaid 7.
Anname aplausi. Leidsime 7 uuesti. [Aplaus] Okei. Muidugi.
Oota vaid veel 1 sekund.
Isegi kui see järgmise protsessi liiki võttis natuke kauem, kui me arvasin, et see,
ausalt öeldes, teie esimene instinkt oli parim, eks? Leidsime 7 silmapilkselt.
Aga oleksime leidis 7 kiiremini, ükskõik mida, selles näites võrreldes selle ühe
sest kui numbrid on kõik järjestatud meelega lehekülgi telefoniraamatust
saate tõepoolest tükelda pool probleem jälle ja jälle ja jälle.
Ja see ei ole päris nii lihtne, et näha seda vaid 8 numbrid
erinevalt 1000-leheküljeline telefoniraamatust kui sa tõesti seda näha visuaalselt,
kuid sel juhul, kui Sean otsisin 7,
kui palju samme halvimal juhul oleks ta pidanud teda? >> [Üliõpilane] 7.
7 halvimal juhul. Noh, halvimal juhul ei 7, kui seal on 8 uksed siin.
Oleks pidanud teda 8 astet.
>> Nii et kui seal on n uste, see võis võtta Sean paar aastat tagasi n samme.
Nüüd, teie puhul, Alex, arvestades, et need numbrid on järjestatud -
ja me saame mingi järeldavad seda, kust me oleme seni selles loos -
Mis töötamise aega Alexi arukam algoritm
alustades keskelt ja seejärel korrata?
[Üliõpilane] 3. >> Nii et see saab olema 3 umbes nii, kui sa minna 8-4 2-1.
Nii et 3 sammu või üldisemalt, see on log n uuesti.
Iga kord, kui sa poole võrra ja vähendada poole võrra ja vähendada poole võrra ja vähendada poole võrra,
see väljendus see idee log n.
Ja nii, et oleks võtnud sul on ainult 3 astet ning ta tõepoolest tegi
kui avasime uksed vähendamine poole võrra ja vähendada poole võrra,
arvestades, et see oleks võtnud Sean umbes 7 või 8 astet.
Nii et tänan teid, et olete koos meiega sel aastal. >> Tänan teid. Oli meeldiv kohtuda.
Täname Alex. >> Samuti. [Aplaus]
>> Mis on siis tõeline tähendus on?
Nüüd kujutage ette, et see ei ole 8 uksed, mis ausalt öeldes kõik meist võiks leida midagi
taga 8 uksed päris kiiresti lihtsalt rebimine paberitükke ja läheb koos oma instinkte.
Aga kui see on miljonit uksed? Mis siis, kui see on 4000000000 uksed?
Juhul 4 miljardit uksed, sa tõesti tahad minna koos Alexi algoritm,
Kahendotsingupuu kui hakkame nimetades seda või jaga ja valitse üldisemalt
kus hoiate poole võrra ja vähendada poole võrra probleem,
sest kui sul on 4000000000 uksed, mitu korda saate karbonaad 4 miljardi pool?
[Üliõpilane] 32. >> See on tegelikult 32. Võite töötada selle läbi paberilehele või oma peaga.
Lähed 4000000000-2000000000 to 1 miljardi pool miljardit, 250 miljonit eurot, dot, dot, dot.
Ja kui sa läbi matemaatika, sa lähed tõesti saada 32,
ja et tegelikult on seotud arvuti teadust, sest me tavaliselt arvatakse 2 astmed.
2 32 juhtub olema 4 miljardit eurot.
Nii et seal on palju tähtsust selliseid volitusi 2 arvutiteadus.
>> Aga mis umbes 8 miljardit? Mitu sammu on, et aega võtab, kui on 8000000000 uksed?
[Üliõpilane] 33. >> Nii et 33. Mis siis, kui seal on 16000000000 uksed? Mitu sammu on, et aega võtab?
[Üliõpilane] 34. >> 34. Võiksime liiki jätkata seda küllastumise. Aga see on võimas asi.
Võite tutvustada miljardeid rohkem sisendeid oma probleemile, kuid pole hullu,
sa lihtsalt võtta 1 täiendav hammustada välja ja seega annab meile midagi binaarne otsing
või jaga ja valitse üldisemalt.
Aga ma olen selline petmine siin, eks?
Juhul Alexi algoritm, tal oli eelis Sean.
Ta teadis, et need numbrid olid sorteeritud, kuid Alex ei olnud neid sorteerida ise.
Ma ette tulid tahvli ja liik kindlaks teinud,
et ma joonistasin neid kõiki läbi sorteeritud järjekorras, siis ma katmine paberiga.
Aga kui palju tööd teinud, et võta mind?
Kui oleksime alustati need numbrid näiliselt juhuslikus järjekorras -
antud juhul seda lihtsamat numbrid, 1 kuni 8 siin -
Kuidas me minna sorteerimine neid väärtusi?
Kui sa olid inimeste andnud selle ülesande, millist intuitiivne Te sooviksite
sorteeritakse terve hunnik numbreid?
Need asjad pandi välja nagu puzzle tükki. Jah.
>> [Üliõpilane] ma võtaks iga arv ja võrrelda seda igaüks
ja jätkame vasakule. >> Olgu, hästi.
Nii, et võta iga number, võrrelda seda teise peal,
ja siis muudkui liigub piki nimekiri, millist rejiggering asju kui lähete.
Nii et siin on meil võimalus võibolla veel mõned inimesed kaasa lööma.
Kas meil on veel 8 vabatahtlikke, kes oleks tore tulla?
Veidi vähem survet, sest sa pole ainuke. 1, 2, 3, 4, 5, 6, 7, 8.
Tule alla. Te ei kavatse olla numbrid 1 kuni 8.
Vaatame, kas me ei saa seda teha sorteerimise Alex palju samamoodi ma tegin seda varem.
1, 2, 3, 4.
Lase käia ja kui sa oleks, rivistama laval vahel muusika kuulamiseks ja mind siia
samas järjekorras nagu slaidi ekraanil.
Uh-oh.
Me töötame su järgmisesse näiteks. Oh, oota, oota. Läheb lahti. Oota.
Järgmine näide on nüüd. Ole lahke. Number 8. Tule üles.
Hea küll. Sorteeri endid vastavalt sellele.
Lükake natuke kõrvale muusika seisan siin.
Nii et meil on 4, 2, 6 - sinna, siin, seal - 3.
Jah. Okei. Lähed siia. Ei, sa seal viibida.
Jah, just seal. No ma eksin. Just seal. Okei, väga hea. Okei.
Nii et nüüd lähme sorteeri need kasvavas järjekorras.
>> Kuidas ma minna seda teed?
Algoritm, mis pakkus hetk tagasi oli, miks me lihtsalt ei võrrelda
inimesed, kes on omamoodi üksteise kõrval ja seejärel määrata vigu,
liikudes vasakult paremale.
Nii et siin on meil 4 ja 2, ilmselt rikkis. Olgem vahetan sinuga. Okei.
Nii et nüüd ma lähen liikuda sätestatakse rida. 4 ja 6, nope. [Naer]
6 ja 8, päris hea. 8 ja 1, las ma vahetan sinuga poisid. Hea küll.
Nii et 8 ja 3, swap kutid.
8 ja 7, las ma vahetan sinuga poisid. 5 ja 8, suurepärane.
Ma annan sulle järjestatud nimekirja.
Hea küll. Nii et mitte päris.
Aga see on parem, sest suuremaid numbreid - näide 8 -
on selline mullidena üles vasakult paremale poole.
Nii et ma sain 1 neist õige, kuid see tunne see ei ole päris lahenda probleemi.
>> Mida Sa välja pakuksid me edasi tegema? >> [Üliõpilane] Hoidke seda teha. >> Hoiame seda teha.
Ja mõistma, jälle, me seada asju, mida lihtsalt millel on kõik inimesed
omamoodi arukalt korraldada ise põhineb sellel pildil,
kuid nüüd peame olema palju rohkem metoodiline.
Me peame olema algoritmilise sellest, nagu oleks me kirjalikult kood -
sel juhul verbaalne pseudokoodi.
Nii et lubage mul lihtsalt proovida seda uuesti. See töötas päris hästi. See ei lahenda seda.
Aga kui see kahtlen, lihtsalt proovida ja proovige uuesti. Nii et 2 ja 4, ei aidanud enam.
4 ja 6. Ah! 6 ja 1 veidi parem nüüd.
6 ja 3, hea. 6 ja 7 7 ja 5, 7 ja 8, hea.
Ja tead, ma ei saa ilmselt ignoreerida 8 nüüd, sest ta on lõpus nimekirja.
Võib-olla me ei pea muretsema keegi läheb mööda.
Aga vaatame, kas see on ohutu eeldusel.
Nüüd nimekiri on - kuradi - ei järjestatud. Proovime seda uuesti.
Nii et 2 ja 4 4 ja 1, 4 ja 3.
4 ja 6, hea. 6 ja 5, hea.
6, 7, ja 8, hea. Aga teate, ma lihtsalt lõpetada siin nüüd ja peatub siin nüüd?
[Üliõpilane] Jah. >> Jah?
Mida teha, kui keegi teie seast oli number 9 kõik teed seal?
See oleks järjestatud. >> Hea. See oleks järjestatud esimest korda ümber.
Hea. Nii et lähme tagasi. Me oleme peaaegu kohal.
1 ja 2, 2 ja 3, 3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8.
>> Olen teinud nüüd, kuid jällegi, ma olen arvuti, mida saab ainult seda, mida ma olen rääkinud, mida teha,
ja mu ainus mälestus on see, et ma tegelikult just tegin natuke tööd.
Midagi muutunud siin.
Nii et ma ei ole tehniliselt kinnitas visuaalselt või algoritmiliselt selle nimekirja tõepoolest sorteerida.
Nii lihtsalt hea meede, lihtsalt olla anal sellest, teeme seda veel 1 kord.
Nii et 1 ja 2, 2 ja 3, 3 ja 4. Ja tead mis?
Lihtsalt hea meede, ma lähen jälgida minu poolt seekord
kui palju vahetuslepingud teen lihtsalt nii, et ma tean, kui palju tööd ma olen tegelikult teinud.
3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8. Ei vahetustehingud.
Nii et nüüd ma õiguspäraselt olla idioot seda teha ka
sest kui ma ei teinud tööd selle kaudu liigu inimestele,
siis selgelt, et juhtub jälle, kui ükski neist on omamoodi juhuslikult
adversarially liigub ise ümber. Nii et nüüd ma ei peatu.
Vaatame nüüd küsida, kui palju tööd teinud seda tegelikult mind?
Mitu sammu see veel kestab? >> N ruudus.
Jah, nii n ruudus. Kust saab n ruudus?
Sa pead kontrollima iga arv -
On n arv, ja sa pead kontrollima iga numbri teiste n arvu.
Hea. >> Nii et see on n ruudus. >> Hea.
>> Nii tundub see võiks väga hästi olla n ruudus, eks?
Seal on n need kutid, 8 eriti sel juhul,
kuid iga kord kui ma läksin läbi selle nimekirja olin võrrelda esimene inimene vastu teise,
teine ​​vastu kolmandat uuesti ja uuesti ja uuesti,
ja kui ma sain lõpuks, mida ma tegin? Ma redid ta.
Nii et kui me üldistada seda seletust oleme n inimesed
ja ma teen ilmselt 8 samme, n samme, iga kord ma lähen läbi selle algoritmi.
Aga mitu korda halvimal juhul ma pean minema läbi selle nimekirja inimestest?
[Üliõpilane] N korda. >> Ilmselt n, eks, sest halvimal juhul,
Mis on ilmselt kõige mustema paigutus need kutid saada-minna?
Kui nad täiesti vastupidises järjekorras
sest lihtsalt oletame, vaimselt, let's - Mis su nimi on? >> Bowen.
Bowen. Okei. Nii Bowen, tule siia hetkeks.
>> Oletame, et Bowen oli siin alguses algoritm,
ja me ei tea, mida kõik teised on, kuid Bowen siin, vastavalt sellele algoritm -
ja kui sa tahad lihtsalt jalutama minuga - läheb mulksuma, kui ta esimest korda ümber,
kõik viis lõpuks.
Aga oletame, et inimene kõrval Bowen oli number 7.
Ma pean minema tagasi ja saada number 7, mis tähendab, ma pean minema kogu tee tagasi siia.
Nüüd ma pean olema, et sama jalutama isikuga, kes on number 7.
Aga kui siis number 6 oli tema kõrval ka?
Siis ma pean minema tagasi ja saada 6.
Nii et taas, iga iteratsiooni see silmus ma räägin iga n inimesed,
ja ma oleks võinud teha n neid jalutuskäike veendumaks, et ma olen tõmmates
kõiki suuremaid elemente tagasi ja tagasi ja tagasi väga loendi lõppu.
Nii n asjad n korda on lihtsalt n korda n või n ruudus.
>> Nii et siin juba on meil algoritm, mis ei ole enam n, et pole enam log n,
see on tegelikult hullem kui midagi oleme varem teinud.
Nii Alex liiki vedas, et ma tegin kõik tööd ilmselt kuni ees teda,
kõik kallis töö, nii et ta saaks nautida selle binaarne otsing algoritm,
mis on samamoodi n.
Aga see on kooskõlas esmaspäeval teema.
Me andsime natuke rohkem ruumi, me kasutasime rohkem bitte, et kiirendada meie sõiduaega.
Nii palju nagu seal see kompromiss ajas ja ruumis
Samuti võib olla ainult kompromisside aega, kuni ees omamoodi asju valmis minema
ja tegelikult täidesaatva algoritm nagu otsing. Proovime veel ühe.
Kui te ei pahanda, lihtsalt kiiresti ümber tõstes end sobitada, et jälle
Proovime midagi veidi teistsugune, kui see ei ole päris nii lihtne
kui lihtsalt fikseerida kõik paarikaupa vigu, mis on super intuitiivne.
Lähme hoopis natuke rohkem tahtlik ja seda teha.
See üks liiga pakun on ilmselt üsna intuitiivne.
>> Olgem valida väikseim inimene nimekirjast ja jälle. Nii et siin me läheme.
4, sa oled kõige väiksem inimene, keda olen seega näinud nii kaugele,
nii et ma lähen vaimselt meeles pidama, et lihtsalt juhtides sind nüüd.
2. Ooh! Unusta number 4. Ma leidsin just uue väikseim element selles loetelus.
Ma lähen omamoodi meeles pidada. 6, 8.
Ooh! 1. Head aega. Nii et nüüd ma lähen mäleta number 1.
Me teame, et 1 on väikseim, kuid ma olen arvuti. Mis siis, kui seal on 0?
Mis siis, kui seal on -1? Ma pean edasi minema.
Nii 3, 7, 5, nope. Okei. Nii et number 1 oli väikseim.
Lubage mul valida te nimekirjast - we'll minna sel viisil -
ja panna teid omavoliliselt alguses nimekirja.
Nüüd oota natuke. Ma nagu petnud.
Kui need kutid esindama ei nimekirja 8 inimest, kuid massiivi
8 tükkideks sidusmäluplokki - ei te sealt tagasi hetkeks?
Seal on tegelikult üldse ruumi teil siin.
Niisiis, kuidas me ruumi teha - mis su nimi on? >> Sammy. >> Sammy.
Kuidas me teeme ruumi Sammy?
>> Me liigume n, mis on enne mind. >> Okei.
Nii et me võiks minna n inimesed, kes on enne teda,
nii et kui te tahate võtta 1 tahtlik, dramaatiline samm vasakule.
Nad kõik tegid seda üheskoos, kuid viimane kord, kui ma kirjutasin mõned kood,
sa ei saa omamoodi liikuda palju asju korraga.
Me võiksime seda teha silmus, liigub igaüks üks kord korraga.
Nii et kui te ei oleks midagi suurendades tagasi paremale,
ja Sammy, kui sa saaksid tagasi astuda, sest seal on veel mingit võimalust sa,
nüüd teeme seda. Kus oli Sammy hetk tagasi? Just seal.
Nii et seal on vahe olemas. Nii et sina saaksid minna Sammy kohapeal.
Nüüd järgmine isik üles ja nüüd järgmine inimene, nüüd järgmisele inimesele. Nüüd on meil ruumi Sammy.
Nüüd keegi saalist - see oli hea, et oli õige,
tundus natuke aega - mis on kiirem? Jah.
[Üliõpilane] uue massiivi? >> Mis see on? >> [Üliõpilane] uue massiivi? >> Olgu, hästi.
>> Nii kooskõlas käesoleva teema lihtsalt kompromisse, miks ei ma lihtsalt teha uus massiiv
ja siis Sammy on ujumine ruumi ees neid inimesi, näiteks
ja me lihtsalt alustada täites uus massiiv kokku. See liiga teeks.
Aga ma ei ole huvitatud kulutusi rohkem ruumi täna. Mis on teine ​​lähenemine?
[Üliõpilane] Vaheta. >> Okei. Me võiksime lihtsalt vahetada need 2 kutid. Mis su nimi on?
Mario. >> Mario. Nii Mario, sa olid praegu siin.
Sammy, kas sa varundada hetkeks? Mario oli siin.
Meil ei ole ruumi enam sinuga, nii et kui sa ei pahanda läheb kus Sammy on,
me paneme Sammy siin, ja nüüd ma tahaks väita, et Sammy Vahetatakse operatsioon oli palju kiirem.
Me tegime 1 toimi vahetada need kutid, või äkki 2 vahetada need kutid,
kuid me ei teinud 1, 2, 3, 4, nii et tundub parem. Nüüd oota natuke.
Ma nagu näha probleemi hullemaks, sest number 4 oli selline lähedal alguses.
Nüüd number 4 on veidi lähemale selleks, aga ma ei tea, või hooli sellest.
Nii et see on lihtsalt halb õnn, et number 4 on natuke kaugemal oma määratud kohas.
Nii et olgem nüüd korrata algoritmi.
>> Et veel kord, kui see lugu oli, kõik me ei olnud kõndida läbi nimekirja
otsin väikseim nummerdatud inimene.
Nii et nüüd teeme seda jälle. Me ei pea muretsema Sammy enam.
Me ei saa lihtsalt minema siit. Ooh! Number 2. See on päris väike arv.
6, 8, 4, 3, 7, 5. Olgu, hästi.
Ja õnneks juhuslikult, ma ei pea liikuma - >> Willie.
Willie, sest ta on tema õige koht nüüd.
Teeme seda uuesti ja neid eirata 2 kutid.
6. See on päris väike arv. Ooh! 8 on kindlasti suurem.
4. Olgem keskenduda 4. Ooh! 3 on isegi parem.
7 ja 5. Mida me siis nüüd teeme koos - >> Roger. >> Roger?
Lähme vahetame ta number 6.
Nii et kui 6 ja 3 sooviks vahetada,
oleme nüüd mingi saanud õnnelik, et 6 on lähemal, kui ta peaks olema,
aga see on lihtsalt kokkusattumus siin. Nii et olgem nüüd minema siit.
8 on päris väike arv. Ooh! 4 on väiksem.
6, 7, 5. Mida me nüüd teeme? >> Vaheta. >> Täpselt.
Nii et nüüd teeme seda omamoodi kiiremini.
8, 6, 7, 5. Kust 5 minna? Hea. Okei.
6, 7, 8. 6 saab peatada, kui ta on. Mis su nimi on? >> Rosalie.
Rosalie saab peatada, kui ta on. 7 jõuab - Vaatame. 7, 8. Okei.
Nii et 7 saab peatada, kui ta on. Mis su nimi on? >> Amna. >> Amna.
>> Nii Amna saab peatada, kui ta on, ja number 8 on juba kus ta nüüd peaks olema.
Olgu, hästi. Tundub nagu me lihtsalt luua töö ise, tõsi küll.
Mis lõppkokkuvõttes sõiduaega Selle algoritmi?
Kui me mõtleme need inimesed ei ole nii 8, kuid kui n? >> See on n.
See on n samme, kuid me uurime iga kord.
Okei. N aga sa kontrollida iga kord?
Okei, aga kui see on n samme, ei tohiks mul on olnud võimalus sorteerida teile lihtsalt läheb 1, 2, 3, 4?
Oh! Okei, see on suur vahe.
Nii n ruudus miks? Mis tegelikult toimub?
Seal on n inimesi selles nimekirjas, kuid leida väikseim isik nimekirja
halvimal juhul, kui palju samme pean võtma? >> N.
>> N, paremale, sest halvimal juhul, number 1 on kõik teed sinna,
nii et ma pean minema saada teda.
Ja siis kui ma lõpuks aru, 1 oli väikseim, siis see on üsna kiire, et vahetada neid.
Aga nüüd pean ma alustama algusest ning otsida kes?
Suuruselt järgmine kahanevas järjekorras isik, mis on 2. Kui halvimal juhul on 2?
Oh, mu jumal. See kõik viis siia lõpus.
Nii et nüüd ma olen lihtsalt teinud teise n samme, teise n samme.
Ja kui meil on n inimesed ja halvimal juhul väikseim inimene on n sammu kaugusel,
see on jälle n korda n, ja nii me jälle on n ruudus.
Seda ei tunne end hästi.
Ja tegelikult, isegi parimal juhul - oletame, et nad alustad järjestatud -
mitu sammu see võtab minu jaoks kasutades seda algoritmi sorteerida neid n inimesed?
N ruudus. >> Kuulsin n ruudus. Miks n ruudus?
Sest sa ikka pead kontrollima iga kord. >> Jah.
Ja sa pead vahetada neid. >> Kuigi me inimestel on mingi kõiketeadja
selles mõttes visuaalselt, et saame lihtsalt selline näen, et see sorteeritakse,
arvuti ei ole nii tark.
See saab vaadata siin ja siin ja siin,
aga kui see, mida ta otsib on väikseim element,
tean vaid, et sa leidsid väikseim element, mida millisel hetkel? Kui oled lõpus.
Aga sel hetkel oled ainult leida praegu väikseim element.
Sa ei pruugi teada midagi olukorra kohta maailmas.
Nii et sa pead minema uuesti ja uuesti ja uuesti.
>> Nii et seekord ma tõesti vaadata loll, sest ma kontrollida, korras, 2, sa oled kõige väiksem,
kuid ma ei tea, et kokku veel.
3, 4, 5, 6, 7, 8. Olgu, hästi. 2 oli tõepoolest kõige väiksem.
Nüüd otsime järgmine kahanevas järjekorras. Okei.
3, sa oled praegu väikseim. Vaatame. 4, 5, 6, 7, 8. Okei, vedas jälle.
3 oli tõepoolest õiges kohas. Aga ma lähen hoida tehes seda uuesti ja uuesti ja uuesti.
Kuidas me saame kunagi nii veidi paremini?
Selle asemel, et inimesed mulksuma paarikaupa alates väiksemast ja lõpetades suuremaga
ja selle asemel, et minna edasi ja tagasi läbi nimekirja valides seejärel väikseim isik,
miks me ei asemel sisestada need inimesed uude nimekirja samm-sammult?
Proovime seda. Nüüd lubage mul nimetame seda asja sisestamise omamoodi.
Nii et siin me oleme siin. Number 1. Ma ei hooli keegi teine ​​selles loetelus.
Minu eesmärk praegu on panna number 1 alguses järjestatud nimekirja.
Ja ma lähen ettepaneku sest mul on ainult 8 mäluhulka,
omavoliliselt praegu olen seina vahel minu väidetavalt sortimata nimekirja,
ja igaüks, kes on mu selja taga ma väita, sorteeritakse.
Nii et nüüd on meil number 1.
Ma tahan lisada ta minu järjestatud nimekirja, nii et ma olen lihtsalt kavatse minna mu seinal,
ja nüüd ma väidavad, et see nimekiri on sorteeritud, see nimekiri on sorteerimata - vähemalt nii palju kui mina tean.
Ma ei näe kõik numbrid korraga.
>> Nüüd ma juhtun kokku puutuvad number 2. Mida ma temaga tegema?
Ma sisestan sa nüüd sisse järjestatud nimekirja. Aga teate, kui lihtne see oli.
Ma lihtsalt pean vaatama. Number 1 on olemas. Oh, loomulikult 2 läheb pool number 1.
Nüüd mida ma pean tegema 3? Ma sisestan teid järjestatud nimekirja. Aga see oli super lihtne.
See on super lihtne, see on super lihtne, see on super lihtne, väga lihtne, väga lihtne.
Ja nüüd on kõik järjestatud minu taga, ja kui palju samme ei, mis võtavad?
[Õpilased] N. >> Nii et see on ainult n. Meil vedas.
Alles n miks? >> [Üliõpilane] Kuna loetelu on järjestatud.
Nimekiri on juba järjestatud. Nii et meil vedas.
Aga me loodud algoritmi see aeg, et rakmed sellist õnne,
et parimal juhul, mida ei raiska asjatut aja.
Nii et meil on nüüd see, mida me nimetame mull kehvasti
kus inimesed sellist mulksuma paarikaupa.
Meil on nüüd valik omamoodi kus me kisu väikseim isik ikka ja jälle.
Ja nüüd on meil sisestamise omamoodi kus me justkui ennetavalt panna inimesed, kui nad kuuluvad
üha järjestatud nimekirja.
Kui meil õnnestuks, aplaus need kutid siin. [Aplaus]
Võtame meie 5-minutilise vaheaja siin.
Ja kui me tagasi tuleme, me laseme kõik need algoritmid veest välja
midagi paremat. Hea küll. Tänan teid väga. Saate hoida neid nagu suveniire.
Hea küll. Me oleme tagasi.
>> Ja sulgege päris kiire, meil oli neid 3 erinevat lähenemist sorteerimine,
Kogu mõte oli saada kuni punktini, kus keegi nagu Alex
võiks otsida nimekirja numbrid kiiremini kui keegi nagu Sean võiks.
Ja kuigi meil on nii lihtne näiteid 8 numbri,
siis võiks ekstrapoleerida kergesti kuni 8 veebilehti, 8 miljardi veebilehti,
ehk 800 miljonit sõpradega Facebook.
Nii et need algoritmid saab kindlasti skaala seda tüüpi väärtusi,
ja ideed on lõpuks sama.
Nii et mull sorteerida oli esimene, kus me sellist mullidena üles suurim inimene
kogu tee paremale vahetades inimesed paarikaupa.
Siis oli meil mida me kutsume valik omamoodi, kus ma veidi tahtlikult
hoida otsin läbi nimekirja, valides kõige vähem uuesti ja uuesti ja uuesti,
loogiline tulemus, mis on selle nimekirja lõpuks sorteerida.
Siis kolmas, Ma sisestasin inimesi oma sobivas kohas
ja me tegime väga kunstlik näiteks, et nimekiri oli juba sorteeritud,
aga see oli saata sõnum, et sisestamise omamoodi juhtum,
võite saada õnnelik.
Kui numbrid on juba sorteeritud, see on ainult kavatse teid n samme kinnituseks,
arvestades, et valik omamoodi sa oled natuke rohkem tunnel nägemine
ja sa ei ole kunagi aru, et nimekiri on juba järjestatud.
Nii et vaatame, mull sorteerida huviorbiidis siin.
Järgmises näites, me parasjagu näha vertikaaltulpade
kelle kõrgused arvude, et saaksime omamoodi visualiseerida sorteerimine juhtuda.
Mida väiksem on baar, väiksem number; suurem baar, suurem number.
>> Ja me mängida seda default kiirusel.
Läheb veidi liigutada kiire nüüd, aga punane on see, mis näitab, 2 baari
võrreldakse kõrvuti.
Ja kui sa vaatad tähelepanelikult, mis juhtub on see, et kui baarid on rikkis,
väiksemat saab liigutada vasakule, suurem üks paremale,
ja siis hoiavad edeneb.
Nii et kui me teeme seda ikka ja jälle, märkate, et väikseim baarid
ei kavatse hoida inching oma tee vasakule
ja suurim baarid ei kavatse hoida inching oma tee paremale.
Ja tõepoolest, me hakkame nägema muster kogu tee paremas servas
nagu nägime 8 ja seejärel 7 lõpuks vahustamine kuni otsas meie inimeste nimekiri.
Nii et see läheb väga kiiresti natuke tüütu, seega lubage mul lõpetada see hetkeks.
Lubage mul muuta kiirust palju kiirem.
Ma ei vaheta algoritm, ma lihtsalt teha animatsiooni juhtuda kiiremini.
Ikka mull sorteerida, sama algoritmi,
kuid nüüd näete palju kiiremini kui meie verbaalne tutvustamistegevuse
et suurim elemendid on tõepoolest vahustamine kuni tippu.
>> Nagu kõrvale, need väikesed ruudud allosas vasakul ja paremal all
on vaid väike meeldetuletus, kui palju võrdlusi sa teed.
Aga nüüd, saame keskenduda püramiid, mis on kuju võtmas, ja seal ta läheb.
Kõige väiksem osa on vasakul, suurim paremal, ja kõike muud nende vahel.
Nüüd vaatame selle asemel vaatleme valik omamoodi.
Ma lähen edasi minna ja vajuta Stopp. Me ei hakka uut juhuslik kogum baarid.
Valik omamoodi, mäletate, läbib nimekirja uuesti ja uuesti ja uuesti,
noppida välja kõige väiksema osa. Nii et siin on valik omamoodi.
Tundub, et seal on vähem tööd juhtub nüüd, sest me ei võrrelda paarikaupa
aga me lihtsalt omamoodi cherry picking väikseim elemendid paremalt vasakule.
See võttis väga vähe aega, nii et seal on lõhe juba.
Lihtsalt, sest algoritm on öelnud, et võtta n ruudus korda, nagu mull sorteerida
ja nagu valik omamoodi, need on tõesti halvima töötab korda.
Näiteks juhul, oletame, valik omamoodi,
Ma tegelikult olen valides väikseim inimene ja paneb teda siin,
siis ma teen seda uuesti, siis ma teen seda uuesti,
kuid seal oli kerge optimeerimine ma võiksin teha.
>> Niipea, kui ma kolisin number 1 siin - Sammy sel juhul -
mida ma pean tegema temaga hiljem? >> [Üliõpilane] Jätke ta.
Jäta ta, eks? Mitte midagi.
Ma ei pea kunagi rääkima Sammy uuesti, sest kui ma olin välja valinud väikseim element
ja pani ta siin, miks raisata aega läheb lõpuks kogu mu nimekirjas?
Järgmisel iteratsiooni andke mulle tegelikult liikuda ainult number 2, ainult number 3.
Nii et tegelikult ma ei tee n asjad n korda.
Ma tegin n asju, siis n - 1 asja, siis n - 2 asja, siis n - 3 asja,
siis n - 4, dot, dot, dot.
Meil on natuke geomeetrilises jadas, mis tähendab lihtsalt
Sa liidad kokku järjest väiksemaid numbreid.
Ei n + n + n + n aga n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Ja mida see üldiselt töötab välja tuleb -
Ma lähen segi ajama mu laud siin hetkeks -
et läheb töötada välja tuleb midagi n (n - 1) / 2
kui me lihtsalt selline pilk tagasi matemaatika raamat, kus sul on kõik cheat lehed
jaoks valemid.
Kui sa oled lihtsalt lisades midagi n + n - 1 + n - 2, see töötab välja midagi sellist.
Ja kui me lihtsalt selline korrutada see läbi, et N-ruudus miinus n / 2.
Ma kordasin n ruudus, kuigi ja see on, sest ma olin selline võttes vaimne otsetee
sest tegelikult n ruudus miinus n jagatud 2 on tõesti tõsi mitmeid samme
et algoritm nagu valik omamoodi võtaks, kui me tõesti loendatakse
kõik need võrdlused ja kõik vähe hõivatud töö, mida me teeme.
Aga ausalt öeldes, kui n saab olla nagu miljon või miljard, kes kuradit see huvitab
kui sa teed miljardit ruudus miinus miljardit jagatuna 2?
Miljardit ruudus on tohutu hulk.
Te võite võtta teise miljardi pealt ta koos - n. See pole nii suur asi.
Nii et suurem number saada, seda vähem tähtis nende madalama tellitud terminid on.
Keda huvitab, kui sa jagad 2, kui sa räägid quadrillions numbrite sammud?
>> Nii et üldiselt, arvuti teadlased kipuvad visata kõike, kuid suurima perspektiivis
ja me lihtsalt selline lihtsustada maailma ja öelda, et see algoritm
võttis umbes n ruudus samme. See on töötamise aeg algoritm.
Nii et me tuleme selle juurde tagasi just hetk mõned konkreetsed näited,
kuid nüüd, see on omamoodi intuitiivne motivatsioon lihtsalt lihtsustades meie maailma
ja rääkides kõige olulisemaks tingimuste asemel sattumist kõik need väljamõeldud valemeid.
Nii et oli valik omamoodi, ja saime natuke õnnelik seal.
Vaatame sisestamise omamoodi. Lubage mul minna ja hakata selle ühe samuti.
Nüüd pane tähele, muster, mis toimub on natuke erinev,
ja alustasime juhuslikud arvud,
Aga kui me tegelikult kokku lugema mitmeid samme halvimal juhul
Kui loend algas täiesti õiges järjekorras,
me oleks ainult võtta n samme mõista nii palju.
>> Aga kui nimekirjas olid tegelikult tagurpidi - näiteks selles asjas -
siis märkate me tegelikult peame tegema palju rohkem tööd ka käesoleval juhul.
Ja see peaks selline tunne, et sulle meeldib see üks on selline töö raskem
saada väiksematele elemente vasakule ja see on, sest meil on õnnetu.
Loetelu on järjestatud kogemata tagurpidi.
Seevastu järjepunktiga omamoodi kui me jäljendada mida tegime meie inimestel siin
alustades kõigiga sorteeritakse ja seejärel alustada, see on päris hea algoritm, eks?
See on juba tegelikult sorteerida.
Nii et proovime kokku täpselt, kui palju aega need asjad on meid
kehtestades lihtsalt natuke kõnepruuki või märke, mis on tegelikult palju lihtsam
kui fanciness omamoodi soovitab.
See asi siin, see suur O ekraanil on see, mida arvuti teadlane üldjuhul kasutada
kirjeldada halvimal juhul sõiduaega algoritm.
>> Jällegi, mida halvimal juhul on see täiesti kontekstist sõltuv.
Mida tähendab meie jaoks halvimal juhul täiesti erinevad vastavalt probleemi me räägime.
Aga kui tegemist on sorteerimise, mis on kõige hullem võimalik stsenaarium?
Kõik on tagurpidi, sest see lihtsalt tundub, et tähendab palju tööd meie eest.
Olen kirja pannud mõned algoritme, et oleme näinud siiani:
lineaarne otsing, binaarne otsing jms telefoniraamatust või paberitükke,
siis mull sorteerida, valik omamoodi ja sisestamise omamoodi nagu nägime meie inimestele,
ja siis veel 1 inimene, mis on lõpuks nimetama hakatakse ühendada sorteerida.
Nii et lineaarne otsing halvimal juhul, kui palju samme läheb aega, et leida number 7
kui on n uste nagu Sean näoga? >> [Üliõpilane] N.
N. Nii et me kirjutada suur O n.
Ma lihtsalt täita mõned lüngad. See on vaid ruudustik toorikud.
Aga parimal juhul lineaarse otsing, 7 oleks võinud kohe alguses nimekirja,
ja Sean võis hakkasin otsima alguses nimekirja.
Nii et kui te kasutate lineaarset otsing ja lihtsalt kontrollida vasakult paremale või äkki paremalt vasakule -
nad samaväärne - parimal juhul mitu sammu võiks lineaarne otsing,
nagu Sean algoritm, võtma? Just 1 samm.
>> Nii et ma lähen ütlen, et see omega märke.
See on lihtsalt kapitali omega.
Omega on lihtsalt seksikas viis öelda parimal juhul sõiduaega.
Nii et parimal juhul on käigu aeg üheetapiline või pidev sammude arv -
1 Sel juhul - kuid halvimal juhul suur O, see on tegelikult n samme.
Ja see siin, teeta, me tegelikult ei kavatse vaadata kohe.
See ei ole seotud selle konkreetse näite.
Aga nüüd proovime binaarne otsing.
Halvimal juhul koos Kahendotsingupuu, kui palju samme ta kavatseb võtta, et leida number 7
või mis iganes me otsime? >> [Üliõpilane] Logi n.
Ikka läheb samamoodi n sest nagu Alex sai õnnetu
kui me tõesti töötas läbi probleem metoodiliselt
ja ta ei leidnud number 7 kuni viimase ukse vaatas ta,
kuigi, õiglus, sai ära visata teatud uksi mööda teed,
Kahendotsingupuu halvimal juhul on töötamise aeg log n.
Ja veel, mis räägib selle jagamisel ja vallutavad.
Aga kuidas parimal juhul?
Ja Alex tegelikult kogenud, et parimal juhul õigus, kui ta tuli lavale.
Mitu sammu ei et võtta Kahendotsingupuu? >> [Üliõpilane] 1.
1, lihtsalt sellepärast, et ta vedas.
Aga sellest pole midagi, sest omega viitab parimal juhul stsenaariumid,
Parimal juhul sisendid, isegi kui see on lihtsalt juhuslik loll õnne.
>> Nüüd on see liiga läheme lihtsalt selline, jäta tühjaks nüüd.
Kuidas nüüd mull sorteerida?
Halvimal juhul koos mull sorteerida, kõik on vastupidises järjekorras,
nii et me peame tegema palju vahustamine.
Aga kui palju samme on, et aega võtab halvimal juhul? >> [Üliõpilane] N ruudus.
See oli n ruudus, sest kui sa mõtle selle peale,
Kui loend on täiesti tagurpidi - 8 on siin, 1 on siin -
kui asi hakkab mull, number 8 saab liikuda nii, nii,
Nii sel viisil, kuid kus on number 7 halvimal juhul?
Siin ta on ikka seal. Nii et me peame tegema seda ikka ja jälle.
Ja see on koht, kus saame n samme, siis n - 1 samme, siis n - 2 sammu.
Ja kui sa võtke minu sõna see - et kui sa sellist korrutada see läbi,
see on umbes n ruudus lõpuks mõned muud tingimused, et me lihtsalt ignoreerida nüüd -
siis halvimal juhul mull sorteerida on n ruudus, võta või jäta.
Aga kuidas parimal juhul koos mull sorteerida?
Milline on parim stsenaarium? Kõik numbrid on järjestatud juba.
Ja milline oli heuristiline olen kasutanud, trikk Ma kasutasin,
mõistma, et ma olin teinud ühtegi tööd ning seetõttu lõpetage varakult?
[Üliõpilane] Vaata seda üks kord. >> Vaata seda üks kord. Aga mida ma teha mööda teed?
Olin jälgida, kui palju vahetuslepingud tegin.
Ja ma sain aru, kui ma ei ole loendatud tahes vahetuslepingute minu sõrmede, siis ma olen teinud ühtegi tööd.
Ma kindlasti ei tohiks proovida teha mingit tööd jälle, et ma saaks lihtsalt lõpetada.
>> Nii et parimal juhul mull sortida, kui loend on juba sorteeritud,
mida sa ütleksid omega märke on, parimal juhul sõiduaega?
See on lihtsalt n. Me peame tegema mõned tööd, kuid meil on ainult teha 1 jalutuskäiku väärt töö.
Ja ka siin ma jätan selle osa tühjaks.
Ja nüüd valik omamoodi.
Valik omamoodi oli mulle kitkumise väikseim isik ikka ja jälle.
Ja mida me ütleme töötamise aeg see oli?
See oli n ruudus halvimal juhul.
Ja kahjuks, parimal juhul on see ka n ruudus
sest ma ei ole mingi kõiketeadev vaade kogu maailmas;
Ma tean vaid pärast täielikku iteratsiooni, et olen tõepoolest leidnud väikseim inimene.
Nii et valik omamoodi selline nõme selles mõttes,
vaid tagurpidi on see on selline intuitiivne.
See on päris lihtne kodeerida üles, sest kõik mida sa pead tegema, on kirjutada paar nested jaoks silmuseid,
tavaliselt, et läheb läbi otsivad väikseim element
ja siis paneb väikseim element, kui ta kuulub lõpus nimekirja.
Nii et ka siin saab olema kompromiss.
Aega kulub teil mõelda ja tegelikult arendada midagi kirjutada koodi
võiks väga hästi võtab rohkem aega, kui soovite paremat algoritmi ja kiiremini tulemusi.
>> Aga kui sa tõesti just selline kood midagi välja kiire ja räpane
ja just selline võtma lollim võimalik idee saab mõelda,
et võib kuluda paar minutit koodi, kuid suurte andmekogumite
oma algoritm võib kuluda tundi joosta.
Ja isegi mina Magistriõppe oleks mõnikord teevad need kompromissid.
Oleks 03:00, üritasin analüüsida mõningaid väga suure andmekogumi
julgeolekuga seotud teadusuuringud ma tegin, ja see oli kas kulutada 5 minutit
tutistamine minu programm, et analüüsida andmeid ja magama minna
või veeta 8 tundi saada see just nii see töötab koheselt ja ei lähe magama.
Ja nii ka seal see on selline teadlik otsus.
Vähem arengu ajal rohkem magada.
Tagasivaates Ma ilmselt ei peaks julgustama, et
kui eesmärk siin on optimeerida kvaliteedi kood,
kuid liiga reaalses maailmas on väga mõistlik kompromiss.
Vähem aega, jõudlus väiksem või vastupidi.
Nii et siin me lõpuks saada võimalus rääkida teeta.
Theta märke on midagi arvuti teadlased avab vestluses
kui suur O ja omega juhtub olema sama.
Sa ütled teeta tõesti saata sõnum, et see on selline tihe seotud.
Ükskõik, kas stsenaarium on hea või halb, see on n ruudus.
Nii et see lihtsalt ei ole olulised need lood siin.
Insertion sorti on viimane me vaatasime,
kus ma olin lihtsalt lisada kõik õiges kohas.
Parimal juhul milline oli jooksmine on asetatud omamoodi nagu me nägime seda siin?
[Üliõpilane] parimal juhul? >> Parimal juhul.
>> See oli n sest parimal juhul kõigile sorteeritud,
ja Sammy ja keegi tõesti olnud üldse liikuda.
Nad olid juba oma õiges kohas.
Nii sisestamise omamoodi parimal juhul on sellisel juhul n.
Aga halvemal juhul see on selline n ruudus. Miks?
Kui minu nimekirja inimestel on vastupidises järjekorras,
Ma esimest korda alustada number 8 ja ma sisestan teda õigesse asendisse, mis on siinsamas.
Ma nagu liikuda külg. Need kutid sortimata, ta on järjestatud.
Aga nüüd ma juhtun leidma kes järgmine? >> [Üliõpilane] 7.
7 halvim, sest see on vastupidises järjekorras.
>> Nii et siin on 7. Kust 7 kuuluvad? Kindlasti minu taga.
Aga nüüd 7 kuulub tegelikult ei ole kohe minu taga aga taga number 8,
nii et ma pean ütlema, et "Vabandage, nr 8, kas te saaksite liikuda sel viisil
"Et teha ruumi 7?" Nüüd ma esineb 6.
"Oh, vabandage mind, nr 8 ja nr 7, saate liikuda, et teha ruumi 6?"
Nii et teiste sõnadega, koos sisestamise sorteerida, kuigi ma ei tee palju liikumist,
inimesed minu selja taga teevad palju tööd, ja et ju maksma kellegi aega.
See läheb maksma arvuti aega.
Nii et kui tegemist on asetatud omamoodi me veel kannatama.
Kui hakkate lisades kuni koguarvust samme, me lõpuks lööb umbes n ruudus
sest need kutid on vaja teha ruumi inimeselt lisatakse tagasi sellesse nimekirja.
Ja nii sel juhul teeta on lihtsalt ei kohaldata eelkõige lugu käepärast.
See on kõik tore ja hea. Meil on need 3 erinevat võimalust rääkimise sõiduaega.
Kuid mida see tegelikult tähendab reaalselt, kui me tegelikult püüame kood kuni algoritm?
>> Las ma ettepaneku, et seal on isegi parem algoritm seal
et endal on mõned kompromissid.
Me läheme seda kutsuda liita omamoodi, ja see on omamoodi see maagiline algoritm
et lihtsalt toimib kiiremini kuidagi, ja see on nii lihtne väljendada, vähemalt pseudokoodi.
Rakendamise algoritmi Tarkvaraprojekteerimise saab olema järgmine.
Kui olete antud n elementi - n arvu n inimesed, olenemata - esimene seal on terve mõistuse kontrolli all.
Kui n on väiksem kui 2, liita omamoodi lihtsalt peatub. See käib nii rääkida.
Miks te lõpetate kui n on väiksem kui 2? >> [Kuuldamatu õpilase vastus]
Õigus. Ja jälle n ei ole nimestikus numbrit, n on suurus nimekirjast.
Kui n on väiksem kui 2, mis tähendab, et teie loend on kas 1,
kuhu ilmselt järjestatud kui see on 1 number,
või 0, mille puhul pole midagi sorteerida,
seega peame sellist tugipunkti.
Kui loend on nii lühike, et seal on lihtsalt midagi teha, sõna otseses mõttes ei tee midagi. Tagasi.
Vastasel sortida vasakul pool elemendid, seejärel sortida paremal pool elemendid,
siis liita 2 järjestatud pooleks.
>> Selline tundub veidi petavad mille ma küsin sinu käest, kuidas sortida elemendid
ja sa räägid mulle, "Sorteerimine vasakul pool, sorteerida paremal pool."
Ma olen nagu, "Olgu. Kuidas sorteerida vasakul pool?"
"Sorteeri vasakul pool vasakul pool, sorteerida paremal pool vasakul pool, ja siis teinud."
Sa oled selline tsükliliselt määratleda, mida tähendab sorteerida,
aga tuleb välja, et on tegelikult geniaalne käesolevas asjas.
See ei ole tõesti see nõiaring, et kunagi lõpeb
sest see ei lõpe, kui? >> [Üliõpilane] Kui jõuad 1 asi.
Kui jõuad 1 asi.
Nii et kuigi võite alustada 8 inimest ja ma ütlen, "Sorteerimine vasakul pool need inimesed,
need 4 inimest, "siis ma ütlen:" Kuidas sorteerida vasakul pool? "
"Noh, sorteerida 2 inimest siin." Ja siis oled nagu, "Olgu."
"Kuidas sa sortida vasakul pool need inimesed?"
"Just sorteerida seda 1 inimene siin." Mis on geniaalne ilmutus nüüd?
Ma pean sortida 1 inimene. Valmis. Ma ei pea tegema muud tööd.
Aga nüüd on mul sortida see inimene, kuid nad ühele isikule, pole midagi teha.
>> Nii maagiline ilmselt on selles Kolmas samm: ühendada järjestatud pooleks.
Nii et ühendada omamoodi võtab see suurepärane ülevaade, et kui sa murda suur probleem alla
sisse 2 väiksemat, identselt suurusega probleeme
ja siis lihtsalt selline liim väiksem lahendusi koos lõpus,
Pakun, et me saame teha palju, palju parem [koputades heli]
kui mõni valik omamoodi või sisestamise omamoodi.
Ma olen tegelikult unustades, et pool tundi, aga ma tõesti ei tea, mis toimub
väljaspool täna. [Whirring heli] [naer]
Nii et vaatame, kas me näeme seda on vähe abi meie sõber Rob Bowden.
Seal on 2 suurt sammu protsessis ühendamise omamoodi.
Esiteks, pidevalt jagada nimekirja tassi pooleks
kuni meil on hunnik nimekirjad vaid 1 tass neid.
Ärge muretsege, kui loend sisaldab paaritu arv
ja te ei saa teha täiesti selgepiiriline nende vahel.
Lihtsalt suvaliselt valida, millist nimekirja lisada pildi tassi sisse
Nii et olgem jagada neid nimekirju.
Nüüd meil on 2 nimekirju.
Nüüd on 4 nimekirju.
Nüüd on meil 8 nimistut, mille ühe tassi iga nimekirja.
Nii et see on mu 1. etapp.
Sest 2.etapp me korduvalt ühendada paari nimekirjad kasutades ühendamise algoritm oleme õppinud varem.
Ühinevad 108 ja 15 on lõpuks nimekiri 15, 108.
Ühinevad 50 ja 4 me lõpetame 4, 50.
Ühinevad 8 ja 42 me lõpetame 8, 42.
Ja ühineva 23 ja 16 me lõpetame 16, 23.
Nüüd kõik meie nimekirjad on suurusega 2.
Pange tähele, et iga 4 nimekirjad on sorteeritud,
nii saame alustada ühinevad paari nimekirjad uuesti.
Ühinevad 15 ja 108 ja 4 ja 50 kõigepealt võtta 4, siis 15,
siis 50, siis 108.
Ühinevad 8, 42 ja 16, 23 me esimest korda võtma 8, siis 16,
siis 23, siis 42.
Nii et nüüd on meil vaid 2 nimekirjad suurus 4, millest igaüks on järjestatud.
Nii et nüüd me koondada need 2 on loetletud.
Esiteks võtame 4, siis võtame 8, siis me võtame 15
ja 16 ja 23 ja 42 ja 50 ja 108.
Ja me oleme valmis. Meil on nüüd järjestatud nimekirja.
>> Rob oli selline ära midagi, mida me veel teinud ei ole.
Arvati, kuid me tegelikult ei tee seda.
Ta tegi midagi füüsiliselt koos tassi, mis viitab
ta oli kulutuste mõnda ressurssi peale aja. >> [Üliõpilane] Space. >> See oli ruumi.
Asjaolu, et ta oli selline bi-taseme tabeli, kus oli ruumi siin
ja ruumi siin all tegelikult tähendab, et ta kasutab kaks korda nii palju ruumi
kui mõni meie algoritmid siiani - sisestamise sorteerida, mull sorteerida, või valik omamoodi -
kuid ta oli võimendades seda lisaruumi selline käik asju edasi ja tagasi
hoides asjad korras.
Ja kuigi see tundub saime järjestatud loetelu, mis tundus see võttis aega.
Tegelikult mida Rob tegin oli täpselt see algoritm.
Ta võttis esimest korda probleemi suurus n, jagas selle vasakul pool ja paremal pool.
Siis ta kolis karikatega. Siis ta kordas, et protsess.
Ta jagas 4 jagatakse 2 seeriat 2 üle siin ja siin.
Siis ta kordas, et protsess ja jagatud 2 arvesse 2 komplekti 1 iga nende eri tassi.
Ja see, kui geniaalne võimalus tekib.
Sel hetkel on lugu, Rob oli 8 nimekirjad suurus 1,
mis kõik on järjestatud juba.
>> Nii siis mida ta edasi teha?
Paarikaupa ta võttis seda järjestatud nimekirja ja seda järjestatud nimekirja ja ühendada neid.
Siis ta võttis selle ühe ja liitis need, siis see üks ja liitis need,
siis see üks ja ühendatakse neid.
Ja siis mida ta järgmisena tegema?
Ta siis uuesti ühendada suuremate nimekirjade ja seejärel uuesti ühendati suurem nimekirju.
Ja kui sina arvad sellest lihtsalt intuitiivselt nüüd, mida ta tegelikult teeb?
Ta oli jagades probleemi pooleks, pooleks, pooleks, pooleks
selleks, et saada need super väike nimekirju.
Siis ta oli selline kombineerimine double, double, double, double.
Nii ta teeb kaks korda nii palju tööd kui oleme näinud seni
koos midagi seotud jaga ja valitse, kuid pole hullu.
Kaks korda nii palju tööd ei ole nii suur asi. See on lihtsalt konstandiks.
Ja palju nagu meie aritmeetiline avaldis enne, ma lihtsalt läheb maha kriipsutama pidev tegurid
nagu korda 2. Keda huvitab? Kui see 2 miljardit korda 2, see on veel palju samme.
Nii et see ühendamine samm tundub olevat Võtmeküsimuseks.
Lähme käime läbi selle lihtsalt arvuliselt enne - Oh, see on mitte jätkata veel.
Lähme käime läbi selle arvuliselt vaid tegelikult näha, kuidas see mängib välja.
See on enamasti natuke vaese mehe animatsioon.
Teeme ettepaneku seda.
Sõiduaega ühendamise omamoodi - me lihtsalt vaja viis räägi sellest.
See ei ole matemaatika, see on lihtsalt selline sisutihe viis väljendada ennast.
Nii T näitab aega ja n on mis? >> [Üliõpilane] suurus -
>> [Malan] Probleemi ulatuse, inimeste arvu.
Nii et ma väidan, et sõiduaega sorteerida n inimesed ei kavatse olla 0 aega
kui n on vähemalt 2, sest kui sul on 1 tass või ei tassi, siis pole midagi sorteerida.
Aga üldiselt ma lähen ettepaneku, et sõiduaega sorteerida n elementi
saab olema aeg, mis kulub, et sorteerida vasakul poolel pluss paremal pool
pluss - mis see veel + n? >> [Üliõpilane] Merge omamoodi.
[Malan] See on tegelikult ühinevad, sest kui sul on n / 2 elementi siia
ja teil on n / 2 elementi siia, kui palju aega läheb aega, et need ühendada?
Just nagu Rob, sa pead sikutama see siin, võibolla sikutama üle siin,
sikutama siia, kisu siia, kisu siin.
Sa pead puudutada iga tassi korraga.
Ja kui seal on 4 tassi pluss 4 tassi, mis on 8 tassi
või üldisemalt, 8 n tassi.
Nii ühineva samm saame väljendada kui n,
ja mis sõna otseses mõttes tähendab seda, mitu korda Rob füüsiliselt puudutada
üks neist vahtpolüstürool cups.
Nii et olgem nüüd teha suvalise näite.
Kui seal on 16 tassi, mis on töötamise aeg sorteerimine, kasutades Rob algoritm, 16 tassi?
See on 2 korda, kui palju aega kulub, et sorteerida 8 tassi
sest meil on 8 tassi siia, 8 tassi siin.
Ma ei tea, kui kaua see võtab, nii et me oleme üldistades seda T hetkel.
Kes teab, mis see on?
Aga nüüd ma saan omamoodi rekursiivselt või korduvalt küsida sama küsimuse.
Kui palju aega läheb aega, et sortida 8 tassi?
8 tassi ma ütlen võtab palju aega kulub, et sorteerida 4 tassi pluss 4 tassi,
siis ühinevad nad kokku.
Olgu. Me sattumist tsükkel juba. Kui kaua läheb aega, et sortida 4 tassi?
Aega kulub sortida 4 tassi on 2 tassi pluss 2 tassi sorteerimine pluss ühinevate protsessi.
Olgu. Kui kaua läheb aega, et sortida 2 tassi?
2 tassi on palju aega kulub, et sortida 1 tass pluss aeg, mis kulub, et järjestada ühe tassi
pluss palju aega kulub, et ühendada, mis on vaid 2.
>> Olgu. Viimane küsimus. Kui kaua läheb aega, et sortida 1 tass?
Siin on aluspõhimõtted, et me ennustasime me tahaks tabas varem.
Asjaolu, et ta ei võta tööle üldse sorteerida väikseim probleeme
tähendab, et nüüd, omamoodi algkool stiil,
saame lihtsalt minema hakata ühendades need numbrid uuesti sisse
Me teame nüüd, mida T 1 on, et ma saaks ühendada 0 T 1.
See annab mulle vastuse T 2, mis ma siis saate ühendada kõrgemal.
See annab mulle T 4, mida ma ei ühendan kõrgemal.
See annab mulle T, 8., mida ma ei ühendan kõrgemal.
Ja kui ma tõesti välja, et matemaatika, ühendades need vastused,
Siis ma saan T 16 on 64.
Ja mida see 64 koosneb?
Kui T on 16, jah, see on 16 korda 4.
Nii ma väita nüüd, et töötamise aeg see asi nimega liita omamoodi -
ja see saab olema fanciest on need, mida me oleme näinud siiani -
läheb nimetatakse n log n
sest kui mitu korda võib röövida jagada terve hunnik tassi poole? Logi n.
See on sama nagu telefoniraamat Näiteks see sama ise loendada näiteks.
>> Mitu korda saab sa jagad midagi pooleks?
Kuid seal on see ühineva samm.
Sa oleks võinud jagada tassi pooleks ja jälle ja jälle,
kuid iga kord, kui lähed on ühendada.
Ja me varem öelnud, et ühineva n tassi võtab n samme
sest sa pead kisu tassi, kisu tassi, ja sa pead puudutada iga tassi üks,
nagu Rob tegi.
Nii et kui me teeme midagi log n korda ja me teeme n asju Igal neist iteratsioone
kõik need halvings, meil on n korda log n.
Nii et kui me lülitame sisse 16 Selles näites 16 korda logi 16. -
ärge muretsege, miks see nii on nüüd, sest ma ei ole koostatud põhi -
kuid samamoodi baasi 2 16 on 4, 16 korda 4 on 64.
Aga vastupidi, kui me kasutaksime mull sorteerida või valik omamoodi või sisestamise omamoodi 16 numbrid,
milline oleks sõiduaega olnud, kui n on 16?
Oleks 16 ruudus, mis on 256, mis isegi kui sa ei ole päris järginud kõiki matemaatika,
256 on suurem kui 64. See on tõesti maagiline Buffee siin.
Ja mõistma, et töö kaudu see väiksemates näiteid nagu te edasi pset
muudab kõik palju selgem.
Aga mida see tegelikult tähendab nii tunda seda algoritm on selline:
Kui me tegelikult vaadata ühendamise omamoodi siin - las ma tõmban ta üles selles aknas siin -
see on veidi teistsugune näide, kus meil on kõik 3 neist algoritme -
mull, valik ja ühendamine - lihtsalt kõrvuti.
>> Nad on kõik algas juhuslikult baari, ja see on hea.
Keegi ei ole oluline eelis teiste üle.
Ma lähen hetke pärast käsku kõik need animatsioonid - Start Start Start -
nii kiiresti kui saan, nii et umbes nii, nad kõik algavad samal ajal,
ja Vaatleme et mull sorteerida on Halvima sõiduaega on mis? >> [Üliõpilane] N ruudus.
N ruudus. Valik omamoodi halvim juhtum sõiduaega on? N ruudus.
Ja ühendada sorteerida on ilmselt - isegi kui sa ei ole päris järgima kõiki matemaatika nüüd,
siis see muutub palju intuitiivsem aja jooksul - on, me väidame, n korda log n.
Ja kuna log n on rangelt väiksem kui n kui meil on suured numbrid,
n korda log n on väiksem kui n korda n või n ruudus.
Mida see tunne on tegelikult olla parem algoritm nii sõiduaega,
n korda log n erinevalt n ruudus? Läheb lahti. Klõpsake nuppu, käsku.
>> See on, mida see tähendab kasutada midagi ühendamise omamoodi.
Meil on praegu. Vaatame, mis juhtub siin.
[Chuckles] Kelle raha on mull sorteerida?
See sõltub pigem sisend mõnikord.
Vaatame.
Tule. Tundub, nagu ta on järele jõudmas. >> [Üliõpilane] Mine, mull sorteerida!
[Õpilased vulisev]
[Malan] Jah, jah.
[Õpilased vulisev] Mine, mine, mine!
[Kõik cheering] [aplaus]
Nii et nüüd vaid 1 viimane, lõplik demo, kui see on natuke keeruline wrap meelt umbes matemaatika
või omamoodi visualiseerimine seal saab tegelikult kuulata kiirused
erinevate algoritmide erinevalt.
See on animatsioon keegi teinud, et tegelikult kaastöötajad kõlab
protsessiga vahetada ja tulpade kõrgust.
Nagu me näeme siin, seal on veel mõned sorteerimise algoritme seal, et inimesed on välja mõelnud.
See esimene saab olema sisestamise järgi, ja see lendab läbi
ja teile kuuldav tunne kuidas neid erinevaid algoritme töö.
Siin on sisestamise omamoodi.
[Elektroonilise piiksumist]
[Malan] mull sorteerida.
[Kiiremini elektroonilise piiksumist]
[Malan] Valik omamoodi.
[Kiiremini elektroonilise piiksumist]
[Malan] Merge omamoodi.
[Elektroonilise piiksumist]
[Piiksumist aeglustab] [naer]
[Malan] Gnome omamoodi.
[Elektroonilise piiksumist]
>> See on CS50. Näeme järgmisel nädalal. [Aplaus ja cheering]
>> [CS50.TV]