1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Tæknilegar Viðtöl]

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

3
00:00:04,630 --> 00:00:08,910
[Þetta er CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hæ allir, ég er Kenny. Ég er nú yngri læra tölvunarfræði.

5
00:00:12,420 --> 00:00:17,310
Ég er fyrrverandi CS TF, og ég vildi að ég hefði þetta þegar ég var underclassman,

6
00:00:17,310 --> 00:00:19,380
og það er hvers vegna ég er að gefa þetta námskeið.

7
00:00:19,380 --> 00:00:21,370
Svo ég vona að þú njótir þess.

8
00:00:21,370 --> 00:00:23,470
Þetta námskeið er um tæknilega viðtölum,

9
00:00:23,470 --> 00:00:26,650
og allar auðlindir mínar er hægt að finna á þessum tengli,

10
00:00:26,650 --> 00:00:32,350
á þennan tengil hérna, a par af auðlindum.

11
00:00:32,350 --> 00:00:36,550
Þannig að ég gerði lista yfir vandamál, reyndar alveg nokkur vandamál.

12
00:00:36,550 --> 00:00:40,800
Einnig almenn auðlindir síðu þar sem við getum fundið ábendingar

13
00:00:40,800 --> 00:00:42,870
um hvernig á að undirbúa sig fyrir viðtalið,

14
00:00:42,870 --> 00:00:46,470
ábendingar um hvað þú átt að gera á meðan á raunverulegum viðtali,

15
00:00:46,470 --> 00:00:51,910
og hvernig á að nálgast vandamál og úrræði til hliðsjónar í framtíðinni.

16
00:00:51,910 --> 00:00:53,980
Það er allt á netinu.

17
00:00:53,980 --> 00:00:58,290
Og bara til að formála þetta námskeið, sem skilmála

18
00:00:58,290 --> 00:01:00,690
eins og það ætti ekki - viðtal undirbúning þinn

19
00:01:00,690 --> 00:01:02,800
ætti ekki að takmarkast við þennan lista.

20
00:01:02,800 --> 00:01:04,750
Þetta er einungis ætlað að vera handbók,

21
00:01:04,750 --> 00:01:08,890
og þú ættir örugglega að taka allt sem ég segi með korn af salti,

22
00:01:08,890 --> 00:01:14,620
en einnig nota allt sem ég nota til að hjálpa þér í undirbúningi viðtalið.

23
00:01:14,620 --> 00:01:16,400
>> Ég ætla að hraða í gegnum næstu skyggnur

24
00:01:16,400 --> 00:01:18,650
svo við getum fengið að raunverulegum dæmum.

25
00:01:18,650 --> 00:01:23,630
Uppbygging á viðtali fyrir verkfræði hugbúnaður postion,

26
00:01:23,630 --> 00:01:26,320
yfirleitt er það 30 til 45 mínútur,

27
00:01:26,320 --> 00:01:29,810
margar umferðir, eftir því hvaða fyrirtæki.

28
00:01:29,810 --> 00:01:33,090
Oft þú munt vera kóðun á hvítum borð.

29
00:01:33,090 --> 00:01:35,960
Svo hvítt borð eins og þetta, en oft á minni skala.

30
00:01:35,960 --> 00:01:38,540
Ef þú ert með síma viðtal, munt þú sennilega vera með

31
00:01:38,540 --> 00:01:44,030
annaðhvort collabedit eða Google Doc svo þeir geti séð þú býrð erfðaskrá

32
00:01:44,030 --> 00:01:46,500
meðan þú ert í viðtali í gegnum síma.

33
00:01:46,500 --> 00:01:48,490
An Viðtalið sjálft er oftast 2 eða 3 vandamál

34
00:01:48,490 --> 00:01:50,620
próf tölvunarfræði þekkingu þína.

35
00:01:50,620 --> 00:01:54,490
Og það verður nánast örugglega taka erfðaskrá.

36
00:01:54,490 --> 00:01:59,540
Þær tegundir af spurningum sem þú munt sjá eru yfirleitt gögn uppbygging og reiknirit.

37
00:01:59,540 --> 00:02:02,210
Og í að gera þessar tegundir af vandamál,

38
00:02:02,210 --> 00:02:07,830
Þeir munu spyrja þig, eins og, það er tími og rúm flókið, stórt O?

39
00:02:07,830 --> 00:02:09,800
Oft þeir spyrja líka hærri stigi spurningar,

40
00:02:09,800 --> 00:02:12,530
svo, að hanna kerfi,

41
00:02:12,530 --> 00:02:14,770
hvernig myndir þú leggja út númerið þitt?

42
00:02:14,770 --> 00:02:18,370
Hvaða tengi, hvaða flokkar, hvaða einingar ertu með í vélinni þinni,

43
00:02:18,370 --> 00:02:20,900
og hvernig þær virka saman?

44
00:02:20,900 --> 00:02:26,130
Svo gögn uppbygging og reiknirit eins og heilbrigður eins og hanna kerfi.

45
00:02:26,130 --> 00:02:29,180
>> Nokkrar almennar ábendingar áður en við kafa inn í dæmisögur okkar.

46
00:02:29,180 --> 00:02:32,300
Ég held að mikilvægasta reglan er alltaf að hugsa upphátt.

47
00:02:32,300 --> 00:02:36,980
Viðtalið á að vera tækifæri til að láta hugsun aðferð.

48
00:02:36,980 --> 00:02:39,820
Tilgangur viðtalsins er að spyrjandi að meta

49
00:02:39,820 --> 00:02:42,660
hvernig þér finnst og hvernig þú ferð í gegnum vandamál.

50
00:02:42,660 --> 00:02:45,210
Það versta sem þú getur gert er að þegja um allt viðtalið.

51
00:02:45,210 --> 00:02:50,090
Það er bara ekki gott.

52
00:02:50,090 --> 00:02:53,230
Þegar þú færð spurningu, vilt þú einnig að ganga úr skugga um að þú skiljir spurninguna.

53
00:02:53,230 --> 00:02:55,350
Svo endurtaka spurninguna til baka í eigin orðum

54
00:02:55,350 --> 00:02:58,920
og reyna að vinna ítarlegar nokkrum einföldum tilvikum próf

55
00:02:58,920 --> 00:03:01,530
til að ganga úr skugga um að þú skiljir spurninguna.

56
00:03:01,530 --> 00:03:05,510
Vinna með nokkrum tilvikum próf mun einnig gefa þér innsæi um hvernig á að leysa þetta vandamál.

57
00:03:05,510 --> 00:03:11,210
Þú gætir jafnvel uppgötva nokkrar mynstur til að hjálpa þér að leysa vandamál.

58
00:03:11,210 --> 00:03:14,500
Stór ábending þeirra er að ekki fá svekktur.

59
00:03:14,500 --> 00:03:17,060
Ekki fá svekktur.

60
00:03:17,060 --> 00:03:19,060
Viðtöl eru krefjandi, en það versta sem þú getur gert,

61
00:03:19,060 --> 00:03:23,330
auk þess að vera þögul, er að sýnilega svekktur.

62
00:03:23,330 --> 00:03:27,410
Þú vilt ekki að gefa því kynna til viðmælanda.

63
00:03:27,410 --> 00:03:33,960
Einn hlutur sem þú - svo margir, þegar þeir fara í viðtal,

64
00:03:33,960 --> 00:03:37,150
þeir reyna að reyna að finna bestu lausn fyrst,

65
00:03:37,150 --> 00:03:39,950
þegar í raun, það er yfirleitt glaringly augljós lausn.

66
00:03:39,950 --> 00:03:43,500
Það gæti verið hægt, gæti verið óhagkvæm, en þú ættir bara að koma fram það,

67
00:03:43,500 --> 00:03:46,210
bara svo þú hafa a upphafsstaður þar sem að vinna betur.

68
00:03:46,210 --> 00:03:48,270
Einnig að benda á lausn er hægur, með tilliti til

69
00:03:48,270 --> 00:03:52,160
stór O tími flókið eða rúm flókið,

70
00:03:52,160 --> 00:03:54,450
mun sýna að spyrjandi að þú skiljir

71
00:03:54,450 --> 00:03:57,510
þessi mál þegar þú skrifar kóðann.

72
00:03:57,510 --> 00:04:01,440
Svo ekki vera hræddur við að koma upp með einföldustu reiknirit fyrst

73
00:04:01,440 --> 00:04:04,950
og þá vinna betur þaðan.

74
00:04:04,950 --> 00:04:09,810
Einhverjar spurningar svo langt? Allt í lagi.

75
00:04:09,810 --> 00:04:11,650
>> Svo við skulum kafa í fyrsta vandamál okkar.

76
00:04:11,650 --> 00:04:14,790
"Í ljósi fylki með n heiltalna, skrifa fall sem stokkar array

77
00:04:14,790 --> 00:04:20,209
í stað þannig að allir permutations í N heiltölur eru jafn líklegt. "

78
00:04:20,209 --> 00:04:23,470
Og ráð fyrir að þú ert í boði handahófi heiltala rafall

79
00:04:23,470 --> 00:04:30,980
sem býr heiltölu á bilinu frá 0 til i, hálf svið.

80
00:04:30,980 --> 00:04:32,970
Þurfa allir að skilja þessa spurningu?

81
00:04:32,970 --> 00:04:39,660
Ég gef þér fjölda n heiltalna, og ég vil að þú að stokka það.

82
00:04:39,660 --> 00:04:46,050
Í skrá minn, skrifaði ég nokkur forrit til að sýna hvað ég meina.

83
00:04:46,050 --> 00:04:48,910
Ég ætla að uppstokkun fylki af 20 þáttum,

84
00:04:48,910 --> 00:04:52,490
úr -10 í +9,

85
00:04:52,490 --> 00:04:57,050
og ég vil að þú að framleiðsla á lista eins og þetta.

86
00:04:57,050 --> 00:05:02,890
Svo er þetta raðað inntak array minn, og ég vil að þú að stokka það.

87
00:05:02,890 --> 00:05:07,070
Við munum gera það aftur.

88
00:05:07,070 --> 00:05:13,780
Þurfa allir að skilja spurninguna? Allt í lagi.

89
00:05:13,780 --> 00:05:16,730
Svo það er komið að þér.

90
00:05:16,730 --> 00:05:21,220
Hvað eru nokkrar hugmyndir? Getur þú gert það eins og n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Opinn fyrir öllu.

92
00:05:34,400 --> 00:05:37,730
Allt í lagi. Svo ein hugmynd, leiðbeinandi við Emmy,

93
00:05:37,730 --> 00:05:45,300
er fyrst reikna með handahófi númer, handahófi heiltala í bilinu 0-20.

94
00:05:45,300 --> 00:05:49,840
Svo ráð array okkar hefur lengd 20.

95
00:05:49,840 --> 00:05:54,800
Í myndinni okkar 20 þáttum,

96
00:05:54,800 --> 00:05:58,560
þetta er inntak array okkar.

97
00:05:58,560 --> 00:06:04,590
Og nú, tillaga hennar er að búa til nýjan array,

98
00:06:04,590 --> 00:06:08,440
þannig að þetta verður framleiðsla array.

99
00:06:08,440 --> 00:06:12,880
Og byggt á ég aftur eftir Rand -

100
00:06:12,880 --> 00:06:17,580
þannig að ef ég væri, segjum, 17,

101
00:06:17,580 --> 00:06:25,640
afrita 17. þáttur í fyrstu stöðu.

102
00:06:25,640 --> 00:06:30,300
Nú þurfum við að eyða - við þurfum að skipta á alla þætti hér

103
00:06:30,300 --> 00:06:36,920
yfir svo að við höfum bilið aftast og engin göt í miðju.

104
00:06:36,920 --> 00:06:39,860
Og nú erum við að endurtaka ferlið.

105
00:06:39,860 --> 00:06:46,360
Nú erum við að velja nýtt handahófi tala á milli 0 og 19.

106
00:06:46,360 --> 00:06:52,510
Við höfum nýtt ég hér, og við afrita þessa hluti í þessari stöðu.

107
00:06:52,510 --> 00:07:00,960
Þá erum við að skipta hlutum lokið og endurtaka ferlið þar til við höfum fulla new Array okkar.

108
00:07:00,960 --> 00:07:05,890
Hver er að keyra þegar þetta reiknirit?

109
00:07:05,890 --> 00:07:08,110
Jæja, við skulum íhuga áhrif þetta.

110
00:07:08,110 --> 00:07:10,380
Við erum að breytast í hvert frumefni.

111
00:07:10,380 --> 00:07:16,800
Þegar við fjarlægja þetta ég, við erum að breytast alla þætti eftir það til vinstri.

112
00:07:16,800 --> 00:07:21,600
Og það er O (n) kostnaður

113
00:07:21,600 --> 00:07:26,100
því hvað ef við fjarlægja fyrsta frumefni?

114
00:07:26,100 --> 00:07:29,670
Svo fyrir hvern flutningur, fjarlægja við -

115
00:07:29,670 --> 00:07:32,170
hver flutningur incurs O (n) til starfa,

116
00:07:32,170 --> 00:07:41,520
og þar sem við höfum n brottflutnings, þetta leiðir til O (n ^ 2) uppstokkun.

117
00:07:41,520 --> 00:07:49,550
Allt í lagi. Svo góð byrjun. Góð byrjun.

118
00:07:49,550 --> 00:07:55,290
>> Önnur tillaga er að nota eitthvað sem kallast Knuth rimmu,

119
00:07:55,290 --> 00:07:57,540
eða Fisher-Yates uppstokkun.

120
00:07:57,540 --> 00:07:59,630
Og það er í raun línuleg tími uppstokkun.

121
00:07:59,630 --> 00:08:02,200
Og hugmyndin er mjög svipuð.

122
00:08:02,200 --> 00:08:05,160
Aftur höfum við inntak array okkar,

123
00:08:05,160 --> 00:08:08,580
en í stað þess að nota tvö fylki fyrir hjálpina okkar / úttak,

124
00:08:08,580 --> 00:08:13,590
notum við fyrsta hluta fylkisins til að halda utan um stokkuð hluta okkar,

125
00:08:13,590 --> 00:08:18,400
og við höldum utan, og þá erum við að láta restina af array okkar fyrir unshuffled hluta.

126
00:08:18,400 --> 00:08:24,330
Svo hér er það sem ég meina. Við byrjum burt með - við veljum að ég,

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

128
00:08:30,910 --> 00:08:36,150
Núverandi músina okkar er að benda á fyrstu vísitölunni.

129
00:08:36,150 --> 00:08:39,590
Við valið nokkrar i hér

130
00:08:39,590 --> 00:08:42,740
og nú erum við að skipta.

131
00:08:42,740 --> 00:08:47,690
Þannig að ef þetta var 5 og þetta var 4,

132
00:08:47,690 --> 00:08:57,150
leiðir array verður 5 hér og 4 hér.

133
00:08:57,150 --> 00:09:00,390
Og nú erum við í huga að merki hér.

134
00:09:00,390 --> 00:09:05,770
Allt til vinstri er stokkuð,

135
00:09:05,770 --> 00:09:15,160
og allt til hægri er unshuffled.

136
00:09:15,160 --> 00:09:17,260
Og nú getum við að endurtaka ferlið.

137
00:09:17,260 --> 00:09:25,210
Við valið af handahófi vísitölu milli 1 og 20 núna.

138
00:09:25,210 --> 00:09:30,650
Svo ætla nýtt okkar ég er hér.

139
00:09:30,650 --> 00:09:39,370
Nú erum við að skipta þessu i við núverandi nýja stöðu okkar hér.

140
00:09:39,370 --> 00:09:44,790
Þannig að við að skipta fram og til baka eins og þetta.

141
00:09:44,790 --> 00:09:51,630
Leyfðu mér að koma upp kóða til að gera það steypu meira.

142
00:09:51,630 --> 00:09:55,290
Við byrjum með vali okkar á i -

143
00:09:55,290 --> 00:09:58,370
við að byrja með ég jafngilda 0, velja við handahófi staðsetningu J

144
00:09:58,370 --> 00:10:02,420
í unshuffled hluta fylkisins, til i n-1.

145
00:10:02,420 --> 00:10:07,280
Svo ef ég er hér, valið af handahófi vísitölu milli hér og annars staðar í fylkinu,

146
00:10:07,280 --> 00:10:12,410
og við skipta.

147
00:10:12,410 --> 00:10:17,550
Þetta er allur kóðinn þarf að stokka Array þínu.

148
00:10:17,550 --> 00:10:21,670
Einhverjar spurningar?

149
00:10:21,670 --> 00:10:25,530
>> Jæja, einn þarf spurningin er, hvers vegna er þetta rétt?

150
00:10:25,530 --> 00:10:28,360
Hvers vegna er hvert permutation jafn líklegt?

151
00:10:28,360 --> 00:10:30,410
Og ég mun ekki fara í gegnum sönnun af þessu,

152
00:10:30,410 --> 00:10:35,970
en mörg vandamál í tölvunarfræði getur verið sannað með innleiðingu.

153
00:10:35,970 --> 00:10:38,520
Hversu margir af þú ert kunnuglegur með að framkalla?

154
00:10:38,520 --> 00:10:40,590
Allt í lagi. Cool.

155
00:10:40,590 --> 00:10:43,610
Svo er hægt að sanna réttmæti þessa reiknirit með einföldu örvun,

156
00:10:43,610 --> 00:10:49,540
þar framkalla tilgáta þín væri gert ráð fyrir að

157
00:10:49,540 --> 00:10:53,290
uppstokkun minn skilar hvert permutation jafn líklegt

158
00:10:53,290 --> 00:10:56,120
upp fyrstu þætti i.

159
00:10:56,120 --> 00:10:58,300
Nú tel ég + 1.

160
00:10:58,300 --> 00:11:02,550
Og eftir því hvernig við veljum vísitölu J okkar að skipta,

161
00:11:02,550 --> 00:11:05,230
þetta leiðir til - og þá vinna út upplýsingar,

162
00:11:05,230 --> 00:11:07,390
að minnsta kosti full sönnun á því hvers vegna þetta reiknirit skilar

163
00:11:07,390 --> 00:11:12,800
hvert permutation með jafn líklegt líkum.

164
00:11:12,800 --> 00:11:15,940
>> Allt í lagi, næsta vandamál.

165
00:11:15,940 --> 00:11:19,170
Svo "gefið fjölda heiltalna, postive, núll, neikvæð,

166
00:11:19,170 --> 00:11:21,290
Skrifið fall sem reiknar hámarks fjárhæð

167
00:11:21,290 --> 00:11:24,720
hvaða continueous subarray inntak fylkisins. "

168
00:11:24,720 --> 00:11:28,370
Dæmi hér um er að ræða þar sem allir tölur eru jákvæðar,

169
00:11:28,370 --> 00:11:31,320
þá nú er besti kosturinn til að taka allt array.

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

171
00:11:34,690 --> 00:11:36,780
Þegar þú hefur nokkrar filmur þar,

172
00:11:36,780 --> 00:11:38,690
í þessu tilfelli sem við viljum bara fyrstu tveimur

173
00:11:38,690 --> 00:11:44,590
því að velja -1 og / eða -3 mun koma summan okkar niður.

174
00:11:44,590 --> 00:11:48,120
Stundum við gætum þurft að byrja í miðju fylkisins.

175
00:11:48,120 --> 00:11:53,500
Stundum viljum við að velja ekki neitt, það er best að ekki taka neitt.

176
00:11:53,500 --> 00:11:56,490
Og stundum er það betra að taka haust

177
00:11:56,490 --> 00:12:07,510
því málið eftir að það er frábær stór. Svo einhverjar hugmyndir?

178
00:12:07,510 --> 00:12:10,970
(Nemandi, óskiljanlegur) >> Já.

179
00:12:10,970 --> 00:12:13,560
Segjum að ég á ekki að taka -1.

180
00:12:13,560 --> 00:12:16,170
Þá annaðhvort ég velja 1.000 og 20.000,

181
00:12:16,170 --> 00:12:18,630
eða ég valið bara 3 milljarðar.

182
00:12:18,630 --> 00:12:20,760
Jæja, besti kosturinn er að taka allar tölur.

183
00:12:20,760 --> 00:12:24,350
Þetta -1, þrátt fyrir að vera neikvæð,

184
00:12:24,350 --> 00:12:31,340
allt sum er betra en þar sem ég ekki að taka -1.

185
00:12:31,340 --> 00:12:36,460
Svo ein af þeim ábendingum sem ég nefndi áðan var að koma fram skýrt augljóst

186
00:12:36,460 --> 00:12:40,540
og skepna afl lausn fyrst.

187
00:12:40,540 --> 00:12:44,340
Hvað er skepna afl lausn á þessu vandamáli? Já?

188
00:12:44,340 --> 00:12:46,890
[Jane] Jæja, ég held að skepna afl lausn

189
00:12:46,890 --> 00:12:52,600
væri að bæta upp allar mögulegar samsetningar (óskiljanlegur).

190
00:12:52,600 --> 00:12:58,250
[Yu] lagi. Svo er hugmynd Jane að taka allar mögulegar -

191
00:12:58,250 --> 00:13:01,470
Ég er paraphrasing - er að taka öll möguleg samfelld subarray,

192
00:13:01,470 --> 00:13:07,840
reikna fjárhæð hennar, og síðan taka allt af öllum mögulegum samfellt subarrays.

193
00:13:07,840 --> 00:13:13,310
Hvað skilgreinir einstaklega a subarray í array inntak mínu?

194
00:13:13,310 --> 00:13:17,380
Eins, hvað tvennt þarf ég? Já?

195
00:13:17,380 --> 00:13:19,970
(Nemandi, óskiljanlegur) >> Right.

196
00:13:19,970 --> 00:13:22,130
A lægri bundinn við vísitölu og efri vísitölu

197
00:13:22,130 --> 00:13:28,300
einstaklega ákvarðar samfellt subarray.

198
00:13:28,300 --> 00:13:31,400
[Kvenkyns nemandi] Erum við að meta það fylki einstaka tölur?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nei Svo spurningunni sinni er, erum við ráð array okkar -

200
00:13:34,280 --> 00:13:39,000
er array okkar öll einstök númer, og svarið er nei.

201
00:13:39,000 --> 00:13:43,390
>> Ef við notum skepna afl lausn okkar, þá byrja / enda vísitölur

202
00:13:43,390 --> 00:13:47,200
einstaklega ákvarðar samfellt subarray okkar.

203
00:13:47,200 --> 00:13:51,680
Svo ef við iterate fyrir allar mögulegar færslur byrjun,

204
00:13:51,680 --> 00:13:58,320
og fyrir alla enda færslur> eða = að byrja, og <n,

205
00:13:58,320 --> 00:14:05,570
þú reikna summu, og þá erum við að taka hámarks upphæð sem við höfum séð hingað til.

206
00:14:05,570 --> 00:14:07,880
Er þetta ljóst?

207
00:14:07,880 --> 00:14:12,230
Hvað er stór O í þessari lausn?

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

209
00:14:16,660 --> 00:14:18,860
Ekki alveg n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Athugið að við iterate frá 0 til n,

211
00:14:25,250 --> 00:14:27,520
svo er það eitt til hliðar.

212
00:14:27,520 --> 00:14:35,120
Við iterate aftur frá nánast upphafi til enda, annar fyrir lykkju.

213
00:14:35,120 --> 00:14:37,640
Og nú, í það, verðum við að summa upp alla færslu,

214
00:14:37,640 --> 00:14:43,810
svo er það annar fyrir lykkju. Þannig að við höfum þrjá orpið fyrir lykkjur, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Allt í lagi. Þetta fer sem útgangspunkt.

216
00:14:46,560 --> 00:14:53,180
Lausnin okkar er ekki verri en n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Er allir skilja skepna afl lausn?

218
00:14:55,480 --> 00:14:59,950
>> Allt í lagi. A betri lausn er að nota hugmynd sem kallast dynamic forritun.

219
00:14:59,950 --> 00:15:03,040
Ef þú tekur CS124, sem er Reiknirit og gögn uppbygging,

220
00:15:03,040 --> 00:15:05,680
þú verður mjög kunnuglegur með þessari tækni.

221
00:15:05,680 --> 00:15:12,190
Og hugmyndin er, að reyna að byggja upp lausnir til smærri vandamál fyrst.

222
00:15:12,190 --> 00:15:17,990
Það sem ég meina með þessu er, höfum við nú að hafa áhyggjur af tvennu: byrja og enda.

223
00:15:17,990 --> 00:15:29,340
Og það er pirrandi. Hvað ef við gætum losna við einn af þeim þáttum?

224
00:15:29,340 --> 00:15:32,650
Ein hugmynd er að - we're gefið upprunalega vandamál okkar,

225
00:15:32,650 --> 00:15:37,470
finna hámarks summa subarray í bilinu [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Og nú höfum við nýja subproblem, þar sem við þekkjum, í núverandi vísitölu okkar i,

227
00:15:47,400 --> 00:15:52,520
við vitum að við verðum gera þar. Subarray okkar verður að enda á núverandi vísitölu.

228
00:15:52,520 --> 00:15:57,640
Svo eftir stendur vandamálið er, hvar ættum við að byrja subarray okkar?

229
00:15:57,640 --> 00:16:05,160
Er þetta skynsamleg? Allt í lagi.

230
00:16:05,160 --> 00:16:12,030
Þannig að ég hef túlkað þetta upp, og við skulum líta á hvað þetta þýðir.

231
00:16:12,030 --> 00:16:16,230
Í codirectory, það er forrit sem heitir subarray,

232
00:16:16,230 --> 00:16:19,470
og það tekur fjölda af hlutum,

233
00:16:19,470 --> 00:16:25,550
og það skilar hámarks subarray summan í stokkuð listanum mínum.

234
00:16:25,550 --> 00:16:29,920
Svo í þessu tilfelli, hámarks subarray okkar er 3.

235
00:16:29,920 --> 00:16:34,850
Og það er tekið bara með því að nota 2 og 1.

236
00:16:34,850 --> 00:16:38,050
Við skulum hlaupa aftur. Það er einnig 3.

237
00:16:38,050 --> 00:16:40,950
En í þetta skiptið, athugaðu hvernig fengum við 3.

238
00:16:40,950 --> 00:16:46,690
Við tók - við að taka bara 3 sig

239
00:16:46,690 --> 00:16:49,980
því það er umkringdur filmur á báðum hliðum,

240
00:16:49,980 --> 00:16:55,080
sem vilja koma fjárhæð <3.

241
00:16:55,080 --> 00:16:57,820
Við skulum hlaupa á 10 atriðum.

242
00:16:57,820 --> 00:17:03,200
This tími það er 7, taka við leiðandi 3 og 4.

243
00:17:03,200 --> 00:17:09,450
This tími það er 8, og við að fá að með því að taka 1, 4 og 3.

244
00:17:09,450 --> 00:17:16,310
Svo til að gefa þér innsæi á því hvernig við getum leyst þetta umbreytt vandamál,

245
00:17:16,310 --> 00:17:18,890
láta 'taka a líta á þetta subarray.

246
00:17:18,890 --> 00:17:23,460
Við erum gefið þetta inntak array, og við vitum að svarið er 8.

247
00:17:23,460 --> 00:17:26,359
Við tökum 1, 4 og 3.

248
00:17:26,359 --> 00:17:29,090
En við skulum líta á hvernig við fengum reyndar að svar.

249
00:17:29,090 --> 00:17:34,160
Við skulum líta á hámarks subarray sem lauk á hverjum þessara vísitalna.

250
00:17:34,160 --> 00:17:40,780
Hvað er hámarks subarray sem þarf að enda í efstu stöðu?

251
00:17:40,780 --> 00:17:46,310
[Nemandi] Zero. >> Zero. Bara ekki taka -5.

252
00:17:46,310 --> 00:17:50,210
Hér það er að fara að vera 0 eins og heilbrigður. Já?

253
00:17:50,210 --> 00:17:56,470
(Nemandi, óskiljanlegur)

254
00:17:56,470 --> 00:17:58,960
[Yu] Ó, fyrirgefðu, það er -3.

255
00:17:58,960 --> 00:18:03,220
Þannig að þetta er 2, þetta er -3.

256
00:18:03,220 --> 00:18:08,690
Allt í lagi. Svo -4, hvað er hámarks subarray til enda þá stöðu

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

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

259
00:18:22,570 --> 00:18:28,060
Nú verð ég að enda á þeim stað þar sem -2 er á.

260
00:18:28,060 --> 00:18:39,330
Svo 6, 5, 7, og það síðasta er 4.

261
00:18:39,330 --> 00:18:43,480
Vitandi að þetta eru færslurnar mínar

262
00:18:43,480 --> 00:18:48,130
fyrir breyttu vandamál þar sem ég þarf að ljúka við hvern þessara vísitalna,

263
00:18:48,130 --> 00:18:51,410
þá er síðasta svar mitt bara, taka sópa yfir,

264
00:18:51,410 --> 00:18:53,580
og taka hámarksfjölda.

265
00:18:53,580 --> 00:18:55,620
Þannig að í þessu tilviki það er 8.

266
00:18:55,620 --> 00:19:00,010
Þetta felur í sér að hámarks subarray endar á þessari vísitölu,

267
00:19:00,010 --> 00:19:04,970
og byrjaði einhvers staðar fyrir það.

268
00:19:04,970 --> 00:19:09,630
Þurfa allir að skilja þetta umbreytt subarray?

269
00:19:09,630 --> 00:19:22,160
>> Allt í lagi. Jæja, við skulum reikna út endurkomu fyrir þetta.

270
00:19:22,160 --> 00:19:27,990
Við skulum íhuga bara fyrstu færslur.

271
00:19:27,990 --> 00:19:35,930
Svo hér það var 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Og þá var -2 hér, og leiddi hana niður í 6.

273
00:19:39,790 --> 00:19:50,800
Svo ef ég kalla færslu í stöðu i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
hvernig get ég notað svar við fyrri subproblem

275
00:19:54,910 --> 00:19:59,360
að svara þessari subproblem?

276
00:19:59,360 --> 00:20:04,550
Ef ég horfi á, við skulum segja, þessi færsla.

277
00:20:04,550 --> 00:20:09,190
Hvernig get ég reikna svarið 6 því að horfa á

278
00:20:09,190 --> 00:20:18,780
sambland af þessu fylki og svör við fyrri subproblems í þessu fylki? Já?

279
00:20:18,780 --> 00:20:22,800
[Kvenkyns nemandi] Þú tekur fjölda fjárhæðir

280
00:20:22,800 --> 00:20:25,430
í þeirri stöðu rétt fyrir það, þannig að 8,

281
00:20:25,430 --> 00:20:32,170
og þá bæta núverandi subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Svo tillaga hennar er að líta á þessar tvær tölur,

283
00:20:36,460 --> 00:20:40,090
þetta númer og þessi tala.

284
00:20:40,090 --> 00:20:50,130
Þannig vísar það 8 að svara fyrir subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Og við skulum kalla inntak array A. minn

286
00:20:57,300 --> 00:21:01,470
Til þess að finna hámarks subarray sem endar á stöðu i,

287
00:21:01,470 --> 00:21:03,980
Ég hef tvo kosti: Ég get annað hvort haldið áfram subarray

288
00:21:03,980 --> 00:21:09,790
sem endaði á milli vísitölu, eða hefja nýja fylki.

289
00:21:09,790 --> 00:21:14,190
Ef ég væri að halda áfram subarray sem hófst á fyrri vísitölu,

290
00:21:14,190 --> 00:21:19,260
þá er hámarks summan ég get náð svarið við fyrri subproblem

291
00:21:19,260 --> 00:21:24,120
auk núverandi array færslu.

292
00:21:24,120 --> 00:21:27,550
En, ég hef líka val um að byrja nýja subarray,

293
00:21:27,550 --> 00:21:30,830
í því tilviki summan er 0.

294
00:21:30,830 --> 00:21:42,860
Svo er svarið max 0, subproblem i - 1, auk núverandi array færslu.

295
00:21:42,860 --> 00:21:46,150
Er þetta endurtekning skynsamleg?

296
00:21:46,150 --> 00:21:50,840
Endurkoma okkar, eins og við uppgötva, er subproblem i

297
00:21:50,840 --> 00:21:54,740
er jöfn hámarki fyrri subproblem auk núverandi array færslu mína,

298
00:21:54,740 --> 00:22:01,490
sem þýðir að halda áfram fyrri subarray,

299
00:22:01,490 --> 00:22:07,250
eða 0, hefja nýtt subarray á núverandi vísitölu minn.

300
00:22:07,250 --> 00:22:10,060
Og þegar við höfum byggt upp þessa töflu af lausnum, svo endanlega svar okkar,

301
00:22:10,060 --> 00:22:13,950
bara gera línulega sópa yfir subproblem array

302
00:22:13,950 --> 00:22:19,890
og taka hámarksfjölda.

303
00:22:19,890 --> 00:22:23,330
Þetta er nákvæmlega framkvæmd af því sem ég sagði rétt.

304
00:22:23,330 --> 00:22:27,320
Þannig að við að búa til nýja subproblem fylki, subproblems.

305
00:22:27,320 --> 00:22:32,330
Fyrsta færsla er annaðhvort 0 eða fyrstu færslu, hámark þeirra tveggja.

306
00:22:32,330 --> 00:22:35,670
Og fyrir the hvíla af the subproblems

307
00:22:35,670 --> 00:22:39,810
við notum endurkomu við uppgötva.

308
00:22:39,810 --> 00:22:49,960
Nú erum við að reikna hámark subproblems array okkar, og það er endanlegt svar okkar.

309
00:22:49,960 --> 00:22:54,130
>> Svo hversu mikið pláss við erum að nota í reiknirit?

310
00:22:54,130 --> 00:23:01,470
Ef þú hefur aðeins tekið CS50, þá þú might ekki hafa rætt pláss mjög mikið.

311
00:23:01,470 --> 00:23:07,750
Jæja, einn hlutur að hafa í huga er að ég kallaði malloc hér með n stærð.

312
00:23:07,750 --> 00:23:13,590
Hvað er að benda á þig?

313
00:23:13,590 --> 00:23:17,450
Þetta reiknirit notar línuleg rúm.

314
00:23:17,450 --> 00:23:21,030
Getum við gert betur?

315
00:23:21,030 --> 00:23:30,780
Er eitthvað sem þú tekur eftir því er óþarfi að reikna endanlega svar?

316
00:23:30,780 --> 00:23:33,290
Ég held að betri spurning er, hvaða upplýsingar

317
00:23:33,290 --> 00:23:40,680
þurfum við ekki að bera alla leið í gegnum til enda?

318
00:23:40,680 --> 00:23:44,280
Nú, ef við lítum á þessar tvær línur,

319
00:23:44,280 --> 00:23:47,720
við umönnun aðeins um fyrri subproblem,

320
00:23:47,720 --> 00:23:50,910
og við umönnun aðeins um allt sem við höfum nokkurn tíma séð svo langt.

321
00:23:50,910 --> 00:23:53,610
Til að reikna endanlega svar okkar, þurfum við ekki allt array.

322
00:23:53,610 --> 00:23:57,450
Við þurfum aðeins síðasta númer, síðustu tveir tölustafir.

323
00:23:57,450 --> 00:24:02,630
Síðasta tala fyrir subproblem array, og síðasta númer fyrir hámark.

324
00:24:02,630 --> 00:24:07,380
Svo, í raun getum við mjúklega þessar lykkjur saman

325
00:24:07,380 --> 00:24:10,460
og fara úr línulegum rúm til stöðugum pláss.

326
00:24:10,460 --> 00:24:15,830
Núverandi summan svo langt, hér kemur, hlutverk subproblem, subproblem array okkar.

327
00:24:15,830 --> 00:24:20,020
Svo núverandi summan, svo langt, er svarið við fyrri subproblem.

328
00:24:20,020 --> 00:24:23,450
Og þessi summa, svo langt, tekur sæti max okkar.

329
00:24:23,450 --> 00:24:28,100
Við reikna allt sem við förum eftir.

330
00:24:28,100 --> 00:24:30,890
Og svo við förum úr línulegum rúm til föstu rými,

331
00:24:30,890 --> 00:24:36,650
og við höfum einnig línulega lausn subarray vandamál okkar.

332
00:24:36,650 --> 00:24:40,740
>> Þessar tegundir af spurningum sem þú munt fá í viðtali.

333
00:24:40,740 --> 00:24:44,450
Hvað er tími flókið, það er pláss flókið?

334
00:24:44,450 --> 00:24:50,600
Getur þú gert betur? Eru hlutir sem eru óþarfi að halda í kring?

335
00:24:50,600 --> 00:24:55,270
Ég gerði þetta til að varpa ljósi greiningar sem þú ættir að taka á eigin spýtur

336
00:24:55,270 --> 00:24:57,400
eins og þú ert að vinna í þessum vandamálum.

337
00:24:57,400 --> 00:25:01,710
Alltaf að spyrja sjálfan þig: "Get ég gert betur?"

338
00:25:01,710 --> 00:25:07,800
Í raun getum við gert betur en þetta?

339
00:25:07,800 --> 00:25:10,730
Konar bragð spurningu. Þú getur ekki, vegna þess að þú þarft að

340
00:25:10,730 --> 00:25:13,590
að minnsta kosti lesa inntak á vandanum.

341
00:25:13,590 --> 00:25:15,570
Þannig að sú staðreynd að þú þarft að minnsta kosti að lesa inntak á vandamáli

342
00:25:15,570 --> 00:25:19,580
þýðir að þú getur ekki gert betur en línulega tíma,

343
00:25:19,580 --> 00:25:22,870
og þú getur ekki gert betur en föstu rými.

344
00:25:22,870 --> 00:25:27,060
Svo er þetta í raun besta lausnin á þessu vandamáli.

345
00:25:27,060 --> 00:25:33,040
Spurningar? Allt í lagi.

346
00:25:33,040 --> 00:25:35,190
>> Verðbréfamarkaðurinn vandamál:

347
00:25:35,190 --> 00:25:38,350
"Í ljósi fylki af n heiltalna, jákvæð, núll eða neikvæð,

348
00:25:38,350 --> 00:25:41,680
að tákna verð á hlutabréfum á n daga,

349
00:25:41,680 --> 00:25:44,080
Skrifið fall til að reikna hámark gróði sem þú getur gert

350
00:25:44,080 --> 00:25:49,350
í ljósi þess að þú kaupa og selja nákvæmlega 1 birgðir innan þessa n daga. "

351
00:25:49,350 --> 00:25:51,690
Í meginatriðum, við viljum að kaupa lágt, selja hátt.

352
00:25:51,690 --> 00:25:58,580
Og við viljum að reikna út bestu hagnaði við getum gert.

353
00:25:58,580 --> 00:26:11,500
Fara aftur á enda minn, hvað er strax ljóst, einfaldasta svarið, en það er hægt?

354
00:26:11,500 --> 00:26:17,690
Já? (Nemandi, óskiljanlegur) >> Já.

355
00:26:17,690 --> 00:26:21,470
>> Svo þú myndir bara fara þó og líta á hlutabréfaverð

356
00:26:21,470 --> 00:26:30,550
á hverjum tíma, (óskiljanlegur).

357
00:26:30,550 --> 00:26:33,990
[Yu] Jæja, svo lausn hennar - tillaga hennar um tölvumál

358
00:26:33,990 --> 00:26:37,380
lægsta og reikna hæsta ekki endilega að vinna

359
00:26:37,380 --> 00:26:42,470
því hæsta gæti orðið áður en lægsta.

360
00:26:42,470 --> 00:26:47,340
Svo er það skepna afl lausn á þessu vandamáli?

361
00:26:47,340 --> 00:26:53,150
Hvað eru tveir hlutir sem ég þarf að einstaklega ákvarða hagnað sem ég gera? Hægri.

362
00:26:53,150 --> 00:26:59,410
Skepna afl lausn er - ó, svo tillaga George er við þurfum bara tvo daga

363
00:26:59,410 --> 00:27:02,880
að einstaklega ákvarða hagnað þessara tveggja daga.

364
00:27:02,880 --> 00:27:06,660
Þannig að við reikna hvert par, eins og að kaupa / selja,

365
00:27:06,660 --> 00:27:12,850
reikna hagnað, sem gæti verið neikvætt eða jákvætt eða núll.

366
00:27:12,850 --> 00:27:18,000
Reiknið hámarks hagnað að við tökum eftir iterating yfir öll pör daga.

367
00:27:18,000 --> 00:27:20,330
Það verður endanlega svar okkar.

368
00:27:20,330 --> 00:27:25,730
Og þessi lausn verður að vera O (n ^ 2), vegna þess að það er n valið tvö pör -

369
00:27:25,730 --> 00:27:30,270
daga sem þú getur valið á milli daga enda.

370
00:27:30,270 --> 00:27:32,580
Allt í lagi, þannig að ég ætla ekki að fara yfir skepna afl lausn hér.

371
00:27:32,580 --> 00:27:37,420
Ég ætla að segja ykkur að það er N log n lausn.

372
00:27:37,420 --> 00:27:45,550
Hvaða reiknirit veistu nú það er n log n?

373
00:27:45,550 --> 00:27:50,730
Það er ekki bragð spurning.

374
00:27:50,730 --> 00:27:54,790
>> Mergesort. Mergesort er n log n,

375
00:27:54,790 --> 00:27:57,760
og í raun ein leið til að leysa þetta vandamál er að nota

376
00:27:57,760 --> 00:28:04,400
a Mergesort konar hugmynd heitir, almennt skipta og sigra.

377
00:28:04,400 --> 00:28:07,570
Og hugmyndin er sem hér segir.

378
00:28:07,570 --> 00:28:12,400
Þú vilt að reikna bestu kaup / selja par á vinstri helming.

379
00:28:12,400 --> 00:28:16,480
Finndu bestu gróði sem þú getur gert, bara með fyrstu n í tvo daga.

380
00:28:16,480 --> 00:28:19,780
Síðan sem þú vilt að oompute bestu kaup / selja par á hægri hluta,

381
00:28:19,780 --> 00:28:23,930
svo síðasta N yfir í tvo daga.

382
00:28:23,930 --> 00:28:32,400
Og nú er spurningin, hvernig sameina við þessar lausnir saman aftur?

383
00:28:32,400 --> 00:28:36,320
Já? (Nemandi, óskiljanlegur)

384
00:28:36,320 --> 00:28:49,890
>> Lagi. Svo láta mig teikna mynd.

385
00:28:49,890 --> 00:29:03,870
Já? (George, óskiljanlegur)

386
00:29:03,870 --> 00:29:06,450
>> Einmitt. Lausn George er nákvæmlega rétt.

387
00:29:06,450 --> 00:29:10,040
Svo tillaga hans er fyrst reikna Kaupa / selja par,

388
00:29:10,040 --> 00:29:16,050
og sem á sér stað í vinstri hluta, þannig að við skulum kalla það vinstri, vinstri.

389
00:29:16,050 --> 00:29:20,790
Kaupa / selja par sem á sér stað í hægri hluta.

390
00:29:20,790 --> 00:29:25,180
En ef við saman bara þessar tvær tölur, við erum að missa málið

391
00:29:25,180 --> 00:29:30,460
þar sem við kaupum hér og selja einhvers staðar á hægri hluta.

392
00:29:30,460 --> 00:29:33,810
Við kaupum í vinstri hluta, selja í rétta hluta.

393
00:29:33,810 --> 00:29:38,490
Og besta leiðin til að reikna Kaupa / selja par sem spannar bæði helminga

394
00:29:38,490 --> 00:29:43,480
er að reikna amk hér og reikna hámarki hér

395
00:29:43,480 --> 00:29:45,580
og taka mismuninn þeirra.

396
00:29:45,580 --> 00:29:50,850
Svo tveimur tilvikum þar sem kaupa / selja par berst aðeins hér,

397
00:29:50,850 --> 00:30:01,910
aðeins hér, eða á báðum helminga er skilgreint af þessum þremur tölum.

398
00:30:01,910 --> 00:30:06,450
Svo reiknirit okkar að sameina lausnir okkar aftur saman,

399
00:30:06,450 --> 00:30:08,350
við viljum reikna Kaupa / selja par

400
00:30:08,350 --> 00:30:13,120
þar sem við kaupum á vinstri hluta og selja á réttum helming.

401
00:30:13,120 --> 00:30:16,740
Og besta leiðin til að gera það er að reikna lægsta verð á fyrri helmingi ársins,

402
00:30:16,740 --> 00:30:20,360
hæsta verð í hægri hluta, og taka máli þeirra.

403
00:30:20,360 --> 00:30:25,390
Sú þrjár hagnaður þessar þrjár tölur, taka þér mest þriggja,

404
00:30:25,390 --> 00:30:32,720
og það er besta hagnað sem þú getur gert á þessum fyrstu og endir daga.

405
00:30:32,720 --> 00:30:36,940
Hér mikilvæg línur eru í rauðu.

406
00:30:36,940 --> 00:30:41,160
Þetta er endurkvæma hringja til að reikna svarið í vinstri helming.

407
00:30:41,160 --> 00:30:44,760
Þetta er endurkvæma hringja til að reikna svarið á hægri hluta.

408
00:30:44,760 --> 00:30:50,720
Þessir tveir fyrir lykkjur reikna min og max á vinstri og hægri hluta, hver um sig.

409
00:30:50,720 --> 00:30:54,970
Nú er ég að reikna hagnað sem spannar bæði helminga,

410
00:30:54,970 --> 00:31:00,530
og endanleg svar er hámark þessara þriggja.

411
00:31:00,530 --> 00:31:04,120
Allt í lagi.

412
00:31:04,120 --> 00:31:06,420
>> Svo viss, verðum við reiknirit, en stærri spurning er,

413
00:31:06,420 --> 00:31:08,290
það er tími flókið þetta?

414
00:31:08,290 --> 00:31:16,190
Og ástæðan fyrir því að ég nefndi Mergesort er að þetta form skipta svarið

415
00:31:16,190 --> 00:31:19,200
í tvo og þá sameina lausnir okkar aftur saman

416
00:31:19,200 --> 00:31:23,580
er einmitt mynd af Mergesort.

417
00:31:23,580 --> 00:31:33,360
Svo láta mig fara í gegnum tíma.

418
00:31:33,360 --> 00:31:41,340
Ef við skilgreint fall t (n) að vera tala af skrefum

419
00:31:41,340 --> 00:31:50,010
fyrir n dögum,

420
00:31:50,010 --> 00:31:54,350
tvær okkar endurkvæma símtöl

421
00:31:54,350 --> 00:32:00,460
eru hver að fara að kosta t (n / 2),

422
00:32:00,460 --> 00:32:03,540
og það er tveir af þessum símtölum.

423
00:32:03,540 --> 00:32:10,020
Nú þarf ég að reikna amk vinstri hluta,

424
00:32:10,020 --> 00:32:17,050
sem ég get gert í N / 2 tíma, auk hámarks á hægri hluta.

425
00:32:17,050 --> 00:32:20,820
Þannig að þetta er bara n.

426
00:32:20,820 --> 00:32:25,050
Og svo plús sumir föstu starfi.

427
00:32:25,050 --> 00:32:27,770
Og þetta endurtekning jöfnu

428
00:32:27,770 --> 00:32:35,560
er einmitt endurkomu Jafna fyrir Mergesort.

429
00:32:35,560 --> 00:32:39,170
Og við vitum öll að Mergesort er n log n tíma.

430
00:32:39,170 --> 00:32:46,880
Því er reiknirit okkar líka n log n tíma.

431
00:32:46,880 --> 00:32:52,220
Er þetta endurtekning skynsamleg?

432
00:32:52,220 --> 00:32:55,780
Bara stutt ágrip af þessu:

433
00:32:55,780 --> 00:32:59,170
T (n) er fjöldi af skrefum til að reikna hámarks hagnað

434
00:32:59,170 --> 00:33:02,750
á meðan á n daga.

435
00:33:02,750 --> 00:33:06,010
Leiðin sem við skipt upp endurkvæma símtöl okkar

436
00:33:06,010 --> 00:33:11,980
er með því að kalla lausn okkar á fyrstu n / 2 daga,

437
00:33:11,980 --> 00:33:14,490
svo er það eitt símtal,

438
00:33:14,490 --> 00:33:16,940
og svo við köllum aftur á seinni hluta ársins.

439
00:33:16,940 --> 00:33:20,440
Svo er það tvö símtöl.

440
00:33:20,440 --> 00:33:25,310
Og þá erum við að finna að minnsta kosti á vinstri hluta, sem við getum gert í línulegum tíma,

441
00:33:25,310 --> 00:33:29,010
finna hámarki hægri hluta, sem við getum gert í línulegum tíma.

442
00:33:29,010 --> 00:33:31,570
Svo N / 2 + N / 2 er bara n.

443
00:33:31,570 --> 00:33:36,020
Þá höfum við nokkur stöðuga vinnu, sem er eins og að gera tölur.

444
00:33:36,020 --> 00:33:39,860
Endurkoma jafna er einmitt endurkomu Jafna fyrir Mergesort.

445
00:33:39,860 --> 00:33:55,490
Þess vegna, uppstokkun reiknirit okkar er einnig N log n.

446
00:33:55,490 --> 00:33:58,520
Svo hversu mikið pláss erum við að nota?

447
00:33:58,520 --> 00:34:04,910
Við skulum fara aftur til kóðann.

448
00:34:04,910 --> 00:34:09,420
>> A betri spurning er, hversu margir stafla ramma sem við höfum alltaf á hverri stundu?

449
00:34:09,420 --> 00:34:11,449
Þar sem við erum með endurkvæmni,

450
00:34:11,449 --> 00:34:23,530
fjölda ramma stafla ákvarðar rúm notkun okkar.

451
00:34:23,530 --> 00:34:29,440
Við skulum íhuga n = 8.

452
00:34:29,440 --> 00:34:36,889
Við köllum uppstokkun á 8,

453
00:34:36,889 --> 00:34:41,580
sem mun kalla uppstokkun á fyrstu fjórum færslum,

454
00:34:41,580 --> 00:34:46,250
sem mun kalla uppstokkun á fyrstu tveimur færslum.

455
00:34:46,250 --> 00:34:51,550
Svo stafla okkar - þetta er stafla okkar.

456
00:34:51,550 --> 00:34:54,980
Og þá erum við kalla uppstokkun aftur á 1,

457
00:34:54,980 --> 00:34:58,070
og það er það sem byggja mál okkar er, svo við aftur strax.

458
00:34:58,070 --> 00:35:04,700
Eigum við alltaf meira en þetta margir rammar stafla?

459
00:35:04,700 --> 00:35:08,880
Nei vegna þess að hvert skipti sem við gerum er ákall,

460
00:35:08,880 --> 00:35:10,770
a endurkvæma ákall á uppstokkun,

461
00:35:10,770 --> 00:35:13,950
við deilum stærð okkar í tvennt.

462
00:35:13,950 --> 00:35:17,020
Svo hámarksfjöldi ramma stafla við höfum alltaf á hverri stundu

463
00:35:17,020 --> 00:35:28,460
er á stærðargráðunni log n stafla ramma.

464
00:35:28,460 --> 00:35:42,460
Hver stafla ramma hefur stöðug pláss,

465
00:35:42,460 --> 00:35:44,410
og því alls pláss,

466
00:35:44,410 --> 00:35:49,240
hámarks pláss sem við notum alltaf er O (log n) rúm

467
00:35:49,240 --> 00:36:03,040
þar sem n er fjöldi daga.

468
00:36:03,040 --> 00:36:07,230
>> Nú, alltaf að spyrja sjálfan þig, "Getum við gert betur?"

469
00:36:07,230 --> 00:36:12,390
Og sérstaklega, getum við draga úr þessu á vandamáli sem við höfum þegar leyst?

470
00:36:12,390 --> 00:36:20,040
A Ábending: við ræddum aðeins tvö önnur vandamál fyrir þetta, og það er ekki að fara að vera uppstokkun.

471
00:36:20,040 --> 00:36:26,200
Við getum breytt þessum markaði lager vandamál í hámarks subarray vandamál.

472
00:36:26,200 --> 00:36:40,100
Hvernig getum við gert þetta?

473
00:36:40,100 --> 00:36:42,570
Einn af þér? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Þannig hámarks subarray vandamál,

477
00:36:59,940 --> 00:37:10,610
við erum að leita að summa yfir samfellt subarray.

478
00:37:10,610 --> 00:37:16,230
Og tillaga Emmy fyrir stokk vandamál,

479
00:37:16,230 --> 00:37:30,720
íhuga breytingar eða deltas.

480
00:37:30,720 --> 00:37:37,440
Og mynd af þessu er - þetta er verð á hlutabréfum,

481
00:37:37,440 --> 00:37:42,610
en ef við tókum muninn hverjum röð degi -

482
00:37:42,610 --> 00:37:45,200
svo sjáum við að hámarks verð, hámarks hagnað við gætum gert

483
00:37:45,200 --> 00:37:50,070
er ef við kaupum hér og selja hér.

484
00:37:50,070 --> 00:37:54,240
En við skulum líta á stöðugt - við skulum líta á subarray vandamál.

485
00:37:54,240 --> 00:38:02,510
Svo hér, getum við gert - að fara áfram til hér,

486
00:38:02,510 --> 00:38:08,410
við höfum jákvæð breyting, og þá fara áfram til hér við höfum neikvæð breyting.

487
00:38:08,410 --> 00:38:14,220
En þá að fara áfram í hér við erum með mikla jákvæða breytingu.

488
00:38:14,220 --> 00:38:20,930
Og þetta eru breytingar sem við viljum að summa upp til að fá endanlega hagnað okkar.

489
00:38:20,930 --> 00:38:25,160
Þá höfum við fleiri neikvæðar breytingar hér.

490
00:38:25,160 --> 00:38:29,990
Lykillinn að því að draga birgðir vandamál okkar í hámarks subarray vandamál okkar

491
00:38:29,990 --> 00:38:36,630
er að fjalla um deltas milli daga.

492
00:38:36,630 --> 00:38:40,630
Þannig að við að búa til nýtt array heitir deltas,

493
00:38:40,630 --> 00:38:43,000
frumstilla fyrstu færslu til að vera 0,

494
00:38:43,000 --> 00:38:46,380
og þá fyrir hverja Delta (i), láta það vera munur

495
00:38:46,380 --> 00:38:52,830
um inntak array mitt (i), og array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Þá erum við að kalla venja aðferð okkar fyrir hámarks subarray

497
00:38:55,530 --> 00:39:01,500
liggur í fylkinu a Delta.

498
00:39:01,500 --> 00:39:06,440
Og af því að hámarks subarray er línuleg tími,

499
00:39:06,440 --> 00:39:09,370
og þessi lækkun, þetta ferli að búa til þetta delta fylking,

500
00:39:09,370 --> 00:39:11,780
er líka línuleg tími,

501
00:39:11,780 --> 00:39:19,060
þá er endanlega lausn fyrir hlutabréf O (n) vinna plús O (n) að vinna, er enn O (n) vinna.

502
00:39:19,060 --> 00:39:23,900
Þannig að við höfum línulega tíma lausn á vanda okkar.

503
00:39:23,900 --> 00:39:29,610
Þurfa allir að skilja þessa umbreytingu?

504
00:39:29,610 --> 00:39:32,140
>> Almennt er góð hugmynd að þú ættir alltaf að hafa

505
00:39:32,140 --> 00:39:34,290
er að reyna að draga úr nýja vandamál sem þú sérð.

506
00:39:34,290 --> 00:39:37,700
Ef það lítur þekkja gamla vandamál,

507
00:39:37,700 --> 00:39:39,590
reyna að draga úr því að gamla vandamál.

508
00:39:39,590 --> 00:39:41,950
Og ef þú getur notað öll þau tæki sem þú hefur notað á gömlu vandamáli

509
00:39:41,950 --> 00:39:46,450
að leysa nýtt vandamál.

510
00:39:46,450 --> 00:39:49,010
Svo til að vefja upp, eru tæknilega viðtöl krefjandi.

511
00:39:49,010 --> 00:39:52,280
Þessi vandamál eru sennilega sumir af the fleiri erfiðum vandamálum

512
00:39:52,280 --> 00:39:54,700
sem þú gætir séð í viðtali,

513
00:39:54,700 --> 00:39:57,690
þannig að ef þú skilur ekki öll vandamál sem ég falla bara, það er allt í lagi.

514
00:39:57,690 --> 00:40:01,080
Þessir ert sumir af the fleiri krefjandi vandamálum.

515
00:40:01,080 --> 00:40:03,050
Practice, æfa, æfa.

516
00:40:03,050 --> 00:40:08,170
Ég gaf fullt af vandamálum í útdeila svo ákveðið stöðva þá út.

517
00:40:08,170 --> 00:40:11,690
Og gangi þér vel á viðtölum þínum. Allar auðlindir mínar eru settar á þennan tengil

518
00:40:11,690 --> 00:40:15,220
og einn af eldri vinum mínum hefur boðist til að gera spotta tæknilegum viðtöl,

519
00:40:15,220 --> 00:40:22,050
þannig að ef þú hefur áhuga, email Will Yao á þetta netfang.

520
00:40:22,050 --> 00:40:26,070
Ef þið hafið einhverjar spurningar, getur þú spyrja mig.

521
00:40:26,070 --> 00:40:28,780
Ert þú krakkar hafa sérstakar spurningar sem tengjast tæknilegum viðtöl

522
00:40:28,780 --> 00:40:38,440
eða einhver vandamál sem við höfum séð hingað til?

523
00:40:38,440 --> 00:40:49,910
Allt í lagi. Jæja, gangi þér vel á viðtölum þínum.

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