1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [3. hét, folytatás]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Harvard University]

3
00:00:04,110 --> 00:00:07,130
>> [Ez CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Rendben van. Üdv újra. Ez CS50, és ez a vége a 3. hét.

5
00:00:11,010 --> 00:00:14,680
>> Így azok számára ismeretlen, az elmúlt évben a Harvard elindította az úgynevezett az Innovation Lab,

6
00:00:14,680 --> 00:00:18,530
vagy i-labor, amely egy csodálatos épület a folyón a HBS campus

7
00:00:18,530 --> 00:00:22,640
amely nyitott a főiskolai hallgatók, GSAS hallgatók, diákok egész campus,

8
00:00:22,640 --> 00:00:27,000
beleértve a kar, és ez a hely, hogy jöjjön össze dolgozni innovatív dolgokat,

9
00:00:27,000 --> 00:00:29,180
különösen a vállalkozói dolgok

10
00:00:29,180 --> 00:00:33,410
ha te és 0 vagy több barátai gondolsz csinál valamit vállalkozói

11
00:00:33,410 --> 00:00:37,080
vagy ez alatt az osztály, miután ez az osztály, illetve azon túl.

12
00:00:37,080 --> 00:00:41,540
>> Tehát az egyik dolog, mégis több mint J távon ezeknek az utazásoknak,

13
00:00:41,540 --> 00:00:44,510
amelyek közül az egyik az, hogy New York, amelyek közül az egyik a Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
A tér nagyon korlátozott, de ez egy lehetőség, hogy dörzsölje vállát MBA

15
00:00:47,530 --> 00:00:52,200
és végzős hallgatók az egész egyetemen, és valóban időt e egyes területeken

16
00:00:52,200 --> 00:00:55,500
csevegés up induló, csevegni fel a vállalkozók és a hasonlók.

17
00:00:55,500 --> 00:00:57,870
Tehát, ha érdekel, nézd meg ezt az URL-t ide.

18
00:00:57,870 --> 00:01:01,220
Ugyancsak elérhető a diák online.

19
00:01:01,220 --> 00:01:04,610
>> Tudnánk hang le a ház hang, csak egy kicsit?

20
00:01:04,610 --> 00:01:08,640
Ha azt szeretné, hogy csatlakozzon hozzánk ebédre a péntek, 13:15 in Fire & Ice, kérjük fejét ott.

21
00:01:08,640 --> 00:01:11,390
Elnézést, ha az űrlap már ki van töltve, mire odaér.

22
00:01:11,390 --> 00:01:13,750
De mi is ezt a hagyományt kezdve.

23
00:01:13,750 --> 00:01:17,350
>> Ma továbbra is a magasabb szintű vita a különböző problémákat, hogy meg tudjuk oldani,

24
00:01:17,350 --> 00:01:21,330
élességállítás sokkal kevesebb, ma legalább a kódot, és sokkal inkább ötleteket.

25
00:01:21,330 --> 00:01:24,720
Szóval szerintem vissza a 0. héten, amikor elszakadt a telefonkönyvet a felére,

26
00:01:24,720 --> 00:01:28,260
amelynek célja az volt, hogy tegyen valamit, igaz, egy kicsit drámai

27
00:01:28,260 --> 00:01:32,360
hanem elküldeni a pontra, hogy keresési nem kell, szükségképpen,

28
00:01:32,360 --> 00:01:35,100
annyira nyilvánvaló első pillantásra, mint gondolnád.

29
00:01:35,100 --> 00:01:40,200
És problémamegoldás általában nem feltétlenül mindig a legjobb -

30
00:01:40,200 --> 00:01:44,130
A legkézenfekvőbb megoldás lehet, hogy nem feltétlenül a legjobb.

31
00:01:44,130 --> 00:01:47,300
Így volt ez a telefonkönyvben, és őszintén szólva, mindannyian ebben a szobában volt, az ösztönök,

32
00:01:47,300 --> 00:01:51,470
legvalószínűbb, hogy indítsa el a közepén, ha keres Mike Smith, majd menj balra vagy jobbra

33
00:01:51,470 --> 00:01:54,280
alapuló bármilyen betűvel mi történt a végén be.

34
00:01:54,280 --> 00:01:57,560
>> De az egyszerű ötlet, hogy az emberek adottnak oly sokáig

35
00:01:57,560 --> 00:02:00,670
Tényleg meg kell kezdeni, hogy jöjjön az élvonalban a fejedben

36
00:02:00,670 --> 00:02:03,900
mert a problémák kap sokkal bonyolultabb, mint egy telefonkönyv,

37
00:02:03,900 --> 00:02:07,420
ugyanezen egyszerű, briliáns meglátásai mit fog lehetővé teszi számunkra,

38
00:02:07,420 --> 00:02:10,259
megoldása sokkal bonyolultabb és több érdekes problémák,

39
00:02:10,259 --> 00:02:12,930
köztük néhány dolog, amit magától értetődőnek már ezekben a napokban.

40
00:02:12,930 --> 00:02:15,720
Milliárdjai weboldalak ott, és még a Google és Bing és hasonlók

41
00:02:15,720 --> 00:02:17,660
képesek a dolgok nekünk ilyesmi.

42
00:02:17,660 --> 00:02:22,300
Ez nem történik a lineáris kereső, kereső segítségével az összes lehetséges weboldalakat.

43
00:02:22,300 --> 00:02:25,290
Facebook tudja mondani, hogy ki az összes barátok vagy ismerősök ismerősei,

44
00:02:25,290 --> 00:02:28,250
és hogy túl lehet tenni látszólag egy pillanat ezekben a napokban

45
00:02:28,250 --> 00:02:30,820
annak ellenére, hogy több millió felhasználó.

46
00:02:30,820 --> 00:02:34,250
>> És hogyan tudjuk valójában megoldani a problémákat, hogy a skála végső soron csökkenti

47
00:02:34,250 --> 00:02:37,830
Az ötleteket néztük, a 0. héten, és egy kicsit ma.

48
00:02:37,830 --> 00:02:42,320
Nem fogunk újra végrehajtani ezt az algoritmust, de emlékszem mi is tette 0. héten e feladat

49
00:02:42,320 --> 00:02:44,780
ahol már mindenki feláll, veszi a 1-es szám,

50
00:02:44,780 --> 00:02:48,720
és akkor már mindenki saját count által párosítás ki, hozzátéve, a számok együtt,

51
00:02:48,720 --> 00:02:51,930
akkor fele banda leült minden iteráció.

52
00:02:51,930 --> 00:02:56,750
Így mentünk 500-tól a tanulókat, hogy 250-125 és így tovább.

53
00:02:56,750 --> 00:03:00,080
De ahogy azt mondta hétfőn, a hatalmas ötlet, ott

54
00:03:00,080 --> 00:03:02,460
az volt, hogy ha megduplázta a méretét, hogy a probléma

55
00:03:02,460 --> 00:03:06,480
és az összes gyerekek Bíróság vagy Ec 10 jött vissza a szobába, és csatlakozott hozzánk,

56
00:03:06,480 --> 00:03:09,510
nos, valószínűleg számolni, hogy az egész csoport összesített

57
00:03:09,510 --> 00:03:13,380
mindössze 1 további nagy iteráció a hurok, mert csak talán kétszeresen

58
00:03:13,380 --> 00:03:15,630
vagy az EK 10 esetében egy kicsit több mint a duplája a méret.

59
00:03:15,630 --> 00:03:18,440
És így kellene költeni egy kicsit több időt,

60
00:03:18,440 --> 00:03:22,000
de nem kell költeni 400 vagy 700 több lépésben.

61
00:03:22,000 --> 00:03:26,550
>> Csak festeni ezt a képet úgy, hogy ez egy kicsit kevésbé elméleti, ne már mindenki álljon fel.

62
00:03:26,550 --> 00:03:31,100
De ha azok, akik úgy döntöttek, hogy üljön a zenekar ma nem bánnám állva,

63
00:03:31,100 --> 00:03:34,580
lássuk, tudunk kitalálni köztetek, aki a legmagasabb ember

64
00:03:34,580 --> 00:03:36,730
ezzel ugyanaz a fajta összehasonlító algoritmus.

65
00:03:36,730 --> 00:03:41,830
Szóval, ha ül a zenekar, elnézést kérek, de az 1. lépésben, állj fel;

66
00:03:41,830 --> 00:03:44,650
2. lépés pár le valaki a közelben van,

67
00:03:44,650 --> 00:03:49,360
kitalálni, aki magasabb, és ülj le, ha rövidebb.

68
00:03:49,360 --> 00:03:51,360
Ezután ismételjük meg.

69
00:03:51,360 --> 00:03:56,280
[Diákok zúgolódás]

70
00:04:13,450 --> 00:04:15,320
>> Oké.

71
00:04:15,320 --> 00:04:19,010
Oké. Egy maradt állva. Mi a neve? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, te vagy a legmagasabb ember a zenekar pont ma.

73
00:04:21,959 --> 00:04:28,100
>> Gratulálok. [Taps és éljenzés] Oké. Van egy helyet. Így találtunk Andrew.

74
00:04:28,100 --> 00:04:30,870
De meddig tartott volna meg, például, hogy megtalálják Andrew

75
00:04:30,870 --> 00:04:33,740
ebben a zenekarban részén 50 + vagy, így az emberek?

76
00:04:33,740 --> 00:04:36,900
Tudtam volna egy viszonylag egyszerű megközelítést, és itt kezdődnek.

77
00:04:36,900 --> 00:04:39,270
És én 2 ember feláll, és én csak hasonlítsa össze őket,

78
00:04:39,270 --> 00:04:42,120
és akkor azt mondom, hogy aki egy kicsit rövidebb, "Oké, te ülj le,"

79
00:04:42,120 --> 00:04:44,380
és fogok emlékezni, akik a magasabb ember volt.

80
00:04:44,380 --> 00:04:49,030
Aztán Ismétlem, ismétlem, ismétlem, én tarts ki, hogy a legmagasabb ember

81
00:04:49,030 --> 00:04:51,920
amíg nem találok valakit, kicsit magasabb, mint őket, ekkor a

82
00:04:51,920 --> 00:04:54,950
A valamivel rövidebb személynek kell majd ülnie.

83
00:04:54,950 --> 00:04:57,690
De ez az algoritmus ebben a zenekarban szakaszban, ha van n van,

84
00:04:57,690 --> 00:05:00,480
hány lépést, hogy algoritmus fog tartani? >> [Hallgató] N.

85
00:05:00,480 --> 00:05:03,580
>> Ez fog tartani n, igaz, mert a legrosszabb, hogy úgy mondjam,

86
00:05:03,580 --> 00:05:09,090
a legmagasabb ember az utolsó ember, hogy kapok, hogy csak véletlen balszerencse.

87
00:05:09,090 --> 00:05:14,260
Így a legrosszabb esetben a futási ideje, hogy az algoritmus lineáris, ez n,

88
00:05:14,260 --> 00:05:18,070
ahol n értéke a teljes száma, akik a térben, a méret a probléma.

89
00:05:18,070 --> 00:05:19,600
Mi ez az algoritmus?

90
00:05:19,600 --> 00:05:22,080
Az a tény, hogy az összes felállt, majd ismét a felét maga leült,

91
00:05:22,080 --> 00:05:23,950
fele úgy ült le, a fele akkor leült.

92
00:05:23,950 --> 00:05:26,070
Hány lépéseket kell tenni, hogy ha van n ide?

93
00:05:26,070 --> 00:05:30,200
[Hallgató] N log n. >> Lenne rosszabb. Jelentkezzen n.

94
00:05:30,200 --> 00:05:32,930
>> Így log n, akkor is, ha nem igazán emlékszem, mi a logaritmus van,

95
00:05:32,930 --> 00:05:38,410
most, csak nyilvánvaló, hogy vonatkozik valahogy ennek felére csökkentését és a felére csökkentését és a felére csökkentését.

96
00:05:38,410 --> 00:05:41,000
Nem kell, hogy egy 2-es szorzóval. Ez lehet egy tényező a 3.

97
00:05:41,000 --> 00:05:46,560
De ez a megismétlése ugyanolyan tényező, hogy a méret a probléma itt kezdődik

98
00:05:46,560 --> 00:05:49,620
de aztán rögtön megy itt, akkor itt, akkor itt, akkor itt.

99
00:05:49,620 --> 00:05:53,580
Ugye nem vesz kis harap ki a problémát, akkor tényleg aprítás el rajta

100
00:05:53,580 --> 00:05:56,160
egy nagy csapásra minden alkalommal.

101
00:05:56,160 --> 00:06:00,810
Így volt 50 fő, majd 25, majd a 12 ½ vagy 13 ember áll,

102
00:06:00,810 --> 00:06:05,370
majd 6 ½ és így tovább, míg végül csak Andrew maradt állva.

103
00:06:05,370 --> 00:06:08,710
Így fogjuk hívni, hogy a log n, és tudod vizualizálni ezt az alábbiak szerint.

104
00:06:08,710 --> 00:06:12,570
Emlékezzünk vissza, ezt a képet itt, ahol egy lineáris algoritmus olyan, mint a piros vonal van,

105
00:06:12,570 --> 00:06:17,520
a sárga vonal volt a számolás által 2s algoritmust, hogy mi használt számláló diákok

106
00:06:17,520 --> 00:06:22,300
a múltban, de ma a Szent Grál lesz, hogy továbbra is ezt a zöld vonal

107
00:06:22,300 --> 00:06:25,470
ahol ha megduplázta a száma, akik a zenekari szakasz vagy csak azt mondta:

108
00:06:25,470 --> 00:06:29,170
pokol, vessünk mindenki az egész terem feláll, nem olyan nagy dolog

109
00:06:29,170 --> 00:06:31,560
mert nagyjából kétszerese hány ember van itt lenn,

110
00:06:31,560 --> 00:06:33,500
1 további iteráció, nem probléma.

111
00:06:33,500 --> 00:06:36,200
>> Úgy találtuk, Andrew vagy akárki történik, hogy magasabb, mint Andrew

112
00:06:36,200 --> 00:06:38,770
a mezzanine, vagy az erkélyen.

113
00:06:38,770 --> 00:06:42,140
Tehát ez az egyszerű ötlet, hogy mi volt annyira magától értetődőnek a telefonkönyv,

114
00:06:42,140 --> 00:06:46,170
észre, hogy olyan sok különböző helyen, ahol mi is alkalmazzák.

115
00:06:46,170 --> 00:06:50,810
Csak néhány pofon zsargont - valójában, ahelyett zsargon első,

116
00:06:50,810 --> 00:06:52,750
engedj el ezt a képet itt.

117
00:06:52,750 --> 00:06:56,970
Most beszéltünk n és n / 2, majd jelentkezzen be n,

118
00:06:56,970 --> 00:07:00,500
de természetesen jön ki, ahogy majd során a félév,

119
00:07:00,500 --> 00:07:05,130
egyéb fajta matematikai képletek, hogy leírja ezt az általános fogalmat a futási idő.

120
00:07:05,130 --> 00:07:07,580
Ezek közül az összefüggésben most, mert meglátjuk nemsokára

121
00:07:07,580 --> 00:07:09,900
algoritmusok, hogy ezek valóban képviselnek.

122
00:07:09,900 --> 00:07:17,990
>> De észre, itt a lineáris vonal n, az egyenes, valójában nagyon alacsony mutat most.

123
00:07:17,990 --> 00:07:22,950
Ez a fajta optikai illúzió, hogy mi csak változtatni, amit az x tengely

124
00:07:22,950 --> 00:07:26,130
és az y tengelyen, és tudjuk, hogy egy egyenes vonal pontjára tetszőleges irányban akarunk.

125
00:07:26,130 --> 00:07:30,350
De az oka annak, hogy ez olyan látszólag sima most

126
00:07:30,350 --> 00:07:35,690
azért van, mert szükséges, hogy legyen hely a grafikonon sokkal lassabban fut alkalommal.

127
00:07:35,690 --> 00:07:39,030
Most, tudom, hogy van néhány nagyon rossz algoritmusok az életben,

128
00:07:39,030 --> 00:07:43,790
amelyek közül néhány nem veszi n lépéseket, vagy, ami még jobb, jelentkezzen n lépéseket, de több.

129
00:07:43,790 --> 00:07:48,820
Így a vonal fölé n itt alul nyilatkozat van n-szer log n,

130
00:07:48,820 --> 00:07:51,410
és meglátjuk, hogy ez mit jelent, mielőtt hosszú.

131
00:07:51,410 --> 00:07:56,010
Fent mely n négyzet, és nem láttunk semmilyen n faragva algoritmusok még de mindjárt.

132
00:07:56,010 --> 00:07:57,660
És úgy néz ki, nagyon rossz.

133
00:07:57,660 --> 00:08:01,610
Van 2-n, valami exponenciális, amely úgy érzi, még rosszabb.

134
00:08:01,610 --> 00:08:05,760
És mégis, furcsa módon, akkor nincs n cubed, ami ha valami előre gondolkodás,

135
00:08:05,760 --> 00:08:10,000
ha a fajta nem a matematika, a 2 az n valóban lesz sokkal egyenesebb,

136
00:08:10,000 --> 00:08:15,930
jóval feljebb, mint n CubeD, ha megnézi a tengelyek elég messzire ki.

137
00:08:15,930 --> 00:08:19,890
Így észre most ezek tengelye önkényesen 2-10 az x tengelyen.

138
00:08:19,890 --> 00:08:21,770
>> És mit jelent ez?

139
00:08:21,770 --> 00:08:23,890
Ez azt jelenti, 2 fő 10 fő részére a szobában.

140
00:08:23,890 --> 00:08:27,200
Ez minden x: olyan méretű probléma, függetlenül a kontextus.

141
00:08:27,200 --> 00:08:30,420
És egy függőleges tengely körül most is több másodperc, vagy több lépésben -

142
00:08:30,420 --> 00:08:31,840
bizonyos időegység.

143
00:08:31,840 --> 00:08:34,740
De észre, hogy ez a 0-60 és 0 10-ig.

144
00:08:34,740 --> 00:08:38,549
De ha ilyen zoom ki, ahogy azt az Excel vagy valamilyen ábrázolási szoftver,

145
00:08:38,549 --> 00:08:43,370
és felmegyünk a 200.000, észre, hogy valami hasonló a 2 az n

146
00:08:43,370 --> 00:08:47,520
fog teljesen elborít a működési idők n négyzetes,

147
00:08:47,520 --> 00:08:50,960
n CubeD, n log n - mindent, amit beszéltünk eddig.

148
00:08:50,960 --> 00:08:54,190
És mégis, a fogás, amikor elkezd beszélni a dolgokat, mint a Facebook

149
00:08:54,190 --> 00:08:57,150
ahol még sok, sok, sok ember minden összekapcsolt,

150
00:08:57,150 --> 00:09:00,650
Ön n az emberek, akik mindegyike lehet, annyi, mint n barátai

151
00:09:00,650 --> 00:09:02,860
ha mindenki egyfajta kishaver a világon,

152
00:09:02,860 --> 00:09:08,100
nos, ez n-szer n már úgy, hogy ez n négyzetes lehetséges barátságok,

153
00:09:08,100 --> 00:09:10,950
legalább 1 irányba, n faragva lehetséges barátságok.

154
00:09:10,950 --> 00:09:15,330
Annak érdekében, hogy már azt sugallja, hogy a Facebook keresést szociális grafikonon, hogy úgy mondjam,

155
00:09:15,330 --> 00:09:18,090
lehet kezdeni kell kifejezni ilyen típusú képleteket.

156
00:09:18,090 --> 00:09:19,820
>> Majd gyere vissza, és hogy ez sokkal több konkrét,

157
00:09:19,820 --> 00:09:23,280
de most a cél a következő hetek

158
00:09:23,280 --> 00:09:27,170
lesz arra, hogy ne menjen a végrehajtási algoritmusok vagy kódot

159
00:09:27,170 --> 00:09:29,870
Ebből a célból vesz fel annyi időt, mint valami, mint ez.

160
00:09:29,870 --> 00:09:33,110
De érdekes dolog számítógép-tudomány, ha továbbra is az ezen a területen

161
00:09:33,110 --> 00:09:38,320
vevő osztályok, mint a CS121, CS124, mindkettő elméleti tanfolyamok,

162
00:09:38,320 --> 00:09:41,300
az, hogy vannak valójában néhány probléma, hogy létezik a világon

163
00:09:41,300 --> 00:09:45,710
hogy alapvetően, amennyire tudjuk, nem lehet megoldani gyorsabban

164
00:09:45,710 --> 00:09:48,880
mint a legrosszabb ezeket grafikonok ténylegesen sugallja.

165
00:09:48,880 --> 00:09:53,660
Tehát van egy csomó nyitott problémák ebben a világban, hogy nem sokkal jobb, mint az embereknek eddig.

166
00:09:53,660 --> 00:09:56,130
>> Szóval kezdjük majd ezt a példát.

167
00:09:56,130 --> 00:09:59,650
Láttunk Sean küzdenek ezzel a kamera, túl ügyetlenül videón.

168
00:09:59,650 --> 00:10:05,270
De a valóság az volt, amikor Sean bízták meg találni egy táblán, mint ez a szám 7,

169
00:10:05,270 --> 00:10:10,300
Emlékeztetek arra, hogy azt mondtam, hogy "van valahol mögött ezeket a darabokat papír vagy fehér ajtók

170
00:10:10,300 --> 00:10:12,570
"A 7-es számú. Sean, találják meg a számunkra."

171
00:10:12,570 --> 00:10:14,200
És ez csodálatosan kínos nézni

172
00:10:14,200 --> 00:10:15,790
mert ő tényleg küzd ezzel a problémával.

173
00:10:15,790 --> 00:10:19,720
A valóság azonban az volt, Sean ugyanolyan jól, mint bárki más a szobában volna tenni.

174
00:10:19,720 --> 00:10:21,890
Vett egy kicsit hosszabb, mint egy átlagos ember is van,

175
00:10:21,890 --> 00:10:24,760
de feltételezte, hogy volt valami trükk, hogy ezt a problémát,

176
00:10:24,760 --> 00:10:26,590
azt feltételezte, hogy ő hiányzik valami.

177
00:10:26,590 --> 00:10:29,320
És ez sem segített, hogy a több száz szeme szem le rá.

178
00:10:29,320 --> 00:10:34,250
>> De a valóság az volt, ha a bemenet a probléma egy csomó véletlen számok

179
00:10:34,250 --> 00:10:37,120
és te azt kérik, hogy megtalálják 1 ilyen száma,

180
00:10:37,120 --> 00:10:39,770
A legjobb, amit tehetünk, lineáris keresés.

181
00:10:39,770 --> 00:10:44,060
Indítsa el a bal oldalon, lépjünk át a jobb, vagy indítsa el a megfelelő, mozgassa balra.

182
00:10:44,060 --> 00:10:48,300
Visszamenőlegesen, akkor lehet gondolkodni, "Sean, miért nem csak elkezd a másik végén?"

183
00:10:48,300 --> 00:10:52,120
Nos, 7 volna éppen olyan könnyen már itt véletlenszerűen,

184
00:10:52,120 --> 00:10:54,980
de én szándékosan tettem oda, mert gondoltam, hogy nem fog kezdeni a végén.

185
00:10:54,980 --> 00:10:59,320
Szóval ilyen manipulált a helyzetet, hanem a véletlen esélye 7 lehetett volna sehol.

186
00:10:59,320 --> 00:11:02,380
Tehát kezdve a jobb szélen talán jobb lett volna akkor,

187
00:11:02,380 --> 00:11:04,320
de mi van, ha a következő évben a 7-mailt?

188
00:11:04,320 --> 00:11:06,830
Ez nem egy gyökeresen új megoldást a problémára -

189
00:11:06,830 --> 00:11:10,520
1-jétől kezdődően végét, vagy a másik -, amikor nem adott más feltételezéseket.

190
00:11:10,520 --> 00:11:13,620
Így Sean kezdte nézegette a számokat, és azt mondta, "5. Ez nem itt."

191
00:11:13,620 --> 00:11:17,280
Aztán itt van, és látta, 19, aztán megállt, körülbelül 20 másodpercig

192
00:11:17,280 --> 00:11:22,330
Aztán kinyitotta ezt a 13, majd nyilvánvalóvá vált,

193
00:11:22,330 --> 00:11:24,270
hogy nem úgy tűnik, hogy a minta itt.

194
00:11:24,270 --> 00:11:28,090
Nem volt 1, 2, 3, 4 vagy a hasonló. Voltak hiányosságok a számok, ami nem segített.

195
00:11:28,090 --> 00:11:32,320
És túl az a tény, hogy ezek az olcsó használt darab papír, hogy fedezze fel a számokat

196
00:11:32,320 --> 00:11:35,270
valójában szándékos, mert ha én el ezeket a darab papír,

197
00:11:35,270 --> 00:11:38,760
a legtöbben, Sean benne, talán volna pillantott fajta makroszkóposan

198
00:11:38,760 --> 00:11:43,410
a tábla, és azt mondta: "Ó, 7 nyilvánvalóan ott van." Megcsináltuk azonnal.

199
00:11:43,410 --> 00:11:46,460
>> És hogy lehet az út az emberi agy munkálatok bizonyos mértékig,

200
00:11:46,460 --> 00:11:50,730
de a valóságban, a szeme vagy az elme valószínűleg futást a számokat jobbról balra,

201
00:11:50,730 --> 00:11:55,190
balról jobbra, középen out - valami folyik élettanilag

202
00:11:55,190 --> 00:11:57,640
oly módon, hogy úgy éreztem, mintha ez történt azonnal,

203
00:11:57,640 --> 00:12:01,360
de odds még belsőleg volt valamilyen módszert találni 7.

204
00:12:01,360 --> 00:12:05,160
És valóban, most, hogy beszélünk tömbök és adatszerkezetek

205
00:12:05,160 --> 00:12:08,780
és a memória belsejében egy számítógép, az egyetlen dolog, amit az emberek tehetünk

206
00:12:08,780 --> 00:12:13,070
hogy nézd meg az egyedi memóriahelyek 1 egy időben.

207
00:12:13,070 --> 00:12:16,600
>> Szóval minden egyéb helyszín is lehet a fedett fel néhány darab papírt

208
00:12:16,600 --> 00:12:21,170
mert nem látni egyébként. Mi csak akkor van 1 dolog egy időben.

209
00:12:21,170 --> 00:12:25,030
Tehát ebben az esetben, a Sean esetében, mentünk ide, majd mentünk itt

210
00:12:25,030 --> 00:12:31,040
aztán mentünk itt, itt, itt, itt, van okos végére

211
00:12:31,040 --> 00:12:34,450
és csak egyfajta átugrott ezt önkényesen és találat 7 ott.

212
00:12:34,450 --> 00:12:37,470
Ez nem volt különösebben különleges. Ez is volt az elromlott.

213
00:12:37,470 --> 00:12:39,530
De végre megtalálta 7.

214
00:12:39,530 --> 00:12:45,360
De most a elvitelre valóban az, hogy a legjobb, amit tehetünk, ha nem adott információt

215
00:12:45,360 --> 00:12:50,400
más, mint a véletlenszerűen válogatott számok kezdeni a bal vagy indítsa el a jobb.

216
00:12:50,400 --> 00:12:54,950
Vagy fene, akkor véletlenszerűen nyit ajtót, de akkor mit is jelent, hogy véletlen?

217
00:12:54,950 --> 00:12:57,220
Nos, volna, hogy valahogy hivatalossá, hogy mit jelent itt kezdődnek,

218
00:12:57,220 --> 00:13:01,150
akkor megy itt, akkor menj ide. Sean volt nagy, és ez csak szórakoztató nézni.

219
00:13:01,150 --> 00:13:06,340
Mi lenne, ha ehelyett változtatni a probléma egy kicsit, és töltsük fel az idei Sean, ha úgy tetszik?

220
00:13:06,340 --> 00:13:09,460
Kér valaki, hogy kényelmes jön a színpadra, és megoldani egy kicsit más probléma

221
00:13:09,460 --> 00:13:12,330
és a megjelenő kamera?

222
00:13:12,330 --> 00:13:15,720
>> Menjünk túl a zenekar, mert ti már elég részt ma már.

223
00:13:15,720 --> 00:13:21,430
Mit szólnál rózsaszín, a kalap? Gyere le. Mi a neve? >> Alex. >> Alex. Oké.

224
00:13:21,430 --> 00:13:24,580
Szóval Alex lesz az idei Sean és meg fog jelenni a következő néhány évben

225
00:13:24,580 --> 00:13:27,770
értékű CS50 előadások.

226
00:13:27,770 --> 00:13:30,340
Alex, örülök, hogy találkoztunk. >> Örülök, hogy találkoztunk is.

227
00:13:30,340 --> 00:13:33,470
A kihívás kéznél az Ön számára, hogy van, hogy egy kicsit könnyebb

228
00:13:33,470 --> 00:13:38,950
az, hogy én mondom ugyanazt a számok itt, de ők most rendezve.

229
00:13:38,950 --> 00:13:41,800
Szóval most a cél az, hogy megtalálják a 7-es szám.

230
00:13:41,800 --> 00:13:45,370
És valóban, mi kéne, hogy ez a - készen a fajta csalás, mint egy számítógép, nem,

231
00:13:45,370 --> 00:13:47,990
megnézi, mi a számok egy pillanattal ezelőtt.

232
00:13:47,990 --> 00:13:50,360
A kréta ez valójában nem fog segíteni, hogy sok minden,

233
00:13:50,360 --> 00:13:52,810
de most úgy tesznek, mintha nem tudod, mi az eredeti tömb.

234
00:13:52,810 --> 00:13:56,600
Minden, amit most már tudom, hogy van egy sor rendezett számok

235
00:13:56,600 --> 00:14:00,360
hogy lehetnek különbségek közöttük, és a cél az, hogy megtalálják a 7-es szám.

236
00:14:00,360 --> 00:14:05,080
Hogyan, egy ésszerű ember, menjen a megállapítás a 7-es szám?

237
00:14:05,080 --> 00:14:07,770
>> Tovább alacsony és magas? >> Oké. Tovább növekvő sorrendben.

238
00:14:07,770 --> 00:14:10,990
És ne tépje őket. Nézzük csak emeljük fel őket, így mi is újra őket.

239
00:14:10,990 --> 00:14:14,730
Oké, tehát 1. Várj. Mielőtt folytasd, ez 1, nyilvánvalóan rossz.

240
00:14:14,730 --> 00:14:17,270
Szóval, mi megy keresztül a fejedben a következő lépés? Mi a következő lépés?

241
00:14:17,270 --> 00:14:23,250
A következő egy. >> Oké. A következő egy. Jó. 3, így helytelen. Mi a következő lépés?

242
00:14:23,250 --> 00:14:27,670
Keep on megy. >> Rendben. Keep on megy. 5.

243
00:14:27,670 --> 00:14:31,110
Így tovább megy, és hadd adja ezt az utókor számára.

244
00:14:31,110 --> 00:14:35,720
7. >> Kiváló. Nagyon jó. Megtaláltam a 7-es szám. [Taps]

245
00:14:35,720 --> 00:14:39,720
Szóval ez jó volt, de Sean is megtalálta a 7-es szám.

246
00:14:39,720 --> 00:14:44,490
És azt állítják, hogy még nem igazán kihasználva ez a kiegészítő információként,

247
00:14:44,490 --> 00:14:47,780
amely szerint ezek a számok vannak rendezve.

248
00:14:47,780 --> 00:14:51,520
Így tehetünk a jobb? Akármi javaslatok itt? Igen, vissza.

249
00:14:51,520 --> 00:14:54,710
[Hallgató] bináris keresés. >> Fogalmam sincs, hogy mi a bináris keresés.

250
00:14:54,710 --> 00:14:58,030
>> [Hallgató] Indítsa el a közepén. >> Indítása a közepén. Oké. Szóval hátha tudunk eljutni.

251
00:14:58,030 --> 00:15:02,580
Tehát, ha ahelyett, amit mondtam kezdetét a középső, megy előre, és nyissa ki a középső ajtót.

252
00:15:02,580 --> 00:15:04,580
Van 8 őket, szóval kell majd önkényesen választani az egyik

253
00:15:04,580 --> 00:15:09,800
kissé balra vagy jobbra. Oké. 7! [Taps] Very nice.

254
00:15:09,800 --> 00:15:11,410
Oké, de hol voltak megyünk ezzel?

255
00:15:11,410 --> 00:15:14,990
Tegyük fel, csak azért, hogy megtörje a nyakkendő akkor kezdett itt

256
00:15:14,990 --> 00:15:16,670
mert ez is történhetett volna is.

257
00:15:16,670 --> 00:15:19,540
Mi csak véletlenül tudom, hogy 7 volt. Szóval ez a 13.

258
00:15:19,540 --> 00:15:21,980
Tehát, ha ők válogatják, és mi csak most kezdődött el a közepén,

259
00:15:21,980 --> 00:15:24,600
mi lenne az optimális következő lépés lett volna?

260
00:15:24,600 --> 00:15:27,740
Menj a bal oldalon. És itt jön a telefonkönyv példa újra.

261
00:15:27,740 --> 00:15:30,130
Ha 13 van, és tudjuk, hogy a sorrend,

262
00:15:30,130 --> 00:15:33,900
akkor az összes ilyen darab papír érdektelen a számunkra most

263
00:15:33,900 --> 00:15:37,400
mert mi már tudjuk, hogy 7 kell, hogy legyen a bal

264
00:15:37,400 --> 00:15:39,510
Ha ezek a számok vannak rendezve, és találtunk 13.

265
00:15:39,510 --> 00:15:42,500
>> Szóval, mi a következő lépés itt? >> Ugrás a bal oldalon. >> Oké, jó.

266
00:15:42,500 --> 00:15:45,080
Akkor menj balra, és - várj, hé, hé, hé. Ez csalás.

267
00:15:47,140 --> 00:15:51,350
Szóval találat 7, de mi volt az algoritmus már csak alkalmazni?

268
00:15:51,350 --> 00:15:56,450
Indítsa el a közepén. >> Jó. Szóval mi a logikus kiterjesztését ugyanezen ötlet?

269
00:15:56,450 --> 00:15:58,970
Ó, csak ezeket. >> Pontosan. >> Szóval itt kezdődnek. >> Jó.

270
00:15:58,970 --> 00:16:02,020
Tehát most mentünk kissé balra újra. Ez 3.

271
00:16:02,020 --> 00:16:05,310
De az érdekes elvihető most melyik ugye nem kell törődni?

272
00:16:05,310 --> 00:16:08,040
Ezek a 2. >> Ezek a 2. Így most ez lehet menni, ez az egy is elmegy.

273
00:16:08,040 --> 00:16:12,330
Most a probléma, hogy volt 8 akkori 4-es méretű most 2-es méret.

274
00:16:12,330 --> 00:16:16,430
Mi megvagyunk elég közel. Ismét megy a közepére e 2 elemeket.

275
00:16:16,430 --> 00:16:20,430
>> Oké. Szóval ez a fajta sajnálatos, hogy most mi lesz mindig marad, mert mi vagyunk a lefelé kerekítés.

276
00:16:20,430 --> 00:16:25,150
De ez rendben van, mert most dobjuk ezt el, és minden mást, így nekünk csak 7.

277
00:16:25,150 --> 00:16:30,490
Adjunk a tapsot. Találtunk 7 újra. [Taps] Oké. Persze.

278
00:16:30,490 --> 00:16:32,220
Várj, mindössze további 1 másodpercig.

279
00:16:32,220 --> 00:16:36,630
Jóllehet ez a következő folyamat a fajta egy kicsit tovább tartott, mint azt érezte volna,

280
00:16:36,630 --> 00:16:40,150
őszintén szólva, az első ösztöne volt a legjobb, igaz? Találtunk 7 azonnal.

281
00:16:40,150 --> 00:16:46,740
De mi lett volna találat 7 gyorsabb, nem számít, mit, ebben a példában szemben ezt

282
00:16:46,740 --> 00:16:50,100
mert ha a számok minden rendezve, akárcsak az oldalakat a telefonkönyv,

283
00:16:50,100 --> 00:16:54,580
Ön valóban vágjuk fele a probléma ki újra és újra és újra.

284
00:16:54,580 --> 00:16:56,740
És ez nem annyira egyszerű, hogy ez a mindössze 8 számot

285
00:16:56,740 --> 00:17:00,100
szemben a 1000 oldalas telefonkönyv, ahol valóban látni vizuális,

286
00:17:00,100 --> 00:17:03,120
de ebben az esetben itt amikor Sean kerestek és 7,

287
00:17:03,120 --> 00:17:06,020
hány lépést a legrosszabb esetben lenne volna neki? >> [Hallgató] 7.

288
00:17:06,020 --> 00:17:11,670
7 a legrosszabb eset. Nos, a legrosszabb esetben sem, ha van 7 8 ajtó van.

289
00:17:11,670 --> 00:17:13,440
Ez volna neki 8 lépésben.

290
00:17:13,440 --> 00:17:18,170
>> Szóval, ha van n ajtókat, talán volna Sean egy pár évvel ezelőtt n lépéseket.

291
00:17:18,170 --> 00:17:21,520
Most, a te esetedben, Alex, tekintettel arra, hogy ezek a számok vannak rendezve -

292
00:17:21,520 --> 00:17:25,130
és mi lehet a fajta e arra következtetnek, ahol voltunk eddig ebben a történetben -

293
00:17:25,130 --> 00:17:28,300
mi a működési ideje Alex látna intelligens algoritmus

294
00:17:28,300 --> 00:17:30,770
indulunk ki, a középső, majd ismétlődő?

295
00:17:30,770 --> 00:17:36,490
[Hallgató] 3. >> Így lesz 3, durván, ha megy 8-4 to 2-1.

296
00:17:36,490 --> 00:17:40,660
Szóval 3 lépés, vagy még általánosabban, ez log n újra.

297
00:17:40,660 --> 00:17:43,380
Minden alkalommal, amikor éppen felére csökkentését és a felére csökkentését, valamint felére csökkentését és a felére csökkentését,

298
00:17:43,380 --> 00:17:45,290
ez egy kifejezése ez a gondolat a log n.

299
00:17:45,290 --> 00:17:48,140
És így volna, csak 3 lépés, és valóban meg is tett

300
00:17:48,140 --> 00:17:50,890
amint kinyitotta az ajtót, és a felére csökkentése felére csökkentését,

301
00:17:50,890 --> 00:17:53,770
mivel ez volna Sean mintegy 7 vagy 8 lépéseket.

302
00:17:53,770 --> 00:17:56,330
Szóval köszönöm, hogy velünk ebben az évben. >> Köszönöm. Örülök, hogy találkoztunk.

303
00:17:56,330 --> 00:18:00,170
Köszönöm Alex. Hasonlóképpen >>. [Taps]

304
00:18:00,170 --> 00:18:02,150
>> Mi akkor az igazi hatása ez?

305
00:18:02,150 --> 00:18:06,050
Most képzeld el, hogy ez nem 8 ajtó, ami, őszintén szólva, mindannyian találtam valamit

306
00:18:06,050 --> 00:18:10,430
mögött, 8 ajtó elég gyorsan csak a szakadás a darab papír és megy a mi ösztönök.

307
00:18:10,430 --> 00:18:14,430
De mi van, ha ez egy millió ajtókat? Mi van, ha 4000000000 ajtókat?

308
00:18:14,430 --> 00:18:19,630
Abban az esetben, 4 milliárd ajtó, te tényleg szeretne majd menni Alex-algoritmus,

309
00:18:19,630 --> 00:18:23,150
bináris keresést kezdünk hívó, vagy oszd meg és uralkodj, még általánosabban,

310
00:18:23,150 --> 00:18:25,220
ahol tartod felére csökkentését, és felére csökkenteni a problémát,

311
00:18:25,220 --> 00:18:30,510
mert ha 4000000000 ajtó, hányszor tudsz chop 4 milliárd félidőben?

312
00:18:30,510 --> 00:18:33,870
[Hallgató] 32. >> Ez valójában 32. Akkor ezt oldani egy darab papír, vagy a fejedben.

313
00:18:33,870 --> 00:18:38,490
Menj 4000000000-2000000000 to 1 milliárd fél milliárd 250 millió, pont, pont, pont.

314
00:18:38,490 --> 00:18:41,620
És ha te meg a matek, fogsz kapni valóban 32,

315
00:18:41,620 --> 00:18:44,950
és a ténylegesen kapcsolódik számítógép-tudomány, mert általában számolnak 2 hatványai.

316
00:18:44,950 --> 00:18:47,600
2 a 32 történetesen 4000000000.

317
00:18:47,600 --> 00:18:51,440
Szóval van egy csomó releváns ilyen típusú 2 hatványai számítástechnika.

318
00:18:51,440 --> 00:18:55,120
>> De mi a helyzet 8000000000? Hány lépés az, hogy fog tartani, ha van 8000000000 ajtókat?

319
00:18:55,120 --> 00:19:00,350
[Hallgató] 33. Szóval >> 33. Mi van, ha 16000000000 ajtókat? Hány lépés az, hogy fog tartani?

320
00:19:00,350 --> 00:19:05,020
[Hallgató] 34. >> 34. Mi lehet a fajta folytassa ezt orrvérzésig. De ez egy hatalmas dolog.

321
00:19:05,020 --> 00:19:09,430
Lehet bevezetni milliárd látna bemenetek a probléma, de nem nagy ügy,

322
00:19:09,430 --> 00:19:14,140
csak hogy további 1 falatot belőle, és így ad nekünk valami hasonló bináris keresés

323
00:19:14,140 --> 00:19:15,920
vagy oszd meg és uralkodj, általában.

324
00:19:15,920 --> 00:19:17,990
De én vagyok a fajta csalás, igaz?

325
00:19:17,990 --> 00:19:22,410
Abban az esetben, Alex algoritmus, volt előnyt Sean.

326
00:19:22,410 --> 00:19:27,780
Tudta, hogy ezek a számok voltak rendezve, de Alex nem kellett rendezni őket magának.

327
00:19:27,780 --> 00:19:30,520
Én előre jött a táblához, és gondoskodott arról, hogy milyen

328
00:19:30,520 --> 00:19:33,670
hogy felhívta őket arra, rendezetten, aztán fedett őket papírra.

329
00:19:33,670 --> 00:19:35,850
De milyen sok munka volt, hogy engem?

330
00:19:35,850 --> 00:19:40,110
Ha már elindult a számokat valamilyen látszólag véletlen sorrendben -

331
00:19:40,110 --> 00:19:43,320
ebben az esetben ezek egyszerűbb számokat 1-től 8 itt -

332
00:19:43,320 --> 00:19:46,090
hogyan megy a válogatás ezeket az értékeket?

333
00:19:46,090 --> 00:19:52,530
Ha volt egy ember megkapja ezt a feladatot, milyen intuitív megközelítés szedése

334
00:19:52,530 --> 00:19:54,800
válogatásnak egy csomó számok?

335
00:19:54,800 --> 00:19:57,050
Ezek a dolgok rakták ki, mint a puzzle darabkái. Igen.

336
00:19:57,050 --> 00:19:59,950
>> [Hallgató] I venné az egyes számot, és hasonlítsa össze a minden egyes

337
00:19:59,950 --> 00:20:03,180
és menj balra. >> Oké, jó.

338
00:20:03,180 --> 00:20:05,720
Tehát hogy egyes szám, hasonlítsa össze az egyik mellette,

339
00:20:05,720 --> 00:20:09,610
és aztán csak folyamatosan mozog a listában, milyen rejiggering dolgok, ahogy megy.

340
00:20:09,610 --> 00:20:13,800
Tehát itt van egy esély talán még néhány emberek belekeveredni.

341
00:20:13,800 --> 00:20:16,290
Ne már 8 további önkéntesek, akik szeretnék, hogy jöjjön fel?

342
00:20:16,290 --> 00:20:23,950
Egy kicsit kevesebb nyomást, mivel nem te vagy az egyetlen. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Gyere le. Ti lesznek a számokat 1-től 8.

344
00:20:28,190 --> 00:20:36,050
Lássuk, ha nem tudjuk ezt válogatás Alex sok ugyanúgy csináltam előre.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Menj előre, és ha lenne, sorban a színpadra a zeneállvány és ide

347
00:20:40,760 --> 00:20:44,960
ugyanabban a sorrendben, mint a dia a képernyőn.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Majd működik, a következő példa. Oh, várj, várj. Itt vagyunk. Várj.

350
00:20:53,230 --> 00:20:57,570
A következő példa most. Tessék. Szám 8. Gyere fel.

351
00:20:57,570 --> 00:21:00,270
Rendben van. Sort magatokat eszerint.

352
00:21:00,270 --> 00:21:03,620
Csúsztassa egy kicsit oldalra a zene itt állni.

353
00:21:03,620 --> 00:21:12,310
Tehát 4, 2, 6 - kap oda, ide, ott - 3.

354
00:21:12,310 --> 00:21:17,570
Igen. Oké. Menj ide. Nem, te maradj ott.

355
00:21:17,570 --> 00:21:21,840
Igen, ott. Nem tévedek. Ott van. Jó, nagyon jó. Oké.

356
00:21:21,840 --> 00:21:24,930
És most nézzük rendezni őket növekvő sorrendben.

357
00:21:24,930 --> 00:21:26,210
>> Hogyan kezdjen csinálja ezt?

358
00:21:26,210 --> 00:21:28,630
Az algoritmus, amely javasolta egy perce volt, miért nem csak összehasonlítani

359
00:21:28,630 --> 00:21:31,970
Az emberek, akik a fajta egymás mellett, majd rögzítse az esetleges hibákat,

360
00:21:31,970 --> 00:21:33,540
mozgó balról jobbra.

361
00:21:33,540 --> 00:21:36,580
Tehát itt van 4 és 2, nyilvánvalóan elromlott. Hadd csere téged. Oké.

362
00:21:36,580 --> 00:21:40,760
Úgyhogy most megyek mozgatni le a pályáról. 4 és 6, nope. [Nevetés]

363
00:21:40,760 --> 00:21:45,010
6 és 8, nagyon jó. 8 és 1, hadd cserélni srácok. Rendben van.

364
00:21:45,010 --> 00:21:48,030
Szóval 8 és 3, csere srácok.

365
00:21:48,030 --> 00:21:52,280
8 és 7, hadd cserélni srácok. 5 és 8, kiváló.

366
00:21:52,280 --> 00:21:54,820
Adok egy rendezett listát.

367
00:21:54,820 --> 00:21:56,860
Rendben van. Tehát nem egészen.

368
00:21:56,860 --> 00:22:01,180
De jobb, mert a nagyobb szám - esetben a 8 -

369
00:22:01,180 --> 00:22:04,030
már fajta buborékoltatunk fel balról át a jobbra.

370
00:22:04,030 --> 00:22:08,010
Szóval 1-et közülük van, de úgy érzi, mintha ez nem igazán oldja meg a problémát.

371
00:22:08,010 --> 00:22:11,150
>> Szóval mit javasolna mi a következő lépés? >> [Hallgató] Tartsuk csinálja. >> Mi folyamatosan csinálja.

372
00:22:11,150 --> 00:22:13,740
És észre újra, mi meg a dolgokat azzal, csak úgy, minden ember

373
00:22:13,740 --> 00:22:17,180
egyfajta intelligens intézkedik magukat alapuló kép

374
00:22:17,180 --> 00:22:19,040
de most már, hogy sokkal módszeres.

375
00:22:19,040 --> 00:22:21,510
Kell lennünk algoritmikus róla, mintha írunk kód -

376
00:22:21,510 --> 00:22:23,520
Ebben az esetben a szóbeli pszeudokód.

377
00:22:23,520 --> 00:22:26,040
Szóval hadd próbáljam meg újra. Ez nagyon jól működött. Ez nem oldja meg.

378
00:22:26,040 --> 00:22:30,400
De amikor kétségbe, csak próbálja és próbálja újra. Tehát 2 és 4, nem segít többé.

379
00:22:30,400 --> 00:22:33,200
4 és 6. Ah! 6 és 1, valamivel jobb most.

380
00:22:33,200 --> 00:22:39,740
6 és 3, jó. 6. és 7, 7 és 5, 7 és 8, a jó.

381
00:22:39,740 --> 00:22:44,060
És tudod, én valószínűleg figyelmen kívül 8 most már, mert ő az a lista végére.

382
00:22:44,060 --> 00:22:47,250
Talán nem kell aggódnia, hogy valaki megy mellette.

383
00:22:47,250 --> 00:22:49,240
De lássuk, hogy ez egy biztonságos feltételezés.

384
00:22:49,240 --> 00:22:52,340
Most lista - rohadt - nem válogatják szét. Próbáljuk meg újra.

385
00:22:52,340 --> 00:22:56,440
SO 2 és 4, 4 és 1, 4 és 3.

386
00:22:56,440 --> 00:22:59,230
4 és 6, jó. 6 és 5, jó.

387
00:22:59,230 --> 00:23:04,890
6, 7, és 8, a jó. De a nyilatkozat, akkor csak meg itt, és most meg itt most?

388
00:23:04,890 --> 00:23:07,770
[Hallgató] Igen. >> Igen?

389
00:23:07,770 --> 00:23:11,160
Mi lenne, ha egyikőtök volt a 9-es számú végig ott?

390
00:23:11,160 --> 00:23:13,640
Ez lett volna rendezve. >> Jó. Ez lett volna rendezve az első alkalommal kb.

391
00:23:13,640 --> 00:23:16,050
Jó. Akkor menjünk vissza. Már majdnem ott vagyunk.

392
00:23:16,050 --> 00:23:22,800
Az 1. és 2., a 2. és 3, 3 és 4, 4 és 5, 5 és 6, 6 és 7, 7 és 8.

393
00:23:22,800 --> 00:23:26,640
>> Én kész, de most megint én vagyok a számítógép csak csinálni, amit én mondtam, hogy nem,

394
00:23:26,640 --> 00:23:30,120
és az egyetlen emléke most, hogy én valójában csak tettem egy kis munka.

395
00:23:30,120 --> 00:23:31,700
Valami megváltozott itt.

396
00:23:31,700 --> 00:23:37,100
Szóval még technikailag nem erősítette vizuálisan vagy algoritmikusan hogy ez a lista valóban rendezve.

397
00:23:37,100 --> 00:23:40,720
Szóval csak a jó intézkedés, csak hogy anális erről, csináljuk ezt az 1 több időt.

398
00:23:40,720 --> 00:23:44,040
Így az 1. és 2., a 2. és 3., 3. és 4.. És tudod mit?

399
00:23:44,040 --> 00:23:46,190
Csak jó intézkedés, megyek, hogy nyomon követhesse a kezem ebben az időben

400
00:23:46,190 --> 00:23:51,110
mennyi swap teszek, csak azért, hogy tudom, hogy mennyi munka, amit valójában tenni.

401
00:23:51,110 --> 00:23:56,930
A 3. és 4, 4 és 5, 5 és 6, 6 és 7, 7 és 8. Nincs swap.

402
00:23:56,930 --> 00:24:00,800
Szóval most azt törvényesen egy idióta, hogy ezt újra

403
00:24:00,800 --> 00:24:03,330
mert ha nem dolgozott ezen keresztül át az emberek,

404
00:24:03,330 --> 00:24:06,710
akkor egyértelmű, hogy ez fog történni újra, ha egyikük sem valami véletlenszerűen

405
00:24:06,710 --> 00:24:10,410
adversarially mozgó maguk körül. Így most tudom abbahagyni.

406
00:24:10,410 --> 00:24:15,120
Most feltenni a kérdést, hogy sok munka volt ez valójában engem?

407
00:24:15,120 --> 00:24:18,260
Hány lépés volt, hogy az el? >> N négyzeten.

408
00:24:18,260 --> 00:24:20,400
Igen, n faragva. Hol kapsz n négyzetes származik?

409
00:24:20,400 --> 00:24:22,660
Be kell, hogy ellenőrizze minden egyes száma -

410
00:24:22,660 --> 00:24:26,530
Van n számokat, és van, hogy ellenőrizze minden egyes szám a többi n számokat.

411
00:24:26,530 --> 00:24:29,030
Jó. >> Szóval ez n faragva. >> Jó.

412
00:24:29,030 --> 00:24:31,060
>> Tehát úgy érzi, hogy nagyon is n négyzetes, ugye?

413
00:24:31,060 --> 00:24:33,820
Van n ezek a srácok, 8 konkrétan ebben az esetben,

414
00:24:33,820 --> 00:24:37,590
de minden alkalommal mentem keresztül ezen a listán voltam összehasonlítva az első, aki ellen a második,

415
00:24:37,590 --> 00:24:39,650
a második ellen a harmadik újra és újra és újra,

416
00:24:39,650 --> 00:24:42,450
és amikor megkaptam a végére, mit tettem? Én redid meg.

417
00:24:42,450 --> 00:24:46,280
Tehát ha általánosítani ezt a magyarázatot, már n emberek

418
00:24:46,280 --> 00:24:51,090
és én vagyok így, nyilván, 8 lépés, n lépéseket, minden alkalommal, amikor megyek keresztül algoritmus.

419
00:24:51,090 --> 00:24:56,070
De hányszor a legrosszabb esetben nem tudom, hogy menjen át ezt a listát az emberek?

420
00:24:56,070 --> 00:24:59,370
[Hallgató] N-szer. Valószínűleg >> n, igaz, mert a legrosszabb esetben

421
00:24:59,370 --> 00:25:03,410
Mi valószínűleg a legrosszabb esetben elrendezése ezek a srácok a get-go?

422
00:25:03,410 --> 00:25:06,520
Ha ők teljesen fordított sorrendben

423
00:25:06,520 --> 00:25:09,310
mert csak tegyük fel, szellemileg, let's - Mi a neve? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Oké. Szóval Bowen, gyere ide egy pillanatra.

425
00:25:12,510 --> 00:25:16,150
>> Tegyük fel, hogy Bowen volt itt elején az algoritmus,

426
00:25:16,150 --> 00:25:19,790
és nem tudom, mi mindenki más, de itt Bowen szerint ez az algoritmus -

427
00:25:19,790 --> 00:25:23,820
és ha azt szeretnénk, hogy csak sétáljon velem - fog buborék fel, mint ahogy az első alkalommal,

428
00:25:23,820 --> 00:25:25,740
egészen a végéig.

429
00:25:25,740 --> 00:25:29,400
De tegyük fel, hogy az adott személy mellett Bowen volt a 7-es szám.

430
00:25:29,400 --> 00:25:33,450
Van, hogy menjen vissza, és kap a 7, ami azt jelenti, hogy el kell menni egészen vissza ide.

431
00:25:33,450 --> 00:25:36,980
Most van, hogy ugyanezen séta a személy, aki a 7-es számú.

432
00:25:36,980 --> 00:25:40,140
De mi van, ha majd 6-os szám mellett volt neki is?

433
00:25:40,140 --> 00:25:42,180
Aztán vissza kell mennem, és kap 6.

434
00:25:42,180 --> 00:25:46,490
Szóval megint minden iterációs e ciklus beszélek az egyes n emberek,

435
00:25:46,490 --> 00:25:50,090
és talán van, hogy n e séták hogy győződjön meg arról vagyok húzva

436
00:25:50,090 --> 00:25:53,760
minden a legnagyobb elem vissza, és vissza, majd vissza a legvégén a listán.

437
00:25:53,760 --> 00:25:58,230
Tehát n dolgok n-szer csak n-szer n vagy n faragva.

438
00:25:58,230 --> 00:26:02,050
>> Tehát itt már van egy algoritmus, amely már nem n, hogy már nem log n,

439
00:26:02,050 --> 00:26:04,820
ez valóban rosszabb, mint bármi, amit eddig csináltunk.

440
00:26:04,820 --> 00:26:09,840
Szóval Alex ilyen szerencsés az, hogy én mindent megtettem a munka látszólag előre neki,

441
00:26:09,840 --> 00:26:14,690
az összes drága munkát, hogy tudta élvezni ebben a bináris keresési algoritmust,

442
00:26:14,690 --> 00:26:16,420
amely a log n.

443
00:26:16,420 --> 00:26:18,240
De ez összhangban van a hétfői témát.

444
00:26:18,240 --> 00:26:23,260
Adtunk egy kicsit több helyet, szoktuk több bit, annak érdekében, hogy felgyorsítsa a működési idő.

445
00:26:23,260 --> 00:26:26,170
Annyira, mint itt van ez a trade-off közötti térben és időben,

446
00:26:26,170 --> 00:26:31,060
ott azt is csak lenni kompromisszumok között eltöltött idő elöl a fajta a dolgok kész

447
00:26:31,060 --> 00:26:35,000
és ténylegesen végrehajtó algoritmus, mint a keresés. Próbáljunk egy másikat.

448
00:26:35,000 --> 00:26:39,050
Ha ti nem bánja csak gyorsan átrendezve magatokat egyeznie újra,

449
00:26:39,050 --> 00:26:42,240
próbáljunk valami kicsit más, ha ez nem olyan egyszerű

450
00:26:42,240 --> 00:26:45,760
mint csak rögzíti az összes páros hibákat, ami szuper intuitív.

451
00:26:45,760 --> 00:26:48,150
Nézzünk inkább egy kicsit szándékos és ezt.

452
00:26:48,150 --> 00:26:51,010
Ez is azt javaslom, valószínűleg elég intuitív.

453
00:26:51,010 --> 00:26:55,070
>> Nézzük válasszuk ki a legkisebb személyt a listáról újra és újra. Szóval itt vagyunk.

454
00:26:55,070 --> 00:26:57,350
4, te vagy a legkisebb ember, akivel így láttam eddig,

455
00:26:57,350 --> 00:27:00,520
így fogok emlékezni, hogy mentálisan, egyszerűen mutatva, hogy most.

456
00:27:00,520 --> 00:27:05,020
2. Ó! Felejtsd el a 4-es számú. Most találtam az új legkisebb elem a listában.

457
00:27:05,020 --> 00:27:07,410
Fogok a fajta emlékszem. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ó! 1. Viszontlátásra. Tehát most fogok emlékezni az 1.

459
00:27:11,190 --> 00:27:14,790
Tudjuk, hogy 1-es a legkisebb, de én vagyok a számítógépet. Mi van, ha van egy 0?

460
00:27:14,790 --> 00:27:17,140
Mi van, ha a -1? Meg kell tartani fog.

461
00:27:17,140 --> 00:27:20,990
Így 3, 7, 5, nope. Oké. Szóval, 1-es szám volt a legkisebb.

462
00:27:20,990 --> 00:27:23,640
Hadd válassza ki Ön a listáról - we'll menni ezen a módon -

463
00:27:23,640 --> 00:27:27,760
és tegye meg önkényesen elején a lista.

464
00:27:27,760 --> 00:27:29,740
Na, várj egy percet. Valahogy csalt.

465
00:27:29,740 --> 00:27:34,010
Ha ezek a srácok nem képviselnek egy listát 8 fős, hanem egy tömb,

466
00:27:34,010 --> 00:27:37,050
8 darabokat összefüggő memóriaterületet - nem bánja megerősítéséről vissza egy pillanatra?

467
00:27:37,050 --> 00:27:39,060
Itt tényleg nincs hely neked itt.

468
00:27:39,060 --> 00:27:41,840
Szóval hogyan tesszük helyet - mi a neve? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Hogyan teszünk helyet Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Mi mozog a n, amelyek előttem. >> Oké.

471
00:27:46,760 --> 00:27:48,850
Így tudnánk mozgatni az n, akik előtte,

472
00:27:48,850 --> 00:27:52,400
így ha akartok, hogy 1 a szándékos, drámai lépést a bal oldalon.

473
00:27:52,400 --> 00:27:57,000
Mindannyian tette, hogy egyszerre, de a múltkor írtam egy kódot,

474
00:27:57,000 --> 00:27:59,740
nem tudja rendezni a mozgás sok dolgot egyszerre.

475
00:27:59,740 --> 00:28:02,450
Megtehetjük azt egy hurok, mozgó mindenki egyszer egy időben.

476
00:28:02,450 --> 00:28:04,340
Tehát, ha ti nem bánja lépett vissza a jobb oldalon,

477
00:28:04,340 --> 00:28:07,230
és Sammy, ha tudna lépést vissza, mert még mindig nincs hely az Ön számára,

478
00:28:07,230 --> 00:28:11,420
Most csináljuk ezt. Hol volt Sammy egy pillanattal ezelőtt? Ott van.

479
00:28:11,420 --> 00:28:16,140
Szóval van egy rés van. Szóval lehet beköltözni Sammy helyszínen.

480
00:28:16,140 --> 00:28:20,580
Most következő személyt, és most következő személyt, most következő személyt. Most szoba Sammy.

481
00:28:20,580 --> 00:28:23,490
Most, hogy valaki a közönség soraiból -, hogy jó volt, hogy helyes volt,

482
00:28:23,490 --> 00:28:27,070
úgy éreztem, egy kicsit időigényes - mi a gyorsabb? Igen.

483
00:28:27,070 --> 00:28:29,440
[Hallgató] Egy új tömb? >> Mi ez? >> [Hallgató] Egy új tömb? >> Oké, jó.

484
00:28:29,440 --> 00:28:33,200
>> Így összhangban e téma csak kompromisszumok, miért nem csak, hogy egy új tömb

485
00:28:33,200 --> 00:28:36,570
 és azután Sammy kerül úszás térben előtt ezeknek az embereknek, például,

486
00:28:36,570 --> 00:28:39,600
és mi is csak elkezd kitöltésével egy új tömb összesen. Ez is működni fog.

487
00:28:39,600 --> 00:28:42,450
De nem érdekel kiadások több helyet ma. Mi a másik megközelítés?

488
00:28:42,450 --> 00:28:46,630
[Hallgató] Swap. >> Oké. Mi is csak csere e 2 srácok. Mi a neve?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Szóval Mario, te voltál a jelenleg itt van.

490
00:28:49,390 --> 00:28:52,480
Sammy, tudsz biztonsági másolatot csak egy pillanatra? Mario itt volt.

491
00:28:52,480 --> 00:28:55,830
Jelenleg nincs hely többé, úgyhogy ha nem bánja majd, ha Sammy van,

492
00:28:55,830 --> 00:29:02,430
berakunk Sammy itt, és most azt állítják, hogy Sammy csere művelet sokkal gyorsabb.

493
00:29:02,430 --> 00:29:06,370
Sikerült 1 művelet csere ezek a srácok, vagy talán a 2 cserélni ezeket a fickókat,

494
00:29:06,370 --> 00:29:11,210
de nem tettünk 1, 2, 3, 4, hogy a jobban érzi magát. Na, várj egy percet.

495
00:29:11,210 --> 00:29:14,660
Valahogy tett a probléma rosszabb, mert 4-es számú kedves volt, közel az elején.

496
00:29:14,660 --> 00:29:19,470
Most 4-es szám egy kicsit közelebb e célból, de nem igazán tudja, vagy érdekel.

497
00:29:19,470 --> 00:29:23,330
Tehát ez csak balszerencse, hogy a 4-es szám egy kicsit távolabb a szánt helyen.

498
00:29:23,330 --> 00:29:25,110
Szóval most ismételje meg ezt algoritmus.

499
00:29:25,110 --> 00:29:28,410
>> Ahhoz, hogy újra bedugni, amíg a történet, minden, amit tett, séta a listán

500
00:29:28,410 --> 00:29:31,130
keresi a legkisebb számozott személy.

501
00:29:31,130 --> 00:29:34,530
Tehát most csináljuk újra. Nem kell aggódni Sammy többé.

502
00:29:34,530 --> 00:29:37,590
Mi is csak ide. Ó! 2. szám. Ez elég kevés.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Oké, jó.

504
00:29:41,180 --> 00:29:43,770
És szerencsére, a véletlen, nem kell mozgatni - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie mert ő az ő helyén most.

506
00:29:45,910 --> 00:29:48,110
Csináljuk újra, és figyelmen kívül hagyja ezeket a 2 srácok.

507
00:29:48,110 --> 00:29:50,460
6. Ez elég kevés. Ó! 8 határozottan nagyobb.

508
00:29:50,460 --> 00:29:53,410
4. Nézzük összpontosít 4. Ó! 3 még jobb.

509
00:29:53,410 --> 00:29:58,290
7 és 5. Szóval, mit csináljunk most - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Nézzük csere őt 6-os szám.

511
00:30:00,250 --> 00:30:03,570
Tehát, ha 6 és 3 szeretném cserélni,

512
00:30:03,570 --> 00:30:07,320
voltunk már ilyen ütött szerencsés az, hogy a 6 közelebb hol kell lennie,

513
00:30:07,320 --> 00:30:10,300
de ez csak véletlen egybeesés van. Úgyhogy most ide.

514
00:30:10,300 --> 00:30:13,430
8 egy nagyon kis számban. Ó! 4 kisebb.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Mit fogunk most csinálni? Swap >>. >> Pontosan.

516
00:30:17,130 --> 00:30:19,010
Tehát most csináljuk ezt a fajta gyorsabb.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Amennyiben ez 5 menni? Jó. Oké.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 kap, hogy maradjon, ahol van. Mi a neve? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie kap, hogy maradjon, ahol van. 7 kerül - Lássuk csak. 7, 8. Oké.

520
00:30:31,770 --> 00:30:35,100
Így 7 lesz, hogy maradjon, ahol van. Mi a neve? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Szóval Amna kap szállást, hol van, és a 8-as szám már ahol most kell.

522
00:30:39,670 --> 00:30:43,960
Oké, jó. Érzés mi csak létre munkát magunknak itt, mégis.

523
00:30:43,960 --> 00:30:47,440
Mi végül a futási ideje ez az algoritmus?

524
00:30:47,440 --> 00:30:51,900
Ha végiggondoljuk ezeket az embereket nem 8, hanem n? >> Ez n.

525
00:30:51,900 --> 00:30:55,440
Ez n lépéseket, de mi ellenőrzése minden egyes alkalommal.

526
00:30:55,440 --> 00:30:57,570
Oké. N de te ellenőrzése minden egyes alkalommal?

527
00:30:57,570 --> 00:31:03,450
Oké, de ha ez n lépéseket, nem voltam képes rendezni Önnek csak lesz 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Oké, ez egy nagy különbség.

529
00:31:05,590 --> 00:31:08,050
Tehát n kockás miért? Mi történik valójában?

530
00:31:08,050 --> 00:31:12,130
Van n ember ebben a listában, de megtalálni a legkisebb ember a listán

531
00:31:12,130 --> 00:31:16,200
a legrosszabb esetben, hány lépést kell még tenni? N. >>

532
00:31:16,200 --> 00:31:19,160
>> N, igaz, mert a legrosszabb esetben az 1-es szám az egész az út ott,

533
00:31:19,160 --> 00:31:20,990
így azt kell menj vele.

534
00:31:20,990 --> 00:31:25,500
És akkor, amikor végre észre, 1 volt a legkisebb, akkor elég gyorsan cserélni őket.

535
00:31:25,500 --> 00:31:28,450
De most el kell kezdeni az elejétől, és keresse meg kicsoda?

536
00:31:28,450 --> 00:31:31,980
A következő legkisebb ember, amely 2. Amennyiben a legrosszabb esetben 2?

537
00:31:31,980 --> 00:31:34,320
Ó, Istenem. Ez egészen ide a végén.

538
00:31:34,320 --> 00:31:37,000
Szóval most már csak tett egy lépést n, egy másik n lépéseket.

539
00:31:37,000 --> 00:31:41,200
És ha van n az emberek és a legrosszabb esetben a legkisebb személy n lépésre,

540
00:31:41,200 --> 00:31:45,230
ez megint n-szer n, és így megint van n faragva.

541
00:31:45,230 --> 00:31:47,280
Ez nem érzi túl jól.

542
00:31:47,280 --> 00:31:52,150
És valóban, még a legjobb esetben - tegyük fel, hogy elindul rendezve -

543
00:31:52,150 --> 00:31:59,080
hány lépést tart nekem ezt az algoritmust, hogy rendezni ezeket n az emberek?

544
00:31:59,080 --> 00:32:01,010
N kockás. >> Hallottam n faragva. Miért n kockás?

545
00:32:01,010 --> 00:32:05,240
Mert még mindig van, hogy ellenőrizze minden egyes alkalommal. >> Igen.

546
00:32:05,240 --> 00:32:08,060
És meg kell cserélni őket. >> Annak ellenére, hogy az emberek ilyen mindentudó

547
00:32:08,060 --> 00:32:10,770
abban az értelemben, hogy vizuálisan tudunk csak egyfajta látni, hogy ez van rendezve,

548
00:32:10,770 --> 00:32:12,140
a számítógép nem olyan okos.

549
00:32:12,140 --> 00:32:14,040
Úgy fog kinézni itt és itt és itt,

550
00:32:14,040 --> 00:32:16,610
de ha mit keres a legkisebb elem,

551
00:32:16,610 --> 00:32:22,110
csak tudja, hogy megtalálta a legkisebb elem, amit pont? Ha már a végén.

552
00:32:22,110 --> 00:32:25,880
De ezen a ponton még csak megtalálta a jelenleg legkisebb elem.

553
00:32:25,880 --> 00:32:28,810
Nem feltétlenül tudnak mást arról, az állam a világon.

554
00:32:28,810 --> 00:32:30,880
Szóval kell menni újra és újra és újra.

555
00:32:30,880 --> 00:32:34,880
>> Szóval ezúttal tényleg nézd buta, mert én ellenőrzése, oké, 2, te vagy a legkisebb,

556
00:32:34,880 --> 00:32:37,530
de nem tudom, hogy összességében még.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Oké, jó. 2 volt valóban a legkisebb.

558
00:32:41,090 --> 00:32:43,150
Most megtalálja a következő legkisebb. Oké.

559
00:32:43,150 --> 00:32:48,350
3, te vagy a jelenleg a legkisebb. Lássuk. 4, 5, 6, 7, 8. Oké, szerencséje volt megint.

560
00:32:48,350 --> 00:32:53,170
3 valóban a megfelelő helyen. De megyek, hogy ezt újra és újra és újra.

561
00:32:53,170 --> 00:32:55,990
Hogyan tudjuk ezt valaha is így kicsit jobban?

562
00:32:55,990 --> 00:33:00,120
Ahelyett, hogy az emberek bubble up páros a legkisebbtől a legnagyobbig

563
00:33:00,120 --> 00:33:04,350
és ahelyett, hogy előre és hátra a listában kiválasztja az akkori legkisebb személy,

564
00:33:04,350 --> 00:33:09,780
miért nem inkább be ezeket az embereket egy új listát lépésről lépésre?

565
00:33:09,780 --> 00:33:13,080
Próbáljuk ezt. Most hadd hívjam fel ezt a dolgot beszúrás sort.

566
00:33:13,080 --> 00:33:17,250
Tehát itt vagyunk itt. 1. szám. Nem érdekel senki más ebben a listában.

567
00:33:17,250 --> 00:33:21,310
A célom most az, hogy az 1-es szám elején egy rendezett lista.

568
00:33:21,310 --> 00:33:23,910
És én fogom javasolni, mert én csak 8 darabokat memória,

569
00:33:23,910 --> 00:33:28,670
önkényesen most én vagyok a fal között én állítólag rendezetlen lista,

570
00:33:28,670 --> 00:33:32,740
és bárki, aki a hátam mögött fogom igénypont van rendezve.

571
00:33:32,740 --> 00:33:34,680
Tehát most már 1-es szám.

572
00:33:34,680 --> 00:33:39,240
Azt szeretné szúrni neki az én rendezett lista, szóval én csak fog elmozdulni falamon ide,

573
00:33:39,240 --> 00:33:43,930
és most azt állítják, ez a sorrend, ez a lista a szétválogatás nélküli - legalábbis amennyire én tudom.

574
00:33:43,930 --> 00:33:46,070
Nem látom az összes számot egyszerre.

575
00:33:46,070 --> 00:33:49,000
>> Most történetesen találkozik a 2. Mit csináljak vele?

576
00:33:49,000 --> 00:33:54,380
Én be most a rendezett lista. De észre, milyen könnyű volt.

577
00:33:54,380 --> 00:33:59,650
Csak meg kell nézni. 1. szám ott van. Oh, természetesen 2 megy mellé 1-es szám.

578
00:33:59,650 --> 00:34:03,700
Most mit csináljak, 3? Én be titeket a rendezett lista. De ez szuper volt könnyű.

579
00:34:03,700 --> 00:34:07,250
Ez szuper könnyű, ez szuper könnyű, ez szuper könnyű, szuper könnyű, szuper könnyű.

580
00:34:07,250 --> 00:34:12,790
És most mindent rendezve a hátam mögött, és hány lépést tett, hogy az el?

581
00:34:12,790 --> 00:34:15,620
[Tanulók] N. >> Szóval ez csak n. Szerencsések vagyunk.

582
00:34:15,620 --> 00:34:18,860
Csak n miért? >> [Hallgató] Mivel a lista sorrendje.

583
00:34:18,860 --> 00:34:21,630
A lista már rendezve. Szóval szerencsénk volt.

584
00:34:21,630 --> 00:34:25,639
De Ajánlott egy algoritmust, ebben az időben, hogy kihasználja ezt a fajta szerencse,

585
00:34:25,639 --> 00:34:29,420
hogy a legjobb esetben is, azáltal, hogy nem vesztegeti felesleges időt.

586
00:34:29,420 --> 00:34:31,750
Tehát most már mit fogunk hívni buborék féle

587
00:34:31,750 --> 00:34:33,949
ahol az emberek a fajta buborék felfelé páros.

588
00:34:33,949 --> 00:34:38,100
Most már van választék sort ahol tépni ki a legkisebb ember újra és újra.

589
00:34:38,100 --> 00:34:42,350
És most már a beszúrási sort, ahol egyfajta proaktív az embereket, ha azok tartoznak

590
00:34:42,350 --> 00:34:45,000
az egyre inkább rendezett listát.

591
00:34:45,000 --> 00:34:49,679
Ha tudnánk, a tapsot ezeket a fickókat itt. [Taps]

592
00:34:49,679 --> 00:34:52,310
Nézzük mi 5-perces szünet van.

593
00:34:52,310 --> 00:34:55,139
És mikor jön vissza, akkor fújja az összes ilyen algoritmusok ki a vízből

594
00:34:55,139 --> 00:35:00,260
valami jobb. Rendben van. Köszönöm szépen. Tudod tartani ezeket emlékbe.

595
00:35:01,710 --> 00:35:04,330
Rendben van. Mi vissza.

596
00:35:04,330 --> 00:35:08,420
>> És újra bedugni igazi böjt, mi volt a 3 különböző megközelítések válogatás,

597
00:35:08,420 --> 00:35:13,000
a lényege az volt, hogy arra a pontra, ahol valaki, mint Alex

598
00:35:13,000 --> 00:35:16,930
lehetne keresni számok listájának gyorsabb, mint valaki, mint Sean tudott.

599
00:35:16,930 --> 00:35:19,830
És bár van ilyen egyszerű példákat 8 számot,

600
00:35:19,830 --> 00:35:24,000
akkor kivetíteni könnyedén 8-weboldalakat, 8 milliárd weboldal,

601
00:35:24,000 --> 00:35:26,680
vagy 800.000.000 barátait a Facebook.

602
00:35:26,680 --> 00:35:30,090
Így ezek az algoritmusok természetesen méretezni, hogy az ilyen jellegű értékek,

603
00:35:30,090 --> 00:35:32,300
és az ötletek végül ugyanaz.

604
00:35:32,300 --> 00:35:36,140
Szóval buborék rendezés volt az első, ahol ilyen vezetünk ki a legnagyobb ember

605
00:35:36,140 --> 00:35:39,110
egészen jobbra swapping ember páros.

606
00:35:39,110 --> 00:35:42,040
Aztán volt, mit fogunk hívni kiválasztási sort, ahol egy kicsit szándékosan

607
00:35:42,040 --> 00:35:46,480
tartotta nézi át a listát, kiválasztja a legkisebb számú, újra és újra és újra,

608
00:35:46,480 --> 00:35:49,530
a logikus következménye, amely szerint a listát végül rendezve.

609
00:35:49,530 --> 00:35:53,780
Aztán a harmadik, én ki az embereket a megfelelő helyre,

610
00:35:53,780 --> 00:35:57,720
és csináltunk egy nagyon kitalált példa, hogy a lista már rendezve,

611
00:35:57,720 --> 00:36:01,100
de ez volt az üzenet, hogy a beszúrási sort esetében,

612
00:36:01,100 --> 00:36:02,670
akkor szerencséd lesz.

613
00:36:02,670 --> 00:36:07,930
Ha a számok már rendezve, ez csak akkor fog eljuthat n lépéseket alátámasztani

614
00:36:07,930 --> 00:36:10,870
mivel a kiválasztási sort te egy kicsit csőlátás

615
00:36:10,870 --> 00:36:14,360
és soha ne észre, hogy a lista már rendezve.

616
00:36:14,360 --> 00:36:16,830
Tehát lássuk buborék nemében akció itt.

617
00:36:16,830 --> 00:36:19,590
A következő példában azt mindjárt látni függőleges sávok

618
00:36:19,590 --> 00:36:23,030
amelynek magasságát a számoknak, hogy mi is egyfajta Visualize válogatás történik.

619
00:36:23,030 --> 00:36:26,630
Minél kisebb a sáv, annál kisebb ez a szám, annál nagyobb a sáv, annál nagyobb a szám.

620
00:36:26,630 --> 00:36:28,860
>> És fogunk játszani ezen alapértelmezett sebességet.

621
00:36:28,860 --> 00:36:33,460
Ez lesz mozogni egy kicsit gyorsan most, de a vörös, ami megmutatja 2 bár

622
00:36:33,460 --> 00:36:35,480
összehasonlított egymás mellett.

623
00:36:35,480 --> 00:36:39,520
És ha közelről nézni, hogy mi történik, hogy ha a sávok ki annak érdekében,

624
00:36:39,520 --> 00:36:42,300
a kisebbik lesz mozgatni a bal, a nagyobb egy jobb,

625
00:36:42,300 --> 00:36:44,360
és akkor folyamatosan halad.

626
00:36:44,360 --> 00:36:48,520
Tehát ha ezt újra és újra, észrevenni, hogy a legkisebb rudak

627
00:36:48,520 --> 00:36:51,090
megy folyamatosan araszolnak az utat a bal

628
00:36:51,090 --> 00:36:54,130
és a legnagyobb bárok fog tartani araszolnak az utat a jobb oldalon.

629
00:36:54,130 --> 00:36:58,490
És valóban, mi kezdik látni a minta végig a jobb oldali

630
00:36:58,490 --> 00:37:04,790
mint láttuk, 8, majd végül 7 bugyogott fel a túlsó végén az emberi listáját.

631
00:37:04,790 --> 00:37:08,750
Tehát ez lesz nagyon gyorsan egy kicsit unalmas, úgyhogy hadd megállítani ezt egy pillanatra.

632
00:37:08,750 --> 00:37:10,980
Hadd változik a sebesség sokkal gyorsabb lesz.

633
00:37:10,980 --> 00:37:15,380
Én nem változik az algoritmus, én csak azt, hogy az animáció történik gyorsabb.

634
00:37:15,380 --> 00:37:18,410
Mégis buborék rendezés, azonos algoritmus,

635
00:37:18,410 --> 00:37:21,910
de most már láthatod sokkal gyorsabban, mint a verbális demonstrációs

636
00:37:21,910 --> 00:37:25,900
hogy a legnagyobb elemek valóban bugyogott fel a csúcsra.

637
00:37:25,900 --> 00:37:29,860
>> Mint félretéve, ezek a kis négyzetek a bal alsó és a jobb alsó

638
00:37:29,860 --> 00:37:33,520
csak kis emlékeztető, hogy hány összehasonlítást csinálsz.

639
00:37:33,520 --> 00:37:37,620
De most, tudunk összpontosítani a piramist, ami kialakulóban, és ott megy.

640
00:37:37,620 --> 00:37:41,510
A legkisebb elem a bal oldalon, a legnagyobb a jobb oldalon, és minden más között.

641
00:37:41,510 --> 00:37:44,470
Most ahelyett, hogy egy pillantást kiválasztás sort.

642
00:37:44,470 --> 00:37:47,260
Én megyek előre, és nyomja meg a Stop gombot. Megyünk, hogy egy új random sor bárok.

643
00:37:47,260 --> 00:37:50,930
Selection sort, visszahívás, megy át a listát újra és újra és újra,

644
00:37:50,930 --> 00:37:54,900
kopasztás ki a legkisebb elem. Tehát itt van választás sort.

645
00:37:54,900 --> 00:37:58,390
Úgy néz ki, ott van kevesebb munkával történik most, mert nem vagyunk páronkénti összehasonlításával

646
00:37:58,390 --> 00:38:02,590
de mi csak egyfajta cseresznye szedés a legkisebb elemeket jobbról balra.

647
00:38:02,590 --> 00:38:06,890
Ez volt nagyon kevés időt, így van egy kettősség már.

648
00:38:06,890 --> 00:38:11,820
Csak azért, mert egy algoritmus azt mondta, hogy n négyzetes időt, mint a buborék rendezés

649
00:38:11,820 --> 00:38:16,100
és hasonló kiválasztás sort, ezek tényleg legrosszabb esetben üzemidő.

650
00:38:16,100 --> 00:38:21,790
Például abban az esetben, mondjuk, kiválasztás sort,

651
00:38:21,790 --> 00:38:27,240
Igazából én kiválasztja a legkisebb személy és üzembe őt ide,

652
00:38:27,240 --> 00:38:29,620
akkor csinálom újra, akkor csinálom újra,

653
00:38:29,620 --> 00:38:32,070
de volt egy kis optimalizálási tudtam tenni.

654
00:38:32,070 --> 00:38:35,040
>> Amint költözött szám 1 itt - Sammy ebben az esetben -

655
00:38:35,040 --> 00:38:38,630
mit kell tennem vele ezután? >> [Hallgató] Hagyd őt.

656
00:38:38,630 --> 00:38:40,140
Hagyd őt, ugye? Semmi.

657
00:38:40,140 --> 00:38:44,310
Nem kell, hogy valaha is beszélni Sammy újra, mert ha én kiválasztotta a legkisebb elem

658
00:38:44,310 --> 00:38:48,580
és tedd, hogy itt, miért vesztegeti az idejét, majd a végén a teljes listát?

659
00:38:48,580 --> 00:38:54,590
A következő iteráció hadd ténylegesen mozgatni csak a 2-es számot, csak a 3-as szám.

660
00:38:54,590 --> 00:38:57,640
Így valójában, én nem csinálok dolgokat n n-szer.

661
00:38:57,640 --> 00:39:05,380
Csinálok n dolgokat, akkor n - 1 a dolgokat, akkor n - 2 dolog, akkor n - 3 dolog,

662
00:39:05,380 --> 00:39:07,080
akkor n - 4, pont, pont, pont.

663
00:39:07,080 --> 00:39:09,470
Van egy kis mértani sorozat, ami csak azt jelenti,

664
00:39:09,470 --> 00:39:11,450
te összeadásával egyre kisebb számban.

665
00:39:11,450 --> 00:39:17,940
Nem n + n + n + n de n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
És mi van, hogy általában működik ki, hogy -

667
00:39:21,380 --> 00:39:24,280
Fogom elrontani a fórumon itt egy pillanatra -

668
00:39:24,280 --> 00:39:28,990
ez működni fog ki, hogy valami hasonló n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
ha csak ilyen pillantást a hátán egy matematikai könyv, ahol az összes cheat lapok

670
00:39:31,930 --> 00:39:33,410
a képleteket.

671
00:39:33,410 --> 00:39:37,760
Ha csak hozzá valami n + n - 1 + n - 2, működik ki, hogy valami ilyesmi.

672
00:39:37,760 --> 00:39:42,320
És ha csak egyfajta szorzás ezt ki, ez n négyzeten mínusz n / 2.

673
00:39:42,320 --> 00:39:46,400
Azt hajtogatta n négyzetes, bár, és ez azért van, mert én voltam a fajta vesz egy mentális parancsikont

674
00:39:46,400 --> 00:39:51,950
mert a valóságban, n négyzetnagyságrendű mínusz n osztva 2 valóban a valódi lépésszám

675
00:39:51,950 --> 00:39:55,510
hogy egy algoritmus, mint kiválasztási sort venné, ha valóban számít fel

676
00:39:55,510 --> 00:39:58,800
az összes ilyen összehasonlítások és az összes kicsit elfoglalt munkát csinálunk.

677
00:39:58,800 --> 00:40:03,210
De őszintén szólva, ha n kap, hogy legyen, mint egy millió, vagy milliárd, ki a fene törődik

678
00:40:03,210 --> 00:40:07,160
ha csinálsz egy milliárd squared mínusz egy milliárd osztva 2?

679
00:40:07,160 --> 00:40:09,320
Egy milliárd squared egy hatalmas szám.

680
00:40:09,320 --> 00:40:13,580
Tudod hogy egy milliárd le azt - n. Ez nem olyan nagy ügy.

681
00:40:13,580 --> 00:40:18,770
Tehát minél nagyobb a számokat kap, a kevésbé fontos az alacsonyabb rendű kifejezések.

682
00:40:18,770 --> 00:40:24,230
Kit érdekel, ha osszuk el 2, ha te beszélsz quadrillions számok a lépések?

683
00:40:24,230 --> 00:40:29,710
>> Így általában, számítógépes szakemberek hajlamosak eldobni mindent, de a legnagyobb ciklus,

684
00:40:29,710 --> 00:40:33,140
és mi csak egyfajta egyszerűsítése a világot, és azt mondják, hogy az algoritmus

685
00:40:33,140 --> 00:40:38,130
tudomásul durván faragva n lépéseket. Ez a működési idő egy algoritmus.

686
00:40:38,130 --> 00:40:40,760
Szóval jövünk vissza ezt egy pillanat néhány konkrét példákkal,

687
00:40:40,760 --> 00:40:45,940
de most, hogy ez a fajta az intuitív motivációja éppen egyszerűsítése világunk

688
00:40:45,940 --> 00:40:51,170
és beszél a legfontosabb feltételeket, ahelyett, hogy az összes ilyen divatos képleteket.

689
00:40:51,170 --> 00:40:53,540
Szóval ez volt a kiválasztás sort, és van egy kis szerencséje van.

690
00:40:53,540 --> 00:40:57,360
Nézzük beszúrási sort. Hadd menjek előre, és indítsa el ezt is.

691
00:40:57,360 --> 00:41:00,330
Most már észre, a minta, ami történik, egy kicsit más,

692
00:41:00,330 --> 00:41:03,410
és elkezdtük a véletlen számokat,

693
00:41:03,410 --> 00:41:06,890
de ha tényleg számít fel a lépések száma a legrosszabb esetben,

694
00:41:06,890 --> 00:41:11,070
ha a lista indult teljesen a megfelelő sorrendben,

695
00:41:11,070 --> 00:41:13,380
mi lenne csak n lépéseket megvalósítani annyi.

696
00:41:13,380 --> 00:41:18,240
>> De ha a lista ténylegesen hátrafelé - például, ebben az esetben itt -

697
00:41:18,240 --> 00:41:23,860
akkor észre, valójában meg kell csinálni egy sokkal több munkát, ebben az esetben.

698
00:41:23,860 --> 00:41:27,080
És ez kell, milyen érzés úgy, mint ez a fajta munka nehezebb

699
00:41:27,080 --> 00:41:30,900
hogy a kisebb elemeket a bal oldalon, és ez azért van, mert mi van szerencsétlen.

700
00:41:30,900 --> 00:41:34,210
A lista sorrendje véletlenül fordított.

701
00:41:34,210 --> 00:41:38,110
Ezzel szemben, beillesztés sort, ha utánozzák, amit tettünk a mi emberek itt

702
00:41:38,110 --> 00:41:42,670
kiindulva mindenki osztályozzák, majd indítsa el, ez egy elég jó algoritmus, ugye?

703
00:41:42,670 --> 00:41:45,010
Ez már, sőt, rendezve.

704
00:41:45,010 --> 00:41:48,670
Akkor próbáljuk meg összefoglalni, hogy pontosan mennyi ideig ezek a dolgok vesznek minket

705
00:41:48,670 --> 00:41:52,360
bevezetésével egy kicsit a zsargon vagy jelölési, hogy valójában sokkal egyszerűbb

706
00:41:52,360 --> 00:41:54,320
mint fanciness fajta sugallja.

707
00:41:54,320 --> 00:41:59,030
Ez a dolog itt, ez a nagy O a képernyőn, amit egy számítógép tudós általában használni

708
00:41:59,030 --> 00:42:03,640
leírni a legrosszabb futási ideje algoritmus.

709
00:42:03,640 --> 00:42:07,360
>> Ismét, a legrosszabb esetben, ez teljesen kontextus-függő.

710
00:42:07,360 --> 00:42:10,890
Mit értünk a legrosszabb esetben teljesen függően változik a probléma beszélünk.

711
00:42:10,890 --> 00:42:14,550
De abban az esetben a válogatás, mi a lehető legrosszabb forgatókönyv?

712
00:42:14,550 --> 00:42:17,860
Minden visszafelé, mert csak úgy érzi, mintha azt jelenti, hogy a sok munka számunkra.

713
00:42:17,860 --> 00:42:21,330
Már papírra vetette néhány olyan algoritmusok láttunk eddig:

714
00:42:21,330 --> 00:42:24,930
lineáris keresés, bináris keresés, mint a telefonkönyv, illetve a darab papír,

715
00:42:24,930 --> 00:42:28,960
majd buborék rendezés, kiválasztás sort, és a beillesztés sort, mint láttuk, a mi emberek,

716
00:42:28,960 --> 00:42:31,770
majd az 1 másik, ami végül lesz hívják egyesíteni sort.

717
00:42:31,770 --> 00:42:37,710
Tehát a lineáris keresés a legrosszabb esetben, hány lépést tart, hogy megtalálják a 7-es szám

718
00:42:37,710 --> 00:42:40,690
ha van n ajtók, mint Sean képű? >> [Hallgató] N.

719
00:42:40,690 --> 00:42:44,180
N. Így fogunk írni nagy O n.

720
00:42:44,180 --> 00:42:47,010
Én csak majd töltse ki néhány üres. Ez csak egy rács üres.

721
00:42:47,010 --> 00:42:52,990
De a legjobb esetben a lineáris keresés, 7 lehetett volna legelején a lista,

722
00:42:52,990 --> 00:42:55,520
és Sean volna elkezdtem keresni elején a listán.

723
00:42:55,520 --> 00:42:58,940
Szóval, ha lineáris keresést, és csak ellenőrzés balról jobbra, vagy talán jobbról balra -

724
00:42:58,940 --> 00:43:02,650
ők ezzel egyenértékű - a legjobb esetben hány lépést talán lineáris keresés,

725
00:43:02,650 --> 00:43:05,550
mint Sean algoritmus, el? Csak 1 lépés.

726
00:43:05,550 --> 00:43:09,450
>> Szóval fogom mondani, hogy ez az omega jelölést.

727
00:43:09,450 --> 00:43:11,570
Ez csak a tőke omega.

728
00:43:11,570 --> 00:43:15,000
Omega csak a szexi szóval legjobb esetben működési idő.

729
00:43:15,000 --> 00:43:18,900
Tehát a legjobb esetben a futási idő egy lépésben vagy állandó lépések száma -

730
00:43:18,900 --> 00:43:24,270
1 ebben az esetben -, de a legrosszabb esetben, nagy O, valójában N lépésben.

731
00:43:24,270 --> 00:43:28,110
És ez itt, theta, mi valójában nem fog nézni most.

732
00:43:28,110 --> 00:43:30,090
Ez nem vonatkozik az adott példát.

733
00:43:30,090 --> 00:43:31,990
De most próbáljuk bináris keresés.

734
00:43:31,990 --> 00:43:35,990
A legrosszabb esetben a bináris keresés, hány lépést is fog tartani, hogy megtalálják a 7-es szám

735
00:43:35,990 --> 00:43:38,340
vagy bármilyen keresünk? >> [Hallgató] Bejelentkezés n.

736
00:43:38,340 --> 00:43:40,980
Még mindig megy, hogy log n, mert ugyanúgy, mint Alex kapott szerencsétlen

737
00:43:40,980 --> 00:43:44,030
amikor valóban eljutott a problémát módszeresen

738
00:43:44,030 --> 00:43:48,220
és ő nem találta a 7-es számú, amíg az utolsó ajtó nézett,

739
00:43:48,220 --> 00:43:51,720
még akkor is, méltányosság, megkapta eldobni bizonyos ajtókat az út mentén,

740
00:43:51,720 --> 00:43:56,920
bináris keresés legrosszabb esetben egy futási ideje log n.

741
00:43:56,920 --> 00:43:59,230
És megint, hogy beszél e elosztjuk és hódító.

742
00:43:59,230 --> 00:44:01,140
De mi a helyzet a legjobb esetben?

743
00:44:01,140 --> 00:44:04,790
És Alex tényleg tapasztaltam, hogy a legjobb esetben is igaza van, amikor jött fel a színpadra.

744
00:44:04,790 --> 00:44:07,290
Hány lépés volt, hogy vegye a bináris keresés? >> [Hallgató] 1.

745
00:44:07,290 --> 00:44:09,380
1, csak azért, mert szerencsés.

746
00:44:09,380 --> 00:44:12,520
De ez jó, mert omega hivatkozik legjobb forgatókönyv esetén,

747
00:44:12,520 --> 00:44:15,770
legjobb esetben bemenet, akkor is, ha ez csak véletlen buta szerencse.

748
00:44:15,770 --> 00:44:18,900
>> Nos, ezt is fogjuk csak egyfajta szabadság üres most.

749
00:44:18,900 --> 00:44:21,010
Hogy van most bubble sort?

750
00:44:21,010 --> 00:44:24,290
A legrosszabb esetben a buborék rendezés, mindenki fordított sorrendben,

751
00:44:24,290 --> 00:44:26,380
így kell csinálni egy csomó pezsgő.

752
00:44:26,380 --> 00:44:30,190
De hány lépés az, hogy megy, hogy a legrosszabb esetben? >> [Hallgató] N faragva.

753
00:44:30,190 --> 00:44:32,550
Ez volt az a n négyzetes, mert ha belegondolsz,

754
00:44:32,550 --> 00:44:36,410
Ha a lista teljesen hátra - 8 ide, az 1 ide -

755
00:44:36,410 --> 00:44:40,530
A dolog kezd buborék, a 8-as számú fog mozogni e az út, ezt,

756
00:44:40,530 --> 00:44:44,540
Ily módon, ez az út, de hol van a 7-es szám a legrosszabb esetben?

757
00:44:44,540 --> 00:44:47,720
Itt van még mindig ott van. Tehát meg kell csinálni újra és újra.

758
00:44:47,720 --> 00:44:53,190
És ez az, ahol megkapjuk n lépésben, majd n - 1 lépésben, majd n - 2 lépéseket.

759
00:44:53,190 --> 00:44:55,960
És ha veszem a szót -, hogy ha ilyen megszorozzuk ki,

760
00:44:55,960 --> 00:45:00,110
ez durván faragva n a végén néhány más feltételekkel, akkor ne törődj most -

761
00:45:00,110 --> 00:45:06,890
akkor a legrosszabb esetben buborék rendezés n négyzetes ide vagy oda.

762
00:45:06,890 --> 00:45:09,490
De mi a helyzet a legjobb esetben a bubble sort?

763
00:45:09,490 --> 00:45:13,050
Mi a legjobb esetben? Minden a számok sorrendje már.

764
00:45:13,050 --> 00:45:15,920
És mi volt a heurisztikus használtam, a trükköt használtam,

765
00:45:15,920 --> 00:45:20,110
jönnöm, hogy nem tettek a munka és így megállítani korán?

766
00:45:20,110 --> 00:45:23,590
[Hallgató] Ellenőrizze egyszer. Ellenőrizze >> egyszer. De mit csináltam az út mentén?

767
00:45:23,590 --> 00:45:26,130
Én annak nyomon követését, hogy hány swap csináltam.

768
00:45:26,130 --> 00:45:30,650
És rájöttem, ha még nem számított semmilyen csereügyletek ujjaim, aztán csináltam nincs munka.

769
00:45:30,650 --> 00:45:34,300
Én biztosan nem próbálkozik semmilyen munkát újra, így tudok csak megáll.

770
00:45:34,300 --> 00:45:37,830
>> Így a legjobb esetben a buborék rendezés, ha a lista már rendezve,

771
00:45:37,830 --> 00:45:41,530
mit mondana az omega jelölés, a legjobb esetben futási idő?

772
00:45:41,530 --> 00:45:48,040
Ez csak n. Van, hogy némi munkát, de csak meg kell csinálni 1 sétát érdemes a munka.

773
00:45:48,040 --> 00:45:50,490
És itt is fogom elhagyni ezt a részt üresen.

774
00:45:50,490 --> 00:45:52,430
És most kiválasztás sort.

775
00:45:52,430 --> 00:45:56,010
Selection sort már nekem kopasztás a legkisebb ember újra és újra.

776
00:45:56,010 --> 00:45:58,380
És mit mondunk a futás ideje, hogy az volt?

777
00:45:58,380 --> 00:46:00,590
Ez n kihúzta a legrosszabb esetben.

778
00:46:00,590 --> 00:46:05,220
És sajnos, a legjobb esetben ez is n squared

779
00:46:05,220 --> 00:46:08,840
mert nem az a fajta mindentudó kilátás nyílik az egész világon;

780
00:46:08,840 --> 00:46:13,140
Csak azt tudom, hol teljes iterációs hogy én valóban találtam a legkisebb ember.

781
00:46:13,140 --> 00:46:15,860
Szóval kiválasztása fajta ilyen szar ebben az értelemben,

782
00:46:15,860 --> 00:46:17,920
de a fejjel ez a fajta intuitív.

783
00:46:17,920 --> 00:46:21,470
Elég könnyű kódolni, mert csak annyit kell tennie, hogy írjon egy pár beágyazott a hurkok,

784
00:46:21,470 --> 00:46:24,620
általában, hogy megy keresztül keresi a legkisebb elem

785
00:46:24,620 --> 00:46:27,840
és majd hozza a legkisebb elem, ahova tartozik az a lista végén.

786
00:46:27,840 --> 00:46:29,900
Tehát itt is lesz egy trade-off.

787
00:46:29,900 --> 00:46:34,440
Az az idő tart, hogy úgy gondolja, és hogy ténylegesen dolgozzanak valamit kódírás

788
00:46:34,440 --> 00:46:39,460
nagyon is több időt vesz igénybe, ha szeretne egy jobb algoritmust és gyorsabb teljesítményt.

789
00:46:39,460 --> 00:46:41,780
>> De ha tényleg csak ilyen kód valamit gyors és piszkos

790
00:46:41,780 --> 00:46:45,000
és csak a fajta meghozza a lehető legostobább ötlet lehet gondolni,

791
00:46:45,000 --> 00:46:47,580
hogy eltart egy pár percig kódot, de a nagy adathalmazok

792
00:46:47,580 --> 00:46:49,580
az algoritmus akár órákig is futtatni.

793
00:46:49,580 --> 00:46:51,690
És még azt a doktori iskola néha ezeket a kompromisszumokat.

794
00:46:51,690 --> 00:46:55,660
Lenne 03:00, próbáltam elemezni nagyon nagy adathalmaz

795
00:46:55,660 --> 00:46:59,650
kapcsolatos biztonsági kutatás csinálok, és azt sem költeni 5 perc

796
00:46:59,650 --> 00:47:03,210
csípés a program elemzi az adatokat, és menj aludni

797
00:47:03,210 --> 00:47:08,420
vagy eltölteni 8 órát kapok csak jobbra, úgy fut azonnal, és nem megy aludni.

798
00:47:08,420 --> 00:47:10,530
És így is ez a fajta tudatos döntés.

799
00:47:10,530 --> 00:47:12,740
Kevesebb fejlesztési időt, több alvás.

800
00:47:12,740 --> 00:47:14,780
Visszatekintve, valószínűleg nem ösztönözhet, hogy a

801
00:47:14,780 --> 00:47:19,120
ha a cél itt az, hogy optimalizálja minősége a kódot,

802
00:47:19,120 --> 00:47:21,280
de ez is a valós világ egy nagyon ésszerű kompromisszum.

803
00:47:21,280 --> 00:47:25,130
Kevesebb idő, kevesebb a teljesítmény vagy fordítva.

804
00:47:25,130 --> 00:47:28,110
Tehát itt végre kap egy esélyt, hogy beszélni theta.

805
00:47:28,110 --> 00:47:32,830
Theta jelölés van valami számítógépes tudósok hozza fel beszélgetés

806
00:47:32,830 --> 00:47:36,160
amikor a nagy O és omega történetesen ugyanaz.

807
00:47:36,160 --> 00:47:40,160
Azt mondod, theta, hogy valóban az üzenetet, hogy ez a fajta egy szűk kötve.

808
00:47:40,160 --> 00:47:43,340
Nem számít, hogy a forgatókönyv jó vagy rossz, ez n faragva.

809
00:47:43,340 --> 00:47:46,510
Szóval csak nem releváns ezeket a történeteket itt.

810
00:47:46,510 --> 00:47:48,560
Insertion sort az utolsó néztük,

811
00:47:48,560 --> 00:47:50,830
ahol éppen behelyezése mindenkit a megfelelő helyre.

812
00:47:50,830 --> 00:47:54,930
A legjobb esetben mi volt a futási idő a behelyezés sort ahogy láttuk itt?

813
00:47:54,930 --> 00:47:57,250
[Hallgató] A legjobb esetben? >> A legjobb esetben.

814
00:47:57,250 --> 00:48:00,100
>> Azt n, mert a legjobb esetben mindenki rendezve,

815
00:48:00,100 --> 00:48:02,580
és Sammy és senki más nem igazán kellett költözniük egyáltalán.

816
00:48:02,580 --> 00:48:04,610
Ők már a megfelelő helyen.

817
00:48:04,610 --> 00:48:08,570
Így beszúrásos rendezés a legjobb esetben az, ebben az esetben, n.

818
00:48:08,570 --> 00:48:12,770
De a legrosszabb esetben ez a fajta n négyzeten. Miért?

819
00:48:12,770 --> 00:48:16,230
Ha a listát emberben fordított sorrendben,

820
00:48:16,230 --> 00:48:21,260
Én először kezdi el a 8-as számú, és beilleszteni őt a jobb helyzetben, ami itt van.

821
00:48:21,260 --> 00:48:25,270
Valahogy mozog oldalra. Ezek a srácok a szétválogatás nélküli, ő van rendezve.

822
00:48:25,270 --> 00:48:28,970
De most történik, hogy megtalálja, aki a következő? >> [Hallgató] 7.

823
00:48:28,970 --> 00:48:31,250
7 a legrosszabb esetben, mert fordított sorrendben.

824
00:48:31,250 --> 00:48:34,920
>> Tehát itt van 7. Amennyiben nem 7 tartozik? Határozottan mögöttem.

825
00:48:34,920 --> 00:48:39,460
De most 7 ténylegesen tartozik közvetlenül nem a hátam mögött, de mögötte száma 8,

826
00:48:39,460 --> 00:48:41,880
így azt kell mondani, hogy "Elnézést, 8-as számú, legyen szíves mozogni így

827
00:48:41,880 --> 00:48:44,640
"Hogy helyet csináljon 7?" Most találkozom 6.

828
00:48:44,640 --> 00:48:48,530
"Ó, bocsánat, a 8 és a 7-es számú, tud mozogni, hogy a szoba 6?"

829
00:48:48,530 --> 00:48:52,360
Más szóval, a beszúrási sort, bár én nem csinál sok mozgás,

830
00:48:52,360 --> 00:48:56,330
az emberek a hátam mögött csinál sokkal több munkát, és hogy van a költségek valaki időt.

831
00:48:56,330 --> 00:48:58,000
Ez fog kerülni a számítógép idő.

832
00:48:58,000 --> 00:49:01,450
Tehát abban az esetben, helyezés sort még mindig szenved.

833
00:49:01,450 --> 00:49:06,260
Ha elkezd összeadjuk az összes lépést, a végén üti durván négyszögletesre n

834
00:49:06,260 --> 00:49:11,160
mert ezek a srácok kell, hogy helyet csináljon az ember kell beilleszteni vissza ezt a listát.

835
00:49:11,160 --> 00:49:15,960
És így ebben az esetben a theta csak nem alkalmazható az adott történetet kéznél.

836
00:49:15,960 --> 00:49:21,100
Ez mind szép és jó. Jelenleg a 3 különböző módon beszél a működési idő.

837
00:49:21,100 --> 00:49:26,370
De mit jelent ez valójában azt jelenti, reálértéken, ha valóban megpróbál kódolásához ki egy algoritmust?

838
00:49:26,370 --> 00:49:31,620
>> Hadd javasolni, hogy van egy még jobb algoritmust ott

839
00:49:31,620 --> 00:49:33,740
hogy maga is bizonyos kompromisszumokat.

840
00:49:33,740 --> 00:49:36,890
Fogjuk hívni egyesítése sort, és ez a fajta e varázslatos algoritmus

841
00:49:36,890 --> 00:49:42,840
hogy csak gyorsabban dolgozik, valahogy, és ez olyan könnyű, hogy kifejezze, legalábbis pszeudokód.

842
00:49:42,840 --> 00:49:46,900
Végrehajtása az algoritmus merge fajta lesz a következő.

843
00:49:46,900 --> 00:49:50,860
Amikor adott n elemek - n számok, n az emberek, függetlenül - először van egy józan csekket.

844
00:49:50,860 --> 00:49:56,340
Ha n kisebb, mint 2, merge sort csak megáll. Ez visszatér, hogy úgy mondjam.

845
00:49:56,340 --> 00:50:00,830
Miért hagyja abba, ha n kisebb, mint 2? >> [Hallhatatlan tanulói válasz]

846
00:50:00,830 --> 00:50:04,480
Rendben. És megint, n nem a szám a listán, n a méret a listán.

847
00:50:04,480 --> 00:50:07,660
Ha n értéke kisebb, mint 2, azt jelenti, hogy a lista az vagy 1,

848
00:50:07,660 --> 00:50:09,640
hová nyilvánvalóan válogatni, ha ez száma 1,

849
00:50:09,640 --> 00:50:11,710
vagy 0, ebben az esetben nincs mit rendezni,

850
00:50:11,710 --> 00:50:13,570
ezért szükségünk van erre a fajta alapeset.

851
00:50:13,570 --> 00:50:20,350
Ha a lista annyira rövid, hogy csak semmi köze, a szó szoros értelmében nem csinál semmit. Vissza.

852
00:50:20,350 --> 00:50:25,090
Ellenkező esetben rendezni bal felén az elemek, majd rendezni a jobb felét az elemek,

853
00:50:25,090 --> 00:50:27,410
majd egyesíteni a 2 fél rendezve.

854
00:50:27,410 --> 00:50:32,130
>> Ez a fajta úgy tűnik, mint egy kis csaló, amelyben azt kérem, hogyan kell rendezni elemek

855
00:50:32,130 --> 00:50:34,900
, és azt mondod: "Rendezze a bal felét, rendezze a jobb felét."

856
00:50:34,900 --> 00:50:37,240
Olyan vagyok, mint: "Rendben. Hogyan rendezheti a bal felét?"

857
00:50:37,240 --> 00:50:40,670
"Sort a bal fele a bal fele, rendezheti jobb felét a bal felét, majd a kész."

858
00:50:40,670 --> 00:50:44,060
Te milyen ciklikusan meghatározása, hogy mit jelent rendezni,

859
00:50:44,060 --> 00:50:46,790
de kiderült, hogy ez valóban zseniális ebben az esetben.

860
00:50:46,790 --> 00:50:50,230
Ez nem igazán az ördögi kört, amely soha nem ér véget

861
00:50:50,230 --> 00:50:52,550
mert ez nem fejeződik be, amikor? >> [Hallgató] Mikor éri el az 1 dolog.

862
00:50:52,550 --> 00:50:54,220
Mikor éri el az 1 dolog.

863
00:50:54,220 --> 00:50:57,850
Így, bár lehet, hogy kezdeni 8 ember, és azt mondják, "sort a bal fele ezeknek az embereknek,

864
00:50:57,850 --> 00:51:00,480
E 4 személy ", akkor azt mondom," Hogyan rendezheti a bal felét? "

865
00:51:00,480 --> 00:51:03,450
"Nos, rendezheti 2 személy itt." És akkor te, mint: "Oké, rendben."

866
00:51:03,450 --> 00:51:05,520
"Hogyan rendezheti bal felén azokat az embereket?"

867
00:51:05,520 --> 00:51:09,040
"Csak rendezni ezt 1 ember itt." Mi a zseniális kinyilatkoztatás most?

868
00:51:09,040 --> 00:51:13,050
Meg kell rendezni 1 fő részére. Kész. Nem tudom, hogy csináljanak valamit.

869
00:51:13,050 --> 00:51:16,580
De most el kell rendezni ezt a személyt, de ők egy személy, semmi köze.

870
00:51:16,580 --> 00:51:21,490
>> Tehát a mágia nyilvánvalóan ebben harmadik lépés: összevonja a rendezett felét.

871
00:51:21,490 --> 00:51:25,770
Szóval merge sort veszi ezt a ragyogó betekintést, hogy ha törik egy nagy probléma le

872
00:51:25,770 --> 00:51:28,650
a 2 kisebb, azonos méretű problémák

873
00:51:28,650 --> 00:51:32,710
és majd csak ilyen ragasztó a kisebb megoldásokkal együtt a végén,

874
00:51:32,710 --> 00:51:34,720
Azt javaslom, hogy tehetünk sokkal, de sokkal jobbak [megérinti hang]

875
00:51:34,720 --> 00:51:38,050
mint bármelyik kiválasztási szettbe vagy beszúrási sort.

876
00:51:38,050 --> 00:51:40,690
Már valóban figyelmen kívül hagyják, hogy egy fél órát, de én tényleg nem tudom, hogy mi folyik itt

877
00:51:40,690 --> 00:51:45,040
ezen kívül ma. [Berregő hang] [nevetés]

878
00:51:45,040 --> 00:51:49,660
Tehát lássuk, ha látja ezt egy kis segítség a barátunk Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Van 2 nagy lépés a folyamat merge sort.

880
00:51:52,810 --> 00:51:56,400
Először is, folyamatosan szét a listáját cups figyelembe félidőt

881
00:51:56,400 --> 00:51:59,610
amíg van egy csomó listák csak 1 csésze őket.

882
00:51:59,610 --> 00:52:02,150
Ne aggódjon, ha a lista tartalmazza a páratlan számú

883
00:52:02,150 --> 00:52:04,830
és nem lehet, hogy egy teljesen tiszta vágás között.

884
00:52:04,830 --> 00:52:08,740
Csak önkényesen válasszon, amely lista tartalmazza az extra pohár be

885
00:52:08,740 --> 00:52:11,320
Szóval szét ezeket a listákat.

886
00:52:12,420 --> 00:52:14,570
Most van 2 listákat.

887
00:52:18,930 --> 00:52:20,930
Most már 4 listákat.

888
00:52:25,730 --> 00:52:28,740
Most már 8 listák egy csésze mindegyik listán.

889
00:52:28,740 --> 00:52:31,520
Szóval ez azt az 1. lépést.

890
00:52:31,520 --> 00:52:37,280
A 2. lépés már többször egyesítése pár listák segítségével az egyesítés algoritmus tudtuk korábban.

891
00:52:37,280 --> 00:52:44,320
Egyesítése 108 és 15 a végén a listát 15, 108.

892
00:52:45,240 --> 00:52:51,330
Összevonása 50 és 4 a végén 4, 50.

893
00:52:51,330 --> 00:52:56,950
Egyesítése 8 és 42 a végén 8, 42.

894
00:52:57,790 --> 00:53:04,360
És egyesülő 23 és 16-a végén 16, 23.

895
00:53:04,360 --> 00:53:08,030
Most minden a mi listák a 2-es méret.

896
00:53:08,030 --> 00:53:10,980
Figyeljük meg, hogy mind a 4 listák sorrendje,

897
00:53:10,980 --> 00:53:14,230
így tudjuk kezdeni egyesülő pár listák újra.

898
00:53:14,230 --> 00:53:22,150
Összevonása 15. és a 108. és 4 és 50 mi előbb a 4, akkor a 15,

899
00:53:22,150 --> 00:53:26,250
akkor a 50, majd a 108.

900
00:53:26,250 --> 00:53:33,020
Összevonása 8, 42 és 16, 23 mi előbb a 8, akkor a 16,

901
00:53:33,020 --> 00:53:37,170
akkor a 23, majd a 42.

902
00:53:37,170 --> 00:53:42,490
Így most már csak 2 listák 4 nagyság, amelyek mindegyike rendezve.

903
00:53:42,490 --> 00:53:45,940
Tehát most már eleget a 2 listákat.

904
00:53:45,940 --> 00:53:54,230
Először vegyük a 4, majd vesszük a 8, akkor vesszük a 15

905
00:53:54,230 --> 00:54:05,280
és 16 és 23, valamint 42 és 50 és 108.

906
00:54:05,280 --> 00:54:09,020
És mi történt. Most már van egy rendezett listát.

907
00:54:09,020 --> 00:54:13,740
>> Rob kedves volt kihasználják valamit, amit mi még nem.

908
00:54:13,740 --> 00:54:16,540
Azt javasolták, de valójában nem csinálni.

909
00:54:16,540 --> 00:54:19,230
Ő csinál valamit fizikailag a cups azt sugallja, hogy

910
00:54:19,230 --> 00:54:23,680
ben töltött néhány forrás mellett időt. >> [Hallgató] Space. >> Volt hely.

911
00:54:23,680 --> 00:54:27,360
Az a tény, hogy volt ez a fajta bi-szintű asztalhoz, ahol volt hely ide

912
00:54:27,360 --> 00:54:31,960
és a tér itt lent valójában arra utal, hogy ő használja kétszer annyi helyet

913
00:54:31,960 --> 00:54:36,390
mint bármelyik eddigi algoritmusok - beillesztés sort, buborék rendezés, vagy kiválasztás sort -

914
00:54:36,390 --> 00:54:40,780
de ő kihasználva ezt a további helyet a fajta mozgás dolog oda-vissza

915
00:54:40,780 --> 00:54:42,600
miközben a dolgokat.

916
00:54:42,600 --> 00:54:47,540
És bár úgy érzi, mintha van egy rendezett lista, hogy úgy éreztem, hogy volt egy darabig.

917
00:54:47,540 --> 00:54:51,060
A valóságban, amit Rob csinált pontosan ez az algoritmus.

918
00:54:51,060 --> 00:54:56,780
Először volt a probléma a mérete n, osztva be a bal oldalán, és a jobb felét.

919
00:54:56,780 --> 00:54:59,380
Ekkor költözött a csészéket. Aztán megismételte ezt a folyamatot.

920
00:54:59,380 --> 00:55:03,390
Ő osztva 4 a 2 db 2-át itt és itt.

921
00:55:03,390 --> 00:55:08,520
Aztán megismételte a folyamatot, és osztva 2 a 2 db 1 minden e különböző csészéket.

922
00:55:08,520 --> 00:55:11,000
És ez az, ahol a ragyogó lehetőség felmerül.

923
00:55:11,000 --> 00:55:15,840
Ezen a ponton a történet, Rob már 8 listák méret 1,

924
00:55:15,840 --> 00:55:18,860
melyek mindegyike rendezett már.

925
00:55:18,860 --> 00:55:20,630
>> Akkor mit is folytatni kell csinálni?

926
00:55:20,630 --> 00:55:25,260
Páronkénti vette ezt a rendezett listát, és ezt a rendezett listát, és összevonták őket.

927
00:55:25,260 --> 00:55:28,200
Aztán vette ezt, és összevonták őket, majd ezt, és összevonták őket,

928
00:55:28,200 --> 00:55:30,670
akkor ez egy és egyesítették őket.

929
00:55:30,670 --> 00:55:32,390
És akkor mit csinált ezután?

930
00:55:32,390 --> 00:55:36,580
Ezután újra egyesült a nagyobb listákat, majd újra egyesült a nagyobb listáját.

931
00:55:36,580 --> 00:55:41,170
És ha úgy gondolja, erre csak ösztönösen most, mit csinál ő valójában?

932
00:55:41,170 --> 00:55:45,450
Ő volt elosztjuk a problémát fél, fél, fél, fél

933
00:55:45,450 --> 00:55:47,600
annak érdekében, hogy ezeket a szuper kis listákat.

934
00:55:47,600 --> 00:55:51,290
Aztán volt olyan kedves, hogy egyesítené dupla, dupla, dupla, dupla.

935
00:55:51,290 --> 00:55:54,120
Így csinál kétszer annyi munkát, mint láttuk eddig

936
00:55:54,120 --> 00:55:56,930
bármi bevonásával oszd meg és uralkodj, de nem nagy ügy.

937
00:55:56,930 --> 00:55:59,630
Kétszer annyi a munka nem is olyan nagy ügy. Ez csak egy állandó tényező.

938
00:55:59,630 --> 00:56:03,920
És még sok minden, mint a mi aritmetikai kifejezés előtt, én csak megy át ki állandó tényezők

939
00:56:03,920 --> 00:56:10,170
mint a szer 2. Kit érdekel? Ha ez 2 milliárd-szer 2, ez még mindig sok lépésből áll.

940
00:56:10,170 --> 00:56:13,160
Szóval ez egyesülő lépés úgy tűnik, hogy a kulcs betekintést.

941
00:56:13,160 --> 00:56:17,000
Sétáljunk át ez csak numerikusan előtt - Ó, ez nem lehet folytatni még.

942
00:56:17,000 --> 00:56:22,890
Sétáljunk át ezt számszerűleg csak azért, hogy valóban látni, hogy ez hogyan játssza ki.

943
00:56:22,890 --> 00:56:25,940
Ez többnyire csak egy kis szegény ember animáció.

944
00:56:25,940 --> 00:56:27,750
Nézzük ezt a javaslatot.

945
00:56:27,750 --> 00:56:31,480
A működési idő merge sort - már csak be kell egy módja beszél erről.

946
00:56:31,480 --> 00:56:34,380
Ez nem matek, ez csak egyfajta tömör kifejezési módja magunkat.

947
00:56:34,380 --> 00:56:39,080
Tehát T jelentése időben és n jelentése mi? >> [Hallgató] A méret a -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] A méret a probléma, az emberek száma.

