1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Gadewch i ni edrych ar fath dethol, algorithm

2
00:00:09,980 --> 00:00:12,800
ar gyfer cymryd rhestr o rifau a didoli nhw.

3
00:00:12,800 --> 00:00:15,750
Mae algorithm, cofiwch, yn syml, gam-wrth-gam

4
00:00:15,750 --> 00:00:18,370
weithdrefn ar gyfer cyflawni'r dasg.

5
00:00:18,370 --> 00:00:21,470
Y syniad sylfaenol y tu ôl math ddethol hon yw rhannu

6
00:00:21,470 --> 00:00:23,390
ein rhestr yn ddau ddogn -

7
00:00:23,390 --> 00:00:26,810
cyfran didoli a chyfran heb eu didoli.

8
00:00:26,810 --> 00:00:30,200
Ym mhob cam o'r algorithm, mae nifer yn cael ei symud o'r

9
00:00:30,200 --> 00:00:33,800
cyfran heb eu didoli i'r gyfran didoli tan y pen draw

10
00:00:33,800 --> 00:00:35,880
rhestr gyfan yn cael ei datrys.

11
00:00:35,880 --> 00:00:38,510
Felly, dyma restr o chwe rhif -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, a 15.

13
00:00:44,010 --> 00:00:47,680
Ar hyn o bryd mae'r rhestr gyfan yn cael ei ystyried heb eu gwahanu.

14
00:00:47,680 --> 00:00:51,770
Hyd yn oed er y gall nifer tebyg i 16 eisoes fod yn ei gywir

15
00:00:51,770 --> 00:00:56,040
lleoliad, mae ein algorithm nid oes ffordd o wybod hynny tan y

16
00:00:56,040 --> 00:00:57,980
rhestr gyfan yn cael ei datrys.

17
00:00:57,980 --> 00:01:01,355
Felly, byddwn yn ystyried pob rhif i gael eu heb eu didoli nes i ni ddatrys

18
00:01:01,355 --> 00:01:03,800
ein hunain.

19
00:01:03,800 --> 00:01:06,890
Rydym yn gwybod ein bod am i'r rhestr fod yn nhrefn esgynnol.

20
00:01:06,890 --> 00:01:10,200
Felly, byddwn yn awyddus i adeiladu i fyny y rhan datrys ein rhestr

21
00:01:10,200 --> 00:01:13,280
o'r chwith i'r dde, o'r lleiaf i'r mwyaf.

22
00:01:13,280 --> 00:01:17,970
I wneud hynny, bydd angen i ni ddod o hyd i'r elfen heb ei threfnu o leiaf

23
00:01:17,970 --> 00:01:21,350
ac yn ei roi ar ddiwedd y rhan didoli.

24
00:01:21,350 --> 00:01:25,370
Gan nad yw'r rhestr hon yn cael ei ddatrys, yr unig ffordd i wneud hynny yw

25
00:01:25,370 --> 00:01:29,330
edrych ar bob elfen yn y gyfran heb eu didoli, cofio

26
00:01:29,330 --> 00:01:32,010
pa elfen yw'r isaf a chymharu

27
00:01:32,010 --> 00:01:33,770
pob elfen i hynny.

28
00:01:33,770 --> 00:01:36,150
Felly, byddwn yn edrych yn gyntaf ar y 23.

29
00:01:36,150 --> 00:01:38,650
Dyma'r elfen gyntaf rydym wedi gweld, felly byddwn yn cofio

30
00:01:38,650 --> 00:01:40,050
fel y lleiafswm.

31
00:01:40,050 --> 00:01:42,320
Nesaf byddwn yn edrych ar 42.

32
00:01:42,320 --> 00:01:46,720
42 yn fwy na 23, felly 23 yn dal i fod y lleiaf.

33
00:01:46,720 --> 00:01:51,210
Yn dilyn hynny y 4 sydd yn llai na 23, felly byddwn yn cofio 4

34
00:01:51,210 --> 00:01:52,880
fel yr isafswm newydd.

35
00:01:52,880 --> 00:01:56,380
Nesaf yn 16 sy'n fwy na 4, hynny 4

