1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminaar: Tegnies Onderhoude]

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

3
00:00:04,630 --> 00:00:08,910
[Hierdie is CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi almal, Ek is Kenny. Ek is tans 'n junior bestudering van Rekenaarwetenskap.

5
00:00:12,420 --> 00:00:17,310
Ek is 'n voormalige CS TF, en ek wens ek het toe ek 'n underclassman,

6
00:00:17,310 --> 00:00:19,380
en dit is hoekom ek hierdie seminaar.

7
00:00:19,380 --> 00:00:21,370
So ek hoop jy geniet dit.

8
00:00:21,370 --> 00:00:23,470
Hierdie seminaar is oor die tegniese onderhoude,

9
00:00:23,470 --> 00:00:26,650
en al my hulpbronne kan gevind word by hierdie skakel,

10
00:00:26,650 --> 00:00:32,350
hierdie skakel reg hier, 'n paar van hulpbronne.

11
00:00:32,350 --> 00:00:36,550
So ek het 'n lys van probleme, eintlik 'n hele paar probleme.

12
00:00:36,550 --> 00:00:40,800
Ook 'n algemene hulpbronne bladsy waar ons kan kry wenke

13
00:00:40,800 --> 00:00:42,870
oor hoe om voor te berei vir 'n onderhoud,

14
00:00:42,870 --> 00:00:46,470
wenke oor wat jy moet doen tydens 'n werklike onderhoud,

15
00:00:46,470 --> 00:00:51,910
asook hoe om probleme en hulpbronne vir toekomstige verwysing te benader.

16
00:00:51,910 --> 00:00:53,980
Dit is al online.

17
00:00:53,980 --> 00:00:58,290
En net hierdie seminaar, 'n disclaimer voorwoord,

18
00:00:58,290 --> 00:01:00,690
soos dit behoort nie - jou onderhoud voorbereiding

19
00:01:00,690 --> 00:01:02,800
moet nie beperk word tot die lys.

20
00:01:02,800 --> 00:01:04,750
Dit is slegs bedoel om 'n gids te wees,

21
00:01:04,750 --> 00:01:08,890
en dan moet jy seker alles wat ek sê met 'n korrel sout,

22
00:01:08,890 --> 00:01:14,620
maar ook alles wat ek gebruik om jou te help in jou onderhoud voorbereiding gebruik.

23
00:01:14,620 --> 00:01:16,400
>> Ek gaan om te versnel deur die volgende paar skyfies

24
00:01:16,400 --> 00:01:18,650
sodat ons kan kry om die werklike gevallestudies.

25
00:01:18,650 --> 00:01:23,630
Die struktuur van 'n onderhoud vir 'n sagteware-ingenieurswese posisie,

26
00:01:23,630 --> 00:01:26,320
dit is tipies 30 tot 45 minute,

27
00:01:26,320 --> 00:01:29,810
verskeie rondes, afhangende van die maatskappy.

28
00:01:29,810 --> 00:01:33,090
Dikwels sal jy kodering word op 'n wit bord.

29
00:01:33,090 --> 00:01:35,960
So 'n wit bord soos hierdie, maar dikwels op 'n kleiner skaal.

30
00:01:35,960 --> 00:01:38,540
As jy 'n telefoon-onderhoud, sal jy waarskynlik gebruik word om

31
00:01:38,540 --> 00:01:44,030
óf collabedit of 'n Google Doc sodat hulle kan sien jy leef kodering

32
00:01:44,030 --> 00:01:46,500
terwyl jy 'n onderhoud oor die telefoon.

33
00:01:46,500 --> 00:01:48,490
'N onderhoud self is gewoonlik 2 of 3 probleme

34
00:01:48,490 --> 00:01:50,620
toets jou rekenaar wetenskaplike kennis.

35
00:01:50,620 --> 00:01:54,490
En dit sal byna beslis betrek kodering.

36
00:01:54,490 --> 00:01:59,540
Die tipe vrae wat jy sien is gewoonlik datastrukture en algoritmes.

37
00:01:59,540 --> 00:02:02,210
En in die doen van hierdie soort probleme,

38
00:02:02,210 --> 00:02:07,830
sal hulle jou vra, wil, wat is die tyd en ruimte kompleksiteit, groot O?

39
00:02:07,830 --> 00:02:09,800
Dikwels is hulle ook hoër-vlak vrae vra,

40
00:02:09,800 --> 00:02:12,530
so, die ontwerp van 'n stelsel,

41
00:02:12,530 --> 00:02:14,770
hoe sou jy jou kode uit te lê?

42
00:02:14,770 --> 00:02:18,370
Watter interfaces, wat klasse, wat modules het jy in jou stelsel,

43
00:02:18,370 --> 00:02:20,900
en hoe hierdie interaksie saam?

44
00:02:20,900 --> 00:02:26,130
So datastrukture en algoritmes sowel as die ontwerp stelsels.

45
00:02:26,130 --> 00:02:29,180
>> N paar algemene wenke voor ons duik in ons gevallestudies.

46
00:02:29,180 --> 00:02:32,300
Ek dink die belangrikste reël altyd dink hardop.

47
00:02:32,300 --> 00:02:36,980
Die onderhoud is veronderstel om jou kans om te wys af jou denke proses.

48
00:02:36,980 --> 00:02:39,820
Die punt van die onderhoud is vir die onderhoudvoerder te meet

49
00:02:39,820 --> 00:02:42,660
hoe jy dink en hoe jy gaan deur middel van 'n probleem.

50
00:02:42,660 --> 00:02:45,210
Die ergste ding wat jy kan doen, is om stil te bly oor die hele onderhoud.

51
00:02:45,210 --> 00:02:50,090
Dit is net nie goed.

52
00:02:50,090 --> 00:02:53,230
As jy 'n vraag gegee word, jy wil ook om seker te maak jy verstaan ​​die vraag.

53
00:02:53,230 --> 00:02:55,350
So herhaal die vraag terug in jou eie woorde

54
00:02:55,350 --> 00:02:58,920
en poging om deeglike 'n paar eenvoudige toets gevalle te werk

55
00:02:58,920 --> 00:03:01,530
om seker te maak jy verstaan ​​die vraag.

56
00:03:01,530 --> 00:03:05,510
Werk deur middel van 'n paar toets-gevalle sal ook vir jou 'n intuïsie oor hoe om hierdie probleem op te los.

57
00:03:05,510 --> 00:03:11,210
Jy kan selfs 'n paar patrone ontdek om jou te help om die probleem op te los.

58
00:03:11,210 --> 00:03:14,500
Hul groot tip is om geen gefrustreerd.

59
00:03:14,500 --> 00:03:17,060
Moet nie gefrustreerd.

60
00:03:17,060 --> 00:03:19,060
Onderhoude is uitdagend, maar die ergste ding wat jy kan doen,

61
00:03:19,060 --> 00:03:23,330
Bykomend tot die stil, sigbaar gefrustreerd is om te word.

62
00:03:23,330 --> 00:03:27,410
Jy wil nie die indruk te gee aan 'n onderhoudvoerder.

63
00:03:27,410 --> 00:03:33,960
Een ding wat jy - so, baie mense, wanneer hulle in 'n onderhoud,

64
00:03:33,960 --> 00:03:37,150
hulle probeer om te probeer om die beste oplossing te vind,

65
00:03:37,150 --> 00:03:39,950
wanneer regtig, daar is gewoonlik 'n paal bo water oplossing.

66
00:03:39,950 --> 00:03:43,500
Dit mag stadig wees, kan dit ondoeltreffend, maar jy moet net noem dit,

67
00:03:43,500 --> 00:03:46,210
net sodat jy het 'n beginpunt om 'n beter werk.

68
00:03:46,210 --> 00:03:48,270
Ook daarop te wys die oplossing is stadig, in terme van

69
00:03:48,270 --> 00:03:52,160
Big O kompleksiteit of ruimte kompleksiteit,

70
00:03:52,160 --> 00:03:54,450
sal demonstreer aan die onderhoudvoerder dat jy verstaan

71
00:03:54,450 --> 00:03:57,510
hierdie kwessies wanneer jou kode skryf.

72
00:03:57,510 --> 00:04:01,440
So moenie bang wees nie om te kom met die eenvoudigste algoritme 1

73
00:04:01,440 --> 00:04:04,950
en dan beter werk van daar af.

74
00:04:04,950 --> 00:04:09,810
Enige vrae tot dusver? Okay.

75
00:04:09,810 --> 00:04:11,650
>> So laat ons duik in ons eerste probleem.

76
00:04:11,650 --> 00:04:14,790
"Gegewe 'n verskeidenheid van n heelgetalle, skryf 'n funksie wat die skikking skud

77
00:04:14,790 --> 00:04:20,209
in die plek van so 'n aard dat alle permutasies van n heelgetalle ewe waarskynlik is. "

78
00:04:20,209 --> 00:04:23,470
En aanvaar wat jy beskikbaar het 'n ewekansige heelgetal generator

79
00:04:23,470 --> 00:04:30,980
wat verwek 'n heelgetal in 'n reeks van 0 tot i, 1/2 reeks.

80
00:04:30,980 --> 00:04:32,970
Verstaan ​​almal hierdie vraag?

81
00:04:32,970 --> 00:04:39,660
Ek gee jou 'n verskeidenheid van n heelgetalle, en ek wil hê jy moet shuffle dit.

82
00:04:39,660 --> 00:04:46,050
In my gids, het ek 'n paar programme om te demonstreer wat ek bedoel.

83
00:04:46,050 --> 00:04:48,910
Ek gaan om 'n skikking van 20 elemente te shuffle,

84
00:04:48,910 --> 00:04:52,490
van -10 tot 9,

85
00:04:52,490 --> 00:04:57,050
en ek wil hê dat jy 'n lys soos hierdie tot uitvoer.

86
00:04:57,050 --> 00:05:02,890
So dit is my gesorteer insette array, en ek wil hê jy moet shuffle dit.

87
00:05:02,890 --> 00:05:07,070
Ons sal dit weer doen.

88
00:05:07,070 --> 00:05:13,780
Nie almal verstaan ​​die vraag? Okay.

89
00:05:13,780 --> 00:05:16,730
So dit is aan jou.

90
00:05:16,730 --> 00:05:21,220
Wat is 'n paar idees? Kan jy dit doen as n ^ 2, n log N, N?

91
00:05:21,220 --> 00:05:34,400
Oop vir voorstelle.

92
00:05:34,400 --> 00:05:37,730
Okay. So 'n idee, voorgestel deur Emmy,

93
00:05:37,730 --> 00:05:45,300
is eers bereken 'n ewekansige getal, ewekansige heelgetal is, in 'n reeks van 0 tot 20.

94
00:05:45,300 --> 00:05:49,840
So aanvaar ons verskeidenheid het 'n lengte van 20.

95
00:05:49,840 --> 00:05:54,800
In ons diagram van 20 elemente,

96
00:05:54,800 --> 00:05:58,560
Dit is ons insette skikking.

97
00:05:58,560 --> 00:06:04,590
En nou, haar voorstel is om 'n nuwe skikking te skep,

98
00:06:04,590 --> 00:06:08,440
so dit sal die uitset skikking wees.

99
00:06:08,440 --> 00:06:12,880
En gebaseer op die i teruggekeer deur rand -

100
00:06:12,880 --> 00:06:17,580
So as ek was, kom ons sê, 17,

101
00:06:17,580 --> 00:06:25,640
Kopieer die 17de element in die eerste posisie.

102
00:06:25,640 --> 00:06:30,300
Nou het ons nodig het om te verwyder - ons moet al die elemente om hier te skuif

103
00:06:30,300 --> 00:06:36,920
oor so dat ons 'n gaping aan die einde en geen gate in die middel.

104
00:06:36,920 --> 00:06:39,860
En nou is ons herhaal die proses.

105
00:06:39,860 --> 00:06:46,360
Nou is ons kies 'n nuwe ewekansige heelgetal tussen 0 en 19.

106
00:06:46,360 --> 00:06:52,510
Ons het 'n nuwe ek hier, en ons kopie van hierdie element in hierdie posisie.

107
00:06:52,510 --> 00:07:00,960
Dan sal ons skuif items oor en ons herhaal die proses totdat ons het ons volle nuwe skikking.

108
00:07:00,960 --> 00:07:05,890
Wat is die aanloop tyd van hierdie algoritme?

109
00:07:05,890 --> 00:07:08,110
Wel, laat ons kyk na die impak van hierdie.

110
00:07:08,110 --> 00:07:10,380
Ons is die verskuiwing van elke element.

111
00:07:10,380 --> 00:07:16,800
Wanneer ons dit Ek, ons skuif al die elemente na aan die linkerkant.

112
00:07:16,800 --> 00:07:21,600
En dit is 'n O (n)-koste

113
00:07:21,600 --> 00:07:26,100
want wat as ons die eerste element verwyder?

114
00:07:26,100 --> 00:07:29,670
Dus, vir elke verwydering, verwyder ons -

115
00:07:29,670 --> 00:07:32,170
elke verwydering aangegaan 'n O (n) werking,

116
00:07:32,170 --> 00:07:41,520
en aangesien ons het N verskuiwings, dit lei tot 'n O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okay. So goed begin. N goeie begin.

118
00:07:49,550 --> 00:07:55,290
>> Nog 'n voorstel is iets wat bekend staan ​​as die Knuth shuffle te gebruik,

119
00:07:55,290 --> 00:07:57,540
of die Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
En dit is eintlik 'n lineêre tyd shuffle.

121
00:07:59,630 --> 00:08:02,200
En die idee is baie soortgelyk.

122
00:08:02,200 --> 00:08:05,160
Weereens, ons het ons insette skikking,

123
00:08:05,160 --> 00:08:08,580
maar in plaas van die gebruik van twee skikkings vir ons input / output,

124
00:08:08,580 --> 00:08:13,590
ons die eerste gedeelte van die skikking gebruik om tred te hou van ons skuifel gedeelte,

125
00:08:13,590 --> 00:08:18,400
en ons hou, en dan laat ons die res van ons verskeidenheid vir die unshuffled gedeelte.

126
00:08:18,400 --> 00:08:24,330
So hier is wat ek bedoel. Ons begin met ons kies 'n i,

127
00:08:24,330 --> 00:08:30,910
'n verskeidenheid 0-20.

128
00:08:30,910 --> 00:08:36,150
Ons huidige wyser wys na die eerste indeks.

129
00:08:36,150 --> 00:08:39,590
Ons kies 'n paar ek hier

130
00:08:39,590 --> 00:08:42,740
en nou is ons ruil.

131
00:08:42,740 --> 00:08:47,690
So as dit was 5 en dit was 4,

132
00:08:47,690 --> 00:08:57,150
die gevolglike skikking 5 here en 4 hier.

133
00:08:57,150 --> 00:09:00,390
En nou het ons kennis neem van 'n merker hier.

134
00:09:00,390 --> 00:09:05,770
Alles aan die linkerkant is skuifel,

135
00:09:05,770 --> 00:09:15,160
en alles wat aan die regterkant is unshuffled.

136
00:09:15,160 --> 00:09:17,260
En nou kan ons herhaal die proses.

137
00:09:17,260 --> 00:09:25,210
Ons kies 'n ewekansige indeks tussen 1 en 20 nou.

138
00:09:25,210 --> 00:09:30,650
So veronderstel ons nuwe ek hier is.

139
00:09:30,650 --> 00:09:39,370
Nou ruil ons hierdie i met ons huidige nuwe posisie.

140
00:09:39,370 --> 00:09:44,790
Sodat ons 'n uitruiling heen en weer soos hierdie.

141
00:09:44,790 --> 00:09:51,630
Laat my bring die kode om dit meer konkreet te maak.

142
00:09:51,630 --> 00:09:55,290
Ons begin met ons keuse van i -

143
00:09:55,290 --> 00:09:58,370
ons begin met i gelyk aan 0, ons kies 'n ewekansige plek j

144
00:09:58,370 --> 00:10:02,420
in die unshuffled gedeelte van die skikking, i n-1.

145
00:10:02,420 --> 00:10:07,280
So as ek hier is, kies 'n ewekansige indeks tussen hier en die res van die skikking,

146
00:10:07,280 --> 00:10:12,410
en ons ruil.

147
00:10:12,410 --> 00:10:17,550
Dit is al die kode wat nodig is om shuffle jou skikking.

148
00:10:17,550 --> 00:10:21,670
Enige vrae?

149
00:10:21,670 --> 00:10:25,530
>> Wel, een nodig vraag is hoekom, is dit korrek?

150
00:10:25,530 --> 00:10:28,360
Hoekom is elke permutasie ewe waarskynlik is?

151
00:10:28,360 --> 00:10:30,410
En Ek sal nie gaan nie deur die bewys van hierdie,

152
00:10:30,410 --> 00:10:35,970
maar baie probleme in die rekenaar wetenskap bewys kan word deur middel van induksie.

153
00:10:35,970 --> 00:10:38,520
Hoeveel van julle is vertroud met induksie?

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

155
00:10:40,590 --> 00:10:43,610
Sodat jy kan die korrektheid van hierdie algoritme deur eenvoudige induksie bewys,

156
00:10:43,610 --> 00:10:49,540
waar jou induksie hipotese sou wees, aanvaar dat

157
00:10:49,540 --> 00:10:53,290
my shuffle terug elke permutasie ewe waarskynlik

158
00:10:53,290 --> 00:10:56,120
tot die eerste i-elemente.

159
00:10:56,120 --> 00:10:58,300
Nou, oorweeg i + 1.

160
00:10:58,300 --> 00:11:02,550
En deur die manier waarop ons kies om ons indeks j te ruil,

161
00:11:02,550 --> 00:11:05,230
dit lei tot - en dan moet jy die besonderhede uit te werk,

162
00:11:05,230 --> 00:11:07,390
ten minste 'n volle bewys van waarom hierdie algoritme terugkeer

163
00:11:07,390 --> 00:11:12,800
elke permutasie met ewe waarskynlike waarskynlikheid.

164
00:11:12,800 --> 00:11:15,940
>> Alle reg, volgende probleem.

165
00:11:15,940 --> 00:11:19,170
So "'n skikking van heelgetalle, positief, nul, negatiewe,

166
00:11:19,170 --> 00:11:21,290
Skryf 'n funksie wat die maksimum bedrag bereken

167
00:11:21,290 --> 00:11:24,720
van enige continueous subarray van die inset-skikking. "

168
00:11:24,720 --> 00:11:28,370
'N voorbeeld hier is, in die geval waar al die syfers is positief,

169
00:11:28,370 --> 00:11:31,320
dan is tans die beste keuse is om die hele skikking te neem.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, is gelyk aan 10.

171
00:11:34,690 --> 00:11:36,780
As jy het 'n paar negatiewe daar,

172
00:11:36,780 --> 00:11:38,690
in hierdie geval wil ons net die eerste twee

173
00:11:38,690 --> 00:11:44,590
want -1 en / of -3 te kies sal ons som bring.

174
00:11:44,590 --> 00:11:48,120
Soms het ons kan hê om te begin in die middel van die skikking.

175
00:11:48,120 --> 00:11:53,500
Soms wil ons niks te kies, dit is die beste om nie enigiets.

176
00:11:53,500 --> 00:11:56,490
En soms is dit beter om die val te neem,

177
00:11:56,490 --> 00:12:07,510
omdat die saak nadat dit is super groot. So enige idees?

178
00:12:07,510 --> 00:12:10,970
(Student, onverstaanbare) >> Ja.

179
00:12:10,970 --> 00:12:13,560
Gestel ek nie -1 nie.

180
00:12:13,560 --> 00:12:16,170
Ek kies dan óf 1.000 en 20.000,

181
00:12:16,170 --> 00:12:18,630
of ek het net die 3 miljard kies.

182
00:12:18,630 --> 00:12:20,760
Wel, die beste keuse is om al die nommers te neem.

183
00:12:20,760 --> 00:12:24,350
Dit -1, ten spyte van die negatiewe,

184
00:12:24,350 --> 00:12:31,340
die hele bedrag is beter as ek nie -1 te neem.

185
00:12:31,340 --> 00:12:36,460
So een van die punte wat ek vroeër genoem was die duidelik voor die hand liggend te stel

186
00:12:36,460 --> 00:12:40,540
en die brute krag oplossing eerste.

187
00:12:40,540 --> 00:12:44,340
Wat is die brute krag oplossing in hierdie probleem? Ja?

188
00:12:44,340 --> 00:12:46,890
[Jane] Wel, ek dink die brute krag oplossing

189
00:12:46,890 --> 00:12:52,600
sou wees om toe te voeg tot al die moontlike kombinasies (onverstaanbaar).

190
00:12:52,600 --> 00:12:58,250
[Yu] Goed. So Jane se idee is om elke moontlike te neem -

191
00:12:58,250 --> 00:13:01,470
Ek is parafrasering - is elke moontlike deurlopende subarray te neem,

192
00:13:01,470 --> 00:13:07,840
bereken die som, en dan neem om die maksimum van al die moontlike deurlopende subarrays.

193
00:13:07,840 --> 00:13:13,310
Wat as unieke identifikasie van 'n subarray in my insette array?

194
00:13:13,310 --> 00:13:17,380
Soos, watter twee dinge het ek nodig? Ja?

195
00:13:17,380 --> 00:13:19,970
(Student, onverstaanbare) >> Reg.

196
00:13:19,970 --> 00:13:22,130
'N ondergrens op die indeks en 'n bogrens-indeks

197
00:13:22,130 --> 00:13:28,300
unieke bepaal 'n deurlopende subarray.

198
00:13:28,300 --> 00:13:31,400
[Vroulik student] Is ons beraming dit is 'n verskeidenheid van unieke nommers?

199
00:13:31,400 --> 00:13:34,280
[Yu] No So haar vraag is, is ons die aanvaarding van ons verskeidenheid -

200
00:13:34,280 --> 00:13:39,000
is ons verskeidenheid unieke nommers, en die antwoord is nee.

201
00:13:39,000 --> 00:13:43,390
>> As ons ons brute krag oplossing, dan is die begin / einde indekse gebruik

202
00:13:43,390 --> 00:13:47,200
unieke bepaal ons deurlopende subarray.

203
00:13:47,200 --> 00:13:51,680
So as ons itereer vir alle moontlike begin inskrywings,

204
00:13:51,680 --> 00:13:58,320
en vir al die einde inskrywings> of = om te begin, en <n

205
00:13:58,320 --> 00:14:05,570
jy bereken die som, en dan moet ons neem om die maksimum bedrag wat ons tot dusver gesien het.

206
00:14:05,570 --> 00:14:07,880
Is dit duidelik?

207
00:14:07,880 --> 00:14:12,230
Wat is die groot O van hierdie oplossing?

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

209
00:14:16,660 --> 00:14:18,860
Nie heeltemal n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Let daarop dat ons van 0 tot n itereer

211
00:14:25,250 --> 00:14:27,520
so dit is een lus.

212
00:14:27,520 --> 00:14:35,120
Ons het weer itereer van byna die begin tot die einde, 'n ander vir die lus.

213
00:14:35,120 --> 00:14:37,640
En nou, binne daardie, ons het elke inskrywing op te som,

214
00:14:37,640 --> 00:14:43,810
so dit is 'n ander loop. So het ons drie geneste vir loops, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Dit gaan as 'n beginpunt.

216
00:14:46,560 --> 00:14:53,180
Ons oplossing is nie erger as n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Verstaan ​​almal die brute krag oplossing?

218
00:14:55,480 --> 00:14:59,950
>> Okay. 'N beter oplossing is met behulp van 'n idee met die naam van dinamiese programmering.

219
00:14:59,950 --> 00:15:03,040
As jy 'CS124, wat algoritmes en datastrukture,

220
00:15:03,040 --> 00:15:05,680
sal jy baie vertroud is met hierdie tegniek.

221
00:15:05,680 --> 00:15:12,190
En die idee is, probeer om die opbou oplossings vir kleiner probleme vir die eerste keer.

222
00:15:12,190 --> 00:15:17,990
Wat ek bedoel is, het ons tans hoef te bekommer oor twee dinge: begin en die einde.

223
00:15:17,990 --> 00:15:29,340
En dit is vervelend. Wat gebeur as ons kan ontslae te raak van een van daardie parameters?

224
00:15:29,340 --> 00:15:32,650
Een idee is om - we're ons oorspronklike probleem,

225
00:15:32,650 --> 00:15:37,470
vind die maksimum bedrag van enige subarray in 'n reeks [O, n-1].

226
00:15:37,470 --> 00:15:47,400
En nou het ons 'n nuwe subproblem, waar ons weet, in ons huidige indeks i

227
00:15:47,400 --> 00:15:52,520
ons weet dat ons daar moet sluit. Ons subarray moet 'n einde aan die huidige indeks.

228
00:15:52,520 --> 00:15:57,640
So die oorblywende probleem is, waar moet ons begin ons subarray?

229
00:15:57,640 --> 00:16:05,160
Maak dit sin? Okay.

230
00:16:05,160 --> 00:16:12,030
So ek het gekodeer hierdie up, en laat ons kyk na wat dit beteken.

231
00:16:12,030 --> 00:16:16,230
In die codirectory, daar is 'n program met die naam subarray,

232
00:16:16,230 --> 00:16:19,470
en dit neem die aantal items,

233
00:16:19,470 --> 00:16:25,550
en dit gee die maksimale subarray som in my skuifel lys.

234
00:16:25,550 --> 00:16:29,920
Dus, in hierdie geval, ons maksimale subarray 3.

235
00:16:29,920 --> 00:16:34,850
En dit is geneem deur net met 2 en 1.

236
00:16:34,850 --> 00:16:38,050
Kom ons loop dit weer. Dit is ook 3.

237
00:16:38,050 --> 00:16:40,950
Maar hierdie keer, let op hoe ons het die 3.

238
00:16:40,950 --> 00:16:46,690
Ons het die - ons het net die 3 self

239
00:16:46,690 --> 00:16:49,980
want dit is aan beide kante omring deur negatiewe,

240
00:16:49,980 --> 00:16:55,080
wat sal 'n som te bring <3.

241
00:16:55,080 --> 00:16:57,820
Kom ons loop op 10 items.

242
00:16:57,820 --> 00:17:03,200
Hierdie keer is dit 7, neem ons die voorste 3 en 4.

243
00:17:03,200 --> 00:17:09,450
Hierdie keer is dit 8, en kry ons dat deur die neem van 1, 3 en 4.

244
00:17:09,450 --> 00:17:16,310
Te gee jy 'n intuïsie oor hoe ons kan hierdie getransformeerde probleem op te los,

245
00:17:16,310 --> 00:17:18,890
Kom ons neem 'n blik op hierdie subarray.

246
00:17:18,890 --> 00:17:23,460
Ons is hierdie insette array, en ons weet die antwoord is 8.

247
00:17:23,460 --> 00:17:26,359
Ons neem die 1, 4, en 3.

248
00:17:26,359 --> 00:17:29,090
Maar laat ons kyk na hoe ons eintlik die antwoord gekry het.

249
00:17:29,090 --> 00:17:34,160
Kom ons kyk na die maksimum subarray wat by elk van hierdie indekse geëindig.

250
00:17:34,160 --> 00:17:40,780
Wat is die maksimum subarray wat by die eerste posisie aan die einde?

251
00:17:40,780 --> 00:17:46,310
[Studente] Zero. >> Zero. Net nie die -5.

252
00:17:46,310 --> 00:17:50,210
Hier is dit gaan wees 0 sowel. Ja?

253
00:17:50,210 --> 00:17:56,470
(Student, onverstaanbaar)

254
00:17:56,470 --> 00:17:58,960
[Yu] O, jammer, dit is 'n -3.

255
00:17:58,960 --> 00:18:03,220
So, dit is 'n 2, dit is 'n -3.

256
00:18:03,220 --> 00:18:08,690
Okay. So -4, wat is die maksimum subarray daardie posisie aan die einde

257
00:18:08,690 --> 00:18:12,910
waar -4 is? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Nou moet ek uiteindelik by die plek waar -2 is by.

260
00:18:28,060 --> 00:18:39,330
So 6, 5, 7, en die laaste een is 4.

261
00:18:39,330 --> 00:18:43,480
Die wete dat dit is my inskrywings

262
00:18:43,480 --> 00:18:48,130
vir die getransformeerde probleem waar ek moet eindig by elk van hierdie indekse,

263
00:18:48,130 --> 00:18:51,410
dan is my finale antwoord net, neem 'n sweep oor

264
00:18:51,410 --> 00:18:53,580
en neem die maksimum aantal.

265
00:18:53,580 --> 00:18:55,620
So in hierdie geval is dit 8.

266
00:18:55,620 --> 00:19:00,010
Dit impliseer dat die maksimale subarray eindig by hierdie indeks,

267
00:19:00,010 --> 00:19:04,970
en begin iewers voor dit.

268
00:19:04,970 --> 00:19:09,630
Verstaan ​​almal hierdie getransformeerde subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Wel, laat ons uit te vind die herhaling hiervoor.

270
00:19:22,160 --> 00:19:27,990
Kom ons kyk na net die eerste paar inskrywings.

271
00:19:27,990 --> 00:19:35,930
So hier is dit was 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
En dan was daar 'n -2 hier, en wat dit tot 6.

273
00:19:39,790 --> 00:19:50,800
So as ek noem die inskrywing by posisie i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
hoe kan ek gebruik om die antwoord op 'n vorige subproblem

275
00:19:54,910 --> 00:19:59,360
om hierdie subproblem te beantwoord?

276
00:19:59,360 --> 00:20:04,550
As ek kyk na die, kom ons sê, hierdie item.

277
00:20:04,550 --> 00:20:09,190
Hoe kan ek bereken deur te kyk na die antwoord 6

278
00:20:09,190 --> 00:20:18,780
'n kombinasie van die skikking en die antwoorde op vorige subprobleme in hierdie skikking? Ja?

279
00:20:18,780 --> 00:20:22,800
[Vroulik student] Jy neem die skikking van somme

280
00:20:22,800 --> 00:20:25,430
in die posisie reg voor dit, so die 8,

281
00:20:25,430 --> 00:20:32,170
en dan moet jy voeg die huidige subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] haar voorstel is dus om te kyk na hierdie twee getalle,

