1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [REPRODUCCIÓ DE MÚSICA] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Aquest és CS50. 5 00:00:12,550 --> 00:00:14,612 I aquest és el començament de la tercera setmana. 6 00:00:14,612 --> 00:00:16,820 Així que tenim un munt d'emocionants coses que cobreixen l'actualitat. 7 00:00:16,820 --> 00:00:20,160 Una gran quantitat d'oportunitats per els voluntaris a l'escenari. 8 00:00:20,160 --> 00:00:22,780 I en última instància, en l'actualitat és No es tracta de codi. 9 00:00:22,780 --> 00:00:24,820 Però es tracta d'idees i es tracta d'algoritmes, 10 00:00:24,820 --> 00:00:28,420 i de fet portar de tornada alguns les lliçons apreses de la setmana zero, 11 00:00:28,420 --> 00:00:31,910 on record, ens introduït aquesta monstruositat. 12 00:00:31,910 --> 00:00:33,880 I l'endeutament inspiració que, per començar 13 00:00:33,880 --> 00:00:36,879 per resoldre cada vegada més sofisticada problemes algorítmicament. 14 00:00:36,879 --> 00:00:38,420 Però primer, un parell d'anuncis. 15 00:00:38,420 --> 00:00:42,020 Així que un, si vol unir-se El personal i els companys de classe de CS50 en el dinar 16 00:00:42,020 --> 00:00:44,670 aquest divendres, tant aquí com a Cambridge, ia New Haven, 17 00:00:44,670 --> 00:00:48,060 si us plau visiti el curs de lloc web, on un URL es pot trobar. 18 00:00:48,060 --> 00:00:50,390 Conferència d'aquest dimecres serà no ser aquí a Sanders. 19 00:00:50,390 --> 00:00:53,610 Serà només en línia, de manera que sintonitzar al lloc web de l'CS50, 20 00:00:53,610 --> 00:00:55,850 ja sigui aquí a Cambridge o New Haven també. 21 00:00:55,850 --> 00:00:58,110 >> I llavors un problema fixar dos ja és a les teves mans. 22 00:00:58,110 --> 00:01:03,067 Si no ha bussejat en el, però, permetin-me per oferir el suggeriment enèrgica 23 00:01:03,067 --> 00:01:05,150 que, sobretot ara, quan el problema estableix per avançat, 24 00:01:05,150 --> 00:01:08,669 vostè realment vol començar ara, si no incursionar una mica en el cap de setmana o abans 25 00:01:08,669 --> 00:01:10,710 la primera vegada que surten a Divendres, perquè vas a 26 00:01:10,710 --> 00:01:14,380 troben que no són necessàriament cada vegada més llargs o més desafiant per 27 00:01:14,380 --> 00:01:14,950 es. 28 00:01:14,950 --> 00:01:17,575 Crec que trobareu que, en en general, tendeixen a tenir més o menys 29 00:01:17,575 --> 00:01:18,892 voltant mateixa quantitat de temps. 30 00:01:18,892 --> 00:01:20,850 Però certament depèn en l'estudiant, i 31 00:01:20,850 --> 00:01:22,880 depèn de la mentalitat amb la qual t'acostes a ella. 32 00:01:22,880 --> 00:01:24,910 Però invariablement, vas córrer contra alguna paret, 33 00:01:24,910 --> 00:01:26,350 i vas a colpejar alguns errors, i no ets més que 34 00:01:26,350 --> 00:01:27,950 no serà capaç de superar-ho en algun moment. 35 00:01:27,950 --> 00:01:31,380 I és enormement valuosa per poder allunyar-se, tornar al dia següent, 36 00:01:31,380 --> 00:01:35,286 anar a les hores d'oficina, missatge l'CS50 Discutiu o similar, per aconseguir realment desbloquejat. 37 00:01:35,286 --> 00:01:36,160 Així que tingues-ho en compte. 38 00:01:36,160 --> 00:01:40,830 Començant d'hora com sigui possible és la millor cosa que pots fer. 39 00:01:40,830 --> 00:01:44,160 Així que aquí és on vam començar la classe, al llarg de la setmana zero. 40 00:01:44,160 --> 00:01:47,441 I podem aconseguir un voluntari aquí per ajudar-me a trobar els micròfons? 41 00:01:47,441 --> 00:01:47,940 D'ACORD. 42 00:01:47,940 --> 00:01:48,900 Dempeus ja. 43 00:01:48,900 --> 00:01:50,080 Anem cap amunt. 44 00:01:50,080 --> 00:01:53,707 Suposo que això és el que va a treballar. 45 00:01:53,707 --> 00:01:54,415 Com et dius? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Anem cap amunt. 49 00:01:57,910 --> 00:01:58,619 Encantat de conéixer-te. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Encantat de conèixer-te. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: I vostè estigués aquí amb nosaltres en la setmana zero, és clar. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: jo. 53 00:02:03,028 --> 00:02:03,160 Jo era. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Així podria anar endavant i trobar per a nosaltres Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tan ràpid com sigui possible? 56 00:02:08,639 --> 00:02:10,639 Tan ràpid com puguis. 57 00:02:10,639 --> 00:02:13,756 Literalment estripar el problema a la meitat del que necessita. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Literalment esquinçant el problema al mig. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Molt bé. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Bé. 66 00:02:24,200 --> 00:02:24,701 Gràcies. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Molt bona. 68 00:02:25,700 --> 00:02:26,210 D'ACORD. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: I pel que ara, que ha retallat cap avall 70 00:02:27,610 --> 00:02:29,320 a la meitat de la mida del problema. 71 00:02:29,320 --> 00:02:31,267 Ara, estem a una quarta part. 72 00:02:31,267 --> 00:02:33,475 Vostè està prestant atenció a de quin costat estem mantenint? 73 00:02:33,475 --> 00:02:34,405 >> [El] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Sí, jo think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Quina secció estem? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Mofles, així. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Però Mike Smith va a ser després de Mofles. 79 00:02:42,810 --> 00:02:44,130 Tan-- 80 00:02:44,130 --> 00:02:48,180 >> [El] 81 00:02:48,180 --> 00:02:48,742 >> Tot bé. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: On estem buscant? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Ara, estem en quirúrgic. 86 00:02:54,760 --> 00:02:57,840 Ara, els metges. 87 00:02:57,840 --> 00:02:58,340 Ara-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- anem amb real. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 D'ACORD. 92 00:03:01,470 --> 00:03:03,700 Si necessita Real. 93 00:03:03,700 --> 00:03:05,250 Ara, quin camí és Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: D'aquesta forma. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Quina manera? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Espera. 97 00:03:08,240 --> 00:03:08,790 Dret M és--? 98 00:03:08,790 --> 00:03:09,110 Comencem con-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Sí. 100 00:03:10,090 --> 00:03:10,650 Estan a l'esquerra. 101 00:03:10,650 --> 00:03:11,430 El seu dret. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Sí. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Així que Mike aquí. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Què? 105 00:03:13,990 --> 00:03:14,665 >> [El] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Mal exemple, nois. 108 00:03:18,330 --> 00:03:18,830 Ho sento. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Això li ensenyarà a saltar de la cadira. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Et tinc. 113 00:03:23,390 --> 00:03:24,670 Et tinc. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Aquesta és-- Bé, et tinc. 117 00:03:26,812 --> 00:03:27,520 Smith aquí? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, gràcies. 119 00:03:28,894 --> 00:03:30,535 Així que seguiré mirant cap amunt Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, sí. 121 00:03:30,790 --> 00:03:31,340 No no No. 122 00:03:31,340 --> 00:03:31,600 Oh no. 123 00:03:31,600 --> 00:03:31,940 Això és meu. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, tens Smith. 125 00:03:32,580 --> 00:03:33,415 D'ACORD. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Sí, Smith va aconseguir aquí. 127 00:03:34,040 --> 00:03:34,700 Ho sento, nois. 128 00:03:34,700 --> 00:03:35,860 Vaig pensar que Michael-- estaves buscant Michael. 129 00:03:35,860 --> 00:03:36,550 Ho sento. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Està bé. 131 00:03:37,550 --> 00:03:39,950 Molt bé, ara estem en Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini i fills. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Només vostè i jo estem en això. 134 00:03:43,158 --> 00:03:44,050 D'ACORD. 135 00:03:44,050 --> 00:03:45,130 Trobeu-nos Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Estem en R per a escombraries. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Malo. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Això va a prendre un temps. 143 00:03:52,480 --> 00:03:54,340 >> [El] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Sabates. 146 00:03:56,720 --> 00:03:58,080 Estem en les sabates. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Ara estem gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Niça. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [El] 151 00:04:03,620 --> 00:04:05,440 Oh, això és genial. 152 00:04:05,440 --> 00:04:06,910 [El] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Està bé. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, això és bo. 156 00:04:11,365 --> 00:04:14,425 No crec que em vaig a tenir amics PSAT després d'això. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Good. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Així que anem a llàgrima això enmig. 163 00:04:21,600 --> 00:04:22,270 Està bé. 164 00:04:22,270 --> 00:04:25,606 Això acaba malament de totes maneres, perquè Mike Smith no estarà a les pàgines grogues. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: No, està bé. 167 00:04:27,140 --> 00:04:28,930 Però anem a suposar com ell està en aquesta pàgina. 168 00:04:28,930 --> 00:04:33,260 Així que ara, vostè ha retallat el problema baix d'una pàgina, i ens trobem amb Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [ANIMA] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 D'acord, gràcies. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 D'ACORD. 174 00:04:41,200 --> 00:04:43,646 Això va ser extraordinari. 175 00:04:43,646 --> 00:04:45,954 Però va ser encara més ràpid de recerca lineal, 176 00:04:45,954 --> 00:04:47,870 en què vam començar a a partir del llibre, 177 00:04:47,870 --> 00:04:51,210 i ens movem la nostra forma d'esquerra a dreta, finalment, a la recerca de Mike Smith. 178 00:04:51,210 --> 00:04:53,540 I així, si la guia telefònica tenia potser 1.000 pàgines, 179 00:04:53,540 --> 00:04:56,300 potser hauria pres ens 10 o més pàgines llàgrimes. 180 00:04:56,300 --> 00:04:59,380 >> Però és possible que hagi aprofitat tocat una suposició 181 00:04:59,380 --> 00:05:03,602 durant tot això, el que és a dir, que la guia de telèfons per endavant era què? 182 00:05:03,602 --> 00:05:04,310 AUDIÈNCIA: Ordenat. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Ha solucionat. 184 00:05:05,000 --> 00:05:05,160 Oi? 185 00:05:05,160 --> 00:05:07,909 S'ordena alfabèticament, per la qual que tots aquests noms i números 186 00:05:07,909 --> 00:05:11,230 estan ordenades pels Atlètics a la Z, i en ordre alfabètic en el medi. 187 00:05:11,230 --> 00:05:13,100 Però avui en dia, ens preguntem ara la pregunta, bé, 188 00:05:13,100 --> 00:05:16,170 Com Verizon o el telèfon empresa posar-lo en aquest estat? 189 00:05:16,170 --> 00:05:19,560 >> A causa que és una cosa d'aprofitar aquesta suposició, i per tant, 190 00:05:19,560 --> 00:05:22,570 resoldre un problema amb un algoritme més eficient. 191 00:05:22,570 --> 00:05:24,900 Però en realitat mai demanat a la setmana zero, bé, 192 00:05:24,900 --> 00:05:27,790 Quant costa Verizon o algú més 193 00:05:27,790 --> 00:05:29,620 per aconseguir que la llibreta de telèfons en forma ordenada? 194 00:05:29,620 --> 00:05:29,780 >> Oi? 195 00:05:29,780 --> 00:05:31,529 No importa si mirant cap amunt Mike Smith 196 00:05:31,529 --> 00:05:35,190 és súper ràpid, si vostè pren un any per ordenar les pàgines inicialment. 197 00:05:35,190 --> 00:05:35,690 Oi? 198 00:05:35,690 --> 00:05:38,620 Vostè pot ser que també acaba de tamisar a través d'un llibre de telèfon a l'atzar, 199 00:05:38,620 --> 00:05:40,690 si va a ser súper cara a solucionar el problema. 200 00:05:40,690 --> 00:05:42,350 Així que si podem tenir un altre voluntari. 201 00:05:42,350 --> 00:05:46,350 Anem a fer una ullada aquí a com might-- Anem up-- com 202 00:05:46,350 --> 00:05:48,100 podríem anar sobre la classificació dels mateixos. 203 00:05:48,100 --> 00:05:51,990 >> I si Jordan podia realitat uneix-te a nosaltres aquí a l'escenari. 204 00:05:51,990 --> 00:05:55,100 Anem cap amunt per un moment. 205 00:05:55,100 --> 00:05:56,359 Com et dius? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, anem cap amunt. 208 00:05:58,691 --> 00:06:02,070 I es et vas unir per mi i Jordània aquí. 209 00:06:02,070 --> 00:06:03,800 Caroline, gràcies. 210 00:06:03,800 --> 00:06:04,300 Tot bé. 211 00:06:04,300 --> 00:06:08,330 Així que el que tenim aquí Caroline té 26 llibres blaus 212 00:06:08,330 --> 00:06:10,747 que FAS utilitza per administrar certs exàmens finals. 213 00:06:10,747 --> 00:06:13,330 Aquests són cada vegada difícil de trobar, però el que hem fet amb antelació 214 00:06:13,330 --> 00:06:15,800 és que ens hem posat el nom d'algú a la part frontal de cada un d'aquests, 215 00:06:15,800 --> 00:06:18,133 però ens hem mantingut simple a continuació, posar els noms complets. 216 00:06:18,133 --> 00:06:22,720 Així que ens agradaria posar a la persona amb el nom A, C, J, B, fins al final de l'A a la Z, 217 00:06:22,720 --> 00:06:24,090 però estan en ordre aleatori. 218 00:06:24,090 --> 00:06:26,890 I pel que si ho faria, parlant de la seva camí a través dels problemes i se li 219 00:06:26,890 --> 00:06:31,620 fes-ho, pot seguir endavant i ordenar aquests per a nosaltres, de la A a la Z. 220 00:06:31,620 --> 00:06:34,070 >> AUDIÈNCIA: OK, llavors L és com, el medi. 221 00:06:34,070 --> 00:06:35,050 C està començant. 222 00:06:35,050 --> 00:06:42,410 B. J abans de L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Mantingui aquesta pensat per un segon. 224 00:06:45,140 --> 00:06:48,910 Perquè en cas contrari, això és només interessant per a vostè, jo, i Jordània. 225 00:06:48,910 --> 00:06:49,724 Cal anar. 226 00:06:49,724 --> 00:06:50,640 AUDIÈNCIA: [inaudible]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Què fas? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M es produeix després d'O 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, bo. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: I, F. Sí. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Per tant, Sembla que ets making-- seguir endavant. 238 00:07:10,689 --> 00:07:12,730 Sembla que estàs fent una pica gran aquí, 239 00:07:12,730 --> 00:07:13,910 i la classe d'una gran pila d'allà. 240 00:07:13,910 --> 00:07:16,230 Així que la primera meitat de l'alfabet, segona meitat de l'alfabet. 241 00:07:16,230 --> 00:07:16,460 D'ACORD. 242 00:07:16,460 --> 00:07:16,960 Bé. 243 00:07:16,960 --> 00:07:19,680 Tipus de dividir el problema en dues. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Sí. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Així que estàs tipus de selecció un darrere l'altre, 248 00:07:25,070 --> 00:07:27,620 posant-ho a l'esquerra oa la dreta, o Z va a terra. 249 00:07:27,620 --> 00:07:28,012 D'ACORD. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z va a terra. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 I va a terra. 253 00:07:30,920 --> 00:07:31,735 Ara podem posar X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G va a l'esquerra. 256 00:07:33,700 --> 00:07:36,017 S va bé. 257 00:07:36,017 --> 00:07:37,642 Tot dret, A va tot el camí de l'esquerra. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Ara, bé. 260 00:07:39,873 --> 00:07:43,260 Tenim A, B, C. W d'anar-hi. 261 00:07:43,260 --> 00:07:45,566 Molt bé, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Bueno. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Al centre, estic gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Així que ara, anem a classe de combinar aquests diversos munts. 267 00:07:52,375 --> 00:08:00,730 Així la A a C, llavors veig D, i E i F, i G, i H i I. Niça. 268 00:08:00,730 --> 00:08:05,540 J, K. I després, aquesta pila és a l'inrevés, però això està bé. 269 00:08:05,540 --> 00:08:06,040 És clar. 270 00:08:06,040 --> 00:08:07,240 Podem tallar algunes cantonades. 271 00:08:07,240 --> 00:08:07,950 D'ACORD. 272 00:08:07,950 --> 00:08:10,530 I llavors hem de W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Sí. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Excel·lent. 275 00:08:11,880 --> 00:08:14,122 Així que un gran agraïment a Caroline per a la classificació d'aquests. 276 00:08:14,122 --> 00:08:15,030 >> [ANIMA] 277 00:08:15,030 --> 00:08:17,287 >> Gràcies. 278 00:08:17,287 --> 00:08:18,120 Moltes gràcies. 279 00:08:18,120 --> 00:08:22,910 Així que ara considerarem per un moment com Caroline va estar fent això, 280 00:08:22,910 --> 00:08:26,040 i què és exactament el que van ser capaços A-- com 281 00:08:26,040 --> 00:08:28,409 van ser capaços de resoldre aquest problema quan estàvem 282 00:08:28,409 --> 00:08:29,950 donat un munt d'entrades aleatòries. 283 00:08:29,950 --> 00:08:31,610 >> Bé, sembla que hi ha era una mica d'un sistema allà? 284 00:08:31,610 --> 00:08:32,110 Dreta. 285 00:08:32,110 --> 00:08:34,495 Així que les cartes anteriors en l'alfabet, ella 286 00:08:34,495 --> 00:08:37,120 era posar a l'esquerra, i el últimes cartes en l'alfabet, 287 00:08:37,120 --> 00:08:38,270 que estava posant en la dreta. 288 00:08:38,270 --> 00:08:40,500 I tan aviat com es va assabentar algunes cartes proximals, uns 289 00:08:40,500 --> 00:08:43,124 que van un al costat de l'altre, posaria els d'ordre. 290 00:08:43,124 --> 00:08:46,750 I pel que d'alguna manera tenia aquests petits munts de entrades ordenades ocorren. 291 00:08:46,750 --> 00:08:50,540 >> I això és molt semblant al que la majoria de nosaltres els humans farien. 292 00:08:50,540 --> 00:08:53,530 Ens tipus de tamisar a través d'ell, i ens agradaria tipus de disposar d'un mecanisme. 293 00:08:53,530 --> 00:08:56,930 Però podria ser difícil escriure cap avall en una fórmula per se. 294 00:08:56,930 --> 00:08:59,010 Se sentia una mica més orgànic que això. 295 00:08:59,010 --> 00:09:02,560 Així que anem a veure si podem ara lligat el problema amb menys recursos. 296 00:09:02,560 --> 00:09:05,170 >> En lloc de 26, anem a fer alguna cosa molt menys 297 00:09:05,170 --> 00:09:09,890 amb només dir, set, darrere aquestes portes, per així dir-ho. 298 00:09:09,890 --> 00:09:11,300 Hi ha només set números? 299 00:09:11,300 --> 00:09:15,240 I si l'objectiu ara en mà és trobar un valor, 300 00:09:15,240 --> 00:09:17,850 anem a veure com de manera eficient podem anar fent això. 301 00:09:17,850 --> 00:09:22,460 I anem a veure si podem ara començar a aplicar alguns números, 302 00:09:22,460 --> 00:09:26,310 o algunes fórmules amb les que descriuen l'eficiència del nostre directori telefònic 303 00:09:26,310 --> 00:09:31,060 algoritme, el nostre algoritme llibre examen, i més en general, la recerca d'informació. 304 00:09:31,060 --> 00:09:34,770 >> Així que per això, deixar-me anar per davant, i a la pantalla tàctil per aquí, 305 00:09:34,770 --> 00:09:41,100 posar un navegador web que té exactament aquestes set portes. 306 00:09:41,100 --> 00:09:46,670 I si poguéssim aconseguir un altre voluntaris per venir per aquí, 307 00:09:46,670 --> 00:09:48,480 He posat aquestes mateixes portes aquí. 308 00:09:48,480 --> 00:09:49,170 Voluntari ràpida. 309 00:09:49,170 --> 00:09:51,130 >> Aquest un-- donem van a un més ràpid i més ràpid ara. 310 00:09:51,130 --> 00:09:51,600 Anem cap avall. 311 00:09:51,600 --> 00:09:52,308 Com et dius? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Molt bé, Trevor, anem cap avall. 315 00:09:55,770 --> 00:09:59,212 Així que Trevor s'ha ofert aquí per fer un problema similar, però un que és 316 00:09:59,212 --> 00:10:02,170 més estret en el seu abast, i això va que ens permeti tractar de formalitzar ara 317 00:10:02,170 --> 00:10:03,970 el procés per a la classificació d'aquests nombres. 318 00:10:03,970 --> 00:10:05,500 >> Així Trevor, encantat de conèixer-te. 319 00:10:05,500 --> 00:10:08,720 Així que aquí és una matriu, de manera que parlar, una llista de set portes. 320 00:10:08,720 --> 00:10:10,327 Vagi per davant i ens trobarà al número 50. 321 00:10:10,327 --> 00:10:12,410 I a continuació, després del fet, nos saber com ho vas trobar. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 En cas de ser-- bé. 324 00:10:20,040 --> 00:10:21,945 Sí, aquest és el que aquí? 325 00:10:21,945 --> 00:10:24,680 UH oh. 326 00:10:24,680 --> 00:10:25,560 D'ACORD. 327 00:10:25,560 --> 00:10:26,680 Va fer clic en aquesta. 328 00:10:26,680 --> 00:10:28,690 Bé. 329 00:10:28,690 --> 00:10:29,780 >> I bé. 330 00:10:29,780 --> 00:10:30,970 Ara ha fet clic en aquest. 331 00:10:30,970 --> 00:10:34,060 I et donaré el micròfon, de manera que vostè ho té en un moment. 332 00:10:34,060 --> 00:10:37,000 Seguiu endavant i feu clic al al costat que té la intenció. 333 00:10:37,000 --> 00:10:39,812 Sí, bé. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Puc desmarca una porta? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: No, no pots desmarcatge. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Aquest. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: On vols anar? 339 00:10:45,640 --> 00:10:46,410 Quin? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Que un. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Aquest. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Sí. 345 00:10:49,020 --> 00:10:49,700 Això era bo. 346 00:10:49,700 --> 00:10:50,380 Tot bé. 347 00:10:50,380 --> 00:10:53,900 Llavors, quin era el seu algoritme o procediment per fer això, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: M'acaba de passar per portes fins que van trobar un 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Excel·lent algoritme. 351 00:10:58,150 --> 00:10:59,540 Així que això està bé. 352 00:10:59,540 --> 00:11:03,120 Perquè, de fet, si revelo el que és darrere d'aquestes altres dues portes, el que 353 00:11:03,120 --> 00:11:06,954 trobarem aquí és que només tenim entrada aleatòria. 354 00:11:06,954 --> 00:11:08,870 Així que va ser realment com bo com es pot aconseguir. 355 00:11:08,870 --> 00:11:12,509 I de fet, tens millor que exhaustivament buscant tot el conjunt, 356 00:11:12,509 --> 00:11:15,300 perquè hauria estat molt mala sort si s'hagués colpejat el nombre 357 00:11:15,300 --> 00:11:16,604 50 en l'últim costat. 358 00:11:16,604 --> 00:11:18,520 Però ¿i si en lloc et va donar una suposició. 359 00:11:18,520 --> 00:11:20,630 Suposem que en certa manera em tots aquestes portes de tot, 360 00:11:20,630 --> 00:11:23,500 quedant amb la números ordenats en aquesta ocasió, 361 00:11:23,500 --> 00:11:29,730 però aquesta vegada és en realitat 1 diferent-- aquest temps, 362 00:11:29,730 --> 00:11:32,640 en realitat està ordenada per a vostè. 363 00:11:32,640 --> 00:11:35,380 I ara el perill a la mà és per colpejar el nombre 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Quin és l'algoritme serà? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Bé, si és ordenats, és ben va 367 00:11:39,628 --> 00:11:42,710 a ser-- si major a major, descendent, va ser el primer, 368 00:11:42,710 --> 00:11:44,751 o si és tot el contrari, serà l'última. 369 00:11:44,751 --> 00:11:48,897 Així que vaig a tocar a la porta, i a continuació, només tocar l'última porta. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Excel·lent. 371 00:11:49,980 --> 00:11:50,270 Tot bé. 372 00:11:50,270 --> 00:11:51,150 Així que trobem el número 50. 373 00:11:51,150 --> 00:11:52,970 Així que tan aviat com vostè sabia van ser ordenats, ens 374 00:11:52,970 --> 00:11:55,040 van ser capaços d'aprofitar aquesta suposició. 375 00:11:55,040 --> 00:11:57,040 Així que són massa semblant l'exemple guia telefònica. 376 00:11:57,040 --> 00:11:59,540 Tan aviat com vostè té, fins i tot amb un petit problema com aquest, 377 00:11:59,540 --> 00:12:02,380 les seves entrades pre-ordenats, podem en realitat trobar el valor discutible 378 00:12:02,380 --> 00:12:03,130 de manera més eficient. 379 00:12:03,130 --> 00:12:05,800 >> I jo no dic que si era ordenats petit a gran o gran a petit, 380 00:12:05,800 --> 00:12:08,080 i pel que era molt raonable per començar en un extrem o l'altre 381 00:12:08,080 --> 00:12:09,750 trobar realment aquest valor objectiu. 382 00:12:09,750 --> 00:12:11,400 Així que gràcies a Trevor també. 383 00:12:11,400 --> 00:12:13,260 I vaig a propose-- molt ben fet. 384 00:12:13,260 --> 00:12:16,960 Tenim un petit clip, en realitat, que és un dels nostres moments favorits en CS50, 385 00:12:16,960 --> 00:12:19,700 pel que de vegades aquestes donem no tot vagi segons el planejat. 386 00:12:19,700 --> 00:12:22,050 I de fet ara mateix, va aturar la interfície equivocada 387 00:12:22,050 --> 00:12:23,508 amb la qual utilitzar la pantalla tàctil. 388 00:12:23,508 --> 00:12:24,660 Així que va ser culpa meva no. 389 00:12:24,660 --> 00:12:26,600 >> Així que això farà per Clip de l'any que com 390 00:12:26,600 --> 00:12:28,570 de per què estava fent clic en la meva pròpia pantalla. 391 00:12:28,570 --> 00:12:31,390 Però donem una ullada ràpida al que va succeir l'any passat 392 00:12:31,390 --> 00:12:34,770 amb Jay, que es va acostar, i molt com Trevor aquí, voluntàriament, 393 00:12:34,770 --> 00:12:39,380 i en aquest breu clip, veuràs com aquesta mateixa demostració no va fer prou 394 00:12:39,380 --> 00:12:41,074 revelar les mateixes lliçons apreses. 395 00:12:41,074 --> 00:12:41,740 [REPRODUCCIÓ DE VÍDEO] 396 00:12:41,740 --> 00:12:45,360 -tots Els que vull que facis ara és de trobar per a mi, i per a nosaltres, 397 00:12:45,360 --> 00:12:51,674 en realitat, el nombre 50 un pas a la vegada. 398 00:12:51,674 --> 00:12:52,450 >> -El Nombre 50? 399 00:12:52,450 --> 00:12:53,190 >> -El Nombre 50. 400 00:12:53,190 --> 00:12:55,356 I vostè pot revelar el que és darrere de cadascuna d'aquestes portes 401 00:12:55,356 --> 00:12:58,540 amb només tocar amb un dit. 402 00:12:58,540 --> 00:13:00,910 Maleït sigui. 403 00:13:00,910 --> 00:13:02,870 >> [El] 404 00:13:02,870 --> 00:13:03,806 >> [FI DE REPRODUCCIÓ] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Així que va ser molt bé. 406 00:13:05,430 --> 00:13:06,796 Aquestes van ser les portes sense classificar. 407 00:13:06,796 --> 00:13:08,670 I Jay, per descomptat, trobat amb massa rapidesa. 408 00:13:08,670 --> 00:13:12,910 Trevor va fer un treball molt millor en termes d'un moment d'aprenentatge, 409 00:13:12,910 --> 00:13:15,850 per així dir-ho, aquest any en prenent més temps per trobar-lo. 410 00:13:15,850 --> 00:13:17,950 Per descomptat, llavors ens vam Jay una segona oportunitat, 411 00:13:17,950 --> 00:13:20,320 pel que ens ho van solucionar les portes, tal com ho vam fer per Trevor, 412 00:13:20,320 --> 00:13:22,300 i Trevor va fer molt bé aquesta vegada. 413 00:13:22,300 --> 00:13:26,124 Però Jay va fer un mitjà tan ràpid. 414 00:13:26,124 --> 00:13:26,790 [REPRODUCCIÓ DE VÍDEO] 415 00:13:26,790 --> 00:13:29,650 -El Objectiu ara és també nosaltres trobar el número 50, 416 00:13:29,650 --> 00:13:33,030 però fer-ho algorítmicament, i dir-nos com va en això. 417 00:13:33,030 --> 00:13:33,660 >> -D'ACORD. 418 00:13:33,660 --> 00:13:35,604 >> -I Si el troba, es manté la pel·lícula. 419 00:13:35,604 --> 00:13:37,228 Si no el troba, li dones l'esquena. 420 00:13:37,228 --> 00:13:38,044 >> -Home. 421 00:13:38,044 --> 00:13:38,860 >> -Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] a D'acord. 423 00:13:40,800 --> 00:13:46,236 Així que vaig a comprovar els extrems primer per determinar si there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Aplaudiments] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [FI DE REPRODUCCIÓ] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Així classificació portes clarament condueix a una major eficiència. 429 00:13:59,760 --> 00:14:01,680 I així, dues vegades més ràpid és el que vaig voler dir no. 430 00:14:01,680 --> 00:14:03,270 I així Jay va tenir sort en les dues ocasions. 431 00:14:03,270 --> 00:14:06,685 I també va tenir sort en aquest últim any, vaig demanar alguns discos Blu-ray 432 00:14:06,685 --> 00:14:07,560 per donar a conèixer realment. 433 00:14:07,560 --> 00:14:09,768 Ho sento d'aquest any, no va tenir la mateixa, Trevor. 434 00:14:09,768 --> 00:14:11,540 Però millor encara era fa uns anys. 435 00:14:11,540 --> 00:14:14,820 I alguns de vostès podrien saber això company, Sean, que quan estava al CS50, 436 00:14:14,820 --> 00:14:17,780 va ser impugnada amb l'exacta mateix problema, encara que en SD, 437 00:14:17,780 --> 00:14:19,360 com aviat veuràs, de tornada al dia. 438 00:14:19,360 --> 00:14:22,622 I trobareu que no només que prengui una mica més de Jay, 439 00:14:22,622 --> 00:14:25,580 una mica més de Trevor, va ser En realitat aquesta meravellosa oportunitat 440 00:14:25,580 --> 00:14:29,820 a participar gairebé tots al gent a la Price is Right, fomentant 441 00:14:29,820 --> 00:14:31,889 ell per trobar el nombre que estàvem buscant. 442 00:14:31,889 --> 00:14:32,930 Anem. fer una ullada ràpida. 443 00:14:32,930 --> 00:14:33,320 >> [REPRODUCCIÓ DE VÍDEO] 444 00:14:33,320 --> 00:14:33,820 >> -D'ACORD. 445 00:14:33,820 --> 00:14:36,680 Així que la seva tasca aquí, Sean, és la següent. 446 00:14:36,680 --> 00:14:40,860 He amagat darrere d'aquests portes el número set. 447 00:14:40,860 --> 00:14:45,120 Però amagat en alguna d'aquestes portes així són altres números negatius. 448 00:14:45,120 --> 00:14:47,500 I el seu objectiu és pensar d'aquesta fila superior dels nombres 449 00:14:47,500 --> 00:14:50,390 com s'acaba d'una matriu, o simplement seqüència dels fulls de paper 450 00:14:50,390 --> 00:14:51,510 amb números darrere d'ells. 451 00:14:51,510 --> 00:14:55,540 I el seu objectiu és, només amb la part superior varietat aquí, em trobar el número set. 452 00:14:55,540 --> 00:14:58,570 I estem a continuació, anem a criticar com vostè va sobre fer-ho. 453 00:14:58,570 --> 00:14:59,070 -Tot bé. 454 00:14:59,070 --> 00:15:00,850 Ens -Buscar el número set, per favor. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 No. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Cinc, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [El] 461 00:15:24,770 --> 00:15:25,910 >> No és una pregunta amb trampa. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Un. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [El] 466 00:15:34,695 --> 00:15:37,861 En aquest punt, la seva puntuació no és molt bo, de manera que així podria seguir endavant. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tres. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [El] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Continuar. 473 00:15:47,774 --> 00:15:50,690 Francament, no puc evitar preguntar- el que estàs tan sols pensar, així que-- 474 00:15:50,690 --> 00:15:51,959 >> [El] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Només la fila superior, de manera que vostè té de tres esquerra. 477 00:15:55,020 --> 00:15:56,200 Així que trobar 7. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [El] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Set. 484 00:16:26,946 --> 00:16:28,780 >> [Aplaudiments] 485 00:16:28,780 --> 00:16:29,426 >> Tot bé. 486 00:16:29,426 --> 00:16:30,360 >> [FI DE REPRODUCCIÓ] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Així que vam poder veure a aquests durant tot el dia. 488 00:16:31,840 --> 00:16:34,090 I, per descomptat, alguns demostracions d'aquest any potser 489 00:16:34,090 --> 00:16:36,330 ara acabar en el pròxim vídeo de l'any també. 490 00:16:36,330 --> 00:16:39,040 Així que ara anem a realitat centrar-se en els algoritmes 491 00:16:39,040 --> 00:16:42,140 aquí, i veure si no podem Ara començar a formalitzar 492 00:16:42,140 --> 00:16:46,650 com podem anar sobre com obtenir les nostres dades en aquest estat que està ordenada, 493 00:16:46,650 --> 00:16:50,054 pel que en última instància, podem realitat buscar-la en el diccionari de manera més eficient. 494 00:16:50,054 --> 00:16:52,470 I tot i que anem utilitzar conjunts de dades bastant petits, 495 00:16:52,470 --> 00:16:54,511 com el que vuit nombres tenim aquí al tauler, 496 00:16:54,511 --> 00:16:58,230 en última instància, podrien aplicar aquestes mateixes idees 1.000 entrades, un milió d'entrades, 497 00:16:58,230 --> 00:17:02,100 4000000000 d'entrades, ja que els algoritmes seran fonamentalment els mateixos. 498 00:17:02,100 --> 00:17:05,359 >> I el que aquesta és la nostra última oportunitat perquè els voluntaris avui en dia, 499 00:17:05,359 --> 00:17:09,790 però potser el més complicat, per a això necessitem vuit voluntaris 500 00:17:09,790 --> 00:17:12,960 per arribar i ens caminar pel procés de classificar el que aviat 501 00:17:12,960 --> 00:17:15,212 estar en aquests faristols aquí. 502 00:17:15,212 --> 00:17:16,170 Permetin-me començar de nou aquí. 503 00:17:16,170 --> 00:17:19,692 >> Així que un al verd turquoise-- és? 504 00:17:19,692 --> 00:17:21,130 Estàs cometent? 505 00:17:21,130 --> 00:17:21,630 Dos. 506 00:17:21,630 --> 00:17:23,069 Anem cap avall. 507 00:17:23,069 --> 00:17:23,569 D'ACORD. 508 00:17:23,569 --> 00:17:24,420 Tres. 509 00:17:24,420 --> 00:17:25,400 Quatre. 510 00:17:25,400 --> 00:17:27,247 Deixi mi-- OK, cinc. 511 00:17:27,247 --> 00:17:28,830 Vostè està sent nominat pel seu amic. 512 00:17:28,830 --> 00:17:31,340 Sis, set-vuit. 513 00:17:31,340 --> 00:17:32,130 Anem cap amunt. 514 00:17:32,130 --> 00:17:32,630 Tot bé. 515 00:17:32,630 --> 00:17:33,190 Moltes gràcies. 516 00:17:33,190 --> 00:17:33,689 Anem cap amunt. 517 00:17:33,689 --> 00:17:34,790 Anem cap amunt. 518 00:17:34,790 --> 00:17:35,330 >> Tot bé. 519 00:17:35,330 --> 00:17:38,890 Així que el que tenim aquí-- i això és un dels més difícils, 520 00:17:38,890 --> 00:17:42,390 ja que això requerirà que l'humor mi per una mica de temps. 521 00:17:42,390 --> 00:17:43,442 Vostè serà el número u. 522 00:17:43,442 --> 00:17:44,150 Com et dius? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 En David. 526 00:17:46,092 --> 00:17:46,800 Com et dius? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Josep, vostè és el número dos. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, número tres. 530 00:17:52,260 --> 00:17:53,722 Stefan, el número quatre. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, número cinc. 533 00:17:57,548 --> 00:17:58,452 [Inaudible] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [inaudible]. 535 00:17:59,618 --> 00:18:00,391 David, el número sis. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: Nombre de Matt 07:00. 538 00:18:02,160 --> 00:18:02,850 ¿I? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, número vuit. 541 00:18:04,470 --> 00:18:04,970 Tot bé. 542 00:18:04,970 --> 00:18:06,510 Si could-- crits. 543 00:18:06,510 --> 00:18:08,820 Si tots vostès, com el seu primer desafiament, hi ha 544 00:18:08,820 --> 00:18:10,820 són vuit faristols aquí davant l'audiència. 545 00:18:10,820 --> 00:18:14,200 Si poguessis posar els seus números en aquests suports de música de tal manera 546 00:18:14,200 --> 00:18:16,560 que s'alineen amb el mateixos números en el tauler. 547 00:18:16,560 --> 00:18:19,560 Així que vostès veuen com que per posar els números en aquesta música 548 00:18:19,560 --> 00:18:21,960 es troba aquí. 549 00:18:21,960 --> 00:18:25,980 Excel·lent fins al moment. 550 00:18:25,980 --> 00:18:26,600 >> Excel·lent. 551 00:18:26,600 --> 00:18:26,890 D'ACORD. 552 00:18:26,890 --> 00:18:29,556 Així que ara, demanarem a la pregunta de diverses maneres diferents. 553 00:18:29,556 --> 00:18:31,610 Com podem anar sobre la classificació aquesta gent aquí? 554 00:18:31,610 --> 00:18:34,500 Perquè teníem un parell d'enfocaments anterior, pel qual van ser 555 00:18:34,500 --> 00:18:36,360 tipus de presa de dos cubs diferents. 556 00:18:36,360 --> 00:18:38,842 I llavors estàvem general recompondre les coses junts. 557 00:18:38,842 --> 00:18:41,050 Tan aviat com vam veure dos nombres que pertanyien junts, 558 00:18:41,050 --> 00:18:41,975 els posem junts. 559 00:18:41,975 --> 00:18:43,350 Dues lletres que van de la mà. 560 00:18:43,350 --> 00:18:45,058 >> Però anem a veure si ens no pot formalitzar aquest, 561 00:18:45,058 --> 00:18:48,044 perquè en última instància, tenim alguns pseudo-codi es vol, 562 00:18:48,044 --> 00:18:49,710 amb el que pot resoldre aquests problemes. 563 00:18:49,710 --> 00:18:51,870 Així que ara, estic mirant aquests números aquí. 564 00:18:51,870 --> 00:18:55,030 I veig un munt d'errors. 565 00:18:55,030 --> 00:18:57,750 Al final, vull un al a l'esquerra i vuit a la dreta. 566 00:18:57,750 --> 00:19:00,650 >> I pel que estic veient aquests dos, quatre-dos. 567 00:19:00,650 --> 00:19:02,930 ¿I quin és el problema, és obvi? 568 00:19:02,930 --> 00:19:04,261 Sí. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dos òbviament ve abans 4, així que vostè sap el que? 571 00:19:07,160 --> 00:19:10,210 Permetin-me primer prenc un enfocament cobdiciosos, si es vol, tant problema com 572 00:19:10,210 --> 00:19:13,790 establir un-- si recorden des del Edició Estàndard de de problemes Un, 573 00:19:13,790 --> 00:19:16,820 on només a nivell local a resoldre el problema això és just aquí al davant de mi 574 00:19:16,820 --> 00:19:17,690 i veure a on em porta. 575 00:19:17,690 --> 00:19:17,870 >> D'ACORD. 576 00:19:17,870 --> 00:19:20,161 Així que dos i quatre, me n'aniré endavant i només et intercanviar dues. 577 00:19:20,161 --> 00:19:22,400 Si vostè pot moure físicament vostès mateixos i del seu paper, 578 00:19:22,400 --> 00:19:25,040 Sembla que he aconseguit el llistar en millor estat. 579 00:19:25,040 --> 00:19:26,330 >> Ara, són bons. 580 00:19:26,330 --> 00:19:28,480 Vaig a seguir endavant, 04:06, es veu bé. 581 00:19:28,480 --> 00:19:29,110 Cap problema. 582 00:19:29,110 --> 00:19:30,440 Sis i vuit, a D'acord. 583 00:19:30,440 --> 00:19:31,860 Vuit i un, un altre problema. 584 00:19:31,860 --> 00:19:34,750 Perquè el que és cert això de les 08:01? 585 00:19:34,750 --> 00:19:36,990 Un ve abans de les vuit, i així ¿què hem de fer? 586 00:19:36,990 --> 00:19:38,090 Anem intercanviï aquests dos. 587 00:19:38,090 --> 00:19:39,316 Un i vuit. 588 00:19:39,316 --> 00:19:40,690 I ara, seguiré endavant. 589 00:19:40,690 --> 00:19:42,030 Jo seguiré mirant cap endavant. 590 00:19:42,030 --> 00:19:42,840 I anem a veure què passa. 591 00:19:42,840 --> 00:19:44,680 Vuit-tres, de Per descomptat, fora d'ordre. 592 00:19:44,680 --> 00:19:45,815 D'intercanvi Let. 593 00:19:45,815 --> 00:19:46,940 Vuit-set, és clar. 594 00:19:46,940 --> 00:19:47,481 No funciona. 595 00:19:47,481 --> 00:19:48,280 D'intercanvi Let. 596 00:19:48,280 --> 00:19:49,940 Vuit-cinc, per descomptat, anem a swap. 597 00:19:49,940 --> 00:19:50,560 Tot bé. 598 00:19:50,560 --> 00:19:51,880 Llista està ordenada. 599 00:19:51,880 --> 00:19:53,060 sí? 600 00:19:53,060 --> 00:19:54,280 >> OK, òbviament no. 601 00:19:54,280 --> 00:19:55,860 Però és una mica millor, no? 602 00:19:55,860 --> 00:19:57,270 A causa avís del que va passar. 603 00:19:57,270 --> 00:20:01,749 Cada vegada que realitza un intercanvi, una més petita nombre de tipus de percolado d'aquesta manera, 604 00:20:01,749 --> 00:20:03,790 i un nombre més gran percolado d'aquesta manera, o anem a 605 00:20:03,790 --> 00:20:06,880 començar dient bombollejar a la bombolleig esquerra o cap a la dreta. 606 00:20:06,880 --> 00:20:10,080 >> Ara, no és suficient, perquè en el millor d'un nombre podria 607 00:20:10,080 --> 00:20:11,990 han mogut un sol lloc cap endavant, o en el pitjor, 608 00:20:11,990 --> 00:20:13,880 un nombre podria tenir mogut un punt més. 609 00:20:13,880 --> 00:20:16,369 Així que ja saps el que, aquest tipus de funcionat prou bé fins ara. 610 00:20:16,369 --> 00:20:17,410 Déjame intentar-ho de nou. 611 00:20:17,410 --> 00:20:18,880 Dos i quatre, que estan bé. 612 00:20:18,880 --> 00:20:20,180 Quatre i sis, que estan bé. 613 00:20:20,180 --> 00:20:21,790 Sis i un, fora d'ordre. 614 00:20:21,790 --> 00:20:23,007 Així que anem a vostès dos swap. 615 00:20:23,007 --> 00:20:25,840 I ara, observi el problema de començant a aconseguir una mica millor de nou. 616 00:20:25,840 --> 00:20:27,006 Sis-tres, fora d'ordre. 617 00:20:27,006 --> 00:20:28,100 Anem a vosaltres dos swap. 618 00:20:28,100 --> 00:20:29,730 Sis-set, ja està bo. 619 00:20:29,730 --> 00:20:32,230 Set-cinc, per descomptat, fora d'ordre. 620 00:20:32,230 --> 00:20:33,920 Set-vuit, en ordre. 621 00:20:33,920 --> 00:20:36,470 I ara, pot ser que hagi de fer això unes quantes vegades més. 622 00:20:36,470 --> 00:20:39,830 I de fet, pensar per si mateixos potser quantes vegades màxim 623 00:20:39,830 --> 00:20:41,330 podria jo haver de caminar d'anada i tornada? 624 00:20:41,330 --> 00:20:42,390 >> Tornarem a això. 625 00:20:42,390 --> 00:20:43,700 Així que dos i quatre continuen en D'acord. 626 00:20:43,700 --> 00:20:44,940 Quatre i un, doncs no. 627 00:20:44,940 --> 00:20:45,747 Així, intercanvi de deixar. 628 00:20:45,747 --> 00:20:47,830 I de nou, observi visualment un és tipus de bombolleig 629 00:20:47,830 --> 00:20:49,163 a l'esquerra, on ha d'estar. 630 00:20:49,163 --> 00:20:50,010 Quatre i tres d'intercanvi. 631 00:20:50,010 --> 00:20:51,330 Quatre i sis. 632 00:20:51,330 --> 00:20:53,100 Sis-cinc anys d'intercanvi. 633 00:20:53,100 --> 00:20:53,959 Sis-set. 634 00:20:53,959 --> 00:20:55,000 Set i vuit són bons. 635 00:20:55,000 --> 00:20:55,500 >> Bé. 636 00:20:55,500 --> 00:20:58,460 Estem rebent encara millor. 637 00:20:58,460 --> 00:20:59,130 Així que anem a veure. 638 00:20:59,130 --> 00:21:00,940 Ara, tenim dos i un. 639 00:21:00,940 --> 00:21:02,520 Per descomptat, canviar. 640 00:21:02,520 --> 00:21:07,520 Dues i tres, tres i quatre, quatre i 5, sis i set, set-vuit. 641 00:21:07,520 --> 00:21:08,020 Bé. 642 00:21:08,020 --> 00:21:08,730 ¿I saps què? 643 00:21:08,730 --> 00:21:11,190 Perquè vaig fer un canvi allà, m'ho dius a mi fer un xec seny. 644 00:21:11,190 --> 00:21:13,023 Déjame anar tot el camí de nou al principi. 645 00:21:13,023 --> 00:21:13,680 D'ACORD. 646 00:21:13,680 --> 00:21:14,750 Un, dos-- yup, veus? 647 00:21:14,750 --> 00:21:15,870 Alguna cosa estava malament. 648 00:21:15,870 --> 00:21:18,420 Tres, quatre, cinc, sis, set, vuit. 649 00:21:18,420 --> 00:21:21,920 I en aquest últim pas, són Se sent còmode amb el meu ara 650 00:21:21,920 --> 00:21:23,830 al·legant que s'ordena? 651 00:21:23,830 --> 00:21:24,330 D'ACORD. 652 00:21:24,330 --> 00:21:25,880 Visualment, això és absolutament cert. 653 00:21:25,880 --> 00:21:28,410 Però funcionalment, el va fer també acaba de succeir 654 00:21:28,410 --> 00:21:31,870 en aquesta última passada que li permet per confirmar que aquesta llista és de fet 655 00:21:31,870 --> 00:21:32,660 ordenats? 656 00:21:32,660 --> 00:21:34,477 >> Què vaig fer o no fer això últim passi? 657 00:21:34,477 --> 00:21:35,810 AUDIÈNCIA: No hi va haver canvis. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Ho sento? 659 00:21:36,120 --> 00:21:37,070 AUDIÈNCIA: No hi ha canvis. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: No hi va haver canvis. 661 00:21:38,653 --> 00:21:41,947 Així que seria estúpid de la meva part fer això mateix algoritme de nou 662 00:21:41,947 --> 00:21:43,780 si jo no vaig fer cap canvia la primera vegada. 663 00:21:43,780 --> 00:21:45,160 I l'estat no ha canviat. 664 00:21:45,160 --> 00:21:47,576 Certament, jo no faré Qualsevol canvi del segon temps. 665 00:21:47,576 --> 00:21:49,820 I així, és segur ara dir, la llista està ordenada. 666 00:21:49,820 --> 00:21:52,069 >> I, de fet, això és ara cosa que anem a general 667 00:21:52,069 --> 00:21:56,900 anomenada d'ordenament de bombolla, en què per parelles, corregir errors de nou, 668 00:21:56,900 --> 00:22:00,210 i una altra, i una altra, i vostè seguir endavant cap enrere i endavant, 669 00:22:00,210 --> 00:22:03,370 i d'anada i tornada, fins que no fer aquest tipus de swaps, i en aquest moment 670 00:22:03,370 --> 00:22:07,089 vostè pot estar segur, si, acabat de fixar tots els errors. 671 00:22:07,089 --> 00:22:08,630 Anem a restablir i jugar diferent. 672 00:22:08,630 --> 00:22:11,590 Si vostès podrien tornar a l'ordre en què van ser fa un moment, 673 00:22:11,590 --> 00:22:13,780 que es veia així. 674 00:22:13,780 --> 00:22:17,640 Ara, anem a fer un enfocament una poc més com el llibre de l'examen, 675 00:22:17,640 --> 00:22:21,122 pel qual estàvem constantment la selecció de la lletra de l'alfabet 676 00:22:21,122 --> 00:22:22,830 quin tipus de volíem per fer front a la propera. 677 00:22:22,830 --> 00:22:26,420 Potser va ser una gran carta, com A, o una lletra Z. baixa 678 00:22:26,420 --> 00:22:28,170 >> Així que tothom està de tornada en aquest ordre. 679 00:22:28,170 --> 00:22:29,800 I ara m'ho dius a mi fer això. 680 00:22:29,800 --> 00:22:34,880 Vegem sé que tinc vuit nombres aquí. 681 00:22:34,880 --> 00:22:37,410 Vaig a seguir endavant i simplement deliberadament seleccioneu 682 00:22:37,410 --> 00:22:38,520 els elements més petits. 683 00:22:38,520 --> 00:22:38,760 Oi? 684 00:22:38,760 --> 00:22:39,801 Això sembla intuïtiva també. 685 00:22:39,801 --> 00:22:42,560 Per què no em sembla el més petit element, el va posar on pertany, 686 00:22:42,560 --> 00:22:45,280 a continuació, obtenir el següent element més petit, ja on pertany, i simplement repetiu. 687 00:22:45,280 --> 00:22:46,820 >> A causa de que de manera intuïtiva, que hauria de funcionar també. 688 00:22:46,820 --> 00:22:48,441 Així que 4, que és un nombre molt petit. 689 00:22:48,441 --> 00:22:49,940 Vaig a recordar d'on és. 690 00:22:49,940 --> 00:22:50,523 Espera un minut. 691 00:22:50,523 --> 00:22:51,577 Dos és més petit. 692 00:22:51,577 --> 00:22:53,910 Permetin-me ara recordo què dos és, i oblidar-se de quatre. 693 00:22:53,910 --> 00:22:55,050 Ens ocuparem d'això més tard. 694 00:22:55,050 --> 00:22:56,460 Sis, no m'interessa. 695 00:22:56,460 --> 00:22:57,810 Vuit, no estic interessat. 696 00:22:57,810 --> 00:22:59,780 Un d'ells és el meu nou número petit. 697 00:22:59,780 --> 00:23:01,470 Així que vaig a recordar on un és. 698 00:23:01,470 --> 00:23:02,534 Tres, no li interessa. 699 00:23:02,534 --> 00:23:03,450 Set, no li interessa. 700 00:23:03,450 --> 00:23:04,530 Cinc, no li interessa. 701 00:23:04,530 --> 00:23:07,390 >> Així que sense caure l'etapa d'aquest any, 702 00:23:07,390 --> 00:23:09,890 Vaig a agafar nombre un-- i el que era el teu nom? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 I si vostè pot unir-se a mi en el principi de la llista, 706 00:23:13,540 --> 00:23:14,870 anem et desanimi a on pertanys. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- ¿com et dius? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan es troba en el camí. 710 00:23:18,191 --> 00:23:23,490 Així que abans de Stefan resol aquest problema, què hem de fer? 711 00:23:23,490 --> 00:23:25,412 Què fem amb Stefan? 712 00:23:25,412 --> 00:23:27,269 >> AUDIÈNCIA: [inaudible]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Així que podríem fer això. 715 00:23:28,850 --> 00:23:31,730 Podríem espècie de prendre Stefan i la seva 4, i només cal posar en una variable 716 00:23:31,730 --> 00:23:33,530 i aferrar-se a ella per una certa quantitat de temps, 717 00:23:33,530 --> 00:23:35,220 fent així espai per al número u. 718 00:23:35,220 --> 00:23:36,280 I això no és dolent. 719 00:23:36,280 --> 00:23:39,270 Que podria suggerir, per què no fer només cal posar Stefan aquí? 720 00:23:39,270 --> 00:23:41,610 Per què podria això violaria un sol de les idees que vam començar 721 00:23:41,610 --> 00:23:44,830 parlant de l'última vegada, la setmana passada? 722 00:23:44,830 --> 00:23:45,330 Sí? 723 00:23:45,330 --> 00:23:45,740 >> AUDIÈNCIA: [inaudible]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: No hi ha índex per a això. 725 00:23:46,860 --> 00:23:49,735 Si vostè pensa en això, de fet, com un matriu, això és com una cosa negativa, 726 00:23:49,735 --> 00:23:52,900 així que no hi ha memòria realitat aquí si aquesta és de fet una matriu, 727 00:23:52,900 --> 00:23:55,090 com hem declarat la setmana passada a la conferència. 728 00:23:55,090 --> 00:23:56,250 Així que no hem de fer això. 729 00:23:56,250 --> 00:23:57,340 Podríem emmagatzemar-lo en una variable. 730 00:23:57,340 --> 00:23:57,820 >> O saps què? 731 00:23:57,820 --> 00:23:59,153 Vaig sentir que algú suggereixi que. 732 00:23:59,153 --> 00:24:01,020 Quina altra cosa podíem fer amb Stefan? 733 00:24:01,020 --> 00:24:03,770 Per què no acaba de desallotjar i el va posar sobre on era el número u. 734 00:24:03,770 --> 00:24:05,170 Així que si vols anar-hi. 735 00:24:05,170 --> 00:24:07,300 I de fet, aquesta és una bastant bona solució. 736 00:24:07,300 --> 00:24:10,480 Ara, per una banda, no tinc classe de fet el problema pitjor. 737 00:24:10,480 --> 00:24:13,650 Quatre és ara més lluny des d'on ha d'estar. 738 00:24:13,650 --> 00:24:14,900 Ha de ser cap a aquest mitjà. 739 00:24:14,900 --> 00:24:16,100 >> Però saps què? 740 00:24:16,100 --> 00:24:17,630 Això podria haver estat mala sort. 741 00:24:17,630 --> 00:24:18,822 Potser el número vuit era aquí. 742 00:24:18,822 --> 00:24:20,530 I per això, potser ho faria han tingut sort, 743 00:24:20,530 --> 00:24:22,460 i empès de vuit més a prop del final. 744 00:24:22,460 --> 00:24:24,710 Així que al final del dia, En certa manera tots mitjana. 745 00:24:24,710 --> 00:24:26,085 No necessitem que es preocupen per quatre. 746 00:24:26,085 --> 00:24:29,400 Tot el que m'importa en aquest moment és seleccionar l'element més petit. 747 00:24:29,400 --> 00:24:32,030 >> I ara, què vaig a fer és oblidar-se de número u 748 00:24:32,030 --> 00:24:35,160 de forma permanent, perquè sé que el llista darrere meu ara ordenades. 749 00:24:35,160 --> 00:24:36,720 Així que la meva llista era prèviament mida 8. 750 00:24:36,720 --> 00:24:37,720 Ara, és de la mida de set. 751 00:24:37,720 --> 00:24:40,340 Així que el meu problema és aconseguir més petit, encara linealment. 752 00:24:40,340 --> 00:24:43,022 Així que ara, vaig a seleccionar el actual element més petit, dues. 753 00:24:43,022 --> 00:24:46,520 Sis, vuit, quatre, tres, set, cinc. 754 00:24:46,520 --> 00:24:47,770 Aquest va ser l'element més petit. 755 00:24:47,770 --> 00:24:49,416 Llavors, què faré con-- ¿Quin era el seu nom? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Josep? 758 00:24:50,085 --> 00:24:52,000 Anem a deixar a Josep al seu lloc. 759 00:24:52,000 --> 00:24:54,842 Ara, vaig a fingir que aquests nois són-- així, 760 00:24:54,842 --> 00:24:56,550 Sé que aquests dos ja estan ordenats. 761 00:24:56,550 --> 00:24:58,424 Ara ens centrarem en la resta de la llista. 762 00:24:58,424 --> 00:25:00,080 Sis és el corrent més petita. 763 00:25:00,080 --> 00:25:01,190 Vuit és més gran. 764 00:25:01,190 --> 00:25:02,970 Quatre és ara el corrent més petita. 765 00:25:02,970 --> 00:25:04,762 Tres és ara el corrent més petita. 766 00:25:04,762 --> 00:25:07,720 I ara, vaig a seleccionar tres, que és-- quin és el teu nom? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, si poguessis gravar el vostre número i d'intercanvi con-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Anem cap enrere, i estem canviarà aquests dos. 772 00:25:15,220 --> 00:25:17,360 I ara, anem a posar això en pilot automàtic. 773 00:25:17,360 --> 00:25:21,589 Vaig a anar i deixar a vostès per seleccionar els següents elements més petits. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Número quatre, ¿què ha de fer? 776 00:25:24,560 --> 00:25:26,261 Excel·lent. 777 00:25:26,261 --> 00:25:27,760 Ara, jo faré un altre passi. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Veig cinc és el immediatament inferior. 780 00:25:31,465 --> 00:25:32,840 Ara, vaig fer un altre pas. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Sis és el més petit. 783 00:25:34,880 --> 00:25:35,520 Bé. 784 00:25:35,520 --> 00:25:36,585 Set és el més petit. 785 00:25:36,585 --> 00:25:37,085 Sense canvis. 786 00:25:37,085 --> 00:25:38,630 Vuit és el més petit. 787 00:25:38,630 --> 00:25:39,170 Fet. 788 00:25:39,170 --> 00:25:43,900 >> Així que el que acabem de fer de forma iterativa seleccionar un element després de l'altra 789 00:25:43,900 --> 00:25:47,230 és posar en pràctica una cosa que estem va formalitzar com a ordenació per selecció. 790 00:25:47,230 --> 00:25:49,120 I és potser fins i tot més simple d'explicar, 791 00:25:49,120 --> 00:25:51,310 en què, literalment, tot el vull fer és mantenir 792 00:25:51,310 --> 00:25:54,700 que van i vénen a través de la llista la selecció, el següent element més petit, 793 00:25:54,700 --> 00:25:55,720 fins que hagi acabat. 794 00:25:55,720 --> 00:25:58,650 >> Pel que és encara més simple, potser intuïtivament, que el passat. 795 00:25:58,650 --> 00:26:00,020 Provem última. 796 00:26:00,020 --> 00:26:03,060 Si vostès podrien restablir mateixos en les següents posicions 797 00:26:03,060 --> 00:26:08,600 per última vegada, anem a veure si no podem ara formalitzar un altre enfocament. 798 00:26:08,600 --> 00:26:12,857 De fet, ho faria algú per aquí agradaria proposar 799 00:26:12,857 --> 00:26:14,440 ¿De quina altra podríem anar fent això? 800 00:26:14,440 --> 00:26:17,439 Sense llançant paraules de moda o tipus de les respostes que ja es coneixen, 801 00:26:17,439 --> 00:26:19,689 simplement intuïtivament, què podíem fer? 802 00:26:19,689 --> 00:26:21,635 >> AUDIÈNCIA: [inaudible]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Sí. 804 00:26:22,510 --> 00:26:24,620 Així que hi ha alguna cosa de gran intuïció allà. 805 00:26:24,620 --> 00:26:28,020 Les bones coses semblen succeir fins al moment en ciències de la computació quan dividim 806 00:26:28,020 --> 00:26:30,832 i conquerir el problema de dividir per la meitat i meitat i meitat. 807 00:26:30,832 --> 00:26:32,540 I així, de fet, ens podria començar a fer això. 808 00:26:32,540 --> 00:26:35,754 I de fet, que serà, anem a veure, una de les nostres millors solucions encara. 809 00:26:35,754 --> 00:26:37,420 Però tornem a la qual en poc temps. 810 00:26:37,420 --> 00:26:40,500 De fet, farem que una mica més tard aquesta setmana. 811 00:26:40,500 --> 00:26:42,180 Què més podríem fer per solucionar això? 812 00:26:42,180 --> 00:26:44,647 Així que aquí tothom està en ordre aparentment aleatori. 813 00:26:44,647 --> 00:26:45,230 Tu saps que? 814 00:26:45,230 --> 00:26:48,320 En lloc d'anar i venir, anada i tornada, d'anada i tornada 815 00:26:48,320 --> 00:26:50,624 cada vegada, això se sent com Estic fent un munt de peu. 816 00:26:50,624 --> 00:26:52,790 Per què no acaba de començar a el principi de la llista, 817 00:26:52,790 --> 00:26:54,960 i només cal posar de quatre que li correspon? 818 00:26:54,960 --> 00:26:59,680 Així que permetin-me assumeixo de moment que la cistella és només aquest primer element. 819 00:26:59,680 --> 00:27:04,937 És de quatre ordenats en aquest moment en el temps, si tot el que m'importa és tot aquí? 820 00:27:04,937 --> 00:27:06,520 Aquesta és una espècie de trivialment cert, ¿no? 821 00:27:06,520 --> 00:27:10,000 Igual que la llista que conté un nombre, i que el número quatre és, òbviament, ordenades. 822 00:27:10,000 --> 00:27:13,070 >> Així que permetin-me estipulo que aquesta llista està ordenada. 823 00:27:13,070 --> 00:27:15,090 Però ara tinc la resta d'aquesta llista. 824 00:27:15,090 --> 00:27:17,240 Així que ara, em trobo amb dos. 825 00:27:17,240 --> 00:27:21,690 D'on ve de dos, òbviament, pertànyer respecte a quatre? 826 00:27:21,690 --> 00:27:22,580 Abans de quatre. 827 00:27:22,580 --> 00:27:23,862 Llavors, què puc fer aquí? 828 00:27:23,862 --> 00:27:24,820 Quin és el teu nom? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Josep, si es pogués fer un pas enrere 831 00:27:26,030 --> 00:27:27,790 per un moment amb el seu número. 832 00:27:27,790 --> 00:27:31,130 I ara el que ha de Stefan fer aquí? 833 00:27:31,130 --> 00:27:33,720 Anem a canviar de lloc Stefan aquí. 834 00:27:33,720 --> 00:27:35,520 I ara, anem a Joseph entrar aquí. 835 00:27:35,520 --> 00:27:39,660 I ara, deixa pretenc que tot el que aquí s'ordena. 836 00:27:39,660 --> 00:27:42,474 Per tant, resultat similar, però una enfocament fonamentalment diferent. 837 00:27:42,474 --> 00:27:44,140 Ni tan sols he mirat el que hi ha allà baix. 838 00:27:44,140 --> 00:27:46,310 Segueixo tenint els elements com se'ls van lliurar a mi, 839 00:27:46,310 --> 00:27:47,240 i tractar amb ells. 840 00:27:47,240 --> 00:27:48,330 >> Així que ara, veig el número sis. 841 00:27:48,330 --> 00:27:51,110 A on pertany número sis? 842 00:27:51,110 --> 00:27:53,250 Tenim dos, quatre, sis. 843 00:27:53,250 --> 00:27:54,800 Exactament on és ara. 844 00:27:54,800 --> 00:27:57,750 Així que deixarem que per si sola, i ara afirmar que aquesta part de la llista 845 00:27:57,750 --> 00:27:58,772 ara està ordenada. 846 00:27:58,772 --> 00:28:01,230 I així, això se sent fonamentalment diferent, ja que només sóc 847 00:28:01,230 --> 00:28:05,230 movent-se a través de la llista aquí linealment, i estic Mai doblegar l'esquena. 848 00:28:05,230 --> 00:28:05,730 Sí. 849 00:28:05,730 --> 00:28:06,230 Tot bé. 850 00:28:06,230 --> 00:28:08,190 Així huit, on pertany vostè? 851 00:28:08,190 --> 00:28:08,730 Aquí mateix. 852 00:28:08,730 --> 00:28:09,310 Perfecte. 853 00:28:09,310 --> 00:28:10,210 Així que ara, un. 854 00:28:10,210 --> 00:28:10,900 UH oh. 855 00:28:10,900 --> 00:28:13,010 Això se sent com si fos serà car. 856 00:28:13,010 --> 00:28:15,690 Ara, en l'algoritme anterior, Jo només vaig canviar persones. 857 00:28:15,690 --> 00:28:18,648 Així que jo li posi tot el camí en al principi, però després es va traslladar a Josep. 858 00:28:18,648 --> 00:28:21,450 Però si em mut Joseph, ara el que va a estar malament? 859 00:28:21,450 --> 00:28:24,250 >> Ara, tinc una mena de undone-- tinc fet un pas cap endavant i després 860 00:28:24,250 --> 00:28:26,300 un pas enrere, perquè ara Joseph estaria fora d'ordre. 861 00:28:26,300 --> 00:28:26,830 Així que anem a fer això. 862 00:28:26,830 --> 00:28:29,150 Si vostè podria prendre el número u i un pas enrere per un moment. 863 00:28:29,150 --> 00:28:30,490 Com podem put-- el era el teu nom? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan en el seu lloc? 866 00:28:32,610 --> 00:28:36,091 Què ha de passar pel que fa a dos, quatre, 06:08? 867 00:28:36,091 --> 00:28:37,570 Tots ells necessiten canviar. 868 00:28:37,570 --> 00:28:42,590 Així que si les huit li agradaria canviar primer, després sis, després quatre, després dos. 869 00:28:42,590 --> 00:28:45,380 I llavors Annan, si ho agradaria venir aquí, bé. 870 00:28:45,380 --> 00:28:47,760 Però aquí, acabem de tipus de pagat un preu 871 00:28:47,760 --> 00:28:49,510 en un punt diferent en l'algoritme. 872 00:28:49,510 --> 00:28:52,550 Mentre que l'última vegada amb la selecció espècie, i fins i tot una mena de bombolla, 873 00:28:52,550 --> 00:28:54,700 Estic caminant cap enrere i endavant, enrere i endavant, 874 00:28:54,700 --> 00:28:58,360 que sens dubte és la suma de pel que fa a temps, i, literalment, pas a pas. 875 00:28:58,360 --> 00:29:00,660 >> L'ordenació per inserció, en un primer moment vista, sembla que és 876 00:29:00,660 --> 00:29:05,150 súper intel·ligent, perquè jo només sóc fer, el progrés gradual lent, 877 00:29:05,150 --> 00:29:07,120 però jo no vaig aquesta anada i tornada. 878 00:29:07,120 --> 00:29:09,410 Però si algú és de fet fora d'ordre, notificació 879 00:29:09,410 --> 00:29:10,840 tota la feina que havia de fer. 880 00:29:10,840 --> 00:29:14,750 Vaig haver de moure la meitat de la llista només per fer espai per al número u. 881 00:29:14,750 --> 00:29:16,790 Així que és la mateixa quantitat de treball fins al moment es 882 00:29:16,790 --> 00:29:18,690 sent, simplement un tipus diferent de treball. 883 00:29:18,690 --> 00:29:19,370 >> Continuem. 884 00:29:19,370 --> 00:29:22,657 Així que ara que sabem que tothom entre un i vuit són ordenats. 885 00:29:22,657 --> 00:29:23,740 Aquí, no tinc el número tres. 886 00:29:23,740 --> 00:29:25,864 Si t'agrada per recollir número tres, un pas enrere un. 887 00:29:25,864 --> 00:29:28,260 ¿I què és el que vostès necessiten fer? 888 00:29:28,260 --> 00:29:28,760 Sí. 889 00:29:28,760 --> 00:29:33,070 Així que aquesta és una altra d'una, dues, tres passos. 890 00:29:33,070 --> 00:29:36,010 Tres unitats de temps que només costen mi, així que 3 ara puc encaixar. 891 00:29:36,010 --> 00:29:37,460 Finalment, set. 892 00:29:37,460 --> 00:29:39,730 >> Seguirem endavant i tenir vostè pren un pas enrere. 893 00:29:39,730 --> 00:29:42,780 Això només ens costarà una unitat de temps, però això està bé. 894 00:29:42,780 --> 00:29:44,170 I ara, cinc d'anar a ser una mica més car. 895 00:29:44,170 --> 00:29:45,340 Si voleu fer un pas enrere. 896 00:29:45,340 --> 00:29:48,380 Hem de passar vuit, i 7, i sis. 897 00:29:48,380 --> 00:29:50,749 I llavors tothom està ara ordenades. 898 00:29:50,749 --> 00:29:52,290 Així que una gran part dels nostres voluntaris aquí. 899 00:29:52,290 --> 00:29:53,554 Moltes gràcies. 900 00:29:53,554 --> 00:29:56,220 >> [Aplaudiments] 901 00:29:56,220 --> 00:29:56,860 >> Gràcies a tots. 902 00:29:56,860 --> 00:29:57,520 Gràcies a tots. 903 00:29:57,520 --> 00:30:02,940 Així que anem a veure ara com costosa tot això era. 904 00:30:02,940 --> 00:30:06,210 Anem a considerar potser la més simple d'aquests, ordenament de bombolla. 905 00:30:06,210 --> 00:30:09,950 I dic més simple, només perquè es pot resoldre amb avidesa per només 906 00:30:09,950 --> 00:30:11,660 solucionar el problema per parelles aquí. 907 00:30:11,660 --> 00:30:13,720 Solucionar el problema de parells aquí, una i altra vegada 908 00:30:13,720 --> 00:30:17,680 i de nou, repetint com molts vegades que realment necessiten. 909 00:30:17,680 --> 00:30:21,050 >> Així resulta que amb una mena de bombolla, bé, 910 00:30:21,050 --> 00:30:25,820 quants passos he d'assumir la primera passada d'aquest algorisme? 911 00:30:25,820 --> 00:30:30,850 Podria take-- anem a veure- un, dos, tres, quatre, cinc, sis, set. 912 00:30:30,850 --> 00:30:32,190 I hi ha vuit elements aquí. 913 00:30:32,190 --> 00:30:35,280 Així que és com n menys passos d'1 a arribar des del principi de la llista 914 00:30:35,280 --> 00:30:36,380 fins al final de la llista. 915 00:30:36,380 --> 00:30:41,350 >> Però amb la selecció espècie, recordo que sóc la selecció dels elements d'una i altra vegada 916 00:30:41,350 --> 00:30:44,590 i una altra que és més petit, Estic posant en el seu lloc, 917 00:30:44,590 --> 00:30:46,616 però llavors jo no sóc mirant darrere meu una altra vegada. 918 00:30:46,616 --> 00:30:49,490 Així que crec que és una mica més clara a continuació, que la primera vegada, jo podria 919 00:30:49,490 --> 00:30:52,680 ha de prendre tot n menys passos d'1 per trobar l'element més petit. 920 00:30:52,680 --> 00:30:55,920 Llavors els vaig posar al seu lloc, i jo desallotjar tot el que estava aquí abans. 921 00:30:55,920 --> 00:30:57,500 >> Però llavors jo no he de seguir buscant en aquest element, 922 00:30:57,500 --> 00:30:59,040 perquè jo sé que és i als més petits. 923 00:30:59,040 --> 00:31:01,581 Així que ara, puc mirar a només set elements, llavors sis elements, 924 00:31:01,581 --> 00:31:03,290 a continuació, cinc elements, després quatre elements. 925 00:31:03,290 --> 00:31:06,900 I així, matemàticament, si n és el nombre d'elements o números 926 00:31:06,900 --> 00:31:11,990 que vam començar amb, es pot imaginar que aquest és el mateix que n menys 1, 927 00:31:11,990 --> 00:31:14,250 més n menys 2 passos, més n menys 3 passos, 928 00:31:14,250 --> 00:31:16,780 més n menys 4 passos, tot el fins arribar a un sol pas. 929 00:31:16,780 --> 00:31:18,160 I estic en la meva última persona. 930 00:31:18,160 --> 00:31:20,650 >> I si vostè recorda que una gran quantitat Estadístiques de llibres o llibres de matemàtiques 931 00:31:20,650 --> 00:31:24,730 tenir aquestes fórmules en el tapa dura enrere o davant d'ells, 932 00:31:24,730 --> 00:31:27,690 resulta que aquesta sèrie pot expressar-se més senzillament 933 00:31:27,690 --> 00:31:28,857 com n vegades n almenys 1 sobre 2. 934 00:31:28,857 --> 00:31:31,273 I està bé si això no és a l'avantguarda de la seva ment. 935 00:31:31,273 --> 00:31:32,420 Però això és cert. 936 00:31:32,420 --> 00:31:34,449 Això és només una manera més senzilla d'escriure. 937 00:31:34,449 --> 00:31:36,240 I llavors si vostè pensa de nou a l'escola primària, 938 00:31:36,240 --> 00:31:38,698 quan acaba de començar a multiplicar coses fora, això, per descomptat, 939 00:31:38,698 --> 00:31:41,820 és simplement n al quadrat almenys n dividit per 2. 940 00:31:41,820 --> 00:31:44,772 L'únic que he fet és ampliar les expressions allà. 941 00:31:44,772 --> 00:31:46,730 I així anem a reescriure aquesta una mica diferent. 942 00:31:46,730 --> 00:31:49,780 Això n al quadrat dividit per 2 menys n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Així que de nou, jo sóc només una mica de l'aplicació una mica d'aritmètica governa allà. 944 00:31:53,270 --> 00:31:57,140 Però noti ara que el major termini En aquesta expressió, per així dir-ho, 945 00:31:57,140 --> 00:31:58,540 és que n al quadrat. 946 00:31:58,540 --> 00:32:02,910 Així que sí, és n al quadrat dividit per 2, menys n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Però, en general, si n és serà un gran valor, 948 00:32:05,080 --> 00:32:08,740 Vaig a dir que n al quadrat va ser el factor dominant. 949 00:32:08,740 --> 00:32:10,490 És només serà un contribuent més gran 950 00:32:10,490 --> 00:32:12,877 amb el nombre de passos que n / 2. 951 00:32:12,877 --> 00:32:13,960 Llavors, què vull dir amb això? 952 00:32:13,960 --> 00:32:16,795 Provem un exemple senzill, fins i tot tot i que les matemàtiques aconsegueix una mica gran. 953 00:32:16,795 --> 00:32:20,210 >> Així que suposem que tenim 1 milió de persones a l'escenari, o 1 milió de coses 954 00:32:20,210 --> 00:32:21,320 que volem ordenar. 955 00:32:21,320 --> 00:32:23,730 Anem a endoll d'un milió exactament en aquesta fórmula 956 00:32:23,730 --> 00:32:27,230 per veure la quantitat de passos que pren total de per ordenar un milió d'elements mitjançant per exemple, 957 00:32:27,230 --> 00:32:28,560 ordenació per selecció. 958 00:32:28,560 --> 00:32:30,760 >> Així tindríem la mateixa fórmula que abans. 959 00:32:30,760 --> 00:32:34,120 Em connecto un milió, pel que tinc un milió al quadrat dividit per 2, 960 00:32:34,120 --> 00:32:35,990 menys d'un milió dividit per 2. 961 00:32:35,990 --> 00:32:40,180 Si faig això matemàtiques per endavant aquí, tenim 500.000.000.000 962 00:32:40,180 --> 00:32:47,460 menys 500.000, que ens dóna 499999500000, 963 00:32:47,460 --> 00:32:49,270 que és bastant maleït gran. 964 00:32:49,270 --> 00:32:54,370 >> De fet, si es compara ara 499000000000, 999.000.000, 965 00:32:54,370 --> 00:33:01,210 500.000 contra el nostre valor original, 500.000.000.000, és tan condemnadament prop. 966 00:33:01,210 --> 00:33:06,850 Oi? n al quadrat dividit per 2 dóna nosaltres-- o més aviat, n al quadrat dividit per 2 967 00:33:06,850 --> 00:33:08,370 ens donar 500 mil milions. 968 00:33:08,370 --> 00:33:13,510 Això és bastant maleït prop a 499999500000, 969 00:33:13,510 --> 00:33:17,970 és a dir, restant off 500000, o, més generalment, restant off 970 00:33:17,970 --> 00:33:20,010 n al quadrat, no és realment un gran problema. 971 00:33:20,010 --> 00:33:22,490 El major al quadrat fa que aquests nombres creixen molt ràpid. 972 00:33:22,490 --> 00:33:25,790 >> Ara, això és important només en la mesura com nosaltres, com els informàtics, 973 00:33:25,790 --> 00:33:29,350 generalment no es va a importar molt sobre els matisos d'aquestes fórmules 974 00:33:29,350 --> 00:33:31,400 i exactament el que el respostes precises. 975 00:33:31,400 --> 00:33:33,390 Ens preocupem només això, saps què? 976 00:33:33,390 --> 00:33:37,810 Al final del dia, aquesta fórmula és de l'ordre de n al quadrat. 977 00:33:37,810 --> 00:33:39,350 >> Sí, estem dividint per 2 en aquest país. 978 00:33:39,350 --> 00:33:41,360 Sí, estem restant fora n almenys 2. 979 00:33:41,360 --> 00:33:46,860 Però al final del dia, el terme que realment ens fa mal i ens costa 980 00:33:46,860 --> 00:33:48,995 un munt de passos és aquest terme quadrat. 981 00:33:48,995 --> 00:33:51,370 I així el que un científic de la computació es va a fer en general 982 00:33:51,370 --> 00:33:54,160 és ignorar tots els termes d'ordre més petits, 983 00:33:54,160 --> 00:33:56,900 i només cal veure què contribueix més al cost. 984 00:33:56,900 --> 00:34:00,530 >> I això és bo, perquè podem ara parlar en molt major generalitat 985 00:34:00,530 --> 00:34:02,470 sobre algoritmes, i pot comparar-los. 986 00:34:02,470 --> 00:34:04,550 I el fet que sóc l'ús d'aquesta O és deliberat. 987 00:34:04,550 --> 00:34:06,680 Quan dic que en l'ordre de, estic específicament 988 00:34:06,680 --> 00:34:09,560 es refereix a alguna cosa anomenat gran O. I gran O 989 00:34:09,560 --> 00:34:14,090 és una notació que un ordinador científic utilitza per descriure 990 00:34:14,090 --> 00:34:16,710 un límit superior en alguna cosa. 991 00:34:16,710 --> 00:34:21,150 >> Així que si vostè diu que un algoritme és en gran O de n al quadrat, 992 00:34:21,150 --> 00:34:23,380 com he proposat només un Fa moment, que els mitjans 993 00:34:23,380 --> 00:34:27,710 que en termes del seu funcionament temps o la seva eficiència, 994 00:34:27,710 --> 00:34:30,090 que es necessita en l'ordre de n quadrat passos. 995 00:34:30,090 --> 00:34:31,420 Potser més, potser menys. 996 00:34:31,420 --> 00:34:33,435 Però és de l'ordre de n al quadrat. 997 00:34:33,435 --> 00:34:34,560 I aquest és el límit superior. 998 00:34:34,560 --> 00:34:36,530 No serà més dolorós que això. 999 00:34:36,530 --> 00:34:40,800 No serà n en cubs o 2 a la n, o alguna cosa molt més gran. 1000 00:34:40,800 --> 00:34:43,800 Aquesta és una fita superior en el que el cost és. 1001 00:34:43,800 --> 00:34:46,150 Així que tenint en compte que, anem a considerar només alguns exemples. 1002 00:34:46,150 --> 00:34:49,820 I això és només una llista finita temps d'execució dels molt comuns 1003 00:34:49,820 --> 00:34:52,870 per als algoritmes que està destinat a ser il·lustratiu d'algunes coses que hem 1004 00:34:52,870 --> 00:34:53,600 ja s'ha vist. 1005 00:34:53,600 --> 00:34:58,060 >> Així, per exemple, en el cas de ordenació per selecció, el que estic dient aquí 1006 00:34:58,060 --> 00:35:02,250 és en execució que la selecció d'espècie el temps és de l'ordre de n al quadrat. 1007 00:35:02,250 --> 00:35:06,260 En el pitjor dels casos, tindré un munt de nombres aleatoris aquí. 1008 00:35:06,260 --> 00:35:08,600 I com hem vist matemàticament, si segueixo caminant 1009 00:35:08,600 --> 00:35:11,310 a través de la llista, a través de la llista, seleccionant l'immediatament inferior 1010 00:35:11,310 --> 00:35:14,410 element i una altra, si jo realitat anoti tots els passos 1011 00:35:14,410 --> 00:35:18,750 Estic prenent com vaig proposar formulaically abans, és de l'ordre de n al quadrat 1012 00:35:18,750 --> 00:35:20,370 mesures que estic prenent. 1013 00:35:20,370 --> 00:35:24,520 >> I resulta que la bombolla classificació i ordenació per inserció 1014 00:35:24,520 --> 00:35:27,370 són tan lent en el pitjor dels casos. 1015 00:35:27,370 --> 00:35:32,040 Considerem, per exemple, l'ordenació per inserció, l'últim algoritme amb el qual tractem, 1016 00:35:32,040 --> 00:35:35,500 que tenien ens fixem en l'element, i després inserir on pertany. 1017 00:35:35,500 --> 00:35:38,720 I després ens fixem en el següent element, i s'insereix on pertany. 1018 00:35:38,720 --> 00:35:40,990 >> Així que considera el millor escenari possible. 1019 00:35:40,990 --> 00:35:45,590 Suposem que jo tenia els meus voluntaris alinear literalment així, un al vuit, 1020 00:35:45,590 --> 00:35:47,440 ja ordenats. 1021 00:35:47,440 --> 00:35:51,300 Quants passos és l'ordenació per inserció va a prendre per ordenar a vuit persones, 1022 00:35:51,300 --> 00:35:55,640 si arriben a l'escenari buscant d'aquesta manera? 1023 00:35:55,640 --> 00:35:57,410 >> Vuit persones ja ordenats. 1024 00:35:57,410 --> 00:35:58,760 I ús ordenació per inserció. 1025 00:35:58,760 --> 00:36:02,180 L'últim dels algoritmes. 1026 00:36:02,180 --> 00:36:03,640 Bé, anem a recrear ràpid real. 1027 00:36:03,640 --> 00:36:05,504 Així que si em poso aquí, ho veig. 1028 00:36:05,504 --> 00:36:06,420 Per on pertanyen? 1029 00:36:06,420 --> 00:36:07,730 Pertany aquí. 1030 00:36:07,730 --> 00:36:08,330 Veig dues. 1031 00:36:08,330 --> 00:36:09,660 D'on ve dos pertanyen? 1032 00:36:09,660 --> 00:36:10,260 Aquí mateix. 1033 00:36:10,260 --> 00:36:10,900 Veig 03:00. 1034 00:36:10,900 --> 00:36:11,920 D'on ve tres pertanyen? 1035 00:36:11,920 --> 00:36:12,480 Aquí mateix. 1036 00:36:12,480 --> 00:36:13,100 >> Veig 04:00. 1037 00:36:13,100 --> 00:36:13,600 Aquí mateix. 1038 00:36:13,600 --> 00:36:15,660 Cinc, sis, set, vuit. 1039 00:36:15,660 --> 00:36:17,320 No hi ha raó per repetir a mi mateix. 1040 00:36:17,320 --> 00:36:21,260 I així, el nombre de passos és que en termes de n? 1041 00:36:21,260 --> 00:36:23,870 És de l'ordre de n passos, oi? n almenys 1. 1042 00:36:23,870 --> 00:36:27,567 Però vaig prendre una sèrie lineal de passos, i ara he acabat. 1043 00:36:27,567 --> 00:36:28,900 Així que aquest és el millor dels casos, però. 1044 00:36:28,900 --> 00:36:29,983 I el pitjor dels casos? 1045 00:36:29,983 --> 00:36:32,730 El que vuit eren d'allà, i set eren allà baix, 1046 00:36:32,730 --> 00:36:35,840 i un i dos eren d'aquí, de manera que que la llista s'invertís en veritat? 1047 00:36:35,840 --> 00:36:38,300 >> Bé, el que passa de fet si aquest és el nombre? 1048 00:36:38,300 --> 00:36:41,300 I farem només un parell d'exemples. 1049 00:36:41,300 --> 00:36:49,300 Què passaria si, de fet, el número vuit és aquí, i els crits number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 ¿I què si, de fet, el nombre vuit és tot el camí fins aquí, 1052 00:36:56,430 --> 00:36:57,790 i estic fent servir l'ordenació per inserció? 1053 00:36:57,790 --> 00:36:58,290 >> D'ACORD. 1054 00:36:58,290 --> 00:37:00,280 Reclam en aquest moment està al seu lloc. 1055 00:37:00,280 --> 00:37:03,152 Però ara, seven-- on van set anys? 1056 00:37:03,152 --> 00:37:04,360 Per descomptat, no cal aquí. 1057 00:37:04,360 --> 00:37:06,760 Així que he de moure i vuit més d'un lloc. 1058 00:37:06,760 --> 00:37:08,554 Ara 6:00, cap a on va? 1059 00:37:08,554 --> 00:37:09,220 Bé, està bé. 1060 00:37:09,220 --> 00:37:13,150 Ara, he de moure i vuit més un lloc i 7 més d'un lloc, 1061 00:37:13,150 --> 00:37:14,440 i després em deixo caure 6. 1062 00:37:14,440 --> 00:37:16,870 >> Així que la primera vegada, el cost mi un pas d'arreglar les coses, 1063 00:37:16,870 --> 00:37:18,570 llavors em va costar dos passos per arreglar les coses. 1064 00:37:18,570 --> 00:37:20,370 Quants passos és va a prendre per solucionar 1065 00:37:20,370 --> 00:37:22,720 coses per posar cinc en el lloc correcte? 1066 00:37:22,720 --> 00:37:23,340 Tres. 1067 00:37:23,340 --> 00:37:29,520 Perquè ara he de moure un, dos, tres. 1068 00:37:29,520 --> 00:37:32,430 Quants passos es prendrà posar quatre en el lloc correcte? 1069 00:37:32,430 --> 00:37:36,040 4 i 5, a més de 6, més 7. 1070 00:37:36,040 --> 00:37:40,260 >> I el que és matemàticament idèntica a el que hem descrit per a la selecció de gènere. 1071 00:37:40,260 --> 00:37:42,130 Tenim aquesta sèrie això és només l'augment. 1072 00:37:42,130 --> 00:37:45,650 1 més 2 més 3 més 4, o per contra, 7 més 6 1073 00:37:45,650 --> 00:37:52,610 més 5 més 4 afegeix avui de efectes a l'ordre de n al quadrat. 1074 00:37:52,610 --> 00:37:57,640 >> Així que permetin-me estipulo també que ordenament de bombolla és també n al quadrat. 1075 00:37:57,640 --> 00:38:01,340 Perquè amb ordenament de bombolla, cada vegada que vaig per la llista, 1076 00:38:01,340 --> 00:38:03,100 Estic prenent més o menys quants passos? 1077 00:38:03,100 --> 00:38:06,260 Cada vegada que, literalment, caminar des d'allà fins allà? 1078 00:38:06,260 --> 00:38:07,960 Al voltant de n passos. 1079 00:38:07,960 --> 00:38:12,650 Però quantes vegades pot ocórrer de passar per la llista? 1080 00:38:12,650 --> 00:38:13,920 >> Bé, més o menys n temps. 1081 00:38:13,920 --> 00:38:15,680 Potser n menys 1, però més o menys n vegades. 1082 00:38:15,680 --> 00:38:16,430 Bé, per què és això? 1083 00:38:16,430 --> 00:38:19,560 Bé, amb la bombolla del tipus, si partim d'ordenament de bombolla, 1084 00:38:19,560 --> 00:38:23,570 amb la llista en la pitjor possible situació, que de nou és completament 1085 00:38:23,570 --> 00:38:25,550 al revés, el que passarà? 1086 00:38:25,550 --> 00:38:28,830 Vaig a través de la llista, i el nombre de un pertany tot el camí per allà. 1087 00:38:28,830 --> 00:38:33,280 >> Però amb la bombolla del tipus, fins on pot un passar el meu primer pas a través de la llista? 1088 00:38:33,280 --> 00:38:36,620 Quants punts és el que obté més a prop de el lloc correcte? 1089 00:38:36,620 --> 00:38:37,240 Només un. 1090 00:38:37,240 --> 00:38:40,281 Així que si vostè tipus de raó a través d'aquest, cada vegada que a través d'aquest algoritme, 1091 00:38:40,281 --> 00:38:41,880 Tenint aproximadament n passos de David. 1092 00:38:41,880 --> 00:38:44,940 Però, quants passis a través de la llista és que 1093 00:38:44,940 --> 00:38:49,060 va a prendre perquè un de bombolles a l'esquerra on pertany? 1094 00:38:49,060 --> 00:38:51,840 >> Ell ha de moure com, n espais d'aquesta manera. 1095 00:38:51,840 --> 00:38:57,960 Així que per fer la classificació de la llista, He d'anar i venir n vegades. 1096 00:38:57,960 --> 00:39:01,540 I cada vegada, estic mirant a n elements. 1097 00:39:01,540 --> 00:39:05,410 El mateix passa amb les coses n n vegades en de l'ordre de n al quadrat. 1098 00:39:05,410 --> 00:39:07,220 >> Ara, anem a veure d'alguna dels curts que 1099 00:39:07,220 --> 00:39:10,440 s'incrusten en el següent problema de CS50 establir, un altre enfocament a aquests, 1100 00:39:10,440 --> 00:39:13,490 però per ara, considerarem altres vegades s'executen, 1101 00:39:13,490 --> 00:39:16,840 especialment si els prenen de classificació una mica de temps per a enfonsar-se en. 1102 00:39:16,840 --> 00:39:21,790 Què és un algorisme que hem vist ja que porta l'ordre de n passos? 1103 00:39:21,790 --> 00:39:27,560 >> Què s'ha de prendre una sèrie lineal dels passos que hem vist fins ara? 1104 00:39:27,560 --> 00:39:29,350 Què és això? 1105 00:39:29,350 --> 00:39:30,480 La recerca en el directori telefònic. 1106 00:39:30,480 --> 00:39:31,390 El primer algorisme. 1107 00:39:31,390 --> 00:39:31,560 Oi? 1108 00:39:31,560 --> 00:39:33,650 On som linealment la recerca de Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 En efecte. 1110 00:39:34,150 --> 00:39:37,180 Des de la setmana zero, quan vaig començar convertir una pàgina alhora, 1111 00:39:37,180 --> 00:39:40,095 i fins i tot li vaig dir que era una espècie d'un algoritme sensació lineal, 1112 00:39:40,095 --> 00:39:42,720 i vam tenir aquesta foto a la tauler amb la línia vermella directa 1113 00:39:42,720 --> 00:39:44,678 i el groc recta línia, aquests eren de fet 1114 00:39:44,678 --> 00:39:46,810 algoritmes que són en gran O de n. 1115 00:39:46,810 --> 00:39:50,680 >> Perquè per trobar Mike Smith en un telèfon llibre de n pàgines, en el pitjor dels casos, 1116 00:39:50,680 --> 00:39:52,422 me n mesures podria prendre. 1117 00:39:52,422 --> 00:39:53,630 Què hi ha de prendre assistència? 1118 00:39:53,630 --> 00:39:55,790 Un, dos, tres, quatre, cinc, sis. 1119 00:39:55,790 --> 00:39:59,420 Què és el temps d'execució de la present algoritme per a la presa d'assistència? 1120 00:39:59,420 --> 00:40:03,070 O gran de n, ja que en teoria em has de apuntar tots a la sala. 1121 00:40:03,070 --> 00:40:05,861 >> Ara com un a part, què passa amb la una altra optimització de setmana zero? 1122 00:40:05,861 --> 00:40:08,117 Dos, quatre, sis, vuit, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Un científic de la computació ho faria adonar-se'n, esperi un minut, 1124 00:40:10,200 --> 00:40:12,320 això és de l'ordre de n dividit per dos passos. 1125 00:40:12,320 --> 00:40:12,820 Oi? 1126 00:40:12,820 --> 00:40:14,444 A causa de que estic fent dues persones alhora. 1127 00:40:14,444 --> 00:40:17,015 Però anem a ignorar els termes d'ordre inferior, 1128 00:40:17,015 --> 00:40:19,140 i nosaltres només anem a llençar la divideix per 2, 1129 00:40:19,140 --> 00:40:21,830 i dir, gran O de n perquè l'algoritme també. 1130 00:40:21,830 --> 00:40:22,760 >> Què tal aquest? 1131 00:40:22,760 --> 00:40:26,170 Ens saltarem sobre alguns d'ells, però el que era un algoritme que era log de n? 1132 00:40:26,170 --> 00:40:29,900 Que va tenir més o menys log n passos? 1133 00:40:29,900 --> 00:40:30,870 El divideix i venceràs. 1134 00:40:30,870 --> 00:40:31,369 Exactament. 1135 00:40:31,369 --> 00:40:33,900 Igual que l'exemple de llibre de telèfon en setmana zero i el dia d'avui, 1136 00:40:33,900 --> 00:40:36,191 on ens vam dividir el problema una i altra vegada i una altra. 1137 00:40:36,191 --> 00:40:39,070 Dibuixem a la pissarra a la setmana zero com una línia verda corbat, 1138 00:40:39,070 --> 00:40:41,460 i ens va dir aquell dia que era un algoritme logarítmic. 1139 00:40:41,460 --> 00:40:44,970 >> I de fet, el nombre de passos que porta a terme divideix i venceràs, 1140 00:40:44,970 --> 00:40:48,610 o recerca binària com començarem cridant, com en la guia telefònica, 1141 00:40:48,610 --> 00:40:50,680 és de l'ordre de registre i passos. 1142 00:40:50,680 --> 00:40:52,470 I això és una mica d'un ésser estrany. 1143 00:40:52,470 --> 00:40:54,910 >> El que dóna un pas, o més específicament 1144 00:40:54,910 --> 00:40:56,240 un nombre constant de passos? 1145 00:40:56,240 --> 00:40:58,865 Potser sigui de dos, potser és tres, però un informàtic sol 1146 00:40:58,865 --> 00:41:01,423 simplifica tan gran O d'1, un nombre constant de passos. 1147 00:41:01,423 --> 00:41:04,256 Què és una cosa que podria fer que pren un nombre constant de passos? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Quin és el temps d'execució d'aplaudir? 1150 00:41:10,930 --> 00:41:11,920 Constant de temps. 1151 00:41:11,920 --> 00:41:12,420 Oi? 1152 00:41:12,420 --> 00:41:15,490 Igual que, quin és el temps de funcionament del fer qualsevol cosa que pren només una 1153 00:41:15,490 --> 00:41:18,570 operació, com imprimir F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Això podria dir-se que la constant de temps, menys que menys cas cantonada amb la impressió M, 1155 00:41:24,110 --> 00:41:28,260 el que podria el temps d'execució d'impressió F realitat sigui? 1156 00:41:28,260 --> 00:41:28,790 I per què? 1157 00:41:28,790 --> 00:41:30,550 Què és la n de mesurament en aquest cas? 1158 00:41:30,550 --> 00:41:32,251 >> AUDIÈNCIA: [inaudible]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Exactament. 1160 00:41:33,250 --> 00:41:34,900 El nombre de caràcters volem imprimir. 1161 00:41:34,900 --> 00:41:36,191 Així que és molt sensible al context. 1162 00:41:36,191 --> 00:41:39,910 Avui, ens hem centrat molt en les lletres i els números aquí al tauler. 1163 00:41:39,910 --> 00:41:43,540 Però també podria ser personatges d'una cadena real. 1164 00:41:43,540 --> 00:41:46,420 Així que resulta que hi ha un altre mesura que començarà a preocupar-se, 1165 00:41:46,420 --> 00:41:48,530 i això és tot el contrari de gran O, per dir-ho així. 1166 00:41:48,530 --> 00:41:50,120 >> Aquesta és la notació omega. 1167 00:41:50,120 --> 00:41:53,380 Mentre que gran O significa el que és, la límit superior del seu temps de funcionament? 1168 00:41:53,380 --> 00:41:55,580 Com a màxim, la quantitat de temps podria prendre alguna cosa? 1169 00:41:55,580 --> 00:41:59,250 Omega-- sento això segueix arribant up-- és el contrari d'això, 1170 00:41:59,250 --> 00:42:02,960 mitjançant el qual es tracta d'un límit inferior en el quantitat de temps que alguna cosa podria prendre. 1171 00:42:02,960 --> 00:42:10,480 >> So. per exemple, què és un algoritme que prengui mesures sempre n al quadrat? 1172 00:42:10,480 --> 00:42:15,600 Bé, un dels algoritmes que he vist Avui en dia, de fet, podria ser que també. 1173 00:42:15,600 --> 00:42:16,720 Selecció tipus. 1174 00:42:16,720 --> 00:42:18,270 Selecció espècie és bastant estúpid. 1175 00:42:18,270 --> 00:42:21,760 Fins i tot si la sento algorithm--, tot i si la matriu ja està ordenat, 1176 00:42:21,760 --> 00:42:24,150 ordenació per selecció va seguir caminant per la llista 1177 00:42:24,150 --> 00:42:28,907 per assegurar-se que compta amb el més petit element d'una i altra i una altra. 1178 00:42:28,907 --> 00:42:31,740 I tot i que els éssers humans en el públic sàpiga que, espera un minut, 1179 00:42:31,740 --> 00:42:33,948 que ja va passar el element més petit, l'ordinador 1180 00:42:33,948 --> 00:42:37,300 no sap que fins que es vegi tot el camí a través de la llista. 1181 00:42:37,300 --> 00:42:40,240 De la mateixa manera, una cota inferior que també pot ser tingut en compte 1182 00:42:40,240 --> 00:42:42,000 podria ser el moment lineal. 1183 00:42:42,000 --> 00:42:48,260 >> Quant de temps es triga a ordenar n elements en la millor 1184 00:42:48,260 --> 00:42:52,420 cas usant una mena com una mena de bombolla? 1185 00:42:52,420 --> 00:42:54,280 Suposem que la llista ja està ordenat. 1186 00:42:54,280 --> 00:42:56,696 Vam dir bombolla espècie adquireix de l'ordre de n al quadrat passos. 1187 00:42:56,696 --> 00:42:59,640 Però el que si ja està ordenada? 1188 00:42:59,640 --> 00:43:02,310 ¿I si et dones compte després un pas a través de la matriu 1189 00:43:02,310 --> 00:43:03,540 que vostè ha fet no hi ha permutes? 1190 00:43:03,540 --> 00:43:05,970 És necessari seguir fent més passades? 1191 00:43:05,970 --> 00:43:06,470 >> No. 1192 00:43:06,470 --> 00:43:10,340 Així que un límit inferior en l'ordenament de bombolla podria dir-se que és lineal. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 I podem veure altres d'aquests també. 1195 00:43:14,450 --> 00:43:17,990 Així que anem a fer una ullada ràpida en tot just una visualització aquí 1196 00:43:17,990 --> 00:43:20,790 per veure com aquestes es distingeixen. 1197 00:43:20,790 --> 00:43:24,592 Vaig a anar per aquí a aquesta pàgina que està disponible a la pàgina web de C50, 1198 00:43:24,592 --> 00:43:27,550 però va ser un mal per aconseguir feina, ja que utilitza una tecnologia anomenada 1199 00:43:27,550 --> 00:43:30,560 Els applets de Java, que és un en gran mesura sense suport en aquests dies, 1200 00:43:30,560 --> 00:43:32,730 almenys per crom i alguns altres. 1201 00:43:32,730 --> 00:43:37,070 >> I me n'aniré endavant i accelerar aquest i explicar el que està passant. 1202 00:43:37,070 --> 00:43:40,840 Aquesta és una demostració de la bombolla espècie, el primer algoritme ens va mirar. 1203 00:43:40,840 --> 00:43:43,950 I és una visualització en què cada d'aquestes barres representa un nombre. 1204 00:43:43,950 --> 00:43:45,710 Com més gran sigui la barra, com més gran sigui el nombre. 1205 00:43:45,710 --> 00:43:47,520 Com més baix sigui la barra, com menor sigui el nombre. 1206 00:43:47,520 --> 00:43:50,353 ¿I què es pot veure visualment, fins i tot encara que això va molt ràpid, 1207 00:43:50,353 --> 00:43:53,699 és que la barra vermella és com jo, caminant cap enrere i fixar successivament problemes. 1208 00:43:53,699 --> 00:43:56,740 Es pot veure que els elements més grans són de fet bombollejant cap a la dreta, 1209 00:43:56,740 --> 00:43:59,650 i els elements més petits estan bombollejant cap a l'esquerra. 1210 00:43:59,650 --> 00:44:01,870 I aquí, si realment mirar més de prop, 1211 00:44:01,870 --> 00:44:04,330 realment podem comptar el nombre de comparacions i swaps 1212 00:44:04,330 --> 00:44:05,350 que s'estaven fent. 1213 00:44:05,350 --> 00:44:07,360 >> Però en lloc, donem una ullada en el segon algoritme 1214 00:44:07,360 --> 00:44:11,240 hem vist abans amb la nostra voluntaris, selecció d'ordenar. 1215 00:44:11,240 --> 00:44:13,500 Visualment, té una molt diferent efecte. 1216 00:44:13,500 --> 00:44:16,820 Però és, de nou, molt intuïtiva, en que guardem la selecció de la pròxima més petita 1217 00:44:16,820 --> 00:44:18,660 element, i ens van donar una mica de sort. 1218 00:44:18,660 --> 00:44:20,110 Això es va sentir fonamentalment més ràpid. 1219 00:44:20,110 --> 00:44:22,840 Però si ens trobem una i altra vegada i una altra vegada amb una gran quantitat d'entrades, 1220 00:44:22,840 --> 00:44:26,680 veuríem que és de fet encara en gran O de n al quadrat. 1221 00:44:26,680 --> 00:44:29,920 >> Anem a fer un últim d'un aquí, l'ordenació per inserció, 1222 00:44:29,920 --> 00:44:33,180 que va ser el tercer algoritme ens vam mirar, i el record 1223 00:44:33,180 --> 00:44:36,700 que aquest s'ocupa de la elements, ja que els troba, 1224 00:44:36,700 --> 00:44:39,290 Però llavors potser torns les coses per a fer lloc, 1225 00:44:39,290 --> 00:44:41,660 la inserció d'elements que pertanyen. 1226 00:44:41,660 --> 00:44:45,330 >> I això també acaba donant la resultat final. Ara els tres dels 1227 00:44:45,330 --> 00:44:46,490 vaig sentir bastant ràpid. 1228 00:44:46,490 --> 00:44:48,740 I, de fet, jo els vaig trobar a un ritme bastant bo. 1229 00:44:48,740 --> 00:44:52,510 Però fonamentalment, són tots bastant horrible, per ser honest. 1230 00:44:52,510 --> 00:44:56,960 Tots aquests algoritmes fins ara que s'executen en gran O de n al quadrat 1231 00:44:56,960 --> 00:44:59,270 prendre una mica de temps per córrer al final. 1232 00:44:59,270 --> 00:45:01,920 >> I de fet, podem veure i sentir aquest últim 1233 00:45:01,920 --> 00:45:04,090 si m'aixeco aquesta tercera i última demostració. 1234 00:45:04,090 --> 00:45:05,840 Aquest és un altre visualització que va 1235 00:45:05,840 --> 00:45:08,500 per mostrar ordenament de bombolla en l'esquerra, ordenació per selecció en el medi, 1236 00:45:08,500 --> 00:45:13,410 i una cosa que, com un del nostre mà planteja suggerir anteriorment, 1237 00:45:13,410 --> 00:45:15,020 ordenament per barreja a la dreta. 1238 00:45:15,020 --> 00:45:16,937 Un divideix i venceràs l'estratègia de la dreta. 1239 00:45:16,937 --> 00:45:19,520 I això és, de fet, el que estem anar a veure dimecres. 1240 00:45:19,520 --> 00:45:21,990 Però el temps aquests s'executi en paral·lel anem. 1241 00:45:21,990 --> 00:45:26,765 És més o menys el mateix nombre de elements, tots funcionant al mateix temps. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bombolla espècie vs selecció espècie vs fusió tipus. 1244 00:45:34,440 --> 00:45:36,760 >> Ara, tots estan corrent en teoria al mateix temps. 1245 00:45:36,760 --> 00:45:39,830 La CPU està funcionant a la mateixa velocitat, però 1246 00:45:39,830 --> 00:45:44,014 pot sentir el avorrit que és va molt ràpidament per convertir-se, 1247 00:45:44,014 --> 00:45:45,930 i com de ràpid quan injectem una mica de setmana 1248 00:45:45,930 --> 00:45:49,330 algoritmes de zero pot que accelerar les coses. 1249 00:45:49,330 --> 00:45:51,760 >> I ara anem a comparar aquests en una última forma. 1250 00:45:51,760 --> 00:45:55,710 Vaig a seguir endavant el lloc web del CS50, on 1251 00:45:55,710 --> 00:45:59,020 tenim aquest última baula per avui, on algú a Internet 1252 00:45:59,020 --> 00:46:03,960 amablement armar un vídeo que capta la diferència classificació 1253 00:46:03,960 --> 00:46:07,510 algoritmes sonen. 1254 00:46:07,510 --> 00:46:09,577 Aquesta és l'ordenació per inserció. 1255 00:46:09,577 --> 00:46:12,072 >> [SO] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Pel qual vostè està demanant una freqüència basat en l'altura de la barra de bar. 1258 00:46:16,850 --> 00:46:19,826 Es tracta d'ordenament de bombolla. 1259 00:46:19,826 --> 00:46:21,822 >> [SO Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Que fins a la pròxima és-- venir al costat és-- ordenació per selecció, 1262 00:46:45,774 --> 00:46:48,820 on de nou, estem seleccionant el següent element més petit, 1263 00:46:48,820 --> 00:46:51,820 i podem veure que cada vegada més d'esquerra a dreta. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Combinar espècie, pel que el nostre guanyador la data d'avui. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Observi com està dividint coses en [inaudible] mitjana i els quarts. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Tipus Gnome, que no tenim parlat, i crea visualment 1270 00:47:21,660 --> 00:47:24,450 i audally una mica d'un diferent forma i so. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 L'anar i venir, la neteja de les coses. 1273 00:47:30,160 --> 00:47:32,230 També pots veure heapsort a la pàgina web d'aquest tipus. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> I això és tot. 1276 00:47:36,810 --> 00:47:38,210 Ens veiem la propera vegada. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing I MÚSICA] 1279 00:47:48,334 --> 00:50:24,839