1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Mae pob hawl, felly, cymhlethdod cyfrifiadurol.

3
00:00:07,910 --> 00:00:10,430
Dim ond ychydig o rybudd
cyn i ni plymio yn rhy far--

4
00:00:10,430 --> 00:00:13,070
Mae'n debyg y byddwch hyn fod ymysg
pethau mwyaf mathemateg-trwm

5
00:00:13,070 --> 00:00:14,200
rydym yn siarad am yn CS50.

6
00:00:14,200 --> 00:00:16,950
Gobeithio na fydd yn rhy llethol
a byddwn yn ceisio eich tywys

7
00:00:16,950 --> 00:00:19,200
drwy'r broses, ond
dim ond ychydig o rybudd teg.

8
00:00:19,200 --> 00:00:21,282
Mae ychydig bach
o mathemateg dan sylw yma.

9
00:00:21,282 --> 00:00:23,990
Mae pob hawl, felly er mwyn gwneud
defnydd o'n hadnoddau cyfrifiadurol

10
00:00:23,990 --> 00:00:28,170
yn y world-- go iawn 'i' 'n sylweddol
bwysig deall algorithmau

11
00:00:28,170 --> 00:00:30,750
a sut y maent yn prosesu data.

12
00:00:30,750 --> 00:00:32,810
Os oes gennym mewn gwirionedd
algorithm effeithlon, rydym yn

13
00:00:32,810 --> 00:00:36,292
Gall lleihau faint o adnoddau
sydd ar gael gennym i ddelio ag ef.

14
00:00:36,292 --> 00:00:38,750
Os oes gennym algorithm sy'n
yn mynd i gymryd llawer o waith

15
00:00:38,750 --> 00:00:41,210
i brosesu 'n sylweddol
set fawr o ddata, mae'n

16
00:00:41,210 --> 00:00:44,030
mynd i angen mwy
a mwy o adnoddau, a oedd yn

17
00:00:44,030 --> 00:00:47,980
arian, RAM, pob math hwnnw o bethau yn.

18
00:00:47,980 --> 00:00:52,090
>> Felly, y gallu i ddadansoddi yn
algorithm gan ddefnyddio'r offeryn hwn set,

19
00:00:52,090 --> 00:00:56,110
yn y bôn, yn gofyn i'r question--
sut mae graddfa algorithm hwn

20
00:00:56,110 --> 00:00:59,020
wrth i ni daflu mwy a mwy o ddata arno?

21
00:00:59,020 --> 00:01:02,220
Yn CS50, faint o ddata rydym yn
gweithio gyda yn eithaf bach.

22
00:01:02,220 --> 00:01:05,140
Yn gyffredinol, mae ein rhaglenni yn mynd
i redeg mewn ail neu less--

23
00:01:05,140 --> 00:01:07,830
yn ôl pob tebyg yn llawer llai
yn enwedig yn gynnar.

24
00:01:07,830 --> 00:01:12,250
>> Ond meddyliwch am gwmni sy'n delio
gyda channoedd o filiynau o gwsmeriaid.

25
00:01:12,250 --> 00:01:14,970
Ac mae angen i brosesu
hynny data cwsmeriaid.

26
00:01:14,970 --> 00:01:18,260
Gan fod nifer y cwsmeriaid y maent yn
wedi mynd yn fwy ac yn fwy,

27
00:01:18,260 --> 00:01:21,230
mae'n mynd i'w gwneud yn ofynnol
mwy a mwy o adnoddau.

28
00:01:21,230 --> 00:01:22,926
Faint mwy o adnoddau?

29
00:01:22,926 --> 00:01:25,050
Wel, mae hynny'n dibynnu ar ba mor
byddwn yn ddadansoddi y algorithm,

30
00:01:25,050 --> 00:01:28,097
defnyddio'r offer yn y blwch offer hwn.

31
00:01:28,097 --> 00:01:31,180
Pan fyddwn yn sôn am gymhlethdod
mae algorithm-- sydd weithiau'n wnewch chi helpu

32
00:01:31,180 --> 00:01:34,040
glywed y cyfeirir ato fel amser
cymhlethdod neu le gymhlethdod

33
00:01:34,040 --> 00:01:36,190
ond rydym yn jyst yn mynd
i alw complexity--

