1
00:00:00,000 --> 00:00:04,419
>> [CHWARAE CERDDORIAETH]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, felly mae uno
didoli yn algorithm arall eto

4
00:00:08,460 --> 00:00:11,200
y gallwn eu defnyddio i roi trefn ar
elfennau amrywiaeth.

5
00:00:11,200 --> 00:00:14,480
Ond fel y byddwn yn gweld, 'i' got a
gwahaniaeth sylfaenol iawn

6
00:00:14,480 --> 00:00:17,850
o fath dethol, swigen
didoli, a didoli mewnosod

7
00:00:17,850 --> 00:00:20,280
sy'n ei gwneud yn wir yn eithaf clyfar.

8
00:00:20,280 --> 00:00:24,290
>> Y syniad sylfaenol y tu ôl i uno
didoli yw didoli arrays llai

9
00:00:24,290 --> 00:00:27,430
ac yna cyfuno arrays rhai
gyda'i gilydd, neu uno them--

10
00:00:27,430 --> 00:00:31,440
dyna pam y name-- er mwyn didoli.

11
00:00:31,440 --> 00:00:34,230
Mae'r ffordd y uno fath yn ei wneud
mae hyn yn dan ddylanwad busnes yn offeryn

12
00:00:34,230 --> 00:00:37,290
Gelwir recursion, sef yr hyn
rydym yn mynd i fod yn siarad am cyn bo hir,

13
00:00:37,290 --> 00:00:39,720
ond nid ydym wedi siarad mewn gwirionedd am hyd yn hyn.

14
00:00:39,720 --> 00:00:43,010
>> Dyma y syniad sylfaenol y tu ôl math uno.

15
00:00:43,010 --> 00:00:46,320
Trefnu yn hanner chwith y array,
gan dybio n yn fwy na 1.

16
00:00:46,320 --> 00:00:49,980
A hyn yr wyf yn ei olygu wrth ddweud
gan dybio n yn fwy na 1 yw,

17
00:00:49,980 --> 00:00:53,970
Yr wyf yn meddwl y gallwn ni gytuno, os amrywiaeth
Dim ond yn cynnwys elfen unigol,

18
00:00:53,970 --> 00:00:54,680
mae'n datrys.

19
00:00:54,680 --> 00:00:56,560
Nid oes mewn gwirionedd yn rhaid i ni
i wneud unrhyw beth iddo.

20
00:00:56,560 --> 00:00:58,059
Gall Rydym yn unig yn datgan iddo gael ei datrys.

21
00:00:58,059 --> 00:01:00,110
Dim ond un elfen.

22
00:01:00,110 --> 00:01:03,610
>> Felly mae'r pseudocode, unwaith eto, yn
ddatrys y hanner chwith y rhesi,

23
00:01:03,610 --> 00:01:08,590
Yna ddatrys yr hanner hawl y array,
Yna uno'r ddau hanner at ei gilydd.

24
00:01:08,590 --> 00:01:11,040
Yn awr, yn barod efallai y byddwch yn
meddwl, mae'n fath o ychydig

25
00:01:11,040 --> 00:01:14,080
swnio fel eich bod yn oedi cyn gwneud the--
nad ydych yn mewn gwirionedd yn gwneud unrhyw beth.

26
00:01:14,080 --> 00:01:16,330
Rydych yn ei ddweud ddatrys y chwith
hanner, didoli'r hanner cywir,

27
00:01:16,330 --> 00:01:19,335
ond nad ydych yn dweud
i mi sut yr ydych yn gwneud hynny.

28
00:01:19,335 --> 00:01:22,220
>> Ond cofiwch fod cyn belled â
amrywiaeth yn elfen sengl,

29
00:01:22,220 --> 00:01:23,705
gallwn ddatgan ei datrys.

30
00:01:23,705 --> 00:01:25,330
Yna gallwn jyst cyfuno gyda'i gilydd.

