1
00:00:00,000 --> 00:00:04,419
>> [TÓNLIST spila]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, svo sameinast
tegund er enn annar reiknirit

4
00:00:08,460 --> 00:00:11,200
að við getum notað til að raða út
þætti array.

5
00:00:11,200 --> 00:00:14,480
En eins og við munum sjá, það er got a
mjög grundvallarmunur

6
00:00:14,480 --> 00:00:17,850
frá Val tagi, kúla
raða, og innsetning tegund

7
00:00:17,850 --> 00:00:20,280
að gera það í raun nokkuð snjall.

8
00:00:20,280 --> 00:00:24,290
>> Grunnhugmyndin á bak við sameinast
tegund er að raða minni fylki

9
00:00:24,290 --> 00:00:27,430
og síðan sameina þá fylki
saman, eða sameina them--

10
00:00:27,430 --> 00:00:31,440
þess vegna name-- í raðaða röð.

11
00:00:31,440 --> 00:00:34,230
Leiðin að Mergesort er
þetta er með því að fá meira tól

12
00:00:34,230 --> 00:00:37,290
heitir endurkvæmni, sem er hvað
við erum að fara að tala um fljótlega,

13
00:00:37,290 --> 00:00:39,720
en við höfum í raun ekki talað um enn.

14
00:00:39,720 --> 00:00:43,010
>> Hér er Grunnhugmyndin á bak mergesort.

15
00:00:43,010 --> 00:00:46,320
Raða vinstri helming fylkisins,
að því gefnu n er meiri en 1.

16
00:00:46,320 --> 00:00:49,980
Og hvað ég meina þegar ég segi
að því gefnu n er meiri en 1 er,

17
00:00:49,980 --> 00:00:53,970
Ég held að við getum verið sammála um að ef array
aðeins samanstendur af einni þáttur,

18
00:00:53,970 --> 00:00:54,680
það er flokkað.

19
00:00:54,680 --> 00:00:56,560
Við gerum ekki raunverulega þörf
að gera neitt við það.

20
00:00:56,560 --> 00:00:58,059
Við getum bara lýsa það að vera flokkaður.

21
00:00:58,059 --> 00:01:00,110
Það er aðeins einn þáttur.

22
00:01:00,110 --> 00:01:03,610
>> Svo sauðakóðanum, aftur, er
raða vinstri hluta fylkisins,

23
00:01:03,610 --> 00:01:08,590
þá raða rétt helmingur array,
þá sameinast tvo helminga saman.

24
00:01:08,590 --> 00:01:11,040
Nú, þegar þú gætir verið
hugsa, það konar bara

25
00:01:11,040 --> 00:01:14,080
hljómar eins og þú ert að setja á the--
þú ert í raun ekki að gera neitt.

26
00:01:14,080 --> 00:01:16,330
Þú ert að segja raða vinstri
helmingur, raða rétt helminginn,

27
00:01:16,330 --> 00:01:19,335
en þú ert ekki að segja
mér hvernig þú ert að gera það.

28
00:01:19,335 --> 00:01:22,220
>> En muna að svo lengi sem
fylki er einn þáttur,

29
00:01:22,220 --> 00:01:23,705
við getum lýst það flokkað.

30
00:01:23,705 --> 00:01:25,330
Þá getum við bara sameina þær.

31
00:01:25,330 --> 00:01:27,788
Og það er í raun
grunnhugsun að baki sameiningu tagi,

32
00:01:27,788 --> 00:01:31,150
er að brjóta það niður þannig að
fylki eru af stærð einni.

33
00:01:31,150 --> 00:01:33,430
Og þá þú endurbyggja þaðan.

34
00:01:33,430 --> 00:01:35,910
>> Mergesort er ákveðið
flókið reiknirit.

35
00:01:35,910 --> 00:01:38,210
Og það er líka svolítið
flókið að sjón.

36
00:01:38,210 --> 00:01:41,870
Svo vonandi er visualization sem ég
hafa hér mun hjálpa þér að fylgja með.