283
00:20:36,460 --> 00:20:40,090
hierdie nommer en hierdie getal.

284
00:20:40,090 --> 00:20:50,130
So, dit 8 verwys na die antwoord vir die subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
En laat ons bel my insette array A.

286
00:20:57,300 --> 00:21:01,470
Ten einde 'n maksimale subarray wat eindig by posisie i te vind,

287
00:21:01,470 --> 00:21:03,980
Ek het twee keuses: Ek kan voortgaan om die subarray

288
00:21:03,980 --> 00:21:09,790
wat geëindig het op die vorige indeks, of begin 'n nuwe skikking.

289
00:21:09,790 --> 00:21:14,190
As ek was die subarray wat begin het by die vorige indeks om voort te gaan,

290
00:21:14,190 --> 00:21:19,260
dan is die maksimum bedrag wat ek kan bereik, is die antwoord op die vorige subproblem

291
00:21:19,260 --> 00:21:24,120
plus die huidige verskeidenheid inskrywing.

292
00:21:24,120 --> 00:21:27,550
, Maar ek het ook die keuse van die begin van 'n nuwe subarray,

293
00:21:27,550 --> 00:21:30,830
in welke geval die bedrag is 0.

294
00:21:30,830 --> 00:21:42,860
So die antwoord is maksimum van 0, subproblem i - 1, plus die huidige verskeidenheid inskrywing.

