1
00:00:00,000 --> 00:00:04,419
>> [Zenelejátszási]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, így egy összevont
Rendezés még egy algoritmus

4
00:00:08,460 --> 00:00:11,200
hogy tudjuk használni, hogy rendet
A tömb elemeit egy.

5
00:00:11,200 --> 00:00:14,480
De mint látni fogjuk, hogy van egy
Nagyon alapvető különbség

6
00:00:14,480 --> 00:00:17,850
a kijelölés sort, buborék
rendezése és beillesztés sort

7
00:00:17,850 --> 00:00:20,280
hogy teszik igazán elég okos.

8
00:00:20,280 --> 00:00:24,290
>> Az alapgondolata merge
rendezés rendezni kisebb tömbök

9
00:00:24,290 --> 00:00:27,430
és egyesítsük azokat a tömböket
együtt, vagy összeolvad them--

10
00:00:27,430 --> 00:00:31,440
így a name-- rendezett sorrendben.

11
00:00:31,440 --> 00:00:34,230
Az hogy merge sort csinál
ez kiaknázásával a szerszám

12
00:00:34,230 --> 00:00:37,290
úgynevezett rekurzív, amely a mi
fogunk beszélni hamarosan,

13
00:00:37,290 --> 00:00:39,720
de még nem igazán beszéltünk még.

14
00:00:39,720 --> 00:00:43,010
>> Itt az alap ötlet mögött merge sort.

15
00:00:43,010 --> 00:00:46,320
Rendezés a bal fele a tömb,
feltételezve, n értéke 1-nél nagyobb.

16
00:00:46,320 --> 00:00:49,980
És mire gondolok, amikor azt mondom,
feltételezve, n értéke 1-nél nagyobb,

17
00:00:49,980 --> 00:00:53,970
Azt hiszem, abban megegyezhetünk, hogy ha egy tömb
csak áll egy elem,

18
00:00:53,970 --> 00:00:54,680
ez válogatni.

19
00:00:54,680 --> 00:00:56,560
Valójában nem kell
hogy bármit hozzá.

20
00:00:56,560 --> 00:00:58,059
Mi is csak azt jelenti ki kell válogatni.

21
00:00:58,059 --> 00:01:00,110
Ez csak egyetlen elem.

22
00:01:00,110 --> 00:01:03,610
>> Tehát a pszeudokódja, újra,
A legújabb bal fele a tömb,

23
00:01:03,610 --> 00:01:08,590
majd rendezni a jobb oldalán a tömb,
majd egyesíteni a két fél együtt.

24
00:01:08,590 --> 00:01:11,040
Most már lehet, hogy
gondoltam, ez a fajta csak

25
00:01:11,040 --> 00:01:14,080
úgy hangzik, mint te teszed le the--
te valójában nem csinál semmit.

26
00:01:14,080 --> 00:01:16,330
Azt mondod, hogy rendezze a bal
fele, rendezni a jobb fele,

27
00:01:16,330 --> 00:01:19,335
de nem mondasz
nekem, hogyan csinálod.

28
00:01:19,335 --> 00:01:22,220
>> De ne feledjük, hogy amíg
Egy tömb egyetlen elem,

29
00:01:22,220 --> 00:01:23,705
kijelenthetjük, hogy válogatni.

30
00:01:23,705 --> 00:01:25,330
Akkor csak összekapcsolják őket.

31
00:01:25,330 --> 00:01:27,788
És ez valóban a
alapgondolata merge sort,

32
00:01:27,788 --> 00:01:31,150
van lebontani, hogy
A tömbök mérete egy.

33
00:01:31,150 --> 00:01:33,430
És akkor újjáépíteni onnan.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort határozottan
egy bonyolult algoritmus.

35
00:01:35,910 --> 00:01:38,210
És ez is egy kicsit
bonyolult elképzelni.

36
00:01:38,210 --> 00:01:41,870
Így remélhetőleg, a vizualizáció, hogy én
Van itt segít kövesse végig.

37
00:01:41,870 --> 00:01:45,640
És én megpróbálom a legjobb tudásom szerint elbeszélni dolgokat
és folytatódik ez egy kicsit

38
00:01:45,640 --> 00:01:49,180
lassabban, mint a többinek
csak azért, hogy remélhetőleg a fejed

39
00:01:49,180 --> 00:01:51,800
az egész ötlet, amin merge sort.

40
00:01:51,800 --> 00:01:54,680
>> Tehát akkor ugyanaz a tömb, mint a
Más rendezési algoritmus videók

