1
00:00:00,000 --> 00:00:04,419
>> [Music kucheza]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: Sawa, hivyo kuunganisha
aina hii bado ni algorithm mwingine

4
00:00:08,460 --> 00:00:11,200
kwamba tunaweza kutumia aina nje
mambo ya safu.

5
00:00:11,200 --> 00:00:14,480
Lakini kama tutaweza kuona, ni got
tofauti ya msingi sana

6
00:00:14,480 --> 00:00:17,850
kutoka uteuzi aina, Bubble
aina, na kuingizwa aina

7
00:00:17,850 --> 00:00:20,280
kwamba kufanya hivyo ni kweli pretty wajanja.

8
00:00:20,280 --> 00:00:24,290
>> Wazo msingi nyuma ya kuunganisha
aina ni aina arrays ndogo

9
00:00:24,290 --> 00:00:27,430
na kisha kuchanganya arrays wale
pamoja, au kuunganisha them--

10
00:00:27,430 --> 00:00:31,440
hivyo name-- ili Iliyopangwa.

11
00:00:31,440 --> 00:00:34,230
Njia ambayo kuunganisha aina gani
hii ni kwa leveraging chombo

12
00:00:34,230 --> 00:00:37,290
aitwaye kujirudia, ambayo ni nini
tunakwenda kuwa na kuzungumza juu hivi karibuni,

13
00:00:37,290 --> 00:00:39,720
lakini sisi si kweli aliyesema kuhusu bado.

14
00:00:39,720 --> 00:00:43,010
>> Hapa ni wazo la msingi la kuunganisha aina.

15
00:00:43,010 --> 00:00:46,320
Aina nusu kushoto wa safu,
kuchukua n ni kubwa kuliko 1.

16
00:00:46,320 --> 00:00:49,980
Na nini maana mimi wakati mimi kusema
kuchukua n ni kubwa kuliko 1 ni,

17
00:00:49,980 --> 00:00:53,970
Nadhani tunaweza kukubaliana kwamba kama safu
tu lina kipengele moja,

18
00:00:53,970 --> 00:00:54,680
ni vyema.

19
00:00:54,680 --> 00:00:56,560
Hatuna haja kweli
kufanya kitu chochote na hiyo.

20
00:00:56,560 --> 00:00:58,059
Tunaweza tu kuyatangaza ya kutatuliwa.

21
00:00:58,059 --> 00:01:00,110
Ni tu kipengele moja.

22
00:01:00,110 --> 00:01:03,610
>> Hivyo pseudocode, tena, ni
aina kushoto nusu ya safu,

23
00:01:03,610 --> 00:01:08,590
kisha kutatua nusu ya haki safu,
kisha kuunganisha sehemu mbili kwa pamoja.

24
00:01:08,590 --> 00:01:11,040
Sasa, tayari unaweza kuwa
kufikiri, ni aina ya tu

25
00:01:11,040 --> 00:01:14,080
Inaonekana kama wewe ni kuweka mbali the--
wewe si kweli kufanya kitu chochote.

26
00:01:14,080 --> 00:01:16,330
Wewe ni kusema kutatua kushoto
nusu, aina nusu haki,

27
00:01:16,330 --> 00:01:19,335
lakini wewe si kuwaambia
mimi jinsi wewe kufanya hivyo.

28
00:01:19,335 --> 00:01:22,220
>> Lakini kumbuka kwamba kwa muda mrefu kama
safu ni kipengele moja,

29
00:01:22,220 --> 00:01:23,705
tunaweza kuitangaza vyema.

30
00:01:23,705 --> 00:01:25,330
Basi tunaweza tu kuchanganya yao pamoja.

31
00:01:25,330 --> 00:01:27,788
Na hiyo ni kweli
msingi Dhana ya aina kuunganisha,

32
00:01:27,788 --> 00:01:31,150
ni kwa kuvunja chini ili
arrays yako ni ya kipimo kimoja.

33
00:01:31,150 --> 00:01:33,430
Na kisha kujenga upya kutoka huko.

34
00:01:33,430 --> 00:01:35,910
>> Kuunganisha aina ni dhahiri
algorithm ngumu.

35
00:01:35,910 --> 00:01:38,210
Na pia ni kidogo
ngumu kupiga taswira.

