1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: V redu, to je CS50. 3 00:00:14,910 --> 00:00:19,020 To je konec tritedenskega, in če niste izkoristili že, 4 00:00:19,020 --> 00:00:21,790 vem, da bo kosilo ta petek, kot je običajno, kadar 5 00:00:21,790 --> 00:00:25,430 boste lahko uživali dober pogovor in hrane na Fire and Ice 6 00:00:25,430 --> 00:00:27,980 z nekaterimi CS50 je osebje in sošolci. 7 00:00:27,980 --> 00:00:30,170 Glavo na tem URL tukaj. 8 00:00:30,170 --> 00:00:33,420 >> Zdaj se morda spomniš, ali si lahko kmalu seznanjeni z, 9 00:00:33,420 --> 00:00:35,970 te stvari tukaj, ki so podani na koncu 10 00:00:35,970 --> 00:00:37,850 semestra za mnoge razrede. 11 00:00:37,850 --> 00:00:40,870 Tako imenovani izpit modre knjige, v kateri napišete svoje odgovore na izpite. 12 00:00:40,870 --> 00:00:44,240 Zdaj imam tukaj 26, kot modre knjige, na vsakem od njih 13 00:00:44,240 --> 00:00:47,580 je napisano ime, A do Z. In celo imena so tako preproste, 14 00:00:47,580 --> 00:00:50,490 skozi Z. In eden cilji pri roki danes 15 00:00:50,490 --> 00:00:53,910 se bo za naprej, kaj smo začeli v ponedeljek, ki je ni 16 00:00:53,910 --> 00:00:57,830 Toliko gledaš kodo, ampak res gledaš idej in reševanje problemov. 17 00:00:57,830 --> 00:01:00,170 Eden od ciljev in obljube o tem tečaju 18 00:01:00,170 --> 00:01:02,985 je, da te nauči, da razmišljajo bolj previdno, bolj načrtno, 19 00:01:02,985 --> 00:01:05,400 in za bolj učinkovito reševanje problemov. 20 00:01:05,400 --> 00:01:09,526 In res, kar lahko naredimo, da res celo brez dotika kode. 21 00:01:09,526 --> 00:01:12,150 Torej imam nekaj slonov do danes, oranžna in modra, 22 00:01:12,150 --> 00:01:15,780 če bi lahko dobili enega prostovoljca, Mogoče od dlje nazaj kot ponavadi. 23 00:01:15,780 --> 00:01:18,070 Kaj pa tam, pridi dol. 24 00:01:18,070 --> 00:01:24,180 Cilj, ki se bo na pomagal plus upravlja ta izpit tukaj. 25 00:01:24,180 --> 00:01:24,935 Kako ti je ime? 26 00:01:24,935 --> 00:01:25,768 >> OBČINSTVO: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, pridi gor. 28 00:01:27,560 --> 00:01:29,560 Naj vzamem mikrofon tukaj za vas. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Lepo, da sva se spoznala. 31 00:01:32,880 --> 00:01:34,005 >> OBČINSTVO: Me veseli. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: V redu, tako da sem moral Tukaj blue knjig do Z, 33 00:01:36,790 --> 00:01:41,680 in bom pretvarjal, da Imam enega od študentov, 34 00:01:41,680 --> 00:01:45,770 in oni, ki prihajajo v nekoliko naključno na koncu triurni izpit blok, 35 00:01:45,770 --> 00:01:49,400 tako oni končali v nekaj semi-naključnem zaporedju, kot je ta. 36 00:01:49,400 --> 00:01:54,510 Sedaj je vaša naloga, v trenutku se dogaja da bilo-- to je pravzaprav, kako so dobili 37 00:01:54,510 --> 00:01:56,820 Izkazalo se je ob koncu leta razred, najverjetneje. 38 00:01:56,820 --> 00:02:01,120 Vaša naloga zdaj se bo precej preprosto, razvrstiti te modre knjige za nas 39 00:02:01,120 --> 00:02:05,220 od A do Z. 40 00:02:05,220 --> 00:02:08,400 >> OBČINSTVO: Oh, to je bo večno traja. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: In bomo gledal kot ste to storili, ni pritiska. 42 00:02:13,747 --> 00:02:15,330 OBČINSTVO: Ne, nobenega pritiska ali kaj podobnega. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: In za zabavo, kaj je dal gor timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> OBČINSTVO: Tako zelo zabavno, tako zabavno. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Lahko držite mikrofon za vas. 49 00:02:38,574 --> 00:02:40,240 V redu, smo samo podvojili hitrost. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Torej, v tem času, mi predstavljajo, kaj je bo vprašanje, Mary Beth 52 00:02:49,060 --> 00:02:51,540 je, kaj počne, kako je ona bo o reševanju tega? 53 00:02:51,540 --> 00:02:54,040 In v resnici, morda nimate kdaj razmišljal o nečem 54 00:02:54,040 --> 00:02:57,440 tako preprosta, kot takrat, ko ste izbrali do 26 knjig, kot je ta, 55 00:02:57,440 --> 00:02:59,350 ki imajo naravno naročanje na njih. 56 00:02:59,350 --> 00:03:01,335 Kakšen je postopek da ste dejansko uporabo? 57 00:03:01,335 --> 00:03:03,770 Je dokaj random samo obiranje prvo kar vidite 58 00:03:03,770 --> 00:03:05,250 in ga je dala v svojem mestu? 59 00:03:05,250 --> 00:03:09,680 Ali najprej premakniti roke okoli išče potem išče B? 60 00:03:09,680 --> 00:03:11,722 Ali ste si ogledali par od njih ob bok 61 00:03:11,722 --> 00:03:14,680 in samo reči, počakaj malo, to ni v redu, nato pa zamenjali vrstni red? 62 00:03:14,680 --> 00:03:16,960 Videli smo že v ponedeljek da obstaja več načinov 63 00:03:16,960 --> 00:03:22,140 v katerem lahko to stori, in res, kot smo blizu konca tukaj, 64 00:03:22,140 --> 00:03:26,360 Jaz bi se seznanijo morda česa Mary Beth počne. 65 00:03:26,360 --> 00:03:30,040 Imamo nekaj kupi kot se zdi, Večji ena, tri manjše. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> OBČINSTVO: Jaz sem jih naročanje ko sem našel dve pismi 68 00:03:36,415 --> 00:03:39,540 da vem, so mi skupaj v zaporedju, Sem jih dal skupaj, tako da ne vem 69 00:03:39,540 --> 00:03:42,915 treba skrbeti za ohranjanje tir celo vrsto knjig. 70 00:03:42,915 --> 00:03:45,706 To je samo, oh, je prva, Imam ta kup tukaj. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Torej, skoraj kot puzzle kosov, ki 72 00:03:47,580 --> 00:03:49,860 imajo pravo obliko za ujemajo med seboj. 73 00:03:49,860 --> 00:03:51,026 OBČINSTVO: Precej, ja. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, odlično. 75 00:03:55,320 --> 00:03:59,850 In zdaj vsako od teh Piloti se verjetno razporejene? 76 00:03:59,850 --> 00:04:00,990 >> OBČINSTVO: Ja. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Dobro, skozi Z. All Dobro, čestitam, uspelo ti je. 78 00:04:09,900 --> 00:04:11,461 Imate izbiro. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 V redu, hvala ti za to. 81 00:04:13,530 --> 00:04:16,679 Torej, Mary Beth je predlagala kaj je njen pristop je bil, 82 00:04:16,679 --> 00:04:19,720 ampak tisto, kar je še en pristop, kako vas bi šel okoli sortiranje te stvari? 83 00:04:19,720 --> 00:04:21,130 Kaj bi vi storili? 84 00:04:21,130 --> 00:04:24,060 Zapis premagati, bi bilo eno minuto in 50 sekund ali tako, 85 00:04:24,060 --> 00:04:26,039 plus tisti, pozabil sem, da računajo. 86 00:04:26,039 --> 00:04:27,080 Kaj bi vi storili? 87 00:04:27,080 --> 00:04:27,579 Ja? 88 00:04:27,579 --> 00:04:28,735 OBČINSTVO: Vzemi kup. 89 00:04:28,735 --> 00:04:29,776 Začeti od začetka. 90 00:04:29,776 --> 00:04:32,284 Preverite svoje dokumente. 91 00:04:32,284 --> 00:04:36,586 In če je vrh enega višja kot, morda, so, 92 00:04:36,586 --> 00:04:38,980 dno ena višje, nato pa jih vključite. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, da se začne na vrhu in na dnu, 94 00:04:41,300 --> 00:04:43,716 in potem delajo svojo pot navznoter, kot da jih je zamenjala? 95 00:04:43,716 --> 00:04:46,580 OK, tako malo podobna v duhu mehurček vrste, 96 00:04:46,580 --> 00:04:49,160 vendar izbiri ekstreme ni sosednji pari. 97 00:04:49,160 --> 00:04:52,080 Ampak kratko o tem je, da obstaja gotovo kup različnih načinov 98 00:04:52,080 --> 00:04:54,210 bi lahko to storili, in Iskreno se vam zdi nekako 99 00:04:54,210 --> 00:04:55,700 sprejela nekaj pristopov, kajne? 100 00:04:55,700 --> 00:05:00,567 Ste naredili nekakšen štirih sortiranih pilotov in nato pa jih učinkovito združila skupaj. 101 00:05:00,567 --> 00:05:02,650 In to je, si trditi, drugo Tehnika v celoti. 102 00:05:02,650 --> 00:05:06,950 Nisi ga obravnava kot en velik kup, si razdelili problem v štiri štirikolesniki, 103 00:05:06,950 --> 00:05:09,820 če hočete, in potem nekako jih združili na koncu. 104 00:05:09,820 --> 00:05:13,410 >> Torej, kaj menijo, končno, kako drugače bi lahko to storimo. 105 00:05:13,410 --> 00:05:15,860 Formalizirana smo pojem mehurčkov razvrščanja zadnjem času, 106 00:05:15,860 --> 00:05:18,780 in bubble sort odpoklic je bil algoritem, ki smo vizualizirali 107 00:05:18,780 --> 00:05:22,640 z osem vaših sošolcev do tu, navidez naključno razporejene na prvi. 108 00:05:22,640 --> 00:05:26,110 In potem smo se odločili po parih, če dva elementa sta v okvari, 109 00:05:26,110 --> 00:05:26,950 preprosto jih swap. 110 00:05:26,950 --> 00:05:28,930 Torej, štiri, dva pa sta očitno v okvari, 111 00:05:28,930 --> 00:05:31,080 tako da ti dve sošolci zamenjal igralno mesto. 112 00:05:31,080 --> 00:05:35,390 In potem smo ponovili s štiri in šest, nato pa šest in osem na vsaki ponovitvi 113 00:05:35,390 --> 00:05:36,980 premika v desno. 114 00:05:36,980 --> 00:05:42,590 >> Torej, glede na osem ljudi, koliko paroma Primerjave sem naredil med hojo od 115 00:05:42,590 --> 00:05:45,220 leve proti desni v eni taki ponovitvi? 116 00:05:45,220 --> 00:05:48,410 Koliko primerjave? 117 00:05:48,410 --> 00:05:49,197 Seven, kajne? 118 00:05:49,197 --> 00:05:51,405 Ker če obstaja osem ljudi, pa imate par 119 00:05:51,405 --> 00:05:53,880 jih in jih premikati en hop na desno, 120 00:05:53,880 --> 00:05:56,060 ti ne boš imel osem primerjave, ker ne moreš primerjati 121 00:05:56,060 --> 00:05:59,226 element proti sebi, da bi ali samo nesmiselno, tako da boste imeli sedem. 122 00:05:59,226 --> 00:06:01,290 Ali bolj splošno, če imamo n ljudi, smo 123 00:06:01,290 --> 00:06:04,300 narediti n minus 1 primerjav z mehurček vrste. 124 00:06:04,300 --> 00:06:08,150 >> Torej, kaj menijo, da je sedaj, kako dobro ali slaba bubble sort dejansko je, in poskusite 125 00:06:08,150 --> 00:06:13,570 da bi sami besedišča s za kritiko algoritmov, kot je ta, 126 00:06:13,570 --> 00:06:14,430 in kmalu je naša lastna. 127 00:06:14,430 --> 00:06:16,970 Torej prvem prehodu skozi mehurček sortiranje, prvič 128 00:06:16,970 --> 00:06:20,909 Hodil sem od leve proti desni po vsej oder, vzel me n minus 1 primerjav. 129 00:06:20,909 --> 00:06:22,950 In to se dogaja, da je moj merska enota, kajne? 130 00:06:22,950 --> 00:06:26,170 Nekako sem govoril in sprehodu, nekoliko hitro, nekoliko počasen, 131 00:06:26,170 --> 00:06:29,300 tako štetje moje število sekund ni posebej govoril, 132 00:06:29,300 --> 00:06:32,260 vendar štetje števila operacije, da sem storil v ponedeljek, 133 00:06:32,260 --> 00:06:35,900 primerjavo dveh ljudi, da se počuti kot lepo mersko enoto. 134 00:06:35,900 --> 00:06:40,980 >> Torej n minus 1 koraki prvič, pa vendar, kaj se je zgodilo po tem? 135 00:06:40,980 --> 00:06:46,610 Kaj je eno glavo enega priložnost skozi sicer nesortiranih seznamu? 136 00:06:46,610 --> 00:06:49,840 Kaj mi lahko poveste o tem elementu , ki je bil vse do tja? 137 00:06:49,840 --> 00:06:51,300 Ja? 138 00:06:51,300 --> 00:06:52,870 To je bil največji element, kajne? 139 00:06:52,870 --> 00:06:55,710 Številka osem, čeprav je začel sem vsakič, ko sem 140 00:06:55,710 --> 00:06:57,860 jo primerjamo z sosed, ona hranijo 141 00:06:57,860 --> 00:07:00,480 prepihavanje do desno z strani seznama. 142 00:07:00,480 --> 00:07:02,710 In res, da je, kjer algoritem dobil ime. 143 00:07:02,710 --> 00:07:07,630 >> Zdaj pa jih je ta logika, koliko primerjave Moram narediti za drugič 144 00:07:07,630 --> 00:07:09,800 Jaz bi to podajo iz leve proti desni? 145 00:07:09,800 --> 00:07:10,730 n minus 2, kajne? 146 00:07:10,730 --> 00:07:14,297 To bi bilo samo zapravljaš svoj čas, če I obdržati primerjavo osem proti nekomu 147 00:07:14,297 --> 00:07:16,630 sicer zato, ker smo že vedeli, je bila na pravem mestu. 148 00:07:16,630 --> 00:07:19,760 Tako da je malo optimizacija, tako da je naslednji akcije 149 00:07:19,760 --> 00:07:23,899 se bo n plus minus dva koraka, kjer je n število ljudi. 150 00:07:23,899 --> 00:07:26,940 Sedaj lahko nekako ekstrapolacijo, čeprav če niste računalniški znanstvenik, 151 00:07:26,940 --> 00:07:27,680 kako se to konča. 152 00:07:27,680 --> 00:07:31,259 Na koncu tega algoritma, predvidoma imaš samo eno primerjavo levo. 153 00:07:31,259 --> 00:07:33,800 Moraš nekako popraviti začetek seznama, v primeru dveh 154 00:07:33,800 --> 00:07:36,540 in eden v okvari in mora biti ena in dva, 155 00:07:36,540 --> 00:07:40,330 tako da je ta dna ven na plus 1 final primerjava. 156 00:07:40,330 --> 00:07:44,500 >> Zdaj dot, dot, dot vrste valov je roke na nekatere juicier podrobnosti 157 00:07:44,500 --> 00:07:46,452 ampak greva naprej in poenostaviti. 158 00:07:46,452 --> 00:07:48,660 Če se spomnite iz visoko šola, odkrito povedano, veliko vas 159 00:07:48,660 --> 00:07:50,340 imeli matematične knjige, ki so imele malo cheat sheet 160 00:07:50,340 --> 00:07:52,550 na naslovnici ali zadnji pokrov, ki vas je pokazala 161 00:07:52,550 --> 00:07:56,400 kaj serije summations kot to na koncu seštejejo. 162 00:07:56,400 --> 00:07:59,600 V splošnem primeru, če imate spremenljivka, kot n in dejansko ta, 163 00:07:59,600 --> 00:08:01,634 če si pogledal na vaš old school math knjiga, 164 00:08:01,634 --> 00:08:04,050 boste videli, da je to dejansko dodaja do te vsote tukaj 165 00:08:04,050 --> 00:08:07,970 n krat n minus 1 vse deljeno z 2. 166 00:08:07,970 --> 00:08:11,172 Za zdaj naj mi določajo to je res, da na preskok vere, 167 00:08:11,172 --> 00:08:12,880 da je tisto, kar v seštevku do, in smo lahko 168 00:08:12,880 --> 00:08:14,341 dokazati, da je v bolj splošnem primeru. 169 00:08:14,341 --> 00:08:15,590 Ampak zdaj pa razširiti to. 170 00:08:15,590 --> 00:08:19,920 Torej pomnožite to ven, tako da je n kvadrat, minus n, vse deliti z 2. 171 00:08:19,920 --> 00:08:23,200 To je res n kvadrat, deliti z 2, minus n več kot 2, 172 00:08:23,200 --> 00:08:25,010 tako da je vse lepo in zanimivo. 173 00:08:25,010 --> 00:08:27,060 Toda kaj se zgodi, če bomo zdaj plug-in v vrednosti? 174 00:08:27,060 --> 00:08:29,724 Recimo nisem imela osem ljudje, ampak pravijo milijon. 175 00:08:29,724 --> 00:08:31,890 In milijonov samo zato, ker to je precej velika številka, 176 00:08:31,890 --> 00:08:34,039 pa vtič, da je v in videli, kaj se bo zgodilo. 177 00:08:34,039 --> 00:08:39,039 Torej, če priključim milijonov v to formulo Jaz bom dobil milijon na kvadrat, 178 00:08:39,039 --> 00:08:42,868 deliti z 2, minus milijonov, deljeno s 2. 179 00:08:42,868 --> 00:08:44,159 Zdaj, kaj je, da bo enako? 180 00:08:44,159 --> 00:08:47,354 Torej, 500 milijard, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 In če sem v resnici naredil da math ven, da se sredstva 182 00:08:49,270 --> 00:08:53,920 da sortiranje milijon ljudje z mehurček vrste 183 00:08:53,920 --> 00:09:01,800 mi lahko traja 499999500000 stopnice ali primerjave na koncu, 184 00:09:01,800 --> 00:09:02,900 smo samo ekstrapolacijo. 185 00:09:02,900 --> 00:09:06,860 >> Da se počuti precej počasen, vendar odkrito povedano merjenje eno posebno vhod 186 00:09:06,860 --> 00:09:09,160 kot je ta, ni vse tako zgovoren. 187 00:09:09,160 --> 00:09:14,050 Ampak res pa predlaga, da se kot n dobi večji in večji, ta algoritem 188 00:09:14,050 --> 00:09:16,280 vrsta počuti slabše in slabše, ali res 189 00:09:16,280 --> 00:09:20,450 začutite bolečino, ki potenciranje, da je n kvadratna 190 00:09:20,450 --> 00:09:21,770 , ki dodaja do precej hitro. 191 00:09:21,770 --> 00:09:25,340 In ta podrobnost ni izgubil na ljudi, v resnici 192 00:09:25,340 --> 00:09:29,640 Pred nekaj leti gotovo senator, ki je bil kampanje, je sedel na razgovor 193 00:09:29,640 --> 00:09:32,180 z Googla Eric Schmidt direktor takrat, 194 00:09:32,180 --> 00:09:36,380 in je izpodbijala z vprašanjem podobno kot smo danes raziskuje. 195 00:09:36,380 --> 00:09:38,468 Oglejmo pogled. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO PREDVAJANJE] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Da si tu na Googlu, in mi je všeč 198 00:09:48,560 --> 00:09:53,382 razmišljati o predsedovanju kot je razgovor za službo. 199 00:09:53,382 --> 00:09:56,434 Sedaj je težko dobiti delo kot predsednik, 200 00:09:56,434 --> 00:09:58,100 in greste skozi mrzlica zdaj. 201 00:09:58,100 --> 00:10:01,860 Prav tako je težko dobiti službo v Googlu. 202 00:10:01,860 --> 00:10:05,490 Imamo vprašanja, in mi Od naših kandidatov vprašanja, 203 00:10:05,490 --> 00:10:09,770 in to je eden od Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Kaj-- mislita, da sem hecam se, da je prav tukaj. 205 00:10:14,760 --> 00:10:17,930 Kaj je najbolj učinkovit način za razvrstiti milijon 32-bitnih celih števil? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> Žal mi je, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Ne, ne, ne. 210 00:10:27,400 --> 00:10:30,700 Mislim, da je mehurček vrste bi bilo napačno pot. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Daj no, kdo mu je to povedal? 213 00:10:38,180 --> 00:10:40,590 Nisem videl računalnika znanost v ozadju. 214 00:10:40,590 --> 00:10:42,130 >> -Mi Smo dobili naše vohune tam. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Kaj je vprašal drugačen intervju vprašanje. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO PREDVAJANJE] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Torej, govorimo o Določene številke čeprav, 219 00:10:52,290 --> 00:10:53,890 se ne bo vse to koristno. 220 00:10:53,890 --> 00:10:56,810 To ni življenjsko lekcijo, da bubble sort, saj milijon vložkov, 221 00:10:56,810 --> 00:10:58,590 Lahko traja tudi do 500 milijard korake. 222 00:10:58,590 --> 00:11:01,120 Vam ne morem posploševati Tudi učinkovito od 223 00:11:01,120 --> 00:11:03,560 in sprejemati dobre odločitve o oblikovanju Pri pisanju programov. 224 00:11:03,560 --> 00:11:07,070 Torej, kaj je osredotočiti, čeprav o tem, kako bomo lahko poenostavi ta rezultat. 225 00:11:07,070 --> 00:11:11,780 >> Tako sem označen z rumeno barvo tukaj Rezultat n kvadrat deljeno z 2, 226 00:11:11,780 --> 00:11:14,330 tako na kvadrat milijonov deljeno z 2, in nato 227 00:11:14,330 --> 00:11:16,710 Sem izpostavila, kaj Končni odgovor je bil 228 00:11:16,710 --> 00:11:20,180 ko smo odšteli off n deljeno z 2. 229 00:11:20,180 --> 00:11:24,850 In trditev, bom, da je zdaj, kdo za vraga briga, če odštejemo off 230 00:11:24,850 --> 00:11:30,060 malo stara n kot 2, ko je prva del te formule je toliko večji? 231 00:11:30,060 --> 00:11:33,910 Dominira drugi Izraz, n kvadrat deljeno z 2 232 00:11:33,910 --> 00:11:37,510 je toliko večji, je jasno, saj n postane velik kot milijon, 233 00:11:37,510 --> 00:11:41,450 da je res velika razlika v Konec dneva med 500 milijard 234 00:11:41,450 --> 00:11:45,730 in 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Ni res. 236 00:11:46,349 --> 00:11:48,640 In kaj bomo storiti, saj je računalniški znanstveniki 237 00:11:48,640 --> 00:11:53,270 prezreti tiste nižje pogoje red in da kaj takega in res 238 00:11:53,270 --> 00:11:56,050 samo to poenostavi na Izraz, ki bo pomembno. 239 00:11:56,050 --> 00:12:00,315 Večje naši podatkovni nizi dobili, večji naše baze podatkov dobiti, več spletnih strani 240 00:12:00,315 --> 00:12:02,690 moramo iskati, bolj prijateljev imate na Facebooku. 241 00:12:02,690 --> 00:12:07,340 >> Kot n postane večja, smo zares dogaja, da skrbi za največje 242 00:12:07,340 --> 00:12:11,560 Izraz v vsakem takem analize naša algoritmi uspešnosti. 243 00:12:11,560 --> 00:12:16,230 In bom rekel, veš kaj, bubble sort je o vrstnem redu veliki O, 244 00:12:16,230 --> 00:12:18,060 o vrstnem redu n kvadrat. 245 00:12:18,060 --> 00:12:20,090 To ni ravno n kvadrati, kot smo videli, 246 00:12:20,090 --> 00:12:22,060 ampak kdo v resnici briga o teh manjših pogoji, 247 00:12:22,060 --> 00:12:24,390 in odkrito, ki resnično briga, če delimo z 2? 248 00:12:24,390 --> 00:12:25,870 To je samo konstantni faktor. 249 00:12:25,870 --> 00:12:29,480 In 500 milijard v primerjavi z 250 milijard res, da je velik za posel? 250 00:12:29,480 --> 00:12:32,190 Jaz bi samo čakati eno leto, Naj svoj laptop dobesedno 251 00:12:32,190 --> 00:12:34,810 dobili dvakrat hitreje v strojni opremi, in da je vrsta razlike 252 00:12:34,810 --> 00:12:36,650 samo izgine seveda sčasoma. 253 00:12:36,650 --> 00:12:39,300 >> Kar nas skrbi, je izraz, del 254 00:12:39,300 --> 00:12:42,489 izraza, ki se dogaja, da se razlikujejo kot naš input dobi večji in večji. 255 00:12:42,489 --> 00:12:45,280 In res, v realnem svetu, da je tisto, kar se dogaja vse pogosteje 256 00:12:45,280 --> 00:12:48,330 se vnosi za naše probleme in algoritmi so dobili večji. 257 00:12:48,330 --> 00:12:53,470 Tako velik O se bo zapis, asymptotic zapis, ki sva jih 258 00:12:53,470 --> 00:12:57,160 uporabite kot računalniški znanstveniki za opisovanje uspešnost ali čas teče, 259 00:12:57,160 --> 00:12:58,130 algoritma. 260 00:12:58,130 --> 00:13:00,800 Tako, da lahko primerjamo algoritme na različnih računalnikih pisnih 261 00:13:00,800 --> 00:13:04,170 z različnimi ljudmi, z uporabo nekateri v osnovi podobna metric 262 00:13:04,170 --> 00:13:07,557 kot števila primerjav ste odločitev, ali morda število zamenjav 263 00:13:07,557 --> 00:13:08,140 delaš. 264 00:13:08,140 --> 00:13:11,910 >> Kaj mi ne bo Število je količina časa 265 00:13:11,910 --> 00:13:13,981 da prehaja na uro na steni tipično. 266 00:13:13,981 --> 00:13:16,230 Kaj ne bomo skrbeti o tem, koliko pomnilnika 267 00:13:16,230 --> 00:13:17,820 ste danes uporabljajo na Vsaj, čeprav je to 268 00:13:17,820 --> 00:13:19,370 drug vir, bomo morda izmeriti. 269 00:13:19,370 --> 00:13:23,610 Bomo poskušali utemeljiti naše analize na samo osnovnih operacij, tisti, 270 00:13:23,610 --> 00:13:25,930 odkrito, da si lahko ogledate najbolj vizualno. 271 00:13:25,930 --> 00:13:30,700 Torej, z nekaj podobnega veliki O n kvadrat, Trdim, da O n kvadrat 272 00:13:30,700 --> 00:13:35,820 je zgornja vezan na tako imenovane čas mehurček vrste teče. 273 00:13:35,820 --> 00:13:38,820 Z drugimi besedami, če vas želel, da trdijo, da je 274 00:13:38,820 --> 00:13:41,370 ta zgornja meja, koliko koraka algoritma lahko traja, 275 00:13:41,370 --> 00:13:46,240 se dogaja, da se v veliki O n kvadrat v tem primeru zgornja meja. 276 00:13:46,240 --> 00:13:49,710 >> Kaj če bi namesto spremeniti Zgodba, da je ne gre mehurček vrste, 277 00:13:49,710 --> 00:13:50,910 ampak o tem zgornja meja. 278 00:13:50,910 --> 00:13:54,030 Lahko si misliš o algoritmu, da smo pogledal že 279 00:13:54,030 --> 00:13:59,530 katerih zgornja meja, največ merjenje časa ali operacij, 280 00:13:59,530 --> 00:14:04,300 bi lahko rekli, da se omejuje z n, linearna funkcija, 281 00:14:04,300 --> 00:14:07,260 ni kvadratna tista, ki je ukrivljena? 282 00:14:07,260 --> 00:14:10,780 Kaj je algoritem, ki vedno ne traja več 283 00:14:10,780 --> 00:14:12,860 kot kot n korakov oziroma 2N koraki, ali 3N koraki? 284 00:14:12,860 --> 00:14:13,360 Ja? 285 00:14:13,360 --> 00:14:15,030 >> OBČINSTVO: Iskanje največja številka v seznamu? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Popoln, iskanje največja številka v seznamu. 287 00:14:16,930 --> 00:14:18,940 Če sem dal seznam ljudje, na primer, 288 00:14:18,940 --> 00:14:21,440 vsaka, ki drži več, tisto, kar je največje število 289 00:14:21,440 --> 00:14:23,770 korakov naj bi me odpeljal, razumno pametna oseba, 290 00:14:23,770 --> 00:14:27,530 da bi našli največji osebo v tem seznamu? 291 00:14:27,530 --> 00:14:28,100 n, kajne? 292 00:14:28,100 --> 00:14:31,320 Ker v najslabšem primeru, če je Morda največja vrednost je? 293 00:14:31,320 --> 00:14:32,700 Dobro, tako na koncu. 294 00:14:32,700 --> 00:14:34,575 Torej v najslabšem primeru zgornjo mejo, bi lahko 295 00:14:34,575 --> 00:14:36,450 iti vso pot sem in se kot, 296 00:14:36,450 --> 00:14:39,170 oh, tukaj je številka osem, ali karkoli, da vrednost. 297 00:14:39,170 --> 00:14:41,330 Zdaj bi le bilo neumno če sem kar naprej dogaja, kajne? 298 00:14:41,330 --> 00:14:43,840 Išče vse več elementov če je zadnja od njih je tam? 299 00:14:43,840 --> 00:14:45,340 Torej zagotovo, n je zgornja meja. 300 00:14:45,340 --> 00:14:47,420 Ne rabim, da sprejmejo več korakov, kot je. 301 00:14:47,420 --> 00:14:51,580 >> Pa kaj, če namesto tega sem predlagal, da obstajajo algoritmi na tem svetu, ki 302 00:14:51,580 --> 00:14:57,750 imeti čas teče, ki je omejeno z velikim O log n log n? 303 00:14:57,750 --> 00:15:00,390 Kjer smo videli že prej? 304 00:15:00,390 --> 00:15:00,890 Ja? 305 00:15:00,890 --> 00:15:03,309 >> OBČINSTVO: Pri problemu telefonskega imenika? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Kot problem telefonskega imenika. 307 00:15:04,850 --> 00:15:07,754 Kaj je merilo, kako koliko časa oziroma koliko pretoĉenih 308 00:15:07,754 --> 00:15:10,170 vzel me je, da bi našli nekoga, kot Mike Smith v telefonskem imeniku? 309 00:15:10,170 --> 00:15:13,212 Smo trdili, da je log n in tudi če ne poznajo, ali pa je 310 00:15:13,212 --> 00:15:15,170 malo motna, kar logaritem ali eksponent je bilo, 311 00:15:15,170 --> 00:15:17,650 Zapomnite si, da log n Na splošno se nanaša na postopek, 312 00:15:17,650 --> 00:15:20,790 V tem primeru, delitve nekaj na pol spet in spet, 313 00:15:20,790 --> 00:15:25,790 in znova in znova, tako da postane bolj majhna, kot si to naredil. 314 00:15:25,790 --> 00:15:28,470 >> Torej, se prijavite z n sklicuje, seveda, na primer telefonski imenik, 315 00:15:28,470 --> 00:15:32,662 za binarno iskanje v teoriji, ko smo imeli virtualne vrata na krovu, 316 00:15:32,662 --> 00:15:34,370 ali ko je Sean iskanju nečesa. 317 00:15:34,370 --> 00:15:37,374 Če bi uporabili binarno iskanje, log n bi bila zgornja meja za koliko 318 00:15:37,374 --> 00:15:38,040 Čas je, da traja. 319 00:15:38,040 --> 00:15:44,027 Toda ti algoritmi, ki je potekal v log n domnevati kaj ključno podrobnost? 320 00:15:44,027 --> 00:15:45,360 To je seznam urejen, kajne? 321 00:15:45,360 --> 00:15:47,789 Vaš algoritem je narobe, če svoj vhod ni urejen, 322 00:15:47,789 --> 00:15:49,830 in še boste uporabljali nekaj takega kot binarno iskanje 323 00:15:49,830 --> 00:15:51,704 kajti lahko bi skočil desno čez element 324 00:15:51,704 --> 00:15:53,600 ne da bi dojel, da je res tam. 325 00:15:53,600 --> 00:15:55,600 >> Zdaj pa, kaj bi to lahko pomenilo, Big O enega? 326 00:15:55,600 --> 00:15:59,117 To ne pomeni, da je vaš algoritma traja en in samo en korak, 327 00:15:59,117 --> 00:16:01,200 to samo pomeni, da je potrebno konstantno število korakov. 328 00:16:01,200 --> 00:16:04,060 Mogoče je 1, morda je 10, morda je 1.000, 329 00:16:04,060 --> 00:16:07,750 ampak to je neodvisno od velikost problema. 330 00:16:07,750 --> 00:16:10,850 Ne glede na to, kako velik je n, stalen čas algoritem 331 00:16:10,850 --> 00:16:12,747 vedno v isto število korakov. 332 00:16:12,747 --> 00:16:15,080 Torej, kaj bi lahko algoritem smo se pogovarjali o tem, ali samo 333 00:16:15,080 --> 00:16:20,418 intuitivno, da pride k vam, da vedno izvaja v tako imenovanem konstantno času? 334 00:16:20,418 --> 00:16:20,918 Ja? 335 00:16:20,918 --> 00:16:22,001 >> OBČINSTVO: Dodajte dve številki. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Dodamo dve številki, 2 plus 2 je enako 4, storjeno. 337 00:16:25,320 --> 00:16:27,227 Tako da bi lahko bilo delo, kaj? 338 00:16:27,227 --> 00:16:28,560 Kaj pa bolj realni svet, ja? 339 00:16:28,560 --> 00:16:30,686 >> OBČINSTVO: Iskanje Prva stvar na seznamu. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Iskanje prva element na seznamu, seveda. 341 00:16:32,810 --> 00:16:34,540 Mi smo dejansko govorimo O nizi že, 342 00:16:34,540 --> 00:16:36,540 kako si dobil na Prvi element v matriki, 343 00:16:36,540 --> 00:16:40,465 ne glede na to, kako dolgo matrika je v C kodo? 344 00:16:40,465 --> 00:16:43,090 Pravkar ste uporabili kot nosilec nič zapis, bam, da si tam. 345 00:16:43,090 --> 00:16:46,120 In res nizi, kot prahi, Podpora nekaj splošno znana 346 00:16:46,120 --> 00:16:49,240 kot bralno, bralno spomin, saj si lahko dobesedno 347 00:16:49,240 --> 00:16:50,284 skok na enem mestu. 348 00:16:50,284 --> 00:16:52,700 To lahko naredimo še bolj preprosto moremo previti nič teden 349 00:16:52,700 --> 00:16:53,900 ko smo naredili nič. 350 00:16:53,900 --> 00:16:59,707 Koliko časa je trajalo, da za pravijo blok v Scratch za usmrtitev? 351 00:16:59,707 --> 00:17:00,790 Samo konstanten čas, kajne? 352 00:17:00,790 --> 00:17:03,960 Nekaj ​​reči, pravijo, kaj, ni važno 353 00:17:03,960 --> 00:17:07,359 kako velike Praske svet, je vedno bo trajalo enako količino časa 354 00:17:07,359 --> 00:17:08,490 da preprosto reči. 355 00:17:08,490 --> 00:17:11,089 >> Torej, to je konstanta čas, ampak kaj je side flip? 356 00:17:11,089 --> 00:17:13,030 Če bi bila zgornja meje, kaj, če želimo 357 00:17:13,030 --> 00:17:17,089 opisati spodnje meje naših algoritmov teče čas? 358 00:17:17,089 --> 00:17:19,852 Skoraj najboljši primer lahko, če hočete, 359 00:17:19,852 --> 00:17:23,060 čeprav bi ti pogoji veljajo za najboljše primeri, najhujših primerov povprečne primerov več 360 00:17:23,060 --> 00:17:26,359 na splošno, temveč se posvetimo samo na nižjih meje bolj na splošno. 361 00:17:26,359 --> 00:17:31,920 Kaj je algoritem, ki ima spodnja meja n korakih, 362 00:17:31,920 --> 00:17:33,350 ali 2N koraki, ali 3N koraki? 363 00:17:33,350 --> 00:17:36,241 Nekateri faktor n korakih, da je njena spodnja meja. 364 00:17:36,241 --> 00:17:36,740 Ja? 365 00:17:36,740 --> 00:17:37,910 >> OBČINSTVO: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort traja ti minimalno n korakov, zakaj? 367 00:17:41,610 --> 00:17:42,279 Zakaj je tako? 368 00:17:42,279 --> 00:17:45,320 Zakaj naj bi, da je začetek, da pridejo do vas intuitivno, čeprav to ne samo 369 00:17:45,320 --> 00:17:46,530 še? 370 00:17:46,530 --> 00:17:47,030 Ja? 371 00:17:47,030 --> 00:17:47,990 >> OBČINSTVO: [neslišno]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Točno tako. 374 00:17:52,360 --> 00:17:55,810 V najboljšem možnem scenariju bubble sort, in veliko algoritmov, 375 00:17:55,810 --> 00:17:58,769 če ti roko osem ljudi ki so že urejene, 376 00:17:58,769 --> 00:18:00,560 to bi bilo neumno za vas, algoritem, 377 00:18:00,560 --> 00:18:02,202 iti naprej in nazaj več kot enkrat, kajne? 378 00:18:02,202 --> 00:18:04,285 Zato, ker takoj, ko vas sprehod po seznamu enkrat, 379 00:18:04,285 --> 00:18:08,090 morate zavedati, oh, sem ne zamenjave, je ta seznam razporejene, izhod. 380 00:18:08,090 --> 00:18:09,700 Ampak to se dogaja, da vam n ukrepe sprejeti. 381 00:18:09,700 --> 00:18:12,033 >> In obratno, kar je še način razmišljanja o tem? 382 00:18:12,033 --> 00:18:15,240 Bubble sort je omega, tako rekoč, n, 383 00:18:15,240 --> 00:18:19,050 ker če pogledaš na manj kot n elementov, kar 384 00:18:19,050 --> 00:18:23,009 je temeljno vprašanje tam? 385 00:18:23,009 --> 00:18:24,550 Saj ne vem, če je to urejeno, prav. 386 00:18:24,550 --> 00:18:26,800 Smo ljudje morda pogled na osmih ljudje, in bo kot, oh, to je urejeno, 387 00:18:26,800 --> 00:18:28,430 da me n korakov ni upošteval, ampak je to storila. 388 00:18:28,430 --> 00:18:30,810 Tvoje oči, čeprav vas nekako o imajo veliko vidno polje, 389 00:18:30,810 --> 00:18:33,184 si pogledal na osem elementov, si pogledal osem ljudi, 390 00:18:33,184 --> 00:18:34,610 to je dejansko osem korakov. 391 00:18:34,610 --> 00:18:38,612 In samo če grem skozi celoten seznam moram zavedati, da, razporejene. 392 00:18:38,612 --> 00:18:41,320 Če neham pol razmišljal, vse V redu, to je precej doslej razporejene, 393 00:18:41,320 --> 00:18:42,520 Kakšne so možnosti, da se ni razvrščena? 394 00:18:42,520 --> 00:18:44,186 Da algoritmi ne bo pravilna. 395 00:18:44,186 --> 00:18:46,250 Morda hitreje, vendar napačno. 396 00:18:46,250 --> 00:18:48,500 >> Torej, zdaj imamo način Opisovanje spodnje meje, 397 00:18:48,500 --> 00:18:49,710 in kaj je s konstantnim časom? 398 00:18:49,710 --> 00:18:54,565 Kaj je algoritem, ki ima nižje vezan na vozno času enega? 399 00:18:54,565 --> 00:18:58,350 1 korak 2 stopnici, 10 korakov, vendar konstanten, neodvisno od n, 400 00:18:58,350 --> 00:18:59,310 velikost vhoda? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Ja, v hrbtu. 403 00:19:04,600 --> 00:19:05,309 >> OBČINSTVO: printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Kaj je to? 405 00:19:06,183 --> 00:19:07,184 OBČINSTVO: printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: printf. 407 00:19:07,850 --> 00:19:08,400 OK, seveda. 408 00:19:08,400 --> 00:19:10,720 Torej je potrebno določeno število korakov. 409 00:19:10,720 --> 00:19:13,170 In moram sedaj-- zdaj, govorimo o C kodo 410 00:19:13,170 --> 00:19:16,040 in ne Scratch, nekaj kot pravijo, z printf, 411 00:19:16,040 --> 00:19:17,710 bi morali začeti, da bi dobili previdni. 412 00:19:17,710 --> 00:19:21,090 Ker printf ne bo input, to je niz, 413 00:19:21,090 --> 00:19:23,220 in godala pa tehnično imajo dolžino. 414 00:19:23,220 --> 00:19:25,530 Torej, če hočemo sedaj poberem na vas, če vas ne moti, 415 00:19:25,530 --> 00:19:29,430 tehnično bi lahko trdili, da printf ne bo spremenljivo vhod dolžine, 416 00:19:29,430 --> 00:19:32,270 in zagotovo bo trajalo več Čas je, da natisnete niz tako dolgo, 417 00:19:32,270 --> 00:19:33,560 od tega dolg. 418 00:19:33,560 --> 00:19:36,570 >> Pa kaj, če upoštevamo samo sortiranje in iskanje primerov? 419 00:19:36,570 --> 00:19:40,450 Kaj pa Mike Smith v telefonu knjiga ali binarno iskanje bolj na splošno? 420 00:19:40,450 --> 00:19:42,220 V najboljšem primeru, kaj se lahko zgodi? 421 00:19:42,220 --> 00:19:45,577 Odprem telefonski imenik in bam, tam je število Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Lahko ga pokličem takoj. 423 00:19:46,660 --> 00:19:49,390 >> Je en korak, morda dveh korakih, vendar je konstantno število korakov 424 00:19:49,390 --> 00:19:50,230 če imam srečo. 425 00:19:50,230 --> 00:19:52,570 In odkrito povedano, smo videli na Ponedeljek tvoj sošolec 426 00:19:52,570 --> 00:19:54,710 dobili precej srečen dvakrat zapored. 427 00:19:54,710 --> 00:19:57,050 In to je bilo res konstantna Čas v nižjem igrišča 428 00:19:57,050 --> 00:20:01,280 o algoritmu zadevno za iskanje Številka 50 zaostaja zaprta 429 00:20:01,280 --> 00:20:01,830 vrata. 430 00:20:01,830 --> 00:20:06,400 >> Zdaj, kot prahi, če boste odkrili, da tako velik O, zgornja meja, 431 00:20:06,400 --> 00:20:09,310 in omega, spodnja meja, sta eno in isto, da 432 00:20:09,310 --> 00:20:11,830 je enako formulo v oklepaje, lahko tudi vi 433 00:20:11,830 --> 00:20:15,170 pravijo, samo, da je fancy, da je nekaj v theta 434 00:20:15,170 --> 00:20:18,270 n ali theta neke druge vrednosti. 435 00:20:18,270 --> 00:20:20,661 To samo pomeni, ko velika O in omega so enaki. 436 00:20:20,661 --> 00:20:21,910 Kaj pa izbirnem vrste zdaj? 437 00:20:21,910 --> 00:20:23,400 Izkoristimo to novo besedišče. 438 00:20:23,400 --> 00:20:27,407 V izbirnem vrste, kar smo ostali počne znova in znova in znova? 439 00:20:27,407 --> 00:20:29,990 Sem šel naprej in nazaj skozi Seznam, ki je videti za koga? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Najmanjše število. 442 00:20:34,730 --> 00:20:37,560 >> Torej, koliko korakov, kako številne primerjave Sem 443 00:20:37,560 --> 00:20:43,250 morali narediti, da bi ugotovili, kdo najmanjši element na seznamu je? 444 00:20:43,250 --> 00:20:44,437 n minus 1, kajne? 445 00:20:44,437 --> 00:20:47,770 Ker, če sem začela z enim sem dana in začnem mu primerjavo, 446 00:20:47,770 --> 00:20:49,519 potem on ali ona, on ali ona, on ali ona, sem 447 00:20:49,519 --> 00:20:52,010 lahko seznanite samo elemente skupaj n minus 1 krat. 448 00:20:52,010 --> 00:20:55,630 Torej, izbira sort podobno traja n minus 1 koraki prvič. 449 00:20:55,630 --> 00:20:59,540 >> Koliko korakov traja me najti drugo najmanjšo element? 450 00:20:59,540 --> 00:21:02,920 n minus 2, ker sem biti neumen če sem vedno gledaš istimi ljudmi 451 00:21:02,920 --> 00:21:06,280 še enkrat, če sem ga že izbrali ali njen in jih postaviti na svoje mesto. 452 00:21:06,280 --> 00:21:09,270 In tretji korak, n minus 3, potem je n minus 4. 453 00:21:09,270 --> 00:21:11,020 Videli smo ta vzorec prej, in dejansko 454 00:21:11,020 --> 00:21:13,460 Izbira nekako podobno je zgornja meja 455 00:21:13,460 --> 00:21:16,210 n kvadrat, če bomo do tega seštevanja. 456 00:21:16,210 --> 00:21:19,790 Kakšna je njegova spodnja meja, izbor sort? 457 00:21:19,790 --> 00:21:25,350 Minimalno, koliko časa je treba izbiro nekako sprejeti, kot smo ga opredelili v ponedeljek? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Predlagala dve možnosti. 460 00:21:30,490 --> 00:21:32,360 Mogoče je n, kot prej. 461 00:21:32,360 --> 00:21:35,040 Mogoče je n kvadrat, saj Zdaj je, kot je zgornja meja. 462 00:21:35,040 --> 00:21:35,874 >> OBČINSTVO: n na kvadrat. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n na kvadrat. 464 00:21:36,664 --> 00:21:37,368 Zakaj? 465 00:21:37,368 --> 00:21:40,060 >> OBČINSTVO: Ker imate opredeliti [neslišno]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Točno tako. 467 00:21:41,510 --> 00:21:45,077 Vsaj tako sem definirana izbora vrste je bilo precej naivno, nadaljuj, 468 00:21:45,077 --> 00:21:46,160 najti najmanjši element. 469 00:21:46,160 --> 00:21:47,770 Pojdi spet najti najmanjši element. 470 00:21:47,770 --> 00:21:49,490 Pojdi spet najti najmanjši element. 471 00:21:49,490 --> 00:21:51,700 Ni nekako Optimizacija tam, da 472 00:21:51,700 --> 00:21:54,350 Morda mi prekinitev po le n ali tako korakov. 473 00:21:54,350 --> 00:21:57,080 Torej res, izbor sort, omega n kvadrat. 474 00:21:57,080 --> 00:22:00,667 >> Kaj vstavitve vrste, kjer sem vzel , ki mi je bila dana, in potem sem ga plopped 475 00:22:00,667 --> 00:22:01,750 ali jo na pravem mestu? 476 00:22:01,750 --> 00:22:04,958 Potem sem nadaljeval na drugo osebo, mu plopped na pravem mestu. 477 00:22:04,958 --> 00:22:07,910 Potem naslednja oseba, plopped ga ali jo na pravem mestu. 478 00:22:07,910 --> 00:22:10,537 Obvestilo, da je to zelo linearna, tako rekoč. 479 00:22:10,537 --> 00:22:12,620 Sem premica, sem ne gre naprej in nazaj, 480 00:22:12,620 --> 00:22:16,080 Nikoli nisem ozrl nazaj res, pa kaj se dogaja, ko sem ga vstavite 481 00:22:16,080 --> 00:22:20,302 ali pa jo v začetku leta seznam, kot smo to storili v ponedeljek? 482 00:22:20,302 --> 00:22:21,010 Kaj se dogaja? 483 00:22:21,010 --> 00:22:21,510 Ja? 484 00:22:21,510 --> 00:22:23,122 OBČINSTVO: [neslišno]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Ja, to je bil ulov, kajne? 486 00:22:24,830 --> 00:22:26,746 Morda se boste spomnili iz tvoji sošolci, če 487 00:22:26,746 --> 00:22:29,670 bili kar vsak premik z njihove noge, da je bila operacija. 488 00:22:29,670 --> 00:22:33,610 Torej, če so bili trije ljudje, tu in nova oseba pripadala pot tja, 489 00:22:33,610 --> 00:22:37,360 na dolgi fazi, kot je ta, seveda, je ali bi lahko bila pojdite do samega konca. 490 00:22:37,360 --> 00:22:40,074 Ampak, če razmišljate o Računalnik in vrsta spomina, 491 00:22:40,074 --> 00:22:41,990 ti ljudje gredo da imajo shuffle prek 492 00:22:41,990 --> 00:22:43,260 da bi naredili prostor za to osebo. 493 00:22:43,260 --> 00:22:46,930 In da n minus 1 shufflings, n minus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings je nekako dogaja za mano, ne pred mano 495 00:22:50,660 --> 00:22:52,710 kot prej, v nekem smislu. 499 00:22:52,557 --> 00:22:54,640 Zdaj, kot prahi, in kot ste morda opazili na spletu 500 00:22:54,640 --> 00:22:57,699 Če ste začeli drezati okoli okoli vrste, obstaja toliko različnih tisti 501 00:22:57,699 --> 00:22:59,490 tam, nekateri od njih boljši od drugih. 502 00:22:59,490 --> 00:23:02,200 Dejansko, bogosort je ena to je kar zabavno pogledati. 503 00:23:02,200 --> 00:23:06,650 Bogosort traja niz številke ali reči kart, 504 00:23:06,650 --> 00:23:09,870 jih naključno premeša, in preveri, če oni razporejene. 505 00:23:09,870 --> 00:23:12,130 In če ne, to počne znova. 506 00:23:12,130 --> 00:23:14,140 In če ne, to počne znova. 507 00:23:14,140 --> 00:23:15,440 Če ne, ga pa še enkrat. 508 00:23:15,440 --> 00:23:17,060 Neverjetno neumno. 509 00:23:17,060 --> 00:23:19,520 >> In res, če ste prebrali kot članek Wikipedia, 510 00:23:19,520 --> 00:23:21,200 njegov vzdevek je nekako neumno. 511 00:23:21,200 --> 00:23:25,180 To bo na koncu delovalo, upajmo, dovolj časa, 512 00:23:25,180 --> 00:23:28,240 vendar časa lahko traja kar nekaj časa. 513 00:23:28,240 --> 00:23:31,650 Torej, če bi lahko, kaj je hitrost stvari up od na primer Mary Beth je prej, 514 00:23:31,650 --> 00:23:35,150 ki jih ima nekaj več elementov, ampak dve procesorji. 515 00:23:35,150 --> 00:23:37,100 Dva človeka, če vas Ne bi se mi pridružil. 516 00:23:37,100 --> 00:23:40,972 Kako približno 1 tukaj, in dajmo tam-- nikogar tam? 517 00:23:40,972 --> 00:23:41,722 Nihče tam? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Vam s črno shirt, ja, pridi dol. 520 00:23:44,190 --> 00:23:45,000 V redu, kako ti je ime? 521 00:23:45,000 --> 00:23:45,720 >> OBČINSTVO: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Kaj je to? 523 00:23:46,100 --> 00:23:46,766 >> OBČINSTVO: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter, David, lepo, da sva se spoznala. 525 00:23:49,450 --> 00:23:53,670 Dobro, imamo Petra tukaj, če vas želijo priti na mizo tukaj. 526 00:23:53,670 --> 00:23:54,550 In kako ti je ime? 527 00:23:54,550 --> 00:23:55,216 >> OBČINSTVO: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, lepo, da sva se spoznala. 530 00:23:57,030 --> 00:23:58,060 Elena izpolnjujejo Petra. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 In potrebovali bomo Andrewa tukaj, kot tudi, prosim. 533 00:24:02,290 --> 00:24:06,107 In vaš izziv bo da se za razvrščanje kart. 534 00:24:06,107 --> 00:24:08,190 In če je ne poznajo, deck kartic naj bi v končni fazi 535 00:24:08,190 --> 00:24:11,064 razvrščeni malo nekaj podobnega to, če bomo storili klubih, nato pa 536 00:24:11,064 --> 00:24:13,660 lopatica, nato srca in diamanti, od asa kot eno, 537 00:24:13,660 --> 00:24:15,570 vse tja do kralja. 538 00:24:15,570 --> 00:24:20,890 >> Kartice bom dal se bo 52 v količini. 539 00:24:20,890 --> 00:24:23,160 Bomo podobno Čas vas, v samo nekaj trenutkov. 540 00:24:23,160 --> 00:24:26,410 Bomo vrgli Andrew na zaslonu tukaj 541 00:24:26,410 --> 00:24:28,170 tako, da vas gledam, kako to storiti. 542 00:24:28,170 --> 00:24:31,070 In da vse to je še toliko bolj vidna, 543 00:24:31,070 --> 00:24:33,490 To so kartice sem dobil na Amazon. 544 00:24:33,490 --> 00:24:42,861 Torej so že naključno razporejene in bomo čas. 545 00:24:42,861 --> 00:24:44,610 In bomo obdržati pravi tokrat, 546 00:24:44,610 --> 00:24:47,820 Tako bomo poskušali prisiliti ker drugače bo ta dobil dolgočasno 547 00:24:47,820 --> 00:24:48,460 hitro. 548 00:24:48,460 --> 00:24:53,860 Če bi lahko nadaljevali rešiti 52 elementi skupaj preko nekaterih sredstev, takoj. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> In spet, kot smo gledal to Fantje, kaj storiti, na koncu 551 00:25:07,180 --> 00:25:10,200 se dogaja, da dobimo jasno Rezultat, pomislite res 552 00:25:10,200 --> 00:25:12,962 kako oni vsak počne, kako bi to opisal. 553 00:25:12,962 --> 00:25:15,045 Ker enkrat, to so Vsi postopki, algoritmi 554 00:25:15,045 --> 00:25:17,090 da se nam zdi samoumevno, kot človeku. 555 00:25:17,090 --> 00:25:22,349 Vendar ste verjetno že dolgo intuicija, dolgo pred vami še 556 00:25:22,349 --> 00:25:24,390 razmišljala o čemer računalništva vam class 557 00:25:24,390 --> 00:25:27,223 Morda so imeli z intuicijo za reševanje problemov, kot je ta. 558 00:25:27,223 --> 00:25:29,560 Toda, ko boste prepoznali vzorci in začnejo 559 00:25:29,560 --> 00:25:32,407 za formaliziranje ukrepe, s katerimi ste reševanje teh problemov, 560 00:25:32,407 --> 00:25:35,490 boste ugotovili, da vam lahko reši veliko bolj zanimivo in veliko bolj kompleksna 561 00:25:35,490 --> 00:25:39,190 Težave hitro. 562 00:25:39,190 --> 00:25:42,351 Torej je nekdo iz občinstva, kar je vsaj en element algoritma 563 00:25:42,351 --> 00:25:43,350 da uporabljate tu? 564 00:25:43,350 --> 00:25:44,275 >> OBČINSTVO: [neslišno] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Kaj je to? 566 00:25:45,150 --> 00:25:47,062 OBČINSTVO: Z obleko. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Z obleko. 568 00:25:47,770 --> 00:25:50,630 Torej, najprej so razvrščene vse diamantov skupaj 569 00:25:50,630 --> 00:25:52,560 zdi se, vse srca skupaj kot se zdi, 570 00:25:52,560 --> 00:25:56,520 in tako naprej, ne glede Za številkami kartic. 571 00:25:56,520 --> 00:26:00,900 In zdaj se pojavijo, na primer, da se jih sortiranju po številu. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Zelo dobro. 574 00:26:08,910 --> 00:26:12,370 >> V redu, kaj se dogaja, da biti zadnji korak, potem tukaj? 575 00:26:12,370 --> 00:26:16,950 Ko imamo štiri razvrstite obleke, kaj storiti moramo storiti na štiri kupe 576 00:26:16,950 --> 00:26:20,059 za dosego enega razporejene krova, preprosto? 577 00:26:20,059 --> 00:26:21,350 Zato jih moramo ponovno združiti. 578 00:26:21,350 --> 00:26:25,160 >> Torej je zanimiva ideja, ki še enkrat, si trditi, je zelo intuitiven celo 579 00:26:25,160 --> 00:26:28,140 če bi si nikoli ne bi udaril da vrste etiket. 580 00:26:28,140 --> 00:26:31,900 Ta temeljni pojem delitve Problem ni v pol tem času, 581 00:26:31,900 --> 00:26:33,410 vendar vsaj na štiri dele. 582 00:26:33,410 --> 00:26:36,810 Reševanje precej v bistvu enaki problemi 583 00:26:36,810 --> 00:26:40,480 ločeno drug od drugega, in nato združitev rezultatov. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 In odlično, opravljeno. 586 00:26:50,140 --> 00:26:52,140 V redu, velik krog aplavz, če bi lahko. 587 00:26:52,140 --> 00:26:56,480 >> [APLAVZ] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Nimam pojma, kaj bom storiti z njimi, ampak tukaj imaš. 589 00:26:59,740 --> 00:27:01,690 Najlepša hvala. 590 00:27:01,690 --> 00:27:04,660 Pa poglejmo, dve minuti in osem sekund, 591 00:27:04,660 --> 00:27:07,490 Če želite izzvati svoje prijatelje. 592 00:27:07,490 --> 00:27:12,160 Kaj pa se dogaja, da lahko traja od tega 593 00:27:12,160 --> 00:27:13,830 da bomo lahko še povečala splošno? 594 00:27:13,830 --> 00:27:16,080 No, mislim nazaj ta niz številk, 595 00:27:16,080 --> 00:27:19,060 in mislim nazaj, zdaj z nekaterimi psevdokoda smo zapisali v preteklosti, 596 00:27:19,060 --> 00:27:22,080 in to je bil psevdokoda za reševanju problema iz telefonskega imenika. 597 00:27:22,080 --> 00:27:25,150 Pri čemer je v psevdokoda I naštel bolj metodičen način 598 00:27:25,150 --> 00:27:28,400 opisati, kako sem zelo intuitiven človeški algoritem deljenja telefon 599 00:27:28,400 --> 00:27:31,650 knjige na pol, ponovitev, ponavljam, ponavljam, dokler ne najdem nekoga, kot je Mike Smith, 600 00:27:31,650 --> 00:27:33,790 če je res, v telefonskem imeniku. 601 00:27:33,790 --> 00:27:37,610 >> Ampak sem nekako uporabiti, kaj bom poklical Zelo iterativni pristop tukaj, 602 00:27:37,610 --> 00:27:42,160 zlasti obvestila vrstica 8 in 11 črta. 603 00:27:42,160 --> 00:27:46,750 Tisti, ki so dokaz, ponavljajoč pristop, pristop zanka, 604 00:27:46,750 --> 00:27:49,040 ker to je točno Vedenje, ki ga povzroči. 605 00:27:49,040 --> 00:27:52,910 Te vrstice oba pravim, pojdi na tretja vrstica, in lahko nekako 606 00:27:52,910 --> 00:27:55,140 mislim, da je v vašem mislih kot zanka. 607 00:27:55,140 --> 00:27:59,080 To vam je povedal, da gredo nazaj v korak tri in ponavljam, znova in znova, 608 00:27:59,080 --> 00:28:00,010 in znova. 609 00:28:00,010 --> 00:28:04,410 >> Toda kaj, če bomo vzvod ključno idejo Tukaj smo, da ni zadnji čas, 610 00:28:04,410 --> 00:28:10,280 in poenostaviti linijo 8 in linija 11 in njihove sosede 611 00:28:10,280 --> 00:28:12,840 kot samo to, v rumeni barvi. 612 00:28:12,840 --> 00:28:16,480 To ni bistveno skrajšanje psevdokoda zelo veliko, 613 00:28:16,480 --> 00:28:20,530 vendar je bistveno spreminjajo naravo mojega algoritma. 614 00:28:20,530 --> 00:28:24,220 Kaj bom zdaj rekel, V koraku 7, v koraku 10, 615 00:28:24,220 --> 00:28:29,140 je iskanje Mika na točno enak način, 616 00:28:29,140 --> 00:28:31,580 ampak samo na levi strani pol ali desno polovico. 617 00:28:31,580 --> 00:28:33,420 >> Torej, z drugimi besedami, če Izhajam iz enega koraka, 618 00:28:33,420 --> 00:28:36,150 pick up telefonski imenik, odprta do sredine iz telefonskega imenika, poglej imen, 619 00:28:36,150 --> 00:28:39,010 če Smith je med Ime mi je, pokličite Mike, ostalo 620 00:28:39,010 --> 00:28:44,340 če Smith je že prej v knjigi, Sedmi korak iskanje Mike v levi polovici knjige. 621 00:28:44,340 --> 00:28:47,130 Ampak to nekako občutek to me zapusti visi, kajne? 622 00:28:47,130 --> 00:28:49,240 V rumeni barvi, je pouk, ampak kako narediti I 623 00:28:49,240 --> 00:28:51,870 iskanje Mike v levo polovica telefonskega imenika? 624 00:28:51,870 --> 00:28:54,210 Kje imam algoritem, s katerim sem 625 00:28:54,210 --> 00:28:57,100 Lahko poiščete nekoga, kot Mike Smith? 626 00:28:57,100 --> 00:28:58,980 No, to je nas strmel v obraz. 627 00:28:58,980 --> 00:29:03,090 Lahko dobesedno uporabite točno isto Program dejansko dogaja na vrh 628 00:29:03,090 --> 00:29:06,490 spet in ponovno tek enake vrstic kode. 629 00:29:06,490 --> 00:29:10,610 >> Torej, čeprav bi to moralo počutijo kot nekaj cikličnega opredelitve 630 00:29:10,610 --> 00:29:13,480 kjer si odgovorite, da je nekdo Vprašanje, ki ga je kar nekako prosi 631 00:29:13,480 --> 00:29:15,990 spet isto vprašanje, kot so, zakaj, zakaj, zakaj? 632 00:29:15,990 --> 00:29:21,580 Realnost je, ker smo težko kodirane Nekaj ​​posebnih linij, korak 4, 633 00:29:21,580 --> 00:29:25,320 , ki je, če in korak 12, ki je dejansko še ena veja, 634 00:29:25,320 --> 00:29:30,120 ker imamo tiste stopgap ukrepe, Ta algoritem se prekine, če bomo 635 00:29:30,120 --> 00:29:32,050 Ugotovijo, Mike, ali če tega ne storimo. 636 00:29:32,050 --> 00:29:36,810 Toda v koraku 7 in 10. Zdaj imamo kaj bomo klic rekurzivni algoritem. 637 00:29:36,810 --> 00:29:40,420 In rekurzija je res močna ideja da je malo um upogibanje na prvi, 638 00:29:40,420 --> 00:29:42,500 da bomo lahko zdaj uporabljajo, kakor sledi. 639 00:29:42,500 --> 00:29:46,600 >> Zlivanjem bo zadnja vrsta, ki gledamo, vsaj v razredu formalno. 640 00:29:46,600 --> 00:29:50,040 In to je bistveno drugačna od teh zadnjih treh, vsekakor pa 641 00:29:50,040 --> 00:29:52,140 zadnja štiri, če štejemo bogosort. 642 00:29:52,140 --> 00:29:54,810 Tukaj je psevdokoda za urejanje z zlivanjem. 643 00:29:54,810 --> 00:30:00,170 Ko se na vhodu n elementov, tako glede matrika velikosti n, če je n manj kot 2, 644 00:30:00,170 --> 00:30:01,040 vrniti. 645 00:30:01,040 --> 00:30:03,610 Torej, zakaj moram, da sanity najprej preveril? 646 00:30:03,610 --> 00:30:09,477 Kaj pa posledice, če bi ti roko polje, katerega dolžina je n manj kot 2? 647 00:30:09,477 --> 00:30:11,060 To je že urejeno, je očitno, kajne? 648 00:30:11,060 --> 00:30:13,640 Ker ima seznam bodisi en element, ki je trivially 649 00:30:13,640 --> 00:30:15,180 razporejene, saj je Edina stvar, ki obstaja. 650 00:30:15,180 --> 00:30:18,138 Ali je velikosti nič, ki pomeni ni nič za razvrščanje, tako da je po naravi 651 00:30:18,138 --> 00:30:18,720 je urejeno. 652 00:30:18,720 --> 00:30:20,410 Obstaja samo ni nič narobe. 653 00:30:20,410 --> 00:30:22,310 Torej, to je naša tako imenovana osnovna. 654 00:30:22,310 --> 00:30:24,440 >> To je podobno kot v duhu s tem, kar smo naredili z Mikom. 655 00:30:24,440 --> 00:30:26,023 Če Mike je v telefonskem imeniku, ga pokličite. 656 00:30:26,023 --> 00:30:27,740 Če ga ni tam, obupajte. 657 00:30:27,740 --> 00:30:31,240 To je tako imenovana osnovna, se prepričajte, Ta algoritem ob koncu dneva 658 00:30:31,240 --> 00:30:33,540 se bo ustavila v določenih okoliščinah. 659 00:30:33,540 --> 00:30:37,890 >> Ampak tukaj je preskok vere zdaj, drugega, razvrstiti levo polovico elementov, 660 00:30:37,890 --> 00:30:39,740 nato razvrstiti pravico polovica elementov, 661 00:30:39,740 --> 00:30:41,189 in nato združiti razvrščenih polovic. 662 00:30:41,189 --> 00:30:43,230 In tu je, če se mu zdi, kot smo copping ven. 663 00:30:43,230 --> 00:30:46,900 Sem te prosil, da razvrstite n elementov, in sem 664 00:30:46,900 --> 00:30:50,712 rekel, OK, ga s sortiranjem levo in sortiranje pravico. 665 00:30:50,712 --> 00:30:52,420 Ampak jaz govorim eno druga stvar, in to 666 00:30:52,420 --> 00:30:55,530 je ključna tema se zdi v intuicijo tako daleč, 667 00:30:55,530 --> 00:30:57,380 tam je tretji korak združevanja. 668 00:30:57,380 --> 00:31:00,430 Ki je, čeprav ji zdi tako neumno v duhu, 669 00:31:00,430 --> 00:31:02,320 kot samo združiti stvari skupaj, se zdi 670 00:31:02,320 --> 00:31:05,380 ključni korak k sestavljanje dveh problemov, ki 671 00:31:05,380 --> 00:31:07,330 so bili razdeljeni na koncu na pol. 672 00:31:07,330 --> 00:31:12,090 >> Torej zlivanjem, naredimo to, če boste humor me, z eno več demonstracij, 673 00:31:12,090 --> 00:31:14,730 samo zato, da imamo nekaj številke delati. 674 00:31:14,730 --> 00:31:19,470 Lahko zamenjam osem stres Žoge za osem ljudi? 675 00:31:19,470 --> 00:31:29,320 V redu, kaj pa vi trije, ti štirje v tem poglavju, pet, šest, in dajva 676 00:31:29,320 --> 00:31:30,720 ne 7, 8, pridi gor. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ja OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, tam gremo, plus 1. 680 00:31:38,640 --> 00:31:39,150 Odlično. 681 00:31:39,150 --> 00:31:42,000 Dobro pridi gor, dajva hitro vam številke. 682 00:31:42,000 --> 00:31:50,800 Drugič, število tri, številka štiri, Številka pet, šest, sedem, osem. 683 00:31:50,800 --> 00:31:52,140 Sem osem pravilno tokrat. 684 00:31:52,140 --> 00:31:56,390 >> OK, tako da gredo naprej, če bi lahko, in pa razporedijo v prvotni vrstni red 685 00:31:56,390 --> 00:31:59,810 da smo imeli včeraj, ki je pogledal kot je ta, če ne bi motilo. 686 00:31:59,810 --> 00:32:03,620 In dajmo pred mizo. 687 00:32:03,620 --> 00:32:06,510 Vse v redu, tako da z zlivanjem. 688 00:32:06,510 --> 00:32:08,820 To je, če se bo da bi dobili vrsto zanimivih, 689 00:32:08,820 --> 00:32:12,800 ker se zdi, da sem kar toliko manj informacij danes. 690 00:32:12,800 --> 00:32:15,149 >> Torej zlivanjem najprej na vhodu n elementov, 691 00:32:15,149 --> 00:32:18,440 in očitno ne manj kot dva, je osem let, tako da sem imel nekaj več dela. 692 00:32:18,440 --> 00:32:21,140 Torej sedaj psihično smo kot razred so zdaj v drugega podružnice, 693 00:32:21,140 --> 00:32:22,540 kar pomeni tri korake. 694 00:32:22,540 --> 00:32:25,017 Najprej moram rešiti leva polovica elementov. 695 00:32:25,017 --> 00:32:26,350 Torej, kako naj grem o tem? 696 00:32:26,350 --> 00:32:28,950 No, bom nekako duševno razdeli seznam tukaj, 697 00:32:28,950 --> 00:32:30,700 vam ne bo treba fizično premakniti, in sem 698 00:32:30,700 --> 00:32:33,180 dogaja, da se osredotoči le na leva polovica elementov tukaj. 699 00:32:33,180 --> 00:32:36,770 Torej, kako naj grem o sortiranje seznam zdaj velikosti štirih? 700 00:32:36,770 --> 00:32:38,730 Kaj je moj algoritem? 701 00:32:38,730 --> 00:32:42,580 Najprej sem preveriti, je n manj kot dve, no, tako da sem spet nadaljuje na drug blok. 702 00:32:42,580 --> 00:32:43,900 Razvrsti levo polovico elementov. 703 00:32:43,900 --> 00:32:45,608 >> Torej, zdaj spet, duševno, in to je, če 704 00:32:45,608 --> 00:32:49,550 boste morali teči veliko duševno zgodovina, če hočete. 705 00:32:49,550 --> 00:32:51,940 Zdaj sem sortiranje levo polovica levi polovici. 706 00:32:51,940 --> 00:32:57,000 Dobro, zdaj sem poklical svojega isti spajanja sortiranje algoritem, je n manj kot dva? 707 00:32:57,000 --> 00:33:00,590 Ne, to je za dva, tako da sem moral rešiti levo polovico in desno polovico. 708 00:33:00,590 --> 00:33:02,042 Torej, gremo, levi polovici razvrstiti. 709 00:33:02,042 --> 00:33:03,750 Zakaj ne samo vzemite en korak naprej. 710 00:33:03,750 --> 00:33:04,415 Kako ti je ime? 711 00:33:04,415 --> 00:33:04,860 >> OBČINSTVO: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan je stopil naprej. 714 00:33:06,040 --> 00:33:06,748 >> OBČINSTVO: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, opravljeno. 716 00:33:09,000 --> 00:33:10,090 Ste rekli Darrena ali Dan? 717 00:33:10,090 --> 00:33:10,550 >> OBČINSTVO: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, je Darren stopil naprej in se je sedaj urejeno. 720 00:33:14,422 --> 00:33:16,130 In to je skoraj Prazen trditev, kajne? 721 00:33:16,130 --> 00:33:18,862 Res ne zdi, da bi dosegli karkoli, vendar pa nadaljujmo. 722 00:33:18,862 --> 00:33:20,820 Zdaj pa me razvrstiti pravico polovica elementov. 723 00:33:20,820 --> 00:33:21,200 Kako ti je ime? 724 00:33:21,200 --> 00:33:21,690 >> OBČINSTVO: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Daj no, stopi naprej. 727 00:33:23,400 --> 00:33:25,640 Storjeno, sem razporejene Luke. 728 00:33:25,640 --> 00:33:28,570 Leva polovica je sedaj razporejene in desna polovica je sedaj urejen, 729 00:33:28,570 --> 00:33:30,770 ampak spet, tam je ključni korak tukaj. 730 00:33:30,770 --> 00:33:32,940 Kaj sem zraven morate storiti? 731 00:33:32,940 --> 00:33:33,941 Združiti razvrščenih polovic. 732 00:33:33,941 --> 00:33:36,648 Zdaj bomo morali vsi naprej in nazaj na ta način, 733 00:33:36,648 --> 00:33:38,620 ker sem nekako potrebujem nekaj prask prostora. 734 00:33:38,620 --> 00:33:40,411 To je skoraj tako kot ti Fantje so na mizi, 735 00:33:40,411 --> 00:33:42,460 in rabim malo prostora da jih premikate naprej. 736 00:33:42,460 --> 00:33:44,170 Torej bom, da se združijo vidva z iskanjem 737 00:33:44,170 --> 00:33:45,960 na levi polovici in desni polovici. 738 00:33:45,960 --> 00:33:48,740 In ki je očitno na prvem mestu, levo polovico ali desno polovico? 739 00:33:48,740 --> 00:33:52,710 Torej desno polovico, tako da gremo preko Luke tukaj, da prvotni položaj Darren je. 740 00:33:52,710 --> 00:33:57,640 In zdaj, da združijo svoje levo polovico leta, Darren se dogaja, da se premaknete tam. 741 00:33:57,640 --> 00:33:59,750 >> Torej, občutek skoraj bubble sort učinek, 742 00:33:59,750 --> 00:34:02,482 ampak moja temeljna algoritem, Zelo tokrat drugače. 743 00:34:02,482 --> 00:34:04,815 Ampak zdaj je, če se stvari malo siten, ker vas 744 00:34:04,815 --> 00:34:06,810 morajo duševno previjanje kje sem pustil off. 745 00:34:06,810 --> 00:34:09,893 Pravkar sem združila razvrstite polovic, kar pomeni, da sem kje v mojem algoritmu? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Imam razvrstiti desno polovico, kajne? 748 00:34:13,770 --> 00:34:15,910 >> Če ste nazaj, dobesedno na video, boste 749 00:34:15,910 --> 00:34:18,339 vidite, da imamo za to točka Luke in Darrena 750 00:34:18,339 --> 00:34:21,370 s sortiranjem levo polovica levi polovici. 751 00:34:21,370 --> 00:34:23,430 Potem smo se združili s tistimi, Urejeni polovičke, ki 752 00:34:23,430 --> 00:34:27,941 pomeni naslednji korak je neke desno polovico levi polovici. 753 00:34:27,941 --> 00:34:29,649 Vse v redu, tako da je To naredite hitreje. 754 00:34:29,649 --> 00:34:33,282 V redu, šest, grem zahtevku ti so zdaj razporejene, pridi naprej. 755 00:34:33,282 --> 00:34:33,990 Kako ti je ime? 756 00:34:33,990 --> 00:34:34,589 >> OBČINSTVO: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano je sedaj urejeno. 759 00:34:36,010 --> 00:34:36,450 In kako ti je ime? 760 00:34:36,450 --> 00:34:37,080 >> OBČINSTVO: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex je sedaj urejeno. 762 00:34:38,379 --> 00:34:40,750 Levo pol, desno polovico, kar je zadnji korak? 763 00:34:40,750 --> 00:34:41,250 Merge. 764 00:34:41,250 --> 00:34:44,310 Precej nepomembno, zato sem dogaja, da se združijo v šestih, 765 00:34:44,310 --> 00:34:46,930 stopiti korak nazaj, osem, korak nazaj. 766 00:34:46,930 --> 00:34:49,530 In zdaj opazil je to uporabno takeaway, kaj 767 00:34:49,530 --> 00:34:53,930 Zdaj je res o levi polovici seznam, ne glede na to, kako smo začeli? 768 00:34:53,930 --> 00:34:55,090 To je urejeno. 769 00:34:55,090 --> 00:34:57,750 >> Zdaj to ni urejeno v veliki načrt stvari, 770 00:34:57,750 --> 00:35:00,250 vendar je razvrščen neodvisno na drugi polovici. 771 00:35:00,250 --> 00:35:04,100 Kaj zdaj korak pa sem, če sem na vodi previjanje, kako se je začela zgodba? 772 00:35:04,100 --> 00:35:05,680 Zdaj moram rešiti desno polovico. 773 00:35:05,680 --> 00:35:07,630 Torej, zdaj smo pot nazaj začetek zgodbe, 774 00:35:07,630 --> 00:35:08,921 in naredimo to hitreje. 775 00:35:08,921 --> 00:35:11,320 Torej bom, da razvrstite desno polovico celotnega seznama. 776 00:35:11,320 --> 00:35:13,060 Kaj je naslednji korak? 777 00:35:13,060 --> 00:35:15,840 Razvrstimo levi polovici desni polovici. 778 00:35:15,840 --> 00:35:18,715 Razvrstite levo polovico levi polovici desni polovici. 779 00:35:18,715 --> 00:35:19,590 In kako ti je ime? 780 00:35:19,590 --> 00:35:20,230 >> OBČINSTVO: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, korak naprej, narediti. 782 00:35:21,970 --> 00:35:22,860 Leva polovica je razvrščen. 783 00:35:22,860 --> 00:35:23,330 In kako ti je ime? 784 00:35:23,330 --> 00:35:23,820 >> OBČINSTVO: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, naredimo korak naprej, sedaj ste razvrščeni. 786 00:35:25,620 --> 00:35:27,010 Kaj je ključni korak zdaj? 787 00:35:27,010 --> 00:35:27,510 Merge. 788 00:35:27,510 --> 00:35:30,509 Torej ga bo, da se združijo v mestu tukaj, če bi lahko naredili korak nazaj, 789 00:35:30,509 --> 00:35:32,930 in tri se bo naredili korak nazaj, združiti. 790 00:35:32,930 --> 00:35:38,080 Torej leva polovica desna polovica, je sedaj urejeno. 791 00:35:38,080 --> 00:35:41,747 Odkrito povedano, ta algoritem počuti kot mi izgubljamo tako več časa kot prej, 792 00:35:41,747 --> 00:35:44,830 če pa je to storila v realnem času, se bomo glej, kaj takeaways bo. 793 00:35:44,830 --> 00:35:47,970 Zdaj sem tu, kajne polovica desni polovici, 794 00:35:47,970 --> 00:35:50,170 Naj gredo naprej in razvrstiti levo polovico. 795 00:35:50,170 --> 00:35:51,482 Korak naprej, kako ti je ime? 796 00:35:51,482 --> 00:35:52,190 OBČINSTVO: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey je sedaj urejeno. 798 00:35:53,210 --> 00:35:53,570 Kako ti je ime? 799 00:35:53,570 --> 00:35:54,200 >> OBČINSTVO: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina je zdaj razvrščen kot No, če si vzamete en korak naprej. 801 00:35:57,033 --> 00:36:00,690 Ključni korak je tu zdaj združiti, sem bom odtrgal od mojih dveh seznamov, 802 00:36:00,690 --> 00:36:01,720 levo in desno. 803 00:36:01,720 --> 00:36:05,150 Pet se dogaja, da pridejo prvi, in sedem bo prišel naslednji. 804 00:36:05,150 --> 00:36:06,410 In spet, da je to namerno. 805 00:36:06,410 --> 00:36:08,535 Dejstvo, da so si ob koraka naprej in nazaj 806 00:36:08,535 --> 00:36:12,997 je mišljeno, da predstavljajo, da ne moremo storiti ta algoritem v mestu kot enostavno 807 00:36:12,997 --> 00:36:15,830 kot nekakšen mehurček in izbora vrste, in vstavljanje sort, kjer smo pravkar 808 00:36:15,830 --> 00:36:16,960 hranijo zamenjavo ljudi. 809 00:36:16,960 --> 00:36:19,940 Sem dobesedno potrebujejo neke za praske papirja, v katerem 810 00:36:19,940 --> 00:36:21,827 da se ti ljudje medtem ko jaz združitev, 811 00:36:21,827 --> 00:36:23,410 in potem sem jih dal nazaj na svoje mesto. 812 00:36:23,410 --> 00:36:27,260 In to je ključnega pomena, ker sem s pomočjo nov vir, prostor, ne samo enkrat. 813 00:36:27,260 --> 00:36:28,270 >> OK, to je neverjetno. 814 00:36:28,270 --> 00:36:32,050 Levo polovico razporejene, desna polovica je urejene tako, da je sedaj ključni korak združitev. 815 00:36:32,050 --> 00:36:33,450 Kako bom združiti to? 816 00:36:33,450 --> 00:36:35,470 Torej, če boste sledili moj levo roko in desno roko, 817 00:36:35,470 --> 00:36:38,930 Bom izpostaviti mojo levo roko na levi polovici, moja desna roka 818 00:36:38,930 --> 00:36:42,680 na desni polovici, in zdaj moram odloči, korak za korakom, na koga naj se stapljajo v. 819 00:36:42,680 --> 00:36:44,650 Ki je očitno na prvem mestu? 820 00:36:44,650 --> 00:36:45,150 Številka ena. 821 00:36:45,150 --> 00:36:47,327 Torej, pridi sem, Tukaj je naš scratch pad. 822 00:36:47,327 --> 00:36:49,910 Torej, zdaj številka ena, in obvestilo kaj bom naredil z mojo desno roko, 823 00:36:49,910 --> 00:36:54,152 Bom premakniti mojo desno eni strani stopite na točko številka tri, 824 00:36:54,152 --> 00:36:55,860 in zdaj moram narediti Enako odločitev. 825 00:36:55,860 --> 00:36:58,387 In dejansko stojijo pravico v front of Luke tukaj, če bi lahko, 826 00:36:58,387 --> 00:36:59,720 zato, ker je to naša scratch pad. 827 00:36:59,720 --> 00:37:00,610 Torej, kdo gre zraven? 828 00:37:00,610 --> 00:37:05,000 Imamo Luke z dvojko ali Chris s številko tri. 829 00:37:05,000 --> 00:37:07,460 Očitno Luke, število dva, tako da ste prišli sem. 830 00:37:07,460 --> 00:37:11,270 >> Ampak moja leva roka sedaj se dogaja, da se poveča do točke na Darrena, 831 00:37:11,270 --> 00:37:15,160 in tukaj je ključ odnese s združujejo, bom vztrajati početje to, 832 00:37:15,160 --> 00:37:17,340 seveda, če ste prijazni od slediti logiki. 833 00:37:17,340 --> 00:37:19,670 Ampak moje roke niso nikoli bo šel nazaj, 834 00:37:19,670 --> 00:37:23,861 kar pomeni, da sem samo kdaj se gibljejo na levo z mojim procesu priključevanja, 835 00:37:23,861 --> 00:37:26,360 in to se dogaja, da je ključ do naša analiza, v trenutku. 836 00:37:26,360 --> 00:37:27,859 >> Torej, zdaj pa je zapravil to zelo hitro. 837 00:37:27,859 --> 00:37:31,650 Torej tri pride zraven, nato štiri prihaja naslednji, 838 00:37:31,650 --> 00:37:38,750 in zdaj pet pride zraven, potem pa šest, in sedem, in nato končno osem. 839 00:37:38,750 --> 00:37:42,960 Počutim se kot najpočasnejšim algoritmom še ni, vendar ne, če smo dejansko 840 00:37:42,960 --> 00:37:45,510 teči hkrati vrste hitrosti ure, tako da 841 00:37:45,510 --> 00:37:48,106 govorijo, z enako tiktaka ura kot prej. 842 00:37:48,106 --> 00:37:48,605 Zakaj? 843 00:37:48,605 --> 00:37:51,100 No, vzemimo pogled na končni rezultat. 844 00:37:51,100 --> 00:37:56,990 >> Pojdimo nazaj sem, pustite me dvigni demonstracijo vizualno 845 00:37:56,990 --> 00:37:59,030 o tem, kaj smo pravkar naredili. 846 00:37:59,030 --> 00:38:06,110 Povečave tukaj, na tem stran tukaj, povedal Firefox 847 00:38:06,110 --> 00:38:08,200 da želimo, da se v vrsto v tem polju, dajva 848 00:38:08,200 --> 00:38:11,260 pravijo mehurček vrste, s katerimi zdaj smo dobro seznanjeni, 849 00:38:11,260 --> 00:38:14,130 izbira sort, kar je še en precej enostavno ena, 850 00:38:14,130 --> 00:38:18,250 in zdaj današnja merge sort, ki bo naš climactic konec. 851 00:38:18,250 --> 00:38:21,530 Razlog, da se je toliko več tukaj z ljudmi in me je verbalno, 852 00:38:21,530 --> 00:38:23,480 seveda, sem pojasnil na vsakem koraku. 853 00:38:23,480 --> 00:38:26,920 Ampak, če si preprosto izvršiti to, kar je precej kot smo bubble sort in izbor 854 00:38:26,920 --> 00:38:30,890 nekako ne le vizualno, watch kako veliko bolj učinkovito 855 00:38:30,890 --> 00:38:33,330 To vzvoda delitev in osvajanje 856 00:38:33,330 --> 00:38:39,150 če se lahko uporablja za vrsto podatkov, ki je Niti velikost osem, ampak tudi veliko, 857 00:38:39,150 --> 00:38:39,970 veliko večji. 858 00:38:39,970 --> 00:38:44,585 Dajem ti zlivanjem, z ramo ob stran s temi drugimi algoritmi. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 To se dogaja, da bi dobili boleče hitro in konec 861 00:38:58,530 --> 00:39:00,890 ni posebej podnebnih, so šele na koncu razporejene. 862 00:39:00,890 --> 00:39:05,280 Ampak ključ vzeti, je, da poglej koliko hitreje zlivanjem 863 00:39:05,280 --> 00:39:08,110 je, če misliš, da sem nekako zajebavam s tabo. 864 00:39:08,110 --> 00:39:13,100 Če to storimo en končni čas, Pojdimo osvežite to, vrnimo 865 00:39:13,100 --> 00:39:14,960 in izberite bubble vrste, in samo za brcne, 866 00:39:14,960 --> 00:39:17,330 dajmo izbrati vstavljanje sort, samo za dober ukrep. 867 00:39:17,330 --> 00:39:20,020 In tokrat spet, dajva izberite zlivanjem in dajva 868 00:39:20,020 --> 00:39:21,595 dejansko vodijo te bok. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> In to v resnici ni, krompir. 871 00:39:26,930 --> 00:39:31,140 Kar sem dejansko naredil, je imam razdeljen svoj prispevek na pol, še enkrat, 872 00:39:31,140 --> 00:39:32,240 in znova in znova. 873 00:39:32,240 --> 00:39:35,590 In tam je samo toliko časa si lahko razdeliti vaš vložek v polovici, levo 874 00:39:35,590 --> 00:39:36,240 in desno. 875 00:39:36,240 --> 00:39:39,425 Kakšna je formula, ki smo ostali vidimo , ki opisuje delitev na pol 876 00:39:39,425 --> 00:39:41,050 znova in znova in znova in znova? 877 00:39:41,050 --> 00:39:41,890 >> OBČINSTVO: Log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Log n. 879 00:39:42,760 --> 00:39:46,300 Ampak potem je tu še en drug ključni korak, Ta algoritem je ni log n korakih. 880 00:39:46,300 --> 00:39:48,992 Če bi bilo samo log n korakih, mi bi bili v istem problemu 881 00:39:48,992 --> 00:39:51,200 kot prej, kadar ne moremo prepričan je vse urejeno. 882 00:39:51,200 --> 00:39:54,480 Moraš minimalno poglej n elementov biti prepričani, n elementi so razporejene, 883 00:39:54,480 --> 00:39:55,950 drugače je preskok vere. 884 00:39:55,950 --> 00:39:59,810 >> Torej, to je minimalno log n korakih, vendar kaj pa ta ključni korak priključevanja 885 00:39:59,810 --> 00:40:04,370 kjer sem združila moja leva in desna polovica pol in se sprehodil po odru? 886 00:40:04,370 --> 00:40:06,980 Koliko korakov je, da združim? 887 00:40:06,980 --> 00:40:10,150 To je n, ampak nisem ravno združiti končni čas. 888 00:40:10,150 --> 00:40:15,089 Na vsakem od teh ugnezdene klicev, na vsaki teh ugnezdene spajanju, sem še vedno razporejene. 889 00:40:15,089 --> 00:40:18,380 Sem združila ta dva fanta, potem ti dve fantje, nato pa ta dva in tako naprej. 890 00:40:18,380 --> 00:40:19,955 >> Torej sem se združujejo spet in spet. 891 00:40:19,955 --> 00:40:20,580 Kolikokrat? 892 00:40:20,580 --> 00:40:23,510 Torej, vsakič, ko sem razdeljen seznam za polovico, sem spajanje. 893 00:40:23,510 --> 00:40:25,460 Razdelite seznam na pol, naredite spajanje. 894 00:40:25,460 --> 00:40:28,570 Torej, če je tako, da se seznam mogoče storiti dnevnik n-krat, 895 00:40:28,570 --> 00:40:33,880 in združitev na koncu prevzame n koraki, kaj bi bilo zdaj zgornja 896 00:40:33,880 --> 00:40:37,000 vezan na delovanje Čas našega algoritma? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> In res, da je kaj Tu smo dosegli. 899 00:40:40,560 --> 00:40:44,650 Tako občutek, da ste videli vizualno ko te tri stvari teči z ramo ob rami 900 00:40:44,650 --> 00:40:47,930 je n kvadrat pred n kvadrat pred n log n. 901 00:40:47,930 --> 00:40:51,010 Ki načeloma bomo videli, ne samo danes, ampak v prihodnje 902 00:40:51,010 --> 00:40:52,760 je še veliko, veliko hitreje. 903 00:40:52,760 --> 00:40:56,010 Aplavz za te fante, Jih bom nagradil z stresnih žogic. 904 00:40:56,010 --> 00:41:00,260 Pojdimo preložitvi danes tukaj, in vas bomo videli v ponedeljek. 905 00:41:00,260 --> 00:41:02,255