1
00:00:00,000 --> 00:00:04,419
>> [Muzika]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG Lloyd: OK, kështu që një merge
lloj është edhe një algoritmi

4
00:00:08,460 --> 00:00:11,200
që ne mund të përdorni për të zgjidhur
elementet e një grup.

5
00:00:11,200 --> 00:00:14,480
Por si ne do të shohim, atë e mori një
Dallimi themelor shumë

6
00:00:14,480 --> 00:00:17,850
nga zgjedhja e renditjes, flluskë
lloj, dhe futje lloj

7
00:00:17,850 --> 00:00:20,280
që e bëjnë atë të vërtetë goxha i zgjuar.

8
00:00:20,280 --> 00:00:24,290
>> Ideja themelore prapa bashkohen
lloj është për të zgjidhur vargjeve të vogla

9
00:00:24,290 --> 00:00:27,430
dhe pastaj të kombinoni ato vargjeve
së bashku, ose shkrihen, porsi

10
00:00:27,430 --> 00:00:31,440
kështu name-- në mënyrë renditura.

11
00:00:31,440 --> 00:00:34,230
Mënyra se si shkrihet lloj bën
kjo është nga leveraging një mjet

12
00:00:34,230 --> 00:00:37,290
quajtur Recursion, e cila është ajo
ne jemi duke shkuar për të folur për së shpejti,

13
00:00:37,290 --> 00:00:39,720
por ne nuk kemi biseduar shumë rreth ende.

14
00:00:39,720 --> 00:00:43,010
>> Ja ideja themelore prapa merge lloj.

15
00:00:43,010 --> 00:00:46,320
Lloj gjysmën e majtë të vektorit,
supozuar n eshte me e madhe se 1.

16
00:00:46,320 --> 00:00:49,980
Dhe çfarë dua të them kur them
supozuar n eshte me e madhe se 1 është,

17
00:00:49,980 --> 00:00:53,970
Unë mendoj se ne mund të bien dakord se në qoftë se një grup
vetëm përbëhet nga një element të vetme,

18
00:00:53,970 --> 00:00:54,680
është e renditura.

19
00:00:54,680 --> 00:00:56,560
Ne nuk mund të vërtetë nevojë
të bëjë asgjë për të.

20
00:00:56,560 --> 00:00:58,059
Ne vetëm mund ta deklarojë atë të zgjidhet.

21
00:00:58,059 --> 00:01:00,110
Kjo është vetëm një element i vetëm.

22
00:01:00,110 --> 00:01:03,610
>> Pra pseudokod, përsëri, është e
lloj gjysmën e majtë të vektorit,

23
00:01:03,610 --> 00:01:08,590
pastaj lloj gjysma e drejtë array,
pastaj bashkojë dy gjysmave së bashku.

24
00:01:08,590 --> 00:01:11,040
Tani, tashmë ju mund të jetë
të menduarit, ai lloj i vetëm

25
00:01:11,040 --> 00:01:14,080
tingëllon si ju jeni duke off the--
ju nuk jeni në të vërtetë duke bërë asgjë.

26
00:01:14,080 --> 00:01:16,330
Ju jeni duke thënë lloj majtë
gjysmë, lloj gjysmën e djathtë,

27
00:01:16,330 --> 00:01:19,335
por ju nuk jeni duke u thënë
mua se si ju jeni duke bërë atë.

28
00:01:19,335 --> 00:01:22,220
>> Por mos harroni se për aq kohë sa
një grup është një element të vetme,

29
00:01:22,220 --> 00:01:23,705
ne mund ta deklarojë atë të renditura.

30
00:01:23,705 --> 00:01:25,330
Atëherë ne mund vetëm të kombinuar ato së bashku.

31
00:01:25,330 --> 00:01:27,788
Dhe kjo është në fakt
Ideja themelore prapa merge lloji,

32
00:01:27,788 --> 00:01:31,150
është që të thyejnë atë poshtë në mënyrë që
Vargjeve tuaja janë të një madhësie.

33
00:01:31,150 --> 00:01:33,430
Dhe pastaj ju rindërtuar nga atje.

34
00:01:33,430 --> 00:01:35,910
>> Merge lloj është padyshim
një algorithm komplikuar.

35
00:01:35,910 --> 00:01:38,210
Dhe kjo është gjithashtu një pak
komplikuar për të kujtoj.

