1
00:00:00,000 --> 00:00:04,419
>> [MUSIC nagpe-play]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, sa gayon ang isang merge
uri ay isa pang algorithm

4
00:00:08,460 --> 00:00:11,200
na maaari naming gamitin upang uriin ang
ang mga elemento ng isang array.

5
00:00:11,200 --> 00:00:14,480
Ngunit bilang namin makita, ito ay nakuha ng isang
napaka pangunahing pagkakaiba

6
00:00:14,480 --> 00:00:17,850
mula sa pagpili ng uri, bubble
uri, at uri pagpapasok

7
00:00:17,850 --> 00:00:20,280
na gawin itong tunay na medyo matalino.

8
00:00:20,280 --> 00:00:24,290
>> Ang pangunahing ideya sa likod merge
uri ay upang ayusin mas maliit na array

9
00:00:24,290 --> 00:00:27,430
at pagkatapos ay pagsamahin ang mga array
sama-sama, o pagsamahin them--

10
00:00:27,430 --> 00:00:31,440
samakatuwid ang name-- sa inayos order.

11
00:00:31,440 --> 00:00:34,230
Ang paraan na pagsamahin ang mga uri
ito ay sa pamamagitan ng pagdaragdag ng isang kasangkapan

12
00:00:34,230 --> 00:00:37,290
tinatawag na recursion, na kung saan ay kung ano ang
kami ay pagpunta sa pakikipag-usap tungkol sa lalong madaling panahon,

13
00:00:37,290 --> 00:00:39,720
ngunit kami ay hindi talagang uusapang tungkol sa pa.

14
00:00:39,720 --> 00:00:43,010
>> Narito ang mga pangunahing ideya sa likod pagsasama-uuri.

15
00:00:43,010 --> 00:00:46,320
Pagsunud-sunurin ang kaliwang kalahati ng array,
sa pag-aakala n ay mas malaki sa 1.

16
00:00:46,320 --> 00:00:49,980
At kung ano ang ibig sabihin ko kapag sinasabi ko
sa pag-aakala n ay mas malaki sa 1 ay,

17
00:00:49,980 --> 00:00:53,970
Sa tingin ko maaari naming sumang-ayon na kung ang isang array
ay binubuo lamang ng isang solong elemento,

18
00:00:53,970 --> 00:00:54,680
ito ay pinagsunod-sunod.

19
00:00:54,680 --> 00:00:56,560
Hindi namin talagang kailangan
gumawa ng kahit ano sa mga ito.

20
00:00:56,560 --> 00:00:58,059
Maaari naming ipahayag lamang ito upang maging inayos.

21
00:00:58,059 --> 00:01:00,110
Ito ay lamang ng isang solong elemento.

22
00:01:00,110 --> 00:01:03,610
>> Kaya ang pseudocode, muli, ay
ayusin ang kaliwa kalahati ng array,

23
00:01:03,610 --> 00:01:08,590
pagkatapos ay ayusin ang kanang kalahati ng array,
pagkatapos ay pagsamahin ang dalawang bahagi ng magkasama.

24
00:01:08,590 --> 00:01:11,040
Ngayon, mayroon na maaari kang maging
pag-iisip, ito uri ng lamang

25
00:01:11,040 --> 00:01:14,080
tunog tulad ng ikaw ay paglagay off the--
hindi ka talaga ginagawa kahit ano.

26
00:01:14,080 --> 00:01:16,330
Ikaw ay nagsasabi uriin ang kaliwang
kalahati, uri-uriin ang kanang kalahati,

27
00:01:16,330 --> 00:01:19,335
ngunit hindi ka nagsasabi
akin kung paano mo ito ginagawa.

28
00:01:19,335 --> 00:01:22,220
>> Ngunit tandaan na hangga't
isang array ay isang solong elemento,

29
00:01:22,220 --> 00:01:23,705
maaari naming ipahayag ito pinagsunod-sunod.

