1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> Gjuha: Në rregull, kjo është CS50.

3
00:00:14,910 --> 00:00:19,020
Ky është fundi i javës së tre, dhe në qoftë se
ju nuk kanë përfituar tashmë,

4
00:00:19,020 --> 00:00:21,790
e di se do të ketë drekë
kjo e premte si zakonisht, ku

5
00:00:21,790 --> 00:00:25,430
ju mund të gëzojnë bisedë të mirë
dhe ushqimit në zjarr dhe akull

6
00:00:25,430 --> 00:00:27,980
me disa nga CS50-së
Stafi dhe shokët e klasës.

7
00:00:27,980 --> 00:00:30,170
Shkojnë në këtë URL këtu.

8
00:00:30,170 --> 00:00:33,420
>> Tani ju mund të kujtohet, apo ju
së shpejti mund të jenë të njohur me,

9
00:00:33,420 --> 00:00:35,970
këto gjëra këtu, të cilat
janë dhënë në fund

10
00:00:35,970 --> 00:00:37,850
i semestrit për shumë klasa.

11
00:00:37,850 --> 00:00:40,870
Libra blu ashtuquajtura provimit, në të cilën
ju shkruani përgjigjet tuaja për provimet.

12
00:00:40,870 --> 00:00:44,240
Tani unë kam këtu 26 të tilla
libra blu, për secilin prej tyre

13
00:00:44,240 --> 00:00:47,580
është shkruar një emër, një pasim Z. Dhe
në të vërtetë emrat janë aq të thjeshta, Një

14
00:00:47,580 --> 00:00:50,490
përmes Z. Dhe një nga
qëllimet në dorë sot

15
00:00:50,490 --> 00:00:53,910
do të jetë për të vazhduar çfarë
kemi filluar të hënën, e cila nuk është

16
00:00:53,910 --> 00:00:57,830
aq shumë kërkuar në kodin, por me të vërtetë
duke kërkuar në idetë dhe zgjidhjen e problemeve.

17
00:00:57,830 --> 00:01:00,170
Një nga qëllimet dhe
premtimet e këtij kursi

18
00:01:00,170 --> 00:01:02,985
është për të mësuar se për të menduar më shumë
me kujdes, më shumë në mënyrë metodike,

19
00:01:02,985 --> 00:01:05,400
dhe për të zgjidhur problemet në mënyrë më efikase.

20
00:01:05,400 --> 00:01:09,526
Dhe me të vërtetë, ne mund të bëjmë që me të vërtetë
edhe pa e prekur një linjë të kodit.

21
00:01:09,526 --> 00:01:12,150
Kështu që unë kam një çift të elefantëve
këtu sot, portokalli dhe blu,

22
00:01:12,150 --> 00:01:15,780
në qoftë se ne mund të marrë një vullnetar,
ndoshta nga më larg prapa se zakonisht.

23
00:01:15,780 --> 00:01:18,070
Si për të drejtë atje, vijnë më poshtë.

24
00:01:18,070 --> 00:01:24,180
Qëllimi i cili do të jenë të
ndihmojë plus administruar këtë provim këtu.

25
00:01:24,180 --> 00:01:24,935
Si e keni emrin?

26
00:01:24,935 --> 00:01:25,768
>> Audienca: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
Gjuha: Mary Beth, eja lart.

28
00:01:27,560 --> 00:01:29,560
Më lejoni të merrni mikrofonin këtu për ju.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Gëzohem që u njohëm.

31
00:01:32,880 --> 00:01:34,005
>> Audienca: Gëzohem që u njohëm.

32
00:01:34,005 --> 00:01:36,790
Gjuha: Në rregull, kështu që unë kam
këtu libra blu Një përmes Z,

33
00:01:36,790 --> 00:01:41,680
dhe unë jam duke shkuar për të pretendojë se
Unë kam një nga studentët,

34
00:01:41,680 --> 00:01:45,770
dhe ata janë të ardhur në disi rastësisht
në fund të një tre orë bllok provimit,

35
00:01:45,770 --> 00:01:49,400
kështu që ata janë duke i dhënë fund deri në disa
mënyrë gjysmë të rastit si kjo.

36
00:01:49,400 --> 00:01:54,510
Tani puna juaj në vetëm një moment do
të be-- kjo është në të vërtetë se si ata marrin

37
00:01:54,510 --> 00:01:56,820
kthyer në në fund të
klasës, ka shumë të ngjarë.

38
00:01:56,820 --> 00:02:01,120
Puna juaj tani do të jetë, mjaft
thjesht, për të zgjidhur këto libra blu për ne

39
00:02:01,120 --> 00:02:05,220
nga A nëpërmjet Z.

40
00:02:05,220 --> 00:02:08,400
>> Audienca: Oh, kjo është e
do të marrë përgjithmonë.

41
00:02:08,400 --> 00:02:13,747
>> Gjuha: Dhe ne do të shikojnë
si ju bëni këtë, nuk ka presion.

42
00:02:13,747 --> 00:02:15,330
Audienca: Jo, nuk ka presion apo ndonjë gjë.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> Gjuha: Dhe për argëtim,
le të vënë një orë me zile.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> Audienca: Pra, shumë e bukur, e bukur aq shumë.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> Gjuha: Unë mund të mbajnë mic për ju.

49
00:02:38,574 --> 00:02:40,240
Në rregull, ne kemi dyfishuar vetëm shpejtësinë tonë.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Pra, në ndërkohë, më lejoni të paraqesin çfarë është
do të jetë pyetje për Mary Beth

52
00:02:49,060 --> 00:02:51,540
është ajo që është duke bërë ajo, se si është
ajo shkon në lidhje me zgjidhjen e kësaj?

53
00:02:51,540 --> 00:02:54,040
Dhe në fakt, ju nuk mund të ketë
menduar ndonjëherë për diçka

54
00:02:54,040 --> 00:02:57,440
aq e thjeshtë sa, kur ju të vini
up 26 libra si kjo,

55
00:02:57,440 --> 00:02:59,350
të cilat kanë një natyrore
urdhëruar atyre.

56
00:02:59,350 --> 00:03:01,335
Cili është procesi
që ju të vërtetë të përdorni?

57
00:03:01,335 --> 00:03:03,770
A është e drejtë të rastit vetëm
picking një të parë që ju shihni

58
00:03:03,770 --> 00:03:05,250
dhe vënë atë në vendin e saj?

59
00:03:05,250 --> 00:03:09,680
A e keni parë të shkojë në duart tuaja rreth
Duke kërkuar për një më pas duke kërkuar për B?

60
00:03:09,680 --> 00:03:11,722
A keni marrë një sy në një
palë ato krah për krah

61
00:03:11,722 --> 00:03:14,680
dhe vetëm thonë, prit një minutë, kjo
nuk është e drejtë, dhe pastaj të bie në ujdi e rendit?

62
00:03:14,680 --> 00:03:16,960
Ne pamë tashmë të hënën
se ka një numër mënyrash

63
00:03:16,960 --> 00:03:22,140
në të cilën ne mund ta bëjë këtë, dhe
me të vërtetë si ne pranë fund këtu,

64
00:03:22,140 --> 00:03:26,360
Unë do të vini re ndoshta
e çfarë Mary Beth është duke bërë.

65
00:03:26,360 --> 00:03:30,040
Ne kemi një shtyllave disa me sa duket, një
më të madhen, tre ato më të vogla.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> Audienca: Unë jam urdhëruar t'i
kur kam gjetur dy letra

68
00:03:36,415 --> 00:03:39,540
që unë e di se janë së bashku në një sekuencë,
I vënë ato së bashku në mënyrë që unë të mos bëj

69
00:03:39,540 --> 00:03:42,915
duhet të shqetësohen për mbajtjen
gjurmët e një rresht të tërë librash.

70
00:03:42,915 --> 00:03:45,706
Është vetëm, oh, A është i pari,
Unë kam marrë këtë rafte këtu.

71
00:03:45,706 --> 00:03:47,580
Gjuha: Pra, pothuajse si
një copë mister që

72
00:03:47,580 --> 00:03:49,860
kanë formën e duhur për të
përputhen me njëri tjetrin.

73
00:03:49,860 --> 00:03:51,026
Audienca: Shumë e shumë, vërtet.

74
00:03:51,026 --> 00:03:55,320
Gjuha: OK, e shkëlqyer.

75
00:03:55,320 --> 00:03:59,850
Dhe tani secili nga këto
shtyllave të zgjidhet me sa duket?

76
00:03:59,850 --> 00:04:00,990
>> Audienca: Po.

77
00:04:00,990 --> 00:04:09,900
>> Gjuha: Në rregull, Një përmes Z. All
drejtë, urime, ju e bëri atë.

78
00:04:09,900 --> 00:04:11,461
Ju keni zgjedhjen tuaj.

79
00:04:11,461 --> 00:04:11,960
Blue?

80
00:04:11,960 --> 00:04:13,530
Në rregull, ju falenderoj për këtë.

81
00:04:13,530 --> 00:04:16,679
Pra Mary Beth ka propozuar
çfarë qasje saj ishte,

82
00:04:16,679 --> 00:04:19,720
por ajo që është një tjetër metodë se si ju
mund të shkoni në lidhje me klasifikim këto gjëra?

83
00:04:19,720 --> 00:04:21,130
Çfarë do të kishit bërë?

84
00:04:21,130 --> 00:04:24,060
Rekord të mundë do të kishte qenë
një minutë dhe 50 apo më shumë sekonda,

85
00:04:24,060 --> 00:04:26,039
plus ato që kam harruar për të numëruar.

86
00:04:26,039 --> 00:04:27,080
Çfarë do të kishit bërë?

87
00:04:27,080 --> 00:04:27,579
Po?

88
00:04:27,579 --> 00:04:28,735
Audienca: Merrni rafte.

89
00:04:28,735 --> 00:04:29,776
Fillojnë nga fillimi.

90
00:04:29,776 --> 00:04:32,284
Kontrolloni letrat tuaja.

91
00:04:32,284 --> 00:04:36,586
Dhe në qoftë se një krye është më e lartë
se, ndoshta, ata janë,

92
00:04:36,586 --> 00:04:38,980
një fund është
më të lartë, pastaj kaloni ato.

93
00:04:38,980 --> 00:04:41,300
>> Gjuha: OK, kështu që duke filluar
në krye dhe në fund,

94
00:04:41,300 --> 00:04:43,716
dhe pastaj të punojnë në rrugën tuaj
brendshëm si kjo, shkëmbejnë ato?

95
00:04:43,716 --> 00:04:46,580
OK, kështu që pak të ngjashme
në frymë të flluskë lloji,

96
00:04:46,580 --> 00:04:49,160
por duke zgjedhur ekstremet
jo palë ngjitur.

97
00:04:49,160 --> 00:04:52,080
Por të shkurtër të tij është se nuk ka
me siguri një bandë e mënyra të ndryshme

98
00:04:52,080 --> 00:04:54,210
ne mund të bëjmë këtë, dhe
sinqerisht, unë mendoj se ju lloj

99
00:04:54,210 --> 00:04:55,700
adoptuar një qasje çift, apo jo?

100
00:04:55,700 --> 00:05:00,567
Ju bërë lloj të katër shtyllave të renditur, dhe
pastaj në mënyrë efektive shkrirë ato së bashku.

101
00:05:00,567 --> 00:05:02,650
Dhe kjo është, guxoj të them, një tjetër
teknikë krejt.

102
00:05:02,650 --> 00:05:06,950
Ju nuk e trajtojnë atë si një grumbull i madh,
ju ndarë problemin në katër quads,

103
00:05:06,950 --> 00:05:09,820
në qoftë se ju do, dhe pastaj disi
shkrirë ato në fund.

104
00:05:09,820 --> 00:05:13,410
>> Pra, le të marrin në konsideratë, në fund të fundit,
si tjetër ne mund të bëjmë këtë.

105
00:05:13,410 --> 00:05:15,860
Ne formalizuar nocionin
i flluskë renditjes herë të fundit,

106
00:05:15,860 --> 00:05:18,780
dhe kujtojnë flluskë lloj ishte një
algorithm që ne visualized

107
00:05:18,780 --> 00:05:22,640
me tetë nga shokët e klasës tuaj deri këtu,
në dukje të renditura rastësisht në fillim.

108
00:05:22,640 --> 00:05:26,110
Dhe ne pastaj vendosi pairwise, nëse
dy elemente janë jashtë rendit,

109
00:05:26,110 --> 00:05:26,950
thjesht bie në ujdi tyre.

110
00:05:26,950 --> 00:05:28,930
Pra, katër dhe dy janë
qartë nga e rendit,

111
00:05:28,930 --> 00:05:31,080
kështu ata të dy shokët e klasës
kaloi pozicionet.

112
00:05:31,080 --> 00:05:35,390
Dhe pastaj kemi përsëritur me katër dhe gjashtë,
pastaj gjashtë dhe të tetë, në çdo përsëritje,

113
00:05:35,390 --> 00:05:36,980
duke lëvizur në të djathtë.

114
00:05:36,980 --> 00:05:42,590
>> Pra, duke pasur parasysh tetë njerëz, sa pairwise
Krahasimet e bëra unë këtë, ndërsa në këmbë nga

115
00:05:42,590 --> 00:05:45,220
majta në të djathtë në një përsëritje të tillë?