34
00:01:36,190 --> 00:01:38,770
rydym yn gyffredinol yn siarad am
y sefyllfa waethaf.

35
00:01:38,770 --> 00:01:42,640
O ystyried y absoliwt pentwr gwaethaf o
data y gallem fod yn taflu arno,

36
00:01:42,640 --> 00:01:46,440
sut mae algorithm hwn yn mynd i
prosesu neu ddelio â data hwnnw?

37
00:01:46,440 --> 00:01:51,450
Rydym yn gyffredinol yn galw y gwaethaf-achos
Rhedeg o algorithm mawr-O.

38
00:01:51,450 --> 00:01:56,770
Felly efallai y algorithm yn cael ei dweud i
rhedeg mewn O n neu O n sgwâr.

39
00:01:56,770 --> 00:01:59,110
A mwy am yr hyn y
y rhai yn ei olygu mewn eiliad.

40
00:01:59,110 --> 00:02:01,620
>> Weithiau, fodd bynnag, rydym yn ei wneud gofal
am y sefyllfa orau-achos.

41
00:02:01,620 --> 00:02:05,400
Os yw'r data yn bopeth yr oeddem am
iddo fod ac yr oedd yn hollol berffaith

42
00:02:05,400 --> 00:02:09,630
ac yr oeddem yn anfon hwn perffaith
set o ddata trwy ein algorithm.

43
00:02:09,630 --> 00:02:11,470
Sut y byddai'n trin yn y sefyllfa honno?

44
00:02:11,470 --> 00:02:15,050
Weithiau, rydym yn cyfeirio at hynny fel
mawr-Omega, felly yn wahanol i fawr-O,

45
00:02:15,050 --> 00:02:16,530
mae gennym fawr-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega ar gyfer y sefyllfa orau-achos.

47
00:02:18,880 --> 00:02:21,319
Big O-gyfer y sefyllfa waethaf.

48
00:02:21,319 --> 00:02:23,860
Yn gyffredinol, pan fyddwn yn sôn am
cymhlethdod algorithm,

49
00:02:23,860 --> 00:02:26,370
rydym yn sôn am y
sefyllfa waethaf.

50
00:02:26,370 --> 00:02:28,100
Felly cadwch hynny mewn cof.

51
00:02:28,100 --> 00:02:31,510
>> Ac yn y dosbarth hwn, rydym yn mynd yn gyffredinol
i adael y dadansoddiad trylwyr o'r neilltu.

52
00:02:31,510 --> 00:02:35,350
Mae gwyddorau a chaeau
neilltuo i math hwn o bethau.

53
00:02:35,350 --> 00:02:37,610
Pan fyddwn yn sôn am rhesymu
trwy algorithmau,

54
00:02:37,610 --> 00:02:41,822
y byddwn yn ei wneud darn-by-darn ar gyfer llawer
algorithmau rydym yn siarad am yn y dosbarth.

55
00:02:41,822 --> 00:02:44,780
Rydym yn wir yn unig yn siarad am
rhesymu drwyddo gyda synnwyr cyffredin,

56
00:02:44,780 --> 00:02:47,070
nid gyda fformiwlâu, neu proflenni,
neu unrhyw beth fel 'na.

57
00:02:47,070 --> 00:02:51,600
Felly peidiwch â phoeni, ni fyddwn yn
droi i mewn i ddosbarth mathemateg mawr.

58
00:02:51,600 --> 00:02:55,920
>> Felly yr wyf yn dweud ein bod yn poeni am gymhlethdod
oherwydd ei fod yn gofyn y cwestiwn, sut

59
00:02:55,920 --> 00:03:00,160
mae ein algorithmau trin mwy o faint a
setiau data mwy o faint yn cael eu taflu atynt.

60
00:03:00,160 --> 00:03:01,960
Wel, beth yw set ddata?

61
00:03:01,960 --> 00:03:03,910
Beth wnes i ei olygu pan ddywedais hynny?

62
00:03:03,910 --> 00:03:07,600
Mae'n golygu beth bynnag yn gwneud y mwyaf
synnwyr mewn cyd-destun, a bod yn onest.

63
00:03:07,600 --> 00:03:11,160
Os oes gennym algorithm, y
Prosesau Strings-- rydym yn ôl pob tebyg

