1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Adran 3 - Mwy cyfforddus]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Mae hyn yn CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Felly, y cwestiwn cyntaf yn cael ei eirio yn rhyfedd.

5
00:00:12,700 --> 00:00:17,480
GDB yn gadael i chi "debug" rhaglen, ond, yn fwy penodol, beth mae'n ei gadael i chi ei wneud?

6
00:00:17,480 --> 00:00:22,590
'N annhymerus' ateb hwnnw, ac nid wyf yn gwybod beth a ddisgwylir yn union,

7
00:00:22,590 --> 00:00:27,910
felly rwy'n dyfalu ei fod yn rhywbeth ar hyd y llinellau mae'n gadael i chi gam wrth gam

8
00:00:27,910 --> 00:00:31,540
gerdded drwy'r rhaglen, rhyngweithio ag ef, newidynnau newid, gwneud yr holl bethau hyn -

9
00:00:31,540 --> 00:00:34,270
yn y bôn yn gyfan gwbl rheoli gweithredu o raglen

10
00:00:34,270 --> 00:00:38,410
ac archwilio unrhyw ran benodol o weithredu y rhaglen.

11
00:00:38,410 --> 00:00:43,030
Felly y nodweddion hynny yn gadael i chi debug pethau.

12
00:00:43,030 --> 00:00:44,830
Iawn.

13
00:00:44,830 --> 00:00:50,520
Pam mae chwiliad deuaidd ei gwneud yn ofynnol bod amrywiaeth yn cael ei datrys?

14
00:00:50,520 --> 00:00:53,360
Pwy sydd eisiau i ateb hynny?

15
00:00:56,120 --> 00:01:00,070
[Myfyrwyr] Oherwydd nad yw'n gweithio os nad yw'n datrys. >> Yeah. [Chwerthin]

16
00:01:00,070 --> 00:01:04,910
Os na chaiff ei ddatrys, yna mae'n amhosibl i rannu yn ei hanner

17
00:01:04,910 --> 00:01:07,850
ac yn gwybod bod popeth ar y chwith yn llai a phopeth ar y dde

18
00:01:07,850 --> 00:01:10,490
yn fwy na gwerth canol.

19
00:01:10,490 --> 00:01:12,790
Felly, mae angen ei datrys.

20
00:01:12,790 --> 00:01:14,170
Iawn.

21
00:01:14,170 --> 00:01:17,570
Pam yn fath swigen yn O o n sgwâr?

22
00:01:17,570 --> 00:01:23,230
A oes unrhyw un yn gyntaf am roi cyflym iawn ar lefel uchel trosolwg o'r hyn y fath swigod yw?

23
00:01:25,950 --> 00:01:33,020
[Myfyrwyr] chi yn y bôn yn mynd drwy bob elfen, ac eich bod yn gwirio yr elfennau cyntaf.

24
00:01:33,020 --> 00:01:37,150
Os ydyn nhw'n allan o ble rydych yn eu cyfnewid, yna eich bod yn gwirio yr elfennau nesaf ac yn y blaen.

25
00:01:37,150 --> 00:01:40,770
Pan fyddwch yn cyrraedd y diwedd, yna rydych yn gwybod bod yr elfen fwyaf yn cael ei osod ar y diwedd,

26
00:01:40,770 --> 00:01:42,750
er mwyn i chi anwybyddu bod un yna byddwch yn dal i fynd drwy,

27
00:01:42,750 --> 00:01:48,490
a phob tro y mae'n rhaid i chi wirio un elfen yn llai hyd nes y byddwch yn gwneud unrhyw newidiadau. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Mae'n cael ei alw fath swigod oherwydd os ydych yn troi ar y rhesi ar ei ochr fel mae i fyny ac i lawr, fertigol,

29
00:01:58,470 --> 00:02:03,100
yna bydd y gwerthoedd mawr yn suddo i'r gwaelod a gwerthoedd bach yn swigen i fyny i ben.

30
00:02:03,100 --> 00:02:05,210
Dyna sut y cafodd ei enw.

31
00:02:05,210 --> 00:02:08,220
Ac ie, 'ch jyst yn mynd drwy.

32
00:02:08,220 --> 00:02:11,190
Byddwch yn dal i fynd drwy'r array, gyfnewid y gwerth mwy

33
00:02:11,190 --> 00:02:14,040
i gael y gwerthoedd mwyaf i'r gwaelod.

34
00:02:14,040 --> 00:02:17,500
>> Pam ei bod hi'n O o n sgwâr?

35
00:02:18,690 --> 00:02:24,620
Yn gyntaf, oes unrhyw un eisiau dweud pam y mae'n O o n sgwâr?

36
00:02:24,620 --> 00:02:28,760
[Myfyrwyr] Gan fod ar gyfer pob rhediad y mae'n mynd adegau n.

37
00:02:28,760 --> 00:02:32,100
Gallwch fod yn sicr eich bod wedi cymryd yr elfen fwyaf yr holl ffordd i lawr,

38
00:02:32,100 --> 00:02:35,230
yna rhaid i chi ailadrodd ar gyfer fel elfennau lawer. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Felly, yn cadw mewn cof yr hyn a fawr O olygu a beth yw ystyr Omega mawr.

40
00:02:41,800 --> 00:02:50,560
Mae'r O mawr yn debyg i'r uchaf rhwymo ar sut araf gall fod mewn gwirionedd redeg.

41
00:02:50,560 --> 00:02:58,990
Felly, drwy ddweud ei fod yn O o n sgwâr, nid yw'n O o n neu arall fyddai'n gallu rhedeg

42
00:02:58,990 --> 00:03:02,640
mewn amser llinol, ond mae'n O o n giwbiau

43
00:03:02,640 --> 00:03:06,390
oherwydd ei fod yn ffinio O o n giwbiau.

44
00:03:06,390 --> 00:03:12,300
Os yw'n ffinio gan O o n sgwâr, yna mae'n ffinio hefyd gan n giwbiau.

45
00:03:12,300 --> 00:03:20,280
Felly, mae'n cael ei n sgwâr, ac yn achos gwaethaf absoliwt na all ei wneud yn well na n sgwâr,

46
00:03:20,280 --> 00:03:22,830
a dyna pam ei fod yn O o n sgwâr.

47
00:03:22,830 --> 00:03:31,200
Felly, er mwyn gweld math bach ar sut y mae'n dod allan i fod yn n sgwâr,

48
00:03:31,200 --> 00:03:40,530
os oes gennym pum peth yn ein rhestr, y tro cyntaf a allai faint o gyfnewid rydym gallai fod angen i wneud

49
00:03:40,530 --> 00:03:47,170
er mwyn cael hyn? Gadewch i ni mewn gwirionedd yn unig -

50
00:03:47,170 --> 00:03:52,040
Faint o gyfnewid ydym yn mynd i gael i wneud yn y tymor cyntaf o fath swigen drwy'r casgliad?

51
00:03:52,040 --> 00:03:53,540
[Myfyrwyr] n - 1. >> Yeah.

52
00:03:53,540 --> 00:03:58,340
>> Os oes 5 elfen, rydym yn mynd i angen i wneud n - 1.

53
00:03:58,340 --> 00:04:01,100
Yna, ar yr ail un faint o gyfnewid ydym yn mynd i gael i wneud?

54
00:04:01,100 --> 00:04:03,440
[Myfyrwyr] n - 2. >> Yeah.

55
00:04:03,440 --> 00:04:11,640
Ac mae'r trydydd yn mynd i fod n - 3, ac yna ar gyfer hwylustod, byddaf yn ysgrifennu y ddwy flynedd ddiwethaf

56
00:04:11,640 --> 00:04:15,270
fel yna rydym yn mynd i angen i wneud 2 cyfnewid ac 1 cyfnewid.

57
00:04:15,270 --> 00:04:19,899
Amcana gall yr un olaf neu beidio mewn gwirionedd yn rhaid i ddigwydd.

58
00:04:19,899 --> 00:04:22,820
A yw'n cyfnewid? Nid wyf yn gwybod.

59
00:04:22,820 --> 00:04:26,490
Felly, mae'r rhain yn y cyfansymiau o gyfnewidiadau neu o leiaf gymariaethau rhaid i chi wneud.

60
00:04:26,490 --> 00:04:29,910
Hyd yn oed os nad ydych yn cyfnewid, bydd angen i chi gymharu'r gwerthoedd.

61
00:04:29,910 --> 00:04:33,910
Felly mae n - 1 cymariaethau yn y tymor cyntaf trwy y rhesi.

62
00:04:33,910 --> 00:04:42,050
Os ydych yn ail-drefnu pethau hyn, gadewch i ni mewn gwirionedd yn ei gwneud yn chwe pheth cymaint o bethau synnwyr 'n glws,

63
00:04:42,050 --> 00:04:44,790
ac yna bydda i'n gwneud 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Felly, dim ond ad-drefnu y symiau hyn, rydym eisiau i weld faint o gymariaethau a wnawn

65
00:04:49,910 --> 00:04:52,700
yn y algorithm cyfan.

66
00:04:52,700 --> 00:04:56,550
Felly, os ydym yn dod â'r guys i lawr yma,

67
00:04:56,550 --> 00:05:07,470
yna rydym yn dal i fod ychydig crynhoi cymariaethau Fodd bynnag, roedd llawer.

68
00:05:07,470 --> 00:05:13,280
Ond os ydym yn crynhoi y rhain ac rydym yn crynhoi y rhain ac rydym yn crynhoi y rhain,

69
00:05:13,280 --> 00:05:18,130
mae'n dal i fod yr un broblem. Rydym yn unig yn crynhoi rhai grwpiau penodol.

70
00:05:18,130 --> 00:05:22,400
>> Felly, nawr rydym ni'n crynhoi 3 n yn. Nid dim ond 3 n yn.

71
00:05:22,400 --> 00:05:27,650
Mae bob amser yn mynd i fod yn n / 2 n yn.

72
00:05:27,650 --> 00:05:29,430
Felly dyma ni yn digwydd i gael 6.

73
00:05:29,430 --> 00:05:34,830
Pe bai gennym 10 peth, yna gallem wneud hyn grwpiad at 5 pâr gwahanol o bethau

74
00:05:34,830 --> 00:05:37,180
a darfod i fyny ag n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Felly, rydych chi'n bob amser yn mynd i gael n / 2 n, ac felly byddwn jot allan i n sgwâr / 2.

76
00:05:45,840 --> 00:05:48,890
Ac felly hyd yn oed er 'i' y ffactor o hanner, sy'n digwydd i ddod i mewn

77
00:05:48,890 --> 00:05:54,190
oherwydd y ffaith bod drwy bob iteriad dros yr amrywiaeth rydym yn cymharu 1 yn llai

78
00:05:54,190 --> 00:05:58,040
felly dyna sut yr ydym yn cael y dros 2, ond mae'n dal i fod yn n sgwâr.

79
00:05:58,040 --> 00:06:01,650
Nid ydym yn poeni am y ffactor cyson o hanner.

80
00:06:01,650 --> 00:06:07,760
Felly, mae llawer o mawr O pethau fel hyn yn dibynnu ar ddim ond math o wneud y math hwn o mathemateg,

81
00:06:07,760 --> 00:06:12,260
gwneud symiau rhifyddol a phethau cyfres geometrig,

82
00:06:12,260 --> 00:06:17,750
ond mae'r rhan fwyaf ohonynt yn y cwrs hwn yn eithaf syml.

83
00:06:17,750 --> 00:06:19,290
Iawn.

84
00:06:19,290 --> 00:06:24,430
Pam yn fath gosod yn Omega o n? Beth mae omega yn ei olygu?

85
00:06:24,430 --> 00:06:27,730
[Ddau fyfyriwr yn siarad ar unwaith - annealladwy] Yeah >>.

86
00:06:27,730 --> 00:06:30,630
Gall Omega chi feddwl fel y is rhwymo.

87
00:06:30,630 --> 00:06:36,550
>> Felly, ni waeth pa mor effeithlon yw eich gosod algorithm fath yw,

88
00:06:36,550 --> 00:06:41,810
waeth beth y rhestr sydd wedi pasio i mewn, mae bob amser yn rhaid i gymharu o leiaf n pethau

89
00:06:41,810 --> 00:06:44,620
neu mae'n rhaid iddo ailadrodd dros bethau n.

90
00:06:44,620 --> 00:06:47,280
Pam hynny?

91
00:06:47,280 --> 00:06:51,190
[Myfyrwyr] Oherwydd os bydd y rhestr yn cael ei datrys yn barod, yna trwy gylch 1

92
00:06:51,190 --> 00:06:54,080
gallwch ond warantu bod yr elfen gyntaf yw'r lleiaf,

93
00:06:54,080 --> 00:06:56,490
a'r ail ailadroddiad gallwch warantu y ddau gyntaf yn

94
00:06:56,490 --> 00:07:00,010
oherwydd nad ydych yn gwybod bod y gweddill y rhestr yn cael ei datrys. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Os byddwch yn pasio mewn rhestr datrys yn llwyr, o leiaf rhaid i chi fynd dros yr holl elfennau

96
00:07:08,910 --> 00:07:12,180
i weld nad oes dim angen symud o gwmpas.

97
00:07:12,180 --> 00:07:14,720
Felly, pasio dros y rhestr a dweud oh, mae hyn yn cael ei drefnu eisoes,

98
00:07:14,720 --> 00:07:18,240
mae'n amhosibl i chi wybod ei fod yn datrys hyd nes eich bod yn gwirio pob elfen

99
00:07:18,240 --> 00:07:20,660
i weld eu bod mewn trefn sortio.

100
00:07:20,660 --> 00:07:25,290
Felly, yr isaf rhwymo ar fath rhoi i mewn yw Omega o n.

101
00:07:25,290 --> 00:07:28,210
Beth yr achos gwaethaf amser rhedeg o uno fath,

102
00:07:28,210 --> 00:07:31,390
achos gwaethaf O fawr eto?

103
00:07:31,390 --> 00:07:37,660
Felly, yn y senario achos gwaethaf, sut mae merge math rhedeg?

104
00:07:42,170 --> 00:07:43,690
[Myfyrwyr] N log n. >> Yeah.

105
00:07:43,690 --> 00:07:49,990
Mae'r cyflymaf algorithmau trefnu cyffredinol yn n log n. Ni allwch wneud yn well.

106
00:07:51,930 --> 00:07:55,130
>> Mae rhai achosion arbennig, ac os oes gennym amser heddiw - ond mae'n debyg won't -

107
00:07:55,130 --> 00:07:59,330
gallem weld un sy'n gwneud yn well na n log n.

108
00:07:59,330 --> 00:08:04,050
Ond yn yr achos cyffredinol, ni allwch wneud yn well na n log n.

109
00:08:04,050 --> 00:08:09,680
Ac uno fath yn digwydd i fod yn un y dylech wybod am y cwrs hwn sydd yn n log n.