295
00:21:42,860 --> 00:21:46,150
Is hierdie herhaling sin maak?

296
00:21:46,150 --> 00:21:50,840
Ons herhaling, as ons net ontdek, is subproblem i

297
00:21:50,840 --> 00:21:54,740
is gelyk aan die maksimum van die vorige subproblem plus my huidige skikking inskrywing,

298
00:21:54,740 --> 00:22:01,490
wat beteken voortgaan die vorige subarray,

299
00:22:01,490 --> 00:22:07,250
of 0, begin 'n nuwe subarray by my huidige indeks.

300
00:22:07,250 --> 00:22:10,060
En sodra ons opgebou hierdie tabel van oplossings, dan is ons finale antwoord,

301
00:22:10,060 --> 00:22:13,950
doen net 'n lineêre sweep oor die subproblem skikking

302
00:22:13,950 --> 00:22:19,890
en neem die maksimum aantal.

303
00:22:19,890 --> 00:22:23,330
Dit is 'n presiese uitvoering van wat ek nou net gesê.

304
00:22:23,330 --> 00:22:27,320
So skep ons 'n nuwe subproblem skikking, subprobleme.

305
00:22:27,320 --> 00:22:32,330
Die eerste inskrywing is óf 0 of die eerste inskrywing, die maksimum van die twee.

