1 00:00:00,000 --> 00:00:02,570 [Powered by Google Translate] [Artikulua 3 - erosoagoa] 2 00:00:02,570 --> 00:00:05,070 [Rob Bowden - Harvard Unibertsitatea] 3 00:00:05,070 --> 00:00:07,310 >> [Hau CS50 da. - CS50.TV] 4 00:00:07,310 --> 00:00:12,700 >> Beraz, lehenengo galdera Harritzeko worded. 5 00:00:12,700 --> 00:00:17,480 GDB aukera ematen dizu "arazteko" programa bat, baina, zehatzago esanda, zer ez duzu egin dezagun? 6 00:00:17,480 --> 00:00:22,590 Bat erantzun dut, eta ez dakit zer zehazki espero 7 00:00:22,590 --> 00:00:27,910 beraz, zerbait dut Asmatzeko da ildo aukera ematen dizu pausoz pauso 8 00:00:27,910 --> 00:00:31,540 programaren bidez oinez, elkarreragin, aldagai-aldaketa, gauza horiek guztiak egin - 9 00:00:31,540 --> 00:00:34,270 funtsean, guztiz kontrolatzeko programa baten exekuzioa 10 00:00:34,270 --> 00:00:38,410 eta egiaztatu emandako edozein programaren exekuzioa. 11 00:00:38,410 --> 00:00:43,030 Ezaugarri horiek Hargatik gauza arazteko duzu. 12 00:00:43,030 --> 00:00:44,830 Ongi da. 13 00:00:44,830 --> 00:00:50,520 Zergatik bitarra bilatu ez array bat horrela antolatu behar? 14 00:00:50,520 --> 00:00:53,360 Nork nahi du erantzutea? 15 00:00:56,120 --> 00:01:00,070 [Ikasleen] ez delako, ez du funtzionatzen ez bada horrela antolatu. >> Bai. [Barreak] 16 00:01:00,070 --> 00:01:04,910 Ez da antolatuz gero, ezinezkoa da erditik zatitu 17 00:01:04,910 --> 00:01:07,850 ezagutu eta ezkerreko dena ez da hain eta eskuinera guztia 18 00:01:07,850 --> 00:01:10,490 erdiko balioa baino handiagoa da. 19 00:01:10,490 --> 00:01:12,790 Beraz horrela antolatu behar da. 20 00:01:12,790 --> 00:01:14,170 Ongi da. 21 00:01:14,170 --> 00:01:17,570 Zergatik bubble n karratu O sort da? 22 00:01:17,570 --> 00:01:23,230 Does Edozeinek lehen zer burbuila sort da goi-mailako ikuspegi oso azkarra eman nahi? 23 00:01:25,950 --> 00:01:33,020 [Ikasleen] elementu bakoitzaren bidez, funtsean, joan eta lehenengo elementu batzuk egiaztatu. 24 00:01:33,020 --> 00:01:37,150 Oraindik bada, non swap duzun, ondoren, hurrengo zenbait elementu eta horrela egiaztatu duzu. 25 00:01:37,150 --> 00:01:40,770 Amaieran iritsi, eta gero elementu handiena da, amaieran jartzen badakizu, 26 00:01:40,770 --> 00:01:42,750 beraz, orduan igaro alde batetara utzi, 27 00:01:42,750 --> 00:01:48,490 eta aldi bakoitzean, ez da aldaketarik egin duzun arte bat gutxiago elementu egiaztatu behar duzu. >> Bai. 28 00:01:48,490 --> 00:01:58,470 Deitzen da burbuila sort irauli array bada bere aldean sortu delako da eta behera, bertikalean, 29 00:01:58,470 --> 00:02:03,100 gero, balio handiek beheraino hondoratzear eta balioak txikiak burbuila goian. 30 00:02:03,100 --> 00:02:05,210 Hau da, bere izena nola lortu. 31 00:02:05,210 --> 00:02:08,220 Eta bai, besterik ez duzu bidez. 32 00:02:08,220 --> 00:02:11,190 Array bidez jarraitzen duzu, balio handiagoa aldaketa 33 00:02:11,190 --> 00:02:14,040 balio handiena lortu beheraino. 34 00:02:14,040 --> 00:02:17,500 >> Zergatik da n karratu O? 35 00:02:18,690 --> 00:02:24,620 Lehenik eta behin, ez du inor zergatik n O karratu esan nahi? 36 00:02:24,620 --> 00:02:28,760 [Ikasleak] run bakoitzean delako n aldiz jartzen da. 37 00:02:28,760 --> 00:02:32,100 Bakarrik ahal izateko, ziur duzula handiena elementu guztiak hartu behera, 38 00:02:32,100 --> 00:02:35,230 orduan errepikatu elementu asko jo behar duzu. >> Bai. 39 00:02:35,230 --> 00:02:41,800 Beraz, kontuan hartu zer big O esan nahi du, eta zer da big Omega bitartez. 40 00:02:41,800 --> 00:02:50,560 Big O nola motela benetan exekutatu aritzeko goiko bezalakoa da. 41 00:02:50,560 --> 00:02:58,990 Beraz, n karratu O esanez, ez da n O edo, bestela, izan da exekutatu ahal izango litzateke 42 00:02:58,990 --> 00:03:02,640 denbora lineala, baina n cubed O da 43 00:03:02,640 --> 00:03:06,390 n cubed O mugatzen delako. 44 00:03:06,390 --> 00:03:12,300 N karratu O mugatzen bada, gero eta mugatzen n cubed ere. 45 00:03:12,300 --> 00:03:20,280 Beraz, N karratu, eta txarrena absolutuaren kasuan, ezin da egin n karratu baino hobeto, 46 00:03:20,280 --> 00:03:22,830 hau da, zergatik karratu N O da. 47 00:03:22,830 --> 00:03:31,200 Beraz, apur bat math ikusteko nola dator n karratu izango da, 48 00:03:31,200 --> 00:03:40,530 ditugu gure zerrendan bost gauza bada, lehen aldiz, zenbat trukeak izan behar potentzialki dugu 49 00:03:40,530 --> 00:03:47,170 Helburu hori lortzeko? Dezagun benetan besterik ez - 50 00:03:47,170 --> 00:03:52,040 Zenbat trukeak dira burbuila sort lehen run array bidez izan dugu? 51 00:03:52,040 --> 00:03:53,540 [Ikasleen] n - 1. >> Bai. 52 00:03:53,540 --> 00:03:58,340 >> 1 - 5 elementu daude bada, n egin behar dugu. 53 00:03:58,340 --> 00:04:01,100 Gero, bigarren bat zenbat trukeak dira, joan egin beharko dugu? 54 00:04:01,100 --> 00:04:03,440 [Ikasleen] n - 2. >> Bai. 55 00:04:03,440 --> 00:04:11,640 Eta hirugarren izan da n - 3, eta, ondoren, erosotasuna, azken bi idatzi egingo dut 56 00:04:11,640 --> 00:04:15,270 ondoren, 2 trukeak eta swap 1 egin behar dugu. 57 00:04:15,270 --> 00:04:19,899 Azkena edo ez benetan gertatuko uste dut. 58 00:04:19,899 --> 00:04:22,820 Da swap? Ez dakit. 59 00:04:22,820 --> 00:04:26,490 Beraz, trukeak kopuru osoa edo, gutxienez, konparazioak egin behar duzu. 60 00:04:26,490 --> 00:04:29,910 Nahiz eta ez duzu swap, oraindik behar duzu balioak alderatzeko. 61 00:04:29,910 --> 00:04:33,910 Beraz, n - 1 array bidez lehen run konparazioak. 62 00:04:33,910 --> 00:04:42,050 Berrantolatzeko gauza horiek bada, dezagun benetan egiteko sei gauza gauza pila beraz nicely 63 00:04:42,050 --> 00:04:44,790 eta, ondoren, 3 egin dut, 2, 1. 64 00:04:44,790 --> 00:04:49,910 Beraz, zenbateko horiek rearranging, zenbat konparazioak egiten dugu ikusi nahi dugu 65 00:04:49,910 --> 00:04:52,700 osoa algoritmoa. 66 00:04:52,700 --> 00:04:56,550 Beraz, bada guys horiek behera ekarri dugu hemen, 67 00:04:56,550 --> 00:05:07,470 ondoren, oraindik ari gara Hala ere, askotan konparazioak ziren summing. 68 00:05:07,470 --> 00:05:13,280 Baina horiek laburbildu dugu eta horiek laburbildu dugu eta horiek laburbildu dugu, 69 00:05:13,280 --> 00:05:18,130 oraindik ere arazo bera da. Bereziki talde horiek batzea besterik ez dugu. 70 00:05:18,130 --> 00:05:22,400 >> Beraz, gaur egun 3 ari gara summing n-en. Ez da besterik ez 3 n. 71 00:05:22,400 --> 00:05:27,650 Beti n / 2 n izango da. 72 00:05:27,650 --> 00:05:29,430 Beraz, hemen 6 gertatuko dugu. 73 00:05:29,430 --> 00:05:34,830 10 gauza izan bada, orduan taldekatze hau egin izan dugu 5 gauza bikote desberdin 74 00:05:34,830 --> 00:05:37,180 eta, azkenean, n + n + n + n + n. 75 00:05:37,180 --> 00:05:45,840 Beraz, beti ari zaren n / 2 n, eta, beraz, hau da jot dugu n karratu / 2. 76 00:05:45,840 --> 00:05:48,890 Eta beraz, nahiz eta erdiak faktorea da, eta hori gertatzen da, etorri da 77 00:05:48,890 --> 00:05:54,190 Izan ere, array zehar iterazio bakoitzerako bitartez 1 gutxiago alderatu dugu delako 78 00:05:54,190 --> 00:05:58,040 beraz, nola lortu 2 baino gehiago ditugu, baina oraindik n karratu. 79 00:05:58,040 --> 00:06:01,650 Ez dugu erdi etengabeko faktorea buruz zaintzeko. 80 00:06:01,650 --> 00:06:07,760 O big stuff asko math sort hau egiteko mota hau atsegin oinarritzen da, beraz, 81 00:06:07,760 --> 00:06:12,260 batuketa aritmetiko eta geometrikoak serie stuff egiten, 82 00:06:12,260 --> 00:06:17,750 baina horietako gehienak Ikastaro honetan nahiko erraza da. 83 00:06:17,750 --> 00:06:19,290 Ongi da. 84 00:06:19,290 --> 00:06:24,430 Zergatik txertatzeko sort n Omega? Zer esan nahi du omega? 85 00:06:24,430 --> 00:06:27,730 [Bi ikasle aldi berean hitz ulertezina] >> Bai. 86 00:06:27,730 --> 00:06:30,630 Omega dezakezu beheko loturik gisa pentsatu. 87 00:06:30,630 --> 00:06:36,550 >> Beraz, ez du axola nola eraginkorra zure txertatzeko sort algoritmoa da, 88 00:06:36,550 --> 00:06:41,810 zerrenda pasa den edozein izanik ere, beti gutxienez n gauzak alderatzea 89 00:06:41,810 --> 00:06:44,620 edo gauza n zehar batetik bestera joateko. 90 00:06:44,620 --> 00:06:47,280 Zergatik da hori? 91 00:06:47,280 --> 00:06:51,190 [Ikasleen] delako zerrendan dagoeneko antolatuz gero, lehen iterazio bidez 92 00:06:51,190 --> 00:06:54,080 elementu oso lehen bakarrik dezakezu bermatzeko gutxienez, 93 00:06:54,080 --> 00:06:56,490 eta bigarren iterazio dezakezu bermatzen lehen bi dira 94 00:06:56,490 --> 00:07:00,010 zerrendan gainerako ordenatuko hori ezagutzen ez duzulako. >> Bai. 95 00:07:00,010 --> 00:07:08,910 Guztiz horrela antolatu zerrenda pasatzen bada, gutxienez, joan elementu guztiak 96 00:07:08,910 --> 00:07:12,180 ezer ez mugitu behar dira inguruan ikusteko. 97 00:07:12,180 --> 00:07:14,720 Beraz, baino gehiago pasatzen zerrenda eta oh, hau da, dagoeneko horrela antolatu esaten, 98 00:07:14,720 --> 00:07:18,240 ezinezkoa da eta ordenatuko zenekien elementu bakoitzaren egiaztatu arte 99 00:07:18,240 --> 00:07:20,660 ordena ordenatuko dira. 100 00:07:20,660 --> 00:07:25,290 Txertatzeko sort aritzeko txikiagoa Beraz, n Omega dago. 101 00:07:25,290 --> 00:07:28,210 Zer da txarrena kasuan merge sort denbora exekutatzen 102 00:07:28,210 --> 00:07:31,390 kasurik okerrenean big O berriro? 103 00:07:31,390 --> 00:07:37,660 Txarrena kasuan agertokia, merge sort nola ez korrika? 104 00:07:42,170 --> 00:07:43,690 [Ikasleen] N log n. >> Bai. 105 00:07:43,690 --> 00:07:49,990 Ordenatzeko azkarrena, oro har, algoritmoak n log n dira. Ezin duzu egin, hobeto. 106 00:07:51,930 --> 00:07:55,130 >> Daude kasu bereziak, eta dugu denbora izanez gero, gaur egun, baina seguruenik won't dugu 107 00:07:55,130 --> 00:07:59,330 horrela, ez n log n baino hobeto ikusi ahal izan genuen. 108 00:07:59,330 --> 00:08:04,050 Baina, oro har, kasu honetan, ezin duzu n log n baino hobea. 109 00:08:04,050 --> 00:08:09,680 Eta batu sort gertatzen ko n log n Ikastaro hau dela jakin behar duzu. 110 00:08:09,680 --> 00:08:13,260 Eta, beraz, benetan dugu gaur egun ezartzeko. 111 00:08:13,260 --> 00:08:18,070 Eta, azkenik, hiru esaldi baino gehiago, nola aukeraketa sort lan egiten du? 112 00:08:18,070 --> 00:08:20,370 Ba al du norbaitek nahi erantzun, eta zure esaldi zenbatu dut 113 00:08:20,370 --> 00:08:22,390 3 baino gehiago joaten bada, 114 00:08:25,530 --> 00:08:28,330 Does Edozeinek aukeraketa sort gogoratzen? 115 00:08:31,280 --> 00:08:37,809 Aukeraketa sort nahiko erraza izan ohi da, izena gogoratzen. 116 00:08:37,809 --> 00:08:45,350 Array batetik bestera joateko baino gehiago besterik ez duzu, edozein izanda ere, balio handiena edo txikiena 117 00:08:45,350 --> 00:08:47,290 edozein dela ere, ordena sartu zaren ordenatzeko 118 00:08:47,290 --> 00:08:50,750 Beraz, demagun txikiena etatik handiena ordenatzeko ari gara. 119 00:08:50,750 --> 00:08:55,250 Batetik bestera joateko, array zehar, edozein gutxieneko elementu bila, 120 00:08:55,250 --> 00:08:59,750 hautatu, eta, ondoren, besterik ez da swap edozein leku lehenengo. 121 00:08:59,750 --> 00:09:04,090 Eta gero, array zehar bigarren mendatean, gutxieneko elementu bila, berriz, 122 00:09:04,090 --> 00:09:07,490 aukeratu da, eta, ondoren, bigarren postua trukatzeko. 123 00:09:07,490 --> 00:09:10,650 Beraz, ari gara produktuak biltzea eta gutxieneko balioak aukeratuz 124 00:09:10,650 --> 00:09:16,050 eta horiek txertatu array aurrean sartu da horrela antolatu arte. 125 00:09:19,210 --> 00:09:21,560 Horri buruzko galderak? 126 00:09:21,560 --> 00:09:25,710 >> Hauek nahitaez betetzeko denean pset bidaltzen ari zaren duzu forma agertzen dira. 127 00:09:29,010 --> 00:09:32,360 Hauek dira, funtsean, horien erantzunak. 128 00:09:32,360 --> 00:09:34,230 Ongi da, eta, beraz, gaur egun arazoak kodifikazioa. 129 00:09:34,230 --> 00:09:40,140 Dagoeneko bidali nuen email baino gehiago - Ba inor ez email hori? Ongi da. 130 00:09:40,140 --> 00:09:46,630 Dagoeneko bidali nuen email baino gehiago ari gara espazio erabiliz, 131 00:09:46,630 --> 00:09:52,120 eta nire izenaren gainean klik egiten baduzu, beraz, behealdean dut uste dut 132 00:09:52,120 --> 00:09:57,170 atzeraka r delako, baina nire izenaren gainean klik egiten baduzu, 2 revisions ikusiko duzu. 133 00:09:57,170 --> 00:10:02,650 Berrikusketa, ordua: 1 behar I dagoeneko kopiatu eta kodea itsatsi Espazioak 134 00:10:02,650 --> 00:10:06,900 bilaketa gauza inplementatzeko izan duzu. 135 00:10:06,900 --> 00:10:10,540 Eta 2 (r) en berrikusketa, ordua: sort gauza ezartzeko ondoren izango da. 136 00:10:10,540 --> 00:10:15,770 Beraz, nire berrikusketa, ordua: 1 klik egin dezakezu, eta hortik landu. 137 00:10:17,350 --> 00:10:22,060 Eta orain binary bilaketa ezartzea nahi dugu. 138 00:10:22,060 --> 00:10:26,470 >> Does Edozeinek goi-mailako azalpen pseudocode bat eman nahi 139 00:10:26,470 --> 00:10:31,440 zer bilaketa egin beharko dugu? Bai. 140 00:10:31,440 --> 00:10:36,170 [Ikasleen] hartu besterik ez duzu array-erdian ikusi eta zer nahi baduzu bila 141 00:10:36,170 --> 00:10:38,650 hori baino gutxiago edo hori baino gehiago da. 142 00:10:38,650 --> 00:10:41,080 Eta ez bada, gutxi gorabehera, joan den gutxiago erdia, 143 00:10:41,080 --> 00:10:44,750 eta gehiago da bada, joan gehiago erdia den eta errepikatu duzu, gauza bat besterik ez duzu iritsi arte. 144 00:10:44,750 --> 00:10:46,570 [Bowden] Bai. 145 00:10:46,570 --> 00:10:51,320 Oharra gure zenbakiak array dagoeneko ordenatuko 146 00:10:51,320 --> 00:10:57,190 eta, beraz, horrek esan nahi du abantaila hartu daiteke hori eta lehen egiaztatu ahal izan genuen, 147 00:10:57,190 --> 00:11:00,390 ados, 50 zenbakia bila nabil. 148 00:11:00,390 --> 00:11:03,720 Beraz, erdi-erdian ezin dut joan. 149 00:11:03,720 --> 00:11:07,380 Erdi gogorra da, gauza bat ere definitzeko, 150 00:11:07,380 --> 00:11:10,820 baina dezagun, besterik gabe esan dugu beti erditik moztu. 151 00:11:10,820 --> 00:11:14,420 Hortaz, hona hemen 8 gauzak ditugu, beraz, erdian 16 izango litzateke. 152 00:11:14,420 --> 00:11:17,330 50 bila nabil, eta, beraz, 50 16 baino handiagoa da. 153 00:11:17,330 --> 00:11:21,310 Beraz, gaur egun, batez ere, ezin dut tratatzeko nire array elementu horiek gisa. 154 00:11:21,310 --> 00:11:23,450 Bota dut dena, 16. 155 00:11:23,450 --> 00:11:27,440 Orain nire array besterik ez da 4 elementu hauek, eta nik errepikatu. 156 00:11:27,440 --> 00:11:31,910 Orduan erdian berriro aurkitu nahi dut, hau da, 42 izango dira. 157 00:11:31,910 --> 00:11:34,730 42 50 baino txikiagoa da, beraz, bota dut bi elementu horiek. 158 00:11:34,730 --> 00:11:36,890 Hau da nire gainerako array da. 159 00:11:36,890 --> 00:11:38,430 Erdian berriro aurkitu dut. 160 00:11:38,430 --> 00:11:42,100 50 adibide txarra izan zen uste dut izan dut beti urrun bota gauzak ezkerrean, 161 00:11:42,100 --> 00:11:48,280 baina, neurri berean, naiz badut zerbait bilatzen 162 00:11:48,280 --> 00:11:52,100 eta elementu baino gutxiago da gaur egun naiz begira, 163 00:11:52,100 --> 00:11:55,080 ondoren, eskubidea dena urrun bota dut. 164 00:11:55,080 --> 00:11:58,150 Beraz, gaur egun ezartzeko behar dugu. 165 00:11:58,150 --> 00:12:02,310 Iragarki tamaina gainditu behar ditugu. 166 00:12:02,310 --> 00:12:06,730 Era berean, ez dugu behar kodea hard-tamaina. 167 00:12:06,730 --> 00:12:11,640 Beraz, bada, kentzeko lortuko dugu # define - 168 00:12:19,630 --> 00:12:21,430 Ongi da. 169 00:12:21,430 --> 00:12:27,180 Nola nicely irudikatu dut zenbakiak array tamaina da gaur egun? 170 00:12:27,180 --> 00:12:30,950 >> Zenbat elementu zenbakiak array dira? 171 00:12:30,950 --> 00:12:33,630 [Ikasleak] zenbakiak, parentesi artean, luzera? 172 00:12:33,630 --> 00:12:36,600 [Bowden] Horrek ez du ez C. existitzen 173 00:12:36,600 --> 00:12:38,580 Beharra. Luzera. 174 00:12:38,580 --> 00:12:42,010 Arrayak ez dute propietate, array jabetza luzera ez da, beraz, 175 00:12:42,010 --> 00:12:45,650 du soilik eman luze Hala ere gertatzen da. 176 00:12:48,180 --> 00:12:51,620 [Ikasleak] Ikus zenbat memoria ditu, eta zenbat by zatitzea - ​​>> Bai. 177 00:12:51,620 --> 00:12:55,810 Beraz, nola egin dezaket zenbat memoria ditu ikusten dugu? >> [Ikasleak] Sizeof. >> Bai, sizeof. 178 00:12:55,810 --> 00:13:01,680 Sizeof operadorea den zenbakiak array tamaina itzuli da. 179 00:13:01,680 --> 00:13:10,060 Eta hori da ordea askotan osokoa izan badira zenbaki oso bat tamaina 180 00:13:10,060 --> 00:13:14,050 geroztik zenbat memoria benetan da hartzen. 181 00:13:14,050 --> 00:13:17,630 Beraz, bada, gauzak array nahi dut, 182 00:13:17,630 --> 00:13:20,560 ondoren, osoko baten tamaina zatitzea nahi dut. 183 00:13:22,820 --> 00:13:26,010 Ongi da. Beraz, aukera ematen dizu pasatzeko tamaina Niri hemen. 184 00:13:26,010 --> 00:13:29,430 Zergatik tamaina gainditu guztiak behar dut? 185 00:13:29,430 --> 00:13:38,570 Zergatik ezin egin dut hemen int size = sizeof (haystack) / sizeof (int)? 186 00:13:38,570 --> 00:13:41,490 Zergatik ez du funtzionatzen? 187 00:13:41,490 --> 00:13:44,470 [Ikasleak] ez da global aldagai bat. 188 00:13:44,470 --> 00:13:51,540 [Bowden] Haystack badagoela eta zenbakiak ari gara haystack gisa pasatuz, 189 00:13:51,540 --> 00:13:54,700 eta zer etorri foreshadowing mota da. Bai. 190 00:13:54,700 --> 00:14:00,170 [Ikasleak] Haystack besterik ez da erreferentzia, eta, beraz, itzultzeko nola big erreferentzia dela litzateke. 191 00:14:00,170 --> 00:14:02,150 Bai. 192 00:14:02,150 --> 00:14:09,000 Zalantzan hitzaldia dut ikusi oraindik pila benetan, eskubidea? 193 00:14:09,000 --> 00:14:11,270 Besterik ez dugu horri buruz hitz egiten. 194 00:14:11,270 --> 00:14:16,090 Beraz, pila bat da, non zure aldagai guztiak gordetzen dira egingo. 195 00:14:16,090 --> 00:14:19,960 >> Duen edozein aldagai tokiko memoria esleitu pila joan 196 00:14:19,960 --> 00:14:24,790 eta funtzio bakoitzak bere espazioa lortzen pila, bere pila-markoa da, zer deitzen. 197 00:14:24,790 --> 00:14:31,590 Beraz, nagusiak bere pila-markoa du, eta horren barruan zenbakiak array hau existitzen da, 198 00:14:31,590 --> 00:14:34,270 eta tamaina sizeof (zenbakiak) izango da. 199 00:14:34,270 --> 00:14:38,180 Elementuak tamainaren arabera banatzen zenbakiak tamaina izan da, 200 00:14:38,180 --> 00:14:42,010 baina nagusiak pila marko barruan bizitza guztiak. 201 00:14:42,010 --> 00:14:45,190 Bilaketa deitzen diogu, bilatu bere pila-markoa lortzen, 202 00:14:45,190 --> 00:14:48,840 bere espazio, bere aldagai tokiko guztiak gordetzeko. 203 00:14:48,840 --> 00:14:56,420 Baina argumentuak hauek hain haystack ez da osoa array honen kopia bat. 204 00:14:56,420 --> 00:15:00,990 Ez dugu kopia bat bezala sartu bilaketa array osoa gainditu. 205 00:15:00,990 --> 00:15:04,030 Array hori erreferentzia bat besterik ez da pasatzen. 206 00:15:04,030 --> 00:15:11,470 Beraz, bilaketa zenbaki horiek sartu ahal izango da erreferentzia honen bidez. 207 00:15:11,470 --> 00:15:17,100 Oraindik gauza nagusia pila marko barruan bizi diren sartzeko 208 00:15:17,100 --> 00:15:22,990 baina funtsean, erakusle dugu, eta horrek laster izan beharko luke, 209 00:15:22,990 --> 00:15:24,980 hau da, zein erakusle dira. 210 00:15:24,980 --> 00:15:29,400 Erakusleak besterik ez dira gauza erreferentziak, eta gauzak sartzeko erakusleak erabili ahal izango duzu 211 00:15:29,400 --> 00:15:32,030 beste gauza pila markoak dira. 212 00:15:32,030 --> 00:15:37,660 Beraz, nahiz eta kopuru nagusia tokiko, oraindik ezin dugu sartu erakuslea honen bidez. 213 00:15:37,660 --> 00:15:41,770 Baina besterik ez geroztik erakuslea eta erreferentzia bat besterik ez da, 214 00:15:41,770 --> 00:15:45,040 sizeof (haystack) erreferentzia bera tamaina du. 215 00:15:45,040 --> 00:15:47,950 Ez du itzuli beharreko gauza da seinalatuz tamaina. 216 00:15:47,950 --> 00:15:51,110 Ez itzultzeko zenbakiak benetako tamaina. 217 00:15:51,110 --> 00:15:55,660 Eta, beraz, hau ez da lanera joan nahi dugun bezala. 218 00:15:55,660 --> 00:15:57,320 >> Horri buruzko galderak? 219 00:15:57,320 --> 00:16:03,250 Erakusleak dira sartuko joan xehetasun nabarmen gehiago góry datozen asteetan. 220 00:16:06,750 --> 00:16:13,740 Eta hau da, zergatik gauzak ikusten dituzu, bilaketa gauza gehienak edo sort gauza asko, 221 00:16:13,740 --> 00:16:16,990 ia guztiak ari dira array benetako tamainan hartu behar du, 222 00:16:16,990 --> 00:16:20,440 C, zeren eta, ez daki zer tamaina array dugu. 223 00:16:20,440 --> 00:16:22,720 Pasatzen da eskuz sartu behar duzu 224 00:16:22,720 --> 00:16:27,190 Eta ezin eskuz array osoa pasatzen ari zaren besterik ez delako erreferentzia pasatzen 225 00:16:27,190 --> 00:16:30,390 eta ezin da tamaina erreferentzia. 226 00:16:30,390 --> 00:16:32,300 Ongi da. 227 00:16:32,300 --> 00:16:38,160 Beraz, gaur egun zer zen azaldu aurretik ezartzea nahi dugu. 228 00:16:38,160 --> 00:16:41,530 Gainean lan egin ahal izango duzu minutu bat, 229 00:16:41,530 --> 00:16:45,250 eta ez duzu dena primeran% 100 lan lortzean kezkatu. 230 00:16:45,250 --> 00:16:51,410 Just idatzi pseudocode erdia nola lan egin behar dela uste duzu. 231 00:16:52,000 --> 00:16:53,630 Ongi da. 232 00:16:53,630 --> 00:16:56,350 Erabat honekin egin oraindik behar No. 233 00:16:56,350 --> 00:17:02,380 Baina ez du inor sentitzen hain urruti dute eroso, 234 00:17:02,380 --> 00:17:05,599 antzeko zerbait batera lan egin ahal izango dugu? 235 00:17:05,599 --> 00:17:09,690 Does Edozeinek nahi boluntario? Edo ausaz egingo dut hautatu. 236 00:17:12,680 --> 00:17:18,599 Ez du neurria edozein baina zerbait aldatu ahal izango dugu, lan-egoera. 237 00:17:18,599 --> 00:17:20,720 [Ikasleak] Sure. >> Ados. 238 00:17:20,720 --> 00:17:27,220 Beraz, berrikuspena gorde Save little ikonoan klik eginez. 239 00:17:27,220 --> 00:17:29,950 Ramya zara, ezta? >> [Ikasleak] Bai. >> [Bowden] Larreina. 240 00:17:29,950 --> 00:17:35,140 Beraz, orain zure berrikuspena ikusi ahal izango dut eta denek tira Berrikusketaren. 241 00:17:35,140 --> 00:17:38,600 Eta hemen dugu - Ongi da. 242 00:17:38,600 --> 00:17:43,160 Beraz Ramya konponbidea errekurtsiboa da, hau da, behin betiko baliozko irtenbide bat joan zen. 243 00:17:43,160 --> 00:17:44,970 Bi modu daude arazo hau egin ahal izango duzu. 244 00:17:44,970 --> 00:17:48,060 Bai egin dezakezu iteratively edo errekurtsiboki. 245 00:17:48,060 --> 00:17:53,860 Egin daiteke errekurtsiboki aurkituko duzu gehien arazoak ere egin behar iteratively. 246 00:17:53,860 --> 00:17:58,510 Hortaz, hona hemen egin dugun errekurtsiboki. 247 00:17:58,510 --> 00:18:03,730 >> Ba al du norbaitek nahi zer funtzio bat recursive definitzeko esan nahi du? 248 00:18:07,210 --> 00:18:08,920 [Ikasleak] funtzioa eduki deitzen bera 249 00:18:08,920 --> 00:18:13,470 eta, ondoren, dei bera dator arte egia eta egia. >> Bai. 250 00:18:13,470 --> 00:18:17,680 Recursive funtzio bat besterik ez da, bera deitzen duen funtzioa. 251 00:18:17,680 --> 00:18:24,140 Badira hiru gauza handia recursive funtzio bat izan behar duela. 252 00:18:24,140 --> 00:18:27,310 Lehenengo eta behin, jakina, bera deitzen da. 253 00:18:27,310 --> 00:18:29,650 Bigarren oinarri-kasua da. 254 00:18:29,650 --> 00:18:33,390 Beraz, uneren batean funtzioa bera deituz gelditzeko behar da, 255 00:18:33,390 --> 00:18:35,610 eta horrek zer oinarri-kasua da. 256 00:18:35,610 --> 00:18:43,860 Beraz, hemen gelditu behar dugu, ezagutzen dugu, amore eman behar dugu gure bilaketa 257 00:18:43,860 --> 00:18:48,150 Irteeran berdinen amaieran, eta joan beharko dugu zer esan nahi duen. 258 00:18:48,150 --> 00:18:52,130 Baina, azkenik, funtzio errekurtsiboa garrantzitsua da azken gauza: 259 00:18:52,130 --> 00:18:59,250 funtzioak behar nolabait hurbiltzen base kasuan. 260 00:18:59,250 --> 00:19:04,140 Atsegin dut ari zaren ez bada benetan ezer eguneratzeko bigarren dei errekurtsiboa egin duzu, 261 00:19:04,140 --> 00:19:07,880 ari zaren literalki funtzioa deituz berriro bera argumentuak 262 00:19:07,880 --> 00:19:10,130 aldagai global eta ez dute ezer aldatu edo, 263 00:19:10,130 --> 00:19:14,430 inoiz ez dira oinarri kasuan iritsi da, kasu honetan hori da txarra. 264 00:19:14,430 --> 00:19:17,950 Infinitua errekurtsibitateko eta pilaren gainezkatzea bat izan behar da izango da. 265 00:19:17,950 --> 00:19:24,330 Baina hemen eguneratzea hori dugu eguneratzeko + amaiera / 2 gertatzen ari den ikusiko dugu, 266 00:19:24,330 --> 00:19:28,180 azken argumentua eguneratzen ari gara hemen, hasierako argumentua eguneratzen ari gara hemen. 267 00:19:28,180 --> 00:19:32,860 Beraz, dei errekurtsiboak guztietan zerbait eguneratzen ari gara. Ongi da. 268 00:19:32,860 --> 00:19:38,110 Gurekin oinez zure irtenbidea bidez nahi al duzu? >> Sure. 269 00:19:38,110 --> 00:19:44,270 SearchHelp erabiltzen dut, beraz, aldi bakoitzean funtzio-dei hau egiten dut 270 00:19:44,270 --> 00:19:47,910 Non array bila nabil hasiera eta amaiera 271 00:19:47,910 --> 00:19:49,380 non array nabil. 272 00:19:49,380 --> 00:19:55,330 >> Pauso bakoitzean non erdiko elementu, hau da, Irteeran + amaiera / 2 da esaten, 273 00:19:55,330 --> 00:19:58,850 hau da, zer bilatzen ari gara berdinak? 274 00:19:58,850 --> 00:20:04,650 Eta bada, ondoren, aurkitu genuen, eta uste dut hori lortzen errekurtsio-maila gainditu. 275 00:20:04,650 --> 00:20:12,540 Eta hori ez da egia, eta, ondoren, array erdiko balioa ez dela handiegia den ala ez egiaztatu dugu, 276 00:20:12,540 --> 00:20:19,320 horrelako array ezker erdia, hasieratik erdiko indizea. 277 00:20:19,320 --> 00:20:22,710 Eta bestela amaiera erdia egiten dugu. 278 00:20:22,710 --> 00:20:24,740 [Bowden] Larreina. 279 00:20:24,740 --> 00:20:27,730 Hori ona soinuak. 280 00:20:27,730 --> 00:20:36,640 Ongi da, pare bat gauza, beraz, eta, benetan, oso goi-mailako gauza bat da 281 00:20:36,640 --> 00:20:41,270 inoiz jakin behar da ikastaro hau, baina egia da. 282 00:20:41,270 --> 00:20:46,080 Errekurtsiboa funtzioak, beti entzuten ari dira tratu txarra 283 00:20:46,080 --> 00:20:51,160 errekurtsiboki deitzen bada zeure burua gehiegi aldiz, pilaren gainezkatzea delako lortuko duzu 284 00:20:51,160 --> 00:20:54,990 geroztik, lehen esan dudan bezala, funtzio bakoitzak bere pila-markoa lortzen. 285 00:20:54,990 --> 00:20:59,500 Beraz, funtzioa errekurtsiboa dei bakoitzak bere pila-markoa jasotzen du. 286 00:20:59,500 --> 00:21:04,140 Beraz, bada, 1.000 dei errekurtsiboak egiten baduzu, 1.000 pila fotogramak eskuratzen 287 00:21:04,140 --> 00:21:08,390 eta azkar eramaten gehiegi pila markoak eta gauzak apurtu behar izan duzu. 288 00:21:08,390 --> 00:21:13,480 Beraz, zergatik recursive funtzioak dira, oro har, txarra. 289 00:21:13,480 --> 00:21:19,370 Baina funtzio errekurtsiboa azpimultzo atsegina da izeneko buztan-errekurtsiboa funtzioak, 290 00:21:19,370 --> 00:21:26,120 eta hau gertatzen da, non konpilatzailea ohar hau adibide bat izan 291 00:21:26,120 --> 00:21:29,920 eta egin beharko lukete, uste dut Clang pasatzen duzu-O2 Ez 292 00:21:29,920 --> 00:21:33,250 ondoren, nabarituko hau da buztan errekurtsiboa izango da eta gauza onak egiteko. 293 00:21:33,250 --> 00:21:40,050 >> Dei errekurtsiboa bakoitzeko eta gehiagoko berriz pila berean marko berrerabiltzeko izango da. 294 00:21:40,050 --> 00:21:47,010 Eta, beraz, pilaren markoa bera geroztik erabiltzen ari zara, ez duzu kezkatu beharrik 295 00:21:47,010 --> 00:21:51,690 inoiz pilatu gainezka, eta aldi berean, aurretik esan duzun bezala, 296 00:21:51,690 --> 00:21:56,380 non behin egia itzuliko gero, itzuli pila fotograma horiek guztiak ditu 297 00:21:56,380 --> 00:22:01,740 eta SearchHelp 9ra itzultzeko dei 10ean, 8an itzultzeko. 298 00:22:01,740 --> 00:22:05,360 Beraz, ez da beharrezkoa denean, funtzio buztana recursive gertatuko. 299 00:22:05,360 --> 00:22:13,740 Eta beraz, zer egiten ari da funtzio-buztana hau recursive oharra dei searchHelp edozein 300 00:22:13,740 --> 00:22:18,470 dei errekurtsiboa dela egiten da, zer itzuli da. 301 00:22:18,470 --> 00:22:25,290 Beraz, lehen deialdian eta SearchHelp, berehala bai dugu itzultzeko faltsu, 302 00:22:25,290 --> 00:22:29,590 berehala itzultzeko egia, edo dei errekurtsiboa bat egiten dugu SearchHelp 303 00:22:29,590 --> 00:22:33,810 non zer itzultzen ari gara, zer dei hori itzuli. 304 00:22:33,810 --> 00:22:51,560 Eta ezin dugu hau egin dugu antzeko zerbait int x = SearchHelp, bueltan x * 2 bada, 305 00:22:51,560 --> 00:22:55,440 ausazko aldaketa batzuk. 306 00:22:55,440 --> 00:23:01,470 >> Beraz, orain dei errekurtsiboa honetan, int x = SearchHelp dei errekurtsiboa 307 00:23:01,470 --> 00:23:05,740 jada ez buztana errekurtsiboa da benetan ez dituelako itzuli 308 00:23:05,740 --> 00:23:10,400 itzuli aurreko pila marko bat da, beraz, funtzio dei aurreko 309 00:23:10,400 --> 00:23:13,040 ondoren, zerbait bueltan balioa. 310 00:23:13,040 --> 00:23:22,190 Beraz, hau ez da buztana recursive, baina zer da nicely buztana recursive aurretik izan genuen. Bai. 311 00:23:22,190 --> 00:23:27,000 [Ikasleak] Ez luke oinarri bigarren kasua da hautatuta lehenengo 312 00:23:27,000 --> 00:23:30,640 egoera bat izan dezake non pasatzen argumentua 313 00:23:30,640 --> 00:23:35,770 = amaieran hasteko duzu, baina orratz balioa dira. 314 00:23:35,770 --> 00:23:47,310 Galdera izan zen ezin exekutatu kasua dugu, non amaiera orratz balio 315 00:23:47,310 --> 00:23:52,000 edo hasi = amaieran, modu egokian, hasi = amaiera 316 00:23:52,000 --> 00:23:59,480 eta ez duzu benetan balio hori bereziki hautatuta oraindik, 317 00:23:59,480 --> 00:24:03,910 ondoren hasi + amaiera / 2 balio bera izango du. 318 00:24:03,910 --> 00:24:07,890 Baina Jadanik itzuli faltsuak eta egia esan, inoiz ez dugu balioa egiaztatu. 319 00:24:07,890 --> 00:24:14,240 Beraz, gutxienez, lehen deialdian, tamaina 0 bada, ondoren faltsuak itzuli nahi dugu. 320 00:24:14,240 --> 00:24:17,710 Baina tamaina 1 bada, ondoren, Irteeran ez da berdina amaieran 321 00:24:17,710 --> 00:24:19,820 eta, gutxienez, egiaztatu dugu elementu bat. 322 00:24:19,820 --> 00:24:26,750 Baina une horretan amaituko hasi ahal izango dugu kasu batean non hasten + amaiera / 2 dela uste dut, 323 00:24:26,750 --> 00:24:31,190 Irteeran amaitzen Irteeran + amaiera / 2 bezala, 324 00:24:31,190 --> 00:24:35,350 baina inoiz ez dugu elementu hautatuta. 325 00:24:35,350 --> 00:24:44,740 >> Beraz, egiaztatu lehenengo badugu erdiko elementuaren balioa da bilatzen ari gara, 326 00:24:44,740 --> 00:24:47,110 ondoren, berehala itzuli ahal izango dugu egia. 327 00:24:47,110 --> 00:24:50,740 Bestela, berdinak dira, gero jarraitu puntua ez da 328 00:24:50,740 --> 00:24:58,440 ari gara, non bakarreko array elementu bat dugu kasu bat eguneratu du. 329 00:24:58,440 --> 00:25:01,110 Duen elementu bakarra ez bada bilatzen ari gara, 330 00:25:01,110 --> 00:25:03,530 ondoren, dena ez da zuzena. Bai. 331 00:25:03,530 --> 00:25:08,900 [Ikasleak] gauza da tamaina geroztik benetan array elementu kopurua baino handiagoa dela, 332 00:25:08,900 --> 00:25:13,070 dago dagoeneko desplazamendu bat >> Beraz, tamaina 333 00:25:13,070 --> 00:25:19,380 [Ikasleak] Esan array tamaina 0 bada, ondoren SearchHelp egingo benetan egiaztatu 0 haystack 334 00:25:19,380 --> 00:25:21,490 lehenengo deialdian. 335 00:25:21,490 --> 00:25:25,300 >> Yeah - array tamaina 0, 0 da, beraz. 336 00:25:25,300 --> 00:25:30,750 Hori beste gauza bat da ona izango da agian. Dezagun uste. 337 00:25:30,750 --> 00:25:40,120 Beraz, bada array 10 elementu zituen, eta erdiko bat egiaztatu dugu index 5, 338 00:25:40,120 --> 00:25:45,700 beraz, 5 ari gara egiaztapena, eta balioa txikiagoa da esan dezagun. 339 00:25:45,700 --> 00:25:50,720 Beraz, dena bota ari gara 5 aurrerantzean. 340 00:25:50,720 --> 00:25:54,030 Beraz, hasteko + amaiera / 2 gure berri amaiera izango da, 341 00:25:54,030 --> 00:25:57,450 yeah, beraz, beti array amaieran kanpo geratzeko. 342 00:25:57,450 --> 00:26:03,570 Kasu bat izan zen bakoiti edo bikoitia bada, orduan egiaztatu, dugu esango, 4, 343 00:26:03,570 --> 00:26:05,770 ari gara, baina oraindik urrun bota - 344 00:26:05,770 --> 00:26:13,500 Yeah Beraz, amaiera beti da array benetako amaiera haratago izango da. 345 00:26:13,500 --> 00:26:18,350 Elementu ari gara bideratua Beraz, amaieran beti dago horren ondoren bat izango da. 346 00:26:18,350 --> 00:26:24,270 Eta beraz, ez Irteeran inoiz berdinak amaieran, tamaina 0 array bat dugu. 347 00:26:24,270 --> 00:26:35,600 >> Pentsatzen ari nintzen beste gauza Irteeran eguneratzen ari gara hasteko behar + amaiera / 2, 348 00:26:35,600 --> 00:26:44,020 beraz, kasu honetan naiz I arazoak izatea, non hasten + amaiera / 2 349 00:26:44,020 --> 00:26:46,820 elementu ikusten ari garen. 350 00:26:46,820 --> 00:26:58,150 Demagun 10-array elementu hau izan genuen. Whatever. 351 00:26:58,150 --> 00:27:03,250 Beraz, hasteko + amaiera / 2 da hau bezalako zerbait izan behar duela, 352 00:27:03,250 --> 00:27:07,060 eta hori bada, ez da balioa, esan eguneratu nahi dugu. 353 00:27:07,060 --> 00:27:10,060 Balioa handiagoa da, beraz, array zati honetan begiratu nahi dugu. 354 00:27:10,060 --> 00:27:15,910 Beraz, nola Irteeran eguneratzen ari gara, hasiera ari gara eguneratzen orain elementu hau. 355 00:27:15,910 --> 00:27:23,790 Baina hori, oraindik, lan egiteko, edo, gutxienez, hasieran egin dezakezu + amaiera / 2 + 1. 356 00:27:23,790 --> 00:27:27,850 [Ikasleak] ez duzu hasteko + amaiera [inaudible] >> Bai. 357 00:27:27,850 --> 00:27:33,240 Ditugu dagoeneko hautatuta elementu hau ezagutu eta ez da bat bilatzen ari gara. 358 00:27:33,240 --> 00:27:36,800 Beraz, ez dugu behar elementu honen Irteeran eguneratzeko. 359 00:27:36,800 --> 00:27:39,560 Besterik ez dugu saltatzeko eta eguneratzeko hasteko elementu hau. 360 00:27:39,560 --> 00:27:46,060 Eta inoiz kasu bat dago, demagun, hori izan ziren amaieran, 361 00:27:46,060 --> 00:27:53,140 beraz, ondoren, hasteko izango litzateke, hasteko + amaiera / 2 hau izango litzateke, 362 00:27:53,140 --> 00:28:00,580 + bukaera - Bai, azkenean errekurtsio infinitua uste dut. 363 00:28:00,580 --> 00:28:12,690 Demagun tamaina 2 edo 1. Tamaina array bat besterik ez da array bat. Hau izango da lan uste dut. 364 00:28:12,690 --> 00:28:19,490 Beraz, gaur egun, hasieran elementu eta amaiera haratago 1. 365 00:28:19,490 --> 00:28:24,110 Beraz, elementu ari garela egiaztatzeko, hau da, 366 00:28:24,110 --> 00:28:29,400 eta orduan Irteeran eguneratu dugu, hasiera ari gara eguneratzen 0 + 1/2, 367 00:28:29,400 --> 00:28:33,160 den gurekin Irteeran elementu hori amaitzeko. 368 00:28:33,160 --> 00:28:36,210 >> Beraz, elementu bera eta gehiagoko berriz egiaztatzen ari gara. 369 00:28:36,210 --> 00:28:43,310 Beraz, kasu honetan, non dei errekurtsiboa behin eguneratu behar benetan zerbait da. 370 00:28:43,310 --> 00:28:48,370 Beraz, Irteeran + amaiera / 2 + 1, edo, bestela, egin behar dugu, kasu batean 371 00:28:48,370 --> 00:28:50,710 non ez ari gara benetan Irteeran eguneratzeko. 372 00:28:50,710 --> 00:28:53,820 Pertsona orok ikusten? 373 00:28:53,820 --> 00:28:56,310 Ongi da. 374 00:28:56,310 --> 00:29:03,860 Does Edozeinek irtenbide hau edo edozein iruzkin gehiago buruzko galderak? 375 00:29:05,220 --> 00:29:10,280 Ongi da. Does Edozeinek dute bat etorriko ahal dugun guztia begiratu irtenbidea? 376 00:29:17,400 --> 00:29:20,940 Ba egin dugu errekurtsiboki? 377 00:29:20,940 --> 00:29:25,950 Edo ere ireki hers bada, orduan gainidatzi dakizukeela Zure aurreko uste dut. 378 00:29:25,950 --> 00:29:28,810 Ez du automatikoki gorde da? Ez naiz positiboa. 379 00:29:35,090 --> 00:29:39,130 Does Edozeinek dute etorriko? 380 00:29:39,130 --> 00:29:42,430 Bidez gara elkarrekin ez bada. 381 00:29:46,080 --> 00:29:48,100 Ideia hori bera izango da. 382 00:30:00,260 --> 00:30:02,830 Etorriko konponbidea. 383 00:30:02,830 --> 00:30:07,140 Ideia bera, funtsean, egin nahi zaitugu 384 00:30:07,140 --> 00:30:16,530 array amaiera pista eta array Irteeran berria non gorde nahi dugu 385 00:30:16,530 --> 00:30:18,510 eta hori egin eta gehiagoko baino gehiago. 386 00:30:18,510 --> 00:30:22,430 Eta zer pista ari gara inoiz gurutzatzen hasiera eta amaiera gisa mantenduz gero, 387 00:30:22,430 --> 00:30:29,020 orduan ez genuen aurkitu eta itzuli faltsua ahal izango dugu. 388 00:30:29,020 --> 00:30:37,540 Beraz, zer egin dut? Edonork edo iradokizunak kodea me tira? 389 00:30:42,190 --> 00:30:47,450 [Ikasleak], berriz, begizta bat. >> Bai. 390 00:30:47,450 --> 00:30:49,450 Begizta bat egin nahi duzu. 391 00:30:49,450 --> 00:30:51,830 >> Ba kodea baduzu tira sortu nuen, edo zer ziren iradokitzen duzu? 392 00:30:51,830 --> 00:30:56,340 [Ikasleak] Baietz uste dut. >> Guztiak eskubidea. Horrek gauzak errazagoa. Zein da zure izena? 393 00:30:56,340 --> 00:30:57,890 [Ikasleen] Lucas. 394 00:31:00,140 --> 00:31:04,190 Berrikusketa, ordua: 1. Ongi da. 395 00:31:04,190 --> 00:31:13,200 Behe hasi aurretik deitu genuen. 396 00:31:13,200 --> 00:31:17,080 Up ez da nahiko zer amaiera deitu dugu aurretik. 397 00:31:17,080 --> 00:31:22,750 Egia esan, amaiera da orain array barruan. Elementu bat da, kontuan hartu behar dugu. 398 00:31:22,750 --> 00:31:26,890 Beraz, baxua 0 da, array-tamaina - 1, 399 00:31:26,890 --> 00:31:34,780 eta, gaur egun, ari gara begizta eta egiaztatzen ari gara 400 00:31:34,780 --> 00:31:37,340 Dezakezu oinez uste dut. 401 00:31:37,340 --> 00:31:41,420 Zein izan da zure pentsamendu honen bidez? Walk gurekin zure kodea bitartez. 402 00:31:41,420 --> 00:31:49,940 [Ikasleak] Sure. Erdi-erdian balio haystack behatu eta konparatu orratza. 403 00:31:49,940 --> 00:31:58,520 Oh, egia esan, atzeraka izan behar du - Beraz, ez da zure orratz baino handiagoa bada, eta, ondoren, nahi duzu. 404 00:31:58,520 --> 00:32:05,180 Urruntzen eskuineko erdia bota nahi ari zara, eta, beraz, bai, horrela izan behar du. 405 00:32:05,180 --> 00:32:08,830 [Bowden] Beraz, hau txikiagoa izan behar da? Da zer esan? >> [Ikasleak] Bai. 406 00:32:08,830 --> 00:32:10,390 [Bowden] Larreina. Gutxiago. 407 00:32:10,390 --> 00:32:15,700 Beraz, bada zer bilatzen ari gara, zer nahi dugun baino txikiagoa da, 408 00:32:15,700 --> 00:32:19,410 ondoren, yeah, kanpoan ezker erdian bota nahi dugu, 409 00:32:19,410 --> 00:32:22,210 horrek esan nahi du, guztia kontuan hartuta ari gara eguneratzen ari gara 410 00:32:22,210 --> 00:32:26,610 array eskubidea baxua mugituz. 411 00:32:26,610 --> 00:32:30,130 Itxura ona. 412 00:32:30,130 --> 00:32:34,550 Nik uste dut gai berean, aurreko batean esan du, 413 00:32:34,550 --> 00:32:49,760 non baxua 0 bada, eta sortu da 1, eta gero baxua + / 2 da berriro gauza bera egingo du. 414 00:32:49,760 --> 00:32:53,860 >> Eta nahiz eta hori ez da kasua, oraindik da eraginkorragoa, gutxienez 415 00:32:53,860 --> 00:32:57,630 bakarrik bota elementu begiratu besterik ez dugu da oker badakigu. 416 00:32:57,630 --> 00:33:03,240 Beraz, baxua + up / 2 + 1 - >> [ikasleak] Hori beste modu batera izan behar du. 417 00:33:03,240 --> 00:33:05,900 [Bowden] Edo hau izan behar du - 1 eta beste bat + 1 izan behar du. 418 00:33:05,900 --> 00:33:09,580 [Ikasleak] Eta bikoitza izan beharko luke berdin ikurra. >> [Bowden] Bai. 419 00:33:09,580 --> 00:33:11,340 [Ikasleen] Bai. 420 00:33:14,540 --> 00:33:15,910 Ongi da. 421 00:33:15,910 --> 00:33:21,280 Eta, azkenik, gaur egun dugun + 1 hau - 1 gauza 422 00:33:21,280 --> 00:33:31,520 da, agian ez da baxua amaitzeko balio bat sortu baino handiagoa da inoiz posible al da? 423 00:33:35,710 --> 00:33:40,320 Nik uste dut, posible al da bide bakarra hori gerta daiteke? >> [Ikasleak] ez dakit. 424 00:33:40,320 --> 00:33:45,220 Baina lortzen trunkatuta bada, eta, ondoren, lortzen minus 1 eta gero - >> Bai. 425 00:33:45,220 --> 00:33:47,480 [Ikasleak] litzateke ziurrenik get messed up. 426 00:33:49,700 --> 00:33:53,940 Nik uste dut ona izango bakarra izan beharko luke 427 00:33:53,940 --> 00:33:58,800 amaituko txikiagoa izan berdinak izan zuten, uste dut. 428 00:33:58,800 --> 00:34:03,070 Baina ez dira berdinak izanez gero, orduan ez genuke egin bitartean loop hasteko 429 00:34:03,070 --> 00:34:06,670 eta itzuli besterik ez dugu balio. Onak ditugu, gaur egun uste dut. 430 00:34:06,670 --> 00:34:11,530 Ohartu, nahiz eta arazo hau ez da gehiago recursive, 431 00:34:11,530 --> 00:34:17,400 ideia mota bera aplikatzen, non ikusi ahal izango dugu nola erraz erabaki bera 432 00:34:17,400 --> 00:34:23,659 Izan ere, ari gara indizeak eguneratzeko eta gehiagoko baino gehiago berriro irtenbide recursive 433 00:34:23,659 --> 00:34:29,960 arazo txikiagoak eta txikiagoak egiten ari gara, array azpimultzo bat ari gara bideratua. 434 00:34:29,960 --> 00:34:40,860 [Ikasleak] baxua 0 bada, eta sortu da 1, bai lukete 0 + 1/2, 0 joan da, 435 00:34:40,860 --> 00:34:44,429 eta, gero, + 1 bat litzateke, izango litzateke 1. 436 00:34:47,000 --> 00:34:50,870 [Ikasleak] Non egiaztatzen dugu berdintasuna? 437 00:34:50,870 --> 00:34:55,100 Atsegin dut erdiko bat benetan orratz bada? 438 00:34:55,100 --> 00:34:58,590 Ez ari gara gaur egun egiten? Oh! 439 00:35:00,610 --> 00:35:02,460 It's bada 440 00:35:05,340 --> 00:35:13,740 Bai. Ezin dugu egin proba behera hemen demagun lehen erdian delako 441 00:35:13,740 --> 00:35:16,430 [Ikasleak] benetan da nahi ez bota urruntzen doazen. 442 00:35:16,430 --> 00:35:20,220 Beraz, bota duzu urruntzen bada koadernatuta, lehen edo dena delakoa ikusteko aukera izango duzu. 443 00:35:20,220 --> 00:35:23,350 Ah. Bai. >> [Ikasleak] Bai. 444 00:35:23,350 --> 00:35:29,650 Beraz, gaur egun, bota dugu urruntzen begiratu gaur egun dugu, 445 00:35:29,650 --> 00:35:33,260 Horrek esan nahi du ere izan behar dugu 446 00:35:33,260 --> 00:35:44,810 (haystack [(baxua) / 2 + up] == orratz) bada, gero itzultzeko egia ahal izango dugu. 447 00:35:44,810 --> 00:35:52,070 Eta jarri ala ez dut bestela, edo, besterik gabe, bada, literalki gauza bera esan nahi du 448 00:35:52,070 --> 00:35:57,110 hau itzuli lukeelako egia. 449 00:35:57,110 --> 00:36:01,450 Beraz, jarri bestela dut, bada, baina ez du axola. 450 00:36:01,450 --> 00:36:10,440 >> Beraz, bestela, bestela, eta hau ez dut gauza komun bat da 451 00:36:10,440 --> 00:36:14,340 nahiz eta kasu non dena ona da hemen da, 452 00:36:14,340 --> 00:36:22,780 baxua inoiz ez bezala sortu baino handiagoa da, eta ez da hori egia den ala ez buruzko arrazoibidea merezi. 453 00:36:22,780 --> 00:36:28,010 Beraz, baita esan dezakezu baxua baino txikiagoa edo berdina bitartean 454 00:36:28,010 --> 00:36:30,720 edo txikia baino txikiagoa da, berriz, 455 00:36:30,720 --> 00:36:35,300 dira inoiz berdinak edo baxua bada gertatzen pasatzeko, 456 00:36:35,300 --> 00:36:40,130 ondoren apurtu ahal izango dugu begizta hau. 457 00:36:41,410 --> 00:36:44,630 Galderak, kezkak, iruzkinak? 458 00:36:47,080 --> 00:36:49,270 Ongi da. Itxura ona. 459 00:36:49,270 --> 00:36:52,230 Orain ordenatu egin nahi dugu. 460 00:36:52,230 --> 00:37:04,030 Nire bigarren berrikuspena joanez gero, ikusiko dugu, zenbaki horiek berdinak 461 00:37:04,030 --> 00:37:07,550 baina gaur egun jada ez dira ordena ordenatuko. 462 00:37:07,550 --> 00:37:12,840 Eta sort ezartzeko n log n O algoritmoa erabiliz nahi dugu. 463 00:37:12,840 --> 00:37:17,240 Duen algoritmoa Beraz, ez dugu hemen ezartzeko behar dela uste duzu? >> [Ikasleak] Batu sort. 464 00:37:17,240 --> 00:37:23,810 [Bowden] Bai. Batu sort O (n log n) da eta, beraz, zer egin behar dugu. 465 00:37:23,810 --> 00:37:26,680 Eta arazoa nahiko antzekoa izango da, 466 00:37:26,680 --> 00:37:31,920 non erraz erabaki du bera recursive irtenbide bat. 467 00:37:31,920 --> 00:37:35,580 Era berean, zatoz gora etorriko irtenbide bat nahi badugu, 468 00:37:35,580 --> 00:37:42,540 baina errekurtsio errazagoa izango da hemen, eta errekurtsibitate egin behar dugu. 469 00:37:45,120 --> 00:37:49,530 Uste dut merge sort bidez lehen egingo dugu oinez, 470 00:37:49,530 --> 00:37:54,280 merge sort bideo eder bat da, nahiz eta dagoeneko. [Barreak] 471 00:37:54,280 --> 00:37:59,780 Beraz, batu sort daude, beraz, paper hau askoz dut galdu. 472 00:37:59,780 --> 00:38:02,080 Oh, ezker bakarra da. 473 00:38:02,080 --> 00:38:03,630 Beraz, batu. 474 00:38:08,190 --> 00:38:12,470 Oh, 1, 3, 5. 475 00:38:26,090 --> 00:38:27,440 Ongi da. 476 00:38:29,910 --> 00:38:33,460 Batu bi array hartzen. 477 00:38:33,460 --> 00:38:36,780 Banaka bi array horiek biak sailkatuko da. 478 00:38:36,780 --> 00:38:40,970 Beraz, array honetan, 1, 3, 5, ordenatuko da. Array honek, 0, 2, 4, ordenatuko da. 479 00:38:40,970 --> 00:38:46,710 Orain zer merge egin behar konbinatu array bakar bat bera ordenatuko da. 480 00:38:46,710 --> 00:38:57,130 Beraz, hori elementu horiek barruan tamaina 6 array nahi dugu 481 00:38:57,130 --> 00:38:59,390 ordena ordenatuko. 482 00:38:59,390 --> 00:39:03,390 >> Eta, beraz, abantaila hartu ahal izango dugu, hain zuzen, bi array horiek antolatuko dira 483 00:39:03,390 --> 00:39:06,800 Horretarako, denbora lineal 484 00:39:06,800 --> 00:39:13,510 denbora lineal esanahia array hau da tamaina x bada, eta hau da tamaina y 485 00:39:13,510 --> 00:39:20,970 ondoren, guztira algoritmoa O (x + y) izan behar du. Ongi da. 486 00:39:20,970 --> 00:39:23,150 Iradokizunak, beraz. 487 00:39:23,150 --> 00:39:26,030 [Ikasleak] Ezin izan da ezker dugu? 488 00:39:26,030 --> 00:39:30,150 Beraz, 0 jarriko duzu lehenengo eta behera ondoren, 1 eta, ondoren, hemen 2. 489 00:39:30,150 --> 00:39:33,320 Beraz, fitxa bat eskuinera mugitzen atsegin mota da. >> [Bowden] Bai. 490 00:39:33,320 --> 00:39:41,070 Array horietako bi besterik ez dugu ezkerreko elementu bada fokua. 491 00:39:41,070 --> 00:39:43,530 Array bi antolatuko dira denez, ezagutzen dugun 2 elementu horiek 492 00:39:43,530 --> 00:39:46,920 array bai elementu txikiena dira. 493 00:39:46,920 --> 00:39:53,500 Beraz, horrek esan nahi du 1 2 elementu horiek gure array batu elementu txikiena izan behar da. 494 00:39:53,500 --> 00:39:58,190 Beraz, zerbait gertatzen txikiena denbora eskuineko on bat da. 495 00:39:58,190 --> 00:40:02,580 Beraz, 0 hartuko dugu, sartu da ezker 0 1 baino gutxiago baita, 496 00:40:02,580 --> 00:40:08,210 beraz, 0 hartu, sartu gure jarrera lehen, eta, ondoren, hau eguneratu dugu 497 00:40:08,210 --> 00:40:12,070 lehen elementu ardatz. 498 00:40:12,070 --> 00:40:14,570 Eta orain errepikatu dugu. 499 00:40:14,570 --> 00:40:20,670 Beraz, gaur egun, 2 alderatu dugu eta 1. 1 txikiagoa da, beraz, 1 sartu dugu. 500 00:40:20,670 --> 00:40:25,300 Erakuslea hau eguneratu dugu guy hau seinalatu. 501 00:40:25,300 --> 00:40:33,160 Orain egiten dugu berriro, beraz, 2. Honek, eguneratu egingo dira horiek, 2, 3 alderatu. 502 00:40:33,160 --> 00:40:37,770 Eguneratzeak hau, ondoren, 4 eta 5. 503 00:40:37,770 --> 00:40:42,110 Beraz, merge. 504 00:40:42,110 --> 00:40:49,010 >> Nahiko argi dago denbora lineal besterik ez dugu elementu bakoitzaren zehar geroztik behin joan behar da. 505 00:40:49,010 --> 00:40:55,980 Eta hori merge sort egiten da hau ezartzeko urrats handiena da. 506 00:40:55,980 --> 00:40:59,330 Eta ez da zaila dela. 507 00:40:59,330 --> 00:41:15,020 Pare bat gauza kezkatu demagun 1, 2, 3, 4, 5, 6 ginen batuz. 508 00:41:15,020 --> 00:41:30,930 Kasu honetan amaituko dugu eszenatoki hori txikiagoa izango da, 509 00:41:30,930 --> 00:41:36,160 ondoren erakuslea hau eguneratu dugu, hau da, txikiagoa izan behar du, eguneratu, 510 00:41:36,160 --> 00:41:41,280 ko hau txikiagoa da, eta gaur egun ezagutzen duzu 511 00:41:41,280 --> 00:41:44,220 denean, benetan duzun agortu elementuen alderatu. 512 00:41:44,220 --> 00:41:49,400 Array hau guztia erabiltzen dugun geroztik, 513 00:41:49,400 --> 00:41:55,190 array honetan dena da orain, hemen sartu. 514 00:41:55,190 --> 00:42:02,040 Beraz, bada, non gure array bat da, guztiz bateratu da dagoeneko puntu sartu dugu inoiz exekutatu, 515 00:42:02,040 --> 00:42:06,510 ondoren, hartu besterik ez dugu beste array elementu guztiak, eta horiek sartu array amaiera. 516 00:42:06,510 --> 00:42:13,630 Beraz, ezin dugu sartu 4, 5, 6. Ongi da. 517 00:42:13,630 --> 00:42:18,070 Hori da gauza bat ikustea da. 518 00:42:22,080 --> 00:42:26,120 Urratsa 1 izan behar ezartzea. 519 00:42:26,120 --> 00:42:32,600 Batu ordenatzeko ondoren horretan oinarrituta, 2 urrats, silly urrats 2. 520 00:42:38,800 --> 00:42:42,090 Dezagun array hau. 521 00:42:57,920 --> 00:43:05,680 Beraz, batu, ordenatu, 1. Pausoan da errekurtsiboki apurtu array halves sartu. 522 00:43:05,680 --> 00:43:09,350 Beraz, zatitu array halves sartu. 523 00:43:09,350 --> 00:43:22,920 Orain 4, 15, 16, 50 eta 8, 23, 42, 108. 524 00:43:22,920 --> 00:43:25,800 Eta gaur egun egiten dugu berriro, eta horiek zatitu dugu halves sartu. 525 00:43:25,800 --> 00:43:27,530 Besterik ez dut egin du alde honetan. 526 00:43:27,530 --> 00:43:34,790 4, 15 eta 16an, beraz, 50. 527 00:43:34,790 --> 00:43:37,440 Gauza bera egin nahi dugu hemen. 528 00:43:37,440 --> 00:43:40,340 Eta orain, zatitu dugu halves berriro. 529 00:43:40,340 --> 00:43:51,080 Eta 4, 15, 16, 50 ditugu. 530 00:43:51,080 --> 00:43:53,170 Beraz, da gure oinarria kasua. 531 00:43:53,170 --> 00:44:00,540 Array tamaina 1 dira ondoren, eta, ondoren gelditu splitting batera halves sartu. 532 00:44:00,540 --> 00:44:03,190 >> Orain zer egiten dugu? 533 00:44:03,190 --> 00:44:15,730 Amaituko dugu hau, halaber, 8, 23, 42, eta 108 sartu deskonposatzen. 534 00:44:15,730 --> 00:44:24,000 Beraz, puntu honetan, gaur egun dugun Oraindik, gaur egun urratsa merge sort bi bikote besterik ez dago batuz zerrendak. 535 00:44:24,000 --> 00:44:27,610 Beraz, horiek batzea nahi dugu. Deitu besterik ez dugu batu. 536 00:44:27,610 --> 00:44:31,410 Merge horiek itzuli egingo ordena ordenatuko ezagutzen dugu. 537 00:44:31,410 --> 00:44:33,920 4, 15. 538 00:44:33,920 --> 00:44:41,440 Orain, horiek batzea nahi dugu, eta hori itzuli egingo ordena ordenatuko dituzten, 539 00:44:41,440 --> 00:44:44,160 16, 50. 540 00:44:44,160 --> 00:44:57,380 Horiek batu ditugu - ezin dut idatzi - 8, 23 eta 42, 108. 541 00:44:57,380 --> 00:45:02,890 Beraz, batu bikote dugu behin. 542 00:45:02,890 --> 00:45:05,140 Orain batzea besterik ez dugu berriro. 543 00:45:05,140 --> 00:45:10,130 Iragarki zerrendak horietako bakoitza ordenatuko berez, 544 00:45:10,130 --> 00:45:15,220 eta, ondoren, besterik gabe batu zerrenda horiek tamaina 4 zerrenda hori horrela antolatu 545 00:45:15,220 --> 00:45:19,990 eta batu bi zerrenda horiek tamaina 4 zerrenda hori ordenatuko lortzeko. 546 00:45:19,990 --> 00:45:25,710 Eta, azkenik, tamaina 4 zerrendak bi horiek batu ahal izango dugu tamaina 8 zerrenda hori ordenatuko lortzeko. 547 00:45:25,710 --> 00:45:34,030 Beraz, hau da, oro har, n log n ikusteko, ikusi dugu dagoeneko merge dela lineala, 548 00:45:34,030 --> 00:45:40,390 beraz, horiek batuz ari gara, aurre merge kostu orokorra 549 00:45:40,390 --> 00:45:43,410 Zerrenda bi horien besterik ez da 2 delako 550 00:45:43,410 --> 00:45:49,610 Edo ongi, n O da, baina n hemen 2 elementu hauek besterik ez da, beraz, 2 da. 551 00:45:49,610 --> 00:45:52,850 Eta horiek 2 2 izango da eta horiek 2 2 izango da eta horiek 2 2 izango da, 552 00:45:52,850 --> 00:45:58,820 beraz, idatzi egin behar dugun guztietan, amaituko dugu n egiten dute. 553 00:45:58,820 --> 00:46:03,210 2 Like + 2 + 2 + 2 8 da, hau da, n, 554 00:46:03,210 --> 00:46:08,060 beraz, multzo honetan konbinatzearen kostua n dago. 555 00:46:08,060 --> 00:46:10,810 Eta gero, gauza bera hemen. 556 00:46:10,810 --> 00:46:16,980 Horiek 2 batu dugu eta, ondoren, horiek 2, eta banan-banan merge hau lau eragiketa egingo da, 557 00:46:16,980 --> 00:46:23,610 merge hau lau eragiketa egingo da, baina berriro ere, horien guztien artean, 558 00:46:23,610 --> 00:46:29,030 amaituko dugu n batuz guztira gauzak, eta, beraz, urrats hau n hartzen du. 559 00:46:29,030 --> 00:46:33,670 Hartzen du, eta, beraz, maila bakoitzean n ari fusionatuko elementuak. 560 00:46:33,670 --> 00:46:36,110 >> Eta zenbat maila daude? 561 00:46:36,110 --> 00:46:40,160 Maila bakoitzean, gure array tamaina 2 hazi da. 562 00:46:40,160 --> 00:46:44,590 Hemen, gure array tamaina 1 dira, hemen Oraindik tamaina 2 dira, hemen Oraindik tamaina 4 dute, 563 00:46:44,590 --> 00:46:46,470 eta, azkenik, tamaina 8 dute. 564 00:46:46,470 --> 00:46:56,450 Beraz, geroztik bikoiztu egin da, ez dago log n maila horietan guztira izango dira. 565 00:46:56,450 --> 00:47:02,090 Beraz, log n mailak, banakako maila bakoitzean hartzen n guztira eragiketak, 566 00:47:02,090 --> 00:47:05,720 n log n algoritmoa lortuko dugu. 567 00:47:05,720 --> 00:47:07,790 Zalantzak dituzu? 568 00:47:08,940 --> 00:47:13,320 Dute jendea jada hau ezartzeko aurrera egin? 569 00:47:13,320 --> 00:47:18,260 Dagoeneko egoera batean edonork non besterik ez dut tira bere kodea da? 570 00:47:20,320 --> 00:47:22,260 Minutu bat eman ahal izango dut. 571 00:47:24,770 --> 00:47:27,470 Hau da, luzeagoa izango da. 572 00:47:27,470 --> 00:47:28,730 Gomendatzen dut marka ditzakezu 573 00:47:28,730 --> 00:47:30,510 Ez daukazu errekurtsio egin merge 574 00:47:30,510 --> 00:47:33,750 merge for errekurtsio direlako, neurri ezberdinetako sorta bat gainditu behar izan duzu. 575 00:47:33,750 --> 00:47:37,150 , Egin dezakezu, baina izorratu egiten da. 576 00:47:37,150 --> 00:47:43,720 Baina sort bera errekurtsio nahiko erraza da. 577 00:47:43,720 --> 00:47:49,190 Literalki, besterik ez duzu deitu sort erdia ezkerreko, eskuineko erdia sort. Ongi da. 578 00:47:51,770 --> 00:47:54,860 Edonork ezer, tira sortu dut, ezin dute? 579 00:47:54,860 --> 00:47:57,540 Edo, bestela, minutu bat eman dut. 580 00:47:58,210 --> 00:47:59,900 Ongi da. 581 00:47:59,900 --> 00:48:02,970 Edonork zerbait lan egin ahal izango dugu? 582 00:48:05,450 --> 00:48:09,680 Edo, bestela, besterik ez dugu honekin lan egin eta gero, hortik zabaltzeko. 583 00:48:09,680 --> 00:48:14,050 >> Edonork hori baino gehiago izan dut tira daiteke? 584 00:48:14,050 --> 00:48:17,770 [Ikasleen] Bai. Tira dezakezu nirea. >> Guztiak eskubidea. 585 00:48:17,770 --> 00:48:19,730 Bai! 586 00:48:22,170 --> 00:48:25,280 [Ikasleak] Baziren baldintzak asko. >> Oh, tiro. Can you 587 00:48:25,280 --> 00:48:28,110 [Ikasleak] gorde behar dut. >> Bai. 588 00:48:32,420 --> 00:48:35,730 Beraz, egin merge bereizita genuen. 589 00:48:35,730 --> 00:48:38,570 Oh, baina ez da txarra dela. 590 00:48:39,790 --> 00:48:41,650 Ongi da. 591 00:48:41,650 --> 00:48:47,080 Beraz, sort bera besterik ez da mergeSortHelp deituz. 592 00:48:47,080 --> 00:48:49,530 Gurekin Azaldu zer mergeSortHelp du. 593 00:48:49,530 --> 00:48:55,700 [Ikasleen] MergeSortHelp pretty askoz du nagusiak bi urrats, 594 00:48:55,700 --> 00:49:01,270 zein da array erdia bakoitzean ordenatzeko eta, ondoren, biak batu. 595 00:49:04,960 --> 00:49:08,050 [Bowden] Ongi da, eta, beraz, ematen dit bigarren bat. 596 00:49:10,850 --> 00:49:13,210 Hau uste dut - >> [ikasleak] behar dut 597 00:49:17,100 --> 00:49:19,400 Bai. Falta zerbait dut. 598 00:49:19,400 --> 00:49:23,100 Merge, array berri bat sortu behar dut konturatzen naiz 599 00:49:23,100 --> 00:49:26,530 izan dut ez delako egin dute. >> Bai. Ezin duzu. Zuzendu. 600 00:49:26,530 --> 00:49:28,170 [Ikasleak] Beraz, array berri bat sortu dut. 601 00:49:28,170 --> 00:49:31,510 Ahaztua dut berriro aldatu batu amaieran. 602 00:49:31,510 --> 00:49:34,490 Ongi da. Array berri bat behar dugu. 603 00:49:34,490 --> 00:49:41,000 Merge sailkatu, hau da, ia-ia beti egia. 604 00:49:41,000 --> 00:49:44,340 Algoritmoa hobea time-wise kostua Taldea 605 00:49:44,340 --> 00:49:47,310 da ia beti pixka bat memoria gehiago erabili beharrik. 606 00:49:47,310 --> 00:49:51,570 Beraz, ez du axola nola egin nahi duzu batu, ordenatu, 607 00:49:51,570 --> 00:49:54,780 ezinbestean, aparteko memoria batzuk erabili behar zenuke. 608 00:49:54,780 --> 00:49:58,240 Berak sortu berri array bat. 609 00:49:58,240 --> 00:50:03,400 Eta gero, amaieran array berri bat kopiatu array jatorrizko besterik ez dugu behar diozu. 610 00:50:03,400 --> 00:50:04,830 [Ikasleak] Baietz uste dut, bai. 611 00:50:04,830 --> 00:50:08,210 Ez dakit hori erreferentzia edo dena delakoa kontatuta dagokionez - 612 00:50:08,210 --> 00:50:11,650 Bai, lan egingo da. >> [Ikasleak] Larreina. 613 00:50:20,620 --> 00:50:24,480 Ba hau abiarazi saiatu duzu? >> [Ikasleak] Ez, oraindik ez. >> Ados. 614 00:50:24,480 --> 00:50:28,880 Saiatu exekutatzen ari da, eta, ondoren, horri buruz hitz egin dut, segundo bat. 615 00:50:28,880 --> 00:50:35,200 [Ikasleak] funtzioa prototipoak eta dena izan behar dut, hala ere, ezta? 616 00:50:37,640 --> 00:50:40,840 Funtzioa prototipoak. Oh, esan nahi duzun bezala - Bai. 617 00:50:40,840 --> 00:50:43,040 Ordena da mergeSortHelp deituz. 618 00:50:43,040 --> 00:50:47,390 >> Beraz, ordena sort mergeSortHelp deitu mergeSortHelp behar bai dira definitzen 619 00:50:47,390 --> 00:50:56,370 sort aurretik edo besterik ez dugu behar prototipoa. Just kopiatu eta itsatsi dela. 620 00:50:56,370 --> 00:50:59,490 Eta, era berean, mergeSortHelp da batu deituz, 621 00:50:59,490 --> 00:51:03,830 baina merge ez du oraindik zehaztu dira, eta, beraz, besterik gabe, ezin dugu utzi mergeSortHelp jakin 622 00:51:03,830 --> 00:51:08,700 horrek zer batzea da itxura, eta hori da hori. 623 00:51:09,950 --> 00:51:15,730 MergeSortHelp Beraz. 624 00:51:22,770 --> 00:51:32,660 Arazo bat izan behar dugu hemen, non oinarria inolaz ere ez dugu. 625 00:51:32,660 --> 00:51:38,110 MergeSortHelp errekurtsiboa da, beraz, funtzioa errekurtsiboa edozein 626 00:51:38,110 --> 00:51:42,610 base kasuan nolabaiteko behar denean gelditzeko errekurtsiboki bera deituz jakin behar da. 627 00:51:42,610 --> 00:51:45,590 Zer dira gure oinarria kasuan gertatzen da hemen? Bai. 628 00:51:45,590 --> 00:51:49,110 [Ikasleen] tamaina 1 bada? >> [Bowden] Bai. 629 00:51:49,110 --> 00:51:56,220 Horrela ikusi genuen bertan, splitting array gelditu 630 00:51:56,220 --> 00:52:01,850 tamaina 1, array, ezinbestean antolatuko dira bere buruari behin lortu dugu. 631 00:52:01,850 --> 00:52:09,530 Beraz, tamaina berdinen 1 bada, array dagoeneko horrela antolatu ezagutzen dugu, 632 00:52:09,530 --> 00:52:12,970 beraz, bakarrik itzuli ahal izango dugu. 633 00:52:12,970 --> 00:52:16,880 >> Iragarki hori void, beraz, ez dugu ezer bereziki itzultzeko, itzuli besterik ez dugu. 634 00:52:16,880 --> 00:52:19,580 Ongi da. Beraz, gure kasuan. 635 00:52:19,580 --> 00:52:27,440 Izan ere gure kasuan gertatuko dugu batuz tamaina 0 array bat asmatzen dut, 636 00:52:27,440 --> 00:52:30,030 uneren batean gelditu nahi dugu, ziurrenik, 637 00:52:30,030 --> 00:52:33,610 beraz, besterik gabe, esan dezakegu tamaina baino gutxiago 2 edo gutxiago 1 edo berdin 638 00:52:33,610 --> 00:52:37,150 dela, beraz, hau izango da array edozein lan egiteko. 639 00:52:37,150 --> 00:52:38,870 Ongi da. 640 00:52:38,870 --> 00:52:42,740 Beraz, gure kasuan. 641 00:52:42,740 --> 00:52:45,950 Orain gurekin oinez merge bidez nahi al duzu? 642 00:52:45,950 --> 00:52:49,140 Zer Kasu horiek guztiak esan nahi du? 643 00:52:49,140 --> 00:52:54,480 Hemen, bakarrik ari gara ideia bera egiten, - 644 00:52:56,970 --> 00:53:02,470 [Ikasleak] pasatuz tamaina mergeSortHelp deiak behar dut. 645 00:53:02,470 --> 00:53:10,080 Tamaina gehitu dut lehen osagarri gisa, eta ez da, tamaina / 2 bezala. 646 00:53:10,080 --> 00:53:16,210 [Bowden] Oh, tamaina / 2, size / 2. >> [Ikasleen] Bai, eta, gainera, funtzio gainetik ere. 647 00:53:16,210 --> 00:53:21,320 [Bowden] Hona hemen? >> [Ikasleak] Just tamaina. >> [Bowden] Oh. Tamaina, tamaina? >> [Ikasleak] Bai. 648 00:53:21,320 --> 00:53:23,010 [Bowden] Larreina. 649 00:53:23,010 --> 00:53:26,580 Uste bigarren bat me. 650 00:53:26,580 --> 00:53:28,780 Exekutatu arazo bat dugu? 651 00:53:28,780 --> 00:53:33,690 Beti ari gara ezker tratatzeko 0. >> [Ikasleen] N º 652 00:53:33,690 --> 00:53:36,340 Hori gertatzen da ere. Sentitzen dugu. Irteeran izan behar da. Bai. 653 00:53:36,340 --> 00:53:39,230 [Bowden] Larreina. Hobea gustatzen zait. 654 00:53:39,230 --> 00:53:43,880 Eta amaiera. Ongi da. 655 00:53:43,880 --> 00:53:47,200 Beraz, gaur egun ez gurekin oinez merge bidez nahi al duzu? >> [Ikasleak] Larreina. 656 00:53:47,200 --> 00:53:52,150 Besterik ez dut dudan array berri honen bidez sortu oinez. 657 00:53:52,150 --> 00:53:57,420 Bere tamaina array zati tamaina nahi dugun ordenatuko da 658 00:53:57,420 --> 00:54:03,460 eta elementu array urrats berri jarri behar dut bila. 659 00:54:03,460 --> 00:54:10,140 Beraz, horretarako, lehenik eta behin array ezkerreko erdia gehiago elementu jarraitzen dut egiaztapena 660 00:54:10,140 --> 00:54:14,260 eta ez bada, eta gero behera joan behar da, bestela, egoera hori, besterik ez dio 661 00:54:14,260 --> 00:54:20,180 ados, eskuineko array behar da, eta hori jarriko dugu uneko indizea newArray. 662 00:54:20,180 --> 00:54:27,620 >> Eta gero, bestela, array-eskuinaldean ere bada amaitu dut egiaztapena 663 00:54:27,620 --> 00:54:30,630 Kasu horretan, ezker besterik ez dut jarri. 664 00:54:30,630 --> 00:54:34,180 Agian ez da beharrezkoa izango. Ez nago ziur. 665 00:54:34,180 --> 00:54:40,970 Baina, hala ere, beste bi kontrol bi zein ezkerreko edo eskuineko txikiagoak dira. 666 00:54:40,970 --> 00:54:49,770 Eta, gainera, kasu bakoitzean, edozein biltegian I Kontatzailea dut incrementing. 667 00:54:49,770 --> 00:54:52,040 [Bowden] Larreina. 668 00:54:52,040 --> 00:54:53,840 Hori itxura ona. 669 00:54:53,840 --> 00:54:58,800 Does Edozeinek iruzkinak edo kezka edo galdera? 670 00:55:00,660 --> 00:55:07,720 Beraz, itxura edo bost bezala lau kasu besterik ez izatea gauza ekarri dugun - 671 00:55:07,720 --> 00:55:13,100 baina ea ezker array agortu du gauzak batu behar dugu kontuan hartu behar dugu, 672 00:55:13,100 --> 00:55:16,390 array eskubidea duen ala ez agortu du gauzak batu behar dugu 673 00:55:16,390 --> 00:55:18,400 Ezer ez dut seinalatuz. 674 00:55:18,400 --> 00:55:21,730 Beraz, ezker array ez du agortu gauza edo eskubidea array agortu du gauza. 675 00:55:21,730 --> 00:55:24,320 Dutenek bi kasu. 676 00:55:24,320 --> 00:55:30,920 Ezkerreko gauza da eskuineko gauza baino gutxiago edo kasuan trivial ere egin beharko dugu. 677 00:55:30,920 --> 00:55:33,910 Ondoren, ezkerreko gauza aukeratu nahi dugu. 678 00:55:33,910 --> 00:55:37,630 Horiek dira kasu guztietan. 679 00:55:37,630 --> 00:55:40,990 Beraz, hau da eskubidea, eta, beraz, hori da, beraz. 680 00:55:40,990 --> 00:55:46,760 Array utzi. 1, 2, 3. Ongi da. Beraz, bai, horiek dira lau gauza egin nahi dugu agian. 681 00:55:50,350 --> 00:55:54,510 Eta ez dugu bat etorriko irtenbide baino gehiago joan. 682 00:55:54,510 --> 00:55:55,980 Ez nuke gomendatuko 683 00:55:55,980 --> 00:56:03,070 Batu nolako funtzio bat da, bai ez buztana recursive adibide bat da, 684 00:56:03,070 --> 00:56:07,040 Ez da erraza da buztana recursive egiteko, 685 00:56:07,040 --> 00:56:13,450 baina, aldi berean, ez da oso erraza etorriko egiteko. 686 00:56:13,450 --> 00:56:16,910 Hau da, oso erraza da. 687 00:56:16,910 --> 00:56:19,170 Merge sort ezartzeko honek, 688 00:56:19,170 --> 00:56:22,140 batu, ez du axola zer egin nahi duzu, merge eraikitzeko duzu. 689 00:56:22,140 --> 00:56:29,170 >> Beraz, batu errekurtsiboki sort konbinazio gainean eraikitako hiru lerro hauek besterik ez da. 690 00:56:29,170 --> 00:56:34,700 Iteratively, gogaikarriak eta zailagoa pentsatu da. 691 00:56:34,700 --> 00:56:41,860 Baina ez dela buztana mergeSortHelp geroztik recursive - bera deiak - 692 00:56:41,860 --> 00:56:46,590 behar du, hala ere, gauzak egiteko dei errekurtsiboa honetan itzultzen ondoren. 693 00:56:46,590 --> 00:56:50,830 Beraz, pila fotograma honetan ere hau deituz ondoren existitzen jarraitu behar du. 694 00:56:50,830 --> 00:56:54,170 Eta orduan, hau deitu, pila-markoa existitzen jarraitu behar 695 00:56:54,170 --> 00:56:57,780 dei hori ere behar delako ondoren, oraindik batu. 696 00:56:57,780 --> 00:57:01,920 Eta nontrivial da buztan hau recursive egiteko. 697 00:57:04,070 --> 00:57:06,270 Zalantzak dituzu? 698 00:57:08,300 --> 00:57:09,860 Guztiak eskubidea. 699 00:57:09,860 --> 00:57:13,400 Beraz, atzera joan ordenatzeko - oh, bi gauza erakutsi nahi dut. Ongi da. 700 00:57:13,400 --> 00:57:17,840 Atzera eginez, ordenatu, azkar egin dugu. 701 00:57:17,840 --> 00:57:21,030 Edo bilaketa. Ordena? Ordena. Bai. 702 00:57:21,030 --> 00:57:22,730 Atzera eginez sort hasieratik. 703 00:57:22,730 --> 00:57:29,870 Algoritmo bat ordenatzen array algoritmoa erabiliz sortu nahi dugu 704 00:57:29,870 --> 00:57:33,660 n O. 705 00:57:33,660 --> 00:57:40,860 Beraz, nola da posible hau? Does Edozeinek edozein 706 00:57:40,860 --> 00:57:44,300 Hinted aurretik I - 707 00:57:44,300 --> 00:57:48,300 Gara, bada log n n n O hobetzeko, 708 00:57:48,300 --> 00:57:51,450 hobetu egin dugu gure algoritmoa time-wise, 709 00:57:51,450 --> 00:57:55,250 horrek esan nahi du zer egin nahi egin behar dugu? 710 00:57:55,250 --> 00:57:59,520 [Ikasleak] Space. >> Bai. Leku gehiago erabiltzen ari gara. 711 00:57:59,520 --> 00:58:04,490 Eta ez, besterik gabe, leku gehiago, esponentzialki leku gehiago da. 712 00:58:04,490 --> 00:58:14,320 Beraz, algoritmo-mota hori sasi zerbait, pseudo polynom dela uste dut 713 00:58:14,320 --> 00:58:18,980 pseudo - ezin dut gogoratzen. Pseudo zerbait. 714 00:58:18,980 --> 00:58:22,210 Baina behar dugu hainbeste espazioa erabili nahi dituelako da 715 00:58:22,210 --> 00:58:28,610 hori lor da, baina ez da errealista. 716 00:58:28,610 --> 00:58:31,220 >> Eta nola egin hori lortzeko? 717 00:58:31,220 --> 00:58:36,810 Hau lortu ahal izango dugu bermatzen badugu array bereziki edozein elementu 718 00:58:36,810 --> 00:58:39,600 azpitik dago, tamaina jakin bat. 719 00:58:42,070 --> 00:58:44,500 Hargatik, besterik gabe esan tamaina 200, 720 00:58:44,500 --> 00:58:48,130 array batean edozein elementu da, tamaina 200 baino gutxiago. 721 00:58:48,130 --> 00:58:51,080 Eta hori da, benetan, oso errealista da. 722 00:58:51,080 --> 00:58:58,660 Oso erraz egin dezakezu array bat ezagutzen duzun guztia 723 00:58:58,660 --> 00:59:00,570 zenbaki bat baino gutxiago izango da. 724 00:59:00,570 --> 00:59:07,400 Duzu bektore edo zerbait erabat masiboa 725 00:59:07,400 --> 00:59:11,810 baina dena da 0 eta 5 bitartean izango badakizu, 726 00:59:11,810 --> 00:59:14,790 ondoren, nabarmen Horretarako azkarragoa izan da. 727 00:59:14,790 --> 00:59:17,930 Eta elementu edozein doazen 5 da, 728 00:59:17,930 --> 00:59:21,980 doazen honetan, beraz, hau da, zenbat memoria erabiltzen ari zaren. 729 00:59:21,980 --> 00:59:26,300 Beraz, koadernatuta 200 da. 730 00:59:26,300 --> 00:59:32,960 Teorian, beti dago doazen zenbaki oso bat besterik ezin da 4 milioi, 731 00:59:32,960 --> 00:59:40,600 baina hori gero erabili beharko genuke espazio geroztik unrealistic 732 00:59:40,600 --> 00:59:44,400 4 milioi ordena. Beraz, unrealistic. 733 00:59:44,400 --> 00:59:47,060 Baina hemen gure doazen esan dugu 200. 734 00:59:47,060 --> 00:59:59,570 N O egiten trikimailu izeneko tamaina zenbatzen Bound beste array bat egin dugu. 735 00:59:59,570 --> 01:00:10,470 Beraz, benetan, hau lasterbide bat da, ez benetan ez dakit Clang ez bada. 736 01:00:11,150 --> 01:00:15,330 Baina, gutxienez GCC - I'm suposatuz Clang du ere 737 01:00:15,330 --> 01:00:18,180 hau, array osoa hasieratu 0 s izan. 738 01:00:18,180 --> 01:00:25,320 Beraz, ez dut nahi ez badu horretarako, eta, ondoren, banan-banan izan nuen egin for (int i = 0; 739 01:00:25,320 --> 01:00:31,500 i 01:00:35,260 Beraz, gaur egun dena da 0 hasieratu. 741 01:00:35,260 --> 01:00:39,570 Batetik bestera joateko baino gehiago dut nire array 742 01:00:39,570 --> 01:00:51,920 eta zer egiten ari naiz, bakoitzaren kopurua dut kontatuta - jaisten da hemen. 743 01:00:51,920 --> 01:00:55,480 4, 15, 16, 50, 8, 23, 42, 108 ditugu. 744 01:00:55,480 --> 01:01:00,010 Kontatuta naiz elementu horiek bakoitzaren agerraldi-kopurua da. 745 01:01:00,010 --> 01:01:03,470 Dezagun benetan gehitu pare bat gehiago hemen errepikatzen batzuekin batera. 746 01:01:03,470 --> 01:01:11,070 Balioa Beraz, hemen dugu, horren balioa array [i]. 747 01:01:11,070 --> 01:01:14,850 Beraz, val 4 edo 8 edo dena delakoa izan daiteke. 748 01:01:14,850 --> 01:01:18,870 Eta orain, zenbat balio duten ikusi dut dut kontatuta, 749 01:01:18,870 --> 01:01:21,230 zenbatzen da, beraz [val] + +; 750 01:01:21,230 --> 01:01:29,430 Hori egin ondoren, zenbatzen da 0001 bezalako zerbait bilatzeko. 751 01:01:29,430 --> 01:01:42,190 Egin dezagun zenbatzen [val] - Bound + 1. 752 01:01:42,190 --> 01:01:48,230 >> Orain besterik Izan ere, 0-tik hasten ari garela kontuan. 753 01:01:48,230 --> 01:01:50,850 Beraz, 200 bada gure gehien izango 754 01:01:50,850 --> 01:01:54,720 0 200 201 gauza da. 755 01:01:54,720 --> 01:02:01,540 Zenbatzen Beraz, 00001 bezala izango da begiratu bat dugu 4 delako. 756 01:02:01,540 --> 01:02:10,210 Ondoren, 0001 non 1 izan dugu Aldaketa 8an indizea izan dugu. 757 01:02:10,210 --> 01:02:14,560 Aldaketa 23an indizea 2 bat izango dugu. 758 01:02:14,560 --> 01:02:17,630 Aldaketa indizea 42 2 bat izango dugu. 759 01:02:17,630 --> 01:02:21,670 Beraz Aldaketa erabili ahal izango dugu. 760 01:02:34,270 --> 01:02:44,920 Beraz num_of_item = zenbatzen [i]. 761 01:02:44,920 --> 01:02:52,540 Eta hala bada num_of_item 2 da, eta horrek esan nahi du 2 txertatzeko kopurua i nahi dugu 762 01:02:52,540 --> 01:02:55,290 gure array horrela antolatu du. 763 01:02:55,290 --> 01:03:02,000 Beraz, segimendua egiteko, noraino dira array sartu behar dugu. 764 01:03:02,000 --> 01:03:05,470 Beraz, index = 0. 765 01:03:05,470 --> 01:03:09,910 Array - besterik ez dut idatzi. 766 01:03:16,660 --> 01:03:18,020 Condes - 767 01:03:19,990 --> 01:03:28,580 array [index + +] = i; 768 01:03:28,580 --> 01:03:32,490 Da zer esan nahi dut? Nik uste dut, hori da nahi dudana. 769 01:03:35,100 --> 01:03:38,290 Bai, hau itxura ona. Ongi da. 770 01:03:38,290 --> 01:03:43,050 Beraz, ez denek ulertzen zer da nire zenbatzen array helburua? 771 01:03:43,050 --> 01:03:48,140 , Zenbaki horiek bakoitzaren agerraldi kopurua da kontatuta. 772 01:03:48,140 --> 01:03:51,780 Ondoren, bit baino gehiago naiz hori zenbatzen array, 773 01:03:51,780 --> 01:03:57,190 eta zenbatzen array posizio Ith 774 01:03:57,190 --> 01:04:01,930 i da kopuru hori behar ordenatuko nire array agertzen da. 775 01:04:01,930 --> 01:04:06,840 Horregatik, 4 zenbatzen 1 izango 776 01:04:06,840 --> 01:04:11,840 eta 8 de zenbatzen 1 izango da, 23 zenbatzen 2 izango da. 777 01:04:11,840 --> 01:04:16,900 Beraz, nola horietako asko nire array ordenatuko txertatzeko nahi dut. 778 01:04:16,900 --> 01:04:19,200 Ondoren, egin dut. 779 01:04:19,200 --> 01:04:28,960 Num_of_item dut txertatu nire array ordenatuko sartu i. 780 01:04:28,960 --> 01:04:31,670 >> Zalantzak dituzu? 781 01:04:32,460 --> 01:04:43,100 Eta, beraz, berriro ere, denbora lineala ari gara geroztik honetan zehar behin errepikatzean, 782 01:04:43,100 --> 01:04:47,470 baina, aldi berean zenbaki hau gertatzen da lineala, 783 01:04:47,470 --> 01:04:50,730 eta, beraz, zein den zure doazen handia araberakoa da. 784 01:04:50,730 --> 01:04:53,290 200 doazen batekin, hori ez da txarra dela. 785 01:04:53,290 --> 01:04:58,330 Zure doazen 10.000 izan nahi baduzu, eta gero apur bat okerragoa, 786 01:04:58,330 --> 01:05:01,360 baina zure koadernatuta dago 4 milioi dolarrekoa izango, bada, guztiz unrealistic 787 01:05:01,360 --> 01:05:07,720 eta array hau tamaina 4 milioi, hau da, unrealistic izango dute. 788 01:05:07,720 --> 01:05:10,860 Beraz, hori. Zalantzak dituzu? 789 01:05:10,860 --> 01:05:13,270 [Inaudible ikaslearen erantzuna] >> Ados. 790 01:05:13,270 --> 01:05:15,710 Beste gauza konturatu nintzen joan ginen. 791 01:05:17,980 --> 01:05:23,720 Nik uste dut arazoa Lucas eta ziurrenik behin bakar bat ikusi dugu. 792 01:05:23,720 --> 01:05:26,330 Ahaztua dut erabat. 793 01:05:26,330 --> 01:05:31,040 Behar duzu nahi nuen gauza bakarra da indize bezalako gauzak aurre ari zaren, 794 01:05:31,040 --> 01:05:38,320 benetan inoiz ez ikusiko duzu noiz ari zaren idazteko loop, 795 01:05:38,320 --> 01:05:41,120 baina teknikoki, betiere indizeak hauekin ari zaren aurre, 796 01:05:41,120 --> 01:05:45,950 pretty askoz behar duzu beti. zeinurik gabeko osoko zenbakien aurre egiteko. 797 01:05:45,950 --> 01:05:53,850 Horren arrazoia denean,, zenbaki osoen sinatu ari zaren aurre, 798 01:05:53,850 --> 01:05:56,090 hala badagokio sinatu zenbaki osoen 2 eta gehitu zaituzte elkarrekin 799 01:05:56,090 --> 01:06:00,640 eta azkenean handiegia, eta gero azkenean zenbaki negatiboa. 800 01:06:00,640 --> 01:06:03,410 Beraz, zer da zenbaki oso gainezkatze bat. 801 01:06:03,410 --> 01:06:10,500 >> 2 milioi eta 1 milioi gehitu bada, amaitzeko I 1 negatiboa milioi. 802 01:06:10,500 --> 01:06:15,480 Hori da, zenbaki osoko ordenagailuak nola lan egiten. 803 01:06:15,480 --> 01:06:17,510 Erabiliz arazoa Beraz 804 01:06:17,510 --> 01:06:23,500 Hori da bada ongi baxua gertatzen da 2 milioi dolarrekoa izango, eta sortu gertatzen 1 milioi dolarrekoa izango, 805 01:06:23,500 --> 01:06:27,120 ondoren, hau da, negatiboa 1 milioi izango da eta ondoren, zatitzen dugu 2 806 01:06:27,120 --> 01:06:29,730 eta, azkenean, 500 negatiboa milioi. 807 01:06:29,730 --> 01:06:33,760 Beraz, hau arazo bat bakarrik gertatuko baduzu array baten bidez bilatzen da 808 01:06:33,760 --> 01:06:38,070 bilioika gauza. 809 01:06:38,070 --> 01:06:44,050 Baina baxua + sortu gainezkatzea gertatzen bada, ondoren, arazo bat. 810 01:06:44,050 --> 01:06:47,750 Eta, ondoren, ahalik eta azkarren egin ditugu unsigned 2 milioi milioi plus 1 3 milioi da. 811 01:06:47,750 --> 01:06:51,960 3 milioi 2 arabera banatzen da 1,5 milioi da. 812 01:06:51,960 --> 01:06:55,670 Beraz, ahalik eta azkarren unsigned Oraindik ere, dena ezin hobea da. 813 01:06:55,670 --> 01:06:59,900 Eta, beraz, hori ere arazo bat zure zaren idazten loops, 814 01:06:59,900 --> 01:07:03,940 eta, benetan, ez ziur aski, automatikoki. 815 01:07:09,130 --> 01:07:12,330 Benetan izango da besterik ez duzu Yell. 816 01:07:12,330 --> 01:07:21,610 Beraz, kopurua handiegia da zenbaki oso bat besterik ez da, baina zeinurik gabeko osoko zenbaki bat egokitzen litzateke, 817 01:07:21,610 --> 01:07:24,970 egingo du Yell, beraz, zergatik benetan ez da inoiz gai sartu exekutatu. 818 01:07:29,150 --> 01:07:34,820 Indizea ez da inoiz negatiboa izango dezakezu, 819 01:07:34,820 --> 01:07:39,220 eta, beraz, array bat baino gehiago ari zaren errepikatzean, 820 01:07:39,220 --> 01:07:43,970 ia beti dezakezu esan unsigned int i, baina ez duzu benetan izan. 821 01:07:43,970 --> 01:07:47,110 Things dira pretty askoz ere lan egiteko besterik ez baita. 822 01:07:48,740 --> 01:07:50,090 Ongi da. [Xuxurlatzen] Zer ordu da? 823 01:07:50,090 --> 01:07:54,020 Azken gauza erakutsi nahi nuen, eta besterik ez dut egin azkarrak benetan. 824 01:07:54,020 --> 01:08:03,190 Nola # dugu # zehaztu ahal izango dugu, beraz, 5 edo zerbait gisa definitzen MAX ezagutzen duzu? 825 01:08:03,190 --> 01:08:05,940 Dezagun ez MAX. # Define 200 gisa aritzeko. Horixe aurretik genuen. 826 01:08:05,940 --> 01:08:10,380 Hori konstante bat da, hau da, besterik gabe, kopiatu eta itsatsi definitzen 827 01:08:10,380 --> 01:08:13,010 lekuan Bound idatzi gertatuko dugu. 828 01:08:13,010 --> 01:08:18,189 >> Beraz, benetan ahal izango dugu # definitzen. 829 01:08:18,189 --> 01:08:21,170 Funtzio # zehaztu ahal izango dugu. 830 01:08:21,170 --> 01:08:23,410 Oraindik ez dute benetan funtzioak, baina dei horiek funtzio dugu. 831 01:08:23,410 --> 01:08:36,000 Adibide bat MAX (x, y) bezalako zerbait izango litzateke (?: X x 01:08:40,660 Beraz, hirutarra adibidez operadorea sintaxia get erabili behar da, 833 01:08:40,660 --> 01:08:49,029 baina ez da x y baino gutxiago? Itzuli y, x bestela itzultzeko. 834 01:08:49,029 --> 01:08:54,390 Beraz, ikusi hau funtzio bereizi bat egin dezakezu dezakezu, 835 01:08:54,390 --> 01:09:01,399 eta funtzioa boolearra MAX 2 argumentu bezala izan daiteke, itzultzeko. 836 01:09:01,399 --> 01:09:08,340 Direnak ohikoena ikusten dut atsegin dute hau egin da. Horietako makro deitzen dugu. 837 01:09:08,340 --> 01:09:11,790 Makro bat da. 838 01:09:11,790 --> 01:09:15,859 Hau besterik ez da sintaxia. 839 01:09:15,859 --> 01:09:18,740 Makro bat idatzi nahi duzuna egin dezakezu. 840 01:09:18,740 --> 01:09:22,649 Maiz ikusiko duzu makro, printfs eta stuff arazteko. 841 01:09:22,649 --> 01:09:29,410 Printf mota daude, beraz, berezia C konstanteak azpimarra bezalako LINE azpimarra 842 01:09:29,410 --> 01:09:31,710 2 azpimarrak LINE azpimarra 843 01:09:31,710 --> 01:09:37,550 eta han ere 2 azpimarrak Bil uste dut. Hori izan daiteke. Horrelako zerbait. 844 01:09:37,550 --> 01:09:40,880 Gauza horiek funtzioaren izena ordeztuko dira 845 01:09:40,880 --> 01:09:42,930 edo lerroan zaudela kopurua. 846 01:09:42,930 --> 01:09:48,630 Maiz, arazteko printfs behera hemen orduan ezin dut idatzi idazten 847 01:09:48,630 --> 01:09:54,260 Arazteko eta lerro-kopurua eta funtzioa izango gerta inprimatu egingo du 848 01:09:54,260 --> 01:09:57,020 aurkitu duela arazteko adierazpena. 849 01:09:57,020 --> 01:09:59,550 Eta gainera, beste gauza batzuk inprima dezakezu. 850 01:09:59,550 --> 01:10:05,990 Beraz, gauza bat da watch out behar duzu gertatuko badut # define DOUBLE_MAX 851 01:10:05,990 --> 01:10:11,380 moduko zerbait, 2 * y 2 * x. 852 01:10:11,380 --> 01:10:14,310 Beraz, edozein arrazoigatik, asko gertatuko duzu. 853 01:10:14,310 --> 01:10:16,650 Beraz, makro bat. 854 01:10:16,650 --> 01:10:18,680 Hori benetan hautsi. 855 01:10:18,680 --> 01:10:23,050 Deitu nuke DOUBLE_MAX (3, 6) antzeko zerbait eginez. 856 01:10:23,050 --> 01:10:27,530 Beraz, zer itzuli behar? 857 01:10:28,840 --> 01:10:30,580 [Ikasleak] 12. 858 01:10:30,580 --> 01:10:34,800 Bai, 12 itzuli behar da, eta 12 itzuliko da. 859 01:10:34,800 --> 01:10:43,350 3 lortzen x ordezkatu, 6 lortzen y ordezkatu, eta 2 * 6 itzuliko gara, hau da, 12. 860 01:10:43,350 --> 01:10:47,710 Orain zer gertatzen da hau? Zer itzuli behar? 861 01:10:47,710 --> 01:10:50,330 [Ikasleak] 14. >> Egokiena, 14. 862 01:10:50,330 --> 01:10:55,290 Arazoa da nola definitzen hash lana, gogoratu hitzez hitz kopiatu eta itsatsi 863 01:10:55,290 --> 01:11:00,160 dena nahiko askoz, beraz, zer hori behar bezala interpretatu 864 01:11:00,160 --> 01:11:11,270 3 2 1 plus 6, aldiz, 1 plus 6, 2 aldiz 3 baino txikiagoa da. 865 01:11:11,270 --> 01:11:19,780 >> Hori dela eta, beraz, itzulbiratu ia beti parentesi artean duzun guztia. 866 01:11:22,180 --> 01:11:25,050 Edozein aldagai ere, parentesi artean ia beti biltzeko. 867 01:11:25,050 --> 01:11:29,570 Daude kasu non ez duzu, ez dakit, ez da horretarako beharrik ez hemen bezala 868 01:11:29,570 --> 01:11:32,110 baino gutxiago delako pretty askoz beti lanera joan 869 01:11:32,110 --> 01:11:34,330 agian ez, nahiz eta egia izan arren. 870 01:11:34,330 --> 01:11:41,870 DOUBLE_MAX (1 == 2) bezalako zerbait barregarria bada, 871 01:11:41,870 --> 01:11:49,760 Orduan, 1 3 baino gutxiago ordeztu berdin berdin 2, 872 01:11:49,760 --> 01:11:53,460 eta, beraz, ondoren 3 1 baino gutxiago egin da joan, eta ez berdintasunaren 2 873 01:11:53,460 --> 01:11:55,620 eta hori ez da zer nahi dugun. 874 01:11:55,620 --> 01:12:00,730 Beraz, edozein operadorea lehentasuna arazoak saihesteko, 875 01:12:00,730 --> 01:12:02,870 beti parentesi biltzeko. 876 01:12:03,290 --> 01:12:07,700 Ongi da. Eta hori izan da, 5:30. 877 01:12:08,140 --> 01:12:12,470 Behar duzu pset buruzko zalantzarik izanez gero, iezaguzu. 878 01:12:12,470 --> 01:12:18,010 Dibertigarria izan behar du, eta hacker edizioan ere askoz ere errealista da 879 01:12:18,010 --> 01:12:22,980 iazko edizioan hacker baino, eta, beraz, espero dugu asko saiatu da. 880 01:12:22,980 --> 01:12:26,460 Iaz oso erabatekoa izan zen. 881 01:12:28,370 --> 01:12:30,000 >> [CS50.TV]