HIZLARIA: Ondo da, hau CS50 da. Hau astean hiru amaiera izango da, eta gero Ez baduzu aprobetxatu dagoeneko, Ezagutzen ez dagoela bazkaria izango da Ostiral honetan ohikoa, non gisa elkarrizketa ona gozatu ahal izango duzu eta Fire eta Ice at elikagaien CS50 batzuk dituzten langileei eta ikaskideei. URL hau hemen burua. Orain gogora ekarri ahal izango duzu, edo bestela, Baliteke izango laster ezagutu, gauza horiek hemen, ematen dira amaieran klaseak askotan seihilekoan. Proba orokorrak deiturikoak liburu urdina, eta bertan, zure erantzunak azterketak idatzi duzu. Orain hemen daukat 26, besteak beste, liburu urdina, horietako bakoitzean idatzita dagoen izen bat, A Z. bidez Eta hain zuzen ere, izen horiek simple, A daudela Z. bidez Eta bat gaur esku artean helburuak da zer jarraitzeko izango da hasi zen astelehenean dugu, eta hori ez da Hainbeste kodea begira, baina benetan ideiak eta arazoak konpontzeko begira. Helburuetako bat eta Ikastaro honen promesak da zuk gehiago pentsatzen irakasteko arretaz, gehiago metodikoki, eta arazoak konpontzeko ere modu eraginkorrean. Eta, hain zuzen, benetan egin ahal izango dugu nahiz eta kode-lerro bat ukitu gabe. Beraz, elefante pare bat daukat up hemen gaur, laranja eta urdina, boluntario bat eskuratu ahal izango bagenu, agian urrunago ohikoa baino back from. Nola bertan buruz, behera etorri dira. Horren helburua da ahal izango da lagun plus administratzeko azterketa hau hemen. Zein da zure izena? IKUSLEEN: Mary Beth. HIZLARIA: Mary Beth, goazen gora. Let mikrofonoa get me hemen zuretzat. Niza zu ezagutzeaz. IKUSLEEN: Niza zu ezagutzeaz. HIZLARIA: Ondo da, beraz, nik egin Hemen Z bidez liburu bat urdina, eta naiz duten asmoa dut Ikasle bat izan nuen, eta zertxobait ausaz ari dira datozen Hiru orduko azterketa-bloke baten amaieran, beraz ari bukatzen dute batzuetan hau bezalako erdi-ausaz. Orain zure une bat besterik ez da lan va hau da, benetan, nola lortuko dute jolasten gaurkoan ere amaieran klasea, ziurrenik. Zure lana orain arte izan nahiko joan, Besterik gabe, guretzat liburu urdin horiek ordenatzeko A-tik Z. bidez IKUSLEEN: Oh, hau da, betiko hartu du. HIZLARIA: Eta ikusten dugu egin duzun bezala, presioa ez. IKUSLEEN: Ez, presio edo ezer ez. HIZLARIA: Eta ondo pasatzeko, dezagun jarri tenporizadorea. IKUSLEEN: Beraz, askoz fun, hainbeste fun. HIZLARIA: mic eduki ahal dut zuretzat. Ondo da, nik besterik bikoiztu egin dugu gure abiadura. Beraz, bien bitartean, utzi planteatzen me zer da Mary Beth galdera izango da hau da, zer da zuen egiten, nola da hau konpontzeko joan zen? Eta hain zuzen ere, agian ez dute Zerbait buruz inoiz pentsatu hain erraza denean jaso ahala 26 Honen antzeko liburu bat egin dute, Horiek egin eta natural bat izatea horiek ordenatzen. Zein da prozesua benetan erabili duzula? Nahiko ausazko besterik lehena ikusten duzu biltzea eta jarriz bere lekuan? Ez lehen, zure eskuak mugitu duzu orduan A B bila? Ez bat begirada bat hartu duzu aldamenean horietako bikotea eta besterik esateko, minutu bat itxaron, hau ez da eskubidea, eta ondoren trukatu ordena? Dagoeneko ikusi astelehenean dugu ez dagoela modu zenbaki bat eta bertan hau egin ahal izango dugu, eta hain zuzen bezala amaiera gertu dugu hemen, Ohar agian hartuko nuke zer of Mary Beth egiten ari da. Pila batzuk badirudi ditugu, bat handiagoak bat, txikiagoa, hiru direnak. IKUSLEEN: horiek ordenatzen ari naiz denean bi letra aurkitu dut ezagutzen dut elkarrekin dira sekuentzia batean, Horiek jarri dut elkarrekin, beraz, ez dut mantenduz kezkatu liburuak ilara oso baten arrastoa. Besterik, oh, A lehen da, Nik pila hau hemen. HIZLARIA: Beraz, ia bezala bat puzzle pieza dela eskuineko forma behar datoz bat elkarrekin. IKUSLEEN: Pretty much, bai. HIZLARIA: OK, bikaina. Eta orain, horietako bakoitzean pila ustez ordenatuko da? IKUSLEEN: Bai. HIZLARIA: Ondo da, A Z. All bidez eskuinera, zorionak, egin zenuen. Zure aukera daukazu. Blue? Ondo da, eskerrik asko horren. Beraz Mary Beth zuen proposa zer bere planteamendu zen, baina zer hurbilketa bat da, nola duzu agian gauza horiek ordenatzeko buruz? Zer egin nahi duzu? Errekorra beat zatekeen minutu bat eta 50 edo segundo, plus direnak ahaztu dut zenbatu. Zer egin nahi duzu? Bai? IKUSLEEN: Hartu pila. Hasieratik hasi. Begiratu zure paperak. Eta inork goiko handiagoa bada baino, agian, dira, bat beheko aldean dagoen handiagoa, orduan piztu zien. HIZLARIA: OK, beraz, hasita goiko eta beheko aldean, eta, ondoren, lan your way barrurantz duten bezala, horien aldaketa? Ados, beraz, antzeko apur bat burbuila sort espirituz, baina muturren aukeratuz Ez ondoko bikoteak. Baina laburra da, ez dagoela ziur aski modu ezberdinak sorta bat hau egin ahal izan genuen, eta Egia, uste dut mota horretako Pare planteamendu bat onartu zuen, ezta? Lau pila ordenatuko moduko egin duzu, eta orduan eraginkortasunez batu itzazu elkarrekin. Eta hori da, daresay, beste Teknika guztira. Ez duzu pila handi bat bezala tratatzen, arazoa banatzen dituzun lau quads sartu, , izango da eta ondoren, nolabait bada batu zien azkenean. Beraz, kontuan hartu dezagun, azken finean, hau nola bestela ez genuke. Nozioa formalizatu dugu burbuila sort azken denbora, eta burbuila sort gogoratzen zen bat algoritmoa, bistaratzen dugu Zortzi sortu hemen zure ikaskideekin batera, itxuraz ausaz hasiera batean ordenatuta. Eta gero pairwise erabaki genuen, gero Bi elementu barrutitik kanpo daude, Besterik gabe trukatzeko. Beraz, lau eta bi dira jakina, ordena, beraz, bi ikaskideekin horiek posizioak piztuta. Eta gero errepikatu lau eta sei ginen, ondoren, sei eta zortzi, iterazio bakoitzean, eskuinera mugitzen. Beraz, emandako zortzi pertsonak, pairwise zenbat konparazioak zuen bitartean oinez egin nuen Ezkerretik eskuinera, besteak beste, iterazio batean? Zenbat konparazioak? Zazpi, ezta? Han zortzi bada delako Jende baina bikotea duzu horiek eta zuk mugitzen mantentzeko hop eskubidea inork, Ez bazara zortzi izan da joan konparazioak delako ezin duzu alderatu beraren aurka elementu bat, edo litzateke besterik izan pointless, beraz, behar duzu zazpi. Edo gehiago, oro har, bada n jendea behar dugu, ditugun Egin n ken 1 konparaketak burbuila ordenatu daitezke. Beraz, kontuan hartu dezagun orain nola ona edo burbuila txarra sort benetan izan zen, eta saiatu geure burua hiztegia emateko dituzten hau bezalako kritika algoritmoak zein, eta laster gure. Beraz bitartez lehen mendatean burbuila ordenatu, lehen aldiz Eskuineko zehar ibili da ezkerretik dut etapa, eraman ninduen n ken 1 konparazioak. Eta hori izango da nire neurri unitatea, ezta? Mota nintzen hitz egiten eta paseatzen, zertxobait azkar, zertxobait motela, beraz, nire segundo kopurua kontatuta Ez da bereziki kontatzea, baina kopurua zenbatuz Eragiketaren eta astelehenean egin nuen, Bi pertsona alderatuz, hori sentitzen neurri unitate polit bat bezala. Beraz, n ken 1 egoteagatik, lehen aldiz, baina gero zer gertatu zen gero? Zer da bat pass bat hankaz bestela Unsorted zerrenda baten bidez? Zer egin dezake elementua buruzko me esango dizu nork han modu guztiak izan zen? Bai? Hori elementu handiena izan zen, ezta? Zenbakia zortzi, nahiz eta zuen arren Hemen hasi zen, denbora dut behin aldean bere kontra bizilagun bat, berak mantendu sortu bubbling eskubidea eskuko zerrendaren alde. Eta hain zuzen ere, hori da, non algoritmoa bere izena du. Orain logika horren arabera, zenbat konparazioak Behar egin du bigarren aldiz egin dut Pass hori egin dut ezkerretik eskuinera? n ken 2, ezta? Besterik ez litzateke izango alferrik galtzen nire denbora badut konparatuz zortzi norbaiten aurka mantentzeko bestela badakigu delako leku egokian zegoen. Beraz, apur bat optimizazioa, beraz, hurrengo pass da izan plus n ken bi urrats egingo, non n pertsonen kopurua da. Orain motatako estrapolatu ahal izango duzu, nahiz eta ez bazaude, ordenagailu zientzialari bat, nola bukatuko du. Algoritmo honen amaieran, zentzuzkoa lortu duzun besterik konparaketa bat utzi. Mota konpondu behar duzu zerrendaren hasieran kasu bitan eta bat barrutitik kanpo daude eta bat eta bi izan beharko luke, beraz, hau ipurdiak out at plus 1 final alderatuz. Orain dot, dot, dot uhinak mota da, Xehetasun juicier batzuk eskuetan, baina dezagun besterik aurretik eta errazteko. Gogoratzen baduzu, goi-tik eskola, Egia, zuk asko math liburuak izan zuela apur bat Cheat fitxa azala edo on- Atzeko estalkia dela erakutsi duzu like zer serie summations hau da, azken finean erantsia sortu ahal izateko. Kasu orokorrean esanda, bat baduzu n aldagai, eta hain zuzen ere, hau, begiratu baduzu at your eskola zaharra matematikako liburu, zuk ikusi nahi hau benetan gehitzen batura hau hemen, n aldiz n ken 1 guztietan 2 banatuta. Beraz, oraingoz utzi zeintzuk besterik me hau da, egia, beraz, fede-jauzi baten gainean, hori da hori zer batzen gehienez, eta ezin izan dugu frogatzeko kasu orokorrago batean. Baina orain utzi zabaltzeko en hau. Hargatik biderkatu hau, beraz, n karratu, ken n, 2 arabera banatzen da. Hori da benetan n karratu, minus n 2 baino gehiago 2 arabera banatzen da,, beraz, horrek guztiak polita eta interesgarria da. Baina zer dugu bada gertatzen orain plug-in balio bat? Demagun ez nuen zortzi jendea, baina esan milioi bat. Eta milioi bat besterik ez delako kopuru nahiko handi bat da, dezagun plug direla eta ikusi zer gertatzen den. Beraz, milioi bat konektatzen dut formula sartu bada Milioi bat karratu lortzeko noa, 2 arabera banatzen da, ken bat milioi, 2 banatuta. Orain zer hori berdinak joan? Beraz, 500 milioi, ken 500.000. Eta badut benetan egiten matematika dagoela out, esan nahi duen duten sailkatzeko milioi bat burbuila sort dituzten pertsonak me har dezake 499.999.500.000 Azkenean, maldarik eta konparazioak, ari gara estrapolatu. Hori sentitzen nahiko motela, baina Egia sarrera jakin bat neurtzeko hau bezala, ez da kontatzeko duten guztiak. Baina, hain zuzen ere iradokitzen n bezala hori ez da handiagoa eta handiagoa, algoritmo hau lortzen mota sentitzen okerragoa eta okerrago, edo benetan hartako mina sentitzen hasten berredura, n karratu, eta horrek gehitzen nahiko azkar. Eta xehetasun hori ez da Jende galdu, hain zuzen ere Duela urte batzuk, senatari jakin bat izan zen kanpainen, eseri elkarrizketa bat Google-en Eric Schmidt, garai hartan zuzendari nagusia, eta galdera batekin zen erronka askoz bezala gaur esploratzen ari gara. Ikus dezagun begirada bat. [Bideo-erreprodukzioa] -Senator, Zu hemen Google at, eta gustatzen lehendakaritza pentsatzea Lan elkarrizketa bat bezala. Orain, zaila da iritsi presidente gisa lan bat, eta orain rigors bidez ari zaren. Era berean, zaila da lan bat lortzeko Google at. Galdera bat daukagu, eta guk gure hautagaien galderak, eta Larry Schwimmer da. What-- naiz uste duzu guys Txantxetan, hementxe da. Zein da modurik eraginkorrena milioi eta 32-bit-eko osokoak ordenatzeko? -Well-- -I'm Barkatu, maybe-- -No, Ez, ez. Burbuila moduko uste dut joan okerreko bidea izango litzateke. -Come, Nork esan zion hau? Ez nuen ordenagailuan ikusi Zure atzean zientzia. -We've Gure espioiak Han lortu. -Ados, Dezagun eskatu desberdin bat elkarrizketa galdera. [END bideo-erreprodukzioa] HIZLARIA: Beraz, buruz hitz egiten zenbaki jakin arren, guztiak baliagarriak izan ez da joan. Ez da bizitza ikasgai bat burbuila duten It ordenatu, emandako milioi bat sarrera, bezain beste 500 milioi urrats bat beharko du. Ezin duzu benetan orokortu too horretatik aurrera eraginkortasunez eta diseinu ona erabakiak denean programak idaztea. Hargatik zentratu dezagun nola on arren Emaitza hori errazteko genuke. Beraz horia Nik azpimarratu hemen n emaitza karratu 2 arabera banatzen da, beraz, milioi bat karratu 2 arabera banatzen da, eta, ondoren, Azpimarratu dut zer azken erantzuna izan zen Behin off kentzen dugu n 2 banatuta. Eta erreklamazioa naiz egin orain gertatzen ari da, nor demontre zaintzen off kentzen baduzu zahar bat 2 gehiagoko n little denean lehenengoa formula horren parte da, beraz, askoz handiagoa? Bestea nagusitzen da terminoa, n karratu 2 banatuta da, beraz, askoz handiagoa da, argi eta garbi, hala n lortzen milioi bat bezala handiak, dela bertan benetan diferentzia handi bat 500 mila milioi artean egunaren amaieran eta 499.999.500.000? Ez da benetan. Eta beraz, zer goaz egin bezala informatikariak da ordena terminoak txikiagoa alboratu eta hau eta benetan horrelako zerbait hartu besterik errazteko egiten den epe hori da axola. Handiagoa gure datu multzoak lortzeko, handiagoa Gure datu-base lortzeko, web orri gehiago , gehiago bilatu behar dugu lagun Facebooken duzu. N handiagoa lortzen bezala, benetan ari gara to handienetako buruzko zaintzeko joan hala nola, edozein azterketa epe gure algoritmoak performance. Eta ez dut esan nahi, badakizu zer, burbuila sort O big ordena da, n ordena karratu. Ez da zehazki n Nik ikusi dugun bezala karratu, baina benetan zaintzen Termino txikiagoa dutenei buruz, eta Egia, benetan zaintzen zatitzen dugu 2-k, bada? Hori konstante bat besterik ez. Eta 500 milioi versus 250 da milioi benetan aurre big? Besterik ezin dut urtebete itxaron, utzi nire laptop literalki lortzeko bi aldiz azkarrago hardwarean, eta desberdintasun moduko hori besterik ez doa urrun naturalean denboran zehar. Zer ardura dugulako da adierazpena, zatia adierazpen hori aldatu egiten joan gure sarrera handiagoa eta handiagoa lortzen. Eta hain zuzen ere, mundu errealean, hori da gero eta gertatzen ari da gure arazoei sarrera eta algoritmoak dira handiagoa lortzean. Beraz, O big da idazkera izango da, the asymptotic notazioa dugu hori besterik informatikariak azaldu behar bezala erabili errendimendua, edo exekutatzen denbora, algoritmo bat. Beraz, algoritmo alderatu dezakegu idatzizko ordenagailu ezberdinetan pertsona desberdinek, erabiliz funtsean antzekoak metriko batzuk konparazioak zenbaki bezala Oraindik , trukeak kopuruan eginez edo agian egiten ari zaren. Zer ez gara joan Aldaketa denbora kopurua da duen erlojua pasatzen hormaren normalean. Zer ez gara kezkatu joan buruz zenbat memoria gaur egun erabiltzen ari zaren gutxienez, nahiz eta hori beste baliabide liteke neurtzen dugu. Gure analisiak oinarritzeko saiatzen gara oinarrizko eragiketak, direnak, Egia, gehienetan begiz ikusi ahal izango duzu. Beraz, big n O antzeko zerbait karratu, hori, n karratu O aldarrikatzen dut da goiko deiturikoak doazen burbuila sort denbora exekutatzen. Beste era batera esanda, nahi baduzue Ba hori da aldarrikatzen nahi izan zenbat muga goiko honetan algoritmo bat igaro daiteke urrats, nik nahi big n O egon joan kasu honetan, karratu, goi-muga bat. Zer I ordez aldatzen baldin Istorioa ez burbuila sort buruz izango da, baina goiko doazen buruz. Ezin duzu algoritmo bat pentsatzea Dagoeneko at dugun begiratu ditudan horren goi-muga, gehienez denbora edo eragiketak neurtu, esan beharko litzateke mugatzen beharreko ek n, funtzio lineal bat, Ez quadratic bat hori da makurrak? Zer da algoritmo bat Beti hartzen ez gehiago n urratsak, edo nahi baino 2n urratsak, edo 3N urratsak? Bai? IKUSLEEN: aurkitzea zerrenda batean kopuru handiena? HIZLARIA: Perfect, aurkitzeko zerrenda batean zenbaki handiena. Zerrenda bat naiz ematen badu adibidez pertsonak, nor bakoitzari zenbaki bat antolatzen, zer gehieneko kopurua da urratsen me hartu behar da, Pertsona arrazoiz adimendun bat, Zerrenda horretan pertsonaren handiena aurkitu? n, ezta? Kasurik okerrenean ere, bertan dagoelako agian balio handiena izan? Eskuin, amaieran modu guztiak. Beraz, kasu txarrenean Goiko doazen, I might modu guztiak joan behar hemen baino gehiago eta antzekoak izan, Oh, hemen zenbakia zortzi, edo balio hori da, edozein dela ere. Orain besterik ez litzateke izango da ergelak , eskuinera joan mantenduko badut? Gero eta gehiago, elementu bila Horietako azkena ez da bada? Beraz, ziur aski, n goi-muga da. Ez dut behar den hartu Hori baino urrats gehiago. Beraz, zer ordez bada proposatu nuela daude mundu honetan algoritmoek duten hori burutzeko denbora bat dute log n O big mugatzen, log n? Non egin dugu hau ikusi aurretik? Bai? IKUSLEEN: telefono-liburuaren arazoa ere? HIZLARIA: telefono-liburuaren arazoa bezala. Zein izan zen nola neurria askoz denbora edo zenbat malkoak da hartu zuen bezalako norbait aurkitu me Mike Smith telefono liburuan? Izan zen log n aldarrikatu dugu, eta Ohituta bada edota hura izan hazy apur bat zer bat Logaritmo edo adierazgarri izan zen, besterik gogoratzen log n oro har, prozesua aipatzen du, kasu honetan, zatituz erdia zerbait berriro, eta berriro, eta berriro, eta berriro, hala nola egiten duten geroz eta txikiagoa lortzen duten egiten duzun bezala. Beraz, saioa n aipatzen da, ziur, telefono-liburua adibide izateko, teorian bilaketa bitarra, dugunean taula gainean ateak birtualak izan, edo Sean zen denean zerbait bilatzen. Zuen erabilitako bilaketa bitarra bada, log n zenbat buruzko goi-muga izango litzateke duten denbora. Baina hori ere ran algoritmo horiek log n gain hartu zer gako zehatz-mehatz? Zerrendan ordenatuko zen hura, ezta? Zure algoritmoa gaizki bada Zure sarrera ez dago ordenatuta, eta oraindik erabiltzen ari zaren bilaketa bitarra antzeko zerbait agian salto egin delako eskuineko elementu baino gehiago konturatu gabe, hain zuzen ere hor da. Orain zer hau esan dezake, bietako bat O big? Horrek ez du esan nahi zure algoritmoa, bat eta urrats bat bakarrik hartzen du, Esan nahi du, besterik ez da, asko kostatzen etengabeko urrats kopurua. Agian aurten 1, agian, da 10, agian 1.000, baina independentea da arazoaren tamaina. Ez dio axola nola handi n da, Etengabeko denbora algoritmoa Beti urrats kopuru bera hartzen du. Beraz, zer algoritmo bat izan daiteke edo, besterik gabe, hitz egin dugu intuizioa duzula dator beti doa denbora etengabe deiturikoak? Bai? IKUSLEEN: bi zenbakiak gehitu. HIZLARIA: Gehitu bi zenbaki, 2 gehi 2 berdin 4, egin. Beraz, lan egin dezake, zer gehiago? Nola mundu errealean buruz, bai? IKUSLEEN: aurkitzea zerrenda batean lehen gauza. HIZLARIA: lehena aurkitzea Zerrenda bateko elementu, ziur. Nik benetan hitz egiten dugu array dagoeneko buruz, nola lortu aztertzea array baten lehenengo elementua, ez du axola zenbat denbora array C kodea da? Parentesi bezala erabiltzea besterik ez duzu zero idazkera, bam, zauden. Eta hain zuzen ere, array, alde batera utzita, laguntza zerbait oro har, ezagutzen ausazko sarbidea bezala, ausazko sarbidea memoria, literalki ahal duzu delako bat edozein leku salto. Besterik gabe, hau da, are gehiago egin ahal izango dugu Aste zero dugu atzeratzeko ahal denean Scratch egin dugu. Zenbat denbora ez da hartu du esan Scratch blokea exekutatu? Just denbora etengabe, ezta? Esan zerbait, esan zerbait, ez du axola Marratu big mundua nola dagoen, beti da denbora kopuru bera hartu du besterik gabe, zerbait esan. Beraz, etengabeko denbora da, baina zer da flip aldean? Hori izan zen, goiko badu mugetatik kanpo, zer nahi badugu beheko mugetatik deskribatzeko gure algoritmoak exekutatzen denbora? Ia kasu onena bat potentzialki, izango bada, ezin baldintza hauek hoberenak aplikatu arren kasu, kasu txarrenean, batez beste kasu gehiago oro har, baina utzi pilatzen dira, besterik gabe mugetatik txikiagoa orohar. Zer da duela algoritmo bat baxuagoa n urrats lotuak, edo 2n urratsak, edo 3N urratsak? N urrats faktore batzuk, duela loturik bertako txikiagoa. Bai? IKUSLEEN: Burbuila sort? HIZLARIA: burbuila moduko hartzen you txikieneko n urratsak, zergatik? Zergatik da hori? Zergatik behar da hasieratik duzula etortzen senez, egiten du, nahiz eta ez soilik hala ere? Bai? IKUSLEEN: [INAUDIBLE]. HIZLARIA: Zehazki. Ahalik eta eszenatoki onenetan burbuila ordenatu, eta algoritmo asko, Eskuz dut bada zortzi pertsona nork antolatuko dira dagoeneko, inozoak izango litzateke zuretzat, algoritmoa, atzera eta aurrera joan behin baino gehiagotan, ezta? Bezain laster bera zerrendan zehar oinez behin, Jakin behar duzu, oi, egin nuen ez trukeak, zerrenda honetan ordenatuko da, irteera. Baina hori ez da n urratsak egingo. Eta alderantziz, zer da beste horri buruz pentsatzeko bidea? Burbuila sort omega da, , n beraz, hitz egiteko, begiratuz gero delako n baino gutxiago elementuak, zer du oinarrizko arazoa da, ez? Ez dakizu horrela antolatu bada, eskubidea. Agian begirada gizakiak gara zortzietan pertsona eta antzekoak izan, ai, eta ordenatuko, ez zuela hartu me n urratsak, baina egin. Zure begiak, nahiz eta mota nahiz buruz duten ikuspegia eremuan handi bat, begiratu zortzi elementu at duzu, begiratu zortzi pertsona duzu, zortzi urrats eraginkorrean. Eta oinez I osoan zehar bada soilik zerrenda egin, konturatu naiz bai, ordenatuta. I gelditu bada erdibidean, pentsamendu guztiak eskuinera, polita da antolatuz, orain arte, zer dira odds Ez da antolatuz? Hori ez algoritmoak zuzena izango. Azkarrago, baina okerra izatea. Beraz, gaur egun modu bat dugu a mugetatik txikiagoa deskribatzen, eta denbora konstante buruz zer? Zer da duela txikiagoa algoritmo bat loturik bere entzierro bat denbora? Urratsa 1, 2 urrats, 10 urrats, baina konstantea, n independentea, sarrera-tamaina? Bai, berriro. IKUSLEEN: Printf? HIZLARIA: Zer da hori? IKUSLEEN: Printf? HIZLARIA: Printf. OK, ziur. Beraz, urrats kopuru finko bat hartzen du. Eta orain, orain behar dut dugu C kodea buruz hitz egiten ari eta ez Scratch, zerbait bezala esan, printf batera, zaindua izaten hasi behar dugu. Printf delako hartu du sarrera, kate bat da, eta kateak ez teknikoki dute luzera. Beraz, orain arte jaso nahi badugu duzu, ez baduzu axola, Teknikoki printf dela argudiatu genezake du hartzen luzera aldakorreko sarrera bat, eta ziur aski gehiago iraun dezake denbora kate bat inprimatu behar da hau luzea, luze hau baino. Beraz, zer besterik ez dugu kontuan hartu bada sailkatzeko eta adibideak bilatzen? Mike Smith telefonoan zertaz liburu edo bilaketa bitarra orokorrago? Kasurik onenean ere, zer gerta liteke? Telefono-liburua ireki nuen eta, bam, han Mike Smith-zenbakia. Berehala ahal nion deitu. Urrats bat, agian bi urratsak eman zituen, baina etengabeko urrats zortea dut bada. Eta Egia, ikusi dugu Astelehena zure ikaskide eskuratu nahiko zortea birritan segidan. Eta hori konstante izan zen, hain zuzen ere a mugetatik txikiagoa denbora galdera algoritmoa on aurkitzeko horiek itxi atzean kopurua 50 ateak. Orain, bat alde batera utzita, ezagutuko bazenitu bezala bai O big, goi-muga hori, eta omega, beheko lotuak, berean bat dira, eta, formula bera da Parentesi dezakezu, gainera esan, besterik ez fancy, zerbait theta da n edo beste balio batzuen theta-ko. Horrek esan nahi du big O eta omega berdinak dira. Orain aukeraketa sort zer? Dezagun hiztegi berria hau erabili. Aukeraketa sailkatu, zer izan ginen berriro egiten, eta berriro, eta berriro? Atzera eta aurrera joan nintzen bidez zerrendan, nori bila? Txikiena kopurua. Beraz, nola urrats asko, nola konparazioak asko egin nuen ahal izateko, irudikatu egin behar duten Zerrendako elementu txikiena izan zen? n ken 1, ezta? Bat naiz I hasteko besterik ez bada delako eman eta berarekin edo bere alderatuz hasten naiz, orduan benetan hura, hura edo bere, benetan hura, I elementu bakarra parekatu ahal elkarrekin n ken 1 aldiz. Beraz, aukeraketa sort antzera hartzen n ken 1 Lehen aldiz urratsak. Zenbat urrats me hartu du elementua bigarren txikiena aurkitu? n ken 2, nago delako muda izateaz mantentzen dut pertsona bera ikusten ari bada Berriro Nik dagoeneko hautatutako zion bada edo horiek bere eta jarri bere lekuan. Eta hirugarren urratsa, n ken 3, orduan n ken 4. Eredu hau ikusi dugu aurretik, eta, hain zuzen hautaketa ordena, era berean, goiko doazen ditu n karratu sortu egiten dugu summation duten bada. Zein da bere beheko muga, aukeraketa sort? Zauri, zenbat denbora ezinbestekoa aukeraketa Ordena hartu du, astelehenean definitu dugun bezala? Bi aukera proposatzen. Agian n da, orain arte bezala. Agian n karratu da, hura bezala da gaur egun goi-muga gisa. IKUSLEEN: n karratu. HIZLARIA: n karratu. Zergatik? IKUSLEEN: duzu delako definitzeko [INAUDIBLE]. HIZLARIA: Zehazki. Hautaketa ordena definitzen dut, gutxienez, Nahiko inozoa izan zen, mantendu egingo da, elementu txikiena aurkitu. Joan berriro, txikiena elementu aurkitu. Joan berriro, txikiena elementu aurkitu. Ez dago moduko ez dagoela ere optimizatu abortatzeko me ondoren utzi dezake besterik n edo, beraz, urrats. Beraz, hain zuzen ere, hautaketa ordenatu, n omega karratu. Txertatzeko sort, non hartu nuen zertaz nork eman zen, eta, ondoren, hura plopped dut edo bere leku egokian? Ondoren, aurretik, bigarren pertsonan egiten dut, plopped zion edo bere leku egokian. Ondoren, hurrengo pertsona, plopped zion edo bere leku egokian. Iragarki hau: lineala, nolabait esateko. Lerro zuzen bat naiz, naiz ez atzera eta aurrera joan, Inoiz ez dut atzera begiratu benetan, baina zer gertatzen hura txertatu dut edo hasieran sartu bere Zerrendako zuten bezala astelehenean dugu? Zer gertatzen da? Bai? IKUSLEEN: [INAUDIBLE]. HIZLARIA: Bai, hori harrapatzen zen, ezta? Gogoratzen dezakezu ikaskideak, badute ziren edozein mugimendu egiteko bere oinak, eta, operazio bat izan zen. Beraz, bada, ez ziren hiru lagun han eta hemen beste pertsona baita modu han, hau bezalako etapa luze bat, ziur, zuen edo ezin izan zuen besterik oso amaiera joan. Baina bat buruz ari zaren pentsatzen bada ordenagailu eta memoria array bat, Pertsona horiek dira joan baino gehiago nahastu dute pertsona horrek gela egiteko. Eta beraz, n ken 1 shufflings, n ken 2 shufflings, n ken 3 shufflings besterik ez mota nire atzean gertatzen ari, ez nire aurrean lehen bezala, zentzu batean. Orain alde batera utzita, eta gisa dituzu online ikusi ahal izan liteke buruz kuxkuxean hasten bazara ordenatzen, ez da hainbeste hainbat direnak daude, horietako batzuk besteak baino hobeak. Izan ere, bogosort da duten fun bilatzeko mota da. Bogosort multzo bat hartzen du zenbakiak edo karta-sorta bat esan, ausaz shuffles horiek, eta egiaztapen badute ordenatuko ari. Eta horrela ez bada, berriro egiten du. Eta horrela ez bada, berriro egiten du. Hala ez bada, berriro egiten du. Oso ergelak. Eta hain zuzen ere, irakurri nahi izanez gero Wikipedia article bezala, Bere goitizena ergelak moduko da. Azkenean lan egingo du, zorionez, nahikoa denbora eman, baina zenbat denbora duten denbora luzez iraun dezake. Beraz, ezin dut, utzi bada abiadura gauzak Mary Beth adibidez lehenago sortu, a elementu batzuk gehiago izatea, baina bi prozesadoreak gehiago. Bi lagun, duzu bada ez luke axola niri batu. Nola buruz 1 hemen, eta dezagun joan egingo han inork ez? No bat han? Ados. Beltzekin duzu alkandora, bai, goazen behera. Ondo da, zer da zure izena? IKUSLEEN: Peter. HIZLARIA: Zer da hori? IKUSLEEN: Peter. HIZLARIA: Peter, David, politak zu ezagutzeaz. Ondo da, Peter dugu hemen, nahi baduzue hemen baino gehiago mahai gainean, etorri nahi. Eta zein da zure izena? IKUSLEEN: Elena. HIZLARIA: Elena. Ados, politak zu ezagutzeaz. Elena betetzen Peter. Peter, Elena. Eta Andrew behar dugu hemen bai gora, mesedez. Eta zure erronka va karta-sorta bat ordenatzeko izan. Eta lanik izanez gero, bizkarreko txartelak egin beharko lukete, azken finean, egon ordenatuko antzeko zerbait apur bat hau non kluben egin dugu, eta gero palak, eta gero bihotzak eta diamante, bateko bat bezala, king gehienez modu guztiak. Txartelak The naiz emateko egingo dira kantitatean 52 izango da. Ari gara, era berean, joan denbora duzu, une bat besterik ez. Andrew botatzen goaz Pantailan hemen sortu, beraz, egin duzun bezala ikustera. Eta, beraz, hori guztia da are nabarmenago, horiek txartelak lortu Amazon I daude. Beraz, dagoeneko dira ausaz ordenatuta, eta denbora goaz. Eta goaz benetako mantendu da oraingoan, beraz ari gara presio saiatu joan zeren bestela hau lapurtera lortuko azkar. Duzu 52 ordenatzeko jarraitu balute elkarrekin bide batzuk erabiliz elementuak, orain. Eta berriro ere, hauetan ikusi dugun bezala guys zer, azkenean, da bistako bat ekoizteko joan Ondorioz, uste benetan buruz Honela egiten dute bakoitzak egiten ari, nola deskribatuko dezakezu. Berriro ere, horiek direlako guztiak prozesu, algoritmo hartu dugun giza gisa emandako. Baina seguruenik luzea izan duzu intuizioa, luzea duzu, nahiz eta aurretik bat hartuz pentsatu informatikako klasean duzu Honekin intuizioa izan liteke honen antzeko arazoak konpontzeko. Baina behin ezagutzen duzu ereduak eta hasteko dituen urratsak formalizatzeko arazo horiek konpontzeko zaren, aurkitu duten askoz konpondu ahal izango duzu duzu gehiago interesgarri eta konplexua askoz gehiago arazoak azkar. Beraz, ikusleek norbait, zer da Algoritmoaren elementu bat gutxienez hemen erabiltzen ari dira? IKUSLEEN: [INAUDIBLE] HIZLARIA: Zer da hori? IKUSLEEN: palo By. HIZLARIA: palo By. Beraz, lehenengo multzokatu dira diamante guztiak elkarrekin dirudienez, guztia bihotzak elkarrekin badirudi, eta abar, errespetu gabe txartelen zenbakiak da. Eta orain, agertzen dira, esate baterako, izango ratuz, eta kopuruaren arabera. Oso ona. Ondo da, beraz, zer ari den gertatzen izan du azken urratsa, ondoren, hemen? Behin lau jantziak ordenatuko, behar dugu zer egiteko lau pila egin behar dugu ordena bat lortzeko helburuarekin ordenatuko bizkarreko, nahiko besterik gabe? Beraz, horiek berriro batu behar dugu. Beraz, ez da ideia interesgarria dela berriro, daresay, oso intuitiboa are agian ez duzu inoiz izan slapped bada etiketa on-mota hori. Zatituz oinarrizko kontzeptu horrek arazoa ez oraingoan erdia, baina, gutxienez, lau zatitan. Nahiko askoz konpontzeko arazoak funtsean berdin- bata bestearen isolamendua, eta, ondoren, emaitzak batuz. Eta, bikaina, egin. Ondo da, borobil handi bat txalo, badugu gabe. [Txaloak] HIZLARIA: Ez dut ideiarik ere zer dituzu hauekin egin, baina hemen. Eskerrik asko. Beraz, ikus dezagun, bi minutu eta zortzi segundo, Zure erronka nahi izanez gero. Orduan zer da joan izan bat kentzen honetatik duten orokorrago leverage dezakegu? Beno, atzera uste zenbakiak array hau, eta uste orain atzera batzuei pseudocode iraganean dugu idatzizko, eta hau izan zen pseudocode telefono-liburuaren arazoa konpontzeko. Pseudocode I Beraren bidez, modu gehiago metodiko bat izendatuak nola oso intuitibo batean egin nuen deskribatzeko Telefono zatituz giza algoritmoa erdia liburua, errepikatu, errepikatu, errepikatu, dut aurkitu arte Mike Smith bezalako norbait, da, hain zuzen ere bada telefono-liburuan. Baina mota horretako zer deitu dut erabiltzen dut Oso etorriko hurbilketa bat hemen, oharra bereziki line 8 eta line 11. Horiek iteratibo baten ebidentzia dira Planteamendu, begizta hurbilketa bat, hori zehazki duelako jokabidea dute bultzatu. Lerro horiek bai esateko joan linea hiru, eta ahal duzun, mota horretako dela uste zure kontuan bere begi begizta bat izateaz gain. Honez diozu atzera joan ahal izateko urratsa Hiru eta errepikatzeko, berriro, eta berriro, eta berriro. Baina zer Ideia bat leverage badugu hemen ez da azken aldia egin dugula, eta linea 8 errazteko eta 11 lerro eta beren auzokoei besterik honetan, horia bezala. Ez da funtsean laburtzen pseudocode asko, baina funtsean aldatzen Nire algoritmoa izaera. Zer naiz orain esaten 7 urratsean, 10 urratsean, bilaketa da, Mike for Era berean zehatza, baina besterik ezkerrean erdi edo eskuineko erdia. Beraz, beste era batera esanda, bada Hasteko urrats bat naiz, telefonoa hartu liburua, erdi irekiak Telefono liburua, izenak begiratu, Smith artean badago Izen horrek, deitu Mike, beste Smith liburu lehenago bada, zazpi urratsera bilatu Mike utzi liburuaren erdia. Baina mota bezala sentitzen me utziz zintzilik, ezta? Horiz, da an instrukzioa, baina nola egin behar dut bilatu Mike for ezkerrean telefono-liburuaren erdia? Nora bat daukat Algoritmo horrekin dut bilatu dezakezu Mike Smith bezalako norbait? Beno, nik begiradak digu aurpegia. Literalki I berean zehatza erabili ahal programan eraginkortasunez sortu goiko joan berriro eta berriro exekutatzen Kode lerro bera. Beraz, hau sentitu behar, nahiz Definizio zikliko bat apur bat bezalakoa non erantzunez zaren norbait da sort galdetuz galdera galdera bera berriz ere, bezala, zergatik, zergatik, zergatik? Errealitatea da, dugu, gogorra delako kodetuak lerro berezi pare bat, 4 urrats, bertan bada bat, eta 12 pauso, zein eraginkortasunez beste adar bat da, stopgap Neurri horiek dugulako, Algoritmo hau desegin egingo badugu aurkitu Mike, edo ez badugu. Baina, 7 eta 10 urrats orain ere, hemengo zer algoritmo errekurtsiboa bat deitu dugu. Eta errekurtsio da, hain zuzen, ideia indartsu bat burura apur bat lehen at tolestuz da, orain dugu honako hau eskatu ahal izango da. Batu sort azken sort izango duten begiratu dugu at, gutxienez klasean formalki. Eta batez ere, desberdina da horiek azken hiru, eta, zalantzarik gabe, aurrera Azken lau sartzen ditugu bogosort bada. Hemen merge sort pseudocode da. Noiz n elementuen sarrera, beraz, emandako tamaina n array bat, n 2 baino txikiagoa bada, itzultzeko. Beraz, zergatik behar dudala behatu check lehen? Zer inplikazioa duzu entregatu badut array baten luzera n 2 baino gutxiago? Dagoeneko ordenatuko da, jakina, ezta? Zerrendako bai duelako elementu bat, eta hori kenduz ordenatuta, da delako Gauza bakarra ez. Edo, da tamaina zero eta horrek esan nahi du ez ezer ordenatzeko, beraz, naturak ordenatuko da. Ez dago ia ezer txarrik ez dago. Beraz, gure kasuan horrela deitzen da. Hori espiritua antzekoa da zer egin Mike ekin genuen. Mike telefono-liburuan badago, deitu zion. Ez bada zuen han, amore eman. Da base baten kasua deiturikoak, ziurtatu Egunaren amaieran, algoritmo hau egingo du egoera jakin batzuetan gelditzeko. Baina hemen fede-jauzi orain, bestela, ezker elementuen erdia ordenatzeko, ondoren ordenatzeko eskubidea elementuen erdia, eta ondoren batu ordenatuko halves. Eta hemen bertan sentitzen atsegin out copping ari gara. Ordenatzeko Nik zaizu n elementu, eta ez naiz , esaten Ados, ez da ordenatzeko arabera utzi eta sailkatzeko eskubidea. Baina nago, inork esaten dut Beste gauza da, eta hau Funtsezko gaia da dirudiena da intuizio batean beraz, orain arte, Han hirugarren batuz urratsa da hau. Zein are arren Badirudi beraz espirituz mutu, bezalako besterik batu gauzak elkarrekin, badirudi giltza norabidean urrats bat izan nahi du bi arazo reassembly duten ziren, azken finean banatzen erditik. Beraz, batu, ordenatu, egin dezagun hau, duzu bada umore me, manifestazio bat gehiago, besterik ez da, beraz, batzuk ditugu Zenbaki horiekin lan. Ezin dut zortzi estres trukatzeko Zortzi lagunentzako pilotak? Ondo da, nola zu hiru, lau Atal honetan, bost, sei, eta dezagun ere do 7, 8, goazen gora. Ados, bai Ados. Minus 8, han, joan gara plus 1. Bikain. Guztiak eskubidea goazen gora, dezagun azkar eman dituzun zenbakiak. Zenbakia bi, hiru zenbaki, lau zenbakia, kopurua bost, sei, zazpi, eta zortzi. Zortzi egin behar bezala dut oraingoan. Ados, beraz, aurrera ahal izango banu, eta en ordenatzeko jatorrizko ordena utzi atzo izan dugun begiratu Hau atsegin, bada ez litzateke axola. Eta egin dezagun mahai aurrean utzi. Ondo da, beraz, batu sort. Hau da, non egingo da motatako lortzeko interesgarri, egon neure buruari emanez badirudi nuelako Hainbeste informazio gutxiago baitago. Beraz, batu, ordenatu, lehenik eta behin n elementuen sarrera oinarrituz, eta ez bi baino gutxiago da, jakina, ez da zortzi, beraz, lan gehiago egin behar dut. Beraz, gaur egun adimen dugu klase bezala dira orain beste adarrean, horrek hiru urrats esan nahi du. Lehenik eta behin, ordenatzeko behar dut ezker elementuen erdia. Beraz, nola ez naiz joaten hau egiten? Beno, noa motatako adimen zatitzen zerrenda hemen, ez duzu behar fisikoki mugitu, eta ez naiz on bakarra bideratzen joan ezker elementuak hemen erdia. Beraz, nola ez ordenatzeko buruz joan nintzen zerrenda lau tamainaren orain? Zein da nire algoritmoa? Lehen dut egiaztatu da n bi baino gutxiago ez, beraz, aurrera jarraitzeko beste blokea dut berriro. Sort elementu erdia utzi. Beraz, orain berriro, adimen, eta hau da, non asko sortuko behar duzu historia mental, izango bada. Orain ordenatzeko naiz ezker ezkerreko erdia erdia. Ondo da, beraz, gaur egun, nire merge bera deitzen dut Algoritmo ordenatzeko, bi baino gutxiago n? Ez, bi da eta, beraz, ongi ordenatzeko behar dut ezkerreko erdia eta eskuineko erdia. Beraz, hemen, joaten gara ezkerreko erdian ordenatzeko. Zergatik ez duzu besterik Urrats bat aurrera. Zein da zure izena? IKUSLEEN: Darren. HIZLARIA: Dan. Dan urratsez urrats aurrera egin du. IKUSLEEN: Darren. HIZLARIA: Darren, done. Ba Darren edo Dan esan duzu? IKUSLEEN: Darren. HIZLARIA: Darren. Ados, Darren zapaldu du aurrerantz eta orain da zuen ordenatuta. Eta hau da, ia bat inane erreklamazioa, ezta? Ez dut Badirudi lortzera ezer, baina dezagun aurrera jarraitzeko. Orain dezagun eskubidea ordenatzeko me elementuen erdia. Zein da zure izena? IKUSLEEN: Luke. HIZLARIA: Luke. Tira, aurrera egin. Luke emana, ordenatuko ditut. Ezkerreko erdia da orain ordenatuko da eta eskuineko erdia sailkatuta gera, baina berriro ere, ez dago gakoa urrats bat da hemen. Zer hurrengo egin behar dut? Batu ordenatuko halves. Orain ari gara besterik ez dute joan denek atzera eta aurrera modu honetan, motatako behar dudalako scratch espazio batzuk. Ia horiek bezalakoa da guys mahai baten gainean daude, eta gela batzuk behar dut horien inguruan mugitu on. Beraz, naiz batu behar mutilak begira dituzu ezkerreko erdia eta eskuineko erdia. Eta nor, jakina, ezer baino lehen, utzi erdi edo eskuineko erdia? Beraz, eskuineko erdia, beraz dezagun aurrera Luke baino gehiago Darren en jatorrizko posizioan hemen. Eta orain euren ezkerreko erdia batzea ere, Darren da bertan mugitu behar. Beraz, ia bezala sentitzen burbuila moduko efektua, baina nire oinarrizko algoritmoa, oso desberdina oraingoan. Baina orain, non gauza lortu txiki gogaikarriak duzulako adimen atzeratzeko behar non utzi nuen. Besterik ordenatuko halves Nik batu, horrek esan nahi du non nago nire algoritmoa? Eskuineko erdia ordenatzeko behar dut, ezta? , Atzeratzeko baduzu hitzez hitz bideoan ere, ikusiko duzu ikusten duten got honetara dugu Luke eta Darren puntua ordenatzeko ezker arabera ezkerreko erdia erdia. Ondoren, horiek batu ditugu ordenatuko halves, eta horrek esan nahi du, hurrengo urratsa da ordena eskuineko ezkerreko erdia erdia. Ondo da, beraz dezagun hau egin azkarrago. Ondo da, sei, naiz aldarrikatzen dut gaur egun ordenatuko dituzu, goazen aurrera. Zein da zure izena? IKUSLEEN: Adriano. HIZLARIA: Adriano. Adriano orain ordenatuko da. Eta zein da zure izena? IKUSLEEN: Alex. HIZLARIA: Alex orain ordenatuko da. Ezkerreko erdia, eskuineko erdia, zer da azken urratsa? Batu. Nahiko hutsala, hain naiz sei eta batu egingo, urrats bat atzera, zortzi, urrats bat atzera. Eta orain konturatu hau da eramateko erabilgarria, zer da gaur egun ezkerreko erdia buruzko egia zerrenda, nola hasi ginen kontuan hartu gabe? It ordenatuko da. Orain ez da ordenatuko eskema gauza handia da, baina independentean ordenatuko da beste erdiak. Orain zer urrats naiz on I mantendu bada istorioa nola hasi errebobinagarriaren? Orain eskuineko erdia ordenatzeko behar dut. Beraz, orain ari garen modu berean itzuli Istorioaren hasieran, eta egin dezagun gehiago azkar utzi. Beraz, ez dut ordenatzeko joan eskubidea zerrenda osoa erdia. Zein da hurrengo urratsa? Sort utzi eskuineko erdia erdia. Sort utzi erdia ezkerretik eskuinera erdia erdia. Eta zein da zure izena? IKUSLEEN: Omar. HIZLARIA: Omar, aurrerapauso, done. Ezkerreko erdia ordenatuko da. Eta zein da zure izena? IKUSLEEN: Chris. HIZLARIA: Chris, beste urrats bat Aurrera, orain ordenatuko dira duzun. Zer da funtsezko urratsa da orain? Batu. Beraz bat da leku batu dira Hemen, urrats bat atzera balute, eta hiru da joan urrats bat atzera, batzea. Beraz, ezkerreko erdia eskuineko erdia, orain ordenatuko da. Egia, algoritmo hau genuen bezala sentitzen dira modu denbora gehiago alferrik galtzen baino, baina hori egin dugu, bada, denbora errealean, zaitugu ikusi zer takeaways izango da. Orain hemen nago, eskuineko eskuineko erdia erdia, utzi aurretik joan eta ezkerreko erdia ordenatzeko. Aurrerapauso, zer da zure izena? IKUSLEEN: Ramsey. HIZLARIA: Ramsey orain ordenatuko da. Zein da zure izena? IKUSLEEN: Marina. HIZLARIA: Marina da, orain bezala ordenatuta bai, pauso bat aurrera egiten duzun ere. Gakoa urratsa hemen orain batzea da, naiz nire bi zerrendetatik pluck joan, ezker eta eskuin. Bost da lehen etorri da joan, eta zazpi hurrengo etorriko da joan. Eta berriro ere, hau nahita. Izan ere, hartzen ari dira aurrera eta atzera pausoak Ahal den adierazten nahi genuela ez Algoritmo hau egiteko leku gisa erraz burbuila ordenatu, eta aukeraketa sort bezala, eta txertatzeko sort non besterik ez dugu Jende aldaketa mantendu. Literalki moduko bat behar dut scratch paper horretan, Folks horiek jartzea batuz egiten dudan bitartean, eta gero berriro jarri ahal dudan lekuan. Eta hori da gakoa nuen bat erabiltzen ari delako baliabide berriak, espazioan, eta ez bakarrik denbora. Ados, hau harrigarria da. Ezkerreko erdia ordenatuko da, eskuineko erdia da ordenatuko, orain gakoa duten batuz urratsa. Nola ari naiz honetan batu egingo da? Beraz, jarraitu egingo baduzu nire ezkerreko eta eskuineko eskua, Nire ezkerreko eskua seinalatu noa Ezkerreko erdia, nire eskuineko eskua eskuineko erdia, eta orain izan dut urratsa nori ere batu urrats erabakitzeko. Nor jakina dator lehen? Zenbaki bat da. Beraz, zatoz hona, Hemen gure scratch pad da. Beraz, inork, eta aldez zenbaki orain zer nire eskuineko eskua egin dut, Eskuineko eskua mugitu noa urratsa baino gehiago hiru zenbaki seinalatu, eta orain egin behar dut Erabaki bera. Eta benetan stand Eskuinetik Luke hemen ahal izango banu aurrean, hau gure scratch pad delako. Beraz, nor dator hurrengo? Luke dute bi zenbaki batera gara edo Chris hiru zenbaki batekin. Jakina Luke, zenbakia bi, beraz, hona etorri. Baina nire ezkerreko orain joan egon handitzen den Darren diete erreferentzia, eta hemen gakoa kentzen dituzten batuz, hau egiten jarraitu nahi dut, jakina, zuk nolako logika jarraitu. Baina nire eskuak dira inoiz atzeraka joan, horrek esan nahi du, naiz bakarrik inoiz mugitzen Nire batuz prozesua geratzen dira, eta hori funtsezkoa izango da Gure une bat besterik analisia. Beraz, gaur egun dezagun amaitzeko, hau oso azkar. Beraz, hiru datorrena, ondoren, lau datorrena, eta orain bost datorrena, ondoren, sei, eta zazpi, eta, ondoren, azkenik, zortzi. Algoritmo geldoena bezala sentitzen oraindik, baina ez badugu benetan exekutatu era bereko at erlojuaren abiadura, beraz, hitz egiten, bera izan beharko erloju ticking lehen bezala. Zergatik? Beno, dezagun bat Azken emaitza begiratu. Dezagun itzuli hemen, let me tira manifestazio bat ikusmen zer egin besterik ez dugu. Hemen zooma handitzea, honetan Hemen orria, Firefox kontatzea ilarara nahi dugun Koadro honetan,, dezagun burbuila ordenatu esan, dituen orain ondo ezagutzen gara, ordenatu, bertan zegoen, bat zuzenean nahiko, eta gaur egungo orain merge sort, eta horrek gure climactic amaiera izango da. Arrazoia, beraz, hartu zuen askoz gehiago Hemen gizakiak eta niri hitzez da, jakina, urrats bakoitza azaltzeko naiz. Baina zuk exekutatu besterik ez bada hau, askoz atsegin genuen burbuila ordenatu eta hautaketa sort ez begiz bakarrik, zaintza besterik zenbat gehiago eraginkortasunez la aprobetxatuz honetan zatiketa eta konkistatu ahal denean, datu multzo hori aplika daiteke ez baita tamaina zortzi, baina, nahiz eta askoz ere, askoz handiagoa. Sort batu duzu, ondoan ematen dut beste algoritmo hauen alde. Hau da mingarria iritsi azkar, eta amaiera ez da bereziki climactic, amaitzeko besterik ez dute ordenatuta. Baina gakoa kentzen dela Begira zenbat azkarrago batu, ordenatu izan zen, naiz uste baduzu behintzat Mota besterik ez duzu aldatzeari. Azken denbora honetan egiten dugu bada, Dezagun freskatuz honetan, goazen atzera eta aukeratu burbuila ordenatu, eta besterik ez Jaurtiketa, dezagun aukeratu txertatzeko ordenatu, neurri ona. Eta oraingoan, berriro ere, dezagun merge sort aukeratu eta dezagun benetan alboko horiek albo exekutatu. Eta ez da, hain zuzen ere, kasualitate bat. Zer eraginkortasunez egiten dut da dut dut nire sarrera banatzen zatian, berriz ere, eta berriro, eta berriro. Eta ez hainbeste bakarrik ahal duzun aldiz zatitzea zure sarrera halves sartu, utzi eta eskuineko. Zein da formula dela ikusten jarraitzen dugu duen banaketa deskribatzen erdia berriro, eta berriro, eta berriro, eta berriro? IKUSLEEN: Sartu n. HIZLARIA: Sartu n. Baina gero ez dago gakoa beste urrats bat da, Algoritmo hau ez da log n urratsak. Ziren bakarrik bada log n urratsak, arazo bera geundeke non ezin dugu orain arte bezala ziur dena ordenatuta. Gutxi n elementu begiratu behar duzu ziur egoteko n elementu ordenatzen dira, bestela fede-jauzi bat da. Beraz log txikieneko n urratsak, baina gako batuz urratsa honi buruz zer non batu dut nire ezkerreko erdia eta eskuineko erdi eta etapa osoan zehar ibili? Zenbat urrats da Batu nahi duten? Da n, baina ez nuen besterik batu da azken aldian. Habiaratuak deiak horietako bakoitzean, bakoitzaren On habiaratuak bateratzeak horiek, oraindik ere horrela antolatu nuen. Bi mutil hauek, batu nuen orduan, bi hauek mutilak, ondoren, bi mutil hauek eta abar. Beraz batuz nuen berriro, eta berriro. Zenbat aldiz? Beraz, aldi bakoitzean I banatzen du Zerrenda erditik, merge bat egin nuen. Zerrenda zatitzeko erdia, merge bat egin. Beraz bada zerrendan zatituz log n aldiz egin daiteke, eta batuz, azken finean hartzen n urrats, zer da orain goiko izan daiteke lasterketari lotuak gure algoritmoaren denbora? n log n. Eta hain zuzen ere, hori da Hemen lortu dugu. Beraz, sentitzen ikusmen denean ikusten duzun Hiru gauza horiek exekutatu aldamenean n n kontra karratu aurkako n log n karratu. Zein funtsean ikusiko dugu, gaur ez ezik, etorkizunean, askoz azkarrago. Txalo Kopako A mutil hauek egiteko, Horiek saritzea da I estresa pilotak. Dezagun adjourn hemen gaur, eta astelehenean ikusiko dugu.