1 00:00:00,000 --> 00:00:11,904 >> [Prehrávanie hudby] 2 00:00:11,904 --> 00:00:12,910 >> Profesor: Dobre. 3 00:00:12,910 --> 00:00:16,730 To je CS50, a to je koncom tretieho týždňa. 4 00:00:16,730 --> 00:00:20,230 Tak sme tu dnes, nie v Sanders Divadlo, namiesto toho v Weidner knižnici. 5 00:00:20,230 --> 00:00:23,170 Vnútri čo je štúdio známy ako Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 alebo povedzme Studio H, alebo musí my say-- ak sa vám to páčilo ten vtip, 7 00:00:28,310 --> 00:00:30,540 je to vlastne z spolužiak, Mark, online, 8 00:00:30,540 --> 00:00:32,420 ktorý navrhol toľko cez Twitter. 9 00:00:32,420 --> 00:00:34,270 Teraz, čo je v pohode tu v štúdiu 10 00:00:34,270 --> 00:00:38,410 je, že som obklopený týchto zelených múry, zelené obrazovky alebo chromakey, 11 00:00:38,410 --> 00:00:43,290 tak povediac, čo znamená, že je CS50 Inscenačné tím unbeknownst mne 12 00:00:43,290 --> 00:00:47,380 práve teraz, môže byť uvedenie Najviac ma kdekoľvek na svete, 13 00:00:47,380 --> 00:00:48,660 k lepšiemu alebo k horšiemu. 14 00:00:48,660 --> 00:00:51,800 >> Teraz, čo je pred nami, nastavte problém dva je vo vašich rukách pre tento týždeň, 15 00:00:51,800 --> 00:00:53,830 ale s problémom set Tri tento nadchádzajúci týždeň, 16 00:00:53,830 --> 00:00:56,600 budete mať za úlohu s tzv hra 15, 17 00:00:56,600 --> 00:00:58,960 starý strana láskavosť, že môžete pripomenúť príjem 18 00:00:58,960 --> 00:01:02,030 ako dieťa, ktorý má veľa čísel, ktorá môže kĺzať hore, dole, 19 00:01:02,030 --> 00:01:05,790 vľavo a vpravo, a je tu ešte jedna medzera v rámci skladačky, do ktorého ste 20 00:01:05,790 --> 00:01:07,840 môže skutočne posunúť tie dielikov. 21 00:01:07,840 --> 00:01:11,150 Nakoniec dostanete tento puzzle v nejakom semifinále náhodnom poradí, 22 00:01:11,150 --> 00:01:12,940 a cieľom je, aby triediť to, zhora dole, 23 00:01:12,940 --> 00:01:16,310 zľava doprava, z jednej celú cestu hore cez 15. 24 00:01:16,310 --> 00:01:19,360 >> Bohužiaľ, implementácia budete mať po ruke 25 00:01:19,360 --> 00:01:21,590 bude softvér na báze, nie je fyzicky. 26 00:01:21,590 --> 00:01:25,280 Tie vlastne bude musieť písať kód, pomocou ktorého študent alebo Užívateľ môže 27 00:01:25,280 --> 00:01:26,760 hrať hru 15. 28 00:01:26,760 --> 00:01:29,030 A v skutočnosti, v hacker vydania hry 15, 29 00:01:29,030 --> 00:01:32,155 budete výzvou realizovať, nie len hranie tejto starej školy 30 00:01:32,155 --> 00:01:35,010 hra, ale skôr riešenie o tom, ktorou sa vykonáva nesmrteľnosť, 31 00:01:35,010 --> 00:01:38,280 aby som tak povedal, že v skutočnosti rieši puzzle pre človeka, 32 00:01:38,280 --> 00:01:41,080 tým, že im s nádychom, po náznaku, po náznakom. 33 00:01:41,080 --> 00:01:42,280 Takže o tom až budúci týždeň. 34 00:01:42,280 --> 00:01:43,720 Ale to je to, čo nás čaká. 35 00:01:43,720 --> 00:01:47,610 >> Pre túto chvíľu pripomenúť, že začiatkom tohto týždňa sme mali tento Cliffhanger, ak chcete, 36 00:01:47,610 --> 00:01:52,560 pričom najlepšie, čo sme robili triedenie múdry bola horná hranica veľkého o n 37 00:01:52,560 --> 00:01:53,210 na druhú. 38 00:01:53,210 --> 00:01:56,520 Inými slovami, bublinkové radenie, výber triedenie, insertion sort, 39 00:01:56,520 --> 00:01:59,120 všetky z nich, zatiaľ čo iné pri ich vykonávaní, 40 00:01:59,120 --> 00:02:03,480 prešiel do n druhú spustenie Čas vo veľmi najhoršom prípade. 41 00:02:03,480 --> 00:02:06,010 A my všeobecne predpokladajú, že úplne najhoršom prípade pre triedenie 42 00:02:06,010 --> 00:02:08,814 je ten, ktorý vaše vstupy sú úplne dozadu. 43 00:02:08,814 --> 00:02:11,980 A skutočne, to trvalo pomerne málo krokov na vykonávanie každej z týchto algoritmov. 44 00:02:11,980 --> 00:02:15,110 >> Teraz na samom konci triedy Pripomeňme, porovnali sme bublinkové triedenie 45 00:02:15,110 --> 00:02:19,390 proti výberu druhu proti jednému iný že sme nazvali merge sort v tej dobe, 46 00:02:19,390 --> 00:02:22,120 a navrhujem, aby to trvá Výhodou lekciu od týždňa 47 00:02:22,120 --> 00:02:24,060 nula, rozdeľ a panuj. 48 00:02:24,060 --> 00:02:28,810 A nejako dosiahnuť nejaký druh logaritmické doba chodu nakoniec, 49 00:02:28,810 --> 00:02:31,024 miesto niečoho to je čisto kvadratická. 50 00:02:31,024 --> 00:02:33,440 A nie je to úplne logaritmickej, je to trochu viac než to. 51 00:02:33,440 --> 00:02:36,520 Ale ak si spomínate z triedy, to bolo oveľa, oveľa rýchlejšie. 52 00:02:36,520 --> 00:02:38,210 Poďme sa pozrieť, kde sme prestali. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble sort proti výberu triediť proti zlúčeniu druhu. 55 00:02:45,370 --> 00:02:47,700 Teraz sú všetci beží, v teórie, v rovnakom čase. 56 00:02:47,700 --> 00:02:50,510 CPU beží rovnakou rýchlosťou. 57 00:02:50,510 --> 00:02:54,990 Ale môžete cítiť, ako to nuda sa veľmi rýchlo stane, 58 00:02:54,990 --> 00:02:58,790 a len ako rýchlo, keď sme injekciu trochu týždni nula je algoritmov, 59 00:02:58,790 --> 00:03:00,080 môžeme veci urýchliť. 60 00:03:00,080 --> 00:03:01,630 >> Takže značka nejako vyzerá úžasne. 61 00:03:01,630 --> 00:03:05,220 Ako môžeme využiť ju, aby rýchlejšie zoradiť čísel. 62 00:03:05,220 --> 00:03:07,140 Tak poďme spomeniem na zložky, ktoré sme 63 00:03:07,140 --> 00:03:10,380 mala už v týždni nula, to hľadať niekoho, kto sa v telefónnom zozname, 64 00:03:10,380 --> 00:03:12,380 a pripomenul, že pseudokód, že sme navrhli, 65 00:03:12,380 --> 00:03:14,560 cez ktorý môžeme nájsť niekto ako Mike Smith, 66 00:03:14,560 --> 00:03:16,310 vyzeral trochu niečo také. 67 00:03:16,310 --> 00:03:20,820 >> Teraz sa pozrite predovšetkým na riadku 7 a 8, a 10 a 11, 68 00:03:20,820 --> 00:03:25,240 ktorý prinútiť ho slučky, čím sme ponechali ísť späť do riadku 3 znovu a znovu, 69 00:03:25,240 --> 00:03:26,520 a znovu. 70 00:03:26,520 --> 00:03:31,790 Ale ukazuje sa, že môžeme zobraziť Tento algoritmus, tu v pseudokódu, 71 00:03:31,790 --> 00:03:33,620 trochu viac holisticky. 72 00:03:33,620 --> 00:03:35,960 V skutočnosti to, čo som hľadal v tu na obrazovke, 73 00:03:35,960 --> 00:03:41,180 je algoritmus pre vyhľadávanie Mike Smith medzi niektorými sady stránok. 74 00:03:41,180 --> 00:03:45,520 A skutočne, môžeme zjednodušiť tento algoritmus v týchto bodov 7 a 8, 75 00:03:45,520 --> 00:03:49,860 a 10 a 11 len povedať to, ktorý som tu uvedená v žltej. 76 00:03:49,860 --> 00:03:52,210 Inými slovami, v prípade, Mike Smith je skôr v knihe, 77 00:03:52,210 --> 00:03:55,004 nepotrebujeme špecifikovať krok za krokom, teraz, ako ho nájsť. 78 00:03:55,004 --> 00:03:56,920 Nemáme špecifikovať sa vrátiť do riadku 3, 79 00:03:56,920 --> 00:03:58,960 prečo nie my len miesto, povedzme, všeobecnejšie, 80 00:03:58,960 --> 00:04:01,500 hľadať Mike v Ľavá polovica knihy. 81 00:04:01,500 --> 00:04:03,960 >> Naopak, pokiaľ je Mike v skutočnosti neskôr v knihe, 82 00:04:03,960 --> 00:04:07,540 prečo nie my len citovať koniec citátu hľadanie Mike v pravej polovici knihy. 83 00:04:07,540 --> 00:04:11,030 Inými slovami, prečo nie my len druh pramici na seba hovorí, 84 00:04:11,030 --> 00:04:13,130 hľadať Mike v tejto podmnožina knihy, 85 00:04:13,130 --> 00:04:16,279 a nechajte to na naše existujúce algoritmus, aby nám povedali 86 00:04:16,279 --> 00:04:18,750 ako hľadať Mike v že ľavá polovica knihy. 87 00:04:18,750 --> 00:04:20,750 Inými slovami, naša algoritmus pracuje či už je to 88 00:04:20,750 --> 00:04:24,670 telefónny zoznam tejto sily, z toho Hrúbka, alebo akejkoľvek hrúbky vôbec. 89 00:04:24,670 --> 00:04:27,826 Takže môžeme rekurzívne definovať tento algoritmus. 90 00:04:27,826 --> 00:04:29,950 Inými slovami, na Obrazovka tu, je algoritmus 91 00:04:29,950 --> 00:04:33,130 pre vyhľadávanie Mike Smith Medzi stránkami telefónneho zoznamu. 92 00:04:33,130 --> 00:04:37,410 Takže v riadku 7 a 10, poďme len povedať, že presne. 93 00:04:37,410 --> 00:04:40,250 A ja používať tento termín na chvíľu Pred, a naozaj, rekurzia 94 00:04:40,250 --> 00:04:42,450 je módne slovo pre túto chvíľu, a to je tento proces 95 00:04:42,450 --> 00:04:47,210 robiť niečo, čo by nejako cyklické pomocou kódu, ktorý už máte, 96 00:04:47,210 --> 00:04:49,722 a znovu volá, a znova a znova. 97 00:04:49,722 --> 00:04:51,930 Teraz to bude dôležité, že sme sa nejako dno 98 00:04:51,930 --> 00:04:53,821 out, a nerobte to nekonečne dlho. 99 00:04:53,821 --> 00:04:56,070 V opačnom prípade budeme majú naozaj nekonečnej slučke. 100 00:04:56,070 --> 00:04:59,810 Ale poďme sa pozrieť, či môžeme požičať túto myšlienku z rekurzie, zase niečo 101 00:04:59,810 --> 00:05:03,600 a znovu a znovu, riešiť triedenie problém cez zlúčenie 102 00:05:03,600 --> 00:05:05,900 triediť, tým efektívnejšie. 103 00:05:05,900 --> 00:05:06,970 >> Takže dávam zlúčenie triediť. 104 00:05:06,970 --> 00:05:07,920 Poďme sa pozrieť. 105 00:05:07,920 --> 00:05:10,850 Takže tu je pseudokód, s ktoré sme mohli vykonávať triedenie, 106 00:05:10,850 --> 00:05:12,640 Pomocou tohto algoritmu s názvom merge sort. 107 00:05:12,640 --> 00:05:13,880 A je to celkom jednoducho to. 108 00:05:13,880 --> 00:05:15,940 Na vstupe n elementy, Inými slovami, ak ste 109 00:05:15,940 --> 00:05:18,830 vzhľadom k tomu, n prvky a čísla a listy alebo čo je vstup, 110 00:05:18,830 --> 00:05:22,430 ak ste dal n elementy, pokiaľ n je menší ako 2, len sa vrátiť. 111 00:05:22,430 --> 00:05:22,930 Je to tak? 112 00:05:22,930 --> 00:05:26,430 Vzhľadom k tomu, ak n je menšia ako 2, ktoré Znamená to, že môj zoznam prvkov 113 00:05:26,430 --> 00:05:30,446 je buď o veľkosti 0 alebo 1, a V oboch týchto prípadoch triviálne, 114 00:05:30,446 --> 00:05:31,570 zoznam už je zoradený. 115 00:05:31,570 --> 00:05:32,810 Ak nie je k dispozícii zoznam, je to triediť. 116 00:05:32,810 --> 00:05:35,185 A ak tam je zoznam dĺžky 1, je to samozrejme triediť. 117 00:05:35,185 --> 00:05:38,280 Takže algoritmus len potrebuje naozaj niečo zaujímavé, 118 00:05:38,280 --> 00:05:40,870 ak budeme mať dva alebo viac prvky nám daná. 119 00:05:40,870 --> 00:05:42,440 Takže poďme sa pozrieť na mágiu potom. 120 00:05:42,440 --> 00:05:47,500 Else zoradiť ľavej polovice prvkov, potom triediť pravú polovicu prvkov, 121 00:05:47,500 --> 00:05:49,640 potom zlúčiť zotriedené polovice. 122 00:05:49,640 --> 00:05:52,440 A čo je druh mysli ohýbanie tu je, že naozaj nemám 123 00:05:52,440 --> 00:05:56,190 Zdá sa, že vám povedal, niečo ešte nie, že jo? 124 00:05:56,190 --> 00:05:59,560 Všetko, čo som povedal, je, dostane zoznam n prvkov, triediť ľavú polovicu, 125 00:05:59,560 --> 00:06:01,800 potom pravé polovice, potom zlúčiť zoradené polovice, 126 00:06:01,800 --> 00:06:03,840 ale tam, kde je skutočný tajný recept? 127 00:06:03,840 --> 00:06:05,260 Kde je algoritmus? 128 00:06:05,260 --> 00:06:09,150 No, ukázalo sa, že tých dvoch liniek Prvý, druh ľavej polovici prvkov, 129 00:06:09,150 --> 00:06:13,970 a druh pravá polovica prvkov, sú rekurzívne volanie, aby som tak povedal. 130 00:06:13,970 --> 00:06:16,120 >> Koniec koncov, na to bod v čase, musím 131 00:06:16,120 --> 00:06:18,950 algoritmus, s ktorým zoradiť veľa prvkov? 132 00:06:18,950 --> 00:06:19,450 Áno. 133 00:06:19,450 --> 00:06:20,620 Je to priamo tu. 134 00:06:20,620 --> 00:06:25,180 Je to priamo tu na obrazovke, a takže môžem použiť ten rovnaký súbor krokov 135 00:06:25,180 --> 00:06:28,500 triediť ľavú polovicu, ako môžem pravá polovica. 136 00:06:28,500 --> 00:06:30,420 A skutočne, znovu a znovu. 137 00:06:30,420 --> 00:06:34,210 Takže tak či onak, a my čoskoro vidieť, kúzlo zlúčenie druhu 138 00:06:34,210 --> 00:06:37,967 je zakotvený v tom, že veľmi konečný linka, zlučovanie triedených polovice. 139 00:06:37,967 --> 00:06:39,300 A to sa zdá byť pomerne intuitívne. 140 00:06:39,300 --> 00:06:41,050 Budete mať dve polovice, a tí, nejako, spojiť ich dohromady, 141 00:06:41,050 --> 00:06:43,260 a my budeme vidieť konkrétne za chvíľu. 142 00:06:43,260 --> 00:06:45,080 >> Ale to je kompletný algoritmus. 143 00:06:45,080 --> 00:06:46,640 A pozrime sa, prečo. 144 00:06:46,640 --> 00:06:50,912 Tak predpokladám, že sme vzhľadom k tie isté Osem prvky tu na obrazovke, jeden 145 00:06:50,912 --> 00:06:53,120 cez osem, ale sú v zdanlivo náhodnom poradí. 146 00:06:53,120 --> 00:06:55,320 A cieľ je na dosah ruky triediť tieto prvky. 147 00:06:55,320 --> 00:06:58,280 Tak ako môžem ísť o robí použitie, znovu, 148 00:06:58,280 --> 00:07:00,407 merge sort, ako na tento pseudokódu? 149 00:07:00,407 --> 00:07:02,740 A opäť, farbiť to v vaša myseľ, len na chvíľu. 150 00:07:02,740 --> 00:07:05,270 V prvom prípade je dosť triviálne, ak je to menej ako 2, 151 00:07:05,270 --> 00:07:07,060 len vrátiť, nie je práce je potrebné urobiť. 152 00:07:07,060 --> 00:07:09,290 Takže naozaj tam je len tri kroky k naozaj mať na pamäti. 153 00:07:09,290 --> 00:07:11,081 Znovu a znovu, ja som bude chcieť mať 154 00:07:11,081 --> 00:07:13,980 triediť ľavú polovicu, triediť pravú polovicu, 155 00:07:13,980 --> 00:07:15,890 a potom ešte raz ich dve polovice sú radené, 156 00:07:15,890 --> 00:07:18,710 Chcem je zlúčiť dohromady do jedného zoradení zoznamu. 157 00:07:18,710 --> 00:07:19,940 Takže majte na pamäti, že. 158 00:07:19,940 --> 00:07:21,310 >> Tak tu je pôvodný zoznam. 159 00:07:21,310 --> 00:07:23,510 Poďme sa touto ako pole, ako sme začali 160 00:07:23,510 --> 00:07:25,800 v dvoch týždni, čo je súvislý blok pamäte. 161 00:07:25,800 --> 00:07:28,480 V tomto prípade, ktorý obsahuje osem Čísla, chrbtom k sebe k sebe. 162 00:07:28,480 --> 00:07:30,700 A poďme sa teraz vzťahujú merge sort. 163 00:07:30,700 --> 00:07:33,300 Tak som sa prvýkrát chcete zoradiť ľavá polovica tohto zoznamu, 164 00:07:33,300 --> 00:07:37,370 a poďme sa teda, zamerať sa na 4, 8, 6, a 2. 165 00:07:37,370 --> 00:07:41,000 >> Teraz, ako mám ísť o radenie zoznamu veľkosti 4? 166 00:07:41,000 --> 00:07:45,990 No musím teraz považujú triedenie vľavo od ľavej polovice. 167 00:07:45,990 --> 00:07:47,720 Opäť platí, poďme vzad len na chvíľu. 168 00:07:47,720 --> 00:07:51,010 V prípade, že je to pseudokód, a ja som dal osem elementov, 169 00:07:51,010 --> 00:07:53,230 8 je samozrejme väčšia, než alebo rovný 2. 170 00:07:53,230 --> 00:07:54,980 A tak sa o prvý prípad, neuplatňuje. 171 00:07:54,980 --> 00:07:58,120 Takže triediť osem elementov, som prvýkrát radiť ľavú polovicu prvkov, 172 00:07:58,120 --> 00:08:01,930 Potom som zoradiť pravú polovicu, potom som sa zlúčiť obe zoradená polovice, každá o veľkosti 4. 173 00:08:01,930 --> 00:08:02,470 OK. 174 00:08:02,470 --> 00:08:07,480 >> Ale ak ste práve mi povedal, Roztieďte ľavá polovica, ktorá je teraz o veľkosti 4, 175 00:08:07,480 --> 00:08:09,350 ako mám triediť ľavú polovicu? 176 00:08:09,350 --> 00:08:11,430 No, ak mám vstup zo štyroch prvkov, 177 00:08:11,430 --> 00:08:14,590 Prvýkrát som radiť ľavú dvoch a potom pravé dva, 178 00:08:14,590 --> 00:08:16,210 a potom som sa spojiť ich dohromady. 179 00:08:16,210 --> 00:08:18,700 Takže znovu, to sa stáva trochu na mysli ohýbanie hru tu, 180 00:08:18,700 --> 00:08:21,450 Pretože tie, druh, musí spomenúť, kde ste v príbehu, 181 00:08:21,450 --> 00:08:23,620 ale na konci dňa, vzhľadom k tomu, ľubovoľný počet prvkov, 182 00:08:23,620 --> 00:08:25,620 najprv chcete triediť ľavá polovica, potom pravá polovica, 183 00:08:25,620 --> 00:08:26,661 potom spojiť ich dohromady. 184 00:08:26,661 --> 00:08:28,630 Poďme začať robiť presne to. 185 00:08:28,630 --> 00:08:30,170 Tu je vstup z ôsmich prvkov. 186 00:08:30,170 --> 00:08:31,910 Teraz sa pozeráme na ľavej polovici tu. 187 00:08:31,910 --> 00:08:33,720 Ako mám triediť štyri prvky? 188 00:08:33,720 --> 00:08:35,610 Tak som najprv zoradiť ľavej polovice. 189 00:08:35,610 --> 00:08:37,720 Teraz, ako sa môžem radiť ľavú polovicu? 190 00:08:37,720 --> 00:08:39,419 No ja som dostal dva prvky. 191 00:08:39,419 --> 00:08:41,240 Takže poďme zoradiť tieto dva prvky. 192 00:08:41,240 --> 00:08:44,540 2 je väčší alebo rovné 2, samozrejme. 193 00:08:44,540 --> 00:08:46,170 Tak, že prvý prípad nevzťahuje. 194 00:08:46,170 --> 00:08:49,010 >> Takže som teraz musí triediť ľavú polovica z týchto dvoch prvkov. 195 00:08:49,010 --> 00:08:50,870 Ľavá polovica, samozrejme, je len 4. 196 00:08:50,870 --> 00:08:54,020 Tak ako mám zoradiť zoznam z jedného prvku? 197 00:08:54,020 --> 00:08:57,960 Tak a teraz, že zvláštne referenčné prípad up vrchole, aby som tak povedal, platí. 198 00:08:57,960 --> 00:09:01,470 1 je menšia ako 2, a my Zoznam je skutočne o veľkosti 1. 199 00:09:01,470 --> 00:09:02,747 Tak som sa vrátiť. 200 00:09:02,747 --> 00:09:03,580 Ja nerobím nič. 201 00:09:03,580 --> 00:09:06,770 A skutočne, pozerať sa na to, čo som urobil, 4 už je zoradený. 202 00:09:06,770 --> 00:09:09,220 Ako by som už čiastočne úspešné tu. 203 00:09:09,220 --> 00:09:11,750 >> Teraz sa zdá, že trochu hlúpy nároku, ale je to pravda. 204 00:09:11,750 --> 00:09:13,700 4 je uvedený zoznam veľkosti 1. 205 00:09:13,700 --> 00:09:15,090 Je to už je zoradený. 206 00:09:15,090 --> 00:09:16,270 To je ľavá polovica. 207 00:09:16,270 --> 00:09:18,010 Teraz som radiť pravú polovicu. 208 00:09:18,010 --> 00:09:22,310 Môj vstup je jedným z prvkov, 8 podobne, už zoradené. 209 00:09:22,310 --> 00:09:25,170 Hlúpy, taky, ale opäť, Tento základný princíp 210 00:09:25,170 --> 00:09:28,310 bude nám umožní si teraz budujú v hornej časti tejto úspešne. 211 00:09:28,310 --> 00:09:32,260 4 radené, 8 je triedený, teraz čo to bolo posledný krok? 212 00:09:32,260 --> 00:09:35,330 Takže tretí a posledný krok, akýkoľvek Čas, ktorý sa triedenie zoznamu, odvolanie, 213 00:09:35,330 --> 00:09:38,310 bolo zlúčiť dve polovice, ľavý a pravý. 214 00:09:38,310 --> 00:09:39,900 Takže poďme urobiť presne to. 215 00:09:39,900 --> 00:09:41,940 Má ľavá polovica je, samozrejme, 4. 216 00:09:41,940 --> 00:09:43,310 Moja pravá polovica je 8. 217 00:09:43,310 --> 00:09:44,100 >> Tak ideme na to. 218 00:09:44,100 --> 00:09:46,410 Najprv budem prideliť niektoré ďalšie pamäť, 219 00:09:46,410 --> 00:09:48,680 že budem reprezentovať tu, len ako sekundárny poľa, 220 00:09:48,680 --> 00:09:49,660 to je dosť veľký, aby sa zmestili to. 221 00:09:49,660 --> 00:09:52,243 Ale môžete si predstaviť rozšírenie že obdĺžnik po celej dĺžke, 222 00:09:52,243 --> 00:09:53,290 ak budeme potrebovať viac neskôr. 223 00:09:53,290 --> 00:09:58,440 Ako môžem zaobstarať 4 a 8, a zlúčiť tieto dva zoznamy veľkosti 1 spolu? 224 00:09:58,440 --> 00:10:00,270 Aj tu celkom jednoduché. 225 00:10:00,270 --> 00:10:03,300 4 je na prvom mieste, potom príde 8. 226 00:10:03,300 --> 00:10:07,130 Pretože ak chcem na triedite ľavá polovica, potom pravá polovica, 227 00:10:07,130 --> 00:10:09,900 a potom zlúčiť tieto dve polovice spoločne, v zoradení poradí, 228 00:10:09,900 --> 00:10:11,940 4 je na prvom mieste, potom príde 8. 229 00:10:11,940 --> 00:10:15,810 >> Takže sa zdá, že bude robiť pokroky, a to aj aj keď som neurobil žiadnu skutočnú prácu. 230 00:10:15,810 --> 00:10:17,800 Ale pamätajte, kde sme v príbehu. 231 00:10:17,800 --> 00:10:19,360 Pôvodne sme vzali osem prvkov. 232 00:10:19,360 --> 00:10:21,480 Vyriešili sme ľavú polovicu, čo je 4. 233 00:10:21,480 --> 00:10:24,450 Potom sme radené ľavú polovicu z ľavej polovice, ktorý bol 2. 234 00:10:24,450 --> 00:10:25,270 A je to tu. 235 00:10:25,270 --> 00:10:26,920 Sme skončili s týmto krokom. 236 00:10:26,920 --> 00:10:29,930 >> Takže ak sme triedi ľavej polovice 2, teraz sme 237 00:10:29,930 --> 00:10:32,130 majú triediť pravú polovicu 2. 238 00:10:32,130 --> 00:10:35,710 Takže pravá polovica 2 je Tieto dve hodnoty tu, 6 a 2. 239 00:10:35,710 --> 00:10:40,620 Takže poďme sa teraz vstup veľkosti 2, a triediť ľavú polovicu, a potom 240 00:10:40,620 --> 00:10:42,610 pravú polovicu, a potom zlúčiť dohromady. 241 00:10:42,610 --> 00:10:45,722 Tak ako mám zoradiť zoznam veľkosti 1, ktorý obsahuje len číslo 6? 242 00:10:45,722 --> 00:10:46,430 Ja som už skončil. 243 00:10:46,430 --> 00:10:48,680 Tento zoznam o veľkosti 1 je zoradený. 244 00:10:48,680 --> 00:10:52,140 >> Ako môžem vyriešiť ďalší zoznam veľkosť 1, tzv pravá polovica. 245 00:10:52,140 --> 00:10:54,690 No to, tiež, už je zoradený. 246 00:10:54,690 --> 00:10:56,190 Číslo 2 je sám. 247 00:10:56,190 --> 00:11:00,160 Takže teraz mám dve polovice, vľavo a Dobre, je potrebné ich zlúčiť dohromady. 248 00:11:00,160 --> 00:11:01,800 Dovoľte mi aby som si nejaké extra priestor. 249 00:11:01,800 --> 00:11:05,580 A dal 2 tam, potom 6 tam, čím 250 00:11:05,580 --> 00:11:10,740 triedenie tohto zoznamu, vľavo a vpravo, a zlučovanie spoločne, nakoniec. 251 00:11:10,740 --> 00:11:12,160 Takže ja som v trochu lepšom stave. 252 00:11:12,160 --> 00:11:16,250 Ja som neskončil, pretože jasne 4, 8, 2, 6 nie je konečný, ktoré nariaďuje chcem. 253 00:11:16,250 --> 00:11:20,640 Ale teraz mám dva zoznamy veľkosti 2, že majú obaja, v danom poradí, boli zoradené. 254 00:11:20,640 --> 00:11:24,580 Takže teraz, ak pretočíte vo vašej mysli oko, kde sa to pre nás znamená? 255 00:11:24,580 --> 00:11:28,520 Začal som s ôsmimi prvkov, potom som orezaný dole do ľavej polovice 4, 256 00:11:28,520 --> 00:11:31,386 potom ľavú časť 2, a potom je pravá polovica 2, 257 00:11:31,386 --> 00:11:34,510 Som skončil, a preto, triedenie ľavý polovice 2, a v pravej polovici 2, 258 00:11:34,510 --> 00:11:37,800 takže to, čo je tu tretí a posledný krok? 259 00:11:37,800 --> 00:11:41,290 Musím sa spojiť dohromady dva zoznamy veľkosti 2. 260 00:11:41,290 --> 00:11:42,040 Tak poďme do toho. 261 00:11:42,040 --> 00:11:43,940 A na obrazovke sa tu, daj mi niektoré ďalšie pamäť, 262 00:11:43,940 --> 00:11:47,170 hoci technicky, všimnite si, že som dostal veľa prázdne miesto na začiatok 263 00:11:47,170 --> 00:11:47,670 tam. 264 00:11:47,670 --> 00:11:50,044 Ak chcem byť obzvlášť efektívna priestor múdry, 265 00:11:50,044 --> 00:11:52,960 Mohol by som dať do pohybu prvky tam a späť, hore a dole. 266 00:11:52,960 --> 00:11:55,460 Ale len pre vizuálnu jasnosť, Chystám sa dať to dole, 267 00:11:55,460 --> 00:11:56,800 udržať veci pekné a čisté. 268 00:11:56,800 --> 00:11:58,150 >> Tak som dostal dva zoznamy veľkosti 2. 269 00:11:58,150 --> 00:11:59,770 Prvý zoznam má 4 a 8. 270 00:11:59,770 --> 00:12:01,500 Druhý zoznam obsahuje 2 a 6. 271 00:12:01,500 --> 00:12:03,950 Poďme zlúčiť tie spolu v zoradení poradí. 272 00:12:03,950 --> 00:12:09,910 2, samozrejme, je na prvom mieste, potom 4, potom 6, potom 8. 273 00:12:09,910 --> 00:12:12,560 A teraz sa zdá, že sa dostať niekde zaujímavé. 274 00:12:12,560 --> 00:12:15,720 Teraz som radené polovica vypísať, a zhodou okolností je to 275 00:12:15,720 --> 00:12:18,650 všetky párne čísla, ale že je naozaj len náhoda. 276 00:12:18,650 --> 00:12:22,220 A teraz si radené ľavý polovica, tak, že to je 2, 4, 6 a 8. 277 00:12:22,220 --> 00:12:23,430 Nič nie je mimo prevádzku. 278 00:12:23,430 --> 00:12:24,620 To sa cíti ako pokrok. 279 00:12:24,620 --> 00:12:26,650 >> Teraz to vyzerá, som bol teraz hovorí navždy, 280 00:12:26,650 --> 00:12:29,850 Takže to, čo zostáva byť videný ak toto algoritmus je skutočne efektívnejšie. 281 00:12:29,850 --> 00:12:31,766 Ale my prechádzame to výborný metodicky. 282 00:12:31,766 --> 00:12:34,060 Počítač, samozrejme, by som to takto. 283 00:12:34,060 --> 00:12:34,840 Tak kde to sme? 284 00:12:34,840 --> 00:12:36,180 Začali sme s ôsmimi prvkov. 285 00:12:36,180 --> 00:12:37,840 Radené som ľavú polovicu 4. 286 00:12:37,840 --> 00:12:39,290 Zdá sa mi, je potrebné urobiť s tým. 287 00:12:39,290 --> 00:12:42,535 Takže teraz je ďalším krokom k triediť pravú polovicu 4. 288 00:12:42,535 --> 00:12:44,410 A táto časť môžeme ísť cez trochu viac 289 00:12:44,410 --> 00:12:47,140 rýchlo, aj keď ste Vítame Vás na vzad alebo pozastaviť, len 290 00:12:47,140 --> 00:12:49,910 myslíte, že cez to na svojím vlastným tempom, ale to, čo 291 00:12:49,910 --> 00:12:53,290 teraz máme, je príležitosť robiť presne rovnaký algoritmus na štyroch 292 00:12:53,290 --> 00:12:54,380 rôzne čísla. 293 00:12:54,380 --> 00:12:57,740 >> Tak poďme do toho, a zamerať sa na pravá polovica, ktorý sme tu. 294 00:12:57,740 --> 00:13:01,260 Ľavá polovica, ktorá pravú polovicu, a teraz 295 00:13:01,260 --> 00:13:04,560 Ľavá polovica vľavo polovica z tej pravej polovice, 296 00:13:04,560 --> 00:13:08,030 a ako zoradiť zoznam veľkosti 1 obsahujúcej iba číslo 1? 297 00:13:08,030 --> 00:13:09,030 Už sa stalo. 298 00:13:09,030 --> 00:13:11,830 Ako to mám urobiť to isté pre zoznam o veľkosti 1, ktorý obsahuje len 7? 299 00:13:11,830 --> 00:13:12,840 Už sa stalo. 300 00:13:12,840 --> 00:13:16,790 Tretí krok pre toto je polovica je zlúčiť tieto dva prvky 301 00:13:16,790 --> 00:13:20,889 do nového zoznamu veľkosti 2, 1 a 7. 302 00:13:20,889 --> 00:13:23,180 Nezdá sa, že urobili všetko že veľa zaujímavá práca. 303 00:13:23,180 --> 00:13:24,346 Pozrime sa, čo sa bude diať ďalej. 304 00:13:24,346 --> 00:13:29,210 Len som radené do ľavej polovice pravá polovica môjho pôvodného vstupu. 305 00:13:29,210 --> 00:13:32,360 Teraz poďme zoradiť právo polovica, ktorá obsahuje 5 a 3. 306 00:13:32,360 --> 00:13:35,740 Poďme sa znovu pozrieť na ľavej strane polovica, triedia, pravá polovica, triedia, 307 00:13:35,740 --> 00:13:39,120 a spojiť tie dva dohromady, do nejakého ďalšieho priestoru, 308 00:13:39,120 --> 00:13:41,670 3 je na prvom mieste, potom príde 5. 309 00:13:41,670 --> 00:13:46,190 A tak teraz sme sa triedi Ľavá polovica pravú polovicu 310 00:13:46,190 --> 00:13:49,420 z pôvodnej problém, a pravá polovica pravú polovicu 311 00:13:49,420 --> 00:13:50,800 z pôvodnej problém. 312 00:13:50,800 --> 00:13:52,480 Čo je tretí a posledný krok? 313 00:13:52,480 --> 00:13:54,854 No zlúčiť tieto dve polovice dohromady. 314 00:13:54,854 --> 00:13:57,020 Tak nech mi, aby som si sám trochu priestor navyše, ale opäť som 315 00:13:57,020 --> 00:13:58,699 môže byť pomocou tohto extra priestor na vrchol. 316 00:13:58,699 --> 00:14:00,490 Ale budeme držať to jednoduché vizuálne. 317 00:14:00,490 --> 00:14:07,070 Dovoľte mi, aby som teraz zlúčiť v 1, a potom 3, a potom 5, a potom 7. 318 00:14:07,070 --> 00:14:10,740 Tým ma teraz opúšťa s Pravá polovica pôvodnej problém 319 00:14:10,740 --> 00:14:12,840 to je dokonale zoradené. 320 00:14:12,840 --> 00:14:13,662 >> Takže to, čo zostane? 321 00:14:13,662 --> 00:14:16,120 Mám pocit, ako by som držať hovoriť rovnaké veci znovu a znovu, 322 00:14:16,120 --> 00:14:18,700 ale to je odrážajúce Skutočnosť, že sme pomocou rekurzia. 323 00:14:18,700 --> 00:14:21,050 Proces za použitia algoritmus znovu a znovu, 324 00:14:21,050 --> 00:14:23,940 na menšie podmnožiny pôvodnej problém. 325 00:14:23,940 --> 00:14:27,580 Takže som teraz sa ľavý zoradená polovicu pôvodnej problém. 326 00:14:27,580 --> 00:14:30,847 Mám právo zoradené polovicu z pôvodnej problém. 327 00:14:30,847 --> 00:14:32,180 Čo je tretí a posledný krok? 328 00:14:32,180 --> 00:14:33,590 Oh, to je zlúčenie. 329 00:14:33,590 --> 00:14:34,480 Takže poďme to urobiť. 330 00:14:34,480 --> 00:14:36,420 Poďme prideliť niektoré ďalšie pamäť, ale môj Bože, 331 00:14:36,420 --> 00:14:37,503 ju mohol dať teraz kdekoľvek. 332 00:14:37,503 --> 00:14:40,356 Máme toľko miesta k dispozícii k nám, ale my budeme držať to jednoduché. 333 00:14:40,356 --> 00:14:42,730 Namiesto toho, aby šiel späť a ďalej s našou pôvodnou pamäťou, 334 00:14:42,730 --> 00:14:44,480 nech to jednoducho urobiť vizuálne tu dole, 335 00:14:44,480 --> 00:14:47,240 aby dokončiť zlúčenie ľavú polovicu a pravá polovica. 336 00:14:47,240 --> 00:14:49,279 >> Takže zlúčením, čo musím urobiť? 337 00:14:49,279 --> 00:14:50,820 Chcem, aby sa prvky v poradí. 338 00:14:50,820 --> 00:14:53,230 Takže pri pohľade na ľavej polovici, Vidím, prvé číslo je 2. 339 00:14:53,230 --> 00:14:55,230 Pozerám sa na pravú polovicu, Vidím prvé číslo 340 00:14:55,230 --> 00:14:58,290 je 1, tak samozrejme čo Číslo nechcem trhať von, 341 00:14:58,290 --> 00:15:00,430 a dal prvý v mojom konečnom zozname? 342 00:15:00,430 --> 00:15:01,449 Samozrejme, 1. 343 00:15:01,449 --> 00:15:02,990 Teraz chcem položiť túto rovnakú otázku. 344 00:15:02,990 --> 00:15:05,040 Na ľavej polovici, som stále číslo 2. 345 00:15:05,040 --> 00:15:07,490 Na pravej polovici, Mám číslo 3. 346 00:15:07,490 --> 00:15:08,930 Ktorý z nich si chcem vybrať? 347 00:15:08,930 --> 00:15:11,760 Samozrejme, že číslo 2 a Teraz si všimnúť kandidátov 348 00:15:11,760 --> 00:15:13,620 sú 4 vľavo, 3 vpravo. 349 00:15:13,620 --> 00:15:15,020 Poďme sa, samozrejme, vyberte 3. 350 00:15:15,020 --> 00:15:18,020 Teraz sú 4 kandidáti na ľavá, 5 na pravej strane. 351 00:15:18,020 --> 00:15:19,460 My, samozrejme, vyberte 4. 352 00:15:19,460 --> 00:15:21,240 6 na ľavej strane, 5 vpravo. 353 00:15:21,240 --> 00:15:22,730 My, samozrejme, vyberte 5. 354 00:15:22,730 --> 00:15:25,020 6 na ľavej strane, 7 na pravej strane. 355 00:15:25,020 --> 00:15:29,320 Vyberáme 6, a potom sme vybrať 7, a potom volíme 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Tak obrovské množstvo slov neskôr sme majú radené tento zoznam ôsmich prvkov 358 00:15:34,370 --> 00:15:38,450 do zoznamu jeden cez osem, ktorý je rastie s každým krokom, 359 00:15:38,450 --> 00:15:40,850 ale koľko času urobil trvať nás to urobiť. 360 00:15:40,850 --> 00:15:43,190 No som zámerne položenej veci obrazovo 361 00:15:43,190 --> 00:15:46,330 tu, takže môžeme druh vidieť alebo oceniť divíziu 362 00:15:46,330 --> 00:15:49,060 dobyť, že sa deje. 363 00:15:49,060 --> 00:15:52,830 >> V skutočnosti, keď sa pozriete späť na brázde, Nechala som všetky tieto prerušovanou čiarou 364 00:15:52,830 --> 00:15:55,660 V držiteľov mieste, môžete, druh, vidieť, v opačnom poradí, 365 00:15:55,660 --> 00:15:58,800 ak ste trochu obzrieť v História teraz, môj pôvodný zoznam 366 00:15:58,800 --> 00:16:00,250 Je, samozrejme, veľkosti 8. 367 00:16:00,250 --> 00:16:03,480 A potom už skôr, som bol zaoberajúce sa dvoma zoznamy veľkosti 4, 368 00:16:03,480 --> 00:16:08,400 a potom štyri zoznamy veľkosti 2, a potom osem zoznamy veľkosti 1. 369 00:16:08,400 --> 00:16:10,151 >> Takže to, čo robí to, druh, vás upozorní na? 370 00:16:10,151 --> 00:16:11,858 No, naozaj, niektoré z algoritmy sme 371 00:16:11,858 --> 00:16:14,430 Pozrel sa na tak ďaleko, kde sme rozdeľ a deliť, a rozdeliť, 372 00:16:14,430 --> 00:16:19,500 zachovať s veci znova, a opäť vedie v tomto všeobecnom myšlienke. 373 00:16:19,500 --> 00:16:23,100 A tak je tu niečo logaritmické tu deje. 374 00:16:23,100 --> 00:16:26,790 A nie je to úplne log n, ale tam je logaritmické komponentov 375 00:16:26,790 --> 00:16:28,280 k tomu, čo sme práve urobili. 376 00:16:28,280 --> 00:16:31,570 >> Teraz sa poďme zvážiť, ako to v skutočnosti je. 377 00:16:31,570 --> 00:16:34,481 Takže log n, opäť bol skvelý hrací čas, 378 00:16:34,481 --> 00:16:36,980 keď sme urobili niečo ako binárne vyhľadávanie, ako my teraz hovoríme, 379 00:16:36,980 --> 00:16:40,090 rozdeľ a panuj stratégie cez ktorý sme našli Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Teraz technicky. 381 00:16:41,020 --> 00:16:43,640 To je základ log 2 n, a to aj aj keď vo väčšine matematických tried, 382 00:16:43,640 --> 00:16:45,770 10 je zvyčajne bázy, ktorá sa domnievate. 383 00:16:45,770 --> 00:16:48,940 Ale počítačoví odborníci takmer vždy myslieť a hovoriť, pokiaľ ide o základni 2, 384 00:16:48,940 --> 00:16:52,569 takže sme sa všeobecne stačí povedať záznam n, namiesto toho, log základne 2 n, 385 00:16:52,569 --> 00:16:55,110 ale sú to presne jeden a To isté vo svete počítača 386 00:16:55,110 --> 00:16:57,234 vedy, a ako stranou, tam je konštantný faktor 387 00:16:57,234 --> 00:17:01,070 Rozdiel medzi týmito dvoma, takže je diskutabilné tak ako tak, pre viac formálnych dôvodov. 388 00:17:01,070 --> 00:17:04,520 >> Ale teraz, to, čo nás zaujíma o je tento príklad. 389 00:17:04,520 --> 00:17:08,520 Takže poďme nedokazuje príkladom, ale v aspoň na jeden príklad z čísel 390 00:17:08,520 --> 00:17:10,730 po ruke ako kontrola sanitačného, ​​ak chcete. 391 00:17:10,730 --> 00:17:14,510 Takže predtým vzorec bol základ log 2 n, ale to, čo je v tomto prípade n. 392 00:17:14,510 --> 00:17:18,526 Mal som n pôvodné čísla, alebo 8 z pôvodného počtu špecificky. 393 00:17:18,526 --> 00:17:20,359 Teraz už je to trochu zatiaľ čo, ale som celkom 394 00:17:20,359 --> 00:17:25,300 istí, že log základ 2 hodnoty 8 je 3, 395 00:17:25,300 --> 00:17:29,630 a naozaj, čo je pekné o ktorý je 3, ktorý je presne počet, koľkokrát 396 00:17:29,630 --> 00:17:33,320 že môžete rozdeliť zoznam dĺžky 8 znovu a znovu, 397 00:17:33,320 --> 00:17:36,160 a znovu, kým ste odišiel zoznamy iba veľkosti 1. 398 00:17:36,160 --> 00:17:36,660 Je to tak? 399 00:17:36,660 --> 00:17:40,790 8 ide do 4, ide do 2, ide k 1, a to je 400 00:17:40,790 --> 00:17:43,470 odrazom presne to picture mali sme pred chvíľou. 401 00:17:43,470 --> 00:17:47,160 Tak trochu zdravý rozum zistiť, kam logaritmus je vlastne jedná. 402 00:17:47,160 --> 00:17:50,180 >> Takže teraz, čo ešte sa tu jedná? n. 403 00:17:50,180 --> 00:17:53,440 Takže si všimnúť, že každý Keď som rozdelil zoznamu, 404 00:17:53,440 --> 00:17:58,260 aj keď v opačnom poradí v histórii tu, bol som stále robí n veci. 405 00:17:58,260 --> 00:18:02,320 Že zlúčenie krok vyžaduje, aby Dotknem každý jeden z čísel, 406 00:18:02,320 --> 00:18:05,060 aby to skĺznuť svojím vhodným umiestnením. 407 00:18:05,060 --> 00:18:10,760 Takže aj keď je výška tejto diagram je veľkosti log n n alebo 3, 408 00:18:10,760 --> 00:18:13,860 špecificky, inými slovami, Urobil som tri divízie sem. 409 00:18:13,860 --> 00:18:18,800 Koľko práce som urobil horizontálne pozdĺž tejto tabuľke zakaždým? 410 00:18:18,800 --> 00:18:21,110 >> No, ja som n kroky fungovať, pretože ak som 411 00:18:21,110 --> 00:18:24,080 dostal štyri elementy a štyri elementy, a musím zlúčiť dohromady. 412 00:18:24,080 --> 00:18:26,040 Musím prejsť tieto štyri a tieto štyri, 413 00:18:26,040 --> 00:18:28,123 nakoniec zlúčiť späť do ôsmich prvkov. 414 00:18:28,123 --> 00:18:32,182 Pokiaľ naopak mám osem prstov tu, čo nechcem, a ôsmich 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- či som dostal štyri prsty tu 416 00:18:34,390 --> 00:18:37,380 ktoré robím, štyri prsty tu, čo robím, 417 00:18:37,380 --> 00:18:40,590 potom je to rovnaké Príkladom ako predtým, keď to urobím 418 00:18:40,590 --> 00:18:44,010 majú osem prstov aj keď v celkom, ktorý som si, druh, áno. 419 00:18:44,010 --> 00:18:47,950 Môžem presne sa tu, potom som si určite 420 00:18:47,950 --> 00:18:50,370 zlúčiť všetky z týchto zoznamov o veľkosti 1, spoločne. 421 00:18:50,370 --> 00:18:54,050 Ale ja rozhodne sa pozrieť pri každom prvku práve raz. 422 00:18:54,050 --> 00:18:59,640 Takže je výška tohto procesu je log n, šírka tohto procesu, aby som tak povedal, 423 00:18:59,640 --> 00:19:02,490 je n, takže to, čo sa nám zdá, mať, nakoniec, je 424 00:19:02,490 --> 00:19:06,470 bežiaci čas o veľkosti n časy log n. 425 00:19:06,470 --> 00:19:08,977 >> Inými slovami, sme rozdelili zoznam, log n-krát, 426 00:19:08,977 --> 00:19:11,810 ale zakaždým, keď sme urobili, že sme mali dotknúť každý jeden z prvkov, 427 00:19:11,810 --> 00:19:13,560 za účelom ich zlúčenie dohromady, čo 428 00:19:13,560 --> 00:19:18,120 n bol krok, takže máme n-krát log n, alebo ako počítačový vedec by povedal, 429 00:19:18,120 --> 00:19:20,380 asymptoticky, ktorý by bolo veľké slovo 430 00:19:20,380 --> 00:19:22,810 popísať hornej viazané na jazdnej doby, 431 00:19:22,810 --> 00:19:28,010 sme sa beží vo veľkom O log n času, aby som tak povedal. 432 00:19:28,010 --> 00:19:31,510 >> Teraz je to významné, pretože spomenúť, čo beží časy boli 433 00:19:31,510 --> 00:19:34,120 bublinkové druhu, a výber triedenie a vkladanie triedenie, 434 00:19:34,120 --> 00:19:38,200 a dokonca aj niekoľko ďalších, ktoré existujú, n štvorcový bolo miesto, kde sme boli na. 435 00:19:38,200 --> 00:19:39,990 A môžete, druh, vidieť tu. 436 00:19:39,990 --> 00:19:45,720 Ak je na druhú n je samozrejme n krát n, ale tu máme n-krát log n, 437 00:19:45,720 --> 00:19:48,770 a my už poznáme z týždňa nula, že log n, logaritmické, 438 00:19:48,770 --> 00:19:50,550 je lepšie ako niečo lineárne. 439 00:19:50,550 --> 00:19:52,930 Koniec koncov, pripomínajú obraz s červenou a žltou 440 00:19:52,930 --> 00:19:56,500 a zelenej linky, ktoré sme vypracovali, tým green logaritmické línia bola oveľa nižšia. 441 00:19:56,500 --> 00:20:00,920 A preto, oveľa lepšie a rýchlejšie než rovných žltej a červenej čiary, 442 00:20:00,920 --> 00:20:05,900 n-krát log n je skutočne lepšie, než N-krát n, alebo n na druhú. 443 00:20:05,900 --> 00:20:09,110 >> Takže sa zdá, že sa identifikoval algoritmus zlúčenie 444 00:20:09,110 --> 00:20:11,870 druh, ktorý beží v oveľa rýchlejší, a dokonca, 445 00:20:11,870 --> 00:20:16,560 to je dôvod, prečo na začiatku tohto týždňa, kedy sme videli, že súťaž medzi bubliny 446 00:20:16,560 --> 00:20:20,750 triedenie, výber triediť, a zlúčiť triedenie, merge sort naozaj, ale naozaj vyhral. 447 00:20:20,750 --> 00:20:23,660 A skutočne, sme nemali ani čakať k Bubble druhu a výberu druhu 448 00:20:23,660 --> 00:20:24,790 až do konca. 449 00:20:24,790 --> 00:20:27,410 >> Teraz sa poďme jeden ďalší priechod na to, ze o niečo viac 450 00:20:27,410 --> 00:20:31,030 formálne perspektíva, len v prípad, to rezonuje lepšie 451 00:20:31,030 --> 00:20:33,380 než tejto vyššej úrovni diskusie. 452 00:20:33,380 --> 00:20:34,880 Takže tu je opäť algoritmus. 453 00:20:34,880 --> 00:20:36,770 Poďme sa sami seba opýtať, čo je doba chodu 454 00:20:36,770 --> 00:20:39,287 Je to algoritmy rôzne kroky? 455 00:20:39,287 --> 00:20:41,620 Poďme rozdeliť ho na prvý púzdro a druhý prípad. 456 00:20:41,620 --> 00:20:46,280 IF a iný v prípade, ak, IF n je menší ako 2, len sa vrátiť. 457 00:20:46,280 --> 00:20:47,580 Cítim sa ako konštantnom čase. 458 00:20:47,580 --> 00:20:50,970 Je to, druh, rovnako ako dvoch krokoch, IF n je menšie ako 2, potom sa vrátite. 459 00:20:50,970 --> 00:20:54,580 Ale ako sme si povedali v pondelok, konštantný čas, alebo veľký O 1, 460 00:20:54,580 --> 00:20:57,130 môžu byť dve, tri kroky kroky, dokonca aj 1000 krokov. 461 00:20:57,130 --> 00:20:59,870 Dôležité je, že je to konštantný počet krokov. 462 00:20:59,870 --> 00:21:03,240 Takže žltý zvýraznené pseudocode tu beží v, budeme hovoriť, 463 00:21:03,240 --> 00:21:04,490 konštantný čas. 464 00:21:04,490 --> 00:21:06,780 Takže viac formálne, a ideme to-- to 465 00:21:06,780 --> 00:21:09,910 bude miera, do ktorej formalizovať toto právo now-- T n, 466 00:21:09,910 --> 00:21:15,030 bežiaci čas problému že sa n somethings ako vstup, 467 00:21:15,030 --> 00:21:19,150 rovná big o jednej, IF n je menšie ako 2. 468 00:21:19,150 --> 00:21:20,640 Takže je to podmienené to. 469 00:21:20,640 --> 00:21:24,150 Tak aby bolo jasno, keď n je menšia ako 2, máme veľmi krátky zoznam, potom 470 00:21:24,150 --> 00:21:29,151 Doba chodu, T n, kde n je 1 alebo 0, v tomto veľmi špecifickom prípade, 471 00:21:29,151 --> 00:21:30,650 je to len bude konštantný čas. 472 00:21:30,650 --> 00:21:32,691 Bude to trvať jeden krok, dva kroky, čokoľvek. 473 00:21:32,691 --> 00:21:33,950 Je to pevne stanovený počet krokov. 474 00:21:33,950 --> 00:21:38,840 >> Takže šťavnaté časť musí určite byť v Druhým prípadom v pseudokódu. 475 00:21:38,840 --> 00:21:40,220 Prípad ELSE. 476 00:21:40,220 --> 00:21:44,870 Triediť ľavú polovicu prvkov, triediť vpravo polovica z prvkov, zlúčiť triedených polovičky. 477 00:21:44,870 --> 00:21:46,800 Ako dlho trvá každý z týchto krokov trvať? 478 00:21:46,800 --> 00:21:49,780 No, v prípade, že beží čas, aby triediť n prvkov 479 00:21:49,780 --> 00:21:53,010 je, nazvime to veľmi všeobecne, T n, 480 00:21:53,010 --> 00:21:55,500 potom triedenie ľavú polovica elementov 481 00:21:55,500 --> 00:21:59,720 je trochu, ako hovoriť, T n delené 2, 482 00:21:59,720 --> 00:22:03,000 a podobne triedenie pravú polovicu prvkov je, druh, ako hovoriť, 483 00:22:03,000 --> 00:22:06,974 T n rozdelená 2, a potom zlučovanie zoradené polovice. 484 00:22:06,974 --> 00:22:08,890 No, ak mám nejaký počet prvkov tu, 485 00:22:08,890 --> 00:22:11,230 rovnako ako štyri, a nejaké číslo prvkov tu, rovnako ako štyri, 486 00:22:11,230 --> 00:22:14,650 a ja musím zlúčiť každej z týchto štyroch v, a každé z týchto štyroch v, jeden 487 00:22:14,650 --> 00:22:17,160 po druhom tak, že nakoniec Mám osem prvkov. 488 00:22:17,160 --> 00:22:20,230 Vyzerá to, že to je veľká o n krokov? 489 00:22:20,230 --> 00:22:23,500 Ak mám n prstov a každý z im musia byť zlúčené do miesta, 490 00:22:23,500 --> 00:22:25,270 to je ako ďalší n krokov. 491 00:22:25,270 --> 00:22:27,360 >> Takže naozaj formulaically, môžeme vyjadriť to, 492 00:22:27,360 --> 00:22:29,960 aj keď trochu desivo sprvu pohľad, ale je to niečo 493 00:22:29,960 --> 00:22:31,600 ktorý zachytáva presne túto logiku. 494 00:22:31,600 --> 00:22:35,710 Doba behu, T n, n IF je väčší alebo rovné 2. 495 00:22:35,710 --> 00:22:42,500 V tomto prípade, ELSE prípade je T n deleno 2 plus T n delené 2, 496 00:22:42,500 --> 00:22:45,320 a veľký o n, niektoré lineárne počet krokov, 497 00:22:45,320 --> 00:22:51,630 možno presne n, možno 2 krát n, ale je to zhruba, poradie n. 498 00:22:51,630 --> 00:22:54,060 Tak to tiež, je to, ako môžeme to vyjadriť formulaically. 499 00:22:54,060 --> 00:22:56,809 Teraz už by nepoznal, pokiaľ to nie je ktoré ste nahrali vo svojej mysli, 500 00:22:56,809 --> 00:22:58,710 alebo hľadať to v zadné učebnice, že 501 00:22:58,710 --> 00:23:00,501 môže mať trochu cheat sheet na konci, 502 00:23:00,501 --> 00:23:03,940 ale to je naozaj ísť do nám veľkú o n log n, 503 00:23:03,940 --> 00:23:06,620 pretože opakovanie, že vidíte tu na obrazovke, 504 00:23:06,620 --> 00:23:09,550 ak ste vlastne robil to, s nekonečný počet príkladov, 505 00:23:09,550 --> 00:23:13,000 alebo ste to urobil formulaically, že nie vidieť, že to, pretože tento vzorec 506 00:23:13,000 --> 00:23:17,100 sám o sebe je rekurzívne, s t n nad niečím na pravej strane, 507 00:23:17,100 --> 00:23:21,680 a t o n cez na ľavej strane, to môže v skutočnosti byť vyjadrené, v konečnom dôsledku, 508 00:23:21,680 --> 00:23:24,339 ako veľký go n log n. 509 00:23:24,339 --> 00:23:26,130 Ak tomu tak nie je presvedčený o tom, že je to pokuta pre túto chvíľu, len 510 00:23:26,130 --> 00:23:28,960 vziať na viere, že to je, naozaj, čo to vedie k opakovaniu, 511 00:23:28,960 --> 00:23:31,780 ale to je len trochu viac matematický prístup k pozerá 512 00:23:31,780 --> 00:23:36,520 v bežiaci dobe merge sort na základe svojho pseudokódu sám. 513 00:23:36,520 --> 00:23:39,030 >> Teraz sa poďme trochu prieduch z všetko, 514 00:23:39,030 --> 00:23:41,710 a vziať pozrieť sa na istý bývalý senátor, ktorý 515 00:23:41,710 --> 00:23:44,260 môže vyzerať trochu povedomý, kto si sadol s Google Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, pred časom, na pohovor na pódiu, v prednej časti celá partia 517 00:23:48,410 --> 00:23:53,710 ľudí, hovorí nakoniec o téma, to je celkom teraz povedomý. 518 00:23:53,710 --> 00:23:54,575 Poďme sa pozrieť. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Teraz Senator, si tu na Google, 521 00:24:03,890 --> 00:24:09,490 a ja som rád myslieť na Predsedníctvo ako pracovný pohovor. 522 00:24:09,490 --> 00:24:11,712 Teraz je ťažké zohnať prácu ako prezident. 523 00:24:11,712 --> 00:24:12,670 Prezident Obama: Správne. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: A ty si robiť [nepočuteľný] teraz. 525 00:24:13,940 --> 00:24:15,523 Je tiež ťažké získať prácu v spoločnosti Google. 526 00:24:15,523 --> 00:24:17,700 Prezident Obama: Správne. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Máme otázky, a žiadame našich kandidátov otázky 528 00:24:21,330 --> 00:24:24,310 a toto je od Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> Prezident Obama: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Čo? 531 00:24:27,005 --> 00:24:28,130 Myslíte si robím srandu? 532 00:24:28,130 --> 00:24:30,590 Je to priamo tu. 533 00:24:30,590 --> 00:24:33,490 Aký je najúčinnejší spôsob, ako triediť milión 32 bit celé číslo? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> Prezident Obama: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Niekedy Možno mi to ľúto, maybe-- 537 00:24:41,020 --> 00:24:42,750 Prezident Obama: Nie, nie, Nie, nie, nie, ja think-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: To nie je to-- 539 00:24:43,240 --> 00:24:45,430 Prezident Obama: Ja myslím, myslím, že bublinu 540 00:24:45,430 --> 00:24:46,875 sort by bol zlý spôsob, ako ísť. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Poď. 543 00:24:50,535 --> 00:24:52,200 Kto mu to povedal? 544 00:24:52,200 --> 00:24:54,020 OK. 545 00:24:54,020 --> 00:24:55,590 Nechcel som počítač veda on-- 546 00:24:55,590 --> 00:24:58,986 >> Prezident Obama: Máme dostal svoje špehov tam. 547 00:24:58,986 --> 00:24:59,860 Profesor: Dobre. 548 00:24:59,860 --> 00:25:03,370 Nechajme za nami teraz teoretický svet algoritmov 549 00:25:03,370 --> 00:25:06,520 v asymptotickej analýze tejto zmluvy, a vrátiť sa do niektoré témy 550 00:25:06,520 --> 00:25:09,940 týždeň od nuly do jednej, a začiatok odstrániť niektoré kolieska, 551 00:25:09,940 --> 00:25:10,450 ak chcete. 552 00:25:10,450 --> 00:25:13,241 Aby ste naozaj pochopiť, nakoniec od základov, čo je 553 00:25:13,241 --> 00:25:16,805 deje pod kapotou, keď vás písať, kompilovať a spúšťať programy. 554 00:25:16,805 --> 00:25:19,680 Pripomeňme, a najmä, že je to Prvý program v jazyku C sme sa na, 555 00:25:19,680 --> 00:25:22,840 kánonický, jednoduchý program druhov, relatívne vzaté, 556 00:25:22,840 --> 00:25:24,620 kde, vytlačí, Hello World. 557 00:25:24,620 --> 00:25:27,610 A Spomínam si, že som povedal, proces že zdrojový kód prechádza 558 00:25:27,610 --> 00:25:28,430 je presne to. 559 00:25:28,430 --> 00:25:31,180 Beriete zdrojového kódu, prejsť to cez kompilátor, ako je Clang, 560 00:25:31,180 --> 00:25:34,650 a von vychádza strojový kód, ktorý môže vyzerať takto, núl a jednotiek 561 00:25:34,650 --> 00:25:37,880 že procesor počítača, centrálne procesorová jednotka alebo mozgu, 562 00:25:37,880 --> 00:25:39,760 nakoniec chápe. 563 00:25:39,760 --> 00:25:42,460 >> Ukázalo sa, že je to bit ako zjednodušujúce, 564 00:25:42,460 --> 00:25:44,480 že sme teraz v Postoj k srandista oddelene 565 00:25:44,480 --> 00:25:46,720 pochopiť, čo to naozaj bolo deje pod kapotou 566 00:25:46,720 --> 00:25:48,600 zakaždým, keď spustíte Clang, alebo všeobecnejšie, 567 00:25:48,600 --> 00:25:53,040 zakaždým, keď program, pomocou funkcie Uskutočniť a CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Najmä, veci ako to je najprv generovaný, 569 00:25:56,760 --> 00:25:58,684 pri prvom kompilácii programu. 570 00:25:58,684 --> 00:26:00,600 Inými slovami, keď vás vezmite si zdrojový kód 571 00:26:00,600 --> 00:26:04,390 a skompilovať, čo je najprv bytia výstupu by Clang 572 00:26:04,390 --> 00:26:06,370 je niečo, čo poznám ako assembleri. 573 00:26:06,370 --> 00:26:08,990 A v skutočnosti, to vyzerá presne ako to. 574 00:26:08,990 --> 00:26:11,170 >> Bežal som príkaz u príkazového riadku skôr. 575 00:26:11,170 --> 00:26:16,260 Rinčať DASH veľkým S hello.c, a to vytvorili súbor 576 00:26:16,260 --> 00:26:19,490 pre mňa volal hello.s, vnútri ktoré boli presne 577 00:26:19,490 --> 00:26:22,290 tieto obsahy, a trochu viac vyššie a trochu nižšie, 578 00:26:22,290 --> 00:26:25,080 ale ja som dal nejšťavnatější Informácie tu na obrazovke. 579 00:26:25,080 --> 00:26:29,190 A keď sa pozriete pozorne, uvidíte, aspoň niekoľko známych kľúčové slová. 580 00:26:29,190 --> 00:26:31,330 Máme hlavné hore. 581 00:26:31,330 --> 00:26:35,140 Máme printf dole uprostred. 582 00:26:35,140 --> 00:26:38,670 A máme tiež hello world spätné lomítko n v úvodzovkách dole. 583 00:26:38,670 --> 00:26:42,450 >> A všetko ostatné tu je návod na veľmi nízkej úrovni 584 00:26:42,450 --> 00:26:45,500 že procesor počítača rozumie. 585 00:26:45,500 --> 00:26:50,090 Pokyny pre CPU, ktoré sa pohybujú pamäť okolo, že zaťaženie struny z pamäte, 586 00:26:50,090 --> 00:26:52,750 a nakoniec, tlač veci na obrazovke. 587 00:26:52,750 --> 00:26:56,780 Teraz, čo sa stane, keď po Táto zostava kód je generovaný? 588 00:26:56,780 --> 00:26:59,964 Nakoniec, to urobíte, naozaj, ešte tvoriť objektový kód. 589 00:26:59,964 --> 00:27:02,630 Ale kroky, ktoré majú naozaj sa deje pod kapotou 590 00:27:02,630 --> 00:27:04,180 vyzerať trochu viac ako je tento. 591 00:27:04,180 --> 00:27:08,390 Zdrojový kód sa stáva kód assembleri, ktorý sa potom stáva kód objektu, 592 00:27:08,390 --> 00:27:11,930 a operatívne pojmy sú to, pri kompilácii zdrojového kódu, 593 00:27:11,930 --> 00:27:16,300 out príde kód montáž, a potom keď si zostaviť svoju assembleri, 594 00:27:16,300 --> 00:27:17,800 out príde objektový kód. 595 00:27:17,800 --> 00:27:20,360 >> Teraz Clang je super sofistikované, ako veľa prekladačov, 596 00:27:20,360 --> 00:27:23,151 a to robí všetky tieto kroky dohromady, a to nie je nevyhnutne 597 00:27:23,151 --> 00:27:25,360 Výstup akýkoľvek medziprodukt súbory, ktoré môžete dokonca vidieť. 598 00:27:25,360 --> 00:27:28,400 Proste kompiluje veci, čo je všeobecný pojem, ktorý 599 00:27:28,400 --> 00:27:30,000 opisuje celý tento proces. 600 00:27:30,000 --> 00:27:32,000 Ale ak naozaj chcete byť konkrétny, je tu 601 00:27:32,000 --> 00:27:34,330 oveľa viac deje aj tam. 602 00:27:34,330 --> 00:27:38,860 >> Ale poďme sa tiež zvážiť, že aj teraz že mimoriadne jednoduchý program, hello.c, 603 00:27:38,860 --> 00:27:40,540 nazýva funkcie. 604 00:27:40,540 --> 00:27:41,870 Vyzvala printf. 605 00:27:41,870 --> 00:27:46,900 Ale ja som nepísal printf, naozaj, ktorý je dodávaný s c, aby som tak povedal. 606 00:27:46,900 --> 00:27:51,139 Je to funkcia, pripomeňme, že je to deklarovaný v štandardnom IO.H, ktorý 607 00:27:51,139 --> 00:27:53,180 je súbor hlavičky, ktorý je téma, budeme vlastne 608 00:27:53,180 --> 00:27:55,780 ponoriť do väčšej hĺbky, ako dlhý. 609 00:27:55,780 --> 00:27:58,000 Ale hlavičkový súbor je zvyčajne sprevádzané 610 00:27:58,000 --> 00:28:02,920 súborom kódu, zdrojový kód súboru, takže rovnako ako existuje štandardná io.h. 611 00:28:02,920 --> 00:28:05,930 >> Pred nejakým časom, niekto, alebo niečí, tiež písal 612 00:28:05,930 --> 00:28:11,040 súbor s názvom štandardné io.c, v ktorý sú skutočné definície, 613 00:28:11,040 --> 00:28:15,220 alebo implementácia printf, a trsy ďalších funkcií, 614 00:28:15,220 --> 00:28:16,870 sú v skutočnosti v písomnej forme. 615 00:28:16,870 --> 00:28:22,140 Takže vzhľadom k tomu, že, ak vezmeme do úvahy s tu na ľavej strane, hello.c, že ​​keď 616 00:28:22,140 --> 00:28:26,250 zostavovať, nám dáva hello.s, aj keď Clang netrápi úspory v mieste 617 00:28:26,250 --> 00:28:31,360 môžeme vidieť, a že kód zhromaždenie dostane zostavené do hello.o, ktorý 618 00:28:31,360 --> 00:28:34,630 je, naozaj, predvolený názov vzhľadom k tomu, kedykoľvek budete kompilovať zdroje 619 00:28:34,630 --> 00:28:39,350 kód do objektového kódu, ale nie sú úplne pripravený vykonať ho ešte, 620 00:28:39,350 --> 00:28:41,460 pretože ďalší krok sa musí stať, a má 621 00:28:41,460 --> 00:28:44,440 dialo v posledných niekoľkých týždňov, možno bez vášho vedomia k vám. 622 00:28:44,440 --> 00:28:47,290 >> Konkrétne niekde V CS50 IDE, a to, 623 00:28:47,290 --> 00:28:49,870 Tiež bude tak trochu oversimplification na chvíľu, 624 00:28:49,870 --> 00:28:54,670 tam je, alebo bol na nejaký čas, súbor s názvom štandardné io.c, 625 00:28:54,670 --> 00:28:58,440 že niekto zostavil do štandardné io.s alebo ekvivalent, 626 00:28:58,440 --> 00:29:02,010 že niekto potom zhromaždil do štandardného io.o, 627 00:29:02,010 --> 00:29:04,600 alebo sa ukáže na A mierne odlišný súbor 628 00:29:04,600 --> 00:29:07,220 formát, ktorý môže mať iný príponu súboru úplne, 629 00:29:07,220 --> 00:29:11,720 ale v teórii a koncepčne, presne tie kroky sa muselo stať v nejakej forme. 630 00:29:11,720 --> 00:29:14,060 Čo znamená, že teraz keď píšem program, 631 00:29:14,060 --> 00:29:17,870 hello.c, že ​​len hovorí, hello world, a ja som s použitím kódu niekoho iného 632 00:29:17,870 --> 00:29:22,480 ako printf, ktorý bol kedysi čas, v súbore s názvom štandardné io.c, 633 00:29:22,480 --> 00:29:26,390 potom nejako musím Take My objektový kód, moji nuly a jednotky, 634 00:29:26,390 --> 00:29:29,260 a že osoby objekt kódu alebo nuly a jednotky, 635 00:29:29,260 --> 00:29:34,970 a nejako spojiť ich do jeden posledný súbor, nazvaný ahoj, že 636 00:29:34,970 --> 00:29:38,070 má všetky núl a tie z mojej hlavnú funkciu, 637 00:29:38,070 --> 00:29:40,830 a všetky núl a tie pre printf. 638 00:29:40,830 --> 00:29:44,900 >> A naozaj, že posledný proces je volal, spájajúcej vaše objektový kód. 639 00:29:44,900 --> 00:29:47,490 Ktorého výstup je spustiteľný súbor. 640 00:29:47,490 --> 00:29:49,780 Takže v spravodlivosť, u koniec dňa, nič 641 00:29:49,780 --> 00:29:52,660 zmenilo od týždňa jedna, keď sme Prvý začal zostavovaní programov. 642 00:29:52,660 --> 00:29:55,200 V skutočnosti, je to všetko deje pod kapotou, 643 00:29:55,200 --> 00:29:57,241 ale teraz sme v situácii, kde môžeme skutočne 644 00:29:57,241 --> 00:29:58,794 srandista oddelene tieto jednotlivé kroky. 645 00:29:58,794 --> 00:30:00,710 A skutočne, na konci dňa, sme stále 646 00:30:00,710 --> 00:30:04,480 odišiel s núl a jednotiek, ktoré je skutočne skvelý segue teraz 647 00:30:04,480 --> 00:30:08,620 na iné schopnosti C, ktorá sme nemali využívať najväčšou pravdepodobnosťou 648 00:30:08,620 --> 00:30:11,250 k dnešnému dňu, známy ako operátory bitové. 649 00:30:11,250 --> 00:30:15,220 Inými slovami, tak ďaleko, kedykoľvek máme zaoberal s dátami v C alebo premenných v C, 650 00:30:15,220 --> 00:30:17,660 sme mali veci, ako znaky a plaváky a ins 651 00:30:17,660 --> 00:30:21,990 a túžia a dvojlôžkové a podobne, ale všetky z nich sú najmenej osem bitov. 652 00:30:21,990 --> 00:30:25,550 My sme ešte nikdy nebol schopný manipulovať s jednotlivými bitmi, 653 00:30:25,550 --> 00:30:28,970 aj keď individuálna bitu, sme Viete, môžu predstavovať 0 a 1. 654 00:30:28,970 --> 00:30:32,640 Teraz sa ukazuje, že v C, vy môžu získať prístup k jednotlivých bitov, 655 00:30:32,640 --> 00:30:35,530 ak viete, syntax, s ktorými sa dostať na ne. 656 00:30:35,530 --> 00:30:38,010 >> Takže poďme sa pozrieť na operátorov bitové. 657 00:30:38,010 --> 00:30:41,700 Tak tu na snímke je niekoľko symboly, ktoré sme sa, druh, druh, predtým nevidel. 658 00:30:41,700 --> 00:30:45,580 Vidím ampersand, vertikálne bar, a niektoré ďalšie, rovnako, 659 00:30:45,580 --> 00:30:49,430 a pripomenula, že ampersand ampersand je niečo, čo sme nevideli. 660 00:30:49,430 --> 00:30:54,060 Logická AND operátor, kde musíte dvaja z nich spoločne, alebo logické OR 661 00:30:54,060 --> 00:30:56,300 operátor, kde na vás majú dva zvislé pruhy. 662 00:30:56,300 --> 00:31:00,550 Bitové operátory, ktoré budeme pozri fungujú na bity jednotlivo, 663 00:31:00,550 --> 00:31:03,810 stačí použiť jeden ampersand, je single zvislá čiara, strieška symbol 664 00:31:03,810 --> 00:31:06,620 príde nabudúce, malý vlnovky, a potom doľava 665 00:31:06,620 --> 00:31:08,990 držiak ľavý držiak, alebo pravá zátvorka pravá zátvorka. 666 00:31:08,990 --> 00:31:10,770 Každý z nich má rôzne významy. 667 00:31:10,770 --> 00:31:11,950 >> V skutočnosti, poďme sa pozrieť. 668 00:31:11,950 --> 00:31:16,560 Poďme stará škola dnes, a použitie dotyková obrazovka z dávnych čias, 669 00:31:16,560 --> 00:31:18,002 známy ako bielu tabuľu. 670 00:31:18,002 --> 00:31:19,710 A to biele tabule bude nám neumožňuje, 671 00:31:19,710 --> 00:31:27,360 vyjadrovať niektoré celkom jednoduché symboly, alebo skôr niektoré pomerne jednoduché vzorce, 672 00:31:27,360 --> 00:31:29,560 že sa potom môžeme nakoniec pákový efekt, za účelom 673 00:31:29,560 --> 00:31:33,230 individuálny prístup bity v rámci programu C. 674 00:31:33,230 --> 00:31:34,480 Inými slovami, ideme na to. 675 00:31:34,480 --> 00:31:37,080 Rokov prvý hovoriť Aby moment o ampersand, 676 00:31:37,080 --> 00:31:39,560 čo je bitové operácie AND operátor. 677 00:31:39,560 --> 00:31:42,130 Inými slovami, je to operátor, ktorý umožňuje 678 00:31:42,130 --> 00:31:45,930 aby som si ľavostranné premenné typicky, a pravá variabilné, 679 00:31:45,930 --> 00:31:50,640 alebo individuálne hodnotu, že ak budeme A je dohromady, mi dáva konečný výsledok. 680 00:31:50,640 --> 00:31:51,560 Tak čo mám na mysli? 681 00:31:51,560 --> 00:31:54,840 Ak je v programe, máte premennú , Ktorý ukladá jednu z týchto hodnôt, 682 00:31:54,840 --> 00:31:58,000 alebo povedzme, aby to jednoduché, a len vypísať nulami a jednotkami jednotlivo, 683 00:31:58,000 --> 00:32:00,940 Tu je návod, ako operátor ampersand funguje. 684 00:32:00,940 --> 00:32:06,400 0 ampersand 0 sa bude rovnať 0. 685 00:32:06,400 --> 00:32:07,210 Teraz prečo je tomu tak? 686 00:32:07,210 --> 00:32:09,291 >> Je to veľmi podobné Boolean výrazy, 687 00:32:09,291 --> 00:32:10,540 že sme diskutovali doteraz. 688 00:32:10,540 --> 00:32:15,800 Ak si myslíte, že po tom všetkom, 0 false, 0 je false, false false 689 00:32:15,800 --> 00:32:18,720 je, ako sme diskutovali logicky, tiež falošné. 690 00:32:18,720 --> 00:32:20,270 Tak dostaneme 0 i tu. 691 00:32:20,270 --> 00:32:24,390 Ak budete mať 0 ampersand 1, dobre, že taky, 692 00:32:24,390 --> 00:32:29,890 bude byť 0, pretože pre tento ľavá expresie aby to bola pravda alebo 1, 693 00:32:29,890 --> 00:32:32,360 to by musela byť pravdivá a pravdivá. 694 00:32:32,360 --> 00:32:36,320 Ale tu máme false a pravdivé, alebo 0 a 1. 695 00:32:36,320 --> 00:32:42,000 A teraz zase, ak máme 1 ampersand 0, to tiež bude 0, 696 00:32:42,000 --> 00:32:47,240 a ak budeme mať 1 ampersand 1, Nakoniec to máme 1 bit. 697 00:32:47,240 --> 00:32:50,340 Takže inými slovami, my nerobíme niečo zaujímavého s týmto operátorom 698 00:32:50,340 --> 00:32:51,850 ešte nie, tento operátor ampersand. 699 00:32:51,850 --> 00:32:53,780 Je to bitové operácie AND operátor. 700 00:32:53,780 --> 00:32:57,290 Ale to sú ingrediencie cez ktorý môžeme urobiť 701 00:32:57,290 --> 00:32:59,240 zaujímavých vecí, ako skoro uvidíme. 702 00:32:59,240 --> 00:33:02,790 >> Teraz sa poďme pozrieť na práve jeden zvislá čiara tu na pravej strane. 703 00:33:02,790 --> 00:33:06,710 Ak mám 0 bit a I ALEBO to s, bitové 704 00:33:06,710 --> 00:33:11,030 OR operátor, ďalší 0 bit, , Čo sa deje, aby mi 0. 705 00:33:11,030 --> 00:33:17,540 Ak by som sa trochu 0 a alebo to s 1 bit, a potom budem mať 1. 706 00:33:17,540 --> 00:33:19,830 A v skutočnosti, len pre jasnosť, nechaj ma ísť späť, 707 00:33:19,830 --> 00:33:23,380 takže moje zvislé pruhy nie sú spliesť 1 je. 708 00:33:23,380 --> 00:33:26,560 Dovoľte mi, aby som prepísať všetky môj 1 je trochu viac 709 00:33:26,560 --> 00:33:32,700 Je zrejmé, že tak, že vedľa vidieť, ak je I majú 1 alebo 0, že to bude 1, 710 00:33:32,700 --> 00:33:39,060 a keď mám 1 alebo 1, ktorá, Tiež bude 1. 711 00:33:39,060 --> 00:33:42,900 Takže môžete vidieť, že logicky OR operátor sa chová veľmi odlišne. 712 00:33:42,900 --> 00:33:48,070 To mi dáva 0 alebo 0 mi dáva 0, ale každá iná kombinácia mi dáva 1. 713 00:33:48,070 --> 00:33:52,480 Tak dlho, ako budem mať jeden 1 V vzorec, výsledok bude 1. 714 00:33:52,480 --> 00:33:55,580 >> Na rozdiel od AND operátor, ampersand, 715 00:33:55,580 --> 00:34:00,940 iba vtedy, keď mám dve 1 je v rovnice, môžem skutočne dostať do vedenia 1 out. 716 00:34:00,940 --> 00:34:02,850 Teraz je tu niekoľko ďalších Prevádzkovatelia rovnako. 717 00:34:02,850 --> 00:34:04,810 Jedným z nich je trochu viac zapojiť. 718 00:34:04,810 --> 00:34:07,980 Tak nechaj ma ísť dopredu a vymazať to, aby sa uvoľnili nejaké miesto. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 A poďme sa pozrieť na strieška symbol, len na chvíľu. 721 00:34:16,460 --> 00:34:18,210 Toto je typicky znak môžete zadať 722 00:34:18,210 --> 00:34:21,420 na klávesnici SHIFT a potom jedno z čísel na vrcholku vašej USA 723 00:34:21,420 --> 00:34:22,250 klávesnice. 724 00:34:22,250 --> 00:34:26,190 >> Tak toto je exkluzívny OR operátor, exclusive OR. 725 00:34:26,190 --> 00:34:27,790 Takže sme práve videli prevádzkovateľom alebo. 726 00:34:27,790 --> 00:34:29,348 Toto je exkluzívny OR operátor. 727 00:34:29,348 --> 00:34:30,639 Aký je vlastne rozdiel? 728 00:34:30,639 --> 00:34:34,570 Tak poďme stačí sa pozrieť na vzorec, a použiť ako prísady v konečnom dôsledku. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Ja som chcel povedať, je vždy 0. 731 00:34:39,650 --> 00:34:41,400 To je definícia XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 bude 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 bude 1, a 1 XOR 1 bude? 734 00:34:58,810 --> 00:34:59,890 Zlé? 735 00:34:59,890 --> 00:35:00,520 Alebo nie? 736 00:35:00,520 --> 00:35:01,860 Neviem. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 A teraz, čo sa tu deje? 739 00:35:04,700 --> 00:35:06,630 No premýšľať o názov tohto operátora. 740 00:35:06,630 --> 00:35:09,980 Exkluzívny OR, tak ako meno, druh, naznačuje, 741 00:35:09,980 --> 00:35:13,940 odpoveď bude iba 1, ak vstupy sú exkluzívne, 742 00:35:13,940 --> 00:35:15,560 výhradne rôzne. 743 00:35:15,560 --> 00:35:18,170 Tak tu vstupy sú rovnaké, takže na výstupe je 0. 744 00:35:18,170 --> 00:35:20,700 Tu vstupy sú rovnaké, takže na výstupe je 0. 745 00:35:20,700 --> 00:35:25,640 Tu sú výstupy sú odlišné, sú exkluzívne, a tak výstup je 1. 746 00:35:25,640 --> 00:35:28,190 Takže je to veľmi podobné A je to veľmi podobné, 747 00:35:28,190 --> 00:35:32,760 alebo skôr je to veľmi podobné OR, ale iba v exkluzívnom spôsobom. 748 00:35:32,760 --> 00:35:36,210 Táto je už nie je 1, pretože máme dve 1 je, 749 00:35:36,210 --> 00:35:38,621 a nie výlučne, len jeden z nich. 750 00:35:38,621 --> 00:35:39,120 Dobre. 751 00:35:39,120 --> 00:35:40,080 A čo ostatní? 752 00:35:40,080 --> 00:35:44,220 No tilda, zatiaľ, je skutočne pekný a jednoduchý, našťastie. 753 00:35:44,220 --> 00:35:46,410 A to je unárne operátor, čo znamená, že 754 00:35:46,410 --> 00:35:50,400 to je aplikovaný len na jeden vstup, jedným operand, aby som tak povedal. 755 00:35:50,400 --> 00:35:51,800 Nie je na ľavej a pravej. 756 00:35:51,800 --> 00:35:56,050 Inými slovami, ak budete mať na vlnovku 0, odpoveď bude opačný. 757 00:35:56,050 --> 00:35:59,710 A ak budete mať vlnovky z 1, odpoveď bude naopak. 758 00:35:59,710 --> 00:36:02,570 Takže tilda prevádzkovateľ spôsob, ako negovanie trochu, 759 00:36:02,570 --> 00:36:06,000 alebo obracející kúsok od 0-1, alebo od 1 do 0 ° C. 760 00:36:06,000 --> 00:36:09,820 >> A to nás necháva konečne s iba dvoma konečnými operátormi, 761 00:36:09,820 --> 00:36:13,840 tzv doľava posun, a takzvaný doprava operátor posunu. 762 00:36:13,840 --> 00:36:16,620 Poďme sa pozrieť na to, ako tejto práci. 763 00:36:16,620 --> 00:36:20,780 Prevádzkovateľ vľavo posun, písaný s dvoma lomených zátvorkách, ako je to, 764 00:36:20,780 --> 00:36:22,110 pracuje nasledovne. 765 00:36:22,110 --> 00:36:27,390 Ak je môj vstup, alebo má operand, vľavo operátor posun je jednoducho 1. 766 00:36:27,390 --> 00:36:33,750 A ja potom povedať počítača na je vľavo posun, že 1, povedzme sedem miest, 767 00:36:33,750 --> 00:36:37,150 Výsledkom je, ako by som prijať, že 1, a presunúť ju 768 00:36:37,150 --> 00:36:40,160 sedem miest, viac ako na vľavo, a v predvolenom nastavení, 769 00:36:40,160 --> 00:36:42,270 budeme predpokladať, že priestor na pravej strane 770 00:36:42,270 --> 00:36:44,080 sa bude orezaný nulami. 771 00:36:44,080 --> 00:36:50,316 Inými slovami, 1 nechalo posun 7 sa deje aby mi, že 1, nasledovaný 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 nuly. 773 00:36:54,060 --> 00:36:57,380 Takže svojím spôsobom to vám umožní trvať malé množstvo ako 1, 774 00:36:57,380 --> 00:37:00,740 a jasne, aby to veľa oveľa, oveľa väčšie, týmto spôsobom, 775 00:37:00,740 --> 00:37:06,460 ale my sme vlastne bude vidieť múdrejší prístupy k nej 776 00:37:06,460 --> 00:37:08,080 namiesto toho, ako aj, 777 00:37:08,080 --> 00:37:08,720 >> Dobre. 778 00:37:08,720 --> 00:37:10,060 To je pre tri týždeň. 779 00:37:10,060 --> 00:37:11,400 Uvidíme sa nabudúce. 780 00:37:11,400 --> 00:37:12,770 To bolo CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Prehrávanie hudby] 783 00:37:22,243 --> 00:37:25,766 >> Reproduktor 1: On bol u občerstvenia bar jesť hot fudge pohár. 784 00:37:25,766 --> 00:37:28,090 Mal to všetko cez tvár. 785 00:37:28,090 --> 00:37:30,506 Má na sebe, že čokoláda ako fúzy 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Čo to robíš? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Čo? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Vedeli ste práve double dip? 790 00:37:36,800 --> 00:37:38,585 Tie double ponoril čipu. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Prepáčte. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: ponoril ste čip, budete vzal sústo, a znovu ponoril. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Takže to je ako dávať Celá vaše ústa priamo v dip. 795 00:37:48,440 --> 00:37:52,400 Nabudúce budete mať čip, ponoriť len raz, a nakoniec to. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Vieš čo, Dane? 797 00:37:53,890 --> 00:37:58,006 Môžete ponoriť spôsob, akým chcete ponoriť. 798 00:37:58,006 --> 00:38:01,900 Budem ponoriť spôsob, akým chcem ponoriť. 799 00:38:01,900 --> 00:38:03,194