31
00:01:25,330 --> 00:01:27,788
A dyna mewn gwirionedd y
syniad sylfaenol y tu ôl math uno,

32
00:01:27,788 --> 00:01:31,150
yw i dorri i lawr fel bod
eich araeau o faint un.

33
00:01:31,150 --> 00:01:33,430
Ac yna byddwch yn ail-adeiladu oddi yno.

34
00:01:33,430 --> 00:01:35,910
>> Cyfuno fath yn bendant
algorithm cymhleth.

35
00:01:35,910 --> 00:01:38,210
Ac mae hefyd ychydig yn
cymhleth i ddelweddu.

36
00:01:38,210 --> 00:01:41,870
Felly, gobeithio, y delweddu fy mod
wedi yma yn eich helpu i ddilyn ar hyd.

37
00:01:41,870 --> 00:01:45,640
A byddaf yn gwneud fy ngorau i adrodd pethau
a symud ymlaen drwy'r ychydig hyn yn fwy

38
00:01:45,640 --> 00:01:49,180
yn araf na'r rhai eraill
dim ond er mwyn, gobeithio cael eich pen

39
00:01:49,180 --> 00:01:51,800
o amgylch y syniadau y tu ôl math uno.

40
00:01:51,800 --> 00:01:54,680
>> Felly mae gennym yr un amrywiaeth â'r
didoli fideos algorithm eraill

41
00:01:54,680 --> 00:01:57,120
os ydych chi wedi gweld them--
o chwe elfen arae.

42
00:01:57,120 --> 00:02:02,110
Ac mae ein cod pseudocode yma yw didoli
yr hanner chwith, didoli'r hanner cywir,

43
00:02:02,110 --> 00:02:03,890
cyfuno'r ddau hanner at ei gilydd.

44
00:02:03,890 --> 00:02:09,770
Felly gadewch i ni gymryd y coch brics tywyll iawn
amrywiaeth a didoli'r hanner chwith ohono.

45
00:02:09,770 --> 00:02:13,380
>> Felly, am y tro, rydym yn mynd
i anwybyddu'r pethau ar y dde.

46
00:02:13,380 --> 00:02:15,740
Mae'n yno, ond rydym yn
nid ar y cam eto.

47
00:02:15,740 --> 00:02:18,220
Nid ydym ni mewn math y
hanner dde o'r rhesi.

48
00:02:18,220 --> 00:02:21,037
Ry'n ni mewn math y chwith
hanner y rhesi.

49
00:02:21,037 --> 00:02:22,870
A dim ond er mwyn
o fod ychydig yn fwy

50
00:02:22,870 --> 00:02:26,480
yn glir, fel y gallaf gyfeirio
i ba gam rydym yn ar,

51
00:02:26,480 --> 00:02:29,800
Rydw i'n mynd i newid y
lliw y set hon i oren.

52
00:02:29,800 --> 00:02:33,190
Yn awr, rydym yn dal i siarad am y
un hanner chwith y rhesi gwreiddiol.

53
00:02:33,190 --> 00:02:38,520
Ond dw i'n gobeithio bod drwy allu
cyfeirio at y lliwiau o eitemau amrywiol,

54
00:02:38,520 --> 00:02:40,900
bydd yn ei gwneud yn ychydig yn fwy
glir beth sy'n digwydd fan hyn.

55
00:02:40,900 --> 00:02:43,270
>> Iawn, felly erbyn hyn mae gennym
tri elfen arae.

56
00:02:43,270 --> 00:02:46,420
Sut rydym ddatrys hanner chwith o hyn
array, sydd yn dal i fod y cam hwn?

57
00:02:46,420 --> 00:02:49,400
Rydym yn ceisio datrys y chwith
hanner y brics coch array--

58
00:02:49,400 --> 00:02:52,410
hanner chwith o'r rhain
Rwyf bellach wedi lliw oren.