36
00:01:38,210 --> 00:01:41,870
Hivyo hopefully, taswira ya kuwa mimi
na hapa kukusaidia kufuata pamoja.

37
00:01:41,870 --> 00:01:45,640
Na mimi itabidi kujaribu bora yangu kusimulia mambo
na kuendelea kwa njia hii zaidi kidogo

38
00:01:45,640 --> 00:01:49,180
polepole zaidi kuliko wale wengine
tu hopefully kupata kichwa yako

39
00:01:49,180 --> 00:01:51,800
karibu mawazo nyuma ya kuunganisha aina.

40
00:01:51,800 --> 00:01:54,680
>> Hivyo tuna safu sawa na
mengine ya kuchagua video algorithm

41
00:01:54,680 --> 00:01:57,120
kama wameweza kuona them--
sita kipengele safu.

42
00:01:57,120 --> 00:02:02,110
Na pseudocode kificho yetu hapa ni aina
nusu kushoto, kutatua nusu ya haki,

43
00:02:02,110 --> 00:02:03,890
kuunganisha sehemu mbili kwa pamoja.

44
00:02:03,890 --> 00:02:09,770
Basi hebu kuchukua hii giza sana tofali nyekundu
safu na aina kushoto nusu yake.

45
00:02:09,770 --> 00:02:13,380
>> Hivyo kwa wakati huu, tunakwenda
kupuuza mambo juu ya haki.

46
00:02:13,380 --> 00:02:15,740
Ni pale, lakini tuko
si wakati kwamba hatua bado.

47
00:02:15,740 --> 00:02:18,220
Sisi siyo katika aina
nusu haki ya safu.

48
00:02:18,220 --> 00:02:21,037
Tupo aina kushoto
nusu ya safu.

49
00:02:21,037 --> 00:02:22,870
Na tu kwa ajili
kuwa kidogo zaidi

50
00:02:22,870 --> 00:02:26,480
wazi, hivyo siwezi kutaja
kwa nini hatua sisi ni juu,

51
00:02:26,480 --> 00:02:29,800
Mimi nina kwenda kubadili
rangi ya kuweka hii kwa rangi ya machungwa.

52
00:02:29,800 --> 00:02:33,190
Sasa, bado tuko kuzungumza juu ya
sawa kushoto nusu ya awali safu.

53
00:02:33,190 --> 00:02:38,520
Lakini nina matumaini kwamba kwa kuwa na uwezo wa
rejea rangi ya vitu mbalimbali,

54
00:02:38,520 --> 00:02:40,900
kutakuwa na kufanya hivyo zaidi kidogo
wazi nini kinaendelea hapa.

55
00:02:40,900 --> 00:02:43,270
>> OK, hivyo kwa sasa tuna
tatu kipengele safu.

56
00:02:43,270 --> 00:02:46,420
Je, sisi kutatua kushoto nusu ya hii
safu, ambayo bado hatua hii?

57
00:02:46,420 --> 00:02:49,400
Sisi ni kujaribu kutatua kushoto
nusu ya tofali nyekundu array--

58
00:02:49,400 --> 00:02:52,410
nusu ya kushoto ya ambayo
Nimekuwa sasa rangi ya machungwa.

59
00:02:52,410 --> 00:02:54,840
>> Naam, tunaweza kujaribu na
kurudia utaratibu huu tena.

60
00:02:54,840 --> 00:02:56,756
Hivyo bado tuko katika
katikati ya kujaribu aina

61
00:02:56,756 --> 00:02:58,700
nusu ya kushoto ya safu kamili.

62
00:02:58,700 --> 00:03:00,450
Nusu ya kushoto ya
safu, mimi nina kwenda tu

63
00:03:00,450 --> 00:03:03,910
kiholela kuamua kwamba nusu ya kushoto
itakuwa ndogo kuliko nusu wa kulia,

64
00:03:03,910 --> 00:03:06,550
kwa sababu hii hutokea kwa
wajumbe wa mambo matatu.

65
00:03:06,550 --> 00:03:11,260
>> Na hivyo mimi nina kwenda kusema kwamba
kushoto nusu ya nusu ya kushoto ya safu

66
00:03:11,260 --> 00:03:14,050
ni tu kipengele tano.

67
00:03:14,050 --> 00:03:18,360
Tano, kuwa kipengele moja
safu, tunajua jinsi ya aina yake.