116
00:05:45,220 --> 00:05:48,410
Sa krahasime?

117
00:05:48,410 --> 00:05:49,197
Shtatë, e drejtë?

118
00:05:49,197 --> 00:05:51,405
Sepse në qoftë se ka tetë
njerëzit por ju keni palë

119
00:05:51,405 --> 00:05:53,880
ata dhe ju mbani lëviz
një hop në të djathtë,

120
00:05:53,880 --> 00:05:56,060
ju nuk jeni do të ketë tetë
krahasime, sepse ju nuk mund të krahasohen

121
00:05:56,060 --> 00:05:59,226
një element kundër vetvetes, ose ajo do të
vetëm të jetë i kotë, kështu që ju keni shtatë.

122
00:05:59,226 --> 00:06:01,290
Ose më në përgjithësi, në qoftë se
ne kemi n njerëz, ne

123
00:06:01,290 --> 00:06:04,300
bëjë n minus 1 krahasime
me flluskë lloji.

124
00:06:04,300 --> 00:06:08,150
>> Pra, le të konsiderojmë tani se sa e mirë apo
flluskë keq lloj të vërtetë ishte, dhe të përpiqemi

125
00:06:08,150 --> 00:06:13,570
për të dhënë vetes fjalorin me
e cila për të algoritme të kritikuar si kjo,

126
00:06:13,570 --> 00:06:14,430
dhe së shpejti tonat.

127
00:06:14,430 --> 00:06:16,970
Pra kalimin e parë përmes
lloj flluskë, hera e parë

128
00:06:16,970 --> 00:06:20,909
Kam ecur nga e majta në të djathtë nëpër
fazë, mori me n minus 1 krahasime.

129
00:06:20,909 --> 00:06:22,950
Dhe kjo do të jetë e mia
njësi të masës, e drejtë?

130
00:06:22,950 --> 00:06:26,170
Unë kam qenë lloj i folur dhe shëtitës,
disi të shpejtë, disi i ngadaltë,

131
00:06:26,170 --> 00:06:29,300
kështu duke numëruar numrin tim të sekonda
nuk është veçanërisht e thënë,

132
00:06:29,300 --> 00:06:32,260
por numërimi numrin e
operacionet që kam bërë të hënën,

133
00:06:32,260 --> 00:06:35,900
krahasuar dy njerëz, që ndihet
si një njësi e bukur e masës.

134
00:06:35,900 --> 00:06:40,980
>> Pra, n minus 1 hapa për herë të parë,
por pastaj çfarë ndodhi pas kësaj?

135
00:06:40,980 --> 00:06:46,610
Çfarë është një kokë e një të kaluar
përmes një listë ndryshe shtëpiake i pa klasifikuar?

136
00:06:46,610 --> 00:06:49,840
Çfarë mund të thoni në lidhje me elementin
që ishte të gjithë rrugën atje?

137
00:06:49,840 --> 00:06:51,300
Po?

138
00:06:51,300 --> 00:06:52,870
Kjo ishte elementi më i madh, e drejtë?

139
00:06:52,870 --> 00:06:55,710
Numri tetë, edhe pse ajo
filluar këtu, çdo herë që unë

140
00:06:55,710 --> 00:06:57,860
krahasuar atë kundër
një fqinj, ajo mbajti

141
00:06:57,860 --> 00:07:00,480
bubbling deri në të djathtë
anën e listës.

142
00:07:00,480 --> 00:07:02,710
Dhe me të vërtetë, kjo është ajo ku
algorithm merr emrin e vet.

143
00:07:02,710 --> 00:07:07,630
>> Tani nga kjo logjikë, sa krahasimet
duhet ta bëjë në të dytën

144
00:07:07,630 --> 00:07:09,800
Unë të bëjë që të kalojë nga e majta në të djathtë?

145
00:07:09,800 --> 00:07:10,730
n minus 2, e drejtë?

146
00:07:10,730 --> 00:07:14,297
Ajo thjesht do të jetë humbur kohën time nëse unë
mbani krahasuar tetë kundër dikujt

147
00:07:14,297 --> 00:07:16,630
tjetër, sepse ne tashmë e dimë
ajo ishte në vendin e duhur.

148
00:07:16,630 --> 00:07:19,760
Pra, kjo është pak e një
optimization, kështu që të kalojë e ardhshme

149
00:07:19,760 --> 00:07:23,899
do të jetë plus n minus dy hapa,
ku n është numri i njerëzve.

150
00:07:23,899 --> 00:07:26,940
Tani ju mund të lloj të nxjerrim, madje edhe
në qoftë se ju nuk jeni një shkencëtar kompjuteri,

151
00:07:26,940 --> 00:07:27,680
se si kjo përfundon.

152
00:07:27,680 --> 00:07:31,259
Në fund të këtij algoritmi, me sa duket
ju keni marrë vetëm një krahasim i majtë.

153
00:07:31,259 --> 00:07:33,800
Ju duhet të lloj të rregulluar
fillimi i listës në rastin e dy

154
00:07:33,800 --> 00:07:36,540
dhe një janë jashtë rendit
dhe duhet të jetë një dhe dy,

155
00:07:36,540 --> 00:07:40,330
kështu që kjo fundeve jashtë në
plus 1 Krahasimi i formës së prerë.

156
00:07:40,330 --> 00:07:44,500
>> Tani dot, dot, dot lloj valëve është
duart në disa nga juicier detaje,

157
00:07:44,500 --> 00:07:46,452
por le të vetëm të shkojnë përpara dhe të thjeshtojë.

158
00:07:46,452 --> 00:07:48,660
Nëse ju kujtohet nga lartë
shkollë, sinqerisht, një shumë prej jush

159
00:07:48,660 --> 00:07:50,340
kishin libra të matematikës që kishin
një mashtrojnë pak fletë

160
00:07:50,340 --> 00:07:52,550
për të mbuluar para ose
mbuluar mbrapa që ju tregoi

161
00:07:52,550 --> 00:07:56,400
summations çfarë seri si
kjo në fund të fundit shtuar deri.

162
00:07:56,400 --> 00:07:59,600
Në rastin e përgjithshëm, në qoftë se ju keni një
variabël si n, dhe në të vërtetë kjo,

163
00:07:59,600 --> 00:08:01,634
në qoftë se keni shikuar tuaj
Libri i math shkollës së vjetër,

164
00:08:01,634 --> 00:08:04,050
ju do të shihni se kjo në të vërtetë
shton deri në këtë shumë këtu,

165
00:08:04,050 --> 00:08:07,970
n herë n minus 1 të gjitha të ndara nga 2.

166
00:08:07,970 --> 00:08:11,172
Kështu që tani për tani më lejoni vetëm të përcaktojnë
kjo është e vërtetë, kështu që për një hap të besimit,

167
00:08:11,172 --> 00:08:12,880
kjo është ajo që kjo përmbledh
deri në, dhe ne mund të

168
00:08:12,880 --> 00:08:14,341
të provojë se në një rast më të përgjithshëm.

169
00:08:14,341 --> 00:08:15,590
Por tani le të zgjerohet këtë.

170
00:08:15,590 --> 00:08:19,920
Pra, le të shumëfishohen këtë, kështu që është e
n katror, ​​minus n, të gjithë të ndarë nga 2.

171
00:08:19,920 --> 00:08:23,200
Kjo është me të vërtetë katror n,
ndarë nga 2, minus n mbi 2,

172
00:08:23,200 --> 00:08:25,010
kështu që është e gjitha e bukur dhe interesante.

173
00:08:25,010 --> 00:08:27,060
Por çfarë ndodh nëse ne
tani plug-në vlerë?

174
00:08:27,060 --> 00:08:29,724
Supozoni se unë nuk kanë tetë
njerëz, por thonë se një milion.

175
00:08:29,724 --> 00:08:31,890
Dhe një milion vetëm për shkak
kjo është një numër goxha i madh,

176
00:08:31,890 --> 00:08:34,039
le të plug atë in dhe të shikoni se çfarë ndodh.

177
00:08:34,039 --> 00:08:39,039
Pra, nëse unë plug një milion në atë formulë
Unë jam duke shkuar për të marrë një milion katror,

178
00:08:39,039 --> 00:08:42,868
ndarë nga 2, minus një
milion, ndarë nga 2.

179
00:08:42,868 --> 00:08:44,159
Tani çfarë po që do të barabartë?

180
00:08:44,159 --> 00:08:47,354
Pra 500 miliardë, minus 500.000.

181
00:08:47,354 --> 00:08:49,270
Dhe në qoftë se unë të bëjë në fakt
që matematikë jashtë, që do të thotë

182
00:08:49,270 --> 00:08:53,920
se zgjidhja e një milion
njerëzit me lloj flluskë

183
00:08:53,920 --> 00:09:01,800
mund të marrë më 499.999.500.000
hapa ose krahasimet në fund,

184
00:09:01,800 --> 00:09:02,900
ne jemi vetëm nxjerrjen.

185
00:09:02,900 --> 00:09:06,860
>> Kjo ndihet shumë e ngadaltë, por sinqerisht
matur një kontribut të veçantë

186
00:09:06,860 --> 00:09:09,160
si kjo, nuk është e gjitha që domethënëse.

187
00:09:09,160 --> 00:09:14,050
Por në të vërtetë ai nuk sugjeron se si n
merr më të mëdha dhe më të madhe, ky algoritëm

188
00:09:14,050 --> 00:09:16,280
lloj ndihet keq dhe
më keq, apo ju me të vërtetë

189
00:09:16,280 --> 00:09:20,450
fillojnë të ndjejnë dhimbjen e që
exponentiation, se n katror,

190
00:09:20,450 --> 00:09:21,770
që përbën deri shumë shpejt.

191
00:09:21,770 --> 00:09:25,340
Dhe ky detaj nuk është
humbur në njerëz, në fakt

192
00:09:25,340 --> 00:09:29,640
disa vjet më parë një senator të caktuar i cili ishte
fushata, u ul për një intervistë

193
00:09:29,640 --> 00:09:32,180
me Eric Google
Schmidt, CEO në atë kohë,

194
00:09:32,180 --> 00:09:36,380
dhe u kundërshtua me një pyetje
ashtu si ne jemi duke eksploruar sot.

195
00:09:36,380 --> 00:09:38,468
Le të bëjmë një vështrim.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO Playback]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Ju jeni këtu
në Google, dhe unë si

198
00:09:48,560 --> 00:09:53,382
për të menduar e presidencës
si një intervistë për punë.

199
00:09:53,382 --> 00:09:56,434
Tani, është e vështirë për të marrë
një punë si president,

200
00:09:56,434 --> 00:09:58,100
dhe ju jeni duke kaluar nëpër masa të rrepta tani.

201
00:09:58,100 --> 00:10:01,860
Është gjithashtu e vështirë për të marrë një punë në Google.

202
00:10:01,860 --> 00:10:05,490
Ne kemi pyetje, dhe ne
bëjnë pyetje kandidatët tanë,

203
00:10:05,490 --> 00:10:09,770
dhe kjo është nga Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
What-- ju djema mendoni se unë jam
shaka, ajo është e drejtë këtu.

205
00:10:14,760 --> 00:10:17,930
Cila është mënyra më efikase për të
zgjidhur një milion numra të plotë 32-bit?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -Me Fal, maybe--

209
00:10:25,200 --> 00:10:27,400
>> Jo, jo, jo.

210
00:10:27,400 --> 00:10:30,700
Unë mendoj se lloj flluskë
do të jetë mënyra e gabuar për të shkuar.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -Come Në, i cili i tha atij këtë?

213
00:10:38,180 --> 00:10:40,590
Unë nuk e shoh kompjuter
shkenca në sfond tuaj.

214
00:10:40,590 --> 00:10:42,130
>> -We've Mori spiunë tona në atje.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> OK, le të kërkojë një tjetër
pyetje intervistë.

217
00:10:48,444 --> 00:10:49,300
>> [VIDEO END rishikim]

218
00:10:49,300 --> 00:10:52,290
>> Gjuha: Pra, duke folur për
numra specifike edhe pse,

219
00:10:52,290 --> 00:10:53,890
nuk do të jetë mbi të gjitha që të dobishme.

220
00:10:53,890 --> 00:10:56,810
Kjo nuk është një mësim i jetës që flluskë
lloj, duke pasur parasysh një milion inputeve,

221
00:10:56,810 --> 00:10:58,590
mund të marrin deri në 500 miliardë hapa.

222
00:10:58,590 --> 00:11:01,120
Ju nuk mund të vërtetë të përgjithësoj
shumë në mënyrë efektive nga se

223
00:11:01,120 --> 00:11:03,560
dhe të marrin vendime të mira të projektimit
kur shkruani programe.

224
00:11:03,560 --> 00:11:07,070
Pra, le të përqëndrohet edhe pse në atë se si
ne mund të thjeshtojë këtë rezultat.

225
00:11:07,070 --> 00:11:11,780
>> Kështu që unë e kam theksuar në të verdhë këtu
rezultat i n katror ndarë nga 2,

226
00:11:11,780 --> 00:11:14,330
kështu që një milion katror
ndarë me 2, dhe pastaj

227
00:11:14,330 --> 00:11:16,710
Unë e kam theksuar se çfarë
përgjigje i fundit ishte

228
00:11:16,710 --> 00:11:20,180
dikur ne zbritet off ndarë n me 2.