59
00:02:52,410 --> 00:02:54,840
>> Wel, gallem geisio
ailadrodd y broses hon eto.

60
00:02:54,840 --> 00:02:56,756
Felly, rydym yn dal i fod yn y
canol ceisio datrys

61
00:02:56,756 --> 00:02:58,700
hanner chwith y rhesi llawn.

62
00:02:58,700 --> 00:03:00,450
Mae hanner chwith y
array, Im 'jyst yn mynd

63
00:03:00,450 --> 00:03:03,910
i benderfynu fympwyol bod yr hanner chwith
yn llai na'r hanner cywir,

64
00:03:03,910 --> 00:03:06,550
gan fod hyn yn digwydd i
yn cynnwys tair elfen.

65
00:03:06,550 --> 00:03:11,260
>> Ac felly yr wyf i'n mynd i ddweud bod y
chwith hanner yr hanner chwith y rhesi

66
00:03:11,260 --> 00:03:14,050
yn unig yw yr elfen pump.

67
00:03:14,050 --> 00:03:18,360
Pump, yn elfen sengl
array, rydym yn gwybod sut i ddatrys y.

68
00:03:18,360 --> 00:03:21,615
Ac felly pump yn cael ei datrys.

69
00:03:21,615 --> 00:03:22,990
Rydym yn jyst yn mynd i ddatgan hynny.

70
00:03:22,990 --> 00:03:24,890
Mae'n elfen amrywiaeth sengl.

71
00:03:24,890 --> 00:03:29,015
>> Felly, rydym yn awr wedi datrys y
chwith hanner y half-- chwith

72
00:03:29,015 --> 00:03:33,190
neu yn hytrach, rydym wedi datrys y
chwith hanner y oren.

73
00:03:33,190 --> 00:03:37,970
Felly nawr, er mwyn dal i fod yn gyflawn
hanner chwith yr amrywiaeth gyffredinol, yn

74
00:03:37,970 --> 00:03:43,481
mae angen i ni ddatrys yr hanner cywir
yr oren, neu pethau hyn.

75
00:03:43,481 --> 00:03:44,230
Sut rydym yn gwneud hynny?

76
00:03:44,230 --> 00:03:45,930
Wel, mae gennym ddwy elfen arae.

77
00:03:45,930 --> 00:03:50,470
Felly, gallwn ddatrys yr hanner chwith
y rhesi, sef dau.

78
00:03:50,470 --> 00:03:52,090
Dau yn elfen sengl.

79
00:03:52,090 --> 00:03:55,890
Felly mae'n trefnu yn ôl ddiofyn.
Yna, gallwn ddatrys yr hanner cywir

80
00:03:55,890 --> 00:03:58,530
o y rhan honno o'r array, yr un.

81
00:03:58,530 --> 00:04:00,210
Dyna fath o yn ddiofyn.

82
00:04:00,210 --> 00:04:03,610
>> Mae hyn yn awr yn y tro cyntaf
rydym wedi cyrraedd cam uno.

83
00:04:03,610 --> 00:04:06,135
Rydym wedi cwblhau, er bod
rydym yn awr yn fath o nythu down--

84
00:04:06,135 --> 00:04:08,420
a dyna fath o anodd
peth gyda recursion yw,

85
00:04:08,420 --> 00:04:10,930
mae angen i chi gadw eich
pennaeth am ble yr ydym.

86
00:04:10,930 --> 00:04:15,560
Felly rydym wedi fath o chwith
hanner y gyfran oren.

87
00:04:15,560 --> 00:04:21,280
>> Ac yn awr, rydym yn yng nghanol didoli
hanner dde o'r gyfran oren.

88
00:04:21,280 --> 00:04:25,320
Ac yn y broses honno, yr ydym yn
bellach am i fod ar y cam,

89
00:04:25,320 --> 00:04:27,850
cyfuno'r ddau hanner at ei gilydd.

