1 00:00:00,000 --> 00:00:11,100 >> [Predvajanja glasbe] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan V redu. 3 00:00:11,490 --> 00:00:12,170 Torej, dobrodošli nazaj. 4 00:00:12,170 --> 00:00:15,180 To je CS50, in je koncu tretjega tedna. 5 00:00:15,180 --> 00:00:17,770 >> Tako opozarjajo v zadnjih nekaj tednih, smo se porabi zelo malo 6 00:00:17,770 --> 00:00:20,820 Čas na C, v programiranju, o skladnji. 7 00:00:20,820 --> 00:00:24,680 In to je povsem normalno, če ste še vedno bori s Problem Set 2, se 8 00:00:24,680 --> 00:00:25,950 razbijati glavo ob zid. 9 00:00:25,950 --> 00:00:28,310 To je skrivnosten usmerjene sporočil o napakah in napake, ki jih 10 00:00:28,310 --> 00:00:29,220 ne more povsem lovil. 11 00:00:29,220 --> 00:00:32,310 Ker, prepričani, da je v pravkar čas nekaj tednov boste ozrli nazaj na 12 00:00:32,310 --> 00:00:35,930 stvari, kot Cezar, in [? V-genair,?] morda celo Crack in 13 00:00:35,930 --> 00:00:40,050 zavedajo, kako daleč ste prišli v kratkem času. 14 00:00:40,050 --> 00:00:43,670 Torej, če je to v tolažbo, potrpi za zdaj. 15 00:00:43,670 --> 00:00:46,610 >> Danes, čeprav smo začeli prehod da stvari višjo raven. 16 00:00:46,610 --> 00:00:49,820 In smo začeli jemati za samoumevno, da veste, kako program, ali 17 00:00:49,820 --> 00:00:52,090 Najmanj začetki da je raven udobja. 18 00:00:52,090 --> 00:00:56,520 In bomo začeli razmisliti, kako smo lahko iti o oblikovanju programov več 19 00:00:56,520 --> 00:00:57,440 učinkovito. 20 00:00:57,440 --> 00:01:01,090 Kako lahko greste o optimizaciji Učinkovitost naših algoritmov in 21 00:01:01,090 --> 00:01:03,110 splošno reševanje več zanimivih problemov. 22 00:01:03,110 --> 00:01:06,850 In začetek samoumevno, da če bi želeli, bi lahko kodo gor koli 23 00:01:06,850 --> 00:01:08,350 od primerov, ki jih imamo v mislih. 24 00:01:08,350 --> 00:01:11,430 Torej danes, ne bomo se dotaknete tipkovnice za kakršno koli obliko kode. 25 00:01:11,430 --> 00:01:15,150 To bo precej višji ravni, in navsezadnje, o reševanju problemov. 26 00:01:15,150 --> 00:01:20,490 >> Torej, da bi prišli do te točke, naj predlaga da naslednjih sedmih 27 00:01:20,490 --> 00:01:24,290 pravokotniki predstavljajo sedem vrata, zadaj ki so cel kup 28 00:01:24,290 --> 00:01:26,340 številke, med katerimi je številka 50. 29 00:01:26,340 --> 00:01:30,470 Dovolite mi, da je to projekt na tem zaslon tudi tukaj. 30 00:01:30,470 --> 00:01:36,770 In predlaga, da potrebujemo prostovoljca pomoč pri iskanju mi ​​številko pred 31 00:01:36,770 --> 00:01:38,140 internet tu za ogled. 32 00:01:38,140 --> 00:01:40,755 Pridi gor, v roza barvi. 33 00:01:40,755 --> 00:01:43,050 Vse je v redu. 34 00:01:43,050 --> 00:01:43,930 Kako ti je ime? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [neslišno] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Oprostite? 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 Vse je v redu, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Lepo, da sva se spoznala. 41 00:01:47,630 --> 00:01:48,370 Pridi gor. 42 00:01:48,370 --> 00:01:52,430 Torej, to tukaj je sedem vrata, in kaj Rad bi, da narediš za nas, 43 00:01:52,430 --> 00:01:56,560 pred vsemi sošolci, se zdi nam, številko 50. 44 00:01:56,560 --> 00:02:00,860 Če želite najti številko, lahko pokukati za vas vsaka od teh vrat s preprostim dotikom 45 00:02:00,860 --> 00:02:03,030 na eno stran vrat, in to bo razkrila svojo številko. 46 00:02:03,030 --> 00:02:06,080 In da vidimo, kako hitro nam lahko najdem številko 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 Lepo opravljeno. 54 00:02:17,350 --> 00:02:18,040 Vse je v redu. 55 00:02:18,040 --> 00:02:19,906 Aplavz za Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [APLAVZ] 57 00:02:21,530 --> 00:02:22,320 >> Vse je v redu. 58 00:02:22,320 --> 00:02:25,254 Torej, kaj je vaša strategija za najti številko, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Hm, sem mislil, če - 60 00:02:27,222 --> 00:02:27,714 [Neslišno] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Daj mu eno sekundo. 63 00:02:29,630 --> 00:02:32,420 Torej je bila vaša strategija za najti številko, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Torej sem začela ob že videli, kaj je prva številka 65 00:02:34,760 --> 00:02:38,590 je bil, potem pa sem mislil, mogoče če oni so razporejene, bom samo nadaljuj 66 00:02:38,590 --> 00:02:39,970 prisluškovanje višje? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 In zdi se, da so ugotovili, , da bi bilo tako. 69 00:02:42,910 --> 00:02:45,670 Čeprav, kaj je lupina nazaj plasti Samo malo, in želite, da gredo 70 00:02:45,670 --> 00:02:47,640 naprej in se razkrivajo druga vrata lahko bi izbrali? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, draga. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Torej, pravkar sem srečen. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Torej imaš srečo. 76 00:02:55,270 --> 00:02:55,710 Vse je v redu. 77 00:02:55,710 --> 00:02:56,795 Torej ni slabo. 78 00:02:56,795 --> 00:02:58,750 Ampak to je zanimivo vpogled, kajne? 79 00:02:58,750 --> 00:03:01,870 Če se domneva, in si zaslužiti, res, malo srečen tam. 80 00:03:01,870 --> 00:03:05,350 Ampak, če domnevamo, da so bile številke razporejene, ste lahko bolj natančni 81 00:03:05,350 --> 00:03:08,750 , kako, da vplivajo tvoje obnašanje? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Torej, če so bile razporejene sem Mislil najmanjših do največjih. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Ali pa, če je ta končal pa res velik, potem največjih do najmanjših. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Torej največjih do najmanjših, ali najmanjših do največjih. 87 00:03:18,170 --> 00:03:21,990 Ampak naj predlagajo, da ste imeli gotten sreče, in domnevam, da so 88 00:03:21,990 --> 00:03:26,840 niso bili v resnici, razporejene, koliko ta vrata ste morda moral pokukati 89 00:03:26,840 --> 00:03:28,590 zadaj v tem najslabšem primeru? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Vsi izmed njih. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Vsi izmed njih. 92 00:03:30,420 --> 00:03:31,740 Torej, kaj je posploševati, da so n. 93 00:03:31,740 --> 00:03:34,790 Se zgodi, da bo 7, vendar naj bolj na splošno reči, tam je n vrata na 94 00:03:34,790 --> 00:03:35,650 Zaslon tukaj. 95 00:03:35,650 --> 00:03:40,110 Torej, v najslabšem primeru pa bi morali pogledati za 7 vrat ali N vrata. 96 00:03:40,110 --> 00:03:44,140 In tako je to res, da je malo sreče danes, ampak to je res linearna 97 00:03:44,140 --> 00:03:46,440 algoritem z menoj, čeprav ste so bili nekako preskoči okoli. 98 00:03:46,440 --> 00:03:47,080 Je to pošteno? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ja. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: No, da vidim, če vaš Strategija spremembe, če sem se gibljejo do nas 101 00:03:50,000 --> 00:03:52,190 naš drugi primer tukaj z 7 različnih vrata. 102 00:03:52,190 --> 00:03:55,240 Same številke, vendar je to ko so razporejene. 103 00:03:55,240 --> 00:03:58,350 Kakšna je vaša strategija tu bo, poskuša dati ven iz svojega uma, kar 104 00:03:58,350 --> 00:03:59,310 druge številke so - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - prej? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Začnimo s prvo. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan V redu. 109 00:04:03,540 --> 00:04:05,190 Začnite s prvo. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Zdaj, če boš šel in zakaj? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4, je res majhen. 113 00:04:10,040 --> 00:04:12,500 Torej, če si neke morda najmanjši da največji, morajo to 114 00:04:12,500 --> 00:04:13,290 se dvakrat, in -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Poglejmo, katere misliš? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Poskusite zadnjega. 118 00:04:19,050 --> 00:04:19,500 Lepo. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Zelo lepo opravljeno. 120 00:04:20,880 --> 00:04:21,860 Vse je v redu. 121 00:04:21,860 --> 00:04:23,010 >> [APLAVZ] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Torej ste pravzaprav počne to strašno, ker si 124 00:04:26,790 --> 00:04:27,700 to počne zelo dobro. 125 00:04:27,700 --> 00:04:31,150 Ki nas pusti more nekatere točke. 126 00:04:31,150 --> 00:04:32,565 Torej poskusimo roll nazaj. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Zelo dobro narediti, vseeno. 129 00:04:35,980 --> 00:04:39,060 Torej ste začeli na začetku, ste videli, da je bil 4., potem 130 00:04:39,060 --> 00:04:40,240 premakne na konec. 131 00:04:40,240 --> 00:04:42,320 Ampak predvidevam, da niste dobili srečo tam, in domnevam 50 132 00:04:42,320 --> 00:04:42,890 je bil nekje drugje. 133 00:04:42,890 --> 00:04:46,190 Kaj je tvoj Tretji korak je bilo? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Pojdite nazaj na začetek. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Pojdi nazaj na začetku. 136 00:04:48,320 --> 00:04:51,320 OK, tako da bi si dotaknil ta vrata, ki je 8. 137 00:04:51,320 --> 00:04:51,660 Vse je v redu. 138 00:04:51,660 --> 00:04:52,650 Torej to ni 50. 139 00:04:52,650 --> 00:04:55,380 Kje bi si pogledal naslednji? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Če nisem vedeli so razporejene. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Pravilno. 142 00:04:57,005 --> 00:04:58,490 No, če si vedel so razporejene - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, vedel, ja. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: -, vendar si ne vem, kje je še 50? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Samo nadaljuj. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan V redu. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Nadaljuj. 149 00:05:03,800 --> 00:05:05,270 OK, da ne morem delati. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Zdaj, če ste pravkar dogaja, da se dogaja, kaj je tvoj 152 00:05:07,210 --> 00:05:09,680 algoritem, ki se prenašajo stisnil v. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: linearna -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: To je nekako linearno. 155 00:05:11,820 --> 00:05:13,480 Ampak naj predlagajo, naj me je dal na kraju samem. 156 00:05:13,480 --> 00:05:14,900 Dovolite mi, da osvežite stran. 157 00:05:14,900 --> 00:05:17,120 Enako število, enako ureditev, ista vrata. 158 00:05:17,120 --> 00:05:21,350 Ampak pomislite na ta prvi dan razred, ko smo trgali imenik, v 159 00:05:21,350 --> 00:05:25,480 pol, nekako, in kaj je bilo Naša strategija je? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Začnite na sredini. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Torej, začeti na sredini. 163 00:05:27,610 --> 00:05:28,790 Torej, gremo naprej in simulira to. 164 00:05:28,790 --> 00:05:30,720 Začnite na sredini razkrivajo ta vrata. 165 00:05:30,720 --> 00:05:31,660 Torej številka 16. 166 00:05:31,660 --> 00:05:35,290 Torej, kaj bi naredil močan fant, ki strgal telefonski imenik na pol, 167 00:05:35,290 --> 00:05:38,450 priti na naslednjo ugibati? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Pojdi v tej polovici. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: In zakaj na desni? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Če bi bile nekakšen najmanjši do največjega, nato 50 mora biti 171 00:05:43,900 --> 00:05:44,720 v ta namen. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Dobro. 173 00:05:44,920 --> 00:05:45,390 Povsem razumno. 174 00:05:45,390 --> 00:05:48,380 Tako kot telefonski imenik, greš na prav v nasprotju z leve strani, vendar tukaj 175 00:05:48,380 --> 00:05:49,500 je ključna hrana za s seboj. 176 00:05:49,500 --> 00:05:53,930 Sedaj lahko vrgel proč, ali odtrgajte, polovica tega problema, kar vam bo pustilo ne 177 00:05:53,930 --> 00:05:55,970 s 7 vrata, ampak res samo z 3. 178 00:05:55,970 --> 00:05:57,870 Kar je približno polovica velikost problema. 179 00:05:57,870 --> 00:05:58,350 Vse je v redu. 180 00:05:58,350 --> 00:06:01,890 Torej, kaj zdaj bi morali storiti, ko gremo desno? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Torej, 16 je še vedno zelo majhen, v primerjavi z 50, tako da morda bom poskusil, 182 00:06:05,870 --> 00:06:06,700 podobno, je ta. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan V redu. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Vse je v redu, tako da zdaj kaj je vaša instinkt vam pove? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Lahko mečejo to nato le - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Dobro, lahko mečejo levo polovico tam. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - izberite to. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: In prav. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ja. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Torej, čeprav je težko da vidim, morda, če obstaja samo 193 00:06:17,820 --> 00:06:21,320 7 vrata, pomislite, zdaj, doslednost 194 00:06:21,320 --> 00:06:22,620 algoritem, ki ste jo pravkar uporabljali. 195 00:06:22,620 --> 00:06:24,510 V prejšnjem primeru, da si posreči, kar je super. 196 00:06:24,510 --> 00:06:26,540 Ampak si uporabite hevristično, Jaz bi rekel. 197 00:06:26,540 --> 00:06:29,150 Uporabili ste nekako instinktom, in vedoč, da je urejeno, če je to precej 198 00:06:29,150 --> 00:06:31,600 majhne na začetku, seveda, ki smo jih Moram iti bolj v desno. 199 00:06:31,600 --> 00:06:34,990 Toda v nekem smislu imaš srečo, ker je mogoče to številko 100, 200 00:06:34,990 --> 00:06:36,220 in morda 50 je bil bolj v sredini. 201 00:06:36,220 --> 00:06:37,910 Mogoče 50 je bil celo tukaj. 202 00:06:37,910 --> 00:06:40,960 >> Ampak kaj si naredil malo drugače je bil to čas, da si isto stvar 203 00:06:40,960 --> 00:06:42,150 znova in znova. 204 00:06:42,150 --> 00:06:45,310 In trdim, da tisto, kar ste pravkar ni, čeprav vplivajo na telefonu 205 00:06:45,310 --> 00:06:48,100 Knjiga primer, je nekaj veliko več algoritmično, in še veliko 206 00:06:48,100 --> 00:06:49,930 manj posebna opazoval. 207 00:06:49,930 --> 00:06:51,620 Veliko manj nagonsko. 208 00:06:51,620 --> 00:06:57,160 Torej, na koncu dneva, kako bi opišete učinkovitost 209 00:06:57,160 --> 00:07:00,530 Prvi algoritem, kjer ste šli od leve proti desni, v primerjavi 210 00:07:00,530 --> 00:07:03,430 Drugi algoritem tukaj? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: To bi moral biti eden, kot je, morda polovico zmanjša čas, ali celo več, ja. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, morda celo več. 213 00:07:07,320 --> 00:07:10,150 Oglejmo potisnite malo težje na to. 214 00:07:10,150 --> 00:07:13,030 Kaj res, če bomo še naprej to logika, bomo zagotovo prepolovila 215 00:07:13,030 --> 00:07:15,830 teče čas s tem drugim algoritmom ga vrgel proč polovico 216 00:07:15,830 --> 00:07:18,470 številke, ampak kaj smo storili na naslednji ponovitev, ko je Jennifer razkrila 217 00:07:18,470 --> 00:07:20,615 druga številka? 218 00:07:20,615 --> 00:07:22,830 >> Ponovno smo prepolovili števila vrat. 219 00:07:22,830 --> 00:07:25,270 In kaj potem smo naredili po tem, če je bilo več vrat, da igrajo z? 220 00:07:25,270 --> 00:07:27,520 Mi bi jih prepolovili, in spet, znova in znova. 221 00:07:27,520 --> 00:07:30,420 In to je ravno tako kot vama vse stoje v prvem tednu 222 00:07:30,420 --> 00:07:33,000 razred, pol si sedel, pol od vas sedel, pol vas 223 00:07:33,000 --> 00:07:35,440 sedel, dokler eden od lone Duša je stal. 224 00:07:35,440 --> 00:07:39,050 In mi je rekel, da čas teče da je število korakov je trajalo 225 00:07:39,050 --> 00:07:40,430 o vrstnem redu kaj? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [neslišno] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Torej dnevnik baza 2 n, ali pa bolj enostavno, da se prijavite na n. 228 00:07:43,970 --> 00:07:45,060 Torej, kaj logaritemsko. 229 00:07:45,060 --> 00:07:48,380 In graf ni ravna črta da bo še slabši in slabši, je bilo 230 00:07:48,380 --> 00:07:52,490 Ta zanimiva krivulja, ki ni dobili tako slabo daljšem časovnem obdobju. 231 00:07:52,490 --> 00:07:53,910 Torej, da imajo na tej ideji. 232 00:07:53,910 --> 00:07:54,690 Oglejmo hvala Jennifer. 233 00:07:54,690 --> 00:07:56,150 Hvala, da si prišel gor. 234 00:07:56,150 --> 00:07:57,400 In ena sek. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Ni desk svetilke danes, vendar smo pa imajo CS50 stres kroglice. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Bravo. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: V redu, tukaj. 239 00:08:04,410 --> 00:08:06,545 Zahvaljujemo se vam za nastale Stres tukaj. 240 00:08:06,545 --> 00:08:07,350 Vse je v redu. 241 00:08:07,350 --> 00:08:10,620 Torej, da vidimo, če ne moremo zdaj To formalizira malo več. 242 00:08:10,620 --> 00:08:14,820 Torej še enkrat, kaj smo pravkar storil, je bilo v bistvu ista stvar kot smo 243 00:08:14,820 --> 00:08:16,660 V tem prvem tednu. 244 00:08:16,660 --> 00:08:23,780 Toda namesto konca s samo linearno Algoritem, ki jo je prikazano 245 00:08:23,780 --> 00:08:27,210 prej kot to premico, pri čemer, če bi dal še eno vrat 246 00:08:27,210 --> 00:08:29,610 zaslon, nato Jennifer bi moral pogledati, potencialno 247 00:08:29,610 --> 00:08:30,600 zadaj še ena vrata. 248 00:08:30,600 --> 00:08:33,490 Če smo se še dve vrati, je morda da si za dve vrata. 249 00:08:33,490 --> 00:08:35,990 >> Tako je bilo to linearna razmerje med velikostjo 250 00:08:35,990 --> 00:08:39,059 Problem na, recimo, na x-osi, in Količina časa, ki je potreben za 251 00:08:39,059 --> 00:08:40,440 rešiti na y. 252 00:08:40,440 --> 00:08:43,330 Ampak slike sem namiguje na prej je bila ta zelena črta. 253 00:08:43,330 --> 00:08:45,970 Zelena namerno, ker to šele počutil bolje. 254 00:08:45,970 --> 00:08:49,790 V teoriji, algoritem, ko nam je uspelo z imeniku, ko nam je uspelo 255 00:08:49,790 --> 00:08:52,420 z vidva štetje seboj, in V drugem primeru, ko Jennifer samo 256 00:08:52,420 --> 00:08:55,250 Uspelo ti je tukaj gor, to je neke za bistveno bolje. 257 00:08:55,250 --> 00:08:57,180 Ker to ni bila samo dvakrat hitreje. 258 00:08:57,180 --> 00:08:58,870 Ni bilo celo štirikrat hitro. 259 00:08:58,870 --> 00:09:03,290 Bilo je povsem odvisna od tega, kaj velikost vhodu je, o tem, koliko 260 00:09:03,290 --> 00:09:05,220 ukrepe, ki jih na koncu vzel. 261 00:09:05,220 --> 00:09:08,040 >> In tako je to preprosto idejo, da smo vsi vzel za odobrene z imenika, 262 00:09:08,040 --> 00:09:10,200 Podobno se lahko uporablja za kaj takega. 263 00:09:10,200 --> 00:09:12,380 In to bi bilo bolj mimogrede znani kot, kot si morda 264 00:09:12,380 --> 00:09:13,940 predstavljate, deli in vladaj. 265 00:09:13,940 --> 00:09:16,390 Ni razliko kar smo seveda z imeniku. 266 00:09:16,390 --> 00:09:18,300 >> Ampak psevdokoda, odpoklic, je bilo to. 267 00:09:18,300 --> 00:09:21,800 Tako da ne bo to naredil še enkrat, ampak spomni da je prvi teden, vse nas je vstal 268 00:09:21,800 --> 00:09:25,140 in potem polovica vas usedel, polovica si se usedel, polovica vas sedel. 269 00:09:25,140 --> 00:09:29,280 Ta algoritem je bil izveden v malo goljufanja način, s tem, da 270 00:09:29,280 --> 00:09:32,870 ni bil le eden od mene štetja, bistveno bolj učinkovito. 271 00:09:32,870 --> 00:09:35,830 V tem primeru sem vplivno sekundarni vir. 272 00:09:35,830 --> 00:09:39,470 Nekako, več procesorjev, več možgani, več pametnih ljudi 273 00:09:39,470 --> 00:09:42,740 Prostor so mi pomagali priti iz nečesa linearno na nekaj 274 00:09:42,740 --> 00:09:45,190 logaritemska, od nečesa rdeča za nekaj zelene barve. 275 00:09:45,190 --> 00:09:48,650 >> Ampak v tem primeru, ne more sam Jennifer bistveno izboljšati 276 00:09:48,650 --> 00:09:52,370 uspešnost svojega prvega algoritma, ki ga, še enkrat, samo razmišljanje malo težje. 277 00:09:52,370 --> 00:09:56,650 Sedaj, ko pride čas za izvedbo te stvari, ugotoviti 278 00:09:56,650 --> 00:10:00,670 kaj vrstic kode lahko pišete na primer ki jih lahko ponovite še enkrat, in 279 00:10:00,670 --> 00:10:03,350 znova in znova, nekako v krožnem način. 280 00:10:03,350 --> 00:10:06,370 Ker ne boš šel, da imajo luksuz, kot je Jennifer storila na eni strani, 281 00:10:06,370 --> 00:10:10,460 samo še cel kup investicijskih skladov in pravijo, hmm, če je to prva številka 4, 282 00:10:10,460 --> 00:10:11,800 Naj skok vse do konca. 283 00:10:11,800 --> 00:10:14,180 Oh, če je ta številka je prevelika, Naj premakniti samovoljno nazaj 284 00:10:14,180 --> 00:10:15,220 z drugim elementom. 285 00:10:15,220 --> 00:10:18,210 Boste ugotovili, da se dogaja, da je veliko težje formalizirati, kaj smo ljudje 286 00:10:18,210 --> 00:10:21,270 samoumevno kot zelo razumen tolči, ampak računalnik je le 287 00:10:21,270 --> 00:10:23,260 naredili tisto, kar je povedal, da ne. 288 00:10:23,260 --> 00:10:25,280 >> Zdaj to je zelo zanimivo posledice. 289 00:10:25,280 --> 00:10:29,950 Ta graf je nekako pomenilo, da nekako preplavijo vizualno, ampak obvestilo, kjer je 290 00:10:29,950 --> 00:10:32,230 je premica v grafu? 291 00:10:32,230 --> 00:10:35,330 Kje je linearen graf , ki ga imenujemo n? 292 00:10:35,330 --> 00:10:37,580 No, to je nekako proti dnu te slike, kajne? 293 00:10:37,580 --> 00:10:40,500 Torej, vse smo naredili, je, ki smo jih nekako pomanjšana na x-osi in 294 00:10:40,500 --> 00:10:44,780 y-os, da bi poskušali dobiti občutek, kaj druge vrste krivulj izgledal. 295 00:10:44,780 --> 00:10:47,760 >> In posebnosti matematično Izrazi danes ne bo pomembno, da 296 00:10:47,760 --> 00:10:52,440 veliko, ampak obvestilo, da obstaja veliko algoritmi, ki so slabša od 297 00:10:52,440 --> 00:10:53,470 nekaj, kar je linearna. 298 00:10:53,470 --> 00:10:55,410 Dejansko n kubikov izgleda precej slabo. 299 00:10:55,410 --> 00:10:58,400 2 do n izgleda precej slabo. n kvadrat izgleda precej slabo. 300 00:10:58,400 --> 00:11:01,630 In bomo videli, kaj nekateri od tistih, Morda je v resnici še danes. 301 00:11:01,630 --> 00:11:05,430 In log n ne počuti tako slabo, vendar bolje kot je n dnevnik baza 2 n. 302 00:11:05,430 --> 00:11:08,080 Ampak veste, bi bilo še bolj neverjetno, če Jennifer, ali pa če mi, 303 00:11:08,080 --> 00:11:12,910 da je prvi teden, je prišel do nekaj, kar je log log n. 304 00:11:12,910 --> 00:11:15,880 >> Torej, z drugimi besedami, da je to celo spekter možnih rešitvah 305 00:11:15,880 --> 00:11:18,570 težave, ampak tudi tu obvestilo kaj se bo zgodilo. 306 00:11:18,570 --> 00:11:22,910 Ko sem pomanjšati, katera od teh krivulj se bo izkazalo, da je absolutna 307 00:11:22,910 --> 00:11:26,630 najslabše od tiste na zaslonu sedaj? 308 00:11:26,630 --> 00:11:28,680 Torej n kubikov izgleda precej slab v tem trenutku. 309 00:11:28,680 --> 00:11:32,470 Ampak, če bomo pomanjšati in si oglejte več x in y os, ki bo 310 00:11:32,470 --> 00:11:34,550 prevladujejo na koncu? 311 00:11:34,550 --> 00:11:37,120 Torej je dejansko izkazalo, da je 2 do n, in lahko to ugotovite le s 312 00:11:37,120 --> 00:11:39,990 priklopom na nekaterih vedno veliko številke, in boste videli, da od 2 do 313 00:11:39,990 --> 00:11:42,070 n, dejansko postane večji veliko hitreje. 314 00:11:42,070 --> 00:11:45,530 Če bomo res pomanjšati, je 2 do n algoritem popolnoma zanič. 315 00:11:45,530 --> 00:11:48,170 Mislim, to se dogaja, da sprejmejo zelo malo časa za 316 00:11:48,170 --> 00:11:49,460 Računalnik churn skozi. 317 00:11:49,460 --> 00:11:52,500 >> Ampak boste videli čez čas, še posebej, s prihodnjimi problematičnih sklopov in celo 318 00:11:52,500 --> 00:11:55,600 končni projekti, so vaši podatki set dobi velik, prav? 319 00:11:55,600 --> 00:11:58,300 Tudi v prvi različici Facebooku kot število prijateljev, in 320 00:11:58,300 --> 00:12:01,840 Število registriranih uporabnikov dobil velik, lahko nekako it v telefon in 321 00:12:01,840 --> 00:12:05,530 izvesti nekaj z linearno iskanje, ali zelo preprosta sortiranje 322 00:12:05,530 --> 00:12:07,030 algoritem, kot bomo videli danes. 323 00:12:07,030 --> 00:12:09,280 Moraš začeti razmišljati težje in težje o teh problemih. 324 00:12:09,280 --> 00:12:12,070 In vrste težave krajih, kot so Facebook in Google in Microsoft, 325 00:12:12,070 --> 00:12:16,350 in drugi delajo na točno ti nekakšen veliki podatkov vrste vprašanj 326 00:12:16,350 --> 00:12:18,530 vedno bolj v teh dneh. 327 00:12:18,530 --> 00:12:18,900 >> Vse je v redu. 328 00:12:18,900 --> 00:12:23,800 Torej uspeh Jenniferjevem v ta drugi algoritem, odkrito povedano, ona presenetljivo 329 00:12:23,800 --> 00:12:26,110 tudi prvič, vendar naj je kot sreče napisati tako, da smo 330 00:12:26,110 --> 00:12:27,000 lahko to točko. 331 00:12:27,000 --> 00:12:30,970 V drugem primeru pa je spodbudil algoritem, ki ponovi in 332 00:12:30,970 --> 00:12:34,670 spet, vendar je vzela za samoumevno nekatere predpostavke, da smo dovolili 333 00:12:34,670 --> 00:12:39,370 njo, ampak ona izkoristiti nekaj podrobnosti drugič, da ni imela 334 00:12:39,370 --> 00:12:39,840 prvič. 335 00:12:39,840 --> 00:12:41,800 , Ki je bil kaj? 336 00:12:41,800 --> 00:12:43,050 >> Ta seznam je bil razvrščen. 337 00:12:43,050 --> 00:12:46,350 Torej, takoj ko razporejene seznam smo trdijo, da je Jennifer sposobna narediti 338 00:12:46,350 --> 00:12:47,480 bistveno bolje. 339 00:12:47,480 --> 00:12:51,450 7 vrata, ja, ni to zanimivo, ampak to domnevam, da smo 7 milijonov vrata. 340 00:12:51,450 --> 00:12:54,080 Log n se definitivno bo opraviti še veliko, veliko 341 00:12:54,080 --> 00:12:55,610 hitreje na dolgi rok. 342 00:12:55,610 --> 00:12:58,880 Ampak ona je morala imeti Vrata razporejene za njo. 343 00:12:58,880 --> 00:13:02,320 Zdaj sem vzel svobodo tem, da vnaprej na računalniškem zaslonu 344 00:13:02,320 --> 00:13:05,160 tu, ampak predvidevam, da je Jennifer moral storiti, da zase? 345 00:13:05,160 --> 00:13:10,120 Recimo, da so vrata v zadevni zastopane podatkov v zbirki podatkov, ali 346 00:13:10,120 --> 00:13:14,260 prijatelji, registrirane za Facebook, ali vse spletne strani na internetu, ki 347 00:13:14,260 --> 00:13:16,880 različne spletne strani, bi morali indeks ali iskanje več. 348 00:13:16,880 --> 00:13:20,940 >> Predvidevam, da si imel neobdelanih podatkov določiti in je bila prepuščena vam, ali 349 00:13:20,940 --> 00:13:23,010 Jennifer storiti je, da sortiranje? 350 00:13:23,010 --> 00:13:26,950 Da ne zahteva, da smo odgovorili Vprašanje, no, koliko časa 351 00:13:26,950 --> 00:13:31,080 bi bili sprejeti Jennifer, ali celo mi, razvrstiti te številke vnaprej, tako 352 00:13:31,080 --> 00:13:32,680 da bi ona to izkoristil? 353 00:13:32,680 --> 00:13:32,880 Kajne? 354 00:13:32,880 --> 00:13:36,620 Ker posledice, seveda, , če se mi je precej časa za razvrščanje 355 00:13:36,620 --> 00:13:40,800 številke, ki so vraga briga, da vas lahko najdete številne kot 50 tako hitro, 356 00:13:40,800 --> 00:13:44,850 kot v primeru Jenniferjevem, če smo več kot preobremenjeni količino celotnega časa 357 00:13:44,850 --> 00:13:46,920 to je s sortiranjem stvari vnaprej? 358 00:13:46,920 --> 00:13:49,320 >> Torej, da vidimo, če ne moremo naslikati sliko tukaj. 359 00:13:49,320 --> 00:13:51,370 Imam cel kup več stresa kroglice, če to pomaga 360 00:13:51,370 --> 00:13:52,270 prebiti led tukaj. 361 00:13:52,270 --> 00:13:55,690 In če ne bi motilo, smo potrebujemo sedem prostovoljec - 362 00:13:55,690 --> 00:13:57,060 no, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Tako da nam ne bo treba porabiti na svetilk mizo, se zdi. 365 00:13:59,250 --> 00:13:59,690 Vse je v redu. 366 00:13:59,690 --> 00:14:01,530 Torej, kako pa ti dve spredaj. 367 00:14:01,530 --> 00:14:04,160 Kaj pa ti dve fantje v hrbtu. 368 00:14:04,160 --> 00:14:04,870 Torej, to je štiri leta. 369 00:14:04,870 --> 00:14:09,890 Kaj pa ti pred pet, šest in sedem. 370 00:14:09,890 --> 00:14:10,320 Tam. 371 00:14:10,320 --> 00:14:13,260 Tvoj prijatelj te je poudaril, tako da boste dobili nagrado. 372 00:14:13,260 --> 00:14:13,700 >> Vse je v redu. 373 00:14:13,700 --> 00:14:14,410 Pridi gor. 374 00:14:14,410 --> 00:14:17,120 In zakaj ne imate fantje, pridi sem. 375 00:14:17,120 --> 00:14:18,960 Bom dal vsako številko. 376 00:14:18,960 --> 00:14:22,150 In iti naprej in se dogovorite sami identično s tem, kar je 377 00:14:22,150 --> 00:14:25,180 prikazano na zaslonu. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing GLAS] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: OOP, žal. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Vse je v redu. 382 00:14:32,180 --> 00:14:32,750 No, pa gremo. 383 00:14:32,750 --> 00:14:34,180 Številka pet. 384 00:14:34,180 --> 00:14:35,136 Število šest. 385 00:14:35,136 --> 00:14:37,770 Ena, dva, tri, štiri, pet, šest, sedem. 386 00:14:37,770 --> 00:14:39,410 Oh, to je čudno. 387 00:14:39,410 --> 00:14:41,210 >> ZVOČNIK 2: bom dobil -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Dober posel. 389 00:14:41,900 --> 00:14:43,130 Vse je v redu. 390 00:14:43,130 --> 00:14:44,611 Hvala za sodelovanje. 391 00:14:44,611 --> 00:14:47,200 >> [APLAVZ] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Vse je v redu. 394 00:14:48,860 --> 00:14:51,970 Torej imamo štiri, dva, šest, ena, tri, sedem, pet. 395 00:14:51,970 --> 00:14:56,010 Izpopolniti tako da imamo sedem prostovoljcev tukaj, ki so enake v širino 396 00:14:56,010 --> 00:14:57,430 matrika, da igramo s prej. 397 00:14:57,430 --> 00:14:59,470 In sem se odločil, sedem razlogov da bo prav 398 00:14:59,470 --> 00:15:00,840 priročno v malo. 399 00:15:00,840 --> 00:15:04,400 In jaz bom predlagala, prvič, da moramo rešiti teh sedem prostovoljcev. 400 00:15:04,400 --> 00:15:06,786 Če želite, prvič, pozdravit, čeprav. 401 00:15:06,786 --> 00:15:08,970 Glede na to, se bo nerodni nekaj minut. 402 00:15:08,970 --> 00:15:10,370 Predstavite se. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Živjo, jaz sem Grace. 404 00:15:10,980 --> 00:15:14,190 Sem letniku Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Pozdravljeni. 406 00:15:14,620 --> 00:15:15,620 Jaz sem Branson. 407 00:15:15,620 --> 00:15:16,920 Jaz sem novinec v Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Pozdravljeni. 410 00:15:20,230 --> 00:15:21,040 Jaz sem Gabe. 411 00:15:21,040 --> 00:15:22,300 Jaz sem junior v Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> Neil: Jaz sem Neil. 414 00:15:25,980 --> 00:15:29,090 Jaz sem novinec v Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Jaz sem Jason. 416 00:15:29,550 --> 00:15:32,816 Jaz sem novinec v Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Jaz sem Mike. 418 00:15:33,700 --> 00:15:37,360 Jaz sem novinec v Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Jaz sem Jess. 420 00:15:37,990 --> 00:15:40,313 Sem letniku Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Odlično. 422 00:15:41,300 --> 00:15:41,850 Vse je v redu. 423 00:15:41,850 --> 00:15:44,190 No, hvala za vse naše Prostovoljci tukaj tako daleč. 424 00:15:44,190 --> 00:15:47,110 In izziv pri roki zdaj se dogaja da razvrstiti od teh fantov, potem pa 425 00:15:47,110 --> 00:15:50,250 bomo morali razmišljati malo težko o tem, kako učinkovito smo dejansko 426 00:15:50,250 --> 00:15:51,110 jih razporejene. 427 00:15:51,110 --> 00:15:52,580 Torej, kaj je najprej poskusite s tem. 428 00:15:52,580 --> 00:15:55,970 Vi lahko vidite število enih in drugih samo z dajanjem okoli vogalov. 429 00:15:55,970 --> 00:15:59,380 Pojdi naprej in traja nekaj sekund, in sortiranje sami od najmanjših na 430 00:15:59,380 --> 00:16:01,240 levo največji na desni strani. 431 00:16:01,240 --> 00:16:02,490 Pojdi. 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 Dobro. 435 00:16:08,030 --> 00:16:09,370 To je bilo res presneto hitro. 436 00:16:09,370 --> 00:16:14,040 Zdaj tukaj je nekdo, kaj je algoritem da se ti fantje? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Najmanj do največje. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Vsaj do največje je res nekako Cilj, vendar nisem prepričan, da je 440 00:16:18,070 --> 00:16:18,890 Res algoritem. 441 00:16:18,890 --> 00:16:21,810 Vsaj največje ne pove me korak za korakom, kaj storiti. 442 00:16:21,810 --> 00:16:22,833 Ja? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [neslišno] 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 Torej, če ste videli oseba, manjši od vašo številko, potem premaknete 447 00:16:28,920 --> 00:16:29,680 Pravica do njih. 448 00:16:29,680 --> 00:16:32,800 Tako da je sedaj vse bolj ekspresivna, več kot algoritem, ker ste 449 00:16:32,800 --> 00:16:35,410 lahko rečemo, če je to, potem je to. 450 00:16:35,410 --> 00:16:37,050 Torej imamo nekakšno pogojen konstrukt. 451 00:16:37,050 --> 00:16:39,700 In ti fantje zdelo, da to, da nekaj krat, saj nekateri izmed vas preselili malo 452 00:16:39,700 --> 00:16:40,420 na daljavo. 453 00:16:40,420 --> 00:16:43,410 Tako je bilo verjetno nekakšen zanka se dogaja v njihovih glavah. 454 00:16:43,410 --> 00:16:44,610 >> Ampak poskusimo formalizirati to. 455 00:16:44,610 --> 00:16:47,540 Če bi vidva ponastaviti nazaj k temu dogovoru. 456 00:16:47,540 --> 00:16:50,650 Poglejmo, če ne moremo formalizirati to bit, in potem vprašati, samo 457 00:16:50,650 --> 00:16:51,580 kako učinkovito je to? 458 00:16:51,580 --> 00:16:54,220 Seveda, ko smo to naredili bolj počasi, to se dogaja, da se počutijo kot dobro 459 00:16:54,220 --> 00:16:57,210 algoritem, ampak poglejmo, če lahko dal svoje prste na natančnih korakih. 460 00:16:57,210 --> 00:16:58,670 >> Torej, vidva sta štiri in dve. 461 00:16:58,670 --> 00:17:01,020 Ali ste pravilno ali napačno, da? 462 00:17:01,020 --> 00:17:01,900 Očitno napačna. 463 00:17:01,900 --> 00:17:02,710 Tako smo zamenjali. 464 00:17:02,710 --> 00:17:05,170 Zdaj bom umaknite tu in reči, 05:56. 465 00:17:05,170 --> 00:17:06,240 Ste pravilna ali napačna? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Pravilno. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Pravilno. 468 00:17:07,180 --> 00:17:08,300 Šest in ena? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Torej, to sta dve zamenjave. 472 00:17:10,490 --> 00:17:11,710 Šest in tri? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Šest in sedem? 476 00:17:13,930 --> 00:17:14,630 Videti je v redu. 477 00:17:14,630 --> 00:17:15,396 Sedem in pet? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [neslišno] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, zamenjali. 480 00:17:17,089 --> 00:17:19,770 In razporejene. 481 00:17:19,770 --> 00:17:19,980 Vse je v redu. 482 00:17:19,980 --> 00:17:21,440 Torej očitno ni, kajne? 483 00:17:21,440 --> 00:17:22,470 Torej je bil tam več dogaja. 484 00:17:22,470 --> 00:17:24,920 Ampak, seveda, ti fantje, čeprav samo nagonsko. 485 00:17:24,920 --> 00:17:25,450 hranijo premika. 486 00:17:25,450 --> 00:17:27,710 Niso samo ustavi, ko popravljena eno težavo. 487 00:17:27,710 --> 00:17:27,839 Torej. 488 00:17:27,839 --> 00:17:29,390 Vsekakor bom še da storijo enako stvar. 489 00:17:29,390 --> 00:17:32,720 Bom moral nekako previjanje nazaj na začetku tega problema, 490 00:17:32,720 --> 00:17:35,630 ali začetku tega sklopa ljudje, začnimo jih kliče. 491 00:17:35,630 --> 00:17:38,366 >> In kaj zdaj, naj moja algoritem na drugem prehodu biti? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Ista stvar. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Ista stvar. 494 00:17:39,940 --> 00:17:41,460 In to, da sem začel imeti rad, kajne? 495 00:17:41,460 --> 00:17:44,720 Kakor hitro lahko znajdete početje isto stvar znova in znova, da je 496 00:17:44,720 --> 00:17:47,890 postaja vse bolj podoben algoritmu, in manj človeški instinkt. 497 00:17:47,890 --> 00:17:48,680 >> Torej, zdaj, tukaj smo spet tam. 498 00:17:48,680 --> 00:17:49,870 Dve leti in štiri? 499 00:17:49,870 --> 00:17:50,220 Število 500 00:17:50,220 --> 00:17:51,050 Štiri in ena? 501 00:17:51,050 --> 00:17:53,380 Ah, tam je bil res nekaj dela še treba storiti. 502 00:17:53,380 --> 00:17:53,620 Za in tremi? 503 00:17:53,620 --> 00:17:54,572 Dobro. 504 00:17:54,572 --> 00:17:56,000 Štiri in šest? 505 00:17:56,000 --> 00:17:58,380 Šest in pet? 506 00:17:58,380 --> 00:17:59,470 Šest in sedem? 507 00:17:59,470 --> 00:18:00,970 OK, sedaj storiti. 508 00:18:00,970 --> 00:18:01,550 OK, ne. 509 00:18:01,550 --> 00:18:02,710 Moram iti nazaj. 510 00:18:02,710 --> 00:18:05,130 >> Torej sedaj, še enkrat, to delamo malo bolj načrtno. 511 00:18:05,130 --> 00:18:08,700 In zdaj, obstaja samo ena možgani izvršitve ta algoritem. 512 00:18:08,700 --> 00:18:10,290 Ena CPU, če ga boste. 513 00:18:10,290 --> 00:18:13,090 In odkrito povedano, to je edini vir da bomo imeli dostop do. 514 00:18:13,090 --> 00:18:16,280 In ko smo se vrniti na tipkovnico in imajo nekaj podobnega C na našem 515 00:18:16,280 --> 00:18:19,600 odstranjevanje, smo samo pisno program da lahko naredimo eno stvar naenkrat. 516 00:18:19,600 --> 00:18:22,900 Ker ti fantje pred nekaj trenutki smo vzvodom njihova kolektivna intelektualnega potenciala 517 00:18:22,900 --> 00:18:24,180 tako kot vi storili v tednu nič. 518 00:18:24,180 --> 00:18:24,980 Torej, kaj je obdržati to. 519 00:18:24,980 --> 00:18:26,260 >> Dva in ena. 520 00:18:26,260 --> 00:18:26,945 Dva in tri. 521 00:18:26,945 --> 00:18:27,460 Tri in štiri. 522 00:18:27,460 --> 00:18:28,310 Štiri in pet. 523 00:18:28,310 --> 00:18:28,620 Pet in šest. 524 00:18:28,620 --> 00:18:30,510 Šest in sedem. 525 00:18:30,510 --> 00:18:31,880 Naredil? 526 00:18:31,880 --> 00:18:34,560 Torej, jaz sem, ampak naj igrajo hudičev odvetnik. 527 00:18:34,560 --> 00:18:37,950 Jaz tudi neke vrste računalnik, ki je pravkar je točno skozi ta niz 528 00:18:37,950 --> 00:18:40,225 ljudje, veste, da sem naredil? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Ne 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Torej, zakaj? 531 00:18:41,050 --> 00:18:46,900 Kaj bi morali storiti, da bi se sklene odločilno, da sem naredil? 532 00:18:46,900 --> 00:18:48,230 Verjetno še ena podaja. 533 00:18:48,230 --> 00:18:48,430 Kajne? 534 00:18:48,430 --> 00:18:51,760 Ker vem, da je od prejšnje Preval je, da sem popraviti napako. 535 00:18:51,760 --> 00:18:53,920 In to pomeni, morda je še ena napaka 536 00:18:53,920 --> 00:18:54,840 da moram popraviti. 537 00:18:54,840 --> 00:18:58,680 Tako sem lahko prepričani samo s previjanjem in nato preverjanje, 01:59, dve in 538 00:18:58,680 --> 00:19:00,940 tri, tri in štiri, štiri in pet, pet in šest, šest in sedem. 539 00:19:00,940 --> 00:19:02,510 OK, zdaj sem brez dela. 540 00:19:02,510 --> 00:19:05,990 >> Vsekakor se spomnim, da sem storil ne delo z nekaj podobnega spremenljivke, 541 00:19:05,990 --> 00:19:06,975 všeč int. 542 00:19:06,975 --> 00:19:12,490 Da zamenjave klic, in če zamenjave je 0 nekoč I tu in se je začel na 0, potem 543 00:19:12,490 --> 00:19:15,520 Rad bi le bilo neumno, da nadaljujem in nazaj, ponovno preverjanje in 544 00:19:15,520 --> 00:19:16,450 spet in spet, kajne? 545 00:19:16,450 --> 00:19:18,450 Ker se vam zatakne pri nekaterih nekako neskončno zanko. 546 00:19:18,450 --> 00:19:21,250 Torej, kakor hitro je 0 zamenjave, lahko trdimo, da je to 547 00:19:21,250 --> 00:19:23,810 Algoritem je res popolna. 548 00:19:23,810 --> 00:19:25,400 >> Zdaj, kaj je dal ime za to. 549 00:19:25,400 --> 00:19:28,930 Algoritem, ki Predlagam smo pravkar izvajati je nekaj, kar ti mehurček 550 00:19:28,930 --> 00:19:32,800 vrste, znane kot tak v smislu, da številke, ki so večje vrste 551 00:19:32,800 --> 00:19:37,990 mehurček svojo pot do vrha, ali do na koncu niza številk. 552 00:19:37,990 --> 00:19:40,270 Ampak kako učinkovito je to algoritem? 553 00:19:40,270 --> 00:19:44,600 Koliko korakov sem fizično moral da, na primer, reda oglasov 554 00:19:44,600 --> 00:19:45,850 sedem ljudi? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Štiri do pet? 557 00:19:49,550 --> 00:19:51,420 OK, preveč je navsezadnje bo odgovor. 558 00:19:51,420 --> 00:19:54,960 Toda tudi takrat, določeno število ni tako zanimivo. 559 00:19:54,960 --> 00:19:56,670 Kaj je to, kot n posploševati. 560 00:19:56,670 --> 00:20:00,520 Torej, če sem n ljudi tu gor, in so so bili nekako v naključnem vrstnem redu na 561 00:20:00,520 --> 00:20:02,180 začenši v tem prvotnem vrstnem redu. 562 00:20:02,180 --> 00:20:04,910 No, koliko korakov pa imam da se v prvem prehodu? 563 00:20:04,910 --> 00:20:09,810 To je bila ena, dva, tri, štiri, pet, šest, in oni so sedem ljudi, tako 564 00:20:09,810 --> 00:20:13,670 da je sedem, šest -, tako da je n minus ena korake prvič. 565 00:20:13,670 --> 00:20:16,280 >> Zdaj, koliko korakov pa imam da se, ko sem previti? 566 00:20:16,280 --> 00:20:19,310 No, lahko bi dejansko podvojila, da če smo res želeli, vendar za zdaj, sem 567 00:20:19,310 --> 00:20:22,300 Samo reči, vse v redu, še n minus 1. 568 00:20:22,300 --> 00:20:25,240 Torej n minus 1 bo dobil nadležno slediti, tako da je 569 00:20:25,240 --> 00:20:26,400 Samo zaokrožitev nekoliko. 570 00:20:26,400 --> 00:20:27,770 Tako 2n koraki. 571 00:20:27,770 --> 00:20:29,310 Torej 14 korakov, gor ali dol. 572 00:20:29,310 --> 00:20:31,930 >> Kolikokrat sem se korak naslednjič? 573 00:20:31,930 --> 00:20:33,740 No, to je 3n. 574 00:20:33,740 --> 00:20:34,510 res. 575 00:20:34,510 --> 00:20:37,920 In zdaj, v najslabšem primeru za na primer, kolikokrat bom moral 576 00:20:37,920 --> 00:20:41,730 šli naprej in nazaj, naprej in nazaj, izvršitve ta algoritem, menjava 577 00:20:41,730 --> 00:20:44,620 ljudje na vsakem prehodu, grobo? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 To je dejansko n kvadrat, kajne? 580 00:20:50,010 --> 00:20:53,000 >> Ker v najslabšem primeru lahko nekako si od razmišljati o tem intuitivno, 581 00:20:53,000 --> 00:20:54,800 čeprav bo trajalo malo malo časa, da se potopi noter 582 00:20:54,800 --> 00:20:57,590 V najslabšem primeru, kaj bi ti Sedem ljudi je izgledala v 583 00:20:57,590 --> 00:21:00,230 pogoji dogovora njihovih številk? 584 00:21:00,230 --> 00:21:01,460 Popolnoma nazaj, kajne? 585 00:21:01,460 --> 00:21:02,815 In samo, da simulira, da kaj je ime? 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 V redu, Mike, si lahko samo se mi pridruži preko tukaj samo eno sekundo? 589 00:21:08,100 --> 00:21:08,880 Pravzaprav ne. 590 00:21:08,880 --> 00:21:10,150 Žal Mike, kaj je navijanje. 591 00:21:10,150 --> 00:21:10,910 Kaj ti je že ime? 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, prideš z me, če vas ne moti. 595 00:21:13,750 --> 00:21:17,150 Torej bom predlagal, samo za preprostost, ki je zdaj v njegovi Neil 596 00:21:17,150 --> 00:21:18,510 najslabši možen primer. 597 00:21:18,510 --> 00:21:20,720 Ampak spomnim, kako sem izvajala moj algoritem. 598 00:21:20,720 --> 00:21:24,530 Jaz sem primerjavo, primerjanje, primerjanje, primerjanje, primerjanje, oh. 599 00:21:24,530 --> 00:21:26,640 Zdaj so ti ljudje iz reda, tako da sem popraviti. 600 00:21:26,640 --> 00:21:27,980 Torej vidva zamenjali. 601 00:21:27,980 --> 00:21:31,630 Vendar menijo, zdaj, koliko dlje pa Neil iti? 602 00:21:31,630 --> 00:21:32,690 To je približno n. 603 00:21:32,690 --> 00:21:33,570 Veš, to ni dejansko n. 604 00:21:33,570 --> 00:21:36,040 To je kot, n minus 1, a se bom motenih sledenja malo 605 00:21:36,040 --> 00:21:37,550 Številka, zato naj samo call it n. 606 00:21:37,550 --> 00:21:42,860 >> Torej, če Neil premakne en korak maksimalno vsak čas, in da se premaknete Neil en korak, 607 00:21:42,860 --> 00:21:46,580 Moram narediti to res dolgočasno glavo in nazaj, to je približno 608 00:21:46,580 --> 00:21:52,080 delaš to, n korakov, skupaj z n-krat, saj se dogaja, da me 609 00:21:52,080 --> 00:21:55,820 da veliko ukrepov, da bi dobili Neil vse pot do tam, kamor spada. 610 00:21:55,820 --> 00:21:58,620 Kaj šele vsi ostali, če vidva so bili vsi napačno naročiti kot dobro. 611 00:21:58,620 --> 00:22:01,100 >> Torej recimo mehurček vrste n kvadrat. 612 00:22:01,100 --> 00:22:04,860 Čas tega algoritem teče, izvajanje tega algoritma, 613 00:22:04,860 --> 00:22:07,120 učinkovitost tega algoritma smo se pravkar opisali več 614 00:22:07,120 --> 00:22:08,800 splošno kot n kvadrat. 615 00:22:08,800 --> 00:22:11,650 Kar je lepo, ker nisem mogel storiti Enako primer z osem ljudi, devet 616 00:22:11,650 --> 00:22:15,450 ljudi, milijon ljudi, in da Odgovor se ne bo spremenilo. 617 00:22:15,450 --> 00:22:18,870 >> Torej, če vi ne bi motilo, dajmo ti prikrivati, kjer ste začeli. 618 00:22:18,870 --> 00:22:22,510 In poskusimo še dva druga pristopov in glej, če ne moremo narediti bistveno 619 00:22:22,510 --> 00:22:23,820 bolje od tega. 620 00:22:23,820 --> 00:22:27,130 Torej ta čas, bom predlagala nekako drugačen algoritem. 621 00:22:27,130 --> 00:22:29,950 To je bil zelo pameten od nas zadnji čas, in vi imeli prav, da imajo 622 00:22:29,950 --> 00:22:32,470 pravi instinkt za samo vrste za zamenjavo parih. 623 00:22:32,470 --> 00:22:36,500 Ampak, če sem res želela približati to preprosto in moj cilj je, da se premaknete 624 00:22:36,500 --> 00:22:39,800 vseh malih številk na ta način, in all velikih številk, ki 625 00:22:39,800 --> 00:22:43,030 način, zakaj ne bi jaz samo to, da je v najbolj naiven način mogoče, in videli, če sem 626 00:22:43,030 --> 00:22:45,730 Lahko si boljši od tistega, kar je bilo dokaj zapleten algoritem? 627 00:22:45,730 --> 00:22:46,620 >> Torej, da vidimo. 628 00:22:46,620 --> 00:22:48,940 Štiri je zelo majhno število, torej sem vas bo pustil tam trenutek. 629 00:22:48,940 --> 00:22:50,610 Ooh, številka dve je še bolje. 630 00:22:50,610 --> 00:22:52,230 Tako da lahko samo korak naprej za trenutek? 631 00:22:52,230 --> 00:22:55,670 To je trenutno moj najmanjši oštevilčena Kandidat, in bom, da se spomnimo 632 00:22:55,670 --> 00:22:57,000 da se z, recimo, spremenljivko. 633 00:22:57,000 --> 00:22:57,930 Ampak bom sproti preverja. 634 00:22:57,930 --> 00:22:59,890 Ali obstaja nekdo, čigar število je manjše? 635 00:22:59,890 --> 00:23:00,460 Šest, št. 636 00:23:00,460 --> 00:23:01,390 Oh, tam je Neil znova. 637 00:23:01,390 --> 00:23:04,050 >> Torej, jaz vas bom potisnite nazaj nekako konceptualno. 638 00:23:04,050 --> 00:23:05,120 Neil bo prišel naprej. 639 00:23:05,120 --> 00:23:08,440 In zdaj, spremenljivke, ki sem uporabo na slediti, kdo ima najmanjši 640 00:23:08,440 --> 00:23:11,390 Številka je posodobiti, da vsebujejo Lokacija Neil je. 641 00:23:11,390 --> 00:23:12,110 No, pa poglejmo. 642 00:23:12,110 --> 00:23:13,960 Tri, sedem, pet. 643 00:23:13,960 --> 00:23:15,590 OK, vem, Neil je najmanjša. 644 00:23:15,590 --> 00:23:18,110 Kaj je najenostavnejša stvar mi pa zdaj? 645 00:23:18,110 --> 00:23:21,410 Jaz ne bom izgubljal časa, ki ga pravkar bisernih Neil eno mesto v levo. 646 00:23:21,410 --> 00:23:25,350 Zakaj ne bi samo dal Neil kjer je pripada, kar je seveda kje? 647 00:23:25,350 --> 00:23:26,160 >> Vse smer na začetku. 648 00:23:26,160 --> 00:23:27,720 Torej Neil, pridi z mano. 649 00:23:27,720 --> 00:23:28,910 In kaj je bilo ime? 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 Torej Grace, žal, si nekako na poti. 654 00:23:32,490 --> 00:23:34,290 Torej, kako bomo rešili ta problem? 655 00:23:34,290 --> 00:23:34,490 Kajne? 656 00:23:34,490 --> 00:23:37,500 Če je to polje, ni le sedem lokacij. 657 00:23:37,500 --> 00:23:40,830 Spomnimo se, da je z Robom, smo se pogovarjali o razglasitvi starosti, in smo imeli samo 658 00:23:40,830 --> 00:23:41,740 končno število starosti? 659 00:23:41,740 --> 00:23:42,535 Isto idejo tukaj. 660 00:23:42,535 --> 00:23:44,300 Imamo le končno število ints. 661 00:23:44,300 --> 00:23:47,590 Grace je nekako v našem način, tako da kako popraviti? 662 00:23:47,590 --> 00:23:49,555 >> Najenostavnejši način je všeč, Grace, oprosti. 663 00:23:49,555 --> 00:23:51,870 Boš moral iti tja tam, tako da bomo lahko naredili prostor. 664 00:23:51,870 --> 00:23:55,290 Zdaj, če menite o tem, morda smo samo na problem slabše. 665 00:23:55,290 --> 00:23:58,510 In morda smo storili, ker kaj če Grace so bili na pravem mestu? 666 00:23:58,510 --> 00:24:01,730 Vemo pa, da je ni, ker V nasprotnem primeru bi ji bilo 667 00:24:01,730 --> 00:24:03,980 stoji naprej namesto Neil v tem trenutku, kajne? 668 00:24:03,980 --> 00:24:05,550 Smo že preverili njeno številko ven. 669 00:24:05,550 --> 00:24:05,770 >> Vse je v redu. 670 00:24:05,770 --> 00:24:09,110 Torej, zdaj, Neil je na pravem mestu, in Jaz lahko naredim rahlo optimizacijo. 671 00:24:09,110 --> 00:24:11,740 Za naslednjo minuto, bom ignorirati Neil vse skupaj, tako da ne 672 00:24:11,740 --> 00:24:15,280 zapravljajo svoj čas, ali nehote ga zamenjali na napačnem mestu. 673 00:24:15,280 --> 00:24:17,805 Torej, zdaj, kako se mi zdi Naslednja element, ki je najmanjša? 674 00:24:17,805 --> 00:24:18,480 Dva. 675 00:24:18,480 --> 00:24:20,225 To je zelo dobra številka, če želite korak naprej in 676 00:24:20,225 --> 00:24:21,100 Zapomnil si vas bom. 677 00:24:21,100 --> 00:24:21,980 Šest, ni dobro. 678 00:24:21,980 --> 00:24:24,820 Štiri, tri, sedem, pet, ni dobro. 679 00:24:24,820 --> 00:24:26,800 Naj vas premestimo na vaš pravi kraj. 680 00:24:26,800 --> 00:24:28,470 In pravkar smo srečo tokrat. 681 00:24:28,470 --> 00:24:31,350 >> Zdaj bom prezreti teh dva fanta, zdaj pa naredite nekaj več 682 00:24:31,350 --> 00:24:32,260 skozi to. 683 00:24:32,260 --> 00:24:33,490 Šest, da je zelo majhno število. 684 00:24:33,490 --> 00:24:34,300 Pridi naprej. 685 00:24:34,300 --> 00:24:35,220 Oh, oprostite. 686 00:24:35,220 --> 00:24:37,640 Številka Grace je bolje, tako stopiti naprej. 687 00:24:37,640 --> 00:24:38,260 Štiri. 688 00:24:38,260 --> 00:24:39,120 Oprostite, Grace. 689 00:24:39,120 --> 00:24:39,950 Spet nazaj. 690 00:24:39,950 --> 00:24:41,550 Številka tri je bolje. 691 00:24:41,550 --> 00:24:42,290 Sedem. 692 00:24:42,290 --> 00:24:42,720 Pet. 693 00:24:42,720 --> 00:24:43,550 In kaj zdaj ti je že ime? 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 Torej, Jason je zdaj najmanjši Element sem izbran. 697 00:24:47,050 --> 00:24:49,160 Kje je šel? 698 00:24:49,160 --> 00:24:50,380 Torej, kje je šest. 699 00:24:50,380 --> 00:24:51,210 In tvoje ime je spet? 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 je na poti. 703 00:24:53,220 --> 00:24:54,640 Kaj je najlažja stvar? 704 00:24:54,640 --> 00:24:58,390 Swap ta dva fanta in še naprej. 705 00:24:58,390 --> 00:24:59,020 Torej, zdaj pa poglejmo. 706 00:24:59,020 --> 00:25:00,170 Kdo je najmanjša? 707 00:25:00,170 --> 00:25:01,030 Štiri. 708 00:25:01,030 --> 00:25:01,990 Dovolite mi, da nekako goljufija. 709 00:25:01,990 --> 00:25:03,090 Pet se bo najmanjši. 710 00:25:03,090 --> 00:25:05,220 Se mi zdi naslednji, če želite stopiti naprej, kaj moram storiti s 711 00:25:05,220 --> 00:25:06,820 ti fantje, s Gabe? 712 00:25:06,820 --> 00:25:08,450 Spet zamenjali. 713 00:25:08,450 --> 00:25:10,740 Torej, zdaj, še vedno rahlo v okvari. 714 00:25:10,740 --> 00:25:14,140 Ugotovil sem, Gabe za najmanjšega, tako Jaz pop ga, vam premakniti fantje znova. 715 00:25:14,140 --> 00:25:15,190 In naredil. 716 00:25:15,190 --> 00:25:17,200 >> Torej odgovor je enak. 717 00:25:17,200 --> 00:25:18,600 Končni rezultat je enak. 718 00:25:18,600 --> 00:25:22,730 Kateri od teh dveh algoritmov je boljši? 719 00:25:22,730 --> 00:25:23,500 Drugi pa, sem slišal. 720 00:25:23,500 --> 00:25:24,252 Zakaj? 721 00:25:24,252 --> 00:25:25,900 >> ZVOČNIK 3: To je n korake [neslišno]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: To je n koraki v večini. 723 00:25:27,600 --> 00:25:28,490 Zanimivo. 724 00:25:28,490 --> 00:25:30,610 Tako je, čeprav? 725 00:25:30,610 --> 00:25:33,630 Torej, kako si se mi zdi najmanjši element? 726 00:25:33,630 --> 00:25:37,060 Koliko korakov sem moral vzeti najti najmanjši element? 727 00:25:37,060 --> 00:25:39,220 Imel sem videti konca Na koncu, kajne? 728 00:25:39,220 --> 00:25:41,530 Ker v tem najslabšem primeru, kaj če bi bil Neil tukaj? 729 00:25:41,530 --> 00:25:45,700 Torej le ugotovitev, najmanjši element se mi n korakov ali N minus 1. 730 00:25:45,700 --> 00:25:46,100 Ampak, v redu. 731 00:25:46,100 --> 00:25:46,980 Torej popraviti Neil. 732 00:25:46,980 --> 00:25:48,740 Ne pozabite, da je minuto ali dve nazaj. 733 00:25:48,740 --> 00:25:51,680 >> Toda kako se mi zdi naslednja najmanjši element? 734 00:25:51,680 --> 00:25:54,830 To je n minus 1 ali n minus 2 res, iz več korakov. 735 00:25:54,830 --> 00:25:55,440 Torej, v redu. 736 00:25:55,440 --> 00:25:57,390 Torej nisem n minus 2. 737 00:25:57,390 --> 00:25:57,600 Vse je v redu. 738 00:25:57,600 --> 00:25:59,130 Tako, da se počuti malo bolje. 739 00:25:59,130 --> 00:25:59,730 Vse je v redu. 740 00:25:59,730 --> 00:26:03,270 Koliko korakov naslednjič poiskati številko tri? 741 00:26:03,270 --> 00:26:04,420 Torej n minus 4. 742 00:26:04,420 --> 00:26:07,670 Tako da se zmanjšuje, ena manj stopiti na vsaki ponovitvi. 743 00:26:07,670 --> 00:26:08,740 Torej to ne počutite bolje, kajne? 744 00:26:08,740 --> 00:26:13,450 Če zadnjem času je bilo približno n krat n, ta čas je n minus 1, plus minus n 745 00:26:13,450 --> 00:26:16,500 2, plus n minus 3 plus n minus 4, pika, dot, pika. 746 00:26:16,500 --> 00:26:18,750 Ampak, če se spomnite iz srednje šole učbeniki, malo goljufija 747 00:26:18,750 --> 00:26:24,380 stanja na zadnji strani, ki je formul, če dodate to vrsto številk, 748 00:26:24,380 --> 00:26:31,280 kar je skupno število korakov bo, da bom tukaj? 749 00:26:31,280 --> 00:26:36,580 >> To je eden od tistih, všeč, n minus 1 krat n, deljeno z 2. 750 00:26:36,580 --> 00:26:39,040 Torej, da vidim, če sem lahko pull to gor za trenutek. 751 00:26:39,040 --> 00:26:42,230 In spet, sem nekako zaokroževanja nekatere številke samo, da naše življenje preprosto, 752 00:26:42,230 --> 00:26:47,830 ampak kot se spomnim, da je nekaj takega kot če Jaz n minus 1 stvari, potem je n minus 753 00:26:47,830 --> 00:26:53,570 2, potem je n minus 3, je v grobem kaj takega več kot 2, in če sem 754 00:26:53,570 --> 00:26:55,510 pomnožite to jasno, da je dejansko n kvadrat. 755 00:26:55,510 --> 00:26:58,940 Da se ne počuti preveč dobro. n minus n čez 2. 756 00:26:58,940 --> 00:27:00,350 >> Ampak tukaj je stvar. 757 00:27:00,350 --> 00:27:03,720 V računalništvu, ko je problematika začeli, da bi dobili zanimivo je, ko n 758 00:27:03,720 --> 00:27:04,700 postane zelo velik. 759 00:27:04,700 --> 00:27:08,110 In ko n postane zelo velik, katera te vrednosti se dogaja, da obvladujejo vse 760 00:27:08,110 --> 00:27:09,750 od drugih? 761 00:27:09,750 --> 00:27:10,990 To je nekako n kvadrat, kajne? 762 00:27:10,990 --> 00:27:13,340 Ja, deljenje z 2 je precej dobro. 763 00:27:13,340 --> 00:27:16,740 Ampak, če govorimo o milijardah koščkov podatkov, ali bilijonov 764 00:27:16,740 --> 00:27:18,700 koščki podatkov, ok, tako da ste dvakrat hitreje. 765 00:27:18,700 --> 00:27:22,440 Ampak kdo res briga, če tega veliko število, če ta faktor kaj dobi 766 00:27:22,440 --> 00:27:23,040 večji in večji. 767 00:27:23,040 --> 00:27:25,990 In zagotovo, da naredi več Razlika od tega tipa. 768 00:27:25,990 --> 00:27:29,120 Torej, čeprav imate prav, Drugi algoritem, bomo ga pokličete 769 00:27:29,120 --> 00:27:32,970 Izbor vrste, je v realnem svetu, malo hitreje lahko, ker sem 770 00:27:32,970 --> 00:27:35,360 ob manj in manj korake vsakič. 771 00:27:35,360 --> 00:27:37,340 >> To ni res bistveno hitreje. 772 00:27:37,340 --> 00:27:41,430 Ker, če smo dejansko igrajo to ven velike vrednosti n, na koncu 773 00:27:41,430 --> 00:27:44,750 dan, za dovolj velik n, da je še vedno dogaja, da se počutijo zelo počasi. 774 00:27:44,750 --> 00:27:46,770 No, naj vzamem eno zadnja podaja na to. 775 00:27:46,770 --> 00:27:48,920 To je tisto, kar bi vas vabim Izbor vrste. 776 00:27:48,920 --> 00:27:51,040 Lahko vidva ponastaviti sami zadnjič? 777 00:27:51,040 --> 00:27:53,550 In v tem zadnjem primeru, bom predlaga nekaj 778 00:27:53,550 --> 00:27:54,970 imenovano vstavljanja vrste. 779 00:27:54,970 --> 00:27:57,470 Vstavljanje neke počutje, konceptualno, malo drugačen. 780 00:27:57,470 --> 00:28:00,980 >> Namesto gredo naprej in nazaj in izbiri najmanjši element, sem 781 00:28:00,980 --> 00:28:05,030 šele tekoč, da se ukvarjajo z vsako od teh fantje, kot sem jih srečujejo, in vstavite 782 00:28:05,030 --> 00:28:06,850 jih v svojem pravem mestu. 783 00:28:06,850 --> 00:28:10,160 Torej bom samo, da začnete z Grace, in vidim, da je ona številka štiri. 784 00:28:10,160 --> 00:28:11,720 Kje številka štiri pripada? 785 00:28:11,720 --> 00:28:14,940 Nisem začel sortiranje ničesar, tako Grace pride, da ostanejo tam. 786 00:28:14,940 --> 00:28:18,355 In zdaj bom trditi, če bi lahko narediti korak na vaši desni strani, to 787 00:28:18,355 --> 00:28:21,650 moj razporejene seznam, to je moj unsorted preostali seznam. 788 00:28:21,650 --> 00:28:23,260 Torej, zdaj bom nadaljuje naslednji, in kaj ti je že ime? 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 Torej Branson je številka dve. 792 00:28:25,375 --> 00:28:27,490 Torej bom peljal ven za trenutek. 793 00:28:27,490 --> 00:28:30,940 In zdaj, kam spadaš V tem polju? 794 00:28:30,940 --> 00:28:32,360 Torej za pravico do Grace. 795 00:28:32,360 --> 00:28:35,670 Torej še enkrat, mi smo nekako tako Grace storiti veliko dela tukaj. 796 00:28:35,670 --> 00:28:37,290 Kje vas čaka? 797 00:28:37,290 --> 00:28:40,120 Torej bomo vas potisnite levo in vstavite Branson tam. 798 00:28:40,120 --> 00:28:41,680 Zdaj pa trdijo, da fantje so storili. 799 00:28:41,680 --> 00:28:43,240 Ampak obvestilo, da sem ne uporabljate dodaten prostor. 800 00:28:43,240 --> 00:28:45,130 To je še vedno 2 elementi Tukaj, 5. sem. 801 00:28:45,130 --> 00:28:47,910 Skupna velikost polja je 7, torej sem ne vara, v redu? 802 00:28:47,910 --> 00:28:51,950 >> Torej, zdaj imamo z Gabe tukaj Številka šest, kam spadaš? 803 00:28:51,950 --> 00:28:52,650 Spet imaš srečo. 804 00:28:52,650 --> 00:28:53,820 Tako da boste dobili, da ostanejo tam. 805 00:28:53,820 --> 00:28:57,210 Vzemite majhen korak v desno Samo da bo jasno, da ste razvrščeni. 806 00:28:57,210 --> 00:29:00,520 In zdaj imamo Neil spet številka ena, kam greš? 807 00:29:00,520 --> 00:29:03,540 In zdaj je, če bomo začeli razumeti, da Ta algoritem, čeprav na prvi 808 00:29:03,540 --> 00:29:05,950 pogled, počuti zelo pameten, pazi kaj se bo zgodilo. 809 00:29:05,950 --> 00:29:07,370 Če bi lahko stopite naprej. 810 00:29:07,370 --> 00:29:09,260 >> Kje želimo postaviti Neil? 811 00:29:09,260 --> 00:29:11,830 Torej očitno tu, da kako bomo dobili Neil tam? 812 00:29:11,830 --> 00:29:12,970 Naredimo to korak za korakom. 813 00:29:12,970 --> 00:29:15,620 Gabe, kam morate iti? 814 00:29:15,620 --> 00:29:19,590 Ja, tako bo en velik korak, ali dva pol-korakov, da 815 00:29:19,590 --> 00:29:20,820 en korak tja. 816 00:29:20,820 --> 00:29:21,750 Grace, kje si? 817 00:29:21,750 --> 00:29:22,510 Dobro. 818 00:29:22,510 --> 00:29:23,500 Torej še en korak. 819 00:29:23,500 --> 00:29:24,960 In končno, Branson? 820 00:29:24,960 --> 00:29:25,460 Še en korak. 821 00:29:25,460 --> 00:29:27,190 In sedaj bomo lahko Neil na svoje mesto. 822 00:29:27,190 --> 00:29:28,440 >> Torej, zdaj, še to logiko. 823 00:29:28,440 --> 00:29:32,420 Čeprav mi ne premikajo Neil več in več in več, da bi ga dal 824 00:29:32,420 --> 00:29:36,420 kam gre, v najslabšem primeru, Naslednja številka se lahko srečajo bi 825 00:29:36,420 --> 00:29:42,220 je število, jasno je, da je število nič, potem pa bomo preusmeriti vse 826 00:29:42,220 --> 00:29:42,730 ti fantje. 827 00:29:42,730 --> 00:29:44,950 Denimo, da je številka, negativna ena, potem imamo za premik 828 00:29:44,950 --> 00:29:46,080 vseh teh fantov. 829 00:29:46,080 --> 00:29:48,500 Tako da smo res nekako lahkota Problem okrog, tako da smo 830 00:29:48,500 --> 00:29:52,620 prenos stroškov iz Postopek izbire tako vstavitev 831 00:29:52,620 --> 00:29:56,930 proces, tako da samo še vidva premakniti približno n minus nekaj 832 00:29:56,930 --> 00:29:57,940 število korakov. 833 00:29:57,940 --> 00:30:01,200 In da je število korakov je samo še povečati, kot sem izberete več številk, 834 00:30:01,200 --> 00:30:04,730 če imam, da pometemo vaju nazaj in nazaj in nazaj. 835 00:30:04,730 --> 00:30:08,320 >> Tako žalostna stvar, zdaj je vse to algoritmi so n kvadrat. 836 00:30:08,320 --> 00:30:10,570 Pojdimo naprej in hvala ti fantje, in vizualizirati te malo 837 00:30:10,570 --> 00:30:11,090 drugače. 838 00:30:11,090 --> 00:30:12,312 Zelo dobro opravljeno. 839 00:30:12,312 --> 00:30:14,120 >> [APLAVZ] 840 00:30:14,120 --> 00:30:15,030 >> Vse je v redu. 841 00:30:15,030 --> 00:30:16,280 Tukaj imaš. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Hvala za - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [neslišno] obdržati številke. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: No, lahko vam da številke, kot dobro. 846 00:30:21,990 --> 00:30:23,440 Vse je v redu. 847 00:30:23,440 --> 00:30:24,100 Lepo opravljeno. 848 00:30:24,100 --> 00:30:25,300 Vse je v redu. 849 00:30:25,300 --> 00:30:30,510 Torej, da vidimo, če ne bomo zdaj lahko povzamemo hitreje in bolj vizualno 850 00:30:30,510 --> 00:30:33,410 kaj se je zgodilo tukaj, kot sledi. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Jaz grem naprej in dvigni Firefox. 853 00:30:38,770 --> 00:30:41,310 Bomo povezati to demonstracijo na spletni strani seveda je. 854 00:30:41,310 --> 00:30:43,870 Java je malce nadležno, da se delo v nekaterih brskalnikih teh dneh. 855 00:30:43,870 --> 00:30:46,760 Torej, če igrajo z to doma, spoznali boste morda morali uporabljati Firefox 856 00:30:46,760 --> 00:30:47,990 da bo stvar delovala. 857 00:30:47,990 --> 00:30:50,440 In kaj bom naredil s tem predstavitev je naslednji. 858 00:30:50,440 --> 00:30:54,875 >> Na dnu, imam cel kup možnosti menija, vključno z začetkom in 859 00:30:54,875 --> 00:30:55,840 Stop. 860 00:30:55,840 --> 00:30:59,450 Prav tako, kot sedmih, se zdi, da bug v teh programih, s katerimi si 861 00:30:59,450 --> 00:31:03,720 ne more dejansko videli začetek ali zaustavitev gumb, če imate Command ali Alt 862 00:31:03,720 --> 00:31:06,560 plus in povečaj, ki radovedno prikazuje več gumbov. 863 00:31:06,560 --> 00:31:09,090 Torej, samo v vednost, če igrate s tem doma. 864 00:31:09,090 --> 00:31:12,870 Zdaj grem kliknite Start v pravkar Trenutek, ko podate zamudo, 865 00:31:12,870 --> 00:31:16,810 podobno, 200 milisekund tukaj, samo tako da bomo lahko videli, kaj se bo zgodilo. 866 00:31:16,810 --> 00:31:20,180 >> Zato trdim, da je to vizualizacija prvega algoritma 867 00:31:20,180 --> 00:31:23,730 ti fantje naredili, bubble sort, pri čemer smo zamenjali ljudi, par-modrih. 868 00:31:23,730 --> 00:31:27,490 Ključ vpogled v vizualizacijo je, da višina palic 869 00:31:27,490 --> 00:31:30,510 predstavlja velikost števila. 870 00:31:30,510 --> 00:31:32,210 Torej višji bar, večje število. 871 00:31:32,210 --> 00:31:33,680 Krajša bar, manjše število. 872 00:31:33,680 --> 00:31:38,630 In če ste opazili, da gremo skozi Prvi primer tega algoritma 873 00:31:38,630 --> 00:31:42,620 zamenjavo velike in majhne številke, tako da Manjše število na prvem mestu in 874 00:31:42,620 --> 00:31:44,280 Veliko število gre v desno. 875 00:31:44,280 --> 00:31:48,770 >> In takoj, ko smo dobili konec niza veliko več kot sedem številk, smo 876 00:31:48,770 --> 00:31:49,900 šel nazaj na začetek. 877 00:31:49,900 --> 00:31:51,140 In to pričakuje. 878 00:31:51,140 --> 00:31:54,860 Na skrajni levi, da malček se dogaja da bi zamenjali na stran, in to 879 00:31:54,860 --> 00:31:56,010 postopek se ponavlja. 880 00:31:56,010 --> 00:31:59,450 Zdaj je to vizualizacija hitro dobi dolgočasno, zato naj gredo naprej in ustavi 881 00:31:59,450 --> 00:32:04,170 da spremenite zakasnitve nekaj veliko hitreje, samo da bi dobili zdaj, občutek za 882 00:32:04,170 --> 00:32:05,060 Ta algoritem. 883 00:32:05,060 --> 00:32:07,840 >> Torej, čeprav sem jo pospešiti, to je kot nadgradnja mojega procesorja, nakup 884 00:32:07,840 --> 00:32:08,580 nov računalnik. 885 00:32:08,580 --> 00:32:12,980 Nisem bistveno spremenila moje algoritem, vendar lahko dejansko videli več 886 00:32:12,980 --> 00:32:16,800 očitno kot pri ljudeh, ki veliko Številke so bisernih do vrha, 887 00:32:16,800 --> 00:32:20,900 in na majhne številke so prepihovanja na dno. 888 00:32:20,900 --> 00:32:22,390 In zdaj to stvar tukaj razporejene. 889 00:32:22,390 --> 00:32:25,260 In kot praha, v kvadrate, obstaja samo nekaj knjigovodstvo tam 890 00:32:25,260 --> 00:32:28,010 vam prešteti, koliko primerjav ali koliko zamenjave so 891 00:32:28,010 --> 00:32:28,950 bilo dejansko narejeno. 892 00:32:28,950 --> 00:32:30,750 >> No, pa poskusite eno ostali pa bomo videli. 893 00:32:30,750 --> 00:32:37,116 Dovolite mi, kliknite tukaj mehurček vrste, in Naj izberejo, in to celo spletno stran 894 00:32:37,116 --> 00:32:38,936 je malo nečistnik. 895 00:32:38,936 --> 00:32:41,155 Oglejmo sprejeti tveganje in ga ponovno zagnati. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Takole. 898 00:32:45,030 --> 00:32:47,180 Torej, kaj je naredil izbor vrste. 899 00:32:47,180 --> 00:32:49,140 Ne vem, zakaj meni se pojavi tam. 900 00:32:49,140 --> 00:32:54,070 Oglejmo povečavo, da se določi, da bug, to spremeni do 50. 901 00:32:54,070 --> 00:32:56,020 Ah, kaj je dejansko naredil da je veliko hitreje. 902 00:32:56,020 --> 00:32:59,160 Pet milisekund ali tako, in začeti. 903 00:32:59,160 --> 00:33:00,470 >> Torej je ta izbor sort. 904 00:33:00,470 --> 00:33:03,070 Torej še enkrat, pomislite, kaj smo storil z ljudmi tukaj. 905 00:33:03,070 --> 00:33:08,490 Šli smo skozi niz in izbrano Najmanjše ponovno element 906 00:33:08,490 --> 00:33:09,250 znova in znova. 907 00:33:09,250 --> 00:33:11,110 Zdaj pa trdijo, da je še vedno precej slabo. 908 00:33:11,110 --> 00:33:15,010 To je bil še n kvadrat, Vzemi ali pusti, vendar je bilo v resničnem svetu, nekoliko 909 00:33:15,010 --> 00:33:18,280 hitreje, ker sem bil res ob nekoliko manj korake vsakič. 910 00:33:18,280 --> 00:33:19,800 Ampak mi govorimo samo kaj? 911 00:33:19,800 --> 00:33:21,830 Morda 40 ali tako bari tukaj? 912 00:33:21,830 --> 00:33:23,200 Ne govorimo 40 milijonov. 913 00:33:23,200 --> 00:33:27,430 Tako da ni povsem jasno, se mi, da je bil res velik dobiček. 914 00:33:27,430 --> 00:33:32,530 >> Dovolite mi, da zdaj iti nazaj in spremeniti v našem Tretji algoritem, ki je bil izbere 915 00:33:32,530 --> 00:33:33,180 Vstavitev vrste. 916 00:33:33,180 --> 00:33:36,380 In zdaj je res buggy, ker meni res ni treba dol. 917 00:33:36,380 --> 00:33:40,840 Torej, zdaj bomo se pomaknete nazaj tu gor in začeti ta algoritem. 918 00:33:40,840 --> 00:33:43,270 Poklič, start in stop. 919 00:33:43,270 --> 00:33:47,160 Torej je to ena vrsta ima precej vzorec z njim, pri čemer smo spet 920 00:33:47,160 --> 00:33:50,240 vstavljanje ljudi, ali V tem primeru, palice v 921 00:33:50,240 --> 00:33:52,620 njihovo ustrezno lokacijo. 922 00:33:52,620 --> 00:33:55,430 In to že storila, preden Obrnil sem se. 923 00:33:55,430 --> 00:33:58,940 Ampak tale je tudi v teoriji, še n kvadrat. 924 00:33:58,940 --> 00:34:01,430 >> Torej, da vidimo, če ne moremo povzeti te, kot sledi. 925 00:34:01,430 --> 00:34:04,750 Jaz grem naprej in samo, da nas neke skupne poti govoril 926 00:34:04,750 --> 00:34:08,489 o teh stvareh, naj vam predstavim samo malo zapis tukaj. 927 00:34:08,489 --> 00:34:12,480 Kmalu boste videli nekaj, kar se imenuje velika O, saj je dobesedno velika 928 00:34:12,480 --> 00:34:16,320 O. in na ta način, da računalnik znanstvenik ali matematik celo uporablja 929 00:34:16,320 --> 00:34:19,230 opisati časa vožnje nekega algoritma. 930 00:34:19,230 --> 00:34:21,400 Koliko korakov se je dejansko trajalo? 931 00:34:21,400 --> 00:34:25,080 >> Zdaj bom jaz spravila v zadrego s moj rokopis tu vsak trenutek. 932 00:34:25,080 --> 00:34:29,020 Ampak naj gredo naprej in rekli, da To bo velik O tukaj. 933 00:34:29,020 --> 00:34:33,610 In naj vam predstavim eno drugo Simbol, kapital omega. 934 00:34:33,610 --> 00:34:37,080 Omega se bo nasprotno v bistvu, z velikim O. ker veliko O 935 00:34:37,080 --> 00:34:40,790 sredstvo, v najslabšem primeru, koliko časa Morda nekateri algoritem sprejme v 936 00:34:40,790 --> 00:34:43,480 Pogoji n, omega bo je, koliko časa bi lahko bilo 937 00:34:43,480 --> 00:34:45,409 da v najboljšem primeru. 938 00:34:45,409 --> 00:34:48,090 In bomo videli, kaj mislimo s Najboljši primer v samo nekaj trenutkov. 939 00:34:48,090 --> 00:34:49,940 >> Torej, začnimo nekaj preprostega. 940 00:34:49,940 --> 00:34:54,719 Naj začnem z linearno iskanje. 941 00:34:54,719 --> 00:34:55,679 Torej ni sortiranja. 942 00:34:55,679 --> 00:34:58,000 Mi bomo to imenujemo linearno iskanje. 943 00:34:58,000 --> 00:35:01,140 In zdaj, da malo miza iz tega. 944 00:35:01,140 --> 00:35:06,600 Zdaj pa v primeru linearnega iskanju v najslabšem primeru, koliko korakov je 945 00:35:06,600 --> 00:35:11,770 se dogaja, da me bo najti Število samovoljne izbire? 946 00:35:11,770 --> 00:35:14,540 In tam je n skupno vrata ali n skupno število. 947 00:35:14,540 --> 00:35:15,940 Najslabšem primeru. 948 00:35:15,940 --> 00:35:18,800 Koliko korakov bom moral da bi našli številko 50 v matriki 949 00:35:18,800 --> 00:35:20,830 iz n vrat? 950 00:35:20,830 --> 00:35:21,410 In zakaj? 951 00:35:21,410 --> 00:35:23,680 Ker bi bilo vse Tako kot na koncu. 952 00:35:23,680 --> 00:35:27,120 Toliko kot Jennifer naleteli, Številka 50 je bilo vse tako kot, tako da v 953 00:35:27,120 --> 00:35:30,760 najslabšem primeru linearna iskanje je velik O n, bomo rekli. 954 00:35:30,760 --> 00:35:33,430 >> Kaj najboljšem primeru če dobiš res srečo? 955 00:35:33,430 --> 00:35:36,200 To je samo bo trajalo en korak, ali nespremenjeno število korakov. 956 00:35:36,200 --> 00:35:37,830 Torej bomo opisali, da kot 1.. 957 00:35:37,830 --> 00:35:39,010 Torej, to je zelo dobro. 958 00:35:39,010 --> 00:35:41,210 Kaj zdaj, če bomo naredili nekaj kot binarni iskanje? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Torej binarno iskanje, v najslabšem zadevo, je, koliko časa? 961 00:35:47,846 --> 00:35:49,250 >> [Interposing GLAS] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Torej, pravzaprav sem Slišal v nekaj mestih. 963 00:35:51,310 --> 00:35:56,390 Torej, to je pravzaprav log n, Vzemi ali pusti, saj, kot smo razdeliti seznam na polovici 964 00:35:56,390 --> 00:36:00,730 spet in spet in spet, smo sposobni najti končno vrednost, 965 00:36:00,730 --> 00:36:04,750 če je tam, vendar pa je ulov. 966 00:36:04,750 --> 00:36:08,590 Kaj je predpostavka, da moramo samoumevno, pri binarnem iskanju? 967 00:36:08,590 --> 00:36:09,700 To mora biti urejeno. 968 00:36:09,700 --> 00:36:12,770 To ni urejeno, se lahko razdeli stvar spet in spet pol, in ti 969 00:36:12,770 --> 00:36:15,490 Lahko greš levo, in lahko greš desno, in lahko greš levo in desno, ampak si 970 00:36:15,490 --> 00:36:18,070 ne boš našel element, če seznam ni urejen, ker 971 00:36:18,070 --> 00:36:18,790 ste morda zamudili. 972 00:36:18,790 --> 00:36:22,120 Ker vaše tolči, za odhod na levi ali desno, se bo napačno, če je 973 00:36:22,120 --> 00:36:23,420 res ne sortirajo. 974 00:36:23,420 --> 00:36:26,110 Torej je neke vrste skritih stroškov s pomočjo nekaj takega. 975 00:36:26,110 --> 00:36:29,250 >> Zdaj pa gremo v našo sortiranje algoritmi ne išče - 976 00:36:29,250 --> 00:36:31,140 oh, pravzaprav gremo v to prazno. 977 00:36:31,140 --> 00:36:33,190 Iskanje binarno v najboljšem primeru? 978 00:36:33,190 --> 00:36:36,290 Prav tako je 1, če je to le zgodi, da se v samem središču matrike, ali 979 00:36:36,290 --> 00:36:37,810 Sredi imeniku. 980 00:36:37,810 --> 00:36:39,710 Sedaj naredimo mehurček vrste. 981 00:36:39,710 --> 00:36:42,570 Torej še enkrat, zdaj vstopamo vrste, ne pa iskanja. 982 00:36:42,570 --> 00:36:47,220 >> V najslabšem primeru, koliko korakov smo naredili Trditev bubble sort bo trajalo? 983 00:36:47,220 --> 00:36:48,410 n kvadrat. 984 00:36:48,410 --> 00:36:49,200 Torej bom pripraviti, da. 985 00:36:49,200 --> 00:36:51,710 Oh, moj rokopis izgleda še slabše če je to predvideno, da je velik. 986 00:36:51,710 --> 00:36:52,510 Vse je v redu. 987 00:36:52,510 --> 00:36:53,570 Tako da je n kvadrat. 988 00:36:53,570 --> 00:36:59,460 In v najboljšem primeru mehurček vrste, koliko korakov je to bo trajalo? 989 00:36:59,460 --> 00:37:00,980 1, sem slišal. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, sem slišal. 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, sem slišal. 994 00:37:05,010 --> 00:37:06,670 Slišim 3? 995 00:37:06,670 --> 00:37:07,080 Vse je v redu. 996 00:37:07,080 --> 00:37:11,390 Tako sem slišal 1, n, 2, vendar naj poberem poleg vsaj prvonavedenega 997 00:37:11,390 --> 00:37:12,330 predlogi, 1. 998 00:37:12,330 --> 00:37:15,370 To ni slabo, instinkt, saj je nekako takole vzorec tukaj. 999 00:37:15,370 --> 00:37:19,670 Ampak, če to traja le 1 korak, kako v svet sem mogel trditi, da je seznam 1000 00:37:19,670 --> 00:37:22,900 so razporejene, ker če sem dovoljena le vzeti 1 korak, koliko elementov 1001 00:37:22,900 --> 00:37:25,230 Jaz bi dejansko, da preverite? 1002 00:37:25,230 --> 00:37:28,270 No, samo 1, kar pomeni, da je n minus 1 elemente, ki bi lahko iz 1003 00:37:28,270 --> 00:37:31,310 Da, in grem na veri po gledaš 1 element, ki 1004 00:37:31,310 --> 00:37:31,850 stvar je razvrščena. 1005 00:37:31,850 --> 00:37:33,930 Torej 1 se ne popravi tukaj. 1006 00:37:33,930 --> 00:37:35,710 Torej minimalno, koliko moram gledati? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposing GLAS] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n minus 1, ali res, n, ker moram gledati na vsak 1009 00:37:40,160 --> 00:37:42,190 element, se prepričajte, da to ni v okvari. 1010 00:37:42,190 --> 00:37:44,750 Ampak še enkrat, bomo nekako val našega roke pri manjših številkah in 1011 00:37:44,750 --> 00:37:47,100 predvidevamo, da, kot je n postane velika, oni nezanimiv vseeno. 1012 00:37:47,100 --> 00:37:48,380 Tako da je mehurček vrste. 1013 00:37:48,380 --> 00:37:49,830 In zdaj, kaj je naredil zadnji dve. 1014 00:37:49,830 --> 00:37:53,520 Izbor vrste, nato pa se bomo storiti vstavljanja vrste. 1015 00:37:53,520 --> 00:37:57,160 In potem bomo odpihnil um z nekaj veliko 1016 00:37:57,160 --> 00:37:58,926 boljši od vseh teh. 1017 00:37:58,926 --> 00:38:00,410 Vse je v redu. 1018 00:38:00,410 --> 00:38:04,700 >> Kaj je v najslabšem primeru teče čas izbirnem vrste? 1019 00:38:04,700 --> 00:38:05,680 >> ZVOČNIK 4: n kvadrat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n kvadrat, slišim. 1021 00:38:06,710 --> 00:38:09,790 Ampak zakaj n kvadrat, intuitivno? 1022 00:38:09,790 --> 00:38:11,170 >> ZVOČNIK 4: Ker smo pravkar storil. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Ker smo pravkar storil. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Dober odgovor. 1026 00:38:13,380 --> 00:38:16,660 Vendar intuitivno, zakaj je izbor sortiranje n kvadrat? 1027 00:38:16,660 --> 00:38:18,980 Kaj moramo storiti znova in znova? 1028 00:38:18,980 --> 00:38:22,570 Sva, da skeniranje skozi, se si najmanjši, ste 1029 00:38:22,570 --> 00:38:24,020 najmanjših, ste najmanjša. 1030 00:38:24,020 --> 00:38:27,480 In odobri, da smo sposobni sprejeti n koraki, potem je n minus 1, potem je n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Ampak, če ste nekako Seątejte vse, ali ga vzamete na veri, da sem dodal 1032 00:38:30,700 --> 00:38:34,810 jih je predhodno, dobimo približno n kvadrat minus nekaterih manjših številk. 1033 00:38:34,810 --> 00:38:36,730 Torej bom poklical to n kvadrat. 1034 00:38:36,730 --> 00:38:39,530 Ampak z izbiro vrste v najboljši primer, koliko korakov je 1035 00:38:39,530 --> 00:38:40,632 da me bodo? 1036 00:38:40,632 --> 00:38:41,840 >> ZVOČNIK 5: [neslišno] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: To je žal še n kvadrat, kajne? 1038 00:38:44,350 --> 00:38:49,590 Ker če sem izbiro najmanjši element, in smo imeli sedem ljudi tukaj, 1039 00:38:49,590 --> 00:38:53,280 Vem le, ko pridem do zelo Konec, ki sem ugotovila, najmanjši 1040 00:38:53,280 --> 00:38:55,670 Številka, kjer je on ali ona bi lahko bilo. 1041 00:38:55,670 --> 00:38:58,820 Ampak kako se mi zdi naslednja Najmanjše število? 1042 00:38:58,820 --> 00:39:00,160 Moram narediti novo sredino. 1043 00:39:00,160 --> 00:39:04,810 Torej, v najboljšem primeru, kar je vhod za izbiro vrste? 1044 00:39:04,810 --> 00:39:07,830 To je že seznam sort, številka ena, Številka dve, številka tri, številka štiri. 1045 00:39:07,830 --> 00:39:08,600 Ampak jaz sem računalnik. 1046 00:39:08,600 --> 00:39:10,190 Jaz lahko ogledate le na eni stvar naenkrat. 1047 00:39:10,190 --> 00:39:12,465 Ne morem se nekako stopijo korak nazaj, kot človek in pravi, 1048 00:39:12,465 --> 00:39:14,030 Ooh, to izgleda pravilna. 1049 00:39:14,030 --> 00:39:17,580 >> Ne morem odločati le v pravilnost Izbor razvrsti po izbiri 1050 00:39:17,580 --> 00:39:18,370 Najmanjše število. 1051 00:39:18,370 --> 00:39:21,390 A tudi če se mi zdi številka ena prvič, če ne vem kaj o 1052 00:39:21,390 --> 00:39:24,460 druge številke, ki jih jaz ne, vse sem vem, da sem dobil niz 1053 00:39:24,460 --> 00:39:27,930 ali niz vrat za katere številke, edini način, vem, da je eden 1054 00:39:27,930 --> 00:39:28,680 je najmanjša? 1055 00:39:28,680 --> 00:39:32,440 Če dobim vso pot sem in zavedaš, Prekleto, eden je bil res najmanjši. 1056 00:39:32,440 --> 00:39:34,870 >> Ampak kako naj potem ugotovijo, da dve je naslednji najmanjši? 1057 00:39:34,870 --> 00:39:38,350 Ki jih počne isto neučinkovitost znova in znova. 1058 00:39:38,350 --> 00:39:42,210 Torej, končno, z vstavljanja vrste, kako, v najslabšem primeru, 1059 00:39:42,210 --> 00:39:44,990 smo rekli, da opravlja? 1060 00:39:44,990 --> 00:39:49,100 To je preveč n kvadrat. 1061 00:39:49,100 --> 00:39:53,020 In kako približno pri najboljšem primeru? 1062 00:39:53,020 --> 00:39:56,282 Bomo pustite, da se kot Cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Bomo izpolnite v tem praznem naslednjem trenutku, ampak najprej naj vam predlagam, da 1064 00:40:00,090 --> 00:40:02,620 bistveno boljši od vsi ti, v redu? 1065 00:40:02,620 --> 00:40:05,220 >> Torej mislite sami, kaj vstavljanje vrsta se bo. 1066 00:40:05,220 --> 00:40:06,910 No, to ni bilo preveč dramatično, ker sem edini 1067 00:40:06,910 --> 00:40:08,970 da je videl spremembo. 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 Torej, tukaj imamo nekoliko drugačna predstavitev. 1071 00:40:12,615 --> 00:40:16,580 Če sem povečate tukaj, boste videli, da je na Na levi strani imamo mehurček vrste, pri 1072 00:40:16,580 --> 00:40:20,740 srednji imamo izbiro vrste in na skrajni desni, imamo nekaj smo 1073 00:40:20,740 --> 00:40:23,380 niso pogledal še imenovano zlivanjem. 1074 00:40:23,380 --> 00:40:26,080 Vendar menijo, kar smo bili tukaj doslej še danes. 1075 00:40:26,080 --> 00:40:29,200 Ko Jennifer prvič prišel na oder, smo šli skozi niz številk 1076 00:40:29,200 --> 00:40:33,750 znova in znova, z linearno iskanje, in imamo linearni čas teče, veliki O 1077 00:40:33,750 --> 00:40:35,100 n, tako rekoč. 1078 00:40:35,100 --> 00:40:41,000 >> Ko si zdaj prvi teden razred, ko smo imeli deli in vladaj, 1079 00:40:41,000 --> 00:40:43,740 in smo imeli telefonski imenik solzenje, in Jennifer, in smo skupaj 1080 00:40:43,740 --> 00:40:47,500 spodbudil, da ključni uvid, ki je bil znova in znova se ga 1081 00:40:47,500 --> 00:40:50,930 nekako vrže proč, metali proč, metanje stran, polovica problem, ali 1082 00:40:50,930 --> 00:40:55,320 na splošno, tako težave na pol, in nato z obdelavo manjši del 1083 00:40:55,320 --> 00:40:59,630 problem kot konceptualno enakovredni na drugi strani pa smo nekako pa 1084 00:40:59,630 --> 00:41:00,910 bistveno bolje. 1085 00:41:00,910 --> 00:41:04,720 Ampak s mehurčkov vrste, z izbiro vrste, z vstavljanja vrste, smo lahko smo 1086 00:41:04,720 --> 00:41:06,560 nobena takšna spoznanja, da Jennifer ni. 1087 00:41:06,560 --> 00:41:10,220 Imamo precej preprosto hodil nazaj in tja cel kup časa in mi 1088 00:41:10,220 --> 00:41:12,650 uglasili stvari malo, menjava v tem vrstnem redu, morda 1089 00:41:12,650 --> 00:41:13,730 vstavljanje ali izbiro. 1090 00:41:13,730 --> 00:41:16,950 Toda na koncu dneva, sem veliko v nerodni hoji naprej in nazaj. 1091 00:41:16,950 --> 00:41:21,160 Mi ni res vzvoda nekaj pameten kot Jennifer maral tako 1092 00:41:21,160 --> 00:41:22,040 in osvajanje. 1093 00:41:22,040 --> 00:41:25,620 >> Torej zlivanjem, nasprotno, kar smo ne bomo videli do naslednjega tedna, da se dogaja 1094 00:41:25,620 --> 00:41:29,540 vzvoda, da je ključna ideja z deljenjem vnos in nato razpolovi, nato 1095 00:41:29,540 --> 00:41:30,580 prepolovili, nato pa razpolovi. 1096 00:41:30,580 --> 00:41:34,590 In na vsaki ponovitvi te zanke, sortiranje levo polovico, in prav 1097 00:41:34,590 --> 00:41:38,200 pol, nato levo polovico levi polovici in desno polovico levi, nato 1098 00:41:38,200 --> 00:41:40,990 levi polovici desni polovici in desni polovici desni polovici. 1099 00:41:40,990 --> 00:41:42,840 In spet in spet ponavlja. 1100 00:41:42,840 --> 00:41:46,170 >> Torej boste to videli vizualno, vendar to je tisto, kar nas čaka naslednji teden. 1101 00:41:46,170 --> 00:41:49,760 In na splošno, ko mislimo, da malo malo težje od takšnih težav. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Smo n kvadrat na levi strani, n kvadrat v sredini in n 1104 00:41:57,970 --> 00:41:59,400 log n na desni strani. 1105 00:41:59,400 --> 00:42:00,590 Torej je tvoj pravi Alpinista. 1106 00:42:00,590 --> 00:42:02,040 Se vidimo v ponedeljek. 1107 00:42:02,040 --> 00:42:05,163 >> [APLAVZ]