37
00:01:41,870 --> 00:01:45,640
Og ég ætla að reyna mitt besta til að sagt hlutina
og halda áfram í gegnum þetta aðeins meira

38
00:01:45,640 --> 00:01:49,180
hægar en hinar
bara að vonandi fá höfuð þitt

39
00:01:49,180 --> 00:01:51,800
um hugmyndum að baki sameiningu tagi.

40
00:01:51,800 --> 00:01:54,680
>> Þannig að við höfum sama array sem er
Önnur flokkun reiknirit myndbönd

41
00:01:54,680 --> 00:01:57,120
ef þú hefur séð them--
sex þáttur array.

42
00:01:57,120 --> 00:02:02,110
Og sauðakóðanum númerið okkar hér er tegund
vinstri helminginn, raða rétt helminginn,

43
00:02:02,110 --> 00:02:03,890
sameina tvo helminga saman.

44
00:02:03,890 --> 00:02:09,770
Svo skulum við taka þetta mjög dökk múrsteinn rauður
array og raða vinstri helmingur af því.

45
00:02:09,770 --> 00:02:13,380
>> Svo um sinn, við erum að fara
að hunsa efni á hægri.

46
00:02:13,380 --> 00:02:15,740
Það er þarna, en við erum
ekki á þeim skref enn.

47
00:02:15,740 --> 00:02:18,220
Við erum ekki á að raða
hægri helminginn af fylkisins.

48
00:02:18,220 --> 00:02:21,037
Við erum á einhverskonar vinstri
helmingur fylkisins.

49
00:02:21,037 --> 00:02:22,870
Og bara fyrir sakir
af því að vera a lítill fleiri

50
00:02:22,870 --> 00:02:26,480
ljóst, svo ég geti átt
hvað skref sem við erum á,

51
00:02:26,480 --> 00:02:29,800
Ég ætla að kveikja á
litur þetta sett til appelsínugult.

52
00:02:29,800 --> 00:02:33,190
Nú erum við enn að tala um
Sama vinstri helminginn af upprunalegu array.

53
00:02:33,190 --> 00:02:38,520
En ég vona að með því að vera fær um að
vísa til litum ýmsu atriði,

54
00:02:38,520 --> 00:02:40,900
það mun gera það svolítið meira
ljóst hvað er að gerast hér.

55
00:02:40,900 --> 00:02:43,270
>> OK, svo nú höfum við
þrír þáttur array.

56
00:02:43,270 --> 00:02:46,420
Hvernig eigum við að raða vinstri hluta þessa
array, sem er enn þetta skref?

57
00:02:46,420 --> 00:02:49,400
Við erum að reyna að raða vinstri
helmingur múrsteinn rauður array--

58
00:02:49,400 --> 00:02:52,410
vinstri helminginn af sem
Ég hef nú litað appelsínugult.

59
00:02:52,410 --> 00:02:54,840
>> Jæja, við reynum og
endurtaka þetta ferli aftur.

60
00:02:54,840 --> 00:02:56,756
Þannig að við erum enn í
miðja þess að reyna að raða

61
00:02:56,756 --> 00:02:58,700
vinstri helminginn af fullum fylkisins.

62
00:02:58,700 --> 00:03:00,450
Vinstri helmingur
array, ég ætla bara að fara

63
00:03:00,450 --> 00:03:03,910
að geðþótta ákveðið að vinstri helmingur
verði minni en hægri hluta,

64
00:03:03,910 --> 00:03:06,550
vegna þess að þetta gerist
samanstanda af þremur þáttum.

65
00:03:06,550 --> 00:03:11,260
>> Og svo ég ætla að segja að
vinstri helminginn af vinstri hluta fylkisins

66
00:03:11,260 --> 00:03:14,050
er bara þáttur fimm.

67
00:03:14,050 --> 00:03:18,360
Fimm, að vera einn þáttur
array, við vitum hvernig á að flokka það.