30
00:01:23,705 --> 00:01:25,330
Pagkatapos ay maaari naming lamang pagsamahin ang mga ito nang magkakasama.

31
00:01:25,330 --> 00:01:27,788
At na aktwal na ang
pangunahing ideya sa likod ng pagsasama-uuri,

32
00:01:27,788 --> 00:01:31,150
ay upang basagin ito pababa upang
iyong array ay ang laki ng isa.

33
00:01:31,150 --> 00:01:33,430
At pagkatapos mong gawing muli mula doon.

34
00:01:33,430 --> 00:01:35,910
>> Pagsamahin ang mga uri ay tiyak
isang komplikadong algorithm.

35
00:01:35,910 --> 00:01:38,210
At ito ay isang maliit na ring
kumplikado upang maisalarawan.

36
00:01:38,210 --> 00:01:41,870
Kaya sana, ang visualization na ako
Mayroon dito ay makakatulong kang sumunod.

37
00:01:41,870 --> 00:01:45,640
At kukunin ko na subukan ang aking pinakamahusay sa magsaysay bagay
at magpatuloy sa pamamagitan ng isang maliit na mas

38
00:01:45,640 --> 00:01:49,180
mabagal kaysa sa iba pang mga iyan
lamang na sana ay makakuha ng iyong ulo

39
00:01:49,180 --> 00:01:51,800
sa paligid ng mga ideya sa likod ng pagsasama-uuri.

40
00:01:51,800 --> 00:01:54,680
>> Kaya kami ay may parehong array bilang ang
iba pang mga pag-uuri algorithm video

41
00:01:54,680 --> 00:01:57,120
kung ang iyong nakita them--
isang array anim na elemento.

42
00:01:57,120 --> 00:02:02,110
At ang aming pseudocode code dito ay uri
sa kaliwang kalahati, uri-uriin ang kanang kalahati,

43
00:02:02,110 --> 00:02:03,890
pagsamahin ang dalawang halves magkasama.

44
00:02:03,890 --> 00:02:09,770
Kaya sabihin ito napaka dark red brick
array at ayusin ang kaliwa kalahati nito.

45
00:02:09,770 --> 00:02:13,380
>> Kaya para sa oras, kami ay pagpunta
upang huwag pansinin ang mga bagay-bagay sa kanan.

46
00:02:13,380 --> 00:02:15,740
Ito ay doon, ngunit hindi namin
hindi sa na pa-hakbang.

47
00:02:15,740 --> 00:02:18,220
Ikinalulungkot namin na hindi sa uri-uriin ang mga
kanang kalahati ng array.

48
00:02:18,220 --> 00:02:21,037
Kami ay sa mga uri sa kaliwa
kalahati ng array.

49
00:02:21,037 --> 00:02:22,870
At para lamang sa kapakanan
ng pagiging isang maliit na mas

50
00:02:22,870 --> 00:02:26,480
malinaw, kaya ang maaari kong sumangguni
sa kung ano ang hakbang na hindi namin sa,

51
00:02:26,480 --> 00:02:29,800
Pupunta ako upang lumipat sa
kulay ng hanay na ito sa orange.

52
00:02:29,800 --> 00:02:33,190
Ngayon, pinag-uusapan pa rin kami tungkol sa
parehong kaliwa kalahati ng orihinal na array.

53
00:02:33,190 --> 00:02:38,520
Ngunit ako umaasa na sa pamamagitan ng kawalan ng kakayahang
sumangguni sa mga kulay ng iba't-ibang mga bagay,

54
00:02:38,520 --> 00:02:40,900
ito ay gumawa ito ng kaunti pa
malinaw kung ano ang nangyayari sa dito.

55
00:02:40,900 --> 00:02:43,270
>> OK, kaya ngayon kami ay may isang
tatlong element ng array.

56
00:02:43,270 --> 00:02:46,420
Paano namin-uri-uriin ang kaliwang kalahati ng
array, na kung saan ay pa rin ang hakbang na ito?