68
00:03:18,360 --> 00:03:21,615
Na hivyo tano ni Iliyopangwa.

69
00:03:21,615 --> 00:03:22,990
Sisi ni kwenda tu kutangaza kwamba.

70
00:03:22,990 --> 00:03:24,890
Ni moja ya kipengele safu.

71
00:03:24,890 --> 00:03:29,015
>> Hivyo tumekuwa sasa yamepangwa
kushoto nusu ya half-- kushoto

72
00:03:29,015 --> 00:03:33,190
au tuseme, tumekuwa yamepangwa
kushoto nusu ya machungwa.

73
00:03:33,190 --> 00:03:37,970
Hivyo sasa, ili bado kamili
ujumla safu ya kushoto nusu,

74
00:03:37,970 --> 00:03:43,481
tunahitaji kutatua nusu ya haki
ya machungwa, au mambo haya.

75
00:03:43,481 --> 00:03:44,230
Je, sisi kufanya hivyo?

76
00:03:44,230 --> 00:03:45,930
Naam, tuna mbili kipengele safu.

77
00:03:45,930 --> 00:03:50,470
Ili tuweze kutatua kushoto nusu
wa safu, ambayo ni mbili.

78
00:03:50,470 --> 00:03:52,090
Mbili ni kipengele moja.

79
00:03:52,090 --> 00:03:55,890
Hivyo ni yamepangwa kwa chaguo-msingi.
Basi tunaweza kutatua nusu ya haki

80
00:03:55,890 --> 00:03:58,530
ya kuwa sehemu ya safu, moja.

81
00:03:58,530 --> 00:04:00,210
Hiyo ni aina ya kama chaguo-msingi.

82
00:04:00,210 --> 00:04:03,610
>> Hii ni mara ya kwanza sasa
tumekuwa kufikiwa kuunganisha hatua.

83
00:04:03,610 --> 00:04:06,135
Tuna kukamilika, ingawa
sisi ni sasa aina ya Furushi down--

84
00:04:06,135 --> 00:04:08,420
na hiyo ni aina ya gumu
Jambo kwa kujirudia ni,

85
00:04:08,420 --> 00:04:10,930
unahitaji kuweka yako
kichwa kuhusu ambapo sisi ni.

86
00:04:10,930 --> 00:04:15,560
Hivyo tumekuwa aina ya kushoto
nusu ya sehemu ya machungwa.

87
00:04:15,560 --> 00:04:21,280
>> Na sasa, tuko katikati ya kuchagua
nusu haki ya fungu machungwa.

88
00:04:21,280 --> 00:04:25,320
Na katika mchakato huo, sisi ni
sasa kuhusu kuwa juu ya hatua,

89
00:04:25,320 --> 00:04:27,850
kuunganisha sehemu mbili kwa pamoja.

90
00:04:27,850 --> 00:04:31,700
Tunapoangalia nusu mbili
wa safu, tunaona mbili na moja.

91
00:04:31,700 --> 00:04:33,880
Ambayo kipengele ni kubwa?

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

93
00:04:35,160 --> 00:04:36,760
>> Basi ni ipi katika kipengele ni kubwa?

94
00:04:36,760 --> 00:04:38,300
Naam, ni mbili au chochote.

95
00:04:38,300 --> 00:04:39,910
Hivyo ni mbili.

96
00:04:39,910 --> 00:04:43,690
Hivyo sasa, tu tena sura
ambapo sisi ni katika mazingira,

97
00:04:43,690 --> 00:04:48,230
sisi yamepangwa
kushoto nusu ya machungwa

98
00:04:48,230 --> 00:04:49,886
na nusu haki ya asili.

99
00:04:49,886 --> 00:04:52,510
Najua nimekuwa iliyopita rangi
tena, lakini hapo ndipo tulikuwa.

100
00:04:52,510 --> 00:04:54,676
Na sababu mimi alifanya hivyo
ni kwa sababu mchakato huu ni

101
00:04:54,676 --> 00:04:57,870
kwenda kuendelea, iterating chini.

102
00:04:57,870 --> 00:05:00,500
Tumekuwa yamepangwa kushoto
nusu ya machungwa zamani

103
00:05:00,500 --> 00:05:02,590
na nusu haki ya machungwa zamani.