36
00:01:38,210 --> 00:01:41,870
Kështu që shpresojmë se, vizualizimi që unë
kemi këtu do të ju ndihmojë të ndjekin së bashku.

37
00:01:41,870 --> 00:01:45,640
Dhe unë do të përpiqet tim më të mirë për të rrëfej gjëra
dhe të vazhdojë me këtë më pak

38
00:01:45,640 --> 00:01:49,180
ngadalë se ato e tjera
vetëm për shpresë të marrë kokën tuaj

39
00:01:49,180 --> 00:01:51,800
rreth ideve prapa merge lloj.

40
00:01:51,800 --> 00:01:54,680
>> Pra, ne kemi të njëjtin grup si më të
sorting video tjera algorithm

41
00:01:54,680 --> 00:01:57,120
në qoftë se ju keni parë, porsi
një grup gjashtë element.

42
00:01:57,120 --> 00:02:02,110
Dhe kodi ynë pseudokod këtu është lloj
gjysmën e majtë, lloj gjysmën e djathtë,

43
00:02:02,110 --> 00:02:03,890
bashkojë dy gjysmave së bashku.

44
00:02:03,890 --> 00:02:09,770
Pra, le të marrin këtë kuqe shumë të errët tulla
array dhe lloj gjysmën e majtë të saj.

45
00:02:09,770 --> 00:02:13,380
>> Pra, për momentin, ne jemi duke shkuar
të injorojë gjëra në të djathtë.

46
00:02:13,380 --> 00:02:15,740
Ajo është aty, por ne jemi
jo në atë hap ende.

47
00:02:15,740 --> 00:02:18,220
Ne nuk jemi në Lloj
gjysma e djathtë e vektorit.

48
00:02:18,220 --> 00:02:21,037
Ne jemi në lloj nga e majta
gjysma e vektorit.

49
00:02:21,037 --> 00:02:22,870
Dhe vetëm për hir
për të qenë pak më shumë

50
00:02:22,870 --> 00:02:26,480
i qartë, kështu që unë mund të referohen
me atë që ne jemi në hap,

51
00:02:26,480 --> 00:02:29,800
Unë jam duke shkuar për të kaluar
Ngjyra e këtij grupi në portokalli.

52
00:02:29,800 --> 00:02:33,190
Tani, ne jemi ende duke folur për
njëjtë gjysma e majtë e vektorit origjinale.

53
00:02:33,190 --> 00:02:38,520
Por unë jam duke shpresuar se duke qenë në gjendje të
referohen ngjyrat e sendeve të ndryshme,

54
00:02:38,520 --> 00:02:40,900
ajo do të bëjë atë një pak më shumë
të qartë se çfarë po ndodh këtu.

55
00:02:40,900 --> 00:02:43,270
>> OK, kështu që tani kemi një
tre element array.

56
00:02:43,270 --> 00:02:46,420
Si nuk kemi zgjidhur gjysmën e majtë të kësaj
grup, i cili është ende ky hap?

57
00:02:46,420 --> 00:02:49,400
Ne jemi duke u përpjekur për të zgjidhur majtë
gjysma e tulla array-- kuqe

58
00:02:49,400 --> 00:02:52,410
gjysma e majtë e të cilave
Unë tani e kam me ngjyrë portokalli.

59
00:02:52,410 --> 00:02:54,840
>> E pra, ne mund të përpiqemi dhe
përsëris këtë proces përsëri.

60
00:02:54,840 --> 00:02:56,756
Pra, ne jemi ende në
mesme e duke u përpjekur për të zgjidhur

61
00:02:56,756 --> 00:02:58,700
gjysma e majtë e koleksion të plotë.

62
00:02:58,700 --> 00:03:00,450
Gjysma e majtë të
grup, unë jam vetëm duke shkuar

63
00:03:00,450 --> 00:03:03,910
për të vendosur në mënyrë arbitrare se gjysma e majtë
do të jetë më i vogël se gjysma e duhur,

64
00:03:03,910 --> 00:03:06,550
sepse kjo ndodh për
përbëhet nga tre elemente.

65
00:03:06,550 --> 00:03:11,260
>> Dhe kështu që unë jam duke shkuar për të thënë se
gjysma e majtë të pjesës së majtë array

66
00:03:11,260 --> 00:03:14,050
është vetëm elementi pesë.

