1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> HIZLARIA: Ondo da, hau CS50 da. 3 00:00:14,910 --> 00:00:19,020 Hau astean hiru amaiera izango da, eta gero Ez baduzu aprobetxatu dagoeneko, 4 00:00:19,020 --> 00:00:21,790 Ezagutzen ez dagoela bazkaria izango da Ostiral honetan ohikoa, non gisa 5 00:00:21,790 --> 00:00:25,430 elkarrizketa ona gozatu ahal izango duzu eta Fire eta Ice at elikagaien 6 00:00:25,430 --> 00:00:27,980 CS50 batzuk dituzten langileei eta ikaskideei. 7 00:00:27,980 --> 00:00:30,170 URL hau hemen burua. 8 00:00:30,170 --> 00:00:33,420 >> Orain gogora ekarri ahal izango duzu, edo bestela, Baliteke izango laster ezagutu, 9 00:00:33,420 --> 00:00:35,970 gauza horiek hemen, ematen dira amaieran 10 00:00:35,970 --> 00:00:37,850 klaseak askotan seihilekoan. 11 00:00:37,850 --> 00:00:40,870 Proba orokorrak deiturikoak liburu urdina, eta bertan, zure erantzunak azterketak idatzi duzu. 12 00:00:40,870 --> 00:00:44,240 Orain hemen daukat 26, besteak beste, liburu urdina, horietako bakoitzean 13 00:00:44,240 --> 00:00:47,580 idatzita dagoen izen bat, A Z. bidez Eta hain zuzen ere, izen horiek simple, A daudela 14 00:00:47,580 --> 00:00:50,490 Z. bidez Eta bat gaur esku artean helburuak 15 00:00:50,490 --> 00:00:53,910 da zer jarraitzeko izango da hasi zen astelehenean dugu, eta hori ez da 16 00:00:53,910 --> 00:00:57,830 Hainbeste kodea begira, baina benetan ideiak eta arazoak konpontzeko begira. 17 00:00:57,830 --> 00:01:00,170 Helburuetako bat eta Ikastaro honen promesak 18 00:01:00,170 --> 00:01:02,985 da zuk gehiago pentsatzen irakasteko arretaz, gehiago metodikoki, 19 00:01:02,985 --> 00:01:05,400 eta arazoak konpontzeko ere modu eraginkorrean. 20 00:01:05,400 --> 00:01:09,526 Eta, hain zuzen, benetan egin ahal izango dugu nahiz eta kode-lerro bat ukitu gabe. 21 00:01:09,526 --> 00:01:12,150 Beraz, elefante pare bat daukat up hemen gaur, laranja eta urdina, 22 00:01:12,150 --> 00:01:15,780 boluntario bat eskuratu ahal izango bagenu, agian urrunago ohikoa baino back from. 23 00:01:15,780 --> 00:01:18,070 Nola bertan buruz, behera etorri dira. 24 00:01:18,070 --> 00:01:24,180 Horren helburua da ahal izango da lagun plus administratzeko azterketa hau hemen. 25 00:01:24,180 --> 00:01:24,935 Zein da zure izena? 26 00:01:24,935 --> 00:01:25,768 >> IKUSLEEN: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 HIZLARIA: Mary Beth, goazen gora. 28 00:01:27,560 --> 00:01:29,560 Let mikrofonoa get me hemen zuretzat. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Niza zu ezagutzeaz. 31 00:01:32,880 --> 00:01:34,005 >> IKUSLEEN: Niza zu ezagutzeaz. 32 00:01:34,005 --> 00:01:36,790 HIZLARIA: Ondo da, beraz, nik egin Hemen Z bidez liburu bat urdina, 33 00:01:36,790 --> 00:01:41,680 eta naiz duten asmoa dut Ikasle bat izan nuen, 34 00:01:41,680 --> 00:01:45,770 eta zertxobait ausaz ari dira datozen Hiru orduko azterketa-bloke baten amaieran, 35 00:01:45,770 --> 00:01:49,400 beraz ari bukatzen dute batzuetan hau bezalako erdi-ausaz. 36 00:01:49,400 --> 00:01:54,510 Orain zure une bat besterik ez da lan va hau da, benetan, nola lortuko dute jolasten 37 00:01:54,510 --> 00:01:56,820 gaurkoan ere amaieran klasea, ziurrenik. 38 00:01:56,820 --> 00:02:01,120 Zure lana orain arte izan nahiko joan, Besterik gabe, guretzat liburu urdin horiek ordenatzeko 39 00:02:01,120 --> 00:02:05,220 A-tik Z. bidez 40 00:02:05,220 --> 00:02:08,400 >> IKUSLEEN: Oh, hau da, betiko hartu du. 41 00:02:08,400 --> 00:02:13,747 >> HIZLARIA: Eta ikusten dugu egin duzun bezala, presioa ez. 42 00:02:13,747 --> 00:02:15,330 IKUSLEEN: Ez, presio edo ezer ez. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> HIZLARIA: Eta ondo pasatzeko, dezagun jarri tenporizadorea. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> IKUSLEEN: Beraz, askoz fun, hainbeste fun. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> HIZLARIA: mic eduki ahal dut zuretzat. 49 00:02:38,574 --> 00:02:40,240 Ondo da, nik besterik bikoiztu egin dugu gure abiadura. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Beraz, bien bitartean, utzi planteatzen me zer da Mary Beth galdera izango da 52 00:02:49,060 --> 00:02:51,540 hau da, zer da zuen egiten, nola da hau konpontzeko joan zen? 53 00:02:51,540 --> 00:02:54,040 Eta hain zuzen ere, agian ez dute Zerbait buruz inoiz pentsatu 54 00:02:54,040 --> 00:02:57,440 hain erraza denean jaso ahala 26 Honen antzeko liburu bat egin dute, 55 00:02:57,440 --> 00:02:59,350 Horiek egin eta natural bat izatea horiek ordenatzen. 56 00:02:59,350 --> 00:03:01,335 Zein da prozesua benetan erabili duzula? 57 00:03:01,335 --> 00:03:03,770 Nahiko ausazko besterik lehena ikusten duzu biltzea 58 00:03:03,770 --> 00:03:05,250 eta jarriz bere lekuan? 59 00:03:05,250 --> 00:03:09,680 Ez lehen, zure eskuak mugitu duzu orduan A B bila? 60 00:03:09,680 --> 00:03:11,722 Ez bat begirada bat hartu duzu aldamenean horietako bikotea 61 00:03:11,722 --> 00:03:14,680 eta besterik esateko, minutu bat itxaron, hau ez da eskubidea, eta ondoren trukatu ordena? 62 00:03:14,680 --> 00:03:16,960 Dagoeneko ikusi astelehenean dugu ez dagoela modu zenbaki bat 63 00:03:16,960 --> 00:03:22,140 eta bertan hau egin ahal izango dugu, eta hain zuzen bezala amaiera gertu dugu hemen, 64 00:03:22,140 --> 00:03:26,360 Ohar agian hartuko nuke zer of Mary Beth egiten ari da. 65 00:03:26,360 --> 00:03:30,040 Pila batzuk badirudi ditugu, bat handiagoak bat, txikiagoa, hiru direnak. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> IKUSLEEN: horiek ordenatzen ari naiz denean bi letra aurkitu dut 68 00:03:36,415 --> 00:03:39,540 ezagutzen dut elkarrekin dira sekuentzia batean, Horiek jarri dut elkarrekin, beraz, ez dut 69 00:03:39,540 --> 00:03:42,915 mantenduz kezkatu liburuak ilara oso baten arrastoa. 70 00:03:42,915 --> 00:03:45,706 Besterik, oh, A lehen da, Nik pila hau hemen. 71 00:03:45,706 --> 00:03:47,580 HIZLARIA: Beraz, ia bezala bat puzzle pieza dela 72 00:03:47,580 --> 00:03:49,860 eskuineko forma behar datoz bat elkarrekin. 73 00:03:49,860 --> 00:03:51,026 IKUSLEEN: Pretty much, bai. 74 00:03:51,026 --> 00:03:55,320 HIZLARIA: OK, bikaina. 75 00:03:55,320 --> 00:03:59,850 Eta orain, horietako bakoitzean pila ustez ordenatuko da? 76 00:03:59,850 --> 00:04:00,990 >> IKUSLEEN: Bai. 77 00:04:00,990 --> 00:04:09,900 >> HIZLARIA: Ondo da, A Z. All bidez eskuinera, zorionak, egin zenuen. 78 00:04:09,900 --> 00:04:11,461 Zure aukera daukazu. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Ondo da, eskerrik asko horren. 81 00:04:13,530 --> 00:04:16,679 Beraz Mary Beth zuen proposa zer bere planteamendu zen, 82 00:04:16,679 --> 00:04:19,720 baina zer hurbilketa bat da, nola duzu agian gauza horiek ordenatzeko buruz? 83 00:04:19,720 --> 00:04:21,130 Zer egin nahi duzu? 84 00:04:21,130 --> 00:04:24,060 Errekorra beat zatekeen minutu bat eta 50 edo segundo, 85 00:04:24,060 --> 00:04:26,039 plus direnak ahaztu dut zenbatu. 86 00:04:26,039 --> 00:04:27,080 Zer egin nahi duzu? 87 00:04:27,080 --> 00:04:27,579 Bai? 88 00:04:27,579 --> 00:04:28,735 IKUSLEEN: Hartu pila. 89 00:04:28,735 --> 00:04:29,776 Hasieratik hasi. 90 00:04:29,776 --> 00:04:32,284 Begiratu zure paperak. 91 00:04:32,284 --> 00:04:36,586 Eta inork goiko handiagoa bada baino, agian, dira, 92 00:04:36,586 --> 00:04:38,980 bat beheko aldean dagoen handiagoa, orduan piztu zien. 93 00:04:38,980 --> 00:04:41,300 >> HIZLARIA: OK, beraz, hasita goiko eta beheko aldean, 94 00:04:41,300 --> 00:04:43,716 eta, ondoren, lan your way barrurantz duten bezala, horien aldaketa? 95 00:04:43,716 --> 00:04:46,580 Ados, beraz, antzeko apur bat burbuila sort espirituz, 96 00:04:46,580 --> 00:04:49,160 baina muturren aukeratuz Ez ondoko bikoteak. 97 00:04:49,160 --> 00:04:52,080 Baina laburra da, ez dagoela ziur aski modu ezberdinak sorta bat 98 00:04:52,080 --> 00:04:54,210 hau egin ahal izan genuen, eta Egia, uste dut mota horretako 99 00:04:54,210 --> 00:04:55,700 Pare planteamendu bat onartu zuen, ezta? 100 00:04:55,700 --> 00:05:00,567 Lau pila ordenatuko moduko egin duzu, eta orduan eraginkortasunez batu itzazu elkarrekin. 101 00:05:00,567 --> 00:05:02,650 Eta hori da, daresay, beste Teknika guztira. 102 00:05:02,650 --> 00:05:06,950 Ez duzu pila handi bat bezala tratatzen, arazoa banatzen dituzun lau quads sartu, 103 00:05:06,950 --> 00:05:09,820 , izango da eta ondoren, nolabait bada batu zien azkenean. 104 00:05:09,820 --> 00:05:13,410 >> Beraz, kontuan hartu dezagun, azken finean, hau nola bestela ez genuke. 105 00:05:13,410 --> 00:05:15,860 Nozioa formalizatu dugu burbuila sort azken denbora, 106 00:05:15,860 --> 00:05:18,780 eta burbuila sort gogoratzen zen bat algoritmoa, bistaratzen dugu 107 00:05:18,780 --> 00:05:22,640 Zortzi sortu hemen zure ikaskideekin batera, itxuraz ausaz hasiera batean ordenatuta. 108 00:05:22,640 --> 00:05:26,110 Eta gero pairwise erabaki genuen, gero Bi elementu barrutitik kanpo daude, 109 00:05:26,110 --> 00:05:26,950 Besterik gabe trukatzeko. 110 00:05:26,950 --> 00:05:28,930 Beraz, lau eta bi dira jakina, ordena, 111 00:05:28,930 --> 00:05:31,080 beraz, bi ikaskideekin horiek posizioak piztuta. 112 00:05:31,080 --> 00:05:35,390 Eta gero errepikatu lau eta sei ginen, ondoren, sei eta zortzi, iterazio bakoitzean, 113 00:05:35,390 --> 00:05:36,980 eskuinera mugitzen. 114 00:05:36,980 --> 00:05:42,590 >> Beraz, emandako zortzi pertsonak, pairwise zenbat konparazioak zuen bitartean oinez egin nuen 115 00:05:42,590 --> 00:05:45,220 Ezkerretik eskuinera, besteak beste, iterazio batean? 116 00:05:45,220 --> 00:05:48,410 Zenbat konparazioak? 117 00:05:48,410 --> 00:05:49,197 Zazpi, ezta? 118 00:05:49,197 --> 00:05:51,405 Han zortzi bada delako Jende baina bikotea duzu 119 00:05:51,405 --> 00:05:53,880 horiek eta zuk mugitzen mantentzeko hop eskubidea inork, 120 00:05:53,880 --> 00:05:56,060 Ez bazara zortzi izan da joan konparazioak delako ezin duzu alderatu 121 00:05:56,060 --> 00:05:59,226 beraren aurka elementu bat, edo litzateke besterik izan pointless, beraz, behar duzu zazpi. 122 00:05:59,226 --> 00:06:01,290 Edo gehiago, oro har, bada n jendea behar dugu, ditugun 123 00:06:01,290 --> 00:06:04,300 Egin n ken 1 konparaketak burbuila ordenatu daitezke. 124 00:06:04,300 --> 00:06:08,150 >> Beraz, kontuan hartu dezagun orain nola ona edo burbuila txarra sort benetan izan zen, eta saiatu 125 00:06:08,150 --> 00:06:13,570 geure burua hiztegia emateko dituzten hau bezalako kritika algoritmoak zein, 126 00:06:13,570 --> 00:06:14,430 eta laster gure. 127 00:06:14,430 --> 00:06:16,970 Beraz bitartez lehen mendatean burbuila ordenatu, lehen aldiz 128 00:06:16,970 --> 00:06:20,909 Eskuineko zehar ibili da ezkerretik dut etapa, eraman ninduen n ken 1 konparazioak. 129 00:06:20,909 --> 00:06:22,950 Eta hori izango da nire neurri unitatea, ezta? 130 00:06:22,950 --> 00:06:26,170 Mota nintzen hitz egiten eta paseatzen, zertxobait azkar, zertxobait motela, 131 00:06:26,170 --> 00:06:29,300 beraz, nire segundo kopurua kontatuta Ez da bereziki kontatzea, 132 00:06:29,300 --> 00:06:32,260 baina kopurua zenbatuz Eragiketaren eta astelehenean egin nuen, 133 00:06:32,260 --> 00:06:35,900 Bi pertsona alderatuz, hori sentitzen neurri unitate polit bat bezala. 134 00:06:35,900 --> 00:06:40,980 >> Beraz, n ken 1 egoteagatik, lehen aldiz, baina gero zer gertatu zen gero? 135 00:06:40,980 --> 00:06:46,610 Zer da bat pass bat hankaz bestela Unsorted zerrenda baten bidez? 136 00:06:46,610 --> 00:06:49,840 Zer egin dezake elementua buruzko me esango dizu nork han modu guztiak izan zen? 137 00:06:49,840 --> 00:06:51,300 Bai? 138 00:06:51,300 --> 00:06:52,870 Hori elementu handiena izan zen, ezta? 139 00:06:52,870 --> 00:06:55,710 Zenbakia zortzi, nahiz eta zuen arren Hemen hasi zen, denbora dut behin 140 00:06:55,710 --> 00:06:57,860 aldean bere kontra bizilagun bat, berak mantendu 141 00:06:57,860 --> 00:07:00,480 sortu bubbling eskubidea eskuko zerrendaren alde. 142 00:07:00,480 --> 00:07:02,710 Eta hain zuzen ere, hori da, non algoritmoa bere izena du. 143 00:07:02,710 --> 00:07:07,630 >> Orain logika horren arabera, zenbat konparazioak Behar egin du bigarren aldiz egin dut 144 00:07:07,630 --> 00:07:09,800 Pass hori egin dut ezkerretik eskuinera? 145 00:07:09,800 --> 00:07:10,730 n ken 2, ezta? 146 00:07:10,730 --> 00:07:14,297 Besterik ez litzateke izango alferrik galtzen nire denbora badut konparatuz zortzi norbaiten aurka mantentzeko 147 00:07:14,297 --> 00:07:16,630 bestela badakigu delako leku egokian zegoen. 148 00:07:16,630 --> 00:07:19,760 Beraz, apur bat optimizazioa, beraz, hurrengo pass 149 00:07:19,760 --> 00:07:23,899 da izan plus n ken bi urrats egingo, non n pertsonen kopurua da. 150 00:07:23,899 --> 00:07:26,940 Orain motatako estrapolatu ahal izango duzu, nahiz eta ez bazaude, ordenagailu zientzialari bat, 151 00:07:26,940 --> 00:07:27,680 nola bukatuko du. 152 00:07:27,680 --> 00:07:31,259 Algoritmo honen amaieran, zentzuzkoa lortu duzun besterik konparaketa bat utzi. 153 00:07:31,259 --> 00:07:33,800 Mota konpondu behar duzu zerrendaren hasieran kasu bitan 154 00:07:33,800 --> 00:07:36,540 eta bat barrutitik kanpo daude eta bat eta bi izan beharko luke, 155 00:07:36,540 --> 00:07:40,330 beraz, hau ipurdiak out at plus 1 final alderatuz. 156 00:07:40,330 --> 00:07:44,500 >> Orain dot, dot, dot uhinak mota da, Xehetasun juicier batzuk eskuetan, 157 00:07:44,500 --> 00:07:46,452 baina dezagun besterik aurretik eta errazteko. 158 00:07:46,452 --> 00:07:48,660 Gogoratzen baduzu, goi-tik eskola, Egia, zuk asko 159 00:07:48,660 --> 00:07:50,340 math liburuak izan zuela apur bat Cheat fitxa 160 00:07:50,340 --> 00:07:52,550 azala edo on- Atzeko estalkia dela erakutsi duzu 161 00:07:52,550 --> 00:07:56,400 like zer serie summations hau da, azken finean erantsia sortu ahal izateko. 162 00:07:56,400 --> 00:07:59,600 Kasu orokorrean esanda, bat baduzu n aldagai, eta hain zuzen ere, hau, 163 00:07:59,600 --> 00:08:01,634 begiratu baduzu at your eskola zaharra matematikako liburu, 164 00:08:01,634 --> 00:08:04,050 zuk ikusi nahi hau benetan gehitzen batura hau hemen, 165 00:08:04,050 --> 00:08:07,970 n aldiz n ken 1 guztietan 2 banatuta. 166 00:08:07,970 --> 00:08:11,172 Beraz, oraingoz utzi zeintzuk besterik me hau da, egia, beraz, fede-jauzi baten gainean, 167 00:08:11,172 --> 00:08:12,880 hori da hori zer batzen gehienez, eta ezin izan dugu 168 00:08:12,880 --> 00:08:14,341 frogatzeko kasu orokorrago batean. 169 00:08:14,341 --> 00:08:15,590 Baina orain utzi zabaltzeko en hau. 170 00:08:15,590 --> 00:08:19,920 Hargatik biderkatu hau, beraz, n karratu, ken n, 2 arabera banatzen da. 171 00:08:19,920 --> 00:08:23,200 Hori da benetan n karratu, minus n 2 baino gehiago 2 arabera banatzen da,, 172 00:08:23,200 --> 00:08:25,010 beraz, horrek guztiak polita eta interesgarria da. 173 00:08:25,010 --> 00:08:27,060 Baina zer dugu bada gertatzen orain plug-in balio bat? 174 00:08:27,060 --> 00:08:29,724 Demagun ez nuen zortzi jendea, baina esan milioi bat. 175 00:08:29,724 --> 00:08:31,890 Eta milioi bat besterik ez delako kopuru nahiko handi bat da, 176 00:08:31,890 --> 00:08:34,039 dezagun plug direla eta ikusi zer gertatzen den. 177 00:08:34,039 --> 00:08:39,039 Beraz, milioi bat konektatzen dut formula sartu bada Milioi bat karratu lortzeko noa, 178 00:08:39,039 --> 00:08:42,868 2 arabera banatzen da, ken bat milioi, 2 banatuta. 179 00:08:42,868 --> 00:08:44,159 Orain zer hori berdinak joan? 180 00:08:44,159 --> 00:08:47,354 Beraz, 500 milioi, ken 500.000. 181 00:08:47,354 --> 00:08:49,270 Eta badut benetan egiten matematika dagoela out, esan nahi duen 182 00:08:49,270 --> 00:08:53,920 duten sailkatzeko milioi bat burbuila sort dituzten pertsonak 183 00:08:53,920 --> 00:09:01,800 me har dezake 499.999.500.000 Azkenean, maldarik eta konparazioak, 184 00:09:01,800 --> 00:09:02,900 ari gara estrapolatu. 185 00:09:02,900 --> 00:09:06,860 >> Hori sentitzen nahiko motela, baina Egia sarrera jakin bat neurtzeko 186 00:09:06,860 --> 00:09:09,160 hau bezala, ez da kontatzeko duten guztiak. 187 00:09:09,160 --> 00:09:14,050 Baina, hain zuzen ere iradokitzen n bezala hori ez da handiagoa eta handiagoa, algoritmo hau lortzen 188 00:09:14,050 --> 00:09:16,280 mota sentitzen okerragoa eta okerrago, edo benetan 189 00:09:16,280 --> 00:09:20,450 hartako mina sentitzen hasten berredura, n karratu, 190 00:09:20,450 --> 00:09:21,770 eta horrek gehitzen nahiko azkar. 191 00:09:21,770 --> 00:09:25,340 Eta xehetasun hori ez da Jende galdu, hain zuzen ere 192 00:09:25,340 --> 00:09:29,640 Duela urte batzuk, senatari jakin bat izan zen kanpainen, eseri elkarrizketa bat 193 00:09:29,640 --> 00:09:32,180 Google-en Eric Schmidt, garai hartan zuzendari nagusia, 194 00:09:32,180 --> 00:09:36,380 eta galdera batekin zen erronka askoz bezala gaur esploratzen ari gara. 195 00:09:36,380 --> 00:09:38,468 Ikus dezagun begirada bat. 196 00:09:38,468 --> 00:09:45,280 >> [Bideo-erreprodukzioa] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Zu hemen Google at, eta gustatzen 198 00:09:48,560 --> 00:09:53,382 lehendakaritza pentsatzea Lan elkarrizketa bat bezala. 199 00:09:53,382 --> 00:09:56,434 Orain, zaila da iritsi presidente gisa lan bat, 200 00:09:56,434 --> 00:09:58,100 eta orain rigors bidez ari zaren. 201 00:09:58,100 --> 00:10:01,860 Era berean, zaila da lan bat lortzeko Google at. 202 00:10:01,860 --> 00:10:05,490 Galdera bat daukagu, eta guk gure hautagaien galderak, 203 00:10:05,490 --> 00:10:09,770 eta Larry Schwimmer da. 204 00:10:09,770 --> 00:10:14,760 What-- naiz uste duzu guys Txantxetan, hementxe da. 205 00:10:14,760 --> 00:10:17,930 Zein da modurik eraginkorrena milioi eta 32-bit-eko osokoak ordenatzeko? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -I'm Barkatu, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> -No, Ez, ez. 210 00:10:27,400 --> 00:10:30,700 Burbuila moduko uste dut joan okerreko bidea izango litzateke. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Come, Nork esan zion hau? 213 00:10:38,180 --> 00:10:40,590 Ez nuen ordenagailuan ikusi Zure atzean zientzia. 214 00:10:40,590 --> 00:10:42,130 >> -We've Gure espioiak Han lortu. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -Ados, Dezagun eskatu desberdin bat elkarrizketa galdera. 217 00:10:48,444 --> 00:10:49,300 >> [END bideo-erreprodukzioa] 218 00:10:49,300 --> 00:10:52,290 >> HIZLARIA: Beraz, buruz hitz egiten zenbaki jakin arren, 219 00:10:52,290 --> 00:10:53,890 guztiak baliagarriak izan ez da joan. 220 00:10:53,890 --> 00:10:56,810 Ez da bizitza ikasgai bat burbuila duten It ordenatu, emandako milioi bat sarrera, 221 00:10:56,810 --> 00:10:58,590 bezain beste 500 milioi urrats bat beharko du. 222 00:10:58,590 --> 00:11:01,120 Ezin duzu benetan orokortu too horretatik aurrera eraginkortasunez 223 00:11:01,120 --> 00:11:03,560 eta diseinu ona erabakiak denean programak idaztea. 224 00:11:03,560 --> 00:11:07,070 Hargatik zentratu dezagun nola on arren Emaitza hori errazteko genuke. 225 00:11:07,070 --> 00:11:11,780 >> Beraz horia Nik azpimarratu hemen n emaitza karratu 2 arabera banatzen da, 226 00:11:11,780 --> 00:11:14,330 beraz, milioi bat karratu 2 arabera banatzen da, eta, ondoren, 227 00:11:14,330 --> 00:11:16,710 Azpimarratu dut zer azken erantzuna izan zen 228 00:11:16,710 --> 00:11:20,180 Behin off kentzen dugu n 2 banatuta. 229 00:11:20,180 --> 00:11:24,850 Eta erreklamazioa naiz egin orain gertatzen ari da, nor demontre zaintzen off kentzen baduzu 230 00:11:24,850 --> 00:11:30,060 zahar bat 2 gehiagoko n little denean lehenengoa formula horren parte da, beraz, askoz handiagoa? 231 00:11:30,060 --> 00:11:33,910 Bestea nagusitzen da terminoa, n karratu 2 banatuta 232 00:11:33,910 --> 00:11:37,510 da, beraz, askoz handiagoa da, argi eta garbi, hala n lortzen milioi bat bezala handiak, 233 00:11:37,510 --> 00:11:41,450 dela bertan benetan diferentzia handi bat 500 mila milioi artean egunaren amaieran 234 00:11:41,450 --> 00:11:45,730 eta 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Ez da benetan. 236 00:11:46,349 --> 00:11:48,640 Eta beraz, zer goaz egin bezala informatikariak da 237 00:11:48,640 --> 00:11:53,270 ordena terminoak txikiagoa alboratu eta hau eta benetan horrelako zerbait hartu 238 00:11:53,270 --> 00:11:56,050 besterik errazteko egiten den epe hori da axola. 239 00:11:56,050 --> 00:12:00,315 Handiagoa gure datu multzoak lortzeko, handiagoa Gure datu-base lortzeko, web orri gehiago 240 00:12:00,315 --> 00:12:02,690 , gehiago bilatu behar dugu lagun Facebooken duzu. 241 00:12:02,690 --> 00:12:07,340 >> N handiagoa lortzen bezala, benetan ari gara to handienetako buruzko zaintzeko joan 242 00:12:07,340 --> 00:12:11,560 hala nola, edozein azterketa epe gure algoritmoak performance. 243 00:12:11,560 --> 00:12:16,230 Eta ez dut esan nahi, badakizu zer, burbuila sort O big ordena da, 244 00:12:16,230 --> 00:12:18,060 n ordena karratu. 245 00:12:18,060 --> 00:12:20,090 Ez da zehazki n Nik ikusi dugun bezala karratu, 246 00:12:20,090 --> 00:12:22,060 baina benetan zaintzen Termino txikiagoa dutenei buruz, 247 00:12:22,060 --> 00:12:24,390 eta Egia, benetan zaintzen zatitzen dugu 2-k, bada? 248 00:12:24,390 --> 00:12:25,870 Hori konstante bat besterik ez. 249 00:12:25,870 --> 00:12:29,480 Eta 500 milioi versus 250 da milioi benetan aurre big? 250 00:12:29,480 --> 00:12:32,190 Besterik ezin dut urtebete itxaron, utzi nire laptop literalki 251 00:12:32,190 --> 00:12:34,810 lortzeko bi aldiz azkarrago hardwarean, eta desberdintasun moduko hori 252 00:12:34,810 --> 00:12:36,650 besterik ez doa urrun naturalean denboran zehar. 253 00:12:36,650 --> 00:12:39,300 >> Zer ardura dugulako da adierazpena, zatia 254 00:12:39,300 --> 00:12:42,489 adierazpen hori aldatu egiten joan gure sarrera handiagoa eta handiagoa lortzen. 255 00:12:42,489 --> 00:12:45,280 Eta hain zuzen ere, mundu errealean, hori da gero eta gertatzen ari 256 00:12:45,280 --> 00:12:48,330 da gure arazoei sarrera eta algoritmoak dira handiagoa lortzean. 257 00:12:48,330 --> 00:12:53,470 Beraz, O big da idazkera izango da, the asymptotic notazioa dugu hori besterik 258 00:12:53,470 --> 00:12:57,160 informatikariak azaldu behar bezala erabili errendimendua, edo exekutatzen denbora, 259 00:12:57,160 --> 00:12:58,130 algoritmo bat. 260 00:12:58,130 --> 00:13:00,800 Beraz, algoritmo alderatu dezakegu idatzizko ordenagailu ezberdinetan 261 00:13:00,800 --> 00:13:04,170 pertsona desberdinek, erabiliz funtsean antzekoak metriko batzuk 262 00:13:04,170 --> 00:13:07,557 konparazioak zenbaki bezala Oraindik , trukeak kopuruan eginez edo agian 263 00:13:07,557 --> 00:13:08,140 egiten ari zaren. 264 00:13:08,140 --> 00:13:11,910 >> Zer ez gara joan Aldaketa denbora kopurua da 265 00:13:11,910 --> 00:13:13,981 duen erlojua pasatzen hormaren normalean. 266 00:13:13,981 --> 00:13:16,230 Zer ez gara kezkatu joan buruz zenbat memoria 267 00:13:16,230 --> 00:13:17,820 gaur egun erabiltzen ari zaren gutxienez, nahiz eta hori 268 00:13:17,820 --> 00:13:19,370 beste baliabide liteke neurtzen dugu. 269 00:13:19,370 --> 00:13:23,610 Gure analisiak oinarritzeko saiatzen gara oinarrizko eragiketak, direnak, 270 00:13:23,610 --> 00:13:25,930 Egia, gehienetan begiz ikusi ahal izango duzu. 271 00:13:25,930 --> 00:13:30,700 Beraz, big n O antzeko zerbait karratu, hori, n karratu O aldarrikatzen dut 272 00:13:30,700 --> 00:13:35,820 da goiko deiturikoak doazen burbuila sort denbora exekutatzen. 273 00:13:35,820 --> 00:13:38,820 Beste era batera esanda, nahi baduzue Ba hori da aldarrikatzen nahi izan 274 00:13:38,820 --> 00:13:41,370 zenbat muga goiko honetan algoritmo bat igaro daiteke urrats, 275 00:13:41,370 --> 00:13:46,240 nik nahi big n O egon joan kasu honetan, karratu, goi-muga bat. 276 00:13:46,240 --> 00:13:49,710 >> Zer I ordez aldatzen baldin Istorioa ez burbuila sort buruz izango da, 277 00:13:49,710 --> 00:13:50,910 baina goiko doazen buruz. 278 00:13:50,910 --> 00:13:54,030 Ezin duzu algoritmo bat pentsatzea Dagoeneko at dugun begiratu ditudan 279 00:13:54,030 --> 00:13:59,530 horren goi-muga, gehienez denbora edo eragiketak neurtu, 280 00:13:59,530 --> 00:14:04,300 esan beharko litzateke mugatzen beharreko ek n, funtzio lineal bat, 281 00:14:04,300 --> 00:14:07,260 Ez quadratic bat hori da makurrak? 282 00:14:07,260 --> 00:14:10,780 Zer da algoritmo bat Beti hartzen ez gehiago 283 00:14:10,780 --> 00:14:12,860 n urratsak, edo nahi baino 2n urratsak, edo 3N urratsak? 284 00:14:12,860 --> 00:14:13,360 Bai? 285 00:14:13,360 --> 00:14:15,030 >> IKUSLEEN: aurkitzea zerrenda batean kopuru handiena? 286 00:14:15,030 --> 00:14:16,930 >> HIZLARIA: Perfect, aurkitzeko zerrenda batean zenbaki handiena. 287 00:14:16,930 --> 00:14:18,940 Zerrenda bat naiz ematen badu adibidez pertsonak, 288 00:14:18,940 --> 00:14:21,440 nor bakoitzari zenbaki bat antolatzen, zer gehieneko kopurua da 289 00:14:21,440 --> 00:14:23,770 urratsen me hartu behar da, Pertsona arrazoiz adimendun bat, 290 00:14:23,770 --> 00:14:27,530 Zerrenda horretan pertsonaren handiena aurkitu? 291 00:14:27,530 --> 00:14:28,100 n, ezta? 292 00:14:28,100 --> 00:14:31,320 Kasurik okerrenean ere, bertan dagoelako agian balio handiena izan? 293 00:14:31,320 --> 00:14:32,700 Eskuin, amaieran modu guztiak. 294 00:14:32,700 --> 00:14:34,575 Beraz, kasu txarrenean Goiko doazen, I might 295 00:14:34,575 --> 00:14:36,450 modu guztiak joan behar hemen baino gehiago eta antzekoak izan, 296 00:14:36,450 --> 00:14:39,170 Oh, hemen zenbakia zortzi, edo balio hori da, edozein dela ere. 297 00:14:39,170 --> 00:14:41,330 Orain besterik ez litzateke izango da ergelak , eskuinera joan mantenduko badut? 298 00:14:41,330 --> 00:14:43,840 Gero eta gehiago, elementu bila Horietako azkena ez da bada? 299 00:14:43,840 --> 00:14:45,340 Beraz, ziur aski, n goi-muga da. 300 00:14:45,340 --> 00:14:47,420 Ez dut behar den hartu Hori baino urrats gehiago. 301 00:14:47,420 --> 00:14:51,580 >> Beraz, zer ordez bada proposatu nuela daude mundu honetan algoritmoek duten 302 00:14:51,580 --> 00:14:57,750 hori burutzeko denbora bat dute log n O big mugatzen, log n? 303 00:14:57,750 --> 00:15:00,390 Non egin dugu hau ikusi aurretik? 304 00:15:00,390 --> 00:15:00,890 Bai? 305 00:15:00,890 --> 00:15:03,309 >> IKUSLEEN: telefono-liburuaren arazoa ere? 306 00:15:03,309 --> 00:15:04,850 HIZLARIA: telefono-liburuaren arazoa bezala. 307 00:15:04,850 --> 00:15:07,754 Zein izan zen nola neurria askoz denbora edo zenbat malkoak da 308 00:15:07,754 --> 00:15:10,170 hartu zuen bezalako norbait aurkitu me Mike Smith telefono liburuan? 309 00:15:10,170 --> 00:15:13,212 Izan zen log n aldarrikatu dugu, eta Ohituta bada edota hura izan 310 00:15:13,212 --> 00:15:15,170 hazy apur bat zer bat Logaritmo edo adierazgarri izan zen, 311 00:15:15,170 --> 00:15:17,650 besterik gogoratzen log n oro har, prozesua aipatzen du, 312 00:15:17,650 --> 00:15:20,790 kasu honetan, zatituz erdia zerbait berriro, eta berriro, 313 00:15:20,790 --> 00:15:25,790 eta berriro, eta berriro, hala nola egiten duten geroz eta txikiagoa lortzen duten egiten duzun bezala. 314 00:15:25,790 --> 00:15:28,470 >> Beraz, saioa n aipatzen da, ziur, telefono-liburua adibide izateko, 315 00:15:28,470 --> 00:15:32,662 teorian bilaketa bitarra, dugunean taula gainean ateak birtualak izan, 316 00:15:32,662 --> 00:15:34,370 edo Sean zen denean zerbait bilatzen. 317 00:15:34,370 --> 00:15:37,374 Zuen erabilitako bilaketa bitarra bada, log n zenbat buruzko goi-muga izango litzateke 318 00:15:37,374 --> 00:15:38,040 duten denbora. 319 00:15:38,040 --> 00:15:44,027 Baina hori ere ran algoritmo horiek log n gain hartu zer gako zehatz-mehatz? 320 00:15:44,027 --> 00:15:45,360 Zerrendan ordenatuko zen hura, ezta? 321 00:15:45,360 --> 00:15:47,789 Zure algoritmoa gaizki bada Zure sarrera ez dago ordenatuta, 322 00:15:47,789 --> 00:15:49,830 eta oraindik erabiltzen ari zaren bilaketa bitarra antzeko zerbait 323 00:15:49,830 --> 00:15:51,704 agian salto egin delako eskuineko elementu baino gehiago 324 00:15:51,704 --> 00:15:53,600 konturatu gabe, hain zuzen ere hor da. 325 00:15:53,600 --> 00:15:55,600 >> Orain zer hau esan dezake, bietako bat O big? 326 00:15:55,600 --> 00:15:59,117 Horrek ez du esan nahi zure algoritmoa, bat eta urrats bat bakarrik hartzen du, 327 00:15:59,117 --> 00:16:01,200 Esan nahi du, besterik ez da, asko kostatzen etengabeko urrats kopurua. 328 00:16:01,200 --> 00:16:04,060 Agian aurten 1, agian, da 10, agian 1.000, 329 00:16:04,060 --> 00:16:07,750 baina independentea da arazoaren tamaina. 330 00:16:07,750 --> 00:16:10,850 Ez dio axola nola handi n da, Etengabeko denbora algoritmoa 331 00:16:10,850 --> 00:16:12,747 Beti urrats kopuru bera hartzen du. 332 00:16:12,747 --> 00:16:15,080 Beraz, zer algoritmo bat izan daiteke edo, besterik gabe, hitz egin dugu 333 00:16:15,080 --> 00:16:20,418 intuizioa duzula dator beti doa denbora etengabe deiturikoak? 334 00:16:20,418 --> 00:16:20,918 Bai? 335 00:16:20,918 --> 00:16:22,001 >> IKUSLEEN: bi zenbakiak gehitu. 336 00:16:22,001 --> 00:16:25,320 HIZLARIA: Gehitu bi zenbaki, 2 gehi 2 berdin 4, egin. 337 00:16:25,320 --> 00:16:27,227 Beraz, lan egin dezake, zer gehiago? 338 00:16:27,227 --> 00:16:28,560 Nola mundu errealean buruz, bai? 339 00:16:28,560 --> 00:16:30,686 >> IKUSLEEN: aurkitzea zerrenda batean lehen gauza. 340 00:16:30,686 --> 00:16:32,810 HIZLARIA: lehena aurkitzea Zerrenda bateko elementu, ziur. 341 00:16:32,810 --> 00:16:34,540 Nik benetan hitz egiten dugu array dagoeneko buruz, 342 00:16:34,540 --> 00:16:36,540 nola lortu aztertzea array baten lehenengo elementua, 343 00:16:36,540 --> 00:16:40,465 ez du axola zenbat denbora array C kodea da? 344 00:16:40,465 --> 00:16:43,090 Parentesi bezala erabiltzea besterik ez duzu zero idazkera, bam, zauden. 345 00:16:43,090 --> 00:16:46,120 Eta hain zuzen ere, array, alde batera utzita, laguntza zerbait oro har, ezagutzen 346 00:16:46,120 --> 00:16:49,240 ausazko sarbidea bezala, ausazko sarbidea memoria, literalki ahal duzu delako 347 00:16:49,240 --> 00:16:50,284 bat edozein leku salto. 348 00:16:50,284 --> 00:16:52,700 Besterik gabe, hau da, are gehiago egin ahal izango dugu Aste zero dugu atzeratzeko ahal 349 00:16:52,700 --> 00:16:53,900 denean Scratch egin dugu. 350 00:16:53,900 --> 00:16:59,707 Zenbat denbora ez da hartu du esan Scratch blokea exekutatu? 351 00:16:59,707 --> 00:17:00,790 Just denbora etengabe, ezta? 352 00:17:00,790 --> 00:17:03,960 Esan zerbait, esan zerbait, ez du axola 353 00:17:03,960 --> 00:17:07,359 Marratu big mundua nola dagoen, beti da denbora kopuru bera hartu du 354 00:17:07,359 --> 00:17:08,490 besterik gabe, zerbait esan. 355 00:17:08,490 --> 00:17:11,089 >> Beraz, etengabeko denbora da, baina zer da flip aldean? 356 00:17:11,089 --> 00:17:13,030 Hori izan zen, goiko badu mugetatik kanpo, zer nahi badugu 357 00:17:13,030 --> 00:17:17,089 beheko mugetatik deskribatzeko gure algoritmoak exekutatzen denbora? 358 00:17:17,089 --> 00:17:19,852 Ia kasu onena bat potentzialki, izango bada, 359 00:17:19,852 --> 00:17:23,060 ezin baldintza hauek hoberenak aplikatu arren kasu, kasu txarrenean, batez beste kasu gehiago 360 00:17:23,060 --> 00:17:26,359 oro har, baina utzi pilatzen dira, besterik gabe mugetatik txikiagoa orohar. 361 00:17:26,359 --> 00:17:31,920 Zer da duela algoritmo bat baxuagoa n urrats lotuak, 362 00:17:31,920 --> 00:17:33,350 edo 2n urratsak, edo 3N urratsak? 363 00:17:33,350 --> 00:17:36,241 N urrats faktore batzuk, duela loturik bertako txikiagoa. 364 00:17:36,241 --> 00:17:36,740 Bai? 365 00:17:36,740 --> 00:17:37,910 >> IKUSLEEN: Burbuila sort? 366 00:17:37,910 --> 00:17:41,610 >> HIZLARIA: burbuila moduko hartzen you txikieneko n urratsak, zergatik? 367 00:17:41,610 --> 00:17:42,279 Zergatik da hori? 368 00:17:42,279 --> 00:17:45,320 Zergatik behar da hasieratik duzula etortzen senez, egiten du, nahiz eta ez soilik 369 00:17:45,320 --> 00:17:46,530 hala ere? 370 00:17:46,530 --> 00:17:47,030 Bai? 371 00:17:47,030 --> 00:17:47,990 >> IKUSLEEN: [INAUDIBLE]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 HIZLARIA: Zehazki. 374 00:17:52,360 --> 00:17:55,810 Ahalik eta eszenatoki onenetan burbuila ordenatu, eta algoritmo asko, 375 00:17:55,810 --> 00:17:58,769 Eskuz dut bada zortzi pertsona nork antolatuko dira dagoeneko, 376 00:17:58,769 --> 00:18:00,560 inozoak izango litzateke zuretzat, algoritmoa, 377 00:18:00,560 --> 00:18:02,202 atzera eta aurrera joan behin baino gehiagotan, ezta? 378 00:18:02,202 --> 00:18:04,285 Bezain laster bera zerrendan zehar oinez behin, 379 00:18:04,285 --> 00:18:08,090 Jakin behar duzu, oi, egin nuen ez trukeak, zerrenda honetan ordenatuko da, irteera. 380 00:18:08,090 --> 00:18:09,700 Baina hori ez da n urratsak egingo. 381 00:18:09,700 --> 00:18:12,033 >> Eta alderantziz, zer da beste horri buruz pentsatzeko bidea? 382 00:18:12,033 --> 00:18:15,240 Burbuila sort omega da, , n beraz, hitz egiteko, 383 00:18:15,240 --> 00:18:19,050 begiratuz gero delako n baino gutxiago elementuak, zer 384 00:18:19,050 --> 00:18:23,009 du oinarrizko arazoa da, ez? 385 00:18:23,009 --> 00:18:24,550 Ez dakizu horrela antolatu bada, eskubidea. 386 00:18:24,550 --> 00:18:26,800 Agian begirada gizakiak gara zortzietan pertsona eta antzekoak izan, ai, eta ordenatuko, 387 00:18:26,800 --> 00:18:28,430 ez zuela hartu me n urratsak, baina egin. 388 00:18:28,430 --> 00:18:30,810 Zure begiak, nahiz eta mota nahiz buruz duten ikuspegia eremuan handi bat, 389 00:18:30,810 --> 00:18:33,184 begiratu zortzi elementu at duzu, begiratu zortzi pertsona duzu, 390 00:18:33,184 --> 00:18:34,610 zortzi urrats eraginkorrean. 391 00:18:34,610 --> 00:18:38,612 Eta oinez I osoan zehar bada soilik zerrenda egin, konturatu naiz bai, ordenatuta. 392 00:18:38,612 --> 00:18:41,320 I gelditu bada erdibidean, pentsamendu guztiak eskuinera, polita da antolatuz, orain arte, 393 00:18:41,320 --> 00:18:42,520 zer dira odds Ez da antolatuz? 394 00:18:42,520 --> 00:18:44,186 Hori ez algoritmoak zuzena izango. 395 00:18:44,186 --> 00:18:46,250 Azkarrago, baina okerra izatea. 396 00:18:46,250 --> 00:18:48,500 >> Beraz, gaur egun modu bat dugu a mugetatik txikiagoa deskribatzen, 397 00:18:48,500 --> 00:18:49,710 eta denbora konstante buruz zer? 398 00:18:49,710 --> 00:18:54,565 Zer da duela txikiagoa algoritmo bat loturik bere entzierro bat denbora? 399 00:18:54,565 --> 00:18:58,350 Urratsa 1, 2 urrats, 10 urrats, baina konstantea, n independentea, 400 00:18:58,350 --> 00:18:59,310 sarrera-tamaina? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Bai, berriro. 403 00:19:04,600 --> 00:19:05,309 >> IKUSLEEN: Printf? 404 00:19:05,309 --> 00:19:06,183 HIZLARIA: Zer da hori? 405 00:19:06,183 --> 00:19:07,184 IKUSLEEN: Printf? 406 00:19:07,184 --> 00:19:07,850 HIZLARIA: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, ziur. 408 00:19:08,400 --> 00:19:10,720 Beraz, urrats kopuru finko bat hartzen du. 409 00:19:10,720 --> 00:19:13,170 Eta orain, orain behar dut dugu C kodea buruz hitz egiten ari 410 00:19:13,170 --> 00:19:16,040 eta ez Scratch, zerbait bezala esan, printf batera, 411 00:19:16,040 --> 00:19:17,710 zaindua izaten hasi behar dugu. 412 00:19:17,710 --> 00:19:21,090 Printf delako hartu du sarrera, kate bat da, 413 00:19:21,090 --> 00:19:23,220 eta kateak ez teknikoki dute luzera. 414 00:19:23,220 --> 00:19:25,530 Beraz, orain arte jaso nahi badugu duzu, ez baduzu axola, 415 00:19:25,530 --> 00:19:29,430 Teknikoki printf dela argudiatu genezake du hartzen luzera aldakorreko sarrera bat, 416 00:19:29,430 --> 00:19:32,270 eta ziur aski gehiago iraun dezake denbora kate bat inprimatu behar da hau luzea, 417 00:19:32,270 --> 00:19:33,560 luze hau baino. 418 00:19:33,560 --> 00:19:36,570 >> Beraz, zer besterik ez dugu kontuan hartu bada sailkatzeko eta adibideak bilatzen? 419 00:19:36,570 --> 00:19:40,450 Mike Smith telefonoan zertaz liburu edo bilaketa bitarra orokorrago? 420 00:19:40,450 --> 00:19:42,220 Kasurik onenean ere, zer gerta liteke? 421 00:19:42,220 --> 00:19:45,577 Telefono-liburua ireki nuen eta, bam, han Mike Smith-zenbakia. 422 00:19:45,577 --> 00:19:46,660 Berehala ahal nion deitu. 423 00:19:46,660 --> 00:19:49,390 >> Urrats bat, agian bi urratsak eman zituen, baina etengabeko urrats 424 00:19:49,390 --> 00:19:50,230 zortea dut bada. 425 00:19:50,230 --> 00:19:52,570 Eta Egia, ikusi dugu Astelehena zure ikaskide 426 00:19:52,570 --> 00:19:54,710 eskuratu nahiko zortea birritan segidan. 427 00:19:54,710 --> 00:19:57,050 Eta hori konstante izan zen, hain zuzen ere a mugetatik txikiagoa denbora 428 00:19:57,050 --> 00:20:01,280 galdera algoritmoa on aurkitzeko horiek itxi atzean kopurua 50 429 00:20:01,280 --> 00:20:01,830 ateak. 430 00:20:01,830 --> 00:20:06,400 >> Orain, bat alde batera utzita, ezagutuko bazenitu bezala bai O big, goi-muga hori, 431 00:20:06,400 --> 00:20:09,310 eta omega, beheko lotuak, berean bat dira, eta, 432 00:20:09,310 --> 00:20:11,830 formula bera da Parentesi dezakezu, gainera 433 00:20:11,830 --> 00:20:15,170 esan, besterik ez fancy, zerbait theta da 434 00:20:15,170 --> 00:20:18,270 n edo beste balio batzuen theta-ko. 435 00:20:18,270 --> 00:20:20,661 Horrek esan nahi du big O eta omega berdinak dira. 436 00:20:20,661 --> 00:20:21,910 Orain aukeraketa sort zer? 437 00:20:21,910 --> 00:20:23,400 Dezagun hiztegi berria hau erabili. 438 00:20:23,400 --> 00:20:27,407 Aukeraketa sailkatu, zer izan ginen berriro egiten, eta berriro, eta berriro? 439 00:20:27,407 --> 00:20:29,990 Atzera eta aurrera joan nintzen bidez zerrendan, nori bila? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Txikiena kopurua. 442 00:20:34,730 --> 00:20:37,560 >> Beraz, nola urrats asko, nola konparazioak asko egin nuen 443 00:20:37,560 --> 00:20:43,250 ahal izateko, irudikatu egin behar duten Zerrendako elementu txikiena izan zen? 444 00:20:43,250 --> 00:20:44,437 n ken 1, ezta? 445 00:20:44,437 --> 00:20:47,770 Bat naiz I hasteko besterik ez bada delako eman eta berarekin edo bere alderatuz hasten naiz, 446 00:20:47,770 --> 00:20:49,519 orduan benetan hura, hura edo bere, benetan hura, I 447 00:20:49,519 --> 00:20:52,010 elementu bakarra parekatu ahal elkarrekin n ken 1 aldiz. 448 00:20:52,010 --> 00:20:55,630 Beraz, aukeraketa sort antzera hartzen n ken 1 Lehen aldiz urratsak. 449 00:20:55,630 --> 00:20:59,540 >> Zenbat urrats me hartu du elementua bigarren txikiena aurkitu? 450 00:20:59,540 --> 00:21:02,920 n ken 2, nago delako muda izateaz mantentzen dut pertsona bera ikusten ari bada 451 00:21:02,920 --> 00:21:06,280 Berriro Nik dagoeneko hautatutako zion bada edo horiek bere eta jarri bere lekuan. 452 00:21:06,280 --> 00:21:09,270 Eta hirugarren urratsa, n ken 3, orduan n ken 4. 453 00:21:09,270 --> 00:21:11,020 Eredu hau ikusi dugu aurretik, eta, hain zuzen 454 00:21:11,020 --> 00:21:13,460 hautaketa ordena, era berean, goiko doazen ditu 455 00:21:13,460 --> 00:21:16,210 n karratu sortu egiten dugu summation duten bada. 456 00:21:16,210 --> 00:21:19,790 Zein da bere beheko muga, aukeraketa sort? 457 00:21:19,790 --> 00:21:25,350 Zauri, zenbat denbora ezinbestekoa aukeraketa Ordena hartu du, astelehenean definitu dugun bezala? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Bi aukera proposatzen. 460 00:21:30,490 --> 00:21:32,360 Agian n da, orain arte bezala. 461 00:21:32,360 --> 00:21:35,040 Agian n karratu da, hura bezala da gaur egun goi-muga gisa. 462 00:21:35,040 --> 00:21:35,874 >> IKUSLEEN: n karratu. 463 00:21:35,874 --> 00:21:36,664 HIZLARIA: n karratu. 464 00:21:36,664 --> 00:21:37,368 Zergatik? 465 00:21:37,368 --> 00:21:40,060 >> IKUSLEEN: duzu delako definitzeko [INAUDIBLE]. 466 00:21:40,060 --> 00:21:41,510 >> HIZLARIA: Zehazki. 467 00:21:41,510 --> 00:21:45,077 Hautaketa ordena definitzen dut, gutxienez, Nahiko inozoa izan zen, mantendu egingo da, 468 00:21:45,077 --> 00:21:46,160 elementu txikiena aurkitu. 469 00:21:46,160 --> 00:21:47,770 Joan berriro, txikiena elementu aurkitu. 470 00:21:47,770 --> 00:21:49,490 Joan berriro, txikiena elementu aurkitu. 471 00:21:49,490 --> 00:21:51,700 Ez dago moduko ez dagoela ere optimizatu 472 00:21:51,700 --> 00:21:54,350 abortatzeko me ondoren utzi dezake besterik n edo, beraz, urrats. 473 00:21:54,350 --> 00:21:57,080 Beraz, hain zuzen ere, hautaketa ordenatu, n omega karratu. 474 00:21:57,080 --> 00:22:00,667 >> Txertatzeko sort, non hartu nuen zertaz nork eman zen, eta, ondoren, hura plopped dut 475 00:22:00,667 --> 00:22:01,750 edo bere leku egokian? 476 00:22:01,750 --> 00:22:04,958 Ondoren, aurretik, bigarren pertsonan egiten dut, plopped zion edo bere leku egokian. 477 00:22:04,958 --> 00:22:07,910 Ondoren, hurrengo pertsona, plopped zion edo bere leku egokian. 478 00:22:07,910 --> 00:22:10,537 Iragarki hau: lineala, nolabait esateko. 479 00:22:10,537 --> 00:22:12,620 Lerro zuzen bat naiz, naiz ez atzera eta aurrera joan, 480 00:22:12,620 --> 00:22:16,080 Inoiz ez dut atzera begiratu benetan, baina zer gertatzen hura txertatu dut 481 00:22:16,080 --> 00:22:20,302 edo hasieran sartu bere Zerrendako zuten bezala astelehenean dugu? 482 00:22:20,302 --> 00:22:21,010 Zer gertatzen da? 483 00:22:21,010 --> 00:22:21,510 Bai? 484 00:22:21,510 --> 00:22:23,122 IKUSLEEN: [INAUDIBLE]. 485 00:22:23,122 --> 00:22:24,830 HIZLARIA: Bai, hori harrapatzen zen, ezta? 486 00:22:24,830 --> 00:22:26,746 Gogoratzen dezakezu ikaskideak, badute 487 00:22:26,746 --> 00:22:29,670 ziren edozein mugimendu egiteko bere oinak, eta, operazio bat izan zen. 488 00:22:29,670 --> 00:22:33,610 Beraz, bada, ez ziren hiru lagun han eta hemen beste pertsona baita modu han, 489 00:22:33,610 --> 00:22:37,360 hau bezalako etapa luze bat, ziur, zuen edo ezin izan zuen besterik oso amaiera joan. 490 00:22:37,360 --> 00:22:40,074 Baina bat buruz ari zaren pentsatzen bada ordenagailu eta memoria array bat, 491 00:22:40,074 --> 00:22:41,990 Pertsona horiek dira joan baino gehiago nahastu dute 492 00:22:41,990 --> 00:22:43,260 pertsona horrek gela egiteko. 493 00:22:43,260 --> 00:22:46,930 Eta beraz, n ken 1 shufflings, n ken 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 ken 3 shufflings besterik ez mota nire atzean gertatzen ari, ez nire aurrean 495 00:22:50,660 --> 00:22:52,710 lehen bezala, zentzu batean. 499 00:22:52,557 --> 00:22:54,640 Orain alde batera utzita, eta gisa dituzu online ikusi ahal izan liteke 500 00:22:54,640 --> 00:22:57,699 buruz kuxkuxean hasten bazara ordenatzen, ez da hainbeste hainbat direnak 501 00:22:57,699 --> 00:22:59,490 daude, horietako batzuk besteak baino hobeak. 502 00:22:59,490 --> 00:23:02,200 Izan ere, bogosort da duten fun bilatzeko mota da. 503 00:23:02,200 --> 00:23:06,650 Bogosort multzo bat hartzen du zenbakiak edo karta-sorta bat esan, 504 00:23:06,650 --> 00:23:09,870 ausaz shuffles horiek, eta egiaztapen badute ordenatuko ari. 505 00:23:09,870 --> 00:23:12,130 Eta horrela ez bada, berriro egiten du. 506 00:23:12,130 --> 00:23:14,140 Eta horrela ez bada, berriro egiten du. 507 00:23:14,140 --> 00:23:15,440 Hala ez bada, berriro egiten du. 508 00:23:15,440 --> 00:23:17,060 Oso ergelak. 509 00:23:17,060 --> 00:23:19,520 >> Eta hain zuzen ere, irakurri nahi izanez gero Wikipedia article bezala, 510 00:23:19,520 --> 00:23:21,200 Bere goitizena ergelak moduko da. 511 00:23:21,200 --> 00:23:25,180 Azkenean lan egingo du, zorionez, nahikoa denbora eman, 512 00:23:25,180 --> 00:23:28,240 baina zenbat denbora duten denbora luzez iraun dezake. 513 00:23:28,240 --> 00:23:31,650 Beraz, ezin dut, utzi bada abiadura gauzak Mary Beth adibidez lehenago sortu, 514 00:23:31,650 --> 00:23:35,150 a elementu batzuk gehiago izatea, baina bi prozesadoreak gehiago. 515 00:23:35,150 --> 00:23:37,100 Bi lagun, duzu bada ez luke axola niri batu. 516 00:23:37,100 --> 00:23:40,972 Nola buruz 1 hemen, eta dezagun joan egingo han inork ez? 517 00:23:40,972 --> 00:23:41,722 No bat han? 518 00:23:41,722 --> 00:23:42,221 Ados. 519 00:23:42,221 --> 00:23:44,190 Beltzekin duzu alkandora, bai, goazen behera. 520 00:23:44,190 --> 00:23:45,000 Ondo da, zer da zure izena? 521 00:23:45,000 --> 00:23:45,720 >> IKUSLEEN: Peter. 522 00:23:45,720 --> 00:23:46,100 >> HIZLARIA: Zer da hori? 523 00:23:46,100 --> 00:23:46,766 >> IKUSLEEN: Peter. 524 00:23:46,766 --> 00:23:49,450 HIZLARIA: Peter, David, politak zu ezagutzeaz. 525 00:23:49,450 --> 00:23:53,670 Ondo da, Peter dugu hemen, nahi baduzue hemen baino gehiago mahai gainean, etorri nahi. 526 00:23:53,670 --> 00:23:54,550 Eta zein da zure izena? 527 00:23:54,550 --> 00:23:55,216 >> IKUSLEEN: Elena. 528 00:23:55,216 --> 00:23:55,970 HIZLARIA: Elena. 529 00:23:55,970 --> 00:23:57,030 Ados, politak zu ezagutzeaz. 530 00:23:57,030 --> 00:23:58,060 Elena betetzen Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Eta Andrew behar dugu hemen bai gora, mesedez. 533 00:24:02,290 --> 00:24:06,107 Eta zure erronka va karta-sorta bat ordenatzeko izan. 534 00:24:06,107 --> 00:24:08,190 Eta lanik izanez gero, bizkarreko txartelak egin beharko lukete, azken finean, 535 00:24:08,190 --> 00:24:11,064 egon ordenatuko antzeko zerbait apur bat hau non kluben egin dugu, eta gero 536 00:24:11,064 --> 00:24:13,660 palak, eta gero bihotzak eta diamante, bateko bat bezala, 537 00:24:13,660 --> 00:24:15,570 king gehienez modu guztiak. 538 00:24:15,570 --> 00:24:20,890 >> Txartelak The naiz emateko egingo dira kantitatean 52 izango da. 539 00:24:20,890 --> 00:24:23,160 Ari gara, era berean, joan denbora duzu, une bat besterik ez. 540 00:24:23,160 --> 00:24:26,410 Andrew botatzen goaz Pantailan hemen sortu, 541 00:24:26,410 --> 00:24:28,170 beraz, egin duzun bezala ikustera. 542 00:24:28,170 --> 00:24:31,070 Eta, beraz, hori guztia da are nabarmenago, 543 00:24:31,070 --> 00:24:33,490 horiek txartelak lortu Amazon I daude. 544 00:24:33,490 --> 00:24:42,861 Beraz, dagoeneko dira ausaz ordenatuta, eta denbora goaz. 545 00:24:42,861 --> 00:24:44,610 Eta goaz benetako mantendu da oraingoan, 546 00:24:44,610 --> 00:24:47,820 beraz ari gara presio saiatu joan zeren bestela hau lapurtera lortuko 547 00:24:47,820 --> 00:24:48,460 azkar. 548 00:24:48,460 --> 00:24:53,860 Duzu 52 ordenatzeko jarraitu balute elkarrekin bide batzuk erabiliz elementuak, orain. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Eta berriro ere, hauetan ikusi dugun bezala guys zer, azkenean, 551 00:25:07,180 --> 00:25:10,200 da bistako bat ekoizteko joan Ondorioz, uste benetan buruz 552 00:25:10,200 --> 00:25:12,962 Honela egiten dute bakoitzak egiten ari, nola deskribatuko dezakezu. 553 00:25:12,962 --> 00:25:15,045 Berriro ere, horiek direlako guztiak prozesu, algoritmo 554 00:25:15,045 --> 00:25:17,090 hartu dugun giza gisa emandako. 555 00:25:17,090 --> 00:25:22,349 Baina seguruenik luzea izan duzu intuizioa, luzea duzu, nahiz eta aurretik 556 00:25:22,349 --> 00:25:24,390 bat hartuz pentsatu informatikako klasean duzu 557 00:25:24,390 --> 00:25:27,223 Honekin intuizioa izan liteke honen antzeko arazoak konpontzeko. 558 00:25:27,223 --> 00:25:29,560 Baina behin ezagutzen duzu ereduak eta hasteko 559 00:25:29,560 --> 00:25:32,407 dituen urratsak formalizatzeko arazo horiek konpontzeko zaren, 560 00:25:32,407 --> 00:25:35,490 aurkitu duten askoz konpondu ahal izango duzu duzu gehiago interesgarri eta konplexua askoz gehiago 561 00:25:35,490 --> 00:25:39,190 arazoak azkar. 562 00:25:39,190 --> 00:25:42,351 Beraz, ikusleek norbait, zer da Algoritmoaren elementu bat gutxienez 563 00:25:42,351 --> 00:25:43,350 hemen erabiltzen ari dira? 564 00:25:43,350 --> 00:25:44,275 >> IKUSLEEN: [INAUDIBLE] 565 00:25:44,275 --> 00:25:45,150 HIZLARIA: Zer da hori? 566 00:25:45,150 --> 00:25:47,062 IKUSLEEN: palo By. 567 00:25:47,062 --> 00:25:47,770 HIZLARIA: palo By. 568 00:25:47,770 --> 00:25:50,630 Beraz, lehenengo multzokatu dira diamante guztiak elkarrekin 569 00:25:50,630 --> 00:25:52,560 dirudienez, guztia bihotzak elkarrekin badirudi, 570 00:25:52,560 --> 00:25:56,520 eta abar, errespetu gabe txartelen zenbakiak da. 571 00:25:56,520 --> 00:26:00,900 Eta orain, agertzen dira, esate baterako, izango ratuz, eta kopuruaren arabera. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Oso ona. 574 00:26:08,910 --> 00:26:12,370 >> Ondo da, beraz, zer ari den gertatzen izan du azken urratsa, ondoren, hemen? 575 00:26:12,370 --> 00:26:16,950 Behin lau jantziak ordenatuko, behar dugu zer egiteko lau pila egin behar dugu 576 00:26:16,950 --> 00:26:20,059 ordena bat lortzeko helburuarekin ordenatuko bizkarreko, nahiko besterik gabe? 577 00:26:20,059 --> 00:26:21,350 Beraz, horiek berriro batu behar dugu. 578 00:26:21,350 --> 00:26:25,160 >> Beraz, ez da ideia interesgarria dela berriro, daresay, oso intuitiboa are 579 00:26:25,160 --> 00:26:28,140 agian ez duzu inoiz izan slapped bada etiketa on-mota hori. 580 00:26:28,140 --> 00:26:31,900 Zatituz oinarrizko kontzeptu horrek arazoa ez oraingoan erdia, 581 00:26:31,900 --> 00:26:33,410 baina, gutxienez, lau zatitan. 582 00:26:33,410 --> 00:26:36,810 Nahiko askoz konpontzeko arazoak funtsean berdin- 583 00:26:36,810 --> 00:26:40,480 bata bestearen isolamendua, eta, ondoren, emaitzak batuz. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Eta, bikaina, egin. 586 00:26:50,140 --> 00:26:52,140 Ondo da, borobil handi bat txalo, badugu gabe. 587 00:26:52,140 --> 00:26:56,480 >> [Txaloak] 588 00:26:56,480 --> 00:26:59,740 >> HIZLARIA: Ez dut ideiarik ere zer dituzu hauekin egin, baina hemen. 589 00:26:59,740 --> 00:27:01,690 Eskerrik asko. 590 00:27:01,690 --> 00:27:04,660 Beraz, ikus dezagun, bi minutu eta zortzi segundo, 591 00:27:04,660 --> 00:27:07,490 Zure erronka nahi izanez gero. 592 00:27:07,490 --> 00:27:12,160 Orduan zer da joan izan bat kentzen honetatik 593 00:27:12,160 --> 00:27:13,830 duten orokorrago leverage dezakegu? 594 00:27:13,830 --> 00:27:16,080 Beno, atzera uste zenbakiak array hau, 595 00:27:16,080 --> 00:27:19,060 eta uste orain atzera batzuei pseudocode iraganean dugu idatzizko, 596 00:27:19,060 --> 00:27:22,080 eta hau izan zen pseudocode telefono-liburuaren arazoa konpontzeko. 597 00:27:22,080 --> 00:27:25,150 Pseudocode I Beraren bidez, modu gehiago metodiko bat izendatuak 598 00:27:25,150 --> 00:27:28,400 nola oso intuitibo batean egin nuen deskribatzeko Telefono zatituz giza algoritmoa 599 00:27:28,400 --> 00:27:31,650 erdia liburua, errepikatu, errepikatu, errepikatu, dut aurkitu arte Mike Smith bezalako norbait, 600 00:27:31,650 --> 00:27:33,790 da, hain zuzen ere bada telefono-liburuan. 601 00:27:33,790 --> 00:27:37,610 >> Baina mota horretako zer deitu dut erabiltzen dut Oso etorriko hurbilketa bat hemen, 602 00:27:37,610 --> 00:27:42,160 oharra bereziki line 8 eta line 11. 603 00:27:42,160 --> 00:27:46,750 Horiek iteratibo baten ebidentzia dira Planteamendu, begizta hurbilketa bat, 604 00:27:46,750 --> 00:27:49,040 hori zehazki duelako jokabidea dute bultzatu. 605 00:27:49,040 --> 00:27:52,910 Lerro horiek bai esateko joan linea hiru, eta ahal duzun, mota horretako 606 00:27:52,910 --> 00:27:55,140 dela uste zure kontuan bere begi begizta bat izateaz gain. 607 00:27:55,140 --> 00:27:59,080 Honez diozu atzera joan ahal izateko urratsa Hiru eta errepikatzeko, berriro, eta berriro, 608 00:27:59,080 --> 00:28:00,010 eta berriro. 609 00:28:00,010 --> 00:28:04,410 >> Baina zer Ideia bat leverage badugu hemen ez da azken aldia egin dugula, 610 00:28:04,410 --> 00:28:10,280 eta linea 8 errazteko eta 11 lerro eta beren auzokoei 611 00:28:10,280 --> 00:28:12,840 besterik honetan, horia bezala. 612 00:28:12,840 --> 00:28:16,480 Ez da funtsean laburtzen pseudocode asko, 613 00:28:16,480 --> 00:28:20,530 baina funtsean aldatzen Nire algoritmoa izaera. 614 00:28:20,530 --> 00:28:24,220 Zer naiz orain esaten 7 urratsean, 10 urratsean, 615 00:28:24,220 --> 00:28:29,140 bilaketa da, Mike for Era berean zehatza, 616 00:28:29,140 --> 00:28:31,580 baina besterik ezkerrean erdi edo eskuineko erdia. 617 00:28:31,580 --> 00:28:33,420 >> Beraz, beste era batera esanda, bada Hasteko urrats bat naiz, 618 00:28:33,420 --> 00:28:36,150 telefonoa hartu liburua, erdi irekiak Telefono liburua, izenak begiratu, 619 00:28:36,150 --> 00:28:39,010 Smith artean badago Izen horrek, deitu Mike, beste 620 00:28:39,010 --> 00:28:44,340 Smith liburu lehenago bada, zazpi urratsera bilatu Mike utzi liburuaren erdia. 621 00:28:44,340 --> 00:28:47,130 Baina mota bezala sentitzen me utziz zintzilik, ezta? 622 00:28:47,130 --> 00:28:49,240 Horiz, da an instrukzioa, baina nola egin behar dut 623 00:28:49,240 --> 00:28:51,870 bilatu Mike for ezkerrean telefono-liburuaren erdia? 624 00:28:51,870 --> 00:28:54,210 Nora bat daukat Algoritmo horrekin dut 625 00:28:54,210 --> 00:28:57,100 bilatu dezakezu Mike Smith bezalako norbait? 626 00:28:57,100 --> 00:28:58,980 Beno, nik begiradak digu aurpegia. 627 00:28:58,980 --> 00:29:03,090 Literalki I berean zehatza erabili ahal programan eraginkortasunez sortu goiko joan 628 00:29:03,090 --> 00:29:06,490 berriro eta berriro exekutatzen Kode lerro bera. 629 00:29:06,490 --> 00:29:10,610 >> Beraz, hau sentitu behar, nahiz Definizio zikliko bat apur bat bezalakoa 630 00:29:10,610 --> 00:29:13,480 non erantzunez zaren norbait da sort galdetuz galdera 631 00:29:13,480 --> 00:29:15,990 galdera bera berriz ere, bezala, zergatik, zergatik, zergatik? 632 00:29:15,990 --> 00:29:21,580 Errealitatea da, dugu, gogorra delako kodetuak lerro berezi pare bat, 4 urrats, 633 00:29:21,580 --> 00:29:25,320 bertan bada bat, eta 12 pauso, zein eraginkortasunez beste adar bat da, 634 00:29:25,320 --> 00:29:30,120 stopgap Neurri horiek dugulako, Algoritmo hau desegin egingo badugu 635 00:29:30,120 --> 00:29:32,050 aurkitu Mike, edo ez badugu. 636 00:29:32,050 --> 00:29:36,810 Baina, 7 eta 10 urrats orain ere, hemengo zer algoritmo errekurtsiboa bat deitu dugu. 637 00:29:36,810 --> 00:29:40,420 Eta errekurtsio da, hain zuzen, ideia indartsu bat burura apur bat lehen at tolestuz da, 638 00:29:40,420 --> 00:29:42,500 orain dugu honako hau eskatu ahal izango da. 639 00:29:42,500 --> 00:29:46,600 >> Batu sort azken sort izango duten begiratu dugu at, gutxienez klasean formalki. 640 00:29:46,600 --> 00:29:50,040 Eta batez ere, desberdina da horiek azken hiru, eta, zalantzarik gabe, aurrera 641 00:29:50,040 --> 00:29:52,140 Azken lau sartzen ditugu bogosort bada. 642 00:29:52,140 --> 00:29:54,810 Hemen merge sort pseudocode da. 643 00:29:54,810 --> 00:30:00,170 Noiz n elementuen sarrera, beraz, emandako tamaina n array bat, n 2 baino txikiagoa bada, 644 00:30:00,170 --> 00:30:01,040 itzultzeko. 645 00:30:01,040 --> 00:30:03,610 Beraz, zergatik behar dudala behatu check lehen? 646 00:30:03,610 --> 00:30:09,477 Zer inplikazioa duzu entregatu badut array baten luzera n 2 baino gutxiago? 647 00:30:09,477 --> 00:30:11,060 Dagoeneko ordenatuko da, jakina, ezta? 648 00:30:11,060 --> 00:30:13,640 Zerrendako bai duelako elementu bat, eta hori kenduz 649 00:30:13,640 --> 00:30:15,180 ordenatuta, da delako Gauza bakarra ez. 650 00:30:15,180 --> 00:30:18,138 Edo, da tamaina zero eta horrek esan nahi du ez ezer ordenatzeko, beraz, naturak 651 00:30:18,138 --> 00:30:18,720 ordenatuko da. 652 00:30:18,720 --> 00:30:20,410 Ez dago ia ezer txarrik ez dago. 653 00:30:20,410 --> 00:30:22,310 Beraz, gure kasuan horrela deitzen da. 654 00:30:22,310 --> 00:30:24,440 >> Hori espiritua antzekoa da zer egin Mike ekin genuen. 655 00:30:24,440 --> 00:30:26,023 Mike telefono-liburuan badago, deitu zion. 656 00:30:26,023 --> 00:30:27,740 Ez bada zuen han, amore eman. 657 00:30:27,740 --> 00:30:31,240 Da base baten kasua deiturikoak, ziurtatu Egunaren amaieran, algoritmo hau 658 00:30:31,240 --> 00:30:33,540 egingo du egoera jakin batzuetan gelditzeko. 659 00:30:33,540 --> 00:30:37,890 >> Baina hemen fede-jauzi orain, bestela, ezker elementuen erdia ordenatzeko, 660 00:30:37,890 --> 00:30:39,740 ondoren ordenatzeko eskubidea elementuen erdia, 661 00:30:39,740 --> 00:30:41,189 eta ondoren batu ordenatuko halves. 662 00:30:41,189 --> 00:30:43,230 Eta hemen bertan sentitzen atsegin out copping ari gara. 663 00:30:43,230 --> 00:30:46,900 Ordenatzeko Nik zaizu n elementu, eta ez naiz 664 00:30:46,900 --> 00:30:50,712 , esaten Ados, ez da ordenatzeko arabera utzi eta sailkatzeko eskubidea. 665 00:30:50,712 --> 00:30:52,420 Baina nago, inork esaten dut Beste gauza da, eta hau 666 00:30:52,420 --> 00:30:55,530 Funtsezko gaia da dirudiena da intuizio batean beraz, orain arte, 667 00:30:55,530 --> 00:30:57,380 Han hirugarren batuz urratsa da hau. 668 00:30:57,380 --> 00:31:00,430 Zein are arren Badirudi beraz espirituz mutu, 669 00:31:00,430 --> 00:31:02,320 bezalako besterik batu gauzak elkarrekin, badirudi 670 00:31:02,320 --> 00:31:05,380 giltza norabidean urrats bat izan nahi du bi arazo reassembly duten 671 00:31:05,380 --> 00:31:07,330 ziren, azken finean banatzen erditik. 672 00:31:07,330 --> 00:31:12,090 >> Beraz, batu, ordenatu, egin dezagun hau, duzu bada umore me, manifestazio bat gehiago, 673 00:31:12,090 --> 00:31:14,730 besterik ez da, beraz, batzuk ditugu Zenbaki horiekin lan. 674 00:31:14,730 --> 00:31:19,470 Ezin dut zortzi estres trukatzeko Zortzi lagunentzako pilotak? 675 00:31:19,470 --> 00:31:29,320 Ondo da, nola zu hiru, lau Atal honetan, bost, sei, eta dezagun ere 676 00:31:29,320 --> 00:31:30,720 do 7, 8, goazen gora. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 Ados, bai Ados. 679 00:31:36,520 --> 00:31:38,640 Minus 8, han, joan gara plus 1. 680 00:31:38,640 --> 00:31:39,150 Bikain. 681 00:31:39,150 --> 00:31:42,000 Guztiak eskubidea goazen gora, dezagun azkar eman dituzun zenbakiak. 682 00:31:42,000 --> 00:31:50,800 Zenbakia bi, hiru zenbaki, lau zenbakia, kopurua bost, sei, zazpi, eta zortzi. 683 00:31:50,800 --> 00:31:52,140 Zortzi egin behar bezala dut oraingoan. 684 00:31:52,140 --> 00:31:56,390 >> Ados, beraz, aurrera ahal izango banu, eta en ordenatzeko jatorrizko ordena utzi 685 00:31:56,390 --> 00:31:59,810 atzo izan dugun begiratu Hau atsegin, bada ez litzateke axola. 686 00:31:59,810 --> 00:32:03,620 Eta egin dezagun mahai aurrean utzi. 687 00:32:03,620 --> 00:32:06,510 Ondo da, beraz, batu sort. 688 00:32:06,510 --> 00:32:08,820 Hau da, non egingo da motatako lortzeko interesgarri, 689 00:32:08,820 --> 00:32:12,800 egon neure buruari emanez badirudi nuelako Hainbeste informazio gutxiago baitago. 690 00:32:12,800 --> 00:32:15,149 >> Beraz, batu, ordenatu, lehenik eta behin n elementuen sarrera oinarrituz, 691 00:32:15,149 --> 00:32:18,440 eta ez bi baino gutxiago da, jakina, ez da zortzi, beraz, lan gehiago egin behar dut. 692 00:32:18,440 --> 00:32:21,140 Beraz, gaur egun adimen dugu klase bezala dira orain beste adarrean, 693 00:32:21,140 --> 00:32:22,540 horrek hiru urrats esan nahi du. 694 00:32:22,540 --> 00:32:25,017 Lehenik eta behin, ordenatzeko behar dut ezker elementuen erdia. 695 00:32:25,017 --> 00:32:26,350 Beraz, nola ez naiz joaten hau egiten? 696 00:32:26,350 --> 00:32:28,950 Beno, noa motatako adimen zatitzen zerrenda hemen, 697 00:32:28,950 --> 00:32:30,700 ez duzu behar fisikoki mugitu, eta ez naiz 698 00:32:30,700 --> 00:32:33,180 on bakarra bideratzen joan ezker elementuak hemen erdia. 699 00:32:33,180 --> 00:32:36,770 Beraz, nola ez ordenatzeko buruz joan nintzen zerrenda lau tamainaren orain? 700 00:32:36,770 --> 00:32:38,730 Zein da nire algoritmoa? 701 00:32:38,730 --> 00:32:42,580 Lehen dut egiaztatu da n bi baino gutxiago ez, beraz, aurrera jarraitzeko beste blokea dut berriro. 702 00:32:42,580 --> 00:32:43,900 Sort elementu erdia utzi. 703 00:32:43,900 --> 00:32:45,608 >> Beraz, orain berriro, adimen, eta hau da, non 704 00:32:45,608 --> 00:32:49,550 asko sortuko behar duzu historia mental, izango bada. 705 00:32:49,550 --> 00:32:51,940 Orain ordenatzeko naiz ezker ezkerreko erdia erdia. 706 00:32:51,940 --> 00:32:57,000 Ondo da, beraz, gaur egun, nire merge bera deitzen dut Algoritmo ordenatzeko, bi baino gutxiago n? 707 00:32:57,000 --> 00:33:00,590 Ez, bi da eta, beraz, ongi ordenatzeko behar dut ezkerreko erdia eta eskuineko erdia. 708 00:33:00,590 --> 00:33:02,042 Beraz, hemen, joaten gara ezkerreko erdian ordenatzeko. 709 00:33:02,042 --> 00:33:03,750 Zergatik ez duzu besterik Urrats bat aurrera. 710 00:33:03,750 --> 00:33:04,415 Zein da zure izena? 711 00:33:04,415 --> 00:33:04,860 >> IKUSLEEN: Darren. 712 00:33:04,860 --> 00:33:05,260 >> HIZLARIA: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan urratsez urrats aurrera egin du. 714 00:33:06,040 --> 00:33:06,748 >> IKUSLEEN: Darren. 715 00:33:06,748 --> 00:33:09,000 HIZLARIA: Darren, done. 716 00:33:09,000 --> 00:33:10,090 Ba Darren edo Dan esan duzu? 717 00:33:10,090 --> 00:33:10,550 >> IKUSLEEN: Darren. 718 00:33:10,550 --> 00:33:11,216 >> HIZLARIA: Darren. 719 00:33:11,216 --> 00:33:14,422 Ados, Darren zapaldu du aurrerantz eta orain da zuen ordenatuta. 720 00:33:14,422 --> 00:33:16,130 Eta hau da, ia bat inane erreklamazioa, ezta? 721 00:33:16,130 --> 00:33:18,862 Ez dut Badirudi lortzera ezer, baina dezagun aurrera jarraitzeko. 722 00:33:18,862 --> 00:33:20,820 Orain dezagun eskubidea ordenatzeko me elementuen erdia. 723 00:33:20,820 --> 00:33:21,200 Zein da zure izena? 724 00:33:21,200 --> 00:33:21,690 >> IKUSLEEN: Luke. 725 00:33:21,690 --> 00:33:22,273 >> HIZLARIA: Luke. 726 00:33:22,273 --> 00:33:23,400 Tira, aurrera egin. 727 00:33:23,400 --> 00:33:25,640 Luke emana, ordenatuko ditut. 728 00:33:25,640 --> 00:33:28,570 Ezkerreko erdia da orain ordenatuko da eta eskuineko erdia sailkatuta gera, 729 00:33:28,570 --> 00:33:30,770 baina berriro ere, ez dago gakoa urrats bat da hemen. 730 00:33:30,770 --> 00:33:32,940 Zer hurrengo egin behar dut? 731 00:33:32,940 --> 00:33:33,941 Batu ordenatuko halves. 732 00:33:33,941 --> 00:33:36,648 Orain ari gara besterik ez dute joan denek atzera eta aurrera modu honetan, 733 00:33:36,648 --> 00:33:38,620 motatako behar dudalako scratch espazio batzuk. 734 00:33:38,620 --> 00:33:40,411 Ia horiek bezalakoa da guys mahai baten gainean daude, 735 00:33:40,411 --> 00:33:42,460 eta gela batzuk behar dut horien inguruan mugitu on. 736 00:33:42,460 --> 00:33:44,170 Beraz, naiz batu behar mutilak begira dituzu 737 00:33:44,170 --> 00:33:45,960 ezkerreko erdia eta eskuineko erdia. 738 00:33:45,960 --> 00:33:48,740 Eta nor, jakina, ezer baino lehen, utzi erdi edo eskuineko erdia? 739 00:33:48,740 --> 00:33:52,710 Beraz, eskuineko erdia, beraz dezagun aurrera Luke baino gehiago Darren en jatorrizko posizioan hemen. 740 00:33:52,710 --> 00:33:57,640 Eta orain euren ezkerreko erdia batzea ere, Darren da bertan mugitu behar. 741 00:33:57,640 --> 00:33:59,750 >> Beraz, ia bezala sentitzen burbuila moduko efektua, 742 00:33:59,750 --> 00:34:02,482 baina nire oinarrizko algoritmoa, oso desberdina oraingoan. 743 00:34:02,482 --> 00:34:04,815 Baina orain, non gauza lortu txiki gogaikarriak duzulako 744 00:34:04,815 --> 00:34:06,810 adimen atzeratzeko behar non utzi nuen. 745 00:34:06,810 --> 00:34:09,893 Besterik ordenatuko halves Nik batu, horrek esan nahi du non nago nire algoritmoa? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Eskuineko erdia ordenatzeko behar dut, ezta? 748 00:34:13,770 --> 00:34:15,910 >> , Atzeratzeko baduzu hitzez hitz bideoan ere, ikusiko duzu 749 00:34:15,910 --> 00:34:18,339 ikusten duten got honetara dugu Luke eta Darren puntua 750 00:34:18,339 --> 00:34:21,370 ordenatzeko ezker arabera ezkerreko erdia erdia. 751 00:34:21,370 --> 00:34:23,430 Ondoren, horiek batu ditugu ordenatuko halves, eta horrek 752 00:34:23,430 --> 00:34:27,941 esan nahi du, hurrengo urratsa da ordena eskuineko ezkerreko erdia erdia. 753 00:34:27,941 --> 00:34:29,649 Ondo da, beraz dezagun hau egin azkarrago. 754 00:34:29,649 --> 00:34:33,282 Ondo da, sei, naiz aldarrikatzen dut gaur egun ordenatuko dituzu, goazen aurrera. 755 00:34:33,282 --> 00:34:33,990 Zein da zure izena? 756 00:34:33,990 --> 00:34:34,589 >> IKUSLEEN: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> HIZLARIA: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano orain ordenatuko da. 759 00:34:36,010 --> 00:34:36,450 Eta zein da zure izena? 760 00:34:36,450 --> 00:34:37,080 >> IKUSLEEN: Alex. 761 00:34:37,080 --> 00:34:38,379 >> HIZLARIA: Alex orain ordenatuko da. 762 00:34:38,379 --> 00:34:40,750 Ezkerreko erdia, eskuineko erdia, zer da azken urratsa? 763 00:34:40,750 --> 00:34:41,250 Batu. 764 00:34:41,250 --> 00:34:44,310 Nahiko hutsala, hain naiz sei eta batu egingo, 765 00:34:44,310 --> 00:34:46,930 urrats bat atzera, zortzi, urrats bat atzera. 766 00:34:46,930 --> 00:34:49,530 Eta orain konturatu hau da eramateko erabilgarria, zer 767 00:34:49,530 --> 00:34:53,930 da gaur egun ezkerreko erdia buruzko egia zerrenda, nola hasi ginen kontuan hartu gabe? 768 00:34:53,930 --> 00:34:55,090 It ordenatuko da. 769 00:34:55,090 --> 00:34:57,750 >> Orain ez da ordenatuko eskema gauza handia da, 770 00:34:57,750 --> 00:35:00,250 baina independentean ordenatuko da beste erdiak. 771 00:35:00,250 --> 00:35:04,100 Orain zer urrats naiz on I mantendu bada istorioa nola hasi errebobinagarriaren? 772 00:35:04,100 --> 00:35:05,680 Orain eskuineko erdia ordenatzeko behar dut. 773 00:35:05,680 --> 00:35:07,630 Beraz, orain ari garen modu berean itzuli Istorioaren hasieran, 774 00:35:07,630 --> 00:35:08,921 eta egin dezagun gehiago azkar utzi. 775 00:35:08,921 --> 00:35:11,320 Beraz, ez dut ordenatzeko joan eskubidea zerrenda osoa erdia. 776 00:35:11,320 --> 00:35:13,060 Zein da hurrengo urratsa? 777 00:35:13,060 --> 00:35:15,840 Sort utzi eskuineko erdia erdia. 778 00:35:15,840 --> 00:35:18,715 Sort utzi erdia ezkerretik eskuinera erdia erdia. 779 00:35:18,715 --> 00:35:19,590 Eta zein da zure izena? 780 00:35:19,590 --> 00:35:20,230 >> IKUSLEEN: Omar. 781 00:35:20,230 --> 00:35:21,970 >> HIZLARIA: Omar, aurrerapauso, done. 782 00:35:21,970 --> 00:35:22,860 Ezkerreko erdia ordenatuko da. 783 00:35:22,860 --> 00:35:23,330 Eta zein da zure izena? 784 00:35:23,330 --> 00:35:23,820 >> IKUSLEEN: Chris. 785 00:35:23,820 --> 00:35:25,620 >> HIZLARIA: Chris, beste urrats bat Aurrera, orain ordenatuko dira duzun. 786 00:35:25,620 --> 00:35:27,010 Zer da funtsezko urratsa da orain? 787 00:35:27,010 --> 00:35:27,510 Batu. 788 00:35:27,510 --> 00:35:30,509 Beraz bat da leku batu dira Hemen, urrats bat atzera balute, 789 00:35:30,509 --> 00:35:32,930 eta hiru da joan urrats bat atzera, batzea. 790 00:35:32,930 --> 00:35:38,080 Beraz, ezkerreko erdia eskuineko erdia, orain ordenatuko da. 791 00:35:38,080 --> 00:35:41,747 Egia, algoritmo hau genuen bezala sentitzen dira modu denbora gehiago alferrik galtzen baino, 792 00:35:41,747 --> 00:35:44,830 baina hori egin dugu, bada, denbora errealean, zaitugu ikusi zer takeaways izango da. 793 00:35:44,830 --> 00:35:47,970 Orain hemen nago, eskuineko eskuineko erdia erdia, 794 00:35:47,970 --> 00:35:50,170 utzi aurretik joan eta ezkerreko erdia ordenatzeko. 795 00:35:50,170 --> 00:35:51,482 Aurrerapauso, zer da zure izena? 796 00:35:51,482 --> 00:35:52,190 IKUSLEEN: Ramsey. 797 00:35:52,190 --> 00:35:53,210 HIZLARIA: Ramsey orain ordenatuko da. 798 00:35:53,210 --> 00:35:53,570 Zein da zure izena? 799 00:35:53,570 --> 00:35:54,200 >> IKUSLEEN: Marina. 800 00:35:54,200 --> 00:35:57,033 >> HIZLARIA: Marina da, orain bezala ordenatuta bai, pauso bat aurrera egiten duzun ere. 801 00:35:57,033 --> 00:36:00,690 Gakoa urratsa hemen orain batzea da, naiz nire bi zerrendetatik pluck joan, 802 00:36:00,690 --> 00:36:01,720 ezker eta eskuin. 803 00:36:01,720 --> 00:36:05,150 Bost da lehen etorri da joan, eta zazpi hurrengo etorriko da joan. 804 00:36:05,150 --> 00:36:06,410 Eta berriro ere, hau nahita. 805 00:36:06,410 --> 00:36:08,535 Izan ere, hartzen ari dira aurrera eta atzera pausoak 806 00:36:08,535 --> 00:36:12,997 Ahal den adierazten nahi genuela ez Algoritmo hau egiteko leku gisa erraz 807 00:36:12,997 --> 00:36:15,830 burbuila ordenatu, eta aukeraketa sort bezala, eta txertatzeko sort non besterik ez dugu 808 00:36:15,830 --> 00:36:16,960 Jende aldaketa mantendu. 809 00:36:16,960 --> 00:36:19,940 Literalki moduko bat behar dut scratch paper horretan, 810 00:36:19,940 --> 00:36:21,827 Folks horiek jartzea batuz egiten dudan bitartean, 811 00:36:21,827 --> 00:36:23,410 eta gero berriro jarri ahal dudan lekuan. 812 00:36:23,410 --> 00:36:27,260 Eta hori da gakoa nuen bat erabiltzen ari delako baliabide berriak, espazioan, eta ez bakarrik denbora. 813 00:36:27,260 --> 00:36:28,270 >> Ados, hau harrigarria da. 814 00:36:28,270 --> 00:36:32,050 Ezkerreko erdia ordenatuko da, eskuineko erdia da ordenatuko, orain gakoa duten batuz urratsa. 815 00:36:32,050 --> 00:36:33,450 Nola ari naiz honetan batu egingo da? 816 00:36:33,450 --> 00:36:35,470 Beraz, jarraitu egingo baduzu nire ezkerreko eta eskuineko eskua, 817 00:36:35,470 --> 00:36:38,930 Nire ezkerreko eskua seinalatu noa Ezkerreko erdia, nire eskuineko eskua 818 00:36:38,930 --> 00:36:42,680 eskuineko erdia, eta orain izan dut urratsa nori ere batu urrats erabakitzeko. 819 00:36:42,680 --> 00:36:44,650 Nor jakina dator lehen? 820 00:36:44,650 --> 00:36:45,150 Zenbaki bat da. 821 00:36:45,150 --> 00:36:47,327 Beraz, zatoz hona, Hemen gure scratch pad da. 822 00:36:47,327 --> 00:36:49,910 Beraz, inork, eta aldez zenbaki orain zer nire eskuineko eskua egin dut, 823 00:36:49,910 --> 00:36:54,152 Eskuineko eskua mugitu noa urratsa baino gehiago hiru zenbaki seinalatu, 824 00:36:54,152 --> 00:36:55,860 eta orain egin behar dut Erabaki bera. 825 00:36:55,860 --> 00:36:58,387 Eta benetan stand Eskuinetik Luke hemen ahal izango banu aurrean, 826 00:36:58,387 --> 00:36:59,720 hau gure scratch pad delako. 827 00:36:59,720 --> 00:37:00,610 Beraz, nor dator hurrengo? 828 00:37:00,610 --> 00:37:05,000 Luke dute bi zenbaki batera gara edo Chris hiru zenbaki batekin. 829 00:37:05,000 --> 00:37:07,460 Jakina Luke, zenbakia bi, beraz, hona etorri. 830 00:37:07,460 --> 00:37:11,270 >> Baina nire ezkerreko orain joan egon handitzen den Darren diete erreferentzia, 831 00:37:11,270 --> 00:37:15,160 eta hemen gakoa kentzen dituzten batuz, hau egiten jarraitu nahi dut, 832 00:37:15,160 --> 00:37:17,340 jakina, zuk nolako logika jarraitu. 833 00:37:17,340 --> 00:37:19,670 Baina nire eskuak dira inoiz atzeraka joan, 834 00:37:19,670 --> 00:37:23,861 horrek esan nahi du, naiz bakarrik inoiz mugitzen Nire batuz prozesua geratzen dira, 835 00:37:23,861 --> 00:37:26,360 eta hori funtsezkoa izango da Gure une bat besterik analisia. 836 00:37:26,360 --> 00:37:27,859 >> Beraz, gaur egun dezagun amaitzeko, hau oso azkar. 837 00:37:27,859 --> 00:37:31,650 Beraz, hiru datorrena, ondoren, lau datorrena, 838 00:37:31,650 --> 00:37:38,750 eta orain bost datorrena, ondoren, sei, eta zazpi, eta, ondoren, azkenik, zortzi. 839 00:37:38,750 --> 00:37:42,960 Algoritmo geldoena bezala sentitzen oraindik, baina ez badugu benetan 840 00:37:42,960 --> 00:37:45,510 exekutatu era bereko at erlojuaren abiadura, beraz, 841 00:37:45,510 --> 00:37:48,106 hitz egiten, bera izan beharko erloju ticking lehen bezala. 842 00:37:48,106 --> 00:37:48,605 Zergatik? 843 00:37:48,605 --> 00:37:51,100 Beno, dezagun bat Azken emaitza begiratu. 844 00:37:51,100 --> 00:37:56,990 >> Dezagun itzuli hemen, let me tira manifestazio bat ikusmen 845 00:37:56,990 --> 00:37:59,030 zer egin besterik ez dugu. 846 00:37:59,030 --> 00:38:06,110 Hemen zooma handitzea, honetan Hemen orria, Firefox kontatzea 847 00:38:06,110 --> 00:38:08,200 ilarara nahi dugun Koadro honetan,, dezagun 848 00:38:08,200 --> 00:38:11,260 burbuila ordenatu esan, dituen orain ondo ezagutzen gara, 849 00:38:11,260 --> 00:38:14,130 ordenatu, bertan zegoen, bat zuzenean nahiko, 850 00:38:14,130 --> 00:38:18,250 eta gaur egungo orain merge sort, eta horrek gure climactic amaiera izango da. 851 00:38:18,250 --> 00:38:21,530 Arrazoia, beraz, hartu zuen askoz gehiago Hemen gizakiak eta niri hitzez da, 852 00:38:21,530 --> 00:38:23,480 jakina, urrats bakoitza azaltzeko naiz. 853 00:38:23,480 --> 00:38:26,920 Baina zuk exekutatu besterik ez bada hau, askoz atsegin genuen burbuila ordenatu eta hautaketa 854 00:38:26,920 --> 00:38:30,890 sort ez begiz bakarrik, zaintza besterik zenbat gehiago eraginkortasunez 855 00:38:30,890 --> 00:38:33,330 la aprobetxatuz honetan zatiketa eta konkistatu 856 00:38:33,330 --> 00:38:39,150 ahal denean, datu multzo hori aplika daiteke ez baita tamaina zortzi, baina, nahiz eta askoz ere, 857 00:38:39,150 --> 00:38:39,970 askoz handiagoa. 858 00:38:39,970 --> 00:38:44,585 Sort batu duzu, ondoan ematen dut beste algoritmo hauen alde. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Hau da mingarria iritsi azkar, eta amaiera 861 00:38:58,530 --> 00:39:00,890 ez da bereziki climactic, amaitzeko besterik ez dute ordenatuta. 862 00:39:00,890 --> 00:39:05,280 Baina gakoa kentzen dela Begira zenbat azkarrago batu, ordenatu 863 00:39:05,280 --> 00:39:08,110 izan zen, naiz uste baduzu behintzat Mota besterik ez duzu aldatzeari. 864 00:39:08,110 --> 00:39:13,100 Azken denbora honetan egiten dugu bada, Dezagun freskatuz honetan, goazen atzera 865 00:39:13,100 --> 00:39:14,960 eta aukeratu burbuila ordenatu, eta besterik ez Jaurtiketa, 866 00:39:14,960 --> 00:39:17,330 dezagun aukeratu txertatzeko ordenatu, neurri ona. 867 00:39:17,330 --> 00:39:20,020 Eta oraingoan, berriro ere, dezagun merge sort aukeratu eta dezagun 868 00:39:20,020 --> 00:39:21,595 benetan alboko horiek albo exekutatu. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Eta ez da, hain zuzen ere, kasualitate bat. 871 00:39:26,930 --> 00:39:31,140 Zer eraginkortasunez egiten dut da dut dut nire sarrera banatzen zatian, berriz ere, 872 00:39:31,140 --> 00:39:32,240 eta berriro, eta berriro. 873 00:39:32,240 --> 00:39:35,590 Eta ez hainbeste bakarrik ahal duzun aldiz zatitzea zure sarrera halves sartu, utzi 874 00:39:35,590 --> 00:39:36,240 eta eskuineko. 875 00:39:36,240 --> 00:39:39,425 Zein da formula dela ikusten jarraitzen dugu duen banaketa deskribatzen erdia 876 00:39:39,425 --> 00:39:41,050 berriro, eta berriro, eta berriro, eta berriro? 877 00:39:41,050 --> 00:39:41,890 >> IKUSLEEN: Sartu n. 878 00:39:41,890 --> 00:39:42,760 >> HIZLARIA: Sartu n. 879 00:39:42,760 --> 00:39:46,300 Baina gero ez dago gakoa beste urrats bat da, Algoritmo hau ez da log n urratsak. 880 00:39:46,300 --> 00:39:48,992 Ziren bakarrik bada log n urratsak, arazo bera geundeke 881 00:39:48,992 --> 00:39:51,200 non ezin dugu orain arte bezala ziur dena ordenatuta. 882 00:39:51,200 --> 00:39:54,480 Gutxi n elementu begiratu behar duzu ziur egoteko n elementu ordenatzen dira, 883 00:39:54,480 --> 00:39:55,950 bestela fede-jauzi bat da. 884 00:39:55,950 --> 00:39:59,810 >> Beraz log txikieneko n urratsak, baina gako batuz urratsa honi buruz zer 885 00:39:59,810 --> 00:40:04,370 non batu dut nire ezkerreko erdia eta eskuineko erdi eta etapa osoan zehar ibili? 886 00:40:04,370 --> 00:40:06,980 Zenbat urrats da Batu nahi duten? 887 00:40:06,980 --> 00:40:10,150 Da n, baina ez nuen besterik batu da azken aldian. 888 00:40:10,150 --> 00:40:15,089 Habiaratuak deiak horietako bakoitzean, bakoitzaren On habiaratuak bateratzeak horiek, oraindik ere horrela antolatu nuen. 889 00:40:15,089 --> 00:40:18,380 Bi mutil hauek, batu nuen orduan, bi hauek mutilak, ondoren, bi mutil hauek eta abar. 890 00:40:18,380 --> 00:40:19,955 >> Beraz batuz nuen berriro, eta berriro. 891 00:40:19,955 --> 00:40:20,580 Zenbat aldiz? 892 00:40:20,580 --> 00:40:23,510 Beraz, aldi bakoitzean I banatzen du Zerrenda erditik, merge bat egin nuen. 893 00:40:23,510 --> 00:40:25,460 Zerrenda zatitzeko erdia, merge bat egin. 894 00:40:25,460 --> 00:40:28,570 Beraz bada zerrendan zatituz log n aldiz egin daiteke, 895 00:40:28,570 --> 00:40:33,880 eta batuz, azken finean hartzen n urrats, zer da orain goiko izan daiteke 896 00:40:33,880 --> 00:40:37,000 lasterketari lotuak gure algoritmoaren denbora? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Eta hain zuzen ere, hori da Hemen lortu dugu. 899 00:40:40,560 --> 00:40:44,650 Beraz, sentitzen ikusmen denean ikusten duzun Hiru gauza horiek exekutatu aldamenean 900 00:40:44,650 --> 00:40:47,930 n n kontra karratu aurkako n log n karratu. 901 00:40:47,930 --> 00:40:51,010 Zein funtsean ikusiko dugu, gaur ez ezik, etorkizunean, 902 00:40:51,010 --> 00:40:52,760 askoz azkarrago. 903 00:40:52,760 --> 00:40:56,010 Txalo Kopako A mutil hauek egiteko, Horiek saritzea da I estresa pilotak. 904 00:40:56,010 --> 00:41:00,260 Dezagun adjourn hemen gaur, eta astelehenean ikusiko dugu. 905 00:41:00,260 --> 00:41:02,255