68
00:03:18,360 --> 00:03:21,615
Og svo fimm er flokkaður.

69
00:03:21,615 --> 00:03:22,990
Við erum bara að fara að lýsa því yfir að.

70
00:03:22,990 --> 00:03:24,890
Það er einn þáttur array.

71
00:03:24,890 --> 00:03:29,015
>> Þannig að við höfum nú flokkuð sem
vinstri helminginn af vinstri half--

72
00:03:29,015 --> 00:03:33,190
eða öllu heldur, höfum við raðað í
vinstri helminginn af appelsína.

73
00:03:33,190 --> 00:03:37,970
Svo nú, í því skyni að enn lokið
vinstri helmingur heildar Array er,

74
00:03:37,970 --> 00:03:43,481
við þurfum að raða rétt helminginn
af appelsínu, eða þessu efni.

75
00:03:43,481 --> 00:03:44,230
Hvernig gerum við það?

76
00:03:44,230 --> 00:03:45,930
Jæja, höfum við tveggja þátturinn array.

77
00:03:45,930 --> 00:03:50,470
Svo við getum raða vinstri hluta
fylkisins, sem er tveir.

78
00:03:50,470 --> 00:03:52,090
Tvö er einn þáttur.

79
00:03:52,090 --> 00:03:55,890
Svo það er flokkað sjálfgefið.
Þá getum við raða rétt helminginn

80
00:03:55,890 --> 00:03:58,530
af þeim hluta fylkisins, einn.

81
00:03:58,530 --> 00:04:00,210
Það er tegund af sjálfgefið.

82
00:04:00,210 --> 00:04:03,610
>> Þetta er nú í fyrsta sinn
við höfum náð sameiningar- skref.

83
00:04:03,610 --> 00:04:06,135
Við höfum lokið, þótt
við erum nú eins konar hreiður down--

84
00:04:06,135 --> 00:04:08,420
og það er tegund af erfiður
Málið með endurkvæmni er,

85
00:04:08,420 --> 00:04:10,930
þú þarft að halda þínum
höfuð um hvar við erum.

86
00:04:10,930 --> 00:04:15,560
Þannig að við höfum konar vinstri
helmingur af appelsínugula hluta.

87
00:04:15,560 --> 00:04:21,280
>> Og nú erum við í miðju flokka
hægri helminginn af appelsínugula hluta.

88
00:04:21,280 --> 00:04:25,320
Og í því ferli, við erum
nú um að vera á þrepi,

89
00:04:25,320 --> 00:04:27,850
sameina tvo helminga saman.

90
00:04:27,850 --> 00:04:31,700
Þegar við skoðum helminga
fylkisins, sjáum við tvo og einn.

91
00:04:31,700 --> 00:04:33,880
Hvaða þáttur er minni?

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

93
00:04:35,160 --> 00:04:36,760
>> Þá er hver þáttur minni?

94
00:04:36,760 --> 00:04:38,300
Jæja, það er tveir eða ekkert.

95
00:04:38,300 --> 00:04:39,910
Svo er það tveir.

96
00:04:39,910 --> 00:04:43,690
Svo nú, bara til aftur ramma
þar sem við erum í samhengi,

97
00:04:43,690 --> 00:04:48,230
við höfum raðað í
vinstri helminginn af Orange

98
00:04:48,230 --> 00:04:49,886
og hægri helminginn af uppruna.

99
00:04:49,886 --> 00:04:52,510
Ég veit að ég hef breytt litum
aftur, en það er þar sem við vorum.

100
00:04:52,510 --> 00:04:54,676
Og ástæða þess að ég gerði þetta
er vegna þess að þetta ferli er

101
00:04:54,676 --> 00:04:57,870
fara að halda áfram, iterating niður.

102
00:04:57,870 --> 00:05:00,500
Við höfum flokkað vinstri
helmingur af fyrrum appelsínugult