41
00:01:54,680 --> 00:01:57,120
ha láttad them--
hat elem tömb.

42
00:01:57,120 --> 00:02:02,110
És mi pszeudokódja kódot itt van valami
A bal felében rendezni a jobb fele,

43
00:02:02,110 --> 00:02:03,890
egyesíti a két fél együtt.

44
00:02:03,890 --> 00:02:09,770
Szóval vessünk ennek a nagyon sötét téglavörös
tömb és rendezni a bal fele.

45
00:02:09,770 --> 00:02:13,380
>> Tehát egyelőre, megyünk
hogy figyelmen kívül hagyja a dolgokat a jobb oldalon.

46
00:02:13,380 --> 00:02:15,740
Ott van, de nem vagyunk
Nem a megfelelő lépésben még.

47
00:02:15,740 --> 00:02:18,220
Nem vagyunk sort a
jobb felét a tömbben.

48
00:02:18,220 --> 00:02:21,037
Mi vagyunk a sort a bal
a fele a tömb.

49
00:02:21,037 --> 00:02:22,870
És csak a kedvéért
Az, hogy egy kicsit többet

50
00:02:22,870 --> 00:02:26,480
egyértelmű, így tudok hivatkozni
hogy milyen lépéseket vagyunk,

51
00:02:26,480 --> 00:02:29,800
Megyek váltani a
színes e állítva narancssárga.

52
00:02:29,800 --> 00:02:33,190
Most, mi még mindig beszélünk
ugyanolyan bal fele az eredeti tömb.

53
00:02:33,190 --> 00:02:38,520
De remélem, hogy azáltal, hogy
olvassa el a színeket a különböző elemek,

54
00:02:38,520 --> 00:02:40,900
ez lesz, hogy ez egy kicsit több
világos, hogy mi folyik itt.

55
00:02:40,900 --> 00:02:43,270
>> OK, így most van egy
három elem tömb.

56
00:02:43,270 --> 00:02:46,420
Hogyan rendezni a bal fele ezt
tömb, amely még mindig ezt a lépést?

57
00:02:46,420 --> 00:02:49,400
Megpróbáljuk rendezni a bal
fele a téglavörös array--

58
00:02:49,400 --> 00:02:52,410
a bal fele, amely
Már most narancssárga színű.

59
00:02:52,410 --> 00:02:54,840
>> Nos, mi is megpróbáljuk
ismételje meg ezt a folyamatot újra.

60
00:02:54,840 --> 00:02:56,756
Szóval mi még mindig a
közepén megpróbálja rendezni

61
00:02:56,756 --> 00:02:58,700
A bal fele a teljes tömb.

62
00:02:58,700 --> 00:03:00,450
A bal fele
tömb, én csak fog

63
00:03:00,450 --> 00:03:03,910
hogy pontosan eldönteni, hogy a bal fél
kisebb lesz, mint a jobb fél,

64
00:03:03,910 --> 00:03:06,550
mert ez történik
áll három elemet.

65
00:03:06,550 --> 00:03:11,260
>> És így fogom mondani, hogy a
bal fele a bal fele a tömb

66
00:03:11,260 --> 00:03:14,050
csak az elem öt.

67
00:03:14,050 --> 00:03:18,360
Öt, hogy egyetlen elem
tömb, tudjuk, hogyan kell rendezni.

68
00:03:18,360 --> 00:03:21,615
És így öt rendezve.

69
00:03:21,615 --> 00:03:22,990
Mi csak megy, hogy nyilvánítsa.

70
00:03:22,990 --> 00:03:24,890
Ez egyetlen elem tömb.

71
00:03:24,890 --> 00:03:29,015
>> Így már most válogatni a
bal fele a bal half--

72
00:03:29,015 --> 00:03:33,190
vagy inkább, amit válogatni a
bal fele a narancs.

73
00:03:33,190 --> 00:03:37,970
Tehát most, hogy még a teljes
a teljes tömb bal felét,

74
00:03:37,970 --> 00:03:43,481
meg kell rendezni a jobb fele
A narancs, vagy ez a cucc.

75
00:03:43,481 --> 00:03:44,230
Hogyan csináljuk ezt?

76
00:03:44,230 --> 00:03:45,930
Nos, van egy két elem tömb.

77
00:03:45,930 --> 00:03:50,470
Így tudjuk rendezni a bal fele
a tömb, ami két.

78
00:03:50,470 --> 00:03:52,090
Két egyetlen eleme.