67
00:03:14,050 --> 00:03:18,360
Pesë, duke qenë një element i vetëm
grup, ne e dimë se si për të zgjidhur atë.

68
00:03:18,360 --> 00:03:21,615
Dhe kështu pesë është e renditura.

69
00:03:21,615 --> 00:03:22,990
Ne jemi vetëm duke shkuar për të deklaruar se.

70
00:03:22,990 --> 00:03:24,890
Është një grup i vetëm element.

71
00:03:24,890 --> 00:03:29,015
>> Pra, ne kemi renditur tani
gjysma e majtë të half-- majtë

72
00:03:29,015 --> 00:03:33,190
ose më mirë, ne kemi renditur
gjysma e majtë e portokalli.

73
00:03:33,190 --> 00:03:37,970
Deri tani, në mënyrë që ende i plotë
gjysma e majtë array Në përgjithësi së,

74
00:03:37,970 --> 00:03:43,481
ne kemi nevojë për të zgjidhur gjysmën e djathtë
e portokalli, apo këtë stuff.

75
00:03:43,481 --> 00:03:44,230
Si e bëjmë këtë?

76
00:03:44,230 --> 00:03:45,930
E pra, ne kemi një koleksion të dy element.

77
00:03:45,930 --> 00:03:50,470
Pra, ne mund të lloj gjysmën e majtë
i vektorit, e cila është e dy.

78
00:03:50,470 --> 00:03:52,090
Dy është një element i vetëm.

79
00:03:52,090 --> 00:03:55,890
Pra, është e renditura nga default.
Atëherë ne mund të lloj gjysmën e djathtë

80
00:03:55,890 --> 00:03:58,530
e asaj pjese të array, atij.

81
00:03:58,530 --> 00:04:00,210
Kjo është lloj i by default.

82
00:04:00,210 --> 00:04:03,610
>> Kjo tani është hera e parë
ne kemi arritur një hap të bashkohen.

83
00:04:03,610 --> 00:04:06,135
Ne kemi përfunduar, edhe pse
ne jemi tani lloj i mbivendosur down--

84
00:04:06,135 --> 00:04:08,420
dhe kjo është lloj i ndërlikuar
gjë me recursion është,

85
00:04:08,420 --> 00:04:10,930
ju duhet të mbani tuaj
kreu për ku jemi.

86
00:04:10,930 --> 00:04:15,560
Pra, ne kemi lloj të majtë
gjysma e pjesës portokalli.

87
00:04:15,560 --> 00:04:21,280
>> Dhe tani, ne jemi në mes të sorting
gjysma e djathtë e pjesës portokalli.

88
00:04:21,280 --> 00:04:25,320
Dhe në këtë proces, ne jemi
tani gati të jetë në hap,

89
00:04:25,320 --> 00:04:27,850
bashkojë dy gjysmave së bashku.

90
00:04:27,850 --> 00:04:31,700
Kur ne shikojmë në dy gjysmave
e grup, ne shohim dy dhe një të tillë.

91
00:04:31,700 --> 00:04:33,880
Cili element është më i vogël?

92
00:04:33,880 --> 00:04:35,160
Një.

93
00:04:35,160 --> 00:04:36,760
>> Atëherë cili element është më i vogël?

94
00:04:36,760 --> 00:04:38,300
E pra, kjo është dy ose asgjë.

95
00:04:38,300 --> 00:04:39,910
Pra, kjo është dy.

96
00:04:39,910 --> 00:04:43,690
Deri tani, vetëm të formojë përsëri
ku ne jemi në kontekst,

97
00:04:43,690 --> 00:04:48,230
ne kemi renditura
gjysma e majtë e portokalli

98
00:04:48,230 --> 00:04:49,886
dhe gjysma e djathtë e origjinës.

99
00:04:49,886 --> 00:04:52,510
Unë e di unë kam ndryshuar ngjyrat
përsëri, por kjo është ajo ku ishim.

100
00:04:52,510 --> 00:04:54,676
Dhe arsyeja që unë e bëri këtë
është për shkak se ky proces është

101
00:04:54,676 --> 00:04:57,870
duke shkuar për të mbajtur vazhdim e sipër, iterating poshtë.

102
00:04:57,870 --> 00:05:00,500
Ne kemi renditura majtë
gjysma e ish-portokalli

103
00:05:00,500 --> 00:05:02,590
dhe gjysma e djathtë e ish-portokalli.