90
00:04:27,850 --> 00:04:31,700
Pan edrychwn ar y ddau hanner
y rhesi, rydym yn gweld dau ac un.

91
00:04:31,700 --> 00:04:33,880
Pa elfen yn llai?

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

93
00:04:35,160 --> 00:04:36,760
>> Yna, pa elfen yn llai?

94
00:04:36,760 --> 00:04:38,300
Wel, mae'n ddau neu ddim byd.

95
00:04:38,300 --> 00:04:39,910
Felly mae'n dau.

96
00:04:39,910 --> 00:04:43,690
Felly nawr, dim ond i ffrâm eto
lle'r ydym ni mewn cyd-destun,

97
00:04:43,690 --> 00:04:48,230
rydym wedi datrys y
chwith hanner y oren

98
00:04:48,230 --> 00:04:49,886
a'r hanner dde o'r tarddiad.

99
00:04:49,886 --> 00:04:52,510
Gwn fy mod wedi newid y lliwiau
unwaith eto, ond dyna lle yr oeddem.

100
00:04:52,510 --> 00:04:54,676
A'r rheswm Fe wnes i hyn
oherwydd bod y broses hon yn

101
00:04:54,676 --> 00:04:57,870
mynd i ddal ati, ailadrodd i lawr.

102
00:04:57,870 --> 00:05:00,500
Rydym wedi sortio y chwith
hanner y cyn-oren

103
00:05:00,500 --> 00:05:02,590
a'r hanner dde o'r cyn-oren.

104
00:05:02,590 --> 00:05:05,620
>> Yn awr, mae angen i uno rhai
ddau hanner at ei gilydd hefyd.

105
00:05:05,620 --> 00:05:07,730
Dyna'r cam rydym ar.

106
00:05:07,730 --> 00:05:11,440
Felly, rydym yn ystyried pob un o'r
elfennau sydd bellach yn wyrdd,

107
00:05:11,440 --> 00:05:12,972
hanner chwith y rhesi gwreiddiol.

108
00:05:12,972 --> 00:05:14,680
Ac rydym yn cyfuno y rhai
gan ddefnyddio'r un broses

109
00:05:14,680 --> 00:05:18,660
gwnaethom dros uno dau
ac un ychydig funudau'n ôl.

110
00:05:18,660 --> 00:05:23,080
>> Mae'r hanner chwith, y lleiaf
Elfen ar hanner chwith yw pump.

111
00:05:23,080 --> 00:05:25,620
Yr elfen lleiaf ar
yr hanner cywir yn un.

112
00:05:25,620 --> 00:05:27,370
Pa un o'r rheini yn llai?

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

114
00:05:29,260 --> 00:05:32,250
>> Yr elfen lleiaf ar
yr hanner chwith yw pump.

115
00:05:32,250 --> 00:05:35,540
Yr elfen lleiaf ar
yr hanner cywir yw dau.

116
00:05:35,540 --> 00:05:36,970
Beth yw'r lleiaf?

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

118
00:05:38,160 --> 00:05:41,540
Ac yna yn olaf pump a
dim byd, gallwn ddweud pump.

119
00:05:41,540 --> 00:05:43,935
>> Iawn, llun mor fawr, gadewch i ni
gymryd seibiant am eiliad

120
00:05:43,935 --> 00:05:46,080
a chyfrif i maes lle yr ydym.

121
00:05:46,080 --> 00:05:48,580
Os byddwn yn dechrau o
y cychwyn cyntaf, rydym yn

122
00:05:48,580 --> 00:05:51,640
bellach wedi cwblhau ar gyfer
yr amrywiaeth gyffredinol yn unig

123
00:05:51,640 --> 00:05:53,810
un cam y cod pseudocode yma.

124
00:05:53,810 --> 00:05:56,645
Rydym wedi datrys y
chwith hanner y rhesi.