79
00:03:52,090 --> 00:03:55,890
Szóval ez sorolva alapértelmezett.
Akkor rendezni a jobb fele

80
00:03:55,890 --> 00:03:58,530
az említett rész a tömb, az egyik.

81
00:03:58,530 --> 00:04:00,210
Ez a fajta alapból.

82
00:04:00,210 --> 00:04:03,610
>> Ez most az első alkalommal
elértük merge lépést.

83
00:04:03,610 --> 00:04:06,135
Befejeztük, bár
mi most egyfajta beágyazott down--

84
00:04:06,135 --> 00:04:08,420
és ez a fajta trükkös
dolog rekurzió,

85
00:04:08,420 --> 00:04:10,930
meg kell tartani a
fej, ​​hogy hol vagyunk.

86
00:04:10,930 --> 00:04:15,560
Így már egyfajta bal
a fele a narancssárga rész.

87
00:04:15,560 --> 00:04:21,280
>> És most, mi vagyunk a közepén válogatás
a jobb fele a narancssárga része.

88
00:04:21,280 --> 00:04:25,320
És ebben a folyamatban vagyunk
Most arról szól, hogy a lépés,

89
00:04:25,320 --> 00:04:27,850
egyesíti a két fél együtt.

90
00:04:27,850 --> 00:04:31,700
Ha megnézzük a két felét
a tömb, azt látjuk, kettő és egy.

91
00:04:31,700 --> 00:04:33,880
Melyik elem kisebb?

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

93
00:04:35,160 --> 00:04:36,760
>> Akkor melyik eleme kisebb?

94
00:04:36,760 --> 00:04:38,300
Nos, ez a két, vagy semmit.

95
00:04:38,300 --> 00:04:39,910
Tehát ez a két.

96
00:04:39,910 --> 00:04:43,690
Tehát most, csak azért, hogy újra a keret
hogy hol tartunk a kontextusban,

97
00:04:43,690 --> 00:04:48,230
már válogatni a
bal fele narancs

98
00:04:48,230 --> 00:04:49,886
és a jobb fele az origó.

99
00:04:49,886 --> 00:04:52,510
Tudom, hogy már megváltoztatta a színek
újra, de ez az, ahol voltunk.

100
00:04:52,510 --> 00:04:54,676
És azért tette ezt
azért van, mert ez a folyamat

101
00:04:54,676 --> 00:04:57,870
fog tartani fog, ismételve le.

102
00:04:57,870 --> 00:05:00,500
Már válogatni a bal
fele a korábbi narancs

103
00:05:00,500 --> 00:05:02,590
és a jobb fele a korábbi narancs.

104
00:05:02,590 --> 00:05:05,620
>> Most kell egyesíteni azokat
két fél együtt is.

105
00:05:05,620 --> 00:05:07,730
Ez a lépés már itt tartunk.

106
00:05:07,730 --> 00:05:11,440
Tehát úgy véljük, minden a
elemek, amelyek most zöld,

107
00:05:11,440 --> 00:05:12,972
A bal fele az eredeti tömb.

108
00:05:12,972 --> 00:05:14,680
És mi egyesítése azoknak
ugyanazt az eljárást használják

109
00:05:14,680 --> 00:05:18,660
tettük egyesülő két
és egy csak egy pillanattal ezelőtt.

110
00:05:18,660 --> 00:05:23,080
>> A bal felében a legkisebb
elemet a bal fele öt.

111
00:05:23,080 --> 00:05:25,620
A legkisebb elem
a jobb oldalán egy.

112
00:05:25,620 --> 00:05:27,370
Azok közül melyik kisebb?

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

114
00:05:29,260 --> 00:05:32,250
>> A legkisebb elem
A bal fele öt.

115
00:05:32,250 --> 00:05:35,540
A legkisebb elem
a jobb oldalán van kettő.

116
00:05:35,540 --> 00:05:36,970
Mi a legkisebb?

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

118
00:05:38,160 --> 00:05:41,540
És akkor végül öt és
semmit, azt mondhatjuk öt.

119
00:05:41,540 --> 00:05:43,935
>> OK, így nagy kép, hadd
egy kis szünetet a második

120
00:05:43,935 --> 00:05:46,080
és kitalálni, hogy hol vagyunk.

121
00:05:46,080 --> 00:05:48,580
Ha abból indultunk ki,
A kezdet kezdetén, mi

122
00:05:48,580 --> 00:05:51,640
Ezzel befejeződött a
a teljes tömb csak