229
00:11:20,180 --> 00:11:24,850
Dhe kërkesa unë jam duke shkuar për të bërë tani është,
kush kujdeset dreq nëse ju zbres off

230
00:11:24,850 --> 00:11:30,060
a n vjetër pak mbi 2 kur i pari
pjesë e kësaj formule është aq shumë më e madhe?

231
00:11:30,060 --> 00:11:33,910
Ajo dominon tjera
Termi, n katror ndarë nga 2

232
00:11:33,910 --> 00:11:37,510
është aq shumë më e madhe, në mënyrë të qartë, si
n merr e madhe si një milion,

233
00:11:37,510 --> 00:11:41,450
se a ka me të vërtetë një ndryshim të madh në
në fund të ditës në mes të 500 miliardë

234
00:11:41,450 --> 00:11:45,730
dhe 499.999.500.000?

235
00:11:45,730 --> 00:11:46,349
Jo me të vërtetë.

236
00:11:46,349 --> 00:11:48,640
Dhe kështu që ajo që ne jemi duke shkuar për
bëni si shkencëtarët kompjuter është

237
00:11:48,640 --> 00:11:53,270
injorojë ato terma më të ulët e rendit dhe
të marrë diçka si kjo dhe të vërtetë

238
00:11:53,270 --> 00:11:56,050
vetëm të lehtësuar atë të
term që do të rëndësi.

239
00:11:56,050 --> 00:12:00,315
Sa më i madh vendos tonë të dhënave të merrni, aq më e madhe
Bazat e të dhënave tona të marrë, faqet web më shumë

240
00:12:00,315 --> 00:12:02,690
ne kemi për të kërkuar, më të
miq keni në Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Si n merr më të madhe, ne jemi me të vërtetë
do të kujdesen për më të madhe

242
00:12:07,340 --> 00:12:11,560
Termi në çdo analizë të tillë të
performancës algoritme tonë.

243
00:12:11,560 --> 00:12:16,230
Dhe unë jam duke shkuar për të thënë, ju e dini se çfarë,
flluskë lloj është në rendin e O të madhe,

244
00:12:16,230 --> 00:12:18,060
në mënyrë të n katror.

245
00:12:18,060 --> 00:12:20,090
Kjo nuk është saktësisht n
katror siç kemi parë,

246
00:12:20,090 --> 00:12:22,060
por që me të vërtetë kujdeset
për ato terma më të vogla,

247
00:12:22,060 --> 00:12:24,390
dhe sinqerisht, që me të vërtetë
kujdeset nëse ne ndani me 2?

248
00:12:24,390 --> 00:12:25,870
Kjo është vetëm një faktor konstant.

249
00:12:25,870 --> 00:12:29,480
Dhe është 500 miliardë kundrejt 250
miliardë vërtetë se i madh i një marrëveshje?

250
00:12:29,480 --> 00:12:32,190
Unë mund vetëm të presim një vit,
le laptop tim fjalë për fjalë

251
00:12:32,190 --> 00:12:34,810
të marrë dy herë më shpejt në hardware,
dhe atë gjë e diferencës

252
00:12:34,810 --> 00:12:36,650
vetëm shkon larg natyrisht me kalimin e kohës.

253
00:12:36,650 --> 00:12:39,300
>> Ajo që ne intereson është
shprehja, pjesa

254
00:12:39,300 --> 00:12:42,489
e shprehjes që do të ndryshojnë
si të dhëna jonë merr më të mëdha.

255
00:12:42,489 --> 00:12:45,280
Dhe me të vërtetë, në botën e vërtetë,
kjo është ajo që po ndodh gjithnjë e më

256
00:12:45,280 --> 00:12:48,330
është inputet për problemet tona dhe të
algoritme janë të bëhet më e madhe.

257
00:12:48,330 --> 00:12:53,470
Pra, O i madh do të jetë simbol,
simbol asymptotic, që ne vetëm

258
00:12:53,470 --> 00:12:57,160
përdorin si shkencëtarët kompjuterike për të përshkruar
performancës, ose koha drejtimin,

259
00:12:57,160 --> 00:12:58,130
e nje algoritmi.

260
00:12:58,130 --> 00:13:00,800
Kështu që ne mund të krahasohen algoritme
në kompjuterë të ndryshëm shkruara

261
00:13:00,800 --> 00:13:04,170
nga njerëz të ndryshëm, duke përdorur
disa metrikë krejtësisht të ngjashme

262
00:13:04,170 --> 00:13:07,557
si numri i krahasimeve të jeni
duke e bërë, ose ndoshta numrin e këmbime

263
00:13:07,557 --> 00:13:08,140
ju jeni duke bërë.

264
00:13:08,140 --> 00:13:11,910
>> Ajo që ne nuk jemi duke shkuar për
akuzë është sasia e kohës

265
00:13:11,910 --> 00:13:13,981
që kalon në orën
në mur mënyrë tipike.

266
00:13:13,981 --> 00:13:16,230
Ajo që ne nuk jemi duke shkuar për t'u shqetësuar
rreth është se sa memorie

267
00:13:16,230 --> 00:13:17,820
ju jeni duke përdorur sot në
paktën, edhe pse kjo është

268
00:13:17,820 --> 00:13:19,370
tjetër burim ne mund matur.

269
00:13:19,370 --> 00:13:23,610
Ne jemi duke shkuar për të përpiqen për të bazojnë analizat tona
në vetëm operacionet themelore, ato,

270
00:13:23,610 --> 00:13:25,930
sinqerisht, që ju mund të shihni më me sy.

271
00:13:25,930 --> 00:13:30,700
Pra, me diçka si O madh të n
katror, ​​unë pretendojnë se o të n katror

272
00:13:30,700 --> 00:13:35,820
është një kufi i sipërm në të ashtuquajturat
drejtimin kohën e flluskë lloji.

273
00:13:35,820 --> 00:13:38,820
Me fjalë të tjera, në qoftë se ju
donte të thonë se nuk ka

274
00:13:38,820 --> 00:13:41,370
ky kufi i sipërm për sa
hapa një algoritmi mund të marrë,

275
00:13:41,370 --> 00:13:46,240
ajo do të jetë në O madh të n
katror në këtë rast, një kufi i sipërm.

276
00:13:46,240 --> 00:13:49,710
>> Çka nëse unë në vend të ndryshojë
histori të mos jetë në lidhje flluskë lloji,

277
00:13:49,710 --> 00:13:50,910
por për këtë kufi i sipërm.

278
00:13:50,910 --> 00:13:54,030
A mund të mendoni për një algoritmi
që ne i kemi shikuar tashmë

279
00:13:54,030 --> 00:13:59,530
cilit kufirin maksimal, maksimale
masë e kohës apo operacioneve,

280
00:13:59,530 --> 00:14:04,300
do të thuhet që do të kufizohet
nga n, një funksion linear,

281
00:14:04,300 --> 00:14:07,260
jo një katror që është lakuar?

282
00:14:07,260 --> 00:14:10,780
Çfarë është një algoritmi që
gjithmonë merr jo më shumë

283
00:14:10,780 --> 00:14:12,860
se si hapat N, ose
Hapa 2n, apo hapa 3n?

284
00:14:12,860 --> 00:14:13,360
Po?

285
00:14:13,360 --> 00:14:15,030
>> Audienca: Gjetja
Numri më i madh në një listë?

286
00:14:15,030 --> 00:14:16,930
>> Gjuha: Perfect, duke gjetur
numri më i madh në një listë.

287
00:14:16,930 --> 00:14:18,940
Nëse unë jam duke dhënë një listë të
njerëzit për shembull,

288
00:14:18,940 --> 00:14:21,440
secili i cili është duke zhvilluar një numër,
çfarë është numri maksimal

289
00:14:21,440 --> 00:14:23,770
hapash duhet të marrë mua,
një person i arsyeshëm i zgjuar,

290
00:14:23,770 --> 00:14:27,530
për të gjetur personin më të madhe në këtë listë?

291
00:14:27,530 --> 00:14:28,100
n, e drejtë?

292
00:14:28,100 --> 00:14:31,320
Sepse në rastin më të keq, kur
mund të jetë vlera më e madhe?

293
00:14:31,320 --> 00:14:32,700
E drejta, të gjitha rrugën në fund.

294
00:14:32,700 --> 00:14:34,575
Pra, në rastin më të keq
sipërme të detyruar, unë mund

295
00:14:34,575 --> 00:14:36,450
kanë për të shkuar gjatë gjithë rrugës
mbi këtu dhe të jetë si,

296
00:14:36,450 --> 00:14:39,170
oh, këtu është numri tetë,
apo çfarëdo që vlerë të.

297
00:14:39,170 --> 00:14:41,330
Tani ajo vetëm do të ishte budallallëk
në qoftë se unë do mbajtur, e drejtë?

298
00:14:41,330 --> 00:14:43,840
Duke kërkuar për elemente gjithnjë e më shumë
në qoftë se i fundit prej tyre është atje?

299
00:14:43,840 --> 00:14:45,340
Pra me siguri, n është një kufi i sipërm.

300
00:14:45,340 --> 00:14:47,420
Unë nuk kam nevojë për të marrë
më shumë hapa se kaq.

301
00:14:47,420 --> 00:14:51,580
>> Pra, çfarë nëse në vend të kësaj kam propozuar që
ka algoritme në këtë botë që

302
00:14:51,580 --> 00:14:57,750
kanë një kohë running që është
kufizohet nga O madh të log n, hyni n?

303
00:14:57,750 --> 00:15:00,390
Ku kemi parë këtë më parë?

304
00:15:00,390 --> 00:15:00,890
Po?

305
00:15:00,890 --> 00:15:03,309
>> Audienca: Në problemin librin e telefonit?

306
00:15:03,309 --> 00:15:04,850
Gjuha: Ashtu si problemin librin e telefonit.

307
00:15:04,850 --> 00:15:07,754
Cili ishte masë e si
shumë kohë ose sa lotët e punon

308
00:15:07,754 --> 00:15:10,170
mori mua për të gjetur dikë si
Mike Smith në librin e telefonit?

309
00:15:10,170 --> 00:15:13,212
Ne pretendoi se ishte log n, dhe
edhe nëse të panjohur ose ajo është e

310
00:15:13,212 --> 00:15:15,170
një mjegullt pak atë që një
logaritmi apo eksponent ishte,

311
00:15:15,170 --> 00:15:17,650
vetëm mos harroni se log n
përgjithësisht referohet procesit,

312
00:15:17,650 --> 00:15:20,790
në këtë rast, e ndarë
diçka në gjysmë përsëri, dhe përsëri,

313
00:15:20,790 --> 00:15:25,790
dhe përsëri, dhe përsëri, të tilla që të
merr gjithnjë e më të vogla si ju bëni këtë.

314
00:15:25,790 --> 00:15:28,470
>> Pra, hyni i referohet n, i sigurt,
për shembull librin e telefonit,

315
00:15:28,470 --> 00:15:32,662
për kërkim binar në teori, kur ne
kishte dyert virtuale në bord,

316
00:15:32,662 --> 00:15:34,370
ose kur Sean ishte
kërkoni për diçka.

317
00:15:34,370 --> 00:15:37,374
Nëse ai kishte përdorur kërko binar, hyni n
do të ishte e sipërme të lidhura nga sa

318
00:15:37,374 --> 00:15:38,040
Koha që merr.

319
00:15:38,040 --> 00:15:44,027
Por ato algoritme që u zhvillua në
Identifikohu n supozohet çfarë detaj kyç?

320
00:15:44,027 --> 00:15:45,360
Kjo listë është renditur, e drejtë?

321
00:15:45,360 --> 00:15:47,789
Algorithm juaj është e gabuar nëse
input juaj nuk zgjidhet,

322
00:15:47,789 --> 00:15:49,830
por ju jeni duke përdorur
diçka si kërkim binar

323
00:15:49,830 --> 00:15:51,704
sepse ju mund të kërcejnë
drejtë mbi elementin

324
00:15:51,704 --> 00:15:53,600
pa e kuptuar se është me të vërtetë atje.

325
00:15:53,600 --> 00:15:55,600
>> Tani çfarë mund të thotë kjo, o të madh të një?

326
00:15:55,600 --> 00:15:59,117
Kjo nuk do të thotë se algoritmi tuaj
merr një dhe vetëm një hap,

327
00:15:59,117 --> 00:16:01,200
ai thjesht do të thotë ajo merr një
Numri i vazhdueshëm i hapave.

328
00:16:01,200 --> 00:16:04,060
Ndoshta është 1, ndoshta është
10, ndoshta është 1000,

329
00:16:04,060 --> 00:16:07,750
por kjo është e pavarur nga
madhësia e problemit.

330
00:16:07,750 --> 00:16:10,850
Pa marrë parasysh se sa e madhe n është,
një algorithm Koha konstante

331
00:16:10,850 --> 00:16:12,747
gjithmonë merr numër të njëjtë të hapave.

332
00:16:12,747 --> 00:16:15,080
Pra, çfarë mund të jetë një algoritmi
kemi folur ose vetëm

333
00:16:15,080 --> 00:16:20,418
intuitive që vjen për ju që
gjithmonë shkon në të ashtuquajturin kohë të vazhdueshme?

334
00:16:20,418 --> 00:16:20,918
Po?

335
00:16:20,918 --> 00:16:22,001
>> Audienca: Add dy numra.

