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]