[Musika jotzen] DAVID J. MALAN: Hau CS50 da. Eta aste honetan, hiru hasiera da. Beraz, lortu dugu zirraragarria asko gaur estaltzeko gauza. Aukera asko egiteko boluntarioen eszenatokian. Eta azken finean, gaur da Ez kodea buruzko guztiak. Baina ideia buruz, eta algoritmoak buruz, eta benetan atzera jarriz batzuk Aste zero ikasitako ikasgaiak, dua oroitzapen, dugu munstrotasuna honetan sartu. Eta zorpetze inspirazio horretatik aurrera, hasteko sofistikatuago konpontzeko arazoak karguen taldeak. Baina lehen, iragarkiak pare bat. Bat, beraz, sartu nahi izanez gero CS50 langileek eta ikaskideekin bazkaria Ostiral honetan, bai hemen eta hasi Cambridge, eta New Haven, mesedez bisitatu ikastaro hamarkadan webgunean, non URL bat aurkitu daiteke. Hitzaldia asteazken honetan izango da Ez hemen Sanders izan. Online izango da bakarrik, beraz, CS50 webgunean melodia, Hemen Cambridge ala edo New Haven baita. Eta gero, arazo bi ezarri dagoeneko zure esku. Oraindik ez duzue atean sartu baduzu, aukera ematen dit biziki idatzitako iradokizun eskaintzeko hori, batez ere, gaur egun, gisa Arazoaren aldez ezartzen, Benetan nahi duzu orain hasteko, ez bada dabble asteburuan edo jaso aurretik, pixka bat aurreneko go dute Ostiraletan, duzulako egingo da aurkituko Oraindik ez dutela nahitaez per luzeagoa edo gehiago Challenging lortzean se. Nik uste dut hori aurkitu duzue, in general, gutxi gorabehera hartu ohi dute Denbora kopuru bera inguruan. Baina zalantzarik gabe araberakoa da ikaslea, eta bere gainean mentalitatea araberakoa horrekin hurbiltzen. Baina beti, bazoazela lasterka hasteko horma batzuen aurka, eta ari hit zoazen bug batzuk, eta besterik ez zaren Ez ahal izango da gainean uneren batean. Eta izugarri baliotsua da gai izan urruntzen urratsera, itzuli eta hurrengo egunean, bulego orduetan joateko, post CS50 eztabaidatzeko edo antzekoak, egia esan, zure zain. Beraz, kontuan izan hori. Ahalik eta lehenbailehen hastea gauzarik onena egin dezakezu. Beraz, hemen non hasi ginen klasea, aste zero gainetik. Eta ezin boluntario lortuko dugu hemen mikrofono aurkitu me laguntzeko? ONDO DA. Dagoeneko zutik. Goazen sortu. Asmatu hori, nola da lanera joan. Nola deitzen zara? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Goazen sortu. Urte askotarako. ALAN ESTRADA: Nice zu ezagutzeaz. DAVID J. MALAN: Eta hemen bazina aste zero digu, noski. ALAN ESTRADA: I zen. Izan dut. DAVID J. MALAN: Beraz, ezin duzu joan Animatu eta guretzat aurkitu Mike Smith, azkar ahal duzun bezala? Ahal duzun bezain azkar. Literalki arazoa urraketaren erdia behar duzun bezala. ALAN ESTRADA: Um. DAVID J. MALAN: Literalki erdia arazoa urraketaren. ALAN ESTRADA: Oh. Mm. Oso ondo. DAVID J. MALAN: OK. Ona. Eskerrik asko. ALAN ESTRADA: Oso ona. ONDO DA. DAVID J. MALAN: Eta beraz, gaur egun, Nik kraskatu izango duzue dena Arazoaren tamaina erdia. Orain, laurden bat behera gabiltza. Arreta duzu ordaindu behar Horrek, alde ari mantenduz dugu? [Barrez] ALAN ESTRADA: Bai, I think-- DAVID J. MALAN: Zer atalean gara? ALAN ESTRADA: mufflers, beraz. DAVID J. MALAN: OK. Baina Mike Smith va to Mufflers ondoren izan. Esaidazu [Barrez] Ados. ALAN ESTRADA: Non ari gara? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: orain, Oraindik Ebakuntza dugu. Orain, medikuei. Da gaur egun ALAN ESTRADA: Let's- joan benetako utzi. Real. DAVID J. MALAN: Real. ONDO DA. Real behar izanez gero. Orain, modu da Mike Smith? ALAN ESTRADA: Horrela. DAVID J. MALAN: Zein bide? ALAN ESTRADA: itxaron. M is-- ezta? With-- hasi ginen DAVID J. MALAN: Bai. Geratzen ari dira. Zure eskubidea. ALAN ESTRADA: Bai. DAVID J. MALAN: Beraz, Mike hemen. ALAN ESTRADA: Zer? [Barrez] Adibidez Bad, mutil. Sentitzen dut. DAVID J. MALAN: Hau landuko zure aulkitik jauzi. ALAN ESTRADA: Oh. Oh. Egin ninduen. Egin ninduen. Oh. Oh. Hori ondo is--, zuk lortu nuen. Smith hemen? DAVID J. MALAN: Smith, eskerrik asko. Beraz eduki dut bila Smith? ALAN ESTRADA: Oh, bai. Ez, ez, ez. Oh ez. Hau nirea da. DAVID J. MALAN: Oh, lortu duzu Smith. ONDO DA. ALAN ESTRADA: Bai, I lortu Smith hementxe. Sentitzen dut, mutilak. Pentsatu nuen Michael-- dugu ziren Michael bila. Sentitzen dut. DAVID J. MALAN: OK da. Ondo da, orain gaude Paccini Hijos sartu. ALAN ESTRADA: Paccini eta semeak. DAVID J. MALAN: zuk bakarrik eta honetan zaude dut. ONDO DA. Aurki digu Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Oraindik zabor for R bizi gara. ALAN ESTRADA: Zabor. Oh. Hau da, berriz, bat hartu behar da. [Barrez] DAVID J. MALAN: Shoes. Oraindik oinetakoetan dugu. ALAN ESTRADA: Orain gonna-- ari gara DAVID J. MALAN: Nice. ALAN ESTRADA: Which-- [Barrez] Oh, hau handia da. [Barrez] DAVID J. MALAN: OK da. ALAN ESTRADA: Oh, hau da ona. Ez dut uste noa PSAT lagunak honen ondoren. DAVID J. MALAN: Ongi. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. MALAN: OK. Hargatik alderik honen erdia. Ondo da. Hau bukatzen gaizki hala ere, Mike delako Smith ez da izango orriak horiak izan. ALAN ESTRADA: Aw. DAVID J. MALAN: Ez, ez da ezer. Baina demagun bezala Orrialde honetako zuen. Beraz, orain, behera kraskatu duzun arazoa Orri bat, eta Mike Smith aurkitu dugu. [Txaloak] Ados, eskerrik asko. ONDO DA. Hori izan zen aparteko. Baina oraindik ere azkarragoa izan zen bilaketa lineala baino, dua hasiko at dugu Liburuaren hasieran, eta gure bidea ezkerretik eskuinera mugitzen gara, Azkenean Mike Smith bila. Eta, beraz, telefono book bada Izan agian 1.000 orrialde, agian, hartu dute litzateke gurekin 10 edo, beraz, orri malkoak. Baina zuk leveraged daiteke hipotesi bat tocado Hori guztia garaian, alegia Telefono aldez aurretik liburu hori zer zen? Ikusleak: ordenatuta. DAVID J. MALAN: ordenatuta. Eskuin? Alfabetikoki ordenatuta, beraz, Izenak eta zenbakiak horiek guztiak dira A-ren aurrean ordenatuko Z-ren, eta alfabetikoki artean. Baina gaur egun, orain galdetzen dugu galdera, bai, nola Verizon egin edo telefonoa Konpainiak lortu da egoera horretan sartu? Gauza bat delako leverage bereganatzeak eta, horrenbestez, batekin arazo bat konpontzeko Algoritmo eraginkortasunez. Baina inoiz ez dugu benetan Aste zero eskatu, bai, zenbat egin da kostua Verizon edo beste norbaitek Telefono ordena ordenatuko liburu hori lortzeko? Eskuin? Ez du axola bada gora begira Mike Smith da super azkarra, zuk bat hartzen bada Urte orrietan hasieran ordenatzeko. Eskuin? Baliteke baita besterik sift Telefono book ausazko baten bidez, bada nik super izango da garestia da ordenatzeko. Beraz, bada boluntario beste izan dezakegu. Utz a hemen begiratu up at en nola might-- etorri gara nola up-- genezake horiek ordenatzeko. Eta bada Jordan izan benetan apunta zaitez hemen etapa. Goazen sortu une bat besterik ez da. Nola deitzen zara? CAROLINE: Caroline. DAVID J. MALAN: Caroline, goazen gora. Eta zuk sartu behar dituzu me eta Jordan hemen. Caroline, eskerrik asko. Ados. Beraz, hemen zer egin behar dugu Caroline 26 liburu urdina da FAS hori erabiltzen kudeatzeko azken azterketak jakin. Hauek hard lortzen ari den aurkitu, baina zer aldez aurretik egin dugu dela jarri dugu norbaiten izena horietako bakoitzaren aurrealdean, baina soilez egiten mantendu dugu Orduz luzatuz izen-abizenak. Beraz, pertsona jarri genuke izenarekin L, D, J, B, horrela A guztien Z bitartez, baina ari ausazko ordenan dute. Eta, beraz, ez litzateke izango bada, hizketan zure modu duzun bezala arazoa bidez ez da, ezin joan aurretik eta ordenatzeko horiek guretzat, A-tik Z. Ikusleak: Ados, beraz, L bezalakoa da, erdian. C hasia da. B. J L. B aurretik, Q. DAVID J. MALAN: Eutsi dagoela segundo batez pentsatu. Bestela delako, hau da bakarra zu, ni, eta Jordan interesgarria. Hor dugu. Ikusleak: [INAUDIBLE]. R. DAVID J. MALAN: OK. Zertan zabiltza? CAROLINE: M O. ondoren dator DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Good. CAROLINE: E. DAVID J. MALAN: E, F. Yeah. CAROLINE: T, U, V. DAVID J. MALAN: V, T, U, V. Beraz, Itxura zauden bezala making-- jarraitzea. Bezala egiten ari zarela dirudi pila handi bat, hemen, eta han pila handi baten antzeko zerbait. Beraz alfabetoaren lehen seihilekoan, alfabetoaren bigarren erdian. ONDO DA. Ona. Kind of arazoa zatitu bi. M, N, X. Yeah. CAROLINE: K. DAVID J. MALAN: OK. K. mota Beraz hautatzen ari zaren bata bestearen atzetik, horiek, bai, ezker-eskuin jarriz, edo Z-ren solairuan joan. ONDO DA. CAROLINE: Z solairuan joan. DAVID J. MALAN: OK. Y lurrean joan. Orain X. jarri ahal izango dugu CAROLINE: G. DAVID J. MALAN: G-ren ezkerrera joan. S xuxen doala. Ondo da, A modu guztiak utzi egingo da. CAROLINE: A, B, C, D. DAVID J. MALAN: Ongi, ona. Lortu dugu A, B, hor behera doa C. W en. Guztiak eskubidea, T. CAROLINE: H, I, J DAVID J. MALAN: H, I, J Good. CAROLINE: Erdian, gonna-- naiz DAVID J. MALAN: OK. Beraz, gaur egun, mota goaz batzea hainbat pila horiek. Beraz, A C bitartez, gero ikusiko dut D, eta E, F eta, eta G eta H, eta I. Nice. J, K. Eta gero, pila hori da goitik behera, baina hori OK. Ziur. Txoko batzuk moztu ahal izango dugu. ONDO DA. Eta gero, W, X, Y, Z. behar dugu CAROLINE: Bai. DAVID J. MALAN: Bikain. Beraz handi bat eskerrik asko Caroline horiek ordenatzeko. [Txaloak] Eskerrik asko. Mila esker. Beraz, gaur egun dezagun, une batez nola Caroline hori eguiten çuela eta zer garen nola zaie ahal izan dugu hori konpontzeko gai izan ziren Arazoa denean besterik ez ginen Emandako ausazko sarrera sorta oso bat. Beno, itxura ez bezalakoa da sistema bat han apur bat izan zen? Eskuin. Beraz, lehenago letrak alfabetoan, zuen zen ezkerreko jarriz, eta alfabetoaren letrak geroago, eskubidea sartu zuen jarriz. Eta ahalik eta azkarren zuen aurkitu proximal letrak, batzuk Hori joateko eskubidea, bata bestearen ondoan, horiek jarri zuela ordena. Eta beraz, mota izan genuen txiki horiek gertatzen ordenatuko sarrera pila. Eta beraz, nahiko bezala zer gizakiak gurekin gehienak ez litzateke. Sort genuke sift horren bidez, eta litzaidake motatako dugun mekanismo bat. Baina zaila izango da agian, idazteko behera formula bat per se da. Apur bat gehiago hori baino organiko sentitu da. Beraz, ikus dezagun orain ezin dugu doazen bada Sarrerek gutxiago arazoa. 26 ordez, dezagun zerbait askoz gutxiago egin besterik esateko, zazpi, atzean Ate horiek, nolabait esateko. Ba al dago besterik zazpi zenbakiak? Eta helburua at orain bada Eskua balio bat aurkitzeko, Ikus dezagun nola eraginkortasunez ezin dugu hau egiten. Eta utzi ikusteko ahal bada en zenbaki batzuk aplikatzeko hasteko, edo formulak batzuk, honekin deskribatuko gure telefono book eraginkortasuna bildu, gure azterketa-book bildu, eta orokorrago, informazioa bilatzeko. Beraz, horretarako, utzi aurrera me, eta ukipen-pantailan hemen baino gehiago, paratu ditu web nabigatzaile baten zehazki zazpi ate horiek. Eta bada beste bat lortu ahal izan genuen etorri hemen baino boluntarioak, Ate horiek berak dut jarri dut hemen baino. Boluntario Quick. One-- demoak hau doaz azkarrago eta azkarrago orain. Goazen behera. Nola deitzen zara? TREVOR: Trevor. DAVID J. MALAN: Trevor? Ondo da, Trevor, behera etorri dira. Beraz, Trevor hemen boluntario ditu antzeko arazoren bat egin, baina hori da esparrua ere estuagoa, eta hori gertatzen ahalbidetuko orain formalizatzeko saiatu gurekin ordenatzeko zenbakiak hauetarako prozesuan. Beraz, Trevor, politak zu ezagutzeaz. Beraz, hemen array bat da, beraz, hitz egin, zazpi ate zerrenda bat. Anima zaitez eta 50 zenbakiaren gauden. Eta gero ere, ondoren, Kontatu nola aurkitu duzu. Guztien eskubidea jolasten beharko luke. Bai, horixe da hemen? Uh-oh. ONDO DA. Bat sakatu duzu. Ona. Eta ona. Orain bat dagoela sakatu duzu. Eta dizute mikrofonoa eman zidan, beraz, nahi baduzu une bat besterik ez. Anima zaitez eta egin klik zuk nahi duten ate ondoan. Bai, ona. TREVOR: Ezin ate bat unclick dut? DAVID J. MALAN: Ez, ezin duzu unclick. TREVOR: OK. Honek bat. DAVID J. MALAN: Nora joan nahi duzu? Zein? TREVOR: Bat dela. DAVID J. MALAN: No. TREVOR: OK. Honek bat. DAVID J. MALAN: Bai. Hori ona izan zen. Ados. Beraz, zer zen zure algoritmo edo honek, Trevor egiteko prozedura? TREVOR: igaro nintzen, besterik ez dut ateak 50 bat aurkitu nuen arte. DAVID J. MALAN: OK. Bikain algoritmoa. Beraz, hori da isuna. Hain zuzen ere, agerian badut delako zer da beste bi ate horien atzean, zer Hemen aurkituko dugu dela ausazko sarrera bakarra izan dugu. Beraz, hori izan zen benetan gisa ona lortu ahal izan duzun bezala. Eta hain zuzen ere, baino hobea lortu duzu zorrotz jaso array osoa bilatuz, Benetan zatekeen delako unlucky baduzu sakatu zuen kopuruaren 50 oso azken atean. Baina zer badugu ordez hipotesi bat eman zenuen. Suposatzen dut Sort guztiak Ate horiek inguruan, beraz, behar duzu zenbakiak oraingo honetan ordenatuta, baina oraingo honetan, egia esan, oraingoan desberdina, benetan da zuretzat ordenatuta. Eta orain, esku helburua 50 zenbakia sakatu. TREVOR: OK. DAVID J. MALAN: Zer da Zure algoritmoa behar du? TREVOR: Denok, bada ordenatuta, bai da joan to handienetako bada handienera jolasten, beheranzko, lehenengoa izango da, edo kontrakoa izanez gero, azkena izango da. Beraz, besterik ez dut ukitu ate hau, eta orduan besterik ukitu azken atea. DAVID J. MALAN: Bikain. Ados. Beraz, 50 zenbakia aurkitu dugu. Bazekien, beraz, ahalik eta azkarren ordenatuko ari zirela, dugu Suposizio hau onura ateratzeko gai izan ziren. Beraz, gehiegi atsegin ari dira Telefono book adibidez. , Nahiz eta elkarrekin izan bezain laster hau bezalako arazo txiki bat, Zure Sarrerek aurrez-ordenatuta, ahal dugun benetan aurkituko balioa, dudarik gabe, eraginkortasunez. Eta ez nuen esango dizu bazegoen handira txikiak, edo big txiki ordenatuta, eta, beraz, oso arrazoizkoa zen mutur edo beste zenbait hasteko helburu balio hori benetan aurkitu. Beraz, Trevor eskerrak baita. Eta nicely egin propose-- dut. Clip txiki bat izan dugu, egia esan, hori Gure CS50 une gogokoenak artean dago, Horren bidez, batzuetan demoak horiek ez nahiko joan planaren arabera. Eta hain zuzen ere oraintxe, I hala sortu oker interfazea bertan ukipen-pantaila erabili. Beraz, hori ez zen nire errua. Beraz, hau izango da egin Hurrengo urteko clip zergatik dut nire pantailan egin klik eginez zen. Baina dezagun begirada bat iaz gertaturikoa Jay, nork sortu izan zen, askoz ere Trevor hemen bezala, borondatez, eta clip labur honetan, ikusiko duzu nola demo hau bera ez da nahiko ikasi ikasgai bera agerian. [Bideo-erreprodukzioa] Denak egin behar duzun gauza bakarra da orain niretzat aurkitu, eta guretzat, benetan, kopurua 50 aldi berean urrats bat. 50 zenbakia -The? 50 zenbakia -The. Eta zer da agerian ditzakezu Ate horietako bakoitzaren atzean besterik ez ukitu hatz batekin. Malditos da. [Barrez] [END erreprodukzioa] DAVID J. MALAN: Beraz, hori oso ondo joan zen. Horiek Unsorted ateak ziren. Eta Jay, noski, suertatu dena azkarregi. Trevor lan askoz hobea egin Une teachable dagokionez, , aurten, beraz, hitz egiteko irauten ari da aurkitzeko. Jakina, orduan eman dugu Jay bigarren aukera bat, Horren bidez, ateak ordenatuko ditugu, Trevor egin genuen bezalaxe, eta Trevor egin super ondo oraingo honetan. Baina Jay egin erdia bezain azkar. [Bideo-erreprodukzioa] Helburua -The orain da, halaber, 50 zenbakira gauden, baina egin karguen taldeak, eta Kontatu nola buruz ari zaren. -ONDO DA. -Eta Aurkitzen baduzu, filma mantentzeko duzu. Izan ez baduzu, aurkitu, eman duzu atzera. -Man. -Oh! - [INAUDIBLE] Ados. Beraz, ez dut muturrak egiaztatu noa Lehenengo den there's-- dauden jakiteko Oh. [Txaloak] [END erreprodukzioa] DAVID J. MALAN: OK. Beraz ateak sailkatuz, argi eta garbi eraginkortasun handiagoa dakar. Eta, beraz, bi aldiz azkarrago zer ez, esan nahi dut. Eta beraz, Jay lortu bi aldiz zortea. Eta, era berean, azken hori ere zortea lortu zuen Urte, Blu-Ray diskoak batzuk agindu dut benetan eman. Sentitzen dut aurten, dugu ez bera, Trevor. Baina hobe oraindik urte batzuk atzera egin baitu. Eta batzuk hau jakin liteke Adiskide, Sean ere, ohiko zen CS50 zuen, zehatza desafioa zen Arazo bera, SD bada ere, laster ikusiko dituzu, egun atzera jo. Eta aurkitu ez hori bakarrik egin ahal izango duzu Jay baino pixka bat gehiago hartu zuen, Trevor baino pixka bat gehiago, izan zen benetan aukera zoragarri honetan ia denek ihardun Epaileak la Price bat Right da, pozgarria kopuruaren bila ari ginela aurkitu zion. Dezagun. begirada bat hartu. [Bideo-erreprodukzioa] -ONDO DA. Beraz, zure lana hemen, Sean, honako hau da. Ditut horien atzean ezkutatuta Ate zazpi zenbakiarekin. Baina kanpoan bilduta ate horietako batzuetan baita beste zenbaki negatiboak dira. Eta zure helburua da, uste goi zenbakien ilara honen besterik array bat, edo, besterik gabe gisa paper zatiak sekuentzia Horien atzean zenbakiekin. Eta zure helburua da, goian bakarrik erabiliz array hemen, niri zazpi zenbakiarekin. Eta ari gara, ondoren, kritika joan egiten nola joan zaitezke. -Ados. Aurkitu gurekin zazpi kopurua, mesedez. No. Bost, 19, 13. [Barrez] Ez da trikimailu galdera bat. One. [Barrez] Une honetan, zure puntuazioa ez da oso ona da, beraz, baita dezakezu mantendu egingo da. Hiru. [Barrez] Tira. Egia, ezin dut lagundu, baina harritzekoa zer duzu, nahiz eta, buruz esaidazu pentsatzen ari [Barrez] Goi ilara bakarra, beraz, baina dituzun hiru ezker. Beraz, aurkituko me zazpi. [Barrez] 17. Zazpi. [Txaloak] Ados. [END erreprodukzioa] DAVID J. MALAN: Beraz, ezin izan dugu ikustera horiek egun osoan zehar. Eta, jakina, batzuk Aurtengo demoak agian orain amaituko da hurrengo urtean Aurtengo bideo baita. Beraz, gaur egun dezagun benetan algoritmoak ardatz hemen, eta ezin dugu ikusi orain formalizatzeko hasteko nola egin dezaket gure datuak lortzean joan gara egoera honetan sartu dela ordenatuta, beraz, azken finean, ahal dugun benetan bilatu eraginkortasunez. Eta ari gara, nahiz eta Datu multzo nahiko txikiak erabili, Zortzi zenbakiak dugun bezala hemen taula gainean, azken finean, ideia horiek berak eskatu ahal 1.000 sarrera, milioi bat sarrera, 4 milioi sarrera, algoritmoak delako funtsean berdina izango. Eta, beraz, hau da, gure azken gaur boluntario aukera, baina agian gehien inplikatu du, horretarako, zortzi boluntario behar ditugu etorri eta oinez gurekin bidez ordenazio-prozesuan zer izango da laster musika hauen gainean egon nabarmentzen hemen. Dezagun hasteko me back hemen. Beraz turquoise-- berde bat dago? Zuk eskatzen duena? Bi. Goazen behera. ONDO DA. Hiru. Lau. Let Niretzat OK, bost. Zure laguna zaren sarietarako izendatu zuten. Sei, zazpi, zortzi. Goazen sortu. Ados. Eskerrik asko. Goazen sortu. Goazen sortu. Ados. Beraz, zer da hemen eta hau dugu gehiago baldar direnak artean dago, hau geroztik umorea, beharrezkoa izango da denbora pixka bat besterik ez da niretzat. Zenbaki bat izango duzu. Nola deitzen zara? Annan: Annan. DAVID J. MALAN: Annan. David. Nola deitzen zara? JOSEPH: Joseph. DAVID J. MALAN: Joseph, bi zenbaki zara. SERENA: Serena, hiru zenbaki. Stefan, lau zenbakia. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, bost zenbakia. [INAUDIBLE] DAVID J. MALAN: [INAUDIBLE]. David, sei zenbakia. MATT: Matt. DAVID J. MALAN: Matt zazpi zenbakia. Eta? WAVERLY: Waverly. DAVID J. MALAN: Waverly, kopuru zortzi. Ados. Whoops could-- baduzu. Duzun guztia bada, eta zure lehen erronka, han daude zortzi musika standak publikoari begira. Duzu zure zenbakiak jarri balute on musika horiek modu bat, nabarmentzen lerro dutela batera taula gainean zenbakiak bera. Beraz Begiratu horrela zuek bezalako arabera Zure zenbakiak jarriz musika horiei buruzko nabarmentzen hemen. Bikain orain arte. Bikain. ONDO DA. Beraz, orain, eskatu goaz zenbait modu desberdinetan galderari. Nola egin dezaket ordenatzeko dugu folks hemen horiek? Planteamendu batzuk izan dugulako lehenago, eta horren bidez ginen mota bi ontzi ezberdinen egiteko. Eta gero, oro har ginen Gauzak elkarrekin lotu. Bezain laster, bi zenbakiak ikusi genuen bezala Bertan, batera baita, jarri dugu elkarrekin. Bi letrak elkarrekin sartzen direla. Baina ikusi bada ren dugu Ezin formalizatzeko honetan, azken finean, ez dugu, beraz, izango duzu, sasi-kodea batzuk, bertan arazo horiek konpondu ahal izango duzu. Beraz, orain, egindako nabil zenbaki horiek hemen. Eta akatsak sorta oso bat ikusi nuen. Azken finean, inork nahi dut ezker eta zortzi eskuin hegaletik. Eta beraz, I nabil bi horiek, lau eta bi. Eta zein da arazoa, jakina? Bai. Hortaz Bi jakina aurretik dator lau, beraz, badakizu zer? Eta hasteko greedy hurbilketa bat hartu dit, Izango duzu, askoz ere atsegin arazoa bada ezarri one-- Gogora batetik bada Edizio Arazoa Ezarri One of Standard, non I besterik lokalean arazoa konponduko Hori Hemen da nire aurrean ikusi eta non me eramango da. ONDO DA. Beraz, bi eta lau, let me go Animatu eta besterik trukatu duzu bi. Fisikoki ezin duzu mugitu bada zuek eta zure paper, Ahaztuak dute badirudi I egoera hobean zerrendatu. Orain, onak dira. On mugitu noa, lau eta sei, itxura ona. Ez da arazo bat. Sei eta zortzi, OK. Zortzi eta bat, beste arazo bat. Zer da zortzi eta bat egia delako? One zortzi aurretik dator, eta, beraz, zer egin behar dugu? Dezagun trukatu bi horiek. One eta zortzi. Eta orain, Noa jarraitzea. Aurrera begira mantentzeko noa. Eta ikus dezagun zer gertatzen den. Zortzi eta hiru, la Jakina, behar bezala erabili. Dezagun swap. Zortzi eta zazpi, noski. Ordena daudelarik. Dezagun swap. Zortzi eta bost, jakina, dezagun swap. Ados. List ordenatuko da. Bai? Ados, jakina, ez. Baina pixka bat hobea da, ezta? Oharra zer gertatu delako. Aldi bakoitzean swap bat, burutu dugu txikiago bat zenbakia motatako percolated era horretan, eta kopuru handiago batean Horrela percolated, edo zaitugu Esaera den bubbled hasteko ezkerrera edo eskuinera bubbled. Orain, ez da nahikoa, zeren onenean zenbaki bat gerta daiteke izan spot bat mugitu Aurrera, edo txarrena, zenbakia izan liteke Leku bat mugitu urrunago. Beraz, badakizu zer, mota honetako ren lan egin nahiko ongi orain arte. Dezagun saiatu besterik ez dit berriro. Bi eta lau, OK ari dira. Lau eta sei, OK ari dira. Sei eta bat, behar bezala erabili. Hargatik trukatu duzu bi. Eta, orain, konturatu arazoa hamarkadan hobea berriro pixka bat iritsi hasita. Sei eta hiru, behar bezala erabili. Dezagun trukatu duzu bi. Sei eta zazpi, onak duzu. Zazpi eta bost, jakina, behar bezala erabili. Zazpi eta zortzi, ordena. Eta orain, agian behar Egin aldiz hau gutxi gehiago. Eta hain zuzen ere, zuek uste nola agian Gehienez adina aldiz agian atzera eta aurrera oinez egin behar dut? Etorri egingo dugu atzera. Beraz, bi eta lau OK daude oraindik. Lau eta bat, Laguia. Beraz, dezagun swap. Eta berriro ere, nabarituko ikusmen Bat bubbling mota da ezkerretik, non egon behar da. Lau eta hiru swap. Lau eta sei. Sei eta bost swap. Sei eta zazpi. Zazpi eta zortzi onak dira. Ona. Are hobeto ari gara. Beraz, ikus dezagun. Orain, bi eta bat daukagu. Jakina, trukatu. Bi eta hiru, hiru eta lau, lau eta bost, sei eta zazpi, zazpi eta zortzi. Ona. Eta zer ezagutzen duzu? Aldaketa bat egin nuen ez delako, let me egin behatu kontrol bat. Dezagun modu guztiak joan me itzuli hasieran. ONDO DA. One, bi Yup, ikusten? Zerbait gaizki. Hiru, lau, bost, sei, zazpi, zortzi. Eta azken pass honetan, eroso nire orain duzu erreklamatzeko ordenatuko da? ONDO DA. Estetikoki, hori da erabat egia. Baina funtzionalki, zer Halaber besterik gertatuko ahalbidetzen duen azken pass horretan Zerrenda hori da, hain zuzen baieztatzeko ordenatuko? Zer egin dut edo ez, azken mendatean Horretarako? Ikusleak: Ez ziren aldaketak. DAVID J. MALAN: Barkatu? Ikusleak: Ez da aldaketarik. DAVID J. MALAN: Ez ziren aldaketak. Beraz, me ergelak izango litzateke Algoritmo hori bera berriro egiten ez nuen egin duen Lehenengo aldiz aldatzen. Eta egoera ez da aldatu. Seguru asko, ez naiz egiteko joan Bat, bigarren aldiz aldatzen. Eta beraz, segurua da orain esan nahi baita, zerrenda ordenatuko da. Eta hain zuzen ere, hau da, gaur egun, Zerbait oro har, ikusiko dugu deiaren burbuila ordenatu, zeinaren Pairwise, akatsak berriro zuzenduta, eta berriro, eta berriro, eta zuk mantentzeko atzera eta aurrera, eta atzera eta aurrera, arte egin gabe, hala nola, trukeak, eta amaitzen da konfiantza dezakezu, bai, I akatsak guztia konpontzen amaitu. Dezagun berrezarri eta saiatu hurbilketa bat. You guys atzera egin balute sartu ordena duela une bat izan zinen, hori dirudi. Orain, dezagun hurbilketa bat little more azterketa-liburuan bezala, Horren bidez, etengabe ginen alfabetoaren letra hautatuz motatako nahi dugun ondoan aurre. Agian gutun altua izan zen, A, edo gutun Z. txikiko bat bezala Beraz, denek ordena honetan atzera. Eta orain utzi egin zidan. Ikus dezagun ezagutzen dut nik egin dezagun Zortzi zenbakiak hemen. Aurrera joan noa eta besterik nahita hautatu elementu txikiena. Eskuin? Hau intuitiboa badirudi too. Zergatik ez txikiena aurkitu dut elementu, jarri dagokion tokian, ondoren, hurrengo elementu txikiena lortzeko, jarri da tokian, eta besterik ez errepikatzeko. Senez delako, hori ere lan egin behar dute. Beraz, lau, hori nahiko kopuru txiki bat da. Gogoratzen non hau da noa. Itxaron minutu bat. Bi txikiagoa da. Let gogoratu me now non bi da, eta lau ahaztu. Egingo duten aurre dugu beranduago. Sei, ez zait interesatzen. Zortzi, ez naiz interesa. One nire kopuru txiki berria da. Beraz, ez dut gogoratzen non da joan. Hiru, inongo interesik. Zazpi, inongo interesik. Bost, inongo interesik. Beraz, off erori gabe etapa aurten, Kopurua hartzen noa one-- eta zer da zure izena berriro? Annan: Annan. DAVID J. MALAN: Annan. Eta zuk me sartu izan balira Zerrenda honen hasieran, dezagun non sartzen duzun jarri duzu. Unfortunately-- Zein da zure izena? STEFAN: Stefan. DAVID J. MALAN: Stefan bidean da. Beraz Stefan konpontzen lehenago honetan Arazoa, zer egin behar dugu? Zer egiten dugu Stefan batekin? Ikusleak: [INAUDIBLE]. DAVID J. MALAN: OK. Beraz, hori egin ahal izan genuen. Ezin Sort hartu dugu Stefan eta bere lau, eta besterik jarri aldagai batean eta eutsi behar da for zenbat denbora pixka bat, horrela kopuru bat egiteko gela egiteko. Eta hori ez da txarra. Iradoki izan dut, zergatik ez jarri besterik ez dugu Stefan hemen? Zergatik honetan aurka joan daiteke bat ideien hasi ginen Azken astean Azken aldiz, buruz hitz egiten,? Bai? Ikusleak: [INAUDIBLE]. DAVID J. MALAN: ez dute horretarako indizea da. Hori dela uste duzu, hain zuzen ere, gisa bada array, hau negatiboa bezalakoa da, beraz, ez dago memoria ez da benetan Hemen hau da, hain zuzen ere bada array bat, atsegin azken astean deklaratu dugu hitzaldia. Beraz, ez dugu egin behar hau. Baliteke gordeko dugu aldagai batean. Edo zer ezagutzen duzu? Beste norbaitek proposatu entzun nuen. Zer gehiago ezin dugu Stefan batekin? Zergatik ez erailak besterik ez dugu hura, eta jarri zion non zenbaki bat baino gehiago izan zen. Beraz, han joan nahi baduzu. Eta hain zuzen ere, hau da, nahiko ona irtenbide. Orain, alde batetik, halako zerbait daukat egina arazoa okerragoa. Lau da orain urrunago non egon behar dute. Zati hau aldera izan beharko luke. Baina, zer ezagutzen duzu? Hau zorte txarra izan zitekeen. Agian kopurua zortzi izan zen hemen. Eta, beraz, agian genuke Ahaztuak zortea, eta bultzatu zortzi amaiera hurbilago. Beraz, egunaren amaieran, nolako bataz bestekoak atera. Ez dugu behar lau arduratu da. Guztiak buruz zaintzen dut oraintxe da txikiena elementu hautatzen. Eta orain, zer naiz joan ez da zenbaki bat ahaztea betirako, badakit delako Zerrenda me atzean gaur egun antolatuta. Beraz, nire zerrenda Lehenago, zortzi. Orain, zazpi tamaina of it. Beraz, nire arazoa bihurtzen ari da txikiagoa, linealki arren. Beraz, gaur egun, naiz hautatzeko joan nintzen egungo elementu txikiena, bi. Sei, zortzi, lau, hiru, zazpi, bost. Txikiena elementu zen. Beraz, nik zer with-- ez dut joan zer da zure izena berriro? JOSEPH: Joseph. DAVID J. MALAN: Joseph? Joseph uzteko leku goaz. Orain, itxurak noa horiek mutilak ondo are--, Dakit bi hauek antolatuko dira dagoeneko. Utzi du orain ren dutelakoan zerrendako gainerako. Sei egungo txikiena da. Zortzi handiagoa da. Lau egungo txikiena da orain. Hiru egungo txikiena da orain. Eta, beraz, gaur egun, naiz hiru hautatzeko joan nintzen, Nork is-- Zein da zure izena berriro? SERENA: Serena. DAVID J. MALAN: Serena, ahal izango banu Zure zenbakia eta swap with-- hartu KALSANG: Kalsang. DAVID J. MALAN: Kalsang. Goazen atzera, eta ez gara bi horiek aldatu behar dugu. Eta orain, dezagun jarri hau autopilot on. Joan eta utzi duzu guys noa hurrengo txikiena elementuak hautatzeko. Dun, dun, dun, dun. Zenbakia lau, zer egin behar duzu? Bikain. Orain, Noa pass beste egiteko. Dun, dun, dun, dun. Ikusten dut bost da hurrengo txikiena. Orain, pass bat hartuko dut. Dun, dun, dun, dun. Sei txikiena da. Ona. Zazpi txikiena da. Aldaketarik ez. Zortzi txikiena da. Done. Beraz, zer egin dugu besterik iteratively burututako elementu bat hautatuz bestearen atzetik hau da, zerbait ari gara ezartzeko hautapen moduko gisa formalizatzeko joan. Eta ez da, beharbada, baita errazagoa azaldu, hori literalki duzu egin da, besterik gabe, gorde nahi atzera eta aurrera joan zerrendan zehar aukeratuz, hurrengo elementu txikiena, Bukatutakoan arte. Beraz, nahiz eta errazagoa da, agian intuizioa, azken baino. Dezagun saiatu bat azkena utzi. You guys zuei berrezarri balute honako posizioak sartu final garai batean, ikus dezagun, ezin dugu bada orain beste hurbilketa bat formalizatzeko. Izan ere, ez litzateke norbait Han kanpoan proposatuko nola bestela hau egiten dugu agian joan? Buzzwords edo ordenatzeko tossing gabe Dagoeneko ezagutzen diren erantzunak, besterik gabe, intuizioa, zer egin genezake? Ikusleak: [INAUDIBLE]. DAVID J. MALAN: Bai. Beraz, ez dira zenbait intuizio handia dago. Gauza ona dirudi orain arte gertatuko informatikako denean zatitzen dugu eta konkistatzeko zatituz arazoa erdia eta erdia eta erdia da. Eta hain zuzen ere, ez dugu Hori egiten hasteko modukoak. Eta hain zuzen ere, hori da hori izango zaitugu joan, ikusi, gure onena irtenbide bat oraindik. Baina dezagun etortzen diren itzuli luze baino lehen. Izan ere, egin goaz Aste honetan, apur bat geroago. Zer gehiago egingo ote dugu hau konpontzeko? Beraz, denek hemen da itxuraz ausazko ordena. Badakizu zer? Joan atzera eta aurrera baino, atzera eta aurrera, atzera eta aurrera aldi bakoitzean, sentitzen atsegin Oinez asko egiten ari naiz. Zergatik ez naiz hasiko besterik Zerrenda honen hasieran, eta besterik jarri lau tokian? Hargatik bere gain hartzen oraingoz me dagoela nire zerrenda lehen elementu hau bakarra da. Une honetan ez dago lau ordenatuko denboran, zaintzen dut dena da hemen, bada? Hau da Ordena kenduz egia, ezta? Kopuru bat biltzen dituen zerrendan, eta antzekoak lau zenbaki hori jakina ordenatuko da. Hargatik zeintzuk besterik me Zerrenda honetan dago antolatuta. Baina orain, zerrenda hau gainerako daukat. Beraz, gaur egun, bi topo dut. Non dago bi jakina lau aldean sartzen zara? Lau aurretik. Beraz, zer egin nahi dut? Zein da zure izena berriro? JOSEPH: Joseph. DAVID J. MALAN: Joseph, atzera urratsa balute besterik zure zenbakia, une batez. Eta orain zer egin behar Stefan egin hemen? Dezagun filmea Stefan hemen baino. Eta orain, utzi Joseph etorri hona. Eta orain, utzi niri erreklamatzeko dena hemen ordenatuko da. Beraz, antzeko emaitza, baina bat Planteamendu funtsean ezberdinak. Ez dut, nahiz eta begiratu zer ekarriko behera dago. Mantendu besterik ez dut elementu hartu me ari dira entregatu gisa, eta haiei aurre egiteko. Beraz, orain, sei zenbakia ikusi dut. Non sartzen duela sei zenbakia? Bi, lau, sei daukagu. Zehazki non oraintxe da zuen. Hargatik uztea dela eta bakarrik, eta orain zerrendako zati hori erreklamatzeko gaur egun antolatuta. Eta, beraz, hau sentitzen funtsean ezberdina besterik ez naiz zerrendan zehar mugitzen hemen linealki, eta ez dut inoiz itzuli bikoiztu. Bai. Ados. Beraz, zortzi, non ez zurea? Hementxe. Perfect. Horrela orain. Uh-oh. Hau sentitzen da bezala garestia izango da. Orain, aurreko algoritmoa ere, Trukatu besterik ez dut jendea. Beraz, nahi dut jarri zion modu guztietan hasieran, baina ondoren, joan zen Joseph. Baina mugitu badut Joseph, orain zer oker joan? Orain, ordenatzeko undone-- dut dut dut hartu urrats bat aurrera eta gero urrats bat atzera, orain delako Joseph ordena izango litzateke. Beraz, egin dezagun. Duzu zenbaki bat eramango balute eta atzerapausoa eman besterik ez da. Nola egin dezaket jarri du dugu zer Zure izena berriro izan zen? Annan: Annan. DAVID J. MALAN: Annan lekuan? Zer behar du aldean gertatuko bi, lau, sei eta zortzi nahi? Filmea behar ditu. Beraz, zortzi bada filmea nahi lehen, ondoren, sei, ondoren, lau, gero bi. Eta gero, Annan, baduzu litzaidake ere hona etorri nahi, ona gustatzen. Baina hemen, besterik ez dugu motatako ordaindutako prezio batean algoritmoan ezberdinak puntu batean. Aukeraketa denbora azken Berriz ordenatu, eta are gehiago, burbuila ordenatu, Itzuli naiz oinez eta aurrera, atzera eta aurrera, hau da, zalantzarik gabe, elkarri eransten denbora aldetik, eta literalki stepwise. Txertatzeko ordenatu, hasiera batean begiratuan, badirudi bezala super smarter, hori besterik ez naiz motela, aurrerapenak areagotu egiten, Baina ez dut atzera eta aurrera joan. Baina norbait bada, hain zuzen ere ordena, oharra atera lana egin izan dut guztia. Zerrenda erdia eraman behar izan nuen besterik kopuru bat gorde ahal izateko. Beraz kopuru bera da lanaren orain arte egiten sentitzen, lan mota desberdin bat besterik ez. Jarrai dezagun. Beraz, gaur egun ezagutzen dugun guztiontzat dela bat eta zortzi artean antolatuko dira. Hemen, hiru zenbaki daukat. Jaso nahi baldin baduzu hirugarrena, atzerapausoa bat. Eta zer egin behar duzu mutilak? Yep. Beraz, hori beste bat, bi, hiru urrats egin. Hiru denbora unitateak hori besterik kostatu me, beraz, hiru orain doi ditzakezu. Azkenik, zazpi. Dezagun aurrera eta Urrats back bat hartuko duzu. Hau da gurekin kostatuko bakarrik joan denbora-unitate bat, baina OK. Eta orain, joan den bost en apur bat garestiagoa izan. Atzera egitea nahi baduzu. Zortzi mugitu behar dugu, eta zazpi, eta sei. Eta, ondoren, denek gaur egun antolatuta. Gure boluntarioek hemen handi bat eskuz beraz. Eskerrik asko. [Txaloak] Eskerrik asko guztioi. Eskerrik asko guztioi. Beraz, ikus dezagun orain nola garestia hori guztia izan zen. Dezagun kontuan beharbada horien errazena, burbuila ordenatu. Eta errazena esaten dut, besterik ez delako irrikaz konpondu ahal izango duzu, besterik arabera pairwise arazoa konpondu hemen. Pairwise arazoa konpontzeko Hemen, behin eta berriro eta berriro, behin eta berriz errepikatzen askotan bezala Nondik duzun bezala, benetan behar. Beraz, izarrekin bihurtzen da burbuila moduko bat da, bai, zenbat urrats egin hartu behar dut algoritmoa, lehen mendatea? Baliteke dezagun see-- bat take-- dut, bi, hiru, lau, bost, sei, zazpi. Eta han zortzi elementu hemen. Beraz, n ken 1 to urrats bezala Zerrenda hasieran lortu zerrendaren amaierara arte. Baina aukeraketa ordenatu, gogoratzen naizela elementuen behin eta berriro hautatu eta berriro hori da txikiena, Jarriko dut, bere lekuan, baina gero, ez naiz me atzean berriro bila. Beraz, uste dut pixka bat argiagoa da ondoren, lehen aldiz, gerta daiteke n guztiak ken 1 urrats hartu behar elementu txikiena aurkitu. Ondoren ipintzen lekuan, eta I erailak duenarentzat zen hemen aurrez. Baina gero, ez dut izan mantentzeko elementu hau begira, dakit zeren da Dagoeneko txikiena. Beraz, gaur egun, zazpi at ezin dut begiratu elementu, ondoren, sei elementu, ondoren, bost elementu, ondoren, lau elementu. Eta beraz, matematikoki, n bada elementu edo zenbaki kopurua hasi gara batera, pentsa dezakezu hori da, n ken 1 berberak, plus n ken 2 urrats, plus n ken 3 urrats, plus n ken 4 urrats hauek guztiak, Bide urrats bat besterik ez behera. Eta naiz nire azken pertsona dut. Eta gogoratzen duzu asko dagoela bada stats liburuak edo matematikako liburuak on formulak horiek Hardcover back edo horien aurrean, bihurtzen da serie hori gehiago besterik adierazi ahal izateko 1 2 egindakoa bezain n aldiz n ken. Eta gauza ederra da hori ez bada Zure gogoaren abangoardian. Baina hori da, hain zuzen ere, egia da. Hori idazteko modu errazago bat besterik ez da. Eta gero uste baduzu kalifikazioa eskolara itzuli, noiz hasi besterik ez duzu biderkatzeko Gauzak out, noski honetan, besterik ez da n karratu ken n 2 banatuta. Guztiak egin dut zabaltzeko adierazpenekin ez. Eta beraz dezagun berridatzi honetan Apur bat ezberdina. Hori n karratu 2 ken n / 2 banatuta. Beraz, berriro ere, mota besterik aplikatuz naiz aritmetika arau batzuk ez. Baina orain konturatzen dela epe handiena adierazpen honetan, nolabait esateko, n duten karratu. Beraz, bai, n karratu da 2, ken n / 2 banatuta. Baina, oro har, n bada balio handi bat izango da, N karratu erreklamatzeko noa da faktore nagusia izango da. Besterik ez da izan joan kolaboratzailea handiago batean n / 2 baino urrats kopurua den. Beraz, zer esan nahi dut? Dezagun saiatu adibide sinple bat, nahiz eta math big apur bat jasotzen du, nahiz eta. Beraz, demagun 1 milioi pertsona izan genuen Etapa, 1 milioi gauzak edo on ordenatzeko nahi dugula. Dezagun plug milioi bat zehazki formula hori sartu guztira zenbat urrats hartzen du ikusteko milioi bat elementu ordenatzeko esan erabiliz, aukeraketa ordenatu. Beraz, formula bera izan genuen orain arte bezala. Plug nuke milioi bat, eta, beraz, ez dut lortzen milioi bat karratu 2 banatuta, ken milioi 2 banatuta. Math hori egin nuen, aldez aurretik bada Hemen, 500 milioi daukagu ken 500.000, eta horrek ematen digu 499.999.500.000, hau da, nahiko darn big. Izan ere, orain alderatu duzu 499 milioi, 999 milioi, 500.000 gure jatorrizko balio aurka, 500 milioi, hain nengoen hurbil da. Eskuin? n karratu 2 ematen arabera banatzen us-- edo, hobeto esanda, n karratu 2 banatuta eman zigun 500 milioi. Hori nahiko darn itxi 499.999.500.000 den, hau da off 500.000 kenduz esateko, edo, oro har, off kenduz n karratu, ez da benetan big aurre. N karratuko egiten horiek zenbakiak oso azkar hazten. Orain, hau da garrantzitsuena ez delakoan dugun bezala, ordenagailu zientzialari gisa, oro har, ez da hainbeste arduratu joan formula hauen ñabardurak buruz eta zehazki zer egin erantzun zehatzak dira. Dugu zainketa hori bakarrik, zer ezagutzen duzu? Egunaren amaieran, formula hau ordenakoa n karratu abian da. Bai, zu 2 zatituko ditugu han. Bai, off n ken 2 ari gara kenduz. Baina egunaren amaieran, epe benetan mina gurekin eta kostuak gurekin urrats asko epe karratu dela. Eta, beraz, ordenagailu zientzialari bat va den, oro har, ez ez ikusi da horiek guztiak Ordena dagokionez txikiagoa, eta bakar bat begiratzen duten kostua gehien laguntzen. Eta hau da, polita, ezin dugulako orain orokortasun askoz handiagoa ere hitz egin algoritmoak buruz, eta horiek alderatu. Eta hain zuzen, I naiz O hau erabiliz nahita. Noiz esan ordena I ren, zehazki naiz Zerbait aipatuz O. big Eta O big deitzen notazio bat da ordenagailu bat Zientzialari erabiltzen den deskribatzeko goiko zerbait lotuak bat. Beraz, esan duzu bada algoritmo bat O big denaren n karratu, I proposatu bezala besterik bati Une duela, horrek esan nahi du duten horien funtzionamendu aldetik denbora edo bere eraginkortasuna, hartzen ordena n karratu urratsak. Agian gehiago, agian gutxiago. Baina buruzko n ordena karratu da. Eta hori muga da. Ez da hori izango da Hori baino gehiago mingarria. Ez da n cubed izan, edo 2 joan n, edo zerbait askoz handiagoa da. Hau da, goiko doazen edozein dela kostu dela. Beraz, emandako hori, dezagun kontuan hartu adibide batzuk. Eta hau zerrenda finitu bat besterik ez da oso ohikoa exekutatzen aldiz hori ekarri nahi izan algoritmoak erabiliz Gauza batzuk ikusi dugu ilustratzailea Dagoeneko ikusi. Horrela, esate baterako, en el caso de aukeraketa ordenatu, hemen zer aldarrikatzen ari naiz Aukeraketa hori moduko exekutatzen da denbora da buruzkoak n ordena karratu. Kasurik okerrenean ere, izan noa ausazko zenbakiak hemen sorta oso bat. Eta matematikoki ikusi dugun bezala, oinez jarraitzen badut Zerrendan zehar, bidez zerrenda, hurrengo txikiena hautatuz elementu, behin eta berriro, badut benetan idatzi pauso guztiak Hartu dut formulaically proposatu dudan bezala aurretik, da n karratu ordena hori hartu dut urrats. Eta bihurtzen da burbuila hori ordenatu eta txertatzeko ordenatu bezain motela txarrena kasuan. Demagun, adibidez, txertatzeko ordenatu, Azkeneko hau algoritmoa jorratutako dugu, bertan izan begiratu elementutik digu, eta gero sartu da dagokion tokian. Eta gero, begiratu hurrengo elementua dugu, eta txertatuko da dagokion tokian. Beraz, kontuan hartu eta ahalik eta onena agertokia. Demagun nuen nire boluntarioek lerro sortu literalki honetan bezala, zortzi batetik, dagoeneko antolatuta. Zenbat urrats txertatzeko ordena Zortzi pertsona ordenatzeko hartu du, iritsiko dira eszenatokian bada Hau atsegin bila? Zortzi pertsona dagoeneko antolatuta. Eta txertatzeko ordenatu erabiltzen dut. Hori algoritmoen azken. Beno, goazen antzezten benetako azkar. Beraz, bada, hemen hasten naiz, inork ikusten dut. Nondik dator bat sartzen zara? Hementxe dagokio. Bi ikusten dut. Non sartzen duela bi? Hementxe. Hiru ikusten dut. Non hiru sartzen ez? Hementxe. Lau ikusten dut. Hementxe. Bost, sei, zazpi, zortzi. Ez dago neure burua errepikatzeko arrazoia. Eta urrats beraz, zenbat dela eta n dagokionez? Da n ordena on It urrats, ezta? n ken 1. Baina kopuru lineal bat hartu nuen Urratsen, eta orain egin naiz. Horregatik, kasu onena da, baina. Zer Kasu txarrena buruz? Zer zortzi baino gehiago egon ziren, eta zazpi behera ziren han, eta bat eta bi hemen baino gehiago izan ziren, beraz, Zerrenda hori benetan alderantzikatu ziren? Beno, zer gertatzen da, hain zuzen ere honetan zenbaki bada? Eta besterik ez, adibide pare bat egin dugu. Zer gertatuko da, hain zuzen ere, zortzi zenbakiaren Hemen da, eta zenbaki whoops. Beraz, zer bada, hain zuzen ere, kopurua Zortzi modu guztiak, hemen, eta txertatzeko ordena erabiltzen ari naiz? ONDO DA. Diotenez unea da leku egiten dut. Baina orain, seven-- non zazpi joan ez? Jakina, hemen baino gehiago doa. Beraz, zortzi mugitzeko leku bat baino gehiago daukat. Orain sei, non ez da joan? Konforme. Orain, zortzi mugitzeko gehiago dut leku bat, eta zazpi leku bat baino gehiago, eta, ondoren, behera plop dut sei. Beraz, lehen aldiz, kostu me urrats bat gauzak konpondu, ondoren, niri bi urrats kostatu gauzak konpondu. Zenbat urrats da konpondu hartzen joan Gauzak bost jarri leku egokian? Hiru. Orain ez daukat delako mugitu bat, bi, hiru. Zenbat urrats joan hartu da lau jarri leku egokian? 4 gehi 5, plus 6, plus 7. Eta beraz, matematikoki denaren berdina da zer deskribatu aukeraketa sort dugu. Serie honen daukagu hori besterik handituz. 1 eta 2 plus 3 eta 4, edo alderantziz, 7 plus 6 plus 5 plus 4 gehitzen gaurko for n ordenaren helburuetarako karratu. Hargatik gehiegi zeintzuk me burbuila sort da, halaber, karratu n. Burbuila ordenatu, bakoitzarekin delako denbora joan zerrendan zehar I, Urrats gutxi gorabehera zenbat hartzen ari naiz? Aldi bakoitzean nuen literalki hortik ez ibiltzera? Gutxi gorabehera n urratsak. Nola baina askotan agian I zerrenda bidez joan behar? Beno, gutxi gorabehera n denbora. Agian n ken 1, baina gutxi gorabehera n aldiz. Beno, zergatik da hori? Beno, burbuila sort, bada hasteko burbuila sort dugu, Posible txarrenean zerrenda batera egoera, eta horrek berriro guztiz atzeraka, zer gertatuko? Go zerrendan zehar I, eta kopuru Modu guztiak pertenece bat han. Baina burbuila sort, noraino du inork Nire zerrendan zehar lehen pass mugitzeko? Zenbat lekuak du lortu zuen leku egokian hurbiltzen da? Bakar bat. Beraz, mota horretako baduzu arrazoi honen bidez, algoritmo honen bidez, aldi bakoitzean, Daviden hartuz gutxi gorabehera n urratsak. Baina zenbat gaindituen zerrendan dela bitartez to bat hartu burbuila joan ezkerreko tokian nahi? Zuen lortu nahi bezala mugitzen, n espazioak modu hau. Beraz, besterik gabe, ordenazio egin Zerrendaren, Atzera eta aurrera ibiltzea n aldiz daukat. Eta aldi bakoitzean, naiz n elementu begira. Beraz, ez gauza nn aldiz on n ordena karratu. Orain, batzuk ikusi dugu Film labur duten dira CS50 hurrengo arazoa murgildurik ezarri, planteamendu beste hauek kontuan hartuz, baina, oraingoz, utzi kontuan hartu nahiko luke batzuk beste exekutatzen aldiz, batez ere, antolatzeko direnak hartu bada denbora pixka bat hondoratzea. Zer da dagoeneko ikusi dugu algoritmo bat Hori n urratsak ordena hartzen du? Zer kopurua lineal bat hartu behar ren urratsak horrela ikusten dugu orain arte? Zer da hori? The telefono direktorioa bilaketa. Lehenengo Algoritmoa. Eskuin? Non linealki gaude Mike Smith bila? Hain zuzen ere. Aste Zerotik, noiz hasi nintzen Orri bat inflexio aldi berean, eta, are gehiago, esan nuen nolako zela Sentimendu lineala algoritmo baten, eta irudi hori izan dugu Marra gorria taula eta horia lerroan, horiek izan ziren, hain zuzen ere Horren n O big daude algoritmoak. Mike Smith aurkitu telefono bat dagoelako n orriak, kasurik okerrenean ere liburuan, me n urratsak liteke. Asistentzia hartzeko zer? Bat, bi, hiru, lau, bost, sei. Zer da martxan honen denbora asistentzia hartzeko algoritmoa? Big n O, teorian dudalako denek seinalatu gelan dute. Ahora bat alde batera utzita, zeri buruz aste zero beste optimizazioa? Bi, lau, sei, zortzi, 10, 12. Ordenagailu litzateke zientzialari A konturatzen, minutu bat itxaron, duten ordena da n bi urrats arabera banatzen da. Eskuin? Bi pertsona egiten garai batean nagoelako. Baina ari gara alde batetara joan horiek ordena dagokionez txikiagoa, eta besterik ez gara joan bota kanpoan arrail 2 arabera, eta besterik esateko, big n O Algoritmo hori bai da. Eta honi buruz zer? Albo batera egingo dugu gorako horietako batzuk, baina zer algoritmoaren arrakasta n erregistroa izan zen? Hartu zuen gutxi gorabehera log n pausoak? Arrail eta konkistatzeko. Hain zuzen ere. Telefono-liburuan adibide bezala Aste zero eta gaur egun lehenago, non arazoa banatzen dugu eta berriro, behin eta berriro. Nik egin dugu aste batean taula gainean zero lerro berdea makurrak gisa, eta esan dugu, egun horretan izan zen logarithmic algoritmoa. Eta hain zuzen ere, kopurua urratsetan arrail egiteko eta konkistatzeko hartzen, edo bilaketa bitarra bezala, dugu hasteko deituz, telefono-liburuan bezala, erregistroa, eta urratsen ordena da. Eta hau bitxi bat pixka bat da. Zer urrats bat hartzen du, edo zehatzago esanda etengabeko urrats ematen? Agian bi da, agian, hiru da, baina ordenagailu zientzialari bat besterik ez sinplifikatzen da big 1 O bezala, urratsen kopurua konstante batzuk. Zer da zerbait egin izan duzu urratsen kopurua konstante bat hartzen? Zer da martxan txaloak momentuan? Etengabeko denbora. Eskuin? Atsegin dut, zer da exekutatzen garai Baten bat besterik hartzen ezer egin eragiketa, atsegin inprimatu F Hello World. Hori esan liteke etengabeko denbora izango da, gutxiago korner inprimatu F kasua ezean, zer gerta exekutatzen denbora inprimatu F benetan izan? Eta zergatik? Zer da n kasu horretan neurketa? Ikusleak: [INAUDIBLE]. DAVID J. MALAN: Zehazki. Karaktere kopurua inprimatu nahi dugu. Beraz, oso testuinguruaren da. Gaur egun, bada bat asko bideratua dugu Letrak eta zenbakiak hemen taula gainean. Baina, era berean izan zitekeen Benetako kate batean pertsonaiak. Beraz, bihurtzen da, ez da beste Neurri hori zaintzearen hasiko da, eta hori kontrakoa O handiak, nolabait esateko. Hori omega idazkera. Berriz O big esan zer da, orduan muga zure exekutatzen denbora? Gehienez, zenbat denbora Zerbait iraun dezake? Omega-- Sentitzen hau mantentzen datozen up-- horren aurkakoa da, Horren bidez, da txikiagoarekin doazen buruzko denbora zerbait kopuru bat beharko du. Hortaz esate baterako, zer da algoritmo bat garamatzan beti n karratu urratsak? Beno, algoritmo bat ikusi dugu gaur, hain zuzen ere, hori izan liteke, baita. Aukeraketa ordenatu. Aukeraketa ordenatu nahiko ergela. Algoritmo Sentitzen bada ere, are array dagoeneko horrela bada, hautaketa ordenatu joan mantendu zerrendan zehar oinez Ziur txikiena dauka egiteko elementu eta behin eta berriro berriro. Eta gizakiak nahiz Ikusleek badakiela, itxaron minutu bat, Dagoeneko pasatu behar du elementu txikiena, ordenagailua ez daki hori, itxura arte zerrendan zehar modu guztiak. Era berean, txikiagoa loturik dagoela agian kontuan hartu denbora lineala izan liteke. Zenbat denbora du hartu du moduko n onenetan elementu Kasu burbuila moduko zerbait erabiliz? Demagun zure zerrendan dagoeneko ordenatuko da. Esan dugu burbuila ordenatu hartzen n ordena karratu urratsak. Baina zer gertatzen da antolatuta dagoeneko? Zer konturatzen zara eta gero pass bat array bidez egin dituzula swaps no? Ez gehiago gainditu egiten jarraitu behar duzu? No. Beraz txikiagoa loturik burbuila moduko on esan liteke lineala izan. N Omega. Eta begiratu ahal izango dugu Horietako beste batzuk ere bai. Beraz, dezagun begirada bat besterik bistaratzea hemen nola horiek bereizteko beraiek ikusteko. Hemen jaisteko honetan sartu noa hori da C50 webgunean topatu orria, baina mina bat lan lortzeko izango da, izeneko teknologia erabiltzen geroztik Java appletak, hau da, bat neurri handi batean onartzen ez den egun hauetan, gutxienez Chrome eta beste batzuek arabera. Eta utzi aurrera me eta bizkortu honetan eman eta azaldu zer gertatzen den. Hau burbuila manifestazio bat da ordenatu, lehen bildu begiratzen dugu. Eta hori ere bistaratzea bakoitza da Taberna horietako zenbaki bat adierazten du. The handiagoa tabernan, handiagoa zenbakira. Txikiagoa tabernan, zenbaki txikiagoa. Eta zer ikusmen ikusi ahal izango dituzu, baita hau da, nahiz eta super azkar joan, zera dela, barra gorria ni bezalako da, atzera eta aurrera ibiltzeko arazoak konpontzen. Ikus dezakegu elementu handiagoa hain zuzen ere bubbling eskubidea, eta txikiagoa elementuak ezkerrean bubbling. Eta hemen behera, bagenu benetan hurbilagotik begiratu, Egia esan, ez dugu zenbatu ahal izango du konparazioak eta trukeak kopurua egiten ari ziren. Baina horren ordez, dezagun bigarren bildu at begiratu batera lehenago dugun gure boluntarioak, hautaketa ordena. Begien egiten du bat eragina oso desberdina. Baina, ez da berriro, oso intuitiboa, in hurrengo txikiena hautatuz mantentzen dugu elementu, eta guk apur bat zortea. Hori sentitu funtsean, azkarrago. Baina hau zuena, behin eta berriro badugu eta berriro sarrera asko, ikusiko genuke, hain zuzen ere badirela oraindik big n O karratu. Egin dezagun bat azkena utzi Hemen, txertatzeko ordenatu, bertan izan zen hirugarren algoritmoa begiratu, eta abisuaren dugu hau dela jorratzen Horietako topaketek bezala elementuak, baina gero agian txandatan da Gauzak baino gehiago gela egiteko, elementu non sartzen tartekatuz. Eta hau ere atzera bueltarik emanez azken emaitza. Orain guztia horietako hiru Nahiko azkar sentitu. Eta hain zuzen ere, horiek ran I clip nahiko ona zen. Baina, funtsean, guztiak ari dira nahiko izugarria, egia esateko. Algoritmo horiek guztiak orain arte n O big run duten karratu pixka bat nahiko hartu azkenean exekutatu denbora. Eta hain zuzen ere, ikusi ahal izango dugu eta sentitzen honetako azkenik tira dut hirugarren eta azken demo honetan bada. Hau da, beste bisualizazio hori joan ezkerrean burbuila ordenatu erakusteko, Aukeraketa erdian ordenatu, eta zerbait, bat bezala gure eskua altxatu lehenago iradoki, batu ordenatu eskuin hegaletik. Arrail A eta konkistatzeko estrategia eskuin hegaletik. Eta hori da, hain zuzen ere, zer ari gara begiratzen asteazkenean egingo da. Baina ez dezagun denbora horiek paraleloan exekutatu. Gutxi gorabehera kopuru bera da elementuak, guztiak aldi berean exekutatzen. Burbuila ordenatu vs aukeraketa moduko batu ordenatu vs. Orain, guztiak exekutatzen ari dira Aldi berean, teorian. PUZak berean exekutatzen abiadura berean, baina zuk sentitu daiteke nola aspergarria hau da bihurtu oso azkar doa, eta nola azkar denean Aste pixka bat injektatu dugu zero en algoritmoak ahal Gauzak bizkortzeko dugu martxan. Eta orain dezagun konparatu azken inprimaki bat horiek. Aurrera joan noa CS50 webgunean, nora Gaurko finalean link hau dugu, non norbait interneten atsegin handiz bildu bideo bat dagoela zer ordenazio ezberdinak aterako ditu algoritmoak soinua bezala. Hau txertatzeko ordena. [Beeping] Horren bidez, frekuentzia bat aplikatuz ari zaren oinarritutako bar barraren altuera gainean. Hau burbuila sort da. [Warped Beeping] Datozen hurrengo datozen is-- Hurrengo is-- aukeraketa ordenatu, non berriro, hautatzen ari garen hurrengo elementu txikiena, eta ikusi ahal izango dugu, gero eta handiagoa ezkerretik eskuinera. Batu ordenatu, beraz, gure irabazlea urrun gaur. Iragarki gauzak nola zatituz da [INAUDIBLE] erdia eta laurden sartu. Gnome ordenatu, eta hori ez daukagu buruz hitz egin zuen, eta sortzen ikusmen eta audally bat pixka bat forma eta soinu ezberdinak. Atzera eta aurrera, gauza garbiketa sortu. Era berean, begiratu heapsort Gizon honen webgunean. Eta hori da. Duzun hurrengoan ikusiko dugu. [Whooshing ETA MUSIKA]