104
00:05:02,590 --> 00:05:05,620
>> Sasa, tunahitaji kuunganisha wale
nusu mbili pamoja pia.

105
00:05:05,620 --> 00:05:07,730
Hiyo ni hatua sisi ni juu.

106
00:05:07,730 --> 00:05:11,440
Hivyo tunaona wote wa
mambo ambayo ni sasa kijani,

107
00:05:11,440 --> 00:05:12,972
nusu ya kushoto ya awali safu.

108
00:05:12,972 --> 00:05:14,680
Na sisi kuunganisha wale
kutumia utaratibu huo

109
00:05:14,680 --> 00:05:18,660
tulivyofanya kwa kuunganisha mbili
na moja tu wakati iliyopita.

110
00:05:18,660 --> 00:05:23,080
>> Kushoto nusu, ndogo
kipengele juu ya nusu kushoto ni watano.

111
00:05:23,080 --> 00:05:25,620
Ndogo kipengele katika
nusu haki ni moja.

112
00:05:25,620 --> 00:05:27,370
Ni yupi kati ya hao ni kubwa?

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

114
00:05:29,260 --> 00:05:32,250
>> Ndogo kipengele katika
nusu kushoto ni watano.

115
00:05:32,250 --> 00:05:35,540
Ndogo kipengele katika
nusu haki ni mbili.

116
00:05:35,540 --> 00:05:36,970
Nini madogo?

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

118
00:05:38,160 --> 00:05:41,540
Na kisha mwisho tano na
kitu, tunaweza kusema tano.

119
00:05:41,540 --> 00:05:43,935
>> OK, hivyo picha kubwa, hebu
kuchukua mapumziko kwa ajili ya pili

120
00:05:43,935 --> 00:05:46,080
na takwimu nje ambapo sisi ni.

121
00:05:46,080 --> 00:05:48,580
Kama sisi kuanza kutoka
mwanzo kabisa, sisi

122
00:05:48,580 --> 00:05:51,640
sasa kukamilika kwa
safu kwa ujumla tu

123
00:05:51,640 --> 00:05:53,810
hatua moja ya pseudocode kificho hapa.

124
00:05:53,810 --> 00:05:56,645
Tuna yamepangwa
kushoto nusu ya safu.

125
00:05:56,645 --> 00:05:59,490
>> Kumbuka kwamba awali
Ili ilikuwa tano, mbili, moja.

126
00:05:59,490 --> 00:06:02,570
Kwa kwenda kupitia mchakato huu
na nesting chini na kurudia,

127
00:06:02,570 --> 00:06:05,990
kuendelea kuvunja tatizo
chini katika sehemu ndogo ndogo,

128
00:06:05,990 --> 00:06:09,670
sisi sasa kukamilika
hatua moja ya pseudocode

129
00:06:09,670 --> 00:06:13,940
kwa kuanzia nzima safu.

130
00:06:13,940 --> 00:06:16,670
Tuna yamepangwa nusu wake wa kushoto.

131
00:06:16,670 --> 00:06:18,670
>> Hivyo sasa hebu kufungia huko.

132
00:06:18,670 --> 00:06:23,087
Na sasa hebu kutatua haki
nusu ya awali safu.

133
00:06:23,087 --> 00:06:25,670
Na tunakwenda kufanya hivyo kwa
kwenda kwa iterative sawa

134
00:06:25,670 --> 00:06:30,630
mchakato wa kuvunja mambo chini
na kisha kuunganisha yao kwa pamoja.

135
00:06:30,630 --> 00:06:34,290
>> Hivyo nusu ya kushoto ya
nyekundu, au nusu ya kushoto

136
00:06:34,290 --> 00:06:38,830
ya nusu ya awali ya haki
safu, mimi nina kwenda kusema ni tatu.

137
00:06:38,830 --> 00:06:40,312
Tena, mimi nina kuwa thabiti hapa.

138
00:06:40,312 --> 00:06:42,020
Kama una isiyo ya kawaida
idadi ya vipengele, ni

139
00:06:42,020 --> 00:06:44,478
kweli haina kujali kama
kufanya kushoto moja ndogo

140
00:06:44,478 --> 00:06:45,620
au ndogo moja ya haki.

