1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [MUZIKO Ludante] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Jen CS50. 5 00:00:12,550 --> 00:00:14,612 Kaj tiu estas la komenco de semajno tri. 6 00:00:14,612 --> 00:00:16,820 Do ni havas multajn ekscita aferojn kovri hodiaŭ. 7 00:00:16,820 --> 00:00:20,160 Multaj eblecoj por volontas supren sur scenejo. 8 00:00:20,160 --> 00:00:22,780 Kaj finfine, hodiaŭ estas Ne pri kodo ajn. 9 00:00:22,780 --> 00:00:24,820 Sed ĝi temas pri ideoj, kaj temas pri algoritmoj, 10 00:00:24,820 --> 00:00:28,420 kaj efektive alportanta reen kelkaj la lecionoj lernis de semajno nulo, 11 00:00:28,420 --> 00:00:31,910 kien revokon, ni enkondukis ĉi monstraĵo. 12 00:00:31,910 --> 00:00:33,880 Kaj pruntado inspiro de tio, por komenci 13 00:00:33,880 --> 00:00:36,879 solvi ĉiam pli kompleksaj problemoj algorítmicamente. 14 00:00:36,879 --> 00:00:38,420 Sed unue, paro de anoncoj. 15 00:00:38,420 --> 00:00:42,020 Do unu, se vi ŝatus aliĝi CS50 bastonon kaj samklasanoj ĉe lunĉo 16 00:00:42,020 --> 00:00:44,670 tiu vendredo, ambaŭ ĉi tie kaj en Kembriĝo, kaj en New Haven, 17 00:00:44,670 --> 00:00:48,060 bonvolu viziti la kurso retejo, kie URL troviĝas. 18 00:00:48,060 --> 00:00:50,390 Prelegi tiu merkredo havos ne estos ĉi tie en Sanders. 19 00:00:50,390 --> 00:00:53,610 Estos rete nur, tial agordu ĉe CS50 la retejo, 20 00:00:53,610 --> 00:00:55,850 ĉu tie en Kembriĝo aŭ New Haven ankaŭ. 21 00:00:55,850 --> 00:00:58,110 >> Kaj tiam problemo starigis du estas jam en viaj manoj. 22 00:00:58,110 --> 00:01:03,067 Se vi ne plonĝis en ankoraŭ, permesu min proponi la energia sugesto 23 00:01:03,067 --> 00:01:05,150 ke, precipe nun, kiam la problemo aroj antaŭas, 24 00:01:05,150 --> 00:01:08,669 vi vere volas komenci nun, se ne dabble iom sur la semajnfino aŭ antaŭ 25 00:01:08,669 --> 00:01:10,710 kiam ili unue eliri sur Vendredo, ĉar vi 26 00:01:10,710 --> 00:01:14,380 trovi ke ili ne estas nepre atingi pli longa aŭ pli defia po 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Mi pensas ke vi trovos ke, Ĝenerale, ili emas preni malglate 29 00:01:17,575 --> 00:01:18,892 ĉirkaŭ sama kvanto de tempo. 30 00:01:18,892 --> 00:01:20,850 Sed certe dependas sur la studento, kaj ĝi 31 00:01:20,850 --> 00:01:22,880 dependas la pensmanieron kun kiu vi alproksimiĝas ĝin. 32 00:01:22,880 --> 00:01:24,910 Sed senescepte, vi tuj kuri supren kontraŭ iu muro, 33 00:01:24,910 --> 00:01:26,350 kaj vi tuj trafis kelkaj cimoj, kaj vi estas nur 34 00:01:26,350 --> 00:01:27,950 ne tuj povos reĝustiĝos ĉe iu punkto. 35 00:01:27,950 --> 00:01:31,380 Kaj ĝi estas tre valora por povi paŝi for, revenu la venontan tagon, 36 00:01:31,380 --> 00:01:35,286 iri al oficejo horoj, post en CS50 Diskutu aŭ simile, por fakte akiri desbloqueado. 37 00:01:35,286 --> 00:01:36,160 Observu do, ke en menso. 38 00:01:36,160 --> 00:01:40,830 Komencante fruaj kiel eble estas la plej bona afero vi povas fari. 39 00:01:40,830 --> 00:01:44,160 Do jen kie ni komencis la klaso, super en semajno nulo. 40 00:01:44,160 --> 00:01:47,441 Kaj ni surterigos volontulo tie helpi min trovi mics? 41 00:01:47,441 --> 00:01:47,940 BONE. 42 00:01:47,940 --> 00:01:48,900 Starante, jam. 43 00:01:48,900 --> 00:01:50,080 Venu supren. 44 00:01:50,080 --> 00:01:53,707 Divenu tiel estas kiel ĝi tuj labori. 45 00:01:53,707 --> 00:01:54,415 Kio estas via nomo? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA Alan Estrado. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrado. 48 00:01:56,778 --> 00:01:57,910 Venu supren. 49 00:01:57,910 --> 00:01:58,619 Agrable renkonti vin. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Nice to meet you. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: Sed vi estis tie kun ni en semajno nulo, kompreneble. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: mi estis. 53 00:02:03,028 --> 00:02:03,160 Mi estis. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Do vi povus iri antaŭen kaj trovi por ni Mike Smith, 55 00:02:05,868 --> 00:02:08,639 kiel rapida kiel vi povas? 56 00:02:08,639 --> 00:02:10,639 Kiel rapida kiel vi povas. 57 00:02:10,639 --> 00:02:13,756 Laŭvorte ŝirante la problemo en duono kiel vi bezonas. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Laŭvorte ŝirante la problemo en duono. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Ho. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Tre bone. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: Bone. 65 00:02:23,700 --> 00:02:24,200 Bona. 66 00:02:24,200 --> 00:02:24,701 Dankon. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Tre bone. 68 00:02:25,700 --> 00:02:26,210 BONE. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: Do nun, vi ĉizis ĝin 70 00:02:27,610 --> 00:02:29,320 al duono de la grandeco de la problemo. 71 00:02:29,320 --> 00:02:31,267 Nun, ni estas malsupren al kvarono. 72 00:02:31,267 --> 00:02:33,475 Ĉu vi atentante kiu flanko ni tenanta? 73 00:02:33,475 --> 00:02:34,405 >> [Ridanta] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Jes, mi think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Kio sekcio estas ni en? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: cxirkauxligojn, tiel. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: Bone. 78 00:02:39,941 --> 00:02:42,810 Sed Mike Smith tuj esti post Mufflers. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Ridanta] 81 00:02:48,180 --> 00:02:48,742 >> Bone. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Kien ni rigardas? 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: Nun, ni estas en kirurgia. 86 00:02:54,760 --> 00:02:57,840 Nun, kuracistoj. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- ni iru kun reala. 89 00:02:59,856 --> 00:03:00,370 Reala. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 BONE. 92 00:03:01,470 --> 00:03:03,700 Se vi bezonas Reala. 93 00:03:03,700 --> 00:03:05,250 Nun, kiudirekten estas Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Tiu vojo. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Kiun vojon? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Atendu. 97 00:03:08,240 --> 00:03:08,790 M is-- pravas? 98 00:03:08,790 --> 00:03:09,110 Ni komencis with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Yeah. 100 00:03:10,090 --> 00:03:10,650 Ili lasis. 101 00:03:10,650 --> 00:03:11,430 Via dekstra. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Yeah. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Do Mike tien. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Kio? 105 00:03:13,990 --> 00:03:14,665 >> [Ridanta] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Malbona ekzemplo, knaboj. 108 00:03:18,330 --> 00:03:18,830 Pardonon. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Ĉi instruos vi salteti el via seĝo. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Ho. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Mi havas vin. 113 00:03:23,390 --> 00:03:24,670 Mi havas vin. 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 Ĉi is-- OK, Mi havas vin. 117 00:03:26,812 --> 00:03:27,520 Forgxiston ĝuste ĉi tie? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, dankon. 119 00:03:28,894 --> 00:03:30,535 Do mi gardos suprenrigardinte Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ho, jes. 121 00:03:30,790 --> 00:03:31,340 Ne, ne, ne. 122 00:03:31,340 --> 00:03:31,600 Ho ne. 123 00:03:31,600 --> 00:03:31,940 Tiu estas mia. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Ah, vi havas Smith. 125 00:03:32,580 --> 00:03:33,415 BONE. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Yeah, Mi akiris Smith ĉi tie. 127 00:03:34,040 --> 00:03:34,700 Pardonu, knaboj. 128 00:03:34,700 --> 00:03:35,860 Mi pensis Michael-- ni serĉis Michael. 129 00:03:35,860 --> 00:03:36,550 Pardonon. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Estas bone. 131 00:03:37,550 --> 00:03:39,950 Bone, nun ni estas en Paccini kaj Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini kaj filoj. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Nur vin kaj mi estas en sur ĉi. 134 00:03:43,158 --> 00:03:44,050 BONE. 135 00:03:44,050 --> 00:03:45,130 Trovi nin Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Forgxiston. 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 Ni estas en R por rubo. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: rubo. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Tiu tuj prenos tempon. 143 00:03:52,480 --> 00:03:54,340 >> [Ridanta] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Ŝuoj. 146 00:03:56,720 --> 00:03:58,080 Ni estas en ŝuoj. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nun ni gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Ridanta] 151 00:04:03,620 --> 00:04:05,440 Ho, tiu estas granda. 152 00:04:05,440 --> 00:04:06,910 [Ridanta] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Estas bone. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Ho, tiu estas bona. 156 00:04:11,365 --> 00:04:14,425 Mi ne kredas mi tuj havas PSAT amikoj post tio. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Bonan. 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: Bone. 162 00:04:19,459 --> 00:04:21,600 Do ni disŝiros tiun duono. 163 00:04:21,600 --> 00:04:22,270 Estas bone. 164 00:04:22,270 --> 00:04:25,606 Ĉi finiĝas nebone ĉiuokaze, ĉar Mike Forgxiston ne estos en la flava paĝoj. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Ne, estas OK. 167 00:04:27,140 --> 00:04:28,930 Sed ni ŝajnigi kiel li estas en tiu ĉi paĝo. 168 00:04:28,930 --> 00:04:33,260 Do nun, vi jam ĉizis la problemo malsupren al unu paĝo, kaj ni trovis Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Huraado] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK, dankon. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 BONE. 174 00:04:41,200 --> 00:04:43,646 Tio estis eksterordinara. 175 00:04:43,646 --> 00:04:45,954 Sed ĝi estis ankoraŭ pli rapida ol lineara serĉo, 176 00:04:45,954 --> 00:04:47,870 kiun ni starti je la komencante de la libro, 177 00:04:47,870 --> 00:04:51,210 kaj ni movas nia vojo de maldekstre dekstren, eventuale serĉas Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Kaj tiel, se la telefono libro havis eble 1.000 paĝoj, 179 00:04:53,540 --> 00:04:56,300 eble ĝi estus preninta us 10 aŭ tiel paĝon larmoj. 180 00:04:56,300 --> 00:04:59,380 >> Sed eble vi ekspluatita tuŝis antaŭsupozo 181 00:04:59,380 --> 00:05:03,602 dum ĉiuj de tiu, kiu estas ke la telefono libro anticipe estis kio? 182 00:05:03,602 --> 00:05:04,310 Publiko: Ordigitaj. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: ĝi estas ordo. 184 00:05:05,000 --> 00:05:05,160 Dekstra? 185 00:05:05,160 --> 00:05:07,909 Ĝi estas ordo alfabete, do ke ĉiuj el tiuj nomoj kaj nombroj 186 00:05:07,909 --> 00:05:11,230 estas ordo de la -a por la Z, kaj alfabete intere. 187 00:05:11,230 --> 00:05:13,100 Sed hodiaŭ, ni nun demandas la demando, nu, 188 00:05:13,100 --> 00:05:16,170 kiel faris Verizon aŭ telefone kompanio akiri ĝin en tiu stato? 189 00:05:16,170 --> 00:05:19,560 >> Ĉar estas unu afero utiligi tiu supozo, kaj sekve, 190 00:05:19,560 --> 00:05:22,570 solvi problemon per algoritmo pli kompetente. 191 00:05:22,570 --> 00:05:24,900 Sed ni neniam vere demandis en semajno nulo, nu, 192 00:05:24,900 --> 00:05:27,790 Kiom ĝi kostis Verizon aŭ iu alia 193 00:05:27,790 --> 00:05:29,620 bonstata telefono libro en ordo ordo? 194 00:05:29,620 --> 00:05:29,780 >> Dekstra? 195 00:05:29,780 --> 00:05:31,529 Ne gravas se suprenrigardinte Mike Smith 196 00:05:31,529 --> 00:05:35,190 estas super rapida, se ĝi prenas vin jaro ordigi la paĝojn komence. 197 00:05:35,190 --> 00:05:35,690 Dekstra? 198 00:05:35,690 --> 00:05:38,620 Vi povus tiel nur kribri tra randomigitaj telefono libro, 199 00:05:38,620 --> 00:05:40,690 se ĝi okazas esti súper multekosta por ordigi ĝin. 200 00:05:40,690 --> 00:05:42,350 Do se ni povas havi alian volontulo. 201 00:05:42,350 --> 00:05:46,350 Ni rigardu supren tie ĉe kiamaniere ni might-- trafos up-- kiom 202 00:05:46,350 --> 00:05:48,100 ni povus iri pri ordigado tiuj. 203 00:05:48,100 --> 00:05:51,990 >> Kaj se Jordan povis reale aliĝi nin tie sur la scenejo. 204 00:05:51,990 --> 00:05:55,100 Venu supren por nur momento. 205 00:05:55,100 --> 00:05:56,359 Kio estas via nomo? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, venu supren. 208 00:05:58,691 --> 00:06:02,070 Kaj vi aligxos apud mi kaj Jordanio tie. 209 00:06:02,070 --> 00:06:03,800 Caroline, dankon. 210 00:06:03,800 --> 00:06:04,300 Bone. 211 00:06:04,300 --> 00:06:08,330 Do kion ni havas ĉi tie por Caroline estas 26 bluaj libroj 212 00:06:08,330 --> 00:06:10,747 ke FAS uzas administri certaj finaj ekzamenoj. 213 00:06:10,747 --> 00:06:13,330 Tiuj iĝas malfacile trovi, sed kion ni faris anticipe 214 00:06:13,330 --> 00:06:15,800 estas ke ni metis ies nomon sur la fronto de ĉiu el tiuj, 215 00:06:15,800 --> 00:06:18,133 sed ni konservis ĝin simpla per tiam elmetanta plenaj nomoj. 216 00:06:18,133 --> 00:06:22,720 Do ni metus la persono kun la nomo L, D, J, B, tuta vojo A tra Z, 217 00:06:22,720 --> 00:06:24,090 sed ili estas en hazarda ordo. 218 00:06:24,090 --> 00:06:26,890 Kaj do se vi farus, parolante via vojo tra la problemon kiel vi 219 00:06:26,890 --> 00:06:31,620 cxu gxi, cxu vi povas antaŭeniri kaj ordigi tiujn por ni, de A al Z. 220 00:06:31,620 --> 00:06:34,070 >> Publiko: Bone, do L estas kiel, la mezo. 221 00:06:34,070 --> 00:06:35,050 C komencas. 222 00:06:35,050 --> 00:06:42,410 B. J antaŭ L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Premu ke pensis por unu sekundo. 224 00:06:45,140 --> 00:06:48,910 Ĉar alie, tio estas nur Interese vi, mi, kaj Jordanio. 225 00:06:48,910 --> 00:06:49,724 Tie ni marŝos. 226 00:06:49,724 --> 00:06:50,640 Spektantaro: [inaudible]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: Bone. 229 00:06:58,090 --> 00:06:59,310 Kion vi faras? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M venas post O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: Bone. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: Ho, Bonan. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Yeah. 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. Do aspektas kiel vi making-- plu iri. 238 00:07:10,689 --> 00:07:12,730 Aspektas kiel vi faras granda amaso super tie, 239 00:07:12,730 --> 00:07:13,910 kaj speco de granda amaso super tie. 240 00:07:13,910 --> 00:07:16,230 Do la unua duono de la alfabeto, dua duono de la alfabeto. 241 00:07:16,230 --> 00:07:16,460 BONE. 242 00:07:16,460 --> 00:07:16,960 Bona. 243 00:07:16,960 --> 00:07:19,680 Speco de fendanta la problemo en du. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Yeah. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: Bone. 247 00:07:22,980 --> 00:07:25,070 K. Do vi speco de elektanta ilin unu post alia, 248 00:07:25,070 --> 00:07:27,620 metante ĝin aŭ maldekstra aŭ dekstra, aŭ Z iranta sur la planko. 249 00:07:27,620 --> 00:07:28,012 BONE. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z okazas surplanke. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: Bone. 252 00:07:29,360 --> 00:07:30,920 Y tuj surplanke. 253 00:07:30,920 --> 00:07:31,735 Nun ni povas meti 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 okazas lasis. 256 00:07:33,700 --> 00:07:36,017 S tuj dekstre. 257 00:07:36,017 --> 00:07:37,642 Bone, A estas iranta tute forlasis. 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: Nun, bone. 260 00:07:39,873 --> 00:07:43,260 Ni havas A, B, C. W la subiro tie. 261 00:07:43,260 --> 00:07:45,566 Bone, 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 Bonan. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: En la centro, mi gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: Bone. 266 00:07:50,000 --> 00:07:52,375 Do nun, ni tuj speco de kunfandi tiujn diversajn amasoj. 267 00:07:52,375 --> 00:08:00,730 Do A tra C, tiam mi vidas D kaj E, kaj F, kaj G, kaj H, kaj I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Kaj tiam, tiu stako estas renversita, sed tio estas bone. 269 00:08:05,540 --> 00:08:06,040 Certe. 270 00:08:06,040 --> 00:08:07,240 Ni povas tranĉi kelkajn angulojn. 271 00:08:07,240 --> 00:08:07,950 BONE. 272 00:08:07,950 --> 00:08:10,530 Kaj tiam ni bezonas W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Yeah. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Bonega. 275 00:08:11,880 --> 00:08:14,122 Do grandan dankon al Caroline por ordigado tiuj. 276 00:08:14,122 --> 00:08:15,030 >> [Huraado] 277 00:08:15,030 --> 00:08:17,287 >> Dankon. 278 00:08:17,287 --> 00:08:18,120 Dankegon. 279 00:08:18,120 --> 00:08:22,910 Do nun ni pripensu dum momento kiom Caroline rondiris fari tion, 280 00:08:22,910 --> 00:08:26,040 kaj kion ekzakte ni povis to-- kiamaniere ni 281 00:08:26,040 --> 00:08:28,409 povis solvi tiun problemo kiam ni estis ĵus 282 00:08:28,409 --> 00:08:29,950 donita tuta amaso de hazardaj enigoj. 283 00:08:29,950 --> 00:08:31,610 >> Nu, tio aspektas kiel ekzistas estis iom de sistemo tie? 284 00:08:31,610 --> 00:08:32,110 Dekstra. 285 00:08:32,110 --> 00:08:34,495 Do la fruaj literoj en la alfabeto, ŝi 286 00:08:34,495 --> 00:08:37,120 estis metante al la maldekstra, kaj la poste literoj en la alfabeto, 287 00:08:37,120 --> 00:08:38,270 ŝi estis metanta en la dekstra. 288 00:08:38,270 --> 00:08:40,500 Kaj tuj kiam ŝi trovis iuj proximal literoj, tiuj 289 00:08:40,500 --> 00:08:43,124 kiuj iras dekstre apud la alia, ŝi metus tiujn en ordo. 290 00:08:43,124 --> 00:08:46,750 Kaj tial ni ia havis tiujn malgrandajn amasoj de ordo enigoj okazanta. 291 00:08:46,750 --> 00:08:50,540 >> Kaj tiel tio estas tute kiel kio plimulto de ni homoj farus. 292 00:08:50,540 --> 00:08:53,530 Ni estus ia kribri tra ĝi, kaj ni estus ia havas mekanismon. 293 00:08:53,530 --> 00:08:56,930 Sed ĝi povus esti malfacile skribi ĝin malsupren en formulo por se. 294 00:08:56,930 --> 00:08:59,010 Ĝi sentis iom pli organika ol tio. 295 00:08:59,010 --> 00:09:02,560 Do ni vidu se ni povas nun mallibera la problemo kun malpli enigoj. 296 00:09:02,560 --> 00:09:05,170 >> Anstataŭ 26, ni fari ion ege malpli 297 00:09:05,170 --> 00:09:09,890 kun nur diru, sep, malantaŭ tiuj pordoj, tiel diri. 298 00:09:09,890 --> 00:09:11,300 Ĉu ekzistas nur sep numeroj? 299 00:09:11,300 --> 00:09:15,240 Kaj se la celo nun ĉe mano estas trovi valoron, 300 00:09:15,240 --> 00:09:17,850 ni vidu kiel kompetente ni povas iri pri faranta tion ĉi. 301 00:09:17,850 --> 00:09:22,460 Kaj ni vidos se ni povas nun komenci apliki iujn numerojn, 302 00:09:22,460 --> 00:09:26,310 aŭ iuj formuloj kun kiu priskribi la efikeco de nia telefono libro 303 00:09:26,310 --> 00:09:31,060 algoritmo, nia ekzameno libro algoritmo, kaj pli ĝenerale, trovanta informon. 304 00:09:31,060 --> 00:09:34,770 >> Do pro tio, lasu min antaŭeniri kaj sur la ekrano táctil tien, 305 00:09:34,770 --> 00:09:41,100 toleri foliumilo kiu havas ĝuste tiuj sep pordoj. 306 00:09:41,100 --> 00:09:46,670 Kaj se ni povus akiri unu alia volontuli veni tien, 307 00:09:46,670 --> 00:09:48,480 Mi metis tiujn samajn pordojn super tie. 308 00:09:48,480 --> 00:09:49,170 Rapida volontulo. 309 00:09:49,170 --> 00:09:51,130 >> Ĉi one-- demonstraĵoj iras al pli kaj pli rapide nun. 310 00:09:51,130 --> 00:09:51,600 Venu malsupren. 311 00:09:51,600 --> 00:09:52,308 Kio estas via nomo? 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 Bone, Trevor, venu malsupren. 315 00:09:55,770 --> 00:09:59,212 Do Trevor jam volontulis tie fari similan problemon, sed kiu estas 316 00:09:59,212 --> 00:10:02,170 mallarĝa en amplekso, kaj ke tuj por permesi nin provi formaligi nun 317 00:10:02,170 --> 00:10:03,970 la procezo por ordigado tiuj nombroj. 318 00:10:03,970 --> 00:10:05,500 >> Do Trevor, agrable renkonti vin. 319 00:10:05,500 --> 00:10:08,720 Do tie estas tabelo, do al paroli, liston de sep pordoj. 320 00:10:08,720 --> 00:10:10,327 Antaŭen kaj trovi nin la numero 50. 321 00:10:10,327 --> 00:10:12,410 Kaj tiam post la fakto, diru al ni, kiel vi trovis ĝin. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Devus be-- gxuste. 324 00:10:20,040 --> 00:10:21,945 Jes, tiu estas tie? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 BONE. 327 00:10:25,560 --> 00:10:26,680 Vi klakis tiu. 328 00:10:26,680 --> 00:10:28,690 Bona. 329 00:10:28,690 --> 00:10:29,780 >> Kaj bona. 330 00:10:29,780 --> 00:10:30,970 Nun vi klakis tiu. 331 00:10:30,970 --> 00:10:34,060 Kaj mi donos al vi la mikrofonon, por ke vi havas ĝin en nur momento. 332 00:10:34,060 --> 00:10:37,000 Iru antaŭen kaj klaku najbare ke vi intencas. 333 00:10:37,000 --> 00:10:39,812 Jes, bone. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Ĉu mi unclick pordon? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Ne, vi ne povas unclick. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Ĉi tiu. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Kie vi volas iri? 339 00:10:45,640 --> 00:10:46,410 Kiu? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Tiu. 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 Ĉi tiu. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Jes. 345 00:10:49,020 --> 00:10:49,700 Tio estis bona. 346 00:10:49,700 --> 00:10:50,380 Bone. 347 00:10:50,380 --> 00:10:53,900 Do kio estis via algoritmo aŭ proceduro por fari tion, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Mi ĵus iris tra pordoj ĝis mi trovis 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: Bone. 350 00:10:56,940 --> 00:10:58,150 Bonegaj algoritmo. 351 00:10:58,150 --> 00:10:59,540 Do tio estas bone. 352 00:10:59,540 --> 00:11:03,120 Ĉar fakte, se mi malkaŝus kio estas malantaŭ tiuj du aliajn pordojn, kion 353 00:11:03,120 --> 00:11:06,954 ni trovos tie estas ke ni nur havas hazardaj enigo. 354 00:11:06,954 --> 00:11:08,870 Tiel ke estis vere kiel bona kiel vi povus akiri. 355 00:11:08,870 --> 00:11:12,509 Kaj fakte, vi igxis pli ol ĝisfunde esploras la tuta tabelo, 356 00:11:12,509 --> 00:11:15,300 ĉar ĝi estintus vere malbonŝanca se vi trafis la numeron 357 00:11:15,300 --> 00:11:16,604 50 je la lasta pordo. 358 00:11:16,604 --> 00:11:18,520 Sed kio se ni anstataŭ donis vin supozo. 359 00:11:18,520 --> 00:11:20,630 Supozi Mi ordigas ĉiujn tiuj pordoj ĉirkaŭe, 360 00:11:20,630 --> 00:11:23,500 por ke vi havas la nombroj ordigitaj tiu tempo, 361 00:11:23,500 --> 00:11:29,730 sed ĉifoje ĝi estas fakte a different-- tiu tempo, 362 00:11:29,730 --> 00:11:32,640 ĝi estas fakte ordo por vi. 363 00:11:32,640 --> 00:11:35,380 Kaj nun la celon ĉe mano estas frapi la numero 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Kio estas via algoritmo tuj estos? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Nu, se ĝi estas ordo, estas ĉu irante 367 00:11:39,628 --> 00:11:42,710 al be-- se plej granda al plej grandaj, malsuprenirantan, ĝi estos la unua, 368 00:11:42,710 --> 00:11:44,751 aŭ se ĝi estas la malo, tio estos la lasta. 369 00:11:44,751 --> 00:11:48,897 Do mi nur tap ĉi pordo, kaj tiam nur tushi la lasta pordo. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Bonega. 371 00:11:49,980 --> 00:11:50,270 Bone. 372 00:11:50,270 --> 00:11:51,150 Do ni trovis la numero 50. 373 00:11:51,150 --> 00:11:52,970 Tuj, kiam vi konis ili ordigataj ni 374 00:11:52,970 --> 00:11:55,040 sukcesis uzi tiun supozon. 375 00:11:55,040 --> 00:11:57,040 Do ili estas tro kiel la telefono libro ekzemplo. 376 00:11:57,040 --> 00:11:59,540 Tuj kiam vi havas, eĉ kun malgrandan problemon kiel tiu, 377 00:11:59,540 --> 00:12:02,380 viaj enigoj pre-ordo, ni povas reale trovi la valoron disputeble 378 00:12:02,380 --> 00:12:03,130 pli kompetente. 379 00:12:03,130 --> 00:12:05,800 >> Kaj mi ne diras al vi se ĝi estis ordo malgranda al granda, aŭ granda por malgranda, 380 00:12:05,800 --> 00:12:08,080 kaj tiel estis tre racia komenci ĉe unu fino aŭ la aliaj 381 00:12:08,080 --> 00:12:09,750 por fakte trovi ke objektiva valoro. 382 00:12:09,750 --> 00:12:11,400 Do dankon al Trevor ankaŭ. 383 00:12:11,400 --> 00:12:13,260 Kaj mi propose-- bele farita. 384 00:12:13,260 --> 00:12:16,960 Ni havas iom klipo, fakte, ke estas inter niaj momentoj favoritos en CS50, 385 00:12:16,960 --> 00:12:19,700 whereby kelkfoje tiuj demonstraĵoj ne tute iru laŭ plano. 386 00:12:19,700 --> 00:12:22,050 Kaj ja ĝuste nun, mi tirita supren malĝustan interfaco 387 00:12:22,050 --> 00:12:23,508 kun kiu uzi la ekranon táctil. 388 00:12:23,508 --> 00:12:24,660 Por ke estis mia kulpo tie. 389 00:12:24,660 --> 00:12:26,600 >> Do ĉi faros por venontjara klipo kiel 390 00:12:26,600 --> 00:12:28,570 kial mi klakanta sur mia propra ekrano. 391 00:12:28,570 --> 00:12:31,390 Sed ni prenu rapidan rigardon kio okazis pasintjare 392 00:12:31,390 --> 00:12:34,770 kun Jay, kiuj venadis multe kiel Trevor tie, volontulis, 393 00:12:34,770 --> 00:12:39,380 kaj en tiu mallonga tranĉeto, vi vidos kiel tiu sama demo faris ne tute 394 00:12:39,380 --> 00:12:41,074 malkaŝi la sama lecionoj lernitaj. 395 00:12:41,074 --> 00:12:41,740 [VIDEO reprodukto] 396 00:12:41,740 --> 00:12:45,360 -All Mi volas vin fari nun estas trovi por mi kaj por ni, 397 00:12:45,360 --> 00:12:51,674 vere, la nombro 50 unu paŝon samtempe. 398 00:12:51,674 --> 00:12:52,450 >> -La Nombro 50? 399 00:12:52,450 --> 00:12:53,190 >> -La Nombro 50. 400 00:12:53,190 --> 00:12:55,356 Kaj vi povas malkaŝi kio estas malantaŭ ĉiu el tiuj pordoj 401 00:12:55,356 --> 00:12:58,540 simple tuŝante ĝin per la fingro. 402 00:12:58,540 --> 00:13:00,910 Damnu ĝin. 403 00:13:00,910 --> 00:13:02,870 >> [Ridanta] 404 00:13:02,870 --> 00:13:03,806 >> [FINO reprodukto] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Do tiu iris tre bone. 406 00:13:05,430 --> 00:13:06,796 Tiuj estis la unsorted pordoj. 407 00:13:06,796 --> 00:13:08,670 Kaj Jay, kompreneble, trovis ĝin tro rapide. 408 00:13:08,670 --> 00:13:12,910 Trevor faris multe pli bonan laboron en terminoj de teachable momento, 409 00:13:12,910 --> 00:13:15,850 tiel diri, tiun jaron en prenante plu trovi ĝin. 410 00:13:15,850 --> 00:13:17,950 Kompreneble, tiam ni donis Jay duan ŝancon, 411 00:13:17,950 --> 00:13:20,320 per kiu ni ordigitaj la pordojn, ĝuste kiel ni faris por Trevor, 412 00:13:20,320 --> 00:13:22,300 kaj Trevor faris súper bone ĉi tiu tempo. 413 00:13:22,300 --> 00:13:26,124 Sed Jay faris duono tiel rapide. 414 00:13:26,124 --> 00:13:26,790 [VIDEO reprodukto] 415 00:13:26,790 --> 00:13:29,650 -La Celo nun estas ankaŭ trovi nin la numero 50, 416 00:13:29,650 --> 00:13:33,030 sed faru ĝin algorítmicamente, kaj diru al ni kiel vi tuj pri ĝi. 417 00:13:33,030 --> 00:13:33,660 >> -BONE. 418 00:13:33,660 --> 00:13:35,604 >> -Kaj Se vi trovas ĝin, vi tenas la filmon. 419 00:13:35,604 --> 00:13:37,228 Se vi ne trovas ĝin, vi donos ĝin reen. 420 00:13:37,228 --> 00:13:38,044 >> -man. 421 00:13:38,044 --> 00:13:38,860 >> -Ho! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] OK. 423 00:13:40,800 --> 00:13:46,236 Do mi tuj kontroli la finoj unua determini se there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Aplaŭdo] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [FINO reprodukto] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: Bone. 428 00:13:56,520 --> 00:13:59,760 Do ordigado pordoj klare kondukas al pli granda efikeco. 429 00:13:59,760 --> 00:14:01,680 Kaj do, duoble rapida estas kion mi volis diri tie. 430 00:14:01,680 --> 00:14:03,270 Kaj tiel Jay akiris bonŝanca ambaŭ fojojn. 431 00:14:03,270 --> 00:14:06,685 Li ankaŭ akiris bonŝanca en tiu lasta jaro, mi mendis iuj Blu-ray 432 00:14:06,685 --> 00:14:07,560 reale sonigas. 433 00:14:07,560 --> 00:14:09,768 Mi bedaŭras tiu jaro, ni ne havas la saman, Trevor. 434 00:14:09,768 --> 00:14:11,540 Sed bona ankoraŭ kelkajn jarojn reen. 435 00:14:11,540 --> 00:14:14,820 Kaj iuj el vi eble scias tion ulo, Sean, kiu kiam li estis en CS50, 436 00:14:14,820 --> 00:14:17,780 estis defiita kun la ĝusta saman problemon, kvankam en SD, 437 00:14:17,780 --> 00:14:19,360 kiel vi baldaŭ vidos, reen en la tago. 438 00:14:19,360 --> 00:14:22,622 Kaj vi trovos, ke ne nur faris li prenos iom pli ol Jay, 439 00:14:22,622 --> 00:14:25,580 iom pli ol Trevor, estis fakte tiu mirinda ŝanco 440 00:14:25,580 --> 00:14:29,820 okupi preskaŭ ĉiuj en la amaso a la Prezo estas Dekstra, kuraĝigante 441 00:14:29,820 --> 00:14:31,889 lin trovi la nombro ni sercxis. 442 00:14:31,889 --> 00:14:32,930 Ni. prenu rapidan rigardon. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO reprodukto] 444 00:14:33,320 --> 00:14:33,820 >> -BONE. 445 00:14:33,820 --> 00:14:36,680 Do via tasko tie, Sean, estas jeno. 446 00:14:36,680 --> 00:14:40,860 Mi kaŝis malantaŭ tiuj pordojn la nombro sep. 447 00:14:40,860 --> 00:14:45,120 Sed ie en iuj el tiuj pordoj tiel estas aliaj negativaj nombroj. 448 00:14:45,120 --> 00:14:47,500 Kaj via celo estas pensi de tiu supera vico de nombroj 449 00:14:47,500 --> 00:14:50,390 kiel nur tabelo, aŭ nur sekvenco de pecoj de papero 450 00:14:50,390 --> 00:14:51,510 kun nombroj malantaŭ ili. 451 00:14:51,510 --> 00:14:55,540 Kaj via celo estas, nur uzante la supro tabelo tie, trovi min la numero sep. 452 00:14:55,540 --> 00:14:58,570 Kaj ni tiam tuj kritiko kiel vi iras pri faranta ĝin. 453 00:14:58,570 --> 00:14:59,070 -Bone. 454 00:14:59,070 --> 00:15:00,850 -Trovu Ni la nombro sep, bonvolu. 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 Kvin, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Ridanta] 461 00:15:24,770 --> 00:15:25,910 >> Ĝi ne estas lertaĵo demando. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Unu. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Ridanta] 466 00:15:34,695 --> 00:15:37,861 Ĉe tiu punkto, via poentaro ne estas tre bona, do vi povus tiel plu iri. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tri. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Ridanta] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Daŭrigu. 473 00:15:47,774 --> 00:15:50,690 Sincere, mi ne povas helpi sed scivolas kion vi eĉ pensas pri, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Ridanta] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Nur la supera vico, do vi havas tri maldekstre. 477 00:15:55,020 --> 00:15:56,200 Do trovi min sep. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Ridanta] 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 Sep. 484 00:16:26,946 --> 00:16:28,780 >> [Aplaŭdo] 485 00:16:28,780 --> 00:16:29,426 >> Bone. 486 00:16:29,426 --> 00:16:30,360 >> [FINO reprodukto] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Do ni povis spekti tiujn tuttage. 488 00:16:31,840 --> 00:16:34,090 Kaj kompreneble, kelkaj el ĉijara demonstraĵoj eble 489 00:16:34,090 --> 00:16:36,330 nun finas en proksima ĉijara vídeo ankaŭ. 490 00:16:36,330 --> 00:16:39,040 Do nun ni vere temigi la algoritmoj 491 00:16:39,040 --> 00:16:42,140 tie kaj vidi se ni ne povas nun komenci formaligi 492 00:16:42,140 --> 00:16:46,650 kiel ni povas iri pri akiri niajn datumojn en tiu stato ke ĝi estas ordo, 493 00:16:46,650 --> 00:16:50,054 por ke finfine, ni povas reale esplorrigardi gxin pli kompetente. 494 00:16:50,054 --> 00:16:52,470 Kaj eĉ se ni iras uzi sufiĉe malgrandaj datumaj aroj, 495 00:16:52,470 --> 00:16:54,511 kiel la ok numerojn ni havas ĉi tie sur la tabulon, 496 00:16:54,511 --> 00:16:58,230 finfine tiuj samaj ideoj povus apliki 1.000 enigoj, miliono enigoj, 497 00:16:58,230 --> 00:17:02,100 4 miliardoj enigoj, ĉar la algoritmoj tuj estos fundamente la sama. 498 00:17:02,100 --> 00:17:05,359 >> Kaj tiel tio estas nia lasta ŝanco volontulojn hodiaŭ, 499 00:17:05,359 --> 00:17:09,790 sed eble la plej implikitaj unu, por kiu ni bezonas ok volontuloj 500 00:17:09,790 --> 00:17:12,960 veni supren kaj piediras nin tra procezo de ordigado kio baldaŭ 501 00:17:12,960 --> 00:17:15,212 esti sur tiujn muziko staras tie. 502 00:17:15,212 --> 00:17:16,170 Permesu min komenci ĉi tien. 503 00:17:16,170 --> 00:17:19,692 >> Do unu en la turquoise-- verda estas? 504 00:17:19,692 --> 00:17:21,130 Cxu vi faras? 505 00:17:21,130 --> 00:17:21,630 Du. 506 00:17:21,630 --> 00:17:23,069 Venu malsupren. 507 00:17:23,069 --> 00:17:23,569 BONE. 508 00:17:23,569 --> 00:17:24,420 Tri. 509 00:17:24,420 --> 00:17:25,400 Kvar. 510 00:17:25,400 --> 00:17:27,247 Lasu kunulinon OK, kvin. 511 00:17:27,247 --> 00:17:28,830 Vi estanta nomumita fare via amiko. 512 00:17:28,830 --> 00:17:31,340 Ses, sep, kaj ok. 513 00:17:31,340 --> 00:17:32,130 Venu supren. 514 00:17:32,130 --> 00:17:32,630 Bone. 515 00:17:32,630 --> 00:17:33,190 Multan dankon. 516 00:17:33,190 --> 00:17:33,689 Venu supren. 517 00:17:33,689 --> 00:17:34,790 Venu supren. 518 00:17:34,790 --> 00:17:35,330 >> Bone. 519 00:17:35,330 --> 00:17:38,890 Do kion ni havas here-- kaj ĉi estas inter la pli mallerta, ili 520 00:17:38,890 --> 00:17:42,390 ĉar tio postulos ke vi humuro min nur iomete de tempo. 521 00:17:42,390 --> 00:17:43,442 Vi devas esti numero unu. 522 00:17:43,442 --> 00:17:44,150 Kio estas via nomo? 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 Davido. 526 00:17:46,092 --> 00:17:46,800 Kio estas via nomo? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Jozef. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Jozef, vi estas numero du. 529 00:17:49,190 --> 00:17:52,260 >> Serena: Serena, numero tri. 530 00:17:52,260 --> 00:17:53,722 Stefan, numero kvar. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, numero kvin. 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 nombro ses. 536 00:18:00,391 --> 00:18:00,890 MATT Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: Matt numero sep. 538 00:18:02,160 --> 00:18:02,850 Kaj? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, numero ok. 541 00:18:04,470 --> 00:18:04,970 Bone. 542 00:18:04,970 --> 00:18:06,510 Se vi could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Se vi cxiuj, kiel via unua defio, tie 544 00:18:08,820 --> 00:18:10,820 Estas ok muziko standojn tie alfrontante la spektantaron. 545 00:18:10,820 --> 00:18:14,200 Se vi povus meti viajn numerojn sur tiuj muziko staras tiel 546 00:18:14,200 --> 00:18:16,560 ke ili viciĝas supren kun la samajn nombrojn sur la tabulo. 547 00:18:16,560 --> 00:18:19,560 Sanktigu vin similos ke de metante vian nombrojn sur tiuj muziko 548 00:18:19,560 --> 00:18:21,960 staras tie. 549 00:18:21,960 --> 00:18:25,980 Bonegaj ĝis nun. 550 00:18:25,980 --> 00:18:26,600 >> Bonege. 551 00:18:26,600 --> 00:18:26,890 BONE. 552 00:18:26,890 --> 00:18:29,556 Do nun, ni tuj demandas la demandon en kelkaj malsamaj vojoj. 553 00:18:29,556 --> 00:18:31,610 Kiel ni iras pri ordigado tiuj uloj tie? 554 00:18:31,610 --> 00:18:34,500 Ĉar ni havis kelkajn alirojn antaŭe, per kiu ni 555 00:18:34,500 --> 00:18:36,360 speco de farante du malsamaj siteloj. 556 00:18:36,360 --> 00:18:38,842 Kaj tiam ni estis ĝenerale piecing aferojn kune. 557 00:18:38,842 --> 00:18:41,050 Tuj kiam ni vidis du nombroj kiuj apartenis kune, 558 00:18:41,050 --> 00:18:41,975 ni metis ilin kune. 559 00:18:41,975 --> 00:18:43,350 Du leteroj kiuj apartenas kune. 560 00:18:43,350 --> 00:18:45,058 >> Sed ni vidu se ni ne povas formaligi tiun, 561 00:18:45,058 --> 00:18:48,044 tiel ke ni finfine havas kelkaj pseŭdo-kodo vi volas, 562 00:18:48,044 --> 00:18:49,710 kun kiu vi povas solvi tiujn problemojn. 563 00:18:49,710 --> 00:18:51,870 Do nun, mi estas elrigardanta ĉe tiuj numeroj tie. 564 00:18:51,870 --> 00:18:55,030 Kaj mi vidas tutan faskon da erarojn. 565 00:18:55,030 --> 00:18:57,750 Finfine, mi volas unu sur la lasis ok dekstre. 566 00:18:57,750 --> 00:19:00,650 >> Kaj tial mi rigardas tiuj du, kvar kaj du. 567 00:19:00,650 --> 00:19:02,930 Kaj kio estas la problemo, evidente? 568 00:19:02,930 --> 00:19:04,261 Yeah. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Du evidente venas antaux kvar, tiel vi scias kion? 571 00:19:07,160 --> 00:19:10,210 Lasu min unue avara alproksimiĝo, se vi volas, multe kiel problemo 572 00:19:10,210 --> 00:19:13,790 fiksita one-- se vi memoras de la Norma Eldono de Problemo Ara Unu, 573 00:19:13,790 --> 00:19:16,820 kie mi nur loke solvi la problemon ke pravas tie antaŭ mi 574 00:19:16,820 --> 00:19:17,690 kaj vidi kie kondukas min. 575 00:19:17,690 --> 00:19:17,870 >> BONE. 576 00:19:17,870 --> 00:19:20,161 Do du kaj kvar, mi iros antaŭen kaj nur interŝanĝu vi du. 577 00:19:20,161 --> 00:19:22,400 Se vi povas fizike movas vin kaj via papero, 578 00:19:22,400 --> 00:19:25,040 Mi ŝajnas esti alveninta la listo en pli bona stato. 579 00:19:25,040 --> 00:19:26,330 >> Nun, ili estas bonaj. 580 00:19:26,330 --> 00:19:28,480 Mi tuj pluiri, kvar kaj ses, aspektas bone. 581 00:19:28,480 --> 00:19:29,110 Ne estas problemo. 582 00:19:29,110 --> 00:19:30,440 Ses kaj ok, OK. 583 00:19:30,440 --> 00:19:31,860 Ok kaj unu, alia problemo. 584 00:19:31,860 --> 00:19:34,750 Ĉar kio estas vera pri ok kaj unu? 585 00:19:34,750 --> 00:19:36,990 Unu venas antaŭ ok, do kion ni faru? 586 00:19:36,990 --> 00:19:38,090 Ni interŝanĝu tiujn du. 587 00:19:38,090 --> 00:19:39,316 Unu ok. 588 00:19:39,316 --> 00:19:40,690 Kaj nun, mi tuj plu iri. 589 00:19:40,690 --> 00:19:42,030 Mi tuj teni rigardante antaŭen. 590 00:19:42,030 --> 00:19:42,840 Kaj ni vidu kio okazas. 591 00:19:42,840 --> 00:19:44,680 Ok kaj tri, de Kompreneble, el ordo. 592 00:19:44,680 --> 00:19:45,815 Ni interŝanĝa. 593 00:19:45,815 --> 00:19:46,940 Ok kaj sep, kompreneble. 594 00:19:46,940 --> 00:19:47,481 Misfunkcias. 595 00:19:47,481 --> 00:19:48,280 Ni interŝanĝa. 596 00:19:48,280 --> 00:19:49,940 Ok kaj kvin, kompreneble, ni interŝanĝa. 597 00:19:49,940 --> 00:19:50,560 Bone. 598 00:19:50,560 --> 00:19:51,880 Listo estas aranĝita. 599 00:19:51,880 --> 00:19:53,060 jes? 600 00:19:53,060 --> 00:19:54,280 >> OK, evidente ne. 601 00:19:54,280 --> 00:19:55,860 Sed estas iom pli bona, ĉu ne? 602 00:19:55,860 --> 00:19:57,270 Ĉar avizo kio okazis. 603 00:19:57,270 --> 00:20:01,749 Ĉiufoje ni elfaris swap, pli malgranda numeron ia percolated tiel, 604 00:20:01,749 --> 00:20:03,790 kaj pli granda nombro percolated tiu maniero, aŭ ni 605 00:20:03,790 --> 00:20:06,880 komenci dirante bobelis al la maldekstra aŭ bobelis dekstre. 606 00:20:06,880 --> 00:20:10,080 >> Nun, ĝi ne sufiĉas, ĉar ĉe bona nombro povus 607 00:20:10,080 --> 00:20:11,990 movis unu loko antaŭen, aŭ en la plej malbona, 608 00:20:11,990 --> 00:20:13,880 kelkaj havu movita punkto cetere. 609 00:20:13,880 --> 00:20:16,369 Do vi scias kion tiu speco el funkciis sufiĉe bone ĝis nun. 610 00:20:16,369 --> 00:20:17,410 Lasu min nur provi ĝin denove. 611 00:20:17,410 --> 00:20:18,880 Du kaj kvar, ili estas okej. 612 00:20:18,880 --> 00:20:20,180 Kvar kaj ses, ili estas okej. 613 00:20:20,180 --> 00:20:21,790 Ses kaj unu, el ordo. 614 00:20:21,790 --> 00:20:23,007 Do ni interŝanĝu vi du. 615 00:20:23,007 --> 00:20:25,840 Kaj nun, rimarki la problemo la komencanta akiri iom pli bone denove. 616 00:20:25,840 --> 00:20:27,006 Ses kaj tri, el ordo. 617 00:20:27,006 --> 00:20:28,100 Ni interŝanĝu vi du. 618 00:20:28,100 --> 00:20:29,730 Ses kaj sep, vi estas bona. 619 00:20:29,730 --> 00:20:32,230 Sep kaj kvin, kompreneble, el ordo. 620 00:20:32,230 --> 00:20:33,920 Sep kaj ok, en ordo. 621 00:20:33,920 --> 00:20:36,470 Kaj nun mi eble bezonas fari tion kelkajn fojojn. 622 00:20:36,470 --> 00:20:39,830 Kaj fakte, pensi por vi eble kiomfoje maksimume 623 00:20:39,830 --> 00:20:41,330 eble mi devas piediri tien kaj reen? 624 00:20:41,330 --> 00:20:42,390 >> Ni revenos al tiu. 625 00:20:42,390 --> 00:20:43,700 Do du kaj kvar estas ankoraŭ OK. 626 00:20:43,700 --> 00:20:44,940 Kvar kaj unu, Nope. 627 00:20:44,940 --> 00:20:45,747 Do, ni interŝanĝa. 628 00:20:45,747 --> 00:20:47,830 Kaj denove, rimarki vide estas speco de bobelanta 629 00:20:47,830 --> 00:20:49,163 maldekstren, kie ĝi devus esti. 630 00:20:49,163 --> 00:20:50,010 Kvar kaj tri interŝanĝa. 631 00:20:50,010 --> 00:20:51,330 Kvar kaj ses. 632 00:20:51,330 --> 00:20:53,100 Ses kaj kvin interŝanĝa. 633 00:20:53,100 --> 00:20:53,959 Ses kaj sep. 634 00:20:53,959 --> 00:20:55,000 Sep kaj ok estas bona. 635 00:20:55,000 --> 00:20:55,500 >> Bona. 636 00:20:55,500 --> 00:20:58,460 Ni nun estas eĉ pli bona. 637 00:20:58,460 --> 00:20:59,130 Do ni vidu. 638 00:20:59,130 --> 00:21:00,940 Nun, ni havas du unu. 639 00:21:00,940 --> 00:21:02,520 Kompreneble, interŝanĝi. 640 00:21:02,520 --> 00:21:07,520 Du kaj tri, tri kaj kvar, kvar kaj kvin, ses kaj sep, sep kaj ok. 641 00:21:07,520 --> 00:21:08,020 Bona. 642 00:21:08,020 --> 00:21:08,730 Kaj vi scias kion? 643 00:21:08,730 --> 00:21:11,190 Ĉar mi faris unu ŝanĝon tie, lasu min fari unu prudento ĉeko. 644 00:21:11,190 --> 00:21:13,023 Lasu min iri la tutan vojon reen al la komenco. 645 00:21:13,023 --> 00:21:13,680 BONE. 646 00:21:13,680 --> 00:21:14,750 Unu, two-- Yup, vidi? 647 00:21:14,750 --> 00:21:15,870 Io eraris. 648 00:21:15,870 --> 00:21:18,420 Tri, kvar, kvin, ses, sep, ok. 649 00:21:18,420 --> 00:21:21,920 Kaj en ĉi tiu lasta paŝo, estas vi komforta kun mia nun 650 00:21:21,920 --> 00:21:23,830 Asertante estas ordo? 651 00:21:23,830 --> 00:21:24,330 BONE. 652 00:21:24,330 --> 00:21:25,880 Vide, tio estas absolute vera. 653 00:21:25,880 --> 00:21:28,410 Sed funkcie, kio ja ankaŭ nur hazarde 654 00:21:28,410 --> 00:21:31,870 en tiu lasta paŝo kiu permesas konfirmi ke ĉi tiu listo estas ja 655 00:21:31,870 --> 00:21:32,660 ordo? 656 00:21:32,660 --> 00:21:34,477 >> Kion mi faru aŭ ne faru ĉi lasta pasu? 657 00:21:34,477 --> 00:21:35,810 Spektantaro: Ne estis ŝanĝoj. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Pardonu? 659 00:21:36,120 --> 00:21:37,070 Publiko: Neniuj ŝanĝoj. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Ne estis ŝanĝoj. 661 00:21:38,653 --> 00:21:41,947 Do estus stulta de mi faros tion saman algoritmon denove 662 00:21:41,947 --> 00:21:43,780 se mi ne faris ajnan ŝanĝas la unua fojo. 663 00:21:43,780 --> 00:21:45,160 Kaj la stato ne ŝanĝiĝis. 664 00:21:45,160 --> 00:21:47,576 Certe, mi ne tuj fari ajna ŝanĝas duafoje. 665 00:21:47,576 --> 00:21:49,820 Kaj se tiel, estas sekura nun diri, listo estas aranĝita. 666 00:21:49,820 --> 00:21:52,069 >> Kaj efektive, tiu estas nun iu kiu ni ĝenerale 667 00:21:52,069 --> 00:21:56,900 alvoko bobelo varo, per duope, vi korekti erarojn denove, 668 00:21:56,900 --> 00:22:00,210 kaj denove, kaj denove, kaj vi plu iri tien kaj reen, 669 00:22:00,210 --> 00:22:03,370 kaj reen, ĝis vi faru nenian tian svopoj, ĉe kiu punkto 670 00:22:03,370 --> 00:22:07,089 vi povas esti certa, jes, mi finis fiksi ĉiujn la erarojn. 671 00:22:07,089 --> 00:22:08,630 Ni retrovu kaj provi alian aliron. 672 00:22:08,630 --> 00:22:11,590 Se vi infanoj povis reeniri la ordon vi estis antaŭ momento, 673 00:22:11,590 --> 00:22:13,780 kiu aspektis kiel ĉi. 674 00:22:13,780 --> 00:22:17,640 Nun, ni prenu alproksimiĝon de iom pli kiel la ekzameno libro, 675 00:22:17,640 --> 00:22:21,122 per kiu ni estis konstante elektanta la litero de la alfabeto 676 00:22:21,122 --> 00:22:22,830 ke ni ia volis trakti sekva. 677 00:22:22,830 --> 00:22:26,420 Eble estis alta leteron, kiel A, aŭ malalta letero Z. 678 00:22:26,420 --> 00:22:28,170 >> Do ĉiuj estas reen en tiu ordo. 679 00:22:28,170 --> 00:22:29,800 Kaj nun lasu min fari tion. 680 00:22:29,800 --> 00:22:34,880 Ni vidu Mi scias min havas ok numeroj tie. 681 00:22:34,880 --> 00:22:37,410 Mi tuj iros antaŭen kaj nur intence elektu 682 00:22:37,410 --> 00:22:38,520 la plej malgranda eroj. 683 00:22:38,520 --> 00:22:38,760 Dekstra? 684 00:22:38,760 --> 00:22:39,801 Tio ŝajnas tro intuicia. 685 00:22:39,801 --> 00:22:42,560 Kial mi ne trovos la plej malgranda elemento, metis ĝin kie ĝi apartenas, 686 00:22:42,560 --> 00:22:45,280 tiam akiri la sekva plej malgranda elemento, metis ĝin kie ĝi apartenas, kaj nur ripetas. 687 00:22:45,280 --> 00:22:46,820 >> Ĉar intuicie, kiuj devus labori tro. 688 00:22:46,820 --> 00:22:48,441 Do kvar, kiuj estas sufiĉe malgranda nombro. 689 00:22:48,441 --> 00:22:49,940 Mi tuj memori kie tiu estas. 690 00:22:49,940 --> 00:22:50,523 Atendu minuton. 691 00:22:50,523 --> 00:22:51,577 Du estas pli malgranda. 692 00:22:51,577 --> 00:22:53,910 Lasu min nun memoras kie du estas, kaj forgesas pri kvar. 693 00:22:53,910 --> 00:22:55,050 Ni agos laŭ tiu poste. 694 00:22:55,050 --> 00:22:56,460 Ses, mi ne estas interesita. 695 00:22:56,460 --> 00:22:57,810 Ok, mi ne interesiĝis. 696 00:22:57,810 --> 00:22:59,780 Unu mia nova malgranda nombro. 697 00:22:59,780 --> 00:23:01,470 Do mi tuj memoras, kie oni estas. 698 00:23:01,470 --> 00:23:02,534 Tri, ne interesas. 699 00:23:02,534 --> 00:23:03,450 Sep, ne interesas. 700 00:23:03,450 --> 00:23:04,530 Kvin, ne interesas. 701 00:23:04,530 --> 00:23:07,390 >> Do sen defalado la scenejo ĉi jaro, 702 00:23:07,390 --> 00:23:09,890 Mi tuj ekpreni nombro one-- kaj kio estis via nomo denove? 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 Kaj se vi povus aliĝi min ĉe la komenco de la listo, 706 00:23:13,540 --> 00:23:14,870 ni kunigu vin kie vi apartenas. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- kio estas via nomo? 708 00:23:16,080 --> 00:23:16,650 >> Stefan: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan estas en la vojo. 710 00:23:18,191 --> 00:23:23,490 Do antaŭ Stefan solvas tiun problemon, kion ni faru? 711 00:23:23,490 --> 00:23:25,412 Kion ni faru kun Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Spektantaro: [inaudible]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: Bone. 714 00:23:28,060 --> 00:23:28,850 Do ni povus fari tion. 715 00:23:28,850 --> 00:23:31,730 Ni povus ia preni Stefan kaj liaj kvar, kaj nur metis ĝin en variablo 716 00:23:31,730 --> 00:23:33,530 kaj teni ĝin por iu kvanto de tempo, 717 00:23:33,530 --> 00:23:35,220 tiel farante spaco por numero unu. 718 00:23:35,220 --> 00:23:36,280 Kaj tio estas ne malbona. 719 00:23:36,280 --> 00:23:39,270 Mi povus sugesti, kial ne ni ĵus metis Stefan tie? 720 00:23:39,270 --> 00:23:41,610 Kial povus tiu seksperforti unu de la ideoj ni komencis 721 00:23:41,610 --> 00:23:44,830 parolante pri pasinta tempo, pasinta semajno? 722 00:23:44,830 --> 00:23:45,330 Yeah? 723 00:23:45,330 --> 00:23:45,740 >> Spektantaro: [inaudible]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Estas ne indekso por ĝi. 725 00:23:46,860 --> 00:23:49,735 Se vi pensas pri tio, ja, kiel tabelo, tio estas kiel negativa, 726 00:23:49,735 --> 00:23:52,900 do ne memoro reale tie se ĉi tiu estas ja tabelo, 727 00:23:52,900 --> 00:23:55,090 kiel ni deklaris pasintsemajne en prelego. 728 00:23:55,090 --> 00:23:56,250 Do ni ne devus fari tion. 729 00:23:56,250 --> 00:23:57,340 Ni povus stoki ĝin en variablo. 730 00:23:57,340 --> 00:23:57,820 >> Aŭ vi scias kion? 731 00:23:57,820 --> 00:23:59,153 Mi aŭdis iun ajn sugestas ĝin. 732 00:23:59,153 --> 00:24:01,020 Kion alian ni povus fari kun Stefan? 733 00:24:01,020 --> 00:24:03,770 Kial ni ne simple elhejmigi lin kaj metis lin super kie numero unu estis. 734 00:24:03,770 --> 00:24:05,170 Do se vi volas iri tien. 735 00:24:05,170 --> 00:24:07,300 Kaj efektive, tiu estas sufiĉe bona solvo. 736 00:24:07,300 --> 00:24:10,480 Nun unuflanke, mi havas specon de farita la problemo malbona. 737 00:24:10,480 --> 00:24:13,650 Kvar estas nun pli malproksima de kie ĝi devus esti. 738 00:24:13,650 --> 00:24:14,900 Ĝi devus estos kun tiu duono. 739 00:24:14,900 --> 00:24:16,100 >> Sed vi scias kion? 740 00:24:16,100 --> 00:24:17,630 Kiu povus esti estinta malbona sorto. 741 00:24:17,630 --> 00:24:18,822 Eble nombro ok estis tie. 742 00:24:18,822 --> 00:24:20,530 Kaj do, eble ni farus akiris bonŝanca, 743 00:24:20,530 --> 00:24:22,460 kaj puŝis ok pli proksime al la fino. 744 00:24:22,460 --> 00:24:24,710 Do en la fino de la tago, ĝi specon de ĉiuj mezumoj eksteren. 745 00:24:24,710 --> 00:24:26,085 Ni ne bezonas zorgi pri kvar. 746 00:24:26,085 --> 00:24:29,400 Ĉiuj mi zorgas pri nun estas elektante la plej malgranda ero. 747 00:24:29,400 --> 00:24:32,030 >> Kaj nun, kion mi tuj fari estas forgesas pri nombro unu 748 00:24:32,030 --> 00:24:35,160 konstante, ĉar mi konas la listo malantaŭ mi nun ordo. 749 00:24:35,160 --> 00:24:36,720 Do mia listo estis antaŭe grandeco ok. 750 00:24:36,720 --> 00:24:37,720 Nun, estas de grandeco sep. 751 00:24:37,720 --> 00:24:40,340 Do mia problemo fariĝas malgranda, kvankam lineare. 752 00:24:40,340 --> 00:24:43,022 Do nun, mi tuj elektu la nuna malgranda elemento, du. 753 00:24:43,022 --> 00:24:46,520 Ses, ok, kvar, tri, sep, kvin. 754 00:24:46,520 --> 00:24:47,770 Tio estis la plej malgranda ero. 755 00:24:47,770 --> 00:24:49,416 Do kio mi estas iranta fari with-- kio via nomo denove? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Jozef. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Jozef? 758 00:24:50,085 --> 00:24:52,000 Ni tuj forlasi Jozef en loko. 759 00:24:52,000 --> 00:24:54,842 Nun, mi tuj ŝajnigi ke tiuj infanoj are-- bone, 760 00:24:54,842 --> 00:24:56,550 Mi scias ke tiuj du estas jam ordo. 761 00:24:56,550 --> 00:24:58,424 Ni nun enfokusigi la resto de la listo. 762 00:24:58,424 --> 00:25:00,080 Ses estas la nuna plej malgranda. 763 00:25:00,080 --> 00:25:01,190 Ok estas granda. 764 00:25:01,190 --> 00:25:02,970 Kvar estas nun la nuna malgranda. 765 00:25:02,970 --> 00:25:04,762 Tri estas nun la nuna malgranda. 766 00:25:04,762 --> 00:25:07,720 Kaj tial nun, mi tuj elektu tri, kiuj is-- kio estas via nomo denove? 767 00:25:07,720 --> 00:25:08,190 Serena: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, se vi povus Ekpreni vian numeron kaj interŝanĝa with-- 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 Venu reen, kaj ni estas tuj interŝanĝi tiujn du. 772 00:25:15,220 --> 00:25:17,360 Kaj nun ni kunigu ĉi sur autopilot. 773 00:25:17,360 --> 00:25:21,589 Mi tuj iros kaj lasi ĝin al vi infanoj elekti la sekva plej malgranda eroj. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Numero kvar, kion vi faras? 776 00:25:24,560 --> 00:25:26,261 Bonege. 777 00:25:26,261 --> 00:25:27,760 Nun, mi tuj faros alian enirpermesilon. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Mi vidas kvin estas la sekva plej malgranda. 780 00:25:31,465 --> 00:25:32,840 Nun, mi tuj prenos alian enirpermesilon. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Ses estas la plej malgranda. 783 00:25:34,880 --> 00:25:35,520 Bona. 784 00:25:35,520 --> 00:25:36,585 Sep estas la plej malgranda. 785 00:25:36,585 --> 00:25:37,085 Neniu ŝanĝo. 786 00:25:37,085 --> 00:25:38,630 Ok estas la plej malgranda. 787 00:25:38,630 --> 00:25:39,170 Done. 788 00:25:39,170 --> 00:25:43,900 >> Do kion ni ĵus faris per ripete selektante unu elemento post la alia 789 00:25:43,900 --> 00:25:47,230 estas implementar iu kiun ni estas tuj formaligi kiel selektado varon. 790 00:25:47,230 --> 00:25:49,120 Kaj estas eble eĉ pli simple klarigi, 791 00:25:49,120 --> 00:25:51,310 en kiu laŭvorte ĉiuj vi volas fari estas simple observu 792 00:25:51,310 --> 00:25:54,700 iri tien kaj reen tra la listo elektante, la sekva plej malgranda elemento, 793 00:25:54,700 --> 00:25:55,720 ĝis vi faris. 794 00:25:55,720 --> 00:25:58,650 >> Do estas eĉ pli simpla, eble intuicie, ol lasta. 795 00:25:58,650 --> 00:26:00,020 Ni provu unu lasta. 796 00:26:00,020 --> 00:26:03,060 Se vi uloj povas reagordi mem en jenajn poziciojn 797 00:26:03,060 --> 00:26:08,600 unu fina tempo, ni vidu, se ni ne povas nun formaligi unu alia alproksimiĝo. 798 00:26:08,600 --> 00:26:12,857 Fakte, ĉu iu tie ekstere ŝatus proponi 799 00:26:12,857 --> 00:26:14,440 kiel alie ni povus iri pri fari ĉi tion? 800 00:26:14,440 --> 00:26:17,439 Sen balanciĝadis el buzzwords aŭ varo de respondoj kiuj estas jam konataj, 801 00:26:17,439 --> 00:26:19,689 nur intuicie, kion ni povis fari? 802 00:26:19,689 --> 00:26:21,635 >> Spektantaro: [inaudible]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Yeah. 804 00:26:22,510 --> 00:26:24,620 Do ekzistas iu granda intuicio tie. 805 00:26:24,620 --> 00:26:28,020 Bonaj aĵoj ŝajnas okazi tiel malproksime en komputiko, kiam ni dividu 806 00:26:28,020 --> 00:26:30,832 kaj konkeri la problemo de dividanta ĝin en duono kaj duono kaj duono. 807 00:26:30,832 --> 00:26:32,540 Kaj tiel ja, ni povis komenci fari tion. 808 00:26:32,540 --> 00:26:35,754 Kaj fakte, tiu tuj estos, ni vidu, unu el niaj plej bonaj solvoj ankoraŭ. 809 00:26:35,754 --> 00:26:37,420 Sed ni revenu al tiu post nelonge. 810 00:26:37,420 --> 00:26:40,500 Fakte, ni tuj faros ke iom poste tiun semajnon. 811 00:26:40,500 --> 00:26:42,180 Kion alian povus fari por solvi tiun? 812 00:26:42,180 --> 00:26:44,647 Do ĉiuj ĉi tie estas en ŝajne hazarda ordo. 813 00:26:44,647 --> 00:26:45,230 Vi scias kion? 814 00:26:45,230 --> 00:26:48,320 Prefere ol iri tien kaj reen, tien kaj reen, tien kaj reen 815 00:26:48,320 --> 00:26:50,624 ĉiun fojon, ĉi sentas kiel Mi faras multajn piedirado. 816 00:26:50,624 --> 00:26:52,790 Kial ne mi simple komencu ĉe la komenco de la listo, 817 00:26:52,790 --> 00:26:54,960 kaj nur meti kvar kie apartenas? 818 00:26:54,960 --> 00:26:59,680 Do mi supozas ke por la momento mia listo estas nur tiu unua elemento. 819 00:26:59,680 --> 00:27:04,937 Estas kvar ordo ĉe tiu momento en tempo, se ne gravas al mi pri estas ĉio ĉi? 820 00:27:04,937 --> 00:27:06,520 Tiu estas speco de bagatele vera, ĉu ne? 821 00:27:06,520 --> 00:27:10,000 Kiel la liston enhavantan unu nombro, kaj tiu numero kvar estas evidente ordigita. 822 00:27:10,000 --> 00:27:13,070 >> Do mi simple kondiĉas ke tiu listo estas aranĝita. 823 00:27:13,070 --> 00:27:15,090 Sed nun mi havas la reston de tiu listo. 824 00:27:15,090 --> 00:27:17,240 Do nun, mi renkontas du. 825 00:27:17,240 --> 00:27:21,690 Kie faras du evidente apartenas kun respekto al kvar? 826 00:27:21,690 --> 00:27:22,580 Antaŭ kvar. 827 00:27:22,580 --> 00:27:23,862 Do kion mi povas fari tie? 828 00:27:23,862 --> 00:27:24,820 Kio estas via nomo denove? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Jozef. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Jozef, se vi povus retropaŝi 831 00:27:26,030 --> 00:27:27,790 por nur momento kun via nombro. 832 00:27:27,790 --> 00:27:31,130 Kaj nun kio devus Stefan faras tie? 833 00:27:31,130 --> 00:27:33,720 Ni movi Stefan super tie. 834 00:27:33,720 --> 00:27:35,520 Lasu do Jozef venis ĉi tien. 835 00:27:35,520 --> 00:27:39,660 Kaj nun lasu min aserti ke ĉio tie estas ordo. 836 00:27:39,660 --> 00:27:42,474 Do, simila rezulto, sed fundamente malsama alproksimiĝo. 837 00:27:42,474 --> 00:27:44,140 Mi eĉ ne rigardis kio estas tie malsupre. 838 00:27:44,140 --> 00:27:46,310 Mi daŭre prenante la elementoj kiam ili estas transdonitaj al mi, 839 00:27:46,310 --> 00:27:47,240 kaj trakti ilin. 840 00:27:47,240 --> 00:27:48,330 >> Do nun, mi vidas la numero ses. 841 00:27:48,330 --> 00:27:51,110 Kie numero ses aparteni? 842 00:27:51,110 --> 00:27:53,250 Ni havas du, kvar, ses. 843 00:27:53,250 --> 00:27:54,800 Precize kie ŝi estas ĝuste nun. 844 00:27:54,800 --> 00:27:57,750 Do ni lasos tion sole, kaj nun asertas ke tiu parto de la listo 845 00:27:57,750 --> 00:27:58,772 nun ordo. 846 00:27:58,772 --> 00:28:01,230 Kaj do, ĉi sentas fundamente malsama en ke mi estas nur 847 00:28:01,230 --> 00:28:05,230 movante tra la listo ĉi tie linie, kaj mi neniam duobliganta reen. 848 00:28:05,230 --> 00:28:05,730 Jes. 849 00:28:05,730 --> 00:28:06,230 Bone. 850 00:28:06,230 --> 00:28:08,190 Do ok, kie vi estas? 851 00:28:08,190 --> 00:28:08,730 Dekstra tie. 852 00:28:08,730 --> 00:28:09,310 Perfekta. 853 00:28:09,310 --> 00:28:10,210 Do nun, unu. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Tiu sentas estas tuj estos multekosta. 856 00:28:13,010 --> 00:28:15,690 Nun, en la antaŭa algoritmo, Mi ĵus interŝanĝis personoj. 857 00:28:15,690 --> 00:28:18,648 Do mi povu lin la tutan vojon en la komenco, sed poste movis Jozef. 858 00:28:18,648 --> 00:28:21,450 Sed se mi kopias Jozef, nun kio okazas estas malĝusta? 859 00:28:21,450 --> 00:28:24,250 >> Nun, mi havas ian undone-- mi havas prenita unu paŝon antaŭen kaj tiam 860 00:28:24,250 --> 00:28:26,300 retropaŝo, ĉar nun Joseph estus el ordo. 861 00:28:26,300 --> 00:28:26,830 Do ni faru ĉi. 862 00:28:26,830 --> 00:28:29,150 Se vi povus preni nombro unu kaj retropaŝi por nur momento. 863 00:28:29,150 --> 00:28:30,490 Kiel ni povas put-- kio estis via nomo denove? 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 loko? 866 00:28:32,610 --> 00:28:36,091 Kio devas okazi kun respekto por du, kvar, ses, ok? 867 00:28:36,091 --> 00:28:37,570 Ili ĉiuj devas movi. 868 00:28:37,570 --> 00:28:42,590 Do se ok ŝatus ŝanĝi unua, tiam ses, tiam kvar, tiam du. 869 00:28:42,590 --> 00:28:45,380 Kaj tiam Annan, se vi estus deziras veni tien, bone. 870 00:28:45,380 --> 00:28:47,760 Sed ĉi tie, ni ĵus ia pagis prezon 871 00:28:47,760 --> 00:28:49,510 ĉe malsama punkto en la algoritmo. 872 00:28:49,510 --> 00:28:52,550 Dum lasta tempo kun selektado speco, kaj eĉ bobelo varo, 873 00:28:52,550 --> 00:28:54,700 Mi promenis tien kaj elirante, tien kaj reen, 874 00:28:54,700 --> 00:28:58,360 kiu estas certe adicio tempo-saĝa, kaj laŭvorte _stepwise_. 875 00:28:58,360 --> 00:29:00,660 >> Inserción varo, unue rigardo, aspektas kiel ĝi estas 876 00:29:00,660 --> 00:29:05,150 súper inteligentaj, en kiuj mi estas nur farante malrapida, dumtajpa progreso, 877 00:29:05,150 --> 00:29:07,120 sed mi ne tuj ĉi tien kaj reen. 878 00:29:07,120 --> 00:29:09,410 Sed se iu estas ja el ordo, avizo 879 00:29:09,410 --> 00:29:10,840 ĉiuj la laboro mi nur devis fari. 880 00:29:10,840 --> 00:29:14,750 Mi devis movi duono de la listo nur por fari lokon por nombro unu. 881 00:29:14,750 --> 00:29:16,790 Do estas la sama kvanto de laboro kaj tiel ege ĝi 882 00:29:16,790 --> 00:29:18,690 sentas, nur malsama tipo de laboro. 883 00:29:18,690 --> 00:29:19,370 >> Ni daŭrigos. 884 00:29:19,370 --> 00:29:22,657 Do nun ni scias ke ĉiuj inter unu kaj ok estas ordo. 885 00:29:22,657 --> 00:29:23,740 Ĉi tie, mi havas numeron tri. 886 00:29:23,740 --> 00:29:25,864 Se vi ŝatus repreni numero tri, retropaŝi unu. 887 00:29:25,864 --> 00:29:28,260 Kaj kion vi uloj bezonas fari? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Do jen alia, du, tri paŝoj. 890 00:29:33,070 --> 00:29:36,010 Tri unuoj de tempo kiu nur kostis mi, tiel ke tri povas nun taŭgas. 891 00:29:36,010 --> 00:29:37,460 Fine, sep. 892 00:29:37,460 --> 00:29:39,730 >> Ni iru antaŭen kaj havas vi doni retropaŝon. 893 00:29:39,730 --> 00:29:42,780 Ĉi nur tuj kostos nin unu unuo de tempo, sed tio estas bone. 894 00:29:42,780 --> 00:29:44,170 Kaj nun, kvin tuj esti iom pli multekostaj. 895 00:29:44,170 --> 00:29:45,340 Se vi ŝatus retropaŝi. 896 00:29:45,340 --> 00:29:48,380 Ni devas movi ok, kaj sep kaj ses. 897 00:29:48,380 --> 00:29:50,749 Kaj poste ĉiuj estas nun ordo. 898 00:29:50,749 --> 00:29:52,290 Do grandan manon al niaj volontuloj tie. 899 00:29:52,290 --> 00:29:53,554 Multan dankon. 900 00:29:53,554 --> 00:29:56,220 >> [Aplaŭdo] 901 00:29:56,220 --> 00:29:56,860 >> Dankon ĉiuj. 902 00:29:56,860 --> 00:29:57,520 Dankon ĉiuj. 903 00:29:57,520 --> 00:30:02,940 Do ni vidu nun kiom kosta ĉiuj kiu estis. 904 00:30:02,940 --> 00:30:06,210 Ni konsideras eble la simpla el tiuj, bobelo varon. 905 00:30:06,210 --> 00:30:09,950 Kaj mi diras simple, nur ĉar vi povas solvi ĝin avide per nur 906 00:30:09,950 --> 00:30:11,660 ripari la duope problemo tie. 907 00:30:11,660 --> 00:30:13,720 Ripari la problemon duope tie, ree kaj ree 908 00:30:13,720 --> 00:30:17,680 kaj denove, ripetante kiel multaj tempoj kiel vi vere bezonas. 909 00:30:17,680 --> 00:30:21,050 >> Do rezultas ke kun bobelo varo, nu, 910 00:30:21,050 --> 00:30:25,820 kiom da paŝoj mi devas alpreni la unua enirpermesilo de tiu algoritmo? 911 00:30:25,820 --> 00:30:30,850 Mi povus take-- ni Konsideru unu, du, tri, kvar, kvin, ses, sep. 912 00:30:30,850 --> 00:30:32,190 Kaj estas ok elementoj tie. 913 00:30:32,190 --> 00:30:35,280 Do estas kiel n minus 1 paŝoj al ricevas el la komenco de la listo 914 00:30:35,280 --> 00:30:36,380 al la fino de la listo. 915 00:30:36,380 --> 00:30:41,350 >> Sed kun selektado varon, memoras ke mi elektanta la elementojn denove kaj denove 916 00:30:41,350 --> 00:30:44,590 kaj denove jen malgranda, Mi metas ĝin en lokon, 917 00:30:44,590 --> 00:30:46,616 sed tiam mi ne rigardante malantaŭ mi. 918 00:30:46,616 --> 00:30:49,490 Do mi kredas ke estas iom pli klara tiam ke la unua fojo, mi povus 919 00:30:49,490 --> 00:30:52,680 devas preni ĉiuj n minus 1 paŝoj por trovi la plej malgranda ero. 920 00:30:52,680 --> 00:30:55,920 Tiam mi metis ilin en lokon kaj elhejmigi ajn estis tie antaŭe. 921 00:30:55,920 --> 00:30:57,500 >> Sed tiam mi ne devas teni rigardanta tiun elementon, 922 00:30:57,500 --> 00:30:59,040 ĉar mi scias, ke tio Jam la plej eta. 923 00:30:59,040 --> 00:31:01,581 Do nun, mi povas rigardi nur sep elementoj, tiam ses elementoj, 924 00:31:01,581 --> 00:31:03,290 tiam kvin elementoj, tiam kvar elementoj. 925 00:31:03,290 --> 00:31:06,900 Do matematike, se n estas la nombro de elementoj aŭ nombroj 926 00:31:06,900 --> 00:31:11,990 ke ni komencis kun, vi povas imagi ke tio estas la sama kiel n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 paŝoj, plus n minus 3 paŝojn, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 paŝoj, ĉiuj vojon malsupren al nur unu paŝo. 929 00:31:16,780 --> 00:31:18,160 Kaj mi sur mia lasta persono. 930 00:31:18,160 --> 00:31:20,650 >> Kaj se vi memoras, ke multo el stats libroj aŭ math libroj 931 00:31:20,650 --> 00:31:24,730 havas tiujn formulojn sur la Hardcover dorso aŭ antaŭ ili, 932 00:31:24,730 --> 00:31:27,690 ĝi rezultas ke ĉi tiu serio povas esti esprimita pli simple 933 00:31:27,690 --> 00:31:28,857 kiel n × n minus 1 super 2. 934 00:31:28,857 --> 00:31:31,273 Kaj ĝi estas bone se tio ne ĉe la avangardo de via menso. 935 00:31:31,273 --> 00:31:32,420 Sed tio estas ja vera. 936 00:31:32,420 --> 00:31:34,449 Tio estas nur pli simpla maniero skribi ĝin. 937 00:31:34,449 --> 00:31:36,240 Kaj tiam se vi opinias reen al grado lernejo, 938 00:31:36,240 --> 00:31:38,698 kiam vi komencu multiplikante aferojn, ĉi kompreneble 939 00:31:38,698 --> 00:31:41,820 estas nur n kvadratoj minus n dividita per 2. 940 00:31:41,820 --> 00:31:44,772 Ĉiuj mi faris estas pligrandigi la esprimoj tie. 941 00:31:44,772 --> 00:31:46,730 Kaj do ni reverki tiun iom malsame. 942 00:31:46,730 --> 00:31:49,780 Jen n kvadrato dividita per 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Do denove, mi estas nur speco de aplikanta iuj aritmetiko regas tie. 944 00:31:53,270 --> 00:31:57,140 Sed rimarki nun ke la plej granda termino en ĉi tiu esprimo, tiel diri, 945 00:31:57,140 --> 00:31:58,540 estas ke n kvadratoj. 946 00:31:58,540 --> 00:32:02,910 Do jes, ĝi estas n kvadratoj dividita per 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Sed ĝenerale, se n estas tuj estos granda valoro, 948 00:32:05,080 --> 00:32:08,740 Mi tuj asertas ke n kvadratoj tuj estos la domina faktoro. 949 00:32:08,740 --> 00:32:10,490 Ĝi simple tuj estos pli granda kontribuanto 950 00:32:10,490 --> 00:32:12,877 la nombro de paŝoj ol n / 2. 951 00:32:12,877 --> 00:32:13,960 Do kion mi celas per tio? 952 00:32:13,960 --> 00:32:16,795 Ni provu simplan ekzemplon, eĉ kvankam la math ricevas iom granda. 953 00:32:16,795 --> 00:32:20,210 >> Do eble ni havis 1 miliono personoj sur scenejo, aŭ 1 miliono aferoj 954 00:32:20,210 --> 00:32:21,320 ke ni volas ordigi. 955 00:32:21,320 --> 00:32:23,730 Ni plug miliono en ĝuste tiu formulo 956 00:32:23,730 --> 00:32:27,230 vidi kiom da ŝtupoj prenas entute ordigi miliono elementoj uzante diru, 957 00:32:27,230 --> 00:32:28,560 selektado varon. 958 00:32:28,560 --> 00:32:30,760 >> Do ni havus la saman formulon kiel antaŭe. 959 00:32:30,760 --> 00:32:34,120 Mi plug miliono, tiel ke mi ricevas miliono kvadrato dividita per 2, 960 00:32:34,120 --> 00:32:35,990 minus miliono dividita per 2. 961 00:32:35,990 --> 00:32:40,180 Se mi faras tion math anticipe tie, ni havas 500 Miliardo 962 00:32:40,180 --> 00:32:47,460 minuso 500,000, kiu donas nin 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 kiuj estas sufiĉe darn granda. 964 00:32:49,270 --> 00:32:54,370 >> Fakte, se vi komparas nun 499 miliardoj, 999 milionoj, 965 00:32:54,370 --> 00:33:01,210 500.000 kontraŭ nia originala valoro, 500 miliardoj, estas tiel malbenita proksime. 966 00:33:01,210 --> 00:33:06,850 Dekstra? n kvadrato dividita per 2 donas us-- aŭ prefere, n kvadrato dividita per 2 967 00:33:06,850 --> 00:33:08,370 donis al ni 500 miliardoj. 968 00:33:08,370 --> 00:33:13,510 Tio estas sufiĉe darn Fermi al 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 kio estas restante ekstere 500.000, aŭ pli ĝenerale, restante ekstere 970 00:33:17,970 --> 00:33:20,010 n kvadratoj, ne estas vere granda interkonsento. 971 00:33:20,010 --> 00:33:22,490 La n kvadratoj faras tiujn nombroj kreskos vere rapida. 972 00:33:22,490 --> 00:33:25,790 >> Nun, ĉi tiu estas grava nur en la mezuro kiel ni, kiel komputilo sciencistoj, 973 00:33:25,790 --> 00:33:29,350 ĝenerale ne tuj zorgas tiom pri la nuancoj de tiuj formuloj 974 00:33:29,350 --> 00:33:31,400 kaj ĝuste kion la preciza respondoj. 975 00:33:31,400 --> 00:33:33,390 Ni zorgas nur tio, vi scias kion? 976 00:33:33,390 --> 00:33:37,810 Fine de la tago, tiu formulo estas sur la ordo de n kvadratoj. 977 00:33:37,810 --> 00:33:39,350 >> Jes, ni dividante per 2 en tie. 978 00:33:39,350 --> 00:33:41,360 Jes, ni restante ekstere n minus 2. 979 00:33:41,360 --> 00:33:46,860 Sed fine de la tago, la termino ke vere doloras nin kaj kostas nin 980 00:33:46,860 --> 00:33:48,995 multaj paŝoj estas ke kvadrata terminon. 981 00:33:48,995 --> 00:33:51,370 Kaj tiel kion komputilo sciencisto tuj ĝenerale faras 982 00:33:51,370 --> 00:33:54,160 estas ignori ĉiuj tiuj malgrandaj por terminoj, 983 00:33:54,160 --> 00:33:56,900 kaj nur rigardi la unu kiu kontribuas la plej al la kosto. 984 00:33:56,900 --> 00:34:00,530 >> Kaj tiu estas bela, ĉar ni povas nun paroli en multa plej granda ĝeneraleco 985 00:34:00,530 --> 00:34:02,470 pri algoritmoj, kaj povas kompari ilin. 986 00:34:02,470 --> 00:34:04,550 Kaj la fakto ke mi estas uzante tiu O estas intenca. 987 00:34:04,550 --> 00:34:06,680 Kiam mi diras sur la ordo de, mi estas specife 988 00:34:06,680 --> 00:34:09,560 aludas ion nomata granda O. Kaj granda a 989 00:34:09,560 --> 00:34:14,090 Estas notacio ke komputilo sciencisto uzas por priskribi 990 00:34:14,090 --> 00:34:16,710 supera baro sur io. 991 00:34:16,710 --> 00:34:21,150 >> Do se vi diras ke algoritmo estas en granda a de n kvadratoj, 992 00:34:21,150 --> 00:34:23,380 kiel mi proponis nur antaŭ momento, ke per 993 00:34:23,380 --> 00:34:27,710 ke en terminoj de lia kurado tempo aŭ lia efikeco, 994 00:34:27,710 --> 00:34:30,090 prenas sur la ordo de n kvadratoj paŝoj. 995 00:34:30,090 --> 00:34:31,420 Eble pli, eble malpli. 996 00:34:31,420 --> 00:34:33,435 Sed ĝi estas sur la ordo de n kvadratoj. 997 00:34:33,435 --> 00:34:34,560 Kaj tio estas la superulo. 998 00:34:34,560 --> 00:34:36,530 Oni ne tuj esti pli dolora ol tio. 999 00:34:36,530 --> 00:34:40,800 Oni ne tuj esti n Cubed, aŭ 2 al la n, aŭ io multe pli granda. 1000 00:34:40,800 --> 00:34:43,800 Tio estas supera baro sur kii ke kosto estas. 1001 00:34:43,800 --> 00:34:46,150 Do donita ke, ni konsideru nur kelkajn ekzemplojn. 1002 00:34:46,150 --> 00:34:49,820 Kaj tiu estas nur finia listo de tre komunaj kurante fojojn 1003 00:34:49,820 --> 00:34:52,870 por algoritmoj kiu signifis esti ilustrativo de iuj aferoj ni 1004 00:34:52,870 --> 00:34:53,600 vidita jam. 1005 00:34:53,600 --> 00:34:58,060 >> Do ekzemple, en la kazo de selektado speco, kion mi asertante tie 1006 00:34:58,060 --> 00:35:02,250 estas ke selektado speco de kurado tempo estas sur la ordo de n kvadratoj. 1007 00:35:02,250 --> 00:35:06,260 En la plej malbona kazo, mi tuj havi tuta amaso de hazardaj nombroj tie. 1008 00:35:06,260 --> 00:35:08,600 Kaj kiel ni vidis matematike, se mi teni marŝi 1009 00:35:08,600 --> 00:35:11,310 tra la listo, tra la listo, selektante la sekva plej malgranda 1010 00:35:11,310 --> 00:35:14,410 elemento denove kaj denove, se mi fakte skribi malsupren ĉiuj la paŝoj 1011 00:35:14,410 --> 00:35:18,750 Mi prenas kiel mi proponis formulaically antaŭe, ĝi estas sur la ordo de n kvadratoj 1012 00:35:18,750 --> 00:35:20,370 paŝoj kiuj mi prenas. 1013 00:35:20,370 --> 00:35:24,520 >> Kaj ĝi rezultas ke bobelo varo kaj inserción varo 1014 00:35:24,520 --> 00:35:27,370 estas tiel malrapida en la plej malbona kazo. 1015 00:35:27,370 --> 00:35:32,040 Konsideru, ekzemple, inserción varo, la tre lasta algoritmo ni pritraktis, 1016 00:35:32,040 --> 00:35:35,500 kiu havis ni rigardu la elementon, kaj poste enmeti ĝin kie ĝi apartenas. 1017 00:35:35,500 --> 00:35:38,720 Kaj poste ni rigardis la sekva elemento, kaj enmetita ĝin kie ĝi apartenas. 1018 00:35:38,720 --> 00:35:40,990 >> Do konsideru la plej bona ebla scenaro. 1019 00:35:40,990 --> 00:35:45,590 Supozu mi mian volontuloj laŭliniigi laŭvorte kiel tiu, unu tra ok, 1020 00:35:45,590 --> 00:35:47,440 jam ordo. 1021 00:35:47,440 --> 00:35:51,300 Kiom da paŝoj estas inserción varo tuj prenos ordigi ok personoj, 1022 00:35:51,300 --> 00:35:55,640 se ili alvenas sur scenejo rigardante tiel? 1023 00:35:55,640 --> 00:35:57,410 >> Ok personoj jam ordo. 1024 00:35:57,410 --> 00:35:58,760 Kaj mi uzas inserción varon. 1025 00:35:58,760 --> 00:36:02,180 Ke lasta el la algoritmoj. 1026 00:36:02,180 --> 00:36:03,640 Nu, ni reenact reala rapida. 1027 00:36:03,640 --> 00:36:05,504 Do se mi komencas tie, mi vidas unu. 1028 00:36:05,504 --> 00:36:06,420 Kie oni apartenas? 1029 00:36:06,420 --> 00:36:07,730 Ĝi apartenas ĉi tie. 1030 00:36:07,730 --> 00:36:08,330 Mi vidas du. 1031 00:36:08,330 --> 00:36:09,660 Kie du apartenas? 1032 00:36:09,660 --> 00:36:10,260 Dekstra tie. 1033 00:36:10,260 --> 00:36:10,900 Mi vidas tri. 1034 00:36:10,900 --> 00:36:11,920 Kie tri aparteni? 1035 00:36:11,920 --> 00:36:12,480 Dekstra tie. 1036 00:36:12,480 --> 00:36:13,100 >> Mi vidas kvar. 1037 00:36:13,100 --> 00:36:13,600 Dekstra tie. 1038 00:36:13,600 --> 00:36:15,660 Kvin, ses, sep, ok. 1039 00:36:15,660 --> 00:36:17,320 Ekzistas neniu kialo por ripeti min mem. 1040 00:36:17,320 --> 00:36:21,260 Kaj tiel, kiom da ŝtupoj estas ke en terminoj de n? 1041 00:36:21,260 --> 00:36:23,870 Ĝi estas sur la ordo de n paŝoj, dekstra? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Sed Mi prenis lineara nombro de paŝoj kaj nun mi estas farita. 1043 00:36:27,567 --> 00:36:28,900 Do jen la plej bona kazo, tamen. 1044 00:36:28,900 --> 00:36:29,983 Kio pri la plej malbona kazo? 1045 00:36:29,983 --> 00:36:32,730 Kio ok estis tie, kaj sep estis malsupren tie, 1046 00:36:32,730 --> 00:36:35,840 kaj unu kaj du estis tie, tiom ke la listo estis vere inversigis? 1047 00:36:35,840 --> 00:36:38,300 >> Nu, kio okazas ja se tiu estas la nombro? 1048 00:36:38,300 --> 00:36:41,300 Kaj ni tion faros nur kelkaj ekzemploj. 1049 00:36:41,300 --> 00:36:49,300 Kio se, efektive, la numero ok estas tie, kaj la number-- whoops. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Do kio se, efektive, la nombro ok estas tute super tie, 1052 00:36:56,430 --> 00:36:57,790 kaj Mi uzas inserción varo? 1053 00:36:57,790 --> 00:36:58,290 >> BONE. 1054 00:36:58,290 --> 00:37:00,280 Mi asertas nuntempe estas en loko. 1055 00:37:00,280 --> 00:37:03,152 Sed nun, seven-- kie does sep iras? 1056 00:37:03,152 --> 00:37:04,360 Kompreneble, ĝi iras tien. 1057 00:37:04,360 --> 00:37:06,760 Do mi devas movi ok super unu loko. 1058 00:37:06,760 --> 00:37:08,554 Nun ses, kie ĝi iras? 1059 00:37:08,554 --> 00:37:09,220 Nu, bone. 1060 00:37:09,220 --> 00:37:13,150 Nun, mi devas movi ok super lokon, kaj sep super loko, 1061 00:37:13,150 --> 00:37:14,440 kaj tiam mi Plop malsupren ses. 1062 00:37:14,440 --> 00:37:16,870 >> Do la unua fojo, ĝi kosto mi unu paŝo ripari aĵojn, 1063 00:37:16,870 --> 00:37:18,570 tiam ĝi kostis al mi du paŝojn al ripari aĵojn. 1064 00:37:18,570 --> 00:37:20,370 Kiom da paŝoj estas tuj prenos ripari 1065 00:37:20,370 --> 00:37:22,720 aferojn meti kvin en la ĝusta loko? 1066 00:37:22,720 --> 00:37:23,340 Tri. 1067 00:37:23,340 --> 00:37:29,520 Ĉar nun mi devas movi unu, du, tri. 1068 00:37:29,520 --> 00:37:32,430 Kiom da paŝoj estas ĝi iranta preni meti kvar en la ĝusta loko? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6, plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> Kaj do ĝi estas matematike identa al kion ni priskribis por selektado speco. 1071 00:37:40,260 --> 00:37:42,130 Ni havas ĉi tiu serio Tio simple kreskanta. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, aŭ inverse, estas 7, 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 Plus 4 adicias supren por hodiaŭaj intencoj al sur la ordo de n kvadratoj. 1074 00:37:52,610 --> 00:37:57,640 >> Do lasu min kondiĉas tro ke bobelo varo estas ankaŭ en n kvadratoj. 1075 00:37:57,640 --> 00:38:01,340 Ĉar kun bobelo varo, ĉiu tempo mi iras tra la listo, 1076 00:38:01,340 --> 00:38:03,100 Mi prenas proksimume kiom da paŝoj? 1077 00:38:03,100 --> 00:38:06,260 Ĉiufoje mi laŭvorte marŝi de tie al tie? 1078 00:38:06,260 --> 00:38:07,960 Malglate n paŝoj. 1079 00:38:07,960 --> 00:38:12,650 Sed kiom da fojoj eble mi bezonas iri tra la listo? 1080 00:38:12,650 --> 00:38:13,920 >> Nu, malglate n tempon. 1081 00:38:13,920 --> 00:38:15,680 Eble n minus 1, sed malglate n fojojn. 1082 00:38:15,680 --> 00:38:16,430 Nu, kial do? 1083 00:38:16,430 --> 00:38:19,560 Nu, kun bobelo varo, se ni komencu per bobelo varo, 1084 00:38:19,560 --> 00:38:23,570 kun la listo en la plej malbona ebla situacio, kiu denove estas tute 1085 00:38:23,570 --> 00:38:25,550 dorsdirekte kio okazos? 1086 00:38:25,550 --> 00:38:28,830 Mi iros tra la listo, kaj nombro oni apartenas tuta vojo super tie. 1087 00:38:28,830 --> 00:38:33,280 >> Sed kun bobelo varo, kiom faras unu movi mian unuan enirpermesilon tra la listo? 1088 00:38:33,280 --> 00:38:36,620 Kiom da makuloj ĉu li ricevos pli proksima al la ĝusta loko? 1089 00:38:36,620 --> 00:38:37,240 Nur unu. 1090 00:38:37,240 --> 00:38:40,281 Do se vi ia kialo tra tiu, ĉiufoje tra tiu algoritmo, 1091 00:38:40,281 --> 00:38:41,880 David prenante malglate n paŝoj. 1092 00:38:41,880 --> 00:38:44,940 Sed kiom da paŝoj tra la listo estas ĝi 1093 00:38:44,940 --> 00:38:49,060 tuj prenos unu al bobelo maldekstren kie apartenas? 1094 00:38:49,060 --> 00:38:51,840 >> Li havas movi kiel, n spacoj tiamaniere. 1095 00:38:51,840 --> 00:38:57,960 Do simple fari la ordigado de la listo, Mi devas piediri reen n fojojn. 1096 00:38:57,960 --> 00:39:01,540 Kaj ĉiufoje, mi estas rigardante n elementoj. 1097 00:39:01,540 --> 00:39:05,410 Do faru n aferoj n fojoj sur la ordo de n kvadratoj. 1098 00:39:05,410 --> 00:39:07,220 >> Nun, ni vidos en iuj de la mallongaj kiu 1099 00:39:07,220 --> 00:39:10,440 estas enigita en CS50 la sekva problemo fiksita, alia alproksimiĝo ĉe tiuj, 1100 00:39:10,440 --> 00:39:13,490 Sed nuntempe, ni nur konsideras iuj aliaj kurante fojojn, 1101 00:39:13,490 --> 00:39:16,840 speciale se la ordigado prenas iomete da tempo sinki je. 1102 00:39:16,840 --> 00:39:21,790 Kio estas algoritmo ni vidis jam kiu prenas sur la ordo de n paŝoj? 1103 00:39:21,790 --> 00:39:27,560 >> Kio devus preni lineara nombro de paŝoj kiujn ni vidis ĝis nun? 1104 00:39:27,560 --> 00:39:29,350 Kio estas tio? 1105 00:39:29,350 --> 00:39:30,480 La telefono dosierujo serĉo. 1106 00:39:30,480 --> 00:39:31,390 La unua algoritmo. 1107 00:39:31,390 --> 00:39:31,560 Dekstra? 1108 00:39:31,560 --> 00:39:33,650 Kie ni estas lineare serĉanta Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Fakte. 1110 00:39:34,150 --> 00:39:37,180 De semajno nulo, kiam mi komencis turnante unu paĝo samtempe, 1111 00:39:37,180 --> 00:39:40,095 kaj mi eĉ diris ke estis speco de lineara sento algoritmo, 1112 00:39:40,095 --> 00:39:42,720 kaj ni havis tiun bildon sur la tabulo kun la rektan ruĝan linion 1113 00:39:42,720 --> 00:39:44,678 kaj la rektan flavan linio, estis ĝuste 1114 00:39:44,678 --> 00:39:46,810 algoritmoj kiuj estas en granda a de n. 1115 00:39:46,810 --> 00:39:50,680 >> Ĉar trovi Mike Smith en telefono libro de n paĝoj, en la plej malbona kazo, 1116 00:39:50,680 --> 00:39:52,422 povus porti min n paŝoj. 1117 00:39:52,422 --> 00:39:53,630 Kio pri preni asistencia? 1118 00:39:53,630 --> 00:39:55,790 Unu, du, tri, kvar, kvin, ses. 1119 00:39:55,790 --> 00:39:59,420 Kio estas la rula tempo de ĉi tiu Algoritmo por prenanta asistencia? 1120 00:39:59,420 --> 00:40:03,070 Big O de n, ĉar en teorio mi devas atentigi ĉiuj en la ĉambro. 1121 00:40:03,070 --> 00:40:05,861 >> Nun kiel flanken, kio pri la aliaj optimumigo el semajno nulo? 1122 00:40:05,861 --> 00:40:08,117 Du, kvar, ses, ok, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Komputila sciencisto realigi, atendu minuton, 1124 00:40:10,200 --> 00:40:12,320 jen sur la ordo de n dividita per du paŝoj. 1125 00:40:12,320 --> 00:40:12,820 Dekstra? 1126 00:40:12,820 --> 00:40:14,444 Ĉar mi faras du personoj samtempe. 1127 00:40:14,444 --> 00:40:17,015 Sed ni tuj ignori tiuj malsupera ordo terminoj, 1128 00:40:17,015 --> 00:40:19,140 kaj ni ĵus tuj forĵetu la dividi per 2, 1129 00:40:19,140 --> 00:40:21,830 kaj ĝuste diri, granda a de n por ke algoritmo ankaŭ. 1130 00:40:21,830 --> 00:40:22,760 >> Kio pri ĉi tiu? 1131 00:40:22,760 --> 00:40:26,170 Ni salti super iu de ĉi tiuj, sed kio Estis algoritmo kiu estis log de n? 1132 00:40:26,170 --> 00:40:29,900 Kiu prenis proksimume log n paŝoj? 1133 00:40:29,900 --> 00:40:30,870 La dividu kaj regu. 1134 00:40:30,870 --> 00:40:31,369 Ekzakte. 1135 00:40:31,369 --> 00:40:33,900 Kiel la telefono libro ekzemple en semajno nulo kaj pli frue hodiaŭ, 1136 00:40:33,900 --> 00:40:36,191 kie ni dividis la problemo denove kaj denove kaj denove. 1137 00:40:36,191 --> 00:40:39,070 Ni tiris ĝin sur la tabulo en semajno nulo kiel kurba verda linio, 1138 00:40:39,070 --> 00:40:41,460 kaj ni diris ke tago estis logaritma algoritmo. 1139 00:40:41,460 --> 00:40:44,970 >> Kaj efektive, la nombro de paŝoj prenas elfari dividu kaj regu, 1140 00:40:44,970 --> 00:40:48,610 aŭ duuma serĉo kiel ni komencos nomante ĝin, kiel en la telefono libro, 1141 00:40:48,610 --> 00:40:50,680 estas sur la ordo de protokolo kaj paŝoj. 1142 00:40:50,680 --> 00:40:52,470 Kaj tiu estas iom de bizara unu. 1143 00:40:52,470 --> 00:40:54,910 >> Kio prenas unu paŝon, aŭ pli specife 1144 00:40:54,910 --> 00:40:56,240 konstanta nombro de paŝoj? 1145 00:40:56,240 --> 00:40:58,865 Eble estas du, eble estas tri, sed komputila sciencisto ĵus 1146 00:40:58,865 --> 00:41:01,423 simpligas ĝin kiel granda O de 1, iu konstanto nombro de paŝoj. 1147 00:41:01,423 --> 00:41:04,256 Kio estas io vi povus fari tion prenas konstanta nombro de paŝoj? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Kio estas la rula tempo de kunfrapante? 1150 00:41:10,930 --> 00:41:11,920 Konstanta tempo. 1151 00:41:11,920 --> 00:41:12,420 Dekstra? 1152 00:41:12,420 --> 00:41:15,490 Kiel, kio estas la rula tempo de fari ion kio prenas nur unu 1153 00:41:15,490 --> 00:41:18,570 operacion, kiel presi F Saluton Mondo. 1154 00:41:18,570 --> 00:41:24,110 Tio povus esti dirita esti konstanta tempo, se malpli angulo kazo kun presitaj F, 1155 00:41:24,110 --> 00:41:28,260 Kio povus la rultempo de presaĵo F reale esti? 1156 00:41:28,260 --> 00:41:28,790 Kaj kial? 1157 00:41:28,790 --> 00:41:30,550 Kio estas n mezura en tiu kazo? 1158 00:41:30,550 --> 00:41:32,251 >> Spektantaro: [inaudible]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Ĝuste. 1160 00:41:33,250 --> 00:41:34,900 La nombro de karakteroj ni volas presi. 1161 00:41:34,900 --> 00:41:36,191 Do estas tre kuntekst-sentema. 1162 00:41:36,191 --> 00:41:39,910 Hodiaŭ, ni estis enfokusigante multe sur literoj kaj numeroj tie sur la tabulo. 1163 00:41:39,910 --> 00:41:43,540 Sed povus ankaŭ esti karakteroj en reala kordoj. 1164 00:41:43,540 --> 00:41:46,420 Do rezultas ke estas alia mezurilo komencos zorgi pri, 1165 00:41:46,420 --> 00:41:48,530 kaj tio estas la malo de granda a, por tiel diri. 1166 00:41:48,530 --> 00:41:50,120 >> Tio omega skribmaniero. 1167 00:41:50,120 --> 00:41:53,380 Dum granda a signifas kio estas, la supera baro sur via rultempo? 1168 00:41:53,380 --> 00:41:55,580 Maksimume, kiom da tempo povus ion prenos? 1169 00:41:55,580 --> 00:41:59,250 Omega-- bedaŭras ĉi levas up-- estas la malo de tio, 1170 00:41:59,250 --> 00:42:02,960 per ĝi estas suba baro sur la kvanto de tempo iu povus preni. 1171 00:42:02,960 --> 00:42:10,480 >> So. Ekzemple, kio estas algoritmo kiu postrestas ĉiam n kvadratoj paŝoj? 1172 00:42:10,480 --> 00:42:15,600 Nu, unu el la algoritmoj ni vidis hodiaŭ, fakte, povus esti ke ankaŭ. 1173 00:42:15,600 --> 00:42:16,720 Selektado varo. 1174 00:42:16,720 --> 00:42:18,270 Selektado speco estas sufiĉe stulta. 1175 00:42:18,270 --> 00:42:21,760 Eĉ se la algorithm-- bedaŭras, eĉ se la tabelo jam ordo, 1176 00:42:21,760 --> 00:42:24,150 selektado varo estas tuj teni promenante tra la listo 1177 00:42:24,150 --> 00:42:28,907 certigi ĝi havas la plej malgrandan elemento denove kaj denove kaj denove. 1178 00:42:28,907 --> 00:42:31,740 Kaj eĉ se vi homoj en la spektantaron scii ke, atendu minuton, 1179 00:42:31,740 --> 00:42:33,948 vi jam pasis la plej malgranda elemento, la komputilo 1180 00:42:33,948 --> 00:42:37,300 Ne scias ke ĝis ĝi aspektas tutan vojon tra la listo. 1181 00:42:37,300 --> 00:42:40,240 Simile, suba baro ke povus ankaŭ konsideri 1182 00:42:40,240 --> 00:42:42,000 estu lineara tempo. 1183 00:42:42,000 --> 00:42:48,260 >> Kiom da tempo estas bezonata por ia n elementoj en la plej bona 1184 00:42:48,260 --> 00:42:52,420 kazo uzante ion kiel bobelo varo? 1185 00:42:52,420 --> 00:42:54,280 Supozi via listo estas jam ordo. 1186 00:42:54,280 --> 00:42:56,696 Ni diris bobelo varo prenas sur la ordo de n kvadratoj paŝoj. 1187 00:42:56,696 --> 00:42:59,640 Sed kio se ĝi estas jam ordo? 1188 00:42:59,640 --> 00:43:02,310 Kio se oni rimarkas post unu enirpermesilo tra la tabelo 1189 00:43:02,310 --> 00:43:03,540 ke vi faris neniun svopoj? 1190 00:43:03,540 --> 00:43:05,970 Ĉu vi devas teni farante pli pasas? 1191 00:43:05,970 --> 00:43:06,470 >> No. 1192 00:43:06,470 --> 00:43:10,340 Do suba baro sur bobelo varo povus esti dirita esti lineara. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 Kaj ni povas rigardi aliaj de ĉi tiuj tiel. 1195 00:43:14,450 --> 00:43:17,990 Do ni prenu rapidan rigardon ĉe ĝuste visualización tie 1196 00:43:17,990 --> 00:43:20,790 vidi kiel tiuj heroe. 1197 00:43:20,790 --> 00:43:24,592 Mi tuj iros malsupren tie en tiu paĝo kiu estas havebla sur la retejo de C50, 1198 00:43:24,592 --> 00:43:27,550 sed estos doloro akiri laborante, kiam ĝi uzas teknologion nomita 1199 00:43:27,550 --> 00:43:30,560 Java apletoj, kiu estas grandparte nesubtenata tiuj tagoj, 1200 00:43:30,560 --> 00:43:32,730 almenaŭ per Chrome kaj iuj aliaj. 1201 00:43:32,730 --> 00:43:37,070 >> Kaj lasu min antaŭeniri kaj akceli ĉi tien kaj klarigi kio okazas. 1202 00:43:37,070 --> 00:43:40,840 Jen pruvo de bobelo varon, la unua algoritmo ni rigardis. 1203 00:43:40,840 --> 00:43:43,950 Kaj ĝi estas visualización en kiuj ĉiu de tiuj stangoj reprezentas ciferon. 1204 00:43:43,950 --> 00:43:45,710 La pli granda la trinkejo, la pli granda la nombro. 1205 00:43:45,710 --> 00:43:47,520 La pli malgranda la trinkejo, la pli malgranda la nombro. 1206 00:43:47,520 --> 00:43:50,353 Kaj kion vi povas vidi vide, eĉ kvankam ĉi tiu tuj super rapida, 1207 00:43:50,353 --> 00:43:53,699 estas ke la ruĝa stango estas kiel mi, marŝi tien kaj reen fiksi problemojn. 1208 00:43:53,699 --> 00:43:56,740 Vi povas vidi ke la pli grandaj elementoj estas ja bobelis supren dekstren, 1209 00:43:56,740 --> 00:43:59,650 kaj la pli malgrandaj elementoj estas bobelis supren maldekstren. 1210 00:43:59,650 --> 00:44:01,870 Kaj ĉi tie malsupre, se ni fakte aspektas pli proksime, 1211 00:44:01,870 --> 00:44:04,330 ni povas vere kalkuli la numeron de komparoj kaj svopoj 1212 00:44:04,330 --> 00:44:05,350 ke oni fabrikis. 1213 00:44:05,350 --> 00:44:07,360 >> Sed anstataŭe, ni rigardu ĉe la dua algoritmo 1214 00:44:07,360 --> 00:44:11,240 ni rigardis antaŭe kun nia volontuloj, selektado varo. 1215 00:44:11,240 --> 00:44:13,500 Vide, ĝi havas tre malsama efiko. 1216 00:44:13,500 --> 00:44:16,820 Sed estas, denove, tre intuicia, en ke ni observas elektanta la sekva plej malgranda 1217 00:44:16,820 --> 00:44:18,660 elemento, kaj ni akiris iom bonŝanca. 1218 00:44:18,660 --> 00:44:20,110 Kiu sentis funde rapida. 1219 00:44:20,110 --> 00:44:22,840 Sed se ni kuris ĉi denove kaj denove kaj denove kun multaj enigoj, 1220 00:44:22,840 --> 00:44:26,680 ni vidus ke ĝi estas efektive ankoraŭ en granda a de n kvadratoj. 1221 00:44:26,680 --> 00:44:29,920 >> Ni faru unu lasta tie, inserción varo, 1222 00:44:29,920 --> 00:44:33,180 kiu estis la tria algoritmo Ni rigardis, kaj revoko 1223 00:44:33,180 --> 00:44:36,700 ke ĉi tiu traktas la elementoj kiel ĝi renkontas ilin, 1224 00:44:36,700 --> 00:44:39,290 sed tiam eble ŝanĝoj aĵoj super fari ĉambron, 1225 00:44:39,290 --> 00:44:41,660 enmeto elementoj kie apartenas. 1226 00:44:41,660 --> 00:44:45,330 >> Kaj tiun tro finas donante la finan rezulton. Nun ĉiuj tri de tiuj 1227 00:44:45,330 --> 00:44:46,490 sentis sufiĉe rapida. 1228 00:44:46,490 --> 00:44:48,740 Kaj efektive, mi kuris ilin ĉe sufiĉe bona klipo. 1229 00:44:48,740 --> 00:44:52,510 Sed fundamente, ili ja ĉiuj bela hororiga esti honesta. 1230 00:44:52,510 --> 00:44:56,960 Ĉiuj de ĉi tiuj algoritmoj ĝis nun kiuj kuras en granda a de n kvadratoj 1231 00:44:56,960 --> 00:44:59,270 preni sufiĉe de tempo por kuri en la fino. 1232 00:44:59,270 --> 00:45:01,920 >> Kaj efektive, ni povas vidi Kaj senti ĉi persiste 1233 00:45:01,920 --> 00:45:04,090 se mi elsxiros ĉi tria kaj lasta demo. 1234 00:45:04,090 --> 00:45:05,840 Tio estas alia videbligo kiu tuj 1235 00:45:05,840 --> 00:45:08,500 montri bobelo varo maldekstre selektado varo en la mezo, 1236 00:45:08,500 --> 00:45:13,410 kaj io, kiel unu el niaj mano levas frue sugestis, 1237 00:45:13,410 --> 00:45:15,020 kunfandi speco sur la dekstran. 1238 00:45:15,020 --> 00:45:16,937 Dividu kaj regu strategio dekstre. 1239 00:45:16,937 --> 00:45:19,520 Kaj tio estas, fakte, kion ni estas tuj rigardi merkrede. 1240 00:45:19,520 --> 00:45:21,990 Sed ni tempo tiuj kuri en paralela. 1241 00:45:21,990 --> 00:45:26,765 Ĝi estas malglate la sama nombro de elementoj, ĉiu kurante samtempe. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bobelo varo vs selektado ia vs merge varon. 1244 00:45:34,440 --> 00:45:36,760 >> Nun, ili ĉiuj kuras teorie samtempe. 1245 00:45:36,760 --> 00:45:39,830 La CPU kuras ĉe la sama rapido, sed vi 1246 00:45:39,830 --> 00:45:44,014 povas senti kiom enuiga ĉi estas tre rapide tuj fariĝis, 1247 00:45:44,014 --> 00:45:45,930 kaj kiom rapida kiam ni injekti iom de semajno 1248 00:45:45,930 --> 00:45:49,330 nulo la algoritmoj povas ni rapidi aferojn supre. 1249 00:45:49,330 --> 00:45:51,760 >> Kaj nun ni komparu tiuj en unu lasta formo. 1250 00:45:51,760 --> 00:45:55,710 Mi tuj iros antaŭen al CS50 la retejo, kie 1251 00:45:55,710 --> 00:45:59,020 ni havas tiun finan ligon por hodiaŭ, kie iu en la interreto 1252 00:45:59,020 --> 00:46:03,960 afable kunmetis video kiu kaptas kion malsamaj ordigado 1253 00:46:03,960 --> 00:46:07,510 algoritmoj soni kiel. 1254 00:46:07,510 --> 00:46:09,577 Jen inserción varon. 1255 00:46:09,577 --> 00:46:12,072 >> [BEEPING] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Whereby vi aplikante frekvenco bazita sur la alto de la stango trinkejo. 1258 00:46:16,850 --> 00:46:19,826 Tio estas bobelo varon. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped BEEPING] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Coming up sekva is-- venanta supren sekva is-- selektado speco, 1262 00:46:45,774 --> 00:46:48,820 kie denove, ni elektanta la sekva plej malgranda elemento, 1263 00:46:48,820 --> 00:46:51,820 kaj ni povas vidi ĝin kreskas de maldekstre al dekstre. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Kunfandi varon, nian gajninto ĝis nun hodiaŭ. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Rimarku kiel ĝi estas dividanta aferojn en [inaudible] duono kaj kvaronoj. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome speco, kiun ni havas ne raportis, kaj kreas vide 1270 00:47:21,660 --> 00:47:24,450 kaj audally iom de malsama formo kaj sono. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Irante tien kaj reen, purigante aĵojn. 1273 00:47:30,160 --> 00:47:32,230 Ankaŭ kontrolu heapsort sur ĉi ulo de afiŝinto. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Kaj tio estas ĝi. 1276 00:47:36,810 --> 00:47:38,210 Ni vidos vin proksima fojo. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [WHOOSHING KAJ MUZIKO] 1279 00:47:48,334 --> 00:50:24,839