57
00:02:46,420 --> 00:02:49,400
Kami ay sinusubukan upang ayusin ang kaliwang
kalahati ng mga brick red array--

58
00:02:49,400 --> 00:02:52,410
sa kaliwang kalahati ng kung saan
Ngayon ko na kulay na ako orange.

59
00:02:52,410 --> 00:02:54,840
>> Well, maaari naming subukan at
ulitin muli ang proseso na ito.

60
00:02:54,840 --> 00:02:56,756
Kaya ikaw pa rin namin sa
gitna ng sinusubukan na ayusin

61
00:02:56,756 --> 00:02:58,700
sa kaliwang kalahati ng buong array.

62
00:02:58,700 --> 00:03:00,450
Ang kaliwang kalahati ng
array, ako lamang ang pagpunta

63
00:03:00,450 --> 00:03:03,910
nagkataon magpasya na ang kaliwang kalahati
ay mas maliit kaysa sa kanang kalahati,

64
00:03:03,910 --> 00:03:06,550
dahil ito ang mangyayari sa mga
binubuo ng tatlong elemento.

65
00:03:06,550 --> 00:03:11,260
>> At kaya ako pagpunta sa sabihin na ang
kaliwang kalahati ng kaliwang kalahati ng array

66
00:03:11,260 --> 00:03:14,050
ay lamang ang mga elemento ng limang.

67
00:03:14,050 --> 00:03:18,360
Five, pagiging isang solong elemento
array, alam namin kung paano ayusin ito.

68
00:03:18,360 --> 00:03:21,615
At kaya limang ay pinagsunod-sunod.

69
00:03:21,615 --> 00:03:22,990
Kami ay pagpunta na idedeklara na.

70
00:03:22,990 --> 00:03:24,890
Ito ay isang solong array elemento.

71
00:03:24,890 --> 00:03:29,015
>> Kaya ngayon inayos na namin ang mga
kaliwang kalahati ng kaliwang half--

72
00:03:29,015 --> 00:03:33,190
o sa halip, na inayos namin ang
kaliwang kalahati ng orange.

73
00:03:33,190 --> 00:03:37,970
Kaya ngayon, upang pa rin kumpleto
kaliwang kalahati ang kabuuang array, ang

74
00:03:37,970 --> 00:03:43,481
kailangan namin upang ayusin ang mga karapatan sa kalahati
ng orange, o mga bagay-bagay na ito.

75
00:03:43,481 --> 00:03:44,230
Paano namin gawin iyon?

76
00:03:44,230 --> 00:03:45,930
Well, kami ay may isang array ng dalawang elemento.

77
00:03:45,930 --> 00:03:50,470
Kaya maaari naming ayusin ang kaliwa kalahati
ng array, na kung saan ay dalawang.

78
00:03:50,470 --> 00:03:52,090
Dalawang ay isang solong elemento.

79
00:03:52,090 --> 00:03:55,890
Kaya ito ay nakaayos ayon sa default.
Pagkatapos ay maaari naming ayusin ang mga karapatan sa kalahati

80
00:03:55,890 --> 00:03:58,530
ng bahaging iyon ng array, ang isa.

81
00:03:58,530 --> 00:04:00,210
Iyan ay ang uri ng default.

82
00:04:00,210 --> 00:04:03,610
>> Ito ay ngayon sa unang pagkakataon
naabot na namin ang isang hakbang merge.

83
00:04:03,610 --> 00:04:06,135
Kami ay nakumpleto na, bagaman
na namin ngayon uri ng nested down--

84
00:04:06,135 --> 00:04:08,420
at na ang mga uri ng mga mapanlinlang
bagay na may recursion ay,

85
00:04:08,420 --> 00:04:10,930
kailangan mong ilagay ang iyong
ulo tungkol sa kung saan tayo ay.

86
00:04:10,930 --> 00:04:15,560
Kaya hindi namin uri ng kaliwang
kalahati ng mga orange na bahagi.

87
00:04:15,560 --> 00:04:21,280
>> At ngayon, hindi namin sa gitna ng pag-uuri
ang kanang kalahati ng orange bahagi.

