1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Musiikkia] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> David J. MALAN: Tämä on CS50. 5 00:00:12,550 --> 00:00:14,612 Ja tämä on alku viikolla kolme. 6 00:00:14,612 --> 00:00:16,820 Joten meillä on paljon jännittäviä asiat kattamaan tänään. 7 00:00:16,820 --> 00:00:20,160 Paljon mahdollisuuksia vapaaehtoisille lavalle. 8 00:00:20,160 --> 00:00:22,780 Ja lopulta, tänään on ei noin koodia ollenkaan. 9 00:00:22,780 --> 00:00:24,820 Mutta se on noin ideoita, ja se on noin algoritmeja, 10 00:00:24,820 --> 00:00:28,420 ja itse asiassa tuoda takaisin joitakin saadut kokemukset viikko nolla, 11 00:00:28,420 --> 00:00:31,910 jossa muistaa, me esitteli tämän monstrosity. 12 00:00:31,910 --> 00:00:33,880 Ja lainanotto inspiraatio siitä, aloittaa 13 00:00:33,880 --> 00:00:36,879 ratkaisemaan yhä kehittyneempiä ongelmia algoritmisesti. 14 00:00:36,879 --> 00:00:38,420 Mutta ensin pari ilmoituksia. 15 00:00:38,420 --> 00:00:42,020 Joten, jos haluat liittyä CS50: n henkilökunta ja luokkatoverit lounaalla 16 00:00:42,020 --> 00:00:44,670 perjantaina, sekä täällä että Cambridge, ja New Haven, 17 00:00:44,670 --> 00:00:48,060 käy kurssin sivusto, jossa URL löytyy. 18 00:00:48,060 --> 00:00:50,390 Luento tämä keskiviikkona ei olla täällä Sanders. 19 00:00:50,390 --> 00:00:53,610 Se on verkossa vain, niin virittää klo CS50 n verkkosivuilla, 20 00:00:53,610 --> 00:00:55,850 onko täällä Cambridge tai New Haven samoin. 21 00:00:55,850 --> 00:00:58,110 >> Ja sitten ongelma asettaa kaksi on jo käsissäsi. 22 00:00:58,110 --> 00:01:03,067 Jos et ole syöksyi vielä, haluan tarjota tiukkasanainen ehdotus 23 00:01:03,067 --> 00:01:05,150 että, varsinkin nyt, kun ongelma asettaa etukäteen, 24 00:01:05,150 --> 00:01:08,669 et todellakaan halua aloittaa nyt, jos ei harrastella vähän viikonloppuna tai ennen 25 00:01:08,669 --> 00:01:10,710 kun he ensin mennä ulos Perjantaisin, koska sinun 26 00:01:10,710 --> 00:01:14,380 toteavat, että ne eivät ole välttämättä pitenevät tai haastavampaa kohden 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Luulen löydät että Yleensä ne yleensä ottaa karkeasti 29 00:01:17,575 --> 00:01:18,892 noin saman verran aikaa. 30 00:01:18,892 --> 00:01:20,850 Mutta se varmasti riippuu opiskelijan, ja se 31 00:01:20,850 --> 00:01:22,880 riippuu ajattelutapa jolla voit lähestyä sitä. 32 00:01:22,880 --> 00:01:24,910 Mutta poikkeuksetta, olet menossa olla ristiriidassa joitakin seinää, 33 00:01:24,910 --> 00:01:26,350 ja aiot lyödä jotkut bug, ja olet vain 34 00:01:26,350 --> 00:01:27,950 ei tule pystyä päästä sen yli jossain vaiheessa. 35 00:01:27,950 --> 00:01:31,380 Ja se on erittäin arvokas pystyä vaiheeseen pois, tule takaisin seuraavana päivänä, 36 00:01:31,380 --> 00:01:35,286 mennä virka, viesti CS50 Keskustele tai kuten, todella saada vapautetuksi. 37 00:01:35,286 --> 00:01:36,160 Niin pitää tämä mielessä. 38 00:01:36,160 --> 00:01:40,830 Alkaen aikaisintaan mahdollisimman on parasta, mitä voit tehdä. 39 00:01:40,830 --> 00:01:44,160 Joten tässä on, jos aloimme luokka, yli viikolla nolla. 40 00:01:44,160 --> 00:01:47,441 Ja saamme vapaaehtoinen täällä auttaa minua löytämään mikrofonit? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Seisomaan jo. 43 00:01:48,900 --> 00:01:50,080 Tule ylös. 44 00:01:50,080 --> 00:01:53,707 Arvaa niin se tulee toimimaan. 45 00:01:53,707 --> 00:01:54,415 Mikä on nimesi? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. MALAN: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Tule ylös. 49 00:01:57,910 --> 00:01:58,619 Kiva tavata. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Hauska tavata. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: Ja olit täällä kanssamme viikolla nolla, tietenkin. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: Olin. 53 00:02:03,028 --> 00:02:03,160 Minä olin. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Joten voisitteko mennä eteenpäin ja löytää meille Mike Smith, 55 00:02:05,868 --> 00:02:08,639 niin nopeasti kuin voit? 56 00:02:08,639 --> 00:02:10,639 Niin nopeasti kuin voit. 57 00:02:10,639 --> 00:02:13,756 Kirjaimellisesti repiminen ongelma kahtia niin sinun täytyy. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Kirjaimellisesti repiminen ongelma kahtia. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Oikein hyvä. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Hyvä. 66 00:02:24,200 --> 00:02:24,701 Kiitos. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Erittäin hyvä. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: Ja nyt, olet supistetaan sen alas 70 00:02:27,610 --> 00:02:29,320 puolet koko ongelman. 71 00:02:29,320 --> 00:02:31,267 Nyt olemme alas neljänneksellä. 72 00:02:31,267 --> 00:02:33,475 Oletko kiinnittämällä huomiota millä puolella olemme pitää? 73 00:02:33,475 --> 00:02:34,405 >> [Nauraa] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Kyllä, minä think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Mitä jakso olemmeko? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: vaimentimet, niin. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Mutta Mike Smith on menossa olla jälkeen vaimentimet. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Nauraa] 81 00:02:48,180 --> 00:02:48,742 >> Selvä. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Missä me etsimme? 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: Nyt olemme kirurgisen. 86 00:02:54,760 --> 00:02:57,840 Nyt, lääkärit. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- mennään todellisia. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. MALAN: Real. 91 00:03:00,970 --> 00:03:01,470 OK. 92 00:03:01,470 --> 00:03:03,700 Jos tarvitset Real. 93 00:03:03,700 --> 00:03:05,250 Nyt, mikä tapa on Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Näin. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Mihin suuntaan? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Odota. 97 00:03:08,240 --> 00:03:08,790 M is-- oikea? 98 00:03:08,790 --> 00:03:09,110 Aloitimme with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Joo. 100 00:03:10,090 --> 00:03:10,650 He vasemmalle. 101 00:03:10,650 --> 00:03:11,430 Sinun oikea. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Joo. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Eli Mike täällä. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Mitä? 105 00:03:13,990 --> 00:03:14,665 >> [Nauraa] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Huono esimerkki, kaverit. 108 00:03:18,330 --> 00:03:18,830 Anteeksi. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Tämä opettaa voit hypätä pois oman tuolin. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oi. 112 00:03:22,890 --> 00:03:23,390 Minä sain sinut. 113 00:03:23,390 --> 00:03:24,670 Minä sain sinut. 114 00:03:24,670 --> 00:03:25,170 Oi. 115 00:03:25,170 --> 00:03:25,669 Oi. 116 00:03:25,669 --> 00:03:26,812 Tämä is-- OK, sain sinut. 117 00:03:26,812 --> 00:03:27,520 Smith täällä? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, kiitos. 119 00:03:28,894 --> 00:03:30,535 Joten aion pitää etsimisessä Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Ai, joo. 121 00:03:30,790 --> 00:03:31,340 Ei Ei ei. 122 00:03:31,340 --> 00:03:31,600 Voi ei. 123 00:03:31,600 --> 00:03:31,940 Tämä on minun. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Voi, sinulla Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Joo, minä sai Smith täällä. 127 00:03:34,040 --> 00:03:34,700 Anteeksi, kaverit. 128 00:03:34,700 --> 00:03:35,860 Luulin Michael-- me etsivät Michael. 129 00:03:35,860 --> 00:03:36,550 Anteeksi. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Se on OK. 131 00:03:37,550 --> 00:03:39,950 Okei, nyt olemme osaksi Paccini ja Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini ja poikia. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Vain sinä ja minä olemme tästä. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Löydä meidät 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 Olemme R roskaa. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Roskaa. 141 00:03:48,644 --> 00:03:50,096 Oi. 142 00:03:50,096 --> 00:03:52,480 Tämä vie aikaa. 143 00:03:52,480 --> 00:03:54,340 >> [Nauraa] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Kengät. 146 00:03:56,720 --> 00:03:58,080 Olemme kengät. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nyt olemme gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Nauraa] 151 00:04:03,620 --> 00:04:05,440 Voi, tämä on suuri. 152 00:04:05,440 --> 00:04:06,910 [Nauraa] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Se on OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Voi, tämä on hyvä. 156 00:04:11,365 --> 00:04:14,425 En usko, aion on PSAT ystäviä jälkeen. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Hyvä. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O-, s 161 00:04:18,668 --> 00:04:19,459 DAVID J. MALAN: OK. 162 00:04:19,459 --> 00:04:21,600 Joten repiä tämän kahtia. 163 00:04:21,600 --> 00:04:22,270 Se on ok. 164 00:04:22,270 --> 00:04:25,606 Tämä päättyy huonosti muutenkin, koska Mike Smith ei keltaiset sivut. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Ei, se on OK. 167 00:04:27,140 --> 00:04:28,930 Mutta katsotaanpa teeskennellä kuten hän on tällä sivulla. 168 00:04:28,930 --> 00:04:33,260 Joten nyt, olet supistetaan ongelma alas yhdelle sivulle, ja löysimme Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Hurraavat] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK kiitos. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 Se oli ihmeellistä. 175 00:04:43,646 --> 00:04:45,954 Mutta se oli edelleen nopeampaa kuin lineaarinen haku, 176 00:04:45,954 --> 00:04:47,870 jossa aloitamme kirjan alussa, 177 00:04:47,870 --> 00:04:51,210 ja siirrymme tiemme vasemmalta oikealle, lopulta etsivät Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Ja niin, jos puhelinluettelo oli ehkä 1000 sivua, 179 00:04:53,540 --> 00:04:56,300 ehkä se olisi ottanut meille 10 tai niin sivu kyyneleitä. 180 00:04:56,300 --> 00:04:59,380 >> Mutta sinulla voi olla velkarahalla kosketti oletus 181 00:04:59,380 --> 00:05:03,602 aikana, kaikki se, mikä on sanoa että puhelinluettelon etukäteen oli mitä? 182 00:05:03,602 --> 00:05:04,310 Yleisö: Lajittelu. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Se on lajiteltu. 184 00:05:05,000 --> 00:05:05,160 Oikea? 185 00:05:05,160 --> 00:05:07,909 Se aakkosjärjestyksessä, joten että kaikki nämä nimet ja numerot 186 00:05:07,909 --> 00:05:11,230 lajitellaan luvulta Z: n, ja aakkosjärjestyksessä välillä. 187 00:05:11,230 --> 00:05:13,100 Mutta tänään, nyt kysyä kysymys, hyvin, 188 00:05:13,100 --> 00:05:16,170 kuinka teki Verizon tai puhelin yritys saada se tuohon tilaan? 189 00:05:16,170 --> 00:05:19,560 >> Koska se on yksi asia hyödyntää että oletus, ja siksi, 190 00:05:19,560 --> 00:05:22,570 ratkaista ongelma algoritmi tehokkaammin. 191 00:05:22,570 --> 00:05:24,900 Mutta emme koskaan todella kysyi viikolla nolla, hyvin, 192 00:05:24,900 --> 00:05:27,790 kuinka paljon se maksoi Verizon tai joku muu 193 00:05:27,790 --> 00:05:29,620 saada, että puhelinluettelon lajitellut järjestyksessä? 194 00:05:29,620 --> 00:05:29,780 >> Oikea? 195 00:05:29,780 --> 00:05:31,529 Sillä ei ole väliä, jos looking up Mike Smith 196 00:05:31,529 --> 00:05:35,190 on huippunopea, jos se vie vuosi lajitella sivuja aluksi. 197 00:05:35,190 --> 00:05:35,690 Oikea? 198 00:05:35,690 --> 00:05:38,620 Voit myös vain siivilöidä kautta satunnaistettu puhelinluettelosta, 199 00:05:38,620 --> 00:05:40,690 jos se tulee olemaan erittäin kallista lajitella. 200 00:05:40,690 --> 00:05:42,350 Joten jos voimme olla toinen vapaaehtoinen. 201 00:05:42,350 --> 00:05:46,350 Otetaanpa etsiä täällä miten me might-- tulla up-- miten 202 00:05:46,350 --> 00:05:48,100 voisimme mennä noin lajittelu näistä. 203 00:05:48,100 --> 00:05:51,990 >> Ja jos Jordan voisi todella liittyä meihin täällä lavalla. 204 00:05:51,990 --> 00:05:55,100 Tule ylös vain hetken. 205 00:05:55,100 --> 00:05:56,359 Mikä on nimesi? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, tule ylös. 208 00:05:58,691 --> 00:06:02,070 Ja sinun on liittynyt minun ja Jordan täällä. 209 00:06:02,070 --> 00:06:03,800 Caroline, kiitos. 210 00:06:03,800 --> 00:06:04,300 Selvä. 211 00:06:04,300 --> 00:06:08,330 Joten mitä meillä täällä Caroline on 26 sininen kirjoja 212 00:06:08,330 --> 00:06:10,747 FAS käyttää hallinnoida tiettyjä loppukokeet. 213 00:06:10,747 --> 00:06:13,330 Nämä saavat vaikea löytää, mutta mitä olemme tehneet etukäteen 214 00:06:13,330 --> 00:06:15,800 on, että olemme laittaa jonkun nimi edessä kunkin näistä, 215 00:06:15,800 --> 00:06:18,133 mutta olemme pitäneet sitä yksinkertaista sitten ojentaen täydelliset nimet. 216 00:06:18,133 --> 00:06:22,720 Joten haluaisimme laittaa henkilö, jonka nimi L, D, J, B, aina A-Z, 217 00:06:22,720 --> 00:06:24,090 mutta ne satunnaisessa järjestyksessä. 218 00:06:24,090 --> 00:06:26,890 Ja niin jos voisitte, puhuminen teidän läpi ongelma kun 219 00:06:26,890 --> 00:06:31,620 tehdä se, voit mennä eteenpäin ja järjestää meille, A: sta Z 220 00:06:31,620 --> 00:06:34,070 >> Yleisö: OK, joten L on kuin, keskellä. 221 00:06:34,070 --> 00:06:35,050 C alkaa. 222 00:06:35,050 --> 00:06:42,410 B. J ennen L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Pidä että Vaikka yhden sekunnin. 224 00:06:45,140 --> 00:06:48,910 Koska muuten, tämä on vain kiinnostaa sinua, minua, ja Jordania. 225 00:06:48,910 --> 00:06:49,724 Siellä mennään. 226 00:06:49,724 --> 00:06:50,640 Yleisö: [äänetön]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. MALAN: OK. 229 00:06:58,090 --> 00:06:59,310 Mitä olet tekemässä? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M tulee jälkeen O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. MALAN: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. MALAN: O, Hyvä. 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. Joo. 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. Joten se näyttää olet making-- jatkaa. 238 00:07:10,689 --> 00:07:12,730 Näyttää siltä, ​​teet iso kasa tänne, 239 00:07:12,730 --> 00:07:13,910 ja tavallaan iso kasa tuolla. 240 00:07:13,910 --> 00:07:16,230 Joten alkupuoliskolla aakkoset, jälkipuoliskolla aakkoset. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Hyvä. 243 00:07:16,960 --> 00:07:19,680 Kind of halkaisu ongelma kahdessa. 244 00:07:19,680 --> 00:07:21,771 M, N, X Joo. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. MALAN: OK. 247 00:07:22,980 --> 00:07:25,070 K. Joten olet tavallaan valitsemalla ne yksi toisensa jälkeen, 248 00:07:25,070 --> 00:07:27,620 laittoi pallon joko vasemmalle tai oikealle, tai Z on menossa lattialle. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z tapahtuu lattialle. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y on menossa lattialle. 253 00:07:30,920 --> 00:07:31,735 Nyt voimme laittaa 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: n menossa vasemmalle. 256 00:07:33,700 --> 00:07:36,017 S on menossa oikeaan. 257 00:07:36,017 --> 00:07:37,642 Hyvä on, menee koko matkan vasemmalle. 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: Nyt, hyvä. 260 00:07:39,873 --> 00:07:43,260 Meillä, B, C W: n menossa sinne. 261 00:07:43,260 --> 00:07:45,566 Selvä, 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 Hyvä. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Keskustassa, olen gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Joten nyt, aiomme eräänlainen ja yhdistää nämä eri paaluilla. 267 00:07:52,375 --> 00:08:00,730 Joten kautta C, niin näen D, ja E, ja F, ja G ja H, ja I. Nizza. 268 00:08:00,730 --> 00:08:05,540 J, K. Ja sitten, tämä kasa on ylösalaisin, mutta se on OK. 269 00:08:05,540 --> 00:08:06,040 Kaikin mokomin. 270 00:08:06,040 --> 00:08:07,240 Voimme leikata joitakin kulmat. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 Ja meidän on W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Joo. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Erinomainen. 275 00:08:11,880 --> 00:08:14,122 Joten iso kiitos Caroline lajitteluun näitä. 276 00:08:14,122 --> 00:08:15,030 >> [Hurraavat] 277 00:08:15,030 --> 00:08:17,287 >> Kiitos. 278 00:08:17,287 --> 00:08:18,120 Kiitos paljon. 279 00:08:18,120 --> 00:08:22,910 Joten nyt Tarkastellaan hetki miten Caroline meni noin tekee, että 280 00:08:22,910 --> 00:08:26,040 ja mitä me pystyivät to-- miten me 281 00:08:26,040 --> 00:08:28,409 pystyivät ratkaisemaan että ongelma, kun olimme juuri 282 00:08:28,409 --> 00:08:29,950 annetaan koko joukko satunnaisia ​​panoksia. 283 00:08:29,950 --> 00:08:31,610 >> No, näyttää siltä, ​​että oli hieman järjestelmässä? 284 00:08:31,610 --> 00:08:32,110 Oikea. 285 00:08:32,110 --> 00:08:34,495 Joten aiemmin kirjaimet aakkosissa, hän 286 00:08:34,495 --> 00:08:37,120 oli laskemisesta vasemmalle, ja myöhemmin kirjaimia, 287 00:08:37,120 --> 00:08:38,270 hän laittoi oikeaan. 288 00:08:38,270 --> 00:08:40,500 Ja kun hän löysi jotkut proksimaalinen kirjeitä, niistä 289 00:08:40,500 --> 00:08:43,124 jotka menevät oikeus vierekkäin, hän laittaa ne kunnossa. 290 00:08:43,124 --> 00:08:46,750 Ja niin me tavallaan oli näitä pieniä kasoittain lajitellun siihen syötetään. 291 00:08:46,750 --> 00:08:50,540 >> Ja niin se on aivan kuin mitä useimmat meistä ihmiset tekisi. 292 00:08:50,540 --> 00:08:53,530 Haluamme tavallaan käydä läpi sitä, ja olisimme sellainen on mekanismi. 293 00:08:53,530 --> 00:08:56,930 Mutta se voi olla vaikea kirjoittaa sen alas kaavassa sinänsä. 294 00:08:56,930 --> 00:08:59,010 Se tuntui hieman enemmän orgaanista kuin. 295 00:08:59,010 --> 00:09:02,560 Joten, jos voimme nyt sidottu ongelma vähemmän tuloa. 296 00:09:02,560 --> 00:09:05,170 >> Sen sijaan 26, katsotaanpa tehdä jotain paljon vähemmän 297 00:09:05,170 --> 00:09:09,890 vain sanoa, seitsemän, takana nämä ovet, niin sanoakseni. 298 00:09:09,890 --> 00:09:11,300 Onko vain seitsemän numeroa? 299 00:09:11,300 --> 00:09:15,240 Ja jos tavoite nyt käsi on löytää arvo, 300 00:09:15,240 --> 00:09:17,850 Katsotaanpa, miten tehokkaasti voimme edetä tässä. 301 00:09:17,850 --> 00:09:22,460 Ja katsotaan, jos voimme nyt alkaa soveltaa joitakin numeroita, 302 00:09:22,460 --> 00:09:26,310 tai joitakin kaavoja, joiden avulla voidaan kuvata tehokkuuteen puhelinluettelo 303 00:09:26,310 --> 00:09:31,060 algoritmi, meidän tentti kirja algoritmi, ja yleisemmin löytää tietoa. 304 00:09:31,060 --> 00:09:34,770 >> Joten tämä, anna minun mennä eteenpäin, ja kosketusnäytöllä tänne, 305 00:09:34,770 --> 00:09:41,100 sietää selain, joka on juuri näiden seitsemän ovet. 306 00:09:41,100 --> 00:09:46,670 Ja jos voisimme saada yksi muu vapaaehtoisesti tulla tänne, 307 00:09:46,670 --> 00:09:48,480 Laitoin nämä samat ovet tänne. 308 00:09:48,480 --> 00:09:49,170 Nopea vapaaehtoinen. 309 00:09:49,170 --> 00:09:51,130 >> Tämä one-- demot ovat menossa on nopeampi ja nopeampi nyt. 310 00:09:51,130 --> 00:09:51,600 Tule alas. 311 00:09:51,600 --> 00:09:52,308 Mikä on nimesi? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. MALAN: Trevor? 314 00:09:53,998 --> 00:09:55,770 Hyvä, Trevor, tule alas. 315 00:09:55,770 --> 00:09:59,212 Joten Trevor on vapaaehtoisesti tästä tehdä samanlainen ongelma, mutta se on 316 00:09:59,212 --> 00:10:02,170 suppeampi, ja että menee jotta voimme yrittää virallistaa nyt 317 00:10:02,170 --> 00:10:03,970 prosessi lajittelun näitä numeroita. 318 00:10:03,970 --> 00:10:05,500 >> Joten Trevor, mukava tavata. 319 00:10:05,500 --> 00:10:08,720 Joten tässä on jono, niin puhua, luettelon seitsemästä ovet. 320 00:10:08,720 --> 00:10:10,327 Menkää ja löytää meidät numero 50. 321 00:10:10,327 --> 00:10:12,410 Ja sitten sen jälkeen se, Kerro meille miten löysit sen. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Jos be-- kunnossa. 324 00:10:20,040 --> 00:10:21,945 Joo, tämä on yksi täällä? 325 00:10:21,945 --> 00:10:24,680 O-ou. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Valitsit, että yksi. 328 00:10:26,680 --> 00:10:28,690 Hyvä. 329 00:10:28,690 --> 00:10:29,780 >> Ja hyvä. 330 00:10:29,780 --> 00:10:30,970 Nyt valitsit, että yksi. 331 00:10:30,970 --> 00:10:34,060 Ja minä annan sinulle mikrofoni, niin että sinulla on se vain hetken. 332 00:10:34,060 --> 00:10:37,000 Menkää ja napsauta vieressä, että aiot. 333 00:10:37,000 --> 00:10:39,812 Kyllä hyvä. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Voinko tyhjennä ovi? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Ei, et voi tyhjennä. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Tämä. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Missä haluat mennä? 339 00:10:45,640 --> 00:10:46,410 Mikä? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Tuo. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: Ei. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Tämä. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Kyllä. 345 00:10:49,020 --> 00:10:49,700 Se oli hyvä. 346 00:10:49,700 --> 00:10:50,380 Selvä. 347 00:10:50,380 --> 00:10:53,900 Joten mikä oli algoritmi tai menettely teet tämän, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Minä vain meni läpi ovet kunnes löysin 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Erinomainen algoritmi. 351 00:10:58,150 --> 00:10:59,540 Niin se käy hyvin. 352 00:10:59,540 --> 00:11:03,120 Koska itse asiassa, jos paljastan mitä Näiden takana muut ovet, mitä 353 00:11:03,120 --> 00:11:06,954 me löydämme tässä että meillä on vain satunnainen tulo. 354 00:11:06,954 --> 00:11:08,870 Joten se oli todella niin hyvä kuin sinä. 355 00:11:08,870 --> 00:11:12,509 Ja itse asiassa, sinulla parempi kuin tyhjentävästi etsivät koko joukko, 356 00:11:12,509 --> 00:11:15,300 koska se olisi ollut todella epäonninen jos olisit osunut numero 357 00:11:15,300 --> 00:11:16,604 50 aivan viime ovi. 358 00:11:16,604 --> 00:11:18,520 Mutta mitä jos me sen sijaan antoi sinulle oletus. 359 00:11:18,520 --> 00:11:20,630 Kai tavallaan kaikki nämä ovet ympäri, 360 00:11:20,630 --> 00:11:23,500 niin että sinulla on numerot lajiteltu tällä kertaa, 361 00:11:23,500 --> 00:11:29,730 mutta tällä kertaa se on todella different-- tällä kertaa, 362 00:11:29,730 --> 00:11:32,640 se on todella lajiteltu sinulle. 363 00:11:32,640 --> 00:11:35,380 Ja nyt tavoite käsillä on lyödä numero 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Mikä algoritmisi olemaan? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: No, jos se on lajiteltu, se on joko menossa 367 00:11:39,628 --> 00:11:42,710 jotta be-- jos suurin suurimpaan, laskeva, se tulee olemaan ensimmäinen, 368 00:11:42,710 --> 00:11:44,751 tai jos se on päinvastainen, se on viimeinen. 369 00:11:44,751 --> 00:11:48,897 Niin minä vain koskettamalla tätä ovea, ja sitten napauttamalla viimeinen ovi. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Erinomainen. 371 00:11:49,980 --> 00:11:50,270 Selvä. 372 00:11:50,270 --> 00:11:51,150 Joten löysimme numero 50. 373 00:11:51,150 --> 00:11:52,970 Niin heti kun tiesit ne lajiteltiin, me 374 00:11:52,970 --> 00:11:55,040 pystyivät hyödyntämään tätä oletusta. 375 00:11:55,040 --> 00:11:57,040 Joten he ovat liian paljon puhelinluettelon esimerkki. 376 00:11:57,040 --> 00:11:59,540 Heti kun on, vaikka pieni ongelma näin, 377 00:11:59,540 --> 00:12:02,380 teidän tuloa esilajiteltuina, voimme itse löytää arvo todennäköisesti 378 00:12:02,380 --> 00:12:03,130 tehokkaammin. 379 00:12:03,130 --> 00:12:05,800 >> Ja en kertonut sinulle, jos se oli lajiteltu pienistä isoihin, tai iso pienille, 380 00:12:05,800 --> 00:12:08,080 ja niin se oli hyvin kohtuullinen aloittaa toisessa päässä tai muita 381 00:12:08,080 --> 00:12:09,750 todella löytää että tavoitearvo. 382 00:12:09,750 --> 00:12:11,400 Joten kiitos Trevor samoin. 383 00:12:11,400 --> 00:12:13,260 Ja minä propose-- hienosti tehty. 384 00:12:13,260 --> 00:12:16,960 Meillä on hieman leikkeen, todella, että on yksi meidän suosikki hetkiä CS50, 385 00:12:16,960 --> 00:12:19,700 jolloin joskus demoja eivät aivan mene suunnitelmien mukaan. 386 00:12:19,700 --> 00:12:22,050 Ja todellakin juuri nyt, minä revitä väärä liitäntä 387 00:12:22,050 --> 00:12:23,508 jolla voidaan käyttää kosketusnäyttöä. 388 00:12:23,508 --> 00:12:24,660 Niin että oli minun vikani siellä. 389 00:12:24,660 --> 00:12:26,600 >> Joten tämä tekee varten ensi vuoden leike nimellä 390 00:12:26,600 --> 00:12:28,570 miksi olin klikkaamalla oman näytön. 391 00:12:28,570 --> 00:12:31,390 Mutta sallikaa vilkaista mitä tapahtui viime vuonna 392 00:12:31,390 --> 00:12:34,770 Jay Hän tuli, paljon kuten Trevor täällä, vapaaehtoisesti, 393 00:12:34,770 --> 00:12:39,380 ja tässä lyhyen pätkän, näet miten tämä sama demo ei aivan 394 00:12:39,380 --> 00:12:41,074 paljastavat samoja opetukset. 395 00:12:41,074 --> 00:12:41,740 [VIDEOTOISTOSTA] 396 00:12:41,740 --> 00:12:45,360 -Kaikki Haluan sinun tehdä nyt on löytää minulle, ja meille, 397 00:12:45,360 --> 00:12:51,674 todella, numero 50 askel kerrallaan. 398 00:12:51,674 --> 00:12:52,450 >> -The Numero 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Numero 50. 400 00:12:53,190 --> 00:12:55,356 Ja voit paljastaa mitä takana jokainen näistä ovet 401 00:12:55,356 --> 00:12:58,540 yksinkertaisesti koskettamalla sitä sormella. 402 00:12:58,540 --> 00:13:00,910 Perkele. 403 00:13:00,910 --> 00:13:02,870 >> [Nauraa] 404 00:13:02,870 --> 00:13:03,806 >> [Lopeta toisto] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Niin että meni hyvin. 406 00:13:05,430 --> 00:13:06,796 Ne olivat lajittelemattoman ovet. 407 00:13:06,796 --> 00:13:08,670 Ja Jay, tietenkin, löytyi kaiken liian nopeasti. 408 00:13:08,670 --> 00:13:12,910 Trevor teki paljon paremmin kannalta oppivainen hetki, 409 00:13:12,910 --> 00:13:15,850 niin sanoakseni, tänä vuonna kauemmin löytää se. 410 00:13:15,850 --> 00:13:17,950 Tietenkin, sitten annoimme Jay toisen mahdollisuuden, 411 00:13:17,950 --> 00:13:20,320 jolloin me lajiteltu ovet, aivan kuten teimme Trevor, 412 00:13:20,320 --> 00:13:22,300 ja Trevor teki Super hyvin tällä kertaa. 413 00:13:22,300 --> 00:13:26,124 Mutta Jay teki sen puoli yhtä nopeasti. 414 00:13:26,124 --> 00:13:26,790 [VIDEOTOISTOSTA] 415 00:13:26,790 --> 00:13:29,650 -The Tavoitteena on nyt myös löytää meidät numero 50, 416 00:13:29,650 --> 00:13:33,030 mutta ei se algoritmisesti, ja Kerro meille miten aiot siitä. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -Ja Jos löydät sen, pidät elokuvan. 419 00:13:35,604 --> 00:13:37,228 Jos et löydä sitä, annat sen takaisin. 420 00:13:37,228 --> 00:13:38,044 >> -karstaamattomista. 421 00:13:38,044 --> 00:13:38,860 >> -Oi! 422 00:13:38,860 --> 00:13:40,800 >> - [Kuultavissa] OK. 423 00:13:40,800 --> 00:13:46,236 Joten aion tarkistaa päät ensimmäinen onko there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [APPLAUSE] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [Lopeta toisto] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Joten lajittelu ovet selvästi johtaa suurempaan tehokkuuteen. 429 00:13:59,760 --> 00:14:01,680 Ja niin, kaksi kertaa niin nopeasti on mitä tarkoitin siellä. 430 00:14:01,680 --> 00:14:03,270 Ja niin Jay onnisti molemmilla kerroilla. 431 00:14:03,270 --> 00:14:06,685 Ja hän sai myös onnekas, että viime vuosi, Tilasin Blu-ray-levyjä 432 00:14:06,685 --> 00:14:07,560 todella antaa ulos. 433 00:14:07,560 --> 00:14:09,768 Olen pahoillani tänä vuonna, me ei ollut sama, Trevor. 434 00:14:09,768 --> 00:14:11,540 Mutta vielä parempi oli muutama vuosi sitten. 435 00:14:11,540 --> 00:14:14,820 Ja jotkut teistä ehkä tietävät tämän kaveri, Sean, kuka kun hän oli CS50, 436 00:14:14,820 --> 00:14:17,780 altistettiin tarkka Sama ongelma, vaikkakin SD, 437 00:14:17,780 --> 00:14:19,360 niin voit pian nähdä, takaisin seuraavana päivänä. 438 00:14:19,360 --> 00:14:22,622 Ja huomaat, että ei ainoastaan hän kestää hieman kauemmin kuin Jay, 439 00:14:22,622 --> 00:14:25,580 hieman kauemmin kuin Trevor, se oli Oikeastaan ​​tämä loistava tilaisuus 440 00:14:25,580 --> 00:14:29,820 harjoittaa lähes kaikki Yleisö la hinta on oikea, kannustamalla 441 00:14:29,820 --> 00:14:31,889 hänet löytää numero olimme etsivät. 442 00:14:31,889 --> 00:14:32,930 Katsotaanpa. vilkaista. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEOTOISTOSTA] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Joten teidän tehtävänne täällä, Sean, on seuraava. 446 00:14:36,680 --> 00:14:40,860 Olen piilossa nämä ovet numero seitsemän. 447 00:14:40,860 --> 00:14:45,120 Mutta makaavat joissakin näistä ovet sekä muita negatiivisia lukuja. 448 00:14:45,120 --> 00:14:47,500 Ja sinun tehtäväsi on ajatella Tämän ylärivin numerot 449 00:14:47,500 --> 00:14:50,390 kuten juuri array, tai vain sekvenssi paperinpaloja 450 00:14:50,390 --> 00:14:51,510 numerot niiden takana. 451 00:14:51,510 --> 00:14:55,540 Ja tavoitteena on, vain käyttämällä alkuun array täällä, etsi minulle numero seitsemän. 452 00:14:55,540 --> 00:14:58,570 Ja olemme sitten menee kritiikkiä miten edetä tee sitä. 453 00:14:58,570 --> 00:14:59,070 -Selvä. 454 00:14:59,070 --> 00:15:00,850 Find meille numero seitsemän, kiitos. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Ei. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Viisi, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Nauraa] 461 00:15:24,770 --> 00:15:25,910 >> Se ei ole temppu kysymys. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Yksi. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Nauraa] 466 00:15:34,695 --> 00:15:37,861 Tässä vaiheessa, sinun pisteet ei ole kovin hyvä, joten voit yhtä hyvin jatkaa. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Kolme. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Nauraa] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Jatka. 473 00:15:47,774 --> 00:15:50,690 Suoraan sanottuna, en voi olla ihmettelemättä mitä olet edes ajatellut, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Nauraa] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Vain ylärivi, joten sinulla kolme vasemmalle. 477 00:15:55,020 --> 00:15:56,200 Joten löytää minut seitsemän. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Nauraa] 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 Seitsemän. 484 00:16:26,946 --> 00:16:28,780 >> [APPLAUSE] 485 00:16:28,780 --> 00:16:29,426 >> Selvä. 486 00:16:29,426 --> 00:16:30,360 >> [Lopeta toisto] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: jotta voisimme katsella näitä koko päivän. 488 00:16:31,840 --> 00:16:34,090 Ja tietenkin, jotkut Tämän vuoden demoja ehkä 489 00:16:34,090 --> 00:16:36,330 nyt päätyvät ensi vuoden video samoin. 490 00:16:36,330 --> 00:16:39,040 Joten Nyt todella keskitytään algoritmien 491 00:16:39,040 --> 00:16:42,140 täällä, ja katso jos emme voi nyt alkaa virallistaa 492 00:16:42,140 --> 00:16:46,650 miten voimme mennä noin saada tietomme tähän tilaan, että se on lajiteltu, 493 00:16:46,650 --> 00:16:50,054 niin että lopulta voimme todella etsiä sitä tehokkaammin. 494 00:16:50,054 --> 00:16:52,470 Ja vaikka me aiomme käyttää melko pieniä aineistoja, 495 00:16:52,470 --> 00:16:54,511 kuten kahdeksan numeroa meillä on tässä pöydällä, 496 00:16:54,511 --> 00:16:58,230 lopulta nämä samat ajatukset voitaisiin soveltaa 1000 tuloa, miljoonaa tuloa, 497 00:16:58,230 --> 00:17:02,100 4000000000 tuloa, koska algoritmit tulevat olemaan pohjimmiltaan sama. 498 00:17:02,100 --> 00:17:05,359 >> Ja niin tämä on meidän viimeinen tilaisuus vapaaehtoisia tänään, 499 00:17:05,359 --> 00:17:09,790 mutta ehkä kaikkein mukana yksi, josta meillä tarvitsevat kahdeksan vapaaehtoisia 500 00:17:09,790 --> 00:17:12,960 keksiä ja kävellä meitä prosessi lajittelu mitä pian 501 00:17:12,960 --> 00:17:15,212 olla seuraavilla musiikki seisoo täällä. 502 00:17:15,212 --> 00:17:16,170 Aloitan takaisin tänne. 503 00:17:16,170 --> 00:17:19,692 >> Joten yksi turquoise-- vihreä on se? 504 00:17:19,692 --> 00:17:21,130 Oletko syyllistyneet? 505 00:17:21,130 --> 00:17:21,630 Kaksi. 506 00:17:21,630 --> 00:17:23,069 Tule alas. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Kolme. 509 00:17:24,420 --> 00:17:25,400 Neljä. 510 00:17:25,400 --> 00:17:27,247 Anna me-- OK, viisi. 511 00:17:27,247 --> 00:17:28,830 Olet parhaillaan nimeämä ystäväsi. 512 00:17:28,830 --> 00:17:31,340 Kuusi, seitsemän ja kahdeksan. 513 00:17:31,340 --> 00:17:32,130 Tule ylös. 514 00:17:32,130 --> 00:17:32,630 Selvä. 515 00:17:32,630 --> 00:17:33,190 Kiitos paljon. 516 00:17:33,190 --> 00:17:33,689 Tule ylös. 517 00:17:33,689 --> 00:17:34,790 Tule ylös. 518 00:17:34,790 --> 00:17:35,330 >> Selvä. 519 00:17:35,330 --> 00:17:38,890 Joten mitä meillä here-- ja tämä on yksi enemmän hankala niistä, 520 00:17:38,890 --> 00:17:42,390 koska tämä edellyttää, että olet huumori minulle vain vähän aikaa. 521 00:17:42,390 --> 00:17:43,442 Sinun on ykkönen. 522 00:17:43,442 --> 00:17:44,150 Mikä on nimesi? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. MALAN: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Mikä on nimesi? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, olet numero kaksi. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, numero kolme. 530 00:17:52,260 --> 00:17:53,722 Stefan, numero neljä. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, numero viisi. 533 00:17:57,548 --> 00:17:58,452 [Äänetön] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [äänetön]. 535 00:17:59,618 --> 00:18:00,391 David, numero kuusi. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: Mattin numero seitsemän. 538 00:18:02,160 --> 00:18:02,850 Ja? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, numero kahdeksan. 541 00:18:04,470 --> 00:18:04,970 Selvä. 542 00:18:04,970 --> 00:18:06,510 Jos could-- oho. 543 00:18:06,510 --> 00:18:08,820 Jos kaikki, kuin Ensimmäinen haaste, siellä 544 00:18:08,820 --> 00:18:10,820 kahdeksan Nuottitelineet tässä yleisöön päin. 545 00:18:10,820 --> 00:18:14,200 Jos voit laittaa numerot nämä musiikki seisoo siten 546 00:18:14,200 --> 00:18:16,560 että he riviin Sama numerot taululle. 547 00:18:16,560 --> 00:18:19,560 Joten tehdä itse näyttää, että laittamalla numerot seuraavilla musiikki 548 00:18:19,560 --> 00:18:21,960 seisoo täällä. 549 00:18:21,960 --> 00:18:25,980 Erinomainen toistaiseksi. 550 00:18:25,980 --> 00:18:26,600 >> Erinomainen. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Joten nyt, me pyydämme kysymys muutamalla eri tavalla. 553 00:18:29,556 --> 00:18:31,610 Kuinka voimme edetä lajittelu nämä ihmiset täällä? 554 00:18:31,610 --> 00:18:34,500 Koska meillä oli muutamia lähestymistapoja aikaisemmin, jolloin olimme 555 00:18:34,500 --> 00:18:36,360 sellainen tehdään kaksi eri kauhat. 556 00:18:36,360 --> 00:18:38,842 Ja sitten olimme yleisesti vähitellen luonut asioita yhdessä. 557 00:18:38,842 --> 00:18:41,050 Heti kun näimme kaksi lukua jotka kuuluivat yhteen, 558 00:18:41,050 --> 00:18:41,975 laitamme ne yhteen. 559 00:18:41,975 --> 00:18:43,350 Kaksi kirjainta, jotka kuuluvat yhteen. 560 00:18:43,350 --> 00:18:45,058 >> Mutta katsotaanpa, jos me voi virallistaa tätä, 561 00:18:45,058 --> 00:18:48,044 jotta voimme lopulta jotkut pseudo-koodi haluatte, 562 00:18:48,044 --> 00:18:49,710 jolla voit ratkaista nämä ongelmat. 563 00:18:49,710 --> 00:18:51,870 Joten nyt, etsin ulos näitä numeroita täällä. 564 00:18:51,870 --> 00:18:55,030 Ja näen koko joukko virheitä. 565 00:18:55,030 --> 00:18:57,750 Lopulta haluan yksi vasemmalle ja kahdeksan oikealla. 566 00:18:57,750 --> 00:19:00,650 >> Ja niin Etsin nämä kaksi, neljä ja kaksi. 567 00:19:00,650 --> 00:19:02,930 Ja mikä on ongelma, ilmeisesti? 568 00:19:02,930 --> 00:19:04,261 Joo. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Kaksi ilmeisesti tulee ennen neljä, niin tiedät mitä? 571 00:19:07,160 --> 00:19:10,210 Haluaisin ensin ottaa ahne lähestymistapa, jos haluatte, aivan kuten ongelma 572 00:19:10,210 --> 00:19:13,790 asettaa one-- jos muistan Standard Edition Harjoitus One, 573 00:19:13,790 --> 00:19:16,820 missä minä vain paikallisesti ratkaista ongelma se täällä edessäni 574 00:19:16,820 --> 00:19:17,690 ja katso mihin se johtaa minua. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Joten kaksi ja neljä, anna minun mennä eteenpäin ja vain vaihtaa te kaksi. 577 00:19:20,161 --> 00:19:22,400 Jos voit fyysisesti liikkua itsenne ja paperi, 578 00:19:22,400 --> 00:19:25,040 Olen ilmeisesti saanut luetella paremmassa kunnossa. 579 00:19:25,040 --> 00:19:26,330 >> Nyt he ovat hyviä. 580 00:19:26,330 --> 00:19:28,480 Aion siirtyä, neljä ja kuusi, näyttää hyvältä. 581 00:19:28,480 --> 00:19:29,110 Ei ole ongelma. 582 00:19:29,110 --> 00:19:30,440 Kuusi ja kahdeksan, OK. 583 00:19:30,440 --> 00:19:31,860 Kahdeksan ja yksi, toinen ongelma. 584 00:19:31,860 --> 00:19:34,750 Sillä mitä on totta noin kahdeksan ja yksi? 585 00:19:34,750 --> 00:19:36,990 Yksi tulee ennen kahdeksaa, ja niin mitä meidän pitäisi tehdä? 586 00:19:36,990 --> 00:19:38,090 Katsotaanpa vaihtaa nämä kaksi. 587 00:19:38,090 --> 00:19:39,316 Yksi ja kahdeksan. 588 00:19:39,316 --> 00:19:40,690 Ja nyt, aion jatkaa. 589 00:19:40,690 --> 00:19:42,030 Aion pitää Jatkossakin. 590 00:19:42,030 --> 00:19:42,840 Ja katsotaan mitä tapahtuu. 591 00:19:42,840 --> 00:19:44,680 Kahdeksan ja kolme, ja Tietenkin epäkunnossa. 592 00:19:44,680 --> 00:19:45,815 Katsotaanpa swap. 593 00:19:45,815 --> 00:19:46,940 Kahdeksan ja seitsemän, tietenkin. 594 00:19:46,940 --> 00:19:47,481 Epäkunnossa. 595 00:19:47,481 --> 00:19:48,280 Katsotaanpa swap. 596 00:19:48,280 --> 00:19:49,940 Kahdeksan ja viisi, tietenkin, katsotaanpa swap. 597 00:19:49,940 --> 00:19:50,560 Selvä. 598 00:19:50,560 --> 00:19:51,880 Lista on järjestetty. 599 00:19:51,880 --> 00:19:53,060 kyllä? 600 00:19:53,060 --> 00:19:54,280 >> OK, ei tietenkään. 601 00:19:54,280 --> 00:19:55,860 Mutta se on hieman parempi, eikö? 602 00:19:55,860 --> 00:19:57,270 Koska ilmoitus mitä tapahtui. 603 00:19:57,270 --> 00:20:01,749 Joka kerta teimme swap, pienempi määrä sellainen percolated näin, 604 00:20:01,749 --> 00:20:03,790 ja isompi numero percolated näin, tai käymme 605 00:20:03,790 --> 00:20:06,880 alkavat sanoa kuplina on vasemmalle tai kuplia oikealle. 606 00:20:06,880 --> 00:20:10,080 >> Nyt, se ei riitä, koska parhaimmillaan luku saattaa 607 00:20:10,080 --> 00:20:11,990 ovat siirtyneet yksi paikalla eteenpäin, tai pahimmillaan, 608 00:20:11,990 --> 00:20:13,880 numero voi olla siirretty yhdellä paikalla edelleen. 609 00:20:13,880 --> 00:20:16,369 Niin tiedät mitä, tällainen on toiminut melko hyvin tähän asti. 610 00:20:16,369 --> 00:20:17,410 Sallikaa minun vain kokeilla sitä uudelleen. 611 00:20:17,410 --> 00:20:18,880 Kaksi ja neljä, he OK. 612 00:20:18,880 --> 00:20:20,180 Neljä ja kuusi, ne ovat OK. 613 00:20:20,180 --> 00:20:21,790 Kuusi ja yksi, epäkunnossa. 614 00:20:21,790 --> 00:20:23,007 Joten vaihtaa te kaksi. 615 00:20:23,007 --> 00:20:25,840 Ja nyt, huomaa ongelma: n alkaa saada hieman paremmin taas. 616 00:20:25,840 --> 00:20:27,006 Kuusi ja kolme, epäkunnossa. 617 00:20:27,006 --> 00:20:28,100 Katsotaanpa vaihtaa sinulle kaksi. 618 00:20:28,100 --> 00:20:29,730 Kuusi ja seitsemän, olet hyvä. 619 00:20:29,730 --> 00:20:32,230 Seitsemän ja viisi, tietenkin, epäkunnossa. 620 00:20:32,230 --> 00:20:33,920 Seitsemän ja kahdeksan, jotta. 621 00:20:33,920 --> 00:20:36,470 Ja nyt, minä ehkä tehdä tämän muutaman kerran. 622 00:20:36,470 --> 00:20:39,830 Ja itse asiassa ajatella itsellenne ehkä kuinka monta kertaa maksimaalisesti 623 00:20:39,830 --> 00:20:41,330 voisin kävellä edestakaisin? 624 00:20:41,330 --> 00:20:42,390 >> Palaamme tähän. 625 00:20:42,390 --> 00:20:43,700 Joten kaksi ja neljä ovat vielä OK. 626 00:20:43,700 --> 00:20:44,940 Neljä ja yksi, nope. 627 00:20:44,940 --> 00:20:45,747 Joten, nyt swap. 628 00:20:45,747 --> 00:20:47,830 Ja vielä, havaitse yksi on sellainen kuplivaa 629 00:20:47,830 --> 00:20:49,163 vasemmalle, missä sen pitäisi olla. 630 00:20:49,163 --> 00:20:50,010 Neljä ja kolme swap. 631 00:20:50,010 --> 00:20:51,330 Neljä ja kuusi. 632 00:20:51,330 --> 00:20:53,100 Kuusi ja viisi swap. 633 00:20:53,100 --> 00:20:53,959 Kuusi ja seitsemän. 634 00:20:53,959 --> 00:20:55,000 Seitsemän ja kahdeksan ovat hyviä. 635 00:20:55,000 --> 00:20:55,500 >> Hyvä. 636 00:20:55,500 --> 00:20:58,460 Saamme jopa parempi. 637 00:20:58,460 --> 00:20:59,130 Katsotaanpa. 638 00:20:59,130 --> 00:21:00,940 Nyt meillä on kaksi ja yksi. 639 00:21:00,940 --> 00:21:02,520 Tietenkin, vaihtaa. 640 00:21:02,520 --> 00:21:07,520 Kaksi ja kolme, kolme ja neljä, neljä ja viisi, kuusi ja seitsemän, seitsemän ja kahdeksan. 641 00:21:07,520 --> 00:21:08,020 Hyvä. 642 00:21:08,020 --> 00:21:08,730 Ja tiedätkö mitä? 643 00:21:08,730 --> 00:21:11,190 Koska olen tehnyt yhden muutoksen siellä, anna minun tehdä yksi järki tarkistaa. 644 00:21:11,190 --> 00:21:13,023 Anna minun mennä aina alkuun. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Yksi, two-- Joo, katso? 647 00:21:14,750 --> 00:21:15,870 Jotain oli vialla. 648 00:21:15,870 --> 00:21:18,420 Kolme, neljä, viisi, kuusi, seitsemän, kahdeksan. 649 00:21:18,420 --> 00:21:21,920 Ja tässä viime taaksepäin, ovat viihtyisää minun nyt 650 00:21:21,920 --> 00:21:23,830 väittämällä lajitellaan? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Visuaalisesti se on aivan totta. 653 00:21:25,880 --> 00:21:28,410 Mutta toiminnallisesti, mitä ei myös vain tapahdu 654 00:21:28,410 --> 00:21:31,870 että viime pass, jonka avulla voit vahvistaa, että tämä luettelo on todellakin 655 00:21:31,870 --> 00:21:32,660 lajiteltu? 656 00:21:32,660 --> 00:21:34,477 >> Mitä olen tehnyt tai ei tehdä tätä viime pass? 657 00:21:34,477 --> 00:21:35,810 Yleisö: ei tapahtunut muutoksia. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Anteeksi? 659 00:21:36,120 --> 00:21:37,070 Yleisö: Ei muutoksia. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: ei tapahtunut muutoksia. 661 00:21:38,653 --> 00:21:41,947 Joten olisi typerää minua tehdä samaa algoritmia uudelleen 662 00:21:41,947 --> 00:21:43,780 jos en tee mitään muuttaa ensimmäistä kertaa. 663 00:21:43,780 --> 00:21:45,160 Ja valtio ei ole muuttunut. 664 00:21:45,160 --> 00:21:47,576 Totisesti, en aio tehdä Muutoksista toisen kerran. 665 00:21:47,576 --> 00:21:49,820 Ja niin, se on turvallista nyt sanoa, Lista on järjestetty. 666 00:21:49,820 --> 00:21:52,069 >> Ja todellakin, tämä on nyt jotain, että me will yleisesti 667 00:21:52,069 --> 00:21:56,900 puhelu kuplalajittelu, jolloin pareittain, voit korjata virheitä uudelleen, 668 00:21:56,900 --> 00:22:00,210 ja uudestaan, ja uudestaan, ja sinä jatka edestakaisin, 669 00:22:00,210 --> 00:22:03,370 ja edestakaisin, kunnes tehdä tällaista swap, jossa vaiheessa 670 00:22:03,370 --> 00:22:07,089 voit olla varma, joo, minä päättynyt vahvistamisesta kaikki virheet. 671 00:22:07,089 --> 00:22:08,630 Katsotaanpa nollata ja kokeile toista lähestymistapaa. 672 00:22:08,630 --> 00:22:11,590 Jos te voisi mennä takaisin tilaus olit hetki sitten, 673 00:22:11,590 --> 00:22:13,780 joka näytti tältä. 674 00:22:13,780 --> 00:22:17,640 Nyt, ottaa lähestymistapa hieman enemmän kuin tentti kirja, 675 00:22:17,640 --> 00:22:21,122 jolloin olimme jatkuvasti valitsemalla kirjain 676 00:22:21,122 --> 00:22:22,830 että me eräänlainen halusimme käsitellä seuraavaksi. 677 00:22:22,830 --> 00:22:26,420 Ehkä se oli korkea kirjeen, kuten tai alhainen kirjain Z. 678 00:22:26,420 --> 00:22:28,170 >> Joten kaikki on taas tässä järjestyksessä. 679 00:22:28,170 --> 00:22:29,800 Ja nyt haluan tehdä tätä. 680 00:22:29,800 --> 00:22:34,880 Katsotaanpa Tiedän, että olen kahdeksan numeroa täällä. 681 00:22:34,880 --> 00:22:37,410 Aion mennä eteenpäin ja vain tarkoituksella valitse 682 00:22:37,410 --> 00:22:38,520 pienin elementtejä. 683 00:22:38,520 --> 00:22:38,760 Oikea? 684 00:22:38,760 --> 00:22:39,801 Tämä tuntuu intuitiivinen liikaa. 685 00:22:39,801 --> 00:22:42,560 Miksi en löydä pienimmän elementti, laita se minne se kuuluu, 686 00:22:42,560 --> 00:22:45,280 sitten saada seuraavaksi pienin elementti, laittaa se mihin se kuuluu, ja vain toista. 687 00:22:45,280 --> 00:22:46,820 >> Koska intuitiivisesti, että pitäisi toimia myös. 688 00:22:46,820 --> 00:22:48,441 Niin neljä, se on aika pieni määrä. 689 00:22:48,441 --> 00:22:49,940 Aion muistaa, missä tämä on. 690 00:22:49,940 --> 00:22:50,523 Hetkinen. 691 00:22:50,523 --> 00:22:51,577 Kaksi on pienempi. 692 00:22:51,577 --> 00:22:53,910 Saanen nyt muista missä kaksi on, ja unohtaa neljä. 693 00:22:53,910 --> 00:22:55,050 Me käsitellä myöhemmin. 694 00:22:55,050 --> 00:22:56,460 Kuusi, en ole kiinnostunut. 695 00:22:56,460 --> 00:22:57,810 Kahdeksan, en ole kiinnostunut. 696 00:22:57,810 --> 00:22:59,780 Yksi on minun uusi pieni määrä. 697 00:22:59,780 --> 00:23:01,470 Joten aion muistaa missä yksi on. 698 00:23:01,470 --> 00:23:02,534 Kolme, ei kiinnosta. 699 00:23:02,534 --> 00:23:03,450 Seitsemän, ei kiinnosta. 700 00:23:03,450 --> 00:23:04,530 Viisi, ei kiinnosta. 701 00:23:04,530 --> 00:23:07,390 >> Joten putoamatta vaiheessa tänä vuonna, 702 00:23:07,390 --> 00:23:09,890 Aion napata numero one-- ja mikä oli nimesi uudelleen? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. MALAN: Annan. 705 00:23:11,220 --> 00:23:13,540 Ja jos voisi liittyä minua listan alkuun, 706 00:23:13,540 --> 00:23:14,870 Laitetaan minne kuulut. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- mikä on nimesi? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan on tiellä. 710 00:23:18,191 --> 00:23:23,490 Joten ennen Stefan ratkaisee tämän ongelma, mitä meidän pitäisi tehdä? 711 00:23:23,490 --> 00:23:25,412 Mitä teemme Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Yleisö: [äänetön]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Jotta voisimme tehdä sen. 715 00:23:28,850 --> 00:23:31,730 Voisimme tavallaan ottaa Stefan ja hänen neljä, ja vain laittaa se muuttuja 716 00:23:31,730 --> 00:23:33,530 ja pitää kiinni sitä jonkin verran aikaa, 717 00:23:33,530 --> 00:23:35,220 jolloin tilaa ykkönen. 718 00:23:35,220 --> 00:23:36,280 Ja se ei ole huono. 719 00:23:36,280 --> 00:23:39,270 Voisin ehdottaa, miksi ei me vain laittaa Stefan täällä? 720 00:23:39,270 --> 00:23:41,610 Miksi tämä voisi rikkoa yksi ideoita aloimme 721 00:23:41,610 --> 00:23:44,830 puhumme viimeisen kerran, viime viikolla? 722 00:23:44,830 --> 00:23:45,330 Joo? 723 00:23:45,330 --> 00:23:45,740 >> Yleisö: [äänetön]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Ei ole indeksiä varten se. 725 00:23:46,860 --> 00:23:49,735 Jos luulet tämän, todellakin, kuten array, tämä on kuin negatiivinen, 726 00:23:49,735 --> 00:23:52,900 joten ei ole muistia oikeastaan tässä jos tämä on todellakin joukko, 727 00:23:52,900 --> 00:23:55,090 kuten me julisti viime viikolla luento. 728 00:23:55,090 --> 00:23:56,250 Joten meidän ei pitäisi tehdä tätä. 729 00:23:56,250 --> 00:23:57,340 Saatamme tallentaa sen muuttujaan. 730 00:23:57,340 --> 00:23:57,820 >> Tai tiedätkö mitä? 731 00:23:57,820 --> 00:23:59,153 Kuulin joku muu ehdottaa sitä. 732 00:23:59,153 --> 00:24:01,020 Mitä muuta voisimme tehdä Stefan? 733 00:24:01,020 --> 00:24:03,770 Miksi emme vain häätää hänet ja laittaa hänet jossa ykkönen oli. 734 00:24:03,770 --> 00:24:05,170 Joten jos haluat mennä sinne. 735 00:24:05,170 --> 00:24:07,300 Ja itse asiassa tämä on melko hyvä ratkaisu. 736 00:24:07,300 --> 00:24:10,480 Nyt toisaalta, olen kiltti on tehty ongelman pahempi. 737 00:24:10,480 --> 00:24:13,650 Neljä on nyt kauempana josta se pitäisi olla. 738 00:24:13,650 --> 00:24:14,900 Sen pitäisi olla kohti tätä puolet. 739 00:24:14,900 --> 00:24:16,100 >> Mutta tiedätkö mitä? 740 00:24:16,100 --> 00:24:17,630 Se olisi voinut olla huonoa onnea. 741 00:24:17,630 --> 00:24:18,822 Ehkä numero kahdeksan oli täällä. 742 00:24:18,822 --> 00:24:20,530 Ja niin, ehkä olisimme saanut onnekas, 743 00:24:20,530 --> 00:24:22,460 ja työnsi kahdeksan lähemmäksi loppua. 744 00:24:22,460 --> 00:24:24,710 Joten loppujen lopuksi, se tavallaan kaikki keskiarvot ulos. 745 00:24:24,710 --> 00:24:26,085 Meidän ei tarvitse välittää neljä. 746 00:24:26,085 --> 00:24:29,400 Kaikki välitän juuri nyt on valitaan pienin elementti. 747 00:24:29,400 --> 00:24:32,030 >> Ja nyt, mitä aion do on unohtaa numero yksi 748 00:24:32,030 --> 00:24:35,160 pysyvästi, koska tiedän lista takanani on nyt järjestetty. 749 00:24:35,160 --> 00:24:36,720 Joten minun lista oli aiemmin koko kahdeksan. 750 00:24:36,720 --> 00:24:37,720 Nyt on koosta seitsemän. 751 00:24:37,720 --> 00:24:40,340 Joten minun ongelma on tulossa pienempi, vaikkakin lineaarisesti. 752 00:24:40,340 --> 00:24:43,022 Joten nyt, aion valita nykyinen pienin elementti, kaksi. 753 00:24:43,022 --> 00:24:46,520 Kuusi, kahdeksan, neljä, kolme, seitsemän, viisi. 754 00:24:46,520 --> 00:24:47,770 Se oli pienin elementti. 755 00:24:47,770 --> 00:24:49,416 Joten mitä olen menossa tekemään with-- mikä oli nimesi uudelleen? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. MALAN: Joseph? 758 00:24:50,085 --> 00:24:52,000 Aiomme jättää Joseph paikallaan. 759 00:24:52,000 --> 00:24:54,842 Nyt aion teeskennellä että nämä kaverit are-- hyvin, 760 00:24:54,842 --> 00:24:56,550 Tiedän, että nämä kaksi on jo järjestetty. 761 00:24:56,550 --> 00:24:58,424 Katsotaanpa nyt keskittyä Loput luettelon. 762 00:24:58,424 --> 00:25:00,080 Kuusi on nykyinen pienin. 763 00:25:00,080 --> 00:25:01,190 Kahdeksan on suurempi. 764 00:25:01,190 --> 00:25:02,970 Neljä on nyt nykyinen pienin. 765 00:25:02,970 --> 00:25:04,762 Kolme on nyt nykyinen pienin. 766 00:25:04,762 --> 00:25:07,720 Ja nyt, aion valita kolme, kuka is-- mikä on nimesi uudelleen? 767 00:25:07,720 --> 00:25:08,190 Serena: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, jos voisit napata numero ja swap with-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. MALAN: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Tule takaisin, ja olemme menossa vaihtaa nämä kaksi. 772 00:25:15,220 --> 00:25:17,360 Ja nyt, nyt laittaa tämä autopilotilla. 773 00:25:17,360 --> 00:25:21,589 Aion mennä ja jättää sen te Valitse seuraavaksi pienin elementtejä. 774 00:25:21,589 --> 00:25:22,380 Dun, Dun Dun Dun. 775 00:25:22,380 --> 00:25:24,560 Numero neljä, mitä pitäisi tehdä? 776 00:25:24,560 --> 00:25:26,261 Erinomainen. 777 00:25:26,261 --> 00:25:27,760 Nyt, aion tehdä toinen omille. 778 00:25:27,760 --> 00:25:28,590 Dun, Dun Dun Dun. 779 00:25:28,590 --> 00:25:31,465 Näen viisi on seuraavaksi pienin. 780 00:25:31,465 --> 00:25:32,840 Nyt aion ottaa toisen omille. 781 00:25:32,840 --> 00:25:33,631 Dun, Dun Dun Dun. 782 00:25:33,631 --> 00:25:34,880 Kuusi on pienin. 783 00:25:34,880 --> 00:25:35,520 Hyvä. 784 00:25:35,520 --> 00:25:36,585 Seitsemän on pienin. 785 00:25:36,585 --> 00:25:37,085 Ei muutosta. 786 00:25:37,085 --> 00:25:38,630 Kahdeksan on pienin. 787 00:25:38,630 --> 00:25:39,170 Tehty. 788 00:25:39,170 --> 00:25:43,900 >> Joten mitä olemme juuri tehneet iteratiivisesti valitaan yksi elementti toisensa jälkeen 789 00:25:43,900 --> 00:25:47,230 on toteuttaa jotain, että olemme menossa virallistaa niin valinta lajitella. 790 00:25:47,230 --> 00:25:49,120 Ja se on ehkä jopa yksinkertaisempaa selittää, 791 00:25:49,120 --> 00:25:51,310 että kirjaimellisesti kaikki mitä haluat tehdä, on vain pitää 792 00:25:51,310 --> 00:25:54,700 menee edestakaisin luetteloa valinnassa, seuraavaksi pienin elementti, 793 00:25:54,700 --> 00:25:55,720 kunnes olet valmis. 794 00:25:55,720 --> 00:25:58,650 >> Joten se on jopa helpompaa, ehkä intuitiivisesti, kuin viime. 795 00:25:58,650 --> 00:26:00,020 Kokeillaan yksi viimeinen. 796 00:26:00,020 --> 00:26:03,060 Jos te voisi palauttaa itse seuraaviin kannat 797 00:26:03,060 --> 00:26:08,600 viimeistä kertaa, katsotaanpa jos emme voi nyt virallistaa yksi muu lähestymistapa. 798 00:26:08,600 --> 00:26:12,857 Itse asiassa, olisi joku siellä haluavat ehdottaa 799 00:26:12,857 --> 00:26:14,440 Miten muuten voisimme edetä tässä? 800 00:26:14,440 --> 00:26:17,439 Ilman tossing ulos iskulauseita tai lajitella vastauksia, jotka ovat jo tiedossa, 801 00:26:17,439 --> 00:26:19,689 vain intuitiivisesti, mitä voisimme tehdä? 802 00:26:19,689 --> 00:26:21,635 >> Yleisö: [äänetön]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Joo. 804 00:26:22,510 --> 00:26:24,620 Joten ei hienoja intuitio siellä. 805 00:26:24,620 --> 00:26:28,020 Hyvät asiat näyttävät tapahtuvan toistaiseksi tietotekniikassa kun jaamme 806 00:26:28,020 --> 00:26:30,832 ja valloittaa ongelma jakamalla se puoliksi ja puolet ja puolet. 807 00:26:30,832 --> 00:26:32,540 Ja niin todellakin, me voisi alkaa tehdä niin. 808 00:26:32,540 --> 00:26:35,754 Ja itse asiassa, että tulee olemaan, me katso, yksi parhaita ratkaisuja vielä. 809 00:26:35,754 --> 00:26:37,420 Mutta katsotaanpa palata että ennen pitkää. 810 00:26:37,420 --> 00:26:40,500 Itse asiassa, aiomme tehdä että hieman myöhemmin tällä viikolla. 811 00:26:40,500 --> 00:26:42,180 Mitä muuta voisi teemme ratkaista tämän? 812 00:26:42,180 --> 00:26:44,647 Joten jokainen täällä on näennäisesti satunnaisessa järjestyksessä. 813 00:26:44,647 --> 00:26:45,230 Arvaa mitä? 814 00:26:45,230 --> 00:26:48,320 Eikä mennä edestakaisin, edestakaisin, edestakaisin 815 00:26:48,320 --> 00:26:50,624 joka kerta, tämä tuntuu Teen paljon kävelyä. 816 00:26:50,624 --> 00:26:52,790 Miksi en vain alkaa klo listan alkuun, 817 00:26:52,790 --> 00:26:54,960 ja vain laittaa neljä minne se kuuluu? 818 00:26:54,960 --> 00:26:59,680 Sallikaa minun olettaa tällä hetkellä, että lista on vain tämä ensimmäinen elementti. 819 00:26:59,680 --> 00:27:04,937 On neljä järjestetty tällä hetkellä, jos kaikki Välitän on kaikki täällä? 820 00:27:04,937 --> 00:27:06,520 Tämä on tavallaan triviaalisti totta, eikö? 821 00:27:06,520 --> 00:27:10,000 Kuten listan, joka sisältää yhden numeron, ja että numero neljä on ilmeisesti lajitellaan. 822 00:27:10,000 --> 00:27:13,070 >> Joten haluan vain määrätä että tämä lista lajitellaan. 823 00:27:13,070 --> 00:27:15,090 Mutta nyt minulla on loput tästä luettelosta. 824 00:27:15,090 --> 00:27:17,240 Joten nyt, I kohtaavat kaksi. 825 00:27:17,240 --> 00:27:21,690 Mistä kaksi ilmeisesti kuuluvat suhteen neljä? 826 00:27:21,690 --> 00:27:22,580 Ennen neljä. 827 00:27:22,580 --> 00:27:23,862 Mitä voin tehdä täällä? 828 00:27:23,862 --> 00:27:24,820 Mikä nimesi olikaan? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, jos voisit askel taaksepäin 831 00:27:26,030 --> 00:27:27,790 vain hetki puhelinnumerosi. 832 00:27:27,790 --> 00:27:31,130 Ja nyt, mitä pitäisi Stefan tehdä täällä? 833 00:27:31,130 --> 00:27:33,720 Katsotaanpa siirtää Stefan täällä. 834 00:27:33,720 --> 00:27:35,520 Ja nyt, anna Joseph tänne. 835 00:27:35,520 --> 00:27:39,660 Ja nyt, haluan väittää, että kaikki täällä lajitellaan. 836 00:27:39,660 --> 00:27:42,474 Joten, samanlainen tulos, mutta täysin eri lähestymistapaa. 837 00:27:42,474 --> 00:27:44,140 En ole edes tutkinut, mitä siellä. 838 00:27:44,140 --> 00:27:46,310 Minä vain pitää ottaen elementit koska he ojensi minulle, 839 00:27:46,310 --> 00:27:47,240 ja käsitellä niitä. 840 00:27:47,240 --> 00:27:48,330 >> Joten nyt, näen numero kuusi. 841 00:27:48,330 --> 00:27:51,110 Mistä numero kuusi kuuluu? 842 00:27:51,110 --> 00:27:53,250 Meillä on kaksi, neljä, kuusi. 843 00:27:53,250 --> 00:27:54,800 Tarkalleen missä hän on nyt. 844 00:27:54,800 --> 00:27:57,750 Joten jätä että yksin, ja nyt väittävät, että tämä osa luettelon 845 00:27:57,750 --> 00:27:58,772 on nyt järjestetty. 846 00:27:58,772 --> 00:28:01,230 Ja niin, tämä tuntuu pohjimmiltaan erilainen, että olen vain 847 00:28:01,230 --> 00:28:05,230 liikkuvat läpi listan täällä lineaarisesti, ja olen koskaan kaksinkertaistaa takaisin. 848 00:28:05,230 --> 00:28:05,730 Kyllä. 849 00:28:05,730 --> 00:28:06,230 Selvä. 850 00:28:06,230 --> 00:28:08,190 Niin kahdeksan, jossa sinä kuulut? 851 00:28:08,190 --> 00:28:08,730 Juuri täällä. 852 00:28:08,730 --> 00:28:09,310 Täydellinen. 853 00:28:09,310 --> 00:28:10,210 Joten nyt, yksi. 854 00:28:10,210 --> 00:28:10,900 O-ou. 855 00:28:10,900 --> 00:28:13,010 Tämä tuntuu se tulee kalliiksi. 856 00:28:13,010 --> 00:28:15,690 Nyt, edellisessä algoritmi, Minä vain vaihtoivat ihmisiä. 857 00:28:15,690 --> 00:28:18,648 Niin voisin laittaa hänet aina osoitteessa alussa, mutta sitten muutti Joseph. 858 00:28:18,648 --> 00:28:21,450 Mutta jos muutan Joosef, nyt mitä tulee olla väärässä? 859 00:28:21,450 --> 00:28:24,250 >> Nyt, olen tavallaan undone-- olen otetaan yksi askel eteenpäin ja sitten 860 00:28:24,250 --> 00:28:26,300 yksi askel taaksepäin, koska nyt Joseph olisi epäkunnossa. 861 00:28:26,300 --> 00:28:26,830 Joten tehdään tämä. 862 00:28:26,830 --> 00:28:29,150 Jos voisit ottaa numero yksi ja askel taaksepäin vain hetken. 863 00:28:29,150 --> 00:28:30,490 Miten voimme put-- mitä oli nimesi uudelleen? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan paikallaan? 866 00:28:32,610 --> 00:28:36,091 Mitä täytyy tapahtua suhteen kaksi, neljä, kuusi ja kahdeksan? 867 00:28:36,091 --> 00:28:37,570 He kaikki tarvitsevat siirtää. 868 00:28:37,570 --> 00:28:42,590 Joten jos kahdeksan haluaa siirtää ensin, sitten kuusi, sitten neljä, sitten kaksi. 869 00:28:42,590 --> 00:28:45,380 Ja sitten Annan, jos haluat haluavat tulla tänne, hyvä. 870 00:28:45,380 --> 00:28:47,760 Mutta täällä, olemme juuri Tällainen maksettu hinta 871 00:28:47,760 --> 00:28:49,510 on eri vaiheessa algoritmi. 872 00:28:49,510 --> 00:28:52,550 Kun viime aikaa valinta lajitella, ja jopa kuplalajittelu, 873 00:28:52,550 --> 00:28:54,700 Kävelen takaisin ja edestakaisin, edestakaisin, 874 00:28:54,700 --> 00:28:58,360 joka on varmasti laskemalla ajallisesti, ja kirjaimellisesti vaiheittain. 875 00:28:58,360 --> 00:29:00,660 >> Lisäyslajittelun, aluksi silmäyksellä, näyttää se 876 00:29:00,660 --> 00:29:05,150 Super fiksumpia, että olen vain hitaasti, vähitellen edistystä, 877 00:29:05,150 --> 00:29:07,120 mutta en aio tätä edestakaisin. 878 00:29:07,120 --> 00:29:09,410 Mutta jos joku on todellakin epäkunnossa, ilmoitus 879 00:29:09,410 --> 00:29:10,840 kaikki työ oli ihan pakko tehdä. 880 00:29:10,840 --> 00:29:14,750 Minulla oli siirtyä puoliskon vain tehdä tilaa ykkönen. 881 00:29:14,750 --> 00:29:16,790 Joten se on sama määrä Työn toistaiseksi se 882 00:29:16,790 --> 00:29:18,690 tuntuu, vain eri tyyppistä työtä. 883 00:29:18,690 --> 00:29:19,370 >> Jatketaan. 884 00:29:19,370 --> 00:29:22,657 Joten nyt me tiedämme, että jokainen yhdestä kahdeksan lajitellaan. 885 00:29:22,657 --> 00:29:23,740 Täällä minulla on numero kolme. 886 00:29:23,740 --> 00:29:25,864 Jos haluat poimia numero kolme, askel taaksepäin yksi. 887 00:29:25,864 --> 00:29:28,260 Ja mitä te tarvitse tehdä? 888 00:29:28,260 --> 00:29:28,760 Jep. 889 00:29:28,760 --> 00:29:33,070 Niin, että on toinen, kaksi, kolme vaihetta. 890 00:29:33,070 --> 00:29:36,010 Kolme aikayksikköinä että vain maksaa minua, joten kolme voivat nyt sovi. 891 00:29:36,010 --> 00:29:37,460 Lopuksi, seitsemän. 892 00:29:37,460 --> 00:29:39,730 >> Mennään eteenpäin ja on voit ottaa askel taaksepäin. 893 00:29:39,730 --> 00:29:42,780 Tämä on vain tulee maksamaan meille yhden yksikön aikaa, mutta se on OK. 894 00:29:42,780 --> 00:29:44,170 Ja nyt, viisi on menossa olla hieman kalliimpaa. 895 00:29:44,170 --> 00:29:45,340 Jos haluat askel taaksepäin. 896 00:29:45,340 --> 00:29:48,380 Meidän on edettävä kahdeksan, ja seitsemän, ja kuusi. 897 00:29:48,380 --> 00:29:50,749 Ja sitten kaikki on nyt järjestetty. 898 00:29:50,749 --> 00:29:52,290 Joten iso käsi meidän vapaaehtoisille täällä. 899 00:29:52,290 --> 00:29:53,554 Kiitos paljon. 900 00:29:53,554 --> 00:29:56,220 >> [APPLAUSE] 901 00:29:56,220 --> 00:29:56,860 >> Kiitos kaikille. 902 00:29:56,860 --> 00:29:57,520 Kiitos kaikille. 903 00:29:57,520 --> 00:30:02,940 Katsotaanpa nyt, kuinka kalliiksi kaikki tämä oli. 904 00:30:02,940 --> 00:30:06,210 Tarkastellaan ehkä Yksinkertaisin näistä, kuplalajittelu. 905 00:30:06,210 --> 00:30:09,950 Ja sanon yksinkertaisin, vain koska voit ratkaista sen ahnaasti vain hieman 906 00:30:09,950 --> 00:30:11,660 korjata pareittain ongelma. 907 00:30:11,660 --> 00:30:13,720 Korjaa pareittain ongelma täällä, uudestaan ​​ja uudestaan 908 00:30:13,720 --> 00:30:17,680 ja uudelleen, toistamalla niin monta kertaa kuin itse tarvitse. 909 00:30:17,680 --> 00:30:21,050 >> Joten käy ilmi, että jossa kuplalajittelu, hyvin, 910 00:30:21,050 --> 00:30:25,820 kuinka monta askelta minun täytyy ottaa ensikierron saman algoritmin? 911 00:30:25,820 --> 00:30:30,850 Saatan take-- nyt see-- yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän. 912 00:30:30,850 --> 00:30:32,190 Ja siellä on kahdeksan elementtejä täällä. 913 00:30:32,190 --> 00:30:35,280 Joten se on kuin n miinus 1 toimenpiteet saada listan alkuun 914 00:30:35,280 --> 00:30:36,380 loppuun luettelosta. 915 00:30:36,380 --> 00:30:41,350 >> Mutta valinta lajitella, muistaa, että olen valitsemalla elementit uudelleen ja uudelleen 916 00:30:41,350 --> 00:30:44,590 ja taas se on pienin, Laitan sen paikallaan, 917 00:30:44,590 --> 00:30:46,616 mutta sitten en ole looking takanani uudelleen. 918 00:30:46,616 --> 00:30:49,490 Niin mielestäni se on hieman selkeä sitten, että ensimmäinen kerta, voisin 919 00:30:49,490 --> 00:30:52,680 on otettava kaikki n miinus 1 vaiheet löytää pienin alkio. 920 00:30:52,680 --> 00:30:55,920 Sitten laitoin ne paikoilleen, ja minä häätää kuka oli täällä aiemmin. 921 00:30:55,920 --> 00:30:57,500 >> Mutta sitten ei tarvitse pitää tarkastella tätä elementtiä, 922 00:30:57,500 --> 00:30:59,040 koska tiedän, että se on jo pienin. 923 00:30:59,040 --> 00:31:01,581 Joten nyt, en voi katsoa vain seitsemän elementtejä, sitten kuusi elementtejä, 924 00:31:01,581 --> 00:31:03,290 sitten viisi elementtiä, sitten neljä osatekijää. 925 00:31:03,290 --> 00:31:06,900 Ja niin matemaattisesti, jos n on alkioiden lukumäärä tai numerot 926 00:31:06,900 --> 00:31:11,990 että aloitimme, voit kuvitella että tämä on sama kuin n-miinus 1, 927 00:31:11,990 --> 00:31:14,250 plus n miinus 2 askelta, plus n miinus 3 vaiheet, 928 00:31:14,250 --> 00:31:16,780 plus n miinus 4 askelmaa, kaikki alas vain yhden askeleen. 929 00:31:16,780 --> 00:31:18,160 Ja olen viimeinen henkilö. 930 00:31:18,160 --> 00:31:20,650 >> Ja jos muistaa, että paljon ja tilastot kirjoja tai matematiikka kirjoja 931 00:31:20,650 --> 00:31:24,730 on niitä kaavojen kovakantinen takaisin tai niiden edessä, 932 00:31:24,730 --> 00:31:27,690 käy ilmi, että tämä sarja voidaan ilmaista yksinkertaisemmin 933 00:31:27,690 --> 00:31:28,857 kuten n kertaa n miinus 1 yli 2. 934 00:31:28,857 --> 00:31:31,273 Ja se on hienoa, jos se ei ole eturintamassa mieltäsi. 935 00:31:31,273 --> 00:31:32,420 Mutta tämä on totta. 936 00:31:32,420 --> 00:31:34,449 Se on vain yksinkertaisempi tapa kirjoittaa se. 937 00:31:34,449 --> 00:31:36,240 Ja sitten jos luulet takaisin alakoulussa, 938 00:31:36,240 --> 00:31:38,698 kun vain aloittaa kertomalla asioita, tämä tietenkin, 939 00:31:38,698 --> 00:31:41,820 on vain n potenssiin miinus n jaettuna 2. 940 00:31:41,820 --> 00:31:44,772 Kaikki Olen tehnyt on laajentaa ilmaisuja siellä. 941 00:31:44,772 --> 00:31:46,730 Ja niin katsotaanpa kirjoittaa tämä hieman eri tavalla. 942 00:31:46,730 --> 00:31:49,780 Joka on n neliöidystä jaettuna 2 miinus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Joten jälleen, olen juuri sellainen soveltamisesta jotkut aritmeettinen säännöt siellä. 944 00:31:53,270 --> 00:31:57,140 Mutta huomaa nyt, että suurin termi tässä ilmaisua, niin sanoakseni, 945 00:31:57,140 --> 00:31:58,540 on, että n potenssiin. 946 00:31:58,540 --> 00:32:02,910 Joten kyllä, se on n potenssiin jaettuna 2, miinus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Mutta yleensä, jos n on olemaan iso arvo, 948 00:32:05,080 --> 00:32:08,740 Aion väittää n potenssiin tulee olemaan määräävä tekijä. 949 00:32:08,740 --> 00:32:10,490 Se on vain olemaan isompi avustaja 950 00:32:10,490 --> 00:32:12,877 ja useita vaiheita kuin n / 2. 951 00:32:12,877 --> 00:32:13,960 Joten mitä minä tarkoitan tällä? 952 00:32:13,960 --> 00:32:16,795 Kokeillaan yksinkertainen esimerkki, vaikka vaikka matematiikka saa hieman iso. 953 00:32:16,795 --> 00:32:20,210 >> Joten Oletetaan meillä oli 1.000.000 ihmistä lavalla tai 1000000 asiat 954 00:32:20,210 --> 00:32:21,320 että haluamme lajitella. 955 00:32:21,320 --> 00:32:23,730 Katsotaanpa plug miljoonaa osaksi juuri, että kaava 956 00:32:23,730 --> 00:32:27,230 kuinka monta askelta kestää yhteensä lajitella miljoona elementtejä käyttäen sanoa, 957 00:32:27,230 --> 00:32:28,560 valinta lajitella. 958 00:32:28,560 --> 00:32:30,760 >> Joten meillä olisi sama kaava kuin ennen. 959 00:32:30,760 --> 00:32:34,120 Olin plug miljoonaa, niin että saan miljoona neliöidystä jaettuna 2, 960 00:32:34,120 --> 00:32:35,990 miinus miljoona jaettuna 2. 961 00:32:35,990 --> 00:32:40,180 Jos en, että matematiikka etukäteen täällä, meillä on 500 miljardin 962 00:32:40,180 --> 00:32:47,460 miinus 500000, joka antaa meille 499999500000, 963 00:32:47,460 --> 00:32:49,270 joka on tosi iso. 964 00:32:49,270 --> 00:32:54,370 >> Itse asiassa, jos vertaa nyt 499000000000, 999000000, 965 00:32:54,370 --> 00:33:01,210 500000 vastaan ​​meidän alkuperäisestä arvosta, 500000000000, se on niin pirun lähellä. 966 00:33:01,210 --> 00:33:06,850 Oikea? n neliöidystä jaettuna 2 antaa us-- tai pikemminkin, n ruudutettu jaettuna 2 967 00:33:06,850 --> 00:33:08,370 antoi meille 500000000000. 968 00:33:08,370 --> 00:33:13,510 Se on tosi lähellä on 499999500000, 969 00:33:13,510 --> 00:33:17,970 toisin sanoen vähentämällä pois 500000, tai yleisemmin, vähentämällä pois 970 00:33:17,970 --> 00:33:20,010 n potenssiin, ei oikeastaan ​​iso juttu. 971 00:33:20,010 --> 00:33:22,490 N potenssiin tekee nämä numerot kasvavat todella nopeasti. 972 00:33:22,490 --> 00:33:25,790 >> Nyt, tämä on tärkeää vain sikäli kuten me, kuin tietotekniikan tutkijoita, 973 00:33:25,790 --> 00:33:29,350 yleensä aio välitä niin paljon noin vivahteita näiden kaavojen 974 00:33:29,350 --> 00:33:31,400 ja mitä täsmällisiä vastauksia ovat. 975 00:33:31,400 --> 00:33:33,390 Välitämme vain että, tiedätkö mitä? 976 00:33:33,390 --> 00:33:37,810 Lopussa päivän, tämä kaava on suuruusluokkaa n neliö. 977 00:33:37,810 --> 00:33:39,350 >> Kyllä, olemme jakamalla 2 siellä. 978 00:33:39,350 --> 00:33:41,360 Kyllä, olemme vähentämällä pois n miinus 2. 979 00:33:41,360 --> 00:33:46,860 Mutta lopussa päivän, aikavälin että todella satuttaa meitä ja maksaa meille 980 00:33:46,860 --> 00:33:48,995 runsaasti portaita on, että neliö aikavälillä. 981 00:33:48,995 --> 00:33:51,370 Ja niin mitä tietojenkäsittelytieteessä aikoo yleensä tehdä 982 00:33:51,370 --> 00:33:54,160 on sivuuttaa kaikki nämä pienempi asteen termit, 983 00:33:54,160 --> 00:33:56,900 ja katsokaa joka vaikuttaa eniten kustannuksia. 984 00:33:56,900 --> 00:34:00,530 >> Ja tämä on mukavaa, koska voimme nyt puhua paljon enemmän yleispätevyyttä 985 00:34:00,530 --> 00:34:02,470 noin algoritmeja, ja voi vertailla niitä. 986 00:34:02,470 --> 00:34:04,550 Ja se, että olen tällä O on tahallista. 987 00:34:04,550 --> 00:34:06,680 Kun sanon määräyksestä on, olen nimenomaan 988 00:34:06,680 --> 00:34:09,560 viittaa jotain sanottujen suurten O. ja Big O 989 00:34:09,560 --> 00:34:14,090 on merkintä, että tietokone tiedemies käyttää kuvaamaan 990 00:34:14,090 --> 00:34:16,710 yläraja jotain. 991 00:34:16,710 --> 00:34:21,150 >> Joten jos sanot että algoritmi on iso O n potenssiin, 992 00:34:21,150 --> 00:34:23,380 kuten ehdotin juuri hetki sitten, että välineet 993 00:34:23,380 --> 00:34:27,710 että mitä sen käynnissä aikaa tai sen tehokkuus, 994 00:34:27,710 --> 00:34:30,090 se ottaa tilauksen n potenssiin vaiheita. 995 00:34:30,090 --> 00:34:31,420 Ehkä enemmän, ehkä vähemmän. 996 00:34:31,420 --> 00:34:33,435 Mutta se on suuruusluokkaa n neliö. 997 00:34:33,435 --> 00:34:34,560 Ja se on yläraja. 998 00:34:34,560 --> 00:34:36,530 Se ei tule olemaan enemmän tuskallista kuin että. 999 00:34:36,530 --> 00:34:40,800 Se ei tule olemaan n kuutioitu, tai 2 ja n, tai jotain paljon suurempi. 1000 00:34:40,800 --> 00:34:43,800 Tämä on yläraja siitä mitä se kustannus on. 1001 00:34:43,800 --> 00:34:46,150 Niin sillä, katsotaanpa harkita vain muutamia esimerkkejä. 1002 00:34:46,150 --> 00:34:49,820 Ja tämä on vain rajallinen luettelo on hyvin yleinen käynnissä kertaa 1003 00:34:49,820 --> 00:34:52,870 algoritmeja, jotka on tarkoitus olla havainnollistavat joitakin asioita olemme 1004 00:34:52,870 --> 00:34:53,600 nähty jo. 1005 00:34:53,600 --> 00:34:58,060 >> Niin esimerkiksi, kun kyseessä on valinta lajitella, mitä olen väittäen täällä 1006 00:34:58,060 --> 00:35:02,250 on, että valinta lajitella n käynnissä aika on suuruusluokkaa n neliö. 1007 00:35:02,250 --> 00:35:06,260 Pahimmassa tapauksessa aion olla koko joukko satunnaisia ​​numeroita täällä. 1008 00:35:06,260 --> 00:35:08,600 Ja kuten näimme matemaattisesti, jos pidän kävely 1009 00:35:08,600 --> 00:35:11,310 luetteloa, kautta luettelo, valitaan seuraavaksi pienin 1010 00:35:11,310 --> 00:35:14,410 elementti uudelleen ja uudelleen, jos en oikeastaan ​​kirjoittaa kaikki vaiheet 1011 00:35:14,410 --> 00:35:18,750 Otan kuten ehdotin formulaically ennen, se on luokkaa n potenssiin 1012 00:35:18,750 --> 00:35:20,370 vaiheet että otan. 1013 00:35:20,370 --> 00:35:24,520 >> Ja käy ilmi, että kupla lajitella ja lisäyslajittelun 1014 00:35:24,520 --> 00:35:27,370 ovat yhtä hitaita pahimmassa tapauksessa. 1015 00:35:27,370 --> 00:35:32,040 Mieti esimerkiksi lisäyslajittelun, viimeinen algoritmi käsittelimme, 1016 00:35:32,040 --> 00:35:35,500 joka oli meitä katsomaan elementti, ja aseta se mihin se kuuluu. 1017 00:35:35,500 --> 00:35:38,720 Ja sitten me katsoimme seuraavaan elementtiin, ja lisätään se mihin se kuuluu. 1018 00:35:38,720 --> 00:35:40,990 >> Joten harkita paras mahdollinen skenaario. 1019 00:35:40,990 --> 00:35:45,590 Oletetaan Olin minun vapaaehtoisille riviin kirjaimellisesti näin, yksi kautta kahdeksan, 1020 00:35:45,590 --> 00:35:47,440 jo järjestetty. 1021 00:35:47,440 --> 00:35:51,300 Kuinka monta askelta on lisäyslajittelun aikoo ryhtyä lajitella kahdeksan ihmistä, 1022 00:35:51,300 --> 00:35:55,640 jos he saapuvat lavalla näköisenä tämä? 1023 00:35:55,640 --> 00:35:57,410 >> Kahdeksan ihmistä jo järjestetty. 1024 00:35:57,410 --> 00:35:58,760 Ja käytän lisäyslajittelun. 1025 00:35:58,760 --> 00:36:02,180 Että viimeinen algoritmeja. 1026 00:36:02,180 --> 00:36:03,640 No, katsotaanpa uudelleen säätää todella nopeasti. 1027 00:36:03,640 --> 00:36:05,504 Joten jos aloitan täällä, näen yksi. 1028 00:36:05,504 --> 00:36:06,420 Jos ei yksi kuuluu? 1029 00:36:06,420 --> 00:36:07,730 Se kuuluu täällä. 1030 00:36:07,730 --> 00:36:08,330 Näen kaksi. 1031 00:36:08,330 --> 00:36:09,660 Missä kaksi kuuluu? 1032 00:36:09,660 --> 00:36:10,260 Juuri täällä. 1033 00:36:10,260 --> 00:36:10,900 Näen kolme. 1034 00:36:10,900 --> 00:36:11,920 Mistä kolme kuuluu? 1035 00:36:11,920 --> 00:36:12,480 Juuri täällä. 1036 00:36:12,480 --> 00:36:13,100 >> Näen neljä. 1037 00:36:13,100 --> 00:36:13,600 Juuri täällä. 1038 00:36:13,600 --> 00:36:15,660 Viisi, kuusi, seitsemän, kahdeksan. 1039 00:36:15,660 --> 00:36:17,320 Ei ole mitään syytä toistaa itseäni. 1040 00:36:17,320 --> 00:36:21,260 Ja niin, kuinka monta askelta on, että mitä n? 1041 00:36:21,260 --> 00:36:23,870 Se on järjestyksessä n vaiheet, eikö? n miinus 1. 1042 00:36:23,870 --> 00:36:27,567 Mutta otin lineaarinen numero vaiheita, ja nyt olen valmis. 1043 00:36:27,567 --> 00:36:28,900 Niin, että parhaassa tapauksessa, vaikka. 1044 00:36:28,900 --> 00:36:29,983 Entä pahimmassa tapauksessa? 1045 00:36:29,983 --> 00:36:32,730 Mitkä kahdeksan oli siellä, ja seitsemän oli siellä, 1046 00:36:32,730 --> 00:36:35,840 ja yksi ja kaksi oli täällä, joten että luettelo oli todella päinvastainen? 1047 00:36:35,840 --> 00:36:38,300 >> No, mitä tapahtuu todella jos tämä on numero? 1048 00:36:38,300 --> 00:36:41,300 Ja teemme vain pari esimerkkiä. 1049 00:36:41,300 --> 00:36:49,300 Mitä jos todellakin numero kahdeksan on täällä, ja number-- oho. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Joten mitä jos todellakin numero kahdeksan on aina tänne, 1052 00:36:56,430 --> 00:36:57,790 ja olen käyttäen lisäyslajittelun? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Väitän tällä hetkellä se on paikallaan. 1055 00:37:00,280 --> 00:37:03,152 Mutta nyt, seven-- mistä seitsemän mennä? 1056 00:37:03,152 --> 00:37:04,360 Tietenkin, se menee tänne. 1057 00:37:04,360 --> 00:37:06,760 Joten minun täytyy siirtää kahdeksan yli yhteen paikkaan. 1058 00:37:06,760 --> 00:37:08,554 Nyt kuusi, jossa se kulkee? 1059 00:37:08,554 --> 00:37:09,220 No, hyvä on. 1060 00:37:09,220 --> 00:37:13,150 Nyt minun täytyy siirtää kahdeksan yli paikka, ja seitsemän yli paikka, 1061 00:37:13,150 --> 00:37:14,440 ja sitten minä plop alas kuusi. 1062 00:37:14,440 --> 00:37:16,870 >> Joten ensimmäistä kertaa, se maksaa minulle yksi askel korjata asioita, 1063 00:37:16,870 --> 00:37:18,570 sitten se maksoi minulle kaksi askelta korjata asioita. 1064 00:37:18,570 --> 00:37:20,370 Kuinka monta askelta on se vie korjata 1065 00:37:20,370 --> 00:37:22,720 asiat laittaa viisi oikeassa paikassa? 1066 00:37:22,720 --> 00:37:23,340 Kolme. 1067 00:37:23,340 --> 00:37:29,520 Koska nyt minun täytyy siirtää yksi, kaksi, kolme. 1068 00:37:29,520 --> 00:37:32,430 Kuinka monta askelta se aikoo ottaa laittaa neljä oikeassa paikassa? 1069 00:37:32,430 --> 00:37:36,040 4 + 5 + 6, ja 7. 1070 00:37:36,040 --> 00:37:40,260 >> Ja niin se on matemaattisesti identtinen mitä me kuvattiin valinta lajitella. 1071 00:37:40,260 --> 00:37:42,130 Meillä on tämä sarja Se on vain kasvussa. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, tai päinvastoin, 7 ja 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 lisää jopa nykypäivän tarkoituksiin luokkaa n neliö. 1074 00:37:52,610 --> 00:37:57,640 >> Haluan siis määrätään myös, että kuplalajittelu on myös n potenssiin. 1075 00:37:57,640 --> 00:38:01,340 Nimittäin kuplalajittelu, kukin kun menen läpi listan, 1076 00:38:01,340 --> 00:38:03,100 Otan suunnilleen kuinka monta askelta? 1077 00:38:03,100 --> 00:38:06,260 Joka kerta olen kirjaimellisesti kävellä sieltä siellä? 1078 00:38:06,260 --> 00:38:07,960 Noin n vaiheet. 1079 00:38:07,960 --> 00:38:12,650 Mutta kuinka monta kertaa pitää I täytyy mennä läpi listan? 1080 00:38:12,650 --> 00:38:13,920 >> No, karkeasti n aikaa. 1081 00:38:13,920 --> 00:38:15,680 Ehkä n miinus 1, mutta karkeasti n kertaa. 1082 00:38:15,680 --> 00:38:16,430 No, miksi? 1083 00:38:16,430 --> 00:38:19,560 No, kuplalajittelu, jos aloitamme kuplalajittelu, 1084 00:38:19,560 --> 00:38:23,570 kanssa alalta pahin mahdollinen tilanne, joka taas on täysin 1085 00:38:23,570 --> 00:38:25,550 taaksepäin, mitä tulee tapahtumaan? 1086 00:38:25,550 --> 00:38:28,830 Käyn läpi listan, ja numero yksi kuuluu aina tuolla. 1087 00:38:28,830 --> 00:38:33,280 >> Mutta kuplalajittelu, kuinka pitkälle ei yksi siirtyä minun ensimmäinen läpi listan? 1088 00:38:33,280 --> 00:38:36,620 Kuinka paljon pisteitä hän saa lähemmäksi oikeaan paikkaan? 1089 00:38:36,620 --> 00:38:37,240 Vain yksi. 1090 00:38:37,240 --> 00:38:40,281 Joten jos sellainen syy kautta, joka kerta kautta tämä algoritmi, 1091 00:38:40,281 --> 00:38:41,880 Daavidin ottaen karkeasti n toimiin. 1092 00:38:41,880 --> 00:38:44,940 Mutta kuinka monta vaihetta luetteloa on se 1093 00:38:44,940 --> 00:38:49,060 vie yhdestä kupla vasemmalle minne se kuuluu? 1094 00:38:49,060 --> 00:38:51,840 >> Hänen täytyy liikkua kuten, n tilat tällä tavalla. 1095 00:38:51,840 --> 00:38:57,960 Joten tehdä lajittelu luettelon, Minun täytyy kävellä edestakaisin n kertaa. 1096 00:38:57,960 --> 00:39:01,540 Ja joka kerta, olen katsot n elementtiä. 1097 00:39:01,540 --> 00:39:05,410 Niin n asioita n kertaa järjestys n neliö. 1098 00:39:05,410 --> 00:39:07,220 >> Nyt näemme joissakin ja shortsit että 1099 00:39:07,220 --> 00:39:10,440 on upotettu CS50 seuraava ongelma set, toinen lähestymistapa näitä, 1100 00:39:10,440 --> 00:39:13,490 mutta nyt haluan vain harkita joitakin muita käynnissä aikoina, 1101 00:39:13,490 --> 00:39:16,840 varsinkin jos lajittelu niistä ottaa vähän aikaa uppoavat. 1102 00:39:16,840 --> 00:39:21,790 Mikä algoritmi olemme nähneet jo joka vie suuruusluokkaa n vaiheet? 1103 00:39:21,790 --> 00:39:27,560 >> Mitä pitäisi lineaarinen numero vaiheita, jotka olemme nähneet tähän mennessä? 1104 00:39:27,560 --> 00:39:29,350 Mikä tuo on? 1105 00:39:29,350 --> 00:39:30,480 Puhelinluettelo haku. 1106 00:39:30,480 --> 00:39:31,390 Ensimmäinen algoritmi. 1107 00:39:31,390 --> 00:39:31,560 Oikea? 1108 00:39:31,560 --> 00:39:33,650 Missä olemme lineaarisesti etsivät Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Todellakin. 1110 00:39:34,150 --> 00:39:37,180 Viikosta nolla, kun aloin kääntämällä yhden sivun kerrallaan, 1111 00:39:37,180 --> 00:39:40,095 ja olen jopa sanoi, että se oli eräänlainen lineaarisen tunne algoritmia, 1112 00:39:40,095 --> 00:39:42,720 ja meillä oli, että kuva aluksella suora punainen viiva 1113 00:39:42,720 --> 00:39:44,678 ja suora keltainen linja, ne olivat todellakin 1114 00:39:44,678 --> 00:39:46,810 algoritmeja, jotka ovat Big O n. 1115 00:39:46,810 --> 00:39:50,680 >> Koska löytää Mike Smith puhelimessa kirja n sivuja, pahimmassa tapauksessa, 1116 00:39:50,680 --> 00:39:52,422 Ottaa minut n toimiin. 1117 00:39:52,422 --> 00:39:53,630 Entä kun läsnäolo? 1118 00:39:53,630 --> 00:39:55,790 Yksi kaksi kolme neljä viisi kuusi. 1119 00:39:55,790 --> 00:39:59,420 Mikä käyntiaika tämän algoritmi ottaa läsnäolo? 1120 00:39:59,420 --> 00:40:03,070 Big O n, koska teoriassa I on kohta kaikki huoneessa. 1121 00:40:03,070 --> 00:40:05,861 >> Nyt kun syrjään, entä muut optimointi viikosta nolla? 1122 00:40:05,861 --> 00:40:08,117 Kaksi, neljä, kuusi, kahdeksan, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Tietojenkäsittelytieteessä olisi ymmärtää, odota minuutti, 1124 00:40:10,200 --> 00:40:12,320 joka on luokkaa n jaettuna kahdessa vaiheessa. 1125 00:40:12,320 --> 00:40:12,820 Oikea? 1126 00:40:12,820 --> 00:40:14,444 Koska mulla kaksi ihmistä kerrallaan. 1127 00:40:14,444 --> 00:40:17,015 Mutta aiomme sivuuttaa ne alemman asteen termit, 1128 00:40:17,015 --> 00:40:19,140 ja olemme juuri menossa heittää pois jaa 2, 1129 00:40:19,140 --> 00:40:21,830 ja vain sanoa, iso O n että algoritmi samoin. 1130 00:40:21,830 --> 00:40:22,760 >> Entä tämä? 1131 00:40:22,760 --> 00:40:26,170 Me ohittaa joitakin näistä, mutta mitä oli algoritmi, joka on log-n? 1132 00:40:26,170 --> 00:40:29,900 Se kesti noin log n vaiheet? 1133 00:40:29,900 --> 00:40:30,870 Hajota ja hallitse. 1134 00:40:30,870 --> 00:40:31,369 Aivan. 1135 00:40:31,369 --> 00:40:33,900 Kuten puhelinluettelon esimerkki viikko nolla ja aiemmin tänään, 1136 00:40:33,900 --> 00:40:36,191 jossa jaoimme ongelma uudestaan ​​ja uudestaan ​​ja uudestaan. 1137 00:40:36,191 --> 00:40:39,070 Me veti sen taululle viikolla nolla kaareva vihreä linja, 1138 00:40:39,070 --> 00:40:41,460 ja sanoimme, että päivä oli logaritminen algoritmi. 1139 00:40:41,460 --> 00:40:44,970 >> Ja todellakin, useita vaiheita se vie suorittaa hajoita ja hallitse, 1140 00:40:44,970 --> 00:40:48,610 tai binäärihakupuu kuin aloitamme kutsuen sitä, kuten puhelinluettelossa, 1141 00:40:48,610 --> 00:40:50,680 on luokkaa tukin ja vaiheita. 1142 00:40:50,680 --> 00:40:52,470 Ja tämä on hieman outo yksi. 1143 00:40:52,470 --> 00:40:54,910 >> Mitä ottaa yhden askeleen, tai erityisemmin 1144 00:40:54,910 --> 00:40:56,240 jatkuva useita vaiheita? 1145 00:40:56,240 --> 00:40:58,865 Ehkä se on kaksi, ehkä se kolme, mutta tietokone tiedemies juuri 1146 00:40:58,865 --> 00:41:01,423 yksinkertaistaa sitä iso O 1, jotkut jatkuva useita vaiheita. 1147 00:41:01,423 --> 00:41:04,256 Mikä jotain voisi tehdä, että vie jatkuva useita toimia? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Mikä ajoaika taputus? 1150 00:41:10,930 --> 00:41:11,920 Jatkuva aika. 1151 00:41:11,920 --> 00:41:12,420 Oikea? 1152 00:41:12,420 --> 00:41:15,490 Kuten, mitä ajoaika tee mitään, joka vie vain yksi 1153 00:41:15,490 --> 00:41:18,570 toiminta, kuten tulostaa F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Se voidaan sanoa olevan vakio ajan, ellei vähemmän nurkassa tapauksessa tulostaa F, 1155 00:41:24,110 --> 00:41:28,260 Mikä voisi käyntiaika tulostaa F todella? 1156 00:41:28,260 --> 00:41:28,790 Ja miksi? 1157 00:41:28,790 --> 00:41:30,550 Mikä on n mitta tässä tapauksessa? 1158 00:41:30,550 --> 00:41:32,251 >> Yleisö: [äänetön]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Aivan. 1160 00:41:33,250 --> 00:41:34,900 Merkkien määrä haluamme tulostaa. 1161 00:41:34,900 --> 00:41:36,191 Joten on erittäin tilannekohtaisia. 1162 00:41:36,191 --> 00:41:39,910 Tänään olemme keskittyneet erän kirjaimia ja numeroita tässä taululle. 1163 00:41:39,910 --> 00:41:43,540 Mutta se voi olla merkkejä todellinen merkkijono. 1164 00:41:43,540 --> 00:41:46,420 Joten se kääntyy pois on toinen toimenpide, joka alkaa välittämistä, 1165 00:41:46,420 --> 00:41:48,530 ja se on päinvastainen iso O, niin sanoakseni. 1166 00:41:48,530 --> 00:41:50,120 >> Se on omega merkintää. 1167 00:41:50,120 --> 00:41:53,380 Kun taas iso O tarkoittaa mitä, yläraja teidän aika? 1168 00:41:53,380 --> 00:41:55,580 Maksimaalisesti, kuinka paljon aikaa ehkä jotain kestää? 1169 00:41:55,580 --> 00:41:59,250 Omega-- anteeksi tämä pitää tulossa up-- on vastakohta, että 1170 00:41:59,250 --> 00:42:02,960 jolloin se on alaraja on aikaa jotain saattaa kestää. 1171 00:42:02,960 --> 00:42:10,480 >> So. esimerkiksi, mitä algoritmia joka vie aina n potenssiin vaiheet? 1172 00:42:10,480 --> 00:42:15,600 No, yksi algoritmien olemme nähneet tänään, itse asiassa, voi olla, että yhtä hyvin. 1173 00:42:15,600 --> 00:42:16,720 Valinta lajitella. 1174 00:42:16,720 --> 00:42:18,270 Valinta sort on melko typerää. 1175 00:42:18,270 --> 00:42:21,760 Vaikka algorithm-- pahoillani, jopa jos jono on jo järjestetty, 1176 00:42:21,760 --> 00:42:24,150 valinta lajitella aikoo pitää kävelevän lista 1177 00:42:24,150 --> 00:42:28,907 varmista, että se on pienin elementti uudestaan ​​ja uudestaan ​​ja uudestaan. 1178 00:42:28,907 --> 00:42:31,740 Ja vaikka ihmisille yleisö tietää, että hetkinen, 1179 00:42:31,740 --> 00:42:33,948 olet jo läpäissyt pienin alkio, tietokone 1180 00:42:33,948 --> 00:42:37,300 ei tiedä, että ennen kuin se näyttää kaikki läpi listan. 1181 00:42:37,300 --> 00:42:40,240 Vastaavasti, alaraja, joka voi myös otettava huomioon 1182 00:42:40,240 --> 00:42:42,000 voisi olla lineaarinen aika. 1183 00:42:42,000 --> 00:42:48,260 >> Kuinka kauan kestää lajitella n elementtejä paras 1184 00:42:48,260 --> 00:42:52,420 tapauksessa käyttäen jotain kuplalajittelu? 1185 00:42:52,420 --> 00:42:54,280 Oletetaan lista on jo järjestetty. 1186 00:42:54,280 --> 00:42:56,696 Sanoimme kuplalajittelu ottaa järjestys n neliö vaiheita. 1187 00:42:56,696 --> 00:42:59,640 Mutta mitä jos se on jo järjestetty? 1188 00:42:59,640 --> 00:43:02,310 Mitä jos huomaat jälkeen yksi läpi array 1189 00:43:02,310 --> 00:43:03,540 että olet tehnyt mitään swap? 1190 00:43:03,540 --> 00:43:05,970 Tarvitseeko sinun pitää tehdä enemmän kulkee? 1191 00:43:05,970 --> 00:43:06,470 >> Ei. 1192 00:43:06,470 --> 00:43:10,340 Joten alaraja kuplalajittelu voidaan sanoa olevan lineaarinen. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 Ja voimme tarkastella toiset näistä samoin. 1195 00:43:14,450 --> 00:43:17,990 Joten ottaa vilkaista juuri visualisointi täällä 1196 00:43:17,990 --> 00:43:20,790 miten nämä erottuvat. 1197 00:43:20,790 --> 00:43:24,592 Aion mennä alas täällä tähän sivu, joka on saatavilla C50: n verkkosivuilla, 1198 00:43:24,592 --> 00:43:27,550 mutta se on tuskaa saada työ, koska se käyttää tekniikkaa kutsutaan 1199 00:43:27,550 --> 00:43:30,560 Java-sovelmat, joka on pitkälti tueta näinä päivinä, 1200 00:43:30,560 --> 00:43:32,730 ainakin Chrome ja tietyt muut. 1201 00:43:32,730 --> 00:43:37,070 >> Ja anna minun mennä eteenpäin ja nopeuttaa tätä ylös ja selittää, mitä on tekeillä. 1202 00:43:37,070 --> 00:43:40,840 Tämä on osoitus kupla lajitella, ensimmäinen algoritmi tarkastelimme. 1203 00:43:40,840 --> 00:43:43,950 Ja se on visualisointi, että kukin Näiden baareja on luku. 1204 00:43:43,950 --> 00:43:45,710 Isompi baari, isompi numero. 1205 00:43:45,710 --> 00:43:47,520 Pienempi palkki, pienempi numero. 1206 00:43:47,520 --> 00:43:50,353 Ja mitä näet visuaalisesti, jopa vaikka tämä on menossa huippunopea, 1207 00:43:50,353 --> 00:43:53,699 on, että punainen palkki on kuin minä, kävely edestakaisin vahvistamisesta ongelmia. 1208 00:43:53,699 --> 00:43:56,740 Voit nähdä, että isompi elementit todellakin kuplii oikealle, 1209 00:43:56,740 --> 00:43:59,650 ja pienemmät elementit ovat kuplii vasemmalle. 1210 00:43:59,650 --> 00:44:01,870 Ja tänne, jos me todella lähemmin, 1211 00:44:01,870 --> 00:44:04,330 voimme todella luottaa määrä vertailuja ja swap 1212 00:44:04,330 --> 00:44:05,350 joita tehdään. 1213 00:44:05,350 --> 00:44:07,360 >> Mutta sen sijaan, katsotaanpa toisessa algoritmi 1214 00:44:07,360 --> 00:44:11,240 me katsoimme aiemmin meidän vapaaehtoisia, valinta lajitella. 1215 00:44:11,240 --> 00:44:13,500 Visuaalisesti se on hyvin erilainen vaikutus. 1216 00:44:13,500 --> 00:44:16,820 Mutta se on, jälleen, hyvin intuitiivinen, vuonna että pidämme valitaan seuraavaksi pienin 1217 00:44:16,820 --> 00:44:18,660 elementti, ja saimme hieman onnekas. 1218 00:44:18,660 --> 00:44:20,110 Joka tuntui pohjimmiltaan nopeampaa. 1219 00:44:20,110 --> 00:44:22,840 Mutta jos me juoksi tätä uudelleen ja uudelleen ja jälleen paljon panoksia, 1220 00:44:22,840 --> 00:44:26,680 näkisimme, että se on todellakin edelleen iso O n neliö. 1221 00:44:26,680 --> 00:44:29,920 >> Tehdään yksi viimeinen täällä, lisäyslajittelun, 1222 00:44:29,920 --> 00:44:33,180 joka oli kolmas algoritmi me katsoimme, ja muistuttaa 1223 00:44:33,180 --> 00:44:36,700 että tämä yksi käsittelee elementtejä se kohtaa niitä, 1224 00:44:36,700 --> 00:44:39,290 mutta sitten se ehkä vuorossa asioita yli tehdä tilaa, 1225 00:44:39,290 --> 00:44:41,660 lisäämällä elementtejä jos ne kuuluvat. 1226 00:44:41,660 --> 00:44:45,330 >> Ja tämäkin päätyy antamaan lopputulokseen. Nyt kaikki kolme näistä 1227 00:44:45,330 --> 00:44:46,490 tuntui melko nopeasti. 1228 00:44:46,490 --> 00:44:48,740 Ja todellakin, juoksin heitä klo aika hyvä leike. 1229 00:44:48,740 --> 00:44:52,510 Mutta pohjimmiltaan, he kaikki aika kamala, olla rehellinen. 1230 00:44:52,510 --> 00:44:56,960 Kaikki nämä algoritmit toistaiseksi että nousun sisään Big O n potenssiin 1231 00:44:56,960 --> 00:44:59,270 ottaa melko vähän aika juosta lopulta. 1232 00:44:59,270 --> 00:45:01,920 >> Ja todellakin, voimme nähdä ja tuntea tämä lopuksi 1233 00:45:01,920 --> 00:45:04,090 jos vedän ylös tämä kolmas ja viimeinen demo. 1234 00:45:04,090 --> 00:45:05,840 Tämä on toinen visualisointi että menee 1235 00:45:05,840 --> 00:45:08,500 näyttää kuplalajittelu vasemmalla, valinta lajitella keskellä, 1236 00:45:08,500 --> 00:45:13,410 ja jotain, koska yksi käytetyt herättää aiemmin ehdottanut, 1237 00:45:13,410 --> 00:45:15,020 yhdistää lajitella oikealla. 1238 00:45:15,020 --> 00:45:16,937 Hajota ja hallitse strategia oikealla. 1239 00:45:16,937 --> 00:45:19,520 Ja se on itse asiassa mitä olemme menossa katsomaan keskiviikkona. 1240 00:45:19,520 --> 00:45:21,990 Mutta katsotaanpa aikaa nämä rinnakkain. 1241 00:45:21,990 --> 00:45:26,765 Se on suunnilleen sama määrä elementtejä, kaikki käynnissä samaan aikaan. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Kuplalajittelu vs valinta lajitella vs Yhdistämisen lajitella. 1244 00:45:34,440 --> 00:45:36,760 >> Nyt he kaikki käynnissä teoriassa samalla. 1245 00:45:36,760 --> 00:45:39,830 CPU on käynnissä samalla nopeudella, mutta sinä 1246 00:45:39,830 --> 00:45:44,014 voi tuntea kuinka tylsää tämä on hyvin nopeasti tulossa, 1247 00:45:44,014 --> 00:45:45,930 ja kuinka nopeasti, kun me pistää vähän viikko 1248 00:45:45,930 --> 00:45:49,330 nolla n algoritmeja voidaan me nopeuttaa asioita. 1249 00:45:49,330 --> 00:45:51,760 >> Ja nyt Katsotaanpa vertailla nämä yhdessä viime muodossa. 1250 00:45:51,760 --> 00:45:55,710 Aion mennä eteenpäin että CS50 verkkosivuilla, jossa 1251 00:45:55,710 --> 00:45:59,020 meillä on tämä viimeinen lenkki tänään, jos joku internetissä 1252 00:45:59,020 --> 00:46:03,960 ystävällisesti koota video, joka kaappaa mitä eri lajittelu 1253 00:46:03,960 --> 00:46:07,510 algoritmeja kuulostaa. 1254 00:46:07,510 --> 00:46:09,577 Tämä on lisäyslajittelun. 1255 00:46:09,577 --> 00:46:12,072 >> [Piippaa] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Jolloin olet soveltamalla taajuus perustuu korkeus bar bar. 1258 00:46:16,850 --> 00:46:19,826 Tämä on kuplalajittelu. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped piippaa] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Tulossa seuraavaksi is-- tulevina seuraavaksi is-- valinta lajitella, 1262 00:46:45,774 --> 00:46:48,820 jossa jälleen, olemme valitsemalla seuraavaksi pienin elementti, 1263 00:46:48,820 --> 00:46:51,820 ja voimme nähdä sen kasvaa vasemmalta oikealle. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Yhdistä lajitella, meidän voittaja toistaiseksi tänään. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Huomaa, miten se jakaa asioita osaksi [äänetön] puoli ja neljäsosaa. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome lajitella, jotka emme ole puhui, ja luo visuaalisesti 1270 00:47:21,660 --> 00:47:24,450 ja audally hieman eri muotoisia ja ääni. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Going edestakaisin, puhdistaa asioita. 1273 00:47:30,160 --> 00:47:32,230 Tutustu myös Kekojärjestäminen tämän kaveri verkkosivuilla. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Ja se on siinä. 1276 00:47:36,810 --> 00:47:38,210 Tulemme näkemään ensi kerralla. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing ja musiikki] 1279 00:47:48,334 --> 00:50:24,839