104
00:05:02,590 --> 00:05:05,620
>> Tani, ne kemi nevojë të bashkojë ato
dy gjysmat së bashku shumë.

105
00:05:05,620 --> 00:05:07,730
Ky është hapi ne jemi në.

106
00:05:07,730 --> 00:05:11,440
Pra, ne e konsiderojmë të gjithë e
elemente që tani janë të gjelbër,

107
00:05:11,440 --> 00:05:12,972
gjysmën e majtë të vektorit origjinale.

108
00:05:12,972 --> 00:05:14,680
Dhe ne bashkojë ata
duke përdorur të njëjtin proces

109
00:05:14,680 --> 00:05:18,660
ne e bëmë për bashkimin e dy
dhe një vetëm një moment më parë.

110
00:05:18,660 --> 00:05:23,080
>> Gjysmën e majtë, më të vogël
element në gjysmën e majtë është pesë.

111
00:05:23,080 --> 00:05:25,620
Elementi më i vogël në
gjysma e drejtë është një.

112
00:05:25,620 --> 00:05:27,370
Cili prej tyre është më i vogël?

113
00:05:27,370 --> 00:05:29,260
Një.

114
00:05:29,260 --> 00:05:32,250
>> Elementi më i vogël në
gjysmën e majtë është pesë.

115
00:05:32,250 --> 00:05:35,540
Elementi më i vogël në
gjysma e drejtë është dy.

116
00:05:35,540 --> 00:05:36,970
Çfarë është më i vogël?

117
00:05:36,970 --> 00:05:38,160
Dy.

118
00:05:38,160 --> 00:05:41,540
Dhe pastaj në fund pesë dhe
asgjë, ne mund të themi pesë.

119
00:05:41,540 --> 00:05:43,935
>> OK, foto kaq i madh, le të
të marrë një pushim për një të dytë

120
00:05:43,935 --> 00:05:46,080
dhe të kuptoj se ku jemi.

121
00:05:46,080 --> 00:05:48,580
Në qoftë se kemi filluar nga
fillimi, ne

122
00:05:48,580 --> 00:05:51,640
kanë përfunduar tani për
array përgjithshme vetëm

123
00:05:51,640 --> 00:05:53,810
një hap i kodit pseudokod këtu.

124
00:05:53,810 --> 00:05:56,645
Ne kemi renditura
gjysma e majtë e vektorit.

125
00:05:56,645 --> 00:05:59,490
>> Kujtojnë se origjinal
rendi i pesë, dy, një.

126
00:05:59,490 --> 00:06:02,570
Duke kaluar nëpër këtë proces
dhe shturë poshtë dhe duke përsëritur,

127
00:06:02,570 --> 00:06:05,990
duke vazhduar për të thyer problemin
poshtë në pjesë më të vogla dhe të vogla,

128
00:06:05,990 --> 00:06:09,670
ne kemi përfunduar tani
hap një nga pseudokod

129
00:06:09,670 --> 00:06:13,940
për të gjithë array fillimit.

130
00:06:13,940 --> 00:06:16,670
Ne kemi renditura gjysmën e saj të majtë.

131
00:06:16,670 --> 00:06:18,670
>> Pra, tani le të ngrijë atje.

132
00:06:18,670 --> 00:06:23,087
Dhe tani le të lloj të drejtën
gjysma e array origjinal.

133
00:06:23,087 --> 00:06:25,670
Dhe ne jemi duke shkuar për të bërë këtë nga
duke kaluar nëpër të njëjtën gjë përsëritës

134
00:06:25,670 --> 00:06:30,630
Procesi i thyer gjëra poshtë
dhe pastaj bashkimi i tyre së bashku.

135
00:06:30,630 --> 00:06:34,290
>> Pra, gjysma e majtë të
kuqe, ose gjysmën e majtë

136
00:06:34,290 --> 00:06:38,830
i gjysmës së djathtë të origjinalit
grup, unë jam duke shkuar për të thënë është tre.

137
00:06:38,830 --> 00:06:40,312
Përsëri, unë jam duke u konsistente këtu.

138
00:06:40,312 --> 00:06:42,020
Nëse keni një i rastësishëm
Numri i elementeve, atë

139
00:06:42,020 --> 00:06:44,478
Nuk ka rëndësi nëse
ju bëni një të majtë më të vogël

140
00:06:44,478 --> 00:06:45,620
ose një e drejtë më të vogla.