306
00:22:32,330 --> 00:22:35,670
En vir die res van die subprobleme

307
00:22:35,670 --> 00:22:39,810
ons gebruik die presiese herhaling wat ons net ontdek.

308
00:22:39,810 --> 00:22:49,960
Nou het ons bereken die maksimum van ons subprobleme verskeidenheid, en dit is ons finale antwoord.

309
00:22:49,960 --> 00:22:54,130
>> So hoeveel ruimte gebruik ons ​​in hierdie algoritme?

310
00:22:54,130 --> 00:23:01,470
As jy net CS50 geneem word, dan is jy dalk nie bespreek het ruimte baie.

311
00:23:01,470 --> 00:23:07,750
Wel, een ding om op te let is dat ek hier genoem malloc met die grootte n.

312
00:23:07,750 --> 00:23:13,590
Wat beteken dat raai u aan?

313
00:23:13,590 --> 00:23:17,450
Hierdie algoritme gebruik lineêre ruimte.

314
00:23:17,450 --> 00:23:21,030
Kan ons beter doen?

315
00:23:21,030 --> 00:23:30,780
Is daar enigiets wat jy sien dat dit onnodig om die finale antwoord te bereken?

316
00:23:30,780 --> 00:23:33,290
Ek dink 'n beter vraag is, watter inligting