949
00:56:41,400 --> 00:56:45,470
Szóval arra hivatkozva, hogy a működési idő rendezni n embereknek lesz 0 időt

950
00:56:45,470 --> 00:56:50,290
ha n kisebb, mint 2, mert ha 1 csésze vagy nem csészék, nincs mit rendezni.

951
00:56:50,290 --> 00:56:55,160
De általánosságban fogom javasolni, hogy a működési idő rendezni n elemet

952
00:56:55,160 --> 00:56:59,350
lesz, hogy mennyi időt vesz igénybe, hogy rendezze a bal felét, plusz a jobb felét

953
00:56:59,350 --> 00:57:03,110
plus - mi ez a kiegészítő + n? >> [Hallgató] Merge sort.

954
00:57:03,110 --> 00:57:07,260
[Malan] Ez valójában egyesülő, mert ha van n / 2 elem van

955
00:57:07,260 --> 00:57:11,500
és van n / 2 elem van, mennyi időbe telik egyesíteni őket?

956
00:57:11,500 --> 00:57:15,050
Csakúgy, mint Rob, van, hogy összeszedi ez ide, talán összeszedi ide,

957
00:57:15,050 --> 00:57:17,120
bátorság ide, bátorság ide, bátorság ide.

958
00:57:17,120 --> 00:57:19,400
Meg kell érinteni az egyes csészék egyszer.

