1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Cyfweliadau Technegol]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Prifysgol Harvard]

3
00:00:04,630 --> 00:00:08,910
[Mae hyn yn CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi pawb, rwy'n Kenny. Hyn o bryd rwy'n gwyddoniaeth gyfrifiadurol iau yn astudio.

5
00:00:12,420 --> 00:00:17,310
Rwy'n gyn-CS TF, a dymunaf gen i hyn pan oeddwn yn underclassman,

6
00:00:17,310 --> 00:00:19,380
a dyna pam yr wyf i'n rhoi seminar hwn.

7
00:00:19,380 --> 00:00:21,370
Felly, yr wyf yn gobeithio y byddwch yn ei fwynhau.

8
00:00:21,370 --> 00:00:23,470
Mae'r seminar yn ymwneud â chyfweliadau technegol,

9
00:00:23,470 --> 00:00:26,650
a gall fy holl adnoddau ar gael yn y cyswllt hwn,

10
00:00:26,650 --> 00:00:32,350
y ddolen hon i'r dde yma, ychydig o adnoddau.

11
00:00:32,350 --> 00:00:36,550
Felly yr wyf yn gwneud rhestr o broblemau, mewn gwirionedd, yn eithaf ychydig o broblemau.

12
00:00:36,550 --> 00:00:40,800
Hefyd, adnoddau tudalen cyffredinol lle y gallwn ddod o hyd i awgrymiadau

13
00:00:40,800 --> 00:00:42,870
ar sut i baratoi ar gyfer cyfweliad,

14
00:00:42,870 --> 00:00:46,470
awgrymiadau ar yr hyn y dylech ei wneud yn ystod cyfweliad go iawn,

15
00:00:46,470 --> 00:00:51,910
yn ogystal â sut i ddelio â phroblemau ac adnoddau ar gyfer y dyfodol.

16
00:00:51,910 --> 00:00:53,980
Mae hyn i gyd ar-lein.

17
00:00:53,980 --> 00:00:58,290
A dim ond i ragflaenu hyn seminar, ymwadiad,

18
00:00:58,290 --> 00:01:00,690
Nid fel hyn ddylai - eich paratoi ar gyfer cyfweliad

19
00:01:00,690 --> 00:01:02,800
ni ddylid eu cyfyngu at y rhestr hon.

20
00:01:02,800 --> 00:01:04,750
Mae hyn yn golygu dim ond i fod yn ganllaw,

21
00:01:04,750 --> 00:01:08,890
a dylech yn sicr yn cymryd popeth yr wyf yn dweud gyda gronyn o halen,

22
00:01:08,890 --> 00:01:14,620
ond hefyd yn defnyddio popeth wyf yn ei ddefnyddio i'ch helpu chi yn eich paratoi ar gyfer cyfweliad.

23
00:01:14,620 --> 00:01:16,400
>> Rydw i'n mynd i gyflymu'r drwy'r sleidiau nesaf

24
00:01:16,400 --> 00:01:18,650
er mwyn i ni gyrraedd yr astudiaethau achos go iawn.

25
00:01:18,650 --> 00:01:23,630
Mae strwythur y cyfweliad ar gyfer peirianneg meddalwedd postion,

26
00:01:23,630 --> 00:01:26,320
fel arfer ei fod yn 30 i 45 munud,

27
00:01:26,320 --> 00:01:29,810
rowndiau lluosog, yn dibynnu ar y cwmni.

28
00:01:29,810 --> 00:01:33,090
Yn aml byddwch yn codio ar fwrdd gwyn.

29
00:01:33,090 --> 00:01:35,960
Felly, bwrdd gwyn fel hyn, ond yn aml ar raddfa lai.

30
00:01:35,960 --> 00:01:38,540
Os ydych yn cael cyfweliad ffôn, mae'n debyg y byddwch yn eu defnyddio

31
00:01:38,540 --> 00:01:44,030
naill ai collabedit neu Doc Google fel y gallant weld rydych chi'n byw codio

32
00:01:44,030 --> 00:01:46,500
tra byddwch chi'n cael eich cyfweld dros y ffôn.

33
00:01:46,500 --> 00:01:48,490
Mae cyfweliad ei hun fel arfer 2 neu 3 broblemau

34
00:01:48,490 --> 00:01:50,620
brofi eich cyfrifiadur gwybodaeth wyddonol.

35
00:01:50,620 --> 00:01:54,490
A bydd yn bron yn bendant yn cynnwys codio.

36
00:01:54,490 --> 00:01:59,540
Mae'r mathau o gwestiynau y byddwch yn gweld fel arfer yn strwythurau data ac algorithmau.

37
00:01:59,540 --> 00:02:02,210
Ac wrth wneud y mathau hyn o broblemau,

38
00:02:02,210 --> 00:02:07,830
byddant yn gofyn i chi, fel, beth yw'r amser ac, cymhlethdod gofod mawr O?

39
00:02:07,830 --> 00:02:09,800
Yn aml, maent hefyd yn gofyn i lefel uwch gwestiynau,

40
00:02:09,800 --> 00:02:12,530
felly, dylunio system,

41
00:02:12,530 --> 00:02:14,770
sut fyddech chi'n gosod eich cod?

42
00:02:14,770 --> 00:02:18,370
Pa rhyngwynebau, pa ddosbarthiadau, pa fodiwlau sydd gennych yn eich system,

43
00:02:18,370 --> 00:02:20,900
a sut mae'r rhain yn rhyngweithio â'i gilydd?

44
00:02:20,900 --> 00:02:26,130
Felly, strwythurau data ac algorithmau yn ogystal â systemau dylunio.

45
00:02:26,130 --> 00:02:29,180
>> Rhai awgrymiadau cyffredinol cyn i ni plymio i mewn i ein hastudiaethau achos.

46
00:02:29,180 --> 00:02:32,300
Rwy'n meddwl bod y rheol pwysicaf yw bob amser yn meddwl yn uchel.

47
00:02:32,300 --> 00:02:36,980
Mae'r cyfweliad yn dybiedig i fod yn eich cyfle i ddangos eich proses meddwl.

48
00:02:36,980 --> 00:02:39,820
Y pwynt y cyfweliad yw i'r cyfwelydd i fesur

49
00:02:39,820 --> 00:02:42,660
sut rydych yn meddwl a sut rydych yn mynd drwy problem.

50
00:02:42,660 --> 00:02:45,210
Y peth gwaethaf y gallwch chi ei wneud yw fod yn dawel drwy gydol y cyfweliad cyfan.

51
00:02:45,210 --> 00:02:50,090
Dyna dim ond dda i ddim.

52
00:02:50,090 --> 00:02:53,230
Pan fyddwch yn cael cwestiwn, byddwch hefyd yn dymuno gwneud yn siŵr eich bod yn deall y cwestiwn.

53
00:02:53,230 --> 00:02:55,350
Felly, ailadrodd y cwestiwn yn ôl yn eich geiriau eich hun

54
00:02:55,350 --> 00:02:58,920
a cheisio gweithio trylwyr o achosion prawf syml ychydig

55
00:02:58,920 --> 00:03:01,530
i wneud yn siŵr eich bod yn deall y cwestiwn.

56
00:03:01,530 --> 00:03:05,510
Bydd gweithio drwy achosion prawf rhai hefyd yn rhoi i chi greddf ar sut i ddatrys y broblem hon.

57
00:03:05,510 --> 00:03:11,210
Efallai y byddwch hyd yn oed ddarganfod patrymau ychydig i'ch helpu chi i ddatrys y broblem.

58
00:03:11,210 --> 00:03:14,500
Mae eu tip mawr yw peidio â mynd yn rhwystredig.

59
00:03:14,500 --> 00:03:17,060
Peidiwch â mynd yn rhwystredig.

60
00:03:17,060 --> 00:03:19,060
Cyfweliadau yn heriol, ond y peth gwaethaf y gallwch ei wneud,

61
00:03:19,060 --> 00:03:23,330
yn ogystal â bod yn dawel, yn cael ei rhwystredig yn amlwg.

62
00:03:23,330 --> 00:03:27,410
Nid ydych am i roi'r argraff i'r cyfwelydd.

63
00:03:27,410 --> 00:03:33,960
Un peth sydd chi - felly, mae llawer o bobl, pan fyddant yn mynd i mewn i gyfweliad,

64
00:03:33,960 --> 00:03:37,150
maent yn ymdrechu i geisio dod o hyd i'r ateb gorau yn gyntaf,

65
00:03:37,150 --> 00:03:39,950
pan mewn gwirionedd, mae fel arfer yn ateb glaringly amlwg.

66
00:03:39,950 --> 00:03:43,500
Gallai fod yn araf, gallai fod yn aneffeithlon, ond dylech dim ond nodi ei,

67
00:03:43,500 --> 00:03:46,210
yn unig fel bod gennych man cychwyn i weithio'n well.

68
00:03:46,210 --> 00:03:48,270
Hefyd, dynnu sylw at yr ateb yn araf, o ran

69
00:03:48,270 --> 00:03:52,160
cymhlethdod amser mawr O neu gymhlethdod gofod,

70
00:03:52,160 --> 00:03:54,450
Bydd ddangos i'r cyfwelydd eich bod yn deall

71
00:03:54,450 --> 00:03:57,510
y materion hyn wrth ysgrifennu cod.

72
00:03:57,510 --> 00:04:01,440
Felly peidiwch â bod ofn i ddod o hyd i'r algorithm symlaf 1

73
00:04:01,440 --> 00:04:04,950
ac yna yn gweithio'n well oddi yno.

74
00:04:04,950 --> 00:04:09,810
Unrhyw gwestiynau hyd yn hyn? Iawn.

75
00:04:09,810 --> 00:04:11,650
>> Felly gadewch i ni neidio i mewn i'n problem cyntaf.

76
00:04:11,650 --> 00:04:14,790
"O ystyried amrywiaeth o gyfanrifau n, ysgrifennwch swyddogaeth sy'n cymysgu'r yr amrywiaeth

77
00:04:14,790 --> 00:04:20,209
yn eu lle fel bod yr holl gyfnewidiadau o'r cyfanrif n yr un mor debygol. "

78
00:04:20,209 --> 00:04:23,470
Ac yn tybio sydd ar gael gennych generadur cyfanrif ar hap

79
00:04:23,470 --> 00:04:30,980
sy'n cynhyrchu cyfanrif mewn amryw o 0 i i, ystod hanner.

80
00:04:30,980 --> 00:04:32,970
Ydy pawb yn deall y cwestiwn hwn?

81
00:04:32,970 --> 00:04:39,660
Yr wyf yn rhoi i chi amrywiaeth o gyfanrifau n, ac yr wyf am i chi siffrwd iddo.

82
00:04:39,660 --> 00:04:46,050
Yn fy cyfeiriadur, ysgrifennais ychydig o raglenni i ddangos yr hyn rwy'n ei olygu.

83
00:04:46,050 --> 00:04:48,910
Rydw i'n mynd i siffrwd amrywiaeth o 20 elfen,

84
00:04:48,910 --> 00:04:52,490
o -10 i +9,

85
00:04:52,490 --> 00:04:57,050
ac yr wyf am i chi allbynnu rhestr fel hyn.

86
00:04:57,050 --> 00:05:02,890
Felly mae hyn yn fy amrywiaeth mewnbwn didoli, ac yr wyf am i chi siffrwd iddo.

87
00:05:02,890 --> 00:05:07,070
Byddwn yn gwneud hynny eto.

88
00:05:07,070 --> 00:05:13,780
Ydy pawb yn deall y cwestiwn? Iawn.

89
00:05:13,780 --> 00:05:16,730
Felly, mae i fyny i chi.

90
00:05:16,730 --> 00:05:21,220
Beth yw rhai syniadau? Allwch chi ei wneud fel n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Yn agored i awgrymiadau.

92
00:05:34,400 --> 00:05:37,730
Iawn. Felly, un syniad, a awgrymwyd gan Emmy,

93
00:05:37,730 --> 00:05:45,300
yn gyntaf gyfrifo rhif ar hap, cyfanrif ar hap, mewn amrywio o 0 i 20.

94
00:05:45,300 --> 00:05:49,840
Felly, cymryd yn ganiataol ein casgliad mae cyfweliadau i 20.

95
00:05:49,840 --> 00:05:54,800
Yn ein diagram o 20 elfen,

96
00:05:54,800 --> 00:05:58,560
mae hyn yn ein amrywiaeth mewnbwn.

97
00:05:58,560 --> 00:06:04,590
Ac yn awr, ei awgrym yw creu amrywiaeth newydd,

98
00:06:04,590 --> 00:06:08,440
felly bydd hyn yn yr amrywiaeth allbwn.

99
00:06:08,440 --> 00:06:12,880
Ac yn seiliedig ar y ff dychwelyd erbyn rand -

100
00:06:12,880 --> 00:06:17,580
felly os fi oedd, gadewch i ni ddweud, 17,

101
00:06:17,580 --> 00:06:25,640
copïo'r elfen 17 i mewn i'r swydd gyntaf.

102
00:06:25,640 --> 00:06:30,300
Nawr mae angen i ddileu - mae angen i ni symud yr holl elfennau yma

103
00:06:30,300 --> 00:06:36,920
drosodd fel bod gennym fwlch ar y diwedd a dim tyllau yn y canol.

104
00:06:36,920 --> 00:06:39,860
Ac yn awr rydym yn ailadrodd y broses.

105
00:06:39,860 --> 00:06:46,360
Nawr rydym yn dewis cyfanrif newydd ar hap rhwng 0 a 19 oed.

106
00:06:46,360 --> 00:06:52,510
Mae gennym i newydd yma, ac rydym yn copïo yr elfen hon yn y sefyllfa hon.

107
00:06:52,510 --> 00:07:00,960
Yna, rydym yn symud eitemau drosodd ac rydym yn ailadrodd y broses nes inni gael ein amrywiaeth llawn newydd.

108
00:07:00,960 --> 00:07:05,890
Beth yw'r amser yn rhedeg y algorithm?

109
00:07:05,890 --> 00:07:08,110
Wel, gadewch i ni ystyried effaith hyn.

110
00:07:08,110 --> 00:07:10,380
Rydym yn symud pob elfen.

111
00:07:10,380 --> 00:07:16,800
Pan fyddwn yn cael gwared hyn i, yr ydym yn symud yr holl elfennau ar ôl iddo ar y chwith.

112
00:07:16,800 --> 00:07:21,600
A dyna yw (n) O cost

113
00:07:21,600 --> 00:07:26,100
oherwydd yr hyn os ydym yn cael gwared ar y elfen gyntaf?

114
00:07:26,100 --> 00:07:29,670
Felly, ar gyfer pob dileu, byddwn yn cael gwared -

115
00:07:29,670 --> 00:07:32,170
pob symud tynnu yn (n) O gweithrediad,

116
00:07:32,170 --> 00:07:41,520
ac ers i ni wedi symud n, mae hyn yn arwain at (n ^ 2) O siffrwd.

117
00:07:41,520 --> 00:07:49,550
Iawn. Felly dechrau da. Dechrau da.

118
00:07:49,550 --> 00:07:55,290
>> Awgrym arall yw defnyddio rhywbeth a elwir yn siffrwd Knuth,

119
00:07:55,290 --> 00:07:57,540
neu 'r siffrwd Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
Ac mewn gwirionedd mae'n shuffle amser llinol.

121
00:07:59,630 --> 00:08:02,200
Ac mae'r syniad yn debyg iawn.

122
00:08:02,200 --> 00:08:05,160
Unwaith eto, rydym wedi ein amrywiaeth mewnbwn,

123
00:08:05,160 --> 00:08:08,580
ond yn hytrach na defnyddio ddau arae ar gyfer ein mewnbwn / allbwn,

124
00:08:08,580 --> 00:08:13,590
rydym yn defnyddio y rhan gyntaf o'r amrywiaeth i gadw golwg ar ein rhan cymysgu,

125
00:08:13,590 --> 00:08:18,400
ac rydym yn cadw trac, ac yna rydym yn gadael y gweddill ein amrywiaeth ar gyfer y rhan unshuffled.

126
00:08:18,400 --> 00:08:24,330
Felly dyma beth rwy'n ei olygu. Rydym yn dechrau i ffwrdd gyda - rydym yn dewis i,

127
00:08:24,330 --> 00:08:30,910
arae 0-20.

128
00:08:30,910 --> 00:08:36,150
Mae ein pwyntydd ar hyn o bryd yn pwyntio at y mynegai cyntaf.

129
00:08:36,150 --> 00:08:39,590
Rydym yn dewis rhai yma i

130
00:08:39,590 --> 00:08:42,740
ac yn awr rydym yn cyfnewid.

131
00:08:42,740 --> 00:08:47,690
Felly os yw hyn oedd 5 ac roedd hyn yn 4,

132
00:08:47,690 --> 00:08:57,150
Bydd yr amrywiaeth o ganlyniad gael 5 yma a 4 yma.

133
00:08:57,150 --> 00:09:00,390
Ac yn awr rydym yn nodi marciwr yma.

134
00:09:00,390 --> 00:09:05,770
Mae popeth ar y chwith yn cael ei gymysgu,

135
00:09:05,770 --> 00:09:15,160
a phopeth ar y dde yn cael ei unshuffled.

136
00:09:15,160 --> 00:09:17,260
Ac yn awr y gallwn ailadrodd y broses.

137
00:09:17,260 --> 00:09:25,210
Rydym yn dewis mynegai ar hap rhwng 1 a 20 awr.

138
00:09:25,210 --> 00:09:30,650
Felly mae'n debyg ein newydd i yma.

139
00:09:30,650 --> 00:09:39,370
Nawr rydym yn gyfnewid hon i gyda ein sefyllfa bresennol newydd yma.

140
00:09:39,370 --> 00:09:44,790
Felly rydym yn yn cyfnewid yn ôl ac ymlaen fel hyn.

141
00:09:44,790 --> 00:09:51,630
Gadewch i mi ddod i fyny y cod i'w wneud yn fwy cadarn.

142
00:09:51,630 --> 00:09:55,290
Rydym yn dechrau gyda ein dewis o i -

143
00:09:55,290 --> 00:09:58,370
rydym yn dechrau gyda i gyfartal i 0, rydym yn dewis j lleoliad ar hap

144
00:09:58,370 --> 00:10:02,420
yn y rhan unshuffled y rhesi, i i n-1.

145
00:10:02,420 --> 00:10:07,280
Felly os dwi yma, dewiswch mynegai ar hap rhwng y fan hon a gweddill y rhesi,

146
00:10:07,280 --> 00:10:12,410
ac rydym yn gyfnewid.

147
00:10:12,410 --> 00:10:17,550
Mae hyn i gyd y cod angenrheidiol i siffrwd eich casgliad.

148
00:10:17,550 --> 00:10:21,670
Unrhyw gwestiynau?

149
00:10:21,670 --> 00:10:25,530
>> Wel, un angen cwestiwn yw, pam fod hyn yn gywir?

150
00:10:25,530 --> 00:10:28,360
Pam mae pob permutation yr un mor debygol?

151
00:10:28,360 --> 00:10:30,410
Ac ni fyddaf yn mynd drwy'r dystiolaeth o hyn,

152
00:10:30,410 --> 00:10:35,970
ond gall llawer o broblemau mewn gwyddoniaeth gyfrifiadurol yn cael ei brofi trwy sefydlu.

153
00:10:35,970 --> 00:10:38,520
Faint ydych yn gyfarwydd â sefydlu?

154
00:10:38,520 --> 00:10:40,590
Iawn. Cool.

155
00:10:40,590 --> 00:10:43,610
Felly, gallwch chi brofi cywirdeb yr algorithm syml gan ddefnyddio anwythiad,

156
00:10:43,610 --> 00:10:49,540
lle y byddai eich ddamcaniaeth sefydlu yn, cymryd yn ganiataol bod

157
00:10:49,540 --> 00:10:53,290
fy siffrwd yn dychwelyd bob permutation yr un mor debygol

158
00:10:53,290 --> 00:10:56,120
hyd at yr elfennau i gyntaf.

159
00:10:56,120 --> 00:10:58,300
Yn awr, ystyriwch i + 1.

160
00:10:58,300 --> 00:11:02,550
A thrwy y ffordd yr ydym yn dewis ein j mynegai i gyfnewid,

161
00:11:02,550 --> 00:11:05,230
hyn yn arwain at - ac yna rydych yn gweithio allan y manylion,

162
00:11:05,230 --> 00:11:07,390
o leiaf prawf llawn pam y algorithm yn dychwelyd

163
00:11:07,390 --> 00:11:12,800
bob permutation gyda thebygolrwydd yr un mor debygol.

164
00:11:12,800 --> 00:11:15,940
>> Mae pob hawl, problem nesaf.

165
00:11:15,940 --> 00:11:19,170
Felly "rhoi amrywiaeth o gyfanrifau, chadaranhaol, sero, negyddol,

166
00:11:19,170 --> 00:11:21,290
ysgrifennu swyddogaeth sy'n cyfrifo y swm uchaf

167
00:11:21,290 --> 00:11:24,720
o unrhyw subarray continueous y rhesi mewnbwn. "

168
00:11:24,720 --> 00:11:28,370
Un enghraifft yma, yn yr achos lle mae'r holl rifau yn gadarnhaol,

169
00:11:28,370 --> 00:11:31,320
Yna, ar hyn o bryd y dewis gorau yw cymryd y casgliad cyfan.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, yn hafal i 10.

171
00:11:34,690 --> 00:11:36,780
Pan fydd gennych rhai pethau negyddol i mewn 'na,

172
00:11:36,780 --> 00:11:38,690
yn yr achos hwn rydym yn unig am y ddau gyntaf

173
00:11:38,690 --> 00:11:44,590
oherwydd bydd dewis -1 a / neu -3 ddod â'n swm i lawr.

174
00:11:44,590 --> 00:11:48,120
Weithiau gallai fod yn rhaid i ddechrau yng nghanol y rhesi.

175
00:11:48,120 --> 00:11:53,500
Weithiau, rydym am i ddewis dim byd o gwbl; mae'n well i beidio â chymryd unrhyw beth.

176
00:11:53,500 --> 00:11:56,490
Ac weithiau mae'n well i gymryd y cwymp,

177
00:11:56,490 --> 00:12:07,510
oherwydd y peth ar ôl ei super mawr. Felly unrhyw syniadau?

178
00:12:07,510 --> 00:12:10,970
(Myfyrwyr, annealladwy) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
Gadewch i ni dybio Nid wyf yn cymryd -1.

180
00:12:13,560 --> 00:12:16,170
Yna naill ai Rwy'n dewis 1,000 a 20,000,

181
00:12:16,170 --> 00:12:18,630
neu Fi jyst dewis y 3 biliwn.

182
00:12:18,630 --> 00:12:20,760
Wel, y dewis gorau yw i gymryd yr holl rifau.

183
00:12:20,760 --> 00:12:24,350
Mae hyn yn -1, er gwaethaf y ffaith bod yn negyddol,

184
00:12:24,350 --> 00:12:31,340
y swm cyfan yn well nag oedd I beidio â chymryd -1.

185
00:12:31,340 --> 00:12:36,460
Felly un o'r awgrymiadau y soniais yn gynharach oedd i ddatgan yr hyn sy'n amlwg yn glir

186
00:12:36,460 --> 00:12:40,540
a'r ateb 'n ysgrublaidd dreisio yn gyntaf.

187
00:12:40,540 --> 00:12:44,340
Beth yw'r ateb 'n ysgrublaidd dreisio yn y broblem? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Wel, yr wyf yn meddwl yr ateb 'n ysgrublaidd dreisio

189
00:12:46,890 --> 00:12:52,600
fyddai ychwanegu yr holl gyfuniadau posibl (annealladwy).

190
00:12:52,600 --> 00:12:58,250
[Yu] Iawn. Felly, Jane syniad yw i fanteisio ar bob bosibl -

191
00:12:58,250 --> 00:13:01,470
Rwy'n aralleirio - yw manteisio ar bob subarray parhaus posibl,

192
00:13:01,470 --> 00:13:07,840
gyfrifo ei swm, ac yna cymryd yr uchafswm yr holl subarrays posibl parhaus.

193
00:13:07,840 --> 00:13:13,310
Beth unigryw yn nodi subarray yn fy amrywiaeth mewnbwn?

194
00:13:13,310 --> 00:13:17,380
Fel, pa ddau beth sydd ei angen arnaf? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Myfyrwyr, annealladwy) Hawl >>.

