1
00:00:00,000 --> 00:00:04,419
>> [Predvaja glasba]

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

3
00:00:05,401 --> 00:00:08,460
>> Doug LLOYD: OK, tako da se združita
nekako je še en algoritem

4
00:00:08,460 --> 00:00:11,200
da bomo lahko uporabite rešiti
elementi matrike.

5
00:00:11,200 --> 00:00:14,480
Toda, kot bomo videli, je to dobil
zelo bistvena razlika

6
00:00:14,480 --> 00:00:17,850
od izbor sort, bubble
razvrščanje in vstavljanje nekako

7
00:00:17,850 --> 00:00:20,280
zaradi katerih je v resnici zelo pameten.

8
00:00:20,280 --> 00:00:24,290
>> Osnovna ideja spajanje
Razvrsti je razvrstiti manjše nize

9
00:00:24,290 --> 00:00:27,430
in nato združite tiste nize
skupaj ali združijo them--

10
00:00:27,430 --> 00:00:31,440
zato name-- v urejenem zaporedju.

11
00:00:31,440 --> 00:00:34,230
Tako, da zlivanjem ne
to je s povečanjem orodje

12
00:00:34,230 --> 00:00:37,290
imenovano rekurzija, ki je kaj
bomo govorili o tem kmalu,

13
00:00:37,290 --> 00:00:39,720
vendar nismo zares govorila še.

14
00:00:39,720 --> 00:00:43,010
>> Tukaj je osnovna ideja zlivanjem.

15
00:00:43,010 --> 00:00:46,320
Razvrstiti levo polovico matrike,
ob predpostavki, n je večji od 1.

16
00:00:46,320 --> 00:00:49,980
In kaj mislim, ko rečem
predpostavki n večji od 1, je,

17
00:00:49,980 --> 00:00:53,970
Mislim, da se lahko strinjamo, da če niz
Samo sestoji iz enega samega elementa,

18
00:00:53,970 --> 00:00:54,680
to je urejeno.

19
00:00:54,680 --> 00:00:56,560
Mi dejansko ne potrebujemo
storiti ničesar, da bi to.

20
00:00:56,560 --> 00:00:58,059
Mi lahko samo razglaša bodo razporejene.

21
00:00:58,059 --> 00:01:00,110
To je samo en element.

22
00:01:00,110 --> 00:01:03,610
>> Torej psevdokoda, še enkrat, je
razvrstiti levi polovici matrike,

23
00:01:03,610 --> 00:01:08,590
nato razvrstite desno polovico matrika,
nato združite obe polovici skupaj.

24
00:01:08,590 --> 00:01:11,040
Zdaj pa že boste morda
misleč, da nekako le

25
00:01:11,040 --> 00:01:14,080
Sliši se, kot da ste zavlačevanja the--
ste dejansko ne počne ničesar.

26
00:01:14,080 --> 00:01:16,330
Praviš razvrstiti levo
pol, razvrstiti desno polovico,

27
00:01:16,330 --> 00:01:19,335
vendar nisi povedal
me, kako to počnete.

28
00:01:19,335 --> 00:01:22,220
>> Ampak ne pozabite, da dokler
matrika je en sam element,

29
00:01:22,220 --> 00:01:23,705
bomo lahko razglasila razporejene.

30
00:01:23,705 --> 00:01:25,330
Potem bomo lahko samo jih združiti skupaj.

31
00:01:25,330 --> 00:01:27,788
In to je pravzaprav
Temeljna ideja zlivanjem,

32
00:01:27,788 --> 00:01:31,150
je, da razgradi, tako da
vaši nizi so velikosti enega.

33
00:01:31,150 --> 00:01:33,430
In potem ko ste obnovili od tam.

34
00:01:33,430 --> 00:01:35,910
>> Zlivanjem je definitivno
zapleten algoritem.

35
00:01:35,910 --> 00:01:38,210
In to je tudi malo
zapleten vizualizirati.

36
00:01:38,210 --> 00:01:41,870
Torej upajmo, vizualizacija, ki sem
imajo tu vam bo pomagal sledite skupaj.

37
00:01:41,870 --> 00:01:45,640
In bom poskusil moje najbolje, da pripovedujejo stvari
in nadaljuje skozi to malo bolj

38
00:01:45,640 --> 00:01:49,180
počasneje od ostalih,
samo, da upajmo, da bi dobili svojo glavo

39
00:01:49,180 --> 00:01:51,800
okoli ideje zlivanjem.