336
00:16:22,001 --> 00:16:25,320
Gjuha: Add dy numra,
2 plus 2 është e barabartë me 4, bëhet.

337
00:16:25,320 --> 00:16:27,227
Kështu që mund të punojnë, çfarë tjetër?

338
00:16:27,227 --> 00:16:28,560
Si në lidhje me botën e më reale, vërtet?

339
00:16:28,560 --> 00:16:30,686
>> Audienca: Gjetja
Gjëja e parë në një listë.

340
00:16:30,686 --> 00:16:32,810
Gjuha: Gjetja e parë
element në një listë, i sigurt.

341
00:16:32,810 --> 00:16:34,540
Ne kemi qenë në të vërtetë duke folur
rreth vargjeve tashmë,

342
00:16:34,540 --> 00:16:36,540
si mendoni ju merrni në
Elementi i parë në një grup,

343
00:16:36,540 --> 00:16:40,465
pa marrë parasysh se sa kohë
array është në kodin e C?

344
00:16:40,465 --> 00:16:43,090
Ju vetëm përdorni si kllapa
zero simbol, bam, ju jeni atje.

345
00:16:43,090 --> 00:16:46,120
Dhe vërtet vargjeve, si një mënjanë,
Mbështetja diçka e njohur përgjithësisht

346
00:16:46,120 --> 00:16:49,240
si qasje të rastit, e gjallë
kujtesës, sepse ju mund të fjalë për fjalë

347
00:16:49,240 --> 00:16:50,284
hidhen në çdo vend një.

348
00:16:50,284 --> 00:16:52,700
Ne mund ta bëjmë këtë edhe më thjesht
ne mund të Rewind në javë zero

349
00:16:52,700 --> 00:16:53,900
kur ne e bëmë Scratch.

350
00:16:53,900 --> 00:16:59,707
Sa kohë u desh për
thonë bllok në Scratch për të ekzekutuar?

351
00:16:59,707 --> 00:17:00,790
Vetëm koha e konstante, e drejtë?

352
00:17:00,790 --> 00:17:03,960
Thuaj diçka, thonë
diçka, kjo nuk ka rëndësi

353
00:17:03,960 --> 00:17:07,359
si Scratches mëdha botërore është, është gjithmonë
do të marrë të njëjtën sasi e kohës

354
00:17:07,359 --> 00:17:08,490
të thjesht të thonë diçka.

355
00:17:08,490 --> 00:17:11,089
>> Pra, kjo është koha konstante,
por ajo që është flip side?

356
00:17:11,089 --> 00:17:13,030
Nëse kjo ishte e sipërme
caqeve, çka nëse ne duam

357
00:17:13,030 --> 00:17:17,089
për të përshkruar kufijtë më të ulët
e algoritmeve tona running kohë?

358
00:17:17,089 --> 00:17:19,852
Pothuajse një rast më të mirë
potencialisht, në qoftë se ju do,

359
00:17:19,852 --> 00:17:23,060
edhe pse këto terma do të mund të aplikojnë për të mirë
raste, raste më të rënda, rastet mesatare më shumë

360
00:17:23,060 --> 00:17:26,359
në përgjithësi, por le të vetëm të përqëndrohet
më të mëdhenj të ulëta në përgjithësi.

361
00:17:26,359 --> 00:17:31,920
Çfarë është një algoritmi që ka
një detyruar të ulët i hapa n,

362
00:17:31,920 --> 00:17:33,350
apo hapa 2n, apo hapa 3n?

363
00:17:33,350 --> 00:17:36,241
Disa faktor hapa n,
që është e saj më të ulët i lidhur.

364
00:17:36,241 --> 00:17:36,740
Po?

365
00:17:36,740 --> 00:17:37,910
>> Audienca: Bubble lloj?

366
00:17:37,910 --> 00:17:41,610
>> Gjuha: Bubble lloj merr
ju hapa n minimalisht, pse?

367
00:17:41,610 --> 00:17:42,279
Pse është se?

368
00:17:42,279 --> 00:17:45,320
Pse duhet që të fillojë për të ardhur tek ju
intuitive, jo edhe në qoftë se ajo bën vetëm

369
00:17:45,320 --> 00:17:46,530
ende?

370
00:17:46,530 --> 00:17:47,030
Po?

371
00:17:47,030 --> 00:17:47,990
>> Audienca: [padëgjueshme].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
Gjuha: Pikërisht.

374
00:17:52,360 --> 00:17:55,810
Në skenarin më të mirë të mundshëm të
lloj flluskë, dhe një shumë e algoritmeve,

375
00:17:55,810 --> 00:17:58,769
në qoftë se unë ju dorë tetë persona
të cilët janë të renditura tashmë,

376
00:17:58,769 --> 00:18:00,560
kjo do të ishte qesharake
për ju, algorithm,

377
00:18:00,560 --> 00:18:02,202
për të shkuar mbrapa dhe me radhë
më shumë se një herë, drejtë?

378
00:18:02,202 --> 00:18:04,285
Sepse sa më shpejt që ju
ecin nëpër lista një herë,

379
00:18:04,285 --> 00:18:08,090
ju duhet të kuptojnë, oh, kam bërë asnjë
këmbime, kjo listë është e renditura, dalje.

380
00:18:08,090 --> 00:18:09,700
Por që do të ju merr n hapa.

381
00:18:09,700 --> 00:18:12,033
>> Dhe anasjelltas, çfarë është një tjetër
mënyrë e të menduarit në lidhje me të?

382
00:18:12,033 --> 00:18:15,240
Bubble lloj është një omega,
mënyrë që të flasin, e n,

383
00:18:15,240 --> 00:18:19,050
sepse në qoftë se ju shikoni në
më pak se n elemente, çfarë

384
00:18:19,050 --> 00:18:23,009
është çështje themelore atje?

385
00:18:23,009 --> 00:18:24,550
Ju nuk e di nëse është e renditura, të drejtë.

386
00:18:24,550 --> 00:18:26,800
Ne njerëzit shikim mund të në tetë
njerëzit dhe të jetë si, oh, është e renditura,

387
00:18:26,800 --> 00:18:28,430
që nuk ka marrë mua n hapa, por ajo e bëri.

388
00:18:28,430 --> 00:18:30,810
Sytë tuaj, edhe pse ju lloj
e kanë një fushë e madhe e vizionit,

389
00:18:30,810 --> 00:18:33,184
ju shikuar në tetë elementeve,
ju shikuar në tetë njerëz,

390
00:18:33,184 --> 00:18:34,610
që është tetë hapa në mënyrë efektive.

391
00:18:34,610 --> 00:18:38,612
Dhe vetëm në qoftë se të ecja gjithë
Lista mund ta kuptojnë, po, të renditura.

392
00:18:38,612 --> 00:18:41,320
Në qoftë se unë të ndaluar në gjysmë të rrugës duke menduar, të gjithë
të drejtë, është e renditura goxha deri tani,

393
00:18:41,320 --> 00:18:42,520
çfarë janë shanset nuk është renditur?

394
00:18:42,520 --> 00:18:44,186
Kjo nuk algoritme do të jetë e saktë.

395
00:18:44,186 --> 00:18:46,250
Mund të jetë më i shpejtë, por të pasakta.

396
00:18:46,250 --> 00:18:48,500
>> Deri tani ne kemi një mënyrë për të
përshkruar një kufi më të ulët,

397
00:18:48,500 --> 00:18:49,710
dhe ajo që për herë të vazhdueshëm?

398
00:18:49,710 --> 00:18:54,565
Çfarë është një algoritmi që ka një më të ulët
lidhur me kohën e saj drejtimin e një?

399
00:18:54,565 --> 00:18:58,350
1 hap, 2 hapa, 10 hapa, por
konstante, të pavarur nga n,

400
00:18:58,350 --> 00:18:59,310
Madhësia e input?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Po, në shpinë.

403
00:19:04,600 --> 00:19:05,309
>> Audienca: printf?

404
00:19:05,309 --> 00:19:06,183
Gjuha: Çfarë është ajo?

405
00:19:06,183 --> 00:19:07,184
Audienca: printf?

406
00:19:07,184 --> 00:19:07,850
Gjuha: printf.

407
00:19:07,850 --> 00:19:08,400
OK, i sigurt.

408
00:19:08,400 --> 00:19:10,720
Pra, ajo merr një numër të caktuar të hapave.

409
00:19:10,720 --> 00:19:13,170
Dhe unë duhet të now-- tani që
ne jemi duke folur në lidhje me kodin C

410
00:19:13,170 --> 00:19:16,040
dhe nuk Scratch, diçka
si të themi, me printf,

411
00:19:16,040 --> 00:19:17,710
ne duhet të fillojë të marrë të kujdesshëm.

412
00:19:17,710 --> 00:19:21,090
Sepse printf merr
input, kjo është një varg,

413
00:19:21,090 --> 00:19:23,220
dhe vargjet e teknikisht kanë gjatësi.

414
00:19:23,220 --> 00:19:25,530
Pra, në qoftë se ne tani duam të marr
për ju, nëse ju nuk do mend,

415
00:19:25,530 --> 00:19:29,430
teknikisht ne mund të argumentojnë se printf
ka marrë një kontribut ndryshueshme gjatësi,

416
00:19:29,430 --> 00:19:32,270
dhe me siguri ajo mund të marrë më shumë
koha për të shkruar një varg këtë kohë,

417
00:19:32,270 --> 00:19:33,560
se kjo kohë.

418
00:19:33,560 --> 00:19:36,570
>> Pra, çfarë po të kemi parasysh vetëm
klasifikim dhe kërkoni shembuj?

419
00:19:36,570 --> 00:19:40,450
Po në lidhje me Mike Smith në telefon
libër, ose kërko binar në përgjithësi?

420
00:19:40,450 --> 00:19:42,220
Në rastin më të mirë, çfarë mund të ndodhë?

421
00:19:42,220 --> 00:19:45,577
I hapur librin e telefonit dhe, bam,
ka numër Mike Smith.

422
00:19:45,577 --> 00:19:46,660
Unë mund të telefononi atë menjëherë.

423
00:19:46,660 --> 00:19:49,390
>> Mori një hap, ndoshta dy hapa,
por një numër të vazhdueshëm të hapave

424
00:19:49,390 --> 00:19:50,230
nëse kam fat.

425
00:19:50,230 --> 00:19:52,570
Dhe sinqerisht, ne pamë në
E hënë shok klase tuaj

426
00:19:52,570 --> 00:19:54,710
të merrni mjaft me fat dy herë në një rresht.

427
00:19:54,710 --> 00:19:57,050
Dhe kjo ishte me të vërtetë konstante
herë në një mëdhenj të ulët

428
00:19:57,050 --> 00:20:01,280
në algorithm në fjalë për gjetjen e
Numri 50 prapa ato mbyllen

429
00:20:01,280 --> 00:20:01,830
dyert.

430
00:20:01,830 --> 00:20:06,400
>> Tani, si një mënjanë, në qoftë se ju të zbuloni
që të dy O i madh, kufi i sipërm,

431
00:20:06,400 --> 00:20:09,310
dhe omega, më të ulët i lidhur,
janë një në njëjtë, që

432
00:20:09,310 --> 00:20:11,830
është njëjtë formulë në
kllapa, ju gjithashtu mund të

433
00:20:11,830 --> 00:20:15,170
thonë, vetëm të jetë i zbukuruar,
se diçka është në theta

434
00:20:15,170 --> 00:20:18,270
e n apo theta e disa vlera të tjera.

435
00:20:18,270 --> 00:20:20,661
Kjo thjesht do të thotë kur i madh
O dhe omega janë njëjtë.

436
00:20:20,661 --> 00:20:21,910
Tani ajo që për përzgjedhjes lloj?

437
00:20:21,910 --> 00:20:23,400
Le të përdorim këtë fjalor të ri.

438
00:20:23,400 --> 00:20:27,407
Në përzgjedhjes lloj, cilat ishin ne
duke bërë përsëri, dhe përsëri, dhe përsëri?

439
00:20:27,407 --> 00:20:29,990
Unë kam qenë duke shkuar mbrapa dhe me radhë përmes
lista, duke kërkuar për të cilët?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Numër më të vogël.

442
00:20:34,730 --> 00:20:37,560
>> Pra, si shumë hapa, se si
shumë krahasime bëri I

443
00:20:37,560 --> 00:20:43,250
duhet të bëni në mënyrë që të kuptoj se kush
element vogël në lista ishte?

444
00:20:43,250 --> 00:20:44,437
n minus 1, e drejtë?

445
00:20:44,437 --> 00:20:47,770
Sepse në qoftë se unë vetëm të fillojë me atë që unë jam
dhënë dhe unë të fillojnë të krahasuar atë,

446
00:20:47,770 --> 00:20:49,519
pastaj atë apo të saj, atë të
ose të saj, atë apo të saj, unë

447
00:20:49,519 --> 00:20:52,010
vetëm mund palë elemente
bashku n minus 1 herë.

448
00:20:52,010 --> 00:20:55,630
Pra, zgjedhja lloj mënyrë të ngjashme merr
n minus 1 hapa për herë të parë.

449
00:20:55,630 --> 00:20:59,540
>> Sa hapa nuk është marrë mua për të
gjeni elementin e dytë më të vogël?

450
00:20:59,540 --> 00:21:02,920
n minus 2, sepse unë jam duke u memec
në qoftë se unë mbaj duke kërkuar në të njëjtit njerëz