103
00:05:00,500 --> 00:05:02,590
og hægri helminginn af fyrrum appelsína.

104
00:05:02,590 --> 00:05:05,620
>> Nú þurfum við að sameinast þeim
tvennt saman líka.

105
00:05:05,620 --> 00:05:07,730
Það er skref sem við erum á.

106
00:05:07,730 --> 00:05:11,440
Þannig að við teljum allt í
þættir sem eru nú grænt,

107
00:05:11,440 --> 00:05:12,972
vinstri helminginn af upprunalegu array.

108
00:05:12,972 --> 00:05:14,680
Og við sameinast þeim
með því að nota sömu aðferð

109
00:05:14,680 --> 00:05:18,660
við gerðum til að sameina tvær
og einn bara í smá stund síðan.

110
00:05:18,660 --> 00:05:23,080
>> Vinstri helmingur, minnstu
þáttur á vinstri helming er fimm.

111
00:05:23,080 --> 00:05:25,620
Minnsta þáttur á
hægri helminginn er einn.

112
00:05:25,620 --> 00:05:27,370
Hver af þeim er minni?

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

114
00:05:29,260 --> 00:05:32,250
>> Minnsta þáttur á
vinstri helmingurinn er fimm.

115
00:05:32,250 --> 00:05:35,540
Minnsta þáttur á
hægri helminginn er tveggja.

116
00:05:35,540 --> 00:05:36,970
Hvað er minnsti?

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

118
00:05:38,160 --> 00:05:41,540
Og þá loks fimm og
ekkert, getum við sagt fimm.

119
00:05:41,540 --> 00:05:43,935
>> OK, svo stór mynd, við skulum
taka hlé í smástund

120
00:05:43,935 --> 00:05:46,080
og reikna út hvar við erum.

121
00:05:46,080 --> 00:05:48,580
Ef við byrjuðum frá
upphafi, við

122
00:05:48,580 --> 00:05:51,640
hefur nú lokið fyrir
heildar array bara

123
00:05:51,640 --> 00:05:53,810
eitt skref í sauðakóðanum kóða hér.

124
00:05:53,810 --> 00:05:56,645
Við höfum raðað í
vinstri hluta fylkisins.

125
00:05:56,645 --> 00:05:59,490
>> Muna að upprunalega
röð var fimm, tveir, einn.

126
00:05:59,490 --> 00:06:02,570
Með því að fara í gegnum þetta ferli
og verpa niður og endurtaka,

127
00:06:02,570 --> 00:06:05,990
að halda áfram að brjóta vandamál
niður í smærri og smærri hluta,

128
00:06:05,990 --> 00:06:09,670
við höfum nú lokið
stíga einn af sauðakóðanum

129
00:06:09,670 --> 00:06:13,940
fyrir allt byrjun fylkisins.

130
00:06:13,940 --> 00:06:16,670
Við höfum flokkað vinstri helming þess.

131
00:06:16,670 --> 00:06:18,670
>> Svo nú skulum frysta það.

132
00:06:18,670 --> 00:06:23,087
Og nú skulum raða rétt
helmingur af upprunalegu array.

133
00:06:23,087 --> 00:06:25,670
Og við erum að fara að gera það
fara í gegnum það sama endurtekningu

134
00:06:25,670 --> 00:06:30,630
Ferlið að brjóta það niður
og síðan sameina þá saman.

135
00:06:30,630 --> 00:06:34,290
>> Þannig að vinstri hluta
rauður eða vinstri helming

136
00:06:34,290 --> 00:06:38,830
á hægri hluta af upprunalegu
array, ég ætla að segja er þrír.

137
00:06:38,830 --> 00:06:40,312
Aftur, ég er að vera í samræmi hér.

138
00:06:40,312 --> 00:06:42,020
Ef þú ert stakur
fjöldi staka, það

139
00:06:42,020 --> 00:06:44,478
skiptir ekki máli hvort
þú gerir vinstri ein minni

