1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Előadó: Rendben, ez CS50. 3 00:00:14,910 --> 00:00:19,020 Ez a három hét végén, és ha Ön még nem vette igénybe már, 4 00:00:19,020 --> 00:00:21,790 tudja, hogy nem lesz ebéd pénteken a szokásos módon, ahol 5 00:00:21,790 --> 00:00:25,430 élvezheti a jó beszélgetés és élelmiszerek Tűz és jég 6 00:00:25,430 --> 00:00:27,980 néhány CS50 a munkatársak és osztálytársak. 7 00:00:27,980 --> 00:00:30,170 Fej ezt az URL itt. 8 00:00:30,170 --> 00:00:33,420 >> Most már emlékszem, vagy hamarosan meg kell ismertetni, 9 00:00:33,420 --> 00:00:35,970 ezeket a dolgokat itt, ami kapnak ki a végén 10 00:00:35,970 --> 00:00:37,850 A félév számos osztályok. 11 00:00:37,850 --> 00:00:40,870 Úgynevezett vizsga kék könyvet, amelyben írjuk meg a választ vizsgák. 12 00:00:40,870 --> 00:00:44,240 Most van itt 26 ilyen kék könyv, mindegyiken 13 00:00:44,240 --> 00:00:47,580 van írva a név, A-tól Z és valóban a nevek, hogy egyszerű, A 14 00:00:47,580 --> 00:00:50,490 keresztül Z. És az egyik a célok kéznél ma 15 00:00:50,490 --> 00:00:53,910 lesz, hogy továbbra is mi mi hétfőn kezdődött, ami nem 16 00:00:53,910 --> 00:00:57,830 annyira nézett kódot, de tényleg nézett ötletek és problémamegoldás. 17 00:00:57,830 --> 00:01:00,170 Az egyik a célok és ígéretek a tanfolyam 18 00:01:00,170 --> 00:01:02,985 az, hogy megtanít gondolkodni alaposan, több módszeresen, 19 00:01:02,985 --> 00:01:05,400 és megoldani a problémákat hatékonyabban. 20 00:01:05,400 --> 00:01:09,526 És valóban, amit tehetünk, hogy valóban anélkül, érintése egy sor kódot. 21 00:01:09,526 --> 00:01:12,150 Szóval van egy pár elefánt ma ide, narancs és kék, 22 00:01:12,150 --> 00:01:15,780 ha tudnánk egy önkéntes, talán a távolabb, mint máskor. 23 00:01:15,780 --> 00:01:18,070 Mi a helyzet ott, gyere le. 24 00:01:18,070 --> 00:01:24,180 Melynek célja lesz, hogy segít plusz kezeli ezt a vizsgát itt. 25 00:01:24,180 --> 00:01:24,935 Mi a neve? 26 00:01:24,935 --> 00:01:25,768 >> Közönség: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Előadó: Mary Beth, gyere fel. 28 00:01:27,560 --> 00:01:29,560 Hadd a mikrofont itt. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Örülök, hogy találkoztunk. 31 00:01:32,880 --> 00:01:34,005 >> Közönség: Örülök, hogy találkoztunk. 32 00:01:34,005 --> 00:01:36,790 Előadó: Rendben, így már itt kék könyvet A-tól Z-ig, 33 00:01:36,790 --> 00:01:41,680 és én fogom állítani, hogy Van egy, a diákok, 34 00:01:41,680 --> 00:01:45,770 és jönnek a némileg véletlenszerűen a végén egy három órás vizsga blokk, 35 00:01:45,770 --> 00:01:49,400 így ők kiöntött néhány félig véletlen sorrendben, mint ez. 36 00:01:49,400 --> 00:01:54,510 Most a munka egy pillanat lesz a be-- ez valójában hogyan kap 37 00:01:54,510 --> 00:01:56,820 fordult végén az osztály, a legvalószínűbb. 38 00:01:56,820 --> 00:02:01,120 Az Ön feladata most lesz, egészen egyszerűen, hogy rendezni ezeket a kék könyv nekünk 39 00:02:01,120 --> 00:02:05,220 A-tól Z- 40 00:02:05,220 --> 00:02:08,400 >> Közönség: Ó, ez fog tartani örökre. 41 00:02:08,400 --> 00:02:13,747 >> Előadó: És mi lesz nézni ahogy ezt megteszi, nincs nyomás. 42 00:02:13,747 --> 00:02:15,330 Közönség: Nem, nincs nyomás, vagy bármi. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: És a móka kedvéért, tegyük fel egy időzítő. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> Közönség: Annyira szórakoztató, annyira szórakoztató. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Előadó: tudom tartani a mikrofont az Ön számára. 49 00:02:38,574 --> 00:02:40,240 Rendben, most már csak megduplázódott a sebesség. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Tehát addig is, hadd tegyek fel, mi van lesz a kérdés Mary Beth 52 00:02:49,060 --> 00:02:51,540 az, amit csinál, hogy van megy a megoldásában? 53 00:02:51,540 --> 00:02:54,040 És valóban, lehet, hogy nincs már, gondoltam valami 54 00:02:54,040 --> 00:02:57,440 olyan egyszerű, mint amikor kiválasztotta akár 26 könyv, mint ez, 55 00:02:57,440 --> 00:02:59,350 amelyek egy természetes rendelési nekik. 56 00:02:59,350 --> 00:03:01,335 Mi az a folyamat hogy ténylegesen használni? 57 00:03:01,335 --> 00:03:03,770 Ez meglehetősen véletlenszerű csak szedés az első látható 58 00:03:03,770 --> 00:03:05,250 és megvalósítják azt a helyére? 59 00:03:05,250 --> 00:03:09,680 Ön először mozgatni a kezét körül Keresek egy majd keres B? 60 00:03:09,680 --> 00:03:11,722 Ön vessünk egy pillantást a pár egymás mellé 61 00:03:11,722 --> 00:03:14,680 és csak annyit, várj egy percet, ez nem helyes, és majd cserélni a sorrendben? 62 00:03:14,680 --> 00:03:16,960 Láttuk már hétfő hogy van számos módon 63 00:03:16,960 --> 00:03:22,140 melyben meg tudjuk csinálni, és Valóban, ahogy a vége felé itt, 64 00:03:22,140 --> 00:03:26,360 Azt tudomásul veszik talán , amit Mary Beth csinál. 65 00:03:26,360 --> 00:03:30,040 Van néhány cölöpök úgy tűnik, a nagyobbat, három kisebb. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Közönség: Én elrendelő ha találok két betű 68 00:03:36,415 --> 00:03:39,540 hogy tudom, hogy együtt vannak a sorrendben, Tettem őket, hogy én nem 69 00:03:39,540 --> 00:03:42,915 kell aggódnia, hogy nyomon pálya egy egész sor könyvet. 70 00:03:42,915 --> 00:03:45,706 Ez csak, ó, az első, Van ez a verem itt. 71 00:03:45,706 --> 00:03:47,580 Előadó: Szóval, mintha a puzzle darabokat, hogy 72 00:03:47,580 --> 00:03:49,860 joguk alakja egyeznek meg egymással. 73 00:03:49,860 --> 00:03:51,026 Közönség: Nagyjából, igen. 74 00:03:51,026 --> 00:03:55,320 Előadó: OK, kiváló. 75 00:03:55,320 --> 00:03:59,850 És most minden egyes ilyen cölöpök feltételezhetően sorrendje? 76 00:03:59,850 --> 00:04:00,990 >> Közönség: Igen. 77 00:04:00,990 --> 00:04:09,900 >> Előadó: Rendben, A-tól Z-All jobb, gratulálok, megcsináltad. 78 00:04:09,900 --> 00:04:11,461 Megvan a választás. 79 00:04:11,461 --> 00:04:11,960 Kék? 80 00:04:11,960 --> 00:04:13,530 Rendben, köszönöm, hogy. 81 00:04:13,530 --> 00:04:16,679 Így Mary Beth nem javasol mi a megközelítés, 82 00:04:16,679 --> 00:04:19,720 de mi egy másik megközelítés, hogy hogyan Lehet, megy a válogatás ezeket a dolgokat? 83 00:04:19,720 --> 00:04:21,130 Mit tettél? 84 00:04:21,130 --> 00:04:24,060 A rekord, hogy megverte volna egy perc és 50 vagy még több másodpercre, 85 00:04:24,060 --> 00:04:26,039 plusz az is elfelejtettem számolni. 86 00:04:26,039 --> 00:04:27,080 Mit tettél? 87 00:04:27,080 --> 00:04:27,579 Igen? 88 00:04:27,579 --> 00:04:28,735 Közönség: Fogd a verem. 89 00:04:28,735 --> 00:04:29,776 Kezdje az elején. 90 00:04:29,776 --> 00:04:32,284 Ellenőrizze a papírokat. 91 00:04:32,284 --> 00:04:36,586 És ha az első egy nagyobb mint, talán, igen, 92 00:04:36,586 --> 00:04:38,980 az egyik az alsó magasabb, akkor váltani őket. 93 00:04:38,980 --> 00:04:41,300 >> Előadó: OK, így kezdődik a felső és az alsó, 94 00:04:41,300 --> 00:04:43,716 majd a munka az utat befelé, mint, hogy swapping őket? 95 00:04:43,716 --> 00:04:46,580 OK, így egy kicsit hasonló a szellem buborék sort, 96 00:04:46,580 --> 00:04:49,160 De a választás a szélsőségeket nem a szomszédos párok. 97 00:04:49,160 --> 00:04:52,080 De rövid az az, hogy van biztosan egy csomó különböző módon 98 00:04:52,080 --> 00:04:54,210 mi is ezt, és őszintén szólva, azt hiszem, ilyen 99 00:04:54,210 --> 00:04:55,700 elfogadott egy pár megközelítést, igaz? 100 00:04:55,700 --> 00:05:00,567 Ön tett valami négy rendezett aranyér, és akkor gyakorlatilag összeolvadt őket. 101 00:05:00,567 --> 00:05:02,650 És ez, mondhatnám, egy másik technika teljesen. 102 00:05:02,650 --> 00:05:06,950 Nem kezelik, mint egy nagy halom, Ön osztva a problémát négy quadok, 103 00:05:06,950 --> 00:05:09,820 ha úgy tetszik, és majd valahogy egyesült őket a végén. 104 00:05:09,820 --> 00:05:13,410 >> Tehát nézzük meg, végül, hogy mást is lehet csinálni ezt. 105 00:05:13,410 --> 00:05:15,860 Mi hivatalossá a fogalom buborék sort utoljára, 106 00:05:15,860 --> 00:05:18,780 és buborék sort visszahívás volt algoritmus, hogy láthatóvá 107 00:05:18,780 --> 00:05:22,640 nyolc az osztálytársaival fel itt, látszólag véletlenszerűen rendezett először. 108 00:05:22,640 --> 00:05:26,110 És akkor úgy döntött, páros, ha két elem elromlott, 109 00:05:26,110 --> 00:05:26,950 csak cserélni őket. 110 00:05:26,950 --> 00:05:28,930 Tehát négy és kettő nyilvánvalóan ki annak érdekében, 111 00:05:28,930 --> 00:05:31,080 így a két osztálytársak helyet cserélt. 112 00:05:31,080 --> 00:05:35,390 Aztán megismételtük négy és hat, majd hat és nyolc, minden ismétlés, 113 00:05:35,390 --> 00:05:36,980 mozog jobbra. 114 00:05:36,980 --> 00:05:42,590 >> Tehát adott nyolc ember, hány páronként összehasonlításokat tettem járás közben a 115 00:05:42,590 --> 00:05:45,220 balról jobbra az egyik iterációban ilyen? 116 00:05:45,220 --> 00:05:48,410 Hány összehasonlítás? 117 00:05:48,410 --> 00:05:49,197 Hét, nem? 118 00:05:49,197 --> 00:05:51,405 Mert ha van nyolc emberek, de van a pár 119 00:05:51,405 --> 00:05:53,880 őket, és folyamatosan mozgásban egyik hop jobbra, 120 00:05:53,880 --> 00:05:56,060 akkor nem lesz nyolc összehasonlítás, mert nem lehet összehasonlítani 121 00:05:56,060 --> 00:05:59,226 egy elem maga ellen, vagy akkor csak értelmetlen, így hét. 122 00:05:59,226 --> 00:06:01,290 Vagy még általánosabban, ha van n emberek, mi 123 00:06:01,290 --> 00:06:04,300 do n mínusz 1 összehasonlítást A buborék sort. 124 00:06:04,300 --> 00:06:08,150 >> Tehát nézzük meg most, hogy jó, vagy rossz buborék sort valójában volt, és próbálja meg 125 00:06:08,150 --> 00:06:13,570 hogy magunkat szókincset amely a kritika algoritmusok, mint ez, 126 00:06:13,570 --> 00:06:14,430 és hamarosan a saját. 127 00:06:14,430 --> 00:06:16,970 Tehát az első lépés a buborék sort, az első alkalommal 128 00:06:16,970 --> 00:06:20,909 Mentem balról jobbra haladva a szakasz, elvitt n mínusz 1 összehasonlítást. 129 00:06:20,909 --> 00:06:22,950 És ez lesz az én mértékegység, igaz? 130 00:06:22,950 --> 00:06:26,170 Én ilyen beszéd és sétáló, kissé gyors, kissé lassú, 131 00:06:26,170 --> 00:06:29,300 így számolás a másodpercek száma nem különösebben erős, 132 00:06:29,300 --> 00:06:32,260 de számolás száma műveletek én hétfőn, 133 00:06:32,260 --> 00:06:35,900 összehasonlítása a két ember, hogy úgy érzi, mint egy szép mértékegység. 134 00:06:35,900 --> 00:06:40,980 >> Tehát n mínusz 1 lépést az első alkalommal, de akkor mi történt? 135 00:06:40,980 --> 00:06:46,610 Mi az az egy fejjel az egy menetben keresztül egyébként rendezetlen listát? 136 00:06:46,610 --> 00:06:49,840 Mit tud mondani a elem aki egészen ott? 137 00:06:49,840 --> 00:06:51,300 Igen? 138 00:06:51,300 --> 00:06:52,870 Ez volt a legnagyobb elem, ugye? 139 00:06:52,870 --> 00:06:55,710 Nyolcas, annak ellenére, hogy itt kezdődött, minden alkalommal, amikor 140 00:06:55,710 --> 00:06:57,860 összehasonlítva a szemben a szomszéd, ő tartotta 141 00:06:57,860 --> 00:07:00,480 bugyogott fel a jobb oldali a listából. 142 00:07:00,480 --> 00:07:02,710 És valóban, ez az, ahol Az algoritmus kapta a nevét. 143 00:07:02,710 --> 00:07:07,630 >> Most az a logika, hogy hány összehasonlítást kell azt, hogy a második alkalommal 144 00:07:07,630 --> 00:07:09,800 Azt, hogy hogy át balról jobbra? 145 00:07:09,800 --> 00:07:10,730 n mínusz 2, ugye? 146 00:07:10,730 --> 00:07:14,297 Ez csak vesztegeti az időmet, ha folyamatosan összehasonlítva nyolc valaki ellen 147 00:07:14,297 --> 00:07:16,630 mást, mert mi már tudjuk, ő volt a megfelelő helyen. 148 00:07:16,630 --> 00:07:19,760 Szóval ez egy kicsit egy optimalizálás, így a következő lépés 149 00:07:19,760 --> 00:07:23,899 lesz, plusz n mínusz két lépést, ahol n az emberek száma. 150 00:07:23,899 --> 00:07:26,940 Most már ilyen extrapolálni, még ha nem egy számítógép tudós, 151 00:07:26,940 --> 00:07:27,680 hogy ez véget ér. 152 00:07:27,680 --> 00:07:31,259 Végén ezen algoritmus, feltehetően megvan csak egy összehasonlítás maradt. 153 00:07:31,259 --> 00:07:33,800 Meg kell, hogy milyen rögzítse a a lista elején ebben az esetben két 154 00:07:33,800 --> 00:07:36,540 és az egyik nincs rendben kell lennie, és az egy és két, 155 00:07:36,540 --> 00:07:40,330 így ez fenekek ki plusz 1 utolsó összehasonlítást. 156 00:07:40,330 --> 00:07:44,500 >> Most a pont, pont, pont olyan hullámokat ez kezét néhány juicier részletek 157 00:07:44,500 --> 00:07:46,452 De tételezzük fel, megy előre, és egyszerűbbé. 158 00:07:46,452 --> 00:07:48,660 Ha felidézzük a nagy iskola, őszintén szólva, sok van 159 00:07:48,660 --> 00:07:50,340 volt matematikai könyvek, hogy már egy kis puskát 160 00:07:50,340 --> 00:07:52,550 az előlapot, illetve a hátlap hogy mutattam 161 00:07:52,550 --> 00:07:56,400 milyen sorozat összegzések, mint a ez végül össze kell adni. 162 00:07:56,400 --> 00:07:59,600 Általános esetben, ha van egy változó, mint n, és valóban ez az egy, 163 00:07:59,600 --> 00:08:01,634 ha ránézett a old school matematika könyvet, 164 00:08:01,634 --> 00:08:04,050 akkor láthatjuk, hogy ez valójában tesz ki, ezt az összeget itt, 165 00:08:04,050 --> 00:08:07,970 n-szer n mínusz 1 egész osztva 2. 166 00:08:07,970 --> 00:08:11,172 Tehát most hadd kikötik ez igaz, így egy ugrás a hit, 167 00:08:11,172 --> 00:08:12,880 ez az, amit ez összegzi ig, és mi is 168 00:08:12,880 --> 00:08:14,341 azt bizonyítják, hogy egy általánosabb eset. 169 00:08:14,341 --> 00:08:15,590 De most nézzük bővíteni ezt ki. 170 00:08:15,590 --> 00:08:19,920 Szóval szaporodnak ezt ki, annak érdekében, hogy ez n négyzeten, mínusz n, mind osztva 2. 171 00:08:19,920 --> 00:08:23,200 Ez tényleg n faragva, osztva 2, mínusz n több mint 2, 172 00:08:23,200 --> 00:08:25,010 hogy minden szép és érdekes. 173 00:08:25,010 --> 00:08:27,060 De mi történik, ha Most plug-in egy értéket? 174 00:08:27,060 --> 00:08:29,724 Tegyük fel, hogy nem volt nyolc emberek, de mondjuk egy millió. 175 00:08:29,724 --> 00:08:31,890 És egy millió csak azért, mert ez egy nagyon nagy szám, 176 00:08:31,890 --> 00:08:34,039 hadd csatlakoztassa, hogy, és meglátjuk, mi történik. 177 00:08:34,039 --> 00:08:39,039 Tehát ha csatlakoztatok egy millió abba a formula Megyek, hogy egy millió kockás, 178 00:08:39,039 --> 00:08:42,868 osztva 2, mínusz a millió, osztva 2. 179 00:08:42,868 --> 00:08:44,159 Most mi lesz, hogy egyenlő? 180 00:08:44,159 --> 00:08:47,354 Tehát 500 milliárd, mínusz 500.000. 181 00:08:47,354 --> 00:08:49,270 És ha tényleg nem hogy a matematika ki, azt jelenti, 182 00:08:49,270 --> 00:08:53,920 hogy a válogatás a millió emberek a buborék sort 183 00:08:53,920 --> 00:09:01,800 Lehet, hogy nekem 499.999.500.000 lépések vagy összehasonlítások a végén, 184 00:09:01,800 --> 00:09:02,900 mi csak kivetítve. 185 00:09:02,900 --> 00:09:06,860 >> Hogy úgy érzi, elég lassú, de őszintén szólva mérése egy adott bemenet 186 00:09:06,860 --> 00:09:09,160 mint ez, nem olyan sokatmondó. 187 00:09:09,160 --> 00:09:14,050 De valójában ez nem azt sugallják, hogy az n egyre nagyobb és nagyobb, ez az algoritmus 188 00:09:14,050 --> 00:09:16,280 a fajta érzés rosszabb és rosszabb, vagy tényleg 189 00:09:16,280 --> 00:09:20,450 kezd érezni a fájdalmat, hogy a hatványozás, hogy n faragva, 190 00:09:20,450 --> 00:09:21,770 amely hozzáteszi fel elég gyorsan. 191 00:09:21,770 --> 00:09:25,340 És ez a részlet nem elveszett ember, sőt 192 00:09:25,340 --> 00:09:29,640 néhány évvel ezelőtt egy bizonyos szenátor, aki kampány, leült egy interjú 193 00:09:29,640 --> 00:09:32,180 a Google Eric Schmidt, vezérigazgató abban az időben, 194 00:09:32,180 --> 00:09:36,380 , és megtámadta a kérdés hasonlóan mi feltárása ma. 195 00:09:36,380 --> 00:09:38,468 Vessünk egy pillantást. 196 00:09:38,468 --> 00:09:45,280 >> [Videolejátszás] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Te itt a Google, és szeretem 198 00:09:48,560 --> 00:09:53,382 gondolni az elnökség mint egy állásinterjú. 199 00:09:53,382 --> 00:09:56,434 Nos, ez nehéz, hogy munkát, mint elnök, 200 00:09:56,434 --> 00:09:58,100 és megy keresztül a szigorú most. 201 00:09:58,100 --> 00:10:01,860 Ez is nehéz munkát találni a Google. 202 00:10:01,860 --> 00:10:05,490 Van kérdés, és mi Kérje jelöltek kérdéseket, 203 00:10:05,490 --> 00:10:09,770 és ez az egyik a Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Mi-- srácok hiszem, viccelek, ez itt van. 205 00:10:14,760 --> 00:10:17,930 Mi a leghatékonyabb módja annak, hogy rendezni egy millió 32 bites egész? 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 >> Ne haragudj, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nem, nem, nem. 210 00:10:27,400 --> 00:10:30,700 Azt hiszem, a buborék fajta lenne a rossz út. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Gyerünk, ki mondta ezt neki? 213 00:10:38,180 --> 00:10:40,590 Nem láttam a számítógép tudomány a háttérben. 214 00:10:40,590 --> 00:10:42,130 >> -Van A kémek is. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Kérdezzük más interjú kérdés. 217 00:10:48,444 --> 00:10:49,300 >> [END Videolejátszás] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Tehát beszél konkrét számokat azonban, 219 00:10:52,290 --> 00:10:53,890 Nem lesz minden, hogy hasznos. 220 00:10:53,890 --> 00:10:56,810 Ez nem egy élet leckét, hogy buborék sort, mivel a millió bemenet, 221 00:10:56,810 --> 00:10:58,590 Lehet, hogy több mint 500 milliárd lépéseket. 222 00:10:58,590 --> 00:11:01,120 Nem igazán lehet általánosítani is hatékonyan az 223 00:11:01,120 --> 00:11:03,560 és a jó tervezési döntések írásakor programok. 224 00:11:03,560 --> 00:11:07,070 Szóval összpontosít mégis hogyan talán egyszerűsíteni ezt az eredményt. 225 00:11:07,070 --> 00:11:11,780 >> Szóval sárga színnel van az eredmény N négyzethálós osztva 2, 226 00:11:11,780 --> 00:11:14,330 így egy millió kockás osztva a 2, majd 227 00:11:14,330 --> 00:11:16,710 Már kiemelt milyen A végső válasz 228 00:11:16,710 --> 00:11:20,180 ha egyszer le kell vonni le n osztva 2. 229 00:11:20,180 --> 00:11:24,850 És a követelés fogok tenni most, Ki a fene törődik, ha kivonni ki 230 00:11:24,850 --> 00:11:30,060 egy kis régi n több mint 2, amikor az első része ez a képlet sokkal nagyobb? 231 00:11:30,060 --> 00:11:33,910 Uralja a többi kifejezés, n négyzethálós osztva 2 232 00:11:33,910 --> 00:11:37,510 annyival nagyobb, tisztán, mint n egyre nagyobb lesz, mint egy millió, 233 00:11:37,510 --> 00:11:41,450 ez valóban egy nagy különbség a végén a nap között 500 milliárd 234 00:11:41,450 --> 00:11:45,730 és 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Nem igazán. 236 00:11:46,349 --> 00:11:48,640 És mit fogunk tegye a számítógép tudósok 237 00:11:48,640 --> 00:11:53,270 figyelmen kívül hagyja ezeket az alacsonyabb rendű tagokat és hogy valami ilyesmi, és tényleg 238 00:11:53,270 --> 00:11:56,050 csak egyszerűsíti azt a kifejezés ez fog számítani. 239 00:11:56,050 --> 00:12:00,315 A nagyobb az adathalmazok kap, a nagyobb adatbázisaink kap, a több weboldalak 240 00:12:00,315 --> 00:12:02,690 meg kell keresni, a több ember van a Facebookon. 241 00:12:02,690 --> 00:12:07,340 >> Az n lesz nagyobb, vagyunk igazán fog törődni a legnagyobb 242 00:12:07,340 --> 00:12:11,560 kifejezés bármely ilyen elemzés az algoritmusok teljesítmény. 243 00:12:11,560 --> 00:12:16,230 És azt fogom mondani, tudod mit, buborék rendezés a sorrendben nagy O, 244 00:12:16,230 --> 00:12:18,060 A rendelés n négyzeten. 245 00:12:18,060 --> 00:12:20,090 Ez nem pontosan n kockás mint láttuk, 246 00:12:20,090 --> 00:12:22,060 de aki igazán érdekel azokról a kisebb szempontból 247 00:12:22,060 --> 00:12:24,390 és őszintén szólva, aki igazán érdekel, ha elosztjuk 2? 248 00:12:24,390 --> 00:12:25,870 Ez csak egy állandó tényező. 249 00:12:25,870 --> 00:12:29,480 És 500 milliárd versus 250 milliárd tényleg olyan nagy dolog? 250 00:12:29,480 --> 00:12:32,190 Én is csak várni egy évet, hagyja a laptop a szó szoros értelmében 251 00:12:32,190 --> 00:12:34,810 kétszer olyan gyorsan kap a hardver, és az a fajta különbség 252 00:12:34,810 --> 00:12:36,650 csak elmegy természetesen az idő múlásával. 253 00:12:36,650 --> 00:12:39,300 >> Mi törődünk az a kifejezés a része, 254 00:12:39,300 --> 00:12:42,489 A kifejezés, hogy fog változtatni mint a bemenő egyre nagyobb és nagyobb. 255 00:12:42,489 --> 00:12:45,280 És valóban, a valós világban, ez az, ami történik inkább 256 00:12:45,280 --> 00:12:48,330 a bemenetek a problémák és algoritmusok egyre nagyobb. 257 00:12:48,330 --> 00:12:53,470 Tehát nagy O lesz a jelölés, az aszimptotikus jelölés, hogy mi csak 258 00:12:53,470 --> 00:12:57,160 használja a számítógép-tudósok leírni a teljesítmény, illetve a működési idő, 259 00:12:57,160 --> 00:12:58,130 egy algoritmus. 260 00:12:58,130 --> 00:13:00,800 Ahhoz, hogy össze tudjuk hasonlítani algoritmusokat különböző számítógépeken írott 261 00:13:00,800 --> 00:13:04,170 különböző emberek, segítségével néhány alapvetően hasonló metrikus 262 00:13:04,170 --> 00:13:07,557 mint az összehasonlítások száma te így, vagy esetleg a számát swapok 263 00:13:07,557 --> 00:13:08,140 írsz. 264 00:13:08,140 --> 00:13:11,910 >> Amit nem fog száma az időt 265 00:13:11,910 --> 00:13:13,981 hogy átadja az óra jellemzően a falon. 266 00:13:13,981 --> 00:13:16,230 Amit nem fog aggódni arról van szó, hogy mennyi memória 267 00:13:16,230 --> 00:13:17,820 Ön használ ma legalábbis, bár ez 268 00:13:17,820 --> 00:13:19,370 Egy másik forrás talán mérni. 269 00:13:19,370 --> 00:13:23,610 Fogunk próbálja alapozni elemzések az csak az alapvető műveleteket, azok, 270 00:13:23,610 --> 00:13:25,930 őszintén, hogy lehet látni a legtöbb vizuálisan. 271 00:13:25,930 --> 00:13:30,700 Tehát valami, mint a nagy O n faragva, azt állítom, hogy O-n négyzetes 272 00:13:30,700 --> 00:13:35,820 egy felső korlát az úgynevezett menetideje buborék sort. 273 00:13:35,820 --> 00:13:38,820 Más szóval, ha akarta állítani, hogy van 274 00:13:38,820 --> 00:13:41,370 Ez a felső határ, hogy hány lépéseket egy algoritmus eltarthat, 275 00:13:41,370 --> 00:13:46,240 ez lesz a nagy O n kockás ebben az esetben, egy felső korlát. 276 00:13:46,240 --> 00:13:49,710 >> Mi van, ha én inkább változtatni a történet, hogy nem a buborék sort, 277 00:13:49,710 --> 00:13:50,910 de erről a felső korlátot. 278 00:13:50,910 --> 00:13:54,030 Nem gondolod, hogy egy algoritmus hogy megnéztük már 279 00:13:54,030 --> 00:13:59,530 amelynek a felső határ, maximum intézkedés az idő vagy a műveletek 280 00:13:59,530 --> 00:14:04,300 azt lehet mondani, hogy korlátos n, egy lineáris függvény, 281 00:14:04,300 --> 00:14:07,260 nem egy másodfokú az egyik, hogy görbe? 282 00:14:07,260 --> 00:14:10,780 Mi az az algoritmus, amely mindig nem több 283 00:14:10,780 --> 00:14:12,860 mint például N lépésben, vagy 2n lépést, vagy 3n lépések? 284 00:14:12,860 --> 00:14:13,360 Igen? 285 00:14:13,360 --> 00:14:15,030 >> Közönség: Megtalálni a legnagyobb szám a listán? 286 00:14:15,030 --> 00:14:16,930 >> Előadó: Tökéletes, találni a legnagyobb szám a listán. 287 00:14:16,930 --> 00:14:18,940 Ha én egy listát, emberek például, 288 00:14:18,940 --> 00:14:21,440 mindegyik, aki a kezében egy számot, mi az a maximális száma 289 00:14:21,440 --> 00:14:23,770 lépést meg kell tennie nekem, meglehetősen okos ember, 290 00:14:23,770 --> 00:14:27,530 hogy megtalálják a legnagyobb ember a listán? 291 00:14:27,530 --> 00:14:28,100 n, igaz? 292 00:14:28,100 --> 00:14:31,320 Mivel a legrosszabb esetben, amikor talán a legnagyobb érték legyen? 293 00:14:31,320 --> 00:14:32,700 Jobb, egészen a végén. 294 00:14:32,700 --> 00:14:34,575 Tehát a legrosszabb esetben felső kötött, talán 295 00:14:34,575 --> 00:14:36,450 kell menni egészen ide, és mint a 296 00:14:36,450 --> 00:14:39,170 Ó, itt van a nyolcas számú, vagy bármi ez az érték. 297 00:14:39,170 --> 00:14:41,330 Most ez csak hülye ha folyamatosan megy, ugye? 298 00:14:41,330 --> 00:14:43,840 Keresi a több és több elemet ha az utolsó közülük ott? 299 00:14:43,840 --> 00:14:45,340 Szóval biztosan, n egy felső korlát. 300 00:14:45,340 --> 00:14:47,420 Nem kell, hogy több lépést, mint a. 301 00:14:47,420 --> 00:14:51,580 >> Mi van, ha ehelyett azt javasolta, hogy vannak algoritmusok ebben a világban, hogy 302 00:14:51,580 --> 00:14:57,750 Van egy futó idő, ami által határolt nagy O log n log n? 303 00:14:57,750 --> 00:15:00,390 Hol láttuk ezt korábban? 304 00:15:00,390 --> 00:15:00,890 Igen? 305 00:15:00,890 --> 00:15:03,309 >> Közönség: a telefonkönyvben probléma? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Mint a telefonkönyv probléma. 307 00:15:04,850 --> 00:15:07,754 Mi volt az intézkedés, hogy milyen sok időt vagy hány könny az 308 00:15:07,754 --> 00:15:10,170 elvitt találni valakit, mint a Mike Smith a telefonkönyvben? 309 00:15:10,170 --> 00:15:13,212 Azt állította, hogy log n, és akkor is, ha ismeretlen, vagy azt, hogy ez 310 00:15:13,212 --> 00:15:15,170 egy kicsit homályos, amit egy logaritmus vagy kitevő volt, 311 00:15:15,170 --> 00:15:17,650 Csak arra emlékszem, hogy a log n általában arra a folyamatra utal, 312 00:15:17,650 --> 00:15:20,790 Ebben az esetben, az osztódó valami félbe újra, és újra, 313 00:15:20,790 --> 00:15:25,790 és újra, és újra, úgy, hogy lesz egyre kisebb, ahogy csinálni. 314 00:15:25,790 --> 00:15:28,470 >> Tehát log n utal, biztos, A telefonkönyv példa, 315 00:15:28,470 --> 00:15:32,662 bináris keresés elméletben, amikor volt a virtuális kapuit a táblán, 316 00:15:32,662 --> 00:15:34,370 vagy amikor Sean volt keres valamit. 317 00:15:34,370 --> 00:15:37,374 Ha ő használt bináris keresés, log n lenne a felső határ, hogy mennyi 318 00:15:37,374 --> 00:15:38,040 alkalom, hogy vesz. 319 00:15:38,040 --> 00:15:44,027 De azok algoritmusok futott log n feltételezett milyen kulcsfontosságú részlet? 320 00:15:44,027 --> 00:15:45,360 Hogy a lista sorrendje, igaz? 321 00:15:45,360 --> 00:15:47,789 Ön algoritmus baj, ha a bemenet nincs rendezve, 322 00:15:47,789 --> 00:15:49,830 és mégis használ olyasmi, mint a bináris keresés 323 00:15:49,830 --> 00:15:51,704 mert lehet, hogy ugrik jobb az elem 324 00:15:51,704 --> 00:15:53,600 anélkül, hogy észrevennénk, hogy ez valóban ott van. 325 00:15:53,600 --> 00:15:55,600 >> Most, hogy mi ez, a nagy O egy? 326 00:15:55,600 --> 00:15:59,117 Ez nem azt jelenti, hogy az algoritmus vesz egy és csak egy lépés, 327 00:15:59,117 --> 00:16:01,200 ez csak azt jelenti, hogy vesz egy állandó számát. 328 00:16:01,200 --> 00:16:04,060 Lehet, hogy 1, lehet, hogy 10, lehet, hogy 1000, 329 00:16:04,060 --> 00:16:07,750 de ez független a méret a problémát. 330 00:16:07,750 --> 00:16:10,850 Nem számít, milyen nagy n, állandó idő algoritmus 331 00:16:10,850 --> 00:16:12,747 mindig úgy azonos lépések számát. 332 00:16:12,747 --> 00:16:15,080 Szóval, mi lehet egy algoritmus beszéltünk, vagy csak 333 00:16:15,080 --> 00:16:20,418 ösztönösen, hogy jön, hogy mindig fut az úgynevezett konstans idő? 334 00:16:20,418 --> 00:16:20,918 Igen? 335 00:16:20,918 --> 00:16:22,001 >> Közönség: Add két szám. 336 00:16:22,001 --> 00:16:25,320 Előadó: Add két szám, 2 plusz 2 egyenlő 4, kész. 337 00:16:25,320 --> 00:16:27,227 Annak érdekében, hogy működhet, mi más? 338 00:16:27,227 --> 00:16:28,560 Mi lenne, még a valós világban, ugye? 339 00:16:28,560 --> 00:16:30,686 >> Közönség: Megtalálni a első dolog, amit egy listában. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Megtalálni az első elem a listán, biztos. 341 00:16:32,810 --> 00:16:34,540 Már valóban beszélt a tömbök már, 342 00:16:34,540 --> 00:16:36,540 hogyan kap a első eleme egy tömb, 343 00:16:36,540 --> 00:16:40,465 nem számít, milyen hosszú a tömb a C kód? 344 00:16:40,465 --> 00:16:43,090 Csak használja, mint a konzol nulla jelölés, bumm, ott vagy. 345 00:16:43,090 --> 00:16:46,120 És valóban tömbök, mint egy félre, támogatás valami általánosan ismert 346 00:16:46,120 --> 00:16:49,240 A véletlen hozzáférés, véletlen elérésű memória, mert akkor szó szerint 347 00:16:49,240 --> 00:16:50,284 ugrás minden egy helyen. 348 00:16:50,284 --> 00:16:52,700 Meg tudjuk csinálni ezt még egyszerűbben akkor hátra hétig nulla 349 00:16:52,700 --> 00:16:53,900 amikor nem Scratch. 350 00:16:53,900 --> 00:16:59,707 Mennyi idő telt el a mondjuk blokk Scratch végrehajtani? 351 00:16:59,707 --> 00:17:00,790 Csak állandó, igaz? 352 00:17:00,790 --> 00:17:03,960 Mondj valamit, mondjuk valamit, akkor nem számít 353 00:17:03,960 --> 00:17:07,359 milyen nagy karcolások világ, ez mindig megy, hogy ugyanannyi idő alatt 354 00:17:07,359 --> 00:17:08,490 hogy egyszerűen mondani valamit. 355 00:17:08,490 --> 00:17:11,089 >> Szóval ez az állandó idő, de mi van a másik oldala? 356 00:17:11,089 --> 00:17:13,030 Ha ez volt a felső határokat, mi van, ha azt akarjuk, 357 00:17:13,030 --> 00:17:17,089 leírni az alsó határt mi algoritmusok futási idő? 358 00:17:17,089 --> 00:17:19,852 Majdnem egy legjobb esetben esetleg, ha úgy tetszik, 359 00:17:19,852 --> 00:17:23,060 bár ezek a feltételek nem alkalmazhatók a legjobban esetek, legrosszabb esetben az átlagos esetek több 360 00:17:23,060 --> 00:17:26,359 általában, de most csak a hangsúly az alsó határ általában. 361 00:17:26,359 --> 00:17:31,920 Mi az az algoritmus, amely alsó határát n lépések 362 00:17:31,920 --> 00:17:33,350 vagy 2n lépést, vagy 3n lépések? 363 00:17:33,350 --> 00:17:36,241 Néhány tényező n lépések, ez az alsó határ. 364 00:17:36,241 --> 00:17:36,740 Igen? 365 00:17:36,740 --> 00:17:37,910 >> Közönség: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> Előadó: Bubble sort tart Ön minimálisan n lépések, miért? 367 00:17:41,610 --> 00:17:42,279 Miért van ez? 368 00:17:42,279 --> 00:17:45,320 Miért kell, hogy a kezdetektől a hozzád ösztönösen, akkor is, ha ez nem csak 369 00:17:45,320 --> 00:17:46,530 még? 370 00:17:46,530 --> 00:17:47,030 Igen? 371 00:17:47,030 --> 00:17:47,990 >> KÖZÖNSÉG: [nem hallható]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 Előadó: Pontosan. 374 00:17:52,360 --> 00:17:55,810 A lehető legjobb forgatókönyv szerint buborék sort, és sok algoritmusok 375 00:17:55,810 --> 00:17:58,769 ha átadom neked nyolc embert akik már válogatni, 376 00:17:58,769 --> 00:18:00,560 butaság lenne az Ön számára, az algoritmus, 377 00:18:00,560 --> 00:18:02,202 hogy menjen oda-vissza többször, nem igaz? 378 00:18:02,202 --> 00:18:04,285 Mert amint séta a listában egyszer, 379 00:18:04,285 --> 00:18:08,090 fel kell ismerniük, ó, nem tett swap, ez lista, kilép. 380 00:18:08,090 --> 00:18:09,700 De ez fog tartani N lépésben. 381 00:18:09,700 --> 00:18:12,033 >> És fordítva, mi egy másik gondolkodásmód ez? 382 00:18:12,033 --> 00:18:15,240 Bubble sort egy omega, hogy úgy mondjam, n, 383 00:18:15,240 --> 00:18:19,050 mert ha megnézi kevesebb, mint n elem, amit 384 00:18:19,050 --> 00:18:23,009 az alapvető probléma ott? 385 00:18:23,009 --> 00:18:24,550 Nem tudom, ha ez válogatni, igaz. 386 00:18:24,550 --> 00:18:26,800 Mi, emberek talán pillantást nyolc emberek, és mint, ó, ez válogatni, 387 00:18:26,800 --> 00:18:28,430 hogy nem engem n lépést, de ez nem. 388 00:18:28,430 --> 00:18:30,810 A szemed, még akkor is, kedves Az egy nagy látómező, 389 00:18:30,810 --> 00:18:33,184 Megnézted nyolc elem, Megnézted nyolc ember, 390 00:18:33,184 --> 00:18:34,610 Ez nyolc lépésben hatékonyan. 391 00:18:34,610 --> 00:18:38,612 És csak akkor, ha sétálok az egész lista nem látom, igen, válogatni. 392 00:18:38,612 --> 00:18:41,320 Ha megáll félúton gondoltam, minden jobb, ez elég válogatott eddig, 393 00:18:41,320 --> 00:18:42,520 mi az esélye, hogy nem válogatott? 394 00:18:42,520 --> 00:18:44,186 Hogy algoritmusok nem lesz helyes. 395 00:18:44,186 --> 00:18:46,250 Lehet, hogy gyorsabb, de helytelen. 396 00:18:46,250 --> 00:18:48,500 >> Tehát most van egy módja leíró alacsonyabb határt, 397 00:18:48,500 --> 00:18:49,710 És mi a helyzet változatlan idő? 398 00:18:49,710 --> 00:18:54,565 Mi az az algoritmus, amely alacsonyabb kötött annak futási ideje egy? 399 00:18:54,565 --> 00:18:58,350 1. lépés, 2 lépés, 10 lépés, de állandó, független n, 400 00:18:58,350 --> 00:18:59,310 a méret a bemeneti? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Igen, vissza. 403 00:19:04,600 --> 00:19:05,309 >> Közönség: printf? 404 00:19:05,309 --> 00:19:06,183 Előadó: Mi ez? 405 00:19:06,183 --> 00:19:07,184 Közönség: printf? 406 00:19:07,184 --> 00:19:07,850 Előadó: printf. 407 00:19:07,850 --> 00:19:08,400 OK, biztos. 408 00:19:08,400 --> 00:19:10,720 Tehát vesz egy fix számát. 409 00:19:10,720 --> 00:19:13,170 És én now-- most, hogy beszélünk C kód 410 00:19:13,170 --> 00:19:16,040 és nem karcolja, valami mint mondják, a printf, 411 00:19:16,040 --> 00:19:17,710 meg kell kezdeni, hogy óvatos. 412 00:19:17,710 --> 00:19:21,090 Mivel a printf nem veszi bemenet, ez egy string, 413 00:19:21,090 --> 00:19:23,220 és vonósok még technikailag is hosszú. 414 00:19:23,220 --> 00:19:25,530 Tehát, ha most szeretnénk felvenni rád, ha nem bánod, 415 00:19:25,530 --> 00:19:29,430 technikailag mi lehetne vitatkozni, hogy printf nem fog egy változó hosszúságú bemenet, 416 00:19:29,430 --> 00:19:32,270 és biztosan lehet, hogy több ideje, hogy nyomtassa ki a húr ezt a hosszú, 417 00:19:32,270 --> 00:19:33,560 mint ilyen sokáig. 418 00:19:33,560 --> 00:19:36,570 >> Mi van, ha figyelembe vesszük, csak a válogatás és keres példát? 419 00:19:36,570 --> 00:19:40,450 Mi a Mike Smith, a telefon könyv, vagy bináris keresés általában? 420 00:19:40,450 --> 00:19:42,220 A legjobb esetben, hogy mi fog történni? 421 00:19:42,220 --> 00:19:45,577 Kinyitom a telefonkönyvben, és bumm, ott van Mike Smith számát. 422 00:19:45,577 --> 00:19:46,660 Én hívom azonnal. 423 00:19:46,660 --> 00:19:49,390 >> Tett egy lépést, talán két lépést, de állandó lépések száma 424 00:19:49,390 --> 00:19:50,230 ha szerencsém volt. 425 00:19:50,230 --> 00:19:52,570 És őszintén szólva, láttuk a Hétfő az osztálytársa 426 00:19:52,570 --> 00:19:54,710 kap elég szerencsés kétszer egymás után. 427 00:19:54,710 --> 00:19:57,050 És ez valóban állandó időt egy alsó korlát 428 00:19:57,050 --> 00:20:01,280 az algoritmus a szóban forgó megállapítás a szám 50 mögött zárt 429 00:20:01,280 --> 00:20:01,830 ajtókat. 430 00:20:01,830 --> 00:20:06,400 >> Most, mint egy félre, ha rájössz hogy mind a nagy O, a felső határ, 431 00:20:06,400 --> 00:20:09,310 és omega, az alsó határ, egyek ugyanaz, hogy 432 00:20:09,310 --> 00:20:11,830 azonos képlet zárójel, akkor is 433 00:20:11,830 --> 00:20:15,170 azt mondják, csak a képzelet, hogy valami van a theta 434 00:20:15,170 --> 00:20:18,270 n vagy theta valamilyen más értéket. 435 00:20:18,270 --> 00:20:20,661 Ez csak azt jelenti, amikor a nagy O és omega azonos. 436 00:20:20,661 --> 00:20:21,910 Most mi a kiválasztás sort? 437 00:20:21,910 --> 00:20:23,400 Használjuk ezt az új szókincs. 438 00:20:23,400 --> 00:20:27,407 A kiválasztás sort, mi voltunk csinál újra, és újra, és újra? 439 00:20:27,407 --> 00:20:29,990 Úgy volt, oda-vissza a listán, akik a kinek? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 A legkisebb szám. 442 00:20:34,730 --> 00:20:37,560 >> Szóval, hány lépés, hogyan sok összehasonlítást tettem 443 00:20:37,560 --> 00:20:43,250 kell tenni annak érdekében, hogy kitaláljuk, ki a legkisebb elem a listán volt? 444 00:20:43,250 --> 00:20:44,437 n mínusz 1, igaz? 445 00:20:44,437 --> 00:20:47,770 Mert ha csak kezdeni az egyik én vagyok adott és elkezdek összehasonlítása neki, 446 00:20:47,770 --> 00:20:49,519 majd neki, őt vagy őt, őt, én 447 00:20:49,519 --> 00:20:52,010 csak párosítani elemek együtt n mínusz 1 alkalommal. 448 00:20:52,010 --> 00:20:55,630 Tehát kiválasztás sort hasonlóan úgy n mínusz 1 lépést az első alkalommal. 449 00:20:55,630 --> 00:20:59,540 >> Hány lépést tart engem meg a második legkisebb elem? 450 00:20:59,540 --> 00:21:02,920 n mínusz 2, mert én vagyok, hogy hülye Ha tovább néztem ugyanazok az emberek 451 00:21:02,920 --> 00:21:06,280 újra, ha már választott neki vagy neki, és tedd a helyükre. 452 00:21:06,280 --> 00:21:09,270 És a harmadik lépés, n mínusz 3, akkor n mínusz 4. 453 00:21:09,270 --> 00:21:11,020 Láttuk ezt a mintát előtt, és valóban 454 00:21:11,020 --> 00:21:13,460 kiválasztás sort hasonlóan van egy felső korlát 455 00:21:13,460 --> 00:21:16,210 n négyzetes ha ezt tesszük fel, hogy az összegzés. 456 00:21:16,210 --> 00:21:19,790 Mi az alsó határ, a kiválasztás sort? 457 00:21:19,790 --> 00:21:25,350 Minimálisan, mennyi idő kiválasztás sort, hogy, amint azt határozta meg hétfőn? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Javaslatot tesz két lehetőség. 460 00:21:30,490 --> 00:21:32,360 Lehet, hogy n, mint korábban. 461 00:21:32,360 --> 00:21:35,040 Lehet, hogy az n faragva, hiszen most mivel a felső határ. 462 00:21:35,040 --> 00:21:35,874 >> Közönség: n négyzeten. 463 00:21:35,874 --> 00:21:36,664 SPEAKER n négyzeten. 464 00:21:36,664 --> 00:21:37,368 Miért? 465 00:21:37,368 --> 00:21:40,060 >> Közönség: Mert van határozza meg [nem hallható]. 466 00:21:40,060 --> 00:21:41,510 >> Előadó: Pontosan. 467 00:21:41,510 --> 00:21:45,077 Legalábbis ahogy én meghatározott kiválasztás sort volt elég naiv, folytasd, 468 00:21:45,077 --> 00:21:46,160 megtalálja a legkisebb elem. 469 00:21:46,160 --> 00:21:47,770 Megint, meg a legkisebb elem. 470 00:21:47,770 --> 00:21:49,490 Megint, meg a legkisebb elem. 471 00:21:49,490 --> 00:21:51,700 Nincs valami optimalizálás ott 472 00:21:51,700 --> 00:21:54,350 Lehet, hadd szakítsa után csak n vagy olyan lépéseket. 473 00:21:54,350 --> 00:21:57,080 Tehát valóban, a kiválasztás sort, omega n négyzeten. 474 00:21:57,080 --> 00:22:00,667 >> Mi a beillesztés sort, ahol vettem aki kaptam, aztán lehuppant rá 475 00:22:00,667 --> 00:22:01,750 töltse le a megfelelő helyen? 476 00:22:01,750 --> 00:22:04,958 Aztán folytatta, hogy a másik személy, lehuppant rá a megfelelő helyen. 477 00:22:04,958 --> 00:22:07,910 Aztán a következő személy, lehuppant őt a megfelelő helyen. 478 00:22:07,910 --> 00:22:10,537 Vegyük észre, hogy ez nagyon lineáris, hogy úgy mondjam. 479 00:22:10,537 --> 00:22:12,620 Én egy egyenes vonal, én vagyok nem megy oda-vissza, 480 00:22:12,620 --> 00:22:16,080 Még soha nem nézett vissza igazán, de mi történik, amikor beszúrni neki 481 00:22:16,080 --> 00:22:20,302 vagy őt elejére A lista, mint mi hétfőn? 482 00:22:20,302 --> 00:22:21,010 Mi történik? 483 00:22:21,010 --> 00:22:21,510 Igen? 484 00:22:21,510 --> 00:22:23,122 KÖZÖNSÉG: [nem hallható]. 485 00:22:23,122 --> 00:22:24,830 Előadó: Igen, volt a fogás, igaz? 486 00:22:24,830 --> 00:22:26,746 Lehet, hogy visszahívja a az osztálytársaival, ha 487 00:22:26,746 --> 00:22:29,670 arra, hogy bármilyen mozgás lábuk, ez a művelet. 488 00:22:29,670 --> 00:22:33,610 Tehát, ha három ember itt Az új személy tartozott út oda, 489 00:22:33,610 --> 00:22:37,360 egy hosszú szakasz, mint ez, biztos, hogy vagy ő is csak megy a legvégén. 490 00:22:37,360 --> 00:22:40,074 De ha nem gondolkodik a és egy sor számítógépes memória, 491 00:22:40,074 --> 00:22:41,990 ezek az emberek mennek hogy a shuffle át 492 00:22:41,990 --> 00:22:43,260 hogy helyet csináljon az ember. 493 00:22:43,260 --> 00:22:46,930 És így, hogy n mínusz 1 shufflings, n mínusz 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 mínusz 3 shufflings csak egyfajta történik a hátam mögött, nem előttem 495 00:22:50,660 --> 00:22:52,710 mint korábban, bizonyos értelemben. 499 00:22:52,557 --> 00:22:54,640 Most, mint egy félre, és mint lehet, hogy látható az interneten 500 00:22:54,640 --> 00:22:57,699 ha elkezd dugta körül a fajta, van olyan sok más is 501 00:22:57,699 --> 00:22:59,490 ott, néhány közülük jobb, mint mások. 502 00:22:59,490 --> 00:23:02,200 Valóban, bogosort egy ez a fajta szórakozás, hogy néz ki. 503 00:23:02,200 --> 00:23:06,650 Bogosort vesz egy sor számokat, vagy mondjuk egy pakli kártya, 504 00:23:06,650 --> 00:23:09,870 véletlenszerűen összekeveri őket, és ellenőrzi, hogy ők rendezve. 505 00:23:09,870 --> 00:23:12,130 És ha nem, nem tesz ilyet. 506 00:23:12,130 --> 00:23:14,140 És ha nem, nem tesz ilyet. 507 00:23:14,140 --> 00:23:15,440 Ha nem, akkor újra. 508 00:23:15,440 --> 00:23:17,060 Hihetetlenül ostoba. 509 00:23:17,060 --> 00:23:19,520 >> És valóban, ha olvas mint a Wikipedia cikket, 510 00:23:19,520 --> 00:23:21,200 a beceneve hülye sort. 511 00:23:21,200 --> 00:23:25,180 Ez végül a munka, remélhetőleg, elegendő idő, 512 00:23:25,180 --> 00:23:28,240 de, hogy mennyi időt is eltarthat egy ideig. 513 00:23:28,240 --> 00:23:31,650 Tehát, ha én is, hadd sebesség dolgok fel Mary Beth példa korábban, 514 00:23:31,650 --> 00:23:35,150 azáltal, hogy még néhány elemet, de két processzort. 515 00:23:35,150 --> 00:23:37,100 Két ember, ha nem bánnám csatlakozik hozzám. 516 00:23:37,100 --> 00:23:40,972 Mit szólnál 1 ide, és nézzük van-- nincs ott? 517 00:23:40,972 --> 00:23:41,722 Nincs ott? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Te a fekete ing, igen, gyere le. 520 00:23:44,190 --> 00:23:45,000 Rendben, mi a neve? 521 00:23:45,000 --> 00:23:45,720 >> Közönség: Peter. 522 00:23:45,720 --> 00:23:46,100 >> Előadó: Mi ez? 523 00:23:46,100 --> 00:23:46,766 >> Közönség: Peter. 524 00:23:46,766 --> 00:23:49,450 Előadó: Peter, David, örülök, hogy találkoztunk. 525 00:23:49,450 --> 00:23:53,670 Rendben, van Peter itt, ha akar jönni az asztalra itt. 526 00:23:53,670 --> 00:23:54,550 És mi a neved? 527 00:23:54,550 --> 00:23:55,216 >> Közönség: Elena. 528 00:23:55,216 --> 00:23:55,970 Előadó: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, örülök, hogy találkoztunk. 530 00:23:57,030 --> 00:23:58,060 Elena megfelelnek Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 És szükségünk lesz Andrew itt is, kérem. 533 00:24:02,290 --> 00:24:06,107 És a kihívás lesz hogy rendezni egy pakli kártya. 534 00:24:06,107 --> 00:24:08,190 És ha ismeretlen, fedélzet kártyák végső soron 535 00:24:08,190 --> 00:24:11,064 lehet válogatni egy kis valami hasonló ez, ahol mi nem a klub, akkor 536 00:24:11,064 --> 00:24:13,660 a pikk, majd a szív-és gyémánt, az ász, mint az egyik, 537 00:24:13,660 --> 00:24:15,570 egészen a király. 538 00:24:15,570 --> 00:24:20,890 >> A kártyák fogok adni lesznek 52 mennyiségben. 539 00:24:20,890 --> 00:24:23,160 Megyünk hasonlóan alkalommal, csak egy pillanat. 540 00:24:23,160 --> 00:24:26,410 Fogunk dobni Andrew a képernyőn itt, 541 00:24:26,410 --> 00:24:28,170 így nézni, mint te ezt. 542 00:24:28,170 --> 00:24:31,070 És így, hogy mindez annál is inkább látható, 543 00:24:31,070 --> 00:24:33,490 Ezek a kártyák kaptam az Amazon. 544 00:24:33,490 --> 00:24:42,861 Így már véletlenszerűen válogatni, és fogunk időt. 545 00:24:42,861 --> 00:24:44,610 És fogunk tartsa valós ebben az időben, 546 00:24:44,610 --> 00:24:47,820 így fogunk próbálni, hogy nyomást Ön mert különben ez lesz unalmas 547 00:24:47,820 --> 00:24:48,460 gyorsan. 548 00:24:48,460 --> 00:24:53,860 Ha lehetne folytatni rendezni 52 elemek együtt keresztül valamilyen módon, most. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> És ismét, ahogy nézni ezeket a fiúk, amit, a végén 551 00:25:07,180 --> 00:25:10,200 lesz, hogy készítsen egy nyilvánvaló eredmény, gondoljon tényleg 552 00:25:10,200 --> 00:25:12,962 hogyan ők minden csinálja, hogyan lehet leírni. 553 00:25:12,962 --> 00:25:15,045 Mivel ismét, ezek minden folyamat, algoritmusok 554 00:25:15,045 --> 00:25:17,090 hogy magától értetődőnek, mint egy ember. 555 00:25:17,090 --> 00:25:22,349 De akkor már valószínűleg régóta intuíció, hosszú, mielőtt még 556 00:25:22,349 --> 00:25:24,390 gondoltam, hogy egy számítástechnika osztály van 557 00:25:24,390 --> 00:25:27,223 lehetett volna az intuíció és ami a problémák megoldásában, mint ez. 558 00:25:27,223 --> 00:25:29,560 De ha egyszer elismerik A minták és kezdődik 559 00:25:29,560 --> 00:25:32,407 hogy hivatalossá a lépéseket, amelyek te megoldani ezeket a problémákat, 560 00:25:32,407 --> 00:25:35,490 rájössz, hogy meg lehet oldani sok érdekesebb és sokkal bonyolultabb 561 00:25:35,490 --> 00:25:39,190 problémák gyors. 562 00:25:39,190 --> 00:25:42,351 Tehát valaki a közönség, ami legalább az egyik eleme az algoritmus 563 00:25:42,351 --> 00:25:43,350 hogy ők a itt? 564 00:25:43,350 --> 00:25:44,275 >> KÖZÖNSÉG: [nem hallható] 565 00:25:44,275 --> 00:25:45,150 Előadó: Mi ez? 566 00:25:45,150 --> 00:25:47,062 Közönség: Az öltöny. 567 00:25:47,062 --> 00:25:47,770 Előadó: Az öltöny. 568 00:25:47,770 --> 00:25:50,630 Így először ezeket csoportosításával az összes gyémánt együtt 569 00:25:50,630 --> 00:25:52,560 úgy tűnik, mind a szív együtt úgy tűnik, 570 00:25:52,560 --> 00:25:56,520 és így tovább, tekintet nélkül A számokat a kártya. 571 00:25:56,520 --> 00:26:00,900 És most úgy tűnik, például, hogy válogatás őket szám. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Nagyon jó. 574 00:26:08,910 --> 00:26:12,370 >> Rendben, mi fog az utolsó lépés, akkor itt? 575 00:26:12,370 --> 00:26:16,950 Ha már négy rendezett ruhák, milyen ezt meg kell tennie, hogy a négy cölöpök 576 00:26:16,950 --> 00:26:20,059 annak érdekében, hogy az egyik sorrendje fedélzet, egyszerűen? 577 00:26:20,059 --> 00:26:21,350 Így kell egyesíteni őket. 578 00:26:21,350 --> 00:26:25,160 >> Szóval van egy érdekes gondolat, hogy újra, mondhatnám, nagyon intuitív is 579 00:26:25,160 --> 00:26:28,140 ha talán soha nem csapott hogy ilyen címke rajta. 580 00:26:28,140 --> 00:26:31,900 Ez az alapvető elképzelés az osztódó a probléma nem fele ebben az időben, 581 00:26:31,900 --> 00:26:33,410 de legalább négy darab. 582 00:26:33,410 --> 00:26:36,810 Megoldása nagyon sok alapvetően azonos problémák 583 00:26:36,810 --> 00:26:40,480 elszigetelten egymástól, majd összevonása az eredményeket. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 És kiváló, kész. 586 00:26:50,140 --> 00:26:52,140 Rendben, egy nagy kerek A taps, ha tudnánk. 587 00:26:52,140 --> 00:26:56,480 >> [Taps] 588 00:26:56,480 --> 00:26:59,740 >> Előadó: Fogalmam sincs, hogy mit fog csinálni ezekkel, de itt van. 589 00:26:59,740 --> 00:27:01,690 Köszönöm szépen. 590 00:27:01,690 --> 00:27:04,660 Tehát lássuk, két perc és nyolc másodperc, 591 00:27:04,660 --> 00:27:07,490 Ha azt szeretné, hogy kihívást jelent a barátok. 592 00:27:07,490 --> 00:27:12,160 Mi akkor fog lehet elvenni ezt 593 00:27:12,160 --> 00:27:13,830 hogy mi is kihasználhatják általában? 594 00:27:13,830 --> 00:27:16,080 Nos, gondolj vissza Ez a tömb számát, 595 00:27:16,080 --> 00:27:19,060 és most visszagondolok, hogy néhány pszeudokódja is írtam korábban, 596 00:27:19,060 --> 00:27:22,080 és ez volt az pszeudokód a oldja meg a telefonkönyv probléma. 597 00:27:22,080 --> 00:27:25,150 Amelynek pszeudokód I felsorolt ​​egy módszeres módon 598 00:27:25,150 --> 00:27:28,400 Az, hogy miként csináltam egy nagyon intuitív emberi algoritmus felosztásának a telefon 599 00:27:28,400 --> 00:27:31,650 könyv fél, ismétlés, ismétlés, ismétlés, amíg nem találok valakit, mint Mike Smith, 600 00:27:31,650 --> 00:27:33,790 ha ő valóban a telefonkönyvben. 601 00:27:33,790 --> 00:27:37,610 >> De fajta használt, amit én hívom Nagyon iteratív megközelítés itt, 602 00:27:37,610 --> 00:27:42,160 különösen értesítés sorban 8. és 11. sor. 603 00:27:42,160 --> 00:27:46,750 Ezek bizonyíték ismétlődő megközelítés, a looping megközelítés, 604 00:27:46,750 --> 00:27:49,040 mert ez pontosan a viselkedés arra késztetik. 605 00:27:49,040 --> 00:27:52,910 Ezek a vonalak mind azt mondják, menj vonal három, és akkor milyen 606 00:27:52,910 --> 00:27:55,140 gondolom, hogy a lelki szemei ​​előtt, hogy a hurok. 607 00:27:55,140 --> 00:27:59,080 Azt mondja, hogy menj vissza lépéshez három és ismételje meg, újra és újra, 608 00:27:59,080 --> 00:28:00,010 és újra. 609 00:28:00,010 --> 00:28:04,410 >> De mi van, ha kihasználja a lényeg itt, hogy nem az utolsó alkalom, 610 00:28:04,410 --> 00:28:10,280 és egyszerűsítése sor a 8. és 11. sor és szomszédaik 611 00:28:10,280 --> 00:28:12,840 mivel csak ezt, a sárga. 612 00:28:12,840 --> 00:28:16,480 Ez alapvetően nem lerövidítése A pszeudokód nagyon sok, 613 00:28:16,480 --> 00:28:20,530 de ez alapvetően változik jellege én algoritmus. 614 00:28:20,530 --> 00:28:24,220 Amit én most azt mondja, 7. lépésben, a 10. lépésben, 615 00:28:24,220 --> 00:28:29,140 az, hogy keressük Mike az pontosan ugyanolyan módon, 616 00:28:29,140 --> 00:28:31,580 de csak a bal fél vagy a jobb felét. 617 00:28:31,580 --> 00:28:33,420 >> Tehát más szavakkal, ha Én lépéstől kezdve egy, 618 00:28:33,420 --> 00:28:36,150 vedd fel telefonkönyv, nyitott közép A telefonkönyv, nézd meg nevét, 619 00:28:36,150 --> 00:28:39,010 ha Smith között neve, hívja Mike, más 620 00:28:39,010 --> 00:28:44,340 ha Smith korábbi könyv, Hét lépés keresni Mike bal fele könyv. 621 00:28:44,340 --> 00:28:47,130 De ez a fajta érzés, ez így nekem lóg, nem igaz? 622 00:28:47,130 --> 00:28:49,240 A sárga, egy oktatás, de hogyan tudom 623 00:28:49,240 --> 00:28:51,870 keresni Mike a bal fele a telefonkönyv? 624 00:28:51,870 --> 00:28:54,210 Hol van egy algoritmus, amit 625 00:28:54,210 --> 00:28:57,100 lehet keresni, hogy valaki, mint Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Nos, bámult minket az arca. 627 00:28:58,980 --> 00:29:03,090 Én szó szerint használhatja pontosan ugyanazt program hatékony megy fel a csúcsra 628 00:29:03,090 --> 00:29:06,490 újra és újra lefolytatja az azonos sornyi kódot. 629 00:29:06,490 --> 00:29:10,610 >> Tehát annak ellenére, hogy ezt kell éreznie mint egy kis ciklikus meghatározás 630 00:29:10,610 --> 00:29:13,480 ahol választ valaki kérdést csak egyfajta kérdezi 631 00:29:13,480 --> 00:29:15,990 ugyanazt a kérdést újra, mint, hogy miért, miért, miért? 632 00:29:15,990 --> 00:29:21,580 A valóság az, mert mi már keményen kódolt egy pár speciális vonalak, a 4. lépésben 633 00:29:21,580 --> 00:29:25,320 amely ha, és a 12. lépésben, amely gyakorlatilag egy másik ága, 634 00:29:25,320 --> 00:29:30,120 azért van, mert ezek a hézagpótló intézkedések, ez az algoritmus megszűnik, ha 635 00:29:30,120 --> 00:29:32,050 talál Mike, vagy ha nem. 636 00:29:32,050 --> 00:29:36,810 De a 7. lépésben és 10 most már mi hívjuk a rekurzív algoritmus. 637 00:29:36,810 --> 00:29:40,420 És rekurzió valóban hatalmas ötlet hogy egy kicsit elme hajlító először, 638 00:29:40,420 --> 00:29:42,500 hogy most már alkalmazni az alábbiak szerint. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort lesz az utolsó sort, hogy nézzük, legalábbis az osztályban hivatalosan. 640 00:29:46,600 --> 00:29:50,040 És ez alapvetően különbözik a az utolsó három, és minden bizonnyal 641 00:29:50,040 --> 00:29:52,140 utolsó négy, ha mi is bogosort. 642 00:29:52,140 --> 00:29:54,810 Itt a pszeudokód a merge sort. 643 00:29:54,810 --> 00:30:00,170 Ha a bemeneti n elemek, így adott egy n méretű tömb, ha n értéke kisebb, mint 2, 644 00:30:00,170 --> 00:30:01,040 vissza. 645 00:30:01,040 --> 00:30:03,610 Akkor miért van, hogy józanság ellenőrizze először? 646 00:30:03,610 --> 00:30:09,477 Mi a következménye, ha kéznél van olyan tömb, amelynek hossza n értéke kisebb, mint 2? 647 00:30:09,477 --> 00:30:11,060 Ez már válogatni, nyilván, nem igaz? 648 00:30:11,060 --> 00:30:13,640 Mivel a lista vagy van egy elem, ami triviálisan 649 00:30:13,640 --> 00:30:15,180 válogatni, mert az egyetlen dolog ott. 650 00:30:15,180 --> 00:30:18,138 Vagy, ez a méret nulla, ami azt jelenti nincs mit rendezni, így a természet 651 00:30:18,138 --> 00:30:18,720 van rendezve. 652 00:30:18,720 --> 00:30:20,410 Már csak semmi baj ott. 653 00:30:20,410 --> 00:30:22,310 Szóval ez a mi úgynevezett alap eset. 654 00:30:22,310 --> 00:30:24,440 >> Hogy hasonló szellemben hogy mit csináltunk Mike. 655 00:30:24,440 --> 00:30:26,023 Ha Mike a telefonkönyvben, hívd fel. 656 00:30:26,023 --> 00:30:27,740 Ha nincs ott, feladja. 657 00:30:27,740 --> 00:30:31,240 Ez egy úgynevezett alap eset, hogy megbizonyosodjon arról, ez az algoritmus a végén a nap 658 00:30:31,240 --> 00:30:33,540 leáll bizonyos körülmények között. 659 00:30:33,540 --> 00:30:37,890 >> De itt van az ugrás a hit most más, rendezni a bal fele az elemek, 660 00:30:37,890 --> 00:30:39,740 majd rendezni a megfelelő fele az elemek, 661 00:30:39,740 --> 00:30:41,189 majd egyesíteni a válogatott felét. 662 00:30:41,189 --> 00:30:43,230 És itt van, ahol úgy érzi, mint mi copping ki. 663 00:30:43,230 --> 00:30:46,900 Kértem, hogy rendezni n elem, és én vagyok 664 00:30:46,900 --> 00:30:50,712 mondván: OK, azt válogatás A bal és a válogatás a jobb. 665 00:30:50,712 --> 00:30:52,420 De mondok egy más dolog, és ez 666 00:30:52,420 --> 00:30:55,530 a legfontosabb téma úgy tűnik, Az intuíció eddig, 667 00:30:55,530 --> 00:30:57,380 itt van ez a harmadik lépés összevonása. 668 00:30:57,380 --> 00:31:00,430 Ami még akkor is, úgy tűnik, hogy néma lélekben, 669 00:31:00,430 --> 00:31:02,320 mint éppen összeolvad dolgok együtt, úgy tűnik 670 00:31:02,320 --> 00:31:05,380 kulcsfontosságú lépés a összeszereléséhez két probléma, hogy a 671 00:31:05,380 --> 00:31:07,330 osztották végül ketté. 672 00:31:07,330 --> 00:31:12,090 >> Tehát merge sort, csináljuk ezt, ha lesz humor engem, még egy bemutató, 673 00:31:12,090 --> 00:31:14,730 csak azért, hogy van néhány számok dolgozni. 674 00:31:14,730 --> 00:31:19,470 Tudok cserélni nyolc stressz golyó nyolc ember? 675 00:31:19,470 --> 00:31:29,320 Rendben, mi lenne, ha három, akkor négy Az ebben a részben, öt, hat, és hagyja, hogy a 676 00:31:29,320 --> 00:31:30,720 Nem 7, 8, gyere fel. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, igen az OK gombra. 679 00:31:36,520 --> 00:31:38,640 Mínusz 8, ott vagyunk, plusz 1. 680 00:31:38,640 --> 00:31:39,150 Kiváló. 681 00:31:39,150 --> 00:31:42,000 Rendben gyere fel, menjünk gyorsan kapsz számokat. 682 00:31:42,000 --> 00:31:50,800 A kettes, hármas, négyes, szám öt, hat, hét, illetve nyolc. 683 00:31:50,800 --> 00:31:52,140 Én nyolc helyesen ezúttal. 684 00:31:52,140 --> 00:31:56,390 >> OK, így megy előre, ha meg tudná, és nézzük rendezni az eredeti sorrendben 685 00:31:56,390 --> 00:31:59,810 hogy mi volt tegnap, amely úgy nézett mint ez, ha nem bánja. 686 00:31:59,810 --> 00:32:03,620 És tegyük elé az asztalra. 687 00:32:03,620 --> 00:32:06,510 Rendben, merge sort. 688 00:32:06,510 --> 00:32:08,820 Ez az, ahol ez lesz hogy milyen érdekes, 689 00:32:08,820 --> 00:32:12,800 mert úgy tűnik, hogy így magam így sokkal kevesebb információ ma. 690 00:32:12,800 --> 00:32:15,149 >> Így egyesíteni fajta először input n elemek, 691 00:32:15,149 --> 00:32:18,440 és nyilvánvalóan nem kevesebb, mint két, ez nyolc, így még egy kis munka. 692 00:32:18,440 --> 00:32:21,140 Tehát most mentálisan is, mint egy osztály most a más ág, 693 00:32:21,140 --> 00:32:22,540 ami azt jelenti, három lépésből áll. 694 00:32:22,540 --> 00:32:25,017 Először is, meg kell rendezni a bal fele az elemek. 695 00:32:25,017 --> 00:32:26,350 Szóval, hogyan kezdjen csinálja ezt? 696 00:32:26,350 --> 00:32:28,950 Nos, én megyek, hogy milyen szellemileg osztani a listát itt, 697 00:32:28,950 --> 00:32:30,700 nem kell fizikailag mozog, és én vagyok 698 00:32:30,700 --> 00:32:33,180 majd, hogy csak a bal felén az elemek itt. 699 00:32:33,180 --> 00:32:36,770 Szóval, hogyan megy a válogatás A lista most már a méret négy? 700 00:32:36,770 --> 00:32:38,730 Mi az én algoritmus? 701 00:32:38,730 --> 00:32:42,580 Először ellenőrizd, n kevesebb, mint két, nem, így folytassa a más blokk újra. 702 00:32:42,580 --> 00:32:43,900 Fajta bal fele elemekkel. 703 00:32:43,900 --> 00:32:45,608 >> Így most újra, szellemileg, és ez az, ahol 704 00:32:45,608 --> 00:32:49,550 meg kell felhalmozni sok szellemi történelem, ha úgy tetszik. 705 00:32:49,550 --> 00:32:51,940 Most válogatás a bal fele a bal felét. 706 00:32:51,940 --> 00:32:57,000 Rendben, most hívom ugyanaz merge rendezési algoritmus, n kevesebb, mint két? 707 00:32:57,000 --> 00:33:00,590 Nem, ez két, úgyhogy meg kell rendezni a bal oldalán, és a jobb fele. 708 00:33:00,590 --> 00:33:02,042 Szóval itt vagyunk, rendezni a bal felét. 709 00:33:02,042 --> 00:33:03,750 Miért nem csak tegyél egy lépést előre. 710 00:33:03,750 --> 00:33:04,415 Mi a neve? 711 00:33:04,415 --> 00:33:04,860 >> Közönség: Darren. 712 00:33:04,860 --> 00:33:05,260 >> Előadó: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan előrelépett. 714 00:33:06,040 --> 00:33:06,748 >> Közönség: Darren. 715 00:33:06,748 --> 00:33:09,000 Előadó: Darren, kész. 716 00:33:09,000 --> 00:33:10,090 Azt mondta, Darren vagy Dan? 717 00:33:10,090 --> 00:33:10,550 >> Közönség: Darren. 718 00:33:10,550 --> 00:33:11,216 >> Előadó: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren fokozta előre, és ő most rendezve. 720 00:33:14,422 --> 00:33:16,130 És ez majdnem egy ostoba állítás, igaz? 721 00:33:16,130 --> 00:33:18,862 Én nem igazán úgy tűnik, hogy eléréséhez semmit, de nézzük tovább. 722 00:33:18,862 --> 00:33:20,820 Most hadd rendezni a megfelelő fele az elemekkel. 723 00:33:20,820 --> 00:33:21,200 Mi a neve? 724 00:33:21,200 --> 00:33:21,690 >> Közönség: Luke. 725 00:33:21,690 --> 00:33:22,273 >> Előadó: Luke. 726 00:33:22,273 --> 00:33:23,400 Gyerünk, lépjen előre. 727 00:33:23,400 --> 00:33:25,640 Kész, már rendezve Luke. 728 00:33:25,640 --> 00:33:28,570 A bal fele most válogatni és a jobb fele ma már rendezett, 729 00:33:28,570 --> 00:33:30,770 de a lényeg, van egy kulcsfontosságú lépés itt. 730 00:33:30,770 --> 00:33:32,940 Mit mellett kell tennem? 731 00:33:32,940 --> 00:33:33,941 Egyesíti a válogatott felét. 732 00:33:33,941 --> 00:33:36,648 Most fogunk csak meg mindenki oda-vissza ezen a módon, 733 00:33:36,648 --> 00:33:38,620 mert a fajta kell néhány karcolás helyet. 734 00:33:38,620 --> 00:33:40,411 Ez majdnem olyan, mint ezek a srácok az asztalra, 735 00:33:40,411 --> 00:33:42,460 és szükségem van egy kis szoba mozgatni őket körül. 736 00:33:42,460 --> 00:33:44,170 Úgyhogy egyesíteni srácok a keresett 737 00:33:44,170 --> 00:33:45,960 A bal oldalán és a jobb fele. 738 00:33:45,960 --> 00:33:48,740 És aki nyilvánvalóan az első, balra félig vagy jobb felét? 739 00:33:48,740 --> 00:33:52,710 Tehát jobb oldalán, tehát menjünk Luke át ide Darren eredeti helyzetébe. 740 00:33:52,710 --> 00:33:57,640 És most, hogy egyesítik a bal fele a, Darren fog mozogni ott. 741 00:33:57,640 --> 00:33:59,750 >> Tehát úgy érzi, szinte a buborék sort hatás 742 00:33:59,750 --> 00:34:02,482 de én alapvető algoritmus, nagyon más ebben az időben. 743 00:34:02,482 --> 00:34:04,815 De most, ahol a dolgok egy kicsit bosszantó, mert 744 00:34:04,815 --> 00:34:06,810 kell visszaforgatni mentálisan Hol hagytam ki. 745 00:34:06,810 --> 00:34:09,893 Épp most összevonták a rendezett felét, ami azt jelenti, ott vagyok, ahol az én algoritmus? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Meg kell rendezni a jobb fél, ugye? 748 00:34:13,770 --> 00:34:15,910 >> Ha visszalép, a szó szoros értelmében A videó, akkor 749 00:34:15,910 --> 00:34:18,339 látni, hogy mi van, hogy ezt a pont Luke és Darren 750 00:34:18,339 --> 00:34:21,370 válogatás a bal fele a bal felét. 751 00:34:21,370 --> 00:34:23,430 Aztán egyesült azokat rendezett felét, ami 752 00:34:23,430 --> 00:34:27,941 azt jelenti, a következő lépés a sort a jobb felét a bal felét. 753 00:34:27,941 --> 00:34:29,649 Rendben, szóval Ehhez gyorsabban. 754 00:34:29,649 --> 00:34:33,282 Rendben, hat, megyek igényt Ön most válogatni, gyerünk előre. 755 00:34:33,282 --> 00:34:33,990 Mi a neve? 756 00:34:33,990 --> 00:34:34,589 >> Közönség: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> Előadó: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano most rendezve. 759 00:34:36,010 --> 00:34:36,450 És mi a neved? 760 00:34:36,450 --> 00:34:37,080 >> Közönség: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Előadó: Alex most rendezve. 762 00:34:38,379 --> 00:34:40,750 Bal fele, jobb felét, mi a végső lépés? 763 00:34:40,750 --> 00:34:41,250 Egyesítése. 764 00:34:41,250 --> 00:34:44,310 Elég triviális, úgyhogy majd összevonni hat, 765 00:34:44,310 --> 00:34:46,930 egy lépést hátra, nyolc, egy lépést hátra. 766 00:34:46,930 --> 00:34:49,530 És most észre ezt hasznos elvihető, milyen 767 00:34:49,530 --> 00:34:53,930 most igaz a bal fele a listáját, függetlenül attól, hogy mi kezdődött? 768 00:34:53,930 --> 00:34:55,090 Ez van rendezve. 769 00:34:55,090 --> 00:34:57,750 >> Most már nem rendezve A nagy dolgok rendjében, 770 00:34:57,750 --> 00:35:00,250 de van rendezve függetlenül a másik felét. 771 00:35:00,250 --> 00:35:04,100 Most mi lépés vagyok az, ha én is visszacsévélés, hogy a történet kezdődött? 772 00:35:04,100 --> 00:35:05,680 Most kell rendezni a jobb felét. 773 00:35:05,680 --> 00:35:07,630 Így most már vissza a az elején a történetet, 774 00:35:07,630 --> 00:35:08,921 és csináljuk gyorsabban. 775 00:35:08,921 --> 00:35:11,320 Így fogok rendezni a jobb fele a teljes lista. 776 00:35:11,320 --> 00:35:13,060 Mi a következő lépés? 777 00:35:13,060 --> 00:35:15,840 Rendezni a bal fele a jobb felét. 778 00:35:15,840 --> 00:35:18,715 Rendezni a bal fele a bal fele a jobb felét. 779 00:35:18,715 --> 00:35:19,590 És mi a neved? 780 00:35:19,590 --> 00:35:20,230 >> Közönség: Omar. 781 00:35:20,230 --> 00:35:21,970 >> Előadó: Omar, lépjen előre, kész. 782 00:35:21,970 --> 00:35:22,860 Bal fele van rendezve. 783 00:35:22,860 --> 00:35:23,330 És mi a neved? 784 00:35:23,330 --> 00:35:23,820 >> Közönség: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Előadó: Chris, egy lépést előre, akkor most rendezve. 786 00:35:25,620 --> 00:35:27,010 Mi az a legfontosabb lépés most? 787 00:35:27,010 --> 00:35:27,510 Egyesítése. 788 00:35:27,510 --> 00:35:30,509 Tehát az egyik fog egyesíteni a helyére Itt, ha lehetne egy lépést hátra, 789 00:35:30,509 --> 00:35:32,930 és három fog egy lépést hátra, összeolvad. 790 00:35:32,930 --> 00:35:38,080 Tehát a bal fele a jobb oldalán, most rendezve. 791 00:35:38,080 --> 00:35:41,747 Őszintén szólva, ez az algoritmus olyan, mint mi pazarolsz így több időt, mint korábban, 792 00:35:41,747 --> 00:35:44,830 de ha nem ez a valós időben, akkor mi az elvitelre lesz. 793 00:35:44,830 --> 00:35:47,970 Most itt vagyok, jobb fele a jobb felét, 794 00:35:47,970 --> 00:35:50,170 hadd menjen előre, és rendezni a bal felét. 795 00:35:50,170 --> 00:35:51,482 Lépjen előre, mi a neve? 796 00:35:51,482 --> 00:35:52,190 Közönség: Ramsey. 797 00:35:52,190 --> 00:35:53,210 Előadó: Ramsey most rendezve. 798 00:35:53,210 --> 00:35:53,570 Mi a neve? 799 00:35:53,570 --> 00:35:54,200 >> Közönség: Marina. 800 00:35:54,200 --> 00:35:57,033 >> Előadó: Marina most sorrendje a Nos, ha veszel egy lépést előre. 801 00:35:57,033 --> 00:36:00,690 Kulcsfontosságú lépés itt most összeolvad, vagyok majd összeszedi az én két listát, 802 00:36:00,690 --> 00:36:01,720 balra és jobbra. 803 00:36:01,720 --> 00:36:05,150 Öt fog jönni az első, és hét fog jönni legközelebb. 804 00:36:05,150 --> 00:36:06,410 És ismét, ez szándékos. 805 00:36:06,410 --> 00:36:08,535 Az a tény, hogy ők figyelembe lépést előre és vissza 806 00:36:08,535 --> 00:36:12,997 célja, hogy képviselje, hogy nem tudjuk Ehhez algoritmus helyen könnyen 807 00:36:12,997 --> 00:36:15,830 A buborék rendezés, és a kiválasztás sort, és beillesztés sort, ahol csak 808 00:36:15,830 --> 00:36:16,960 tartotta csere emberek. 809 00:36:16,960 --> 00:36:19,940 Szó szerint kell egyfajta A semmiből papírt, amelyben 810 00:36:19,940 --> 00:36:21,827 , hogy ezek az emberek míg én az egyesülő, 811 00:36:21,827 --> 00:36:23,410 és akkor én is őket vissza a helyére. 812 00:36:23,410 --> 00:36:27,260 És ez kulcsfontosságú, mert én egy új forrás, hely, nem csak időt. 813 00:36:27,260 --> 00:36:28,270 >> OK, ez fantasztikus. 814 00:36:28,270 --> 00:36:32,050 Bal fele van rendezve, jobb fele rendezett, most, hogy kulcs összevonása lépés. 815 00:36:32,050 --> 00:36:33,450 Hogyan fogom egyesíteni ezt? 816 00:36:33,450 --> 00:36:35,470 Tehát, ha lesz követni a bal és jobb kéz, 817 00:36:35,470 --> 00:36:38,930 Fogom mutatni a bal oldali a bal fele, a jobb kezem 818 00:36:38,930 --> 00:36:42,680 a jobb oldalán, és most azt kell dönt lépésről lépésre akit összevonni. 819 00:36:42,680 --> 00:36:44,650 Aki nyilvánvalóan előbb? 820 00:36:44,650 --> 00:36:45,150 Számú. 821 00:36:45,150 --> 00:36:47,327 Szóval gyerünk ide, itt van a jegyzettömb. 822 00:36:47,327 --> 00:36:49,910 Így most első számú, és a közlemény mit fogok csinálni a jobb kezemmel, 823 00:36:49,910 --> 00:36:54,152 Fogom mozgatni a jobb kezét egy átlépni pont száma három, 824 00:36:54,152 --> 00:36:55,860 és most már, hogy a ugyanazt a döntést. 825 00:36:55,860 --> 00:36:58,387 És valóban áll közvetlenül előtt Luke ide, ha lehetne, 826 00:36:58,387 --> 00:36:59,720 mert ez a mi jegyzettömb. 827 00:36:59,720 --> 00:37:00,610 Szóval, ki lesz a következő? 828 00:37:00,610 --> 00:37:05,000 Van Luke a kettes számú vagy Chris a hármas szám. 829 00:37:05,000 --> 00:37:07,460 Nyilvánvaló Luke, szám két, így jön ide. 830 00:37:07,460 --> 00:37:11,270 >> De a bal kezem most fog növekedhet, hogy rámutasson Darren, 831 00:37:11,270 --> 00:37:15,160 és itt van a kulcs, hogy el összevonása, fogom tartani ezt, 832 00:37:15,160 --> 00:37:17,340 Nyilvánvaló, hogy ha kedves a logikáját követik. 833 00:37:17,340 --> 00:37:19,670 De a kezem soha megyek vissza, 834 00:37:19,670 --> 00:37:23,861 ami azt jelenti, hogy én mindig csak költözik A bal oldali az én összefonódó folyamat, 835 00:37:23,861 --> 00:37:26,360 és ez lesz a kulcs elemzés csak egy pillanat. 836 00:37:26,360 --> 00:37:27,859 >> Tehát most fejezzük be ezt fel gyorsan. 837 00:37:27,859 --> 00:37:31,650 Tehát három következik, majd négy következik, 838 00:37:31,650 --> 00:37:38,750 és most öt következik, akkor hat, és hét, és végül nyolc. 839 00:37:38,750 --> 00:37:42,960 Olyan, mint a leglassabb algoritmus még, de akkor nem, ha tényleg 840 00:37:42,960 --> 00:37:45,510 futtatni ugyanazon fajta Az órajel, így a 841 00:37:45,510 --> 00:37:48,106 beszél, az azonos óra ketyeg, mint korábban. 842 00:37:48,106 --> 00:37:48,605 Miért? 843 00:37:48,605 --> 00:37:51,100 Nos, hogy egy nézd meg a végeredmény. 844 00:37:51,100 --> 00:37:56,990 >> Menjünk vissza ide, hadd húzza fel a bemutató vizuálisan 845 00:37:56,990 --> 00:37:59,030 Az, amit most csináltunk. 846 00:37:59,030 --> 00:38:06,110 Nagyítás itt, ezen oldalon van, és azt mondta a Firefox 847 00:38:06,110 --> 00:38:08,200 hogy azt akarjuk, hogy sorban fel ebben a dobozban, nézzük 848 00:38:08,200 --> 00:38:11,260 mondjuk buborék sort, amellyel mi most jól ismert, 849 00:38:11,260 --> 00:38:14,130 kiválasztás sort, amely egy másik meglehetősen egyszerű egy, 850 00:38:14,130 --> 00:38:18,250 és most a mai merge sort, amely lesz a klimatikus véget. 851 00:38:18,250 --> 00:38:21,530 Az ok tartott ilyen sokáig itt az emberek, és én szóban is, 852 00:38:21,530 --> 00:38:23,480 Nyilvánvaló, hogy én elmagyarázza minden lépésnél. 853 00:38:23,480 --> 00:38:26,920 De ha ki ezt a sok mint mi buborék sort és kiválasztás 854 00:38:26,920 --> 00:38:30,890 fajta nem csak vizuálisan, óra hogy mennyi hatékonyabban 855 00:38:30,890 --> 00:38:33,330 ez kiegyenlítését megosztottság és hódító 856 00:38:33,330 --> 00:38:39,150 lehet alkalmazni egy adathalmaz, ami sem méret nyolc, de még sok, 857 00:38:39,150 --> 00:38:39,970 sokkal nagyobb. 858 00:38:39,970 --> 00:38:44,585 Adok egyesíteni sort, egymás oldalán az egyéb algoritmusok. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Ez fog kapni fájdalmas gyorsan, és a vége 861 00:38:58,530 --> 00:39:00,890 nem különösebben éghajlati, ők csak a végén rendezve. 862 00:39:00,890 --> 00:39:05,280 De a legfontosabb, hogy el, hogy Nézd, milyen sokkal gyorsabb merge sort 863 00:39:05,280 --> 00:39:08,110 volt, kivéve, ha azt hiszed, csak egyfajta szórakozik veled. 864 00:39:08,110 --> 00:39:13,100 Ha ezt egy utolsó alkalommal, Nézzük reload ezt, menjünk vissza 865 00:39:13,100 --> 00:39:14,960 , és válassza a buborék sort, és csak a hecc kedvéért, 866 00:39:14,960 --> 00:39:17,330 hadd válassza beillesztés sort, csak a jó intézkedés. 867 00:39:17,330 --> 00:39:20,020 És újra, nézzük választani merge sort és nézzük 868 00:39:20,020 --> 00:39:21,595 valójában futtatni ezeket egymás mellett. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> És ez nem, sőt, a véletlen. 871 00:39:26,930 --> 00:39:31,140 Amit gyakorlatilag kész van én már osztva a bemenet félbe, megint, 872 00:39:31,140 --> 00:39:32,240 és újra, és újra. 873 00:39:32,240 --> 00:39:35,590 És csak annyi alkalommal lehet ossza meg bevinni fele, bal 874 00:39:35,590 --> 00:39:36,240 és jobb. 875 00:39:36,240 --> 00:39:39,425 Mi az a formula, amit folyamatosan látják hogy leírja a hadosztály fele 876 00:39:39,425 --> 00:39:41,050 újra, és újra, és újra, és újra? 877 00:39:41,050 --> 00:39:41,890 >> Közönség: log n. 878 00:39:41,890 --> 00:39:42,760 >> Előadó: log n. 879 00:39:42,760 --> 00:39:46,300 De akkor van egy másik fontos lépés, Ez az algoritmus nem log n. 880 00:39:46,300 --> 00:39:48,992 Ha csak log n, mi lenne ugyanaz a probléma 881 00:39:48,992 --> 00:39:51,200 mint korábban, ahol nem lehet Biztos minden rendben rendezve. 882 00:39:51,200 --> 00:39:54,480 Meg kell minimálisan nézni n eleme hogy biztos, n elemek sorrendje, 883 00:39:54,480 --> 00:39:55,950 egyébként ez egy ugrás a hit. 884 00:39:55,950 --> 00:39:59,810 >> Szóval ez minimálisan log n lépést, de Mi van ezzel a kulcs összevonása lépés 885 00:39:59,810 --> 00:40:04,370 ahol egyesült a bal felét és a jobb fél és átsétált a színpadon? 886 00:40:04,370 --> 00:40:06,980 Hány lépés az, hogy egyesíteni? 887 00:40:06,980 --> 00:40:10,150 Ez n, de én nem csak egyesíti a végső idő. 888 00:40:10,150 --> 00:40:15,089 Minden ilyen beágyazott hívások, minden azok beágyazott egyesítés, én még mindig rendezve. 889 00:40:15,089 --> 00:40:18,380 Én egyesült a két fickó, akkor ez a két srácok, akkor ez a két fickó, és így tovább. 890 00:40:18,380 --> 00:40:19,955 >> Úgyhogy összevonása újra, és újra. 891 00:40:19,955 --> 00:40:20,580 Hányszor? 892 00:40:20,580 --> 00:40:23,510 Így minden alkalommal, amikor megosztotta a lista félbe, csináltam egy merge. 893 00:40:23,510 --> 00:40:25,460 Osszuk a listát fél, nem a merge. 894 00:40:25,460 --> 00:40:28,570 Tehát, ha elosztjuk a lista lehet tenni log n-szer, 895 00:40:28,570 --> 00:40:33,880 és az egyesülő végül vesz n lépések, mi lehet most a felső 896 00:40:33,880 --> 00:40:37,000 kötött a futó idő a mi algoritmus? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> És valóban, ez az, ami értünk el itt. 899 00:40:40,560 --> 00:40:44,650 Így az érzést, amit látsz vizuálisan amikor a három dolog fut egymás mellett 900 00:40:44,650 --> 00:40:47,930 n négyzetes ellen n kockás ellen n log n. 901 00:40:47,930 --> 00:40:51,010 Amely alapvetően majd meglátjuk, nem csak ma, hanem a jövőben, 902 00:40:51,010 --> 00:40:52,760 sokkal, de sokkal gyorsabb. 903 00:40:52,760 --> 00:40:56,010 A tapsot ezek a srácok, Én megjutalmazza őket stressz labda. 904 00:40:56,010 --> 00:41:00,260 Hadd vonuljon ma, és majd meglátjuk, hogy hétfőn. 905 00:41:00,260 --> 00:41:02,255