>> [Musiikki soi]
>> DAVID J. MALAN: Okei.
Joten tervetuloa takaisin.
Tﺣ۳mﺣ۳ on CS50, ja on viikon lopussa kolme.
>> Joten muistaa aiemmin useita viikkoja, olemme viettﺣ۳ﺣ۳ melko vﺣ۳hﺣ۳n
aikaa C, ohjelmointi, syntaksi.
Ja se on aivan normaalia, jos olet vielﺣ۳ kamppailee Harjoitus 2, on
hakkaa pﺣ۳ﺣ۳tﺣ۳si seinﺣ۳ﺣ۳n.
Se on arvoituksellinen nﺣ۳kﺣﭘinen virheilmoituksia ja bugeja ettﺣ۳
ei aivan jahtaamaan.
Koska varma, ettﺣ۳ vain Muutaman viikon kuluttua voit muistella
asioita, kuten Caesar ja [? V-genair,?] ehkﺣ۳ jopa Crack, ja
ymmﺣ۳rtﺣ۳ﺣ۳, miten pitkﺣ۳lle olet tullut lyhyen ajan kuluessa.
Joten jos se yhtﺣ۳ﺣ۳n lohduttaa, roikkua siellﺣ۳ nyt.
>> Tﺣ۳nﺣ۳ﺣ۳n kuitenkin alamme siirtyminen asioita korkeammalla tasolla.
Ja alamme itsestﺣ۳ﺣ۳n selvﺣ۳nﺣ۳, ettﺣ۳ te tiedﺣ۳tte, miten ohjelma, tai
ainakin alkaa ettﺣ۳ viihtyvyyteen.
Ja alamme pohtia, miten voimme edetﺣ۳ ohjelmien suunnitteluun lisﺣ۳ﺣ۳
tehokkaasti.
Miten voimme edetﺣ۳ optimoimalla tehokkuuden algoritmit, ja
yleensﺣ۳ ratkaista enemmﺣ۳n mielenkiintoisia ongelmia.
Ja alkaa itsestﺣ۳ﺣ۳n selvﺣ۳nﺣ۳, ettﺣ۳ jos haluaisimme, voisimme koodata mihin tahansa
esimerkkien meillﺣ۳ on mielessﺣ۳.
Joten tﺣ۳nﺣ۳ﺣ۳n, emme kosketa nﺣ۳ppﺣ۳imistﺣﭘﺣ۳ minkﺣ۳ﺣ۳nlaiseen koodia.
Se tulee olemaan paljon korkeampi, ja lopulta noin ongelmanratkaisuun.
>> Joten pﺣ۳ﺣ۳stﺣ۳ tﺣ۳hﺣ۳n pisteeseen, haluaisin ehdottaa ettﺣ۳ seuraavat seitsemﺣ۳n
suorakaide edustaa seitsemﺣ۳n ovien takana jotka ovat koko joukko
numerot, joista on numero 50.
Saanen projisoida tﺣ۳mﺣ۳ tﺣ۳stﺣ۳ nﺣ۳ytﺣﭘn myﺣﭘs tﺣ۳ﺣ۳llﺣ۳.
Ja ehdottaa, ettﺣ۳ meidﺣ۳n vapaaehtoisen auttaa lﺣﭘytﺣ۳mﺣ۳ﺣ۳n minua numeron edessﺣ۳
Internet tﺣ۳ﺣ۳llﺣ۳ nﺣ۳hdﺣ۳.
Tule ylﺣﭘs, loistokunnossa.
Selvﺣ۳.
Mikﺣ۳ sinun nimesi on?
>> JENNIFER: [ﺣ۳ﺣ۳netﺣﭘn]
>> DAVID J. MALAN: Anteeksi?
>> JENNIFER: Jennifer.
>> DAVID J. MALAN: Jennifer.
Okei, Jennifer.
Hauska tavata.
Tule ylﺣﭘs.
Joten nﺣ۳mﺣ۳ tﺣ۳ssﺣ۳ ovat seitsemﺣ۳n ovea, ja mitﺣ۳ Haluaisin sinun tekevﺣ۳n meille tﺣ۳ﺣ۳llﺣ۳,
edessﺣ۳ kaikki luokkatoverit, on lﺣﭘytﺣ۳ﺣ۳ meidﺣ۳t numero 50.
Voit lﺣﭘytﺣ۳ﺣ۳ useita, voit kurkistaa jokin nﺣ۳istﺣ۳ ovet yksinkertaisesti koskettamalla
yhdellﺣ۳ ovet, ja se paljastaa sen numero.
Ja katsotaanpa kuinka nopeasti Lﺣﭘydﺣ۳t meidﺣ۳t numero 50.
>> 15.
16.
50.
Hienosti tehty.
Selvﺣ۳.
Aplodit Jennifer.
>> [APPLAUSE]
>> Selvﺣ۳.
Joten mikﺣ۳ oli strategian lﺣﭘytﺣ۳ﺣ۳ numero 50?
>> JENNIFER: Tuota, ajattelin ehkﺣ۳ jos -
[ﺣﺣ۳netﺣﭘn]
>> DAVID J. MALAN: Oh.
Anna se yksi toinen.
Joten oli teidﺣ۳n strategia lﺣﭘytﺣ۳ﺣ۳ numero 50?
>> JENNIFER: Olen siis vain alkaa alkaa nﺣ۳hdﺣ۳, mitﺣ۳ ensimmﺣ۳inen numero
oli, ja sitten ajattelin, ehkﺣ۳ jos he lajitellaan, minﺣ۳ vain pitﺣ۳ﺣ۳
napauttamalla ylempﺣ۳nﺣ۳?
>> DAVID J. MALAN: OK.
Ja nﺣ۳ytﺣ۳mme lﺣﭘytﺣ۳neen ettﺣ۳ on kyse.
Vaikka nyt Taitat kerrokset vain vﺣ۳hﺣ۳n, ja haluat mennﺣ۳
eteenpﺣ۳in ja paljastaa muiden ovien olet voinut valita?
>> JENNIFER: Voi, rakas.
>> DAVID J. MALAN: Ah.
>> JENNIFER: Joten olen vain onnekas.
>> DAVID J. MALAN: Sait onnekas.
Selvﺣ۳.
Joten ei paha.
Mutta se on mielenkiintoista oivalluksia, eikﺣﭘ?
Jos oletetaan, ja teit saat, todellakin hieman onnekas siellﺣ۳.
Mutta jos oletetaan, ettﺣ۳ luvut olivat lajitellaan, voit olla tﺣ۳smﺣ۳llisempi
siitﺣ۳, miten se vaikuttaa kﺣ۳ytﺣﭘstﺣ۳si?
>> JENNIFER: Joten jos ne lajitellaan, I Ajattelin pienimmﺣ۳stﺣ۳ isoimpaan.
>> DAVID J. MALAN: OK.
>> JENNIFER: Tai jos tﺣ۳mﺣ۳ pﺣ۳ﺣ۳tyi todella iso, sitten suurimmasta pienimpﺣ۳ﺣ۳n.
>> DAVID J. MALAN: OK.
Joten suurimmasta pienimpﺣ۳ﺣ۳n, tai pienimmﺣ۳stﺣ۳ isoimpaan.
Mutta haluan ehdottaa, kai oli mennyt epﺣ۳onninen, ja olettaa, ettﺣ۳ ne
ei, itse asiassa, lajitellaan, kuinka moni ne ovet ehkﺣ۳ sinulla on ollut kurkistaa
jﺣ۳ljessﺣ۳, ettﺣ۳ pahimmassa tapauksessa?
>> JENNIFER: Kaikki.
>> DAVID J. MALAN: Kaikki.
Joten yleistﺣ۳ﺣ۳, ettﺣ۳ n.
Siellﺣ۳ sattuu olemaan 7, mutta katsotaanpa lisﺣ۳ﺣ۳ yleisesti sanoa siellﺣ۳ n ovet
nﺣ۳yttﺣﭘ tﺣ۳stﺣ۳.
Joten pahimmassa tapauksessa olisit katsoa taakse 7 ovien tai n ovet.
Ja niin tﺣ۳mﺣ۳ todella on, se on vﺣ۳hﺣ۳n onnea tﺣ۳nﺣ۳ﺣ۳n, mutta se on todella lineaarinen
algoritmi lajittelee, vaikka olivat erﺣ۳ﺣ۳nlainen ohita ympﺣ۳rille.
Onko tﺣ۳mﺣ۳ reilua?
>> JENNIFER: Joo.
>> DAVID J. MALAN: No, anna minun nﺣ۳hdﺣ۳, jos Strategian muutokset jos muutan meitﺣ۳
meidﺣ۳n toinen esimerkki tﺣ۳ﺣ۳llﺣ۳ 7 eri ovet.
Samat numerot, mutta tﺣ۳mﺣ۳ kun ne lajitellaan.
Minkﺣ۳ strategian tﺣ۳ﺣ۳llﺣ۳ tulee olemaan, yrittﺣ۳ﺣ۳ laittaa jﺣ۳rkesi, mitﺣ۳
muut numerot olivat -
>> JENNIFER: OK.
>> DAVID J. MALAN: - aikaisemmin?
>> JENNIFER: Aloitetaan ensimmﺣ۳isen kanssa.
>> DAVID J. MALAN: Okei.
Aloita ensimmﺣ۳inen.
4.
Nyt jos olet menossa, ja miksi?
>> JENNIFER: 4 on todella pieni.
Joten jos he tavallaan ehkﺣ۳ pienin suurimpaan, sen pitﺣ۳isi
olla kaksi kertaa, ja -.
>> DAVID J. MALAN: OK.
Katsotaan, mikﺣ۳ luulet?
>> JENNIFER: Kokeile viimeinen.
Nice.
>> DAVID J. MALAN: Erittﺣ۳in hienosti tehty.
Selvﺣ۳.
>> [APPLAUSE]
>> DAVID J. MALAN: OK.
Joten olet juuri tekemﺣ۳ssﺣ۳ tﺣ۳tﺣ۳ hirvittﺣ۳vﺣ۳n, koska olet
tekee sen hyvin.
Joka jﺣ۳ttﺣ۳ﺣ۳ meidﺣ۳t pysty tehdﺣ۳ tiettyjﺣ۳ kohtia.
Joten yrittﺣ۳ﺣ۳ heittﺣ۳ﺣ۳ takaisin tﺣ۳nne.
>> JENNIFER: OK.
>> DAVID J. MALAN: Erittﺣ۳in hyvin tehty kuitenkin.
Joten olet aloittanut alussa, nﺣ۳it, ettﺣ۳ se oli 4, sitten
muutti loppuun.
Mutta oletetaan, et onnekas siellﺣ۳, ja kai 50
oli jossain muualla.
Mitﺣ۳ kolmas vaihe on?
>> JENNIFER: Mene takaisin alkuun.
>> DAVID J. MALAN: Mene takaisin alkuun.
OK, niin olisit koskettanut tﺣ۳mﺣ۳ ovi, joka oli 8.
Selvﺣ۳.
Joten se ei ole 50.
Missﺣ۳ olet tutkinut seuraavaksi?
>> JENNIFER: Jos en tietﺣ۳vﺣ۳t lajitellaan.
>> DAVID J. MALAN: Oikea.
No, jos et tiedﺣ۳ ne on jﺣ۳rjestetty -
>> JENNIFER: Voi, ei tiedﺣ۳, joo.
>> DAVID J. MALAN: - mutta et ole tietﺣ۳ﺣ۳, missﺣ۳ 50 oli vielﺣ۳?
>> JENNIFER: Jatka vain.
>> DAVID J. MALAN: Okei.
OK.
Jatkakaa.
OK, ettﺣ۳ voin tyﺣﭘskennellﺣ۳.
>> JENNIFER: OK.
>> DAVID J. MALAN: Nyt, jos olet vain menossa pitﺣ۳mﺣ۳ﺣ۳n menossa, mikﺣ۳ on sinun
algoritmi taantunut perﺣ۳ytyminen.
>> JENNIFER: lineaarinen -.
>> DAVID J. MALAN: Se on erﺣ۳ﺣ۳nlainen lineaarinen.
Mutta haluan ehdottaa, anna Laitan paikan pﺣ۳ﺣ۳llﺣ۳.
Saanen pﺣ۳ivitﺣ۳t sivun.
Sama numero, sama jﺣ۳rjestely, Sama ovet.
Mutta muistelen, ettﺣ۳ ensimmﺣ۳inen pﺣ۳ivﺣ۳ luokassa, kun me repﺣ۳isi puhelinluettelon
puolet, tavallaan, ja mikﺣ۳ oli Strategiamme on?
>> JENNIFER: Aloita keskellﺣ۳.
>> DAVID J. MALAN: OK.
Niin alkaa keskellﺣ۳.
Joten mene eteenpﺣ۳in ja simuloida sitﺣ۳.
Aloita keskeltﺣ۳ paljastaa, ettﺣ۳ ovi.
Joten numero 16.
Joten mikﺣ۳ olisi vahva kaveri tehnyt, joka repi puhelinluettelon kahtia,
pﺣ۳ﺣ۳stﺣ۳ seuraavalle arvaus?
>> JENNIFER: Mene tﺣ۳llﺣ۳ puolen.
>> DAVID J. MALAN: Ja miksi oikealle?
>> JENNIFER: Jos ne tavallaan pienin suurimpaan, sitten 50 olisi
tuossa lopussa.
>> DAVID J. MALAN: Hyvﺣ۳.
Tﺣ۳ysin kohtuullinen.
Joten kuten puhelinluettelossa, menet oikeutta eikﺣ۳ vasemmalle, mutta tﺣ۳ssﺣ۳
on avain takeaway.
Nyt voit heittﺣ۳ﺣ۳ pois tai repiﺣ۳ irti, puolet tﺣ۳mﺣ۳n ongelman, jolloin et
7-ovet, mutta oikeastaan ﻗﻗvain 3.
Mikﺣ۳ on noin puolet Ongelman laajuutta.
Selvﺣ۳.
Joten nyt, mitﺣ۳ olisi tehdﺣ۳, kun menet oikealle?
>> JENNIFER: Eli 16 on edelleen melko pieni, suhteessa 50, joten ehkﺣ۳ yritﺣ۳n,
kuten tﺣ۳mﺣ۳.
>> DAVID J. MALAN: Okei.
42.
Okei, joten nyt mikﺣ۳ on sinun vaisto kertoo sinulle?
>> JENNIFER: Voin heittﺣ۳ﺣ۳ pois tﺣ۳mﺣ۳ ja sitten vain -
>> DAVID J. MALAN: OK.
Hyvﺣ۳, voit heittﺣ۳ﺣ۳ pois vasen puoli siellﺣ۳.
>> JENNIFER: - valitse tﺣ۳mﺣ۳.
>> DAVID J. MALAN: Ja oikea.
>> JENNIFER: Joo.
>> DAVID J. MALAN: Joten vaikka se on vaikeaa nﺣ۳hdﺣ۳ ehkﺣ۳ kun on vain
7 ovet, ajattele nyt, johdonmukaisuus
algoritmi juuri sovellettu.
Edellisessﺣ۳ tapauksessa teit onnekas, mikﺣ۳ oli hienoa.
Mutta et kﺣ۳ytﺣ۳ heuristista, Sanoisin.
Kﺣ۳ytit tavallaan vaistosi, ja tietﺣ۳en se lajitellaan, jos ihan
pieni alussa, luonnollisesti, olemme tﺣ۳ytyy mennﺣ۳ enemmﺣ۳n oikealle.
Mutta jossain mielessﺣ۳, sinulla onnekas, koska ehkﺣ۳ tﺣ۳mﺣ۳ oli numero 100,
ja ehkﺣ۳ 50 oli keskellﺣ۳.
Ehkﺣ۳ 50 oli vielﺣ۳ tﺣ۳ﺣ۳llﺣ۳.
>> Mutta mitﺣ۳ teit hieman eri tavalla tﺣ۳llﺣ۳ kertaa oli, teit sama asia
uudelleen ja uudelleen.
Ja vﺣ۳itﺣ۳n, ettﺣ۳ mitﺣ۳ vain ei tosin vaikuttaa puhelimen
kirjaesimerkkiin, on jotain paljon enemmﺣ۳n algoritmi, ja paljon
yhtﺣ۳ erityistﺣ۳ cased.
Paljon vﺣ۳hemmﺣ۳n vaistomainen.
Joten loppujen lopuksi, miten kuvaat tehokkuutta
Ensimmﺣ۳inen algoritmi, missﺣ۳ meni vasemmalta oikealle, vs.
Toinen algoritmi tﺣ۳ﺣ۳llﺣ۳?
>> JENNIFER: Tﺣ۳mﺣ۳ olisi kuin, ehkﺣ۳ puolittaa tai jopa enemmﺣ۳n, joo.
>> DAVID J. MALAN: OK, ehkﺣ۳ jopa enemmﺣ۳n.
Katsotaanpa tyﺣﭘntﺣ۳ﺣ۳ hieman vaikeampi siitﺣ۳.
Mitﺣ۳ todella, jos jatkamme tﺣ۳tﺣ۳ logiikka, me varmasti puolittui
kﺣ۳yntiaika tﺣ۳mﺣ۳n toisen algoritmin heittﺣ۳mﺣ۳llﺣ۳ pois puolet
numeroita, mutta mitﺣ۳ teemme seuraavaksi iteraatio, kun Jennifer paljasti
toinen numero?
>> Puolitimme numerot jﺣ۳lleen ovensa.
Ja mitﺣ۳ sitten teimme sen jﺣ۳lkeen, jos oli enemmﺣ۳n ovia pelata?
Olisimme puolittaa ne ja uudelleen, ja uudestaan, ja uudestaan.
Ja tﺣ۳mﺣ۳ oli aivan kuten te kaikki seisomaan klo ensimmﺣ۳isellﺣ۳ viikolla
luokka, puoli olet istuen, puoli teistﺣ۳ istuen, puoli olet
istuen, kunnes yksinﺣ۳inen sielu seisoi.
Ja sanoimme, ettﺣ۳ ajoaika ettﺣ۳ useita vaiheita kesti oli
suuruusluokkaa mitﺣ۳?
>> SPEAKER 1: [ﺣ۳ﺣ۳netﺣﭘn]
>> DAVID J. MALAN: Eli logaritmi 2 n, tai vain yksinkertaisemmin, kirjaudu n.
Joten jotain logaritminen.
Ja kuvaaja ei ollut suora viiva ettﺣ۳ juuri huonommaksi, se oli
tﺣ۳mﺣ۳ mielenkiintoinen kﺣ۳yrﺣ۳, joka ei saada niin huono ajan.
Joten pitﺣ۳ﺣ۳ tﺣ۳tﺣ۳ ajatusta.
Katsotaanpa kiittﺣ۳ﺣ۳ Jennifer.
Kiitos niin paljon tulossa ylﺣﭘs.
Ja, yhden sekunnin.
Ei Kirjoituspﺣﭘydﺣ۳n lamput tﺣ۳nﺣ۳ﺣ۳n, mutta me ei ole CS50 stressi pallot.
>> JENNIFER: Jee.
>> DAVID J. MALAN: Okei, tﺣ۳ssﺣ۳.
Kiitos aiheutuu stressi tﺣ۳ﺣ۳llﺣ۳.
Selvﺣ۳.
Katsotaanpa, jos emme voi nyt muodollistamiseksi hieman.
Joten jﺣ۳lleen, mitﺣ۳ teimme oli pohjimmiltaan sama asia kuin teimme
ettﺣ۳ ensimmﺣ۳isellﺣ۳ viikolla.
Mutta sen sijaan pﺣ۳ﺣ۳ttyvﺣ۳t vain lineaarinen algoritmi, jota on kuvattu
aiemmin kuin tﺣ۳mﺣ۳ suora viiva, siitﺣ۳, ettﺣ۳ jos laitamme yksi ovi
nﺣ۳ytﺣﭘlle ja Jennifer olisi tﺣ۳ytynyt katsoa, ﻗﻗmahdollisesti,
takana yksi ovi.
Jos laitamme kaksi ovea, hﺣ۳n olisi nﺣ۳yttﺣ۳ﺣ۳ takana kaksi ovea.
>> Ja niin, oli tﺣ۳mﺣ۳ lineaarinen suhde koon
ongelma, eli x-akselin, ja aikaa kuluu
ratkaista y-.
Mutta kuva olin viittaamatta aiemmin oli tﺣ۳mﺣ۳ vihreﺣ۳ viiva.
Green tarkoituksella, koska se vain tuntui paremmalta.
Teoriassa algoritmin, kun me teimme sen kanssa puhelinluettelosta, kun me teimme sen
teidﺣ۳n kanssa laskenta toisiaan, ja Toisessa tapauksessa, kun Jennifer vain
teki sen tﺣ۳ﺣ۳llﺣ۳, se oli tavallaan perustaltaan paremmin.
Koska se ei ollut vain kaksi kertaa niin nopeasti.
Se ei ollut edes neljﺣ۳ kertaa niin nopeasti.
Se oli tﺣ۳ysin riippuvainen siitﺣ۳, mitﺣ۳ koko panos oli, kuinka monta
toimiin se lopulta kesti.
>> Ja niin tﺣ۳mﺣ۳ yksinkertainen ajatus, ettﺣ۳ me kaikki otimme itsestﺣ۳ﺣ۳nselvyytenﺣ۳ kanssa puhelinluettelosta,
voidaan samalla tavoin soveltaa jotain tﺣ۳llaista.
Ja tﺣ۳mﺣ۳ voisi olla rennosti tunnetaan, niin saatat
kuvitella, hajoita ja hallitse.
Ei toisin mitﺣ۳ teimme, tietenkin, kanssa puhelinluettelosta.
>> Mutta pseudokoodit muistaa, oli tﺣ۳mﺣ۳.
Joten emme tee tﺣ۳tﺣ۳ uudelleen, mutta muistuttaa ettﺣ۳ ensimmﺣ۳isellﺣ۳ viikolla, me kaikki nousi
ja sitten puolet istahti, puolet istahti, puolet istahti.
Tﺣ۳mﺣ۳ algoritmi toteutettiin hieman huijaaminen tavalla, ettﺣ۳ se
ei ollut vain yksi minua laskenta, pohjimmiltaan tehokkaammin.
Siinﺣ۳ tapauksessa, olin hyﺣﭘdyntﺣ۳en toissijaisena luonnonvarana.
Lajittele, useita suorittimia, useita aivot, useita ﺣ۳lykkﺣ۳itﺣ۳ ihmisiﺣ۳
huone auttoivat minua saada jotain lineaarinen jotain
logaritminen, jostakin punaisesta jotain vihreﺣ۳ﺣ۳.
>> Mutta tﺣ۳ssﺣ۳ tapauksessa, Jennifer voi yksin pohjimmiltaan parannella
suorituskyky hﺣ۳nen ensimmﺣ۳inen algoritmi, uudelleen, vain ajatella vﺣ۳hﺣ۳n vaikeampaa.
Ja nyt, kun on aika toteuttaa nﺣ۳mﺣ۳ asiat, mietitﺣ۳ﺣ۳n
mitﺣ۳ riviﺣ۳ koodia voit kirjoittaa niin ettﺣ۳ voit toistaa niitﺣ۳ uudelleen, ja
uudestaan, ja uudestaan, tavallaan vuonna looping tavalla.
Koska et aio olla ylellisyyttﺣ۳, kuten Jennifer teki aluksi, ettﺣ۳
vain koko joukko jossittelua ja sanoa, hmm, jos tﺣ۳mﺣ۳ ensimmﺣ۳inen numero on 4,
haluan hypﺣ۳tﺣ۳ aina loppuun.
Ooh, jos mﺣ۳ﺣ۳rﺣ۳ on liian suuri, haluan liikkua mielivaltaisesti takaisin
toiseen osaan.
Huomaat, ettﺣ۳ se tulee olemaan paljon vaikeampaa virallistaa mitﺣ۳ me ihmiset
itsestﺣ۳ﺣ۳nselvyytenﺣ۳ erittﺣ۳in kohtuullinen heuristiikka, mutta tietokone on vain
tekee mitﺣ۳ kerrot sen tehdﺣ۳.
>> Nyt tﺣ۳mﺣ۳ on erittﺣ۳in mielenkiintoinen seurauksia.
Tﺣ۳mﺣ۳ kuvaaja on tavallaan tarkoitus tavallaan hukuttaa visuaalisesti, mutta huomaa, jos
on suora viiva tﺣ۳ssﺣ۳ kuvaaja?
Missﺣ۳ on lineaarinen kuvaaja jota me kutsumme n?
No, se on tavallaan pohjaa kohti Kuvan, eikﺣﭘ?
Joten kaikki olemme tehneet on olemme tavallaan zoomataan ulos x-akselin ja
y-akseli yrittﺣ۳ﺣ۳ saada tunteen siitﺣ۳, mitﺣ۳ muita kﺣ۳yrﺣ۳t nﺣ۳yttﺣ۳vﺣ۳t.
>> Ja erityispiirteet matemaattisten ilmaisuja tﺣ۳nﺣ۳ﺣ۳n ei niin vﺣ۳liﺣ۳
paljon, mutta huomaa, ettﺣ۳ siellﺣ۳ on paljon algoritmeja, jotka ovat paljon huonommat kuin
jotain, joka on lineaarinen.
Itse asiassa n kuutioitu nﺣ۳yttﺣ۳ﺣ۳ pahalta.
2 n nﺣ۳yttﺣ۳ﺣ۳ pahalta. n potenssiin nﺣ۳yttﺣ۳ﺣ۳ pahalta.
Ja nﺣ۳emme, mitﺣ۳ joidenkin saattaa olla todellisuudessa tﺣ۳nﺣ۳ﺣ۳n.
Ja log n ei tunnu niin pahalta, mutta parempi n on logaritmi 2 n.
Mutta te tiedﺣ۳tte, se olisi ollut vielﺣ۳ ihmeellisempﺣ۳ﺣ۳, jos Jennifer, tai jos,
ettﺣ۳ ensimmﺣ۳isellﺣ۳ viikolla, oli keksittﺣ۳vﺣ۳ jotain, joka on log log n.
>> Eli toisin sanoen, on tﺣ۳mﺣ۳ koko erilaisia ﻗﻗmahdollisia ratkaisuja
ongelmia, mutta siinﺣ۳kin, ilmoitus mitﺣ۳ tulee tapahtumaan.
Kun minﺣ۳ loitontaa, mikﺣ۳ nﺣ۳istﺣ۳ kﺣ۳yrﺣ۳t tulee olemaan ehdoton
Pahin niistﺣ۳ ruudulla nyt?
Joten n kuutioitu nﺣ۳yttﺣ۳ﺣ۳ aika nyt huono.
Mutta jos me loitontaa ja nﺣ۳hdﺣ۳ enemmﺣ۳n x ja y-akseli, joka tulee
hallitsevat lopulta?
Joten se todella osoittautuu, ettﺣ۳ 2 n, ja voit selvittﺣ۳ﺣ۳ tﺣ۳mﺣ۳n vain
kytkemﺣ۳llﺣ۳ jotkut yhﺣ۳ suuria numerot, ja nﺣ۳et, ettﺣ۳ 2
n todellakin saa isompi paljon nopeammin.
Jos me todella loitontaa, 2 n algoritmi aivan perseestﺣ۳.
Siis tﺣ۳mﺣ۳ vie melko vﺣ۳hﺣ۳n aikaa
tietokone vaihtuvuus kautta.
>> Mutta nﺣ۳et ajan, erityisesti tulevaisuuden ongelma sarjaa ja jopa
opinnﺣ۳ytetyﺣﭘt, on tietosi set saa suuret, okei?
Jopa ensimmﺣ۳inen versio Facebook, kuin joukko ystﺣ۳viﺣ۳, ja
rekisterﺣﭘityneiden kﺣ۳yttﺣ۳jien saivat suuret, voit lajitella puhelimen sen ja
toteuttaa jotain lineaarista hakua, tai hyvin yksinkertainen lajittelu
algoritmi, kuten nﺣ۳emme tﺣ۳nﺣ۳ﺣ۳n.
Sinun tﺣ۳ytyy alkaa ajatella kovemmin ja vaikeampi nﺣ۳istﺣ۳ ongelmista.
Ja tyyppisiﺣ۳ ongelmia paikoissa, kuten Facebook ja Google ja Microsoft,
ja muut tyﺣﭘtﺣ۳ on juuri nﺣ۳mﺣ۳ tavallaan iso tietojen kysymyksistﺣ۳ on
yhﺣ۳ nﺣ۳inﺣ۳ pﺣ۳ivinﺣ۳.
>> Selvﺣ۳.
Joten Jennifer menestys, ettﺣ۳ toinen algoritmi, rehellisesti, hﺣ۳n teki hﺣ۳mmﺣ۳styttﺣ۳vﺣ۳n
hyvin ensimmﺣ۳isen kerran, mutta katsotaanpa kirjoittaa sitﺣ۳ onnea, jotta me
voi tehdﺣ۳ tﺣ۳ssﺣ۳ vaiheessa.
Toisessa tapauksessa hﺣ۳n velkarahalla algoritmi, joka toistuu uudestaan ﻗﻗja
uudelleen, mutta hﺣ۳n otti itsestﺣ۳ﺣ۳nselvyytenﺣ۳ tiettyjﺣ۳ oletukseen, ettﺣ۳ annoimme
hﺣ۳ntﺣ۳, mutta hﺣ۳n hyﺣﭘdyntﺣ۳ﺣ۳ joitakin yksityiskohtia toisen kerran, ettﺣ۳ hﺣ۳n ei ole
ensimmﺣ۳isen kerran.
Joka oli mitﺣ۳?
>> Tﺣ۳mﺣ۳ lista on lajiteltu.
Joten kun luettelo on lajiteltu, me vﺣ۳ittﺣ۳vﺣ۳t, ettﺣ۳ Jennifer pystyi tekemﺣ۳ﺣ۳n
pohjimmiltaan paremmin.
7 ovet, kyllﺣ۳, ei ole niin kiinnostavaa, mutta kai se olemme 7000000 ovet.
Log n on ehdottomasti menossa tehdﺣ۳ paljon, paljon
nopeammin pitkﺣ۳llﺣ۳ aikavﺣ۳lillﺣ۳.
Mutta hﺣ۳n piti olla ovet lajitellaan hﺣ۳ntﺣ۳.
Nyt otin vapauden tehdﺣ۳ se etukﺣ۳teen tietokoneen nﺣ۳ytﺣﭘllﺣ۳
tﺣ۳ﺣ۳llﺣ۳, mutta olettaa, ettﺣ۳ Jennifer tﺣ۳ytyi tehdﺣ۳ itse?
Oletetaan, ettﺣ۳ ovet kyseessﺣ۳ edustettuina tiedot tietokantaan tai
ystﺣ۳vﺣ۳t rekisterﺣﭘity Facebook, tai kaikkia verkkosivuja Internetissﺣ۳, jotka
eri verkkosivustoja ehkﺣ۳ indeksoida tai etsi yli.
>> Oletetaan, ettﺣ۳ olet juuri ollut raakadatan asettaa ja se jﺣ۳i sinulle, tai
Jennifer tehdﺣ۳ lajittelemalla?
Se pikemminkin edellyttﺣ۳ﺣ۳, ettﺣ۳ me vastaamme kysymys, hyvin, kuinka paljon aikaa
olisi ottanut Jennifer tai jopa minua, lajitella nﺣ۳mﺣ۳ numerot etukﺣ۳teen, jotta
ettﺣ۳ hﺣ۳n voisi hyﺣﭘdyntﺣ۳ﺣ۳ sitﺣ۳?
Oikea?
Koska vaikutuksia, on tietenkin jos se vie minut jonkin aikaa lajitella
numerot, jotka helkutti kiinnostaa, ettﺣ۳ olet lﺣﭘytyy useita, kuten 50 niin nopeasti,
kuten Jennifer tapauksessa, jos yli hukkua mﺣ۳ﺣ۳rﺣ۳ kokonaisaika
kesti lajittelemalla asioita etukﺣ۳teen?
>> Katsotaanpa, jos emme voi maalaa kuva tﺣ۳ﺣ۳llﺣ۳.
Minulla on koko joukko enemmﺣ۳n stressiﺣ۳ pallot, jos se auttaa
murtaa jﺣ۳ﺣ۳n tﺣ۳nne.
Ja jos et mielessﺣ۳, me tarvitsevat seitsemﺣ۳n vapaaehtoinen -
on, OK.
Wow.
Joten meidﺣ۳n ei tarvitse kﺣ۳yttﺣ۳ﺣ۳ tyﺣﭘpﺣﭘytﺣ۳ valaisimet, miltﺣ۳ se nﺣ۳yttﺣ۳ﺣ۳.
Selvﺣ۳.
Niin miten te kaksi edessﺣ۳.
Entﺣ۳ te kaksi kaverit takana.
Niin, ettﺣ۳ neljﺣ۳.
Miten sinusta edessﺣ۳ viisi, kuusi ja seitsemﺣ۳n.
Tuolla.
Ystﺣ۳vﺣ۳si osoittaa sinua ulos, niin saat palkinnon.
>> Selvﺣ۳.
Tule ylﺣﭘs.
Ja miksi emme ole sinulle miehet ovat tulleet tﺣ۳nne.
Aion antaa sinulle jokaisen numeron.
Ja mennﺣ۳ eteenpﺣ۳in ja jﺣ۳rjestﺣ۳ﺣ۳ itse identtisen mitﺣ۳
kuvattu ruudulla.
>> [Interposing ﺣﺣNTﺣ]
>> DAVID J. MALAN: Oop, sorry.
Bug.
Selvﺣ۳.
No, tﺣ۳ssﺣ۳ sitﺣ۳ mennﺣ۳ﺣ۳n.
Numero viisi.
Numero kuusi.
Yksi, kaksi, kolme, neljﺣ۳, viisi, kuusi, seitsemﺣ۳n.
Voi, tﺣ۳mﺣ۳ on hankala.
>> SPEAKER 2: Minﺣ۳ saan vain -.
>> DAVID J. MALAN: Good deal.
Selvﺣ۳.
Kiitos osallistumisesta.
>> [APPLAUSE]
>> OK.
Selvﺣ۳.
Joten meillﺣ۳ on neljﺣ۳, kaksi, kuusi, yksi, kolme, seitsemﺣ۳n, viisi.
Perfect joten meillﺣ۳ on seitsemﺣ۳n vapaaehtoisia tﺣ۳ﺣ۳llﺣ۳, jotka ovat yhtﺣ۳ leveﺣ۳
array, ettﺣ۳ me pelaamme kanssa aiemmin.
Ja pﺣ۳ﺣ۳tin seitsemﺣ۳n syistﺣ۳ joka on vain
kﺣ۳tevﺣ۳ vﺣ۳hﺣ۳n.
Ja aion ehdottaa ensin, ettﺣ۳ me lajitella nﺣ۳mﺣ۳ seitsemﺣ۳n vapaaehtoisia.
Jos haluat, ensimmﺣ۳inen, tervehtimﺣ۳ﺣ۳n vaikka.
Koska tﺣ۳mﺣ۳ tulee olemaan hankala useita minuutteja.
Esitellﺣ۳ itsenne.
>> GRACE: Hei, olen Grace.
Olen toisen vuoden opiskelija Leverett House.
>> BRANSON: Hei.
Olen Branson.
Olen fuksi Weld.
>> GABE: Hei.
Olen Gabe.
Olen juniori Cabot.
>> NEIL: Olen Neil.
Olen fuksi Matthews.
>> JASON: Olen Jason.
Olen fuksi Greenough.
>> MIKE: Olen Mike.
Olen fuksi Grays.
>> JESS: Olen Jess.
Olen toisen vuoden opiskelija Leverett.
>> DAVID J. MALAN: Erinomainen.
Selvﺣ۳.
No, kiitos kaikille Vapaaehtoiset toistaiseksi.
Ja haaste kﺣ۳sillﺣ۳ nyt on menossa olla tavallaan nﺣ۳mﺣ۳ kaverit, mutta sitten
aiomme tﺣ۳ytyy ajatella hieman kova, miten tehokkaasti me oikeastaan
ne on lajiteltu.
Joten ensin kokeilla tﺣ۳tﺣ۳.
Te voi nﺣ۳hdﺣ۳ toistensa numerot vain sijoittamalla kulmien ympﺣ۳ri.
Mennﺣ۳ eteenpﺣ۳in ja kestﺣ۳ﺣ۳ muutaman sekunnin, ja lajitella itsenne pienimmistﺣ۳
jﺣ۳ﺣ۳ suurin oikealla.
Go.
>> OK.
Hyvﺣ۳.
Se oli todella hiton nopeasti.
Nyt joku tﺣ۳ﺣ۳llﺣ۳, mikﺣ۳ oli algoritmi ettﺣ۳ nﺣ۳mﺣ۳ kaverit sovelletaan?
>> SPEAKER 1: Korkeasta suurin.
>> DAVID J. MALAN: OK.
Ainakin suurin on todella tavallaan tavoite, mutta en ole varma, ettﺣ۳ se
todella algoritmi.
Ainakin suurin ei kerro minulle askel askeleelta mitﺣ۳ tehdﺣ۳.
Niin?
>> SPEAKER 1: [ﺣ۳ﺣ۳netﺣﭘn]
>> DAVID J. MALAN: OK.
Joten jos nﺣ۳et henkilﺣﭘn pienempi kuin numerosi, sitten siirtyﺣ۳
oikea niistﺣ۳.
Niin, ettﺣ۳ nyt saada enemmﺣ۳n ilmeikﺣ۳s, enemmﺣ۳n kuin algoritmi, koska
voi sanoa, jos tﺣ۳mﺣ۳, niin se.
Joten meillﺣ۳ on jonkinlainen ehdollinen rakennelma.
Ja nﺣ۳mﺣ۳ kaverit nﺣ۳yttivﺣ۳t tehdﺣ۳ muutamia kertaa, koska jotkut teistﺣ۳ muuttanut hieman
ja etﺣ۳isyyden.
Joten oli oletettavasti jonkinlainen looping tapahtuu heidﺣ۳n mielessﺣ۳ﺣ۳n.
>> Mutta yritetﺣ۳ﺣ۳n virallistaa ettﺣ۳.
Jos te voisi palauttaa takaisin Tﺣ۳mﺣ۳n jﺣ۳rjestelyn.
Katsotaan, jos emme voi virallistaa tﺣ۳mﺣ۳n bittinen, ja sitten kysyﺣ۳, vain
kuinka tehokas tﺣ۳mﺣ۳ on?
Tietenkin, kun teemme tﺣ۳tﺣ۳ hitaammin, se tulee tuntea niin hyvﺣ۳ﺣ۳
algoritmi, mutta katsotaan jos voimme laittaa sormet tarkka vaiheet.
>> Joten te kaksi olette neljﺣ۳ ja kaksi.
Tai sitten oikea tai vﺣ۳ﺣ۳rﺣ۳ jﺣ۳rjestys?
Selvﺣ۳sti virheellinen.
Joten vaihdoin.
Nyt aion siirtyﺣ۳ sivuun ja sanoa neljﺣ۳stﺣ۳ kuuteen.
Oletko oikea tai vﺣ۳ﺣ۳rﺣ۳?
>> GABE: Oikea.
>> DAVID J. MALAN: Oikea.
Kuusi ja yksi?
Ehei.
Swap.
Niin, ettﺣ۳ kaksi swap.
Kuusi ja kolme?
Ehei.
Swap.
Kuusi ja seitsemﺣ۳n?
Nﺣ۳yttﺣ۳ﺣ۳ hyvﺣ۳ltﺣ۳.
Seitsemﺣ۳n ja viisi?
>> JESS: [ﺣ۳ﺣ۳netﺣﭘn]
>> DAVID J. MALAN: OK, vaihtaa.
Ja lajitellaan.
Selvﺣ۳.
Joten ilmeisesti ei, eikﺣﭘ?
Joten oli enemmﺣ۳n tekeillﺣ۳.
Mutta tosiaan, nﺣ۳mﺣ۳ kaverit, vaikka vain vaistomaisesti.
pidettﺣ۳vﺣ۳ liikkeessﺣ۳.
He eivﺣ۳t vain lopettaa, kun ne korjattu yksi ongelma.
So.
Itse aion olla tehdﺣ۳ sama asia.
Aion olla tavallaan taaksepﺣ۳in takaisin alkuun tﺣ۳mﺣ۳n ongelman
tai alussa joukko ihmiset, aloitamme kutsuvan heitﺣ۳.
>> Ja nyt, mitﺣ۳ pitﺣ۳isi minun algoritmi Toisessa lﺣ۳piviennissﺣ۳ on?
>> SPEAKER 1: Sama juttu.
>> DAVID J. MALAN: Sama juttu.
Ja tﺣ۳mﺣ۳, olen alkanut pitﺣ۳mﺣ۳ﺣ۳n, eikﺣﭘ?
Heti kun lﺣﭘydﺣ۳t itsesi tekemﺣ۳ssﺣ۳ sama asia uudestaan ﻗﻗja uudestaan, se on
tulossa enemmﺣ۳n kuin algoritmin ja vﺣ۳hemmﺣ۳n ihmisen vaisto.
>> Joten nyt, tﺣ۳ssﺣ۳ sitﺣ۳ taas.
Kaksi ja neljﺣ۳?
Ei.
Neljﺣ۳ ja yksi?
Ah, siellﺣ۳ oli todellakin joitakin tyﺣﭘtﺣ۳ on vielﺣ۳ tekemﺣ۳ttﺣ۳.
Sillﺣ۳ ja kolme?
Hyvﺣ۳.
Neljﺣ۳ ja kuusi?
Kuusi ja viisi?
Kuusi ja seitsemﺣ۳n?
OK, nyt tehdﺣ۳ﺣ۳n.
OK, no.
Minun tﺣ۳ytyy mennﺣ۳ takaisin.
>> Joten nyt taas, teemme tﺣ۳tﺣ۳ hieman tarkoituksella.
Ja nyt siellﺣ۳ on vain yksi aivojen tﺣ۳ytﺣ۳ntﺣﭘﺣﭘnpanosta tﺣ۳mﺣ۳n algoritmi.
Yksi CPU, jos haluatte.
Ja suoraan sanottuna, se on ainoa resurssi aiomme saada.
Ja kun emme mene takaisin nﺣ۳ppﺣ۳imistﺣﭘ ja on jotain C meidﺣ۳n
hﺣ۳vittﺣ۳minen, olemme vain ohjelman kirjoittaminen joka voi tehdﺣ۳ yksi asia kerrallaan.
Sekﺣ۳ katsoo, nﺣ۳mﺣ۳ kaverit hetki sitten, me velkarahalla kollektiivista aivokapasiteetti
kuten teitte kaverit viikolla nolla.
Joten pitﺣ۳ﺣ۳ tehdﺣ۳ tﺣ۳tﺣ۳.
>> Kaksi ja yksi.
Kaksi ja kolme.
Kolme ja neljﺣ۳.
Neljﺣ۳ ja viisi.
Viisi ja kuusi.
Kuusi ja seitsemﺣ۳n.
Tehty?
Joten olen, mutta anna minun pelata paholaisen asianajajana.
Voin, tﺣ۳llainen tietokone, joka vain teki ohittamaan tﺣ۳mﺣ۳n joukko
ihmiset, tietﺣ۳vﺣ۳t, ettﺣ۳ olen tehnyt?
>> SPEAKER 1: No
>> DAVID J. MALAN: Miksi?
Mitﺣ۳ minun pitﺣ۳ﺣ۳ tehdﺣ۳, jotta pﺣ۳ﺣ۳tellﺣ۳ ratkaisevasti, ettﺣ۳ olen tehnyt?
Luultavasti yksi syﺣﭘttﺣﭘ.
Oikea?
Koska kaikki Tiedﺣ۳n, ettﺣ۳ edellinen pass on, ettﺣ۳ korjasin virheen.
Ja se tarkoittaa, ehkﺣ۳ siellﺣ۳ on vielﺣ۳ toisen virheen
ettﺣ۳ minun tﺣ۳ytyy korjata.
Joten voin vain olla varma uudelleenrullaamalla, ja sitten tarkistaa, yksi kaksi, kaksi ja
kolme, kolme ja neljﺣ۳, neljﺣ۳ ja viisi, viisi ja kuusi, kuusi ja seitsemﺣ۳n.
OK, nyt tein mitﺣ۳ﺣ۳n tyﺣﭘtﺣ۳.
>> Voin varmasti muistaa, ettﺣ۳ tein mitﺣ۳ﺣ۳n tyﺣﭘskennellﺣ۳ jotain muuttuja,
kuten int.
Soita se swap, ja jos swap on 0, kun olen tﺣ۳nne, ja se alkoi 0, niin
Haluan vain olla tyhmﺣ۳ pitﺣ۳ﺣ۳ kﺣ۳ynnissﺣ۳ edestakaisin, tarkistaa uudelleen, ja
uudestaan, ja uudestaan, eikﺣﭘ?
Koska saat kiinni joissakin Tﺣ۳llainen pﺣ۳ﺣ۳ttymﺣ۳ttﺣﭘmﺣ۳ﺣ۳n silmukkaan.
Joten kun siellﺣ۳ on 0 koronvaihtosopimukset, voimme vﺣ۳ittﺣ۳ﺣ۳, ettﺣ۳ tﺣ۳mﺣ۳
algoritmi on todellakin tﺣ۳ydellinen.
>> Nyt, laita nimi tﺣ۳hﺣ۳n.
Algoritmi, ettﺣ۳ ehdotan me vain tﺣ۳ytﺣ۳ntﺣﭘﺣﭘn on jotain kutsutaan kupla
lajitella, sinﺣ۳nsﺣ۳ tunnettuja siinﺣ۳ mielessﺣ۳, ettﺣ۳ numeroita, jotka ovat suurempia sellainen
kupla tiensﺣ۳ ylﺣﭘs, tai jopa loppuun joukko numeroita.
Mutta miten tehokas oli tﺣ۳mﺣ۳ algoritmi?
Kuinka monta askelta minﺣ۳ fyysisesti on ottaa esimerkiksi lajitella nﺣ۳mﺣ۳
seitsemﺣ۳n ihmisiin?
>> Neljﺣ۳ viisi?
OK, liikaa on viime kﺣ۳dessﺣ۳ olemaan vastaus.
Mutta silloinkin, tietty mﺣ۳ﺣ۳rﺣ۳ ei ole niin kiinnostavaa.
Katsotaanpa yleistﺣ۳ﺣ۳ sitﺣ۳ n.
Joten jos olisin n ihmisiﺣ۳ tﺣ۳ﺣ۳llﺣ۳, ja ne olivat, tavallaan, satunnaisessa jﺣ۳rjestyksessﺣ۳
alussa, ettﺣ۳ alkuperﺣ۳isessﺣ۳ jﺣ۳rjestyksessﺣ۳.
No, kuinka monta askelta minun tarvinnut ottaa ensikierron?
Se oli yksi, kaksi, kolme, neljﺣ۳, viisi, kuusi, ja ne seitsemﺣ۳n henkilﺣﭘﺣ۳, joten
se on seitsemﺣ۳n, kuusi -, niin se on n miinus yksi vaiheet ensimmﺣ۳isen kerran.
>> Nyt, kuinka monta askelta minun tarvinnut ottaa kun kelata?
No, voisimme todella kaksinkertainen, jos halusimme, mutta nyt olen
juuri menossa sanoa, okei, toinen n miinus 1.
Joten n miinus 1 on menossa ﺣ۳rsyttﺣ۳vﺣ۳ﺣ۳ seurata, joten katsotaanpa
vain pyﺣﭘristﺣ۳ﺣ۳ ylﺣﭘspﺣ۳in hieman.
Joten 2n vaiheet.
Joten 14 vaiheet, antaa tai ottaa.
>> Kuinka monta kertaa otan askel seuraavan kerran?
No, se on 3n.
todella.
Ja nyt, pahimmassa tapauksessa Esimerkiksi kuinka monta kertaa olisin
mennyt edestakaisin, edestakaisin, tﺣ۳ytﺣ۳ntﺣﭘﺣﭘnpanosta tﺣ۳mﺣ۳n algoritmin, vaihtamalla
ihmiset jokaisen syﺣﭘtﺣﭘn, suunnilleen?
Se on oikeastaan ﻗﻗn potenssiin, eikﺣﭘ?
>> Koska pahimmassa tapauksessa voit sellaista ajattelevat tﺣ۳stﺣ۳ intuitiivisesti,
vaikka se saattaa kestﺣ۳ﺣ۳ hieman vﺣ۳hﺣ۳n aikaa upota sisﺣ۳ﺣ۳n
Pahimmassa tapauksessa, mitﺣ۳ olisi nﺣ۳mﺣ۳ seitsemﺣ۳n ihmistﺣ۳ nﺣ۳yttﺣ۳neet, vuonna
Jﺣ۳rjestelyssﺣ۳ niiden numerot?
Tﺣ۳ysin taaksepﺣ۳in, eikﺣﭘ?
Ja vain simuloida, ettﺣ۳ mikﺣ۳ sinun nimesi olikaan?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, voisitko liittyﺣ۳ minua tﺣ۳ﺣ۳llﺣ۳ vain hetken?
Oikeastaan ﻗﻗei.
Sorry Mike, katsotaanpa taaksepﺣ۳in.
Mikﺣ۳ sinun nimesi olikaan?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, tulet minulle, jos et pahastu.
Joten aion ehdottaa, vain yksinkertaisuus, ettﺣ۳ Neil on nyt hﺣ۳nen
pahin mahdollinen tapaus.
Mutta muistaa miten toteutetaan minun algoritmi.
Olen vertaamalla, vertaamalla, vertaamalla, vertaamalla, vertaamalla, oh.
Nyt nﺣ۳mﺣ۳ kaverit ovat poissa jﺣ۳rjestyksessﺣ۳, niin voin korjata.
Joten te vaihtaa.
Ajatelkaa nyt, kuinka paljon kauemmas ei Neil tﺣ۳ytyy mennﺣ۳?
Se on suunnilleen n.
Tiedﺣ۳thﺣ۳n, se ei ole oikeastaan ﻗﻗn.
Se on kuin, n miinus 1, mutta Saan harmissaan pitﺣ۳ﺣ۳ kirjaa vﺣ۳hﺣ۳n
numero, joten haluan vain kutsua sitﺣ۳ n.
>> Joten jos Neil siirtyy askeleen maksimaalisesti kunkin aikaa, ja siirtyﺣ۳ Neil askeleen,
Minun tﺣ۳ytyy tehdﺣ۳ tﺣ۳mﺣ۳ todella ikﺣ۳vﺣ۳ pass edestakaisin, tﺣ۳mﺣ۳ on karkeasti
Nﺣ۳in n askelta, yhteensﺣ۳ n kertaa, koska se vie minut
ettﺣ۳ monet askeleen pﺣ۳ﺣ۳stﺣ۳ Neil kaikki tapa, mihin hﺣ۳n kuuluu.
Puhumattakaan kaikki muutkin, jos te olivat kaikki vﺣ۳ﺣ۳rin tilata samoin.
>> Joten soita kupla lajitella n potenssiin.
Kﺣ۳yntiaika tﺣ۳mﺣ۳n algoritmin, suorituskyky tﺣ۳mﺣ۳n algoritmin
tehokkuutta tﺣ۳mﺣ۳n algoritmin, meillﺣ۳ on vain kuvata enemmﺣ۳n
yleisesti n potenssiin.
Mikﺣ۳ on mukavaa, koska en voinut tehdﺣ۳ Sama esimerkiksi kahdeksan ihmistﺣ۳, yhdeksﺣ۳n
ihmisiﺣ۳, miljoona ihmistﺣ۳, ja ettﺣ۳ vastaus ei tule muuttaa.
>> Joten jos te panisi pahakseni, katsotaanpa palauttaa sinut missﺣ۳ aloitit.
Ja koetamme kaksi muuta lﺣ۳hestymistapoja ja katso jos emme voi tehdﺣ۳ pohjimmiltaan
parempi kuin tﺣ۳mﺣ۳.
Joten tﺣ۳llﺣ۳ kertaa, aion ehdottaa erﺣ۳ﺣ۳nlainen eri algoritmia.
Se oli erittﺣ۳in taitava meistﺣ۳ viime kerralla, ja olitte oikeus saada
oikeus vaistot juuri sellainen vaihtava pareittain.
Mutta jos halusin lﺣ۳hestyﺣ۳ tﺣ۳tﺣ۳ yksinkertaisesti, ja minun tavoite on siirtﺣ۳ﺣ۳
kaikki pikku numerot tﺣ۳llﺣ۳ tavalla, ja tyﺣﭘntﺣ۳ﺣ۳ kaikki suuret numerot, ettﺣ۳
Muuten, miksi en vain tehdﺣ۳, ettﺣ۳ Useimmissa naiivi mahdollisella tavalla ja nﺣ۳hdﺣ۳, jos olen
voi tehdﺣ۳ paremmin kuin mitﺣ۳ oli melko monimutkainen algoritmi?
>> Katsotaanpa.
Neljﺣ۳ on melko pieni mﺣ۳ﺣ۳rﺣ۳, joten olen aio jﺣ۳ttﺣ۳ﺣ۳ sinua siellﺣ۳ hetki.
Ooh, numero kaksi on vielﺣ۳ parempi.
Joten voitte vain askel eteenpﺣ۳in hetkeksi?
Tﺣ۳mﺣ۳ on tﺣ۳llﺣ۳ hetkellﺣ۳ minun pienin numeroitu ehdokas, ja aion muistaa
ettﺣ۳ niinku muuttuja.
Mutta aion pitﺣ۳ﺣ۳ tarkistaa.
Onko joku, jonka mﺣ۳ﺣ۳rﺣ۳ on pienempi?
Kuusi, no.
Voi, on Neil uudelleen.
>> Joten aion tyﺣﭘntﺣ۳ﺣ۳ sinut takaisin tavallaan kﺣ۳sitteellisesti.
Neil tulee eteen.
Ja nyt, muuttuja ettﺣ۳ olen kﺣ۳yttﺣ۳vﺣ۳t seurata kuka on pienin
numero pﺣ۳ivitetﺣ۳ﺣ۳n sisﺣ۳ltﺣ۳mﺣ۳ﺣ۳n Neil sijainti.
No, katsotaanpa.
Kolme, seitsemﺣ۳n, viisi.
Tunnen Neil oli pienin.
Mikﺣ۳ on yksinkertaisin asia minun tehdﺣ۳ nyt?
En aio tuhlata aikaani vain kuplivaa Neil yksi paikka vasemmalle.
Miksi en vain laittaa Neil jossa hﺣ۳n kuuluu, mikﺣ۳ on tietysti missﺣ۳?
>> Koko matkan alussa.
Joten Neil, tule.
Ja mikﺣ۳ sinun nimesi olikaan?
>> GRACE: Grace.
>> DAVID J. MALAN: Grace.
OK.
Joten Grace, valitettavasti, olet Tﺣ۳llainen tavalla.
Miten siis ratkaista tﺣ۳mﺣ۳n ongelman?
Oikea?
Jos tﺣ۳mﺣ۳ on jono, siellﺣ۳ on vain seitsemﺣ۳llﺣ۳ paikkakunnalla.
Muista, ettﺣ۳, Rob, puhuimme julistaa ikﺣ۳isiﺣ۳, ja meillﺣ۳ oli vain
ﺣ۳ﺣ۳rellinen mﺣ۳ﺣ۳rﺣ۳ ikﺣ۳isille?
Sama ajatus tﺣ۳ﺣ۳llﺣ۳.
Meillﺣ۳ on vain rajallinen mﺣ۳ﺣ۳rﺣ۳ ints.
Grace on tavallaan meidﺣ۳n tavalla, niin miten me korjata?
>> Yksinkertaisin tapa on kuin, Grace, anteeksi.
Olet menossa on mennﺣ۳ yli siellﺣ۳ niin voimme tehdﺣ۳ tilaa.
Nyt, jos ajattelee tﺣ۳tﺣ۳, ehkﺣ۳ Olemme juuri tehnyt ongelma pahempi.
Ja ehkﺣ۳ teimme, koska mitﺣ۳ jos Grace oli oikeassa paikassa?
Mutta me tiedﺣ۳mme, hﺣ۳n ei ole, koska muuten hﺣ۳n olisi ollut
seisoo eteenpﺣ۳in sijaan Neil tﺣ۳llﺣ۳ kertaa, eikﺣﭘ?
Meillﺣ۳ on jo tarkistanut hﺣ۳nen numeronsa ulos.
>> Selvﺣ۳.
Joten nyt, Neil on oikeassa paikassa, ja Voin tehdﺣ۳ hieman optimointia.
Seuraavan minuutin, aion sivuuttaa Neil kaikki yhdessﺣ۳, jotta ei
tuhlaa aikaansa, tai vahingossa vaihtaa hﺣ۳net vﺣ۳ﺣ۳rﺣ۳ﺣ۳n paikkaan.
Joten nyt, miten lﺣﭘydﺣ۳n seuraavan elementti, joka on pienin?
Kaksi.
Se on aika hyvﺣ۳ mﺣ۳ﺣ۳rﺣ۳, jos Haluatko astua esiin ja
Minﺣ۳ muistan sinut.
Kuusi, ole hyvﺣ۳.
Neljﺣ۳, kolme, seitsemﺣ۳n, viisi, ei hyvﺣ۳.
Joten anna minun siirtﺣ۳ﺣ۳ sinut oikea paikka.
Ja me vain onnekas tﺣ۳llﺣ۳ kertaa.
>> Nyt aion jﺣ۳ttﺣ۳ﺣ۳ nﺣ۳mﺣ۳ Kaksi miestﺣ۳, ja nyt vielﺣ۳ yhden
lﺣ۳pi tﺣ۳mﺣ۳n.
Kuusi, ettﺣ۳ melko pieni mﺣ۳ﺣ۳rﺣ۳.
Tule eteenpﺣ۳in.
Anteeksi.
Grace numero on parempi, joten astua eteenpﺣ۳in.
Neljﺣ۳.
Anteeksi, Grace.
Mene takaisin.
Numero kolme on parempi.
Seitsemﺣ۳n.
Viisi.
Ja nyt, mitﺣ۳ sinun nimesi olikaan?
>> JASON: Jason.
>> DAVID J. MALAN: Jason.
Joten Jason on nyt pienin elementti Olen valinnut.
Jos hﺣ۳n aikoo mennﺣ۳?
Joten missﺣ۳ kuusi on.
Ja sinun nimesi on jﺣ۳lleen?
>> GABE: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe on tiellﺣ۳.
Mikﺣ۳ on helpoin asia tehdﺣ۳?
Vaihda nﺣ۳mﺣ۳ kaksi kaveria ja jatkaa.
Joten nyt katsotaanpas.
Kuka pienin?
Neljﺣ۳.
Haluan vain sellainen huijata.
Viisi tulee olemaan pienin.
Minusta seuraava, jos haluat astua eteenpﺣ۳in, mitﺣ۳ minun tﺣ۳ytyy tehdﺣ۳
nﺣ۳mﺣ۳ kaverit, joiden Gabe?
Vaihda uudelleen.
Joten nyt vielﺣ۳ hieman epﺣ۳kunnossa.
I todettiin Gabe olevan pienin, niin Olen pop syﺣﭘtﺣﭘllﺣ۳ﺣ۳n, siirrﺣ۳ te yli.
Ja tehty.
>> Joten vastaus on sama.
Lopputulos on sama.
Kumpi nﺣ۳istﺣ۳ kahdesta algoritmeja on parempi?
Toinen, kuulin.
Miksi?
>> SPEAKER 3: Se n askelta [kuultavissa].
>> DAVID J. MALAN: Se n vaiheet eniten.
Mielenkiintoista.
Niin on se kuitenkin?
Joten miten lﺣﭘydﺣ۳n pienimmﺣ۳n alkion?
Kuinka monta askelta ei minun on otettava lﺣﭘytﺣ۳ﺣ۳ pienimmﺣ۳n alkion?
Olin nﺣ۳yttﺣ۳ﺣ۳ aina lopussa, eikﺣﭘ?
Koska ettﺣ۳ pahimmassa tapauksessa, mitﺣ۳ jos Neil olivat tﺣ۳ﺣ۳llﺣ۳?
Joten vain lﺣﭘytﺣ۳ﺣ۳ pienimmﺣ۳n alkion vie minut n askelta, tai n miinus 1.
Mutta, OK.
Korjatkaa Neil.
Muista, ettﺣ۳ minuutti sitten.
>> Mutta miten saan seuraavan pienimmﺣ۳n alkion?
Se n miinus 1 tai n miinus 2 todella, alkaen useita vaiheita.
Niin OK.
Joten en n miinus 2.
Selvﺣ۳.
Niin ettﺣ۳ tuntuu hieman paremmin.
Selvﺣ۳.
Kuinka monta askelta seuraavan kerran lﺣﭘytﺣ۳ﺣ۳ numero kolme?
Joten n miinus 4.
Joten se on laskussa, yksi vﺣ۳hemmﺣ۳n astua jokaisen iteraation.
Joten tﺣ۳mﺣ۳ ei tuntea paremmin, eikﺣﭘ?
Jos viime kerralla se oli noin n kertaa n, tﺣ۳llﺣ۳ kertaa se n miinus 1, plus n miinus
2, plus n miinus 3, plus n miinus 4, piste, piste, piste.
Mutta jos muistatte omasta lukion oppikirjat, vﺣ۳hﺣ۳n huijata
arkki takaisin, ettﺣ۳ on kaavojen avulla, jos lisﺣ۳ﺣ۳t tﺣ۳tﺣ۳ numerosarja,
mikﺣ۳ on portaiden kokonaismﺣ۳ﺣ۳rﺣ۳ﺣ۳ olemaan, ettﺣ۳ otan tﺣ۳ﺣ۳llﺣ۳?
>> Tﺣ۳mﺣ۳ on yksi niistﺣ۳, kuten, n miinus 1 kertaa n, jaettuna 2.
Joten anna minun nﺣ۳hdﺣ۳, jos voin vetﺣ۳ﺣ۳ tﺣ۳hﺣ۳n asti vain hetken.
Ja vielﺣ۳, olen sellainen pyﺣﭘristys joidenkin numerot vain pitﺣ۳ﺣ۳ elﺣ۳mﺣ۳ﺣ۳mme yksinkertainen,
mutta muistaakseni se on jotain, jos En n miinus 1 asioita, niin n miinus
2, niin n miinus 3, se on suurin piirtein jotain tﺣ۳llaista yli 2, ja jos minﺣ۳
moninkertaistaa tﺣ۳mﺣ۳n, se on todella n neliﺣﭘ.
Se ei tunne liian hyvﺣ۳. n miinus n yli 2.
>> Mutta tﺣ۳ssﺣ۳ on asia.
Tietotekniikassa, kun ongelmia alkaa saada mielenkiintoista on kun n
saa todella suuri.
Ja kun n saa todella suuri, mikﺣ۳ Nﺣ۳iden arvojen tulee hallitsemaan kaikkia
ja muut?
Se on tavallaan n potenssiin, eikﺣﭘ?
Kyllﺣ۳, jakamalla 2 on melko hyvﺣ۳.
Mutta jos puhut miljardeja paloja tietoja tai miljardeja
datakappaleesta, OK, niin olet kaksi kertaa niin nopeasti.
Mutta kuka todella vﺣ۳littﺣ۳ﺣ۳, jos suuri mﺣ۳ﺣ۳rﺣ۳, jos tﺣ۳mﺣ۳ seikka on mitﺣ۳ saa
isompi ja isompi.
Ja varmasti, se tekee enemmﺣ۳n ero kuin tﺣ۳mﺣ۳ kaveri.
Joten vaikka te olette oikeassa, Toinen algoritmi, me kutsumme sitﺣ۳
valinta lajitella, on, todellisessa maailmassa, hieman nopeampi mahdollisesti, koska olen
ottaen yhﺣ۳ harvempi askeleen kerrallaan.
>> Se ei ole oikeastaan ﻗﻗpohjimmiltaan nopeammin.
Koska jos me todella pelata tﺣ۳tﺣ۳ ulos suuret n: n arvoilla, lopussa
pﺣ۳ivﺣ۳, tarpeeksi suuri n, se on silti menossa tuntea melko hidasta.
No, anna minun ottaa yksi viime pass tuohon.
Sitﺣ۳ minﺣ۳ kutsuisin valinta lajitella.
Voisitteko palauttaa itseﺣ۳nne viimeisen kerran?
Ja tﺣ۳ssﺣ۳ viime tapauksessa aion ehdottaa jotain
nimeltﺣ۳ﺣ۳n lisﺣ۳yslajittelu.
Lisﺣ۳yslajittelu on kﺣ۳sitteellisesti vﺣ۳hﺣ۳n erilainen.
>> Sijaan menee edestakaisin ja valitsemalla pienimmﺣ۳n alkion, olen
juuri menossa kﺣ۳sitellﺣ۳ kutakin nﺣ۳istﺣ۳ kaverit kuin minﺣ۳ kohtaavat heitﺣ۳, ja aseta
ne osaksi oikeassa paikassa.
Joten olen juuri menossa aloittaa Grace, ja nﺣ۳en, ettﺣ۳ hﺣ۳n on numero neljﺣ۳.
Mistﺣ۳ numero neljﺣ۳ kuuluu?
En ole alkanut lajittelu mitﺣ۳ﺣ۳n, niin Grace saa jﺣ۳ﺣ۳dﺣ۳ oikeassa.
Ja nyt aion vaatia, jos voisit ottaa askel oikealla, tﺣ۳mﺣ۳
minun lajiteltu lista, tﺣ۳mﺣ۳ on minun lajittelemattoman jﺣ۳ljellﺣ۳ lista.
Joten nyt aion edetﺣ۳ seuraavaan, ja mikﺣ۳ sinun nimesi olikaan?
>> BRANSON: Branson.
>> DAVID J. MALAN: Branson.
Joten Branson on numero kaksi.
Joten aion viedﺣ۳ sinut pois hetkeksi.
Ja nyt, jos kuulut Tﺣ۳ssﺣ۳ array?
Joten oikeus Grace.
Joten jﺣ۳lleen olemme tavallaan tehdﺣ۳ Grace tehdﺣ۳ paljon tyﺣﭘtﺣ۳ tﺣ۳ﺣ۳llﺣ۳.
Minne laitamme sinut?
Joten aiomme liukumaan sinua vasemmalle ja aseta Branson siellﺣ۳.
Mutta nyt Vﺣ۳itﺣ۳n, ettﺣ۳ te olette tehneet.
Mutta huomaa, en kﺣ۳ytﺣ۳ lisﺣ۳tilaa.
Se on edelleen 2 elementtiﺣ۳ tﺣ۳ﺣ۳llﺣ۳, 5 tﺣ۳nne.
Yhteensﺣ۳ jonon pituus on 7, joten olen ei huijaa, kaikki hyvin?
>> Joten nyt meillﺣ۳ on, ja Gabe tﺣ۳ﺣ۳llﺣ۳, numero kuusi, jossa sinﺣ۳ kuulut?
Olet onnekas uudelleen.
Niin saat pysyﺣ۳ oikeassa.
Ota vain hieman askel oikeaan vain tehdﺣ۳ selvﺣ۳ksi, ettﺣ۳ olet lajitellaan.
Ja nyt meillﺣ۳ on Neil uudelleen, numero yksi, minne menet?
Ja nyt on, jos alamme nﺣ۳hdﺣ۳, ettﺣ۳ tﺣ۳mﺣ۳ algoritmi, vaikka ensimmﺣ۳isen
silmﺣ۳yksellﺣ۳, tuntuu aika fiksu, katsella mitﺣ۳ tulee tapahtumaan.
Jos voisit askel eteenpﺣ۳in.
>> Missﺣ۳ haluamme laittaa Neil?
Joten ilmeisesti tﺣ۳ﺣ۳llﺣ۳, niin miten saamme Neil siellﺣ۳?
Tehdﺣ۳ﺣ۳n tﺣ۳mﺣ۳ askel-askeleelta.
Gabe, mistﺣ۳ sinun tﺣ۳ytyy mennﺣ۳?
Jep, niin ottaa yksi iso askel, tai kaksi puolen toimiin, jotta
yksi askel tuolla.
Grace, missﺣ۳ mennﺣ۳ﺣ۳n?
Hyvﺣ۳.
Joten toinen vaihe.
Ja lopuksi, Branson?
Toinen vaihe.
Ja nyt voimme Neil paikoilleen.
>> Joten nyt jatkaa tﺣ۳tﺣ۳ logiikkaa.
Vaikka emme ole siirtymﺣ۳ssﺣ۳ Neil yli, ja yli, ja yli, laittaa hﺣ۳net
missﺣ۳ hﺣ۳n menee, pahimmassa tapauksessa seuraava numero saatamme kohdata voitaisiin
olla numero, eli siellﺣ۳ oli useita nolla, niin aiomme siirtﺣ۳ﺣ۳ kaikki
nﺣ۳mﺣ۳ kaverit.
Oletetaan, ettﺣ۳ on olemassa useita, negatiivinen , sitten meidﺣ۳n tﺣ۳ytyy siirtyﺣ۳
kaikki nﺣ۳mﺣ۳ kaverit.
Olemme siis oikeastaan ﻗﻗvain sellainen kﺣ۳ﺣ۳nnetﺣ۳ﺣ۳n ongelman ympﺣ۳rillﺣ۳, niin ettﺣ۳ olemme
siirtﺣ۳mﺣ۳llﺣ۳ kustannuksella alkaen valintaprosessi joten lisﺣ۳ys
prosessi, niin ettﺣ۳ te vain oli liikkua karkeasti n miinus jotain
useita vaiheita.
Ja ettﺣ۳ useita vaiheita on vain menee kasvavan valitsen enemmﺣ۳n numeroita,
jos minun tﺣ۳ytyy pitﺣ۳ﺣ۳ tyﺣﭘntﺣ۳mﺣ۳ﺣ۳n teitﺣ۳ takaisin, ja takaisin, ja takaisin.
>> Niin surullista nyt on kaikki nﺣ۳mﺣ۳ algoritmit ovat n potenssiin.
Mennﺣ۳ﺣ۳n eteenpﺣ۳in ja kiitos nﺣ۳istﺣ۳ kaverit, ja visualisoida nﺣ۳mﺣ۳ vﺣ۳hﺣ۳n
eri tavalla.
Hyvin tehty.
>> [APPLAUSE]
>> Selvﺣ۳.
Siellﺣ۳ mennﺣ۳ﺣ۳n.
Kiitos -
>> BRANSON: [kuultavissa] pitﺣ۳ﺣ۳ numerot.
>> DAVID J. MALAN: Ei, voit pitﺣ۳ﺣ۳ numerot samoin.
Selvﺣ۳.
Hienosti tehty.
Selvﺣ۳.
Katsotaanpa, jos emme voi nyt tiivistﺣ۳ﺣ۳ nopeammin, ja visuaalisesti,
mitﺣ۳ juuri tapahtui tﺣ۳ssﺣ۳ seuraavasti.
Aion mennﺣ۳ eteenpﺣ۳in ja vedﺣ۳ ylﺣﭘs Firefox.
Liitﺣ۳mme tﺣ۳mﺣ۳n esittelyn kurssin verkkosivuilla.
Java on vﺣ۳hﺣ۳n ﺣ۳rsyttﺣ۳vﺣ۳ﺣ۳ saada tyﺣﭘ Joissakin selaimissa nﺣ۳inﺣ۳ pﺣ۳ivinﺣ۳.
Joten jos et pelata tﺣ۳tﺣ۳ kotona, ymmﺣ۳rtﺣ۳ﺣ۳, saatat joutua kﺣ۳yttﺣ۳mﺣ۳ﺣ۳n Firefox
saada se toimimaan.
Ja mitﺣ۳ aion tehdﺣ۳ tﺣ۳mﺣ۳n esittelyﺣ۳ on seuraava.
>> Alareunassa, minulla on koko joukko valikon vaihtoehdot, kuten alku-ja
STOP-painiketta.
Lisﺣ۳ksi, kuten syrjﺣ۳ﺣ۳n, siellﺣ۳ nﺣ۳yttﺣ۳ﺣ۳ olevan bug nﺣ۳issﺣ۳ ohjelmissa, jolloin voit
ei voi itse nﺣ۳hdﺣ۳ alusta tai lopettaa painiketta ellet pidﺣ۳ Command tai Alt
plus ja zoomaus, joka uteliaana nﺣ۳yttﺣ۳ﺣ۳ enemmﺣ۳n painikkeita.
Joten FYI jos pelaat tﺣ۳mﺣ۳n kotona.
Nyt aion valitse Kﺣ۳ynnistﺣ۳ vain hetkellﺣ۳, kun mﺣ۳ﺣ۳ritellﺣ۳ﺣ۳n viive,
kuten 200 millisekuntia tﺣ۳ﺣ۳llﺣ۳, vain jotta voimme nﺣ۳hdﺣ۳, mitﺣ۳ tapahtuu.
>> Olen siis vﺣ۳ittﺣ۳vﺣ۳t, ettﺣ۳ tﺣ۳mﺣ۳ on visualisointi Ensimmﺣ۳isen algoritmin
nﺣ۳mﺣ۳ kaverit tekivﺣ۳t, kupla lajitella, jolloin Vaihdoimme ihmiset pareittain.
Keskeinen oivallus tﺣ۳hﺣ۳n visualisointi on se, ettﺣ۳ korkeus tankojen
edustaa koko mﺣ۳ﺣ۳rﺣ۳ﺣ۳.
Joten pitempi palkki, isompi numero.
Lyhyemmﺣ۳t baari, pienempi numero.
Ja jos huomaat, olemme menossa lﺣ۳pi Ensimmﺣ۳inen tﺣ۳mﺣ۳n algoritmin,
vaihtamalla iso ja pieni mﺣ۳ﺣ۳rﺣ۳, jotta pieni mﺣ۳ﺣ۳rﺣ۳ tulee ensin ja
suuri mﺣ۳ﺣ۳rﺣ۳ menee oikealle.
>> Ja heti kun saamme loppuun array paljon enemmﺣ۳n numeroita kuin seitsemﺣ۳n, olemme
menossa takaisin alkuun.
Ja ennakoida tﺣ۳tﺣ۳.
ﺣﺣ۳rimmﺣ۳isenﺣ۳ vasemmalla, ettﺣ۳ pikku kaveri on menossa vaihtaa puolelle, ja tﺣ۳mﺣ۳
prosessi toistuu.
Nyt tﺣ۳mﺣ۳ visualisointi saa nopeasti tylsﺣ۳ﺣ۳, joten haluan mennﺣ۳ eteenpﺣ۳in ja lopettaa
, muuttaa viive jotain paljon nopeampi vain saada nyt tuntumaa
tﺣ۳mﺣ۳ algoritmi.
>> Joten vaikka olen nopeuttanut sitﺣ۳, tﺣ۳mﺣ۳ on kuten pﺣ۳ivittﺣ۳ﺣ۳ minun prosessori, ostaa
uusi tietokone.
En ole olennaisesti muuttanut algoritmi, mutta voit todellakin nﺣ۳hdﺣ۳ enemmﺣ۳n
selvﺣ۳sti kuin ihmisten kanssa, ettﺣ۳ iso numerot kuplii ylﺣﭘs,
ja pienet numerot ovat kuplivaa pohjaan.
Ja nyt tﺣ۳mﺣ۳ asia tﺣ۳ﺣ۳llﺣ۳ jﺣ۳rjestetty.
Ja syrjﺣ۳ﺣ۳n, toreilla, siellﺣ۳ vain joitakin kirjanpidon siellﺣ۳
auttaa laskemaan, kuinka monta vertailuja, tai kuinka monta swap on
todella tehty.
>> No, kokeile jotakin muut nﺣ۳imme.
Saanen klikkaa kupla lajitella tﺣ۳ﺣ۳llﺣ۳, ja anna minun valita, ja tﺣ۳mﺣ۳ koko web-sivun
on vﺣ۳hﺣ۳n buginen.
Katsotaanpa hyvﺣ۳ksyﺣ۳ riski ja kﺣ۳yttﺣ۳ﺣ۳ sitﺣ۳ uudelleen.
Siellﺣ۳ mennﺣ۳ﺣ۳n.
Tehdﺣ۳ﺣ۳npﺣ۳ valinta tavallaan.
En tiedﺣ۳ miksi valikosta nﺣ۳kyy tuolla.
Katsotaanpa zoomata vahvistaa, ettﺣ۳ bug, muuttaa 50.
Ah, nyt itse tehdﺣ۳ ettﺣ۳ paljon nopeammin.
Viisi millisekunnin, ja Start.
>> Joten tﺣ۳mﺣ۳ on valinta tavallaan.
Joten jﺣ۳lleen, miettiﺣ۳, mitﺣ۳ me teki ihmisiin tﺣ۳ﺣ۳llﺣ۳.
Kﺣ۳vimme lﺣ۳pi array ja valitut pienimmﺣ۳n alkion uudelleen,
ja uudestaan, ja uudestaan.
Nyt Vﺣ۳itﺣ۳n, ettﺣ۳ oli vielﺣ۳ melko huono.
Se oli vielﺣ۳ n neliﺣﭘ, antaa tai ottaa, mutta se oli, todellisessa maailmassa, hieman
nopeammin, koska olin todellakin ottaen hieman vﺣ۳hemmﺣ۳n vaiheita joka kerta.
Mutta me vain puhumme mitﺣ۳?
Ehkﺣ۳ 40 tai niin baareissa tﺣ۳ﺣ۳llﺣ۳?
Emme puhu 40 miljoonaa.
Joten se ei ole tﺣ۳ysin selvﺣ۳ﺣ۳, ettﺣ۳ oli todellakin merkittﺣ۳vﺣ۳ voitto.
>> Anna minun mennﺣ۳ takaisin ja muuttaa meidﺣ۳n Kolmas algoritmi, joka valitaan
lisﺣ۳yslajittelu.
Ja nyt se on todella buginen, koska valikko ei todellakaan pitﺣ۳isi olla siellﺣ۳.
Joten nyt me vierittﺣ۳ﺣ۳ takaisin tﺣ۳nne ja aloittaa tﺣ۳mﺣ۳n algoritmi.
Huutaa, kﺣ۳ynnistﺣ۳ﺣ۳ ja pysﺣ۳yttﺣ۳ﺣ۳.
Joten tﺣ۳mﺣ۳ yhdenlaista on melko kuvio sen, jolloin olemme taas
lisﺣ۳ﺣ۳mﺣ۳llﺣ۳ ihmisten tai Tﺣ۳llﺣﭘin baareja osaksi
niiden oikeassa paikassa.
Ja se on jo tehnyt ennen Kﺣ۳ﺣ۳nnyin ympﺣ۳ri.
Mutta myﺣﭘs tﺣ۳mﺣ۳ teoriassa on vielﺣ۳ n potenssiin.
>> Katsotaanpa, jos emme voi tiivistﺣ۳ﺣ۳ Nﺣ۳iden seuraavasti.
Aion mennﺣ۳ eteenpﺣ۳in ja vain antaa meille erﺣ۳ﺣ۳nlainen yhteinen tapa puhua
nﺣ۳istﺣ۳ asioista, haluan esitellﺣ۳ vain vﺣ۳hﺣ۳n merkintﺣ۳tapa tﺣ۳ﺣ۳llﺣ۳.
Olet tulleet niin sanotun suuren O, koska se on kirjaimellisesti iso
O. Ja tﺣ۳mﺣ۳ on tapa, ettﺣ۳ tietokone tiedemies tai matemaatikko edes kﺣ۳yttﺣ۳ﺣ۳
kuvaamaan kﺣ۳yntiaika Joidenkin algoritmi.
Kuinka monta askelta se todella ottaa?
>> Nyt aion nolata itseni kanssa minun kﺣ۳sialalla tﺣ۳ﺣ۳llﺣ۳ vain hetken.
Mutta haluan mennﺣ۳ eteenpﺣ۳in ja sanoa, ettﺣ۳ tﺣ۳mﺣ۳ on iso O tﺣ۳nne.
Ja haluan esitellﺣ۳ yksi muu symboli, pﺣ۳ﺣ۳oman omega.
Omega tulee olemaan pﺣ۳invastainen, lﺣ۳hinnﺣ۳ iso O. katsoo iso O
vﺣ۳lineet, pahimmassa tapauksessa, kuinka paljon aikaa saattaa joissakin algoritmi toteuttaa vuonna
ehtojen n, omega on menossa olla kuinka paljon aikaa saattaa se
ottaa parhaassa tapauksessa.
Ja nﺣ۳emme, mitﺣ۳ me tarkoitamme Parhaassa tapauksessa vain hetken.
>> Joten aloitetaan jotain yksinkertaista.
Aloitan lineaarista hakua.
Joten ei lajittelu.
Me kutsumme tﺣ۳tﺣ۳ lineaarista hakua.
Ja nyt, tehdﺣ۳ vﺣ۳hﺣ۳n taulukko pois tﺣ۳stﺣ۳.
Ja nyt, kun kyseessﺣ۳ on lineaarinen haku, pahimmassa tapauksessa, kuinka monta askelta on
se vie minut lﺣﭘytﺣ۳ﺣ۳ mﺣ۳ﺣ۳rﺣ۳ mielivaltainen valinta?
Ja siellﺣ۳ n yhteensﺣ۳ ovet tai n kokonaismﺣ۳ﺣ۳rﺣ۳t.
Pahimmassa tapauksessa.
Kuinka monta askelta olen menossa on ottaa lﺣﭘytﺣ۳ﺣ۳ numeron 50 array
n ovet?
Ja miksi?
Koska se voisi olla kaikki reilusti yli kiinni loppuun.
Niin paljon kuin Jennifer kohdanneet, numero 50 oli aina yli, joten
Pahimmassa tapauksessa lineaarinen haku on iso O n, me sanomme.
>> Entﺣ۳ parhaassa tapauksessa jos saat todella onnekas?
Se tekee vain ottaa yksi askel, tai jatkuvasti useita vaiheita.
Joten me kuvataan, ettﺣ۳ 1.
Joten tﺣ۳mﺣ۳ on melko hyvﺣ۳.
Nyt mitﺣ۳ jos teimme jotain kuten binﺣ۳ﺣ۳rihaku?
Joten binﺣ۳ﺣ۳rihaku pahimmassa tapauksessa kesti kuinka paljon aikaa?
>> [Interposing ﺣﺣNTﺣ]
>> DAVID J. MALAN: Niin todella, minﺣ۳ kuullut sen pari paikkaa.
Joten se on todella kirjautua n, antaa tai ottaa, koska sillﺣ۳ jaamme listan kahtia
uudestaan, ja uudestaan, ja uudestaan, pystymme lﺣﭘytﺣ۳ﺣ۳ lopulta arvosta,
jos se on olemassa, mutta on kiinni.
Mikﺣ۳ oletus, ettﺣ۳ meidﺣ۳n on itsestﺣ۳ﺣ۳nselvyytenﺣ۳ binary search?
Se on jﺣ۳rjestetty.
Se ei ole lajiteltu, voit jakaa asia kahtia uudestaan ﻗﻗja uudestaan, ja sinﺣ۳
voi mennﺣ۳ vasemmalle, ja voit mennﺣ۳ oikealle, ja voit mennﺣ۳ vasemmalle ja oikealle, mutta olet
tule lﺣﭘytﺣ۳mﺣ۳ﺣ۳n elementti, jos luetteloa ei lajitella, koska
saatat menettﺣ۳ﺣ۳ sen.
Koska heuristinen menossa vasemmalle tai oikealle tulee olla virheellinen, jos se on
todellakin ole lajiteltu.
Niin siellﺣ۳ on tavallaan piilokustannuksia kﺣ۳yttﺣ۳mﺣ۳ﺣ۳n jotain tﺣ۳llaista.
>> Nyt mennﺣ۳ﺣ۳n meidﺣ۳n lajittelu algoritmit etsimﺣ۳ttﺣ۳ -
oh, todella mennﺣ۳ﺣ۳n tﺣ۳ssﺣ۳ tyhjﺣ۳ksi.
Binﺣ۳ﺣ۳rihaku parhaassa tapauksessa?
Se on myﺣﭘs 1, jos se vain sattuu olemaan aivan keskellﺣ۳ array, tai
keskellﺣ۳ puhelinluettelosta.
Nyt tehdﺣ۳ kupla tavallaan.
Joten jﺣ۳lleen, nyt olemme syﺣﭘttﺣ۳mﺣ۳llﺣ۳ lajittelee, ei hakuja.
>> Pahimmassa tapauksessa, kuinka monta askelta teimme vﺣ۳ite kupla tavallaan vie?
n potenssiin.
Joten aion tehdﺣ۳ sen.
Ooh, minun kﺣ۳siala nﺣ۳yttﺣ۳ﺣ۳ jopa pahempi kun se on ennustettu, ettﺣ۳ iso.
Selvﺣ۳.
Niin, ettﺣ۳ N-potenssiin.
Ja parhaassa tapauksessa kupla lajitella, kuinka monta askelta se aikoo ryhtyﺣ۳?
1, kuulin.
>> Kaiutin 1: n.
>> DAVID J. MALAN: n, kuulin.
>> SPEAKER 1: 2.
>> DAVID J. MALAN: 2, kuulin.
Kuulenko 3?
Selvﺣ۳.
Niin olen kuullut 1 n, 2, mutta nyt valita lisﺣ۳ksi ainakin ensimmﺣ۳inen nﺣ۳istﺣ۳
ehdotuksia, 1.
Se ei ole huono vaisto, koska se Tﺣ۳llainen seuraa kuvio tﺣ۳ﺣ۳llﺣ۳.
Mutta jos se kestﺣ۳ﺣ۳ vain 1 askel, miten maailman voisin vﺣ۳ittﺣ۳ﺣ۳, ettﺣ۳ luettelon
lajitellaan, koska jos olen vain sallittu ottaa 1 askel, kuinka monta elementtiﺣ۳
voisin oikeastaan ﻗﻗvarmista?
No, vain 1, mikﺣ۳ tarkoittaa, ettﺣ۳ on n miinus 1 seikkoja, jotka voisivat olla pois
jﺣ۳rjestyksessﺣ۳, ja olen juuri menossa uskoon jﺣ۳lkeen katsomalla 1 elementti, joka
asia on jﺣ۳rjestetty.
Joten 1 ei ole korjata tﺣ۳ﺣ۳llﺣ۳.
Joten vﺣ۳hﺣ۳n, kuinka monta minun tﺣ۳ytyy katsoa?
>> [Interposing ﺣﺣNTﺣ]
>> DAVID J. MALAN: n miinus 1, tai oikeastaan, n, koska minun tﺣ۳ytyy tarkastella jokaisen
elementti varmistaa, ettﺣ۳ se ei ole epﺣ۳kunnossa.
Mutta jﺣ۳lleen kerran, me tavallaan aalto meidﺣ۳n kﺣ۳det pienempi mﺣ۳ﺣ۳rﺣ۳ ja
olettaa, ettﺣ۳ n saa suuria, ne ovat mielenkiinnoton muutenkin.
Niin, ettﺣ۳ kupla tavallaan.
Ja nyt, nyt nﺣ۳mﺣ۳ kaksi viimeistﺣ۳.
Valinta lajitella ja niin me hyvitﺣ۳mme tehdﺣ۳ lisﺣ۳yslajittelu.
Ja sitten me rﺣ۳jﺣ۳yttﺣ۳ﺣ۳ mielissﺣ۳ jotain paljon
parempi kuin kaikki nﺣ۳mﺣ۳.
Selvﺣ۳.
>> Mikﺣ۳ on pahin kﺣ۳ynnissﺣ۳ valintahetkellﺣ۳ tavallaan?
>> SPEAKER 4: n potenssiin.
>> DAVID J. MALAN: n neliﺣﭘ, kuulen.
Mutta miksi n potenssiin, intuitiivisesti?
>> SPEAKER 4: Koska me vain teimme sen.
>> DAVID J. MALAN: Koska me vain teimme sen.
OK.
Hyvﺣ۳ vastaus.
Mutta intuitiivisesti, miksi valinta sort n potenssiin?
Mitﺣ۳ meidﺣ۳n on tehtﺣ۳vﺣ۳ uudestaan ﻗﻗja uudestaan?
Meidﺣ۳n piti pitﺣ۳ﺣ۳ skannauksen kautta, ovat olet pienin, oletko
pienin, oletko pienin.
Ja myﺣﭘnsi, pystyimme ottamaan n vaiheet, niin n miinus 1, niin n miinus 2.
Mutta jos sellainen lisﺣ۳tﺣ۳ ne kaikki ylﺣﭘs, tai ottaa sen uskon, ettﺣ۳ olen lisﺣ۳nnyt
niitﺣ۳ etukﺣ۳teen, saamme karkeasti n potenssiin miinus joitakin pienempiﺣ۳ numeroita.
Joten aion kutsua tﺣ۳tﺣ۳ n potenssiin.
Mutta valinta lajitella paras tapauksessa, kuinka monta askelta on se
vie minut?
>> SPEAKER 5: [ﺣ۳ﺣ۳netﺣﭘn]
>> DAVID J. MALAN: Se on valitettavasti vielﺣ۳ n potenssiin, eikﺣﭘ?
Koska jos olen valinnut pienin elementti, ja meillﺣ۳ oli seitsemﺣ۳n ihmistﺣ۳ tﺣ۳ﺣ۳llﺣ۳,
Tiedﺣ۳n vain, kun pﺣ۳ﺣ۳sen hyvin lopussa, ettﺣ۳ olen lﺣﭘytﺣ۳nyt pienin
numero, missﺣ۳ hﺣ۳n tai joutuneensa.
Mutta miten lﺣﭘydﺣ۳n seuraavan pienin mﺣ۳ﺣ۳rﺣ۳?
Minun tﺣ۳ytyy tehdﺣ۳ toinen pass.
Joten parhaassa tapauksessa, mikﺣ۳ on valintamekanismille tavallaan?
Se on jo lajitteluluetteloon, numero yksi, numero kaksi, numero kolme, numero neljﺣ۳.
Mutta olen tietokone.
Voin vain katsoa yksi asia kerrallaan.
En voi tavallaan ottaa askel takaisin kuin ihmisen ja sanoa,
ooh, tﺣ۳mﺣ۳ nﺣ۳yttﺣ۳ﺣ۳ oikein.
>> Voin vain ratkaista oikeellisuus valinta lajitella valitsemalla
pienin mﺣ۳ﺣ۳rﺣ۳.
Mutta vaikka lﺣﭘydﺣ۳n ykkﺣﭘnen ensin, jos en tiedﺣ۳ mitﺣ۳ﺣ۳n muuta
muut numerot, joita en ole, kaikki I tietﺣ۳ﺣ۳, ettﺣ۳ olen kulkenut array
tai joukko ovien takana, jotka ovat numerot, ainoa tapa Tiedﺣ۳n, ettﺣ۳ yksi
oli pienin?
Jos saan kaikki tﺣ۳nne ja ymmﺣ۳rtﺣ۳ﺣ۳, Hitto, yksi oli todellakin pienin.
>> Mutta miten voin sitten pﺣ۳ﺣ۳ttﺣ۳ﺣ۳, ettﺣ۳ kaksi on seuraavaksi pienin?
Tekemﺣ۳llﺣ۳ sama tehottomuus uudelleen ja uudelleen.
Joten lopuksi, jossa lisﺣ۳yslajittelu, miten, pahimmassa tapauksessa,
Sanoimmeko se toimii?
Sekin on n potenssiin.
Ja miten paras asia?
Jﺣ۳tﺣ۳mme ettﺣ۳ jﺣ۳nnitysnﺣ۳ytelmﺣ۳.
Me tﺣ۳yttﺣ۳ﺣ۳ ettﺣ۳ tyhjﺣ۳ seuraavan kerran, mutta haluan ensin ehdottaa, ettﺣ۳
pohjimmiltaan tehdﺣ۳ paremmin kuin kaikki nﺣ۳mﺣ۳, okei?
>> Ajattele itse, mitﺣ۳ paikoilleen sort tulee olemaan.
No, se ei ollut kovin dramaattinen, koska olen vain yksi
ettﺣ۳ nﺣ۳ki muutoksen.
Wow.
OK.
Joten tﺣ۳ssﺣ۳ meillﺣ۳ on hieman eri esittelyﺣ۳.
Jos minﺣ۳ suurentaa tﺣ۳ﺣ۳llﺣ۳, nﺣ۳et, ettﺣ۳ Vasemmalla on kupla lajitella, vuonna
keskellﺣ۳ meillﺣ۳ on valikoima lajitella, ja ﺣ۳ﺣ۳rioikeisto, olemme me
ole katsonut vielﺣ۳ nimeltﺣ۳ﺣ۳n yhdistﺣ۳ﺣ۳ tavallaan.
Ajatelkaa mitﺣ۳ olemme olleet teet tﺣ۳ﺣ۳llﺣ۳ tﺣ۳hﺣ۳n mennessﺣ۳ tﺣ۳nﺣ۳ﺣ۳n.
Kun Jennifer ensimmﺣ۳inen tuli lavalle, kﺣ۳vimme lﺣ۳pi joukko numeroita
uudestaan, ja uudestaan, lineaarinen haku, ja saimme lineaarinen kﺣ۳yntiaika, iso O
n, niin sanoakseni.
>> Kun me nyt harkita ensimmﺣ۳isellﺣ۳ viikolla luokka, kun olimme hajoita ja hallitse,
ja meillﺣ۳ oli puhelinluettelon repiminen, ja Jennifer, ja me yhdessﺣ۳
velkarahalla, ettﺣ۳ keskeiset oivallus, joka oli toista itseﺣ۳si uudestaan ﻗﻗja uudestaan
jotenkin heittﺣ۳ﺣ۳ pois, heittﺣ۳ﺣ۳ pois, heittﺣ۳ﺣ۳ pois, puolet ongelma tai
yleisesti, jakamalla ongelma puoli, ja sitten kﺣ۳sittelemﺣ۳llﺣ۳ pienempi pala
ongelma kﺣ۳sitteellisesti vastaa Muihin me jotenkin pallo
pohjimmiltaan paremmin.
Mutta kupla lajitella, jossa valinta lajitella, jossa lisﺣ۳yslajittelu, olemme voi
tﺣ۳llaisia ﻗﻗoivalluksia ettﺣ۳ Jennifer teki.
Olemme aika paljon vain kﺣ۳veli takaisin ja esiin koko joukko kertaa, ja me
viritetty asioita hieman, vaihtamalla tﺣ۳ssﺣ۳ jﺣ۳rjestyksessﺣ۳, ehkﺣ۳
lisﺣ۳ﺣ۳mﺣ۳llﺣ۳ tai valitsemalla.
Mutta loppujen lopuksi, tein paljon hankala kﺣ۳vely edestakaisin.
Meillﺣ۳ ei oikeastaan ﻗﻗhyﺣﭘdyntﺣ۳ﺣ۳ jotain ﺣ۳lykﺣ۳s kuten Jennifer teki kuten jakamalla
ja valloitusta.
>> Joten yhdistﺣ۳ﺣ۳ lajitella, sen sijaan, jota eivﺣ۳t nﺣ۳e vasta ensi viikolla, se menee
hyﺣﭘdyntﺣ۳ﺣ۳, ettﺣ۳ keskeinen ajatus jakamalla tulo, ja sitten puolittaa, ja sitten
puolittaa, ja sitten puolittaa.
Ja jokaisen iteraation ettﺣ۳ silmukka, lajittelu vasen puoli ja oikea
puoli, sitten vasen puoli on vasen puoli, ja oikealla puolella vasemmalle, sitten
vasen puoli oikea puoli, ja oikea puoli oikea puoli.
Ja toistamalla uudestaan ﻗﻗja uudestaan.
>> Niin nﺣ۳et tﺣ۳mﺣ۳n visuaalisesti, mutta tﺣ۳mﺣ۳ on mitﺣ۳ odottaa meitﺣ۳ ensi viikolla.
Ja yleensﺣ۳, kun ajattelemme hieman vﺣ۳hﺣ۳n kovemmin tﺣ۳llaisia ﻗﻗongelmia.
Meillﺣ۳ on n potenssiin vasemmalla n potenssiin keskellﺣ۳, ja n
log n oikealla.
Joten siellﺣ۳ on todellinen jﺣ۳nnitysnﺣ۳ytelmﺣ۳.
Nﺣ۳hdﺣ۳ﺣ۳n maanantaina.
>> [APPLAUSE]