196
00:13:19,970 --> 00:13:22,130
Mae is rhwymo ar y mynegai a mynegai rhwymo uchaf

197
00:13:22,130 --> 00:13:28,300
unigryw yn gyfrifol am y subarray parhaus.

198
00:13:28,300 --> 00:13:31,400
[Myfyrwraig] A ydym yn amcangyfrif ei fod yn amrywiaeth o rifau unigryw?

199
00:13:31,400 --> 00:13:34,280
[Yu] Rhif Felly, ei gwestiwn yn cael ei, rydym yn cymryd ein amrywiaeth -

200
00:13:34,280 --> 00:13:39,000
yw ein amrywiaeth holl rifau unigryw, a'r ateb yw na.

201
00:13:39,000 --> 00:13:43,390
>> Os ydym yn defnyddio ein ateb 'n ysgrublaidd dreisio, yna bydd y mynegeion dechrau / diwedd

202
00:13:43,390 --> 00:13:47,200
unigryw yn pennu ein subarray barhaus.

203
00:13:47,200 --> 00:13:51,680
Felly, os ydym yn ailadrodd ar gyfer pob cais cychwyn posibl,

204
00:13:51,680 --> 00:13:58,320
ac ar gyfer pob cofnod diwedd> neu = i ddechrau, a <n,