141
00:06:45,620 --> 00:06:49,230
>> Ajo që ka rëndësi është se sa herë që ju
ndeshen me këtë problem në kryerjen e

142
00:06:49,230 --> 00:06:51,422
një bashkojë, ju duhet të jenë në përputhje.

143
00:06:51,422 --> 00:06:53,505
Ju ose gjithmonë duhet të
të bëjë një Krahu i majtë më të vogël

144
00:06:53,505 --> 00:06:55,421
apo gjithmonë duhet të bëni
anën e djathtë të vogla.

145
00:06:55,421 --> 00:06:57,720
Këtu, unë kam zgjedhur për të gjithmonë
të bëjë anën e majtë të vogla

146
00:06:57,720 --> 00:07:04,380
kur array ime, ose im
nën-grup, është e një madhësi çuditshme.

147
00:07:04,380 --> 00:07:07,420
>> Tre është një element i vetëm,
dhe kështu ajo është e renditura.

148
00:07:07,420 --> 00:07:10,860
Ne kemi leveraged që supozim
gjatë gjithë procesit tonë deri tani.

149
00:07:10,860 --> 00:07:15,020
Pra, tani le të lloj të drejtën
gjysma e pjesës së duhur,

150
00:07:15,020 --> 00:07:18,210
ose gjysma e djathtë e kuqe.

151
00:07:18,210 --> 00:07:20,390
>> Përsëri, ne kemi nevojë për të ndarë këtë poshtë.

152
00:07:20,390 --> 00:07:21,910
Kjo nuk është një grup i vetëm element.

153
00:07:21,910 --> 00:07:23,970
Ne nuk mund ta deklarojë atë të renditura.

154
00:07:23,970 --> 00:07:27,060
Dhe kështu për herë të parë, ne jemi duke shkuar
për të zgjidhur gjysmën e majtë.

155
00:07:27,060 --> 00:07:31,620
>> Gjysma e majtë është një element i vetëm,
kështu që kjo është lloj i by default.

156
00:07:31,620 --> 00:07:34,840
Pastaj ne jemi duke shkuar për të zgjidhur të drejtën
gjysma, e cila është një element i vetëm.

157
00:07:34,840 --> 00:07:41,250
Është e renditura by default. Dhe tani,
ne mund të bashkojë ata të dy së ​​bashku.

158
00:07:41,250 --> 00:07:45,820
Katër është më i vogël, dhe
atëherë gjashtë është më i vogël.

159
00:07:45,820 --> 00:07:48,870
>> Përsëri, çfarë kemi bërë në këtë pikë?

160
00:07:48,870 --> 00:07:52,512
Ne kemi renditura majtë
gjysma e pjesës së duhur.

161
00:07:52,512 --> 00:07:54,720
Ose duke shkuar prapa në origjinal
ngjyra që ndodheshin aty,

162
00:07:54,720 --> 00:07:57,875
ne kemi renditur e majtë
gjysma e kuqe butë.

163
00:07:57,875 --> 00:08:00,416
Kjo ishte fillimisht një tullë të errët
të kuqe dhe tani kjo është një të kuqe të butë,

164
00:08:00,416 --> 00:08:02,350
apo kjo ishte një e kuqe butë.

165
00:08:02,350 --> 00:08:05,145
>> Dhe pastaj ne kemi renditur
gjysma e djathtë e kuqe butë.

166
00:08:05,145 --> 00:08:08,270
Tani, mirë, ata janë të gjelbër përsëri, vetëm
sepse ne jemi duke shkuar nëpër një proces.

167
00:08:08,270 --> 00:08:10,720
Dhe ne kemi për të përsëritur
ky pushim.

168
00:08:10,720 --> 00:08:14,695
>> Deri tani ne mund të bashkojë ato
dy gjysmat së bashku.

169
00:08:14,695 --> 00:08:15,820
Dhe kjo është ajo që ne bëjmë këtu.

170
00:08:15,820 --> 00:08:17,653
Pra, të vijë të zezë vetëm
ndau gjysmën e majtë

171
00:08:17,653 --> 00:08:19,690
dhe gjysma e drejta e kësaj pjese renditjes.

172
00:08:19,690 --> 00:08:24,310
>> Ne krahasojmë vlerën më të vogël
në anën e majtë të array--