140
00:06:44,478 --> 00:06:45,620
eða rétt ein minni.

141
00:06:45,620 --> 00:06:49,230
>> Það sem skiptir máli er að þegar þér
fundur this vandamál í framkvæmd

142
00:06:49,230 --> 00:06:51,422
a sameinast, þú þarft að vera í samræmi.

143
00:06:51,422 --> 00:06:53,505
Þú annað hvort alltaf þurfa að
gera vinstri hlið minni

144
00:06:53,505 --> 00:06:55,421
eða alltaf þurfa að gera
hægra megin minni.

145
00:06:55,421 --> 00:06:57,720
Hér hef ég valið að alltaf
gera vinstri hlið minni

146
00:06:57,720 --> 00:07:04,380
þegar array minn eða minn
undir-array, er stakur stærð.

147
00:07:04,380 --> 00:07:07,420
>> Þrjú er einn þáttur,
og svo það er flokkað.

148
00:07:07,420 --> 00:07:10,860
Við höfum skuldsett það forsendu
í gegnum allt ferli okkar svo langt.

149
00:07:10,860 --> 00:07:15,020
Svo nú skulum raða rétt
helmingur hægri hluta,

150
00:07:15,020 --> 00:07:18,210
eða hægri helminginn af rauðu.

151
00:07:18,210 --> 00:07:20,390
>> Aftur, við þurfum að skipta þessu niður.

152
00:07:20,390 --> 00:07:21,910
Þetta er ekki einn þáttur array.

153
00:07:21,910 --> 00:07:23,970
Við getum ekki sagt það flokkað.

154
00:07:23,970 --> 00:07:27,060
Og svo fyrst, við erum að fara
að raða vinstri helming.

155
00:07:27,060 --> 00:07:31,620
>> Vinstri helmingurinn er einn þáttur,
svo það er tegund af sjálfgefið.

156
00:07:31,620 --> 00:07:34,840
Þá erum við að fara að raða rétt
helming, sem er einn þáttur.

157
00:07:34,840 --> 00:07:41,250
Það er raðað sjálfkrafa. Og nú,
við getum sameinast þessir tveir saman.

158
00:07:41,250 --> 00:07:45,820
Fjögur er minni, og
þá er sex minni.

159
00:07:45,820 --> 00:07:48,870
>> Aftur, hvað höfum við gert á þessum tímapunkti?

160
00:07:48,870 --> 00:07:52,512
Við höfum flokkað vinstri
helmingur hægri hluta.

161
00:07:52,512 --> 00:07:54,720
Eða fara aftur til upprunalega
litir, sem þar bjuggu,

162
00:07:54,720 --> 00:07:57,875
við höfum raðað vinstri
helmingur mýkri rauðu.

163
00:07:57,875 --> 00:08:00,416
Það var upphaflega dökk múrsteinn
rauður og nú er það mýkri rautt,

164
00:08:00,416 --> 00:08:02,350
eða það var mýkri rautt.

165
00:08:02,350 --> 00:08:05,145
>> Og þá höfum við raðað í
hægri helminginn af mýkri rauðu.

166
00:08:05,145 --> 00:08:08,270
Nú, jæja, þá eru þeir aftur græn, bara
vegna þess að við erum að fara í gegnum ferli.

167
00:08:08,270 --> 00:08:10,720
Og við verðum að endurtaka
þetta aftur og aftur.

168
00:08:10,720 --> 00:08:14,695
>> Svo nú getum við sameinast þeim
tvennt saman.

169
00:08:14,695 --> 00:08:15,820
Og það er það sem við gerum hér.

170
00:08:15,820 --> 00:08:17,653
Svo svarta línu bara
skipt vinstri helming

171
00:08:17,653 --> 00:08:19,690
og hægri helminginn af þessu tagi hluta.

172
00:08:19,690 --> 00:08:24,310
>> Við berum saman lægsta gildi
á vinstri hlið af the array--

173
00:08:24,310 --> 00:08:26,710
eða afsaka mig, minnstu
gildi vinstri hluta