36
00:01:56,380 --> 00:01:57,980
yn dal i fod y lleiaf.

37
00:01:57,980 --> 00:02:03,670
8 yn fwy na 4, a 15 yn fwy na 4, felly mae'n rhaid 4 yn

38
00:02:03,670 --> 00:02:05,980
yr elfen lleiaf heb eu didoli.

39
00:02:05,980 --> 00:02:09,350
Felly hyd yn oed er, fel bodau dynol, gallwn ar unwaith weld bod 4 yn

40
00:02:09,350 --> 00:02:12,300
yr elfen lleiaf, ein algorithm angen i edrych ar

41
00:02:12,300 --> 00:02:15,710
bob elfen heb eu didoli, hyd yn oed ar ôl i ni wedi dod o hyd i'r 4 - y

42
00:02:15,710 --> 00:02:16,860
elfen lleiaf.

43
00:02:16,860 --> 00:02:19,900
Felly nawr ein bod wedi dod o hyd i'r elfen lleiaf, 4, byddwn eisiau

44
00:02:19,900 --> 00:02:23,410
i symud i mewn i'r gyfran datrys y rhestr.

45
00:02:23,410 --> 00:02:27,320
Gan fod hyn yw'r cam cyntaf, mae hyn yn golygu ein bod eisiau rhoi 4 yn

46
00:02:27,320 --> 00:02:29,680
ddechrau'r rhestr.

47
00:02:29,680 --> 00:02:33,040
Ar hyn o bryd 23 yw ar ddechrau'r rhestr, felly

48
00:02:33,040 --> 00:02:36,080
gadewch i ni gyfnewid y 4 a'r 23.

49
00:02:36,080 --> 00:02:38,870
Felly nawr ein rhestr yn edrych fel hyn.

50
00:02:38,870 --> 00:02:42,710
Rydym yn gwybod bod yn rhaid i 4 fod ar ei lleoliad terfynol, oherwydd ei fod yn

51
00:02:42,710 --> 00:02:45,890
yr elfen lleiaf a'r elfen ar y dechrau

52
00:02:45,890 --> 00:02:46,960
y rhestr.

53
00:02:46,960 --> 00:02:50,650
Felly, mae hyn yn golygu nad ydym byth angen i symud eto.

54
00:02:50,650 --> 00:02:53,910
Felly, gadewch i ni ailadrodd y broses hon i ychwanegu elfen arall at y

55
00:02:53,910 --> 00:02:55,910
cyfran datrys y rhestr.

56
00:02:55,910 --> 00:02:58,950
Rydym yn gwybod nad oes angen i ni edrych ar y 4, oherwydd ei fod yn

57
00:02:58,950 --> 00:03:00,000
datrys eisoes.

58
00:03:00,000 --> 00:03:03,540
Felly, gallwn ddechrau ar y 42, y byddwn yn ei gofio fel y

59
00:03:03,540 --> 00:03:05,290
elfen lleiaf.

60
00:03:05,290 --> 00:03:08,700
Felly nesaf, byddwn yn edrych ar y 23 sydd yn llai na 42, felly rydym yn

61
00:03:08,700 --> 00:03:11,620
cofio 23 yw isafswm newydd.

62
00:03:11,620 --> 00:03:14,870
Nesaf rydym yn gweld y 16 sydd i fod yn llai na 23, felly

63
00:03:14,870 --> 00:03:16,800
16 oed yw'r isafswm newydd.

64
00:03:16,800 --> 00:03:19,720
Nawr rydym yn edrych ar y 8 sy'n llai na 16, felly

65
00:03:19,720 --> 00:03:21,130
8 yn yr isafswm newydd.

66
00:03:21,130 --> 00:03:25,900
Ac yn olaf 8 yn llai na 15, felly rydym yn gwybod bod 8 yn o leiaf

67
00:03:25,900 --> 00:03:27,780
elfen heb eu didoli.

68
00:03:27,780 --> 00:03:30,660
Felly mae hynny'n golygu y dylem atodi 8 i ddatrys

69
00:03:30,660 --> 00:03:32,450
gyfran o'r rhestr.