173
00:08:24,310 --> 00:08:26,710
ose më falni, më të vogël
Vlera e pjesës së majtë

174
00:08:26,710 --> 00:08:30,790
me vlerën më të vogël të së drejtës
gjysmë dhe për të gjetur se tre është më i vogël.

175
00:08:30,790 --> 00:08:32,530
Dhe tani pak e një optimization, e drejtë?

176
00:08:32,530 --> 00:08:35,175
Nuk është në fakt asgjë
la në anën e majtë.

177
00:08:35,175 --> 00:08:37,440
>> Nuk ka asgjë të mbetur
në anën e majtë,

178
00:08:37,440 --> 00:08:40,877
kështu që ne mund në mënyrë efikase
vetëm move-- ne mund të deklarojë

179
00:08:40,877 --> 00:08:42,960
pjesa tjetër e saj është në fakt
të renditura dhe vetëm litar atë

180
00:08:42,960 --> 00:08:45,126
në, sepse nuk ka asgjë
tjetër për të krahasuar kundër.

181
00:08:45,126 --> 00:08:49,140
Dhe ne e dimë se ana e djathtë
e anën e djathtë është e renditura.

182
00:08:49,140 --> 00:08:52,770
>> OK, kështu që tani le të ngrijë përsëri dhe
kuptoj se ku jemi në histori.

183
00:08:52,770 --> 00:08:56,120
Në grup të përgjithshëm,
çfarë kemi arritur?

184
00:08:56,120 --> 00:08:58,790
Ne kemi në fakt të kryer
tani hapa një dhe hap dy.

185
00:08:58,790 --> 00:09:03,300
Ne renditura gjysmën e majtë, dhe
ne të renditura gjysmën e djathtë.

186
00:09:03,300 --> 00:09:08,210
>> Deri tani, të gjitha që mbetet është për ne
të bashkojë këto dy gjysmave së bashku.

187
00:09:08,210 --> 00:09:11,670
Pra, ne krahasojmë më të ulët të vlerësuar
element i secilit gjysma e vektorit

188
00:09:11,670 --> 00:09:13,510
nga ana e tij dhe të vazhdojë.

189
00:09:13,510 --> 00:09:16,535
Njëra është më pak se tre, kështu shkon.

190
00:09:16,535 --> 00:09:19,770
>> Dy është më pak se tre, kështu që dy shkon.

191
00:09:19,770 --> 00:09:22,740
Tre është më pak se 5, kështu që tre shkon.

192
00:09:22,740 --> 00:09:25,820
Katër është më pak se 5, kështu që katër shkon.

193
00:09:25,820 --> 00:09:30,210
Atëherë pesë është më pak se gjashtë,
dhe gjashtë është e tëra që mbetet.

194
00:09:30,210 --> 00:09:31,820
>> Tani, unë e di, se ishte një shumë e hapa.

195
00:09:31,820 --> 00:09:33,636
Dhe ne kemi lënë shumë
e kujtesës në prag tonë.

196
00:09:33,636 --> 00:09:35,260
Dhe kjo është ajo që këto sheshe janë gri.

197
00:09:35,260 --> 00:09:40,540
Dhe kjo ndoshta ndjehet si ajo mori një
shumë më të gjatë se futje lloji, flluskë

198
00:09:40,540 --> 00:09:42,660
lloj, apo përzgjedhja lloj.

199
00:09:42,660 --> 00:09:45,330
>> Por në fakt, për shkak se një
shumë prej këtyre proceseve

200
00:09:45,330 --> 00:09:48,260
janë duke ndodhur në të njëjtën time--
e cila është diçka që ne do të, përsëri,

201
00:09:48,260 --> 00:09:51,100
flasim për kur flasim për
Recursion në një të ardhme video--

202
00:09:51,100 --> 00:09:53,799
ky algoritëm fakt
në mënyrë të qartë është krejtësisht

203
00:09:53,799 --> 00:09:55,590
ndryshe se çdo gjë
ne kemi parë më parë

204
00:09:55,590 --> 00:09:58,820
por është gjithashtu në mënyrë të konsiderueshme
më efikase.

205
00:09:58,820 --> 00:09:59,532
>> Pse eshte ajo?

206
00:09:59,532 --> 00:10:01,240
E pra, në më të keq
skenari, ne kemi

207
00:10:01,240 --> 00:10:04,830
për të ndarë n elemente lart
dhe pastaj recombine tyre.

