1 00:00:00,000 --> 00:00:11,904 >> [Glazbom] 2 00:00:11,904 --> 00:00:12,910 >> PROFESOR: U redu. 3 00:00:12,910 --> 00:00:16,730 To je CS50 i to je kraj tjedna tri. 4 00:00:16,730 --> 00:00:20,230 Tako smo danas ovdje, a ne u Sanders Kazalište, umjesto u Weidner knjižnici. 5 00:00:20,230 --> 00:00:23,170 Unutar kojih je studio poznat kao Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 ili ćemo reći Studio H, ili će smo say-- ako ste uživali tu šalu, 7 00:00:28,310 --> 00:00:30,540 to je zapravo iz kolega, Mark, on-line, 8 00:00:30,540 --> 00:00:32,420 koji je sugerirao koliko putem Twittera. 9 00:00:32,420 --> 00:00:34,270 Sada ono što je cool o biti ovdje u studiju 10 00:00:34,270 --> 00:00:38,410 je da sam okružena njima zeleno Zidovi, zeleni zaslon ili chroma, 11 00:00:38,410 --> 00:00:43,290 da se tako izrazim, što znači da je CS50 produkcijski tim, bez znanja mi 12 00:00:43,290 --> 00:00:47,380 upravo sada, mogao biti stavljajući me najviše bilo gdje u svijetu, 13 00:00:47,380 --> 00:00:48,660 za bolje ili na gore. 14 00:00:48,660 --> 00:00:51,800 >> Sada ono što je pred nama, problem postaviti dva je u vašim rukama za ovaj tjedan, 15 00:00:51,800 --> 00:00:53,830 ali s problemom postaviti tri Ovog će tjedna, 16 00:00:53,830 --> 00:00:56,600 ćete biti izazvan s tzv igra 15, 17 00:00:56,600 --> 00:00:58,960 stara stranka milost da možda podsjetiti prima 18 00:00:58,960 --> 00:01:02,030 kao dijete koje ima cijela hrpa brojeva koji mogu slajd gore, dolje, 19 00:01:02,030 --> 00:01:05,790 lijevo i desno, a postoji jedan jaz unutar slagalice, u koju 20 00:01:05,790 --> 00:01:07,840 zapravo može kliziti one slagalice. 21 00:01:07,840 --> 00:01:11,150 Na kraju ćete dobiti ovo zagonetka u nekom polu slučajnim redoslijedom, 22 00:01:11,150 --> 00:01:12,940 a cilj je da se to riješiti, od vrha do dna, 23 00:01:12,940 --> 00:01:16,310 lijeva na desno, od jednog pa sve do preko 15 godina. 24 00:01:16,310 --> 00:01:19,360 >> Nažalost, provedba ćete imati pri ruci 25 00:01:19,360 --> 00:01:21,590 će biti softvera temelji, a ne fizički. 26 00:01:21,590 --> 00:01:25,280 Vi ste zapravo morati napisati kod s kojim student ili korisnik može 27 00:01:25,280 --> 00:01:26,760 igrati igru ​​15. 28 00:01:26,760 --> 00:01:29,030 A u stvari, u hakera izdanje igre od 15 godina, 29 00:01:29,030 --> 00:01:32,155 ćete biti izazov za provedbu, ne samo igranje ove stare škole 30 00:01:32,155 --> 00:01:35,010 igra, nego rješavanje nje, provedbu boga mod, 31 00:01:35,010 --> 00:01:38,280 da tako kažemo, da je zapravo rješava zagonetku za čovjeka, 32 00:01:38,280 --> 00:01:41,080 pružajući im savjet, Nakon savjet, nakon naznaka. 33 00:01:41,080 --> 00:01:42,280 Dakle, više o tome sljedeći tjedan. 34 00:01:42,280 --> 00:01:43,720 No, to je ono što se nalazi ispred. 35 00:01:43,720 --> 00:01:47,610 >> Za sada podsjećaju da je ranije ovog tjedna imali smo tu Cliffhanger, ako hoćete, 36 00:01:47,610 --> 00:01:52,560 pri čemu najbolje radimo sortiranje Mudar je gornja granica za velike o n 37 00:01:52,560 --> 00:01:53,210 kvadrat. 38 00:01:53,210 --> 00:01:56,520 Drugim riječima, mjehurić sortirati, izbor vrsta, umetanje vrsta, 39 00:01:56,520 --> 00:01:59,120 sve njih, a razlikuju u njihovoj provedbi, 40 00:01:59,120 --> 00:02:03,480 devolved u n na kvadrat trčanje Vrijeme u vrlo najgorem slučaju. 41 00:02:03,480 --> 00:02:06,010 I općenito pretpostaviti da vrlo najgori slučaj za sortiranje 42 00:02:06,010 --> 00:02:08,814 jedan je da vaši inputi potpuno unatrag. 43 00:02:08,814 --> 00:02:11,980 I doista, to je dosta koraka provesti svaki od tih algoritama. 44 00:02:11,980 --> 00:02:15,110 >> Sada je na samom kraju klase Podsjetimo, usporedili smo mjehurić vrsta 45 00:02:15,110 --> 00:02:19,390 protiv selekcije vrste protiv jednog drugog koje se zove pisma vrsta u to vrijeme, 46 00:02:19,390 --> 00:02:22,120 i predlažem da je uzimanje Prednost lekcije iz tjedna 47 00:02:22,120 --> 00:02:24,060 nula, podijeli pa vladaj. 48 00:02:24,060 --> 00:02:28,810 I nekako postizanje neke vrste logaritamska vrijeme rada u konačnici, 49 00:02:28,810 --> 00:02:31,024 umjesto nečega to je čisto kvadratna. 50 00:02:31,024 --> 00:02:33,440 I to nije sasvim logaritamska, to je malo više od toga. 51 00:02:33,440 --> 00:02:36,520 Ali, ako se sjećate iz razreda, bilo je mnogo, mnogo brže. 52 00:02:36,520 --> 00:02:38,210 Idemo pogledati gdje smo stali. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble sort odnosu izbor vrsta u odnosu na spajanje vrste. 55 00:02:45,370 --> 00:02:47,700 Sada svi oni prikazuju u teorije, istovremeno. 56 00:02:47,700 --> 00:02:50,510 CPU radi na istoj brzini. 57 00:02:50,510 --> 00:02:54,990 Ali možete osjetiti kako se to dosadno je vrlo brzo će postati, 58 00:02:54,990 --> 00:02:58,790 i koliko brzo, kada smo se uvelo malo algoritama tjedan Zero-a, 59 00:02:58,790 --> 00:03:00,080 možemo ubrzati. 60 00:03:00,080 --> 00:03:01,630 >> Dakle, oznaka vrsta izgleda nevjerojatna. 61 00:03:01,630 --> 00:03:05,220 Kako to možemo iskoristiti, kako bi sortirati brojeve brže. 62 00:03:05,220 --> 00:03:07,140 Pa neka je misliti leđa na sastojak koji se 63 00:03:07,140 --> 00:03:10,380 imali još u tjednu nula, onaj u potrazi za nekoga u telefonskom imeniku, 64 00:03:10,380 --> 00:03:12,380 i podsjetiti da je pseudokod koje smo predložili, 65 00:03:12,380 --> 00:03:14,560 putem koje možemo naći netko poput Mike Smith, 66 00:03:14,560 --> 00:03:16,310 Pogledao malo nešto ovako. 67 00:03:16,310 --> 00:03:20,820 >> Sada pogledajte osobito u liniji 7 i 8 i 10 i 11, 68 00:03:20,820 --> 00:03:25,240 koji potiču tu petlju, pri čemu smo zadržao povratak na liniji 3 opet, i opet, 69 00:03:25,240 --> 00:03:26,520 i opet. 70 00:03:26,520 --> 00:03:31,790 Ali ispada da možemo vidjeti Ovaj algoritam, ovdje u pseudokod, 71 00:03:31,790 --> 00:03:33,620 malo više holistički. 72 00:03:33,620 --> 00:03:35,960 U stvari, ono što tražim na ovdje na zaslonu, 73 00:03:35,960 --> 00:03:41,180 je algoritam za traženje Mike Smith među nekim skupom stranica. 74 00:03:41,180 --> 00:03:45,520 I doista, možemo pojednostaviti ovaj algoritam u tim linijama 7 i 8, 75 00:03:45,520 --> 00:03:49,860 i 10 i 11 na samo reći ovo, što sam ovdje predstavljen u žuto. 76 00:03:49,860 --> 00:03:52,210 Drugim riječima, ako Mike Smith je ranije u knjizi 77 00:03:52,210 --> 00:03:55,004 ne trebamo odrediti korak po korak kako sada ići ga naći. 78 00:03:55,004 --> 00:03:56,920 Nemamo odrediti vratiti na liniji 3, 79 00:03:56,920 --> 00:03:58,960 zašto ne bismo samo umjesto toga, recimo, općenitije, 80 00:03:58,960 --> 00:04:01,500 tražiti Mikeom u lijeva polovica knjige. 81 00:04:01,500 --> 00:04:03,960 >> Isto tako, ako je Mike zapravo kasnije u knjizi, 82 00:04:03,960 --> 00:04:07,540 zašto ne bismo jednostavno citirati citat pretragu za Mike u desnoj polovici knjige. 83 00:04:07,540 --> 00:04:11,030 Drugim riječima, zašto ne bismo jednostavno vrsta čamac za sebe kaže, 84 00:04:11,030 --> 00:04:13,130 tražiti Mike u ovom podskup knjige, 85 00:04:13,130 --> 00:04:16,279 i prepustiti našim postojećim Algoritam nam reći 86 00:04:16,279 --> 00:04:18,750 kako tražiti Mikea u da lijeva polovica knjige. 87 00:04:18,750 --> 00:04:20,750 Drugim riječima, naš algoritam radi li je 88 00:04:20,750 --> 00:04:24,670 telefonski knjiga ove debljine, to Debljina, ili bilo debljine god. 89 00:04:24,670 --> 00:04:27,826 Tako možemo rekurzivno definirati ovaj algoritam. 90 00:04:27,826 --> 00:04:29,950 Drugim riječima, na Zaslon ovdje je algoritam 91 00:04:29,950 --> 00:04:33,130 za traženje Mike Smith među stranicama telefonskog imenika. 92 00:04:33,130 --> 00:04:37,410 Dakle, u skladu 7 i 10, neka je samo reći upravo to. 93 00:04:37,410 --> 00:04:40,250 I koristim taj termin trenutak Prije, i doista, rekurzija 94 00:04:40,250 --> 00:04:42,450 je buzzword za sada, i to je taj proces 95 00:04:42,450 --> 00:04:47,210 radiš nešto ciklički nekako pomoću kôd koji već imate, 96 00:04:47,210 --> 00:04:49,722 a nazvavši ga opet, i opet, i opet. 97 00:04:49,722 --> 00:04:51,930 Sada to će biti važno da mi je nekako dno 98 00:04:51,930 --> 00:04:53,821 van, a ne radi to beskonačno dugo. 99 00:04:53,821 --> 00:04:56,070 Inače idemo na ima uistinu beskonačan petlju. 100 00:04:56,070 --> 00:04:59,810 Ali neka je vidjeti ako mi može posuditi tu ideju od rekurzije, opet radi nešto 101 00:04:59,810 --> 00:05:03,600 i opet i opet, riješiti sortiranje problema putem spajanja 102 00:05:03,600 --> 00:05:05,900 sortiranje, sve učinkovitije. 103 00:05:05,900 --> 00:05:06,970 >> Tako sam vam dati spojiti vrsta. 104 00:05:06,970 --> 00:05:07,920 Idemo pogledati. 105 00:05:07,920 --> 00:05:10,850 Dakle, ovdje je pseudokod, s koje smo mogli provesti razvrstavanje, 106 00:05:10,850 --> 00:05:12,640 koristeći ovaj algoritam se zove spajanje vrsta. 107 00:05:12,640 --> 00:05:13,880 I to je jednostavno to. 108 00:05:13,880 --> 00:05:15,940 Na ulaz n elemenata, Drugim riječima, ako ste 109 00:05:15,940 --> 00:05:18,830 s obzirom n elemenata i brojeve i slova ili što god da je ulaz, 110 00:05:18,830 --> 00:05:22,430 ako ste s obzirom n elemenata, ako n je manje od 2, jednostavno vratiti. 111 00:05:22,430 --> 00:05:22,930 Pravo? 112 00:05:22,930 --> 00:05:26,430 Jer, ako je n manji od 2, koje znači da moj popis elemenata 113 00:05:26,430 --> 00:05:30,446 bilo je veličine 0 ili 1, i u obje te sitnice, 114 00:05:30,446 --> 00:05:31,570 popis je već riješeno. 115 00:05:31,570 --> 00:05:32,810 Ako ne postoji popis, to je riješeno. 116 00:05:32,810 --> 00:05:35,185 A ako postoji popis duljine 1, to je očito razvrstani. 117 00:05:35,185 --> 00:05:38,280 Dakle, algoritam treba samo stvarno učiniti nešto zanimljivo, 118 00:05:38,280 --> 00:05:40,870 ako imamo dva ili više Elementi dao nama. 119 00:05:40,870 --> 00:05:42,440 Pa pogledajmo magiju tada. 120 00:05:42,440 --> 00:05:47,500 Inače sortirati lijevu polovicu elemenata, zatim poredati desnu polovicu elemenata, 121 00:05:47,500 --> 00:05:49,640 zatim spojiti sortirani polovice. 122 00:05:49,640 --> 00:05:52,440 A što je vrsta uma savijanje ovdje je da ja stvarno ne 123 00:05:52,440 --> 00:05:56,190 Čini se da su ti rekao ništa samo još, zar ne? 124 00:05:56,190 --> 00:05:59,560 Sve što sam rekao je, s obzirom na popis n elemenata, sortiranje lijevu polovicu, 125 00:05:59,560 --> 00:06:01,800 zatim pravo na pola, a zatim spojiti sortirani polovice, 126 00:06:01,800 --> 00:06:03,840 ali gdje je stvarna tajna umak? 127 00:06:03,840 --> 00:06:05,260 Gdje je algoritam? 128 00:06:05,260 --> 00:06:09,150 Pa ispada da ta dva reda Prvo, vrsta napustio pola elemenata, 129 00:06:09,150 --> 00:06:13,970 i vrsta pravu pola elemenata, su rekurzivni pozivi, da se tako izrazim. 130 00:06:13,970 --> 00:06:16,120 >> Uostalom, na ovaj točka u vremenu, moram 131 00:06:16,120 --> 00:06:18,950 algoritam s kojim se sortirati cijela hrpa elemenata? 132 00:06:18,950 --> 00:06:19,450 Da. 133 00:06:19,450 --> 00:06:20,620 To je upravo ovdje. 134 00:06:20,620 --> 00:06:25,180 To je upravo ovdje na zaslonu i tako da ja mogu koristiti taj isti skup koraka 135 00:06:25,180 --> 00:06:28,500 sortirati lijevu polovicu, što mogu pravo na pola. 136 00:06:28,500 --> 00:06:30,420 I doista, opet, i opet. 137 00:06:30,420 --> 00:06:34,210 Dakle, na neki način, i mi uskoro ćete vidjeti, magiju spajanje vrste 138 00:06:34,210 --> 00:06:37,967 koji je ugrađen u vrlo konačna linija, spajanjem razvrstanih polovice. 139 00:06:37,967 --> 00:06:39,300 A to se čini prilično intuitivno. 140 00:06:39,300 --> 00:06:41,050 Uzmeš dvije polovice, a ti, nekako spojiti ih zajedno, 141 00:06:41,050 --> 00:06:43,260 pa ćemo vidjeti konkretno u ovom trenutku. 142 00:06:43,260 --> 00:06:45,080 >> No, to je kompletan algoritam. 143 00:06:45,080 --> 00:06:46,640 I da vidimo točno zašto. 144 00:06:46,640 --> 00:06:50,912 Pa pretpostavimo da smo dali to ista osam elemenata ovdje na ekranu, jedan 145 00:06:50,912 --> 00:06:53,120 kroz osam, ali su u naizgled nasumičnim redoslijedom. 146 00:06:53,120 --> 00:06:55,320 A cilj je pri ruci sortirati tih elemenata. 147 00:06:55,320 --> 00:06:58,280 Pa kako mogu ići o radi korištenja, opet, 148 00:06:58,280 --> 00:07:00,407 spajanje vrsta, kao i po ovom pseudokod? 149 00:07:00,407 --> 00:07:02,740 I opet, okorio ovo vaš um, samo na trenutak. 150 00:07:02,740 --> 00:07:05,270 Prvi slučaj je lijepa trivijalna, ako je manje od 2, 151 00:07:05,270 --> 00:07:07,060 Samo se vrati, nema posla koji treba obaviti. 152 00:07:07,060 --> 00:07:09,290 Pa stvarno postoji samo tri koraci stvarno treba imati na umu. 153 00:07:09,290 --> 00:07:11,081 Opet, i opet, ja sam će htjeti imati 154 00:07:11,081 --> 00:07:13,980 sortirati lijevu polovicu, sortirati desnu polovicu, 155 00:07:13,980 --> 00:07:15,890 a onda nakon njihove dvije polovice su razvrstani, 156 00:07:15,890 --> 00:07:18,710 Želim ih spojiti zajedno u jednu sortiranog popisa. 157 00:07:18,710 --> 00:07:19,940 Pa imajte to na umu. 158 00:07:19,940 --> 00:07:21,310 >> Dakle ovdje je izvorni popis. 159 00:07:21,310 --> 00:07:23,510 Idemo tretirati kao niz, kao što smo počeli 160 00:07:23,510 --> 00:07:25,800 u tjedan dva, što je granični blok memorije. 161 00:07:25,800 --> 00:07:28,480 U tom slučaju, koja sadrži osam brojevi, natrag na leđa na leđa. 162 00:07:28,480 --> 00:07:30,700 I neka sada vrijede pisma vrsta. 163 00:07:30,700 --> 00:07:33,300 Tako sam prvi put želite sortirati lijeva polovica tog popisa, 164 00:07:33,300 --> 00:07:37,370 i neka je, dakle, usredotočiti na 4, 8, 6, i 2. 165 00:07:37,370 --> 00:07:41,000 >> Sada kako mogu ići o sortiranje popisa veličine 4? 166 00:07:41,000 --> 00:07:45,990 Pa moram sada razmotriti sortiranje lijevo od lijeve polovine. 167 00:07:45,990 --> 00:07:47,720 Opet, neka je natrag samo na trenutak. 168 00:07:47,720 --> 00:07:51,010 Ako pseudokod je to, i ja sam dao osam elemenata, 169 00:07:51,010 --> 00:07:53,230 8 je očito veći od ili jednak 2. 170 00:07:53,230 --> 00:07:54,980 Tako je s prvi slučaj ne primjenjuje. 171 00:07:54,980 --> 00:07:58,120 Dakle, za sortiranje osam elemenata, sam prvi put sortirati lijevu polovicu elemenata, 172 00:07:58,120 --> 00:08:01,930 onda sam sortirati desnu polovicu, onda sam spojiti dvije polovice razvrstane, svaki veličine 4. 173 00:08:01,930 --> 00:08:02,470 U REDU. 174 00:08:02,470 --> 00:08:07,480 >> Ali, ako ste upravo mi je rekao, sortiranje lijeva polovica, koja je sada veličine 4, 175 00:08:07,480 --> 00:08:09,350 kako mogu sortirati utakmice polovicu? 176 00:08:09,350 --> 00:08:11,430 Pa, ako imam ulaz četiri elementa, 177 00:08:11,430 --> 00:08:14,590 Prvi put sam sortirati lijevu dva, onda pravo dva, 178 00:08:14,590 --> 00:08:16,210 i onda sam ih spojiti zajedno. 179 00:08:16,210 --> 00:08:18,700 Pa opet, to postaje malo od uma savijanje igra ovdje 180 00:08:18,700 --> 00:08:21,450 zato vas, vrsta, moraju sjetiti gdje ste u priči, 181 00:08:21,450 --> 00:08:23,620 ali na kraju dana, daje bilo koji broj elemenata, 182 00:08:23,620 --> 00:08:25,620 prvo se želite sortiranje lijeva polovica, onda pravo na pola, 183 00:08:25,620 --> 00:08:26,661 a zatim ih spojiti zajedno. 184 00:08:26,661 --> 00:08:28,630 Počnimo učiniti upravo to. 185 00:08:28,630 --> 00:08:30,170 Evo ulaz osam elemenata. 186 00:08:30,170 --> 00:08:31,910 Sada smo u potrazi na lijevoj polovici ovdje. 187 00:08:31,910 --> 00:08:33,720 Kako sortirati četiri elementa? 188 00:08:33,720 --> 00:08:35,610 Pa sam prvo sortirati lijevoj polovici. 189 00:08:35,610 --> 00:08:37,720 Sada kako mogu sortirati utakmice polovicu? 190 00:08:37,720 --> 00:08:39,419 Pa sam dao dva elementa. 191 00:08:39,419 --> 00:08:41,240 Tako ćemo razvrstati ova dva elementa. 192 00:08:41,240 --> 00:08:44,540 2 je veći od ili jednak 2, naravno. 193 00:08:44,540 --> 00:08:46,170 Tako da prvi slučaj ne primjenjuje. 194 00:08:46,170 --> 00:08:49,010 >> Tako sam sada morati sortirati lijevu polovica tih dvaju elemenata. 195 00:08:49,010 --> 00:08:50,870 Lijeva polovica, naravno, samo 4. 196 00:08:50,870 --> 00:08:54,020 Pa kako mogu sortirati popis jednog elementa? 197 00:08:54,020 --> 00:08:57,960 Pa sad, da je posebna baza slučaj do vrha, da tako kažem, vrijedi. 198 00:08:57,960 --> 00:09:01,470 1 manji od 2, i moj Popis je uistinu veličine 1. 199 00:09:01,470 --> 00:09:02,747 Dakle, samo sam se vratiti. 200 00:09:02,747 --> 00:09:03,580 Ja ne radim ništa. 201 00:09:03,580 --> 00:09:06,770 I doista, pogledajte što sam učinjeno, 4 već riješeno. 202 00:09:06,770 --> 00:09:09,220 Kao što sam već sam djelomično uspješna ovdje. 203 00:09:09,220 --> 00:09:11,750 >> Sada se to čini vrsta glupo zahtjevu, ali to je istina. 204 00:09:11,750 --> 00:09:13,700 4 je popis veličine 1. 205 00:09:13,700 --> 00:09:15,090 Već je riješeno. 206 00:09:15,090 --> 00:09:16,270 To je lijeva polovica. 207 00:09:16,270 --> 00:09:18,010 Sada sam sortirati desnu polovicu. 208 00:09:18,010 --> 00:09:22,310 Moj ulaz je jedan element, 8 Slično tome, već riješeno. 209 00:09:22,310 --> 00:09:25,170 Glupo je, također, ali opet, to osnovno načelo 210 00:09:25,170 --> 00:09:28,310 će nam omogućiti da izgrade sada na vrhu ove uspješno. 211 00:09:28,310 --> 00:09:32,260 4 razvrstani, 8. razvrstani sada što je to posljednji korak? 212 00:09:32,260 --> 00:09:35,330 Tako je treći i završni korak, bilo put ste sortiranja popisa, podsjetimo, 213 00:09:35,330 --> 00:09:38,310 je spojiti dvije polovice, lijeva i desna. 214 00:09:38,310 --> 00:09:39,900 Tako ćemo učiniti upravo to. 215 00:09:39,900 --> 00:09:41,940 Moja lijeva polovica je, naravno, 4. 216 00:09:41,940 --> 00:09:43,310 Moja desna polovica 8. 217 00:09:43,310 --> 00:09:44,100 >> Tako ćemo to učiniti. 218 00:09:44,100 --> 00:09:46,410 Prvo ću izdvojiti neke dodatne memorije, 219 00:09:46,410 --> 00:09:48,680 da ću ovdje predstavljam, samo kao sekundarni polje, 220 00:09:48,680 --> 00:09:49,660 to je dovoljno velika da stane to. 221 00:09:49,660 --> 00:09:52,243 Ali možete zamisliti širi da pravokutnik cijela duljina, 222 00:09:52,243 --> 00:09:53,290 ako nam je potrebno više kasnije. 223 00:09:53,290 --> 00:09:58,440 Kako sam se 4 i 8, i spajanje te dvije liste veličine 1 zajedno? 224 00:09:58,440 --> 00:10:00,270 Ovdje, također, vrlo jednostavna. 225 00:10:00,270 --> 00:10:03,300 4. na prvom mjestu, onda dolazi 8. 226 00:10:03,300 --> 00:10:07,130 Jer ako želim sortiranje lijeva polovica, onda pravo na pola, 227 00:10:07,130 --> 00:10:09,900 a zatim spojiti te dvije polovice zajedno, u sortiranog bi, 228 00:10:09,900 --> 00:10:11,940 4. na prvom mjestu, onda dolazi 8. 229 00:10:11,940 --> 00:10:15,810 >> Zato mi se čini da se napreduje, čak iako nisam učinio nikakav stvarni rad. 230 00:10:15,810 --> 00:10:17,800 Ali zapamtite gdje smo u priči. 231 00:10:17,800 --> 00:10:19,360 Mi smo izvorno je osam elemenata. 232 00:10:19,360 --> 00:10:21,480 Razvrstani smo lijevu polovicu, što je 4. 233 00:10:21,480 --> 00:10:24,450 Onda smo razvrstani lijevu polovicu lijeve polovice, što je 2. 234 00:10:24,450 --> 00:10:25,270 I ovdje mi ići. 235 00:10:25,270 --> 00:10:26,920 Mi smo učinili s tim korakom. 236 00:10:26,920 --> 00:10:29,930 >> Dakle, ako smo razvrstani ostavi pola 2, sada smo 237 00:10:29,930 --> 00:10:32,130 moraju sortirati pravu polovicu 2. 238 00:10:32,130 --> 00:10:35,710 Dakle, pravo na pola 2 je ove dvije vrijednosti ovdje, 6 i 2. 239 00:10:35,710 --> 00:10:40,620 Tako ćemo sada uzeti ulaz veličine 2, i sortirati lijevu polovicu, a zatim 240 00:10:40,620 --> 00:10:42,610 pravo na pola, a onda ih spojiti zajedno. 241 00:10:42,610 --> 00:10:45,722 Pa kako mogu sortirati popis veličini 1, koji sadrži samo broj 6? 242 00:10:45,722 --> 00:10:46,430 Ja sam već učinio. 243 00:10:46,430 --> 00:10:48,680 Taj popis veličine 1 je riješeno. 244 00:10:48,680 --> 00:10:52,140 >> Kako sortirati drugi popis Veličina 1, tzv desna polovica. 245 00:10:52,140 --> 00:10:54,690 Pa to je, također, već je riješeno. 246 00:10:54,690 --> 00:10:56,190 Broj 2 je sama. 247 00:10:56,190 --> 00:11:00,160 Tako sada imam dvije polovice, lijevo i Dobro, moram ih spojiti zajedno. 248 00:11:00,160 --> 00:11:01,800 Dopustite mi da si dati neki dodatni prostor. 249 00:11:01,800 --> 00:11:05,580 I staviti 2 tamo, zatim 6 tamo, čime 250 00:11:05,580 --> 00:11:10,740 sortiranje taj popis, lijevo i desno, i spajanje zajedno, u konačnici. 251 00:11:10,740 --> 00:11:12,160 Dakle, ja sam u malo boljoj formi. 252 00:11:12,160 --> 00:11:16,250 Nisam učinio, jer je očito 4, 8, 2, 6 nije konačan poredak koji želim. 253 00:11:16,250 --> 00:11:20,640 Ali ja sada imam dva popisa veličine 2, da su oba, odnosno, bili razvrstani. 254 00:11:20,640 --> 00:11:24,580 Pa sad, ako natrag u vaš um je oko, gdje je taj nas ostaviti? 255 00:11:24,580 --> 00:11:28,520 Počeo sam s osam elemenata, onda sam whittled ga na lijevu polovicu 4, 256 00:11:28,520 --> 00:11:31,386 zatim lijevu polovicu od 2, i onda pravo pola 2, 257 00:11:31,386 --> 00:11:34,510 Sam završio, dakle, sortiranje lijevi pola 2, a pravo pola 2, 258 00:11:34,510 --> 00:11:37,800 tako što je treći i posljednji korak ovdje? 259 00:11:37,800 --> 00:11:41,290 Moram spojiti zajedno dvije liste veličine 2. 260 00:11:41,290 --> 00:11:42,040 Tako ćemo ići naprijed. 261 00:11:42,040 --> 00:11:43,940 A na zaslonu ovdje, dati mi neke dodatne memorije, 262 00:11:43,940 --> 00:11:47,170 iako tehnički, primijetiti da imam dobio hrpu praznog prostora do vrha 263 00:11:47,170 --> 00:11:47,670 tamo. 264 00:11:47,670 --> 00:11:50,044 Ako želim biti posebno učinkovit prostor mudar, 265 00:11:50,044 --> 00:11:52,960 Samo sam mogao početi kreće elemente natrag i naprijed, gore i dolje. 266 00:11:52,960 --> 00:11:55,460 Ali samo za vizualne jasnoće, Idem ga staviti dolje, 267 00:11:55,460 --> 00:11:56,800 držati stvari lijepo i čisto. 268 00:11:56,800 --> 00:11:58,150 >> Dakle imam dva popisa veličine 2. 269 00:11:58,150 --> 00:11:59,770 Prvi popis je 4 i 8. 270 00:11:59,770 --> 00:12:01,500 Drugi popis je 2 i 6. 271 00:12:01,500 --> 00:12:03,950 Idemo spojiti one zajedno sortiranog bi. 272 00:12:03,950 --> 00:12:09,910 2, naravno, na prvom mjestu, zatim 4, zatim 6, a zatim 8. 273 00:12:09,910 --> 00:12:12,560 I sada mi se čini da je dobivanje negdje zanimljiv. 274 00:12:12,560 --> 00:12:15,720 Sada sam razvrstani polovica popis, i slučajno, to je 275 00:12:15,720 --> 00:12:18,650 sve čak brojeve, ali to je, doista, samo slučajnost. 276 00:12:18,650 --> 00:12:22,220 I sada razvrstani lijevu polovicu, tako da je 2, 4, 6 i 8. 277 00:12:22,220 --> 00:12:23,430 Ništa je iz reda. 278 00:12:23,430 --> 00:12:24,620 To se osjeća kao napredak. 279 00:12:24,620 --> 00:12:26,650 >> Sada se osjeća kao da sam Razgovarali zauvijek sada, 280 00:12:26,650 --> 00:12:29,850 pa što ostaje da se vidi je li to Algoritam je, doista, učinkovitiji. 281 00:12:29,850 --> 00:12:31,766 Ali ćemo kroz super metodično. 282 00:12:31,766 --> 00:12:34,060 Računalo, dakako, Učinit će to tako. 283 00:12:34,060 --> 00:12:34,840 Pa gdje smo mi? 284 00:12:34,840 --> 00:12:36,180 Počeli smo s osam elemenata. 285 00:12:36,180 --> 00:12:37,840 Ja razvrstani lijevu polovicu 4. 286 00:12:37,840 --> 00:12:39,290 Čini mi se da se radi s tim. 287 00:12:39,290 --> 00:12:42,535 Tako sada sljedeći korak je sortirati pravu polovinu 4. 288 00:12:42,535 --> 00:12:44,410 I to je dio možemo ići kroz malo više 289 00:12:44,410 --> 00:12:47,140 brzo, iako ste dobrodošli natrag ili pauziranja, samo 290 00:12:47,140 --> 00:12:49,910 mislim kroz njega na vlastitim tempom, ali ono 291 00:12:49,910 --> 00:12:53,290 smo sada je prilika da se napraviti isti algoritam na četiri 292 00:12:53,290 --> 00:12:54,380 različiti brojevi. 293 00:12:54,380 --> 00:12:57,740 >> Tako ćemo ići naprijed, i usredotočiti se na pravo na pola, koji smo ovdje. 294 00:12:57,740 --> 00:13:01,260 Lijeva polovica da pravo na pola, a sada 295 00:13:01,260 --> 00:13:04,560 lijeva polovica lijevo polovica tog desne polovice, 296 00:13:04,560 --> 00:13:08,030 i kako mogu sortirati popis veličini 1 sadrži samo broj 1? 297 00:13:08,030 --> 00:13:09,030 Već je učinjeno. 298 00:13:09,030 --> 00:13:11,830 Kako sam učiniti isto za popis veličine 1 sadrži samo 7? 299 00:13:11,830 --> 00:13:12,840 Već je učinjeno. 300 00:13:12,840 --> 00:13:16,790 Korak tri za Vezni onda se spojiti ova dva elementa 301 00:13:16,790 --> 00:13:20,889 u novi popis veličine 2, 1 i 7. 302 00:13:20,889 --> 00:13:23,180 Ne čini se da su učinili sve toliko zanimljiv rad. 303 00:13:23,180 --> 00:13:24,346 Idemo vidjeti što će se dogoditi sljedeći. 304 00:13:24,346 --> 00:13:29,210 Upravo sam razvrstani lijevu polovicu Pravo pola mog izvornog unosa. 305 00:13:29,210 --> 00:13:32,360 Sada ćemo razvrstati pravo pola, koji sadrži 5 i 3. 306 00:13:32,360 --> 00:13:35,740 Idemo ponovno pogledate lijevo pola, razvrstani, desna polovica, razvrstani, 307 00:13:35,740 --> 00:13:39,120 i spojiti to dvoje zajedno, u neki dodatni prostor, 308 00:13:39,120 --> 00:13:41,670 3 na prvom mjestu, onda dolazi 5. 309 00:13:41,670 --> 00:13:46,190 I tako sada smo razvrstani lijeva polovica desne polovice 310 00:13:46,190 --> 00:13:49,420 originalnog problema, i pravo polovice desne polovice 311 00:13:49,420 --> 00:13:50,800 originalnog problema. 312 00:13:50,800 --> 00:13:52,480 Što je treći i posljednji korak? 313 00:13:52,480 --> 00:13:54,854 Pa spojiti te dvije polovice zajedno. 314 00:13:54,854 --> 00:13:57,020 Zato mi dopustite da ja osobno dobiti neki dodatni prostor, ali, opet, sam 315 00:13:57,020 --> 00:13:58,699 može biti da koristite rezervni prostor do vrha. 316 00:13:58,699 --> 00:14:00,490 Ali ćemo zadržati to jednostavno vizualno. 317 00:14:00,490 --> 00:14:07,070 Dopustite mi stopiti sada 1, a zatim 3, a zatim 5, a zatim 7. 318 00:14:07,070 --> 00:14:10,740 Time ostavljajući me sada s desna polovica originalnog problema 319 00:14:10,740 --> 00:14:12,840 koji savršeno je riješeno. 320 00:14:12,840 --> 00:14:13,662 >> Dakle, ono što ostaje? 321 00:14:13,662 --> 00:14:16,120 Osjećam se kao da sam zadržati rekavši iste stvari opet, i opet, 322 00:14:16,120 --> 00:14:18,700 ali to je reflektirajuća od Činjenica da smo pomoću rekurzija. 323 00:14:18,700 --> 00:14:21,050 Proces korištenjem Algoritam opet, i opet, 324 00:14:21,050 --> 00:14:23,940 na manjim podskupova izvorni problem. 325 00:14:23,940 --> 00:14:27,580 Tako sam sada imaju lijeva razvrstani polovica originalnog problema. 326 00:14:27,580 --> 00:14:30,847 Imam pravo sortirani pol originalnog problema. 327 00:14:30,847 --> 00:14:32,180 Što je treći i završni korak? 328 00:14:32,180 --> 00:14:33,590 Oh, to je spajanje. 329 00:14:33,590 --> 00:14:34,480 Tako ćemo učiniti. 330 00:14:34,480 --> 00:14:36,420 Idemo izdvojiti neke dodatne memorije, ali Bože moj, što 331 00:14:36,420 --> 00:14:37,503 staviti ga bilo gdje sada. 332 00:14:37,503 --> 00:14:40,356 Imamo toliko prostora na raspolaganju nama, ali ćemo ga zadržati jednostavan. 333 00:14:40,356 --> 00:14:42,730 Umjesto ide natrag i naprijed s našim originalnim memorije, 334 00:14:42,730 --> 00:14:44,480 Ajmo to učiniti vizualno ovdje u nastavku, 335 00:14:44,480 --> 00:14:47,240 dovršiti spajanjem lijeva polovica i pravo na pola. 336 00:14:47,240 --> 00:14:49,279 >> Dakle spajanjem, što trebam učiniti? 337 00:14:49,279 --> 00:14:50,820 Želim uzeti elemente u redu. 338 00:14:50,820 --> 00:14:53,230 Dakle, gleda na lijevoj polovici, Vidim prvi broj 2. 339 00:14:53,230 --> 00:14:55,230 Gledam na desnoj polovici, Vidim prvi broj 340 00:14:55,230 --> 00:14:58,290 1, tako očito što Broj želim iščupati, 341 00:14:58,290 --> 00:15:00,430 i staviti prvi u mom konačni popis? 342 00:15:00,430 --> 00:15:01,449 Naravno, 1. 343 00:15:01,449 --> 00:15:02,990 Sada želim pitati to isto pitanje. 344 00:15:02,990 --> 00:15:05,040 Na lijevoj polovici, sam ipak je dobio broj 2. 345 00:15:05,040 --> 00:15:07,490 Na desnoj polovici, Imam broj 3. 346 00:15:07,490 --> 00:15:08,930 Koji želim odabrati? 347 00:15:08,930 --> 00:15:11,760 Naravno, broj 2 Sada obavijest kandidatima 348 00:15:11,760 --> 00:15:13,620 su 4 na lijevo, 3 na desnoj strani. 349 00:15:13,620 --> 00:15:15,020 Idemo, naravno, izabrati 3. 350 00:15:15,020 --> 00:15:18,020 Sada kandidati su 4 na lijeva, 5 na desnoj strani. 351 00:15:18,020 --> 00:15:19,460 Mi, naravno, izabrati 4. 352 00:15:19,460 --> 00:15:21,240 6 na lijevoj strani, 5 na desnoj strani. 353 00:15:21,240 --> 00:15:22,730 Mi, naravno, izaberite 5. 354 00:15:22,730 --> 00:15:25,020 6 na lijevoj strani, 7. na desnoj strani. 355 00:15:25,020 --> 00:15:29,320 Mi izabrati 6, a onda smo izaberite 7, a zatim biramo 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Tako veliki broj riječi kasnije smo su razvrstani ovaj popis osam elemenata 358 00:15:34,370 --> 00:15:38,450 u popisu jedan kroz osam, da je povećanje na svakom koraku, 359 00:15:38,450 --> 00:15:40,850 ali koliko je vremena nas odvesti na to. 360 00:15:40,850 --> 00:15:43,190 Pa imam namjerno položio stvari iz slikovno 361 00:15:43,190 --> 00:15:46,330 ovdje, tako da možemo vrsta vidjeti ili cijeniti podjelu 362 00:15:46,330 --> 00:15:49,060 u osvajanju koji je bio događa. 363 00:15:49,060 --> 00:15:52,830 >> Doista, ako se osvrnem na svjetlu, Ostavio sam sve ove iscrtanih linija 364 00:15:52,830 --> 00:15:55,660 u držačima mjestu, možete, vrsta, vidi, u obrnutom redoslijedu, 365 00:15:55,660 --> 00:15:58,800 ako vrsta osvrnuti na povijest je sada, moj originalni popis 366 00:15:58,800 --> 00:16:00,250 je, naravno, veličine 8. 367 00:16:00,250 --> 00:16:03,480 A onda je prije, bio sam bave dva lista veličine 4, 368 00:16:03,480 --> 00:16:08,400 a onda četiri liste veličine 2, a zatim osam popisi veličine 1. 369 00:16:08,400 --> 00:16:10,151 >> Pa što to, vrsta, podsjetiti vas na? 370 00:16:10,151 --> 00:16:11,858 Pa, zapravo, bilo koji od algoritmi smo 371 00:16:11,858 --> 00:16:14,430 pogledao do sada gdje smo podijeli i podijelite i podjela, 372 00:16:14,430 --> 00:16:19,500 zadržati vlasništvo stvari opet, i opet, rezultira u ovoj općoj ideji. 373 00:16:19,500 --> 00:16:23,100 I tako postoji nešto logaritamska događa ovdje. 374 00:16:23,100 --> 00:16:26,790 I to nije sasvim dnevnik n, ali tu je logaritamska komponenta 375 00:16:26,790 --> 00:16:28,280 na ono što smo upravo učinili. 376 00:16:28,280 --> 00:16:31,570 >> Sada ćemo razmotriti kako da se zapravo jest. 377 00:16:31,570 --> 00:16:34,481 Dakle, prijavite n, ponovno je velik vrijeme rada, 378 00:16:34,481 --> 00:16:36,980 kad smo radili nešto slično binarno pretraživanje, kao što smo sada ga zovu, 379 00:16:36,980 --> 00:16:40,090 podjela pa vladaj strategija putem koje smo našli Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Sada tehnički. 381 00:16:41,020 --> 00:16:43,640 To je dnevnik baza 2 n, čak iako u većini math klase, 382 00:16:43,640 --> 00:16:45,770 10 je obično točka koju pretpostavljamo. 383 00:16:45,770 --> 00:16:48,940 No, računalni znanstvenici gotovo uvijek razmišljati i razgovarati u smislu bazi 2, 384 00:16:48,940 --> 00:16:52,569 pa smo uglavnom samo reći dnevnik N, umjesto log baze 2 n, 385 00:16:52,569 --> 00:16:55,110 ali oni su upravo jedan te Isto u svijetu računala 386 00:16:55,110 --> 00:16:57,234 znanost, a kao usput, postoji konstantan faktor 387 00:16:57,234 --> 00:17:01,070 Razlika između ta dva, tako da je Ionako sporan, za više formalnih razloga. 388 00:17:01,070 --> 00:17:04,520 >> No, za sada, ono što mi je stalo o je ovaj primjer. 389 00:17:04,520 --> 00:17:08,520 Dakle, nemojmo se pokazati primjerom, ali u najmanje koristiti primjer brojeva 390 00:17:08,520 --> 00:17:10,730 pri ruci kao provjera razum, ako hoćete. 391 00:17:10,730 --> 00:17:14,510 Tako je prije formula je dnevnik baze 2 n, ali ono što je n u ovom slučaju. 392 00:17:14,510 --> 00:17:18,526 Imao sam n izvorne brojeve, ili 8 od izvornog broja posebno. 393 00:17:18,526 --> 00:17:20,359 Sada je bio malo dok je, ali ja sam prilično 394 00:17:20,359 --> 00:17:25,300 je li zapisnik baza 2 vrijednosti 8 je 3, 395 00:17:25,300 --> 00:17:29,630 i doista, što je lijepo o kako je da 3 je upravo broj puta 396 00:17:29,630 --> 00:17:33,320 koje možete podijeliti popis duljine 8 opet, i opet, 397 00:17:33,320 --> 00:17:36,160 i opet, sve dok ste napustili s popisima samo veličine 1. 398 00:17:36,160 --> 00:17:36,660 Pravo? 399 00:17:36,660 --> 00:17:40,790 8 ide na 4, ide na 2, ide do 1, a to je 400 00:17:40,790 --> 00:17:43,470 odražava upravo to Slika imali smo samo trenutak prije. 401 00:17:43,470 --> 00:17:47,160 Dakle, malo razum provjeriti gdje logaritam zapravo uključeni. 402 00:17:47,160 --> 00:17:50,180 >> Pa sad, što drugo je uključen ovdje? n. 403 00:17:50,180 --> 00:17:53,440 Dakle, primijetite da je svaki Vrijeme sam podijeliti popis, 404 00:17:53,440 --> 00:17:58,260 iako u obrnutom redoslijedu u povijesti ovdje, ja još uvijek radio n stvari. 405 00:17:58,260 --> 00:18:02,320 To spajanjem korak zahtijeva da Dodirnem svaki od brojeva, 406 00:18:02,320 --> 00:18:05,060 kako bi ga gurnite u njegov odgovarajuće mjesto. 407 00:18:05,060 --> 00:18:10,760 Dakle, iako je visina ovog Dijagram je veličina log n n ili 3, 408 00:18:10,760 --> 00:18:13,860 posebno, drugim riječima, Ja sam tri divizije ovdje. 409 00:18:13,860 --> 00:18:18,800 Koliko posla sam učinio vodoravno uz ovaj grafikonu svaki put? 410 00:18:18,800 --> 00:18:21,110 >> Pa, ja sam n koraka raditi, jer ako imam 411 00:18:21,110 --> 00:18:24,080 dobio četiri elementa i četiri elementa, i moram ih spojiti zajedno. 412 00:18:24,080 --> 00:18:26,040 Moram proći kroz ove četiri i to četiri, 413 00:18:26,040 --> 00:18:28,123 konačnici ih spojiti natrag u osam elemenata. 414 00:18:28,123 --> 00:18:32,182 Ako s druge strane imam osam prstiju ovdje, što ja ne, a osam 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Ako sam dobio četiri prsta ovdje, 416 00:18:34,390 --> 00:18:37,380 što mi je činiti, četiri prsta ovdje, što mi je činiti, 417 00:18:37,380 --> 00:18:40,590 zatim da je ista Primjer kao i prije, ako mi je činiti 418 00:18:40,590 --> 00:18:44,010 ima osam prstiju iako u Ukupno, koji se mogu, vrsta, učiniti. 419 00:18:44,010 --> 00:18:47,950 Ja točno možete učiniti ovdje, onda ja mogu sigurno 420 00:18:47,950 --> 00:18:50,370 spojiti sve te liste veličine 1 zajedno. 421 00:18:50,370 --> 00:18:54,050 Ali ja sigurno morati gledati na svakom elementu točno jednom. 422 00:18:54,050 --> 00:18:59,640 Tako je visina tog procesa je zapisnik nje, širina tog procesa, da se tako izrazim, 423 00:18:59,640 --> 00:19:02,490 n, tako da ono što čini da, u konačnici, je 424 00:19:02,490 --> 00:19:06,470 trčanje vrijeme veličine n puta prijavite nje. 425 00:19:06,470 --> 00:19:08,977 >> Drugim riječima, mi podijeljeni popis, zapisnik n puta, 426 00:19:08,977 --> 00:19:11,810 ali svaki put smo to učinili, imali smo dotaknuti svaki od elemenata 427 00:19:11,810 --> 00:19:13,560 kako bi ih spojiti svi zajedno, što 428 00:19:13,560 --> 00:19:18,120 bio je N korak, tako da imamo n puta prijaviti nje, ili kao računalni znanstvenik će reći, 429 00:19:18,120 --> 00:19:20,380 asimptotski, koji će biti velika riječ 430 00:19:20,380 --> 00:19:22,810 opisati gornja vezan na trčanje vremena, 431 00:19:22,810 --> 00:19:28,010 smo prikazivati ​​u velikom o log n vrijeme, da se tako izrazim. 432 00:19:28,010 --> 00:19:31,510 >> A ovo je značajan, jer je sjetiti što su trčanje puta 433 00:19:31,510 --> 00:19:34,120 s mjehurića vrsta i odabir sortiranje i umetanje sortiranje, 434 00:19:34,120 --> 00:19:38,200 pa čak i nekoliko drugih koje postoje, n na kvadrat bio gdje smo bili na. 435 00:19:38,200 --> 00:19:39,990 A možete, vrsta, vidjeti ovdje. 436 00:19:39,990 --> 00:19:45,720 Ako je n kvadrat očito n puta nje, ali ovdje imamo n puta prijaviti nje, 437 00:19:45,720 --> 00:19:48,770 a mi već znamo iz tjedna nula, da je zapisnik nje je logaritamska, 438 00:19:48,770 --> 00:19:50,550 je bolje nego nešto linearno. 439 00:19:50,550 --> 00:19:52,930 Uostalom, prisjetiti sliku sa crveno i žuto 440 00:19:52,930 --> 00:19:56,500 i zelene crte koje zagrabiše je zelena logaritamska linija bila znatno niža. 441 00:19:56,500 --> 00:20:00,920 I zato, mnogo bolje i brže od ravne žute i crvene linije, 442 00:20:00,920 --> 00:20:05,900 n puta prijavite nje je, doista, bolje od n puta n ili n na kvadrat. 443 00:20:05,900 --> 00:20:09,110 >> Dakle, izgleda da imamo identificirati algoritam spajanje 444 00:20:09,110 --> 00:20:11,870 vrsta koja radi u mnogo brže vrijeme, i doista, 445 00:20:11,870 --> 00:20:16,560 Zato, ranije ovog tjedna, kada je Vidjeli smo da je natjecanje između mjehura 446 00:20:16,560 --> 00:20:20,750 sortiranje, odabir vrsta, i spajanje vrsta, spajanje vrsta stvarno, stvarno pobijedio. 447 00:20:20,750 --> 00:20:23,660 I doista, nismo ni čekati za mjehur vrsta i odabir vrste 448 00:20:23,660 --> 00:20:24,790 Završiti. 449 00:20:24,790 --> 00:20:27,410 >> Sada ćemo uzeti jednu drugu sredinu u ovom, od nešto više 450 00:20:27,410 --> 00:20:31,030 formalno perspektive, samo u slučaj, to bolje rezonira 451 00:20:31,030 --> 00:20:33,380 nego da više razine rasprave. 452 00:20:33,380 --> 00:20:34,880 Dakle ovdje je algoritam ponovno. 453 00:20:34,880 --> 00:20:36,770 Idemo se pitamo, što je trčanje vrijeme 454 00:20:36,770 --> 00:20:39,287 je to algoritmima različite korake? 455 00:20:39,287 --> 00:20:41,620 Budimo podijeliti u prvi slučaj i drugi slučaj. 456 00:20:41,620 --> 00:20:46,280 IF i drugo u slučaju da, Ako je n manji od 2, samo se vrati. 457 00:20:46,280 --> 00:20:47,580 Osjećaj konstantne vrijeme. 458 00:20:47,580 --> 00:20:50,970 To je, vrsta, kao i dva koraka, Ako je n manji od 2, a zatim se vratiti. 459 00:20:50,970 --> 00:20:54,580 No, kao što smo rekli u ponedjeljak, vremenska konstanta, ili velika o 1, 460 00:20:54,580 --> 00:20:57,130 mogu biti dva koraka, tri koraka, čak 1.000 koraka. 461 00:20:57,130 --> 00:20:59,870 Ono što je važno je da je konstantan broj koraka. 462 00:20:59,870 --> 00:21:03,240 Dakle žuti istaknuo pseudokod Ovdje radi u, mi ćemo ga nazvati, 463 00:21:03,240 --> 00:21:04,490 vremenska konstanta. 464 00:21:04,490 --> 00:21:06,780 Tako više formalno i idemo to-- ovo 465 00:21:06,780 --> 00:21:09,910 biti će u kojoj mjeri smo formalizirati to pravo now-- T n, 466 00:21:09,910 --> 00:21:15,030 Vrijeme rada problema koji traje n somethings kao ulaz, 467 00:21:15,030 --> 00:21:19,150 jednako velika o jedan, Ako je n manji od 2. 468 00:21:19,150 --> 00:21:20,640 Dakle, to je uvjetno na to. 469 00:21:20,640 --> 00:21:24,150 Dakle, da bude jasno, ako je n manji od 2, imamo vrlo kratak popis, a zatim 470 00:21:24,150 --> 00:21:29,151 vrijeme rada, T n, gdje je n 1 ili 0, u ovom vrlo konkretnom slučaju, 471 00:21:29,151 --> 00:21:30,650 to samo će biti konstantna vrijeme. 472 00:21:30,650 --> 00:21:32,691 To se događa da se jedan korak, dva koraka, bilo što. 473 00:21:32,691 --> 00:21:33,950 To je fiksni broj koraka. 474 00:21:33,950 --> 00:21:38,840 >> Tako je sočna dio mora sigurno biti u Drugi slučaj u pseudokod. 475 00:21:38,840 --> 00:21:40,220 JOŠ slučaj. 476 00:21:40,220 --> 00:21:44,870 Sortiraj lijeva polovica elemenata, sortiranje pravo pola elemenata, spajanja razvrstanih polovice. 477 00:21:44,870 --> 00:21:46,800 Koliko je svaki od tih koraka poduzeti? 478 00:21:46,800 --> 00:21:49,780 Pa, ako je pokrenut Vrijeme za sortiranje n elemenata 479 00:21:49,780 --> 00:21:53,010 je, nazovimo ga vrlo općenito, T n, 480 00:21:53,010 --> 00:21:55,500 zatim sortiranje lijevu polovina elemenata 481 00:21:55,500 --> 00:21:59,720 je vrsta, kao što je rekao, T n podijeljena 2, 482 00:21:59,720 --> 00:22:03,000 i slično sortiranja desnu polovicu elemenata je vrsta, kao što je rekao, 483 00:22:03,000 --> 00:22:06,974 T n podijeljen 2, a potom spajanjem sortirani polovice. 484 00:22:06,974 --> 00:22:08,890 Pa, ako sam dobio neke broj elemenata ovdje, 485 00:22:08,890 --> 00:22:11,230 kao i četiri, i neki broj elemenata ovdje, kao i četiri, 486 00:22:11,230 --> 00:22:14,650 i moram spojiti svaku od ove četiri u, a svaki od njih četiri u, jedan 487 00:22:14,650 --> 00:22:17,160 nakon druge, tako da se konačnici Imam osam elemenata. 488 00:22:17,160 --> 00:22:20,230 To se osjeća kao da je veliki o od n koraka? 489 00:22:20,230 --> 00:22:23,500 Ako imam n prste i svaki od ih mora spojiti u mjestu, 490 00:22:23,500 --> 00:22:25,270 to je kao da još n koraka. 491 00:22:25,270 --> 00:22:27,360 >> Dakle, istina formulaically, možemo izraziti, 492 00:22:27,360 --> 00:22:29,960 doduše malo scarily na prvi pogled, ali to je nešto 493 00:22:29,960 --> 00:22:31,600 koji bilježi upravo tu logiku. 494 00:22:31,600 --> 00:22:35,710 Računanje vremena, T n, ako je N je veća od ili jednaka 2. 495 00:22:35,710 --> 00:22:42,500 U tom slučaju, na drugome slučaju, T n podijeljen 2, plus T od N podijeljen 2, 496 00:22:42,500 --> 00:22:45,320 uz veliki o n, neki linearna broj koraka, 497 00:22:45,320 --> 00:22:51,630 možda točno n, možda 2 puta nje, ali to je otprilike, redoslijed n. 498 00:22:51,630 --> 00:22:54,060 Tako da je, također, kako možemo izraziti formulaically. 499 00:22:54,060 --> 00:22:56,809 Sada ne bi znao to, osim ako ste ga snimio u svom umu, 500 00:22:56,809 --> 00:22:58,710 ili ga potražiti u natrag udžbenika, koji 501 00:22:58,710 --> 00:23:00,501 možda malo varati list na kraju, 502 00:23:00,501 --> 00:23:03,940 ali to je, doista, će daju nam veliki o n log n, 503 00:23:03,940 --> 00:23:06,620 jer ponavljanje da vidite ovdje na zaslonu, 504 00:23:06,620 --> 00:23:09,550 ako stvarno to učinio prema van, beskonačan broj primjera, 505 00:23:09,550 --> 00:23:13,000 ili si to učinio formulaically, što bi vidjeti da je to, jer ove formule 506 00:23:13,000 --> 00:23:17,100 Sam je rekurzivna, s t nje zbog nečega na desnoj strani, 507 00:23:17,100 --> 00:23:21,680 a t n više na lijevoj strani, to može zapravo se izrazio, u konačnici, 508 00:23:21,680 --> 00:23:24,339 kao velika go n log n. 509 00:23:24,339 --> 00:23:26,130 Ako nije uvjeren, da je to u redu za sada, samo 510 00:23:26,130 --> 00:23:28,960 se na vjeri, da je to, zapravo, što je to povratak vodi, 511 00:23:28,960 --> 00:23:31,780 ali to je samo nešto više od matematički pristup u potrazi 512 00:23:31,780 --> 00:23:36,520 u trajanju od pisma koje vrste na temelju svojih pseudokod sama. 513 00:23:36,520 --> 00:23:39,030 >> Sada ćemo uzeti malo odušak od svega toga, 514 00:23:39,030 --> 00:23:41,710 i uzeti pogledati određeni bivši senator, koji je 515 00:23:41,710 --> 00:23:44,260 Možda izgleda malo poznato, koji je sjeo s Googleovim Ericom 516 00:23:44,260 --> 00:23:48,410 Schmidt, prije nekog vremena, za intervju na pozornici, ispred cijela hrpa 517 00:23:48,410 --> 00:23:53,710 ljudi, govori o kraju tema, to je prilično sada poznato. 518 00:23:53,710 --> 00:23:54,575 Idemo pogledati. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Sada senator, ti si ovdje na Googleu, 521 00:24:03,890 --> 00:24:09,490 i volim misliti na Predsjedništvo kao intervju za posao. 522 00:24:09,490 --> 00:24:11,712 Sada je teško dobiti posao kao predsjednika. 523 00:24:11,712 --> 00:24:12,670 Predsjednik Obama: Tako je. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: A ti si učiniti [nečujan] sada. 525 00:24:13,940 --> 00:24:15,523 Također je teško dobiti posao u Googleu. 526 00:24:15,523 --> 00:24:17,700 Predsjednik Obama: Tako je. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Imamo pitanja, i tražimo naši kandidati pitanja, 528 00:24:21,330 --> 00:24:24,310 i to je jedan od Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> Predsjednik Obama: U redu. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Što? 531 00:24:27,005 --> 00:24:28,130 Vi mislite Šalim? 532 00:24:28,130 --> 00:24:30,590 To je upravo ovdje. 533 00:24:30,590 --> 00:24:33,490 Koji je najučinkovitiji način za sortirati milijun 32 bitni prirodni brojevi? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> Predsjednik Obama: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Ponekad, možda Žao mi je, maybe-- 537 00:24:41,020 --> 00:24:42,750 Predsjednik Obama: Ne, ne, ne, ne, ne, ja think-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: To nije it-- 539 00:24:43,240 --> 00:24:45,430 Predsjednik Obama: ja mislim, mislim mjehurić 540 00:24:45,430 --> 00:24:46,875 sortirati bi pogrešan način da ide. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Hajde. 543 00:24:50,535 --> 00:24:52,200 Tko ga je to rekao? 544 00:24:52,200 --> 00:24:54,020 U REDU. 545 00:24:54,020 --> 00:24:55,590 Nisam računalo znanost on-- 546 00:24:55,590 --> 00:24:58,986 >> Predsjednik Obama: Imamo dobio naše špijune tamo. 547 00:24:58,986 --> 00:24:59,860 PROFESOR: U redu. 548 00:24:59,860 --> 00:25:03,370 Ostavimo iza nas sada teorijski svijet algoritama 549 00:25:03,370 --> 00:25:06,520 u asimptotske analize njihove, i vratiti se na nekim temama 550 00:25:06,520 --> 00:25:09,940 iz tjedna nula i jedan, i početi ukloniti neke trening kotačima, 551 00:25:09,940 --> 00:25:10,450 ako hoćete. 552 00:25:10,450 --> 00:25:13,241 Tako da stvarno razumiju u konačnici od temelja, što je 553 00:25:13,241 --> 00:25:16,805 događa ispod haube, kada vas napisati, sastaviti, i izvršavanje programa. 554 00:25:16,805 --> 00:25:19,680 Podsjetimo posebno, da je to Prvi C programa smo pogledali, 555 00:25:19,680 --> 00:25:22,840 kanonski, jednostavan program sorti, relativno govoreći, 556 00:25:22,840 --> 00:25:24,620 u kojoj, ispisuje, Hello World. 557 00:25:24,620 --> 00:25:27,610 I podsjetiti da je sam rekao, proces da izvorni kod prolazi kroz 558 00:25:27,610 --> 00:25:28,430 je upravo to. 559 00:25:28,430 --> 00:25:31,180 Možete uzeti izvorni kod, prolaze to kroz prevodilac, kao što su jeka, 560 00:25:31,180 --> 00:25:34,650 i kako dolazi objektnog koda, koji može izgledati ovako, nula i jedinica 561 00:25:34,650 --> 00:25:37,880 da računalo CPU, središnja procesorska jedinica ili mozga, 562 00:25:37,880 --> 00:25:39,760 konačnici razumije. 563 00:25:39,760 --> 00:25:42,460 >> Ispada da to je malo je pojednostavljivanje, 564 00:25:42,460 --> 00:25:44,480 da smo sada u Položaj zafrkavati osim 565 00:25:44,480 --> 00:25:46,720 razumjeti što se stvarno bio događa ispod haube 566 00:25:46,720 --> 00:25:48,600 svaki put kada pokrenete Jeka, ili općenitije, 567 00:25:48,600 --> 00:25:53,040 svaki put kad bi program, pomoću Napravite CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Konkretno, takve stvari ovaj prvi je generiran, 569 00:25:56,760 --> 00:25:58,684 kada ste prvi sastaviti svoj program. 570 00:25:58,684 --> 00:26:00,600 Drugim riječima, kada se ti uzmite izvorni kod 571 00:26:00,600 --> 00:26:04,390 i sastaviti ga, što je prvi se reproduciraju po zveket 572 00:26:04,390 --> 00:26:06,370 je nešto poznato kao montaže kod. 573 00:26:06,370 --> 00:26:08,990 A u stvari, to izgleda upravo ovako. 574 00:26:08,990 --> 00:26:11,170 >> Ran sam naredbu na naredbenog retka ranije. 575 00:26:11,170 --> 00:26:16,260 Zveket DASH Capital s hello.c, a to stvorio datoteku 576 00:26:16,260 --> 00:26:19,490 za mene zove hello.s, unutar kojih su se upravo 577 00:26:19,490 --> 00:26:22,290 ti sadržaji, i malo više iznad i malo više u nastavku, 578 00:26:22,290 --> 00:26:25,080 ali sam stavio juiciest informacija ovdje na zaslonu. 579 00:26:25,080 --> 00:26:29,190 I ako malo bolje pogledate, vidjet ćete barem nekoliko poznatih riječi. 580 00:26:29,190 --> 00:26:31,330 Imamo glavni na vrhu. 581 00:26:31,330 --> 00:26:35,140 Mi smo printf dolje u sredini. 582 00:26:35,140 --> 00:26:38,670 I mi također imaju Hello World backslash nje u navodnike dolje. 583 00:26:38,670 --> 00:26:42,450 >> A sve ostalo ovdje je uputa vrlo niskoj razini 584 00:26:42,450 --> 00:26:45,500 da računalo CPU razumije. 585 00:26:45,500 --> 00:26:50,090 CPU upute koje se kreću memorije oko, da opterećenje žice iz memorije, 586 00:26:50,090 --> 00:26:52,750 i na kraju, za ispis stvari na zaslonu. 587 00:26:52,750 --> 00:26:56,780 Sada što se događa, iako nakon ovaj zbor broj se generira? 588 00:26:56,780 --> 00:26:59,964 Na kraju, vi, doista, dalje generirati objektnog koda. 589 00:26:59,964 --> 00:27:02,630 Ali koraci koje su stvarno događa ispod haube 590 00:27:02,630 --> 00:27:04,180 izgleda malo više kao što je ovaj. 591 00:27:04,180 --> 00:27:08,390 Izvorni kod postaje skupština koda, koji tada postaje predmet broj, 592 00:27:08,390 --> 00:27:11,930 a operativna riječi ovdje su da, kada sastaviti svoj izvorni kod, 593 00:27:11,930 --> 00:27:16,300 kako dolazi sklop kod, a zatim kad skupite svoju montaže kod, 594 00:27:16,300 --> 00:27:17,800 kako dolazi objektnog koda. 595 00:27:17,800 --> 00:27:20,360 >> Sada zveket je super sofisticiran, kao puno prevodiocima, 596 00:27:20,360 --> 00:27:23,151 i to sve od tih koraka zajedno, i to ne mora nužno 597 00:27:23,151 --> 00:27:25,360 Izlaz bilo intermedijer datoteke koje možete čak i vidjeti. 598 00:27:25,360 --> 00:27:28,400 To samo sastavlja stvari, koja je opći pojam koji 599 00:27:28,400 --> 00:27:30,000 opisuje cijeli taj proces. 600 00:27:30,000 --> 00:27:32,000 Ali ako stvarno želite Posebno se, ima 601 00:27:32,000 --> 00:27:34,330 puno više događa tamo. 602 00:27:34,330 --> 00:27:38,860 >> Ali neka se također uzeti u obzir da čak i sada da super jednostavan program, hello.c, 603 00:27:38,860 --> 00:27:40,540 naziva funkcija. 604 00:27:40,540 --> 00:27:41,870 To se zove printf. 605 00:27:41,870 --> 00:27:46,900 Ali nisam pisati printf, doista, koji dolazi s c, da se tako izrazim. 606 00:27:46,900 --> 00:27:51,139 To je funkcija Sjetite se da je proglasio je u standardnoj io.h, koji 607 00:27:51,139 --> 00:27:53,180 je zaglavlje datoteke, što je tema ćemo zapravo 608 00:27:53,180 --> 00:27:55,780 zaroniti u dublje prije dugo. 609 00:27:55,780 --> 00:27:58,000 No, zaglavlje datoteke obično popraćena 610 00:27:58,000 --> 00:28:02,920 po koda datoteke, izvorni kod datoteke, tako slično postoji standardna io.h. 611 00:28:02,920 --> 00:28:05,930 >> Negdje prije, netko, ili neciji, napisao 612 00:28:05,930 --> 00:28:11,040 datoteka se zove standardni io.c u koji su stvarni definicije, 613 00:28:11,040 --> 00:28:15,220 ili implementacije printf, i grozdova suhog druge funkcije, 614 00:28:15,220 --> 00:28:16,870 zapravo napisao. 615 00:28:16,870 --> 00:28:22,140 Pa s obzirom da je, ako uzmemo u obzir potrebe Ovdje na lijevoj strani, hello.c, da kada 616 00:28:22,140 --> 00:28:26,250 sastavio, daje nam hello.s, čak i ako Zveket ne smetaju uštedu na mjestu 617 00:28:26,250 --> 00:28:31,360 možemo ga vidjeti, i da je Skupština kod dobiva sklopljeni u hello.o, koji 618 00:28:31,360 --> 00:28:34,630 je, doista, zadani naziv dao kad god sastaviti izvora 619 00:28:34,630 --> 00:28:39,350 kod u objektnom kodu, ali nisu sasvim spremni da ga izvrši, ali, 620 00:28:39,350 --> 00:28:41,460 jer još jedan korak mora dogoditi, te ima 621 00:28:41,460 --> 00:28:44,440 se događa u posljednjih nekoliko tjedana, možda i bez znanja vama. 622 00:28:44,440 --> 00:28:47,290 >> Naime negdje u CS50 IDE, i to, 623 00:28:47,290 --> 00:28:49,870 također, će biti malo od pojednostavljivanje na trenutak, 624 00:28:49,870 --> 00:28:54,670 postoji, ili je bio davno, datoteka se zove standardni io.c, 625 00:28:54,670 --> 00:28:58,440 da je netko sastavio u Standardni io.s ili ekvivalent, 626 00:28:58,440 --> 00:29:02,010 da je netko tada okupio u standardnom io.o, 627 00:29:02,010 --> 00:29:04,600 ili ispada u malo drugačiji datoteka 628 00:29:04,600 --> 00:29:07,220 format koji može imati drugačiji ekstenzija datoteke uopce, 629 00:29:07,220 --> 00:29:11,720 ali u teoriji i konceptualno, točno one korake morao dogoditi u nekom obliku. 630 00:29:11,720 --> 00:29:14,060 Što će reći, da je sada kad pišem programa, 631 00:29:14,060 --> 00:29:17,870 hello.c, koji samo govori, halo svijet, i ja sam koristeći tuđe šifru 632 00:29:17,870 --> 00:29:22,480 kao printf, koji je nekada na stvaranju Vrijeme u datoteci pod nazivom standardni io.c, 633 00:29:22,480 --> 00:29:26,390 onda nekako moram uzeti moj Šifra objekta, moji nula i jedinica, 634 00:29:26,390 --> 00:29:29,260 i te osobe predmet kod, ili nula i jedinica, 635 00:29:29,260 --> 00:29:34,970 i nekako ih povezati zajedno u jedan konačni datoteku, pod nazivom Pozdrav, da 636 00:29:34,970 --> 00:29:38,070 ima sve nula i one iz mog glavne funkcije, 637 00:29:38,070 --> 00:29:40,830 i sve nule i one za printf. 638 00:29:40,830 --> 00:29:44,900 >> I doista, da je prošle proces zove, povezujući svoj objektnog koda. 639 00:29:44,900 --> 00:29:47,490 Od kojih je izlaz je izvršna datoteka. 640 00:29:47,490 --> 00:29:49,780 Tako je u pravednosti, u kraju dana, ništa 641 00:29:49,780 --> 00:29:52,660 se promijenilo od tjedan jednom, kad smo prvi počeo sastavljanju programa. 642 00:29:52,660 --> 00:29:55,200 Doista, sve to je događa ispod haube, 643 00:29:55,200 --> 00:29:57,241 ali sada smo u poziciji Gdje možemo zapravo 644 00:29:57,241 --> 00:29:58,794 zafrkavati osim ove različite korake. 645 00:29:58,794 --> 00:30:00,710 I doista, na kraju dana, još smo 646 00:30:00,710 --> 00:30:04,480 otišao s nula i jedinica, koje je zapravo velika prikazali sada 647 00:30:04,480 --> 00:30:08,620 na drugi sposobnosti C, kako nismo imali utjecati najvjerojatnije 648 00:30:08,620 --> 00:30:11,250 do danas, poznat kao bitovni operatori. 649 00:30:11,250 --> 00:30:15,220 Drugim riječima, do sada, bilo kada imamo bavila podataka u C ili varijabli u C, 650 00:30:15,220 --> 00:30:17,660 imali smo stvari kao što su znakova i pluta i ins 651 00:30:17,660 --> 00:30:21,990 i čezne i parovima i slično, ali svi oni su najmanje osam bitova. 652 00:30:21,990 --> 00:30:25,550 Nikada nismo još bili u mogućnosti manipulirati pojedinačne bitove, 653 00:30:25,550 --> 00:30:28,970 iako pojedinog malo, mi Znate, može predstavljati 0 i 1. 654 00:30:28,970 --> 00:30:32,640 Sada ispada da je u C, što možete dobiti pristup pojedinim bitova, 655 00:30:32,640 --> 00:30:35,530 ako znate sintaksu, s kojom se dobiti na njih. 656 00:30:35,530 --> 00:30:38,010 >> Tako ćemo pogledati na bitovima operatora. 657 00:30:38,010 --> 00:30:41,700 Dakle ovdje na slici su neke simbole koji smo, vrsta, vrsta, vidjela. 658 00:30:41,700 --> 00:30:45,580 Vidim ampersand, vertikalni bar, i neki drugi, kao i, 659 00:30:45,580 --> 00:30:49,430 i podsjetiti da ampersand ampersand je nešto što smo vidjeli prije. 660 00:30:49,430 --> 00:30:54,060 Logično i operatora, gdje imate Njih dvoje zajedno, ili logički ILI 661 00:30:54,060 --> 00:30:56,300 Operator, gdje vas imaju dvije okomite pruge. 662 00:30:56,300 --> 00:31:00,550 Bitovni operatori, koji ćemo vidi djeluju na bitova pojedinačno, 663 00:31:00,550 --> 00:31:03,810 samo koristiti jedan ampersand, A jedna okomita traka je znak za umetanje simbola 664 00:31:03,810 --> 00:31:06,620 dolazi sljedeći, malo tilda, a zatim otišao 665 00:31:06,620 --> 00:31:08,990 nosač napustio nosač, ili Pravo nosač pravo nosač. 666 00:31:08,990 --> 00:31:10,770 Svaki od njih ima različita značenja. 667 00:31:10,770 --> 00:31:11,950 >> U stvari, neka je pogledati. 668 00:31:11,950 --> 00:31:16,560 Idemo stara škola i danas, i uporaba zaslon osjetljiv na dodir od prošle, 669 00:31:16,560 --> 00:31:18,002 poznat kao bijela ploča. 670 00:31:18,002 --> 00:31:19,710 I to bijela ploča će nam omogućiti 671 00:31:19,710 --> 00:31:27,360 izraziti neke prilično jednostavne simbole, odnosno neke prilično jednostavne formule, 672 00:31:27,360 --> 00:31:29,560 kako možemo onda u konačnici poluge, kako bi 673 00:31:29,560 --> 00:31:33,230 pristupiti individualno bitova unutar programa C. 674 00:31:33,230 --> 00:31:34,480 Drugim riječima, učinimo to. 675 00:31:34,480 --> 00:31:37,080 Neka prvi razgovor za Trenutak oko znakom, 676 00:31:37,080 --> 00:31:39,560 što je bitovni AND operator. 677 00:31:39,560 --> 00:31:42,130 Drugim riječima, to je operator koji omogućuje 678 00:31:42,130 --> 00:31:45,930 ja imati varijablu lijevu tipično, varijabilna i desni, 679 00:31:45,930 --> 00:31:50,640 ili pojedinačna vrijednost, da ako mi i ih zajedno, daje mi konačni rezultat. 680 00:31:50,640 --> 00:31:51,560 Pa što mislim? 681 00:31:51,560 --> 00:31:54,840 Ako se u programu, imate varijablu koji sprema jedan od tih vrijednosti, 682 00:31:54,840 --> 00:31:58,000 ili ćemo ga zadržati jednostavan i jednostavno napisati nula i jedinica pojedinačno, 683 00:31:58,000 --> 00:32:00,940 evo kako operator znak za struju radi. 684 00:32:00,940 --> 00:32:06,400 0 0 znak za struju će jednaka 0. 685 00:32:06,400 --> 00:32:07,210 Sad zašto je to tako? 686 00:32:07,210 --> 00:32:09,291 >> To je vrlo slično Boolean izrazi, 687 00:32:09,291 --> 00:32:10,540 da smo do sada razgovarali. 688 00:32:10,540 --> 00:32:15,800 Ako mislite da se nakon svega, 0 je lažna, 0 je lažna, lažna i pogrešna 689 00:32:15,800 --> 00:32:18,720 je, kao što smo razgovarali logično, također lažna. 690 00:32:18,720 --> 00:32:20,270 Tako smo dobili 0 i ovdje. 691 00:32:20,270 --> 00:32:24,390 Ako uzmete 0 ampersand 1, te da je, također, 692 00:32:24,390 --> 00:32:29,890 će biti 0, jer je za to lijevi izraz da bi bilo istinito ili 1, 693 00:32:29,890 --> 00:32:32,360 to bi trebao biti istinito i istinito. 694 00:32:32,360 --> 00:32:36,320 Ali ovdje imamo lažna i istina, ili 0 i 1. 695 00:32:36,320 --> 00:32:42,000 Sada opet, ako imamo 1 ampersand 0, da, također, će biti 0, 696 00:32:42,000 --> 00:32:47,240 a ako imamo 1 ampersand 1, napokon ćemo imati 1 bit. 697 00:32:47,240 --> 00:32:50,340 Dakle, drugim riječima, mi ne radimo ništa zanimljivo s ovim operatorom 698 00:32:50,340 --> 00:32:51,850 samo još ovo znak za struju operatora. 699 00:32:51,850 --> 00:32:53,780 To je bitovni AND operator. 700 00:32:53,780 --> 00:32:57,290 No, to su sastojci preko kojeg možemo učiniti 701 00:32:57,290 --> 00:32:59,240 zanimljivosti, kao što ćemo uskoro vidjeti. 702 00:32:59,240 --> 00:33:02,790 >> Sada pogledajmo samo jednom okomita traka ovdje na desnoj strani. 703 00:33:02,790 --> 00:33:06,710 Ako imam 0 malo i ja Ili je to sa, bitovni 704 00:33:06,710 --> 00:33:11,030 Operator OR, još malo 0, da će mi dati 0. 705 00:33:11,030 --> 00:33:17,540 Ako sam se malo i 0 ili je s A 1 malo, a onda ću dobiti 1. 706 00:33:17,540 --> 00:33:19,830 A u stvari, samo za Jasnoća, neka mi se vratiti, 707 00:33:19,830 --> 00:33:23,380 tako da mi okomite trake nisu u zabludi za 1-a. 708 00:33:23,380 --> 00:33:26,560 Dopustite mi prepisati sve moj 1 je malo više 709 00:33:26,560 --> 00:33:32,700 Jasno, kako bismo iduće vidjeti, ako ja su 1 ili 0, to će biti 1, 710 00:33:32,700 --> 00:33:39,060 a ako imam 1 ili 1 da, također će biti 1. 711 00:33:39,060 --> 00:33:42,900 Tako možete vidjeti logično da ILI Operator ponaša vrlo različito. 712 00:33:42,900 --> 00:33:48,070 To mi daje 0 ili 0 daje mi 0, ali svaka druga kombinacija daje mi 1. 713 00:33:48,070 --> 00:33:52,480 Sve dok imam jedno 1 u Formula, rezultat će biti 1. 714 00:33:52,480 --> 00:33:55,580 >> Za razliku od AND Operater je znak za struju, 715 00:33:55,580 --> 00:34:00,940 samo ako imam dva +1 u jednadžba, ja zapravo dobiti 1 out. 716 00:34:00,940 --> 00:34:02,850 Sada postoji nekoliko drugih operateri, kao dobro. 717 00:34:02,850 --> 00:34:04,810 Jedan od njih je malo više uključeni. 718 00:34:04,810 --> 00:34:07,980 Pa neka mi ići naprijed i brisanje to slobodan gore neki prostor. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 I neka je pogledajte znak za umetanje simbola, samo na trenutak. 721 00:34:16,460 --> 00:34:18,210 To je tipično lik možete upisati 722 00:34:18,210 --> 00:34:21,420 na vašem gospodarstvu tipkovnice Shift i zatim jedan od brojeva na vrhu vašeg SAD 723 00:34:21,420 --> 00:34:22,250 tipkovnice. 724 00:34:22,250 --> 00:34:26,190 >> Dakle, ovo je ekskluzivni Operator OR, ekskluzivno ILI. 725 00:34:26,190 --> 00:34:27,790 Tako smo upravo vidjeli operatoru ili. 726 00:34:27,790 --> 00:34:29,348 To je isključivo ILI operatora. 727 00:34:29,348 --> 00:34:30,639 Što je zapravo razlika? 728 00:34:30,639 --> 00:34:34,570 Pa neka je samo pogledajte formulom, i koristiti kao sastojci u konačnici. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Idem reći je uvijek 0. 731 00:34:39,650 --> 00:34:41,400 To je definicija XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 će biti 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 će biti 1, i 1 XOR 1 će biti? 734 00:34:58,810 --> 00:34:59,890 Pogrešno? 735 00:34:59,890 --> 00:35:00,520 Ili zar ne? 736 00:35:00,520 --> 00:35:01,860 Ne znam. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Sada što se ovdje događa? 739 00:35:04,700 --> 00:35:06,630 Pa mislim o Naziv ovog operatora. 740 00:35:06,630 --> 00:35:09,980 Ekskluzivno ILI, pa kao naziv, vrsta, sugerira, 741 00:35:09,980 --> 00:35:13,940 odgovor će biti samo A 1, ako se ulazi su isključivi, 742 00:35:13,940 --> 00:35:15,560 isključivo drugačije. 743 00:35:15,560 --> 00:35:18,170 Dakle ovdje ulazi su Isto tako je izlaz 0. 744 00:35:18,170 --> 00:35:20,700 Ovdje ulazi su Isto tako je izlaz 0. 745 00:35:20,700 --> 00:35:25,640 Ovdje su rezultati su različiti, oni su isključivi, pa izlaz je 1. 746 00:35:25,640 --> 00:35:28,190 Dakle, to je vrlo slično I, to je vrlo sličan, 747 00:35:28,190 --> 00:35:32,760 odnosno to je vrlo slično ILI, ali samo u ekskluzivnom način. 748 00:35:32,760 --> 00:35:36,210 Ovo je jedna više nije 1, jer imamo dvije 1-a, 749 00:35:36,210 --> 00:35:38,621 a ne isključivo, samo jedan od njih. 750 00:35:38,621 --> 00:35:39,120 U redu. 751 00:35:39,120 --> 00:35:40,080 Što je s ostalima? 752 00:35:40,080 --> 00:35:44,220 Pa tilda, u međuvremenu, je zapravo lijepo i jednostavno, srećom. 753 00:35:44,220 --> 00:35:46,410 I to je predznak operater, što znači 754 00:35:46,410 --> 00:35:50,400 to primjenjuje samo jedan ulaz, jedan operand, da se tako izrazim. 755 00:35:50,400 --> 00:35:51,800 Ne lijevi i desni. 756 00:35:51,800 --> 00:35:56,050 Drugim riječima, ako se uzme u tilda 0, odgovor će biti upravo suprotno. 757 00:35:56,050 --> 00:35:59,710 A ako se uzme tilda od 1, Odgovor će biti suprotan. 758 00:35:59,710 --> 00:36:02,570 Dakle tilda operator način negirajući malo, 759 00:36:02,570 --> 00:36:06,000 ili flipping malo od 0 do 1, ili 1 do 0 ° C. 760 00:36:06,000 --> 00:36:09,820 >> I to nas ostavlja na kraju sa samo dvije završne operatora, 761 00:36:09,820 --> 00:36:13,840 tzv lijevi pomak, a Takozvani pravo operatora pomaka. 762 00:36:13,840 --> 00:36:16,620 Idemo pogledati kako ti posla. 763 00:36:16,620 --> 00:36:20,780 Lijeva operatora pomaka, napisao s dva kutnika kao što je to, 764 00:36:20,780 --> 00:36:22,110 na sljedeći način. 765 00:36:22,110 --> 00:36:27,390 Ako moj ulaz, ili moja operand, lijevo Operator pomak je vrlo jednostavno 1. 766 00:36:27,390 --> 00:36:33,750 A ja onda kažem računalo na napustio pomak da je 1, kažu sedam mjesta, 767 00:36:33,750 --> 00:36:37,150 rezultat je kao da sam uzeti da je 1, i premjestiti ga 768 00:36:37,150 --> 00:36:40,160 Sedam mjesta na za lijevo, a po defaultu, 769 00:36:40,160 --> 00:36:42,270 ćemo pretpostaviti da prostor na desnoj strani 770 00:36:42,270 --> 00:36:44,080 će biti postavljen nulama. 771 00:36:44,080 --> 00:36:50,316 Drugim riječima, 1 napustio pomak 7 ide se prouzročiti 1, zatim 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 nula. 773 00:36:54,060 --> 00:36:57,380 Dakle, na neki način, što vam omogućuje da se uzeti mali broj kao 1, 774 00:36:57,380 --> 00:37:00,740 i jasno ga učiniti mnogo mnogo, mnogo veći na ovaj način, 775 00:37:00,740 --> 00:37:06,460 ali mi zapravo idemo vidjeti više pametan pristupi za njega 776 00:37:06,460 --> 00:37:08,080 umjesto toga, kao i, 777 00:37:08,080 --> 00:37:08,720 >> U redu. 778 00:37:08,720 --> 00:37:10,060 To je to za tjedan dana tri. 779 00:37:10,060 --> 00:37:11,400 Mi ćemo vas vidjeti sljedeći put. 780 00:37:11,400 --> 00:37:12,770 Ovo je CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Glazbom] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: On je bio na marendu bar jede u kremastom sundae. 784 00:37:25,766 --> 00:37:28,090 On je sve to imao preko lica. 785 00:37:28,090 --> 00:37:30,506 On je nosio tu čokoladu kao bradom 786 00:37:30,506 --> 00:37:31,756 ZVUČNIK 2: Što to radiš? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Što? 789 00:37:33,500 --> 00:37:36,800 >> ZVUČNIK 2: Jeste li samo dvaput dip? 790 00:37:36,800 --> 00:37:38,585 Dvaput kratko čip. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Ispričavam se. 792 00:37:39,460 --> 00:37:44,440 ZVUČNIK 2: kratka ti čip, što zagrize, a ti opet kratka. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 ZVUČNIK 2: Dakle, to je poput stavljanja cijela tvoja usta pravo u dip. 795 00:37:48,440 --> 00:37:52,400 Sljedeći put kada se čip, samo ga umočiti jednom i završiti ga. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Znate što, Dan? 797 00:37:53,890 --> 00:37:58,006 Možete umočiti način na koji želite umočiti. 798 00:37:58,006 --> 00:38:01,900 Ja ću umočiti način na koji želim dip. 799 00:38:01,900 --> 00:38:03,194