317
00:23:33,290 --> 00:23:40,680
hoef ons nie al die pad deur te voer aan die einde?

318
00:23:40,680 --> 00:23:44,280
Nou, as ons kyk na hierdie twee lyne,

319
00:23:44,280 --> 00:23:47,720
ons net oor die vorige subproblem,

320
00:23:47,720 --> 00:23:50,910
en ons het net sorg oor die maksimum wat ons nog ooit gesien het so ver.

321
00:23:50,910 --> 00:23:53,610
Ons finale antwoord te bereken, het ons nie nodig om die hele skikking.

322
00:23:53,610 --> 00:23:57,450
Ons moet net die laaste nommer, die laaste twee getalle.

323
00:23:57,450 --> 00:24:02,630
Laaste nommer vir die subproblem array, en die laaste nommer vir die maksimum.

324
00:24:02,630 --> 00:24:07,380
Dus, in werklikheid, kan ons versmelt hierdie loops saam

325
00:24:07,380 --> 00:24:10,460
en gaan van lineêre ruimte konstante ruimte.

326
00:24:10,460 --> 00:24:15,830
Huidige som tot dusver hier, vervang die rol van subproblem, ons subproblem verskeidenheid.

327
00:24:15,830 --> 00:24:20,020
So huidige som, tot dusver, is die antwoord op die vorige subproblem.

328
00:24:20,020 --> 00:24:23,450
En daardie som, so ver, neem die plek van ons max.

