1
00:00:00,000 --> 00:00:04,419
>> [MUZIKO Ludante]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: Bone, do a merge
varo estas ankoraŭ alia algoritmo

4
00:00:08,460 --> 00:00:11,200
ke ni povas uzi por ordigi
la elementoj de tabelo.

5
00:00:11,200 --> 00:00:14,480
Sed kiel ni vidos, ĝi estas alvenis al
tre fundamenta diferenco

6
00:00:14,480 --> 00:00:17,850
el selektado varon, bobelo
speco, kaj inserción varo

7
00:00:17,850 --> 00:00:20,280
kiuj faras ĝin vere tre lertaj.

8
00:00:20,280 --> 00:00:24,290
>> La baza ideo malantaŭ merge
varo estas ordigi malgrandaj tabeloj

9
00:00:24,290 --> 00:00:27,430
kaj tiam kombini tiujn tabeloj
kune, aŭ kunfandi them--

10
00:00:27,430 --> 00:00:31,440
tie la name-- en ordo ordo.

11
00:00:31,440 --> 00:00:34,230
La maniero ke kunfandi speco faras
ĉi estas por utiligante ilo

12
00:00:34,230 --> 00:00:37,290
nomata rekursio, kio estas kio
ni tuj parolos pri baldaŭ,

13
00:00:37,290 --> 00:00:39,720
sed ni ne vere parolis ankoraŭ.

14
00:00:39,720 --> 00:00:43,010
>> Jen la baza ideo malantaŭ merge varon.

15
00:00:43,010 --> 00:00:46,320
Ordigi la maldekstra duono de la tabelo,
supozante n pli granda ol 1.

16
00:00:46,320 --> 00:00:49,980
Kaj kion mi volas diri kiam mi diras
supozante n pli granda ol 1 estas,

17
00:00:49,980 --> 00:00:53,970
Mi kredas ke ni povas konsenti ke se tabelo
nur konsistas de sola elemento,

18
00:00:53,970 --> 00:00:54,680
ĝi estas ordo.

19
00:00:54,680 --> 00:00:56,560
Ni ne vere bezonas
fari ion al ŝi.

20
00:00:56,560 --> 00:00:58,059
Ni povas nur diveni esti ordo.

21
00:00:58,059 --> 00:01:00,110
Estas nur unu sola ero.

22
00:01:00,110 --> 00:01:03,610
>> Do la _pseudocode_, denove, estas
ordigi la maldekstra duono de la tabelo,

23
00:01:03,610 --> 00:01:08,590
tiam ordigi la dekstra duono de la tabelo,
tiam kunfandi la du duonojn kune.

24
00:01:08,590 --> 00:01:11,040
Nun, jam vi povus esti
pensante, ĝi speco de simple

25
00:01:11,040 --> 00:01:14,080
sonas vi demeto the--
vi fakte ne fari ion.

26
00:01:14,080 --> 00:01:16,330
Vi diras ordigi la maldekstra
duono, ordigi la dekstra duono,

27
00:01:16,330 --> 00:01:19,335
sed vi ne rakontanta
mi kiel vi faras ĝin.

28
00:01:19,335 --> 00:01:22,220
>> Sed memoru, ke dum
tabelo estas ununura ero,

29
00:01:22,220 --> 00:01:23,705
ni povas diveni ordo.

30
00:01:23,705 --> 00:01:25,330
Tiam ni povas nur kombini ilin kune.

31
00:01:25,330 --> 00:01:27,788
Kaj tio estas vere la
fundamenta ideo malantaŭ merge varo,

32
00:01:27,788 --> 00:01:31,150
estas rompi ĝin malsupren tiel ke
via arrays estas de amplekso unu.

33
00:01:31,150 --> 00:01:33,430
Kaj tiam vi rekonstruas de tie.

34
00:01:33,430 --> 00:01:35,910
>> Kunfandi varo estas definitive
komplika algoritmo.

35
00:01:35,910 --> 00:01:38,210
Kaj ĝi estas ankaŭ iom
komplika visualizar.