88
00:04:21,280 --> 00:04:25,320
At sa prosesong iyon, kami ay
tungkol sa ngayon na sa hakbang na ito,

89
00:04:25,320 --> 00:04:27,850
pagsamahin ang dalawang halves magkasama.

90
00:04:27,850 --> 00:04:31,700
Kapag tinitingnan namin ang dalawang bahagi
ng array, nakita namin ng dalawa at isa.

91
00:04:31,700 --> 00:04:33,880
Aling elemento ay mas maliit?

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

93
00:04:35,160 --> 00:04:36,760
>> Pagkatapos na elemento ay mas maliit?

94
00:04:36,760 --> 00:04:38,300
Well, ito ay ang dalawa o wala.

95
00:04:38,300 --> 00:04:39,910
Kaya ito ay dalawa.

96
00:04:39,910 --> 00:04:43,690
Kaya ngayon, sa muli-frame lamang
kung saan tayo ay sa konteksto,

97
00:04:43,690 --> 00:04:48,230
may inayos namin ang mga
kaliwang kalahati ng orange

98
00:04:48,230 --> 00:04:49,886
at ang kanang kalahati ng pinanggalingan.

99
00:04:49,886 --> 00:04:52,510
Alam ko ako ay nagbago ang mga kulay
muli, ngunit iyan ay kung saan namin.

100
00:04:52,510 --> 00:04:54,676
At ang dahilan ginawa ko ito
ay dahil ang proseso na ito ay

101
00:04:54,676 --> 00:04:57,870
pagpunta sa panatilihin ang pagpunta, iterating down.

102
00:04:57,870 --> 00:05:00,500
Inayos na namin ang kaliwang
kalahati ng mga dating orange

103
00:05:00,500 --> 00:05:02,590
at ang kanang kalahati ng dating orange.

104
00:05:02,590 --> 00:05:05,620
>> Ngayon, kailangan namin upang sumanib sa mga
dalawang kalahati magkasama masyadong.

105
00:05:05,620 --> 00:05:07,730
Iyan ang step kami sa.

106
00:05:07,730 --> 00:05:11,440
Kaya isaalang-alang namin ang lahat ng
elemento na green ngayon,

107
00:05:11,440 --> 00:05:12,972
sa kaliwang kalahati ng orihinal na array.

108
00:05:12,972 --> 00:05:14,680
At sumanib namin ang mga
gamit ang parehong proseso

109
00:05:14,680 --> 00:05:18,660
ginawa namin para sa pinagsasama ang dalawang
at isa lamang ng isang sandali ang nakalipas.

110
00:05:18,660 --> 00:05:23,080
>> Ang kaliwang kalahati, ang pinakamaliit
elemento sa kaliwang kalahati ay limang.

111
00:05:23,080 --> 00:05:25,620
Ang pinakamaliit na elemento sa
ang kanang kalahati ay isa.

112
00:05:25,620 --> 00:05:27,370
Alin sa mga ito ay mas maliit?

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

114
00:05:29,260 --> 00:05:32,250
>> Ang pinakamaliit na elemento sa
sa kaliwang kalahati ay limang.

115
00:05:32,250 --> 00:05:35,540
Ang pinakamaliit na elemento sa
ang kanang kalahati ay dalawa.

116
00:05:35,540 --> 00:05:36,970
Ano ang pinakamaliit?

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

118
00:05:38,160 --> 00:05:41,540
At pagkatapos ay sa wakas limang at
wala, maaari naming sabihin lima.

119
00:05:41,540 --> 00:05:43,935
>> OK, kaya malaki larawan, sabihin
kumuha ng pahinga para sa isang segundo

120
00:05:43,935 --> 00:05:46,080
at malaman kung saan kami.

121
00:05:46,080 --> 00:05:48,580
Kung nagsimula kami mula sa
Na sa simula, kami ay

