1 00:00:00,000 --> 00:00:11,904 >> [MUSIC SPILLE] 2 00:00:11,904 --> 00:00:12,910 >> PROFESSOR: All right. 3 00:00:12,910 --> 00:00:16,730 Dette er CS50, og dette er slutten av uke tre. 4 00:00:16,730 --> 00:00:20,230 Så vi er her i dag, ikke i Sanders Teater, i stedet i Weidner Library. 5 00:00:20,230 --> 00:00:23,170 Innsiden av som er et studio kjent som Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 eller skal vi si Studio H, eller skal vi say-- hvis du likte den vitsen, 7 00:00:28,310 --> 00:00:30,540 det er faktisk fra klassekamerat, Mark, online, 8 00:00:30,540 --> 00:00:32,420 som foreslo så mye via Twitter. 9 00:00:32,420 --> 00:00:34,270 Nå hva er kult om å være her i et studio 10 00:00:34,270 --> 00:00:38,410 er at jeg er omgitt av disse grønne vegger, en grønn skjerm eller chromakey, 11 00:00:38,410 --> 00:00:43,290 så å si, noe som betyr at CS50 s produksjon team, ukjent for meg 12 00:00:43,290 --> 00:00:47,380 akkurat nå, kunne være å sette meg mest hvor som helst i verden, 13 00:00:47,380 --> 00:00:48,660 for bedre eller verre. 14 00:00:48,660 --> 00:00:51,800 >> Nå hva som ligger foran oss, oppgavesettet to er i dine hender for denne uken, 15 00:00:51,800 --> 00:00:53,830 men med oppgavesettet tre denne kommende uken, 16 00:00:53,830 --> 00:00:56,600 du vil bli utfordret med den såkalte game of 15, 17 00:00:56,600 --> 00:00:58,960 et gammelt parti favør at du kanskje husker mottak 18 00:00:58,960 --> 00:01:02,030 som et barn som har en hel haug av tall som kan skyve opp, ned, 19 00:01:02,030 --> 00:01:05,790 venstre og høyre, og det er ett gap innen puslespillet, der du 20 00:01:05,790 --> 00:01:07,840 faktisk kan skyve disse brikkene. 21 00:01:07,840 --> 00:01:11,150 Til syvende og sist du får denne puslespillet i noen semi tilfeldig rekkefølge, 22 00:01:11,150 --> 00:01:12,940 og målet er å sortere det, topp til bunn, 23 00:01:12,940 --> 00:01:16,310 venstre til høyre, fra ett hele veien opp til og med 15. 24 00:01:16,310 --> 00:01:19,360 >> Dessverre, gjennomføring du har for hånden 25 00:01:19,360 --> 00:01:21,590 kommer til å være programvare basert, ikke fysisk. 26 00:01:21,590 --> 00:01:25,280 Du er faktisk nødt til å skrive kode med som en student eller bruker kan 27 00:01:25,280 --> 00:01:26,760 spille spillet på 15. 28 00:01:26,760 --> 00:01:29,030 Og faktisk, i hacker utgaven av spillet på 15, 29 00:01:29,030 --> 00:01:32,155 du vil bli en utfordring å implementere, ikke bare å spille av denne gamle skolen 30 00:01:32,155 --> 00:01:35,010 spillet, men heller løse av det, implementere gud modus, 31 00:01:35,010 --> 00:01:38,280 så å si, som faktisk løser gåten for det menneskelige, 32 00:01:38,280 --> 00:01:41,080 ved å gi dem hint, etter hint etter hint. 33 00:01:41,080 --> 00:01:42,280 Så mer om det i neste uke. 34 00:01:42,280 --> 00:01:43,720 Men det er det som ligger foran oss. 35 00:01:43,720 --> 00:01:47,610 >> For nå husker at tidligere denne uken vi hadde denne cliffhanger, om du vil, 36 00:01:47,610 --> 00:01:52,560 hvorved det beste vi gjorde sortering klok var en øvre grense for store o n 37 00:01:52,560 --> 00:01:53,210 squared. 38 00:01:53,210 --> 00:01:56,520 Med andre ord, boble sortere, utvalg sortere, innsetting sortere, 39 00:01:56,520 --> 00:01:59,120 alle av dem, mens forskjellige i gjennomføringen, 40 00:01:59,120 --> 00:02:03,480 delegert til en n squared kjører tid i det aller verste tilfelle. 41 00:02:03,480 --> 00:02:06,010 Og vi generelt anta at det aller verste fall for sortering 42 00:02:06,010 --> 00:02:08,814 er en som dataen er helt bakover. 43 00:02:08,814 --> 00:02:11,980 Og ja, det tok ganske få skritt for å gjennomføre hver av disse algoritmer. 44 00:02:11,980 --> 00:02:15,110 >> Nå helt på slutten av klassen tilbakekallingen, sammenlignet vi boble liksom 45 00:02:15,110 --> 00:02:19,390 mot valget sort mot en annen som vi kalte merge sort på den tiden, 46 00:02:19,390 --> 00:02:22,120 og jeg foreslår at det tar Fordelen med en leksjon fra uke 47 00:02:22,120 --> 00:02:24,060 null, Splitt og hersk. 48 00:02:24,060 --> 00:02:28,810 Og en eller annen måte å oppnå en slags logaritmisk kjøretid til slutt, 49 00:02:28,810 --> 00:02:31,024 i stedet for noe det er rent kvadratisk. 50 00:02:31,024 --> 00:02:33,440 Og det er ikke helt logaritmisk, det er litt mer enn det. 51 00:02:33,440 --> 00:02:36,520 Men hvis du husker fra klassen, Det var mye raskere. 52 00:02:36,520 --> 00:02:38,210 La oss ta en titt på hvor vi slapp. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble slags versus utvalg sorter versus merge sort. 55 00:02:45,370 --> 00:02:47,700 Nå er de alle kjører i teori, samtidig. 56 00:02:47,700 --> 00:02:50,510 CPU kjører i samme hastighet. 57 00:02:50,510 --> 00:02:54,990 Men du kan føle hvor kjedelig dette er svært raskt kommer til å bli, 58 00:02:54,990 --> 00:02:58,790 og hvor fort, når vi injiserer litt av uken null algoritmer, 59 00:02:58,790 --> 00:03:00,080 kan vi fart på sakene. 60 00:03:00,080 --> 00:03:01,630 >> Så mark liksom ser fantastisk. 61 00:03:01,630 --> 00:03:05,220 Hvordan kan vi utnytte det, for å sortere tall raskere. 62 00:03:05,220 --> 00:03:07,140 Vel la oss tenke tilbake til en ingrediens som vi 63 00:03:07,140 --> 00:03:10,380 hadde tilbake i uke null, nemlig søker etter noen i en telefonboken, 64 00:03:10,380 --> 00:03:12,380 og minner om at pseudokode som vi foreslått, 65 00:03:12,380 --> 00:03:14,560 via som vi kan finne noen som Mike Smith, 66 00:03:14,560 --> 00:03:16,310 så litt noe sånt som dette. 67 00:03:16,310 --> 00:03:20,820 >> Nå tar en titt i særdeleshet ved linje 7 og 8, og 10 og 11, 68 00:03:20,820 --> 00:03:25,240 som induserer at loop, der vi holdt går tilbake til linje 3 igjen, og igjen, 69 00:03:25,240 --> 00:03:26,520 og igjen. 70 00:03:26,520 --> 00:03:31,790 Men det viser seg at vi kan se denne algoritmen, her i pseudokode, 71 00:03:31,790 --> 00:03:33,620 litt mer helhetlig. 72 00:03:33,620 --> 00:03:35,960 Faktisk, hva jeg ser på her på skjermen, 73 00:03:35,960 --> 00:03:41,180 er en algoritme for å søke etter Mike Smith blant noen sett med sider. 74 00:03:41,180 --> 00:03:45,520 Og ja, vi kunne forenkle dette algoritmen i disse linjene 7 og 8, 75 00:03:45,520 --> 00:03:49,860 og 10 og 11 for å bare si dette, som jeg har presentert her i gult. 76 00:03:49,860 --> 00:03:52,210 Med andre ord, hvis Mike Smith er tidligere i boken, 77 00:03:52,210 --> 00:03:55,004 vi trenger ikke å spesifisere trinn trinn nå hvordan du skal gå finne ham. 78 00:03:55,004 --> 00:03:56,920 Vi trenger ikke å oppgi å gå tilbake til linje 3, 79 00:03:56,920 --> 00:03:58,960 hvorfor gjør vi ikke bare stedet, si, mer generelt, 80 00:03:58,960 --> 00:04:01,500 søke etter Mike i venstre halvdel av boken. 81 00:04:01,500 --> 00:04:03,960 >> Derimot, hvis Mike er faktisk senere i boken, 82 00:04:03,960 --> 00:04:07,540 hvorfor ikke vi bare sitere unquote søk for Mike i høyre halvdel av boken. 83 00:04:07,540 --> 00:04:11,030 Med andre ord, hvorfor gjør vi ikke bare slags punt til oss selv sier, 84 00:04:11,030 --> 00:04:13,130 søke etter Mike i denne undergruppe av boken, 85 00:04:13,130 --> 00:04:16,279 og la den til vår eksisterende algoritme for å fortelle oss 86 00:04:16,279 --> 00:04:18,750 hvordan du søker etter Mike i at venstre halvdel av boken. 87 00:04:18,750 --> 00:04:20,750 Med andre ord, vår algoritmen fungerer enten det er 88 00:04:20,750 --> 00:04:24,670 en telefon bok av denne tykkelse, av dette tykkelse, eller en hvilken som helst tykkelse hodet. 89 00:04:24,670 --> 00:04:27,826 Så vi kan rekursivt definere denne algoritmen. 90 00:04:27,826 --> 00:04:29,950 Med andre ord, i skjermen her, er en algoritme 91 00:04:29,950 --> 00:04:33,130 for å lete etter Mike Smith blant sidene i en telefonkatalog. 92 00:04:33,130 --> 00:04:37,410 Så i linje 7 og 10, la oss bare si akkurat det. 93 00:04:37,410 --> 00:04:40,250 Og jeg bruker dette begrepet et øyeblikk siden, og ja, rekursjon 94 00:04:40,250 --> 00:04:42,450 er buzzword for nå, og det er denne prosessen 95 00:04:42,450 --> 00:04:47,210 for å gjøre noe syklisk av en eller annen måte bruker kode som du allerede har, 96 00:04:47,210 --> 00:04:49,722 og kaller det igjen, og igjen, og igjen. 97 00:04:49,722 --> 00:04:51,930 Nå kommer det til å være viktig at vi liksom bunnen 98 00:04:51,930 --> 00:04:53,821 ut, og gjør ikke det uendelig lang. 99 00:04:53,821 --> 00:04:56,070 Ellers skal vi har faktisk en uendelig loop. 100 00:04:56,070 --> 00:04:59,810 Men la oss se om vi kan låne denne ideen av en rekursjon, gjør noe nytt 101 00:04:59,810 --> 00:05:03,600 og igjen og igjen, for å løse sorterings problem via merge 102 00:05:03,600 --> 00:05:05,900 sort, desto mer effektivt. 103 00:05:05,900 --> 00:05:06,970 >> Så jeg gir deg flette slag. 104 00:05:06,970 --> 00:05:07,920 La oss ta en titt. 105 00:05:07,920 --> 00:05:10,850 Så her er pseudokode, med som vi kunne implementere sortering, 106 00:05:10,850 --> 00:05:12,640 bruker denne algoritmen kalles merge sort. 107 00:05:12,640 --> 00:05:13,880 Og det er ganske enkelt dette. 108 00:05:13,880 --> 00:05:15,940 På innspill fra n elementer, med andre ord, hvis du er 109 00:05:15,940 --> 00:05:18,830 gitt n elementer og tall og bokstaver eller hva input er, 110 00:05:18,830 --> 00:05:22,430 hvis du får n elementer, hvis n er mindre enn to, bare tilbake. 111 00:05:22,430 --> 00:05:22,930 Høyre? 112 00:05:22,930 --> 00:05:26,430 Fordi hvis n er mindre enn 2, dvs. betyr at min liste over elementer 113 00:05:26,430 --> 00:05:30,446 er enten av størrelse 0 eller 1, og i begge disse triviell tilfeller 114 00:05:30,446 --> 00:05:31,570 listen allerede er sortert. 115 00:05:31,570 --> 00:05:32,810 Hvis det ikke er noen liste, er det sortert. 116 00:05:32,810 --> 00:05:35,185 Og hvis det er en liste over lengde 1, er det åpenbart sortert. 117 00:05:35,185 --> 00:05:38,280 Så algoritmen kun trenger å virkelig gjøre noe interessant, 118 00:05:38,280 --> 00:05:40,870 hvis vi har to eller flere elementer gitt til oss. 119 00:05:40,870 --> 00:05:42,440 Så la oss se på den magiske da. 120 00:05:42,440 --> 00:05:47,500 Else sortere den venstre halvdelen av elementene, deretter sortere høyre halvdel av elementene 121 00:05:47,500 --> 00:05:49,640 fletter deretter sortert halvdeler. 122 00:05:49,640 --> 00:05:52,440 Og hva er slags tankene bøyd her, er at jeg egentlig ikke 123 00:05:52,440 --> 00:05:56,190 synes å ha fortalt deg noe ennå, ikke sant? 124 00:05:56,190 --> 00:05:59,560 Alt jeg har sagt er, gitt en liste over n elementer, sortere venstre halvdel, 125 00:05:59,560 --> 00:06:01,800 Da den høyre halvdel, og deretter fusjonere de sortert halvdeler, 126 00:06:01,800 --> 00:06:03,840 men hvor er selve hemmeligheten saus? 127 00:06:03,840 --> 00:06:05,260 Hvor er algoritmen? 128 00:06:05,260 --> 00:06:09,150 Vel, det viser seg at disse to linjene først, liksom forlot halvparten av elementer, 129 00:06:09,150 --> 00:06:13,970 og sortere høyre halvdel av elementer, er rekursive samtaler, så å si. 130 00:06:13,970 --> 00:06:16,120 >> Tross alt, på dette tidspunkt, må jeg 131 00:06:16,120 --> 00:06:18,950 en algoritme som å sortere en hel haug med elementer? 132 00:06:18,950 --> 00:06:19,450 Ja. 133 00:06:19,450 --> 00:06:20,620 Det er rett her. 134 00:06:20,620 --> 00:06:25,180 Det er rett her på skjermen, og så jeg kan bruke det samme sett med trinn 135 00:06:25,180 --> 00:06:28,500 å sortere venstre halvdel, som jeg kan høyre halvdel. 136 00:06:28,500 --> 00:06:30,420 Og ja, igjen, og igjen. 137 00:06:30,420 --> 00:06:34,210 Så en eller annen måte, og vi vil snart se denne, den magiske merge sort 138 00:06:34,210 --> 00:06:37,967 er innebygd i det meget endelige linje, sammenslåing de sorterte halvdeler. 139 00:06:37,967 --> 00:06:39,300 Og det virker ganske intuitivt. 140 00:06:39,300 --> 00:06:41,050 Du tar to halvdeler, og du, en eller annen måte, flette dem sammen, 141 00:06:41,050 --> 00:06:43,260 og vi får se dette konkret i et øyeblikk. 142 00:06:43,260 --> 00:06:45,080 >> Men dette er en fullstendig algoritme. 143 00:06:45,080 --> 00:06:46,640 Og la oss se nøyaktig hvorfor. 144 00:06:46,640 --> 00:06:50,912 Vel antar at vi får de samme åtte elementer her på skjermen, ett 145 00:06:50,912 --> 00:06:53,120 gjennom åtte, men de er i tilsynelatende tilfeldig rekkefølge. 146 00:06:53,120 --> 00:06:55,320 Og målet for hånden er å sortere disse elementene. 147 00:06:55,320 --> 00:06:58,280 Vel hvordan kan jeg gå om gjøre det ved hjelp, igjen, 148 00:06:58,280 --> 00:07:00,407 flette slag, som per denne pseudo? 149 00:07:00,407 --> 00:07:02,740 Og igjen, ingrain dette i tankene dine, for bare et øyeblikk. 150 00:07:02,740 --> 00:07:05,270 Den første saken er ganske trivielt, hvis det er mindre enn 2, 151 00:07:05,270 --> 00:07:07,060 bare tilbake, det er ingen jobb å gjøre. 152 00:07:07,060 --> 00:07:09,290 Så egentlig er det bare tre tiltak for å virkelig huske på. 153 00:07:09,290 --> 00:07:11,081 Igjen og igjen, jeg kommer til å ønske å ha 154 00:07:11,081 --> 00:07:13,980 å sortere venstre halvdel, sortere høyre halvdel, 155 00:07:13,980 --> 00:07:15,890 og deretter en gang deres to halvdelene er sortert, 156 00:07:15,890 --> 00:07:18,710 Jeg ønsker å flette dem sammen inn i en sortert liste. 157 00:07:18,710 --> 00:07:19,940 Så hold det i tankene. 158 00:07:19,940 --> 00:07:21,310 >> Så her er den opprinnelige listen. 159 00:07:21,310 --> 00:07:23,510 La oss behandle dette som en array, så vi begynte å 160 00:07:23,510 --> 00:07:25,800 uke i to, som er et sammenhengende minneblokk. 161 00:07:25,800 --> 00:07:28,480 I dette tilfellet, som inneholder åtte tall, rygg mot rygg mot rygg. 162 00:07:28,480 --> 00:07:30,700 Og la oss nå søke merge sort. 163 00:07:30,700 --> 00:07:33,300 Så jeg først ønsker å sortere den venstre halvdelen av denne listen, 164 00:07:33,300 --> 00:07:37,370 og la oss derfor fokuserer på 4, 8, 6, og to. 165 00:07:37,370 --> 00:07:41,000 >> Nå hvordan går jeg om sortering en liste over størrelse 4? 166 00:07:41,000 --> 00:07:45,990 Vel jeg må nå vurdere sortering til venstre for den venstre halvdel. 167 00:07:45,990 --> 00:07:47,720 Igjen, la oss spole tilbake for bare et øyeblikk. 168 00:07:47,720 --> 00:07:51,010 Hvis pseudokode er dette, og jeg får åtte elementer, 169 00:07:51,010 --> 00:07:53,230 8 er åpenbart større enn eller lik 2. 170 00:07:53,230 --> 00:07:54,980 Så med det første tilfellet gjelder ikke. 171 00:07:54,980 --> 00:07:58,120 Så for å sortere åtte elementer, jeg først sortere den venstre halvdelen av elementer 172 00:07:58,120 --> 00:08:01,930 så jeg sortere høyre halvdel, så jeg flette de to sorterte halvdeler, hver på størrelse 4. 173 00:08:01,930 --> 00:08:02,470 OK. 174 00:08:02,470 --> 00:08:07,480 >> Men hvis du nettopp har fortalt meg, sortere venstre halvdel, som nå er i størrelse 4, 175 00:08:07,480 --> 00:08:09,350 hvordan kan jeg sortere venstre halvdel? 176 00:08:09,350 --> 00:08:11,430 Vel, hvis jeg har en input av fire elementer, 177 00:08:11,430 --> 00:08:14,590 Jeg først sortere venstre to, så kan den riktige to, 178 00:08:14,590 --> 00:08:16,210 og da jeg flette dem sammen. 179 00:08:16,210 --> 00:08:18,700 Så igjen, blir det litt av et sinn bøying spillet her, 180 00:08:18,700 --> 00:08:21,450 fordi du, hva slags, må huske hvor du er i historien, 181 00:08:21,450 --> 00:08:23,620 men på slutten av dagen, gis hvilket som helst antall elementer 182 00:08:23,620 --> 00:08:25,620 du først ønsker å sortere venstre halvdel, deretter høyre halvdel, 183 00:08:25,620 --> 00:08:26,661 deretter flette dem sammen. 184 00:08:26,661 --> 00:08:28,630 La oss begynne å gjøre akkurat det. 185 00:08:28,630 --> 00:08:30,170 Her er inngangen av åtte elementer. 186 00:08:30,170 --> 00:08:31,910 Nå vi ser på den venstre halvdelen her. 187 00:08:31,910 --> 00:08:33,720 Hvordan sorterer fire elementene gjør? 188 00:08:33,720 --> 00:08:35,610 Vel jeg først sortere venstre halvdel. 189 00:08:35,610 --> 00:08:37,720 Nå hvordan kan jeg sortere venstre halvdel? 190 00:08:37,720 --> 00:08:39,419 Vel jeg har fått to elementer. 191 00:08:39,419 --> 00:08:41,240 Så la oss sortere disse to elementene. 192 00:08:41,240 --> 00:08:44,540 2 er større enn eller lik 2, selvfølgelig. 193 00:08:44,540 --> 00:08:46,170 Så det første tilfellet gjelder ikke. 194 00:08:46,170 --> 00:08:49,010 >> Så jeg har nå til å sortere venstre halvparten av disse to elementer. 195 00:08:49,010 --> 00:08:50,870 Venstre halvdel, selvfølgelig, er bare fire. 196 00:08:50,870 --> 00:08:54,020 Så hvordan kan jeg sortere en liste over ett element? 197 00:08:54,020 --> 00:08:57,960 Vel nå, at spesielle base case opp toppen, så å si, gjelder. 198 00:08:57,960 --> 00:09:01,470 1 er mindre enn to, og min Listen er faktisk av størrelse 1. 199 00:09:01,470 --> 00:09:02,747 Så jeg bare tilbake. 200 00:09:02,747 --> 00:09:03,580 Jeg kan ikke gjøre noe. 201 00:09:03,580 --> 00:09:06,770 Og ja, se på hva jeg har gjort, er fire allerede sortert. 202 00:09:06,770 --> 00:09:09,220 Som jeg allerede delvis vellykket her. 203 00:09:09,220 --> 00:09:11,750 >> Nå som virker litt dum krav, men det er sant. 204 00:09:11,750 --> 00:09:13,700 4 er en liste over størrelse en. 205 00:09:13,700 --> 00:09:15,090 Det er allerede sortert. 206 00:09:15,090 --> 00:09:16,270 Det er den venstre halvdelen. 207 00:09:16,270 --> 00:09:18,010 Nå har jeg sortere høyre halvdel. 208 00:09:18,010 --> 00:09:22,310 Mitt innspill er ett element, 8 på samme måte, som allerede er sortert. 209 00:09:22,310 --> 00:09:25,170 Dum, også, men igjen, Dette grunnleggende prinsippet 210 00:09:25,170 --> 00:09:28,310 kommer til å tillate oss å nå bygge på toppen av dette med hell. 211 00:09:28,310 --> 00:09:32,260 4 sorteres, 8 sorteres, nå hva var det siste trinnet? 212 00:09:32,260 --> 00:09:35,330 Slik det tredje og siste trinnet, hvilken som helst gang du sortere en liste, husker, 213 00:09:35,330 --> 00:09:38,310 var å slå sammen de to halvdelene, venstre og høyre. 214 00:09:38,310 --> 00:09:39,900 Så la oss gjøre akkurat det. 215 00:09:39,900 --> 00:09:41,940 Min venstre halvdel er, selvfølgelig, 4. 216 00:09:41,940 --> 00:09:43,310 Min høyre halvdel er åtte. 217 00:09:43,310 --> 00:09:44,100 >> Så la oss gjøre dette. 218 00:09:44,100 --> 00:09:46,410 Først skal jeg fordele noen ekstra minne, 219 00:09:46,410 --> 00:09:48,680 at jeg skal representere her, som bare en sekundær array, 220 00:09:48,680 --> 00:09:49,660 som er stor nok til å passe dette. 221 00:09:49,660 --> 00:09:52,243 Men du kan forestille deg å utvide at rektangelet hele lengden, 222 00:09:52,243 --> 00:09:53,290 hvis vi trenger mer senere. 223 00:09:53,290 --> 00:09:58,440 Hvordan tar jeg 4 og 8, og flette disse to lister med størrelse 1 sammen? 224 00:09:58,440 --> 00:10:00,270 Også her ganske enkel. 225 00:10:00,270 --> 00:10:03,300 4 kommer først, så kommer 8. 226 00:10:03,300 --> 00:10:07,130 Fordi hvis jeg ønsker å sortere venstre halvdel, deretter høyre halvdel, 227 00:10:07,130 --> 00:10:09,900 og deretter fusjonere de to halvdelene sammen, i sortert orden, 228 00:10:09,900 --> 00:10:11,940 4 kommer først, så kommer 8. 229 00:10:11,940 --> 00:10:15,810 >> Så vi synes å være å gjøre fremgang, selv selv om jeg ikke har gjort noe faktisk arbeid. 230 00:10:15,810 --> 00:10:17,800 Men husk hvor vi er i historien. 231 00:10:17,800 --> 00:10:19,360 Vi opprinnelig tok åtte elementer. 232 00:10:19,360 --> 00:10:21,480 Vi sortert venstre halvdel, som er 4. 233 00:10:21,480 --> 00:10:24,450 Da vi sortert venstre halvdel av den venstre halvdelen, som var to. 234 00:10:24,450 --> 00:10:25,270 Og her vi går. 235 00:10:25,270 --> 00:10:26,920 Vi er ferdig med dette trinnet. 236 00:10:26,920 --> 00:10:29,930 >> Så hvis vi har sortert venstre halvdel av 2, nå er vi 237 00:10:29,930 --> 00:10:32,130 å sortere den høyre halvdel av to. 238 00:10:32,130 --> 00:10:35,710 Så høyre halvdel av 2 er disse to verdier her, 6 og 2. 239 00:10:35,710 --> 00:10:40,620 Så la oss nå ta en inngang på størrelse 2, og sortere den venstre halvdelen, og deretter 240 00:10:40,620 --> 00:10:42,610 høyre halvdel, og deretter flette dem sammen. 241 00:10:42,610 --> 00:10:45,722 Vel hvordan kan jeg sortere en liste over størrelse 1, som inneholder bare antall 6? 242 00:10:45,722 --> 00:10:46,430 Jeg er allerede gjort. 243 00:10:46,430 --> 00:10:48,680 Denne listen av størrelse 1 er sortert. 244 00:10:48,680 --> 00:10:52,140 >> Hvordan jeg sortere trenger en annen liste over størrelse 1, den såkalte høyre halvdel. 245 00:10:52,140 --> 00:10:54,690 Vel det også, er allerede sortert. 246 00:10:54,690 --> 00:10:56,190 Tallet 2 er alene. 247 00:10:56,190 --> 00:11:00,160 Så nå har jeg to halvdeler, venstre og rett, jeg trenger å flette dem sammen. 248 00:11:00,160 --> 00:11:01,800 La meg gi meg selv litt ekstra plass. 249 00:11:01,800 --> 00:11:05,580 Og sette to der inne, 6 så der derved 250 00:11:05,580 --> 00:11:10,740 sortering den listen, venstre og høyre, og sammenslåing det sammen til slutt. 251 00:11:10,740 --> 00:11:12,160 Så jeg er i litt bedre form. 252 00:11:12,160 --> 00:11:16,250 Jeg er ikke ferdig, fordi klart 4, 8, 2, 6 er ikke den endelige bestilling som jeg ønsker. 253 00:11:16,250 --> 00:11:20,640 Men jeg har nå to lister med størrelse 2, som har begge, henholdsvis, er sortert. 254 00:11:20,640 --> 00:11:24,580 Så nå hvis du spole tilbake i ditt indre øye, hvor ble det oss? 255 00:11:24,580 --> 00:11:28,520 Jeg startet med åtte elementer, så jeg whittled det ned til den venstre halvdelen av fire, 256 00:11:28,520 --> 00:11:31,386 Da den venstre halvdelen av to, og Da den høyre halvdel av 2, 257 00:11:31,386 --> 00:11:34,510 Jeg er ferdig, derfor, sortering venstre halvparten av to, og den høyre halvdel av 2, 258 00:11:34,510 --> 00:11:37,800 så hva er den tredje og siste trinnet her? 259 00:11:37,800 --> 00:11:41,290 Jeg må flette sammen to lister med størrelse 2. 260 00:11:41,290 --> 00:11:42,040 Så la oss gå videre. 261 00:11:42,040 --> 00:11:43,940 Og på skjermen her, gi meg noen ekstra minne, 262 00:11:43,940 --> 00:11:47,170 om teknisk, merker at jeg har fikk en hel haug med blank plass opp toppen 263 00:11:47,170 --> 00:11:47,670 der. 264 00:11:47,670 --> 00:11:50,044 Hvis jeg ønsker å være spesielt effektiv plass klokt, 265 00:11:50,044 --> 00:11:52,960 Jeg kunne bare begynne å bevege elementene frem og tilbake, topp og bunn. 266 00:11:52,960 --> 00:11:55,460 Men bare for visuell klarhet, Jeg kommer til å legge det ned nedenfor, 267 00:11:55,460 --> 00:11:56,800 å holde ting rent og pent. 268 00:11:56,800 --> 00:11:58,150 >> Så jeg har to lister med størrelse 2. 269 00:11:58,150 --> 00:11:59,770 Den første listen har fire og åtte. 270 00:11:59,770 --> 00:12:01,500 Den andre listen har to og seks. 271 00:12:01,500 --> 00:12:03,950 La oss slå dem sammen i sortert rekkefølge. 272 00:12:03,950 --> 00:12:09,910 2, selvsagt, kommer først deretter 4, deretter seks, deretter åtte. 273 00:12:09,910 --> 00:12:12,560 Og nå vi synes å være å få et sted interessant. 274 00:12:12,560 --> 00:12:15,720 Nå har jeg sortert halvdel av liste, og tilfeldigvis er det 275 00:12:15,720 --> 00:12:18,650 alle partall, men det er faktisk bare en tilfeldighet. 276 00:12:18,650 --> 00:12:22,220 Og jeg har nå sortert venstre halvparten, slik at den er 2, 4, 6, og 8. 277 00:12:22,220 --> 00:12:23,430 Ingenting er ute av drift. 278 00:12:23,430 --> 00:12:24,620 Det føles som pågår. 279 00:12:24,620 --> 00:12:26,650 >> Nå føles det som jeg har snakket alltid nå, 280 00:12:26,650 --> 00:12:29,850 så hva gjenstår å se om dette Algoritmen er faktisk mer effektivt. 281 00:12:29,850 --> 00:12:31,766 Men vi går igjennom det super metodisk. 282 00:12:31,766 --> 00:12:34,060 En datamaskin, selvfølgelig, ville gjøre det sånn. 283 00:12:34,060 --> 00:12:34,840 Så hvor er vi? 284 00:12:34,840 --> 00:12:36,180 Vi startet med åtte elementer. 285 00:12:36,180 --> 00:12:37,840 Jeg sortert venstre halvdel av fire. 286 00:12:37,840 --> 00:12:39,290 Jeg synes å bli ferdig med det. 287 00:12:39,290 --> 00:12:42,535 Så nå neste steg er å sortere høyre halvdel av fire. 288 00:12:42,535 --> 00:12:44,410 Og denne delen kan vi gå gjennom en litt mer 289 00:12:44,410 --> 00:12:47,140 raskt, selv om du er Velkommen til spole eller ta pause, bare 290 00:12:47,140 --> 00:12:49,910 tenke gjennom det på ditt eget tempo, men hva 291 00:12:49,910 --> 00:12:53,290 vi har nå er en mulighet til å gjøre akkurat det samme algoritme på fire 292 00:12:53,290 --> 00:12:54,380 forskjellige numre. 293 00:12:54,380 --> 00:12:57,740 >> Så la oss gå videre, og fokus på høyre halvdel, som vi er her. 294 00:12:57,740 --> 00:13:01,260 Den venstre halvdel av denne høyre halvdel, og nå 295 00:13:01,260 --> 00:13:04,560 venstre halvdel av venstre halvparten av det høyre halvdel, 296 00:13:04,560 --> 00:13:08,030 og hvordan kan jeg sortere en liste over størrelse En inneholdende bare antall 1? 297 00:13:08,030 --> 00:13:09,030 Det er allerede gjort. 298 00:13:09,030 --> 00:13:11,830 Hvordan gjør jeg det samme for en liste av størrelse 1 inneholder bare 7? 299 00:13:11,830 --> 00:13:12,840 Det er allerede gjort. 300 00:13:12,840 --> 00:13:16,790 Trinn tre for halvparten så er å slå sammen disse to elementene 301 00:13:16,790 --> 00:13:20,889 inn en ny liste over størrelse 2, 1 og 7. 302 00:13:20,889 --> 00:13:23,180 Synes ikke å ha gjort alt at mye interessant arbeid. 303 00:13:23,180 --> 00:13:24,346 La oss se hva som skjer videre. 304 00:13:24,346 --> 00:13:29,210 Jeg bare sortert venstre halvdel av høyre halvdel av mitt opprinnelige innspill. 305 00:13:29,210 --> 00:13:32,360 Nå la oss sortere riktig halvparten, som inneholder fem og tre. 306 00:13:32,360 --> 00:13:35,740 La oss igjen se på venstre halvparten, sortert, høyre halvdel, sortert, 307 00:13:35,740 --> 00:13:39,120 og flette de to sammen, inn noen ekstra plass, 308 00:13:39,120 --> 00:13:41,670 3 kommer først, så kommer 5. 309 00:13:41,670 --> 00:13:46,190 Og så nå har vi sortert venstre halvdel av den høyre halvdel 310 00:13:46,190 --> 00:13:49,420 av det opprinnelige problem, og den høyre halvdel av den høyre halvdel 311 00:13:49,420 --> 00:13:50,800 av det opprinnelige problem. 312 00:13:50,800 --> 00:13:52,480 Hva er den tredje og siste trinn? 313 00:13:52,480 --> 00:13:54,854 Vel å slå sammen de to halvdelene sammen. 314 00:13:54,854 --> 00:13:57,020 Så la meg få meg noen ekstra plass, men igjen, jeg 315 00:13:57,020 --> 00:13:58,699 kan bruke de ledig plass opp toppen. 316 00:13:58,699 --> 00:14:00,490 Men vi kommer til å holde det enkelt visuelt. 317 00:14:00,490 --> 00:14:07,070 La meg slå sammen i nå ett, og deretter tre, og deretter 5, og deretter 7. 318 00:14:07,070 --> 00:14:10,740 Dermed forlate meg nå med høyre halvparten av det opprinnelige problem 319 00:14:10,740 --> 00:14:12,840 som er perfekt sortert. 320 00:14:12,840 --> 00:14:13,662 >> Så hva gjenstår? 321 00:14:13,662 --> 00:14:16,120 Jeg føler at jeg holder å si det samme tingene igjen og igjen, 322 00:14:16,120 --> 00:14:18,700 men det er reflekterende av At vi bruker rekursjon. 323 00:14:18,700 --> 00:14:21,050 Prosessen med å bruke en algoritme igjen, og igjen, 324 00:14:21,050 --> 00:14:23,940 på mindre undergrupper av det opprinnelige problemet. 325 00:14:23,940 --> 00:14:27,580 Så jeg har nå en venstre sortert halvparten av det opprinnelige problem. 326 00:14:27,580 --> 00:14:30,847 Jeg har rett sortert halvparten av det opprinnelige problem. 327 00:14:30,847 --> 00:14:32,180 Hva er den tredje og siste trinnet? 328 00:14:32,180 --> 00:14:33,590 Åh, det er sammenslåing. 329 00:14:33,590 --> 00:14:34,480 Så la oss gjøre det. 330 00:14:34,480 --> 00:14:36,420 La oss sette av litt ekstra minne, men min Gud, vi 331 00:14:36,420 --> 00:14:37,503 kunne sette den hvor som helst nå. 332 00:14:37,503 --> 00:14:40,356 Vi har så mye ledig plass til oss, men vi vil holde det enkelt. 333 00:14:40,356 --> 00:14:42,730 Istedenfor å gå tilbake og frem med vår opprinnelige minne, 334 00:14:42,730 --> 00:14:44,480 la oss bare gjøre det visuelt ned her nedenfor, 335 00:14:44,480 --> 00:14:47,240 til slutt opp sammenslåing venstre halvdel og høyre halvdel. 336 00:14:47,240 --> 00:14:49,279 >> Så ved å slå sammen, hva må jeg gjøre? 337 00:14:49,279 --> 00:14:50,820 Jeg ønsker å ta elementene i orden. 338 00:14:50,820 --> 00:14:53,230 Så se på venstre halvdel, Jeg ser det første tallet er 2. 339 00:14:53,230 --> 00:14:55,230 Jeg ser på høyre halvdel, Jeg ser det første tallet 340 00:14:55,230 --> 00:14:58,290 er en, så åpenbart som nummer ønsker jeg å rykke ut, 341 00:14:58,290 --> 00:15:00,430 og satt først i min endelige listen? 342 00:15:00,430 --> 00:15:01,449 Selvfølgelig, 1. 343 00:15:01,449 --> 00:15:02,990 Nå ønsker jeg å stille det samme spørsmålet. 344 00:15:02,990 --> 00:15:05,040 På venstre halvdel, har jeg likevel fikk nummer 2. 345 00:15:05,040 --> 00:15:07,490 På den høyre halvdel, Jeg har fått nummer tre. 346 00:15:07,490 --> 00:15:08,930 Hvem av dem vil jeg skal velge? 347 00:15:08,930 --> 00:15:11,760 Selvfølgelig, nummer 2 og nå merke kandidatene 348 00:15:11,760 --> 00:15:13,620 er fire på venstre side, 3 på høyre side. 349 00:15:13,620 --> 00:15:15,020 La oss, selvfølgelig, velger tre. 350 00:15:15,020 --> 00:15:18,020 Nå kandidatene er fire på venstre, fem på høyre side. 351 00:15:18,020 --> 00:15:19,460 Vi selvsagt velge fire. 352 00:15:19,460 --> 00:15:21,240 6 på venstre, fem på høyre side. 353 00:15:21,240 --> 00:15:22,730 Vi selvsagt velge fem. 354 00:15:22,730 --> 00:15:25,020 6 på venstre side, 7 til høyre. 355 00:15:25,020 --> 00:15:29,320 Vi velger seks, og da vi velge 7, og da velger vi åtte. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Så et stort antall ord senere, vi har sortert denne listen over åtte elementer 358 00:15:34,370 --> 00:15:38,450 inn i en liste over en gjennom åtte, som er økende med hvert trinn, 359 00:15:38,450 --> 00:15:40,850 men hvor mye tid gjorde det tar oss å gjøre det. 360 00:15:40,850 --> 00:15:43,190 Vel jeg har bevisst Laid ting ut billedlig 361 00:15:43,190 --> 00:15:46,330 her, slik at vi kan slags se eller sette pris på divisjon 362 00:15:46,330 --> 00:15:49,060 i erobrende som har skjedd. 363 00:15:49,060 --> 00:15:52,830 >> Faktisk hvis du ser tilbake på kjølvannet, Jeg har forlatt alle disse stiplede linjene 364 00:15:52,830 --> 00:15:55,660 i aliaser, kan du, slags, se, i omvendt rekkefølge, 365 00:15:55,660 --> 00:15:58,800 hvis du slags se tilbake på historie nå, min opprinnelige liste 366 00:15:58,800 --> 00:16:00,250 er, selvfølgelig, av størrelse 8. 367 00:16:00,250 --> 00:16:03,480 Og så tidligere, var jeg arbeider med to lister med størrelse 4, 368 00:16:03,480 --> 00:16:08,400 og deretter fire lister med størrelse 2, og deretter åtte lister over størrelsen 1. 369 00:16:08,400 --> 00:16:10,151 >> Så hva gjør dette, slags, minne deg om? 370 00:16:10,151 --> 00:16:11,858 Vel, ja, noen av algoritmene vi har 371 00:16:11,858 --> 00:16:14,430 sett på så langt der vi dividere og dividere og dele, 372 00:16:14,430 --> 00:16:19,500 holde å ha ting på nytt, og igjen, resulterer i denne generelle ideen. 373 00:16:19,500 --> 00:16:23,100 Og så er det noe logaritmisk skjer her. 374 00:16:23,100 --> 00:16:26,790 Og det er ikke helt logg over n, men det er en logaritmisk komponent 375 00:16:26,790 --> 00:16:28,280 til det vi nettopp har gjort. 376 00:16:28,280 --> 00:16:31,570 >> Nå la oss vurdere hvordan det faktisk er. 377 00:16:31,570 --> 00:16:34,481 Så logger av n, igjen var en stor kjører tid, 378 00:16:34,481 --> 00:16:36,980 når vi gjorde noe sånt binære søk, som vi nå kaller det, 379 00:16:36,980 --> 00:16:40,090 skillet og hersk-strategi via som vi fant Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Nå teknisk. 381 00:16:41,020 --> 00:16:43,640 Det er log base 2 av n, selv men i de fleste matematikk klasser, 382 00:16:43,640 --> 00:16:45,770 10 er vanligvis basen som du antar. 383 00:16:45,770 --> 00:16:48,940 Men dataforskere nesten alltid tenker og snakker i form av base 2, 384 00:16:48,940 --> 00:16:52,569 så vi vanligvis bare si logg over n, i stedet for log base 2 av n, 385 00:16:52,569 --> 00:16:55,110 men de er akkurat ett og samme i verden av datamaskinen 386 00:16:55,110 --> 00:16:57,234 vitenskap, og som en side, det er en konstant faktor 387 00:16:57,234 --> 00:17:01,070 Forskjellen mellom de to, slik at den er Moot uansett, for mer formelle grunner. 388 00:17:01,070 --> 00:17:04,520 >> Men for nå, hva vi bryr oss om er dette eksempelet. 389 00:17:04,520 --> 00:17:08,520 Så la oss ikke bevise ved eksempel, men på Minst bruke et eksempel av tallene 390 00:17:08,520 --> 00:17:10,730 på hånden som en mental helse sjekk, hvis du vil. 391 00:17:10,730 --> 00:17:14,510 Så tidligere formelen var log basen 2 av n, men hva er n i dette tilfellet. 392 00:17:14,510 --> 00:17:18,526 Jeg hadde n opprinnelige tall, eller 8 av opprinnelige nummeret spesifikt. 393 00:17:18,526 --> 00:17:20,359 Nå har det vært en liten stund, men jeg er ganske 394 00:17:20,359 --> 00:17:25,300 sikker på at log base 2 av verdien 8 er 3, 395 00:17:25,300 --> 00:17:29,630 og ja, det er fint om det er 3 er det nøyaktig antall ganger 396 00:17:29,630 --> 00:17:33,320 at du kan dele opp en liste av lengde 8 igjen, og igjen, 397 00:17:33,320 --> 00:17:36,160 og igjen, helt til du sitter igjen med lister over bare størrelse 1. 398 00:17:36,160 --> 00:17:36,660 Høyre? 399 00:17:36,660 --> 00:17:40,790 8 går til 4, går til to, går til en, og det er 400 00:17:40,790 --> 00:17:43,470 reflekterende av akkurat det Bildet vi hadde bare et øyeblikk siden. 401 00:17:43,470 --> 00:17:47,160 Så litt sunn fornuft sjekk om hvor logaritmen er faktisk involvert. 402 00:17:47,160 --> 00:17:50,180 >> Så nå, hva annet er involvert her? n. 403 00:17:50,180 --> 00:17:53,440 Så merker at hver gang jeg dele listen, 404 00:17:53,440 --> 00:17:58,260 riktignok i omvendt rekkefølge i historien her, var jeg fortsatt gjør n ting. 405 00:17:58,260 --> 00:18:02,320 At sammenslåing trinnet kreves at Jeg berører hver og en av tallene, 406 00:18:02,320 --> 00:18:05,060 for å skyve den inn dens passende plassering. 407 00:18:05,060 --> 00:18:10,760 Så selv om høyden av denne diagrammet er av størrelse log n av n eller 3, 408 00:18:10,760 --> 00:18:13,860 spesifikt, med andre ord, Jeg gjorde tre divisjoner her. 409 00:18:13,860 --> 00:18:18,800 Hvor mye arbeid har jeg gjort horisontalt langs denne oversikten hver gang? 410 00:18:18,800 --> 00:18:21,110 >> Vel, jeg gjorde n trinnene fungere, fordi hvis jeg har 411 00:18:21,110 --> 00:18:24,080 fikk fire elementer og fire elementer, og jeg trenger å flette dem sammen. 412 00:18:24,080 --> 00:18:26,040 Jeg trenger å gå gjennom disse fire og disse fire, 413 00:18:26,040 --> 00:18:28,123 slutt å flette dem tilbake i åtte elementer. 414 00:18:28,123 --> 00:18:32,182 Hvis omvendt Jeg har åtte fingre over her, som jeg ikke gjør det, og åtte 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Hvis jeg har fikk fire fingre over her, 416 00:18:34,390 --> 00:18:37,380 som jeg gjør, fire fingre over her, som jeg gjør, 417 00:18:37,380 --> 00:18:40,590 så det er det samme eksempel som før, hvis jeg gjør 418 00:18:40,590 --> 00:18:44,010 har åtte fingre skjønt i totalt, som jeg kan, på en måte, gjør. 419 00:18:44,010 --> 00:18:47,950 Jeg kan egentlig gjøre her, Da kan jeg sikkert 420 00:18:47,950 --> 00:18:50,370 flette alle disse listene av størrelse 1 sammen. 421 00:18:50,370 --> 00:18:54,050 Men jeg absolutt må se på hvert element nøyaktig en gang. 422 00:18:54,050 --> 00:18:59,640 Slik at høyden på denne prosessen er log n, bredden av denne prosessen, så å si, 423 00:18:59,640 --> 00:19:02,490 er n, så hva vi synes å ha, til slutt, er 424 00:19:02,490 --> 00:19:06,470 en spilletid på størrelse n ganger log n. 425 00:19:06,470 --> 00:19:08,977 >> Med andre ord, vi delt listen, log n ganger, 426 00:19:08,977 --> 00:19:11,810 men hver gang vi gjorde det, hadde vi å berøre hver og en av elementene 427 00:19:11,810 --> 00:19:13,560 for å slå dem sammen alle sammen, noe 428 00:19:13,560 --> 00:19:18,120 ble n skritt, så vi har n ganger log n, eller som en datamaskin vitenskapsmann ville si, 429 00:19:18,120 --> 00:19:20,380 asymptotisk, som ville være store ord 430 00:19:20,380 --> 00:19:22,810 for å beskrive den øvre bundet på en driftstid, 431 00:19:22,810 --> 00:19:28,010 vi kjører i en stor o log n tid, så å si. 432 00:19:28,010 --> 00:19:31,510 >> Nå er dette viktig, fordi huske hva de kjører ganger var 433 00:19:31,510 --> 00:19:34,120 med boble sortere og utvalg sortere og innsetting sortere, 434 00:19:34,120 --> 00:19:38,200 og enda et par andre som eksisterer, n squared var der vi var på. 435 00:19:38,200 --> 00:19:39,990 Og du kan, på en måte, ser dette her. 436 00:19:39,990 --> 00:19:45,720 Hvis n squared er åpenbart n ganger n, men her har vi n ganger log n, 437 00:19:45,720 --> 00:19:48,770 og vi vet allerede fra uke null, som log n, logaritmisk, 438 00:19:48,770 --> 00:19:50,550 er bedre enn noe lineær. 439 00:19:50,550 --> 00:19:52,930 Tross alt, husker bildet med den røde og den gule 440 00:19:52,930 --> 00:19:56,500 og de grønne linjer som vi trakk, den grønn logaritmisk linje var mye lavere. 441 00:19:56,500 --> 00:20:00,920 Og derfor mye bedre og raskere enn de rette gule og røde linjer, 442 00:20:00,920 --> 00:20:05,900 n ganger log n er faktisk bedre enn n ganger n eller n kvadrat. 443 00:20:05,900 --> 00:20:09,110 >> Så vi synes å ha identifisert en algoritme merge 444 00:20:09,110 --> 00:20:11,870 sorter som går i mye raskere tid, og ja, 445 00:20:11,870 --> 00:20:16,560 det er derfor, tidligere denne uken, da vi så at konkurransen mellom boble 446 00:20:16,560 --> 00:20:20,750 sortere, utvalg sortere og flette sortere, fusjonere slags virkelig, virkelig vunnet. 447 00:20:20,750 --> 00:20:23,660 Og ja, vi hadde ikke engang vente for boble sortere og utvalg sort 448 00:20:23,660 --> 00:20:24,790 å bli ferdig. 449 00:20:24,790 --> 00:20:27,410 >> La oss nå ta en annen pass på dette, fra en litt mer 450 00:20:27,410 --> 00:20:31,030 formell perspektiv, bare i tilfellet, resonerer dette bedre 451 00:20:31,030 --> 00:20:33,380 enn det høyere nivå diskusjon. 452 00:20:33,380 --> 00:20:34,880 Så her er algoritmen igjen. 453 00:20:34,880 --> 00:20:36,770 La oss spørre oss selv, hvilken kjøretiden 454 00:20:36,770 --> 00:20:39,287 er av denne algoritmer forskjellige trinn? 455 00:20:39,287 --> 00:20:41,620 La oss dele det inn i den første saken og det andre tilfellet. 456 00:20:41,620 --> 00:20:46,280 IF og ellers i IF fall IF n er mindre enn to, bare tilbake. 457 00:20:46,280 --> 00:20:47,580 Føles som konstant tid. 458 00:20:47,580 --> 00:20:50,970 Det er, på en måte, som to trinn, IF n er mindre enn to, så tilbake. 459 00:20:50,970 --> 00:20:54,580 Men som vi sa på mandag, konstant tid, eller store o av en, 460 00:20:54,580 --> 00:20:57,130 kan være to trinn, tre trinn, og med 1.000 trinn. 461 00:20:57,130 --> 00:20:59,870 Det som betyr noe er at det er et konstant antall skritt. 462 00:20:59,870 --> 00:21:03,240 Så den gule uthevet pseudo her går i, vi kaller det, 463 00:21:03,240 --> 00:21:04,490 konstant tid. 464 00:21:04,490 --> 00:21:06,780 Så mer formelt, og vi kommer to-- dette 465 00:21:06,780 --> 00:21:09,910 vil være i hvilken grad vi formalisere denne retten now-- T av n, 466 00:21:09,910 --> 00:21:15,030 kjøretiden til et problem som tar n somethings som input, 467 00:21:15,030 --> 00:21:19,150 tilsvarer stort o av en, IF n er mindre enn to. 468 00:21:19,150 --> 00:21:20,640 Så det er betinget av det. 469 00:21:20,640 --> 00:21:24,150 Så for å være klar, IF n er mindre enn 2, har vi en veldig kort liste, deretter 470 00:21:24,150 --> 00:21:29,151 driftstiden, T av n, hvor n er 1 eller 0, i dette svært spesifikke tilfellet, 471 00:21:29,151 --> 00:21:30,650 det bare kommer til å være konstant tid. 472 00:21:30,650 --> 00:21:32,691 Det kommer til å ta ett trinn, to trinn, uansett. 473 00:21:32,691 --> 00:21:33,950 Det er et bestemt antall trinn. 474 00:21:33,950 --> 00:21:38,840 >> Så saftig del må sikkert være i det andre tilfellet i pseudokode. 475 00:21:38,840 --> 00:21:40,220 Den ELSE tilfelle. 476 00:21:40,220 --> 00:21:44,870 Sorter venstre halvdel av elementer, liksom rett halvparten av elementer, fusjonere sorterte halvdeler. 477 00:21:44,870 --> 00:21:46,800 Hvor lang tid tar hver av disse trinnene? 478 00:21:46,800 --> 00:21:49,780 Vel, hvis driften tid til å sortere n elementer 479 00:21:49,780 --> 00:21:53,010 er, la oss kalle det veldig generisk, T n; 480 00:21:53,010 --> 00:21:55,500 deretter sortering venstre halvparten av elementene 481 00:21:55,500 --> 00:21:59,720 er, på en måte, som å si, T n dividert med 2, 482 00:21:59,720 --> 00:22:03,000 og tilsvarende sortering høyre halvdel av elementer er, på en måte, som å si, 483 00:22:03,000 --> 00:22:06,974 T n oppdelt 2, og deretter sammenslåing av sortert halvdeler. 484 00:22:06,974 --> 00:22:08,890 Vel, hvis jeg har fått noen antall elementer her, 485 00:22:08,890 --> 00:22:11,230 som fire, og et antall av elementer her, som fire, 486 00:22:11,230 --> 00:22:14,650 og jeg må flette hver av disse fire i, og hver av disse fire i, ett 487 00:22:14,650 --> 00:22:17,160 etter den andre, slik at slutt Jeg har åtte elementer. 488 00:22:17,160 --> 00:22:20,230 Det føles som det er stor o av n trinn? 489 00:22:20,230 --> 00:22:23,500 Hvis jeg har fått n fingre og hver av dem har til å bli slått sammen på plass, 490 00:22:23,500 --> 00:22:25,270 det er som en annen n trinn. 491 00:22:25,270 --> 00:22:27,360 >> Så ja formulaically, Vi kan uttrykke dette, 492 00:22:27,360 --> 00:22:29,960 riktignok litt skremmende i starten øyekast, men det er noe 493 00:22:29,960 --> 00:22:31,600 som fanger opp akkurat det logikk. 494 00:22:31,600 --> 00:22:35,710 Kjøretiden, T for n, IF n er større enn eller lik 2. 495 00:22:35,710 --> 00:22:42,500 I dette tilfellet, ELSE tilfellet er T n dividert med to, i tillegg til T av N dividert med 2, 496 00:22:42,500 --> 00:22:45,320 pluss store o n, noen lineær antall skritt, 497 00:22:45,320 --> 00:22:51,630 kanskje akkurat n, kanskje 2 ganger n, men det er omtrent, orden n. 498 00:22:51,630 --> 00:22:54,060 Så det også, er hvordan vi kan uttrykke dette formulaically. 499 00:22:54,060 --> 00:22:56,809 Nå trenger du ikke ville vite dette med mindre du har spilt det i tankene dine, 500 00:22:56,809 --> 00:22:58,710 eller slå det opp i baksiden av en lærebok, som 501 00:22:58,710 --> 00:23:00,501 kan ha litt jukse ark på slutten, 502 00:23:00,501 --> 00:23:03,940 men dette er faktisk kommer til å gi oss en stor o n log n, 503 00:23:03,940 --> 00:23:06,620 fordi gjentakelse som du ser her på skjermen, 504 00:23:06,620 --> 00:23:09,550 hvis du faktisk gjorde det ut, med et uendelig antall eksempler, 505 00:23:09,550 --> 00:23:13,000 eller du gjorde det formulaically, ville du se at dette, fordi denne formelen 506 00:23:13,000 --> 00:23:17,100 selv er rekursiv, med t av n over noe på høyre side, 507 00:23:17,100 --> 00:23:21,680 og t av N over på venstre side, kan dette faktisk bli uttrykt, til slutt, 508 00:23:21,680 --> 00:23:24,339 som store go n log n. 509 00:23:24,339 --> 00:23:26,130 Hvis ikke overbevist, det er greit for nå, bare 510 00:23:26,130 --> 00:23:28,960 ta på tro, at det er, ja, hva som gjentakelse fører til, 511 00:23:28,960 --> 00:23:31,780 men dette er bare litt mer av en matematisk tilnærming til jakt 512 00:23:31,780 --> 00:23:36,520 på kjøretiden til merge sort basert på sin pseudokode alene. 513 00:23:36,520 --> 00:23:39,030 >> Nå la oss ta en bit av en pusterom fra alt dette, 514 00:23:39,030 --> 00:23:41,710 og ta en titt på en viss tidligere senator, som 515 00:23:41,710 --> 00:23:44,260 kan se litt kjent, som satte seg ned med Googles Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, en tid siden, for et intervju på scenen, foran en hel haug 517 00:23:48,410 --> 00:23:53,710 mennesker, snakke til slutt om et tema, det er ganske nå kjent. 518 00:23:53,710 --> 00:23:54,575 La oss ta en titt. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Nå Senator, du er her på Google, 521 00:24:03,890 --> 00:24:09,490 og jeg liker å tenke på formannskapet som et jobbintervju. 522 00:24:09,490 --> 00:24:11,712 Nå er det vanskelig å få en jobb som president. 523 00:24:11,712 --> 00:24:12,670 PRESIDENT OBAMA: Høyre. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: Og du er kommer til å gjøre [uhørbart] nå. 525 00:24:13,940 --> 00:24:15,523 Det er også vanskelig å få en jobb på Google. 526 00:24:15,523 --> 00:24:17,700 PRESIDENT OBAMA: Høyre. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Vi har spørsmål, og vi ber våre kandidater spørsmål, 528 00:24:21,330 --> 00:24:24,310 og dette er fra Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> PRESIDENT OBAMA: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Hva? 531 00:24:27,005 --> 00:24:28,130 Dere tror jeg tuller? 532 00:24:28,130 --> 00:24:30,590 Det er rett her. 533 00:24:30,590 --> 00:24:33,490 Hva er den mest effektive måten å sortere en million 32 bits heltall? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> PRESIDENT OBAMA: samt-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Noen ganger, kanskje jeg er lei meg, maybe-- 537 00:24:41,020 --> 00:24:42,750 PRESIDENT OBAMA: Nei, nei, nei, nei, nei, think-- jeg 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: Det er ikke it-- 539 00:24:43,240 --> 00:24:45,430 PRESIDENT OBAMA: I tror, ​​jeg tror boblen 540 00:24:45,430 --> 00:24:46,875 sorter ville være feil vei å gå. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Kom igjen. 543 00:24:50,535 --> 00:24:52,200 Som fortalte ham dette? 544 00:24:52,200 --> 00:24:54,020 OK. 545 00:24:54,020 --> 00:24:55,590 Jeg gjorde ikke det informatikk on-- 546 00:24:55,590 --> 00:24:58,986 >> PRESIDENT OBAMA: Vi har fikk våre spioner der inne. 547 00:24:58,986 --> 00:24:59,860 PROFESSOR: All right. 548 00:24:59,860 --> 00:25:03,370 La oss legge bak oss nå teoretisk verden av algoritmer 549 00:25:03,370 --> 00:25:06,520 i asymptotisk analyse av disse, og gå tilbake til noen temaer 550 00:25:06,520 --> 00:25:09,940 fra uke null og én, og start å fjerne noen trening hjul, 551 00:25:09,940 --> 00:25:10,450 Hvis du vil. 552 00:25:10,450 --> 00:25:13,241 Slik at du virkelig forstår til slutt opp fra grunnen av, hva er 553 00:25:13,241 --> 00:25:16,805 skjer under panseret, når du skrive, kompilere og kjøre programmer. 554 00:25:16,805 --> 00:25:19,680 Husker spesielt at dette var den første C-programmet vi så på, 555 00:25:19,680 --> 00:25:22,840 en kanonisk, enkelt program slags, relativt sett, 556 00:25:22,840 --> 00:25:24,620 hvor, det skrives, Hello World. 557 00:25:24,620 --> 00:25:27,610 Og husker at jeg sa, prosessen at kildekoden går gjennom 558 00:25:27,610 --> 00:25:28,430 er akkurat dette. 559 00:25:28,430 --> 00:25:31,180 Du tar din kildekode, pass det gjennom en kompilator, som klang, 560 00:25:31,180 --> 00:25:34,650 og ut kommer objektkode, som kan se ut som dette, nuller og enere 561 00:25:34,650 --> 00:25:37,880 at datamaskinens CPU, sentral processing unit eller hjerne, 562 00:25:37,880 --> 00:25:39,760 slutt forstår. 563 00:25:39,760 --> 00:25:42,460 >> Det viser seg at det er en litt av en overforenkling, 564 00:25:42,460 --> 00:25:44,480 at vi er nå i en posisjon til å erte hverandre 565 00:25:44,480 --> 00:25:46,720 å forstå hva som egentlig vært skjer under panseret 566 00:25:46,720 --> 00:25:48,600 hver gang du kjører Klang, eller mer generelt, 567 00:25:48,600 --> 00:25:53,040 hver gang du gjør et program, bruker Lag og CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Spesielt ting som dette er første generert, 569 00:25:56,760 --> 00:25:58,684 når du først kompilere programmet. 570 00:25:58,684 --> 00:26:00,600 Med andre ord, når ta kildekoden 571 00:26:00,600 --> 00:26:04,390 og kompilere den, hva er første blir sendt ut av klang 572 00:26:04,390 --> 00:26:06,370 er noe som kalles montering kode. 573 00:26:06,370 --> 00:26:08,990 Og faktisk, det ser ut akkurat som dette. 574 00:26:08,990 --> 00:26:11,170 >> Jeg kjørte en kommando på kommandolinje tidligere. 575 00:26:11,170 --> 00:26:16,260 Klang dash kapital s hello.c, og dette har skapt en fil 576 00:26:16,260 --> 00:26:19,490 for meg kalt hello.s, Innsiden var akkurat 577 00:26:19,490 --> 00:26:22,290 dette innholdet, og litt mer over og litt under, 578 00:26:22,290 --> 00:26:25,080 men jeg har satt den saftigste informasjon her på skjermen. 579 00:26:25,080 --> 00:26:29,190 Og hvis du ser nøye etter, vil du se minst et par kjente søkeord. 580 00:26:29,190 --> 00:26:31,330 Vi har hoved på toppen. 581 00:26:31,330 --> 00:26:35,140 Vi har printf ned i midten. 582 00:26:35,140 --> 00:26:38,670 Og vi har også hello world backslash n i anførselstegn ned nedenfor. 583 00:26:38,670 --> 00:26:42,450 >> Og alt annet her er svært lave nivå instruksjoner 584 00:26:42,450 --> 00:26:45,500 at datamaskinens CPU forstår. 585 00:26:45,500 --> 00:26:50,090 CPU instruksjoner som beveger minne rundt, som laster strenger fra minnet, 586 00:26:50,090 --> 00:26:52,750 og til slutt, print ting på skjermen. 587 00:26:52,750 --> 00:26:56,780 Nå hva som skjer om etter denne forsamlingen kode genereres? 588 00:26:56,780 --> 00:26:59,964 Til syvende og sist, gjør du, ja, fortsatt genererer objektkode. 589 00:26:59,964 --> 00:27:02,630 Men trinnene som har virkelig pågått under panseret 590 00:27:02,630 --> 00:27:04,180 ser litt mer ut som dette. 591 00:27:04,180 --> 00:27:08,390 Kildekode blir montering kode, som deretter blir objektkode, 592 00:27:08,390 --> 00:27:11,930 og de operative ord her er det, når du kompilere kildekoden, 593 00:27:11,930 --> 00:27:16,300 ut kommer montering kode, og deretter når du monterer montering kode, 594 00:27:16,300 --> 00:27:17,800 ut kommer objektkode. 595 00:27:17,800 --> 00:27:20,360 >> Nå klang er super sofistikert, som mange kompilatorer, 596 00:27:20,360 --> 00:27:23,151 og det gjør alle disse trinnene sammen, og det gjør ikke nødvendigvis 597 00:27:23,151 --> 00:27:25,360 utgang mellomliggende filer som du selv kan se. 598 00:27:25,360 --> 00:27:28,400 Det kompilerer bare ting, som er den generelle betegnelsen som 599 00:27:28,400 --> 00:27:30,000 beskriver hele denne prosessen. 600 00:27:30,000 --> 00:27:32,000 Men hvis du virkelig ønsker å være særlig, er det 601 00:27:32,000 --> 00:27:34,330 mye mer å gå på der også. 602 00:27:34,330 --> 00:27:38,860 >> Men la oss også vurdere nå at selv at super enkelt program, hello.c, 603 00:27:38,860 --> 00:27:40,540 kalles en funksjon. 604 00:27:40,540 --> 00:27:41,870 Det kalles printf. 605 00:27:41,870 --> 00:27:46,900 Men jeg skrev ikke printf, ja, som følger med c, så å si. 606 00:27:46,900 --> 00:27:51,139 Det er en funksjon tilbakekalling som er deklarert i standard io.h, som 607 00:27:51,139 --> 00:27:53,180 er en header fil, som er et tema vi faktisk 608 00:27:53,180 --> 00:27:55,780 dykke mer i dybden før lenge. 609 00:27:55,780 --> 00:27:58,000 Men en header fil vanligvis ledsaget 610 00:27:58,000 --> 00:28:02,920 av en kode fil, kildekode fil, så mye som det finnes standard io.h. 611 00:28:02,920 --> 00:28:05,930 >> Gang siden, noen, eller vekke, skrev også 612 00:28:05,930 --> 00:28:11,040 en fil som heter standard io.c, i som selve definisjonene, 613 00:28:11,040 --> 00:28:15,220 eller implementeringer av printf, og bunter av andre funksjoner, 614 00:28:15,220 --> 00:28:16,870 er faktisk skrevet. 615 00:28:16,870 --> 00:28:22,140 Så gitt at, hvis vi vurdere å ha her til venstre, hello.c, at når 616 00:28:22,140 --> 00:28:26,250 utarbeidet, gir oss hello.s, selv om Klang ikke bry besparelse på et sted 617 00:28:26,250 --> 00:28:31,360 vi kan se det, og at forsamlingen kode blir satt sammen til hello.o, som 618 00:28:31,360 --> 00:28:34,630 er faktisk standardnavnet gitt når du kompilere kilde 619 00:28:34,630 --> 00:28:39,350 kode til objektkode, men er ikke helt klar til å kjøre den ennå, 620 00:28:39,350 --> 00:28:41,460 fordi et nytt skritt må skje, og har 621 00:28:41,460 --> 00:28:44,440 foregått de siste par uker, kanskje ukjent for deg. 622 00:28:44,440 --> 00:28:47,290 >> Spesifikt sted i CS50 IDE, og dette, 623 00:28:47,290 --> 00:28:49,870 også vil være litt av en forenkling for et øyeblikk, 624 00:28:49,870 --> 00:28:54,670 det er, eller var en gang, en fil som heter standard io.c, 625 00:28:54,670 --> 00:28:58,440 at noen kompilert inn standard io.s eller tilsvarende, 626 00:28:58,440 --> 00:29:02,010 at noen deretter satt sammen inn standard io.o, 627 00:29:02,010 --> 00:29:04,600 eller det viser seg i en litt annen fil 628 00:29:04,600 --> 00:29:07,220 format som kan ha en annen filtypen helt, 629 00:29:07,220 --> 00:29:11,720 men i teorien og konseptuelt, nøyaktig disse trinnene måtte skje i en eller annen form. 630 00:29:11,720 --> 00:29:14,060 Som er å si, at nå når jeg skriver et program, 631 00:29:14,060 --> 00:29:17,870 hello.c, som bare sier hei verden, og jeg bruker noen andres kode 632 00:29:17,870 --> 00:29:22,480 som printf, som var en gang i tid, i en fil som heter standard io.c, 633 00:29:22,480 --> 00:29:26,390 så en eller annen måte må jeg ta min objektkode, mine nuller og enere, 634 00:29:26,390 --> 00:29:29,260 og at personens objekt kode, eller nuller og enere, 635 00:29:29,260 --> 00:29:34,970 og liksom koble dem sammen til en siste fil, kalt hallo, at 636 00:29:34,970 --> 00:29:38,070 har alle de nuller og de fra min hovedfunksjon, 637 00:29:38,070 --> 00:29:40,830 og alle nuller og de for printf. 638 00:29:40,830 --> 00:29:44,900 >> Og ja, det er siste ferd heter, linke din objektkode. 639 00:29:44,900 --> 00:29:47,490 Utgangen fra hvilken er en kjørbar fil. 640 00:29:47,490 --> 00:29:49,780 Så i rettferdighet, på slutten av dagen, noe 641 00:29:49,780 --> 00:29:52,660 har endret seg siden uke en, når vi først begynte å kompilere programmer. 642 00:29:52,660 --> 00:29:55,200 Faktisk har alt dette vært skjer under panseret, 643 00:29:55,200 --> 00:29:57,241 men nå er vi i en posisjon hvor vi faktisk kan 644 00:29:57,241 --> 00:29:58,794 erte hverandre disse ulike trinnene. 645 00:29:58,794 --> 00:30:00,710 Og faktisk, på slutten av dagen, vi er fortsatt 646 00:30:00,710 --> 00:30:04,480 igjen med nuller og enere, som er faktisk en fin naturlig overgang nå 647 00:30:04,480 --> 00:30:08,620 til et annet evnen til C, som vi har ikke hatt til å utnytte mest sannsynlig 648 00:30:08,620 --> 00:30:11,250 til dags dato, kjent som bitvis operatører. 649 00:30:11,250 --> 00:30:15,220 Med andre ord, så langt, når som helst vi har jobbet med data i C eller variabler i C, 650 00:30:15,220 --> 00:30:17,660 vi har hatt ting som chars og flyter og ins 651 00:30:17,660 --> 00:30:21,990 og lengter og dobler og lignende, men alle av dem er minst åtte bits. 652 00:30:21,990 --> 00:30:25,550 Vi har aldri ennå ikke vært i stand til å manipulere individuelle biter, 653 00:30:25,550 --> 00:30:28,970 selv om en individuell bit, vi vet, kan representere en 0 og 1. 654 00:30:28,970 --> 00:30:32,640 Nå viser det seg at i C, du kan få tilgang til enkelte biter, 655 00:30:32,640 --> 00:30:35,530 hvis du vet syntaks, med å få på dem. 656 00:30:35,530 --> 00:30:38,010 >> Så la oss ta en titt på bitvis operatører. 657 00:30:38,010 --> 00:30:41,700 Så avbildet her er noen symboler som vi har, type, liksom, sett før. 658 00:30:41,700 --> 00:30:45,580 Jeg ser en ampersand, en vertikal bar, og noen andre også, 659 00:30:45,580 --> 00:30:49,430 og husker at ampersand-tegn er noe vi har sett før. 660 00:30:49,430 --> 00:30:54,060 Den logiske AND operatør, hvor du har to av dem sammen, eller den logiske OR 661 00:30:54,060 --> 00:30:56,300 operatør, hvor du har to loddrette streker. 662 00:30:56,300 --> 00:31:00,550 Bitvis operatører, som vi vil se operere på bitene hver for seg, 663 00:31:00,550 --> 00:31:03,810 bare bruke en enkelt-tegn, en enkelt vertikal bar, cirkumflekstegnet symbol 664 00:31:03,810 --> 00:31:06,620 kommer etterpå, den lille tilde, og deretter til venstre 665 00:31:06,620 --> 00:31:08,990 brakett venstre brakett, eller høyre brakett høyre brakett. 666 00:31:08,990 --> 00:31:10,770 Hver av disse har forskjellige betydninger. 667 00:31:10,770 --> 00:31:11,950 >> Faktisk, la oss ta en titt. 668 00:31:11,950 --> 00:31:16,560 La oss gå gamle skolen i dag, og bruk en berøringsskjerm fra en svunnen tid, 669 00:31:16,560 --> 00:31:18,002 kjent som en hvit bord. 670 00:31:18,002 --> 00:31:19,710 Og denne hvite bord kommer til å tillate oss 671 00:31:19,710 --> 00:31:27,360 å uttrykke noen ganske enkle symboler, eller rettere sagt noen ganske enkle formler, 672 00:31:27,360 --> 00:31:29,560 at vi kan så til slutt innflytelse, for 673 00:31:29,560 --> 00:31:33,230 å få tilgang til enkelte bits innenfor et C-program. 674 00:31:33,230 --> 00:31:34,480 Med andre ord, la oss gjøre dette. 675 00:31:34,480 --> 00:31:37,080 La oss først snakke om en øyeblikk om ampersand, 676 00:31:37,080 --> 00:31:39,560 som er bitvis AND operatør. 677 00:31:39,560 --> 00:31:42,130 Med andre ord er denne en operatør som gjør det mulig 678 00:31:42,130 --> 00:31:45,930 meg å ha en venstre variabel typisk, og en høyre variabel, 679 00:31:45,930 --> 00:31:50,640 eller en enkeltverdi, at hvis vi AND dem sammen, gir meg et endelig resultat. 680 00:31:50,640 --> 00:31:51,560 Så hva mener jeg? 681 00:31:51,560 --> 00:31:54,840 Hvis du er i et program, har du en variabel som lagrer en av disse verdiene 682 00:31:54,840 --> 00:31:58,000 eller la oss holde det enkelt, og bare skrive ut nuller og enere individuelt, 683 00:31:58,000 --> 00:32:00,940 her er hvordan tegnet operatør fungerer. 684 00:32:00,940 --> 00:32:06,400 0 tegnet 0 kommer til å like 0. 685 00:32:06,400 --> 00:32:07,210 Nå hvorfor er det? 686 00:32:07,210 --> 00:32:09,291 >> Det er svært lik Boolske uttrykk, 687 00:32:09,291 --> 00:32:10,540 at vi har diskutert så langt. 688 00:32:10,540 --> 00:32:15,800 Hvis du tror tross alt, er det 0 falsk, er falsk, falsk og usann 0 689 00:32:15,800 --> 00:32:18,720 er, som vi har diskutert logisk, også falske. 690 00:32:18,720 --> 00:32:20,270 Så vi får 0 her også. 691 00:32:20,270 --> 00:32:24,390 Hvis du tar 0-tegn 1, vel det også, 692 00:32:24,390 --> 00:32:29,890 kommer til å være 0, fordi for dette venstre uttrykk for å være sanne eller 1, 693 00:32:29,890 --> 00:32:32,360 det må være sant og ekte. 694 00:32:32,360 --> 00:32:36,320 Men her har vi false og sant, eller 0 og 1. 695 00:32:36,320 --> 00:32:42,000 Nå igjen, hvis vi har en ampersand 0, som også kommer til å være 0, 696 00:32:42,000 --> 00:32:47,240 og hvis vi har en ampersand 1, endelig har vi en 1 bit. 697 00:32:47,240 --> 00:32:50,340 Så med andre ord, vi ikke gjør noe interessant med denne operatøren 698 00:32:50,340 --> 00:32:51,850 ennå, dette tegnet operatør. 699 00:32:51,850 --> 00:32:53,780 Det er bitvis AND operatør. 700 00:32:53,780 --> 00:32:57,290 Men disse er ingrediensene via som vi kan gjøre 701 00:32:57,290 --> 00:32:59,240 interessante ting, som vi snart se. 702 00:32:59,240 --> 00:33:02,790 >> La oss nå se på akkurat enkelt vertikale linjen over her til høyre. 703 00:33:02,790 --> 00:33:06,710 Hvis jeg har en 0 bit og jeg ELLER den med, bitvis 704 00:33:06,710 --> 00:33:11,030 OR operatør, en annen 0 bit, som kommer til å gi meg 0. 705 00:33:11,030 --> 00:33:17,540 Hvis jeg tar en 0 bit og OR det med en 1 bit, så jeg kommer til å få en. 706 00:33:17,540 --> 00:33:19,830 Og faktisk, bare for klarhet, la meg gå tilbake, 707 00:33:19,830 --> 00:33:23,380 slik at mine vertikale linjene ikke forveksles med en s. 708 00:33:23,380 --> 00:33:26,560 La meg omskrive alle min en er litt mer 709 00:33:26,560 --> 00:33:32,700 tydelig, slik at vi neste ser, hvis jeg har en 1 eller 0, som kommer til å være en 1, 710 00:33:32,700 --> 00:33:39,060 og hvis jeg har en 1 eller en som, også, kommer til å bli en en. 711 00:33:39,060 --> 00:33:42,900 Så du kan se logisk at OR operatør oppfører seg veldig annerledes. 712 00:33:42,900 --> 00:33:48,070 Dette gir meg 0 ELLER 0 gir meg 0, men annenhver kombinasjonen gir meg en. 713 00:33:48,070 --> 00:33:52,480 Så lenge jeg har en 1 i formel, er resultatet vil være en. 714 00:33:52,480 --> 00:33:55,580 >> I motsetning til AND operatør,-tegnet, 715 00:33:55,580 --> 00:34:00,940 bare hvis jeg har to 1-er i ligningen, jeg faktisk får en en ut. 716 00:34:00,940 --> 00:34:02,850 Nå er det et par andre operatører. 717 00:34:02,850 --> 00:34:04,810 En av dem er litt mer involvert. 718 00:34:04,810 --> 00:34:07,980 Så la meg gå videre og slette dette for å frigjøre litt plass. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Og la oss ta en titt på caret symbol, for bare et øyeblikk. 721 00:34:16,460 --> 00:34:18,210 Dette er typisk en tegn du kan skrive 722 00:34:18,210 --> 00:34:21,420 på tastaturet holding Shift og deretter ett av tallene oppå din US 723 00:34:21,420 --> 00:34:22,250 tastatur. 724 00:34:22,250 --> 00:34:26,190 >> Så dette er den eksklusive OR operatør, eksklusive ELLER. 725 00:34:26,190 --> 00:34:27,790 Så vi bare så ELLER operatør. 726 00:34:27,790 --> 00:34:29,348 Dette er den eksklusive operatoren OR. 727 00:34:29,348 --> 00:34:30,639 Hva er egentlig forskjellen? 728 00:34:30,639 --> 00:34:34,570 Vel la oss bare se på formelen, og bruke dette som ingredienser til slutt. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Jeg kommer til å si er alltid 0. 731 00:34:39,650 --> 00:34:41,400 Det er definisjonen av XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR en kommer til å være en. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 kommer til å bli en, og en XOR en kommer til å være? 734 00:34:58,810 --> 00:34:59,890 Galt? 735 00:34:59,890 --> 00:35:00,520 Eller rett? 736 00:35:00,520 --> 00:35:01,860 Jeg vet ikke. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Nå hva som skjer her? 739 00:35:04,700 --> 00:35:06,630 Vel tenke på Navnet på denne operatøren. 740 00:35:06,630 --> 00:35:09,980 Eksklusive ELLER-, så som navn, foreslår, 741 00:35:09,980 --> 00:35:13,940 Svaret er bare kommer til å være en 1 hvis inngangene er eksklusiv, 742 00:35:13,940 --> 00:35:15,560 utelukkende annerledes. 743 00:35:15,560 --> 00:35:18,170 Så her inngangene er samme, slik at produksjonen er 0. 744 00:35:18,170 --> 00:35:20,700 Her inngangene er samme, slik at produksjonen er 0. 745 00:35:20,700 --> 00:35:25,640 Her er de utgangene er forskjellige, de er eksklusive, og slik at produksjonen er en. 746 00:35:25,640 --> 00:35:28,190 Så det er svært lik OG, det er veldig likt, 747 00:35:28,190 --> 00:35:32,760 eller rettere sagt det er svært lik OR, men bare i en eksklusiv måte. 748 00:35:32,760 --> 00:35:36,210 Dette er ikke lenger en 1, fordi vi har to 1-tallet, 749 00:35:36,210 --> 00:35:38,621 og ikke utelukkende, bare en av dem. 750 00:35:38,621 --> 00:35:39,120 Greit. 751 00:35:39,120 --> 00:35:40,080 Hva med de andre? 752 00:35:40,080 --> 00:35:44,220 Vel tilde, i mellomtiden, er faktisk fin og enkel, heldigvis. 753 00:35:44,220 --> 00:35:46,410 Og dette er en enhetlige Operatøren, som betyr 754 00:35:46,410 --> 00:35:50,400 det er påført bare en inngang, én operand, så å si. 755 00:35:50,400 --> 00:35:51,800 Ikke til en venstre og en til høyre. 756 00:35:51,800 --> 00:35:56,050 Med andre ord, hvis du tar tilde av 0, vil svaret være det motsatte. 757 00:35:56,050 --> 00:35:59,710 Og hvis du tar tilde av en, den Svaret vil det være motsatt. 758 00:35:59,710 --> 00:36:02,570 Så tilde operatør er en måte å benektende litt, 759 00:36:02,570 --> 00:36:06,000 eller bla litt fra Fra 0 til 1 eller 1 til 0. 760 00:36:06,000 --> 00:36:09,820 >> Og som etterlater oss til slutt med bare to endelige operatører, 761 00:36:09,820 --> 00:36:13,840 den såkalte venstre skift, og såkalte høyre shift operatør. 762 00:36:13,840 --> 00:36:16,620 La oss ta en titt på hvordan de arbeidet. 763 00:36:16,620 --> 00:36:20,780 Den venstre skifte operatør skrevet med to vinkelparenteser som det, 764 00:36:20,780 --> 00:36:22,110 virker som følger. 765 00:36:22,110 --> 00:36:27,390 Hvis mitt innspill, eller min operand, til venstre skifte operatør er ganske enkelt en en. 766 00:36:27,390 --> 00:36:33,750 Og jeg da fortelle datamaskinen til venstre skift som en, sier syv plasser, 767 00:36:33,750 --> 00:36:37,150 resultatet er som om jeg ta det en, og flytt den 768 00:36:37,150 --> 00:36:40,160 syv steder i løpet av venstre, og som standard, 769 00:36:40,160 --> 00:36:42,270 vi kommer til å anta at rom til høyre 770 00:36:42,270 --> 00:36:44,080 kommer til å være polstret med nuller. 771 00:36:44,080 --> 00:36:50,316 Med andre ord, en venstre shift 7 kommer å gi meg at 1, fulgt av 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 nuller. 773 00:36:54,060 --> 00:36:57,380 Så på en måte, det kan du ta et lite tall som 1, 774 00:36:57,380 --> 00:37:00,740 og tydelig gjør det mye mye, mye større på denne måten 775 00:37:00,740 --> 00:37:06,460 men vi er faktisk kommer til å se mer smarte tilnærminger for det 776 00:37:06,460 --> 00:37:08,080 i stedet, samt, 777 00:37:08,080 --> 00:37:08,720 >> Greit. 778 00:37:08,720 --> 00:37:10,060 Det er det for uke tre. 779 00:37:10,060 --> 00:37:11,400 Vi vil se deg neste gang. 780 00:37:11,400 --> 00:37:12,770 Dette var CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [MUSIC SPILLE] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Han var på snack bar spise en hot fudge sundae. 784 00:37:25,766 --> 00:37:28,090 Han hadde det over hele ansiktet hans. 785 00:37:28,090 --> 00:37:30,506 Han har på seg at sjokolade som et skjegg 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Hva er det du gjør? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Hva? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Visste du bare dobbel dip? 790 00:37:36,800 --> 00:37:38,585 Du dobbelt dyppet brikken. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Unnskyld meg. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Du dyppet chip, du tok en bit, og du dyppet igjen. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Så det er som å sette hele munnen rett i dip. 795 00:37:48,440 --> 00:37:52,400 Neste gang du tar en chip, bare dyppe det en gang, og avslutte den. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Vet du hva, Dan? 797 00:37:53,890 --> 00:37:58,006 Du dyppe den måten at du ønsker å dyppe. 798 00:37:58,006 --> 00:38:01,900 Jeg skal dyppe den måten at jeg ønsker å dyppe. 799 00:38:01,900 --> 00:38:03,194