110
00:08:09,680 --> 00:08:13,260
Ac felly byddwn mewn gwirionedd yn gweithredu hynny heddiw.

111
00:08:13,260 --> 00:08:18,070
Ac yn olaf, mewn dim mwy na tair brawddeg, sut yn gweithio fath dethol?

112
00:08:18,070 --> 00:08:20,370
Oes rhywun eisiau ateb, a byddaf yn cyfrif eich brawddegau

113
00:08:20,370 --> 00:08:22,390
oherwydd os byddwch yn mynd dros 3 -

114
00:08:25,530 --> 00:08:28,330
A oes unrhyw un yn cofio fath dethol?

115
00:08:31,280 --> 00:08:37,809
Dewis fath fel arfer yn eithaf hawdd i'w gofio yn unig gan y enw.

116
00:08:37,809 --> 00:08:45,350
'Ch jyst ailadrodd dros y array, dod o hyd i beth bynnag yw gwerth mwyaf, neu lleiaf -

117
00:08:45,350 --> 00:08:47,290
mha drefn bynnag rydych yn didoli i mewn

118
00:08:47,290 --> 00:08:50,750
Felly, gadewch i ni ddweud ein bod yn didoli o'r lleiaf i'r mwyaf.

119
00:08:50,750 --> 00:08:55,250
Byddwch yn ailadrodd dros yr amrywiaeth, yn chwilio am beth bynnag yr elfen lleiaf yw,

120
00:08:55,250 --> 00:08:59,750
dewis, ac yna dim ond cyfnewid beth bynnag sydd yn y lle cyntaf.

121
00:08:59,750 --> 00:09:04,090
Ac yna ar y tocyn ail ar yr amrywiaeth, edrychwch am yr elfen lleiaf unwaith eto,

122
00:09:04,090 --> 00:09:07,490
dewis, ac yna eu cyfnewid gyda beth sydd yn yr ail safle.

123
00:09:07,490 --> 00:09:10,650
Felly, rydym yn unig yn dewis a dethol y gwerthoedd lleiaf

124
00:09:10,650 --> 00:09:16,050
a mewnosod i mewn i flaen y rhesi nes iddo gael ei datrys.

125
00:09:19,210 --> 00:09:21,560
Cwestiynau ar hynny?

126
00:09:21,560 --> 00:09:25,710
>> Mae'r rhain yn anochel yn ymddangos yn y ffurflenni yn rhaid i chi lenwi pan fyddwch yn cyflwyno'r pset.

127
00:09:29,010 --> 00:09:32,360
Mae'r rhai yn y bôn yr atebion i'r rheini.

128
00:09:32,360 --> 00:09:34,230
Iawn, felly, yn awr codio problemau.

129
00:09:34,230 --> 00:09:40,140
Rwyf eisoes yn anfon allan dros e-bost - nid oedd unrhyw un yn cael yr e-bost? Iawn.

130
00:09:40,140 --> 00:09:46,630
Rwyf eisoes yn anfon allan dros e-bost y gofod ein bod ni'n mynd i gael ei ddefnyddio,

131
00:09:46,630 --> 00:09:52,120
ac os ydych yn clicio ar fy enw - felly yr wyf yn meddwl fy mod i'n mynd i fod ar y gwaelod

132
00:09:52,120 --> 00:09:57,170
oherwydd y r yn ôl - ond os ydych yn clicio ar fy enw byddwch gweler 2 diwygiadau.

133
00:09:57,170 --> 00:10:02,650
Adolygu 1 yn mynd i gael ei gopïo I eisoes a gludo y cod i mewn Mannau

134
00:10:02,650 --> 00:10:06,900
am y peth chwilio yr ydych yn mynd i gael eu gweithredu.

135
00:10:06,900 --> 00:10:10,540
A bydd Revision 2 fod y peth math yr ydym yn gweithredu ar ôl hynny.

136
00:10:10,540 --> 00:10:15,770
Felly, gallwch glicio ar fy Revision 1 ac yn gweithio oddi yno.

137
00:10:17,350 --> 00:10:22,060
Ac yn awr rydym am weithredu chwiliad deuaidd.

138
00:10:22,060 --> 00:10:26,470
>> A oes unrhyw un eisiau i ddim ond yn rhoi pseudocode lefel uchel esboniad

139
00:10:26,470 --> 00:10:31,440
o'r hyn yr ydym yn mynd i gael ei wneud ar gyfer chwilio? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Myfyrwyr] Rydych yn unig yn cymryd ganol y rhesi a gweld os yr hyn yr ydych yn chwilio am

141
00:10:36,170 --> 00:10:38,650
yn llai na hynny neu fwy na hynny.

142
00:10:38,650 --> 00:10:41,080
Ac os yw'n llai, byddwch yn mynd i'r hanner yn llai,

143
00:10:41,080 --> 00:10:44,750
ac os yw'n fwy, byddwch yn mynd i'r hanner yn fwy ac yn ailadrodd hynny nes eich bod dim ond yn cael un peth.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Yeah.

145
00:10:46,570 --> 00:10:51,320
Sylwch fod ein rhifau amrywiaeth ei drefnu eisoes,

146
00:10:51,320 --> 00:10:57,190
ac felly mae hynny'n golygu y gallwn fanteisio ar hynny a allai yn gyntaf wirio,

147
00:10:57,190 --> 00:11:00,390
iawn, dwi'n chwilio am y rhif 50.

148
00:11:00,390 --> 00:11:03,720
Felly, gallaf fynd i mewn i'r canol.

149
00:11:03,720 --> 00:11:07,380
Canol yn anodd ei ddiffinio pan ei fod yn nifer hyd yn oed o bethau,

150
00:11:07,380 --> 00:11:10,820
ond gadewch i ni dim ond yn dweud y byddan byddwn bob amser yn gwtogi'r amser i'r canol.

151
00:11:10,820 --> 00:11:14,420
Felly dyma gennym 8 pethau, felly byddai'r canol fod yn 16.

152
00:11:14,420 --> 00:11:17,330
Dwi'n chwilio am 50, felly 50 yn fwy na 16.

153
00:11:17,330 --> 00:11:21,310
Felly nawr gallaf drin fy bôn amrywiaeth fel elfennau hyn.

154
00:11:21,310 --> 00:11:23,450
Gallaf daflu popeth o 16 drosodd.

155
00:11:23,450 --> 00:11:27,440
Nawr mae fy amrywiaeth yn unig y 4 elfen, a dywedaf eto.

156
00:11:27,440 --> 00:11:31,910
Felly, yna rwyf am ddod o hyd i'r canol unwaith eto, sydd yn mynd i fod yn 42.

157
00:11:31,910 --> 00:11:34,730
42 yn llai na 50, er mwyn i mi daflu i ffwrdd y ddwy elfen.

158
00:11:34,730 --> 00:11:36,890
Dyma fy amrywiaeth sy'n weddill.

159
00:11:36,890 --> 00:11:38,430
Rydw i'n mynd i ddod o hyd i'r canol unwaith eto.

160
00:11:38,430 --> 00:11:42,100
Amcana 50 yn esiampl wael oherwydd fy mod bob amser yn taflu pethau i'r chwith,

161
00:11:42,100 --> 00:11:48,280
ond gan yr un mesur, os ydw i'n chwilio am rywbeth

162
00:11:48,280 --> 00:11:52,100
ac mae'n llai na'r elfen o bryd rwy'n edrych ar,

163
00:11:52,100 --> 00:11:55,080
Yna rwy'n mynd i daflu i ffwrdd popeth ar y dde.

164
00:11:55,080 --> 00:11:58,150
Felly, yn awr mae angen i ni weithredu.

165
00:11:58,150 --> 00:12:02,310
Sylwch fod angen i ni roi o ran maint.

166
00:12:02,310 --> 00:12:06,730
Ni all angen i ni hefyd galed-god maint.

167
00:12:06,730 --> 00:12:11,640
Felly, os byddwn yn cael gwared ar y # diffinio -

168
00:12:19,630 --> 00:12:21,430
Iawn.

169
00:12:21,430 --> 00:12:27,180
Sut y gallaf 'n glws chyfrif i maes beth yw maint y rhesi rhifau ar hyn o bryd?

170
00:12:27,180 --> 00:12:30,950
>> Faint o elfennau yn yr amrywiaeth rhifau?

171
00:12:30,950 --> 00:12:33,630
[Myfyrwyr] Rhifau, cromfachau,. Hyd?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Nid yw hynny'n bodoli yn C.

173
00:12:36,600 --> 00:12:38,580
Angen. Hyd.

174
00:12:38,580 --> 00:12:42,010
Nid oes gan araeau eiddo, felly nid oes dim eiddo hyd araeau

175
00:12:42,010 --> 00:12:45,650
a fydd yn unig yn rhoi i chi waeth pa mor hir mae'n digwydd i fod.

176
00:12:48,180 --> 00:12:51,620
[Myfyrwyr] Gweler faint o gof sydd ganddo a'i rannu â faint - Yeah >>.

177
00:12:51,620 --> 00:12:55,810
Felly sut allwn ni weld faint o gof sydd ganddo? >> [Myfyrwyr] Sizeof. >> Yeah, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof yw'r gweithredwr sy'n mynd i ddychwelyd maint y rhesi rhifau.

179
00:13:01,680 --> 00:13:10,060
Ac mae hynny'n mynd i fod yn gyfanrifau, fodd bynnag, mae llawer o gwaith maint o gyfanrif

180
00:13:10,060 --> 00:13:14,050
ers hynny mae faint o gof mae'n mewn gwirionedd yn cymryd i fyny.

181
00:13:14,050 --> 00:13:17,630
Felly, os ydw i am nifer o bethau yn yr amrywiaeth,

182
00:13:17,630 --> 00:13:20,560
yna dwi'n mynd i eisiau ei rannu â faint o gyfanrif.

183
00:13:22,820 --> 00:13:26,010
Iawn. Felly, sy'n gadael i mi basio o ran maint yma.

184
00:13:26,010 --> 00:13:29,430
Pam ydw i'n angen i chi basio o ran maint o gwbl?

185
00:13:29,430 --> 00:13:38,570
Pam na allaf ond yn gwneud i fyny yma faint int = sizeof (tas wair) / sizeof (canolradd)?

186
00:13:38,570 --> 00:13:41,490
Pam nad yw hyn yn gweithio?

187
00:13:41,490 --> 00:13:44,470
[Myfyrwyr] Dyw hi ddim yn newidyn byd-eang.

188
00:13:44,470 --> 00:13:51,540
Haystack [Bowden] yn bodoli ac rydym yn pasio yn y niferoedd fel tas wair,

189
00:13:51,540 --> 00:13:54,700
ac mae hyn yn fath o foreshadowing o'r hyn sydd i ddod. Yeah.

190
00:13:54,700 --> 00:14:00,170
[Myfyrwyr] Haystack yn unig yw'r cyfeiriad ato, felly byddai'n dychwelyd pa mor fawr mae'r cyfeiriad hwnnw.

191
00:14:00,170 --> 00:14:02,150
Yeah.

192
00:14:02,150 --> 00:14:09,000
Yr wyf yn amau ​​mewn darlith yr ydych wedi gweld y simnai eto mewn gwirionedd, dde?

193
00:14:09,000 --> 00:14:11,270
Rydym wedi siarad yn unig am y peth.

194
00:14:11,270 --> 00:14:16,090
Felly, y corn simnai yw ble mae eich holl newidynnau yn mynd i gael eu storio.

195
00:14:16,090 --> 00:14:19,960
>> Unrhyw cof sydd wedi dyrannu ar gyfer newidynnau lleol yn mynd yn y simnai,

196
00:14:19,960 --> 00:14:24,790
a phob swyddogaeth yn cael ei ofod ei hun ar y simnai, ei ffrâm stac ei hun yw'r hyn fe'i gelwir.

197
00:14:24,790 --> 00:14:31,590
Felly, prif wedi ei ffrâm pentwr, a'r tu mewn ohono yn mynd i fodoli y amrywiaeth rhifau,

198
00:14:31,590 --> 00:14:34,270
ac mae'n mynd i fod o (nifer) sizeof maint.

199
00:14:34,270 --> 00:14:38,180
Mae'n mynd i gael faint y rhifau rhannu yn ôl maint y elfennau,

200
00:14:38,180 --> 00:14:42,010
ond bod yr holl byw o fewn ffrâm pentwr prif.

201
00:14:42,010 --> 00:14:45,190
Pan fyddwn yn galw chwilio, chwilio yn cael ei ffrâm pentwr ei hun,

202
00:14:45,190 --> 00:14:48,840
ei le ei hun i storio ei holl newidynnau lleol.

203
00:14:48,840 --> 00:14:56,420
Ond mae'r dadleuon - felly nid tas wair yn gopi o'r amrywiaeth gyfan.

204
00:14:56,420 --> 00:15:00,990
Nid ydym yn trosglwyddo yn y casgliad cyfan fel copi i chwilio.

205
00:15:00,990 --> 00:15:04,030
'I jyst yn pasio gyfeiriad at y casgliad.

206
00:15:04,030 --> 00:15:11,470
Felly, gall chwilio gael gafael ar y rhifau drwy geirda hwn.

207
00:15:11,470 --> 00:15:17,100
Mae'n dal i gael mynediad at y pethau sy'n byw tu mewn ffrâm pentwr prif,

208
00:15:17,100 --> 00:15:22,990
ond yn y bôn, pan fyddwn yn mynd i awgrymiadau, a ddylai fod yn fuan,

209
00:15:22,990 --> 00:15:24,980
mae hyn yn beth awgrymiadau yn cael eu.

210
00:15:24,980 --> 00:15:29,400
Pointers yn unig gyfeiriadau at bethau, a gallwch ddefnyddio awgrymiadau i gael gafael ar bethau

211
00:15:29,400 --> 00:15:32,030
sydd mewn fframiau stac pethau eraill '.

212
00:15:32,030 --> 00:15:37,660
Felly hyd yn oed er bod y niferoedd yn lleol to main, gallwn barhau i gael mynediad iddo trwy'r pwyntydd.

213
00:15:37,660 --> 00:15:41,770
Ond gan ei fod dim ond pwyntydd ac mae'n dim ond cyfeiriad,

214
00:15:41,770 --> 00:15:45,040
sizeof (tas wair) dim ond yn dychwelyd y maint y cyfeiriad ei hun.

215
00:15:45,040 --> 00:15:47,950
Nid yw'n dychwelyd maint y peth mae'n pwyntio at.

216
00:15:47,950 --> 00:15:51,110
Nid yw'n dychwelyd y maint gwirioneddol y rhifau.

217
00:15:51,110 --> 00:15:55,660
Ac felly nid yw hyn yn mynd i weithio fel yr ydym am iddo.

218
00:15:55,660 --> 00:15:57,320
>> Cwestiynau ar hynny?

219
00:15:57,320 --> 00:16:03,250
Bydd awgrymiadau yn mynd i mewn yn fanwl llawer mwy gwaedlyd yn yr wythnosau i ddod.