959
00:57:19,400 --> 00:57:22,030
És ha van 4 csésze plusz 4 csésze, ez 8 csésze

960
00:57:22,030 --> 00:57:25,200
vagy még általánosabban, 8 N csésze.

961
00:57:25,200 --> 00:57:28,470
Tehát az egyesülő lépésben képes kifejezni, mint n,

962
00:57:28,470 --> 00:57:31,330
és hogy szó szerint magában foglalja a szám, ahányszor a Rob fizikailag érintett

963
00:57:31,330 --> 00:57:33,410
egyike azoknak a hungarocell csésze.

964
00:57:33,410 --> 00:57:35,850
Szóval most csinál egy tetszőleges példát.

965
00:57:35,850 --> 00:57:41,850
Ha van 16 csésze, mi a futási idő a válogatás, a Rob-algoritmus, 16 cups?

966
00:57:41,850 --> 00:57:44,710
Ez a 2-szer annyi időt vesz igénybe, hogy rendezni 8 csésze

967
00:57:44,710 --> 00:57:46,920
mert van 8 csésze van, 8 csésze ide.

968
00:57:46,920 --> 00:57:51,520
Nem tudom, mennyi ideig tart, úgyhogy általánosítani, hogy a T a pillanatban.

969
00:57:51,520 --> 00:57:53,320
Ki tudja, mi ez?

