1 00:00:00,000 --> 00:00:11,100 >> [MUSIC PLAYING] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Rendben. 3 00:00:11,490 --> 00:00:12,170 Szóval szívesen vissza. 4 00:00:12,170 --> 00:00:15,180 Ez CS50, és az is A három hét végére. 5 00:00:15,180 --> 00:00:17,770 >> Így felidézni az elmúlt néhány hét, mi már töltött egy kicsit a 6 00:00:17,770 --> 00:00:20,820 idő a C, a programozás, a szintaxis. 7 00:00:20,820 --> 00:00:24,680 És ez teljesen normális, ha még mindig küzd Probléma Set 2, hogy 8 00:00:24,680 --> 00:00:25,950 dörömböl a fejét a falba. 9 00:00:25,950 --> 00:00:28,310 Ez rejtélyes külsejű hibaüzenetek és a hibákat, hogy 10 00:00:28,310 --> 00:00:29,220 nem egészen üldözőbe le. 11 00:00:29,220 --> 00:00:32,310 Mert, biztos lehetsz benne, hogy csak egy Néhány héten belül akkor tekint vissza 12 00:00:32,310 --> 00:00:35,930 dolgok, mint Caesar, és a [? V-genair,?] talán Crack, és 13 00:00:35,930 --> 00:00:40,050 észre, hogy milyen messzire jöttél egy rövid idő alatt. 14 00:00:40,050 --> 00:00:43,670 Tehát, ha ez vigasztal, Tarts ki most. 15 00:00:43,670 --> 00:00:46,610 >> Ma azonban kezdjük átmenet a dolgok magasabb szintre. 16 00:00:46,610 --> 00:00:49,820 És elkezdjük magától értetődőnek, hogy tudjátok, hogyan kell programozni, vagy 17 00:00:49,820 --> 00:00:52,090 legalább kezdetei hogy kényelmet. 18 00:00:52,090 --> 00:00:56,520 És kezdjük, hogy fontolja meg, hogyan lehet megy a tervezés programokat 19 00:00:56,520 --> 00:00:57,440 hatékonyan. 20 00:00:57,440 --> 00:01:01,090 Hogyan lehet menni optimalizálása hatékonyságát algoritmusok és 21 00:01:01,090 --> 00:01:03,110 általában több megoldása érdekes probléma. 22 00:01:03,110 --> 00:01:06,850 És kezd magától értetődőnek, hogy a ha akarnánk, tudnánk kódot fel semmilyen 23 00:01:06,850 --> 00:01:08,350 A példa van szem előtt. 24 00:01:08,350 --> 00:01:11,430 Így ma már ne érintse meg a billentyűzetet bármilyen formában a kódot. 25 00:01:11,430 --> 00:01:15,150 Ez lesz sokkal magasabb szinten, és végül, a problémamegoldás. 26 00:01:15,150 --> 00:01:20,490 >> Tehát, hogy az ezen a ponton, hadd javaslatot hogy a következő hét 27 00:01:20,490 --> 00:01:24,290 téglalapok képviseli hét ajtó mögött amely egy csomó 28 00:01:24,290 --> 00:01:26,340 számok, amelyek közül az a szám, 50. 29 00:01:26,340 --> 00:01:30,470 Hadd vetíteni ezt a képernyő itt is. 30 00:01:30,470 --> 00:01:36,770 És javaslom, hogy szükségünk van egy önkéntes segítsen megtalálni nekem a szám előtt 31 00:01:36,770 --> 00:01:38,140 az internet ide. 32 00:01:38,140 --> 00:01:40,755 Gyere fel, a rózsaszín. 33 00:01:40,755 --> 00:01:43,050 Rendben van. 34 00:01:43,050 --> 00:01:43,930 Mi a neve? 35 00:01:43,930 --> 00:01:44,850 >> Jennifer: [hangtalan] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Tessék? 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 Rendben, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Örülök, hogy megismerhetem. 41 00:01:47,630 --> 00:01:48,370 Gyere fel. 42 00:01:48,370 --> 00:01:52,430 Tehát ezek itt hét ajtók, és milyen Szeretném, ha tenni minket, 43 00:01:52,430 --> 00:01:56,560 előtt minden az osztálytársaival, A hozzánk a szám, 50. 44 00:01:56,560 --> 00:02:00,860 Találni egy számot, akkor kandikál mögött bármelyik ajtó egyszerűen megérinti 45 00:02:00,860 --> 00:02:03,030 az egyik ajtót, és felfedi annak számát. 46 00:02:03,030 --> 00:02:06,080 És lássuk, milyen gyorsan talál minket a számot, 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 Szép munka. 54 00:02:17,350 --> 00:02:18,040 Rendben van. 55 00:02:18,040 --> 00:02:19,906 Tapsot Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Taps] 57 00:02:21,530 --> 00:02:22,320 >> Rendben van. 58 00:02:22,320 --> 00:02:25,254 Szóval, mi volt a stratégia megtalálni a számot, 50? 59 00:02:25,254 --> 00:02:27,222 >> Jennifer: Um, azt gondoltam, ha - 60 00:02:27,222 --> 00:02:27,714 [Nem hallható] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Adj egy percet. 63 00:02:29,630 --> 00:02:32,420 Így volt a stratégia megtalálni a számot, 50? 64 00:02:32,420 --> 00:02:34,760 >> Jennifer: Szóval csak elindítani a kezd, hogy mi az első szám 65 00:02:34,760 --> 00:02:38,590 volt, és úgy gondoltam, talán ha ők sorrendje, én csak tartani 66 00:02:38,590 --> 00:02:39,970 megérinti feljebb? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 És úgy tűnik, hogy megtalálta hogy ez a helyzet. 69 00:02:42,910 --> 00:02:45,670 Bár hadd húzza vissza a rétegek csak egy kicsit, és azt szeretné, hogy menjen 70 00:02:45,670 --> 00:02:47,640 előre, és felfedi a többi ajtó akkor választott? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> Jennifer: Ó, drágám. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> Jennifer: Szóval én csak szerencsém volt. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Szóval szerencsém volt. 76 00:02:55,270 --> 00:02:55,710 Rendben van. 77 00:02:55,710 --> 00:02:56,795 Tehát nem rossz. 78 00:02:56,795 --> 00:02:58,750 De ez egy érdekes betekintést, nem igaz? 79 00:02:58,750 --> 00:03:01,870 Ha feltételezzük, és nem kap, Valóban, egy kicsit szerencsés is. 80 00:03:01,870 --> 00:03:05,350 De ha feltételezzük, hogy a számok sorrendje, lehet pontosabban 81 00:03:05,350 --> 00:03:08,750 , hogy hogyan befolyásolja a viselkedése? 82 00:03:08,750 --> 00:03:11,715 >> Jennifer: Tehát, ha őket sorrendje, azt gondoltam, a legkisebbtől a legnagyobbig. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> Jennifer: Vagy, ha ez végül is igazán nagy, akkor legnagyobbtól a legkisebb felé. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Így legnagyobb a legkisebb, vagy legkisebbtől a legnagyobbig. 87 00:03:18,170 --> 00:03:21,990 De hadd javaslom, tegyük fel, hogy van ütött szerencsétlen, és tegyük fel, hogy a 88 00:03:21,990 --> 00:03:26,840 nem, sőt, válogatott, hány az ajtók is meg kellett volna kandikál 89 00:03:26,840 --> 00:03:28,590 mögött, hogy a legrosszabb esetben? 90 00:03:28,590 --> 00:03:29,860 >> Jennifer: Mindannyian. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Mindegyik. 92 00:03:30,420 --> 00:03:31,740 Szóval általánosítani, hogy az n. 93 00:03:31,740 --> 00:03:34,790 Előfordul, hogy 7, de most inkább Általában azt mondják, az n kapuit a 94 00:03:34,790 --> 00:03:35,650 képernyő itt. 95 00:03:35,650 --> 00:03:40,110 Így a legrosszabb esetben, ha volna mögé nézni 7 ajtók, vagy n ajtók. 96 00:03:40,110 --> 00:03:44,140 És ez tényleg, ez egy kicsit szerencse ma, de ez tényleg egy lineáris 97 00:03:44,140 --> 00:03:46,440 algoritmus a fajta, még akkor is, volt ilyen kihagyás körül. 98 00:03:46,440 --> 00:03:47,080 Ez tisztességes? 99 00:03:47,080 --> 00:03:47,500 >> Jennifer: Igen. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Nos, lássuk, ha a stratégia változik, ha mozgok, hogy 101 00:03:50,000 --> 00:03:52,190 A második példa itt 7 különböző ajtók. 102 00:03:52,190 --> 00:03:55,240 Ugyanazt a számot, de ez a alkalommal, amikor a helyére kerül. 103 00:03:55,240 --> 00:03:58,350 Mi a stratégia itt lesz, próbál tenni az eszed, mi 104 00:03:58,350 --> 00:03:59,310 A többi szám is - 105 00:03:59,310 --> 00:03:59,930 >> Jennifer: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - korábban? 107 00:04:02,290 --> 00:04:03,180 >> Jennifer: Kezdjük az első. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Rendben. 109 00:04:03,540 --> 00:04:05,190 Kezdjük az elsővel. 110 00:04:05,190 --> 00:04:05,960 4.. 111 00:04:05,960 --> 00:04:08,810 Most hová fogsz menni, és miért? 112 00:04:08,810 --> 00:04:10,040 >> Jennifer: 4 nagyon kicsi. 113 00:04:10,040 --> 00:04:12,500 Tehát, ha ők valami talán legkisebb a legnagyobb, meg kell 114 00:04:12,500 --> 00:04:13,290 legyen kétszer, és -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Lássuk, amely úgy gondolja? 117 00:04:15,990 --> 00:04:19,050 >> Jennifer: Próbálja az utolsó. 118 00:04:19,050 --> 00:04:19,500 Szép. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: nagyon jól tette. 120 00:04:20,880 --> 00:04:21,860 Rendben van. 121 00:04:21,860 --> 00:04:23,010 >> [Taps] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Szóval tényleg ezt rettenetesen, mert te 124 00:04:26,790 --> 00:04:27,700 csinálja jól. 125 00:04:27,700 --> 00:04:31,150 Ami hagy minket nem bizonyos pontokat. 126 00:04:31,150 --> 00:04:32,565 Így próbáljuk dobni ide. 127 00:04:32,565 --> 00:04:34,560 >> Jennifer: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Nagyon jó kész, mégis. 129 00:04:35,980 --> 00:04:39,060 Így kezdődött az elején, Ön látta, hogy ez 4, akkor 130 00:04:39,060 --> 00:04:40,240 költözött a végére. 131 00:04:40,240 --> 00:04:42,320 De tegyük fel, hogy nem szerencsés ott, és tegyük fel, 50 132 00:04:42,320 --> 00:04:42,890 valahol máshol. 133 00:04:42,890 --> 00:04:46,190 Amit a harmadik lépés volt? 134 00:04:46,190 --> 00:04:47,680 >> Jennifer: Menj vissza az elejére. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Vissza az elejére. 136 00:04:48,320 --> 00:04:51,320 OK, így akkor már megérintett ezt az ajtót, ami 8. 137 00:04:51,320 --> 00:04:51,660 Rendben van. 138 00:04:51,660 --> 00:04:52,650 Szóval ez nem 50. 139 00:04:52,650 --> 00:04:55,380 Hová is néztem a következő lépés? 140 00:04:55,380 --> 00:04:56,720 >> Jennifer: Ha nem tudják, hogy rendezve. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Helyes. 142 00:04:57,005 --> 00:04:58,490 Nos, ha nem tudja, voltak rendezve - 143 00:04:58,490 --> 00:04:58,700 >> Jennifer: Ó, nem tudja, igen. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - de nem tetted tudja, hol 50 volt még? 145 00:05:00,910 --> 00:05:01,785 >> Jennifer: Csak menj tovább. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Rendben. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Folytasd. 149 00:05:03,800 --> 00:05:05,270 OK, hogy tudok dolgozni. 150 00:05:05,270 --> 00:05:05,610 >> Jennifer: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Most, ha csak majd menj tovább, mi a 152 00:05:07,210 --> 00:05:09,680 algoritmus háruló hátrált. 153 00:05:09,680 --> 00:05:10,740 >> Jennifer: A lineáris -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: Ez a fajta lineáris. 155 00:05:11,820 --> 00:05:13,480 De hadd javasolja, legyen nekem fel a helyszínen. 156 00:05:13,480 --> 00:05:14,900 Hadd frissíteni kell az oldalt. 157 00:05:14,900 --> 00:05:17,120 ugyanazt a számot, ugyanabban az elrendezésben, ugyanaz ajtók. 158 00:05:17,120 --> 00:05:21,350 De gondolom, vissza, hogy az első napon osztály, amikor elszakadt a telefonkönyvet 159 00:05:21,350 --> 00:05:25,480 fele, valami, és mi Stratégiánk ott? 160 00:05:25,480 --> 00:05:26,450 >> Jennifer: Kezdjük a közepén. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Így kezdődik a közepén. 163 00:05:27,610 --> 00:05:28,790 Szóval menjünk előre, és szimulálni ezt. 164 00:05:28,790 --> 00:05:30,720 Kezdjük a középső felfedve, hogy ajtót. 165 00:05:30,720 --> 00:05:31,660 Így a 16-os számú. 166 00:05:31,660 --> 00:05:35,290 Tehát mi is az erős fickó volna, Ki tépte a telefonkönyv a felére, 167 00:05:35,290 --> 00:05:38,450 hogy a következő kitalálni? 168 00:05:38,450 --> 00:05:39,400 >> Jennifer: Menj el ezzel a felét. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: És miért a jobb? 170 00:05:41,700 --> 00:05:43,900 >> Jennifer: Ha ők valami legkisebb a legnagyobb, akkor 50 kell 171 00:05:43,900 --> 00:05:44,720 az ennek érdekében. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Jó. 173 00:05:44,920 --> 00:05:45,390 Teljesen ésszerű. 174 00:05:45,390 --> 00:05:48,380 Szóval, mint egy telefonkönyv, megy a jobb szemben a bal oldalon, de itt 175 00:05:48,380 --> 00:05:49,500 a kulcs elvihető. 176 00:05:49,500 --> 00:05:53,930 Most is dobja el, és ne tépje le, a fele ezt a problémát, így ha nem 177 00:05:53,930 --> 00:05:55,970 7 ajtók, de tényleg csak 3. 178 00:05:55,970 --> 00:05:57,870 Ami nagyjából a fele a a probléma nagyságát. 179 00:05:57,870 --> 00:05:58,350 Rendben van. 180 00:05:58,350 --> 00:06:01,890 Tehát most, hogy mit kellett volna tenni, miután jobbra? 181 00:06:01,890 --> 00:06:05,870 >> Jennifer: Tehát 16 még mindig elég kicsi, képest 50, így talán megpróbálom, 182 00:06:05,870 --> 00:06:06,700 mint ez. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Rendben. 184 00:06:07,890 --> 00:06:08,720 42.. 185 00:06:08,720 --> 00:06:10,830 Jól van, most mi a ösztön mondom? 186 00:06:10,830 --> 00:06:12,100 >> Jennifer: Én dobni ezt, és aztán csak - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Jó, akkor dobja el bal oldalán is. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - vedd ezt. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: És a jobb oldalon. 191 00:06:15,530 --> 00:06:15,760 >> Jennifer: Igen. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Tehát annak ellenére, hogy nehéz hogy talán, ha már csak 193 00:06:17,820 --> 00:06:21,320 7 ajtók, gondolj, most az összhang a 194 00:06:21,320 --> 00:06:22,620 algoritmust csak alkalmazni. 195 00:06:22,620 --> 00:06:24,510 Az előző esetben nem szerencsés, ami nagyon jó volt. 196 00:06:24,510 --> 00:06:26,540 De nem használ heurisztikus, Azt mondanám. 197 00:06:26,540 --> 00:06:29,150 Használt fajta az ösztönök, és tudva, hogy válogatott, ha ez elég 198 00:06:29,150 --> 00:06:31,600 kicsi az elején, természetesen, most már van, hogy menjen inkább a jobb. 199 00:06:31,600 --> 00:06:34,990 De bizonyos értelemben, akkor szerencséje, mert talán ez volt a 100-as 200 00:06:34,990 --> 00:06:36,220 50 és talán több volt a közepén. 201 00:06:36,220 --> 00:06:37,910 Lehet, hogy 50 volt még itt. 202 00:06:37,910 --> 00:06:40,960 >> De amit tett, egy kicsit másképp ebben az időben volt, akkor nem ugyanaz a dolog 203 00:06:40,960 --> 00:06:42,150 újra és újra. 204 00:06:42,150 --> 00:06:45,310 És azt állítják, hogy amit most volt, bár befolyásolja a telefon 205 00:06:45,310 --> 00:06:48,100 könyv például, valami sokkal több algoritmikus, és még sok minden 206 00:06:48,100 --> 00:06:49,930 kevésbé speciális tokozású. 207 00:06:49,930 --> 00:06:51,620 Sokkal kevésbé ösztönös. 208 00:06:51,620 --> 00:06:57,160 Így a végén a nap, hogyan jellemezné a hatékonyságát 209 00:06:57,160 --> 00:07:00,530 els ˝ o, hol járt balról jobbra, szemben a 210 00:07:00,530 --> 00:07:03,430 második algoritmus itt? 211 00:07:03,430 --> 00:07:06,460 >> Jennifer: Ez kell, mondjuk, talán felére az idő, vagy még több, igen. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, talán még inkább. 213 00:07:07,320 --> 00:07:10,150 Nézzük nyomja egy kicsit nehezebb, hogy. 214 00:07:10,150 --> 00:07:13,030 Ami igazán, ha továbbra is ezt logika, akkor biztosan a felére csökkent 215 00:07:13,030 --> 00:07:15,830 futó idő a második algoritmus dobtak el fele 216 00:07:15,830 --> 00:07:18,470 számok, de mit teszünk a következő iteráció, amikor Jennifer kiderült 217 00:07:18,470 --> 00:07:20,615 a második szám? 218 00:07:20,615 --> 00:07:22,830 >> Mi felére csökkent a száma az ajtók újra. 219 00:07:22,830 --> 00:07:25,270 És akkor mit csinálunk utána, hogy ha több volt ajtó játszani? 220 00:07:25,270 --> 00:07:27,520 Azt felére őket, és újra, és újra, és újra. 221 00:07:27,520 --> 00:07:30,420 És ez olyan volt, mint ti srácok állva az első héten 222 00:07:30,420 --> 00:07:33,000 osztály fele ülsz le félig A ülsz le, a fele meg 223 00:07:33,000 --> 00:07:35,440 leült, amíg egy magányos lélek állt. 224 00:07:35,440 --> 00:07:39,050 És azt mondta, hogy a futási ideje , hogy a lépések száma elég volt 225 00:07:39,050 --> 00:07:40,430 a sorrendben, mi? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [hangtalan] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Tehát log alap 2 n, vagy csak egyszerűbben, jelentkezzen n. 228 00:07:43,970 --> 00:07:45,060 Tehát valami logaritmikus. 229 00:07:45,060 --> 00:07:48,380 És a grafikon volt nem egy egyenes vonal hogy csak rosszabb és rosszabb lesz, nem volt 230 00:07:48,380 --> 00:07:52,490 ezt az érdekes görbe, ami nem hogy olyan rossz az idő múlásával. 231 00:07:52,490 --> 00:07:53,910 Szóval tartsd ezt az elképzelést. 232 00:07:53,910 --> 00:07:54,690 Nézzük köszönöm Jennifer. 233 00:07:54,690 --> 00:07:56,150 Köszönöm, hogy jön fel. 234 00:07:56,150 --> 00:07:57,400 És egy pillanat. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 No asztali lámpa ma, de megvan CS50 stressz labda. 237 00:08:02,925 --> 00:08:03,420 >> Jennifer: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Rendben, itt. 239 00:08:04,410 --> 00:08:06,545 Köszönjük, hogy ebből A stressz itt. 240 00:08:06,545 --> 00:08:07,350 Rendben van. 241 00:08:07,350 --> 00:08:10,620 Szóval ha most nem formálissá ezt egy kicsit. 242 00:08:10,620 --> 00:08:14,820 Tehát újra, amit most tett, lényegében ugyanaz, mint a mi 243 00:08:14,820 --> 00:08:16,660 abban az első héten. 244 00:08:16,660 --> 00:08:23,780 De ahelyett, hogy vége csak egy lineáris algoritmus, amit ábrázolt 245 00:08:23,780 --> 00:08:27,210 korábban, mint ez egyenes vonal, amely, ha teszünk még egy ajtó 246 00:08:27,210 --> 00:08:29,610 a képernyőn, majd Jennifer lenne kellett nézni, potenciálisan 247 00:08:29,610 --> 00:08:30,600 mögött még egy ajtó. 248 00:08:30,600 --> 00:08:33,490 Ha fel két ajtó, ő lehet, hogy mögé nézni két ajtó. 249 00:08:33,490 --> 00:08:35,990 >> És így volt ez a lineáris közötti kapcsolat a méret a 250 00:08:35,990 --> 00:08:39,059 probléma, mondjuk, az x-tengely mentén, és a mennyi időt vesz igénybe, 251 00:08:39,059 --> 00:08:40,440 oldja meg az y. 252 00:08:40,440 --> 00:08:43,330 De a kép voltam utalva, hogy korábban volt ez a zöld vonal. 253 00:08:43,330 --> 00:08:45,970 Zöld szándékosan, mert csak jobban érezte magát. 254 00:08:45,970 --> 00:08:49,790 Elméletileg, az algoritmus, amikor megcsináltuk A telefonkönyv, amikor megcsináltuk 255 00:08:49,790 --> 00:08:52,420 veletek számít egymást, és a második esetben, amikor csak Jennifer 256 00:08:52,420 --> 00:08:55,250 tette fel itt, ez valami Az alapvetően jobb. 257 00:08:55,250 --> 00:08:57,180 Mivel ez nem csak kétszer olyan gyors. 258 00:08:57,180 --> 00:08:58,870 Még csak nem is négyszer olyan gyorsan. 259 00:08:58,870 --> 00:09:03,290 Ez teljes mértékben függ, hogy milyen a a bemeneti mérete volt, hogy hány 260 00:09:03,290 --> 00:09:05,220 lépések végső soron volt. 261 00:09:05,220 --> 00:09:08,040 >> És így ez az egyszerű ötlet, hogy mi minden volt számára biztosították a telefonkönyvben, 262 00:09:08,040 --> 00:09:10,200 hasonlóképpen lehet alkalmazni valami, mint ez. 263 00:09:10,200 --> 00:09:12,380 És ez talán még véletlenül ismert, ahogy azt 264 00:09:12,380 --> 00:09:13,940 elképzelni, oszd meg és uralkodj. 265 00:09:13,940 --> 00:09:16,390 Nem úgy, mint amit tett, természetesen, A telefonkönyv. 266 00:09:16,390 --> 00:09:18,300 >> De a pszeudokódját, emlékszem, volt ez. 267 00:09:18,300 --> 00:09:21,800 Így nem fog még egyszer, de emlékszem , hogy az első héten, mindannyian felálltak 268 00:09:21,800 --> 00:09:25,140 a másik felét meg leült, a fele ültél le, a fele meg leült. 269 00:09:25,140 --> 00:09:29,280 Ez az algoritmus végre a kicsit egy csaló módon, az, hogy ez 270 00:09:29,280 --> 00:09:32,870 nem csak az egyik én számolás, alapvetően, hatékonyabban. 271 00:09:32,870 --> 00:09:35,830 Ebben az esetben én is kihasználva másodlagos forrás. 272 00:09:35,830 --> 00:09:39,470 Valahogy, több processzor, több agy, több okos ember van a 273 00:09:39,470 --> 00:09:42,740 szoba is segítettél kap valamit lineáris valami 274 00:09:42,740 --> 00:09:45,190 logaritmikus, valamiben piros valami zöld. 275 00:09:45,190 --> 00:09:48,650 >> De ebben az esetben, Jennifer egyedül képes alapvetően javítja fel a 276 00:09:48,650 --> 00:09:52,370 teljesítménye az első algoritmus, újra, csak gondoltam, egy kicsit nehezebb. 277 00:09:52,370 --> 00:09:56,650 És most, ha eljön az ideje, hogy végre ezeket a dolgokat, kitalálni 278 00:09:56,650 --> 00:10:00,670 milyen sornyi kódot lehet írni, mint hogy lehet megismételni újra, és 279 00:10:00,670 --> 00:10:03,350 újra, és újra, valami egy hurok módon. 280 00:10:03,350 --> 00:10:06,370 Mert nem megy, hogy a luxus, mint a Jennifer volt az első, a 281 00:10:06,370 --> 00:10:10,460 csak egy csomó IFS és azt mondják, hmm, ha ez az első szám 4, 282 00:10:10,460 --> 00:10:11,800 hadd ugrani egészen a végéig. 283 00:10:11,800 --> 00:10:14,180 Ó, ha ez a szám túl nagy, hadd mozog önkényesen vissza 284 00:10:14,180 --> 00:10:15,220 a második elem. 285 00:10:15,220 --> 00:10:18,210 Megtudja, hogy ez lesz a sok nehezebb hivatalossá, amit az emberek 286 00:10:18,210 --> 00:10:21,270 magától értetődőnek, mint kedvező heurisztikus, de a számítógép csak 287 00:10:21,270 --> 00:10:23,260 fog tenni, amit mondani, hogy igen. 288 00:10:23,260 --> 00:10:25,280 >> Most ez nagyon érdekes következményei. 289 00:10:25,280 --> 00:10:29,950 Ez a grafikon a fajta célja, hogy egyfajta elborít vizuálisan, de észre, amikor 290 00:10:29,950 --> 00:10:32,230 az egyenes vonal a grafikonon? 291 00:10:32,230 --> 00:10:35,330 Hol van a lineáris grafikon hogy hívjuk n? 292 00:10:35,330 --> 00:10:37,580 Nos, ez a fajta alja felé ezt a képet, nem igaz? 293 00:10:37,580 --> 00:10:40,500 Tehát minden, amit tettem az, hogy mi már egyfajta ránagyít az x tengely és az 294 00:10:40,500 --> 00:10:44,780 y-tengely, hogy próbálja meg egy értelemben, hogy mi más típusú görbék néz. 295 00:10:44,780 --> 00:10:47,760 >> És a pontos részletek a matematikai kifejezések ma nem számít annyira 296 00:10:47,760 --> 00:10:52,440 sok, de észrevettem, hogy van egy csomó algoritmusok sokkal rosszabb, mint a 297 00:10:52,440 --> 00:10:53,470 valamit, ami lineáris. 298 00:10:53,470 --> 00:10:55,410 Sőt, n kockára vágott néz ki rosszul. 299 00:10:55,410 --> 00:10:58,400 2. A n úgy néz ki, nagyon rossz. n kockás néz ki rosszul. 300 00:10:58,400 --> 00:11:01,630 És majd meglátjuk, mi néhány ilyen Lehet, hogy a valóságban ma. 301 00:11:01,630 --> 00:11:05,430 És log n nem érzi magát olyan rosszul, de jobb, mint n log alapja 2 n. 302 00:11:05,430 --> 00:11:08,080 De tudod, hogy lett volna még inkább hihetetlen, ha Jennifer, vagy mi, 303 00:11:08,080 --> 00:11:12,910 , hogy az első héten jött össze valamit, ami log log n. 304 00:11:12,910 --> 00:11:15,880 >> Más szóval, van ez az egész a lehetséges megoldások 305 00:11:15,880 --> 00:11:18,570 problémák, de még itt is, értesítés mi fog történni. 306 00:11:18,570 --> 00:11:22,910 Mikor kicsinyíteni, melyik görbék lesz bizonyítani, hogy az abszolút 307 00:11:22,910 --> 00:11:26,630 legrosszabb az is a képernyőn most? 308 00:11:26,630 --> 00:11:28,680 Tehát n kocka néz ki rossz abban a pillanatban. 309 00:11:28,680 --> 00:11:32,470 De ha kicsinyíteni, és még több a x és az y tengely, ki fog 310 00:11:32,470 --> 00:11:34,550 dominálnak végül? 311 00:11:34,550 --> 00:11:37,120 Így tulajdonképpen kiderül, hogy a 2 a n, és akkor ezt meg csak a 312 00:11:37,120 --> 00:11:39,990 dugulás néhány egyre nagyobb számokat, és látni fogod, hogy a 2 a 313 00:11:39,990 --> 00:11:42,070 n, sőt, egyre nagyobb lesz sokkal gyorsabb. 314 00:11:42,070 --> 00:11:45,530 Ha tényleg kicsinyíteni, 2 a n algoritmus teljesen szar. 315 00:11:45,530 --> 00:11:48,170 Úgy értem, ez fog tartani egy kicsit az idő a 316 00:11:48,170 --> 00:11:49,460 számítógép lemorzsolódás keresztül. 317 00:11:49,460 --> 00:11:52,500 >> De látni fogod azt idővel, különösen a jövőbeli probléma határozza sőt 318 00:11:52,500 --> 00:11:55,600 utolsó projektekre az adatok set lesz nagy, rendben? 319 00:11:55,600 --> 00:11:58,300 Még az első verzió a Facebook, mint a barátok száma, és a 320 00:11:58,300 --> 00:12:01,840 A regisztrált felhasználó van a nagy, akkor valami telefon is és 321 00:12:01,840 --> 00:12:05,530 végre valami lineáris keresés vagy egy nagyon egyszerű válogatás 322 00:12:05,530 --> 00:12:07,030 algoritmus, mint látni fogjuk ma. 323 00:12:07,030 --> 00:12:09,280 Meg kell kezdeni gondolkodni nehezebb és nehezebb ezekről a problémákról. 324 00:12:09,280 --> 00:12:12,070 És a típusú problémák olyan helyeken, mint Facebook, és a Google és a Microsoft, 325 00:12:12,070 --> 00:12:16,350 és mások dolgoznak éppen ezek valami nagy adat fajta kérdések 326 00:12:16,350 --> 00:12:18,530 inkább ezekben a napokban. 327 00:12:18,530 --> 00:12:18,900 >> Rendben van. 328 00:12:18,900 --> 00:12:23,800 Tehát Jennifer sikere, hogy a második algoritmus, őszintén szólva, ő volt meglepően 329 00:12:23,800 --> 00:12:26,110 Nos az első alkalom, de most írd a szerencse, hogy mi 330 00:12:26,110 --> 00:12:27,000 is, hogy ezen a ponton. 331 00:12:27,000 --> 00:12:30,970 A második esetben, ő egy tőkeáttételes algoritmus újra és 332 00:12:30,970 --> 00:12:34,670 újra, de ő vette biztosra a bizonyos feltételezés, hogy lehetővé tette 333 00:12:34,670 --> 00:12:39,370 , de ő kihasznált néhány részlet a másodszor, hogy ő nem volt a 334 00:12:39,370 --> 00:12:39,840 első alkalommal. 335 00:12:39,840 --> 00:12:41,800 Mi volt az? 336 00:12:41,800 --> 00:12:43,050 >> Ez a lista sorrendje. 337 00:12:43,050 --> 00:12:46,350 Tehát amint a lista rendezve, mi azt állítják, hogy Jennifer volt képes 338 00:12:46,350 --> 00:12:47,480 alapvetően jobb. 339 00:12:47,480 --> 00:12:51,450 7 ajtók, igen, nem olyan érdekes, de hiszem, mi vagyunk 7000000 ajtók. 340 00:12:51,450 --> 00:12:54,080 Log n határozottan fog elvégzésére sokkal, de sokkal 341 00:12:54,080 --> 00:12:55,610 gyorsabb hosszú távon. 342 00:12:55,610 --> 00:12:58,880 De volt, hogy a ajtók sorrendje neki. 343 00:12:58,880 --> 00:13:02,320 Most vettem a bátorságot, és csinálja előre a számítógép képernyőjén 344 00:13:02,320 --> 00:13:05,160 itt, de tegyük fel, hogy Jennifer kellett tennem, hogy maga? 345 00:13:05,160 --> 00:13:10,120 Tegyük fel, hogy az ajtók a kérdéses képviselte az adatokat egy adatbázisban, vagy 346 00:13:10,120 --> 00:13:14,260 barátok regisztrált a Facebook, vagy a olyan weboldalak az interneten, 347 00:13:14,260 --> 00:13:16,880 különböző honlapokon szüksége lehet az index vagy a keresést. 348 00:13:16,880 --> 00:13:20,940 >> Tegyük fel, hogy most volt a nyers adatok meg, és maradt meg, illetve a 349 00:13:20,940 --> 00:13:23,010 Jennifer a teendő, hogy a válogatás? 350 00:13:23,010 --> 00:13:26,950 Ez inkább megköveteli, hogy választ az a kérdés, nos, mennyi időt 351 00:13:26,950 --> 00:13:31,080 volna Jennifer, vagy akár én, rendezni ezeket a számokat előre, 352 00:13:31,080 --> 00:13:32,680 hogy ő is kihasználni ezt? 353 00:13:32,680 --> 00:13:32,880 Nem igaz? 354 00:13:32,880 --> 00:13:36,620 Mivel a hatása, természetesen, ha elvisz egy darabig, hogy rendezni 355 00:13:36,620 --> 00:13:40,800 A számok, ki a fene törődik, hogy Megtalálható számos hasonló 50 olyan gyorsan, 356 00:13:40,800 --> 00:13:44,850 mint Jennifer esetében, ha több mint túlterheltek az összeg a teljes idő 357 00:13:44,850 --> 00:13:46,920 ez volt a válogatás a dolgokat előre? 358 00:13:46,920 --> 00:13:49,320 >> Tehát lássuk, ha nem tudjuk a festeni a képet. 359 00:13:49,320 --> 00:13:51,370 Van egy csomó nagyobb hangsúlyt golyók, ha ez segít 360 00:13:51,370 --> 00:13:52,270 megtöri a jeget itt. 361 00:13:52,270 --> 00:13:55,690 És ha nem bánja, akkor kell hét önkéntes - 362 00:13:55,690 --> 00:13:57,060 az, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Tehát nem kell költeni az asztali lámpa, úgy tűnik. 365 00:13:59,250 --> 00:13:59,690 Rendben van. 366 00:13:59,690 --> 00:14:01,530 Szóval, mi lenne, ha kettő elöl. 367 00:14:01,530 --> 00:14:04,160 Mi lenne, ha két srác vissza. 368 00:14:04,160 --> 00:14:04,870 Szóval ez a négy. 369 00:14:04,870 --> 00:14:09,890 Mi lenne, ha előtte öt, hat és hét. 370 00:14:09,890 --> 00:14:10,320 Ott. 371 00:14:10,320 --> 00:14:13,260 Ismerőse mutat ki, így kap a díjat. 372 00:14:13,260 --> 00:14:13,700 >> Rendben van. 373 00:14:13,700 --> 00:14:14,410 Gyere fel. 374 00:14:14,410 --> 00:14:17,120 És miért nem voltál srácok gyere ide. 375 00:14:17,120 --> 00:14:18,960 Meg fogom adni egy-egy számot. 376 00:14:18,960 --> 00:14:22,150 És megy előre, és intézkedik magatokat azonos a mi 377 00:14:22,150 --> 00:14:25,180 látható a képernyőn. 378 00:14:25,180 --> 00:14:26,530 >> [Közbeiktatásával VOICES] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Hopp, bocsi. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Rendben van. 382 00:14:32,180 --> 00:14:32,750 Nos, itt vagyunk. 383 00:14:32,750 --> 00:14:34,180 Az ötödik. 384 00:14:34,180 --> 00:14:35,136 Hatos. 385 00:14:35,136 --> 00:14:37,770 Egy, kettő, három, négy, öt, hat, hét. 386 00:14:37,770 --> 00:14:39,410 Ó, ez kínos. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: én csak kap egy -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: jó üzlet. 389 00:14:41,900 --> 00:14:43,130 Rendben van. 390 00:14:43,130 --> 00:14:44,611 Köszönjük, hogy részt. 391 00:14:44,611 --> 00:14:47,200 >> [Taps] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Rendben van. 394 00:14:48,860 --> 00:14:51,970 Tehát négy, kettő, hat, egy, három, hét, öt. 395 00:14:51,970 --> 00:14:56,010 Tökéletes, így már hét önkéntesek itt, akik egyenlő szélessége a 396 00:14:56,010 --> 00:14:57,430 tömb játszunk a korábbi. 397 00:14:57,430 --> 00:14:59,470 És én választottam hét okokból hogy lesz csak 398 00:14:59,470 --> 00:15:00,840 kényelmes egy kicsit. 399 00:15:00,840 --> 00:15:04,400 És én fogom javasolni, hogy az első mi rendezni a hét önkéntesek. 400 00:15:04,400 --> 00:15:06,786 Ha szeretné, az első, köszönni mégis. 401 00:15:06,786 --> 00:15:08,970 Mivel ez lesz az kínos néhány percig. 402 00:15:08,970 --> 00:15:10,370 Tegyünk magatokat. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Szia, én vagyok Grace. 404 00:15:10,980 --> 00:15:14,190 Vagyok másodéves Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Szia. 406 00:15:14,620 --> 00:15:15,620 Én Branson. 407 00:15:15,620 --> 00:15:16,920 Én egy újonc a Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Szia. 410 00:15:20,230 --> 00:15:21,040 Én Gabe. 411 00:15:21,040 --> 00:15:22,300 Én vagyok a junior Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Én vagyok Neil. 414 00:15:25,980 --> 00:15:29,090 Én egy újonc a Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Én vagyok Jason. 416 00:15:29,550 --> 00:15:32,816 Én egy újonc a Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Én vagyok Mike. 418 00:15:33,700 --> 00:15:37,360 Én egy újonc a Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Én vagyok Jess. 420 00:15:37,990 --> 00:15:40,313 Vagyok másodéves Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excellent. 422 00:15:41,300 --> 00:15:41,850 Rendben van. 423 00:15:41,850 --> 00:15:44,190 Nos, köszönöm, hogy minden a mi önkéntesek itt eddig. 424 00:15:44,190 --> 00:15:47,110 És a kihívás kéznél most folyik hogy rendezni ezek a srácok, de aztán 425 00:15:47,110 --> 00:15:50,250 mi lesz, hogy szerintem egy kicsit kemény, hogyan hatékonyan valójában 426 00:15:50,250 --> 00:15:51,110 rendezve őket. 427 00:15:51,110 --> 00:15:52,580 Szóval először próbálja meg ezt. 428 00:15:52,580 --> 00:15:55,970 Ti Láthatjuk egymás számok csak azáltal körül a sarkokban. 429 00:15:55,970 --> 00:15:59,380 Menj előre, és néhány másodpercig, és a sort magatokat legkisebb a 430 00:15:59,380 --> 00:16:01,240 balra legnagyobb a jobb oldalon. 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 Jó. 435 00:16:08,030 --> 00:16:09,370 Ez tényleg rohadt gyorsan. 436 00:16:09,370 --> 00:16:14,040 Most itt valaki, mi volt az algoritmus hogy ezek a srácok alkalmazni? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: legkevésbé a legnagyobb. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Legalábbis legnagyobb valóban rendezni a cél, de nem vagyok benne biztos, hogy ez 440 00:16:18,070 --> 00:16:18,890 tényleg egy algoritmus. 441 00:16:18,890 --> 00:16:21,810 Legalábbis legnagyobb nem mondja nekem lépésről-lépésre, hogy mit kell tennie. 442 00:16:21,810 --> 00:16:22,833 Igen? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [hangtalan] 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 Tehát, ha egy embernek kisebb a számot, majd lépjen 447 00:16:28,920 --> 00:16:29,680 a jobb közülük. 448 00:16:29,680 --> 00:16:32,800 Szóval ez már egyre kifejezőbb, több, mint egy algoritmus, mert 449 00:16:32,800 --> 00:16:35,410 lehet mondani, ha ez, akkor azt. 450 00:16:35,410 --> 00:16:37,050 Tehát valamilyen feltételes konstrukció. 451 00:16:37,050 --> 00:16:39,700 És ezek a srácok úgy tűnt, hogy ezt, hogy néhány alkalommal, mert néhányan át egy kicsit 452 00:16:39,700 --> 00:16:40,420 a távolság. 453 00:16:40,420 --> 00:16:43,410 Tehát feltehetően valamilyen hurok folyik a fejükben. 454 00:16:43,410 --> 00:16:44,610 >> De próbáljuk meg, hogy hivatalossá. 455 00:16:44,610 --> 00:16:47,540 Ha ti is visszaáll hogy ez a megállapodás. 456 00:16:47,540 --> 00:16:50,650 Lássuk, ha nem ezt a hivatalossá bit, majd fel a kérdést, csak 457 00:16:50,650 --> 00:16:51,580 mennyire hatékony ez? 458 00:16:51,580 --> 00:16:54,220 Természetesen, ha ezt lassabban, ez meg fog érezni, jó 459 00:16:54,220 --> 00:16:57,210 egy algoritmus, de lássuk, ha tudjuk fel ujjainkat a pontos lépéseket. 460 00:16:57,210 --> 00:16:58,670 >> Szóval két srác négy és két. 461 00:16:58,670 --> 00:17:01,020 Vagy helyes vagy helytelen-e? 462 00:17:01,020 --> 00:17:01,900 Nyilvánvalóan helytelen. 463 00:17:01,900 --> 00:17:02,710 Így cserélték. 464 00:17:02,710 --> 00:17:05,170 Most fogok félre itt, és azt mondják, 4-6. 465 00:17:05,170 --> 00:17:06,240 Ön a helyes vagy helytelen? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Helyes. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Helyes. 468 00:17:07,180 --> 00:17:08,300 Hat, egy? 469 00:17:08,300 --> 00:17:08,609 Nem. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Szóval ez két swap. 472 00:17:10,490 --> 00:17:11,710 Hat és három? 473 00:17:11,710 --> 00:17:11,980 Nem. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Hat és hét? 476 00:17:13,930 --> 00:17:14,630 Jól néz ki. 477 00:17:14,630 --> 00:17:15,396 Hét és öt? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [hangtalan] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, csere. 480 00:17:17,089 --> 00:17:19,770 És rendezett. 481 00:17:19,770 --> 00:17:19,980 Rendben van. 482 00:17:19,980 --> 00:17:21,440 Tehát nyilvánvalóan nem igaz? 483 00:17:21,440 --> 00:17:22,470 Így nem volt még folyik. 484 00:17:22,470 --> 00:17:24,920 De, sőt, ezek a fiúk, még csak ösztönösen. 485 00:17:24,920 --> 00:17:25,450 mozgott. 486 00:17:25,450 --> 00:17:27,710 Nem csak megáll, amint javított egy probléma. 487 00:17:27,710 --> 00:17:27,839 Így. 488 00:17:27,839 --> 00:17:29,390 Sőt, megyek, hogy hogy nem ugyanaz a dolog. 489 00:17:29,390 --> 00:17:32,720 Megyek kell rendezni a visszatekerés vissza az elején ezt a problémát, 490 00:17:32,720 --> 00:17:35,630 vagy az elején ez a tömb emberek, kezdjük nevezve őket. 491 00:17:35,630 --> 00:17:38,366 >> És most mit kell az algoritmus A második lépésben az? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Ugyanaz. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Ugyanaz. 494 00:17:39,940 --> 00:17:41,460 És ez, kezdek tetszik, ugye? 495 00:17:41,460 --> 00:17:44,720 Amint megtalálja magát csinál ugyanaz a dolog, újra és újra, hogy ez 496 00:17:44,720 --> 00:17:47,890 egyre inkább, mint egy algoritmus, és kevésbé az emberi ösztön. 497 00:17:47,890 --> 00:17:48,680 >> Tehát most, itt vagyunk megint. 498 00:17:48,680 --> 00:17:49,870 Kettő és négy? 499 00:17:49,870 --> 00:17:50,220 Nem. 500 00:17:50,220 --> 00:17:51,050 Négy és egy? 501 00:17:51,050 --> 00:17:53,380 Ah, ott valóban valami munka még hátra. 502 00:17:53,380 --> 00:17:53,620 A, három? 503 00:17:53,620 --> 00:17:54,572 Jó. 504 00:17:54,572 --> 00:17:56,000 Négy és hat? 505 00:17:56,000 --> 00:17:58,380 Hat, öt? 506 00:17:58,380 --> 00:17:59,470 Hat és hét? 507 00:17:59,470 --> 00:18:00,970 OK, most kész. 508 00:18:00,970 --> 00:18:01,550 OK, nem. 509 00:18:01,550 --> 00:18:02,710 Mennem kell vissza. 510 00:18:02,710 --> 00:18:05,130 >> Tehát most megint ezt csináljuk egy kicsit szándékosan. 511 00:18:05,130 --> 00:18:08,700 És most már csak egy agy végrehajtása az algoritmus. 512 00:18:08,700 --> 00:18:10,290 Egy CPU, ha úgy tetszik. 513 00:18:10,290 --> 00:18:13,090 És őszintén szólva, ez az egyetlen forrás, mi lesz, hogy hozzáférjenek. 514 00:18:13,090 --> 00:18:16,280 És ha már nem megy vissza a billentyűzet és van valami, mint a C-on a 515 00:18:16,280 --> 00:18:19,600 rendelkezésére, mi csak írni egy programot , amely egy dolgot egy időben. 516 00:18:19,600 --> 00:18:22,900 Mivel ezek a srácok egy kicsit ezelőtt, tőkeáttételes kollektív agyak 517 00:18:22,900 --> 00:18:24,180 mint ti tette hét nulla. 518 00:18:24,180 --> 00:18:24,980 Szóval csinálom ezt. 519 00:18:24,980 --> 00:18:26,260 >> Kettő és egy. 520 00:18:26,260 --> 00:18:26,945 Kettő, három. 521 00:18:26,945 --> 00:18:27,460 Három, négy. 522 00:18:27,460 --> 00:18:28,310 Négy és öt. 523 00:18:28,310 --> 00:18:28,620 Öt és hat. 524 00:18:28,620 --> 00:18:30,510 Hat és hét. 525 00:18:30,510 --> 00:18:31,880 Kész? 526 00:18:31,880 --> 00:18:34,560 Tehát én vagyok, de hadd játsszon ördög ügyvédje. 527 00:18:34,560 --> 00:18:37,950 Tudom, az a fajta, aki csak számítógép kikezdett ezen keresztül tömb 528 00:18:37,950 --> 00:18:40,225 ember, tudja, hogy kész vagyok? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Nem. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Miért? 531 00:18:41,050 --> 00:18:46,900 Mit kell tennem annak érdekében, hogy következtetni, döntően, hogy én tettem? 532 00:18:46,900 --> 00:18:48,230 Talán még egy menetben. 533 00:18:48,230 --> 00:18:48,430 Nem igaz? 534 00:18:48,430 --> 00:18:51,760 Mert minden, amit tudok az, hogy a korábbi át, hogy én javított hiba. 535 00:18:51,760 --> 00:18:53,920 És ez azt jelenti, lehet, hogy van még egy hiba 536 00:18:53,920 --> 00:18:54,840 amit ki kell javítani. 537 00:18:54,840 --> 00:18:58,680 Szóval csak biztos a felhúzás, és majd ellenőrzi, 1-2, két-és 538 00:18:58,680 --> 00:19:00,940 három, három és négy, négy és öt, Öt, hat, hat és hét. 539 00:19:00,940 --> 00:19:02,510 OK, most már nem dolgozott. 540 00:19:02,510 --> 00:19:05,990 >> Én biztosan emlékszem, hogy nem tett dolgozni valami, mint egy változó, 541 00:19:05,990 --> 00:19:06,975 mint egy int. 542 00:19:06,975 --> 00:19:12,490 Nevezzük swap, és ha a swapok 0 egyszer ide, és kezdődött a 0, akkor 543 00:19:12,490 --> 00:19:15,520 Én csak hülye, hogy tartani fog oda-vissza, ellenőrzés ismét, és 544 00:19:15,520 --> 00:19:16,450 újra, és újra, igaz? 545 00:19:16,450 --> 00:19:18,450 Mert elakad néhány ilyen végtelen ciklusba. 546 00:19:18,450 --> 00:19:21,250 Tehát amint ott 0 swap, azt állítják, hogy ez a 547 00:19:21,250 --> 00:19:23,810 algoritmus valóban befejeződött. 548 00:19:23,810 --> 00:19:25,400 >> Nos, mondjuk a nevemet. 549 00:19:25,400 --> 00:19:28,930 Az algoritmus, hogy azt javaslom, mi csak végre az úgynevezett buborék 550 00:19:28,930 --> 00:19:32,800 sort, az úgynevezett így abban az értelemben, hogy a a számok, melyek nagyobb fajta 551 00:19:32,800 --> 00:19:37,990 buborék az utat felfelé a csúcsra, vagy akár hogy a végén a tömb a számok. 552 00:19:37,990 --> 00:19:40,270 De milyen hatékony volt ez az algoritmus? 553 00:19:40,270 --> 00:19:44,600 Hány lépést tettem fizikailag kell Vegyük például, hogy rendezni ezeket a 554 00:19:44,600 --> 00:19:45,850 hét ember? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Négy-öt? 557 00:19:49,550 --> 00:19:51,420 OK, túl sok végső soron lesz a válasz. 558 00:19:51,420 --> 00:19:54,960 De még akkor is, az adott szám nem olyan érdekes. 559 00:19:54,960 --> 00:19:56,670 Nézzük általánosítani, mint n. 560 00:19:56,670 --> 00:20:00,520 Tehát, ha én n ember van itt, és volt, valami, véletlenszerű sorrendben, a 561 00:20:00,520 --> 00:20:02,180 elején, az, hogy az eredeti sorrendben. 562 00:20:02,180 --> 00:20:04,910 Nos, hány lépést tettem meg hogy az első lépésben? 563 00:20:04,910 --> 00:20:09,810 Ez volt egy, kettő, három, négy, öt, hat, és ők hét ember, így 564 00:20:09,810 --> 00:20:13,670 ez hét, hat -, hogy az n mínusz egy lépést az első alkalommal. 565 00:20:13,670 --> 00:20:16,280 >> Most, hogy hány lépést tettem meg hogy mikor Visszatekertem? 566 00:20:16,280 --> 00:20:19,310 Nos, mi is valójában kétszer, hogy ha akartunk, de most én vagyok 567 00:20:19,310 --> 00:20:22,300 csak mondani, rendben, másik n mínusz 1. 568 00:20:22,300 --> 00:20:25,240 Tehát az n mínusz 1 fog kapni bosszantó, hogy nyomon követni, úgyhogy 569 00:20:25,240 --> 00:20:26,400 csak felhajt kicsit. 570 00:20:26,400 --> 00:20:27,770 Tehát 2n lépéseket. 571 00:20:27,770 --> 00:20:29,310 Tehát 14 lépésben, ide vagy oda. 572 00:20:29,310 --> 00:20:31,930 >> Hányszor veszek egy lépés a következő alkalommal? 573 00:20:31,930 --> 00:20:33,740 Nos, ez 3n. 574 00:20:33,740 --> 00:20:34,510 igazán. 575 00:20:34,510 --> 00:20:37,920 És most, a legrosszabb esetben, a Például, hányszor kellene már 576 00:20:37,920 --> 00:20:41,730 ment oda-vissza, oda-vissza, végrehajtása az algoritmus, csere 577 00:20:41,730 --> 00:20:44,620 emberek minden lépésben, durván? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Ez tulajdonképpen n négyzeten, igaz? 580 00:20:50,010 --> 00:20:53,000 >> Mivel a legrosszabb esetben, akkor milyen Az gondolni ezt ösztönösen, 581 00:20:53,000 --> 00:20:54,800 annak ellenére, hogy lehet, hogy egy kicsit kis idő süllyedni be 582 00:20:54,800 --> 00:20:57,590 A legrosszabb esetben, mi lenne ezek a hét ember nézett ki, mint a 583 00:20:57,590 --> 00:21:00,230 tekintetében a megállapodás a számok? 584 00:21:00,230 --> 00:21:01,460 Teljesen hátra, igaz? 585 00:21:01,460 --> 00:21:02,815 És csak, hogy szimulálja, hogy a mi volt a neve? 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, csak velem át Itt csak egy pillanatra? 589 00:21:08,100 --> 00:21:08,880 Igazából nem. 590 00:21:08,880 --> 00:21:10,150 Sajnálom Mike, hadd visszatekerés. 591 00:21:10,150 --> 00:21:10,910 Mi a neved? 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, jössz nekem, ha nem bánod. 595 00:21:13,750 --> 00:21:17,150 Így fogom javasolni, csak egyszerűség, hogy Neil most az ő 596 00:21:17,150 --> 00:21:18,510 legrosszabb esetben. 597 00:21:18,510 --> 00:21:20,720 De emlékszem, hogy azt végre az algoritmus. 598 00:21:20,720 --> 00:21:24,530 Én összehasonlítása, összehasonlítása, összehasonlítása, összehasonlítása, összehasonlítása, oh. 599 00:21:24,530 --> 00:21:26,640 Most ezek a srácok ki a rend, így javítani. 600 00:21:26,640 --> 00:21:27,980 Szóval srácok cserélni. 601 00:21:27,980 --> 00:21:31,630 De gondolja most, hogy sokkal messzebb nem Neil kell menni? 602 00:21:31,630 --> 00:21:32,690 Ez nagyjából n. 603 00:21:32,690 --> 00:21:33,570 Tudod, ez valójában nem n. 604 00:21:33,570 --> 00:21:36,040 Ez olyan, mint, n mínusz 1, de kapok bosszús nyomon követése a kis 605 00:21:36,040 --> 00:21:37,550 szám, úgyhogy csak ez n. 606 00:21:37,550 --> 00:21:42,860 >> Tehát, ha Neil egy lépéssel tovább megy maximálisan minden időt, és hogy mozog egy lépéssel Neil, 607 00:21:42,860 --> 00:21:46,580 Azt kell, hogy ez tényleg unalmas át oda-vissza, ez nagyjából 608 00:21:46,580 --> 00:21:52,080 ezt, N lépésben, összesen N-szer, mert ez fog vinni 609 00:21:52,080 --> 00:21:55,820 hogy sok lépés, hogy Neil minden a módja annak, hogy ahová tartozik. 610 00:21:55,820 --> 00:21:58,620 Nemhogy mindenki más, ha ti mind rosszul rendelhető. 611 00:21:58,620 --> 00:22:01,100 >> Így nevezzük buborék sort n négyzeten. 612 00:22:01,100 --> 00:22:04,860 A futási ideje ez az algoritmus, a teljesítmény ez az algoritmus, a 613 00:22:04,860 --> 00:22:07,120 hatékonyságát ez az algoritmus, fogjuk csak le több 614 00:22:07,120 --> 00:22:08,800 általánosságban N négyzeten. 615 00:22:08,800 --> 00:22:11,650 Ami szép és jó, mert én is ezt a ugyanaz például nyolc ember, kilenc 616 00:22:11,650 --> 00:22:15,450 emberek, egy millió ember, és hogy a válasz nem fog megváltozni. 617 00:22:15,450 --> 00:22:18,870 >> Tehát, ha ti nem bánja, most vissza, hogy hol kezdődött. 618 00:22:18,870 --> 00:22:22,510 És próbáljuk két másik megközelítés és hátha nem alapvetően 619 00:22:22,510 --> 00:22:23,820 jobb, mint ez. 620 00:22:23,820 --> 00:22:27,130 Ez alkalommal, fogom javasolni egyfajta másik algoritmust. 621 00:22:27,130 --> 00:22:29,950 Ez nagyon okos volt velünk utoljára, és ti igaza volt, hogy a 622 00:22:29,950 --> 00:22:32,470 jobb ösztönei csak ilyen A csere páronként. 623 00:22:32,470 --> 00:22:36,500 De ha igazán akartam megközelíteni ezt egyszerűen, és a cél az, hogy 624 00:22:36,500 --> 00:22:39,800 mind a kis számok így, és nyomja minden a nagy számok 625 00:22:39,800 --> 00:22:43,030 út, miért nem csak csinálni, hogy a legtöbb naiv módja lehetséges, és ha én 626 00:22:43,030 --> 00:22:45,730 nem jobb, mint ami a meglehetősen összetett algoritmus? 627 00:22:45,730 --> 00:22:46,620 >> Tehát lássuk csak. 628 00:22:46,620 --> 00:22:48,940 Négy egy nagyon kevés, úgyhogy fogja hagyni ott pillanatban. 629 00:22:48,940 --> 00:22:50,610 Ó, a második még jobb. 630 00:22:50,610 --> 00:22:52,230 Így tud csak lépés előre egy pillanatra? 631 00:22:52,230 --> 00:22:55,670 Ez jelenleg a legkisebb sorszámú jelölt, és fogok emlékezni 632 00:22:55,670 --> 00:22:57,000 hogy az, mint egy változó. 633 00:22:57,000 --> 00:22:57,930 De én, hogy nézz. 634 00:22:57,930 --> 00:22:59,890 Van valaki, akinek szám kisebb? 635 00:22:59,890 --> 00:23:00,460 Hat, nem. 636 00:23:00,460 --> 00:23:01,390 Ó, ott van Neil megint. 637 00:23:01,390 --> 00:23:04,050 >> Úgyhogy, hogy álljon vissza fajta fogalmilag. 638 00:23:04,050 --> 00:23:05,120 Neil fog előterjeszteni. 639 00:23:05,120 --> 00:23:08,440 És most, a változó, hogy én vagyok használ nyomon követni, hogy ki van a legkisebb 640 00:23:08,440 --> 00:23:11,390 szám frissítve tartalmaz Neil helyét. 641 00:23:11,390 --> 00:23:12,110 Nos, lássuk csak. 642 00:23:12,110 --> 00:23:13,960 Három hét, öt. 643 00:23:13,960 --> 00:23:15,590 OK, tudom, hogy Neil volt a legkisebb. 644 00:23:15,590 --> 00:23:18,110 Mi a legegyszerűbb dolog , mit tegyek most? 645 00:23:18,110 --> 00:23:21,410 Nem fogom vesztegetni az időt, csak fortyogó Neil egy helyen balra. 646 00:23:21,410 --> 00:23:25,350 Miért nem csak fel Neil ahol tartozik, ami persze hol? 647 00:23:25,350 --> 00:23:26,160 >> Egészen az elején. 648 00:23:26,160 --> 00:23:27,720 Tehát Neil, gyere velem. 649 00:23:27,720 --> 00:23:28,910 És mi volt a neve? 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 Tehát Grace, sajnos, akkor ilyen az úton. 654 00:23:32,490 --> 00:23:34,290 Szóval hogyan lehet megoldani ezt a problémát? 655 00:23:34,290 --> 00:23:34,490 Nem igaz? 656 00:23:34,490 --> 00:23:37,500 Ha ez egy tömb, van csak hét helyszínen. 657 00:23:37,500 --> 00:23:40,830 Emlékezzünk, hogy a Rob, beszélgettünk kijelentette korosztály, és csak volt egy 658 00:23:40,830 --> 00:23:41,740 véges számú korosztály? 659 00:23:41,740 --> 00:23:42,535 Ugyanaz ötlet. 660 00:23:42,535 --> 00:23:44,300 Már csak véges számú ints. 661 00:23:44,300 --> 00:23:47,590 Grace a fajta a mi módon, így hogyan lehet megjavítani? 662 00:23:47,590 --> 00:23:49,555 >> A legegyszerűbb módja, mint a, Grace, sajnálom. 663 00:23:49,555 --> 00:23:51,870 Te kell majd menjen át ott így tudjuk, hogy szobát. 664 00:23:51,870 --> 00:23:55,290 Nos, ha úgy gondolja, erről, talán Csak tette a probléma rosszabb. 665 00:23:55,290 --> 00:23:58,510 És talán nem, mert mi van, ha Grace volt a jó helyen? 666 00:23:58,510 --> 00:24:01,730 De tudjuk, hogy ő nem, mert a egyébként, ő lett volna 667 00:24:01,730 --> 00:24:03,980 álló előre helyett Neil ebben az időben, nem igaz? 668 00:24:03,980 --> 00:24:05,550 Már ellenőrizte a számot ki. 669 00:24:05,550 --> 00:24:05,770 >> Rendben van. 670 00:24:05,770 --> 00:24:09,110 Tehát most, Neil van a megfelelő helyen, és Meg tudom csinálni egy kis optimalizálás. 671 00:24:09,110 --> 00:24:11,740 A következő pillanatban, fogom figyelmen kívül hagyni Neil együtt, úgy, hogy ne 672 00:24:11,740 --> 00:24:15,280 vesztegette az idejét, vagy véletlenül csere, hogy a rossz helyen. 673 00:24:15,280 --> 00:24:17,805 Tehát most, hogy tudom megtalálni a következő elem legkisebb? 674 00:24:17,805 --> 00:24:18,480 Kettő. 675 00:24:18,480 --> 00:24:20,225 Ez egy nagyon jó szám, ha szeretnénk előre lépni, és 676 00:24:20,225 --> 00:24:21,100 Én emlékszem rád. 677 00:24:21,100 --> 00:24:21,980 Hat, nem jó. 678 00:24:21,980 --> 00:24:24,820 Négy, három, hét, öt, nem jó. 679 00:24:24,820 --> 00:24:26,800 Hadd mozog, hogy A megfelelő helyre. 680 00:24:26,800 --> 00:24:28,470 És csak most szerencsés ebben az időben. 681 00:24:28,470 --> 00:24:31,350 >> Most fogom figyelmen kívül hagyni ezeket két srác, és most még egyet 682 00:24:31,350 --> 00:24:32,260 áthaladnak ezen. 683 00:24:32,260 --> 00:24:33,490 Hat, hogy egy szép kis szám. 684 00:24:33,490 --> 00:24:34,300 Gyerünk előre. 685 00:24:34,300 --> 00:24:35,220 Ó, sajnálom. 686 00:24:35,220 --> 00:24:37,640 Grace szám jobb, így lépjen előre. 687 00:24:37,640 --> 00:24:38,260 Négy. 688 00:24:38,260 --> 00:24:39,120 Sajnálom, Grace. 689 00:24:39,120 --> 00:24:39,950 Menj vissza. 690 00:24:39,950 --> 00:24:41,550 Száma három jobb. 691 00:24:41,550 --> 00:24:42,290 Hét. 692 00:24:42,290 --> 00:24:42,720 Öt. 693 00:24:42,720 --> 00:24:43,550 És most mi is a neved? 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 Tehát Jason most a legkisebb elem, amit választott. 697 00:24:47,050 --> 00:24:49,160 Hova megy, hogy megy? 698 00:24:49,160 --> 00:24:50,380 Szóval hol hatos. 699 00:24:50,380 --> 00:24:51,210 És a név ismét? 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 az úton. 703 00:24:53,220 --> 00:24:54,640 Mi a legegyszerűbb dolog? 704 00:24:54,640 --> 00:24:58,390 Swap ez a két fickó, és folytassa. 705 00:24:58,390 --> 00:24:59,020 Tehát most lássuk. 706 00:24:59,020 --> 00:25:00,170 Ki az a legkisebb? 707 00:25:00,170 --> 00:25:01,030 Négy. 708 00:25:01,030 --> 00:25:01,990 Hadd ilyen cheat. 709 00:25:01,990 --> 00:25:03,090 Öt lesz a legkisebb. 710 00:25:03,090 --> 00:25:05,220 Találom a következő, ha azt szeretnénk, hogy lépést előre, mit kell csinálni 711 00:25:05,220 --> 00:25:06,820 ezek a srácok, és Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap újra. 713 00:25:08,450 --> 00:25:10,740 Tehát most, még mindig kicsit elromlott. 714 00:25:10,740 --> 00:25:14,140 Én találtam Gabe, hogy a legkisebb, így Én pop őt vigye srácok vége. 715 00:25:14,140 --> 00:25:15,190 És kész. 716 00:25:15,190 --> 00:25:17,200 >> Tehát válasz ugyanaz. 717 00:25:17,200 --> 00:25:18,600 A végeredmény ugyanaz. 718 00:25:18,600 --> 00:25:22,730 Melyik két algoritmus a jobb? 719 00:25:22,730 --> 00:25:23,500 A második, hallottam. 720 00:25:23,500 --> 00:25:24,252 Miért? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Ez N lépésben [hallható]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Ez n lépés a legtöbb. 723 00:25:27,600 --> 00:25:28,490 Érdekes. 724 00:25:28,490 --> 00:25:30,610 Szóval, hogy mégis? 725 00:25:30,610 --> 00:25:33,630 Szóval hogyan találom meg a legkisebb elem? 726 00:25:33,630 --> 00:25:37,060 Hány lépést kellett nekem, hogy az megtalálja a legkisebb elem? 727 00:25:37,060 --> 00:25:39,220 Megnéztem végig a végén, nem igaz? 728 00:25:39,220 --> 00:25:41,530 Mert hogy a legrosszabb esetben, milyen ha Neil volt itt? 729 00:25:41,530 --> 00:25:45,700 Tehát csak megtalálni a legkisebb elem elvisz n lépéseket, vagy n mínusz 1. 730 00:25:45,700 --> 00:25:46,100 De, OK. 731 00:25:46,100 --> 00:25:46,980 Így fix Neil. 732 00:25:46,980 --> 00:25:48,740 Ne feledje, hogy egy perc múlva óra. 733 00:25:48,740 --> 00:25:51,680 >> De hogyan találom meg a következő legkisebb elem? 734 00:25:51,680 --> 00:25:54,830 Ez n mínusz 1 vagy mínusz 2 n igazán, a lépések számát. 735 00:25:54,830 --> 00:25:55,440 Így az OK gombra. 736 00:25:55,440 --> 00:25:57,390 Úgyhogy n mínusz 2. 737 00:25:57,390 --> 00:25:57,600 Rendben van. 738 00:25:57,600 --> 00:25:59,130 Annak érdekében, hogy úgy érzi, egy kicsit jobban. 739 00:25:59,130 --> 00:25:59,730 Rendben van. 740 00:25:59,730 --> 00:26:03,270 Hány lépést a következő alkalommal találni a harmadik? 741 00:26:03,270 --> 00:26:04,420 Tehát n mínusz 4. 742 00:26:04,420 --> 00:26:07,670 Szóval ez csökken, eggyel kevesebb lépést minden iteráció. 743 00:26:07,670 --> 00:26:08,740 Tehát ez jobban érzi magát, nem igaz? 744 00:26:08,740 --> 00:26:13,450 Ha utóbbi időben ez volt nagyjából n-szer n ezúttal n mínusz 1, plusz mínusz n 745 00:26:13,450 --> 00:26:16,500 2, plusz n mínusz 3, és n mínusz 4, pont, pont, pont. 746 00:26:16,500 --> 00:26:18,750 De ha visszahívja a gimnázium tankönyvek, a kis csaló 747 00:26:18,750 --> 00:26:24,380 lapot a hátsó, amely képleteket, ha hozzá ezt a számsort, 748 00:26:24,380 --> 00:26:31,280 mi a lépcsőfokok számát lesz, hogy veszek itt? 749 00:26:31,280 --> 00:26:36,580 >> Ez egyike azoknak, mint, n mínusz 1 alkalommal n, osztva 2-vel. 750 00:26:36,580 --> 00:26:39,040 Hadd hátha tudok húzni ezt fel egy pillanatra. 751 00:26:39,040 --> 00:26:42,230 És ismét, én vagyok ilyen kerekítés bizonyos számok csak hogy életünk egyszerű, 752 00:26:42,230 --> 00:26:47,830 de ha jól emlékszem, ez olyasmi, mint ha Én n mínusz 1 dolog, akkor n mínusz 753 00:26:47,830 --> 00:26:53,570 2, akkor n mínusz 3, ez nagyjából valami ilyesmi több mint 2, és ha 754 00:26:53,570 --> 00:26:55,510 szaporodnak ezt ki, ez valójában N téren. 755 00:26:55,510 --> 00:26:58,940 Ez nem érzi túl jól. n N mínusz több mint 2. 756 00:26:58,940 --> 00:27:00,350 >> De itt van a dolog. 757 00:27:00,350 --> 00:27:03,720 A számítógép-tudomány, amikor a problémák kezd érdekessé válni, amikor n 758 00:27:03,720 --> 00:27:04,700 lesz igazán nagy. 759 00:27:04,700 --> 00:27:08,110 És amikor n lesz igazán nagy, ami a ezeket az értékeket fogja uralni minden 760 00:27:08,110 --> 00:27:09,750 a többiek? 761 00:27:09,750 --> 00:27:10,990 Elég az n négyzetes, igaz? 762 00:27:10,990 --> 00:27:13,340 Igen, elosztjuk a 2 nagyon jó. 763 00:27:13,340 --> 00:27:16,740 De ha beszélünk milliárd A darab az adatok, vagy milliárdjai 764 00:27:16,740 --> 00:27:18,700 darab adat, OK, így te kétszer olyan gyorsan. 765 00:27:18,700 --> 00:27:22,440 De aki igazán érdekel, ha ez a nagy szám, ha ez a tényező az, amit kap 766 00:27:22,440 --> 00:27:23,040 nagyobb és nagyobb. 767 00:27:23,040 --> 00:27:25,990 És biztos, hogy van több a a különbség, mint ez a fickó. 768 00:27:25,990 --> 00:27:29,120 Tehát annak ellenére, Igazatok van, a második algoritmus, hívjuk meg 769 00:27:29,120 --> 00:27:32,970 kiválasztás sort, az, hogy a való világban, a kicsit gyorsabb potenciálisan, mert én vagyok 770 00:27:32,970 --> 00:27:35,360 figyelembe egyre kevesebb lépéseket minden egyes alkalommal. 771 00:27:35,360 --> 00:27:37,340 >> Ez nem igazán alapvetően gyorsabb. 772 00:27:37,340 --> 00:27:41,430 Mert ha tényleg játszani ezt a ki n értéke nagy, a végén 773 00:27:41,430 --> 00:27:44,750 a nap, elég nagy n, még mindig majd úgy érzi, elég lassú. 774 00:27:44,750 --> 00:27:46,770 Nos, hadd vegyen be egy utolsó lépés az, hogy. 775 00:27:46,770 --> 00:27:48,920 Ez az, amit én neveznék kiválasztás sort. 776 00:27:48,920 --> 00:27:51,040 Tudtok vissza magatokat utoljára? 777 00:27:51,040 --> 00:27:53,550 És ebben az utóbbi esetben, megyek javasolni valamit 778 00:27:53,550 --> 00:27:54,970 nevű beszúrás sort. 779 00:27:54,970 --> 00:27:57,470 Beillesztése sort, hogy fogalmilag, egy kicsit más. 780 00:27:57,470 --> 00:28:00,980 >> Ahelyett, hogy megy oda-vissza, és kiválasztja a legkisebb elem, én vagyok 781 00:28:00,980 --> 00:28:05,030 csak fog foglalkozni minden egyes ilyen fiúk, mint én találkozni velük, és helyezze 782 00:28:05,030 --> 00:28:06,850 azokat a megfelelő helyre. 783 00:28:06,850 --> 00:28:10,160 Szóval csak fog kezdeni Grace, és látom, hogy ő a negyedik. 784 00:28:10,160 --> 00:28:11,720 Hol négyes tartozik? 785 00:28:11,720 --> 00:28:14,940 Még nem indult válogatás semmit, így Grace lesz, hogy maradjon ott. 786 00:28:14,940 --> 00:28:18,355 És most fogok igényt, ha lehet egy lépést a helyes, ez a 787 00:28:18,355 --> 00:28:21,650 a rendezett lista, ez az én rendezetlen maradék listát. 788 00:28:21,650 --> 00:28:23,260 Szóval most megyek, hogy folytassa a következő, és mi a neved? 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 Tehát Branson a kettes számú. 792 00:28:25,375 --> 00:28:27,490 Így fogok vinni ki egy pillanatra. 793 00:28:27,490 --> 00:28:30,940 És most, hol tartoznak ebben a tömbben? 794 00:28:30,940 --> 00:28:32,360 Tehát, hogy a jobb Grace. 795 00:28:32,360 --> 00:28:35,670 Tehát újra, mi olyan, hogy Grace sokat dolgoznak itt. 796 00:28:35,670 --> 00:28:37,290 Hol téged? 797 00:28:37,290 --> 00:28:40,120 Így fogunk csúszni, hogy a balra, és helyezze Branson ott. 798 00:28:40,120 --> 00:28:41,680 De most már azt állítják, hogy srácok kész. 799 00:28:41,680 --> 00:28:43,240 De vegyük észre, én nem használ extra helyet. 800 00:28:43,240 --> 00:28:45,130 Még mindig 2 elem Itt, 5. ide. 801 00:28:45,130 --> 00:28:47,910 Total tömb mérete 7, úgyhogy nem csalás, rendben? 802 00:28:47,910 --> 00:28:51,950 >> Tehát most már, és Gabe itt, a hatos, hol tartozol? 803 00:28:51,950 --> 00:28:52,650 Van szerencsém újra. 804 00:28:52,650 --> 00:28:53,820 Szóval, hogy maradjon ott. 805 00:28:53,820 --> 00:28:57,210 Csak egy kis lépés, hogy a megfelelő csak azért, hogy világos, hogy te rendezve. 806 00:28:57,210 --> 00:29:00,520 És most már Neil ismét szám Egy, hová mész? 807 00:29:00,520 --> 00:29:03,540 És most, amikor elkezdjük látni, hogy Az algoritmus, de az első 808 00:29:03,540 --> 00:29:05,950 Dióhéjban, úgy érzi, elég okos, nézni mi fog történni. 809 00:29:05,950 --> 00:29:07,370 Ha lehet előrelépés. 810 00:29:07,370 --> 00:29:09,260 >> Hol akarjuk, hogy Neil? 811 00:29:09,260 --> 00:29:11,830 Tehát nyilvánvaló itt, akkor hogyan jutunk Neil oda? 812 00:29:11,830 --> 00:29:12,970 Csináljuk lépésről-lépésre. 813 00:29:12,970 --> 00:29:15,620 Gabe, hol kell menni? 814 00:29:15,620 --> 00:29:19,590 Igen, így, hogy egy nagy lépést, vagy két fél lépéseket, hogy 815 00:29:19,590 --> 00:29:20,820 egy lépéssel ott. 816 00:29:20,820 --> 00:29:21,750 Grace, hová mész? 817 00:29:21,750 --> 00:29:22,510 Jó. 818 00:29:22,510 --> 00:29:23,500 Tehát még egy lépést. 819 00:29:23,500 --> 00:29:24,960 És végül, Branson? 820 00:29:24,960 --> 00:29:25,460 Újabb lépés. 821 00:29:25,460 --> 00:29:27,190 És most is fel Neil helyére. 822 00:29:27,190 --> 00:29:28,440 >> Tehát most, továbbra is ezt a logikát. 823 00:29:28,440 --> 00:29:32,420 Annak ellenére, hogy mi nem változó Neil újra és újra, és újra, hogy őt 824 00:29:32,420 --> 00:29:36,420 hová megy, a legrosszabb esetben, a következő szám talán találkozunk lehetett 825 00:29:36,420 --> 00:29:42,220 száma legyen, mondjuk, volt egy számot nulla, akkor fogunk váltani minden 826 00:29:42,220 --> 00:29:42,730 ezek a srácok. 827 00:29:42,730 --> 00:29:44,950 Tegyük fel, hogy van egy szám, negatív egy, akkor meg kell váltani 828 00:29:44,950 --> 00:29:46,080 mind ezek a srácok. 829 00:29:46,080 --> 00:29:48,500 Szóval tényleg csak ilyen essek A probléma körül, úgy, hogy mi 830 00:29:48,500 --> 00:29:52,620 át a költség a kiválasztási folyamat így a beillesztés 831 00:29:52,620 --> 00:29:56,930 folyamat, úgy, hogy ti most volt mozog nagyjából n mínusz valamit 832 00:29:56,930 --> 00:29:57,940 számát. 833 00:29:57,940 --> 00:30:01,200 És ez a szám a lépést csak akkor fog növelni, ahogy válasszon több számot, 834 00:30:01,200 --> 00:30:04,730 ha van, hogy tolta a srácok vissza, és vissza, és vissza. 835 00:30:04,730 --> 00:30:08,320 >> Tehát a szomorú dolog most az összes ilyen algoritmusokat n négyzeten. 836 00:30:08,320 --> 00:30:10,570 Menjünk előre, és ezeknek köszönhetően fiúk, és elképzelni ezeket egy kicsit 837 00:30:10,570 --> 00:30:11,090 másképp. 838 00:30:11,090 --> 00:30:12,312 Nagyon jól sikerült. 839 00:30:12,312 --> 00:30:14,120 >> [Taps] 840 00:30:14,120 --> 00:30:15,030 >> Rendben van. 841 00:30:15,030 --> 00:30:16,280 Tessék. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Köszönöm - 844 00:30:18,470 --> 00:30:19,190 >> Branson: [hangtalan] tartsa a számokat. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Nem, Ön hogy a számok is. 846 00:30:21,990 --> 00:30:23,440 Rendben van. 847 00:30:23,440 --> 00:30:24,100 Szép munka. 848 00:30:24,100 --> 00:30:25,300 Rendben van. 849 00:30:25,300 --> 00:30:30,510 Tehát lássuk, ha nem most összegezni gyorsabban, és megjelenését, 850 00:30:30,510 --> 00:30:33,410 Pontosan mi történt Itt a következők szerint. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Én megyek előre és húzza fel a Firefox. 853 00:30:38,770 --> 00:30:41,310 Majd kapcsolja a demonstráció A kurzus honlapján. 854 00:30:41,310 --> 00:30:43,870 Java egy kicsit bosszantó, hogy kap munka egyes böngészőkben ezekben a napokban. 855 00:30:43,870 --> 00:30:46,760 Tehát, ha játszani ezt otthon, rájössz, hogy szükség lehet használni Firefox 856 00:30:46,760 --> 00:30:47,990 , hogy ez működik. 857 00:30:47,990 --> 00:30:50,440 És mit fogok csinálni a bemutató a következő. 858 00:30:50,440 --> 00:30:54,875 >> Alul van egy csomó menüpontok, beleértve a kezdő és a 859 00:30:54,875 --> 00:30:55,840 stop gombot. 860 00:30:55,840 --> 00:30:59,450 Továbbá, mint egy félre, úgy tűnik, hogy egy bug ezekben a programokban, amely akkor 861 00:30:59,450 --> 00:31:03,720 nem láthatók a kezdeti és a gombot, ha nem tartja Command vagy az Alt 862 00:31:03,720 --> 00:31:06,560 plus és nagyítás, ami furcsa azt mutatja, hogy több gomb. 863 00:31:06,560 --> 00:31:09,090 Tehát csak FYI, ha játszik ezzel otthon. 864 00:31:09,090 --> 00:31:12,870 Most megyek kattintson a Start gombra, mindössze egy pillanatban megadása után a késleltetés, 865 00:31:12,870 --> 00:31:16,810 mint 200 milliszekundum itt, csak így látjuk, mi történik. 866 00:31:16,810 --> 00:31:20,180 >> Szóval azt állítják, hogy ez a megjelenítés Az első algoritmust 867 00:31:20,180 --> 00:31:23,730 ezek a srácok nem, buborék sort, amely mi cserélték emberek páros. 868 00:31:23,730 --> 00:31:27,490 A legfontosabb betekintést a megjelenítés az, hogy a magassága a rudak 869 00:31:27,490 --> 00:31:30,510 képviseli a méret a számot. 870 00:31:30,510 --> 00:31:32,210 Így a magasabb a sáv, Minél nagyobb a szám. 871 00:31:32,210 --> 00:31:33,680 Rövidebb az oszlop, annál kisebb a szám. 872 00:31:33,680 --> 00:31:38,630 És ha azt veszi észre, mi megy keresztül az első iteráció ezen algoritmus, 873 00:31:38,630 --> 00:31:42,620 csere nagy és kis mennyiségben, hogy a A kis számú az első, és 874 00:31:42,620 --> 00:31:44,280 A nagy szám megy jobbra. 875 00:31:44,280 --> 00:31:48,770 >> És amint megkapjuk a végén a tömb A több mint hét számot, vagyunk 876 00:31:48,770 --> 00:31:49,900 megyek vissza az elejére. 877 00:31:49,900 --> 00:31:51,140 És előre ezt. 878 00:31:51,140 --> 00:31:54,860 A bal szélen, az a kis fickó fog cserélni az oldalra, és ez a 879 00:31:54,860 --> 00:31:56,010 folyamat ismétlődik. 880 00:31:56,010 --> 00:31:59,450 Most ez a megjelenítés gyorsan kerül unalmas, hadd menjen előre, és megáll 881 00:31:59,450 --> 00:32:04,170 , változtassa meg a késés valami sokkal gyorsabb csak azért, hogy most egy érezni 882 00:32:04,170 --> 00:32:05,060 Ezt az algoritmust. 883 00:32:05,060 --> 00:32:07,840 >> Így, bár én már felgyorsult fel, ez mint a korszerűsítés a processzor, vásárlási 884 00:32:07,840 --> 00:32:08,580 egy új számítógépet. 885 00:32:08,580 --> 00:32:12,980 Én alapvetően nem változtak az algoritmus, de valójában még több 886 00:32:12,980 --> 00:32:16,800 világosabban, mint az emberek, hogy a nagy számok bugyogott fel a csúcsra, 887 00:32:16,800 --> 00:32:20,900 , és a kis számok átbuborékoltatásával le az aljára. 888 00:32:20,900 --> 00:32:22,390 És most ez a dolog itt rendezve. 889 00:32:22,390 --> 00:32:25,260 És mint egy félre, a terek, van csak néhány könyvelés ott 890 00:32:25,260 --> 00:32:28,010 segít hány összehasonlítást, vagy hány swap van 891 00:32:28,010 --> 00:32:28,950 valóban megtörtént. 892 00:32:28,950 --> 00:32:30,750 >> Nos, nézzük meg egy a többi, amit láttunk. 893 00:32:30,750 --> 00:32:37,116 Hadd kattintson bubble sort itt, és én döntöm el, és ez az egész weboldal 894 00:32:37,116 --> 00:32:38,936 egy kicsit bugos. 895 00:32:38,936 --> 00:32:41,155 Fogadjuk el a kockázatot és futtassa újra. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Ott vagyunk. 898 00:32:45,030 --> 00:32:47,180 Tehát lássuk kiválasztás sort. 899 00:32:47,180 --> 00:32:49,140 Én nem tudom, miért a menü jelenik meg ott. 900 00:32:49,140 --> 00:32:54,070 Nézzük nagyítás rögzíteni, hogy a bug, változtatni 50-re. 901 00:32:54,070 --> 00:32:56,020 Ah, most ténylegesen hogy sokkal gyorsabb. 902 00:32:56,020 --> 00:32:59,160 Öt ezredmásodperc, vagy úgy, és a Start gombot. 903 00:32:59,160 --> 00:33:00,470 >> Tehát ez a fajta választás. 904 00:33:00,470 --> 00:33:03,070 Tehát még egyszer, gondolom, hogy mi vagyunk tette az emberek itt. 905 00:33:03,070 --> 00:33:08,490 Mentünk a tömb és kiválasztott a legkisebb elem ismét 906 00:33:08,490 --> 00:33:09,250 és újra, és újra. 907 00:33:09,250 --> 00:33:11,110 Most azt állítják, hogy még mindig nagyon rossz. 908 00:33:11,110 --> 00:33:15,010 Még mindig n négyzetes, ide vagy oda, de ez, a való világban, egy kicsit 909 00:33:15,010 --> 00:33:18,280 gyorsabb, mert én valóban figyelembe valamivel kevesebb lépést minden egyes alkalommal. 910 00:33:18,280 --> 00:33:19,800 De mi csak beszélünk, mi? 911 00:33:19,800 --> 00:33:21,830 Lehet, hogy 40, vagy úgy bar itt? 912 00:33:21,830 --> 00:33:23,200 Mi nem beszélünk a 40 millió. 913 00:33:23,200 --> 00:33:27,430 Szóval ez nem teljesen világos számomra, hogy valóban jelentős nyereséget. 914 00:33:27,430 --> 00:33:32,530 >> Hadd menjek vissza, és változtatni a mi harmadik algoritmus, melyet válasszuk 915 00:33:32,530 --> 00:33:33,180 beszúrás sort. 916 00:33:33,180 --> 00:33:36,380 És most már tényleg hibás, mert az étlap tényleg nem lehet ott. 917 00:33:36,380 --> 00:33:40,840 Tehát most akkor lépjünk vissza ide és meg kell kezdeni az algoritmus. 918 00:33:40,840 --> 00:33:43,270 Whoop, start és stop. 919 00:33:43,270 --> 00:33:47,160 Tehát ez a fajta, egy szép minta hozzá, ahol vagyunk újra 920 00:33:47,160 --> 00:33:50,240 behelyezése az emberek, vagy Ebben az esetben a rudakat 921 00:33:50,240 --> 00:33:52,620 a megfelelő helyre. 922 00:33:52,620 --> 00:33:55,430 És ez már azelőtt Megfordultam. 923 00:33:55,430 --> 00:33:58,940 De ez is, elvileg, még n négyzeten. 924 00:33:58,940 --> 00:34:01,430 >> Tehát lássuk, ha nem tudjuk összefoglalni ezek a következők szerint. 925 00:34:01,430 --> 00:34:04,750 Én megyek előre, és csak azért, hogy bennünket egyfajta közös módon beszél 926 00:34:04,750 --> 00:34:08,489 ezekről a dolgokról, hadd mutassam be csak egy kis jelölés itt. 927 00:34:08,489 --> 00:34:12,480 Mindjárt látni úgynevezett nagy O, mert ez egy nagy szó 928 00:34:12,480 --> 00:34:16,320 O. És ez az egyik módja, hogy a számítógép tudós vagy matematikus akár használt 929 00:34:16,320 --> 00:34:19,230 leírni a működési idő néhány algoritmus. 930 00:34:19,230 --> 00:34:21,400 Hány lépés történik mindez? 931 00:34:21,400 --> 00:34:25,080 >> Most fogok zavarba magam a kézírás itt csak egy pillanatra. 932 00:34:25,080 --> 00:34:29,020 De hadd menjek előre, és azt mondják, hogy ez lesz a nagy O ide. 933 00:34:29,020 --> 00:34:33,610 És hadd mutassam be egy másik szimbólum, a tőke omega. 934 00:34:33,610 --> 00:34:37,080 Omega lesz a másik, lényegében nagy O. mivel nagy O 935 00:34:37,080 --> 00:34:40,790 azt jelenti, hogy a legrosszabb esetben mennyi idő talán néhány algoritmus, hogy, a 936 00:34:40,790 --> 00:34:43,480 feltételek n, omega fog , hogy mennyi idő lehet, hogy ez 937 00:34:43,480 --> 00:34:45,409 hogy a legjobb esetben. 938 00:34:45,409 --> 00:34:48,090 És majd meglátjuk, mit értünk legjobb esetben csak egy pillanat. 939 00:34:48,090 --> 00:34:49,940 >> Tehát kezdjük valami egyszerű. 940 00:34:49,940 --> 00:34:54,719 Hadd kezdjem egy lineáris keresést. 941 00:34:54,719 --> 00:34:55,679 Tehát nem válogatás. 942 00:34:55,679 --> 00:34:58,000 Hívjuk ezt lineáris keresést. 943 00:34:58,000 --> 00:35:01,140 És most, hogy egy kis táblázat ebből. 944 00:35:01,140 --> 00:35:06,600 És most, abban az esetben a lineáris keresés a legrosszabb esetben, hogy hány lépés van 945 00:35:06,600 --> 00:35:11,770 fog tartani, hogy találjak egy száma önkényes választás? 946 00:35:11,770 --> 00:35:14,540 És ott van n összesen ajtók vagy n teljes számokat. 947 00:35:14,540 --> 00:35:15,940 Legrosszabb esetben. 948 00:35:15,940 --> 00:35:18,800 Hány lépést fogok kell hogy a megfelelő számú 50 tömbben 949 00:35:18,800 --> 00:35:20,830 n ajtók? 950 00:35:20,830 --> 00:35:21,410 És miért? 951 00:35:21,410 --> 00:35:23,680 Mert lehet, hogy az összes utat át rá a végén. 952 00:35:23,680 --> 00:35:27,120 Annyira, mint Jennifer találkozott, a száma 50 volt, egészen át, így 953 00:35:27,120 --> 00:35:30,760 a legrosszabb esetben lineáris keresés nagy O n, akkor mondjuk. 954 00:35:30,760 --> 00:35:33,430 >> Mi a helyzet a legjobb esetben, ha igazán szerencsés? 955 00:35:33,430 --> 00:35:36,200 Ez csak megy, hogy egy lépést, vagy állandó számú lépésben. 956 00:35:36,200 --> 00:35:37,830 Tehát leírjuk, hogy az 1. 957 00:35:37,830 --> 00:35:39,010 Szóval ez nagyon jó. 958 00:35:39,010 --> 00:35:41,210 Most mi van, ha nem valami mint bináris keresés? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Tehát bináris keresés, a legrosszabb esetben volt, hogy mennyi idő alatt? 961 00:35:47,846 --> 00:35:49,250 >> [Közbeiktatásával VOICES] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Tehát tulajdonképpen azt hallotta egy pár helyen. 963 00:35:51,310 --> 00:35:56,390 Tehát valójában log n, ide vagy oda, mert ahogy osztani a lista fele 964 00:35:56,390 --> 00:36:00,730 újra, és újra, és újra, képesek vagyunk megtalálni, végső soron, az érték, 965 00:36:00,730 --> 00:36:04,750 ha ott van, de van egy fogás. 966 00:36:04,750 --> 00:36:08,590 Mi az a feltételezés, hogy meg kell adottnak a bináris keresés? 967 00:36:08,590 --> 00:36:09,700 Meg kell válogatni. 968 00:36:09,700 --> 00:36:12,770 Ez nem válogatni, akkor hasít a dolog fél újra és újra, és 969 00:36:12,770 --> 00:36:15,490 mehet balra, és akkor menj jobbra, és akkor megy bal és a jobb, de te 970 00:36:15,490 --> 00:36:18,070 nem fog találni az elem, ha A lista nincs rendezve, mert 971 00:36:18,070 --> 00:36:18,790 lehet eltéveszteni. 972 00:36:18,790 --> 00:36:22,120 Mert a heurisztikus, az megy bal vagy jobbra lesz hibás, ha ez 973 00:36:22,120 --> 00:36:23,420 Valóban nincs rendezve. 974 00:36:23,420 --> 00:36:26,110 Tehát van egyfajta rejtett költség használata valami ilyesmi. 975 00:36:26,110 --> 00:36:29,250 >> Nos, menjünk be a válogatás algoritmusok nem keres - 976 00:36:29,250 --> 00:36:31,140 oh, tényleg menjünk üresen. 977 00:36:31,140 --> 00:36:33,190 Bináris keresés a legjobb esetben? 978 00:36:33,190 --> 00:36:36,290 Ez is 1, ha ez csak történik, hogy kellős közepén a tömb, vagy a 979 00:36:36,290 --> 00:36:37,810 a közepén a telefonkönyvben. 980 00:36:37,810 --> 00:36:39,710 Most ismét egy buborék sort. 981 00:36:39,710 --> 00:36:42,570 Tehát újra, most pedig belépő fajta, nem a keresést. 982 00:36:42,570 --> 00:36:47,220 >> A legrosszabb esetben, hogy hány lépést tettünk igény bubble sort fog tartani? 983 00:36:47,220 --> 00:36:48,410 N négyzeten. 984 00:36:48,410 --> 00:36:49,200 Így fogok rajzolni. 985 00:36:49,200 --> 00:36:51,710 Ó, az én kézírás néz ki, még rosszabb amikor ez várható, hogy nagy. 986 00:36:51,710 --> 00:36:52,510 Rendben van. 987 00:36:52,510 --> 00:36:53,570 Szóval ez n négyzeten. 988 00:36:53,570 --> 00:36:59,460 És a legjobb esetben a buborék sort, hány lépést fog ez tartani? 989 00:36:59,460 --> 00:37:00,980 1, hallottam. 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, hallottam. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 2: 1. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, hallottam. 994 00:37:05,010 --> 00:37:06,670 Nem hallom 3? 995 00:37:06,670 --> 00:37:07,080 Rendben van. 996 00:37:07,080 --> 00:37:11,390 Én is úgy hallottam 1, n, 2, de hadd vegye egymástól legalább az első azoknak 997 00:37:11,390 --> 00:37:12,330 javaslatok, 1. 998 00:37:12,330 --> 00:37:15,370 Ez nem egy rossz ösztön, mert egyfajta mintát követ itt. 999 00:37:15,370 --> 00:37:19,670 De ha csak úgy 1 lépés, hogy a világ is azt állítom, hogy a lista 1000 00:37:19,670 --> 00:37:22,900 van rendezve, mert ha én csak szabad hogy 1 lépés, hogy sok eleme 1001 00:37:22,900 --> 00:37:25,230 Igazából lehet ellenőrizni, hogy biztos? 1002 00:37:25,230 --> 00:37:28,270 Nos, csak 1, ami azt jelenti, van n mínusz 1 elem, hogy lehet ki 1003 00:37:28,270 --> 00:37:31,310 rend, és én csak megy a hit után néztem 1 elem a 1004 00:37:31,310 --> 00:37:31,850 dolog van rendezve. 1005 00:37:31,850 --> 00:37:33,930 Tehát 1 nem helyes itt. 1006 00:37:33,930 --> 00:37:35,710 Tehát minimálisan hány tudom kell nézni? 1007 00:37:35,710 --> 00:37:36,680 >> [Közbeiktatásával VOICES] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n mínusz 1, vagy nagyon, n, mert meg kell nézni minden 1009 00:37:40,160 --> 00:37:42,190 elem, hogy megbizonyosodjon arról, hogy az ez nem elromlott. 1010 00:37:42,190 --> 00:37:44,750 De ismétlem, mi fajta hullám a kezét a kisebb számok és 1011 00:37:44,750 --> 00:37:47,100 feltételezik, hogy az n egyre nagyobb lesz, ők érdektelen egyébként. 1012 00:37:47,100 --> 00:37:48,380 Szóval ez buborék sort. 1013 00:37:48,380 --> 00:37:49,830 És most csináljuk az utolsó kettő. 1014 00:37:49,830 --> 00:37:53,520 Selection sort, és aztán do beszúrás sort. 1015 00:37:53,520 --> 00:37:57,160 És akkor majd robbantani a fejében valami sokkal 1016 00:37:57,160 --> 00:37:58,926 jobb, mint az összes ilyen. 1017 00:37:58,926 --> 00:38:00,410 Rendben van. 1018 00:38:00,410 --> 00:38:04,700 >> Mi a legrosszabb esetben futó ideje kiválasztás sort? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n négyzeten. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n tér, hallok. 1021 00:38:06,710 --> 00:38:09,790 De miért n kihúzta, ösztönösen? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Mivel mi csak tette. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Mivel mi csak tette. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Jó válasz. 1026 00:38:13,380 --> 00:38:16,660 De ösztönösen, miért kiválasztás sort n négyzete? 1027 00:38:16,660 --> 00:38:18,980 Mit kell tennünk újra és újra? 1028 00:38:18,980 --> 00:38:22,570 Meg kellett, hogy a szkennelés, az akkor a legkisebb, te vagy a 1029 00:38:22,570 --> 00:38:24,020 legkisebb, te vagy a legkisebb. 1030 00:38:24,020 --> 00:38:27,480 És adott, tudtuk, hogy n lépésben, akkor n mínusz 1, akkor n mínusz 2. 1031 00:38:27,480 --> 00:38:30,700 De ha ilyen hozzá az egészet, vagy hogy azt hittel, hogy én már hozzá 1032 00:38:30,700 --> 00:38:34,810 őket előre, kapunk durván n négyzet mínusz néhány kisebb számokat. 1033 00:38:34,810 --> 00:38:36,730 Így fogom hívni ezt a N négyzeten. 1034 00:38:36,730 --> 00:38:39,530 De kiválasztás sort a legjobb eset, hogy hány lépés van 1035 00:38:39,530 --> 00:38:40,632 fog tartani engem? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [hangtalan] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Ez sajnos még n négyzet, nem igaz? 1038 00:38:44,350 --> 00:38:49,590 Mert ha én kiválasztja a legkisebb elem, és mi volt hét ember van, 1039 00:38:49,590 --> 00:38:53,280 Csak azt tudom, ha egyszer eljut a nagyon vége, hogy én találtam a legkisebb 1040 00:38:53,280 --> 00:38:55,670 szám, bárhol is vagy ő lehetett. 1041 00:38:55,670 --> 00:38:58,820 De hogyan találom meg a következő legkisebb szám? 1042 00:38:58,820 --> 00:39:00,160 Meg kell csinálni egy menetben. 1043 00:39:00,160 --> 00:39:04,810 Így a legjobb esetben, mi a bemenet kiválasztás sort? 1044 00:39:04,810 --> 00:39:07,830 Ez egy már rendezni, első számú, kettes, hármas, négyes. 1045 00:39:07,830 --> 00:39:08,600 De én vagyok egy számítógép. 1046 00:39:08,600 --> 00:39:10,190 Én csak nézni egy dolog egy időben. 1047 00:39:10,190 --> 00:39:12,465 Nem tudok valahogy egy lépést vissza, mint egy ember, és azt mondják, 1048 00:39:12,465 --> 00:39:14,030 ó, ez úgy néz ki a helyes. 1049 00:39:14,030 --> 00:39:17,580 >> Én csak határozni korrektség kiválasztás Rendezés kiválasztásával 1050 00:39:17,580 --> 00:39:18,370 legkisebb szám. 1051 00:39:18,370 --> 00:39:21,390 De még ha találok számú első, Ha nem tudom, mást a 1052 00:39:21,390 --> 00:39:24,460 A többi szám, amit én nem, én tudom, hogy már átadott tömb 1053 00:39:24,460 --> 00:39:27,930 vagy egy sor ajtó mögött, amely számok, az egyetlen módja, tudom, hogy egy 1054 00:39:27,930 --> 00:39:28,680 volt a legkisebb? 1055 00:39:28,680 --> 00:39:32,440 Ha kapok egészen idáig, és rájönnek, A fenébe, az egyik valóban a legkisebb. 1056 00:39:32,440 --> 00:39:34,870 >> De hogyan, akkor megállapítható, hogy kettő a következő kisebb? 1057 00:39:34,870 --> 00:39:38,350 Ezzel ugyanaz a hatékonysági újra és újra. 1058 00:39:38,350 --> 00:39:42,210 Így végül, a beillesztés sort, hogyan, a legrosszabb esetben, 1059 00:39:42,210 --> 00:39:44,990 nem azt mondják, hogy végre? 1060 00:39:44,990 --> 00:39:49,100 Ez is n négyzeten. 1061 00:39:49,100 --> 00:39:53,020 És mi a helyzet a legjobb esetben? 1062 00:39:53,020 --> 00:39:56,282 Majd hagyjuk, hogy a filmsorozat. 1063 00:39:56,282 --> 00:40:00,090 Majd töltse ki az üres legközelebb, de előbb hadd javaslom, hogy 1064 00:40:00,090 --> 00:40:02,620 alapvetően jobban, mint Mindezen, rendben? 1065 00:40:02,620 --> 00:40:05,220 >> Szóval szerintem magad milyen beillesztés fajta lesz. 1066 00:40:05,220 --> 00:40:06,910 Nos, ez nem túl drámai, mert én vagyok az egyetlen 1067 00:40:06,910 --> 00:40:08,970 hogy látta a változást. 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 Tehát itt van egy kicsit különböző bemutató. 1071 00:40:12,615 --> 00:40:16,580 Ha nagyítani itt, látni fogja, hogy a A bal oldali van buborék sort, a 1072 00:40:16,580 --> 00:40:20,740 középen van választék sort, valamint a a szélsőjobboldali, van valami, amit 1073 00:40:20,740 --> 00:40:23,380 még nem nézett még nevű merge sort. 1074 00:40:23,380 --> 00:40:26,080 De gondolja meg, amit már itt eddig ma. 1075 00:40:26,080 --> 00:40:29,200 Amikor Jennifer először jött fel a színpadra, mentünk át a tömböt a számok 1076 00:40:29,200 --> 00:40:33,750 újra, és újra, és lineáris keresés és mi van a lineáris működési idő, nagy O 1077 00:40:33,750 --> 00:40:35,100 n, hogy úgy mondjam. 1078 00:40:35,100 --> 00:40:41,000 >> Ha most úgy az első héten osztály, amikor már oszd meg és uralkodj, 1079 00:40:41,000 --> 00:40:43,740 és mi volt a telefonkönyv könnyezés, és Jennifer, és közösen 1080 00:40:43,740 --> 00:40:47,500 alátámasztani, hogy a legfontosabb betekintést, ami az volt, hogy ismételje meg magát újra és újra 1081 00:40:47,500 --> 00:40:50,930 valahogy eldobja, eldobja, eldobja, fele a probléma, vagy a 1082 00:40:50,930 --> 00:40:55,320 általában elosztjuk a probléma a felére, kezeljük, majd a kisebb darab 1083 00:40:55,320 --> 00:40:59,630 A probléma fogalmilag egyenértékű a másik, akkor valahogy 1084 00:40:59,630 --> 00:41:00,910 alapvetően jobb. 1085 00:41:00,910 --> 00:41:04,720 De buborék sort, a kiválasztás sort, a beillesztés sort, most már lehet 1086 00:41:04,720 --> 00:41:06,560 ilyen betekintést, hogy Jennifer nem. 1087 00:41:06,560 --> 00:41:10,220 Mi nagyjából csak sétált vissza oda egy csomó idő, és mi 1088 00:41:10,220 --> 00:41:12,650 csípett a dolgokat egy kicsit, csere ebben a sorrendben, talán 1089 00:41:12,650 --> 00:41:13,730 behelyezése vagy kiválasztásával. 1090 00:41:13,730 --> 00:41:16,950 De a végén a nap, csináltam egy csomó A kínos séta oda-vissza. 1091 00:41:16,950 --> 00:41:21,160 Nem igazán tőkeáttétel valami okos, mint Jennifer tetszett elválasztó 1092 00:41:21,160 --> 00:41:22,040 és hódító. 1093 00:41:22,040 --> 00:41:25,620 >> Tehát merge sort, ezzel szemben, amit nem fogja látni, amíg a jövő héten, hogy megy 1094 00:41:25,620 --> 00:41:29,540 hogy kiterjessze e lényeg, hogy elosztjuk a bemeneti, majd felére, majd 1095 00:41:29,540 --> 00:41:30,580 felére, majd a felére. 1096 00:41:30,580 --> 00:41:34,590 És iterációk hogy hurok, válogatás a bal felére, és a megfelelő 1097 00:41:34,590 --> 00:41:38,200 felét, majd a bal fele a bal felét, és a jobb fele a bal oldalon, majd 1098 00:41:38,200 --> 00:41:40,990 a bal fele a jobb felére, és a jobb fele a jobb felét. 1099 00:41:40,990 --> 00:41:42,840 És ismétlődő újra és újra. 1100 00:41:42,840 --> 00:41:46,170 >> Szóval majd meglátjuk, ezt vizuálisan, de ez a az, mi vár ránk a jövő héten. 1101 00:41:46,170 --> 00:41:49,760 És általában, amikor azt gondoljuk, egy kicsit kicsit nehezebb minden ilyen probléma. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Mi n négyzetes a bal oldalon, n négyzetes a közepén, és n 1104 00:41:57,970 --> 00:41:59,400 log n a jobb oldalon. 1105 00:41:59,400 --> 00:42:00,590 Tehát az igazi Cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Találkozunk hétfőn. 1107 00:42:02,040 --> 00:42:05,163 >> [Taps]