122
00:05:48,580 --> 00:05:51,640
may ngayon nakumpleto para
ang kabuuang array lamang

123
00:05:51,640 --> 00:05:53,810
isang hakbang ng pseudocode code dito.

124
00:05:53,810 --> 00:05:56,645
Kami ay inayos ang
kaliwang kalahati ng array.

125
00:05:56,645 --> 00:05:59,490
>> Alalahanin na ang mga orihinal na
sunod ay limang, dalawa, isa.

126
00:05:59,490 --> 00:06:02,570
Sa pamamagitan ng pagpunta sa pamamagitan ng proseso na ito
at mamahinga pababa at paulit-ulit,

127
00:06:02,570 --> 00:06:05,990
patuloy na putulin ang problema
down sa mas maliit at mas maliit na bahagi,

128
00:06:05,990 --> 00:06:09,670
ngayon kami ay nakumpleto
hakbang isa sa pseudocode

129
00:06:09,670 --> 00:06:13,940
para sa buong panimulang array.

130
00:06:13,940 --> 00:06:16,670
Kami ay inayos kaliwang kalahati nito.

131
00:06:16,670 --> 00:06:18,670
>> Kaya ni-freeze doon ngayon hayaan.

132
00:06:18,670 --> 00:06:23,087
At ayusin sa ngayon hayaan
kalahati ng orihinal na array.

133
00:06:23,087 --> 00:06:25,670
At kami ay pagpunta upang gawin iyon sa pamamagitan ng
pagpunta sa pamamagitan ng parehong umuulit

134
00:06:25,670 --> 00:06:30,630
proseso ng paglabag bagay down
at pagkatapos ay pinagsasama ang mga ito nang magkakasama.

135
00:06:30,630 --> 00:06:34,290
>> Kaya ang kaliwang kalahati ng
pula, o sa kaliwang kalahati

136
00:06:34,290 --> 00:06:38,830
ng kanang kalahati ng orihinal
array, ako ng pagpunta sa sabihin ay tatlo.

137
00:06:38,830 --> 00:06:40,312
Muli, ako pagiging pare-pareho dito.

138
00:06:40,312 --> 00:06:42,020
Kung ikaw ay may isang kakaiba
bilang ng mga elemento, ito

139
00:06:42,020 --> 00:06:44,478
ay hindi talagang mahalaga kung
mong gawin ang mga ditong isang mas maliit

140
00:06:44,478 --> 00:06:45,620
o ang karapatan ng isa na mas maliit.

141
00:06:45,620 --> 00:06:49,230
>> Ano ang mga bagay na kahit kailan mo
magkasalubong ang problemang ito sa pagsasagawa

142
00:06:49,230 --> 00:06:51,422
isang merge, kailangan mo upang maging pare-pareho.

143
00:06:51,422 --> 00:06:53,505
Kang mag-laging kailangan upang
gumawa ng isang kaliwang bahagi ng mas maliit na

144
00:06:53,505 --> 00:06:55,421
o laging kailangan upang gumawa ng mga
sa kanang bahagi ng mas maliit.

145
00:06:55,421 --> 00:06:57,720
Dito, pinili ko na laging
gawin ang kaliwang bahagi ng mas maliit na

146
00:06:57,720 --> 00:07:04,380
kapag ang aking mga array, o ang aking
sub-array, ay ng isang kakaibang sukat.

147
00:07:04,380 --> 00:07:07,420
>> Tatlong ay isang solong elemento,
at sa gayon ito ay pinagsunod-sunod.

148
00:07:07,420 --> 00:07:10,860
Leveraged namin na palagay
buong aming buong proseso sa ngayon.

149
00:07:10,860 --> 00:07:15,020
Kaya ngayon ayusin ni kanan ipaalam
kalahati ng kanang kalahati,

150
00:07:15,020 --> 00:07:18,210
o ang karapatan sa kalahati ng mga pula.

151
00:07:18,210 --> 00:07:20,390
>> Muli, kailangan nating nahati ito pababa.