970
00:57:53,320 --> 00:57:58,990
De most is egyfajta rekurzív vagy többször fel ugyanazt a kérdést.

971
00:57:58,990 --> 00:58:01,920
Mennyi időbe telik, hogy rendezni 8 csésze?

972
00:58:01,920 --> 00:58:07,030
8 csésze fogom mondani, úgy időt vesz igénybe, hogy rendezni 4 csésze plusz 4 csésze,

973
00:58:07,030 --> 00:58:08,880
majd egyesülő őket.

974
00:58:08,880 --> 00:58:13,080
Fine. Mi bekerülni a ciklus már. Mennyi időbe telik, hogy rendezni 4 csésze?

975
00:58:13,080 --> 00:58:19,150
A szükséges idő rendezni 4 csésze a 2 csésze plusz 2 csésze válogatása plusz az egyesülő folyamatot.

976
00:58:19,150 --> 00:58:21,440
Fine. Mennyi időbe telik, hogy rendezni 2 csésze?

977
00:58:21,440 --> 00:58:26,290
2 csésze az mennyi időt vesz igénybe, hogy rendezni 1 csésze plusz időt, hogy rendezze egy csésze

978
00:58:26,290 --> 00:58:29,040
plusz időt vesz igénybe, egyesíteni, ami mindössze 2.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Utolsó kérdés. Mennyi időbe telik, hogy rendezni 1 csésze?