36
00:01:38,210 --> 00:01:41,870
Do espereble, la visualización ke mi
havas tie helpos vin sekvi kune.

37
00:01:41,870 --> 00:01:45,640
Kaj mi provos mian plejeblon por rakonti aferojn
kaj procedi tra tiu iom pli

38
00:01:45,640 --> 00:01:49,180
malrapide ol la alia ones
nur espereble ricevos vian kapon

39
00:01:49,180 --> 00:01:51,800
ĉirkaŭ la ideoj malantaŭ merge varon.

40
00:01:51,800 --> 00:01:54,680
>> Do ni havas la sama tabelo kiel la
aliaj ordiga algoritmo filmetoj

41
00:01:54,680 --> 00:01:57,120
se vi vidis them--
ses elemento tabelo.

42
00:01:57,120 --> 00:02:02,110
Kaj nia _pseudocode_ kodo tie estas ia
la maldekstra duono, ordigi la dekstra duono,

43
00:02:02,110 --> 00:02:03,890
kunfandi la du duonojn kune.

44
00:02:03,890 --> 00:02:09,770
Do ni prenu tiun tre malhela briko ruĝa
tabelo kaj ordigi la maldekstra duono.

45
00:02:09,770 --> 00:02:13,380
>> Do provizore, ni tuj
ignori la havajxoj dekstre.

46
00:02:13,380 --> 00:02:15,740
Ĝi estas tie, sed ni estas
ne en tiu paŝo ankoraŭ.

47
00:02:15,740 --> 00:02:18,220
Ni ne estas en la speco
dekstra duono de la tabelo.

48
00:02:18,220 --> 00:02:21,037
Ni estas ĉe ia maldekstre
duono de la tabelo.

49
00:02:21,037 --> 00:02:22,870
Kaj ĝuste pro
esti iom pli

50
00:02:22,870 --> 00:02:26,480
klara, do mi povas referi
al kio paŝo ni estas sur,

51
00:02:26,480 --> 00:02:29,800
Mi tuj ŝanĝos la
koloro de ĉi tiu aro al oranĝo.

52
00:02:29,800 --> 00:02:33,190
Nun, ni ankoraŭ parolas pri la
sama maldekstra duono de la originala tabelo.

53
00:02:33,190 --> 00:02:38,520
Sed mi esperas, ke por povi
rilati al la koloroj de diversaj artikoloj,

54
00:02:38,520 --> 00:02:40,900
gxi devos fari ĝin iom pli
malbari kion okazas tie.

55
00:02:40,900 --> 00:02:43,270
>> Bone, do nun ni havas
tri elemento tabelo.

56
00:02:43,270 --> 00:02:46,420
Kiel ni ordigi la maldekstra duono de tiu
tabelo, kiu estas ankoraŭ ĉi paŝon?

57
00:02:46,420 --> 00:02:49,400
Ni provas ordigi la maldekstra
duono de la briko ruĝa tabelo

58
00:02:49,400 --> 00:02:52,410
la maldekstra duono de kiu
Mi nun kolorita oranĝa.

59
00:02:52,410 --> 00:02:54,840
>> Nu, ni povus provi kaj
Ripeti ĉi procezo denove.

60
00:02:54,840 --> 00:02:56,756
Do ni estas ankoraŭ en la
mezo de provi ordigi

61
00:02:56,756 --> 00:02:58,700
la maldekstra duono de la plena tabelo.

62
00:02:58,700 --> 00:03:00,450
La maldekstra duono de la
tabelo, mi simple tuj

63
00:03:00,450 --> 00:03:03,910
arbitre decidi ke la maldekstra duono
estos pli malgranda ol la dekstra duono,

64
00:03:03,910 --> 00:03:06,550
ĉar ĉi tio okazas al
konsisti el tri elementoj.

65
00:03:06,550 --> 00:03:11,260
>> Kaj tiel mi tuj diru, ke la
maldekstra duono de la maldekstra duono de la tabelo

66
00:03:11,260 --> 00:03:14,050
Estas ĝuste la elemento kvin.

67
00:03:14,050 --> 00:03:18,360
Kvin, estante sola elemento
tabelo, ni scias kiel ordigi ĝin.