451
00:21:02,920 --> 00:21:06,280
përsëri në qoftë se unë e kam zgjedhur tashmë atë
apo të saj dhe vënien e tyre në vendin e tyre.

452
00:21:06,280 --> 00:21:09,270
Dhe hapi i tretë, n
minus 3, atëherë n minus 4.

453
00:21:09,270 --> 00:21:11,020
Ne e kemi parë këtë model
para, dhe në të vërtetë

454
00:21:11,020 --> 00:21:13,460
Zgjedhja lloj të ngjashme
ka një lidhje të lartë

455
00:21:13,460 --> 00:21:16,210
e n katror nëse ne bëjmë deri atë përmbledhje.

456
00:21:16,210 --> 00:21:19,790
Ajo që është më e ulët i detyruar, zgjedhja lloj i saj?

457
00:21:19,790 --> 00:21:25,350
Minimalisht, sa kohë duhet përzgjedhje
lloj të marrë, si ne definuar atë të hënën?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Propozojë dy opsione.

460
00:21:30,490 --> 00:21:32,360
Ndoshta është n, si më parë.

461
00:21:32,360 --> 00:21:35,040
Ndoshta kjo është katror n, si të
tani është si kufi i sipërm.

462
00:21:35,040 --> 00:21:35,874
>> Audienca: katror n.

463
00:21:35,874 --> 00:21:36,664
Gjuha: n katror.

464
00:21:36,664 --> 00:21:37,368
Pse?

465
00:21:37,368 --> 00:21:40,060
>> Audienca: Sepse ju keni
për të përcaktuar [e padëgjueshme].

466
00:21:40,060 --> 00:21:41,510
>> Gjuha: Pikërisht.

467
00:21:41,510 --> 00:21:45,077
Të paktën siç e përcaktuar përzgjedhjes lloj
se ishte mjaft naive, do të mbajë,

468
00:21:45,077 --> 00:21:46,160
gjeni elementin më të vogël.

469
00:21:46,160 --> 00:21:47,770
Shko përsëri, gjeni elementin më të vogël.

470
00:21:47,770 --> 00:21:49,490
Shko përsëri, gjeni elementin më të vogël.

471
00:21:49,490 --> 00:21:51,700
Nuk ka asnjë lloj
optimization në atje që

472
00:21:51,700 --> 00:21:54,350
mund të më lejoni të ndërpresin shtatzëninë pas
vetëm n apo më shumë hapa.

473
00:21:54,350 --> 00:21:57,080
Pra me të vërtetë, zgjedhja
lloj, omega e n katror.

474
00:21:57,080 --> 00:22:00,667
>> Po në lidhje me llojin e hyrjes, ku unë u
që I është dhënë, dhe pastaj unë plopped atë

475
00:22:00,667 --> 00:22:01,750
ose të saj në vendin e duhur?

476
00:22:01,750 --> 00:22:04,958
Pastaj kam vazhduar për personin e dytë,
plopped atë në vendin e duhur.

477
00:22:04,958 --> 00:22:07,910
Pastaj personi tjetër, plopped
atë apo të saj në vendin e duhur.

478
00:22:07,910 --> 00:22:10,537
Vini re se kjo është shumë e
lineare, mënyrë që të flasin.

479
00:22:10,537 --> 00:22:12,620
Unë jam një vijë e drejtë, unë jam
mos shkuar mbrapa dhe me radhë,

480
00:22:12,620 --> 00:22:16,080
Unë kurrë nuk kam shikuar prapa të vërtetë, por
se çfarë po ndodh, kur kam futur atë

481
00:22:16,080 --> 00:22:20,302
ose saj në fillim të
lista si ne e bëmë të hënën?

482
00:22:20,302 --> 00:22:21,010
Çfarë po ndodh?

483
00:22:21,010 --> 00:22:21,510
Po?

484
00:22:21,510 --> 00:22:23,122
Audienca: [padëgjueshme].

485
00:22:23,122 --> 00:22:24,830
Gjuha: Po, se
ishte kapur, e drejtë?

486
00:22:24,830 --> 00:22:26,746
Ju mund të kujtojnë nga
shokët e klasës tuaj, nëse ata

487
00:22:26,746 --> 00:22:29,670
janë duke bërë çdo lëvizje me
këmbët e tyre, që ishte një operacion.

488
00:22:29,670 --> 00:22:33,610
Pra, nëse do të kishte tre persona këtu dhe
personi i ri i takonte rruga atje,

489
00:22:33,610 --> 00:22:37,360
në një fazë të gjatë si kjo, i sigurt, ai
ose ajo mund të shkojë vetëm deri në fund.

490
00:22:37,360 --> 00:22:40,074
Por në qoftë se ne jemi duke menduar për një
kompjuter dhe një koleksion të kujtesës,

491
00:22:40,074 --> 00:22:41,990
këta njerëz janë duke shkuar
që të ketë për të riorganizimi mbi

492
00:22:41,990 --> 00:22:43,260
për të bërë vend për atë person.

493
00:22:43,260 --> 00:22:46,930
Dhe kështu që n minus 1 shufflings,
n minus 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
minus 3 shufflings është vetëm lloj i
ndodh pas meje, nuk para meje

495
00:22:50,660 --> 00:22:52,710
si më parë, në një kuptim.

499
00:22:52,557 --> 00:22:54,640
Tani si një mënjanë, dhe si
ju mund të keni parë në internet

500
00:22:54,640 --> 00:22:57,699
në qoftë se ju filloni poking rreth në lidhje me
llojet, ka ato kaq shumë të ndryshme

501
00:22:57,699 --> 00:22:59,490
atje, disa prej tyre
mirë se të tjerët.

502
00:22:59,490 --> 00:23:02,200
Në të vërtetë, bogosort është një
që është lloj i argëtim të kërkoni.

503
00:23:02,200 --> 00:23:06,650
Bogosort merr një sërë
numra ose thonë se një kuvertë të kartave,

504
00:23:06,650 --> 00:23:09,870
rastësisht lëvizjet e tyre, dhe
kontrollon nëse ata janë të renditura.

505
00:23:09,870 --> 00:23:12,130
Dhe nëse jo, e bën atë përsëri.

506
00:23:12,130 --> 00:23:14,140
Dhe nëse jo, e bën atë përsëri.

507
00:23:14,140 --> 00:23:15,440
Nëse jo, e bën atë përsëri.

508
00:23:15,440 --> 00:23:17,060
Tepër të trashë.

509
00:23:17,060 --> 00:23:19,520
>> Dhe me të vërtetë, në qoftë se ju lexoni
si artikull Wikipedia,

510
00:23:19,520 --> 00:23:21,200
pseudonimi i tij është lloj budalla.

511
00:23:21,200 --> 00:23:25,180
Kjo përfundimisht do të punojë,
me shpresë, duke pasur kohë të mjaftueshme,

512
00:23:25,180 --> 00:23:28,240
por se sasia e kohës
mund të marrë shumë kohë.

513
00:23:28,240 --> 00:23:31,650
Pra, nëse unë mund të, le të me shpejtësi të gjërave
nga shembull Mary Beth-së më parë,

514
00:23:31,650 --> 00:23:35,150
duke pasur disa elemente më shumë,
por dy procesorë më shumë.

515
00:23:35,150 --> 00:23:37,100
Dy njerëz, nëse ju
nuk do mend bashkuar me mua.

516
00:23:37,100 --> 00:23:40,972
Si për 1 gjatë këtu, dhe
le të go-- askush mbi atje?

517
00:23:40,972 --> 00:23:41,722
Askush atje?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Ju me të zeza
shirt, po, vijnë më poshtë.

520
00:23:44,190 --> 00:23:45,000
Në rregull, si e ke emrin?

521
00:23:45,000 --> 00:23:45,720
>> Audienca: Peter.

522
00:23:45,720 --> 00:23:46,100
>> Gjuha: Çfarë është ajo?

523
00:23:46,100 --> 00:23:46,766
>> Audienca: Peter.

524
00:23:46,766 --> 00:23:49,450
Gjuha: Peter, David, nice to meet you.

525
00:23:49,450 --> 00:23:53,670
Në rregull, ne kemi Pjetër këtu, në qoftë se ju
duan të vijnë mbi tryezë mbi këtu.

526
00:23:53,670 --> 00:23:54,550
Dhe si e ke emrin?

527
00:23:54,550 --> 00:23:55,216
>> Audienca: Elena.

528
00:23:55,216 --> 00:23:55,970
Gjuha: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, nice to meet you.

530
00:23:57,030 --> 00:23:58,060
Elena takuar Pjetrin.

531
00:23:58,060 --> 00:23:59,170
Peter, Elena.

532
00:23:59,170 --> 00:24:02,290
Dhe ne do të duhet Andrew
deri këtu, si edhe, ju lutem.

533
00:24:02,290 --> 00:24:06,107
Dhe sfida juaj është duke shkuar
të jetë për të zgjidhur një kuvertë të kartave.

534
00:24:06,107 --> 00:24:08,190
Dhe në qoftë se të panjohura, kuvertë
e kartave të duhet në fund të fundit

535
00:24:08,190 --> 00:24:11,064
të zgjidhet një diçka të vogël si
kjo ku ne do të bëjmë klubet, atëherë

536
00:24:11,064 --> 00:24:13,660
e maç, atëherë zemrat dhe
diamante, nga ACE si një,

537
00:24:13,660 --> 00:24:15,570
të gjithë rrugën deri te mbreti.

538
00:24:15,570 --> 00:24:20,890
>> Kartat Unë jam duke shkuar për të ju jap
do të jetë 52 në sasi.

539
00:24:20,890 --> 00:24:23,160
Ne jemi duke shkuar për të në mënyrë të ngjashme
Ora ju, në vetëm një moment.

540
00:24:23,160 --> 00:24:26,410
Ne jemi duke shkuar për të hedhur Andrew
deri në ekran këtu,

541
00:24:26,410 --> 00:24:28,170
në mënyrë që të shikojnë si ju bëni këtë.

542
00:24:28,170 --> 00:24:31,070
Dhe në mënyrë që e gjithë kjo
është edhe më e dukshme,

543
00:24:31,070 --> 00:24:33,490
këto janë kartat e kam marrë në Amazon.

544
00:24:33,490 --> 00:24:42,861
Pra, ata janë tashmë të rastësishme
renditura, dhe ne jemi duke shkuar në kohë ju.

545
00:24:42,861 --> 00:24:44,610
Dhe ne jemi duke shkuar për
mbani atë të vërtetë këtë herë,

546
00:24:44,610 --> 00:24:47,820
kështu që ne jemi duke shkuar për të përpiqen për të ju presion
sepse përndryshe kjo do të merrni lodhshme

547
00:24:47,820 --> 00:24:48,460
shpejt.

548
00:24:48,460 --> 00:24:53,860
Nëse ju mund të vazhdojë për të zgjidhur 52
elemente së bashku nëpërmjet disa mjeteve, tani.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Dhe përsëri, si ne shikojnë këto
djema bëni çfarë, në fund

551
00:25:07,180 --> 00:25:10,200
do të prodhojë një e qartë
rezultat, mendoj se për të vërtetë

552
00:25:10,200 --> 00:25:12,962
se si ata po secili duke bërë atë,
se si ju mund të përshkruajnë atë.

553
00:25:12,962 --> 00:25:15,045
Sepse përsëri, këto janë
të gjitha proceseve, algoritme

554
00:25:15,045 --> 00:25:17,090
që kemi marrë për të dhënë si një njeri.

555
00:25:17,090 --> 00:25:22,349
Por ndoshta ju keni pasur gjatë
intuita, shumë kohë para jush edhe

556
00:25:22,349 --> 00:25:24,390
menduar për marrjen e një
klasë shkenca kompjuterike ju

557
00:25:24,390 --> 00:25:27,223
mund të ketë pasur intuitë me
e cila për të zgjidhur probleme si kjo.

558
00:25:27,223 --> 00:25:29,560
Por sapo ju njohin
modelet dhe të fillojnë

559
00:25:29,560 --> 00:25:32,407
për të formalizuar hapat me të cilat
ju jeni zgjidhjen e këtyre problemeve,

560
00:25:32,407 --> 00:25:35,490
ju do të gjeni se ju mund të zgjidhin shumë
më interesante dhe shumë më tepër komplekse

561
00:25:35,490 --> 00:25:39,190
Problemet shpejt.

562
00:25:39,190 --> 00:25:42,351
Pra, dikush nga publiku, çka është
të paktën një element i algoritmin

563
00:25:42,351 --> 00:25:43,350
se ata janë duke përdorur këtu?

564
00:25:43,350 --> 00:25:44,275
>> Audienca: [padëgjueshme]

565
00:25:44,275 --> 00:25:45,150
Gjuha: Çfarë është ajo?

566
00:25:45,150 --> 00:25:47,062
Audienca: By kostum.

567
00:25:47,062 --> 00:25:47,770
Gjuha: By kostum.

568
00:25:47,770 --> 00:25:50,630
Pra, së pari ata janë clustering
gjithë diamantët bashku

569
00:25:50,630 --> 00:25:52,560
me sa duket, të gjithë
zemrat së bashku me sa duket,

570
00:25:52,560 --> 00:25:56,520
dhe kështu me radhë, pa respekt
për numrat në kartat.

