>> [Speel van musiek]
>> David J. MALAN: Alle reg.
So terug te verwelkom.
Dit is CS50, en die is die einde van die week, drie.
>> So onthou in die afgelope paar weke, het ons spandeer nogal 'n bietjie van
tyd op C, op ontwikkeling, op sintaksis.
En dit is heel normaal, as jy nog sukkel met die probleem Stel 2, te wees
gebons jou kop teen die muur.
Dit is kripties-looking fout boodskappe en foute wat jy
kan nie heeltemal jaag.
Omdat, gerus wees, wat in net 'n paar weke sal jy terugkyk op
dinge soos Caesar, en [? V-genair,?] miskien selfs kraak, en
besef net hoe ver het jy gekom in 'n kort tydperk van die tyd.
So as dit enige troos, hang in daar vir nou.
>> Vandag, egter, is ons begin met die oorgang om dinge hoër vlak.
En ons begin om te neem as vanselfsprekend aanvaar dat julle weet hoe om die program, of by
minste die begin van die dat comfort vlak.
En ons sal begin om te dink oor hoe ons kan gaan oor die ontwerp van programme meer
effektief.
Hoe kan ons gaan oor die optimalisering van die doeltreffendheid van ons algoritmes, en
algemeen oplossing meer interessante probleme.
En begin om te neem as vanselfsprekend aanvaar dat, As ons wou, kon ons ook kode op enige
van die voorbeelde wat ons in gedagte het.
So vandag, het ons nie raak die klawerbord vir enige vorm van kode.
Dit sal veel hoër vlak wees, en uiteindelik oor probleemoplossing.
>> So te kry om daardie punt, laat my stel dat die volgende sewe
reghoeke uit sewe deure, agter wat is 'n hele klomp van die
nommers, waaronder die nommer 50.
Laat my by hierdie projek op hierdie skerm hier so goed.
En stel voor dat ons nodig het om 'n vrywilliger te help om my 'n nommer in die voorkant van
die internet hier om te sien.
Kom op, in die pienk.
Alle regte.
Wat is jou naam?
>> JENNIFER: [onhoorbaar]
>> David J. Malan Jammer?
>> JENNIFER: Jennifer.
>> David J. MALAN: Jennifer.
Alle reg, Jennifer.
Nice om jou te ontmoet.
Kom up.
So het hierdie hier is sewe deure, en wat Ek wil graag om te doen vir ons hier,
in die voorkant van al jou klasmaats, word vind ons die getal, 50.
'N nommer te vind, kan jy loer agter enige van hierdie deure deur eenvoudig
op een van die deure, en dit sal openbaar sy nommer.
En laat ons sien hoe vinnig jy vind ons die getal, 50.
>> 15.
16.
50.
Mooi gedoen.
Alle regte.
Rondte van applous vir Jennifer.
>> [Applous]
>> Alle regte.
So, wat was jou strategie vir vind die getal, 50?
>> JENNIFER: Um, ek het gedink miskien is indien -
[Onhoorbaar]
>> David J. Malan Oh.
Gee dit 'n sekonde.
So was jou strategie vir vind die getal, 50?
>> JENNIFER: So het ek net begin by die begin om te sien wat die eerste getal
was, en dan het ek gedink, miskien as hulle is gesorteer, ek sal net hou
afluister hoër op?
>> David J. MALAN: OK.
En ons lyk gevind wat die geval te wees.
Alhoewel, laat ons terug skil die lae net 'n bietjie, en jy wil om te gaan
voor en onthul die ander deure jy kon gekies het?
>> JENNIFER: O, liewe.
>> David J. MALAN: Ag.
>> JENNIFER: So het ek net gelukkig.
>> David J. MALAN: So jy het gelukkig nie.
Alle regte.
So nie sleg nie.
Maar dit is 'n interessante insig, reg?
As jy aanvaar, en jy het kry, Inderdaad, 'n bietjie geluk is daar.
Maar as jy aanvaar dat die getalle was gesorteer, kan jy meer presies te wees
oor hoe dit beïnvloed jou gedrag?
>> JENNIFER: So as hulle is gesorteer, ek gedink miskien is die kleinste tot die grootste.
>> David J. MALAN: OK.
>> JENNIFER: Of as dit beland baie groot, dan is die grootste tot die kleinste.
>> David J. MALAN: OK.
So die grootste tot die kleinste, of kleinste tot die grootste.
Maar laat my stel, veronderstel jy het gekry het ongelukkig, en dink dat hulle
is nie, in werklikheid, gesorteer, hoeveel van die deure kan jy gehad het om te blik
agter in die ergste geval?
>> JENNIFER: Almal van hulle.
>> David J. MALAN: Almal van hulle.
So laat se veralgemeen dat as n.
Daar gebeur te wees 7, maar laat ons meer algemeen sê daar is 'n deure op die
skerm hier.
So in die ergste geval, sou jy om te kyk agter 7 deure, of N deure.
En so is dit regtig nie, dit is 'n bietjie van ' geluk van vandag, maar dit is regtig 'n lineêre
algoritme van die spesies, selfs al is jy was soort van spring rond.
Is dit regverdig?
>> JENNIFER: Ja.
>> David J. MALAN: Wel, laat ek sien of jou strategie verander as ek beweeg om ons te
ons tweede voorbeeld hier met 7 verskillende deure.
Dieselfde getalle nie, maar dit tyd wat hulle is gesorteer.
Wat is jou strategie hier gaan wees, probeer om uit jou gees wat
die ander getalle is -
>> JENNIFER: OK.
>> David J. Malan - vroeër?
>> JENNIFER: Kom ons begin met die eerste een.
>> David J. MALAN: Alle reg.
Begin met die eerste een.
4.
Nou waar jy gaan om te gaan, en hoekom?
>> JENNIFER: 4 is baie klein.
So as hulle is soort miskien kleinste tot die grootste, moet dit
twee keer nie, en -.
>> David J. MALAN: OK.
Kom ons kyk, wat dink jy?
>> JENNIFER: Probeer die laaste een.
Nice.
>> David J. MALAN: Baie mooi gedoen.
Alle regte.
>> [Applous]
>> David J. MALAN: OK.
So jy is eintlik om dit te doen verskriklik, omdat jy
doen dit baie goed.
Wat laat ons nie in staat is om te maak sekere punte.
So laat ons probeer om terug te rol hier.
>> JENNIFER: OK.
>> David J. MALAN: Baie goed gedoen het, nietemin.
So jy begin by die begin, jy sien dat dit was 4, dan is jy
verskuif na die einde.
Maar dink jy nie kry gelukkig daar is, en veronderstel 50
was iewers anders.
Wat jou derde stap gewees het?
>> JENNIFER: Gaan terug na die begin.
>> David J. MALAN: Gaan terug aan die begin.
OK, so jy sal aangeraak het hierdie deur, wat was 8.
Alle regte.
So dit is nie 50.
Waar sou jy gelyk het volgende?
>> JENNIFER: As ek gedoen het nie Weet hulle gesorteer.
>> David J. MALAN: Korrekte.
Wel, as jy nie weet hulle is gesorteer -
>> JENNIFER: Ag, geweet het, ja.
>> David J. Malan - maar julle het nie weet waar 50 was nie?
>> JENNIFER: Slegs te gaan.
>> David J. MALAN: Alle reg.
OK.
Gaan hou.
OK, wat ek kan werk.
>> JENNIFER: OK.
>> David J. MALAN: Nou, as jy net gaan om voort te gaan, wat is jou
algoritme wentel ondersteun in.
>> JENNIFER: Die lineêre -.
>> David J. MALAN: Dit is 'n soort van lineêre.
Maar laat my stel, laat my sit op die plek.
Laat my verfris die bladsy.
dieselfde nommer, dieselfde reëling, dieselfde deure.
Maar dink terug aan daardie eerste dag in klas toe ons skeur 'n telefoon boek in
helfte, soort van, en wat was ons strategie is daar?
>> JENNIFER: Begin by die middel.
>> David J. MALAN: OK.
So begin by die middel.
So laat ons gaan voort en boots dit.
Begin by die middel deur die onthulling dat die deure.
So het die nommer 16.
So, wat sou die sterk man gedoen het nie, wat die telefoon boek skeur in die helfte,
te kry om die volgende raaiskoot?
>> JENNIFER: Gaan in hierdie helfte.
>> David J. MALAN: En hoekom die reg?
>> JENNIFER: As hulle soort van kleinste tot die grootste, dan is 50 moet wees
aan die einde.
>> David J. MALAN: Goed.
Heeltemal redelike.
Dus, net soos 'n telefoon boek, gaan jy na die reg in teenstelling met die linker, maar hier
is die sleutel afhaal.
Jy kan nou weggooi, of skeur af, helfte van hierdie probleem, sodat jy nie
met 7 deure, maar eintlik met net 3.
Dit is ongeveer die helfte van die omvang van die probleem.
Alle regte.
So nou wat jy wil hê gedoen nadat jy gaan reg?
>> JENNIFER: So 16 is nog redelik klein, relatief tot 50, so miskien sal ek probeer,
soos hierdie een.
>> David J. MALAN: Alle reg.
42.
Alle reg, so nou wat is jou instink wat jy vertel?
>> JENNIFER: Ek kan weggooi hierdie en dan net -
>> David J. MALAN: OK.
Goed is, kan jy weggooi die linker helfte was daar.
>> JENNIFER: - kies hierdie een.
>> David J. MALAN: En die reg.
>> JENNIFER: Ja.
>> David J. MALAN: So selfs al is dit moeilik miskien sien, wanneer daar net
7 deure, dink, nou, die konsekwentheid van die
algoritme jy net toegepas word.
In die vorige geval, jy het gelukkig is, wat so groot was.
Maar jy het gebruik 'n heuristiese, Ek sou sê.
Jy gebruik soort van jou instink, en wetende dat dit gesorteer is, as dit is mooi
klein aan die begin, natuurlik, ons het het meer om te gaan na die regterkant.
Maar in 'n sekere sin, jy het gelukkig, want miskien was dit die getal 100,
en miskien 50 was meer in die middel.
Miskien 50 was nog hier.
>> Maar wat jy het 'n bietjie anders hierdie tyd was, julle het dieselfde ding
weer en weer.
En ek sou argumenteer dat dit wat jy net het, al is dit beïnvloed deur die telefoon
boek byvoorbeeld, is iets veel meer algoritmiese, en nog baie
minder spesiale cased.
Veel minder instinktief.
So in die einde van die dag, hoe sou jy beskryf die doeltreffendheid van die
eerste algoritme, waar jy gegaan het links na regs, teenoor die
tweede algoritme hier?
>> JENNIFER: Dit moet 'n mens, soos, miskien helfte van die tyd, of selfs meer, ja.
>> David J. MALAN: OK, miskien selfs meer.
Kom ons druk 'n bietjie harder op daardie.
Wat regtig, as ons voortgaan om hierdie logika, het ons beslis gehalveer die
tyd met hierdie tweede algoritme deur gooi weg die helfte van die
getalle nie, maar wat het ons op die volgende iterasie, wanneer Jennifer geopenbaar
die tweede getal?
>> Ons gehalveer die nommers van die deure weer.
En dan wat het ons te doen na dat indien was daar meer deure te speel met?
Ons wil halveer hulle, en weer, en weer en weer.
En dit was net soos julle almal staan ​​by die eerste week van
klas, die helfte van julle sit, half van julle sit, die helfte van u
sit, totdat een eensame siel gestaan.
En ons het gesê dat die loop van die tyd van dat die aantal stappe wat dit geneem het was
op die einde van wat?
>> Spreker 1: [onhoorbaar]
>> David J. MALAN: So log basis 2 van n, of net meer eenvoudig, teken van n.
So iets logaritmiese.
En die grafiek was nie 'n reguit lyn wat net erger en erger, was dit
hierdie interessante kurwe wat nie kry so sleg met verloop van tyd.
So laat ons vashou aan hierdie idee.
Kom ons dank Jennifer.
Baie dankie vir die kom op up.
En een sek.
Geen lessenaar lampe vandag, maar ons hoef CS50 stres balle.
>> JENNIFER: Yay.
>> David J. MALAN: Alle reg, hier.
Dankie vir die aangaan die spanning hier.
Alle regte.
So laat ons kyk of ons kan nie nou formalisering van hierdie 'n bietjie meer.
So weer, wat ons nou net gedoen het, was basies dieselfde ding as wat ons gedoen het
in die eerste week.
Maar eerder as die einde met net 'n lineêre algoritme, wat ons uitgebeeld
voorheen as dit reguit lyn, waardeur, as ons sit nog een deur op
die skerm, dan Jennifer sou gehad het om te kyk, potensieel,
agter een deur.
As ons nog twee deure, kan sy ' om te kyk agter twee deure.
>> En so, was daar hierdie lineêre verhouding tussen die grootte van die
probleem op, sê, die x-as, en die bedrag van die tyd wat dit neem om te
los op die y.
Maar die prentjie wat ek het verwys na vroeër was dit groen lyn.
Groen doelbewus, omdat dit net beter gevoel.
In teorie, die algoritme, toe ons dit gedoen het met die telefoon boek, wanneer ons dit gedoen het
met julle tel mekaar, en in die tweede geval is, wanneer Jennifer net
het dit hier, dit was soort fundamenteel beter.
Want dit was nie net twee keer so vinnig.
Dit was nie eens vier keer so vinnig.
Dit was heeltemal afhanklik van wat die grootte van die insette was, oor hoeveel
stappe om dit uiteindelik het.
>> En so het hierdie eenvoudige idee dat ons almal het vanselfsprekend met die telefoon boek,
Net so kan toegepas word om iets soos hierdie.
En dit mag dalk meer ligtelik bekend as, as jy dalk
dink, verdeel en oorwin.
Nie in teenstelling met wat ons gedoen het, natuurlik, met die telefoon boek.
>> Maar die pseudokode, onthou, was dit.
So ons sal nie weer doen nie, maar onthou dat die eerste week, almal van ons het opgestaan
en dan die helfte van julle sit, die helfte van jy sit die helfte van julle gaan sit.
Dit algoritme is geïmplementeer in 'n bietjie van 'n kullery manier, in die sin dat dit
net een van my is nie die tel, fundamenteel, meer doeltreffend.
In daardie geval, ek was gebruik te maak 'n sekondêre bron.
Soort, verskeie CPUs, verskeie brein, verskeie slim mense in die
kamer was om my te help kry van iets lineêre na iets
logaritmiese, van iets rooi na iets groen.
>> Maar in hierdie geval, Jennifer alleen kan fundamenteel verbeter op die
prestasie van haar eerste algoritme deur, weer, dink net 'n bietjie moeiliker.
En nou, wanneer dit tyd is om te implementeer hierdie dinge, uitzoeken
watter reëls van die kode wat jy kan skryf soos dat jy kan dit weer doen, en
weer en weer, soort in 'n herhaling mode.
Omdat jy nie gaan die te hê luukse, soos Jennifer het op die eerste, te
net nog 'n hele klomp van die ifs en sê: hmm, as die eerste getal 4,
laat my spring al die pad na die einde.
Oe, as dat die getal is te groot, laat my arbitrêr terug te beweeg
na die tweede element.
Jy sal vind dat dit gaan 'n baie wees harder te formaliseer wat ons mense
vanselfsprekend aanvaar as 'n baie redelike heuristiek nie, maar 'n rekenaar is slegs
gaan om te doen wat dit wat jy vertel om te doen.
>> Nou is dit het 'n baie interessante implikasies.
Hierdie grafiek is 'n soort van bedoel om te sorteer oorweldig visueel, maar kennisgewing, waar
is die reguit lyn in die grafiek?
Waar is die lineêre grafiek wat ons noem n?
Wel, dit is soort van die rigting van die onderkant van hierdie prentjie, reg?
So al wat ons gedoen het, is ons het soort van ingezoomd uit na die x-as en die
y-as om te probeer om 'n gevoel van wat om te kry ander vorme van boë lyk.
>> En die besonderhede van die wiskundige uitdrukkings vandag sal nie so saak nie
veel nie, maar sien dat daar is 'n baie algoritmes wat veel erger as
iets wat lineêr.
Inderdaad, in blokkies gesny n lyk baie sleg.
2 na die n lyk baie sleg. n vierkant lyk baie sleg.
En ons sal sien wat sommige van dié kan wees in werklikheid vandag.
En log n voel nie so sleg nie, maar beter as n 'log basis 2 van n.
Maar jy weet, sou dit selfs gewees het meer amazing as Jennifer, of as ons,
dat die eerste week, het gekom met iets wat log van log van n.
>> So met ander woorde, daar is hierdie hele reeks moontlike oplossings te
probleme, maar selfs hier, kennisgewing wat gaan gebeur nie.
Toe ek vergroot nie, na watter van hierdie krommes gaan blyk te wees die absolute
ergste van die mense wat op die skerm nou?
So n blokkies lyk mooi sleg op die oomblik nie.
Maar as ons zoom uit en sien meer van die x-en y-as, wat gaan
oorheers uiteindelik?
So dit blyk eintlik dat 2 tot die n, en jy kan dit uit figuur net deur
steek in sommige toenemend groot nommers, en jy sal sien dat 2 van die
n, wel, kry groter veel vinniger.
As ons regtig vergroot nie, na 'n 2 aan die n algoritme suig absoluut.
Ek bedoel dit gaan neem nogal 'n bietjie van die tyd vir die
rekenaar te kansellasies deur.
>> Maar jy sal sien met verloop van tyd, veral met toekomstige probleem stelle en selfs
finale projekte, is jou data stel kry groot, alles reg?
Selfs in die eerste weergawe van Facebook, as die aantal vriende, en die
aantal geregistreerde gebruikers het 'n groot, jy kan sorteer van die telefoon in en
implementeer iets met lineêre soek, of 'n baie eenvoudige sortering
algoritme, as ons vandag sien.
Jy het om te begin dink harder en harder oor hierdie probleme.
En die aard van die probleme plekke soos Facebook, en Google en Microsoft,
en ander werk op juis hierdie soort van groot data soort van vrae
toenemend hierdie dae.
>> Alle regte.
So Jennifer se sukses in die tweede algoritme, eerlik, sy het ongelooflik
goed die eerste keer nie, maar laat se skryf dit soos geluk, sodat ons
kan maak hierdie punt.
In die tweede geval is, het sy 'n aged algoritme wat herhaal weer en
weer, maar sy het vir toegestaan ​​'n sekere aanname dat ons toegelaat
haar, maar sy uitgebuit 'n paar besonderhede oor die tweede keer dat sy nie die
eerste keer.
Wat was wat?
>> Dat die lys is gesorteer.
So gou as die lys gesorteer is ons beweer dat Jennifer was in staat om te doen
fundamenteel beter.
7 deure, ja, is dit nie interessant, maar dink dit is ons 7 miljoen deure.
Teken van n gaan beslis baie, baie uit te voer
vinniger in die lang termyn.
Maar sy het die te hê deure gesorteer vir haar.
Nou, ek het die vryheid om dit te doen vooraf op die rekenaar skerm
hier, maar veronderstel dat Jennifer gehad het om te doen wat haarself?
Veronderstel dat die deure in vraag verteenwoordig data in 'n databasis, of
Vriende geregistreer vir Facebook, of enige webblaaie op die internet wat
verskeie webwerwe dalk nodig na die indeks of soek oor.
>> Veronderstel dat jy net 'n rou data stel en dit is links na jou toe, of na
Jennifer dat sortering te doen?
Dit, eerder, vereis dat ons antwoord Die vraag, wel, hoeveel tyd
sou geneem het Jennifer, of selfs my hierdie syfers te sorteer in advance so
dat sy kan neem voordeel van dit?
Reg?
Omdat die implikasie is natuurlik Indien dit my nogal 'n rukkie om te sorteer
die nommers, wat die heck sorg dat jy kan 'n aantal soos 50 so vinnig vind,
as in Jennifer se geval, as ons meer as oorweldig die bedrag van die totale tyd
dit het deur sorteer dinge in advance?
>> So kom ons kyk of ons nie die verf die prentjie hier.
Ek het 'n hele klomp meer stres balle, as dit sal help
breek die ys hier.
En as jy nie omgee nie, ons het sewe vrywilliger -
op, OK.
Sjoe.
Sodat ons nie hoef te spandeer op die lessenaar lampe, dit lyk.
Alle regte.
So hoe om jou twee in die voorkant.
Hoe gaan jy twee ouens in die rug.
So dit is vier.
Hoe gaan jy in die voorkant vyf, ses en sewe.
Reg daar.
Jou vriend se wys jou uit, sodat jy die prys.
>> Alle regte.
Kom up.
En waarom ons nie hê jy ouens kom hier.
Ek gaan om te gee jy elke 'n nommer.
En voort te gaan en reël self identies aan wat is
uitgebeeld op die skerm.
>> [INTERPOSING Voices]
>> David J. MALAN: Oop, jammer.
Fout.
Alle regte.
Wel, hier gaan ons.
Nommer vyf.
Nommer ses.
Een, twee, drie, vier, vyf, ses, sewe.
O, dit is moeilik.
>> Spreker 2: Ek sal net 'n -.
>> David J. Malan Goeie deal.
Alle regte.
Dankie vir jou deelname.
>> [Applous]
>> OK.
Alle regte.
So het ons vier, twee, ses, een, drie, sewe, vyf.
Vervolmaak sodat ons sewe vrywilligers hier wat gelyk is in breedte aan die
skikking wat ons speel met die vroeër.
En ek het sewe vir redes wat sal net
gerieflik in 'n bietjie.
En ek gaan na die eerste stel voor dat ons sorteer hierdie sewe vrywilligers.
As jy wil, in die eerste, hallo te sê al is.
Aangesien dit gaan wees om 'n ongemaklike paar minute.
Stel julself.
>> GRACE: Hi, ek is Grace.
Ek is 'n stage in Leverett House.
>> BRANSON: Hi.
Ek is Branson.
Ek is 'n groentjie in sweis.
>> GABE: Hi.
Ek is Gabe.
Ek is 'n junior in Cabot.
>> NEIL: Ek is Neil.
Ek is 'n groentjie in Matthews.
>> JASON: Ek is Jason.
Ek is 'n groentjie in Greenough.
>> Mike: Ek is Mike.
Ek is 'n groentjie in Grays.
>> JESS: Ek is Jess.
Ek is 'n stage in Leverett.
>> David J. MALAN: Uitstekende.
Alle regte.
Wel, dankie aan al ons vrywilligers hier tot dusver.
En die uitdaging aan hand gaan om te sorteer van hierdie ouens, maar dan
Ons gaan 'n bietjie te dink hard oor hoe doeltreffend ons eintlik
ingedeel.
So laat ons eers probeer om hierdie.
Julle kan mekaar se nommers net deur die plasing om die hoeke.
Gaan voort en neem 'n paar sekondes, en soort self van die kleinste op die
links na grootste op die regterkant.
Gaan.
>> OK.
Goed.
Dit was regtig darn vinnig.
Nou kan iemand hier, wat was die algoritme dat hierdie ouens toegepas?
>> Spreker 1: minste tot die meeste.
>> David J. MALAN: OK.
Minste tot die meeste is regtig sorteer van die doel, maar ek is nie seker dit is
regtig 'n algoritme.
Minste tot die meeste nie vertel my stap-vir-stap wat om te doen.
Ja?
>> Spreker 1: [onhoorbaar]
>> David J. MALAN: OK.
So as jy sien 'n persoon kleiner as jou nommer, dan skuif na
die reg van hulle.
So dit is nou om meer uitdrukkingsvolle meer soos 'n algoritme, omdat jy
kan sê, as dit, dan is dit.
So het ons 'n soort voorwaardelike bou.
En hierdie ouens was dat 'n paar om te doen keer, want sommige van julle het 'n bietjie
van 'n afstand.
En daar was vermoedelik 'n soort van herhaling gaan aan in hul gedagtes.
>> Maar laat ons probeer om daardie te formaliseer.
As jy ouens kan weer terug hierdie reëling.
Kom ons kyk of ons kan dit nie 'n formalisering bietjie, en dan vra die vraag, net
hoe doeltreffend is dit?
Natuurlik, wanneer ons dit doen, meer stadig, dit gaan voel so goed van
'n algoritme, maar laat ons kyk of ons kan sit ons vingers op die presiese stappe.
>> So julle twee ouens is vier en twee.
Of jy reg of verkeerd om?
Ooglopend verkeerd is.
So het ons verruil.
Nou gaan ek opsy te skuif hier en sê: 05:56.
Is jy reg of verkeerd?
>> GABE: Korrekte.
>> David J. MALAN: Korrekte.
Ses en een?
Nee.
Ruil.
So dit is twee swaps.
Ses en drie?
Nee.
Ruil.
Ses en sewe?
Lyk goed.
Sewe en vyf?
>> JESS: [onhoorbaar]
>> David J. MALAN: OK, ruil.
En gesorteer.
Alle regte.
So natuurlik nie, reg?
So daar is meer aan die gang.
Maar, inderdaad, hierdie ouens, selfs net instinktief.
gehou beweeg.
Hulle het net nie ophou nie, wanneer hulle reggestel een probleem.
So.
Trouens, ek gaan te hê dieselfde ding te doen.
Ek gaan om te sorteer van rewind terug aan die begin van hierdie probleem,
of die begin van hierdie reeks mense, laat ons begin bel hulle.
>> En nou Wat moet my algoritme op die tweede pas wees?
>> Spreker 1: Dieselfde ding.
>> David J. MALAN: Dieselfde ding.
En dit, ek begin te hou, reg?
So gou as wat jy kan vind jouself doen dieselfde ding weer en weer, dit is
meer soos 'n algoritme, en minder menslike instink.
>> So nou, hier gaan ons weer.
Twee en vier?
No
Vier en een?
Ag, was daar wel 'n paar werk nog gedoen moet word.
Vir drie en?
Goed.
Vier en ses?
Ses en vyf?
Ses en sewe?
OK, nou, gedoen.
OK, no.
Ek het om terug te gaan.
>> So nou, weer, is ons om dit te doen 'n bietjie meer doelbewus.
En nou, is daar net een brein uitvoering van hierdie algoritme.
Een CPU, as jy wil.
En eerlik, dit is die enigste bron ons gaan om toegang te hê.
En sodra ons terug gaan nie na 'n klavier en het iets soos C by ons
beskikking, kan ons slegs die skryf van 'n program wat een ding doen op 'n tyd.
Terwyl, hierdie ouens 'n oomblik gelede, het ons aged hul kollektiewe breinkrag
soos jy ouens het in week nul.
So laat ons hou om dit te doen.
>> Twee en 'n mens.
Twee en drie.
Drie en vier.
Vier en vyf.
Vyf en ses.
Ses en sewe.
Gedoen?
So ek is nie, maar laat my speel duiwel se advokaat.
Doen ek, die soort van die rekenaar wat net het 'n slaagsyfer deur middel van hierdie reeks
mense, weet dat ek gedoen het?
>> Spreker 1: No
>> David J. MALAN: So hoekom?
Wat sou ek het om te doen ten einde te sluit beslissend dat ek gedoen?
Waarskynlik een meer slaag.
Reg?
Want al wat ek weet van dat die vorige slaag, is dat ek 'n fout reggestel.
En dit beteken, miskien is daar ' nog 'n fout
wat ek nodig het om te herstel.
So ek kan net seker wees deur omwikkelen, en dan nagaan, 1-2, twee-en-
drie, drie en vier, vier en vyf, vyf en ses, ses en sewe.
OK, nou het ek geen werk.
>> Ek kan beslis onthou wat ek gedoen het nie werk met iets soos 'n veranderlike,
graag 'n int.
Noem dit swaps, en as swaps is 0 keer ek kry hier, en dit begin by 0, dan
Ek wil net dom wees om aan te hou heen en weer, seker die weer, en
weer en weer, reg?
Omdat jy vassit in sommige soort van oneindige lus.
So gou as daar is 0 swaps, ons kan beweer dat dit
algoritme is inderdaad voltooi.
>> Nou, laat ons 'n naam op hierdie punt.
Die algoritme wat ek stel voor ons net geïmplementeer is iets genoem borrel
soort, wat bekend staan ​​as sodanig in die sin dat die nommers wat groter soort
borrel hul pad na die top, of tot aan die einde van die skikking van getalle.
Maar hoe doeltreffend was hierdie algoritme?
Hoeveel treë Ek het fisies in 'n neem, byvoorbeeld, om dit te sorteer
sewe mense?
>> Vier tot vyf?
OK, te veel is uiteindelik gaan die antwoord wees.
Maar selfs dan, die spesifieke getal is nie so interessant.
Kom ons veralgemeen dit as 'n.
So as ek het n 'mense hier, en hulle was, soort van, in enige volgorde op die
begin, in die oorspronklike bestelling.
Wel, hoeveel stappe wat ek het te neem op die eerste slaag?
Dit was een, twee, drie, vier, vyf, ses, en hulle is sewe mense, so
Dit is sewe, ses -, so dit is n minus een stappe die eerste keer.
>> Nou, hoeveel stappe wat ek het om te neem wanneer ek terug gespoeld?
Wel, ons kan eintlik verdubbel dat indien Ons wou eintlik om nie, maar vir nou, is ek
net gaan om te sê, alles reg, nog n minus 1.
So die n minus 1 gaan kry irriterende tred te hou, so laat
net om effens.
So 2n stappe.
So 14 stappe, gee of neem.
>> Hoeveel keer het ek 'n stap om die volgende keer?
Wel, dit is 3n.
regtig.
En nou, in die ergste geval, vir Byvoorbeeld, hoeveel keer het ek
gegaan heen en weer, heen en weer, uitvoering van hierdie algoritme uitruiling
mense op elke slaag, rofweg?
Dit is eintlik n 'vierkantig, reg?
>> Want in die ergste geval, jy kan soort van dink oor hierdie intuïtief,
selfs al is dit dalk 'n bietjie n bietjie van die tyd om te sink in
In die ergste geval, wat sou hierdie sewe mense is gelyk, in
terme van die ooreenkoms van hul getalle?
Heeltemal agtertoe, reg?
En net dat na te boots, wat was jou naam nou weer?
>> Mike: Mike.
>> David J. MALAN: Mike?
OK, Mike, jy kan net saam met my oor hier vir net een sekonde?
Eintlik nie.
Jammer Mike, laat se rewind.
Wat is jou naam nou weer?
>> NEIL: Neil.
>> David J. MALAN: Neil.
OK, Neil, kom jy met my, as jy nie omgee nie.
So ek gaan voor te stel, net vir eenvoud, wat Neil is nou in sy
ergste moontlike geval.
Maar onthou hoe ek geïmplementeer my algoritme.
Ek vergelyk, vergelyk, vergelyk, vergelyk, vergelyk, o.
Nou hierdie ouens is uit van orde, so ek los.
So julle ouens ruil.
Maar nou kyk, hoeveel verder nie Neil het om te gaan?
Dit is min of meer n.
Jy weet, is dit nie eintlik n.
Dit is soos, n minus 1, maar ek kry vererg hou van die klein
nommer, so laat ons noem dit net n.
>> So as Neil beweeg 'n stap maksimaal elke tyd, en Neil n stap te beweeg,
Ek het dit regtig vervelige pas te maak heen en weer, dit is ongeveer
om dit te doen, n werk, 'n totaal van n keer, want dit gaan om my te neem
dat baie stappe Neil almal te kry die pad na waar hy hoort.
Laat staan ​​almal anders as jy ouens is almal mis-bestel as well.
>> So kom ons noem borrel soort n vierkant.
Die loop van die tyd van hierdie algoritme, die uitvoering van hierdie algoritme, die
doeltreffendheid van hierdie algoritme ons sal net beskryf meer
algemeen as n vierkant.
Wat is lekker, want ek kon doen om die dieselfde voorbeeld met agt mense, nege
mense, 'n miljoen mense, en dat antwoord is nie van plan te verander.
>> So as jy ouens sal nie omgee, laat herstel jy na die plek waar jy begin het.
En laat ons probeer om twee ander benaderings en kyk of ons kan dit nie doen nie fundamenteel
beter as dit.
So hierdie tyd, ek gaan voor te stel 'n soort van verskillende algoritme.
Dit was baie slim van ons laaste tyd, en julle ouens was reg om die
reg instink van net 'n soort van die uitruiling van paarsgewyse.
Maar as ek regtig wou dit te benader eenvoudig, en my doel is om te beweeg
al die klein getalle op hierdie manier, en druk al die groot getalle wat
manier, hoekom nie ek doen net wat in die mees naïewe manier moontlik en kyk of ek
beter kan doen as wat 'n redelik komplekse algoritme?
>> So laat ons sien.
Vier is 'n mooi klein aantal, so ek is gaan jy om daar te verlaat oomblik.
Oe, nommer twee is nog beter.
So kan jy net vorentoe te stap vir 'n oomblik?
Dit is tans my kleinste getel kandidaat, en ek gaan om te onthou
wat nie, soos 'n veranderlike.
Maar Ek gaan om te hou keur.
Is daar iemand wie se getal is kleiner?
Ses, no.
O ja, daar is Neil weer.
>> So ek gaan om jou te stoot terug soort van konseptueel.
Neil na vore sal kom.
En nou, die veranderlike wat ek gebruik om te hou van wat die kleinste het
getal word opgedateer te bevat Neil se plek.
Wel, laat ons sien.
Drie, sewe, vyf.
OK, ek weet Neil was die kleinste.
Wat is die eenvoudigste ding vir my nou te doen?
Ek gaan nie my tyd te mors deur net borrel Neil een plek na links.
Hoekom kan ek nie net sit Neil waar hy behoort, wat natuurlik waar?
>> Al die pad aan die begin.
So Neil, kom saam met my.
En wat was jou naam nou weer?
>> GRACE: Grace.
>> David J. Malan Grace.
OK.
So Grace, ongelukkig, is jy soort in die pad.
So hoe los ons die probleem?
Reg?
As dit is 'n skikking, is daar net sewe plekke.
Onthou dat, met Rob, het ons gepraat oor verklaar ouderdomme, en ons het net 'n
beperkte aantal ouderdomme?
Dieselfde idee hier.
Ons het net 'n beperkte aantal ints.
Grace is 'n soort van in ons manier, so hoe ons dit regmaak?
>> Die eenvoudigste manier is soos, Genade, jammer.
Jy gaan hê om oor te gaan daar sodat ons kan vertrek.
Nou, as jy dink oor hierdie, miskien Ons het net het die probleem vererger.
En dalk het ons gedoen het nie, want wat as Grace was op die regte plek?
Maar ons weet sy is nie, want Anders sou sy gewees het
staan ​​vorentoe in plaas van Neil in hierdie tyd, reg?
Ons het reeds nagegaan haar nommer.
>> Alle regte.
So nou, Neil is op die regte plek, en Ek kan dit doen 'n effense optimalisering.
Vir die volgende minuut, ek gaan om te ignoreer Neil almal saam, sodat dit nie te
mors sy tyd, of per ongeluk ruil hom na die verkeerde plek.
So nou, hoe kan ek kry die volgende element wat is die kleinste?
Twee.
Dit is 'n goeie, indien jy wil om vorentoe te stap en
Ek sal aan julle dink.
Ses, nie goed nie.
Vier, drie, sewe, vyf, nie goed nie.
So laat my beweeg om jou te jou regte plek.
En ons het net gelukkig hierdie tyd.
>> Nou, ek gaan om dit te ignoreer twee ouens, en nou nog een
slaag deur middel van hierdie.
Ses, wat 'n mooi klein aantal.
Kom vorentoe.
O, jammer.
Grace se nommer is beter, so stap op vorentoe.
Vier.
Jammer, Grace.
Gaan weer terug.
Nommer drie is beter.
Sewe.
Vyf.
Maar nou, wat is jou naam nou weer?
>> JASON: Jason.
>> David J. MALAN: Jason.
So Jason is nou die kleinste element Ek het gekies.
Waar is hy gaan om te gaan?
So waar ses is.
En jou naam nou weer?
>> GABE: Gabe.
>> David J. MALAN: Gabe.
Gabe is in die pad.
Wat is die maklikste ding om te doen?
Ruil die twee ouens en gaan voort.
So laat ons nou sien.
Wie is die kleinste?
Vier.
Laat my net 'n soort oneerlik.
Vyf gaan wees om die kleinste.
Ek soek die volgende, indien jy wil om te stap vorentoe, wat ek te doen het met
hierdie ouens, met Gabe?
Ruil weer.
So nou, steeds effens buite orde.
Ek het gevind Gabe tot die kleinste, so Ek pop hom uit, beweeg julle oor.
En gedoen het.
>> So antwoord is dieselfde.
Die eindresultaat is dieselfde.
Watter van hierdie twee algoritmes is beter?
Die tweede een, het ek gehoor.
Hoekom?
>> SPREKER 3: Dit is n stappe [onhoorbaar].
>> David J. MALAN: Dis n stappe op die meeste.
Interessant.
So is dit al?
So hoe het ek die kleinste element?
Hoeveel stappe het ek het om te neem die vind van die kleinste element?
Ek het 'n kyk al die pad aan die einde, reg?
Want in die ergste geval, wat As Neil was hier?
So net die vind van die kleinste element neem my n stappe, of n minus 1.
Maar, OK.
So los Neil.
Onthou dat 'n minuut of wat gelede.
>> Maar hoe het ek die volgende kleinste element?
Dit is 'n minus 1, of n minus 2 werklik, van die aantal stappe.
So OK.
So ek het n 'minus 2.
Alle regte.
So wat voel 'n bietjie beter.
Alle regte.
Hoeveel treë die volgende keer nommer drie te vind?
So n minus 4.
So dit afneem, een minder stap op elke iterasie.
So dit beteken beter voel, reg?
As laaste tyd was dit ongeveer n keer n, hierdie keer is dit n minus 1, plus n minus
2, plus n minus 3, plus n minus 4, dot, dot, dot.
Maar as jy onthou van jou hoërskool handboeke, die klein oneerlik
vel aan die agterkant wat formules, indien jy optel hierdie reeks van getalle,
Wat is die totale aantal stappe gaan wees dat ek hier op te neem?
>> Dit is een van daardie, soos, n minus 1 keer n, gedeel deur 2.
So laat my sien as ek kan trek hierdie vir net 'n oomblik.
En weer, ek is soort van afronding sommige getalle net om ons lewe eenvoudige,
maar as ek reg onthou, is dit iets soos as Ek doen n minus 1 dinge, dan is n minus
2, dan is n minus 3, dit is ongeveer iets soos hierdie meer as 2, en as ek
vermenigvuldig dit uit, dis eintlik n vierkant.
Dit is nie te goed voel. n minus n meer as 2.
>> Maar hier is die ding.
In rekenaar wetenskap, wanneer die probleme begin om te kry interessant is, is wanneer n
regtig groot.
En toe n regtig groot, wat van hierdie waardes gaan al te domineer
van die ander?
Dit is soort van die n vierkant, reg?
Ja, deel deur 2 is redelik goed.
Maar as jy praat oor die miljarde stukke van data, of triljoene
stukke van data, OK, so jy is twee keer so vinnig.
Maar wat regtig omgee as dat 'n groot aantal, As hierdie faktor is wat kry
groter en groter.
En seker maak dit meer van 'n verskil as hierdie man.
So selfs al is jy ouens is reg, die tweede algoritme, sal ons noem dit
seleksie soort, is, in die werklike wêreld, 'n bietjie vinniger potensieel, omdat ek
neem minder en minder stappe elke keer.
>> Dit is nie regtig fundamenteel vinniger.
Want as ons eintlik speel hierdie uit vir groot waardes van n, aan die einde van
die dag, vir groot genoeg N, dit is nog steeds gaan voel redelik stadig.
Wel, laat my toe om een laaste pass op daardie.
Dit is wat ek sou noem seleksie soort.
Kan julle weer julle 'n laaste keer?
En in die laaste geval, ek gaan iets voor te stel
genoem voeg soort.
Invoeging soort wese, konseptueel, 'n bietjie anders.
>> Eerder as om heen en weer en kies die kleinste element, ek is
net gaan om te gaan met elkeen van hierdie ouens soos ek hulle teëkom, en voeg
hulle in hul korrekte plek.
So ek is net gaan om te begin met Grace, en ek sien dat sy is nommer vier.
Waar kom nommer vier behoort?
Ek het nog nie begin sorteer enigiets, so ook die genade kry om net daar te bly.
En nou gaan ek te eis, as jy kon neem 'n stap na regs, hierdie
my gesorteer lys, dit is my ongesorteerde oorblywende lys.
So nou is ek volgende gaan voort, En wat is jou naam nou weer?
>> BRANSON: Branson.
>> David J. MALAN: Branson.
So Branson is nommer twee.
So ek gaan om jou te neem uit vir 'n oomblik.
En nou, waar jy behoort in hierdie reeks?
So aan die regterkant van die genade.
So weer, ons is soort van die maak van Grace doen 'n baie werk hier.
Waar sit ons u?
So ons gaan om jou te skuif na die links, en voeg Branson daar.
Maar nou het ek beweer dat Julle is gedoen.
Maar kennis, ek is nie die gebruik van ekstra ruimte.
Dit is nog steeds 2 elemente hier, 5 hier.
Totale verskeidenheid grootte is 7, so ek is nie verneuk, alles reg?
>> So nou het ons, met Gabe hier, die nommer ses, waar val jy?
Jy het gelukkig weer.
So jy net daar bly.
Net 'n effense stap na regs net om duidelik te maak dat jy gesorteer.
En nou het ons Neil weer, die aantal een, waar jy gaan?
En nou is waar ons sal begin om te sien dat hierdie algoritme, al op die eerste
oogopslag, voel redelik slim, kyk Wat is die punt om te gebeur nie.
As jy kon stap vorentoe.
>> Waar wil ons Neil te sit?
So natuurlik hier nie, so hoe kry ons Neil daar?
Kom ons doen dit stap-vir-stap.
Gabe, waar jy nodig het om te gaan?
Yep, so neem 'n groot stap, of twee half-stappe te maak
een stap daar.
Grace, waar jy gaan?
Goed.
So 'n stap.
En uiteindelik, Branson?
Nog 'n stap.
En nou kan ons sit Neil in plek.
>> So nou, hierdie logika.
Selfs al is ons nie verskuif Neil oor en oor en oor hom te sit
waar hy gaan, in die ergste geval, die volgende getal ons mag teëkom kon
die aantal, sê, was daar 'n aantal nul is, dan gaan ons almal om te skuif
hierdie ouens.
Veronderstel dat daar is 'n aantal, negatiewe een, dan het ons om te skuif
al hierdie ouens.
So ons is regtig net 'n soort van daarby die probleem om, soos wat ons is
die oordrag van die koste van die keuringsproses so te voeg
proses, soos wat julle het net rofweg n minus iets om te beweeg
aantal stappe.
En dat die getal van die stappe is slegs gaan te verhoog as ek kies meer getalle,
As ek het om te hou stoot julle ouens terug, en weer, en weer terug.
>> So het die hartseer ding is nou al hierdie algoritmes is n 'kwadraat.
Kom ons gaan voort en te danke aan hierdie ouens, en sien hierdie 'n bietjie
anders.
Baie goed gedoen.
>> [Applous]
>> Alle regte.
Daar gaan jy.
Dankie vir die -
>> BRANSON: [onhoorbaar] hou die nommers.
>> David J. MALAN: Nee, jy mag hou die getalle so goed.
Alle regte.
Mooi gedoen.
Alle regte.
So laat ons kyk of ons kan nou nie 'n opsomming vinniger en meer visueel,
presies wat nou net gebeur hier soos volg.
Ek gaan om voort te gaan en trek Firefox.
Ons sal verbind hierdie demonstrasie op die kursus se webblad.
Java is 'n bietjie lastig om te werk in sommige blaaiers hierdie dae.
So as jy speel met dit by die huis, besef jy dalk nodig Firefox te gebruik
te kry om dit te werk.
En wat gaan ek doen met hierdie demonstrasie is die volgende.
>> Aan die onderkant, ek het 'n hele klomp van die opsies, insluitend 'n begin en 'n
stop knoppie.
Ook, as 'n eenkant, daar blyk te wees 'n fout in hierdie programme, waardeur jy
kan nie eintlik sien die begin of stop knoppie tensy jy bevel of Alt
plus en zoom in, wat vreemd wys jou meer knoppies.
Dus net FYI as jy speel met hierdie by die huis.
Nou gaan ek begin om te klik in net 'n oomblik na spesifiseer 'n vertraging van,
soos, 200 millisekondes hier, net sodat ons kan sien wat gebeur.
>> So ek beweer dat dit 'n visualisering van die eerste algoritme
hierdie ouens het, borrel soort, waardeur Ons verruil mense paarsgewyse.
Die sleutel insig van hierdie visualisering is dat die hoogte van die bars
verteenwoordig die grootte van die getal.
So die langer die bar, die Hoe groter die nommer.
Korter die bar, kleiner die nommer.
En as jy sien, gaan ons deur die eerste iterasie van hierdie algoritme
uitruiling groot en klein getalle, sodat die klein getal kom eerste en
die groot aantal gaan aan die regterkant.
>> En so gou as wat ons kry aan die einde van verskeidenheid van baie meer as sewe nommers, ons is
gaan om terug te gaan na die begin.
En verwag dit.
Op die ver links, is dat die outjie gaan om te wissel na die kant, en hierdie
proses herhaal.
Nou is hierdie visualisering kry vinnig vervelig, so laat my voort te gaan en te stop
dit verander die vertraging iets veel vinniger net om nou te kry, 'n gevoel vir
hierdie algoritme.
>> So selfs al het ek het dit versnel, is dit soos die opgradering van my verwerker, koop
'n nuwe rekenaar.
Ek het fundamenteel nie verander nie my algoritme, maar jy kan wel sien meer
duidelik as met die mens, dat die groot getalle borrel tot die top,
en die klein getalle borrelende af na die bodem.
En nou hierdie ding hier gesorteer.
En as 'n eenkant, in die blokkies, is daar net 'n paar boekhouding daar te
help tel hoeveel vergelykings, of hoeveel swaps het
eintlik gedoen is.
>> Wel, laat ons probeer om een ​​van die ander wat ons gesien het.
Laat my op borrel soort hier, en laat my kies, en hierdie hele webblad
is 'n bietjie karretjie.
Kom ons aanvaar die risiko en dit loop weer.
Daar gaan ons.
So laat ons doen seleksie soort.
Ek weet nie hoekom die spyskaart verskyn daar.
Kom ons zoom in wat op te los fout, dit verander na 50.
Ag, laat ons werklik te doen wat baie vinniger.
Vyf millisekondes of so, en begin nie.
>> So dit is seleksie soort.
So weer, dink oor wat ons gedoen het met die mense hier.
Ons het deur die skikking en gekies die kleinste element weer
en weer en weer.
Nou moet ek sê dat nog baie sleg.
Dit is nog steeds n 'vierkantig, gee of neem, maar dit was, in die werklike wêreld, 'n bietjie
vinniger, want ek was inderdaad neem effens minder stappe elke keer.
Maar ons is net praat wat?
Miskien 40 of so bars hier?
Ons praat nie 40 miljoen.
So dit is nie heeltemal duidelik vir my dat was inderdaad 'n beduidende wins.
>> Laat my trek, en verander ons derde algoritme, wat kies
voeg soort.
En nou is dit regtig karretjie omdat die spyskaart moet regtig nie daar.
So nou gaan ons terug hier blaai en begin hierdie algoritme.
Woep, begin en stop.
So hierdie een soort het 'n mooi patroon om dit, waardeur ons weer
invoeging van die mens, of in hierdie geval, die bars in
hulle toepaslike plek.
En dit is reeds gedoen voordat Ek het omgedraai.
Maar hierdie een ook, in teorie, is nog steeds n 'kwadraat.
>> So laat ons kyk of ons nie kan vat hierdie soos volg.
Ek gaan om voort te gaan en net te gee ons soort van 'n gemeenskaplike manier van praat
oor hierdie dinge, laat my voer net 'n bietjie van die notering hier.
Jy oor om te sien iets genoem groot O, want dit is letterlik 'n groot
O. En dit is 'n manier dat 'n rekenaar wetenskaplike of 'n wiskundige selfs gebruik
die loop van die tyd om te beskryf van 'n paar algoritme.
Hoeveel treë dit eintlik neem?
>> Nou gaan ek myself verleentheid te stel met my handskrif hier in net 'n oomblik.
Maar laat my gaan voort en sê dat dit sal groot O hier.
En laat my voer een ander simbool, 'n kapitale omega.
Omega gaan na die teenoorgestelde wees, wese, van die groot O. AANGESIEN groot O
beteken, in die ergste geval, hoeveel tyd dalk 'n algoritme neem, in
terme van n, is omega gaan wees hoeveel tyd kan dit
neem in die beste geval.
En ons sal sien wat ons bedoel met beste geval in net 'n oomblik.
>> So laat ons begin iets eenvoudig.
Laat my begin met 'n lineêre soek.
So nie te sorteer.
Ons sal noem dit lineêre soek.
En nou, 'n bietjie tafel uit hierdie.
En nou, in die geval van lineêre soek, In die ergste geval, hoeveel stappe is
dit gaan my 'n te vind aantal arbitrêre keuse?
En daar is 'n totale deure of n totale getalle.
Ergste geval.
Hoeveel treë ek gaan hê om te neem die getal 50 te vind in 'n verskeidenheid
van n deure?
En hoekom?
Want dit kan wees om al die manier oor na die einde.
So baie soos Jennifer ondervind, die nommer 50 was al die pad, so in
die ergste geval lineêre soek is 'n groot O van n, sal ons sê.
>> Wat van die beste geval, As jy regtig gelukkig?
Dit is net gaan 'n stap te neem, of 'n konstante aantal stappe.
So sal ons beskryf dat as 1.
So, dit is redelik goed.
Nou wat as ons het iets hou binêre soek?
So binêre soek, in die ergste geval het hoeveel tyd?
>> [INTERPOSING Voices]
>> David J. MALAN: So eintlik, ek hoor dit in 'n paar plekke.
So dit is eintlik meld n, gee of neem, want as deel ons die lys in die helfte
weer en weer en weer, ons is in staat om om uit te vind, uiteindelik, die waarde,
As dit is daar, maar daar is 'n vangs.
Wat is die veronderstelling dat ons moet vanselfsprekend aanvaar vir binêre soek?
Dit moet uitgesorteer.
Dit is nie uitgesorteer is, kan jy verdeel die ding in die helfte weer en weer, en jy
kan gaan verlaat, en jy kan reg gaan, en jy kan gaan links en regs, maar jy
gaan nie die element as om uit te vind Die lys is nie gesorteer, want
jy mag misloop nie.
Omdat jou heuristiese, want na links of regs gaan word gebrekkig as dit
inderdaad nie gesorteer.
So daar is soort van 'n versteekte koste om die gebruik van iets soos hierdie.
>> Nou, laat ons gaan in ons sortering algoritmes soek nie -
Ag, eintlik laat ons gaan in hierdie leeg.
Binêre soek in die beste geval?
Dit is ook 1 as dit net gebeur om te wees in die baie middel van die skikking, of
die middel van die telefoon boek.
Nou kom ons doen borrel soort.
So weer, nou is ons die aanvang van die soorte, nie die navrae.
>> In die ergste geval, hoeveel stappe gedoen het wat ons eis borrel soort gaan neem?
n vierkant.
So ek gaan dit te trek.
Ooh, my handskrif lyk nog erger wanneer dit geprojekteer dat groot.
Alle regte.
Sodat se N-kwadraat.
En in die beste geval van borrel soort, hoeveel stappe gaan dit neem?
1, het ek gehoor.
>> Spreker 1: n.
>> David J. MALAN: n, hoor ek.
>> Spreker 1: 2.
>> David J. MALAN: 2, hoor ek.
Hoor ek 3?
Alle regte.
So ek het gehoor 1, n, 2, maar laat haal uitmekaar ten minste die eerste van daardie
voorstelle, 1.
Dit is nie 'n slegte instink, want dit soort volg 'n patroon hier.
Maar as dit neem net 1 stap, hoe om in die wêreld kan ek sê dat die lys
gesorteer is, want as ek net toegelaat 1 stap, hoeveel elemente te neem
Ek kon eintlik gaan om seker te wees?
Wel, net 1, wat beteken daar is 'n minus 1 elemente wat kan wees uit
orde, en ek gaan net op geloof na op soek na 1 element wat die
ding is gesorteer.
So 1 is nie hier los.
So minimaal, hoeveel het ek om te sien?
>> [INTERPOSING Voices]
>> David J. Malan n minus 1, of werklik, n, want ek nodig het om te kyk na elke
element om seker te maak dat dit is nie buite orde.
Maar weereens, sal ons die soort van golf ons hande op die kleiner getalle en
aanvaar dat, as n groot kry, hulle is oninteressant in elk geval.
So dit is borrel soort.
En nou, laat ons doen hierdie laaste twee.
Seleksie soort, en dan sal ons doen voeg soort.
En dan sal ons blaas jou gedagtes met iets veel
beter as al hierdie.
Alle regte.
>> Wat is die ergste geval loop tyd van seleksie soort?
>> SPREKER 4: n vierkant.
>> David J. Malan n vierkant, ek hoor.
Maar hoekom n vierkant, intuïtief?
>> SPREKER 4: Omdat ons net dit gedoen het.
>> David J. MALAN: Omdat ons net dit gedoen het.
OK.
Goeie antwoord.
Maar intuïtief, is die rede waarom seleksie sorteer n vierkant?
Wat het ons te doen het weer en weer?
Ons het om te hou die skandering deur, is jy die kleinste, is jy die
kleinste, is jy die kleinste.
En toegestaan ​​is, het ons in staat was om n te neem stappe te doen, dan is n minus 1, dan is n minus 2.
Maar as jy soort voeg diegene wat al op, of neem dit op die geloof wat ek het bygevoeg
hulle in advance, kry ons ongeveer n vierkante minus 'n paar kleiner getalle.
So ek gaan om te noem dit 'n vierkant.
Maar met die seleksie soort in die beste geval, hoeveel stappe is dit
gaan om my te neem?
>> SPREKER 5: [onhoorbaar]
>> David J. MALAN: Dis ongelukkig nog steeds n vierkant, reg?
Want as ek die kies van die kleinste element, en ons het sewe mense hier,
Ek weet net, wanneer ek na die heel einde, wat ek gevind het die kleinste
nommer, waar hy of sy mag gewees het.
Maar hoe kry ek die volgende kleinste getal?
Ek het 'n ander pas om te doen.
So in die beste geval, wat is die insette te seleksie soort?
Dit is 'n reeds soort lys, nommer een, nommer twee, nommer drie, nommer vier.
Maar ek is 'n rekenaar.
Ek kan net kyk na een ding op 'n slag.
Ek kan nie uitsorteer van 'n stap terug soos 'n mens en sê:
ooh, dit lyk reg.
>> Ek kan net beoordeel korrektheid in seleksie soort deur die kies van die
kleinste getal.
Maar selfs as ek 'n nommer een eerste, As ek weet nie iets anders oor
die ander getalle, wat ek doen nie, al wat ek weet dat ek 'n skikking ingehandig
of 'n stel van die deure agter wat getalle, is die enigste manier wat ek weet dat 'n mens
was die kleinste?
As ek al die pad hier en besef, Damn, een was inderdaad die kleinste.
>> Maar hoe bepaal ek dan dat twee is die volgende kleinste?
Deur dit te doen dieselfde ondoeltreffendheid weer en weer.
So uiteindelik, met inplaas soort, hoe, in die ergste geval,
het, sê ons dit doen?
Dit het ook 'n 'kwadraat.
En hoe oor met die beste geval?
Ons sal laat dit as 'n fotonische lewe.
Ons sal vul dat leë volgende keer, maar laat my eers voor dat ons
fundamenteel beter doen as al hierdie, al reg?
>> So dink vir jouself wat inplanting soort gaan wees.
Wel, dit was nie baie dramatiese, want ek is die enigste een
wat het die verandering.
Sjoe.
OK.
So hier het ons 'n ietwat verskillende demonstrasie.
As ek zoom in hier, sal jy sien dat op die linker ons borrel soort, in die
Midde ons seleksie soort, en op die heel regs, ons het iets wat ons
het nie gekyk na nog genoem saamsmelt soort.
Maar kyk wat ons het al hier tot dusver vandag.
Wanneer Jennifer eerste keer op die verhoog, ons het in die skikking van getalle
weer en weer, met lineêre soek, en ons het lineêre loop van die tyd, 'n groot O
van N, om so te spreek.
>> As ons nou kyk na die eerste week van klas, toe ons verdeel en heers,
en ons het die telefoon boek skeur, en Jennifer, en ons gesamentlik
aged dat die sleutel insig, wat was om te herhaal jouself weer en weer deur
een of ander manier weg te gooi, gooi weg, weg te gooi, die helfte van die probleem, of
oor die algemeen, die verdeling van 'n probleem in die helfte, en dan die behandeling van die kleiner stuk
die probleem as konseptueel ekwivalent aan die ander kant, het ons een of ander manier het
fundamenteel beter.
Maar met borrel soort, met seleksie soort, met inplaas soort, het ons kan
geen sodanige insigte wat Jennifer het.
Ons pretty much net gestap terug en weer 'n hele klomp van die tye, en ons
tweaked dinge 'n bietjie, uitruiling in hierdie volgorde, miskien
voeg of te kies.
Maar aan die einde van die dag, ek het 'n baie ongemaklike loop heen en weer.
Ons het nie regtig iets hefboom smart soos Jennifer het, soos die verdeling
en verower.
>> So saamsmelt soort, daarenteen, wat ons sal sien nie tot volgende week, gaan dit
om die invloed wat die sleutel idee deur die verdeling die insette, en dan te halveer, en dan
halveer, en dan te halveer.
En op elke iterasie van die lus, sorteer die linker helfte, en die reg
helfte, dan is die linker helfte van die linker helfte, en die reg om die helfte van die links, dan
die linker helfte van die reg om die helfte, en die reg om die helfte van die reg om die helfte.
En herhaal weer en weer.
>> So, sien jy hierdie visueel, maar dit is wat op ons wag volgende week.
En in die algemeen, wanneer ons dink 'n bietjie bietjie harder op enige sodanige probleem.
Ons het n 'vierkantig aan die linkerkant, n vierkantig in die middel, en n
teken N op die regterkant.
So daar is jou regte fotonische lewe.
Ons sal sien dat jy op Maandag.
>> [Applous]