70
00:03:32,450 --> 00:03:35,990
Ar hyn o bryd 4 yw'r elfen didoli yn unig, felly mae arnom eisiau rhoi

71
00:03:35,990 --> 00:03:38,410
nesaf 8 i'r 4.

72
00:03:38,410 --> 00:03:41,920
Ers 42 yn yr elfen gyntaf yn y rhan heb eu didoli y

73
00:03:41,920 --> 00:03:47,260
rhestr, byddwn yn awyddus i gyfnewid y 42 a'r 8.

74
00:03:47,260 --> 00:03:49,680
Felly nawr ein rhestr yn edrych fel hyn.

75
00:03:49,680 --> 00:03:53,830
4 ac 8 yn cynrychioli'r gyfran datrys y rhestr, ac mae'r

76
00:03:53,830 --> 00:03:56,440
niferoedd sy'n weddill yn cynrychioli'r heb eu didoli

77
00:03:56,440 --> 00:03:58,260
gyfran o'r rhestr.

78
00:03:58,260 --> 00:04:00,630
Felly, gadewch i ni barhau â'r fersiwn arall.

79
00:04:00,630 --> 00:04:03,850
Rydym yn dechrau gyda 23 y tro hwn, gan nad oes angen i ni edrych ar

80
00:04:03,850 --> 00:04:05,770
y 4 ac 8 anymore oherwydd maent wedi

81
00:04:05,770 --> 00:04:07,660
eisoes wedi cael ei datrys.

82
00:04:07,660 --> 00:04:10,270
16 yn llai na 23, felly byddwn yn cofio

83
00:04:10,270 --> 00:04:12,070
16 fel yr isafswm newydd.

84
00:04:12,070 --> 00:04:18,149
16 yn llai na 42, ond 15 yn llai na 16, felly mae'n rhaid 15 fod yn

85
00:04:18,149 --> 00:04:20,480
yr elfen heb ei threfnu o leiaf.

86
00:04:20,480 --> 00:04:24,580
Felly, nawr rydym am i gyfnewid y 15 a'r 23 i

87
00:04:24,580 --> 00:04:26,310
yn rhoi i ni y rhestr hon.

88
00:04:26,310 --> 00:04:30,500
Mae'r rhan datrys y rhestr yn cynnwys 4, 8 a 15 oed, a

89
00:04:30,500 --> 00:04:33,210
elfennau hyn yn cael eu heb eu didoli o hyd.

90
00:04:33,210 --> 00:04:36,900
Ond dim ond fel y digwydd bod yr elfen heb ei threfnu nesaf, 16,

91
00:04:36,900 --> 00:04:38,480
cael ei drefnu yn barod.

92
00:04:38,480 --> 00:04:42,060
Fodd bynnag, does dim ffordd ar gyfer ein algorithm i wybod fod 16

93
00:04:42,060 --> 00:04:45,230
eisoes yn ei lleoliad cywir, felly rydym yn dal angen i ni

94
00:04:45,230 --> 00:04:47,870
ailadrodd yn union yr un broses.

95
00:04:47,870 --> 00:04:53,750
Felly rydym yn gweld bod 16 yn llai na 42, a 16 yn llai na 23, felly

96
00:04:53,750 --> 00:04:56,230
16 Rhaid fod yr elfen lleiaf.

97
00:04:56,230 --> 00:04:59,010
Mae'n amhosibl i gyfnewid yr elfen hon gyda ei hun, fel y gallwn

98
00:04:59,010 --> 00:05:01,780
dim ond ei adael yn y lleoliad hwn.

99
00:05:01,780 --> 00:05:04,660
Felly, mae angen pasio un yn fwy o'n algorithm.

100
00:05:04,660 --> 00:05:09,370
42 yn fwy na 23, felly mae'n rhaid i 23 fydd y

101
00:05:09,370 --> 00:05:10,970
elfen lleiaf heb eu didoli.

102
00:05:10,970 --> 00:05:17,410
Unwaith y byddwn yn cyfnewid y 23 a'r 42, rydym yn y pen draw ein terfynol

103
00:05:17,410 --> 00:05:18,530
rhestr datrys -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Rydym yn gwybod bod yn rhaid 42 fod yn y lle cywir gan ei fod yn y