141
00:06:45,620 --> 00:06:49,230
>> Kitu muhimu ni kwamba wakati wowote
kukutana na tatizo hili katika kuendesha

142
00:06:49,230 --> 00:06:51,422
kuunganisha, unahitaji kuwa thabiti.

143
00:06:51,422 --> 00:06:53,505
Wewe ama daima haja ya
kufanya kushoto upande ndogo

144
00:06:53,505 --> 00:06:55,421
au siku zote haja ya kufanya
upande wa kulia ndogo.

145
00:06:55,421 --> 00:06:57,720
Hapa, nimekuwa waliochaguliwa kwa siku zote
kufanya kushoto upande ndogo

146
00:06:57,720 --> 00:07:04,380
wakati safu yangu, au yangu
ndogo ya safu, ni ya kawaida isiyo ya kawaida.

147
00:07:04,380 --> 00:07:07,420
>> Tatu ni kipengele moja,
na hivyo ni vyema.

148
00:07:07,420 --> 00:07:10,860
Tumekuwa leveraged dhana kwamba
katika mchakato yetu yote hadi sasa.

149
00:07:10,860 --> 00:07:15,020
Hivyo sasa hebu kutatua haki
nusu ya nusu haki,

150
00:07:15,020 --> 00:07:18,210
au nusu haki ya nyekundu.

151
00:07:18,210 --> 00:07:20,390
>> Tena, tunahitaji umegawanyika hii chini.

152
00:07:20,390 --> 00:07:21,910
Hii si moja ya kipengele safu.

153
00:07:21,910 --> 00:07:23,970
Hatuwezi kutangaza ni yamepangwa.

154
00:07:23,970 --> 00:07:27,060
Na hivyo kwanza, tunakwenda
kutatua nusu kushoto.

155
00:07:27,060 --> 00:07:31,620
>> Nusu kushoto ni kipengele moja,
hivyo ni aina ya kama chaguo-msingi.

156
00:07:31,620 --> 00:07:34,840
Kisha tunakwenda aina haki
nusu, ambayo ni kipengele moja.

157
00:07:34,840 --> 00:07:41,250
Ni yamepangwa kwa chaguo-msingi. Na sasa,
tunaweza kuunganisha hizo mbili pamoja.

158
00:07:41,250 --> 00:07:45,820
Nne ni ndogo, na
kisha sita ni ndogo.

159
00:07:45,820 --> 00:07:48,870
>> Tena, tumefanya nini katika hatua hii?

160
00:07:48,870 --> 00:07:52,512
Tumekuwa yamepangwa kushoto
nusu ya nusu ya haki.

161
00:07:52,512 --> 00:07:54,720
Au kwenda nyuma ya awali
rangi wale waliokuwa pale,

162
00:07:54,720 --> 00:07:57,875
tumekuwa yamepangwa kushoto
nusu ya nyekundu laini.

163
00:07:57,875 --> 00:08:00,416
Awali ilikuwa matofali giza
nyekundu na sasa ni laini nyekundu,

164
00:08:00,416 --> 00:08:02,350
au ilikuwa ni nyekundu laini.

165
00:08:02,350 --> 00:08:05,145
>> Na kisha tumekuwa yamepangwa
nusu haki ya nyekundu laini.

166
00:08:05,145 --> 00:08:08,270
Sasa, vizuri, wao uko kijani tena, tu
kwa sababu tunakwenda kupitia mchakato.

167
00:08:08,270 --> 00:08:10,720
Na tuna kurudia
juu ya hili na zaidi.

168
00:08:10,720 --> 00:08:14,695
>> Hivyo sasa tunaweza kuunganisha wale
mbili halves pamoja.

169
00:08:14,695 --> 00:08:15,820
Na kwamba ni nini tunafanya hapa.

170
00:08:15,820 --> 00:08:17,653
Hivyo mstari mweusi tu
kugawanywa nusu ya kushoto

171
00:08:17,653 --> 00:08:19,690
na nusu haki ya huu sehemu namna yo yote.

172
00:08:19,690 --> 00:08:24,310
>> Sisi kulinganisha thamani ndogo
upande wa kushoto wa array--

173
00:08:24,310 --> 00:08:26,710
au udhuru kwangu, ndogo
thamani ya nusu ya kushoto