125
00:05:56,645 --> 00:05:59,490
>> Dwyn i gof bod y ddogfen wreiddiol
gorchymyn oedd pump, dau, un.

126
00:05:59,490 --> 00:06:02,570
Drwy fynd drwy'r broses hon
a nythu i lawr ac ailadrodd,

127
00:06:02,570 --> 00:06:05,990
parhau i dorri'r broblem
i lawr yn rhannau llai ac yn llai,

128
00:06:05,990 --> 00:06:09,670
rydym bellach wedi cwblhau
cam un o'r pseudocode

129
00:06:09,670 --> 00:06:13,940
am yr amrywiaeth cychwyn cyfan.

130
00:06:13,940 --> 00:06:16,670
Rydym wedi datrys ei hanner chwith.

131
00:06:16,670 --> 00:06:18,670
>> Felly nawr gadewch i rewi yno.

132
00:06:18,670 --> 00:06:23,087
Ac yn awr gadewch i ni ddatrys yr hawl
hanner y rhesi gwreiddiol.

133
00:06:23,087 --> 00:06:25,670
Ac rydym yn mynd i wneud hynny drwy
mynd trwy'r un ailadroddol

134
00:06:25,670 --> 00:06:30,630
broses o dorri pethau i lawr
ac yna eu cyfuno gyda'i gilydd.

135
00:06:30,630 --> 00:06:34,290
>> Felly mae'r hanner chwith y
coch, neu'r hanner chwith

136
00:06:34,290 --> 00:06:38,830
o hanner dde o'r gwreiddiol
array, dwi'n mynd i ddweud yw tri.

137
00:06:38,830 --> 00:06:40,312
Unwaith eto, rwy'n bod yn gyson yma.

138
00:06:40,312 --> 00:06:42,020
Os oes gennych rhyfedd
nifer o elfennau, mae'n

139
00:06:42,020 --> 00:06:44,478
Nid yw o bwys mewn gwirionedd a yw
byddwch yn gwneud yr un a adawodd llai

140
00:06:44,478 --> 00:06:45,620
neu yr un cywir llai.

141
00:06:45,620 --> 00:06:49,230
>> Yr hyn sy'n bwysig yw bod pryd bynnag y byddwch
yn dod ar draws y broblem hon wrth gynnal

142
00:06:49,230 --> 00:06:51,422
yn uno, mae angen i chi fod yn gyson.

143
00:06:51,422 --> 00:06:53,505
Rydych naill ai angen i bob amser
gwneud ochr chwith llai

144
00:06:53,505 --> 00:06:55,421
neu bob amser angen i ni wneud
yr ochr dde llai.

145
00:06:55,421 --> 00:06:57,720
Yma, yr wyf wedi dewis bob amser
yn gwneud yr ochr chwith llai

146
00:06:57,720 --> 00:07:04,380
pan fydd fy array, neu fy
is-array, o faint od.

147
00:07:04,380 --> 00:07:07,420
>> Tri yn elfen sengl,
ac felly mae'n cael ei datrys.

148
00:07:07,420 --> 00:07:10,860
Rydym wedi ysgogi y rhagdybiaeth
drwy gydol ein proses gyfan hyd yn hyn.

149
00:07:10,860 --> 00:07:15,020
Felly nawr gadewch i ni ddatrys yr hawl
hanner yr hanner cywir,

150
00:07:15,020 --> 00:07:18,210
neu hanner dde o'r coch.

151
00:07:18,210 --> 00:07:20,390
>> Unwaith eto, mae angen i ni rannu hyn i lawr.

152
00:07:20,390 --> 00:07:21,910
Nid yw hyn yn elfen amrywiaeth sengl.

153
00:07:21,910 --> 00:07:23,970
Ni allwn ddatgan ei datrys.

154
00:07:23,970 --> 00:07:27,060
Ac felly yn gyntaf, rydym yn mynd
i roi trefn ar yr hanner chwith.

