1
00:00:00,000 --> 00:00:03,360
>> [CHWARAE CERDDORIAETH]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: pob hawl, felly
didoli swigen yn algorithm

4
00:00:06,730 --> 00:00:08,730
gallwch ei ddefnyddio i ddatrys cyfres o elfennau.

5
00:00:08,730 --> 00:00:10,850
Gadewch i ni edrych ar sut y mae'n gweithio.

6
00:00:10,850 --> 00:00:13,240
>> Felly, y syniad sylfaenol y tu ôl
math swigen yn hyn.

7
00:00:13,240 --> 00:00:17,340
Rydym yn gyffredinol yn awyddus i symud yn uwch
elfennau gwerthfawr yn gyffredinol ar y dde,

8
00:00:17,340 --> 00:00:20,340
ac yn is elfennau gwerthfawr yn gyffredinol
ar y chwith, fel y byddem yn ei ddisgwyl.

9
00:00:20,340 --> 00:00:23,256
Rydym am i'r pethau isaf i fod ar
y dechrau, a'r pethau uwch

10
00:00:23,256 --> 00:00:24,970
i fod ar y diwedd.

11
00:00:24,970 --> 00:00:26,130
>> Sut ydym ni'n gwneud hyn?

12
00:00:26,130 --> 00:00:28,040
Yn dda yn y cod pseudocode,
gallem ddweud, gadewch i ni

13
00:00:28,040 --> 00:00:30,320
gosod cownter cyfnewid at werth nad yw'n sero.

14
00:00:30,320 --> 00:00:32,570
Cawn weld pam rydym yn gwneud hynny mewn eiliad.

15
00:00:32,570 --> 00:00:36,090
Ac yna rydym yn ailadrodd y canlynol
broses nes bod y cownter cyfnewid yn 0,

16
00:00:36,090 --> 00:00:39,910
neu hyd nes y byddwn yn gwneud unrhyw gyfnewidiadau o gwbl.

17
00:00:39,910 --> 00:00:43,170
>> Ailosod y cownter cyfnewid i
0 os nad yw'n barod 0.

18
00:00:43,170 --> 00:00:46,420
Yna edrych ar bob
pâr cyfagos o elfennau.

19
00:00:46,420 --> 00:00:49,550
Os bydd y ddwy elfen yn
Nid yw mewn trefn, cyfnewid nhw,

20
00:00:49,550 --> 00:00:51,620
ac yn ychwanegu 1 i'r cownter cyfnewid.

21
00:00:51,620 --> 00:00:53,870
Os ydych chi'n meddwl am
hyn cyn i chi ddychmygu iddo,

22
00:00:53,870 --> 00:00:57,471
yn sylwi y bydd hyn yn symud yn is
elfennau gwerthfawr i'r chwith

23
00:00:57,471 --> 00:01:00,720
ac elfennau ar y dde gwerthfawr uwch,
wneud yn effeithiol yr hyn yr ydym am ei wneud,

24
00:01:00,720 --> 00:01:03,940
sydd yn symud grwpiau hynny
o elfennau yn y ffordd honno.

25
00:01:03,940 --> 00:01:07,035
Gadewch i ddychmygu sut mae hyn yn
Gallai edrych ddefnyddio ein amrywiaeth

26
00:01:07,035 --> 00:01:10,504
ein bod yn eu defnyddio i brofi
allan algorithmau hyn.

27
00:01:10,504 --> 00:01:13,420
Mae gennym amrywiaeth heb ei ddidoli yma unwaith eto,
a nodir gan bob un o'r elfennau

28
00:01:13,420 --> 00:01:14,840
bod mewn coch.

29
00:01:14,840 --> 00:01:17,970
Ac yr wyf yn gosod fy cownter cyfnewid
at werth nonzero.

30
00:01:17,970 --> 00:01:20,610
Yr wyf yn fympwyol dewis
negyddol 1-- nid yw'n 0.

31
00:01:20,610 --> 00:01:23,840
Rydym yn awyddus i ailadrodd y broses hon
nes bod y cownter cyfnewid yw 0.

32
00:01:23,840 --> 00:01:26,540
Dyma pam yr wyf yn gosod fy cyfnewid
groes i ryw werth heb fod yn sero,

33
00:01:26,540 --> 00:01:29,400
oherwydd fel arall y
Byddai cownter gyfnewid fod yn 0.

34
00:01:29,400 --> 00:01:31,610
Ni fyddem yn hyd yn oed yn dechrau ar y
proses y algorithm.

