1
00:00:00,000 --> 00:00:05,726
>> [CHWARAE CERDDORIAETH]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: didoli Dethol yn
algorithm hynny, fel y byddech yn ei ddisgwyl,

3
00:00:08,600 --> 00:00:10,470
didoli'r set o elfennau.

4
00:00:10,470 --> 00:00:12,470
Ac algorithm adalw
yn set cam-wrth-gam

5
00:00:12,470 --> 00:00:15,260
o gyfarwyddiadau am gwblhau tasg.

6
00:00:15,260 --> 00:00:17,580
>> Yn dethol didoli'r
syniad sylfaenol yw hyn,

7
00:00:17,580 --> 00:00:22,080
ddod o hyd i'r elfen heb eu didoli lleiaf a
ychwanegu at ddiwedd y rhestr ddidoli.

8
00:00:22,080 --> 00:00:26,970
I bob pwrpas beth mae hyn yn ei wneud yw adeiladu
rhestr didoli, un elfen ar y tro.

9
00:00:26,970 --> 00:00:29,800
Torri i lawr i pseudocode
gallem ddatgan algorithm hwn

10
00:00:29,800 --> 00:00:34,490
fel a ganlyn, ailadrodd hyn nes
dim elfennau heb eu didoli yn parhau.

11
00:00:34,490 --> 00:00:38,660
Chwiliwch drwy'r heb eu didoli
data i ddarganfod gwerth lleiaf,

12
00:00:38,660 --> 00:00:44,130
Yna gyfnewid y gwerth lleiaf gyda'r
Elfen gyntaf y rhan heb eu didoli.

13
00:00:44,130 --> 00:00:47,130
>> Gallai fod o gymorth i ddychmygu hyn,
felly gadewch i ni edrych ar hyn.

14
00:00:47,130 --> 00:00:49,710
Felly, mae hyn, yr wyf yn dadlau, yn
amrywiaeth heb eu didoli ac rwyf wedi

15
00:00:49,710 --> 00:00:53,040
Nododd iddo gan nodi bod yr holl
o'r elfennau yn cael eu lliwio'n goch,

16
00:00:53,040 --> 00:00:54,420
Nid ydynt yn cael eu datrys eto.

17
00:00:54,420 --> 00:00:57,670
Mae hyn yn y cyfan
rhan heb eu didoli y rhesi.

18
00:00:57,670 --> 00:01:02,020
>> Felly gadewch i ni fynd drwy'r camau o
didoli dewis i ddatrys amrywiaeth hwn.

19
00:01:02,020 --> 00:01:05,296
Felly unwaith eto, rydym yn ailadrodd gonna
hyd nes nad oes elfennau heb eu didoli yn parhau.

20
00:01:05,296 --> 00:01:07,920
Rydym yn chwilio gonna drwy'r
data i ddarganfod gwerth lleiaf,

21
00:01:07,920 --> 00:01:11,990
ac yna cyfnewid y gwerth hwnnw gyda'r
Elfen gyntaf y rhan heb eu didoli.

22
00:01:11,990 --> 00:01:14,380
>> Ar hyn o bryd, unwaith eto, mae'r cyfan
amrywiaeth yw'r rhan heb eu didoli.

23
00:01:14,380 --> 00:01:16,534
Mae pob un o'r elfennau coch yn heb eu didoli.

24
00:01:16,534 --> 00:01:18,700
Felly, rydym yn chwilio drwy a
rydym yn dod o hyd i'r gwerth lleiaf.

25
00:01:18,700 --> 00:01:20,533
Rydym yn dechrau ar y dechrau,
rydym yn mynd at y diwedd,

26
00:01:20,533 --> 00:01:23,630
rydym yn dod o hyd i'r gwerth lleiaf yw, un.

27
00:01:23,630 --> 00:01:24,860
Felly mae hynny'n rhan un.

28
00:01:24,860 --> 00:01:29,440
Ac yna rhan dau, gyfnewid y gwerth hwnnw gyda
yr elfen gyntaf y rhan heb eu didoli,

29
00:01:29,440 --> 00:01:31,340
neu yr elfen goch cyntaf.

30
00:01:31,340 --> 00:01:34,980
>> Yn yr achos hwn a fyddai'n cael ei
pump, felly rydym yn gyfnewid un a phump.

31
00:01:34,980 --> 00:01:37,320
Pan fyddwn yn gwneud hyn, y gallwn
ar eu golwg yn gweld bod rydym wedi

32
00:01:37,320 --> 00:01:41,260
Symudodd yr elfen lleiaf gwerthfawr
y rhesi, i'r cychwyn cyntaf.

33
00:01:41,260 --> 00:01:43,920
Didoli yr elfen honno yn effeithiol.

34
00:01:43,920 --> 00:01:47,520
>> Ac felly y gallwn ni wir gadarnhau
ac yn datgan fod un, yn cael ei datrys.

35
00:01:47,520 --> 00:01:52,080
Ac felly byddwn yn dangos y rhan didoli
o'n array, trwy liwio ei las.

36
00:01:52,080 --> 00:01:53,860
>> Nawr rydym yn unig ailadrodd y broses eto.

37
00:01:53,860 --> 00:01:57,430
Rydym yn chwilio drwy'r rhan heb eu didoli o
yr amrywiaeth i ddod o hyd i'r elfen lleiaf.

38
00:01:57,430 --> 00:01:59,000
Yn yr achos hwn, mae'n ddau.