220
00:16:06,750 --> 00:16:13,740
A dyma pam mae llawer o bethau yr ydych yn gweld, pethau chwilio mwyaf neu bethau fath,

221
00:16:13,740 --> 00:16:16,990
eu bod bron i gyd yn mynd i angen i gymryd y maint gwirioneddol y array,

222
00:16:16,990 --> 00:16:20,440
oherwydd yn C, nid oes gennym unrhyw syniad beth yw maint y rhesi yn.

223
00:16:20,440 --> 00:16:22,720
Mae angen i chi llaw ei drosglwyddo i mewn

224
00:16:22,720 --> 00:16:27,190
Ac ni allwch manually basio yn yr amrywiaeth cyfan oherwydd eich bod yn mynd heibio yn y cyfeiriad

225
00:16:27,190 --> 00:16:30,390
ac ni all gael y maint o'r cyfeiriad.

226
00:16:30,390 --> 00:16:32,300
Iawn.

227
00:16:32,300 --> 00:16:38,160
Felly, nawr rydym am i weithredu'r hyn Eglurwyd o'r blaen.

228
00:16:38,160 --> 00:16:41,530
Gallwch weithio arno am funud,

229
00:16:41,530 --> 00:16:45,250
ac nid oes rhaid i chi boeni am gael popeth yn berffaith 100% gweithio.

230
00:16:45,250 --> 00:16:51,410
Dim ond yn ysgrifennu i fyny 'r pseudocode hanner ar gyfer sut rydych chi'n meddwl y dylai weithio.

231
00:16:52,000 --> 00:16:53,630
Iawn.

232
00:16:53,630 --> 00:16:56,350
Nid oes angen i gael ei wneud yn gyfan gwbl â hyn eto.

233
00:16:56,350 --> 00:17:02,380
Ond oes unrhyw un yn teimlo'n gyfforddus â'r hyn sydd ganddynt hyd yn hyn,

234
00:17:02,380 --> 00:17:05,599
fel rhywbeth y gallwn weithio gyda gyda'n gilydd?

235
00:17:05,599 --> 00:17:09,690
A oes unrhyw un eisiau gwirfoddoli? Neu byddaf yn dewis ar hap.

236
00:17:12,680 --> 00:17:18,599
Nid oes rhaid i fod yn iawn gan unrhyw fesur, ond rhywbeth y gallwn addasu i gyflwr gweithio.

237
00:17:18,599 --> 00:17:20,720
[Myfyrwyr] Cadarn. >> Iawn.

238
00:17:20,720 --> 00:17:27,220
Felly a allwch arbed y diwygiad drwy glicio ar yr eicon Save bach.

239
00:17:27,220 --> 00:17:29,950
Rydych chi'n Ramya, dde? >> [Myfyrwyr] Yeah. >> [Bowden] Iawn.

240
00:17:29,950 --> 00:17:35,140
Felly nawr gallaf weld eich adolygu a gall pawb dynnu i fyny y diwygiad.

241
00:17:35,140 --> 00:17:38,600
Ac yma mae gennym - Iawn.

242
00:17:38,600 --> 00:17:43,160
Felly Ramya aeth gyda'r ateb recursive, sydd yn bendant yn ateb dilys.

243
00:17:43,160 --> 00:17:44,970
Mae dwy ffordd y gallwch wneud y broblem hon.

244
00:17:44,970 --> 00:17:48,060
Gallwch naill ai wneud yn iteraidd neu ailadroddus.

245
00:17:48,060 --> 00:17:53,860
Gall problemau y rhan fwyaf o ddod ar eu traws y gellir ei wneud recursively hefyd yn cael ei wneud yn iteraidd.

246
00:17:53,860 --> 00:17:58,510
Felly dyma ni wedi gwneud hynny ailadroddus.

247
00:17:58,510 --> 00:18:03,730
>> Oes rhywun eisiau i ddiffinio'r hyn y mae'n ei olygu i wneud swyddogaeth recursive?

248
00:18:07,210 --> 00:18:08,920
[Myfyrwyr] Pan fydd gennych swyddogaeth alw ei hun

249
00:18:08,920 --> 00:18:13,470
ac yna galw ei hun hyd nes ei fod yn dod allan gyda'r wir ac yn wir. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
Mae swyddogaeth recursive yn unig yw swyddogaeth sy'n galw ei hun.

251
00:18:17,680 --> 00:18:24,140
Mae tri pheth mawr bod rhaid i swyddogaeth ailadroddus gael.

252
00:18:24,140 --> 00:18:27,310
Y cyntaf yn amlwg, mae'n galw ei hun.

253
00:18:27,310 --> 00:18:29,650
Yr ail yw'r achos sylfaenol.

254
00:18:29,650 --> 00:18:33,390
Felly, ar ryw bwynt y swyddogaeth mae angen i roi'r gorau i ffonio ei hun,

255
00:18:33,390 --> 00:18:35,610
a dyna beth yr achos sylfaenol ar gyfer.

256
00:18:35,610 --> 00:18:43,860
Felly, yma rydym yn gwybod y dylem roi'r gorau, dylem roi'r gorau i chwilio yn ein

257
00:18:43,860 --> 00:18:48,150
pan fydd yn dychwelyd dechrau diwedd - a byddwn yn mynd dros yr hyn mae'n ei olygu.

258
00:18:48,150 --> 00:18:52,130
Ond o'r diwedd, y peth olaf sy'n bwysig ar gyfer swyddogaethau recursive:

259
00:18:52,130 --> 00:18:59,250
rhaid i swyddogaethau'r rywsut gysylltu â'r achos sylfaenol.

260
00:18:59,250 --> 00:19:04,140
Fel os nad ydych chi'n mewn gwirionedd yn diweddaru unrhyw beth pan fyddwch yn gwneud yr alwad recursive ail,

261
00:19:04,140 --> 00:19:07,880
os ydych yn llythrennol dim ond galw swyddogaeth eto gyda'r un dadleuon

262
00:19:07,880 --> 00:19:10,130
ac nid oes unrhyw newidynnau byd-eang wedi newid neu unrhyw beth,

263
00:19:10,130 --> 00:19:14,430
fyddwch chi byth yn cyrraedd yr achos sylfaenol, yn yr achos hwnnw yn ddrwg.

264
00:19:14,430 --> 00:19:17,950
Bydd yn dychweliad diddiwedd a gorlif pentwr.

265
00:19:17,950 --> 00:19:24,330
Ond dyma rydym yn gweld bod y diweddariad yn digwydd gan ein bod yn diweddaru dechrau + diwedd / 2,

266
00:19:24,330 --> 00:19:28,180
rydym yn diweddaru'r ddadl diwedd yma, rydym yn diweddaru'r ddadl i ddechrau yma.

267
00:19:28,180 --> 00:19:32,860
Felly, yn yr holl alwadau recursive rydym yn diweddaru rhywbeth. Iawn.

268
00:19:32,860 --> 00:19:38,110
Ydych chi eisiau i gerdded i ni drwy eich ateb? >> Cadarn.

269
00:19:38,110 --> 00:19:44,270
Im 'yn arfer SearchHelp fel bod pob tro y byddaf yn gwneud yr alwad swyddogaeth

270
00:19:44,270 --> 00:19:47,910
Rwy'n cael y cychwyn o ble rwy'n chwilio amdano yn y casgliad a diwedd

271
00:19:47,910 --> 00:19:49,380
o ble rwy'n edrych y rhesi.

272
00:19:49,380 --> 00:19:55,330
>> Ar bob cam lle mae'n dweud ei fod yn elfen canol, sydd yn dechrau + diwedd / 2,

273
00:19:55,330 --> 00:19:58,850
yw bod gyfartal i'r hyn rydym yn chwilio amdano?

274
00:19:58,850 --> 00:20:04,650
Ac os ydyw, yna ni eu canfod, ac yr wyf yn dyfalu bod yn cael ei basio i fyny y lefelau o dychweliad.

275
00:20:04,650 --> 00:20:12,540
Ac os nad yw hynny'n wir, yna byddwn yn gwirio a yw'r gwerth canol y rhesi yn rhy fawr,

276
00:20:12,540 --> 00:20:19,320
ac os felly byddwn yn edrych ar hanner chwith y casgliad drwy fynd o'r dechrau i'r mynegai canol.

277
00:20:19,320 --> 00:20:22,710
Ac fel arall rydym yn ei wneud hanner diwedd.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Iawn.

279
00:20:24,740 --> 00:20:27,730
Mae hynny'n swnio'n dda.

280
00:20:27,730 --> 00:20:36,640
Iawn, felly ychydig bethau, ac mewn gwirionedd, mae hyn yn beth lefel uchel iawn

281
00:20:36,640 --> 00:20:41,270
na fydd angen i chi wybod am y cwrs hwn, ond mae'n wir.

282
00:20:41,270 --> 00:20:46,080
Swyddogaethau recursive, byddwch bob amser yn clywed eu bod yn bargen wael

283
00:20:46,080 --> 00:20:51,160
oherwydd os ydych recursively ffonio eich hun gormod o weithiau, byddwch yn cael gorlif stac

284
00:20:51,160 --> 00:20:54,990
ers hynny, fel y dywedais o'r blaen, mae pob swyddogaeth yn cael ei ffrâm pentwr hun.

285
00:20:54,990 --> 00:20:59,500
Felly mae gan bob galwad y swyddogaeth ailadroddus yn cael ei ffrâm pentwr hun.

286
00:20:59,500 --> 00:21:04,140
Felly, os ydych yn gwneud 1,000 o alwadau recursive, byddwch yn cael 1,000 fframiau simnai,

287
00:21:04,140 --> 00:21:08,390
ac yn gyflym i chi arwain at orfod fframiau stac gormod a phethau yn unig torri.

288
00:21:08,390 --> 00:21:13,480
Felly dyna pam mae swyddogaethau recursive yn gyffredinol wael.

289
00:21:13,480 --> 00:21:19,370
Ond mae is-set 'n glws o swyddogaethau ailadroddus a elwir yn gynffon-recursive swyddogaethau,

290
00:21:19,370 --> 00:21:26,120
ac mae hyn yn digwydd i fod yn enghraifft o un lle os yw'r compiler hysbysiadau hyn

291
00:21:26,120 --> 00:21:29,920
ac y dylai fod, yr wyf yn meddwl - yn Clang os byddwch yn llwyddo yn y O2-faner

292
00:21:29,920 --> 00:21:33,250
yna bydd yn sylwi ar hyn yn gynffon ailadroddus ac yn gwneud pethau da.

293
00:21:33,250 --> 00:21:40,050
>> Bydd yn ail-ddefnyddio'r ffrâm pentwr un drosodd a throsodd ar gyfer pob galwad ailadroddus.

294
00:21:40,050 --> 00:21:47,010
Ac felly ers ydych chi'n defnyddio'r ffrâm pentwr un, nid oes angen i chi boeni am

295
00:21:47,010 --> 00:21:51,690
erioed stacio gorlifo, ac ar yr un pryd, fel y dywedasoch o'r blaen,

296
00:21:51,690 --> 00:21:56,380
lle ar ôl i chi ddychwelyd wir, yna mae'n rhaid iddo ddychwelyd i fyny pob un o'r fframiau stac

297
00:21:56,380 --> 00:22:01,740
a'r galw 10fed SearchHelp wedi dychwelyd i'r 9fed, yn gorfod dychwelyd i'r 8fed.

298
00:22:01,740 --> 00:22:05,360
Felly nid oes angen i hyn ddigwydd pan fydd swyddogaethau yn gynffon ailadroddus.

299
00:22:05,360 --> 00:22:13,740
Ac felly yr hyn sy'n gwneud y gynffon swyddogaeth recursive yw rhybudd ar gyfer unrhyw alwad a roddir i searchHelp

300
00:22:13,740 --> 00:22:18,470
yr alwad recursive ei fod yn gwneud yr hyn y mae'n dychwelyd.

301
00:22:18,470 --> 00:22:25,290
Felly, yn yr alwad gyntaf i SearchHelp, rydym naill ai ar unwaith dychwelyd ffug,

302
00:22:25,290 --> 00:22:29,590
dychwelyd ar unwaith yn wir, neu os byddwn yn gwneud galwad recursive i SearchHelp

303
00:22:29,590 --> 00:22:33,810
lle yr hyn yr ydym yn dychwelyd yr hyn yr alwad honno yn dychwelyd.

304
00:22:33,810 --> 00:22:51,560
Ac nid oeddem yn gallu gwneud hyn os ydym yn gwneud rhywbeth tebyg int x = SearchHelp, dychwelyd x * 2,

305
00:22:51,560 --> 00:22:55,440
dim ond rhywfaint o newid ar hap.

306
00:22:55,440 --> 00:23:01,470
>> Felly nawr alwad hon recursive, mae hyn yn int x = SearchHelp galwad recursive,

307
00:23:01,470 --> 00:23:05,740
yw bellach yn gynffon recursive oherwydd ei fod mewn gwirionedd yn rhaid i chi ddychwelyd

308
00:23:05,740 --> 00:23:10,400
yn ôl i ffrâm pentwr flaenorol fel bod y galwad blaenorol i'r swyddogaeth

309
00:23:10,400 --> 00:23:13,040
Yna gall wneud rhywbeth gyda'r gwerth dychwelyd.

310
00:23:13,040 --> 00:23:22,190
Felly, nid yw hyn yn gynffon recursive, ond yr hyn oedd gennym o'r blaen yn 'n glws cynffon ailadroddus. Yeah.

311
00:23:22,190 --> 00:23:27,000
Os na [myfyrwyr] yr achos ail ganolfan yn cael ei wirio 1

312
00:23:27,000 --> 00:23:30,640
oherwydd gallai fod sefyllfa lle pan fyddwch yn ei drosglwyddo y ddadl

313
00:23:30,640 --> 00:23:35,770
ydych wedi dechrau = diwedd, ond maent yn werth nodwydd.

314
00:23:35,770 --> 00:23:47,310
Y cwestiwn Ni all oedd rydym yn rhedeg i mewn i'r achos lle diwedd yw gwerth nodwydd

315
00:23:47,310 --> 00:23:52,000
neu ddechrau = diwedd, yn briodol, yn dechrau = diwedd

316
00:23:52,000 --> 00:23:59,480
ac nad ydych wedi gwirio mewn gwirionedd y gwerth penodol hynny eto,

317
00:23:59,480 --> 00:24:03,910
yna dechreuwch + diwedd / 2 yn unig yn mynd i fod yn un gwerth.

318
00:24:03,910 --> 00:24:07,890
Ond rydym eisoes wedi dychwelyd ffug ac ni fyddwn byth yn gwirio mewn gwirionedd y gwerth.

319
00:24:07,890 --> 00:24:14,240
Felly, o leiaf, yn yr alwad gyntaf, os yw maint yw 0, yna rydym eisiau dychwelyd ffug.