205
00:13:58,320 --> 00:14:05,570
chi gyfrifo swm, ac yna rydym yn cymryd y swm uchaf y byddwn wedi gweld hyd yn hyn.

206
00:14:05,570 --> 00:14:07,880
A yw hyn yn glir?

207
00:14:07,880 --> 00:14:12,230
Beth yw O fawr o'r ateb hwn?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
Heb n eithaf ^ 2.

210
00:14:18,860 --> 00:14:25,250
Sylwer ein bod yn ailadrodd o 0 i n,

211
00:14:25,250 --> 00:14:27,520
felly dyna un ar gyfer dolen.

212
00:14:27,520 --> 00:14:35,120
Rydym yn ailadrodd eto o bron dechrau i'r diwedd, un arall ar gyfer dolen.

213
00:14:35,120 --> 00:14:37,640
Ac yn awr, o fewn hynny, mae'n rhaid i ni grynhoi bob cofnod,

214
00:14:37,640 --> 00:14:43,810
felly dyna un arall ar gyfer dolen. Felly, mae gennym dri nythu ar gyfer dolenni, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Iawn. Mae hyn yn mynd fel man cychwyn.

216
00:14:46,560 --> 00:14:53,180
Mae ein ateb yn ddim gwaeth na n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ydy pawb yn deall yr ateb 'n ysgrublaidd dreisio?

