1 00:00:00,000 --> 00:00:03,332 >> [REPRODUCCIÓ DE MÚSICA] 2 00:00:03,332 --> 00:00:06,490 >> ANDI Peng: Benvinguts a la setmana 3 de la secció. 3 00:00:06,490 --> 00:00:09,550 Gràcies, nois, per a tots ve a aquesta hora d'inici el dia d'avui. 4 00:00:09,550 --> 00:00:11,466 Tenim un bonic i petit grup íntim avui. 5 00:00:11,466 --> 00:00:14,570 Així que espero que arribarem a acabat, potser, d'hora, 6 00:00:14,570 --> 00:00:15,780 una mica d'hora avui. 7 00:00:15,780 --> 00:00:22,057 Així que ràpidament, només algunes anuncis per a l'ordre del dia d'avui. 8 00:00:22,057 --> 00:00:23,890 Abans de començar, estem va anar sobre 9 00:00:23,890 --> 00:00:28,910 alguns problemes logístics breus, pset preguntes, interrogar, coses així. 10 00:00:28,910 --> 00:00:30,250 I després anem a bussejar en dret. 11 00:00:30,250 --> 00:00:34,710 Utilitzarem un depurador GDB de trucada començar desacreditant el nostre codi, que David 12 00:00:34,710 --> 00:00:36,550 explicar en conferència l'altre dia. 13 00:00:36,550 --> 00:00:39,420 Anem a repassar els quatre tipus de classes. 14 00:00:39,420 --> 00:00:42,310 Anirem sobre ells amb força rapidesa ja que són molt intensius. 15 00:00:42,310 --> 00:00:45,710 Però saber que totes les diapositives i codi font són sempre en línia. 16 00:00:45,710 --> 00:00:50,810 Així que no dubti, en la seva lectura, a tornar enrere i fer una ullada a això. 17 00:00:50,810 --> 00:00:53,930 >> Anirem a través notació asimptòtica, que 18 00:00:53,930 --> 00:00:55,944 és només una forma elegant de dir "els temps d'execució" 19 00:00:55,944 --> 00:00:58,360 on tenim la gran O, el que David va explicar en conferència. 20 00:00:58,360 --> 00:01:01,550 I també hem Omega, que és el temps d'execució de límit inferior. 21 00:01:01,550 --> 00:01:06,450 I parlarem una mica més en profunditat pel que fa a com els treballs. 22 00:01:06,450 --> 00:01:10,160 I finalment, anem a repassar recerca binària, perquè molts de vostès que ja tenen 23 00:01:10,160 --> 00:01:15,190 va mirar als seus conjunts de processadors probablement saber que aquesta és una pregunta que està en el seu conjunt de processadors. 24 00:01:15,190 --> 00:01:17,470 Així que tots estarem feliços que cobrim això avui. 25 00:01:17,470 --> 00:01:20,610 >> I finalment, per la seva secció de comentaris, en realitat 26 00:01:20,610 --> 00:01:23,000 l'esquerra a uns 15 minuts a Al final només repassar 27 00:01:23,000 --> 00:01:27,730 logística de pset3, qualsevol pregunta, potser una mica d'orientació, si es vol, 28 00:01:27,730 --> 00:01:28,990 abans de començar la programació. 29 00:01:28,990 --> 00:01:30,890 Així que anem a tractar d'aconseguir a través de el material amb força rapidesa. 30 00:01:30,890 --> 00:01:33,880 I després podem passar algun temps tenint més preguntes per al conjunt de processadors. 31 00:01:33,880 --> 00:01:35,230 D'ACORD. 32 00:01:35,230 --> 00:01:39,570 >> Ràpidament, de manera que només uns pocs anuncis abans de començar avui. 33 00:01:39,570 --> 00:01:45,410 En primer lloc, recepció per fer a través de dos dels seus conjunts de processadors. 34 00:01:45,410 --> 00:01:49,432 Vaig consultar a tu-- Sí, anem a aconseguir un aplaudiment per a aquest. 35 00:01:49,432 --> 00:01:51,140 En realitat, jo estava molt, realment impressionats. 36 00:01:51,140 --> 00:01:55,800 Jo vaig qualificar el primer conjunt de processadors per a vostès setmana i últims nois van fer increïble. 37 00:01:55,800 --> 00:01:58,290 >> Estil estava en punt a més d'alguns comentaris. 38 00:01:58,290 --> 00:02:00,660 Assegureu-vos que està sempre comentant el seu codi. 39 00:02:00,660 --> 00:02:03,040 Però els seus conjunts de processadors estaven a punt. 40 00:02:03,040 --> 00:02:05,549 I segueix així. 41 00:02:05,549 --> 00:02:08,090 I és bo per al grau de veig que vostès estan posant 42 00:02:08,090 --> 00:02:10,704 en tant esforç en el seu estil i el seu disseny en el seu codi 43 00:02:10,704 --> 00:02:12,120 que ens agradaria perquè vostè vegi. 44 00:02:12,120 --> 00:02:16,450 Així que estic passant per la meva gratitud per a la resta de les AATT. 45 00:02:16,450 --> 00:02:19,210 >> No obstant això, hi ha una algunes preguntes debrief 46 00:02:19,210 --> 00:02:22,010 Només vull anar més que faria que tant la meva vida 47 00:02:22,010 --> 00:02:24,900 i un munt de l'altra TA 'viu una mica més fàcil. 48 00:02:24,900 --> 00:02:28,220 En primer lloc, m'he adonat d'això passat week-- quants de vostès 49 00:02:28,220 --> 00:02:32,301 han estat funcionant en check50 el seu codi abans d'enviar? 50 00:02:32,301 --> 00:02:32,800 D'ACORD. 51 00:02:32,800 --> 00:02:36,690 Així que tothom hauria d'estar fent check50, porque-- 1 secret-- realitat 52 00:02:36,690 --> 00:02:41,540 executar check50 com a part de la nostra correcció guions per provar el codi. 53 00:02:41,540 --> 00:02:45,480 Així que si el seu codi està fallant check50, amb tota probabilitat, 54 00:02:45,480 --> 00:02:47,570 que probablement va a fracassar el procés de registre també. 55 00:02:47,570 --> 00:02:49,320 De vegades els nois tenir les respostes correctes. 56 00:02:49,320 --> 00:02:52,200 Igual que, en cobdiciosos, alguns vostè té els números correctes, 57 00:02:52,200 --> 00:02:53,960 que acaba d'imprimir algunes coses extra. 58 00:02:53,960 --> 00:02:55,940 I aquest material extra en realitat no passa la verificació, 59 00:02:55,940 --> 00:02:58,440 perquè l'equip no realment sap el que està buscant. 60 00:02:58,440 --> 00:03:00,981 I així s'acaba d'executar a través de, veure que la seva sortida no 61 00:03:00,981 --> 00:03:03,810 igualarem el que esperem la resposta ser, i marcar que és un error. 62 00:03:03,810 --> 00:03:06,560 >> I sé que va succeir en alguns dels seus casos d'aquesta setmana. 63 00:03:06,560 --> 00:03:09,870 Així que vaig tornar i manual classificat de nou codi de tots. 64 00:03:09,870 --> 00:03:12,780 En el futur, però, per favor, per favor, asseguri 65 00:03:12,780 --> 00:03:14,570 que s'està executant comprovar 50 en el teu codi. 66 00:03:14,570 --> 00:03:17,970 A causa que és una mena de dolor per a la TA a haver de tornar enrere i manualment reclassificar 67 00:03:17,970 --> 00:03:21,197 cada conjunt de processadors única per a cada únic, exemple mica perdut. 68 00:03:21,197 --> 00:03:22,530 Així que no em trec cap punt. 69 00:03:22,530 --> 00:03:25,210 Crec que em vaig treure potser un o dos per al disseny. 70 00:03:25,210 --> 00:03:27,710 En el futur, tot i que, si vostè està fallant check50, 71 00:03:27,710 --> 00:03:31,330 es prendran punts apagat per a la correcció. 72 00:03:31,330 --> 00:03:35,020 >> A més, són conjunts de processadors a causa divendres al migdia. 73 00:03:35,020 --> 00:03:38,990 Crec que hi ha un nen de set minuts període de gràcia finals que li donem. 74 00:03:38,990 --> 00:03:42,434 Per temps de Harvard, que els permeti set minuts tard a tot. 75 00:03:42,434 --> 00:03:44,350 Així que aquí a Yale, anem a adherir-se a això també. 76 00:03:44,350 --> 00:03:47,910 Però més o menys, a les 00:07, si el seu conjunt de processadors no es troba en, 77 00:03:47,910 --> 00:03:49,720 que serà marcat com a tard. 78 00:03:49,720 --> 00:03:53,160 I així, mentre es marca el més tard, el TA-- estic 79 00:03:53,160 --> 00:03:54,870 encara serà la classificació dels seus conjunts de processadors. 80 00:03:54,870 --> 00:03:56,760 Així que vostè encara veu aparèixer un grau. 81 00:03:56,760 --> 00:03:58,820 No obstant això, saber que en Al final del semestre, 82 00:03:58,820 --> 00:04:02,270 tots els conjunts de processadors finals seran només posat a zero automàticament per l'ordinador. 83 00:04:02,270 --> 00:04:04,490 >> Fem això per dues raons. 84 00:04:04,490 --> 00:04:09,220 Un, de vegades obtenim excusat, com a excuses de Dean, 85 00:04:09,220 --> 00:04:10,762 més endavant que jo no sé res encara. 86 00:04:10,762 --> 00:04:13,761 Així que ens agrada assegurar-nos que estem classificació tot per si de cas, com, estic 87 00:04:13,761 --> 00:04:15,080 falta l'excusa d'un degà. 88 00:04:15,080 --> 00:04:17,000 I en segon lloc, tenir en ment, vostè pot encara 89 00:04:17,000 --> 00:04:19,370 excloure un conjunt de processadors que té punts d'abast complet. 90 00:04:19,370 --> 00:04:21,430 I així ens agrada grau tots els conjunts de processadors només 91 00:04:21,430 --> 00:04:24,730 per assegurar-se que el seu àmbit d'aplicació allà i vostè els està tractant. 92 00:04:24,730 --> 00:04:29,150 Així que fins i tot si és tard, se li segueix obtenir crèdit per als punts d'abast, crec. 93 00:04:29,150 --> 00:04:33,730 >> Així moralitat de la història és, fer Assegureu-vos que els seus conjunts de processadors estan en el temps. 94 00:04:33,730 --> 00:04:38,350 I si no estan en el temps, Sap que no és gran. 95 00:04:38,350 --> 00:04:41,678 Sí, abans de passar, algú té qualsevol pregunta respecte retroalimentació pset? 96 00:04:41,678 --> 00:04:42,178 Sí. 97 00:04:42,178 --> 00:04:43,630 >> AUDIÈNCIA: Has dit que pot caure un dels conjunts de processadors? 98 00:04:43,630 --> 00:04:44,296 >> ANDI Peng: Sí. 99 00:04:44,296 --> 00:04:47,050 Així que hi ha nou conjunts de processadors general en el transcurs del semestre. 100 00:04:47,050 --> 00:04:50,610 I si vostè té abast points-- el abast és just, 101 00:04:50,610 --> 00:04:53,567 més o menys, se li intenta la problema, estàs posant en el temps, 102 00:04:53,567 --> 00:04:56,150 se li mostra que vostè té demostrat que hagis llegit l'especificació. 103 00:04:56,150 --> 00:04:57,191 Això és més o menys abast. 104 00:04:57,191 --> 00:04:59,370 I si vostè està complint punts d'abast, que 105 00:04:59,370 --> 00:05:03,360 pot caure més baix un fos d'abast complet. 106 00:05:03,360 --> 00:05:06,790 Així que això és en el seu avantatge per completar i provar cada conjunt de processadors. 107 00:05:06,790 --> 00:05:10,320 >> Fins i tot upload-- si cap de ells treballen, pujar-los tots. 108 00:05:10,320 --> 00:05:13,711 I després anem a tant de bo siguem capaços de li donarà alguns d'aquests punts enrere. 109 00:05:13,711 --> 00:05:14,210 Fresc. 110 00:05:14,210 --> 00:05:16,780 Alguna altra pregunta? 111 00:05:16,780 --> 00:05:17,840 Gran. 112 00:05:17,840 --> 00:05:21,960 >> En segon lloc, l'oficina hores-- uns pocs notes ràpides sobre les hores d'oficina. 113 00:05:21,960 --> 00:05:24,300 Així que primer, arribar d'hora a la setmana. 114 00:05:24,300 --> 00:05:26,909 Ningú està mai en horari d'oficina els dilluns. 115 00:05:26,909 --> 00:05:28,700 Christabel va venir a les hores d'oficina de la nit anterior. 116 00:05:28,700 --> 00:05:29,691 Sí, Christabel. 117 00:05:29,691 --> 00:05:32,190 I què ens tenim a l'oficina hores d'anit, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> AUDIÈNCIA: Teníem gelat. 119 00:05:33,020 --> 00:05:36,160 >> ANDI Peng: Així que està bé, vam tenir gelat en horari d'oficina ahir a la nit. 120 00:05:36,160 --> 00:05:39,390 Encara que no puc prometre que tindrem gelat en horari d'oficina 121 00:05:39,390 --> 00:05:43,230 cada setmana, el que puc prometre és que hi haurà una significativament 122 00:05:43,230 --> 00:05:45,380 millor proporció d'estudiants per TA. 123 00:05:45,380 --> 00:05:47,650 Igual que fiar, és com tres a un. 124 00:05:47,650 --> 00:05:50,350 Atès que, contrastar això amb Dijous, tens al voltant de 150 125 00:05:50,350 --> 00:05:52,830 molt estressada nens i no gelat. 126 00:05:52,830 --> 00:05:55,360 I no és només productiva per a qualsevol persona. 127 00:05:55,360 --> 00:05:58,730 Així moralitat de la història és, arribar d'hora a les hores d'oficina i les coses bones 128 00:05:58,730 --> 00:06:00,310 passarà. 129 00:06:00,310 --> 00:06:02,110 >> També, vingui preparat per fer preguntes. 130 00:06:02,110 --> 00:06:03,200 Saps? 131 00:06:03,200 --> 00:06:05,420 Independentment del que els TA, em pensar, he estat dient, 132 00:06:05,420 --> 00:06:10,710 hem estat rebent un parell d'estudiants que vénen en dijous a, com, 10:50 133 00:06:10,710 --> 00:06:15,100 no haver llegit l'especificació sent així que m'ajudi, que m'ajudi. 134 00:06:15,100 --> 00:06:18,200 Desafortunadament en aquest punt, no hi ha no hi ha molt que puguem fer per ajudar-lo. 135 00:06:18,200 --> 00:06:19,590 Així que si us plau vingui a principis de la setmana. 136 00:06:19,590 --> 00:06:22,040 Vingui d'hora per les hores d'oficina. 137 00:06:22,040 --> 00:06:23,350 Vingui preparat per fer preguntes. 138 00:06:23,350 --> 00:06:25,310 Assegureu-vos que vostè, com a un estudiant, són on 139 00:06:25,310 --> 00:06:27,620 ha de ser perquè el TA pot guiar-lo al llarg, 140 00:06:27,620 --> 00:06:32,850 que és el que les hores d'oficina ha de ser assignat per. 141 00:06:32,850 --> 00:06:37,380 >> En segon lloc, pel que sé professors agradaria sorprendre'ns amb proves. 142 00:06:37,380 --> 00:06:39,439 Vaig tenir un professor dels com, jo, per cert, 143 00:06:39,439 --> 00:06:41,230 recordar que de meitat de període vostè té dilluns que ve. 144 00:06:41,230 --> 00:06:42,855 Sí, jo no sé res d'això de meitat de període. 145 00:06:42,855 --> 00:06:45,630 Així que seré que TA que recorda tot el que prova 146 00:06:45,630 --> 00:06:47,270 0-- perquè, ja saps, estem CS. 147 00:06:47,270 --> 00:06:50,730 Ara que hem matrius done, s'obté per què és prova 0, no interrogar 1, eh? 148 00:06:50,730 --> 00:06:51,320 D'ACORD. 149 00:06:51,320 --> 00:06:52,490 Oh, tinc algunes rialles en aquesta. 150 00:06:52,490 --> 00:06:53,120 D'ACORD. 151 00:06:53,120 --> 00:06:59,710 >> Així concurs 0 serà el 14 d'octubre, si vostè està en la secció de dilluns a dimecres 152 00:06:59,710 --> 00:07:02,920 i 15 d'octubre, si vostè està en la secció de dimarts a dijous. 153 00:07:02,920 --> 00:07:05,630 Això no s'aplica per als aquells de vostès a Harvard 154 00:07:05,630 --> 00:07:10,350 que-- Crec que tots podràs prendre els seus exàmens en la 14a. 155 00:07:10,350 --> 00:07:13,560 >> Així que sí, la setmana que ve, si David, a la conferència, es va, 156 00:07:13,560 --> 00:07:15,747 si, així que en això prova la setmana que ve, a tots 157 00:07:15,747 --> 00:07:17,580 no serà sorprès perquè vostè va venir a la secció 158 00:07:17,580 --> 00:07:19,664 i vostè sap que el seu concurs 0 és en dues setmanes. 159 00:07:19,664 --> 00:07:21,580 I tindrem opinió sessions i tot. 160 00:07:21,580 --> 00:07:26,360 Així que no et preocupis per tenir por per això. 161 00:07:26,360 --> 00:07:29,890 Qualsevol pregunta abans-- alguna pregunta en totes les qüestions logístiques relatives, 162 00:07:29,890 --> 00:07:32,591 classificació, les hores d'oficina, seccions? 163 00:07:32,591 --> 00:07:33,090 Sí. 164 00:07:33,090 --> 00:07:35,100 >> AUDIÈNCIA: Així que la prova és serà durant la conferència? 165 00:07:35,100 --> 00:07:35,766 >> ANDI Peng: Sí. 166 00:07:35,766 --> 00:07:39,460 Així que la prova, crec, és 60 minuts assignats en aquest interval de temps 167 00:07:39,460 --> 00:07:42,240 que vostè acaba de prendre a la sala de conferències. 168 00:07:42,240 --> 00:07:44,810 Així que vostè no ha de venir a en, com, un atzar 19:00. 169 00:07:44,810 --> 00:07:46,140 Està tot bé. 170 00:07:46,140 --> 00:07:47,100 Sí. 171 00:07:47,100 --> 00:07:50,060 Fresc. 172 00:07:50,060 --> 00:07:50,840 >> Tot bé. 173 00:07:50,840 --> 00:07:54,330 Així que anem a introduir un concepte per a vostè 174 00:07:54,330 --> 00:08:00,760 aquesta setmana que David ja té classe del tocat en la conferència de la setmana passada. 175 00:08:00,760 --> 00:08:02,010 Es diu GDB. 176 00:08:02,010 --> 00:08:05,570 I quants de vostès, mentre que en el curs de l'escriptura dels seus conjunts de processadors, 177 00:08:05,570 --> 00:08:09,981 han notat un gran botó que diu "Depuració" a la part superior del seu IDE? 178 00:08:09,981 --> 00:08:10,480 D'ACORD. 179 00:08:10,480 --> 00:08:13,770 Així que ara anem a realment arribem a descobrir el misteri del que en realitat botó 180 00:08:13,770 --> 00:08:14,270 ho fa. 181 00:08:14,270 --> 00:08:16,790 I et garanteixo que, es tracta d'un , Bella que té mèrit. 182 00:08:16,790 --> 00:08:20,740 >> Així que, fins ara, crec que ha hagut dues coses 183 00:08:20,740 --> 00:08:23,320 els estudiants han estat mai fent en depurar conjunts de processadors. 184 00:08:23,320 --> 00:08:27,635 Un d'ells, o bé afegir a printf () - pel que cada poques línies, 185 00:08:27,635 --> 00:08:29,760 s'agreguen en un printf () - oh, què és aquesta variable? 186 00:08:29,760 --> 00:08:32,551 Oh, què és aquesta variable ara-- i quin tipus de veure la progressió 187 00:08:32,551 --> 00:08:33,940 del seu codi ja que s'executa. 188 00:08:33,940 --> 00:08:37,030 O el segon mètode que fan els nens és que acaba d'escriure tot l'assumpte 189 00:08:37,030 --> 00:08:38,610 i després anar així al final. 190 00:08:38,610 --> 00:08:39,970 Esperem que funciona. 191 00:08:39,970 --> 00:08:44,851 Et garanteixo que, GDB és millor que tots dos d'aquests mètodes. 192 00:08:44,851 --> 00:08:45,350 Sí. 193 00:08:45,350 --> 00:08:46,980 Així que aquest serà el seu nou millor amic. 194 00:08:46,980 --> 00:08:51,780 Perquè és una cosa bella visualment que mostra tant 195 00:08:51,780 --> 00:08:54,850 el que el seu codi està fent en un punt específic 196 00:08:54,850 --> 00:08:57,486 així com el que la totalitat del seu variables que estan portant, 197 00:08:57,486 --> 00:08:59,610 com quins són els seus valors, en aquest punt específic. 198 00:08:59,610 --> 00:09:02,670 I d'aquesta manera, vostè pot realment establir punts d'interrupció en el codi. 199 00:09:02,670 --> 00:09:04,350 Vostè pot executar a través de línia per línia. 200 00:09:04,350 --> 00:09:07,324 I BGF només tindrà per vostè, mostren perquè vostè, 201 00:09:07,324 --> 00:09:09,490 el que totes les seves variables són, què estan fent, 202 00:09:09,490 --> 00:09:10,656 el que està passant en el codi. 203 00:09:10,656 --> 00:09:13,240 I de tal manera, que és molt més fàcil de veure 204 00:09:13,240 --> 00:09:17,120 el que està succeint en lloc de-ció printf o escriure les seves declaracions. 205 00:09:17,120 --> 00:09:19,160 >> Així que farem un exemple d'això més endavant. 206 00:09:19,160 --> 00:09:20,660 Així que això sembla una mica abstracte. 207 00:09:20,660 --> 00:09:23,490 No es preocupi, nosaltres farem exemples. 208 00:09:23,490 --> 00:09:29,170 I així, en essència, els tres més grans, funcions més utilitzades que necessitarà en el BGF 209 00:09:29,170 --> 00:09:32,500 són la continuació, passar per sobre, i Pas a botons. 210 00:09:32,500 --> 00:09:34,860 Vaig a dirigir- hi ha, en realitat, en aquest moment. 211 00:09:34,860 --> 00:09:40,930 >> Així es pot veure que tots els nois o hauria d'apropar una mica? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 A la part posterior, es pot veure això? 214 00:09:44,470 --> 00:09:45,730 He de fer un zoom? 215 00:09:45,730 --> 00:09:46,480 Només una mica? 216 00:09:46,480 --> 00:09:49,390 D'acord, guai. 217 00:09:49,390 --> 00:09:50,280 Som-hi. 218 00:09:50,280 --> 00:09:50,960 D'ACORD. 219 00:09:50,960 --> 00:09:57,000 >> Així que tinc, aquí, el meu aplicació de cobdiciosos. 220 00:09:57,000 --> 00:10:01,430 I mentre molts de vostès va escriure cobdiciosos en bucle while form-- que 221 00:10:01,430 --> 00:10:04,890 és una manera perfectament acceptable fer it-- una altra manera de fer-ho és simplement 222 00:10:04,890 --> 00:10:06,280 dividir en el mòdul. 223 00:10:06,280 --> 00:10:09,290 Perquè llavors vostè pot tenir el seu valor i després tenen la resta. 224 00:10:09,290 --> 00:10:11,150 I llavors vostè pot simplement afegir tot junt. 225 00:10:11,150 --> 00:10:13,390 La lògica del que estic fent aquí té sentit per a tothom, 226 00:10:13,390 --> 00:10:14,117 abans de començar? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Tipus de? 229 00:10:17,980 --> 00:10:18,710 Fresc. 230 00:10:18,710 --> 00:10:19,210 Gran. 231 00:10:19,210 --> 00:10:21,290 És una peça molt sexy del codi, diria jo. 232 00:10:21,290 --> 00:10:23,502 Com he dit, David, en donar una conferència, després d'un temps, 233 00:10:23,502 --> 00:10:25,960 tots vostès començarà a veure codi com una cosa que és bonic. 234 00:10:25,960 --> 00:10:29,950 I a vegades, quan veus bonica codi, és una sensació meravellosa. 235 00:10:29,950 --> 00:10:35,410 >> Així que no obstant això, mentre que aquest codi és molt bonic, que no funciona correctament. 236 00:10:35,410 --> 00:10:37,750 Així que anem a córrer check50 en això. 237 00:10:37,750 --> 00:10:39,440 Comprovi 50 20-- oop. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 És que PSet2? 241 00:10:44,990 --> 00:10:46,870 Sí. 242 00:10:46,870 --> 00:10:47,520 Oh, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 D'ACORD. 245 00:10:52,890 --> 00:10:53,900 Així correm check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> I com vostès poden veure aquí, està fallant un parell de casos. 248 00:11:07,170 --> 00:11:10,165 I per a alguns de vostès, al curs de fer els seus butlletins de problemes, 249 00:11:10,165 --> 00:11:11,110 vostè és com, ah, ¿per què no està funcionant. 250 00:11:11,110 --> 00:11:13,318 Per què és treballant des de fa valors, però no per a altres? 251 00:11:13,318 --> 00:11:17,760 Bé, GDB es va a ajudar a la figura per què aquestes entrades no estaven funcionant. 252 00:11:17,760 --> 00:11:18,320 >> D'ACORD. 253 00:11:18,320 --> 00:11:21,640 Així que anem a veure, un dels xecs que estava fallant en check50 254 00:11:21,640 --> 00:11:24,920 era el valor d'entrada de 0,41. 255 00:11:24,920 --> 00:11:27,830 Així que la resposta correcta que que hauria d'estar rebent és un 4. 256 00:11:27,830 --> 00:11:33,090 Però en lloc del que estic imprimint és el 3-n, que és incorrecte. 257 00:11:33,090 --> 00:11:36,190 Així que anem a executar això manualment, simplement assegurar-se que check50 està treballant. 258 00:11:36,190 --> 00:11:36,940 Fem ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Vaja, he de fer cobdiciós. 261 00:11:43,340 --> 00:11:43,840 Som-hi. 262 00:11:43,840 --> 00:11:44,381 Ara ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Quant se li deu? 265 00:11:47,670 --> 00:11:49,550 Fem 0.41. 266 00:11:49,550 --> 00:11:52,590 I sí, ens veiem aquí que està la sortida 3 267 00:11:52,590 --> 00:11:55,160 quan la resposta correcta, De fet, hauria de ser abril. 268 00:11:55,160 --> 00:12:01,460 Així que anem a entrar al BGF i ​​vegem com ens pot anar sobre la fixació d'aquest problema. 269 00:12:01,460 --> 00:12:03,992 >> Així que el primer pas en Sempre depurar el seu codi 270 00:12:03,992 --> 00:12:05,950 és establir un punt d'interrupció, o d'un punt en el qual 271 00:12:05,950 --> 00:12:09,079 desitja que l'ordinador o la depurador per iniciar mirant. 272 00:12:09,079 --> 00:12:11,120 Així que si vostè realment no sé quin és el teu problema, 273 00:12:11,120 --> 00:12:14,670 en general, el típic volem fer és configurar el nostre punt d'interrupció en el principal. 274 00:12:14,670 --> 00:12:18,520 Així que si vostès poden veure això botó vermell allà, 275 00:12:18,520 --> 00:12:22,860 sí, aquest era jo l'establiment d'un punt de ruptura per a la funció principal. 276 00:12:22,860 --> 00:12:24,130 Faig clic en això. 277 00:12:24,130 --> 00:12:26,130 >> I llavors em puc anar al meu botó de depuració. 278 00:12:26,130 --> 00:12:27,036 Vaig colpejar aquest botó. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Permetin-me amplia la imatge si puc. 281 00:12:36,555 --> 00:12:38,020 Som-hi. 282 00:12:38,020 --> 00:12:40,730 Així que tenim, aquí, un panell de la dreta. 283 00:12:40,730 --> 00:12:43,680 Ho sento, nois a la part posterior, que en realitat no pot veure molt bé. 284 00:12:43,680 --> 00:12:49,090 Però, en essència, tot aquest panell de la dreta està fent 285 00:12:49,090 --> 00:12:53,130 és no perdre de vista tant del lloc de relleu línia, que és la línia de codi 286 00:12:53,130 --> 00:12:56,640 que l'equip està executant actualment, així com totes les seves variables 287 00:12:56,640 --> 00:12:57,600 aquí baix. 288 00:12:57,600 --> 00:13:00,487 >> Així que tens centaus, monedes, n, totes declarat a coses diferents 289 00:13:00,487 --> 00:13:01,070 en aquest punt. 290 00:13:01,070 --> 00:13:04,850 No es preocupi, perquè en realitat no tenen ells inicialitzat a qualsevol variable encara. 291 00:13:04,850 --> 00:13:07,200 Així que a l'ordinador, la seva equip acaba de veure, 292 00:13:07,200 --> 00:13:14,376 oh, 32767 va ser l'última funció utilitzada d'aquest espai de memòria en el meu equip. 293 00:13:14,376 --> 00:13:16,000 Així que aquí és on actualment centaus és. 294 00:13:16,000 --> 00:13:19,360 Però ningú que una vegada que s'executa el codi, hauria de convertir inicialitzat. 295 00:13:19,360 --> 00:13:24,110 >> Així que anem a anar a través, línia per line, el que està passant aquí. 296 00:13:24,110 --> 00:13:25,350 D'ACORD. 297 00:13:25,350 --> 00:13:29,400 Així que aquí estan els tres botons que acabo d'explicar. 298 00:13:29,400 --> 00:13:34,090 Vostè té el joc, o la funció Executar, botó, vostè té el pas sobre el botó, 299 00:13:34,090 --> 00:13:36,600 i també té el Pas a botó. 300 00:13:36,600 --> 00:13:41,260 I, essencialment, els tres ells només van a través del seu codi 301 00:13:41,260 --> 00:13:42,690 i fer coses diferents. 302 00:13:42,690 --> 00:13:45,680 >> Així que en general, quan vostè està de depuració, nosaltres no volem només cal prémer Play, 303 00:13:45,680 --> 00:13:47,930 perquè Play n'hi ha prou amb executar el seu codi al final de la mateixa. 304 00:13:47,930 --> 00:13:49,070 I llavors no ho farà realitat saber quin és el seu problema 305 00:13:49,070 --> 00:13:51,432 és menys que estableixi múltiples punts d'interrupció. 306 00:13:51,432 --> 00:13:53,890 Si estableix diversos punts d'interrupció, s'acaba de forma automàtica 307 00:13:53,890 --> 00:13:56,030 córrer d'un punt de ruptura, a la següent, a la següent. 308 00:13:56,030 --> 00:13:58,030 Però en aquest cas que hem només que un, perquè 309 00:13:58,030 --> 00:13:59,970 volen treballar nostre camí de dalt a baix a baix. 310 00:13:59,970 --> 00:14:04,830 Així que anem a ignorar aquest botó en aquest moment per als propòsits d'aquest programa. 311 00:14:04,830 --> 00:14:08,230 >> Així que el pas sobre la funció només passos sobre cada línia 312 00:14:08,230 --> 00:14:11,510 i et diu el que l'equip està fent. 313 00:14:11,510 --> 00:14:14,630 El Pas en funció va en la funció real 314 00:14:14,630 --> 00:14:16,000 això és en la seva línia de codi. 315 00:14:16,000 --> 00:14:19,070 Així, per exemple, com printf (), que és una funció, no? 316 00:14:19,070 --> 00:14:21,980 Si volgués pas físicament en la funció printf (), 317 00:14:21,980 --> 00:14:25,610 Jo realment entrar en el tros de codi on printf () va ser escrit i veure 318 00:14:25,610 --> 00:14:26,730 el que està passant allà. 319 00:14:26,730 --> 00:14:29,924 >> Però en general, se suposa que el codi que et donem funciona. 320 00:14:29,924 --> 00:14:31,340 Assumim el printf () està treballant. 321 00:14:31,340 --> 00:14:33,170 Suposem que getInt () està treballant. 322 00:14:33,170 --> 00:14:35,170 Així que no hi ha necessitat de entrar en aquestes funcions. 323 00:14:35,170 --> 00:14:37,170 Però si hi ha funcions que escrigui vostè mateix 324 00:14:37,170 --> 00:14:39,060 que desitja comprovar el que està passant, 325 00:14:39,060 --> 00:14:41,200 vostè vol fer un pas en aquesta funció. 326 00:14:41,200 --> 00:14:43,940 >> Així que ara només anem al passar per sobre d'aquest tros de codi. 327 00:14:43,940 --> 00:14:44,485 Així que anem a veure. 328 00:14:44,485 --> 00:14:46,547 Oh, imprimir, "Oh hai, com es va deure en gran canvi? " 329 00:14:46,547 --> 00:14:47,130 No ens importa. 330 00:14:47,130 --> 00:14:49,830 Sabem que està funcionant, així que passar per sobre d'ella. 331 00:14:49,830 --> 00:14:53,290 >> Així que n, que és la nostra carrossa que que hem initialized-- o declared-- 332 00:14:53,290 --> 00:14:56,810 a la part superior, ara estem igualant que a GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Així que anem a passar per sobre d'això. 334 00:14:57,810 --> 00:14:59,580 I veiem en la fons aquí, el programa 335 00:14:59,580 --> 00:15:03,360 m'està incitant a l'entrada d'un valor. 336 00:15:03,360 --> 00:15:08,580 Així d'entrada de deixar que el valor que volem per provar aquí, que és 0,41. 337 00:15:08,580 --> 00:15:09,160 Gran. 338 00:15:09,160 --> 00:15:12,780 >> Així que ara N-- Vostès Veure aquí, al bottom-- és 339 00:15:12,780 --> 00:15:15,140 stored-- perquè no han arrodonit però, és 340 00:15:15,140 --> 00:15:19,540 emmagatzemada en aquest gegant com flotant que és 0,4099999996, 341 00:15:19,540 --> 00:15:22,550 que és prou a prop del nostre propòsits, ara mateix, a 0,41. 342 00:15:22,550 --> 00:15:26,090 I després ja veurem més endavant, a mesura que continuar passant per sobre del programa, 343 00:15:26,090 --> 00:15:29,850 després aquí, n s'ha convertit en arrodonida i centaus s'ha convertit en 41. 344 00:15:29,850 --> 00:15:30,350 Gran. 345 00:15:30,350 --> 00:15:32,230 Així que sabem que el treball de la nostra arrodoniment. 346 00:15:32,230 --> 00:15:34,700 Sabem que tenim la nombre correcte de centaus, 347 00:15:34,700 --> 00:15:36,990 així que sabem que això és no és realment el problema. 348 00:15:36,990 --> 00:15:40,050 >> Així que seguim pas a pas en aquest programa. 349 00:15:40,050 --> 00:15:40,900 Anem aquí. 350 00:15:40,900 --> 00:15:46,139 I així, després d'aquesta línia de codi, ha de saber quants quarts que tenim. 351 00:15:46,139 --> 00:15:46,680 Fem un pas més. 352 00:15:46,680 --> 00:15:52,040 I vostè veure el que fem, de fet, tenim un sol trimestre perquè hem restem 25 353 00:15:52,040 --> 00:15:53,790 del nostre valor inicial de 41. 354 00:15:53,790 --> 00:15:55,890 I tenim 16 esquerra per als nostres centaus. 355 00:15:55,890 --> 00:15:58,830 >> Tothom entén com el programa està intensificant a través 356 00:15:58,830 --> 00:16:02,980 i per què centaus ara s'ha convertit en 16 i per què, ara, les monedes s'ha convertit en 1? 357 00:16:02,980 --> 00:16:04,610 Està tot el món seguint aquesta lògica? 358 00:16:04,610 --> 00:16:05,110 Fresc. 359 00:16:05,110 --> 00:16:07,860 Així que a partir d'aquest punt, el de treball del programa, no? 360 00:16:07,860 --> 00:16:09,797 Sabem que està fent exactament el que volem que ho faci. 361 00:16:09,797 --> 00:16:11,880 I no ho vam fer realitat han d'imprimir, oh, què 362 00:16:11,880 --> 00:16:14,430 és cèntims en aquest punt, el que és les monedes en aquest punt. 363 00:16:14,430 --> 00:16:17,170 >> Seguim passant pel programa. 364 00:16:17,170 --> 00:16:18,100 Pas acabat. 365 00:16:18,100 --> 00:16:18,620 Fresc. 366 00:16:18,620 --> 00:16:19,700 Repassem monedes de deu centaus. 367 00:16:19,700 --> 00:16:20,200 Gran. 368 00:16:20,200 --> 00:16:22,367 Veiem que es pren de $ 0.10 per a un cèntim. 369 00:16:22,367 --> 00:16:23,450 I ara tenim dues monedes. 370 00:16:23,450 --> 00:16:25,260 Això és correcte. 371 00:16:25,260 --> 00:16:31,555 >> Repassem penics i veiem que que ens queda més centaus. 372 00:16:31,555 --> 00:16:32,680 Hmm, això és estrany. 373 00:16:32,680 --> 00:16:37,540 Fins aquí, al programa, que se suposava haver restat meus penics. 374 00:16:37,540 --> 00:16:39,400 Potser jo no estava fent que la línia dreta. 375 00:16:39,400 --> 00:16:42,190 I per desgràcia, es pot veure aquí, perquè sabem 376 00:16:42,190 --> 00:16:44,360 que estem trepitjant a través de línies 32 i 33, 377 00:16:44,360 --> 00:16:50,560 aquí és on el nostre programa inadequadament van tenir les variables corren. 378 00:16:50,560 --> 00:16:55,136 Així que podem mirar i veure, oh, Estic restant centaus aquí, 379 00:16:55,136 --> 00:16:57,010 però no estic realment afegir a la meva valor de la moneda. 380 00:16:57,010 --> 00:16:57,860 Estic afegint a centaus. 381 00:16:57,860 --> 00:17:00,234 I jo no vull afegir a centaus, vull afegir a monedes. 382 00:17:00,234 --> 00:17:05,420 Així que si canviem això a monedes, tenim un programa de treball. 383 00:17:05,420 --> 00:17:06,730 Puc córrer check50. 384 00:17:06,730 --> 00:17:11,063 Vostè només pot sortir del BGF dret aquí i després executar check50 nou. 385 00:17:11,063 --> 00:17:11,938 Jo només podia fer això. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 He de fer cobdiciós. 388 00:17:18,480 --> 00:17:19,940 0.41. 389 00:17:19,940 --> 00:17:22,819 I aquí, és la impressió la resposta correcta. 390 00:17:22,819 --> 00:17:26,569 >> Així com vostès poden veure, el BGF és una eina molt potent 391 00:17:26,569 --> 00:17:29,940 per quan tenim tant codi passant i tantes variables 392 00:17:29,940 --> 00:17:32,510 que és difícil per a nosaltres, com un ésser humà, no perdre de vista. 393 00:17:32,510 --> 00:17:35,360 L'equip, en el BGF depurador, té la capacitat 394 00:17:35,360 --> 00:17:37,020 fer un seguiment de tot. 395 00:17:37,020 --> 00:17:40,480 Ja ho sé, en Visionaire, vostès probablement podria haver afectat alguns errors de segmentació 396 00:17:40,480 --> 00:17:43,150 a causa que s'estava executant fora dels límits de la matriu. 397 00:17:43,150 --> 00:17:46,510 En l'exemple de César, això és exactament el que he implementat aquí. 398 00:17:46,510 --> 00:17:50,060 >> Així que em vaig oblidar de comprovar ¿Què passaria si jo 399 00:17:50,060 --> 00:17:52,510 no tenir dos arguments de la línia d'ordres. 400 00:17:52,510 --> 00:17:53,880 Simplement no em poso en el registre d'entrada. 401 00:17:53,880 --> 00:17:57,380 I així, si em quedo Debug-- configurar meu punt de ruptura a la dreta allà. 402 00:17:57,380 --> 00:17:58,055 Corro de depuració. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> D'ACORD. 405 00:18:16,550 --> 00:18:17,050 Sí. 406 00:18:17,050 --> 00:18:20,350 Així que en realitat, el BGF se suposava m'han dit que hi ha 407 00:18:20,350 --> 00:18:22,300 Va ser un error de segmentació allà. 408 00:18:22,300 --> 00:18:24,883 No sé el que estava passant allà mateix, però quan em vaig trobar amb ell, 409 00:18:24,883 --> 00:18:25,590 que estava treballant. 410 00:18:25,590 --> 00:18:29,410 Quan s'executa a través de línies de codi i BGF podria deixar de cop i volta sobre tu, 411 00:18:29,410 --> 00:18:31,540 puja i mira el que és l'error vermell. 412 00:18:31,540 --> 00:18:33,930 L'hi diré, bé, tingut un error de segmentació, 413 00:18:33,930 --> 00:18:38,550 el que significa que va intentar accedir espai en una matriu que no existia. 414 00:18:38,550 --> 00:18:39,050 Sí. 415 00:18:39,050 --> 00:18:43,280 >> Així que en el següent problema estableixi aquesta setmana, nois 416 00:18:43,280 --> 00:18:45,600 probablement tindrà una gran quantitat de Variables surant al voltant. 417 00:18:45,600 --> 00:18:48,560 No va a estar segur del que tots ells signifiquen en un moment determinat. 418 00:18:48,560 --> 00:18:53,560 Així GDB realment l'ajudarà a esbrinar el que tots ells estan igualant 419 00:18:53,560 --> 00:18:55,940 i ser capaç de veure que visualment. 420 00:18:55,940 --> 00:19:01,995 Hi ha algú confós sobre com res d'això estava treballant? 421 00:19:01,995 --> 00:19:02,495 Fresc. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Tot bé. 424 00:19:10,620 --> 00:19:14,260 Així que després d'això, estem anar a bussejar en dret 425 00:19:14,260 --> 00:19:17,562 en són quatre diferents tipus de classes per a aquesta setmana. 426 00:19:17,562 --> 00:19:19,520 Quants de vostès, primer sobretot, abans de començar, 427 00:19:19,520 --> 00:19:23,020 han llegit tota l'especificació per pset3? 428 00:19:23,020 --> 00:19:23,824 D'ACORD. 429 00:19:23,824 --> 00:19:24,740 Estic orgullós de vosaltres. 430 00:19:24,740 --> 00:19:29,110 Això és com la meitat de la classe, que és significativament més que l'última vegada. 431 00:19:29,110 --> 00:19:33,950 >> Així que això és genial, perquè quan parlem sobre el contingut 432 00:19:33,950 --> 00:19:36,170 en lecture-- o ho sento, en secció- m'agrada 433 00:19:36,170 --> 00:19:38,210 relacionar molt d'això de nou al que el conjunt de processadors és 434 00:19:38,210 --> 00:19:40,210 i com voleu implementar això en el seu conjunt de processadors. 435 00:19:40,210 --> 00:19:42,400 Així que si vostè ve tenint llegir l'especificació, que va 436 00:19:42,400 --> 00:19:45,510 ser molt més fàcil perquè vostè entengui el que estic parlant quan dic, 437 00:19:45,510 --> 00:19:48,720 oh bo, això podria ser una realitat bon lloc per posar en pràctica aquest tipus. 438 00:19:48,720 --> 00:19:52,870 Així que aquells de vostès que han llegit el spec saber que, com a part del seu conjunt de processadors, 439 00:19:52,870 --> 00:19:54,900 vostè va a haver de escriure un tipus d'espècie. 440 00:19:54,900 --> 00:19:58,670 Així que això pot ser molt útil per a molts de vostès avui. 441 00:19:58,670 --> 00:20:01,760 >> Així que anem a començar amb, en essència, el tipus més senzill 442 00:20:01,760 --> 00:20:04,580 de gènere, l'ordenació per selecció. 443 00:20:04,580 --> 00:20:06,800 L'algorisme típic per com ens agradaria anar sobre això 444 00:20:06,800 --> 00:20:10,460 és-- David va passar per aquests tots en conferència, així que passaré ràpidament al llarg 445 00:20:10,460 --> 00:20:13,900 aquí-- és essencialment, que tenir una matriu de valors. 446 00:20:13,900 --> 00:20:17,170 I després trobar el menor valor sense classificar 447 00:20:17,170 --> 00:20:20,200 i canvies aquest valor amb el primer valor sense classificar. 448 00:20:20,200 --> 00:20:22,700 I després et quedes amb la repetició amb la resta de la seva llista. 449 00:20:22,700 --> 00:20:25,740 >> I aquí hi ha una explicació visual de la manera com havia de funcionar. 450 00:20:25,740 --> 00:20:30,460 Així, per exemple, si haguéssim de començar amb una sèrie de cinc elements, l'índex 451 00:20:30,460 --> 00:20:35,910 0 a 4, amb 3, 5, 2, 6, i 4 valors col·locat en el array-- així que ara, 452 00:20:35,910 --> 00:20:38,530 només assumirem que tots estan sense classificar 453 00:20:38,530 --> 00:20:41,130 perquè no hem provat el contrari. 454 00:20:41,130 --> 00:20:44,130 >> Llavors, com una tria tipus faria la feina és que ho faria primer 455 00:20:44,130 --> 00:20:46,800 executar a través de la totalitat de la matriu sense classificar. 456 00:20:46,800 --> 00:20:49,120 Seria seleccionar el valor més petit. 457 00:20:49,120 --> 00:20:51,750 En aquest cas, 3, a la dreta Ara, és el més petit. 458 00:20:51,750 --> 00:20:52,680 Es posa a 5. 459 00:20:52,680 --> 00:20:55,620 No, 5 no és gran no sigui: o ho sento, no és inferior a: 3. 460 00:20:55,620 --> 00:20:57,779 Per tant el valor mínim és encara 3. 461 00:20:57,779 --> 00:20:58,695 I llavors s'arriba a 2. 462 00:20:58,695 --> 00:21:00,990 L'equip considera que, oh, 2 és inferior a 3. 463 00:21:00,990 --> 00:21:02,750 2 ha d'ésser ara el valor mínim. 464 00:21:02,750 --> 00:21:06,630 I així febrer swaps amb aquest primer valor. 465 00:21:06,630 --> 00:21:10,702 >> Així que després d'una passada, nosaltres de fet veiem que el 2 i el 3 s'intercanvien. 466 00:21:10,702 --> 00:21:13,910 I només continuarem fent això de nou amb la resta de la matriu. 467 00:21:13,910 --> 00:21:17,660 Així que anem a simplement executar a través de els últims quatre índexs de la matriu. 468 00:21:17,660 --> 00:21:20,670 Veurem que 3 és el següent valor mínim. 469 00:21:20,670 --> 00:21:23,240 Així que anem a canviar això amb 4. 470 00:21:23,240 --> 00:21:26,900 I llavors només anem a mantenir que travessa fins que, finalment, es 471 00:21:26,900 --> 00:21:33,730 arribar a un arranjament ordenat en el qual 2, 3, 4, 5, i 6 es tot Tipus. 472 00:21:33,730 --> 00:21:37,530 Tots entenen la lògica de com funciona una selecció espècie? 473 00:21:37,530 --> 00:21:39,669 >> Només tens algun tipus d'un valor mínim. 474 00:21:39,669 --> 00:21:41,210 Ets fer el seguiment del que és. 475 00:21:41,210 --> 00:21:45,170 I cada vegada que el trobes, canvies el amb el primer valor al array-- 476 00:21:45,170 --> 00:21:48,740 o bé, no és la primera value-- el següent valor en la matriu. 477 00:21:48,740 --> 00:21:50,150 Fresc. 478 00:21:50,150 --> 00:21:55,460 >> Així com vostès classe de va veure des d'un breu cop d'ull, 479 00:21:55,460 --> 00:21:58,450 anem a Pseudocodi això. 480 00:21:58,450 --> 00:22:02,510 Així que si vostès a la part posterior voleu formar un grup, tothom en una taula 481 00:22:02,510 --> 00:22:06,170 poden formar un petit company, vaig per donar-li tipus com tres minuts 482 00:22:06,170 --> 00:22:08,190 simplement parlar a través de la lògica, en anglès, 483 00:22:08,190 --> 00:22:14,161 de com podríem ser capaços d'implementar pseudocodi per escriure una ordenació per selecció. 484 00:22:14,161 --> 00:22:14,910 I hi ha dolços. 485 00:22:14,910 --> 00:22:16,118 Si us plau vingui i aconseguir caramels. 486 00:22:16,118 --> 00:22:19,520 Si estàs a la part de darrere i desitja dolços, puc tirar caramels a vostè. 487 00:22:19,520 --> 00:22:22,850 En realitat, fer fresc usted--. 488 00:22:22,850 --> 00:22:23,552 Oh, ho sento. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 D'ACORD. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Així que si ens agradaria, ja que una classe, escriure pseudocodi 493 00:25:27,140 --> 00:25:30,466 per com es podria acostar- aquest problema, tot just sent lliure. 494 00:25:30,466 --> 00:25:32,340 Aniré al seu voltant i, per tal, demani grups 495 00:25:32,340 --> 00:25:35,065 per a la següent línia de el que hauríem d'estar fent. 496 00:25:35,065 --> 00:25:37,840 Així que si vostès volen començar fora, ¿què és el primer 497 00:25:37,840 --> 00:25:40,600 Què fer quan vostè està tractant de posar en pràctica una forma de resoldre aquest programa 498 00:25:40,600 --> 00:25:43,480 per ordenar selectivament una llista? 499 00:25:43,480 --> 00:25:46,349 Anem a suposar que tenir una matriu, ¿d'acord? 500 00:25:46,349 --> 00:25:49,088 >> AUDIÈNCIA: Vols crear alguns espècie de [inaudible] que ets 501 00:25:49,088 --> 00:25:50,420 corrent a través de tota la seva gamma. 502 00:25:50,420 --> 00:25:51,128 >> ANDI Peng: Correcte. 503 00:25:51,128 --> 00:25:54,100 Així que vas a voler repetir a través de cada espai, no? 504 00:25:54,100 --> 00:26:05,490 Tan gran. 505 00:26:05,490 --> 00:26:08,600 Si vostès volen que em donés el juntament line-- sí, a la part posterior. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> AUDIÈNCIA: Fes- sobretot per als més petits. 508 00:26:13,290 --> 00:26:14,248 >> ANDI Peng: No. 509 00:26:14,248 --> 00:26:17,438 Així que volem anar a través i verifiqui veure el que el valor mínim és, oi? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Vaig a abreujar que a "min". 512 00:26:24,840 --> 00:26:27,658 Què és el que vostès volen fer després has trobat el valor mínim? 513 00:26:27,658 --> 00:26:28,533 >> AUDIÈNCIA: [inaudible] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI Peng: ¿Així que vas a voler canviar amb el primer d'aquesta sèrie, 516 00:26:33,150 --> 00:26:33,650 Oi? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Aquest és el principi, que vaig a dir. 519 00:26:46,850 --> 00:26:47,220 Tot bé. 520 00:26:47,220 --> 00:26:50,386 Així que ara que ha canviat el primer un, ¿què és el que vols fer després d'això? 521 00:26:50,386 --> 00:26:54,840 Així que ara sabem que aquest d'aquí ha de ser el valor més petit, no? 522 00:26:54,840 --> 00:26:58,310 Llavors vostè té un descans addicional de la matriu que està sense classificar. 523 00:26:58,310 --> 00:27:01,569 Així que el que vull fer aquí, si nois volen donar-me la següent línia? 524 00:27:01,569 --> 00:27:04,610 AUDIÈNCIA: Llavors vol iterar a través de la resta de la matriu. 525 00:27:04,610 --> 00:27:05,276 ANDI Peng: Sí. 526 00:27:05,276 --> 00:27:09,857 I així ho fa a través de la iteració tipus de implicar que probablement necessitarem? 527 00:27:09,857 --> 00:27:10,440 Quin tipus de-- 528 00:27:10,440 --> 00:27:12,057 >> AUDIÈNCIA: Oh, una variable addicional? 529 00:27:12,057 --> 00:27:13,890 ANDI Peng: Probablement una altra per al bucle, oi? 530 00:27:13,890 --> 00:27:28,914 Així que probablement voldrem iterar through-- gran. 531 00:27:28,914 --> 00:27:31,830 I després vas a tornar i Probablement comprovar el mínim de nou, 532 00:27:31,830 --> 00:27:32,100 Oi? 533 00:27:32,100 --> 00:27:34,975 I vostè va a seguir repetint això, perquè els bucles només va 534 00:27:34,975 --> 00:27:36,010 per seguir funcionant, no? 535 00:27:36,010 --> 00:27:39,190 >> Així com vostès poden veure, només tenen un pseudocodi en general 536 00:27:39,190 --> 00:27:41,480 de com volem que aquest programa es vegi. 537 00:27:41,480 --> 00:27:46,646 Aquest reiterar aquí, què fem normalment necessitarà escriure en el nostre codi 538 00:27:46,646 --> 00:27:49,270 si volem recórrer un matriu, quin tipus d'estructura? 539 00:27:49,270 --> 00:27:51,030 Crec que Christabel ja s'ha dit abans. 540 00:27:51,030 --> 00:27:51,500 >> AUDIÈNCIA: Un bucle for. 541 00:27:51,500 --> 00:27:52,160 >> ANDI Peng: Un bucle for? 542 00:27:52,160 --> 00:27:52,770 Exactament. 543 00:27:52,770 --> 00:27:56,060 Així que aquest és probablement Serà un bucle for. 544 00:27:56,060 --> 00:27:59,240 Què és un xec aquí va a entendre? 545 00:27:59,240 --> 00:28:02,536 Normalment, si desitja comprovar si alguna cosa és alguna cosa else-- 546 00:28:02,536 --> 00:28:03,270 >> AUDIÈNCIA: Si. 547 00:28:03,270 --> 00:28:06,790 >> ANDI Peng: Un cas, ¿no? 548 00:28:06,790 --> 00:28:10,790 I llavors el bescanvi Aquí, anem a anar més tard, perquè David 549 00:28:10,790 --> 00:28:12,770 passar per que en la conferència també. 550 00:28:12,770 --> 00:28:14,580 I llavors la segona iteració implies-- 551 00:28:14,580 --> 00:28:15,120 >> AUDIÈNCIA: Una altra de bucle. 552 00:28:15,120 --> 00:28:16,745 >> ANDI Peng: --another bucle for, exactament. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Així que si estem buscant en aquest correctament, 555 00:28:22,000 --> 00:28:24,680 pot veure que estem probablement va a necessitar un niat bucle for 556 00:28:24,680 --> 00:28:28,330 amb una sentència condicional allà i després una veritable peça de codi que és 557 00:28:28,330 --> 00:28:31,360 canviarà els valors. 558 00:28:31,360 --> 00:28:35,980 Així que en general, que he escrit un codi de pseudocodi aquí. 559 00:28:35,980 --> 00:28:38,910 I llavors estem realment va físicament, com una classe, 560 00:28:38,910 --> 00:28:40,700 tractar d'aplicar això avui. 561 00:28:40,700 --> 00:28:42,486 Tornem a aquest IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> UH oh. 564 00:28:50,230 --> 00:28:51,754 Per què és que no-- aquí està. 565 00:28:51,754 --> 00:28:52,253 D'ACORD. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Ho sentim, però vaig a tractar d'apropar una mica més. 568 00:28:57,500 --> 00:28:59,310 Som-hi. 569 00:28:59,310 --> 00:29:05,060 Tot el que estic fent aquí és que he creat un programa anomenat "selecció / sort.c." 570 00:29:05,060 --> 00:29:10,860 He creat una sèrie de nou anys valors, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 Actualment, com pugui veure, són desordenats. 572 00:29:14,370 --> 00:29:17,880 n serà el nombre que li diu la quantitat de valors 573 00:29:17,880 --> 00:29:18,920 que té en el seu arsenal. 574 00:29:18,920 --> 00:29:20,670 En aquest cas, tenim nou valors. 575 00:29:20,670 --> 00:29:23,760 I només tinc un bucle for aquí que imprimeix la matriu sense classificar. 576 00:29:23,760 --> 00:29:28,370 >> I al final, jo també tinc una per bucle que només imprimeix cap a fora una altra vegada. 577 00:29:28,370 --> 00:29:32,070 Així que en teoria, si aquest programa funciona correctament, al final, 578 00:29:32,070 --> 00:29:35,670 ha de mostrar un imprimeixen bucle for en el qual 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 són tot correctament en ordre. 580 00:29:39,310 --> 00:29:43,410 >> Així que tenim el nostre pseudocodi aquí. 581 00:29:43,410 --> 00:29:46,090 Algú vol A-- Només sóc va a anar demanar volunteers-- 582 00:29:46,090 --> 00:29:49,540 digues-me exactament què escriure si volem, en primer lloc, simplement iterar 583 00:29:49,540 --> 00:29:52,840 a través del principi d'aquesta matriu? 584 00:29:52,840 --> 00:29:55,204 Quina és la línia de codi que sóc Probablement necessitarà aquí? 585 00:29:55,204 --> 00:29:56,990 >> AUDIÈNCIA: [inaudible] 586 00:29:56,990 --> 00:29:59,010 >> ANDI Peng: Sí, se sent A-- sento lliure, vostè 587 00:29:59,010 --> 00:30:02,318 no han de suportar up-- sensació llibertat per aixecar la veu una mica. 588 00:30:02,318 --> 00:30:08,190 >> AUDIÈNCIA: Per int i és igual 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI Peng: Sí, bé. 590 00:30:10,690 --> 00:30:15,220 >> AUDIÈNCIA: i és menor que la longitud de la matriu. 591 00:30:15,220 --> 00:30:19,630 >> ANDI Peng: Així que tingui en la ment aquí, perquè nosaltres 592 00:30:19,630 --> 00:30:23,060 no tenen una funció que ens diu la longitud d'una matriu, 593 00:30:23,060 --> 00:30:25,790 ja tenim una valor que emmagatzema això. 594 00:30:25,790 --> 00:30:27,920 Oi? 595 00:30:27,920 --> 00:30:31,010 Una altra cosa a tenir en mente-- en una matriu 596 00:30:31,010 --> 00:30:33,940 de nou valors, quins són els índexs? 597 00:30:33,940 --> 00:30:38,720 Diguem que aquesta matriu va ser 0-3. 598 00:30:38,720 --> 00:30:41,500 Vostè veu que l'últim índex és en realitat març. 599 00:30:41,500 --> 00:30:45,530 No és 4, tot i que hi ha quatre valors en la matriu. 600 00:30:45,530 --> 00:30:49,866 >> Així que aquí, hem de tenir molta cura del que la nostra condició per a la longitud 601 00:30:49,866 --> 00:30:50,490 va ser. 602 00:30:50,490 --> 00:30:51,948 >> AUDIÈNCIA: ¿No seria n almenys 1? 603 00:30:51,948 --> 00:30:54,440 ANDI Peng: Va n menys 1, exactament. 604 00:30:54,440 --> 00:30:57,379 Té sentit, per què és n menys 1, tothom? 605 00:30:57,379 --> 00:30:58,920 És perquè les matrius són indexats de zero. 606 00:30:58,920 --> 00:31:02,010 Comencen a 0 i s'executen fins an almenys 1. 607 00:31:02,010 --> 00:31:03,210 Sí, és una mica complicat. 608 00:31:03,210 --> 00:31:03,730 D'ACORD. 609 00:31:03,730 --> 00:31:05,929 I llavors-- 610 00:31:05,929 --> 00:31:08,054 AUDIÈNCIA: Isnt'1 que ja atesos, però, 611 00:31:08,054 --> 00:31:11,400 per no dir "inferior o igual a "i dir" menys? " 612 00:31:11,400 --> 00:31:13,108 >> ANDI Peng: Aquesta és una molt bona pregunta. 613 00:31:13,108 --> 00:31:13,630 Així que, sí. 614 00:31:13,630 --> 00:31:17,410 Però també, la forma en què estem fer efectiu el dret de comprovar, 615 00:31:17,410 --> 00:31:19,120 cal comparar dos valors. 616 00:31:19,120 --> 00:31:21,009 Així que vostè realment vol sortir de la "a" buit. 617 00:31:21,009 --> 00:31:23,050 Perquè si es compara aquest, no vas 618 00:31:23,050 --> 00:31:25,530 tenir res després comparar, no? 619 00:31:25,530 --> 00:31:27,460 Sí. 620 00:31:27,460 --> 00:31:29,297 Així que i ++. 621 00:31:29,297 --> 00:31:30,380 Anem a afegir els nostres suports a. 622 00:31:30,380 --> 00:31:30,880 Vaja. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Gran. 625 00:31:34,710 --> 00:31:39,117 Així que tenim el començament del nostre bucle exterior. 626 00:31:39,117 --> 00:31:41,450 Així que ara que probablement volem crear una variable per mantenir 627 00:31:41,450 --> 00:31:43,085 pista del valor més petit, no? 628 00:31:43,085 --> 00:31:45,751 Algú vol donar-me la línia de codi que faria això? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Què necessitem si anem voler emmagatzemar alguna cosa? 631 00:31:53,570 --> 00:31:55,047 >> Dreta. 632 00:31:55,047 --> 00:31:57,630 Potser un millor nom perquè seria ser-- "temp" totalment works-- 633 00:31:57,630 --> 00:32:00,655 potser una més ben anomenat seria, si volem que el value-- més petit 634 00:32:00,655 --> 00:32:01,624 >> AUDIÈNCIA: Min. 635 00:32:01,624 --> 00:32:02,790 ANDI Peng: min, aquí anem. 636 00:32:02,790 --> 00:32:05,230 min seria bo. 637 00:32:05,230 --> 00:32:08,340 I aquí, què fem que inicialitzar a? 638 00:32:08,340 --> 00:32:09,620 Això és una mica complicat. 639 00:32:09,620 --> 00:32:13,580 A causa que en aquest moment en el a partir d'aquesta matriu, 640 00:32:13,580 --> 00:32:15,730 vostè no ha mirat res, oi? 641 00:32:15,730 --> 00:32:19,200 Llavors, què, de forma automàtica, si estem només en i és igual a 0, 642 00:32:19,200 --> 00:32:22,302 ¿Què volem per inicialitzar el nostre primer valor mínim de? 643 00:32:22,302 --> 00:32:22,802 AUDIÈNCIA: i. 644 00:32:22,802 --> 00:32:24,790 ANDI Peng: i, exactament. 645 00:32:24,790 --> 00:32:27,040 Christabel, per què volem per inicialitzar a i? 646 00:32:27,040 --> 00:32:28,510 >> AUDIÈNCIA: Perquè, bé, estem començant amb 0. 647 00:32:28,510 --> 00:32:31,660 Així que perquè no tenim res per comparar a, el mínim va a acabar sent 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI Peng: Exactament. 649 00:32:32,451 --> 00:32:34,400 Així que ella és exactament correcte. 650 00:32:34,400 --> 00:32:36,780 Com que tenim en realitat no mirat res encara, 651 00:32:36,780 --> 00:32:38,680 no sabem quin és el nostre valor mínim és. 652 00:32:38,680 --> 00:32:41,960 Volem simplement inicialitzar a I, que, actualment, és aquí. 653 00:32:41,960 --> 00:32:44,750 I a mesura que continuem baixar aquesta matriu, 654 00:32:44,750 --> 00:32:48,122 veurem que, amb cada passi addicional, i increments. 655 00:32:48,122 --> 00:32:49,830 I així, en aquest punt, i probablement va 656 00:32:49,830 --> 00:32:52,329 a voler ser el mínim, perquè va a ser el que sigui 657 00:32:52,329 --> 00:32:54,520 és el principi de la matriu sense classificar. 658 00:32:54,520 --> 00:32:55,270 Fresc. 659 00:32:55,270 --> 00:32:58,720 >> Així que ara volem afegir un bucle for aquí això és 660 00:32:58,720 --> 00:33:03,225 va recórrer el sense classificar, o la resta d'aquesta sèrie. 661 00:33:03,225 --> 00:33:05,808 Algú vol donar-me un línia de codi que faria això? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- Què necessitem ací baix? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 ¿Què passarà en aquest bucle for? 666 00:33:18,820 --> 00:33:19,465 Sí. 667 00:33:19,465 --> 00:33:21,590 AUDIÈNCIA: Així que ens agradaria tenir un nombre enter diferent, 668 00:33:21,590 --> 00:33:25,080 perquè ens estem quedant per la resta de la matriu en lloc de la i, així que potser 669 00:33:25,080 --> 00:33:25,760 j. 670 00:33:25,760 --> 00:33:27,301 >> ANDI Peng: Sí, j sona bé per a mi. 671 00:33:27,301 --> 00:33:27,850 És igual? 672 00:33:27,850 --> 00:33:33,930 >> AUDIÈNCIA: Llavors seria i + 1, perquè estàs començant en el següent valor. 673 00:33:33,930 --> 00:33:40,395 I després a la end-- així que de nou, j és menys de n menys 1, i després j ++. 674 00:33:40,395 --> 00:33:41,103 ANDI Peng: Gran. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> I després aquí, anem a voler per comprovar si es compleix la nostra condició, 677 00:33:52,750 --> 00:33:53,250 Oi? 678 00:33:53,250 --> 00:33:55,740 Perquè vols canviar el valor mínim 679 00:33:55,740 --> 00:33:58,700 si en realitat és més petit que el que vostè està comparant a, oi? 680 00:33:58,700 --> 00:34:01,146 Llavors, què anem a voler en aquesta llista? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Comproveu. 683 00:34:04,897 --> 00:34:06,730 Quin tipus de declaració estem probablement anem 684 00:34:06,730 --> 00:34:08,389 tu voleu utilitzar si que vulgueu comprovar alguna cosa? 685 00:34:08,389 --> 00:34:09,360 >> AUDIÈNCIA: Una sentència if. 686 00:34:09,360 --> 00:34:10,485 >> ANDI Peng: Una sentència if. 687 00:34:10,485 --> 00:34:13,155 Així que si: i el que serà la condició que volem a l'interior 688 00:34:13,155 --> 00:34:13,988 de la nostra sentència if? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> AUDIÈNCIA: Si el valor de j és menor que el valor de I-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI Peng: Exactament. 692 00:34:24,600 --> 00:34:27,480 Així que si: pel que aquesta sèrie es diu "matriu". 693 00:34:27,480 --> 00:34:27,980 Gran. 694 00:34:27,980 --> 00:34:30,465 Així que si array-- què va ser això? 695 00:34:30,465 --> 00:34:31,090 Digues-ho de nou. 696 00:34:31,090 --> 00:34:39,590 >> AUDIÈNCIA: Si array-j és menor que matriu-i, llavors canviaria el min. 697 00:34:39,590 --> 00:34:41,590 Així que el mínim seria j. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI Peng: Té sentit? 700 00:34:47,249 --> 00:34:48,670 D'ACORD. 701 00:34:48,670 --> 00:34:52,929 I ara aquí, en realitat desitgi implementar el canvi, oi? 702 00:34:52,929 --> 00:34:58,285 Així que recorda, en la conferència, que David, quan ell estava tractant de canviar ell-- del que era 703 00:34:58,285 --> 00:34:59,996 suc de taronja it-- i milk-- 704 00:34:59,996 --> 00:35:01,150 >> AUDIÈNCIA: Això era fastigós. 705 00:35:01,150 --> 00:35:02,816 >> ANDI Peng: Sí, això era una mica brut. 706 00:35:02,816 --> 00:35:05,310 Però va ser una bona bonica concepte de temps demostrant. 707 00:35:05,310 --> 00:35:08,430 Així que pensa en els seus valors aquí. 708 00:35:08,430 --> 00:35:10,794 Tens una matriu de minuts, una gran varietat de i, 709 00:35:10,794 --> 00:35:12,460 o el que estàvem tractant de canviar aquí. 710 00:35:12,460 --> 00:35:15,310 I és probable que no es pot abocar en entre si, al mateix temps, oi? 711 00:35:15,310 --> 00:35:17,180 Així que, què anem a haver de crear aquí 712 00:35:17,180 --> 00:35:19,126 per tal d'intercanviar correctament els valors? 713 00:35:19,126 --> 00:35:19,820 >> AUDIÈNCIA: Una variable temporal. 714 00:35:19,820 --> 00:35:21,370 >> ANDI Peng: Una variable temporal. 715 00:35:21,370 --> 00:35:22,570 Així que farem int temp. 716 00:35:22,570 --> 00:35:25,681 Mira, això seria una millor temps A-- Whoa, què va ser això? 717 00:35:25,681 --> 00:35:26,180 D'ACORD. 718 00:35:26,180 --> 00:35:29,800 Així que això hauria estat una millor temps per nomenar el "temp." variables 719 00:35:29,800 --> 00:35:30,730 Així que farem int temp. 720 00:35:30,730 --> 00:35:32,563 Què farem setembre temp igual a aquí? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 AUDIÈNCIA: Min? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI Peng: És una mica complicat. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 En realitat, no importa al final. 727 00:35:44,880 --> 00:35:47,690 No importa el que per a que triï de canviar de 728 00:35:47,690 --> 00:35:50,862 sempre que vostè està fent segur que ets fer el seguiment del que estàs intercanviant. 729 00:35:50,862 --> 00:35:52,250 >> AUDIÈNCIA: Podria ser array-i. 730 00:35:52,250 --> 00:35:53,666 >> ANDI Peng: Sí, farem array-i. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 I llavors quin és la següent línia de codi que volem tenir aquí? 733 00:35:59,305 --> 00:36:00,680 AUDIÈNCIA: array-i és igual array-j. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI Peng: I finalment? 736 00:36:08,070 --> 00:36:12,070 AUDIÈNCIA: array-j és igual array-i. 737 00:36:12,070 --> 00:36:14,525 AUDIÈNCIA: O array-j iguals -array temp-- o, temp. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI Peng: OK. 740 00:36:19,430 --> 00:36:21,510 Així que anem a executar això i veure si es va a treballar. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 On està això passi? 743 00:36:39,335 --> 00:36:40,210 Oh, això és un problema. 744 00:36:40,210 --> 00:36:44,320 Mira, en la línia 40, que estem tractant d'usar matriu de j? 745 00:36:44,320 --> 00:36:47,022 Però, d'on j només existeixen en? 746 00:36:47,022 --> 00:36:48,402 >> AUDIÈNCIA: En el bucle for. 747 00:36:48,402 --> 00:36:49,110 ANDI Peng: Correcte. 748 00:36:49,110 --> 00:36:51,730 Llavors, què haurem de fer? 749 00:36:51,730 --> 00:36:53,170 >> AUDIÈNCIA: Definir fora ell-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 AUDIÈNCIA: Sí, suposo que tens utilitzar una altra sentència if, oi? 752 00:37:00,610 --> 00:37:05,230 Així com, si el minimum-- bé, deixa pensar. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Peng: Nois, tractar per fer una ullada de Let 755 00:37:09,990 --> 00:37:11,270 veiem, el que és una cosa que podem fer aquí? 756 00:37:11,270 --> 00:37:11,811 >> AUDIÈNCIA: OK. 757 00:37:11,811 --> 00:37:15,900 Així que si el mínim no és igual a j-- pel que si el mínim és encara jo-- 758 00:37:15,900 --> 00:37:17,570 llavors no hauríem de canviar. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI Peng: ¿Això potser i? 761 00:37:24,712 --> 00:37:25,920 Què vol dir aquí? 762 00:37:25,920 --> 00:37:30,494 >> AUDIÈNCIA: O sí, si el mínim no és igual a I, si. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI Peng: OK. 765 00:37:40,210 --> 00:37:42,040 Bé, això resol, una cosa així, els nostres problemes. 766 00:37:42,040 --> 00:37:47,265 Però això encara no resol el problema del que passa si j-- des j 767 00:37:47,265 --> 00:37:49,890 no existeix fora d'ella, el que Com se'ns vol fer amb ell? 768 00:37:49,890 --> 00:37:50,698 Declarar fora? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Anem a tractar d'executar aquest. 771 00:38:02,730 --> 00:38:04,435 UH oh. 772 00:38:04,435 --> 00:38:06,200 La nostra espècie no està funcionant. 773 00:38:06,200 --> 00:38:10,060 >> Com es pot veure, la nostra inicial matriu tenia aquests valors. 774 00:38:10,060 --> 00:38:14,800 I després que hauria de tenir estat en 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 No està funcionant. 776 00:38:15,530 --> 00:38:16,030 Ahh. 777 00:38:16,030 --> 00:38:17,184 Què fem? 778 00:38:17,184 --> 00:38:17,850 AUDIÈNCIA: Depuració. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI Peng: Molt bé, podem provar això. 781 00:38:23,370 --> 00:38:25,030 Podem depurar. 782 00:38:25,030 --> 00:38:26,042 Reduir una mica. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Anem a posar el nostre punt d'interrupció. 785 00:38:33,656 --> 00:38:37,280 Anem com-- acord. 786 00:38:37,280 --> 00:38:40,444 >> Així doncs ja sabem que aquestes línies, 15 a 22, 787 00:38:40,444 --> 00:38:43,610 es working-- perquè tot el que estic fent és simplement iterar a través i printing-- 788 00:38:43,610 --> 00:38:45,406 Puc seguir endavant i saltar això. 789 00:38:45,406 --> 00:38:47,280 Anem a començar en la línia 25. 790 00:38:47,280 --> 00:38:48,712 Oop, deixa desfer-me d'això. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> AUDIÈNCIA: Llavors el punt d'interrupció on comença la depuració? 793 00:38:54,057 --> 00:38:54,890 ANDI Peng: O parades. 794 00:38:54,890 --> 00:38:55,670 AUDIÈNCIA: O parades. 795 00:38:55,670 --> 00:38:55,930 ANDI Peng: Sí. 796 00:38:55,930 --> 00:38:58,640 Podeu configurar diversos punts d'interrupció i només pot saltar d'una a una altra. 797 00:38:58,640 --> 00:39:01,590 Però en aquest cas no sabem on l'error està succeint. 798 00:39:01,590 --> 00:39:03,780 Així que només volem començar de dalt a baix. 799 00:39:03,780 --> 00:39:05,020 Sí. 800 00:39:05,020 --> 00:39:05,550 D'ACORD. 801 00:39:05,550 --> 00:39:08,460 >> Així que aquesta línia d'aquí, podem intervenir. 802 00:39:08,460 --> 00:39:11,499 Es pot veure aquí baix, tenim una matriu. 803 00:39:11,499 --> 00:39:13,290 Aquests són els valors que es troben a la matriu. 804 00:39:13,290 --> 00:39:16,360 Veus això, com l'índex 0, es correspon a la value-- oh, 805 00:39:16,360 --> 00:39:17,526 Vaig a tractar de fer un zoom. 806 00:39:17,526 --> 00:39:20,650 Malauradament, és molt difícil a veure- a l'índex de matriu 0, 807 00:39:20,650 --> 00:39:24,090 tenim un valor de 4 i a continuació, així successivament i així successivament. 808 00:39:24,090 --> 00:39:25,670 Tenim les nostres variables locals. 809 00:39:25,670 --> 00:39:28,570 Ara mateix i és igual a 0, el que volem que sigui. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> I així seguirem pas a pas a través. 812 00:39:33,690 --> 00:39:36,850 La nostra mínim és igual a 0, que també volem que sigui. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 I llavors entrem en el nostre segon per llaç, si array-j és menor de gamma-i, 815 00:39:45,560 --> 00:39:46,380 que no ho era. 816 00:39:46,380 --> 00:39:48,130 Així que vas veure com que ometen sobre això? 817 00:39:48,130 --> 00:39:52,430 >> AUDIÈNCIA: Llavors, si el cas mínim, tot això-- no hauria que 818 00:39:52,430 --> 00:39:55,424 estar dins de la primera bucle for? 819 00:39:55,424 --> 00:39:57,340 ANDI Peng: No, perquè vostè encara vol provar. 820 00:39:57,340 --> 00:40:00,329 Vols fer una comparació cada temps, fins i tot després d'executar a través d'ell. 821 00:40:00,329 --> 00:40:02,620 No només vol fer-ho en el primer pas. 822 00:40:02,620 --> 00:40:05,240 Vols fer-ho amb cada passada addicional de nou. 823 00:40:05,240 --> 00:40:07,198 ¿Així que vols comprovar seva condició interior. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Així que només anem a seguir corrent per aquí. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Et vaig a donar una pista nois. 828 00:40:18,420 --> 00:40:23,910 Té a veure amb el fet que quan vostè està comprovant la seva condicional, 829 00:40:23,910 --> 00:40:26,600 vostè no està comprovant per a l'índex correcte. 830 00:40:26,600 --> 00:40:32,510 Així que ara vostè està comprovant índex de matriu de j és menys de matriu 831 00:40:32,510 --> 00:40:33,970 Índex de i. 832 00:40:33,970 --> 00:40:36,580 Però, què estàs fent cap amunt en el principi del bucle for? 833 00:40:36,580 --> 00:40:38,260 No estàs configurant j igual a i? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Sí, pel que pot en realitat sortir del depurador aquí. 836 00:40:45,415 --> 00:40:47,040 Així que donem una ullada a la nostra pseudocodi. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 Para-- anem a començarà a les i és igual a 0. 839 00:40:52,580 --> 00:40:54,760 Anirem fins an almenys 1. 840 00:40:54,760 --> 00:40:58,040 Anem a veure, què tenim aquest dret? 841 00:40:58,040 --> 00:40:59,580 Sí, això era correcte. 842 00:40:59,580 --> 00:41:02,080 >> Així que aquí dins, estem crearà un valor mínim 843 00:41:02,080 --> 00:41:03,630 i establir que igual a i. 844 00:41:03,630 --> 00:41:04,950 ¿Vam fer això? 845 00:41:04,950 --> 00:41:06,270 Sí, ho va fer. 846 00:41:06,270 --> 00:41:10,430 Ara en el nostre interior per bucle, estem farà j és igual a i n almenys 1. 847 00:41:10,430 --> 00:41:11,950 ¿Vam fer això? 848 00:41:11,950 --> 00:41:15,540 De fet, ho vam fer. 849 00:41:15,540 --> 00:41:19,922 >> Així que, però, què estem comparant aquí? 850 00:41:19,922 --> 00:41:20,925 >> AUDIÈNCIA: j més 1. 851 00:41:20,925 --> 00:41:21,716 ANDI Peng: Exactament. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 I llavors vostè va a voler establir seva mínima igual a j plus 1 també. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Així que em vaig anar a través d'aquesta realitat ràpidament. 856 00:41:32,640 --> 00:41:36,190 Entenen vostès per què és j més 1? 857 00:41:36,190 --> 00:41:36,890 D'ACORD. 858 00:41:36,890 --> 00:41:40,700 >> Així que en el seu conjunt, en el primer pas a través, 859 00:41:40,700 --> 00:41:44,850 el bucle for, per int i és igual a 0, anem a 860 00:41:44,850 --> 00:41:46,740 assumeix això no s'ha canviat encara. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 Tenim una gran varietat de, per complet, només quatre elements no ordenats, oi? 863 00:41:56,760 --> 00:42:00,760 Així que volem inicialitzar i igual a 0. 864 00:42:00,760 --> 00:42:03,650 I em va acaba executar aquest bucle. 865 00:42:03,650 --> 00:42:08,560 I així, en la primera passada, anem per inicialitzar una variable anomenada "min" 866 00:42:08,560 --> 00:42:11,245 que també és igual a I, perquè no tenim un valor mínim. 867 00:42:11,245 --> 00:42:12,870 Així que aquesta és actualment igual a 0 també. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 I després anem a passar. 870 00:42:17,640 --> 00:42:19,270 I volem repetir. 871 00:42:19,270 --> 00:42:22,900 Ara que hem trobat el que el nostre mínima És a dir, volem recórrer 872 00:42:22,900 --> 00:42:25,190 de nou per veure si es tracta de comparar, oi? 873 00:42:25,190 --> 00:42:40,440 Així j, aquí, es va a la igualtat d'i, que és 0. 874 00:42:40,440 --> 00:42:46,320 I després, si arsenal j més i, que és el que està al costat una altra vegada, com menys 875 00:42:46,320 --> 00:42:49,270 del que el seu mínim actual valor és, que desitja intercanviar. 876 00:42:49,270 --> 00:42:56,850 >> Així que anem a dir que hem té, com, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 En aquest moment, i és igual a 0 i j és igual a 0. 878 00:43:01,610 --> 00:43:05,210 I aquest és el nostre valor mínim. 879 00:43:05,210 --> 00:43:09,950 Si varietat j-plus jo-- pel que si el això és després de la qual estem veient 880 00:43:09,950 --> 00:43:13,450 és més gran que l'anterior, que es convertirà en el mínim. 881 00:43:13,450 --> 00:43:18,120 >> Així que aquí veiem que 5 no és menys que això. 882 00:43:18,120 --> 00:43:19,730 Així que va a estar 5. 883 00:43:19,730 --> 00:43:23,580 Veiem que 1 és menor que 2, oi? 884 00:43:23,580 --> 00:43:32,970 Així que ara que sabem que el nostre mínim és serà el valor de l'índex en 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Sí? 886 00:43:34,030 --> 00:43:39,170 I després quan arribes aquí, vostè pot canviar els valors correctes. 887 00:43:39,170 --> 00:43:42,610 >> Així que quan vostès simplement van tenir la j abans, no estaven buscant en el 888 00:43:42,610 --> 00:43:43,260 després d'ella. 889 00:43:43,260 --> 00:43:44,520 Estaves mirant el mateix valor, el qual 890 00:43:44,520 --> 00:43:46,290 és per això que no estava fent res. 891 00:43:46,290 --> 00:43:49,721 ¿Això té sentit per a tothom, per això necessitem que mai 1 allà? 892 00:43:49,721 --> 00:43:50,220 D'ACORD. 893 00:43:50,220 --> 00:43:53,345 Ara anem a executar a través d'ell per fer Assegureu-vos que la resta del codi és correcte. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Per què és que això passi? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ah, és el mínim aquí. 898 00:44:16,364 --> 00:44:17,780 Estàvem comparant el valor incorrecte. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 Oh no. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Ah, sí, aquí estàvem el bescanvi dels valors erronis també. 903 00:44:33,482 --> 00:44:34,940 A causa de que estàvem buscant en i i j. 904 00:44:34,940 --> 00:44:36,440 Aquests són els que marxàvem. 905 00:44:36,440 --> 00:44:39,160 En realitat, volem canviar la mínim, el mínim actual, 906 00:44:39,160 --> 00:44:40,550 amb el que l'exterior és. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 I com vostès poden veure a baix aquí, tenim un arranjament ordenat. 909 00:45:05,402 --> 00:45:07,110 Simplement tenia a veure amb el fet que quan 910 00:45:07,110 --> 00:45:09,350 ens anàvem el valors que estàvem comparant, 911 00:45:09,350 --> 00:45:11,226 que no estàvem buscant en els valors correctes. 912 00:45:11,226 --> 00:45:13,850 Estàvem buscant en el mateix aquí, en realitat no és el canvi. 913 00:45:13,850 --> 00:45:17,135 Vostè ha de mirar l'un al costat a ell i després es pot canviar. 914 00:45:17,135 --> 00:45:19,260 Així que això és el que era una mena de molestant el nostre codi abans. 915 00:45:19,260 --> 00:45:22,460 I el que vaig fer aquí ho és tot el depurador podria haver fet per a tu 916 00:45:22,460 --> 00:45:23,810 Jo només ho va fer al tauler, perquè és més fàcil 917 00:45:23,810 --> 00:45:26,320 per veure en lloc de tractar per apropar el depurador. 918 00:45:26,320 --> 00:45:29,391 ¿Això té sentit per a tothom? 919 00:45:29,391 --> 00:45:29,890 Fresc. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Tot bé. 922 00:45:35,410 --> 00:45:41,070 Podem passar a parlar de notació asimptòtica, que 923 00:45:41,070 --> 00:45:44,580 és només una forma elegant de dir la temps d'execució de tots aquests tipus. 924 00:45:44,580 --> 00:45:47,650 Així que sé David, a la conferència, referit als temps d'execució. 925 00:45:47,650 --> 00:45:52,124 I se'n va anar per tota la fórmula de com calcular els temps d'execució. 926 00:45:52,124 --> 00:45:53,040 No et preocupis per això. 927 00:45:53,040 --> 00:45:54,660 Si vostè és realment curiós sobre com funciona, 928 00:45:54,660 --> 00:45:55,810 no dubti en parlar amb mi després de la secció. 929 00:45:55,810 --> 00:45:57,560 Podem caminar a través d' les fórmules junts. 930 00:45:57,560 --> 00:46:00,689 Però tots vostès tenen per realment saber és que n al quadrat més de 2 931 00:46:00,689 --> 00:46:01,980 és el mateix que n al quadrat. 932 00:46:01,980 --> 00:46:04,710 A causa que el nombre més gran, l'exponent, més creix. 933 00:46:04,710 --> 00:46:06,590 I així, per als nostres propòsits, tots ens preocupem per 934 00:46:06,590 --> 00:46:09,470 és aquest nombre gegant que està creixent. 935 00:46:09,470 --> 00:46:13,340 >> Llavors, quin és el millor dels casos temps d'execució de l'ordenació per selecció? 936 00:46:13,340 --> 00:46:15,830 Si vostè va a tenir per recórrer una llista 937 00:46:15,830 --> 00:46:18,712 i després recórrer la resta de la llista, 938 00:46:18,712 --> 00:46:20,420 Quantes vegades es vostè va a probablement 939 00:46:20,420 --> 00:46:24,612 en el pitjor cas-- al millor dels casos, sorry-- executar a través de? 940 00:46:24,612 --> 00:46:27,070 Potser la millor pregunta és preguntar, quin és el pitjor dels casos 941 00:46:27,070 --> 00:46:28,153 temps d'execució de l'ordenació per selecció. 942 00:46:28,153 --> 00:46:29,366 AUDIÈNCIA: n al quadrat. 943 00:46:29,366 --> 00:46:30,740 ANDI Peng: Ha n al quadrat, dreta. 944 00:46:30,740 --> 00:46:36,986 Així que una manera fàcil de pensar en això és com, qualsevol moment tens dues niat per als bucles, 945 00:46:36,986 --> 00:46:38,110 que serà n al quadrat. 946 00:46:38,110 --> 00:46:40,386 Perquè no només és vostè corrent a través un cop més, 947 00:46:40,386 --> 00:46:42,260 vostè ha de tornar volta i córrer a través d'ell 948 00:46:42,260 --> 00:46:44,980 un cop a l'interior de cada valor. 949 00:46:44,980 --> 00:46:48,640 Així que en aquest cas, s'està executant n temps n al quadrat, que aquests: ho sento, 950 00:46:48,640 --> 00:46:50,505 n vegades n, que és igual a n al quadrat. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> I espècie és també una mica únic en el sentit 953 00:46:56,360 --> 00:46:59,774 que no importa si aquests valors ja estan en ordre. 954 00:46:59,774 --> 00:47:01,440 Encara va a executar a través de totes maneres. 955 00:47:01,440 --> 00:47:03,872 Diguem que aquest va ser d'1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Independentment de si era o no en fi, encara hauria córrer a través de 957 00:47:07,080 --> 00:47:08,620 i encara comprovat el valor mínim. 958 00:47:08,620 --> 00:47:10,100 Hi hauria fet el mateix nombre de xecs 959 00:47:10,100 --> 00:47:12,780 cada vegada, fins i tot si en realitat no tocar res. 960 00:47:12,780 --> 00:47:16,940 >> Així doncs, en aquest cas, el millor i el pitjor temps d'execució són en realitat equivalents. 961 00:47:16,940 --> 00:47:19,160 Així que el temps d'execució esperat d'ordenació per selecció, 962 00:47:19,160 --> 00:47:23,790 que designem pel símbol de theta, theta, en aquest cas, 963 00:47:23,790 --> 00:47:24,790 també seria n al quadrat. 964 00:47:24,790 --> 00:47:26,480 Els tres d'ells serien n al quadrat. 965 00:47:26,480 --> 00:47:29,653 Està clar per què tothom la durada és n al quadrat? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Tot bé. 968 00:47:33,980 --> 00:47:39,120 Així que només vaig a córrer ràpidament per la resta dels gèneres. 969 00:47:39,120 --> 00:47:41,137 L'algoritme per bombolla sort-- recordi, 970 00:47:41,137 --> 00:47:43,220 aquesta va ser la primera David es va acostar a la conferència. 971 00:47:43,220 --> 00:47:46,000 Essencialment, vostè camina a través de la llista sencera 972 00:47:46,000 --> 00:47:48,950 i que acaba de swap-- comparar els dos alhora. 973 00:47:48,950 --> 00:47:51,350 I si un és més gran, el que només els intercanviar. 974 00:47:51,350 --> 00:47:53,590 Així que si aquests són majors, que canviaria. 975 00:47:53,590 --> 00:47:56,180 Tinc oficial aquí. 976 00:47:56,180 --> 00:47:59,100 >> Així que anem a dir que tenia 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Es podria comparar el 8 i un 6. 978 00:48:00,571 --> 00:48:01,570 Vostè necessitaria per intercanviar-les. 979 00:48:01,570 --> 00:48:02,610 Es podria comparar el 8 i un 4. 980 00:48:02,610 --> 00:48:03,609 Vostè necessitaria per intercanviar-les. 981 00:48:03,609 --> 00:48:07,000 Si ha de canviar el 8 i el 2, canviï ells també. 982 00:48:07,000 --> 00:48:10,760 Així doncs, en aquest sentit, es pot veure, jugat a terme durant un llarg període de temps, 983 00:48:10,760 --> 00:48:13,730 com els valors de tipus de bombolla els extrems, la qual cosa és per això que en diuen 984 00:48:13,730 --> 00:48:15,320 ordenament de bombolla. 985 00:48:15,320 --> 00:48:19,950 >> Ens agradaria simplement executar a través de nou en la nostra segona passada, i el nostre tercer pas, 986 00:48:19,950 --> 00:48:21,150 i el nostre quart passi. 987 00:48:21,150 --> 00:48:25,820 Essencialment, bombolla espècie només s'executa fins que no faci més swaps. 988 00:48:25,820 --> 00:48:31,109 Així que en aquest sentit, això és només el pseudocodi general per a això. 989 00:48:31,109 --> 00:48:32,650 No es preocupi, aquests seran tots en línia. 990 00:48:32,650 --> 00:48:34,990 No hem d'anar realment sobre això. 991 00:48:34,990 --> 00:48:38,134 >> Acabem inicialitzem un comptador variable que comença en 0. 992 00:48:38,134 --> 00:48:39,800 I recórrer tota la matriu. 993 00:48:39,800 --> 00:48:43,420 I si un valor és-- si això valor és més gran que aquest valor, 994 00:48:43,420 --> 00:48:44,610 ves per intercanviar-les. 995 00:48:44,610 --> 00:48:46,860 I llavors no ets més que seguirà endavant. 996 00:48:46,860 --> 00:48:47,970 I vas a explicar. 997 00:48:47,970 --> 00:48:50,845 I només continuarem fent això mentre que el comptador és més gran 998 00:48:50,845 --> 00:48:53,345 que 0, el que significa que cada vegada que ha de canviar, 999 00:48:53,345 --> 00:48:55,220 vostè sap que vol anar esquena i pots tornar a intentar-ho. 1000 00:48:55,220 --> 00:48:59,510 Vostè vol mantenir la comprovació fins que vostè sàpiga que vostè no ha de canviar ja. 1001 00:48:59,510 --> 00:49:05,570 >> Llavors, què són els millors i pitjors cas els motors d'execució d'ordenament de bombolla? 1002 00:49:05,570 --> 00:49:09,300 I hint-- això és realment diferent des de la selecció del tipus en el sentit 1003 00:49:09,300 --> 00:49:11,810 que aquestes dues respostes no són iguals. 1004 00:49:11,810 --> 00:49:14,709 Penseu en el que succeiria en un cas si ja es va solucionar. 1005 00:49:14,709 --> 00:49:16,500 I pensar en el Què passaria si fos 1006 00:49:16,500 --> 00:49:18,372 en el cas en què no es va solucionar. 1007 00:49:18,372 --> 00:49:20,580 I vostè pot classe de córrer a través de per què està succeint. 1008 00:49:20,580 --> 00:49:22,954 Et vaig a donar els nois, com, 30 segon per pensar en això. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> D'ACORD. 1011 00:49:53,540 --> 00:49:57,462 Algú té una pista sobre el que el pitjor dels casos el temps d'execució de la bombolla de tipus és? 1012 00:49:57,462 --> 00:49:57,962 Sí. 1013 00:49:57,962 --> 00:50:07,810 >> AUDIÈNCIA: Seria, com, n vegades n almenys 1 o alguna cosa així? 1014 00:50:07,810 --> 00:50:10,650 Igual que, cada vegada que s'executa, és només, com, un intercanvi menys 1015 00:50:10,650 --> 00:50:10,960 que tot el que era. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI Peng: Sí, així vostè és del tot encertada. 1017 00:50:12,668 --> 00:50:15,940 I aquest és un cas en què el resposta era en realitat més complexa 1018 00:50:15,940 --> 00:50:17,240 que el que hem de donar. 1019 00:50:17,240 --> 00:50:19,772 Així que va a run-- estic va a esborrar tot això aquí. 1020 00:50:19,772 --> 00:50:20,480 És bo tothom? 1021 00:50:20,480 --> 00:50:21,869 Puc esborrar això? 1022 00:50:21,869 --> 00:50:22,368 D'ACORD. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Vostè va a executar a través de n vegades la primera vegada, oi? 1025 00:50:30,320 --> 00:50:33,200 I ells van a executar a través de n almenys 1 la segona vegada, oi? 1026 00:50:33,200 --> 00:50:37,130 I després vas a mantenir va, n mina 2, etcètera. 1027 00:50:37,130 --> 00:50:40,210 David va fer això en una conferència, en què, si s'ha afegit a tots aquests valors, 1028 00:50:40,210 --> 00:50:48,080 vostè aconsegueix una cosa que és com-- yeah-- més de 2, el que redueix essencialment només 1029 00:50:48,080 --> 00:50:49,784 cap avall per n al quadrat. 1030 00:50:49,784 --> 00:50:51,700 Vostè va a obtenir una fracció rar aquí. 1031 00:50:51,700 --> 00:50:53,892 I així, només sé que el n al quadrat sempre 1032 00:50:53,892 --> 00:50:55,350 té prioritat sobre la fracció. 1033 00:50:55,350 --> 00:50:58,450 I així, en aquest cas, el pitjor temps d'execució seria n al quadrat. 1034 00:50:58,450 --> 00:51:00,210 Si va ser en descens ordre, crec, que 1035 00:51:00,210 --> 00:51:02,530 haver de fer un intercanvi cada vegada. 1036 00:51:02,530 --> 00:51:05,170 >> Quin seria, potencialment, el millor temps d'execució cas? 1037 00:51:05,170 --> 00:51:08,580 Diguem, si la llista ja estava per tal, quin seria el temps d'execució? 1038 00:51:08,580 --> 00:51:09,565 >> AUDIÈNCIA: n. 1039 00:51:09,565 --> 00:51:10,690 ANDI Peng: És n, exactament. 1040 00:51:10,690 --> 00:51:11,600 I per què és n? 1041 00:51:11,600 --> 00:51:13,850 AUDIÈNCIA: Com que vostè acaba de haurà de comprovar en cada vegada. 1042 00:51:13,850 --> 00:51:14,770 ANDI Peng: Exactament. 1043 00:51:14,770 --> 00:51:17,150 Així doncs, en la millor execució possible, si aquesta llista ja estava 1044 00:51:17,150 --> 00:51:20,270 sorted-- diguem 1, 2, 3, 4-- vostè acaba de passar, que li tira, 1045 00:51:20,270 --> 00:51:21,720 veuries, oh, tots ells resulten. 1046 00:51:21,720 --> 00:51:22,636 Jo no havia de canviar. 1047 00:51:22,636 --> 00:51:23,370 He acabat. 1048 00:51:23,370 --> 00:51:26,500 Així que en aquest cas, és només n o el nombre de passos que acaba de 1049 00:51:26,500 --> 00:51:29,870 haver de comprovar en la primera llista. 1050 00:51:29,870 --> 00:51:33,990 >> I després, ara colpegem ordenació per inserció, on 1051 00:51:33,990 --> 00:51:39,260 l'algoritme és essencialment divideix en una part ordenada i sense classificar. 1052 00:51:39,260 --> 00:51:42,810 I llavors un per un, els valors no classificats són 1053 00:51:42,810 --> 00:51:46,880 inserit en el seu apropiada posicions en el principi de la llista. 1054 00:51:46,880 --> 00:51:52,120 >> Així, per exemple, tenim una Llista de 3, 5, 2, 6, 4 de nou. 1055 00:51:52,120 --> 00:51:54,750 Sabem que és actualment sense classificar perquè acabem de 1056 00:51:54,750 --> 00:51:57,030 començat mirar-lo. 1057 00:51:57,030 --> 00:52:00,610 Fem una ullada i sabem que el primer valor s'ordena, oi? 1058 00:52:00,610 --> 00:52:04,190 Si només està buscant en una sèrie de mida d'un, vostè sap que està ordenada. 1059 00:52:04,190 --> 00:52:08,230 >> Així que sabem que el altres quatre són sense classificar. 1060 00:52:08,230 --> 00:52:10,980 Anem a través i veiem aquest valor. 1061 00:52:10,980 --> 00:52:11,730 Tornem. 1062 00:52:11,730 --> 00:52:13,130 Veure que el valor de 5? 1063 00:52:13,130 --> 00:52:14,110 Fem una ullada. 1064 00:52:14,110 --> 00:52:15,204 Comparem a 3. 1065 00:52:15,204 --> 00:52:17,870 Sabem que és més gran que 3, pel que sabem que això està solucionat. 1066 00:52:17,870 --> 00:52:22,940 Així que ara sabem que els dos primers s'ordenen i els tres últims no ho són. 1067 00:52:22,940 --> 00:52:24,270 >> Fem una ullada a 2. 1068 00:52:24,270 --> 00:52:25,720 En primer lloc, comprovem amb 5. 1069 00:52:25,720 --> 00:52:26,700 És menor que 5? 1070 00:52:26,700 --> 00:52:27,240 No ho es. 1071 00:52:27,240 --> 00:52:29,510 Així que hem de seguir mirant cap avall. 1072 00:52:29,510 --> 00:52:30,940 Després de comprovar març 2. 1073 00:52:30,940 --> 00:52:31,850 És menor que? 1074 00:52:31,850 --> 00:52:32,350 No. 1075 00:52:32,350 --> 00:52:35,430 Així que ja saps una 2 ha d'ésser inserit a la part davantera i 3 i 5 1076 00:52:35,430 --> 00:52:38,200 tots dos han de ser expulsats. 1077 00:52:38,200 --> 00:52:42,190 Feu això de nou amb 6 i 4. 1078 00:52:42,190 --> 00:52:48,962 I nosaltres només seguim comprovant en essència, on acabem de comprovar, verificar, comprovar. 1079 00:52:48,962 --> 00:52:51,170 I fins que estigui a la dreta posició, tipus de sol 1080 00:52:51,170 --> 00:52:54,890 inserir-lo en la posició correcta, que és on el nom del vi. 1081 00:52:54,890 --> 00:52:59,830 >> Així que això és només l'algorisme, pseudocodi per se, una mena de, 1082 00:52:59,830 --> 00:53:04,990 sobre com anàvem a posar en pràctica un tipus d'inserció. 1083 00:53:04,990 --> 00:53:05,954 Pseudocodi és aquí. 1084 00:53:05,954 --> 00:53:06,620 Tot està en línia. 1085 00:53:06,620 --> 00:53:10,720 No us preocupeu si vostès són tractant de copiar això. 1086 00:53:10,720 --> 00:53:14,500 Així que una vegada més, el mateix pregunta-- seria el millor i el pitjor dels temps d'execució 1087 00:53:14,500 --> 00:53:16,120 per a l'ordenació per inserció? 1088 00:53:16,120 --> 00:53:17,750 És molt similar a l'última pregunta. 1089 00:53:17,750 --> 00:53:20,479 Et vaig a donar els nois, com, 30 segon per pensar en això també. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> OK Algú vol dóna'm el pitjor temps d'execució? 1092 00:53:50,071 --> 00:53:50,570 Sí. 1093 00:53:50,570 --> 00:53:51,490 >> AUDIÈNCIA: n al quadrat. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI Peng: Ha n al quadrat. 1095 00:53:52,573 --> 00:53:53,730 I per què és n al quadrat? 1096 00:53:53,730 --> 00:53:57,562 >> AUDIÈNCIA: Perquè en ordre invers, vostè té 1097 00:53:57,562 --> 00:54:02,619 de passar per n vegades n, que aquests: 1098 00:54:02,619 --> 00:54:03,660 ANDI Peng: Sí, exactament. 1099 00:54:03,660 --> 00:54:06,610 Així mateix que en l'ordenament de bombolla. 1100 00:54:06,610 --> 00:54:08,720 Si aquesta llista està en ordre descendent, ets 1101 00:54:08,720 --> 00:54:11,240 va a haver de comprovar primer una vegada. 1102 00:54:11,240 --> 00:54:13,470 I a continuació, amb cada valor addicional, vostè és 1103 00:54:13,470 --> 00:54:16,390 va a haver de comprovar que en contra cada valor únic, no? 1104 00:54:16,390 --> 00:54:20,290 I així, en conjunt, que faràs un moment n passar a un altre n passen, que 1105 00:54:20,290 --> 00:54:21,750 està n al quadrat. 1106 00:54:21,750 --> 00:54:22,860 I el millor dels casos? 1107 00:54:22,860 --> 00:54:24,360 Sí. 1108 00:54:24,360 --> 00:54:28,840 >> AUDIÈNCIA: n menys 1, ja que el primer ja s'eleva al quadrat. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI Peng: Així, a prop. 1110 00:54:30,270 --> 00:54:31,850 La resposta és en realitat n. 1111 00:54:31,850 --> 00:54:37,189 Perquè si bé la primera és ordenats, pot ser que no es actually-- 1112 00:54:37,189 --> 00:54:38,980 només vam tenir sort, en aquest exemple, que 2 1113 00:54:38,980 --> 00:54:40,930 va passar a ser el número més petit. 1114 00:54:40,930 --> 00:54:43,680 Però això no sempre serà el cas. 1115 00:54:43,680 --> 00:54:48,040 Si 2 ja és ordenat al principi però et veus i hi ha un 1 aquí, 1116 00:54:48,040 --> 00:54:49,144 l'1 va topar. 1117 00:54:49,144 --> 00:54:51,060 I que va a acabar sent copejat de totes maneres. 1118 00:54:51,060 --> 00:54:56,250 >> Així que en el millor dels casos, en realitat és només serà n. 1119 00:54:56,250 --> 00:54:59,090 Si vostè té 1, 2, 3, 4, 5, 6, 7, 8, ets 1120 00:54:59,090 --> 00:55:00,940 va executar a través de aquesta llista tota vegada 1121 00:55:00,940 --> 00:55:03,430 comprovar per veure si tot està bé. 1122 00:55:03,430 --> 00:55:07,390 Estan tots clar en funcionament temps de la selecció així? 1123 00:55:07,390 --> 00:55:09,960 Sé que estic passant aquests realment ràpid. 1124 00:55:09,960 --> 00:55:13,330 Però només sé que si es coneix el conceptes generals, ha de ser bo. 1125 00:55:13,330 --> 00:55:16,070 D'ACORD. 1126 00:55:16,070 --> 00:55:19,790 Així que només et donaré nois potser, com, un minut per parlar amb els seus veïns 1127 00:55:19,790 --> 00:55:21,890 en el que són només algunes de les principals diferències 1128 00:55:21,890 --> 00:55:23,540 entre aquests tipus de classes. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Anem a repassar que aviat. 1131 00:56:25,570 --> 00:56:26,444 AUDIÈNCIA: Oh, OK. 1132 00:56:26,444 --> 00:56:27,320 ANDI Peng: Sí. 1133 00:56:27,320 --> 00:56:28,380 D'ACORD. 1134 00:56:28,380 --> 00:56:33,420 Fresc, anem novament les com a classe. 1135 00:56:33,420 --> 00:56:34,330 D'ACORD. 1136 00:56:34,330 --> 00:56:37,579 Així que això era una mena de pregunta oberta en el sentit 1137 00:56:37,579 --> 00:56:39,120 que hi ha un munt de respostes a ells. 1138 00:56:39,120 --> 00:56:40,746 I anem a repassar alguns d'ells breument. 1139 00:56:40,746 --> 00:56:43,411 Jo només volia aconseguir que els nois pensant en el diferenciat 1140 00:56:43,411 --> 00:56:44,530 els tres tipus de classes. 1141 00:56:44,530 --> 00:56:47,440 I vaig sentir, també, una gran pregunta-- què ordenament per barreja fer? 1142 00:56:47,440 --> 00:56:50,110 Molt bona pregunta, perquè això és el que estem cobrint següent. 1143 00:56:50,110 --> 00:56:52,850 >> Així ordenament per barreja és la un tipus que funciona 1144 00:56:52,850 --> 00:56:56,100 molt diferent als altres tipus. 1145 00:56:56,100 --> 00:56:58,180 Com vostès poden veure- va fer David aquesta demo 1146 00:56:58,180 --> 00:57:01,130 on tenia tot el fresc sorolls de veure com es fusionen 1147 00:57:01,130 --> 00:57:04,010 espècie va córrer, com, infinitament més ràpid que els altres dos tipus? 1148 00:57:04,010 --> 00:57:04,510 D'ACORD. 1149 00:57:04,510 --> 00:57:07,580 Així que això és degut a la fusió classe implementa aquesta bretxa 1150 00:57:07,580 --> 00:57:11,020 i conquerir el concepte que hem parlat molt en conferència. 1151 00:57:11,020 --> 00:57:14,550 En aquest sentit que ens agrada treballar més intel·ligent, no més difícil, quan es divideix 1152 00:57:14,550 --> 00:57:18,120 i conquerir problemes, i trencar- baix, i després posar-los junts, 1153 00:57:18,120 --> 00:57:19,930 bones coses sempre succeeixen. 1154 00:57:19,930 --> 00:57:21,960 >> Així que la forma en què es fusionen treballa espècie essencialment 1155 00:57:21,960 --> 00:57:24,660 és què es divideix una array sense ordenar a la meitat. 1156 00:57:24,660 --> 00:57:26,500 I llavors té dues meitats de matrius. 1157 00:57:26,500 --> 00:57:28,220 I simplement ordena aquestes dues meitats. 1158 00:57:28,220 --> 00:57:31,750 Simplement segueix dividint a la meitat, en mitjana, enmig fins que tot s'ordena 1159 00:57:31,750 --> 00:57:33,680 i després recursivament posa tot junt. 1160 00:57:33,680 --> 00:57:36,550 >> Així que això és molt abstracte. 1161 00:57:36,550 --> 00:57:38,750 Així que això és només una mica de pseudocodi. 1162 00:57:38,750 --> 00:57:41,040 ¿Això té sentit en la forma en què s'està executant? 1163 00:57:41,040 --> 00:57:43,870 Així que diguem que vostè té una arranjament de n elements, oi? 1164 00:57:43,870 --> 00:57:45,450 Si n és menor que 2, pot tornar. 1165 00:57:45,450 --> 00:57:49,040 Perquè vostè sap que si hi ha només una cosa, ha de ser ordenada. 1166 00:57:49,040 --> 00:57:52,600 Si no, s'ordena la meitat esquerra, i després ordenar la meitat dreta, 1167 00:57:52,600 --> 00:57:54,140 i després combinar. 1168 00:57:54,140 --> 00:57:56,979 >> Així, mentre que es veu molt fàcil, en la realitat, pensant que és 1169 00:57:56,979 --> 00:58:00,270 una mica difícil. Perquè vostè és com, bé, això és una cosa que s'executa en si mateix. 1170 00:58:00,270 --> 00:58:00,769 Oi? 1171 00:58:00,769 --> 00:58:02,430 S'executa en si mateix. 1172 00:58:02,430 --> 00:58:05,479 Així que en aquest sentit, David va tocar sobre la recursivitat a classe. 1173 00:58:05,479 --> 00:58:07,270 I això és un concepte parlarem més. 1174 00:58:07,270 --> 00:58:11,430 És que això, aquestes dues línies aquí, en realitat és només el programa 1175 00:58:11,430 --> 00:58:13,860 dient que s'executi en si amb diferent entrada. 1176 00:58:13,860 --> 00:58:17,230 Així que en lloc de córrer en si amb la totalitat de n elements, 1177 00:58:17,230 --> 00:58:20,530 es pot descompondre en el meitat esquerra i la meitat dreta 1178 00:58:20,530 --> 00:58:22,680 i després tornar a executar. 1179 00:58:22,680 --> 00:58:26,050 >> I després veurem visualment, perquè sóc un aprenent visual. 1180 00:58:26,050 --> 00:58:27,270 Funciona millor per a mi. 1181 00:58:27,270 --> 00:58:29,890 Així que anem a veure un exemple visual aquí. 1182 00:58:29,890 --> 00:58:36,237 >> Diguem que tenim una matriu, de sis elements, 3, 5, 2, 6, 4, 1, no ordenats. 1183 00:58:36,237 --> 00:58:37,820 Molt bé, hi ha molt en aquesta pàgina. 1184 00:58:37,820 --> 00:58:43,179 Així que si vostès poden mirar el primer pas aquí, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 es pot dividir per la meitat. 1186 00:58:44,220 --> 00:58:45,976 Vostè té 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Vostè sap que aquests aren't-- vostè no sé si estan ordenats o no, 1188 00:58:48,850 --> 00:58:52,517 de manera que mantenir el seu desglossament, al mig, al mig, al mig, fins que finalment, 1189 00:58:52,517 --> 00:58:53,600 només té un element. 1190 00:58:53,600 --> 00:58:56,790 I un element sempre està ordenada, oi? 1191 00:58:56,790 --> 00:59:01,560 >> Així que sabem que 3, 5, 2, 4, 6, 1, per si mateixos, són ordenats. 1192 00:59:01,560 --> 00:59:05,870 I ara podem tornar a posar-los junts. 1193 00:59:05,870 --> 00:59:07,510 Així sabem que el 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Posem les juntes. 1195 00:59:08,510 --> 00:59:09,617 Sabem que és ordenada. 1196 00:59:09,617 --> 00:59:10,450 Els 2 segueix allà. 1197 00:59:10,450 --> 00:59:11,830 Podem posar el 4 i el 6 junts. 1198 00:59:11,830 --> 00:59:13,996 Sabem que això es va solucionar, així que vam posar que junts. 1199 00:59:13,996 --> 00:59:14,940 I l'1 és allà. 1200 00:59:14,940 --> 00:59:18,720 >> I llavors vostè acaba de veure aquestes dues meitats aquí. 1201 00:59:18,720 --> 00:59:21,300 Vostè té el 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Només pot comparar la a partir de tot. 1203 00:59:23,465 --> 00:59:26,340 Perquè vostè sap que això està ordenada i vostè sap que això està solucionat. 1204 00:59:26,340 --> 00:59:29,360 Així que vostè ni tan sols ha de comparar el 5, que acaba de comparar el 3. 1205 00:59:29,360 --> 00:59:32,070 I el 2 és menor que 3, per la saps 2 han d'anar al final. 1206 00:59:32,070 --> 00:59:33,120 >> El mateix allà. 1207 00:59:33,120 --> 00:59:34,740 L'1 ha d'anar aquí. 1208 00:59:34,740 --> 00:59:37,330 I després quan es posarà aquests dos valors junts, 1209 00:59:37,330 --> 00:59:39,950 vostè sap que això està ordenada i vostè sap que el que es va solucionar. 1210 00:59:39,950 --> 00:59:43,240 Així llavors l'1 i el 2, l'1 és inferior a 2. 1211 00:59:43,240 --> 00:59:45,570 Això et diu que l'1 ha d'anar al final d'aquest 1212 00:59:45,570 --> 00:59:47,480 sense mirar si més no a 3 o 5. 1213 00:59:47,480 --> 00:59:50,100 I després el 4, només pot xec, que va a la dreta aquí. 1214 00:59:50,100 --> 00:59:51,480 Vostè no ha de mirar el 5. 1215 00:59:51,480 --> 00:59:52,570 El mateix amb el 6. 1216 00:59:52,570 --> 00:59:55,860 Vostè sap que el 6-- només no necessita ser mirat. 1217 00:59:55,860 --> 00:59:57,870 >> I així, d'aquesta manera, vostè és simplement estalviant- 1218 00:59:57,870 --> 00:59:59,526 una gran quantitat de passos quan vostè està comparant. 1219 00:59:59,526 --> 01:00:02,150 Vostè no ha de comparar cada element contra altres elements. 1220 01:00:02,150 --> 01:00:05,230 Vostè acaba de comparar contra els que vostè necessita per comparar contra. 1221 01:00:05,230 --> 01:00:06,870 Així que això és una cosa d'un concepte abstracte. 1222 01:00:06,870 --> 01:00:10,540 No us preocupeu si no és bastant colpejar la seva dreta encara. 1223 01:00:10,540 --> 01:00:14,740 Però, en general, això és com una combinació de tipus funciona. 1224 01:00:14,740 --> 01:00:17,750 Preguntes, preguntes ràpides, abans de passar? 1225 01:00:17,750 --> 01:00:18,550 Sí. 1226 01:00:18,550 --> 01:00:22,230 >> AUDIÈNCIA: Llavors vostè diu que vostè pren l'1, i després el 4 i el 6 1227 01:00:22,230 --> 01:00:23,860 i posar-los en. 1228 01:00:23,860 --> 01:00:26,800 Així que no són those-- no estan que mirar-los 1229 01:00:26,800 --> 01:00:28,544 com a elements separats, no com el tot? 1230 01:00:28,544 --> 01:00:29,210 ANDI Peng: Sí. 1231 01:00:29,210 --> 01:00:32,020 Així que el que està passant és que, bàsicament, 1232 01:00:32,020 --> 01:00:33,650 estan creant una nova gamma de la marca. 1233 01:00:33,650 --> 01:00:36,690 Així que ja saps que, aquí, tinc dues matrius de mida 3, oi? 1234 01:00:36,690 --> 01:00:39,600 Així que ja saps que el meu matriu ordenada necessita tenir 6 elements. 1235 01:00:39,600 --> 01:00:42,270 Així que vostè acaba de crear una nova quantitat de memòria. 1236 01:00:42,270 --> 01:00:44,270 Així que vostè és una mena sent un malbaratament de la memòria, 1237 01:00:44,270 --> 01:00:46,186 però això no importa perquè és molt petita. 1238 01:00:46,186 --> 01:00:48,590 Així que ens fixem en l'1 i ens fixem en el 2. 1239 01:00:48,590 --> 01:00:50,770 I vostè sap que l'1 és inferior a 2. 1240 01:00:50,770 --> 01:00:53,840 Així que ja saps que 1 ha d'anar en el començament de tot això. 1241 01:00:53,840 --> 01:00:55,850 >> Ni tan sols necessita mirar el 3 i el 5. 1242 01:00:55,850 --> 01:00:57,400 Així que ja saps gener hi va. 1243 01:00:57,400 --> 01:00:59,300 Llavors, bàsicament, tallar l'1. 1244 01:00:59,300 --> 01:01:00,370 És, com, mort per a nosaltres. 1245 01:01:00,370 --> 01:01:03,690 Llavors només tenim 2, 3, 5, i després 4 i 6. 1246 01:01:03,690 --> 01:01:06,270 I llavors vostè sap això, comparar el 4 i el 2, 1247 01:01:06,270 --> 01:01:07,560 oh, el 2 ha d'entrar aquí. 1248 01:01:07,560 --> 01:01:09,685 Així que vostè plop del 2 a baix, vostè avantatge apagat. 1249 01:01:09,685 --> 01:01:12,060 Llavors només ha el 3 i el 5 en el 4 i el 6. 1250 01:01:12,060 --> 01:01:14,650 I et quedes picat fora fins que se'ls posa a la matriu. 1251 01:01:14,650 --> 01:01:17,110 >> AUDIÈNCIA: Llavors, no ets més que sempre comparant el [inaudible]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI Peng: Exactament. 1253 01:01:17,710 --> 01:01:19,590 Així que en aquest sentit, vostè és simplement comparant, en essència, 1254 01:01:19,590 --> 01:01:21,240 un nombre contra l'altre nombre. 1255 01:01:21,240 --> 01:01:22,990 I perquè saps que ha ordenat, que 1256 01:01:22,990 --> 01:01:24,350 no han de mirar a través de tots els números. 1257 01:01:24,350 --> 01:01:25,870 Només has de mirar a la primera. 1258 01:01:25,870 --> 01:01:27,582 I llavors vostè pot simplement plop cap avall, perquè saps 1259 01:01:27,582 --> 01:01:29,640 pertanyen on han de pertànyer. 1260 01:01:29,640 --> 01:01:31,030 Sí. 1261 01:01:31,030 --> 01:01:32,920 Bona pregunta. 1262 01:01:32,920 --> 01:01:35,290 >> I a continuació, si algun de vostès són una mica ambiciós, 1263 01:01:35,290 --> 01:01:38,660 no dubti en mirar aquest codi. 1264 01:01:38,660 --> 01:01:40,680 Això és en realitat la implementació física 1265 01:01:40,680 --> 01:01:42,150 de com escriuríem fusió tipus. 1266 01:01:42,150 --> 01:01:44,070 I vostè pot veure, és molt curt. 1267 01:01:44,070 --> 01:01:46,310 Però les idees que hi ha darrere que són bastant complexos. 1268 01:01:46,310 --> 01:01:50,865 Així que si tens ganes de dibuixar això en la seva tasca aquesta nit, no dubteu en. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> D'ACORD. 1271 01:01:54,740 --> 01:01:58,070 David també es va acostar això en conferència. 1272 01:01:58,070 --> 01:02:00,660 Quins són el millor cas temps d'execució, pitjors temps d'execució de casos, 1273 01:02:00,660 --> 01:02:05,680 i els temps d'execució previstos de fusió tipus? 1274 01:02:05,680 --> 01:02:07,260 Un parell de segons per pensar. 1275 01:02:07,260 --> 01:02:11,198 Això és bastant difícil, però una mica intuïtiva si es pensa en això. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Tot bé. 1278 01:02:23,054 --> 01:02:25,269 >> AUDIÈNCIA: És el pitjor dels casos n log n? 1279 01:02:25,269 --> 01:02:26,060 ANDI Peng: Exactament. 1280 01:02:26,060 --> 01:02:29,380 I per què és n log n. 1281 01:02:29,380 --> 01:02:32,230 >> AUDIÈNCIA: ¿No és perquè es converteix en exponencialment més ràpid, 1282 01:02:32,230 --> 01:02:35,390 així que és com una funció de la qual en comptes de ser n 1283 01:02:35,390 --> 01:02:37,529 quadrat o alguna cosa així? 1284 01:02:37,529 --> 01:02:38,320 ANDI Peng: Exactament. 1285 01:02:38,320 --> 01:02:40,750 Així que la raó per què el temps d'execució en aquest registre és n 1286 01:02:40,750 --> 01:02:44,310 n és porque-- ho estàs fent en tots aquests passos? 1287 01:02:44,310 --> 01:02:46,190 No ets més que tallar per la meitat, no? 1288 01:02:46,190 --> 01:02:48,750 I així, quan estem fent registre, tot el que està fent 1289 01:02:48,750 --> 01:02:53,150 es dividir un problema en un mitjà, al mig, en un mitjà, en més de meitats. 1290 01:02:53,150 --> 01:02:56,430 I en aquest sentit, pot espècie d'eliminar el model lineal 1291 01:02:56,430 --> 01:02:57,510 que hem estat utilitzant. 1292 01:02:57,510 --> 01:03:00,254 Perquè quan picar coses de la mitjana, que és un registre. 1293 01:03:00,254 --> 01:03:02,420 Això és només la matemàtica manera de representar-lo. 1294 01:03:02,420 --> 01:03:06,310 >> I, finalment, al final, ets només fer una última passada a través 1295 01:03:06,310 --> 01:03:07,930 posar tot en ordre, no? 1296 01:03:07,930 --> 01:03:10,330 I pel que si vostè només ha de comprovar una cosa, això és n. 1297 01:03:10,330 --> 01:03:13,420 I pel que és classe de multiplicant els dos junts. 1298 01:03:13,420 --> 01:03:17,660 Així que és com si tinguessis aquesta final comprovar N aquí amb un registre de n 1299 01:03:17,660 --> 01:03:18,390 fins aquí. 1300 01:03:18,390 --> 01:03:21,060 I si es multiplica ells, això és n log n. 1301 01:03:21,060 --> 01:03:26,100 >> I així, el millor dels casos i el pitjor cas i espera que es tot n log n. 1302 01:03:26,100 --> 01:03:27,943 És també com una altra espècie. 1303 01:03:27,943 --> 01:03:30,090 És com una mena de selecció en el sentit que 1304 01:03:30,090 --> 01:03:32,131 no importa el que el seu llista és, que només va 1305 01:03:32,131 --> 01:03:34,801 a fer el mateix cada vegada. 1306 01:03:34,801 --> 01:03:35,300 D'ACORD. 1307 01:03:35,300 --> 01:03:39,950 Així com vostès poden veure, tot i que els gèneres que ens hem anat through-- n 1308 01:03:39,950 --> 01:03:41,660 quadrat, no és molt eficient. 1309 01:03:41,660 --> 01:03:47,060 I fins i tot aquest n log n és no és el més eficient. 1310 01:03:47,060 --> 01:03:49,720 Si vostès són curiosos, hi ha mecanismes d'ordenació 1311 01:03:49,720 --> 01:03:54,310 que són tan eficients que són gairebé essencialment pla en temps d'execució. 1312 01:03:54,310 --> 01:03:55,420 >> Tens algun log n de. 1313 01:03:55,420 --> 01:03:58,190 Tens algun registre de log n de. 1314 01:03:58,190 --> 01:04:00,330 No toquem sobre ells en aquesta classe en aquest moment. 1315 01:04:00,330 --> 01:04:02,663 Però si vostès són curiosos, no dubti a google, el que és 1316 01:04:02,663 --> 01:04:04,392 els mecanismes de classificació més eficient. 1317 01:04:04,392 --> 01:04:06,350 No ho sé, hi ha alguns realment divertits, 1318 01:04:06,350 --> 01:04:09,860 com-- hi ha alguna cosa de veritat els divertits que la gent fa. 1319 01:04:09,860 --> 01:04:12,210 I un es pregunta com Alguna vegada has pensat en això. 1320 01:04:12,210 --> 01:04:15,730 Així google, si tens una mica de recanvi temps, d'ara endavant, quins són algunes maneres divertides 1321 01:04:15,730 --> 01:04:17,730 que persones--, així com persones ways-- eficients 1322 01:04:17,730 --> 01:04:20,371 han estat capaços de posar en pràctica les classes. 1323 01:04:20,371 --> 01:04:20,870 D'ACORD. 1324 01:04:20,870 --> 01:04:22,880 I aquí és només una mica de pràctica taula. 1325 01:04:22,880 --> 01:04:26,850 Sé que tots vostès, abans d'aquesta prova 0, estarà a la seva habitació, probablement tractant 1326 01:04:26,850 --> 01:04:27,960 memoritzar això. 1327 01:04:27,960 --> 01:04:30,940 Així que això és bo aquí per a vostès. 1328 01:04:30,940 --> 01:04:37,120 Però no us oblideu la lògica que made-- ¿Per què aquests números estaven passant. 1329 01:04:37,120 --> 01:04:39,870 Si sempre estàs perdut, simplement fer Assegureu-vos de saber el que els tipus són. 1330 01:04:39,870 --> 01:04:40,820 I es pot executar a través de en la teva ment 1331 01:04:40,820 --> 01:04:42,903 esbrinar per què els respostes són aquestes respostes. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Tot bé. 1334 01:04:47,600 --> 01:04:49,680 Així que anem a moure en, finalment, a la recerca. 1335 01:04:49,680 --> 01:04:51,638 Perquè com els de vostè que han llegit el conjunt de processadors, 1336 01:04:51,638 --> 01:04:55,175 la recerca és també part de El problema d'aquesta setmana posa. 1337 01:04:55,175 --> 01:04:57,300 Se li demanarà a aplicar dos tipus de cerques. 1338 01:04:57,300 --> 01:05:00,070 Es tracta d'una recerca lineal i un és una recerca binària. 1339 01:05:00,070 --> 01:05:01,760 >> Així que la recerca lineal és bastant fàcil. 1340 01:05:01,760 --> 01:05:04,070 El que desitja és buscar elements d'una llista per veure si vostè ho aconsegueix. 1341 01:05:04,070 --> 01:05:05,444 Només has de recórrer. 1342 01:05:05,444 --> 01:05:08,170 I si és igual a alguna cosa, vostè pot tornar-lo, oi? 1343 01:05:08,170 --> 01:05:10,890 Però el que estem més interessat en parlar de 1344 01:05:10,890 --> 01:05:14,550 és la recerca binària, la dreta, que és el dividir i conquerir mecanisme que 1345 01:05:14,550 --> 01:05:18,190 David estava demostrant en la conferència. 1346 01:05:18,190 --> 01:05:20,810 >> Recordeu l'exemple guia de telèfons que segueix l'educació de, 1347 01:05:20,810 --> 01:05:23,960 la qual ell va lluitar tipus de una mica en aquest últim any, 1348 01:05:23,960 --> 01:05:27,530 on es divideix el problema en el medi, al mig, al mig, una i altra vegada, 1349 01:05:27,530 --> 01:05:30,730 fins a trobar el que estàs buscant? 1350 01:05:30,730 --> 01:05:33,727 I tens la temps d'execució d'això també. 1351 01:05:33,727 --> 01:05:35,810 I vostè pot veure, és significativament més eficient 1352 01:05:35,810 --> 01:05:39,080 que qualsevol altre tipus de cerca. 1353 01:05:39,080 --> 01:05:41,880 >> Així que la forma en que anàvem a anar sobre la implementació d'una recerca binària 1354 01:05:41,880 --> 01:05:46,510 És a dir, si teníem una matriu, índex de 0 a 6, set elements, 1355 01:05:46,510 --> 01:05:49,790 podem mirar al medi, dreta- ho sento, si la nostra pregunta primer-- 1356 01:05:49,790 --> 01:05:53,840 si volem fer la pregunta de, té la matriu conté l'element de 7, 1357 01:05:53,840 --> 01:05:56,840 òbviament, sent els éssers humans, i que té com un petit arsenal, és fàcil per a nosaltres 1358 01:05:56,840 --> 01:05:58,210 dir que sí. 1359 01:05:58,210 --> 01:06:05,750 Però la manera d'implementar un binari Cerca seria buscar en el medi. 1360 01:06:05,750 --> 01:06:08,020 >> Sabem que l'índex 3 és el medi, ja que 1361 01:06:08,020 --> 01:06:09,270 saben que hi ha set elements. 1362 01:06:09,270 --> 01:06:10,670 Quin 7 dividit per 2? 1363 01:06:10,670 --> 01:06:12,850 Vostè pot tallar aquest extra 1. 1364 01:06:12,850 --> 01:06:14,850 Tens 3 en el medi. 1365 01:06:14,850 --> 01:06:17,590 Així que és conjunt de 3 igual a 7? 1366 01:06:17,590 --> 01:06:18,900 No es tracta, no? 1367 01:06:18,900 --> 01:06:21,050 Però podem fer un parell de xecs. 1368 01:06:21,050 --> 01:06:25,380 És gamma de 3 a menys de 7 o és gamma de 3 més gran que 7? 1369 01:06:25,380 --> 01:06:27,240 >> I sabem que és menys de 7. 1370 01:06:27,240 --> 01:06:30,259 Així que sabem que, oh, ha no estar a la meitat esquerra. 1371 01:06:30,259 --> 01:06:32,300 Sabem que ha de ser en la meitat dreta, no? 1372 01:06:32,300 --> 01:06:34,662 Així que només podem tallar la meitat de la matriu. 1373 01:06:34,662 --> 01:06:36,370 Ni tan sols hem de veure-ho mai més. 1374 01:06:36,370 --> 01:06:38,711 Perquè sabem que la meitat del nostre problema-- 1375 01:06:38,711 --> 01:06:41,210 sabem que la resposta està en la meitat dreta del nostre problema. 1376 01:06:41,210 --> 01:06:42,580 Així que només ens fixem en això ara. 1377 01:06:42,580 --> 01:06:44,860 >> Així que ara ens fixem en el mitjà del que queda. 1378 01:06:44,860 --> 01:06:46,880 Aquest índex maig. 1379 01:06:46,880 --> 01:06:50,200 Fem el mateix xec de nou i veiem que és més petit. 1380 01:06:50,200 --> 01:06:52,050 Així que mirem a l'esquerra d'això. 1381 01:06:52,050 --> 01:06:53,430 I llavors veiem que xec. 1382 01:06:53,430 --> 01:06:57,600 És el valor de la matriu en índex de 4 igual a 7? 1383 01:06:57,600 --> 01:06:58,260 Ho és. 1384 01:06:58,260 --> 01:07:03,580 Així que podem tornar cert, perquè trobem el valor a la nostra llista. 1385 01:07:03,580 --> 01:07:06,738 La manera en què jo vaig passar per Això té sentit per a tothom? 1386 01:07:06,738 --> 01:07:08,760 D'ACORD. 1387 01:07:08,760 --> 01:07:11,670 Et vaig a donar nois potser, com, tres, quatre minuts per esbrinar 1388 01:07:11,670 --> 01:07:13,270 com això en pseudocodi. 1389 01:07:13,270 --> 01:07:18,070 >> Així que imagino que et vaig demanar que escriure una funció anomenada de recerca () que retorna 1390 01:07:18,070 --> 01:07:20,640 un valor, un valor booleà, això era cert o false-- com, 1391 01:07:20,640 --> 01:07:22,970 cert si vostè va trobar el valor, false si no ho vas fer. 1392 01:07:22,970 --> 01:07:25,230 I llavors eres aprovada en el valor que 1393 01:07:25,230 --> 01:07:28,410 estaves buscant en valors, que és la array-- oh, definitivament vaig posar 1394 01:07:28,410 --> 01:07:29,410 que en el lloc equivocat. 1395 01:07:29,410 --> 01:07:29,580 D'ACORD. 1396 01:07:29,580 --> 01:07:31,829 De tota manera, això hauria de tenir estat a la dreta dels valors. 1397 01:07:31,829 --> 01:07:36,280 I després int n és el nombre d'elements en la matriu. 1398 01:07:36,280 --> 01:07:39,430 Com faria vostè per tractar pseudocodi per a aquest problema en? 1399 01:07:39,430 --> 01:07:41,630 Et vaig a donar a tipus com tres minuts per fer això. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 No, crec que hi ha only-- sí, n'hi ha un just aquí. 1402 01:08:02,595 --> 01:08:03,261 AUDIÈNCIA: Puc? 1403 01:08:03,261 --> 01:08:04,388 ANDI Peng: Sí, el tens. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 És que el treball? 1406 01:08:11,050 --> 01:08:12,290 D'acord, guai. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> D'ACORD. 1409 01:10:44,720 --> 01:10:47,630 Totes les persones adequades, estem frenarà en. 1410 01:10:47,630 --> 01:10:49,730 D'ACORD. 1411 01:10:49,730 --> 01:10:54,020 Així que suposem que tenim aquesta bella petita matriu amb n valors en el mateix. 1412 01:10:54,020 --> 01:10:55,170 Jo no dibuixar les línies. 1413 01:10:55,170 --> 01:10:58,649 Però, com podem anar sobre tractant d'escriure això? 1414 01:10:58,649 --> 01:11:00,440 Algú vol dóna'm la primera línia? 1415 01:11:00,440 --> 01:11:02,814 Si vol donar-me la primera línia d'aquest pseudocodi. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> AUDIÈNCIA: [inaudible] 1418 01:11:08,430 --> 01:11:10,138 AUDIÈNCIA: El que vol iterar through-- 1419 01:11:10,138 --> 01:11:11,094 AUDIÈNCIA: Només un altre bucle for? 1420 01:11:11,094 --> 01:11:11,760 AUDIÈNCIA: --per. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI Peng: Així que aquest és una mica complicat. 1423 01:11:17,780 --> 01:11:23,130 Penseu sobre-- desitja per seguir funcionant aquest bucle 1424 01:11:23,130 --> 01:11:27,950 una i altra vegada fins quan? 1425 01:11:27,950 --> 01:11:30,819 >> AUDIÈNCIA: Fins al [inaudible] valor és igual a aquest valor. 1426 01:11:30,819 --> 01:11:31,610 ANDI Peng: Exactament. 1427 01:11:31,610 --> 01:11:33,900 Així que vostè pot en realitat només write-- fins i tot podem simplificar més. 1428 01:11:33,900 --> 01:11:35,630 Només podem fer un bucle while, oi? 1429 01:11:35,630 --> 01:11:39,380 Així que vostè pot simplement tenir loop-- sabem que es tracta d'un temps. 1430 01:11:39,380 --> 01:11:42,850 Però per ara, em vaig dir "bucle" - a través de què? 1431 01:11:42,850 --> 01:11:46,640 Loop until-- ho és la nostra condició de finalització? 1432 01:11:46,640 --> 01:11:47,510 Crec que el vaig escoltar. 1433 01:11:47,510 --> 01:11:48,530 Vaig sentir a algú dir que. 1434 01:11:48,530 --> 01:11:51,255 >> Audiència: Els valors equivalen a mitjà. 1435 01:11:51,255 --> 01:11:52,255 ANDI Peng: Digues-ho una altra vegada. 1436 01:11:52,255 --> 01:11:54,470 AUDIÈNCIA: O bé, fins que el valor que està buscant 1437 01:11:54,470 --> 01:11:58,470 per és igual al valor mitjà. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI Peng: ¿I si no hi és? 1439 01:12:00,280 --> 01:12:03,113 Què passa si el valor que està buscant per no és en realitat en aquesta sèrie? 1440 01:12:03,113 --> 01:12:05,890 AUDIÈNCIA: Tornarà 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI Peng: Però, què és el que volem bucle fins si tenim una condició? 1442 01:12:08,850 --> 01:12:09,350 Sí. 1443 01:12:09,350 --> 01:12:11,239 >> AUDIÈNCIA: Fins que no hi hagi un sol valor? 1444 01:12:11,239 --> 01:12:13,530 ANDI Peng: Vostè pot recórrer until-- així que vostè sap que vostè és 1445 01:12:13,530 --> 01:12:15,714 tindrà un valor màxim, no? 1446 01:12:15,714 --> 01:12:18,130 I saps que tenir un valor mínim, no? 1447 01:12:18,130 --> 01:12:20,379 Perquè també, això és una cosa Em vaig oblidar de dir abans, 1448 01:12:20,379 --> 01:12:22,640 que alguna cosa que és crític sobre la recerca binària 1449 01:12:22,640 --> 01:12:24,182 és que la matriu ja està ordenat. 1450 01:12:24,182 --> 01:12:26,973 Perquè no hi ha forma de fer això si que són valors simplement a l'atzar. 1451 01:12:26,973 --> 01:12:29,190 Vostè no sap si un és més gran que l'altra, no? 1452 01:12:29,190 --> 01:12:32,720 >> Així que ja saps que el seu màxim i seus minuts són aquí, oi? 1453 01:12:32,720 --> 01:12:35,590 Si vostè va a ser l'ajust el seu màxim en els seus minuts i els mid-- 1454 01:12:35,590 --> 01:12:38,470 anem a suposar que la seva mitjans valor és aquí-- dret 1455 01:12:38,470 --> 01:12:43,910 vas a bàsicament bucle fins al seu mínim és 1456 01:12:43,910 --> 01:12:47,510 gairebé el mateix que el seu màxim, a la dreta, o si el seu màxim no és el mateix que el min. 1457 01:12:47,510 --> 01:12:48,040 Oi? 1458 01:12:48,040 --> 01:12:51,340 Perquè quan això passa, vostè sap que que finalment ha colpejat el mateix valor. 1459 01:12:51,340 --> 01:12:59,135 ¿Així que vols bucle fins el min és menor o igual A-- perdó, 1460 01:12:59,135 --> 01:13:01,510 no menys d'o igual a, l'altra forma és around-- max. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> ¿Això té sentit? 1463 01:13:16,160 --> 01:13:18,810 Vaig prendre un parell d'intents per obtenir aquest dret. 1464 01:13:18,810 --> 01:13:21,869 Però bucle fins al seu valor màxim és essencialment gairebé menys 1465 01:13:21,869 --> 01:13:23,410 o igual que el mínim, no? 1466 01:13:23,410 --> 01:13:25,201 Això és quan vostè sap que ha convergit. 1467 01:13:25,201 --> 01:13:29,290 AUDIÈNCIA: Quan el seu màxim valor sigui inferior al mínim? 1468 01:13:29,290 --> 01:13:31,040 ANDI Peng: Si es manté ajustant-, que 1469 01:13:31,040 --> 01:13:32,380 és el que ens anem estar fent en aquest. 1470 01:13:32,380 --> 01:13:33,460 Això té sentit? 1471 01:13:33,460 --> 01:13:35,750 Mínim i màxim són només sencers que som, probablement, 1472 01:13:35,750 --> 01:13:39,260 voldrà crear per mantenir la pista d'on estem buscant. 1473 01:13:39,260 --> 01:13:41,790 A causa de que existeix la matriu independentment del que estem fent. 1474 01:13:41,790 --> 01:13:45,030 Igual, que no som en realitat físicament tallant la matriu, no? 1475 01:13:45,030 --> 01:13:47,261 Estem ajustant on estem buscant. 1476 01:13:47,261 --> 01:13:48,136 Això té sentit? 1477 01:13:48,136 --> 01:13:48,472 >> AUDIÈNCIA: Sí. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI Peng: OK. 1479 01:13:49,110 --> 01:13:57,090 Així que si aquesta és la condició per al nostre bucle, ¿Què és el que volem dins d'aquest bucle? 1480 01:13:57,090 --> 01:13:58,700 Què anem a voler fer? 1481 01:13:58,700 --> 01:14:02,390 Així que ara mateix, tenim un màxim i un mínim, a la dreta, 1482 01:14:02,390 --> 01:14:04,962 probablement creat per aquí en algun lloc. 1483 01:14:04,962 --> 01:14:07,170 Anem a probable que desitgi trobar un mitjà, no? 1484 01:14:07,170 --> 01:14:08,450 Com serem capaç de trobar el mitjà? 1485 01:14:08,450 --> 01:14:09,491 Quina és la mathematical-- 1486 01:14:09,491 --> 01:14:11,079 AUDIÈNCIA: Max plus min dividit per 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI Peng: Exactament. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Això té sentit? 1490 01:14:21,620 --> 01:14:25,780 I és el que vostès veig per què no acaba de servei- per què vam fer això 1491 01:14:25,780 --> 01:14:27,850 en lloc de fer simplement n dividit per 2? 1492 01:14:27,850 --> 01:14:30,310 És perquè n és un valor això seguirà igual. 1493 01:14:30,310 --> 01:14:30,979 Oi? 1494 01:14:30,979 --> 01:14:34,020 Però a mesura que ens adaptem la nostra mínim i valors màxims, que canviaran. 1495 01:14:34,020 --> 01:14:36,040 I com a resultat, la nostra mitjana canviarà també. 1496 01:14:36,040 --> 01:14:37,873 Així que per això volem per fer això aquí. 1497 01:14:37,873 --> 01:14:38,510 D'ACORD. 1498 01:14:38,510 --> 01:14:41,600 >> I després, ara que que hem trobat our-- si. 1499 01:14:41,600 --> 01:14:44,270 >> AUDIÈNCIA: Només un pregunta-- ràpida quan dius mínim i màxim, 1500 01:14:44,270 --> 01:14:46,410 estem assumint que ja està ordenada? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI Peng: Sí, això és en realitat un condició prèvia per a una recerca binària, 1502 01:14:48,400 --> 01:14:49,816 que vostè ha de saber que està ordenada. 1503 01:14:49,816 --> 01:14:53,660 Quina és la raó per classe, vostè escriu en el seu problema ja davant de la seva recerca binària. 1504 01:14:53,660 --> 01:14:55,910 D'ACORD. 1505 01:14:55,910 --> 01:14:58,876 Així que ara que sabem que el nostre punt mig És a dir, què és el que vols fer aquí? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> AUDIÈNCIA: Volem comparar que a l'altra. 1508 01:15:04,319 --> 01:15:05,110 ANDI Peng: Exactament. 1509 01:15:05,110 --> 01:15:12,280 Així que anem a comparar mitjan valor, no? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 I què diuen nosaltres quan comparem? 1512 01:15:18,670 --> 01:15:22,226 Què és el que volem fer després? 1513 01:15:22,226 --> 01:15:25,389 >> AUDIÈNCIA: Si el valor és més gran dels mitjans, volem tallar-lo. 1514 01:15:25,389 --> 01:15:26,180 ANDI Peng: Exactament. 1515 01:15:26,180 --> 01:15:33,940 Així que si el valor és més gran dels mitjans, estem 1516 01:15:33,940 --> 01:15:36,550 voldrà canviar aquests Maxes mínim i, oi? 1517 01:15:36,550 --> 01:15:38,980 Què és el que volem canviar? 1518 01:15:38,980 --> 01:15:42,145 Així que si coneixem el valor està en algun lloc aquí, el que hem de fer per canviar? 1519 01:15:42,145 --> 01:15:44,758 Volem canviar la nostra mínima per a ser intervinguts, oi? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 I després una altra cosa, si és en aquest mitjà, ¿què és el que volem canviar? 1522 01:15:54,292 --> 01:15:55,306 >> AUDIÈNCIA: La seva màxima. 1523 01:15:55,306 --> 01:15:55,972 ANDI Peng: Sí. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 I després et vas mantenir bucle, oi? 1526 01:16:04,680 --> 01:16:08,920 Perquè ara, després d'una iteració a través, tens un màxim aquí. 1527 01:16:08,920 --> 01:16:10,760 I llavors vostè pot tornar a calcular una mitjana. 1528 01:16:10,760 --> 01:16:11,990 I llavors vostè pot comparar. 1529 01:16:11,990 --> 01:16:14,766 I seguiràs endavant fins que els minuts i els Maxes 1530 01:16:14,766 --> 01:16:15,890 essencialment han convergit. 1531 01:16:15,890 --> 01:16:17,890 I això és quan se sap que has arribat a la final de la mateixa. 1532 01:16:17,890 --> 01:16:20,280 I ja sigui que ho hagis trobat o vostè no té en aquest punt. 1533 01:16:20,280 --> 01:16:23,170 >> Té això sentit per a tothom? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 D'ACORD. 1536 01:16:26,770 --> 01:16:27,900 Això és molt important, ja que tindrà 1537 01:16:27,900 --> 01:16:29,760 escriure això en el codi d'aquesta nit. 1538 01:16:29,760 --> 01:16:32,660 Però vostès tenen una molt bona sentit del que hauria d'estar fent, 1539 01:16:32,660 --> 01:16:34,051 la qual cosa és bo. 1540 01:16:34,051 --> 01:16:34,550 D'ACORD. 1541 01:16:34,550 --> 01:16:38,840 Així que tenim al voltant de set minut secció esquerra. 1542 01:16:38,840 --> 01:16:43,170 Així que anem a parlar de aquest conjunt de processadors que farem. 1543 01:16:43,170 --> 01:16:46,410 Així que el conjunt de processadors es divideix en dues meitats. 1544 01:16:46,410 --> 01:16:50,230 La primera mitja implica la implementació d'una troballa 1545 01:16:50,230 --> 01:16:54,210 en el qual s'escriu una recerca lineal, 1 recerca binària, i un algoritme de classificació. 1546 01:16:54,210 --> 01:16:56,690 >> Així que aquesta és la primera temps en un conjunt de processadors, on 1547 01:16:56,690 --> 01:17:00,050 estarem donant-li nois el que es diu codi de distribució, que és el codi 1548 01:17:00,050 --> 01:17:02,740 que hem pre-escrita, però només va deixar algunes peces fora 1549 01:17:02,740 --> 01:17:04,635 perquè vostè pugui acabar d'escriure. 1550 01:17:04,635 --> 01:17:07,510 Així que vostès, si ens fixem en aquest codi, és possible que es realment espantat. 1551 01:17:07,510 --> 01:17:08,630 Si acaba agrada, ahh, jo no saben el que està fent, 1552 01:17:08,630 --> 01:17:11,670 No sé, com, això sembla tan complicat, ahh, relaxar-se. 1553 01:17:11,670 --> 01:17:12,170 Està bé. 1554 01:17:12,170 --> 01:17:12,930 Llegir l'especificació. 1555 01:17:12,930 --> 01:17:16,920 L'especificació li explicarà exactament el que tots aquests programes estan fent. 1556 01:17:16,920 --> 01:17:20,560 >> Per exemple, és un programa generate.c que vindrà amb el seu conjunt de processadors. 1557 01:17:20,560 --> 01:17:24,060 En realitat no cal tocar-lo, però vostè ha d'entendre el que està fent. 1558 01:17:24,060 --> 01:17:28,550 I generate.c, l'únic que està fent és ja sigui generació de nombres aleatoris 1559 01:17:28,550 --> 01:17:32,400 o pot donar-li una llavor, com un nombre preestablert que es necessita, 1560 01:17:32,400 --> 01:17:34,140 i genera més números. 1561 01:17:34,140 --> 01:17:37,170 Així que hi ha una forma específica de aplicar en el qual generate.c 1562 01:17:37,170 --> 01:17:42,760 vostè pot fer un munt de nombres per fer realitat els teus altres mètodes successivament. 1563 01:17:42,760 --> 01:17:45,900 >> Així que si vostè volia, per exemple, prova de la seva troballa, 1564 01:17:45,900 --> 01:17:48,970 que es vol executar generate.c, generar un munt de nombres, 1565 01:17:48,970 --> 01:17:50,880 i després executar la seva funció d'ajudants. 1566 01:17:50,880 --> 01:17:53,930 La funció dels seus ajudants és on estàs escriure realment físicament codi. 1567 01:17:53,930 --> 01:17:59,330 I pensar ajudants com un arxiu de biblioteca que està escrit que troballa està trucant. 1568 01:17:59,330 --> 01:18:02,950 I així dins helpers.c, podràs fer recerca i classificació. 1569 01:18:02,950 --> 01:18:06,500 >> I després vas a essencialment només cal posar a tots plegats. 1570 01:18:06,500 --> 01:18:10,350 L'especificació li dirà com ja que en la línia d'ordres. 1571 01:18:10,350 --> 01:18:14,880 I podràs provar si o no és el seu tipus i de recerca estan treballant. 1572 01:18:14,880 --> 01:18:15,870 Fresc. 1573 01:18:15,870 --> 01:18:18,720 Algú ha començat i problemes o dubtes plantejats 1574 01:18:18,720 --> 01:18:20,520 que tenen ara amb això? 1575 01:18:20,520 --> 01:18:21,020 D'ACORD. 1576 01:18:21,020 --> 01:18:21,476 >> AUDIÈNCIA: Espereu. 1577 01:18:21,476 --> 01:18:21,932 Tinc una pregunta. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI Peng: Sí. 1579 01:18:22,844 --> 01:18:28,390 >> AUDIÈNCIA: Així que vaig començar a fer la recerca lineal en helpers.c 1580 01:18:28,390 --> 01:18:29,670 i no va ser realment funciona. 1581 01:18:29,670 --> 01:18:34,590 Però més tard, vaig saber que només que eliminar-lo i fer recerca binària. 1582 01:18:34,590 --> 01:18:36,991 Així que què importa si no funciona? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI Peng: Resposta curta és no. 1585 01:18:41,510 --> 01:18:42,642 Però ja que estem no-- 1586 01:18:42,642 --> 01:18:44,350 AUDIÈNCIA: Però ningú de realitat de xecs. 1587 01:18:44,350 --> 01:18:46,058 ANDI Peng: Mai estem va a veure això. 1588 01:18:46,058 --> 01:18:49,590 Però és probable que vulgui fer Assegureu-vos que la cerca està treballant. 1589 01:18:49,590 --> 01:18:51,700 Perquè si la seva lineal cerca no funciona, 1590 01:18:51,700 --> 01:18:54,410 llavors és probable que el seu binari cerca no funcionarà tan bé. 1591 01:18:54,410 --> 01:18:56,646 A causa que té similars lògica en tots dos. 1592 01:18:56,646 --> 01:18:58,020 I no, no importa. 1593 01:18:58,020 --> 01:19:01,300 Així que els únics que convertiran en to de classificació i recerca binària. 1594 01:19:01,300 --> 01:19:02,490 Sí. 1595 01:19:02,490 --> 01:19:06,610 >> I també, una gran quantitat de nens estaven compilar helpers.c. 1596 01:19:06,610 --> 01:19:09,550 No està realment permès per fer això, perquè helpers.c 1597 01:19:09,550 --> 01:19:11,200 no té una funció principal. 1598 01:19:11,200 --> 01:19:13,550 I pel que només ha ser en realitat la compilació 1599 01:19:13,550 --> 01:19:18,670 generar i trobar, perquè trobar trucades helpers.c i les funcions que la integren. 1600 01:19:18,670 --> 01:19:20,790 Així que fa la depuració un dolor al cul. 1601 01:19:20,790 --> 01:19:22,422 Però això és el que hem de fer. 1602 01:19:22,422 --> 01:19:23,880 AUDIÈNCIA: Vostè acaba de fer de tot, no? 1603 01:19:23,880 --> 01:19:27,290 ANDI Peng: Vostè pot simplement fer tot així, si. 1604 01:19:27,290 --> 01:19:28,060 D'ACORD. 1605 01:19:28,060 --> 01:19:32,570 Així que és això en termes del el conjunt de processadors està demanant a tots a fer. 1606 01:19:32,570 --> 01:19:35,160 Si vostè té alguna pregunta, lliure de preguntar després de la secció. 1607 01:19:35,160 --> 01:19:37,580 Vaig a ser aquí per com 20 minuts. 1608 01:19:37,580 --> 01:19:40,500 >> I sí, de el joc de paràmetres no està tan malament. 1609 01:19:40,500 --> 01:19:41,680 Vostès haurien d'estar bé. 1610 01:19:41,680 --> 01:19:43,250 Aquests, només has de seguir les directrius. 1611 01:19:43,250 --> 01:19:47,840 Classe de tenir un sentit de, lògicament, el que hauria d'estar succeint i se li multa. 1612 01:19:47,840 --> 01:19:48,690 No sigui massa espantada. 1613 01:19:48,690 --> 01:19:50,220 Hi ha una gran quantitat de codi ja escrit allà. 1614 01:19:50,220 --> 01:19:53,011 No sigui massa espantat si no ho fa entendre el que tot això significa. 1615 01:19:53,011 --> 01:19:54,749 Si és molt, és totalment bé. 1616 01:19:54,749 --> 01:19:55,790 I arribat a les hores d'oficina. 1617 01:19:55,790 --> 01:19:57,520 Nosaltres l'ajudarem a fer una ullada. 1618 01:19:57,520 --> 01:20:00,810 >> AUDIÈNCIA: Amb l'extra funcions, què busquem els de dalt? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI Peng: Sí, aquestes són en el codi. 1620 01:20:03,417 --> 01:20:05,750 En el joc de 15, la meitat de ja està escrit per a vostè. 1621 01:20:05,750 --> 01:20:09,310 Així que aquestes funcions estan Ja en el codi. 1622 01:20:09,310 --> 01:20:12,020 Sí. 1623 01:20:12,020 --> 01:20:12,520 Tot bé. 1624 01:20:12,520 --> 01:20:14,000 Bé, millor de les sorts. 1625 01:20:14,000 --> 01:20:15,180 És un dia fastigós. 1626 01:20:15,180 --> 01:20:19,370 Així que espero que vostès no se senten massa mal per romandre dins i codificació. 1627 01:20:19,370 --> 01:20:22,133