35
00:01:31,610 --> 00:01:33,610
Felly eto, y camau yw--
ailosod y cownter cyfnewid

36
00:01:33,610 --> 00:01:37,900
i 0, ac yna edrych ar bob cyfagos
pâr, ac os ydyn nhw allan o drefn,

37
00:01:37,900 --> 00:01:40,514
cyfnewid nhw, ac yn ychwanegu 1
at y cownter cyfnewid.

38
00:01:40,514 --> 00:01:41,680
Felly gadewch i ni ddechrau y broses hon.

39
00:01:41,680 --> 00:01:44,430
Felly, y peth cyntaf yr ydym yn ei wneud yw
rydym yn gosod y cownter cyfnewid i 0,

40
00:01:44,430 --> 00:01:46,660
ac yna rydym yn dechrau edrych
ym mhob pâr cyfagos.

41
00:01:46,660 --> 00:01:49,140
>> Felly, rydym yn gyntaf dechrau edrych ar 5 a 2.

42
00:01:49,140 --> 00:01:52,410
Rydym yn gweld eu bod allan o
archebu ac felly rydym yn eu cyfnewid.

43
00:01:52,410 --> 00:01:53,830
Ac rydym yn ychwanegu 1 i'r cownter cyfnewid.

44
00:01:53,830 --> 00:01:57,860
Felly nawr ein cownter cyfnewid yw 1,
a 2 a 5 wedi cael eu diffodd.

45
00:01:57,860 --> 00:01:59,370
Nawr rydym yn ailadrodd y broses eto.

46
00:01:59,370 --> 00:02:03,540
>> Rydym yn edrych ar y pâr cyfagos nesaf,
5 a 1-- maen nhw hefyd allan o drefn,

47
00:02:03,540 --> 00:02:06,960
felly rydym yn eu cyfnewid ac ychwanegu
1 i'r cownter cyfnewid.

48
00:02:06,960 --> 00:02:08,900
Yna, rydym yn edrych ar 5 a 3.

49
00:02:08,900 --> 00:02:13,830
Maent yn cael eu allan o drefn, felly rydym yn gyfnewid
iddynt ac rydym yn ychwanegu 1 i'r cownter cyfnewid.

50
00:02:13,830 --> 00:02:15,550
Yna, rydym yn edrych ar 5 a 6.

51
00:02:15,550 --> 00:02:18,630
Maen nhw mewn trefn, felly nid ydym yn ei wneud mewn gwirionedd
Mae angen i gyfnewid unrhyw beth y tro hwn.

52
00:02:18,630 --> 00:02:20,250
Yna, rydym yn edrych ar 6 a 4.

53
00:02:20,250 --> 00:02:24,920
Maen nhw hefyd allan o drefn, felly rydym yn gyfnewid
iddynt ac rydym yn ychwanegu 1 i'r cownter cyfnewid.

54
00:02:24,920 --> 00:02:26,230
>> Nawr sylwi ar yr hyn sydd wedi digwydd.

55
00:02:26,230 --> 00:02:29,514
Rydym wedi symud 6 yr holl ffordd i'r diwedd.

56
00:02:29,514 --> 00:02:32,180
Felly, yn y math dewis, os ydych chi wedi
gweld bod fideo, yr hyn a wnaethom oedd

57
00:02:32,180 --> 00:02:35,290
rydym yn dod i ben i fyny yn symud y
elfennau lleiaf yn adeilad

58
00:02:35,290 --> 00:02:39,640
yr amrywiaeth ddidoli yn y bôn o
o'r chwith i'r dde, o'r lleiaf i'r mwyaf.

59
00:02:39,640 --> 00:02:43,200
Yn achos math swigen, os ydym yn
yn dilyn hyn algorithm penodol,

60
00:02:43,200 --> 00:02:46,720
rydym yn mewn gwirionedd yn mynd i gael ei adeiladu
yr amrywiaeth ddidoli o'r dde

61
00:02:46,720 --> 00:02:49,100
i'r chwith, mwyaf i'r lleiaf.

62
00:02:49,100 --> 00:02:53,840
Rydym wedi bubbled 6, mae'r effeithiol
gwerth mwyaf, yr holl ffordd hyd y diwedd.

63
00:02:53,840 --> 00:02:56,165
>> Ac felly y gallwn ddatgan yn awr
bod hynny'n cael ei ddidoli,