64
00:03:11,160 --> 00:03:13,440
siarad am faint y llinyn.

65
00:03:13,440 --> 00:03:15,190
Dyna y data set--
maint, mae nifer

66
00:03:15,190 --> 00:03:17,050
o gymeriadau sy'n rhan o'r llinyn.

67
00:03:17,050 --> 00:03:20,090
Os ydym yn sôn am
algorithm sy'n prosesu ffeiliau,

68
00:03:20,090 --> 00:03:23,930
Efallai y byddwn yn sôn am sut
llawer o kilobytes yn cynnwys y ffeil.

69
00:03:23,930 --> 00:03:25,710
A dyna y set ddata.

70
00:03:25,710 --> 00:03:28,870
Os ydym yn sôn am algorithm
sy'n delio araeau yn fwy cyffredinol,

71
00:03:28,870 --> 00:03:31,510
fel algorithmau didoli
neu chwilio algorithmau,

72
00:03:31,510 --> 00:03:36,690
yn ôl pob tebyg rydym yn sôn am y nifer
o elfennau sy'n cynnwys amrywiaeth.

73
00:03:36,690 --> 00:03:39,272
>> Yn awr, gallwn fesur yn
algorithm-- yn arbennig,

74
00:03:39,272 --> 00:03:40,980
wrth ddweud y gallwn
mesur algorithm, yr wyf yn

75
00:03:40,980 --> 00:03:43,840
yn golygu y gallwn fesur pa mor
llawer o adnoddau y mae'n ei gymryd i fyny.

76
00:03:43,840 --> 00:03:48,990
P'un adnoddau hynny yw, faint o
bytes o RAM-- neu megabeit o RAM

77
00:03:48,990 --> 00:03:49,790
mae'n defnyddio.

78
00:03:49,790 --> 00:03:52,320
Neu faint o amser mae'n ei gymryd i redeg.

79
00:03:52,320 --> 00:03:56,200
A gall rydym yn galw hyn
mesur, fympwyol, f o n.

80
00:03:56,200 --> 00:03:59,420
Pan n yw nifer y
elfennau yn y set ddata.

81
00:03:59,420 --> 00:04:02,640
A f o n yw faint o somethings.

82
00:04:02,640 --> 00:04:07,530
Sawl uned o adnoddau yn
mae'n ei gwneud yn ofynnol i brosesu data hynny.

83
00:04:07,530 --> 00:04:10,030
>> Nawr, nid ydym mewn gwirionedd yn poeni
am yr hyn y f o n yn union.

84
00:04:10,030 --> 00:04:13,700
Yn wir, rydym yn anaml iawn will--
yn sicr y bydd byth yn y wyf class--

85
00:04:13,700 --> 00:04:18,709
plymio i mewn i unrhyw 'n sylweddol dwfn
dadansoddiad o beth f o n yn.

86
00:04:18,709 --> 00:04:23,510
Rydym yn jyst yn mynd i siarad am yr hyn f o
n tua neu'r hyn mae'n tueddu i.

87
00:04:23,510 --> 00:04:27,600
Ac mae'r duedd o algorithm yw
bennu gan ei dymor radd uchaf.

88
00:04:27,600 --> 00:04:29,440
A gallwn weld yr hyn yr wyf
olygu wrth hynny drwy gymryd

89
00:04:29,440 --> 00:04:31,910
a edrych ar enghraifft yn fwy pendant.

90
00:04:31,910 --> 00:04:34,620
>> Felly, gadewch i ni ddweud ein bod wedi
tri algorithmau gwahanol.

91
00:04:34,620 --> 00:04:39,350
Y cyntaf ohonynt yn cymryd n
giwbiau, mae rhai unedau o adnoddau

92
00:04:39,350 --> 00:04:42,880
i brosesu set ddata o faint n.

93
00:04:42,880 --> 00:04:47,000
Mae gennym ail algorithm sy'n cymryd
n torri'n giwbiau ac adnoddau n sgwâr

94
00:04:47,000 --> 00:04:49,350
i brosesu set ddata o faint n.

95
00:04:49,350 --> 00:04:52,030
Ac mae gennym traean
algorithm sy'n rhedeg in-- hynny