174
00:08:26,710 --> 00:08:30,790
kwa ndogo thamani ya haki
nusu na kupata kwamba tatu ni ndogo.

175
00:08:30,790 --> 00:08:32,530
Na sasa kidogo ya Biashara, sawa?

176
00:08:32,530 --> 00:08:35,175
Kuna kweli hakuna kitu
kushoto upande wa kushoto.

177
00:08:35,175 --> 00:08:37,440
>> Kuna kitu iliyobaki
upande wa kushoto,

178
00:08:37,440 --> 00:08:40,877
ili tuweze kwa ufanisi
tu move-- tunaweza kutangaza

179
00:08:40,877 --> 00:08:42,960
mapumziko ya ni kweli
yamepangwa na tu upepo ni

180
00:08:42,960 --> 00:08:45,126
juu, kwa sababu kuna kitu
mwingine kulinganisha dhidi ya.

181
00:08:45,126 --> 00:08:49,140
Tunajua kwamba upande wa kulia
ya upande wa kulia ni Iliyopangwa.

182
00:08:49,140 --> 00:08:52,770
>> OK, hivyo sasa hebu kufungia tena na
kufikiri ambapo sisi ni katika hadithi.

183
00:08:52,770 --> 00:08:56,120
Katika safu kwa ujumla,
nini sisi yametimia?

184
00:08:56,120 --> 00:08:58,790
Tumekuwa kweli kukamilisha
sasa hatua moja na hatua mbili.

185
00:08:58,790 --> 00:09:03,300
Sisi yamepangwa nusu ya kushoto, na
sisi yamepangwa nusu ya haki.

186
00:09:03,300 --> 00:09:08,210
>> Hivyo sasa, kwamba bado ni kwa ajili yetu
kuunganisha wale nusu mbili pamoja.

187
00:09:08,210 --> 00:09:11,670
Hivyo sisi kulinganisha chini yenye thamani
kipengele cha kila nusu ya safu

188
00:09:11,670 --> 00:09:13,510
kwa upande wake na kuendelea.

189
00:09:13,510 --> 00:09:16,535
Moja ni chini ya tatu, hivyo moja unaendelea.

190
00:09:16,535 --> 00:09:19,770
>> Mbili ni chini ya tatu, hivyo wawili unaendelea.

191
00:09:19,770 --> 00:09:22,740
Tatu ni chini ya 5, hivyo tatu unaendelea.

192
00:09:22,740 --> 00:09:25,820
Nne ni chini ya 5, hivyo vinne unaendelea.

193
00:09:25,820 --> 00:09:30,210
Kisha tano ni chini ya sita,
na sita ni kwamba bado.

194
00:09:30,210 --> 00:09:31,820
>> Sasa, Mimi najua kuwa na mengi ya hatua.

195
00:09:31,820 --> 00:09:33,636
Na tumekuwa kushoto mengi
ya kumbukumbu katika wake zetu.

196
00:09:33,636 --> 00:09:35,260
Na kwamba ni nini viwanja wale Gray ni.

197
00:09:35,260 --> 00:09:40,540
Na pengine waliona kama kwamba alichukua
muda mrefu kuliko kuingizwa aina, Bubble

198
00:09:40,540 --> 00:09:42,660
aina, au uteuzi aina.

199
00:09:42,660 --> 00:09:45,330
>> Lakini kwa kweli, kwa sababu
mengi ya taratibu hizi

200
00:09:45,330 --> 00:09:48,260
yanayotokea katika time-- sawa
ambayo ni kitu tutaweza, tena,

201
00:09:48,260 --> 00:09:51,100
majadiliano juu wakati sisi majadiliano juu
kujirudia katika siku zijazo video--

202
00:09:51,100 --> 00:09:53,799
algorithm hii kwa kweli
wazi ni kimsingi

203
00:09:53,799 --> 00:09:55,590
tofauti kuliko kitu chochote
tumeona kabla

204
00:09:55,590 --> 00:09:58,820
lakini pia ni kwa kiasi kikubwa
ufanisi zaidi.

205
00:09:58,820 --> 00:09:59,532
>> Kwanini hivyo?

206
00:09:59,532 --> 00:10:01,240
Naam, katika hali mbaya zaidi
kesi, tuna

207
00:10:01,240 --> 00:10:04,830
kugawa n vipengele up
na kisha mawazoni mwao.