64
00:02:56,165 --> 00:02:59,130
ac yn y dyfodol iterations--
mynd drwy'r llu again--

65
00:02:59,130 --> 00:03:01,280
Nid oes rhaid i ni ystyried 6 anymore.

66
00:03:01,280 --> 00:03:03,850
Dim ond i ni ystyried
yr elfennau heb eu didoli

67
00:03:03,850 --> 00:03:06,299
pan fyddwn yn edrych ar barau cyfagos.

68
00:03:06,299 --> 00:03:08,340
Felly rydym wedi gorffen un
mynd trwy fath swigen.

69
00:03:08,340 --> 00:03:11,941
Felly nawr rydym yn mynd yn ôl at y cwestiwn,
ailadrodd nes bod y cownter cyfnewid yw 0.

70
00:03:11,941 --> 00:03:13,690
Wel y cownter cyfnewid
yw 4, felly rydym yn mynd

71
00:03:13,690 --> 00:03:15,410
i gadw ailadrodd y broses hon eto.

72
00:03:15,410 --> 00:03:19,180
>> Rydym yn mynd i ailosod y cownter cyfnewid
i 0, ac yn edrych ar bob pâr cyfagos.

73
00:03:19,180 --> 00:03:21,890
Felly, rydym yn dechrau gyda 2 a 1-- eu bod
allan o drefn, felly rydym yn eu gyfnewid

74
00:03:21,890 --> 00:03:23,620
ac rydym yn ychwanegu 1 i'r cownter cyfnewid.

75
00:03:23,620 --> 00:03:25,490
2 a 3, eu bod mewn trefn.

76
00:03:25,490 --> 00:03:27,060
Nid oes angen i ni wneud unrhyw beth.

77
00:03:27,060 --> 00:03:28,420
3 a 5 mewn trefn.

78
00:03:28,420 --> 00:03:30,150
Nid oes angen i ni wneud unrhyw beth yno.

79
00:03:30,150 --> 00:03:32,515
>> 5 a 4, maent yn cael eu allan
o drefn, ac felly rydym yn

80
00:03:32,515 --> 00:03:35,130
Mae angen i gyfnewid nhw ac ychwanegu
1 i'r cownter cyfnewid.

81
00:03:35,130 --> 00:03:38,880
Ac yn awr rydym wedi symud 5,
yr elfen fwyaf nesaf,

82
00:03:38,880 --> 00:03:40,920
hyd at ddiwedd y gyfran heb eu didoli.

83
00:03:40,920 --> 00:03:44,360
Felly, gallwn yn awr yn galw hynny
rhan o'r gyfran didoli.

84
00:03:44,360 --> 00:03:47,180
>> Nawr eich bod yn edrych ar y
sgrin ac yn ôl pob tebyg yn gallu dweud,

85
00:03:47,180 --> 00:03:50,130
ag y gallaf, fod yr amrywiaeth
yn cael ei datrys ar hyn o bryd.

86
00:03:50,130 --> 00:03:51,820
Ond ni allwn brofi hynny eto.

87
00:03:51,820 --> 00:03:54,359
Nid oes gennym warant
ei fod yn datrys.

88
00:03:54,359 --> 00:03:56,900
Ond dyma lle mae'r cyfnewid
cownter yn mynd i ddod i chwarae.

89
00:03:56,900 --> 00:03:59,060
>> Felly rydym wedi cwblhau tocyn.

90
00:03:59,060 --> 00:04:00,357
Mae'r cownter cyfnewid yw 2.

91
00:04:00,357 --> 00:04:02,190
Felly rydym yn mynd i ailadrodd
y broses hon eto,

92
00:04:02,190 --> 00:04:04,290
ailadrodd nes bod y cownter cyfnewid yw 0.

93
00:04:04,290 --> 00:04:05,550
Ailosod y cownter cyfnewid i 0.

94
00:04:05,550 --> 00:04:06,820
Felly byddwn yn ei ailosod.

95
00:04:06,820 --> 00:04:09,810
>> Nawr edrychwch ar bob pâr cyfagos.

96
00:04:09,810 --> 00:04:11,880
Dyna mewn trefn, 1 a 2.

97
00:04:11,880 --> 00:04:13,590
2 a 3 yn eu trefn.

98
00:04:13,590 --> 00:04:15,010
3 a 4 mewn trefn.

99
00:04:15,010 --> 00:04:19,250
Felly, yn y fan hon, yn sylwi ein bod wedi cwblhau
edrych ar bob pâr cyfagos,