320
00:24:14,240 --> 00:24:17,710
Ond os maint yw 1, yna nid yw dechrau yn mynd i ben cyfartal,

321
00:24:17,710 --> 00:24:19,820
a byddwn o leiaf yn gwirio yr un elfen.

322
00:24:19,820 --> 00:24:26,750
Ond yr wyf yn meddwl eich bod yn iawn yn y gallwn yn y pen draw mewn achos lle dechrau + diwedd / 2,

323
00:24:26,750 --> 00:24:31,190
dechrau dod i ben i fyny yr un fath â dechrau + diwedd / 2,

324
00:24:31,190 --> 00:24:35,350
ond ni fyddwn byth gwirio mewn gwirionedd yr elfen honno.

325
00:24:35,350 --> 00:24:44,740
>> Felly, os ydym yn gwiriwch yn gyntaf yw'r elfen ganol y gwerth rydym yn chwilio am,

326
00:24:44,740 --> 00:24:47,110
yna gallwn ar unwaith ddychwelyd yn wir.

327
00:24:47,110 --> 00:24:50,740
Arall os ydynt yn gyfartal, yna does dim pwynt i barhau

328
00:24:50,740 --> 00:24:58,440
ers i ni yn unig yn mynd i ddiweddaru at achos lle rydym ar amrywiaeth un-elfen.

329
00:24:58,440 --> 00:25:01,110
Os nad yw'r elfen unigol yw'r un yr ydym yn chwilio amdano,

330
00:25:01,110 --> 00:25:03,530
yna mae popeth yn anghywir. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Myfyrwyr] Y peth yw bod ers faint mewn gwirionedd yn fwy na'r nifer o elfennau yn yr amrywiaeth,

332
00:25:08,900 --> 00:25:13,070
mae eisoes yn offset - >> Felly, bydd maint -

333
00:25:13,070 --> 00:25:19,380
[Myfyrwyr] Dywedwch os yr amrywiaeth oedd maint 0, yna bydd y SearchHelp mewn gwirionedd yn gwirio tas wair o 0

334
00:25:19,380 --> 00:25:21,490
ar yr alwad gyntaf.

335
00:25:21,490 --> 00:25:25,300
Mae amrywiaeth o faint 0, felly mae'r 0 yw - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Mae peth arall hynny - gallai fod yn dda. Gadewch i ni feddwl.

337
00:25:30,750 --> 00:25:40,120
Felly, os yr amrywiaeth oedd gan 10 elfen a'r un canol ydym yn mynd i wirio yw mynegai 5,

338
00:25:40,120 --> 00:25:45,700
felly rydym yn gwirio 5, a gadewch i ni ddweud bod y gwerth yn llai.

339
00:25:45,700 --> 00:25:50,720
Felly, rydym yn taflu popeth i ffwrdd o 5 ymlaen.

340
00:25:50,720 --> 00:25:54,030
Felly dechrau + diwedd / 2 yn mynd i fod ein pen newydd,

341
00:25:54,030 --> 00:25:57,450
felly yeah, mae bob amser yn mynd i aros y tu hwnt i ddiwedd y rhesi.

342
00:25:57,450 --> 00:26:03,570
Os yw'n achos os oedd yn eilrif neu'n odrif, yna byddem yn gwirio, dyweder, 4,

343
00:26:03,570 --> 00:26:05,770
ond rydym yn dal i daflu i ffwrdd -

344
00:26:05,770 --> 00:26:13,500
Felly yeah, diwedd bob amser yn mynd i fod tu hwnt i ddiwedd gwirioneddol y rhesi.

345
00:26:13,500 --> 00:26:18,350
Felly, yr elfennau ydym yn canolbwyntio ar, diwedd bob amser yn mynd i fod yn un ar ôl hynny.

346
00:26:18,350 --> 00:26:24,270
Ac felly os dechrau gwneud erioed diwedd cyfartal, yr ydym mewn amrywiaeth o faint 0.

347
00:26:24,270 --> 00:26:35,600
>> Y peth arall yr wyf yn meddwl yw ein bod yn diweddaru dechrau cael ei ddechrau + diwedd / 2,

348
00:26:35,600 --> 00:26:44,020
felly mae hyn yn wir fy mod i'n cael trafferth gyda nhw, lle dechrau + diwedd / 2

349
00:26:44,020 --> 00:26:46,820
yw'r elfen rydym yn gwirio.

350
00:26:46,820 --> 00:26:58,150
Lets 'ddeud gawsom y casgliad 10-elfen. Beth bynnag.

351
00:26:58,150 --> 00:27:03,250
Felly dechrau + diwedd / 2 yn mynd i fod yn rhywbeth fel yr un yma,

352
00:27:03,250 --> 00:27:07,060
ac os nad yw hynny'n werth, yn dweud ein bod am ddiweddaru.

353
00:27:07,060 --> 00:27:10,060
Mae'r gwerth yn fwy, felly rydym yn awyddus i edrych ar y hanner y rhesi.

354
00:27:10,060 --> 00:27:15,910
Felly, sut rydym yn diweddaru dechrau, rydym yn diweddaru dechrau yn hyn yn yr elfen hon.

355
00:27:15,910 --> 00:27:23,790
Ond efallai y bydd hyn yn dal i weithio, neu o leiaf, gallwch wneud dechrau + diwedd / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Myfyrwyr] Nid oes angen i chi gael ei ddechrau + diwedd [Anghlywadwy] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Rydym wedi gwirio eisoes yr elfen hon ac yn gwybod nad yw'n un yr ydym yn chwilio amdano.

358
00:27:33,240 --> 00:27:36,800
Felly nid oes angen i ddiweddaru dechrau i fod yn yr elfen hon.

359
00:27:36,800 --> 00:27:39,560
Gallwn yn unig sgip a diweddaru dechrau i fod yn yr elfen hon.

360
00:27:39,560 --> 00:27:46,060
Ac a oes byth achos, gadewch i ni ddweud, bod hyn oedd diwedd,

361
00:27:46,060 --> 00:27:53,140
Byddai hynny wedyn yn dechrau yn hyn, yn dechrau + diwedd / byddai 2 yn hyn,

362
00:27:53,140 --> 00:28:00,580
dechrau + diwedd - Yeah, yr wyf yn meddwl y gall ddod i ben i fyny mewn dychweliad ddiddiwedd.

363
00:28:00,580 --> 00:28:12,690
Lets 'ddeud' i 'jyst amrywiaeth o faint 2 neu amrywiaeth o faint 1. Rwy'n credu y bydd hyn yn gweithio.

364
00:28:12,690 --> 00:28:19,490
Felly, ar hyn o bryd, cychwyn yw bod elfen a diwedd yw 1 y tu hwnt iddo.

365
00:28:19,490 --> 00:28:24,110
Felly, mae'r elfen ein bod ni'n mynd i wirio yw hwn yn un,

366
00:28:24,110 --> 00:28:29,400
ac yna pan fyddwn yn diweddaru dechrau, rydym yn diweddaru dechrau i fod yn 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
sydd yn mynd i orffen â ni yn ôl gyda dechrau yn yr elfen hon.

368
00:28:33,160 --> 00:28:36,210
>> Felly, rydym yn gwirio yr un elfen drosodd a throsodd.

369
00:28:36,210 --> 00:28:43,310
Felly, mae hyn yn wir lle mae'n rhaid i bob galwad recursive mewn gwirionedd yn diweddaru rhywbeth.

370
00:28:43,310 --> 00:28:48,370
Felly mae angen i wneud cychwyn + diwedd / 2 + 1, neu fel arall mae achos

371
00:28:48,370 --> 00:28:50,710
lle nad ydym yn mewn gwirionedd yn dechrau diweddaru.

372
00:28:50,710 --> 00:28:53,820
Mae pawb yn gweld hynny?

373
00:28:53,820 --> 00:28:56,310
Iawn.

374
00:28:56,310 --> 00:29:03,860
Oes gan unrhyw un cwestiynau ar yr ateb hwn neu sylwadau unrhyw mwy?

375
00:29:05,220 --> 00:29:10,280
Iawn. A oes unrhyw un wedi iteraidd ateb y gallwn i gyd edrych ar?

376
00:29:17,400 --> 00:29:20,940
Gwnaethom ni gyd yn ei wneud recursively?

377
00:29:20,940 --> 00:29:25,950
Neu hefyd yr wyf yn dyfalu os ydych yn agor iddi, yna efallai y bydd gennych gor-redeg eich un flaenorol.

378
00:29:25,950 --> 00:29:28,810
A yw'n awtomatig arbed? Dydw i ddim yn gadarnhaol.

379
00:29:35,090 --> 00:29:39,130
A oes unrhyw un wedi ailadroddol?

380
00:29:39,130 --> 00:29:42,430
Gallwn cerdded trwy ei gilydd os nad ydyw.

381
00:29:46,080 --> 00:29:48,100
Mae'r syniad yn mynd i fod yr un fath.

382
00:30:00,260 --> 00:30:02,830
Ailadroddol ateb.

383
00:30:02,830 --> 00:30:07,140
Rydym yn mynd i eisiau i yn y bôn gwneud yr un syniad

384
00:30:07,140 --> 00:30:16,530
lle rydym am gadw golwg ar y diwedd newydd y rhesi a dechrau newydd y rhesi

385
00:30:16,530 --> 00:30:18,510
a gwneud hynny drosodd a throsodd.

386
00:30:18,510 --> 00:30:22,430
Ac os yr hyn yr ydym yn cadw golwg ar y dechrau a diwedd erioed croestorri,

387
00:30:22,430 --> 00:30:29,020
hynny, nid ydym yn ei chael yn a gallwn ddychwelyd ffug.

388
00:30:29,020 --> 00:30:37,540
Felly, sut ydw i'n gwneud hynny? Dylai unrhyw un gennych unrhyw awgrymiadau neu god i mi dynnu i fyny?

389
00:30:42,190 --> 00:30:47,450
[Myfyrwyr] A oes dolen gyfnod. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Rydych yn mynd i eisiau i wneud dolen.

391
00:30:49,450 --> 00:30:51,830
>> A wnaethoch chi gael cod y gallwn i dynnu i fyny, neu beth oeddech chi'n mynd i awgrymu?

392
00:30:51,830 --> 00:30:56,340
[Myfyrwyr] Rwy'n credu hynny. >> Mae pob hawl. Mae hyn yn gwneud pethau'n haws. Beth oedd eich enw?

393
00:30:56,340 --> 00:30:57,890
[Myfyrwyr] Lucas.

394
00:31:00,140 --> 00:31:04,190
Adolygu 1. Iawn.

395
00:31:04,190 --> 00:31:13,200
Isel yw hyn yr ydym elwir yn dechrau cyn.

396
00:31:13,200 --> 00:31:17,080
Nid Up yn eithaf yr hyn yr ydym elwir ben cyn.

397
00:31:17,080 --> 00:31:22,750
A dweud y gwir, diwedd bellach o fewn y rhesi. Mae'n elfen dylem eu hystyried.

398
00:31:22,750 --> 00:31:26,890
Mor isel yw 0, i fyny yw maint y rhesi - 1,

399
00:31:26,890 --> 00:31:34,780
ac yn awr rydym yn dolennu, ac rydym yn gwirio -

400
00:31:34,780 --> 00:31:37,340
Amcana y gallwch chi gerdded drwyddo.

401
00:31:37,340 --> 00:31:41,420
Beth oedd eich ffordd o feddwl drwy hyn? Cerddwch i ni drwy eich cod.

402
00:31:41,420 --> 00:31:49,940
[Myfyrwyr] Cadarn. Edrychwch ar y gwerth tas wair yn y canol a'i gymharu â nodwydd.

403
00:31:49,940 --> 00:31:58,520
Felly, os yw'n fwy na'ch nodwydd, yna rydych am - oh, mewn gwirionedd, dylai hynny fod yn ôl.

404
00:31:58,520 --> 00:32:05,180
Rydych yn mynd i eisiau i daflu i ffwrdd yr hanner iawn, ac felly yeah, a ddylai fod y ffordd.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Felly, dylai hyn fod yn llai? A yw bod yr hyn a ddywedasoch? >> [Myfyrwyr] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Iawn. Llai.

407
00:32:10,390 --> 00:32:15,700
Felly, os yw'r hyn rydym yn edrych ar yn llai na'r hyn yr ydym ei eisiau,

408
00:32:15,700 --> 00:32:19,410
Yna, yeah, rydym am i daflu i ffwrdd yr hanner chwith,

409
00:32:19,410 --> 00:32:22,210
sy'n golygu ein bod yn diweddaru popeth rydym yn ystyried

410
00:32:22,210 --> 00:32:26,610
drwy symud isel i'r dde y rhesi.

411
00:32:26,610 --> 00:32:30,130
Mae hyn yn edrych yn dda.

412
00:32:30,130 --> 00:32:34,550
Rwy'n credu ei fod yr un mater yr ydym yn dweud ar yr un blaenorol,

413
00:32:34,550 --> 00:32:49,760
lle os isel yw 0 a hyd yn 1, yna isel + i fyny / 2 yn mynd i sefydlu i fod yr un peth eto.

414
00:32:49,760 --> 00:32:53,860
>> A hyd yn oed os nad yw hynny'n wir, mae'n dal yn fwy effeithlon o leiaf

415
00:32:53,860 --> 00:32:57,630
i ychydig daflu i ffwrdd yr elfen ydym yn unig yn edrych ar y gwyddom ei fod yn anghywir.

416
00:32:57,630 --> 00:33:03,240
Felly isel + i fyny / 2 + 1 - >> [myfyrwyr] Dylai hynny fod y ffordd arall.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Neu dylai hyn fod yn - 1 a dylai'r llall fod yn + 1.

418
00:33:05,900 --> 00:33:09,580
[Myfyrwyr] A dylai fod yn ddwbl arwydd hafal. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Myfyrwyr] Yeah.

420
00:33:14,540 --> 00:33:15,910
Iawn.

421
00:33:15,910 --> 00:33:21,280
Ac yn olaf, nawr bod gennym y 1 + - 1 peth,

422
00:33:21,280 --> 00:33:31,520
yw hi - mae'n bosibl na fydd - a yw'n bosibl i erioed isel i roi diwedd ar i fyny gyda mwy o werth nag am i fyny?

423
00:33:35,710 --> 00:33:40,320
Rwy'n credu yr unig ffordd y gall hynny ddigwydd - A yw'n bosibl? >> [Myfyrwyr] Nid wyf yn gwybod.

424
00:33:40,320 --> 00:33:45,220
Ond os bydd yn mynd cwtogi ac yna yn cael minws bod 1 ac yna - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Myfyrwyr] Byddai'n bosibl cael cyboledig i fyny.

426
00:33:49,700 --> 00:33:53,940
Rwy'n credu y dylai fod yn dda dim ond oherwydd