68
00:03:18,360 --> 00:03:21,615
Kaj do kvin estas ordo.

69
00:03:21,615 --> 00:03:22,990
Ni nur tuj deklari tion.

70
00:03:22,990 --> 00:03:24,890
Ĝi estas ununura elemento tabelo.

71
00:03:24,890 --> 00:03:29,015
>> Do ni nun ordo la
maldekstra duono de la maldekstra half--

72
00:03:29,015 --> 00:03:33,190
aŭ pli ĝuste, ni ordo la
maldekstra duono de la oranĝo.

73
00:03:33,190 --> 00:03:37,970
Do nun, por ankoraŭ kompleta
la totala tabelo la maldekstra duono,

74
00:03:37,970 --> 00:03:43,481
ni devas ordigi la dekstra duono
de la oranĝo, aŭ tiun materialon.

75
00:03:43,481 --> 00:03:44,230
Kiel ni faru tion?

76
00:03:44,230 --> 00:03:45,930
Nu, ni havas du elemento tabelo.

77
00:03:45,930 --> 00:03:50,470
Do ni povas ordigi la maldekstra duono
de la tabelo, kiu estas du.

78
00:03:50,470 --> 00:03:52,090
Du estas ununura elemento.

79
00:03:52,090 --> 00:03:55,890
Do ĝi estas ordo defaŭlte.
Tiam ni povas ordigi la dekstra duono

80
00:03:55,890 --> 00:03:58,530
de tiu parto de la tabelo, la unu.

81
00:03:58,530 --> 00:04:00,210
Tio estas speco de defaŭlte.

82
00:04:00,210 --> 00:04:03,610
>> Jen nun la unuan fojon
ni atingis merge paŝo.

83
00:04:03,610 --> 00:04:06,135
Ni kompletigis, kvankam
ni nun speco de nestitaj down--

84
00:04:06,135 --> 00:04:08,420
kaj tio estas ia la delikata
afero kun rekursio estas,

85
00:04:08,420 --> 00:04:10,930
vi bezonas konservi vian
kapo pri kie ni estas.

86
00:04:10,930 --> 00:04:15,560
Do ni ia maldekstre
duono de la oranĝo porcion.

87
00:04:15,560 --> 00:04:21,280
>> Nun ni estas en la mezo de ordiga
la dekstra duono de la oranĝo porcion.

88
00:04:21,280 --> 00:04:25,320
En tiu procezo, ni estas
nun baldaux estos sur la ŝtupo,

89
00:04:25,320 --> 00:04:27,850
kunfandi la du duonojn kune.

90
00:04:27,850 --> 00:04:31,700
Kiam ni rigardas la du duonoj
de la tabelo, ni vidas du unu.

91
00:04:31,700 --> 00:04:33,880
Kiu elemento estas malgranda?

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

93
00:04:35,160 --> 00:04:36,760
>> Tiam kiun elemento estas malgranda?

94
00:04:36,760 --> 00:04:38,300
Nu, estas du aŭ nenio.

95
00:04:38,300 --> 00:04:39,910
Do estas du.

96
00:04:39,910 --> 00:04:43,690
Do nun, nur por denove enmarcar
kie ni estas en kunteksto,

97
00:04:43,690 --> 00:04:48,230
ni ordo la
maldekstra duono de la oranĝo

98
00:04:48,230 --> 00:04:49,886
kaj la dekstran duonon de la origino.

99
00:04:49,886 --> 00:04:52,510
Mi scias ke mi ŝanĝis la kolorojn
denove, sed tio estas kie ni estis.

100
00:04:52,510 --> 00:04:54,676
Kaj la kialo mi faris tion
estas ĉar tiu procezo estas

101
00:04:54,676 --> 00:04:57,870
tuj plu iri, ripetanta suben.

102
00:04:57,870 --> 00:05:00,500
Ni ordo maldekstren
duono de la iama oranĝo

103
00:05:00,500 --> 00:05:02,590
kaj la dekstran duonon de la iama oranĝo.

