1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> SPEAKER 1: Hej ĉiuj! 3 00:00:12,300 --> 00:00:13,890 Bonvenon al sekcio. 4 00:00:13,890 --> 00:00:17,480 Tiel ĝojis vidi tantos vin ambaux tie, kaj cxiu, kiu estas rigardi rete. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Do, kiel kutime bonvenon reen. 7 00:00:20,920 --> 00:00:24,360 Mi esperas ke vi ĉiuj havis belan semajnfino, plena de ripozo, malstreĉiĝo. 8 00:00:24,360 --> 00:00:26,026 Estis bela el hieraŭ. 9 00:00:26,026 --> 00:00:27,525 Do, mi esperas, ke vi ĝuis la libera aero. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Do unue kelkaj anoncoj. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Grading. 14 00:00:32,700 --> 00:00:37,350 Do, la plimulto de ili devus esti alveninta al retmesaĝi de mi pri via Scratch Pset, 15 00:00:37,350 --> 00:00:39,920 krom grading por Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Do, nur paro aĵoj. 18 00:00:42,220 --> 00:00:45,150 Nepre uzu check50 en style50. 19 00:00:45,150 --> 00:00:47,250 Tiuj estas signifita esti rimedojn por vi uloj, 20 00:00:47,250 --> 00:00:50,660 por certiĝi, ke vi fariĝas kiel multaj punktoj kiel vi povas 21 00:00:50,660 --> 00:00:52,390 sen senbezone perdi ilin. 22 00:00:52,390 --> 00:00:54,407 Do, aĵoj kiel stilo estas tre grava. 23 00:00:54,407 --> 00:00:55,740 Ni iras al despegar por ĝi. 24 00:00:55,740 --> 00:00:58,115 Iuj el vi eble jam rimarkis ke de via Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 Kaj check50 estas nur vere facila maniero por certigi 27 00:01:01,450 --> 00:01:05,050 ke ni vere revenis kio bezonas reveni al la uzanto, 28 00:01:05,050 --> 00:01:06,690 kaj ke ĉio funkcias konvene. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Sur la dua noto, certigu vian alŝuti aĵojn por la ĝentila dosierujo. 31 00:01:12,040 --> 00:01:14,470 Ĝi faras mian vivon nur Iomete pli malfacila 32 00:01:14,470 --> 00:01:18,836 se vi alŝutu Pset 2 en Pset 1 ĉar kiam mi elŝuti aferojn, 33 00:01:18,836 --> 00:01:20,085 ne elŝuti korekte. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 Kaj mi scias, ke tio iom wonky en sistemo kutimi, 36 00:01:24,560 --> 00:01:26,950 sed simple esti súper zorgu, se nur por mi, 37 00:01:26,950 --> 00:01:30,080 tiel ke kiam vi fariĝas retpoŝtojn ĉe kiel 2-a horo matene kaj mi grading. 38 00:01:30,080 --> 00:01:33,710 Se ne tio mi devas rigardi ĉirkaŭe por via Pset. 39 00:01:33,710 --> 00:01:34,440 Malvarmeta. 40 00:01:34,440 --> 00:01:37,270 >> Mi scias ke estas frue, sed mi tute got forlevata gvardio 41 00:01:37,270 --> 00:01:40,800 per eseon tio pro tiu vendredo, ke miaj profesoroj ĵus ŝatas, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Memoru, vi havas eseo pro vendrede. 43 00:01:42,550 --> 00:01:45,780 Do, mi konas neniun ŝatas pensi midterms, 44 00:01:45,780 --> 00:01:50,620 sed via unua kvizo estas sur Oktobro 15, kio oktobro komenciĝas ĉi-semajne. 45 00:01:50,620 --> 00:01:53,290 Do, eble estus pli frue ol vi atendis estas ĉio. 46 00:01:53,290 --> 00:01:57,510 Por ke vi ne ĵetitaj desprevenida kiam Mi mencias sekva semajno sekcio kiu ho, 47 00:01:57,510 --> 00:02:00,560 vian kvizon sekva semajno, mi pensis Mi ŝatus doni al vi iom pli 48 00:02:00,560 --> 00:02:01,500 de kapoj nun. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Do, via problemo aro, numero tri. 51 00:02:04,660 --> 00:02:07,070 Kiel homoj legis la Spec pro scivolemo? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 OK. 54 00:02:09,199 --> 00:02:10,229 Ni ricevis paron. 55 00:02:10,229 --> 00:02:12,320 Speco de sube de lasta semajne sed tio estas en ordo. 56 00:02:12,320 --> 00:02:13,650 Mi scias, ke estis bela ekstere. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Do Break Out. 59 00:02:16,660 --> 00:02:21,010 Definitive post vi get farita hodiaŭ legis vian specifon almenaŭ 60 00:02:21,010 --> 00:02:25,240 provu kiel elŝuti dissendo kodo kaj kurado 61 00:02:25,240 --> 00:02:27,430 kiel la unua komenca kion oni petas al vi. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Ĉar ni estas uzanta dissendo kodo kaj biblioteko 64 00:02:32,590 --> 00:02:36,790 ke ni nur using-- --It nur duafoje ni faris ĉi Pset, 65 00:02:36,790 --> 00:02:38,650 frenezaj aĵoj povas okazi kun via aparato, 66 00:02:38,650 --> 00:02:41,370 kaj vi volas trovi ke el nun kontre poste. 67 00:02:41,370 --> 00:02:45,570 >> Ĉar se estas ĵaŭdo nokte aŭ estas Merkredo nokte kaj ial 68 00:02:45,570 --> 00:02:48,912 via aparato simple ne volas funkcii kun la biblioteko 69 00:02:48,912 --> 00:02:50,620 aŭ kun la dissendo kodo, ke per 70 00:02:50,620 --> 00:02:52,309 Vi eĉ ne povas komenci fari la kodigon. 71 00:02:52,309 --> 00:02:54,100 Ĉar vi ne povas kontroli vidi se funkcias. 72 00:02:54,100 --> 00:02:55,975 Viaj ne gonna povos por vidi se ĝi kompilas. 73 00:02:55,975 --> 00:03:00,500 Vi volas prizorgi tiujn frue la semajno, kiam vi ankoraŭ povas retmesaĝi min 74 00:03:00,500 --> 00:03:03,100 aŭ unu el la aliaj TFS, kaj ni povas akiri tiujn fiksita. 75 00:03:03,100 --> 00:03:05,410 Ĉar tiuj estas demandoj ke tuj haltos vin 76 00:03:05,410 --> 00:03:07,120 el farante ajnan realan progreson. 77 00:03:07,120 --> 00:03:10,055 Ne estas kiel unu cimon, ke Vi povas simple speco de salti super. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Se vi havas demandojn per viaj aparato aŭ dissendo kodo, 80 00:03:13,420 --> 00:03:16,211 vi vere volas bonstata prenita Zorgi pri frue anstataŭ poste. 81 00:03:16,211 --> 00:03:20,410 Do eĉ se vi ne gonna reale komenci kodigo, elŝutu la distribuo 82 00:03:20,410 --> 00:03:24,040 kodo, legu la specifo, certigu ĉio laboras tie. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 Se vi povas simple fari tion, mi promesi viajn vivojn estos facila. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 Kaj tiel vi probable irante fari ĝin ĝuste nun justa? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 Do, demandojn tie? 89 00:03:33,950 --> 00:03:35,850 Ajna logistika aferojn? 90 00:03:35,850 --> 00:03:36,910 Ĉies bono? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer por tiuj de vi en la ĉambron kaj online. 93 00:03:41,700 --> 00:03:45,437 Mi tuj esti provante ŝanĝi inter PowerPoint en la aparato 94 00:03:45,437 --> 00:03:47,270 ĉar tuj esti farante iu kodigo 95 00:03:47,270 --> 00:03:53,630 hodiaŭ por populara peto de la anonima sugesto enketo mi sendis lastan semajnon. 96 00:03:53,630 --> 00:03:55,480 Do, ni faros kelkajn kodigo. 97 00:03:55,480 --> 00:03:57,800 Do, se vi uloj volas ankaŭ pafi viajn aparatojn, 98 00:03:57,800 --> 00:04:02,910 kaj vi ricevus email de mi kun specimeno dosiero. 99 00:04:02,910 --> 00:04:04,310 Bonvolu senti liberan fari tion. 100 00:04:04,310 --> 00:04:07,340 >> Do, ni tuj parolu pri GDB, kiu estas sencimigilon. 101 00:04:07,340 --> 00:04:09,970 Ĝi tuj helpi vin speco de elŝeligi kie 102 00:04:09,970 --> 00:04:11,860 aferoj iras malbone en via kodo. 103 00:04:11,860 --> 00:04:15,370 Estas vere nur vojo por vi tretas tra via kodo kiel okazas, 104 00:04:15,370 --> 00:04:19,100 kaj povos elprinti variabloj aŭ vidi kio reale okazis 105 00:04:19,100 --> 00:04:22,980 sub la kapuĉo versoj via programo nur kurante, estas kiel faulting, 106 00:04:22,980 --> 00:04:25,030 kaj vi estas kiel, neniu ideo kio ĵus okazis tie. 107 00:04:25,030 --> 00:04:26,730 Mi ne scias kion linio malsukcesinta ĉe. 108 00:04:26,730 --> 00:04:29,040 Mi ne scias, kie li estis malĝusta. 109 00:04:29,040 --> 00:04:31,280 Do, GDB tuj helpi vin kun tio. 110 00:04:31,280 --> 00:04:35,240 Ankaŭ, se vi decidas daŭrigi jes, kaj prenu 61, 111 00:04:35,240 --> 00:04:38,430 gxi vere, vere via bona amiko, ĉar mi povas diri al vi 112 00:04:38,430 --> 00:04:40,840 ĉar Mi iras tra tiu klaso. 113 00:04:40,840 --> 00:04:43,620 >> Ni tuj rigardi duuma Serĉu, kaj se vi uloj memori 114 00:04:43,620 --> 00:04:47,540 la granda telefono libro ekzemplo spektaklo de klaso. 115 00:04:47,540 --> 00:04:50,620 Ni devas apliki tion, kaj promenante tra tiu iom pli, 116 00:04:50,620 --> 00:04:54,650 kaj tiam ni iras tra kvar malsamaj varoj, kiuj estas Bubble, 117 00:04:54,650 --> 00:04:56,285 Selektado, Insertion kaj Merge. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Malvarmeta. 120 00:04:58,330 --> 00:05:00,390 Do, GDB kiel mi menciis, estas sencimigilon. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 Kaj tiuj estas speco de la granda aĵoj, la grandaj funkcioj aŭ komandoj 123 00:05:09,370 --> 00:05:13,240 ke vi uzas ene GDB, kaj Mi iros vi tra demo ĝin en dua. 124 00:05:13,240 --> 00:05:15,360 >> Do, ĉi tiu estas ne nur restos abstrakta. 125 00:05:15,360 --> 00:05:18,000 Mi provos kaj faros gxin kiel betono kiel ebla por vi uloj. 126 00:05:18,000 --> 00:05:19,870 Do, rompi. 127 00:05:19,870 --> 00:05:22,200 Ĝi devos ĉu esti rompo kiel, iu nombro, kiu 128 00:05:22,200 --> 00:05:26,900 reprezentas linio en via programo, aux vi povas nomumi funkcio. 129 00:05:26,900 --> 00:05:30,150 Do, se vi diras rompi ĉefa, ĝi haltos ĉe ĉefa, 130 00:05:30,150 --> 00:05:32,400 kaj lasos vin iri tra tiu funkcio. 131 00:05:32,400 --> 00:05:36,350 >> Simile, se vi havas iuj eksteraj funkcii kiel Swap aŭ Cube, 132 00:05:36,350 --> 00:05:38,450 ke ni rigardis pasintan semajnon. 133 00:05:38,450 --> 00:05:41,780 Se vi diras malobservos unu el tiuj, kiam via programo batas ke, 134 00:05:41,780 --> 00:05:44,290 ĝi atendos vin sciigi, kion fari. 135 00:05:44,290 --> 00:05:47,860 Antaŭ tio nur ekzekuti tiel vi povus reale enpaŝi la funkcio 136 00:05:47,860 --> 00:05:49,020 kaj vidu kio okazas. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Do, tuj, simple saltas super la sekva linio, iras super funkcioj. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Paŝo. 141 00:05:55,560 --> 00:05:56,810 Tiuj estas ĉiuj iom abstrakta. 142 00:05:56,810 --> 00:06:00,530 Do, mi simple tuj kuras tra ili, sed vi vidos ilin en uzo en dua. 143 00:06:00,530 --> 00:06:01,810 >> Paŝi al funkcio. 144 00:06:01,810 --> 00:06:04,170 Tiel kiel mi diris, kiel kun Swap, estus 145 00:06:04,170 --> 00:06:07,110 permesas al efektive kvazaŭ vi estas kiel fizike tretante enen, 146 00:06:07,110 --> 00:06:10,990 vi povas salaton kun tiuj variabloj, print kio estas, vidos kio okazas. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Listo estos laŭvorte nur presi el la ĉirkaŭa kodo. 149 00:06:14,830 --> 00:06:17,570 Do, se vi ia forgesi kie vi estas en via programo, 150 00:06:17,570 --> 00:06:19,880 aŭ vi demandante kio okazas ĉirkaŭ li, 151 00:06:19,880 --> 00:06:23,790 tio ĝuste presi segmento de kiel kvin aŭ ses linioj ĉirkaŭ ĝi. 152 00:06:23,790 --> 00:06:26,080 Do, vi povas get orientis pri kie vi estas. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Presi kelkaj variabloj. 155 00:06:28,650 --> 00:06:34,590 Do, se vi havas la ŝlosilon ŝatas en Cezaro, ke ni rigardu. 156 00:06:34,590 --> 00:06:36,220 Vi povas diri Presi Ŝlosilo en ajna punkto. 157 00:06:36,220 --> 00:06:40,070 Ĝi diros al vi, kion la valoro estas tiel ke, eble ie survoje, 158 00:06:40,070 --> 00:06:42,070 vi overwrote via ŝlosilo. 159 00:06:42,070 --> 00:06:45,495 Vi povas fakte diri ke ĉar Vi povas fakte observi tiun valoron. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> En la lokanoj, nur impresoj el via loka variabloj. 162 00:06:48,780 --> 00:06:53,120 Do, anytime vi ene banto, kaj vi simple volas vidi kiel, oh. 163 00:06:53,120 --> 00:06:54,270 Kio estas mia mi? 164 00:06:54,270 --> 00:06:57,020 Kio estas ĉi tiu ŝlosilo valoro ke mi pravalorizi ĉi tie? 165 00:06:57,020 --> 00:06:58,537 Kio estas la mesaĝo ĉe tiu punkto? 166 00:06:58,537 --> 00:07:00,370 Ĝi simple presi ĉiuj de tiuj, por ke vi 167 00:07:00,370 --> 00:07:04,330 ne devas individue diru Presi I. Presi Mesaĝo. 168 00:07:04,330 --> 00:07:04,970 Print Ŝlosilo. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 Kaj tiam Montriĝo. 171 00:07:07,700 --> 00:07:10,370 Kion faras estas kiel vi paŝo tra la programo, 172 00:07:10,370 --> 00:07:13,980 ĝi devos simple certigi ke ĝi estas montrante iuj certaj variablo 173 00:07:13,980 --> 00:07:14,780 je ĉiu punkto. 174 00:07:14,780 --> 00:07:17,160 Por ke vi also-- --it estas speco de ŝparvojo kie 175 00:07:17,160 --> 00:07:19,530 vi ne devas teni irante kiel, oh. 176 00:07:19,530 --> 00:07:23,150 Print Ŝlosilo aŭ Presi I. Ĝi simple aŭtomate fari ĝin por vi. 177 00:07:23,150 --> 00:07:25,959 >> Do, kun tio, ni iras Vidi kiel ĉi iras. 178 00:07:25,959 --> 00:07:28,000 Mi tuj provos kaj ŝaltilo super mian aparaton. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Vidu se mi povas fari ĉi tion. 181 00:07:31,271 --> 00:07:31,770 Ĉiuj. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Ni nur tuj speguli ĝin. 184 00:07:42,370 --> 00:07:44,530 Nenio freneza sur mia tekkomputilo anyways. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 OK. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Ĉi devas esti ĉi tiu. 189 00:08:01,054 --> 00:08:01,795 Estas tiom eta. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Vidu se ni povas fari ĉi tion. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> OK. 194 00:08:10,940 --> 00:08:15,305 Alice estas evidente baraktante tie nur iomete, 195 00:08:15,305 --> 00:08:17,995 sed ni akiros ĝin en momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 OK. 198 00:08:22,020 --> 00:08:25,900 Ni nur tuj pliigos ĉi. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 OK. 201 00:08:29,380 --> 00:08:31,679 Povas ĉiuj speco de vidi ke? 202 00:08:31,679 --> 00:08:32,470 Eble iomete? 203 00:08:32,470 --> 00:08:33,594 Mi scias ke estas iom malgranda. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Vi ne povas tute elkompreni kiel fari tiu granda. 206 00:08:37,530 --> 00:08:38,350 Se iu scias. 207 00:08:38,350 --> 00:08:40,309 Ĉu iu scias kiel fari ĝin pli granda? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 Ni tuj ruliĝi kun ĝi. 210 00:08:42,140 --> 00:08:45,801 Ne gravas anyways ĉar estas nur tio estas la kodo kiu vi uloj devus 211 00:08:45,801 --> 00:08:46,300 havas. 212 00:08:46,300 --> 00:08:48,310 >> Kio estas pli grava estas la fina tie. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 Kaj ni havas tie Kial estas tiel malgranda? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Agordojn. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Vera Ike. 220 00:09:09,500 --> 00:09:10,880 Kiel estas tio? 221 00:09:10,880 --> 00:09:11,770 El tie. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Estas kiu pli bona por ĉiuj? 224 00:09:21,810 --> 00:09:22,525 OK ,. 225 00:09:22,525 --> 00:09:23,025 Malvarmeta. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Vi scias, kiam vi estas en CS klaso teknikajn malfacilaĵojn 228 00:09:28,220 --> 00:09:32,971 estas ia parto de the-- Do, ni purigi ĉi. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 Do, ĉi tie en sekcio, kiun ni havis ĉi tie. 231 00:09:38,060 --> 00:09:40,830 Cezaro estas plenumebla dosiero. 232 00:09:40,830 --> 00:09:41,800 Do mi faris ĝin. 233 00:09:41,800 --> 00:09:46,370 Do unu afero realigi kun GDB estas ke nur funkcias sur plenumeblajn dosierojn. 234 00:09:46,370 --> 00:09:48,040 Do, vi ne povas kuri ĝin sur dotsy. 235 00:09:48,040 --> 00:09:50,532 Vi devas efektive fari certa ke via kodo kompilas, 236 00:09:50,532 --> 00:09:51,865 kaj kiu povas fakte esti lanĉita. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Do, certigi ke se ĝi ne kompili, prenu gxin por kompili, 239 00:09:56,186 --> 00:09:57,810 por ke vi povu ia trafluas ĝin. 240 00:09:57,810 --> 00:10:04,590 Do, por komenci GDB, ĉiuj vi devas fari; Gloria tipo GDB, kaj subite la 241 00:10:04,590 --> 00:10:06,250 dosiero, kiun vi volas. 242 00:10:06,250 --> 00:10:08,240 Mi ĉiam misspell Cezaro. 243 00:10:08,240 --> 00:10:11,730 Sed vi volas certigi ĉar ĝi estas plenumebla, 244 00:10:11,730 --> 00:10:14,210 ti la skalara flash por ke signifas ke vi iras 245 00:10:14,210 --> 00:10:19,240 kuri CSI vi tuj ekzekuti ĉi fajlilo ĉu kun la erarserĉilo. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 Do, vi faros tion, vi ricevos tiu speco de stultaĵoj. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Estas nur ĉio pri sencimigilon. 250 00:10:25,750 --> 00:10:28,200 Vi ne vere devas maltrankviligi ŝin nun. 251 00:10:28,200 --> 00:10:31,460 Kaj kiel vi vidas, ni havas ĉi malfermita parens, GDP, proksime parens, 252 00:10:31,460 --> 00:10:34,690 kaj ĝuste speco de aspektas nia komandlinio, dekstra? 253 00:10:34,690 --> 00:10:37,010 >> Do, kion ni volas do-- --So, La unua afero 254 00:10:37,010 --> 00:10:39,570 Estas ni volas elekti loko por rompi ĝin. 255 00:10:39,570 --> 00:10:42,332 Do, ekzistas unu cimon en ĉi Caesar programo 256 00:10:42,332 --> 00:10:44,290 ke mi prezenti, ke ni iras al elŝeligi. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Ĝi Kio ĝi estas prenas la enigo Barfoo en ĉiuj kaskedoj kaj ial 259 00:10:56,350 --> 00:11:01,950 ĝi ne ŝanĝas A. Ĝi nur lasas ĝin sole, Ĉu ĉio ĝustas, 260 00:11:01,950 --> 00:11:03,980 sed la dua letero A restas neŝanĝita. 261 00:11:03,980 --> 00:11:07,120 Do, ni tuj provi elŝeligi kial tio estas. 262 00:11:07,120 --> 00:11:10,440 Do, la unua afero vi tipe volas fari kiam vi komencas en GDB 263 00:11:10,440 --> 00:11:12,010 estas elkompreni kie rompi ĝin. 264 00:11:12,010 --> 00:11:14,956 >> Do Cezaro estas sufiĉe mallonga programo. 265 00:11:14,956 --> 00:11:16,330 Ni nur havas unu funkcion, dekstra? 266 00:11:16,330 --> 00:11:18,520 Kio estis nia funkcio en Cezaro? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Ekzistas nur unu funkcion, Ĉefa dekstra? 269 00:11:24,350 --> 00:11:26,490 Ĉefa estas funkcio por ĉiuj viaj programoj. 270 00:11:26,490 --> 00:11:29,230 Se vi ne havas Main, mi povus iom maltrankviliĝis nun, 271 00:11:29,230 --> 00:11:31,000 sed mi esperas, ke vi ĉiuj havis Ĉefa tien. 272 00:11:31,000 --> 00:11:34,150 Do, kion ni povas fari estas ni povas nur rompi Main, ĝuste tiel. 273 00:11:34,150 --> 00:11:35,190 Do, ĝi diras, OK. 274 00:11:35,190 --> 00:11:37,430 Ni metis niajn Haltpunkto unu tie. 275 00:11:37,430 --> 00:11:42,870 >> Do, nun la afero memori estas Cezaro prenas unu komandlinio argumento dekstra 276 00:11:42,870 --> 00:11:45,150 kaj ni ne faris tion, ie ankoraŭ. 277 00:11:45,150 --> 00:11:47,560 Do, kion vi faras kiam Vi vere iru kuri 278 00:11:47,560 --> 00:11:51,540 La programo, ajna programo kiu vi estas kurante en GDB kiu bezonas komandlinio 279 00:11:51,540 --> 00:11:55,010 argumentojn, vi tuj enigo kiam vi unue komencos kuri ĝin. 280 00:11:55,010 --> 00:11:59,280 Do, en ĉi tiu kazo, ni faru Kuri kun ŝlosilo de tri. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 Kaj ĝi efektive komenci. 283 00:12:02,040 --> 00:12:08,480 >> Do, se vi vidas tie, ni havas Se RC estas ne egala al 2. 284 00:12:08,480 --> 00:12:12,210 Do se vi uloj ĉiuj havas ke dosiero ke mi sendis supren 285 00:12:12,210 --> 00:12:15,100 vi vidos, ke tio estas kvazaŭ la unua linio nia ĉefa funkcio, dekstra? 286 00:12:15,100 --> 00:12:17,890 Ĝi estas kontrolanta vidi se ni havas la ĝusta nombro de argumentoj. 287 00:12:17,890 --> 00:12:20,620 Do, se vi scivolas se RC estas ĝentila, 288 00:12:20,620 --> 00:12:23,250 vi povas fari ion ĝuste kiel Presi RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC estas du, kio estas kion ni atendis, ĉu ne? 291 00:12:28,640 --> 00:12:32,010 >> Do, ni povas iri Venonta, kaj daŭrigas tra. 292 00:12:32,010 --> 00:12:33,200 Do, ni havas iun klavon tie. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 Kaj ni povas presi niajn ŝlosilo por certiĝi ke estas korekta. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interesa. 297 00:12:39,500 --> 00:12:41,210 Ne tute kion ni atendis. 298 00:12:41,210 --> 00:12:44,810 Do unu afero realigi kun GDB ankaŭ, estas 299 00:12:44,810 --> 00:12:49,000 ke ne ĝis vi efektive trafis Next, la linio kiun vi ĵus vidis 300 00:12:49,000 --> 00:12:50,720 fakte ekzekutita. 301 00:12:50,720 --> 00:12:53,870 Do, en ĉi tiu kazo Ŝlosilo ne estis atribuita ankoraŭ. 302 00:12:53,870 --> 00:12:57,050 Do, Cayo estas iuj rubo valoro ke vi vidas sur la fundo. 303 00:12:57,050 --> 00:13:03,680 Negativa $ 120-- --It la unu miliardo kaj iom strange aferojn dekstra? 304 00:13:03,680 --> 00:13:05,340 Ĝi ne estas la ŝlosilo kiun ni atendis. 305 00:13:05,340 --> 00:13:10,720 Sed se ni batis Venonta, kaj poste ni provu Presi ŝlosilon, estas tri. 306 00:13:10,720 --> 00:13:11,710 >> Ĉiuj vidis? 307 00:13:11,710 --> 00:13:13,780 Do, se vi prenos ion ke vi ŝatas, atendu. 308 00:13:13,780 --> 00:13:15,540 Tio estas tute malĝusta, kaj mi ne scias 309 00:13:15,540 --> 00:13:20,150 kiel tio okazus ĉar mi volas fari estas atribui numeron, variablo, 310 00:13:20,150 --> 00:13:22,900 provu bati Next, provu printado denove, kaj vidi se tiu funkcias. 311 00:13:22,900 --> 00:13:27,830 Ĉar ĝi estas nur tuj ekzekuti kaj efektive asigni ion post vi 312 00:13:27,830 --> 00:13:29,340 batita Next. 313 00:13:29,340 --> 00:13:30,336 Sencon por ĉiuj? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: Kiam vi hazarda nombroj kion tio signifas? 316 00:13:33,220 --> 00:13:34,790 >> SPEAKER 1: Estas nur hazardo. 317 00:13:34,790 --> 00:13:35,710 Estas nur rubon. 318 00:13:35,710 --> 00:13:38,320 Estas nur ion ke via komputilo hazarde atribui. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Malvarmeta. 321 00:13:40,220 --> 00:13:45,760 Do, nun ni povas movi tra, ktp Nun ni havas ĉi tekstaj GetString. 322 00:13:45,760 --> 00:13:48,600 Do, lasu min simple enkonduki kio okazos kiam ni batis Sekva tie. 323 00:13:48,600 --> 00:13:51,320 Niaj GDB ia malaperas, ĉu ne? 324 00:13:51,320 --> 00:13:55,720 Tio estas ĉar GetString nun ekzekutas, dekstra? 325 00:13:55,720 --> 00:14:01,460 Do, kiam ni vidis tekstaj egalas GetString, malferma parens kaj parens, 326 00:14:01,460 --> 00:14:04,380 kaj ni batis Next, kiu havas fakte ekzekutita nun. 327 00:14:04,380 --> 00:14:06,580 Do, ĝi estas atendante Ni enigi ion. 328 00:14:06,580 --> 00:14:13,560 >> Do, ni tuj input nia manĝaĵo kiu estas kio ĝi estas maltrafi kiel mi diris al vi, 329 00:14:13,560 --> 00:14:18,020 kaj ke nur diras ke ĝi estas finita ekzekuti, ke la fermita 330 00:14:18,020 --> 00:14:19,980 krampo signifas estas forlaso el tiu buklo. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Do, ni povas bati Venonta, kaj nun, dum mi estas certe vi ja ĉiuj konas de Cezaro, 333 00:14:25,420 --> 00:14:27,260 tio estas, kio estas ĉi tiu linio tuj faros. 334 00:14:27,260 --> 00:14:32,030 Estas por Mez mi egalas 0, N egalas Strlen, plata teksto, kaj tiam 335 00:14:32,030 --> 00:14:33,960 Mi estas malpli ol n, mi, pli, pli. 336 00:14:33,960 --> 00:14:35,210 Kio estas ĉi tiu buklo faros? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Malfermu vian mesaĝon. 339 00:14:39,160 --> 00:14:39,770 Malvarmeta. 340 00:14:39,770 --> 00:14:41,330 Do, ni komencu fari tion. 341 00:14:41,330 --> 00:14:47,210 >> Do, ĉu ĉi tiu kondiĉo parigi, por nia unua? 342 00:14:47,210 --> 00:14:52,250 Se ĝi estas B, estas tekstaj I. Ni povas akiri informojn pri niaj lokaj. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Do, mi estas nulo, kaj se ses, kiuj ni atendas, kaj nia ŝlosilo estas tri. 345 00:14:57,970 --> 00:14:59,227 Ĉio tio havas sencon, ĉu ne? 346 00:14:59,227 --> 00:15:01,310 Tiuj nombroj estas ĉiuj ĝuste kio ili devus esti. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Do, zumas? 349 00:15:03,870 --> 00:15:05,620 SPEAKER 3: Mi havas hazardaj nombroj por mia. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: Nu, ni povas check-- --we povas babili pri tio en dua. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Sed vi devus akiri ĉi. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Do, se ni havas majusklan B por nia unua, 356 00:15:20,130 --> 00:15:22,080 tiu kondiĉo devas kapti ĝin, ĉu ne? 357 00:15:22,080 --> 00:15:27,120 Do, se ni batis Tuj, ni vidu ke tio Se efektive ekzekutas. 358 00:15:27,120 --> 00:15:29,220 Ĉar se vi jenajn kune en via kodo, 359 00:15:29,220 --> 00:15:33,460 tiu linio tie, kie tekstaj mi estas anstataŭita per tiu aritmetiko, 360 00:15:33,460 --> 00:15:35,720 nur ekzekutas se Se kondiĉo estas korekta dekstra? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB nur tuj montros al vi kio estas reale ekzekuti. 363 00:15:40,240 --> 00:15:45,140 Do se tio Se kondiĉo ne renkontis, estas nur tuj saltas al la sekva linio. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 Do, ni havas tiun. 366 00:15:48,510 --> 00:15:51,171 Ĉi krampo signifas estas fermita el tiu buklo nun. 367 00:15:51,171 --> 00:15:52,420 Do, ĝi tuj komencas denove. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Ĝuste tiel. 370 00:15:56,280 --> 00:15:59,120 Tiel, ke ni povas akiri info pri niaj lokaj tie, 371 00:15:59,120 --> 00:16:02,575 kaj ni vidos, ke nia unua letero ŝanĝiĝis, ĉu ne? 372 00:16:02,575 --> 00:16:05,150 Estas nun E, kiel devus esti. 373 00:16:05,150 --> 00:16:07,360 Do, ni povas daŭrigi plu. 374 00:16:07,360 --> 00:16:08,500 >> Kaj ni havas ĉi ĉeko. 375 00:16:08,500 --> 00:16:09,916 Kaj tiu ĉeko devas labori, ĉu ne? 376 00:16:09,916 --> 00:16:12,570 Estas A. Ĝi devus esti ŝanĝita tri leteroj antaŭen. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Sed se vi rimarkas, ni akiri iun malsama. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Do en tiu kazo ĝis tie, li kaptis ĝin, kaj tial tiu linio ekzekutitaj, 381 00:16:22,860 --> 00:16:28,620 kio modifita nia B. Sed, en tiu kazo tie, 382 00:16:28,620 --> 00:16:32,860 ni havas ke nur saltis ĝi, kaj iris al la [? L Siff. ?] 383 00:16:32,860 --> 00:16:34,660 Do io okazas tie. 384 00:16:34,660 --> 00:16:37,780 Kio tio estas diranta al vi estas tiu, Ni scias ke ĝi devus kapti tie, 385 00:16:37,780 --> 00:16:39,200 sed estas ne. 386 00:16:39,200 --> 00:16:42,210 Ĉu iu povas vidi kion niaj problemo estas en tiu linio? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Ĝi estas tre minuto afero. 389 00:16:46,969 --> 00:16:48,510 Kaj vi povas ankaŭ rigardi vian kodon. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Ĝi estas ankaŭ line-- forgesu kion linio estas en there-- sed estas en la [inaudible]. 392 00:16:54,940 --> 00:16:55,480 Jes? 393 00:16:55,480 --> 00:16:58,639 >> SPEAKER 4: Ĝi estas sur la pli granda ol paĝo se vi legas ĝin en la libro. 394 00:16:58,639 --> 00:16:59,430 SPEAKER 1: Ekzakte. 395 00:16:59,430 --> 00:17:02,620 Do, la erarserĉilo ne povus diri vi tion, sed la erarserĉilo 396 00:17:02,620 --> 00:17:05,880 povis akiri vin malsupren al linio ke vi konas ne funkciis. 397 00:17:05,880 --> 00:17:09,319 Kaj kelkfoje, kiam precipe poste en la semestro, kiam 398 00:17:09,319 --> 00:17:12,910 vi kontraktanta kun cento, al cent malmultaj linioj de kodo, kaj vi 399 00:17:12,910 --> 00:17:16,190 ne scias, kie ĝi estas maltrafante, ĉi estas granda vojo por fari ĝin. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Do, ni trovis nian cimon. 402 00:17:18,989 --> 00:17:21,530 Vi povas fiksi ĝin en vian dosieron, kaj tiam vi povus ruli ĝin denove, 403 00:17:21,530 --> 00:17:23,029 kaj ĉio funkcius perfekte. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 Kaj la plej granda aĵo tio povas ŝajni, OK. 406 00:17:30,590 --> 00:17:31,090 Yeah. 407 00:17:31,090 --> 00:17:31,370 Malvarmeta. 408 00:17:31,370 --> 00:17:32,744 Vi sciis, kion vi serĉas. 409 00:17:32,744 --> 00:17:34,910 Do, vi sciis, kion fari. 410 00:17:34,910 --> 00:17:39,021 >> GDB povas esti súper utila ĉar vi povas presi cxiujn tiujn farojn, kiujn vi 411 00:17:39,021 --> 00:17:39,520 ne volis. 412 00:17:39,520 --> 00:17:41,160 Ĝi estas multe pli utila ol printf. 413 00:17:41,160 --> 00:17:43,440 Kiel multaj el vi uzas kiel printf deklaroj 414 00:17:43,440 --> 00:17:46,200 elkompreni kie cimo estis, ĉu ne? 415 00:17:46,200 --> 00:17:48,450 Do, kun ĉi tio, vi ne devi teni reiri, 416 00:17:48,450 --> 00:17:51,139 kaj kiel dirante en Printf, aŭ komentoj ekstere, 417 00:17:51,139 --> 00:17:52,930 kaj elkompreni Vi devas presi. 418 00:17:52,930 --> 00:17:55,670 Tiu fakte nur permesas paŝo tra, presi tion 419 00:17:55,670 --> 00:18:00,000 kiel vi estas iranta tra, tiel, vi povas observi kiel ili ŝanĝas en reala tempo 420 00:18:00,000 --> 00:18:02,190 kiel via programo kuras. 421 00:18:02,190 --> 00:18:04,390 >> Kaj ne prenu iom iom de kutimante. 422 00:18:04,390 --> 00:18:07,850 Mi forte rekomendas ĝuste speco esti iom frustrita kun ĝi 423 00:18:07,850 --> 00:18:08,930 por nun. 424 00:18:08,930 --> 00:18:13,450 Se vi pasigas horon super la sekva semajno lerni kiel uzi GDB, 425 00:18:13,450 --> 00:18:16,140 vi savos vin mem tiom da tempo poste. 426 00:18:16,140 --> 00:18:18,750 Kaj laŭvorte. ni diru tio al personoj ĉiu jaro, 427 00:18:18,750 --> 00:18:23,890 Mi memoras kiam mi prenis la klaso, mi estis kiel, mi estos bone. 428 00:18:23,890 --> 00:18:24,700 No. 429 00:18:24,700 --> 00:18:27,030 Pset 6 eliris kaj mi kiel, mi gonna lerni 430 00:18:27,030 --> 00:18:29,500 kiel uzi GDB ĉar mi ne scias kio okazas tie. 431 00:18:29,500 --> 00:18:32,940 >> Do se vi preni la tempon por uzi gxin en malgrandaj programoj 432 00:18:32,940 --> 00:18:35,697 ke vi tuj estos funkcias plu, kiel labori 433 00:18:35,697 --> 00:18:37,530 tra iu kiel Visionare, kiel tiu. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Aŭ se vi volas ekstrajn praktiko, mi certas Mi povis veni supren kun kalesxo programoj, 436 00:18:42,850 --> 00:18:45,300 Vi devas elpurigi se vi ŝatus. 437 00:18:45,300 --> 00:18:49,300 >> Sed se vi nur bezonos iom da tempo por akiri kutimiĝis, bonvolu ludi kun ĝi, 438 00:18:49,300 --> 00:18:50,550 ĝi vere servos al vi bone. 439 00:18:50,550 --> 00:18:52,591 Kaj estas vere unu el tiuj aferoj kiujn vi ĵus 440 00:18:52,591 --> 00:18:57,340 devas provi kaj instigi viajn manojn malpurajn kun, antaŭ vi vere komprenis. 441 00:18:57,340 --> 00:19:02,090 Mi vere nur komprenis ĝin unufoje Mi devis elpurigi aferojn kun ĝi, 442 00:19:02,090 --> 00:19:08,170 kaj tio estas multe pli agrable havi ideon de kiom elpurigi frue anstataŭ poste. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 Malvarmeta. 445 00:19:09,625 --> 00:19:12,960 Mi scias ke estas speco de kiel urĝa kurso en GDB, 446 00:19:12,960 --> 00:19:16,400 Mi certe laboros pri atingi tiuj rigardi granda venontfoje. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Malvarmeta. 449 00:19:18,280 --> 00:19:20,390 >> Do, se ni reiru al nia PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Estas ĉi irante labori? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 Awh. 454 00:19:30,210 --> 00:19:31,101 Jes. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 Do, se vi bezonos iun el tiujn denove, tie estas la listo. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Do Binary Search, kiun chiuj memoras la grandan spektaklon de Davido 459 00:19:40,830 --> 00:19:42,259 ŝiri telefono libroj en duono. 460 00:19:42,259 --> 00:19:44,050 Mi ne vere akiri la telefono librojn plu, 461 00:19:44,050 --> 00:19:46,530 ĉar kiel kie vi akiri telefonon libroj tiujn tagojn? 462 00:19:46,530 --> 00:19:48,220 Mi vere ne scias. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 La Binary Search. 465 00:19:50,590 --> 00:19:52,464 Ĉu iu memoras kiom Binary Serĉo verkoj? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Iu ajn? 468 00:19:55,220 --> 00:19:56,325 Yeah? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Vi scias, kiam Vi rigardu, kiu duone 470 00:19:58,283 --> 00:20:01,146 estus en, Bazita sur tio, kaj liveri de la alia duono. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Ĝuste. 472 00:20:01,896 --> 00:20:06,290 Do, Duuma Search, estas speco de a-- --we ŝatas nomi ŝin dividi kaj venki. 473 00:20:06,290 --> 00:20:09,170 Do, kion vi devos fari estas vi rigardu en la mezo, 474 00:20:09,170 --> 00:20:11,990 kaj vi vidos se ĝi egalas kion vi serĉas. 475 00:20:11,990 --> 00:20:15,420 Kaj se ne, tiam oni provas elkompreni, estas tio tuj estos lasita 476 00:20:15,420 --> 00:20:16,450 duono aŭ la dekstra duono. 477 00:20:16,450 --> 00:20:19,325 Do, tiu povus esti se vi serĉas en iu kiu estas alfabetizado, 478 00:20:19,325 --> 00:20:20,720 vi vidas, ho. 479 00:20:20,720 --> 00:20:22,750 Ĉu Allison venu antaux M? 480 00:20:22,750 --> 00:20:23,250 Jes. 481 00:20:23,250 --> 00:20:25,030 Do, ni tuj rigardi la unuan duonon. 482 00:20:25,030 --> 00:20:26,450 >> Aŭ ĝi povus esti kiel kun nombroj. 483 00:20:26,450 --> 00:20:28,830 Anything ke vi povas kompari, ĝi povas esti ordo. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Vi povas uzi duuma serĉo plu. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Do, iu memoras ĉi grafeo aŭ kia estas? 488 00:20:37,455 --> 00:20:39,520 Estas Asimptota Komplekseco. 489 00:20:39,520 --> 00:20:42,830 Do, ĉi grafikaĵo nur priskribas kiom longe 490 00:20:42,830 --> 00:20:46,230 prenas vin solvi problemon kiel Vi pliigas la nombron de aferoj 491 00:20:46,230 --> 00:20:47,090 ke vi uzas. 492 00:20:47,090 --> 00:20:51,260 >> Do, ni havas n, kiu estas lineara tempo. 493 00:20:51,260 --> 00:20:54,560 Se N super du, kio estas iomete bona, ankoraŭ kreskas super rapida. 494 00:20:54,560 --> 00:20:58,360 Kaj tiam ni Ensaluta, kio estas kion ni konsideras Binary Search. 495 00:20:58,360 --> 00:21:03,630 Se ni rimarkos, kiel via problemo ricevas multe kaj multe pli granda, 496 00:21:03,630 --> 00:21:06,600 la tempa ĝi prenas vin solvi ĝin vere ne pliigos ke multe. 497 00:21:06,600 --> 00:21:09,010 Estas kiel kompareblaj tie en la komenco. 498 00:21:09,010 --> 00:21:10,060 Vi ŝatas, OK. 499 00:21:10,060 --> 00:21:13,000 Nenio ĉi tie ne vere gravas kiun el ni uzas, 500 00:21:13,000 --> 00:21:16,220 sed vi eliru por miliono, miliardo. 501 00:21:16,220 --> 00:21:20,010 Vi provas trovi some-- --you're provante trovi nadlo en garbejo. 502 00:21:20,010 --> 00:21:21,550 >> Mi pensas ke vi volas ĉi tiun problemon. 503 00:21:21,550 --> 00:21:25,850 Vi volas kompleksecon, ne lineal ĉar por ĉiu vi 504 00:21:25,850 --> 00:21:30,049 koni vian gonna esti trasercxante ĉiu individua nadlo, aĵo de fojno, 505 00:21:30,049 --> 00:21:31,340 provante serĉi vian nadlo. 506 00:21:31,340 --> 00:21:34,730 Kaj tio ne estas tro amuza miaopinie. 507 00:21:34,730 --> 00:21:35,500 Mi ŝatas rapida. 508 00:21:35,500 --> 00:21:36,620 Mi ŝatas eficiente. 509 00:21:36,620 --> 00:21:40,450 Kaj kiel laboristo studentoj vi infanoj estas, vi scias labori inteligenta, 510 00:21:40,450 --> 00:21:43,010 Ne malfacila tipo afero, kiel vi povas fari tiujn algoritmojn. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Do, ni iras promeni tra nur rapidan ekzemplon. 513 00:21:47,910 --> 00:21:51,090 Mi kredas ke vi infanoj devus havi mano sur Binary Search, 514 00:21:51,090 --> 00:21:54,352 sed se iu estas iom lanuga, volas plifortigi ĝin, 515 00:21:54,352 --> 00:21:56,310 Ni tuj ĝuste iri tra ekzemplo tie. 516 00:21:56,310 --> 00:21:59,490 Do, ni serĉas se La tabelo enhavas sep. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Do, unue ni faras estas rigardi en la mezo, dekstra? 519 00:22:06,010 --> 00:22:09,340 Kaj ankaŭ vi tuj estos kodigo Duuma Serĉo en nur dua. 520 00:22:09,340 --> 00:22:11,310 Do, ĝi tuj estos amuza. 521 00:22:11,310 --> 00:22:13,710 Do ni atendu la mezo iom arrays 3. 522 00:22:13,710 --> 00:22:15,501 Ĉu 3 egalas 7? 523 00:22:15,501 --> 00:22:16,000 Ne. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Estas ses. 526 00:22:19,550 --> 00:22:21,480 Do, ĝi estas malpli ol aŭ pli granda ol sep? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Malpli ol. 529 00:22:23,960 --> 00:22:24,570 Jes. 530 00:22:24,570 --> 00:22:25,170 Nice laboron infanoj. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Mi sentas min ŝatas mi devus havi bombono, ĉar mi 533 00:22:27,360 --> 00:22:29,460 voli ĵeti ĝin en la kortoj. 534 00:22:29,460 --> 00:22:30,270 Ĝi estas kion mi tuj faros la proksiman semajnon. 535 00:22:30,270 --> 00:22:31,436 Ĝi vin gardos infanoj akra. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Do, ni forĵetu ke unua duono, dekstra? 538 00:22:34,690 --> 00:22:35,670 estis malpli ol. 539 00:22:35,670 --> 00:22:39,325 Ni scias ke ĉiu sur tiu maldekstra flanko 540 00:22:39,325 --> 00:22:41,700 tuj estos malpli ol kion ni fakte serĉas. 541 00:22:41,700 --> 00:22:43,491 Do, estas nenia bezono atentu lin. 542 00:22:43,491 --> 00:22:45,120 Simple forgesi pri tio. 543 00:22:45,120 --> 00:22:48,720 Do, nun ni rigardos niajn dekstra flanko, kaj ni rigardu la mezo tien, 544 00:22:48,720 --> 00:22:50,510 kaj nun estas naŭ. 545 00:22:50,510 --> 00:22:55,510 Do, 9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Pli granda ol kio ni estas serĉante, ĉu ne? 547 00:22:57,470 --> 00:22:59,860 Do, ni tuj ĵeti for ĉiun dekstre. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Tiel. 550 00:23:01,940 --> 00:23:03,700 Nun, ĉiuj ni marŝis kun unu. 551 00:23:03,700 --> 00:23:07,760 Do ni kontrolu, estas ĉi tiu kio Ni serĉas? estas. 552 00:23:07,760 --> 00:23:08,970 Ni trovis kion ni deziris. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Do ni faris. 555 00:23:11,690 --> 00:23:12,550 Dulineara Search. 556 00:23:12,550 --> 00:23:15,740 >> Se vi rimarkas, ni havis sep enigoj tie. 557 00:23:15,740 --> 00:23:24,320 Ĝi nur prenis nin kiel tri fojojn, sed se vi faras kiel biliono, 558 00:23:24,320 --> 00:23:28,190 vi uloj scias kiom da paŝoj li volus preni se ni havis kvar miliardoj aferojn? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Ajna divenas? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Ĝi estas 32. 563 00:23:33,960 --> 00:23:37,110 32 paŝojn por trovi ion en kvar miliardoj 564 00:23:37,110 --> 00:23:39,650 elemento tabelo pro potencoj de du. 565 00:23:39,650 --> 00:23:43,550 Do du estas 32, estas kvar miliardoj. 566 00:23:43,550 --> 00:23:50,430 >> Tiel bela freneza kiom vi ankoraŭ ene kiel sufiĉe malgranda nombro da ŝtupoj 567 00:23:50,430 --> 00:23:52,650 trovi ion kvar miliardoj elementoj. 568 00:23:52,650 --> 00:23:55,730 Do en tiu noto, ni estas tuj programi tiu 569 00:23:55,730 --> 00:23:58,950 tial vi uloj povas reale speco de vidi kiel tio funkcias. 570 00:23:58,950 --> 00:24:01,520 Bone, do vi uloj povas kodigi. 571 00:24:01,520 --> 00:24:04,100 Mi tuj lasos infanoj paroli iomete. 572 00:24:04,100 --> 00:24:07,970 Konatiĝu personoj ĉirkaŭ vi, kiu estas kion iu volis de lasta sekcio. 573 00:24:07,970 --> 00:24:10,280 >> Tiel ekkoni la homojn ĉirkaŭ vi. 574 00:24:10,280 --> 00:24:11,305 Paroli iomete. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 Kaj mi volas de vi infanoj nun estas nur 577 00:24:15,730 --> 00:24:17,575 provu krei modelon de _pseudocode_. 578 00:24:17,575 --> 00:24:18,075 OK? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Halt. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Mi volas de vi uloj estas vi nur tuj plenigi ĉi dum kazo. 583 00:24:29,520 --> 00:24:32,170 Do mi proponis tiujn suprajn kaj subaj baroj kiuj 584 00:24:32,170 --> 00:24:35,250 reprezenti la komenco kaj la fino de nia tabelo. 585 00:24:35,250 --> 00:24:40,440 Kaj vi tuj reale banto tra kaj elkompreni 586 00:24:40,440 --> 00:24:42,470 kion ni faras ene de tiu tempo buklo. 587 00:24:42,470 --> 00:24:45,810 >> Do se vi povas diveni out-- mi aludo there-- kio estas kazoj 588 00:24:45,810 --> 00:24:46,640 ke ni havas ĉi tie? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Do se vi volas eltrovi la kazoj, ni _Pseudocode_ tiuj 591 00:24:51,560 --> 00:24:53,350 kaj tiam ni efektive programi ilin. 592 00:24:53,350 --> 00:24:55,330 Kaj tuj estos, mi opinias, espereble ĝi malebligos 593 00:24:55,330 --> 00:24:56,788 esti iom pli facila ol vi supozas. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Ĉar ne ke multe kodon, efektive, kio estas vere genia. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Hmm? 598 00:25:35,018 --> 00:25:35,893 >> Student: [inaudible]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 Instruisto: Jes. 601 00:25:37,650 --> 00:25:38,595 Okazis io trovi en la mezo. 602 00:25:38,595 --> 00:25:39,552 >> Student: Do ni povas uzi tiun. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> Instruisto: Perfekta. 605 00:25:40,603 --> 00:25:42,950 Do tio estas la unua aĵo kiun ni bezonas por fari. 606 00:25:42,950 --> 00:25:44,330 Do trovu la mezo. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Granda. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Do ĉu vi havas ideon de kiel ni povus vere trovos la mezo kun kodo? 611 00:25:55,010 --> 00:25:55,980 >> Student: Yeah. 612 00:25:55,980 --> 00:25:57,000 n ol 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 Instruisto: Do ​​n super 2. 615 00:25:59,500 --> 00:26:05,170 Do unu afero por memori estas ke via supra kaj subaj baroj ŝanĝi. 616 00:26:05,170 --> 00:26:08,110 Ni daǔre constricting la parto de la tabelo ni serĉas. 617 00:26:08,110 --> 00:26:11,970 Do n super 2 funkcias nur por la unua afero kiun ni faras. 618 00:26:11,970 --> 00:26:17,810 Tiel prenante supra kaj malsupra en rakontas, kiom eble ni atingos, ke meza ero? 619 00:26:17,810 --> 00:26:20,640 Ĉar ni deziras la mezo inter supra kaj malsupra dekstra? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Hmm? 622 00:26:22,494 --> 00:26:23,369 >> Student: [inaudible]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> Instruisto: Do ​​ni havas iom meza. 625 00:26:28,080 --> 00:26:32,730 Kaj tio estos supra plus malsupra ol 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Awesome. 628 00:26:35,690 --> 00:26:36,570 Tie ni iras. 629 00:26:36,570 --> 00:26:37,280 Unu linio suben. 630 00:26:37,280 --> 00:26:38,560 Vi ĉiuj estas sur via vojo. 631 00:26:38,560 --> 00:26:41,400 Do nun ke ni havas niajn mezo, kion ni volas fari? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Nur ĝenerale. 634 00:26:45,900 --> 00:26:47,734 Vi ne devas programi ĝin. 635 00:26:47,734 --> 00:26:48,335 Jes. 636 00:26:48,335 --> 00:26:49,210 Student: [inaudible]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 Instruisto: Do ​​ĝi estas pli ĉar vi estas trovanta la mezumo inter la du 639 00:27:10,310 --> 00:27:10,810 de ili. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Do, se vi pensas pri ili, kiel speco de kreskanta el la flankoj, 642 00:27:17,370 --> 00:27:21,640 pensi pri ĝi kiel vi alproksimigi meze, vi volas tiel. 643 00:27:21,640 --> 00:27:27,150 Do se vi estus ambaŭflanke de la mezo, kaj ni havas kiel 5 kaj 7. 644 00:27:27,150 --> 00:27:31,440 Kiam vi aldonas ilin al vi akiri 12, vi dividos 2, estas 6. 645 00:27:31,440 --> 00:27:33,726 >> Kelkfoje estas malfacile klarigi kial tio funkcias, 646 00:27:33,726 --> 00:27:35,600 sed se vi laboras per ekzemplo kelkfoje, 647 00:27:35,600 --> 00:27:37,962 Ĝi helpos vin eltrovi se Ĝi devus esti pli aŭ malpli. 648 00:27:37,962 --> 00:27:38,846 Jes. 649 00:27:38,846 --> 00:27:40,830 >> Student: [inaudible] precize en la mezo 650 00:27:40,830 --> 00:27:43,950 se ili havis kazon kie tie estas multa pli malgrandaj nombroj 651 00:27:43,950 --> 00:27:45,860 kaj kiel unu granda nombro? 652 00:27:45,860 --> 00:27:49,750 >> Instruisto: Do ​​ĉiuj vi bezonas Estas la mezo de la tabelo. 653 00:27:49,750 --> 00:27:53,010 Do se vi havis amason de malgrandaj nombroj kaj tiam oni vere granda nombro 654 00:27:53,010 --> 00:27:54,799 fine, ne gravas. 655 00:27:54,799 --> 00:27:56,840 Ĉiuj kiu importas estas kiu ili estas ordigataj vi nur 656 00:27:56,840 --> 00:27:59,339 deziras rigardi la mezo de la tabelo ĉar vi estas ankoraŭ 657 00:27:59,339 --> 00:28:00,700 tranĉaĵanta vian problemon en la duono. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Malvarmeta. 660 00:28:03,680 --> 00:28:06,430 Do nun ke ni havas la mezo, kion ni faru nun? 661 00:28:06,430 --> 00:28:07,150 >> Student: Komparu. 662 00:28:07,150 --> 00:28:08,150 Instruisto: La kompari. 663 00:28:08,150 --> 00:28:11,670 Do kompari mezo al value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Malvarmeta. 666 00:28:15,160 --> 00:28:17,950 Do vi vidas tie supre ni havas tiun valoron ni volas tie supre. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Memoru ke ni estas tabelo. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Do mezo referencas al la indekso. 671 00:28:26,970 --> 00:28:29,785 Do ni volas fari valorojn de meza. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Ne forgesu, se vi volas kompari, duobla egalaj. 674 00:28:35,650 --> 00:28:38,250 Vi do sola egalas vi nur tuj religi ĝin, 675 00:28:38,250 --> 00:28:41,090 kaj tiam, kompreneble, estas tuj estos la valoro vi volas. 676 00:28:41,090 --> 00:28:42,300 Do ne faru tion. 677 00:28:42,300 --> 00:28:44,350 >> Do ni tuj vidos se la valorojn ĉe la mezo 678 00:28:44,350 --> 00:28:46,460 estas egala al la valoro ni volas. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Ne forgesu vian krampoj. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox devus foriri. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Do kion ni faru en tiu kazo? 685 00:28:56,200 --> 00:28:59,360 Se ĝi estas kion ni volas reveni? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Ni provas diri. 688 00:29:02,626 --> 00:29:03,440 >> Student: Presu ekstere. 689 00:29:03,440 --> 00:29:05,314 >> Instruisto: Nu, ni ne volas presi ekstere. 690 00:29:05,314 --> 00:29:08,220 Do tio estas bool tie, do ni volas reveni vera aŭ malvera. 691 00:29:08,220 --> 00:29:12,280 Ni diras, estas tiu nombro unu [? RRA? ?] Do se ĝi estas, 692 00:29:12,280 --> 00:29:13,788 Ni nur redoni ĝin vera. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Se mi povas literumi vera. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> Student: Kial vi ne revenos nulo? 697 00:29:20,805 --> 00:29:22,930 Instruisto: Tiel vi povus reveni nulo se vi volas. 698 00:29:22,930 --> 00:29:26,780 Sed en ĉi tiu kazo, ĉar nia funkcio redonas bool, 699 00:29:26,780 --> 00:29:28,962 Ni bezonas reveni ĉu vera aŭ malvera. 700 00:29:28,962 --> 00:29:30,920 Student: Kiam vi estas dirante bulea esprimo 701 00:29:30,920 --> 00:29:33,450 ĉu vi starigis ĝin egala al falsa? 702 00:29:33,450 --> 00:29:39,860 Kiel se mi volas diri, se tiu kondiĉo ne konis, kiel estas supra egalas malvera. 703 00:29:39,860 --> 00:29:42,332 Ĉu ĝi komprenos se vi nur metis falsajn transe? 704 00:29:42,332 --> 00:29:43,040 Instruisto: Jes. 705 00:29:43,040 --> 00:29:44,820 Do efektive, se vi estas iam fari ion 706 00:29:44,820 --> 00:29:49,600 kiel estas supra aŭ estas pli malaltaj, kiu revenas vera aŭ malvera 707 00:29:49,600 --> 00:29:53,850 kaj ĝi estas efektive malbona stilon diru egalas egalas veraj aŭ egalaj 708 00:29:53,850 --> 00:29:54,840 egalas malvera. 709 00:29:54,840 --> 00:30:00,210 Vi volas uzi tiun rezulto kiel kiel via ĉeko. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Ne, kion mi volis. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Tio estas kion mi volis. 714 00:30:09,240 --> 00:30:13,205 Do, en la kazo de vi demandante pri iu kiel savi ĉi en c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Do se ni havas int main (void) kaj ion kiel tiu. 717 00:30:25,150 --> 00:30:31,922 Kaj vi havas se estas supraj de iu enmeton kaj vi 718 00:30:31,922 --> 00:30:33,630 demandante se vi povas fari ion similan? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Rajto? 721 00:30:35,679 --> 00:30:37,470 Lernanto: Mi provis fari ĝin [inaudible]. 722 00:30:37,470 --> 00:30:38,450 Ĉar se it's-- 723 00:30:38,450 --> 00:30:39,200 Instruisto: Ĝuste. 724 00:30:39,200 --> 00:30:41,197 Do vi volas ĉi tion al esti malvera, dekstra? 725 00:30:41,197 --> 00:30:41,780 Student: Yeah. 726 00:30:41,780 --> 00:30:45,960 Instruisto: Do ​​en tiu kazo vi volas lin ekzekuti se ĝi ne estas vera. 727 00:30:45,960 --> 00:30:50,510 Do la malvarmeta afero vi estas tio. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Do memoru ekkrio punkto neas tion? 730 00:30:55,650 --> 00:30:58,270 Ĝi diras [inaudible] signifas ne. 731 00:30:58,270 --> 00:31:03,590 Do se ni rigardas nur tiun parton ĉi tie, oni kredus 732 00:31:03,590 --> 00:31:05,740 diri ke taksas al falsa kiel vi deziras ĝin. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Ne falsaj veras kion signifas tiu ekzekutus. 735 00:31:09,880 --> 00:31:11,037 Ĉu tio havas sencon? 736 00:31:11,037 --> 00:31:11,620 Student: Yeah. 737 00:31:11,620 --> 00:31:12,453 Instruisto: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 OK. 740 00:31:14,300 --> 00:31:16,330 Do ni povus simple reveni vera en tiu kazo. 741 00:31:16,330 --> 00:31:20,357 Do nun ni havas du aliajn kazoj en tiu kazo. 742 00:31:20,357 --> 00:31:21,565 Kio estas niaj du aliajn kazojn? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Ni nur faru gxin tiamaniere. 745 00:31:32,900 --> 00:31:40,660 Do ni komencu per alia se taksas je la mezo 746 00:31:40,660 --> 00:31:43,230 estas malpli ol la valoro ni volas. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Do nia valoro en la mezo estas malpli ol la valoro kiun ni serĉas. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Do kion baro vi ke ni volas ĝisdatigi? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Supra aŭ suba? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Supra? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Do kiu flanko de la tabelo ni tuj estos rigardante? 757 00:32:06,470 --> 00:32:07,500 >> Student: La malsupra. 758 00:32:07,500 --> 00:32:09,750 >> Instruisto: Ni ni iras esti rigardante maldekstren. 759 00:32:09,750 --> 00:32:11,120 Do alie se malmulta valoro estas malpli. 760 00:32:11,120 --> 00:32:14,730 Do via mezo valoron tie estas malpli ol kion ni volas. 761 00:32:14,730 --> 00:32:17,202 Do ni volas preni la dekstra flanko de nia tabelo. 762 00:32:17,202 --> 00:32:18,910 Do ni tuj ĝisdatigi niajn suba baro. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Do ni religi nian malsupra. 765 00:32:23,020 --> 00:32:25,221 Kaj kion vi pensas malsupra devus esti? 766 00:32:25,221 --> 00:32:26,304 Student: La meza valoro? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 Instruisto: Do ​​la mezo value-- 769 00:32:28,820 --> 00:32:30,136 Student: Plus 1. 770 00:32:30,136 --> 00:32:31,010 Instruisto: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Ĉu iu povas diri al mi, kial Ni havas tiun plus 1? 773 00:32:34,380 --> 00:32:35,730 >> Student: [? Neniu valoron?] estas pli egala al gxi. 774 00:32:35,730 --> 00:32:36,120 >> Instruisto: Ĝuste. 775 00:32:36,120 --> 00:32:38,661 Ĉar ni jam scias ke nia mezo valoro ne egala al 776 00:32:38,661 --> 00:32:42,750 kaj ni volas ekskludi ĝin de ĉiuj postaj serĉoj. 777 00:32:42,750 --> 00:32:46,360 Se vi forgesas ke plus 1, ĉi ŝatos buklo nedifinite. 778 00:32:46,360 --> 00:32:49,620 Kaj vi nur estos kaptitaj en senfina buklo kaj tiam vi segfault 779 00:32:49,620 --> 00:32:50,370 kaj aĵoj iras malbone. 780 00:32:50,370 --> 00:32:54,780 Tiel ĉiam certiĝu, ke vi ne inkludante la valoro kiun vi ĵus 781 00:32:54,780 --> 00:32:55,380 rigardis. 782 00:32:55,380 --> 00:32:58,530 Do ni prizorgas ke kun alpago 1. 783 00:32:58,530 --> 00:33:04,840 >> Do nun ni havas nia lasta kondiĉo kiun mi ĉiam por sekureco sake 784 00:33:04,840 --> 00:33:12,664 vi povas kontroli ĉi tie, alie se valoro Meze estas pli granda ol la valoro 785 00:33:12,664 --> 00:33:13,163 ni volas. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Tio signifas, ke ni volas maldekstre duono. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Do kiu ni tuj ĝisdatigi? 790 00:33:23,260 --> 00:33:23,760 Supra. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 Kaj kio estas ĉi tiu tuj egalos? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Meza minus 1 ĉar, kompreneble ni volas 795 00:33:33,690 --> 00:33:38,370 por certiĝi, ke ni estas ne rigardante ke meza valoro denove. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 Kaj tiam ni havos. 798 00:33:45,110 --> 00:33:45,610 Nur tio. 799 00:33:45,610 --> 00:33:46,820 Jen ĉio duuma serĉo estas. 800 00:33:46,820 --> 00:33:48,190 Ne estas tiel malbona, dekstra? 801 00:33:48,190 --> 00:33:51,590 Estas kiel 10 linioj de Kodo kun blanka spaco. 802 00:33:51,590 --> 00:33:57,510 Do tre potenca, tre utila, vi volas esti uzante ĝin en unu el viaj postaj psets. 803 00:33:57,510 --> 00:33:59,360 Eble tio ne estas unu, sed poste. 804 00:33:59,360 --> 00:34:00,670 Tiel lernas ĝin. 805 00:34:00,670 --> 00:34:01,510 Amas ŝin. 806 00:34:01,510 --> 00:34:02,980 Ĝi traktos vin bone. 807 00:34:02,980 --> 00:34:05,370 Do ĉu iu havas ajnan demandoj pri duuma serĉo? 808 00:34:05,370 --> 00:34:06,196 Jes. 809 00:34:06,196 --> 00:34:09,840 >> Lernanto: Ĉu gravas ĉu via n estas para aŭ nepara? 810 00:34:09,840 --> 00:34:10,750 >> Instruisto: No. 811 00:34:10,750 --> 00:34:18,150 Ĉar ni jxetu gxin en la mezon de de int, gxi simple malpligrandigi ĝin. 812 00:34:18,150 --> 00:34:21,600 Do ĝi restos entjero kaj ĝi volas eventuale ordigi tra ĉio. 813 00:34:21,600 --> 00:34:23,909 Do vi ne devas maltrankviligi pri tio. 814 00:34:23,909 --> 00:34:24,580 CXiu bona? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Awesome. 817 00:34:26,850 --> 00:34:27,919 Malvarmeta. 818 00:34:27,919 --> 00:34:30,836 Do, vi uloj havas ĉi. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slideshow. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Do kiel ni parolas, mi scias David menciita komplekseco runtimes. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Do, en la plej bona kazo, estas nur unu, kiun ni nomas konstanta tempo. 825 00:34:50,340 --> 00:34:51,909 Ĉu iu povas diri al mi, kial tiu povus esti? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Kio tipo de scenaro estus kiu kunportas? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Hmm. 830 00:34:58,760 --> 00:34:59,926 >> Student: [inaudible] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 Instruisto: Do ​​la mezo estas la unua elemento kiun ni atingos, dekstra? 833 00:35:03,830 --> 00:35:08,167 Do ĉu tabelo de unu aŭ ajn ni serĉas nur 834 00:35:08,167 --> 00:35:09,750 sekvinbero al esti vangofrapon DAB en la mezo. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Do tio estas nia plej bona kazo. 837 00:35:13,380 --> 00:35:17,540 Vi akiras en verajn problemojn, probable ne tuj atingos [inaudible] kiu ofte. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Kio pri niaj plej malbona kazo? 840 00:35:19,750 --> 00:35:21,270 Nia plej malbona kazo estas log n. 841 00:35:21,270 --> 00:35:25,360 Kaj kiu devas vidi kun la tuta potencoj de du afero kiun mi raportis. 842 00:35:25,360 --> 00:35:30,930 >> Do, en la plej malbona kazo signifus ke ni devis haki la tabelo malsupren 843 00:35:30,930 --> 00:35:33,270 ĝis ĝi estis elemento de unu. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Do ni devis haki ĝin en duono tantas fojoj kiel ni eble povus. 846 00:35:38,930 --> 00:35:41,430 Tio estas kial ĝi estas log n ĉar vi simple teni dividadon por du. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Do premisoj, kiujn vi bezonas koni se vi iam 849 00:35:45,830 --> 00:35:48,050 tuj uzas binaran serĉon. 850 00:35:48,050 --> 00:35:50,680 Via elementoj devas esti ordo. 851 00:35:50,680 --> 00:35:53,890 Ili devas esti ordo ĉar tio estas la sola maniero vi 852 00:35:53,890 --> 00:35:57,060 povas scii se vi povas forĵeti duonon el ĝi. 853 00:35:57,060 --> 00:36:00,260 >> Se vi havis ĉi implikas sakon de nombroj kaj vi diras, 854 00:36:00,260 --> 00:36:05,380 OK, mi tuj kontrolu la mezo nombro kaj la nombro Mi serĉas 855 00:36:05,380 --> 00:36:08,510 estas malpli ol tio, mi simple irante arbitre elĵetas duonon. 856 00:36:08,510 --> 00:36:11,130 Vi ne scius se via nombroj en tiu alia duono. 857 00:36:11,130 --> 00:36:12,655 Via listo devas esti ordo. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Siavice, ĉi tio povas esti antaŭenirante iom, 860 00:36:16,560 --> 00:36:18,360 sed vi bezonos havi hazarda aliro. 861 00:36:18,360 --> 00:36:21,940 Vi bezonos por povi ĝuste iri al tiu mezo elemento. 862 00:36:21,940 --> 00:36:25,110 Se vi devas trairi tra ion 863 00:36:25,110 --> 00:36:28,630 aŭ ĝi prenas vin ekstra paŝoj por atingi ke meza ero, 864 00:36:28,630 --> 00:36:31,750 ĝi ne log n anymore ĉar vi aldonante pli laboro en ĝin. 865 00:36:31,750 --> 00:36:34,800 Kaj ĉi faros iom pli sentita en du semajnoj, 866 00:36:34,800 --> 00:36:37,950 sed mi simple ia volis antaŭparolo, doni vi uloj ideon de kio estas 867 00:36:37,950 --> 00:36:38,999 veni. 868 00:36:38,999 --> 00:36:40,790 Sed tiuj estas la du gravaj premisoj 869 00:36:40,790 --> 00:36:44,804 ke vi bezonos por duuma listo. 870 00:36:44,804 --> 00:36:45,720 Certiĝu ke la ordo. 871 00:36:45,720 --> 00:36:47,920 Tio estas la granda unu por vi uloj nun. 872 00:36:47,920 --> 00:36:52,170 Kaj en kiun ni povas iri en la resto de niaj varoj. 873 00:36:52,170 --> 00:36:56,444 Do kvar sorts-- bobelo, inserción, selektado kaj kunigon. 874 00:36:56,444 --> 00:36:57,485 Ili estas ĉiaj malvarmeta. 875 00:36:57,485 --> 00:37:02,860 Se vi uloj decidas preni CS 124, Vi lernos pri ĉiaj varoj. 876 00:37:02,860 --> 00:37:07,575 Kaj se vi estas XKCD fano, tie Estas vere malvarmeta komikajn pri 877 00:37:07,575 --> 00:37:11,530 kiel vere senutila varoj, kiujn mi tre rekomendas vin tuj rigardi. 878 00:37:11,530 --> 00:37:16,170 Unu el ili estas kiel panikon varon, kiun estas kiel, ho ne, revenu hazarda tabelo. 879 00:37:16,170 --> 00:37:16,991 Elŝaltita sistemo. 880 00:37:16,991 --> 00:37:17,490 Lasu. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Do geeky humuro estas ĉiam bona. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Do ĉu iu memoras speco de kiel simple ĝenerala ideo 885 00:37:25,750 --> 00:37:27,810 de kiel bobelo speco funkcias. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Vi memoras? 888 00:37:32,155 --> 00:37:32,755 >> Student: Yeah. 889 00:37:32,755 --> 00:37:33,970 >> Instruisto: Iru al ĝi. 890 00:37:33,970 --> 00:37:38,980 >> Student: Do vi iras tra kaj se ĝi estas pli granda, tiam vi interŝangi la du. 891 00:37:38,980 --> 00:37:39,820 >> Instruisto: Hmm. 892 00:37:39,820 --> 00:37:40,564 Ĝuste. 893 00:37:40,564 --> 00:37:41,730 Do vi nur persisti tra. 894 00:37:41,730 --> 00:37:43,050 Vi kontrolu du ciferoj. 895 00:37:43,050 --> 00:37:46,510 Se la antauxjugxo estas pli granda ol la poste, 896 00:37:46,510 --> 00:37:50,230 vi simple interŝanĝi ilin por ke tiamaniere ĉiuj altaj nombroj 897 00:37:50,230 --> 00:37:54,990 bobelo supren al la fino de la listo kaj la tuta suba nombroj bobelo suben. 898 00:37:54,990 --> 00:37:59,355 >> Li montras vi uloj malvarmeta soni efekton ordig video? 899 00:37:59,355 --> 00:38:00,480 Estas speco de malvarmeta. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Tiel kiel Robert nur diris, la algoritmo ke vi simple paŝo tra la listo, 902 00:38:05,200 --> 00:38:07,930 interŝanĝante la najbaraj valoroj se ili ne estas en ordo. 903 00:38:07,930 --> 00:38:10,975 Kaj tiam simple daŭre ripetas ĝis vi ne faras neniun interŝanĝojn. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Do ne estas malbona, ĉu? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Do ni nur devas rapidan ekzemplo tie. 908 00:38:16,319 --> 00:38:18,360 Do tiu tuj ordigi ilin en supreniranta ordon. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Do kiam ni trairu la unua tempo, ni rigardu tra ok 911 00:38:23,470 --> 00:38:26,880 kaj ses estas evidente ne en ordo, ni interŝanĝas ilin. 912 00:38:26,880 --> 00:38:27,985 >> Do rigardu la venonta unu. 913 00:38:27,985 --> 00:38:29,430 Ok kaj kvar ne en ordo. 914 00:38:29,430 --> 00:38:30,450 Permuta ilin. 915 00:38:30,450 --> 00:38:32,530 Kaj tiam ok kaj du, interŝanĝi ilin. 916 00:38:32,530 --> 00:38:33,470 Tie ni iras. 917 00:38:33,470 --> 00:38:39,519 Do post via unua paŝo, vi scias, ke via plej granda nombro 918 00:38:39,519 --> 00:38:41,810 tuj estos tuta vojo ĉe la supro, ĉar ĝi estas nur 919 00:38:41,810 --> 00:38:44,210 tuj estos senĉese pli granda ol ĉiu alia 920 00:38:44,210 --> 00:38:46,810 kaj ĝi estas nur tuj bobelo la tutan vojon al la fino. 921 00:38:46,810 --> 00:38:48,226 Ĉu tio havas sencon por ĉiuj? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Malvarmeta. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Tial do ni rigardas nian duan paŝon. 926 00:38:53,920 --> 00:38:54,980 Ses kaj kvar, ŝaltilo. 927 00:38:54,980 --> 00:38:55,920 Ses kaj du, ŝaltilo. 928 00:38:55,920 --> 00:38:58,700 Kaj nun ni havas kelkon en ordo. 929 00:38:58,700 --> 00:39:02,240 Do por ĉiu paŝo kiun ni fari per nia tutan liston, 930 00:39:02,240 --> 00:39:06,320 Ni scias, ke tiel multaj numeroj fine estos estinta ordo. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Do ni faras trian pass, kiu estas unu swap. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 Kaj tiam en nia kvara pasas, ni havas nulon fendoj. 935 00:39:15,910 --> 00:39:18,570 Kaj do ni scias ke niaj tabelo estas ordigita. 936 00:39:18,570 --> 00:39:20,900 >> Kaj tio estas la granda aferon kun bobelo varo. 937 00:39:20,900 --> 00:39:23,720 Ni scias, ke kiam ni havas nulo interŝanĝojn, kiuj 938 00:39:23,720 --> 00:39:26,497 signifas ke ĉiu estas en kompleta ordo. 939 00:39:26,497 --> 00:39:27,580 Ĝi estas speco de kiel ni kontrolu. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Do ni estas ankaux tuj programi bobelo speco kiu ankaŭ ne estas tro malbona. 942 00:39:36,480 --> 00:39:38,120 Neniu el tiuj estas ke malbona. 943 00:39:38,120 --> 00:39:40,210 Mi scias ke ili povas simili iom timiga. 944 00:39:40,210 --> 00:39:42,124 Mi sciis, kiam Mi prenis la klaso, eĉ kiam mi 945 00:39:42,124 --> 00:39:44,290 instruis la klason por la unuan fojon pasintjare, 946 00:39:44,290 --> 00:39:46,165 Mi ŝatas, kiel mi faru tion? 947 00:39:46,165 --> 00:39:48,540 Indas teorie, sed Kiel do ni efektive faru tion? 948 00:39:48,540 --> 00:39:51,420 Tial Mi ankaux volas marŝi tra kodo kun vi uloj tie. 949 00:39:51,420 --> 00:39:54,915 Do mi havas _pseudocode_ por vi uloj tiu tempo. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Do ĝuste konservi ĉi tio en menso kiel ni al transiron super. 952 00:39:58,970 --> 00:40:04,210 Do ni havas kelkajn nombrilo ke sekvadon de niaj interŝanĝojn, 953 00:40:04,210 --> 00:40:08,370 ĉar ni bezonas por certigi ke ni kontrolanta tio. 954 00:40:08,370 --> 00:40:11,830 Kaj ni persisti la tuta tabelo kiel ni faris kun ĉi tiu ekzemplo. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Se la elemento antaux estas pli granda ol la elemento post kie ni estas je, 957 00:40:17,325 --> 00:40:20,760 Ni interŝanĝas ilin kaj ni pliigo nia nombrilo ĉar ni apenaŭ interŝanĝi, 958 00:40:20,760 --> 00:40:23,850 Ni volas lasi nian nombrilo scias. 959 00:40:23,850 --> 00:40:26,247 Demandojn tie? 960 00:40:26,247 --> 00:40:27,580 Io ŝajnas amuza super tie. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 Lernanto: Ĉu vi starigis la vendotablo al nulo ĉiufoje kiam vi iros tra la buklo? 963 00:40:32,350 --> 00:40:34,339 Ĉu vi ne plu iri reen al nulo ĉiufoje? 964 00:40:34,339 --> 00:40:35,505 Instruisto: Ne nepre. 965 00:40:35,505 --> 00:40:39,710 Do kio okazas estas ni trairu tien. 966 00:40:39,710 --> 00:40:43,830 Tiel faru dum, memoru ĉi ekzekutos fojon sen halto. 967 00:40:43,830 --> 00:40:46,480 Do tuj starigis la nombrilo egala al nulo, 968 00:40:46,480 --> 00:40:48,070 tiam tuj persisti tra. 969 00:40:48,070 --> 00:40:50,590 Kiel ĝi ripetas tra, ĝi ĝisdatigos vendotablo. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Kiel ĝi ĝisdatigas vendotablo, kiam ĝi estas farita, kiam ĝi atingis la finon de la milito, 972 00:40:56,900 --> 00:41:00,830 se nia listo ne ordigataj nombrilo estos ĝisdatigita. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Tial ĝi kontrolas la kondiĉon kaj ĝi diras, OK, estas nombrilo granda ol nulo. 975 00:41:07,150 --> 00:41:09,290 Se jes, faru ĝin denove. 976 00:41:09,290 --> 00:41:14,340 Vi volas reagordi tiel ke kiam vi trairu, nombrilo estas egala al nulo. 977 00:41:14,340 --> 00:41:18,240 Se vi iras tra ordo tabelo, nenion ŝanĝas, 978 00:41:18,240 --> 00:41:21,355 tio fiaskos, kaj vi redoni la ordo listo. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Ĉu tio havas sencon? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 Student: eble en iom. 983 00:41:26,356 --> 00:41:27,147 Instruisto: Bone. 984 00:41:27,147 --> 00:41:28,980 Se estas iu alia demando kiu venas supren. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Jes. 987 00:41:30,680 --> 00:41:33,760 >> Student: Kion la funkcio prezentu interŝanĝante la elementoj? 988 00:41:33,760 --> 00:41:36,900 >> Instruisto: Do ​​ni povas fakte skribi ke se ni tuj nun. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Malvarmeta. 991 00:41:38,300 --> 00:41:42,155 Do en tiu noto, Alison tuj por reiri al la aparato. 992 00:41:42,155 --> 00:41:43,080 Ĝi tuj estos amuza. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 Kaj ni havas nian belan bobelo speco afero tie. 995 00:41:47,390 --> 00:41:50,800 Do mi jam faris bicikladon tra la tabelo. 996 00:41:50,800 --> 00:41:53,030 Ni havas niajn interŝanĝojn kiuj estas egala al nulo. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Do ni volas interŝanĝi apudajn elementoj se ili estas el ordo. 999 00:41:58,440 --> 00:42:03,020 Do la unua afero kiun ni bezonas por Ne estas persisti tra nia tabelo. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Do kiel vi pensas ni povus persisti tra nia tabelo? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Ni havas por kaj i egalas 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Ni deziras mi al esti malpli ol n minus 1 minus k. 1006 00:42:22,454 --> 00:42:23,870 Kaj mi klarigos ke en dua. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Do tio estas optimumiga tie kie, memoras, ke mi diris post ĉiu paŝo 1009 00:42:32,830 --> 00:42:36,655 tra la tabelo ni scias, ke kio estas on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Do post paŝo ni scias ke tiu ordo. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Post du paŝoj ni scias ke ĉiuj ĉi estas ordigitaj. 1014 00:42:50,060 --> 00:42:52,750 Post tri paŝoj ni scias ke la ordo. 1015 00:42:52,750 --> 00:42:55,620 Do la manieron mi ripetanta tra la tabelo ĉi tie, 1016 00:42:55,620 --> 00:43:01,090 Estas ĝi estas certigi nur iri tra kion ni scias estas unsorted. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 Tio estas nur unu optimumigo. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Vi povus skribi ĝin naive simple ripetanta tra ĉio, 1021 00:43:08,210 --> 00:43:09,970 estus simple preni plu. 1022 00:43:09,970 --> 00:43:12,470 Kun ĉi kvar buklo estas nur bela optimumigo 1023 00:43:12,470 --> 00:43:18,460 ĉar ni scias, ke post ĉiu plena ripeto tra la tabelo ĉi tie, 1024 00:43:18,460 --> 00:43:24,050 kiel ĉiu plena buklo tie, ni scias ke oni pli de tiuj elementoj 1025 00:43:24,050 --> 00:43:25,760 estos ordo fine. 1026 00:43:25,760 --> 00:43:28,294 >> Do ni ne devas zorgi pri tiuj. 1027 00:43:28,294 --> 00:43:29,710 Ĉu tio havas sencon por ĉiuj? 1028 00:43:29,710 --> 00:43:30,950 Ke malvarmeta iom lertaĵon? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Do en tiu kazo, se ni ripetanta tra, 1031 00:43:37,270 --> 00:43:50,590 Ni scias, ke ni volas kontroli se tabelo n kaj n plus 1 estas en ordo. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 OK. 1034 00:43:53,559 --> 00:43:54,600 Do jen la _pseudocode_. 1035 00:43:54,600 --> 00:43:57,540 Ni volas kontroli se tabelo n kaj n plus 1 estas en ordo. 1036 00:43:57,540 --> 00:43:59,520 Do kio povus ni havas tie? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Ĝi tuj estos iuj kondiĉa. 1039 00:44:03,120 --> 00:44:04,220 Estos se. 1040 00:44:04,220 --> 00:44:07,066 >> Student: Se tabelo n estas malpli ol tabelo n plus 1. 1041 00:44:07,066 --> 00:44:07,816 Instruisto: Hmm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Nu, malpli ol aŭ pli granda ol. 1044 00:44:10,699 --> 00:44:11,615 Student: Pli granda ol. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Tiam ni volas interŝanĝi ilin. 1047 00:44:17,620 --> 00:44:18,570 Ĝuste. 1048 00:44:18,570 --> 00:44:23,570 Do nun ni eniras kio estas la mekanismo por interŝanĝi ilin? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Do ni iris tra ĉi brevemente, tipo de swap funkcio pasintsemajne. 1051 00:44:28,137 --> 00:44:29,595 Ĉu iu memoras kiel ĝi funkciis? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Do ni ne povas ĝuste religi ilin, ĉu ne? 1054 00:44:34,950 --> 00:44:36,640 Ĉar unu el ili perdiĝas. 1055 00:44:36,640 --> 00:44:41,696 Se ni diras A estas egala al B kaj tiam B estas egala al, ĉiuj subita ambaux 1056 00:44:41,696 --> 00:44:43,150 Estas ĝuste egala al B. 1057 00:44:43,150 --> 00:44:45,720 >> Do kion ni devas fari estas ni havi portempa variablo tio 1058 00:44:45,720 --> 00:44:49,055 tuj tenos unu el nia tempo Ni estas en la procezo de interŝanĝi. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Do kion ni havas estas ke ni devos iom int temp egalas to-- vi povas atribui ĝin 1061 00:44:56,464 --> 00:44:59,130 al kiom oni volas, simple certiĝu vi konservi trako de it-- 1062 00:44:59,130 --> 00:45:01,840 tial en ĉi tiu kazo, mi tuj atribuos ĝin al tabelo n plus 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 Tiel ke tuj teni ajn valoro estas en tiu dua bloko 1065 00:45:07,674 --> 00:45:08,590 ke ni rigardas. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> Kaj tiam ni povas fari estas ni povas iri antaŭeniras kaj religi tabelo n plus 1, 1068 00:45:13,240 --> 00:45:14,990 ĉar ni scias ke ni havas tiun valoron stokita. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Tiu estas ankaŭ unu el la grandaj things-- Mi ne scias ĉu iu el vi 1071 00:45:19,270 --> 00:45:23,780 havis temoj kie se vi ŝanĝos du linioj de kodo subite aferojn laboris. 1072 00:45:23,780 --> 00:45:25,880 Ordo estas tre grava en CS. 1073 00:45:25,880 --> 00:45:29,450 Tiel faro certe vi diagramo aferojn el laŭeble 1074 00:45:29,450 --> 00:45:31,230 pri kio vere okazas. 1075 00:45:31,230 --> 00:45:34,256 Do nun ni tuj religi tabelo n plus 1, 1076 00:45:34,256 --> 00:45:36,005 ĉar ni scias ke ni havas tiun valoron stokita. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> Kaj ni povas atribui ke tabelo n aŭ en ĉi tiu kazo tabelo i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Tro multaj variabloj. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 OK. 1083 00:45:55,470 --> 00:46:01,500 Do nun ni reasignado tabelo i plus 1 egali kio estas en tabelo i. 1084 00:46:01,500 --> 00:46:08,240 Kaj nun ni povas iri tien kaj atribui tabelo i al kio? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Iu? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> Student: 10. 1089 00:46:14,010 --> 00:46:14,680 >> Instruisto: 10. 1090 00:46:14,680 --> 00:46:15,180 Ĝuste. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 Kaj unu lasta afero. 1093 00:46:18,640 --> 00:46:21,840 Se ni interŝanĝis ĝin nun, Kion ni devas fari? 1094 00:46:21,840 --> 00:46:23,740 Kio estas la afero ke tuj informi nin 1095 00:46:23,740 --> 00:46:27,542 se ni iam finiĝi tiun programon? 1096 00:46:27,542 --> 00:46:29,250 Kion diras al ni, ke ni havi ordigita listo? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Se ni ne plenumi ajnan interŝanĝojn, dekstra? 1099 00:46:33,750 --> 00:46:36,900 Se interŝanĝojn egalas nulo je la fino de tiu ĉi. 1100 00:46:36,900 --> 00:46:42,975 Do kiam ajn vi elfari swap, kiel ni nur faris ĉi tie, ni volas ĝisdatigi interŝanĝojn. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 Kaj mi scias, ke estis demando antaŭe pri ĉu eblas 1103 00:46:47,210 --> 00:46:49,689 uzu nul aŭ unu anstataŭe de veraj aŭ falsaj. 1104 00:46:49,689 --> 00:46:50,980 Kaj tio ĉi faras tie. 1105 00:46:50,980 --> 00:46:52,750 Do tio diras se ne interŝanĝojn. 1106 00:46:52,750 --> 00:47:01,310 Do se interŝanĝojn estas nulo, kiu is-- mi ĉiam alportu mian veroj kaj mia falses intermiksiĝas. 1107 00:47:01,310 --> 00:47:03,960 Ni deziras al ni taksi al vera kaj ne estas. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Do se estas nulo, tiam ĝi estas malvera. 1110 00:47:09,630 --> 00:47:12,560 Se vi neas ĝin per [? bang?] devenas vera. 1111 00:47:12,560 --> 00:47:13,975 Tial tiu linio ekzekutas. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Veroj kaj falsa kaj nuloj kaj akiri freneza. 1114 00:47:17,370 --> 00:47:20,690 Nur se vi malrapide marŝi tra ĝi faros senson. 1115 00:47:20,690 --> 00:47:23,320 Sed tio, kio estas tiu malgranda iom da kodo tie faras. 1116 00:47:23,320 --> 00:47:26,490 Do tiu kontrolas vidi ni faris ajnan interŝanĝojn. 1117 00:47:26,490 --> 00:47:30,054 Do se io krom nulo, ĝi tuj estos falsa 1118 00:47:30,054 --> 00:47:31,970 kaj la tuta aĵo estas tuj ekzekuti denove. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Cool? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> Student: Kion signifas rompon fari? 1123 00:47:36,000 --> 00:47:38,990 >> Instruisto: Break simple rompas vin el la buklo. 1124 00:47:38,990 --> 00:47:41,570 Do en tiu kazo estus nur ŝatus fini la programon 1125 00:47:41,570 --> 00:47:43,828 kaj vi farus ĝuste havas vian ordo listo. 1126 00:47:43,828 --> 00:47:44,536 Student: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 Instruisto: Mi bedaŭras? 1129 00:47:49,010 --> 00:47:52,110 Student: Ĉar ni antaŭe uzis skribita 1 pli skribita nulo 1130 00:47:52,110 --> 00:47:54,170 prezenti ke se kiuj funkcios aŭ ne. 1131 00:47:54,170 --> 00:47:54,878 >> Instruisto: Jes. 1132 00:47:54,878 --> 00:47:56,410 Do vi povas reveni nulo aŭ 1. 1133 00:47:56,410 --> 00:47:58,950 En ĉi tiu kazo, ĉar ni ne vere fari ion kun la funkcio, 1134 00:47:58,950 --> 00:48:00,150 Ni nur volas ĝin rompi. 1135 00:48:00,150 --> 00:48:02,680 Ni ne vere zorgas pri tio. 1136 00:48:02,680 --> 00:48:06,960 Bremso estas ankaŭ bona se ĝi estas uzata por florantajxo 1137 00:48:06,960 --> 00:48:10,710 de kvar cikloj aŭ kondiĉoj kiuj vi ne volas konservi ekzekuti. 1138 00:48:10,710 --> 00:48:12,110 Ĝi nur prenas vin de ili. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Estas iom de nuancon afero. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Mi sentas ke estas multan manon svingas, 1143 00:48:18,445 --> 00:48:19,740 kiel vi lernos pri ĉi baldaŭ. 1144 00:48:19,740 --> 00:48:20,955 >> Sed vi lernos pri ĉi baldaŭ. 1145 00:48:20,955 --> 00:48:21,500 Mi promesas. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 OK. 1148 00:48:23,170 --> 00:48:24,840 Do ne ĉiuj ricevas bobelo speco? 1149 00:48:24,840 --> 00:48:25,550 Ne tro malbona. 1150 00:48:25,550 --> 00:48:31,910 Persisti tra, swap aferojn uzante temp variablo, kaj ni ĉiuj starigis tie? 1151 00:48:31,910 --> 00:48:32,960 Malvarmeta. 1152 00:48:32,960 --> 00:48:34,080 Awesome. 1153 00:48:34,080 --> 00:48:34,807 OK. 1154 00:48:34,807 --> 00:48:35,765 Reen al la PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Demandojn, ĝenerale pri tiuj ĝis nun? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Malvarmeta. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Hmm. 1161 00:48:43,695 --> 00:48:45,279 >> Student: [inaudible] int ĉefa kutime. 1162 00:48:45,279 --> 00:48:46,695 Ĉu vi devas havi tiun por tio? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> Instruisto: Do ​​ni nur rigardis ĝuste je la efektiva ordigado algoritmo. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Se vi havus gxin interne kiel granda programo, 1167 00:48:56,350 --> 00:48:57,891 vi havus int ĉefa ie. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Depende kie vi utiligas ĉi algoritmon, 1170 00:49:02,880 --> 00:49:05,860 ĝi determinus kio estas revenante de gxi. 1171 00:49:05,860 --> 00:49:09,960 Sed por nia kazo, ni estas strikte rigardante kiel faras ĉi reale 1172 00:49:09,960 --> 00:49:11,300 persisti tra tabelo. 1173 00:49:11,300 --> 00:49:12,570 Do ni ne zorgu pri tio. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Do ni parolis pri bona kazo kaj plej malbona kazo scenejoj por duuma serĉo. 1176 00:49:19,830 --> 00:49:22,470 Do ĝi estas ankaŭ grava por fari kiu por ĉiu de niaj varoj. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Do kion vi pensas estas la plej malbona kazo runtime de bobelo speco? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Vi ĉiuj memoras? 1181 00:49:30,700 --> 00:49:31,784 >> Student: N minus 1. 1182 00:49:31,784 --> 00:49:32,700 Instruisto: N minus 1. 1183 00:49:32,700 --> 00:49:35,070 Do tio signifas ke estas n minus 1 komparoj. 1184 00:49:35,070 --> 00:49:40,060 Do unu afero realigi estas ke sur la unua ripeto, 1185 00:49:40,060 --> 00:49:43,360 Ni iru tra, ni komparu tiuj two-- tiel ke estas 1. 1186 00:49:43,360 --> 00:49:46,685 Tiuj du, tri, kvar. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Do post ripeta ni jam havas kvar komparoj. 1189 00:49:55,050 --> 00:49:58,230 Kiam mi parolas pri ekzekuto kaj n. 1190 00:49:58,230 --> 00:50:04,680 N reprezentas la nombron de komparoj kiel funkcio de kiel multaj eroj 1191 00:50:04,680 --> 00:50:05,570 ni havas. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> Do ni iru tra, ni havas kvar. 1194 00:50:08,860 --> 00:50:11,780 La venontan fojon vi scias ke ni ne devas prizorgi ĉi. 1195 00:50:11,780 --> 00:50:15,140 Ni komparu ĉi tiuj du, tiuj du, tiuj du, 1196 00:50:15,140 --> 00:50:20,050 kaj se ni ne havas tiun optimumigo kun la kvar buklo kiun mi skribis, 1197 00:50:20,050 --> 00:50:22,750 Vi devus esti komparante tien anyways. 1198 00:50:22,750 --> 00:50:26,170 Do vi devus kuri tra la tabelo 1199 00:50:26,170 --> 00:50:34,380 kaj fari n komparoj n tempoj, ĉar ĉiufoje kiam ni 1200 00:50:34,380 --> 00:50:36,670 kuras tra ĝi ni specon unu afero. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> Kaj ĉiufoje kiam ni kuras tra la tabelo, ni faru n komparoj. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Do nia runtime cxar tio efektive n kvadratoj, kiuj 1205 00:50:46,330 --> 00:50:48,400 Estas multe pli malbone en nia ensalutu fino ĉar tio 1206 00:50:48,400 --> 00:50:51,965 signifas se ni havis kvar miliardo elementoj, ĝi estas 1207 00:50:51,965 --> 00:50:55,260 tuj prenos al ni kvar miliardoj kvadrato anstataŭ 32. 1208 00:50:55,260 --> 00:51:01,240 Do ne la plej bona tempo de ekzekuto, sed por iuj aferoj, 1209 00:51:01,240 --> 00:51:04,610 vi scias, se vi estas ene certa gamo de eroj 1210 00:51:04,610 --> 00:51:06,540 bobelo speco povas esti delikata uzi. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 Do kio estas la plej bona kazo ekzekuto? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 Student: Zero? 1215 00:51:14,940 --> 00:51:16,420 Aŭ 1? 1216 00:51:16,420 --> 00:51:18,140 >> Instruisto: Do ​​1 farus unu komparon. 1217 00:51:18,140 --> 00:51:19,114 Dekstre. 1218 00:51:19,114 --> 00:51:20,002 >> Student: N minus 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> Instruisto: Do, jes. 1221 00:51:22,320 --> 00:51:22,990 Do n minus 1. 1222 00:51:22,990 --> 00:51:26,510 Whenever vi havas koncepton kiel n minus 1, ni inklinas nur faligi ĝin 1223 00:51:26,510 --> 00:51:31,680 kaj ni simple diri n ĉar vi havas kompari ĉiun el these-- ĉiu paro. 1224 00:51:31,680 --> 00:51:36,470 Do estus n minus 1, kiun ni ni volas nur diri estas proksimume n. 1225 00:51:36,470 --> 00:51:39,280 Kiam vi kontraktanta kun ekzekuto, ĉio estas en aproksimas. 1226 00:51:39,280 --> 00:51:43,860 Tiel longe kiel la eksponento estas ĝusta, vi estas sufiĉe bona. 1227 00:51:43,860 --> 00:51:45,700 >> Tiel estas kiel ni pritrakti ĝin. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Tial la plej bona okazo estas n, kiu signifas ke la listo estas jam ordigataj 1230 00:51:51,780 --> 00:51:54,320 kaj ĉiuj ni kuras tra kaj kontrolu ke ĝi estas ordigitaj. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Malvarmeta. 1233 00:51:56,855 --> 00:51:57,355 Bone. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Do kiel vi vidas tie, ni simple havas iom pli grafikaĵoj. 1236 00:52:01,920 --> 00:52:02,660 Do n kvadratoj. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Amuza. 1239 00:52:05,120 --> 00:52:09,730 Multe pli malbone ol n kiel ni vidas, kaj multe, multe pli malbone ol log 2n. 1240 00:52:09,730 --> 00:52:12,060 Kaj tiam vi ankaŭ eniras en log ŝtipoj. 1241 00:52:12,060 --> 00:52:18,020 Kaj vi prenos 124, vi eniri kiel log stelo, kiu estas kiel freneza. 1242 00:52:18,020 --> 00:52:20,172 Do, se vi interesiĝas, lookup log stelo. 1243 00:52:20,172 --> 00:52:20,880 Estas speco de amuzo. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Do ni havas tiun grandan abako. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Nur kapoj supre, tiu estas mirinda abako havi 1248 00:52:28,720 --> 00:52:31,350 por via meza termino ĉar ni longe demandi vin tiuj viaj. 1249 00:52:31,350 --> 00:52:36,090 Do nur kapojn supren, havi tion en via Meze termino sur via bela Gvidfolio 1250 00:52:36,090 --> 00:52:36,616 tie. 1251 00:52:36,616 --> 00:52:37,990 Do ni nur rigardis bobelo varo. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Plej malbona kazo, n kvadratoj, bona kazo, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 Kaj ni iras por rigardi la aliajn. 1256 00:52:44,950 --> 00:52:47,940 >> Kaj kiel vi povas vidi, la sola Kiu vere faras bone 1257 00:52:47,940 --> 00:52:50,910 Estas merge varon, kiun ni devos eniri kial. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Do ni tuj iru al la proksima here-- selektado varo. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Ĉu iu memoras kiom selektado speco funkciis? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Iri por ĝi. 1264 00:53:05,700 --> 00:53:08,210 >> Student: Esence trairu ordonon kaj krei novan liston. 1265 00:53:08,210 --> 00:53:11,001 Kaj ĝuste kiel vi metante elementoj en, metis ilin en la ĝusta loko 1266 00:53:11,001 --> 00:53:11,750 en la nova listo. 1267 00:53:11,750 --> 00:53:14,040 >> Instruisto: Por ke sonoj pli kiel inserción varo. 1268 00:53:14,040 --> 00:53:15,040 Sed vi estas vere proksimaj. 1269 00:53:15,040 --> 00:53:15,915 Ili estas tre similaj. 1270 00:53:15,915 --> 00:53:17,440 Eĉ mi havigu ilin miksas kelkfoje. 1271 00:53:17,440 --> 00:53:18,981 Antaŭ ĉi tiu sekcio mi estis kiel, atendu. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 OK. 1274 00:53:20,630 --> 00:53:24,141 Do kion vi volas fari estas selektado speco, 1275 00:53:24,141 --> 00:53:25,890 la vojo vi povas pensi pri ĝi kaj la vojon 1276 00:53:25,890 --> 00:53:30,140 Mi certiĝu mi provas ne akiri ili intermiksiĝas, estas ĝia transiro 1277 00:53:30,140 --> 00:53:33,280 kaj ĝi selektas la malgranda nombro kaj ĝi 1278 00:53:33,280 --> 00:53:36,070 metas ke komence de via listo. 1279 00:53:36,070 --> 00:53:37,730 Ĝi interŝanĝas kun tiu unua loko. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Ili fakte havas ekzemplon por mi. 1282 00:53:45,370 --> 00:53:46,540 Awesome. 1283 00:53:46,540 --> 00:53:50,130 Do simple maniero pensi it-- selektado varon, elektu la plej malgranda valoro. 1284 00:53:50,130 --> 00:53:51,940 Kaj ni tuj kuri tra ekzemplo 1285 00:53:51,940 --> 00:53:55,320 ke mi kredas helpos ĉar Mi kredas vidaĵojn ĉiam helpas. 1286 00:53:55,320 --> 00:53:58,510 Do ni komencu per io kiu estas tute unsorted. 1287 00:53:58,510 --> 00:54:00,730 Ruĝa estos unsorted, verda estos ordo. 1288 00:54:00,730 --> 00:54:02,190 Ĝi ĉiuj sencon en dua. 1289 00:54:02,190 --> 00:54:08,950 >> Do ni iru tra ni persisti de la komenco ĝis la fino. 1290 00:54:08,950 --> 00:54:12,320 Kaj ni diras, OK, 2 nia malgranda nombro. 1291 00:54:12,320 --> 00:54:15,680 Do ni tuj prenu 2 kaj ni iras movi ĝin al la fronto de niaj tabelo 1292 00:54:15,680 --> 00:54:17,734 ĉar ĝi estas la malgranda kvanto ni havas. 1293 00:54:17,734 --> 00:54:19,150 Do jen kion tiu faras tie. 1294 00:54:19,150 --> 00:54:20,820 Estas nur tuj interŝanĝi tiujn du. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Do nun ni estas ordo parto kaj unsorted parto. 1297 00:54:25,450 --> 00:54:27,810 Kaj kio estas bona por memori pri selektado speco 1298 00:54:27,810 --> 00:54:30,690 Estas ni nur elektanta el unsorted parto. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> La ordo parton vi simple forlasi sola. 1301 00:54:34,527 --> 00:54:35,660 Hmm? 1302 00:54:35,660 --> 00:54:38,452 >> Student: Kiel ĝi scias kio estas la pli malgranda sen kompari ĝin 1303 00:54:38,452 --> 00:54:39,868 al ĉiu alia valoro en la tabelo. 1304 00:54:39,868 --> 00:54:41,250 Instruisto: Edito kompari ĝin. 1305 00:54:41,250 --> 00:54:42,041 Ni ŝatas saltis ĝin. 1306 00:54:42,041 --> 00:54:43,850 Tiu estas nur ĝeneralaj entute. 1307 00:54:43,850 --> 00:54:44,831 Yeah. 1308 00:54:44,831 --> 00:54:47,205 Kiam ni skribas la kodon min certe vi estos pli kontenta. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Sed vi stoki tiu unua elemento kiel la plej malgranda. 1311 00:54:53,030 --> 00:54:56,110 Vi komparas vin diras, OK, ĉu malgrandaj? 1312 00:54:56,110 --> 00:54:56,660 Jes. 1313 00:54:56,660 --> 00:54:57,460 Konservu ĝin. 1314 00:54:57,460 --> 00:54:58,640 Jen ĝi malgrandaj? 1315 00:54:58,640 --> 00:54:59,660 Neniu? 1316 00:54:59,660 --> 00:55:02,510 >> Tiu estas via malgranda, religi ĝin al via valoro. 1317 00:55:02,510 --> 00:55:06,340 Kaj vi estos multe pli feliĉa Kiam ni trairu la kodon. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Do ni iru tra, ni interŝanĝas ĝin, do tiam ni rigardas tiun unsorted porcion. 1320 00:55:13,970 --> 00:55:15,810 Do ni tuj elektu tri eksteren. 1321 00:55:15,810 --> 00:55:18,890 Ni tuj metis ĝin sur je Fine de nia ordo parton. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 Kaj ni simple intencas teni faranta ke, agante tiel, kaj farante tion. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Do jen nia speco de _pseudocode_ tie. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Ni programi ĝin tie en sekundo. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Sed nur io marŝi tra sur alta nivelo. 1330 00:55:37,270 --> 00:55:40,275 Vi tuj iros de i egalas 0 ĝis n minus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Tio estas alia optimumigo. 1333 00:55:43,530 --> 00:55:45,020 Ne tro maltrankviliĝu pri tio. 1334 00:55:45,020 --> 00:55:46,620 Do kiel vi diras. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Kiel Jakob diris, kiel do ni konservi trako de kio nia minimuma estas? 1337 00:55:54,406 --> 00:55:55,030 Kiel ni sciu? 1338 00:55:55,030 --> 00:55:57,060 Ni devas kompari ĉio en nia listo. 1339 00:55:57,060 --> 00:55:59,600 >> Do minimuma egalas i. 1340 00:55:59,600 --> 00:56:03,870 Ĝi simple diri en tiu kazo la indico de nia minimuma valoro. 1341 00:56:03,870 --> 00:56:07,660 Tial do tio okazas persisti tra kaj ĝi iras de la j egalas i plus 1. 1342 00:56:07,660 --> 00:56:11,420 Do ni jam scias ke tio estas nia unua elemento. 1343 00:56:11,420 --> 00:56:13,240 Ni ne bezonas kompari ĝin mem. 1344 00:56:13,240 --> 00:56:16,970 Do ni komencu komparante ĝin al la venonta unu kiu estas kial i plus 1 al n 1345 00:56:16,970 --> 00:56:20,110 minus 1, kiu estas la Fine de la tabelo tie. 1346 00:56:20,110 --> 00:56:25,090 Kaj ni diris ke se tabelo cxe j estas malpli ol tabelo min, 1347 00:56:25,090 --> 00:56:29,200 tiam ni religi kie nia minimuma indeksoj estas. 1348 00:56:29,200 --> 00:56:37,470 >> Kaj se min ne estas egala al i, kiel en kie nin reen super tie. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Tiel kiel kiam ni unue faris ĉi tiu. 1351 00:56:41,790 --> 00:56:49,310 En ĉi tiu kazo, ĝi komencus je nulo, ĝi finus estante du. 1352 00:56:49,310 --> 00:56:53,010 Do min ne volis egalaj i en la fino. 1353 00:56:53,010 --> 00:56:55,720 Kiu lasas nin scii ke ni bezonas interŝanĝi ilin. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Mi sentas kiel konkretan ekzemplon helpos multe pli ol tio. 1356 00:57:00,470 --> 00:57:04,970 Do mi devos kodigi tiu kun vi uloj nun mi opinias ke estos pli bona. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Varoj inklinas funkcias tiel en tiu ĝi estas ofte pli bone simple vidi ilin. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Do kion ni volas fari estas ni unue volas la plej malgranda 1361 00:57:17,280 --> 00:57:19,890 elemento en lia pozicio en la tabelo. 1362 00:57:19,890 --> 00:57:21,280 Ĝuste kion Jakob diris. 1363 00:57:21,280 --> 00:57:23,090 Vi devas gardi ke iel. 1364 00:57:23,090 --> 00:57:25,900 Do ni tuj komenci tie ripetanta super la tabelo. 1365 00:57:25,900 --> 00:57:28,970 Ni tuj diras ke nia unue oni nur komence. 1366 00:57:28,970 --> 00:57:38,308 Do ni tuj havos int malgranda egalas tabelo je i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Do unu afero rimarki, ĉiu tempo ĉi buklo ekzekutas, 1369 00:57:45,050 --> 00:57:48,550 Ni komencas unu paŝon antaŭen. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Kiam ni komencos ni rigardu ĉi tiu. 1372 00:57:57,440 --> 00:58:00,840 La venontan fojon ni persisti tra, ni ekde ĉi tiu 1373 00:58:00,840 --> 00:58:02,680 kaj atribuante lin nia malgranda valoro. 1374 00:58:02,680 --> 00:58:10,450 Do ĝi estas tre simila al bobelo speco kie ni scias, ke post unu pasas, 1375 00:58:10,450 --> 00:58:11,700 tiu lasta elemento estas ordigitaj. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Kun selektado speco, ĝi estas ĝuste la malo. 1378 00:58:15,120 --> 00:58:18,950 >> Ĉe ĉiu paŝo, ni scias, ke La unua unu estas ordigitaj. 1379 00:58:18,950 --> 00:58:21,360 Post la dua paŝo, la dua estos ordo. 1380 00:58:21,360 --> 00:58:26,470 Kaj ke vi vidis kun la glito ekzemploj nia ordo parton ĝuste tenas kreskanta. 1381 00:58:26,470 --> 00:58:34,020 Do per opcio niaj plej malgranda al arrays i, ĉio jam estas faranta 1382 00:58:34,020 --> 00:58:37,340 Estas constricting kio ni rigardis tiom kiel 1383 00:58:37,340 --> 00:58:40,164 minimumigi la nombron de komparoj ni faras. 1384 00:58:40,164 --> 00:58:41,770 Ĉu tio havas sencon por ĉiuj? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Ĉu vi bezonas min kuri tra tiu denove malrapidaj aŭ en malsamaj vortoj? 1387 00:58:46,380 --> 00:58:47,180 Mi feliĉas. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 OK. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Do ni stokante la valoro je tiu punkto, 1392 00:58:55,540 --> 00:58:57,840 sed ni ankaŭ volas konservi la indekso. 1393 00:58:57,840 --> 00:59:01,010 Do ni iras por stoki la pozicio de la plej malgranda 1394 00:59:01,010 --> 00:59:02,770 unu, kiu estas ĝuste tuj estos mi. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Do nun Jakob estas kontentigita. 1397 00:59:05,440 --> 00:59:06,870 Ni havas aferojn stokitaj. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 Kaj nun ni bezonas trarigardi la unsorted parto de la tabelo. 1400 00:59:11,870 --> 00:59:18,170 Do en tiu kazo ĉi estus nia unsorted. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Tio estas mi. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 OK. 1405 00:59:26,210 --> 00:59:30,040 >> Do kion ni faros tuj estos por buklo. 1406 00:59:30,040 --> 00:59:32,066 Kiam ajn vi bezonos persisti tra tabelo, 1407 00:59:32,066 --> 00:59:33,440 via menso povus iri por buklo. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Do por iuj int k equals-- Kion ni pensas 1410 00:59:38,090 --> 00:59:39,700 k tuj egalos komenci kun? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Tio estas kion ni starigu kiel nia malgranda valoro kaj ni volas kompari ĝin. 1413 00:59:44,766 --> 00:59:47,090 Kion ni volas kompari ĝin al? 1414 00:59:47,090 --> 00:59:48,730 Ĝi tuj estos tiu proksima, dekstra? 1415 00:59:48,730 --> 00:59:53,200 Do ni volas k esti inicializado i plus 1 por komenci. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> Kaj ni volas k en tiu kazo jam grandeco stokitaj ĝis tie, 1418 01:00:02,800 --> 01:00:03,930 do ni povas simple uzi grandeco. 1419 01:00:03,930 --> 01:00:06,240 Grandeco estas la grandeco de la tabelo. 1420 01:00:06,240 --> 01:00:09,620 Kaj ni volas nur ĝisdatigi k per unu ĉiufoje. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Malvarmeta. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Do nun ni bezonas trovi la plej malgranda elemento tie. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Do se ni persisti tra, ni volas diri, se arangxis antaux k 1427 01:00:31,380 --> 01:00:37,080 estas malpli ol nia malgranda value-- ĉi tiu estas kie ni estas reale 1428 01:00:37,080 --> 01:00:42,950 konservanta trako de kio estas la plej malgranda here-- 1429 01:00:42,950 --> 01:00:47,740 do ni preferas religi kio nia malgranda valoro. 1430 01:00:47,740 --> 01:00:50,645 >> Ĉi tio signifas ke, ho, ni estas ripetanta tra tie. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Ajn valoro estas ĉi tie Ĉu nia malgranda afero. 1433 01:00:53,740 --> 01:00:54,448 Ni ne volas ĝin. 1434 01:00:54,448 --> 01:00:56,100 Ni preferas religi ĝin. 1435 01:00:56,100 --> 01:01:02,050 Do se ni reassigning ĝi, kion fari vi pensas povus esti en tiu kodo tie? 1436 01:01:02,050 --> 01:01:04,160 Ni preferas religi malgranda kaj pozicio. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Do kio estas la plej malgranda nun? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 Student: Array k. 1441 01:01:09,130 --> 01:01:09,963 Instruisto: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 Kaj kia estas pozicio nun? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Kio estas la indicoj de nia malgranda valoro? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Estas nur k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Do tabelo k, k, ili kongruas supren. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Do ni volis religi tio. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 Kaj tiam poste ni trovis nian malgranda, tial al la fino de ĉi por buklo 1454 01:01:39,950 --> 01:01:45,100 tie ni trovis kion nia malgranda valoro, do ni simple interŝanĝi ĝin. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 En tiu kazo, kiel diras nia malgranda valoro estas el cxi tie. 1457 01:01:50,816 --> 01:01:51,940 Tio estas nia malgranda valoro. 1458 01:01:51,940 --> 01:01:57,690 >> Ni nur volas interŝanĝi ĝin ĉi tie, kiu estas kion tio swap funkcio ĉe la malsupro 1459 01:01:57,690 --> 01:02:01,270 faris, kion ni ĵus redaktis kune paro minutoj. 1460 01:02:01,270 --> 01:02:02,775 Do ĝi devus rigardi familiara. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 Kaj tiam ĝi nur persisti tra ĝis ĝi atingas la tutan vojon 1463 01:02:08,030 --> 01:02:13,100 al la fino, kio signifas, ke vi havas nulo elementoj kiuj unsorted 1464 01:02:13,100 --> 01:02:14,800 kaj ĉio alia estas ordigitaj. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Sencon? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Iom pli konkrete? 1469 01:02:19,280 --> 01:02:19,990 La kodo helpon? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> Student: Por grandecon, Vi neniam vere difini ĝin aŭ ŝanĝi ĝin, 1472 01:02:26,410 --> 01:02:27,340 kiel faras ĝi scias? 1473 01:02:27,340 --> 01:02:32,380 >> Instruisto: Do ​​unu afero rimarki ĝis tie estas int grandeco. 1474 01:02:32,380 --> 01:02:35,680 Do ni diris en ĉi sort-- speco estas funkcio en ĉi case-- estas 1475 01:02:35,680 --> 01:02:40,770 selektado speco, ĝi estas pasinta en la funkcio. 1476 01:02:40,770 --> 01:02:43,460 Do se oni ne pasis , vi povus fari ion 1477 01:02:43,460 --> 01:02:47,840 kiel kun la longo de la tabelo alie vi persisti tra 1478 01:02:47,840 --> 01:02:49,390 trovi la longo. 1479 01:02:49,390 --> 01:02:52,680 Sed ĉar ĝi pasis en, ni povas simple uzi ĝin. 1480 01:02:52,680 --> 01:02:55,720 Vi nur supozi ke la uzanto donis al vi validan grandeco kiu 1481 01:02:55,720 --> 01:02:57,698 efektive reprezentas grandecon de via tabelo. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Cool? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Se vi uloj havas problemojn kun tiuj aŭ volas pli oportuna kodigo specoj 1486 01:03:05,870 --> 01:03:08,050 sur via propra, Vi devus iru study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Ĝi estas ilo. 1489 01:03:12,670 --> 01:03:15,040 Ili havas Kontrolilo ke Vi povas fakte skribi. 1490 01:03:15,040 --> 01:03:16,180 Ili faras _pseudocode_. 1491 01:03:16,180 --> 01:03:19,310 Ili havas pli videoj kaj diapozitivoj inkludante tiujn mi uzas tie. 1492 01:03:19,310 --> 01:03:23,150 Do se vi ankoraŭ sentas iom nebula, provu tion diveni. 1493 01:03:23,150 --> 01:03:25,670 Kiel ĉiam, venis paroli al mi ankaŭ. 1494 01:03:25,670 --> 01:03:26,320 Demando? 1495 01:03:26,320 --> 01:03:28,611 >> Lernanto: Ĉu vi diras la grandeco estas difinita antaŭe? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 Instruisto: Jes. 1498 01:03:29,900 --> 01:03:35,570 Grandeco estas antaŭe difinita supren tie en la funkcio deklaro. 1499 01:03:35,570 --> 01:03:39,060 Do vi supozas ke ĝi estas estis pasita en de la uzanto, kaj pro simpleco kaj pro 1500 01:03:39,060 --> 01:03:41,896 Ni tuj supozi ke la uzanto donis al ni la ĝustan grandecon. 1501 01:03:41,896 --> 01:03:43,240 Malvarmeta. 1502 01:03:43,240 --> 01:03:44,390 Do tio estas selektado varo. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Knaboj, mi scias ni lernas multe hodiaŭ. 1505 01:03:47,640 --> 01:03:49,710 Ĝi estas densa datumoj por sekcio. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Do kun tio, ni iras iri inserción varo. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> OK. 1510 01:04:02,510 --> 01:04:06,100 Tiel, ke ni devas fari nia runtime analizo tie. 1511 01:04:06,100 --> 01:04:10,190 Do, en la plej bona kazo, donita de kiam mi montris al vi 1512 01:04:10,190 --> 01:04:11,960 la tablon mi jam ia donis gxin. 1513 01:04:11,960 --> 01:04:15,430 Sed bona kazo ekzekuto, kion ni pensas? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Ĉiu ordo. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N kvadrato. 1518 01:04:22,070 --> 01:04:24,780 Ĉiu havas klarigon Kial vi opinias? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> Student: Vi komparante through-- 1521 01:04:30,519 --> 01:04:31,268 Instruisto: Ĝuste. 1522 01:04:31,268 --> 01:04:32,540 Vi komparas tra. 1523 01:04:32,540 --> 01:04:35,630 Ĉe ĉiu ripeto, kvankam ni decrementing ĉi lauxvice, 1524 01:04:35,630 --> 01:04:38,950 vi ankoraŭ trasercxante ĉion por trovi la plej malgranda. 1525 01:04:38,950 --> 01:04:42,390 Do eĉ se via malgranda valoro estas tie en la komenco, 1526 01:04:42,390 --> 01:04:44,710 vi ankoraŭ kompari ĝin kontraŭ ĉiu alia 1527 01:04:44,710 --> 01:04:46,550 certigi ĝi estas la plej malgranda afero. 1528 01:04:46,550 --> 01:04:49,820 Do vi finos kurante tra proksimume n kvadratoj fojojn. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Bone. 1531 01:04:51,590 --> 01:04:52,785 Kaj kio estas la plej malbona kazo? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Ankaŭ n kvadratoj ĉar vi iras esti farante tiu sama proceduro. 1534 01:04:57,980 --> 01:05:01,670 Do en ĉi tiu kazo, selektado varo havas ion 1535 01:05:01,670 --> 01:05:04,010 ke ni ankaŭ nomas atendita ekzekuto. 1536 01:05:04,010 --> 01:05:07,400 Do, en la aliaj, ni nur scias la supra kaj malsupra limoj. 1537 01:05:07,400 --> 01:05:11,180 Dependanta sur kiel freneza nia lerta estas aŭ kiom unsorted estas, 1538 01:05:11,180 --> 01:05:15,350 ili varias inter n aŭ n kvadratoj. 1539 01:05:15,350 --> 01:05:16,550 Ni ne scias. 1540 01:05:16,550 --> 01:05:22,820 >> Sed ĉar selektado varo havas la saman plej malbona kaj plej bona kazo, kiu nin diras ke 1541 01:05:22,820 --> 01:05:25,880 negrave kio tipo de eniro nin havi, ĉu ĝi estas tute 1542 01:05:25,880 --> 01:05:29,130 ordo aŭ tute inversigi ordo, estas 1543 01:05:29,130 --> 01:05:30,740 tuj prenos la sama kvanto de tempo. 1544 01:05:30,740 --> 01:05:33,760 Do en tiu kazo, se vi memoras el nia tablo 1545 01:05:33,760 --> 01:05:38,610 Ĝi efektive havis valoron kiu tiuj du specoj ne havas, 1546 01:05:38,610 --> 01:05:40,390 kio estas atendita ekzekuto. 1547 01:05:40,390 --> 01:05:43,350 Do ni scias ke kiam ajn Ni kuras selektado speco, 1548 01:05:43,350 --> 01:05:45,380 ĝi estas garantiita kuri n kvadratoj tempo. 1549 01:05:45,380 --> 01:05:46,630 Ne estas variebleco tie. 1550 01:05:46,630 --> 01:05:47,630 Estas nur atendis. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 Kaj denove, se vi volas lerni pli, kaptu CS 124 en la printempo. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Bone. 1555 01:05:56,712 --> 01:05:57,545 Ni vidis ĉi tiun. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Malvarmeta. 1558 01:05:59,030 --> 01:06:00,930 Do inserción varo. 1559 01:06:00,930 --> 01:06:03,330 Kaj mi verŝajne iros al Blaze tra tiu. 1560 01:06:03,330 --> 01:06:05,440 Mi ne havas vi uloj programi ĝin. 1561 01:06:05,440 --> 01:06:06,580 Ni simple marŝi tra ĝi. 1562 01:06:06,580 --> 01:06:10,500 Do inserción varo estas afabla simile al selektado speco 1563 01:06:10,500 --> 01:06:14,460 cxar ni havas ambaŭ la unsorted kaj ordigitaj parto de la tabelo. 1564 01:06:14,460 --> 01:06:20,260 >> Sed kio estas malsama estas ke kiel ni trairi unu post la alia: 1565 01:06:20,260 --> 01:06:24,210 ni simple prenas kion ajn nombro estas apud niaj unsorted, 1566 01:06:24,210 --> 01:06:28,507 kaj ĝuste ordigi ŝin en nian ordo tabelo. 1567 01:06:28,507 --> 01:06:30,090 Ĝi faros pli sentita kun ekzemplo. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Do ĉio komenciĝas kiel unsorted, nur ŝatas kun selektado varo. 1570 01:06:35,430 --> 01:06:38,740 Kaj ni tuj ordigi tion en supreniranta ordon kiel ni. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Do en nia unua paŝo Ni prenu la unua valoro 1573 01:06:43,340 --> 01:06:46,700 kaj ni diru, bone, vi estas nun en lerta sola. 1574 01:06:46,700 --> 01:06:49,150 >> Ĉar vi estas en lerta de vi mem, vi estas ordo. 1575 01:06:49,150 --> 01:06:52,460 Gratulojn por esti la unua ero en tiu tabelo. 1576 01:06:52,460 --> 01:06:54,800 Vi jam ordigitaj ĉiuj sur via propra. 1577 01:06:54,800 --> 01:06:58,900 Do nun ni estas ordo kaj unsorted tabelo. 1578 01:06:58,900 --> 01:07:01,760 Do nun ni prenu la unuan. 1579 01:07:01,760 --> 01:07:05,600 Kio okazas inter tie kaj jen, kion ni diras, 1580 01:07:05,600 --> 01:07:08,890 OK, ni iras por rigardi la unua valoro de nia unsorted tabelo 1581 01:07:08,890 --> 01:07:13,270 kaj ni iras enigi ĝin en lia ĝusta loko en la ordo tabelo. 1582 01:07:13,270 --> 01:07:21,460 >> Do kion ni faras estas ni prenas 5 Ni diru, OK, 5 estas pli granda ol 3, 1583 01:07:21,460 --> 01:07:24,630 do ni nur insertarlo dekstra dekstre de tio. 1584 01:07:24,630 --> 01:07:25,130 Ni estas bonaj. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Do tiam ni veturos al nia proksima. 1587 01:07:28,420 --> 01:07:29,720 Kaj ni prenos 2. 1588 01:07:29,720 --> 01:07:34,330 Ni diras, OK, 2 estas malpli ol 3, do ni scias ke ĝi 1589 01:07:34,330 --> 01:07:36,220 bezonas esti en la antaŭ nia listo nun. 1590 01:07:36,220 --> 01:07:41,800 Do kion ni faras estas ni puŝi 3 kaj 5 malsupren kaj ni movas 2 en tiu unua fendo. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Do ni nur enigante ĝin en la ĝusta loko devus esti. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Tiam ni rigardas nian proksima, kaj ni diru 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 estas pli granda ol ĉio en nia ordo tabelo, 1596 01:07:53,620 --> 01:07:56,000 do ni nur marki ĝin sur la fino. 1597 01:07:56,000 --> 01:07:56,960 Kaj tiam ni rigardas 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 estas malpli ol 6, estas malpli ol 5 sed estas pli granda ol 3. 1600 01:08:03,020 --> 01:08:06,270 Do ni nur insertarlo rekte en meze inter 3 kaj 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Do fari tiun iom iom pli konkretaj, 1603 01:08:10,530 --> 01:08:12,280 jen speco de ideon pri kio okazis. 1604 01:08:12,280 --> 01:08:16,430 Do por ĉiu unsorted elemento, ni determini kie en la ordo parto 1605 01:08:16,430 --> 01:08:17,090 estas. 1606 01:08:17,090 --> 01:08:20,680 >> Do konsiderante la ordo kaj unsorted, 1607 01:08:20,680 --> 01:08:26,080 ni devas trairi tra kaj figuro el kie ĝi persvadas en la ordo tabelo. 1608 01:08:26,080 --> 01:08:31,460 Kaj ni enŝovu ĝin movante la elementoj dekstren de ĝi malsupren. 1609 01:08:31,460 --> 01:08:34,910 Kaj tiam ni simple teni ripetanta tra ĝis ni 1610 01:08:34,910 --> 01:08:39,270 havas tute ordigita listo kie unsorted nun nulo 1611 01:08:39,270 --> 01:08:41,720 kaj ordigitaj okupas la tuteco de nia listo. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Do, denove, por fari aferojn eĉ pli konkreta, ni havas _pseudocode_. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Do esence por i estas egala al 0 por n minus 1 1616 01:08:52,410 --> 01:08:54,790 tio estas nur la longon de nia tabelo. 1617 01:08:54,790 --> 01:09:00,979 Ni havas elementon kiu estas egala al la unua tabelo aŭ la unuajn indicojn. 1618 01:09:00,979 --> 01:09:03,200 Ni starigu j egala al tio. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Do dum la j estas pli granda ol nulo kaj la tabelo, j minus 1 1621 01:09:09,210 --> 01:09:11,660 estas pli granda ol la elemento, tial ĉio tio, kio faras 1622 01:09:11,660 --> 01:09:17,479 estas certigi ke via j vere reprezentas 1623 01:09:17,479 --> 01:09:20,010 la unsorted parto de la tabelo. 1624 01:09:20,010 --> 01:09:30,745 >> Do dum estas ankoraŭ tion ordigi kaj j minus unu is-- kio 1625 01:09:30,745 --> 01:09:31,840 estas la elemento sxi? 1626 01:09:31,840 --> 01:09:34,760 J neniam difinis tie. 1627 01:09:34,760 --> 01:09:35,677 Estas speco de ĝena. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 Anyways. 1630 01:09:36,689 --> 01:09:39,899 Do j minus 1, vi kontrolanta la elemento antaŭ ĝi. 1631 01:09:39,899 --> 01:09:46,460 Vi diras: Bone, estas la elemento antaŭ kien mi am-- ni 1632 01:09:46,460 --> 01:09:47,540 efektive desegni ĉi ekstere. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Tiel diru ĉi estas kiel sur nia dua pass. 1635 01:09:56,830 --> 01:09:59,525 Do mi tuj estos egalaj 1, kiu estas tie. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Do mi tuj estos egala al 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Tiu estus 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Bone. 1642 01:10:16,750 --> 01:10:20,945 Do nia ero en tiu kazo tuj estos egala al 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 Kaj ni havas kelkajn j tio tuj estos egala al 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Ho, j decrementing. 1647 01:10:30,971 --> 01:10:31,720 Tio estas kion ĝi estas. 1648 01:10:31,720 --> 01:10:35,680 Do j estas egala al i, do kia estas parolo estas kiu kiel ni movas antaŭen, 1649 01:10:35,680 --> 01:10:37,530 Ni nur certigi ke ni ne estas sur 1650 01:10:37,530 --> 01:10:43,520 indeksante tiu maniero kiam ni provas enmeti tion en nian ordo listo. 1651 01:10:43,520 --> 01:10:49,850 >> Do kiam j estas egala al 1 en tiu kazo kaj tabelo j minus one-- tia tabelo j minus 1 1652 01:10:49,850 --> 01:10:54,610 estas 2 en ĉi case-- se tio granda ol la elemento, 1653 01:10:54,610 --> 01:10:57,700 tiam cxio tio faras estas movanta aferojn suben. 1654 01:10:57,700 --> 01:11:04,790 Do en ĉi tiu kazo, tabelo j minus unu estus tabelo nulo, kiu estas 2. 1655 01:11:04,790 --> 01:11:08,430 2 estas ne pli granda ol 4 tial ĉi ne ekzekuti. 1656 01:11:08,430 --> 01:11:11,460 Do la movo ne moviĝas suben. 1657 01:11:11,460 --> 01:11:18,790 Kion tiu faras ĉi tie estas nur movanta via ordo tabelo suben. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 En tiu kazo, fakte, ni povus do-- ni faru ĉi 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Do se ni estos marŝi per ĉi tiu ekzemplo, ni estas nun ĉi tie. 1662 01:11:31,970 --> 01:11:32,740 Tiu estas ordigitaj. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Tio estas unsorted. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Cool? 1667 01:11:39,860 --> 01:11:46,620 Do i estas egala al 2, do nia elemento egalas al 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 Kaj niajn j estas egala al 2. 1670 01:11:52,270 --> 01:12:00,620 Do ni trarigardu kaj ni diras, OK, estas tabelo j minus unu 1671 01:12:00,620 --> 01:12:03,470 granda ol la elemento ke ni rigardas? 1672 01:12:03,470 --> 01:12:05,540 Kaj la respondo estas jes, ĉu ne? 1673 01:12:05,540 --> 01:12:11,275 4 estas pli granda ol 3 kaj j estas 2, tial tiu kodo ekzekutas. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Do kion ni faru tabelo cxe 2, do ĉi tie, ni interŝanĝas ilin. 1676 01:12:18,550 --> 01:12:25,620 Tial ni diras, OK, tabelo je 2 estas nun tuj estos 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 Kaj j tuj egalos j minus 1, kiu estas 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Tio estas terura, sed vi uloj akiras la ideon. 1681 01:12:37,200 --> 01:12:38,360 J estas nun egala al 1. 1682 01:12:38,360 --> 01:12:44,360 Kaj batalarangxis j ĝuste tuj estos egala al nia elemento, kiu estis 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Mi viŝis ion mi neutilas havi aŭ miswrote ion, 1685 01:12:48,570 --> 01:12:49,910 sed vi uloj akiras la ideon. 1686 01:12:49,910 --> 01:12:50,640 >> Ĝi moviĝas n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 Kaj tiam se tio estis, tio farus maŝo denove kaj ĝi dirus, OK, j estas 1 nun. 1689 01:12:57,960 --> 01:13:00,665 Kaj batalarangxis j minus 1 nun estas 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 Estas 2 malpli ol nia ero? 1692 01:13:03,760 --> 01:13:04,540 Neniu? 1693 01:13:04,540 --> 01:13:07,970 Tio signifas, ke ni enmetita ĉi ero 1694 01:13:07,970 --> 01:13:10,110 en la ĝusta loko en nia ordo tabelo. 1695 01:13:10,110 --> 01:13:14,400 Tiam ni povas preni tion kaj ni diru, OK, nia ordo tabelo estas tie. 1696 01:13:14,400 --> 01:13:19,940 Kaj ĝi prenus tiu numero 6 kaj estu kiel, nu bone, estas 6 malpli ol tiu nombro? 1697 01:13:19,940 --> 01:13:20,480 Neniu? 1698 01:13:20,480 --> 01:13:21,080 Malvarmeta. 1699 01:13:21,080 --> 01:13:22,680 Ni estas fajna. 1700 01:13:22,680 --> 01:13:23,530 >> Faru tion refoje. 1701 01:13:23,530 --> 01:13:24,740 Ni diru 7. 1702 01:13:24,740 --> 01:13:29,010 Estas 7 malpli ol la fino de nia ordo tabelo? 1703 01:13:29,010 --> 01:13:29,520 No. 1704 01:13:29,520 --> 01:13:30,430 Do ni estas fajna. 1705 01:13:30,430 --> 01:13:32,760 Do tiu estus ordo. 1706 01:13:32,760 --> 01:13:38,610 Esence ĉiu ĉi tio Estas ĝi estas jene take 1707 01:13:38,610 --> 01:13:42,060 La unua elemento de via unsorted tabelo, 1708 01:13:42,060 --> 01:13:46,010 elŝeligi kie eliras en via ordo tabelo. 1709 01:13:46,010 --> 01:13:48,780 Kaj tiu nur prizorgas de interŝanĝojn fari tion. 1710 01:13:48,780 --> 01:13:51,300 Vi esence nur interŝanĝante ĝis ĝi estas en la dekstra loko. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 La vida bildo estas ke vi estas movante ĉio malsupren de faranta tion. 1713 01:13:56,990 --> 01:13:59,420 >> Tiel estas kiel duono bobelo speco-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Check out studo 50. 1716 01:14:03,420 --> 01:14:06,000 Mi forte rekomendas provi kodigi tion en via propra. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Se vi havas ajnajn demandojn aux volas vidi specimenon kodo por inserción varon, 1719 01:14:12,450 --> 01:14:13,750 bonvolu sciigi min. 1720 01:14:13,750 --> 01:14:14,500 Mi estas ĉiam ĉirkaŭ. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Do plej malbona kazo runtime kaj bona kazo ekzekuto. 1723 01:14:20,200 --> 01:14:30,700 Kiel knabo vidis el la tablo mi jam montris al vi, ĝi estas ambaŭ n kvadrato kaj n. 1724 01:14:30,700 --> 01:14:35,590 >> Do ia ekpaŝis kion ni parolis pri niaj antaŭaj varoj, plej malbona 1725 01:14:35,590 --> 01:14:38,760 kazo ekzekuto estas ke se ĝi estas tute unsorted, 1726 01:14:38,760 --> 01:14:42,530 ni devas kompari ĉiuj tiuj n fojojn. 1727 01:14:42,530 --> 01:14:47,020 Ni faras tuta loto de komparoj ĉar se ĝi estas en inversa ordo, 1728 01:14:47,020 --> 01:14:50,360 Ni tuj diru, bone, tio estas la sama, tio estas bona; 1729 01:14:50,360 --> 01:14:54,650 kaj ĉi tiu devos esti komparitaj kontraŭ la unua unu por esti movita reen. 1730 01:14:54,650 --> 01:14:56,710 Kaj kiam ni atingos al la vosto fino, ni havas 1731 01:14:56,710 --> 01:14:59,440 kompari, kompari, kaj kompari kontraŭ ĉiu. 1732 01:14:59,440 --> 01:15:03,030 >> Do ĝi finas estante proksimume n kvadratoj. 1733 01:15:03,030 --> 01:15:09,510 Se ĝi estas korekta tiam vi diras, OK, 2, vi estas bona. 1734 01:15:09,510 --> 01:15:11,330 3, vi komparis al 2. 1735 01:15:11,330 --> 01:15:12,310 Vi estas bona. 1736 01:15:12,310 --> 01:15:14,150 4, vi simple komparas al la vosto. 1737 01:15:14,150 --> 01:15:14,990 Vi estas bona. 1738 01:15:14,990 --> 01:15:17,140 6, komparu al la vosto, vi estas bela. 1739 01:15:17,140 --> 01:15:20,870 Do por ĉiu punkto se ĝi estas jam ordigataj vi farante komparon. 1740 01:15:20,870 --> 01:15:22,320 Do estas nur n. 1741 01:15:22,320 --> 01:15:26,840 Kaj ĉar ni havas bonan kazon runtime de n kaj plej malbona kazo runtime de n 1742 01:15:26,840 --> 01:15:28,680 kvadrato, ni ne havas atenditan ekzekuto. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Ĝi nur dependas de la ĥaoso de nia listo tie. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 Kaj ankaux alia grafikaĵo kaj alia tablo. 1747 01:15:39,530 --> 01:15:41,170 Do diferencoj inter varoj. 1748 01:15:41,170 --> 01:15:44,180 Mi nur tuj brizo, Mi sentas kiel ni parolis vaste 1749 01:15:44,180 --> 01:15:46,570 pri kio ili ĉiuj speco de varias kaj ligas kune. 1750 01:15:46,570 --> 01:15:50,564 Do merge varo estas la lasta Mi trapiku vi uloj kun. 1751 01:15:50,564 --> 01:15:52,105 Ni havas belan pitoreskan bildon. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Do kunfandi varo estas rekursia algoritmo. 1754 01:15:56,040 --> 01:15:59,910 Do ĉu vi uloj scias kion rekursia funkcio estas? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Iu volas diri? 1757 01:16:03,320 --> 01:16:04,739 Vi volas provi? 1758 01:16:04,739 --> 01:16:07,280 Do rekursia funkcio estas nur funkcio kiu nomas sin. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Do se vi uloj estas familiara kun la Fibonaĉi sinsekvo, 1761 01:16:11,590 --> 01:16:15,670 kiuj estas konsiderataj rekursiaj ĉar vi prenos la du antaŭaj 1762 01:16:15,670 --> 01:16:17,530 kaj aldoni ilin kune akiri vian proksima. 1763 01:16:17,530 --> 01:16:21,440 Do rekursie, mi ĉiam pensas de rikuro kiel kiel spirala 1764 01:16:21,440 --> 01:16:24,430 tial vi estas kiel kirliĝas en gxin. 1765 01:16:24,430 --> 01:16:27,150 Sed estas nur funkcio kiu nomas sin. 1766 01:16:27,150 --> 01:16:32,660 >> Kaj, efektive, vere rapide mi povas montri vin kion tio aspektas. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Do rekursiaj tie, se ni rigardas, estas la rekursiaj maniero sumo super tabelo. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Do ĉio, kion ni faras estas ni havos sum funkcio 1771 01:16:47,880 --> 01:16:52,210 sumo kiu prenas grandecon kaj tabelo. 1772 01:16:52,210 --> 01:16:55,210 Se vi rimarkas, grandeco dekrementojn per unu ĉiufoje. 1773 01:16:55,210 --> 01:17:00,365 Kaj ĉiuj faras estas se x egalas al zero-- do se la grandeco de la tabelo 1774 01:17:00,365 --> 01:17:02,710 egalas zero-- revenas nulo. 1775 01:17:02,710 --> 01:17:10,440 >> Alie ĝi resumas ĉi lasta ero de la matrico, 1776 01:17:10,440 --> 01:17:14,790 kaj tiam prenas sumo de la resto de la tabelo. 1777 01:17:14,790 --> 01:17:17,555 Do ĝi estas nur rompas ĝin malsupren en malgrandaj kaj pli malgrandaj problemoj. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Longan rakonton, rekursio, Funkcio kiu nomas sin. 1780 01:17:21,890 --> 01:17:25,740 Se tio estas ĉio vi eliris el tiu, ke estas kion rekursia funkcio estas. 1781 01:17:25,740 --> 01:17:29,870 Se vi prenos la 51, vi ricevos tre, tre komforta kun rekursio. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Estas vere malvarmeta. 1784 01:17:32,370 --> 01:17:34,660 Ĝi taŭgis je ŝatas 3 AM nokto eksteren. 1785 01:17:34,660 --> 01:17:37,900 Kaj mi, kiel, kial Mi neniam uzas tion? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Do por merge varon, esence kio okazos al fari estas ĝi estas 1788 01:17:42,430 --> 01:17:45,620 tuj rompos ĝin kaj rompi ĝin boli ĝis ĝi estas nur sola elementoj. 1789 01:17:45,620 --> 01:17:47,570 La sola elementoj estas facile ordigi. 1790 01:17:47,570 --> 01:17:48,070 Ni vidas tion. 1791 01:17:48,070 --> 01:17:50,760 Se vi havas unu elemento, estas jam konsiderita ordo. 1792 01:17:50,760 --> 01:17:53,800 Ktp enigaĵoj de n elementoj, se n estas malpli ol 2, 1793 01:17:53,800 --> 01:17:58,120 nur reveni ĉar tio signifas ĝi estas ĉu 0 aŭ 1, kiel ni vidis. 1794 01:17:58,120 --> 01:18:00,050 Tiuj estas konsideritaj ordigitaj elementoj. 1795 01:18:00,050 --> 01:18:02,170 >> Alie rompi ĝin en duono. 1796 01:18:02,170 --> 01:18:06,336 Ordigi la unua duono, ordigi la dua duono, kaj poste kunigi ilin kune. 1797 01:18:06,336 --> 01:18:07,460 Kial ĝi nomiĝas merge varo. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Do ni havas ĉi tie ni ordigi tiujn. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Do ni observas havante ilin ĝis la tabelo esas 1. 1802 01:18:17,210 --> 01:18:20,790 Do kiam estas 1, ni simple reveni ĉar tiu estas ordo tabelo, 1803 01:18:20,790 --> 01:18:23,940 kaj jen ia ordo tabelo, kaj tio estas kun ordo tabelo, ni ĉiuj ordo. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Do kion ni faras estas ni komenci kunfandi ilin kune. 1806 01:18:29,420 --> 01:18:31,820 >> Do kiel vi povas pensi fandado estas 1807 01:18:31,820 --> 01:18:36,240 vi simple forigu la malgrandaj numeron de ĉiu de la sub arrays 1808 01:18:36,240 --> 01:18:38,330 kaj ĝuste alfiksus ĝin al la emerĝis tabelo. 1809 01:18:38,330 --> 01:18:44,290 Do se vi rigardas tie, kiam ni havas tiuj aroj ni havas 4, 6, kaj 1. 1810 01:18:44,290 --> 01:18:47,280 Kiam ni volas kunfandi tiujn, Ni rigardu tiuj du unuaj 1811 01:18:47,280 --> 01:18:50,730 kaj ni diru, OK, 1 estas malgranda, iras al la fronto. 1812 01:18:50,730 --> 01:18:54,330 4 kaj 6, estas nenio kompari ĝin, nur marki ĝin sur la fino. 1813 01:18:54,330 --> 01:18:58,020 >> Kiam ni kombini tiujn du, ni simple preni la plej malgranda el tiuj du, 1814 01:18:58,020 --> 01:18:59,310 do estas 1. 1815 01:18:59,310 --> 01:19:01,690 Kaj nun ni prenu la malgranda de ĉi tiuj du, do 2. 1816 01:19:01,690 --> 01:19:03,330 Malgranda de ĉi tiuj du, 3. 1817 01:19:03,330 --> 01:19:06,260 Malgranda de ĉi tiuj du, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Do vi simple tirante ekstere tiujn. 1819 01:19:08,630 --> 01:19:11,210 Kaj ĉar ili jam solviĝis antaŭe, 1820 01:19:11,210 --> 01:19:14,300 vi nur havas unu komparo ĉiu tempo. 1821 01:19:14,300 --> 01:19:19,610 Do pli kodo tien, simple prezento. 1822 01:19:19,610 --> 01:19:24,410 Do vi komencas je la mezo kaj vi speco maldekstren kaj dekstren 1823 01:19:24,410 --> 01:19:26,180 kaj tiam vi nur kunfandi tiujn. 1824 01:19:26,180 --> 01:19:30,080 >> Kaj ni ne havas kodon por kunfandi ĉi tie. 1825 01:19:30,080 --> 01:19:34,110 Sed, denove, se vi iros en studi 50, ĝi estos tie. 1826 01:19:34,110 --> 01:19:36,860 Alie veni alparolas min Se vi ankoraŭ konfuzita. 1827 01:19:36,860 --> 01:19:42,340 Tiel malvarmeta afero estas, ke plej bona kazo, plej malbona kazo, kaj atendita ekzekuto 1828 01:19:42,340 --> 01:19:46,250 estas ĉiuj en log n, kiu estas multe pli bona ol ni 1829 01:19:46,250 --> 01:19:48,000 viditaj dum la resto de niaj varoj. 1830 01:19:48,000 --> 01:19:51,840 Ni vidis n kvadratoj kaj kion ni reale 1831 01:19:51,840 --> 01:19:54,380 tien estas n logo n, kiu estas granda. 1832 01:19:54,380 --> 01:19:55,830 >> Rigardu kiom bone tio estas. 1833 01:19:55,830 --> 01:19:56,780 Tia bela kurbo. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Tiom pli eficiente. 1836 01:20:00,120 --> 01:20:03,510 Se vi iam povos, uzo kunfandi varo. 1837 01:20:03,510 --> 01:20:04,810 Ĝi savos vin tempo. 1838 01:20:04,810 --> 01:20:07,670 Tiam denove, kiel ni diris, se vi malsupren en tiu malsupra regiono, 1839 01:20:07,670 --> 01:20:09,480 ne fari tiun multe de diferenco. 1840 01:20:09,480 --> 01:20:11,360 Vi korpigi al miloj kaj miloj de enigoj, 1841 01:20:11,360 --> 01:20:13,318 vi certe volas pli kompetenta algoritmo. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 Kaj, denove, nia bela tablo de ĉiuj varoj kiujn vi uloj lernis hodiaŭ. 1844 01:20:19,400 --> 01:20:21,157 >> Do mi konas jam pasis densa tago. 1845 01:20:21,157 --> 01:20:23,490 Tio ne nepre por helpi vin kun via pset. 1846 01:20:23,490 --> 01:20:28,250 Sed mi nur volas fari malgarantio tiu sekcio ne estas nur cxirkaux psets. 1847 01:20:28,250 --> 01:20:31,240 Ĉio ĉi materialo estas bela Ludo por via midterms. 1848 01:20:31,240 --> 01:20:35,430 Kaj ankaŭ se vi faras daŭrigi kun CS, Tio estas vere gravaj fundamentoj 1849 01:20:35,430 --> 01:20:37,870 ke vi bezonas scii. 1850 01:20:37,870 --> 01:20:41,700 Do kelkaj tagoj estos Iom pli pset helpo, 1851 01:20:41,700 --> 01:20:44,600 sed kelkaj semajnoj estos multe pli efektiva enhavo 1852 01:20:44,600 --> 01:20:46,600 ke ne sxajnu súper utila al vi nun, 1853 01:20:46,600 --> 01:20:51,215 sed mi promesas, se vi daŭre sur estos tre, tre utila. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> Do tio estas por sekcio. 1856 01:20:54,250 --> 01:20:55,250 Malsupren al la drato. 1857 01:20:55,250 --> 01:20:56,570 Mi faris gxin interne de unu minuto. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Sed vi iru. 1860 01:20:58,970 --> 01:21:01,240 Kaj mi havos benjetoj aŭ dolĉaĵoj. 1861 01:21:01,240 --> 01:21:03,464 Ĉu iu alergia al io, sur la vojo? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Ovoj kaj lakto. 1864 01:21:05,890 --> 01:21:08,120 Do benjetoj estas ne? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 OK. 1867 01:21:10,160 --> 01:21:10,770 Bone. 1868 01:21:10,770 --> 01:21:12,120 Ĉokolado ne? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts estas bonaj. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 Ni tuj devos Starburst venontan semajnon poste. 1874 01:21:17,045 --> 01:21:18,240 Tio estas kion mi akiras. 1875 01:21:18,240 --> 01:21:19,690 Vi ĉiuj havas grandan semajnon. 1876 01:21:19,690 --> 01:21:20,460 Legu vian spec. 1877 01:21:20,460 --> 01:21:22,130 >> Sciigi min se vi havas demandojn. 1878 01:21:22,130 --> 01:21:25,300 Pset du kvalifikoj devus esti al Vi per ĵaŭdo. 1879 01:21:25,300 --> 01:21:28,320 Se vi havas ajnajn demandojn pri kio mi gradita ion 1880 01:21:28,320 --> 01:21:32,250 kaj kial mi gradita io kia mi ne, bonvolu retmesaĝi al mi, venu paroli kun mi. 1881 01:21:32,250 --> 01:21:34,210 Mi estas iomete freneza ĉi semajno, sed mi promesas 1882 01:21:34,210 --> 01:21:36,340 Mi ankoraŭ respondi ene de 24 horoj. 1883 01:21:36,340 --> 01:21:38,240 Do havi grandan semajno, cxiu. 1884 01:21:38,240 --> 01:21:40,090 Bonŝancon en via pset. 1885 01:21:40,090 --> 01:21:41,248