218
00:14:55,480 --> 00:14:59,950
>> Iawn. Ateb gwell yn defnyddio syniad a elwir yn rhaglennu deinamig.

219
00:14:59,950 --> 00:15:03,040
Os ydych yn cymryd CS124, sef Algorithmau a Strwythurau Data,

220
00:15:03,040 --> 00:15:05,680
byddwch yn dod yn gyfarwydd iawn gyda'r dechneg hon.

221
00:15:05,680 --> 00:15:12,190
Ac y syniad yw, ceisio adeiladu i fyny atebion i broblemau llai yn gyntaf.

222
00:15:12,190 --> 00:15:17,990
Beth a olygaf wrth hyn yw, yr ydym ar hyn o bryd rhaid i chi boeni am ddau beth: dechrau a diwedd.

223
00:15:17,990 --> 00:15:29,340
Ac mae hynny'n blino. Beth pe gallem gael gwared o un o'r paramedrau?

224
00:15:29,340 --> 00:15:32,650
Un syniad yw - we're o ystyried ein problem gwreiddiol,

225
00:15:32,650 --> 00:15:37,470
ddod o hyd i'r swm mwyaf o unrhyw subarray mewn ystod [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Ac yn awr mae gennym subproblem newydd, lle y gwyddom, yn ein mynegai ar hyn o bryd i,

227
00:15:47,400 --> 00:15:52,520
rydym yn gwybod mae'n rhaid i ni ddod i'r casgliad yno. Rhaid i'n subarray dod i ben ar y mynegai ar hyn o bryd.

228
00:15:52,520 --> 00:15:57,640
Felly, y broblem sydd ar ôl yw, ble y dylem ddechrau ein subarray?

229
00:15:57,640 --> 00:16:05,160
A yw hyn yn gwneud synnwyr? Iawn.

230
00:16:05,160 --> 00:16:12,030
Felly, yr wyf wedi eu codio hyn i fyny, a gadewch i ni edrych ar beth mae hyn yn ei olygu.

231
00:16:12,030 --> 00:16:16,230
Yn y codirectory, mae 'na raglen o'r enw subarray,

232
00:16:16,230 --> 00:16:19,470
ac mae'n cymryd nifer o eitemau,

233
00:16:19,470 --> 00:16:25,550
ac yn dychwelyd y swm mwyaf posibl subarray yn fy rhestr cymysgu.

234
00:16:25,550 --> 00:16:29,920
Felly, yn yr achos hwn, mae ein subarray mwyaf posibl yw 3.

235
00:16:29,920 --> 00:16:34,850
A bod wedi cymryd gan ddefnyddio dim ond 2 ac 1.

236
00:16:34,850 --> 00:16:38,050
Gadewch i ni ei gynnal eto. Mae hefyd yn 3.

237
00:16:38,050 --> 00:16:40,950
Ond y tro hwn, yn nodi sut rydym yn cael y 3.

238
00:16:40,950 --> 00:16:46,690
Rydym yn cymryd y - rydym yn unig yn cymryd y 3 ei hun

239
00:16:46,690 --> 00:16:49,980
oherwydd ei fod yn amgylchynu gan negyddol ar y ddwy ochr,

240
00:16:49,980 --> 00:16:55,080
fydd yn dod â swm <3.

241
00:16:55,080 --> 00:16:57,820
Gadewch i ni redeg ar 10 eitem.

242
00:16:57,820 --> 00:17:03,200
Y tro hwn mae'n 7, rydym yn cymryd y 3 blaenllaw a 4.

243
00:17:03,200 --> 00:17:09,450
Y tro hwn mae'n 8, ac rydym yn cael bod drwy gymryd 1, 4 a 3.

244
00:17:09,450 --> 00:17:16,310
Felly, er mwyn rhoi i chi greddf ar sut y gallwn ddatrys y broblem hon trawsnewid,

245
00:17:16,310 --> 00:17:18,890
gadewch i ni edrych ar y subarray.

246
00:17:18,890 --> 00:17:23,460
Rydym yn rhoi y array mewnbwn, ac rydym yn gwybod yr ateb yw 8.

247
00:17:23,460 --> 00:17:26,359
Rydym yn cymryd y 1, 4, a 3.

248
00:17:26,359 --> 00:17:29,090
Ond gadewch i ni edrych ar sut yr ydym mewn gwirionedd yn cael yr ateb hwnnw.

249
00:17:29,090 --> 00:17:34,160
Gadewch i ni edrych ar y subarray mwyaf posibl a ddaeth i ben ym mhob un o'r mynegeion hyn.

250
00:17:34,160 --> 00:17:40,780
Beth yw'r subarray mwyaf posibl sydd wedi dod i ben ar y sefyllfa cyntaf?

251
00:17:40,780 --> 00:17:46,310
[Myfyrwyr] Zero. >> Zero. Nid yn unig yn cymryd y -5.

252
00:17:46,310 --> 00:17:50,210
Yma, mae'n mynd i fod yn 0 yn ogystal. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Myfyrwyr, annealladwy)

254
00:17:56,470 --> 00:17:58,960
[Yu] O, mae'n ddrwg gennyf, a -3.

255
00:17:58,960 --> 00:18:03,220
Felly, mae hyn yn 2, mae hyn yn -3.

256
00:18:03,220 --> 00:18:08,690
Iawn. Felly -4, beth yw'r subarray mwyaf posibl i roi terfyn ar y sefyllfa honno

257
00:18:08,690 --> 00:18:12,910
lle -4 ar? Zero.

258
00:18:12,910 --> 00:18:22,570
Un? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Yn awr, rhaid i mi orffen yn y lleoliad lle -2 ar.

260
00:18:28,060 --> 00:18:39,330
Felly 6, 5, 7, ac mae'r un olaf yn 4.

261
00:18:39,330 --> 00:18:43,480
Mae gwybod bod y rhain yn fy cofnodion

262
00:18:43,480 --> 00:18:48,130
am y broblem trawsnewid lle mae'n rhaid imi orffen ym mhob un o'r mynegeion hyn,