571
00:25:56,520 --> 00:26:00,900
Dhe tani ata duket, për shembull,
që do të zgjidhja e tyre sipas numrit.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Shumë mirë.

574
00:26:08,910 --> 00:26:12,370
>> Në rregull, kështu që çfarë do të
të jetë hapi i fundit pastaj këtu?

575
00:26:12,370 --> 00:26:16,950
Pasi ne kemi katër kostume të renditura, ajo që
nuk kemi nevojë të bëjmë për të katër shtyllave

576
00:26:16,950 --> 00:26:20,059
në mënyrë që të arrihet një
renditura kuvertë, mjaft e thjesht?

577
00:26:20,059 --> 00:26:21,350
Pra, ne kemi nevojë për të bashkojë ato përsëri.

578
00:26:21,350 --> 00:26:25,160
>> Pra, ka një ide interesante që
përsëri, guxoj të them, është shumë intuitiv edhe

579
00:26:25,160 --> 00:26:28,140
në qoftë se ju nuk mund të keni shuplakë
se lloj i etiketës mbi të.

580
00:26:28,140 --> 00:26:31,900
Ky nocion themelor i ndarjes
problemi jo në gjysmën e kësaj kohe,

581
00:26:31,900 --> 00:26:33,410
por të paktën në katër pjesë.

582
00:26:33,410 --> 00:26:36,810
Zgjidhja e shumë e shumë
Problemet krejtësisht identike

583
00:26:36,810 --> 00:26:40,480
ne izolimin e njëri tjetrit,
dhe pastaj bashkimi rezultatet.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Dhe, e shkëlqyer, bërë.

586
00:26:50,140 --> 00:26:52,140
Në rregull, një raund i madh
e duartrokitje, në qoftë se ne mund të.

587
00:26:52,140 --> 00:26:56,480
>> [Duartrokitje]

588
00:26:56,480 --> 00:26:59,740
>> Gjuha: Unë nuk kam asnjë ide se çfarë ju do të
bëjnë me këto, por këtu ju shkoni.

589
00:26:59,740 --> 00:27:01,690
Thank you so much.

590
00:27:01,690 --> 00:27:04,660
Pra, le të shohim, dy minuta
dhe tetë sekonda,

591
00:27:04,660 --> 00:27:07,490
në qoftë se ju dëshironi për të sfiduar miqtë tuaj.

592
00:27:07,490 --> 00:27:12,160
Çfarë atëherë do të
të jetë një të marrë larg nga kjo

593
00:27:12,160 --> 00:27:13,830
që ne të mund të levave në përgjithësi?

594
00:27:13,830 --> 00:27:16,080
E pra, mendoni përsëri në
ky grup i numrave,

595
00:27:16,080 --> 00:27:19,060
dhe mendoj se mbrapa tani për disa nga
pseudokod ne kemi shkruar në të kaluarën,

596
00:27:19,060 --> 00:27:22,080
dhe kjo ishte pseudokod për
zgjidhjen e problemit libër telefon.

597
00:27:22,080 --> 00:27:25,150
Ku në pseudokod I
renditura një mënyrë më metodike

598
00:27:25,150 --> 00:27:28,400
për të përshkruar se si unë e bëri një shumë intuitiv
algorithm njeriut i ndarë në telefon

599
00:27:28,400 --> 00:27:31,650
Libri në gjysmë, e përsëris, e përsëris, e përsëris,
derisa të gjej dikë si Mike Smith,

600
00:27:31,650 --> 00:27:33,790
në qoftë se ai është me të vërtetë në librin e telefonit.

601
00:27:33,790 --> 00:27:37,610
>> Por unë lloj përdorur atë që unë do të thërrasë
një qasje shumë përsëritës këtu,

602
00:27:37,610 --> 00:27:42,160
në njoftimin e veçantë e linjës 8 dhe linjë 11.

603
00:27:42,160 --> 00:27:46,750
Këto janë dëshmi të një përsëritës
qasje, një qasje looping,

604
00:27:46,750 --> 00:27:49,040
sepse kjo është pikërisht
sjellje që nxisin.

605
00:27:49,040 --> 00:27:52,910
Ato linja të dy thonë se shkojnë në
lloj linjë tre, dhe ju mund të

606
00:27:52,910 --> 00:27:55,140
mendojnë për se në tuaj
sy mendjen e si një lak.

607
00:27:55,140 --> 00:27:59,080
Kjo ju është thënë që të kthehen deri në hap
tre dhe të përsëritur, përsëri, dhe përsëri,

608
00:27:59,080 --> 00:28:00,010
dhe përsëri.

609
00:28:00,010 --> 00:28:04,410
>> Por çfarë nëse ne levave një ide kyçe
këtu se ne e bëmë jo hera e fundit,

610
00:28:04,410 --> 00:28:10,280
dhe do të thjeshtojë linjë 8 dhe
Linja 11 dhe fqinjët e tyre

611
00:28:10,280 --> 00:28:12,840
pasi vetëm kjo, në të verdhë.

612
00:28:12,840 --> 00:28:16,480
Kjo nuk është krejtësisht shkurtimin
pseudokod shumë,

613
00:28:16,480 --> 00:28:20,530
por është rrënjësisht ndryshon
natyra e algorithm time.

614
00:28:20,530 --> 00:28:24,220
Ajo që unë jam tani duke thënë
në hapin 7, në hapin 10,

615
00:28:24,220 --> 00:28:29,140
është për të kërkuar për Mike
në të njëjtën mënyrë të saktë,

616
00:28:29,140 --> 00:28:31,580
por vetëm në të majtë
gjysma apo gjysmë e drejtë.

617
00:28:31,580 --> 00:28:33,420
>> Pra, me fjalë të tjera, në qoftë se
Unë të fillojë nga një hap,

618
00:28:33,420 --> 00:28:36,150
bie në librin e telefonit, e hapur për mes
e librin e telefonit, shikoni në emrat,

619
00:28:36,150 --> 00:28:39,010
nëse Smith është në mesin
Emri-së, thirrje Mike, tjetër

620
00:28:39,010 --> 00:28:44,340
nëse Smith është parë në libër, hap shtatë
kërkoni për Mike në gjysmën e majtë të librit.

621
00:28:44,340 --> 00:28:47,130
Por kjo lloj ndjehet si
është e lënë mua varur, e drejtë?

622
00:28:47,130 --> 00:28:49,240
Në të verdhë, është një
udhëzim, por si mund të

623
00:28:49,240 --> 00:28:51,870
kërkoni për Mike në të majtë
gjysma e librit të telefonit?

624
00:28:51,870 --> 00:28:54,210
Ku mund ta ketë një
Algoritmi me të cilin unë

625
00:28:54,210 --> 00:28:57,100
mund të kërkoni për dikë si Mike Smith?

626
00:28:57,100 --> 00:28:58,980
E pra, kjo është na ndezur në fytyrë.

627
00:28:58,980 --> 00:29:03,090
Unë mund të vërtetë të përdorni të njëjtën gjë e saktë
Programi në mënyrë efektive duke shkuar deri në krye

628
00:29:03,090 --> 00:29:06,490
përsëri dhe ri-running
të njëjtën gjë e kodit.

629
00:29:06,490 --> 00:29:10,610
>> Pra, edhe pse kjo duhet të ndjehen të
si pak e një përkufizimi ciklike

630
00:29:10,610 --> 00:29:13,480
ku ju jeni duke iu përgjigjur dikujt
pyetje nga vetëm lloj i kërkuar

631
00:29:13,480 --> 00:29:15,990
njëjtën pyetje përsëri,
si pse, pse, pse?

632
00:29:15,990 --> 00:29:21,580
Realiteti është sepse ne kemi koduar vështirë
një çift të linjave të veçanta, hap i 4,

633
00:29:21,580 --> 00:29:25,320
cila është një nëse, dhe hapi 12, e cila
është efektivisht një tjetër degë,

634
00:29:25,320 --> 00:29:30,120
sepse ne kemi ato e masave të përkohshme,
ky algoritëm do të përfundojë në qoftë se ne

635
00:29:30,120 --> 00:29:32,050
gjeni Mike, ose në qoftë se ne nuk bëjmë.

636
00:29:32,050 --> 00:29:36,810
Por në hap 7 dhe 10 tani, ne kemi
atë që ne do të thërrasë një algoritmi rekursive.

637
00:29:36,810 --> 00:29:40,420
Dhe recursion është me të vërtetë një ide e fuqishme
që është një mendje pak lakimi në fillim,

638
00:29:40,420 --> 00:29:42,500
që ne tani mund të aplikojnë si në vijim.

639
00:29:42,500 --> 00:29:46,600
>> Merge lloj do të jetë lloj i fundit që
shohim, të paktën në klasë formalisht.

640
00:29:46,600 --> 00:29:50,040
Dhe kjo është krejtësisht e ndryshme
nga ato tre të fundit, dhe sigurisht

641
00:29:50,040 --> 00:29:52,140
katër fundit në qoftë se ne të përfshijë bogosort.

642
00:29:52,140 --> 00:29:54,810
Ja pseudokod për merge lloj.

643
00:29:54,810 --> 00:30:00,170
Kur në të dhënat e elementeve n, dhënë kështu
një grup i madhësisë n, nëse n është më pak se 2,

644
00:30:00,170 --> 00:30:01,040
kthehen.

645
00:30:01,040 --> 00:30:03,610
Pra, pse nuk kam se
mendje e shëndoshë kontrolloni parë?

646
00:30:03,610 --> 00:30:09,477
Çfarë është implikimi në qoftë se unë ju dorë
një grup gjatësia e të cilit n është më pak se 2?

647
00:30:09,477 --> 00:30:11,060
Është renditura tashmë, natyrisht, e drejtë?

648
00:30:11,060 --> 00:30:13,640
Sepse lista ose ka
një element, që është trivially

649
00:30:13,640 --> 00:30:15,180
renditura për shkak se është
e vetmja gjë atje.

650
00:30:15,180 --> 00:30:18,138
Ose, është e madhësisë zero që do të thotë
nuk ka asgjë për të zgjidhur, kështu nga natyra

651
00:30:18,138 --> 00:30:18,720
ajo është e renditura.

652
00:30:18,720 --> 00:30:20,410
Ka vetëm asgjë të keqe aty.

653
00:30:20,410 --> 00:30:22,310
Pra, kjo është i ashtuquajturi rasti ynë bazë.

654
00:30:22,310 --> 00:30:24,440
>> Kjo është e ngjashme në frymë
me atë që ne e bëmë me Mike.

655
00:30:24,440 --> 00:30:26,023
Nëse Mike-së në librin e telefonit, e quajnë atë.

656
00:30:26,023 --> 00:30:27,740
Nëse ai nuk është aty, të heqë dorë.

657
00:30:27,740 --> 00:30:31,240
Kjo është një të ashtuquajtur rasti bazë, për të siguruar
ky algoritmi në fund të ditës

658
00:30:31,240 --> 00:30:33,540
do të ndalet në rrethana të caktuara.

659
00:30:33,540 --> 00:30:37,890
>> Por këtu është hap i besimit tani, tjetër,
lloj gjysmën e majtë të elementeve,

660
00:30:37,890 --> 00:30:39,740
pastaj lloj të drejtën
gjysma e elementeve,

661
00:30:39,740 --> 00:30:41,189
dhe pastaj bashkojë gjysmave të renditura.

662
00:30:41,189 --> 00:30:43,230
Dhe këtu është ku ai ndjehet
si ne jemi copping jashtë.

663
00:30:43,230 --> 00:30:46,900
Unë e kam pyetur ju për të zgjidhur
n elemente, dhe unë jam i

664
00:30:46,900 --> 00:30:50,712
duke thënë, OK, e atë nga zgjidhja
la dhe klasifikim të drejtë.

665
00:30:50,712 --> 00:30:52,420
Por unë jam duke thënë një të tillë
gjë tjetër, dhe kjo

666
00:30:52,420 --> 00:30:55,530
është tema kryesore duket
në intuitë deri më tani,

667
00:30:55,530 --> 00:30:57,380
ka ky hap i tretë i bashkimit.

668
00:30:57,380 --> 00:31:00,430
Të cilat edhe pse të
duket kështu memec në shpirt,

669
00:31:00,430 --> 00:31:02,320
si vetëm të bashkojë gjëra
së bashku, duket

670
00:31:02,320 --> 00:31:05,380
të jetë një hap i rëndësishëm drejt
reassembly e dy problemeve që

671
00:31:05,380 --> 00:31:07,330
u ndanë në fund të fundit në gjysmë.

672
00:31:07,330 --> 00:31:12,090
>> Pra shkrihen lloj, le ta bëjmë këtë, në qoftë se ju do të
humor mua, me një demonstrim më shumë,

673
00:31:12,090 --> 00:31:14,730
vetëm që të kemi disa
numrat për të punuar me të.

674
00:31:14,730 --> 00:31:19,470
A mund të shkëmbejnë tetë stresin
topa për tetë njerëz?

675
00:31:19,470 --> 00:31:29,320
Në rregull, si në lidhje me ju tre, ju katër
në këtë seksion, pesë, gjashtë, dhe le të

676
00:31:29,320 --> 00:31:30,720
e 7, 8, eja lart.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, po OK.

679
00:31:36,520 --> 00:31:38,640
Minus 8, atje ne do të shkojmë, plus 1.

680
00:31:38,640 --> 00:31:39,150
Excellent.