427
00:33:53,940 --> 00:33:58,800
ar ei gyfer yn y pen draw yn is byddai'n rhaid iddynt fod yn gyfartal, dwi'n meddwl.

428
00:33:58,800 --> 00:34:03,070
Ond os ydynt yn gyfartal, yna ni fyddem wedi gwneud y ddolen amser i ddechrau

429
00:34:03,070 --> 00:34:06,670
ac rydym fyddai dim ond wedi dychwelyd y gwerth. Felly, yr wyf yn meddwl ein bod ni'n dda yn awr.

430
00:34:06,670 --> 00:34:11,530
Hysbysiad bod hyd yn oed er bod hyn yn broblem bellach yn ailadroddus,

431
00:34:11,530 --> 00:34:17,400
yr un math o syniadau yn berthnasol lle gallwn weld sut y mae hyn mor hawdd cynnig ei hun

432
00:34:17,400 --> 00:34:23,659
i ateb recursive gan y ffaith bod ni jyst yn diweddaru'r mynegeion drosodd a throsodd,

433
00:34:23,659 --> 00:34:29,960
rydym yn gwneud y broblem yn llai ac yn llai, rydym yn canolbwyntio ar is-set o'r amrywiaeth.

434
00:34:29,960 --> 00:34:40,860
[Myfyrwyr] Os isel yw 0 a hyd yn 1, byddai'r ddau fod yn 0 + 1/2, a fyddai'n mynd i 0,

435
00:34:40,860 --> 00:34:44,429
ac yna byddai un yn + 1, byddai un yn - 1.

436
00:34:47,000 --> 00:34:50,870
[Myfyrwyr] Ble rydym yn gwirio cydraddoldeb?

437
00:34:50,870 --> 00:34:55,100
Fel os yw'r un canol mewn gwirionedd nodwydd?

438
00:34:55,100 --> 00:34:58,590
Nid ydym yn gwneud hynny ar hyn o bryd? Oh!

439
00:35:00,610 --> 00:35:02,460
Os it's -

440
00:35:05,340 --> 00:35:13,740
Ydw. Ni allwn wneud y prawf i lawr yma oherwydd gadewch i ni ddweud y canol cyntaf -

441
00:35:13,740 --> 00:35:16,430
[Myfyrwyr] Mae'n mewn gwirionedd yn hoffi â thaflu i ffwrdd y rhwymo.

442
00:35:16,430 --> 00:35:20,220
Felly, os byddwch yn ei daflu y rhwymo, rhaid i chi wirio yn gyntaf neu beth bynnag.

443
00:35:20,220 --> 00:35:23,350
Ah. Yeah. >> [Myfyrwyr] Yeah.

444
00:35:23,350 --> 00:35:29,650
Felly, erbyn hyn rydym wedi taflu un yr ydym ar hyn o bryd yn edrych ar,

445
00:35:29,650 --> 00:35:33,260
sy'n golygu ein bod bellach angen i ni hefyd

446
00:35:33,260 --> 00:35:44,810
os (tas wair [(isel + i fyny) / 2] == nodwydd), yna gallwn ddychwelyd yn wir.

447
00:35:44,810 --> 00:35:52,070
Ac os wyf yn rhoi arall neu dim ond os, mae'n golygu llythrennol yr un peth

448
00:35:52,070 --> 00:35:57,110
gan y byddai hyn wedi dychwelyd yn wir.

449
00:35:57,110 --> 00:36:01,450
Felly, byddaf yn rhoi arall os, ond does dim ots.

450
00:36:01,450 --> 00:36:10,440
>> Felly arall os yw hyn, arall y, ac mae hyn yn beth cyffredin i ei wneud

451
00:36:10,440 --> 00:36:14,340
lle hyd yn oed os mai dyma'r achos lle mae popeth yn dda yma,

452
00:36:14,340 --> 00:36:22,780
fel na ellir byth isel fod yn fwy nag am i fyny, nid yw'n werth rhesymu ynghylch a yw hynny'n wir.

453
00:36:22,780 --> 00:36:28,010
Felly, efallai y byddwch yn ogystal ddweud tra isel yn llai na neu'n hafal i

454
00:36:28,010 --> 00:36:30,720
neu tra isel yn llai na

455
00:36:30,720 --> 00:36:35,300
felly os byth y maent gyfartal neu isel yn digwydd i basio i fyny,

456
00:36:35,300 --> 00:36:40,130
yna gallwn dorri allan o hyn ddolen.

457
00:36:41,410 --> 00:36:44,630
Cwestiynau, pryderon, sylwadau?

458
00:36:47,080 --> 00:36:49,270
Iawn. Mae hyn yn edrych yn dda.

459
00:36:49,270 --> 00:36:52,230
Nawr rydym am ei wneud fath.

460
00:36:52,230 --> 00:37:04,030
Os ydym yn mynd i fy ail adolygiad, rydym yn gweld y rhifau un,

461
00:37:04,030 --> 00:37:07,550
ond erbyn hyn nad ydynt bellach er mwyn datrys.

462
00:37:07,550 --> 00:37:12,840
Ac rydym am i weithredu fath ddefnyddio unrhyw algorithm yn O o log n n.

463
00:37:12,840 --> 00:37:17,240
Felly, pa algorithm ydych chi'n meddwl y dylem weithredu yma? >> [Myfyrwyr] fath Cyfuno.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Cyfuno fath yw O (n log n), felly dyna beth ydym yn mynd i'w wneud.

465
00:37:23,810 --> 00:37:26,680
Ac mae'r broblem yn mynd i fod yn eithaf tebyg,

466
00:37:26,680 --> 00:37:31,920
lle mae'n yn addas i ateb ailadroddus.

467
00:37:31,920 --> 00:37:35,580
Gallwn hefyd ddod o hyd i ateb ailadroddol os ydym am,

468
00:37:35,580 --> 00:37:42,540
ond bydd dychweliad yn haws yma ac y dylem wneud dychweliad.

469
00:37:45,120 --> 00:37:49,530
Amcana y byddwn yn cerdded drwy uno fath yn gyntaf,

470
00:37:49,530 --> 00:37:54,280
er bod fideo hyfryd ar uno fath eisoes. [Chwerthin]

471
00:37:54,280 --> 00:37:59,780
Felly uno fath mae yna - yr wyf yn gwastraffu cymaint o'r papur hwn.

472
00:37:59,780 --> 00:38:02,080
O, dim ond un sydd ar ôl.

473
00:38:02,080 --> 00:38:03,630
Felly uno.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Iawn.

476
00:38:29,910 --> 00:38:33,460
Uno yn cymryd ddau arae ar wahân.

477
00:38:33,460 --> 00:38:36,780
Unigol y ddau arae ill dau datrys.

478
00:38:36,780 --> 00:38:40,970
Felly, mae hyn array, 1, 3, 5, didoli. Mae hyn yn array, 0, 2, 4, didoli.

479
00:38:40,970 --> 00:38:46,710
Nawr yr hyn y dylai ei wneud yw uno cyfuno i mewn i amrywiaeth un sydd ei hun yn datrys.

480
00:38:46,710 --> 00:38:57,130
Felly, rydym am amrywiaeth o maint 6 sy'n mynd i gael yr elfennau hyn y tu mewn ohono

481
00:38:57,130 --> 00:38:59,390
er mwyn datrys.

482
00:38:59,390 --> 00:39:03,390
>> Ac fel y gallwn fanteisio ar y ffaith bod y ddau arae yn cael eu datrys

483
00:39:03,390 --> 00:39:06,800
i wneud hyn mewn pryd llinol,

484
00:39:06,800 --> 00:39:13,510
ystyr amser llinol os yw hyn yn amrywiaeth x maint ac mae hyn yn y maint,

485
00:39:13,510 --> 00:39:20,970
yna dylai'r algorithm cyfanswm O (x + y). Iawn.

486
00:39:20,970 --> 00:39:23,150
Felly awgrymiadau.

487
00:39:23,150 --> 00:39:26,030
[Myfyrwyr] allem ddechrau o'r chwith?

488
00:39:26,030 --> 00:39:30,150
Felly byddwch yn rhoi o 0 i lawr yn gyntaf ac yna'r 1 ac yna dyma ydych chi yn y 2.

489
00:39:30,150 --> 00:39:33,320
Felly, mae'n fath o fel bod gennych tab sydd wedi symud i'r dde. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Ar gyfer y ddau o'r rhain araeau os ydym yn unig yn canolbwyntio ar yr elfen leftmost.

491
00:39:41,070 --> 00:39:43,530
Gan fod y ddwy araeau cael eu datrys, rydym yn gwybod bod y 2 elfen

492
00:39:43,530 --> 00:39:46,920
yw'r elfennau lleiaf yn y naill amrywiaeth.

493
00:39:46,920 --> 00:39:53,500
Felly mae hynny'n golygu bod yn rhaid i 1 o'r rheiny 2 elfen yr elfen lleiaf yn ein amrywiaeth unedig.

494
00:39:53,500 --> 00:39:58,190
Fel mae'n digwydd bod y lleiaf yw'r un ar y dde y tro hwn.

495
00:39:58,190 --> 00:40:02,580
Felly, rydym yn cymryd 0, rhowch ef ar y chwith oherwydd 0 yn llai nag 1,

496
00:40:02,580 --> 00:40:08,210
felly cymerwch 0, rhowch i mewn i'n safle cyntaf, ac yna rydym yn diweddaru hwn

497
00:40:08,210 --> 00:40:12,070
i yn awr yn canolbwyntio ar yr elfen gyntaf.

498
00:40:12,070 --> 00:40:14,570
Ac yn awr rydym yn ailadrodd.

499
00:40:14,570 --> 00:40:20,670
Felly, yn awr rydym yn cymharu 2 ac 1. 1 yn llai, felly byddwn yn mewnosod 1.

500
00:40:20,670 --> 00:40:25,300
Rydym yn diweddaru'r pwyntydd i bwyntio at y boi.

501
00:40:25,300 --> 00:40:33,160
Nawr rydym yn ei wneud eto, felly 2. Bydd hyn yn diweddaru, cymharu'r rhain 2, 3.

502
00:40:33,160 --> 00:40:37,770
Mae hwn yn diweddaru, yna 4 a 5.

503
00:40:37,770 --> 00:40:42,110
Felly dyna uno.

504
00:40:42,110 --> 00:40:49,010
>> Dylai fod yn weddol amlwg ei fod yn amser llinol ers i ni yn unig yn mynd ar draws pob elfen unwaith.

505
00:40:49,010 --> 00:40:55,980
A dyna yw'r cam mwyaf i weithredu'r uno fath yn gwneud hyn.

506
00:40:55,980 --> 00:40:59,330
Ac nid yw mor anodd.

507
00:40:59,330 --> 00:41:15,020
Mae pethau cwpl i chi boeni am yw gadewch i ni ddweud ein bod yn cyfuno 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Yn yr achos hwn rydym yn y pen draw yn y sefyllfa lle mae hyn yn un yn mynd i fod yn llai,

509
00:41:30,930 --> 00:41:36,160
yna rydym yn diweddaru'r pwyntydd, mae hyn yn un yn mynd i fod yn llai, diweddaru'r hyn,

510
00:41:36,160 --> 00:41:41,280
hyn yn un 'llai, ac yn awr mae'n rhaid i chi gydnabod

511
00:41:41,280 --> 00:41:44,220
pan fyddwch wedi mewn gwirionedd yn rhedeg allan o elfennau i gymharu â hwy.

512
00:41:44,220 --> 00:41:49,400
Ers i ni wedi defnyddio y casgliad cyfan,

513
00:41:49,400 --> 00:41:55,190
popeth yn y casgliad bellach yn mewnosod i mewn yma.

514
00:41:55,190 --> 00:42:02,040
Felly, os ydym byth yn rhedeg i mewn i'r pwynt lle mae un o'n araeau yn cael ei uno yn gyfan gwbl yn barod,

515
00:42:02,040 --> 00:42:06,510
yna rydym yn unig yn cymryd yr holl elfennau y rhesi eraill a rhowch nhw i mewn i ddiwedd y rhesi.

516
00:42:06,510 --> 00:42:13,630
Felly gallwn rhowch 4, 5, 6. Iawn.

517
00:42:13,630 --> 00:42:18,070
Dyna un peth i wylio allan amdano.

518
00:42:22,080 --> 00:42:26,120
Gweithredu a ddylai fod cam 1.

519
00:42:26,120 --> 00:42:32,600
Cyfuno didoli wedyn ar sail hynny, mae'n 2 gam, 2 cam gwirion.

520
00:42:38,800 --> 00:42:42,090
Gadewch i 'jyst roi'r casgliad.

521
00:42:57,920 --> 00:43:05,680
Felly uno fath, cam 1 yw recursively torri'r amrywiaeth i mewn i hanner.

522
00:43:05,680 --> 00:43:09,350
Rhannu Felly, mae hyn yn hanner amrywiaeth.

523
00:43:09,350 --> 00:43:22,920
Erbyn hyn mae gennym 4, 15, 16, 50 ac 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Ac yn awr rydym yn ei wneud eto, ac rydym yn rhannu'r rhain yn hanner.

525
00:43:25,800 --> 00:43:27,530
'N annhymerus' jyst yn gwneud hynny ar yr ochr hon.

526
00:43:27,530 --> 00:43:34,790
Felly 4, 15 ac 16, 50.

527
00:43:34,790 --> 00:43:37,440
Byddem yn gwneud yr un peth dros yma.

528
00:43:37,440 --> 00:43:40,340
Ac yn awr rydym yn ei rannu'n hanner eto.

529
00:43:40,340 --> 00:43:51,080
Ac mae gennym 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Felly, dyna yw ein achos sylfaenol.

531
00:43:53,170 --> 00:44:00,540
Unwaith y bydd y araeau o faint 1, yna rydym yn dod i ben gyda hollti i mewn i hanner.

532
00:44:00,540 --> 00:44:03,190
>> Nawr beth ydym yn ei wneud â hyn?

533
00:44:03,190 --> 00:44:15,730
Rydym yn y pen draw bydd hyn hefyd yn torri i lawr i 8, 23, 42, a 108.

534
00:44:15,730 --> 00:44:24,000
Felly nawr ein bod yn y fan hon, yn awr gam dau o uno fath yn unig yw uno parau i y rhestrau.

535
00:44:24,000 --> 00:44:27,610
Felly, rydym am i uno rhain. Rydym yn unig yn galw uno.

536
00:44:27,610 --> 00:44:31,410
Rydym yn gwybod y bydd uno ddychwelyd y rhain er mwyn datrys.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Nawr rydym am i uno rhain, a fydd yn dychwelyd rhestr gyda rheini er didoli,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Rydym yn cyfuno rhai - Ni allaf ysgrifennu - 8, 23 a 42, 108.

541
00:44:57,380 --> 00:45:02,890
Felly, rydym wedi barau unedig unwaith.

542
00:45:02,890 --> 00:45:05,140
Nawr rydym yn unig uno eto.