96
00:04:52,030 --> 00:04:58,300
cymryd n 8n minws wedi'i dorri'n giwbiau sgwâr
yn ogystal â 20 o unedau n adnoddau

97
00:04:58,300 --> 00:05:02,370
i brosesu algorithm
gyda data a osodir o faint n.

98
00:05:02,370 --> 00:05:05,594
>> Nawr eto, yr ydym ddim wir yn mynd
i fynd i mewn y lefel hon o fanylder.

99
00:05:05,594 --> 00:05:08,260
Im 'mewn gwirionedd dim ond gael y rhain i fyny
yma fel enghraifft o bwynt

100
00:05:08,260 --> 00:05:10,176
fy mod i'n mynd i fod yn
gwneud mewn eiliad, a oedd

101
00:05:10,176 --> 00:05:12,980
yw ein bod dim ond 'n sylweddol gofal
am y duedd o bethau

102
00:05:12,980 --> 00:05:14,870
gan fod y setiau data yn cynyddu.

103
00:05:14,870 --> 00:05:18,220
Felly, os yw'r set ddata yn fach, mae '
mewn gwirionedd gwahaniaeth eithaf mawr

104
00:05:18,220 --> 00:05:19,870
yn y algorithmau hyn.

105
00:05:19,870 --> 00:05:23,000
Mae'r trydydd algorithm yno
yn cymryd 13 gwaith yn hirach,

106
00:05:23,000 --> 00:05:27,980
13 gwaith y swm o adnoddau
i redeg o'i gymharu â'r un cyntaf.

107
00:05:27,980 --> 00:05:31,659
>> Os yw ein set ddata yw maint 10, sy'n
yn fwy, ond nid o reidrwydd enfawr,

108
00:05:31,659 --> 00:05:33,950
gallwn weld bod yna
mewn gwirionedd yn dipyn o wahaniaeth.

109
00:05:33,950 --> 00:05:36,620
Mae'r trydydd algorithm
yn dod yn fwy effeithlon.

110
00:05:36,620 --> 00:05:40,120
Mae'n ymwneud â gwirionedd 40% -
neu 60% yn fwy effeithlon.

111
00:05:40,120 --> 00:05:41,580
Mae'n cymryd 40% faint o amser.

112
00:05:41,580 --> 00:05:45,250
Gall run-- gall gymryd
400 o unedau o adnoddau

113
00:05:45,250 --> 00:05:47,570
i brosesu set ddata o faint 10.

114
00:05:47,570 --> 00:05:49,410
Tra bod y cyntaf
algorithm, mewn cyferbyniad,

115
00:05:49,410 --> 00:05:54,520
yn cymryd 1,000 o unedau o adnoddau
i brosesu set ddata o faint 10.

116
00:05:54,520 --> 00:05:57,240
Ond edrychwch beth sy'n digwydd fel
ein rhifau gael hyd yn oed yn fwy.

117
00:05:57,240 --> 00:05:59,500
>> Yn awr, mae'r gwahaniaeth
rhwng y algorithmau hyn

118
00:05:59,500 --> 00:06:01,420
dechrau dod ychydig yn llai amlwg.

119
00:06:01,420 --> 00:06:04,560
Ac mae'r ffaith bod yna
is-archebu terms-- neu yn hytrach,

120
00:06:04,560 --> 00:06:09,390
delerau â exponents-- is
dechrau dod yn amherthnasol.

121
00:06:09,390 --> 00:06:12,290
Os set ddata o faint
1,000 a'r algorithm cyntaf

122
00:06:12,290 --> 00:06:14,170
yn rhedeg mewn biliwn o gamau.

123
00:06:14,170 --> 00:06:17,880
A'r ail algorithm yn rhedeg mewn
camau biliwn a miliwn.

124
00:06:17,880 --> 00:06:20,870
A'r trydydd algorithm yn rhedeg
mewn dim ond yn swil o biliwn o gamau.

125
00:06:20,870 --> 00:06:22,620
Mae'n 'n bert lawer biliwn o gamau.

126
00:06:22,620 --> 00:06:25,640
Mae'r rhai termau is-archebu cychwyn
i fod yn wir yn amherthnasol.