980
00:58:33,340 --> 00:58:37,260
Itt az alap eset, hogy mi várható mi lenne hit korábban.

981
00:58:37,260 --> 00:58:42,250
Az a tény, hogy nem veszi a munka egyáltalán rendezni a legkisebb problémák

982
00:58:42,250 --> 00:58:44,120
azt jelenti, hogy most, a fajta iskolában stílus,

983
00:58:44,120 --> 00:58:46,460
akkor csak menj kezdeni dugulás ezeket a számokat ismét bejelentkezni!

984
00:58:46,460 --> 00:58:50,630
Most már tudom, mit T 1, így tudok csatlakoztatni a 0 T: 1 db.

985
00:58:50,630 --> 00:58:54,420
Ez ad nekem választ T 2, amit akkor lehet csatlakoztatni feljebb.

986
00:58:54,420 --> 00:58:56,930
Ez ad nekem T 4, amit lehet csatlakoztatni feljebb.

987
00:58:56,930 --> 00:58:58,920
Ez ad nekem T 8, amit tud csatlakoztatni feljebb.

988
00:58:58,920 --> 00:59:04,330
És ha ténylegesen arra, hogy a matematika a dugulás ezeket a válaszokat,

989
00:59:04,330 --> 00:59:08,590
Aztán kap egy T 16-64.