104
00:05:02,590 --> 00:05:05,620
>> Nun, ni bezonas kunfandi tiujn
du duonojn kune tro.

105
00:05:05,620 --> 00:05:07,730
Tio estas la paŝo ni estas sur.

106
00:05:07,730 --> 00:05:11,440
Do ni konsideras ĉiujn
elementoj, kiuj estas nun verda,

107
00:05:11,440 --> 00:05:12,972
la maldekstra duono de la originala tabelo.

108
00:05:12,972 --> 00:05:14,680
Kaj ni kunfandi tiujn
uzante la saman procezon

109
00:05:14,680 --> 00:05:18,660
ni faris por kunfalado du
kaj unu nur antaŭ momento.

110
00:05:18,660 --> 00:05:23,080
>> La maldekstra duono, la plej malgranda
elemento maldekstre duono estas kvin.

111
00:05:23,080 --> 00:05:25,620
La plej malgranda elemento sur
la dekstra duono estas unu.

112
00:05:25,620 --> 00:05:27,370
Kiu el tiuj estas pli malgranda?

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

114
00:05:29,260 --> 00:05:32,250
>> La plej malgranda elemento sur
la maldekstra duono estas kvin.

115
00:05:32,250 --> 00:05:35,540
La plej malgranda elemento sur
la dekstra duono estas du.

116
00:05:35,540 --> 00:05:36,970
Kio estas la plej malgranda?

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

118
00:05:38,160 --> 00:05:41,540
Kaj poste persiste kvin
nenion, ni povas diri kvin.

119
00:05:41,540 --> 00:05:43,935
>> Bone, do granda bildo, ni
paŭzi dum sekundo

120
00:05:43,935 --> 00:05:46,080
kaj eltrovi kie ni estas.

121
00:05:46,080 --> 00:05:48,580
Se ni komencis
la komenco, ni

122
00:05:48,580 --> 00:05:51,640
nun kompletigis por
la totala tabelo nur

123
00:05:51,640 --> 00:05:53,810
unu paŝo de la _pseudocode_ kodo tie.

124
00:05:53,810 --> 00:05:56,645
Ni ordo la
maldekstra duono de la tabelo.

125
00:05:56,645 --> 00:05:59,490
>> Memoru ke la originala
ordono estis kvin, du, unu.

126
00:05:59,490 --> 00:06:02,570
Irante tra ĉi tiu procezo
kaj nestumas malsupren kaj ripeti,

127
00:06:02,570 --> 00:06:05,990
daŭra rompi la problemo
malsupren en pli malgrandajn kaj pli malgrandaj partoj,

128
00:06:05,990 --> 00:06:09,670
ni nun kompletigita
paŝi unu el la _pseudocode_

129
00:06:09,670 --> 00:06:13,940
por la tuta komenca tabelo.

130
00:06:13,940 --> 00:06:16,670
Ni ordigitaj lia maldekstra duono.

131
00:06:16,670 --> 00:06:18,670
>> Do nun ni glaciiĝas tie.

132
00:06:18,670 --> 00:06:23,087
Kaj nun ni ordigi la dekstra
duonon de la originala tabelo.

133
00:06:23,087 --> 00:06:25,670
Kaj ni tuj faros tion per
irante tra la sama ripeta

134
00:06:25,670 --> 00:06:30,630
procezo de rompado aferojn malsupren
kaj tiam kunfandante ilin kune.

135
00:06:30,630 --> 00:06:34,290
>> Do la maldekstra duono de la
ruĝa, aŭ la maldekstra duono

136
00:06:34,290 --> 00:06:38,830
de la dekstra duono de la originalo
tabelo, Mi tuj diros estas tri.

137
00:06:38,830 --> 00:06:40,312
Denove, mi esti konsekvenca tie.

138
00:06:40,312 --> 00:06:42,020
Se vi havas neparan
nombro de elementoj, ĝi

139
00:06:42,020 --> 00:06:44,478
ne vere gravas ĉu
vi faras la maldekstra malgrandaj

140
00:06:44,478 --> 00:06:45,620
aŭ la dekstra unu malgranda.

