1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Zenelejátszási] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. MALAN: Ez CS50. 5 00:00:12,550 --> 00:00:14,612 És ez az a hét elején három. 6 00:00:14,612 --> 00:00:16,820 Tehát van egy csomó izgalmas dolgokat, hogy fedezze ma. 7 00:00:16,820 --> 00:00:20,160 Sok lehetőséget önkéntesek a színpadon. 8 00:00:20,160 --> 00:00:22,780 És végül, a ma Nem a kódot egyáltalán. 9 00:00:22,780 --> 00:00:24,820 De ez a gondolatok, és ez körülbelül algoritmusok, 10 00:00:24,820 --> 00:00:28,420 és valóban hozza vissza néhány tanulságait héten nulla, 11 00:00:28,420 --> 00:00:31,910 ahol emlékszem, mi vezette be ezt a szörnyűséget. 12 00:00:31,910 --> 00:00:33,880 És hitelfelvételi ihletet attól, hogy kezdeni 13 00:00:33,880 --> 00:00:36,879 megoldására egyre kifinomultabb problémákat algoritmikusan. 14 00:00:36,879 --> 00:00:38,420 De először, egy pár bejelentések. 15 00:00:38,420 --> 00:00:42,020 Tehát az egyik, ha szeretne csatlakozni CS50 személyzete és az osztálytársak ebédre 16 00:00:42,020 --> 00:00:44,670 ez a péntek, itt és Cambridge és New Haven, 17 00:00:44,670 --> 00:00:48,060 kérjük, látogasson el a pálya honlapján, ahol egy URL megtalálható. 18 00:00:48,060 --> 00:00:50,390 Előadás szerdán lesz Nem lehet itt Sanders. 19 00:00:50,390 --> 00:00:53,610 Ez lesz csak online, így ráhangolódni a CS50 honlapján, 20 00:00:53,610 --> 00:00:55,850 hogy itt Cambridge vagy New Haven is. 21 00:00:55,850 --> 00:00:58,110 >> És akkor a probléma meg két már a kezedben. 22 00:00:58,110 --> 00:01:03,067 Ha még nem merültem a még engedjék meg, kínálnak a határozottan megfogalmazott javaslatot 23 00:01:03,067 --> 00:01:05,150 hogy különösen most, A probléma határozza előre, 24 00:01:05,150 --> 00:01:08,669 ha tényleg akar kezdeni most, ha nem pancsolás egy kicsit a hétvégén, vagy előzetes 25 00:01:08,669 --> 00:01:10,710 amikor először kimenni Pénteken, mert akkor 26 00:01:10,710 --> 00:01:14,380 találják, hogy ők nem feltétlenül egyre hosszabb vagy nagyobb kihívást per 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Azt hiszem, rájössz, hogy Általánosságban, azok hajlamosak arra, hogy durván 29 00:01:17,575 --> 00:01:18,892 körül ugyanannyi idő. 30 00:01:18,892 --> 00:01:20,850 De ez persze függ a diák, és ez 31 00:01:20,850 --> 00:01:22,880 függ a gondolkodásmód amellyel megközelíteni. 32 00:01:22,880 --> 00:01:24,910 De mindig, fogsz hogy belebotlik néhány falat, 33 00:01:24,910 --> 00:01:26,350 és máris megy, hogy elérje néhány hiba, és te csak 34 00:01:26,350 --> 00:01:27,950 Nem lesz képes túl lesz rajta egy bizonyos ponton. 35 00:01:27,950 --> 00:01:31,380 És ez rendkívül értékes, hogy képes a lépésre, gyere vissza másnap, 36 00:01:31,380 --> 00:01:35,286 megy munkaidejében hozzászólás CS50 Beszéljétek vagy hasonló, hogy valóban kap feloldják. 37 00:01:35,286 --> 00:01:36,160 Tehát hogy tartsa szem előtt. 38 00:01:36,160 --> 00:01:40,830 Kezdve legkorábbi lehető a legjobb dolog, amit tehetünk. 39 00:01:40,830 --> 00:01:44,160 Tehát itt van, ahol elkezdtük az osztály, mint a heti nulla. 40 00:01:44,160 --> 00:01:47,441 És tudjuk, hogy egy önkéntes itt, hogy segítsen nekem megtalálni mikrofonok? 41 00:01:47,441 --> 00:01:47,940 OKÉ. 42 00:01:47,940 --> 00:01:48,900 Állva már. 43 00:01:48,900 --> 00:01:50,080 Gyere fel. 44 00:01:50,080 --> 00:01:53,707 Találd ki, hogy ez hogyan fog működni. 45 00:01:53,707 --> 00:01:54,415 Mi a neved? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 David J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Gyere fel. 49 00:01:57,910 --> 00:01:58,619 Örvendek. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Örülök, hogy találkoztunk. 51 00:01:59,910 --> 00:02:02,772 David J. MALAN: És itt lennél velünk héten nulla, persze. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: voltam. 53 00:02:03,028 --> 00:02:03,160 Voltam. 54 00:02:03,160 --> 00:02:05,868 >> David J. MALAN: Így lehetne mész előre, és megtalálni a számunkra Mike Smith, 55 00:02:05,868 --> 00:02:08,639 amilyen gyorsan csak lehet? 56 00:02:08,639 --> 00:02:10,639 Amilyen gyorsan csak lehet. 57 00:02:10,639 --> 00:02:13,756 Szó tépte a problémát félbe, ahogy kell. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Hm. 59 00:02:15,130 --> 00:02:17,380 David J. MALAN: Szó szerint tépte a probléma felét. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Nagyon jó. 64 00:02:23,300 --> 00:02:23,700 >> David J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Jó. 66 00:02:24,200 --> 00:02:24,701 Köszönöm. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Nagyon jó. 68 00:02:25,700 --> 00:02:26,210 OKÉ. 69 00:02:26,210 --> 00:02:27,610 >> David J. MALAN: És így most, amit szűkítették le 70 00:02:27,610 --> 00:02:29,320 fele a méret a problémát. 71 00:02:29,320 --> 00:02:31,267 Most vagyunk egészen a negyede. 72 00:02:31,267 --> 00:02:33,475 Figyelsz, hogy melyik oldalon vagyunk tartani? 73 00:02:33,475 --> 00:02:34,405 >> [Nevet] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Igen, én think-- 75 00:02:35,970 --> 00:02:37,594 >> David J. MALAN: Mit részén vagyunk itt? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: nyaksál, így van. 77 00:02:39,150 --> 00:02:39,941 >> David J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 De Mike Smith megy hogy miután kipufogócsövek. 79 00:02:42,810 --> 00:02:44,130 Na-- 80 00:02:44,130 --> 00:02:48,180 >> [Nevet] 81 00:02:48,180 --> 00:02:48,742 >> Minden rendben. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Hol keresünk? 83 00:02:50,200 --> 00:02:52,049 David J. MALAN: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 David J. MALAN: Most mi vagyunk a sebészeti. 86 00:02:54,760 --> 00:02:57,840 Most, orvosok. 87 00:02:57,840 --> 00:02:58,340 Most-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- menjünk igazi. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> David J. MALAN: Real. 91 00:03:00,970 --> 00:03:01,470 OKÉ. 92 00:03:01,470 --> 00:03:03,700 Ha szüksége van a Real. 93 00:03:03,700 --> 00:03:05,250 Most, merre van Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Ez így. 95 00:03:06,250 --> 00:03:07,333 >> David J. MALAN: Merre? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Várj. 97 00:03:08,240 --> 00:03:08,790 M is-- ugye? 98 00:03:08,790 --> 00:03:09,110 Elkezdtünk with-- 99 00:03:09,110 --> 00:03:10,090 >> David J. MALAN: Igen. 100 00:03:10,090 --> 00:03:10,650 Ők maradt. 101 00:03:10,650 --> 00:03:11,430 A jobb. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Igen. 103 00:03:11,710 --> 00:03:13,126 >> David J. MALAN: Szóval Mike itt. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Mi? 105 00:03:13,990 --> 00:03:14,665 >> [Nevet] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Rossz példa srácok. 108 00:03:18,330 --> 00:03:18,830 Bocsánat. 109 00:03:18,830 --> 00:03:21,610 David J. MALAN: Ez megtanít hogy kiugrik a széket. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Ó. 112 00:03:22,890 --> 00:03:23,390 Elkaptalak. 113 00:03:23,390 --> 00:03:24,670 Elkaptalak. 114 00:03:24,670 --> 00:03:25,170 Ó. 115 00:03:25,170 --> 00:03:25,669 Ó. 116 00:03:25,669 --> 00:03:26,812 Ez is-- OK, hoztam neked. 117 00:03:26,812 --> 00:03:27,520 Smith itt? 118 00:03:27,520 --> 00:03:28,894 >> David J. MALAN: Smith, köszönöm. 119 00:03:28,894 --> 00:03:30,535 Szóval fogom tartani keresi fel Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ó, igen. 121 00:03:30,790 --> 00:03:31,340 Nem nem nem. 122 00:03:31,340 --> 00:03:31,600 Oh ne. 123 00:03:31,600 --> 00:03:31,940 Ez az enyém. 124 00:03:31,940 --> 00:03:32,580 >> David J. MALAN: Ó, megvan Smith. 125 00:03:32,580 --> 00:03:33,415 OKÉ. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Igen, Van Smith itt. 127 00:03:34,040 --> 00:03:34,700 Bocs, srácok. 128 00:03:34,700 --> 00:03:35,860 Azt hittem Michael-- vagyunk kerestek Michael. 129 00:03:35,860 --> 00:03:36,550 Bocsánat. 130 00:03:36,550 --> 00:03:37,550 >> David J. MALAN: Nem baj. 131 00:03:37,550 --> 00:03:39,950 Rendben, most mi vagyunk a Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini és fiai. 133 00:03:41,242 --> 00:03:43,158 David J. MALAN: csak te és én már ezen. 134 00:03:43,158 --> 00:03:44,050 OKÉ. 135 00:03:44,050 --> 00:03:45,130 Keresse meg minket Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> David J. MALAN: Smith. 139 00:03:46,750 --> 00:03:47,728 Mi vagyunk a K szeméthez. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Vacak. 141 00:03:48,644 --> 00:03:50,096 Ó. 142 00:03:50,096 --> 00:03:52,480 Ez el fog tartani egy darabig. 143 00:03:52,480 --> 00:03:54,340 >> [Nevet] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 David J. MALAN: Cipő. 146 00:03:56,720 --> 00:03:58,080 Mi vagyunk a cipő. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Most már gonna-- 148 00:04:00,210 --> 00:04:01,105 >> David J. MALAN: Szép. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Nevet] 151 00:04:03,620 --> 00:04:05,440 Ó, ez nagyszerű. 152 00:04:05,440 --> 00:04:06,910 [Nevet] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> David J. MALAN: Nem baj. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Ó, ez jó. 156 00:04:11,365 --> 00:04:14,425 Nem hiszem, hogy fogok Van PSAT haverok után. 157 00:04:14,425 --> 00:04:15,300 David J. MALAN: Jó. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 David J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Úgyhogy szakadjon ennek a fele. 163 00:04:21,600 --> 00:04:22,270 Oké. 164 00:04:22,270 --> 00:04:25,606 Ez a vége rosszul egyébként, mert Mike Smith nem lesz a sárga lapok. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Ó. 166 00:04:26,430 --> 00:04:27,140 >> David J. MALAN: Nem, nem baj. 167 00:04:27,140 --> 00:04:28,930 De nézzük úgy, mintha ő ezen az oldalon. 168 00:04:28,930 --> 00:04:33,260 Tehát most, hogy már szűkítették a problémát le az egyik oldalon, és azt találtuk, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Éljenzés] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Rendben köszönöm. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OKÉ. 174 00:04:41,200 --> 00:04:43,646 Ez volt rendkívüli. 175 00:04:43,646 --> 00:04:45,954 De ez még mindig gyorsabb mint a lineáris keresés, 176 00:04:45,954 --> 00:04:47,870 ahol kezdjük meg a A könyv elején, 177 00:04:47,870 --> 00:04:51,210 és haladunk utunkat balról jobbra, végül keres Mike Smith. 178 00:04:51,210 --> 00:04:53,540 És így, ha a telefonkönyvben volt talán 1000 oldal, 179 00:04:53,540 --> 00:04:56,300 talán ez volna nekünk 10, vagy úgy oldalon könnyek. 180 00:04:56,300 --> 00:04:59,380 >> De lehet, hogy tőkeáttételes megérintette a feltételezés 181 00:04:59,380 --> 00:05:03,602 alatt minden, hogy ami azt hogy a telefonkönyv előre mi volt? 182 00:05:03,602 --> 00:05:04,310 Közönség: Rendezés. 183 00:05:04,310 --> 00:05:05,000 David J. MALAN: Ez válogatni. 184 00:05:05,000 --> 00:05:05,160 Jobb? 185 00:05:05,160 --> 00:05:07,909 Ez ábécé-sorrendben, így hogy az összes ilyen nevek és számok 186 00:05:07,909 --> 00:05:11,230 vannak sorolva a A. a Z, és betűrendben között. 187 00:05:11,230 --> 00:05:13,100 De ma, hogy most megkérdezzük A kérdést, nos, 188 00:05:13,100 --> 00:05:16,170 Milyen volt a Verizon vagy a telefon cég kap ez az állapotban? 189 00:05:16,170 --> 00:05:19,560 >> Mert az egy dolog, hogy felerősítse hogy a feltételezés, és ezért, 190 00:05:19,560 --> 00:05:22,570 megoldani egy problémát egy algoritmus hatékonyabban. 191 00:05:22,570 --> 00:05:24,900 De soha nem kérdezte héten nulla, nos, 192 00:05:24,900 --> 00:05:27,790 mennyibe került ez költsége Verizon vagy valaki más 193 00:05:27,790 --> 00:05:29,620 kap, hogy a telefonkönyv rendezett sorrendben? 194 00:05:29,620 --> 00:05:29,780 >> Jobb? 195 00:05:29,780 --> 00:05:31,529 Nem számít, ha felnézett Mike Smith 196 00:05:31,529 --> 00:05:35,190 szuper gyors, ha ez visz egy évben rendezni az oldalakat kezdetben. 197 00:05:35,190 --> 00:05:35,690 Jobb? 198 00:05:35,690 --> 00:05:38,620 Lehet, hogy azt is csak szitál egy randomizált telefonkönyv, 199 00:05:38,620 --> 00:05:40,690 ha lesz szuper drága szortírozni. 200 00:05:40,690 --> 00:05:42,350 Tehát, ha tudjuk, hogy egy másik önkéntes. 201 00:05:42,350 --> 00:05:46,350 Vessünk egy pillantást fel itt hogyan might-- gyere up-- hogyan 202 00:05:46,350 --> 00:05:48,100 talán megy a válogatás ezeket. 203 00:05:48,100 --> 00:05:51,990 >> És ha Jordan ténylegesen csatlakozzon hozzánk itt a színpadon. 204 00:05:51,990 --> 00:05:55,100 Gyere fel egy pillanatra. 205 00:05:55,100 --> 00:05:56,359 Mi a neved? 206 00:05:56,359 --> 00:05:57,150 Caroline: Caroline. 207 00:05:57,150 --> 00:05:58,691 David J. MALAN: Caroline, gyere fel. 208 00:05:58,691 --> 00:06:02,070 És máris csatlakozott én és Jordan itt. 209 00:06:02,070 --> 00:06:03,800 Caroline, köszönöm. 210 00:06:03,800 --> 00:06:04,300 Minden rendben. 211 00:06:04,300 --> 00:06:08,330 Szóval mi van itt Caroline 26 kék könyvek 212 00:06:08,330 --> 00:06:10,747 hogy FAS használ adminisztrálni Bizonyos záróvizsgák. 213 00:06:10,747 --> 00:06:13,330 Ezek egyre nehéz találni, de mit tettünk előre 214 00:06:13,330 --> 00:06:15,800 az, hogy már fel valakinek a nevét az első az egyes ilyen, 215 00:06:15,800 --> 00:06:18,133 de már tartotta egyszerűek majd kidugta a teljes nevét. 216 00:06:18,133 --> 00:06:22,720 Tehát tenné a személy nevét L, D, J, B, egészen a A-Z, 217 00:06:22,720 --> 00:06:24,090 de ők véletlenszerű sorrendben. 218 00:06:24,090 --> 00:06:26,890 És így ha lenne, beszél a végig a problémát, ahogy 219 00:06:26,890 --> 00:06:31,620 csinálni, akkor megy előre, és rendezni ezeket a számunkra, A-tól Z- 220 00:06:31,620 --> 00:06:34,070 >> Közönség: OK, így L, mint a közepén. 221 00:06:34,070 --> 00:06:35,050 C kezd. 222 00:06:35,050 --> 00:06:42,410 B. J előtt L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> David J. MALAN: tartsd meg elgondolkodott egy pillanatra. 224 00:06:45,140 --> 00:06:48,910 Mivel egyébként, ez csak Érdekes, hogy te, én, és a Jordan. 225 00:06:48,910 --> 00:06:49,724 Ott vagyunk. 226 00:06:49,724 --> 00:06:50,640 Közönség: [hallható]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 David J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 Mit csinálsz? 230 00:06:59,310 --> 00:07:01,730 >> Caroline: M után jön O. 231 00:07:01,730 --> 00:07:02,564 >> David J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> Caroline: O. 233 00:07:03,064 --> 00:07:04,120 David J. MALAN: O, jó. 234 00:07:04,120 --> 00:07:04,970 >> Caroline: E. 235 00:07:04,970 --> 00:07:06,730 >> David J. MALAN: E, F. Igen. 236 00:07:06,730 --> 00:07:07,620 >> Caroline: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> David J. MALAN: V, T, U, V Tehát úgy néz ki, mint te vagy making-- tartani fog. 238 00:07:10,689 --> 00:07:12,730 Úgy néz ki, hogy még van egy nagy halom ide, 239 00:07:12,730 --> 00:07:13,910 és milyen egy nagy halom ott. 240 00:07:13,910 --> 00:07:16,230 Tehát az első felében az ábécé, második felében az ábécé. 241 00:07:16,230 --> 00:07:16,460 OKÉ. 242 00:07:16,460 --> 00:07:16,960 Jó. 243 00:07:16,960 --> 00:07:19,680 Kind ketté a problémát kettő. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Igen. 245 00:07:21,771 --> 00:07:22,270 Caroline: K. 246 00:07:22,270 --> 00:07:22,980 David J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Szóval fajta kiválasztása sorban egymás után, 248 00:07:25,070 --> 00:07:27,620 megvalósítják azt balra vagy jobbra, vagy Z folyik a padlóra. 249 00:07:27,620 --> 00:07:28,012 OKÉ. 250 00:07:28,012 --> 00:07:29,190 >> Caroline: Z folyik a padlóra. 251 00:07:29,190 --> 00:07:29,360 >> David J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y folyik a padlóra. 253 00:07:30,920 --> 00:07:31,735 Most már tudjuk tenni X. 254 00:07:31,735 --> 00:07:32,409 >> Caroline: G. 255 00:07:32,409 --> 00:07:33,700 David J. MALAN: G megy a bal. 256 00:07:33,700 --> 00:07:36,017 S lesz jobb. 257 00:07:36,017 --> 00:07:37,642 Rendben, egy megy végig maradt. 258 00:07:37,642 --> 00:07:38,790 >> Caroline: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> David J. MALAN: Most jó. 260 00:07:39,873 --> 00:07:43,260 Van A, B, C W folyik odalent. 261 00:07:43,260 --> 00:07:45,566 Rendben, T. 262 00:07:45,566 --> 00:07:46,611 >> Caroline: H, I, J. 263 00:07:46,611 --> 00:07:47,860 David J. MALAN: H, I, J Jó. 264 00:07:47,860 --> 00:07:49,160 Caroline: A központban, én gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Tehát most, megyünk a fajta A eleget a különböző cölöpök. 267 00:07:52,375 --> 00:08:00,730 Tehát A-C, akkor látom D, és E és F, valamint a G, és H, és I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K És akkor ez a halom fejjel lefelé, de ez rendben van. 269 00:08:05,540 --> 00:08:06,040 Persze. 270 00:08:06,040 --> 00:08:07,240 Mi lehet vágni néhány sarkok. 271 00:08:07,240 --> 00:08:07,950 OKÉ. 272 00:08:07,950 --> 00:08:10,530 És akkor mi van szüksége W, X, Y, Z 273 00:08:10,530 --> 00:08:11,250 >> Caroline: Igen. 274 00:08:11,250 --> 00:08:11,880 >> David J. MALAN: Kitűnő. 275 00:08:11,880 --> 00:08:14,122 Szóval egy nagy köszönet Caroline válogatás ezeket. 276 00:08:14,122 --> 00:08:15,030 >> [Éljenzés] 277 00:08:15,030 --> 00:08:17,287 >> Köszönöm. 278 00:08:17,287 --> 00:08:18,120 Köszi szépen. 279 00:08:18,120 --> 00:08:22,910 Tehát most nézzük meg egy pillanatra hogyan Caroline széjjeljárt, hogy 280 00:08:22,910 --> 00:08:26,040 és pontosan mit is képesek voltak az alábbiakra: hogyan 281 00:08:26,040 --> 00:08:28,409 voltak képesek megoldani, hogy probléma, amikor mi éppen 282 00:08:28,409 --> 00:08:29,950 adott egy csomó véletlen bemenetre. 283 00:08:29,950 --> 00:08:31,610 >> Nos, úgy tűnik, van Volt egy kis rendszer van? 284 00:08:31,610 --> 00:08:32,110 Jobb. 285 00:08:32,110 --> 00:08:34,495 Így a korábbi leveleket az ábécé, a lány 286 00:08:34,495 --> 00:08:37,120 volt, amivel a bal oldalon, és a Később betű az ábécében, 287 00:08:37,120 --> 00:08:38,270 ő rakta be a jobb. 288 00:08:38,270 --> 00:08:40,500 És amint rájött, Néhány közeli betűket, akik 289 00:08:40,500 --> 00:08:43,124 hogy megy jobb egymás mellett, ő is tesz azok érdekében. 290 00:08:43,124 --> 00:08:46,750 És így egyfajta kellett ezeket a kis halom sorba rendezett bemenetek előforduló. 291 00:08:46,750 --> 00:08:50,540 >> És ez az egész, mint amit a legtöbben emberek tennék. 292 00:08:50,540 --> 00:08:53,530 Azt a fajta keresgélést meg, és mi lenne egyfajta mechanizmust. 293 00:08:53,530 --> 00:08:56,930 De lehet, hogy nehéz írni le egy képletet önmagában. 294 00:08:56,930 --> 00:08:59,010 Úgy éreztem, egy kicsit több szerves annál. 295 00:08:59,010 --> 00:09:02,560 Szóval lássuk, mi most megkötött A probléma a kevesebb bemenettel. 296 00:09:02,560 --> 00:09:05,170 >> Ahelyett, hogy 26, nézzük tenni valamit sokkal kevesebb 297 00:09:05,170 --> 00:09:09,890 csak azt mondják, hét, mögötte ezek az ajtók, hogy úgy mondjam. 298 00:09:09,890 --> 00:09:11,300 Van csak hét számot? 299 00:09:11,300 --> 00:09:15,240 És ha a cél most kezét az, hogy megtaláljuk az érték, 300 00:09:15,240 --> 00:09:17,850 lássuk, milyen hatékonyan mehetünk körülbelül ezt. 301 00:09:17,850 --> 00:09:22,460 És lássuk, mi most akkor kell alkalmazni, néhány számot, 302 00:09:22,460 --> 00:09:26,310 vagy néhány képletek, amelyekkel leírására hatékonyságát a telefonkönyvben 303 00:09:26,310 --> 00:09:31,060 algoritmus, mi vizsgát könyv algoritmust, és általánosabban információk megtalálása. 304 00:09:31,060 --> 00:09:34,770 >> Tehát erre, hadd menjen előre, és az érintőképernyőn át ide, 305 00:09:34,770 --> 00:09:41,100 elvállal egy web böngészőt, Pontosan ez a hét ajtó. 306 00:09:41,100 --> 00:09:46,670 És ha tudnánk egy másik önként gyere ide, 307 00:09:46,670 --> 00:09:48,480 Már fel ugyanezek ajtók ide. 308 00:09:48,480 --> 00:09:49,170 Gyors önkéntes. 309 00:09:49,170 --> 00:09:51,130 >> Ez one-- demók mennek a gyorsabb és gyorsabb most. 310 00:09:51,130 --> 00:09:51,600 Gyere le. 311 00:09:51,600 --> 00:09:52,308 Mi a neved? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> David J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Rendben, Trevor, gyere le. 315 00:09:55,770 --> 00:09:59,212 Tehát Trevor önként ide csinál egy hasonló probléma, de az egyik, hogy 316 00:09:59,212 --> 00:10:02,170 korlátozottabb, és ez fog hogy lehetővé teszik számunkra, hogy megpróbálja hivatalossá most 317 00:10:02,170 --> 00:10:03,970 A folyamat válogatás ezeket a számokat. 318 00:10:03,970 --> 00:10:05,500 >> Szóval Trevor, örülök, hogy találkoztunk. 319 00:10:05,500 --> 00:10:08,720 Tehát itt van egy tömbben, így a beszélnek, egy listát a hét ajtók. 320 00:10:08,720 --> 00:10:10,327 Menj, és talál minket száma 50. 321 00:10:10,327 --> 00:10:12,410 Majd miután az a tény, mondja el, hogyan találta meg. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Amennyiben be-- minden rendben. 324 00:10:20,040 --> 00:10:21,945 Igen, ez az egy van? 325 00:10:21,945 --> 00:10:24,680 UH Oh. 326 00:10:24,680 --> 00:10:25,560 OKÉ. 327 00:10:25,560 --> 00:10:26,680 Ön kattintott, hogy az egyik. 328 00:10:26,680 --> 00:10:28,690 Jó. 329 00:10:28,690 --> 00:10:29,780 >> És jó. 330 00:10:29,780 --> 00:10:30,970 Most már kattintott, hogy az egyik. 331 00:10:30,970 --> 00:10:34,060 És hadd adjak a mikrofont, úgy, hogy ez csak egy pillanatra. 332 00:10:34,060 --> 00:10:37,000 Menj előre, és kattintson a a szomszédban, hogy kíván. 333 00:10:37,000 --> 00:10:39,812 Igen, jó. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Tudok unclick egy ajtót? 335 00:10:41,020 --> 00:10:42,620 David J. MALAN: Nem, nem tudod unclick. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Ezt. 338 00:10:43,974 --> 00:10:45,640 David J. MALAN: Hol akarod, hogy menjen? 339 00:10:45,640 --> 00:10:46,410 Melyik az? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Ez az egyik. 341 00:10:47,230 --> 00:10:48,042 >> David J. MALAN: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Ezt. 344 00:10:48,735 --> 00:10:49,020 >> David J. MALAN: Igen. 345 00:10:49,020 --> 00:10:49,700 Az jó volt. 346 00:10:49,700 --> 00:10:50,380 Minden rendben. 347 00:10:50,380 --> 00:10:53,900 Tehát mi volt az algoritmus vagy eljárás ezt, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Én most ment át ajtók, amíg találtam egy 50. 349 00:10:56,149 --> 00:10:56,940 David J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Kiváló algoritmus. 351 00:10:58,150 --> 00:10:59,540 Szóval ez rendben van. 352 00:10:59,540 --> 00:11:03,120 Mert valójában, ha elárulom, mi van mögött két másik ajtó, mit 353 00:11:03,120 --> 00:11:06,954 találunk itt az, hogy már csak véletlen bemenet. 354 00:11:06,954 --> 00:11:08,870 Szóval ez volt tulajdonképpen a jó, mint lehetne még. 355 00:11:08,870 --> 00:11:12,509 És valóban, van jobb, mint a kimerítően keres az egész tömböt, 356 00:11:12,509 --> 00:11:15,300 mert ez lett volna igazán szerencsétlen, ha megütötte száma 357 00:11:15,300 --> 00:11:16,604 50 az utolsó ajtó. 358 00:11:16,604 --> 00:11:18,520 De mi lenne, ha ahelyett, kaptál egy feltételezés. 359 00:11:18,520 --> 00:11:20,630 Tegyük fel, hogy azt a fajta összes ezek az ajtók körül, 360 00:11:20,630 --> 00:11:23,500 úgy, hogy a számok rendezve ebben az időben, 361 00:11:23,500 --> 00:11:29,730 de ezúttal ez valójában egy different-- ebben az időben, 362 00:11:29,730 --> 00:11:32,640 mert tulajdonképpen ez válogatni az Ön számára. 363 00:11:32,640 --> 00:11:35,380 És most a cél kéznél az, hogy elérje a szám 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> David J. MALAN: Mi Ön algoritmus lesz? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Nos, ha ez válogatni, ez sem megy, 367 00:11:39,628 --> 00:11:42,710 hogy be-- ha legnagyobb a legnagyobb, csökkenő, ez lesz az első, 368 00:11:42,710 --> 00:11:44,751 vagy ha ez ellentétes, ez lesz az utolsó. 369 00:11:44,751 --> 00:11:48,897 Szóval én csak érintse az ajtót, és akkor csak érintse az utolsó ajtó. 370 00:11:48,897 --> 00:11:49,980 David J. MALAN: Kitűnő. 371 00:11:49,980 --> 00:11:50,270 Minden rendben. 372 00:11:50,270 --> 00:11:51,150 Így találtunk száma 50. 373 00:11:51,150 --> 00:11:52,970 Így amint tudta, őket válogatni, akkor 374 00:11:52,970 --> 00:11:55,040 képesek voltak mozgósítani ezt a feltételezést. 375 00:11:55,040 --> 00:11:57,040 Tehát ők túl sokat, mint A telefonkönyv példa. 376 00:11:57,040 --> 00:11:59,540 Amint van, még egy kis probléma, mint ez, 377 00:11:59,540 --> 00:12:02,380 A bemenetek előválogatva, tudjuk valóban megtalálja az értéket vitathatatlanul 378 00:12:02,380 --> 00:12:03,130 hatékonyabban. 379 00:12:03,130 --> 00:12:05,800 >> És én nem mondtam el, ha azt válogatni kis és nagy, vagy nagy a kis, 380 00:12:05,800 --> 00:12:08,080 És ez így volt, nagyon ésszerű kezdeni az egyik végén, vagy a másik 381 00:12:08,080 --> 00:12:09,750 hogy valóban úgy találják, hogy célérték. 382 00:12:09,750 --> 00:12:11,400 Szóval köszönöm, hogy Trevor is. 383 00:12:11,400 --> 00:12:13,260 És én propose-- szépen tenni. 384 00:12:13,260 --> 00:12:16,960 Van egy kis klip, valóban, hogy között a kedvenc pillanatait CS50, 385 00:12:16,960 --> 00:12:19,700 ahol néha ezek a demók Nem egészen a terv szerint megy. 386 00:12:19,700 --> 00:12:22,050 És valóban, most én húzta fel a rossz interfész 387 00:12:22,050 --> 00:12:23,508 amellyel az érintőképernyő használatához. 388 00:12:23,508 --> 00:12:24,660 Szóval ez az én hibám volt ott. 389 00:12:24,660 --> 00:12:26,600 >> Szóval ez lehetővé teszi majd a jövő évi csipesz 390 00:12:26,600 --> 00:12:28,570 hogy miért voltam kattintva saját képernyőjén. 391 00:12:28,570 --> 00:12:31,390 De vessünk egy gyors pillantást hogy mi történt tavaly 392 00:12:31,390 --> 00:12:34,770 Jay, aki jött, sok mint Trevor itt, önként, 393 00:12:34,770 --> 00:12:39,380 és ebben a rövid klip, látni fogod hogy ez ugyanaz a demo nem egészen 394 00:12:39,380 --> 00:12:41,074 leleplezik a hasonlóan tanulságokat. 395 00:12:41,074 --> 00:12:41,740 [Videó lejátszás] 396 00:12:41,740 --> 00:12:45,360 -Minden Azt akarom, hogy ne most találni nekem, és nekünk, 397 00:12:45,360 --> 00:12:51,674 Tényleg, a szám 50 egy lépéssel egy időben. 398 00:12:51,674 --> 00:12:52,450 >> -A 50-? 399 00:12:52,450 --> 00:12:53,190 >> -A Száma 50. 400 00:12:53,190 --> 00:12:55,356 És akkor mutatják mi mögött minden ilyen ajtók 401 00:12:55,356 --> 00:12:58,540 egyszerűen érjen hozzá az ujjával. 402 00:12:58,540 --> 00:13:00,910 Basszus. 403 00:13:00,910 --> 00:13:02,870 >> [Nevet] 404 00:13:02,870 --> 00:13:03,806 >> [Lejátszás vége] 405 00:13:03,806 --> 00:13:05,430 David J. MALAN: Úgy, hogy nagyon jól ment. 406 00:13:05,430 --> 00:13:06,796 Ezek voltak a szétválogatás nélküli ajtók. 407 00:13:06,796 --> 00:13:08,670 És Jay, természetesen, találtam túl gyorsan. 408 00:13:08,670 --> 00:13:12,910 Trevor nem sokkal jobb munkát szempontjából egy tanítható pillanatra, 409 00:13:12,910 --> 00:13:15,850 hogy úgy mondjam, ebben az évben hosszabb időt vesz igénybe, hogy megtalálja. 410 00:13:15,850 --> 00:13:17,950 Persze, akkor adta Jay egy második esélyt, 411 00:13:17,950 --> 00:13:20,320 ami által rendezett az ajtók, mint ahogy tettük Trevor, 412 00:13:20,320 --> 00:13:22,300 és Trevor tette szuper jól ebben az időben. 413 00:13:22,300 --> 00:13:26,124 De Jay csinálta fele olyan gyorsan. 414 00:13:26,124 --> 00:13:26,790 [Videó lejátszás] 415 00:13:26,790 --> 00:13:29,650 -A Cél most az, hogy is talál minket száma 50, 416 00:13:29,650 --> 00:13:33,030 de azt algoritmus, és mondja el, hogyan fogsz róla. 417 00:13:33,030 --> 00:13:33,660 >> -OKÉ. 418 00:13:33,660 --> 00:13:35,604 >> -És Ha megtalálja, akkor tartsa a filmet. 419 00:13:35,604 --> 00:13:37,228 Ha nem találja meg, akkor add vissza. 420 00:13:37,228 --> 00:13:38,044 >> -man. 421 00:13:38,044 --> 00:13:38,860 >> -Ó! 422 00:13:38,860 --> 00:13:40,800 >> - [Hallható] OK. 423 00:13:40,800 --> 00:13:46,236 Így fogok, hogy ellenőrizze a végek Először határoztam meg, ha there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Taps] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [Lejátszás vége] 427 00:13:55,729 --> 00:13:56,520 David J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Tehát a válogatás ajtók egyértelműen vezet a nagyobb hatékonyság érdekében. 429 00:13:59,760 --> 00:14:01,680 És így, kétszer olyan gyorsan az, amit akartam ott. 430 00:14:01,680 --> 00:14:03,270 És így Jay szerencséje volt mindkét alkalommal. 431 00:14:03,270 --> 00:14:06,685 És ő is szerencsém volt, hogy az utolsó év, én elrendelte a Blu-ray lemezek 432 00:14:06,685 --> 00:14:07,560 hogy valóban ad ki. 433 00:14:07,560 --> 00:14:09,768 Sajnálom idén is nem volt azonos, Trevor. 434 00:14:09,768 --> 00:14:11,540 De még jobb volt néhány évvel ezelőtt. 435 00:14:11,540 --> 00:14:14,820 És néhányan talán tudják ezt fickó, Sean, aki amikor ő volt a CS50, 436 00:14:14,820 --> 00:14:17,780 megtámadta a pontos Ugyanez a probléma, jóllehet SD, 437 00:14:17,780 --> 00:14:19,360 mint hamarosan látni, vissza a nap. 438 00:14:19,360 --> 00:14:22,622 És rájössz, hogy nem csak hogy ő egy kicsit tovább tart, mint Jay, 439 00:14:22,622 --> 00:14:25,580 egy kicsit hosszabb, mint Trevor, ez volt ténylegesen ezt a csodálatos lehetőséget 440 00:14:25,580 --> 00:14:29,820 hogy vegyenek szinte mindenki a tömegben a la ár megfelelő, ösztönözve 441 00:14:29,820 --> 00:14:31,889 neki, hogy megtalálják a szám, amit kerestek. 442 00:14:31,889 --> 00:14:32,930 Nézzük. hogy egy gyors pillantást. 443 00:14:32,930 --> 00:14:33,320 >> [Videó lejátszás] 444 00:14:33,320 --> 00:14:33,820 >> -OKÉ. 445 00:14:33,820 --> 00:14:36,680 Tehát a feladat itt, Sean, a következő. 446 00:14:36,680 --> 00:14:40,860 Én mögött ezeket a ajtók száma hét. 447 00:14:40,860 --> 00:14:45,120 De élj néhány ilyen ajtók valamint más negatív számok. 448 00:14:45,120 --> 00:14:47,500 És a cél az, hogy úgy gondolja, E felső sorban a számok 449 00:14:47,500 --> 00:14:50,390 mint csak egy tömb, vagy csak szekvenciája darab papír 450 00:14:50,390 --> 00:14:51,510 számokkal mögöttük. 451 00:14:51,510 --> 00:14:55,540 És a cél az, csak használ a felső tömb van, keresse meg a hetes szám. 452 00:14:55,540 --> 00:14:58,570 És mi majd lesz kritika hogyan kezdjen csinálja. 453 00:14:58,570 --> 00:14:59,070 -Minden rendben. 454 00:14:59,070 --> 00:15:00,850 -Find Velünk a hetes szám, kérem. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nem. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Öt, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Nevet] 461 00:15:24,770 --> 00:15:25,910 >> Ez nem egy trükkös kérdés. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Egy. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Nevet] 466 00:15:34,695 --> 00:15:37,861 Ezen a ponton, a pontszám nem túl jó, így akár meg is tartani fog. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Három. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Nevet] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Tovább. 473 00:15:47,774 --> 00:15:50,690 Őszintén szólva, nem tudok segíteni, de csoda, mit is gondol, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Nevet] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Csak a felső sorban, így megvan a három bal. 477 00:15:55,020 --> 00:15:56,200 Szóval rám talál hét. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Nevet] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Hét. 484 00:16:26,946 --> 00:16:28,780 >> [Taps] 485 00:16:28,780 --> 00:16:29,426 >> Minden rendben. 486 00:16:29,426 --> 00:16:30,360 >> [Lejátszás vége] 487 00:16:30,360 --> 00:16:31,840 >> David J. MALAN: így sikerült nézni ezeket egész nap. 488 00:16:31,840 --> 00:16:34,090 És persze, néhány Az idei bemutatók talán 489 00:16:34,090 --> 00:16:36,330 Most a végén a következő évi videó is. 490 00:16:36,330 --> 00:16:39,040 Így most nézzük a ténylegesen összpontosítani algoritmusok 491 00:16:39,040 --> 00:16:42,140 Itt, és nézd meg, mi nem Most kezd hivatalossá 492 00:16:42,140 --> 00:16:46,650 hogyan tudunk menni körülbelül szerzés adatainkat ebbe az állapotba, hogy ez válogatni, 493 00:16:46,650 --> 00:16:50,054 hogy aztán végül, mi is valójában keresni azt hatékonyabban. 494 00:16:50,054 --> 00:16:52,470 És bár megyünk használni viszonylag kis adathalmazok, 495 00:16:52,470 --> 00:16:54,511 mint a nyolc számban vagyunk Van itt a fórumon, 496 00:16:54,511 --> 00:16:58,230 végül ugyanezek az elképzelések alkalmazni 1000 bemenet, egy millió be-, 497 00:16:58,230 --> 00:17:02,100 4 milliárd bemenetek, mert az algoritmusok lesznek alapvetően ugyanaz. 498 00:17:02,100 --> 00:17:05,359 >> És így ez az utolsó lehetőséget önkéntesek ma, 499 00:17:05,359 --> 00:17:09,790 de talán a leginkább érintett az egyik, amelyhez szükség van a nyolc önkéntesek 500 00:17:09,790 --> 00:17:12,960 hogy jöjjön fel és járj minket a folyamata a válogatás, amit hamarosan 501 00:17:12,960 --> 00:17:15,212 legyen a következő zene áll itt. 502 00:17:15,212 --> 00:17:16,170 Hadd kezdjem vissza ide. 503 00:17:16,170 --> 00:17:19,692 >> Tehát az egyik a turquoise-- zöld ez? 504 00:17:19,692 --> 00:17:21,130 Te elkövető? 505 00:17:21,130 --> 00:17:21,630 Kettő. 506 00:17:21,630 --> 00:17:23,069 Gyere le. 507 00:17:23,069 --> 00:17:23,569 OKÉ. 508 00:17:23,569 --> 00:17:24,420 Három. 509 00:17:24,420 --> 00:17:25,400 Négy. 510 00:17:25,400 --> 00:17:27,247 Hadd me-- OK, öt. 511 00:17:27,247 --> 00:17:28,830 Te jelölése alapján a barátod. 512 00:17:28,830 --> 00:17:31,340 Hat, hét, illetve nyolc. 513 00:17:31,340 --> 00:17:32,130 Gyere fel. 514 00:17:32,130 --> 00:17:32,630 Minden rendben. 515 00:17:32,630 --> 00:17:33,190 Köszönöm szépen. 516 00:17:33,190 --> 00:17:33,689 Gyere fel. 517 00:17:33,689 --> 00:17:34,790 Gyere fel. 518 00:17:34,790 --> 00:17:35,330 >> Minden rendben. 519 00:17:35,330 --> 00:17:38,890 Szóval mi van here-- és ez az egyik több kínos is, 520 00:17:38,890 --> 00:17:42,390 mivel ez megköveteli, hogy a humor nekem csak egy kis idő. 521 00:17:42,390 --> 00:17:43,442 Te leszel az első. 522 00:17:43,442 --> 00:17:44,150 Mi a neved? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> David J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Mi a neved? 527 00:17:46,800 --> 00:17:47,140 >> Joseph: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> David J. MALAN: Joseph, Ön a két számot. 529 00:17:49,190 --> 00:17:52,260 >> Serena: Serena, a hármas számú. 530 00:17:52,260 --> 00:17:53,722 Stefan, száma négy. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 David J. MALAN: Cynthia, az ötödik. 533 00:17:57,548 --> 00:17:58,452 [Hallhatatlan] 534 00:17:58,452 --> 00:17:59,618 David J. MALAN: [hallható]. 535 00:17:59,618 --> 00:18:00,391 David, a hatos. 536 00:18:00,391 --> 00:18:00,890 Matt: Matt. 537 00:18:00,890 --> 00:18:02,160 David J. MALAN: Matt száma hét. 538 00:18:02,160 --> 00:18:02,850 És? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> David J. MALAN: Waverly, száma nyolc. 541 00:18:04,470 --> 00:18:04,970 Minden rendben. 542 00:18:04,970 --> 00:18:06,510 Ha could-- Hoppá. 543 00:18:06,510 --> 00:18:08,820 Ha az összes, mint a első kihívás, ott 544 00:18:08,820 --> 00:18:10,820 Nyolc zenepavilonokkal Itt a közönség felé. 545 00:18:10,820 --> 00:18:14,200 Ha lehetne tenni a számok ezek zene áll, oly módon, 546 00:18:14,200 --> 00:18:16,560 hogy közvetlenül az ugyanolyan számokat a táblán. 547 00:18:16,560 --> 00:18:19,560 Úgyhogy győződjön meg magatokat kinézni, hogy a teszed a szám a következő zene 548 00:18:19,560 --> 00:18:21,960 Itt áll. 549 00:18:21,960 --> 00:18:25,980 Kiváló eddig. 550 00:18:25,980 --> 00:18:26,600 >> Kitűnő. 551 00:18:26,600 --> 00:18:26,890 OKÉ. 552 00:18:26,890 --> 00:18:29,556 Tehát most, megyünk kérni a kérdést néhány különböző módokon. 553 00:18:29,556 --> 00:18:31,610 Hogyan tudjuk járni válogatás ezek az emberek itt? 554 00:18:31,610 --> 00:18:34,500 Mert volt néhány megközelítés korábban, ahol voltunk 555 00:18:34,500 --> 00:18:36,360 fajta, hogy két különböző vödrök. 556 00:18:36,360 --> 00:18:38,842 És akkor általában piecing dolgokat együtt. 557 00:18:38,842 --> 00:18:41,050 Amint láttuk, a két szám hogy összetartoznak, 558 00:18:41,050 --> 00:18:41,975 rakjuk őket össze. 559 00:18:41,975 --> 00:18:43,350 Két betű, hogy összetartozunk. 560 00:18:43,350 --> 00:18:45,058 >> De lássuk, ha Nem formát ennek, 561 00:18:45,058 --> 00:18:48,044 hogy mi végső soron néhány pszeudo-kód lesz, 562 00:18:48,044 --> 00:18:49,710 amellyel meg lehet oldani ezeket a problémákat. 563 00:18:49,710 --> 00:18:51,870 Szóval most én keresem ki ezeket a számokat itt. 564 00:18:51,870 --> 00:18:55,030 És látok egy csomó hibát. 565 00:18:55,030 --> 00:18:57,750 Végül, szeretnék egyet a bal és nyolc a jobb oldalon. 566 00:18:57,750 --> 00:19:00,650 >> És így nézem E két, négy és két. 567 00:19:00,650 --> 00:19:02,930 És mi a probléma, nyilván? 568 00:19:02,930 --> 00:19:04,261 Igen. 569 00:19:04,261 --> 00:19:04,760 Na. 570 00:19:04,760 --> 00:19:07,160 Két nyilván szó előtt Négy, hogy tudd, mi? 571 00:19:07,160 --> 00:19:10,210 Először is hadd vessen egy kapzsi megközelítést, ha úgy tetszik, ugyanúgy, mint probléma 572 00:19:10,210 --> 00:19:13,790 állítsa one-- ha visszaemlékeztek a Standard Edition Probléma Set One, 573 00:19:13,790 --> 00:19:16,820 ahol én csak helyben megoldani a problémát ez itt előttem 574 00:19:16,820 --> 00:19:17,690 és nézd meg, hova vezet engem. 575 00:19:17,690 --> 00:19:17,870 >> OKÉ. 576 00:19:17,870 --> 00:19:20,161 Tehát két és négy, hadd menjen előre, és csak csere ti ketten. 577 00:19:20,161 --> 00:19:22,400 Ha fizikailag mozgatni magad és papír, 578 00:19:22,400 --> 00:19:25,040 Úgy tűnik, hogy ütött az listához jobb állapotban. 579 00:19:25,040 --> 00:19:26,330 >> Most, hogy jók. 580 00:19:26,330 --> 00:19:28,480 Megyek lépni, négy és hat, jól néz ki. 581 00:19:28,480 --> 00:19:29,110 Nem probléma. 582 00:19:29,110 --> 00:19:30,440 Hat és nyolc, az OK gombra. 583 00:19:30,440 --> 00:19:31,860 Nyolc és egy másik probléma. 584 00:19:31,860 --> 00:19:34,750 Mert ami igaz, körülbelül nyolc és egyet? 585 00:19:34,750 --> 00:19:36,990 Egy szó nyolc előtt, és így mit tegyünk? 586 00:19:36,990 --> 00:19:38,090 Nézzük cserélni a két. 587 00:19:38,090 --> 00:19:39,316 Egy-nyolc. 588 00:19:39,316 --> 00:19:40,690 És most, fogok tartani fog. 589 00:19:40,690 --> 00:19:42,030 Én fogom tartani előretekintve. 590 00:19:42,030 --> 00:19:42,840 És lássuk, mi történik. 591 00:19:42,840 --> 00:19:44,680 Nyolc és három, a Természetesen elromlott. 592 00:19:44,680 --> 00:19:45,815 Nézzük csere. 593 00:19:45,815 --> 00:19:46,940 Nyolc és hét, természetesen. 594 00:19:46,940 --> 00:19:47,481 Nem működik. 595 00:19:47,481 --> 00:19:48,280 Nézzük csere. 596 00:19:48,280 --> 00:19:49,940 Nyolc és öt, persze, hadd csere. 597 00:19:49,940 --> 00:19:50,560 Minden rendben. 598 00:19:50,560 --> 00:19:51,880 Lista. 599 00:19:51,880 --> 00:19:53,060 Igen? 600 00:19:53,060 --> 00:19:54,280 >> OK, nyilván nem. 601 00:19:54,280 --> 00:19:55,860 De ez egy kicsit jobb, ugye? 602 00:19:55,860 --> 00:19:57,270 Mert észre, hogy mi történt. 603 00:19:57,270 --> 00:20:01,749 Minden alkalommal, amikor végre a swap, egy kisebb számú fajta főzött, hogy így, 604 00:20:01,749 --> 00:20:03,790 és minél nagyobb számú átszűrődő így, vagy mi 605 00:20:03,790 --> 00:20:06,880 kezdeni azzal vezetünk a balra vagy vezetünk a jobb. 606 00:20:06,880 --> 00:20:10,080 >> Most, hogy ez nem elég, mert a legjobb egy számot talán 607 00:20:10,080 --> 00:20:11,990 költözött egy helyen előre, vagy a legrosszabb esetben, 608 00:20:11,990 --> 00:20:13,880 Számos volna költözött egy helyen további. 609 00:20:13,880 --> 00:20:16,369 Szóval tudod mit, ez a fajta A nagyon jól működött eddig. 610 00:20:16,369 --> 00:20:17,410 Hadd próbálja meg újra. 611 00:20:17,410 --> 00:20:18,880 Két és négy, ők az OK gombra. 612 00:20:18,880 --> 00:20:20,180 Négy és hat, ők az OK gombra. 613 00:20:20,180 --> 00:20:21,790 Hat, egy, elromlott. 614 00:20:21,790 --> 00:20:23,007 Úgyhogy cserélni ti ketten. 615 00:20:23,007 --> 00:20:25,840 És most, észre a probléma vagy már egy kicsit jobban meg újra. 616 00:20:25,840 --> 00:20:27,006 Hat és három, elromlott. 617 00:20:27,006 --> 00:20:28,100 Nézzük cserélni ti ketten. 618 00:20:28,100 --> 00:20:29,730 Hat-hét, te jó. 619 00:20:29,730 --> 00:20:32,230 Hét és öt, persze, elromlott. 620 00:20:32,230 --> 00:20:33,920 Hét és nyolc, annak érdekében. 621 00:20:33,920 --> 00:20:36,470 És most, talán kell Ehhez még néhány alkalommal. 622 00:20:36,470 --> 00:20:39,830 És valóban, gondolom magatoknak Talán hányszor maximálisan 623 00:20:39,830 --> 00:20:41,330 Lehet, hogy én már járni oda-vissza? 624 00:20:41,330 --> 00:20:42,390 >> Majd vissza kell térni. 625 00:20:42,390 --> 00:20:43,700 Tehát két és négy még mindig OK. 626 00:20:43,700 --> 00:20:44,940 Négy és egy, dehogy. 627 00:20:44,940 --> 00:20:45,747 Nos, nézzük csere. 628 00:20:45,747 --> 00:20:47,830 És ismét, észre vizuálisan az egyik fajta fortyogó 629 00:20:47,830 --> 00:20:49,163 balra, ahol lennie kell. 630 00:20:49,163 --> 00:20:50,010 Négy és három csere. 631 00:20:50,010 --> 00:20:51,330 Négy-hat. 632 00:20:51,330 --> 00:20:53,100 Hat és öt csere. 633 00:20:53,100 --> 00:20:53,959 Hat-hét. 634 00:20:53,959 --> 00:20:55,000 Hét és nyolc jók. 635 00:20:55,000 --> 00:20:55,500 >> Jó. 636 00:20:55,500 --> 00:20:58,460 Mi megvagyunk, még jobb. 637 00:20:58,460 --> 00:20:59,130 Tehát lássuk. 638 00:20:59,130 --> 00:21:00,940 Most már két és egy. 639 00:21:00,940 --> 00:21:02,520 Természetesen cserélni. 640 00:21:02,520 --> 00:21:07,520 Két és három, három és négy, négy és öt, hat, hét, hét és nyolc. 641 00:21:07,520 --> 00:21:08,020 Jó. 642 00:21:08,020 --> 00:21:08,730 És tudod mit? 643 00:21:08,730 --> 00:21:11,190 Mert elkövettem egy változás van, hadd tegye józanság csekket. 644 00:21:11,190 --> 00:21:13,023 Hadd menjen végig vissza az elejére. 645 00:21:13,023 --> 00:21:13,680 OKÉ. 646 00:21:13,680 --> 00:21:14,750 Az egyik, two-- Ja, látod? 647 00:21:14,750 --> 00:21:15,870 Valami nem volt rendben. 648 00:21:15,870 --> 00:21:18,420 Három, négy, öt, hat, hét, nyolc. 649 00:21:18,420 --> 00:21:21,920 És ebben az utolsó lépés, a kényelmes az én most 650 00:21:21,920 --> 00:21:23,830 azt állítva, hogy válogatni? 651 00:21:23,830 --> 00:21:24,330 OKÉ. 652 00:21:24,330 --> 00:21:25,880 Vizuálisan, ez teljesen igaz. 653 00:21:25,880 --> 00:21:28,410 De funkcionálisan, mit nem is csak úgy történnek 654 00:21:28,410 --> 00:21:31,870 ebben az utolsó lépés, amely lehetővé teszi annak igazolására, hogy ez a lista valóban 655 00:21:31,870 --> 00:21:32,660 válogatni? 656 00:21:32,660 --> 00:21:34,477 >> Mit csináltam, vagy nem tudja ezt az utolsó menetben? 657 00:21:34,477 --> 00:21:35,810 Közönség: Nem volt változás. 658 00:21:35,810 --> 00:21:36,120 David J. MALAN: Sajnáljuk? 659 00:21:36,120 --> 00:21:37,070 Közönség: Nincs változás. 660 00:21:37,070 --> 00:21:38,653 David J. MALAN: Nem volt változás. 661 00:21:38,653 --> 00:21:41,947 Így lenne hülye vagyok, hogy Ehhez ugyanazt az algoritmust újra 662 00:21:41,947 --> 00:21:43,780 ha nem tesz megváltoztatja az első alkalommal. 663 00:21:43,780 --> 00:21:45,160 És az állam nem változott. 664 00:21:45,160 --> 00:21:47,576 Bizonyára nem fogok tenni bármilyen változás a második alkalommal. 665 00:21:47,576 --> 00:21:49,820 És így, most már biztonságban mondani, lista. 666 00:21:49,820 --> 00:21:52,069 >> És valóban, ez most valami, amit akkor általában 667 00:21:52,069 --> 00:21:56,900 Hívás buborékos rendezést, amely szerint a páros, korrigálta a hibákat újra, 668 00:21:56,900 --> 00:22:00,210 és újra, és újra, és meg menj oda-vissza, 669 00:22:00,210 --> 00:22:03,370 és oda-vissza, amíg meg nem hogy nincs ilyen csereügyletek, ekkor 670 00:22:03,370 --> 00:22:07,089 Ön biztos lehet benne, igen, én befejezte rögzítéséről az összes hibát. 671 00:22:07,089 --> 00:22:08,630 Nézzük reset és megpróbál egy másik megközelítés. 672 00:22:08,630 --> 00:22:11,590 Ha a srácok mehet vissza A megrendelés volt egy perce 673 00:22:11,590 --> 00:22:13,780 amely úgy nézett ki, mint ez. 674 00:22:13,780 --> 00:22:17,640 Most, vessünk egy megközelítést a kicsit több, mint a vizsgán könyvet, 675 00:22:17,640 --> 00:22:21,122 ahol voltunk állandóan kiválasztja a betűvel 676 00:22:21,122 --> 00:22:22,830 hogy azt a fajta akarta foglalkozni másikra. 677 00:22:22,830 --> 00:22:26,420 Talán egy nagy levél, mint az A, illetve az alacsony levelet Z. 678 00:22:26,420 --> 00:22:28,170 >> Szóval mindenki vissza ebben a sorrendben. 679 00:22:28,170 --> 00:22:29,800 És most hadd csináljam ezt. 680 00:22:29,800 --> 00:22:34,880 Lássuk, tudom, hogy van nyolc számból itt. 681 00:22:34,880 --> 00:22:37,410 Megyek megy előre, és Csak szándékosan válasszon 682 00:22:37,410 --> 00:22:38,520 A legkisebb eleme. 683 00:22:38,520 --> 00:22:38,760 Jobb? 684 00:22:38,760 --> 00:22:39,801 Úgy tűnik, ez az intuitív is. 685 00:22:39,801 --> 00:22:42,560 Miért nem találom a legkisebb elemet, tedd ahová tartozik, 686 00:22:42,560 --> 00:22:45,280 akkor kap a következő legkisebb eleme, tedd ez, ahová tartozik, és csak ismételni. 687 00:22:45,280 --> 00:22:46,820 >> Mert ösztönösen, hogy is működnie kell. 688 00:22:46,820 --> 00:22:48,441 Tehát négy, ez egy nagyon kevés. 689 00:22:48,441 --> 00:22:49,940 Megyek, hogy emlékezzen, ahol ez. 690 00:22:49,940 --> 00:22:50,523 Várj egy percet. 691 00:22:50,523 --> 00:22:51,577 Két kisebb. 692 00:22:51,577 --> 00:22:53,910 Hadd ne feledje, ha két van, és felejtse el a négy. 693 00:22:53,910 --> 00:22:55,050 Majd foglalkozik, hogy később. 694 00:22:55,050 --> 00:22:56,460 Hat, nem vagyok érdekelt. 695 00:22:56,460 --> 00:22:57,810 Nyolc, nem vagyok érdekelt. 696 00:22:57,810 --> 00:22:59,780 Az egyik az én új kis számot. 697 00:22:59,780 --> 00:23:01,470 Így fogok visszaemlékezni, hol az egyik. 698 00:23:01,470 --> 00:23:02,534 Három, nem érdekli. 699 00:23:02,534 --> 00:23:03,450 Hét, nem érdekli. 700 00:23:03,450 --> 00:23:04,530 Öt, nem érdekli. 701 00:23:04,530 --> 00:23:07,390 >> Tehát nélkül esett le A színpadon idén, 702 00:23:07,390 --> 00:23:09,890 Megyek megragad száma one-- és mi volt a neve? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> David J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 És ha tudna csatlakozni hozzám az elején a lista, 706 00:23:13,540 --> 00:23:14,870 mondjuk, hol tartoznak. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- mi a neved? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> David J. MALAN: Stefan van az út. 710 00:23:18,191 --> 00:23:23,490 Szóval mielőtt Stefan megoldja ezt probléma, mit tegyünk? 711 00:23:23,490 --> 00:23:25,412 Mit csináljunk Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Közönség: [hallható]. 713 00:23:27,269 --> 00:23:28,060 David J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Így lehet megtenni. 715 00:23:28,850 --> 00:23:31,730 Mi lehetne egyfajta vegye Stefan és ő négy, és csak tedd egy változóban 716 00:23:31,730 --> 00:23:33,530 és tartsd meg az bizonyos mennyiségű időt, 717 00:23:33,530 --> 00:23:35,220 ezáltal teret számú. 718 00:23:35,220 --> 00:23:36,280 És ez nem is rossz. 719 00:23:36,280 --> 00:23:39,270 Én azt sugallhatja, hogy miért nem mi csak tesz Stefan itt? 720 00:23:39,270 --> 00:23:41,610 Miért lehet ez sérti az egyik Az ötletek kezdtük 721 00:23:41,610 --> 00:23:44,830 beszélünk utoljára, a múlt héten? 722 00:23:44,830 --> 00:23:45,330 Igen? 723 00:23:45,330 --> 00:23:45,740 >> Közönség: [hallható]. 724 00:23:45,740 --> 00:23:46,860 >> David J. MALAN: Nincs indexe érte. 725 00:23:46,860 --> 00:23:49,735 Ha úgy gondolja, ennek, sőt, mint tömb, ez olyan, mint negatív, 726 00:23:49,735 --> 00:23:52,900 így nincs memória ténylegesen Itt, ha ez valóban egy olyan tömb, 727 00:23:52,900 --> 00:23:55,090 mint mi nyilvánította a múlt héten előadást. 728 00:23:55,090 --> 00:23:56,250 Tehát nem ezt. 729 00:23:56,250 --> 00:23:57,340 Lehet, hogy tárolja egy változóban. 730 00:23:57,340 --> 00:23:57,820 >> Vagy tudod mit? 731 00:23:57,820 --> 00:23:59,153 Hallottam, hogy valaki mást javasoljuk. 732 00:23:59,153 --> 00:24:01,020 Mi mást tehettünk volna Stefan? 733 00:24:01,020 --> 00:24:03,770 Miért nem csak kilakoltatására neki, és tedd őt, ahol számú volt. 734 00:24:03,770 --> 00:24:05,170 Tehát, ha azt szeretnénk, hogy menjen oda. 735 00:24:05,170 --> 00:24:07,300 És valóban, ez egy nagyon jó megoldás. 736 00:24:07,300 --> 00:24:10,480 Most egyrészt, én már ilyen A tett a probléma rosszabb. 737 00:24:10,480 --> 00:24:13,650 Négy most távolabb re, ahol lennie kell. 738 00:24:13,650 --> 00:24:14,900 Meg kell felé a másikon. 739 00:24:14,900 --> 00:24:16,100 >> De tudod mit? 740 00:24:16,100 --> 00:24:17,630 Hogy lehetett volna a balszerencse. 741 00:24:17,630 --> 00:24:18,822 Talán nyolcas itt volt. 742 00:24:18,822 --> 00:24:20,530 És igen, talán mi lenne ütött szerencsés, 743 00:24:20,530 --> 00:24:22,460 és tolta nyolc közelebb a végére. 744 00:24:22,460 --> 00:24:24,710 Így a végén a nap, ez a fajta minden átlagosan ki. 745 00:24:24,710 --> 00:24:26,085 Nem kell törődnünk négy. 746 00:24:26,085 --> 00:24:29,400 Csak az érdekel, most is kiválasztja a legkisebb eleme. 747 00:24:29,400 --> 00:24:32,030 >> És most, mit fogok tennie, hogy felejtse el a number one 748 00:24:32,030 --> 00:24:35,160 véglegesen, mert tudom, hogy a listát a hátam mögött most válogatni. 749 00:24:35,160 --> 00:24:36,720 Szóval a lista a korábban mérete nyolc. 750 00:24:36,720 --> 00:24:37,720 Most, ez a méret a hét. 751 00:24:37,720 --> 00:24:40,340 Szóval a probléma egyre alacsonyabb, ámbár lineárisan. 752 00:24:40,340 --> 00:24:43,022 Tehát most, megyek ki a jelenlegi legkisebb eleme, kettő. 753 00:24:43,022 --> 00:24:46,520 Hat, nyolc, négy, három, hét, öt. 754 00:24:46,520 --> 00:24:47,770 Ez volt a legkisebb eleme. 755 00:24:47,770 --> 00:24:49,416 Szóval mit fogok csinálni with-- mi volt a neve? 756 00:24:49,416 --> 00:24:49,760 >> Joseph: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> David J. MALAN: Joseph? 758 00:24:50,085 --> 00:24:52,000 Fogunk hagyja József helyére. 759 00:24:52,000 --> 00:24:54,842 Most megyek, mintha hogy ezek a srácok are-- is, 760 00:24:54,842 --> 00:24:56,550 Tudom, hogy ez a két már rendezve. 761 00:24:56,550 --> 00:24:58,424 Nézzük most összpontosítani fennmaradó lista. 762 00:24:58,424 --> 00:25:00,080 Hat jelenlegi legkisebb. 763 00:25:00,080 --> 00:25:01,190 Nyolc nagyobb. 764 00:25:01,190 --> 00:25:02,970 Négy most a jelenlegi legkisebb. 765 00:25:02,970 --> 00:25:04,762 Három most a jelenlegi legkisebb. 766 00:25:04,762 --> 00:25:07,720 És így most fogom kiválasztani a három, aki is-- mi is a neved? 767 00:25:07,720 --> 00:25:08,190 Serena: Serena. 768 00:25:08,190 --> 00:25:10,620 David J. MALAN: Serena, ha tehetnéd fogd meg a számot és swap with-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 David J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Gyere vissza, és mi vagyunk fog cserélni a kettő között. 772 00:25:15,220 --> 00:25:17,360 És most, tegyük ezt a robotpilóta. 773 00:25:17,360 --> 00:25:21,589 Én megyek, és hagyja, hogy a srácok válassza ki a következő legkisebb eleme. 774 00:25:21,589 --> 00:25:22,380 Dun, ordas, ordas, ordas. 775 00:25:22,380 --> 00:25:24,560 A négyes számú, mit tegyünk? 776 00:25:24,560 --> 00:25:26,261 Kitűnő. 777 00:25:26,261 --> 00:25:27,760 Most megyek, hogy egy másik labdát. 778 00:25:27,760 --> 00:25:28,590 Dun, ordas, ordas, ordas. 779 00:25:28,590 --> 00:25:31,465 Látom ötös a következő kisebb. 780 00:25:31,465 --> 00:25:32,840 Most megyek újabb passz. 781 00:25:32,840 --> 00:25:33,631 Dun, ordas, ordas, ordas. 782 00:25:33,631 --> 00:25:34,880 Hat a legkisebb. 783 00:25:34,880 --> 00:25:35,520 Jó. 784 00:25:35,520 --> 00:25:36,585 Hét a legkisebb. 785 00:25:36,585 --> 00:25:37,085 Nincs változás. 786 00:25:37,085 --> 00:25:38,630 Nyolc a legkisebb. 787 00:25:38,630 --> 00:25:39,170 Kész. 788 00:25:39,170 --> 00:25:43,900 >> Tehát amit az imént végzett iteratív kiválasztunk egy elemet a másik után 789 00:25:43,900 --> 00:25:47,230 A végre valami, ami mi vagyunk lesz, hogy hivatalossá a kiválasztási sorrend. 790 00:25:47,230 --> 00:25:49,120 És ez talán még egyszerűbb elmagyarázni, 791 00:25:49,120 --> 00:25:51,310 abban a szó szoros értelmében minden, amit akarok csak tartani 792 00:25:51,310 --> 00:25:54,700 oda-vissza végig a listát kiválasztásával, a következő legkisebb eleme, 793 00:25:54,700 --> 00:25:55,720 amíg kész. 794 00:25:55,720 --> 00:25:58,650 >> Szóval ez még egyszerűbb, talán ösztönösen, mint az utolsó. 795 00:25:58,650 --> 00:26:00,020 Próbáljuk az egyik utolsó. 796 00:26:00,020 --> 00:26:03,060 Ha ti is vissza magatokat a következő pozíciók 797 00:26:03,060 --> 00:26:08,600 még egyszer utoljára, lássuk, ha nem tudjuk Most hivatalossá egy másik megközelítés. 798 00:26:08,600 --> 00:26:12,857 Tény, akar valaki ott szeretném javasolni 799 00:26:12,857 --> 00:26:14,440 hogy mást elmehetnénk csinálja ezt? 800 00:26:14,440 --> 00:26:17,439 Anélkül dobált ki hívószavak vagy rendezési A választ a már ismert, 801 00:26:17,439 --> 00:26:19,689 Csak ösztönösen, mit tehetünk? 802 00:26:19,689 --> 00:26:21,635 >> Közönség: [hallható]. 803 00:26:21,635 --> 00:26:22,510 David J. MALAN: Igen. 804 00:26:22,510 --> 00:26:24,620 Szóval van néhány nagy intuíció van. 805 00:26:24,620 --> 00:26:28,020 Jó dolgok fognak történni, eddig a számítógép-tudomány, ha elosztjuk 806 00:26:28,020 --> 00:26:30,832 és meghódítsa a problémát a választóvonal félbe, és fele-fele. 807 00:26:30,832 --> 00:26:32,540 És így valóban, indulhasson erre. 808 00:26:32,540 --> 00:26:35,754 És valóban, hogy ez lesz, akkor lásd, az egyik legjobb megoldás még. 809 00:26:35,754 --> 00:26:37,420 De térjünk vissza, hogy nemsokára. 810 00:26:37,420 --> 00:26:40,500 Tény, hogy fogunk csinálni hogy egy kicsit később ezen a héten. 811 00:26:40,500 --> 00:26:42,180 Mi mást lehet tennünk azért, hogy megoldja ezt? 812 00:26:42,180 --> 00:26:44,647 Szóval itt mindenki a látszólag véletlenszerű sorrendben. 813 00:26:44,647 --> 00:26:45,230 Tudod mit? 814 00:26:45,230 --> 00:26:48,320 Ahelyett, hogy menjen előre és hátra, oda-vissza, oda-vissza 815 00:26:48,320 --> 00:26:50,624 minden egyes alkalommal, ez az érzés Csinálok a sok gyaloglás. 816 00:26:50,624 --> 00:26:52,790 Miért nem tudok csak kezdődik az elején a lista, 817 00:26:52,790 --> 00:26:54,960 és csak tedd négy ahova tartozik? 818 00:26:54,960 --> 00:26:59,680 Szóval hadd vállalnak a pillanatban, hogy listámon csak az első eleme. 819 00:26:59,680 --> 00:27:04,937 A négy válogatni ebben a pillanatban az időben, ha minden érdekel, hogy itt minden? 820 00:27:04,937 --> 00:27:06,520 Ez a fajta triviálisan igaz, ugye? 821 00:27:06,520 --> 00:27:10,000 Mint a listát, amely egy számot, és ez a szám négy nyilvánvalóan rendezve. 822 00:27:10,000 --> 00:27:13,070 >> Szóval hadd kikötik hogy ez a lista. 823 00:27:13,070 --> 00:27:15,090 De most már a többi ezt a listát. 824 00:27:15,090 --> 00:27:17,240 Tehát most, találkozom kettő. 825 00:27:17,240 --> 00:27:21,690 Hol két nyilvánvalóan tartoznak tekintetében négy? 826 00:27:21,690 --> 00:27:22,580 Mielőtt négy. 827 00:27:22,580 --> 00:27:23,862 Szóval mit lehet itt csinálni? 828 00:27:23,862 --> 00:27:24,820 Mi is a neved? 829 00:27:24,820 --> 00:27:25,090 >> Joseph: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> David J. MALAN: Joseph, ha tudna lépést hátra 831 00:27:26,030 --> 00:27:27,790 egy pillanatra a saját számát. 832 00:27:27,790 --> 00:27:31,130 És most mi legyen Stefan itt csinálni? 833 00:27:31,130 --> 00:27:33,720 Nézzük elmozdulás Stefan ide. 834 00:27:33,720 --> 00:27:35,520 És most, hadd Joseph jönnek ide. 835 00:27:35,520 --> 00:27:39,660 És most hadd állítják, hogy itt minden van rendezve. 836 00:27:39,660 --> 00:27:42,474 Tehát, hasonló eredménnyel, de egy alapvetően más megközelítést. 837 00:27:42,474 --> 00:27:44,140 Én még nem is látszott, mi van odalent. 838 00:27:44,140 --> 00:27:46,310 Csak azt figyelembe az elemek mivel ők a kezembe, 839 00:27:46,310 --> 00:27:47,240 és foglalkoznak velük. 840 00:27:47,240 --> 00:27:48,330 >> Tehát most, látom a hatos. 841 00:27:48,330 --> 00:27:51,110 Hol száma hat tartozik? 842 00:27:51,110 --> 00:27:53,250 Van két, négy, hat. 843 00:27:53,250 --> 00:27:54,800 Pontosan hol van most. 844 00:27:54,800 --> 00:27:57,750 Szóval hagyjuk, hogy egyedül, és most azt állítják, hogy ez a lista egy részét 845 00:27:57,750 --> 00:27:58,772 most válogatni. 846 00:27:58,772 --> 00:28:01,230 És igen, ez olyan, alapvetően különbözik, hogy én csak 847 00:28:01,230 --> 00:28:05,230 halad át a listát itt lineárisan, és én soha nem megduplázva vissza. 848 00:28:05,230 --> 00:28:05,730 Igen. 849 00:28:05,730 --> 00:28:06,230 Minden rendben. 850 00:28:06,230 --> 00:28:08,190 Tehát nyolc, ahol tartozol? 851 00:28:08,190 --> 00:28:08,730 Pont itt. 852 00:28:08,730 --> 00:28:09,310 Tökéletes. 853 00:28:09,310 --> 00:28:10,210 Tehát most, az egyik. 854 00:28:10,210 --> 00:28:10,900 UH Oh. 855 00:28:10,900 --> 00:28:13,010 Ez olyan, mint ez lesz drága. 856 00:28:13,010 --> 00:28:15,690 Most, az előző algoritmust, Én csak cserélték az embereket. 857 00:28:15,690 --> 00:28:18,648 Szóval lehet, hogy őt egészen a az elején, de utána költözött József. 858 00:28:18,648 --> 00:28:21,450 De ha mozgok József, most mi lesz baj? 859 00:28:21,450 --> 00:28:24,250 >> Most, én már egyfajta undone-- voltam tett egy lépést előre, majd 860 00:28:24,250 --> 00:28:26,300 egy lépést hátra, mert most Joseph lenne elromlott. 861 00:28:26,300 --> 00:28:26,830 Tehát lássuk ezt. 862 00:28:26,830 --> 00:28:29,150 Ha lehetne számú és lépjen vissza egy pillanatra. 863 00:28:29,150 --> 00:28:30,490 Hogyan tudjuk mi put-- volt a neved? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> David J. MALAN: Annan helyett? 866 00:28:32,610 --> 00:28:36,091 Mit kell történnie tekintetében két, négy, hat, illetve nyolc? 867 00:28:36,091 --> 00:28:37,570 Mindannyian kell váltani. 868 00:28:37,570 --> 00:28:42,590 Tehát, ha a nyolc szeretne váltani először, majd hat, majd négy, majd kettő. 869 00:28:42,590 --> 00:28:45,380 És akkor Annan, ha azt szívesen jövök ide, jó. 870 00:28:45,380 --> 00:28:47,760 De itt, most már csak fajta árat fizetett 871 00:28:47,760 --> 00:28:49,510 egy másik pontján az algoritmus. 872 00:28:49,510 --> 00:28:52,550 Mivel utoljára a kiválasztási sort, és még buborékos rendezést, 873 00:28:52,550 --> 00:28:54,700 Sétálok vissza oda, oda-vissza, 874 00:28:54,700 --> 00:28:58,360 ami minden bizonnyal összeadjuk idő-bölcs, és szó szerint lépésenként. 875 00:28:58,360 --> 00:29:00,660 >> Behelyezés sort, az első pillantásra úgy néz ki, mintha 876 00:29:00,660 --> 00:29:05,150 szuper okosabb, az, hogy én vagyok hogy lassú, fokozatos haladást, 877 00:29:05,150 --> 00:29:07,120 de nem fogom ezt oda-vissza. 878 00:29:07,120 --> 00:29:09,410 De ha valaki valóban elromlott, értesítés 879 00:29:09,410 --> 00:29:10,840 az összes munka csak meg kellett csinálni. 880 00:29:10,840 --> 00:29:14,750 Azt kellett költözniük a fele a listát csak azért, hogy legyen hely az első számú. 881 00:29:14,750 --> 00:29:16,790 Tehát ugyanazt az összeget A munka eddig is 882 00:29:16,790 --> 00:29:18,690 úgy érzi, csak egy másik típusú munkát. 883 00:29:18,690 --> 00:29:19,370 >> Folytassuk. 884 00:29:19,370 --> 00:29:22,657 Tehát most már tudjuk, hogy mindenki egy-nyolc sorrendje. 885 00:29:22,657 --> 00:29:23,740 Itt van három. 886 00:29:23,740 --> 00:29:25,864 Ha szeretné, hogy vegye fel A hármas számú, lépjen vissza egyet. 887 00:29:25,864 --> 00:29:28,260 És mit srácok kell tenned? 888 00:29:28,260 --> 00:29:28,760 Ja. 889 00:29:28,760 --> 00:29:33,070 Szóval ez egy másik egy, kettő, három lépésben. 890 00:29:33,070 --> 00:29:36,010 Három egység, ameddig csak költség Számomra úgy, hogy a három most illik. 891 00:29:36,010 --> 00:29:37,460 Végül hét. 892 00:29:37,460 --> 00:29:39,730 >> Menjünk előre, és Ön egy lépést hátra. 893 00:29:39,730 --> 00:29:42,780 Ez csak akkor fog kerülni nekünk Egy egységnyi idő alatt, de ez rendben van. 894 00:29:42,780 --> 00:29:44,170 És most, öt meg fog egy kicsit drágább. 895 00:29:44,170 --> 00:29:45,340 Ha azt szeretné, hogy lépjen vissza. 896 00:29:45,340 --> 00:29:48,380 Meg kell mozgatni nyolc, valamint hét, illetve hat. 897 00:29:48,380 --> 00:29:50,749 És akkor mindenki őt rendezve. 898 00:29:50,749 --> 00:29:52,290 Szóval egy nagy kezét, hogy önkénteseink itt. 899 00:29:52,290 --> 00:29:53,554 Köszönöm szépen. 900 00:29:53,554 --> 00:29:56,220 >> [Taps] 901 00:29:56,220 --> 00:29:56,860 >> Köszönök mindent. 902 00:29:56,860 --> 00:29:57,520 Köszönök mindent. 903 00:29:57,520 --> 00:30:02,940 Nézzük most, hogy mennyire költséges minden volt. 904 00:30:02,940 --> 00:30:06,210 Nézzük meg talán a legegyszerűbb ilyen, buborékos rendezést. 905 00:30:06,210 --> 00:30:09,950 És én azt mondom legegyszerűbb, csak azért, mert meg lehet oldani, hogy mohón mellett csak 906 00:30:09,950 --> 00:30:11,660 erősít a páros probléma van. 907 00:30:11,660 --> 00:30:13,720 Fix páros probléma itt, újra és újra 908 00:30:13,720 --> 00:30:17,680 és újra ismételve annyi ahányszor csak tényleg kell. 909 00:30:17,680 --> 00:30:21,050 >> Így kiderül, hogy a egy buborék rendezés, valamint, 910 00:30:21,050 --> 00:30:25,820 hány lépést kell lennem ahhoz, hogy a Az első lépés az, hogy algoritmus? 911 00:30:25,820 --> 00:30:30,850 Talán take-- nézzük see-- egy, kettő, három, négy, öt, hat, hét. 912 00:30:30,850 --> 00:30:32,190 És ott van a nyolc elem van. 913 00:30:32,190 --> 00:30:35,280 Tehát ez olyan, mint n mínusz 1 lépéseket hogy a lista elején 914 00:30:35,280 --> 00:30:36,380 hogy a végén a lista. 915 00:30:36,380 --> 00:30:41,350 >> De kiválasztási sorrend, emlékszem, hogy én vagyok az elemek kiválasztása újra és újra 916 00:30:41,350 --> 00:30:44,590 és újra, hogy ez a legkisebb, Leteszem a helyén, 917 00:30:44,590 --> 00:30:46,616 de aztán nem vagyok keres mögöttem újra. 918 00:30:46,616 --> 00:30:49,490 Tehát úgy gondolom, hogy ez egy kicsit világosabb akkor ez az első alkalom, talán 919 00:30:49,490 --> 00:30:52,680 meg kell tennie minden n mínusz 1 lépéseket hogy megtalálják a legkisebb eleme. 920 00:30:52,680 --> 00:30:55,920 Aztán tedd a helyére, és én kilakoltatására aki itt volt korábban. 921 00:30:55,920 --> 00:30:57,500 >> De aztán nem kell folyamatosan nézi ezt az elemet, 922 00:30:57,500 --> 00:30:59,040 mert tudom, hogy ez Már a legkisebb. 923 00:30:59,040 --> 00:31:01,581 Szóval, most nézd meg mindössze hét elemeket, majd hat elem, 924 00:31:01,581 --> 00:31:03,290 Ezután öt elem, majd négy elem. 925 00:31:03,290 --> 00:31:06,900 És így matematikailag, ha n Az elemek száma vagy számok 926 00:31:06,900 --> 00:31:11,990 hogy mi kezdődött, el lehet képzelni, hogy ez ugyanaz, mint az n mínusz 1, 927 00:31:11,990 --> 00:31:14,250 plusz n mínusz 2 lépésben, + n mínusz 3 lépéseket, 928 00:31:14,250 --> 00:31:16,780 plusz n mínusz 4 lépésben, az összes lement csak egy lépés. 929 00:31:16,780 --> 00:31:18,160 És én vagyok az utolsó ember. 930 00:31:18,160 --> 00:31:20,650 >> És ha emlékeztetnek arra, hogy a sok A statisztika könyv vagy matematikai könyvek 931 00:31:20,650 --> 00:31:24,730 hogy ezeket a képleteket a keménykötésben vissza, vagy előttük, 932 00:31:24,730 --> 00:31:27,690 kiderül, hogy ez a sorozat fejezhető több egyszerűen 933 00:31:27,690 --> 00:31:28,857 mint n-szer n mínusz 1 több mint 2. 934 00:31:28,857 --> 00:31:31,273 És ez rendben van, ha ez nem élen jár a fejedben. 935 00:31:31,273 --> 00:31:32,420 De ez valóban igaz. 936 00:31:32,420 --> 00:31:34,449 Ez csak egy egyszerűbb módja írás is. 937 00:31:34,449 --> 00:31:36,240 És aztán, ha úgy gondolja, vissza az általános iskolában 938 00:31:36,240 --> 00:31:38,698 ha csak elkezd szorozni dolgokat, ez természetesen 939 00:31:38,698 --> 00:31:41,820 csak n faragva mínusz n osztva 2. 940 00:31:41,820 --> 00:31:44,772 Minden, amit tettem az bővíteni A kifejezések vannak. 941 00:31:44,772 --> 00:31:46,730 És így írjuk át ezt a egy kicsit másképp. 942 00:31:46,730 --> 00:31:49,780 Ez az n négyzethálós osztva 2 mínusz n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Szóval megint én vagyok csak ilyen alkalmazása Néhány számtani szabályokat is. 944 00:31:53,270 --> 00:31:57,140 De észre most, hogy a legnagyobb távon ebben a kifejezésben, hogy úgy mondjam, 945 00:31:57,140 --> 00:31:58,540 az, hogy n négyzeten. 946 00:31:58,540 --> 00:32:02,910 Szóval igen, ez n négyzetes osztva 2, mínusz n / 2. 947 00:32:02,910 --> 00:32:05,080 >> De általában, ha n lesz egy nagy érték, 948 00:32:05,080 --> 00:32:08,740 Megyek állítják, hogy n négyzeten lesz a meghatározó tényező. 949 00:32:08,740 --> 00:32:10,490 Ez csak lesz nagyobb mértékben járul 950 00:32:10,490 --> 00:32:12,877 a lépések számát, mint n / 2. 951 00:32:12,877 --> 00:32:13,960 Szóval mit értünk ez alatt? 952 00:32:13,960 --> 00:32:16,795 Próbáljunk egy egyszerű példát, sőt bár a matek kap egy kicsit nagy. 953 00:32:16,795 --> 00:32:20,210 >> Tehát tegyük fel, hogy 1 millió ember a színpadon, vagy 1 millió dolgot 954 00:32:20,210 --> 00:32:21,320 hogy szeretnénk rendezni. 955 00:32:21,320 --> 00:32:23,730 Nézzük dugja egy millió be pontosan azt a képletet 956 00:32:23,730 --> 00:32:27,230 hogy hány lépést tart összesen rendezni egy millió elemek felhasználásával mondjuk, 957 00:32:27,230 --> 00:32:28,560 kiválasztási sorrend. 958 00:32:28,560 --> 00:32:30,760 >> Szóval mi lenne azonos képlet, mint korábban. 959 00:32:30,760 --> 00:32:34,120 Én dugja egy millió, így kapok egy millió négyzethálós osztva 2, 960 00:32:34,120 --> 00:32:35,990 mínusz egymillió osztva 2. 961 00:32:35,990 --> 00:32:40,180 Ha tudom, hogy a matematika előre Itt van 500 milliárd 962 00:32:40,180 --> 00:32:47,460 mínusz 500.000, amelyek ad nekünk 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 ami elég rohadt nagy. 964 00:32:49,270 --> 00:32:54,370 >> Sőt, ha összehasonlítjuk a vállalattal 499 milliárd forint, 999.000.000, 965 00:32:54,370 --> 00:33:01,210 500.000 ellen eredeti érték, 500 milliárd, ez annyira rohadt közel. 966 00:33:01,210 --> 00:33:06,850 Jobb? n négyzethálós osztva 2 ad us-- vagy inkább n négyzethálós osztva 2 967 00:33:06,850 --> 00:33:08,370 adott nekünk 500 milliárd. 968 00:33:08,370 --> 00:33:13,510 Ez elég rohadt közel a 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 ami azt levonjuk ki 500.000, vagy általánosabban, kivonva le 970 00:33:17,970 --> 00:33:20,010 n faragva, nem igazán nagy dolog. 971 00:33:20,010 --> 00:33:22,490 Az n faragva teszi ezeket szám nőni nagyon gyorsan. 972 00:33:22,490 --> 00:33:25,790 >> Nos, ez a fontos csak annyiban mint mi, számítógépes szakemberek, 973 00:33:25,790 --> 00:33:29,350 általában nem fog érdekel annyira a árnyalatok ezeket a képleteket 974 00:33:29,350 --> 00:33:31,400 és pontosan mi a pontos válaszok. 975 00:33:31,400 --> 00:33:33,390 Mi érdekel csak, hogy tudod, mit? 976 00:33:33,390 --> 00:33:37,810 Végén a nap, ez a képlet ez a sorrend n négyzeten. 977 00:33:37,810 --> 00:33:39,350 >> Igen, mi elosztjuk 2 odabent. 978 00:33:39,350 --> 00:33:41,360 Igen, mi levonjuk le n mínusz 2. 979 00:33:41,360 --> 00:33:46,860 De a végén a nap, a kifejezés ami igazán bánt minket, és kerül nekünk 980 00:33:46,860 --> 00:33:48,995 sok lépésből áll, hogy a négyzet távon. 981 00:33:48,995 --> 00:33:51,370 És akkor mi van egy számítógép tudós fog általában nem 982 00:33:51,370 --> 00:33:54,160 A figyelmen kívül hagyja az összes ilyen kisebb rendű tagokat, 983 00:33:54,160 --> 00:33:56,900 és csak nézd meg az egyik, hogy a leginkább hozzájárul a költségek. 984 00:33:56,900 --> 00:34:00,530 >> És ez a szép és jó, mert nem tudjuk Most beszéljünk sokkal nagyobb általánosság 985 00:34:00,530 --> 00:34:02,470 mintegy algoritmusok, és össze lehet hasonlítani őket. 986 00:34:02,470 --> 00:34:04,550 És az a tény, hogy én vagyok Ezzel a O szándékos. 987 00:34:04,550 --> 00:34:06,680 Amikor azt mondom, a rend Az vagyok, konkrétan 988 00:34:06,680 --> 00:34:09,560 dologra utal úgynevezett nagy O. és a nagy O 989 00:34:09,560 --> 00:34:14,090 egy jelölést, hogy a számítógép tudós használ, hogy leírja 990 00:34:14,090 --> 00:34:16,710 egy felső korlátot valamit. 991 00:34:16,710 --> 00:34:21,150 >> Tehát ha azt mondod, hogy egy algoritmus a nagy O n faragva, 992 00:34:21,150 --> 00:34:23,380 ahogy javasolt csak egy perce, hogy úton 993 00:34:23,380 --> 00:34:27,710 hogy tekintve a működési idő vagy annak hatékonyságát, 994 00:34:27,710 --> 00:34:30,090 ez megváltó érdekében n faragva lépéseket. 995 00:34:30,090 --> 00:34:31,420 Talán több, talán kevesebb. 996 00:34:31,420 --> 00:34:33,435 De ez a sorrend n négyzeten. 997 00:34:33,435 --> 00:34:34,560 És ez a felső határ. 998 00:34:34,560 --> 00:34:36,530 Ez nem lesz fájdalmasabb, mint ezt. 999 00:34:36,530 --> 00:34:40,800 Ez nem lesz n kockára vágott, vagy 2 A n, vagy valami sokkal nagyobb. 1000 00:34:40,800 --> 00:34:43,800 Ez egy felső korlát akármilyen hogy a költségek. 1001 00:34:43,800 --> 00:34:46,150 Tehát tekintettel arra, hogy lássuk úgy ez csak néhány példa. 1002 00:34:46,150 --> 00:34:49,820 És ez csak egy véges lista A nagyon gyakori futásidoket 1003 00:34:49,820 --> 00:34:52,870 algoritmusok, ami azt jelentette, hogy bemutatnak néhány dolgot, amit 1004 00:34:52,870 --> 00:34:53,600 láttam már. 1005 00:34:53,600 --> 00:34:58,060 >> Így például, abban az esetben, kiválasztási sorrend, amit én itt azt állítva, 1006 00:34:58,060 --> 00:35:02,250 az, hogy a kiválasztási sorrend fut idő nagyságrendileg n négyzeten. 1007 00:35:02,250 --> 00:35:06,260 A legrosszabb esetben, én megyek is egy csomó véletlen számokat itt. 1008 00:35:06,260 --> 00:35:08,600 És ahogy láttuk matematikailag, ha folyamatosan séta 1009 00:35:08,600 --> 00:35:11,310 Ha a listában, a listát, kiválasztja a következő legkisebb 1010 00:35:11,310 --> 00:35:14,410 elemet újra és újra, ha én ténylegesen sorold fel azokat a lépéseket, 1011 00:35:14,410 --> 00:35:18,750 Elviszem én javasolt formulaically előtt, ez a sorrend n négyzetes 1012 00:35:18,750 --> 00:35:20,370 lépéseket, hogy én viszem. 1013 00:35:20,370 --> 00:35:24,520 >> És kiderül, hogy a buborék rendezés és beillesztés sort 1014 00:35:24,520 --> 00:35:27,370 ugyanolyan lassú a legrosszabb esetben. 1015 00:35:27,370 --> 00:35:32,040 Vegyük például, beillesztés sort, A legutolsó algoritmus foglalkoztunk, 1016 00:35:32,040 --> 00:35:35,500 ami volt számunkra nézd meg a elemet, majd helyezze, ahová tartozik. 1017 00:35:35,500 --> 00:35:38,720 Aztán megnéztük a következő elem, és bedugta, ahova tartozik. 1018 00:35:38,720 --> 00:35:40,990 >> Tehát úgy a lehető legjobb forgatókönyv. 1019 00:35:40,990 --> 00:35:45,590 Tegyük fel, hogy már én önkéntesek sorakoznak Szó szerint, mint ez, egytől nyolc, 1020 00:35:45,590 --> 00:35:47,440 Már rendezve. 1021 00:35:47,440 --> 00:35:51,300 Hány lépés az illesztési sorrend fog tartani rendezni nyolc embert, 1022 00:35:51,300 --> 00:35:55,640 ha megérkeznek a színpadon így néz ki? 1023 00:35:55,640 --> 00:35:57,410 >> Nyolc ember már válogatni. 1024 00:35:57,410 --> 00:35:58,760 És tudom használni behelyezés sort. 1025 00:35:58,760 --> 00:36:02,180 Ez az utolsó algoritmusok. 1026 00:36:02,180 --> 00:36:03,640 Nos, nézzük reenact igazi böjt. 1027 00:36:03,640 --> 00:36:05,504 Tehát, ha én itt kezdődnek, látok egyet. 1028 00:36:05,504 --> 00:36:06,420 Hol az egyik tagja? 1029 00:36:06,420 --> 00:36:07,730 Tartozik itt. 1030 00:36:07,730 --> 00:36:08,330 Látom kettő. 1031 00:36:08,330 --> 00:36:09,660 Hol kettő tartozik? 1032 00:36:09,660 --> 00:36:10,260 Pont itt. 1033 00:36:10,260 --> 00:36:10,900 Látom három. 1034 00:36:10,900 --> 00:36:11,920 Hol három tartozik? 1035 00:36:11,920 --> 00:36:12,480 Pont itt. 1036 00:36:12,480 --> 00:36:13,100 >> Látom négy. 1037 00:36:13,100 --> 00:36:13,600 Pont itt. 1038 00:36:13,600 --> 00:36:15,660 Öt, hat, hét, nyolc. 1039 00:36:15,660 --> 00:36:17,320 Nincs oka ismételni magam. 1040 00:36:17,320 --> 00:36:21,260 És igen, hány lépést az, hogy szempontjából n? 1041 00:36:21,260 --> 00:36:23,870 Ez a sorrend n lépések, ugye? n mínusz 1. 1042 00:36:23,870 --> 00:36:27,567 De vettem egy lineáris száma A lépés, és most kész vagyok. 1043 00:36:27,567 --> 00:36:28,900 Szóval ez a legjobb esetben mégis. 1044 00:36:28,900 --> 00:36:29,983 Mi a helyzet a legrosszabb esetben? 1045 00:36:29,983 --> 00:36:32,730 Milyen nyolc volt ott, hét pedig ott, 1046 00:36:32,730 --> 00:36:35,840 és egy, kettő pedig több mint itt, így hogy a listán volt igazán fordított? 1047 00:36:35,840 --> 00:36:38,300 >> Nos, mi történik valójában Ha ez a szám? 1048 00:36:38,300 --> 00:36:41,300 És mi nem csak egy pár példa. 1049 00:36:41,300 --> 00:36:49,300 Mi lenne, ha valóban a nyolcas szám itt van, és a number-- Hoppá. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Szóval mi van, ha valóban száma A nyolcas egészen át ide, 1052 00:36:56,430 --> 00:36:57,790 és én vagyok a behelyezés sort? 1053 00:36:57,790 --> 00:36:58,290 >> OKÉ. 1054 00:36:58,290 --> 00:37:00,280 Azt állítják, abban a pillanatban, hogy ez a hely. 1055 00:37:00,280 --> 00:37:03,152 De most, seven-- hol hét menni? 1056 00:37:03,152 --> 00:37:04,360 Persze, ez megy itt. 1057 00:37:04,360 --> 00:37:06,760 Szóval meg kell mozgatni nyolc alatt egy helyen. 1058 00:37:06,760 --> 00:37:08,554 Most hat, ahol nem is megy? 1059 00:37:08,554 --> 00:37:09,220 Nos, rendben. 1060 00:37:09,220 --> 00:37:13,150 Most azt kell mozgatni nyolc fölött egy hely, és a hét egy helyen, 1061 00:37:13,150 --> 00:37:14,440 és aztán lehuppansz hat. 1062 00:37:14,440 --> 00:37:16,870 >> Tehát az első alkalom, hogy költség nekem egy lépéssel rögzíteni a dolgokat, 1063 00:37:16,870 --> 00:37:18,570 akkor ez nekem két lépésben rögzíteni a dolgokat. 1064 00:37:18,570 --> 00:37:20,370 Hány lépés van fog tartani rögzíteni 1065 00:37:20,370 --> 00:37:22,720 dolgokat, hogy öt jó helyen? 1066 00:37:22,720 --> 00:37:23,340 Három. 1067 00:37:23,340 --> 00:37:29,520 Mert most már, hogy mozgatni egy, kettő, három. 1068 00:37:29,520 --> 00:37:32,430 Hány lépés ez fog venni hogy négy jó helyen? 1069 00:37:32,430 --> 00:37:36,040 4 és 5, és 6, plusz 7. 1070 00:37:36,040 --> 00:37:40,260 >> És így matematikailag megegyezik amit leírt kiválasztási sorrend. 1071 00:37:40,260 --> 00:37:42,130 Van ez a sorozat ez csak növekszik. 1072 00:37:42,130 --> 00:37:45,650 1 plusz 2 + 3 + 4, vagy fordítva, 7 plusz 6 1073 00:37:45,650 --> 00:37:52,610 plusz 5 plusz 4 összeadja a mai célú nagyságrendű n négyzeten. 1074 00:37:52,610 --> 00:37:57,640 >> Szóval hadd kikötik azt is, hogy buborékos rendezést is n négyzeten. 1075 00:37:57,640 --> 00:38:01,340 Mivel a buborék rendezés, minden alkalommal megyek át a listát, 1076 00:38:01,340 --> 00:38:03,100 Elviszem nagyjából hány lépést? 1077 00:38:03,100 --> 00:38:06,260 Minden alkalommal, amikor szó szerint séta onnan van? 1078 00:38:06,260 --> 00:38:07,960 Nagyjából n lépéseket. 1079 00:38:07,960 --> 00:38:12,650 De hányszor lehet, hogy én kell, hogy menjen végig a listán? 1080 00:38:12,650 --> 00:38:13,920 >> Nos, nagyjából n időt. 1081 00:38:13,920 --> 00:38:15,680 Talán n mínusz 1, de nagyjából n-szer. 1082 00:38:15,680 --> 00:38:16,430 Nos, miért van ez? 1083 00:38:16,430 --> 00:38:19,560 Nos, a buborékos rendezést, ha kezdjük buborékos rendezést, 1084 00:38:19,560 --> 00:38:23,570 A lista a lehető legrosszabb helyzetet, ami szintén teljesen 1085 00:38:23,570 --> 00:38:25,550 hátra, mi fog történni? 1086 00:38:25,550 --> 00:38:28,830 Én végig a listát, és a szám Egy tartozik egészen ott. 1087 00:38:28,830 --> 00:38:33,280 >> De buborékos rendezést, milyen messze egy lépni az első áthaladnak a listán? 1088 00:38:33,280 --> 00:38:36,620 Hány foltok nem ő kap közelebb a megfelelő helyre? 1089 00:38:36,620 --> 00:38:37,240 Csak egy. 1090 00:38:37,240 --> 00:38:40,281 Tehát, ha ilyen okból ezen keresztül, minden alkalommal át ezt az algoritmust, 1091 00:38:40,281 --> 00:38:41,880 Dávid véve nagyjából n lépéseket. 1092 00:38:41,880 --> 00:38:44,940 De hány menetben Ha a listában van 1093 00:38:44,940 --> 00:38:49,060 fog tartani egy buborék balra, ahova tartozik? 1094 00:38:49,060 --> 00:38:51,840 >> Neki mozogni, mint, N terek ezen a módon. 1095 00:38:51,840 --> 00:38:57,960 Szóval, csak hogy ne a válogatás a listán, Én már járni oda-vissza n-szer. 1096 00:38:57,960 --> 00:39:01,540 És minden alkalommal, én vagyok néztem n eleme. 1097 00:39:01,540 --> 00:39:05,410 Tehát nem n dolgokat n-szer nagyságrendű n négyzeten. 1098 00:39:05,410 --> 00:39:07,220 >> Most majd meglátjuk néhány a nadrág, hogy 1099 00:39:07,220 --> 00:39:10,440 ágyazódnak CS50 következő probléma állítva, egy másik megközelítés ezeket, 1100 00:39:10,440 --> 00:39:13,490 de most, nézzük csak úgy néhány más futási idők, 1101 00:39:13,490 --> 00:39:16,840 különösen, ha a válogatás is megteszi egy kis időt, hogy elsüllyed. 1102 00:39:16,840 --> 00:39:21,790 Mi az az algoritmus, láttunk már hogy felveszi a rendelést n lépések? 1103 00:39:21,790 --> 00:39:27,560 >> Mi kell egy lineáris száma A lépések, amiket láttam eddig? 1104 00:39:27,560 --> 00:39:29,350 Az mi? 1105 00:39:29,350 --> 00:39:30,480 A telefonkönyv kereső. 1106 00:39:30,480 --> 00:39:31,390 Az első algoritmust. 1107 00:39:31,390 --> 00:39:31,560 Jobb? 1108 00:39:31,560 --> 00:39:33,650 Hol vagyunk lineárisan keres Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Valóban. 1110 00:39:34,150 --> 00:39:37,180 Hétről nulla, amikor elkezdtem fordult egy oldalt egy időben, 1111 00:39:37,180 --> 00:39:40,095 és még azt is mondta, hogy ez a fajta lineáris érzés algoritmus, 1112 00:39:40,095 --> 00:39:42,720 és mi volt, hogy a képet a fórumon, hogy az egyenes piros vonal 1113 00:39:42,720 --> 00:39:44,678 és az egyenes sárga vonal, azok valóban 1114 00:39:44,678 --> 00:39:46,810 algoritmusok, amelyek a nagy O n. 1115 00:39:46,810 --> 00:39:50,680 >> Mert, hogy megtalálja Mike Smith egy telefont könyvében n oldalak, a legrosszabb esetben, 1116 00:39:50,680 --> 00:39:52,422 Lehet, hogy engem n lépéseket. 1117 00:39:52,422 --> 00:39:53,630 Mi a helyzet figyelembe látogatottsága? 1118 00:39:53,630 --> 00:39:55,790 Egy kettő három négy öt hat. 1119 00:39:55,790 --> 00:39:59,420 Mi a menetideje ezt algoritmus figyelembe látogatottsága? 1120 00:39:59,420 --> 00:40:03,070 Big O n, mert az elméletet én van, hogy pont a teremben mindenki. 1121 00:40:03,070 --> 00:40:05,861 >> Most Mellesleg, mi a helyzet a más optimalizálási hétről nulla? 1122 00:40:05,861 --> 00:40:08,117 Kettő, négy, hat, nyolc, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 A számítógép-tudós lenne megvalósítani, várj egy percet, 1124 00:40:10,200 --> 00:40:12,320 ez a sorrend N osztva két lépésben. 1125 00:40:12,320 --> 00:40:12,820 Jobb? 1126 00:40:12,820 --> 00:40:14,444 Mert én csinálok két ember egy időben. 1127 00:40:14,444 --> 00:40:17,015 De mi lesz figyelmen kívül hagyni Ezeket az alsó rendű tagokat, 1128 00:40:17,015 --> 00:40:19,140 és mi csak fog dobja el a osszuk el 2, 1129 00:40:19,140 --> 00:40:21,830 és csak azt mondom, nagy O n számára, hogy az algoritmus is. 1130 00:40:21,830 --> 00:40:22,760 >> Mit szólsz ehhez? 1131 00:40:22,760 --> 00:40:26,170 Majd átugrik néhány ilyen, de mi volt egy algoritmus, hogy volt log n? 1132 00:40:26,170 --> 00:40:29,900 Hogy elvitt körülbelül log n? 1133 00:40:29,900 --> 00:40:30,870 Az oszd meg és uralkodj. 1134 00:40:30,870 --> 00:40:31,369 Pontosan. 1135 00:40:31,369 --> 00:40:33,900 Mint a telefonkönyvben például heti nulla és a korábbi ma, 1136 00:40:33,900 --> 00:40:36,191 ahol osztva a problémát újra és újra és újra. 1137 00:40:36,191 --> 00:40:39,070 Felhívtuk a táblára a héten nulla ívelt zöld vonal, 1138 00:40:39,070 --> 00:40:41,460 és azt mondtuk, hogy a nap volt logaritmikus algoritmus. 1139 00:40:41,460 --> 00:40:44,970 >> És valóban, a lépések számát is úgy, hogy végre oszd meg és uralkodj, 1140 00:40:44,970 --> 00:40:48,610 vagy bináris keresés, mint fogjuk kezdeni amelyben ez, mint a telefonkönyvben, 1141 00:40:48,610 --> 00:40:50,680 ez a sorrend napló és lépéseket. 1142 00:40:50,680 --> 00:40:52,470 És ez egy kicsit furcsa. 1143 00:40:52,470 --> 00:40:54,910 >> Mit vesz egy lépéssel, vagy pontosabban 1144 00:40:54,910 --> 00:40:56,240 konstans számú lépést? 1145 00:40:56,240 --> 00:40:58,865 Lehet, hogy ez a két, talán három, de egy számítógép tudós csak 1146 00:40:58,865 --> 00:41:01,423 leegyszerűsíti azt a nagy O 1, Néhány állandó lépések számát. 1147 00:41:01,423 --> 00:41:04,256 Mi az, amit tehet, hogy úgy konstans számú lépést? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Mi a menetideje taps? 1150 00:41:10,930 --> 00:41:11,920 Állandó időt. 1151 00:41:11,920 --> 00:41:12,420 Jobb? 1152 00:41:12,420 --> 00:41:15,490 Mint, mi a menetideje csinál semmit, hogy már csak egy 1153 00:41:15,490 --> 00:41:18,570 működését, mint a print F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Hogy lehet mondani, hogy az állandó idő, kivéve, ha kevesebb sarkában esetében nyomtatási N, 1155 00:41:24,110 --> 00:41:28,260 Mi lehet a futási idő A nyomtatási F valóban? 1156 00:41:28,260 --> 00:41:28,790 És miért? 1157 00:41:28,790 --> 00:41:30,550 Mi n mérési ebben az esetben? 1158 00:41:30,550 --> 00:41:32,251 >> Közönség: [hallható]. 1159 00:41:32,251 --> 00:41:33,250 David J. MALAN: Pontosan. 1160 00:41:33,250 --> 00:41:34,900 A karakterek száma szeretnénk nyomtatni. 1161 00:41:34,900 --> 00:41:36,191 Így nagyon környezetfüggő. 1162 00:41:36,191 --> 00:41:39,910 Ma már összpontosítva sokat Betűk és számok itt a fórumon. 1163 00:41:39,910 --> 00:41:43,540 De ez is lehet karakterek tényleges húr. 1164 00:41:43,540 --> 00:41:46,420 Így kiderül, van egy másik intézkedés, amely indul törődve, 1165 00:41:46,420 --> 00:41:48,530 és ez az ellenkezője A nagy O, hogy úgy mondjam. 1166 00:41:48,530 --> 00:41:50,120 >> Ez omega jelölés. 1167 00:41:50,120 --> 00:41:53,380 Mivel nagy O azt jelenti, mi, a felső korlátot a futási időt? 1168 00:41:53,380 --> 00:41:55,580 Maximálisan, hogy mennyi időt Lehet valamit tenni? 1169 00:41:55,580 --> 00:41:59,250 Omega-- sajnálom ezt tartja jön up-- az ellentéte, hogy 1170 00:41:59,250 --> 00:42:02,960 ahol ez egy alsó korlátot a időt valamit eltarthat. 1171 00:42:02,960 --> 00:42:10,480 >> Na. Például, mi az algoritmus vevő mindig n faragva lépéseket? 1172 00:42:10,480 --> 00:42:15,600 Nos, az egyik algoritmusok láttunk ma, sőt, lehet, hogy is. 1173 00:42:15,600 --> 00:42:16,720 Válogatás a fajta. 1174 00:42:16,720 --> 00:42:18,270 Válogatás a fajta elég hülye. 1175 00:42:18,270 --> 00:42:21,760 Még ha a algorithm-- sajnálom, még ha a tömb már rendezve, 1176 00:42:21,760 --> 00:42:24,150 kiválasztási sorrend fog tartsa séta a listát 1177 00:42:24,150 --> 00:42:28,907 hogy megbizonyosodjon arról, hogy a legkisebb elemet újra és újra és újra. 1178 00:42:28,907 --> 00:42:31,740 És bár az emberek a közönség tudja, hogy várj egy percet, 1179 00:42:31,740 --> 00:42:33,948 Ön már túljutott az legkisebb elem, a számítógép 1180 00:42:33,948 --> 00:42:37,300 Nem tudja, hogy amíg úgy néz ki végig a listán. 1181 00:42:37,300 --> 00:42:40,240 Hasonlóképpen, az alsó határát, hogy Esetleg ezek is figyelembe kell venni 1182 00:42:40,240 --> 00:42:42,000 Lehet, hogy a lineáris idő. 1183 00:42:42,000 --> 00:42:48,260 >> Mennyi időt vesz igénybe a Rendezés n elem a legjobb 1184 00:42:48,260 --> 00:42:52,420 esetében segítségével olyasmi, mint buborékos rendezést? 1185 00:42:52,420 --> 00:42:54,280 Tegyük fel, hogy a listán már válogatni. 1186 00:42:54,280 --> 00:42:56,696 Azt mondtuk, buborékos rendezést veszi nagyságrendű n faragva lépéseket. 1187 00:42:56,696 --> 00:42:59,640 De mi van, ha ez már válogatni? 1188 00:42:59,640 --> 00:43:02,310 Mi van, ha rájössz után egy áthaladás az array 1189 00:43:02,310 --> 00:43:03,540 hogy már nem tett csereügyletek? 1190 00:43:03,540 --> 00:43:05,970 Szüksége van-e tartani, hogy több menetet? 1191 00:43:05,970 --> 00:43:06,470 >> Nem. 1192 00:43:06,470 --> 00:43:10,340 Tehát egy alsó korlátot buborékos rendezést Lehet, hogy azt mondják, hogy a lineáris. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 És nézd meg mások ezeket is. 1195 00:43:14,450 --> 00:43:17,990 Szóval vessünk egy gyors pillantást mindössze egy vizualizációs itt 1196 00:43:17,990 --> 00:43:20,790 belátni, hogy ezek megkülönböztetni magukat. 1197 00:43:20,790 --> 00:43:24,592 Én megyek le ide ebbe Oldal hogy a rendelkezésre álló C50 honlapján, 1198 00:43:24,592 --> 00:43:27,550 de ez lesz a fájdalom, amelyek a dolgozó, mivel az általa használt technológia az úgynevezett 1199 00:43:27,550 --> 00:43:30,560 Java applet, amely egy nagyrészt támogatott ezekben a napokban, 1200 00:43:30,560 --> 00:43:32,730 legalább Chrome és bizonyos mások. 1201 00:43:32,730 --> 00:43:37,070 >> És hadd menjen előre, és meggyorsíthatja ezt fel, és elmagyarázza, mi folyik itt. 1202 00:43:37,070 --> 00:43:40,840 Ez egy demo buborék sort, az első algoritmus néztük. 1203 00:43:40,840 --> 00:43:43,950 És ez egy vizualizációs, hogy az egyes Ezen rudak számot jelent. 1204 00:43:43,950 --> 00:43:45,710 Minél nagyobb a bárban, Minél nagyobb a szám. 1205 00:43:45,710 --> 00:43:47,520 Minél kisebb a bárban, Minél kisebb a szám. 1206 00:43:47,520 --> 00:43:50,353 És mit lehet látni vizuálisan is bár ez lesz szuper gyors, 1207 00:43:50,353 --> 00:43:53,699 az, hogy a piros sáv, mint én, séta oda-vissza a problémák. 1208 00:43:53,699 --> 00:43:56,740 Láthatjuk, hogy a nagyobb elemek valóban bugyogott fel a jobb, 1209 00:43:56,740 --> 00:43:59,650 és a kisebb elemek vannak bugyogott fel, hogy a bal oldalon. 1210 00:43:59,650 --> 00:44:01,870 És itt lent, ha ténylegesen meg közelebbről, 1211 00:44:01,870 --> 00:44:04,330 mi is valójában számít a összehasonlítások száma és csereügyletek 1212 00:44:04,330 --> 00:44:05,350 amelyeket nem történt. 1213 00:44:05,350 --> 00:44:07,360 >> De ahelyett, nézzük meg a második algoritmus 1214 00:44:07,360 --> 00:44:11,240 néztük korábban a mi önkéntesek, a kiválasztás sort. 1215 00:44:11,240 --> 00:44:13,500 Vizuálisan van egy nagyon különböző hatást. 1216 00:44:13,500 --> 00:44:16,820 De ez megint nagyon intuitív, a hogy megtartjuk adja meg a következő legkisebb 1217 00:44:16,820 --> 00:44:18,660 elemet, és kaptunk egy kis szerencséje. 1218 00:44:18,660 --> 00:44:20,110 Hogy érezte alapvetően gyorsabb. 1219 00:44:20,110 --> 00:44:22,840 De ha már futott ez újra és újra és ismét sok bemenet, 1220 00:44:22,840 --> 00:44:26,680 látnánk, hogy ez valóban Még mindig nagy O n négyzeten. 1221 00:44:26,680 --> 00:44:29,920 >> Csináljuk egy utolsót Itt, beillesztés sort, 1222 00:44:29,920 --> 00:44:33,180 amely volt a harmadik algoritmus néztük, és visszahívás 1223 00:44:33,180 --> 00:44:36,700 hogy ez az egy foglalkozik a elemeket nem találkozik velük, 1224 00:44:36,700 --> 00:44:39,290 de akkor talán műszakban dolgokat, hogy legyen hely, 1225 00:44:39,290 --> 00:44:41,660 behelyezése elemek, ahová tartoznak. 1226 00:44:41,660 --> 00:44:45,330 >> És ez is véget ér fel, amely a végeredmény. Most itt felsorolt ​​három 1227 00:44:45,330 --> 00:44:46,490 éreztem elég gyors. 1228 00:44:46,490 --> 00:44:48,740 És valóban, futottam velük egy nagyon jó klip. 1229 00:44:48,740 --> 00:44:52,510 De alapvetően, ők mind elég szörnyű, hogy őszinte legyek. 1230 00:44:52,510 --> 00:44:56,960 Mindezek a algoritmusok eddig futó nagy O n faragva 1231 00:44:56,960 --> 00:44:59,270 hogy egy kicsit a időt futni a végén. 1232 00:44:59,270 --> 00:45:01,920 >> És valóban, azt látjuk, és úgy érzi, ez végül 1233 00:45:01,920 --> 00:45:04,090 ha kihúzom ezt a harmadik és egyben utolsó demo. 1234 00:45:04,090 --> 00:45:05,840 Ez egy másik vizualizáció, hogy folyik 1235 00:45:05,840 --> 00:45:08,500 megmutatni buborékos rendezést a bal oldalon, kiválasztási sorrend közepén, 1236 00:45:08,500 --> 00:45:13,410 és valami, mint az egyik kéz emel korábban javasolták, 1237 00:45:13,410 --> 00:45:15,020 merge sort a jobb oldalon. 1238 00:45:15,020 --> 00:45:16,937 A Oszd meg és uralkodj stratégia a helyes. 1239 00:45:16,937 --> 00:45:19,520 És ez, sőt, mi vagyunk Ismerkedjünk meg szerdán. 1240 00:45:19,520 --> 00:45:21,990 De nézzük az időben ezek fut párhuzamosan. 1241 00:45:21,990 --> 00:45:26,765 Ez nagyjából azonos számú elemek, minden futó ugyanabban az időben. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs kiválasztása Rendezés vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Most, ők minden futó elméletileg ugyanabban az időben. 1245 00:45:36,760 --> 00:45:39,830 A CPU fut azonos sebességgel, de 1246 00:45:39,830 --> 00:45:44,014 úgy érezhetik, hogy unalmas ez nagyon gyorsan fog válni, 1247 00:45:44,014 --> 00:45:45,930 és milyen gyorsan, amikor mi adja egy kicsit a héten 1248 00:45:45,930 --> 00:45:49,330 Zero algoritmusok mi gyorsítsák fel a dolgokat. 1249 00:45:49,330 --> 00:45:51,760 >> És most nézzük összehasonlítani Ezek egy utolsó formában. 1250 00:45:51,760 --> 00:45:55,710 Megyek, hogy menjen előre a CS50 honlapján, ahol 1251 00:45:55,710 --> 00:45:59,020 itt van ez a végső kapcsolatot a mai napra, ahol valaki az interneten 1252 00:45:59,020 --> 00:46:03,960 Kérjük össze egy videót, hogy rögzíti, amit a különböző rendezési 1253 00:46:03,960 --> 00:46:07,510 algoritmusok hangzik. 1254 00:46:07,510 --> 00:46:09,577 Ez behelyezés sort. 1255 00:46:09,577 --> 00:46:12,072 >> [Csipogó] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Amellyel te alkalmazásával infó alapján a magassága a bar bar. 1258 00:46:16,850 --> 00:46:19,826 Ez buborékos rendezést. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped csipogó] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Következik is-- jön mellé is-- kiválasztási sorrend, 1262 00:46:45,774 --> 00:46:48,820 ahol újra, mi kiválasztása A következő legkisebb eleme, 1263 00:46:48,820 --> 00:46:51,820 és látjuk, hogy egyre balról jobbra. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, mi nyertese eddig ma. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Figyeljük meg, hogy ez elosztjuk a dolgokat a [hallhatatlan] felében és negyedek. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome sort, amit már nem beszélt, és létrehoz vizuálisan 1270 00:47:21,660 --> 00:47:24,450 és audally egy kicsit különböző alakú és a hang. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Megy oda-vissza, takarítás a dolgokat. 1273 00:47:30,160 --> 00:47:32,230 Szintén nézd meg kupacrendezés ez a fickó honlapján. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> És ez az. 1276 00:47:36,810 --> 00:47:38,210 Látni fogjuk legközelebb. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing ÉS ZENE] 1279 00:47:48,334 --> 00:50:24,839