990
00:59:08,590 --> 00:59:12,090
És mit jelent 64 képvisel?

991
00:59:12,090 --> 00:59:15,700
Ha a T-16, igen, ez 16-szor 4.

992
00:59:15,700 --> 00:59:20,120
Szóval most azt állítják, hogy a futási idő ez a dolog az úgynevezett merge sort -

993
00:59:20,120 --> 00:59:22,590
és ez lesz a fanciest az is láttunk eddig -

994
00:59:22,590 --> 00:59:26,160
fog hívni n log n

995
00:59:26,160 --> 00:59:31,140
mert hányszor lehet rabolni megosztani egy csomó csésze félidőben? Jelentkezzen n.

996
00:59:31,140 --> 00:59:34,370
Ez ugyanaz, mint a telefonkönyv Például, ez ugyanaz, mint az ön-számlálás példa.

997
00:59:34,370 --> 00:59:36,380
>> Hányszor lehet osztani valamit félidőben?

998
00:59:36,380 --> 00:59:38,410
Azonban ez a beolvadó lépést.

999
00:59:38,410 --> 00:59:42,920
Lehet, hogy meg kell osztani a poharak a 1/2, újra és újra és újra,

1000
00:59:42,920 --> 00:59:45,640
de minden alkalommal fogsz össze kell fésülni.