329
00:24:23,450 --> 00:24:28,100
Ons bereken die maksimum as ons gaan saam.

330
00:24:28,100 --> 00:24:30,890
En so gaan ons van lineêre ruimte konstante ruimte,

331
00:24:30,890 --> 00:24:36,650
en ons het ook 'n lineêre oplossing vir ons subarray probleem.

332
00:24:36,650 --> 00:24:40,740
>> Hierdie soort vrae wat jy sal kry tydens 'n onderhoud.

333
00:24:40,740 --> 00:24:44,450
Wat is die tyd kompleksiteit, wat is die ruimte kompleksiteit?

334
00:24:44,450 --> 00:24:50,600
Kan jy beter doen? Is daar dinge wat onnodig te hou rond?

335
00:24:50,600 --> 00:24:55,270
Ek het hierdie ontleding na vore te bring, dat jy op jou eie moet neem

336
00:24:55,270 --> 00:24:57,400
as jy werk deur middel van hierdie probleme.

337
00:24:57,400 --> 00:25:01,710
Altyd vra jouself, "Kan ek beter doen?"

338
00:25:01,710 --> 00:25:07,800
In feite, kan ons beter doen as dit?

339
00:25:07,800 --> 00:25:10,730
Soort van 'n truuk vraag. Jy kan nie, want jy moet

340
00:25:10,730 --> 00:25:13,590
ten minste die inset vir die probleem te lees.

341
00:25:13,590 --> 00:25:15,570
En die feit dat jy nodig het om te lees ten minste die inset vir die probleem

342
00:25:15,570 --> 00:25:19,580
beteken dat jy nie beter kan doen as lineêre tyd,

343
00:25:19,580 --> 00:25:22,870
en jy kan dit nie doen beter as konstante ruimte.

344
00:25:22,870 --> 00:25:27,060
So, dit is, in werklikheid, die beste oplossing vir hierdie probleem.

345
00:25:27,060 --> 00:25:33,040
Vrae? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Aandelemark probleem:

347
00:25:35,190 --> 00:25:38,350
"Gegewe 'n verskeidenheid van n heelgetalle, positiewe, nul of negatief,

348
00:25:38,350 --> 00:25:41,680
wat die prys van 'n voorraad oor n dae,

349
00:25:41,680 --> 00:25:44,080
Skryf 'n funksie om die maksimum wins te bereken wat jy kan maak

350
00:25:44,080 --> 00:25:49,350
gegee dat jy presies 1 voorraad te koop en te verkoop binne hierdie N dae. "

351
00:25:49,350 --> 00:25:51,690
Wese, ons wil koop laag, verkoop hoog.

352
00:25:51,690 --> 00:25:58,580
En ons wil om uit te vind die beste wins wat ons kan maak.

353
00:25:58,580 --> 00:26:11,500
Terug te gaan na my punt, wat is die onmiddellik duidelik, die eenvoudigste antwoord, maar dit is stadig?

354
00:26:11,500 --> 00:26:17,690
Ja? (Student, onverstaanbare) >> Ja.

355
00:26:17,690 --> 00:26:21,470
>> So jy wil net al gaan kyk na die voorraad pryse

356
00:26:21,470 --> 00:26:30,550
by elke punt in tyd, (onverstaanbaar).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, so haar oplossing - haar voorstel van die rekenaar

358
00:26:33,990 --> 00:26:37,380
die laagste en die berekening van die hoogste nie noodwendig werk

359
00:26:37,380 --> 00:26:42,470
want die hoogste mag voorkom voor die laagste.

360
00:26:42,470 --> 00:26:47,340
So, wat is die brute krag oplossing vir hierdie probleem?

361
00:26:47,340 --> 00:26:53,150
Wat is die twee dinge wat ek nodig het om 'n unieke bepaal die wins wat ek maak? Reg.

362
00:26:53,150 --> 00:26:59,410
Die brute krag oplossing is - oh, so, George se voorstel is dat ons moet net twee dae

363
00:26:59,410 --> 00:27:02,880
unieke bepaal die wins van die twee dae.

364
00:27:02,880 --> 00:27:06,660
Dus bereken ons elke paar, wil koop / verkoop,

365
00:27:06,660 --> 00:27:12,850
bereken die wins, wat negatief of positief of nul kan wees.

366
00:27:12,850 --> 00:27:18,000
Bereken die maksimum wins wat ons maak na die iterating oor alle pare van dae.

367
00:27:18,000 --> 00:27:20,330
Dit sal ons finale antwoord wees.

368
00:27:20,330 --> 00:27:25,730
En dat die oplossing sal wees O (n ^ 2), want daar is 'n kies twee pare -

369
00:27:25,730 --> 00:27:30,270
dae wat jy kan kies tussen die einde dae.

370
00:27:30,270 --> 00:27:32,580
Okay, so ek is nie gaan om te gaan oor die brute krag oplossing hier.

371
00:27:32,580 --> 00:27:37,420
Ek gaan jou te vertel dat daar is 'n log n oplossing.

372
00:27:37,420 --> 00:27:45,550
Wat algoritme jy tans weet wat 'n log n?

373
00:27:45,550 --> 00:27:50,730
Dit is nie 'n truuk vraag.

374
00:27:50,730 --> 00:27:54,790
>> Merge soort. Merge soort is n log n,

375
00:27:54,790 --> 00:27:57,760
en in die feit, een manier om hierdie probleem op te los, is om te gebruik

376
00:27:57,760 --> 00:28:04,400
'n merge soort soort van die idee genoem, in die algemeen, te verdeel en oorwin.

377
00:28:04,400 --> 00:28:07,570
En die idee is soos volg.

378
00:28:07,570 --> 00:28:12,400
Jy wil die beste koop te bereken / paar verkoop in die linker helfte.

379
00:28:12,400 --> 00:28:16,480
Vind die beste wins wat jy kan maak, net met die eerste n oor twee dae.

380
00:28:16,480 --> 00:28:19,780
Dan is jy die beste koop oompute / paar verkoop op die regter helfte,

381
00:28:19,780 --> 00:28:23,930
sodat die laaste n oor twee dae.

382
00:28:23,930 --> 00:28:32,400
En nou is die vraag, hoe saamsmelt ons hierdie oplossings terug saam?

383
00:28:32,400 --> 00:28:36,320
Ja? (Student, onverstaanbaar)

384
00:28:36,320 --> 00:28:49,890
>> Goed. So laat my 'n prentjie teken.

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

386
00:29:03,870 --> 00:29:06,450
>> Presies. George se oplossing is presies reg.

387
00:29:06,450 --> 00:29:10,040
So het sy voorstel is, in die eerste bereken die beste koop / verkoop denim,

388
00:29:10,040 --> 00:29:16,050
en wat plaasvind in die linker helfte, so laat ons noem dat die links, links.

389
00:29:16,050 --> 00:29:20,790
Beste koop / verkoop paar wat plaasvind in die regte helfte.

390
00:29:20,790 --> 00:29:25,180
Maar as ons net hierdie twee getalle in vergelyking, mis ons die geval

391
00:29:25,180 --> 00:29:30,460
waar ons hier iewers in die regte helfte koop en verkoop.

392
00:29:30,460 --> 00:29:33,810
Ons koop, verkoop in die linker helfte in die regte helfte.