174
00:08:26,710 --> 00:08:30,790
í minnstu gildi hægri
helmingur og kemst að því að þrjú er minni.

175
00:08:30,790 --> 00:08:32,530
Og nú dálítið af hagræðingu, ekki satt?

176
00:08:32,530 --> 00:08:35,175
Það er í raun ekkert
vinstri á vinstri hlið.

177
00:08:35,175 --> 00:08:37,440
>> Það er ekkert eftir
á vinstri hlið,

178
00:08:37,440 --> 00:08:40,877
svo við getum duglegur
bara move-- við getum lýst

179
00:08:40,877 --> 00:08:42,960
restin af því er í raun
flokkaður og bara tittur það

180
00:08:42,960 --> 00:08:45,126
á, vegna þess að það er ekkert
annað að bera saman gegn.

181
00:08:45,126 --> 00:08:49,140
Og við vitum að hægri hlið
af hægri hlið er flokkaður.

182
00:08:49,140 --> 00:08:52,770
>> OK, svo nú skulum frysta aftur og
reikna út þar sem við erum í sögunni.

183
00:08:52,770 --> 00:08:56,120
Í heild array,
Hvað höfum við náð?

184
00:08:56,120 --> 00:08:58,790
Við höfum í raun náð
nú skref eitt og stíga tvö.

185
00:08:58,790 --> 00:09:03,300
Við raðað vinstri helming, og
Við raðað rétt helminginn.

186
00:09:03,300 --> 00:09:08,210
>> Svo nú, allt sem helst er fyrir okkur
að sameina þessa tvo helminga saman.

187
00:09:08,210 --> 00:09:11,670
Svo við saman lægstu metin
þáttur hvers hluta fylkisins

188
00:09:11,670 --> 00:09:13,510
aftur og halda áfram.

189
00:09:13,510 --> 00:09:16,535
Eitt er minna en þrír, svo maður fer.

190
00:09:16,535 --> 00:09:19,770
>> Tvö er minna en þrír, svo tveir fer.

191
00:09:19,770 --> 00:09:22,740
Þrjú er minna en 5, þannig þrír fer.

192
00:09:22,740 --> 00:09:25,820
Fjögur er minna en 5, þannig fjórir fer.

193
00:09:25,820 --> 00:09:30,210
Þá er fimm minna en sex,
og sex er allt sem er eftir.

194
00:09:30,210 --> 00:09:31,820
>> Nú veit ég, það var mikið af skrefum.

195
00:09:31,820 --> 00:09:33,636
Og við höfum vinstri mikið
minni í kjölfar okkar.

196
00:09:33,636 --> 00:09:35,260
Og það er það sem þeir gráum reitum eru.

197
00:09:35,260 --> 00:09:40,540
Og það var sennilega svona tók
mikið lengur en Innsetningarröðun, kúla

198
00:09:40,540 --> 00:09:42,660
tegund, eða val konar.

199
00:09:42,660 --> 00:09:45,330
>> En í raun, vegna þess að
mikið af þessum ferlum

200
00:09:45,330 --> 00:09:48,260
eru að gerast á sama time--
sem er eitthvað sem við munum aftur,

201
00:09:48,260 --> 00:09:51,100
tala um þegar við tölum um
endurkvæmni í framtíðinni video--

202
00:09:51,100 --> 00:09:53,799
Þetta reiknirit raun
greinilega er í grundvallaratriðum

203
00:09:53,799 --> 00:09:55,590
öðruvísi en nokkuð
við höfum séð áður

204
00:09:55,590 --> 00:09:58,820
en er einnig verulega
skilvirkari.

205
00:09:58,820 --> 00:09:59,532
>> Afhverju er það?

206
00:09:59,532 --> 00:10:01,240
Jæja, í versta
falli, höfum við

207
00:10:01,240 --> 00:10:04,830
að skipta n þætti upp
og þá sameinum þær.