263
00:18:48,130 --> 00:18:51,410
yna fy ateb terfynol yn unig, yn cymryd ysgubo ar draws,

264
00:18:51,410 --> 00:18:53,580
ac yn cymryd y nifer mwyaf posibl.

265
00:18:53,580 --> 00:18:55,620
Felly, yn yr achos hwn mae'n 8.

266
00:18:55,620 --> 00:19:00,010
Mae hyn yn awgrymu bod y subarray mwyaf posibl yn dod i ben ar y mynegai,

267
00:19:00,010 --> 00:19:04,970
a dechrau rhywle ger ei fron.

268
00:19:04,970 --> 00:19:09,630
Ydy pawb yn deall y subarray trawsnewid?

269
00:19:09,630 --> 00:19:22,160
>> Iawn. Wel, gadewch i chyfrif i maes y digwydd eto ar gyfer hyn.

270
00:19:22,160 --> 00:19:27,990
Gadewch i ni ystyried dim ond y cofnodion cyntaf.

271
00:19:27,990 --> 00:19:35,930
Felly dyma ei fod yn 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Ac yna roedd -2 yma, ac a ddaeth ag ef i lawr i 6.

273
00:19:39,790 --> 00:19:50,800
Felly, os galwaf y cofnod yn safle i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
sut y gallaf ddefnyddio'r ateb i subproblem blaenorol

275
00:19:54,910 --> 00:19:59,360
i ateb y subproblem?

276
00:19:59,360 --> 00:20:04,550
Os byddaf yn edrych ar, gadewch i ni ddweud, y cofnod hwn.

277
00:20:04,550 --> 00:20:09,190
Sut alla i gyfrifo yr ateb 6 drwy edrych ar

278
00:20:09,190 --> 00:20:18,780
cyfuniad o'r amrywiaeth a'r atebion i subproblems blaenorol yn y casgliad? Ydw?

279
00:20:18,780 --> 00:20:22,800
[Myfyrwraig] i chi gymryd y casgliad o symiau

280
00:20:22,800 --> 00:20:25,430
yn y safle cywir cyn hynny, felly yr 8,

281
00:20:25,430 --> 00:20:32,170
ac yna i chi ychwanegu'r subproblem ar hyn o bryd.

282
00:20:32,170 --> 00:20:36,460
[Yu] Felly, ei awgrym yw edrych ar y ddau rif,

283
00:20:36,460 --> 00:20:40,090
rhif hwn a rhif hwn.

284
00:20:40,090 --> 00:20:50,130
Felly, mae hyn 8 yn cyfeirio at yr ateb yn y subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
A gadewch i ni alw fy mewnbwn A. amrywiaeth

286
00:20:57,300 --> 00:21:01,470
Er mwyn dod o hyd i subarray mwyaf posibl sy'n dod i ben yn safle i,

287
00:21:01,470 --> 00:21:03,980
Mae gen i ddau ddewis: gallaf naill ai barhau â'r subarray

288
00:21:03,980 --> 00:21:09,790
a ddaeth i ben ar y mynegai blaenorol, neu ddechrau casgliad newydd.

289
00:21:09,790 --> 00:21:14,190
Pe bawn i barhau â'r subarray a ddechreuodd ar y mynegai blaenorol,

290
00:21:14,190 --> 00:21:19,260
yna bydd y swm uchaf y gallaf ei gyflawni yw'r ateb i'r subproblem blaenorol

291
00:21:19,260 --> 00:21:24,120
yn ogystal â'r cofnod amrywiaeth ar hyn o bryd.

292
00:21:24,120 --> 00:21:27,550
Ond, yr wyf hefyd yn cael y dewis o ddechrau subarray newydd,

293
00:21:27,550 --> 00:21:30,830
yn yr achos hwnnw y swm yw 0.

294
00:21:30,830 --> 00:21:42,860
Felly yr ateb yw uchafswm o 0, subproblem i - 1, yn ogystal â'r cofnod amrywiaeth presennol.

295
00:21:42,860 --> 00:21:46,150
A yw hyn yn digwydd eto yn gwneud synnwyr?

296
00:21:46,150 --> 00:21:50,840
Mae ein eto, fel yr ydym yn unig darganfod, yn subproblem i

297
00:21:50,840 --> 00:21:54,740
yn hafal i uchafswm y subproblem flaenorol ynghyd fy nghofnod array ar hyn o bryd,

298
00:21:54,740 --> 00:22:01,490
sy'n golygu parhau â'r subarray blaenorol,

299
00:22:01,490 --> 00:22:07,250
neu 0, dechrau subarray newydd yn fy mynegai ar hyn o bryd.

300
00:22:07,250 --> 00:22:10,060
Ac unwaith y byddwn wedi adeiladu i fyny y tabl hwn o atebion, yna mae ein ateb terfynol,

301
00:22:10,060 --> 00:22:13,950
dim ond gwneud ysgubo llinol ar draws y llu subproblem

302
00:22:13,950 --> 00:22:19,890
ac yn cymryd y nifer mwyaf posibl.

303
00:22:19,890 --> 00:22:23,330
Mae hwn yn gweithredu union yr hyn yr wyf newydd ei ddweud.

304
00:22:23,330 --> 00:22:27,320
Felly, rydym yn creu amrywiaeth subproblem newydd, subproblems.

305
00:22:27,320 --> 00:22:32,330
Y cofnod cyntaf yw naill ai 0 neu y cofnod cyntaf, yr uchafswm o'r ddau.

306
00:22:32,330 --> 00:22:35,670
Ac ar gyfer gweddill y subproblems

307
00:22:35,670 --> 00:22:39,810
byddwn yn defnyddio'r digwydd eto yn union yr ydym yn unig darganfod.

308
00:22:39,810 --> 00:22:49,960
Nawr rydym gyfrifo uchafswm ein subproblems array, a dyna ein hateb terfynol.

309
00:22:49,960 --> 00:22:54,130
>> Felly, faint o le yr ydym yn defnyddio yn y algorithm?

310
00:22:54,130 --> 00:23:01,470
Os ydych wedi cymryd dim ond CS50, yna efallai nad ydych wedi trafod o le yn fawr iawn.

311
00:23:01,470 --> 00:23:07,750
Wel, un peth i'w nodi yw fy mod wedi galw malloc yma gyda n maint.

312
00:23:07,750 --> 00:23:13,590
Beth mae hynny'n awgrymu i chi?

313
00:23:13,590 --> 00:23:17,450
Mae'r algorithm yn defnyddio gofod llinol.

314
00:23:17,450 --> 00:23:21,030
Allwn ni wneud yn well?

315
00:23:21,030 --> 00:23:30,780
A oes unrhyw beth y byddwch yn sylwi bod yn ddiangen i gyfrifo yr ateb terfynol?

316
00:23:30,780 --> 00:23:33,290
Amcana gwestiwn gwell yw, pa wybodaeth

317
00:23:33,290 --> 00:23:40,680
Nid oes angen i ni yr holl ffordd drwodd i'r diwedd?

318
00:23:40,680 --> 00:23:44,280
Yn awr, os ydym yn edrych ar y ddwy linell,

319
00:23:44,280 --> 00:23:47,720
byddwn ond yn gofalu am y subproblem blaenorol,

320
00:23:47,720 --> 00:23:50,910
a dim ond gofalu am yr uchafswm ydym wedi gweld erioed hyd yn hyn.

321
00:23:50,910 --> 00:23:53,610
I gyfrifo ein hateb terfynol, nid oes angen yr amrywiaeth gyfan.

322
00:23:53,610 --> 00:23:57,450
Dim ond angen y rhif olaf, yn para dau rif.

323
00:23:57,450 --> 00:24:02,630
Rhif olaf ar gyfer, array subproblem a rhif olaf ar gyfer yr uchafswm.

324
00:24:02,630 --> 00:24:07,380
Felly, mewn gwirionedd, gallwn ffiws hyn dolenni at ei gilydd

325
00:24:07,380 --> 00:24:10,460
ac yn mynd o le i le llinol yn gyson.

326
00:24:10,460 --> 00:24:15,830
Swm ar hyn o bryd hyd yn hyn, dyma, yn disodli'r rôl subproblem, ein amrywiaeth subproblem.

327
00:24:15,830 --> 00:24:20,020
Swm Felly ar hyn o bryd, hyd yma, yw'r ateb i'r subproblem blaenorol.

328
00:24:20,020 --> 00:24:23,450
Ac y swm hwnnw, hyd yn hyn, yn cymryd lle ein max.

