1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Trefnu Mewnosod]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

3
00:00:04,240 --> 00:00:07,290
[Mae hyn yn CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Gadewch i ni edrych ar fath gosod, algorithm ar gyfer cymryd restr o rifau a didoli nhw.

5
00:00:13,060 --> 00:00:18,300
Mae algorithm, cofiwch, yn syml, trefn cam-wrth-gam ar gyfer cyflawni'r dasg.

6
00:00:18,300 --> 00:00:23,640
Y syniad sylfaenol y tu ôl math gosod, yw rhannu ein rhestr yn ddau ddogn,

7
00:00:23,640 --> 00:00:26,580
cyfran didoli a chyfran heb eu didoli.

8
00:00:26,580 --> 00:00:29,290
>> Ym mhob cam o'r algorithm, mae nifer yn cael ei symud

9
00:00:29,290 --> 00:00:32,439
gan y rhan heb eu didoli i'r gyfran datrys

10
00:00:32,439 --> 00:00:35,680
nes yn y pen draw y rhestr gyfan yn cael ei datrys.

11
00:00:35,680 --> 00:00:43,340
Dyma restr o chwe rhif heb eu didoli - 23, 42, 4, 16, 8, a 15.

12
00:00:43,340 --> 00:00:47,680
Gan nad yw'r rhifau i gyd mewn trefn esgynnol, maen nhw'n heb eu gwahanu.

13
00:00:47,680 --> 00:00:53,890
Gan nad ydym wedi dechrau didoli eto, byddwn yn ystyried pob un o'r chwe elfen ein cyfran heb eu didoli.

14
00:00:53,890 --> 00:00:59,270
>> Unwaith y byddwn yn dechrau didoli, byddwn yn gosod y rhain rhifau didoli ar ochr chwith y rhain.

15
00:00:59,270 --> 00:01:03,600
Felly, gadewch i ni ddechrau gyda 23, yr elfen gyntaf yn ein rhestr.

16
00:01:03,600 --> 00:01:06,930
Nid oes gennym unrhyw elfennau yn ein cyfran datrys eto,

17
00:01:06,930 --> 00:01:12,460
felly gadewch i ni dim ond yn ystyried 23 i fod yn ddechrau a diwedd ein cyfran datrys.

18
00:01:12,460 --> 00:01:16,510
Yn awr, mae ein cyfran didoli un rhif, 23,

19
00:01:16,510 --> 00:01:20,260
ac mae ein cyfran heb eu didoli yn y pum rhifau.

20
00:01:20,260 --> 00:01:27,320
Gadewch i ni yn awr rhowch y rhif nesaf yn ein cyfran heb eu didoli, 42, i mewn i'r gyfran datrys.

21
00:01:27,320 --> 00:01:35,930
>> I wneud hynny, bydd angen i ni gymharu y 42 i 23 - yr elfen yn unig yn ein cyfran datrys hyd yn hyn.

22
00:01:35,930 --> 00:01:41,980
Mae pedwar deg dau yn fwy na 23, fel y gallwn yn syml atodi 42 i ddiwedd y

23
00:01:41,980 --> 00:01:45,420
o gyfran datrys y rhestr. Great!

24
00:01:45,420 --> 00:01:51,850
Nawr ein cyfran datrys ddwy elfen, ac mae ein cyfran heb eu didoli Mae pedair elfen.

25
00:01:51,850 --> 00:01:57,200
Felly, gadewch i ni nawr symud i 4, yr elfen nesaf yn y gyfran heb eu didoli.

26
00:01:57,200 --> 00:02:00,230
Felly, dylai ble y caiff ei osod yn y gyfran datrys?

27
00:02:00,230 --> 00:02:04,220
>> Cofiwch, mae arnom eisiau rhoi rhif hwn er mwyn datrys

28
00:02:04,220 --> 00:02:08,680
felly mae ein cyfran datrys yn parhau i fod didoli'n gywir bob amser.

29
00:02:08,680 --> 00:02:14,380
Os ydym yn rhoi 4 i'r dde o'r 42, yna bydd ein rhestr fod allan o drefn.

30
00:02:14,380 --> 00:02:18,380
Felly, gadewch i ni barhau i symud dde-i-chwith yn ein cyfran fath.

31
00:02:18,380 --> 00:02:23,260
Wrth i ni symud, gadewch i ni symud pob rhif i lawr lle i wneud lle ar gyfer y rhif newydd.

32
00:02:25,440 --> 00:02:31,740
Iawn, 4 hefyd yn llai na 23, felly ni allwn osod yma chwaith.

33
00:02:31,740 --> 00:02:34,480
Gadewch i ni symud y 23 cywir un lle.

34
00:02:36,500 --> 00:02:43,120
>> Mae hynny'n golygu hoffem i osod y 4 i mewn i'r slot cyntaf yn y gyfran datrys.

35
00:02:43,120 --> 00:02:46,300
Hysbysiad sut y gofod hwn yn y rhestr eisoes yn wag,

36
00:02:46,300 --> 00:02:51,120
oherwydd ein bod wedi bod yn symud elfennau trefnu i lawr fel yr ydym wedi dod ar eu traws nhw.

37
00:02:51,120 --> 00:02:52,740
Mae pob hawl. Felly, rydym hanner ffordd yno.

38
00:02:52,740 --> 00:02:57,990
Gadewch i ni barhau ein algorithm trwy fewnosod y 16 i mewn i'r gyfran datrys.

39
00:02:59,260 --> 00:03:03,820
Un ar bymtheg yn llai na 42, felly gadewch i ni symud y 42 i ar y dde.

40
00:03:05,700 --> 00:03:10,190
Un ar bymtheg hefyd yn llai na 23, felly gadewch i ni hefyd yn symud yr elfen honno.

41
00:03:11,790 --> 00:03:20,820
>> Yn awr, 16 yn fwy na 4. Felly, mae'n edrych fel hoffem i fewnosod y 16 rhwng y 4 a'r 23.

42
00:03:20,820 --> 00:03:24,620
Er symud drwy'r rhan datrys y rhestr o'r dde i'r chwith,

43
00:03:24,620 --> 00:03:29,160
4 yw'r rhif cyntaf rydym wedi gweld bod yn llai na'r nifer a

44
00:03:29,160 --> 00:03:31,540
rydym yn ceisio i fewnosod.

45
00:03:31,540 --> 00:03:35,820
Felly, yn awr gallwn mewnosoder y 16 i hyn slot gwag,

46
00:03:35,820 --> 00:03:40,520
sydd, cofiwch, rydym wedi creu gan elfennau sy'n symud yn y rhan fath dros y

47
00:03:40,520 --> 00:03:43,340
fel yr ydym wedi dod ar eu traws nhw.

48
00:03:43,340 --> 00:03:47,900
>> Mae pob hawl. Yn awr, mae gennym bedair elfen didoli a dwy elfen heb eu didoli.

49
00:03:47,900 --> 00:03:51,600
Felly, gadewch i ni symud yr 8 i mewn i'r gyfran datrys.

50
00:03:51,600 --> 00:03:55,010
Wyth yn llai na 42.

51
00:03:55,010 --> 00:03:56,940
Wyth yn llai na 23.

52
00:03:56,940 --> 00:04:00,230
Ac 8 yn llai na 16.

53
00:04:00,230 --> 00:04:03,110
Ond mae 8 yn fwy na 4.

54
00:04:03,110 --> 00:04:07,280
Felly, byddem yn hoffi i fewnosod yr 8 rhwng y 4 a'r 16.

55
00:04:09,070 --> 00:04:13,650
Ac yn awr rydym yn unig un elfen yn weddill i ddatrys - y 15.

56
00:04:13,950 --> 00:04:16,589
Bymtheg yn llai na 42,

57
00:04:16,589 --> 00:04:19,130
Bymtheg yn llai na 23.

58
00:04:19,130 --> 00:04:21,750
A 15 yn llai na 16.

59
00:04:21,750 --> 00:04:24,810
Ond 15 yn fwy na 8.

60
00:04:24,810 --> 00:04:27,440
>> Felly, dyma lle rydym eisiau gwneud ein gosod terfynol.

61
00:04:28,770 --> 00:04:30,330
Ac rydym ni'n ei wneud.

62
00:04:30,330 --> 00:04:33,540
Nid oes gennym unrhyw elfennau mwy yn y gyfran heb eu didoli,

63
00:04:33,540 --> 00:04:36,670
ac mae ein cyfran didoli yn y drefn gywir.

64
00:04:36,670 --> 00:04:40,270
Mae'r niferoedd yn cael eu harchebu o'r lleiaf i'r mwyaf.

65
00:04:40,270 --> 00:04:44,330
Felly, gadewch i ni edrych ar rai pseudocode sy'n disgrifio'r camau rydym yn unig berfformio.

66
00:04:46,760 --> 00:04:51,740
>> Ar llinell 1, gallwn weld bod bydd angen i ni ailadrodd dros bob elfen yn y rhestr

67
00:04:51,740 --> 00:04:57,060
ac eithrio'r cyntaf, bydd gan fod yr elfen gyntaf yn y gyfran heb eu didoli yn troi'n ddim ond

68
00:04:57,060 --> 00:05:00,220
yr elfen gyntaf yn y rhan didoli.

69
00:05:00,220 --> 00:05:06,320
Ar linellau 2 a 3, rydym yn cadw golwg ar ein lle ar hyn o bryd yn y gyfran heb eu didoli.

70
00:05:06,320 --> 00:05:10,450
Elfen yn cynrychioli nifer o bryd rydym yn symud i mewn i'r gyfran didoli,

71
00:05:10,450 --> 00:05:15,600
a j yn cynrychioli ein mynegai yn y gyfran heb eu didoli.

72
00:05:15,600 --> 00:05:20,980
>> Ar llinell 4, rydym yn ailadrodd drwy'r gyfran datrys o dde i'r chwith.

73
00:05:20,980 --> 00:05:26,010
Rydym yn awyddus i roi'r gorau i ailadrodd unwaith y bydd yr elfen i'r chwith ar ein sefyllfa bresennol

74
00:05:26,010 --> 00:05:30,050
yn llai na'r elfen ydym yn ceisio ei fewnosod.

75
00:05:30,050 --> 00:05:35,600
Ar llinell 5, rydym yn symud pob elfen rydym yn dod ar draws un lle i'r dde.

76
00:05:35,600 --> 00:05:40,950
Drwy hynny, bydd gennym ofod clir i fewnosod yn pan fyddwn yn dod o hyd i'r elfen gyntaf

77
00:05:40,950 --> 00:05:44,080
llai na'r elfen rydym yn symud.

78
00:05:44,080 --> 00:05:50,800
Ar llinell 6, rydym yn diweddaru ein cownter i barhau i symud i'r chwith trwy'r rhan didoli.

79
00:05:50,800 --> 00:05:56,860
Yn olaf, ar-lein 7, rydym yn gosod yr elfen yn y rhan datrys y rhestr.

80
00:05:56,860 --> 00:06:00,020
>> Rydym yn gwybod ei bod yn iawn i fewnosod yn j sefyllfa,

81
00:06:00,020 --> 00:06:05,360
oherwydd ein bod wedi symud yn barod yr elfen a arferai fod yno un lle i'r dde.

82
00:06:05,360 --> 00:06:09,460
Cofiwch, rydym yn symud drwy'r rhan didoli o'r dde i'r chwith,

83
00:06:09,460 --> 00:06:13,960
ond rydym yn symud drwy'r rhan heb eu didoli o'r chwith i'r dde.

84
00:06:13,960 --> 00:06:19,090
Mae pob hawl. Gadewch i ni yn awr yn cymryd golwg ar ba mor hir yn rhedeg y algorithm yn cymryd.

85
00:06:19,090 --> 00:06:25,300
Byddwn ofyn yn gyntaf y cwestiwn pa mor hir mae'n ei gymryd ar gyfer y algorithm i redeg yn yr achos gwaethaf.

86
00:06:25,300 --> 00:06:29,040
Dwyn i gof ein bod yn cynrychioli y tro hwn yn rhedeg gyda Big O nodiant.

87
00:06:32,530 --> 00:06:38,500
Er mwyn datrys ein rhestr, bu'n rhaid i ni ailadrodd dros yr elfennau yn y rhan heb eu didoli,

88
00:06:38,500 --> 00:06:43,430
ac ar gyfer pob un o'r elfennau hynny, o bosibl dros yr holl elfennau yn y rhan didoli.

89
00:06:43,430 --> 00:06:47,950
Yn reddfol, mae hyn yn swnio fel llawdriniaeth O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Edrych ar ein pseudocode, mae gennym dolen nythu y tu mewn arall dolen,

91
00:06:51,840 --> 00:06:55,290
sydd, yn wir, swnio fel llawdriniaeth O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Fodd bynnag, nid yw'r gyfran datrys y rhestr yn cynnwys y rhestr gyfan tan y diwedd un.

93
00:07:01,590 --> 00:07:06,920
Still, gallem o bosibl ychwanegu elfen newydd ar y cychwyn cyntaf y gyfran datrys

94
00:07:06,920 --> 00:07:09,320
ar bob fersiwn o'r algorithm,

95
00:07:09,320 --> 00:07:14,500
sy'n golygu y byddai'n rhaid i ni edrych ar bob elfen ar hyn o bryd yn y rhan didoli.

96
00:07:14,500 --> 00:07:20,090
Felly, mae hynny'n golygu yn bosibl i ni wneud un gymhariaeth ar gyfer yr ail elfen,

97
00:07:20,090 --> 00:07:24,660
2 cymariaethau ar gyfer y drydedd elfen, ac yn y blaen.

98
00:07:24,660 --> 00:07:32,480
Felly, cyfanswm nifer o gamau yn y swm y cyfanrifau o 1 i hyd y rhestr minws 1.

99
00:07:32,480 --> 00:07:35,240
Gallwn gynrychioli hyn gyda symiant.

100
00:07:41,170 --> 00:07:47,270
>> Ni fyddwn yn mynd i mewn i summations yma, ond mae'n troi allan fod y symiant yn hafal i

101
00:07:47,270 --> 00:07:57,900
n (n - 1) dros 2, sef n gyfwerth ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Wrth sôn am runtime asymptotic,

103
00:08:00,800 --> 00:08:05,170
hyn ^ n 2 Tymor yn mynd i dra-arglwyddiaethu y tymor n.

104
00:08:05,170 --> 00:08:11,430
Felly, didoli rhoi i mewn yw Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Beth os ydym yn rhedeg fath gosod ar restr datrys eisoes.

106
00:08:16,150 --> 00:08:20,960
Yn yr achos hwnnw, byddem yn syml yn adeiladu i fyny y rhan didoli o'r chwith i'r dde.

107
00:08:20,960 --> 00:08:25,050
Felly, byddwn dim ond angen ar y drefn o gamau n.

108
00:08:25,050 --> 00:08:29,740
>> Mae hynny'n golygu y math mewnosod Mae perfformiad gorau-achos n,

109
00:08:29,740 --> 00:08:34,130
yr ydym yn cynrychioli gyda Ω (n).

110
00:08:34,130 --> 00:08:36,190
A dyna ni am y math gosod,

111
00:08:36,190 --> 00:08:40,429
dim ond un o'r algorithmau llawer y gallwn ei defnyddio i ddatrys rhestr.

112
00:08:40,429 --> 00:08:43,210
Fy enw i yw Tommy, ac mae hyn yn CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
O, ni allwch atal hynny unwaith y bydd yn dechrau.

115
00:09:01,620 --> 00:09:04,760
O, rydym yn gwneud hynny - Boom >>!