543
00:45:05,140 --> 00:45:10,130
Sylwch fod pob un o'r rhestrau hyn yn cael ei ddidoli yn ei hun,

544
00:45:10,130 --> 00:45:15,220
ac yna gallwn dim ond uno rhestrau hyn i gael rhestr o faint 4 sy'n cael ei drefnu

545
00:45:15,220 --> 00:45:19,990
ac yn cyfuno'r ddwy restr i gael rhestr o faint 4 sy'n cael ei drefnu.

546
00:45:19,990 --> 00:45:25,710
Ac yn olaf, gallwn gyfuno'r rhai ddwy restr o faint 4 i gael un rhestr o faint 8 sy'n cael ei datrys.

547
00:45:25,710 --> 00:45:34,030
Felly, i weld bod hyn yn gyffredinol n n log, yr ydym eisoes yn gweld bod uno yn llinol,

548
00:45:34,030 --> 00:45:40,390
felly pan fyddwn yn delio â uno'r rhain, felly fel y gost gyffredinol o uno

549
00:45:40,390 --> 00:45:43,410
ar gyfer y ddwy restr yn unig 2 oherwydd -

550
00:45:43,410 --> 00:45:49,610
Neu yn dda, mae'n O n, ond n yma yn unig y 2 elfen, felly mae'n 2.

551
00:45:49,610 --> 00:45:52,850
A bydd y 2 yn 2 a bydd y rhain 2 yn 2 a bydd y 2 o 2,

552
00:45:52,850 --> 00:45:58,820
hynny ar draws yr holl uno y mae angen ei wneud, rydym yn y pen draw yn gwneud n.

553
00:45:58,820 --> 00:46:03,210
Fel 2 + 2 + 2 + 2 yn 8, sef n,

554
00:46:03,210 --> 00:46:08,060
felly y gost o uno yn y set hon yn n.

555
00:46:08,060 --> 00:46:10,810
Ac yna yr un peth yma.

556
00:46:10,810 --> 00:46:16,980
Byddwn yn cyfuno'r 2, yna y 2, ac yn unigol bydd hyn yn uno yn cymryd pedwar gweithrediad,

557
00:46:16,980 --> 00:46:23,610
Bydd hyn yn uno yn cymryd pedwar gweithrediad, ond unwaith eto, rhwng pob un o'r rhain,

558
00:46:23,610 --> 00:46:29,030
rydym yn y pen draw cyfuno n phethau cyfanswm, ac felly y cam hwn yn cymryd n.

559
00:46:29,030 --> 00:46:33,670
Ac felly mae pob lefel yn cymryd elfennau n cael eu huno.

560
00:46:33,670 --> 00:46:36,110
>> A faint o lefelau sydd yna?

561
00:46:36,110 --> 00:46:40,160
Ar bob lefel, mae ein casgliad yn tyfu yn ôl maint 2.

562
00:46:40,160 --> 00:46:44,590
Dyma ein araeau o faint 1, dyma maen nhw'n maint 2, dyma maen nhw'n maint 4,

563
00:46:44,590 --> 00:46:46,470
ac yn olaf, maen nhw'n maint 8.

564
00:46:46,470 --> 00:46:56,450
Felly, gan ei fod yn dyblu, mae yn mynd i fod cyfanswm o log n o'r lefelau hyn.

565
00:46:56,450 --> 00:47:02,090
Felly, gyda log n lefelau, bob lefel unigol gymryd n gweithrediadau cyfanswm,

566
00:47:02,090 --> 00:47:05,720
rydym yn cael log n n algorithm.

567
00:47:05,720 --> 00:47:07,790
Cwestiynau?

568
00:47:08,940 --> 00:47:13,320
A yw pobl sydd eisoes wedi gwneud cynnydd ar sut i weithredu hyn?

569
00:47:13,320 --> 00:47:18,260
A oes unrhyw un eisoes mewn cyflwr lle gall Fi jyst dynnu i fyny eu cod?

570
00:47:20,320 --> 00:47:22,260
Gallaf roi munud.

571
00:47:24,770 --> 00:47:27,470
Mae hyn yn un yn mynd i fod yn hirach.

572
00:47:27,470 --> 00:47:28,730
Byddwn yn argymell ailddigwydd -

573
00:47:28,730 --> 00:47:30,510
Nid oes rhaid i chi wneud dychweliad i uno

574
00:47:30,510 --> 00:47:33,750
oherwydd mae gwneud dychweliad i uno, rydych chi'n mynd i gael i basio criw o wahanol feintiau.

575
00:47:33,750 --> 00:47:37,150
Gallwch, ond mae'n blino.

576
00:47:37,150 --> 00:47:43,720
Ond dychweliad ar gyfer trefnu ei hun yn eithaf hawdd.

577
00:47:43,720 --> 00:47:49,190
'Ch jyst llythrennol ffonio fath ar hanner chwith, math ar hanner cywir. Iawn.

578
00:47:51,770 --> 00:47:54,860
Dylai unrhyw un gennych unrhyw beth y gallaf ei dynnu i fyny eto?

579
00:47:54,860 --> 00:47:57,540
Neu arall 'n annhymerus' roi munud.

580
00:47:58,210 --> 00:47:59,900
Iawn.

581
00:47:59,900 --> 00:48:02,970
Dylai unrhyw un â rhywbeth y gallwn weithio gyda?

582
00:48:05,450 --> 00:48:09,680
Neu arall byddwn yn gweithio yn unig gyda hyn ac yna ehangu oddi yno.

583
00:48:09,680 --> 00:48:14,050
>> Dylai unrhyw un yn cael mwy na hyn y gallaf ei dynnu i fyny?

584
00:48:14,050 --> 00:48:17,770
[Myfyrwyr] Yeah. Gallwch dynnu i fyny fy un i. >> Mae pob hawl.

585
00:48:17,770 --> 00:48:19,730
Ie!

586
00:48:22,170 --> 00:48:25,280
[Myfyrwyr] Roedd llawer o amodau. >> O, saethu. Allwch chi -

587
00:48:25,280 --> 00:48:28,110
[Myfyrwyr] yn rhaid i mi achub. >> Yeah.

588
00:48:32,420 --> 00:48:35,730
Felly, rydym yn ddim yn gwneud y uno ar wahân.

589
00:48:35,730 --> 00:48:38,570
O, ond nid yw mor ddrwg.

590
00:48:39,790 --> 00:48:41,650
Iawn.

591
00:48:41,650 --> 00:48:47,080
Felly fath yn galw ei hun yn unig mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Eglurwch i ni beth mergeSortHelp yn ei wneud.

593
00:48:49,530 --> 00:48:55,700
[Myfyrwyr] MergeSortHelp 'n bert lawer yn y ddau brif gam,

594
00:48:55,700 --> 00:49:01,270
a fydd yn datrys pob hanner y rhesi, ac yna i uno'r ddau ohonynt.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Iawn, felly rhowch i mi ail.

596
00:49:10,850 --> 00:49:13,210
Rwy'n credu bod hyn - >> [myfyrwyr] angen i mi -

597
00:49:17,100 --> 00:49:19,400
Yeah. Rwy'n colli rhywbeth.

598
00:49:19,400 --> 00:49:23,100
Yn uno, yr wyf yn sylweddoli bod angen i mi greu casgliad newydd

599
00:49:23,100 --> 00:49:26,530
oherwydd ni allwn wneud hynny ar waith. >> Ydy. Nid ydych yn gallu. Cywir.

600
00:49:26,530 --> 00:49:28,170
[Myfyrwyr] Felly, yr wyf yn creu amrywiaeth newydd.

601
00:49:28,170 --> 00:49:31,510
Wedi anghofio ar ddiwedd uno i ail-newid.

602
00:49:31,510 --> 00:49:34,490
Iawn. Mae angen amrywiaeth newydd.

603
00:49:34,490 --> 00:49:41,000
Yn merge fath, mae hyn yn bron bob amser yn wir.

604
00:49:41,000 --> 00:49:44,340
Rhan o gost algorithm gwell amser-doeth

605
00:49:44,340 --> 00:49:47,310
bron bob amser yn angen i ddefnyddio cof ychydig yn fwy.

606
00:49:47,310 --> 00:49:51,570
Felly yma, ni waeth sut yr ydych yn ei wneud uno fath,

607
00:49:51,570 --> 00:49:54,780
byddech yn anochel angen i chi ddefnyddio rhai cof ychwanegol.

608
00:49:54,780 --> 00:49:58,240
Ef neu hi yn creu amrywiaeth newydd.

609
00:49:58,240 --> 00:50:03,400
Ac yna ydych yn dweud ar y diwedd, ond mae angen i gopïo amrywiaeth newydd i'r casgliad gwreiddiol.

610
00:50:03,400 --> 00:50:04,830
[Myfyrwyr] yr wyf yn meddwl hynny, yeah.

611
00:50:04,830 --> 00:50:08,210
Nid wyf yn gwybod os sy'n gweithio o ran gyfrif trwy gyfeirio neu beth bynnag -

612
00:50:08,210 --> 00:50:11,650
Yeah, bydd yn gweithio. >> [Myfyrwyr] Iawn.

613
00:50:20,620 --> 00:50:24,480
A wnaethoch chi roi cynnig ar redeg hyn? >> [Myfyrwyr] Na, ddim eto. >> Iawn.

614
00:50:24,480 --> 00:50:28,880
Ceisiwch redeg, ac yna byddaf yn siarad am y peth am eiliad.

615
00:50:28,880 --> 00:50:35,200
[Myfyrwyr] angen i mi gael yr holl prototeipiau swyddogaeth a phopeth, fodd bynnag, dde?

616
00:50:37,640 --> 00:50:40,840
Mae'r prototeipiau swyddogaeth. O, rydych yn golygu fel - Ydy.

617
00:50:40,840 --> 00:50:43,040
Trefnu yn galw mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Felly, er mwyn i fath i alw mergeSortHelp, mae'n rhaid i mergeSortHelp naill ai wedi cael eu diffinio

619
00:50:47,390 --> 00:50:56,370
cyn didoli neu ni jyst angen y prototeip. Jyst adysgrifia a bastio hynny.

620
00:50:56,370 --> 00:50:59,490
Ac yn yr un modd, mergeSortHelp yn galw uno,

621
00:50:59,490 --> 00:51:03,830
ond nid yw uno wedi cael ei ddiffinio hyd yma, er mwyn i ni dim ond gadewch i mergeSortHelp gwybod

622
00:51:03,830 --> 00:51:08,700
bod dyna beth uno yn mynd i edrych fel, a dyna hynny.

623
00:51:09,950 --> 00:51:15,730
Felly mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Mae gennym mater yma lle nad oes gennym achos sylfaenol.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp yn ailadroddus, felly recursive unrhyw swyddogaeth

626
00:51:38,110 --> 00:51:42,610
yn mynd i angen rhyw fath o achos sylfaenol i wybod pryd i roi'r gorau recursively galw ei hun.

627
00:51:42,610 --> 00:51:45,590
Beth yw ein achos sylfaenol yn mynd i gael ei yma? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Myfyrwyr] Os yw maint yw 1? >> [Bowden] Ydw.

629
00:51:49,110 --> 00:51:56,220
Felly, fel y gwelsom iawn yno, rydym yn rhoi'r gorau i araeau hollti

630
00:51:56,220 --> 00:52:01,850
unwaith y byddwn yn mynd i mewn araeau o faint 1, sydd yn anochel yn cael eu didoli eu hunain.

631
00:52:01,850 --> 00:52:09,530
Felly os maint hafal i 1, rydym yn gwybod y casgliad yn cael ei datrys eisoes,

632
00:52:09,530 --> 00:52:12,970
er mwyn i ni fynd yn ôl.

633
00:52:12,970 --> 00:52:16,880
>> Hysbysiad bod yn ddi-rym, felly nid ydym yn dychwelyd unrhyw beth penodol, rydym yn unig yn dychwelyd.

634
00:52:16,880 --> 00:52:19,580
Iawn. Felly, dyna ein achos sylfaenol.

635
00:52:19,580 --> 00:52:27,440
Amcana y gallai ein achos sylfaenol hefyd fod os ydym yn digwydd bod yn cyfuno amrywiaeth o faint 0,

636
00:52:27,440 --> 00:52:30,030
mae'n debyg am roi'r gorau ar ryw adeg,

637
00:52:30,030 --> 00:52:33,610
fel y gallwn ddweud faint yn llai na 2 neu llai na neu'n hafal i 1

638
00:52:33,610 --> 00:52:37,150
fel y bydd hyn yn gweithio ar gyfer unrhyw amrywiaeth yn awr.

639
00:52:37,150 --> 00:52:38,870
Iawn.

640
00:52:38,870 --> 00:52:42,740
Felly, dyna ein achos sylfaenol.

641
00:52:42,740 --> 00:52:45,950
Nawr ydych chi eisiau i gerdded ni drwy uno?

642
00:52:45,950 --> 00:52:49,140
Beth mae'r holl achosion hyn yn ei olygu?

643
00:52:49,140 --> 00:52:54,480
Up yma, rydym yn unig yn gwneud yr un syniad, y -

644
00:52:56,970 --> 00:53:02,470
[Myfyrwyr] angen i mi eu pasio maint gyda'r holl alwadau mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
I ychwanegu faint fel gynradd ychwanegol ac nid yw yno, fel maint / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] O, maint / 2, maint / 2. >> [Myfyrwyr] Yeah, a hefyd yn y swyddogaeth uchod yn ogystal.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Yma? >> [Myfyrwyr] Dim ond maint. >> [Bowden] Oh. Maint, faint? >> [Myfyrwyr] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Iawn.

649
00:53:23,010 --> 00:53:26,580
Gadewch i mi feddwl am eiliad.

650
00:53:26,580 --> 00:53:28,780
A ydym yn rhedeg i mewn i fater?

651
00:53:28,780 --> 00:53:33,690
Rydym bob amser yn trin y chwith fel 0. >> [Myfyrwyr] Rhif

652
00:53:33,690 --> 00:53:36,340
Mae hynny'n anghywir hefyd. Mae'n ddrwg gennym. Dylai fod yn dechrau. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Iawn. Rwy'n hoffi bod yn well.

654
00:53:39,230 --> 00:53:43,880
A diwedd. Iawn.

655
00:53:43,880 --> 00:53:47,200
Felly nawr rydych am i ni drwy gerdded uno? >> [Myfyrwyr] Iawn.

656
00:53:47,200 --> 00:53:52,150
Im 'jyst yn cerdded drwy'r amrywiaeth newydd yr wyf wedi'u creu.

657
00:53:52,150 --> 00:53:57,420
Ei faint yw maint y rhan y rhesi yr ydym am ei gael ei datrys

658
00:53:57,420 --> 00:54:03,460
ac yn ceisio dod o hyd i'r elfen y dylwn ei roi yn y cam casgliad newydd.