208
00:10:04,830 --> 00:10:06,680
En þegar við sameinum
þá, hvað við erum að gera

209
00:10:06,680 --> 00:10:11,110
er í grundvallaratriðum að tvöföldun á
Stærð minni fylki.

210
00:10:11,110 --> 00:10:14,260
Við höfum fullt af einn þáttur
fylki sem við í raun

211
00:10:14,260 --> 00:10:16,290
sameina í tvo staka fylki.

212
00:10:16,290 --> 00:10:18,590
Og þá erum við að taka þær
tvær þáttur fylki

213
00:10:18,590 --> 00:10:21,890
og sameina þær í
fjögur frumefni fylki, og svo framvegis,

214
00:10:21,890 --> 00:10:26,130
og svo framvegis, og svo framvegis, þar til við
hafa einn n þátturinn array.

215
00:10:26,130 --> 00:10:29,910
>> En hversu margir helmingsstækkanir
tekur það að fá að n?

216
00:10:29,910 --> 00:10:31,460
Hugsaðu til baka í símaskrá dæmi.

217
00:10:31,460 --> 00:10:34,490
Hversu oft við þurfum að rífa
símaskrá í tvennt, hversu margir fleiri

218
00:10:34,490 --> 00:10:38,370
sinnum eigum við að rífa símaskrá
í tvennt, ef stærð símaskránni

219
00:10:38,370 --> 00:10:39,680
tvöfaldast?

220
00:10:39,680 --> 00:10:41,960
Það er bara eitt, ekki satt?

221
00:10:41,960 --> 00:10:45,360
>> Þannig að það er einhvers konar
lógaritmískum þáttur hér.

222
00:10:45,360 --> 00:10:48,590
En við einnig enn að minnsta kosti
líta á alla þá N þætti.

223
00:10:48,590 --> 00:10:53,860
Svo í versta falli,
Mergesort keyrir n log n.

224
00:10:53,860 --> 00:10:56,160
Við verðum að líta á
öllu af N þáttum,

225
00:10:56,160 --> 00:11:02,915
og við verðum að sameina þá
saman log n sett af skrefum.

226
00:11:02,915 --> 00:11:05,290
Í besta falli,
array er fullkomlega raðað.

227
00:11:05,290 --> 00:11:06,300
Það er frábært.

228
00:11:06,300 --> 00:11:09,980
En miðað við reiknirit sem við höfum hér,
við höfum enn að skipta og sameinum.

229
00:11:09,980 --> 00:11:13,290
Þó að í þessu tilfelli,
recombining er góður af árangurslaus.

230
00:11:13,290 --> 00:11:14,720
Það er ekki þörf.

231
00:11:14,720 --> 00:11:17,580
En við förum samt í gegnum
allt ferlið engu að síður.

232
00:11:17,580 --> 00:11:21,290
>> Svo í besta tilfelli
og í versta tilfelli,

233
00:11:21,290 --> 00:11:24,970
Þetta reiknirit keyrir n log n tíma.

234
00:11:24,970 --> 00:11:29,130
Mergesort er ákveðið dálítið trickier
en aðrar helstu flokkun reiknirit

235
00:11:29,130 --> 00:11:33,470
við höfum talað um CS50 en er
verulega öflugri.

236
00:11:33,470 --> 00:11:35,400
>> Og svo ef þú finnur alltaf
tilefni til að þurfa það

237
00:11:35,400 --> 00:11:38,480
eða til að nota það til að raða a
stór gögnum, fá

238
00:11:38,480 --> 00:11:41,940
höfuðið í kringum þá hugmynd endurkvæmni
er að fara að vera mjög öflugur.

239
00:11:41,940 --> 00:11:45,270
Og það er að fara að gera þinn
forrit í raun mun skilvirkari

240
00:11:45,270 --> 00:11:48,700
nota Mergesort móti allt annað.

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

242
00:11:49,640 --> 00:11:51,970
Þetta er CS50.

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