329
00:24:23,450 --> 00:24:28,100
Rydym gyfrifo uchafswm wrth i ni fynd ymlaen.

330
00:24:28,100 --> 00:24:30,890
Ac felly rydym yn mynd o le llinol i ofod gyson,

331
00:24:30,890 --> 00:24:36,650
ac mae gennym hefyd ateb llinol i'n problem subarray.

332
00:24:36,650 --> 00:24:40,740
>> Mae'r mathau hyn o gwestiynau y byddwch yn ei gael yn ystod cyfweliad.

333
00:24:40,740 --> 00:24:44,450
Beth yw cymhlethdod amser; beth yw'r cymhlethdod gofod?

334
00:24:44,450 --> 00:24:50,600
Allwch chi wneud yn well? Oes yna bethau sy'n ddiangen i'w cadw?

335
00:24:50,600 --> 00:24:55,270
Fe wnes i hyn i dynnu sylw at ddadansoddiadau y dylech eu cymryd ar eich pen eich hun

336
00:24:55,270 --> 00:24:57,400
wrth i chi weithio drwy'r problemau hyn.

337
00:24:57,400 --> 00:25:01,710
Bob amser yn gofyn i chi eich hun, "Alla i wneud yn well?"

338
00:25:01,710 --> 00:25:07,800
Yn wir, a allwn ni wneud yn well na hyn?

339
00:25:07,800 --> 00:25:10,730
Fath o gwestiwn tric. Nid ydych yn gallu, oherwydd mae angen i chi

340
00:25:10,730 --> 00:25:13,590
o leiaf yn darllen y mewnbwn i'r broblem.

341
00:25:13,590 --> 00:25:15,570
Felly, y ffaith bod angen i chi o leiaf ddarllen y mewnbwn i'r broblem

342
00:25:15,570 --> 00:25:19,580
yn golygu na allwch chi wneud yn well nag amser llinol,

343
00:25:19,580 --> 00:25:22,870
ac ni allwch wneud yn well na ofod gyson.

344
00:25:22,870 --> 00:25:27,060
Felly, mae hyn, mewn gwirionedd, yr ateb gorau i'r broblem hon.

345
00:25:27,060 --> 00:25:33,040
Cwestiynau? Iawn.

346
00:25:33,040 --> 00:25:35,190
>> Problem farchnad Stoc:

347
00:25:35,190 --> 00:25:38,350
"O ystyried amrywiaeth o gyfanrifau n, cadarnhaol, sero, neu negyddol,

348
00:25:38,350 --> 00:25:41,680
sy'n cynrychioli'r pris stoc dros gyfnod o ddyddiau n,

349
00:25:41,680 --> 00:25:44,080
ysgrifennu swyddogaeth i gyfrifo yr elw mwyaf y gallwch ei wneud

350
00:25:44,080 --> 00:25:49,350
ystyried eich bod yn prynu a gwerthu yn union 1 Stoc o fewn y dyddiau n. "

351
00:25:49,350 --> 00:25:51,690
Yn y bôn, rydym yn awyddus i brynu isel, gwerthu uchel.

352
00:25:51,690 --> 00:25:58,580
Ac rydym am i chyfrif i maes y elw gorau y gallwn ei wneud.

353
00:25:58,580 --> 00:26:11,500
Fynd yn ôl at fy tip, beth yw'r amlwg ar unwaith, ateb symlaf, ond mae'n araf?

354
00:26:11,500 --> 00:26:17,690
Ydw? (Myfyrwyr, annealladwy) >> Ydy.

355
00:26:17,690 --> 00:26:21,470
>> Felly byddech yn unig yn mynd er bod ac edrych ar y prisiau stoc

356
00:26:21,470 --> 00:26:30,550
ar bob pwynt mewn amser, (annealladwy).

357
00:26:30,550 --> 00:26:33,990
[Yu] Iawn, felly mae ei ateb - mae ei awgrym o gyfrifiadura

358
00:26:33,990 --> 00:26:37,380
nad yr isaf a chyfrifiadurol yr uchaf o reidrwydd yn gweithio

359
00:26:37,380 --> 00:26:42,470
oherwydd gallai'r uchaf yn digwydd cyn yr isaf.

360
00:26:42,470 --> 00:26:47,340
Felly beth yw'r ateb 'n ysgrublaidd dreisio i'r broblem hon?

361
00:26:47,340 --> 00:26:53,150
Beth yw'r ddau beth sydd angen i mi benderfynu unigryw yr elw i'n gwneud? Hawl.

362
00:26:53,150 --> 00:26:59,410
Yr ateb yw 'n ysgrublaidd dreisio - oh, felly, George awgrym yw ein bod dim ond angen dau ddiwrnod

363
00:26:59,410 --> 00:27:02,880
i bennu unigryw yr elw o'r ddau ddiwrnod.

364
00:27:02,880 --> 00:27:06,660
Felly, rydym yn cyfrifo bob pâr, fel prynu / gwerthu,

365
00:27:06,660 --> 00:27:12,850
gyfrifo elw, a allai fod yn negyddol neu'n gadarnhaol neu sero.

366
00:27:12,850 --> 00:27:18,000
Gyfrifo elw mwyaf yr ydym yn gwneud ar ôl ailadrodd dros yr holl barau o ddyddiau.

367
00:27:18,000 --> 00:27:20,330
Bydd hynny'n ein hateb terfynol.

368
00:27:20,330 --> 00:27:25,730
A bydd yr ateb hwnnw yn O (n ^ 2), oherwydd bod n dewis dau bâr -

369
00:27:25,730 --> 00:27:30,270
y dyddiau y gallwch ddewis ymhlith ddyddiau diwedd.

370
00:27:30,270 --> 00:27:32,580
Iawn, felly nid wyf ddim yn mynd i fynd dros yr ateb 'n ysgrublaidd dreisio yma.

371
00:27:32,580 --> 00:27:37,420
Rydw i'n mynd i ddweud wrthych fod yna ateb n log n.

372
00:27:37,420 --> 00:27:45,550
Pa algorithm ydych chi'n gwybod bod ar hyn o bryd yw n log n?

373
00:27:45,550 --> 00:27:50,730
Nid yw'n gwestiwn castia.

374
00:27:50,730 --> 00:27:54,790
>> Cyfuno fath. Cyfuno fath yw n log n,

375
00:27:54,790 --> 00:27:57,760
ac yn wir, un ffordd o ddatrys y broblem hon yw defnyddio

376
00:27:57,760 --> 00:28:04,400
math fath o syniad uno a elwir, yn gyffredinol, rhannu a goncro.

377
00:28:04,400 --> 00:28:07,570
Ac y syniad yw fel a ganlyn.

378
00:28:07,570 --> 00:28:12,400
Rydych am i gyfrifo y prynu gorau / gwerthu pâr yn yr hanner chwith.

379
00:28:12,400 --> 00:28:16,480
Dod o hyd yr elw gorau y gallwch ei wneud, yn unig â'r n gyntaf dros ddau ddiwrnod.

380
00:28:16,480 --> 00:28:19,780
Yna byddwch eisiau oompute y prynu gorau / gwerthu pâr ar yr hanner dde,

381
00:28:19,780 --> 00:28:23,930
felly mae'r n ddiwethaf dros ddau ddiwrnod.

382
00:28:23,930 --> 00:28:32,400
Ac yn awr y cwestiwn yw, sut rydym yn cyfuno'r atebion ôl at ei gilydd?

383
00:28:32,400 --> 00:28:36,320
Ydw? (Myfyrwyr, annealladwy)

384
00:28:36,320 --> 00:28:49,890
>> Iawn. Felly, gadewch i mi dynnu llun.

385
00:28:49,890 --> 00:29:03,870
Ydw? (George, annealladwy)

386
00:29:03,870 --> 00:29:06,450
>> Yn union. George ateb yn union gywir.

387
00:29:06,450 --> 00:29:10,040
Felly ei awgrym yw, yn gyntaf gyfrifo y gorau prynu / gwerthu pâr,

388
00:29:10,040 --> 00:29:16,050
ac sy'n digwydd yn yr hanner chwith, felly gadewch i ni alw y chwith, ar ôl.

389
00:29:16,050 --> 00:29:20,790
Gorau prynu / gwerthu pâr sy'n digwydd yn yr hanner cywir.