123
00:05:51,640 --> 00:05:53,810
egy lépéssel a pszeudokódja kódot itt.

124
00:05:53,810 --> 00:05:56,645
Mi már válogatni a
bal fele a tömbben.

125
00:05:56,645 --> 00:05:59,490
>> Emlékezzünk vissza, hogy az eredeti
érdekében öt, kettő, egy.

126
00:05:59,490 --> 00:06:02,570
Csak végig kell mennie a folyamatban
fészkelő le, és ismétlődő,

127
00:06:02,570 --> 00:06:05,990
továbbra is megtörni a problémát
le kisebb és kisebb részekre,

128
00:06:05,990 --> 00:06:09,670
most már befejezett
fokozzák az egyik pszeudokódja

129
00:06:09,670 --> 00:06:13,940
az egész kiindulási tömb.

130
00:06:13,940 --> 00:06:16,670
Mi már válogatni a bal fele.

131
00:06:16,670 --> 00:06:18,670
>> Így most nézzük fagyasztható van.

132
00:06:18,670 --> 00:06:23,087
És most nézzük rendezni a jobb
a fele az eredeti tömb.

133
00:06:23,087 --> 00:06:25,670
És fogunk csinálni, hogy a
megy keresztül ugyanazon iteratív

134
00:06:25,670 --> 00:06:30,630
folyamata törés dolgokat
majd összevonással együtt.

135
00:06:30,630 --> 00:06:34,290
>> Így a bal fele
piros, vagy a bal fele

136
00:06:34,290 --> 00:06:38,830
A jobb fele az eredeti
tömb, fogom mondani, három.

137
00:06:38,830 --> 00:06:40,312
Ismét én következetes itt.

138
00:06:40,312 --> 00:06:42,020
Ha van egy furcsa
számú elemet, hogy

139
00:06:42,020 --> 00:06:44,478
nem igazán számít, hogy
csinál a bal, egy kisebb

140
00:06:44,478 --> 00:06:45,620
vagy az igazit kisebb.

141
00:06:45,620 --> 00:06:49,230
>> A lényeg, hogy amikor
ilyen probléma merül lebonyolítása

142
00:06:49,230 --> 00:06:51,422
egy összevont, meg kell, hogy legyen következetes.

143
00:06:51,422 --> 00:06:53,505
Vagy mindig kell
hogy egy bal oldali kisebb

144
00:06:53,505 --> 00:06:55,421
vagy mindig kell, hogy
a jobb oldali kisebb.

145
00:06:55,421 --> 00:06:57,720
Itt, úgy döntöttem, hogy mindig
hogy a bal oldali kisebb

146
00:06:57,720 --> 00:07:04,380
amikor a tömb, vagy én
tömbbök, a páratlan méretű.

147
00:07:04,380 --> 00:07:07,420
>> Három önálló elemként,
És ez így van rendezve.

148
00:07:07,420 --> 00:07:10,860
Már tőkeáttételes ezt a feltételezést
az egész a mi egész folyamat eddig.

149
00:07:10,860 --> 00:07:15,020
Így most nézzük rendezni a jobb
felét a jobb fél,

150
00:07:15,020 --> 00:07:18,210
vagy a jobb fele a piros.

151
00:07:18,210 --> 00:07:20,390
>> Ismét meg kell osztani ezt le.

152
00:07:20,390 --> 00:07:21,910
Ez nem egy elemet tömb.

153
00:07:21,910 --> 00:07:23,970
Nem jelenthetjük ki, hogy válogatni.

154
00:07:23,970 --> 00:07:27,060
És így az első, megyünk
rendezni a bal felét.

155
00:07:27,060 --> 00:07:31,620
>> A bal fele egyetlen elem,
így ez a fajta alapból.

156
00:07:31,620 --> 00:07:34,840
Aztán megyünk rendezni a jobb
fele, amely egyetlen elem.

157
00:07:34,840 --> 00:07:41,250
Ez sorolva alapértelmezett. És most,
tudjuk egyesíteni a két együttes.

158
00:07:41,250 --> 00:07:45,820
Négy kisebb, és
majd hat kisebb.

159
00:07:45,820 --> 00:07:48,870
>> Ismét mit tettünk ezen a ponton?

160
00:07:48,870 --> 00:07:52,512
Már válogatni a bal
a fele a jobb felét.

161
00:07:52,512 --> 00:07:54,720
Vagy megy vissza az eredeti
színek, hogy ott voltak,

162
00:07:54,720 --> 00:07:57,875
mi már válogatni a bal
a fele a lágyabb vörös.