393
00:29:33,810 --> 00:29:38,490
En die beste manier om die beste koop / verkoop paar wat strek oor beide helftes te bereken

394
00:29:38,490 --> 00:29:43,480
is die minimum om hier te bereken en bereken die maksimum hier

395
00:29:43,480 --> 00:29:45,580
en neem hulle verskil.

396
00:29:45,580 --> 00:29:50,850
Sodat die twee gevalle waar die koop / verkoop-paar kom net hier,

397
00:29:50,850 --> 00:30:01,910
net hier, of op beide helftes word gedefinieer deur hierdie drie getalle.

398
00:30:01,910 --> 00:30:06,450
Sodat ons algoritme ons oplossings vir terug saamsmelt,

399
00:30:06,450 --> 00:30:08,350
ons wil die beste koop / verkoop paar te bereken

400
00:30:08,350 --> 00:30:13,120
waar ons koop op die linker helfte en verkoop op die regter helfte.

401
00:30:13,120 --> 00:30:16,740
En die beste manier om dit te doen, is die laagste prys in die eerste helfte te bereken,

402
00:30:16,740 --> 00:30:20,360
die hoogste prys in die regte helfte, en hulle verskil.

403
00:30:20,360 --> 00:30:25,390
Die gevolglike drie winste, hierdie drie getalle, neem jy die maksimum van die drie,

404
00:30:25,390 --> 00:30:32,720
en dit is die beste wins wat jy kan maak oor hierdie eerste en end dae.

405
00:30:32,720 --> 00:30:36,940
Hier is die belangrike lyne is in die rooi.

406
00:30:36,940 --> 00:30:41,160
Dit is 'n rekursiewe oproep om die antwoord te bereken in die linker helfte.

407
00:30:41,160 --> 00:30:44,760
Dit is 'n rekursiewe oproep om die antwoord te bereken in die regte helfte.

408
00:30:44,760 --> 00:30:50,720
Hierdie twee vir loops bereken die min en die maksimum op die linker-en regter helfte, onderskeidelik.

409
00:30:50,720 --> 00:30:54,970
Nou het ek bereken die wins wat oor beide helftes,

410
00:30:54,970 --> 00:31:00,530
en die finale antwoord is die maksimum van hierdie drie.

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

412
00:31:04,120 --> 00:31:06,420
>> So, seker nie, ons het 'n algoritme, maar die groter vraag is,

413
00:31:06,420 --> 00:31:08,290
wat is die kompleksiteit van hierdie?

414
00:31:08,290 --> 00:31:16,190
En die rede waarom ek genoem merge soort is dat hierdie vorm van die antwoord verdeel

415
00:31:16,190 --> 00:31:19,200
in twee en dan die samesmelting van ons oplossings weer saam

416
00:31:19,200 --> 00:31:23,580
is presies die vorm van merge soort.

417
00:31:23,580 --> 00:31:33,360
So laat my gaan deur die duur.

418
00:31:33,360 --> 00:31:41,340
As ons 'n funksie gedefinieer t (n) die aantal stappe

419
00:31:41,340 --> 00:31:50,010
vir n dae,

420
00:31:50,010 --> 00:31:54,350
ons twee rekursiewe oproepe

421
00:31:54,350 --> 00:32:00,460
word elk gaan t (n / 2) kos,

422
00:32:00,460 --> 00:32:03,540
en daar is twee van hierdie oproepe.

423
00:32:03,540 --> 00:32:10,020
Nou moet ek die minimum van die linker helfte te bereken,

424
00:32:10,020 --> 00:32:17,050
wat ek kan doen in 'n / 2 tyd, plus die maksimum van die regter helfte.

425
00:32:17,050 --> 00:32:20,820
So dit is net n.

426
00:32:20,820 --> 00:32:25,050
En toe plus 'n konstante werk.

427
00:32:25,050 --> 00:32:27,770
En hierdie herhaling vergelyking

428
00:32:27,770 --> 00:32:35,560
is presies die herhaling vergelyking vir merge soort.

429
00:32:35,560 --> 00:32:39,170
En ons almal weet dat merge soort is n log n tyd.

430
00:32:39,170 --> 00:32:46,880
Daarom word ook ons ​​algoritme n log n tyd.

431
00:32:46,880 --> 00:32:52,220
Is hierdie iterasie sin maak?

432
00:32:52,220 --> 00:32:55,780
Net 'n kort herhaling van hierdie:

433
00:32:55,780 --> 00:32:59,170
T (n) is die aantal stappe om die maksimum wins te bereken

434
00:32:59,170 --> 00:33:02,750
oor die loop van n dae.

435
00:33:02,750 --> 00:33:06,010
Die manier waarop ons ons rekursiewe oproepe verdeel

436
00:33:06,010 --> 00:33:11,980
is deur die roeping van ons oplossing op die eerste n / 2 dae,

437
00:33:11,980 --> 00:33:14,490
so dit is 'n oproep,

438
00:33:14,490 --> 00:33:16,940
en dan noem ons weer op die tweede helfte.

439
00:33:16,940 --> 00:33:20,440
So dit is twee oproepe.

440
00:33:20,440 --> 00:33:25,310
En dan vind ons 'n minimum op die linker helfte, wat ons kan doen in lineêre tyd,

441
00:33:25,310 --> 00:33:29,010
die maksimum van die regter helfte, wat ons kan doen in lineêre tyd.

442
00:33:29,010 --> 00:33:31,570
So n / 2 + n / 2 is net n.

443
00:33:31,570 --> 00:33:36,020
Dan het ons 'n konstante werk, wat is soos die doen van rekenkunde.

444
00:33:36,020 --> 00:33:39,860
Hierdie herhaling vergelyking is presies die herhaling vergelyking vir merge soort.

445
00:33:39,860 --> 00:33:55,490
Dus, ons shuffle algoritme is ook 'n teken n.

446
00:33:55,490 --> 00:33:58,520
So hoeveel ruimte gebruik ons?

447
00:33:58,520 --> 00:34:04,910
Kom ons gaan terug na die kode.

448
00:34:04,910 --> 00:34:09,420
>> 'N beter vraag is, hoeveel stapel rame wat ons ooit op enige gegewe oomblik?

449
00:34:09,420 --> 00:34:11,449
Aangesien ons met behulp van rekursie,

450
00:34:11,449 --> 00:34:23,530
die aantal van stapel rame bepaal ons ruimte gebruik.

451
00:34:23,530 --> 00:34:29,440
Kom ons kyk na n = 8.

452
00:34:29,440 --> 00:34:36,889
Ons doen 'n beroep shuffle op 8,

453
00:34:36,889 --> 00:34:41,580
wat shuffle sal 'n beroep op die eerste vier inskrywings,

454
00:34:41,580 --> 00:34:46,250
wat 'n shuffle op die eerste twee inskrywings sal roep.

455
00:34:46,250 --> 00:34:51,550
So ons stapel is - dit is ons stapel.

456
00:34:51,550 --> 00:34:54,980
En dan noem ons shuffle weer op 1,

457
00:34:54,980 --> 00:34:58,070
en dit is wat ons basis geval is, sodat ons onmiddellik terugkeer.

458
00:34:58,070 --> 00:35:04,700
Het ons ooit meer as dit baie stapel rame?