141
00:06:45,620 --> 00:06:49,230
>> Kio gravas estas ke whenever vi
renkontas tiun problemon en farado

142
00:06:49,230 --> 00:06:51,422
a merge, vi devas esti konsekvenca.

143
00:06:51,422 --> 00:06:53,505
Vi ĉu ĉiam necesas
fari maldekstre malgrandaj

144
00:06:53,505 --> 00:06:55,421
aŭ ĉiam devas fari
la dekstra flanko pli malgranda.

145
00:06:55,421 --> 00:06:57,720
Tie, mi elektis por ĉiam
fari la maldekstra flanko pli malgranda

146
00:06:57,720 --> 00:07:04,380
kiam mia tabelo, aŭ mia
sub-tabelo, estas de nepara grandeco.

147
00:07:04,380 --> 00:07:07,420
>> Tri estas ununura ero,
kaj tiel ĝi estas ordo.

148
00:07:07,420 --> 00:07:10,860
Ni ekspluatita ke supozo
dum nia tuta procezo ĝis nun.

149
00:07:10,860 --> 00:07:15,020
Do nun ni ordigi la dekstra
duono de la dekstra duono,

150
00:07:15,020 --> 00:07:18,210
aŭ la dekstra duono de la ruĝa.

151
00:07:18,210 --> 00:07:20,390
>> Denove, ni bezonas dividi ĉi malsupren.

152
00:07:20,390 --> 00:07:21,910
Tio ne estas ununura elemento tabelo.

153
00:07:21,910 --> 00:07:23,970
Ni ne povas diveni ordo.

154
00:07:23,970 --> 00:07:27,060
Kaj do unue, ni tuj
ordigi la maldekstra duono.

155
00:07:27,060 --> 00:07:31,620
>> La maldekstra duono estas ununura ero,
do estas ia defaŭlte.

156
00:07:31,620 --> 00:07:34,840
Tiam ni iras por ordigi dekstren
duonon, kio estas ununura elemento.

157
00:07:34,840 --> 00:07:41,250
Ĝi estas ordo defaŭlte. Kaj nun,
ni povas kunfandi tiujn du kune.

158
00:07:41,250 --> 00:07:45,820
Kvar estas pli malgranda, kaj
tiam ses estas pli malgranda.

159
00:07:45,820 --> 00:07:48,870
>> Denove, kion ni faris je ĉi tiu punkto?

160
00:07:48,870 --> 00:07:52,512
Ni ordo maldekstren
duono de la dekstra duono.

161
00:07:52,512 --> 00:07:54,720
Aŭ revenanta al la originala
koloroj kiuj tie estis,

162
00:07:54,720 --> 00:07:57,875
ni ordigitaj maldekstren
duonon de la pli mola ruĝa.

163
00:07:57,875 --> 00:08:00,416
Estis origine malhela briko
ruĝa kaj nun ĝi estas pli mola ruĝa,

164
00:08:00,416 --> 00:08:02,350
aŭ ĝi estis pli molaj ruĝa.

165
00:08:02,350 --> 00:08:05,145
>> Kaj tiam ni ordo la
dekstra duono de la pli mola ruĝa.

166
00:08:05,145 --> 00:08:08,270
Nun, nu, ili estas verda denove, nur
ĉar ni tuj tra procezo.

167
00:08:08,270 --> 00:08:10,720
Kaj ni devas ripeti
tiun denove kaj denove.

168
00:08:10,720 --> 00:08:14,695
>> Do nun ni povas kunfandi tiujn
du duonoj kune.

169
00:08:14,695 --> 00:08:15,820
Kaj tio estas kion ni faras ĉi tie.

170
00:08:15,820 --> 00:08:17,653
Do la nigran linion ĵus
dividis la maldekstra duono

171
00:08:17,653 --> 00:08:19,690
kaj la dekstra duono de tiu speco parto.

172
00:08:19,690 --> 00:08:24,310
>> Ni komparu la plej malgranda valoro
sur la maldekstra flanko de la tabelo