127
00:06:25,640 --> 00:06:27,390
A dim ond i wir
morthwyl gartref y point--

128
00:06:27,390 --> 00:06:31,240
os yw'r mewnbynnu data o faint a
million-- pob un o'r tri o'r rhain yn 'n bert lawer

129
00:06:31,240 --> 00:06:34,960
cymryd un quintillion-- os
fy mathemateg yn gamau correct--

130
00:06:34,960 --> 00:06:37,260
i brosesu data a fewnbynnir
o faint miliwn.

131
00:06:37,260 --> 00:06:38,250
Mae hynny'n llawer o risiau.

132
00:06:38,250 --> 00:06:42,092
Ac mae'r ffaith bod un ohonynt efallai
yn cymryd ychydig 100,000, neu gwpl 100

133
00:06:42,092 --> 00:06:44,650
miliwn hyd yn oed yn llai pan
rydym yn sôn am nifer

134
00:06:44,650 --> 00:06:46,990
hynny big-- mae'n fath o amherthnasol.

135
00:06:46,990 --> 00:06:50,006
Maent i gyd yn tueddu i gymryd
tua n giwbiau,

136
00:06:50,006 --> 00:06:52,380
ac felly byddem yn mewn gwirionedd yn cyfeirio
i bob un o'r algorithmau hyn

137
00:06:52,380 --> 00:06:59,520
fel bod ar y drefn n
torri'n giwbiau neu fawr-O n dorri'n giwbiau.

138
00:06:59,520 --> 00:07:03,220
>> Dyma restr o rai o'r mwy
dosbarthiadau cymhlethdod cyfrifiadurol cyffredin

139
00:07:03,220 --> 00:07:05,820
y byddwn yn dod ar eu traws mewn
algorithmau, yn gyffredinol.

140
00:07:05,820 --> 00:07:07,970
A hefyd yn benodol mewn CS50.

141
00:07:07,970 --> 00:07:11,410
Mae'r rhain yn cael eu harchebu gan
Yn gyffredinol gyflymaf ar y brig,

142
00:07:11,410 --> 00:07:13,940
i yn gyffredinol arafaf ar y gwaelod.

143
00:07:13,940 --> 00:07:16,920
Felly algorithmau amser cyson yn tueddu
i fod y cyflymaf, beth bynnag

144
00:07:16,920 --> 00:07:19,110
o faint y
mewnbynnu data i chi basio i mewn.

145
00:07:19,110 --> 00:07:23,760
Maent bob amser yn cymryd un llawdriniaeth neu
un uned o adnoddau i ddelio ag ef.

146
00:07:23,760 --> 00:07:25,730
Gallai fod yn 2, y gallai
fod yn 3, gallai fod yn 4.

147
00:07:25,730 --> 00:07:26,910
Ond mae'n rhif gyson.

148
00:07:26,910 --> 00:07:28,400
Nid yw'n amrywio.

149
00:07:28,400 --> 00:07:31,390
>> Algorithmau amser logarithmig
ychydig yn well.

150
00:07:31,390 --> 00:07:33,950
Ac yn enghraifft dda iawn o
algorithm amser logarithmig

151
00:07:33,950 --> 00:07:37,420
eich bod wedi gweld yn sicr erbyn hyn yw'r
rhwygo ar wahân y llyfr ffôn

152
00:07:37,420 --> 00:07:39,480
i ddod o hyd Mike Smith yn y llyfr ffôn.

153
00:07:39,480 --> 00:07:40,980
Rydym yn torri y broblem yn ei hanner.

154
00:07:40,980 --> 00:07:43,580
Ac felly fel n mynd yn fwy
a mwy o faint a larger--

155
00:07:43,580 --> 00:07:47,290
mewn gwirionedd, bob tro y byddwch yn dyblu
n, dim ond yn cymryd un cam mwy.

156
00:07:47,290 --> 00:07:49,770
Felly dyna yn llawer gwell
na, dyweder, amser llinol.

157
00:07:49,770 --> 00:07:53,030
Pa un yw os ydych yn dyblu n, mae'n
cymryd dwbl y nifer o gamau.

158
00:07:53,030 --> 00:07:55,980
Os byddwch yn triphlyg n, mae'n cymryd
dreblu nifer o gamau.