39
00:01:59,000 --> 00:02:02,100
>> Rydym yn cyfnewid bod gyda'r cyntaf
elfen o'r rhan heb eu didoli.

40
00:02:02,100 --> 00:02:05,540
Yn yr achos dau hefyd yn digwydd bod
yr elfen gyntaf y rhan heb eu didoli.

41
00:02:05,540 --> 00:02:08,650
Felly, rydym yn gyfnewid dau gyda ei hun,
sydd mewn gwirionedd dim ond yn gadael dau

42
00:02:08,650 --> 00:02:11,257
lle y mae, ac mae'n datrys.

43
00:02:11,257 --> 00:02:13,840
Gan barhau ymlaen, rydym yn chwilio drwy'r
i ddod o hyd i'r elfen lleiaf.

44
00:02:13,840 --> 00:02:15,030
Mae'n tri.

45
00:02:15,030 --> 00:02:17,650
Rydym yn cyfnewid gyda'r cyntaf
elfen, sef pump.

46
00:02:17,650 --> 00:02:19,450
Ac yn awr dri cael ei drefnu.

47
00:02:19,450 --> 00:02:22,440
>> Rydym yn chwilio drwy unwaith eto, ac yr ydym yn
ddod o hyd i'r elfen lleiaf yw pedwar.

48
00:02:22,440 --> 00:02:28,070
Rydym yn cyfnewid 'i ag yr elfen gyntaf y
rhan heb eu didoli, ac yn awr bedwar yn cael ei sortio.

49
00:02:28,070 --> 00:02:29,910
>> Rydym yn canfod bod bump oed yn
yr elfen lleiaf.

50
00:02:29,910 --> 00:02:32,900
Rydym yn cyfnewid gyda'r cyntaf
elfen o'r rhan heb eu didoli.

51
00:02:32,900 --> 00:02:34,740
Ac yn awr bump yn didoli.

52
00:02:34,740 --> 00:02:36,660
>> Ac yna yn olaf, mae ein
rhan heb eu didoli yn cynnwys

53
00:02:36,660 --> 00:02:38,576
o ddim ond un elfen,
felly rydym yn chwilio drwy

54
00:02:38,576 --> 00:02:41,740
a gwelwn fod chwech yw'r
lleiaf, ac mewn gwirionedd, dim ond elfen.

55
00:02:41,740 --> 00:02:44,906
Ac yna gallwn ddweud ei fod yn datrys.

56
00:02:44,906 --> 00:02:47,530
Ac yn awr rydym wedi newid ein array
rhag cael eu heb eu didoli yn gyfan gwbl

57
00:02:47,530 --> 00:02:52,660
mewn coch, er mwyn didoli yn gyfan gwbl
mewn glas, gan ddefnyddio didoli dewis.

58
00:02:52,660 --> 00:02:54,920
>> Felly beth yw'r sefyllfa waethaf yma?

59
00:02:54,920 --> 00:02:57,830
Yn dda yn y gwaethaf absoliwt
achos, mae'n rhaid i ni edrych drosodd

60
00:02:57,830 --> 00:03:02,170
holl elfennau y rhesi i
ddod o hyd i'r elfen heb eu didoli lleiaf,

61
00:03:02,170 --> 00:03:04,750
ac mae'n rhaid i ni ailadrodd
y broses hon n amser.

62
00:03:04,750 --> 00:03:09,090
Unwaith ar gyfer pob elfen o'r casgliad
oherwydd ein bod yn unig, yn y algorithm hwn,

63
00:03:09,090 --> 00:03:12,180
didoli un elfen ar pryd.

64
00:03:12,180 --> 00:03:13,595
>> Beth yw'r senario achos gorau?

65
00:03:13,595 --> 00:03:15,040
Wel mae'n union yr un fath, dde?

66
00:03:15,040 --> 00:03:18,440
Mae gennym mewn gwirionedd yn dal i gamu drwy
pob elfen unigol y rhesi

67
00:03:18,440 --> 00:03:22,040
er mwyn cadarnhau ei fod,
mewn gwirionedd, yr elfen lleiaf.

68
00:03:22,040 --> 00:03:26,760
>> Felly mae'r Rhedeg achos gwaethaf, yr ydym
rhaid ailadrodd broses n amserau,

69
00:03:26,760 --> 00:03:28,960
unwaith ar gyfer pob un o'r elfennau n.

70
00:03:28,960 --> 00:03:31,940
Ac yn y senario achos gorau,
mae'n rhaid i ni wneud yr un peth.

71
00:03:31,940 --> 00:03:35,340
>> Felly meddwl yn ôl at ein
blwch offer cymhlethdod cyfrifiadurol,

72
00:03:35,340 --> 00:03:39,250
beth yn eich barn chi yn y gwaethaf
Rhedeg achos dros fath dethol?

73
00:03:39,250 --> 00:03:41,840
Beth yn eich barn chi yw'r gorau
Rhedeg achos dros fath dethol?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> A wnaethoch chi ddyfalu Big O n sgwâr,
a Big Omega o n sgwâr?

76
00:03:49,325 --> 00:03:49,950
Byddech yn iawn.

77
00:03:49,950 --> 00:03:52,490
Mae'r rhai yn cael eu, mewn gwirionedd, y
achos gwaethaf a rhedeg achos gorau

78
00:03:52,490 --> 00:03:55,100
adegau, ar gyfer y math dethol.

79
00:03:55,100 --> 00:03:56,260
>> Rwy'n Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Mae hyn yn CS50.

81
00:03:58,600 --> 00:04:00,279