1001
00:59:45,640 --> 00:59:48,270
És mi azt mondtuk korábban, hogy egyesülő n kupák előnyben n lépések

1002
00:59:48,270 --> 00:59:52,060
mert meg kell tépni egy csésze, bátorság egy csésze, és van, hogy miden csésze egyszer,

1003
00:59:52,060 --> 00:59:53,510
mint Rob tette.

1004
00:59:53,510 --> 00:59:59,430
Tehát, ha csinálunk valamit, log n-szer, és csinálunk n dolgokat minden ilyen ismétléseket

1005
00:59:59,430 --> 01:00:03,090
Minden ilyen halvings, már n-szer log n.

1006
01:00:03,090 --> 01:00:07,220
Ha tehát csatlakoztassa 16 ebben a példában, 16-szor log 16 -

1007
01:00:07,220 --> 01:00:10,600
ne aggódj, hogy miért ez a helyzet most, mert én már nem készítették az alap -

1008
01:00:10,600 --> 01:00:16,100
de log 2 alaprész 16 4, 16-szer 64 4.

1009
01:00:16,100 --> 01:00:22,350
De ezzel szemben, ha mi is használta bubble sort vagy szelekciós szettbe vagy beszúrási sort, 16 szám,

1010
01:00:22,350 --> 01:00:26,420
mi lenne a futási idő lett volna, ha n 16?

