1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [MUSIC PLAYING] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Rendben. 4 00:00:13,500 --> 00:00:14,670 Rendben, szívesen vissza. 5 00:00:14,670 --> 00:00:18,120 Szóval ez a 4. héten, az elején erről már. 6 00:00:18,120 --> 00:00:21,320 És emlékezzünk csak vissza, hogy a múlt héten, tesszük kódot félre egy kicsit 7 00:00:21,320 --> 00:00:24,240 és elkezdtünk beszélgetni egy kicsit magas szintű, a dolgok, mint a 8 00:00:24,240 --> 00:00:28,130 keresés és válogatás, amely ugyan kissé egyszerű ötletek, amelyek 9 00:00:28,130 --> 00:00:31,840 képviselője osztály a problémák akkor kezdenek megoldani különösen 10 00:00:31,840 --> 00:00:34,820 ahogy elkezd gondolkodni végső projektek és érdekes megoldásokat 11 00:00:34,820 --> 00:00:36,760 Lehet, hogy valós problémákat. 12 00:00:36,760 --> 00:00:39,490 Most buborék fajta volt az egyik legegyszerűbb ilyen algoritmusok, és ez 13 00:00:39,490 --> 00:00:42,900 dolgozott, azáltal, hogy ezek a kis számú listában, vagy egy sor olyan 14 00:00:42,900 --> 00:00:46,530 buborék az utat felfelé a csúcsra, és a nagy számban mozognak az utat lefelé 15 00:00:46,530 --> 00:00:47,930 a végén, hogy a listán. 16 00:00:47,930 --> 00:00:50,650 >> És emlékszem, hogy mi lehetett képzelni bubble sort egy kicsit 17 00:00:50,650 --> 00:00:52,310 valami ilyesmi. 18 00:00:52,310 --> 00:00:53,640 Hadd megy előre, és kattintson az Indítás gombra. 19 00:00:53,640 --> 00:00:55,350 Már előre kiválasztott bubble sort. 20 00:00:55,350 --> 00:00:58,920 És ha emlékeztetni arra, hogy a magasabb kék vonalak nagy számok, kis- 21 00:00:58,920 --> 00:01:03,300 kék vonalak kis számban, mint megyünk át ezt újra és újra, és 22 00:01:03,300 --> 00:01:07,680 Ismét, összehasonlítva két bár egymás mellett másik piros, megyünk, hogy a csere a 23 00:01:07,680 --> 00:01:11,010 legnagyobb és a legkisebb, ha ezek elromlott. 24 00:01:11,010 --> 00:01:14,150 >> Tehát ez megy, és megy és megy tovább, és látni fogod, hogy a nagyobb 25 00:01:14,150 --> 00:01:16,700 elemek teszik az utat, hogy a jobbra, és a kisebb elemek 26 00:01:16,700 --> 00:01:17,900 útjukat balra. 27 00:01:17,900 --> 00:01:21,380 De elkezdett számszerűsíteni A hatékonyság, a 28 00:01:21,380 --> 00:01:22,970 minősége az algoritmus. 29 00:01:22,970 --> 00:01:25,200 És azt mondta, hogy a legrosszabb esetben, ez az algoritmus került 30 00:01:25,200 --> 00:01:27,940 nagyjából hány lépés? 31 00:01:27,940 --> 00:01:28,980 >> Tehát n négyzeten. 32 00:01:28,980 --> 00:01:30,402 És mi volt n? 33 00:01:30,402 --> 00:01:31,650 >> Közönség: Elemek száma. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Tehát n volt elemek száma. 35 00:01:32,790 --> 00:01:33,730 És így fogjuk ezt gyakran. 36 00:01:33,730 --> 00:01:36,650 Minden alkalommal, amikor szeretnénk beszélni a méret a probléma, vagy a mérete 37 00:01:36,650 --> 00:01:39,140 bemenet, vagy az időt vesz igénybe hogy a kimenet, akkor csak 38 00:01:39,140 --> 00:01:41,610 általános bármi a bemenet, amint n. 39 00:01:41,610 --> 00:01:45,970 Tehát vissza a 0. héten, hogy hány oldalt a telefonkönyvben volt n. 40 00:01:45,970 --> 00:01:47,550 A hallgatók száma A szobát n. 41 00:01:47,550 --> 00:01:49,630 Tehát itt is, mi után ezt a mintát. 42 00:01:49,630 --> 00:01:52,800 >> Most n squared nem különösebben gyors, így megpróbáltuk jobban. 43 00:01:52,800 --> 00:01:55,970 És így nézett néhány más algoritmusok, amelyek közül 44 00:01:55,970 --> 00:01:57,690 volt kiválasztás sort. 45 00:01:57,690 --> 00:01:59,180 Így kiválasztás sort volt egy kicsit más. 46 00:01:59,180 --> 00:02:03,130 Már majdnem egyszerűbb, merem mondani, ahol kezdtem elején a 47 00:02:03,130 --> 00:02:06,740 lista a önkéntesek, és én csak újra és újra és újra ment keresztül 48 00:02:06,740 --> 00:02:10,060 A lista kopasztás ki a legkisebb elem egy időben és üzembe neki, vagy 49 00:02:10,060 --> 00:02:13,040 őt a lista elején. 50 00:02:13,040 --> 00:02:16,410 >> De ez is, miután elkezdtünk gondolkodni a matematika és a nagyobb 51 00:02:16,410 --> 00:02:19,860 kép, gondoltam, hányszor Én megyek vissza oda-vissza 52 00:02:19,860 --> 00:02:24,090 oda, azt mondta, a legrosszabb esetben, kiválasztás sort is, mi volt? 53 00:02:24,090 --> 00:02:24,960 N négyzeten. 54 00:02:24,960 --> 00:02:27,490 Most a valós világban, talán valóban kis mértékben gyorsabb. 55 00:02:27,490 --> 00:02:30,620 Mert megint nem kell tartani visszalépés egyszer én is rendezett a 56 00:02:30,620 --> 00:02:31,880 legkisebb elem. 57 00:02:31,880 --> 00:02:35,090 De ha belegondolunk nagyon nagy n, és ha valami tenniük ki a matematika, mint 58 00:02:35,090 --> 00:02:39,170 Én a táblán, az n négyzetes mínusz valami, minden más 59 00:02:39,170 --> 00:02:41,850 mellett az n négyzetes, ha n lesz nagyon nagy, nem 60 00:02:41,850 --> 00:02:42,850 igazán számít annyira. 61 00:02:42,850 --> 00:02:45,470 Szóval mint számítógépes szakemberek, azt valahogy szemet huny a kisebb 62 00:02:45,470 --> 00:02:49,220 tényezők, és elsősorban csak a tényező kifejezés, ami megy, hogy 63 00:02:49,220 --> 00:02:50,330 a legnagyobb különbség. 64 00:02:50,330 --> 00:02:52,840 >> Nos, végül, néztünk A beszúrás sort. 65 00:02:52,840 --> 00:02:56,620 És ez volt a hasonló szellemben, de nem megy át iteratív és 66 00:02:56,620 --> 00:03:01,250 válassza ki azt a legkisebb elemet egyenként időben, ahelyett, hogy vette a kezemet, 67 00:03:01,250 --> 00:03:04,070 foglalkozott, és úgy döntöttem, minden van, akkor ide tartozik. 68 00:03:04,070 --> 00:03:06,160 Aztán haladt, hogy a következő elem és úgy döntött, hogy ő maga vagy 69 00:03:06,160 --> 00:03:07,470 ő ide tartozik. 70 00:03:07,470 --> 00:03:08,810 Aztán haladt tovább. 71 00:03:08,810 --> 00:03:11,780 És talán az, az út mentén, váltás ezek a srácok, hogy 72 00:03:11,780 --> 00:03:13,030 hogy helyet nekik. 73 00:03:13,030 --> 00:03:16,880 Szóval ez volt az a fajta mentális megfordítása A kiválasztás sort, hogy mi 74 00:03:16,880 --> 00:03:18,630 nevű beszúrás sort. 75 00:03:18,630 --> 00:03:20,810 >> Tehát ezek a témák fordulnak elő a valós világban. 76 00:03:20,810 --> 00:03:23,640 Csak néhány évvel ezelőtt, amikor egy bizonyos szenátor elnöki székért, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, abban az időben a vezérigazgató Google, valóban volt lehetősége 78 00:03:27,160 --> 00:03:28,040 hogy interjút vele. 79 00:03:28,040 --> 00:03:32,010 És azt hittük, ossza meg ezt a YouTube klip itt, ha tudnánk előkerülnek 80 00:03:32,010 --> 00:03:32,950 a hangerőt. 81 00:03:32,950 --> 00:03:39,360 >> [VIDEÓ LEJÁTSZÁS] 82 00:03:39,360 --> 00:03:44,620 >> -Nos, szenátor, hogy itt vagy a Google, és szeretem azt hinni, az elnökség 83 00:03:44,620 --> 00:03:46,042 mint egy állásinterjún. 84 00:03:46,042 --> 00:03:47,770 >> [Nevetés] 85 00:03:47,770 --> 00:03:50,800 >> -Most már nehéz, hogy munkát mint elnök. 86 00:03:50,800 --> 00:03:52,480 És megy keresztül a borzongás most. 87 00:03:52,480 --> 00:03:54,330 Az is nehéz, hogy a munkát a Google. 88 00:03:54,330 --> 00:03:59,610 Van kérdése és kérjük a jelöltek kérdésekre. 89 00:03:59,610 --> 00:04:02,250 És ez az egyik a Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Nevetés] 91 00:04:05,325 --> 00:04:06,400 -Azt hiszitek, viccelek? 92 00:04:06,400 --> 00:04:08,750 Ez itt van. 93 00:04:08,750 --> 00:04:12,110 Mi a leghatékonyabb módja annak, hogy rendezni a két millió bites egész? 94 00:04:12,110 --> 00:04:15,810 >> [Nevetés] 95 00:04:15,810 --> 00:04:18,260 >> -Nos, hát - 96 00:04:18,260 --> 00:04:19,029 >> -Sajnálom. 97 00:04:19,029 --> 00:04:19,745 Talán meg kellene - 98 00:04:19,745 --> 00:04:21,000 >> -Nem, nem, nem, nem, nem. 99 00:04:21,000 --> 00:04:21,470 >> -Ez nem egy - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Azt hiszem, a buborék fajta lenne nem a megfelelő út. 102 00:04:25,328 --> 00:04:26,792 >> [Nevetés] 103 00:04:26,792 --> 00:04:28,510 >> [Éljenez és tapsol] 104 00:04:28,510 --> 00:04:31,211 >> -Ugyan már, ki mondta ezt neki? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END VIDEÓ LEJÁTSZÁS] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Szóval ott van ez. 108 00:04:35,070 --> 00:04:39,600 Így elkezdtünk számszerűsíteni a működési alkalommal, hogy úgy mondjam, valami 109 00:04:39,600 --> 00:04:43,480 nevű aszimptotikus jelölés, amely csak utal a fajta fordult 110 00:04:43,480 --> 00:04:47,420 egy vak szemet a kisebb tényezők és csak nézte a működési idő, 111 00:04:47,420 --> 00:04:51,250 teljesítményét ezen algoritmusok, az n lesz igazán nagy az idő múlásával. 112 00:04:51,250 --> 00:04:55,110 És így be nagy O. és nagy O képviseltem valamit, hogy azt gondoltuk, 113 00:04:55,110 --> 00:04:57,000 , mint egy felső határ. 114 00:04:57,000 --> 00:04:59,570 És valóban, Barry, tudunk alacsonyabb mint a mikrofon egy kicsit? 115 00:04:59,570 --> 00:05:01,040 >> Úgy gondoltuk, ez egy felső határ. 116 00:05:01,040 --> 00:05:04,710 Olyan nagy O n négyzetes azt jelenti, hogy A legrosszabb esetben, valami hasonló 117 00:05:04,710 --> 00:05:07,780 kiválasztás sort venne n négyzeten lépéseket. 118 00:05:07,780 --> 00:05:10,310 Vagy valami hasonló beszúrás sort lenne n négyzeten lépéseket. 119 00:05:10,310 --> 00:05:15,150 Most valami hasonló beillesztés sort, hogy mi volt a legrosszabb? 120 00:05:15,150 --> 00:05:18,200 Adott egy tömb, mi a legrosszabb, lehetséges forgatókönyv, hogy lehet találni 121 00:05:18,200 --> 00:05:20,650 magát szembe? 122 00:05:20,650 --> 00:05:21,860 >> Ez teljesen hátra, igaz? 123 00:05:21,860 --> 00:05:24,530 Mert ha ez teljesen hátra, meg kell csinálni egy csomó munkát. 124 00:05:24,530 --> 00:05:26,420 Mert ha teljesen hátra, fogsz találni a 125 00:05:26,420 --> 00:05:28,840 legnagyobb elem itt, annak ellenére, tartozik oda. 126 00:05:28,840 --> 00:05:31,140 Így fogsz mondani, minden rendben, a ebben a pillanatban, akkor ide tartozik, 127 00:05:31,140 --> 00:05:32,310 így hagyja békén. 128 00:05:32,310 --> 00:05:35,425 >> Aztán rájössz, ó, a fenébe, meg kell mozog ez valamivel kisebb elemet 129 00:05:35,425 --> 00:05:36,470 A bal oldali a ketten. 130 00:05:36,470 --> 00:05:38,770 Akkor azt kell csinálni, hogy újra és újra és újra. 131 00:05:38,770 --> 00:05:41,410 És ha mentem oda-vissza, akkor ami egyfajta érezni a teljesítmény 132 00:05:41,410 --> 00:05:45,540 ez az algoritmus, mert állandóan vagyok csoszogó mindenki le a 133 00:05:45,540 --> 00:05:46,510 array, hogy helyet is. 134 00:05:46,510 --> 00:05:47,750 Szóval ez a legrosszabb esetben. 135 00:05:47,750 --> 00:05:48,570 >> Ezzel szemben - 136 00:05:48,570 --> 00:05:50,320 és ez volt a filmsorozat utoljára - 137 00:05:50,320 --> 00:05:54,065 azt mondta, hogy a beszúrás sort volt egy omega, mi? 138 00:05:54,065 --> 00:05:57,530 Mi a legjobb eset futás behelyezés sort? 139 00:05:57,530 --> 00:05:58,520 Szóval ez tényleg n. 140 00:05:58,520 --> 00:06:00,980 Ez volt az üres, hogy mi maradt a táblán utoljára. 141 00:06:00,980 --> 00:06:03,160 >> És ez az omega n, mert miért? 142 00:06:03,160 --> 00:06:06,630 Nos, a legjobb helyzet, mi a beillesztés sort fog adni? 143 00:06:06,630 --> 00:06:09,830 Nos, a lista, amelyet teljesen rendezett már, minimális munka. 144 00:06:09,830 --> 00:06:12,460 De mi szép a beszúrás sort az, hogy mivel itt kezdődik, és 145 00:06:12,460 --> 00:06:15,340 úgy dönt, ó, te vagy a szám egy, akkor ide tartozik. 146 00:06:15,340 --> 00:06:16,970 Ó, milyen jó szerencse. 147 00:06:16,970 --> 00:06:17,740 >> Te vagy a kettes számú. 148 00:06:17,740 --> 00:06:19,030 Azt is ide tartozik. 149 00:06:19,030 --> 00:06:21,010 A hármas számú, még jobb, ide tartozol. 150 00:06:21,010 --> 00:06:25,210 Amint ez lesz a végén a lista, egy beszúrás sort a pszeudokódja 151 00:06:25,210 --> 00:06:28,010 hogy sétált szóban utoljára, ez kész. 152 00:06:28,010 --> 00:06:32,790 De kiválasztás sort, ezzel szemben, tartotta mit csinál? 153 00:06:32,790 --> 00:06:35,260 >> Folyamatosan megy a listában újra és újra és újra. 154 00:06:35,260 --> 00:06:39,160 Mivel a kulcs betekintést már csak ha már úgy nézett végig a 155 00:06:39,160 --> 00:06:42,500 A lista végén lehet biztos hogy az elem kiválasztott volt 156 00:06:42,500 --> 00:06:45,560 sőt a jelenleg legkisebb elem. 157 00:06:45,560 --> 00:06:48,920 Tehát ezek a különböző mentális modellek vége fel engedve néhány nagyon valós 158 00:06:48,920 --> 00:06:53,130 különbségek számunkra, valamint az ilyen elméleti aszimptotikus különbségeket. 159 00:06:53,130 --> 00:06:56,910 >> Szóval összefoglalva, akkor nagy O n négyzet, láttunk néhány olyan 160 00:06:56,910 --> 00:06:58,350 algoritmusok eddig. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Mi az az algoritmus, amely elmondható, hogy nagy O n? 163 00:07:02,870 --> 00:07:06,930 A legrosszabb esetben, hogy úgy lineáris lépések számát. 164 00:07:06,930 --> 00:07:07,810 >> OK, lineáris keresést. 165 00:07:07,810 --> 00:07:10,470 És a legrosszabb esetben, amikor a elem, amit keres, ha 166 00:07:10,470 --> 00:07:12,950 alkalmazása lineáris keresést? 167 00:07:12,950 --> 00:07:14,680 >> OK, a legrosszabb esetben, még csak nem is ott van. 168 00:07:14,680 --> 00:07:17,000 Vagy a második legrosszabb esetben ez egészen a végén, amely a 169 00:07:17,000 --> 00:07:18,880 plusz vagy mínusz egy lépésben a különbség. 170 00:07:18,880 --> 00:07:21,180 Így a végén a nap, azt mondhatjuk, hogy lineáris. 171 00:07:21,180 --> 00:07:23,910 Big O n lesz lineáris keresés mivel a legrosszabb esetben a 172 00:07:23,910 --> 00:07:26,610 elem még csak nem is ott, vagy ez egészen a végén. 173 00:07:26,610 --> 00:07:29,370 >> Nos, nagy O log n. 174 00:07:29,370 --> 00:07:32,760 Mi nem beszélünk nagy részletesen , de már láttam ilyet. 175 00:07:32,760 --> 00:07:36,840 Mi fut úgynevezett logaritmikus időt, a legrosszabb esetben? 176 00:07:36,840 --> 00:07:38,500 >> Igen, bináris keresés. 177 00:07:38,500 --> 00:07:42,930 És bináris keresés legrosszabb esetben lehet, hogy az elem valahol 178 00:07:42,930 --> 00:07:45,640 A közép-, vagy valahol belül a tömbben. 179 00:07:45,640 --> 00:07:48,040 De csak akkor találja meg, ha osztani a lista felét, az 180 00:07:48,040 --> 00:07:48,940 fél, fél, fél. 181 00:07:48,940 --> 00:07:50,200 És akkor íme, itt van. 182 00:07:50,200 --> 00:07:52,500 Vagy megint a legrosszabb esetben még csak nem is ott van. 183 00:07:52,500 --> 00:07:56,770 De nem tudod, hogy ez nincs amíg el nem éri a fajta, hogy az utolsó 184 00:07:56,770 --> 00:08:00,470 legalsó elemek felére és megfelezve és felére. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1. 186 00:08:01,400 --> 00:08:03,540 Így lehet nagy O 2, O 3 nagy. 187 00:08:03,540 --> 00:08:06,260 Amikor csak akar, csak egy állandó szám, Mi csak a fajta csak egyszerűsítése 188 00:08:06,260 --> 00:08:07,280 hogy olyan nagy O 1. 189 00:08:07,280 --> 00:08:10,440 Annak ellenére, hogy reálisan, hogy úgy 2 vagy akár 100 lépést, ha ez a 190 00:08:10,440 --> 00:08:13,680 konstans lépések számát, Csak mondjuk nagy O 1. 191 00:08:13,680 --> 00:08:15,930 Mi az az algoritmus, ami nagy O 1? 192 00:08:15,930 --> 00:08:18,350 >> KÖZÖNSÉG: Finding hosszát változó. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Megtalálni a hossza egy változó? 194 00:08:21,090 --> 00:08:23,870 >> Közönség: Nem, a hosszúság ha már rendezve. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Jó. 196 00:08:24,160 --> 00:08:27,850 OK, így a megállapítás a hossza valami ha a hossza, hogy valami, mint a 197 00:08:27,850 --> 00:08:30,020 tömb, tárolják néhány változó. 198 00:08:30,020 --> 00:08:33,380 Mert akkor csak olvasd el a változó, vagy nyomtassa ki a változó, vagy 199 00:08:33,380 --> 00:08:34,960 csak általában elérni az adott változó. 200 00:08:34,960 --> 00:08:37,299 És íme, hogy vesz konstans id. 201 00:08:37,299 --> 00:08:38,909 >> Ezzel szemben, gondolom, vissza a semmiből. 202 00:08:38,909 --> 00:08:42,460 Gondolj vissza az első héten a C, hívás csak printf és nyomtatás 203 00:08:42,460 --> 00:08:46,240 valamit a képernyőn, vitathatatlanul konstans időben, mert ez csak úgy 204 00:08:46,240 --> 00:08:50,880 bizonyos számú CPU mutatni ezt a szöveget a képernyőn. 205 00:08:50,880 --> 00:08:52,720 Vagy várj - nem igaz? 206 00:08:52,720 --> 00:08:56,430 Másképp hogyan tudnánk modellezni teljesítménye printf? 207 00:08:56,430 --> 00:09:00,420 Akar valaki szeretne egyet, hogy a talán nem is konstans id? 208 00:09:00,420 --> 00:09:03,600 Milyen értelemben lehet printf fut idő, tulajdonképpen nyomtatás a string 209 00:09:03,600 --> 00:09:05,580 a képernyőn, hogy valami nem állandó. 210 00:09:05,580 --> 00:09:07,860 >> Közönség: [hangtalan]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Igen. 212 00:09:08,230 --> 00:09:09,300 Tehát attól függ, hogy mi szempontunkból. 213 00:09:09,300 --> 00:09:13,390 Ha valóban úgy gondolja, a bemenet printf mint a húr, és 214 00:09:13,390 --> 00:09:16,380 ezért mérni a méretét, hogy a bemenet a hossza - így hívjuk 215 00:09:16,380 --> 00:09:17,780 hogy n hosszúságú is - 216 00:09:17,780 --> 00:09:21,990 vitathatóan, printf maga nagy O n mert fog tartani, N lépésben 217 00:09:21,990 --> 00:09:24,750 hogy nyomtassa ki minden egyes ilyen n karakterekből legvalószínűbb. 218 00:09:24,750 --> 00:09:27,730 Legalább olyan mértékben, hogy azt feltételezzük, hogy talán ez egy for ciklus 219 00:09:27,730 --> 00:09:28,560 a motorháztető alatt. 220 00:09:28,560 --> 00:09:30,860 >> De akkor meg kell nézni, hogy az kódot, hogy jobban megértsétek. 221 00:09:30,860 --> 00:09:33,650 És valóban, ha egyszer elkezd srácok elemezve a saját algoritmusokat, akkor 222 00:09:33,650 --> 00:09:34,900 szó szerint nem csak ezt. 223 00:09:34,900 --> 00:09:37,765 Valahogy szemgolyó a kódot, és gondolom, a - minden rendben, itt van ez loop 224 00:09:37,765 --> 00:09:41,870 itt, vagy van egy egymásba ágyazott hurkok itt, hogy fog csinálni a dolgokat n n-szer, 225 00:09:41,870 --> 00:09:46,050 és akkor valami okból az utat át a kódot, akkor is, ha ez 226 00:09:46,050 --> 00:09:47,980 pszeudokódját, és nem maga a kód. 227 00:09:47,980 --> 00:09:49,730 >> Szóval mi van omega n négyzete? 228 00:09:49,730 --> 00:09:53,582 Mi volt egy algoritmust, amely a legjobban esetben még csak n négyzeten lépések? 229 00:09:53,582 --> 00:09:54,014 Igen? 230 00:09:54,014 --> 00:09:54,880 >> Közönség: [hangtalan]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: Tehát kiválasztás sort. 232 00:09:55,900 --> 00:09:59,150 Mert, hogy a probléma valóban csökkent arra, hogy újra, nem tudom, 233 00:09:59,150 --> 00:10:02,600 Találtam a jelenlegi legkisebb, amíg Megnéztem az összes rohadt elemekkel. 234 00:10:02,600 --> 00:10:08,050 Tehát omega, mondjuk, n, akkor most jött egy. 235 00:10:08,050 --> 00:10:09,300 Beillesztése sort. 236 00:10:09,300 --> 00:10:12,370 Ha a lista történik rendezhető már, a legjobb esetben is csak 237 00:10:12,370 --> 00:10:15,090 hogy az egyik átmegy rajta, ekkor biztosak vagyunk benne. 238 00:10:15,090 --> 00:10:17,890 És akkor, hogy lehet mondani a lineáris, az biztos. 239 00:10:17,890 --> 00:10:20,570 >> Mi a helyzet omega 1? 240 00:10:20,570 --> 00:10:23,790 Mi a legjobb esetben, eltarthat állandó számú lépésben? 241 00:10:23,790 --> 00:10:27,220 Tehát lineáris keresés, ha csak szerencséd lesz és az elem, amit keresel 242 00:10:27,220 --> 00:10:31,000 igaza van a lista elején, ha ez az, ahol te kezdő 243 00:10:31,000 --> 00:10:33,070 lineáris bejárása a listán. 244 00:10:33,070 --> 00:10:35,180 >> És ez igaz a számú dolog. 245 00:10:35,180 --> 00:10:37,660 Például, akár bináris keresés omega 1. 246 00:10:37,660 --> 00:10:40,310 Mert mi van, ha igazán rohadt szerencsés és íz-DAB közepén 247 00:10:40,310 --> 00:10:42,950 A tömb a szám keres? 248 00:10:42,950 --> 00:10:45,730 Így szerencsés ott is. 249 00:10:45,730 --> 00:10:49,190 >> Ez végül omega n log n. 250 00:10:49,190 --> 00:10:52,573 Tehát n log n, akkor nem igazán beszélni még, de - 251 00:10:52,573 --> 00:10:53,300 >> Közönség: Merge sort? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: Merge sort. 253 00:10:53,960 --> 00:10:56,920 Ez volt az a Cliffhanger utoljára, ahol javasolta, és megmutattuk, 254 00:10:56,920 --> 00:10:58,600 vizuálisan, hogy vannak algoritmusok. 255 00:10:58,600 --> 00:11:02,470 És egyesíti a fajta csak egy ilyen algoritmus alapvetően gyorsabb 256 00:11:02,470 --> 00:11:03,450 mint néhány ilyen többiek. 257 00:11:03,450 --> 00:11:07,800 Tény, egyesítése rövidzárlat nemcsak a legjobb esetben n log n, a legrosszabb 258 00:11:07,800 --> 00:11:09,460 Az N log n. 259 00:11:09,460 --> 00:11:14,540 És ha ez a véletlen omega és a nagy O, hogy ugyanaz a dolog? 260 00:11:14,540 --> 00:11:17,310 Mi valóban leírni, hogy mivel mi nevű theta, bár ez a 261 00:11:17,310 --> 00:11:18,220 kevésbé gyakori. 262 00:11:18,220 --> 00:11:21,730 De ez csak azt jelenti, a két határt, ebben az esetben azonosak. 263 00:11:21,730 --> 00:11:25,770 >> Tehát merge sort, mit jelent ez a Tényleg szűkülnek le nekünk? 264 00:11:25,770 --> 00:11:27,000 Nos, emlékszem a motiváció. 265 00:11:27,000 --> 00:11:30,340 Hadd húzza fel egy animáció mi nem nézni utoljára. 266 00:11:30,340 --> 00:11:33,390 Ez az egy, ugyanaz a gondolat, de a ez egy kicsit nagyobb. 267 00:11:33,390 --> 00:11:36,160 És én megyek előre, és rámutatni először - már behelyezés sort a 268 00:11:36,160 --> 00:11:39,410 A bal felső sarokban, majd a kiválasztás sort, buborék sort, néhány más típusú - 269 00:11:39,410 --> 00:11:42,670 héj és gyorsan -, hogy nem beszéltünk szól, és halom és egyesíti sort. 270 00:11:42,670 --> 00:11:47,090 >> Így legalább próbáljuk összpontosítani a szemét az első három, a bal oldalon, majd a 271 00:11:47,090 --> 00:11:49,120 merge sort amikor rákattintok ez a zöld nyíl. 272 00:11:49,120 --> 00:11:51,900 De hagyom mindet futni, csak azért, hogy ad egyfajta sokszínűségének 273 00:11:51,900 --> 00:11:53,980 algoritmusok, hogy létezik a világon. 274 00:11:53,980 --> 00:11:56,180 Én hagyom, hogy ezt a futamot csak néhány másodpercig. 275 00:11:56,180 --> 00:11:59,640 És ha összpontosítani a szemed - válasszon egy algoritmus, összpontosítani, hogy csak egy 276 00:11:59,640 --> 00:12:02,970 másodperc - akkor kezdődik, hogy a minta, hogy ez megvalósítani. 277 00:12:02,970 --> 00:12:04,530 >> Merge sort, értesítés, kész. 278 00:12:04,530 --> 00:12:06,430 Heap sort, gyorsan sort, héj - 279 00:12:06,430 --> 00:12:09,480 így úgy tűnik, hogy bevezette a három legrosszabb algoritmusok a múlt héten. 280 00:12:09,480 --> 00:12:12,960 De jó, hogy itt vagyunk ma nézd meg merge sort, ami az egyik 281 00:12:12,960 --> 00:12:16,500 a legkönnyebben, hogy nézd meg, még de ez valószínűleg hajlik a fejében 282 00:12:16,500 --> 00:12:17,490 csak egy kicsit. 283 00:12:17,490 --> 00:12:21,130 Itt láthatjuk, hogy mennyi kiválasztás sort szar. 284 00:12:21,130 --> 00:12:24,600 >> De a másik oldala, hogy nagyon könnyen megvalósítható. 285 00:12:24,600 --> 00:12:28,160 És talán a P Set 3, ez az egyik, a algoritmusok úgy döntött, hogy végre 286 00:12:28,160 --> 00:12:28,960 A standard változat. 287 00:12:28,960 --> 00:12:30,970 Tökéletesen, teljesen korrekt. 288 00:12:30,970 --> 00:12:35,210 >> De ismétlem, az n lesz nagy, ha úgy dönt, hogy végre egy gyorsabb algoritmust 289 00:12:35,210 --> 00:12:39,020 mint merge sort, esély a nagyobb és nagyobb bemenet, a kódot csak 290 00:12:39,020 --> 00:12:39,800 majd, hogy gyorsabban fusson. 291 00:12:39,800 --> 00:12:41,090 Saját honlap fog jobban működnek. 292 00:12:41,090 --> 00:12:42,650 A felhasználók lesznek boldogabbak. 293 00:12:42,650 --> 00:12:45,280 És így van ez a hatás A tényleges adó 294 00:12:45,280 --> 00:12:47,350 nekünk mélyebb gondolat. 295 00:12:47,350 --> 00:12:49,990 >> Szóval vessünk egy pillantást, amit egyesíteni sort valójában szól. 296 00:12:49,990 --> 00:12:52,992 A jó dolog az, hogy egyesíti rendezés csak ez. 297 00:12:52,992 --> 00:12:56,300 Ez megint mi már az úgynevezett pszeudokódját, pszeudokódja lény 298 00:12:56,300 --> 00:12:57,720 Angol, mint a szintaxis. 299 00:12:57,720 --> 00:12:59,890 És az egyszerűséget az valami lenyűgöző. 300 00:12:59,890 --> 00:13:02,840 >> Szóval input n elemű - hogy csak azt jelenti, hogy itt egy sor. 301 00:13:02,840 --> 00:13:04,000 Van rajta n dolgokat benne. 302 00:13:04,000 --> 00:13:05,370 Ez minden, amit mondasz ott. 303 00:13:05,370 --> 00:13:07,560 >> Ha n kisebb, mint 2, vissza. 304 00:13:07,560 --> 00:13:08,640 Szóval ez csak a triviális. 305 00:13:08,640 --> 00:13:12,580 Ha n kisebb, mint 2, akkor nyilván ez 1 vagy 0, ebben az esetben a dolog 306 00:13:12,580 --> 00:13:14,780 már rendezett, vagy nem létező, így csak vissza. 307 00:13:14,780 --> 00:13:15,900 Nincs mit tenni. 308 00:13:15,900 --> 00:13:18,360 Szóval ez egy egyszerű eset, hogy összeszedi le. 309 00:13:18,360 --> 00:13:20,110 >> Else, van három lépésből áll. 310 00:13:20,110 --> 00:13:23,650 Rendezze a bal oldalán az elemek, sort a jobb fele az elemek, 311 00:13:23,650 --> 00:13:26,650 majd egyesíteni a rendezett felét. 312 00:13:26,650 --> 00:13:29,400 Ami érdekes az, hogy Én vagyok a fajta punting, igaz? 313 00:13:29,400 --> 00:13:32,300 Van egyfajta körkörös definíció ez az algoritmus. 314 00:13:32,300 --> 00:13:35,986 Milyen értelemben ez az algoritmus meghatározása kerek? 315 00:13:35,986 --> 00:13:37,850 >> Közönség: [hangtalan]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Igen, a rendezési algoritmus, annak két lépés "sort 317 00:13:41,670 --> 00:13:44,640 valami. "És, hogy felveti a kérdés, nos, mit fogok használni 318 00:13:44,640 --> 00:13:46,460 rendezni a bal felét és a jobb fele? 319 00:13:46,460 --> 00:13:49,600 És a szépség az, hogy annak ellenére, megint ez a pszichedelikus 320 00:13:49,600 --> 00:13:54,030 rész potenciálisan, akkor ugyanazt algoritmus rendezni a bal felét. 321 00:13:54,030 --> 00:13:54,700 >> De várjunk csak egy percet. 322 00:13:54,700 --> 00:13:57,070 Amikor mondták, hogy rendezze a bal oldalán, melyek a két 323 00:13:57,070 --> 00:13:58,240 lépés lesz a következő? 324 00:13:58,240 --> 00:14:00,550 Majd rendezni a bal fele a bal oldalán, a jobb 325 00:14:00,550 --> 00:14:01,420 a fele a bal felét. 326 00:14:01,420 --> 00:14:04,430 A fenébe, hogyan tudom rendezni a két fél, vagy negyed, most? 327 00:14:04,430 --> 00:14:05,260 >> De ez rendben van. 328 00:14:05,260 --> 00:14:07,830 Van egy rendezési algoritmust itt. 329 00:14:07,830 --> 00:14:10,660 És bár lehet, hogy aggódik a az első ez a fajta végtelen 330 00:14:10,660 --> 00:14:12,780 loop, ez egy ciklus, amely soha nem lesz a vége - ez lesz a 331 00:14:12,780 --> 00:14:15,770 ér véget, amikor mi történik? 332 00:14:15,770 --> 00:14:16,970 Miután n értéke kisebb, mint 2. 333 00:14:16,970 --> 00:14:19,180 Amely végül fog történni, mert ha folyamatosan felére és 334 00:14:19,180 --> 00:14:23,020 felére a felére következő részre, biztosan végül maga lesz a vége 335 00:14:23,020 --> 00:14:25,350 fel csak 1 vagy 0 elemeket. 336 00:14:25,350 --> 00:14:28,500 Ekkor ez az algoritmus azt mondja, hogy kész. 337 00:14:28,500 --> 00:14:31,020 >> Tehát az igazi varázslat ebben algoritmust úgy tűnik, hogy 338 00:14:31,020 --> 00:14:33,470 hogy a végső lépést, összevonása. 339 00:14:33,470 --> 00:14:37,190 Ez az egyszerű ötlet, csak két összefonódó dolog, hogy az, ami végül is lesz 340 00:14:37,190 --> 00:14:40,920 hogy lehetővé teszik számunkra, hogy rendezni egy sor, mondjuk nyolc elem. 341 00:14:40,920 --> 00:14:44,410 Szóval van még nyolc stressz labda fel Itt nyolc darab papír, és egy 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 amit kap, hogy. 344 00:14:46,140 --> 00:14:46,960 >> [Nevetés] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Ha tudnánk, hogy nyolc önkéntesek, és nézzük meg, ha tudjuk 346 00:14:48,970 --> 00:14:51,430 játszani ezt, így. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Számítástechnika egyre szórakoztató. 349 00:14:53,565 --> 00:14:54,320 Rendben van. 350 00:14:54,320 --> 00:14:57,770 Mi lenne, ha három, legnagyobb kezét oda. 351 00:14:57,770 --> 00:14:58,580 Négy hátul. 352 00:14:58,580 --> 00:15:02,220 És mi lenne, ha majd te három ebben a sorban? 353 00:15:02,220 --> 00:15:03,390 És négy az első. 354 00:15:03,390 --> 00:15:04,920 Szóval nyolc, gyere fel. 355 00:15:04,920 --> 00:15:12,060 >> [Nevetés] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: Én tényleg nem tudja, mi az. 357 00:15:13,450 --> 00:15:14,810 Ez a stressz labda? 358 00:15:14,810 --> 00:15:16,510 Az asztali lámpa? 359 00:15:16,510 --> 00:15:18,650 Az anyag? 360 00:15:18,650 --> 00:15:19,680 Az interneten? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Szóval, gyere fel. 363 00:15:21,310 --> 00:15:22,310 Ki szeretne - 364 00:15:22,310 --> 00:15:23,570 jönnek fel. 365 00:15:23,570 --> 00:15:24,240 Lássuk. 366 00:15:24,240 --> 00:15:26,460 És ez hozza meg a helyszínen - 367 00:15:26,460 --> 00:15:27,940 te egy helyre. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, várj egy percet. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - ó, jó. 370 00:15:30,760 --> 00:15:31,310 Rendben, rendben vagyunk. 371 00:15:31,310 --> 00:15:35,130 Rendben, mindenki helyet, de nem a Google Glass. 372 00:15:35,130 --> 00:15:36,475 Hadd sorban e fel. 373 00:15:36,475 --> 00:15:37,115 Mi a neve? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Rendben, hogy néz ki, mint A stréber, ha nem gond. 377 00:15:42,000 --> 00:15:44,625 Nos, én is, azt hiszem, csak egy pillanatra. 378 00:15:44,625 --> 00:15:45,875 Rendben, készenlét. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Próbáltuk, hogy dolgozzon ki egy használni az esetben a Google Glass, és 381 00:15:50,950 --> 00:15:53,750 gondoltam, hogy jó, hogy csak nem ezt, amikor az emberek a színpadon. 382 00:15:53,750 --> 00:15:57,120 Mi rögzíti a világot a saját szemszögéből. 383 00:15:57,120 --> 00:15:58,410 Rendben van. 384 00:15:58,410 --> 00:15:59,830 Nem talán, amit a Google szánták. 385 00:15:59,830 --> 00:16:02,260 Rendben, ha nem bánod visel ez a következő kínos perc 386 00:16:02,260 --> 00:16:03,150 hogy csodálatos lenne. 387 00:16:03,150 --> 00:16:08,620 >> Rendben, van itt egy sor elemeket, és hogy a tömb, mint egy a 388 00:16:08,620 --> 00:16:11,480 papírdarab ezek az emberek " kéz, jelenleg unsorted. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Ó, ez olyan furcsa. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: Elég sok véletlen. 391 00:16:12,810 --> 00:16:15,760 És csak egy pillanatra, fogunk próbálni végrehajtása egyesíteni sort össze 392 00:16:15,760 --> 00:16:17,950 és hol a kulcs meglátás. 393 00:16:17,950 --> 00:16:21,970 És a trükk itt merge sort is valamit, amit még nem vállalt még. 394 00:16:21,970 --> 00:16:24,030 Igazából kell egy kis további helyet. 395 00:16:24,030 --> 00:16:26,650 Tehát mi lesz különösen érdekes az, hogy ezek a 396 00:16:26,650 --> 00:16:29,270 srácok fognak mozogni egy kicsit kicsit, mert én fogom fel, hogy 397 00:16:29,270 --> 00:16:31,880 van egy extra sor a tér, mondani, ugye mögöttük. 398 00:16:31,880 --> 00:16:34,570 >> Tehát, ha ők mögött szék, ez a második tömb. 399 00:16:34,570 --> 00:16:36,960 Ha ők ülnek itt, ez az elsődleges tömb. 400 00:16:36,960 --> 00:16:40,170 De ez egy olyan erőforrás, hogy van nem tőkeáttételes eddig buborék 401 00:16:40,170 --> 00:16:42,040 sort, a kiválasztás sort, A behelyezés sort. 402 00:16:42,040 --> 00:16:44,600 Emlékezzünk a múlt héten, mindenki csak ilyen csoszogott a helyén. 403 00:16:44,600 --> 00:16:46,840 Nem használja a memóriát. 404 00:16:46,840 --> 00:16:49,310 Csináltunk helyet emberek mozgó emberek. 405 00:16:49,310 --> 00:16:50,580 >> Tehát ez egy fontos betekintést is. 406 00:16:50,580 --> 00:16:53,410 Van ez a trade-off, az általános számítástechnika, a források. 407 00:16:53,410 --> 00:16:55,800 Ha szeretné, hogy gyorsítsák fel valamit mint az idő, fogsz 408 00:16:55,800 --> 00:16:56,900 kell fizetni az árát. 409 00:16:56,900 --> 00:17:00,750 És az egyik ilyen árak gyakran hely, a memória vagy kemény 410 00:17:00,750 --> 00:17:01,700 lemezterület használ. 411 00:17:01,700 --> 00:17:03,640 Vagy, őszintén szólva, az összeg A programozó idő. 412 00:17:03,640 --> 00:17:06,700 Mennyi időt vesz igénybe, az ember, ténylegesen alkalmazni néhány 413 00:17:06,700 --> 00:17:07,829 bonyolult algoritmus. 414 00:17:07,829 --> 00:17:09,760 De ma, a trade-off az idő és a tér. 415 00:17:09,760 --> 00:17:11,930 >> Tehát, ha ti is csak tartsa be a számokat, így láthatjuk, hogy te 416 00:17:11,930 --> 00:17:15,839 Valóban megfelelő 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Kiváló. 418 00:17:16,599 --> 00:17:19,520 Úgyhogy megpróbálom hangszerel dolgok, ha ti csak 419 00:17:19,520 --> 00:17:21,800 kövess engem itt. 420 00:17:21,800 --> 00:17:26,650 >> Így fogok végrehajtani, először az első lépésében a pszeudokód, amely 421 00:17:26,650 --> 00:17:29,440 bemeneten n elemű, ha n kevesebb, mint 2, majd vissza. 422 00:17:29,440 --> 00:17:31,370 Nyilvánvaló, hogy ez nem vonatkoznak, így megyünk tovább. 423 00:17:31,370 --> 00:17:33,340 Így rendezni a bal fele az elemek. 424 00:17:33,340 --> 00:17:36,220 Ez azt jelenti, fogok összpontosítani a figyelmet egy pillanatra a következő 425 00:17:36,220 --> 00:17:37,310 négy srác itt. 426 00:17:37,310 --> 00:17:39,774 Rendben, mit tegyek a következő csinálni? 427 00:17:39,774 --> 00:17:40,570 >> Közönség: Rendezze a bal felét. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Tehát most már rendezni a bal fele ezek a srácok. 429 00:17:42,780 --> 00:17:45,580 Mert megint fel magadnak a célja, hogy rendezze a bal felét. 430 00:17:45,580 --> 00:17:46,440 Hogy csinálod ezt? 431 00:17:46,440 --> 00:17:49,140 Kövesse az utasításokat, sőt bár mi csináljuk újra. 432 00:17:49,140 --> 00:17:50,160 Így rendezni a bal felét. 433 00:17:50,160 --> 00:17:52,030 Most válogatás a két srác. 434 00:17:52,030 --> 00:17:53,563 Mi jön ezután? 435 00:17:53,563 --> 00:17:54,510 >> Közönség: Rendezze a bal felét. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: rendezés a bal felét. 437 00:17:55,460 --> 00:18:00,680 Tehát most ezek, ez a hely itt, egy lista az 1-es méretű. 438 00:18:00,680 --> 00:18:01,365 És mi a neved? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Princess Daisy itt. 441 00:18:03,690 --> 00:18:07,470 És ő már válogatott, mert a lista az 1-es méretű. 442 00:18:07,470 --> 00:18:09,490 Mit csinál a következő? 443 00:18:09,490 --> 00:18:13,680 OK, vissza, mert ez a lista a 1-es méret, ami kevesebb, mint 2. 444 00:18:13,680 --> 00:18:14,320 Akkor mi a következő lépés? 445 00:18:14,320 --> 00:18:17,490 És most meg kell, hogy milyen visszalép a fejedben. 446 00:18:17,490 --> 00:18:19,340 >> Rendezze a jobb fele, ami - 447 00:18:19,340 --> 00:18:19,570 mi a neve? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 És mit teszünk most, hogy van egy lista a méret 1? 451 00:18:23,210 --> 00:18:24,440 >> Közönség: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Óvatosan. 453 00:18:24,760 --> 00:18:29,540 Mi vissza először, és most a harmadik lépés - és ha valahogy ábrázolják azt 454 00:18:29,540 --> 00:18:33,490 felölelő két ülés most, most már kell egyesíteni ezt a két elemet. 455 00:18:33,490 --> 00:18:35,530 Tehát most sajnos az elemek ki a rend. 456 00:18:35,530 --> 00:18:39,920 De ez az, ahol az összefonódó folyamat kezd lenyűgöző. 457 00:18:39,920 --> 00:18:42,410 >> Tehát, ha ti is állni csak Egy pillanatra fogok szükségem van rád, egy 458 00:18:42,410 --> 00:18:44,170 Jelenleg lépéssel mögötte a széket. 459 00:18:44,170 --> 00:18:46,480 És ha Linda, mert 2 kisebb, mint 4, miért nem 460 00:18:46,480 --> 00:18:48,130 jössz körül az első? 461 00:18:48,130 --> 00:18:48,690 Maradj ott. 462 00:18:48,690 --> 00:18:50,520 Szóval Linda, akkor magához tér az első. 463 00:18:50,520 --> 00:18:53,820 >> Most, a valóságban, ha ez csak egy tömb tudtuk csak mozgatni a valós időben 464 00:18:53,820 --> 00:18:55,360 ebből a székből, hogy ezen a helyen. 465 00:18:55,360 --> 00:18:57,770 Így elképzelhető, hogy volt néhány állandó lépések száma 1. 466 00:18:57,770 --> 00:18:58,480 És most - 467 00:18:58,480 --> 00:19:01,490 de meg kell, hogy tegye meg a Az első hely itt. 468 00:19:01,490 --> 00:19:03,930 >> És most, ha tudnál jönni körül, is, fogunk 469 00:19:03,930 --> 00:19:06,300 legyen hely két. 470 00:19:06,300 --> 00:19:09,120 És bár ez olyan, mintha egy darabig, mi szép most 471 00:19:09,120 --> 00:19:14,710 hogy a bal fele a bal fele ma már rendezve. 472 00:19:14,710 --> 00:19:18,010 Tehát mi volt a következő lépés, ha most hátra tovább a történet? 473 00:19:18,010 --> 00:19:18,980 >> Közönség: jobb felét. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: rendezés a jobb felét. 475 00:19:19,900 --> 00:19:21,320 Szóval srácok ezt is. 476 00:19:21,320 --> 00:19:23,510 Tehát, ha meg tudná állni egy pillanatra? 477 00:19:23,510 --> 00:19:25,192 És mi a neve? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, így Jess most a bal felét a jobb felét. 481 00:19:29,720 --> 00:19:31,400 És ő a lista 1-es méretű. 482 00:19:31,400 --> 00:19:32,380 Ő nyilvánvalóan rendezve. 483 00:19:32,380 --> 00:19:33,070 És a neve? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle nyilvánvalóan egy listát a 1-es méretű. 486 00:19:35,340 --> 00:19:36,050 Már így is rendezve. 487 00:19:36,050 --> 00:19:38,690 Tehát most a varázslat történik, az egyesülő folyamat. 488 00:19:38,690 --> 00:19:39,790 Szóval, ki fog jönni az első? 489 00:19:39,790 --> 00:19:41,560 Nyilvánvalóan Michelle. 490 00:19:41,560 --> 00:19:43,280 Tehát, ha meg tudná magához tér vissza. 491 00:19:43,280 --> 00:19:47,090 A tér már elérhető neki most igaza van e mögött székét. 492 00:19:47,090 --> 00:19:51,580 És most, ha tudna jönni vissza is, most már, hogy világos legyen, két 493 00:19:51,580 --> 00:19:53,810 fele, egyenként 2-es méret - 494 00:19:53,810 --> 00:19:57,090 és csak az ábrázolás kedvéért, ha lehet, hogy egy kicsit a tér - 495 00:19:57,090 --> 00:19:59,780 Egy bal fele itt, egy jobb felét itt. 496 00:19:59,780 --> 00:20:01,160 >> Rewind tovább a történet. 497 00:20:01,160 --> 00:20:02,270 Mi a következő lépés? 498 00:20:02,270 --> 00:20:03,030 >> Közönség: Merge. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Tehát most már össze kell fésülni. 500 00:20:04,160 --> 00:20:07,490 Tehát OK, így most, szerencsére, akkor csak felszabadult négy szék. 501 00:20:07,490 --> 00:20:11,480 Ezért is használtam kétszer annyi memóriát, de adhatunk flip-flopra között 502 00:20:11,480 --> 00:20:12,330 A két tömb. 503 00:20:12,330 --> 00:20:14,190 Tehát melyik szám az első helyen? 504 00:20:14,190 --> 00:20:14,850 Tehát Michelle, nyilván. 505 00:20:14,850 --> 00:20:16,680 Így jár, és hogy itt a helyed. 506 00:20:16,680 --> 00:20:19,120 És akkor 2-es szám nyilvánvalóan következő, így jön ide. 507 00:20:19,120 --> 00:20:21,520 4. szám, 6-os szám. 508 00:20:21,520 --> 00:20:23,390 És ismét, bár van egy kis séta szó, 509 00:20:23,390 --> 00:20:26,010 Tényleg ezek megtörténhet azonnal, mozgatásával egy - 510 00:20:26,010 --> 00:20:26,880 OK, jól játszott. 511 00:20:26,880 --> 00:20:28,350 >> [Nevetés] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: És most mi vagyunk elég jó formában. 513 00:20:29,680 --> 00:20:34,910 A bal fele a teljes input most rendezve. 514 00:20:34,910 --> 00:20:37,370 Rendben, ezek a srácok voltak az az előnye, az én - 515 00:20:37,370 --> 00:20:40,340 hogyan csinálta a végén a lányok a balra, és a fiúk a jobb? 516 00:20:40,340 --> 00:20:42,450 >> OK, így fiúk viszont most. 517 00:20:42,450 --> 00:20:44,680 Tehát nem fogok járni végig ezeket a lépéseket. 518 00:20:44,680 --> 00:20:46,550 Meglátjuk, ha tudjuk újra ugyanaz pszeudokódja. 519 00:20:46,550 --> 00:20:50,050 Ha azt szeretné, hogy menjen előre, és felállni, és ti, hadd adjak a mikrofont. 520 00:20:50,050 --> 00:20:52,990 Nézd meg, hogy nem tudja megismételni, amit Csak nem itt a 521 00:20:52,990 --> 00:20:53,880 másik végét a listából. 522 00:20:53,880 --> 00:20:59,530 Kinek kell beszélni az első, alapján az algoritmus? 523 00:20:59,530 --> 00:21:03,210 Szóval, elmagyarázni, hogy mit csinálsz, mielőtt bármit láb mozgását. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Rendben, mert Én vagyok a bal fele a 525 00:21:05,930 --> 00:21:07,790 bal fele, visszatérek. 526 00:21:07,790 --> 00:21:08,730 Nem igaz? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Jó. 528 00:21:09,250 --> 00:21:10,350 >> SPEAKER 1: És akkor - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Ki a mikrofon megy tovább? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: Következő szám. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Szóval én vagyok a jobb felét a bal fele a 532 00:21:14,720 --> 00:21:17,830 bal fele, és én vissza. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Jó. 534 00:21:18,050 --> 00:21:18,550 Visszatér. 535 00:21:18,550 --> 00:21:21,855 Akkor most mi lesz a következő az Ön számára két? 536 00:21:21,855 --> 00:21:23,740 >> Hangszóró 2: Azt akarjuk látni, ki kisebb. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Pontosan. 538 00:21:24,200 --> 00:21:24,940 Azt akarjuk, hogy egyesíteni. 539 00:21:24,940 --> 00:21:27,590 A tér fogunk használni, hogy egyesíteni került, annak ellenére, hogy 540 00:21:27,590 --> 00:21:30,250 nyilvánvalóan sorrendje már, megyünk hogy ugyanezt az algoritmust. 541 00:21:30,250 --> 00:21:31,560 Tehát, aki megy vissza az első? 542 00:21:31,560 --> 00:21:35,720 Így 3, majd 7. 543 00:21:35,720 --> 00:21:38,570 És most a mikrofon megy hogy ezek a srácok, oké? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Szóval én vagyok a jobb felét a bal fele, és az én n kisebb, mint 545 00:21:43,590 --> 00:21:45,048 1, úgyhogy csak átutazóban - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Jó. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: én vagyok a jobb felét a jobb felét a jobb fele, és én vagyok 548 00:21:49,450 --> 00:21:51,740 is egy ember, úgyhogy majd vissza. 549 00:21:51,740 --> 00:21:52,990 Szóval most mi egyesítése. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPEAKER 3: Szóval vissza. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Szóval megy vissza. 553 00:21:57,160 --> 00:21:59,200 Tehát 5 megy először, majd a 8. 554 00:21:59,200 --> 00:22:01,240 És most közönség, amely a lépésre meg kell teremteni a visszatekerés 555 00:22:01,240 --> 00:22:02,200 vissza, hogy a fejekben? 556 00:22:02,200 --> 00:22:02,940 >> Közönség: Merge. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: egyesítése bal oldalán és a jobb a fele az eredeti bal felét. 558 00:22:07,270 --> 00:22:08,840 Tehát most - 559 00:22:08,840 --> 00:22:10,520 és csak azért, hogy ez világos, hogy egy kis helyet 560 00:22:10,520 --> 00:22:11,690 köztetek srácok. 561 00:22:11,690 --> 00:22:13,800 Tehát most, hogy ez a két listát, balra és jobbra. 562 00:22:13,800 --> 00:22:18,320 Szóval hogyan most egyesíteni titeket a Az első üléssor megint? 563 00:22:18,320 --> 00:22:19,600 >> 3. kezd. 564 00:22:19,600 --> 00:22:20,850 Ezután 5 nyilván. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Ezután 7, és most 8. 567 00:22:27,330 --> 00:22:28,710 OK, és most már? 568 00:22:28,710 --> 00:22:29,650 >> Közönség: Nem történik. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: nem történik meg, mert a Nyilvánvaló, hogy ez egy lépés van hátra. 570 00:22:32,440 --> 00:22:35,720 De ismétlem, azért én ezzel a zsargon, mint a "hátra a fejedben," 571 00:22:35,720 --> 00:22:37,160 azért, mert ez tényleg mi történik. 572 00:22:37,160 --> 00:22:39,610 Megyünk végig ezeket a lépéseket, de mi valami megállt egy 573 00:22:39,610 --> 00:22:42,480 pillanat, búvárkodás mélyebbre algoritmus, megállt egy pillanatra, 574 00:22:42,480 --> 00:22:45,840 Mélyebben az algoritmus, és most már rendezni a visszatekerés a mi 575 00:22:45,840 --> 00:22:49,430 elmék és visszavonás mindezen rétegek hogy már egyfajta tartásba kerül. 576 00:22:49,430 --> 00:22:51,790 >> Tehát most már két listát 4-es méret. 577 00:22:51,790 --> 00:22:54,790 Ha ti is állni utoljára és egy kis hely itt 578 00:22:54,790 --> 00:22:57,230 egyértelművé teszi, hogy ez a bal a fele az eredeti, a 579 00:22:57,230 --> 00:22:58,620 jobb felére. 580 00:22:58,620 --> 00:23:01,060 Ki volt az első szám, amit kell húzni a hátsó? 581 00:23:01,060 --> 00:23:01,870 Michelle, természetesen. 582 00:23:01,870 --> 00:23:03,230 >> Tehát fel Michelle itt. 583 00:23:03,230 --> 00:23:05,080 És aki a 2? 584 00:23:05,080 --> 00:23:06,440 2. szám jön vissza is. 585 00:23:06,440 --> 00:23:07,800 3. szám? 586 00:23:07,800 --> 00:23:08,510 Kiváló. 587 00:23:08,510 --> 00:23:16,570 4. szám, 5-ös, 6-os, 7-es és a 8-as szám. 588 00:23:16,570 --> 00:23:18,850 >> OK, így úgy éreztem, mint sok lépések, az biztos. 589 00:23:18,850 --> 00:23:22,390 De most nézzük meg, ha nem tudjuk megerősíteni fajta ösztönösen, hogy ez a 590 00:23:22,390 --> 00:23:26,190 algoritmus alapvetően, különösen n lesz nagyon nagy, ahogy láttam 591 00:23:26,190 --> 00:23:29,170 A animációk, a alapvetően gyorsabb. 592 00:23:29,170 --> 00:23:33,400 Tehát azt állítom, ez az algoritmus, a legrosszabb eset, és még a legjobb esetben, 593 00:23:33,400 --> 00:23:36,160 nagy O n log n-szer. 594 00:23:36,160 --> 00:23:39,160 Vagyis, van néhány szempont a algoritmus vesz n lépéseket, de 595 00:23:39,160 --> 00:23:43,110 van egy másik szempont valahol hogy ismétlés, hogy a hurok, hogy 596 00:23:43,110 --> 00:23:44,410 vesz log n lépésben. 597 00:23:44,410 --> 00:23:49,154 Lehet tesszük ujját, hogy mi az két szám utal? 598 00:23:49,154 --> 00:23:51,320 Nos, hol - 599 00:23:51,320 --> 00:23:54,160 Hol a mikrofon el? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: Vajon a log n törés minket két - 601 00:23:58,660 --> 00:23:59,630 elosztjuk két, lényegében. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Pontosan. 603 00:24:00,120 --> 00:24:03,000 Bármikor látjuk minden algoritmus tehát messze van már ez a minta 604 00:24:03,000 --> 00:24:04,200 elválasztó, elválasztó, osztódását. 605 00:24:04,200 --> 00:24:05,700 És ez általában csökken valami, ami 606 00:24:05,700 --> 00:24:07,100 logaritmikus, log alap 2. 607 00:24:07,100 --> 00:24:10,180 De tényleg bármi lehet, de log alap 2. 608 00:24:10,180 --> 00:24:11,330 >> Mi a helyzet a n? 609 00:24:11,330 --> 00:24:14,550 Látom, hogy milyen osztott meg srácok - osztott meg, osztott meg, 610 00:24:14,550 --> 00:24:15,910 osztott meg, osztott meg. 611 00:24:15,910 --> 00:24:18,760 Hol a végén származik? 612 00:24:18,760 --> 00:24:19,810 >> Tehát ez az összevonása. 613 00:24:19,810 --> 00:24:20,610 Mert gondolni. 614 00:24:20,610 --> 00:24:25,420 Ha egyesíteni nyolc embereket, amelynek a fele egy olyan négy 615 00:24:25,420 --> 00:24:27,770 és a másik felét egy másik meg négy, hogyan megy 616 00:24:27,770 --> 00:24:28,820 csinál az egyesülő? 617 00:24:28,820 --> 00:24:30,830 Nos, srácok tette meglehetősen intuitív. 618 00:24:30,830 --> 00:24:34,140 >> De ha inkább nem, hogy egy kicsit módszeresen, talán már rámutatott 619 00:24:34,140 --> 00:24:38,090 a bal szélső személy először az én bal Ugyanakkor rámutatott a bal szélső ember 620 00:24:38,090 --> 00:24:42,080 Az, hogy a fele az én jobb kezemben, és a csak később ment át a 621 00:24:42,080 --> 00:24:46,990 lista, mutatva a legkisebb elem minden egyes alkalommal, mozog az ujját, és 622 00:24:46,990 --> 00:24:48,970 mint ahogy szükség az egész listát. 623 00:24:48,970 --> 00:24:51,890 De mi a kulcs ebben összevonása folyamat Én összevetjük a pár 624 00:24:51,890 --> 00:24:53,460 elemek. 625 00:24:53,460 --> 00:24:57,270 A jobb felét, és a bal oldali fél, én egyszer sem visszalépés. 626 00:24:57,270 --> 00:25:00,570 >> Tehát az egyesítés is vesz nem több, mint n lépésben. 627 00:25:00,570 --> 00:25:03,250 És hányszor volt már erre összevonása? 628 00:25:03,250 --> 00:25:07,150 Nos, nem több, mint n, és mi csak látta, hogy a végső egyesítés. 629 00:25:07,150 --> 00:25:13,120 És ha valami, hogy úgy log n lépésben n-szer, vagy fordítva, 630 00:25:13,120 --> 00:25:15,210 ez meg fog adni nekünk n log n-szer. 631 00:25:15,210 --> 00:25:16,310 >> És miért van ez jobb? 632 00:25:16,310 --> 00:25:19,600 Nos, ha már tudjuk, hogy log n jobb, mint n - igaz? 633 00:25:19,600 --> 00:25:22,590 Láttuk bináris keresés a telefonkönyvben Például log n határozottan 634 00:25:22,590 --> 00:25:23,760 jobb, mint a lineáris. 635 00:25:23,760 --> 00:25:28,420 Ez azt jelenti, n-szer log n határozottan jobb, mint n-szer egy másik 636 00:25:28,420 --> 00:25:30,390 N, N AKA négyzeten. 637 00:25:30,390 --> 00:25:32,400 És ez az, amit végül is érezni. 638 00:25:32,400 --> 00:25:34,928 >> Olyan nagy tapsot, ha tudnánk, mert ezek a srácok. 639 00:25:34,928 --> 00:25:38,920 >> [Taps] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: És az elválás ajándékok - lehet tartani a számokat, 641 00:25:41,550 --> 00:25:44,010 ha szeretné. 642 00:25:44,010 --> 00:25:45,620 És az elválás ajándék, mint mindig. 643 00:25:45,620 --> 00:25:47,290 Ja, és mi elküldjük Önnek a felvételeket, Michelle. 644 00:25:47,290 --> 00:25:48,343 Köszönöm. 645 00:25:48,343 --> 00:25:49,250 Rendben van. 646 00:25:49,250 --> 00:25:50,400 Segíts magadon, hogy a stressz labdát. 647 00:25:50,400 --> 00:25:54,110 >> És hadd húzza fel, az időközben barátunk Rob Bowden nyújt 648 00:25:54,110 --> 00:25:59,520 némileg más szemszögből e, mert akkor gondol ezekről 649 00:25:59,520 --> 00:26:01,280 lépés történik egy kissé más módon. 650 00:26:01,280 --> 00:26:04,750 Tény, hogy a set-up, amit Rob van szó hogy megmutassa azt feltételezi, hogy már 651 00:26:04,750 --> 00:26:09,030 már megtette a felosztva a nagy listát nyolc kis lista, 652 00:26:09,030 --> 00:26:10,570 minden 1-es méretű. 653 00:26:10,570 --> 00:26:13,350 >> Szóval változó pszeudokód a kicsit csak rendezni a kap a 654 00:26:13,350 --> 00:26:15,320 központi gondolata, hogy az egyesülő működik. 655 00:26:15,320 --> 00:26:17,600 De az üzemidő, amit mindjárt nem is mindig 656 00:26:17,600 --> 00:26:19,110 lesz ugyanaz. 657 00:26:19,110 --> 00:26:23,540 És ismét, a set-up az, hogy ő kezdődött nyolc listáját méret 1. 658 00:26:23,540 --> 00:26:27,730 Szóval hiányzott az a része, ahol ő ténylegesen elvégzett log n log n log n 659 00:26:27,730 --> 00:26:31,205 elosztjuk a bemeneti. 660 00:26:31,205 --> 00:26:32,120 >> [VIDEÓ LEJÁTSZÁS] 661 00:26:32,120 --> 00:26:33,615 >> -Ez az a lépés. 662 00:26:33,615 --> 00:26:38,270 A második lépés, többször merge pár listák. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Csak a hang jön ki a számítógépet. 665 00:26:41,270 --> 00:26:42,520 Próbáljuk meg újra. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Csak önkényesen felvenni, amely - most már négy lista. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Tanulj előtt. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Tessék. 671 00:26:53,040 --> 00:27:00,510 >> -Összevonása 108. és 15, akkor a végén fel a lista 15., 108.. 672 00:27:00,510 --> 00:27:07,170 Egyesítése és 4. 50, mi a végén a 4, 50. 673 00:27:07,170 --> 00:27:12,990 Összevonása 8 és 42, akkor a végén a 8., 42.. 674 00:27:12,990 --> 00:27:19,970 És összevonással 23 és 16, akkor a végén a 16., 23.. 675 00:27:19,970 --> 00:27:23,270 >> Most minden listák a 2-es méret. 676 00:27:23,270 --> 00:27:26,690 Figyeljük meg, hogy az egyes négy lista van rendezve. 677 00:27:26,690 --> 00:27:29,450 Tehát lehet kezdeni összevonása pár listák újra. 678 00:27:29,450 --> 00:27:38,420 15 egyesítése és 108., valamint a 4. és 50, mi előbb a 4., majd a 15, majd a 679 00:27:38,420 --> 00:27:41,500 Az 50, akkor a 108. 680 00:27:41,500 --> 00:27:50,610 Összevonása 8., 42. és 16., 23., először vegye a 8, akkor a 16, akkor a 23, 681 00:27:50,610 --> 00:27:52,700 akkor a 42. 682 00:27:52,700 --> 00:27:57,600 >> Így most már csak két lista mérete 4, amelyek mindegyike rendezve. 683 00:27:57,600 --> 00:28:01,170 Tehát most már eleget a két listát. 684 00:28:01,170 --> 00:28:11,835 Először is, hogy a 4, akkor tegye meg a 8, akkor vesszük a 15, majd 16, majd 685 00:28:11,835 --> 00:28:19,456 23, majd 42, majd 50, majd 108. 686 00:28:19,456 --> 00:28:19,872 >> [END VIDEÓ LEJÁTSZÁS] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Megint értesítés, soha nem megérintette adott pohár több mint egyszer 688 00:28:23,430 --> 00:28:24,860 miután előre túl. 689 00:28:24,860 --> 00:28:26,200 Tehát soha nem ismétlődő. 690 00:28:26,200 --> 00:28:29,850 Szóval ő mindig mozog oldalra, és ez az, ahol megvan a n. 691 00:28:29,850 --> 00:28:33,290 >> Miért nem engedi, hogy húzza fel egy animáció hogy láttuk korábban, de ezúttal 692 00:28:33,290 --> 00:28:35,110 koncentrálva csak merge sort. 693 00:28:35,110 --> 00:28:38,030 Hadd menjek előre, és nagyítás az ezen a itt. 694 00:28:38,030 --> 00:28:42,530 Először is hadd válasszon egy véletlen bemenet, magasztalja ezt, és akkor valahogy látni 695 00:28:42,530 --> 00:28:46,600 amit biztosra vett, korábban, merge sort valójában csinál. 696 00:28:46,600 --> 00:28:50,330 >> Így veszi észre, hogy lehet ezeket a fél, illetve ezek a negyedek, vagy ezeket a nyolcad 697 00:28:50,330 --> 00:28:53,140 probléma, hogy hirtelen kezd, hogy jó formában. 698 00:28:53,140 --> 00:28:57,070 És végül, látod a a legvégén, hogy a BAM, 699 00:28:57,070 --> 00:28:58,860 minden összefűzve. 700 00:28:58,860 --> 00:29:01,690 >> Tehát ezek csak három különböző veszi fel ugyanezt a gondolatot. 701 00:29:01,690 --> 00:29:05,980 De a legfontosabb betekintést, mint szakadék és meghódítani az első osztályú, 702 00:29:05,980 --> 00:29:10,640 az volt, hogy úgy döntöttünk, hogy valahogy osztani A probléma valami nagy, a 703 00:29:10,640 --> 00:29:14,760 valami fajta azonos szellemben, de kisebb és kisebb és kisebb 704 00:29:14,760 --> 00:29:15,660 és kisebb. 705 00:29:15,660 --> 00:29:18,420 >> Most másik módját valahogy gondolni ezekről, annak ellenére, hogy nem 706 00:29:18,420 --> 00:29:20,520 fog adni ugyanazt intuitív megértés, az 707 00:29:20,520 --> 00:29:21,640 az alábbi animáció. 708 00:29:21,640 --> 00:29:25,400 Tehát ez egy videót valaki össze hogy a kapcsolódó különböző 709 00:29:25,400 --> 00:29:29,970 hangokat a különböző műveletek beszúrás sort, a merge sort, és 710 00:29:29,970 --> 00:29:31,150 egy pár mások. 711 00:29:31,150 --> 00:29:32,330 Így egy pillanat, megyek hit játszani. 712 00:29:32,330 --> 00:29:33,600 Arról van szó, egy perc hosszú. 713 00:29:33,600 --> 00:29:37,410 És bár még mindig látni a minták történik, ez alkalommal is 714 00:29:37,410 --> 00:29:41,420 azt is hallani, hogy ezek algoritmusok végző másképp és 715 00:29:41,420 --> 00:29:43,950 némileg különböző mintákat. 716 00:29:43,950 --> 00:29:45,830 >> Ez a beillesztés fajta. 717 00:29:45,830 --> 00:29:50,400 >> [HANGOK Playing] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Ismét megpróbálja beilleszteni egyes elemek 719 00:29:52,400 --> 00:29:52,900 bele, ahová tartozik. 720 00:29:52,900 --> 00:29:54,628 Ez a fajta buborék. 721 00:29:54,628 --> 00:30:10,097 >> [HANGOK Playing] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN És akkor valami érzést hogy viszonylag kevés munka csinál 723 00:30:13,630 --> 00:30:15,834 minden egyes lépést. 724 00:30:15,834 --> 00:30:20,470 Ez az, amit unalom hangzik. 725 00:30:20,470 --> 00:30:21,472 >> [HANGOK Playing] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Ez a szelekció sort, ahol válassza ki az elemet szeretnénk a 727 00:30:25,222 --> 00:30:28,845 megy keresztül, újra és újra és újra és üzembe azt az elején. 728 00:30:28,845 --> 00:30:37,674 >> [HANGOK Playing] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Ez merge sort, amely akkor tényleg elkezd érezni. 730 00:30:43,970 --> 00:30:51,810 >> [HANGOK Playing] 731 00:30:51,810 --> 00:30:54,770 >> [Nevetés] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Valami úgynevezett gnome sort, amit nem nézett. 733 00:30:58,395 --> 00:31:13,630 >> [HANGOK Playing] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Tehát lássuk csak, most, zavart, ahogy remélhetőleg a 735 00:31:17,910 --> 00:31:21,110 zene, ha tudok csúszik egy kicsit kis matek itt. 736 00:31:21,110 --> 00:31:24,850 Tehát van egy negyedik módszer is, hogy tudjuk gondolni, mit jelent ezeknek 737 00:31:24,850 --> 00:31:29,210 funkciók, hogy gyorsabb, mint azok hogy már látott. 738 00:31:29,210 --> 00:31:32,470 És ha jön a kurzust a matematika háttérben, akkor 739 00:31:32,470 --> 00:31:36,030 valójában talán már tudják, hogy pofon a távon ez a technika - 740 00:31:36,030 --> 00:31:40,400 nevezetesen rekurzió, a függvény valahogy nevezi magát. 741 00:31:40,400 --> 00:31:44,780 >> És ismét, emlékeztetni arra, hogy merge sort pszeudokódját volt rekurzív abban az értelemben, 742 00:31:44,780 --> 00:31:48,460 hogy az egyik merge sort lépteit volt, hogy hívja sort - 743 00:31:48,460 --> 00:31:49,740 hogy van, maga is. 744 00:31:49,740 --> 00:31:52,480 De szerencsére, mert folyamatosan hívás sort, vagy összeolvad sort, 745 00:31:52,480 --> 00:31:55,880 Konkrétabban, egy kisebb és kisebb és kisebb listát, hogy végül 746 00:31:55,880 --> 00:32:00,005 mélypontját köszönhetően mit fogunk hívni alapesetben a beégetett esetben, 747 00:32:00,005 --> 00:32:04,270 azt mondta, ha a lista kicsi, kevesebb, mint 2 Ebben az esetben csak vissza azonnal. 748 00:32:04,270 --> 00:32:07,550 Ha nem volt, hogy a speciális esetben a algoritmus soha mélypontot, 749 00:32:07,550 --> 00:32:11,010 és akkor tényleg kap egy végtelen ciklusba igazán örökre. 750 00:32:11,010 --> 00:32:14,330 >> De tegyük fel, hogy mi volna a most is Egyes számok ezt újra, ahol n 751 00:32:14,330 --> 00:32:15,660 mint a méret a bemenet. 752 00:32:15,660 --> 00:32:18,680 És meg akartam kérdezni, mi a a teljes időt vesz részt 753 00:32:18,680 --> 00:32:19,800 futó merge sort? 754 00:32:19,800 --> 00:32:22,960 Vagy még általánosabban, mi költsége az időben? 755 00:32:22,960 --> 00:32:24,730 >> Nos, ez elég könnyen mérhető, hogy az. 756 00:32:24,730 --> 00:32:29,010 Ha n kisebb, mint 2, az idő részt A válogatás n eleme, 757 00:32:29,010 --> 00:32:30,480 ahol n értéke 2, 0.. 758 00:32:30,480 --> 00:32:31,410 Mert csak vissza. 759 00:32:31,410 --> 00:32:32,510 Nincs tennivaló. 760 00:32:32,510 --> 00:32:35,660 Most kétségtelenül, lehet, hogy egy-két lépést lépéseket, hogy kitaláljuk, az összeget a 761 00:32:35,660 --> 00:32:38,420 működik, de elég közel van ahhoz, hogy a 0 Én csak úgy nemet mondani a munka 762 00:32:38,420 --> 00:32:40,940 szükség, ha a lista olyan kicsi hogy érdektelen. 763 00:32:40,940 --> 00:32:42,580 >> De ez az eset érdekes. 764 00:32:42,580 --> 00:32:47,320 A rekurzív ügy az ága A pszeudokód azt mondta más, sort 765 00:32:47,320 --> 00:32:52,000 A bal oldalán, rendezni a megfelelő fele, összevonja a két fél. 766 00:32:52,000 --> 00:32:55,530 Most miért ez a kifejezés képviseli, hogy a terhére? 767 00:32:55,530 --> 00:32:58,690 Nos, T n csak azt jelenti, a ideje rendezni n eleme. 768 00:32:58,690 --> 00:33:03,070 És akkor a jobb oldali egyenlőségjel ott, a T n megosztott 769 00:33:03,070 --> 00:33:06,600 2-utal, hogy a költségek, mi? 770 00:33:06,600 --> 00:33:07,570 Válogatás a bal felét. 771 00:33:07,570 --> 00:33:10,990 A többi T n osztva 2 feltehetően utalva a költsége 772 00:33:10,990 --> 00:33:12,390 rendezni a jobb felét. 773 00:33:12,390 --> 00:33:14,590 >> És akkor a plusz n? 774 00:33:14,590 --> 00:33:15,420 Van az összevonása. 775 00:33:15,420 --> 00:33:19,120 Mert ha van két listát, az egyik size n több mint 2 és egy másik n méretű 776 00:33:19,120 --> 00:33:22,580 több mint 2, akkor lényegében megérinteni minden egyes ilyen elemek, mint Rob 777 00:33:22,580 --> 00:33:24,990 megérintette az egyes csészék, és csak ahogy mutatott az egyes 778 00:33:24,990 --> 00:33:26,310 önkéntesek a színpadon. 779 00:33:26,310 --> 00:33:28,790 Tehát n rovására összevonása. 780 00:33:28,790 --> 00:33:31,780 >> Most sajnos, ez a formula is maga rekurzív. 781 00:33:31,780 --> 00:33:36,390 Tehát, ha a kérdést, ha n, mondjuk, 16, ha van 16 ember a színpadon 782 00:33:36,390 --> 00:33:40,670 vagy 16 csésze a videó, hogy hány teljes lépést tart rendezni őket 783 00:33:40,670 --> 00:33:41,550 A merge sort? 784 00:33:41,550 --> 00:33:45,790 Ez valójában nem egy nyilvánvaló válasz, mert most meg kell rendezni az 785 00:33:45,790 --> 00:33:48,500 rekurzívan válaszolni ezt a képletet. 786 00:33:48,500 --> 00:33:51,190 >> De ez rendben van, mert hadd javaslatot , hogy mi a következő. 787 00:33:51,190 --> 00:33:56,670 Az idő részt rendezni 16 ember, vagy 16 csésze lesz képviselt 788 00:33:56,670 --> 00:33:58,020 általánosságban T 16. 789 00:33:58,020 --> 00:34:01,400 De ez egyenlő, szerint a korábbi formula, 2-szer annyi 790 00:34:01,400 --> 00:34:04,780 idő kell ahhoz, hogy rendezni 8 csésze és 16. 791 00:34:04,780 --> 00:34:08,590 És ismét, és 16 az idő, hogy egyesülnek, és a két T-szer 8 az 792 00:34:08,590 --> 00:34:10,790 ideje rendezni bal oldalán és a jobb felét. 793 00:34:10,790 --> 00:34:11,989 >> De ismétlem, ez nem elég. 794 00:34:11,989 --> 00:34:13,210 Meg kell merülni a mélyebb. 795 00:34:13,210 --> 00:34:16,409 Ez azt jelenti, meg kell válaszolni a kérdés, mi T 8? 796 00:34:16,409 --> 00:34:19,610 Hát T 8 mindössze 2 T-szor 4 plusz 8. 797 00:34:19,610 --> 00:34:20,520 Nos, mi T 4? 798 00:34:20,520 --> 00:34:23,780 T 4 csak 2-szer T 2 és 4. 799 00:34:23,780 --> 00:34:25,489 Nos, mi T 2? 800 00:34:25,489 --> 00:34:29,030 T 2 csak 2-szer T 1 és 2. 801 00:34:29,030 --> 00:34:31,940 >> És ismét, mi fajta egyre megragadt ebben a ciklusban. 802 00:34:31,940 --> 00:34:34,790 De arról, hogy elérje, hogy az úgynevezett alapeset. 803 00:34:34,790 --> 00:34:37,310 Mert mi a T 1, nem azt állítjuk? 804 00:34:37,310 --> 00:34:37,810 0-ra. 805 00:34:37,810 --> 00:34:39,730 Tehát most végre, akkor a munka hátra. 806 00:34:39,730 --> 00:34:44,290 >> Ha a T 1 0, én most menj vissza egyet sorban ennek az embernek itt, és én is 807 00:34:44,290 --> 00:34:46,330 plug in 0 T 1. 808 00:34:46,330 --> 00:34:51,770 Tehát ez azt jelenti, hogy egyenlő 2-szer nulla, más néven 0, plusz 2. 809 00:34:51,770 --> 00:34:53,739 És így, hogy az egész kifejezés 2 lehet. 810 00:34:53,739 --> 00:34:58,740 >> Most, ha veszek a T 2, melynek válasz 2, dugja be a középső sor, T 811 00:34:58,740 --> 00:35:02,740 4, hogy ad nekem 2-szer 2 és 4, így a 8. 812 00:35:02,740 --> 00:35:07,080 Ha majd dugja 8 a korábbi vonal, hogy ad nekem 2-szer 8, 16. 813 00:35:07,080 --> 00:35:12,470 És ha majd folytassa, hogy a 24, hozzátéve, a 16, végül kap egy 814 00:35:12,470 --> 00:35:13,820 értéke 64,. 815 00:35:13,820 --> 00:35:18,480 >> Most, hogy már önmagában egyfajta beszél semmit az n jelölést, a 816 00:35:18,480 --> 00:35:20,700 nagy O, az Omega, hogy már beszélt. 817 00:35:20,700 --> 00:35:24,890 De kiderül, hogy a 64 valóban 16, a méret a bemenet, 818 00:35:24,890 --> 00:35:27,110 log alap 2 16. 819 00:35:27,110 --> 00:35:30,200 És ha ez egy kicsit szokatlan, csak gondoljon vissza, és akkor gyere vissza 820 00:35:30,200 --> 00:35:30,700 hogy akkor végül. 821 00:35:30,700 --> 00:35:33,775 Ha ez log 2-es alapú, ez olyan, mint 2 emelt, amit ad 16? 822 00:35:33,775 --> 00:35:36,380 Ó, ez 4, így 16-szor 4. 823 00:35:36,380 --> 00:35:39,380 >> És ismét, ez nem egy nagy dolog, ha ez egyfajta ködös emlék már. 824 00:35:39,380 --> 00:35:43,720 De most, hogy a hit hogy 16 log 16 64. 825 00:35:43,720 --> 00:35:46,590 És így valóban, ezzel az egyszerű józan ész ellenőrizze, már megerősített - 826 00:35:46,590 --> 00:35:48,250 de nem bizonyult formálisan - 827 00:35:48,250 --> 00:35:52,800 hogy a futási ideje egyesítése sort valóban n log n. 828 00:35:52,800 --> 00:35:53,790 >> Tehát nem rossz. 829 00:35:53,790 --> 00:35:57,260 Tuti, hogy jobb, mint a algoritmusok láttunk eddig, és 830 00:35:57,260 --> 00:36:00,710 ez azért van, mert megmutatta, egy, nevezett technikával rekurziót. 831 00:36:00,710 --> 00:36:03,880 De sokkal érdekesebb, mint az, hogy a fogalma osztódó és hódító. 832 00:36:03,880 --> 00:36:07,460 Ismét igazán 0. hét dolog, hogy még most is visszatérő a 833 00:36:07,460 --> 00:36:08,740 vonzóbb módon. 834 00:36:08,740 --> 00:36:11,750 >> Most egy jó kis testmozgás, ha már soha nem csináltam - és valószínűleg 835 00:36:11,750 --> 00:36:14,660 nem lett volna, mert valami normális ember nem gondol erre. 836 00:36:14,660 --> 00:36:20,650 De ha elmegyek a google.com, és ha Szeretnék tanulni valamit 837 00:36:20,650 --> 00:36:22,356 rekurzió, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Nevetés] 840 00:36:29,058 --> 00:36:32,030 [Még több nevetés] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: rossz vicc lassan terjed. 842 00:36:33,385 --> 00:36:34,450 [Nevetés] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Csak abban az esetben, hogy ott van. 844 00:36:36,970 --> 00:36:38,710 Nem varázslat rosszul, és ott van a vicc. 845 00:36:38,710 --> 00:36:40,810 Rendben van. 846 00:36:40,810 --> 00:36:42,950 Magyarázd el, hogy az emberek mellett, ha nem egészen kattintott csak még. 847 00:36:42,950 --> 00:36:47,650 De rekurzió, általában arra utal, A folyamat egy függvény hívás 848 00:36:47,650 --> 00:36:51,430 maga, vagy még általánosabban, elosztjuk a probléma, valami, hogy lehet 849 00:36:51,430 --> 00:36:56,220 megoldani darabonként megoldásával azonos képviselő problémákat. 850 00:36:56,220 --> 00:36:58,400 >> Nos, a változás fogaskerekek csak egy pillanatra. 851 00:36:58,400 --> 00:37:00,840 Azt szeretném befejezni bizonyos cliffhangers, úgyhogy kezdjük beállítani 852 00:37:00,840 --> 00:37:05,870 a színpadon, néhány percig, egy nagyon egyszerű ötlet - 853 00:37:05,870 --> 00:37:07,620 hogy a csere két elem, nem igaz? 854 00:37:07,620 --> 00:37:10,040 Mindezek algoritmusok voltunk beszélt az elmúlt pár 855 00:37:10,040 --> 00:37:12,420 előadások is némi a fajta csere. 856 00:37:12,420 --> 00:37:14,630 Ma is láthatóvá kezd velük fel ki a szék és 857 00:37:14,630 --> 00:37:18,570 sétálni, de kódot, akkor azt csak hogy egy elem egy tömb 858 00:37:18,570 --> 00:37:20,370 és nyár, hogy egy másik. 859 00:37:20,370 --> 00:37:21,880 >> Szóval hogyan megy körülbelül ezt? 860 00:37:21,880 --> 00:37:24,850 Nos, hadd menjen előre, és írni gyors program itt. 861 00:37:24,850 --> 00:37:31,600 Én megyek előre, és nem ezt a következő. 862 00:37:31,600 --> 00:37:33,910 Nevezzük ezt - 863 00:37:33,910 --> 00:37:38,070 mit akarunk hívni ezt? 864 00:37:38,070 --> 00:37:38,650 >> Igazából nem. 865 00:37:38,650 --> 00:37:39,420 Hadd visszatekerés. 866 00:37:39,420 --> 00:37:41,220 Én nem akarom, hogy az Cliffhanger még. 867 00:37:41,220 --> 00:37:42,270 Ez rontja a móka. 868 00:37:42,270 --> 00:37:43,600 Csináljuk ezt helyette. 869 00:37:43,600 --> 00:37:47,430 >> Tegyük fel, hogy szeretnék írni egy kicsit programot, és hogy most magában a 870 00:37:47,430 --> 00:37:48,700 ötlete rekurzió. 871 00:37:48,700 --> 00:37:50,370 Valahogy van előtt magam ott. 872 00:37:50,370 --> 00:37:51,420 Megyek tegye a következőket. 873 00:37:51,420 --> 00:38:00,220 >> Először is, a gyors is a szabványos io.h, valamint egy include a cs50.h. 874 00:38:00,220 --> 00:38:03,200 Aztán megyek előre és kijelentik, int main érvénytelennek 875 00:38:03,200 --> 00:38:04,360 a szokásos módon. 876 00:38:04,360 --> 00:38:07,920 Rájöttem már misnamed a fájlt, így hadd hozzá. c kiterjesztés itt ilyen 877 00:38:07,920 --> 00:38:09,510 hogy tudjuk fordítani rendesen. 878 00:38:09,510 --> 00:38:10,970 Indítsa el ezt a funkciót. 879 00:38:10,970 --> 00:38:13,290 >> És a függvény akarok írni, elég Egyszerűen, az egyik, hogy kéri a 880 00:38:13,290 --> 00:38:16,210 felhasználó a számot, majd hozzáteszi fel minden szám között, hogy a 881 00:38:16,210 --> 00:38:19,920 szám, és azt mondják, 0-ra. 882 00:38:19,920 --> 00:38:22,510 Tehát először fogok menni előre és kijelentik, int n. 883 00:38:22,510 --> 00:38:24,760 Aztán másolni néhány kód már használják egy ideig. 884 00:38:24,760 --> 00:38:26,660 Amíg valami igaz. 885 00:38:26,660 --> 00:38:28,000 Jövök vissza, hogy egy pillanat alatt. 886 00:38:28,000 --> 00:38:29,010 >> Mit akarok? 887 00:38:29,010 --> 00:38:33,460 Azt akarom mondani printf pozitív egész kérem. 888 00:38:33,460 --> 00:38:36,130 És akkor fogok mondjuk n lesz kap int. 889 00:38:36,130 --> 00:38:38,800 Tehát még egyszer, néhány boilerplate kód hogy már korábban használt. 890 00:38:38,800 --> 00:38:40,810 És én fogom ezt míg n értéke 1-nél kisebb. 891 00:38:40,810 --> 00:38:44,120 Tehát ez biztosítja, hogy a felhasználó ad nekem egy pozitív egész szám. 892 00:38:44,120 --> 00:38:45,490 >> És most megyek és tegyük a következőket. 893 00:38:45,490 --> 00:38:51,020 Azt akarom, hogy összeadjuk a számok közötti és n és 1, illetve 0 és n, 894 00:38:51,020 --> 00:38:52,570 azzal egyenértékű, hogy a teljes összeget. 895 00:38:52,570 --> 00:38:55,100 Tehát a nagy szigma szimbólum hogy lehet felidézni. 896 00:38:55,100 --> 00:38:59,050 Így fogom, hogy ezt az első hívás függvény szigma nevű, 897 00:38:59,050 --> 00:39:06,030 halad n, aztán megyek mondjuk printf, a válasz ott van. 898 00:39:06,030 --> 00:39:08,180 >> Tehát röviden, kapok, és int a felhasználó elől. 899 00:39:08,180 --> 00:39:09,280 Azt biztosítja, hogy pozitív. 900 00:39:09,280 --> 00:39:12,700 Kijelentem, változó nevű válasz int típusú, és tárolja azt a visszatérő 901 00:39:12,700 --> 00:39:15,610 értéke sigma, átadva az n bemenet. 902 00:39:15,610 --> 00:39:17,060 Aztán kinyomtatni ezt a választ. 903 00:39:17,060 --> 00:39:19,550 >> Sajnos, annak ellenére, szigma hangzik mint valami, ami lehet, hogy 904 00:39:19,550 --> 00:39:24,040 A math.h fájlt, a nyilatkozatát, ez valójában nem az. 905 00:39:24,040 --> 00:39:24,690 Szóval ez rendben van. 906 00:39:24,690 --> 00:39:26,170 Én végre ezt magam. 907 00:39:26,170 --> 00:39:29,160 Megyek, hogy végre egy függvényt nevű szigma, és ez fog tartani egy 908 00:39:29,160 --> 00:39:29,900 paraméter - 909 00:39:29,900 --> 00:39:32,100 hívjuk csak azt m, csak így más. 910 00:39:32,100 --> 00:39:35,910 És akkor itt, azt fogom mondani, Nos, ha m értéke 1-nél kisebb - ez egy 911 00:39:35,910 --> 00:39:38,180 nagyon érdektelen programot. 912 00:39:38,180 --> 00:39:41,700 Szóval megyek előre, és azonnal vissza 0-ra. 913 00:39:41,700 --> 00:39:45,920 Csak nincs értelme, hogy adja ki az összes A számok 1 és m, ha m 914 00:39:45,920 --> 00:39:48,470 maga 0 vagy negatív. 915 00:39:48,470 --> 00:39:50,900 >> Aztán megyek előre és ezt nagyon iteratív. 916 00:39:50,900 --> 00:39:53,090 Fogom ezt a fajta old-school, és én megyek előre 917 00:39:53,090 --> 00:39:57,150 és azt mondják, hogy én fogok kijelentik összeget, hogy 0-ra. 918 00:39:57,150 --> 00:39:59,630 Aztán megyek is a for ciklus int - 919 00:39:59,630 --> 00:40:02,820 és engedi, hogy megfeleljen a elosztás kódot, így van egy példány 920 00:40:02,820 --> 00:40:07,500 otthon. int i lesz az 1-ig i kisebb vagy egyenlő, mint m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 Aztán belül ez a for ciklus - 923 00:40:11,430 --> 00:40:12,440 majdnem ott vagyunk - 924 00:40:12,440 --> 00:40:15,810 összeget kap összeg plusz 1. 925 00:40:15,810 --> 00:40:17,670 Aztán megyek vissza az összeget. 926 00:40:17,670 --> 00:40:19,420 >> Így aztán ezt gyorsan, nagyon igaz. 927 00:40:19,420 --> 00:40:22,775 De ismétlem, a fő funkciója elég egyszerű, alapuló kód voltunk 928 00:40:22,775 --> 00:40:23,190 írt eddig. 929 00:40:23,190 --> 00:40:25,610 Használja a kettős hurok, hogy egy pozitív int a felhasználó elől. 930 00:40:25,610 --> 00:40:29,870 Aztán át, hogy int egy új funkció nevű sigma, amelyben ez, megint, n. 931 00:40:29,870 --> 00:40:33,100 És tárolja a visszatérési értéket, a válasz A fekete doboz jelenleg 932 00:40:33,100 --> 00:40:35,460 néven Sigma, egy változóban nevű válasz. 933 00:40:35,460 --> 00:40:36,580 Aztán nyomtassa ki. 934 00:40:36,580 --> 00:40:39,090 >> Ha most is a történetet, hogyan szigma végrehajtani? 935 00:40:39,090 --> 00:40:40,840 Azt javaslom, hogy hajtsák végre a következő. 936 00:40:40,840 --> 00:40:43,560 Először is, egy kis hiba-ellenőrzés annak biztosítása, hogy a felhasználó nem 937 00:40:43,560 --> 00:40:46,480 szórakozik velem, és halad néhány negatív vagy 0-t. 938 00:40:46,480 --> 00:40:49,710 Aztán, hogy egy változót nevű Összefoglalva és állítsa 0-ra. 939 00:40:49,710 --> 00:40:55,910 >> És most kezd mozogni i értéke 1 egészen bezárólag m, 940 00:40:55,910 --> 00:41:00,130 mert azt akarom, hogy az összes a számokat egytől m, befogadó. 941 00:41:00,130 --> 00:41:04,350 És azon belül a for ciklus, csak csinálni összeget kapja amit most, valamint a 942 00:41:04,350 --> 00:41:08,900 i értéke. 943 00:41:08,900 --> 00:41:10,370 Plusz az i értékét. 944 00:41:10,370 --> 00:41:14,090 >> Mellesleg, ha már nem látta ezt előtt, van néhány szintaktikai cukor 945 00:41:14,090 --> 00:41:14,870 ezen a vonalon. 946 00:41:14,870 --> 00:41:21,120 Tudom átírni ezt a plusz egyenlő i, csak azért, hogy mentsem magam néhány karakternél 947 00:41:21,120 --> 00:41:22,570 és egy kicsit hűvösebb. 948 00:41:22,570 --> 00:41:23,140 De ez minden. 949 00:41:23,140 --> 00:41:24,660 Ez funkcionálisan ugyanaz. 950 00:41:24,660 --> 00:41:26,710 >> Sajnos, ezt a kódot a nem fog össze még. 951 00:41:26,710 --> 00:41:31,600 Ha futok, hogy szigma 0, mennyire vagyok Fogok kapni kiabált? 952 00:41:31,600 --> 00:41:33,473 Mit fog ez nem tetszik? 953 00:41:33,473 --> 00:41:35,740 >> Közönség: [hangtalan]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Igen, én nem nyilvánítja A funkció fel csúcsra, igaz? 955 00:41:37,800 --> 00:41:40,590 C a fajta hülye, az, hogy csak a mit mondani, hogy igen, és 956 00:41:40,590 --> 00:41:41,880 meg kell csinálni, ebben a sorrendben. 957 00:41:41,880 --> 00:41:45,910 És ha én Enter itt fogok kap egy figyelmeztetést szigma implicit 958 00:41:45,910 --> 00:41:46,860 nyilatkozat. 959 00:41:46,860 --> 00:41:48,120 >> Ó, nem probléma. 960 00:41:48,120 --> 00:41:50,370 Mehetek fel a csúcsra, és én is mondjuk, rendben, várj egy percet. 961 00:41:50,370 --> 00:41:54,240 Sigma egy olyan függvényt, amely egy int és vár 962 00:41:54,240 --> 00:41:56,620 int bemenet, pontosvessző. 963 00:41:56,620 --> 00:41:59,550 Vagy sodorhatják az egész funkció fenti fő, de általában, azt 964 00:41:59,550 --> 00:42:02,260 Javasoljuk, ellen, mert szép, hogy mindig fő a tetején, így 965 00:42:02,260 --> 00:42:06,310 lehet zuhanásra és tudja, mi a programot csinál, ha elolvassa legfontosabb először. 966 00:42:06,310 --> 00:42:07,930 >> Tehát most hadd törölje a képernyőt. 967 00:42:07,930 --> 00:42:09,330 Remake szigma 0-ra. 968 00:42:09,330 --> 00:42:10,340 Úgy tűnik, hogy nézd meg. 969 00:42:10,340 --> 00:42:11,970 Engedik szigma 0-ra. 970 00:42:11,970 --> 00:42:12,770 Pozitív inter. 971 00:42:12,770 --> 00:42:15,580 Odaadom a számot 3, hogy ez egyszerű. 972 00:42:15,580 --> 00:42:18,710 Annak érdekében, hogy adjon nekem 3 plusz 2 plusz 1, így 6. 973 00:42:18,710 --> 00:42:20,750 Adja meg, sőt kapok 6. 974 00:42:20,750 --> 00:42:21,820 >> Tehetek valami nagyobb - 975 00:42:21,820 --> 00:42:24,080 50., 12., 75.. 976 00:42:24,080 --> 00:42:27,690 Csakúgy, mint egy érintő, azt fogom tenni valami nevetséges, mint egy nagyon nagy 977 00:42:27,690 --> 00:42:30,375 szám, Ó, hogy valóban dolgozott ki - 978 00:42:30,375 --> 00:42:31,600 eh, én nem hiszem, hogy így van. 979 00:42:31,600 --> 00:42:32,810 Lássuk. 980 00:42:32,810 --> 00:42:34,060 Nézzük igazán rendetlenség vele. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Ez a probléma. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Mi folyik itt? 985 00:42:44,970 --> 00:42:46,050 A kód nem is olyan rossz. 986 00:42:46,050 --> 00:42:48,470 Még mindig lineáris. 987 00:42:48,470 --> 00:42:50,810 Fütyörészve egy jó hatással, mégis. 988 00:42:50,810 --> 00:42:52,060 Mi folyik itt? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Nem biztos, hogy hallottam. 991 00:42:55,620 --> 00:42:57,620 Így kiderül - és ez, mint egy félre. 992 00:42:57,620 --> 00:42:59,400 Ez nem a mag ötlete rekurzió. 993 00:42:59,400 --> 00:43:02,480 Kiderült, hogy azért, mert próbálok jelentenek olyan nagy szám, a legtöbb 994 00:43:02,480 --> 00:43:06,980 valószínűleg ez is félreértelmezik a C, mint egy nem pozitív szám, 995 00:43:06,980 --> 00:43:09,980 de negatív szám. 996 00:43:09,980 --> 00:43:12,690 >> Még nem beszéltünk erről, de a Kiderült, vannak negatív számok 997 00:43:12,690 --> 00:43:14,210 a világ mellett a pozitív számok. 998 00:43:14,210 --> 00:43:16,290 És azokat az eszközöket, amelyek segítségével képviselnek negatív szám 999 00:43:16,290 --> 00:43:19,530 lényegében, van ilyen speciális bit jelzi 1000 00:43:19,530 --> 00:43:20,400 pozitív lesz negatív. 1001 00:43:20,400 --> 00:43:22,950 Ez egy kicsit bonyolultabb, mint az, de ez az alapötlet. 1002 00:43:22,950 --> 00:43:26,740 >> Tehát sajnos, ha a C zavaró egy Az ezeket a biteket ténylegesen jelenti, 1003 00:43:26,740 --> 00:43:30,790 ó, ez egy negatív szám, a hurok Itt például, valójában soha 1004 00:43:30,790 --> 00:43:31,740 majd megszűnik. 1005 00:43:31,740 --> 00:43:33,850 Tehát, ha én tényleg valami nyomtatás újra és újra, mi lenne 1006 00:43:33,850 --> 00:43:34,650 lát egy csomó. 1007 00:43:34,650 --> 00:43:36,220 De ismétlem, ez mellett a lényeg. 1008 00:43:36,220 --> 00:43:38,590 Ez tényleg csak egyfajta intellektuális kíváncsiság, hogy mi fog jönni 1009 00:43:38,590 --> 00:43:39,550 vissza, hogy végül. 1010 00:43:39,550 --> 00:43:43,400 De most, hogy ez a helyes végrehajtás, ha feltételezzük, hogy a 1011 00:43:43,400 --> 00:43:45,970 felhasználó biztosítja ints illik a ints. 1012 00:43:45,970 --> 00:43:49,370 >> De azt állítják, hogy ezt a kódot, őszintén szólva, lehet tenni, így sokkal egyszerűbben. 1013 00:43:49,370 --> 00:43:54,060 Ha a cél a kezét, hogy egy számot mint m, és adja ki az összes 1014 00:43:54,060 --> 00:43:59,510 közötti számok, és 1, vagy fordítva 1 és, azt állítják, 1015 00:43:59,510 --> 00:44:03,380 , hogy én is ezt a gondolatot, hogy a kölcsön egyesíteni sort is, amely vesz egy probléma 1016 00:44:03,380 --> 00:44:05,660 Az ilyen méretű, és azt elosztjuk valami kisebb. 1017 00:44:05,660 --> 00:44:09,875 Lehet, hogy nem fél, de kisebb, de reprezentatív ugyanaz. 1018 00:44:09,875 --> 00:44:12,130 Ugyanez a gondolat, de a kisebb probléma. 1019 00:44:12,130 --> 00:44:15,470 >> Szóval tényleg - hadd menteni a fájlt egy másik verzió számot. 1020 00:44:15,470 --> 00:44:17,670 Hívjuk ezt a verziót 1 0 helyett. 1021 00:44:17,670 --> 00:44:20,790 És azt állítják, hogy én valóban újraimplementálni ezt a fajta 1022 00:44:20,790 --> 00:44:22,160 pszichedelikus módon. 1023 00:44:22,160 --> 00:44:23,710 >> Fogom hagyni részét egyedül. 1024 00:44:23,710 --> 00:44:27,710 Azt fogom mondani, ha m kisebb vagy akár mint az egyenlő 0 - 1025 00:44:27,710 --> 00:44:29,280 Én csak lesz egy kis több anális ezúttal 1026 00:44:29,280 --> 00:44:30,520 az én hibaellenőrzés - 1027 00:44:30,520 --> 00:44:33,190 Én megyek előre, és vissza 0-ra. 1028 00:44:33,190 --> 00:44:34,490 Ez önkényes. 1029 00:44:34,490 --> 00:44:37,500 Én egyszerűen annak eldöntéséhez, hogy a felhasználó ad nekem egy negatív szám, én vagyok 1030 00:44:37,500 --> 00:44:41,490 visszatérő 0, és kellett volna olvasni a dokumentáció jobban. 1031 00:44:41,490 --> 00:44:42,170 >> Else - 1032 00:44:42,170 --> 00:44:44,070 észre, mit fogok csinálni. 1033 00:44:44,070 --> 00:44:49,260 Else fogok visszatérni m plus - 1034 00:44:49,260 --> 00:44:51,010 mi szigma m? 1035 00:44:51,010 --> 00:44:56,710 Nos, szigma m plusz mínusz 1 m, plusz mínusz m 2, plusz mínusz 3 m. 1036 00:44:56,710 --> 00:44:58,030 Én nem akarok írni minden adott ki. 1037 00:44:58,030 --> 00:44:59,120 Miért nem csak punt? 1038 00:44:59,120 --> 00:45:05,080 Rekurzívan hívja magam egy kicsit Kisebb probléma, pontosvessző, 1039 00:45:05,080 --> 00:45:06,840 és ez egy nap? 1040 00:45:06,840 --> 00:45:07,040 >> Nem igaz? 1041 00:45:07,040 --> 00:45:10,980 Most itt is, úgy érezheti, vagy aggódni hogy ez egy végtelen ciklus, hogy én vagyok 1042 00:45:10,980 --> 00:45:15,450 indukáló, ahol én végrehajtási sigma sigma meghívásával. 1043 00:45:15,450 --> 00:45:20,342 De ez teljesen rendben van, mert én gondolt előre hozzáadott melyik vonal? 1044 00:45:20,342 --> 00:45:22,600 >> Közönség: [hangtalan]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: 23-26, ami az én, ha a feltétel. 1046 00:45:25,430 --> 00:45:28,390 Mert mi a jó a kivonás itt, mert én is 1047 00:45:28,390 --> 00:45:31,180 átadta szigma kisebb problémák, kisebb problémák, kisebb - ez nem 1048 00:45:31,180 --> 00:45:31,870 feleakkora. 1049 00:45:31,870 --> 00:45:34,380 Ez csak egy apró lépés a kisebb, de ez rendben van. 1050 00:45:34,380 --> 00:45:38,050 Mert végül is, akkor a munka utunkat lefelé 1-re vagy 0-ra. 1051 00:45:38,050 --> 00:45:41,630 És ha elérünk 0, Sigma nem fogja hívni magát többé. 1052 00:45:41,630 --> 00:45:43,590 Ez lesz, hogy azonnal vissza 0-ra. 1053 00:45:43,590 --> 00:45:47,960 >> Így a hatás, ha a fajta szél a a fejedben, hogy adjunk m plusz 1054 00:45:47,960 --> 00:45:52,740 m mínusz 1, plusz mínusz m 2, plusz mínusz m 3-hoz, pont, pont, pont, m mínusz 1055 00:45:52,740 --> 00:45:57,820 m, végül így 0, és a hatás végül hozzá az összes 1056 00:45:57,820 --> 00:45:59,070 ezeket a dolgokat együtt. 1057 00:45:59,070 --> 00:46:02,380 Tehát nem a rekurzió, megoldotta a problémát, hogy mi 1058 00:46:02,380 --> 00:46:03,470 nem tudta megoldani előtt. 1059 00:46:03,470 --> 00:46:06,840 Sőt, 0-s verzió ezt, és minden probléma a mai napig, már megoldható 1060 00:46:06,840 --> 00:46:09,980 csak használ hurkok, vagy pedig hurkok vagy hasonló konstrukciók. 1061 00:46:09,980 --> 00:46:13,150 >> De rekurzió, merem állítani, ad más módon való gondolkodás 1062 00:46:13,150 --> 00:46:17,010 probléma, amely ha tudunk egy probléma, ossza azt valami 1063 00:46:17,010 --> 00:46:22,340 kissé nagy valami kissé Kisebb, azt állítom, hogy meg tudjuk oldani 1064 00:46:22,340 --> 00:46:26,040 talán egy kicsit elegánsabban szempontból A design, a kevesebb kód, 1065 00:46:26,040 --> 00:46:30,980 és talán még megoldani a problémákat, amelyek nehezebb lesz, hiszen akkor végül 1066 00:46:30,980 --> 00:46:33,280 Látod, megoldása tisztán iteratív. 1067 00:46:33,280 --> 00:46:35,980 >> De az, hogy én nem Cliffhanger akarja elhagyni minket volt ez. 1068 00:46:35,980 --> 00:46:40,720 Hadd menjek előre, és nyitott egy fájl - 1069 00:46:40,720 --> 00:46:44,300 tényleg, hadd menjen, és ezt nagyon gyorsan. 1070 00:46:44,300 --> 00:46:46,875 Hadd menjek előre, és javaslatot a következő. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Napjaink kódja a fájl itt. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Ez itt, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Tehát ez egy hülye kis program, amely Én felkorbácsolta, hogy azt állítja, hogy nem 1076 00:47:06,260 --> 00:47:06,940 a következő. 1077 00:47:06,940 --> 00:47:10,140 A legfontosabb, hogy először kijelenti egy int hívott x és hozzárendeli 1078 00:47:10,140 --> 00:47:11,100 az 1 értéket. 1079 00:47:11,100 --> 00:47:13,520 Aztán kijelenti egy int y és hozzárendeli az érték 2. 1080 00:47:13,520 --> 00:47:15,310 Aztán kiírja, hogy milyen x és y. 1081 00:47:15,310 --> 00:47:17,781 Majd azt mondja, csere, pont, pont. 1082 00:47:17,781 --> 00:47:21,670 >> Majd azt állítja, hogy hívja a függvényt nevezett csere, átadva x és 1083 00:47:21,670 --> 00:47:24,290 y, az ötlet, amely szerint remélhetőleg x és y vissza fog térni 1084 00:47:24,290 --> 00:47:25,620 más, az ellenkezője. 1085 00:47:25,620 --> 00:47:27,110 Akkor állítják cserélték! 1086 00:47:27,110 --> 00:47:28,420 egy felkiáltójel. 1087 00:47:28,420 --> 00:47:30,190 Aztán kiírja x és y. 1088 00:47:30,190 --> 00:47:33,480 >> De kiderül, hogy ez a nagyon egyszerű bemutató le 1089 00:47:33,480 --> 00:47:35,570 Itt valóban hibás. 1090 00:47:35,570 --> 00:47:38,870 Bár én nyilvánított átmeneti változó ideiglenesen amivel egy a 1091 00:47:38,870 --> 00:47:42,010 , akkor én átcsoportosításával egy az értéke B - 1092 00:47:42,010 --> 00:47:45,080 amely úgy érzi, indokolt, mert én már mentett egy példányát a temp. 1093 00:47:45,080 --> 00:47:48,410 Aztán frissítse b egyenlő bármi volt temp. 1094 00:47:48,410 --> 00:47:51,610 Ez a fajta shell játék mozgatása a b és b egy ezzel a 1095 00:47:51,610 --> 00:47:54,360 közép-man nevű temp érez teljesen ésszerű. 1096 00:47:54,360 --> 00:47:57,270 >> De azt állítják, hogy amikor elindul a kódot, ahogy én nem most - 1097 00:47:57,270 --> 00:47:59,490 hadd menjen előre, és illessze be itt. 1098 00:47:59,490 --> 00:48:01,995 Hívom ezt noswap.c. 1099 00:48:01,995 --> 00:48:05,630 És ahogy a neve is mutatja, ez nem lesz megfelelő programot. 1100 00:48:05,630 --> 00:48:09,460 Legyen noswap. / Nincs csere. 1101 00:48:09,460 --> 00:48:12,110 x értéke 1, y értéke 2, csere, cserélték. 1102 00:48:12,110 --> 00:48:14,220 x értéke 1, y értéke 2. 1103 00:48:14,220 --> 00:48:16,920 Ez alapvetően rossz, még de ez úgy tűnik, tökéletesen 1104 00:48:16,920 --> 00:48:17,730 ésszerű nekem. 1105 00:48:17,730 --> 00:48:21,330 És van egy ok, de mi nem vagyunk lesz, hogy felfedje az ok csak még. 1106 00:48:21,330 --> 00:48:24,610 >> Mert most a második Cliffhanger akartam itt hagyni ez, egy 1107 00:48:24,610 --> 00:48:27,120 bejelentése a fajta a kupon kód. 1108 00:48:27,120 --> 00:48:31,590 Az innováció végén napok idén váltott ki a nem elhanyagolható számban 1109 00:48:31,590 --> 00:48:33,830 A kérdés, ami Nem célunk. 1110 00:48:33,830 --> 00:48:36,590 A szándék e kupon kód, amely, ha nem a probléma része 1111 00:48:36,590 --> 00:48:39,850 meg korán, így kapok egy extra napot, igazán, hogy segítsen nektek segíteni 1112 00:48:39,850 --> 00:48:42,420 magad korán kezdeni, sort Az a ösztönzünk téged. 1113 00:48:42,420 --> 00:48:44,880 Segít terjeszteni terhelést a nyitvatartási jobban, hogy 1114 00:48:44,880 --> 00:48:45,740 Ez a fajta win-win. 1115 00:48:45,740 --> 00:48:48,860 >> Sajnos, azt hiszem az utasításaimat nem volt, a mai napig, nagyon világos, így 1116 00:48:48,860 --> 00:48:52,230 Visszamentem a hétvégén és frissített A spec a nagyobb, merészebb szöveg 1117 00:48:52,230 --> 00:48:53,600 megmagyarázni golyók, mint ezek. 1118 00:48:53,600 --> 00:48:56,900 És csak azt mondom, hogy több nyilvános, a Alapértelmezésben probléma határozza miatt csütörtök 1119 00:48:56,900 --> 00:48:58,400 délben, egy a tananyag. 1120 00:48:58,400 --> 00:49:02,030 Ha korán kezdeni, befejező része A probléma által szerda 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, az a része, amely kapcsolódik egy kupon kódot, az ötlet, hogy akkor terjed 1122 00:49:05,170 --> 00:49:07,710 A határidő a P meg péntekig. 1123 00:49:07,710 --> 00:49:10,890 Ez azt jelenti, kicsit le egy kis része a P beállítva ahhoz képest, amit jellemzően a 1124 00:49:10,890 --> 00:49:13,200 nagyobb probléma, és veszel magadnak egy extra napot. 1125 00:49:13,200 --> 00:49:15,190 Ismét lesz gondoltál A probléma meg, kap, hogy 1126 00:49:15,190 --> 00:49:16,380 munkaidőben hamarabb. 1127 00:49:16,380 --> 00:49:20,670 De a kupon kód probléma még mindig szükséges, akkor is, ha nem nyújtja be azt. 1128 00:49:20,670 --> 00:49:23,340 >> De még ez a feltűnően. 1129 00:49:23,340 --> 00:49:26,520 (Színpadi suttogással) És azok emberek így elején fognak bánni. 1130 00:49:26,520 --> 00:49:28,620 Ahogy az emberek az erkélyen. 1131 00:49:28,620 --> 00:49:32,510 Előre is elnézést, hogy az emberek a az erkélyen okok miatt lesz 1132 00:49:32,510 --> 00:49:33,920 világos csak egy pillanat. 1133 00:49:33,920 --> 00:49:37,050 >> Így szerencsések vagyunk, hogy az egyik CS50 korábbi vezetője tanítása fiúk at 1134 00:49:37,050 --> 00:49:39,302 nevű cég dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Ők nagylelkűen adományozott a kuponkódja ide a sok helyet, 1136 00:49:45,500 --> 00:49:48,180 amely akár a szokásos 2 gigabájt. 1137 00:49:48,180 --> 00:49:51,740 Tehát mi azt gondoltuk, hogy ezt ezen a utolsó megjegyzés nem egy kicsit giveaway, 1138 00:49:51,740 --> 00:49:55,380 ahol csak egy pillanat, mi fog kiderülni a győztes, aki a szelvényt 1139 00:49:55,380 --> 00:49:57,980 kódot, akkor majd megy a website, írja be, és íme, kap egy 1140 00:49:57,980 --> 00:50:01,370 az egész sokkal több hely a Dropbox készülék és a személyes fájlok. 1141 00:50:01,370 --> 00:50:05,690 >> És az első, aki szeretne részt venni ebben a rajzban? 1142 00:50:05,690 --> 00:50:09,630 OK, most, hogy teszi még szórakoztatóbb. 1143 00:50:09,630 --> 00:50:14,010 Az a személy, aki megkapja ezt a 25 GB-os szelvény kód - amely messze 1144 00:50:14,010 --> 00:50:16,150 vonzóbb, mint a néhai Napok óta, talán - 1145 00:50:16,150 --> 00:50:20,620 az, aki ül a tetején egy ülőpárna, amely alatt van 1146 00:50:20,620 --> 00:50:21,620 hogy kupon kód. 1147 00:50:21,620 --> 00:50:23,480 Lehet, hogy most meg alatta az ülőpárna. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [VIDEÓ LEJÁTSZÁS] 1150 00:50:29,680 --> 00:50:31,620 >> -Egy, kettő, három. 1151 00:50:31,620 --> 00:50:35,015 >> [Screaming] 1152 00:50:35,015 --> 00:50:35,985 >> -Kapsz egy autó! 1153 00:50:35,985 --> 00:50:36,670 Kapsz egy autót! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Meglátjuk akkor szerdán. 1155 00:50:37,970 --> 00:50:38,904 >> -Kapsz egy autó! 1156 00:50:38,904 --> 00:50:39,371 Kapsz egy autót! 1157 00:50:39,371 --> 00:50:40,305 Kapsz egy autót! 1158 00:50:40,305 --> 00:50:41,706 Kapsz egy autót! 1159 00:50:41,706 --> 00:50:43,107 Kapsz egy autót! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: Erkély emberek, gyere ide, hogy az első, 1161 00:50:45,530 --> 00:50:46,866 ahol már extrával. 1162 00:50:46,866 --> 00:50:50,282 >> -Mindenki kap egy autót! 1163 00:50:50,282 --> 00:50:52,234 Mindenki kap egy autó! 1164 00:50:52,234 --> 00:50:52,722 >> [END VIDEÓ LEJÁTSZÁS] 1165 00:50:52,722 --> 00:50:54,590 >> Srácok A következő CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Oh, istenem istenem istenem gosh Istenem Istenem Istenem Istenem Istenem Istenem - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukelele PLAYS]