152
00:07:20,390 --> 00:07:21,910
Ito ay hindi isang solong array elemento.

153
00:07:21,910 --> 00:07:23,970
Hindi namin ipahayag ito pinagsunod-sunod.

154
00:07:23,970 --> 00:07:27,060
At kaya una, kami ay pagpunta
upang ayusin ang kaliwang kalahati.

155
00:07:27,060 --> 00:07:31,620
>> Ang kaliwang kalahati ay isang solong elemento,
kaya ito ay uri ng sa pamamagitan ng default.

156
00:07:31,620 --> 00:07:34,840
Pagkatapos kami ay pagpunta sa uri-uriin ang mga karapatan
kalahati, na kung saan ay isang solong elemento.

157
00:07:34,840 --> 00:07:41,250
Ito ay nakaayos ayon sa default. At ngayon,
kami ay maaaring sumanib sa mga dalawang magkasama.

158
00:07:41,250 --> 00:07:45,820
Apat ay mas maliit, at
pagkatapos ng anim na ito ay mas maliit.

159
00:07:45,820 --> 00:07:48,870
>> Muli, kung ano ang mayroon kami tapos sa puntong ito?

160
00:07:48,870 --> 00:07:52,512
Inayos na namin ang kaliwang
kalahati ng mga karapatan sa kalahati.

161
00:07:52,512 --> 00:07:54,720
O balik sa orihinal na
kulay nandoon,

162
00:07:54,720 --> 00:07:57,875
Inayos na namin ang kaliwang
kalahati ng hinaan red.

163
00:07:57,875 --> 00:08:00,416
Ito ay orihinal na isang madilim na ladrilyo
red at ngayon ito ay isang hinaan pula,

164
00:08:00,416 --> 00:08:02,350
o ito ay isang hinaan red.

165
00:08:02,350 --> 00:08:05,145
>> At pagkatapos Inayos na namin ang mga
kanang kalahati ng hinaan red.

166
00:08:05,145 --> 00:08:08,270
Ngayon, well, ang mga ito ay berde muli, lamang
dahil kami ay pagpunta sa pamamagitan ng isang proseso.

167
00:08:08,270 --> 00:08:10,720
At kami ay may upang ulitin
ito nang paulit-ulit.

168
00:08:10,720 --> 00:08:14,695
>> Kaya ngayon maaari naming pagsamahin ang mga
dalawang kalahati magkasama.

169
00:08:14,695 --> 00:08:15,820
At na kung ano ang ginagawa namin dito.

170
00:08:15,820 --> 00:08:17,653
Kaya ang itim na linya lamang
nahahati sa kaliwang kalahati

171
00:08:17,653 --> 00:08:19,690
at ang kanang kalahati ng uri na ito bahagi.

172
00:08:19,690 --> 00:08:24,310
>> Inihambing namin ang pinakamaliit na halaga
sa kaliwang bahagi ng array--

173
00:08:24,310 --> 00:08:26,710
o patawarin ninyo ako, ang pinakamaliit
halaga ng kaliwang kalahati

174
00:08:26,710 --> 00:08:30,790
sa pinakamaliit na halaga ng mga karapatan
half at natagpuan na ang tatlong ay mas maliit.

175
00:08:30,790 --> 00:08:32,530
At ngayon ng isang piraso ng isang pag-optimize, i-right?

176
00:08:32,530 --> 00:08:35,175
Mayroon talagang walang
iniwan sa kaliwang bahagi.

177
00:08:35,175 --> 00:08:37,440
>> May walang natitirang ay
sa kaliwang bahagi,

178
00:08:37,440 --> 00:08:40,877
upang maaari naming mahusay
move-- lamang maaari naming ipahayag

179
00:08:40,877 --> 00:08:42,960
ang natitirang bahagi ng mga ito ay tunay na
inayos at tak lang ito

180
00:08:42,960 --> 00:08:45,126
on, dahil mayroong wala
iba pa upang ihambing kumpara sa.