459
00:35:04,700 --> 00:35:08,880
No. Want elke keer wanneer ons 'n aanroeping,

460
00:35:08,880 --> 00:35:10,770
'n rekursiewe aanroeping te skuif,

461
00:35:10,770 --> 00:35:13,950
deel ons ons grootte in die helfte.

462
00:35:13,950 --> 00:35:17,020
So het die maksimum aantal van stapel rame ons ooit sal hê op enige gegewe oomblik

463
00:35:17,020 --> 00:35:28,460
is op die einde van die log n stapel rame.

464
00:35:28,460 --> 00:35:42,460
Elke stapel raam het konstant ruimte,

465
00:35:42,460 --> 00:35:44,410
en daarom is die totale bedrag van die ruimte,

466
00:35:44,410 --> 00:35:49,240
die maksimum bedrag van die ruimte wat ons ooit gebruik is O (log n) ruimte

467
00:35:49,240 --> 00:36:03,040
waar n die aantal dae.

468
00:36:03,040 --> 00:36:07,230
>> Nou, altyd vra jouself, "Kan ons beter doen?"

469
00:36:07,230 --> 00:36:12,390
En in die besonder, kan ons verminder dit na 'n probleem wat ons het reeds opgelos?

470
00:36:12,390 --> 00:36:20,040
'N wenk: ons net twee ander probleme bespreek voor dit, en dit is nie van plan om shuffle.

471
00:36:20,040 --> 00:36:26,200
Ons kan hierdie aandelemark probleem omskep in die maksimum subarray probleem.

472
00:36:26,200 --> 00:36:40,100
Hoe kan ons dit doen?

473
00:36:40,100 --> 00:36:42,570
Een van julle? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
So die maksimum subarray probleem,

477
00:36:59,940 --> 00:37:10,610
ons is op soek vir 'n bedrag oor 'n deurlopende subarray.

478
00:37:10,610 --> 00:37:16,230
En Emmy se voorstel vir die voorraad probleem,

479
00:37:16,230 --> 00:37:30,720
Oorweeg die veranderinge, of die deltas.

480
00:37:30,720 --> 00:37:37,440
En 'n foto van hierdie is - dit is die prys van 'n voorraad,

481
00:37:37,440 --> 00:37:42,610
maar as ons het die verskil tussen elke opeenvolgende dag -

482
00:37:42,610 --> 00:37:45,200
So sien ons dat die maksimum prys maksimum wins kan maak

483
00:37:45,200 --> 00:37:50,070
is as ons hier koop en verkoop hier.

484
00:37:50,070 --> 00:37:54,240
Maar laat ons kyk na die voortdurende laat ons kyk by die subarray probleem.

485
00:37:54,240 --> 00:38:02,510
So hier is, kan ons gaan van hier tot hier,

486
00:38:02,510 --> 00:38:08,410
ons het 'n positiewe verandering, en dan gaan van hier tot hier het ons 'n negatiewe verandering.

487
00:38:08,410 --> 00:38:14,220
Maar dan gaan van hier tot hier het ons 'n groot positiewe verandering.

488
00:38:14,220 --> 00:38:20,930
En dit is die veranderinge wat ons wil op te som ons finale wins te kry.

489
00:38:20,930 --> 00:38:25,160
Dan het ons meer negatiewe veranderinge hier.

490
00:38:25,160 --> 00:38:29,990
Die sleutel tot die vermindering van ons voorraad probleem in ons maksimale subarray probleem

491
00:38:29,990 --> 00:38:36,630
is die deltas tussen dae te oorweeg.

492
00:38:36,630 --> 00:38:40,630
So skep ons 'n nuwe skikking met die naam deltas,

493
00:38:40,630 --> 00:38:43,000
inisialiseer die eerste toegang tot 0,

494
00:38:43,000 --> 00:38:46,380
en dan vir elke delta (i), wat die verskil wees

495
00:38:46,380 --> 00:38:52,830
van my insette array (i), en skikking (i - 1).

496
00:38:52,830 --> 00:38:55,530
Dan noem ons ons roetine prosedure vir 'n maksimale subarray

497
00:38:55,530 --> 00:39:01,500
wat in 'n delta se verskeidenheid.

498
00:39:01,500 --> 00:39:06,440
En omdat maksimale subarray is lineêr tyd,

499
00:39:06,440 --> 00:39:09,370
en hierdie vermindering, die proses van die skep van hierdie delta skikking,

500
00:39:09,370 --> 00:39:11,780
is ook 'n lineêre tyd,

501
00:39:11,780 --> 00:39:19,060
dan die finale oplossing vir die lêers is O (n) werk plus O (n) werk, is nog steeds O (n) werk.

502
00:39:19,060 --> 00:39:23,900
So ons het 'n lineêre tyd oplossing vir ons probleem.

503
00:39:23,900 --> 00:39:29,610
Verstaan ​​almal hierdie transformasie?

504
00:39:29,610 --> 00:39:32,140
>> In die algemeen, 'n goeie idee dat jy altyd moet

505
00:39:32,140 --> 00:39:34,290
is probeer om 'n nuwe probleem wat jy sien te verminder.

506
00:39:34,290 --> 00:39:37,700
As dit lyk bekend aan 'n ou probleem,

507
00:39:37,700 --> 00:39:39,590
probeer die vermindering van dit aan 'n ou probleem.

508
00:39:39,590 --> 00:39:41,950
En as jy kan gebruik maak van al die gereedskap wat jy gebruik het op die ou probleem

509
00:39:41,950 --> 00:39:46,450
die nuwe probleem op te los.

510
00:39:46,450 --> 00:39:49,010
So te draai, tegniese onderhoude uitdagend.

511
00:39:49,010 --> 00:39:52,280
Hierdie probleme is waarskynlik 'n paar van die meer moeilike probleme

512
00:39:52,280 --> 00:39:54,700
wat jy kan sien in 'n onderhoud,

513
00:39:54,700 --> 00:39:57,690
so as jy nie al die probleme wat ek net gedek verstaan, dis oukei.

514
00:39:57,690 --> 00:40:01,080
Dit is 'n paar van die meer uitdagende probleme.

515
00:40:01,080 --> 00:40:03,050
Oefen, oefen, oefen.

516
00:40:03,050 --> 00:40:08,170
Ek het 'n baie van die probleme in die opdragstuk, so beslis gaan diegene wat nie.

517
00:40:08,170 --> 00:40:11,690
En baie geluk op jou onderhoude. Al my hulpbronne gepos word by hierdie skakel,

518
00:40:11,690 --> 00:40:15,220
en een van my senior vriende het aangebied om spot tegniese onderhoude te doen,

519
00:40:15,220 --> 00:40:22,050
so as jy belangstel, e-pos sal Yao op daardie e-pos adres.

520
00:40:22,050 --> 00:40:26,070
As jy het 'n paar vrae, kan jy my vra.

521
00:40:26,070 --> 00:40:28,780
Moenie julle het spesifieke vrae wat verband hou met tegniese onderhoude

522
00:40:28,780 --> 00:40:38,440
of enige probleme wat ons tot dusver gesien het?

523
00:40:38,440 --> 00:40:49,910
Okay. Wel, baie geluk op jou onderhoude.

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