163
00:07:57,875 --> 00:08:00,416
Ez eredetileg egy sötét tégla
piros és most ez egy lágyabb piros,

164
00:08:00,416 --> 00:08:02,350
vagy ez egy lágyabb vörös.

165
00:08:02,350 --> 00:08:05,145
>> És akkor mi már válogatni a
jobb felét a lágyabb piros.

166
00:08:05,145 --> 00:08:08,270
Most, nos, ők zöld újra, csak
mert mi folyamaton megy keresztül.

167
00:08:08,270 --> 00:08:10,720
És meg kell ismételni
ezt újra és újra.

168
00:08:10,720 --> 00:08:14,695
>> Így most már összevonjátok
két fél együtt.

169
00:08:14,695 --> 00:08:15,820
És ez az, amit mi itt.

170
00:08:15,820 --> 00:08:17,653
Így a fekete vonal csak
osztva a bal fele

171
00:08:17,653 --> 00:08:19,690
és a jobb fele ilyen része.

172
00:08:19,690 --> 00:08:24,310
>> Összehasonlítjuk a legkisebb érték
a bal oldalon a array--

173
00:08:24,310 --> 00:08:26,710
vagy bocsánat, a legkisebb
értéke a bal felét

174
00:08:26,710 --> 00:08:30,790
a legkisebb érték a jobb
fele és kiderül, hogy a három kisebb.

175
00:08:30,790 --> 00:08:32,530
És most egy kicsit az optimalizálás, ugye?

176
00:08:32,530 --> 00:08:35,175
Itt tulajdonképpen semmi
elhagyta a bal oldalon.

177
00:08:35,175 --> 00:08:37,440
>> Nincs semmi fennmaradó
a bal oldalon,

178
00:08:37,440 --> 00:08:40,877
így tudjuk hatékonyan
Csak move-- kijelenthetjük

179
00:08:40,877 --> 00:08:42,960
a többi része valójában
válogatni és csak csapáson meg

180
00:08:42,960 --> 00:08:45,126
tovább, mert nincs semmi
mást összehasonlítani.

181
00:08:45,126 --> 00:08:49,140
És tudjuk, hogy a jobb oldali
A jobb oldalon van rendezve.

182
00:08:49,140 --> 00:08:52,770
>> OK, így most nézzük újra lefagyasztani, és
kitalálni, hogy hol vagyunk a történetben.

183
00:08:52,770 --> 00:08:56,120
A teljes tömb,
mit értünk el?

184
00:08:56,120 --> 00:08:58,790
Mi már valóban véghez
Most lépéseket egy és két lépésben.

185
00:08:58,790 --> 00:09:03,300
Mi válogatni a bal fele, és
mi válogatni a jobb fele.

186
00:09:03,300 --> 00:09:08,210
>> Tehát most, minden marad a számunkra
egyesíteni a két fél együtt.

187
00:09:08,210 --> 00:09:11,670
Így összevetjük a legalacsonyabb értékű
eleme mindkét felét a tömb

188
00:09:11,670 --> 00:09:13,510
után, és folytassa.

189
00:09:13,510 --> 00:09:16,535
Egy kisebb, mint három, úgy sem megy.

190
00:09:16,535 --> 00:09:19,770
>> Két kisebb, mint három, így a két megy.

191
00:09:19,770 --> 00:09:22,740
Három kisebb, mint 5, ezért három megy.

192
00:09:22,740 --> 00:09:25,820
Négy kisebb, mint 5, így négy megy.

193
00:09:25,820 --> 00:09:30,210
Ezután öt kevesebb mint hat,
és hat minden marad.

194
00:09:30,210 --> 00:09:31,820
>> Most, tudom, hogy volt egy csomó lépést.

195
00:09:31,820 --> 00:09:33,636
És mi maradt egy csomó
A memória a mi nyomán.

196
00:09:33,636 --> 00:09:35,260
És ez az, amit ezek a szürke négyzet.

197
00:09:35,260 --> 00:09:40,540
És valószínűleg úgy érezte, mintha, hogy vett egy
sokkal hosszabb, mint beillesztés sort, buborék

198
00:09:40,540 --> 00:09:42,660
rendezés, illetve kiválasztási sorrend.

199
00:09:42,660 --> 00:09:45,330
>> De valójában, mert a
sok ilyen folyamatok

200
00:09:45,330 --> 00:09:48,260
történnek ugyanabban az time--
ami valami fogunk megint

