1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Muzikos grojimo] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. Malan: Tai CS50. 5 00:00:12,550 --> 00:00:14,612 Ir tai yra savaitės trys pradžia. 6 00:00:14,612 --> 00:00:16,820 Taigi mes turime daug įdomių dalykų, kuriuos reikia padengti šiandien. 7 00:00:16,820 --> 00:00:20,160 Daug galimybių už savanoriai ant scenos. 8 00:00:20,160 --> 00:00:22,780 Ir galiausiai, šiandien yra ne apie kodo ne visiems. 9 00:00:22,780 --> 00:00:24,820 Bet tai apie idėjas ir tai apie algoritmus, 10 00:00:24,820 --> 00:00:28,420 ir iš tikrųjų sugrįžus kai ko pasimokyta iš nulio savaitę 11 00:00:28,420 --> 00:00:31,910 kuriame Prisiminkite, mes pristatė šį Straszliwość. 12 00:00:31,910 --> 00:00:33,880 Ir skolinimasis įkvėpimas to, pradėti 13 00:00:33,880 --> 00:00:36,879 išspręsti vis sudėtingesnės problemos algoritmiškai. 14 00:00:36,879 --> 00:00:38,420 Bet pirmiausia, iš skelbimų pora. 15 00:00:38,420 --> 00:00:42,020 Taigi vienas, jei norėtumėte prisijungti CS50 personalas ir klasiokų pietų 16 00:00:42,020 --> 00:00:44,670 šį penktadienį, tiek čia ir Kembridžo ir New Haven, 17 00:00:44,670 --> 00:00:48,060 apsilankykite aikštyno svetainė, kurioje URL gali būti rasta. 18 00:00:48,060 --> 00:00:50,390 Paskaita šį trečiadienį bus ne čia Sanders. 19 00:00:50,390 --> 00:00:53,610 Tai bus tik internete, todėl melodija ne CS50 tinklalapyje, 20 00:00:53,610 --> 00:00:55,850 ar čia Kembridže ar Niu Heivenas, taip pat. 21 00:00:55,850 --> 00:00:58,110 >> Ir tada problema nustatyti du jau jūsų rankose. 22 00:00:58,110 --> 00:01:03,067 Jei neturite nėrė dar, leiskite man pasiūlyti stipriai suformuluotą pasiūlymą 23 00:01:03,067 --> 00:01:05,150 kad, ypač dabar, kaip problema nustato iš anksto, 24 00:01:05,150 --> 00:01:08,669 jūs tikrai norite pradėti jau dabar, jei ne taškytis ant savaitgalį arba prieš tiek 25 00:01:08,669 --> 00:01:10,710 kai jie pirmą kartą išeiti Penktadieniais, nes jūs 26 00:01:10,710 --> 00:01:14,380 kad jie nebūtinai ilgėja ar sunkiau už 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Manau, kad jūs rasite, kad Apskritai, jie linkę imtis maždaug 29 00:01:17,575 --> 00:01:18,892 aplink tą patį laiką. 30 00:01:18,892 --> 00:01:20,850 Bet tai tikrai priklauso mokinyje, ir ji 31 00:01:20,850 --> 00:01:22,880 priklauso nuo mąstymo su kuria jūs požiūrį. 32 00:01:22,880 --> 00:01:24,910 Bet visada, jūs ketinate paleisti prieš tikrą sieną, 33 00:01:24,910 --> 00:01:26,350 ir jūs ketinate Hit kai klaida, ir jūs tiesiog 34 00:01:26,350 --> 00:01:27,950 nesiruošia galėtų gauti per jį tam tikru momentu. 35 00:01:27,950 --> 00:01:31,380 Ir tai labai vertingas, kad būtų galima žingsnį, grįžti kitą dieną, 36 00:01:31,380 --> 00:01:35,286 pereiti prie darbo valandų, post CS50 Aptarkite ar panašiai, faktiškai gauti atblokuota. 37 00:01:35,286 --> 00:01:36,160 Taigi keep that in mind. 38 00:01:36,160 --> 00:01:40,830 Nuo anksčiau, kaip įmanoma yra geriausia, ką jūs galite padaryti. 39 00:01:40,830 --> 00:01:44,160 Taigi čia, kur mes pradėjome klasė, daugiau kaip nulinės savaitę. 40 00:01:44,160 --> 00:01:47,441 Ir mes galime gauti savanoris Čia padėti man rasti mikrofonus? 41 00:01:47,441 --> 00:01:47,940 GERAI. 42 00:01:47,940 --> 00:01:48,900 Atsistojus jau. 43 00:01:48,900 --> 00:01:50,080 Nagi iki. 44 00:01:50,080 --> 00:01:53,707 Manau, kad tai, kaip ji vyksta į darbą. 45 00:01:53,707 --> 00:01:54,415 Koks tavo vardas? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alanas Estrada. 47 00:01:55,570 --> 00:01:56,778 David J. Malan: Alanas Estrada. 48 00:01:56,778 --> 00:01:57,910 Nagi iki. 49 00:01:57,910 --> 00:01:58,619 Malonu susipažinti. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Nice to meet jums. 51 00:01:59,910 --> 00:02:02,772 David J. Malan: Ir tu buvai čia su mus nulinės savaitę, žinoma. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: buvau. 53 00:02:03,028 --> 00:02:03,160 Aš buvau. 54 00:02:03,160 --> 00:02:05,868 >> David J. Malan: Taigi gal jūs einate į priekį ir rasti mums Mike Smith 55 00:02:05,868 --> 00:02:08,639 taip pat greitai, kaip jūs galite? 56 00:02:08,639 --> 00:02:10,639 Kaip greitai, kaip jūs galite. 57 00:02:10,639 --> 00:02:13,756 Drąsiai ašarojimas problemą per pusę, kaip jums reikia. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Hm. 59 00:02:15,130 --> 00:02:17,380 David J. Malan: Pažodžiui ašarojimas per pusę problemą. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: O. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Labai gerai. 64 00:02:23,300 --> 00:02:23,700 >> David J. Malan: Gerai. 65 00:02:23,700 --> 00:02:24,200 Geras. 66 00:02:24,200 --> 00:02:24,701 Ačiū. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Labai gera. 68 00:02:25,700 --> 00:02:26,210 GERAI. 69 00:02:26,210 --> 00:02:27,610 >> David J. Malan: Ir taip dabar Jūs sutrumpino jį žemyn 70 00:02:27,610 --> 00:02:29,320 pusei problemos dydžio. 71 00:02:29,320 --> 00:02:31,267 Dabar mes iki ketvirčio. 72 00:02:31,267 --> 00:02:33,475 Ar jūs atkreipti dėmesį į kurioje pusėje mes išlaikyti? 73 00:02:33,475 --> 00:02:34,405 >> [Atsakyti] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Taip, aš think-- 75 00:02:35,970 --> 00:02:37,594 >> David J. Malan: Kas skyriuje mes esame? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: DUSLINTUVAI, todėl. 77 00:02:39,150 --> 00:02:39,941 >> David J. Malan: Gerai. 78 00:02:39,941 --> 00:02:42,810 Bet Mike Smith ketina būti po Garso slopintuvas. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Atsakyti] 81 00:02:48,180 --> 00:02:48,742 >> Gerai. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Kur mes ieškome? 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: Dabar mes chirurginių. 86 00:02:54,760 --> 00:02:57,840 Dabar gydytojai. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- eikime su realiais. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> David J. Malan: Nekilnojamojo. 91 00:03:00,970 --> 00:03:01,470 GERAI. 92 00:03:01,470 --> 00:03:03,700 Jei reikia realių. 93 00:03:03,700 --> 00:03:05,250 Dabar, kuris būdas yra Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Šis būdas. 95 00:03:06,250 --> 00:03:07,333 >> David J. Malan: Kokiu būdu? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Palaukite. 97 00:03:08,240 --> 00:03:08,790 M is-- tiesa? 98 00:03:08,790 --> 00:03:09,110 Mes pradėjome with-- 99 00:03:09,110 --> 00:03:10,090 >> David J. Malan: Taip. 100 00:03:10,090 --> 00:03:10,650 Jie paliko. 101 00:03:10,650 --> 00:03:11,430 Tu teisus. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Taip. 103 00:03:11,710 --> 00:03:13,126 >> David J. Malan: Taigi Mike čia. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Kas? 105 00:03:13,990 --> 00:03:14,665 >> [Atsakyti] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Blogas pavyzdys, vaikinai. 108 00:03:18,330 --> 00:03:18,830 Atsiprašau. 109 00:03:18,830 --> 00:03:21,610 David J. Malan: tai bus išmokyti jums šuolis iš savo kėdės. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: O. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Aš turiu jums. 113 00:03:23,390 --> 00:03:24,670 Aš turiu jums. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Tai is-- Gerai, aš turiu jums. 117 00:03:26,812 --> 00:03:27,520 Smith čia? 118 00:03:27,520 --> 00:03:28,894 >> David J. Malan: Smith, ačiū. 119 00:03:28,894 --> 00:03:30,535 Taigi aš nuolat ieško iki Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: O, taip. 121 00:03:30,790 --> 00:03:31,340 Ne, ne, ne. 122 00:03:31,340 --> 00:03:31,600 O ne. 123 00:03:31,600 --> 00:03:31,940 Tai yra mano. 124 00:03:31,940 --> 00:03:32,580 >> David J. Malan: Oi, jūs turite Smith. 125 00:03:32,580 --> 00:03:33,415 GERAI. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Taip, aš gavo Smith čia. 127 00:03:34,040 --> 00:03:34,700 Atsiprašome, vaikinai. 128 00:03:34,700 --> 00:03:35,860 Maniau Michael-- mes ieško Michael. 129 00:03:35,860 --> 00:03:36,550 Atsiprašau. 130 00:03:36,550 --> 00:03:37,550 >> David J. Malan: Tai gerai. 131 00:03:37,550 --> 00:03:39,950 Gerai, dabar mes į Paccini ir Sūnų. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini ir sūnūs. 133 00:03:41,242 --> 00:03:43,158 David J. Malan: Tik jūs ir aš yra apie tai. 134 00:03:43,158 --> 00:03:44,050 GERAI. 135 00:03:44,050 --> 00:03:45,130 Raskite mus 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 Mes R už šiukšlių. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Šiukšlės. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Tai ketina užtrukti. 143 00:03:52,480 --> 00:03:54,340 >> [Atsakyti] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 David J. Malan: Avalynė. 146 00:03:56,720 --> 00:03:58,080 Mes į batus. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Dabar mes gonna-- 148 00:04:00,210 --> 00:04:01,105 >> David J. Malan: gražus. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Atsakyti] 151 00:04:03,620 --> 00:04:05,440 O, tai puiku. 152 00:04:05,440 --> 00:04:06,910 [Atsakyti] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> David J. Malan: Tai gerai. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: O, tai yra gerai. 156 00:04:11,365 --> 00:04:14,425 Aš nemanau, kad aš ruošiuosi turi PSAT bičiuliai po šio. 157 00:04:14,425 --> 00:04:15,300 David J. Malan: Geras. 158 00:04:15,300 --> 00:04:16,078 Sporto. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporto. 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: Gerai. 162 00:04:19,459 --> 00:04:21,600 Taigi leiskite ašara tai per pusę. 163 00:04:21,600 --> 00:04:22,270 Viskas gerai. 164 00:04:22,270 --> 00:04:25,606 Tai baigiasi blogai vistiek, nes Mike Smith nebus geltonieji puslapiai. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> David J. Malan: Ne, tai gerai. 167 00:04:27,140 --> 00:04:28,930 Bet tegul apsimeta kaip jis šiame puslapyje. 168 00:04:28,930 --> 00:04:33,260 Taigi dabar jūs sutrumpino problemą žemyn kad viename puslapyje, ir mes nustatėme, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Didelio džiaugsmo] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Gerai, ačiū. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 GERAI. 174 00:04:41,200 --> 00:04:43,646 Tai buvo nepaprastas. 175 00:04:43,646 --> 00:04:45,954 Bet tai dar greičiau buvo nei tiesinės paieškos, 176 00:04:45,954 --> 00:04:47,870 kuriame mes pradėsime ne pradedant knygos, 177 00:04:47,870 --> 00:04:51,210 ir mes perkelti savo kelią iš kairės į dešinę, galiausiai ieško Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Ir taip, jei telefonas knyga turėjo gal 1000 puslapių, 179 00:04:53,540 --> 00:04:56,300 gal jis ėmėsi mums 10 ar taip puslapis ašaros. 180 00:04:56,300 --> 00:04:59,380 >> Tačiau jums gali būti išnaudojamos palietė prielaidą, 181 00:04:59,380 --> 00:05:03,602 per visa tai, ir kuri yra pasakyti, kad telefonas užsisakyti iš anksto buvo kas? 182 00:05:03,602 --> 00:05:04,310 Auditorija: Rūšiuota. 183 00:05:04,310 --> 00:05:05,000 David J. Malan: Tai rūšiuojami. 184 00:05:05,000 --> 00:05:05,160 Teisė? 185 00:05:05,160 --> 00:05:07,909 Tai rūšiuojami pagal abėcėlę, taip kad visi iš šių pavadinimų ir numeriai 186 00:05:07,909 --> 00:05:11,230 yra rūšiuojami nuo A s į Z ir abėcėlę tarp jų. 187 00:05:11,230 --> 00:05:13,100 Tačiau šiandien, mes dabar paklausti klausimas, gerai, 188 00:05:13,100 --> 00:05:16,170 Kaip "Verizon arba telefonas Bendrovė gauti jį į tos valstybės? 189 00:05:16,170 --> 00:05:19,560 >> Nes tai vienas dalykas, siekiant pritraukti kad prielaida, ir todėl, 190 00:05:19,560 --> 00:05:22,570 išspręsti su problema algoritmas efektyviau. 191 00:05:22,570 --> 00:05:24,900 Bet mes niekada paklausė nulio savaitę, gerai, 192 00:05:24,900 --> 00:05:27,790 Kiek tai kainuos "Verizon" ar kažkas 193 00:05:27,790 --> 00:05:29,620 gauti, kad telefono knygą rūšiuotų tam? 194 00:05:29,620 --> 00:05:29,780 >> Teisė? 195 00:05:29,780 --> 00:05:31,529 Nesvarbu, jei žiūrint Mike Smith 196 00:05:31,529 --> 00:05:35,190 yra super greitas, jei ji nukelia į metų rūšiuoti puslapius pradžių. 197 00:05:35,190 --> 00:05:35,690 Teisė? 198 00:05:35,690 --> 00:05:38,620 Jūs galite taip pat tiesiog atsijoti per atsitiktinių imčių telefonų knygoje, 199 00:05:38,620 --> 00:05:40,690 jei jis bus super brangu rūšiuoti. 200 00:05:40,690 --> 00:05:42,350 Taigi, jei mes galime turėti dar vieną savanorį. 201 00:05:42,350 --> 00:05:46,350 Paimkime pažvelgti čia kaip mes might-- nagi up-- kaip 202 00:05:46,350 --> 00:05:48,100 mes galime eiti apie rūšiavimą jų. 203 00:05:48,100 --> 00:05:51,990 >> Ir jei Jordanija tikrųjų galėtų prisijungti prie mūsų čia ant scenos. 204 00:05:51,990 --> 00:05:55,100 Nagi už akimirką. 205 00:05:55,100 --> 00:05:56,359 Koks tavo vardas? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 David J. Malan: Caroline, nagi iki. 208 00:05:58,691 --> 00:06:02,070 Ir jums bus sujungtos man ir Jordanijos čia. 209 00:06:02,070 --> 00:06:03,800 Karolina, ačiū. 210 00:06:03,800 --> 00:06:04,300 Gerai. 211 00:06:04,300 --> 00:06:08,330 Taigi, ką mes turime čia Caroline 26 mėlyna knygos 212 00:06:08,330 --> 00:06:10,747 kad FAS naudoja administruoti tam tikri baigiamuosius egzaminus. 213 00:06:10,747 --> 00:06:13,330 Tai vis sunku rasti, bet ką mes padarėme iš anksto 214 00:06:13,330 --> 00:06:15,800 yra tai, kad mes įdėti kažkieno vardą ant kiekvieno iš jų priekyje, 215 00:06:15,800 --> 00:06:18,133 bet mes nuolat jį paprasta iki tada pradėti iš vardai ir pavardės. 216 00:06:18,133 --> 00:06:22,720 Taigi mes įdėti asmenį su pavadinimu L, D, J, B, visą kelią nuo A iki Z, 217 00:06:22,720 --> 00:06:24,090 bet jie atsitiktine tvarka. 218 00:06:24,090 --> 00:06:26,890 Ir taip, jei galėtumėte, kalbėti tavo kelią per problema, kaip jums 219 00:06:26,890 --> 00:06:31,620 tai padaryti, galite eiti į priekį ir rūšiuoti jų mums, nuo A iki Z. 220 00:06:31,620 --> 00:06:34,070 >> Auditorija: Gerai, kad L yra kaip, viduryje. 221 00:06:34,070 --> 00:06:35,050 C prasideda. 222 00:06:35,050 --> 00:06:42,410 B. J prieš L. B Q. 223 00:06:42,410 --> 00:06:45,140 >> David J. Malan: laikykite, kad pagalvojo vieną sekundę. 224 00:06:45,140 --> 00:06:48,910 Nes kitaip, tai yra tik Jums įdomu, ME, ir Jordanija. 225 00:06:48,910 --> 00:06:49,724 Čia mes eiti. 226 00:06:49,724 --> 00:06:50,640 Auditorija: [nesigirdi]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 David J. Malan: Gerai. 229 00:06:58,090 --> 00:06:59,310 Ką tu darai? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M ateina po O. 231 00:07:01,730 --> 00:07:02,564 >> David J. Malan: Gerai. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE O. 233 00:07:03,064 --> 00:07:04,120 David J. Malan: "O, gerai. 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. Taip. 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, todėl atrodo, kad jūs esate making-- nesustoti. 238 00:07:10,689 --> 00:07:12,730 Jis atrodo kaip jūs darote didelis krūva per čia 239 00:07:12,730 --> 00:07:13,910 ir rūšis didelis krūva ten. 240 00:07:13,910 --> 00:07:16,230 Todėl pirmoji pusė abėcėlės, Antroji pusė abėcėlės. 241 00:07:16,230 --> 00:07:16,460 GERAI. 242 00:07:16,460 --> 00:07:16,960 Geras. 243 00:07:16,960 --> 00:07:19,680 Geras išskaidyti problemą į dvi dalis. 244 00:07:19,680 --> 00:07:21,771 M, N X. Taip. 245 00:07:21,771 --> 00:07:22,270 CAROLINE K. 246 00:07:22,270 --> 00:07:22,980 David J. Malan: Gerai. 247 00:07:22,980 --> 00:07:25,070 K. Taigi jūs rūšies pasirinkdami vienas jų po kito, 248 00:07:25,070 --> 00:07:27,620 išleisti jį kairę arba į dešinę, arba Z vyksta ant grindų. 249 00:07:27,620 --> 00:07:28,012 GERAI. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: ZA vyksta ant grindų. 251 00:07:29,190 --> 00:07:29,360 >> David J. Malan: Gerai. 252 00:07:29,360 --> 00:07:30,920 Y vyksta ant grindų. 253 00:07:30,920 --> 00:07:31,735 Dabar mes galime įdėti 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 vyksta į kairę. 256 00:07:33,700 --> 00:07:36,017 S vyksta teisinga. 257 00:07:36,017 --> 00:07:37,642 Visos teisės A vyksta visą kelią į kairę. 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: Dabar gerai. 260 00:07:39,873 --> 00:07:43,260 Mes turime A, B, C. W. vyksta ten. 261 00:07:43,260 --> 00:07:45,566 Visos teisės 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. Geras. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Centre, aš gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. Malan: Gerai. 266 00:07:50,000 --> 00:07:52,375 Taigi dabar mes ketiname rūšies iš sujungti šiuos įvairius poliais. 267 00:07:52,375 --> 00:08:00,730 Taigi per C, tada matau D ir E ir F, ir G, ir H, ir I. Nica. 268 00:08:00,730 --> 00:08:05,540 J K. Ir tada, tai krūva yra apverstą, bet viskas OK. 269 00:08:05,540 --> 00:08:06,040 Tikrai. 270 00:08:06,040 --> 00:08:07,240 Mes galime sumažinti kai kampuose. 271 00:08:07,240 --> 00:08:07,950 GERAI. 272 00:08:07,950 --> 00:08:10,530 Ir tada turime W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Taip. 274 00:08:11,250 --> 00:08:11,880 >> David J. Malan: Puikiai. 275 00:08:11,880 --> 00:08:14,122 Taigi didelis ačiū Caroline rūšiavimo jų. 276 00:08:14,122 --> 00:08:15,030 >> [Didelio džiaugsmo] 277 00:08:15,030 --> 00:08:17,287 >> Ačiū. 278 00:08:17,287 --> 00:08:18,120 Labai ačiū. 279 00:08:18,120 --> 00:08:22,910 Taigi, dabar aptarkime akimirkai kaip Caroline vaikščiojo, darydamas, kad 280 00:08:22,910 --> 00:08:26,040 ir ką tiksliai mes galėjo to-- kaip mes 281 00:08:26,040 --> 00:08:28,409 galėjo išspręsti, kad problema, kai mes buvome tik 282 00:08:28,409 --> 00:08:29,950 suteikta visa krūva atsitiktinių įėjimai. 283 00:08:29,950 --> 00:08:31,610 >> Na, atrodo, kad ten buvo sistemos ten bitų? 284 00:08:31,610 --> 00:08:32,110 Teisė. 285 00:08:32,110 --> 00:08:34,495 Taigi ankstesnių laiškų abėcėlė, ji 286 00:08:34,495 --> 00:08:37,120 buvo išleisti į kairę, ir vėliau raidės abėcėlės, 287 00:08:37,120 --> 00:08:38,270 ji buvo išleisti į dešinę. 288 00:08:38,270 --> 00:08:40,500 Ir kuo greičiau ji rado kai artimieji raidės, ones 289 00:08:40,500 --> 00:08:43,124 kad eiti šalia viena kitos, ji būtų įdėti tuos tvarka. 290 00:08:43,124 --> 00:08:46,750 Ir todėl mes natūra turėjo tai mažas krūvos rūšiuotų žaliavų pasikartojimui. 291 00:08:46,750 --> 00:08:50,540 >> Ir taip, kad visai patinka tai, ką Daugelis iš mūsų žmonės būtų padaryti. 292 00:08:50,540 --> 00:08:53,530 Mes tarsi atsijoti per jį, ir mes norime rūšies turėti mechanizmą. 293 00:08:53,530 --> 00:08:56,930 Bet tai gali būti sunku rašyti jį žemyn SE formulę per. 294 00:08:56,930 --> 00:08:59,010 Jis manė, šiek tiek daugiau organinių kad ne. 295 00:08:59,010 --> 00:09:02,560 Taigi pažiūrėkime, jei mes galime dabar jungiasi Su mažiau sąnaudų problema. 296 00:09:02,560 --> 00:09:05,170 >> Vietoj 26, tegul kažką daryti kur kas mažiau 297 00:09:05,170 --> 00:09:09,890 su tik pasakyti, septyni, už Šios durys, taip sakant. 298 00:09:09,890 --> 00:09:11,300 Ar ten tik septyni numeriai? 299 00:09:11,300 --> 00:09:15,240 Ir jei tikslas dabar ranka yra rasti vertę, 300 00:09:15,240 --> 00:09:17,850 pažiūrėkime, kaip efektyviai mes galime eiti apie tai daryti. 301 00:09:17,850 --> 00:09:22,460 Ir tegul pamatyti, jei mes galime dabar pradėti taikyti kai kuriuos skaičius, 302 00:09:22,460 --> 00:09:26,310 arba kai formulės, su kuria apibūdinti mūsų telefonų knygoje efektyvumas 303 00:09:26,310 --> 00:09:31,060 algoritmas, mūsų egzaminas knyga algoritmas ir apskritai ieškant informacijos. 304 00:09:31,060 --> 00:09:34,770 >> Taigi už tai, leiskite man eiti į priekį ir ant jutiklinio ekrano nei čia 305 00:09:34,770 --> 00:09:41,100 taikstytis naršyklę, kuri turi tiksliai šie septyni durys. 306 00:09:41,100 --> 00:09:46,670 Ir jei mes galime gauti vieną kitą pasisiūlyti ateiti per čia 307 00:09:46,670 --> 00:09:48,480 Aš įdėti tuos pačius duris čia. 308 00:09:48,480 --> 00:09:49,170 Greita savanoris. 309 00:09:49,170 --> 00:09:51,130 >> Šis one-- demo vyksta kad greitesnis ir greitesnis dabar. 310 00:09:51,130 --> 00:09:51,600 Nagi žemyn. 311 00:09:51,600 --> 00:09:52,308 Koks tavo vardas? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevoras. 313 00:09:53,040 --> 00:09:53,998 >> David J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Gerai, Trevoras, nagi žemyn. 315 00:09:55,770 --> 00:09:59,212 Taigi Trevoras buvo čia pasisiūlė padaryti panašią problemą, bet vienas, kad 316 00:09:59,212 --> 00:10:02,170 siauresnės apimties, ir kad vyksta leisti mums pabandyti įforminti dabar 317 00:10:02,170 --> 00:10:03,970 už rūšiavimas šiuos numerius procesas. 318 00:10:03,970 --> 00:10:05,500 >> Taigi Trevoras, nice to meet jums. 319 00:10:05,500 --> 00:10:08,720 Taigi čia yra masyvas, taip kalbėti, septynių durų sąrašą. 320 00:10:08,720 --> 00:10:10,327 Eiti į priekį ir mus rasti skaičių 50. 321 00:10:10,327 --> 00:10:12,410 Ir tada, po to,, papasakoti, kaip jums rasti ją. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Jei be-- visą teisę. 324 00:10:20,040 --> 00:10:21,945 Taip, tai yra vienas čia? 325 00:10:21,945 --> 00:10:24,680 Uh Oh. 326 00:10:24,680 --> 00:10:25,560 GERAI. 327 00:10:25,560 --> 00:10:26,680 Jūs paspaudėte, kad vienas. 328 00:10:26,680 --> 00:10:28,690 Geras. 329 00:10:28,690 --> 00:10:29,780 >> Ir gerai. 330 00:10:29,780 --> 00:10:30,970 Dabar jūs paspaudėte, kad vienas. 331 00:10:30,970 --> 00:10:34,060 Ir leiskite man duoti jums mikrofoną, taip, kad jūs turite jį vos akimirką. 332 00:10:34,060 --> 00:10:37,000 Eiti į priekį ir spustelėkite šalia durų, kad jūs ketinate. 333 00:10:37,000 --> 00:10:39,812 Taip gerai. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Ar galiu nuimkite duris? 335 00:10:41,020 --> 00:10:42,620 David J. Malan: Ne, jūs negalite nuimkite. 336 00:10:42,620 --> 00:10:43,119 TREVOR: Gerai. 337 00:10:43,119 --> 00:10:43,974 Šitas. 338 00:10:43,974 --> 00:10:45,640 David J. Malan: Kur tu nori eiti? 339 00:10:45,640 --> 00:10:46,410 Kuris? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Tai viena. 341 00:10:47,230 --> 00:10:48,042 >> David J. Malan: Ne 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: Gerai. 343 00:10:48,450 --> 00:10:48,735 Šitas. 344 00:10:48,735 --> 00:10:49,020 >> David J. Malan: Taip. 345 00:10:49,020 --> 00:10:49,700 Tai buvo gera. 346 00:10:49,700 --> 00:10:50,380 Gerai. 347 00:10:50,380 --> 00:10:53,900 Taigi, kas buvo jūsų algoritmu arba tvarka tai daryti, Laisvas valdo? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Aš ką tik išgyveno durys kol radau 50. 349 00:10:56,149 --> 00:10:56,940 David J. Malan: Gerai. 350 00:10:56,940 --> 00:10:58,150 Puikus algoritmas. 351 00:10:58,150 --> 00:10:59,540 Taigi, kad viskas gerai. 352 00:10:59,540 --> 00:11:03,120 Nes iš tiesų, jei aš atskleisti tai, kas Už šių dviejų kitų durų, kas 353 00:11:03,120 --> 00:11:06,954 mes surasime, kad čia yra mes turime tik atsitiktinis įvestį. 354 00:11:06,954 --> 00:11:08,870 Taigi, kad iš tikrųjų buvo taip gerai, kaip jūs galite gauti. 355 00:11:08,870 --> 00:11:12,509 Ir iš tiesų, jūs turite geriau nei išsamiai ieško visą masyvą, 356 00:11:12,509 --> 00:11:15,300 nes tai būtų buvę tikrai nelaimingas, jei jau nukentėjo numerį 357 00:11:15,300 --> 00:11:16,604 50, per paskutinę duris. 358 00:11:16,604 --> 00:11:18,520 Bet kas, jei mes vietoj padovanojo tau prielaidą. 359 00:11:18,520 --> 00:11:20,630 Tarkime, aš tarsi visi Šios durys aplink, 360 00:11:20,630 --> 00:11:23,500 taip, kad jūs turite numeriai surūšiuoti šį kartą, 361 00:11:23,500 --> 00:11:29,730 bet šį kartą tai tikrai different-- šį kartą, 362 00:11:29,730 --> 00:11:32,640 tai tikrai rūšiuojami už jus. 363 00:11:32,640 --> 00:11:35,380 Ir dabar po ranka tikslas yra pataikyti skaičių 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: Gerai. 365 00:11:36,090 --> 00:11:37,670 >> David J. Malan: Kas Jūsų algoritmas bus? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Na, jei tai rūšiuojamos, tai arba ketina 367 00:11:39,628 --> 00:11:42,710 į be-- jei didžiausias iki didžiausių mažėjančia tvarka, tai bus pirmasis, 368 00:11:42,710 --> 00:11:44,751 arba, jei tai priešinga, ji bus paskutinis. 369 00:11:44,751 --> 00:11:48,897 Taigi aš tiesiog bakstelėkite šį dureles ir tada tiesiog bakstelėkite paskutinį duris. 370 00:11:48,897 --> 00:11:49,980 David J. Malan: Puikiai. 371 00:11:49,980 --> 00:11:50,270 Gerai. 372 00:11:50,270 --> 00:11:51,150 Taigi mes nustatėme, kad skaičių 50. 373 00:11:51,150 --> 00:11:52,970 Taigi kuo greičiau jūs žinojo jie buvo rūšiuojamos, mes 374 00:11:52,970 --> 00:11:55,040 galėjome išnaudoti šią prielaidą. 375 00:11:55,040 --> 00:11:57,040 Taigi jie per daug, kaip telefonų knyga pavyzdys. 376 00:11:57,040 --> 00:11:59,540 Kaip tik jūs turite, net su maža problema, kaip tai, 377 00:11:59,540 --> 00:12:02,380 Jūsų įėjimai iš anksto rūšiuojamos, mes galime iš tikrųjų rasti vertę, be abejo, 378 00:12:02,380 --> 00:12:03,130 efektyviau. 379 00:12:03,130 --> 00:12:05,800 >> Ir aš ne pasakyti jums, jei ji buvo rūšiuojami mažų iki didelių, ar didelis, mažas, 380 00:12:05,800 --> 00:12:08,080 ir todėl buvo labai protinga pradėti viename gale arba kita 381 00:12:08,080 --> 00:12:09,750 kad iš tikrųjų surasti tą siektiną vertę. 382 00:12:09,750 --> 00:12:11,400 Taigi padėkoti Trevor taip pat. 383 00:12:11,400 --> 00:12:13,260 Ir aš propose-- gražiai padaryta. 384 00:12:13,260 --> 00:12:16,960 Mes turime mažai įrašą, iš tikrųjų, kad yra tarp mūsų mėgstamų momentus CS50, 385 00:12:16,960 --> 00:12:19,700 kuriuo kartais šie demo ne visai eiti pagal planą. 386 00:12:19,700 --> 00:12:22,050 Ir iš tiesų, dabar, aš išrautas klaidingą sąsaja 387 00:12:22,050 --> 00:12:23,508 su kuria naudoti jutiklinį ekraną. 388 00:12:23,508 --> 00:12:24,660 Taigi, tai buvo mano kaltė ten. 389 00:12:24,660 --> 00:12:26,600 >> Taigi tai padarys už kitų metų klipas taip 390 00:12:26,600 --> 00:12:28,570 kodėl aš Paspaudę ant mano paties ekrano. 391 00:12:28,570 --> 00:12:31,390 Bet tegul priimti greitai pažvelgti kas atsitiko pernai 392 00:12:31,390 --> 00:12:34,770 su Jay, kuris atėjo daug kaip Trevor čia savanoriškai, 393 00:12:34,770 --> 00:12:39,380 ir šį trumpą klipą, pamatysite kaip tai tas pats demo ne visai 394 00:12:39,380 --> 00:12:41,074 atskleisti pačias pamokas. 395 00:12:41,074 --> 00:12:41,740 [Vaizdo įrašų atkūrimas] 396 00:12:41,740 --> 00:12:45,360 -Visos Noriu jums padaryti dabar rasti man, ir mums, 397 00:12:45,360 --> 00:12:51,674 tikrai, skaičius 50 vienas žingsnis metu. 398 00:12:51,674 --> 00:12:52,450 >> -The Numeris 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Numeris 50. 400 00:12:53,190 --> 00:12:55,356 Ir jūs galite atskleisti, kas po kiekvieno iš šių durų 401 00:12:55,356 --> 00:12:58,540 tiesiog palietus jį su pirštu. 402 00:12:58,540 --> 00:13:00,910 Velnias. 403 00:13:00,910 --> 00:13:02,870 >> [Atsakyti] 404 00:13:02,870 --> 00:13:03,806 >> [PABAIGA PLAYBACK] 405 00:13:03,806 --> 00:13:05,430 David J. Malan: Taigi, kad išėjo labai gerai. 406 00:13:05,430 --> 00:13:06,796 Tai buvo nerūšiuotos durys. 407 00:13:06,796 --> 00:13:08,670 Jay, žinoma, nustatė, kad jis pernelyg greitai. 408 00:13:08,670 --> 00:13:12,910 Trevoras padarė daug geresnį darbą kalbant apie tam Pojętny metu 409 00:13:12,910 --> 00:13:15,850 taip sakant, šiais metais trunka ilgiau jį rasti. 410 00:13:15,850 --> 00:13:17,950 Žinoma, tada mes davė Jay antras šansas, 411 00:13:17,950 --> 00:13:20,320 kurią mes rūšiuojami duris, kaip mes padarė Trevor, 412 00:13:20,320 --> 00:13:22,300 ir Trevoras padarė super gerai šį kartą. 413 00:13:22,300 --> 00:13:26,124 Bet Jay tai padarė pusę taip greitai. 414 00:13:26,124 --> 00:13:26,790 [Vaizdo įrašų atkūrimas] 415 00:13:26,790 --> 00:13:29,650 -The Tikslas dabar yra taip pat mus rasti skaičių 50, 416 00:13:29,650 --> 00:13:33,030 bet tai padaryti algoritmiškai ir papasakoti, kaip jūs ketinate apie tai. 417 00:13:33,030 --> 00:13:33,660 >> -GERAI. 418 00:13:33,660 --> 00:13:35,604 >> -O Jei jums rasti ją, jūs nuolat filmą. 419 00:13:35,604 --> 00:13:37,228 Jei nerandate, galite duoti jį atgal. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -OH! 422 00:13:38,860 --> 00:13:40,800 >> - [Nesigirdi] Gerai. 423 00:13:40,800 --> 00:13:46,236 Taigi, aš ruošiuosi patikrinti galus pirmiausia reikia patikrinti, ar there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Plojimai] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [PABAIGA PLAYBACK] 427 00:13:55,729 --> 00:13:56,520 David J. Malan: Gerai. 428 00:13:56,520 --> 00:13:59,760 Taigi rūšiavimo duris aiškiai veda prie didesnio efektyvumo. 429 00:13:59,760 --> 00:14:01,680 Ir taip, du kartus taip greitai, yra tai, ką aš ten reiškė. 430 00:14:01,680 --> 00:14:03,270 Ir taip Jay pasisekė abu kartus. 431 00:14:03,270 --> 00:14:06,685 Ir jis taip pat pasisekė, kad paskutinis metus, aš užsisakiau keletą Blu-ray diskus 432 00:14:06,685 --> 00:14:07,560 kad iš tikrųjų duoti. 433 00:14:07,560 --> 00:14:09,768 Aš atsiprašau šiemet, mes neturėjo tas pats, Laisvas valdo. 434 00:14:09,768 --> 00:14:11,540 Bet vis tiek geriau buvo keletą metų atgal. 435 00:14:11,540 --> 00:14:14,820 Ir kai kurie iš jūsų gali žinoti kolega Sean, kuris, kai jis buvo CS50, 436 00:14:14,820 --> 00:14:17,780 buvo užginčytas su Tiksli Ta pati problema, nors ir SD, 437 00:14:17,780 --> 00:14:19,360 kaip jūs netrukus pamatysite, atgal per dieną. 438 00:14:19,360 --> 00:14:22,622 Ir jūs pamatysite, kad ne tik nebuvo jis užtrukti šiek tiek ilgiau nei Jay, 439 00:14:22,622 --> 00:14:25,580 šiek tiek ilgiau nei Trevor, tai buvo iš tikrųjų tai puiki galimybė 440 00:14:25,580 --> 00:14:29,820 užsiimti beveik kiekvienas Minia a la Kaina yra teisinga, skatinant 441 00:14:29,820 --> 00:14:31,889 jam rasti skaičių buvome ieško. 442 00:14:31,889 --> 00:14:32,930 Leiskite. priimti greitai pažvelgti. 443 00:14:32,930 --> 00:14:33,320 >> [Vaizdo įrašų atkūrimas] 444 00:14:33,320 --> 00:14:33,820 >> -GERAI. 445 00:14:33,820 --> 00:14:36,680 Taigi jūsų užduotis čia Sean, yra tokia. 446 00:14:36,680 --> 00:14:40,860 Aš paslėpta už tai durys skaičius septyni. 447 00:14:40,860 --> 00:14:45,120 Bet nuošalioje kai kuriose iš šių durų taip pat yra ir kitų neigiami skaičiai. 448 00:14:45,120 --> 00:14:47,500 Ir jūsų tikslas yra galvoti Šio viršų eilės numerių 449 00:14:47,500 --> 00:14:50,390 kaip tik masyvo, arba tiesiog seka popieriaus lapų, 450 00:14:50,390 --> 00:14:51,510 su numeriais už jų. 451 00:14:51,510 --> 00:14:55,540 Ir jūsų tikslas yra, tik naudojant viršaus masyvas čia rasite me skaičius septyni. 452 00:14:55,540 --> 00:14:58,570 Ir mes tada ketiname kritika kaip jums eiti apie tai daro. 453 00:14:58,570 --> 00:14:59,070 -Gerai. 454 00:14:59,070 --> 00:15:00,850 -Find Mums skaičius septyni, prašau. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Ne. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Penki, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Atsakyti] 461 00:15:24,770 --> 00:15:25,910 >> Tai ne triukas klausimas. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Vienas. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Atsakyti] 466 00:15:34,695 --> 00:15:37,861 Šiuo metu, jūsų rezultatas nėra labai gerai, todėl jums gali taip pat nesustoti. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Trys. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Atsakyti] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Tęsk. 473 00:15:47,774 --> 00:15:50,690 Atvirai kalbant, aš negaliu padėti, bet įdomu ką jūs net galvoti apie, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Atsakyti] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Tik viršutinėje eilutėje, todėl jūs turite tris kairę. 477 00:15:55,020 --> 00:15:56,200 Taigi mane surasti septyni. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Atsakyti] 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 Septynios. 484 00:16:26,946 --> 00:16:28,780 >> [Plojimai] 485 00:16:28,780 --> 00:16:29,426 >> Gerai. 486 00:16:29,426 --> 00:16:30,360 >> [PABAIGA PLAYBACK] 487 00:16:30,360 --> 00:16:31,840 >> David J. Malan: kad galėtume žiūrėti šiuos visą dieną. 488 00:16:31,840 --> 00:16:34,090 Ir, žinoma, kai kurie iš šiemet demo galbūt 489 00:16:34,090 --> 00:16:36,330 dabar baigti Kitas metų vaizdo, taip pat. 490 00:16:36,330 --> 00:16:39,040 Taigi, dabar tegul iš tikrųjų sutelkti dėmesį į algoritmų 491 00:16:39,040 --> 00:16:42,140 čia, ir pamatyti, jei mes negalime dabar pradeda formalizuoti 492 00:16:42,140 --> 00:16:46,650 kaip mes galime eiti apie tai mūsų duomenis į šios valstybės, kad ji manimi rūšiuojamos, 493 00:16:46,650 --> 00:16:50,054 taip, kad galiausiai, mes galime iš tikrųjų ieškoti ją efektyviau. 494 00:16:50,054 --> 00:16:52,470 Ir nors mes ketiname naudoti gana mažas duomenų rinkinius, 495 00:16:52,470 --> 00:16:54,511 kaip aštuoni numeriai ir mes turime čia ant lentos, 496 00:16:54,511 --> 00:16:58,230 galiausiai tie patys idėjos galėtų taikyti 1000 įėjimai, milijonas įėjimai, 497 00:16:58,230 --> 00:17:02,100 4 mlrd įėjimai, nes algoritmai yra bus iš esmės ta pati. 498 00:17:02,100 --> 00:17:05,359 >> Ir todėl tai yra mūsų paskutinis galimybė savanorių šiandien 499 00:17:05,359 --> 00:17:09,790 bet galbūt labiausiai dalyvauja viena, dėl kurių mes turime aštuonis savanorius 500 00:17:09,790 --> 00:17:12,960 sugalvoti ir vaikščioti su mumis per procesas rūšiavimas, ką netrukus 501 00:17:12,960 --> 00:17:15,212 būti šių muzikos stovi čia. 502 00:17:15,212 --> 00:17:16,170 Leiskite man pradėti vėl čia. 503 00:17:16,170 --> 00:17:19,692 >> Taigi vienas iš turquoise-- žalia tai? 504 00:17:19,692 --> 00:17:21,130 Ar jūs įsipareigojant? 505 00:17:21,130 --> 00:17:21,630 Du. 506 00:17:21,630 --> 00:17:23,069 Nagi žemyn. 507 00:17:23,069 --> 00:17:23,569 GERAI. 508 00:17:23,569 --> 00:17:24,420 Trys. 509 00:17:24,420 --> 00:17:25,400 Keturi. 510 00:17:25,400 --> 00:17:27,247 Tegul me-- Gerai, penki. 511 00:17:27,247 --> 00:17:28,830 Jūs esate nominuotas jūsų draugas. 512 00:17:28,830 --> 00:17:31,340 Šeši, septyni, aštuoni. 513 00:17:31,340 --> 00:17:32,130 Nagi iki. 514 00:17:32,130 --> 00:17:32,630 Gerai. 515 00:17:32,630 --> 00:17:33,190 Labai ačiū. 516 00:17:33,190 --> 00:17:33,689 Nagi iki. 517 00:17:33,689 --> 00:17:34,790 Nagi iki. 518 00:17:34,790 --> 00:17:35,330 >> Gerai. 519 00:17:35,330 --> 00:17:38,890 Taigi, ką mes turime here-- ir tai yra tarp daugiau nepatogios tie, 520 00:17:38,890 --> 00:17:42,390 nes tai reikalauja, kad jūs humoras man tik už šiek tiek laiko. 521 00:17:42,390 --> 00:17:43,442 Jūs turi būti numeris vienas. 522 00:17:43,442 --> 00:17:44,150 Koks tavo vardas? 523 00:17:44,150 --> 00:17:44,610 >> Ananas: Annanas. 524 00:17:44,610 --> 00:17:45,526 >> David J. Malan: Annanas. 525 00:17:45,526 --> 00:17:46,092 Davidas. 526 00:17:46,092 --> 00:17:46,800 Koks tavo vardas? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Juozapas. 528 00:17:47,140 --> 00:17:49,190 >> David J. Malan: Juozapas Jūs esate numeris du. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, numeris trys. 530 00:17:52,260 --> 00:17:53,722 Stefanas numeris keturi. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 David J. Malan: Cynthia numeris penki. 533 00:17:57,548 --> 00:17:58,452 [Nesigirdi] 534 00:17:58,452 --> 00:17:59,618 David J. Malan: [nesigirdi]. 535 00:17:59,618 --> 00:18:00,391 Davidas numeris šeši. 536 00:18:00,391 --> 00:18:00,890 Matt: Matt. 537 00:18:00,890 --> 00:18:02,160 David J. Malan: Matt skaičius septyni. 538 00:18:02,160 --> 00:18:02,850 Ir? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> David J. Malan: Waverly numeris aštuoni. 541 00:18:04,470 --> 00:18:04,970 Gerai. 542 00:18:04,970 --> 00:18:06,510 Jei could-- šūksniais. 543 00:18:06,510 --> 00:18:08,820 Jei jums visiems, kaip jūsų Pirmasis uždavinys, yra 544 00:18:08,820 --> 00:18:10,820 Yra aštuonios muzikos stendai Čia susiduria auditoriją. 545 00:18:10,820 --> 00:18:14,200 Jei galite įdėti savo numerius šie muzikos stovi tokiu būdu, 546 00:18:14,200 --> 00:18:16,560 kad jie išsirikiuoja su tie patys numeriai ant lentos. 547 00:18:16,560 --> 00:18:19,560 Todėl įsitikinkite patys atrodyti, kad išleisti savo numerius šių muzikos 548 00:18:19,560 --> 00:18:21,960 stovi čia. 549 00:18:21,960 --> 00:18:25,980 Puikus iki šiol. 550 00:18:25,980 --> 00:18:26,600 >> Puikus. 551 00:18:26,600 --> 00:18:26,890 GERAI. 552 00:18:26,890 --> 00:18:29,556 Taigi dabar mes ketiname paklausti klausimas keletą skirtingų būdų. 553 00:18:29,556 --> 00:18:31,610 Kaip mes galime eiti apie rūšiavimas Šie žmonės čia? 554 00:18:31,610 --> 00:18:34,500 Kadangi mes turėjome keletą požiūrių anksčiau, pagal kurį mes buvome 555 00:18:34,500 --> 00:18:36,360 rūšies priėmimo du skirtingus kibirus. 556 00:18:36,360 --> 00:18:38,842 Ir tada mes paprastai buvo susegimas kartu. 557 00:18:38,842 --> 00:18:41,050 Kaip greitai, kaip mes matėme du numerius kad priklausė kartu, 558 00:18:41,050 --> 00:18:41,975 mes juos kartu. 559 00:18:41,975 --> 00:18:43,350 Dvi raidės, kurios priklauso kartu. 560 00:18:43,350 --> 00:18:45,058 >> Bet pažiūrėkime, jei mes negali įteisinti tai, 561 00:18:45,058 --> 00:18:48,044 kad mes galiausiai turi kai pseudo-kodas bus, 562 00:18:48,044 --> 00:18:49,710 su kuria jūs galite išspręsti šias problemas. 563 00:18:49,710 --> 00:18:51,870 Taigi dabar aš dairytis ne šie skaičiai čia. 564 00:18:51,870 --> 00:18:55,030 Ir aš matau visa krūva klaidų. 565 00:18:55,030 --> 00:18:57,750 Galų gale, aš noriu vieną ant kairysis ir aštuoni dešinėje. 566 00:18:57,750 --> 00:19:00,650 >> Ir taip aš žiūriu šių dviejų, keturių ir dviejų. 567 00:19:00,650 --> 00:19:02,930 Ir kas yra problema, žinoma? 568 00:19:02,930 --> 00:19:04,261 Taip. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Du akivaizdžiai ateina prieš keturi, kad jūs žinote, ką? 571 00:19:07,160 --> 00:19:10,210 Leiskite pirmiausia imtis gobšus požiūrį, jei bus, panašiai kaip problema 572 00:19:10,210 --> 00:19:13,790 nustatyti one-- Jei prisimenate iš Standard Edition problema nustatyti vieną, 573 00:19:13,790 --> 00:19:16,820 kur aš tiesiog vietoje išspręsti problemą tai čia priešais mane 574 00:19:16,820 --> 00:19:17,690 ir pamatyti, kur ji veda mane. 575 00:19:17,690 --> 00:19:17,870 >> GERAI. 576 00:19:17,870 --> 00:19:20,161 Taigi du keturi, leiskite man eiti į priekį ir tiesiog sukeisti tau du. 577 00:19:20,161 --> 00:19:22,400 Jei galite fiziškai judėti patys ir jūsų popierius, 578 00:19:22,400 --> 00:19:25,040 Man atrodo, kad Dotarłeś sąrašą geriau valstybei. 579 00:19:25,040 --> 00:19:26,330 >> Dabar, jie geri. 580 00:19:26,330 --> 00:19:28,480 Aš ruošiuosi judėti į priekį, keturių ir šešių, gerai atrodo. 581 00:19:28,480 --> 00:19:29,110 Ne problema. 582 00:19:29,110 --> 00:19:30,440 Šeši aštuoni, Gerai. 583 00:19:30,440 --> 00:19:31,860 Aštuoni ir viena, ir kita problema. 584 00:19:31,860 --> 00:19:34,750 Nes tai, kas tiesa apie aštuonių ir vienas? 585 00:19:34,750 --> 00:19:36,990 Vienas ateina prieš aštuonių, ir taip ką mums daryti? 586 00:19:36,990 --> 00:19:38,090 Leiskite apsikeitimo šias dvi. 587 00:19:38,090 --> 00:19:39,316 Vienas aštuoni. 588 00:19:39,316 --> 00:19:40,690 Ir dabar, aš ruošiuosi nesustoti. 589 00:19:40,690 --> 00:19:42,030 Aš ruošiuosi nuolat ieško priekį. 590 00:19:42,030 --> 00:19:42,840 Ir pažiūrėkime, kas vyksta. 591 00:19:42,840 --> 00:19:44,680 Aštuoni ir trys, ir Žinoma, iš tvarka. 592 00:19:44,680 --> 00:19:45,815 Leiskite apsikeitimo. 593 00:19:45,815 --> 00:19:46,940 Aštuonių ir septynių, žinoma. 594 00:19:46,940 --> 00:19:47,481 Neveikia. 595 00:19:47,481 --> 00:19:48,280 Leiskite apsikeitimo. 596 00:19:48,280 --> 00:19:49,940 Aštuoni ir penki, žinoma, galime apsikeitimo. 597 00:19:49,940 --> 00:19:50,560 Gerai. 598 00:19:50,560 --> 00:19:51,880 Sąrašas surūšiuotas. 599 00:19:51,880 --> 00:19:53,060 Taip? 600 00:19:53,060 --> 00:19:54,280 >> Gerai, žinoma, nėra. 601 00:19:54,280 --> 00:19:55,860 Bet tai šiek tiek geriau, tiesa? 602 00:19:55,860 --> 00:19:57,270 Kadangi pranešimas, kas atsitiko. 603 00:19:57,270 --> 00:20:01,749 Kiekvieną kartą, kai mes atlikome apsikeitimo mažesniu Taškų rūšies percolated, kad taip, 604 00:20:01,749 --> 00:20:03,790 ir didesnis skaičius percolated šį kelią, ar mes 605 00:20:03,790 --> 00:20:06,880 pradėti sakydamas burbuliukais į kairę arba į burbuliukais į dešinę. 606 00:20:06,880 --> 00:20:10,080 >> Dabar, tai nėra pakankamai, nes geriausiu skaičius gali 607 00:20:10,080 --> 00:20:11,990 persikėlė vienoje vietoje į priekį, arba blogiausiu atveju, 608 00:20:11,990 --> 00:20:13,880 skaičius gali būti persikėlė vienoje vietoje toliau. 609 00:20:13,880 --> 00:20:16,369 Taigi jūs žinote, ką šis natūra išdirba gana gerai iki šiol. 610 00:20:16,369 --> 00:20:17,410 Leiskite man tiesiog pabandykite dar kartą. 611 00:20:17,410 --> 00:20:18,880 Dviejų ir keturių, jie Gerai. 612 00:20:18,880 --> 00:20:20,180 Keturi šeši, jie Gerai. 613 00:20:20,180 --> 00:20:21,790 Šeši ir vienas iš tvarka. 614 00:20:21,790 --> 00:20:23,007 Taigi leiskite apsikeitimo jūs abu. 615 00:20:23,007 --> 00:20:25,840 Ir dabar, pastebėsite, kad problema s pradeda gauti šiek tiek geriau dar kartą. 616 00:20:25,840 --> 00:20:27,006 Šešių ir trijų iš tvarka. 617 00:20:27,006 --> 00:20:28,100 Leiskite apsikeitimo jūs abu. 618 00:20:28,100 --> 00:20:29,730 Šeši septyni, jūs gerai. 619 00:20:29,730 --> 00:20:32,230 Septynios ir penki, žinoma, iš tvarka. 620 00:20:32,230 --> 00:20:33,920 Septyni aštuoni, kad. 621 00:20:33,920 --> 00:20:36,470 Ir dabar, aš gali tekti tai padaryti dar kelis kartus. 622 00:20:36,470 --> 00:20:39,830 Ir iš tiesų, manau sau gal kiek kartų maksimaliai 623 00:20:39,830 --> 00:20:41,330 gali turiu vaikščioti pirmyn ir atgal? 624 00:20:41,330 --> 00:20:42,390 >> Mes grįžti prie to. 625 00:20:42,390 --> 00:20:43,700 Taigi du keturios tebėra Gerai. 626 00:20:43,700 --> 00:20:44,940 Keturi ir vienas, nope. 627 00:20:44,940 --> 00:20:45,747 Taigi, tegul apsikeitimo. 628 00:20:45,747 --> 00:20:47,830 Ir vėl pastebėti vizualiai viena yra natūra burbuliuoja 629 00:20:47,830 --> 00:20:49,163 į kairę, kur ji turėtų būti. 630 00:20:49,163 --> 00:20:50,010 Keturių ir trijų apsikeitimo. 631 00:20:50,010 --> 00:20:51,330 Keturi šeši. 632 00:20:51,330 --> 00:20:53,100 Šeši penki apsikeitimo. 633 00:20:53,100 --> 00:20:53,959 Šeši septyni. 634 00:20:53,959 --> 00:20:55,000 Septyni aštuoni yra gera. 635 00:20:55,000 --> 00:20:55,500 >> Geras. 636 00:20:55,500 --> 00:20:58,460 Mes vis dar geriau. 637 00:20:58,460 --> 00:20:59,130 Taigi pažiūrėkime. 638 00:20:59,130 --> 00:21:00,940 Dabar, mes turime du ir vienas. 639 00:21:00,940 --> 00:21:02,520 Žinoma, apsikeitimo. 640 00:21:02,520 --> 00:21:07,520 Dviejų ir trijų, trijų ir keturių, keturi ir penki, šeši ir septyni, septyni aštuoni. 641 00:21:07,520 --> 00:21:08,020 Geras. 642 00:21:08,020 --> 00:21:08,730 Ir žinote ką? 643 00:21:08,730 --> 00:21:11,190 Nes aš padariau vieną pakeitimą ten, leiskite man padaryti vieną normalumas patikrinti. 644 00:21:11,190 --> 00:21:13,023 Leiskite man pereiti visą kelią atgal į pradžioje. 645 00:21:13,023 --> 00:21:13,680 GERAI. 646 00:21:13,680 --> 00:21:14,750 Vienas iš jų, two-- Yup, pamatyti? 647 00:21:14,750 --> 00:21:15,870 Kažkas buvo negerai. 648 00:21:15,870 --> 00:21:18,420 Trys, keturi, penki, šeši, septyni, aštuoni. 649 00:21:18,420 --> 00:21:21,920 Ir šioje paskutinio perdavimo, yra jums patogu su mano dabar 650 00:21:21,920 --> 00:21:23,830 tvirtindami, kad yra rūšiuojami? 651 00:21:23,830 --> 00:21:24,330 GERAI. 652 00:21:24,330 --> 00:21:25,880 Vizualiai tai visiškai teisinga. 653 00:21:25,880 --> 00:21:28,410 Bet funkciškai ką nebuvo taip tiesiog atsitikti 654 00:21:28,410 --> 00:21:31,870 toje paskutinio perdavimo, kuris leidžia jums patvirtinti, kad šis sąrašas yra iš tiesų 655 00:21:31,870 --> 00:21:32,660 rūšiuoti? 656 00:21:32,660 --> 00:21:34,477 >> Ką man daryti, ar ne padaryti šį paskutinį perdavimą? 657 00:21:34,477 --> 00:21:35,810 Auditorija: Nebuvo jokių pakeitimų. 658 00:21:35,810 --> 00:21:36,120 David J. Malan: Atsiprašome? 659 00:21:36,120 --> 00:21:37,070 Auditorija: Nėra pakeitimų. 660 00:21:37,070 --> 00:21:38,653 David J. Malan: Nebuvo jokių pakeitimų. 661 00:21:38,653 --> 00:21:41,947 Taigi būtų kvaila ir man padaryti tą patį algoritmą vėl 662 00:21:41,947 --> 00:21:43,780 jei aš nepadarė keičia pirmą kartą. 663 00:21:43,780 --> 00:21:45,160 Ir valstybė nepasikeitė. 664 00:21:45,160 --> 00:21:47,576 Žinoma, aš nesiruošia padaryti Bet kokie pakeitimai antrą kartą. 665 00:21:47,576 --> 00:21:49,820 Ir taip, tai saugu dabar pasakyti, sąrašas surūšiuotas. 666 00:21:49,820 --> 00:21:52,069 >> Ir iš tikrųjų, tai yra, dabar kažkas, kad mes paprastai 667 00:21:52,069 --> 00:21:56,900 kvietimas burbulas rūšiuoti, kuriuo Porinis, Jūs ištaisyti klaidas vėl, 668 00:21:56,900 --> 00:22:00,210 ir vėl, ir vėl, ir jūs nesustoti ir atgal, 669 00:22:00,210 --> 00:22:03,370 ir pirmyn ir atgal, kol jums atlikti tokius apsikeitimo Ne, kuri vieta 670 00:22:03,370 --> 00:22:07,089 galite būti tikri, taip, aš baigė tvirtinimo visus klaidų. 671 00:22:07,089 --> 00:22:08,630 Leiskite naujo ir bandykite kitą metodą. 672 00:22:08,630 --> 00:22:11,590 Jei jus vaikinai gali grįžti į pavedimas jums buvo metu senumo, 673 00:22:11,590 --> 00:22:13,780 kuris atrodė kaip šis. 674 00:22:13,780 --> 00:22:17,640 Dabar galime imtis požiūris šiek tiek daugiau kaip egzamino knygos 675 00:22:17,640 --> 00:22:21,122 kuriuo buvome nuolat parinkus abėcėlės raidė 676 00:22:21,122 --> 00:22:22,830 kad mes rūšies norėjau elgtis su kitais. 677 00:22:22,830 --> 00:22:26,420 Gal tai buvo didelė raidė, pavyzdžiui, A, arba mažo raide Z. 678 00:22:26,420 --> 00:22:28,170 >> Taigi kiekvienas atgal tokia tvarka. 679 00:22:28,170 --> 00:22:29,800 O dabar leiskite man tai padaryti. 680 00:22:29,800 --> 00:22:34,880 Pažiūrėkime, aš žinau, aš turiu aštuoni numeriai čia. 681 00:22:34,880 --> 00:22:37,410 Aš ruošiuosi eiti į priekį ir tiesiog sąmoningai pasirinkti 682 00:22:37,410 --> 00:22:38,520 mažiausias elementai. 683 00:22:38,520 --> 00:22:38,760 Teisė? 684 00:22:38,760 --> 00:22:39,801 Tai atrodo intuityviai pernelyg. 685 00:22:39,801 --> 00:22:42,560 Kodėl manau, mažiausias elementas, įdėti jį ten, kur jis priklauso, 686 00:22:42,560 --> 00:22:45,280 tada gauti kitą mažiausią elementą, įdėti tai jei ji priklauso, ir tik pakartoti. 687 00:22:45,280 --> 00:22:46,820 >> Kadangi intuityviai, kad turėtų per darbą. 688 00:22:46,820 --> 00:22:48,441 Taigi keturi, tai yra gana mažas skaičius. 689 00:22:48,441 --> 00:22:49,940 Aš ruošiuosi prisiminti, kur tai yra. 690 00:22:49,940 --> 00:22:50,523 Palauk minutėlę. 691 00:22:50,523 --> 00:22:51,577 Du yra mažesnis. 692 00:22:51,577 --> 00:22:53,910 Tegul dabar man prisiminti, kur dvi yra, ir pamiršti apie keturi. 693 00:22:53,910 --> 00:22:55,050 Mes spręsti vėliau. 694 00:22:55,050 --> 00:22:56,460 Šeši, aš nesu suinteresuotas. 695 00:22:56,460 --> 00:22:57,810 Aštuoni, aš nesu suinteresuotas. 696 00:22:57,810 --> 00:22:59,780 Vienas iš jų yra mano naujas nedidelis skaičius. 697 00:22:59,780 --> 00:23:01,470 Taigi, aš ruošiuosi prisiminti, kur vienas yra. 698 00:23:01,470 --> 00:23:02,534 Trys neįdomu. 699 00:23:02,534 --> 00:23:03,450 Septyni, neįdomu. 700 00:23:03,450 --> 00:23:04,530 Penki neįdomu. 701 00:23:04,530 --> 00:23:07,390 >> Taigi be nukristi etapas šiais metais, 702 00:23:07,390 --> 00:23:09,890 Aš ruošiuosi patraukti skaičių one-- ir kas buvo tavo vardas dar kartą? 703 00:23:09,890 --> 00:23:10,150 >> Ananas: Annanas. 704 00:23:10,150 --> 00:23:11,220 >> David J. Malan: Annanas. 705 00:23:11,220 --> 00:23:13,540 Ir jei jūs galėtumėte prisijungti su manimi iš sąrašo pradžia, 706 00:23:13,540 --> 00:23:14,870 tegul padėti jums, jei jūs priklausote. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- koks tavo vardas? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefanas. 709 00:23:16,650 --> 00:23:18,191 >> David J. Malan: Stefan į kelią. 710 00:23:18,191 --> 00:23:23,490 Taigi prieš Stefan išsprendžia šią problema, ką turėtume daryti? 711 00:23:23,490 --> 00:23:25,412 Ką mes darome su Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Auditorija: [nesigirdi]. 713 00:23:27,269 --> 00:23:28,060 David J. Malan: Gerai. 714 00:23:28,060 --> 00:23:28,850 Taigi, mes galime tai padaryti. 715 00:23:28,850 --> 00:23:31,730 Mes galime tarsi imtis Stefan ir jo keturi, ir tiesiog įdėti jį į kintamąjį 716 00:23:31,730 --> 00:23:33,530 ir palaikykite jai kai laikotarpis, 717 00:23:33,530 --> 00:23:35,220 tokiu būdu kambarį numeris vienas. 718 00:23:35,220 --> 00:23:36,280 Ir tai nėra blogai. 719 00:23:36,280 --> 00:23:39,270 Galėčiau pasiūlyti, kodėl gi ne mes tiesiog įdėti Stefan čia? 720 00:23:39,270 --> 00:23:41,610 Kodėl tai gali pažeisti vieną idėjų mes pradėjome 721 00:23:41,610 --> 00:23:44,830 kalbame apie paskutinį kartą, praėjusią savaitę? 722 00:23:44,830 --> 00:23:45,330 Taip? 723 00:23:45,330 --> 00:23:45,740 >> Auditorija: [nesigirdi]. 724 00:23:45,740 --> 00:23:46,860 >> David J. Malan: Nėra už jį indeksas. 725 00:23:46,860 --> 00:23:49,735 Jei manote, kad tai, iš tiesų, kaip masyvo, tai yra, kaip neigiamas, 726 00:23:49,735 --> 00:23:52,900 todėl nėra atminties tikrųjų čia, jei tai iš tiesų masyvas, 727 00:23:52,900 --> 00:23:55,090 kaip mes paskelbė praėjusią savaitę paskaita. 728 00:23:55,090 --> 00:23:56,250 Taigi, mes turime tai padaryti. 729 00:23:56,250 --> 00:23:57,340 Mes galime laikyti jį į kintamąjį. 730 00:23:57,340 --> 00:23:57,820 >> Arba jūs žinote, ką? 731 00:23:57,820 --> 00:23:59,153 Aš girdėjau, kad kažkas rodo ją. 732 00:23:59,153 --> 00:24:01,020 Ką dar būtų galima padaryti su Stefan? 733 00:24:01,020 --> 00:24:03,770 Kodėl ne mes tiesiog iškeldinti jį ir įdėti jį per kur numeris vienas buvo. 734 00:24:03,770 --> 00:24:05,170 Taigi, jei norite eiti ten. 735 00:24:05,170 --> 00:24:07,300 Ir iš tikrųjų, tai yra gana geras sprendimas. 736 00:24:07,300 --> 00:24:10,480 Dabar, viena vertus, aš rūšies Made problemą blogiau. 737 00:24:10,480 --> 00:24:13,650 Keturi dabar tolyn iš kur ji turėtų būti. 738 00:24:13,650 --> 00:24:14,900 Ji turėtų būti link šio pusę. 739 00:24:14,900 --> 00:24:16,100 >> Bet žinote ką? 740 00:24:16,100 --> 00:24:17,630 Tai galėjo būti nepasisekimas. 741 00:24:17,630 --> 00:24:18,822 Gal numeris aštuoni buvo čia. 742 00:24:18,822 --> 00:24:20,530 Ir taip, gal mes būtume Dotarłeś pasisekė, 743 00:24:20,530 --> 00:24:22,460 ir stumti aštuonių arčiau pabaigos. 744 00:24:22,460 --> 00:24:24,710 Taigi, dienos pabaigoje, Jis rūšies visų vidurkiai iš. 745 00:24:24,710 --> 00:24:26,085 Mums nereikia rūpintis keturi. 746 00:24:26,085 --> 00:24:29,400 Viskas, ką aš rūpi dabar yra Pasirinkę mažiausią elementą. 747 00:24:29,400 --> 00:24:32,030 >> Ir dabar, ką aš ruošiuosi padaryti, tai pamiršti apie numeris vienas 748 00:24:32,030 --> 00:24:35,160 nuolat, nes žinau, kad Sąrašas už manęs dabar rūšiuojami. 749 00:24:35,160 --> 00:24:36,720 Taigi, mano sąrašas buvo anksčiau dydis aštuoni. 750 00:24:36,720 --> 00:24:37,720 Dabar, tai dydžio septyni. 751 00:24:37,720 --> 00:24:40,340 Taigi, mano problema yra gauti mažesni, nors tiesiškai. 752 00:24:40,340 --> 00:24:43,022 Taigi dabar aš ruošiuosi pasirinkti Dabartinė mažiausia elementas, du. 753 00:24:43,022 --> 00:24:46,520 Šeši, aštuoni, keturi, trys, septyni, penki. 754 00:24:46,520 --> 00:24:47,770 Tai buvo mažiausias elementas. 755 00:24:47,770 --> 00:24:49,416 Taigi, ką aš ketinu daryti with-- kas buvo jūsų vardas vėl? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Juozapas. 757 00:24:49,760 --> 00:24:50,085 >> David J. Malan: Juozapas? 758 00:24:50,085 --> 00:24:52,000 Mes ketiname palikti Juozapą vietoje. 759 00:24:52,000 --> 00:24:54,842 Dabar aš ruošiuosi apsimesti kad šie vaikinai are-- gerai, 760 00:24:54,842 --> 00:24:56,550 Žinau, kad šie du jau rūšiuojamos. 761 00:24:56,550 --> 00:24:58,424 Tegul dabar orientavimą į likusi sąrašo. 762 00:24:58,424 --> 00:25:00,080 Šeši yra dabartinė mažiausių. 763 00:25:00,080 --> 00:25:01,190 Aštuoni yra didesni. 764 00:25:01,190 --> 00:25:02,970 Keturi dabar dabartinė mažiausių. 765 00:25:02,970 --> 00:25:04,762 Trys dabar dabartinė mažiausių. 766 00:25:04,762 --> 00:25:07,720 Ir todėl dabar aš ruošiuosi pasirinkti tris, kas is-- koks tavo vardas dar kartą? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 David J. Malan: Serena, jei galėtumėte patraukti savo numerį ir apsikeitimo 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 Nagi atgal, ir mes ketina sukeisti šių dviejų. 772 00:25:15,220 --> 00:25:17,360 Ir dabar, tegul įdėti šią autopilotas. 773 00:25:17,360 --> 00:25:21,589 Aš ruošiuosi eiti ir palikti jį jums vaikinai Norėdami pasirinkti kitą smulkiausius elementus. 774 00:25:21,589 --> 00:25:22,380 Dun Dun Dun Dun. 775 00:25:22,380 --> 00:25:24,560 Taškų keturi, ką daryti? 776 00:25:24,560 --> 00:25:26,261 Puikus. 777 00:25:26,261 --> 00:25:27,760 Dabar aš ruošiuosi padaryti kitą perdavimo. 778 00:25:27,760 --> 00:25:28,590 Dun Dun Dun Dun. 779 00:25:28,590 --> 00:25:31,465 Matau penkių yra šalia mažiausias. 780 00:25:31,465 --> 00:25:32,840 Dabar aš ruošiuosi fotografuoti kitą perdavimo. 781 00:25:32,840 --> 00:25:33,631 Dun Dun Dun Dun. 782 00:25:33,631 --> 00:25:34,880 Šeši yra mažiausias. 783 00:25:34,880 --> 00:25:35,520 Geras. 784 00:25:35,520 --> 00:25:36,585 Septynios yra mažiausias. 785 00:25:36,585 --> 00:25:37,085 Jokių pokyčių. 786 00:25:37,085 --> 00:25:38,630 Aštuoni yra mažiausias. 787 00:25:38,630 --> 00:25:39,170 Atlikta. 788 00:25:39,170 --> 00:25:43,900 >> Taigi, ką mes ką tik padaryta keletą kartų pasirenkant vieną elementą po kito 789 00:25:43,900 --> 00:25:47,230 yra įgyvendinti kažką, kad mes ketina įteisinti kaip atrankos rūšiuoti. 790 00:25:47,230 --> 00:25:49,120 Ir tai gal net paprasčiau paaiškinti, 791 00:25:49,120 --> 00:25:51,310 tuo, kad tiesiog viskas, ko jums noriu padaryti, tai tiesiog laikyti 792 00:25:51,310 --> 00:25:54,700 vyksta ir atgal per sąrašą atrankos, kitą mažiausias elementas, 793 00:25:54,700 --> 00:25:55,720 kol baigsite. 794 00:25:55,720 --> 00:25:58,650 >> Taigi tai dar paprasčiau, galbūt intuityviai, nei paskutinis. 795 00:25:58,650 --> 00:26:00,020 Pabandykime vieną paskutinį vienas. 796 00:26:00,020 --> 00:26:03,060 Jei jus vaikinai gali iš naujo save į šias pozicijas 797 00:26:03,060 --> 00:26:08,600 Vienas galutinis laikas, pažiūrėkime, jei mes negalime dabar įteisinti vieną kitą požiūrį. 798 00:26:08,600 --> 00:26:12,857 Tiesą sakant, būtų kažkas ten norėčiau pasiūlyti 799 00:26:12,857 --> 00:26:14,440 kaip kitaip mes galime eiti apie tai daro? 800 00:26:14,440 --> 00:26:17,439 Be supimas iš buzzwords ar rūšiuoti atsakymų, kurie jau žinomi, 801 00:26:17,439 --> 00:26:19,689 tiesiog intuityviai, ką galėtume padaryti? 802 00:26:19,689 --> 00:26:21,635 >> Auditorija: [nesigirdi]. 803 00:26:21,635 --> 00:26:22,510 David J. Malan: Taip. 804 00:26:22,510 --> 00:26:24,620 Taigi ten puikiai intuicija ten. 805 00:26:24,620 --> 00:26:28,020 Geri dalykai atrodo, kad taip atsitiktų šiol kompiuterių mokslo, kai mes padalinti 806 00:26:28,020 --> 00:26:30,832 ir užkariauti padalinus problemą jis per pusę, o kitą pusę ir pusę. 807 00:26:30,832 --> 00:26:32,540 Ir taip iš tiesų, mes gali pradėti tai daryti. 808 00:26:32,540 --> 00:26:35,754 Ir iš tiesų, kad tai bus, mes matyti, vienas iš mūsų geriausių sprendimų dar. 809 00:26:35,754 --> 00:26:37,420 Bet tegul grįžti į, kad iki ilgai. 810 00:26:37,420 --> 00:26:40,500 Tiesą sakant, mes ketiname daryti kad šiek tiek vėliau šią savaitę. 811 00:26:40,500 --> 00:26:42,180 Ką dar gali darome išspręsti tai? 812 00:26:42,180 --> 00:26:44,647 Taigi visi čia yra atrodytų, atsitiktinė tvarka. 813 00:26:44,647 --> 00:26:45,230 Zinai ka? 814 00:26:45,230 --> 00:26:48,320 Užuot eiti pirmyn ir atgal, pirmyn ir atgal, pirmyn ir atgal, 815 00:26:48,320 --> 00:26:50,624 kiekvieną kartą, tai jaučiasi Darau daug vaikščioti. 816 00:26:50,624 --> 00:26:52,790 Kodėl ne aš tiesiog prasideda iš sąrašo pradžia, 817 00:26:52,790 --> 00:26:54,960 ir tiesiog įdėti keturis, jei ji priklauso? 818 00:26:54,960 --> 00:26:59,680 Taigi leiskite man už tą akimirką, kad Mano sąrašas tik tai pirmasis elementas. 819 00:26:59,680 --> 00:27:04,937 Yra keturių rūšiuojami šiuo momentu, jei viskas, ką aš rūpi viskas čia? 820 00:27:04,937 --> 00:27:06,520 Tai tarsi banaliai tiesa, tiesa? 821 00:27:06,520 --> 00:27:10,000 Kaip sąrašą, kuriame vieną numerį ir šis skaičius keturių akivaizdžiai rūšiuojami. 822 00:27:10,000 --> 00:27:13,070 >> Taigi leiskite man tiesiog nurodoma, kad šis sąrašas surūšiuotas. 823 00:27:13,070 --> 00:27:15,090 Bet dabar turiu šį sąrašą pailsėti. 824 00:27:15,090 --> 00:27:17,240 Taigi, dabar, aš susiduria du. 825 00:27:17,240 --> 00:27:21,690 Kur du akivaizdžiai priklauso susijusių su keturių? 826 00:27:21,690 --> 00:27:22,580 Prieš keturias. 827 00:27:22,580 --> 00:27:23,862 Taigi, ką aš galiu padaryti čia? 828 00:27:23,862 --> 00:27:24,820 Koks jūsų vardas vėl? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Juozapas. 830 00:27:25,090 --> 00:27:26,030 >> David J. Malan: Juozapas jei galėtų atsitraukti 831 00:27:26,030 --> 00:27:27,790 tik už akimirką su savo numeriu. 832 00:27:27,790 --> 00:27:31,130 Ir dabar kas turėtų Stefanas padaryti čia? 833 00:27:31,130 --> 00:27:33,720 Leiskite pereiti Stefan čia. 834 00:27:33,720 --> 00:27:35,520 Ir dabar, tegul Juozapas atėjo čia. 835 00:27:35,520 --> 00:27:39,660 O dabar leiskite man teigti, kad Viskas čia yra rūšiuojami. 836 00:27:39,660 --> 00:27:42,474 Taigi, panašus rezultatas, bet iš esmės skiriasi požiūris. 837 00:27:42,474 --> 00:27:44,140 Aš net mačiau, kas ten. 838 00:27:44,140 --> 00:27:46,310 Aš tiesiog gertumėte elementai kaip jie įteikė man 839 00:27:46,310 --> 00:27:47,240 ir su jais susidoroti. 840 00:27:47,240 --> 00:27:48,330 >> Taigi dabar, matau skaičių šeši. 841 00:27:48,330 --> 00:27:51,110 Kur numeris šešių priklauso? 842 00:27:51,110 --> 00:27:53,250 Mes turime du, keturi, šeši. 843 00:27:53,250 --> 00:27:54,800 Tiksliai ten, kur ji yra dabar. 844 00:27:54,800 --> 00:27:57,750 Taigi palikime, kad vieni, ir dabar teigia, kad šio sąrašo dalis 845 00:27:57,750 --> 00:27:58,772 dabar rūšiuojami. 846 00:27:58,772 --> 00:28:01,230 Ir taip, tai jaučiasi iš esmės skiriasi tuo, kad aš tiesiog 847 00:28:01,230 --> 00:28:05,230 juda per sąrašą čia tiesiškai, ir aš niekada dvigubai atgal. 848 00:28:05,230 --> 00:28:05,730 Taip. 849 00:28:05,730 --> 00:28:06,230 Gerai. 850 00:28:06,230 --> 00:28:08,190 Taigi aštuoni, kur jūs priklausote? 851 00:28:08,190 --> 00:28:08,730 Štai čia. 852 00:28:08,730 --> 00:28:09,310 Tobula. 853 00:28:09,310 --> 00:28:10,210 Taigi dabar, vienas. 854 00:28:10,210 --> 00:28:10,900 Uh Oh. 855 00:28:10,900 --> 00:28:13,010 Tai jaučiasi tai bus brangus. 856 00:28:13,010 --> 00:28:15,690 Dabar, ankstesnį algoritmas, Aš tiesiog pavertė žmones. 857 00:28:15,690 --> 00:28:18,648 Taigi galiu įdėti jį visą kelią ne pradžioje, tačiau vėliau persikėlė Juozapą. 858 00:28:18,648 --> 00:28:21,450 Bet jei aš judėti Juozapą, dabar kas bus negerai? 859 00:28:21,450 --> 00:28:24,250 >> Dabar, aš tarsi undone-- aš imtasi vieną žingsnį į priekį ir tada 860 00:28:24,250 --> 00:28:26,300 vienas žingsnis atgal, nes dabar Juozapas būtų iš eilės. 861 00:28:26,300 --> 00:28:26,830 Taigi leiskite tai padaryti. 862 00:28:26,830 --> 00:28:29,150 Jei galėtų imtis numeris vienas ir žingsnis atgal tik akimirką. 863 00:28:29,150 --> 00:28:30,490 Kaip mes galime put-- ką buvo jūsų vardas vėl? 864 00:28:30,490 --> 00:28:31,130 >> Ananas: Annanas. 865 00:28:31,130 --> 00:28:32,610 >> David J. Malan: Ananas vietoje? 866 00:28:32,610 --> 00:28:36,091 Kas turi įvykti, atsižvelgiant į dviejų, keturių, šešių, o aštuonių? 867 00:28:36,091 --> 00:28:37,570 Jie visi turime pereiti. 868 00:28:37,570 --> 00:28:42,590 Taigi, jei aštuoni norėtų pereiti pirma, tada šešių, tada keturių, tada du. 869 00:28:42,590 --> 00:28:45,380 Ir tada Annanas, jei norite patinka ateiti čia gera. 870 00:28:45,380 --> 00:28:47,760 Bet čia mes ką tik rūšies sumokėjo kainą 871 00:28:47,760 --> 00:28:49,510 skirtingu taško algoritmą. 872 00:28:49,510 --> 00:28:52,550 Kadangi paskutinį kartą su atrankos Rūšiuoti, ir net burbulas rūšiuoti, 873 00:28:52,550 --> 00:28:54,700 Aš einu atgal ir pirmyn, pirmyn ir atgal, 874 00:28:54,700 --> 00:28:58,360 kuri yra tikrai sudėjus laiko atžvilgiu, ir tiesiog palaipsniui. 875 00:28:58,360 --> 00:29:00,660 >> Įterpimas rūšiuoti, iš pradžių žvilgsnis, atrodo, kad jis yra 876 00:29:00,660 --> 00:29:05,150 Super protingesni, nes aš tiesiog priėmimo lėtai ir laipsnišką pažangą, 877 00:29:05,150 --> 00:29:07,120 bet aš nesiruošia tai pirmyn ir atgal. 878 00:29:07,120 --> 00:29:09,410 Bet jei kas nors iš tiesų yra iš eilės, pranešimu 879 00:29:09,410 --> 00:29:10,840 visus darbus aš tiesiog turėjo tai padaryti. 880 00:29:10,840 --> 00:29:14,750 Aš turėjo judėti pusė sąrašo tiesiog padaryti kambarį numeris vienas. 881 00:29:14,750 --> 00:29:16,790 Taigi, tai ta pati suma Darbo šiol ją 882 00:29:16,790 --> 00:29:18,690 jaučiasi, tik skirtingo tipo darbo. 883 00:29:18,690 --> 00:29:19,370 >> Leiskite tęsti. 884 00:29:19,370 --> 00:29:22,657 Taigi, dabar mes žinome, kad kiekvienas tarp vieno ir aštuonių rūšiuojami. 885 00:29:22,657 --> 00:29:23,740 Čia turiu numeris trys. 886 00:29:23,740 --> 00:29:25,864 Jei jums patinka pasiimti numeris trys, žingsnis atgal vieną. 887 00:29:25,864 --> 00:29:28,260 Ir ką jūs vaikinai reikia daryti? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Štai dar vienas, du, trys žingsniai. 890 00:29:33,070 --> 00:29:36,010 Trys laiko vienetais, kurie tiesiog kainuoti me, todėl, kad trys dabar gali tilptų. 891 00:29:36,010 --> 00:29:37,460 Galiausiai, septyni. 892 00:29:37,460 --> 00:29:39,730 >> Vykime į priekį ir turi Jums žengti žingsnį atgal. 893 00:29:39,730 --> 00:29:42,780 Tai tik ketina kainavo mums vienas vienetas metu, bet viskas OK. 894 00:29:42,780 --> 00:29:44,170 Ir dabar, penkių ketina būti šiek tiek daugiau brangi. 895 00:29:44,170 --> 00:29:45,340 Jei norite atsitraukti. 896 00:29:45,340 --> 00:29:48,380 Turime judėti aštuoni, septyni, o šeši. 897 00:29:48,380 --> 00:29:50,749 Ir tada visi dabar rūšiuojami. 898 00:29:50,749 --> 00:29:52,290 Taigi didelis ranka mūsų savanoriai čia. 899 00:29:52,290 --> 00:29:53,554 Labai ačiū. 900 00:29:53,554 --> 00:29:56,220 >> [Plojimai] 901 00:29:56,220 --> 00:29:56,860 >> Ačiū jums visiems. 902 00:29:56,860 --> 00:29:57,520 Ačiū jums visiems. 903 00:29:57,520 --> 00:30:02,940 Taigi pažiūrėkime, dabar tik kaip brangu visa tai buvo. 904 00:30:02,940 --> 00:30:06,210 Apsvarstykite, ko gero, Paprasčiausias iš jų, burbulas rūšiuoti. 905 00:30:06,210 --> 00:30:09,950 Ir aš sakau, paprasčiausias, tik dėl to, galite ją išspręsti godžiai tiesiog 906 00:30:09,950 --> 00:30:11,660 nustatyti Porinis problema čia. 907 00:30:11,660 --> 00:30:13,720 Pritvirtinkite Porinis problemą čia vėl ir vėl 908 00:30:13,720 --> 00:30:17,680 ir vėl, kartojant, nes daugelis kartų, kiek iš tikrųjų reikia. 909 00:30:17,680 --> 00:30:21,050 >> Taigi, tai Pasirodo, kad su burbulas rūšiuoti, gerai, 910 00:30:21,050 --> 00:30:25,820 kiek žingsnių turiu imtis pirmasis perdavimas šio algoritmo? 911 00:30:25,820 --> 00:30:30,850 Galėčiau take-- tegul see-- vieną, dviejų, trijų, keturių, penkių, šešių, septynių. 912 00:30:30,850 --> 00:30:32,190 Ir ten aštuonis elementus čia. 913 00:30:32,190 --> 00:30:35,280 Taigi, tai, kaip n atėmus 1 žingsnių gauti iš sąrašo pradžioje 914 00:30:35,280 --> 00:30:36,380 į sąrašo pabaigoje. 915 00:30:36,380 --> 00:30:41,350 >> Bet su atrankos rūšiuoti, priminti, kad aš vėl ir vėl pasirinkdami elementus 916 00:30:41,350 --> 00:30:44,590 ir vėl, kad mažiausias, Aš pradėti jį į vietą, 917 00:30:44,590 --> 00:30:46,616 bet tada aš nesu ieško už manęs dar kartą. 918 00:30:46,616 --> 00:30:49,490 Taigi, aš manau, kad tai šiek tiek daugiau aišku tada, kad pirmą kartą, galiu 919 00:30:49,490 --> 00:30:52,680 turi imtis visų n minuso veiksmus nuo 1 rasti mažiausią elementą. 920 00:30:52,680 --> 00:30:55,920 Tada aš įdėti juos į vietą, ir aš iškeldinti kas čia buvo anksčiau. 921 00:30:55,920 --> 00:30:57,500 >> Bet tada aš neturiu nuolat ieško šio elemento, 922 00:30:57,500 --> 00:30:59,040 nes aš žinau, tai jau mažiausias. 923 00:30:59,040 --> 00:31:01,581 Taigi, dabar, aš galiu pažvelgti tik septyni elementai, tada šeši elementai, 924 00:31:01,581 --> 00:31:03,290 tada penki elementai, tada keturi elementai. 925 00:31:03,290 --> 00:31:06,900 Ir taip matematiškai, jei n yra iš elementų ar numerių 926 00:31:06,900 --> 00:31:11,990 kad mes pradėjome, galite įsivaizduoti, , kad tai yra tas pats, kaip n minus 1, 927 00:31:11,990 --> 00:31:14,250 plius n ± 2 žingsniai, plius n atėmus 3 žingsniai, 928 00:31:14,250 --> 00:31:16,780 plius n minus 4 žingsniai, visi kelią žemyn tik vienas žingsnis. 929 00:31:16,780 --> 00:31:18,160 Ir aš tikiu, mano paskutinis žmogus. 930 00:31:18,160 --> 00:31:20,650 >> Ir jei jūs prisimenate, kad daug nuo statistika knygas ar matematikos knygas 931 00:31:20,650 --> 00:31:24,730 turi tas formules ant Kieti atgal arba priešais juos, 932 00:31:24,730 --> 00:31:27,690 paaiškėja, kad šios serijos gali būti išreikštas daugiau tiesiog 933 00:31:27,690 --> 00:31:28,857 N kartų n atėmus 1 per 2. 934 00:31:28,857 --> 00:31:31,273 Ir tai gerai, jei tai ne ne savo proto priešakyje. 935 00:31:31,273 --> 00:31:32,420 Bet tai tiesa. 936 00:31:32,420 --> 00:31:34,449 Tai tiesiog paprastesnis būdas jį raštu. 937 00:31:34,449 --> 00:31:36,240 Ir tada, jei jūs manote Atgal į pradinėje mokykloje, 938 00:31:36,240 --> 00:31:38,698 kai jūs tiesiog pradėkite dauginant dalykų, ši žinoma, 939 00:31:38,698 --> 00:31:41,820 tiesiog n kvadrato atėmus n padalytą iš 2. 940 00:31:41,820 --> 00:31:44,772 Viskas, ką aš padariau yra išplėsti pasakymai ten. 941 00:31:44,772 --> 00:31:46,730 Ir todėl galime perrašyti šio šiek tiek kitaip. 942 00:31:46,730 --> 00:31:49,780 Štai N kvadratėliais padalintas 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Taigi dar kartą, aš tiesiog rūšies taikymo kai aritmetinis ten taisykles. 944 00:31:53,270 --> 00:31:57,140 Tačiau pastebėti, kad dabar didžiausias terminas Šioje išraiška, taip sakant, 945 00:31:57,140 --> 00:31:58,540 yra tai, kad n kvadrato. 946 00:31:58,540 --> 00:32:02,910 Ir taip, tai n kvadratu padalytą iš 2, atėmus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Tačiau paprastai, jei n yra bus didelis vertė, 948 00:32:05,080 --> 00:32:08,740 Aš ruošiuosi teigia, kad n kvadratu bus dominuojantis veiksnys. 949 00:32:08,740 --> 00:32:10,490 Tai tiesiog bus didesnis indėlis 950 00:32:10,490 --> 00:32:12,877 į žingsnius nei N / 2 numeriu. 951 00:32:12,877 --> 00:32:13,960 Taigi, ką aš turiu galvoje tai? 952 00:32:13,960 --> 00:32:16,795 Pabandykime paprastą pavyzdį, net nors matematikos gauna šiek tiek didelis. 953 00:32:16,795 --> 00:32:20,210 >> Taigi tarkime, mes turėjome 1 milijonas žmonių scenoje, arba 1 mln dalykų 954 00:32:20,210 --> 00:32:21,320 kad mes norime rūšiuoti. 955 00:32:21,320 --> 00:32:23,730 Leiskite prijungti mln į lygiai tą formulę 956 00:32:23,730 --> 00:32:27,230 pamatyti, kiek žingsnių užtrunka viso rūšiuoti milijoną elementus naudojant tarkim, 957 00:32:27,230 --> 00:32:28,560 pasirinkimas rūšiuoti. 958 00:32:28,560 --> 00:32:30,760 >> Taigi, mes norime turėti tą pačią formulę kaip ir anksčiau. 959 00:32:30,760 --> 00:32:34,120 Aš prijunkite milijono, kad gaunu milijono kvadratėliais padalintas iš 2, 960 00:32:34,120 --> 00:32:35,990 minus mln padalytą iš 2. 961 00:32:35,990 --> 00:32:40,180 Jei aš padaryti, kad matematikos anksto čia mes turime 500 mlrd 962 00:32:40,180 --> 00:32:47,460 atėmus 500000, kuris suteikia mums 499999500000, 963 00:32:47,460 --> 00:32:49,270 kuris yra pretty darn didelis. 964 00:32:49,270 --> 00:32:54,370 >> Iš tiesų, jei jūs palyginkite dabar 499000000000 999 milijonų eurų, 965 00:32:54,370 --> 00:33:01,210 500.000 prieš mūsų pradinės vertės, 500 milijardų, tai taip velniškai arti. 966 00:33:01,210 --> 00:33:06,850 Teisė? N kvadratėliais padalintas 2 suteikia us-- ar veikiau, N kvadratėliais padalintas iš 2 967 00:33:06,850 --> 00:33:08,370 davė mums 500 mlrd. 968 00:33:08,370 --> 00:33:13,510 Štai pretty darn Uždaryti į 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 kuri yra pasakyti atimant nuo 500,000, arba apskritai, atimant išjungtas 970 00:33:17,970 --> 00:33:20,010 n kvadratu, tikrai ne big deal. 971 00:33:20,010 --> 00:33:22,490 Pagal "n kvadratu daro šias numeriai auga tikrai greitai. 972 00:33:22,490 --> 00:33:25,790 >> Dabar, tai yra svarbus tik tiek, kaip mes, kompiuterių specialistų, 973 00:33:25,790 --> 00:33:29,350 paprastai nesiruošia taip rūpinatės apie šių formulių niuansų 974 00:33:29,350 --> 00:33:31,400 ir būtent tai, ką Tikslios atsakymai. 975 00:33:31,400 --> 00:33:33,390 Mes rūpinamės tik, kad jūs žinote, ką? 976 00:33:33,390 --> 00:33:37,810 Tuo dienos pabaigos, ši formulė yra ant tam, n kvadrato. 977 00:33:37,810 --> 00:33:39,350 >> Taip, mes padalinus iš 2 ten. 978 00:33:39,350 --> 00:33:41,360 Taip, mes atimant išjungta n ± 2. 979 00:33:41,360 --> 00:33:46,860 Bet dienos pabaigoje, terminas kad tikrai skauda su mumis ir mums kainuoja 980 00:33:46,860 --> 00:33:48,995 žingsnių daug yra tai, kad kvadrato sąvoka. 981 00:33:48,995 --> 00:33:51,370 Ir taip, ko kompiuterių mokslininkas ketina paprastai padaryti 982 00:33:51,370 --> 00:33:54,160 yra ignoruoti visus tuos mažesni pavedimo sąlygas, 983 00:33:54,160 --> 00:33:56,900 ir tik pažvelgti į vieną, kad prisideda į sąnaudas labiausiai. 984 00:33:56,900 --> 00:34:00,530 >> Ir tai yra gražus, nes mes galime dabar kalbėti daug daugiau bendrumo 985 00:34:00,530 --> 00:34:02,470 apie algoritmų, ir gali juos palyginti. 986 00:34:02,470 --> 00:34:04,550 Ir tai, kad aš Naudojant šią O yra sąmoningas. 987 00:34:04,550 --> 00:34:06,680 Kai aš sakau, pagal užsakymą apie, aš specialiai 988 00:34:06,680 --> 00:34:09,560 nuoroda į kažką vadinamas didelis O. didelis O 989 00:34:09,560 --> 00:34:14,090 yra notacija, kad kompiuteris mokslininkas naudoja apibūdinti 990 00:34:14,090 --> 00:34:16,710 viršutinė riba kažką. 991 00:34:16,710 --> 00:34:21,150 >> Taigi, jei jūs sakote, kad algoritmas yra didelis O n kvadratu, 992 00:34:21,150 --> 00:34:23,380 kaip aš pasiūliau tik akimirka prieš tai reiškia, kad 993 00:34:23,380 --> 00:34:27,710 kad, kalbant apie jos veikia laikas arba jo efektyvumas, 994 00:34:27,710 --> 00:34:30,090 jis įgauna tam n kvadrato žingsnius. 995 00:34:30,090 --> 00:34:31,420 Gal daugiau, gal mažiau. 996 00:34:31,420 --> 00:34:33,435 Bet tai ant n Kad kvadrato. 997 00:34:33,435 --> 00:34:34,560 Ir tai viršutinė riba. 998 00:34:34,560 --> 00:34:36,530 Jis nesiruošia būti labiau skausminga, nei nurodyta. 999 00:34:36,530 --> 00:34:40,800 Jis nesiruošia būti n kubeliais, arba 2 į N, ar kažkas daug daugiau. 1000 00:34:40,800 --> 00:34:43,800 Tai viršutinė riba ant kokio kad kaina yra. 1001 00:34:43,800 --> 00:34:46,150 Taigi atsižvelgiant į tai, tegul mano tik keletą pavyzdžių. 1002 00:34:46,150 --> 00:34:49,820 Ir tai tik baigtinis sąrašas labai dažni bėgimo kartų 1003 00:34:49,820 --> 00:34:52,870 algoritmai, kurie reiškia būti iliustruoja kai kurių dalykų mes 1004 00:34:52,870 --> 00:34:53,600 matyti jau. 1005 00:34:53,600 --> 00:34:58,060 >> Taigi, pavyzdžiui, tokiais atvejais, kai pasirinkimas rūšiuoti, ką aš teigdamas čia 1006 00:34:58,060 --> 00:35:02,250 yra, kad atrankos Rūšiuoti bėga laikas yra ant n siekiant kvadrato. 1007 00:35:02,250 --> 00:35:06,260 Blogiausiu atveju, aš ruošiuosi visa krūva atsitiktinių skaičių čia. 1008 00:35:06,260 --> 00:35:08,600 Ir kaip mes matėme matematiškai, jei aš nuolat vaikščioti 1009 00:35:08,600 --> 00:35:11,310 per sąrašą, per sąrašas, pasirinkdami kitą mažiausias 1010 00:35:11,310 --> 00:35:14,410 elementas vėl ir vėl, jei aš iš tikrųjų užsirašyti visus veiksmus, 1011 00:35:14,410 --> 00:35:18,750 Aš atsižvelgiant, kaip aš formulaically pasiūlė anksčiau, tai nuo n kvadratu tam 1012 00:35:18,750 --> 00:35:20,370 žingsnių, kad aš vartojate. 1013 00:35:20,370 --> 00:35:24,520 >> Ir paaiškėja, kad burbulas rūšiuoti bei įterpimo Rūšiuoti 1014 00:35:24,520 --> 00:35:27,370 yra lygiai taip pat lėtai, blogiausiu atveju. 1015 00:35:27,370 --> 00:35:32,040 Apsvarstykite, pavyzdžiui, įterpiant rūšiuoti, labai paskutinis algoritmas mes nagrinėjami, 1016 00:35:32,040 --> 00:35:35,500 kuri turėjo mums pažvelgti į elementą, ir įdėkite jį ten, kur jis priklauso. 1017 00:35:35,500 --> 00:35:38,720 Ir tada mes pažvelgė į kito elemento, ir įterpiamas jį ten, kur jis priklauso. 1018 00:35:38,720 --> 00:35:40,990 >> Taigi mano geriausią įmanomą scenarijų. 1019 00:35:40,990 --> 00:35:45,590 Tarkime, aš turėjau savanoriai išsirikiuoti pažodžiui, kaip šis, vienas per aštuonių, 1020 00:35:45,590 --> 00:35:47,440 jau rūšiuojamos. 1021 00:35:47,440 --> 00:35:51,300 Kiek žingsnių yra įterpimo Rūšiuoti ketina imtis rūšiuoti aštuoni žmonės, 1022 00:35:51,300 --> 00:35:55,640 jei jie atvyksta į sceną ieško patinka tai? 1023 00:35:55,640 --> 00:35:57,410 >> Aštuoni žmonės jau rūšiuojamos. 1024 00:35:57,410 --> 00:35:58,760 Ir aš naudoju įterpimo rūšiuoti. 1025 00:35:58,760 --> 00:36:02,180 Tai paskutinis iš algoritmai. 1026 00:36:02,180 --> 00:36:03,640 Na, tegul Kartoti labai greitai. 1027 00:36:03,640 --> 00:36:05,504 Taigi, jei aš pradedu čia matau vieną. 1028 00:36:05,504 --> 00:36:06,420 Kur vienas priklauso? 1029 00:36:06,420 --> 00:36:07,730 Jis priklauso čia. 1030 00:36:07,730 --> 00:36:08,330 Matau du. 1031 00:36:08,330 --> 00:36:09,660 Kur du priklauso? 1032 00:36:09,660 --> 00:36:10,260 Štai čia. 1033 00:36:10,260 --> 00:36:10,900 Matau tris. 1034 00:36:10,900 --> 00:36:11,920 Kur trys priklauso? 1035 00:36:11,920 --> 00:36:12,480 Štai čia. 1036 00:36:12,480 --> 00:36:13,100 >> "Aš matau keturis. 1037 00:36:13,100 --> 00:36:13,600 Štai čia. 1038 00:36:13,600 --> 00:36:15,660 Penki, šeši, septyni, aštuoni. 1039 00:36:15,660 --> 00:36:17,320 Nėra jokios priežasties, kad pasikartosiu. 1040 00:36:17,320 --> 00:36:21,260 Ir taip, kiek žingsnių yra tai, kad, kalbant apie n? 1041 00:36:21,260 --> 00:36:23,870 Tai ant n tvarka žingsniai, tiesa? n atėmus 1. 1042 00:36:23,870 --> 00:36:27,567 Bet aš paėmė linijinis skaičių žingsnių, ir dabar aš padaryti. 1043 00:36:27,567 --> 00:36:28,900 Taigi, kad geriausiu atveju, nors. 1044 00:36:28,900 --> 00:36:29,983 Ką apie blogiausiu atveju? 1045 00:36:29,983 --> 00:36:32,730 Kas aštuoni buvo ten, o septyni buvo ten, 1046 00:36:32,730 --> 00:36:35,840 ir vienas ir du buvo per čia, todėl kad šis sąrašas buvo tikrai pasikeitė? 1047 00:36:35,840 --> 00:36:38,300 >> Na, kas atsitinka iš tikrųjų jei tai yra numeris? 1048 00:36:38,300 --> 00:36:41,300 Ir mes padarysime tik keletą pavyzdžių. 1049 00:36:41,300 --> 00:36:49,300 Ką daryti, jei, žinoma, numeris aštuoni yra čia ir number-- šūksniais. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Taigi ką daryti, jei iš tiesų, skaičius aštuonių yra visą kelią per čia 1052 00:36:56,430 --> 00:36:57,790 ir aš naudoju įterpimo rūšiuoti? 1053 00:36:57,790 --> 00:36:58,290 >> GERAI. 1054 00:36:58,290 --> 00:37:00,280 Aš teigia šiuo metu jis yra vietoje. 1055 00:37:00,280 --> 00:37:03,152 Bet dabar, seven-- kur nėra septynių eiti? 1056 00:37:03,152 --> 00:37:04,360 Žinoma, jis eina čia. 1057 00:37:04,360 --> 00:37:06,760 Taigi turiu judėti aštuoni per vieną vietą. 1058 00:37:06,760 --> 00:37:08,554 Dabar šešių, kur ji eiti? 1059 00:37:08,554 --> 00:37:09,220 Na, viskas gerai. 1060 00:37:09,220 --> 00:37:13,150 Dabar, aš turiu judėti aštuoni per vieta, o septyni per vietą, 1061 00:37:13,150 --> 00:37:14,440 ir tada aš pop žemyn šeši. 1062 00:37:14,440 --> 00:37:16,870 >> Taigi, pirmą kartą, ji išlaidų man vienas žingsnis siekiant nustatyti dalykus, 1063 00:37:16,870 --> 00:37:18,570 tada jis man kainavo du žingsnius nustatyti dalykus. 1064 00:37:18,570 --> 00:37:20,370 Kiek žingsnių tai ketina imtis nustatyti 1065 00:37:20,370 --> 00:37:22,720 dalykų, kuriuos reikia sudėti penkias reikiamoje vietoje? 1066 00:37:22,720 --> 00:37:23,340 Trys. 1067 00:37:23,340 --> 00:37:29,520 Kadangi dabar turiu judėti vienas, du, trys. 1068 00:37:29,520 --> 00:37:32,430 Kiek žingsnių ji ketina imtis įdėti keturi reikiamoje vietoje? 1069 00:37:32,430 --> 00:37:36,040 4 plius 5, plius 6, plius 7. 1070 00:37:36,040 --> 00:37:40,260 >> Ir todėl matematiškai identiška ką mes aprašyta atrankos rūšiuoti. 1071 00:37:40,260 --> 00:37:42,130 Mes turime šią seriją tai tik didėja. 1072 00:37:42,130 --> 00:37:45,650 1 plius 2 plius 3 plius 4, arba atvirkščiai, 7 plius 6 1073 00:37:45,650 --> 00:37:52,610 plius 5 plius 4 išauga iki šiandienos tikslais ant n Kad kvadrato. 1074 00:37:52,610 --> 00:37:57,640 >> Taigi leiskite man nurodoma, kad per burbulas rūšiuoti taip pat n kvadratu. 1075 00:37:57,640 --> 00:38:01,340 Kadangi su burbulas rūšiuoti, kiekvieno kartą aš einu per sąrašą, 1076 00:38:01,340 --> 00:38:03,100 Aš atsižvelgiant maždaug kiek žingsnių? 1077 00:38:03,100 --> 00:38:06,260 Kiekvieną kartą, kai aš tiesiog vaikščioti iš ten į ten? 1078 00:38:06,260 --> 00:38:07,960 Maždaug n žingsnių. 1079 00:38:07,960 --> 00:38:12,650 Bet kiek kartų galėčiau reikia eiti per sąrašą? 1080 00:38:12,650 --> 00:38:13,920 >> Na, maždaug n laiko. 1081 00:38:13,920 --> 00:38:15,680 Gal n atėmus 1, tačiau maždaug n kartų. 1082 00:38:15,680 --> 00:38:16,430 Na, kodėl taip yra? 1083 00:38:16,430 --> 00:38:19,560 Na, su burbulas rūšiuoti, jei mes pradėti su burbulas rūšiuoti, 1084 00:38:19,560 --> 00:38:23,570 su blogiausiu įmanoma sąrašą situacija, kuri vėl yra visiškai 1085 00:38:23,570 --> 00:38:25,550 atgal, kas nutiks? 1086 00:38:25,550 --> 00:38:28,830 Aš einu per sąrašą, ir numeris vienas priklauso visą kelią ten. 1087 00:38:28,830 --> 00:38:33,280 >> Bet su burbulas rūšiuoti, kiek daro vieną perkelti ant mano pirmojo prasiskverbimo per sąrašą? 1088 00:38:33,280 --> 00:38:36,620 Kiek taškų jis prieina arčiau teisingoje vietoje? 1089 00:38:36,620 --> 00:38:37,240 Tik vienas. 1090 00:38:37,240 --> 00:38:40,281 Taigi, jei jūs rūšies priežastis per tai, kiekvieną kartą, per šį algoritmą, 1091 00:38:40,281 --> 00:38:41,880 Dovydo atsižvelgiant maždaug n žingsnių. 1092 00:38:41,880 --> 00:38:44,940 Bet kiek eina Sąraše yra ją 1093 00:38:44,940 --> 00:38:49,060 ketina imtis vienas burbulas į kairę, kur jis priklauso? 1094 00:38:49,060 --> 00:38:51,840 >> Kamuolys atšoko judėti kaip, n erdves šiuo būdu. 1095 00:38:51,840 --> 00:38:57,960 Taigi tiesiog padaryti rūšiavimą sąrašo, Turiu vaikščioti pirmyn ir atgal n kartų. 1096 00:38:57,960 --> 00:39:01,540 Ir kiekvieną kartą, aš žiūri n elementų. 1097 00:39:01,540 --> 00:39:05,410 Taigi, tai n dalykų n kartų iš n Kad kvadrato. 1098 00:39:05,410 --> 00:39:07,220 >> Dabar mes pamatysime kai iš šortai 1099 00:39:07,220 --> 00:39:10,440 yra įdėta į CS50 naujos problemos nustatyti, kitą metodą ne tai, 1100 00:39:10,440 --> 00:39:13,490 Bet dabar, tegul tiesiog apsvarstyti kai kurių kitų bėgimo kartų, 1101 00:39:13,490 --> 00:39:16,840 ypač jei rūšiavimo tie imtis šiek tiek laiko, kad kriaukle. 1102 00:39:16,840 --> 00:39:21,790 Kas yra algoritmas mes matėme jau kad įgauna n žingsnių tam,? 1103 00:39:21,790 --> 00:39:27,560 >> Kas turėtų imtis linijinis skaičių žingsnių, kad mes matėme iki šiol? 1104 00:39:27,560 --> 00:39:29,350 Kas tai? 1105 00:39:29,350 --> 00:39:30,480 Telefonas katalogas paiešką. 1106 00:39:30,480 --> 00:39:31,390 Pirmasis algoritmas. 1107 00:39:31,390 --> 00:39:31,560 Teisė? 1108 00:39:31,560 --> 00:39:33,650 Kur mes tiesiškai ieškoti Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Išties. 1110 00:39:34,150 --> 00:39:37,180 Nuo nulio savaitę, kai aš pradėjau sukant vieną lapą vienu metu, 1111 00:39:37,180 --> 00:39:40,095 ir aš net sakė, kad jis buvo natūra linijinio jausmas algoritmas, 1112 00:39:40,095 --> 00:39:42,720 ir mes turėjome tą nuotrauką ant lenta su tiesiu raudona linija 1113 00:39:42,720 --> 00:39:44,678 ir tiesiai geltona linija, tai buvo iš tiesų 1114 00:39:44,678 --> 00:39:46,810 algoritmai, kurie yra didelis O n. 1115 00:39:46,810 --> 00:39:50,680 >> Kadangi rasti Mike Smith telefoną knyga n puslapių, blogiausiu atveju, 1116 00:39:50,680 --> 00:39:52,422 gali pasiimti mane n veiksmus. 1117 00:39:52,422 --> 00:39:53,630 Ką apie vartojate lankomumą? 1118 00:39:53,630 --> 00:39:55,790 Vienas du trys Keturi Penki Šeši. 1119 00:39:55,790 --> 00:39:59,420 Koks veikimo laikas apie tai algoritmas, atsižvelgiant lankomumą? 1120 00:39:59,420 --> 00:40:03,070 Didelės O n, nes teoriškai aš turi atkreipti visus į kambarį. 1121 00:40:03,070 --> 00:40:05,861 >> Dabar, kaip panaikinti, ką apie kita optimizavimas nuo nulinio savaitę? 1122 00:40:05,861 --> 00:40:08,117 Dviejų, keturių, šešių, aštuonių, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Kompiuterių mokslininkas būtų suvokti, palauk, 1124 00:40:10,200 --> 00:40:12,320 tai remiantis tam N, padalytą iš dviejų etapų. 1125 00:40:12,320 --> 00:40:12,820 Teisė? 1126 00:40:12,820 --> 00:40:14,444 Nes aš darau du žmones vienu metu. 1127 00:40:14,444 --> 00:40:17,015 Tačiau mes ketiname ignoruoti Šios žemesnės pavedimo sąlygas, 1128 00:40:17,015 --> 00:40:19,140 ir mes tik ketina išmesti padalinti iš 2, 1129 00:40:19,140 --> 00:40:21,830 ir tiesiog pasakyti, didelis O n už šio algoritmo taip pat. 1130 00:40:21,830 --> 00:40:22,760 >> Ką manai apie šį? 1131 00:40:22,760 --> 00:40:26,170 Mes praleisti kai kurie iš jų, bet ką buvo algoritmas, kuris buvo žurnalo n? 1132 00:40:26,170 --> 00:40:29,900 Tam prireikė maždaug log n veiksmus? 1133 00:40:29,900 --> 00:40:30,870 Skaldyk ir valdyk. 1134 00:40:30,870 --> 00:40:31,369 Būtent. 1135 00:40:31,369 --> 00:40:33,900 Patinka telefonų knygos pavyzdžiui, nulis savaitę ir anksčiau šiandien, 1136 00:40:33,900 --> 00:40:36,191 kur mes suskirstyti problemą vėl ir vėl ir vėl. 1137 00:40:36,191 --> 00:40:39,070 Mes išsitraukė jį ant lentos į savaitę nulis kaip lenkta žalia linija, 1138 00:40:39,070 --> 00:40:41,460 ir sakėme, kad diena buvo logaritminis algoritmas. 1139 00:40:41,460 --> 00:40:44,970 >> Ir iš tiesų, numerių veiksmus, kurių ji mano, kad atlikti skaldyk ir valdyk, 1140 00:40:44,970 --> 00:40:48,610 arba dvejetainis paiešką kaip mes pradėsime vadindami jį, kaip į telefonų knygą, 1141 00:40:48,610 --> 00:40:50,680 yra ant log ir priemones, tvarka. 1142 00:40:50,680 --> 00:40:52,470 Ir tai yra keistai vienas bitas. 1143 00:40:52,470 --> 00:40:54,910 >> Kas užima vieną žingsnį, arba, konkrečiau 1144 00:40:54,910 --> 00:40:56,240 pastovus pakopų skaičius? 1145 00:40:56,240 --> 00:40:58,865 Gal tai dvi, o gal tai trys, bet kompiuteris mokslininkas tiesiog 1146 00:40:58,865 --> 00:41:01,423 supaprastina jį kaip didelis O 1, kai nuolatinis pakopų skaičius. 1147 00:41:01,423 --> 00:41:04,256 Kas ką galite padaryti, kad mano pastovų skaičių žingsnių? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Koks veikimo laikas plojimai? 1150 00:41:10,930 --> 00:41:11,920 Pastovus laikas. 1151 00:41:11,920 --> 00:41:12,420 Teisė? 1152 00:41:12,420 --> 00:41:15,490 Kaip, kas yra veikimo laikas daro viską, kad turėjo tik vieną 1153 00:41:15,490 --> 00:41:18,570 operacija, kaip spausdinti F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Tai gali būti laikomas pastovus laikas, nebent mažiau kampe atveju su spausdinimo F, 1155 00:41:24,110 --> 00:41:28,260 kas gali veikimo laiką Spausdinimo F tikrųjų? 1156 00:41:28,260 --> 00:41:28,790 Ir kodėl? 1157 00:41:28,790 --> 00:41:30,550 Tai, kas yra n matavimo tuo atveju? 1158 00:41:30,550 --> 00:41:32,251 >> Auditorija: [nesigirdi]. 1159 00:41:32,251 --> 00:41:33,250 David J. Malan: Būtent. 1160 00:41:33,250 --> 00:41:34,900 Simbolių skaičių mes norime spausdinti. 1161 00:41:34,900 --> 00:41:36,191 Taigi tai labai konteksto. 1162 00:41:36,191 --> 00:41:39,910 Šiandien mes jau dėmesio daug apie raidės ir skaičiai čia ant lentos. 1163 00:41:39,910 --> 00:41:43,540 Tačiau ji taip pat gali būti simbolių faktinė eilutę. 1164 00:41:43,540 --> 00:41:46,420 Taigi paaiškėja, yra dar vienas priemonė, kuri pradės rūpintis, 1165 00:41:46,420 --> 00:41:48,530 ir tai yra priešinga stambaus O, taip sakant. 1166 00:41:48,530 --> 00:41:50,120 >> Štai Omega notacija. 1167 00:41:50,120 --> 00:41:53,380 Kadangi didelis O tai kas, The viršutinė riba nuo jūsų važiavimo laikas? 1168 00:41:53,380 --> 00:41:55,580 Maksimaliai, kiek laiko gali kas nors imtis? 1169 00:41:55,580 --> 00:41:59,250 Omega-- Atsiprašome Tai apsaugo ateina up-- yra, kad priešais, 1170 00:41:59,250 --> 00:42:02,960 kuriuo tai apatinė riba laiką kažkas gali imtis. 1171 00:42:02,960 --> 00:42:10,480 >> So. Pavyzdžiui, kas yra algoritmas kad mano visada n kvadratu veiksmus? 1172 00:42:10,480 --> 00:42:15,600 Na, vienas iš algoritmų mes matėme šiandien, iš tikrųjų, gali būti, kad taip pat. 1173 00:42:15,600 --> 00:42:16,720 Atrankos rūšiuoti. 1174 00:42:16,720 --> 00:42:18,270 Atrankos Rūšiuoti gana kvaila. 1175 00:42:18,270 --> 00:42:21,760 Net jei algorithm-- Atsiprašome, net jei masyvas jau rūšiuojamos, 1176 00:42:21,760 --> 00:42:24,150 pasirinkimas Rūšiuoti ketina nuolat vaikščioti per sąrašą 1177 00:42:24,150 --> 00:42:28,907 įsitikinkite, kad jis yra mažiausias elementas vėl ir vėl ir vėl. 1178 00:42:28,907 --> 00:42:31,740 Ir net jei žmogaus veiklos rezultatas publika žino, kad, palauk, 1179 00:42:31,740 --> 00:42:33,948 Jūs jau praėjo mažiausias elementas, kompiuteris 1180 00:42:33,948 --> 00:42:37,300 nežino, kad tol, kol ji atrodo visą kelią per sąrašą. 1181 00:42:37,300 --> 00:42:40,240 Panašiai, apatinė, kad Taip pat gali būti atsižvelgiama į 1182 00:42:40,240 --> 00:42:42,000 gali būti linijinė laiko. 1183 00:42:42,000 --> 00:42:48,260 >> Kiek laiko užtrunka Rūšiuoti n elementų geriausias 1184 00:42:48,260 --> 00:42:52,420 atveju naudojant kažką panašaus burbulas rūšiuoti? 1185 00:42:52,420 --> 00:42:54,280 Tarkime, kad jūsų sąrašas yra jau išspręstos. 1186 00:42:54,280 --> 00:42:56,696 Mes pasakė burbulas rūšiuoti įgauna iš n Kad kvadrato veiksmus. 1187 00:42:56,696 --> 00:42:59,640 Bet kas, jei jis jau rūšiuojami? 1188 00:42:59,640 --> 00:43:02,310 Ką daryti, jei jūs suprasite, kai vienas pro masyvo 1189 00:43:02,310 --> 00:43:03,540 kad jūs atlikote jokių apsikeitimo? 1190 00:43:03,540 --> 00:43:05,970 Ar jums reikia išlaikyti priimant daugiau eina? 1191 00:43:05,970 --> 00:43:06,470 >> Ne. 1192 00:43:06,470 --> 00:43:10,340 Taigi apatinės burbulas rūšiuoti gali būti laikomas linijinė. 1193 00:43:10,340 --> 00:43:11,830 Omega-n. 1194 00:43:11,830 --> 00:43:14,450 Ir mes galime pažvelgti į kiti šių, taip pat. 1195 00:43:14,450 --> 00:43:17,990 Taigi leiskite priimti greitai pažvelgti ne tik vizualizacijos čia 1196 00:43:17,990 --> 00:43:20,790 pamatyti, kaip jie atskirti save. 1197 00:43:20,790 --> 00:43:24,592 Aš ruošiuosi eiti čia į tai puslapis tai galima rasti C50 tinklalapyje, 1198 00:43:24,592 --> 00:43:27,550 tačiau ji bus skausmas gauti darbo, nes jis naudoja technologiją, vadinamą 1199 00:43:27,550 --> 00:43:30,560 Java programėles, kuris yra daugiausia nepalaikomas šių dienų, 1200 00:43:30,560 --> 00:43:32,730 bent Chrome ir tam tikrų kitų. 1201 00:43:32,730 --> 00:43:37,070 >> Ir leiskite man eiti į priekį ir pagreitinti šį aukštyn ir paaiškinti, kas vyksta. 1202 00:43:37,070 --> 00:43:40,840 Tai yra burbuliukų demonstravimo Rūšiuoti pirmasis algoritmas mes pažvelgė. 1203 00:43:40,840 --> 00:43:43,950 Ir tai, kad vizualizacija kiekvienas Šių barų reiškia skaičių. 1204 00:43:43,950 --> 00:43:45,710 Kuo didesnis baras, Kuo didesnis skaičius. 1205 00:43:45,710 --> 00:43:47,520 Kuo mažesnis baras, mažesnis skaičius. 1206 00:43:47,520 --> 00:43:50,353 Ir tai, ką jūs galite pamatyti vizualiai, net nors tai vyksta super greitai, 1207 00:43:50,353 --> 00:43:53,699 yra tai, kad raudona juosta yra panašus į mane, vaikščioti pirmyn ir atgal nustatymo problemas. 1208 00:43:53,699 --> 00:43:56,740 Jūs galite pamatyti, kad didesni elementai iš tiesų burbuliuoja iki dešinę, 1209 00:43:56,740 --> 00:43:59,650 ir mažesni elementai yra burbuliuoja iki kairę. 1210 00:43:59,650 --> 00:44:01,870 Ir žemyn čia, jei mes realiai atrodo geriau, 1211 00:44:01,870 --> 00:44:04,330 mes iš tikrųjų galime suskaičiuoti skaičius palyginimais ir apsikeitimo 1212 00:44:04,330 --> 00:44:05,350 kad buvo daroma. 1213 00:44:05,350 --> 00:44:07,360 >> Bet vietoj to, pažiūrėkime antroje algoritmu 1214 00:44:07,360 --> 00:44:11,240 mes pažvelgė anksčiau su mūsų savanoriai, atranka rūšiuoti. 1215 00:44:11,240 --> 00:44:13,500 Vizualiai jis turi labai skiriasi poveikis. 1216 00:44:13,500 --> 00:44:16,820 Bet tai vėlgi labai intuityvus, į kad mes nuolat pasirinkdami kitą mažiausias 1217 00:44:16,820 --> 00:44:18,660 elementas, ir mes turime šiek tiek pasisekė. 1218 00:44:18,660 --> 00:44:20,110 Tai pajuto esmės greičiau. 1219 00:44:20,110 --> 00:44:22,840 Bet jei mes bėgo tai vėl ir vėl ir vėl su daug įėjimų, 1220 00:44:22,840 --> 00:44:26,680 mes norėtume pamatyti, kad tai iš tiesų dar didelis O n kvadratu. 1221 00:44:26,680 --> 00:44:29,920 >> Darom paskutinį vieną čia įterpimo rūšiuoti, 1222 00:44:29,920 --> 00:44:33,180 kuri buvo trečioji algoritmas mes pažvelgė ir atšaukimo 1223 00:44:33,180 --> 00:44:36,700 kad tai vienas susijęs su elementai, kaip ji susiduria juos, 1224 00:44:36,700 --> 00:44:39,290 bet tada jis gal pamainomis viskas per padaryti kambarį, 1225 00:44:39,290 --> 00:44:41,660 įterpiant elementus, jei jie priklauso. 1226 00:44:41,660 --> 00:44:45,330 >> Ir tai taip pat baigiasi suteikiant Galutinis rezultatas. Dabar visi tie trys 1227 00:44:45,330 --> 00:44:46,490 jaučiausi gana greitai. 1228 00:44:46,490 --> 00:44:48,740 Ir iš tiesų, išbėgau juos ne gana gera klipas. 1229 00:44:48,740 --> 00:44:52,510 Bet iš esmės, jie visi gana siaubinga, būti sąžiningiems. 1230 00:44:52,510 --> 00:44:56,960 Visi šie algoritmo šiol kad paleisti į didįjį O n kvadratu 1231 00:44:56,960 --> 00:44:59,270 imtis gana šiek tiek laiko paleisti į pabaigoje. 1232 00:44:59,270 --> 00:45:01,920 >> Ir iš tiesų, mes galime pamatyti, ir manote, kad tai galiausiai 1233 00:45:01,920 --> 00:45:04,090 jei aš atsigriebti šį trečiąjį ir galutinis demo. 1234 00:45:04,090 --> 00:45:05,840 Tai yra dar vienas vizualizacija, kad vyksta 1235 00:45:05,840 --> 00:45:08,500 rodyti burbulas rūšiuoti kairėje, pasirinkimas Rūšiuoti centru, 1236 00:45:08,500 --> 00:45:13,410 ir kažkas, kaip vienas iš mūsų ranka kelia anksčiau siūlė, 1237 00:45:13,410 --> 00:45:15,020 sujungti rūšiuoti dešinėje. 1238 00:45:15,020 --> 00:45:16,937 Skaldyk ir valdyk strategija dešinėje. 1239 00:45:16,937 --> 00:45:19,520 Ir tai, tiesą sakant, tai, ką mes ketiname ieškoti trečiadienį. 1240 00:45:19,520 --> 00:45:21,990 Bet tegul laiko juos lygiagrečiai. 1241 00:45:21,990 --> 00:45:26,765 Tai beveik tas pats numeris elementai, visų veikia tuo pačiu metu. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Burbulas rūšiuoti vs atrankos Rūšiuoti vs merge rūšiuoti. 1244 00:45:34,440 --> 00:45:36,760 >> Dabar jie visi veikia teoriškai, tuo pačiu metu. 1245 00:45:36,760 --> 00:45:39,830 CPU veikia pačiu greičiu, bet jūs 1246 00:45:39,830 --> 00:45:44,014 gali jaustis kaip nuobodu tai labai greitai taps, 1247 00:45:44,014 --> 00:45:45,930 ir tiesiog, kaip greitai, kai mes švirkšti savaitę tiek 1248 00:45:45,930 --> 00:45:49,330 Zero algoritmai gali mes pagreitinti. 1249 00:45:49,330 --> 00:45:51,760 >> O dabar tegul palyginti tai vienoje paskutinio forma. 1250 00:45:51,760 --> 00:45:55,710 Aš ruošiuosi eiti į priekį į CS50 tinklalapyje, kur 1251 00:45:55,710 --> 00:45:59,020 mes turime šį galutinį adreso šiandien kai kažkas į internetą 1252 00:45:59,020 --> 00:46:03,960 Maloniai sudėti vaizdo įrašą, kuris fiksuoja Kokios rūšiavimą 1253 00:46:03,960 --> 00:46:07,510 algoritmai skamba. 1254 00:46:07,510 --> 00:46:09,577 Tai įterpimo rūšiuoti. 1255 00:46:09,577 --> 00:46:12,072 >> [Pypsėjimas] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Drauge jūs kreipiatės dažnį remiantis brūkšniniu juostoje aukščio. 1258 00:46:16,850 --> 00:46:19,826 Tai burbulas rūšiuoti. 1259 00:46:19,826 --> 00:46:21,822 >> [Deformuotas pypsėjimas] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Coming Up Next is-- ateina Kitas is-- pasirinkimas rūšiuoti, 1262 00:46:45,774 --> 00:46:48,820 kur vėl, mes pasirinkdami Kitas mažiausias elementas, 1263 00:46:48,820 --> 00:46:51,820 ir mes galime pamatyti, kad auga iš kairės į dešinę. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Sujungti rūšiuoti, todėl mūsų nugalėtojas kas šiandien. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Atkreipkite dėmesį, kaip jis padalinus dalykus į [nesigirdi] pusė ir ketvirčiai. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome Rūšiuoti, kurį mes turime ne kalbėjo apie, ir sukuria vizualiai 1270 00:47:21,660 --> 00:47:24,450 ir audally iš šiek tiek skirtingos formos ir sveiki. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Ėjimas pirmyn ir atgal, Valymo dalykų. 1273 00:47:30,160 --> 00:47:32,230 Taip pat patikrinkite heapsort dėl šios vaikino svetainėje. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Ir tai viskas. 1276 00:47:36,810 --> 00:47:38,210 Pamatysime, jums kitą kartą. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [WHOOSHING ir muzika] 1279 00:47:48,334 --> 00:50:24,839