159
00:07:55,980 --> 00:07:58,580
Un cam yr uned.

160
00:07:58,580 --> 00:08:01,790
>> Yna pethau'n mynd ychydig o more--
ychydig yn llai gwych oddi yno.

161
00:08:01,790 --> 00:08:06,622
Mae gennych amser rhythmig llinol, weithiau
Gelwir log amser llinol neu dim ond n log n.

162
00:08:06,622 --> 00:08:08,330
Ac rydym chi helpu enghraifft
o algorithm sy'n

163
00:08:08,330 --> 00:08:13,370
yn rhedeg yn n log n, sydd yn dal yn well
na cwadratig adeg-- n sgwâr.

164
00:08:13,370 --> 00:08:17,320
Neu amser polynomial, n dau
unrhyw nifer fwy na dau.

165
00:08:17,320 --> 00:08:20,810
Neu amser esbonyddol, a oedd yn
hyd yn oed yn worse-- C i'r n.

166
00:08:20,810 --> 00:08:24,670
Felly mae rhai rhif gyson codi i
grym maint y mewnbwn.

167
00:08:24,670 --> 00:08:28,990
Felly, os oes 1,000-- os bydd y
mewnbynnu data o faint 1,000,

168
00:08:28,990 --> 00:08:31,310
byddai'n cymryd C i'r pŵer 1,000fed.

169
00:08:31,310 --> 00:08:33,559
Mae'n llawer gwaeth nag amser polynomial.

170
00:08:33,559 --> 00:08:35,030
>> Amser ffactoraidd yn oed yn waeth.

171
00:08:35,030 --> 00:08:37,760
Ac yn wir, mae yna wir yn
bodoli algorithmau amser anfeidrol,

172
00:08:37,760 --> 00:08:43,740
megis, hyn a elwir yn sort-- dwp y mae ei
swydd yw siffrwd arae ar hap

173
00:08:43,740 --> 00:08:45,490
ac yna edrychwch i weld a
boed yn datrys.

174
00:08:45,490 --> 00:08:47,589
Ac os nad yw'n, ar hap
siffrwd y rhesi eto

175
00:08:47,589 --> 00:08:49,130
a gwirio i weld a yw'n datrys.

176
00:08:49,130 --> 00:08:51,671
Ac fel y mae'n debyg y gallwch imagine--
gallwch ddychmygu sefyllfa

177
00:08:51,671 --> 00:08:55,200
ble yn y gwaethaf-achos, bydd hynny
byth mewn gwirionedd yn dechrau gyda y rhesi.

178
00:08:55,200 --> 00:08:57,150
Byddai hynny'n algorithm rhedeg am byth.

179
00:08:57,150 --> 00:08:59,349
Ac felly byddai hynny'n
algorithm amser anfeidrol.

180
00:08:59,349 --> 00:09:01,890
Gobeithio na fyddwch yn ysgrifennu
unrhyw adeg ffactoraidd neu anfeidrol

181
00:09:01,890 --> 00:09:04,510
algorithmau yn CS50.

182
00:09:04,510 --> 00:09:09,150
>> Felly, gadewch i ni gymryd ychydig yn fwy
Golwg concrit ar rai symlach

183
00:09:09,150 --> 00:09:11,154
dosbarthiadau cymhlethdod cyfrifiadurol.

184
00:09:11,154 --> 00:09:13,070
Felly mae gennym example--
neu ddwy enghraifft Yma--

185
00:09:13,070 --> 00:09:15,590
o algorithmau amser cyson,
sydd bob amser yn cymryd

186
00:09:15,590 --> 00:09:17,980
llawdriniaeth sengl yn y gwaethaf-achos.

187
00:09:17,980 --> 00:09:20,050
Felly, y example-- cyntaf
mae gennym swyddogaeth

188
00:09:20,050 --> 00:09:23,952
Gelwir 4 ar eich cyfer, a oedd yn
yn cymryd amrywiaeth o faint 1,000.

189
00:09:23,952 --> 00:09:25,660
Ond yna mae'n debyg
nid yw'n edrych mewn gwirionedd

190
00:09:25,660 --> 00:09:29,000
nid yn iddo-- ddim wir yn poeni beth sydd
tu mewn iddo, o'r rhesi.

