1 00:00:00,000 --> 00:00:11,904 >> [Musik spiller] 2 00:00:11,904 --> 00:00:12,910 >> PROFESSOR: Okay. 3 00:00:12,910 --> 00:00:16,730 Dette er CS50, og det er i slutningen af ​​ugen tre. 4 00:00:16,730 --> 00:00:20,230 Så vi er her i dag, ikke i Sanders Teater, i stedet i Weidner Bibliotek. 5 00:00:20,230 --> 00:00:23,170 Inderside er et studie kendt som Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 eller skal vi sige Studio H, eller skal vi say-- hvis du har nydt at joke, 7 00:00:28,310 --> 00:00:30,540 det er faktisk fra klassekammerat, Mark, online, 8 00:00:30,540 --> 00:00:32,420 der foreslog så meget via Twitter. 9 00:00:32,420 --> 00:00:34,270 Nu, hvad er cool om være her i et studie 10 00:00:34,270 --> 00:00:38,410 er, at jeg er omgivet af disse grønne vægge, en grøn skærm eller chromakey, 11 00:00:38,410 --> 00:00:43,290 så at sige, hvilket betyder, at CS50 s produktion team, ukendt for mig 12 00:00:43,290 --> 00:00:47,380 lige nu, kunne være at sætte mig mest overalt i verden, 13 00:00:47,380 --> 00:00:48,660 for bedre eller værre. 14 00:00:48,660 --> 00:00:51,800 >> Nu, hvad der ligger forude, problem sæt to er i dine hænder for denne uge, 15 00:00:51,800 --> 00:00:53,830 men med problemet sæt tre i den kommende uge, 16 00:00:53,830 --> 00:00:56,600 vil du blive udfordret med den såkaldte omgang 15, 17 00:00:56,600 --> 00:00:58,960 en gammel part favor, at du måske huske at modtage 18 00:00:58,960 --> 00:01:02,030 som et barn, der har en hel flok af numre, som kan glide op, ned, 19 00:01:02,030 --> 00:01:05,790 venstre og højre, og der er én hul inden puslespillet, hvori du 20 00:01:05,790 --> 00:01:07,840 kan faktisk skubbe disse puslespilsbrikker. 21 00:01:07,840 --> 00:01:11,150 I sidste ende du modtager denne puslespil i nogle semi tilfældig rækkefølge, 22 00:01:11,150 --> 00:01:12,940 og målet er at sortere det, top til bund, 23 00:01:12,940 --> 00:01:16,310 venstre til højre, fra en hele vejen op gennem 15. 24 00:01:16,310 --> 00:01:19,360 >> Desværre, gennemførelse vil du have ved hånden 25 00:01:19,360 --> 00:01:21,590 vil være software baseret, ikke fysisk. 26 00:01:21,590 --> 00:01:25,280 Du faktisk nødt til at skrive kode med som en studerende eller bruger dåse 27 00:01:25,280 --> 00:01:26,760 spille spillet på 15. 28 00:01:26,760 --> 00:01:29,030 Og i virkeligheden, i hacker udgave af spillet på 15, 29 00:01:29,030 --> 00:01:32,155 vil du være en udfordring at gennemføre, ikke bare at spille i denne gamle skole 30 00:01:32,155 --> 00:01:35,010 spil, men snarere løsningen af det, gennemføre gud tilstand, 31 00:01:35,010 --> 00:01:38,280 så at sige, der rent faktisk løser puslespillet for den humane, 32 00:01:38,280 --> 00:01:41,080 ved at give dem tip, efter tip, efter tip. 33 00:01:41,080 --> 00:01:42,280 Så mere om det i næste uge. 34 00:01:42,280 --> 00:01:43,720 Men det er, hvad der ligger forude. 35 00:01:43,720 --> 00:01:47,610 >> For nu huske, at tidligere i denne uge vi havde denne cliffhanger, hvis du vil, 36 00:01:47,610 --> 00:01:52,560 hvorved det bedste, vi gjorde sortering klogt var en øvre grænse for store o n 37 00:01:52,560 --> 00:01:53,210 potens. 38 00:01:53,210 --> 00:01:56,520 Med andre ord, boble sortere, udvælgelse sortere, indsættelse sortere, 39 00:01:56,520 --> 00:01:59,120 dem alle, selvom de er forskellige i deres gennemførelse, 40 00:01:59,120 --> 00:02:03,480 overdrages til en n kvadreret kører tid i værste fald. 41 00:02:03,480 --> 00:02:06,010 Og vi generelt antager, at det værste tilfælde til sortering 42 00:02:06,010 --> 00:02:08,814 er en, der dine input er helt bagud. 43 00:02:08,814 --> 00:02:11,980 Og ja, det tog et par skridt at gennemføre hver af disse algoritmer. 44 00:02:11,980 --> 00:02:15,110 >> Nu i slutningen af ​​klassen tilbagekaldelse, vi sammenlignet boble sortere 45 00:02:15,110 --> 00:02:19,390 mod valg Sorter mod en anden at vi kaldte mergesort dengang, 46 00:02:19,390 --> 00:02:22,120 og jeg foreslår, at det tager fordel af en lektion fra uge 47 00:02:22,120 --> 00:02:24,060 nul, dividere og erobre. 48 00:02:24,060 --> 00:02:28,810 Og en eller anden måde at opnå en form for logaritmisk køretid sidste ende, 49 00:02:28,810 --> 00:02:31,024 i stedet for noget det er rent kvadratisk. 50 00:02:31,024 --> 00:02:33,440 Og det er ikke helt logaritmisk, det er lidt mere end det. 51 00:02:33,440 --> 00:02:36,520 Men hvis du husker fra klassen, Det var meget, meget hurtigere. 52 00:02:36,520 --> 00:02:38,210 Lad os tage et kig på, hvor vi slap. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble sortere versus udvælgelse sortere versus mergesort. 55 00:02:45,370 --> 00:02:47,700 Nu er de alle kører i teori, på samme tid. 56 00:02:47,700 --> 00:02:50,510 CPU kører ved samme hastighed. 57 00:02:50,510 --> 00:02:54,990 Men du kan føle, hvordan kedelige dette er meget hurtigt ved at blive, 58 00:02:54,990 --> 00:02:58,790 og hvor hurtigt, når vi injicere lidt af uge nul algoritmer, 59 00:02:58,790 --> 00:03:00,080 kan vi fremskynde tingene op. 60 00:03:00,080 --> 00:03:01,630 >> Så mark slags ser fantastisk. 61 00:03:01,630 --> 00:03:05,220 Hvordan kan vi udnytte det, for at sortere tal hurtigere. 62 00:03:05,220 --> 00:03:07,140 Jamen så lad os tænke tilbage en ingrediens, som vi 63 00:03:07,140 --> 00:03:10,380 havde igen i uge nul, nemlig søger efter en person i en telefonbog, 64 00:03:10,380 --> 00:03:12,380 og minde om, at pseudokode, som vi foreslog, 65 00:03:12,380 --> 00:03:14,560 via hvilken vi kan finde en som Mike Smith, 66 00:03:14,560 --> 00:03:16,310 kiggede lidt noget som dette. 67 00:03:16,310 --> 00:03:20,820 >> Nu tage et kig i særdeleshed på linje 7 og 8, og 10 og 11, 68 00:03:20,820 --> 00:03:25,240 som inducerer, at loop, hvorved vi holdt gå tilbage til linje 3 igen og igen, 69 00:03:25,240 --> 00:03:26,520 og igen. 70 00:03:26,520 --> 00:03:31,790 Men det viser sig, at vi kan se denne algoritme, her i pseudokode, 71 00:03:31,790 --> 00:03:33,620 lidt mere holistisk. 72 00:03:33,620 --> 00:03:35,960 Faktisk hvad jeg søger på her på skærmen, 73 00:03:35,960 --> 00:03:41,180 er en algoritme til at søge efter Mike Smith blandt nogle sæt sider. 74 00:03:41,180 --> 00:03:45,520 Og ja, kunne vi forenkle denne algoritme i disse linjer 7 og 8, 75 00:03:45,520 --> 00:03:49,860 og 10 og 11 til blot sige dette, som jeg har præsenteret her i gult. 76 00:03:49,860 --> 00:03:52,210 Med andre ord, hvis Mike Smith er tidligere i bogen, 77 00:03:52,210 --> 00:03:55,004 Vi behøver ikke at angive trin for skridt nu, hvordan at gå finde ham. 78 00:03:55,004 --> 00:03:56,920 Vi behøver ikke at angive at gå tilbage til linje 3, 79 00:03:56,920 --> 00:03:58,960 hvorfor vi ikke bare stedet, sige, mere generelt, 80 00:03:58,960 --> 00:04:01,500 søge efter Mike i venstre halvdel af bogen. 81 00:04:01,500 --> 00:04:03,960 >> Omvendt, hvis Mike er faktisk senere i bogen, 82 00:04:03,960 --> 00:04:07,540 hvorfor vi ikke bare citere citat slut søgning til Mike i højre halvdel af bogen. 83 00:04:07,540 --> 00:04:11,030 Med andre ord, hvorfor vi ikke bare slags punt til os selv at sige, 84 00:04:11,030 --> 00:04:13,130 søge efter Mike i denne delmængde af bogen, 85 00:04:13,130 --> 00:04:16,279 og overlade det til vores eksisterende algoritme til at fortælle os 86 00:04:16,279 --> 00:04:18,750 hvordan du søger efter Mike i at venstre halvdel af bogen. 87 00:04:18,750 --> 00:04:20,750 Med andre ord, vores algoritme fungerer uanset om det er 88 00:04:20,750 --> 00:04:24,670 en telefonbog af denne tykkelse, af denne tykkelse eller nogen som helst tykkelse. 89 00:04:24,670 --> 00:04:27,826 Så vi kan rekursivt definerer denne algoritme. 90 00:04:27,826 --> 00:04:29,950 Med andre ord, om skærmen her, er en algoritme 91 00:04:29,950 --> 00:04:33,130 til at søge efter Mike Smith blandt siderne i en telefonbog. 92 00:04:33,130 --> 00:04:37,410 Så på linje 7 og 10, lad os bare sige præcis det. 93 00:04:37,410 --> 00:04:40,250 Og jeg bruger dette udtryk et øjeblik siden, og faktisk, rekursion 94 00:04:40,250 --> 00:04:42,450 er buzzword for nu, og det er denne proces 95 00:04:42,450 --> 00:04:47,210 for at gøre noget cyklisk ved en eller anden måde bruge kode, som du allerede har, 96 00:04:47,210 --> 00:04:49,722 og kalder det igen, og igen og igen. 97 00:04:49,722 --> 00:04:51,930 Nu det vil være vigtigt at vi på en måde bunden 98 00:04:51,930 --> 00:04:53,821 ud, og ikke gør det uendelig lang. 99 00:04:53,821 --> 00:04:56,070 Ellers vil vi har faktisk en uendelig løkke. 100 00:04:56,070 --> 00:04:59,810 Men lad os se, om vi kan låne denne idé af en rekursion, at gøre noget igen 101 00:04:59,810 --> 00:05:03,600 og igen og igen, at løse den sortering problemet via merge 102 00:05:03,600 --> 00:05:05,900 Sorter, desto mere effektivt. 103 00:05:05,900 --> 00:05:06,970 >> Så jeg giver dig mergesort. 104 00:05:06,970 --> 00:05:07,920 Lad os tage et kig. 105 00:05:07,920 --> 00:05:10,850 Så her er pseudokode, med som vi kunne gennemføre sortering, 106 00:05:10,850 --> 00:05:12,640 ved hjælp af denne algoritme kaldes mergesort. 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å input af n elementer, med andre ord, hvis du er 109 00:05:15,940 --> 00:05:18,830 givet n elementer og tal, og breve eller hvad input er, 110 00:05:18,830 --> 00:05:22,430 hvis du er givet n elementer, hvis n er mindre end 2, blot tilbage. 111 00:05:22,430 --> 00:05:22,930 Højre? 112 00:05:22,930 --> 00:05:26,430 For hvis n er mindre end 2, at betyder, at min liste over elementer 113 00:05:26,430 --> 00:05:30,446 enten størrelse 0 eller 1, og i begge disse trivielle tilfælde, 114 00:05:30,446 --> 00:05:31,570 listen er allerede sorteret. 115 00:05:31,570 --> 00:05:32,810 Hvis der ikke er nogen liste, er det ordnet. 116 00:05:32,810 --> 00:05:35,185 Og hvis der er en liste over længde 1, er det naturligvis sorteres. 117 00:05:35,185 --> 00:05:38,280 Så algoritmen kun behøver at virkelig gøre noget interessant, 118 00:05:38,280 --> 00:05:40,870 hvis vi har to eller flere elementer givet til os. 119 00:05:40,870 --> 00:05:42,440 Så lad os se på det magiske dengang. 120 00:05:42,440 --> 00:05:47,500 Else sortere den venstre halvdel af elementerne, derefter sortere højre halvdel af elementer, 121 00:05:47,500 --> 00:05:49,640 derefter flette de sorterede halvdele. 122 00:05:49,640 --> 00:05:52,440 Og hvad er form for sindet bøjning her, er, at jeg ikke rigtig 123 00:05:52,440 --> 00:05:56,190 synes at have fortalt dig noget endnu, ikke? 124 00:05:56,190 --> 00:05:59,560 Alt, hvad jeg har sagt er, givet en liste over n elementer, sortere den venstre halvdel, 125 00:05:59,560 --> 00:06:01,800 derefter den højre halvdel, derefter fusionere de sorterede halvdele, 126 00:06:01,800 --> 00:06:03,840 men hvor er den egentlige hemmelige sauce? 127 00:06:03,840 --> 00:06:05,260 Hvor er den algoritme? 128 00:06:05,260 --> 00:06:09,150 Jamen det viser sig, at de to linjer første, sortere venstre halvdel af elementer, 129 00:06:09,150 --> 00:06:13,970 og sortering højre halvdel af elementer, er rekursive kald, så at sige. 130 00:06:13,970 --> 00:06:16,120 >> Efter alt, på dette tidspunkt, har jeg 131 00:06:16,120 --> 00:06:18,950 en algoritme med at sortere en hel masse elementer? 132 00:06:18,950 --> 00:06:19,450 Ja. 133 00:06:19,450 --> 00:06:20,620 Det er lige her. 134 00:06:20,620 --> 00:06:25,180 Det er lige her på skærmen, og så jeg kan bruge den samme sæt af trin 135 00:06:25,180 --> 00:06:28,500 at sortere venstre halvdel, som jeg kan højre halvdel. 136 00:06:28,500 --> 00:06:30,420 Og ja, igen og igen. 137 00:06:30,420 --> 00:06:34,210 Så en eller anden måde, og vi vil snart se dette, den magiske af mergesort 138 00:06:34,210 --> 00:06:37,967 er indlejret i det meget endelige linje, sammenlægning af de sorterede halvdele. 139 00:06:37,967 --> 00:06:39,300 Og det forekommer temmelig intuitiv. 140 00:06:39,300 --> 00:06:41,050 Du tager to halvdele, og du, en eller anden måde, flette dem sammen, 141 00:06:41,050 --> 00:06:43,260 og vi vil se denne konkret i et øjeblik. 142 00:06:43,260 --> 00:06:45,080 >> Men dette er en komplet algoritme. 143 00:06:45,080 --> 00:06:46,640 Og lad os se præcis hvorfor. 144 00:06:46,640 --> 00:06:50,912 Nå antage, at vi er givet disse samme otte elementer her på skærmen, en 145 00:06:50,912 --> 00:06:53,120 gennem otte, men de er i tilsyneladende tilfældig rækkefølge. 146 00:06:53,120 --> 00:06:55,320 Og målet ved hånden er at sortere disse elementer. 147 00:06:55,320 --> 00:06:58,280 Godt, hvordan kan jeg gå om gør det ved hjælp igen, 148 00:06:58,280 --> 00:07:00,407 mergesort, som pr denne pseudokode? 149 00:07:00,407 --> 00:07:02,740 Og igen, ingrain dette i dit sind, for bare et øjeblik. 150 00:07:02,740 --> 00:07:05,270 Det første tilfælde er temmelig trivielt, hvis det er mindre end 2, 151 00:07:05,270 --> 00:07:07,060 bare tilbage, er der ingen arbejde der skal gøres. 152 00:07:07,060 --> 00:07:09,290 Så virkelig er der bare tre skridt til virkelig huske. 153 00:07:09,290 --> 00:07:11,081 Igen og igen, jeg er vil ønsker at have 154 00:07:11,081 --> 00:07:13,980 at sortere venstre halvdel, sortere højre halvdel, 155 00:07:13,980 --> 00:07:15,890 og derefter en gang deres to halvdele er sorteret, 156 00:07:15,890 --> 00:07:18,710 Jeg vil flette dem sammen i en sorteret liste. 157 00:07:18,710 --> 00:07:19,940 Så holder det i tankerne. 158 00:07:19,940 --> 00:07:21,310 >> Så her er den oprindelige liste. 159 00:07:21,310 --> 00:07:23,510 Lad os behandle dette som et array, som vi begyndte at 160 00:07:23,510 --> 00:07:25,800 i uge to, som er en sammenhængende blok hukommelse. 161 00:07:25,800 --> 00:07:28,480 I dette tilfælde indeholder otte numre, ryg mod ryg mod ryg. 162 00:07:28,480 --> 00:07:30,700 Og lad os nu anvende mergesort. 163 00:07:30,700 --> 00:07:33,300 Så jeg først vil sortere den venstre halvdel af denne liste, 164 00:07:33,300 --> 00:07:37,370 og lad os derfor fokusere på 4, 8, 6 og 2. 165 00:07:37,370 --> 00:07:41,000 >> Nu hvordan kan jeg gå om sortering en liste over størrelse 4? 166 00:07:41,000 --> 00:07:45,990 Jeg må godt nu overveje sortering venstre for den venstre halvdel. 167 00:07:45,990 --> 00:07:47,720 Igen, lad os spole tilbage for et øjeblik. 168 00:07:47,720 --> 00:07:51,010 Hvis pseudokode er det, og jeg fik otte elementer, 169 00:07:51,010 --> 00:07:53,230 8 er klart større end eller lig med 2. 170 00:07:53,230 --> 00:07:54,980 Så med det første tilfælde ikke finder anvendelse. 171 00:07:54,980 --> 00:07:58,120 Så for at sortere otte elementer, jeg først sortere den venstre halvdel af elementer, 172 00:07:58,120 --> 00:08:01,930 så jeg sortere den højre halvdel, så jeg flette de to sorterede halvdele, hver med størrelsen 4. 173 00:08:01,930 --> 00:08:02,470 OK. 174 00:08:02,470 --> 00:08:07,480 >> Men hvis du lige har fortalt mig, sortere venstre halvdel, som nu er i størrelse 4, 175 00:08:07,480 --> 00:08:09,350 hvordan kan jeg sortere venstre halvleg? 176 00:08:09,350 --> 00:08:11,430 Tja, hvis jeg har en input af fire elementer, 177 00:08:11,430 --> 00:08:14,590 Jeg først sortere venstre to, så den højre to, 178 00:08:14,590 --> 00:08:16,210 og så vil jeg flette dem sammen. 179 00:08:16,210 --> 00:08:18,700 Så igen, bliver det en smule af et sind bøjning spil her, 180 00:08:18,700 --> 00:08:21,450 fordi du, slags, er nødt til at huske, hvor du er i historien, 181 00:08:21,450 --> 00:08:23,620 men i slutningen af ​​dagen, givet nogen række elementer, 182 00:08:23,620 --> 00:08:25,620 du først ønsker at sortere venstre halvdel, derefter den højre halvdel, 183 00:08:25,620 --> 00:08:26,661 derefter flette dem sammen. 184 00:08:26,661 --> 00:08:28,630 Lad os begynde at gøre netop dette. 185 00:08:28,630 --> 00:08:30,170 Her er input af otte elementer. 186 00:08:30,170 --> 00:08:31,910 Nu er vi kigger på den venstre halvdel her. 187 00:08:31,910 --> 00:08:33,720 Hvordan kan jeg sortere fire elementer? 188 00:08:33,720 --> 00:08:35,610 Jamen jeg først sortere venstre halvdel. 189 00:08:35,610 --> 00:08:37,720 Nu hvordan kan jeg sortere venstre halvleg? 190 00:08:37,720 --> 00:08:39,419 Jamen jeg har fået to elementer. 191 00:08:39,419 --> 00:08:41,240 Så lad os sortere disse to elementer. 192 00:08:41,240 --> 00:08:44,540 2 er større end eller svarende til 2, selvfølgelig. 193 00:08:44,540 --> 00:08:46,170 Så det første tilfælde ikke finder anvendelse. 194 00:08:46,170 --> 00:08:49,010 >> Så nu har jeg til at sortere venstre halvdelen af ​​disse to elementer. 195 00:08:49,010 --> 00:08:50,870 Den venstre halvdel, selvfølgelig, er kun 4. 196 00:08:50,870 --> 00:08:54,020 Så hvordan får jeg sorterer en liste med et element? 197 00:08:54,020 --> 00:08:57,960 Nå nu, at særlige base case op toppen, så at sige, finder anvendelse. 198 00:08:57,960 --> 00:09:01,470 1 er mindre end 2, og min Listen er faktisk størrelse 1. 199 00:09:01,470 --> 00:09:02,747 Så jeg bare vende tilbage. 200 00:09:02,747 --> 00:09:03,580 Jeg kan ikke gøre noget. 201 00:09:03,580 --> 00:09:06,770 Og ja, se på, hvad jeg har gjort, er 4 allerede sorteret. 202 00:09:06,770 --> 00:09:09,220 Ligesom jeg er allerede delvis succes her. 203 00:09:09,220 --> 00:09:11,750 >> Nu, synes slags dum at kræve, men det er sandt. 204 00:09:11,750 --> 00:09:13,700 4 er en liste over størrelse 1. 205 00:09:13,700 --> 00:09:15,090 Det er allerede ordnet. 206 00:09:15,090 --> 00:09:16,270 Det er den venstre halvdel. 207 00:09:16,270 --> 00:09:18,010 Nu jeg sortere højre halvdel. 208 00:09:18,010 --> 00:09:22,310 Mit input er et element, 8 Ligeledes allerede sorteret. 209 00:09:22,310 --> 00:09:25,170 Dum, også, men igen, dette grundlæggende princip 210 00:09:25,170 --> 00:09:28,310 kommer til at give os mulighed for nu at bygge øverst på denne succes. 211 00:09:28,310 --> 00:09:32,260 4 sorteret, 8 sorteres, nu hvad var det sidste skridt? 212 00:09:32,260 --> 00:09:35,330 Så det tredje og sidste trin, som helst gang du sortere en liste, tilbagekaldelse, 213 00:09:35,330 --> 00:09:38,310 var at fusionere de to halvdele, venstre og højre. 214 00:09:38,310 --> 00:09:39,900 Så lad os gøre netop dette. 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øjre halvdel er 8. 217 00:09:43,310 --> 00:09:44,100 >> Så lad os gøre det. 218 00:09:44,100 --> 00:09:46,410 Først vil jeg tildele nogle ekstra hukommelse, 219 00:09:46,410 --> 00:09:48,680 at jeg vil repræsentere her, som blot en sekundær matrix, 220 00:09:48,680 --> 00:09:49,660 der er stor nok til at passe dette. 221 00:09:49,660 --> 00:09:52,243 Men du kan forestille dig at udvide dette rektangel hele længden, 222 00:09:52,243 --> 00:09:53,290 hvis vi har brug for mere senere. 223 00:09:53,290 --> 00:09:58,440 Hvordan tager 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 temmelig simpel. 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 at sortere venstre halvdel, derefter den højre halvdel, 227 00:10:07,130 --> 00:10:09,900 og derefter fusionere de to halvdele sammen i sorteret 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 at gøre fremskridt, selv selvom jeg ikke har gjort noget egentlige arbejde. 230 00:10:15,810 --> 00:10:17,800 Men huske, hvor vi er i historien. 231 00:10:17,800 --> 00:10:19,360 Vi oprindeligt tog otte elementer. 232 00:10:19,360 --> 00:10:21,480 Vi sorteret den venstre halvdel, hvilket er 4. 233 00:10:21,480 --> 00:10:24,450 Derefter sorteres vi venstre halvdel af den venstre halvdel, som var 2. 234 00:10:24,450 --> 00:10:25,270 Og her går vi. 235 00:10:25,270 --> 00:10:26,920 Vi er færdig med dette skridt. 236 00:10:26,920 --> 00:10:29,930 >> Så hvis vi har ordnet det venstre halvdel af 2, nu er vi 237 00:10:29,930 --> 00:10:32,130 nødt til at sortere højre halvdel af 2. 238 00:10:32,130 --> 00:10:35,710 Så højre halvdel af 2 disse to værdier her, 6 og 2. 239 00:10:35,710 --> 00:10:40,620 Så lad os nu tage et input af størrelse 2, og sortere den venstre halvdel, og derefter 240 00:10:40,620 --> 00:10:42,610 den højre halvdel, og derefter flette dem sammen. 241 00:10:42,610 --> 00:10:45,722 Godt, hvordan kan jeg sorterer en liste over størrelse 1, indeholder kun nummer 6? 242 00:10:45,722 --> 00:10:46,430 Jeg er allerede gjort. 243 00:10:46,430 --> 00:10:48,680 Denne liste over størrelse 1 sorteres. 244 00:10:48,680 --> 00:10:52,140 >> Hvordan kan jeg sortere en anden liste over størrelse 1, den såkaldte højre halvdel. 245 00:10:52,140 --> 00:10:54,690 Godt det også allerede er sorteret. 246 00:10:54,690 --> 00:10:56,190 Det nummer 2 er alene. 247 00:10:56,190 --> 00:11:00,160 Så nu har jeg to halvdele, venstre og ret, jeg har brug for at flette dem sammen. 248 00:11:00,160 --> 00:11:01,800 Lad mig give mig nogle ekstra plads. 249 00:11:01,800 --> 00:11:05,580 Og sætte 2 derinde, derefter 6 derinde, hvorved 250 00:11:05,580 --> 00:11:10,740 sortering denne liste, venstre og højre, og sammenlægning det sammen, i sidste ende. 251 00:11:10,740 --> 00:11:12,160 Så jeg er i lidt bedre form. 252 00:11:12,160 --> 00:11:16,250 Jeg er ikke færdig, 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 nu to lister med størrelse 2, at har begge henholdsvis blevet sorteret. 254 00:11:20,640 --> 00:11:24,580 Så nu, hvis du spole tilbage i dit sind s øjet, hvor har der forlader os? 255 00:11:24,580 --> 00:11:28,520 Jeg startede med otte elementer, så jeg skåret det ned til den venstre halvdel af 4, 256 00:11:28,520 --> 00:11:31,386 derefter den venstre halvdel af 2, og derefter den højre halvdel af 2, 257 00:11:31,386 --> 00:11:34,510 Jeg er færdig, derfor, sortering venstre halvdelen af ​​2 og den højre halvdel af 2, 258 00:11:34,510 --> 00:11:37,800 så hvad er den tredje og sidste trin her? 259 00:11:37,800 --> 00:11:41,290 Jeg er nødt til at smelte sammen to lister med størrelse 2. 260 00:11:41,290 --> 00:11:42,040 Så lad os gå videre. 261 00:11:42,040 --> 00:11:43,940 Og på skærmen her, giver mig nogle ekstra hukommelse, 262 00:11:43,940 --> 00:11:47,170 dog teknisk set, mærke til, at jeg har fik en hel masse tom plads op øverst 263 00:11:47,170 --> 00:11:47,670 der. 264 00:11:47,670 --> 00:11:50,044 Hvis jeg ønsker at være særligt effektiv plads klogt, 265 00:11:50,044 --> 00:11:52,960 Jeg kunne bare begynde at bevæge elementerne frem og tilbage, top og bund. 266 00:11:52,960 --> 00:11:55,460 Men bare for visuel klarhed, Jeg har tænkt mig at sætte den ned under, 267 00:11:55,460 --> 00:11:56,800 at holde tingene pæn og ren. 268 00:11:56,800 --> 00:11:58,150 >> Så jeg har fået to lister med størrelse 2. 269 00:11:58,150 --> 00:11:59,770 Den første liste har 4 og 8. 270 00:11:59,770 --> 00:12:01,500 Den anden liste har 2 og 6. 271 00:12:01,500 --> 00:12:03,950 Lad os flette dem sammen i sorteret orden. 272 00:12:03,950 --> 00:12:09,910 2 naturligvis kommer først, derefter 4 og derefter 6, derefter 8. 273 00:12:09,910 --> 00:12:12,560 Og nu synes vi at være at få et sted interessant. 274 00:12:12,560 --> 00:12:15,720 Nu har jeg ordnet halvdelen af liste, og tilfældigvis er det 275 00:12:15,720 --> 00:12:18,650 alle de lige numre, men er, ja, bare en tilfældighed. 276 00:12:18,650 --> 00:12:22,220 Og jeg har nu sorteres venstre halvdelen, således at det er 2, 4, 6 og 8. 277 00:12:22,220 --> 00:12:23,430 Intet er ude af drift. 278 00:12:23,430 --> 00:12:24,620 Der føles som fremskridt. 279 00:12:24,620 --> 00:12:26,650 >> Nu føles det som jeg har talt evigt nu, 280 00:12:26,650 --> 00:12:29,850 så hvad er stadig uvist, om dette algoritme er faktisk mere effektiv. 281 00:12:29,850 --> 00:12:31,766 Men vi går igennem det super metodisk. 282 00:12:31,766 --> 00:12:34,060 En computer, naturligvis, ville gøre det sådan. 283 00:12:34,060 --> 00:12:34,840 Så hvor er vi? 284 00:12:34,840 --> 00:12:36,180 Vi startede med otte elementer. 285 00:12:36,180 --> 00:12:37,840 Jeg sorteret den venstre halvdel af 4. 286 00:12:37,840 --> 00:12:39,290 Jeg synes at ske med det. 287 00:12:39,290 --> 00:12:42,535 Så nu det næste skridt er at sortere højre halvdel af 4. 288 00:12:42,535 --> 00:12:44,410 Og denne del, vi kan gå gennem lidt mere 289 00:12:44,410 --> 00:12:47,140 hurtigt, selvom du er velkommen til at spole tilbage eller pause, bare 290 00:12:47,140 --> 00:12:49,910 tænke igennem det på dit eget tempo, men hvad 291 00:12:49,910 --> 00:12:53,290 Vi har nu en mulighed for at gøre nøjagtig samme algoritme på fire 292 00:12:53,290 --> 00:12:54,380 forskellige numre. 293 00:12:54,380 --> 00:12:57,740 >> Så lad os gå videre og fokusere på den højre halvdel, som vi er her. 294 00:12:57,740 --> 00:13:01,260 Den venstre halvdel af denne højre halvdel, og nu 295 00:13:01,260 --> 00:13:04,560 venstre halvdel af den venstre halvdelen af ​​denne højre halvdel, 296 00:13:04,560 --> 00:13:08,030 og hvordan kan jeg sorterer en liste over størrelse 1 kun indeholder nummer 1? 297 00:13:08,030 --> 00:13:09,030 Det er allerede gjort. 298 00:13:09,030 --> 00:13:11,830 Hvordan gør jeg det samme for en liste størrelse 1 indeholdende kun 7? 299 00:13:11,830 --> 00:13:12,840 Det er allerede gjort. 300 00:13:12,840 --> 00:13:16,790 Trin tre for denne halve derefter er at fusionere disse to elementer 301 00:13:16,790 --> 00:13:20,889 i en ny liste over størrelsen 2, 1 og 7. 302 00:13:20,889 --> 00:13:23,180 Synes ikke at have gjort alt at meget interessant arbejde. 303 00:13:23,180 --> 00:13:24,346 Lad os se, hvad der sker næste. 304 00:13:24,346 --> 00:13:29,210 Jeg har lige ordnet den venstre halvdel af højre halvdel af min oprindelige indgang. 305 00:13:29,210 --> 00:13:32,360 Lad os nu sortere ret halvdelen, der indeholder 5 og 3. 306 00:13:32,360 --> 00:13:35,740 Lad os igen se på venstre halvdelen, sorteret, højre halvdel, sorteret, 307 00:13:35,740 --> 00:13:39,120 og flette de to sammen, ind i nogle ekstra plads, 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å nu, har vi sorteret de venstre halvdel af den højre halvdel 310 00:13:46,190 --> 00:13:49,420 af det oprindelige problem, og den højre halvdel af den højre halvdel 311 00:13:49,420 --> 00:13:50,800 af det oprindelige problem. 312 00:13:50,800 --> 00:13:52,480 Hvad er den tredje og sidste trin? 313 00:13:52,480 --> 00:13:54,854 Nå at fusionere de to halvdele sammen. 314 00:13:54,854 --> 00:13:57,020 Så lad mig få mig nogle ekstra plads, men igen, I 315 00:13:57,020 --> 00:13:58,699 kunne være ved hjælp af denne overskydende plads op øverst. 316 00:13:58,699 --> 00:14:00,490 Men vi kommer til at holde det nemt visuelt. 317 00:14:00,490 --> 00:14:07,070 Lad mig fusionere i nu 1, og derefter 3 og derefter 5, og derefter 7. 318 00:14:07,070 --> 00:14:10,740 Derved forlader mig nu med højre halvdel af det oprindelige problem 319 00:14:10,740 --> 00:14:12,840 der er perfekt ordnet. 320 00:14:12,840 --> 00:14:13,662 >> Så hvad der er tilbage? 321 00:14:13,662 --> 00:14:16,120 Jeg føler, at jeg holder siger samme ting igen og igen, 322 00:14:16,120 --> 00:14:18,700 men det er reflekterende af faktum, at vi bruger rekursion. 323 00:14:18,700 --> 00:14:21,050 Processen med at bruge en algoritme igen og igen, 324 00:14:21,050 --> 00:14:23,940 på mindre delmængder af det oprindelige problem. 325 00:14:23,940 --> 00:14:27,580 Så jeg har nu en venstre sorteres halvdelen af ​​det oprindelige problem. 326 00:14:27,580 --> 00:14:30,847 Jeg har ret sorterede halvdel af det oprindelige problem. 327 00:14:30,847 --> 00:14:32,180 Hvad er den tredje og sidste skridt? 328 00:14:32,180 --> 00:14:33,590 Åh, det er fletning. 329 00:14:33,590 --> 00:14:34,480 Så lad os gøre det. 330 00:14:34,480 --> 00:14:36,420 Lad os afsætte nogle ekstra hukommelse, men min Gud, vi 331 00:14:36,420 --> 00:14:37,503 kunne sætte det overalt nu. 332 00:14:37,503 --> 00:14:40,356 Vi har så meget plads til rådighed for os, men vi vil holde det enkelt. 333 00:14:40,356 --> 00:14:42,730 I stedet for at gå tilbage og frem med vores oprindelige hukommelse, 334 00:14:42,730 --> 00:14:44,480 lad os bare gøre det visuelt hernede nedenfor, 335 00:14:44,480 --> 00:14:47,240 at slutte op sammenlægning af venstre halvdel og højre halvdel. 336 00:14:47,240 --> 00:14:49,279 >> Så ved at fusionere, hvad skal jeg gøre? 337 00:14:49,279 --> 00:14:50,820 Jeg ønsker at tage de elementer i orden. 338 00:14:50,820 --> 00:14:53,230 Så ser på den venstre halvdel, Jeg ser det første tal er 2. 339 00:14:53,230 --> 00:14:55,230 Jeg ser på den højre halvdel, Jeg ser det første nummer 340 00:14:55,230 --> 00:14:58,290 er 1, så selvfølgelig som nummer ønsker jeg at plukke ud, 341 00:14:58,290 --> 00:15:00,430 og sætte først i min endelige liste? 342 00:15:00,430 --> 00:15:01,449 Selvfølgelig 1. 343 00:15:01,449 --> 00:15:02,990 Nu vil jeg bede om, at samme spørgsmål. 344 00:15:02,990 --> 00:15:05,040 På venstre halvdel, jeg har stadig fik nummer 2. 345 00:15:05,040 --> 00:15:07,490 På den højre halvdel, Jeg har fået nummer 3. 346 00:15:07,490 --> 00:15:08,930 Hvilken en skal jeg vælge? 347 00:15:08,930 --> 00:15:11,760 Selvfølgelig nummer 2 og nu mærke til de kandidater, 348 00:15:11,760 --> 00:15:13,620 er 4 til venstre, 3 til højre. 349 00:15:13,620 --> 00:15:15,020 Lad os naturligvis vælge 3. 350 00:15:15,020 --> 00:15:18,020 Nu kandidaterne er 4 på venstre, 5 til højre. 351 00:15:18,020 --> 00:15:19,460 Vi naturligvis vælge 4. 352 00:15:19,460 --> 00:15:21,240 6 til venstre, 5 til højre. 353 00:15:21,240 --> 00:15:22,730 Vi naturligvis vælge 5. 354 00:15:22,730 --> 00:15:25,020 6 til venstre, 7 til højre. 355 00:15:25,020 --> 00:15:29,320 Vi vælger 6, og så er vi vælge 7, og vælg derefter vi 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Er således et stort antal ord senere, vi har sorteret denne liste over otte elementer 358 00:15:34,370 --> 00:15:38,450 i en liste med en gennem otte, der er stigende med hvert trin, 359 00:15:38,450 --> 00:15:40,850 men hvor meget tid gjorde det tage os at gøre det. 360 00:15:40,850 --> 00:15:43,190 Jamen jeg har med vilje lagte ting ud billedligt 361 00:15:43,190 --> 00:15:46,330 her, så vi kan slags se eller værdsætter division 362 00:15:46,330 --> 00:15:49,060 i erobre, der er blevet sker. 363 00:15:49,060 --> 00:15:52,830 >> Faktisk, hvis man ser tilbage på kølvandet, Jeg har efterladt alle disse stiplede linjer 364 00:15:52,830 --> 00:15:55,660 i pladsholdere, kan du, slags, se i omvendt rækkefølge, 365 00:15:55,660 --> 00:15:58,800 hvis du slags se tilbage i historie nu, min oprindelige liste 366 00:15:58,800 --> 00:16:00,250 er naturligvis af størrelsen 8. 367 00:16:00,250 --> 00:16:03,480 Og så tidligere, var jeg beskæftiger sig med to lister med størrelse 4, 368 00:16:03,480 --> 00:16:08,400 og derefter fire lister over størrelse 2, og derefter otte lister over størrelse 1. 369 00:16:08,400 --> 00:16:10,151 >> Så hvad gør dette, slags, minde dig om? 370 00:16:10,151 --> 00:16:11,858 Nå, ja, nogen af de algoritmer, vi har 371 00:16:11,858 --> 00:16:14,430 så på hidtil hvor vi kløft, og dividere, og dividere, 372 00:16:14,430 --> 00:16:19,500 holde have tingene igen, og igen, resulterer i denne generelle idé. 373 00:16:19,500 --> 00:16:23,100 Og så er der noget logaritmisk foregår her. 374 00:16:23,100 --> 00:16:26,790 Og det er ikke helt log over n, men der er en logaritmisk komponent 375 00:16:26,790 --> 00:16:28,280 til det, vi lige har gjort. 376 00:16:28,280 --> 00:16:31,570 >> Lad os nu overveje, hvordan der rent faktisk er. 377 00:16:31,570 --> 00:16:34,481 Så log n, igen var en stor køretid, 378 00:16:34,481 --> 00:16:36,980 når vi gjorde noget lignende binær søgning, som vi nu kalder det, 379 00:16:36,980 --> 00:16:40,090 kløften og erobre strategi via som vi fandt Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Nu teknisk. 381 00:16:41,020 --> 00:16:43,640 Det er totalslogaritmen 2 n, selv men i de fleste matematiske klasser, 382 00:16:43,640 --> 00:16:45,770 10 er normalt i bunden, som du antager. 383 00:16:45,770 --> 00:16:48,940 Men dataloger næsten altid tænker og taler om bunden 2, 384 00:16:48,940 --> 00:16:52,569 så vi generelt bare sige log over n, i stedet for log basis 2 af n, 385 00:16:52,569 --> 00:16:55,110 men de er nøjagtigt én og samme i verden af ​​computeren 386 00:16:55,110 --> 00:16:57,234 videnskab, og som en sidebemærkning, der er en konstant faktor 387 00:16:57,234 --> 00:17:01,070 Forskellen mellem de to, så det er omstridt alligevel, for mere formelle grunde. 388 00:17:01,070 --> 00:17:04,520 >> Men for nu, hvad vi bekymrer om, er dette eksempel. 389 00:17:04,520 --> 00:17:08,520 Så lad os ikke bevise ved eksempel, men på det mindste bruge et eksempel på tallene 390 00:17:08,520 --> 00:17:10,730 ved hånden som en tilregnelighed check, hvis du vil. 391 00:17:10,730 --> 00:17:14,510 Så tidligere formlen var totalslogaritmen 2 af n, men hvad der er n i dette tilfælde. 392 00:17:14,510 --> 00:17:18,526 Jeg havde n originale numre, eller 8 af oprindelige antal specifikt. 393 00:17:18,526 --> 00:17:20,359 Nu er det blevet lidt stykke tid, men jeg er temmelig 394 00:17:20,359 --> 00:17:25,300 sikker på, at bunden 2 log af værdien 8 er 3, 395 00:17:25,300 --> 00:17:29,630 og ja, hvad er rart om der er at 3 er nøjagtigt det antal gange 396 00:17:29,630 --> 00:17:33,320 at du kan opdele en liste af længde 8 igen og igen, 397 00:17:33,320 --> 00:17:36,160 og igen, indtil du er tilbage med lister over bare størrelse 1. 398 00:17:36,160 --> 00:17:36,660 Højre? 399 00:17:36,660 --> 00:17:40,790 8 går til 4, går til 2, går til 1, og det er 400 00:17:40,790 --> 00:17:43,470 reflekterende af netop dette billede, vi havde bare et øjeblik siden. 401 00:17:43,470 --> 00:17:47,160 Så lidt fornuft tjek på, hvor logaritmen er faktisk involveret. 402 00:17:47,160 --> 00:17:50,180 >> Så nu, hvad der ellers er involveret her? n. 403 00:17:50,180 --> 00:17:53,440 Så mærke til, at hver tid jeg opdele listen, 404 00:17:53,440 --> 00:17:58,260 omend i omvendt rækkefølge i historien her, var jeg stadig gør n ting. 405 00:17:58,260 --> 00:18:02,320 Det fusionerende trin krævede, at Jeg rører hver et af de numre, 406 00:18:02,320 --> 00:18:05,060 for at skubbe den ind dens passende placering. 407 00:18:05,060 --> 00:18:10,760 Så selvom højden af ​​denne diagrammet er af størrelsen log n af n eller 3, 408 00:18:10,760 --> 00:18:13,860 specifikt, med andre ord, Jeg gjorde tre divisioner her. 409 00:18:13,860 --> 00:18:18,800 Hvor meget arbejde gjorde jeg vandret langs dette skema hver gang? 410 00:18:18,800 --> 00:18:21,110 >> Nå, jeg gjorde n trin arbejde, fordi hvis jeg har 411 00:18:21,110 --> 00:18:24,080 fik fire elementer og fire elementer, og jeg har brug for at flette dem sammen. 412 00:18:24,080 --> 00:18:26,040 Jeg har brug for at gå gennem disse fire og disse fire, 413 00:18:26,040 --> 00:18:28,123 i sidste ende til at flette dem tilbage til otte elementer. 414 00:18:28,123 --> 00:18:32,182 Hvis omvendt I got otte fingre herovre, hvilket jeg ikke gør, og otte 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Hvis jeg har fik fire fingre herovre, 416 00:18:34,390 --> 00:18:37,380 som jeg gør, fire fingre herovre, som jeg gør, 417 00:18:37,380 --> 00:18:40,590 så det er det samme eksempel som før, hvis jeg gør 418 00:18:40,590 --> 00:18:44,010 har otte fingre men i alt, som jeg kan, slags, gør. 419 00:18:44,010 --> 00:18:47,950 Jeg kan netop gøre her, så jeg kan helt sikkert 420 00:18:47,950 --> 00:18:50,370 flette alle disse lister størrelse 1 sammen. 421 00:18:50,370 --> 00:18:54,050 Men jeg bestemt nødt til at se på hvert element præcis én gang. 422 00:18:54,050 --> 00:18:59,640 Så højden af ​​denne proces er log n, bredden af ​​denne proces, så at sige, 423 00:18:59,640 --> 00:19:02,490 er n, så hvad vi synes at have, i sidste ende, er 424 00:19:02,490 --> 00:19:06,470 en køretid på størrelse n gange log n. 425 00:19:06,470 --> 00:19:08,977 >> Med andre ord, vi delt listen, log n gange, 426 00:19:08,977 --> 00:19:11,810 men hver gang vi gjorde det, vi havde at røre hver enkelt af elementerne 427 00:19:11,810 --> 00:19:13,560 for at flette dem alle sammen, hvilket 428 00:19:13,560 --> 00:19:18,120 var n skridt, så vi har n gange log n, eller som en datalog ville sige, 429 00:19:18,120 --> 00:19:20,380 asymptotisk, som ville være stort ord 430 00:19:20,380 --> 00:19:22,810 at beskrive den øvre bundet på en køretid, 431 00:19:22,810 --> 00:19:28,010 vi kører i en stor o af log n tid, så at sige. 432 00:19:28,010 --> 00:19:31,510 >> Nu er dette er signifikant, fordi huske, hvad de kører tider var 433 00:19:31,510 --> 00:19:34,120 med boble sortere, og udvælgelse sortere og indsættelse sortere, 434 00:19:34,120 --> 00:19:38,200 og endda et par andre, der findes, n kvadreret var, hvor vi var på. 435 00:19:38,200 --> 00:19:39,990 Og du kan, slags, se denne her. 436 00:19:39,990 --> 00:19:45,720 Hvis n kvadreret er naturligvis n gange n, men her har vi n gange log n, 437 00:19:45,720 --> 00:19:48,770 og vi ved allerede fra uge nul, det log n, den logaritmiske, 438 00:19:48,770 --> 00:19:50,550 er bedre end noget lineær. 439 00:19:50,550 --> 00:19:52,930 Efter alt, husker billedet med det røde og det gule 440 00:19:52,930 --> 00:19:56,500 og de grønne linjer, som vi drog, den grøn logaritmisk linje var meget lavere. 441 00:19:56,500 --> 00:20:00,920 Og derfor meget bedre og hurtigere end de lige gule og røde linjer, 442 00:20:00,920 --> 00:20:05,900 n gange log n er faktisk bedre end n gange n, eller n potens. 443 00:20:05,900 --> 00:20:09,110 >> Så vi synes at have identificeret en algoritme merge 444 00:20:09,110 --> 00:20:11,870 slags, der kører i meget hurtigste tid, og faktisk, 445 00:20:11,870 --> 00:20:16,560 det er derfor, tidligere i denne uge, da vi så, at konkurrencen mellem boble 446 00:20:16,560 --> 00:20:20,750 sortering, udvælgelse sortere, og flette sortere, mergesort virkelig, virkelig vundet. 447 00:20:20,750 --> 00:20:23,660 Og ja, vi ikke engang vente til boble sortere og udvælgelse sortere 448 00:20:23,660 --> 00:20:24,790 at færdiggøre. 449 00:20:24,790 --> 00:20:27,410 >> Lad os nu tage en anden pass på dette, fra en lidt mere 450 00:20:27,410 --> 00:20:31,030 formelle perspektiv, bare i tilfælde, det genlyd bedre 451 00:20:31,030 --> 00:20:33,380 end højere diskussion niveau. 452 00:20:33,380 --> 00:20:34,880 Så her er algoritmen igen. 453 00:20:34,880 --> 00:20:36,770 Lad os spørge os selv, hvad køretiden 454 00:20:36,770 --> 00:20:39,287 er af denne algoritmer forskellige trin? 455 00:20:39,287 --> 00:20:41,620 Lad os opdele det i den første sagen og det andet tilfælde. 456 00:20:41,620 --> 00:20:46,280 IF og andet i IF tilfælde Hvis n er mindre end 2, blot tilbage. 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, sådan, som to trin, Hvis n er mindre end 2, derefter vende tilbage. 459 00:20:50,970 --> 00:20:54,580 Men som vi sagde i mandags, konstant tid, eller store o på 1, 460 00:20:54,580 --> 00:20:57,130 kan være to trin, tre trin, selv 1.000 trin. 461 00:20:57,130 --> 00:20:59,870 Det afgørende er, at det er et konstant antal trin. 462 00:20:59,870 --> 00:21:03,240 Så den gule fremhævet pseudokode her kører i, vi vil kalde det, 463 00:21:03,240 --> 00:21:04,490 konstant tid. 464 00:21:04,490 --> 00:21:06,780 Så mere formelt, og vi vil at-- dette 465 00:21:06,780 --> 00:21:09,910 vil være i hvilket omfang vi formalisere denne ret nu-- T n, 466 00:21:09,910 --> 00:21:15,030 køretiden for et problem der tager n somethings som input, 467 00:21:15,030 --> 00:21:19,150 lig stor o af en, Hvis n er mindre end 2. 468 00:21:19,150 --> 00:21:20,640 Så det er betinget af det. 469 00:21:20,640 --> 00:21:24,150 Så for at være klar, hvis n er mindre end 2, har vi en meget kort liste, så 470 00:21:24,150 --> 00:21:29,151 køretiden, T n, hvor n er 1 eller 0, i denne meget specifikke tilfælde, 471 00:21:29,151 --> 00:21:30,650 det bare at gå at være konstant tid. 472 00:21:30,650 --> 00:21:32,691 Det kommer til at tage en trin, to skridt, uanset hvad. 473 00:21:32,691 --> 00:21:33,950 Det er et fast antal trin. 474 00:21:33,950 --> 00:21:38,840 >> Så den saftige del må da være i det andet tilfælde i pseudokode. 475 00:21:38,840 --> 00:21:40,220 ELSE sag. 476 00:21:40,220 --> 00:21:44,870 Sorter venstre halvdel af elementer, sortere højre halvdelen af ​​elementer, flette sorterede halvdele. 477 00:21:44,870 --> 00:21:46,800 Hvor lang tid tager hver af disse trin tage? 478 00:21:46,800 --> 00:21:49,780 Tja, hvis driften tid til at sortere n elementer 479 00:21:49,780 --> 00:21:53,010 er, lad os kalde det meget generisk, T n, 480 00:21:53,010 --> 00:21:55,500 derefter sortering venstre halvdelen af ​​elementerne 481 00:21:55,500 --> 00:21:59,720 er, sådan, som at sige, T n divideret med 2, 482 00:21:59,720 --> 00:22:03,000 og tilsvarende sortering højre halvdel elementer er, sådan, som at sige, 483 00:22:03,000 --> 00:22:06,974 T n delt 2, og derefter sammenlægning de sorterede halvdele. 484 00:22:06,974 --> 00:22:08,890 Tja, hvis jeg har fået nogle antal elementer her, 485 00:22:08,890 --> 00:22:11,230 ligesom fire, og et tal elementer her, ligesom fire, 486 00:22:11,230 --> 00:22:14,650 og jeg er nødt til at fusionere hver af disse fire i, og hver af disse fire i én 487 00:22:14,650 --> 00:22:17,160 efter den anden, således at i sidste ende har jeg otte elementer. 488 00:22:17,160 --> 00:22:20,230 Det føles som det er stort o af n trin? 489 00:22:20,230 --> 00:22:23,500 Hvis jeg har fået n fingre og hver af dem skal flettes på plads, 490 00:22:23,500 --> 00:22:25,270 det er ligesom en anden n trin. 491 00:22:25,270 --> 00:22:27,360 >> Så ja formulaically, Vi kan udtrykke dette, 492 00:22:27,360 --> 00:22:29,960 omend lidt skræmmende ved første øjekast, men det er noget 493 00:22:29,960 --> 00:22:31,600 der fanger netop denne logik. 494 00:22:31,600 --> 00:22:35,710 Køretiden, T n, hvis n er større end eller lig med 2. 495 00:22:35,710 --> 00:22:42,500 I dette tilfælde ELSE tilfælde er T n divideret med 2, plus T N divideret med 2, 496 00:22:42,500 --> 00:22:45,320 plus store o af n, nogle lineær antal trin, 497 00:22:45,320 --> 00:22:51,630 måske præcis n, måske 2 gange n, men det er groft, orden n. 498 00:22:51,630 --> 00:22:54,060 Så det også, er, hvordan vi kan udtrykke denne formulaically. 499 00:22:54,060 --> 00:22:56,809 Nu vil du ikke vide dette, medmindre du har optaget det i dit sind, 500 00:22:56,809 --> 00:22:58,710 eller slå det op i bagsiden af ​​en lærebog, at 501 00:22:58,710 --> 00:23:00,501 kunne have lidt snyde ark i slutningen, 502 00:23:00,501 --> 00:23:03,940 men dette er faktisk kommer til at give os en stor o af n log n, 503 00:23:03,940 --> 00:23:06,620 fordi gentagelse, der du ser her på skærmen, 504 00:23:06,620 --> 00:23:09,550 hvis du rent faktisk gjorde det ud, med et uendeligt antal eksempler, 505 00:23:09,550 --> 00:23:13,000 eller du gjorde det formulaically, ville du se, at dette, fordi denne formel 506 00:23:13,000 --> 00:23:17,100 selv er rekursiv, med t n over noget til højre, 507 00:23:17,100 --> 00:23:21,680 og t for nanoteknologi over til venstre, kan dette faktisk udtrykkes, i sidste ende, 508 00:23:21,680 --> 00:23:24,339 så store go af n log n. 509 00:23:24,339 --> 00:23:26,130 Hvis ikke overbevist, det er bøde for nu, bare 510 00:23:26,130 --> 00:23:28,960 tage på tro, at det er, ja, hvad det gentagelse fører til, 511 00:23:28,960 --> 00:23:31,780 men det er bare lidt mere af en matematiske tilgang til at kigge 512 00:23:31,780 --> 00:23:36,520 på køretiden for mergesort baseret på dens pseudokode alene. 513 00:23:36,520 --> 00:23:39,030 >> Lad os nu tage lidt af en pause fra alt dette, 514 00:23:39,030 --> 00:23:41,710 og tage et kig på en visse tidligere senator, der 515 00:23:41,710 --> 00:23:44,260 ser måske lidt bekendt, der sad ned med Googles Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, for nogen tid siden, til et interview på scenen, foran en hel flok 517 00:23:48,410 --> 00:23:53,710 af mennesker, taler i sidste ende om et emne, der er temmelig nu velkendte. 518 00:23:53,710 --> 00:23:54,575 Lad os tage et kig. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Nu senator, du er her hos Google, 521 00:24:03,890 --> 00:24:09,490 og jeg kan lide at tænke på formandskab som en jobsamtale. 522 00:24:09,490 --> 00:24:11,712 Nu er det svært at få et job som præsident. 523 00:24:11,712 --> 00:24:12,670 Præsident Obama: Right. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: Og du er vil gøre [uhørligt] nu. 525 00:24:13,940 --> 00:24:15,523 Det er også svært at få et job hos Google. 526 00:24:15,523 --> 00:24:17,700 Præsident Obama: Right. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Vi har spørgsmål, og vi beder vores kandidater spørgsmål, 528 00:24:21,330 --> 00:24:24,310 og denne er fra Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> Præsident Obama: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Hvad? 531 00:24:27,005 --> 00:24:28,130 Du fyre tror jeg kidding? 532 00:24:28,130 --> 00:24:30,590 Det er lige her. 533 00:24:30,590 --> 00:24:33,490 Hvad er den mest effektive måde at sortere en million 32 bit heltal? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> Præsident Obama: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Nogle gange, måske er jeg ked af, maybe-- 537 00:24:41,020 --> 00:24:42,750 Præsident Obama: Nej, nej, nej, nej, nej, jeg tror-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: Det er ikke det-- 539 00:24:43,240 --> 00:24:45,430 Præsident Obama: Jeg tror, ​​jeg tror, ​​boblen 540 00:24:45,430 --> 00:24:46,875 sortering ville være den forkerte vej at gå. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Kom nu. 543 00:24:50,535 --> 00:24:52,200 Hvem fortalte ham det? 544 00:24:52,200 --> 00:24:54,020 OK. 545 00:24:54,020 --> 00:24:55,590 Jeg gjorde ikke datalogi on-- 546 00:24:55,590 --> 00:24:58,986 >> Præsident Obama: Vi har fik vores spioner derinde. 547 00:24:58,986 --> 00:24:59,860 PROFESSOR: Okay. 548 00:24:59,860 --> 00:25:03,370 Lad os efterlade os nu teoretiske verden af ​​algoritmer 549 00:25:03,370 --> 00:25:06,520 i asymptotiske analyse deraf, og vende tilbage til nogle emner 550 00:25:06,520 --> 00:25:09,940 fra uge nul og én, og starte at fjerne nogle uddannelse hjul, 551 00:25:09,940 --> 00:25:10,450 hvis du vil. 552 00:25:10,450 --> 00:25:13,241 Så du virkelig forstår i sidste ende fra jorden op, hvad er 553 00:25:13,241 --> 00:25:16,805 foregår under kølerhjelmen, når du skrive, kompilere, og udføre programmer. 554 00:25:16,805 --> 00:25:19,680 Husk især, at dette var det første C-program vi kiggede på, 555 00:25:19,680 --> 00:25:22,840 en kanonisk, simpelt program slags, relativt set, 556 00:25:22,840 --> 00:25:24,620 hvor, udskriver, Hello World. 557 00:25:24,620 --> 00:25:27,610 Og husker, at jeg sagde, at processen denne kildekode går gennem 558 00:25:27,610 --> 00:25:28,430 er netop dette. 559 00:25:28,430 --> 00:25:31,180 Du tager din kildekode, pass det gennem en compiler, ligesom Dunk, 560 00:25:31,180 --> 00:25:34,650 og ud kommer objektkode, at kunne se sådan ud, nuller og ettaller 561 00:25:34,650 --> 00:25:37,880 at computerens CPU, centrale behandlingsenhed eller hjerne, 562 00:25:37,880 --> 00:25:39,760 i sidste ende forstår. 563 00:25:39,760 --> 00:25:42,460 >> Det viser sig, at der er en lidt af en oversimplificering, 564 00:25:42,460 --> 00:25:44,480 at vi er nu i en position til at drille hinanden 565 00:25:44,480 --> 00:25:46,720 at forstå, hvad der virkelig har været foregår under emhætten 566 00:25:46,720 --> 00:25:48,600 hver gang du kører Klang, eller mere generelt, 567 00:25:48,600 --> 00:25:53,040 hver gang du laver et program, hjælp Foretag og CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Især ting som dette genereres først, 569 00:25:56,760 --> 00:25:58,684 når du først kompilere dit program. 570 00:25:58,684 --> 00:26:00,600 Med andre ord, når man tage din kildekode 571 00:26:00,600 --> 00:26:04,390 og kompilere det, hvad er først blive udsendt ved Dunk 572 00:26:04,390 --> 00:26:06,370 er noget kendt som samling kode. 573 00:26:06,370 --> 00:26:08,990 Og i virkeligheden er det ser ud præcis som dette. 574 00:26:08,990 --> 00:26:11,170 >> Jeg løb en kommando ved kommandolinjen tidligere. 575 00:26:11,170 --> 00:26:16,260 Klang Dash kapital s hello.c, og dette skabte en fil 576 00:26:16,260 --> 00:26:19,490 for mig kaldte hello.s, inden i hvilken var nøjagtigt 577 00:26:19,490 --> 00:26:22,290 disse indhold og lidt mere ovenfor og lidt mere nedenfor, 578 00:26:22,290 --> 00:26:25,080 men jeg har lagt den juiciest information her på skærmen. 579 00:26:25,080 --> 00:26:29,190 Og hvis man ser nøje, vil du se mindst et par velkendte søgeord. 580 00:26:29,190 --> 00:26:31,330 Vi har vigtigste øverst. 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å goddag verden backslash n i anførselstegn ned nedenfor. 583 00:26:38,670 --> 00:26:42,450 >> Og alt andet i her er instruktioner meget lavt niveau 584 00:26:42,450 --> 00:26:45,500 at computerens CPU forstår. 585 00:26:45,500 --> 00:26:50,090 CPU instruktioner, der bevæger hukommelse omkring, at belastning strenge fra hukommelsen, 586 00:26:50,090 --> 00:26:52,750 og i sidste ende, udskrive ting på skærmen. 587 00:26:52,750 --> 00:26:56,780 Nu, hvad der sker, selvom efter denne forsamling kode er genereret? 588 00:26:56,780 --> 00:26:59,964 I sidste ende, du gør, ja, stadig generere objektkode. 589 00:26:59,964 --> 00:27:02,630 Men de skridt, der har virkelig stået på under hætten 590 00:27:02,630 --> 00:27:04,180 se lidt mere som denne. 591 00:27:04,180 --> 00:27:08,390 Kildekode bliver forsamling kode, som så bliver objektkode, 592 00:27:08,390 --> 00:27:11,930 og de operative ord her er at, når du kompilere din kildekode, 593 00:27:11,930 --> 00:27:16,300 ud kommer forsamling kode, og derefter når du samler din samling kode, 594 00:27:16,300 --> 00:27:17,800 ud kommer objektkode. 595 00:27:17,800 --> 00:27:20,360 >> Nu Dunk er super sofistikeret, som en masse compilere, 596 00:27:20,360 --> 00:27:23,151 og det gør alle disse trin sammen, og det gør ikke nødvendigvis 597 00:27:23,151 --> 00:27:25,360 output nogen mellemliggende filer, som du selv kan se. 598 00:27:25,360 --> 00:27:28,400 Det bare samler ting, som er den generelle betegnelse, 599 00:27:28,400 --> 00:27:30,000 beskriver hele denne proces. 600 00:27:30,000 --> 00:27:32,000 Men hvis du virkelig ønsker at være særlig, der er 601 00:27:32,000 --> 00:27:34,330 meget mere foregår der. 602 00:27:34,330 --> 00:27:38,860 >> Men lad os også overveje nu, at selv at super simpelt program, hello.c, 603 00:27:38,860 --> 00:27:40,540 kaldes en funktion. 604 00:27:40,540 --> 00:27:41,870 Det opfordrede printf. 605 00:27:41,870 --> 00:27:46,900 Men jeg skrev ikke printf, ja, der kommer med C, så at sige. 606 00:27:46,900 --> 00:27:51,139 Det er en funktion, tilbagekaldelse, der er erklæret i standard io.h, som 607 00:27:51,139 --> 00:27:53,180 er en header fil, som er et emne, vi vil faktisk 608 00:27:53,180 --> 00:27:55,780 dykke mere i dybden inden længe. 609 00:27:55,780 --> 00:27:58,000 Men en header fil er typisk ledsaget 610 00:27:58,000 --> 00:28:02,920 ved en kode-fil, kildekode-fil, så meget gerne der findes standard io.h. 611 00:28:02,920 --> 00:28:05,930 >> Engang siden, nogen, eller læserens, skrev også 612 00:28:05,930 --> 00:28:11,040 en fil kaldet standard io.c, i som den faktiske definitioner, 613 00:28:11,040 --> 00:28:15,220 eller implementeringer af printf, og klaser af andre funktioner, 614 00:28:15,220 --> 00:28:16,870 er faktisk skrevet. 615 00:28:16,870 --> 00:28:22,140 Så givet, at hvis vi overveje at have her til venstre, hello.c, at når 616 00:28:22,140 --> 00:28:26,250 kompileret, giver os hello.s, selv om Dunk ikke generer besparelse på et sted 617 00:28:26,250 --> 00:28:31,360 vi kan se det, og det samling kode bliver samlet i hello.o, som 618 00:28:31,360 --> 00:28:34,630 er faktisk standardnavnet givet, når du kompilere kilde 619 00:28:34,630 --> 00:28:39,350 kode til objektkode, men er ikke helt klar til at udføre det endnu, 620 00:28:39,350 --> 00:28:41,460 fordi endnu et skridt skal ske, og har 621 00:28:41,460 --> 00:28:44,440 været tilfældet i de sidste par uger, måske ukendt for dig. 622 00:28:44,440 --> 00:28:47,290 >> Specielt et sted i CS50 IDE, og dette, 623 00:28:47,290 --> 00:28:49,870 vil også være lidt af en oversimplificering for et øjeblik, 624 00:28:49,870 --> 00:28:54,670 der er, eller var på et tidspunkt, en fil kaldet standard io.c, 625 00:28:54,670 --> 00:28:58,440 at nogen samlet i standard io.s eller tilsvarende, 626 00:28:58,440 --> 00:29:02,010 at nogen derefter samles i standard io.o, 627 00:29:02,010 --> 00:29:04,600 eller det viser sig i en lidt anderledes fil 628 00:29:04,600 --> 00:29:07,220 format, der kan have en anden fil forlængelse helt, 629 00:29:07,220 --> 00:29:11,720 men i teori og begrebsmæssigt, præcis disse skridt skulle ske i en eller anden form. 630 00:29:11,720 --> 00:29:14,060 Hvilket vil sige, at nu når jeg skriver et program, 631 00:29:14,060 --> 00:29:17,870 hello.c, der bare siger, hej verden, og jeg bruger en andens kode 632 00:29:17,870 --> 00:29:22,480 ligesom printf, som engang var på en tid, i en fil kaldet standard io.c, 633 00:29:22,480 --> 00:29:26,390 så en eller anden måde jeg nødt til at tage min objektkode, mine nuller og ettaller, 634 00:29:26,390 --> 00:29:29,260 og at personens objekt kode, eller nuller og ettaller, 635 00:29:29,260 --> 00:29:34,970 og på en måde linke dem sammen i en sidste fil, kaldet goddag, at 636 00:29:34,970 --> 00:29:38,070 har alle de nuller og dem fra min vigtigste funktion, 637 00:29:38,070 --> 00:29:40,830 og alle de nuller og dem for printf. 638 00:29:40,830 --> 00:29:44,900 >> Og ja, det sidste proces er kaldes, der forbinder dit objekt kode. 639 00:29:44,900 --> 00:29:47,490 Hvis udgang er en eksekverbar fil. 640 00:29:47,490 --> 00:29:49,780 Så i retfærdighed, på slutningen af ​​dagen, intet 641 00:29:49,780 --> 00:29:52,660 har ændret sig siden uge en, når vi begyndte kompilering programmer. 642 00:29:52,660 --> 00:29:55,200 Faktisk har alt dette været sker under kølerhjelmen, 643 00:29:55,200 --> 00:29:57,241 men nu er vi i en position hvor vi kan faktisk 644 00:29:57,241 --> 00:29:58,794 drille hinanden disse forskellige trin. 645 00:29:58,794 --> 00:30:00,710 Og ja, i slutningen af dagen, vi er stadig 646 00:30:00,710 --> 00:30:04,480 venstre med nuller og ettaller, som er faktisk en stor segue nu 647 00:30:04,480 --> 00:30:08,620 til en anden evne C, der vi har ikke haft til at udnytte sandsynligvis 648 00:30:08,620 --> 00:30:11,250 til dato, kendt som bitvise operatører. 649 00:30:11,250 --> 00:30:15,220 Med andre ord, hidtil, når som helst vi har behandlet data i C eller variabler i C, 650 00:30:15,220 --> 00:30:17,660 vi har haft ting som chars og flåd og ins 651 00:30:17,660 --> 00:30:21,990 og længes og doubler og lignende, men alle disse er mindst otte bits. 652 00:30:21,990 --> 00:30:25,550 Vi har endnu aldrig været i stand til manipulere individuelle bits, 653 00:30:25,550 --> 00:30:28,970 selv om en individuel bit, vi ved, kan udgøre en 0 og en 1. 654 00:30:28,970 --> 00:30:32,640 Nu viser det sig, at i C, du kan få adgang til individuelle bits, 655 00:30:32,640 --> 00:30:35,530 hvis du kender syntaksen, med til at få ram på dem. 656 00:30:35,530 --> 00:30:38,010 >> Så lad os tage et kig ved bitvise operatører. 657 00:30:38,010 --> 00:30:41,700 Så afbilledet her er et par symboler, vi har, sådan, en slags, set før. 658 00:30:41,700 --> 00:30:45,580 Jeg ser en ét-tegn, en lodret bar, og nogle andre samt, 659 00:30:45,580 --> 00:30:49,430 og minde om, at tegnet tegnet er noget, vi har set før. 660 00:30:49,430 --> 00:30:54,060 Den logiske og operatør, hvor du har to af dem sammen, eller logisk OR 661 00:30:54,060 --> 00:30:56,300 operatør, hvor du har to lodrette stænger. 662 00:30:56,300 --> 00:31:00,550 Bitvise operatører, som vi vil se operere på bits individuelt, 663 00:31:00,550 --> 00:31:03,810 bare bruge en enkelt ét-tegn, et enkelt lodret bar, indsætningstegn symbol 664 00:31:03,810 --> 00:31:06,620 kommer næste, den lille tilde, og derefter til venstre 665 00:31:06,620 --> 00:31:08,990 beslag venstre konsol eller højre beslag til højre beslag. 666 00:31:08,990 --> 00:31:10,770 Hver af disse har forskellige betydninger. 667 00:31:10,770 --> 00:31:11,950 >> Faktisk, lad os tage et kig. 668 00:31:11,950 --> 00:31:16,560 Lad os gå gamle skole i dag, og brug en touch skærm fra gårsdagens, 669 00:31:16,560 --> 00:31:18,002 kendt som et hvidt bord. 670 00:31:18,002 --> 00:31:19,710 Og denne hvide bord kommer til at give os 671 00:31:19,710 --> 00:31:27,360 at udtrykke nogle temmelig simple symboler, eller rettere nogle temmelig simple formler, 672 00:31:27,360 --> 00:31:29,560 at vi kan så i sidste ende gearing, med henblik på 673 00:31:29,560 --> 00:31:33,230 at få adgang til de enkelte bits inden for et C-program. 674 00:31:33,230 --> 00:31:34,480 Med andre ord, lad os gøre det. 675 00:31:34,480 --> 00:31:37,080 Lad os først tale om en øjeblik om tegnet, 676 00:31:37,080 --> 00:31:39,560 som er den bitvise OG operatør. 677 00:31:39,560 --> 00:31:42,130 Med andre ord er dette en operatør, der giver mulighed 678 00:31:42,130 --> 00:31:45,930 mig at have en venstre variabel typisk, og en højre variabel, 679 00:31:45,930 --> 00:31:50,640 eller en individuel værdi, at hvis vi OG dem sammen, giver mig et endeligt resultat. 680 00:31:50,640 --> 00:31:51,560 Så hvad gør jeg mener? 681 00:31:51,560 --> 00:31:54,840 Hvis der i et program, har du en variabel der lagrer en af ​​disse værdier, 682 00:31:54,840 --> 00:31:58,000 eller lad os holde det simpelt, og bare skrive nuller og ettaller individuelt, 683 00:31:58,000 --> 00:32:00,940 her er hvordan det tegnet operatør fungerer. 684 00:32:00,940 --> 00:32:06,400 0 0 tegnet vil lig med 0. 685 00:32:06,400 --> 00:32:07,210 Nu hvorfor er det? 686 00:32:07,210 --> 00:32:09,291 >> Det er meget lig Booleske udtryk, 687 00:32:09,291 --> 00:32:10,540 at vi har diskuteret hidtil. 688 00:32:10,540 --> 00:32:15,800 Hvis du tror trods alt 0 er falsk, 0 er falsk, falsk og falsk 689 00:32:15,800 --> 00:32:18,720 er, som vi har diskuteret logisk, også er falsk. 690 00:32:18,720 --> 00:32:20,270 Så vi får 0 her. 691 00:32:20,270 --> 00:32:24,390 Hvis du tager 0-tegn 1, Det er også, 692 00:32:24,390 --> 00:32:29,890 kommer til at være 0, da denne venstre udtryk til at være sandt eller 1, 693 00:32:29,890 --> 00:32:32,360 det vil være nødvendigt at være sandt og rigtigt. 694 00:32:32,360 --> 00:32:36,320 Men her har vi falske og sandt, eller 0 og 1. 695 00:32:36,320 --> 00:32:42,000 Nu igen, hvis vi har en ét-tegn 0, at også kommer til at 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 gør noget interessant med denne operator 698 00:32:50,340 --> 00:32:51,850 lige nu, denne tegnet operatør. 699 00:32:51,850 --> 00:32:53,780 Det er den bitvise OG operatør. 700 00:32:53,780 --> 00:32:57,290 Men disse er ingredienserne via hvilken vi kan gøre 701 00:32:57,290 --> 00:32:59,240 interessante ting, som vi snart vil se. 702 00:32:59,240 --> 00:33:02,790 >> Lad os nu se på det helt enkelt lodret streg over her til højre. 703 00:33:02,790 --> 00:33:06,710 Hvis jeg har en 0 bit og jeg Eller det med, den bitvise 704 00:33:06,710 --> 00:33:11,030 ELLER operatør, en anden 0 bit, der kommer til at give mig 0. 705 00:33:11,030 --> 00:33:17,540 Hvis jeg tager en 0 bit og OR det med en 1 bit, så jeg har tænkt mig at få 1. 706 00:33:17,540 --> 00:33:19,830 Og i virkeligheden, bare for klarhed, lad mig gå tilbage, 707 00:33:19,830 --> 00:33:23,380 så mine lodrette stænger ikke forveksles med 1 s. 708 00:33:23,380 --> 00:33:26,560 Lad mig omskrive alle min 1 er lidt mere 709 00:33:26,560 --> 00:33:32,700 klart, således at vi næste se, om jeg har en 1 eller 0, der kommer til at være en 1, 710 00:33:32,700 --> 00:33:39,060 og hvis jeg har en 1 eller 1, der, Også vil være en 1. 711 00:33:39,060 --> 00:33:42,900 Så du kan se logisk, at OR operatør opfører sig meget forskelligt. 712 00:33:42,900 --> 00:33:48,070 Det giver mig 0 eller 0 giver mig 0, men hver anden kombination giver mig 1. 713 00:33:48,070 --> 00:33:52,480 Så længe jeg har en 1 i formel, bliver resultatet kommer til at være 1. 714 00:33:52,480 --> 00:33:55,580 >> I modsætning til AND operatøren, tegnet, 715 00:33:55,580 --> 00:34:00,940 kun hvis jeg har to 1'er i ligning, jeg faktisk få en 1 ud. 716 00:34:00,940 --> 00:34:02,850 Nu er der et par andre operatører så godt. 717 00:34:02,850 --> 00:34:04,810 En af dem er lidt mere involveret. 718 00:34:04,810 --> 00:34:07,980 Så lad mig gå videre og slette dette for at frigøre noget plads. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Og lad os tage et kig på den indskudsmærke symbol, for bare et øjeblik. 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å dit tastatur beholdning Shift og derefter et af numrene oven din amerikanske 723 00:34:21,420 --> 00:34:22,250 tastatur. 724 00:34:22,250 --> 00:34:26,190 >> Så dette er den eksklusive ELLER operatør, eksklusive OR. 725 00:34:26,190 --> 00:34:27,790 Så vi har lige set operatoren OR. 726 00:34:27,790 --> 00:34:29,348 Dette er den eksklusive OR operatøren. 727 00:34:29,348 --> 00:34:30,639 Hvad er egentlig forskellen? 728 00:34:30,639 --> 00:34:34,570 Jamen så lad os bare se på formlen, og bruge denne som ingredienser i sidste ende. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Jeg har tænkt mig at sige, er altid 0. 731 00:34:39,650 --> 00:34:41,400 Det er definitionen af ​​XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 vil være 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 vil være 1, og 1 XOR 1 kommer til at være? 734 00:34:58,810 --> 00:34:59,890 Forkert? 735 00:34:59,890 --> 00:35:00,520 Eller højre? 736 00:35:00,520 --> 00:35:01,860 Jeg ved ikke. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Nu, hvad der foregår her? 739 00:35:04,700 --> 00:35:06,630 Nå tænke på navn på denne operatør. 740 00:35:06,630 --> 00:35:09,980 Eksklusiv OR, så som navn, type, antyder, 741 00:35:09,980 --> 00:35:13,940 svaret er kun vil være en 1, hvis input er eksklusive, 742 00:35:13,940 --> 00:35:15,560 udelukkende anderledes. 743 00:35:15,560 --> 00:35:18,170 Så her indgangene er samme, så produktionen er 0. 744 00:35:18,170 --> 00:35:20,700 Her indgangene er samme, så produktionen er 0. 745 00:35:20,700 --> 00:35:25,640 Her er de udgange er forskellige, de er eksklusive, og så produktionen er 1. 746 00:35:25,640 --> 00:35:28,190 Så det er meget lig Og det er meget ens, 747 00:35:28,190 --> 00:35:32,760 eller det er snarere meget lig OR, men kun i en eksklusiv måde. 748 00:35:32,760 --> 00:35:36,210 Dette er ikke længere en 1, fordi vi har to 1 s, 749 00:35:36,210 --> 00:35:38,621 og ikke udelukkende, kun et af dem. 750 00:35:38,621 --> 00:35:39,120 Okay. 751 00:35:39,120 --> 00:35:40,080 Hvad med de andre? 752 00:35:40,080 --> 00:35:44,220 Nå tilde, i mellemtiden, er faktisk nice og enkel, heldigvis. 753 00:35:44,220 --> 00:35:46,410 Og det er en unary operatør, hvilket betyder 754 00:35:46,410 --> 00:35:50,400 det er anvendt kun én indgang, én operand, så at sige. 755 00:35:50,400 --> 00:35:51,800 Ikke at en venstre og en højre. 756 00:35:51,800 --> 00:35:56,050 Med andre ord, hvis du tager tilde af 0, vil svaret være det modsatte. 757 00:35:56,050 --> 00:35:59,710 Og hvis du tager tilde på 1, det Svaret vil der være det modsatte. 758 00:35:59,710 --> 00:36:02,570 Så den tilde operatør en måde at bevirke en smule, 759 00:36:02,570 --> 00:36:06,000 eller spejlvende lidt fra Fra 0 til 1, eller 1 til 0. 760 00:36:06,000 --> 00:36:09,820 >> Og det efterlader os endelig med blot to endelige operatører, 761 00:36:09,820 --> 00:36:13,840 den såkaldte venstre skift, og såkaldte ret-operatør. 762 00:36:13,840 --> 00:36:16,620 Lad os tage et kig på, hvordan de arbejder. 763 00:36:16,620 --> 00:36:20,780 Den venstre skift operatør, skriftlig med to vinkelbeslag som dette, 764 00:36:20,780 --> 00:36:22,110 fungerer som følger. 765 00:36:22,110 --> 00:36:27,390 Hvis min input, eller min operand, til venstre skift operatør er ganske enkelt en 1. 766 00:36:27,390 --> 00:36:33,750 Og jeg så fortælle computeren til venstre skift at 1, siger syv pladser, 767 00:36:33,750 --> 00:36:37,150 resultatet er, som om jeg tage, at 1, og flytte det 768 00:36:37,150 --> 00:36:40,160 syv pladser over til venstre, og som standard, 769 00:36:40,160 --> 00:36:42,270 vi kommer til at antage, at plads til højre 770 00:36:42,270 --> 00:36:44,080 vil være polstret med nuller. 771 00:36:44,080 --> 00:36:50,316 Med andre ord, 1 venstre skift 7 går at give mig, at 1, efterfulgt af 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åde, det giver dig mulighed for at tage et lille antal som 1, 774 00:36:57,380 --> 00:37:00,740 og klart gøre det meget meget, meget større på denne måde, 775 00:37:00,740 --> 00:37:06,460 men vi faktisk kommer til at se mere kloge metoder til det 776 00:37:06,460 --> 00:37:08,080 stedet, samt, 777 00:37:08,080 --> 00:37:08,720 >> Okay. 778 00:37:08,720 --> 00:37:10,060 Det er det for uge tre. 779 00:37:10,060 --> 00:37:11,400 Vi vil se dig næste gang. 780 00:37:11,400 --> 00:37:12,770 Det var CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Musik spiller] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Han var på snack bar spise en varm sludder sundae. 784 00:37:25,766 --> 00:37:28,090 Han havde det hele hans ansigt. 785 00:37:28,090 --> 00:37:30,506 Han er iført at chokolade som en skæg 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Hvad laver du? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Hvad? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Har du lige double dip? 790 00:37:36,800 --> 00:37:38,585 Du dobbelt dyppet chippen. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Undskyld mig. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Du dyppet chippen, du tog en bid, og du dyppet igen. 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 ligesom at sætte Hele din mund lige i dip. 795 00:37:48,440 --> 00:37:52,400 Næste gang du tager en chip, bare dyppe den én gang, og afslutte det. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Ved du hvad, Dan? 797 00:37:53,890 --> 00:37:58,006 Du dyppe den måde, du ønsker at dyppe. 798 00:37:58,006 --> 00:38:01,900 Jeg vil dyppe den måde, at jeg ønsker at dyppe. 799 00:38:01,900 --> 00:38:03,194