681
00:31:39,150 --> 00:31:42,000
Të gjitha të vijë të drejtë në dorë, le të
shpejt ju jap numrat.

682
00:31:42,000 --> 00:31:50,800
Numri dy, numri tre, numër katër,
numër pesë, gjashtë, shtatë dhe tetë.

683
00:31:50,800 --> 00:31:52,140
Unë e bëri tetë saktë këtë kohë.

684
00:31:52,140 --> 00:31:56,390
>> OK, kështu që të shkojnë përpara në qoftë se ju mund të, dhe
le të zgjidhur në mënyrë origjinale

685
00:31:56,390 --> 00:31:59,810
që kemi pasur dje cila dukej
si kjo, në qoftë se ju nuk do mend.

686
00:31:59,810 --> 00:32:03,620
Dhe le të bëjë atë para të tabelës.

687
00:32:03,620 --> 00:32:06,510
Në rregull, kështu që bashkohen lloj.

688
00:32:06,510 --> 00:32:08,820
Kjo është ajo ku ajo do
për të marrë lloj i interesante,

689
00:32:08,820 --> 00:32:12,800
sepse unë duket të jetë duke i dhënë veten
aq shumë më pak informacione sot.

690
00:32:12,800 --> 00:32:15,149
>> Pra bashkojë lloj para së gjithash
në të dhënat e elementeve n,

691
00:32:15,149 --> 00:32:18,440
dhe është padyshim jo më pak se dy, është e
tetë, kështu që unë kam disa punë më shumë për të bërë.

692
00:32:18,440 --> 00:32:21,140
Deri tani mendërisht ne si një klasë
tani janë në tjetër degë,

693
00:32:21,140 --> 00:32:22,540
që do të thotë tre hapa.

694
00:32:22,540 --> 00:32:25,017
Së pari, unë kam për të zgjidhur
gjysma e majtë e elementeve.

695
00:32:25,017 --> 00:32:26,350
Pra, si mund të shkojë për të bërë këtë?

696
00:32:26,350 --> 00:32:28,950
E pra, unë jam duke shkuar për të lloj
mendërisht ndajnë listën këtu,

697
00:32:28,950 --> 00:32:30,700
ju nuk keni për të
fizikisht të lëvizur, dhe unë jam i

698
00:32:30,700 --> 00:32:33,180
do të fokusohet vetëm në
gjysma e majtë e elementeve këtu.

699
00:32:33,180 --> 00:32:36,770
Pra, si mund të shkoj për klasifikim
një listë tani e madhësisë katër?

700
00:32:36,770 --> 00:32:38,730
Çfarë është algorithm ime?

701
00:32:38,730 --> 00:32:42,580
Së pari unë kontrolloni është n më pak se dy, jo,
kështu që unë të vazhdojë në tjetër bllok përsëri.

702
00:32:42,580 --> 00:32:43,900
Lloj la gjysmën e elementeve.

703
00:32:43,900 --> 00:32:45,608
>> Deri tani përsëri, mendërisht,
dhe kjo është ajo ku

704
00:32:45,608 --> 00:32:49,550
ju duhet të rritet një shumë të
historia mendore, nëse ju do.

705
00:32:49,550 --> 00:32:51,940
Tani unë jam zgjidhja e majtë
gjysma e pjesës së majtë.

706
00:32:51,940 --> 00:32:57,000
Në rregull, kështu që tani unë e quaj të njëjtë bashkohen tim
sorting algorithm, është n më pak se dy?

707
00:32:57,000 --> 00:33:00,590
Jo, ajo është dy, kështu që unë kam për të zgjidhur
gjysma e majtë, dhe gjysmë të drejtë.

708
00:33:00,590 --> 00:33:02,042
Pra, këtu ne do të shkojmë, lloj gjysmën e majtë.

709
00:33:02,042 --> 00:33:03,750
Pse nuk ju vetëm
të marrë një hap përpara.

710
00:33:03,750 --> 00:33:04,415
Si e keni emrin?

711
00:33:04,415 --> 00:33:04,860
>> Audienca: Darren.

712
00:33:04,860 --> 00:33:05,260
>> Gjuha: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan ka dha përpara.

714
00:33:06,040 --> 00:33:06,748
>> Audienca: Darren.

715
00:33:06,748 --> 00:33:09,000
Gjuha: Darren, bërë.

716
00:33:09,000 --> 00:33:10,090
A ju thoni Darren apo Dan?

717
00:33:10,090 --> 00:33:10,550
>> Audienca: Darren.

718
00:33:10,550 --> 00:33:11,216
>> Gjuha: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren ka rritur
përpara dhe ai është zgjidhet tani.

720
00:33:14,422 --> 00:33:16,130
Dhe kjo është pothuajse një
pretendim pakuptim, e drejtë?

721
00:33:16,130 --> 00:33:18,862
Unë vërtetë nuk duket të jetë arritur
asgjë, por le të vazhdojë.

722
00:33:18,862 --> 00:33:20,820
Tani më lejoni të lloj të drejtën
gjysma e elementeve.

723
00:33:20,820 --> 00:33:21,200
Si e keni emrin?

724
00:33:21,200 --> 00:33:21,690
>> Audienca: Luka.

725
00:33:21,690 --> 00:33:22,273
>> Gjuha: Luka.

726
00:33:22,273 --> 00:33:23,400
Eja, hap përpara.

727
00:33:23,400 --> 00:33:25,640
Done, kam renditura Luka.

728
00:33:25,640 --> 00:33:28,570
Gjysma e majtë është renditur tani dhe
gjysma e drejtë është renditur tani,

729
00:33:28,570 --> 00:33:30,770
por përsëri, ka një hap kyç këtu.

730
00:33:30,770 --> 00:33:32,940
Çfarë tjetër duhet të bëni?

731
00:33:32,940 --> 00:33:33,941
Merge gjysmave të renditura.

732
00:33:33,941 --> 00:33:36,648
Tani ne jemi duke shkuar për të vetëm
të gjithë me radhë dhe në këtë mënyrë,

733
00:33:36,648 --> 00:33:38,620
sepse unë lloj nevojë
disa hapësirë ​​zeroja.

734
00:33:38,620 --> 00:33:40,411
Është pothuajse si këto
djema jeni në një tavolinë,

735
00:33:40,411 --> 00:33:42,460
dhe kam nevojë për një dhomë
për t'i lëvizë më.

736
00:33:42,460 --> 00:33:44,170
Kështu që unë jam duke shkuar për të bashkuar
ju djema nga në kërkim

737
00:33:44,170 --> 00:33:45,960
në gjysmën e majtë dhe pjesën e djathtë.

738
00:33:45,960 --> 00:33:48,740
Dhe që padyshim vjen e para,
la gjysmë apo gjysmë e drejtë?

739
00:33:48,740 --> 00:33:52,710
Pra gjysma e drejtë, kështu që le të lëvizë Luka gjatë
këtu për pozicionin origjinal Darren.

740
00:33:52,710 --> 00:33:57,640
Dhe tani të bashkojë gjysmën e tyre e majtë në,
Darren do të lëvizin drejtë atje.

741
00:33:57,640 --> 00:33:59,750
>> Pra ndjehet si pothuajse
një efekt flluskë lloj,

742
00:33:59,750 --> 00:34:02,482
por algoritmi im themelor,
shumë të ndryshme këtë herë.

743
00:34:02,482 --> 00:34:04,815
Por tani është ku gjërat marrin një
pak i bezdisshëm, sepse ju

744
00:34:04,815 --> 00:34:06,810
duhet të Rewind mendërisht
ku e kam lënë jashtë.

745
00:34:06,810 --> 00:34:09,893
Unë kam bashkuar vetëm gjysmave të renditura,
që do të thotë unë jam ku në algorithm time?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Unë kam për të zgjidhur gjysmën e duhur, e drejtë?

748
00:34:13,770 --> 00:34:15,910
>> Nëse ju rewind, fjalë për fjalë
në video, ju do të

749
00:34:15,910 --> 00:34:18,339
shohim që kemi marrë për këtë
pika e Luka dhe Darren

750
00:34:18,339 --> 00:34:21,370
nga zgjidhja e majtë
gjysma e pjesës së majtë.

751
00:34:21,370 --> 00:34:23,430
Pastaj ne u bashkua ata
gjysmave të renditura, të cilat

752
00:34:23,430 --> 00:34:27,941
do të thotë hapi tjetër është lloj
gjysma e drejtë e pjesës së majtë.

753
00:34:27,941 --> 00:34:29,649
Në rregull, kështu që le të
bëni këtë shumë shpejt.

754
00:34:29,649 --> 00:34:33,282
Në rregull, gjashtë, unë jam duke shkuar për të kërkuar
ju janë të renditura tani, vijnë më përpara.

755
00:34:33,282 --> 00:34:33,990
Si e keni emrin?

756
00:34:33,990 --> 00:34:34,589
>> Audienca: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> Gjuha: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano është zgjidhet tani.

759
00:34:36,010 --> 00:34:36,450
Dhe si e ke emrin?

760
00:34:36,450 --> 00:34:37,080
>> Audienca: Alex.

761
00:34:37,080 --> 00:34:38,379
>> Gjuha: Alex është zgjidhet tani.

762
00:34:38,379 --> 00:34:40,750
Gjysma Majtas, gjysmë të drejtë,
çfarë është hapi përfundimtar?

763
00:34:40,750 --> 00:34:41,250
Merge.

764
00:34:41,250 --> 00:34:44,310
Pretty parëndësishme, kështu që unë jam i
do të bashkojë në gjashtë,

765
00:34:44,310 --> 00:34:46,930
të marrë një hap prapa,
tetë, të marrë një hap prapa.

766
00:34:46,930 --> 00:34:49,530
Dhe tani vini re kjo është
një takeaway të dobishme, çfarë

767
00:34:49,530 --> 00:34:53,930
tani është e vërtetë për gjysmën e majtë të
listë, pa marrë parasysh se si kemi filluar?

768
00:34:53,930 --> 00:34:55,090
Ajo është e renditura.

769
00:34:55,090 --> 00:34:57,750
>> Tani ajo nuk është e renditura në
Skema e madhe e gjërave,

770
00:34:57,750 --> 00:35:00,250
por ajo është e renditura në mënyrë të pavarur
e gjysmën tjetër.

771
00:35:00,250 --> 00:35:04,100
Tani ajo që hap jam unë në qoftë se unë mbaj
rewinding se si filloi historia?

772
00:35:04,100 --> 00:35:05,680
Tani unë kam për të zgjidhur gjysmën e duhur.

773
00:35:05,680 --> 00:35:07,630
Deri tani ne jemi mënyrë mbrapa në
fillimi i tregimit,

774
00:35:07,630 --> 00:35:08,921
dhe le ta bëjmë këtë shumë shpejt.

775
00:35:08,921 --> 00:35:11,320
Kështu që unë jam duke shkuar për të zgjidhur
gjysma e drejtë e të gjithë listën.

776
00:35:11,320 --> 00:35:13,060
Cili është hapi tjetër?

777
00:35:13,060 --> 00:35:15,840
Sort gjysmën e majtë të pjesës së djathtë.

778
00:35:15,840 --> 00:35:18,715
Sort gjysmën e majtë të
gjysma e majtë të pjesës së djathtë.

779
00:35:18,715 --> 00:35:19,590
Dhe si e ke emrin?

780
00:35:19,590 --> 00:35:20,230
>> Audienca: Omar.

781
00:35:20,230 --> 00:35:21,970
>> Gjuha: Omar, hap përpara, bëhet.

782
00:35:21,970 --> 00:35:22,860
Gjysma e majtë është e renditura.

783
00:35:22,860 --> 00:35:23,330
Dhe si e ke emrin?

784
00:35:23,330 --> 00:35:23,820
>> Audienca: Chris.

785
00:35:23,820 --> 00:35:25,620
>> Gjuha: Chris, të marrë një hap
përpara, ju janë të renditura tani.

786
00:35:25,620 --> 00:35:27,010
Cili është hapi kyç tani?

787
00:35:27,010 --> 00:35:27,510
Merge.

788
00:35:27,510 --> 00:35:30,509
Pra, një do të shkrihen në vendin e
këtu, në qoftë se ju mund të marrë një hap prapa,

789
00:35:30,509 --> 00:35:32,930
dhe tre do të
të marrë një hap prapa, të bashkohen.

790
00:35:32,930 --> 00:35:38,080
Pra, gjysma e majtë e
gjysma e drejtë, është e renditura tani.

791
00:35:38,080 --> 00:35:41,747
Sinqerisht, ky algoritëm ndjehet si ne
janë humbur mënyrë më shumë kohë se më parë,

792
00:35:41,747 --> 00:35:44,830
por në qoftë se ne e bëmë këtë në kohë reale, ne do të
parë se çfarë takeaways do të jetë.

793
00:35:44,830 --> 00:35:47,970
Tani unë jam këtu, e drejtë
gjysma e pjesës së duhur,

794
00:35:47,970 --> 00:35:50,170
më lejoni të shkoj përpara dhe të zgjidhur gjysmën e majtë.

795
00:35:50,170 --> 00:35:51,482
Hap përpara, si e ke emrin?

796
00:35:51,482 --> 00:35:52,190
Audienca: Ramsey.

797
00:35:52,190 --> 00:35:53,210
Gjuha: Ramsey është zgjidhet tani.

