[Musika jotzen] DAVID MALAN: Eskubidea guztiak. Ongi, ongi etorria itzuli. Beraz, aste honetan 4 da, hasiera-hasieratik haietan, dagoeneko. Eta gogora ekarri azken astean duzula ikusiko dugu jarri kodea alde batera bakarrik pixka bat egiteko eta pixka bat gehiago hitz egiten hasi ginen goi-maila bezala, gauzak bilatu eta sailkatzeko, eta horrek, nahiz eta zertxobait ideia sinpleak dira, arazo klase bat ordezkari hasten dira, batez ere konpondu ahal izango duzu hasten zara pentsatzen azken gisa proiektuak eta interesgarri irtenbideak duzu baliteke mundu errealeko arazoak izan. Orain burbuila ordenatu errazena bat izan zen hala nola, algoritmo, eta txiki zenbaki hauek izatea lan egin zerrenda batean edo array mota de burbuila beren bidea sortu goian, eta big zenbakiak mugitu bidean behera zerrendaren amaieran. Eta gogora ekarri ahal izan dugun ikusteko burbuila sort apur bat honen antzeko zerbait. Hargatik aurrera ni eta sakatu Hasi. Hautatuko dut burbuila ordenatu. Eta gogoratzen baduzu taller urdin hori lerro zenbakiak irudikatzeko handi, txiki blue lerro zenbakiak irudikatzeko txiki, gisa honen bidez joan gara, behin eta berriz, eta berriro ere, bi taberna alderatuz ondoan bakoitzean Gorriz beste swap goaz handiena eta txikiena bada atera dira, ordena. Hau joan egingo da, eta, beraz, joan eta joan , eta ikusiko dela handiagoa izango zara elementu batzuk bere bidea egiten ari da eskubidea, eta txikiagoa elementuak dira bere bidea egiten ari da ezkerretik. Baina zenbatzeko hasi ginen eraginkortasuna da, algoritmo honen kalitatea. Eta esan txarrena dela kasuan, algoritmo hau hartu Gutxi gorabehera, zenbat urrats? Beraz n karratu. Eta zer izan zen n? Ikusleak: elementu kopurua. DAVID MALAN: Beraz n izan zen elementu kopurua. Eta, beraz, hau egingo dugu sarritan. Edonoiz tamaina buruz hitz egin nahi dugu arazo bat edo tamaina sarrera, edo zenbat denbora da hartzen irteera ekoizteko, besterik ez dugu orokortua edozein dela ere sarrera-n bezala. Beraz, atzera Astea 0, zenbaki orrialdeak telefono-liburua izan zen n. Ikasle kopurua aretoan zen n. Beraz, hemen ere, jarraituz ari gara eredu hori. Orain n karratuko ez da bereziki azkar, beraz, hobeto egiten saiatu gara. Eta, beraz, begiratu pare bat dugu beste algoritmoak, eta horien artean ziren hautaketa ordenatu. Beraz, aukeraketa sort zen apur bat desberdina da. Ia-ia errazagoa izan zen, esaten ausartzen naiz, Horren bidez, hasi zen hasieran I gure boluntarioen zerrenda eta dut berriro eta behin eta berriro joan bidez zerrendan, eta plucking txikiena aldi berean, elementu eta berarekin jarriz edo bere zerrendaren hasieran. Baina honetan ere, beste behin pentsatzen hasi ginen matematika eta handiagoa bidez Irudian, zenbat aldiz pentsatu Itzuli nintzen joan eta aurrera eta atzera eta aurrera, esan zuen, eta kasurik okerrenean gaude, aukeraketa, ordenatu, ere, izan zen zer? n karratu. Gaur egun, mundu errealean, Agian benetan marginalki azkarrago. Berriro ere, zeren, ez nuen gorde nuen horrela antolatu du beste behin backtracking txikiena elementuak. Baina, n oso handia pentsatzen badugu, eta Ordena duzu bada math bezalako Egin taula gainean I, n karratu dituzten ken zerbait, beste guztia n, behin karratu n gain lortzen benetan handia da, ez du benetan axola bezainbeste. Beraz, ordenagailu zientzialari gisa, mota dugu piztu begi itsu bat txikiagoa faktoreak eta faktore bakarra buruzko ikuspegia adierazpen hori egiteko joan diferentzia handiena. Beno, azkenik, begiratu dugu txertatzeko ordenatu zen. Eta hau izan zen espiritua antzekoa da, baina baino gehiago pasa eta iteratively hautatu batean elementu txikiena ko denbora hartu ordez dut eskua dut landu zen, eta erabaki dut, guztia eskubidea, hemen sartzen duzun. Orduan joan nintzen hurrengo elementua eta erabaki zuen, edo hori Hemen baita zuen. Eta, ondoren, mugitu eta nik. Eta agian I, bidean, mugitzeko mutil hauek egin ahal izateko horiek egiteko gela. Horrela mental moduko atzerakada izan zen aukeraketa Ordena dugu izeneko txertatzeko ordenatu. Gai horiek gertatzeko, beraz, mundu errealean. Besterik gabe, duela urte batzuk, noiz jakin bat senatari izan zen presidente martxan Eric Schmidt, garai hartan CEO du Google, benetan aukera izan zuten zion elkarrizketak. YouTube eta partekatu genuen pentsatu genuen zuretzat moztu hemen, gora eginez balute bolumena. [Bideo-erreprodukzioa] -Orain, senataria, zu hemen Google-n, eta Lehendakaritza pentsatzea gustatzen zait lan elkarrizketa baten ondorioz. [Barreak] -Orain zaila da iritsi presidente gisa lan bat. Eta bitartez duzu rigors orain. Era berean, gogor Google-lan bat lortzeko. Galderak egin ditugu, eta eskatu gure hautagaiak galderak. Eta hau Larry Schwimmer da. [Barreak] -Zaudete uste Txantxetan ari naiz? Eskubidea hemen da. Zer modurik eraginkorrena da ordenatzeko milioi bat bi-bit osokoak? [Barreak] -Ba, uh - -I'm sorry. Agian behar dugu - -Ez, ez, ez, ez, ez. -Hori ez da bat - Ados. -I burbuila ordena uste okerreko bidea joan daiteke. [Barreak] [Eta txaloak txalo] -Tira, nork esan zion hau? Ados. [END bideo-erreprodukzioa] DAVID MALAN: Beraz, ez daukazu. Beraz, hauek exekutatzen zenbatzeko hasi ginen aldiz, eta, beraz, hitz egiteko zerbait izeneko asymptotic idazkera, hau da, besterik gabe, gure inflexio moduko aipatuz txikiagoa faktore horiek begi itsu eta bakarra exekutatzen denbora begira, algoritmo hauen errendimendua, n lortzen benetan handi gisa denboran zehar. Eta, beraz, big O. eta Big O sartu dugu irudikatzen zerbait pentsatu dugu goiko doazen bezala. Eta egia esan, Barry, ezin dugu jaistea mic pixka bat baino? Pentsatu da, goiko bat lotu dugu. Beraz, big n bitartez karratu O duten kasurik okerrenean, zerbait aukeraketa ordenatu litzateke hartu karratu urrats n. Edo txertatzeko sort antzeko zerbait litzateke n karratu urratsak. Txertatzeko moduko zerbait orain ordenatu, txarrena zer gertatu zen? Emandako array bat, zer txarrena da ahalik eta eszenatoki agian duzula aurkitu aurrean zure burua? Erabat atzeraka da, ezta? Zeren erabat atzeraka egin da, lan asko egin behar duzu. Bazara guztiz atzeraka galtzen delako, aurkitu behar duzu handiena elementu hemen, nahiz behera pertenece han. Beraz, esan duzu, bai, at Une honetan, hemen sartzen duzun, beraz, utzi pakean. Gero, ohartzen zara Oh, madarikatua, behar dut mugitzeko, apur bat txikiagoak elementu duzu ezkerreko du. Orduan, berriro egin behar dut eta behin eta berriro. Ibili eta gero atzera eta aurrera, zu sentitzen de la actuación sailkatuko litzateke algoritmoa, izan ere, etengabe ari naiz Besteek nahasteko behera hasi array gela egin behar da. Beraz, hori txarrena kasua da. Aitzitik - cliffhanger eta hau izan zen azken aldia - esan txertatzeko ordenatu duten izan zen zer omega bat? Zer best-kasuan korrika da txertatzeko Ordena denbora? Beraz, benetan n. Hau zurian utzi genituen taula gainean azken aldiz. Eta n omega zergatik delako da? Beno, onena kasuan, zer txertatzeko ordenatu entregatu egingo da? Beno, zerrenda bat dela guztiz ordenatuko dagoeneko, gutxieneko lan egin. Baina zer txertatzeko ordenatu buruzko neat hasten da hemen, zeren eta erabakitzen du, ai, zenbaki zara bat, hemen sartzen duzun. Oh, zer zortea bat. Zenbaki bi zara. Sartzen dira, halaber, hemen. Hirugarrena, are hobeto, Hemen sartzen duzun. Bezain laster lortzen amaieran da zerrenda, txertatzeko per ordenatu en pseudocode hitzez bidez garela ibili azken aldiz, egiten da. Baina aukeraketa ordenatu, aitzitik, mantendu, zer egiten? Mantendu zerrendan zehar joan behin eta berriro, eta berriro. Gako ikuspegi han zelako bakarrik duzun begiratu behin modu guztiak zerrendaren bukaeran ahal izango duzu, zenbait elementu hautatutako zela hain zuzen ere, gaur egun, txikiena elementua. Desberdin horien buruko ereduak amaieran, beraz, Oso mundu errealeko yielding sortu Gurekin desberdintasunak, eta baita horiek teoriko asymptotic ezberdintasunak. Beraz, argibideak nahi izanez gero, big n O karratu, ikusi dugu gutxi batzuk, hala nola, algoritmoak, beraz, oso urrun. Big n O? Zer algoritmo bat izan da esan big n O izateko? Kasurik okerrenean ere, hartzen urratsen kopurua lineal bat. Ados, lineal bilaketa. Eta txarrena kasuan, non da denean elementu bila zabiltzan bilaketa lineala aplikatuz? Ados, txarrena kasuan, ez da, nahiz eta ez. Edo txarrena bigarren kasuan, haren eta, azkenean, modu batean, hau da, guztiak gehi-or-ken-ko urratsa aldea. Beraz, egunaren amaieran, esan lineala dela esan daiteke. Big n O bilaketa lineala izango litzateke, txarrena kasuan, delako elementua ez da, nahiz eta ez dago edo oso amaieran modu guztiak. Beno, big n log O. Ez dugu zehaztasun handiz hitz egin hau, baina ikusi dugu lehenago. Zer deiturikoak logaritmikoa exekutatzen denbora, txarrena kasuan? Bai, beraz, bilaketa bitarra. Eta txarrena kasuan bilaketa bitarra elementua izan dezake nonbait hasi erdi-erdian, edo nonbait array barruan. Baina besterik ez duzu zuk behin zatitzen zerrenda erdia, hasi erdia, erdia, erditik. Eta, ondoren, voila, ez da. Edo, berriro ere, kasurik okerrenean, ez da, nahiz eta ez. Baina ez dakizu hori ez Ordena iritsi arte, azken hori behetik gehien halving by elementuak eta halving halving. Big O 1. Hain handia, 2, 3 big O O genezake. Nahi duzun kopurua konstante bat edonoiz, errazteko besterik ez du besterik ez dugu ordenatzeko big 1 O bezala. Nahiz eta errealistan, bada hartzen du, nahiz eta 2 edo are 100 urrats, bada bat da urrats-kopurua konstante esatea besterik ez dugu 1 O big. Zer algoritmo bat, hori da big 1 O-en? Ikusleak: luzera aurkitzea aldagai bat da. DAVID MALAN: aurkitzea aldagai baten luzera? Ikusleak: Ez, luzera nik dagoeneko antolatuta. DAVID MALAN: Ongi. Ados, beraz, zerbait luzera aurkitzeko zerbait luzera, nahi izanez array bat da, aldagai batzuk gordetzen dira. Ezin duzu besterik ez delako irakurri aldagaia, edo inprimatu aldagaia, edo oro har sartzeko duen aldagaia. Eta voila, konstante denbora. Aitzitik, uste itzuli urratu. Think itzuli C lehenengo astean, besterik printf deituz eta inprimatzeko pantailan zerbait da, dudarik gabe, etengabeko denbora, besterik ez da hartzen duelako PUZaren zenbait ziklo kopurua erakusteko pantailan testua. Edo itxaron - egiten du? Nola liteke bestela, ereduetan dugu printf errendimendua? Litzateke norbait nahi ados, hori agian ez da benetan etengabeko denbora? Zer zentzu baliteke printf da exekutatzen denbora, benetan kate batean inprimatzeko pantailan, zerbait izango etengabeko beste. Ikusleak: [INAUDIBLE]. DAVID MALAN: Bai. Araberakoa izango da, beraz, gure ikuspegitik da. Benetan dugu sarrera bada pentsatzea katea bezala printf, eta beraz, horren tamaina neurtzen dugu bere luzera by input - Hargatik deitu luzera n bai - dudarik gabe, printf da berez n O big Zu zara n urratsak delako joan inprimatu n horietako bakoitzean pertsonaiak, ziurrenik. Gutxienez neurri hartu dugun agian hori da begizta erabiliz egiteko kanpaia azpian. Baina hori begiratu nahi dugu kodea hobeto ulertzeko. Eta, hain zuzen ere, behin zaudete hasteko Zeure algoritmoak aztertu, ikusiko duzu hitzez hitz egin besterik ez da. Eyeball moduko zure kodea, eta uste buruz - eskubidea, begizta hau daukat hemen edo daukat Habiaratutako kiribil bat hemen, hori gauza n n aldiz egingo, eta arrazoia dezakezu zure ordenatzeko modu kodearen bidez, nahiz eta oso pseudocode eta ez benetako kodea. Beraz n karratu de omega buruz zer? Zein izan zen algoritmoaren onena dela kasuan, oraindik hartu n karratu urratsak? Bai? Ikusleak: [INAUDIBLE]. DAVID MALAN: Beraz, aukeraketa ordenatu. Arazo hori benetan murriztu delako Izan ere, berriro ere, ez dakit Aurkitu dut gaur egungo txikiena arte Checked dut darn elementu guztiak. , Esan, eta, beraz, omega n, dugu besterik ez zen bat ere. Txertatzeko ordenatu. Zerrendan gertatzen ordenatuko nahi baduzu dagoeneko, onenen kasuan besterik ez dugu pass bat egiteko horren bidez, puntu ziur gaude at. Eta gero, esan liteke lineala izango da, ziur. 1 omega zer? Zer da onena, kasu honetan, agian hartu urrats-kopurua konstante bat? Beraz, bilaketa lineala, besterik ez duzu lortzen bada zortea eta elementu bilatzen ari zaren eskubidea da zerrendaren hasieran, hori da, non zure zaren hasten bada lineal zerrenda hori eskuratzea. Eta hau da, benetako gauza kopurua. Esate baterako, nahiz eta bitar Bilaketa 1 omega da. Zer gertatuko da benetan delako darn lortuko duzu Zorioneko eta smack-DAB erditik aurrera hasi Zure array kopurua da bilatzen ari zarena? Beraz, zortea dezakezu han, bai. Honek, azkenik, n log n omega. Beraz n log n, ez dugu benetan gabe hitz egin zuen, baina - Ikusleak: Batu ordenatu? DAVID MALAN: Batu ordenatu. Denbora azken cliffhanger zen, non, proposatu dugu, eta erakutsi dugu ikusmen, daudela algoritmoak. Bateratu eta bakar bat, besteak beste, antzeko algoritmoa, funtsean azkarrago guys horiek beste batzuk baino. Izan ere, bateratu laburra da, eta ez bakarrik hasi onenak kasu n log n, txarrena en Kasu n log n. Eta noiz kasualitatea horren behar duzu omega eta big O gauza bera izatea? Egia esan, ezin dugu hori deskribatzeko zer gisa izeneko theta, da, nahiz eta bat zertxobait gutxiago dira. Baina, besterik gabe esan nahi du bi mugak, kasu honetan, berdinak dira. Beraz, batu, ordenatu, zer da hau benetan irakiten behera Gurekin? Beno, gogoratzen motibazioa. Let me tira gora animaziozko beste ez genuen azken aldiz begiratu. Honek, ideia bera, baina pixka bat handiagoa da. Eta aurrera joan eta azpimarratu dut lehen - txertatzeko ordenatu izan dugu goiko ezkerreko eta, ondoren, hautapen ordenatu, burbuila ordenatu, ordenatzen beste pare bat - Shell eta azkar - ez ditugula hitz buruz, eta zeure ordenatu eta batu. Gutxienez saiatu zure begiak arreta, beraz hiru goiko ezkerreko eta, ondoren, batu ordenatu nuenean sakatu gezi berdeak honetan. Baina horiek guztiak exekutatu dut, besterik ez ematen duzu aniztasuna zentzua algoritmo hori munduko existitzen. Exekuzio honetan utzi dut besterik gabe, segundo batzuk. Eta fokua duzu zure begiak bada - hautatzeko bat bildu, zentratu da, besterik gabe, bat segundo - Hasteko, ikusiko duzu eredua dela ezartzeko. Batu, ordenatu, oharra, eginda dago. Montón ordenatu, azkarra, ordenatu, shell - beraz, badirudi hiru sartu dugu txarrena algoritmoak azken astean. Baina hori onak garela hemen gaur merge ordenatu begiratu, zein da errazagoa da, bai ikusteko, nahiz ziurrenik zure kontuan, nahiz eta okertu egingo besterik gabe, apur bat. Hemen ikusi ahal izango dugu, besterik gabe, zenbat aukeraketa ordenatu sucks. Baina flip albo batean, haren Benetan erraza ezartzea. Eta, agian, P ezarri 3, hori bat da algoritmoak inplementatzeko aukeratu duzu estandarra ediziorako. Primeran fina, erabat zuzena. Baina, berriro, n bezala lortzen handiak, baduzu aukeratu azkarragoa algoritmo bat ezartzeko gustatzen batu, ordenatu, odds handiagoak dira, eta sarrera handiagoak, zure kodea ez da besterik azkarrago exekutatu behar. Zure web orria da hobeto lan egiten du. Zure erabiltzaile daude zoriontsuagoa izango. Eta, beraz, ez dira efektu horiek benetan ematea gurekin batzuk sakonago pentsatu. Beraz dezagun zer batu begirada bat ordenatu da benetan guztiei buruz. Cool gauza da batzen duten sort besterik ez da hau. Hau da, berriz ere, zer deitzen dugun pseudocode, pseudocode izaki English antzerako sintaxia. Eta soiltasuna da liluragarriak agintzea. Beraz, n elementu sarrera on - beraz, esan nahi du, besterik gabe, hemen array bat da. Honez lortu n gauzak bertan. Duten guztiak ez gara esaten da. N 2 baino txikiagoa bada, itzultzeko. Beraz, hori besterik Bañales kasuan. N 2 baino gutxiago bada, orduan, jakina, oso 1 edo 0, kasu horretan, gauza ordenatuko da, dagoeneko existitzen ez den edo, beraz, besterik ez itzultzeko. Ez da ezer egin behar da. Beraz, erraz bat Kasu off pluck behar da. Bestela, hiru urrats egin behar dugu. Ordenatzeko elementuak erdia ezker, eta ordenatu elementuak erdia eskubidea, eta, ondoren, batu erdi ordenatuko du. Zer da interesgarria hemen da Punting mota naiz, ezta? Ez dago zirkular definizio mota da to algoritmo hau. Zer zentzu da, algoritmo honen Definizio zirkularra? Ikusleak: [INAUDIBLE]. DAVID MALAN: Bai, nire ordena bildu, bere urrats bi dira "Ordenaren zerbait. "Eta beraz, segurutzat jotzen du galdera, bai, zer am going to erabili dut Ezkerraldean erdia ordenatzeko eta eskuineko erdia? Eta edertasuna, hemen da, nahiz eta hori berriz ere, hau da, kontuan-flexiones da zati potentzialki, bera erabili ahal izango duzu algoritmoa ezkerreko erdia ordenatzeko. Baina itxaron minutu bat. Duzunean esan ordenatzeko Ezkerraldean erdia, zer bi dira hurrengo urratsak izango da? Erdia ezker sailkatuko dugu Ezkerraldean erdi eta eskuin ezkerreko erdi erdia. Malditos, nola diren bi sailkatuko dut erdi edo laurden, orain? Baina hori Ados. Ordenatzeko algoritmo bat dugu hemen. Eta nahiz eta kezkatu baliteke at Lehenengo hau amaigabea da mota begizta, ziklo hori inoiz ez da Amaierara joan - da joan Amaierara behin zer gertatzen da? Behin n 2 baino gutxiago da. Horrek, azkenean da gertatuko, mantentzen baduzu eta halving delako erdi hauetan halving batean, ziur aski halving azkenean amaituko duzu besterik ez da 1 edo 0 elementuak sortu. Duen puntua, algoritmoa honetan dio Bukatutakoan. Honetan, benetako magia, hain algoritmoa dirudi en duen azken urratsa, batuz. Bi konbinatzeko ideia sinplea duten gauzak, hori da, azken finean, zer gertatzen da array baten ordenatzeko ahal izateko, demagun, zortzi elementu. Beraz, zortzi gehiago estresa pilotak daukat sortu Hemen, zortzi paper zatiak, eta bat Google Glass - horrek mantentzea lortu dut. [Barreak] DAVID MALAN: zortzi dugu balute boluntarioak, eta ikus dezagun dugu, ahal bada play hau, beraz. Wow, OK. Informatika da fun lortzean. Guztiak eskubidea. Beraz, zer egin dezakezu, hiru, handiena, han sortu eskua. Atzealdean lau. Eta nola buruz egingo dugu Lerro honetan hiru? Eta aurreko lau. Beraz, zortzi, etorri da. [Barreak] DAVID MALAN: benetan naiz ez ziur zer den. Da estresa pilotak? Lanparak mahaian? Materiala? Interneten? Ados. Beraz, zatoz gora. Nor nahi - Datozen mantentzeko. Ikus dezagun. Eta hau jartzen baduzu, kokapen - Oraindik kokapen bat zara. Uh-oh, minutu bat itxaron. 1, 2, 3, 4, 5, 6, 7 - Oh, ona da. Ondo da, onak ditugu. Guztiak eskubidea, beraz, denek dute eserlekua, baina ez da Google Glass gainean. Let me up ilara horiek. Zein da zure izena? MICHELLE: Michelle. DAVID MALAN: Michelle? Ondo da, eta itxura lortuko duzu geek, hau da Ados. Beno, gehiegi egin dut, suposatzen dut, besterik gabe, une batez. Guztiak eskubidea, egonean. Izan gara etorri batekin saiatzen erabili kasu Google beira, eta guk uste dibertigarria besterik ez litzateke egin pertsonak dira eszenatokian. honetan Munduko grabatu egingo dugu bere ikuspuntutik. Guztiak eskubidea. Ez da, ziurrenik, Google xedea. Ondo da, ez baduzu axola jantzita baldar du hurrengo minutu honetan, hori zoragarria izango litzateke. Ondo da, beraz, hemen dugu array baten elementuak, eta array duten bezala, per paper zatiak Folks hauetan ' eskuak, gaur egun, Sailkatu gabe. MICHELLE: Oh, hori da hain arraroa. DAVID MALAN: nahiko askoz ausazko da. Eta besterik gabe, une batean, saiatzen gara batu ordenatu elkarrekin ezartzeko ikusi eta non ulertzeko gakoa dela. Eta trikimailu hemen merge Ordena da zerbait ez ditugula bere gain hartu oraindik. Benetan behar dugu zenbait osagarriak espazioa. Beraz, batez ere, zer izango honen inguruan interesgarria da horiek mutilak dira, pixka bat mugitu joan bit, naiz dudalako joan nahi du bere gain hartzen duten ez espazioa array estra bat da, esan, eskubidea atzean. Hala bada Oraindik bere aulkia atzean dira, duten bigarren mailako array da. Ari dira eserita, bada, hemen, hori da lehen array. Baina hau baliabide bat dugula da Ez da, beraz, oso urrun leveraged burbuila batera ordenatu, hautaketa Ordena, Ordena txertatzeko. Gogoratzen azken astean, denek besterik nolako lekua nahastu. Ez zuten erabili osagarriak memoria edozein. Lagunentzako tokia egin dugu pertsona inguru mugitzen. Beraz, gakoa ikuspegi bat da, gehiegi. Ez dago hau merkataritza-off da, oro har, informatika, baliabideak. Nahi duzun azkartzeko zerbait bada denbora bezala, behar duzu dute prezio bat ordaindu behar izan. Prezioak, eta horietako bat da, oso maiz espazioa da, memoria edo gogorra Diskoan lekua erabiltzen ari zaren. Edo, sinceramente, zenbatekoa programatzaile denbora. Zenbat aldiz hartzen du, giza, benetan ezartzeko gehiago konplikatuak algoritmoa. Baina, gaur egun, merkataritza-off denbora eta espazioa da. Beraz baduzu guys besterik ezin eutsi zure zenbakiak, beraz, ikusten ari zaren dezakegu hain zuzen ere, 4, 2, 6, 1, 3, 7, 8 betetzen. Bikain. Beraz orkestratu saiatu naiz gauzak, baduzu guys besterik jarraitu nire beruna hemen. Beraz, garatu dut, lehenengo, lehen pseudocode urratsera, hau da, n elementuen sarrera, n bada on 2 baino gutxiago, eta gero itzultzeko. Jakina, horrek ez du bada, beraz, mugitzeko dugu. Beraz ordenatzeko elementuak erdia ezkerrera. Beraz, horrek esan nahi du, bideratzeko dut nire besterik gabe, horiek une batean arreta lau mutil hemen. Guztiak eskubidea, zer egin behar dut hurrengo? Publikoa: Sort ezkerreko erdian. DAVID MALAN: Beraz, orain ordenatzeko daukat mutil hauek erdia ezkerrera. Zeren eta berriro, zure burua bere gain helburua da ezkerreko erdia ordenatzeko. Nola egiten da hori? Just jarraitu, nahiz eta ari gara, nahiz eta egiten ari da berriro. Beraz ordenatzeko ezkerreko erdian. Orain bi mutil hauek dut ordenatzeko. Zer datorrena? Publikoa: Sort ezkerreko erdian. DAVID MALAN: Sort ezkerreko erdian. Beraz, gaur egun horiek, eserlekua hau hemen, tamaina 1 zerrenda bat da. Eta zein da zure izena berriro? PRINCESS DAISY: Princess Daisy. DAVID MALAN: Princess Daisy da hemen. Eta, beraz, berak horrela antolatu da dagoeneko, izan ere, zerrenda tamaina 1 da. Zer egin hurrengo dut? Ados, bueltatu, zerrenda hori delako tamaina 1, 2 baino gutxiago. Orduan, zer da hurrengo urratsa? Eta orain, mota behar duzu zure gogoan backtrack. Ordenatzeko eskuineko erdia, hau da, - Zein da zure izena? LINDA: Linda. DAVID MALAN: Linda. Eta, beraz, zer egin dezaket orain egin dugu tamaina 1 zerrenda bat egin behar dugu? Ikusleak: Sartu. DAVID MALAN: Kontuz. Lehenengo itzuliko gara, eta, orain, hirugarren urratsa -, eta badut nolako itxura duen bi eserleku besarkatzen orain, gaur egun I bi elementu horiek batzeko. Beraz, gaur egun, zoritxarrez, elementu ordenatik kanpo daude. Baina hori non uztartzeko prozesua da hasten da sinesgarria lortzeko. Beraz baduzu guys zutik zitekeen soilik Une batean, behar duzun noa, batean Oraingoz, zure aulkia igarotzea. Eta Linda, 2 duelako bada 4 baino txikiagoa da, zergatik ez inguruan zatoz lehen? Egonaldia. Linda, beraz, inguru zatoz lehen. Errealitatea da gaur egun, besterik ez bada, array bat besterik ezin dugu bere denbora errealean aulki hau tik Leku hau. Beraz, imajina hartu duten konstante batzuk 1 urrats kopurua. Eta orain - baina jarri behar dugu lehen kokalekua hemen. Eta orain, inguruan zaudela balute, baita ere, nahi dugu kokapena, bi izango dira. Eta nahiz eta hau sentitzen duen bezala pixka bat hartu, zer polita da orain erdia ezkerraldean Ezkerraldean erdia da, gaur egun antolatuta. Beraz, zer izan zen hurrengo urratsa dugu, orain bada atzeratzeko gehiago istorioan? Ikusleak: Eskuin erdia. DAVID MALAN: Sort eskuineko erdia. Beraz, you guys dute hori egin ahal izateko, bai. Beraz, bada, Zutik dezakezu besterik gabe, une batez? Eta zein da zure izena? Jess: Jess. DAVID MALAN: Jess. Ados, eta, beraz, gaur egun, Jess Ezkerraldean eskuineko erdia erdia. Eta, beraz, tamaina 1 zerrenda bat egin zuen. She da, jakina, ordenatzen. Eta zure izena berriro? MICHELLE: Michelle. DAVID MALAN: Michelle da, jakina, tamaina 1 zerrenda. She dagoeneko antolatuta. Beraz, magia gertatzen da, konbinatzeko prozesua. Beraz, nork lehenengo etortzen da? Jakina Michelle. Hala bada etortzen inguruan asmoz itzuli. Espazioa bere eskuragarri dugu orain eskuineko aulki hau hemen atzean. Eta, orain, itzuli baduzu, etorri ahal izan baita, ditugu, argi izan behar da, bi erdi, tamaina bakoitzeko 2 - eta besterik irudikatze en onerako, baduzu espazio bat pixka bat egin dezake - erdia hemen utzi, bat eskuineko erdia hemen. Atzeratzeko gehiago istorioan. Zer da hurrengo urratsa? Ikusleak: Batu. DAVID MALAN: Beraz, orain batu ditugu. Beraz, OK, beraz, gaur egun, zorionez, ez dugu besterik askatuko lau aulkiak. Beraz, erabili dugu bi aldiz memoria askoz, baina eman flip-flopping dezakegu arteko bi matrizeak. Beraz, zein da zenbakia lehen etorri nahi? Beraz, Michelle, jakina. Beraz, zatoz eta inguruan hartu zure eserlekua hemen. Eta, ondoren, multzoko 2 da, jakina, hurrengo, eta, beraz, hemen etortzen zara. 4, 6. Eta, berriro ere, nahiz eta bat inplikatutako oinez pixka, Benetan, horiek berehala gerta liteke, - ko mugituz Ados, ongi jokatu. [Barreak] DAVID MALAN: Eta orain gara forma nahiko ona da. Osoa erdia Ezkerraldean sarrera izan da antolatuta. Ondo da, beraz, mutil hauek izan nire abantaila - Nola amaituko da on neskak guztiak utzi eta eskuinera egiten mutilen guztiak? Ados, beraz, mutilak, orain buelta ». Beraz, ez dut zure bitartez oinez urrats hauek. Ikusiko dugu reapply bada dizugu berean pseudocode du. Nahi duzun aurrera, eta stand up bada, eta zaudete, utzi dizu me mic. Ikusi ez baduzu errepikatzeko zer egin besterik ez dugu hemen an zerrendaren bukaeran beste. Nork behar du lehen hitz egiten, algoritmoan oinarritutako? Beraz, aurretik azaldu zer egiten ari zaren Oinez mugimenduak egin duzu. HIZLARIA 1: Guztiak eskubidea, beraz, geroztik Erdia ezker naiz Ezkerraldean erdia, I itzultzeko. Eskuin? DAVID MALAN: Ongi. HIZLARIA 1: Eta gero - DAVID MALAN: nork ez du mic hurrengo joan? HIZLARIA: 1 Hurrengo kopurua. HIZLARIA 2: Beraz, eskuineko erdia naiz ezkerreko erdiko Ezkerraldean erdia, eta ni itzultzeko. DAVID MALAN: Ongi. Duzu itzultzeko. Beraz, orain zer duzu bi hurrengo sortu da? HIZLARIA 2: ikusi nor txikiagoa nahi dugu. DAVID MALAN: Horixe. Ra batu nahi ditugu. Espazioa behar batzeko erabili behar dugu baduzu, sartu, nahiz Oraindik ordenatuko da, jakina, dagoeneko, joan gara berean algoritmoa jarraitzeko. Beraz, nork atzera lehenengo doa? 3 Beraz, eta, ondoren, 7. Eta orain, mic doa to mutil hauek, OK? HIZLARIA 3: Beraz erdia eskubidea dut Ezkerraldean erdia, eta nire n baino txikiagoa 1, beraz, besterik ez naiz pasatzen joan - DAVID MALAN: Ongi. HIZLARIA 4: erdia eskubidea dut eskubidea eskuineko erdia erdiak, eta nago Era berean, pertsona bat, naiz eta, beraz, itzuli egingo da. Beraz, orain batu ditugu. HIZLARIA 3: Beraz, atzera egingo dugu. DAVID MALAN: Beraz, atzera jo duzun. Beraz, 5 doa lehenengo eta, ondoren, 8. Eta orain, ikusleek, eta hori da, urratsera orain atzera egin behar dugu itzuli gure adimenak? Ikusleak: Batu. DAVID MALAN: batzea ezker erdiko eta eskuineko ezkerreko jatorrizko erdi erdia. Beraz, orain - eta, besterik gabe, honek argi eta garbi egiteko, egiteko espazio pixka bat duzun bitartean, bi mutil. Beraz, gaur egun, hori da, bi zerrendak, ezkerreko eta eskuineko. Beraz, nola ez, batu dugu zaudete sartu eserleku-ilara aurrean berriro? 3 doa lehen. Ondoren, 5, jakina. Ondoren, 7, 8 eta orain. Ados, eta orain gauden? AUDIENCE: ez da egin. DAVID MALAN: egin ez delako, jakina, ez dago urrats bat Gainerako da. Baina, berriro ere, arrazoia dut hau erabiliz "zure kontuan atzeratzeko," bezalako jargon hori benetan delako da Zer ari da gertatzen. Urrats guztiak osatu dugu, baina bat gelditzea moduko gara Oraingoz, sartu sakonago urpekaritza bildu, une batez gelditzea, urpekaritza algoritmoa barneratu, eta orain, atzeratzeko moduko gure dugu adimenak eta desegin geruza horiek guztiak dugun Ordena atxikitzen da. Beraz, orain bi tamaina 4 zerrendetan dugu. Zaudete zutik balute, azken denbora eta espazio pixka bat hemen argi hori ez dela ezker , jatorrizko erdia jatorrizko erdia eskuinera. Nork lehen zenbakia da, guk behar berriro sartu tira? Michelle, noski. Beraz, Michelle jarri dugu hemen. Eta nor multzoko 2 du? Multzoko 2 dator berriro ere. 3 zenbakia? Bikain. 4 zenbakia, zenbaki 5, 6, 7, eta 8. Ados, beraz, sentitu asko bezala eskailera, ziur. Baina orain, ikus dezagun, ezin dugu bada baieztatzeko sort intuizioa dela horren algoritmo batez ere, batez ere n lortzen benetan handia da, nik ikusi dugun bezala animazioak batera, da funtsean, azkarrago. Beraz, algoritmo hau aldarrikatzen dut, txarrena en kasuan, eta nahiz eta onena kasuan, handi n aldiz log n O. Hau da, honen alderdi batzuk algoritmoa egiten n urratsak, baina ez beste alderdi bat da, nonbait hasi iterazio dela, begizta duela hartzen log n urratsak. Gure hatz jarri dugu zer diren bi zenbakiak erreferentzia? Beno, non - where'd mic joan? HIZLARIA: 1 Nahi saioa n Gurekin hausteko bi sartu - bi, zatituz, funtsean. DAVID MALAN: Horixe. Edonoiz ikus algoritmoa edozein dugu, beraz, Orain arte, ez da patroi hau izan da , zatituz zatituz, zatituz. Eta nik, normalean, murriztu den zerbait da logaritmikoa, log 2 oinarria. Baina ezin da ezer izan, baina saioa 2 oinarria. Orain n buruz zer? Ikusteko nolako dugun banatzen dezaket guys - banatzen duzu, banatzen baduzu, banatzen duzu, banatzen duzu. Non amaieran dator? Beraz batzea da. Buruz uste duelako. Noiz zortzi pertsona batu batera, Horren bidez, erdiak lau multzo bat dira eta beste erdia, beste hauek dira lau multzo, nola joan du batuz egiten? Beno, zuk guys zuen nahiko intuizioa. Baina nik bada, apur bat gehiago metodikoki, at dut agian adierazi du ezkerreko pertsona nire ezkerreko lehen alde batetik, eta ezkerreko pertsona at adierazi nire eskua eskuineko erdia, eta besterik gabe, ondoren barrena ibili zerrenda, txikiena elementu seinalatuz aldi bakoitzean, nire hatz gainean eta higitzen gisa baino gehiago zerrendan zehar, behar den. Baina zer da hau batuz buruzko gakoa prozesu bikote hauek dut alderatuz elementuen. Eskuineko erdia eta ezkerretik erdi, inoiz ez dut behin backtracking. Beraz, konbinazio bera hartzen ari da ez baino gehiago n urratsak. Eta zenbat aldiz egin dut a batuz egin? Beno, ez n baino askoz gehiago da, eta guk, besterik gabe, urtean behin betiko merge duten. Eta, beraz, nahi duzu zerbait hartzen bada saioa n urratsak n aldiz, edo alderantziz, Gurekin n aldiz log n eman behar da joan. Eta zergatik da hau hobeto? Beno, dagoeneko ezagutzen ditugun log galtzen duten n n baino hobeto - ezta? Ikusi bilaketa bitarra dugu, telefono-liburua Adibidez, egunkari-n izan zen, zalantzarik gabe, lineal baino hobeto. Beraz, horrek esan nahi du n aldiz log n behin betiko n aldiz baino hobeto beste n, AKA n karratu. Eta hori da, azken finean, sentitzen dugu. Beraz, txalo zaparrada handia Kopako, bada , ezin dugu mutil hauek egiteko. [Txaloak] DAVID MALAN: Eta zure parting opariak - zenbakiak gorde ahal izango duzu, Nahi izanez gero. Eta zure parting oparia, ohikoa den bezala. Oh, eta duzuela material, Michelle. Eskerrik asko. Guztiak eskubidea. Laguntza zaitez estresa baloi bat. Eta utzi sortu tira niri, bitartean, gure lagun Rob Bowden eskaintzeko zertxobait ezberdinak honetako ikuspegitik, dezakezu hauei buruzko geroztik uste urrats pixka bat gertatzen modu ezberdin. Izan ere, zer da Rob about set-up erakusteko bere gain hartzen dugun Jadanik egindako zatituko du gora zortzi zerrendak txikitan zerrenda handia, tamaina 1 bakoitzean. Beraz pseudocode ari gara aldatzen bat pixka bat, besterik gabe, bertan lortzeko moduko core nola lanak uztartzeko ideia. Baina zer da denbora martxan egin zuen, buruz da oraindik bera izango da. Eta berriro ere, set-up Hemen da zuen zortzi tamaina 1 zerrendak hasi. Beraz, galdutako duzun zatia non zuen benetan egin egunkari n, egunkari-n, egunkari-n sarrera zatitu. [Bideo-erreprodukzioa] -Hori da, beste urrats bat da. Urrats bi, behin eta berriz egiteko batu zerrendak bikoteak. DAVID MALAN: Hm. Soilik audio is coming nire ordenagailuan daudelarik. Dezagun saiatu berriro. -Just arbitrarioki hautatu den - orain lau zerrendak dugu. Argibide aurretik. DAVID MALAN: Ez goaz. -Batzea 108 eta 15, amaituko dugu gora zerrenda-15, 108. 50 eta 4 batzea dugu azkenean, 4, 50. 8 eta 42 batzea dugu azkenean, 8, 42. Eta 23 eta 16 batuz, dugu azkenean, 16, 23. Orain gure zerrendak guztiak tamaina 2 dira. Iragarki bakoitzak lau zerrendak dago antolatuta. Beraz, hasteko batuz dezakegu zerrendak bikoteak berriro. 15 eta 108 eta 4 eta 50 batzea dugu 4 lehenengo hartu eta, ondoren, 15 eta, ondoren, 50 eta, ondoren, 108. 8, 42 eta 16 batzea, 23, hartu dugun lehenengo 8, 16 orduan, eta, ondoren, 23, ondoren, 42. Beraz, orain bi tamaina zerrendak dugu 4, bakoitza dago antolatuta. Beraz, orain bi zerrenda horiek batu ditugu. Lehenik eta behin, 4 hartuko dugu, eta gero hartuko dugu 8, ondoren, 15 hartuko dugu eta, ondoren, 16 eta, ondoren, 23 eta, ondoren, 42, 50, gero, gero, 108. [END bideo-erreprodukzioa] DAVID MALAN: Berriz ere, aldez aurretik abisatu zuen inoiz ukitu bat ematen, kopa bat baino gehiago denbora it haratago aurrera egin ondoren. Beraz, inoiz ez zuen errepikatuz. Beraz, beti zuen alde mugituz, eta hori da gure n ginen. Zergatik ez utzi sortu tira me ko animazioa ikusi dugun bezala, baina oraingo honetan bakarrik bideratua merge sort on. Dezagun aurrera me eta zoom hau hemen ere. Lehenengoa utzi ausazko sarrera bat aukeratu me, handitu honetan, eta ikusi ahal izango duzu, ordenatzeko zer hartu emana, lehenago genuen, batu ordenatu benetan egiten. Beraz, nabarituko lortu duzu erdi edo laurden horiek edo horien kortxeak du Arazo bat-batean guztiak hasteko ona forma hartzen. Eta, azkenik, ikusiko duzu Oso amaiera bam dela, dena batu elkarrekin. Horiek besterik ez dira, beraz, hiru ideia bera hartzen du. Baina gakoa ezagutzeko, besterik ez bezalako haustura eta lehen klasean konkistatzeko, zen erabaki genuen nolabait zatitzea zerbait, big alegia arazoa zerbait espirituz berdinak ordenatu, baina txikiagoak eta txikiagoak eta txikiagoak eta txikiagoa da. Orain beste modu dibertigarrian pentsatzeko moduko horiei buruz, hala ere, ez da emateko berean intuitiboa joan ulertzea da, Ondorengo animazioan. Beraz, hau bildu norbaitek bideo bat da lotutako hainbat eragiketa hainbat soinuak txertatzeko, ordenatu, merge ordenatu, eta besteak beste pare bat. Beraz, une batean, Play hit noa. Minutu bat inguru luze da. Eta, nahiz eta oraindik ere ikus ereduak, gertatzen ari den garai honetan, ahal duzun Horrez gain, entzun nola algoritmo horiek ezberdinean eta lantzean zertxobait ezberdinak ereduak. Hau txertatzeko ordenatu da. [Tonuak JOLASEAN] DAVID MALAN: berriro ere saiatzen ari elementu bakoitzaren txertatzeko tokian sartu. Hau da, burbuila ordenatu. [Tonuak JOLASEAN] DAVID MALAN: Eta sentitzen dezakezu ordenatzeko nola nahiko gutxi lan egiten ari da Urrats bakoitzean. Hau da, zer tediousness soinuak bezala. [Tonuak JOLASEAN] DAVID MALAN: aukeraketa sort hau da, non elementu nahi dugun aukeratu dugu igaro eta berriro eta berriro eta jarriz hasieran. [Tonuak JOLASEAN] DAVID MALAN: This ordenatu batzea da, eta horrek benetan dezakezu hasteko sentitzen. [Tonuak JOLASEAN] [Barreak] DAVID MALAN: Zerbait izeneko gnome ordenatu, eta hori ez dugu begiratu at. [Tonuak JOLASEAN] DAVID MALAN: Hargatik me ikusten, orain, arreta espero duzun bezalakoa dira musika, apur bat badut irrist dezakezu matematika apur hemen. Beraz, laugarren bidea ahal dugun da horiek zer esan nahi duen pentsatu funtzioak baino azkarrago izateko dugun ikusi baino lehen. Eta zaren ikastaroa bada datozen matematika hondo, duzu egia esan, jakin, agian, dagoeneko duzula epe bat Slap daiteke teknika honetan - hots errekurtsibitate, funtzioa nolabait deitzen dio berak. Eta, berriz ere, gogora ekarri merge ordenatu duten pseudocode zen recursive zentzuan merge ordenatu horrek urrats bat sort zen deiari - hau da, berez. Baina, zorionez, mantendu dugulako sort deituz, edo ordenatu bateratzeko, zehazki, on bat txikiagoak eta txikiagoak eta txikiagoa zerrenda dugu, azkenean, hondo out zer deitu dugu esker Oinarri kasuan, hard-kodetuak kasua dela esan zerrenda txikia da, bada, 2 baino gutxiago kasu horretan, bakarrik itzultzeko berehala. Zuen gero, ez dute kasu berezia dela, algoritmoa litzateke inoiz hondoa out, eta, hain zuzen zenuke beti sartu infinitua benetan betiko begizta. Baina demagun nahi izan dugu, orain jarri honetan, zenbaki batzuk, berriz ere, n sarrera tamainan. Eta zuk galdetu nahi nuen, zer inplikatutako guztizko denbora merge ordenatu lasterketak? Edo, oro har, zer haren kostua denboran? Beno, nahiko erraza da neurtzen duten. N 2 baino gutxiago izanez gero, aldiz, parte hartzen duten n elementuak ordenatzeko ere, non n, 2, 0 da. Besterik ez dugu itzuliko delako. Ez dago ez lan egin behar da. Orain, dudarik gabe, agian oso urrats bat edo bi urratsak irudikatu nahi zenbatekoaren lan egiten, baina oso hurbil 0 nahikoa dela Besterik ez naiz lana ez da esanen beharrezkoa da zerrenda oso txikia bada izanarren izango da. Baina kasu honetan oso interesgarria da. Errekurtsiboaren kasuan adarraren zen pseudocode esan bestela, ordenatu Ezkerraldean erdian, ordenatzeko eskubidea erdi, bi erdi batzea da. Orain zergatik, adierazpen honek irudikatzeko gastu hori? Beno, n T, besterik gabe esan nahi du denbora n elementuak ordenatzeko. Eta, ondoren, eskuineko eskua gainean berdin zeinu han, n T banatzen 2 da, eta zer kostu buruz? Ezkerraldean erdia ordenatzeko. N T beste 2 arabera banatzen da zentzuzkoa kostuaren erreferentzia ordenatzeko eskuineko erdia. Eta, ondoren, gehi n? Batzea da. Bi zerrendak, bat galtzen delako tamaina n 2 baino gehiago, eta beste tamaina n 2 baino gehiago, eta, funtsean, ukitu behar duzu elementu horietako bakoitzak, besterik Rob bezala ukitu katilu bakoitzean, eta besterik bakoitzean dugun bezala adierazi Eszenatokira boluntario. Beraz n batuz kaltetan da. Orain, zoritxarrez, formula hau Era berean, bere burua errekurtsibitatean. Beraz, bada, galdera da, n bada, esan, 16, badago 16 eszenatokian pertsonen edo 16 bideo edalontziak, zenbat guztira urratsak ez du haiek ordenatzeko hartu merge Ordena? Egia esan, ez da begi-bistakoa erantzun bat, orain, ordenatzeko duzulako errekurtsiboki erantzun formula hau. Baina hori OK, let me delako proposatzen Hori egin dugu honako hau. Parte hartzen duten 16 pertsona ordenatzeko edo garai 16 cups da irudikatzen egingo Oro har, T gisa 16. Baina hori berdin, horren arabera, gure Aurreko formula, 2 aldiz zenbatekoa denbora ordenatzeko hartzen du 8 cups plus 16. Eta berriro, gehi 16 denbora batzea da, eta 8 T bi aldiz da denbora ezker erdiko eta eskuineko erdia ordenatzeko. Baina, berriro ere, hori ez da nahikoa. To sakonago batean murgiltzeko aukera dugu. Horrek esan nahi du erantzun behar dugu galdera, zer 8 T da? Beno 8 T 2 besterik ez da 4 aldiz plus 8 T. Beno, 4 T da? 4 T besterik 2 aldiz 2 gehi 4 T da. Beno, zer 2 T? 2 T besterik 1 2 gehi 2 T da. Eta berriro ere, lortzeko moduko gara ziklo honetan itsatsita. Baina buruz hit da hori izenekoak oinarri kasu. Zer 1 T delako, ez dugu aldarrikatzen? 0. Beraz, orain, azkenik, lan atzeraka egin ahal izango dugu. 1 T 0 bada, orain ezin dut joan atzera gora a guy hau bat hemen, eta I can T 0 1 plug. Beraz, horrek esan nahi du 2 aldiz zero berdin da, bestela, 0, gehi 2 bezala ezagutzen. Eta, beraz, oro har, adierazpen 2. Orain, bada, 2 T, zeinen erantzuna hartzen dut 2, entxufatu lerro erdiko, T sartu 4, ematen dit 2 aldiz Gehi 2, 4, 8, beraz. Ondoren, I 8 konektatu nahi izanez gero, aurreko line, ematen dit 2 8, 16. Eta gero, jarraituko dugu gero duen 24, 16 gehituz, azkenean lortu dugu 64 balioa. Orain, eta bera Ordena hitz egiten n idazkera ezer ez da, big O, omega dugun buruz hitz egiten ari dira. Baina bihurtzen da, hau da, 64 hain zuzen ere, 16 sarrera tamaina, saioa oinarria 2 16. Eta hau da, pixka bat ezagutzen, besterik ez bada Uste atzera, eta itzuli egingo nahi duzun azkenean. Hau log 2 oinarria bada, da 2 bezala zer ematen dizu 16 planteatu? Oh, 4 da, beraz, 16 aldiz 4 da. Eta, berriro ere, ez da big aurre honetan bada bat hazy memoria moduko da orain. Baina oraingoz, fedea hartu 16 log 16 hori 64 da. Hain zuzen ere, eta, beraz, erraz hau behatu dituzten egiaztatzeko, baieztatu dugu - baina ez frogatu formalki - merge iraupena duen ordenatu da, hain zuzen ere, n n saioa. Beraz, ez da txarra. Behin betiko baino hobea da algoritmoak ikusi dugu, beraz, orain arte, eta dugu leveraged delako da, bat, errekurtsio izeneko teknika bat. Baina hori baino gehiago interesgarria da, konkistatu eta zatitu kontzeptua. Berriz ere, benetan aste 0 stuff nahiz eta gaur egun batean errepikatutako gehiago sinesgarria era. Orain fun little ariketa, dudan baduzu inoiz egin hori -, eta ziurrenik ez luke, zeren normala moduko jendeak ez dut uste hori egin. Baina google.com eta badut joateko bada Zer ikasi nahi dut errekurtsibitate, Sartu. [Barreak] [Gehiago barreak] DAVID MALAN: Bad txantxa poliki-poliki zabalduz. [Barreak] DAVID MALAN: Badaezpada ere, ez da. Nik ez dut ortografia oker, eta ez da txantxa. Guztiak eskubidea. Azaldu pertsonen ondoan baduzu ez da nahiko klik egin du, besterik gabe. Errekurtsio baina, oro har, aipatzen funtzio bat deituz prozesua bera, edo, oro har, bat zatituz zerbait sartu daiteke arazoa konpondu piecemeal berdin-konpontzeko arabera ordezkari arazoak. Beno, goazen aldaketa engranajeak besterik gabe, une batez. To cliffhangers zenbait amaituko gustatzen zaigu, beraz ezarri hasteko en etapa, hainbat minutuz, Oso erraza da, ideia on - bi elementu trukea da, ezta? Guztiak algoritmo hauek izan gara bikote iragan buruz hitz egiten hitzaldi inplikatzeko batzuk trukea agintzea. Gaur egun, izan zen horietako lortzean by bistaratzen bere aulki eta paseatzea, baina kodean, nahi dugu Just hartu elementu bat array-tik eta plop da beste. Beraz, nola ez, joan egiten gara? Beno, goazen aurrera me eta idatzi azkar programa hemen. Aurrera joan eta egin dut honako hau ere. Dezagun deitzen hau - zer lotura bat deitu nahi dugu? Egia esan, ez. Let me atzeratzeko. Ez dut nahi hori egin cliffhanger oraindik. Fun hondatu egingo da. Egin dezagun ordez. Demagun nahi dut pixka bat idazteko programa, eta, orain, besarkatu honetan errekurtsio ideia. Mota lortu nuen aurretik neure burua han. Honako hau egin behar dut. Lehenik eta behin, azkar estandar bat io.h kontutan, baita cs50.h. kontutan bat Eta, ondoren, aurrera noa eta deklaratzen int nagusia void ohiko eran. Misnamed Nik fitxategia konturatu nintzen, beraz, utzi gehitu besterik ez niri. c luzapena hemen hori bildu ahal dugun bezala. Hasi funtzio hau kendu. Eta funtzioa, idazten, nahiko nahi dut besterik gabe, bat duten galdetzen da zenbaki bat eman eta gero, erabiltzaileak gehitzen arteko zenbaki guztiak zenbakia eta, esan, 0. Beraz, lehenengo aurrera noa eta deklaratzen int n. Ondoren, kode batzuk kopiatu dut pixka bat erabiltzen dugu. Zerbait egia da bitartean. Itzuli nahi dut une batean. Zer egin nahi dut? Printf positiboak esan nahi dut osokoa mesedez. Eta, ondoren noa esan n lortzen lortu int. Beraz, berriro ere, boilerplate kodea batzuk dugun erabiltzen aurretik. Eta hau egin nahi dut n 1 baino gutxiago da. Beraz, hau izango dela bermatzeko, erabiltzaileak ematen dit oso positibo bat. Eta, gaur egun, honako hauek egin behar dut. Sortu gehitzeko zenbakiak guztia nahi dut 1 eta n eta, edo 0 eta n, equivalently, guztira batura lortzeko. Big sigma ikurra, beraz, agian duzula gogoratzen. Beraz, hori egin deituz lehenengo noa Sigma izeneko funtzio bat, pasatuz n, eta ondoren noa printf esan, erantzuna da bertan. Beraz, azken finean, eta lortu dut erabiltzailearen INT. Positiboa dela ziurtatzeko dut. Aldakorra izeneko erantzun deklaratzen dut int mota eta denda bertan bueltan sigma balioa, n sarrera gisa pasatuz. Eta gero, inprimatzen ditut erantzuna. Zoritxarrez, nahiz eta sigma soinuak zerbait izan liteke bezala du math.h fitxategia, bere adierazpena, Egia esan, ez da. Beraz, hori da Ados. Hau ezartzeko ahal izango dut neure burua. Izeneko funtzio bat ezarri nahi dut sigma, eta bere bat hartzen joan Parametro - dezagun, besterik ez deitu m, besterik beraz, desberdina da. Eta gero, hemen, esan nahi dut, Beno, m 1 baino txikiagoa bada - hau da, Oso programa izanarren. Beraz, aurrera noa, eta berehala itzultzeko 0. Besterik ez da, ez du zentzurik sortu gehitzeko guztiak 1 eta m m bada arteko zenbakiak da berez 0 edo negatiboa. Eta, ondoren, aurrera noa egin eta hau oso iteratively. Zahar-eskola moduko hau egin nahi dut, eta aurrera noa eta esan dut joan deklaratzeko batura 0 izango da. Ondoren, behar dut int begizta bat - eta gure etortzeko da egin me banaketa kodea, beraz, kopia bat izan dezazun etxean. int 1 lortzen i buruzko baino txikiagoa edo berdina da m i. i Plus. Eta, ondoren, honen barruan begizta for - ia ez gara - batura batura gehi 1 du. Eta, ondoren batura itzuliko naiz. Beraz, hau egin nuen, azkar, nahiko Admittedly. Baina, berriro ere, funtzio nagusia da nahiko erraza, kodea dugu oinarritutako idatziak, beraz, oso urrun. Begizta bikoitza erabiltzen du positibo bat lortzeko erabiltzailearen INT. Pasatzen dut eta gero int duten funtzio berri bat izeneko sigma, eta deituz, berriz, n. Eta itzulitako balioa, erantzuna gorde dut beltza koadroan egun sigma bezala ezagutzen da, aldagai batean izeneko erantzuna. Ondoren, inprimatu dut. Orain, bada, jarraituko dugu istorioa, nola sigma inplementatu? Honako hauek ezartzea proposatzen dut. Lehenik eta behin, akatsak egiaztapena pixka bat Ziur erabiltzailea ez da hori egiteko nirekin eta aldatzeari batean igaro negatiboak edo 0 balioa batzuk. Ondoren, aldagai bat deitu deklaratzen dut Laburbilduz eta ezarri 0. Eta orain, berdin i mugitzeko hasten naiz 1 bidea sortu eta m guztiak barne, nahi dut, guztiak ere hartzen duelako m bidez batetik zenbakiak, biak barne. Eta honen barruan begizta egiteko, egin dut batura lortzen edozein dela gaur egun, gehi i balioa. Plus i balioa. Bat alde batera bezala, nik ez baduzu ikusi aurretik, ez dago sintaktiko azukre batzuk linea honetan. Hau berridatzi ezin dut gehi berdin i gisa, besterik gabe, neure burua salbatzeko gutxi zanpatze bat eta pixka freskoago bat bilatzeko. Baina hori da dena. Funtzionalki da gauza bera. Zoritxarrez, kode honen oraindik ez dira bildu behar. Exekutatu dut sigma 0, nola goizeko bada Joatea lortu nahi dut oihu? Zer egin behar dut gogoko? Ikusleak: [INAUDIBLE]. DAVID MALAN: Bai, ez nuen deklaratzeko goian, eskubidea sortu funtzioa? C motako ergelak, hau da soilik zer egin behar duen esango dizu, eta zuk izan da egin behar duten. Eta beraz hit dut Idatzi hemen bada, noa lortu sigma buruzko abisu bat inplizitu aitorpena. Oh, ez da arazo bat. Igo dezaket goian, eta I can esan, guztiak eskuinera, minutu bat itxaron. Sigma funtzio bat itzultzen da int bat eta bat espero sarrera, koma gisa int. Edo funtzio osoa jarri izan dut nagusiak, batez ere, baina, oro har, nahiko nuke aurka gomendatzen, delako Niza beti nagusiaren goialdean, beraz, at murgiltze eskuineko ahal izango duzu eta ez dakit zer bat programa nagusia irakurriz lehen egiten. Beraz, orain utzi pantaila garbitu zidan. Remake sigma 0. Badirudi guztiak ikusteko. Let sigma 0 abiarazi dit. Urte arteko hazkunde positiboa. Eman dut kopurua 3 it simple mantentzeko. Beraz, niri eman beharko 3 gehi 2 gehi 1, beraz, 6. Sartu, eta hain zuzen ere, 6 zait. Zerbait handiagoa egin ahal izango dut - 50, 12, 75. Just tangente bezala, egin dut zerbait benetan handi bat bezala irrigarri zenbakia, Oh, benetan lan out - eh, ez dut uste hori eskuinera. Ikus dezagun. Dezagun benetan berarekin mezurik. Hori arazo bat da. Zer gertatzen da? Kodea ez da txarra dela. Oraindik ere ez da lineala. Txistu ona efektu bat da, baina. Zer gertatzen da? Ziur entzun ez badut ere. Beraz bihurtzen da - eta hori alde batera utzi da. Hau da, ez dute core errekurtsio ideia. Bihurtzen da, naiz saiatzen ari delako irudikatzeko kopuru handi bat, besteak beste, gehienak Agian ari misinterpreted ez da zenbaki positibo gisa C arabera, baina negatiboa. Ez dugu horri buruz hitz egin zuen, baina bihurtzen ez out negatiboak dira zenbakiak Horrez gain, munduko positiboa zenbakiak. Eta horrek esan nahi du dezakezu irudikatzeko negatiboa funtsean, bat erabili duzu bereziak bit adierazten negatiboak positiboak baino gehiago. Pixka bat gehiago, hori baino konplexuagoa da, baina oinarrizko ideia. Beraz, tamalez, C bat bada nahasia benetan zentzua gisa bit horien, oh, hau negatiboa zenbakia, nire begizta da Hemen, adibidez, ez da inoiz amaitutzat eman behar dugu. Hala bada, benetan ziren zerbait inprimatzeko behin eta berriro, nahiko genuke ikusi osoan asko. Baina, berriro, eta hau puntua da gainera. Hau da, benetan moduko bat besterik ez du jakin-min intelektuala duten ikusiko dugu azkenean, atzera. Baina, oraingoz, hau zuzena da ezartzeko bere gain hartzen badugu duela Erabiltzaile ints emango duten ints barruan sartzen dira. Baina kode honek, sinceramente aldarrikatzen dut, egin ahal izango dira, beraz, askoz gehiago, besterik gabe. Eskuan helburua da zenbaki bat hartu nahi izanez gero, m bezala, eta gehitu igo guztiak da eta 1, edo alderantziz arteko zenbakiak 1 artean, eta, diotenez, I Ideia hau batu hori maileguan hartu ahal izango dut sort izan zen arazo bat hartuz tamaina hori, eta zatitu zerbait txikiagoa da. Agian ez erdia da, baina txikiagoa, baina representatively berdinak. Ideia bera, baina txikiagoa arazo bat. Beraz, benetan ari naiz - utzi fitxategi hau gorde me baten bertsio desberdinak zenbaki batekin. Bertsio hau deitu dugu 1 ordez 0. Eta ezin dut hori benetan erreklamatzeko dut reimplement hau ordenatu honen kontuan-flexiones bidea. Zati utzi bakarrik noa. Esan dut m gutxiago bada baino, edo are berdina 0 - Besterik ez naiz pixka bat izango da gehiago anal denbora honetan - Nire error with egiaztapena Aurrera joan eta 0 itzuliko naiz. Hau da arbitrarioa. Besterik ez naiz, besterik gabe, erabakitzeko Erabiltzaileak ematen dit zenbaki negatiboa izan, naiz 0 itzuliz, eta irakurri behar dute dokumentazioa xehetasun gehiago. Bestela - nabarituko zer egin behar dut. Bestela m gehi itzuliko naiz - zer da m sigma? Beno, gehi m m ken 1 sigma, plus m ken 2, gehi m 3 kenduta. Ez dut nahi hori guztia idatzi. Zergatik ez punt dut? Errekurtsiboki deitzen neure burua apur batekin txikiagoa arazoa, puntu eta koma, eta deitu egun bat? Eskuin? Orain, hemen ere, sentitzen duzu, edo agian kezkatu hori infinitua begizta naizela da inducing, horregatik ezartzeko dut deituz Sigma Sigma arabera. Baina hori ezin hobeto OK, dudalako pentsatu aurretik bat gehitu lerro horrek? Ikusleak: [INAUDIBLE]. DAVID MALAN: 23, 26, eta horrek nire egoera bada. Zer buruzko polita delako kenketa hemen, gorde dudalako ematea sigma txikiagoa arazoak, txikiagoa arazoak, txikiagoa da - ez da tamaina erdia. Bakarrik haurra urrats txikiagoa da, baina hori da Ados. Azkenean, lan egiten duelako dugu Gure behera 1 edo 0 bidea. Eta behin 0 hit dugu, Sigma ez berak deitzea gehiago joan. Berehala itzultzeko 0 da joan. Beraz, eragina, ordenatu haize badituzu zure kontuan, m gehi gehitzeko m ken 1, gehi m ken 2, gehi m ken 3, gehi dot, dot, dot, m ken m, azkenean, 0 ematen du, eta efektua da, azken finean, guztien gehitzeko gauza horiek elkarrekin. Beraz, ez dugu, errekurtsio batera, arazoa konpondu dugu ezin konpondu aurretik. Izan ere, bertsio hau 0, eta behin data arazoa, izan solvable begiztak egiteko bakarrik erabiliz, edo, aldiz, begiztak edo antzeko eraikuntza. Baina errekurtsio, I daresay, ematen digu pentsatzeko beste modu bat arazoak, beraz, bat hartzen badugu dezakezu arazoa, banatu zerbait tik zertxobait zerbait handi samarra sartu txikiagoa, hura konpondu ahal izango dugu aldarrikatzen dut agian pixka bat gehiago dotore dagokionez diseinua, kode gutxiago, eta, agian, are gehiago, arazoak konponduko lukeen gogorragoa izango da, azkenean dizkizugu gisa ikusten, guztiz iteratively konpontzeko. Baina cliffhanger egin ditudan nahi digu utzi behar izan zen hau. Let me aurrera eta ireki fitxategi bat sortu du - benetan, let me joan eta egiteko benetako azkar honetan. Dezagun aurrera me proposatu eta honako hau. Gaur egungo kodearen artean fitxategi hau da hemen. Ko hau hemen, noswap. Beraz, hau ergelak programa txiki hori da Sortu whipped dut erreklamazioak egin honako hau. Nagusian, deklaratzen lehen bat int x deitzen da eta esleituko 1 balioa. Ondoren, int y bat adierazten du, eta esleituko da, balio 2. Gero inprimatzen zer x eta y da. Gero, esaten du, aldaketa dot dot dot. Ondoren deituz funtzio bat dioen izeneko swap, x eta igaro y, ideia den espero duten x eta y atzera etorriko da desberdina da, kontrakoa. Ondoren, trukatu aldarrikatzen da! harridura puntu batekin. Gero, bistaratzen da, x eta y. Baina bihurtzen da hau oso simple manifestazio behera Hemen da, benetan, akatsak. Nahiz eta aldi baterako geratuko naiz aldagai eta aldi baterako bat jarriz Ondoren, naiz kentzea b-ren balioa bat - sentitzen den arrazoizkoa dut dudalako gorde temp baten kopia bat. Ondoren b eguneratu dut berdina edozein dela aldi baterako izan zen. Shell bat mugitzeko moduko joko honetan b sartu eta b bihurtu hau erabiliz erdi-man izeneko temp sentitzen primeran arrazoizkoa. Baina hau aldarrikatzen dut nik kodea, orain bezala, ez dut egingo - let me aurrera eta itsatsi hemen. Noswap.c hau deituko dut. Eta izena dioen bezala, hau ez da zuzena programa bat izango da. Egin noswap. / Swap ez. x 1, y 2, trukea, trukatu. x 1, y 2. Hau da, funtsean, oker, nahiz eta badirudi, nahiz eta ezin hobeto niretzat arrazoizkoa. Eta ez dago arrazoi bat da, baina ez gara arrazoia argitzeko, besterik gabe joan. Oraingoz cliffhanger bigarren dut nahi utzi ahal izateko, hau da, beti kupoi kodeak On mota deialdia. Gure egunetan berandu batera, aurten berrikuntza du eragin ez hutsala zenbaki bat galdera izan zen, Ez da gure asmoa. Kupoi kodeak hauen asmoa, Horren bidez, nahi duzu arazoa zati ote ezarri hasieran, horrela, aparteko egun bat lortzean, izan zen benetan guys laguntzeko laguntzeko hasieran, ordenatu hasteko yourself duzu incentivizing arabera. Laguntzen zama banatu gurekin zehar bulego orduetan, beraz, hobe dela Irabazi-irabazi moduko bat da. Zoritxarrez, nire uste dut jarraibideak ez dira, orain arte, oso argia da, beraz, Itzuli nintzen, asteburu honetan eta eguneratu , handiagoa bolder testu batean zehaztutako azaldu horrelako balak. Eta besterik esateko gehiago publikoki arabera lehenetsia, arazo multzo daude ondorioz, osteguna Eguerdian, curriculumaren arabera. Hasten baduzu hasieran, parte akabera Asteazkena ezarritako at 12:00 arazoa PM, zati hori kupoi bat erlazionatzen kodea, ideia ditzakezun zabaltzeko Zure epea P ostiralera arte ezarri. Hau da, apur P zati txiki-txiki bat off ezarri nahi du, normalean, zer da erlatiboa handiagoa den arazoa, eta erosi zeuk aparteko egun bat. Berriz ere, lortzen duzu pentsatzen arazo multzoa, lortzen duzun bulegoko ordu lehenago. Baina kupoi kodea arazoa da oraindik beharrezkoa bada ere, ez duzu aurkeztuko du. Baina, hau da, egunkariak. (Stage xuxurla) Eta Folks horiek utzi goiztiarrak dira damutuko botako. Dira balkoian Folks. Dut Folks, aldez aurretik barkamena eskatzen an arrazoi izango da balkoitik besterik gabe, une batean garbitu. Beraz, zorioneko gaude bat izatea CS50 en ohia buru irakasteko bekadun at dropbox.com izeneko enpresa bat. Oso eskuzabal dute dohaintzan bat kupoi kodea hemen hau askoz espazio, hau da, batetik sortu Ohikoa 2 gigabyte. Beraz, zer pentsatu nuen honetako genuke egin Azken ohar Giveaway egin da pixka bat, Horren bidez, besterik gabe, une batean, agerian izango dugu irabazlea eta nork kupoi bat dauka kodea ahal izango dituzu, gero, beren joan web, idatzi, eta voila, get asko gehiago Dropbox zure espazioa tresnaren eta zure fitxategiak pertsonalerako. Eta lehen, nork parte hartu nahi Zozketa honetan? Ados, orain egiten are gehiago da dibertigarria. Pertsonaren 25 gigako honetan jasotzen kupoi kodea - hau da, orain arte gehiago berandu baino sinesgarria egun, gaur egun, agian - ko nor da baten gainean eserita dago eserlekuaren azpian kuxin den ez dago kupoi kodea duten. Orain ikusten azpian zure eserlekua kuxin. [Bideo-erreprodukzioa] -Bat, bi, hiru. [Garrasi] You-auto bat lortzeko! Auto bat lortuko duzu! DAVID MALAN: ikusiko dugu Asteazkenean duzu. You-auto bat lortzeko! Auto bat lortuko duzu! Auto bat lortuko duzu! Auto bat lortuko duzu! Auto bat lortuko duzu! DAVID MALAN: Balkoia lagunok, etorri behera hemen, aurrean, non estrak behar dugu. Denek-auto bat lortzen! Denek auto bat lortzen! [END bideo-erreprodukzioa] Narratzailea: Hurrengo CS50 At - HIZLARIA 5: Oh my Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh - [UKELELE antzezlanak]