201
00:09:48,260 --> 00:09:51,100
beszélnek, amikor arról beszélünk,
rekurzió egy későbbi video--

202
00:09:51,100 --> 00:09:53,799
ez az algoritmus valójában
egyértelműen alapvetően

203
00:09:53,799 --> 00:09:55,590
más, mint bármi
láttuk

204
00:09:55,590 --> 00:09:58,820
de az is jelentősen
hatékonyabb.

205
00:09:58,820 --> 00:09:59,532
>> Miert van az?

206
00:09:59,532 --> 00:10:01,240
Nos, a legrosszabb
forgatókönyv, van

207
00:10:01,240 --> 00:10:04,830
megosztani n elemek akár
majd újra össze.

208
00:10:04,830 --> 00:10:06,680
De amikor rekombinálódnak
őket, mit csinálunk

209
00:10:06,680 --> 00:10:11,110
alapvetően megduplázva a
méret a kisebb tömbök.

210
00:10:11,110 --> 00:10:14,260
Van egy csomó egyik eleme
tömbök, hogy hatékonyan

211
00:10:14,260 --> 00:10:16,290
egyesíteni a két elem tömbök.

212
00:10:16,290 --> 00:10:18,590
És akkor, hogy ezeket a
Két elem tömbök

213
00:10:18,590 --> 00:10:21,890
és rendezhetjük azokat
négy elem tömbök, és így tovább,

214
00:10:21,890 --> 00:10:26,130
és így tovább, és így tovább, amíg mi
egy N elem tömb.

215
00:10:26,130 --> 00:10:29,910
>> De hány megduplázódásának
tart eljutni n?

216
00:10:29,910 --> 00:10:31,460
Gondolj vissza a telefonkönyv példa.

217
00:10:31,460 --> 00:10:34,490
Hányszor kell még, hogy szakadjon
A telefonkönyv félbe, még hány

218
00:10:34,490 --> 00:10:38,370
alkalommal kell még, hogy szakadjon a telefonkönyv
félbe, ha a méret a telefonkönyv

219
00:10:38,370 --> 00:10:39,680
megduplázódott?

220
00:10:39,680 --> 00:10:41,960
Már csak egy, igaz?

221
00:10:41,960 --> 00:10:45,360
>> Szóval van valami
logaritmikus eleme van.

222
00:10:45,360 --> 00:10:48,590
De azt is mindig van legalább
megnézi az összes N elemekkel.

223
00:10:48,590 --> 00:10:53,860
Tehát a legrosszabb forgatókönyv esetén,
merge sort fut n log n.

224
00:10:53,860 --> 00:10:56,160
Meg kell nézni
az összes N elemek,

225
00:10:56,160 --> 00:11:02,915
és van, hogy összekapcsolják őket
együtt log n készlet lépéseket.

226
00:11:02,915 --> 00:11:05,290
A legjobb forgatókönyv esetén,
A tömb tökéletesen rendezve.

227
00:11:05,290 --> 00:11:06,300
Az remek.

228
00:11:06,300 --> 00:11:09,980
De az algoritmus alapján mi van itt,
még mindig meg kell osztani, és újraegyesítése.

229
00:11:09,980 --> 00:11:13,290
Bár ebben az esetben a
rekombinálódó a fajta hatástalan.

230
00:11:13,290 --> 00:11:14,720
Ez nem szükséges.

231
00:11:14,720 --> 00:11:17,580
De még mindig megy keresztül
Az egész folyamat egyébként.

232
00:11:17,580 --> 00:11:21,290
>> Tehát a legjobb esetben
és a legrosszabb esetben,

233
00:11:21,290 --> 00:11:24,970
Az algoritmus fut n log n idő.

234
00:11:24,970 --> 00:11:29,130
Merge sort mindenképpen egy kicsit trükkösebb
mint a másik fő rendező algoritmus

235
00:11:29,130 --> 00:11:33,470
beszéltünk CS50 de
lényegesen erősebb.

236
00:11:33,470 --> 00:11:35,400
>> És így ha valaha is megtalálják
alkalma van rá

237
00:11:35,400 --> 00:11:38,480
illetve felhasználják rendezni a
nagy adathalmaz, egyre

238
00:11:38,480 --> 00:11:41,940
fejed köré a gondolat, rekurzió
lesz igazán erős.

239
00:11:41,940 --> 00:11:45,270
És ez megy, hogy a
programok valóban sokkal hatékonyabb

240
00:11:45,270 --> 00:11:48,700
az egyesítés rendezési szemben bármi más.

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

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

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