1 00:00:00,000 --> 00:00:11,100 >> [Musiikki soi] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Okei. 3 00:00:11,490 --> 00:00:12,170 Joten tervetuloa takaisin. 4 00:00:12,170 --> 00:00:15,180 Tämä on CS50, ja on viikon lopussa kolme. 5 00:00:15,180 --> 00:00:17,770 >> Joten muistaa aiemmin useita viikkoja, olemme viettää melko vähän 6 00:00:17,770 --> 00:00:20,820 aikaa C, ohjelmointi, syntaksi. 7 00:00:20,820 --> 00:00:24,680 Ja se on aivan normaalia, jos olet vielä kamppailee Harjoitus 2, on 8 00:00:24,680 --> 00:00:25,950 hakkaa päätäsi seinään. 9 00:00:25,950 --> 00:00:28,310 Se on arvoituksellinen näköinen virheilmoituksia ja bugeja että 10 00:00:28,310 --> 00:00:29,220 ei aivan jahtaamaan. 11 00:00:29,220 --> 00:00:32,310 Koska varma, että vain Muutaman viikon kuluttua voit muistella 12 00:00:32,310 --> 00:00:35,930 asioita, kuten Caesar ja [? V-genair,?] ehkä jopa Crack, ja 13 00:00:35,930 --> 00:00:40,050 ymmärtää, miten pitkälle olet tullut lyhyen ajan kuluessa. 14 00:00:40,050 --> 00:00:43,670 Joten jos se yhtään lohduttaa, roikkua siellä nyt. 15 00:00:43,670 --> 00:00:46,610 >> Tänään kuitenkin alamme siirtyminen asioita korkeammalla tasolla. 16 00:00:46,610 --> 00:00:49,820 Ja alamme itsestään selvänä, että te tiedätte, miten ohjelma, tai 17 00:00:49,820 --> 00:00:52,090 ainakin alkaa että viihtyvyyteen. 18 00:00:52,090 --> 00:00:56,520 Ja alamme pohtia, miten voimme edetä ohjelmien suunnitteluun lisää 19 00:00:56,520 --> 00:00:57,440 tehokkaasti. 20 00:00:57,440 --> 00:01:01,090 Miten voimme edetä optimoimalla tehokkuuden algoritmit, ja 21 00:01:01,090 --> 00:01:03,110 yleensä ratkaista enemmän mielenkiintoisia ongelmia. 22 00:01:03,110 --> 00:01:06,850 Ja alkaa itsestään selvänä, että jos haluaisimme, voisimme koodata mihin tahansa 23 00:01:06,850 --> 00:01:08,350 esimerkkien meillä on mielessä. 24 00:01:08,350 --> 00:01:11,430 Joten tänään, emme kosketa näppäimistöä minkäänlaiseen koodia. 25 00:01:11,430 --> 00:01:15,150 Se tulee olemaan paljon korkeampi, ja lopulta noin ongelmanratkaisuun. 26 00:01:15,150 --> 00:01:20,490 >> Joten päästä tähän pisteeseen, haluaisin ehdottaa että seuraavat seitsemän 27 00:01:20,490 --> 00:01:24,290 suorakaide edustaa seitsemän ovien takana jotka ovat koko joukko 28 00:01:24,290 --> 00:01:26,340 numerot, joista on numero 50. 29 00:01:26,340 --> 00:01:30,470 Saanen projisoida tämä tästä näytön myös täällä. 30 00:01:30,470 --> 00:01:36,770 Ja ehdottaa, että meidän vapaaehtoisen auttaa löytämään minua numeron edessä 31 00:01:36,770 --> 00:01:38,140 Internet täällä nähdä. 32 00:01:38,140 --> 00:01:40,755 Tule ylös, loistokunnossa. 33 00:01:40,755 --> 00:01:43,050 Selvä. 34 00:01:43,050 --> 00:01:43,930 Mikä sinun nimesi on? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [äänetön] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Anteeksi? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Okei, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Hauska tavata. 41 00:01:47,630 --> 00:01:48,370 Tule ylös. 42 00:01:48,370 --> 00:01:52,430 Joten nämä tässä ovat seitsemän ovea, ja mitä Haluaisin sinun tekevän meille täällä, 43 00:01:52,430 --> 00:01:56,560 edessä kaikki luokkatoverit, on löytää meidät numero 50. 44 00:01:56,560 --> 00:02:00,860 Voit löytää useita, voit kurkistaa jokin näistä ovet yksinkertaisesti koskettamalla 45 00:02:00,860 --> 00:02:03,030 yhdellä ovet, ja se paljastaa sen numero. 46 00:02:03,030 --> 00:02:06,080 Ja katsotaanpa kuinka nopeasti Löydät meidät numero 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Hienosti tehty. 54 00:02:17,350 --> 00:02:18,040 Selvä. 55 00:02:18,040 --> 00:02:19,906 Aplodit Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [APPLAUSE] 57 00:02:21,530 --> 00:02:22,320 >> Selvä. 58 00:02:22,320 --> 00:02:25,254 Joten mikä oli strategian löytää numero 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Tuota, ajattelin ehkä jos - 60 00:02:27,222 --> 00:02:27,714 [Äänetön] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Anna se yksi toinen. 63 00:02:29,630 --> 00:02:32,420 Joten oli teidän strategia löytää numero 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Olen siis vain alkaa alkaa nähdä, mitä ensimmäinen numero 65 00:02:34,760 --> 00:02:38,590 oli, ja sitten ajattelin, ehkä jos he lajitellaan, minä vain pitää 66 00:02:38,590 --> 00:02:39,970 napauttamalla ylempänä? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 Ja näytämme löytäneen että on kyse. 69 00:02:42,910 --> 00:02:45,670 Vaikka nyt Taitat kerrokset vain vähän, ja haluat mennä 70 00:02:45,670 --> 00:02:47,640 eteenpäin ja paljastaa muiden ovien olet voinut valita? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Voi, rakas. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Joten olen vain onnekas. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Sait onnekas. 76 00:02:55,270 --> 00:02:55,710 Selvä. 77 00:02:55,710 --> 00:02:56,795 Joten ei paha. 78 00:02:56,795 --> 00:02:58,750 Mutta se on mielenkiintoista oivalluksia, eikö? 79 00:02:58,750 --> 00:03:01,870 Jos oletetaan, ja teit saat, todellakin hieman onnekas siellä. 80 00:03:01,870 --> 00:03:05,350 Mutta jos oletetaan, että luvut olivat lajitellaan, voit olla täsmällisempi 81 00:03:05,350 --> 00:03:08,750 siitä, miten se vaikuttaa käytöstäsi? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Joten jos ne lajitellaan, I Ajattelin pienimmästä isoimpaan. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Tai jos tämä päätyi todella iso, sitten suurimmasta pienimpään. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Joten suurimmasta pienimpään, tai pienimmästä isoimpaan. 87 00:03:18,170 --> 00:03:21,990 Mutta haluan ehdottaa, kai oli mennyt epäonninen, ja olettaa, että ne 88 00:03:21,990 --> 00:03:26,840 ei, itse asiassa, lajitellaan, kuinka moni ne ovet ehkä sinulla on ollut kurkistaa 89 00:03:26,840 --> 00:03:28,590 jäljessä, että pahimmassa tapauksessa? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Kaikki. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Kaikki. 92 00:03:30,420 --> 00:03:31,740 Joten yleistää, että n. 93 00:03:31,740 --> 00:03:34,790 Siellä sattuu olemaan 7, mutta katsotaanpa lisää yleisesti sanoa siellä n ovet 94 00:03:34,790 --> 00:03:35,650 näyttö tästä. 95 00:03:35,650 --> 00:03:40,110 Joten pahimmassa tapauksessa olisit katsoa taakse 7 ovien tai n ovet. 96 00:03:40,110 --> 00:03:44,140 Ja niin tämä todella on, se on vähän onnea tänään, mutta se on todella lineaarinen 97 00:03:44,140 --> 00:03:46,440 algoritmi lajittelee, vaikka olivat eräänlainen ohita ympärille. 98 00:03:46,440 --> 00:03:47,080 Onko tämä reilua? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Joo. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: No, anna minun nähdä, jos Strategian muutokset jos muutan meitä 101 00:03:50,000 --> 00:03:52,190 meidän toinen esimerkki täällä 7 eri ovet. 102 00:03:52,190 --> 00:03:55,240 Samat numerot, mutta tämä kun ne lajitellaan. 103 00:03:55,240 --> 00:03:58,350 Minkä strategian täällä tulee olemaan, yrittää laittaa järkesi, mitä 104 00:03:58,350 --> 00:03:59,310 muut numerot olivat - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - aikaisemmin? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Aloitetaan ensimmäisen kanssa. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Okei. 109 00:04:03,540 --> 00:04:05,190 Aloita ensimmäinen. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Nyt jos olet menossa, ja miksi? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 on todella pieni. 113 00:04:10,040 --> 00:04:12,500 Joten jos he tavallaan ehkä pienin suurimpaan, sen pitäisi 114 00:04:12,500 --> 00:04:13,290 olla kaksi kertaa, ja -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Katsotaan, mikä luulet? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Kokeile viimeinen. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Erittäin hienosti tehty. 120 00:04:20,880 --> 00:04:21,860 Selvä. 121 00:04:21,860 --> 00:04:23,010 >> [APPLAUSE] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Joten olet juuri tekemässä tätä hirvittävän, koska olet 124 00:04:26,790 --> 00:04:27,700 tekee sen hyvin. 125 00:04:27,700 --> 00:04:31,150 Joka jättää meidät pysty tehdä tiettyjä kohtia. 126 00:04:31,150 --> 00:04:32,565 Joten yrittää heittää takaisin tänne. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Erittäin hyvin tehty kuitenkin. 129 00:04:35,980 --> 00:04:39,060 Joten olet aloittanut alussa, näit, että se oli 4, sitten 130 00:04:39,060 --> 00:04:40,240 muutti loppuun. 131 00:04:40,240 --> 00:04:42,320 Mutta oletetaan, et onnekas siellä, ja kai 50 132 00:04:42,320 --> 00:04:42,890 oli jossain muualla. 133 00:04:42,890 --> 00:04:46,190 Mitä kolmas vaihe on? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Mene takaisin alkuun. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Mene takaisin alkuun. 136 00:04:48,320 --> 00:04:51,320 OK, niin olisit koskettanut tämä ovi, joka oli 8. 137 00:04:51,320 --> 00:04:51,660 Selvä. 138 00:04:51,660 --> 00:04:52,650 Joten se ei ole 50. 139 00:04:52,650 --> 00:04:55,380 Missä olet tutkinut seuraavaksi? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Jos en tietävät lajitellaan. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Oikea. 142 00:04:57,005 --> 00:04:58,490 No, jos et tiedä ne on järjestetty - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Voi, ei tiedä, joo. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - mutta et ole tietää, missä 50 oli vielä? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Jatka vain. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Okei. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Jatkakaa. 149 00:05:03,800 --> 00:05:05,270 OK, että voin työskennellä. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Nyt, jos olet vain menossa pitämään menossa, mikä on sinun 152 00:05:07,210 --> 00:05:09,680 algoritmi taantunut peräytyminen. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: lineaarinen -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: Se on eräänlainen lineaarinen. 155 00:05:11,820 --> 00:05:13,480 Mutta haluan ehdottaa, anna Laitan paikan päällä. 156 00:05:13,480 --> 00:05:14,900 Saanen päivität sivun. 157 00:05:14,900 --> 00:05:17,120 Sama numero, sama järjestely, Sama ovet. 158 00:05:17,120 --> 00:05:21,350 Mutta muistelen, että ensimmäinen päivä luokassa, kun me repäisi puhelinluettelon 159 00:05:21,350 --> 00:05:25,480 puolet, tavallaan, ja mikä oli Strategiamme on? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Aloita keskellä. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Niin alkaa keskellä. 163 00:05:27,610 --> 00:05:28,790 Joten mene eteenpäin ja simuloida sitä. 164 00:05:28,790 --> 00:05:30,720 Aloita keskeltä paljastaa, että ovi. 165 00:05:30,720 --> 00:05:31,660 Joten numero 16. 166 00:05:31,660 --> 00:05:35,290 Joten mikä olisi vahva kaveri tehnyt, joka repi puhelinluettelon kahtia, 167 00:05:35,290 --> 00:05:38,450 päästä seuraavalle arvaus? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Mene tällä puolen. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: Ja miksi oikealle? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Jos ne tavallaan pienin suurimpaan, sitten 50 olisi 171 00:05:43,900 --> 00:05:44,720 tuossa lopussa. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Hyvä. 173 00:05:44,920 --> 00:05:45,390 Täysin kohtuullinen. 174 00:05:45,390 --> 00:05:48,380 Joten kuten puhelinluettelossa, menet oikeutta eikä vasemmalle, mutta tässä 175 00:05:48,380 --> 00:05:49,500 on avain takeaway. 176 00:05:49,500 --> 00:05:53,930 Nyt voit heittää pois tai repiä irti, puolet tämän ongelman, jolloin et 177 00:05:53,930 --> 00:05:55,970 7-ovet, mutta oikeastaan ​​vain 3. 178 00:05:55,970 --> 00:05:57,870 Mikä on noin puolet Ongelman laajuutta. 179 00:05:57,870 --> 00:05:58,350 Selvä. 180 00:05:58,350 --> 00:06:01,890 Joten nyt, mitä olisi tehdä, kun menet oikealle? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Eli 16 on edelleen melko pieni, suhteessa 50, joten ehkä yritän, 182 00:06:05,870 --> 00:06:06,700 kuten tämä. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Okei. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Okei, joten nyt mikä on sinun vaisto kertoo sinulle? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Voin heittää pois tämä ja sitten vain - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Hyvä, voit heittää pois vasen puoli siellä. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - valitse tämä. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: Ja oikea. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Joo. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Joten vaikka se on vaikeaa nähdä ehkä kun on vain 193 00:06:17,820 --> 00:06:21,320 7 ovet, ajattele nyt, johdonmukaisuus 194 00:06:21,320 --> 00:06:22,620 algoritmi juuri sovellettu. 195 00:06:22,620 --> 00:06:24,510 Edellisessä tapauksessa teit onnekas, mikä oli hienoa. 196 00:06:24,510 --> 00:06:26,540 Mutta et käytä heuristista, Sanoisin. 197 00:06:26,540 --> 00:06:29,150 Käytit tavallaan vaistosi, ja tietäen se lajitellaan, jos ihan 198 00:06:29,150 --> 00:06:31,600 pieni alussa, luonnollisesti, olemme täytyy mennä enemmän oikealle. 199 00:06:31,600 --> 00:06:34,990 Mutta jossain mielessä, sinulla onnekas, koska ehkä tämä oli numero 100, 200 00:06:34,990 --> 00:06:36,220 ja ehkä 50 oli keskellä. 201 00:06:36,220 --> 00:06:37,910 Ehkä 50 oli vielä täällä. 202 00:06:37,910 --> 00:06:40,960 >> Mutta mitä teit hieman eri tavalla tällä kertaa oli, teit sama asia 203 00:06:40,960 --> 00:06:42,150 uudelleen ja uudelleen. 204 00:06:42,150 --> 00:06:45,310 Ja väitän, että mitä vain ei tosin vaikuttaa puhelimen 205 00:06:45,310 --> 00:06:48,100 kirjaesimerkkiin, on jotain paljon enemmän algoritmi, ja paljon 206 00:06:48,100 --> 00:06:49,930 yhtä erityistä cased. 207 00:06:49,930 --> 00:06:51,620 Paljon vähemmän vaistomainen. 208 00:06:51,620 --> 00:06:57,160 Joten loppujen lopuksi, miten kuvaat tehokkuutta 209 00:06:57,160 --> 00:07:00,530 Ensimmäinen algoritmi, missä meni vasemmalta oikealle, vs. 210 00:07:00,530 --> 00:07:03,430 Toinen algoritmi täällä? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Tämä olisi kuin, ehkä puolittaa tai jopa enemmän, joo. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, ehkä jopa enemmän. 213 00:07:07,320 --> 00:07:10,150 Katsotaanpa työntää hieman vaikeampi siitä. 214 00:07:10,150 --> 00:07:13,030 Mitä todella, jos jatkamme tätä logiikka, me varmasti puolittui 215 00:07:13,030 --> 00:07:15,830 käyntiaika tämän toisen algoritmin heittämällä pois puolet 216 00:07:15,830 --> 00:07:18,470 numeroita, mutta mitä teemme seuraavaksi iteraatio, kun Jennifer paljasti 217 00:07:18,470 --> 00:07:20,615 toinen numero? 218 00:07:20,615 --> 00:07:22,830 >> Puolitimme numerot jälleen ovensa. 219 00:07:22,830 --> 00:07:25,270 Ja mitä sitten teimme sen jälkeen, jos oli enemmän ovia pelata? 220 00:07:25,270 --> 00:07:27,520 Olisimme puolittaa ne ja uudelleen, ja uudestaan, ja uudestaan. 221 00:07:27,520 --> 00:07:30,420 Ja tämä oli aivan kuten te kaikki seisomaan klo ensimmäisellä viikolla 222 00:07:30,420 --> 00:07:33,000 luokka, puoli olet istuen, puoli teistä istuen, puoli olet 223 00:07:33,000 --> 00:07:35,440 istuen, kunnes yksinäinen sielu seisoi. 224 00:07:35,440 --> 00:07:39,050 Ja sanoimme, että ajoaika että useita vaiheita kesti oli 225 00:07:39,050 --> 00:07:40,430 suuruusluokkaa mitä? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [äänetön] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Eli logaritmi 2 n, tai vain yksinkertaisemmin, kirjaudu n. 228 00:07:43,970 --> 00:07:45,060 Joten jotain logaritminen. 229 00:07:45,060 --> 00:07:48,380 Ja kuvaaja ei ollut suora viiva että juuri huonommaksi, se oli 230 00:07:48,380 --> 00:07:52,490 tämä mielenkiintoinen käyrä, joka ei saada niin huono ajan. 231 00:07:52,490 --> 00:07:53,910 Joten pitää tätä ajatusta. 232 00:07:53,910 --> 00:07:54,690 Katsotaanpa kiittää Jennifer. 233 00:07:54,690 --> 00:07:56,150 Kiitos niin paljon tulossa ylös. 234 00:07:56,150 --> 00:07:57,400 Ja, yhden sekunnin. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Ei Kirjoituspöydän lamput tänään, mutta me ei ole CS50 stressi pallot. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Jee. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Okei, tässä. 239 00:08:04,410 --> 00:08:06,545 Kiitos aiheutuu stressi täällä. 240 00:08:06,545 --> 00:08:07,350 Selvä. 241 00:08:07,350 --> 00:08:10,620 Katsotaanpa, jos emme voi nyt muodollistamiseksi hieman. 242 00:08:10,620 --> 00:08:14,820 Joten jälleen, mitä teimme oli pohjimmiltaan sama asia kuin teimme 243 00:08:14,820 --> 00:08:16,660 että ensimmäisellä viikolla. 244 00:08:16,660 --> 00:08:23,780 Mutta sen sijaan päättyvät vain lineaarinen algoritmi, jota on kuvattu 245 00:08:23,780 --> 00:08:27,210 aiemmin kuin tämä suora viiva, siitä, että jos laitamme yksi ovi 246 00:08:27,210 --> 00:08:29,610 näytölle ja Jennifer olisi täytynyt katsoa, ​​mahdollisesti, 247 00:08:29,610 --> 00:08:30,600 takana yksi ovi. 248 00:08:30,600 --> 00:08:33,490 Jos laitamme kaksi ovea, hän olisi näyttää takana kaksi ovea. 249 00:08:33,490 --> 00:08:35,990 >> Ja niin, oli tämä lineaarinen suhde koon 250 00:08:35,990 --> 00:08:39,059 ongelma, eli x-akselin, ja aikaa kuluu 251 00:08:39,059 --> 00:08:40,440 ratkaista y-. 252 00:08:40,440 --> 00:08:43,330 Mutta kuva olin viittaamatta aiemmin oli tämä vihreä viiva. 253 00:08:43,330 --> 00:08:45,970 Green tarkoituksella, koska se vain tuntui paremmalta. 254 00:08:45,970 --> 00:08:49,790 Teoriassa algoritmin, kun me teimme sen kanssa puhelinluettelosta, kun me teimme sen 255 00:08:49,790 --> 00:08:52,420 teidän kanssa laskenta toisiaan, ja Toisessa tapauksessa, kun Jennifer vain 256 00:08:52,420 --> 00:08:55,250 teki sen täällä, se oli tavallaan perustaltaan paremmin. 257 00:08:55,250 --> 00:08:57,180 Koska se ei ollut vain kaksi kertaa niin nopeasti. 258 00:08:57,180 --> 00:08:58,870 Se ei ollut edes neljä kertaa niin nopeasti. 259 00:08:58,870 --> 00:09:03,290 Se oli täysin riippuvainen siitä, mitä koko panos oli, kuinka monta 260 00:09:03,290 --> 00:09:05,220 toimiin se lopulta kesti. 261 00:09:05,220 --> 00:09:08,040 >> Ja niin tämä yksinkertainen ajatus, että me kaikki otimme itsestäänselvyytenä kanssa puhelinluettelosta, 262 00:09:08,040 --> 00:09:10,200 voidaan samalla tavoin soveltaa jotain tällaista. 263 00:09:10,200 --> 00:09:12,380 Ja tämä voisi olla rennosti tunnetaan, niin saatat 264 00:09:12,380 --> 00:09:13,940 kuvitella, hajoita ja hallitse. 265 00:09:13,940 --> 00:09:16,390 Ei toisin mitä teimme, tietenkin, kanssa puhelinluettelosta. 266 00:09:16,390 --> 00:09:18,300 >> Mutta pseudokoodit muistaa, oli tämä. 267 00:09:18,300 --> 00:09:21,800 Joten emme tee tätä uudelleen, mutta muistuttaa että ensimmäisellä viikolla, me kaikki nousi 268 00:09:21,800 --> 00:09:25,140 ja sitten puolet istahti, puolet istahti, puolet istahti. 269 00:09:25,140 --> 00:09:29,280 Tämä algoritmi toteutettiin hieman huijaaminen tavalla, että se 270 00:09:29,280 --> 00:09:32,870 ei ollut vain yksi minua laskenta, pohjimmiltaan tehokkaammin. 271 00:09:32,870 --> 00:09:35,830 Siinä tapauksessa, olin hyödyntäen toissijaisena luonnonvarana. 272 00:09:35,830 --> 00:09:39,470 Lajittele, useita suorittimia, useita aivot, useita älykkäitä ihmisiä 273 00:09:39,470 --> 00:09:42,740 huone auttoivat minua saada jotain lineaarinen jotain 274 00:09:42,740 --> 00:09:45,190 logaritminen, jostakin punaisesta jotain vihreää. 275 00:09:45,190 --> 00:09:48,650 >> Mutta tässä tapauksessa, Jennifer voi yksin pohjimmiltaan parannella 276 00:09:48,650 --> 00:09:52,370 suorituskyky hänen ensimmäinen algoritmi, uudelleen, vain ajatella vähän vaikeampaa. 277 00:09:52,370 --> 00:09:56,650 Ja nyt, kun on aika toteuttaa nämä asiat, mietitään 278 00:09:56,650 --> 00:10:00,670 mitä riviä koodia voit kirjoittaa niin että voit toistaa niitä uudelleen, ja 279 00:10:00,670 --> 00:10:03,350 uudestaan, ja uudestaan, tavallaan vuonna looping tavalla. 280 00:10:03,350 --> 00:10:06,370 Koska et aio olla ylellisyyttä, kuten Jennifer teki aluksi, että 281 00:10:06,370 --> 00:10:10,460 vain koko joukko jossittelua ja sanoa, hmm, jos tämä ensimmäinen numero on 4, 282 00:10:10,460 --> 00:10:11,800 haluan hypätä aina loppuun. 283 00:10:11,800 --> 00:10:14,180 Ooh, jos määrä on liian suuri, haluan liikkua mielivaltaisesti takaisin 284 00:10:14,180 --> 00:10:15,220 toiseen osaan. 285 00:10:15,220 --> 00:10:18,210 Huomaat, että se tulee olemaan paljon vaikeampaa virallistaa mitä me ihmiset 286 00:10:18,210 --> 00:10:21,270 itsestäänselvyytenä erittäin kohtuullinen heuristiikka, mutta tietokone on vain 287 00:10:21,270 --> 00:10:23,260 tekee mitä kerrot sen tehdä. 288 00:10:23,260 --> 00:10:25,280 >> Nyt tämä on erittäin mielenkiintoinen seurauksia. 289 00:10:25,280 --> 00:10:29,950 Tämä kuvaaja on tavallaan tarkoitus tavallaan hukuttaa visuaalisesti, mutta huomaa, jos 290 00:10:29,950 --> 00:10:32,230 on suora viiva tässä kuvaaja? 291 00:10:32,230 --> 00:10:35,330 Missä on lineaarinen kuvaaja jota me kutsumme n? 292 00:10:35,330 --> 00:10:37,580 No, se on tavallaan pohjaa kohti Kuvan, eikö? 293 00:10:37,580 --> 00:10:40,500 Joten kaikki olemme tehneet on olemme tavallaan zoomataan ulos x-akselin ja 294 00:10:40,500 --> 00:10:44,780 y-akseli yrittää saada tunteen siitä, mitä muita käyrät näyttävät. 295 00:10:44,780 --> 00:10:47,760 >> Ja erityispiirteet matemaattisten ilmaisuja tänään ei niin väliä 296 00:10:47,760 --> 00:10:52,440 paljon, mutta huomaa, että siellä on paljon algoritmeja, jotka ovat paljon huonommat kuin 297 00:10:52,440 --> 00:10:53,470 jotain, joka on lineaarinen. 298 00:10:53,470 --> 00:10:55,410 Itse asiassa n kuutioitu näyttää pahalta. 299 00:10:55,410 --> 00:10:58,400 2 n näyttää pahalta. n potenssiin näyttää pahalta. 300 00:10:58,400 --> 00:11:01,630 Ja näemme, mitä joidenkin saattaa olla todellisuudessa tänään. 301 00:11:01,630 --> 00:11:05,430 Ja log n ei tunnu niin pahalta, mutta parempi n on logaritmi 2 n. 302 00:11:05,430 --> 00:11:08,080 Mutta te tiedätte, se olisi ollut vielä ihmeellisempää, jos Jennifer, tai jos, 303 00:11:08,080 --> 00:11:12,910 että ensimmäisellä viikolla, oli keksittävä jotain, joka on log log n. 304 00:11:12,910 --> 00:11:15,880 >> Eli toisin sanoen, on tämä koko erilaisia ​​mahdollisia ratkaisuja 305 00:11:15,880 --> 00:11:18,570 ongelmia, mutta siinäkin, ilmoitus mitä tulee tapahtumaan. 306 00:11:18,570 --> 00:11:22,910 Kun minä loitontaa, mikä näistä käyrät tulee olemaan ehdoton 307 00:11:22,910 --> 00:11:26,630 Pahin niistä ruudulla nyt? 308 00:11:26,630 --> 00:11:28,680 Joten n kuutioitu näyttää aika nyt huono. 309 00:11:28,680 --> 00:11:32,470 Mutta jos me loitontaa ja nähdä enemmän x ja y-akseli, joka tulee 310 00:11:32,470 --> 00:11:34,550 hallitsevat lopulta? 311 00:11:34,550 --> 00:11:37,120 Joten se todella osoittautuu, että 2 n, ja voit selvittää tämän vain 312 00:11:37,120 --> 00:11:39,990 kytkemällä jotkut yhä suuria numerot, ja näet, että 2 313 00:11:39,990 --> 00:11:42,070 n todellakin saa isompi paljon nopeammin. 314 00:11:42,070 --> 00:11:45,530 Jos me todella loitontaa, 2 n algoritmi aivan perseestä. 315 00:11:45,530 --> 00:11:48,170 Siis tämä vie melko vähän aikaa 316 00:11:48,170 --> 00:11:49,460 tietokone vaihtuvuus kautta. 317 00:11:49,460 --> 00:11:52,500 >> Mutta näet ajan, erityisesti tulevaisuuden ongelma sarjaa ja jopa 318 00:11:52,500 --> 00:11:55,600 opinnäytetyöt, on tietosi set saa suuret, okei? 319 00:11:55,600 --> 00:11:58,300 Jopa ensimmäinen versio Facebook, kuin joukko ystäviä, ja 320 00:11:58,300 --> 00:12:01,840 rekisteröityneiden käyttäjien saivat suuret, voit lajitella puhelimen sen ja 321 00:12:01,840 --> 00:12:05,530 toteuttaa jotain lineaarista hakua, tai hyvin yksinkertainen lajittelu 322 00:12:05,530 --> 00:12:07,030 algoritmi, kuten näemme tänään. 323 00:12:07,030 --> 00:12:09,280 Sinun täytyy alkaa ajatella kovemmin ja vaikeampi näistä ongelmista. 324 00:12:09,280 --> 00:12:12,070 Ja tyyppisiä ongelmia paikoissa, kuten Facebook ja Google ja Microsoft, 325 00:12:12,070 --> 00:12:16,350 ja muut työtä on juuri nämä tavallaan iso tietojen kysymyksistä on 326 00:12:16,350 --> 00:12:18,530 yhä näinä päivinä. 327 00:12:18,530 --> 00:12:18,900 >> Selvä. 328 00:12:18,900 --> 00:12:23,800 Joten Jennifer menestys, että toinen algoritmi, rehellisesti, hän teki hämmästyttävän 329 00:12:23,800 --> 00:12:26,110 hyvin ensimmäisen kerran, mutta katsotaanpa kirjoittaa sitä onnea, jotta me 330 00:12:26,110 --> 00:12:27,000 voi tehdä tässä vaiheessa. 331 00:12:27,000 --> 00:12:30,970 Toisessa tapauksessa hän velkarahalla algoritmi, joka toistuu uudestaan ​​ja 332 00:12:30,970 --> 00:12:34,670 uudelleen, mutta hän otti itsestäänselvyytenä tiettyjä oletukseen, että annoimme 333 00:12:34,670 --> 00:12:39,370 häntä, mutta hän hyödyntää joitakin yksityiskohtia toisen kerran, että hän ei ole 334 00:12:39,370 --> 00:12:39,840 ensimmäisen kerran. 335 00:12:39,840 --> 00:12:41,800 Joka oli mitä? 336 00:12:41,800 --> 00:12:43,050 >> Tämä lista on lajiteltu. 337 00:12:43,050 --> 00:12:46,350 Joten kun luettelo on lajiteltu, me väittävät, että Jennifer pystyi tekemään 338 00:12:46,350 --> 00:12:47,480 pohjimmiltaan paremmin. 339 00:12:47,480 --> 00:12:51,450 7 ovet, kyllä, ei ole niin kiinnostavaa, mutta kai se olemme 7000000 ovet. 340 00:12:51,450 --> 00:12:54,080 Log n on ehdottomasti menossa tehdä paljon, paljon 341 00:12:54,080 --> 00:12:55,610 nopeammin pitkällä aikavälillä. 342 00:12:55,610 --> 00:12:58,880 Mutta hän piti olla ovet lajitellaan häntä. 343 00:12:58,880 --> 00:13:02,320 Nyt otin vapauden tehdä se etukäteen tietokoneen näytöllä 344 00:13:02,320 --> 00:13:05,160 täällä, mutta olettaa, että Jennifer täytyi tehdä itse? 345 00:13:05,160 --> 00:13:10,120 Oletetaan, että ovet kyseessä edustettuina tiedot tietokantaan tai 346 00:13:10,120 --> 00:13:14,260 ystävät rekisteröity Facebook, tai kaikkia verkkosivuja Internetissä, jotka 347 00:13:14,260 --> 00:13:16,880 eri verkkosivustoja ehkä indeksoida tai etsi yli. 348 00:13:16,880 --> 00:13:20,940 >> Oletetaan, että olet juuri ollut raakadatan asettaa ja se jäi sinulle, tai 349 00:13:20,940 --> 00:13:23,010 Jennifer tehdä lajittelemalla? 350 00:13:23,010 --> 00:13:26,950 Se pikemminkin edellyttää, että me vastaamme kysymys, hyvin, kuinka paljon aikaa 351 00:13:26,950 --> 00:13:31,080 olisi ottanut Jennifer tai jopa minua, lajitella nämä numerot etukäteen, jotta 352 00:13:31,080 --> 00:13:32,680 että hän voisi hyödyntää sitä? 353 00:13:32,680 --> 00:13:32,880 Oikea? 354 00:13:32,880 --> 00:13:36,620 Koska vaikutuksia, on tietenkin jos se vie minut jonkin aikaa lajitella 355 00:13:36,620 --> 00:13:40,800 numerot, jotka helkutti kiinnostaa, että olet löytyy useita, kuten 50 niin nopeasti, 356 00:13:40,800 --> 00:13:44,850 kuten Jennifer tapauksessa, jos yli hukkua määrä kokonaisaika 357 00:13:44,850 --> 00:13:46,920 kesti lajittelemalla asioita etukäteen? 358 00:13:46,920 --> 00:13:49,320 >> Katsotaanpa, jos emme voi maalaa kuva täällä. 359 00:13:49,320 --> 00:13:51,370 Minulla on koko joukko enemmän stressiä pallot, jos se auttaa 360 00:13:51,370 --> 00:13:52,270 murtaa jään tänne. 361 00:13:52,270 --> 00:13:55,690 Ja jos et mielessä, me tarvitsevat seitsemän vapaaehtoinen - 362 00:13:55,690 --> 00:13:57,060 on, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Joten meidän ei tarvitse käyttää työpöytä valaisimet, miltä se näyttää. 365 00:13:59,250 --> 00:13:59,690 Selvä. 366 00:13:59,690 --> 00:14:01,530 Niin miten te kaksi edessä. 367 00:14:01,530 --> 00:14:04,160 Entä te kaksi kaverit takana. 368 00:14:04,160 --> 00:14:04,870 Niin, että neljä. 369 00:14:04,870 --> 00:14:09,890 Miten sinusta edessä viisi, kuusi ja seitsemän. 370 00:14:09,890 --> 00:14:10,320 Tuolla. 371 00:14:10,320 --> 00:14:13,260 Ystäväsi osoittaa sinua ulos, niin saat palkinnon. 372 00:14:13,260 --> 00:14:13,700 >> Selvä. 373 00:14:13,700 --> 00:14:14,410 Tule ylös. 374 00:14:14,410 --> 00:14:17,120 Ja miksi emme ole sinulle miehet ovat tulleet tänne. 375 00:14:17,120 --> 00:14:18,960 Aion antaa sinulle jokaisen numeron. 376 00:14:18,960 --> 00:14:22,150 Ja mennä eteenpäin ja järjestää itse identtisen mitä 377 00:14:22,150 --> 00:14:25,180 kuvattu ruudulla. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing ÄÄNTÄ] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Selvä. 382 00:14:32,180 --> 00:14:32,750 No, tässä sitä mennään. 383 00:14:32,750 --> 00:14:34,180 Numero viisi. 384 00:14:34,180 --> 00:14:35,136 Numero kuusi. 385 00:14:35,136 --> 00:14:37,770 Yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän. 386 00:14:37,770 --> 00:14:39,410 Voi, tämä on hankala. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Minä saan vain -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Good deal. 389 00:14:41,900 --> 00:14:43,130 Selvä. 390 00:14:43,130 --> 00:14:44,611 Kiitos osallistumisesta. 391 00:14:44,611 --> 00:14:47,200 >> [APPLAUSE] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Selvä. 394 00:14:48,860 --> 00:14:51,970 Joten meillä on neljä, kaksi, kuusi, yksi, kolme, seitsemän, viisi. 395 00:14:51,970 --> 00:14:56,010 Perfect joten meillä on seitsemän vapaaehtoisia täällä, jotka ovat yhtä leveä 396 00:14:56,010 --> 00:14:57,430 array, että me pelaamme kanssa aiemmin. 397 00:14:57,430 --> 00:14:59,470 Ja päätin seitsemän syistä joka on vain 398 00:14:59,470 --> 00:15:00,840 kätevä vähän. 399 00:15:00,840 --> 00:15:04,400 Ja aion ehdottaa ensin, että me lajitella nämä seitsemän vapaaehtoisia. 400 00:15:04,400 --> 00:15:06,786 Jos haluat, ensimmäinen, tervehtimään vaikka. 401 00:15:06,786 --> 00:15:08,970 Koska tämä tulee olemaan hankala useita minuutteja. 402 00:15:08,970 --> 00:15:10,370 Esitellä itsenne. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hei, olen Grace. 404 00:15:10,980 --> 00:15:14,190 Olen toisen vuoden opiskelija Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hei. 406 00:15:14,620 --> 00:15:15,620 Olen Branson. 407 00:15:15,620 --> 00:15:16,920 Olen fuksi Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hei. 410 00:15:20,230 --> 00:15:21,040 Olen Gabe. 411 00:15:21,040 --> 00:15:22,300 Olen juniori Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Olen Neil. 414 00:15:25,980 --> 00:15:29,090 Olen fuksi Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Olen Jason. 416 00:15:29,550 --> 00:15:32,816 Olen fuksi Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Olen Mike. 418 00:15:33,700 --> 00:15:37,360 Olen fuksi Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Olen Jess. 420 00:15:37,990 --> 00:15:40,313 Olen toisen vuoden opiskelija Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Erinomainen. 422 00:15:41,300 --> 00:15:41,850 Selvä. 423 00:15:41,850 --> 00:15:44,190 No, kiitos kaikille Vapaaehtoiset toistaiseksi. 424 00:15:44,190 --> 00:15:47,110 Ja haaste käsillä nyt on menossa olla tavallaan nämä kaverit, mutta sitten 425 00:15:47,110 --> 00:15:50,250 aiomme täytyy ajatella hieman kova, miten tehokkaasti me oikeastaan 426 00:15:50,250 --> 00:15:51,110 ne on lajiteltu. 427 00:15:51,110 --> 00:15:52,580 Joten ensin kokeilla tätä. 428 00:15:52,580 --> 00:15:55,970 Te voi nähdä toistensa numerot vain sijoittamalla kulmien ympäri. 429 00:15:55,970 --> 00:15:59,380 Mennä eteenpäin ja kestää muutaman sekunnin, ja lajitella itsenne pienimmistä 430 00:15:59,380 --> 00:16:01,240 jää suurin oikealla. 431 00:16:01,240 --> 00:16:02,490 Go. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Hyvä. 435 00:16:08,030 --> 00:16:09,370 Se oli todella hiton nopeasti. 436 00:16:09,370 --> 00:16:14,040 Nyt joku täällä, mikä oli algoritmi että nämä kaverit sovelletaan? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Korkeasta suurin. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Ainakin suurin on todella tavallaan tavoite, mutta en ole varma, että se 440 00:16:18,070 --> 00:16:18,890 todella algoritmi. 441 00:16:18,890 --> 00:16:21,810 Ainakin suurin ei kerro minulle askel askeleelta mitä tehdä. 442 00:16:21,810 --> 00:16:22,833 Niin? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [äänetön] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Joten jos näet henkilön pienempi kuin numerosi, sitten siirtyä 447 00:16:28,920 --> 00:16:29,680 oikea niistä. 448 00:16:29,680 --> 00:16:32,800 Niin, että nyt saada enemmän ilmeikäs, enemmän kuin algoritmi, koska 449 00:16:32,800 --> 00:16:35,410 voi sanoa, jos tämä, niin se. 450 00:16:35,410 --> 00:16:37,050 Joten meillä on jonkinlainen ehdollinen rakennelma. 451 00:16:37,050 --> 00:16:39,700 Ja nämä kaverit näyttivät tehdä muutamia kertaa, koska jotkut teistä muuttanut hieman 452 00:16:39,700 --> 00:16:40,420 ja etäisyyden. 453 00:16:40,420 --> 00:16:43,410 Joten oli oletettavasti jonkinlainen looping tapahtuu heidän mielessään. 454 00:16:43,410 --> 00:16:44,610 >> Mutta yritetään virallistaa että. 455 00:16:44,610 --> 00:16:47,540 Jos te voisi palauttaa takaisin Tämän järjestelyn. 456 00:16:47,540 --> 00:16:50,650 Katsotaan, jos emme voi virallistaa tämän bittinen, ja sitten kysyä, vain 457 00:16:50,650 --> 00:16:51,580 kuinka tehokas tämä on? 458 00:16:51,580 --> 00:16:54,220 Tietenkin, kun teemme tätä hitaammin, se tulee tuntea niin hyvää 459 00:16:54,220 --> 00:16:57,210 algoritmi, mutta katsotaan jos voimme laittaa sormet tarkka vaiheet. 460 00:16:57,210 --> 00:16:58,670 >> Joten te kaksi olette neljä ja kaksi. 461 00:16:58,670 --> 00:17:01,020 Tai sitten oikea tai väärä järjestys? 462 00:17:01,020 --> 00:17:01,900 Selvästi virheellinen. 463 00:17:01,900 --> 00:17:02,710 Joten vaihdoin. 464 00:17:02,710 --> 00:17:05,170 Nyt aion siirtyä sivuun ja sanoa neljästä kuuteen. 465 00:17:05,170 --> 00:17:06,240 Oletko oikea tai väärä? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Oikea. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Oikea. 468 00:17:07,180 --> 00:17:08,300 Kuusi ja yksi? 469 00:17:08,300 --> 00:17:08,609 Ehei. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Niin, että kaksi swap. 472 00:17:10,490 --> 00:17:11,710 Kuusi ja kolme? 473 00:17:11,710 --> 00:17:11,980 Ehei. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Kuusi ja seitsemän? 476 00:17:13,930 --> 00:17:14,630 Näyttää hyvältä. 477 00:17:14,630 --> 00:17:15,396 Seitsemän ja viisi? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [äänetön] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, vaihtaa. 480 00:17:17,089 --> 00:17:19,770 Ja lajitellaan. 481 00:17:19,770 --> 00:17:19,980 Selvä. 482 00:17:19,980 --> 00:17:21,440 Joten ilmeisesti ei, eikö? 483 00:17:21,440 --> 00:17:22,470 Joten oli enemmän tekeillä. 484 00:17:22,470 --> 00:17:24,920 Mutta tosiaan, nämä kaverit, vaikka vain vaistomaisesti. 485 00:17:24,920 --> 00:17:25,450 pidettävä liikkeessä. 486 00:17:25,450 --> 00:17:27,710 He eivät vain lopettaa, kun ne korjattu yksi ongelma. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 Itse aion olla tehdä sama asia. 489 00:17:29,390 --> 00:17:32,720 Aion olla tavallaan taaksepäin takaisin alkuun tämän ongelman 490 00:17:32,720 --> 00:17:35,630 tai alussa joukko ihmiset, aloitamme kutsuvan heitä. 491 00:17:35,630 --> 00:17:38,366 >> Ja nyt, mitä pitäisi minun algoritmi Toisessa läpiviennissä on? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Sama juttu. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Sama juttu. 494 00:17:39,940 --> 00:17:41,460 Ja tämä, olen alkanut pitämään, eikö? 495 00:17:41,460 --> 00:17:44,720 Heti kun löydät itsesi tekemässä sama asia uudestaan ​​ja uudestaan, se on 496 00:17:44,720 --> 00:17:47,890 tulossa enemmän kuin algoritmin ja vähemmän ihmisen vaisto. 497 00:17:47,890 --> 00:17:48,680 >> Joten nyt, tässä sitä taas. 498 00:17:48,680 --> 00:17:49,870 Kaksi ja neljä? 499 00:17:49,870 --> 00:17:50,220 Ei. 500 00:17:50,220 --> 00:17:51,050 Neljä ja yksi? 501 00:17:51,050 --> 00:17:53,380 Ah, siellä oli todellakin joitakin työtä on vielä tekemättä. 502 00:17:53,380 --> 00:17:53,620 Sillä ja kolme? 503 00:17:53,620 --> 00:17:54,572 Hyvä. 504 00:17:54,572 --> 00:17:56,000 Neljä ja kuusi? 505 00:17:56,000 --> 00:17:58,380 Kuusi ja viisi? 506 00:17:58,380 --> 00:17:59,470 Kuusi ja seitsemän? 507 00:17:59,470 --> 00:18:00,970 OK, nyt tehdään. 508 00:18:00,970 --> 00:18:01,550 OK, no. 509 00:18:01,550 --> 00:18:02,710 Minun täytyy mennä takaisin. 510 00:18:02,710 --> 00:18:05,130 >> Joten nyt taas, teemme tätä hieman tarkoituksella. 511 00:18:05,130 --> 00:18:08,700 Ja nyt siellä on vain yksi aivojen täytäntöönpanosta tämän algoritmi. 512 00:18:08,700 --> 00:18:10,290 Yksi CPU, jos haluatte. 513 00:18:10,290 --> 00:18:13,090 Ja suoraan sanottuna, se on ainoa resurssi aiomme saada. 514 00:18:13,090 --> 00:18:16,280 Ja kun emme mene takaisin näppäimistö ja on jotain C meidän 515 00:18:16,280 --> 00:18:19,600 hävittäminen, olemme vain ohjelman kirjoittaminen joka voi tehdä yksi asia kerrallaan. 516 00:18:19,600 --> 00:18:22,900 Sekä katsoo, nämä kaverit hetki sitten, me velkarahalla kollektiivista aivokapasiteetti 517 00:18:22,900 --> 00:18:24,180 kuten teitte kaverit viikolla nolla. 518 00:18:24,180 --> 00:18:24,980 Joten pitää tehdä tätä. 519 00:18:24,980 --> 00:18:26,260 >> Kaksi ja yksi. 520 00:18:26,260 --> 00:18:26,945 Kaksi ja kolme. 521 00:18:26,945 --> 00:18:27,460 Kolme ja neljä. 522 00:18:27,460 --> 00:18:28,310 Neljä ja viisi. 523 00:18:28,310 --> 00:18:28,620 Viisi ja kuusi. 524 00:18:28,620 --> 00:18:30,510 Kuusi ja seitsemän. 525 00:18:30,510 --> 00:18:31,880 Tehty? 526 00:18:31,880 --> 00:18:34,560 Joten olen, mutta anna minun pelata paholaisen asianajajana. 527 00:18:34,560 --> 00:18:37,950 Voin, tällainen tietokone, joka vain teki ohittamaan tämän joukko 528 00:18:37,950 --> 00:18:40,225 ihmiset, tietävät, että olen tehnyt? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: No 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Miksi? 531 00:18:41,050 --> 00:18:46,900 Mitä minun pitää tehdä, jotta päätellä ratkaisevasti, että olen tehnyt? 532 00:18:46,900 --> 00:18:48,230 Luultavasti yksi syöttö. 533 00:18:48,230 --> 00:18:48,430 Oikea? 534 00:18:48,430 --> 00:18:51,760 Koska kaikki Tiedän, että edellinen pass on, että korjasin virheen. 535 00:18:51,760 --> 00:18:53,920 Ja se tarkoittaa, ehkä siellä on vielä toisen virheen 536 00:18:53,920 --> 00:18:54,840 että minun täytyy korjata. 537 00:18:54,840 --> 00:18:58,680 Joten voin vain olla varma uudelleenrullaamalla, ja sitten tarkistaa, yksi kaksi, kaksi ja 538 00:18:58,680 --> 00:19:00,940 kolme, kolme ja neljä, neljä ja viisi, viisi ja kuusi, kuusi ja seitsemän. 539 00:19:00,940 --> 00:19:02,510 OK, nyt tein mitään työtä. 540 00:19:02,510 --> 00:19:05,990 >> Voin varmasti muistaa, että tein mitään työskennellä jotain muuttuja, 541 00:19:05,990 --> 00:19:06,975 kuten int. 542 00:19:06,975 --> 00:19:12,490 Soita se swap, ja jos swap on 0, kun olen tänne, ja se alkoi 0, niin 543 00:19:12,490 --> 00:19:15,520 Haluan vain olla tyhmä pitää käynnissä edestakaisin, tarkistaa uudelleen, ja 544 00:19:15,520 --> 00:19:16,450 uudestaan, ja uudestaan, eikö? 545 00:19:16,450 --> 00:19:18,450 Koska saat kiinni joissakin Tällainen päättymättömään silmukkaan. 546 00:19:18,450 --> 00:19:21,250 Joten kun siellä on 0 koronvaihtosopimukset, voimme väittää, että tämä 547 00:19:21,250 --> 00:19:23,810 algoritmi on todellakin täydellinen. 548 00:19:23,810 --> 00:19:25,400 >> Nyt, laita nimi tähän. 549 00:19:25,400 --> 00:19:28,930 Algoritmi, että ehdotan me vain täytäntöön on jotain kutsutaan kupla 550 00:19:28,930 --> 00:19:32,800 lajitella, sinänsä tunnettuja siinä mielessä, että numeroita, jotka ovat suurempia sellainen 551 00:19:32,800 --> 00:19:37,990 kupla tiensä ylös, tai jopa loppuun joukko numeroita. 552 00:19:37,990 --> 00:19:40,270 Mutta miten tehokas oli tämä algoritmi? 553 00:19:40,270 --> 00:19:44,600 Kuinka monta askelta minä fyysisesti on ottaa esimerkiksi lajitella nämä 554 00:19:44,600 --> 00:19:45,850 seitsemän ihmisiin? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Neljä viisi? 557 00:19:49,550 --> 00:19:51,420 OK, liikaa on viime kädessä olemaan vastaus. 558 00:19:51,420 --> 00:19:54,960 Mutta silloinkin, tietty määrä ei ole niin kiinnostavaa. 559 00:19:54,960 --> 00:19:56,670 Katsotaanpa yleistää sitä n. 560 00:19:56,670 --> 00:20:00,520 Joten jos olisin n ihmisiä täällä, ja ne olivat, tavallaan, satunnaisessa järjestyksessä 561 00:20:00,520 --> 00:20:02,180 alussa, että alkuperäisessä järjestyksessä. 562 00:20:02,180 --> 00:20:04,910 No, kuinka monta askelta minun tarvinnut ottaa ensikierron? 563 00:20:04,910 --> 00:20:09,810 Se oli yksi, kaksi, kolme, neljä, viisi, kuusi, ja ne seitsemän henkilöä, joten 564 00:20:09,810 --> 00:20:13,670 se on seitsemän, kuusi -, niin se on n miinus yksi vaiheet ensimmäisen kerran. 565 00:20:13,670 --> 00:20:16,280 >> Nyt, kuinka monta askelta minun tarvinnut ottaa kun kelata? 566 00:20:16,280 --> 00:20:19,310 No, voisimme todella kaksinkertainen, jos halusimme, mutta nyt olen 567 00:20:19,310 --> 00:20:22,300 juuri menossa sanoa, okei, toinen n miinus 1. 568 00:20:22,300 --> 00:20:25,240 Joten n miinus 1 on menossa ärsyttävää seurata, joten katsotaanpa 569 00:20:25,240 --> 00:20:26,400 vain pyöristää ylöspäin hieman. 570 00:20:26,400 --> 00:20:27,770 Joten 2n vaiheet. 571 00:20:27,770 --> 00:20:29,310 Joten 14 vaiheet, antaa tai ottaa. 572 00:20:29,310 --> 00:20:31,930 >> Kuinka monta kertaa otan askel seuraavan kerran? 573 00:20:31,930 --> 00:20:33,740 No, se on 3n. 574 00:20:33,740 --> 00:20:34,510 todella. 575 00:20:34,510 --> 00:20:37,920 Ja nyt, pahimmassa tapauksessa Esimerkiksi kuinka monta kertaa olisin 576 00:20:37,920 --> 00:20:41,730 mennyt edestakaisin, edestakaisin, täytäntöönpanosta tämän algoritmin, vaihtamalla 577 00:20:41,730 --> 00:20:44,620 ihmiset jokaisen syötön, suunnilleen? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Se on oikeastaan ​​n potenssiin, eikö? 580 00:20:50,010 --> 00:20:53,000 >> Koska pahimmassa tapauksessa voit sellaista ajattelevat tästä intuitiivisesti, 581 00:20:53,000 --> 00:20:54,800 vaikka se saattaa kestää hieman vähän aikaa upota sisään 582 00:20:54,800 --> 00:20:57,590 Pahimmassa tapauksessa, mitä olisi nämä seitsemän ihmistä näyttäneet, vuonna 583 00:20:57,590 --> 00:21:00,230 Järjestelyssä niiden numerot? 584 00:21:00,230 --> 00:21:01,460 Täysin taaksepäin, eikö? 585 00:21:01,460 --> 00:21:02,815 Ja vain simuloida, että mikä sinun nimesi olikaan? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, voisitko liittyä minua täällä vain hetken? 589 00:21:08,100 --> 00:21:08,880 Oikeastaan ​​ei. 590 00:21:08,880 --> 00:21:10,150 Sorry Mike, katsotaanpa taaksepäin. 591 00:21:10,150 --> 00:21:10,910 Mikä sinun nimesi olikaan? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, tulet minulle, jos et pahastu. 595 00:21:13,750 --> 00:21:17,150 Joten aion ehdottaa, vain yksinkertaisuus, että Neil on nyt hänen 596 00:21:17,150 --> 00:21:18,510 pahin mahdollinen tapaus. 597 00:21:18,510 --> 00:21:20,720 Mutta muistaa miten toteutetaan minun algoritmi. 598 00:21:20,720 --> 00:21:24,530 Olen vertaamalla, vertaamalla, vertaamalla, vertaamalla, vertaamalla, oh. 599 00:21:24,530 --> 00:21:26,640 Nyt nämä kaverit ovat poissa järjestyksessä, niin voin korjata. 600 00:21:26,640 --> 00:21:27,980 Joten te vaihtaa. 601 00:21:27,980 --> 00:21:31,630 Ajatelkaa nyt, kuinka paljon kauemmas ei Neil täytyy mennä? 602 00:21:31,630 --> 00:21:32,690 Se on suunnilleen n. 603 00:21:32,690 --> 00:21:33,570 Tiedäthän, se ei ole oikeastaan ​​n. 604 00:21:33,570 --> 00:21:36,040 Se on kuin, n miinus 1, mutta Saan harmissaan pitää kirjaa vähän 605 00:21:36,040 --> 00:21:37,550 numero, joten haluan vain kutsua sitä n. 606 00:21:37,550 --> 00:21:42,860 >> Joten jos Neil siirtyy askeleen maksimaalisesti kunkin aikaa, ja siirtyä Neil askeleen, 607 00:21:42,860 --> 00:21:46,580 Minun täytyy tehdä tämä todella ikävä pass edestakaisin, tämä on karkeasti 608 00:21:46,580 --> 00:21:52,080 Näin n askelta, yhteensä n kertaa, koska se vie minut 609 00:21:52,080 --> 00:21:55,820 että monet askeleen päästä Neil kaikki tapa, mihin hän kuuluu. 610 00:21:55,820 --> 00:21:58,620 Puhumattakaan kaikki muutkin, jos te olivat kaikki väärin tilata samoin. 611 00:21:58,620 --> 00:22:01,100 >> Joten soita kupla lajitella n potenssiin. 612 00:22:01,100 --> 00:22:04,860 Käyntiaika tämän algoritmin, suorituskyky tämän algoritmin 613 00:22:04,860 --> 00:22:07,120 tehokkuutta tämän algoritmin, meillä on vain kuvata enemmän 614 00:22:07,120 --> 00:22:08,800 yleisesti n potenssiin. 615 00:22:08,800 --> 00:22:11,650 Mikä on mukavaa, koska en voinut tehdä Sama esimerkiksi kahdeksan ihmistä, yhdeksän 616 00:22:11,650 --> 00:22:15,450 ihmisiä, miljoona ihmistä, ja että vastaus ei tule muuttaa. 617 00:22:15,450 --> 00:22:18,870 >> Joten jos te panisi pahakseni, katsotaanpa palauttaa sinut missä aloitit. 618 00:22:18,870 --> 00:22:22,510 Ja koetamme kaksi muuta lähestymistapoja ja katso jos emme voi tehdä pohjimmiltaan 619 00:22:22,510 --> 00:22:23,820 parempi kuin tämä. 620 00:22:23,820 --> 00:22:27,130 Joten tällä kertaa, aion ehdottaa eräänlainen eri algoritmia. 621 00:22:27,130 --> 00:22:29,950 Se oli erittäin taitava meistä viime kerralla, ja olitte oikeus saada 622 00:22:29,950 --> 00:22:32,470 oikeus vaistot juuri sellainen vaihtava pareittain. 623 00:22:32,470 --> 00:22:36,500 Mutta jos halusin lähestyä tätä yksinkertaisesti, ja minun tavoite on siirtää 624 00:22:36,500 --> 00:22:39,800 kaikki pikku numerot tällä tavalla, ja työntää kaikki suuret numerot, että 625 00:22:39,800 --> 00:22:43,030 Muuten, miksi en vain tehdä, että Useimmissa naiivi mahdollisella tavalla ja nähdä, jos olen 626 00:22:43,030 --> 00:22:45,730 voi tehdä paremmin kuin mitä oli melko monimutkainen algoritmi? 627 00:22:45,730 --> 00:22:46,620 >> Katsotaanpa. 628 00:22:46,620 --> 00:22:48,940 Neljä on melko pieni määrä, joten olen aio jättää sinua siellä hetki. 629 00:22:48,940 --> 00:22:50,610 Ooh, numero kaksi on vielä parempi. 630 00:22:50,610 --> 00:22:52,230 Joten voitte vain askel eteenpäin hetkeksi? 631 00:22:52,230 --> 00:22:55,670 Tämä on tällä hetkellä minun pienin numeroitu ehdokas, ja aion muistaa 632 00:22:55,670 --> 00:22:57,000 että niinku muuttuja. 633 00:22:57,000 --> 00:22:57,930 Mutta aion pitää tarkistaa. 634 00:22:57,930 --> 00:22:59,890 Onko joku, jonka määrä on pienempi? 635 00:22:59,890 --> 00:23:00,460 Kuusi, no. 636 00:23:00,460 --> 00:23:01,390 Voi, on Neil uudelleen. 637 00:23:01,390 --> 00:23:04,050 >> Joten aion työntää sinut takaisin tavallaan käsitteellisesti. 638 00:23:04,050 --> 00:23:05,120 Neil tulee eteen. 639 00:23:05,120 --> 00:23:08,440 Ja nyt, muuttuja että olen käyttävät seurata kuka on pienin 640 00:23:08,440 --> 00:23:11,390 numero päivitetään sisältämään Neil sijainti. 641 00:23:11,390 --> 00:23:12,110 No, katsotaanpa. 642 00:23:12,110 --> 00:23:13,960 Kolme, seitsemän, viisi. 643 00:23:13,960 --> 00:23:15,590 Tunnen Neil oli pienin. 644 00:23:15,590 --> 00:23:18,110 Mikä on yksinkertaisin asia minun tehdä nyt? 645 00:23:18,110 --> 00:23:21,410 En aio tuhlata aikaani vain kuplivaa Neil yksi paikka vasemmalle. 646 00:23:21,410 --> 00:23:25,350 Miksi en vain laittaa Neil jossa hän kuuluu, mikä on tietysti missä? 647 00:23:25,350 --> 00:23:26,160 >> Koko matkan alussa. 648 00:23:26,160 --> 00:23:27,720 Joten Neil, tule. 649 00:23:27,720 --> 00:23:28,910 Ja mikä sinun nimesi olikaan? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Joten Grace, valitettavasti, olet Tällainen tavalla. 654 00:23:32,490 --> 00:23:34,290 Miten siis ratkaista tämän ongelman? 655 00:23:34,290 --> 00:23:34,490 Oikea? 656 00:23:34,490 --> 00:23:37,500 Jos tämä on jono, siellä on vain seitsemällä paikkakunnalla. 657 00:23:37,500 --> 00:23:40,830 Muista, että, Rob, puhuimme julistaa ikäisiä, ja meillä oli vain 658 00:23:40,830 --> 00:23:41,740 äärellinen määrä ikäisille? 659 00:23:41,740 --> 00:23:42,535 Sama ajatus täällä. 660 00:23:42,535 --> 00:23:44,300 Meillä on vain rajallinen määrä ints. 661 00:23:44,300 --> 00:23:47,590 Grace on tavallaan meidän tavalla, niin miten me korjata? 662 00:23:47,590 --> 00:23:49,555 >> Yksinkertaisin tapa on kuin, Grace, anteeksi. 663 00:23:49,555 --> 00:23:51,870 Olet menossa on mennä yli siellä niin voimme tehdä tilaa. 664 00:23:51,870 --> 00:23:55,290 Nyt, jos ajattelee tätä, ehkä Olemme juuri tehnyt ongelma pahempi. 665 00:23:55,290 --> 00:23:58,510 Ja ehkä teimme, koska mitä jos Grace oli oikeassa paikassa? 666 00:23:58,510 --> 00:24:01,730 Mutta me tiedämme, hän ei ole, koska muuten hän olisi ollut 667 00:24:01,730 --> 00:24:03,980 seisoo eteenpäin sijaan Neil tällä kertaa, eikö? 668 00:24:03,980 --> 00:24:05,550 Meillä on jo tarkistanut hänen numeronsa ulos. 669 00:24:05,550 --> 00:24:05,770 >> Selvä. 670 00:24:05,770 --> 00:24:09,110 Joten nyt, Neil on oikeassa paikassa, ja Voin tehdä hieman optimointia. 671 00:24:09,110 --> 00:24:11,740 Seuraavan minuutin, aion sivuuttaa Neil kaikki yhdessä, jotta ei 672 00:24:11,740 --> 00:24:15,280 tuhlaa aikaansa, tai vahingossa vaihtaa hänet väärään paikkaan. 673 00:24:15,280 --> 00:24:17,805 Joten nyt, miten löydän seuraavan elementti, joka on pienin? 674 00:24:17,805 --> 00:24:18,480 Kaksi. 675 00:24:18,480 --> 00:24:20,225 Se on aika hyvä määrä, jos Haluatko astua esiin ja 676 00:24:20,225 --> 00:24:21,100 Minä muistan sinut. 677 00:24:21,100 --> 00:24:21,980 Kuusi, ole hyvä. 678 00:24:21,980 --> 00:24:24,820 Neljä, kolme, seitsemän, viisi, ei hyvä. 679 00:24:24,820 --> 00:24:26,800 Joten anna minun siirtää sinut oikea paikka. 680 00:24:26,800 --> 00:24:28,470 Ja me vain onnekas tällä kertaa. 681 00:24:28,470 --> 00:24:31,350 >> Nyt aion jättää nämä Kaksi miestä, ja nyt vielä yhden 682 00:24:31,350 --> 00:24:32,260 läpi tämän. 683 00:24:32,260 --> 00:24:33,490 Kuusi, että melko pieni määrä. 684 00:24:33,490 --> 00:24:34,300 Tule eteenpäin. 685 00:24:34,300 --> 00:24:35,220 Anteeksi. 686 00:24:35,220 --> 00:24:37,640 Grace numero on parempi, joten astua eteenpäin. 687 00:24:37,640 --> 00:24:38,260 Neljä. 688 00:24:38,260 --> 00:24:39,120 Anteeksi, Grace. 689 00:24:39,120 --> 00:24:39,950 Mene takaisin. 690 00:24:39,950 --> 00:24:41,550 Numero kolme on parempi. 691 00:24:41,550 --> 00:24:42,290 Seitsemän. 692 00:24:42,290 --> 00:24:42,720 Viisi. 693 00:24:42,720 --> 00:24:43,550 Ja nyt, mitä sinun nimesi olikaan? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Joten Jason on nyt pienin elementti Olen valinnut. 697 00:24:47,050 --> 00:24:49,160 Jos hän aikoo mennä? 698 00:24:49,160 --> 00:24:50,380 Joten missä kuusi on. 699 00:24:50,380 --> 00:24:51,210 Ja sinun nimesi on jälleen? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe on tiellä. 703 00:24:53,220 --> 00:24:54,640 Mikä on helpoin asia tehdä? 704 00:24:54,640 --> 00:24:58,390 Vaihda nämä kaksi kaveria ja jatkaa. 705 00:24:58,390 --> 00:24:59,020 Joten nyt katsotaanpas. 706 00:24:59,020 --> 00:25:00,170 Kuka pienin? 707 00:25:00,170 --> 00:25:01,030 Neljä. 708 00:25:01,030 --> 00:25:01,990 Haluan vain sellainen huijata. 709 00:25:01,990 --> 00:25:03,090 Viisi tulee olemaan pienin. 710 00:25:03,090 --> 00:25:05,220 Minusta seuraava, jos haluat astua eteenpäin, mitä minun täytyy tehdä 711 00:25:05,220 --> 00:25:06,820 nämä kaverit, joiden Gabe? 712 00:25:06,820 --> 00:25:08,450 Vaihda uudelleen. 713 00:25:08,450 --> 00:25:10,740 Joten nyt vielä hieman epäkunnossa. 714 00:25:10,740 --> 00:25:14,140 I todettiin Gabe olevan pienin, niin Olen pop syötöllään, siirrä te yli. 715 00:25:14,140 --> 00:25:15,190 Ja tehty. 716 00:25:15,190 --> 00:25:17,200 >> Joten vastaus on sama. 717 00:25:17,200 --> 00:25:18,600 Lopputulos on sama. 718 00:25:18,600 --> 00:25:22,730 Kumpi näistä kahdesta algoritmeja on parempi? 719 00:25:22,730 --> 00:25:23,500 Toinen, kuulin. 720 00:25:23,500 --> 00:25:24,252 Miksi? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Se n askelta [kuultavissa]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Se n vaiheet eniten. 723 00:25:27,600 --> 00:25:28,490 Mielenkiintoista. 724 00:25:28,490 --> 00:25:30,610 Niin on se kuitenkin? 725 00:25:30,610 --> 00:25:33,630 Joten miten löydän pienimmän alkion? 726 00:25:33,630 --> 00:25:37,060 Kuinka monta askelta ei minun on otettava löytää pienimmän alkion? 727 00:25:37,060 --> 00:25:39,220 Olin näyttää aina lopussa, eikö? 728 00:25:39,220 --> 00:25:41,530 Koska että pahimmassa tapauksessa, mitä jos Neil olivat täällä? 729 00:25:41,530 --> 00:25:45,700 Joten vain löytää pienimmän alkion vie minut n askelta, tai n miinus 1. 730 00:25:45,700 --> 00:25:46,100 Mutta, OK. 731 00:25:46,100 --> 00:25:46,980 Korjatkaa Neil. 732 00:25:46,980 --> 00:25:48,740 Muista, että minuutti sitten. 733 00:25:48,740 --> 00:25:51,680 >> Mutta miten saan seuraavan pienimmän alkion? 734 00:25:51,680 --> 00:25:54,830 Se n miinus 1 tai n miinus 2 todella, alkaen useita vaiheita. 735 00:25:54,830 --> 00:25:55,440 Niin OK. 736 00:25:55,440 --> 00:25:57,390 Joten en n miinus 2. 737 00:25:57,390 --> 00:25:57,600 Selvä. 738 00:25:57,600 --> 00:25:59,130 Niin että tuntuu hieman paremmin. 739 00:25:59,130 --> 00:25:59,730 Selvä. 740 00:25:59,730 --> 00:26:03,270 Kuinka monta askelta seuraavan kerran löytää numero kolme? 741 00:26:03,270 --> 00:26:04,420 Joten n miinus 4. 742 00:26:04,420 --> 00:26:07,670 Joten se on laskussa, yksi vähemmän astua jokaisen iteraation. 743 00:26:07,670 --> 00:26:08,740 Joten tämä ei tuntea paremmin, eikö? 744 00:26:08,740 --> 00:26:13,450 Jos viime kerralla se oli noin n kertaa n, tällä kertaa se n miinus 1, plus n miinus 745 00:26:13,450 --> 00:26:16,500 2, plus n miinus 3, plus n miinus 4, piste, piste, piste. 746 00:26:16,500 --> 00:26:18,750 Mutta jos muistatte omasta lukion oppikirjat, vähän huijata 747 00:26:18,750 --> 00:26:24,380 arkki takaisin, että on kaavojen avulla, jos lisäät tätä numerosarja, 748 00:26:24,380 --> 00:26:31,280 mikä on portaiden kokonaismäärää olemaan, että otan täällä? 749 00:26:31,280 --> 00:26:36,580 >> Tämä on yksi niistä, kuten, n miinus 1 kertaa n, jaettuna 2. 750 00:26:36,580 --> 00:26:39,040 Joten anna minun nähdä, jos voin vetää tähän asti vain hetken. 751 00:26:39,040 --> 00:26:42,230 Ja vielä, olen sellainen pyöristys joidenkin numerot vain pitää elämäämme yksinkertainen, 752 00:26:42,230 --> 00:26:47,830 mutta muistaakseni se on jotain, jos En n miinus 1 asioita, niin n miinus 753 00:26:47,830 --> 00:26:53,570 2, niin n miinus 3, se on suurin piirtein jotain tällaista yli 2, ja jos minä 754 00:26:53,570 --> 00:26:55,510 moninkertaistaa tämän, se on todella n neliö. 755 00:26:55,510 --> 00:26:58,940 Se ei tunne liian hyvä. n miinus n yli 2. 756 00:26:58,940 --> 00:27:00,350 >> Mutta tässä on asia. 757 00:27:00,350 --> 00:27:03,720 Tietotekniikassa, kun ongelmia alkaa saada mielenkiintoista on kun n 758 00:27:03,720 --> 00:27:04,700 saa todella suuri. 759 00:27:04,700 --> 00:27:08,110 Ja kun n saa todella suuri, mikä Näiden arvojen tulee hallitsemaan kaikkia 760 00:27:08,110 --> 00:27:09,750 ja muut? 761 00:27:09,750 --> 00:27:10,990 Se on tavallaan n potenssiin, eikö? 762 00:27:10,990 --> 00:27:13,340 Kyllä, jakamalla 2 on melko hyvä. 763 00:27:13,340 --> 00:27:16,740 Mutta jos puhut miljardeja paloja tietoja tai miljardeja 764 00:27:16,740 --> 00:27:18,700 datakappaleesta, OK, niin olet kaksi kertaa niin nopeasti. 765 00:27:18,700 --> 00:27:22,440 Mutta kuka todella välittää, jos suuri määrä, jos tämä seikka on mitä saa 766 00:27:22,440 --> 00:27:23,040 isompi ja isompi. 767 00:27:23,040 --> 00:27:25,990 Ja varmasti, se tekee enemmän ero kuin tämä kaveri. 768 00:27:25,990 --> 00:27:29,120 Joten vaikka te olette oikeassa, Toinen algoritmi, me kutsumme sitä 769 00:27:29,120 --> 00:27:32,970 valinta lajitella, on, todellisessa maailmassa, hieman nopeampi mahdollisesti, koska olen 770 00:27:32,970 --> 00:27:35,360 ottaen yhä harvempi askeleen kerrallaan. 771 00:27:35,360 --> 00:27:37,340 >> Se ei ole oikeastaan ​​pohjimmiltaan nopeammin. 772 00:27:37,340 --> 00:27:41,430 Koska jos me todella pelata tätä ulos suuret n: n arvoilla, lopussa 773 00:27:41,430 --> 00:27:44,750 päivä, tarpeeksi suuri n, se on silti menossa tuntea melko hidasta. 774 00:27:44,750 --> 00:27:46,770 No, anna minun ottaa yksi viime pass tuohon. 775 00:27:46,770 --> 00:27:48,920 Sitä minä kutsuisin valinta lajitella. 776 00:27:48,920 --> 00:27:51,040 Voisitteko palauttaa itseänne viimeisen kerran? 777 00:27:51,040 --> 00:27:53,550 Ja tässä viime tapauksessa aion ehdottaa jotain 778 00:27:53,550 --> 00:27:54,970 nimeltään lisäyslajittelu. 779 00:27:54,970 --> 00:27:57,470 Lisäyslajittelu on käsitteellisesti vähän erilainen. 780 00:27:57,470 --> 00:28:00,980 >> Sijaan menee edestakaisin ja valitsemalla pienimmän alkion, olen 781 00:28:00,980 --> 00:28:05,030 juuri menossa käsitellä kutakin näistä kaverit kuin minä kohtaavat heitä, ja aseta 782 00:28:05,030 --> 00:28:06,850 ne osaksi oikeassa paikassa. 783 00:28:06,850 --> 00:28:10,160 Joten olen juuri menossa aloittaa Grace, ja näen, että hän on numero neljä. 784 00:28:10,160 --> 00:28:11,720 Mistä numero neljä kuuluu? 785 00:28:11,720 --> 00:28:14,940 En ole alkanut lajittelu mitään, niin Grace saa jäädä oikeassa. 786 00:28:14,940 --> 00:28:18,355 Ja nyt aion vaatia, jos voisit ottaa askel oikealla, tämä 787 00:28:18,355 --> 00:28:21,650 minun lajiteltu lista, tämä on minun lajittelemattoman jäljellä lista. 788 00:28:21,650 --> 00:28:23,260 Joten nyt aion edetä seuraavaan, ja mikä sinun nimesi olikaan? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Joten Branson on numero kaksi. 792 00:28:25,375 --> 00:28:27,490 Joten aion viedä sinut pois hetkeksi. 793 00:28:27,490 --> 00:28:30,940 Ja nyt, jos kuulut Tässä array? 794 00:28:30,940 --> 00:28:32,360 Joten oikeus Grace. 795 00:28:32,360 --> 00:28:35,670 Joten jälleen olemme tavallaan tehdä Grace tehdä paljon työtä täällä. 796 00:28:35,670 --> 00:28:37,290 Minne laitamme sinut? 797 00:28:37,290 --> 00:28:40,120 Joten aiomme liukumaan sinua vasemmalle ja aseta Branson siellä. 798 00:28:40,120 --> 00:28:41,680 Mutta nyt Väitän, että te olette tehneet. 799 00:28:41,680 --> 00:28:43,240 Mutta huomaa, en käytä lisätilaa. 800 00:28:43,240 --> 00:28:45,130 Se on edelleen 2 elementtiä täällä, 5 tänne. 801 00:28:45,130 --> 00:28:47,910 Yhteensä jonon pituus on 7, joten olen ei huijaa, kaikki hyvin? 802 00:28:47,910 --> 00:28:51,950 >> Joten nyt meillä on, ja Gabe täällä, numero kuusi, jossa sinä kuulut? 803 00:28:51,950 --> 00:28:52,650 Olet onnekas uudelleen. 804 00:28:52,650 --> 00:28:53,820 Niin saat pysyä oikeassa. 805 00:28:53,820 --> 00:28:57,210 Ota vain hieman askel oikeaan vain tehdä selväksi, että olet lajitellaan. 806 00:28:57,210 --> 00:29:00,520 Ja nyt meillä on Neil uudelleen, numero yksi, minne menet? 807 00:29:00,520 --> 00:29:03,540 Ja nyt on, jos alamme nähdä, että tämä algoritmi, vaikka ensimmäisen 808 00:29:03,540 --> 00:29:05,950 silmäyksellä, tuntuu aika fiksu, katsella mitä tulee tapahtumaan. 809 00:29:05,950 --> 00:29:07,370 Jos voisit askel eteenpäin. 810 00:29:07,370 --> 00:29:09,260 >> Missä haluamme laittaa Neil? 811 00:29:09,260 --> 00:29:11,830 Joten ilmeisesti täällä, niin miten saamme Neil siellä? 812 00:29:11,830 --> 00:29:12,970 Tehdään tämä askel-askeleelta. 813 00:29:12,970 --> 00:29:15,620 Gabe, mistä sinun täytyy mennä? 814 00:29:15,620 --> 00:29:19,590 Jep, niin ottaa yksi iso askel, tai kaksi puolen toimiin, jotta 815 00:29:19,590 --> 00:29:20,820 yksi askel tuolla. 816 00:29:20,820 --> 00:29:21,750 Grace, missä mennään? 817 00:29:21,750 --> 00:29:22,510 Hyvä. 818 00:29:22,510 --> 00:29:23,500 Joten toinen vaihe. 819 00:29:23,500 --> 00:29:24,960 Ja lopuksi, Branson? 820 00:29:24,960 --> 00:29:25,460 Toinen vaihe. 821 00:29:25,460 --> 00:29:27,190 Ja nyt voimme Neil paikoilleen. 822 00:29:27,190 --> 00:29:28,440 >> Joten nyt jatkaa tätä logiikkaa. 823 00:29:28,440 --> 00:29:32,420 Vaikka emme ole siirtymässä Neil yli, ja yli, ja yli, laittaa hänet 824 00:29:32,420 --> 00:29:36,420 missä hän menee, pahimmassa tapauksessa seuraava numero saatamme kohdata voitaisiin 825 00:29:36,420 --> 00:29:42,220 olla numero, eli siellä oli useita nolla, niin aiomme siirtää kaikki 826 00:29:42,220 --> 00:29:42,730 nämä kaverit. 827 00:29:42,730 --> 00:29:44,950 Oletetaan, että on olemassa useita, negatiivinen , sitten meidän täytyy siirtyä 828 00:29:44,950 --> 00:29:46,080 kaikki nämä kaverit. 829 00:29:46,080 --> 00:29:48,500 Olemme siis oikeastaan ​​vain sellainen käännetään ongelman ympärillä, niin että olemme 830 00:29:48,500 --> 00:29:52,620 siirtämällä kustannuksella alkaen valintaprosessi joten lisäys 831 00:29:52,620 --> 00:29:56,930 prosessi, niin että te vain oli liikkua karkeasti n miinus jotain 832 00:29:56,930 --> 00:29:57,940 useita vaiheita. 833 00:29:57,940 --> 00:30:01,200 Ja että useita vaiheita on vain menee kasvavan valitsen enemmän numeroita, 834 00:30:01,200 --> 00:30:04,730 jos minun täytyy pitää työntämään teitä takaisin, ja takaisin, ja takaisin. 835 00:30:04,730 --> 00:30:08,320 >> Niin surullista nyt on kaikki nämä algoritmit ovat n potenssiin. 836 00:30:08,320 --> 00:30:10,570 Mennään eteenpäin ja kiitos näistä kaverit, ja visualisoida nämä vähän 837 00:30:10,570 --> 00:30:11,090 eri tavalla. 838 00:30:11,090 --> 00:30:12,312 Hyvin tehty. 839 00:30:12,312 --> 00:30:14,120 >> [APPLAUSE] 840 00:30:14,120 --> 00:30:15,030 >> Selvä. 841 00:30:15,030 --> 00:30:16,280 Siellä mennään. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Kiitos - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [kuultavissa] pitää numerot. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Ei, voit pitää numerot samoin. 846 00:30:21,990 --> 00:30:23,440 Selvä. 847 00:30:23,440 --> 00:30:24,100 Hienosti tehty. 848 00:30:24,100 --> 00:30:25,300 Selvä. 849 00:30:25,300 --> 00:30:30,510 Katsotaanpa, jos emme voi nyt tiivistää nopeammin, ja visuaalisesti, 850 00:30:30,510 --> 00:30:33,410 mitä juuri tapahtui tässä seuraavasti. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Aion mennä eteenpäin ja vedä ylös Firefox. 853 00:30:38,770 --> 00:30:41,310 Liitämme tämän esittelyn kurssin verkkosivuilla. 854 00:30:41,310 --> 00:30:43,870 Java on vähän ärsyttävää saada työ Joissakin selaimissa näinä päivinä. 855 00:30:43,870 --> 00:30:46,760 Joten jos et pelata tätä kotona, ymmärtää, saatat joutua käyttämään Firefox 856 00:30:46,760 --> 00:30:47,990 saada se toimimaan. 857 00:30:47,990 --> 00:30:50,440 Ja mitä aion tehdä tämän esittelyä on seuraava. 858 00:30:50,440 --> 00:30:54,875 >> Alareunassa, minulla on koko joukko valikon vaihtoehdot, kuten alku-ja 859 00:30:54,875 --> 00:30:55,840 STOP-painiketta. 860 00:30:55,840 --> 00:30:59,450 Lisäksi, kuten syrjään, siellä näyttää olevan bug näissä ohjelmissa, jolloin voit 861 00:30:59,450 --> 00:31:03,720 ei voi itse nähdä alusta tai lopettaa painiketta ellet pidä Command tai Alt 862 00:31:03,720 --> 00:31:06,560 plus ja zoomaus, joka uteliaana näyttää enemmän painikkeita. 863 00:31:06,560 --> 00:31:09,090 Joten FYI jos pelaat tämän kotona. 864 00:31:09,090 --> 00:31:12,870 Nyt aion valitse Käynnistä vain hetkellä, kun määritellään viive, 865 00:31:12,870 --> 00:31:16,810 kuten 200 millisekuntia täällä, vain jotta voimme nähdä, mitä tapahtuu. 866 00:31:16,810 --> 00:31:20,180 >> Olen siis väittävät, että tämä on visualisointi Ensimmäisen algoritmin 867 00:31:20,180 --> 00:31:23,730 nämä kaverit tekivät, kupla lajitella, jolloin Vaihdoimme ihmiset pareittain. 868 00:31:23,730 --> 00:31:27,490 Keskeinen oivallus tähän visualisointi on se, että korkeus tankojen 869 00:31:27,490 --> 00:31:30,510 edustaa koko määrää. 870 00:31:30,510 --> 00:31:32,210 Joten pitempi palkki, isompi numero. 871 00:31:32,210 --> 00:31:33,680 Lyhyemmät baari, pienempi numero. 872 00:31:33,680 --> 00:31:38,630 Ja jos huomaat, olemme menossa läpi Ensimmäinen tämän algoritmin, 873 00:31:38,630 --> 00:31:42,620 vaihtamalla iso ja pieni määrä, jotta pieni määrä tulee ensin ja 874 00:31:42,620 --> 00:31:44,280 suuri määrä menee oikealle. 875 00:31:44,280 --> 00:31:48,770 >> Ja heti kun saamme loppuun array paljon enemmän numeroita kuin seitsemän, olemme 876 00:31:48,770 --> 00:31:49,900 menossa takaisin alkuun. 877 00:31:49,900 --> 00:31:51,140 Ja ennakoida tätä. 878 00:31:51,140 --> 00:31:54,860 Äärimmäisenä vasemmalla, että pikku kaveri on menossa vaihtaa puolelle, ja tämä 879 00:31:54,860 --> 00:31:56,010 prosessi toistuu. 880 00:31:56,010 --> 00:31:59,450 Nyt tämä visualisointi saa nopeasti tylsää, joten haluan mennä eteenpäin ja lopettaa 881 00:31:59,450 --> 00:32:04,170 , muuttaa viive jotain paljon nopeampi vain saada nyt tuntumaa 882 00:32:04,170 --> 00:32:05,060 tämä algoritmi. 883 00:32:05,060 --> 00:32:07,840 >> Joten vaikka olen nopeuttanut sitä, tämä on kuten päivittää minun prosessori, ostaa 884 00:32:07,840 --> 00:32:08,580 uusi tietokone. 885 00:32:08,580 --> 00:32:12,980 En ole olennaisesti muuttanut algoritmi, mutta voit todellakin nähdä enemmän 886 00:32:12,980 --> 00:32:16,800 selvästi kuin ihmisten kanssa, että iso numerot kuplii ylös, 887 00:32:16,800 --> 00:32:20,900 ja pienet numerot ovat kuplivaa pohjaan. 888 00:32:20,900 --> 00:32:22,390 Ja nyt tämä asia täällä järjestetty. 889 00:32:22,390 --> 00:32:25,260 Ja syrjään, toreilla, siellä vain joitakin kirjanpidon siellä 890 00:32:25,260 --> 00:32:28,010 auttaa laskemaan, kuinka monta vertailuja, tai kuinka monta swap on 891 00:32:28,010 --> 00:32:28,950 todella tehty. 892 00:32:28,950 --> 00:32:30,750 >> No, kokeile jotakin muut näimme. 893 00:32:30,750 --> 00:32:37,116 Saanen klikkaa kupla lajitella täällä, ja anna minun valita, ja tämä koko web-sivun 894 00:32:37,116 --> 00:32:38,936 on vähän buginen. 895 00:32:38,936 --> 00:32:41,155 Katsotaanpa hyväksyä riski ja käyttää sitä uudelleen. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Siellä mennään. 898 00:32:45,030 --> 00:32:47,180 Tehdäänpä valinta tavallaan. 899 00:32:47,180 --> 00:32:49,140 En tiedä miksi valikosta näkyy tuolla. 900 00:32:49,140 --> 00:32:54,070 Katsotaanpa zoomata vahvistaa, että bug, muuttaa 50. 901 00:32:54,070 --> 00:32:56,020 Ah, nyt itse tehdä että paljon nopeammin. 902 00:32:56,020 --> 00:32:59,160 Viisi millisekunnin, ja Start. 903 00:32:59,160 --> 00:33:00,470 >> Joten tämä on valinta tavallaan. 904 00:33:00,470 --> 00:33:03,070 Joten jälleen, miettiä, mitä me teki ihmisiin täällä. 905 00:33:03,070 --> 00:33:08,490 Kävimme läpi array ja valitut pienimmän alkion uudelleen, 906 00:33:08,490 --> 00:33:09,250 ja uudestaan, ja uudestaan. 907 00:33:09,250 --> 00:33:11,110 Nyt Väitän, että oli vielä melko huono. 908 00:33:11,110 --> 00:33:15,010 Se oli vielä n neliö, antaa tai ottaa, mutta se oli, todellisessa maailmassa, hieman 909 00:33:15,010 --> 00:33:18,280 nopeammin, koska olin todellakin ottaen hieman vähemmän vaiheita joka kerta. 910 00:33:18,280 --> 00:33:19,800 Mutta me vain puhumme mitä? 911 00:33:19,800 --> 00:33:21,830 Ehkä 40 tai niin baareissa täällä? 912 00:33:21,830 --> 00:33:23,200 Emme puhu 40 miljoonaa. 913 00:33:23,200 --> 00:33:27,430 Joten se ei ole täysin selvää, että oli todellakin merkittävä voitto. 914 00:33:27,430 --> 00:33:32,530 >> Anna minun mennä takaisin ja muuttaa meidän Kolmas algoritmi, joka valitaan 915 00:33:32,530 --> 00:33:33,180 lisäyslajittelu. 916 00:33:33,180 --> 00:33:36,380 Ja nyt se on todella buginen, koska valikko ei todellakaan pitäisi olla siellä. 917 00:33:36,380 --> 00:33:40,840 Joten nyt me vierittää takaisin tänne ja aloittaa tämän algoritmi. 918 00:33:40,840 --> 00:33:43,270 Huutaa, käynnistää ja pysäyttää. 919 00:33:43,270 --> 00:33:47,160 Joten tämä yhdenlaista on melko kuvio sen, jolloin olemme taas 920 00:33:47,160 --> 00:33:50,240 lisäämällä ihmisten tai Tällöin baareja osaksi 921 00:33:50,240 --> 00:33:52,620 niiden oikeassa paikassa. 922 00:33:52,620 --> 00:33:55,430 Ja se on jo tehnyt ennen Käännyin ympäri. 923 00:33:55,430 --> 00:33:58,940 Mutta myös tämä teoriassa on vielä n potenssiin. 924 00:33:58,940 --> 00:34:01,430 >> Katsotaanpa, jos emme voi tiivistää Näiden seuraavasti. 925 00:34:01,430 --> 00:34:04,750 Aion mennä eteenpäin ja vain antaa meille eräänlainen yhteinen tapa puhua 926 00:34:04,750 --> 00:34:08,489 näistä asioista, haluan esitellä vain vähän merkintätapa täällä. 927 00:34:08,489 --> 00:34:12,480 Olet tulleet niin sanotun suuren O, koska se on kirjaimellisesti iso 928 00:34:12,480 --> 00:34:16,320 O. Ja tämä on tapa, että tietokone tiedemies tai matemaatikko edes käyttää 929 00:34:16,320 --> 00:34:19,230 kuvaamaan käyntiaika Joidenkin algoritmi. 930 00:34:19,230 --> 00:34:21,400 Kuinka monta askelta se todella ottaa? 931 00:34:21,400 --> 00:34:25,080 >> Nyt aion nolata itseni kanssa minun käsialalla täällä vain hetken. 932 00:34:25,080 --> 00:34:29,020 Mutta haluan mennä eteenpäin ja sanoa, että tämä on iso O tänne. 933 00:34:29,020 --> 00:34:33,610 Ja haluan esitellä yksi muu symboli, pääoman omega. 934 00:34:33,610 --> 00:34:37,080 Omega tulee olemaan päinvastainen, lähinnä iso O. katsoo iso O 935 00:34:37,080 --> 00:34:40,790 välineet, pahimmassa tapauksessa, kuinka paljon aikaa saattaa joissakin algoritmi toteuttaa vuonna 936 00:34:40,790 --> 00:34:43,480 ehtojen n, omega on menossa olla kuinka paljon aikaa saattaa se 937 00:34:43,480 --> 00:34:45,409 ottaa parhaassa tapauksessa. 938 00:34:45,409 --> 00:34:48,090 Ja näemme, mitä me tarkoitamme Parhaassa tapauksessa vain hetken. 939 00:34:48,090 --> 00:34:49,940 >> Joten aloitetaan jotain yksinkertaista. 940 00:34:49,940 --> 00:34:54,719 Aloitan lineaarista hakua. 941 00:34:54,719 --> 00:34:55,679 Joten ei lajittelu. 942 00:34:55,679 --> 00:34:58,000 Me kutsumme tätä lineaarista hakua. 943 00:34:58,000 --> 00:35:01,140 Ja nyt, tehdä vähän taulukko pois tästä. 944 00:35:01,140 --> 00:35:06,600 Ja nyt, kun kyseessä on lineaarinen haku, pahimmassa tapauksessa, kuinka monta askelta on 945 00:35:06,600 --> 00:35:11,770 se vie minut löytää määrä mielivaltainen valinta? 946 00:35:11,770 --> 00:35:14,540 Ja siellä n yhteensä ovet tai n kokonaismäärät. 947 00:35:14,540 --> 00:35:15,940 Pahimmassa tapauksessa. 948 00:35:15,940 --> 00:35:18,800 Kuinka monta askelta olen menossa on ottaa löytää numeron 50 array 949 00:35:18,800 --> 00:35:20,830 n ovet? 950 00:35:20,830 --> 00:35:21,410 Ja miksi? 951 00:35:21,410 --> 00:35:23,680 Koska se voisi olla kaikki reilusti yli kiinni loppuun. 952 00:35:23,680 --> 00:35:27,120 Niin paljon kuin Jennifer kohdanneet, numero 50 oli aina yli, joten 953 00:35:27,120 --> 00:35:30,760 Pahimmassa tapauksessa lineaarinen haku on iso O n, me sanomme. 954 00:35:30,760 --> 00:35:33,430 >> Entä parhaassa tapauksessa jos saat todella onnekas? 955 00:35:33,430 --> 00:35:36,200 Se tekee vain ottaa yksi askel, tai jatkuvasti useita vaiheita. 956 00:35:36,200 --> 00:35:37,830 Joten me kuvataan, että 1. 957 00:35:37,830 --> 00:35:39,010 Joten tämä on melko hyvä. 958 00:35:39,010 --> 00:35:41,210 Nyt mitä jos teimme jotain kuten binäärihaku? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Joten binäärihaku pahimmassa tapauksessa kesti kuinka paljon aikaa? 961 00:35:47,846 --> 00:35:49,250 >> [Interposing ÄÄNTÄ] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Niin todella, minä kuullut sen pari paikkaa. 963 00:35:51,310 --> 00:35:56,390 Joten se on todella kirjautua n, antaa tai ottaa, koska sillä jaamme listan kahtia 964 00:35:56,390 --> 00:36:00,730 uudestaan, ja uudestaan, ja uudestaan, pystymme löytää lopulta arvosta, 965 00:36:00,730 --> 00:36:04,750 jos se on olemassa, mutta on kiinni. 966 00:36:04,750 --> 00:36:08,590 Mikä oletus, että meidän on itsestäänselvyytenä binary search? 967 00:36:08,590 --> 00:36:09,700 Se on järjestetty. 968 00:36:09,700 --> 00:36:12,770 Se ei ole lajiteltu, voit jakaa asia kahtia uudestaan ​​ja uudestaan, ja sinä 969 00:36:12,770 --> 00:36:15,490 voi mennä vasemmalle, ja voit mennä oikealle, ja voit mennä vasemmalle ja oikealle, mutta olet 970 00:36:15,490 --> 00:36:18,070 tule löytämään elementti, jos luetteloa ei lajitella, koska 971 00:36:18,070 --> 00:36:18,790 saatat menettää sen. 972 00:36:18,790 --> 00:36:22,120 Koska heuristinen menossa vasemmalle tai oikealle tulee olla virheellinen, jos se on 973 00:36:22,120 --> 00:36:23,420 todellakin ole lajiteltu. 974 00:36:23,420 --> 00:36:26,110 Niin siellä on tavallaan piilokustannuksia käyttämään jotain tällaista. 975 00:36:26,110 --> 00:36:29,250 >> Nyt mennään meidän lajittelu algoritmit etsimättä - 976 00:36:29,250 --> 00:36:31,140 oh, todella mennään tässä tyhjäksi. 977 00:36:31,140 --> 00:36:33,190 Binäärihaku parhaassa tapauksessa? 978 00:36:33,190 --> 00:36:36,290 Se on myös 1, jos se vain sattuu olemaan aivan keskellä array, tai 979 00:36:36,290 --> 00:36:37,810 keskellä puhelinluettelosta. 980 00:36:37,810 --> 00:36:39,710 Nyt tehdä kupla tavallaan. 981 00:36:39,710 --> 00:36:42,570 Joten jälleen, nyt olemme syöttämällä lajittelee, ei hakuja. 982 00:36:42,570 --> 00:36:47,220 >> Pahimmassa tapauksessa, kuinka monta askelta teimme väite kupla tavallaan vie? 983 00:36:47,220 --> 00:36:48,410 n potenssiin. 984 00:36:48,410 --> 00:36:49,200 Joten aion tehdä sen. 985 00:36:49,200 --> 00:36:51,710 Ooh, minun käsiala näyttää jopa pahempi kun se on ennustettu, että iso. 986 00:36:51,710 --> 00:36:52,510 Selvä. 987 00:36:52,510 --> 00:36:53,570 Niin, että N-potenssiin. 988 00:36:53,570 --> 00:36:59,460 Ja parhaassa tapauksessa kupla lajitella, kuinka monta askelta se aikoo ryhtyä? 989 00:36:59,460 --> 00:37:00,980 1, kuulin. 990 00:37:00,980 --> 00:37:01,760 >> Kaiutin 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, kuulin. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, kuulin. 994 00:37:05,010 --> 00:37:06,670 Kuulenko 3? 995 00:37:06,670 --> 00:37:07,080 Selvä. 996 00:37:07,080 --> 00:37:11,390 Niin olen kuullut 1 n, 2, mutta nyt valita lisäksi ainakin ensimmäinen näistä 997 00:37:11,390 --> 00:37:12,330 ehdotuksia, 1. 998 00:37:12,330 --> 00:37:15,370 Se ei ole huono vaisto, koska se Tällainen seuraa kuvio täällä. 999 00:37:15,370 --> 00:37:19,670 Mutta jos se kestää vain 1 askel, miten maailman voisin väittää, että luettelon 1000 00:37:19,670 --> 00:37:22,900 lajitellaan, koska jos olen vain sallittu ottaa 1 askel, kuinka monta elementtiä 1001 00:37:22,900 --> 00:37:25,230 voisin oikeastaan ​​varmista? 1002 00:37:25,230 --> 00:37:28,270 No, vain 1, mikä tarkoittaa, että on n miinus 1 seikkoja, jotka voisivat olla pois 1003 00:37:28,270 --> 00:37:31,310 järjestyksessä, ja olen juuri menossa uskoon jälkeen katsomalla 1 elementti, joka 1004 00:37:31,310 --> 00:37:31,850 asia on järjestetty. 1005 00:37:31,850 --> 00:37:33,930 Joten 1 ei ole korjata täällä. 1006 00:37:33,930 --> 00:37:35,710 Joten vähän, kuinka monta minun täytyy katsoa? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposing ÄÄNTÄ] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n miinus 1, tai oikeastaan, n, koska minun täytyy tarkastella jokaisen 1009 00:37:40,160 --> 00:37:42,190 elementti varmistaa, että se ei ole epäkunnossa. 1010 00:37:42,190 --> 00:37:44,750 Mutta jälleen kerran, me tavallaan aalto meidän kädet pienempi määrä ja 1011 00:37:44,750 --> 00:37:47,100 olettaa, että n saa suuria, ne ovat mielenkiinnoton muutenkin. 1012 00:37:47,100 --> 00:37:48,380 Niin, että kupla tavallaan. 1013 00:37:48,380 --> 00:37:49,830 Ja nyt, nyt nämä kaksi viimeistä. 1014 00:37:49,830 --> 00:37:53,520 Valinta lajitella ja niin me hyvitämme tehdä lisäyslajittelu. 1015 00:37:53,520 --> 00:37:57,160 Ja sitten me räjäyttää mielissä jotain paljon 1016 00:37:57,160 --> 00:37:58,926 parempi kuin kaikki nämä. 1017 00:37:58,926 --> 00:38:00,410 Selvä. 1018 00:38:00,410 --> 00:38:04,700 >> Mikä on pahin käynnissä valintahetkellä tavallaan? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n potenssiin. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n neliö, kuulen. 1021 00:38:06,710 --> 00:38:09,790 Mutta miksi n potenssiin, intuitiivisesti? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Koska me vain teimme sen. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Koska me vain teimme sen. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Hyvä vastaus. 1026 00:38:13,380 --> 00:38:16,660 Mutta intuitiivisesti, miksi valinta sort n potenssiin? 1027 00:38:16,660 --> 00:38:18,980 Mitä meidän on tehtävä uudestaan ​​ja uudestaan? 1028 00:38:18,980 --> 00:38:22,570 Meidän piti pitää skannauksen kautta, ovat olet pienin, oletko 1029 00:38:22,570 --> 00:38:24,020 pienin, oletko pienin. 1030 00:38:24,020 --> 00:38:27,480 Ja myönsi, pystyimme ottamaan n vaiheet, niin n miinus 1, niin n miinus 2. 1031 00:38:27,480 --> 00:38:30,700 Mutta jos sellainen lisätä ne kaikki ylös, tai ottaa sen uskon, että olen lisännyt 1032 00:38:30,700 --> 00:38:34,810 niitä etukäteen, saamme karkeasti n potenssiin miinus joitakin pienempiä numeroita. 1033 00:38:34,810 --> 00:38:36,730 Joten aion kutsua tätä n potenssiin. 1034 00:38:36,730 --> 00:38:39,530 Mutta valinta lajitella paras tapauksessa, kuinka monta askelta on se 1035 00:38:39,530 --> 00:38:40,632 vie minut? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [äänetön] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Se on valitettavasti vielä n potenssiin, eikö? 1038 00:38:44,350 --> 00:38:49,590 Koska jos olen valinnut pienin elementti, ja meillä oli seitsemän ihmistä täällä, 1039 00:38:49,590 --> 00:38:53,280 Tiedän vain, kun pääsen hyvin lopussa, että olen löytänyt pienin 1040 00:38:53,280 --> 00:38:55,670 numero, missä hän tai joutuneensa. 1041 00:38:55,670 --> 00:38:58,820 Mutta miten löydän seuraavan pienin määrä? 1042 00:38:58,820 --> 00:39:00,160 Minun täytyy tehdä toinen pass. 1043 00:39:00,160 --> 00:39:04,810 Joten parhaassa tapauksessa, mikä on valintamekanismille tavallaan? 1044 00:39:04,810 --> 00:39:07,830 Se on jo lajitteluluetteloon, numero yksi, numero kaksi, numero kolme, numero neljä. 1045 00:39:07,830 --> 00:39:08,600 Mutta olen tietokone. 1046 00:39:08,600 --> 00:39:10,190 Voin vain katsoa yksi asia kerrallaan. 1047 00:39:10,190 --> 00:39:12,465 En voi tavallaan ottaa askel takaisin kuin ihmisen ja sanoa, 1048 00:39:12,465 --> 00:39:14,030 ooh, tämä näyttää oikein. 1049 00:39:14,030 --> 00:39:17,580 >> Voin vain ratkaista oikeellisuus valinta lajitella valitsemalla 1050 00:39:17,580 --> 00:39:18,370 pienin määrä. 1051 00:39:18,370 --> 00:39:21,390 Mutta vaikka löydän ykkönen ensin, jos en tiedä mitään muuta 1052 00:39:21,390 --> 00:39:24,460 muut numerot, joita en ole, kaikki I tietää, että olen kulkenut array 1053 00:39:24,460 --> 00:39:27,930 tai joukko ovien takana, jotka ovat numerot, ainoa tapa Tiedän, että yksi 1054 00:39:27,930 --> 00:39:28,680 oli pienin? 1055 00:39:28,680 --> 00:39:32,440 Jos saan kaikki tänne ja ymmärtää, Hitto, yksi oli todellakin pienin. 1056 00:39:32,440 --> 00:39:34,870 >> Mutta miten voin sitten päättää, että kaksi on seuraavaksi pienin? 1057 00:39:34,870 --> 00:39:38,350 Tekemällä sama tehottomuus uudelleen ja uudelleen. 1058 00:39:38,350 --> 00:39:42,210 Joten lopuksi, jossa lisäyslajittelu, miten, pahimmassa tapauksessa, 1059 00:39:42,210 --> 00:39:44,990 Sanoimmeko se toimii? 1060 00:39:44,990 --> 00:39:49,100 Sekin on n potenssiin. 1061 00:39:49,100 --> 00:39:53,020 Ja miten paras asia? 1062 00:39:53,020 --> 00:39:56,282 Jätämme että jännitysnäytelmä. 1063 00:39:56,282 --> 00:40:00,090 Me täyttää että tyhjä seuraavan kerran, mutta haluan ensin ehdottaa, että 1064 00:40:00,090 --> 00:40:02,620 pohjimmiltaan tehdä paremmin kuin kaikki nämä, okei? 1065 00:40:02,620 --> 00:40:05,220 >> Ajattele itse, mitä paikoilleen sort tulee olemaan. 1066 00:40:05,220 --> 00:40:06,910 No, se ei ollut kovin dramaattinen, koska olen vain yksi 1067 00:40:06,910 --> 00:40:08,970 että näki muutoksen. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Joten tässä meillä on hieman eri esittelyä. 1071 00:40:12,615 --> 00:40:16,580 Jos minä suurentaa täällä, näet, että Vasemmalla on kupla lajitella, vuonna 1072 00:40:16,580 --> 00:40:20,740 keskellä meillä on valikoima lajitella, ja äärioikeisto, olemme me 1073 00:40:20,740 --> 00:40:23,380 ole katsonut vielä nimeltään yhdistää tavallaan. 1074 00:40:23,380 --> 00:40:26,080 Ajatelkaa mitä olemme olleet teet täällä tähän mennessä tänään. 1075 00:40:26,080 --> 00:40:29,200 Kun Jennifer ensimmäinen tuli lavalle, kävimme läpi joukko numeroita 1076 00:40:29,200 --> 00:40:33,750 uudestaan, ja uudestaan, lineaarinen haku, ja saimme lineaarinen käyntiaika, iso O 1077 00:40:33,750 --> 00:40:35,100 n, niin sanoakseni. 1078 00:40:35,100 --> 00:40:41,000 >> Kun me nyt harkita ensimmäisellä viikolla luokka, kun olimme hajoita ja hallitse, 1079 00:40:41,000 --> 00:40:43,740 ja meillä oli puhelinluettelon repiminen, ja Jennifer, ja me yhdessä 1080 00:40:43,740 --> 00:40:47,500 velkarahalla, että keskeiset oivallus, joka oli toista itseäsi uudestaan ​​ja uudestaan 1081 00:40:47,500 --> 00:40:50,930 jotenkin heittää pois, heittää pois, heittää pois, puolet ongelma tai 1082 00:40:50,930 --> 00:40:55,320 yleisesti, jakamalla ongelma puoli, ja sitten käsittelemällä pienempi pala 1083 00:40:55,320 --> 00:40:59,630 ongelma käsitteellisesti vastaa Muihin me jotenkin pallo 1084 00:40:59,630 --> 00:41:00,910 pohjimmiltaan paremmin. 1085 00:41:00,910 --> 00:41:04,720 Mutta kupla lajitella, jossa valinta lajitella, jossa lisäyslajittelu, olemme voi 1086 00:41:04,720 --> 00:41:06,560 tällaisia ​​oivalluksia että Jennifer teki. 1087 00:41:06,560 --> 00:41:10,220 Olemme aika paljon vain käveli takaisin ja esiin koko joukko kertaa, ja me 1088 00:41:10,220 --> 00:41:12,650 viritetty asioita hieman, vaihtamalla tässä järjestyksessä, ehkä 1089 00:41:12,650 --> 00:41:13,730 lisäämällä tai valitsemalla. 1090 00:41:13,730 --> 00:41:16,950 Mutta loppujen lopuksi, tein paljon hankala kävely edestakaisin. 1091 00:41:16,950 --> 00:41:21,160 Meillä ei oikeastaan ​​hyödyntää jotain älykäs kuten Jennifer teki kuten jakamalla 1092 00:41:21,160 --> 00:41:22,040 ja valloitusta. 1093 00:41:22,040 --> 00:41:25,620 >> Joten yhdistää lajitella, sen sijaan, jota eivät näe vasta ensi viikolla, se menee 1094 00:41:25,620 --> 00:41:29,540 hyödyntää, että keskeinen ajatus jakamalla tulo, ja sitten puolittaa, ja sitten 1095 00:41:29,540 --> 00:41:30,580 puolittaa, ja sitten puolittaa. 1096 00:41:30,580 --> 00:41:34,590 Ja jokaisen iteraation että silmukka, lajittelu vasen puoli ja oikea 1097 00:41:34,590 --> 00:41:38,200 puoli, sitten vasen puoli on vasen puoli, ja oikealla puolella vasemmalle, sitten 1098 00:41:38,200 --> 00:41:40,990 vasen puoli oikea puoli, ja oikea puoli oikea puoli. 1099 00:41:40,990 --> 00:41:42,840 Ja toistamalla uudestaan ​​ja uudestaan. 1100 00:41:42,840 --> 00:41:46,170 >> Niin näet tämän visuaalisesti, mutta tämä on mitä odottaa meitä ensi viikolla. 1101 00:41:46,170 --> 00:41:49,760 Ja yleensä, kun ajattelemme hieman vähän kovemmin tällaisia ​​ongelmia. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Meillä on n potenssiin vasemmalla n potenssiin keskellä, ja n 1104 00:41:57,970 --> 00:41:59,400 log n oikealla. 1105 00:41:59,400 --> 00:42:00,590 Joten siellä on todellinen jännitysnäytelmä. 1106 00:42:00,590 --> 00:42:02,040 Nähdään maanantaina. 1107 00:42:02,040 --> 00:42:05,163 >> [APPLAUSE]