106
00:05:26,830 --> 00:05:30,210
gadael elfen yn unig, ac mae hynny'n fath dethol.

107
00:05:30,210 --> 00:05:32,100
Gadewch i ni bellach yn ffurfioli ein algorithm gyda rhai

108
00:05:32,100 --> 00:05:34,540
pseudocode.

109
00:05:34,540 --> 00:05:37,760
Ar-lein un, gallwn weld bod angen i integreiddio dros

110
00:05:37,760 --> 00:05:39,530
pob elfen o'r rhestr.

111
00:05:39,530 --> 00:05:42,150
Heblaw y elfen olaf, gan fod y elfen 1

112
00:05:42,150 --> 00:05:44,230
rhestr yn cael ei datrys eisoes.

113
00:05:44,230 --> 00:05:48,100
Ar-lein dau, rydym yn ystyried yr elfen gyntaf y heb eu didoli

114
00:05:48,100 --> 00:05:51,080
gyfran o'r rhestr i fod y safon gofynnol, fel y gwnaethom gyda'n

115
00:05:51,080 --> 00:05:53,750
enghraifft, felly mae gennym rywbeth i gymharu.

116
00:05:53,750 --> 00:05:57,260
Llinell tri yn dechrau dolen ail yr ydym yn ailadrodd dros

117
00:05:57,260 --> 00:05:59,170
bob elfen heb eu didoli.

118
00:05:59,170 --> 00:06:02,150
Rydym yn gwybod bod ar ôl i iteriadau, y gyfran didoli

119
00:06:02,150 --> 00:06:05,330
Mae'n rhaid ein rhestr gael i elfennau ynddo gan fod pob cam

120
00:06:05,330 --> 00:06:06,890
fath un elfen.

121
00:06:06,890 --> 00:06:11,770
Felly, mae'n rhaid i'r elfen heb eu didoli cyntaf yn sefyllfa i + 1.

122
00:06:11,770 --> 00:06:15,440
Ar-lein pedwar, rydym yn cymharu yr elfen presennol i'r lleiafswm

123
00:06:15,440 --> 00:06:17,750
elfen yr ydym wedi ei weld hyd yn hyn.

124
00:06:17,750 --> 00:06:20,560
Os yw'r elfen ar hyn o bryd yn llai na'r isafswm

125
00:06:20,560 --> 00:06:23,870
elfen, yna rydym yn cofio yr elfen gyfredol fel newydd

126
00:06:23,870 --> 00:06:26,250
lleiafswm ar-lein pump.

127
00:06:26,250 --> 00:06:29,900
Yn olaf, ar linellau chwech a saith, rydym yn cyfnewid y lleiafswm

128
00:06:29,900 --> 00:06:33,080
elfen sydd â'r elfen heb ei threfnu yn gyntaf, a thrwy hynny

129
00:06:33,080 --> 00:06:36,990
ychwanegu at y gyfran datrys y rhestr.

130
00:06:36,990 --> 00:06:40,030
Unwaith y byddwn wedi algorithm, cwestiwn pwysig i'w ofyn

131
00:06:40,030 --> 00:06:43,370
ein hunain fel rhaglenwyr yn cael ei pa mor hir oedd hynny'n ei gymryd?

132
00:06:43,370 --> 00:06:46,970
Byddwn ofyn yn gyntaf y cwestiwn pa mor hir mae'n ei gymryd ar gyfer y

133
00:06:46,970 --> 00:06:50,070
algorithm i redeg yn yr achos gwaethaf?

134
00:06:50,070 --> 00:06:51,640
Cofio ydym yn eu cynrychioli hon rhedeg

135
00:06:51,640 --> 00:06:55,060
amser gyda mawr O nodiant.

136
00:06:55,060 --> 00:06:58,650
Er mwyn penderfynu ar yr elfen heb ei threfnu isafswm, rydym yn

137
00:06:58,650 --> 00:07:01,880
yn y bôn roedd yn rhaid i gymharu pob elfen yn y rhestr i

138
00:07:01,880 --> 00:07:04,040
pob elfen arall yn y rhestr.