390
00:29:20,790 --> 00:29:25,180
Ond os ydym yn cymharu dim ond y ddau rif hyn, rydym yn colli achos

391
00:29:25,180 --> 00:29:30,460
lle rydym yn prynu ac yn gwerthu yma yn rhywle yn yr hanner cywir.

392
00:29:30,460 --> 00:29:33,810
Rydym yn prynu yn yr hanner chwith, gwerthu yn yr hanner cywir.

393
00:29:33,810 --> 00:29:38,490
A'r ffordd orau i gyfrifo y gorau prynu / gwerthu pâr sy'n rhychwantu dau hanner

394
00:29:38,490 --> 00:29:43,480
yw i gyfrifo isafswm yma ac gyfrifo uchafswm yma

395
00:29:43,480 --> 00:29:45,580
ac yn cymryd eu gwahaniaeth.

396
00:29:45,580 --> 00:29:50,850
Felly, y ddau achos lle mae'r pâr prynu / gwerthu yn digwydd yn unig yma,

397
00:29:50,850 --> 00:30:01,910
yn unig yma, neu ar y ddau hanner yn cael ei ddiffinio gan y tri rhif.

398
00:30:01,910 --> 00:30:06,450
Felly mae ein algorithm i uno ein datrysiadau ôl at ei gilydd,

399
00:30:06,450 --> 00:30:08,350
rydym am i gyfrifo y gorau prynu / gwerthu pâr

400
00:30:08,350 --> 00:30:13,120
lle rydym yn prynu ar yr hanner chwith a gwerthu ar yr hanner dde.

401
00:30:13,120 --> 00:30:16,740
A'r ffordd orau o wneud hynny yw i gyfrifo y pris isaf yn yr hanner cyntaf,

402
00:30:16,740 --> 00:30:20,360
y pris uchaf yn yr hanner iawn, ac yn cymryd eu gwahaniaeth.

403
00:30:20,360 --> 00:30:25,390
Mae'r tri deillio o elw, mae'r rhain yn dri rhif, byddwch yn cymryd yr uchafswm o'r tri,

404
00:30:25,390 --> 00:30:32,720
a dyna yr elw gorau y gallwch ei wneud dros y diwrnod cyntaf a diwrnod diwedd.

405
00:30:32,720 --> 00:30:36,940
Yma, mae'r llinellau pwysig yn goch.

406
00:30:36,940 --> 00:30:41,160
Mae hyn yn galw recursive i gyfrifo yr ateb yn yr hanner chwith.

407
00:30:41,160 --> 00:30:44,760
Mae hyn yn galw recursive i gyfrifo yr ateb yn hanner cywir.

408
00:30:44,760 --> 00:30:50,720
Mae'r rhain dau ar gyfer dolenni gyfrifo min a'r uchafswm ar yr hanner chwith a dde, yn y drefn honno.

409
00:30:50,720 --> 00:30:54,970
Nawr rwy'n gyfrifo elw sy'n rhychwantu dau hanner,

410
00:30:54,970 --> 00:31:00,530
a'r ateb terfynol yw'r mwyaf o'r tri hyn.

411
00:31:00,530 --> 00:31:04,120
Iawn.

412
00:31:04,120 --> 00:31:06,420
>> Felly, yn sicr, mae gennym algorithm, ond y cwestiwn mwy yw,

413
00:31:06,420 --> 00:31:08,290
beth yw cymhlethdod amser o hyn?

414
00:31:08,290 --> 00:31:16,190
A'r rheswm pam y crybwyllais uno fath yw bod y math hwn o rannu yr ateb

415
00:31:16,190 --> 00:31:19,200
yn ddau ac yna uno ein datrysiadau ôl at ei gilydd

416
00:31:19,200 --> 00:31:23,580
yn union y math o uno fath.

417
00:31:23,580 --> 00:31:33,360
Felly, gadewch i mi fynd drwy gydol.

418
00:31:33,360 --> 00:31:41,340
Os byddwn yn diffinio swyddogaeth (n) t i fod yn nifer o gamau

419
00:31:41,340 --> 00:31:50,010
am ddyddiau n,

420
00:31:50,010 --> 00:31:54,350
ein dwy alwad recursive

421
00:31:54,350 --> 00:32:00,460
yn cael eu pob un yn mynd i gostio t (n / 2),

422
00:32:00,460 --> 00:32:03,540
ac mae dau o'r galwadau hyn.

423
00:32:03,540 --> 00:32:10,020
Nawr mae angen i gyfrifo isafswm o hanner chwith,

424
00:32:10,020 --> 00:32:17,050
y gallaf ei wneud yn n / 2 amser, yn ogystal â'r uchafswm o hanner cywir.

425
00:32:17,050 --> 00:32:20,820
Felly, mae hyn yn n unig.

426
00:32:20,820 --> 00:32:25,050
Ac yna yn ogystal â rhywfaint o waith cyson.

427
00:32:25,050 --> 00:32:27,770
Ac mae hyn yn digwydd eto hafaliad

428
00:32:27,770 --> 00:32:35,560
yn union yr hafaliad eto ar gyfer uno fath.

429
00:32:35,560 --> 00:32:39,170
Ac rydym i gyd yn gwybod bod uno fath yw n log n amser.

430
00:32:39,170 --> 00:32:46,880
Felly, mae ein algorithm yn n hefyd log n amser.

431
00:32:46,880 --> 00:32:52,220
A yw hyn yn fersiwn yn gwneud synnwyr?

432
00:32:52,220 --> 00:32:55,780
Dim ond ailadrodd byr o'r hyn:

433
00:32:55,780 --> 00:32:59,170
T (n) yw nifer o gamau i gyfrifo yr elw mwyaf

434
00:32:59,170 --> 00:33:02,750
dros gyfnod o ddyddiau n.

435
00:33:02,750 --> 00:33:06,010
Mae'r ffordd yr ydym gwahanu ein galwadau recursive

436
00:33:06,010 --> 00:33:11,980
yw drwy ffonio ein ateb ar y dyddiau n / 2 gyntaf,

437
00:33:11,980 --> 00:33:14,490
felly dyna un alwad,

438
00:33:14,490 --> 00:33:16,940
ac yna rydym yn galw unwaith eto ar yr ail hanner.

439
00:33:16,940 --> 00:33:20,440
Felly dyna dwy alwad.

440
00:33:20,440 --> 00:33:25,310
Ac yna rydym yn dod o hyd o leiaf ar yr hanner chwith, y gallwn ei wneud mewn pryd llinol,

441
00:33:25,310 --> 00:33:29,010
ddod o hyd i'r uchafswm o hanner iawn, y gallwn ei wneud mewn amser llinol.

442
00:33:29,010 --> 00:33:31,570
Felly n / 2 + n / 2 yn unig n.

443
00:33:31,570 --> 00:33:36,020
Yna, mae gennym rywfaint o waith cyson, sydd fel gwneud rhifyddeg.

444
00:33:36,020 --> 00:33:39,860
Mae'r hafaliad digwydd eto yn union yr hafaliad eto ar gyfer uno fath.

445
00:33:39,860 --> 00:33:55,490
Felly, mae ein algorithm siffrwd hefyd logio n n.

446
00:33:55,490 --> 00:33:58,520
Felly, faint o le yr ydym yn ei ddefnyddio?

447
00:33:58,520 --> 00:34:04,910
Gadewch i ni fynd yn ôl at y cod.

448
00:34:04,910 --> 00:34:09,420
>> Cwestiwn gwell yw, faint o fframiau stac ydym byth ar unrhyw adeg benodol?

449
00:34:09,420 --> 00:34:11,449
Ers i ni yn defnyddio dychweliad,

450
00:34:11,449 --> 00:34:23,530
nifer y fframiau a stac yn pennu ein defnydd o le.

451
00:34:23,530 --> 00:34:29,440
Gadewch i ni ystyried n = 8.

452
00:34:29,440 --> 00:34:36,889
Rydym yn galw ar 8 siffrwd,

453
00:34:36,889 --> 00:34:41,580
a fydd yn galw siffrwd ar y pedwar cyntaf cofnodion,

454
00:34:41,580 --> 00:34:46,250
a fydd yn galw shuffle ar y ddau gyntaf cofnodion.

455
00:34:46,250 --> 00:34:51,550
Felly mae ein stac yw - mae hyn yn ein pentwr.

456
00:34:51,550 --> 00:34:54,980
Ac yna rydym yn galw siffrwd eto ar 1,