173
00:08:24,310 --> 00:08:26,710
aŭ pardonu, la plej malgranda
valoro de la maldekstra duono

174
00:08:26,710 --> 00:08:30,790
al la plej malgranda valoro de la dekstra
duono kaj trovi ke tri estas pli malgranda.

175
00:08:30,790 --> 00:08:32,530
Kaj nun iom de optimumigo, dekstra?

176
00:08:32,530 --> 00:08:35,175
Ekzistas fakte nenio
lasis sur la maldekstra flanko.

177
00:08:35,175 --> 00:08:37,440
>> Nenio restas
sur la maldekstra flanko,

178
00:08:37,440 --> 00:08:40,877
Do ni povas kompetente
nur move-- ni povas deklari

179
00:08:40,877 --> 00:08:42,960
la resto de ĝi estas reale
ordo kaj ĝuste najlu gxin

180
00:08:42,960 --> 00:08:45,126
sur, ĉar nenio
alia por komparo.

181
00:08:45,126 --> 00:08:49,140
Kaj ni scias ke la dekstra flanko
de la dekstra flanko estas ordo.

182
00:08:49,140 --> 00:08:52,770
>> Bone, do nun ni frostigi denove kaj
eltrovi kie ni estas en la rakonto.

183
00:08:52,770 --> 00:08:56,120
En la totala tabelo,
Kion ni plenumis?

184
00:08:56,120 --> 00:08:58,790
Ni reale plenumi
nun paŝas unu kaj du paŝo.

185
00:08:58,790 --> 00:09:03,300
Ni ordo la maldekstra duono, kaj
ni ordigitaj la dekstra duono.

186
00:09:03,300 --> 00:09:08,210
>> Do nun, ĉiu kiu restas estas por ni
kunfandi tiujn du duonoj kune.

187
00:09:08,210 --> 00:09:11,670
Do ni komparu la plej malalta takso
elemento de ĉiu duono de la tabelo

188
00:09:11,670 --> 00:09:13,510
siavice kaj procedi.

189
00:09:13,510 --> 00:09:16,535
Unu estas malpli ol tri, do oni iras.

190
00:09:16,535 --> 00:09:19,770
>> Du estas malpli ol tri, do du iras.

191
00:09:19,770 --> 00:09:22,740
Tri estas malpli ol 5, do tri iras.

192
00:09:22,740 --> 00:09:25,820
Kvar estas malpli ol 5, do kvar iras.

193
00:09:25,820 --> 00:09:30,210
Tiam kvin estas malpli ol ses,
kaj ses estas ĉiuj kiuj restas.

194
00:09:30,210 --> 00:09:31,820
>> Nun, mi scias, ke estis multe da ŝtupoj.

195
00:09:31,820 --> 00:09:33,636
Kaj ni lasis multe
de memoro en nia maldormo.

196
00:09:33,636 --> 00:09:35,260
Kaj tio estas kio tiuj grizaj kvadratoj estas.

197
00:09:35,260 --> 00:09:40,540
Kaj ĝi verŝajne sentis ke prenis
multe pli longe ol inserción varo, bobelo

198
00:09:40,540 --> 00:09:42,660
varon, aŭ selektado varon.

199
00:09:42,660 --> 00:09:45,330
>> Sed fakte, ĉar
multe de tiuj procezoj

200
00:09:45,330 --> 00:09:48,260
okazas samtempe time--
kio estas io ni, denove,

201
00:09:48,260 --> 00:09:51,100
paroli pri kiam ni parolas pri
rekursio en estonta video--

202
00:09:51,100 --> 00:09:53,799
tiu algoritmo reale
klare estas fundamente

203
00:09:53,799 --> 00:09:55,590
malsama ol io
ni vidis antaŭ

204
00:09:55,590 --> 00:09:58,820
sed estas ankaŭ signife
pli efika.

205
00:09:58,820 --> 00:09:59,532
>> Kial estas tio?

206
00:09:59,532 --> 00:10:01,240
Nu, en la plej malbona
kazo scenaro, ni havas

207
00:10:01,240 --> 00:10:04,830
fendi n elementoj supren
kaj tiam recombinar ilin.