40
00:01:51,800 --> 00:01:54,680
>> Torej imamo isto vrsto kot
drugi sortiranje algoritem videos

41
00:01:54,680 --> 00:01:57,120
če ste videli them--
Niz šest element.

42
00:01:57,120 --> 00:02:02,110
In naša psevdokoda koda tukaj je nekako
levo polovico, razvrstiti desno polovico,

43
00:02:02,110 --> 00:02:03,890
združiti obe polovici skupaj.

44
00:02:03,890 --> 00:02:09,770
Tako da je to zelo temno opečnato rdeča
Niz in razvrstiti levo polovico tega.

45
00:02:09,770 --> 00:02:13,380
>> Torej za zdaj, gremo
prezreti stvari na desni strani.

46
00:02:13,380 --> 00:02:15,740
To je tam, vendar smo
ne pa v tej fazi še ni.

47
00:02:15,740 --> 00:02:18,220
Nismo na Razvrščanje
Desna polovica matriki.

48
00:02:18,220 --> 00:02:21,037
Mi smo na vrsto po levi
polovica matriki.

49
00:02:21,037 --> 00:02:22,870
In samo zavoljo
, da so malo bolj

50
00:02:22,870 --> 00:02:26,480
Jasno, da sem se lahko nanašajo
s tem, kar korak smo na,

51
00:02:26,480 --> 00:02:29,800
Jaz grem za preklop
Barva tega niza v oranžno.

52
00:02:29,800 --> 00:02:33,190
Zdaj smo še vedno govorimo o
Enako levo polovico prvotnega niza.

53
00:02:33,190 --> 00:02:38,520
Vendar sem upal, da ga bi mogli
nanašajo na barve različnih predmetov,

54
00:02:38,520 --> 00:02:40,900
da bomo, da je nekoliko bolj
jasno, kaj se dogaja tukaj.

55
00:02:40,900 --> 00:02:43,270
>> OK, tako da zdaj imamo
tri element matrike.

56
00:02:43,270 --> 00:02:46,420
Kako bomo levo polovico te vrste
matrika, ki je še vedno ta korak?

57
00:02:46,420 --> 00:02:49,400
Poskušamo rešiti levo
polovica opečnato rdeča array--

58
00:02:49,400 --> 00:02:52,410
leva polovica katerih
Sem zdaj obarvana oranžno.

59
00:02:52,410 --> 00:02:54,840
>> No, lahko bi poskusila
Ta postopek ponovite.

60
00:02:54,840 --> 00:02:56,756
Torej smo še vedno v
Sredi poskuša rešiti

61
00:02:56,756 --> 00:02:58,700
levo polovico celotnega niza.

62
00:02:58,700 --> 00:03:00,450
Leva polovica
matrika, sem le, da bo

63
00:03:00,450 --> 00:03:03,910
samovoljno odloči, da leva polovica
bo manjši kot desni polovici,

64
00:03:03,910 --> 00:03:06,550
ker se to zgodi
sestavljen iz treh elementov.

65
00:03:06,550 --> 00:03:11,260
>> In tako bom rekel, da je
leva polovica levi polovici matrike

66
00:03:11,260 --> 00:03:14,050
je le element pet.

67
00:03:14,050 --> 00:03:18,360
Pet, pri čemer je en sam element
matrika, vemo, kako ga rešiti.

68
00:03:18,360 --> 00:03:21,615
In tako pet je razvrščen.

69
00:03:21,615 --> 00:03:22,990
Mi smo le, da bo razglasila, da je.

70
00:03:22,990 --> 00:03:24,890
To je en sam element matrike.

71
00:03:24,890 --> 00:03:29,015
>> Tako smo zdaj razporejene
leva polovica kazenski half--

72
00:03:29,015 --> 00:03:33,190
ali bolje, smo razporejene
leva polovica oranžno.

73
00:03:33,190 --> 00:03:37,970
Zdaj, da bi se vedno nahaja
leva polovica splošnim Array je,

74
00:03:37,970 --> 00:03:43,481
moramo razvrstiti desno polovico
od oranžne, ali te stvari.

75
00:03:43,481 --> 00:03:44,230
Kako to storimo?

76
00:03:44,230 --> 00:03:45,930
No, imamo niz dveh elementov.

77
00:03:45,930 --> 00:03:50,470
Tako bomo lahko z levo polovico razvrstiti
matrike, ki je dva.