208
00:10:04,830 --> 00:10:06,680
Lakini wakati sisi mawazoni
yao, nini sisi ni kufanya

209
00:10:06,680 --> 00:10:11,110
kimsingi mara dufu
ukubwa wa arrays ndogo.

210
00:10:11,110 --> 00:10:14,260
Tuna kundi la kipengele moja
arrays kwamba sisi kwa ufanisi

211
00:10:14,260 --> 00:10:16,290
kuchanganya katika arrays mbili kipengele.

212
00:10:16,290 --> 00:10:18,590
Na kisha tunachukua wale
arrays mbili kipengele

213
00:10:18,590 --> 00:10:21,890
na kuchanganya yao pamoja katika
arrays kipengele wanne, na kadhalika,

214
00:10:21,890 --> 00:10:26,130
na kadhalika, na kadhalika, mpaka sisi
kuwa moja n kipengele safu.

215
00:10:26,130 --> 00:10:29,910
>> Lakini doublings wangapi
gani kuchukua ili kupata n?

216
00:10:29,910 --> 00:10:31,460
Fikiria nyuma kitabu cha simu mfano.

217
00:10:31,460 --> 00:10:34,490
Ni mara ngapi kufanya tuna machozi
kitabu cha simu katika nusu, jinsi wengi zaidi

218
00:10:34,490 --> 00:10:38,370
mara kufanya tuna machozi kitabu cha simu
katika nusu, kama ukubwa wa kitabu cha simu

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

220
00:10:39,680 --> 00:10:41,960
Kuna mmoja tu, sawa?

221
00:10:41,960 --> 00:10:45,360
>> Hivyo kuna baadhi ya aina ya
logarithmic kipengele hapa.

222
00:10:45,360 --> 00:10:48,590
Lakini pia bado wana angalau
kuangalia yote ya n vipengele.

223
00:10:48,590 --> 00:10:53,860
Hivyo katika mazingira ya kesi mbaya,
kuunganisha aina anaendesha katika n logi n.

224
00:10:53,860 --> 00:10:56,160
Tuna kuangalia
wote wa mambo n,

225
00:10:56,160 --> 00:11:02,915
na tuna kuchanganya yao
pamoja katika logi n seti ya hatua.

226
00:11:02,915 --> 00:11:05,290
Katika bora kesi,
safu kikamilifu yamepangwa.

227
00:11:05,290 --> 00:11:06,300
Hiyo ni kubwa.

228
00:11:06,300 --> 00:11:09,980
Lakini kulingana na algorithm sisi hapa,
bado tuna kugawa na mawazoni.

229
00:11:09,980 --> 00:11:13,290
Ingawa katika kesi hiyo,
recombining ni aina ya ufanisi.

230
00:11:13,290 --> 00:11:14,720
Ni si inahitajika.

231
00:11:14,720 --> 00:11:17,580
Lakini sisi bado kwenda kwa njia ya
mchakato mzima hata hivyo.

232
00:11:17,580 --> 00:11:21,290
>> Hivyo katika kesi bora
na katika hali mbaya zaidi,

233
00:11:21,290 --> 00:11:24,970
algorithm hii anaendesha katika n logi n mara.

234
00:11:24,970 --> 00:11:29,130
Kuunganisha aina ni dhahiri kidogo trickier
kuliko nyingine kuu kuchagua algorithms

235
00:11:29,130 --> 00:11:33,470
tumekuwa aliyesema kuhusu CS50 lakini ni
kikubwa na nguvu zaidi.

236
00:11:33,470 --> 00:11:35,400
>> Na hivyo kama wewe milele kupata
nafasi ya haja yake

237
00:11:35,400 --> 00:11:38,480
au kuitumia kutatua
kubwa seti data, kupata

238
00:11:38,480 --> 00:11:41,940
kichwa wako karibu wazo la recursion
ni kwenda kuwa kweli nguvu.

239
00:11:41,940 --> 00:11:45,270
Na ni kwenda kufanya yako
Mipango kweli ufanisi mkubwa zaidi

240
00:11:45,270 --> 00:11:48,700
kutumia kuunganisha aina dhidi ya kitu kingine chochote.

241
00:11:48,700 --> 00:11:49,640
Mimi nina Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Hii ni CS50.

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