208
00:10:04,830 --> 00:10:06,680
Sed kiam ni recombinar
ilin, kion ni faras

209
00:10:06,680 --> 00:10:11,110
estas esence duobligante la
grandeco de la pli malgranda sensilo.

210
00:10:11,110 --> 00:10:14,260
Ni havas aron de unu elemento
arrays ke ni efike

211
00:10:14,260 --> 00:10:16,290
kombini en du elemento tabeloj.

212
00:10:16,290 --> 00:10:18,590
Kaj tiam ni prenas tiujn
du elemento tabeloj

213
00:10:18,590 --> 00:10:21,890
kaj kombini ilin en
kvar elemento arrays, kaj tiel plu,

214
00:10:21,890 --> 00:10:26,130
kaj tiel plu, kaj tiel plu, ĝis ni
havi solan n elemento tabelo.

215
00:10:26,130 --> 00:10:29,910
>> Sed kiom da doublings
necesas por atingi n?

216
00:10:29,910 --> 00:10:31,460
Pensu reen al la telefono libro ekzemplo.

217
00:10:31,460 --> 00:10:34,490
Multfoje ni havas ŝiri
la telefono libro en duono, kiom pli

218
00:10:34,490 --> 00:10:38,370
fojojn ni devos ŝiri la telefono libro
en duono, se la grandeco de la telefono libro

219
00:10:38,370 --> 00:10:39,680
duobliĝis?

220
00:10:39,680 --> 00:10:41,960
Restas nur unu, ĉu ne?

221
00:10:41,960 --> 00:10:45,360
>> Do ekzistas ia
logaritma elemento tie.

222
00:10:45,360 --> 00:10:48,590
Sed ni ankaŭ ankoraŭ devas almenaŭ
rigardi ĉiujn de la n elementoj.

223
00:10:48,590 --> 00:10:53,860
Do en la plej malbona kazo scenaro,
kunfandi speco kuras en n log n.

224
00:10:53,860 --> 00:10:56,160
Ni devas rigardi
ĉiuj de la n elementoj,

225
00:10:56,160 --> 00:11:02,915
kaj ni devas kombini ilin
kune en log n aroj de paŝoj.

226
00:11:02,915 --> 00:11:05,290
En la plej bona kazo scenaro,
la tabelo estas perfekte ordigita.

227
00:11:05,290 --> 00:11:06,300
Tio estas granda.

228
00:11:06,300 --> 00:11:09,980
Sed bazita sur la algoritmo ni havas ĉi tie,
ni ankoraŭ devas fendi kaj recombinar.

229
00:11:09,980 --> 00:11:13,290
Kvankam en ĉi tiu kazo, la
rekombini afablas senutila.

230
00:11:13,290 --> 00:11:14,720
Ĝi ne estas necesa.

231
00:11:14,720 --> 00:11:17,580
Sed ni ankoraŭ iras tra
la tuta procezo ĉiuokaze.

232
00:11:17,580 --> 00:11:21,290
>> Do en la plej bona kazo
kaj en la plej malbona kazo,

233
00:11:21,290 --> 00:11:24,970
tiu algoritmo kuras en n logo n tempon.

234
00:11:24,970 --> 00:11:29,130
Kunfandi varo estas sendube iom trickier
ol la alia ĉefa ordigado algoritmoj

235
00:11:29,130 --> 00:11:33,470
ni parolis pri CS50 sed estas
substance pli potenca.

236
00:11:33,470 --> 00:11:35,400
>> Kaj do se vi iam trovas
okazo bezoni ĝin

237
00:11:35,400 --> 00:11:38,480
aŭ uzi ĝin por ordigi
granda datuma aro, Akiranta

238
00:11:38,480 --> 00:11:41,940
vian kapon ĉirkaŭ la ideo de rekursio
tuj estos vere potenca.

239
00:11:41,940 --> 00:11:45,270
Kaj ĝi estas iranta fari vian
programojn vere multe pli eficiente

240
00:11:45,270 --> 00:11:48,700
uzante kunfandi speco kontre io alia.

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

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

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