457
00:34:54,980 --> 00:34:58,070
a dyna beth yw ein sylfaen yn achos, felly byddwn yn dychwelyd ar unwaith.

458
00:34:58,070 --> 00:35:04,700
A oes gennym erioed wedi mwy na hyn fframiau stac lawer?

459
00:35:04,700 --> 00:35:08,880
Rhif Gan fod pob tro y byddwn yn gwneud invocation,

460
00:35:08,880 --> 00:35:10,770
a invocation recursive i siffrwd,

461
00:35:10,770 --> 00:35:13,950
rydym yn rhannu ein maint yn ei hanner.

462
00:35:13,950 --> 00:35:17,020
Felly, y nifer uchaf o fframiau stac ni byth ar unrhyw adeg benodol

463
00:35:17,020 --> 00:35:28,460
ar y drefn fframiau log n simnai.

464
00:35:28,460 --> 00:35:42,460
Mae gan bob ffrâm pentwr o ofod gyson,

465
00:35:42,460 --> 00:35:44,410
ac felly cyfanswm y gofod,

466
00:35:44,410 --> 00:35:49,240
y swm uchaf o le fyddwn byth yn defnyddio yw O (log n) lle

467
00:35:49,240 --> 00:36:03,040
lle mae n yw nifer y dyddiau.

468
00:36:03,040 --> 00:36:07,230
>> Nawr, gofynnwch bob amser i chi'ch hun, "Allwn ni wneud yn well?"

469
00:36:07,230 --> 00:36:12,390
Ac yn arbennig, rydym yn lleihau hyn i broblem yr ydym wedi ei datrys yn barod?

470
00:36:12,390 --> 00:36:20,040
Mae awgrym: dim ond trafod dwy broblem eraill cyn hyn, ac nid yw'n mynd i fod yn siffrwd.

471
00:36:20,040 --> 00:36:26,200
Gallwn newid y stoc problem farchnad i mewn i'r broblem subarray mwyaf posibl.

472
00:36:26,200 --> 00:36:40,100
Sut allwn ni wneud hyn?

473
00:36:40,100 --> 00:36:42,570
Un ohonoch chi? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, annealladwy)

475
00:36:47,680 --> 00:36:53,860
[Yu] Yn union.

476
00:36:53,860 --> 00:36:59,940
Felly mae'r broblem subarray mwyaf posibl,

477
00:36:59,940 --> 00:37:10,610
rydym yn chwilio am swm dros subarray parhaus.

478
00:37:10,610 --> 00:37:16,230
Ac Emmy awgrym am y broblem stociau,

479
00:37:16,230 --> 00:37:30,720
ystyried y newidiadau, neu y deltâu.

480
00:37:30,720 --> 00:37:37,440
A llun o hyn yw - mae hyn yn y pris stoc,

481
00:37:37,440 --> 00:37:42,610
ond os ydym yn cymryd y gwahaniaeth rhwng pob diwrnod yn olynol -

482
00:37:42,610 --> 00:37:45,200
felly rydym yn gweld bod y pris uchaf, elw mwyaf posibl y gallem eu gwneud

483
00:37:45,200 --> 00:37:50,070
yw os ydym yn prynu ac yn gwerthu yma yma.

484
00:37:50,070 --> 00:37:54,240
Ond gadewch i ni edrych ar y barhaus - gadewch i ni edrych ar y broblem subarray.

485
00:37:54,240 --> 00:38:02,510
Felly yma, y ​​gallwn wneud - mynd oddi yma i yma,

486
00:38:02,510 --> 00:38:08,410
gennym newid cadarnhaol, ac yna yn mynd oddi yma i yma mae gennym wedi newid er gwaeth.

487
00:38:08,410 --> 00:38:14,220
Ond yna, yn mynd oddi yma i yma mae gennym newid cadarnhaol enfawr.

488
00:38:14,220 --> 00:38:20,930
Ac mae'r rhain yn newidiadau yr ydym eisiau i grynhoi i gael ein elw terfynol.

489
00:38:20,930 --> 00:38:25,160
Yna, mae gennym newidiadau mwy negyddol yma.

490
00:38:25,160 --> 00:38:29,990
Yr allwedd i leihau ein problem stoc i mewn i'n problem subarray mwyaf posibl

491
00:38:29,990 --> 00:38:36,630
yw ystyried y deltâu rhwng diwrnodau.

492
00:38:36,630 --> 00:38:40,630
Felly, rydym yn creu amrywiaeth newydd o'r enw deltâu,

493
00:38:40,630 --> 00:38:43,000
ymgychwyn y cofnod cyntaf i fod yn 0,

494
00:38:43,000 --> 00:38:46,380
ac yna ar gyfer pob delta (i), gadael i hynny fod y gwahaniaeth

495
00:38:46,380 --> 00:38:52,830
o fy (i) array mewnbwn, a array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Yna, rydym yn galw ein trefn arferol ar gyfer subarray mwyaf posibl

497
00:38:55,530 --> 00:39:01,500
pasio mewn delta o amrywiaeth.

498
00:39:01,500 --> 00:39:06,440
Ac oherwydd subarray mwyaf posibl o amser llinol,

499
00:39:06,440 --> 00:39:09,370
ac y gostyngiad hwn, mae'r broses o greu'r amrywiaeth delta,

500
00:39:09,370 --> 00:39:11,780
Mae hefyd yn amser llinol,

501
00:39:11,780 --> 00:39:19,060
yna yr ateb terfynol ar gyfer stociau yw O (n) yn gweithio yn ogystal O (n) yn gweithio, yn dal O (n) yn gweithio.

502
00:39:19,060 --> 00:39:23,900
Felly mae gennym ateb amser llinol i'n problem.

503
00:39:23,900 --> 00:39:29,610
Ydy pawb yn deall y trawsnewid?

504
00:39:29,610 --> 00:39:32,140
>> Yn gyffredinol, yn syniad da y dylech bob amser

505
00:39:32,140 --> 00:39:34,290
yn ceisio lleihau'r broblem newydd yr ydych yn gweld.

506
00:39:34,290 --> 00:39:37,700
Os yw'n edrych yn gyfarwydd i hen broblem,

507
00:39:37,700 --> 00:39:39,590
ceisiwch leihau i hen broblem.

508
00:39:39,590 --> 00:39:41,950
Ac os allwch chi ddefnyddio'r holl offer yr ydych wedi eu defnyddio ar y hen broblem

509
00:39:41,950 --> 00:39:46,450
i ddatrys y broblem newydd.

510
00:39:46,450 --> 00:39:49,010
Felly, i lapio fyny, cyfweliadau technegol yn heriol.

511
00:39:49,010 --> 00:39:52,280
Mae'r problemau hyn yn debyg bod rhai o'r problemau mwyaf anodd

512
00:39:52,280 --> 00:39:54,700
y gallech eu gweld mewn cyfweliad,

513
00:39:54,700 --> 00:39:57,690
felly os nad ydych yn deall yr holl broblemau a grybwyllais yn unig, ei fod yn iawn.

514
00:39:57,690 --> 00:40:01,080
Mae'r rhain yn rhai o'r problemau yn fwy heriol.

515
00:40:01,080 --> 00:40:03,050
Ymarfer, ymarfer, ymarfer.

516
00:40:03,050 --> 00:40:08,170
Rhoddais llawer o broblemau yn y daflen, felly yn sicr wirio y rhai allan.

517
00:40:08,170 --> 00:40:11,690
A phob lwc ar eich cyfweliad. Mae pob fy adnoddau yn cael eu postio ar y ddolen hon,

518
00:40:11,690 --> 00:40:15,220
ac un o fy ffrindiau uwch wedi cynnig i wneud cyfweliadau ffug technegol,

519
00:40:15,220 --> 00:40:22,050
felly os oes gennych ddiddordeb, e-bost Will Yao yn y cyfeiriad e-bost.

520
00:40:22,050 --> 00:40:26,070
Os oes gennych gwestiynau, gallwch ofyn i mi.

521
00:40:26,070 --> 00:40:28,780
Ydych chi'n guys gennych gwestiynau penodol yn ymwneud â chyfweliadau technegol

522
00:40:28,780 --> 00:40:38,440
neu unrhyw broblemau yr ydym wedi ei weld hyd yn hyn?

523
00:40:38,440 --> 00:40:49,910
Iawn. Wel, pob lwc ar eich cyfweliad.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]