191
00:09:29,000 --> 00:09:30,820
Bob amser yn unig yn dychwelyd pedwar.

192
00:09:30,820 --> 00:09:32,940
Felly, y algorithm,
er gwaethaf y ffaith ei fod yn

193
00:09:32,940 --> 00:09:35,840
yn cymryd 1,000 o elfennau nad yw'n
gwneud unrhyw beth gyda nhw.

194
00:09:35,840 --> 00:09:36,590
Dim ond yn dychwelyd pedwar.

195
00:09:36,590 --> 00:09:38,240
Mae bob amser un cam.

196
00:09:38,240 --> 00:09:41,600
>> Yn wir, ychwanegwch 2 nums-- sy'n
rydym wedi gweld o'r blaen fel well--

197
00:09:41,600 --> 00:09:43,680
dim ond prosesau dau rif cyfan.

198
00:09:43,680 --> 00:09:44,692
Nid yw'n un cam.

199
00:09:44,692 --> 00:09:45,900
Mae'n mewn gwirionedd camau cwpl.

200
00:09:45,900 --> 00:09:50,780
Byddwch yn cael, byddwch yn cael b, rydych yn eu hychwanegu
gyda'i gilydd, ac yr ydych allbwn y canlyniadau.

201
00:09:50,780 --> 00:09:53,270
Felly mae'n 84 cam.

202
00:09:53,270 --> 00:09:55,510
Ond mae'n gyson bob amser,
waeth beth a neu b.

203
00:09:55,510 --> 00:09:59,240
Mae'n rhaid i chi gael, yn cael b, ychwanegu
nhw at ei gilydd, allbwn y canlyniad.

204
00:09:59,240 --> 00:10:02,900
Felly dyna algorithm amser cyson.

205
00:10:02,900 --> 00:10:05,170
>> Dyma enghraifft o
algorithm-- amser llinol

206
00:10:05,170 --> 00:10:08,740
algorithm sy'n gets-- sy'n cymryd
un cam ychwanegol, o bosibl,

207
00:10:08,740 --> 00:10:10,740
fel eich mewnbwn yn tyfu gan 1.

208
00:10:10,740 --> 00:10:14,190
Felly, gadewch i ni ddweud ein bod yn chwilio am
rhif 5 tu mewn arae.

209
00:10:14,190 --> 00:10:16,774
Efallai y bydd gennych sefyllfa lle
gallwch ddod o hyd iddo yn weddol gynnar.

210
00:10:16,774 --> 00:10:18,606
Ond gallech hefyd gael
sefyllfa lle y mae'n

211
00:10:18,606 --> 00:10:20,450
Efallai fod yr elfen olaf y rhesi.

212
00:10:20,450 --> 00:10:23,780
Mewn amrywiaeth o faint 5, os
rydym yn chwilio am y rhif 5.

213
00:10:23,780 --> 00:10:25,930
Byddai'n cymryd 5 cam.

214
00:10:25,930 --> 00:10:29,180
Ac yn wir, ddychmygu bod yna
Nid yw 5 yn unrhyw le yn amrywiaeth hwn.

215
00:10:29,180 --> 00:10:32,820
Mae gennym mewn gwirionedd yn edrych ar
pob elfen unigol y rhesi

216
00:10:32,820 --> 00:10:35,550
er mwyn penderfynu
ai peidio 5 yno.

217
00:10:35,550 --> 00:10:39,840
>> Felly, yn y-achos gwaethaf, sef bod
yr elfen hon yn olaf yn y casgliad

218
00:10:39,840 --> 00:10:41,700
neu os nad yw'n bodoli o gwbl.

219
00:10:41,700 --> 00:10:44,690
Rydym yn dal i orfod edrych ar
pob un o'r elfennau n.

220
00:10:44,690 --> 00:10:47,120
Ac felly algorithm hwn
yn rhedeg mewn amser llinol.

221
00:10:47,120 --> 00:10:50,340
Gallwch gadarnhau bod gan
allosod ychydig drwy ddweud,

222
00:10:50,340 --> 00:10:53,080
pe bai gennym 6-elfen amrywiaeth a
roeddem yn chwilio am y rhif 5,

223
00:10:53,080 --> 00:10:54,890
gall gymryd 6 cham.