155
00:07:27,060 --> 00:07:31,620
>> Mae'r hanner chwith yn elfen sengl,
felly mae'n fath o yn ddiofyn.

156
00:07:31,620 --> 00:07:34,840
Yna, rydyn ni'n mynd i ddatrys yr hawl
hanner, sy'n elfen sengl.

157
00:07:34,840 --> 00:07:41,250
Mae'n trefnu yn ddiofyn. Ac yn awr,
gallwn uno dwy hynny at ei gilydd.

158
00:07:41,250 --> 00:07:45,820
Pedwar yn llai, ac
Yna, chwech yn llai.

159
00:07:45,820 --> 00:07:48,870
>> Unwaith eto, beth ydyn ni wedi'i wneud yn y fan hon?

160
00:07:48,870 --> 00:07:52,512
Rydym wedi sortio y chwith
hanner yr hanner cywir.

161
00:07:52,512 --> 00:07:54,720
Neu fynd yn ôl at y gwreiddiol
lliwiau a oedd yno,

162
00:07:54,720 --> 00:07:57,875
rydym wedi datrys y chwith
hanner y coch meddal.

163
00:07:57,875 --> 00:08:00,416
Yn wreiddiol roedd yn brics tywyll
coch ac yn awr mae'n feddalach yn goch,

164
00:08:00,416 --> 00:08:02,350
neu roedd yn goch meddal.

165
00:08:02,350 --> 00:08:05,145
>> Ac yna rydym wedi datrys y
hanner dde o'r coch meddal.

166
00:08:05,145 --> 00:08:08,270
Yn awr, yn dda, eu bod yn wyrdd unwaith eto, dim ond
oherwydd ein bod yn mynd trwy broses.

167
00:08:08,270 --> 00:08:10,720
Ac mae'n rhaid i ni ailadrodd
dros y a throsodd.

168
00:08:10,720 --> 00:08:14,695
>> Felly, erbyn hyn gallwn uno rhai
ddau hanner at ei gilydd.

169
00:08:14,695 --> 00:08:15,820
A dyna beth rydym yn ei wneud yma.

170
00:08:15,820 --> 00:08:17,653
Felly y llinell ddu yn unig
Rhannwyd yr hanner chwith

171
00:08:17,653 --> 00:08:19,690
a'r hanner cywir o'r math hwn yn rhan.

172
00:08:19,690 --> 00:08:24,310
>> Rydym yn cymharu gwerth lleiaf
ar ochr chwith y array--

173
00:08:24,310 --> 00:08:26,710
neu esgus i mi, y lleiaf
gwerth y hanner chwith

174
00:08:26,710 --> 00:08:30,790
i werth lleiaf o'r hawl
hanner ac yn canfod bod tri yn llai.

175
00:08:30,790 --> 00:08:32,530
Ac yn awr yn dipyn o optimeiddio, dde?

176
00:08:32,530 --> 00:08:35,175
Does dim byd mewn gwirionedd
gadael ar yr ochr chwith.

177
00:08:35,175 --> 00:08:37,440
>> Does dim byd sy'n weddill
ar yr ochr chwith,

178
00:08:37,440 --> 00:08:40,877
felly y gallwn effeithlon
dim ond move-- y gallwn ddatgan

179
00:08:40,877 --> 00:08:42,960
gweddill ei fod mewn gwirionedd
didoli a dim ond tac ei

180
00:08:42,960 --> 00:08:45,126
ymlaen, oherwydd does dim byd
arall i gymharu yn erbyn.

181
00:08:45,126 --> 00:08:49,140
Ac rydym yn gwybod bod yr ochr dde
o'r ochr dde yn cael ei datrys.

182
00:08:49,140 --> 00:08:52,770
>> Iawn, felly nawr gadewch i rewi eto ac
chyfrif i maes ble yr ydym yn y stori.