100
00:04:19,250 --> 00:04:22,530
ond y cownter cyfnewid yn dal i fod 0.

101
00:04:22,530 --> 00:04:25,520
>> Os nad oes gennym i newid
unrhyw elfennau, yna maent

102
00:04:25,520 --> 00:04:28,340
rhaid iddo fod mewn trefn, gan
yn rhinwedd y broses hon.

103
00:04:28,340 --> 00:04:32,000
Ac felly effeithlonrwydd o ryw fath,
y mae gwyddonwyr yr ydym cyfrifiadur caru,

104
00:04:32,000 --> 00:04:35,560
yn y gallwn ddatgan yn awr
rhaid i'r amrywiaeth cyfan

105
00:04:35,560 --> 00:04:38,160
eu didoli, oherwydd nid ydym yn gwneud
rhaid i gyfnewid unrhyw elfennau.

106
00:04:38,160 --> 00:04:40,380
Dyna 'n bert' n glws.

107
00:04:40,380 --> 00:04:43,260
>> Felly beth yw'r achos gwaethaf
senario gyda'r math swigen?

108
00:04:43,260 --> 00:04:46,240
Yn yr achos gwaethaf yr amrywiaeth yn
er mwyn gwbl cefn,

109
00:04:46,240 --> 00:04:49,870
ac felly mae'n rhaid i bob swigen
o'r elfennau mawr i gyd

110
00:04:49,870 --> 00:04:51,780
y ffordd ar draws y rhesi.

111
00:04:51,780 --> 00:04:55,350
Ac mae gennym hefyd effeithiol i
swigen holl elfennau bach yn ôl

112
00:04:55,350 --> 00:04:57,050
yr holl ffordd ar draws yr amrywiaeth, hefyd.

113
00:04:57,050 --> 00:05:01,950
Felly, mae pob un o'r elfennau n yn gorfod symud
ar draws pob un o'r elfennau n arall.

114
00:05:01,950 --> 00:05:04,102
Felly dyna y senario achos gwaethaf.

115
00:05:04,102 --> 00:05:05,810
Yn yr achos gorau
senario fodd bynnag, mae hyn yn

116
00:05:05,810 --> 00:05:07,880
ychydig yn wahanol fath dethol.

117
00:05:07,880 --> 00:05:10,040
Mae'r amrywiaeth yn barod
datrys pan fyddwn yn mynd i mewn.

118
00:05:10,040 --> 00:05:12,550
Nid oes rhaid i ni wneud unrhyw
cyfnewidiadau ar y tocyn cyntaf.

119
00:05:12,550 --> 00:05:14,940
Felly gallai fod yn rhaid inni edrych
yn llai o elfennau, dde?

120
00:05:14,940 --> 00:05:18,580
Nid oes rhaid i ni ailadrodd hyn
prosesu sawl gwaith drosodd.

121
00:05:18,580 --> 00:05:19,540
>> Felly beth mae hynny'n ei olygu?

122
00:05:19,540 --> 00:05:22,390
Felly beth yw'r sefyllfa waethaf
ar gyfer y math swigod, a beth sy'n

123
00:05:22,390 --> 00:05:25,330
y senario achos gorau ar gyfer y math swigen?

124
00:05:25,330 --> 00:05:27,770
A wnaethoch chi ddyfalu hyn?

125
00:05:27,770 --> 00:05:32,420
Yn yr achos gwaethaf yn rhaid i chi ailadrodd
ar draws yr holl elfennau n amserau n.

126
00:05:32,420 --> 00:05:34,220
Felly yr achos gwaethaf ei sgwâr n.

127
00:05:34,220 --> 00:05:36,550
>> Os yw'r amrywiaeth yn berffaith
ddidoli fodd bynnag, dim ond

128
00:05:36,550 --> 00:05:38,580
rhaid i ni edrych ar bob
o'r elfennau unwaith.

129
00:05:38,580 --> 00:05:42,670
Ac os y cownter cyfnewid yn dal i fod 0,
gallwch ddweud amrywiaeth hwn yn cael ei datrys.

130
00:05:42,670 --> 00:05:45,780
Ac felly yn yr achos gorau, mae hyn yn
mewn gwirionedd yn well na ddethol

131
00:05:45,780 --> 00:05:49,230
sort-- mae'n omega o n.

132
00:05:49,230 --> 00:05:50,270
>> Rwy'n Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Mae hyn yn CS50.

134
00:05:52,140 --> 00:05:54,382