798
00:35:53,210 --> 00:35:53,570
Si e keni emrin?

799
00:35:53,570 --> 00:35:54,200
>> Audienca: Marina.

800
00:35:54,200 --> 00:35:57,033
>> Gjuha: Marina tani është renditur si
mirë, në qoftë se ju të marrë një hap përpara.

801
00:35:57,033 --> 00:36:00,690
Hap kyç këtu tani po shkrihen, unë jam
duke shkuar për të shembur nga dy listave të mia,

802
00:36:00,690 --> 00:36:01,720
majtë dhe të djathtë.

803
00:36:01,720 --> 00:36:05,150
Pesë do të vijë më parë,
dhe shtatë do të ndodhë më pas.

804
00:36:05,150 --> 00:36:06,410
Dhe përsëri, kjo është e qëllimshme.

805
00:36:06,410 --> 00:36:08,535
Fakti që ata janë duke marrë
hapa përpara dhe mbrapa

806
00:36:08,535 --> 00:36:12,997
ka për qëllim të përfaqësojë se ne nuk mund të
bëni këtë algorithm në vend aq lehtë

807
00:36:12,997 --> 00:36:15,830
si lloj flluskë, dhe përzgjedhjes lloj,
dhe futje lloj ku ne vetëm

808
00:36:15,830 --> 00:36:16,960
mbajtur shkëmbejnë njerëzit.

809
00:36:16,960 --> 00:36:19,940
Unë fjalë për fjalë duhet një lloj
letër zeroja në të cilën

810
00:36:19,940 --> 00:36:21,827
për të vënë këto folks
ndërsa unë bëj bashkimin,

811
00:36:21,827 --> 00:36:23,410
dhe pastaj unë mund të vënë ata të kthehen në vend.

812
00:36:23,410 --> 00:36:27,260
Dhe kjo është çelësi për shkak se unë jam duke përdorur një
burimeve të reja, hapësira, jo vetëm koha.

813
00:36:27,260 --> 00:36:28,270
>> OK, kjo është e mahnitshme.

814
00:36:28,270 --> 00:36:32,050
Gjysma Majtas është renditur, gjysma e drejtë është
Renditur, tani që çelësi bashkimin hap.

815
00:36:32,050 --> 00:36:33,450
Si jam unë do të bashkojë këtë?

816
00:36:33,450 --> 00:36:35,470
Pra, nëse ju do të ndiqni tim
la dorë dhe dora e djathtë,

817
00:36:35,470 --> 00:36:38,930
Unë jam duke shkuar për të vënë në dorën e majtë
në gjysmën e majtë, dora ime e djathtë

818
00:36:38,930 --> 00:36:42,680
në gjysmën e duhur, dhe tani unë duhet të
vendosë hap pas hapi që të bashkojë në.

819
00:36:42,680 --> 00:36:44,650
Kush padyshim vjen e para?

820
00:36:44,650 --> 00:36:45,150
Numri një.

821
00:36:45,150 --> 00:36:47,327
Pra, eja këtu,
këtu është pad tonë zeroja.

822
00:36:47,327 --> 00:36:49,910
Deri tani numër një, dhe njoftim
çfarë unë do të bëj me të djathtën time,

823
00:36:49,910 --> 00:36:54,152
Unë jam duke shkuar për të lëvizur një e djathtë të dorës
hap mbi të theksoj numrin tre,

824
00:36:54,152 --> 00:36:55,860
dhe tani unë kam për të bërë
njëjtin vendim.

825
00:36:55,860 --> 00:36:58,387
Dhe në të vërtetë qëndrojnë të drejtë në
përparme e Luka këtu nëse ju mund të,

826
00:36:58,387 --> 00:36:59,720
sepse kjo është e pad tonë zeroja.

827
00:36:59,720 --> 00:37:00,610
Pra, kush vjen më pas?

828
00:37:00,610 --> 00:37:05,000
Ne kemi Luka me numrin dy
apo Chris me numrin tre.

829
00:37:05,000 --> 00:37:07,460
Natyrisht Luka, numri
dy, kështu që ju të vijnë këtu.

830
00:37:07,460 --> 00:37:11,270
>> Por dora ime e majtë tani do të
të incremented për pikë në Darren,

831
00:37:11,270 --> 00:37:15,160
dhe këtu është çelësi heq me
bashkimi, unë jam duke shkuar për të mbajtur të bërë këtë,

832
00:37:15,160 --> 00:37:17,340
natyrisht, në qoftë se ju lloj
të ndjekin logjikën.

833
00:37:17,340 --> 00:37:19,670
Por duart e mia nuk janë të
do të shkojnë prapa,

834
00:37:19,670 --> 00:37:23,861
që do të thotë unë jam vetëm ndonjëherë duke shkuar për të
e majta me procesin tim bashkimin,

835
00:37:23,861 --> 00:37:26,360
dhe që do të jetë kyç për të
Analiza jonë në vetëm një moment.

836
00:37:26,360 --> 00:37:27,859
>> Pra, tani le të përfundojë kjo deri me shpejtësi.

837
00:37:27,859 --> 00:37:31,650
Pra, tre vjen më pas,
pastaj katër vjen më pas,

838
00:37:31,650 --> 00:37:38,750
dhe tani pesë vjen më pas, pastaj gjashtë,
dhe të shtatë, dhe pastaj në fund të tetë.

839
00:37:38,750 --> 00:37:42,960
Ndjehet si algorithm slowest
ende, por jo në qoftë se ne të vërtetë

840
00:37:42,960 --> 00:37:45,510
drejtuar atë në të njëjtën lloj
i shpejtësisë orën, në mënyrë që të

841
00:37:45,510 --> 00:37:48,106
flasin, me të njëjtën
kurdisur orën si më parë.

842
00:37:48,106 --> 00:37:48,605
Pse?

843
00:37:48,605 --> 00:37:51,100
E pra, le të marrin një
shikoni në rezultat në fund.

844
00:37:51,100 --> 00:37:56,990
>> Le të kthehemi gjatë këtu, le të më
tërheqë një demonstrim vizualisht

845
00:37:56,990 --> 00:37:59,030
e asaj që ne vetëm e bëri.

846
00:37:59,030 --> 00:38:06,110
Zooming në këtu, në këtë
faqe këtu, duke u thënë Firefox

847
00:38:06,110 --> 00:38:08,200
që ne duam të radhë
deri në këtë kuti, le të

848
00:38:08,200 --> 00:38:11,260
thonë flluskë lloj, me të cilat
ne jemi tani edhe të njohur,

849
00:38:11,260 --> 00:38:14,130
lloj përzgjedhje, e cila është një tjetër
mjaft e hapur,

850
00:38:14,130 --> 00:38:18,250
dhe tani lloj sotme bashkojë, të cilat
do të jetë fundi ynë klimatik.

851
00:38:18,250 --> 00:38:21,530
Arsyeja që u desh kaq shumë më të gjatë
këtu me njerëzit dhe mua me gojë është,

852
00:38:21,530 --> 00:38:23,480
natyrisht, unë jam duke shpjeguar çdo hap.

853
00:38:23,480 --> 00:38:26,920
Por në qoftë se ju thjesht të ekzekutuar këtë, shumë më
si ne e bëmë lloj flluskë dhe përzgjedhja

854
00:38:26,920 --> 00:38:30,890
lloj jo vetëm vizualisht, watch
se sa shumë më efikase

855
00:38:30,890 --> 00:38:33,330
kjo leveraging e
ndarje dhe pushtues

856
00:38:33,330 --> 00:38:39,150
mund të kur zbatohet në një grup të të dhënave që është
as madhësia e tetë, por edhe më shumë,

857
00:38:39,150 --> 00:38:39,970
shumë më e madhe.

858
00:38:39,970 --> 00:38:44,585
Unë ju jap bashkojë lloj, krah për
anë me këto algoritme të tjera.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Kjo do të merrni të dhimbshme
shpejt, dhe duke i dhënë fund

861
00:38:58,530 --> 00:39:00,890
nuk është veçanërisht klimatik,
ata vetëm të përfundojë renditura.

862
00:39:00,890 --> 00:39:05,280
Por kryesore marr me vete është se
shikoni se sa shpejt shkrihen lloj

863
00:39:05,280 --> 00:39:08,110
ishte, nëse ju mendoni se unë jam
vetëm lloj messing me ju.

864
00:39:08,110 --> 00:39:13,100
Nëse ne e bëjmë këtë një herë të fundit,
Le të rifreskoni këtë, le të kthehemi

865
00:39:13,100 --> 00:39:14,960
dhe zgjidhni flluskë lloj,
dhe vetëm për shkelma,

866
00:39:14,960 --> 00:39:17,330
le të zgjedhin shtënie
lloj, vetëm për masë të mirë.

867
00:39:17,330 --> 00:39:20,020
Dhe këtë herë përsëri, le të
zgjidhni bashkojë lloj dhe të le të

868
00:39:20,020 --> 00:39:21,595
në të vërtetë të drejtuar këto krah për krah.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Dhe kjo nuk është, në fakt, një pikë për shans.

871
00:39:26,930 --> 00:39:31,140
Ajo që unë kam bërë në mënyrë efektive është që unë kam
ndarë kontributin tim në gjysmë, përsëri,

872
00:39:31,140 --> 00:39:32,240
dhe përsëri, dhe përsëri.

873
00:39:32,240 --> 00:39:35,590
Dhe nuk ka vetëm kaq shumë herë ju mund
ndajnë kontributin tuaj në gjysmave, la

874
00:39:35,590 --> 00:39:36,240
dhe të drejtë.

875
00:39:36,240 --> 00:39:39,425
Çfarë është formula që do të vazhdojmë të shohim
që përshkruan ndarjen në gjysmë

876
00:39:39,425 --> 00:39:41,050
përsëri, dhe përsëri, dhe përsëri, dhe përsëri?

877
00:39:41,050 --> 00:39:41,890
>> Audienca: Identifikohu n.

878
00:39:41,890 --> 00:39:42,760
>> Gjuha: Identifikohu n.

879
00:39:42,760 --> 00:39:46,300
Por atëherë nuk është një hap tjetër i rëndësishëm,
kjo algorithm nuk është log n hapa.

880
00:39:46,300 --> 00:39:48,992
Nëse do të ishte vetëm log n hapa,
ne do të jetë në të njëjtin problem

881
00:39:48,992 --> 00:39:51,200
si më parë, ku ne nuk mund të jetë
që çdo gjë të zgjidhet.

882
00:39:51,200 --> 00:39:54,480
Ju duhet të shikoni në minimalisht elementet n
të jetë i sigurt n elemente janë të renditura,

883
00:39:54,480 --> 00:39:55,950
përndryshe ajo është një hap i besimit.

884
00:39:55,950 --> 00:39:59,810
>> Pra, kjo është log minimalisht n hapa, por
ajo që për këtë hap të rëndësishëm bashkimin

885
00:39:59,810 --> 00:40:04,370
ku unë u bashkua gjysma ime e majtë dhe të djathtë
gjysmë dhe eci nëpër skenë?

886
00:40:04,370 --> 00:40:06,980
Sa hapa është që të bashkojë?

887
00:40:06,980 --> 00:40:10,150
Është n, por nuk e kam vetëm
bashkojë kohën përfundimtar.

888
00:40:10,150 --> 00:40:15,089
Në secilin prej këtyre thirrjeve mbivendosur, në çdo
e atyre shkrirja mbivendosur, unë ende të renditura.

889
00:40:15,089 --> 00:40:18,380
I shkrirë këto dy djem, atëherë këto dy
djema, atëherë këto dy djem dhe kështu me radhë.

890
00:40:18,380 --> 00:40:19,955
>> Kështu që unë kam bashkimin përsëri, dhe përsëri.

891
00:40:19,955 --> 00:40:20,580
Sa herë?

892
00:40:20,580 --> 00:40:23,510
Kështu që çdo herë që unë të ndarë
Lista në gjysmë, kam bërë një bashkim.

893
00:40:23,510 --> 00:40:25,460
Ndani listën në gjysmë, të bëjë një bashkim.

894
00:40:25,460 --> 00:40:28,570
Pra, nëse e ndarë listën
mund të bëhet herë log n,

895
00:40:28,570 --> 00:40:33,880
dhe shkrirja në fund të fundit merr n
hapa, ajo mund të jetë tani e sipërme

896
00:40:33,880 --> 00:40:37,000
lidhur në drejtimin
Koha e algorithm tonë?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Dhe me të vërtetë, kjo është ajo që
ne kemi arritur këtu.

899
00:40:40,560 --> 00:40:44,650
Kështu ndjehen që ju shihni me sy kur
këto tri gjëra të drejtuar krah për krah

900
00:40:44,650 --> 00:40:47,930
është katror n kundër n
katror kundër log n n.

901
00:40:47,930 --> 00:40:51,010
E cila në thelb ne do të shohim,
jo vetëm sot, por në të ardhmen,

902
00:40:51,010 --> 00:40:52,760
është shumë, shumë më të shpejtë.

903
00:40:52,760 --> 00:40:56,010
Një raund i duartrokitje për këta njerëz,
Unë do të shpërblejë ata me topa stresit.

904
00:40:56,010 --> 00:41:00,260
Le të shtyjë sot këtu, dhe
ne do të shohim të hënën.

905
00:41:00,260 --> 00:41:02,255