[Powered by Google Translate] [Aste 3, Continúa]
>> [David J. Malan - Harvard Unibertsitatea]
>> [Hau CS50 da. - CS50.TV]
>> Guztiak eskubidea. Ongi etorri berriro. Hau CS50 da eta 3 aste bukaera honetan.
>> Beraz, ezagunenak dira, iaz Harvard zer Innovation Lab izeneko jarri zuen abian,
edo i-lab, HBS en campus ibaian zehar eraikin zoragarri bat da
hau da, unibertsitateko ikasle, ikasle GSAS, guztietan campus ikasleek zabalik,
fakultateko barne, eta elkarrekin gauza berritzailea lan egiteko leku bat da,
batik bat, ekintzaile gauzak
eta 0 edo gehiago lagunak dira zerbait ekintzailea egiten bada, pentsatzen
bai klase honetan zehar, klase honen ondoren, edo haratago.
>> Beraz J epe egin dute gauza bat bidaiak horiek,
eta horietako batek, New York, eta horietako batek Silicon Valley da.
Space oso mugatua da, baina aukera bat sorbalda igurtzi to MBAs
eta campus osoan zehar, eta egia esan, ikasleek graduondoko denbora eremu horiek, hurrenez hurren
txateatzen startups, ekintzaile txateatzen eta antzekoak.
Beraz, bada, egiaztatu URL hau hemen.
Da, halaber, eskuragarri online diapositibak.
>> Ezin behera tonua ditugu etxe audio besterik pixka bat?
Bazkaria gurekin ostiral honetan izan nahi baduzu, Fire & Ice 1:15 etan, mesedez, buru dago.
Apologies formularioa dagoeneko iritsi duzun denbora bete.
Baina tradizio hau jarraitu dugu aurrera.
>> Gaur egun, hainbat arazo konpondu ahal izango dugu, maila handiagoa eztabaida jarraituko dugu,
askoz ere txikiagoa da bideratua, gaur egun, gutxienez, kodea, eta askoz ere ideia gehiago.
Beraz, uste back aste 0 telefono-liburu bat Tore dugu erdia,
horren helburua zen zerbait egin behar, admittedly, apur bat dramatikoa
baina puntu Bilatzen duen ez izatea, nahitaez bidaltzeko,
Lehen begiratuan agian uste duzu argi geratu da.
Eta, oro har, arazo konpontzeko agian ez du zertan beti onena
Konponbide nabarmenena agian ez duela zertan onena izan.
Beraz, telefono-liburu hau izan genuen, eta Egia, gela honetan gurekin izan senak
seguru asko, erdi-erdian Mike Smith bila hasi eta, ondoren, joan ezkerrera edo eskuinera
alfabetoaren letra edozein izanda ere azkenean gertatu oinarritzen da.
>> Baina hori ideia sinplea da dugu gizakiak hartu duten hain luze ematen
benetan zure gogoaren abangoardian etortzen hasi behar
arazoak lortu telefono-liburu bat baino askoz konplexuagoa delako,
berean simple horiek, ikuspegi liluragarria gaitu egingo dira
askoz ere zailagoa da eta gehiago interesgarri arazoak konpontzeko,
horien artean, gauza batzuk dagoeneko egun hauetan emandako hartuko dugu.
Bilioika web orrialdeak daude, eta oraindik, Google eta Bing eta antzeko
gauzak aurkitzeko gai Gurekin horrela.
Hori ez da gertatzen lineal bilaketa baten bidez, guztiak ahalik eta web orriak bidez bilatzen.
Facebook da gai dira zure lagunak dira, edo lagunen lagunak,
eta hori ere egin ahal izango dira, itxuraz berehalako batean egun hauetan
nahiz eta milioika erabiltzaileei dute.
>> Eta, beraz, nola arazoak konpontzeko benetan eskala horretan izango da, azken finean, murrizteko
ideiak begiratu aste 0 dugu, eta pixka bat gehiago gaur egun.
Ez dugu berriro algoritmo hau exekutatu, baina gogoratzen aste 0 ariketa hau ere egin genuen
non denek genuen Zutik, 1 zenbakia izango ditu, eta
eta, ondoren, denek auto-kopuruan izan dugu off parekatu, zure zenbakiak gehituz batera,
ondoren, Koadrilaren erdia eseri iterazio guztietan.
Beraz, 500 ikasle eta 250 125 joan ginen, eta abar.
Baina, astelehena, gisa esan, ideia indartsua dago
izan zen, tamaina bikoiztu dugu arazo hori bada
eta Justizia edo EE 10 lagunak itzuli zen gelan sartu eta gurekin sartu
ondo izan dugu, ziurrenik, agregazio osoa talde hori zenbatu
1 Begizta gehiago big iterazio zuten soilik agian duelako bikoiztu tamaina
edo EE 10 kasua bikoitza tamaina baino pixka bat gehiago.
Eta, beraz, apur bat pasatzeko denbora gehiago genuke,
baina ez genuke izan 400 edo 700 urrats gehiago pasatzeko.
>> Just argazki hau margotzeko modu bat, apur bat gutxiago abstraktuak, ez dute denek Zutik.
Baina dutenek aukeratu zuen, gaur egun, orkestra eseri axola ez balu, zutik,
dezagun ikusi dugu irudikatu dezakezu artean duten pertsona altuena da
konparazio-algoritmoa moduko bera eginez.
Beraz, bada, orkestra, nire apologies, baina 1. Pausoan ari zaren eserita, Zutik;
2. urratsa, bikotea off edonork Gertuko duzu,
irudikatu nor da taller, eta eseri zara laburragoa bada.
Ondoren, errepikatu.
[Ikasle murmuring]
>> Ongi da.
Ongi da. One geratzen da zutik. Zein da zure izena? >> Andrew.
>> Andrew, orkestra atalean pertsona garaiena gaur dira.
>> Zorionak. [Txaloak eta txaloak] Larreina. Eserlekua. Beraz, Andrew aurkitu dugu.
Baina zenbat denbora hartu me, esate baterako, Andrew aurkitu
50 + edo, beraz, pertsona orkestra hau?
Hartu nuen oso ikuspegi sinple bat eta hemen.
Eta 2 pertsona dut Zutik eta alderatu besterik ez ditut,
eta, ondoren, esaten duenak pixka bat laburragoa izan da, "Ongi da, eseri duzu"
eta taller pertsona izan zen gogoratzen dut.
Ondoren, errepikatu dut errepikatu, errepikatu, eta pertsona altuena zintzilik I
aurkitu dut norbait horiek baino apur bat taller arte, eta amaitzen da
pixka bat laburragoa izan ditu, ondoren, eseri.
Baina orkestra Atal honetan algoritmoa dela, badago-n,
zenbat urrats algoritmoa, hartu egingo da? >> [Ikasleen] N.
>> N hartu, eskuinera, kasurik okerrenean, eta, beraz, delako hitz egiten da,
altuena pertsona oso azken pertsona dut besterik ez ausazko zorte txarra da.
Beraz, kasu horretan, txarrena, algoritmoa, denbora lineala da, n,
non n espazioa pertsonen kopurua guztira, arazoaren tamaina da.
Algoritmoa honi buruz?
Izan ere, guztiak altxatu eta berriro erdia eseri,
duzun erdia eseri, eseri duzun erdia.
Zenbat urrats behar izan diren duzun n bada hemen?
[Ikasleen] N log n. >> Hori okerragoa izango litzateke. Saioa hasi n.
>> Beraz, saioa n, nahiz eta ez duzu nahiko gogoratu logaritmo bat zer den,
oraingoz, eskertzen erlazionatzen dela, nolabait, hau eta halving halving eta halving.
Faktorea 2 ez du zertan izan behar. 3-faktore bat izan daiteke.
Baina faktore, hala nola, mota berean errepikatzea da, arazoaren tamaina hemen hasten da
baina gero, berehala doa hemen, eta ondoren, hemen, eta gero hemen, eta gero hemen.
Ziztadak txikiak hartzen ari zara arazoa, benetan ari zaren kanpoan Tajadura ere
handi bat jaitsi swoop aldi bakoitzean.
Beraz, 50 pertsona izan genuen eta, ondoren, 25 eta, ondoren, 12 ½ edo 13 pertsonak zutik,
ondoren, 6 ½ eta abar zutik azkenik besterik ez Andrew geratu zen arte.
Beraz n erregistroa deitzen dugu, eta hau honela ikusteko dezakezu.
Gogoratu hemen argazki hau non algoritmo lineal bat, lerro gorriaren bezala dago,
lerro horiak zenbaketa 2s algoritmoa izan zen ikasle kontatuta erabiltzen dugun
iraganean, baina, gaur egun, Santo Grial berdea linea honetan jarraituko du
non orkestra atalean pertsonen kopurua bikoiztu egin dugu izanez gero edo, besterik gabe, esan zuen,
infernua, egin ditzagun osoan gela guztiek Zutik, ez aurre handi bat, hala nola,
gutxi gorabehera bikoiztu delako zenbat pertsonak dira hemen,
1 iterazio gehiago, ez da arazo bat.
>> Aurkitu dugu Andrew edo duenarentzat gertatzen Andrew baino altuagoa izan
entreplanta edo balkoian.
Simple hartu dugun hainbeste telefono-liburu batean ematen Beraz, ideia hau,
konturatzen ez direla hainbeste toki ezberdinetan aplikatu ahal izango dugu.
Just jargon batzuk Slap - benetan, baino jargon lehenik eta behin,
utzi joan argazki hau me hemen.
Oraintxe n eta n / 2 buruz hitz egin dugu, eta, ondoren, saioa n,
baina etorri, seihilekoan zehar egingo dugu,
beste formula matematiko sort iraupena ideia orokor hau deskribatzeko.
Hauek dira oraingoz testuinguru luze baino lehen ikusiko dugu delako
algoritmo horiek benetan ordezkatzen.
>> Baina hemen nabarituko lineal line n, lerro zuzena da, benetan, oso baxua seinalatuz oraintxe.
Ilusio optikoa sort hori aldatu besterik ez dugu zer adierazten du x ardatzaren
eta y ardatza, eta nahi dugun norabidea edozein zuzen puntu bat egin ahal izango dugu.
Baina arrazoia da, beraz, itxuraz lauak gaur egun
grafikoa gela egin behar dugu exekutatzen ari askoz motelagoa aldiz delako.
Oraingoz, jakin bizitza algoritmo nahiko txarra batzuk daudela,
horietako batzuk ez hartu n urratsak edo, hobeto oraindik, n urrats baina gehiago saioa.
Beraz, lerro gainetik n hemen beheko oharra n aldiz n erregistroa,
ikusi eta zer esan nahi du, hau baino lehen luzea dugu.
Gainetik karratu n, eta ez dugu edozein n karratu algoritmoak ikusi oraindik, baina buruz ari gara.
Eta hori itxura oso txarra da.
Dago 2 n, zerbait esponentzialean, eta sentitzen are okerragoa da.
Eta, hala ere, bitxikeria bada ere, gero n cubed, Oraindik duzu aurretik pentsatzen sort izanez gero,
mota egin nahi duzu matematika, 2 n benetan askoz straighter bihurtzen da,
askoz ere handiagoa n baino cubed ardatz begiratuz gero urruti nahikoa out.
Beraz, konturatu oraintxe ardatzak hauek dira arbitrarioki 2 10 x ardatza.
>> Eta zer esan nahi du horrek?
Horrek esan nahi du 2 pertsonek gela 10 pertsona.
Arazo tamaina, edozein testuinguru da: That guztiak x bide bat da.
Eta ardatz bertikala oraintxe segundo kopurua edo urrats kopurua
denbora-unitate batzuk.
Baina hori 0 eta 60 eta 0 eta 10.
Baina zoom out mota, Excel edo diagramen software batzuk agian, bada
eta igo dugu, 200.000 nabarituko 2 atsegin n zerbait
n karratu aldiz martxan guztiz gaindituak izaten da,
n cubed, n log n - dena buruz hitz egin dugu, beraz, oso urrun.
Eta, oraindik, harrapaketa Facebook bezalako gauzak buruz hitz egiten hasi
asko, asko, jende asko guztiak elkarrekin lotuak,
pertsona izan dira parte hartu dutenak, n, bakoitzak horietatik n lagunak asko izan dezake
guztiek buddy-buddy sort bada munduan,
ondo, n aldiz n dagoeneko, eta, beraz, hori ahalik eta lagun karratu n
gutxienez 1 norabidea, n karratu ahalik eta adiskidetasuna.
Beraz, dagoeneko iradokitzen Facebook gizarte grafikoan bilatuz, nolabait esateko,
formula mota horiek adierazten has daiteke.
>> Itzuli gara eta hau askoz zehatzagoak egiteko,
baina, oraingoz, hurrengo asteetan asko helburu
ziur ez algoritmoak ezartzeko edo kode buruz izango da
honen antzeko zerbait sortu denbora askoz gisa hartu amaieran.
Baina informatika buruz gauza liluragarriak jarraitzen baduzu, arlo honetan
klaseak hartu CS121, CS124 bezala, biak ikastaroak teoria,
dagoela, egia esan, mundu honetan dauden arazo batzuk
funtsean, ezagutzen dugun neurrian, ezin dira konpondu edozein azkarrago
grafikoak horien txarrena baino benetan iradokitzen du.
Beraz, mundu honetan irekita arazo askoz hobeto gizakiak baino, beraz, orain arte egin asko.
>> Beraz, dezagun hasteko, ondoren, adibide honekin.
Sean kamera honekin borroka, guztiak ere awkwardly bideoa ikusi dugu.
Baina errealitatea zen Sean taula honetan zenbaki 7 atsegin aurkitzeko tasked zen,
gogoratzen esan nuen, "Ez dago nonbait paper pieza horiek edo zuria ateak atzean
"Kopurua 7. Sean, aurkitu digu."
Eta wonderfully awkward zen ikusteko
izan zen benetan delako arazo honekin borrokan.
Baina errealitatea zen Sean egin gelan edonork egin izan baita.
Pixka bat gehiago hartu zuen, ohiko pertsona baino liteke izan,
baina ez zela trikimailu batzuk arazo hau bere gain hartu zuen,
zela zerbait falta zuen bere gain hartu zuen.
Eta ez da begiak ehunka jaitsi zirela kontuan hartuta zuen.
>> Baina errealitatea zen arazoa sarrera ausazko zenbakiak sorta bat bada
eta zu, hala nola 1 zenbakia eskatu
onena egin dezakezu bilaketa lineala.
Hasi ezker, eskuinera mugitzeko, edo eskubidea etan hasiko da, ezkerrera mugitu.
Retroactively, pentsatzen dugu agian, "Sean, zergatik ez beste muturrean besterik ez duzu hasi?"
Beno, 7 bezain erraz izan da izan hemen ausaz,
baina nahita jarri dut han figured I ez du amaieran hasi behar duelako.
Beraz, manipulatu mota dut egoera, baina aukera ausazko 7 izan zitekeen edozein lekutan.
Beraz, eskuin muturrean hasita hobea izan liteke, ondoren,
baina zer izanez gero, hurrengo urteko 7 mugitzen dut beste nonbait?
Hori ez da arazoaren konponbidea funtsean berri bat -
1 amaieran edo beste hasita duzunean emandako beste hipotesi ez.
Beraz, Sean zenbakiak bidez bila hasi zen, eta esan zuen, "5. Hori ez da hemen."
Gero, hara joan zen eta 19 ikusi eta, ondoren, pausatuta 20 segundotan egin zuen,
ondoren, hau ireki zuen 13 eta, ondoren, itxurazko bihurtu zen
ez dagoela ez dirudi hemen eredu bat izan.
Ezin izan da, 1, 2, 3, 4 edo antzekoak. Baziren zenbakiak hutsuneak, eta horrek ez du lagunduko.
Eta ere, Izan ere, erabili dut paper pieza merkea hauek estaltzeko zenbakiak
da, benetan, nahita, kendu dut paper pieza horiek guztiak galtzen delako,
gurekin gehienak, Sean barne, seguruenik begiratu litzateke sort macroscopically-
arbelean eta esan zuen, "Oh, 7, jakina da bertan." Ez dugu berehala.
>> Eta hori, neurri batean lan egiten du, giza burmuina izan daiteke,
baina errealitatean, bere begiak edo kontuan izan zen ziurrenik skimming zenbakiak eskuinetik ezkerrera,
eskubidea, erdiko kanpo utzi zerbait izan zen joan fisiologikoki
hala nola sentitu zen berehala gertatzen ari den bezala,
baina odds are barrutik metodologia mota batzuk ez zen 7 aurkitzeko.
Eta, hain zuzen ere, gaur egun ari gara array egitura eta datuak buruz hitz egiten
eta memoria ordenagailu baten barruan, gauza bakarra dugu gizakiak egin dezaket
oroimen indibiduala kokapenak begiratu 1 aldi berean.
>> Beraz, beste behin, baliteke baita ere estalita paper batzuk
ikusi ahal izango dugu ez delako dena den. Bakarrik egin ahal izango ditugu, aldi berean gauza 1.
Beraz, kasu honetan, Sean kasuan, hemen ginen eta gero, hara joan ginen
eta gero, hara joan ginen, hemen, hemen, hemen, baina clever amaieran
eta mota horretako saltatu hau arbitrarioki eta 7 bertan aurkitu.
Hau ez da batez ere berezia izan zen. Oso ordena.
Baina azkenik aurkitu zuen 7.
Baina orain takeaway onena egin dezakezu orduan emandako informazioa ez da benetan
zenbakiak ausaz ordenatuko baino beste ezker edo eskuinera abiatuko da.
Edo arraioa, ausaz dezakezu ireki ateak, baina orduan ere zer ez ausazko izan nahi?
Beno, nolabait formalizatzeko zer esan nahi du, hemen hasteko genuke,
ondoren, hemen, eta hemen. Sean handia egin, eta soilik ondo pasatzeko izan zen ikusteko.
Zer ordez bada arazoa pixka bat aldatu dugu eta ekarri aurtengo Sean, bada?
Egingo luke edonork izango eroso datozen etapa, eta pixka bat beste arazo bat konpontzeko
eta kamera agertzen?
>> Dezagun orkestra haratago joan you guys delako nahiko parte hartzen duten gaur egun dagoeneko.
How about pink, kapela? Goazen behera. Zein da zure izena? >> Alex. >> Alex. Ongi da.
Beraz, Alex aurtengo Sean izango da, eta agertuko da hurrengo urteetan hainbat
CS50 hitzaldiak merezi du.
Alex, politak zu ezagutzeaz. >> Nice zu ere.
Esku erronka da zuretzat errazagoa eta pixka bat duzula
duzun naiz kontatzeko zenbakiek berdinak dira hemen, baina gaur egun ordenatuko dira.
Beraz, zure helburua da 7 zenbakia aurkitu.
Eta benetan, benetan behar dugu hau iruzurra mota you're, ordenagailu bat bezala izango litzateke,
zer begira zenbakiak izan ziren une batez ago.
Klarion honekin benetan ez da asko lagunduko du,
baina dezagun asmoa ez duzula ez dakit zer array jatorrizko da.
Gaur egun ezagutzen duzun guztia duzula zenbakiak ordenatuko array
haien arteko hutsuneak izan daiteke, eta zure helburua da 7 zenbakia aurkitu.
Nola nahi duzu, zentzuzko gizakiaren, 7 zenbakia aurkitzeko?
>> Handiko baxua? >> Ados. Joan handiko baxua.
Eta ez malko horiek off. Dezagun igogailua horiek horiek berrerabili ahal izateko.
Ongi da, eta, beraz, 1. Itxaron. Mantentzeko joan aurretik, 1, argi eta garbi okerra izan zen.
Beraz, zer zure kontuan bidez hurrengo? Zein da zure hurrengo mugitzen da?
Hurrengoa. >> Ados. Hurrengoa. Good. 3, eta, beraz, okerra. Zein da zure hurrengo mugitzen da?
Joan mantentzeko. >> Guztiak eskubidea. Joan mantentzeko. 5.
Beraz, joan mantentzeko, eta utzi entregatu me hau posteridad.
7. >> Bikain. Oso ona. Found kopurua 7. [Txalo]
Beraz, ona izan zen, baina Sean ere, 7 zenbakia aurkitu.
Eta ez duzula benetan ustiatu informazio pieza gehiago defendatzen dut,
hau da, zenbaki horiek ordenatuko dira.
Beraz, hobeto egiten dugu? Edozein iradokizun hemen? Bai, berriro.
[Ikasleak] Binary bilaketa. >> Ideia ez daukat zer bitar bilaketa.
>> [Ikasleak] Hasi erdian. >> Erdian Hasi. Ongi da. Beraz, ikus dezagun ez gara daiteke.
Beraz ordez bada kontatzen ari zaren Irteeran erdialdetik aurrera eta erdiko atea ireki.
Horietako 8, beraz, arbitrarioki aukeratu bat ari zaren.
pixka bat ezkerrera edo eskuinera. Ongi da. 7! [Txalo] Very nice.
Ongi da, baina non ziren joan honekin?
Dezagun abiarazi izan duzu hemen gorbata besterik ez hausteko
berdin gertatu delako izan da baita.
Gertatu zen 7 zegoen jakin nahi dugu. Beraz, honen 13ra arte egongo da.
Beraz, ari ordenatuko eta erdian hasi ginen,
zer egingo zenuke hurrengo mugimenduan optimoa izan dira?
Joan ezkerrera. Eta, beraz, hemen telefono book Adibidez dator berriro.
13ra arte egongo da hemen eta zerrenda ordenatuko bada badakigu,
ondoren, paper pieza horiek guztiak gurekin uninteresting
dagoeneko 7 ezkerreko behar dugu ezagutzen delako
zenbaki horiek antolatuko dira eta 13 aurkitu dugu.
>> Beraz, zer da da zure hurrengo mugimenduan hemen? >> Ezkerrera joan. >> Ongi, ona da.
Beraz, ezkerrean, eta - itxaron, hey, hey, hey. Hori iruzurra.
Beraz, 7 aurkitu duzu, baina zer zen algoritmoa aplikatu besterik ez dugu?
Hasi erdian. >> Good. Beraz, zer ideia bereko luzapena logikoa da?
Oh, besterik ez horiek. >> Zehazki. >> Beraz, hemen hasten dut. >> Good.
Beraz, gaur egun, apur bat ezkerrera joan ginen berriro. 3 da.
Baina interesgarria takeaway gaur egun ez duten do bat zaintzeko buruz?
Hauek 2. >> Hauek 2. Beraz, gaur egun hau urrun joan daiteke, urrun joan daiteke.
, Orain zela 8 gero arazoa zen, tamaina 4 tamaina 2.
Nahiko hurbil ari gara. Berriz ere, 2 elementu horiek erdian joan da.
>> Ongi da. Beraz, sort da zorigaiztoko orain dela beti ari gara ezkerrera joan gara biribiltze duelako behera.
Baina hori fina, gaur egun hau bota dugulako kanpoan eta beste guztia, gurekin utzi besterik ez 7.
Eman dezagun txalo txanda. 7 aurkitu dugu berriro. [Txaloak] Larreina. Ziur.
Just 1 bigarren Hang on.
Nahiz eta prozesu hori hurrengo mota hartu pixka bat gehiago sentitzen dugu lukeena baino,
Egia, zure lehen senak onenak izan ziren, ezta? 7 eta berehala aurkitu dugu.
Baina aurkitu izana genuke 7 azkarrago, ez du axola zer, adibide honetan hau versus
zenbakiak ordenatuko dira guztiak galtzen delako, askoz ere telefono-liburu batean orri bezala,
hain zuzen ere, arazoaren erdia dezakezu txikitu berriro eta behin eta berriro.
Eta ez da nahiko erraza ikusteko 8 zenbakiak
1.000 orrialde telefono-liburuaren non ikusiko duzula bisualki ez bezala,
baina kasu honetan hemen Sean zen 7 bilatuz,
zenbat kasu txarrena urrats hartu zion? >> [Ikasleak] 7.
Txarrena kasuan, 7. Beno, kasu txarrenean ez 7 ez 8 ateak hemen.
Hartu dute litzateke zion 8 urrats.
>> Beraz, n ateak bada, hartu dute agian Sean, duela pare bat urte n urratsak.
Orain, zure kasua, Alex, ematen, zenbaki horiek ordenatuko
eta non izan dugu, beraz, istorio hau den neurrian mota hau infer dugu
Alex algoritmoa adimendunak iraupena
erdi-erdian, eta ondoren hasten errepikatzea?
[Ikasleak] 3. >> Beraz, 3, gutxi gorabehera, 8 4 bazoaz 2 eta 1 joan.
3 urrats Beraz, edo, oro har, log n berriro.
Edonoiz eta zaren halving eta halving halving eta halving,
log n ideia hori adierazpen bat da.
Eta horrela hartu nahi duzun 3 urrats besterik ez, eta, hain zuzen ere, egin
behin, ateak eta halving halving ireki genuen,
hau hartu dute, berriz, Sean batzuk 7 edo 8 urrats.
Beraz, eskerrik asko aurten gurekin izateagatik. >> Eskerrik asko. Niza bilera duzu.
Eskerrik asko Alex. >> Era berean. [Txalo]
>> Zer da hau benetako inplikazioa?
Orain imajinatu ez duela 8 ateak,, Egia, guztiok zerbait aurkitu
8 ateak atzean nahiko azkar paper pieza tearing eta gure senak.
Baina, zer da milioi ateak bada? Zer da bada 4 milioi ateak?
4 milioi ateak kasuan, benetan ari zaren Alex-en algoritmoa joan nahi du,
bitarra bilaketa deituz gisa hasiko edo zatitzea eta konkistatzeko, oro har,
arazoa halving eta halving mantendu,
4 milioi ateak duzu bada, zenbat aldiz daitekeelako 4 milioi txikitu erditik?
[Ikasleak] 32. >> Benetan da 32. Hau lan egin dezakezu paper zati bat edo zure burua.
4 milioi - 2 milioi 1 milioi bat milioi erdi joan behar duzu, 250 milioi, dot, dot, dot.
Eta ez duzu bada math, 32 hain zuzen ere, lortu zaren joan,
eta hori benetan informatika normalean erlazionatzen dugu 2 eskumenak zenbatu.
2 32 gertatzen 4 milioi dolarrekoa izango da.
Beraz, 2 eskumenak informatikako mota horiek garrantzi handia.
>> Baina, zer da 8 milioi? Zenbat urrats hori hartu daude 8 milioi ateak?
[Ikasleak] 33. >> Beraz, 33. Zer badago 16 milioi ateak? Zenbat urrats hori hartu?
[Ikasleak] 34. >> 34. Mota jarraitu izan dugu, ad nauseam hau. Baina hori gauza bat indartsua da.
Bilioika input gehiago aurkeztu ahal izango duzu zure arazoa, baina, big aurre ez,
hartu besterik ez duzu 1 ziztadak osagarria da, eta, beraz, bilaketa bitarra antzeko zerbait ematen digu
edo zatitzea eta konkistatzeko, oro har.
Baina hemen tranpa mota naiz, ezta?
Alex-en algoritmoa kasuan, Sean abantaila bat izan zuen.
Zenbaki horiek ordenatuko ziren bazekien, baina Alex ez dituzten ordenatzeko bere burua.
Aldez aurretik izan zen sortu egin ziurtatu arbel eta mota
Drew ditut guztiak, ordena horrela antolatu, eta gero horiek estaltzen dut paper.
Baina zenbat lan egin zuen hartzen duten me?
Genuen hasi bada off itxuraz ausazko ordena zenbaki horiek
kasu honetan horiek errazagoa zenbakiak, 8 Hemen bidez 1 -
nola joaten balio horiek ordenatzeko dugu?
Zeregin hori giza zinen bada, zer nolako ikuspegi intuitiboa hartu nahi duzun
zenbaki-sorta oso bat ordenatzeko?
Gauza hauek ezarritako puzzle pieza gisa. Bai.
>> [Ikasleak] zenbaki bakoitzean hartu nahi dut eta alderatu bakoitzak
eta ezkerrera joan. >> Ongi, ona da.
Beraz, zenbaki bakoitza, konparatu bat ondoan,
eta, ondoren, bakarrik zerrendan, joan ahala gauzak rejiggering mota batera mugitzen mantentzeko.
Hortaz, hona hemen, agian batzuk gehiago folks parte hartzeko aukera dugu.
8 boluntario gehiago etortzen maite dugu?
A gutxiago presio pixka Oraindik ez bakarra. 1, 2, 3, 4, 5, 6, 7, 8.
Goazen behera. Zaudete zenbakiak 1 8 bidez.
Ikus dezagun ezin dugu egin Ordenatzeko honetan Alex askoz ere modu berean egin nuen, aldez aurretik.
1, 2, 3, 4.
Anima zaitez eta duzun izanez gero, etapa on line sortu music stand eta ni hemen arteko
pantailan diapositiba gisa eta ordena berdinean.
Uh-oh.
Lan egin dugu, sartu hurrengo adibidez. Oh, itxaron, itxaron. Hemen goaz. Itxaron.
Hurrengo adibide da orain. Hemen duzu joan. Multzoko 8. Goazen sortu.
Guztiak eskubidea. Ordena honen arabera zuei.
Irristatu apur bat musikaren alde stand hemen.
Beraz, 4, 2, 6 dugu - bertan, hemen baino gehiago, bertan 3.
Bai. Ongi da. Baino gehiago duzu hemen. Ez, bertan geratuko duzu.
Bai, bertan. N º oker nago. Eskuin dago. Ados, oso ona da. Ongi da.
Beraz, gaur egun dezagun ordenatzeko ordena handitzeko.
>> Nola egin dezaket hau egiten dut?
Algoritmoa proposatu zen duela une bat izan zen, zergatik ez konparatu besterik ez dugu
folks diren mota bata bestearen ondoan eta, ondoren, konpondu akatsak edozein
ezkerretik eskuinera mugituz.
Beraz, hemen, 4 eta 2 dugu, jakina, ordena. Dezagun swap duzu. Ongi da.
Beraz, lerro behera noa. 4 eta 6, Laguia. [Barreak]
6 eta 8, pretty good. 8 eta 1, utzi duzu swap me guys. Guztiak eskubidea.
8 eta 3 Beraz, swap duzu guys.
8 eta 7, utzi duzu swap me guys. 5 eta 8, bikaina.
Ematen dizut horrela antolatu zerrenda bat.
Guztiak eskubidea. Beraz, ez da nahiko.
Baina hobe da handiagoa zenbakiak delako kasuan puntu 8 -
dute mota bubbled ezker eskuinera.
Beraz, horietako 1 got diot, baina sentitzen atsegin dute hau ez da nahiko arazoa konpontzen.
>> Beraz, zer egingo zenuke hurrengo egiten dugu proposatzen duzu? >> [Ikasleak] Mantendu egiten. >> Egiten jarraitu dugu.
Eta konturatzen, berriz, gauzak dugu gizakietan guztiak izatea
sort adimentsuan antolatu bere burua argazki horretan oinarritzen da,
baina gaur egun askoz ere metodikoa izan behar dugu.
Buruzko algoritmikoak kodea izango bagina bezala ari gara idazten ditugu
kasu honetan, hitzezko pseudocode.
Hargatik saiatu berriro. Hori lan egin nahiko ongi. Ez da konpondu.
Baina zalantzan jartzen denean, saiatu eta saiatu berriro. Hori dela eta, 2 eta 4, ez da laguntza gehiago.
4 eta 6. Ah! 6 eta 1, apur bat hobeto gaur egun.
6 eta 3, ona. 6 eta 7, 7 eta 5, 7 eta 8, ona.
Eta badakizu, ziurrenik ezin dut ignore 8 zerrendaren amaieran zuen delako.
Agian ez dugu hura igaroz norbait kezkatu.
Baina ikus dezagun suposizio bat dela segurua bada.
Orain zerrenda - madarikatua ez ordenatuko. Dezagun saiatu berriro.
Beraz, 2 eta 4, 4 eta 1, 4 eta 3.
4 eta 6, ona da. 6 eta 5, ona da.
6, 7 eta 8, ona da. Baina oharra, ezin gelditu besterik ez dut hemen gelditu eta hemen orain?
[Ikasleak] Bai. >> Bai?
Zer duzu bat izan bada, kopurua 9 han?
Izan ordenatuko da. >> Good. Izana litzateke horrela antolatu lehenengo aldiz inguruan.
Good. Beraz, goazen berriro. Ia ez gara.
1 eta 2, 2 eta 3, 3 eta 4, 4 eta 5, 5 eta 6, 6 eta 7, 7 eta 8.
>> Egin dut, gaur egun, baina, berriro ere, ordenagailu bat besterik ezin da egin, zer egin dut kontatu dut,
eta nire oroitzapena bakarra da, benetan dut lan apur bat egin zuten.
Zerbait aldatu hemen.
Beraz, ez dut teknikoki baieztatu ikusmen edo algorithmically zerrenda hori horrela antolatu da, hain zuzen ere.
Beraz, neurri ona, besterik gabe, honi buruz anal izan, egin dezagun, une honetan 1 gehiago.
Beraz, 1 eta 2, 2 eta 3, 3 eta 4. Eta zer ezagutzen duzu?
Just neurri ona, segimendua egiteko, une honetan, nire eskua dut
zenbat trukeak besterik ez beraz, ezagutzen dut zenbat lan egiten dut benetan egiten dut.
3 eta 4, 4 eta 5, 5 eta 6, 6 eta 7, 7 eta 8. Trukeak No.
Beraz, orain legitimoa nuke lelo hau berriro egin
gabe lan egin nuen Gizatiarrak pass honen bidez ere,
ondoren, argi eta garbi hori berriro gertatuko da horietako bat ere ez da sort ausaz bada
adversarially bere burua mugitzen inguruan. Beraz, gaur egun gelditu ezin dut.
Orain dezagun galdera galdetu, zenbat lan egin zuen hau benetan hartu nahi?
Zenbat urratsak ez hartzeko? >> N karratu.
Bai, eta, beraz, n karratu. Nora egin n karratu lortu duzu?
Num bakoitzean egiaztatu behar duzu
Dago n zenbakiak, eta zenbaki bakoitzaren ikusteko n beste zenbakiak.
Good. >> Beraz, karratu n. >> Good.
>> Beraz, izan bezala oso ondo egon n karratu, eskuinera sentitzen da?
Guys horiek. N, 8, bereziki kasu honetan,
baina denbora Zerrenda honen bidez joan nintzen bakoitzean bigarren aurkako lehen pertsonan nintzen alderatuz,
hirugarren aurka bigarren berriro, eta behin eta berriro,
eta noiz, azkenean lortu dut, zer egin dezaket? Redid dut.
Beraz, oro har, azalpen hau bada, pertsona dugu n
eta, naiz egiten, jakina, 8 urratsak, n urrats algoritmo honen bidez, denbora guztietan.
Baina zenbat aldiz kasurik okerrenean pertsonen zerrenda honen bidez joan egin behar dut?
[Ikasleen] N aldiz. >> Seguruenik n, eskuinera, kasurik okerrenean ere,
zer da, ziur aski, guys horiek kasuan txarrena antolaketa-get joan?
Erabat ari dira bada alderantzikatu
besterik ez delako demagun mentalki, let's - Zein da zure izena? >> Bowen.
Bowen. Ongi da. Horrela, Bowen, une bat besterik ez hona etorri.
>> Demagun Bowen hemen algoritmoa hasieran izan zela,
eta ez dakigu zer Besteek, baina Bowen hemen, algoritmoa honen arabera
eta nirekin ibili nahi izanez gero, burbuila sortu da, lehen aldiz egin zuen inguruan,
amaieran.
Baina demagun ondoan Bowen pertsona kopurua 7 izan zen.
Atzera joan eta 7, eta horrek esan nahi du modu guztiak joan itzuli behar dut hemen daukat.
Orain ibilaldi hori bera izan duen pertsona kopurua 7 daukat.
Baina zer gertatzen da gero, multzoko 6 zion ondoan izan baita?
Ondoren, atzera joan eta 6 lortu behar dut.
Beraz, berriro ere, begizta honen iterazio guztietan n pertsona bakoitzari ari naiz,
eta n egiteko ibilaldi horien ziurtatu dio dut
elementu handiena itzuli eta itzuli eta itzuli zerrendaren bukaeran oso guztiak.
Beraz, gauza n n aldiz n aldiz n edo n karratu da.
>> Hortaz, hona hemen dagoeneko algoritmo bat jada ez n, no longer log n dugu,
benetan ezer egin dugu aurretik baino okerragoa da.
Beraz, Alex mota lortu zortea duten lana itxuraz bere aurrean egin nuen,
garestiak lan guztiak, beraz, bilaketa bitarraren algoritmoa gozatu ahal izan zuen,
n erregistroa da.
Baina hori koherentea da astelehenetik gaia.
Pixka bat eman dugu, leku gehiago, bit gehiago erabili dugu, gure denborak azkartzeko.
Beraz, askoz ere denbora eta espazioaren arteko merkataritza-off bezala,
ditzake merkataritza-offs denbora arteko gauzak joan prest lortzean sort aurrean
eta benetan bilaketa bezalako algoritmo bat exekutatzen ari da. Dezagun saiatu beste bat.
You guys axola ez balu, besterik ez azkar rearranging dator zuei berriro,
utzi saiatu zerbait pixka bat desberdinak non ere ez da oso erraza
bezala konpondu pairwise akatsak, hau da, super intuitiboa.
Dezagun ordez apur bat gehiago nahita eta hau egin.
Da, ziur aski, hau ere proposatuko nuke nahiko intuitiboa.
>> Zerrendako pertsona txikiena hautatu dadila behin eta berriro. Beraz, hemen goaz.
4, txikiena pertsona horrela ikusi dut hain urruti zaude,
beraz, adimen-gogoratu besterik ez duzu orain seinalatu noa.
2. Ooh! Ahaztu multzoko 4. Aurkitu dut zerrenda honetan elementu berriak txikiena.
Mota gogoratu dut. 6, 8.
Ooh! 1. Goodbye. Beraz multzoko 1 gogoratzen dut.
1 txikiena dugu ezagutzen,, baina ordenagailua naiz. Zer badago, 0 bat?
Zer badago -1 bat? Jarraitzeko behar dut.
Beraz, 3, 7, 5, Laguia. Ongi da. Multzoko 1 Beraz, txikiena izan zen.
Duzun me zerrenda - we'll joan Modu honetan
eta jarri arbitrarioki zerrendaren hasieran.
Orain, minutu bat itxaron. Mota cheated dut.
Guys horiek ordezkatzen 8 pertsonek ez da zerrenda, baina array bat bada,
Eta 8 memoria Elkarren ondoko zatiak ez atzera hurrats axola, une bat besterik ez duzu?
Ez, egia esan, ez duzu espazio hemen.
Beraz, nola egin espazio egin dugu - Zein da zure izena? >> Sammy. >> Sammy.
Nola espazio egin dugu Sammy?
>> N me aurretik mugitzen dugu. >> Ados.
Beraz, n duten pertsonen haren aurrean mugitu ahal izan genuen,
baduzu guys nahi 1 nahita, dramatikoa ezkerrera urrats.
Egin ziren denak batera, baina azken aldian kodea idatzi nuen,
ezin duzu ordenatzeko mugitzeko gauza asko aldi berean.
Egin izan dugu begizta batean, denok mugitzen aldi berean behin.
Beraz, baduzu guys ez litzateke axola hurrats eskuinera,
eta Sammy, atzera urratsa bada izan oraindik ez da gela ez dela,
gaur egun egin dezagun hau. Non izan zen Sammy Duela momentu bat? Eskuin dago.
Beraz, hutsune bat dago. Beraz, Sammy bere Leku mugitu ahal izango duzu.
Orain hurrengo pertsona eta, gaur egun, hurrengo pertsona, orain hurrengo pertsona. Orain, Sammy gela ditugu.
Orain, ikusleek norbait ona zen, zuzena zen,
da denbora-kontsumitzen apur bat sentitzen - Zer da azkarragoa? Bai.
[Ikasleak] array berri bat? >> Zer da hori? >> [Ikasleak] array berri bat? >> Ongi, ona da.
>> Beraz, besterik gabe, merkataritza-offs gai honekin koherentea, zergatik ez egin dut array bat berria
eta, ondoren, pertsona horien aurrean espazio Sammy egingo da, igeriketa, adibidez,
eta bakarrik hasi ahal izango dugu array bat beteko guztira. Hau ere lan egiten dute.
Baina ez dut leku gehiago gastatzea gaur egun interesa. Zer da hurbilketa bat da?
[Ikasleak] Swap. >> Ados. 2 guys horiek bakarrik izan dugu trukatu. Zein da zure izena?
Mario. >> Mario. Mario Beraz, gaur egun, hemen duzu.
Sammy, babeskopia une bat besterik ez? Mario izan zen hemen.
Ez dugu zure gela gehiago, beraz, ez bada nahi duzun axola non Sammy joan
Sammy jarri dugu hemen, eta, orain, argudiatzeko Sammy aldaketa eragiketa zela askoz azkarrago nuke.
1 eragiketa egin dugu guys horiek trukatu, edo agian 2 guys horiek trukatu,
baina ez dugu 1, 2, 3, 4, eta, beraz, hori sentitzen hobea. Orain, minutu bat itxaron.
Egin mota I arazoa okerragoa kopurua 4 mota izan zen hasiera-hasieratik hurbil delako.
Orain multzoko 4 Horretarako, apur bat hurbilago, baina ez dakit edo horri buruzko zaintzeko.
Beraz, zorte txarra hori da zenbakia 4 dela apur bat urrunago bere lekua helburu.
Hargatik errepikatu algoritmoa.
>> , Laburpena, betiere, istorioa bezala, guztiek izan zen genuen zerrendan zehar oinez
zenbakidun txikiena pertsona bila.
Beraz, gaur egun egin dezagun berriro. Ez dugu Sammy kezkatu gehiago.
Bakarrik joan ahal izango dugu hemen. Ooh! Multzoko 2. Hori nahiko kopuru txiki bat da.
6, 8, 4, 3, 7, 5. Ongi, ona da.
Eta zorionez, kasualitatez, ez dut mugitu - >> Willie.
Willie zuen bere tokia eskuin delako orain.
Egin dezagun berriro, eta 2 guys horiek alde batetara utzi.
6. Hori nahiko kopuru txiki bat da. Ooh! 8 izango da, zalantzarik gabe handiagoa da.
4. Dezagun 4 ardatz. Ooh! 3 are hobeto.
7 eta 5. Beraz, zer egiten dugu - >> Roger. >> Roger?
Dezagun swap bere multzoko 6.
Beraz, 6 eta 3 trukatu nahi nuke,
dugu mota horretako ahaztuak 6 non egon behar zuen hurbiltzen da zortea,
baina besterik ez da kasualitate hutsa hemen. Hargatik sartu hemen.
8 pretty kopuru txiki bat da. Ooh! 4 txikiagoa da.
6, 7, 5. Zer egiten dugu? >> Swap. >> Zehazki.
Beraz, gaur egun egin dezagun azkarrago sort honetan.
8, 6, 7, 5. Non ez 5? Good. Ongi da.
6, 7, 8. 6 lortzen zuen lo. Zein da zure izena? >> Rosalie.
Rosalie lortzen zuen lo. 7 lortzen - Ikus dezagun. 7, 8. Ongi da.
Beraz, 7 lortzen, bertan lo. Zein da zure izena? >> Amna. >> Amna.
>> Beraz, Amna lortzen, bertan lo egin, eta multzoko 8. Da jada non egin behar zuen izan.
Ongi, ona da. Sentitzen ari garen bezala, geure buruari lana sortzea hemen, baina.
Zer da, azken finean, algoritmo honen iraupena?
Ez 8 gisa, baina n gisa pertsona hauei buruzko uste baduzu? >> N da.
Urratsak n, baina aldi bakoitzean bakarra egiaztatzen ari gara.
Ongi da. N, baina aldi bakoitzean bakarra markatuta ari?
Ados, baina, urrats bat ematen badu n, ez luke izan dut ordenatzeko besterik ez joan 1, 2, 3, 4?
Oh! Ados, diferentzia handi bat da.
Beraz, n karratu zergatik? Zer da benetan gertatzen da?
N zerrenda honetan jendea dago, baina zerrendan pertsona txikiena aurkitu
kasu horretan, txarrena, zenbat urrats hartu behar dut? >> N.
>> N, eskuinera, kasurik okerrenean, multzoko 1. Delako han modu guztiak, hau da,
beraz lortzeko bere joan behar dut.
Eta orduan konturatzen, azkenik, I 1 txikiena zen eta, ondoren, nahiko azkarra da horietako swap.
Baina orain, hasieratik hasteko eta nor bilatzeko behar dut?
Hurrengo txikiena pertsona, hau da, 2. Non kasuan, txarrena 2?
Oh, ene Jainkoa. Hemen modu amaieran da.
Beraz, orain, beste urrats n, n urrats beste egiten dut.
Eta dugu got bada, n pertsona eta kasu horretan, txarrena da pertsona txikiena n urratsak kanpoan,
hori berriro n aldiz-n, eta, beraz, berriro dugu karratu n.
Hau ez da, beraz, eta oso ondo sentitu naiz.
Eta, hain zuzen ere, nahiz eta, kasu horretan, onena demagun off hasten direla ordenatuko
zenbat urrats ez algoritmo hau erabiltzeagatik n pertsona horiek ordenatzeko?
N karratu. >> N entzun nuen karratu. Zergatik karratu n?
Duzu aldi bakoitzean bakarra dela ikusteko. >> Bai.
Eta haien trukatu behar duzu. >> Nahiz eta gizakiak omniscient mota
zentzu begien besterik gabe, hori horrela antolatu mota dugu,
ordenagailu bat ez da smart.
Eta hemen, hemen eta hemen begiratu,
baina zer da bilatzen elementu txikiena bada,
bakarrik ezagutzen duzu zein puntu elementu txikiena aurkitu duzula? Behin Oraindik amaieran.
Baina puntu horretan bakarrik aurkitu dituzun elementu gaur egun txikiena.
Ez duzu nahitaez munduko egoerari buruz beste ezer ezagutzen.
Beraz, behin eta berriro eta berriro joan behar duzu.
>> Une honetan ez dut begiratu muda Beraz, dut, ados, izan ere, egiaztapena 2, txikiena bazaude,
baina ez dakit hori guztira oraindik.
3, 4, 5, 6, 7, 8. Ongi, ona da. 2 izan zen, hain zuzen ere txikiena.
Aurki dezagun hurrengo txikiena. Ongi da.
3, gaur egun Oraindik duzu txikiena. Ikus dezagun. 4, 5, 6, 7, 8. Ongi da, baina zortea berriro.
3 izan zen, hain zuzen ere, leku egokian. Baina hau egiteko berriz, eta behin eta berriro mantentzeko noa.
Nola egin dezaket inoiz beraz apur bat hobea egiten dugu?
Horren ordez pertsona burbuila dutela pairwise txikiena etatik handiena
eta horren ordez, atzera eta aurrera joan ondoren txikiena pertsona hautatzen zerrenda bidez,
zergatik ez sartu ordez pertsona horiek zerrenda urrats berri bat sartu paso?
Dezagun saiatu honekin. Dezagun gauza txertatzeko sort hau deitu me.
Beraz, hemen hemen gaude. Número: 1. Inork zerrenda honetan ez dut axola.
Nire helburua oraintxe multzoko 1 ordenatuko zerrenda baten hasieran jartzen da.
Eta proposatzen dut 8 memoria zatiak besterik ez dut geroztik,
arbitrarioki oraintxe nire zerrenda ustez Unsorted arteko horma naiz,
eta edonork me atzean erreklamatzeko noa ordenatuko da.
Beraz, gaur egun zenbaki 1 behar dugu.
Nire zerrenda ordenatuko sartu zion txertatzeko nahi dut, besterik ez naiz hemen baino gehiago nire hormara mugitzeko, beraz,
eta zerrenda hori horrela antolatu aldarrikatzen dut, zerrenda honetan Unsorted - gutxienez, beraz, urruti ezagutzen dudan bezala.
Zenbaki guztiak ikusi ezin dut aldi berean.
>> Orain multzoko 2 topo gertatuko dut. Zer egin dut berarekin?
Sartu naiz ordenatzen du zerrenda. Baina konturatu nola erraza izan zen.
Besterik ez dut begiratzen. Zenbakia 1 dago. Oh, jakina, 2 multzoko 1. Alde doa.
Orain zer egiten dut 3? Sartu dut ordenatzen du zerrenda. Baina hori super erraza izan zen.
Super erraza, hau da super erraza, erraza super, super erraza, super erraza da.
Eta orain dena da me atzean ordenatuta, eta zenbat urrats ez hartzen?
[Ikasle] N. >> Beraz, soilik n. Zortea lortu dugu.
Bakarrik n zergatik izan da? >> [Ikasleak] zerrenda zen horrela antolatu delako.
Zerrenda dagoeneko ordenatuko da. Beraz, zortea ginen.
Baina algoritmo bat diseinatu dugu denbora hori zorte mota horretako harnesses
kasu horretan onena agertokia, ez alferrikako denborarik galdu.
Beraz, gaur egun zer burbuila-era askotako deitu dugu,
non pertsonek pairwise sortu bubble mota.
Orain aukeraketa sort non pertsona txikiena pluck dugu behin eta berriro.
Eta orain txertatzeko sort dugu non jarri sort-proaktiboan dugu jendea non sartzen dira
gero ordenatuko zerrendan.
Ezin izan bada, hemen guys horiek txalo txanda. [Txalo]
Dezagun gure 5 minutuko break hemen.
Eta itzuli gara, algoritmoak horiek guztiak kolpe egingo dugu ur-out
zerbait hobea. Guztiak eskubidea. Eskerrik asko asko. Oroigarri gisa gorde dezakezu.
Guztiak eskubidea. Itzuli gara.
>> Eta benetako azkar laburpena, 3 ezberdinak izan genuen ikuspegi horien arabera ordenatzeko,
horietatik puntu osoa izan zen puntua lortu non Alex bezalako norbait
zenbakiak azkarrago zerrenda bat bilatu Sean Could bezalako norbait baino.
Eta, besteak beste, nahiz eta 8 zenbakiak adibide simple dugu,
erraz 8 web-orriak, 8 milioi web orrialde estrapolatu ahal izango duzu,
edo Facebook-en 800 milioi lagun.
Beraz, algoritmo horiek, zalantzarik gabe, balio mota horiek eskalatzeko,
eta ideiak dira, azken finean, gauza bera da.
Burbuila lehen Beraz sort non bubbled mota dugu pertsona handiena
eskuineko bidea pertsonek aldaketa pairwise.
Ondoren, aukeraketa sort deitu dugu non apur bat gehiago nahita izan genuen
mantendu zerrendan zehar joan, bilatzen kopurua txikiena hautatuz behin eta berriro, eta berriro,
emaitza logikoa da zerrenda hori azkenean horrela antolatu.
Gero, hirugarren batean, pertsona txertatuko dut leku egokia da,
eta oso contrived adibide bat zerrendan dagoeneko horrela antolatu genuen,
baina hori izan zen mezua bidali txertatzeko sort kasu horretan,
lortzeko zortea dezakezu.
Zenbakiak ordenatuko dira dagoeneko bada, besterik ez da n urratsak askoz ere berretsi du,
aukeraketa sort, berriz, apur bat gehiago tunel ikuspegia Oraindik
eta ez duzu inoiz konturatzen zerrenda ordenatuko dagoeneko.
Beraz, ikus dezagun burbuila ekintza sort hemen.
Ondorengo adibidez, barra bertikalak ikusteko gaude
horren altuera adierazten da, beraz, ikusteko gertatuko ordenatzeko ordenatzeko dezakegu.
Txikiagoa bar, zenbaki txikiagoa; handiagoa barra, kopurua handiagoa.
>> Eta jolastu dugu default abiadura honetan.
Orain little azkar mugitu da, baina gorria da zer 2 taberna erakusten
ari aldean alboan.
Eta ikusten duzu lotura estua bada, zer gertatzen da, tabernak dira ordena,
txikiago bat lortzen ezkerrera mugitu, eskuinera bat handiagoa,
eta, ondoren, aurrera mantentzeko.
Beraz, egiten dugu behin eta berriro, konturatu taberna txikiena
beraien bidean ezkerrera inching mantentzeko
eta taberna handiena beraien bidean eskuinera inching mantentzeko.
Eta, hain zuzen ere, eredu bat ikusten ari gara eskuinaldean modu hasita
8 bezala ikusi dugu, eta, ondoren, 7 azkenean bubbling gure zerrendan giza amaiera urrun.
Beraz, hau da, oso azkar pixka bat lapurtera, eta, beraz, utzi hau gelditzeko une batez.
Dezagun abiadura aldatzeko me askoz azkarrago.
Ez dut algoritmoa aldatu, besterik ez dut animazioa gertatuko azkarrago egiteko.
Oraindik burbuila sort, algoritmoa bera,
baina gaur egun askoz ere azkarrago ikusi ahal izango duzu gure manifestazio hitzezko baino
handiena duten elementuak dira, hain zuzen ere goiko bubbling.
>> Bat alde batera utzita, beheko ezkerreko laukiak txiki eta eskubide horiek beheko
besterik ez dira zenbat konparazioak egiten ari zaren gogorarazleak txiki.
Baina orain, piramide forma duen hartu ahal izango dugu pilatzen dira, eta ez da doan.
Ezkerreko, eskuineko handiena, eta beste guztia artean elementu txikiena da.
Orain dezagun ordez aukeraketa sort begirada bat hartu.
Aurretik joan eta Stop sakatu dut. Taberna ausazko multzoa iritsi gara.
Aukeraketa ordenatu, abisuaren, zerrendan zehar doa berriro, eta behin eta berriro,
plucking elementu txikiena. Hortaz, hona hemen aukeraketa sort da.
Itxura ez du bere lana gutxiago gaur egun gertatzen ari den bezala da, ez delako ari gara pairwise alderatuz
baina ari gara gerezi eskubidea elementuak txikiena aukeratzea ezkerrera ordenatzeko.
Oso denbora gutxi izan zen, eta, beraz, beraz, ez dikotomia bat da dagoeneko.
Just delako algoritmo bat da, esan zuen, eta, denbora n karratu hartu, burbuila ordenatu bezala
eta aukeraketa sort bezala, horiek dira benetan txarrena kasuan aldiz exekutatzen ari da.
Esate baterako, kasuan, demagun, hautaketa ordena
Actually I am pertsona txikiena hautatu eta bere jarriz hemen,
ondoren, berriro egiten ari naiz, gero dut egiten ari da berriro,
baina apur bat egin izan dut optimizazioa.
>> 1 hemen bezain laster joan zen bizitzera I - Sammy kasu horretan
zer egin berarekin hortik aurrera egin behar dut? >> [Ikasleak] Utzi zion.
Utzi, ezta? Ezer ez.
Ez dut inoiz hitz Sammy berriro hautatu badituzu elementu txikiena izan dudalako
eta hemen jarri zion, zergatik hondakinak denbora nire zerrenda osoa amaieran?
Hurrengo iterazio On benetan mugitu me multzoko 2 bakarrik, bakarrik multzoko 3.
Beraz, errealitatean, ez nintzen gauza n n aldiz egiten.
1 gauzak, eta n - 2 gauzak, gero n - 3 gauza n gauzak, eta ondoren n egiten zen I
ondoren, n - 4, dot, dot, dot.
Serie geometriko bat apur bat, besterik gabe, esan nahi ditugu
gehitzen ari zaren pixkanaka txikiagoa zenbakiak.
N + n + n + n, baina n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Eta zer esan, oro har, lanak izan
Nahastea dut nire taula gora hemen une bat besterik ez -
/ 2 - den lan n antzeko zerbait (1 n)
besterik ez badugu begirada mota math book non Cheat orriak guztiak dituzula atzeko aldean
formulak.
Ari zaren besterik ez bada zerbait gehituz n + n - 1 + n - 2, berau hau atsegin zerbait izan behar duela.
Eta gara mota biderkatu hau bada, hori karratu ken n / 2 n.
N esaten karratu, nahiz eta mantendu dut, eta hori nintzen mota mental lasterbide bat hartu duelako
errealitatean, n delako karratu minus n 2 arabera banatzen da, hain zuzen ere, urrats kopuru benetako
aukeraketa sort bezala algoritmoa benetan zenbatuko dugu bada hartuko luke
konparazioak horiek guztiak eta lanpetuta little lana egiten ari gara guztiak.
Baina, Egia, behin n lortzen milioi bat edo milioi demontre zaintzen duten bezala
ari zaren bat milioi karratu minus milioi 2 banatuta egiten bada?
A milioi zenbaki karratu handi bat da.
Beste milioi off hartu ahal izango duzu - n. Aurre handi bat, hala nola, ez da.
Beraz, zenbakiak handiagoa lortzeko, hain garrantzitsua ordenatuan termino horiek txikiagoak dira.
Nork zaintzen 2 zatitzen bada ari zaren urrats zenbakiak quadrillions buruz hitz egiten badugu?
>> Beraz, oro har, ordenagailu zientzialari ohi gola botatzen guztia, baina epe handiena,
eta errazteko besterik ez mota dugu munduaren eta esan algoritmoa,
hartu zuen gutxi gorabehera n karratu urratsak. Algoritmo bat exekutatzen ari da.
Beraz, itzuli dugu une bat besterik ez da hau hormigoizko adibide batzuekin,
baina orain, intuitiboa motibazioa sort gure mundua sinplifikatuz atzean
eta fancy formula horiek guztiak sartzeko beharrean baldintza garrantzitsuena buruz hitz egiten.
Beraz, aukeraketa sort zen, eta pixka bat zortea genuen han.
Dezagun txertatzeko sort begiratu. Dezagun aurrera eta hau hasteko baita.
Orain konturatu ereduarekin gertatzen apur bat desberdina da,
eta zenbakiak ausazko hasi dugu,
baina benetan zenbatzen badituzu urratsen kopurua txarrena kasuan,
zerrenda hasi zen erabat ordena egokian,
n bakarrik nahi dugu urrats askoz ere konturatzen.
>> Baina zerrenda ziren benetan bada atzeraka - Adibidez, hemen kasu honetan -
ondoren nabarituko kasu honetan lan asko egin behar izan dugu.
Eta mota egin behar litzateke hau sentitzen gogorragoa lan mota
elementu horiek txikiak ezkerreko, eta hori lortu dugu unlucky delako.
Zerrenda gabe alderantzizko antolatuko zen.
Por el contrario, txertatzeko sort imitatzen dugu zer egin dugu gure gizakietan bada hemen
denek horrela antolatu hasi eta ondoren hasi, algoritmo nahiko ona da, ezta?
Dagoeneko, izan ere, ordenatuko da.
Beraz, utzi gauza horiek zehatz-mehatz zenbat denbora hartu dira gurekin laburbiltzen saiatuko en
jargon apur bat besterik ez edo notazio askoz errazagoa da benetan sartu
sort-fanciness baino iradokitzen du.
Gauza hau hemen, big O pantailan, ordenagailu zientzialari bat izango da, oro har, erabili
kasurik okerrenean algoritmo bat deskribatzeko.
>> Berriz ere, kasu txarrenean, guztiz testuinguruaren mendeko da.
Zer esan nahi dugu kasu txarrena erabat desberdina izango da arazo buruz hitz egiten ari gara oinarritzen da.
Baina Ordenatzeko kasuan, txarrena ahalik eta eszenatoki zer?
Dena da atzeraka delako eta bakarrik sentitzen duten bezala, lan asko esan nahi du Gurekin.
Jotted dut Nik horrela ikusten dugu orain arte algoritmoak batzuk:
lineal bilaketa, bilaketa bitarra telefono-book edo paper zatiak bezala,
gero burbuila ordenatu, aukeraketa, ordenatu, eta txertatzeko sort bezala, ikusi dugu gure gizakietan
eta, ondoren, 1 bestelako den azkenean deitu batu sort.
Beraz, kasurik okerrenean bilaketa lineala, zenbat urrats ditu kopurua 7 aurkituko hartu
ate n dira Sean aurrean bezala bada? >> [Ikasleen] N.
N. Beraz, big n O idatzi dugu.
Hutsuneak batzuk bete besterik ez dut egingo. Hutsuneak sareta bat besterik ez da.
Baina bilaketa lineal kasuan onena, 7 zerrendaren Irteeran agian izan da,
eta Sean hasi liteke zerrendaren hasiera begira.
Beraz, bada bilaketa lineala erabiltzen ari zarela eta ezkerretik eskuinera, edo agian eskuinetik ezkerrera egiaztapena
baliokideak dira kasu horretan onena zenbat urrats gerta daiteke lineala bilaketa
Sean-en algoritmoa bezala, hartu nahi duzu? Just 1 urratsa.
>> Beraz, omega idazkera esan nahi dut.
Kapital omega hau besterik ez da.
Omega besterik ez da onena kasu iraupena esaten modu sexy.
Beraz, kasu horretan, onena ari da denbora urrats bakar bat edo konstante zenbakiaren urrats
1 Kasu honetan, baina kasu horretan, txarrena, big O, benetan da n urratsak.
Eta hau hemen, theta, benetan ari gara ez begiratzen oraintxe.
Ez da adibide hau, bereziki garrantzitsua da.
Baina orain dezagun saiatu bitar bilaketa.
In, bilaketa bitarra kasuan txarrenean, zenbat urrats kopurua 7 aurkituko hartu du
edo dena delakoa bilatzen ari gara? >> [Ikasleen] Log n.
Oraindik log-n bezala Alex got delako unlucky
arazoa bidez benetan dugu lan metodikoki
eta ez zuen aurkitu azken begiratu zuen atea arte, 7 zenbakia
nahiz eta, zuzentasuna, kanpoan bota ateak zenbait bidean lortu zuen,
binary log n kasurik okerrenean bilaketa iraupena du.
Eta berriro ere, hau zatituz eta konkistatu hitz egiten du.
Baina zer gertatzen da kasu onena?
Eta Alex benetan bizitako Kasu horretan, onena izan zen zuen agertokian.
Zenbat urrats bilaketa bitarra ez hartu? >> [Ikasleak] 1.
1, bakarrik lortu zuen zortea delako.
Baina hori da onena kasu eszenatoki fina omega aipatzen delako,
kasu input onena, nahiz eta muda ausazko zorte besterik ez da.
>> Orain, hau ere baja hutsik mota ari gara orain.
How about burbuila sort?
Burbuila sort kasu txarrenean, denok alderantzizko ordenan da,
beraz bubbling asko egin behar dugu.
Baina zenbat urrats da txarrena kasuan hartu? >> [Ikasleen] N karratu.
Hau izan zen n karratuko, uste duzulako,
zerrenda erabat atzeraka - 8 da hemen, 1 da hemen.
gauza burbuila hasteko Horrela, modu honetan, 8 zenbakia eraman behar du,
kasurik okerrenean kopurua 7 Horrela, modu honetan, baina non da?
Hemen jarraitzen zuen han. Beraz, behin eta berriro egin behar izan dugu.
Eta hori da, non n urratsak, eta, ondoren, n - 1 urratsak eta, ondoren, n - 2 urrats.
Eta nire hitza hartu duzu bada - mota duzu biderkatzen bada,
gutxi gorabehera n amaieran egingo dugun oraintxe ignore beste termino batzuk karratu
ondoren, txarrena kasuan burbuila sailkatu n karratu da, eman edo hartu.
Baina burbuila sort kasua onena buruz zer?
Zer da kasu onena agertokia? Zenbakiak guztiak antolatuko dira dagoeneko.
Eta zer heuristiko erabiltzen dut, trikimailu erabiltzen dut,
izan dut egindako lana ez, eta, beraz, ezin izan dute gelditu goiz konturatzen?
[Ikasleak] Begiratu behin. >> Begiratu behin. Baina zer zen egiten dut bidean?
Pista nintzen mantenduz zenbat trukeak egin nuen.
Zenbatzen ez badut, trukeak edozein, nire behatzak, eta gero egin dut lana ez konturatu nintzen.
Behar du, zalantzarik gabe, ez dut saiatu lanak ez dira berriro egin, eta, beraz, besterik gabe gelditu ahal izango dut.
>> Beraz, burbuila-sort kasuan onena zerrendan dagoeneko ordenatuta,
zer, omega idazkera esan duzu, kasuan onena iraupena?
Just n. Lan egin behar dugu, baina besterik ez dugu 1 ibilaldi lana merezi.
Eta hemen ere, zati hau hutsik utzi behar dut.
Eta orain, aukeraketa sort.
Aukeraketa sort izan plucking pertsona txikiena me behin eta berriro.
Eta zer egin izan zen denbora exekutatzen ari dela esan genezake?
Hori izan zen n kasurik okerrenean karratu.
Eta, zoritxarrez, kasu horretan onena Honez gain n karratu
mundu osoan ikuspegi omniscient sort izan ez dudalako;
Osoa iterazio gainean besterik ez dut ezagutzen ditudan pertsona txikiena, hain zuzen ere aurkitu.
Aukeraketa sort mota zentzu horretan sucks
baina hankaz intuitiboa mota da.
Nahiko erraza da kodea da egin behar duzun guztia idatzi loops for habiaratua pare bat delako,
normalean, txikiena elementu bila pasatzen
eta, ondoren, non pertenece zerrendaren amaieran elementu txikiena jartzen.
Beraz, hemen ere ez da merkataritza-off bat izango da.
Zenbat denbora uste eta benetan zerbait garatzeko kodea idatziz hartzen du
oso ondo hartu nahi duzun algoritmoa hobea eta azkarragoa performance bat izanez gero denbora gehiago.
>> Baina besterik ez duzula mota kodea zerbait sortu bada, azkar eta zikin
eta, besterik gabe mota ideia stupidest posible uste dezakezu,
iraun dezake minutu batzuk kodea, baina datuak multzo handi
zure algoritmoa ordu iraun dezake exekutatu.
Eta are eskola graduondoko batzuetan horiek merkataritza-offs.
3am litzateke, batzuk oso handiak datuak multzoa aztertzen saiatzen ari zen I
segurtasun ikerketa egiten ari nintzen, eta bai zen, 5 minutu igaro
tweaking nire programa datuak aztertu eta joan lo egin
edo pasatzeko 8 ordu lortzean egokia berehala exekutatzen da, beraz, eta ez joan, lo egin.
Eta, beraz, han ere kontziente erabakia mota da.
Garapen-denbora gutxiago, gehiago lo.
Atzera begirako, ziurrenik ez dut bultzatu dela
helburua hemen kalitatea optimizatzeko kodea,
baina mundu errealean oso moduzko merkataritza-off da.
Denbora gutxiago, errendimendu gutxiago, edo alderantziz.
Hortaz, hona hemen, azkenik, lortu dugu theta buruz hitz egiteko aukera.
Theta idazkera ordenagailuan zientzialari ekarri elkarrizketetan zerbait da
big O eta omega gertatuko berdinak izatea.
Theta benetan bidali mezu hori estu loturik mota da esaten duzu.
Ez dio axola, egoera ona edo txarra den ala ez, eta karratu n.
Beraz, ez da garrantzitsua hemen ipuin hauek.
Insertion sort (a) ren begiratu dugu, hau da,
non nintzen guztiontzat leku egokian txertatzen.
Kasu honetan onena txertatzeko sort iraupena izan zen ikusi dugu hemen?
[Ikasleak] kasua? >> Kasua.
>> N kasuan, onena izan zen guztiontzat horrela antolatu delako,
eta Sammy eta ez beste inor benetan guztiak eraman behar izan zuen.
Dagoeneko ziren leku eskuineko.
Beraz txertatzeko onena kasu sort da, kasu honetan, n.
Baina kasu horretan, txarrena karratu n mota da. Zergatik?
Gizakien zerrendan alderantzizko ordenan bada,
8 zenbakia dut eta berarekin sartu dut, edo bere posizioa eskubidea, hau da, hemen.
Mota alde mugitzen dut. Guys hauek Unsorted zuen, edo horrela antolatu du.
Baina orain, nor hurrengo gertatuko I? >> [Ikasleak] 7.
Kasu horretan, txarrena 7 alderantzizko ordenan delako.
>> Beraz, hemen da, 7. Non ez 7 sartzen zara? Definitely me atzean.
Baina, orain 7 benetan pertenece ez berehala me atzean, baina multzoko 8 atzean,
izan dut, beraz, esan "me Barkatu, multzoko 8, mugitzeko modu hau mesedez
"7 gela egiteko?" Orain 6 topo.
"Oh, libratuko me, 8 eta 7, 6 gela egiteko mugitu duzu?"
Beraz, beste era batera esanda, txertatzeko sort, nahiz eta ez dut askoz mugimendu egiten,
me atzean pertsona asko lan gehiago egiten ari dira, eta hori lortu norbait denbora kostatuko.
Ordenagailua denbora kostatuko da.
Beraz, txertatzeko sort kasuan jasaten jarraitzen dugu.
Urratsen kopuru osoa gehitzen bada, amaituko dugu, gutxi gorabehera n karratu sakatuz
guys horiek gela egin behar, giza delako txertatuko dira zerrenda horretan itzuli.
Eta horrela, kasu honetan theta besterik ez da esku istorioa jakin ez dagokio.
Hori da polita eta ona. Iraupena buruz hitz egiten 3 modu ezberdinetan hauek ditugu.
Baina zer du termino errealetan, benetan esan nahi benetan saiatu egin behar dugu gero algoritmo bat sortu kodea?
>> Utzidazu proposatu ez daude algoritmoa are hobeto
bera, zenbait merkataritza-offs.
Sort batzeko deia ari gara, eta hau magikoa algoritmoa sort da
bakarrik lan egiten azkarrago nolabait, eta beraz, erraza da, gutxienez pseudocode adierazteko.
Algoritmoa merge sort hau ezartzeko, honela izango da.
Duzunean n elementu - n zenbakiak, n pertsona, edozein delarik ere lehen behatu txeke bat eman.
N 2 baino gutxiago bada, batu sort besterik ez gelditzen da. Itzultzen da, nolabait esateko.
Zergatik n 2 baino gutxiago bada geldiarazten ez dituzun? >> [Inaudible ikaslearen erantzuna]
Eskuin. Eta berriro ere, n da, ez dago zerrendan, n zerrendaren tamaina da.
N 2 baino gutxiago bada, horrek esan nahi du zure zerrenda bai 1,
non zauden, jakina, horrela antolatu da zenbaki 1 bada,
edo 0, eta kasu horretan ez dago ezer ordenatzeko,
base kasuan sort behar dugu.
Zerrenda laburra da, beraz, ez dagoela ezer egin bada, literalki, ez ezer. Joan-etorrikoa.
Bestela, ordenatzeko elementuak ezkerreko erdia eta, ondoren, ordenatzeko elementuak eskuineko erdia,
ondoren batu ordenatuko halves 2.
>> Mota hau apur bat Cheat dirudienez, horren bidez galdetzen dut nola elementu ordenatzeko
eta ni ari zaren kontatzea, "Ordenatu ezkerreko erdialdean, eskuineko erdia ordenatzeko."
Bezala, nago "eskubidea guztiak. Nola ezkerreko erdian ordenatzeko?"
"Ordenatu ezker ezkerreko erdia erdia, ezkerreko erdia erdia ordenatzeko, eta, ondoren, egin".
Ziklikoki zer ordenatzeko esan nahi du definitzeko mota zara,
baina bihurtzen da, kasu honetan, benetan zoragarria.
Ez da benetan gurpil ziklo hau ez da inoiz bukatzen
noiz amaituko ez delako? >> [Ikasleak] 1 gauza iristen denean.
1 gauza iritsiko duzu.
Beraz, nahiz eta 8 pertsona has dezakezu eta esaten dut, "Ordenatu pertsona horien erdia ezkerreko
4 pertsona horiek, "gero esango dizut," Nola ezkerreko erdian ordenatzeko duzu? "
"Beno, ordenatzeko 2 pertsonek hemen." Eta gero, hala nola "guztiak, eskuineko fina".
"Nola ezkerreko pertsona horien erdia ordenatzeko duzu?"
"Just ordenatzeko 1 pertsonek hau hemen." Zein liluragarria errebelazio orain?
1 pertsonek ordenatzeko behar dut. Eginda. Nik ez dut edozein lan egiteko.
Baina orain, pertsona hau ordenatzeko behar dut, baina pertsona bakar bat, ez da ezer egin behar dira.
>> Beraz, magia, itxuraz, hirugarren urrats honetan: ordenatuko halves batzea.
Beraz batu sort liluragarria ezagutzeko honek arazo handi bat apurtzen bada behera
2, txikiagoa berdinean tamainako arazoak sartu
eta, ondoren, kola mota irtenbide txikiak eta amaieran,
Asko dugu, askoz hobeto [hariztaketa soinua proposatzen dut]
aukeraketa sort edo txertatzeko sort edozein baino.
Benetan Nik ordu erdi ez ikusi egingo zaio, baina benetan ez dakit zer ari den gertatzen
gaur egun kanpo. [Whirring soinu] [barreak]
Beraz, ikus dezagun hau ikus daiteke gure lagun Rob Bowden pixka laguntza.
2 merge sort prozesuan urrats handiak daude.
Lehenik eta behin, etengabe zatitu cups zerrenda halves sartu
horietan kopa 1 besterik ez dugu zerrendak sorta bat arte.
Ez kezkatu zerrenda batean bakoitiak zenbaki bat badu
eta ezin duzu haien arteko ebaki primeran garbi bat egiteko.
Just arbitrarioki hautatzeko zerrenda extra kopa sartu, besteak beste
Beraz, dezagun zatitu, zerrenda horiek.
Orain 2 zerrendak dugu.
Orain 4 zerrendak dugu.
Orain 8 zerrendak zerrenda bakoitzean kopa bakar bat dugu.
Beraz, urrats 1.
Urratsa 2 bikoteka behin eta berriz batu ditugu zerrendak merge aurretik ikasi dugu algoritmoa erabiliz.
108 eta 15 biltzen amaituko dugu zerrendan 15, 108.
50 eta 4 biltzen amaituko dugu, 4, 50.
8 eta 42 biltzen amaituko dugu, 8, 42.
Eta 23 eta 16 batuz sortu amaituko dugu 16, 23.
Orain gure zerrendak tamaina 2.
Iragarki 4 zerrendak bakoitza ordenatuko
beraz, zerrendak bikoteak batuz berriro hasi ahal izango dugu.
15 eta 108 eta 4 eta 50 batzen 4 lehen hartu dugu, gero, 15,
ondoren, 50 eta, ondoren, 108.
8, 42 eta 16, 23 biltzen lehen hartu dugu 8, ondoren, 16,
ondoren, 23 eta, ondoren, 42.
Beraz, orain 2 tamaina 4 zerrendak besterik ez ditugu, eta bakoitzak bere ordenatuko da.
Beraz, gaur egun, 2, zerrenda horiek batu ditugu.
Lehenik eta behin, 4 hartuko dugu eta, ondoren, 8 hartuko dugu eta, ondoren, 15 hartuko dugu
eta 16 eta 23 eta 42 eta 50 eta 108.
Eta Bukatutakoan dugu. Zerrenda ordenatuko dugu.
>> Rob aprobetxatuz mota zerbait ez dugu oraindik egin zen.
It iradoki zen, baina ez du ezer egiten.
Zerbait zen egiten fisikoki cups iradokitzen
baliabide batzuk zuen gastua gain. >> [Ikasleak] Space. >> Espazioa izan da.
Izan ere, zuela bi-maila taula non sort hau espazio zuen hemen
eta hemen behera espazioa zen benetan, esan zuen bi aldiz ere espazio erabiliz ulertuta
txertatzeko ordenatu, burbuila ordenatu, edo hautapena sort gure algoritmoak edozein beraz, orain arte bezala
baina osagarriak espazioa aprobetxatuz zuen atzera eta aurrera mugitzen gauza mota
mantenduz gauza ordena.
Eta nahiz eta horrela antolatu zerrenda bat lortu dugu bezala sentitzen du, sentitu zuen, berriz, bat bezala.
Egia esan, zer Rob zen egiten ari zen, hain zuzen ere algoritmo hau.
Lehen aldiz hartu zuen tamaina n arazoa, banatu erdi ezkerreko eta eskuineko erdia.
Cups mugitu zuen. Ondoren, prozesu hori errepikatu zuen.
4 2 2 multzo banatu zituen hemen eta gehiagoko hemen baino gehiago.
Ondoren, prozesu hori errepikatu zuen eta 2 banatzen da 2 1 multzo horiek hainbat cups bakoitzean.
Eta hori da, non, aukera bikaina sortzen.
Istorioa puntu hartan, Rob izan 8 1. Tamaina zerrendak,
horietatik dagoeneko horrela antolatu ziren.
>> Orduan zer egin, aurrera jarraitu zuen?
Pairwise hau horrela antolatu zerrenda eta ordenatuko zerrenda hau hartu zuen, eta horiek batu.
Ondoren, hau hartu zuen, eta horiek batu, eta gero hau, eta hauek batu
ondoren, hau bat eta batu ditu.
Eta gero, zer egin hurrengo egin zuen?
Ondoren, berriro fusionatuko handiagoa zerrendak eta, ondoren, handiagoak zerrendak berriro fusionatuko.
Eta honi buruz uste baduzu besterik ez oraingoz intuitiboki, zer zen egiten benetan?
Arazoa zen zatituz erdia, erdiak, erdiak, erdia
super txiki horiek zerrendak lortzeko.
Ondoren, bikoitza, double, bikoitza, bikoitza konbinatuz mota izan zen.
Beraz, bi aldiz izan zen lana askoz gisa egiten dut ikusi dugun bezala, beraz, orain arte
ezer arrail eta konkistatzeko, baina big aurre ez duten.
Birritan ere ez da big aurre. Etengabeko faktore bat besterik ez da.
Eta askoz ere gure adierazpen aritmetikoa aurretik bezala, besterik ez dut faktore konstante zeharkatuko du
aldiz 2 atsegin dute. Nork zaintzen? 2 bilioika bada 2 aldiz, oraindik urrats asko.
Beraz, urrats hau batuz gako insight izango dela dirudi.
Dezagun honen bidez ibiltzea besterik ez zenbakiaren aurretik - Oh, hori ez da jarraitu behar oraindik.
Dezagun hau zenbakiaren, besterik gabe, benetan ikusteko nola jokatzen du izarrekin ibiltzeko.
Hau da, batez ere apur bat pobrea gizon animazioa.
Dezagun proposatzen hau.
Merge sort denbora - honi buruz hitz egiteko modu bat besterik ez dugu behar.
Hau ez da matematika, hau da, geure burua adierazteko modu succinct mota.
Beraz, T adierazten du denbora eta n zer adierazten du? >> [Ikasleak] tamaina
>> [Malan] arazoaren tamaina, pertsonen kopurua.
Beraz, n pertsona ordenatzeko denbora exekutatzen ari dela, 0 denbora zenbatekoa izango naiz erreklamatzeko
n 2 baino gutxiago bada, 1 kopa edo cups ez bada, ez da ezer ordenatzeko delako duzu.
Baina, oro har, denborak aurrera egin du n elementuak ordenatzeko proposatzen dut
ezkerreko erdia ordenatzeko hartzen du plus eskuineko erdia izango da
plus - zer gehigarri hau + n? >> [Ikasleak] Batu sort.
[Malan] actually da, batuz bada n / 2 elementu duzulako hemen
eta n / 2 elementu Hemen duzu, zenbat denbora du batu behar da?
Just Rob bezala, hau pluck hemen duzu, agian pluck hemen,
pluck baino gehiago hemen, pluck baino gehiago hemen, pluck baino gehiago hemen.
Cups, bakoitza ukitu behin duzu.
Eta ez da 4 cups gehi 4 cups bada, 8 cups
edo, oro har, 8 cups n.
Beraz batuz urratsa n gaitezke adierazteko,
eta hori, literalki, zenbat aldiz Rob fisikoki ukitu dakar
Styrofoam cups horietako bat.
Hargatik egin arbitrarioak adibide bat.
16 cups bada, zer ordenatzeko iraupena, Rob bildu, 16 cups erabiliz?
2 aldiz denbora zenbatekoa 8 cups hartzen ordenatzeko
8 cups dugulako hemen, 8 cups hemen.
Ez dakit zenbat denbora hartzen du, beraz, generalizing T gisa ari gara oraingoz.
Nork daki zer da?
Baina orain ordenatzeko errekurtsiboki edo galdera bera behin eta berriz eskatu ahal izango dut.
Zenbat denbora du 8 cups ordenatzeko hartu?
8 cups esan nahi dut, 4 cups gehi 4 cups ordenatzeko hartzen du zenbat denbora hartzen du,
gero batuz elkarrekin.
Ederren. Ziklo batean lortzean ari gara dagoeneko. Nola irauten du 4 cups ordenatzeko hartu?
4 cups ordenatzeko hartzen du 2 cups plus 2 cups, ordenatzeko plus batuz prozesua da.
Ederren. Nola irauten du 2 cups ordenatzeko hartu?
2 cups 1 kopa ordenatzeko zenbat denbora hartzen du gehi kopa beste ordenatzeko hartzen du
plus zenbat denbora batzea hartzen du, besterik ez 2.
>> Ederren. Azken galdera. Nola irauten du 1 kopa ordenatzeko hartu?
Hona hemen oinarri kasuan iragarri dugun hit lehenago genuke.
Izan ere, egiten duen lana inolako arazo txikiena ordenatzeko
esan nahi du, gaur egun, eskola kalifikazioa estilo ordenatu,
bakarrik joan ahal izango dugu zenbaki horiek plugging back sartu
Orain badakigu zer da 1 T, eta, beraz, T 0 1 konektatu ahal izango dut.
Horrek erantzuna emango me 2 T, ondoren I goragotik konektatu.
Hori me emango, 4 T, goragotik I entxufatu.
Hori me emango 8 T, goragotik konektatu ahal izango dut.
Eta egia esan, ez dut bada math hori, erantzun horiek plugging,
Lortu ondoren, 16-T ez da 64.
Eta zer 64 ordezkatzen du?
T 16 bada, bai, 16 aldiz 4.
Beraz, orain dela gauza honen iraupena izeneko batu sort aldarrikatzen dut
eta hori ikusi dugu, beraz, oso urrun direnak fanciest izango
deritzo egingo n log n
zenbat aldiz zatitu erdia cups sorta oso bat Rob daitekeelako? Saioa hasi n.
Telefono book Adibidez gisa berean da, auto-Manacorense adibide gisa bera da.
>> Zenbat aldiz erdia zerbait zatitzea duzu?
Hala eta guztiz ere, ez dago batuz urratsa da hau.
Cups zatitzeko erdia behin eta berriro eta berriro, baliteke
baina, aldi bakoitzean bazoazela batu dute.
Eta lehenago esan genuen n cups batuz hartzen n urratsak
kopa bat pluck delako, pluck kopa bat, eta behin kopa behin ukitu behar duzu,
Rob bezala besterik ez zuten.
Beraz, bada zerbait log n aldiz egiten ari gara eta n gauzak egiten ari gara, iterazio horietako bakoitzean,
halvings horietako bakoitzean, n aldiz log n dugu.
Beraz, bada entxufatu 16 Adibide honetan, 16 aldiz saioa 16 -
ez kezkatu zergatik orain gertatzen da oinarria marrazten dut ez delako
baina log base 2 16 4, 16 aldiz 4 da 64.
Baina, aitzitik, genuen erabiltzen bada burbuila sort edo hautapena sort edo txertatzeko sort 16 zenbakiak,
zer egingo zenuke exekutatzen ari den denbora izan dira n 16 bada?
16 karratu izango litzateke, hau da, 256, nahiz eta ondoren ez duzu nahiko math guztiak
256 64 baino handiagoa da. Hori da benetan magikoa takeaway hemen.
Eta honen bidez konturatzen adibide txikiagoa baita pset batean lan
egiten du guztiak askoz intuitiboagoa.
Baina, zer da benetan algoritmoa hau sentitzen dagokionez esan nahi du:
Benetan merge sort hemen nahi baduzu, begiratu dezagun tira me up Hemen leiho hau
Horren bidez, algoritmoak horiek guztiak 3 dugu apur bat desberdina adibide da
burbuila, aukeraketa, eta batu besterik aldamenean.
>> Tabernak ausazko hasi dute, eta hori ona da.
Inor ez da beste funtsezko abantaila bat dauka.
Dut une batean joan egin klik animazioak horietako bakoitzean - Hasi, Hasi, hasiera
azkar ahal ditut, beraz, gutxi gorabehera, aldi berean Irteeran,
eta dezagun kontuan hartu burbuila sort okerragoa kasuan denbora exekutatzen ari dela? >> [Ikasleen] N karratu.
N karratu. Sort-en hautapena txarrena kasuan denbora lasterketak? N karratu.
Eta merge sort itxuraz, nahiz eta zuk ez duzu nahiko math guztiak jarraitu orain
bihurtu da askoz ere intuitiboagoa denboran zehar egingo da, aldarrikatzen dugu, n aldiz log-n.
Eta log n delako zorrozki baino gutxiago n behin big zenbakiak ditugu,
n aldiz log n n aldiz baino txikiagoa n edo n karratu.
Beraz, zer du benetan iraupena termino algoritmoa hobeto sentitzen da,
n aldiz log n n karratu aurrean? Hemen goaz. Egin klik, egin klik egin klik.
>> Horixe merge sort antzeko zerbait esan nahi du.
Une bat daukagu. Dezagun zer gertatzen den ikusteko hemen.
[Chuckles] Whose burbuila sort dirua?
Sarrera batzuetan beharrean araberakoa da.
Ikus dezagun.
Goazen. Zituen bezala harrapatzeko sentitzen da. >> [Ikasleak] joan, burbuila ordena!
[Ikasle murmuring]
[Malan] Bai, bai.
[Ikasle murmuring] joan, joan, joan!
[Txaloak] [guztiak kontsolatzeko]
Beraz, gaur egun 1, azken final demo, bada pixka bat delikatua your mind itzulbiratu math inguruan
edo sort han ikus, benetan dezakezu abiadura entzun
algoritmo beste modu ezberdina du.
Hau da benetan egin duten bazkide soinuak animazio norbait
aldaketa prozesua eta tabernak altuera.
Hemen ikusten dugun bezala dugu, ez da gutxi Ordenatzeko algoritmoak daude folks duten pentsatu.
Lehena hori txertatzeko sort izango da, eta hau izango da hegan bidez
eman eta hauek nola algoritmoak hainbat lan zentzua akustikoa.
Hona hemen txertatzeko sort da.
[Elektronikoen beeping]
[Malan] Bubble sort.
[Azkarrago elektronikoen beeping]
[Malan] Aukeraketa sort.
[Azkarrago elektronikoen beeping]
[Malan] Batu sort.
[Elektronikoen beeping]
[Beeping moteldu] [barreak]
[Malan] Gnome sort.
[Elektronikoen beeping]
>> Hau CS50 da. Ikusiko dugu datorren astean. [Txaloak eta txaloak]
>> [CS50.TV]