181
00:08:45,126 --> 00:08:49,140
At nalalaman natin na ang kanang bahagi
ng kanang bahagi ay nakaayos.

182
00:08:49,140 --> 00:08:52,770
>> OK, kaya ngayon sabihin freeze muli at
malaman kung saan tayo sa kuwento.

183
00:08:52,770 --> 00:08:56,120
Sa pangkalahatang array,
kung ano kami ay tapos na?

184
00:08:56,120 --> 00:08:58,790
Talaga namin ang magawa ang
ngayon hakbang isa at dalawang hakbang.

185
00:08:58,790 --> 00:09:03,300
Inayos namin ang kaliwang kalahati, at
Inayos namin ang karapatan kalahati.

186
00:09:03,300 --> 00:09:08,210
>> Kaya ngayon, ang lahat na nananatiling ay para sa amin
upang sumanib sa mga dalawang halves magkasama.

187
00:09:08,210 --> 00:09:11,670
Kaya namin ihambing ang pinakamababang minamahal
sangkap ng bawat kalahati ng array

188
00:09:11,670 --> 00:09:13,510
naman at magpatuloy.

189
00:09:13,510 --> 00:09:16,535
Ang isa ay mas mababa sa tatlong, para magpunta.

190
00:09:16,535 --> 00:09:19,770
>> Dalawang ay mas mababa kaysa sa tatlong, kaya dalawang napupunta.

191
00:09:19,770 --> 00:09:22,740
Tatlong ay mas mababa sa 5, kaya tatlong napupunta.

192
00:09:22,740 --> 00:09:25,820
Apat ay mas mababa sa 5, kaya apat na napupunta.

193
00:09:25,820 --> 00:09:30,210
Pagkatapos ng limang ay mas mababa sa anim na,
at anim ay ang lahat na nananatiling.

194
00:09:30,210 --> 00:09:31,820
>> Ngayon, alam ko, na noon ay isang pulutong ng mga hakbang.

195
00:09:31,820 --> 00:09:33,636
At kami iniwan na ng maraming
ng memory sa aming wake.

196
00:09:33,636 --> 00:09:35,260
At na kung ano ang mga kulay-abo na kahon ay.

197
00:09:35,260 --> 00:09:40,540
At ito marahil ang nadama tulad na kinuha ng isang
maraming mas mahaba kaysa uuri, bubble

198
00:09:40,540 --> 00:09:42,660
uri-uriin, o uri ng pagpili.

199
00:09:42,660 --> 00:09:45,330
>> Ngunit ang tunay na, dahil ang isang
pulutong ng mga proseso

200
00:09:45,330 --> 00:09:48,260
ay nangyayari sa parehong time--
na kung saan ay isang bagay na ipapakita namin, muli,

201
00:09:48,260 --> 00:09:51,100
makipag-usap tungkol sa usaping
recursion sa isang hinaharap video--

202
00:09:51,100 --> 00:09:53,799
algorithm na ito ang tunay
malinaw ay panimula

203
00:09:53,799 --> 00:09:55,590
naiiba kaysa sa anumang bagay
nakita natin dati

204
00:09:55,590 --> 00:09:58,820
ngunit ding makabuluhang
mas mahusay.

205
00:09:58,820 --> 00:09:59,532
>> Bakit na?

206
00:09:59,532 --> 00:10:01,240
Well, sa pinakamasama
case na sitwasyon, kami ay

207
00:10:01,240 --> 00:10:04,830
sa split n elemento up
at pagkatapos ay muling pagsamahin ang mga ito.

208
00:10:04,830 --> 00:10:06,680
Ngunit kapag muling pagsamahin namin
ang mga ito, kung ano ang aming ginagawa

209
00:10:06,680 --> 00:10:11,110
ay talaga pagdodoble ang
laki ng mas maliit na array.

210
00:10:11,110 --> 00:10:14,260
Kami ay may isang bungkos ng isang elemento
array na namin epektibong

211
00:10:14,260 --> 00:10:16,290
pagsamahin sa dalawang array elemento.