78
00:03:50,470 --> 00:03:52,090
Dva enojna element.

79
00:03:52,090 --> 00:03:55,890
Torej je to urejeno privzeto.
Potem bomo lahko z desno polovico razvrstiti

80
00:03:55,890 --> 00:03:58,530
tega dela polja, v eno.

81
00:03:58,530 --> 00:04:00,210
To je nekako privzeto.

82
00:04:00,210 --> 00:04:03,610
>> To je sedaj prvič
smo dosegli spajanje korak.

83
00:04:03,610 --> 00:04:06,135
Zaključili smo, čeprav
smo zdaj nekako ugnezdena down--

84
00:04:06,135 --> 00:04:08,420
in to je neke vrste rafiniran
stvar z rekurzije je,

85
00:04:08,420 --> 00:04:10,930
morate, da bo vaš
glavo o tem, kje smo.

86
00:04:10,930 --> 00:04:15,560
Zato smo nekako v levo
polovica oranžno odseka.

87
00:04:15,560 --> 00:04:21,280
>> In zdaj, smo sredi sortiranje
desno polovico oranžnega odseka.

88
00:04:21,280 --> 00:04:25,320
In v tem procesu, smo
Zdaj bo kmalu na koraku

89
00:04:25,320 --> 00:04:27,850
združiti obe polovici skupaj.

90
00:04:27,850 --> 00:04:31,700
Ko gledamo na dveh polovic
array, vidimo dva in enega.

91
00:04:31,700 --> 00:04:33,880
Kateri element je manjša?

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

93
00:04:35,160 --> 00:04:36,760
>> Potem kateri element je manjša?

94
00:04:36,760 --> 00:04:38,300
No, to je dva ali nič.

95
00:04:38,300 --> 00:04:39,910
Torej, to je dva.

96
00:04:39,910 --> 00:04:43,690
Torej sedaj, samo da spet okvir
kjer smo v okviru

97
00:04:43,690 --> 00:04:48,230
smo razporejene
leva polovica oranžne

98
00:04:48,230 --> 00:04:49,886
in desno polovico izvora.

99
00:04:49,886 --> 00:04:52,510
Vem, da sem spremenila barve
spet, ampak da je, kjer smo bili.

100
00:04:52,510 --> 00:04:54,676
In razlog, zakaj sem to storil
je zato, ker je ta proces

101
00:04:54,676 --> 00:04:57,870
dogaja, da se dogaja, ponavljanjem dol.

102
00:04:57,870 --> 00:05:00,500
Mi smo razporejene levo
polovica nekdanjega oranžne

103
00:05:00,500 --> 00:05:02,590
in desno polovico nekdanjega oranžno.

104
00:05:02,590 --> 00:05:05,620
>> Zdaj moramo združiti tiste,
Polovici skupaj preveč.

105
00:05:05,620 --> 00:05:07,730
To je korak, da smo na.

106
00:05:07,730 --> 00:05:11,440
Zato menimo, da vse
elemente, ki so zdaj zelena,

107
00:05:11,440 --> 00:05:12,972
levo polovico prvotnega niza.

108
00:05:12,972 --> 00:05:14,680
In smo združiti tiste,
po istem postopku

109
00:05:14,680 --> 00:05:18,660
smo naredili za združitev dveh
in eno samo trenutek nazaj.

110
00:05:18,660 --> 00:05:23,080
>> Leva polovica, najmanjša
element na levi polovici je pet.

111
00:05:23,080 --> 00:05:25,620
Najmanjši element na
desna polovica je ena.

112
00:05:25,620 --> 00:05:27,370
Kateri od teh je manjši?

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

114
00:05:29,260 --> 00:05:32,250
>> Najmanjši element na
leva polovica je pet.

115
00:05:32,250 --> 00:05:35,540
Najmanjši element na
desna polovica je dva.

116
00:05:35,540 --> 00:05:36,970
Kakšna je najmanjša?

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

118
00:05:38,160 --> 00:05:41,540
In potem na koncu pet in
nič, lahko rečemo, pet.

119
00:05:41,540 --> 00:05:43,935
>> OK, tako velika slika, kaj je
odmor za sekundo

120
00:05:43,935 --> 00:05:46,080
in ugotoviti, kje smo.

121
00:05:46,080 --> 00:05:48,580
Če smo začeli z
samega začetka smo

122
00:05:48,580 --> 00:05:51,640
so zdaj končana za
celotna matrika samo