224
00:10:54,890 --> 00:10:57,620
Os oes gennym 7-elfen amrywiaeth a
rydym yn chwilio am y rhif 5.

225
00:10:57,620 --> 00:10:59,160
Gallai gymryd 7 cam.

226
00:10:59,160 --> 00:11:02,920
Wrth i ni ychwanegu un elfen fwy at ein
array, mae'n cymryd un cam mwy.

227
00:11:02,920 --> 00:11:06,750
Dyna algorithm llinol
yn y gwaethaf-achos.

228
00:11:06,750 --> 00:11:08,270
>> Cwpl gwestiynau cyflym i chi.

229
00:11:08,270 --> 00:11:11,170
Beth yw'r runtime-- beth sy'n
yr-achos gwaethaf runtime

230
00:11:11,170 --> 00:11:13,700
o hyn snippet arbennig o god?

231
00:11:13,700 --> 00:11:17,420
Felly mae gen i ddolen 4 yma sy'n rhedeg
o j yn dychwelyd 0, yr holl ffordd i fyny at m.

232
00:11:17,420 --> 00:11:21,980
A beth dw i'n gweld yma, yw bod y
corff y ddolen yn rhedeg mewn amser cyson.

233
00:11:21,980 --> 00:11:24,730
Felly ddefnyddio'r derminoleg y
rydym eisoes wedi siarad about-- beth

234
00:11:24,730 --> 00:11:29,390
fyddai y gwaethaf-achos
Rhedeg yr algorithm hwn?

235
00:11:29,390 --> 00:11:31,050
Cymerwch eiliad.

236
00:11:31,050 --> 00:11:34,270
Mae'r rhan fewnol y ddolen
yn rhedeg mewn amser cyson.

237
00:11:34,270 --> 00:11:37,510
A'r rhan allanol y
ddolen yn mynd i redeg amseroedd m.

238
00:11:37,510 --> 00:11:40,260
Felly beth yw'r Rhedeg waethaf yma?

239
00:11:40,260 --> 00:11:43,210
A wnaethoch chi ddyfalu fawr-O o'r m?

240
00:11:43,210 --> 00:11:44,686
Byddech yn iawn.

241
00:11:44,686 --> 00:11:46,230
>> Beth am un arall?

242
00:11:46,230 --> 00:11:48,590
Y tro hwn mae gennym
dolen tu mewn dolen.

243
00:11:48,590 --> 00:11:50,905
Mae gennym dolen allanol
sy'n rhedeg o sero i t.

244
00:11:50,905 --> 00:11:54,630
Ac mae gennym dolen mewnol sy'n rhedeg
o sero i p, ac y tu mewn o hynny,

245
00:11:54,630 --> 00:11:57,890
Yr wyf yn datgan bod y corff y
ddolen yn rhedeg mewn amser cyson.

246
00:11:57,890 --> 00:12:02,330
Felly beth yw'r Rhedeg gwaethaf-achos
o hyn snippet arbennig o god?

247
00:12:02,330 --> 00:12:06,140
Wel, unwaith eto, mae gennym
dolen allanol sy'n rhedeg amseroedd t.

248
00:12:06,140 --> 00:12:09,660
A phob iteriad adeg--
o'r ddolen, yn hytrach.

249
00:12:09,660 --> 00:12:13,170
Mae gennym dolen mewnol
hynny hefyd yn rhedeg amseroedd t.

250
00:12:13,170 --> 00:12:16,900
Ac yna y tu mewn o hynny, mae y
snippet bach adeg-- cyson yno.

251
00:12:16,900 --> 00:12:19,890
>> Felly, os oes gennym dolen allanol sy'n
yn rhedeg amseroedd p tu mewn sydd yn

252
00:12:19,890 --> 00:12:22,880
dolen mewnol sy'n
rhedeg p times-- hyn sy'n

253
00:12:22,880 --> 00:12:26,480
yr-achos gwaethaf runtime
o snippet hon o god?

254
00:12:26,480 --> 00:12:30,730
A wnaethoch chi ddyfalu fawr-O o p sgwâr?

255
00:12:30,730 --> 00:12:31,690
>> Rwy'n Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Mae hyn yn CS50.

257
00:12:33,880 --> 00:12:35,622