208
00:10:04,830 --> 00:10:06,680
Por, kur ne recombine
ata, ajo që ne jemi duke bërë

209
00:10:06,680 --> 00:10:11,110
është në thelb dyfishuar
Madhësia e vargjeve të vogla.

210
00:10:11,110 --> 00:10:14,260
Ne kemi një bandë e një elementi
vargjeve që ne në mënyrë efektive

211
00:10:14,260 --> 00:10:16,290
kombinohen në dy vargjeve element.

212
00:10:16,290 --> 00:10:18,590
Dhe pastaj ne kemi marrë ato
dy vargjeve element

213
00:10:18,590 --> 00:10:21,890
dhe të kombinuar ato së bashku në
katër vargjeve element, dhe kështu me radhë,

214
00:10:21,890 --> 00:10:26,130
dhe kështu me radhë, dhe kështu me radhë, deri sa ne
kanë një të vetme koleksion element n.

215
00:10:26,130 --> 00:10:29,910
>> Por sa doublings
nuk është marrë për të marrë në n?

216
00:10:29,910 --> 00:10:31,460
Mendoni përsëri për shembull librin e telefonit.

217
00:10:31,460 --> 00:10:34,490
Sa herë ne duhet të heq
libri telefon në gjysmë, sa më tepër

218
00:10:34,490 --> 00:10:38,370
herë nuk kemi të heq librin e telefonit
në gjysmë, në qoftë se madhësia e librin e telefonit

219
00:10:38,370 --> 00:10:39,680
dyfishuar?

220
00:10:39,680 --> 00:10:41,960
Ka vetëm një, e drejtë?

221
00:10:41,960 --> 00:10:45,360
>> Pra, ka disa lloj
element logaritmike këtu.

222
00:10:45,360 --> 00:10:48,590
Por ne gjithashtu ende duhet të paktën
shikoni në të gjitha elementet n.

223
00:10:48,590 --> 00:10:53,860
Pra, në rastin më të keq,
bashkojë lloj shkon në log n n.

224
00:10:53,860 --> 00:10:56,160
Ne duhet të shikojmë në
të gjithë elementet n,

225
00:10:56,160 --> 00:11:02,915
dhe ne kemi për të kombinuar ato
së bashku në log n grupe të hapave.

226
00:11:02,915 --> 00:11:05,290
Në rastin më të mirë,
array është renditur në mënyrë të përkryer.

227
00:11:05,290 --> 00:11:06,300
Kjo është e madhe.

228
00:11:06,300 --> 00:11:09,980
Por bazuar në algorithm ne kemi këtu,
ne ende kemi për të ndarë dhe recombine.

229
00:11:09,980 --> 00:11:13,290
Edhe pse në këtë rast,
recombining është lloj i paefektshëm.

230
00:11:13,290 --> 00:11:14,720
Ajo nuk është e nevojshme.

231
00:11:14,720 --> 00:11:17,580
Por ne ende kalojnë nëpër
i gjithë procesi gjithsesi.

232
00:11:17,580 --> 00:11:21,290
>> Pra, në rastin më të mirë
dhe në rastin më të keq,

233
00:11:21,290 --> 00:11:24,970
kjo algorithm shkon në log n n kohë.

234
00:11:24,970 --> 00:11:29,130
Merge lloj është padyshim pak i komplikuar
se algoritme tjera kryesore klasifikim

235
00:11:29,130 --> 00:11:33,470
ne kemi biseduar për CS50, por është
në thelb më të fuqishme.

236
00:11:33,470 --> 00:11:35,400
>> Dhe kështu që nëse ju ndonjëherë gjeni
rast të ketë nevojë për atë

237
00:11:35,400 --> 00:11:38,480
ose të përdorin atë për të zgjidhur një
grup i madh të dhënave, duke marrë

238
00:11:38,480 --> 00:11:41,940
kokën tuaj rreth idesë së recursion
do të jetë me të vërtetë i fuqishëm.

239
00:11:41,940 --> 00:11:45,270
Dhe kjo do të bëjë tuaj
Programet me të vërtetë shumë më të efektshme

240
00:11:45,270 --> 00:11:48,700
duke përdorur bashkojë lloj kundrejt çdo gjë tjetër.

241
00:11:48,700 --> 00:11:49,640
Unë jam Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Kjo është CS50.

243
00:11:51,970 --> 00:11:53,826