1011
01:00:26,420 --> 01:00:33,310
Lenne 16 négyzeten, ami 256, ami még akkor is ha nem teljesen követi a matek,

1012
01:00:33,310 --> 01:00:38,390
256 nagyobb, mint 64. Ez tényleg a mágikus elvitelre itt.

1013
01:00:38,390 --> 01:00:41,990
És észre, hogy a munka ezen keresztül kisebb példákat fogsz egy Pset

1014
01:00:41,990 --> 01:00:44,260
teszi, hogy sokkal több intuitív.

1015
01:00:44,260 --> 01:00:49,070
De mit jelent valójában szempontjából az érzést az algoritmus a következő:

1016
01:00:49,070 --> 01:00:54,520
Ha tényleg megnézi merge sort itt - hadd vessem fel ebben az ablakban van -

1017
01:00:54,520 --> 01:00:58,560
ez egy kicsit más példa, amelyben van mind a 3 Ezen algoritmusok -

1018
01:00:58,560 --> 01:01:01,440
buborék, a kiválasztás, és egyesíti - csak egymás mellett.

1019
01:01:01,440 --> 01:01:03,740
>> Ők egész kezdődött véletlenszerű bárok, és ez jó.

1020
01:01:03,740 --> 01:01:06,240
Senki sem alapvető előnye a másikkal szemben.

1021
01:01:06,240 --> 01:01:09,500
Megyek egy pillanat kattintson minden egyes ilyen animációk - a Start, Start, Start -

1022
01:01:09,500 --> 01:01:13,270
, amilyen gyorsan csak lehet, hogy a, durván, ők minden kezdődik egyszerre,

1023
01:01:13,270 --> 01:01:17,450
és nézzük meg, hogy a buborék rendezés a rosszabb esetben futási idő mi? >> [Hallgató] N faragva.

1024
01:01:17,450 --> 01:01:21,560
N kockás. Selection sort a legrosszabb futási idő van? N kockás.

1025
01:01:21,560 --> 01:01:25,150
És merge sort nyilvánvalóan - akkor is, ha nem igazán követi a matek most

1026
01:01:25,150 --> 01:01:30,610
ez lesz sokkal intuitívabb idővel - az, hogy azt állítják, n-szer log n.

1027
01:01:30,610 --> 01:01:35,210
És mivel log n szigorúan kisebb, mint n, ha már nagy számok,

1028
01:01:35,210 --> 01:01:40,230
n-szer log n kisebb, mint n-szer n-vagy n négyzetével.

1029
01:01:40,230 --> 01:01:44,410
Szóval mit érzés, hogy valóban egy jobb algoritmust tekintetében működési idő,

1030
01:01:44,410 --> 01:01:50,380
n-szer log n, szemben az n négyzet? Itt vagyunk. Klikk, klikk, klikk.

1031
01:01:55,690 --> 01:01:58,650
>> Ez az, hogy mit jelent használni valami ilyesmit merge sort.

1032
01:01:58,650 --> 01:02:01,680
Van egy pillanat. Lássuk, mi történik itt.

1033
01:02:09,440 --> 01:02:12,440
[Kuncog] Kinek pénz van a bubble sort?

1034
01:02:14,960 --> 01:02:16,730
Sokkal inkább függ a bemeneti néha.

1035
01:02:16,730 --> 01:02:18,120
Lássuk.

1036
01:02:18,120 --> 01:02:23,320
Gyerünk. Olyan érzés, mintha a felzárkózás. >> [Hallgató] Menj, bubble sort!

1037
01:02:23,320 --> 01:02:27,370
[Diákok zúgolódás]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Igen, igen.

1039
01:02:29,120 --> 01:02:34,520
[Diákok zúgolódás] Menj, menj, menj!

1040
01:02:37,210 --> 01:02:40,450
[Összes éljenzés] [taps]

1041
01:02:40,450 --> 01:02:46,240
Tehát most az 1 utolsó, záró demo, ha ez egy kicsit trükkös, hogy tekerje elméd köré a matek

1042
01:02:46,240 --> 01:02:49,280
vagy valami a vizualizáció van, akkor valóban hallani a sebesség

1043
01:02:49,280 --> 01:02:51,000
a különböző algoritmusok másképp.

1044
01:02:51,000 --> 01:02:53,900
Ez egy animáció valaki tett, amely ténylegesen társult hangzik

1045
01:02:53,900 --> 01:02:56,980
abba a folyamatba, és a csere magasságát a rudak.

1046
01:02:56,980 --> 01:03:00,440
Mint látni fogjuk itt, van még néhány rendező algoritmus, hogy ott emberek is gondoltam.

1047
01:03:00,440 --> 01:03:03,660
Az első lesz beillesztés sort, és ez repülnek át

1048
01:03:03,660 --> 01:03:07,090
és kapsz egy hallható értelemben, hogy ezek a különböző algoritmusok munka.

1049
01:03:07,090 --> 01:03:09,080
Itt helyezés sort.

1050
01:03:09,080 --> 01:03:18,410
[Elektronikus csipogás]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Gyorsabb elektronikus csipogó]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Selection sort.

1054
01:03:48,950 --> 01:04:03,580
[Gyorsabb elektronikus csipogó]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge sort.

1056
01:04:05,770 --> 01:04:17,270
[Elektronikus csipogás]

1057
01:04:17,270 --> 01:04:20,180
[Csipogó lelassítja] [nevetés]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome sort.

1059
01:04:22,590 --> 01:04:38,580
[Elektronikus csipogás]

1060
01:04:39,740 --> 01:04:46,150
>> Ez CS50. Találkozunk jövő héten. [Taps és éljenzés]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]