659
00:54:03,460 --> 00:54:10,140
Felly, i wneud hynny, yn gyntaf dwi'n gweld a yw'r hanner chwith y rhesi yn parhau i gael elfennau unrhyw mwy,

660
00:54:10,140 --> 00:54:14,260
ac os nad yw'n gwneud hynny, yna byddwch yn mynd i lawr at y cyflwr arall, a dim ond yn dweud

661
00:54:14,260 --> 00:54:20,180
iawn, rhaid iddo fod yn yr amrywiaeth cywir, a byddwn yn rhoi hynny yn y mynegai presennol newArray.

662
00:54:20,180 --> 00:54:27,620
>> Ac yna wahanol, yr wyf i'n gwirio a yw'r ochr dde y rhesi yn cael ei orffen hefyd,

663
00:54:27,620 --> 00:54:30,630
ac yn yr achos Fi jyst ei roi yn y chwith.

664
00:54:30,630 --> 00:54:34,180
Ni allai fod mewn gwirionedd yn angenrheidiol. Dwi ddim yn siŵr.

665
00:54:34,180 --> 00:54:40,970
Ond beth bynnag, y ddau arall gwirio pa un o'r ddau yn llai yn y chwith neu i'r dde.

666
00:54:40,970 --> 00:54:49,770
A hefyd ym mhob achos, rwy'n incrementing pa un bynnag dalfan I hicyn.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Iawn.

668
00:54:52,040 --> 00:54:53,840
Mae hynny'n edrych yn dda.

669
00:54:53,840 --> 00:54:58,800
Oes gan unrhyw un sylwadau neu bryderon neu gwestiynau?

670
00:55:00,660 --> 00:55:07,720
Felly, y pedwar achos bod yn rhaid inni ddod â phethau i mewn dim ond bod - neu mae'n edrych fel pump -

671
00:55:07,720 --> 00:55:13,100
ond rhaid i ni ystyried a yw'r amrywiaeth chwith wedi rhedeg allan o bethau mae angen i ni uno,

672
00:55:13,100 --> 00:55:16,390
a yw'r amrywiaeth cywir wedi rhedeg allan o bethau mae angen i ni gyfuno -

673
00:55:16,390 --> 00:55:18,400
Rwy'n pwyntio at ddim byd.

674
00:55:18,400 --> 00:55:21,730
Felly, os yr amrywiaeth chwith wedi rhedeg allan o pethau neu y casgliad cywir wedi rhedeg allan o bethau.

675
00:55:21,730 --> 00:55:24,320
Mae'r rheini'n ddau achos.

676
00:55:24,320 --> 00:55:30,920
Rydym hefyd angen achos dibwys a yw'r peth chwith yn llai na'r peth iawn.

677
00:55:30,920 --> 00:55:33,910
Yna, rydym yn awyddus i ddewis y peth chwith.

678
00:55:33,910 --> 00:55:37,630
Dyna'r yr achosion.

679
00:55:37,630 --> 00:55:40,990
Felly, mae hyn yn iawn, felly dyna hynny.

680
00:55:40,990 --> 00:55:46,760
Array chwith. Mae'n 1, 2, 3. Iawn. Felly ie, y rhai yn y pedwar peth y gallem eisiau ei wneud.

681
00:55:50,350 --> 00:55:54,510
Ac ni fyddwn yn mynd dros iteraidd ateb.

682
00:55:54,510 --> 00:55:55,980
Ni fyddwn yn argymell -

683
00:55:55,980 --> 00:56:03,070
Cyfuno fath yn enghraifft o swyddogaeth sydd yn y ddau heb gynffon recursive,

684
00:56:03,070 --> 00:56:07,040
nid yw'n hawdd i'w wneud yn gynffon recursive,

685
00:56:07,040 --> 00:56:13,450
ond hefyd nid yw'n hawdd iawn i'w wneud yn ailadroddol.

686
00:56:13,450 --> 00:56:16,910
Mae hyn yn hawdd iawn.

687
00:56:16,910 --> 00:56:19,170
Mae hyn yn gweithredu o uno fath,

688
00:56:19,170 --> 00:56:22,140
uno, ni waeth beth ydych yn ei wneud, rydych chi'n mynd i adeiladu uno.

689
00:56:22,140 --> 00:56:29,170
>> Felly gyfuno math a adeiladwyd ar ben uno recursively yn unig yw tair llinell hyn.

690
00:56:29,170 --> 00:56:34,700
Iteraidd, mae'n fwy blino ac yn fwy anodd i feddwl amdano.

691
00:56:34,700 --> 00:56:41,860
Ond sylwch nad yw'n gynffon recursive ers mergeSortHelp - pan fydd yn galw ei hun -

692
00:56:41,860 --> 00:56:46,590
mae angen o hyd i wneud pethau ar ôl hyn yn dychwelyd galwadau ailadroddus.

693
00:56:46,590 --> 00:56:50,830
Felly, rhaid i'r ffrâm pentwr yn parhau i fodoli hyd yn oed wedi galw hyn.

694
00:56:50,830 --> 00:56:54,170
Ac yna pan fyddwch yn ffonio hyn, rhaid i'r ffrâm pentwr yn parhau i fodoli

695
00:56:54,170 --> 00:56:57,780
oherwydd hyd yn oed ar ôl yr alwad honno, rydym yn dal angen i uno.

696
00:56:57,780 --> 00:57:01,920
Ac mae'n nontrivial i wneud y gynffon ailadroddus.

697
00:57:04,070 --> 00:57:06,270
Cwestiynau?

698
00:57:08,300 --> 00:57:09,860
Mae pob hawl.

699
00:57:09,860 --> 00:57:13,400
Felly, mynd yn ôl i ddidoli - oh, mae dau beth rwyf eisiau dangos. Iawn.

700
00:57:13,400 --> 00:57:17,840
Mynd yn ôl i ddidoli, byddwn yn gwneud hyn yn gyflym.

701
00:57:17,840 --> 00:57:21,030
Neu chwilio. Trefnu? Trefnu. Yeah.

702
00:57:21,030 --> 00:57:22,730
Mynd yn ôl at y dechreuadau fath.

703
00:57:22,730 --> 00:57:29,870
Rydym am i greu algorithm sy'n didoli'r casgliad gan ddefnyddio unrhyw algorithm

704
00:57:29,870 --> 00:57:33,660
yng O n.

705
00:57:33,660 --> 00:57:40,860
Felly, sut mae hyn yn bosibl? A oes unrhyw un yn cael unrhyw fath o -

706
00:57:40,860 --> 00:57:44,300
Yr awgrymais yn blaen yn -

707
00:57:44,300 --> 00:57:48,300
Os ydym chi ar fin i wella o log n n i O n,

708
00:57:48,300 --> 00:57:51,450
rydym wedi gwella ein algorithm amser-ddoeth,

709
00:57:51,450 --> 00:57:55,250
sy'n golygu beth ydym yn mynd i angen i wneud i wneud iawn am hynny?

710
00:57:55,250 --> 00:57:59,520
[Myfyrwyr] Space. >> Yeah. Rydym yn mynd i fod yn defnyddio mwy o le.

711
00:57:59,520 --> 00:58:04,490
Ac nid hyd yn oed mwy o le, mae'n le gynt a chynt mwy.

712
00:58:04,490 --> 00:58:14,320
Felly, yr wyf yn meddwl y math hwn o algorithm yn rhywbeth ffug, ffug polynom -

713
00:58:14,320 --> 00:58:18,980
ffug - ni allaf gofio. Rhywbeth ffug.

714
00:58:18,980 --> 00:58:22,210
Ond mae'n oherwydd mae angen i ni ddefnyddio cymaint o le

715
00:58:22,210 --> 00:58:28,610
bod hyn yn gyraeddadwy ond nid yn realistig.

716
00:58:28,610 --> 00:58:31,220
>> A sut rydym yn cyflawni hyn?

717
00:58:31,220 --> 00:58:36,810
Gallwn gyflawni hyn os rydym yn gwarantu y bydd unrhyw elfen benodol yn yr amrywiaeth

718
00:58:36,810 --> 00:58:39,600
yn is na maint penodol.

719
00:58:42,070 --> 00:58:44,500
Felly, gadewch i 'jyst dweud bod maint yn 200,

720
00:58:44,500 --> 00:58:48,130
unrhyw elfen mewn arae yn is na maint 200.

721
00:58:48,130 --> 00:58:51,080
Ac mae hyn mewn gwirionedd yn realistig iawn.

722
00:58:51,080 --> 00:58:58,660
Gallwch yn hawdd iawn, mae gennym gasgliad eich bod yn gwybod popeth ynddo

723
00:58:58,660 --> 00:59:00,570
yn mynd i fod yn llai na rhai rhif.

724
00:59:00,570 --> 00:59:07,400
Fel os oes gennych rywfaint fector enfawr i ledaenu neu rywbeth

725
00:59:07,400 --> 00:59:11,810
ond eich bod yn gwybod popeth yn mynd i fod rhwng 0 a 5,

726
00:59:11,810 --> 00:59:14,790
yna mae'n mynd i fod yn sylweddol gyflymach i wneud hyn.

727
00:59:14,790 --> 00:59:17,930
Ac mae'r rhwymo ar unrhyw un o'r elfennau yw 5,

728
00:59:17,930 --> 00:59:21,980
felly mae hyn yn rhwymo, hynny yw faint o gof rydych chi'n mynd i gael ei ddefnyddio.

729
00:59:21,980 --> 00:59:26,300
Felly y rwymo yw 200.

730
00:59:26,300 --> 00:59:32,960
Mewn theori, mae yna bob amser rwymo gan y gall cyfanrif ond fod hyd at 4 biliwn,

731
00:59:32,960 --> 00:59:40,600
ond mae hynny'n afrealistig ers hynny byddem yn defnyddio gofod

732
00:59:40,600 --> 00:59:44,400
ar y drefn o 4 biliwn. Felly dyna afrealistig.

733
00:59:44,400 --> 00:59:47,060
Ond yma byddwn yn dweud ein rhwymo yw 200.

734
00:59:47,060 --> 00:59:59,570
Y tric i wneud yn O o n yn yr ydym yn gwneud amrywiaeth arall a elwir yn cyfrif o faint BOUND.

735
00:59:59,570 --> 01:00:10,470
Felly, mewn gwirionedd, mae hwn yn llwybr byr i - Dydw i ddim mewn gwirionedd yn gwybod os Clang yn gwneud hyn.

736
01:00:11,150 --> 01:00:15,330
Ond yn GCC o leiaf - Clang dybio I'm mae'n rhy -

737
01:00:15,330 --> 01:00:18,180
Bydd hyn yn unig ymgychwyn yr amrywiaeth gyfan i fod yn 0au.

