1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> Spreker 1: Hey almal! 3 00:00:12,300 --> 00:00:13,890 Welkom terug na afdeling. 4 00:00:13,890 --> 00:00:17,480 So bly so baie van julle albei hier om te sien, en almal wat aanlyn kyk. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 So, soos gewoonlik welkom terug. 7 00:00:20,920 --> 00:00:24,360 Ek hoop dat julle almal het 'n pragtige naweek, vol rus, ontspanning. 8 00:00:24,360 --> 00:00:26,026 Dit was 'n pragtige uit gister. 9 00:00:26,026 --> 00:00:27,525 So, ek hoop jy geniet die buitelug. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> So eers 'n paar van die aankondiging. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Gradering. 14 00:00:32,700 --> 00:00:37,350 So, moet die meeste van julle gekry het 'n e-pos van my oor jou Scratch Pset, 15 00:00:37,350 --> 00:00:39,920 sowel as die formaat vir Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 So, net 'n paar dinge. 18 00:00:42,220 --> 00:00:45,150 Maak seker dat jy check50 te gebruik in style50. 19 00:00:45,150 --> 00:00:47,250 Dit is bedoel om te wees hulpbronne vir julle, 20 00:00:47,250 --> 00:00:50,660 om seker te maak dat jy kry maak soveel punte as wat jy kan 21 00:00:50,660 --> 00:00:52,390 sonder onnodig verloor het. 22 00:00:52,390 --> 00:00:54,407 So, dinge soos styl is baie belangrik. 23 00:00:54,407 --> 00:00:55,740 Ons gaan om af te neem, want dit. 24 00:00:55,740 --> 00:00:58,115 Sommige van julle kan reeds opgemerk dat van jou Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 En check50 is net 'n baie maklike manier om seker te maak 27 00:01:01,450 --> 00:01:05,050 dat ons eintlik is terug wat moet teruggestuur word aan die gebruiker, 28 00:01:05,050 --> 00:01:06,690 en dat alles is goed werk. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Op die tweede noot, maak seker dat jou oplaai dinge aan die korrekte gids. 31 00:01:12,040 --> 00:01:14,470 Dit maak my lewe net 'n bietjie meer moeilik 32 00:01:14,470 --> 00:01:18,836 As jy Pset 2 oplaai in Pset 1 want toe ek aflaai dinge, 33 00:01:18,836 --> 00:01:20,085 hulle nie korrek laai. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 En ek weet dit is 'n bietjie onstabiel in 'n stelsel om gewoond te raak aan, 36 00:01:24,560 --> 00:01:26,950 maar net super wees versigtig, al is dit net vir my, 37 00:01:26,950 --> 00:01:30,080 sodat wanneer jy kry e-pos op soos 02:00 en ek is gradering. 38 00:01:30,080 --> 00:01:33,710 Indien nie want ek het om te kyk alles rondom jou Pset. 39 00:01:33,710 --> 00:01:34,440 Cool. 40 00:01:34,440 --> 00:01:37,270 >> Ek weet dit is vroeg, maar ek heeltemal het geneem onkant 41 00:01:37,270 --> 00:01:40,800 deur 'n opstel wat as gevolg van hierdie Vrydag, wat my professore is net soos, o ja. 42 00:01:40,800 --> 00:01:42,550 Onthou, jy het 'n opstel gevolg op Vrydag. 43 00:01:42,550 --> 00:01:45,780 So, ek weet niemand hou na te dink oor midterms, 44 00:01:45,780 --> 00:01:50,620 maar jou eerste toets is op 15 Oktober wat Oktober is die begin van hierdie week. 45 00:01:50,620 --> 00:01:53,290 So, is dit dalk gouer wees as wat jy verwag is nie. 46 00:01:53,290 --> 00:01:57,510 Sodat jy nie afgegooi betrap toe Ek noem die volgende week se artikel wat o, 47 00:01:57,510 --> 00:02:00,560 jou quiz volgende week, het ek gedink Ek sal vir jou 'n bietjie meer 48 00:02:00,560 --> 00:02:01,500 van 'n kop nou. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> So, jou probleem stel, nommer drie. 51 00:02:04,660 --> 00:02:07,070 Hoe mense lees die spec uit nuuskierigheid? 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 Ons het 'n paar. 55 00:02:10,229 --> 00:02:12,320 Soort van uit die verlede week, maar dit is OK. 56 00:02:12,320 --> 00:02:13,650 Ek weet dit was 'n pragtige uit. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 So Breek Uit. 59 00:02:16,660 --> 00:02:21,010 Beslis nadat jy gedoen te kry vandag lees jou spec ten minste 60 00:02:21,010 --> 00:02:25,240 probeer om soos die aflaai verspreiding kode en hardloop 61 00:02:25,240 --> 00:02:27,430 soos die eerste aanvanklike ding wat hulle vra om jou te. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Want ons is met behulp van verspreiding-kode en 'n biblioteek 64 00:02:32,590 --> 00:02:36,790 dat ons net using-- --It is net die tweede keer dat ons hierdie Pset gedoen het, 65 00:02:36,790 --> 00:02:38,650 gek dinge kan gebeur met jou apparaat, 66 00:02:38,650 --> 00:02:41,370 en jy wil om te vind dat nou uit versus later. 67 00:02:41,370 --> 00:02:45,570 >> Want as dit is Donderdagaand of dit Woensdagaand en vir een of ander rede 68 00:02:45,570 --> 00:02:48,912 jou toestel nie net nie wil om te hardloop met die biblioteek 69 00:02:48,912 --> 00:02:50,620 of met die verspreiding kode, wat beteken dat 70 00:02:50,620 --> 00:02:52,309 jy kan nie eens begin om die kodering. 71 00:02:52,309 --> 00:02:54,100 Omdat jy nie kan sien om te sien of dit werk. 72 00:02:54,100 --> 00:02:55,975 Jou nie eers in staat wees om om te sien of dit stel. 73 00:02:55,975 --> 00:03:00,500 Jy wil vroeg in die sorg van diegene te neem die week, toe jy my nog kan e-pos 74 00:03:00,500 --> 00:03:03,100 of een van die ander TFS, en ons kan kry die vaste. 75 00:03:03,100 --> 00:03:05,410 Want dit is kwessies wat gaan om jou te stop 76 00:03:05,410 --> 00:03:07,120 uit die maak van enige werklike vordering. 77 00:03:07,120 --> 00:03:10,055 Dit is nie soos 'n fout, wat jy kan net soort van spring oor. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 As jy probleme met jou toestel of verspreiding kode, 80 00:03:13,420 --> 00:03:16,211 jy regtig wil om te kry wat geneem sorg van vroeër eerder as later. 81 00:03:16,211 --> 00:03:20,410 So selfs as jy nie eintlik nou eers begin kodering, laai die verspreiding 82 00:03:20,410 --> 00:03:24,040 kode, lees die spec, maak seker alles is daar werk. 83 00:03:24,040 --> 00:03:25,134 OK? 84 00:03:25,134 --> 00:03:27,675 As jy net kan doen wat ek jou lewe belowe, sal makliker wees. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 En so gaan jy waarskynlik om dit te doen nou reg? 87 00:03:31,410 --> 00:03:32,100 OK. 88 00:03:32,100 --> 00:03:33,950 So, enige vrae is daar? 89 00:03:33,950 --> 00:03:35,850 Enige logistieke dinge? 90 00:03:35,850 --> 00:03:36,910 Almal is goed? 91 00:03:36,910 --> 00:03:38,270 OK. 92 00:03:38,270 --> 00:03:41,700 >> Disclaimer vir dié van jy in die kamer en aanlyn. 93 00:03:41,700 --> 00:03:45,437 Ek gaan om te probeer om oor te skakel tussen PowerPoint in die toestel 94 00:03:45,437 --> 00:03:47,270 want ons gaan te wees om 'n paar kodering 95 00:03:47,270 --> 00:03:53,630 vandag deur die gewilde vraag van die anonieme voorstel poll Ek het verlede week. 96 00:03:53,630 --> 00:03:55,480 So, sal ons doen 'n paar kodering. 97 00:03:55,480 --> 00:03:57,800 So, as jy ouens wil ook te brand jou toestelle, 98 00:03:57,800 --> 00:04:02,910 en jy moet gekry het 'n e-pos van my, met 'n voorbeeld lêer. 99 00:04:02,910 --> 00:04:04,310 Voel asseblief vry om dit te doen. 100 00:04:04,310 --> 00:04:07,340 >> So, ons gaan om te praat oor GDB, wat 'n debugger. 101 00:04:07,340 --> 00:04:09,970 Dit gaan om jou te help soort uit te vind waar 102 00:04:09,970 --> 00:04:11,860 dinge verkeerd gaan in jou kode. 103 00:04:11,860 --> 00:04:15,370 Dit is regtig net 'n manier vir jou om te stap deur jou kode as dit gebeur, 104 00:04:15,370 --> 00:04:19,100 en in staat wees om uit te druk veranderlikes of sien wat regtig aangaan 105 00:04:19,100 --> 00:04:22,980 onder die enjinkap verse jou program net loop, is dit soos onderbrekings, 106 00:04:22,980 --> 00:04:25,030 en jy soos, geen idee wat net hier gebeur het. 107 00:04:25,030 --> 00:04:26,730 Ek weet nie watter lyn dit nie by. 108 00:04:26,730 --> 00:04:29,040 Ek weet nie waar dit verkeerd gegaan het. 109 00:04:29,040 --> 00:04:31,280 So, is GDB gaan om jou te help met dit. 110 00:04:31,280 --> 00:04:35,240 Ook, as jy besluit om te voortgaan ja, en neem 61, 111 00:04:35,240 --> 00:04:38,430 dit sal regtig, regtig jou beste vriend, want ek kan jou vertel 112 00:04:38,430 --> 00:04:40,840 want ek gaan deur middel van die klas. 113 00:04:40,840 --> 00:04:43,620 >> Ons gaan om te kyk na binêre soek, en as julle onthou 114 00:04:43,620 --> 00:04:47,540 die groot telefoon boek voorbeeld skouspel uit die klas. 115 00:04:47,540 --> 00:04:50,620 Ons sal word implementering nie, en loop deur dat 'n bietjie meer, 116 00:04:50,620 --> 00:04:54,650 en dan gaan ons deur middel van vier verskillende soorte, wat borrel, 117 00:04:54,650 --> 00:04:56,285 Keuring, plasing, en saam te smelt. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Cool. 120 00:04:58,330 --> 00:05:00,390 So, GDB soos ek genoem het, is 'n debugger. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 En dit is soort van die groot dinge, die groot funksies of opdragte 123 00:05:09,370 --> 00:05:13,240 dat jy binne GDB gebruik, en ek sal loop jou deur 'n demonstrasie van dit in 'n tweede. 124 00:05:13,240 --> 00:05:15,360 >> So, dit is nie net gaan abstrakte te bly. 125 00:05:15,360 --> 00:05:18,000 Ek sal probeer en maak dit as konkrete as moontlik vir julle. 126 00:05:18,000 --> 00:05:19,870 So, breek. 127 00:05:19,870 --> 00:05:22,200 Dit sal óf breek soos sommige nommer, wat 128 00:05:22,200 --> 00:05:26,900 verteenwoordig 'n lyn in jou program, of jy kan noem 'n funksie. 129 00:05:26,900 --> 00:05:30,150 So, as jy sê breek hoof, dit sal stop by die hoof, 130 00:05:30,150 --> 00:05:32,400 en laat jou deur daardie funksie te loop. 131 00:05:32,400 --> 00:05:36,350 >> Net so, as jy 'n paar eksterne funksioneer soos Swap of Cube, 132 00:05:36,350 --> 00:05:38,450 dat ons kyk na verlede week. 133 00:05:38,450 --> 00:05:41,780 As jy sê breek een van daardie, wanneer jou program treffers wat, 134 00:05:41,780 --> 00:05:44,290 dit sal wag vir jou om te vertel dit wat om te doen. 135 00:05:44,290 --> 00:05:47,860 Voor dit sal net so voer jy kon eintlik stap in die funksie 136 00:05:47,860 --> 00:05:49,020 en kyk wat aangaan. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 So, Volgende, spring net oor die volgende lyn, gaan oor funksies. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Stap. 141 00:05:55,560 --> 00:05:56,810 Dit is al die klein abstrakte. 142 00:05:56,810 --> 00:06:00,530 So, ek gaan net om te loop deur hulle maar jy sal dit sien in die gebruik in 'n tweede. 143 00:06:00,530 --> 00:06:01,810 >> Stap in 'n funksie. 144 00:06:01,810 --> 00:06:04,170 So as ek gesê het, soos met Swap, sou dit 145 00:06:04,170 --> 00:06:07,110 toelaat dat jy eintlik asof jy soos fisies binne trap, 146 00:06:07,110 --> 00:06:10,990 jy kan mors met daardie veranderlikes, druk uit wat hulle is, sien wat gaan aan. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Lys sal letterlik net druk uit die omliggende kode. 149 00:06:14,830 --> 00:06:17,570 So, as jy soort van vergeet waar jy in jou program, 150 00:06:17,570 --> 00:06:19,880 of jy wonder wat gaan aan om dit 151 00:06:19,880 --> 00:06:23,790 dit sal net druk 'n segment van soos vyf of ses lyne rondom. 152 00:06:23,790 --> 00:06:26,080 So, kan jy georiënteerde raak oor waar jy is. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Druk 'n paar veranderlike. 155 00:06:28,650 --> 00:06:34,590 So, as jy die sleutel hou in Caesar, dat ons sal kyk. 156 00:06:34,590 --> 00:06:36,220 Jy kan sê Print Sleutel by enige punt. 157 00:06:36,220 --> 00:06:40,070 Dit sal jou vertel wat die waarde is dus dat, miskien iewers langs die pad, 158 00:06:40,070 --> 00:06:42,070 jy overwrote jou sleutel. 159 00:06:42,070 --> 00:06:45,495 Jy kan eintlik sê dat omdat jy kan eintlik sien dat waarde. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> In die plaaslike bevolking, net druk uit jou plaaslike veranderlikes. 162 00:06:48,780 --> 00:06:53,120 So, wanneer jy in 'n lus, en jy wil net om te sien soos, ag. 163 00:06:53,120 --> 00:06:54,270 Wat is my ek? 164 00:06:54,270 --> 00:06:57,020 Wat is hierdie sleutel waarde dat ek hier inisialiseer? 165 00:06:57,020 --> 00:06:58,537 Wat is die boodskap op hierdie punt? 166 00:06:58,537 --> 00:07:00,370 Dit sal net druk al van daardie, sodat jy 167 00:07:00,370 --> 00:07:04,330 nie individueel te sê Print I. Druk boodskap. 168 00:07:04,330 --> 00:07:04,970 Print Sleutel. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 En dan vertoon. 171 00:07:07,700 --> 00:07:10,370 Wat nou gebeur is dat as jy stap vir stap deur die program, 172 00:07:10,370 --> 00:07:13,980 dit sal net seker maak dat dit vertoon 'n sekere veranderlike 173 00:07:13,980 --> 00:07:14,780 op elke punt. 174 00:07:14,780 --> 00:07:17,160 Sodat jy also-- --it is soort van 'n kortpad waar 175 00:07:17,160 --> 00:07:19,530 jy hoef nie om aan te hou soos, ag. 176 00:07:19,530 --> 00:07:23,150 Print Sleutel of Print I. Dit het net sal outomaties doen dit vir jou. 177 00:07:23,150 --> 00:07:25,959 >> So, met wat, ons gaan om te sien hoe dit gaan. 178 00:07:25,959 --> 00:07:28,000 Ek gaan om te probeer en skakelaar oor my toestel. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Sien as ek dit kan doen. 181 00:07:31,271 --> 00:07:31,770 Almal. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Ons is net gaan om dit te weerspieël. 184 00:07:42,370 --> 00:07:44,530 Daar is niks gek op my laptop 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 Dit moet aan hierdie een wees. 189 00:08:01,054 --> 00:08:01,795 Dit is so klein. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Kom ons kyk of ons dit kan doen. 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 is natuurlik sukkel hier net 'n bietjie, 195 00:08:15,305 --> 00:08:17,995 maar ons sal dit kry in 'n 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 Ons is net gaan om dit te verhoog. 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 Kan almal soort van sien dat? 202 00:08:31,679 --> 00:08:32,470 Miskien 'n bietjie? 203 00:08:32,470 --> 00:08:33,594 Ek weet dit is 'n bietjie klein. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Jy kan nie heeltemal uit te vind hoe dit groter te maak. 206 00:08:37,530 --> 00:08:38,350 As iemand weet. 207 00:08:38,350 --> 00:08:40,309 Is daar iemand wat weet hoe om dit groter te maak? 208 00:08:40,309 --> 00:08:40,932 OK. 209 00:08:40,932 --> 00:08:42,140 Ons gaan aan die gang met dit. 210 00:08:42,140 --> 00:08:45,801 Maak nie saak nie anyways, want dit is net dit is die kode wat julle moet 211 00:08:45,801 --> 00:08:46,300 het. 212 00:08:46,300 --> 00:08:48,310 >> Wat is meer belangrik is die terminale hier. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 En ons het hier Hoekom is dit so klein? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Instellings. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 O. 219 00:09:08,420 --> 00:09:09,500 Ware Ike. 220 00:09:09,500 --> 00:09:10,880 Hoe is dit? 221 00:09:10,880 --> 00:09:11,770 Daar uit. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Is dit beter vir almal? 224 00:09:21,810 --> 00:09:22,525 OK ,. 225 00:09:22,525 --> 00:09:23,025 Cool. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Jy weet wanneer jy in 'n CS klas tegniese probleme 228 00:09:28,220 --> 00:09:32,971 is soort van 'n deel van the-- So, laat ons duidelik nie. 229 00:09:32,971 --> 00:09:33,470 OK. 230 00:09:33,470 --> 00:09:38,060 So, hier in afdeling wat ons hier gehad het. 231 00:09:38,060 --> 00:09:40,830 Caesar is 'n uitvoerbare lêer. 232 00:09:40,830 --> 00:09:41,800 So ek het dit gemaak. 233 00:09:41,800 --> 00:09:46,370 So, een ding om te besef met GDB is dat dit werk net op uitvoerbare lêers. 234 00:09:46,370 --> 00:09:48,040 So, jy kan nie loop dit op 'n dotsy. 235 00:09:48,040 --> 00:09:50,532 Jy moet eintlik maak seker dat jou kode stel, 236 00:09:50,532 --> 00:09:51,865 en dat dit eintlik kan uitgevoer word. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> So, maak seker dat indien dit nie gebeur nie stel, kry dit saam te stel, 239 00:09:56,186 --> 00:09:57,810 sodat jy kan soort van loop deur dit. 240 00:09:57,810 --> 00:10:04,590 So, GDB om te begin, alles wat jy doen, Gloria tipe GDB, en dan net die 241 00:10:04,590 --> 00:10:06,250 lêer wat jy wil. 242 00:10:06,250 --> 00:10:08,240 Ek het altyd spelfoute Caesar. 243 00:10:08,240 --> 00:10:11,730 Maar jy wil om seker te maak want dit is 'n uitvoerbare, 244 00:10:11,730 --> 00:10:14,210 tie se dot flits sodat beteken jy gaan 245 00:10:14,210 --> 00:10:19,240 hardloop CSI jy gaan om uit te voer hierdie lêers óf met die debugger. 246 00:10:19,240 --> 00:10:19,910 OK. 247 00:10:19,910 --> 00:10:22,885 So, jy doen nie, jy hierdie soort van brabbeltaal. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 Dis net alles oor debugger. 250 00:10:25,750 --> 00:10:28,200 Jy het nie regtig te bekommerd wees oor dit nou. 251 00:10:28,200 --> 00:10:31,460 En as jy sien, ons het hierdie oop parens, BBP, naby parens, 252 00:10:31,460 --> 00:10:34,690 en net soort van lyk Ons opdrag lyn, reg? 253 00:10:34,690 --> 00:10:37,010 >> So, wat ons wil do-- --So, Die eerste ding 254 00:10:37,010 --> 00:10:39,570 is wat ons wil om te kies 'n plek om dit te breek. 255 00:10:39,570 --> 00:10:42,332 So, daar is 'n fout in hierdie Caesar program 256 00:10:42,332 --> 00:10:44,290 dat ek stel dat ons gaan om uit te vind. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 Dit Wat beteken dit is wat dit neem om die insette Barfoo in hoofletters, en vir een of ander rede 259 00:10:56,350 --> 00:11:01,950 dit nie verander A. Dit laat net dit alleen, is alles anders korrek is, 260 00:11:01,950 --> 00:11:03,980 maar die tweede brief A bly onveranderd. 261 00:11:03,980 --> 00:11:07,120 So, ons gaan om te probeer en uit te vind waarom dit is. 262 00:11:07,120 --> 00:11:10,440 So, die eerste ding wat jy tipies wil doen wanneer jy begin op GDB 263 00:11:10,440 --> 00:11:12,010 is uit te vind waar om dit te breek. 264 00:11:12,010 --> 00:11:14,956 >> So Caesar is 'n mooi kort program. 265 00:11:14,956 --> 00:11:16,330 Ons het net een funksie, reg? 266 00:11:16,330 --> 00:11:18,520 Wat was ons funksie in die keiser? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 Daar is net een funksie, Main reg? 269 00:11:24,350 --> 00:11:26,490 Main is 'n funksie vir al jou programme. 270 00:11:26,490 --> 00:11:29,230 As jy het nie Main, kan ek 'n bietjie bekommerd nou, 271 00:11:29,230 --> 00:11:31,000 maar ek hoop julle almal het Main daar. 272 00:11:31,000 --> 00:11:34,150 So, wat ons kan doen, is om ons kan net breek Main, net soos dit. 273 00:11:34,150 --> 00:11:35,190 So, dit sê, OK. 274 00:11:35,190 --> 00:11:37,430 Ons stel ons breekpunt een daar. 275 00:11:37,430 --> 00:11:42,870 >> So, nou die ding om te onthou, is die keiser neem een ​​command line argument reg 276 00:11:42,870 --> 00:11:45,150 en ons het nie gedoen wat enige plek nie. 277 00:11:45,150 --> 00:11:47,560 So, wat jy doen, is wanneer jy eintlik gaan na afloop 278 00:11:47,560 --> 00:11:51,540 die program, 'n program wat jy hardloop in GDB wat moet command line 279 00:11:51,540 --> 00:11:55,010 argumente, jy gaan om insette wanneer jy die eerste keer begin om dit te draai. 280 00:11:55,010 --> 00:11:59,280 So, in hierdie geval, ons doen Begin met 'n sleutel van drie. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 En dit sal eintlik begin. 283 00:12:02,040 --> 00:12:08,480 >> So, as jy hier sien, het ons ' As RC is nie gelyk aan 2. 284 00:12:08,480 --> 00:12:12,210 So as julle almal lêer wat ek uitgestuur het 285 00:12:12,210 --> 00:12:15,100 sal jy sien dat dit is soos die eerste reël ons vernaamste funksie, reg? 286 00:12:15,100 --> 00:12:17,890 Dit is om te kyk of ons 'n die korrekte aantal argumente. 287 00:12:17,890 --> 00:12:20,620 So, as jy wonder As RC korrek is, 288 00:12:20,620 --> 00:12:23,250 jy iets net soos Print RC kan doen. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC is twee, wat wat ons verwag het, reg? 291 00:12:28,640 --> 00:12:32,010 >> Dus, kan ons nou volgende, en gaan voort deur middel van. 292 00:12:32,010 --> 00:12:33,200 So, ons het 'n paar belangrike daar. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 En ons kan druk ons ​​sleutel om seker te maak dat die inligting korrek is nie. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interessant. 297 00:12:39,500 --> 00:12:41,210 Nie heeltemal wat ons verwag het. 298 00:12:41,210 --> 00:12:44,810 So, een ding om te besef met GDB ook is 299 00:12:44,810 --> 00:12:49,000 dat dit nie totdat jy eintlik getref Volgende, dat die lyn wat jy nou net gesien 300 00:12:49,000 --> 00:12:50,720 is eintlik uitgevoer. 301 00:12:50,720 --> 00:12:53,870 So, in hierdie geval Sleutel het nie toegeken is nie. 302 00:12:53,870 --> 00:12:57,050 So, Sleutel is 'n gemors waarde wat jy sien op die bodem daar. 303 00:12:57,050 --> 00:13:03,680 Negatiewe $ 120-- --It se een biljoen en iets vreemd dinge reg? 304 00:13:03,680 --> 00:13:05,340 Dit is nie die sleutel wat ons verwag het. 305 00:13:05,340 --> 00:13:10,720 Maar as ons getref Volgende, en dan moet ons probeer Print sleutel, dit is drie. 306 00:13:10,720 --> 00:13:11,710 >> Almal sien dat? 307 00:13:11,710 --> 00:13:13,780 Dus, as jy iets dat jy soos, wag. 308 00:13:13,780 --> 00:13:15,540 Dit is heeltemal verkeerd is, en ek weet nie 309 00:13:15,540 --> 00:13:20,150 hoe dit sal gebeur nie, want al wat ek wil te doen, is wys 'n nommer, 'n veranderlike, 310 00:13:20,150 --> 00:13:22,900 probeer slaan Volgende, probeer om druk dit weer, en sien as dit werk. 311 00:13:22,900 --> 00:13:27,830 Want dit gaan net om uit te voer en eintlik iets wys nadat jy 312 00:13:27,830 --> 00:13:29,340 getref Volgende. 313 00:13:29,340 --> 00:13:30,336 Sin maak vir almal? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> Spreker 2: Wanneer jy ewekansige getalle wat beteken dit? 316 00:13:33,220 --> 00:13:34,790 >> Spreker 1: Dis net lukraak. 317 00:13:34,790 --> 00:13:35,710 Dis net gemors. 318 00:13:35,710 --> 00:13:38,320 Dit is net iets wat jou rekenaar sal lukraak toeken. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Cool. 321 00:13:40,220 --> 00:13:45,760 So, nou kan ons beweeg deur, en so nou het ons hierdie eenvoudige teks GetString. 322 00:13:45,760 --> 00:13:48,600 So, laat my net stel wat sal gebeur wanneer ons Next hier getref. 323 00:13:48,600 --> 00:13:51,320 Ons GDB soort verdwyn, reg? 324 00:13:51,320 --> 00:13:55,720 Dit is omdat GetString is nou die uitvoering, reg? 325 00:13:55,720 --> 00:14:01,460 So, toe ons sien plain text gelyk GetString, oop parens en parens, 326 00:14:01,460 --> 00:14:04,380 en ons getref Volgende, wat eintlik nou uitgevoer word. 327 00:14:04,380 --> 00:14:06,580 So, is dit wag vir ons insette iets. 328 00:14:06,580 --> 00:14:13,560 >> So, gaan ons insette ons kos wat is wat dit versuim as ek jou vertel 329 00:14:13,560 --> 00:14:18,020 en wat net sê dat dit klaar te voer, dat die geslote 330 00:14:18,020 --> 00:14:19,980 bracket beteken dit opwindende uit daardie lus. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Dus, kan ons getref Volgende, en nou, want ek is seker dat jy al bekend van Caesar, 333 00:14:25,420 --> 00:14:27,260 dit is, wat is hierdie lyn gaan doen. 334 00:14:27,260 --> 00:14:32,030 Dis vir Int ek gelyk 0, N is gelyk aan Strlen, gewone teks, en dan 335 00:14:32,030 --> 00:14:33,960 Ek is minder as N, Ek, plus, plus. 336 00:14:33,960 --> 00:14:35,210 Wat is hierdie lus gaan doen? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Maak jou boodskap. 339 00:14:39,160 --> 00:14:39,770 Cool. 340 00:14:39,770 --> 00:14:41,330 So, laat ons begin om dit te doen. 341 00:14:41,330 --> 00:14:47,210 >> So, moet hierdie toestand pas, vir ons eerste een? 342 00:14:47,210 --> 00:14:52,250 As dit is 'n B, dit is plain text I. Ons kan inligting oor ons locals kry. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 So, ek is nul, en as ses, wat ons verwag, en ons sleutel is drie. 345 00:14:57,970 --> 00:14:59,227 Al wat sin maak, reg? 346 00:14:59,227 --> 00:15:01,310 Hierdie syfers is almal presies wat hulle behoort te wees. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 So, neurie? 349 00:15:03,870 --> 00:15:05,620 SPREKER 3: Ek het ewekansige nommers vir my. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 Spreker 1: Wel, kan ons --we check-- kan gesels oor wat in 'n tweede. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Maar jy moet wees om hierdie. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 So, as ons 'n kapitale B vir ons eerste een, 356 00:15:20,130 --> 00:15:22,080 hierdie toestand moet dit vang, reg? 357 00:15:22,080 --> 00:15:27,120 So, as ons getref Volgende, sien ons dat hierdie As eintlik voer. 358 00:15:27,120 --> 00:15:29,220 Want as jy volgende saam in jou kode, 359 00:15:29,220 --> 00:15:33,460 hierdie lyn hier, waar plain text ek vervang met hierdie rekenkundige, 360 00:15:33,460 --> 00:15:35,720 net voer indien die As toestand is korrek reg? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB is slegs gaan om jou te wys dinge wat eintlik die uitvoering. 363 00:15:40,240 --> 00:15:45,140 So as dit Indien die toestand nie nagekom is, dit is net gaan na die volgende lyn. 364 00:15:45,140 --> 00:15:46,540 OK? 365 00:15:46,540 --> 00:15:48,510 So, ons het dit. 366 00:15:48,510 --> 00:15:51,171 Dit bracket beteken dit gesluit nou uit daardie lus. 367 00:15:51,171 --> 00:15:52,420 So, dit gaan om weer te begin. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Net soos dit. 370 00:15:56,280 --> 00:15:59,120 So, dat ons inligting kan kry oor ons plaaslike inwoners hier, 371 00:15:59,120 --> 00:16:02,575 en ons sien dat ons eerste brief verander het, reg? 372 00:16:02,575 --> 00:16:05,150 Dit is nou 'n E, soos dit moet wees. 373 00:16:05,150 --> 00:16:07,360 Dus, kan ons voortgaan op. 374 00:16:07,360 --> 00:16:08,500 >> En ons het die tjek. 375 00:16:08,500 --> 00:16:09,916 En die tjek moet werk, reg? 376 00:16:09,916 --> 00:16:12,570 Dit is A. Dit moet verander word drie letters vorentoe. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Maar as jy sien, ons kry iets anders. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 So in hierdie geval hier, dit gevang dit, en so hierdie lyn uitgevoer word, 381 00:16:22,860 --> 00:16:28,620 wat aangepas ons B. Maar, in hierdie geval hier, 382 00:16:28,620 --> 00:16:32,860 Ons het dit net oorgeslaan het, en na die [? L siff. ?] 383 00:16:32,860 --> 00:16:34,660 So iets gaan daar aan. 384 00:16:34,660 --> 00:16:37,780 Wat dit is wat jy vertel is dat, ons weet dat dit hier moet vang, 385 00:16:37,780 --> 00:16:39,200 maar dit is nie. 386 00:16:39,200 --> 00:16:42,210 Kan iemand sien wat ons probleem is in die lyn? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 Dit is 'n baie klein ding. 389 00:16:46,969 --> 00:16:48,510 En jy kan ook kyk na jou kode. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 Dit is ook line-- vergeet wat lyn is dit in there-- maar dit is in die [onhoorbaar]. 392 00:16:54,940 --> 00:16:55,480 Ja? 393 00:16:55,480 --> 00:16:58,639 >> SPREKER 4: Dit is op die groter as bladsy as jy dit lees in die boek. 394 00:16:58,639 --> 00:16:59,430 Spreker 1: Presies. 395 00:16:59,430 --> 00:17:02,620 So, kon die debugger nie vertel jy dit nie, maar die debugger 396 00:17:02,620 --> 00:17:05,880 kon kry jy af na 'n lyn dat jy weet nie in werking is. 397 00:17:05,880 --> 00:17:09,319 En soms, wanneer veral later in die semester, wanneer 398 00:17:09,319 --> 00:17:12,910 jy met 'n honderd, 'n honderd paar reëls van die kode, en jy 399 00:17:12,910 --> 00:17:16,190 Ek weet nie waar dit versuim, dit is 'n goeie manier om dit te doen. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 So, ons het ons fout. 402 00:17:18,989 --> 00:17:21,530 Jy kan dit los in jou lêer, en dan kan jy dit weer te hardloop, 403 00:17:21,530 --> 00:17:23,029 en alles sal goed werk. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 En die grootste ding is Dit kan lyk soos, OK. 406 00:17:30,590 --> 00:17:31,090 Ja. 407 00:17:31,090 --> 00:17:31,370 Cool. 408 00:17:31,370 --> 00:17:32,744 Jy het geweet wat jy soek. 409 00:17:32,744 --> 00:17:34,910 So, jy het geweet wat om te doen. 410 00:17:34,910 --> 00:17:39,021 >> GDB kan wees super nuttig omdat jy Al hierdie dinge kan uitdruk dat jy 411 00:17:39,021 --> 00:17:39,520 sou nie. 412 00:17:39,520 --> 00:17:41,160 Dit is baie meer nuttig is as printf. 413 00:17:41,160 --> 00:17:43,440 Hoeveel van julle gebruik soos printf state 414 00:17:43,440 --> 00:17:46,200 om uit te vind waar 'n fout was, reg? 415 00:17:46,200 --> 00:17:48,450 So, met hierdie, jy doen nie het om aan te hou terug, 416 00:17:48,450 --> 00:17:51,139 en graag kommentaar in Printf, of kommentaar het, 417 00:17:51,139 --> 00:17:52,930 en uit te vind wat jy moet druk. 418 00:17:52,930 --> 00:17:55,670 Dit eintlik net kan jy stap vir stap deur, druk dinge 419 00:17:55,670 --> 00:18:00,000 as jy gaan, so, kan jy sien hoe hulle verander in reële tyd, 420 00:18:00,000 --> 00:18:02,190 as jou program loop. 421 00:18:02,190 --> 00:18:04,390 >> En dit neem 'n bietjie bietjie gewoond raak aan. 422 00:18:04,390 --> 00:18:07,850 Ek sou raai net soort om 'n bietjie gefrustreerd met dit 423 00:18:07,850 --> 00:18:08,930 vir nou. 424 00:18:08,930 --> 00:18:13,450 As jy oor die spandeer 'n uur volgende week leer hoe GDB om te gebruik, 425 00:18:13,450 --> 00:18:16,140 sal jy jouself red so baie tyd later. 426 00:18:16,140 --> 00:18:18,750 En letterlik. ons vertel hierdie mense elke jaar, 427 00:18:18,750 --> 00:18:23,890 en ek onthou toe ek die klas, ek was soos ek sal goed wees. 428 00:18:23,890 --> 00:18:24,700 No. 429 00:18:24,700 --> 00:18:27,030 Pset 6 gekom en ek was soos, ek gaan leer 430 00:18:27,030 --> 00:18:29,500 hoe GDB te gebruik, want ek doen nie weet wat gaan hier aan. 431 00:18:29,500 --> 00:18:32,940 >> So as jy die tyd, so neem gebruik dit op kleiner programme 432 00:18:32,940 --> 00:18:35,697 wat jy gaan wees werk, soos die werk 433 00:18:35,697 --> 00:18:37,530 deur iets soos Visionare, soos hierdie. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 Of as jy wil ekstra oefening, ek is seker Ek kon kom met karretjie programme, 436 00:18:42,850 --> 00:18:45,300 vir jou om te ontfout as jy wil. 437 00:18:45,300 --> 00:18:49,300 >> Maar as jy net 'n tyd neem om te kry gebruik om dit, net speel rond met dit, 438 00:18:49,300 --> 00:18:50,550 dit sal regtig dien jou goed. 439 00:18:50,550 --> 00:18:52,591 En dit is regtig een van daardie dinge wat jy net 440 00:18:52,591 --> 00:18:57,340 het om te probeer, en jou hande vuil kry met, voordat jy regtig dit verstaan. 441 00:18:57,340 --> 00:19:02,090 Ek het regtig net een keer verstaan ​​dit Ek moes debug dinge met dit, 442 00:19:02,090 --> 00:19:08,170 en dit is baie lekkerder om 'n idee te hê van hoe om vroeër eerder as later te ontfout. 443 00:19:08,170 --> 00:19:08,850 OK. 444 00:19:08,850 --> 00:19:09,625 Cool. 445 00:19:09,625 --> 00:19:12,960 Ek weet dit is soort van soos 'n crash kursus in GDB, 446 00:19:12,960 --> 00:19:16,400 en ek sal beslis werk om hierdie groter volgende keer te kyk. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Cool. 449 00:19:18,280 --> 00:19:20,390 >> So, as ons gaan terug na ons PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 Is dit gaan om te werk? 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 Ja. 455 00:19:31,101 --> 00:19:31,600 OK. 456 00:19:31,600 --> 00:19:35,480 So, as jy ooit enige van nodig diegene weer, daar is die lys. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 So binêre soek, wat almal onthou die groot skouspel van Dawid 459 00:19:40,830 --> 00:19:42,259 rip telefoon boeke in die helfte. 460 00:19:42,259 --> 00:19:44,050 Ek het nie regtig kry nie die telefoon boeke nie, 461 00:19:44,050 --> 00:19:46,530 want soos waar doen jy kry telefoon boeke hierdie dae? 462 00:19:46,530 --> 00:19:48,220 Ek weet regtig nie. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 Die binêre soek. 465 00:19:50,590 --> 00:19:52,464 Is daar iemand onthou hoe binêre soek werk? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Enigeen by almal? 468 00:19:55,220 --> 00:19:56,325 Ja? 469 00:19:56,325 --> 00:19:58,283 SPREKER 5: Jy weet wanneer jy kyk na wat die helfte 470 00:19:58,283 --> 00:20:01,146 dit sou in wees, op grond van dat, en ontslae te raak van die ander helfte. 471 00:20:01,146 --> 00:20:01,896 >> Spreker 1 Presies. 472 00:20:01,896 --> 00:20:06,290 So, binêre soek, dit is soort van a-- --we graag noem dit verdeel en oorwin. 473 00:20:06,290 --> 00:20:09,170 So, wat jy doen, is jy kyk in die middel, 474 00:20:09,170 --> 00:20:11,990 en jy sal sien as dit ooreenstem met wat jy soek. 475 00:20:11,990 --> 00:20:15,420 En as dit nie gebeur nie, dan probeer om jou te uit te vind, gaan dit gelaat word 476 00:20:15,420 --> 00:20:16,450 half of die regter helfte. 477 00:20:16,450 --> 00:20:19,325 So, kan dit wees as jy op soek is na op iets wat analfabeet, 478 00:20:19,325 --> 00:20:20,720 jy sien, o. 479 00:20:20,720 --> 00:20:22,750 Maak Allison kom voor M? 480 00:20:22,750 --> 00:20:23,250 Ja. 481 00:20:23,250 --> 00:20:25,030 So, gaan ons kyk na die eerste helfte. 482 00:20:25,030 --> 00:20:26,450 >> Of dit kan wees soos met nommers. 483 00:20:26,450 --> 00:20:28,830 Enigiets wat jy kan vergelyk, kan dit gesorteer word. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 Jy kan binêre soektog op gebruik. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 So, almal onthou hierdie grafiek of wat dit is nie? 488 00:20:37,455 --> 00:20:39,520 Dit is Asymptotische kompleksiteit. 489 00:20:39,520 --> 00:20:42,830 So, hierdie grafiek net beskryf hoe lank dit 490 00:20:42,830 --> 00:20:46,230 neem jou 'n probleem op te los as jy verhoog die aantal van die dinge wat 491 00:20:46,230 --> 00:20:47,090 wat jy gebruik. 492 00:20:47,090 --> 00:20:51,260 >> So, ons het N, wat is lineêr tyd. 493 00:20:51,260 --> 00:20:54,560 As N meer as twee, wat effens beter, groei steeds super vinnig. 494 00:20:54,560 --> 00:20:58,360 En dan het ons Teken, wat wat ons beskou as binêre soek. 495 00:20:58,360 --> 00:21:03,630 As ons sien, as jou probleem kry veel en veel groter, 496 00:21:03,630 --> 00:21:06,600 die tyd wat dit neem om dit op te los nie regtig verhoog dat baie. 497 00:21:06,600 --> 00:21:09,010 Dit is soos 'n vergelykbare hier in die begin. 498 00:21:09,010 --> 00:21:10,060 Jy is soos, OK. 499 00:21:10,060 --> 00:21:13,000 Enigiets hier nie regtig saak watter een wat ons gebruik, 500 00:21:13,000 --> 00:21:16,220 maar jy kry uit 'n miljoen, 'n miljard. 501 00:21:16,220 --> 00:21:20,010 Jy probeer some-- --you're te vind probeer om 'n naald in 'n hooimied te vind. 502 00:21:20,010 --> 00:21:21,550 >> Ek dink jy wil hierdie probleem. 503 00:21:21,550 --> 00:21:25,850 Jy wil hierdie kompleksiteit, nie lineêr want vir alles wat jy 504 00:21:25,850 --> 00:21:30,049 weet wat jou gaan soek word deur elke individuele naald ding van hooi, 505 00:21:30,049 --> 00:21:31,340 probeer om te kyk vir jou naald. 506 00:21:31,340 --> 00:21:34,730 En dit is nie te lekker in my opinie. 507 00:21:34,730 --> 00:21:35,500 Ek hou van vinnig. 508 00:21:35,500 --> 00:21:36,620 Ek hou van doeltreffende. 509 00:21:36,620 --> 00:21:40,450 En as hardwerkende studente jy ouens is, weet jy slimmer te werk, 510 00:21:40,450 --> 00:21:43,010 nie harder soort ding, hoe jy kan maak om hierdie algoritmes. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> So, ons gaan om te loop deur net 'n vinnige voorbeeld. 513 00:21:47,910 --> 00:21:51,090 Ek dink jy ouens moet 'n hand op binêre soek, 514 00:21:51,090 --> 00:21:54,352 maar in die geval iemand is 'n bietjie vaag, dit wil versterk, 515 00:21:54,352 --> 00:21:56,310 ons gaan net gaan deur 'n voorbeeld hier. 516 00:21:56,310 --> 00:21:59,490 Dus, is ons op soek na as die skikking bevat sewe. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> So, die eerste ding wat ons doen, is om kyk in die middel, reg? 519 00:22:06,010 --> 00:22:09,340 En ook jy gaan word kodering Binêre soek in net 'n tweede. 520 00:22:09,340 --> 00:22:11,310 So, dit gaan pret wees. 521 00:22:11,310 --> 00:22:13,710 So ons kyk in die middel bietjie skikkings 3. 522 00:22:13,710 --> 00:22:15,501 Maak 3 gelyke 7? 523 00:22:15,501 --> 00:22:16,000 Nie. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Dit is ses. 526 00:22:19,550 --> 00:22:21,480 So, is dit minder as of groter is as sewe? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Minder as. 529 00:22:23,960 --> 00:22:24,570 Ja. 530 00:22:24,570 --> 00:22:25,170 Nice job ouens. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Ek voel ek soos ek moet het lekkergoed, want ek 533 00:22:27,360 --> 00:22:29,460 wil dit uit te gooi in die meter. 534 00:22:29,460 --> 00:22:30,270 Dit is wat ek gaan volgende week te doen. 535 00:22:30,270 --> 00:22:31,436 Dit sal verseker dat jy ouens skerp. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> So, gooi ons weg wat eerste helfte, reg? 538 00:22:34,690 --> 00:22:35,670 dit was minder as. 539 00:22:35,670 --> 00:22:39,325 ons weet dat alles op daardie linkerkant 540 00:22:39,325 --> 00:22:41,700 gaan minder wees as wat ons is eintlik op soek na. 541 00:22:41,700 --> 00:22:43,491 So, daar is geen behoefte om te aandag te gee aan dit. 542 00:22:43,491 --> 00:22:45,120 Net nie vergeet nie. 543 00:22:45,120 --> 00:22:48,720 So, nou is ons kyk na ons regterkant, en ons kyk na die middel daar, 544 00:22:48,720 --> 00:22:50,510 en nou is dit nege. 545 00:22:50,510 --> 00:22:55,510 So, 9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Groter is as wat ons is soek, reg? 547 00:22:57,470 --> 00:22:59,860 So, ons gaan om te gooi alles weg aan die regterkant. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Soos dit. 550 00:23:01,940 --> 00:23:03,700 Nou, is al wat ons gelaat met een. 551 00:23:03,700 --> 00:23:07,760 So ons kyk, is hierdie een wat Ons is op soek na? dit is. 552 00:23:07,760 --> 00:23:08,970 Ons het gevind wat ons wou hê. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 So het ons klaar is. 555 00:23:11,690 --> 00:23:12,550 Bilinear Search. 556 00:23:12,550 --> 00:23:15,740 >> En as jy sien, ons het sewe insette daar. 557 00:23:15,740 --> 00:23:24,320 Dit het ons het net soos drie keer, Maar as jy doen soos 'n miljard, 558 00:23:24,320 --> 00:23:28,190 julle weet hoe baie stappe wat dit sou neem as ons het 4000000000 dinge? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Enige raaiskote? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Dit is 32. 563 00:23:33,960 --> 00:23:37,110 32 stappe om iets te vind in 'n 4000000000 564 00:23:37,110 --> 00:23:39,650 element skikking gevolg van magte van twee. 565 00:23:39,650 --> 00:23:43,550 So twee is tot 32, is tot vier miljard gestyg. 566 00:23:43,550 --> 00:23:50,430 >> So mooi mal hoe jy nog steeds binne soos 'n redelik klein aantal stappe 567 00:23:50,430 --> 00:23:52,650 om iets te vind in 4000000000 elemente. 568 00:23:52,650 --> 00:23:55,730 So op daardie noot, ons gaan om dit te kodeer 569 00:23:55,730 --> 00:23:58,950 sodat julle kan eintlik soort van sien hoe dit werk. 570 00:23:58,950 --> 00:24:01,520 Alle reg, sodat julle kan kode. 571 00:24:01,520 --> 00:24:04,100 Ek gaan julle te laat praat vir 'n bietjie. 572 00:24:04,100 --> 00:24:07,970 Kry mense om jou te leer ken, wat wat iemand wou van die laaste artikel. 573 00:24:07,970 --> 00:24:10,280 >> So kry die mense om jou te leer ken. 574 00:24:10,280 --> 00:24:11,305 Praat vir 'n bietjie. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 En al wat ek wil graag van jou ouens is nou net 577 00:24:15,730 --> 00:24:17,575 probeer om 'n uiteensetting van pseudokode te skep. 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 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Al wat ek wil van julle ouens is jy net gaan in hierdie geval, terwyl te vul. 583 00:24:29,520 --> 00:24:32,170 So het ek hierdie boonste stel en laer perke wat 584 00:24:32,170 --> 00:24:35,250 verteenwoordig die begin en einde van ons reeks. 585 00:24:35,250 --> 00:24:40,440 En jy gaan eintlik loop deur en uit te vind 586 00:24:40,440 --> 00:24:42,470 wat ons doen in hierdie while lus. 587 00:24:42,470 --> 00:24:45,810 >> So as jy kan uitvind out-- Ek het 'n wenk there-- wat die gevalle 588 00:24:45,810 --> 00:24:46,640 dat ons hier? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 So as jy wil om uit te vind die gevalle, sal ons pseudokode diegene 591 00:24:51,560 --> 00:24:53,350 en dan sal ons werklik kodeer hulle. 592 00:24:53,350 --> 00:24:55,330 En dit gaan wees, het ek dink, hopelik sal dit 593 00:24:55,330 --> 00:24:56,788 'n bietjie makliker as wat jy verwag. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Want dit is nie dat veel kode, eintlik, wat is regtig cool. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> STUDENT: [onhoorbaar]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 INSTRUCTOR: Ja. 601 00:25:37,650 --> 00:25:38,595 Daar was iets te vind in die middel. 602 00:25:38,595 --> 00:25:39,552 >> STUDENT: So ons kan gebruik nie. 603 00:25:39,552 --> 00:25:39,770 OK. 604 00:25:39,770 --> 00:25:40,603 >> INSTRUCTOR: Perfect. 605 00:25:40,603 --> 00:25:42,950 So wat is die eerste ding wat ons moet doen. 606 00:25:42,950 --> 00:25:44,330 So vind die middel. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Groot. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 So jy het 'n idee van hoe ons kan eintlik vind die middel met 'n kode? 611 00:25:55,010 --> 00:25:55,980 >> STUDENT: Ja. 612 00:25:55,980 --> 00:25:57,000 N meer as 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 INSTRUCTOR: So n meer as 2. 615 00:25:59,500 --> 00:26:05,170 So een ding om te onthou, is dat jou boonste en onderste grense verander. 616 00:26:05,170 --> 00:26:08,110 Ons hou versmoor die deel van die skikking wat ons soek na. 617 00:26:08,110 --> 00:26:11,970 So n meer as 2 sal net werk vir die eerste ding wat ons doen. 618 00:26:11,970 --> 00:26:17,810 So neem die boonste en onderste in ag, Hoe kan ons kry dat die middel element? 619 00:26:17,810 --> 00:26:20,640 Want ons wil die middel tussen die boonste en onderste, reg? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> STUDENT: [onhoorbaar]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> INSTRUCTOR: So ons het 'n paar middel. 625 00:26:28,080 --> 00:26:32,730 En dit sal die boonste plus laer as 2 wees. 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 Daar gaan ons. 629 00:26:36,570 --> 00:26:37,280 Een lyn af. 630 00:26:37,280 --> 00:26:38,560 Julle is op jou pad. 631 00:26:38,560 --> 00:26:41,400 So nou dat ons ons middel, doen wat ons wil doen? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Net in die algemeen. 634 00:26:45,900 --> 00:26:47,734 Jy hoef nie om dit te Code. 635 00:26:47,734 --> 00:26:48,335 Ja. 636 00:26:48,335 --> 00:26:49,210 STUDENT: [onhoorbaar]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 INSTRUCTOR: So is dit plus omdat jy vind die gemiddeld tussen die twee 639 00:27:10,310 --> 00:27:10,810 van hulle. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 So as jy dink van hulle as soort verhoog in van die kante, 642 00:27:17,370 --> 00:27:21,640 dink oor dit as jy nader die middel, jy wil soos dit. 643 00:27:21,640 --> 00:27:27,150 So as jy aan weerskante van die middel, en ons het soos 5 en 7. 644 00:27:27,150 --> 00:27:31,440 Wanneer jy hulle voeg julle saam kry 12, jy verdeel deur 2, 6. 645 00:27:31,440 --> 00:27:33,726 >> Soms is dit moeilik om te verduidelik waarom dit werk, 646 00:27:33,726 --> 00:27:35,600 maar as jy deur te werk 'n voorbeeld soms, 647 00:27:35,600 --> 00:27:37,962 dit sal jou help om uit te vind of dit plus of minus moet wees. 648 00:27:37,962 --> 00:27:38,846 Ja. 649 00:27:38,846 --> 00:27:40,830 >> STUDENT: [onhoorbaar] presies in die middel 650 00:27:40,830 --> 00:27:43,950 As hulle 'n saak waar daar is 'n baie kleiner getalle 651 00:27:43,950 --> 00:27:45,860 en soos een groot aantal? 652 00:27:45,860 --> 00:27:49,750 >> INSTRUCTOR: So al wat jy moet is die middel van die skikking. 653 00:27:49,750 --> 00:27:53,010 So as jy 'n klomp van die klein getalle en dan 'n baie groot aantal 654 00:27:53,010 --> 00:27:54,799 aan die einde is, beteken dit nie saak nie. 655 00:27:54,799 --> 00:27:56,840 Al wat saak maak, is dat hulle gesorteer, jy moet net 656 00:27:56,840 --> 00:27:59,339 wil om te kyk na die middel van die skikking, want jy is nog steeds 657 00:27:59,339 --> 00:28:00,700 sny jou probleem in die helfte. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Cool. 660 00:28:03,680 --> 00:28:06,430 So nou dat ons die middel, wat doen ons nou? 661 00:28:06,430 --> 00:28:07,150 >> STUDENT: vergelyk. 662 00:28:07,150 --> 00:28:08,150 INSTRUCTOR: Die vergelyk. 663 00:28:08,150 --> 00:28:11,670 So vergelyk middel tot value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Cool. 666 00:28:15,160 --> 00:28:17,950 So jy sien hier het ons 'n hierdie waarde wil ons hier. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Onthou, dit is 'n skikking. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 So middel verwys na die indeks. 671 00:28:26,970 --> 00:28:29,785 So wil ons waardes van die middel te doen. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Moenie vergeet as jy wil , dubbel gelykes te vergelyk. 674 00:28:35,650 --> 00:28:38,250 Jy doen enkele gelyk is jy net gaan om dit te toewys, 675 00:28:38,250 --> 00:28:41,090 en dan, natuurlik, dit is gaan die waarde wat jy wil wees. 676 00:28:41,090 --> 00:28:42,300 So dit nie doen nie. 677 00:28:42,300 --> 00:28:44,350 >> So ons gaan om te sien of die waardes by die middel 678 00:28:44,350 --> 00:28:46,460 gelyk is aan die waarde wat ons wil hê. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Moenie jou draadjies vergeet nie. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox moet weggaan. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 So wat doen ons in hierdie geval? 685 00:28:56,200 --> 00:28:59,360 As dit is wat ons wil om terug te keer? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Ons probeer om te sê. 688 00:29:02,626 --> 00:29:03,440 >> STUDENT: Druk af. 689 00:29:03,440 --> 00:29:05,314 >> INSTRUCTOR: Wel, ons wil nie te druk nie. 690 00:29:05,314 --> 00:29:08,220 So dit is 'n Bool hier, so ons wil terugkeer waar of vals is. 691 00:29:08,220 --> 00:29:12,280 Ons sê, is hierdie getal 'n [? RRA? ?] So as dit is, 692 00:29:12,280 --> 00:29:13,788 Ons het net stuur dit waar is. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 As ek kan spel waar. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> STUDENT: Hoekom sal jy nie terug nul? 697 00:29:20,805 --> 00:29:22,930 INSTRUCTOR: So jy kan terugkeer nul as jy wil. 698 00:29:22,930 --> 00:29:26,780 Maar in hierdie geval, omdat ons funksie gee terug 'n Bool, 699 00:29:26,780 --> 00:29:28,962 Ons moet as waar of onwaar om terug te keer. 700 00:29:28,962 --> 00:29:30,920 STUDENT: As jy sê Boole-uitdrukking, 701 00:29:30,920 --> 00:29:33,450 kan jy stel dit gelyk aan vals? 702 00:29:33,450 --> 00:29:39,860 Soos as ek wil sê, as hierdie toestand nie nagekom word nie, soos is bo gelyk vals. 703 00:29:39,860 --> 00:29:42,332 Sal dit verstaan ​​as jy net sit valse aan die ander kant? 704 00:29:42,332 --> 00:29:43,040 INSTRUCTOR: Ja. 705 00:29:43,040 --> 00:29:44,820 So eintlik as jy ooit iets doen 706 00:29:44,820 --> 00:29:49,600 soos is bo of laer, wat terugkeer waar of vals 707 00:29:49,600 --> 00:29:53,850 en dit is eintlik slegte styl sê gelyk gelyk waar of gelykes 708 00:29:53,850 --> 00:29:54,840 gelyk vals. 709 00:29:54,840 --> 00:30:00,210 Jy wil hê dat die resultaat te gebruik as homself as u tjek. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Nie wat ek wou hê. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Dit is wat ek wou hê. 714 00:30:09,240 --> 00:30:13,205 So in die geval van jy vra oor iets soos stoor hierdie in c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> So as ons int main (void) en iets soos hierdie. 717 00:30:25,150 --> 00:30:31,922 En jy het as is bo van 'n paar insette en jy 718 00:30:31,922 --> 00:30:33,630 vra of jy kan doen iets soos hierdie? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Reg? 721 00:30:35,679 --> 00:30:37,470 STUDENT: Ek het probeer om dit te doen [onhoorbaar]. 722 00:30:37,470 --> 00:30:38,450 Want as it's-- 723 00:30:38,450 --> 00:30:39,200 INSTRUCTOR: Right. 724 00:30:39,200 --> 00:30:41,197 So jy wil hierdie vals is, reg? 725 00:30:41,197 --> 00:30:41,780 STUDENT: Ja. 726 00:30:41,780 --> 00:30:45,960 INSTRUCTOR: So in hierdie geval wil dit uit te voer as dit is nie waar nie. 727 00:30:45,960 --> 00:30:50,510 So die koel ding wat jy doen daar is dit. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 So onthou uitroep punt negeer dinge? 730 00:30:55,650 --> 00:30:58,270 Dit sê [onhoorbaar] beteken nie. 731 00:30:58,270 --> 00:31:03,590 So, as ons kyk na net hierdie deel hier, wil jy 732 00:31:03,590 --> 00:31:05,740 sê dat evalueer om valse as jy wil om dit te. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Nie vals is waar wat beteken dit sou voer. 735 00:31:09,880 --> 00:31:11,037 Maak dit sin maak? 736 00:31:11,037 --> 00:31:11,620 STUDENT: Ja. 737 00:31:11,620 --> 00:31:12,453 INSTRUCTOR: 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 So kan ons net terug waar in hierdie geval. 741 00:31:16,330 --> 00:31:20,357 So nou het ons twee ander gevalle in hierdie geval. 742 00:31:20,357 --> 00:31:21,565 Wat is ons twee ander gevalle? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Kom ons doen dit net op hierdie manier. 745 00:31:32,900 --> 00:31:40,660 So laat ons begin met die ander As waardes by die middel 746 00:31:40,660 --> 00:31:43,230 minder is as die waarde wat ons wil hê. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 So ons waarde in die middel is minder as die waarde wat ons soek. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> So wat gebind doen jy dink ons ​​wil om te werk? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Boonste of onderste? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Bo? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 So watter kant van die skikking gaan ons kyk na? 757 00:32:06,470 --> 00:32:07,500 >> STUDENT: Die laer. 758 00:32:07,500 --> 00:32:09,750 >> INSTRUCTOR: Ons gaan ons om te kyk na die linkerkant. 759 00:32:09,750 --> 00:32:11,120 So anders as min waarde is minder. 760 00:32:11,120 --> 00:32:14,730 Sodat jou middelste waarde hier minder is as wat ons wil hê. 761 00:32:14,730 --> 00:32:17,202 So wil ons die te neem regs van ons verskeidenheid. 762 00:32:17,202 --> 00:32:18,910 So ons gaan werk ons ​​ondergrens. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 So sal ons ons laer toewys. 765 00:32:23,020 --> 00:32:25,221 En wat dink jy laer behoort te wees? 766 00:32:25,221 --> 00:32:26,304 STUDENT: Die middelste waarde? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 INSTRUCTOR: So het die middel value-- 769 00:32:28,820 --> 00:32:30,136 STUDENT: Plus 1. 770 00:32:30,136 --> 00:32:31,010 INSTRUCTOR: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Kan iemand vir my sê hoekom Ons het dit plus 1? 773 00:32:34,380 --> 00:32:35,730 >> STUDENT: [? Geen waarde?] meer gelyk aan dit. 774 00:32:35,730 --> 00:32:36,120 >> INSTRUCTOR: Right. 775 00:32:36,120 --> 00:32:38,661 Omdat ons reeds weet dat ons middelste waarde is nie gelyk aan 776 00:32:38,661 --> 00:32:42,750 en ons wil om dit te sluit van alle daaropvolgende navrae. 777 00:32:42,750 --> 00:32:46,360 As jy vergeet dat plus 1, hierdie sal graag lus vir onbepaalde tyd. 778 00:32:46,360 --> 00:32:49,620 En jy sal net in 'n gevang word oneindige lus, en dan sal jy segfault 779 00:32:49,620 --> 00:32:50,370 en dinge gaan sleg. 780 00:32:50,370 --> 00:32:54,780 So maak seker dat jy nie insluitend die waarde wat jy net 781 00:32:54,780 --> 00:32:55,380 gekyk. 782 00:32:55,380 --> 00:32:58,530 So ons sorg dat ons met 'n plus 1. 783 00:32:58,530 --> 00:33:04,840 >> So nou het ons ons laaste voorwaarde wat ek altyd ter wille van veiligheid 784 00:33:04,840 --> 00:33:12,664 jy hier kan sien, anders as waarde op die middel is groter as die waarde 785 00:33:12,664 --> 00:33:13,163 ons wil hê. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Dit beteken dat ons wil die linkerhand helfte. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 So watter een gaan ons te werk? 790 00:33:23,260 --> 00:33:23,760 Boonste. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 En wat is hierdie een gaan gelyk? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Midde minus 1 omdat natuurlik, ons wil 795 00:33:33,690 --> 00:33:38,370 om seker te maak dat ons nie ' soek weer op daardie middelste waarde. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 En dan het ons dit. 798 00:33:45,110 --> 00:33:45,610 Dit is dit. 799 00:33:45,610 --> 00:33:46,820 Dit is al wat binêre soek is. 800 00:33:46,820 --> 00:33:48,190 Dit is nie so sleg nie, reg? 801 00:33:48,190 --> 00:33:51,590 Dit is soos 10 reëls van kode met wit ruimte. 802 00:33:51,590 --> 00:33:57,510 So baie sterk, baie nuttig, sal jy wees om dit te gebruik in een van jou later psets. 803 00:33:57,510 --> 00:33:59,360 Miskien nie hierdie een nie, maar later. 804 00:33:59,360 --> 00:34:00,670 So leer. 805 00:34:00,670 --> 00:34:01,510 Mal daaroor. 806 00:34:01,510 --> 00:34:02,980 Dit sal jou goed behandel. 807 00:34:02,980 --> 00:34:05,370 So het iemand enige vrae oor binêre soek? 808 00:34:05,370 --> 00:34:06,196 Ja. 809 00:34:06,196 --> 00:34:09,840 >> STUDENT: Maak dit saak of jou n ewe of onewe? 810 00:34:09,840 --> 00:34:10,750 >> INSTRUCTOR: No. 811 00:34:10,750 --> 00:34:18,150 Omdat ons dit gegooi in die middel as 'n int, dit sal net dit afgebreek word. 812 00:34:18,150 --> 00:34:21,600 So sal dit 'n heelgetal te bly en dit sal uiteindelik sorteer deur middel van alles. 813 00:34:21,600 --> 00:34:23,909 Sodat jy nie hoef te bekommer oor dat. 814 00:34:23,909 --> 00:34:24,580 Almal goeie? 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 Cool. 818 00:34:27,919 --> 00:34:30,836 So, julle het hierdie. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Skyfievertoning. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 So as ons praat, ek weet David genoem kompleksiteit Runtimes. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> So in die beste geval, dit is net een, wat ons noem konstante tyd. 825 00:34:50,340 --> 00:34:51,909 Kan iemand vir my sê hoekom dit kan wees? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Watter tipe scenario sou dit behels? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> STUDENT: [onhoorbaar] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 INSTRUCTOR: So het die middel om die eerste element wat ons kom na, reg? 833 00:35:03,830 --> 00:35:08,167 So óf 'n verskeidenheid van een of alles wat ons is op soek na net 834 00:35:08,167 --> 00:35:09,750 gebeur smack schar in die middel te wees. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 So dit is ons beste geval. 837 00:35:13,380 --> 00:35:17,540 Jy kry in die werklike probleme, waarskynlik nie gaan wat dikwels bereik [onhoorbaar]. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 Wat van ons ergste geval? 840 00:35:19,750 --> 00:35:21,270 Ons ergste geval is log n. 841 00:35:21,270 --> 00:35:25,360 En wat te doen het met die hele magte van twee ding wat ek het gepraat oor. 842 00:35:25,360 --> 00:35:30,930 >> So in die ergste geval, sou dit beteken wat ons gehad het die skikking af te kap 843 00:35:30,930 --> 00:35:33,270 totdat dit 'n element van die een. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 So ons moes dit af te kap in die helfte soveel keer as wat ons moontlik kan. 846 00:35:38,930 --> 00:35:41,430 Dit is waarom dit is log N omdat jy hou net deur twee te deel. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 So aannames, dinge wat jy nodig het om te weet as jy ooit 849 00:35:45,830 --> 00:35:48,050 gaan 'n binêre soek om te gebruik. 850 00:35:48,050 --> 00:35:50,680 Jou elemente moet uitgesorteer word. 851 00:35:50,680 --> 00:35:53,890 Hulle moet gesorteer word nie omdat dit is die enigste manier waarop jy 852 00:35:53,890 --> 00:35:57,060 kan weet as jy in staat is om uit te gooi die helfte van dit. 853 00:35:57,060 --> 00:36:00,260 >> As jy het hierdie deurmekaar sak van getalle en jy sê, 854 00:36:00,260 --> 00:36:05,380 OK, ek gaan die middel te gaan en die aantal Ek is op soek na 855 00:36:05,380 --> 00:36:08,510 is minder as dit, ek gaan net arbitrêr gooi die een helfte. 856 00:36:08,510 --> 00:36:11,130 Jy sal nie weet of jou getalle in die ander helfte. 857 00:36:11,130 --> 00:36:12,655 Jou lys moet gesorteer word. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Asook, kan dit wees voort te gaan om 'n bietjie, 860 00:36:16,560 --> 00:36:18,360 maar jy moet ewekansige toegang te hê. 861 00:36:18,360 --> 00:36:21,940 Jy moet in staat wees om net gaan na die middel element. 862 00:36:21,940 --> 00:36:25,110 As jy het om te deurkruis deur iets 863 00:36:25,110 --> 00:36:28,630 of dit neem jou ekstra stappe te kry om dit middel element, 864 00:36:28,630 --> 00:36:31,750 dit is nie inteken N nie, want nie meer werk toe te voeg in dit. 865 00:36:31,750 --> 00:36:34,800 En dit sal 'n bietjie te maak meer sin in twee weke, 866 00:36:34,800 --> 00:36:37,950 maar ek het net soort wou voorwoord, gee julle 'n idee van wat 867 00:36:37,950 --> 00:36:38,999 te kom. 868 00:36:38,999 --> 00:36:40,790 Maar dit is die twee belangrike aannames 869 00:36:40,790 --> 00:36:44,804 wat jy nodig het vir 'n binêre lys. 870 00:36:44,804 --> 00:36:45,720 Maak seker dit is gesorteer. 871 00:36:45,720 --> 00:36:47,920 Dit is die groot een vir julle nou. 872 00:36:47,920 --> 00:36:52,170 En dat ons kan gaan in die res van ons spesies. 873 00:36:52,170 --> 00:36:56,444 So vier sorts-- borrel, plasing, seleksie, en voeg. 874 00:36:56,444 --> 00:36:57,485 Hulle is al die soort van cool. 875 00:36:57,485 --> 00:37:02,860 As jy ouens besluit CS 124 te neem, sal jy leer oor allerhande soorte. 876 00:37:02,860 --> 00:37:07,575 En as jy 'n Kletskerk fan, daar is 'n baie cool komiese oor 877 00:37:07,575 --> 00:37:11,530 soos baie oneffektief vorme, wat ek raai jy gaan om te kyk na. 878 00:37:11,530 --> 00:37:16,170 Een van hulle is soos paniek soort, wat is soos, o nee, terugkeer ewekansige skikking. 879 00:37:16,170 --> 00:37:16,991 Afsluit stelsel. 880 00:37:16,991 --> 00:37:17,490 Verlaat. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 So geeky humor is altyd goed. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> So nie almal soort onthou van soos net 'n algemene idee 885 00:37:25,750 --> 00:37:27,810 hoe borrel soort werk. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Jy onthou? 888 00:37:32,155 --> 00:37:32,755 >> STUDENT: Ja. 889 00:37:32,755 --> 00:37:33,970 >> INSTRUCTOR: Gaan vir dit. 890 00:37:33,970 --> 00:37:38,980 >> STUDENT: So jy gaan en As dit is groter, dan kan jy ruil die twee. 891 00:37:38,980 --> 00:37:39,820 >> INSTRUCTOR: MM-hm. 892 00:37:39,820 --> 00:37:40,564 Presies. 893 00:37:40,564 --> 00:37:41,730 Sodat jy net Itereer deur. 894 00:37:41,730 --> 00:37:43,050 Jy is so twee getalle. 895 00:37:43,050 --> 00:37:46,510 As die een is voor groter as die een daarna, 896 00:37:46,510 --> 00:37:50,230 jy net ruil hulle so dat in hierdie manier al die hoër getalle 897 00:37:50,230 --> 00:37:54,990 borrel teen die einde van die lys en al die laer getalle borrel af. 898 00:37:54,990 --> 00:37:59,355 >> Het hy wys julle ouens die koel klank effek sorteer video? 899 00:37:59,355 --> 00:38:00,480 Dit is soort van cool. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 So as Robert het net gesê, die algoritme dat jy net stap vir stap deur die lys, 902 00:38:05,200 --> 00:38:07,930 uitruiling aangrensende waardes as hulle nie in orde is. 903 00:38:07,930 --> 00:38:10,975 En dan hou net herhaal totdat jy maak nie enige verteenwoordig. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 So nie sleg nie, reg? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 So ons moet net 'n vinnige voorbeeld hier. 908 00:38:16,319 --> 00:38:18,360 So dit gaan om te sorteer hulle in stygende volgorde. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 So wanneer ons deur die eerste tyd, ons kyk deur agt 911 00:38:23,470 --> 00:38:26,880 en ses is natuurlik nie in orde, ons ruil hulle. 912 00:38:26,880 --> 00:38:27,985 >> So kyk na die volgende een. 913 00:38:27,985 --> 00:38:29,430 Agt en vier nie in orde is. 914 00:38:29,430 --> 00:38:30,450 Ruil hulle. 915 00:38:30,450 --> 00:38:32,530 En dan agt en twee, ruil hulle. 916 00:38:32,530 --> 00:38:33,470 Daar gaan ons. 917 00:38:33,470 --> 00:38:39,519 So na jou eerste slaag, moet jy weet dat jou grootste getal 918 00:38:39,519 --> 00:38:41,810 gaan al die pad wees by die top, want dit is net 919 00:38:41,810 --> 00:38:44,210 gaan voortdurend groter as alles anders 920 00:38:44,210 --> 00:38:46,810 en dit is net gaan om te borrel tot al die pad na die einde daar. 921 00:38:46,810 --> 00:38:48,226 Doen wat sin maak vir almal? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Cool. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> So dan is ons kyk na ons tweede slaag. 926 00:38:53,920 --> 00:38:54,980 Ses en vier, skakel. 927 00:38:54,980 --> 00:38:55,920 Ses en twee, skakel. 928 00:38:55,920 --> 00:38:58,700 En nou het ons 'n paar dinge in orde is. 929 00:38:58,700 --> 00:39:02,240 So vir elke pass dat ons maak deur ons hele lys, 930 00:39:02,240 --> 00:39:06,320 ons weet dat net soos wat baie nommers aan die einde sal uitgesorteer het. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 So ons doen 'n derde slaag, Dit is een omruil. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 En dan op ons vierde slaag, het ons 'n nul slots. 935 00:39:15,910 --> 00:39:18,570 En so weet ons dat ons skikking is gesorteer. 936 00:39:18,570 --> 00:39:20,900 >> En dit is die groot ding met borrel soort. 937 00:39:20,900 --> 00:39:23,720 Ons weet dat wanneer ons nul swaps, wat 938 00:39:23,720 --> 00:39:26,497 beteken dat alles is in 'n volledige orde. 939 00:39:26,497 --> 00:39:27,580 Dit is soort van hoe ons gaan. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 So is ons ook gaan borrel te kodeer soort wat ook nie so sleg nie. 942 00:39:36,480 --> 00:39:38,120 Nie een van hierdie is so sleg nie. 943 00:39:38,120 --> 00:39:40,210 Ek weet hulle kan lyk 'n bietjie scary. 944 00:39:40,210 --> 00:39:42,124 Ek weet toe ek die klas, selfs wanneer ek 945 00:39:42,124 --> 00:39:44,290 is die onderrig van die klas vir die eerste keer verlede jaar, 946 00:39:44,290 --> 00:39:46,165 Ek was soos, hoe doen ek dit? 947 00:39:46,165 --> 00:39:48,540 Dit maak sin in teorie, maar hoe ons eintlik doen dit? 948 00:39:48,540 --> 00:39:51,420 Dit is waarom ek wil ook so te wandel deur kode met julle ouens hier. 949 00:39:51,420 --> 00:39:54,915 So ek het 'n pseudokode vir julle hierdie tyd. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Dus net dit in gedagte hou as ons is oor die oorgang oor. 952 00:39:58,970 --> 00:40:04,210 So ons het 'n paar counter dat hou van ons swaps, 953 00:40:04,210 --> 00:40:08,370 omdat ons nodig het om seker te maak dat ons seker te maak dat. 954 00:40:08,370 --> 00:40:11,830 En ons Itereer die hele skikking as ons nou net gedoen met hierdie voorbeeld. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 As die element voor groter as die element na waar ons op, 957 00:40:17,325 --> 00:40:20,760 ruil ons hulle en ons inkrementeer ons counter want sodra ons ruil, 958 00:40:20,760 --> 00:40:23,850 ons wil laat ons counter weet dat. 959 00:40:23,850 --> 00:40:26,247 Enige vrae is daar? 960 00:40:26,247 --> 00:40:27,580 Iets lyk snaaks hier. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 STUDENT: stel jy die toonbank tot nul elke keer as jy gaan deur die loop? 963 00:40:32,350 --> 00:40:34,339 Hou jy nie gaan elke keer terug na nul? 964 00:40:34,339 --> 00:40:35,505 INSTRUCTOR: Nie noodwendig nie. 965 00:40:35,505 --> 00:40:39,710 So, wat gebeur is dat ons gaan hier deur. 966 00:40:39,710 --> 00:40:43,830 So doen terwyl, onthou, hierdie sal weer uit te voer sonder versuim. 967 00:40:43,830 --> 00:40:46,480 So dit gaan die te stel counter gelyk aan nul, 968 00:40:46,480 --> 00:40:48,070 dan is dit gaan om deur te Itereer. 969 00:40:48,070 --> 00:40:50,590 As dit iterate deur, dit sal werk toonbank. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 As dit updates toonbank, wanneer dit gedoen is, wanneer dit aan die einde van die skikking, 972 00:40:56,900 --> 00:41:00,830 As ons lys is nie gesorteer, counter sal opgedateer het. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> So dan is dit gaan die toestand en dit sê, OK, is teen groter as nul. 975 00:41:07,150 --> 00:41:09,290 As dit is, dit weer doen. 976 00:41:09,290 --> 00:41:14,340 Jy wil so dat wanneer jy weer gaan deur, counter is gelyk aan nul. 977 00:41:14,340 --> 00:41:18,240 As jy gaan deur 'n gesorteerde skikking, niks verander nie, 978 00:41:18,240 --> 00:41:21,355 dit misluk, en jy terugkeer om die lys gesorteer. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Doen wat sin maak? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 STUDENT: Dit mag in 'n bietjie. 983 00:41:26,356 --> 00:41:27,147 INSTRUCTOR: OK. 984 00:41:27,147 --> 00:41:28,980 As daar enige ander vraag wat opkom. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Ja. 987 00:41:30,680 --> 00:41:33,760 >> STUDENT: Wat sou die funksie wees vir die uitruiling van die elemente? 988 00:41:33,760 --> 00:41:36,900 >> INSTRUCTOR: So kan ons eintlik skryf dat as ons gaan nou reg te stel. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Cool. 991 00:41:38,300 --> 00:41:42,155 So op daardie noot, is Alison gaan terug te keer na die toestel skakel. 992 00:41:42,155 --> 00:41:43,080 Dit gaan pret wees. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 En ons het ons mooi borrel soort ding hier. 995 00:41:47,390 --> 00:41:50,800 So ek reeds gedoen het fietsry deur die skikking. 996 00:41:50,800 --> 00:41:53,030 Ons het ons swaps wat is gelyk aan nul. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 So ons wil ruil aangrensende elemente as hulle buite orde. 999 00:41:58,440 --> 00:42:03,020 So die eerste ding wat ons nodig het om te doen, is Itereer deur ons verskeidenheid. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> So hoe dink jy ons kan Itereer deur ons verskeidenheid? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Ons het vir en ek is gelyk aan 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Ons wil ek minder te wees as n minus 1 minus k. 1006 00:42:22,454 --> 00:42:23,870 En Ek sal verduidelik wat in 'n tweede. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 So, dit is 'n optimalisering hier waar, onthou hoe ek gesê het na elke pass 1009 00:42:32,830 --> 00:42:36,655 deur die skikking ons weet dat net die on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> So na 'n pass ons weet dat dit gesorteer is. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Na twee aangeë ons weet dat dit alles gesorteer. 1014 00:42:50,060 --> 00:42:52,750 Na drie aangeë ons weet dit is gesorteer. 1015 00:42:52,750 --> 00:42:55,620 So die manier waarop ek iterating deur die skikking hier 1016 00:42:55,620 --> 00:43:01,090 is dit om seker te maak om net te gaan deur middel van wat ons weet, is ongesorteerde. 1017 00:43:01,090 --> 00:43:01,644 OK? 1018 00:43:01,644 --> 00:43:02,810 Dit is net 'n optimalisering. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Jy kan dit naïef skryf net iterating deur alles, 1021 00:43:08,210 --> 00:43:09,970 sou dit net langer neem. 1022 00:43:09,970 --> 00:43:12,470 Met hierdie vier lus is dit net 'n mooi optimalisering 1023 00:43:12,470 --> 00:43:18,460 omdat ons weet dat na elke volledige iterasie deur die skikking hier 1024 00:43:18,460 --> 00:43:24,050 soos elke volle lus hier is, weet ons dat 'n mens meer van hierdie elemente 1025 00:43:24,050 --> 00:43:25,760 sal gesorteer word aan die einde. 1026 00:43:25,760 --> 00:43:28,294 >> Sodat ons nie hoef te bekommer oor hulle. 1027 00:43:28,294 --> 00:43:29,710 Doen wat sin maak vir almal? 1028 00:43:29,710 --> 00:43:30,950 Dit koel bietjie truuk? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 So in daardie geval, indien ons iterating deur, 1031 00:43:37,270 --> 00:43:50,590 ons weet wat ons wil om te kyk of skikking N en N plus 1 in orde is. 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 So hier is die pseudokode. 1035 00:43:54,600 --> 00:43:57,540 Ons wil om te kyk of skikking N en N plus 1 in orde is. 1036 00:43:57,540 --> 00:43:59,520 So, wat kan ons daar? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Dit gaan 'n voorwaardelike wees. 1039 00:44:03,120 --> 00:44:04,220 Dit sal 'n as. 1040 00:44:04,220 --> 00:44:07,066 >> STUDENT: As skikking N is minder as skikking N plus 1. 1041 00:44:07,066 --> 00:44:07,816 INSTRUCTOR: MM-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Wel, minder as of groter as. 1044 00:44:10,699 --> 00:44:11,615 STUDENT: Meer as. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Dan wil ons hulle te ruil. 1047 00:44:17,620 --> 00:44:18,570 Presies. 1048 00:44:18,570 --> 00:44:23,570 So nou kry ons in wat die meganisme vir die uitruiling hulle? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 So het ons deur hierdie kort, 'n tipe van ruil-funksie verlede week. 1051 00:44:28,137 --> 00:44:29,595 Is daar iemand onthou hoe dit gewerk het? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 So kan ons nie net toewys hulle, reg? 1054 00:44:34,950 --> 00:44:36,640 Omdat een van hulle verlore sal gaan nie. 1055 00:44:36,640 --> 00:44:41,696 As ons sê A is gelyk aan B en dan B is gelyk aan A, al 'n skielike beide van hulle 1056 00:44:41,696 --> 00:44:43,150 is net gelyk aan B. 1057 00:44:43,150 --> 00:44:45,720 >> So wat ons moet doen, is om ons 'n tydelike veranderlike wat 1058 00:44:45,720 --> 00:44:49,055 gaan een van ons s'n, terwyl te hou Ons is in die proses van uitruiling. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 So, wat ons het, is ons sal 'n paar int het temp is gelyk aan- jy dit kan wys 1061 00:44:56,464 --> 00:44:59,130 om watter een jy wil, net maak seker dat jy die spoor van it-- hou 1062 00:44:59,130 --> 00:45:01,840 So in hierdie geval, ek gaan toewys om dit te skikking N plus 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 So wat gaan hou wat waarde is in die tweede blok 1065 00:45:07,674 --> 00:45:08,590 dat ons is op soek na. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> En dan het ons kan doen is om ons kan gaan voor en toewys skikking N plus 1, 1068 00:45:13,240 --> 00:45:14,990 omdat ons weet dat ons het wat waarde gestoor. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Dit is ook een van die groot things-- Ek weet nie of enige van julle 1071 00:45:19,270 --> 00:45:23,780 het probleme waar as jy oorskakel twee reëls van die kode skielik dinge gewerk het. 1072 00:45:23,780 --> 00:45:25,880 Orde is baie belangrik in die CS. 1073 00:45:25,880 --> 00:45:29,450 So maak seker dat jy diagram dinge uit indien moontlik 1074 00:45:29,450 --> 00:45:31,230 oor wat eintlik gebeur. 1075 00:45:31,230 --> 00:45:34,256 So nou gaan ons toewys skikking N plus 1, 1076 00:45:34,256 --> 00:45:36,005 omdat ons weet dat ons het wat waarde gestoor. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> En ons kan wys wat aan skikking N of in hierdie geval verskeidenheid i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Te veel veranderlikes. 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 So nou het ons oorgeplaas verskeidenheid i plus 1 tot gelyke wat is opgestel i. 1084 00:46:01,500 --> 00:46:08,240 En nou kan ons teruggaan en toewys verskeidenheid i na wat? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Iemand? 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 >> INSTRUCTOR: 10. 1090 00:46:14,680 --> 00:46:15,180 Presies. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 En een laaste ding. 1093 00:46:18,640 --> 00:46:21,840 As ons nou omgeruil het, wat moet ons doen? 1094 00:46:21,840 --> 00:46:23,740 Wat is die een ding wat gaan om ons te vertel 1095 00:46:23,740 --> 00:46:27,542 As ons ooit hierdie program beëindig? 1096 00:46:27,542 --> 00:46:29,250 Wat vertel ons dat ons 'n gesorteerde lys? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 As ons nie enige swaps presteer nie, reg? 1099 00:46:33,750 --> 00:46:36,900 As swaps is gelyk aan nul aan die einde van hierdie. 1100 00:46:36,900 --> 00:46:42,975 So wanneer jy voer 'n ruil, soos ons net hier gedoen het, wil ons swaps te werk. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 En ek weet daar was 'n vraag vroeër oor wat jy kan 1103 00:46:47,210 --> 00:46:49,689 gebruik nul of een plaas van waar of vals is. 1104 00:46:49,689 --> 00:46:50,980 En dit is wat dit beteken hier. 1105 00:46:50,980 --> 00:46:52,750 So dit sê indien nie verteenwoordig. 1106 00:46:52,750 --> 00:47:01,310 So as swaps is nul, wat is-- Ek het altyd kry my waarhede en my falses deurmekaar. 1107 00:47:01,310 --> 00:47:03,960 Ons wil hê ons moet evalueer waar en dit is nie. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 So as dit is zero, dan is dit vals. 1110 00:47:09,630 --> 00:47:12,560 As jy dit ontken met 'n [? bang?] dit waar is. 1111 00:47:12,560 --> 00:47:13,975 So dan hierdie lyn voer. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Waarhede en valse en nulle en ene kry mal. 1114 00:47:17,370 --> 00:47:20,690 Net as jy stadig loop deur dit sal sin maak. 1115 00:47:20,690 --> 00:47:23,320 Maar dit is wat hierdie klein bietjie van die kode hier doen. 1116 00:47:23,320 --> 00:47:26,490 So hierdie tjeks om te sien het ons gedoen om enige verteenwoordig. 1117 00:47:26,490 --> 00:47:30,054 So as dit is iets anders nul, gaan dit vals te wees 1118 00:47:30,054 --> 00:47:31,970 en die hele ding is weer gaan voer. 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: Wat beteken break doen? 1123 00:47:36,000 --> 00:47:38,990 >> INSTRUCTOR: Breek net breek jy uit van die lus. 1124 00:47:38,990 --> 00:47:41,570 So in hierdie geval sou dit wil slegs die einde van die program 1125 00:47:41,570 --> 00:47:43,828 en jy wil net jou gesorteer lys. 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 INSTRUCTOR: Ek is jammer? 1129 00:47:49,010 --> 00:47:52,110 STUDENT: Omdat voorheen ons gebruik is geskryf 1 oor geskryf nul 1130 00:47:52,110 --> 00:47:54,170 wat aan te bied as wat sal werk of nie. 1131 00:47:54,170 --> 00:47:54,878 >> INSTRUCTOR: Ja. 1132 00:47:54,878 --> 00:47:56,410 Sodat jy kan terug nul of 1. 1133 00:47:56,410 --> 00:47:58,950 In hierdie geval, want ons is nie eintlik om iets te doen met die funksie, 1134 00:47:58,950 --> 00:48:00,150 ons wil net om dit te breek. 1135 00:48:00,150 --> 00:48:02,680 Ons het nie regtig omgee oor dit. 1136 00:48:02,680 --> 00:48:06,960 Brake is ook goed as dit gebruik word vir die breek 1137 00:48:06,960 --> 00:48:10,710 vier sirkelroetes of toestande wat jy nie wil hê om te hou die uitvoering. 1138 00:48:10,710 --> 00:48:12,110 Dit neem jy net uit hulle. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 Dit is 'n bietjie van 'n nuanse ding. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Ek voel daar is 'n baie van die hand swaai, 1143 00:48:18,445 --> 00:48:19,740 soos jy sal leer oor hierdie gou. 1144 00:48:19,740 --> 00:48:20,955 >> Maar jy sal leer oor dit binnekort. 1145 00:48:20,955 --> 00:48:21,500 Ek belowe. 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 So het almal kry borrel soort? 1149 00:48:24,840 --> 00:48:25,550 Nie te sleg nie. 1150 00:48:25,550 --> 00:48:31,910 Itereer deurgaan nie, ruil kosse met 'n tydelike veranderlike, en ons is almal daar te vestig? 1151 00:48:31,910 --> 00:48:32,960 Cool. 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 Terug na die PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Enige vrae in die algemeen oor hierdie so ver? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Cool. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> STUDENT: [onhoorbaar] int main gewoonlik. 1162 00:48:45,279 --> 00:48:46,695 Het jy wat vir hierdie te hê? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> INSTRUCTOR: Ons is net op soek na net op die werklike sorteringsalgoritme. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 As jy dit binne soos 'n groter program, 1167 00:48:56,350 --> 00:48:57,891 jy sal moet 'n int main iewers. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 Afhangende van waar jy gebruik hierdie algoritme 1170 00:49:02,880 --> 00:49:05,860 dit sal bepaal wat is teruggestuur word deur dit. 1171 00:49:05,860 --> 00:49:09,960 Maar vir ons geval, ons is streng kyk na hoe dit eintlik 1172 00:49:09,960 --> 00:49:11,300 Itereer deur 'n skikking. 1173 00:49:11,300 --> 00:49:12,570 Sodat ons nie daaroor bekommer nie. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> So ons praat oor die beste geval en ergste geval scenario's vir binêre soek. 1176 00:49:19,830 --> 00:49:22,470 So is dit ook belangrik om te doen wat vir elkeen van ons spesies. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 So, wat dink jy is die ergste geval runtime van borrel soort? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Julle onthou? 1181 00:49:30,700 --> 00:49:31,784 >> STUDENT: N minus 1. 1182 00:49:31,784 --> 00:49:32,700 INSTRUCTOR: N minus 1. 1183 00:49:32,700 --> 00:49:35,070 Dus beteken dit dat daar N minus 1 vergelykings. 1184 00:49:35,070 --> 00:49:40,060 So een ding om te besef is wat op die eerste iterasie, 1185 00:49:40,060 --> 00:49:43,360 ons gaan deur, ons vergelyk hierdie two-- so dit is 1. 1186 00:49:43,360 --> 00:49:46,685 Hierdie twee, drie, vier. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 So na een iterasie ons reeds vier vergelykings. 1189 00:49:55,050 --> 00:49:58,230 Wanneer ek praat runtime en n. 1190 00:49:58,230 --> 00:50:04,680 N verteenwoordig die aantal vergelykings as 'n funksie van hoeveel elemente 1191 00:50:04,680 --> 00:50:05,570 ons het. 1192 00:50:05,570 --> 00:50:06,430 OK? 1193 00:50:06,430 --> 00:50:08,860 >> So gaan ons deur ons vier. 1194 00:50:08,860 --> 00:50:11,780 Die volgende keer wat jy weet ons dit nie doen nie het om te sorg van hierdie. 1195 00:50:11,780 --> 00:50:15,140 Ons vergelyk hierdie twee, hierdie twee, die twee, 1196 00:50:15,140 --> 00:50:20,050 en as ons nie daardie optimalisering met die vier lus wat ek geskryf het, 1197 00:50:20,050 --> 00:50:22,750 jy sal vergelyk word hier anyways. 1198 00:50:22,750 --> 00:50:26,170 So jy sal moet loop deur die skikking 1199 00:50:26,170 --> 00:50:34,380 en maak n vergelykings N keer nie, want elke keer as ons 1200 00:50:34,380 --> 00:50:36,670 loop deur dit soort een ding wat ons. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> En elke keer as ons loop deur die skikking, maak ons ​​n vergelykings. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Sodat ons runtime hiervoor is eintlik n vierkant, wat 1205 00:50:46,330 --> 00:50:48,400 is veel erger in ons teken einde, want dit 1206 00:50:48,400 --> 00:50:51,965 beteken dat as ons het vier miljard elemente, is dit 1207 00:50:51,965 --> 00:50:55,260 gaan ons 4000000000 te neem vierkantig plaas uit 32. 1208 00:50:55,260 --> 00:51:01,240 So nie die beste runtime, maar vir 'n paar dinge, 1209 00:51:01,240 --> 00:51:04,610 jy weet, as jy binne 'n sekere verskeidenheid van elemente 1210 00:51:04,610 --> 00:51:06,540 borrel soort kan fyn te gebruik. 1211 00:51:06,540 --> 00:51:07,530 >> OK. 1212 00:51:07,530 --> 00:51:12,290 So nou, wat is die beste geval runtime? 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 Of 1? 1216 00:51:16,420 --> 00:51:18,140 >> INSTRUCTOR: So 1 sou een vergelyking. 1217 00:51:18,140 --> 00:51:19,114 Right. 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 >> INSTRUCTOR: So, ja. 1221 00:51:22,320 --> 00:51:22,990 So n minus 1. 1222 00:51:22,990 --> 00:51:26,510 Wanneer jy 'n konsep soos n minus 1, is ons geneig om net gooi dit af 1223 00:51:26,510 --> 00:51:31,680 en ons net sê N, want jy het elk van these-- elke paar te vergelyk. 1224 00:51:31,680 --> 00:51:36,470 So dit sou wees n minus 1, wat ons Ons wil net sê, is ongeveer N. 1225 00:51:36,470 --> 00:51:39,280 Wanneer jy met runtime, alles is in benadering. 1226 00:51:39,280 --> 00:51:43,860 Solank as wat die eksponent korrek is, is jy redelik goed. 1227 00:51:43,860 --> 00:51:45,700 >> Dit is hoe ons dit hanteer. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 Sodat die beste geval is N, wat beteken dat die lys is reeds gesorteer is, 1230 00:51:51,780 --> 00:51:54,320 en alles wat ons doen is loop deur en seker te maak dat dit gesorteer. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Cool. 1233 00:51:56,855 --> 00:51:57,355 Alle regte. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 So as jy hier sien, het ons net 'n paar meer grafieke. 1236 00:52:01,920 --> 00:52:02,660 So n vierkant. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Pret. 1239 00:52:05,120 --> 00:52:09,730 Veel erger as N as ons sien, en baie, baie erger as log 2n. 1240 00:52:09,730 --> 00:52:12,060 En dan kry jy ook by log stompe. 1241 00:52:12,060 --> 00:52:18,020 En jy neem 124, kry jy in soos log ster, wat soos mal. 1242 00:52:18,020 --> 00:52:20,172 So as jy belangstel, soek log ster. 1243 00:52:20,172 --> 00:52:20,880 Dit is soort van pret. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 So ons het hierdie groot grafiek. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Net 'n kop, dit 'n wonderlike grafiek te hê 1248 00:52:28,720 --> 00:52:31,350 vir jou mid-term, want ons lank jy hierdie verdunt te stel. 1249 00:52:31,350 --> 00:52:36,090 Dus net 'n kop, het dit op jou mid-term op jou mooi oneerlik blad 1250 00:52:36,090 --> 00:52:36,616 daar. 1251 00:52:36,616 --> 00:52:37,990 Sodat ons net kyk na borrel soort. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Ergste geval, n vierkant, die beste geval, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 En ons gaan om te kyk na die ander. 1256 00:52:44,950 --> 00:52:47,940 >> En soos jy kan sien, is die enigste een wat regtig goed 1257 00:52:47,940 --> 00:52:50,910 is merge soort, wat ons kry in waarom. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 So ons gaan om te gaan na die volgende een here-- seleksie soort. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Is daar iemand onthou hoe seleksie soort gewerk? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Gaan vir dit. 1264 00:53:05,700 --> 00:53:08,210 >> STUDENT: Eintlik gaan deur 'n bevel en die skep van 'n nuwe lys. 1265 00:53:08,210 --> 00:53:11,001 En net soos jy om elemente in, sit hulle in die regte plek 1266 00:53:11,001 --> 00:53:11,750 in die nuwe lys. 1267 00:53:11,750 --> 00:53:14,040 >> INSTRUCTOR: So wat klanke meer soos invoeging soort. 1268 00:53:14,040 --> 00:53:15,040 Maar jy is baie naby. 1269 00:53:15,040 --> 00:53:15,915 Hulle is baie soortgelyk. 1270 00:53:15,915 --> 00:53:17,440 Selfs ek kry hulle deurmekaar soms. 1271 00:53:17,440 --> 00:53:18,981 Voordat hierdie artikel Ek was soos, wag. 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 So wat jy wil doen, is seleksie soort, 1275 00:53:24,141 --> 00:53:25,890 die manier waarop jy kan dink oor dit en die manier waarop 1276 00:53:25,890 --> 00:53:30,140 Ek maak seker ek probeer om nie te kry hulle deurmekaar, is dit gaan deur 1277 00:53:30,140 --> 00:53:33,280 en dit kies die kleinste getal en dit 1278 00:53:33,280 --> 00:53:36,070 plaas wat aan die begin van die lys. 1279 00:53:36,070 --> 00:53:37,730 Dit ruil dit met die eerste plek. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 Hulle het eintlik 'n voorbeeld vir my. 1282 00:53:45,370 --> 00:53:46,540 Awesome. 1283 00:53:46,540 --> 00:53:50,130 So net 'n manier om te dink it-- seleksie sorteer, kies die kleinste waarde. 1284 00:53:50,130 --> 00:53:51,940 En ons gaan loop deur 'n voorbeeld 1285 00:53:51,940 --> 00:53:55,320 wat ek dink sal help, want Ek dink beeldmateriaal altyd help. 1286 00:53:55,320 --> 00:53:58,510 So het ons begin met iets dit is heeltemal ongesorteerde. 1287 00:53:58,510 --> 00:54:00,730 Rooi sal ongesorteerde wees, groen sal gesorteer word. 1288 00:54:00,730 --> 00:54:02,190 Dit sal al sin maak in 'n tweede. 1289 00:54:02,190 --> 00:54:08,950 >> So gaan ons deur en ons Itereer van die begin tot die einde. 1290 00:54:08,950 --> 00:54:12,320 En ons sê, OK, 2 is ons kleinste getal. 1291 00:54:12,320 --> 00:54:15,680 So ons gaan neem 2 en ons gaan om dit te skuif na die voorkant van ons verskeidenheid 1292 00:54:15,680 --> 00:54:17,734 want dit is die kleinste getal wat ons het. 1293 00:54:17,734 --> 00:54:19,150 So dit is wat dit is hier om te doen. 1294 00:54:19,150 --> 00:54:20,820 Dit is net gaan die twee te ruil. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 So nou het ons 'n gesorteer deel en 'n ongesorteerde deel. 1297 00:54:25,450 --> 00:54:27,810 En wat is goed om te onthou oor seleksie soort 1298 00:54:27,810 --> 00:54:30,690 is ons net kies uit die ongesorteerde deel. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> Die gesorteer deel jy net uitlos. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> STUDENT: Hoe weet wat die kleinste, sonder dat dit te vergelyk 1303 00:54:38,452 --> 00:54:39,868 elke ander waarde in die skikking. 1304 00:54:39,868 --> 00:54:41,250 INSTRUCTOR: Dit maak dit vergelyk. 1305 00:54:41,250 --> 00:54:42,041 Ons hou oorgeslaan nie. 1306 00:54:42,041 --> 00:54:43,850 Dit is net 'n algemene algehele. 1307 00:54:43,850 --> 00:54:44,831 Ja. 1308 00:54:44,831 --> 00:54:47,205 Wanneer ons skryf die kode ek seker jy sal meer tevrede wees. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Maar jy slaan die eerste element as die kleinste. 1311 00:54:53,030 --> 00:54:56,110 Jy kan vergelyk en u sê, OK, is dit kleiner? 1312 00:54:56,110 --> 00:54:56,660 Ja. 1313 00:54:56,660 --> 00:54:57,460 Hou dit. 1314 00:54:57,460 --> 00:54:58,640 Hier is dit kleiner? 1315 00:54:58,640 --> 00:54:59,660 Geen? 1316 00:54:59,660 --> 00:55:02,510 >> Dit is jou kleinste, toewys dit aan jou waarde. 1317 00:55:02,510 --> 00:55:06,340 En jy sal baie gelukkiger wees wanneer ons gaan deur die kode. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 So ons gaan deur ons ruil dit, so dan ons kyk na hierdie ongesorteerde gedeelte. 1320 00:55:13,970 --> 00:55:15,810 So ons gaan drie uit te kies. 1321 00:55:15,810 --> 00:55:18,890 Ons gaan om dit te sit op ten die einde van ons gesorteerde gedeelte. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 En ons is net gaan om te hou doen dat dit te doen, en om dit te doen. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 So dit is ons soort van pseudokode hier. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Ons sal kodeer dit hier in 'n tweede. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Maar net om iets te loop deur op 'n hoë vlak. 1330 00:55:37,270 --> 00:55:40,275 Jy gaan om te gaan uit Ek is gelyk aan 0 tot N minus 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Dit is 'n ander optimalisering. 1333 00:55:43,530 --> 00:55:45,020 Moenie te veel bekommerd wees oor dit. 1334 00:55:45,020 --> 00:55:46,620 So as jy sê. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 As Jakob het gesê, hoe kan ons spoor van wat ons minimum is hou? 1337 00:55:54,406 --> 00:55:55,030 Hoe weet ons dit? 1338 00:55:55,030 --> 00:55:57,060 Ons het om te vergelyk alles in ons lys. 1339 00:55:57,060 --> 00:55:59,600 >> So minimum gelyk aan i. 1340 00:55:59,600 --> 00:56:03,870 Dit is net te sê in hierdie geval die indeks van ons minimum waarde. 1341 00:56:03,870 --> 00:56:07,660 So dan is dit gaan om Itereer deur en dit gaan van j gelyk i plus 1. 1342 00:56:07,660 --> 00:56:11,420 So het ons reeds weet dat dit is ons eerste element. 1343 00:56:11,420 --> 00:56:13,240 Ons moet nie huiwer om dit te vergelyk met self. 1344 00:56:13,240 --> 00:56:16,970 So het ons begin vergelyk dit na die volgende een wat is die rede waarom dit is i plus 1 tot N 1345 00:56:16,970 --> 00:56:20,110 minus 1, wat is die einde van die skikking is daar. 1346 00:56:20,110 --> 00:56:25,090 En ons het gesê dat indien die rigting van j is minder as skikking min, 1347 00:56:25,090 --> 00:56:29,200 dan toewys ons waar ons minimum indekse. 1348 00:56:29,200 --> 00:56:37,470 >> En as min is nie gelyk aan Ek, as in waar ons terug hier. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 So hou wanneer ons die eerste het hierdie een. 1351 00:56:41,790 --> 00:56:49,310 In hierdie geval, sou dit begin by nul, sou dit uiteindelik 'n twee. 1352 00:56:49,310 --> 00:56:53,010 So min wil nie gelyk i in die einde. 1353 00:56:53,010 --> 00:56:55,720 Dit laat ons weet wat ons nodig het om hulle te ruil. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Ek voel soos 'n konkrete voorbeeld sal help om veel meer as dit. 1356 00:57:00,470 --> 00:57:04,970 So ek sal hierdie kode met julle nou en ek dink dit sal beter wees. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Allerhande geneig dat die pad in die werk dit is dikwels beter om net om hulle te sien. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 So wat ons wil doen, is Ons wil eers die kleinste 1361 00:57:17,280 --> 00:57:19,890 element in sy posisie in die skikking. 1362 00:57:19,890 --> 00:57:21,280 Presies wat Jakob gesê het. 1363 00:57:21,280 --> 00:57:23,090 Jy moet dit een of ander manier te stoor. 1364 00:57:23,090 --> 00:57:25,900 So ons gaan hier begin iterating oor die skikking. 1365 00:57:25,900 --> 00:57:28,970 Ons gaan om te sê dit is ons eerste een net om te begin met. 1366 00:57:28,970 --> 00:57:38,308 So ons gaan int te hê kleinste is gelyk aan die rigting van i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> So een ding, elke op te let keer lus voer, 1369 00:57:45,050 --> 00:57:48,550 begin ons 'n stap verder. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Wanneer ons begin ons kyk na hierdie een. 1372 00:57:57,440 --> 00:58:00,840 Die volgende keer wat ons Itereer deur, ons begin by hierdie een 1373 00:58:00,840 --> 00:58:02,680 en die toeken dit ons kleinste waarde. 1374 00:58:02,680 --> 00:58:10,450 So dit is baie soortgelyk aan borrel soort waar ons weet dat daar na een pas, 1375 00:58:10,450 --> 00:58:11,700 hierdie laaste element is gesorteer. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Met seleksie soort, dit is net die teenoorgestelde. 1378 00:58:15,120 --> 00:58:18,950 >> By elke slaag, weet ons dat Die eerste een is gesorteer. 1379 00:58:18,950 --> 00:58:21,360 Na afloop van die tweede slaag, die tweede een sal gesorteer word. 1380 00:58:21,360 --> 00:58:26,470 En as jy sien met die skyfie voorbeelde, ons gesorteer gedeelte hou net groei. 1381 00:58:26,470 --> 00:58:34,020 So deur die instelling van ons kleinste een om skikkings i, al is dit doen 1382 00:58:34,020 --> 00:58:37,340 is versmoor wat Ons is op soek na so 1383 00:58:37,340 --> 00:58:40,164 om die getal te verminder vergelykings wat ons maak. 1384 00:58:40,164 --> 00:58:41,770 Maak dit sin maak vir almal? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Het jy my nodig het om te loop deur wat weer stadiger of in ander woorde? 1387 00:58:46,380 --> 00:58:47,180 Ek is bly om te. 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 >> So ons is die stoor van die waarde op hierdie punt, 1392 00:58:55,540 --> 00:58:57,840 maar ons wil ook die indeks te stoor. 1393 00:58:57,840 --> 00:59:01,010 So ons gaan die stoor posisie van die kleinste 1394 00:59:01,010 --> 00:59:02,770 een wat net gaan ek te wees. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 So nou Jacob tevrede is. 1397 00:59:05,440 --> 00:59:06,870 Ons het dinge gestoor. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 En nou het ons nodig het om te kyk deur die ongesorteerde deel van die skikking. 1400 00:59:11,870 --> 00:59:18,170 So in hierdie geval die sou wees om ons ongesorteerde. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Dit is Ek. 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 >> So wat ons gaan doen gaan wees vir 'n lus. 1406 00:59:30,040 --> 00:59:32,066 Wanneer jy nodig het om te Itereer deur 'n skikking, 1407 00:59:32,066 --> 00:59:33,440 jou gedagtes kan gaan vir 'n loop. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 So vir 'n paar int k equals-- wat dink ons 1410 00:59:38,090 --> 00:59:39,700 k gaan gelyk te begin met? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Dit is wat ons stel as ons kleinste waarde en ons wil om dit te vergelyk. 1413 00:59:44,766 --> 00:59:47,090 Wat wil ons dit te vergelyk met? 1414 00:59:47,090 --> 00:59:48,730 Dit gaan hierdie volgende een wees, reg? 1415 00:59:48,730 --> 00:59:53,200 So ons wil k geïnisialiseer word te i plus 1 te begin. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> En ons wil k in hierdie geval het ons reeds grootte opgegaar hier 1418 01:00:02,800 --> 01:00:03,930 sodat ons kan net gebruik grootte. 1419 01:00:03,930 --> 01:00:06,240 Grootte synde die grootte van die skikking. 1420 01:00:06,240 --> 01:00:09,620 En ons wil net werk k deur elke keer een. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Cool. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 So nou het ons nodig het om te vind die kleinste element hier. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 So as ons Itereer deur ons wil sê, as die rigting van k 1427 01:00:31,380 --> 01:00:37,080 minder is as ons kleinste value-- dit is waar ons is eintlik 1428 01:00:37,080 --> 01:00:42,950 dop van wat die kleinste here-- 1429 01:00:42,950 --> 01:00:47,740 dan wil ons toewys wat ons kleinste waarde is. 1430 01:00:47,740 --> 01:00:50,645 >> Dit beteken dat, o, ons iterating deur hier. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Wat ook al waarde is hier nie ons kleinste ding. 1433 01:00:53,740 --> 01:00:54,448 Ons wil dit nie. 1434 01:00:54,448 --> 01:00:56,100 Ons wil om dit te toewys. 1435 01:00:56,100 --> 01:01:02,050 So as ons gehou indiensneming nie, wat doen dink jy kan wees in hierdie kode hier? 1436 01:01:02,050 --> 01:01:04,160 Ons wil toewys kleinste en posisie. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 So, wat is die kleinste nou? 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 INSTRUCTOR: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 En wat is die posisie nou? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Wat is die indekse van ons kleinste waarde? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 Dit is net k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 So verskeidenheid k, k, pas hulle op. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Sodat ons wou dit toewys. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 En dan na ons gevind dat ons kleinste, So aan die einde van hierdie lus 1454 01:01:39,950 --> 01:01:45,100 Hier het ons het gevind wat ons kleinste waarde is, sodat ons net ruil nie. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 In hierdie geval, soos sê ons kleinste waarde is hier. 1457 01:01:50,816 --> 01:01:51,940 Dit is ons kleinste waarde. 1458 01:01:51,940 --> 01:01:57,690 >> Ons wil dit net hier te ruil, wat wat dit omruil funksie aan die onderkant 1459 01:01:57,690 --> 01:02:01,270 gedoen het, wat ons nou net geskryf het saam 'n paar minute gelede. 1460 01:02:01,270 --> 01:02:02,775 So dit moet lyk bekend. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 En dan sal dit net Itereer deur totdat dit al die pad bereik 1463 01:02:08,030 --> 01:02:13,100 tot aan die einde, wat beteken dat jy nul elemente wat ongesorteerde 1464 01:02:13,100 --> 01:02:14,800 en alles is gesorteer. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Sin maak? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 'N bietjie meer konkreet? 1469 01:02:19,280 --> 01:02:19,990 Die kode hulp? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> STUDENT: Vir 'n grote, jy nooit dit regtig definieer of verander dit, 1472 01:02:26,410 --> 01:02:27,340 hoe dit weet? 1473 01:02:27,340 --> 01:02:32,380 >> INSTRUCTOR: So een ding om te sien hier is int grootte. 1474 01:02:32,380 --> 01:02:35,680 So ons is in hierdie sort-- soort sê is 'n funksie in hierdie case-- dit 1475 01:02:35,680 --> 01:02:40,770 seleksie soort, is dit verby met die funksie. 1476 01:02:40,770 --> 01:02:43,460 So as dit was nie geslaag in, sal jy iets doen 1477 01:02:43,460 --> 01:02:47,840 soos met die lengte van die skikking of jy wil Itereer deur 1478 01:02:47,840 --> 01:02:49,390 die lengte te vind. 1479 01:02:49,390 --> 01:02:52,680 Maar, want dit is verby in, kan ons dit net gebruik. 1480 01:02:52,680 --> 01:02:55,720 Jy aanvaar net dat die gebruiker het jy 'n geldige grootte wat 1481 01:02:55,720 --> 01:02:57,698 eintlik verteenwoordig 'n grootte van jou skikking. 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 >> As julle enige probleme met hierdie of wil jy meer praktyk kodering vorme 1486 01:03:05,870 --> 01:03:08,050 op jou eie, moet jy gaan na study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Dit is 'n instrument. 1489 01:03:12,670 --> 01:03:15,040 Hulle het 'n checker wat jy eintlik kan skryf. 1490 01:03:15,040 --> 01:03:16,180 Hulle doen pseudokode. 1491 01:03:16,180 --> 01:03:19,310 Hulle het meer video's en skyfies insluitend die wat ek hier gebruik. 1492 01:03:19,310 --> 01:03:23,150 So as jy nog steeds voel 'n bietjie fuzzy, probeer om uit te. 1493 01:03:23,150 --> 01:03:25,670 Soos altyd, kom praat met my ook. 1494 01:03:25,670 --> 01:03:26,320 Vraag? 1495 01:03:26,320 --> 01:03:28,611 >> STUDENT: Is jy sê die grootte voorheen gedefinieer? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 INSTRUCTOR: Ja. 1498 01:03:29,900 --> 01:03:35,570 Grootte voorheen gedefinieer up hier in die funksie verklaring. 1499 01:03:35,570 --> 01:03:39,060 So jy aanneem dat dit in is verby deur die gebruiker, en ter wille van eenvoud, 1500 01:03:39,060 --> 01:03:41,896 ons gaan om te aanvaar dat die gebruiker het ons die regte grootte. 1501 01:03:41,896 --> 01:03:43,240 Cool. 1502 01:03:43,240 --> 01:03:44,390 So dit is seleksie soort. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Ouens, ek weet ons leer baie vandag. 1505 01:03:47,640 --> 01:03:49,710 Dit is 'n digte data vir artikel. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 So met dit, gaan ons om te gaan na voeg soort. 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 So voor dat ons te doen het ons runtime analise hier. 1511 01:04:06,100 --> 01:04:10,190 So in die beste geval, toegestaan, want ek het julle 1512 01:04:10,190 --> 01:04:11,960 die tafel ek reeds soort het dit weg. 1513 01:04:11,960 --> 01:04:15,430 Maar die beste geval runtime, wat dink ons ​​doen? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Alles gesorteer. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N vierkant. 1518 01:04:22,070 --> 01:04:24,780 Enigiemand het 'n verduideliking waarom jy dink? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> STUDENT: Jy vergelyk through-- 1521 01:04:30,519 --> 01:04:31,268 INSTRUCTOR: Right. 1522 01:04:31,268 --> 01:04:32,540 Jy vergelyk deur. 1523 01:04:32,540 --> 01:04:35,630 By elke iterasie, selfs al ons decrementing hierdie een, 1524 01:04:35,630 --> 01:04:38,950 jy nog soek deur alles wat die kleinste een te vind. 1525 01:04:38,950 --> 01:04:42,390 So selfs as jou kleinste waarde is hier aan die begin, 1526 01:04:42,390 --> 01:04:44,710 jy nog steeds dit te vergelyk teen alles 1527 01:04:44,710 --> 01:04:46,550 om seker te maak dit is die kleinste ding maak. 1528 01:04:46,550 --> 01:04:49,820 So sal jy eindig loop deur ongeveer N vierkantig tye. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Alle regte. 1531 01:04:51,590 --> 01:04:52,785 En wat is die ergste geval? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Ook N vierkantig want jy gaan om te doen wat dieselfde prosedure. 1534 01:04:57,980 --> 01:05:01,670 So in hierdie geval, keuring soort iets 1535 01:05:01,670 --> 01:05:04,010 dat ons ook 'n beroep verwagte looptyd. 1536 01:05:04,010 --> 01:05:07,400 So in die ander, het ons net weet die boonste en onderste grense. 1537 01:05:07,400 --> 01:05:11,180 Afhangende van hoe mal ons lys is of hoe ongesorteerde dit is, 1538 01:05:11,180 --> 01:05:15,350 hulle wissel tussen N of n vierkant. 1539 01:05:15,350 --> 01:05:16,550 Ons weet nie. 1540 01:05:16,550 --> 01:05:22,820 >> Maar omdat seleksie soort het dieselfde ergste en die beste geval, wat ons vertel dat 1541 01:05:22,820 --> 01:05:25,880 maak nie saak watter tipe van insette wat ons het, of dit nou heeltemal 1542 01:05:25,880 --> 01:05:29,130 gesorteer of heeltemal reverse gesorteer, dit is 1543 01:05:29,130 --> 01:05:30,740 gaan dieselfde hoeveelheid tyd te neem. 1544 01:05:30,740 --> 01:05:33,760 So in daardie geval, as jy Onthou van ons tafel, 1545 01:05:33,760 --> 01:05:38,610 dit het eintlik 'n waarde wat hierdie twee vorme het nie, 1546 01:05:38,610 --> 01:05:40,390 wat verwag runtime. 1547 01:05:40,390 --> 01:05:43,350 So ons weet dat wanneer loop ons seleksie soort, 1548 01:05:43,350 --> 01:05:45,380 dit is gewaarborg om hardloop 'n n vierkant tyd. 1549 01:05:45,380 --> 01:05:46,630 Daar is geen variasie daar. 1550 01:05:46,630 --> 01:05:47,630 Dit is net wat verwag is. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 En weer, as jy wil leer meer, neem CS 124 in die lente. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Alle regte. 1555 01:05:56,712 --> 01:05:57,545 Ons het gesien dat hierdie een. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Cool. 1558 01:05:59,030 --> 01:06:00,930 So voeg soort. 1559 01:06:00,930 --> 01:06:03,330 En ek is waarskynlik gaan te brand deur middel van hierdie. 1560 01:06:03,330 --> 01:06:05,440 Ek wil nie hê dat julle ouens die kode nie. 1561 01:06:05,440 --> 01:06:06,580 Ons sal net loop deur dit. 1562 01:06:06,580 --> 01:06:10,500 So voeg soort is 'n soort van soortgelyke seleksie soort 1563 01:06:10,500 --> 01:06:14,460 in wat ons het beide 'n ongesorteerde en gesorteer deel van die skikking. 1564 01:06:14,460 --> 01:06:20,260 >> Maar wat anders is, is dat as ons gaan deur een vir een, 1565 01:06:20,260 --> 01:06:24,210 Ons het net neem wat die getal langs in ons ongesorteerde, 1566 01:06:24,210 --> 01:06:28,507 en korrek sorteer dit in ons gesorteerde skikking. 1567 01:06:28,507 --> 01:06:30,090 Dit sal meer sin maak met 'n voorbeeld. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 So alles begin as ongesorteerde, Net soos 'n seleksie soort. 1570 01:06:35,430 --> 01:06:38,740 En ons gaan dit in te sorteer stygende volgorde soos ons gewees het. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 So op ons eerste pas neem ons die eerste waarde 1573 01:06:43,340 --> 01:06:46,700 en ons sê, OK, jy is nou in 'n lys wat deur jouself. 1574 01:06:46,700 --> 01:06:49,150 >> Omdat jy in 'n lys deur jouself, is jy gesorteer. 1575 01:06:49,150 --> 01:06:52,460 Baie geluk vir die feit dat die eerste element in hierdie reeks. 1576 01:06:52,460 --> 01:06:54,800 Jy is reeds gesorteer al op jou eie. 1577 01:06:54,800 --> 01:06:58,900 So nou het ons 'n gesorteer en 'n ongesorteerde skikking. 1578 01:06:58,900 --> 01:07:01,760 So nou het ons neem die eerste. 1579 01:07:01,760 --> 01:07:05,600 Wat gebeur tussen hier en hier is dat ons sê: 1580 01:07:05,600 --> 01:07:08,890 OK, ons gaan om te kyk na die eerste waarde van ons ongesorteerde skikking 1581 01:07:08,890 --> 01:07:13,270 en ons gaan om insette dit in sy regte plek in die gesorteerde skikking. 1582 01:07:13,270 --> 01:07:21,460 >> So, wat ons doen, is ons 5 en ons sê, OK, 5 is groter as 3, 1583 01:07:21,460 --> 01:07:24,630 sodat ons net plaas dit reg aan die regterkant van die. 1584 01:07:24,630 --> 01:07:25,130 Ons is goed. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 So dan gaan ons na ons volgende een. 1587 01:07:28,420 --> 01:07:29,720 En ons neem 2. 1588 01:07:29,720 --> 01:07:34,330 Ons sê, OK, 2 minder as 3, so ons weet dat dit 1589 01:07:34,330 --> 01:07:36,220 moet wees by die voor ons lys nou. 1590 01:07:36,220 --> 01:07:41,800 So wat ons doen is ons druk 3 en 5 af en ons beweeg 2 in die eerste slot. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 So ons is net te voeg dit in die regte plek dit behoort te wees. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Dan kyk ons ​​na ons volgende een, en ons sê 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 is groter as alles in ons gesorteerde skikking, 1596 01:07:53,620 --> 01:07:56,000 sodat ons net merk dit aan die einde. 1597 01:07:56,000 --> 01:07:56,960 En dan moet ons kyk na 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 is minder as 6, is dit minder as 5 maar dit is groter as 3. 1600 01:08:03,020 --> 01:08:06,270 Sodat ons net plaas dit regs in die middel tussen 3 en 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 So maak dat 'n bietjie bietjie meer konkrete, 1603 01:08:10,530 --> 01:08:12,280 hier is 'n soort van die idee van wat gebeur het. 1604 01:08:12,280 --> 01:08:16,430 So vir elke ongesorteerde element, ons bepaal waar in die gesorteerde gedeelte 1605 01:08:16,430 --> 01:08:17,090 dit is. 1606 01:08:17,090 --> 01:08:20,680 >> So in gedagte hou die gesorteer en ongesorteerde, 1607 01:08:20,680 --> 01:08:26,080 Ons het om oor te steek deur en figuur uit waar dit inpas in die gesorteerde skikking. 1608 01:08:26,080 --> 01:08:31,460 En ons plaas dit deur die verskuiwing van die elemente aan die regterkant van dit af. 1609 01:08:31,460 --> 01:08:34,910 En dan moet ons net aanhou iterating deur totdat ons 1610 01:08:34,910 --> 01:08:39,270 het 'n heeltemal gesorteer lys waar ongesorteerde is nou nul 1611 01:08:39,270 --> 01:08:41,720 en gesorteer neem die geheel van ons lys. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 So, weer, om dinge selfs meer konkrete, ons het pseudokode. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> So basies, want ek is gelyk aan 0 tot N minus 1, 1616 01:08:52,410 --> 01:08:54,790 dit is net die lengte van ons verskeidenheid. 1617 01:08:54,790 --> 01:09:00,979 Ons het 'n element wat gelyk is aan die eerste skikking of die eerste indekse. 1618 01:09:00,979 --> 01:09:03,200 Ons stel j gelyk aan dit. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Dus, terwyl j is groter as nul en die skikking, j minus 1 1621 01:09:09,210 --> 01:09:11,660 groter is as die element, so al wat doen 1622 01:09:11,660 --> 01:09:17,479 is om seker te maak dat jou j regtig verteenwoordig 1623 01:09:17,479 --> 01:09:20,010 die ongesorteerde gedeelte van die skikking. 1624 01:09:20,010 --> 01:09:30,745 >> Dus, terwyl daar is nog dinge te sorteer en j minus een is-- wat 1625 01:09:30,745 --> 01:09:31,840 is die element haar? 1626 01:09:31,840 --> 01:09:34,760 J was nog nooit hier gedefinieer. 1627 01:09:34,760 --> 01:09:35,677 Dit is soort van irriterende. 1628 01:09:35,677 --> 01:09:36,176 OK. 1629 01:09:36,176 --> 01:09:36,689 In elk geval. 1630 01:09:36,689 --> 01:09:39,899 So j minus 1, jy kontrolering die element voor dit. 1631 01:09:39,899 --> 01:09:46,460 Jy sê, OK, is die element voor waar ek am-- laat 1632 01:09:46,460 --> 01:09:47,540 eintlik trek dit uit. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 So kom ons sê dit is soos op ons tweede slaag. 1635 01:09:56,830 --> 01:09:59,525 So ek gaan om gelyk te wees 1, wat is hier. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> So ek gaan gelyk aan 1 te wees. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Dit sou wees 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Alle regte. 1642 01:10:16,750 --> 01:10:20,945 So ons element in hierdie geval gaan gelyk aan 4 nie. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 En ons het 'n paar j dis gaan gelyk aan 1 te wees. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 O, is j decrementing. 1647 01:10:30,971 --> 01:10:31,720 Dit is wat dit is. 1648 01:10:31,720 --> 01:10:35,680 So j is gelyk aan i, so wat dit is sê, is dat as ons vorentoe beweeg, 1649 01:10:35,680 --> 01:10:37,530 ons is net om seker te maak dat ons oor is nie 1650 01:10:37,530 --> 01:10:43,520 kruip op hierdie manier wanneer ons probeer dinge te voeg in ons gesorteer lys. 1651 01:10:43,520 --> 01:10:49,850 >> So wanneer j is gelyk aan 1 in hierdie geval en verskeidenheid j minus one-- so skikking j minus 1 1652 01:10:49,850 --> 01:10:54,610 2 in hierdie case-- as dit is groter is as die element, 1653 01:10:54,610 --> 01:10:57,700 dan sal al hierdie doen verskuif dinge af. 1654 01:10:57,700 --> 01:11:04,790 So in hierdie geval, verskeidenheid j minus een sou skikking nul, wat 2 wees. 1655 01:11:04,790 --> 01:11:08,430 2 is nie groter as 4, sodat dit nie uit te voer. 1656 01:11:08,430 --> 01:11:11,460 So het die skof nie af beweeg. 1657 01:11:11,460 --> 01:11:18,790 Wat dit beteken hier is net beweeg jou gesorteerde skikking af. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 In hierdie geval, eintlik, ons kon do-- laat ons hierdie 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 So as ons te loop deur met hierdie voorbeeld, het ons nou hier is. 1662 01:11:31,970 --> 01:11:32,740 Dit word gesorteer. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Dit is ongesorteerde. 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 So ek is gelyk aan 2, so ons element is gelykstaande aan 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 En ons j is gelyk aan 2. 1670 01:11:52,270 --> 01:12:00,620 So ons kyk deur en ons sê, OK, is verskeidenheid j minus een 1671 01:12:00,620 --> 01:12:03,470 groter is as die element dat ons is op soek na? 1672 01:12:03,470 --> 01:12:05,540 En die antwoord is ja, reg? 1673 01:12:05,540 --> 01:12:11,275 4 is groter as 3 en j is 2, dus is hierdie kode voer. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> So nou wat ons doen 'n skikking te 2, so reg hier, ons ruil hulle. 1676 01:12:18,550 --> 01:12:25,620 Sodat ons net sê, OK, skikking op 2 nou gaan wees 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 En j gaan gelyk j minus 1, wat is 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Dit is verskriklik, maar julle kry die idee. 1681 01:12:37,200 --> 01:12:38,360 J is nou gelyk aan 1. 1682 01:12:38,360 --> 01:12:44,360 Skikking j is net gaan om te wees gelyk aan ons element, wat 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Ek iets uitgewis ek moet nie het of miswrote iets, 1685 01:12:48,570 --> 01:12:49,910 maar julle ouens kry die idee. 1686 01:12:49,910 --> 01:12:50,640 >> Dit beweeg teen n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 En dan as dit was, sou dit lus weer en dit sou sê, OK, j is 1 nou. 1689 01:12:57,960 --> 01:13:00,665 Skikking j minus 1 is nou 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 2 minder as die element? 1692 01:13:03,760 --> 01:13:04,540 Geen? 1693 01:13:04,540 --> 01:13:07,970 Dit beteken dat ons plaas hierdie element 1694 01:13:07,970 --> 01:13:10,110 in die regte plek in ons gesorteerde skikking. 1695 01:13:10,110 --> 01:13:14,400 Dan kan ons hierdie en ons sê, OK, ons gesorteerde skikking is hier. 1696 01:13:14,400 --> 01:13:19,940 En dit sal die nommer 6 neem en soos, OK, 6 minder as die getal? 1697 01:13:19,940 --> 01:13:20,480 Geen? 1698 01:13:20,480 --> 01:13:21,080 Cool. 1699 01:13:21,080 --> 01:13:22,680 Ons is goed. 1700 01:13:22,680 --> 01:13:23,530 >> Doen dit weer. 1701 01:13:23,530 --> 01:13:24,740 Ons sê 7. 1702 01:13:24,740 --> 01:13:29,010 7 minder as die einde van ons gesorteerde skikking? 1703 01:13:29,010 --> 01:13:29,520 No. 1704 01:13:29,520 --> 01:13:30,430 So ons is fine. 1705 01:13:30,430 --> 01:13:32,760 So dit sal uitgesorteer word. 1706 01:13:32,760 --> 01:13:38,610 Basies alles doen is dit gesê neem 1707 01:13:38,610 --> 01:13:42,060 die eerste element van jou ongesorteerde skikking, 1708 01:13:42,060 --> 01:13:46,010 uit te vind waar dit gaan in jou gesorteerde skikking. 1709 01:13:46,010 --> 01:13:48,780 En dit neem net sorg van swaps om dit te doen. 1710 01:13:48,780 --> 01:13:51,300 Jy is basies net uitruiling totdat dit in die regte plek. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 Die visuele beeld is dat jy beweeg om alles af deur dit te doen. 1713 01:13:56,990 --> 01:13:59,420 >> So dit is soos half borrel soort-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Check studie 50. 1716 01:14:03,420 --> 01:14:06,000 Ek raai probeer hierdie kode op jou eie. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Indien u enige kwessies of jy wil sien voorbeeld kode vir 'n inplanting soort, 1719 01:14:12,450 --> 01:14:13,750 laat weet my asseblief. 1720 01:14:13,750 --> 01:14:14,500 Ek is altyd rond. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 So ergste geval runtime en die beste geval runtime. 1723 01:14:20,200 --> 01:14:30,700 As jy man gesien het van die tafel ek reeds het julle dit beide n vierkant en n. 1724 01:14:30,700 --> 01:14:35,590 >> So soort gaan af van wat ons gepraat oor ons vorige vorme, ergste 1725 01:14:35,590 --> 01:14:38,760 geval runtime is dat indien Dit is heeltemal ongesorteerde, 1726 01:14:38,760 --> 01:14:42,530 ons het al hierdie n keer te vergelyk. 1727 01:14:42,530 --> 01:14:47,020 Ons doen 'n hele klomp van vergelykings want as dit is in omgekeerde volgorde, 1728 01:14:47,020 --> 01:14:50,360 ons gaan om te sê, OK, dit is dieselfde, dit is goed, 1729 01:14:50,360 --> 01:14:54,650 en hierdie een sal hê om te vergelyk teen die eerste een te wees verhuis terug. 1730 01:14:54,650 --> 01:14:56,710 En as ons in die rigting van die stertkant, ons het 1731 01:14:56,710 --> 01:14:59,440 te vergelyk, te vergelyk, en vergelyk teen alles. 1732 01:14:59,440 --> 01:15:03,030 >> So is dit eindig word ongeveer N vierkant. 1733 01:15:03,030 --> 01:15:09,510 As dit korrek is dan is jy sê, OK, 2, jy is goed. 1734 01:15:09,510 --> 01:15:11,330 3, is jy in vergelyking met 2. 1735 01:15:11,330 --> 01:15:12,310 Jy is goed. 1736 01:15:12,310 --> 01:15:14,150 4, jy vergelyk net die stert. 1737 01:15:14,150 --> 01:15:14,990 Jy is goed. 1738 01:15:14,990 --> 01:15:17,140 6, vergelyk met die stert, jy is fine. 1739 01:15:17,140 --> 01:15:20,870 So vir elke plek as dit reeds gesorteer, jy maak 'n vergelyking. 1740 01:15:20,870 --> 01:15:22,320 So dit is net n. 1741 01:15:22,320 --> 01:15:26,840 En omdat ons 'n beste geval runtime van N en 'n ergste geval runtime van N 1742 01:15:26,840 --> 01:15:28,680 vierkantig, ons het nie verwag runtime. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Dit hang net op die chaos van ons lys is daar. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 En weer 'n ander grafiek en 'n ander tafel. 1747 01:15:39,530 --> 01:15:41,170 So verskille tussen spesies. 1748 01:15:41,170 --> 01:15:44,180 Ek is net gaan om te briesie deur, het ek voel soos ons het breedvoerig gepraat 1749 01:15:44,180 --> 01:15:46,570 oor hoe hulle al die soort van verskil en met mekaar skakel. 1750 01:15:46,570 --> 01:15:50,564 Sodat fuseren soort is die laaste een Ek sal julle gebaar ouens met. 1751 01:15:50,564 --> 01:15:52,105 Ons het 'n mooi kleurvolle prentjie. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 So saamsmelt soort is 'n rekursiewe algoritme. 1754 01:15:56,040 --> 01:15:59,910 So weet julle nie wat 'n rekursiewe funksie is? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Iemand wil hê om te sê? 1757 01:16:03,320 --> 01:16:04,739 Jy wil om te probeer? 1758 01:16:04,739 --> 01:16:07,280 So 'n rekursiewe funksie is net 'n funksie wat homself. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 So as julle vertroud is met die Fibonacci-ry, 1761 01:16:11,590 --> 01:16:15,670 dit is geag rekursiewe omdat neem jy die vorige twee 1762 01:16:15,670 --> 01:16:17,530 en voeg hulle saam jou volgende een te kry. 1763 01:16:17,530 --> 01:16:21,440 So rekursiewe, dink ek altyd van rekursie as soos 'n spiraal 1764 01:16:21,440 --> 01:16:24,430 sodat jy soos stygende af in dit. 1765 01:16:24,430 --> 01:16:27,150 Maar dit is net 'n funksie wat roep self. 1766 01:16:27,150 --> 01:16:32,660 >> En eintlik, regtig vinnig I kan jy wys wat dit lyk. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 So rekursiewe hier, as ons kyk, is dit die rekursiewe manier op te som oor 'n skikking. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 So al wat ons doen is ons het som funksie 1771 01:16:47,880 --> 01:16:52,210 som wat nie 'n grote en 'n skikking. 1772 01:16:52,210 --> 01:16:55,210 En as jy sien, grootte decrements deur een elke keer. 1773 01:16:55,210 --> 01:17:00,365 En al wat dit doen is as x is gelyk aan zero-- so as die grootte van die skikking 1774 01:17:00,365 --> 01:17:02,710 is gelyk aan zero-- dit gee nul. 1775 01:17:02,710 --> 01:17:10,440 >> Anders is dit vat hierdie laaste element van die skikking, 1776 01:17:10,440 --> 01:17:14,790 en neem dan 'n bedrag van die res van die reeks. 1777 01:17:14,790 --> 01:17:17,555 So dit is net dit af te breek in kleiner en kleiner probleme. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Lang storie kort, rekursie, funksie wat homself. 1780 01:17:21,890 --> 01:17:25,740 As dit is al wat jy het om uit hierdie, dit is wat 'n rekursiewe funksie is. 1781 01:17:25,740 --> 01:17:29,870 As jy 51 is, sal jy baie kry, baie gemaklik met rekursie. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 Dit is regtig cool. 1784 01:17:32,370 --> 01:17:34,660 Dit het sin soos 03:00 een aand uit. 1785 01:17:34,660 --> 01:17:37,900 En ek was soos, hoekom Ek gebruik dit nooit? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> So vir merge soort, basies wat dit gaan doen, is dit 1788 01:17:42,430 --> 01:17:45,620 gaan dit af te breek en breek dit totdat dit is net enkele elemente. 1789 01:17:45,620 --> 01:17:47,570 Die enkele elemente is maklik om te sorteer. 1790 01:17:47,570 --> 01:17:48,070 Ons sien dat. 1791 01:17:48,070 --> 01:17:50,760 As jy een element, is dit reeds beskou gesorteer. 1792 01:17:50,760 --> 01:17:53,800 So op 'n bydrae van N elemente, As n is minder as 2, 1793 01:17:53,800 --> 01:17:58,120 net terugkeer, want dit beteken dit is óf 0 of 1 soos ons gesien het. 1794 01:17:58,120 --> 01:18:00,050 Diegene oorweeg gesorteer elemente. 1795 01:18:00,050 --> 01:18:02,170 >> Anders breek dit in die helfte. 1796 01:18:02,170 --> 01:18:06,336 Sorteer die eerste helfte, sorteer die tweede helfte, en dan saam te smelt hulle saam. 1797 01:18:06,336 --> 01:18:07,460 Hoekom is dit genoem merge soort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 So het ons hier ons sal sorteer. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 So hou ons met hulle totdat die skikking grootte is 1. 1802 01:18:17,210 --> 01:18:20,790 So wanneer dit 1, het ons net terug want dit is 'n gesorteerde skikking, 1803 01:18:20,790 --> 01:18:23,940 en dit is 'n gesorteerde skikking, en dit is 'n gesorteerde skikking, ons is almal gesorteer. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 So dan wat ons doen, is ons begin samesmelting hulle saam. 1806 01:18:29,420 --> 01:18:31,820 >> So die manier wat jy kan dink oor samesmelting is 1807 01:18:31,820 --> 01:18:36,240 jy net verwyder die kleiner getal van elk van die sub skikkings 1808 01:18:36,240 --> 01:18:38,330 en net voeg dit aan die lig gekom skikking. 1809 01:18:38,330 --> 01:18:44,290 So as jy kyk hier, wanneer ons hierdie stelle ons het 4, 6, en 1. 1810 01:18:44,290 --> 01:18:47,280 Wanneer ons wil om dit te smelt, ons kyk na die eerste twee 1811 01:18:47,280 --> 01:18:50,730 en ons sê, OK, 1 is kleiner, dit gaan na die front. 1812 01:18:50,730 --> 01:18:54,330 4 en 6, daar is niks om te vergelyk dit net merk dit aan die einde. 1813 01:18:54,330 --> 01:18:58,020 >> Wanneer ons kombineer hierdie twee, het ons net neem die kleiner een van die twee, 1814 01:18:58,020 --> 01:18:59,310 so dit is 1. 1815 01:18:59,310 --> 01:19:01,690 En nou het ons neem die kleiner van die twee, so 2. 1816 01:19:01,690 --> 01:19:03,330 Kleiner van die twee, 3. 1817 01:19:03,330 --> 01:19:06,260 Kleiner van die twee, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 So jy net trek uit hierdie. 1819 01:19:08,630 --> 01:19:11,210 En omdat hulle voorheen gesorteer, 1820 01:19:11,210 --> 01:19:14,300 jy moet net een vergelyking elke keer daar. 1821 01:19:14,300 --> 01:19:19,610 Sodat meer kode hier, net verteenwoordiging. 1822 01:19:19,610 --> 01:19:24,410 So jy begin by die middel en jy soort links en regs 1823 01:19:24,410 --> 01:19:26,180 en dan kan jy net saam te smelt hulle. 1824 01:19:26,180 --> 01:19:30,080 >> En ons het nie 'kode vir saamsmelt hier. 1825 01:19:30,080 --> 01:19:34,110 Maar, weer, as jy gaan op studeer 50, sal dit daar wees. 1826 01:19:34,110 --> 01:19:36,860 Anders kom praat met my As jy nog steeds verward. 1827 01:19:36,860 --> 01:19:42,340 So cool ding hier is dat die beste geval, ergste geval, en verwag runtime 1828 01:19:42,340 --> 01:19:46,250 is almal in log N, wat is baie beter as wat ons het 1829 01:19:46,250 --> 01:19:48,000 gesien vir die res van ons spesies. 1830 01:19:48,000 --> 01:19:51,840 Ons het gesien hoe n vierkant en wat ons eintlik 1831 01:19:51,840 --> 01:19:54,380 kry hier is n teken n, wat is groot. 1832 01:19:54,380 --> 01:19:55,830 >> Kyk hoe baie beter wat. 1833 01:19:55,830 --> 01:19:56,780 So 'n mooi kurwe. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Soveel meer doeltreffend te maak. 1836 01:20:00,120 --> 01:20:03,510 As jy ooit kan, gebruik saamsmelt soort. 1837 01:20:03,510 --> 01:20:04,810 Dit sal jou tyd bespaar. 1838 01:20:04,810 --> 01:20:07,670 Dan weer, soos ons gesê het, as jy in hierdie laer streek, 1839 01:20:07,670 --> 01:20:09,480 dit maak nie dat veel van 'n verskil maak. 1840 01:20:09,480 --> 01:20:11,360 Jy kry tot duisende en duisende van insette, 1841 01:20:11,360 --> 01:20:13,318 jy beslis wil 'n meer doeltreffende algoritme. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 En weer, ons pragtige tafel van alle spesies wat julle vandag geleer het. 1844 01:20:19,400 --> 01:20:21,157 >> So ek weet dit is 'n digte dag. 1845 01:20:21,157 --> 01:20:23,490 Dit is nie noodwendig gaan om jou te help met jou pset. 1846 01:20:23,490 --> 01:20:28,250 Maar ek wil net 'n disclaimer te maak daardie artikel is nie net oor psets. 1847 01:20:28,250 --> 01:20:31,240 Al hierdie materiaal is regverdig spel vir jou midterms. 1848 01:20:31,240 --> 01:20:35,430 En ook as jy voortgaan met CS, Dit is baie belangrik grondbeginsels 1849 01:20:35,430 --> 01:20:37,870 wat jy nodig sou wees om te weet. 1850 01:20:37,870 --> 01:20:41,700 So 'n paar dae sal wees om 'n bietjie meer pset hulp 1851 01:20:41,700 --> 01:20:44,600 maar sommige weke sal wees veel meer werklike inhoud 1852 01:20:44,600 --> 01:20:46,600 wat mag lyk nie super nuttig vir jou nou, 1853 01:20:46,600 --> 01:20:51,215 maar ek belowe as jy aanhou op sal baie, baie nuttig. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> So dit is dit vir artikel. 1856 01:20:54,250 --> 01:20:55,250 Af na die draad. 1857 01:20:55,250 --> 01:20:56,570 Ek het dit in 'n minuut. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Maar daar gaan jy. 1860 01:20:58,970 --> 01:21:01,240 En Ek sal donuts of lekkergoed. 1861 01:21:01,240 --> 01:21:03,464 Is daar iemand allergies vir enigiets op die pad? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Eiers en melk. 1864 01:21:05,890 --> 01:21:08,120 So donuts is 'n nie? 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 Alle regte. 1868 01:21:10,770 --> 01:21:12,120 Sjokolade geen? 1869 01:21:12,120 --> 01:21:12,620 Burst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts is goed. 1872 01:21:14,670 --> 01:21:15,170 OK. 1873 01:21:15,170 --> 01:21:17,045 Ons gaan hê Burst volgende week dan. 1874 01:21:17,045 --> 01:21:18,240 Dit is wat ek kry. 1875 01:21:18,240 --> 01:21:19,690 Julle het 'n groot week. 1876 01:21:19,690 --> 01:21:20,460 Lees jou spec. 1877 01:21:20,460 --> 01:21:22,130 >> Laat my weet as jy enige vrae het. 1878 01:21:22,130 --> 01:21:25,300 Pset twee grade moet wees uit na jou teen Donderdag. 1879 01:21:25,300 --> 01:21:28,320 As jy enige vrae het oor hoe ek iets gegradeer 1880 01:21:28,320 --> 01:21:32,250 of waarom ek gegradeer iets wat die manier waarop ek het nie, kan u my e-pos, kom praat met my. 1881 01:21:32,250 --> 01:21:34,210 Ek is 'n bietjie mal hierdie week, maar ek belowe 1882 01:21:34,210 --> 01:21:36,340 Ek sal nog steeds 'n antwoord binne 24 uur. 1883 01:21:36,340 --> 01:21:38,240 So het 'n groot week, almal. 1884 01:21:38,240 --> 01:21:40,090 Sterkte op jou pset. 1885 01:21:40,090 --> 01:21:41,248