139
00:07:04,040 --> 00:07:08,430
Yn reddfol, mae hyn yn swnio fel O n gweithredu sgwâr.

140
00:07:08,430 --> 00:07:12,050
Edrych ar ein pseudocode, mae gennym hefyd dolen nythu y tu mewn

141
00:07:12,050 --> 00:07:14,420
arall dolen, sydd yn wir yn swnio fel O

142
00:07:14,420 --> 00:07:16,480
o n gweithredu sgwâr.

143
00:07:16,480 --> 00:07:19,250
Fodd bynnag, cofiwch nad oedd angen i ni edrych dros y

144
00:07:19,250 --> 00:07:23,460
rhestr gyfan wrth benderfynu ar yr elfen heb ei threfnu o leiaf?

145
00:07:23,460 --> 00:07:26,600
Unwaith y byddwn yn gwybod bod y 4 gael ei ddatrys, er enghraifft, nid ydym yn gwneud

146
00:07:26,600 --> 00:07:28,170
angen i ni edrych arno eto.

147
00:07:28,170 --> 00:07:31,020
Felly, mae hyn yn is yr amser yn rhedeg?

148
00:07:31,020 --> 00:07:34,510
Ar gyfer ein rhestr o hyd 6, roedd angen i ni gwneud pum

149
00:07:34,510 --> 00:07:37,990
cymariaethau ar gyfer yr elfen gyntaf, pedwar cymariaethau ar gyfer

150
00:07:37,990 --> 00:07:40,750
yr ail elfen, ac yn y blaen.

151
00:07:40,750 --> 00:07:44,690
Mae hynny'n golygu bod y cyfanswm nifer o gamau yn y swm o

152
00:07:44,690 --> 00:07:49,160
y cyfanrifau o 1 i hyd y rhestr minws 1.

153
00:07:49,160 --> 00:07:51,005
Gallwn gynrychioli hyn gyda symiant.

154
00:07:57,980 --> 00:07:59,910
Ni fyddwn yn mynd i mewn i summations yma.

155
00:07:59,910 --> 00:08:04,900
Ond mae'n troi allan fod y symiant yn hafal i amserau n

156
00:08:04,900 --> 00:08:07,540
n minws 1 dros 2.

157
00:08:07,540 --> 00:08:14,220
Neu equivalently, n sgwâr dros 2 minws n dros 2.

158
00:08:14,220 --> 00:08:18,860
Wrth sôn am runtime asymptotic, y tymor hwn sgwâr n

159
00:08:18,860 --> 00:08:22,070
yn mynd i dra-arglwyddiaethu y tymor n.

160
00:08:22,070 --> 00:08:27,850
Felly fath dewis yn O o n sgwâr.

161
00:08:27,850 --> 00:08:31,460
Dwyn i gof bod yn ein enghraifft, didoli dewis dal angen i

162
00:08:31,460 --> 00:08:33,850
gwirio os oes nifer cafodd hynny ei ddatrys yn barod

163
00:08:33,850 --> 00:08:35,450
angen eu symud.

164
00:08:35,450 --> 00:08:38,929
Felly mae hynny'n golygu, os ydym yn rhedeg fath ddewis dros eisoes yn

165
00:08:38,929 --> 00:08:43,070
ddidoli rhestr, byddai angen yr un nifer o camau hynny y mae'n

166
00:08:43,070 --> 00:08:46,340
byddai'n rhedeg dros restr gyfan gwbl heb eu didoli.

167
00:08:46,340 --> 00:08:51,470
Felly fath dethol Mae perfformiad achosion gorau o n sgwâr,

168
00:08:51,470 --> 00:08:56,820
yr ydym yn cynrychioli gyda n sgwâr omega.

169
00:08:56,820 --> 00:08:58,600
A dyna ni am y math dethol.

170
00:08:58,600 --> 00:09:00,630
Dim ond un o'r algorithmau llawer y gallwn

171
00:09:00,630 --> 00:09:02,390
defnyddio i ddatrys rhestr.

172
00:09:02,390 --> 00:09:05,910
Fy enw i yw Tommy, ac mae hyn yn cs50.