123
00:05:51,640 --> 00:05:53,810
en korak kode psevdokoda tukaj.

124
00:05:53,810 --> 00:05:56,645
Smo razporejene
leva polovica matriki.

125
00:05:56,645 --> 00:05:59,490
>> Spomnimo se, da je bila prvotna
Da bi imel pet, dve, ena.

126
00:05:59,490 --> 00:06:02,570
Skozi ta proces
in gnezdijo navzdol in ponavljanje,

127
00:06:02,570 --> 00:06:05,990
nadaljuje, da bi prekinil problem
v manjše in manjše dele,

128
00:06:05,990 --> 00:06:09,670
smo zdaj končana
korak eden od psevdokoda

129
00:06:09,670 --> 00:06:13,940
za celotno začetno zaporedje.

130
00:06:13,940 --> 00:06:16,670
Imamo razporejene svojo levo polovico.

131
00:06:16,670 --> 00:06:18,670
>> Torej, zdaj pa zamrzne tam.

132
00:06:18,670 --> 00:06:23,087
In sedaj dajmo razvrstiti pravico
polovico prvotnega niza.

133
00:06:23,087 --> 00:06:25,670
In bomo storiti, da jih
gredo skozi isto iterativni

134
00:06:25,670 --> 00:06:30,630
Proces breaking stvari navzdol
in jih nato združujejo.

135
00:06:30,630 --> 00:06:34,290
>> Torej leva polovica
rdeče ali levo polovico

136
00:06:34,290 --> 00:06:38,830
desne polovice originalnega
matrika, bom rekel, je tri.

137
00:06:38,830 --> 00:06:40,312
Spet sem biti skladna tukaj.

138
00:06:40,312 --> 00:06:42,020
Če imate neparno
število elementov tako,

139
00:06:42,020 --> 00:06:44,478
sploh ni pomembno, ali
naredite levo ena manjša

140
00:06:44,478 --> 00:06:45,620
ali desno ena manjša.

141
00:06:45,620 --> 00:06:49,230
>> Pomembno je, da vsakič, ko vas
naleteli na to težavo pri vodenju

142
00:06:49,230 --> 00:06:51,422
Združitev, morate biti dosledni.

143
00:06:51,422 --> 00:06:53,505
Ali boste vedno morali
narediti levo stran manjša

144
00:06:53,505 --> 00:06:55,421
ali vedno treba narediti
na desni strani manjši.

145
00:06:55,421 --> 00:06:57,720
Tukaj sem izbral, da vedno
da leva stran manjša

146
00:06:57,720 --> 00:07:04,380
ko je moj matrika, ali moj
sub-matrika, je liho velikosti.

147
00:07:04,380 --> 00:07:07,420
>> Tri je posamezen element,
in se tako razporejene.

148
00:07:07,420 --> 00:07:10,860
Mi smo vzvodom to domnevo
vsej naši celotnem procesu doslej.

149
00:07:10,860 --> 00:07:15,020
Torej, zdaj pa si razvrstiti pravico
polovica desni polovici,

150
00:07:15,020 --> 00:07:18,210
ali desno polovico rdeče.

151
00:07:18,210 --> 00:07:20,390
>> Spet moramo razdeliti to navzdol.

152
00:07:20,390 --> 00:07:21,910
To ni en sam element matrika.

153
00:07:21,910 --> 00:07:23,970
Ne moremo razglaša razporejene.

154
00:07:23,970 --> 00:07:27,060
In tako najprej gremo
razvrstiti levo polovico.

155
00:07:27,060 --> 00:07:31,620
>> Leva polovica je en sam element,
tako da je nekako privzeto.

156
00:07:31,620 --> 00:07:34,840
Potem bomo razvrstiti pravico
pol, ki je en sam element.

157
00:07:34,840 --> 00:07:41,250
To je urejeno privzeto. In zdaj,
moremo združiti tiste dve skupaj.

158
00:07:41,250 --> 00:07:45,820
Štiri je manjše, in
nato šest manjši.

159
00:07:45,820 --> 00:07:48,870
>> Še enkrat, kaj smo naredili na tem mestu?

160
00:07:48,870 --> 00:07:52,512
Mi smo razporejene levo
polovica desni polovici.

161
00:07:52,512 --> 00:07:54,720
Ali gre nazaj v izvirniku
Barve, ki so bili tam,

162
00:07:54,720 --> 00:07:57,875
smo razporejene levo
polovica mehkejšega rdečega.