183
00:08:52,770 --> 00:08:56,120
Yn yr amrywiaeth gyffredinol,
yr hyn rydym wedi ei gyflawni?

184
00:08:56,120 --> 00:08:58,790
Rydym wedi cyflawni mewn gwirionedd
bellach camau un a dau gam.

185
00:08:58,790 --> 00:09:03,300
Rydym yn datrys yr hanner chwith, ac
rydym yn datrys yr hanner cywir.

186
00:09:03,300 --> 00:09:08,210
>> Felly nawr, cyfan sydd ar ôl yw i ni
i uno dau hanner y rheini at ei gilydd.

187
00:09:08,210 --> 00:09:11,670
Felly, rydym yn cymharu yr isaf gwerthfawr
elfen o bob hanner y rhesi

188
00:09:11,670 --> 00:09:13,510
yn eu tro ac yn symud ymlaen.

189
00:09:13,510 --> 00:09:16,535
Mae un yn llai na thri, felly neb yn mynd.

190
00:09:16,535 --> 00:09:19,770
>> Dau yn llai na thri, felly dau yn mynd.

191
00:09:19,770 --> 00:09:22,740
Three yn llai na 5, felly thri yn mynd.

192
00:09:22,740 --> 00:09:25,820
Mae pedwar yn llai na 5, felly phedwar yn mynd.

193
00:09:25,820 --> 00:09:30,210
Yna bum yn llai na chwech,
a chwech cyfan sy'n weddill.

194
00:09:30,210 --> 00:09:31,820
>> Yn awr, yr wyf yn gwybod, a oedd yn llawer o gamau.

195
00:09:31,820 --> 00:09:33,636
Ac rydym wedi gadael llawer
o gof yn ein deffro.

196
00:09:33,636 --> 00:09:35,260
A dyna beth sgwariau llwyd hynny.

197
00:09:35,260 --> 00:09:40,540
Ac mae'n fwy na thebyg yn teimlo fel hynny yn cymryd
llawer hwy na didoli fewnosod, swigen

198
00:09:40,540 --> 00:09:42,660
didoli, neu ddidoli dethol.

199
00:09:42,660 --> 00:09:45,330
>> Ond mewn gwirionedd, gan fod
llawer o'r prosesau hyn

200
00:09:45,330 --> 00:09:48,260
yn digwydd ar yr un adeg--
sydd yn rhywbeth yr ydym n annhymerus ', unwaith eto,

201
00:09:48,260 --> 00:09:51,100
siarad am pan fyddwn yn sôn am
recursion mewn dyfodol video--

202
00:09:51,100 --> 00:09:53,799
algorithm hwn mewn gwirionedd
yn amlwg yn sylfaenol

203
00:09:53,799 --> 00:09:55,590
yn wahanol nag unrhyw beth
yr ydym wedi ei weld o'r blaen

204
00:09:55,590 --> 00:09:58,820
ond mae hefyd yn sylweddol
yn fwy effeithlon.

205
00:09:58,820 --> 00:09:59,532
>> Pam hynny?

206
00:09:59,532 --> 00:10:01,240
Wel, yn y gwaethaf
senario achos, rydym wedi

207
00:10:01,240 --> 00:10:04,830
i rannu'r n elfen fyny
ac yna eu ailgyfuno.

208
00:10:04,830 --> 00:10:06,680
Ond pan fyddwn yn ailgyfuno
iddynt, yr hyn rydym yn ei wneud

209
00:10:06,680 --> 00:10:11,110
yn dyblu yn y bôn y
maint y arrays llai.

210
00:10:11,110 --> 00:10:14,260
Mae gennym griw o un elfen
araeau yr ydym yn effeithiol

211
00:10:14,260 --> 00:10:16,290
cyfuno i mewn i ddau arae elfen.

212
00:10:16,290 --> 00:10:18,590
Ac yna rydym yn cymryd rhai
ddau arae elfen