738
01:00:18,180 --> 01:00:25,320
Felly, os nad wyf am wneud hynny, yna gallwn ar wahân ei wneud ar gyfer (i int = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND: i + +) ac yn cyfrif [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Felly, nawr mae popeth yn cael ei ymgychwyn i 0.

741
01:00:35,260 --> 01:00:39,570
I ailadrodd dros fy array,

742
01:00:39,570 --> 01:00:51,920
a beth rwy'n ei wneud yw fy mod i'n cyfrif y nifer o bob un - Gadewch i fynd i lawr yma.

743
01:00:51,920 --> 01:00:55,480
Mae gennym 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Beth wyf yn cyfrif yw nifer y digwyddiadau o bob un o'r elfennau hynny.

745
01:01:00,010 --> 01:01:03,470
Gadewch i ni mewn gwirionedd yn ychwanegu ychydig mwy yma gyda rhai ailddarllediadau.

746
01:01:03,470 --> 01:01:11,070
Felly, y gwerth sydd gennym yma, y ​​gwerth sy'n mynd i fod yn array [i].

747
01:01:11,070 --> 01:01:14,850
Felly, gallai fod yn Val 4 neu 8 neu beth bynnag.

748
01:01:14,850 --> 01:01:18,870
Ac yn awr rwy'n cyfrif faint o'r gwerth hwnnw rwyf wedi ei weld,

749
01:01:18,870 --> 01:01:21,230
felly cyfrif [val] + +;

750
01:01:21,230 --> 01:01:29,430
Ar ôl gwneud hyn, yn cyfrif yn mynd i edrych rhywbeth fel 0001.

751
01:01:29,430 --> 01:01:42,190
Gadewch i ni wneud cyfrifiadau [val] - BOUND + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nawr bod dim ond i gyfrif am y ffaith ein bod yn dechrau o 0.

753
01:01:48,230 --> 01:01:50,850
Felly, os 200 yn cael ei mynd i fod yn ein rhif mwyaf,

754
01:01:50,850 --> 01:01:54,720
Yna, 0-200 yw 201 pethau.

755
01:01:54,720 --> 01:02:01,540
Felly cyfrif, bydd yn edrych fel 00,001 gan fod gennym un 4.

756
01:02:01,540 --> 01:02:10,210
Yna, bydd gennym 0001 lle byddwn yn cael 1 yn y mynegai 8fed cyfrif.

757
01:02:10,210 --> 01:02:14,560
Bydd gennym 2 yn y mynegai 23ain o gyfrif.

758
01:02:14,560 --> 01:02:17,630
Bydd gennym 2 yn y mynegai 42eg o gyfrif.

759
01:02:17,630 --> 01:02:21,670
Felly, gallwn ddefnyddio cyfrif.

760
01:02:34,270 --> 01:02:44,920
Felly num_of_item = cyfrif [i].

761
01:02:44,920 --> 01:02:52,540
Ac felly os num_of_item yw 2, sy'n golygu ein bod am osod 2 y nifer i

762
01:02:52,540 --> 01:02:55,290
yn ein casgliad didoli.

763
01:02:55,290 --> 01:03:02,000
Felly, mae angen i ni gadw golwg ar ba mor bell yr ydym yn i mewn i'r casgliad.

764
01:03:02,000 --> 01:03:05,470
= Mynegai Felly 0.

765
01:03:05,470 --> 01:03:09,910
Array - 'n annhymerus' jyst ysgrifennu.

766
01:03:16,660 --> 01:03:18,020
Cyfri -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
Yw bod yr hyn yr wyf eisiau? Rwy'n credu bod yr hyn yr wyf eisiau.

769
01:03:35,100 --> 01:03:38,290
Ydy, mae hyn yn edrych yn dda. Iawn.

770
01:03:38,290 --> 01:03:43,050
Felly, mae pawb yn deall beth yw pwrpas fy cyfrif amrywiaeth yw?

771
01:03:43,050 --> 01:03:48,140
Mae'n cyfrif nifer y digwyddiadau o bob un o'r rhifau hyn.

772
01:03:48,140 --> 01:03:51,780
Yna yr wyf yn ailadrodd dros y array cyfrif,

773
01:03:51,780 --> 01:03:57,190
a'r sefyllfa ith yn yr amrywiaeth cyfrif

774
01:03:57,190 --> 01:04:01,930
yw nifer y I a ddylai ymddangos yn fy amrywiaeth datrys.

775
01:04:01,930 --> 01:04:06,840
Dyna pam y cyfrif o 4 yn mynd i fod yn 1

776
01:04:06,840 --> 01:04:11,840
ac yn cyfrif o 8 yn mynd i fod yn 1, cyfrif o 23 yn mynd i fod yn 2.

777
01:04:11,840 --> 01:04:16,900
Felly dyna sut y mae llawer ohonynt wyf i am osod i mewn i fy amrywiaeth datrys.

778
01:04:16,900 --> 01:04:19,200
Yna, Fi jyst yn gwneud hynny.

779
01:04:19,200 --> 01:04:28,960
Yr wyf yn mewnosod num_of_item i yn i mewn i fy amrywiaeth datrys.

780
01:04:28,960 --> 01:04:31,670
>> Cwestiynau?

781
01:04:32,460 --> 01:04:43,100
Ac felly eto, mae hwn yn amser llinol ers i ni yn unig ailadrodd dros y unwaith,

782
01:04:43,100 --> 01:04:47,470
ond mae hefyd yn llinol yn yr hyn y nifer hwn yn digwydd i fod,

783
01:04:47,470 --> 01:04:50,730
ac felly mae'n drwm yn dibynnu ar beth yw eich rhwymo yn.

784
01:04:50,730 --> 01:04:53,290
Gyda rhwymo o 200, nid yw hynny'n ddrwg.

785
01:04:53,290 --> 01:04:58,330
Os yw eich rhwymo yn mynd i fod yn 10,000, yna mae hynny'n ychydig yn waeth,

786
01:04:58,330 --> 01:05:01,360
ond os yw eich rhwymo yn mynd i fod yn 4 biliwn, mae hynny'n hollol afrealistig

787
01:05:01,360 --> 01:05:07,720
ac mae'r amrywiaeth yn mynd i gael i fod o faint 4 biliwn, sydd yn afrealistig.

788
01:05:07,720 --> 01:05:10,860
Felly dyna hynny. Cwestiynau?

789
01:05:10,860 --> 01:05:13,270
[Ymateb y myfyrwyr Anghlywadwy] >> Iawn.

790
01:05:13,270 --> 01:05:15,710
Sylweddolais un peth arall pan oeddem yn mynd drwyddo.

791
01:05:17,980 --> 01:05:23,720
Rwy'n meddwl bod y broblem yn Lucas, ac yn ôl pob tebyg mae pob un rydym wedi gweld.

792
01:05:23,720 --> 01:05:26,330
Yr wyf yn llwyr anghofio.

793
01:05:26,330 --> 01:05:31,040
Yr unig beth oeddwn am wneud sylwadau arno yw bod pan fyddwch yn delio gyda phethau fel mynegeion,

794
01:05:31,040 --> 01:05:38,320
dydych chi byth yn wir yn gweld hyn pan fyddwch yn ysgrifennu ar gyfer dolen,

795
01:05:38,320 --> 01:05:41,120
ond yn dechnegol, pryd bynnag y byddwch yn delio â mynegeion hyn,

796
01:05:41,120 --> 01:05:45,950
dylech 'n bert lawer bob amser yn delio gyda chyfanrifau heb eu harwyddo.

797
01:05:45,950 --> 01:05:53,850
Y rheswm am hyn yw pan fyddwch chi'n delio gyda chyfanrifau llofnodi,

798
01:05:53,850 --> 01:05:56,090
felly os oes gennych 2 gyfanrifau llofnodi a chi eu hychwanegu at ei gilydd

799
01:05:56,090 --> 01:06:00,640
ac maent yn dod i ben i fyny yn rhy fawr, yna byddwch yn darfod i fyny ag rhif negatif.

800
01:06:00,640 --> 01:06:03,410
Felly, dyna beth gorlif cyfanrif yw.

801
01:06:03,410 --> 01:06:10,500
>> Os byddaf yn ychwanegu 2 biliwn a 1 biliwn, yr wyf darfod i fyny ag negyddol 1 biliwn.

802
01:06:10,500 --> 01:06:15,480
Dyna sut gyfanrifau yn gweithio ar gyfrifiaduron.

803
01:06:15,480 --> 01:06:17,510
Felly, y broblem gyda defnyddio -

804
01:06:17,510 --> 01:06:23,500
Mae hynny'n iawn ac eithrio os isel yn digwydd i fod yn 2 biliwn ac i fyny yn digwydd i fod yn 1 biliwn,

805
01:06:23,500 --> 01:06:27,120
yna mae hyn yn mynd i fod yn negyddol 1 biliwn ac yna rydym yn mynd i rannu hynny gyda 2

806
01:06:27,120 --> 01:06:29,730
a darfod i fyny ag negyddol 500 miliwn.

807
01:06:29,730 --> 01:06:33,760
Felly, mae hyn dim ond yn broblem os ydych yn digwydd bod yn chwilio drwy amrywiaeth

808
01:06:33,760 --> 01:06:38,070
o filiynau o bethau.

809
01:06:38,070 --> 01:06:44,050
Ond os + isel hyd yn digwydd i orlifo, yna mae hynny'n broblem.

810
01:06:44,050 --> 01:06:47,750
Cyn gynted ag y byddwn yn gwneud iddynt heb ei arwyddo, yna 2 biliwn a mwy 1 biliwn 3 biliwn.

811
01:06:47,750 --> 01:06:51,960
3000000000 rhannu â 2 yw 1.5 biliwn.

812
01:06:51,960 --> 01:06:55,670
Felly, cyn gynted ag y maen nhw'n heb ei arwyddo, mae popeth yn berffaith.

813
01:06:55,670 --> 01:06:59,900
Ac felly dyna hefyd yn fater pan fyddwch yn ysgrifennu eich gyfer dolenni,

814
01:06:59,900 --> 01:07:03,940
ac mewn gwirionedd, mae'n debyg ei wneud yn awtomatig.

815
01:07:09,130 --> 01:07:12,330
Bydd yn gwirionedd dim ond gweiddi ar chi.

816
01:07:12,330 --> 01:07:21,610
Felly, os y nifer hwn yn rhy fawr i fod mewn dim ond cyfanrif ond byddai'n ffitio mewn cyfanrif heb ei arwyddo,

817
01:07:21,610 --> 01:07:24,970
bydd yn gweiddi arnoch chi, felly dyna pam na fyddwch yn rhedeg wir i mewn i'r mater.

818
01:07:29,150 --> 01:07:34,820
Gallwch weld na mynegai yn mynd i fod yn negyddol,

819
01:07:34,820 --> 01:07:39,220
ac felly pan fyddwch yn ailadrodd dros array,

820
01:07:39,220 --> 01:07:43,970
gallwch chi bron bob amser yn dweud heb ei arwyddo int i, ond nid oes yn rhaid i.

821
01:07:43,970 --> 01:07:47,110
Mae pethau'n mynd i weithio 'n bert lawer yr un mor dda.

822
01:07:48,740 --> 01:07:50,090
Iawn. [Sibrydion] Faint o'r gloch yw hi?

823
01:07:50,090 --> 01:07:54,020
Y peth olaf roeddwn i eisiau dangos - a byddaf yn gwneud hynny mewn gwirionedd gyflym.

824
01:07:54,020 --> 01:08:03,190
Rydych yn gwybod sut yr ydym wedi diffinio # fel y gallwn # ddiffinio MAX â 5 neu rywbeth?

825
01:08:03,190 --> 01:08:05,940
Gadewch i ni beidio gwneud MAX. # Diffinio BOUND â 200. Dyna beth a wnaethom o'r blaen.

826
01:08:05,940 --> 01:08:10,380
Sy'n diffinio cyson, sy'n cael ei dim ond yn mynd i gael ei gopïo a gludo

827
01:08:10,380 --> 01:08:13,010
lle bynnag y byddwn yn digwydd i ysgrifennu BOUND.

828
01:08:13,010 --> 01:08:18,189
>> Felly gallwn mewn gwirionedd yn gwneud mwy gyda # diffinio.

829
01:08:18,189 --> 01:08:21,170
Gallwn # ddiffinio swyddogaethau.

830
01:08:21,170 --> 01:08:23,410
Nid ydynt yn wirioneddol swyddogaethau, ond byddwn yn eu galw swyddogaethau.

831
01:08:23,410 --> 01:08:36,000
Enghraifft o hyn fyddai rhywbeth fel MAX (x, y) ei ddiffinio fel (x <y y:? X). Iawn.

832
01:08:36,000 --> 01:08:40,660
Felly, dylech ddod i arfer cystrawen weithredwr teiran,

833
01:08:40,660 --> 01:08:49,029
ond mae'n x yn llai na y? Dychwelyd y, arall dychwelyd x.

834
01:08:49,029 --> 01:08:54,390
Felly, gallwch weld y gallwch chi wneud hyn yn swyddogaeth ar wahân,

835
01:08:54,390 --> 01:09:01,399
a gallai'r swyddogaeth fod fel bool MAX yn cymryd 2 dadleuon, ddychwelyd y ffurflen hon.

836
01:09:01,399 --> 01:09:08,340
Mae hwn yn un o'r rhai mwyaf cyffredin yr wyf yn gweld ei wneud fel hyn. Rydym yn eu galw macros.

837
01:09:08,340 --> 01:09:11,790
Mae hyn yn macro.

838
01:09:11,790 --> 01:09:15,859
Mae hyn yn unig y gystrawen ar ei gyfer.

839
01:09:15,859 --> 01:09:18,740
Gallwch ysgrifennu macro i wneud beth bynnag ydych ei eisiau.

840
01:09:18,740 --> 01:09:22,649
Byddwch yn aml yn ystyried macros ar gyfer debugging printfs a stwff.

841
01:09:22,649 --> 01:09:29,410
Felly, math o printf, mae yn gysonion arbennig yn C fel tanlinellu LLINELL tanlinellu,

842
01:09:29,410 --> 01:09:31,710
2 tanlinellu LLINELL tanlinellu,

843
01:09:31,710 --> 01:09:37,550
ac mae hefyd yr wyf yn credu fod 2 tanlinellu func. Gallai hynny fod yn ei. Rhywbeth fel 'na.

844
01:09:37,550 --> 01:09:40,880
Bydd y rhai pethau yn cael ei ddisodli gan enw'r swyddogaeth

845
01:09:40,880 --> 01:09:42,930
neu nifer y llinell eich bod ar.

846
01:09:42,930 --> 01:09:48,630
Yn aml, byddwch yn ysgrifennu printfs debugging bod i lawr yma gallwn wedyn, ysgrifennwch

847
01:09:48,630 --> 01:09:54,260
Dadfygio a bydd yn argraffu'r rhif llinell a swyddogaeth fy mod yn digwydd i fod yn

848
01:09:54,260 --> 01:09:57,020
ei fod yn dod ar draws y datganiad hwnnw debug.

849
01:09:57,020 --> 01:09:59,550
A allwch chi hefyd argraffu pethau eraill.

850
01:09:59,550 --> 01:10:05,990
Felly, un peth y dylech wylio amdano yw os wyf yn digwydd # ddiffinio DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
fel rhywbeth fel 2 * y * a 2 x.

852
01:10:11,380 --> 01:10:14,310
Felly, am reswm bynnag, digwydd i chi wneud hynny llawer.

853
01:10:14,310 --> 01:10:16,650
Felly, yn ei gwneud yn macro.

854
01:10:16,650 --> 01:10:18,680
Mae hyn yn cael ei dorri mewn gwirionedd.

855
01:10:18,680 --> 01:10:23,050
Byddwn yn ei alw drwy wneud rhywbeth fel DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Felly, beth ddylid ei dychwelyd?

857
01:10:28,840 --> 01:10:30,580
[Myfyrwyr] 12.

858
01:10:30,580 --> 01:10:34,800
Oes, dylai 12 yn cael ei dychwelyd, a 12 yn cael ei ddychwelyd.

859
01:10:34,800 --> 01:10:43,350
3 yn cael ei ddisodli ar gyfer x, 6 yn cael ei ddisodli gyfer y, a byddwn yn dychwelyd 2 * 6, sydd yn 12.

860
01:10:43,350 --> 01:10:47,710
Nawr beth am hyn? Beth ddylid ei dychwelyd?

861
01:10:47,710 --> 01:10:50,330
[Myfyrwyr] 14. >> Yn ddelfrydol, 14.

862
01:10:50,330 --> 01:10:55,290
Y broblem yw bod sut hash diffinio gwaith, cofiwch ei fod yn gopi llythrennol a gludo

863
01:10:55,290 --> 01:11:00,160
o bopeth 'n bert lawer, felly beth mae hyn yn mynd i gael eu dehongli fel

864
01:11:00,160 --> 01:11:11,270
yw 3 yn llai nag 1 a 6, 2 gwaith 1 a 6, 2 waith 3.

865
01:11:11,270 --> 01:11:19,780
>> Felly, ar gyfer y rheswm hwn, rydych bron bob amser yn lapio popeth mewn cromfachau.

866
01:11:22,180 --> 01:11:25,050
Unrhyw newidyn rydych bron bob amser lapio mewn cromfachau.

867
01:11:25,050 --> 01:11:29,570
Mae yna achosion lle nad oes rhaid i chi, fel yr wyf yn gwybod nad oes angen i mi wneud hynny yma

868
01:11:29,570 --> 01:11:32,110
oherwydd llai na 'n bert lawer bob amser yn unig yn mynd i weithio,

869
01:11:32,110 --> 01:11:34,330
er na allai fod hyd yn oed fod yn wir.

870
01:11:34,330 --> 01:11:41,870
Os oes rhywbeth chwerthinllyd fel DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
yna mae hynny'n mynd i gael eu disodli gyda 3 yn llai nag 1 yn dychwelyd gyfystyr â 2,

872
01:11:49,760 --> 01:11:53,460
ac felly, yna mae'n mynd i wneud 3 yn llai nag 1, yn bod 2 gyfartal,

873
01:11:53,460 --> 01:11:55,620
nad yw hyn yr ydym ei eisiau.

874
01:11:55,620 --> 01:12:00,730
Felly, er mwyn atal unrhyw weithredwr broblemau blaenoriaeth,

875
01:12:00,730 --> 01:12:02,870
bob amser yn lapio mewn cromfachau.

876
01:12:03,290 --> 01:12:07,700
Iawn. A dyna ni, 5:30.

877
01:12:08,140 --> 01:12:12,470
Os oes gennych unrhyw gwestiynau ar y pset, gadewch i ni wybod.

878
01:12:12,470 --> 01:12:18,010
Dylai fod yn hwyl, ac mae'r rhifyn haciwr hefyd yn llawer mwy realistig

879
01:12:18,010 --> 01:12:22,980
na'r argraffiad haciwr y llynedd, felly rydym yn gobeithio y bydd llawer o chi roi cynnig arni.

880
01:12:22,980 --> 01:12:26,460
Llynedd yn iawn llethol.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]