163
00:07:57,875 --> 00:08:00,416
To je bil sprva temno opeke
rdeče in zdaj je mehkejša rdeča,

164
00:08:00,416 --> 00:08:02,350
ali pa je mehkejša rdeče.

165
00:08:02,350 --> 00:08:05,145
>> In potem smo razporejene
Desna polovica mehkejšega rdečega.

166
00:08:05,145 --> 00:08:08,270
Sedaj, dobro, oni zeleni spet, samo
ker gremo skozi proces.

167
00:08:08,270 --> 00:08:10,720
In moramo ponoviti
to znova in znova.

168
00:08:10,720 --> 00:08:14,695
>> Torej, zdaj smo lahko združi tiste,
Polovici skupaj.

169
00:08:14,695 --> 00:08:15,820
In to je tisto, kar počnemo tukaj.

170
00:08:15,820 --> 00:08:17,653
Torej črno črto tik
razdeljen levo polovico

171
00:08:17,653 --> 00:08:19,690
in desno polovico te vrste dela.

172
00:08:19,690 --> 00:08:24,310
>> Primerjamo najmanjšo vrednost
na levi strani array--

173
00:08:24,310 --> 00:08:26,710
ali oprostite, najmanjši
Vrednost levi polovici

174
00:08:26,710 --> 00:08:30,790
do najmanjše vrednosti pravice
pol, in ugotovili, da je tri manjše.

175
00:08:30,790 --> 00:08:32,530
In zdaj malo optimizacije, kajne?

176
00:08:32,530 --> 00:08:35,175
Tam je pravzaprav nič
levo na levi strani.

177
00:08:35,175 --> 00:08:37,440
>> Nič ni preostalo
na levi strani,

178
00:08:37,440 --> 00:08:40,877
tako da bomo lahko učinkovito
Samo move-- moremo razglasiti

179
00:08:40,877 --> 00:08:42,960
preostanek pa je pravzaprav
razporejene in šele tack

180
00:08:42,960 --> 00:08:45,126
no, saj ni nič
drugega, da se primerjajo.

181
00:08:45,126 --> 00:08:49,140
In vemo, da je desna stran
na desni strani je razvrščen.

182
00:08:49,140 --> 00:08:52,770
>> OK, zdaj pa zamrzne znova in
ugotovimo, kje smo v zgodbi.

183
00:08:52,770 --> 00:08:56,120
V celotni niz,
Kaj smo dosegli?

184
00:08:56,120 --> 00:08:58,790
Mi smo dejansko dosegli
Sedaj koraka ena in dva korak.

185
00:08:58,790 --> 00:09:03,300
Razporejene smo levo polovico, in
smo razporejene desni polovici.

186
00:09:03,300 --> 00:09:08,210
>> Torej sedaj, vse, kar ostane, je za nas
za združitev teh dveh polovic skupaj.

187
00:09:08,210 --> 00:09:11,670
Tako smo primerjali najnižja vrednoti
element vsaki polovici matrike

188
00:09:11,670 --> 00:09:13,510
v zameno in nadaljujte.

189
00:09:13,510 --> 00:09:16,535
Eden od njih je manj kot tri, tako da nekdo gre.

190
00:09:16,535 --> 00:09:19,770
>> Dva manjša od tri, tako da dva gre.

191
00:09:19,770 --> 00:09:22,740
Tri je manj kot 5, tako da tri gre.

192
00:09:22,740 --> 00:09:25,820
Štiri je manj kot 5, tako da štiri gre.

193
00:09:25,820 --> 00:09:30,210
Potem je pet manj kot šest,
in šest je vse, kar ostane.

194
00:09:30,210 --> 00:09:31,820
>> Zdaj vem, da je bilo veliko korakov.

195
00:09:31,820 --> 00:09:33,636
In smo pustili veliko
spomina v našem zgledu.

196
00:09:33,636 --> 00:09:35,260
In to je tisto, kar ti sivi kvadrati so.

197
00:09:35,260 --> 00:09:40,540
In verjetno se počutil, kot da je vzel
Veliko več od vstavitve vrste, mehurček

198
00:09:40,540 --> 00:09:42,660
razvrščanje, ali izbira vrste.

199
00:09:42,660 --> 00:09:45,330
>> Ampak v resnici, ker
Veliko teh procesov

200
00:09:45,330 --> 00:09:48,260
se dogaja na isti time--
kar je nekaj, kar bomo spet