213
00:10:18,590 --> 00:10:21,890
a'u cyfuno gyda'i gilydd i mewn i
pedwar araeau elfennau, ac yn y blaen,

214
00:10:21,890 --> 00:10:26,130
ac yn y blaen, ac yn y blaen, nes i ni
ag elfen n amrywiaeth sengl.

215
00:10:26,130 --> 00:10:29,910
>> Ond faint o doublings
mae'n ei gymryd i gyrraedd n?

216
00:10:29,910 --> 00:10:31,460
Meddyliwch yn ôl at yr enghraifft llyfr ffôn.

217
00:10:31,460 --> 00:10:34,490
Sawl gwaith sydd gennym i rwygo
y llyfr ffôn yn ei hanner, faint yn fwy

218
00:10:34,490 --> 00:10:38,370
Amseroedd sydd gennym i rwygo y llyfr ffôn
yn ei hanner, os yw maint y llyfr ffôn

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

220
00:10:39,680 --> 00:10:41,960
Dim ond un, dde?

221
00:10:41,960 --> 00:10:45,360
>> Felly mae yna rhyw fath o
Elfen logarithmig yma.

222
00:10:45,360 --> 00:10:48,590
Ond rydym hefyd yn dal i orfod leiaf
edrych ar yr holl elfennau n.

223
00:10:48,590 --> 00:10:53,860
Felly, yn y senario achos gwaethaf,
uno fath yn rhedeg yn n log n.

224
00:10:53,860 --> 00:10:56,160
Mae'n rhaid i ni edrych ar
holl elfennau n,

225
00:10:56,160 --> 00:11:02,915
ac yr ydym wedi eu cyfuno
gyda'i gilydd mewn log n set o risiau.

226
00:11:02,915 --> 00:11:05,290
Yn y senario achos gorau,
yr amrywiaeth yn cael ei datrys yn berffaith.

227
00:11:05,290 --> 00:11:06,300
Mae hynny'n wych.

228
00:11:06,300 --> 00:11:09,980
Ond yn seiliedig ar y algorithm sydd gennym yma,
rydym yn dal i orfod rhannu ac ailgyfuno.

229
00:11:09,980 --> 00:11:13,290
Er bod yn yr achos hwn, mae'r
hailgyfuno yn fath o aneffeithiol.

230
00:11:13,290 --> 00:11:14,720
Nad oes ei angen.

231
00:11:14,720 --> 00:11:17,580
Ond rydym yn dal i fynd drwy
y broses gyfan beth bynnag.

232
00:11:17,580 --> 00:11:21,290
>> Felly, yn yr achos gorau
ac yn yr achos gwaethaf,

233
00:11:21,290 --> 00:11:24,970
algorithm hwn yn rhedeg mewn n log n amser.

234
00:11:24,970 --> 00:11:29,130
Cyfuno fath yn bendant yn ychydig yn fwy anodd
na'r prif algorithmau didoli eraill

235
00:11:29,130 --> 00:11:33,470
rydym wedi siarad am CS50, ond mae
llawer mwy pwerus.

236
00:11:33,470 --> 00:11:35,400
>> Ac felly os ydych chi erioed yn dod o hyd
achlysur i ei angen

237
00:11:35,400 --> 00:11:38,480
neu ei ddefnyddio i roi trefn ar
set fawr o ddata, cael

238
00:11:38,480 --> 00:11:41,940
eich pen o gwmpas y syniad o recursion
yn mynd i fod yn wirioneddol pwerus.

239
00:11:41,940 --> 00:11:45,270
Ac mae'n mynd i wneud eich
rhaglenni 'n sylweddol llawer mwy effeithlon

240
00:11:45,270 --> 00:11:48,700
gan ddefnyddio uno fath yn erbyn unrhyw beth arall.

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

242
00:11:49,640 --> 00:11:51,970
Mae hyn yn CS50.

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