212
00:10:16,290 --> 00:10:18,590
At pagkatapos ay dadalhin namin ang mga
dalawang array elemento

213
00:10:18,590 --> 00:10:21,890
at pagsamahin ang mga ito nang magkakasama sa
apat na array na sangkap, at iba pa,

214
00:10:21,890 --> 00:10:26,130
at iba pa, at iba pa, hanggang sa kami
magkaroon ng isang solong array n element.

215
00:10:26,130 --> 00:10:29,910
>> Ngunit kung gaano karaming doublings
aabutin upang makakuha n?

216
00:10:29,910 --> 00:10:31,460
Isipin bumalik sa halimbawa phone book.

217
00:10:31,460 --> 00:10:34,490
Gaano karaming beses ang mayroon kami sa mapunit
ang telepono ng libro sa kalahati, kung paano mas maraming

218
00:10:34,490 --> 00:10:38,370
beses kailangan namin upang pilasin ang telepono ng libro
sa kalahati, kung ang laki ng mga libro ng telepono

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

220
00:10:39,680 --> 00:10:41,960
May isa lang, di ba?

221
00:10:41,960 --> 00:10:45,360
>> Kaya may ilang mga uri ng
logarithmic elemento dito.

222
00:10:45,360 --> 00:10:48,590
Ngunit pa rin namin ay mayroon din na hindi bababa sa
tingnan ang lahat ng mga n elemento.

223
00:10:48,590 --> 00:10:53,860
Kaya sa pinakamasama kaso sitwasyon,
sumanib-uuri ay tumatakbo sa n log n.

224
00:10:53,860 --> 00:10:56,160
Mayroon kaming upang tumingin sa
lahat ng mga n elemento,

225
00:10:56,160 --> 00:11:02,915
at kami ay upang pagsamahin ang mga ito
magkasama sa log n set ng mga hakbang.

226
00:11:02,915 --> 00:11:05,290
Sa ang pinakamahusay na kaso sitwasyon,
array ay ganap na pinagsunod-sunod.

227
00:11:05,290 --> 00:11:06,300
Mabuti iyan.

228
00:11:06,300 --> 00:11:09,980
Ngunit batay sa mga algorithm na namin dito,
mayroon pa rin kaming mag-split at muling pagsamahin.

229
00:11:09,980 --> 00:11:13,290
Kahit na sa kasong ito, ang
recombining ay uri ng walang saysay.

230
00:11:13,290 --> 00:11:14,720
Ito ay hindi kinakailangan.

231
00:11:14,720 --> 00:11:17,580
Ngunit kami ay pumunta pa rin sa pamamagitan
ang buong proseso pa rin.

232
00:11:17,580 --> 00:11:21,290
>> Kaya sa pinakamahusay na kaso
at sa pinakamasama kaso,

233
00:11:21,290 --> 00:11:24,970
algorithm na ito ay tumatakbo sa n log n oras.

234
00:11:24,970 --> 00:11:29,130
Pagsamahin ang mga uri ay talagang nangangailangan ng kaunting kasanayan
kaysa sa iba pang mga pangunahing pag-uuri algorithm

235
00:11:29,130 --> 00:11:33,470
Na-usapan natin ang tungkol sa CS50 ngunit ay
malaki mas malakas na.

236
00:11:33,470 --> 00:11:35,400
>> At kaya kung sakaling mahanap mo
okasyon sa kailangan ito

237
00:11:35,400 --> 00:11:38,480
o upang gamitin ito upang maipagsama-sama ang isang
malaking hanay ng data, pagkuha

238
00:11:38,480 --> 00:11:41,940
ang inyong ulo sa paligid ng ideya ng recursion
ay magiging talagang malakas.

239
00:11:41,940 --> 00:11:45,270
At ito ay pagpunta sa gawin ang iyong mga
talagang mas mahusay na mga programa

240
00:11:45,270 --> 00:11:48,700
gamit sumanib uri laban sa anumang bagay.

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

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

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