201
00:09:48,260 --> 00:09:51,100
govori o tem, ko govorimo o
rekurzija v prihodnosti video--

202
00:09:51,100 --> 00:09:53,799
Ta algoritem dejansko
jasno je bistveno

203
00:09:53,799 --> 00:09:55,590
drugačna od vsega,
smo videli pred

204
00:09:55,590 --> 00:09:58,820
vendar je tudi bistveno
bolj učinkovito.

205
00:09:58,820 --> 00:09:59,532
>> Zakaj je tako?

206
00:09:59,532 --> 00:10:01,240
No, v najslabšem
scenarij, imamo

207
00:10:01,240 --> 00:10:04,830
razdeliti n elementov up
in jih nato rekombinacije.

208
00:10:04,830 --> 00:10:06,680
Toda, ko smo rekombinacije
jim, kaj delamo

209
00:10:06,680 --> 00:10:11,110
je v bistvu podvojitev
velikost manjših polj.

210
00:10:11,110 --> 00:10:14,260
Imamo kup enega elementa
nizi da učinkovito

211
00:10:14,260 --> 00:10:16,290
združiti v dveh matrikah elementov.

212
00:10:16,290 --> 00:10:18,590
In potem smo se tisti,
dve nizi elementov

213
00:10:18,590 --> 00:10:21,890
in jih združite v
štirje nizi elementov, in tako naprej,

214
00:10:21,890 --> 00:10:26,130
in tako naprej, in tako naprej, dokler ne bomo
ima en sam n element matriko.

215
00:10:26,130 --> 00:10:29,910
>> Toda koliko podvajanjih
je potrebno, da pridete do n?

216
00:10:29,910 --> 00:10:31,460
Pomislite na primer telefonski imenik.

217
00:10:31,460 --> 00:10:34,490
Kolikokrat moramo trgati
imenika na pol, koliko več

218
00:10:34,490 --> 00:10:38,370
krat imamo trgati imenika
na pol, če velikost imenika

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

220
00:10:39,680 --> 00:10:41,960
Obstaja samo ena, kajne?

221
00:10:41,960 --> 00:10:45,360
>> Torej je neke vrste
logaritemsko element tukaj.

222
00:10:45,360 --> 00:10:48,590
Vendar imamo tudi še vsaj
poglej vse n elementov.

223
00:10:48,590 --> 00:10:53,860
Torej, v najslabšem primeru,
zlivanjem teče v n log n.

224
00:10:53,860 --> 00:10:56,160
Moramo gledati
vse n elementov,

225
00:10:56,160 --> 00:11:02,915
in jih moramo kombinirati
skupaj v dnevniku n sklopov korakov.

226
00:11:02,915 --> 00:11:05,290
V najboljšem primeru,
array je popolnoma urejeno.

227
00:11:05,290 --> 00:11:06,300
To je super.

228
00:11:06,300 --> 00:11:09,980
Temveč temelji na algoritmu imamo tod
bomo še vedno morali razdeliti in rekombinacije.

229
00:11:09,980 --> 00:11:13,290
Čeprav je v tem primeru
rekombinacija je nekako neučinkovita.

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

231
00:11:14,720 --> 00:11:17,580
Vendar smo še vedno iti skozi
celoten proces anyway.

232
00:11:17,580 --> 00:11:21,290
>> Torej v najboljšem primeru
in v najslabšem primeru,

233
00:11:21,290 --> 00:11:24,970
Ta algoritem teče v n log n časa.

234
00:11:24,970 --> 00:11:29,130
Zlivanjem je definitivno malo težje
od drugih glavnih algoritmov za razvrščanje

235
00:11:29,130 --> 00:11:33,470
smo se pogovarjali o CS50, vendar je
bistveno močnejši.

236
00:11:33,470 --> 00:11:35,400
>> In tako, če boste kdaj našli
priložnost, da jo potrebujejo

237
00:11:35,400 --> 00:11:38,480
ali jo uporabite za razvrščate
Velik nabor podatkov, pridobivanje

238
00:11:38,480 --> 00:11:41,940
tvoja glava okoli idejo rekurzije
se bo res močna.

239
00:11:41,940 --> 00:11:45,270
In to se dogaja, da se vaš
programi res veliko bolj učinkovito

240
00:11:45,270 --> 00:11:48,700
uporabo zlivanjem versus karkoli drugega.

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

242
00:11:49,640 --> 00:11:51,970
To je CS50.

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