1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminario: Teknika Intervjuoj]

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

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

4
00:00:08,910 --> 00:00:12,420
Saluton ĉiuj, Mi estas Kenny. Mi estas aktuale junior studi komputiko.

5
00:00:12,420 --> 00:00:17,310
Mi estas eks-CS TF, kaj mi deziras, ke mi havis tiun, kiam mi estis subklasulo,

6
00:00:17,310 --> 00:00:19,380
kaj tial mi donas ĉi seminario.

7
00:00:19,380 --> 00:00:21,370
Do mi esperas ke vi ĝuos ĝin.

8
00:00:21,370 --> 00:00:23,470
Tiu seminario temas pri teknika intervjuoj,

9
00:00:23,470 --> 00:00:26,650
kaj ĉiuj miaj rimedoj troveblas ĉe ĉi tiu ligilo,

10
00:00:26,650 --> 00:00:32,350
ĉi ligilon ĉi tie, paro de rimedoj.

11
00:00:32,350 --> 00:00:36,550
Tiam mi faris liston de problemoj, fakte, sufiĉe da problemoj.

12
00:00:36,550 --> 00:00:40,800
Ankaŭ ĝenerala rimedoj paĝo kie ni povas trovi konsiloj

13
00:00:40,800 --> 00:00:42,870
pri kiel pretigi por intervjuo,

14
00:00:42,870 --> 00:00:46,470
konsiloj de kion vi devas fari dum reala intervjuo,

15
00:00:46,470 --> 00:00:51,910
tiel kiel kiel alproksimigi problemoj kaj rimedoj por estonta referenco.

16
00:00:51,910 --> 00:00:53,980
Estas ĉio ensalutintaj.

17
00:00:53,980 --> 00:00:58,290
Kaj ĝuste al antaŭparolo ĉi seminario, oni disclaimer,

18
00:00:58,290 --> 00:01:00,690
kiel tiu ne devus - via intervjuo preparado

19
00:01:00,690 --> 00:01:02,800
ne devus esti limigita al tiu listo.

20
00:01:02,800 --> 00:01:04,750
Tiu estas nur signifis esti gvidas,

21
00:01:04,750 --> 00:01:08,890
kaj vi devas definitive preni ĉion, kion mi diras per greno de salo,

22
00:01:08,890 --> 00:01:14,620
sed ankaŭ uzi ĉio Iam mi helpos vin en via intervjuo preparado.

23
00:01:14,620 --> 00:01:16,400
>> Mi iros por akceli tra la venontaj diapozitivoj

24
00:01:16,400 --> 00:01:18,650
tiel ni povos atingi al la reala kazo studoj.

25
00:01:18,650 --> 00:01:23,630
La strukturo de intervjuo dum programado postion,

26
00:01:23,630 --> 00:01:26,320
tipe ĝi estas 30 ĝis 45 minutoj,

27
00:01:26,320 --> 00:01:29,810
multnombraj ĉirkaŭvojoj, depende de la kompanio.

28
00:01:29,810 --> 00:01:33,090
Ofte vi estos kodigo sur blanka tabulo.

29
00:01:33,090 --> 00:01:35,960
Do blankan tabulon kiel ĉi tiu, sed ofte sur pli malgranda skalo.

30
00:01:35,960 --> 00:01:38,540
Se vi havas telefonon intervjuo, vi verŝajne uzas

31
00:01:38,540 --> 00:01:44,030
ĉu collabedit aŭ Google Doc do ili povas vidi vin vivi kodigo

32
00:01:44,030 --> 00:01:46,500
dum vi esti intervjuita pri la telefono.

33
00:01:46,500 --> 00:01:48,490
Intervjuo mem estas tipe 2 aŭ 3 problemoj

34
00:01:48,490 --> 00:01:50,620
provante vian komputiko scio.

35
00:01:50,620 --> 00:01:54,490
Kaj estos preskaŭ certe engaĝi kodigo.

36
00:01:54,490 --> 00:01:59,540
La tipoj de demandoj kiujn vi vidos kutime datumstrukturoj kaj algoritmoj.

37
00:01:59,540 --> 00:02:02,210
Kaj por fari tiajn problemojn,

38
00:02:02,210 --> 00:02:07,830
ili demandos vin, kiel, kio estas la tempo kaj spaca komplekseco, granda O?

39
00:02:07,830 --> 00:02:09,800
Ili ofte ankaŭ peti pli alta-nivelo demandoj,

40
00:02:09,800 --> 00:02:12,530
tiel, desegnante sistemo,

41
00:02:12,530 --> 00:02:14,770
kiel vi jalonan via kodo?

42
00:02:14,770 --> 00:02:18,370
Kio interfacoj, kion klasoj, kio moduloj vi havas en via sistemo,

43
00:02:18,370 --> 00:02:20,900
kaj kion tiuj interagi kune?

44
00:02:20,900 --> 00:02:26,130
Do datumstrukturoj kaj algoritmoj tiel kiel desegni sistemoj.

45
00:02:26,130 --> 00:02:29,180
>> Iuj ĝeneralaj konsiloj antaŭ ol ni plonĝi en nia kazo studoj.

46
00:02:29,180 --> 00:02:32,300
Mi kredas ke la plej grava regulo estas ĉiam pensas laŭte.

47
00:02:32,300 --> 00:02:36,980
La intervjuo estas supozata esti via ŝanco por montri vian penson procezo.

48
00:02:36,980 --> 00:02:39,820
La punkto de la intervjuo estas por la intervjuanto por taksi

49
00:02:39,820 --> 00:02:42,660
kiel vi opinias kaj kiel vi iros tra problemo.

50
00:02:42,660 --> 00:02:45,210
La plej malbona afero vi povas fari estas silenti tra la tuta intervjuo.

51
00:02:45,210 --> 00:02:50,090
Tio estas nur nenio bona.

52
00:02:50,090 --> 00:02:53,230
Kiam vi donas al demando, vi ankaŭ volas certigi vin kompreni la demandon.

53
00:02:53,230 --> 00:02:55,350
Do ripeti la demandon reen en viaj propraj vortoj

54
00:02:55,350 --> 00:02:58,920
kaj provi labori funda kelkaj simpla provo kazoj

55
00:02:58,920 --> 00:03:01,530
certigi vi komprenas la demandon.

56
00:03:01,530 --> 00:03:05,510
Laborante per kelkaj provoj kazoj ankaŭ doni al vi intuicio pri kiel solvi tiun problemon.

57
00:03:05,510 --> 00:03:11,210
Vi eble eĉ malkovri kelkajn ŝablonoj por helpi vin solvi la problemon.

58
00:03:11,210 --> 00:03:14,500
Ilia granda pinto estas ne get frustrita.

59
00:03:14,500 --> 00:03:17,060
Ili ne frustrita.

60
00:03:17,060 --> 00:03:19,060
Intervjuoj estas defia, sed la plej malbona afero vi povas fari,

61
00:03:19,060 --> 00:03:23,330
krom esti silentaj, devas esti videble frustrita.

62
00:03:23,330 --> 00:03:27,410
Vi ne volas doni tiun impreson al intervjuinto.

63
00:03:27,410 --> 00:03:33,960
Unu afero, kiun vi - jes, multe da homoj, kiam ili iros en intervjuo,

64
00:03:33,960 --> 00:03:37,150
ili provas provi trovi la plej bona solvo unua,

65
00:03:37,150 --> 00:03:39,950
kiam vere, estas kutime glaringly evidenta solvo.

66
00:03:39,950 --> 00:03:43,500
Povus esti malrapida, ĝi povus esti senutilaj, sed vi devas simple indiki gxin,

67
00:03:43,500 --> 00:03:46,210
nur tiom vi havas deirpunkto de kiu funkcios pli bone.

68
00:03:46,210 --> 00:03:48,270
Ankaŭ, markante la solvo estas malrapida, en terminoj de

69
00:03:48,270 --> 00:03:52,160
granda a tempa komplekseco aŭ spaca komplekseco,

70
00:03:52,160 --> 00:03:54,450
pruvos al la intervjuanto ke vi komprenas

71
00:03:54,450 --> 00:03:57,510
tiuj temoj kiam skribante kodon.

72
00:03:57,510 --> 00:04:01,440
Do ne timu veni supren kun la plej simpla algoritmo unua

73
00:04:01,440 --> 00:04:04,950
kaj tiam funkcias pli bone de tie.

74
00:04:04,950 --> 00:04:09,810
Demandojn ĝis nun? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Do estu la plonĝi en nia unua problemo.

76
00:04:11,650 --> 00:04:14,790
"Donita aro de n entjeroj, skribi funkcio kiu ludkartaro la tabelo

77
00:04:14,790 --> 00:04:20,209
en loko tia ke ĉiuj permutoj de la n entjeroj estas egale verŝajna. "

78
00:04:20,209 --> 00:04:23,470
Kaj alpreni vi havas disponebla hazarda entjero generilo

79
00:04:23,470 --> 00:04:30,980
kiu generas entjero en rango de 0 al mi, duono gamo.

80
00:04:30,980 --> 00:04:32,970
Ĉu ĉiuj komprenas ĉi demando?

81
00:04:32,970 --> 00:04:39,660
Mi donas al vi tabelo de n entjeroj, kaj mi volas ke vi barajar ĝin.

82
00:04:39,660 --> 00:04:46,050
En mia dosierujo, mi skribis kelkajn programojn por pruvi kion mi volas diri.

83
00:04:46,050 --> 00:04:48,910
Mi tuj barajar tabelo de 20 elementoj,

84
00:04:48,910 --> 00:04:52,490
el -10 al +9,

85
00:04:52,490 --> 00:04:57,050
kaj mi volas ke vi Eligu listo ŝatas tion.

86
00:04:57,050 --> 00:05:02,890
Do ĉi tiu estas mia ordo enigo tabelo, kaj mi volas ke vi barajar ĝin.

87
00:05:02,890 --> 00:05:07,070
Ni tion faros denove.

88
00:05:07,070 --> 00:05:13,780
Ĉu ĉiuj komprenas la demandon? Okay.

89
00:05:13,780 --> 00:05:16,730
Do ĝi estas ĝis vi.

90
00:05:16,730 --> 00:05:21,220
Kio estas iuj ideoj? Ĉu vi povas fari tion kiel n ^ 2, n logo n, n?

91
00:05:21,220 --> 00:05:34,400
Malfermu al sugestoj.

92
00:05:34,400 --> 00:05:37,730
Okay. Do unu ideo, proponita de Emmy,

93
00:05:37,730 --> 00:05:45,300
estas unue komputi hazarda nombro, hazarda entjero, en rango de 0 al 20.

94
00:05:45,300 --> 00:05:49,840
Do supozi nia tabelo havas longitudon de 20.

95
00:05:49,840 --> 00:05:54,800
En la diagramo de 20 elementoj,

96
00:05:54,800 --> 00:05:58,560
tio estas nia eniro tabelo.

97
00:05:58,560 --> 00:06:04,590
Kaj nun, ŝia sugesto estas krei novan tabelo,

98
00:06:04,590 --> 00:06:08,440
tial ĉi tiu estos la eligo tabelo.

99
00:06:08,440 --> 00:06:12,880
Kaj bazita sur la i revenis por rand -

100
00:06:12,880 --> 00:06:17,580
do se i estis, diru, 17,

101
00:06:17,580 --> 00:06:25,640
kopii la 17a elemento en la unua pozicio.

102
00:06:25,640 --> 00:06:30,300
Nun ni bezonas forigi - ni bezonas ŝanĝi ĉiujn elementojn tie

103
00:06:30,300 --> 00:06:36,920
super tiel ke ni havas truon en la fino kaj neniu truoj en la mezo.

104
00:06:36,920 --> 00:06:39,860
Kaj nun ni ripetos la procezon.

105
00:06:39,860 --> 00:06:46,360
Nun oni prenas novajn hazarda entjero inter 0 kaj 19.

106
00:06:46,360 --> 00:06:52,510
Ni havas novan i tie, kaj ni kopias ĉi elemento en tiun pozicion.

107
00:06:52,510 --> 00:07:00,960
Tiam ni ŝanĝi artikoloj super kaj ni ripeti la procezon ĝis ni havos niajn plena nova tabelo.

108
00:07:00,960 --> 00:07:05,890
Kio estas la tempo de ekzekuto de ĉi tiu algoritmo?

109
00:07:05,890 --> 00:07:08,110
Nu, ni konsideru la trafo de ĉi.

110
00:07:08,110 --> 00:07:10,380
Ni sxangxigxantaj ĉiu elemento.

111
00:07:10,380 --> 00:07:16,800
Kiam ni forpreni ĉi mi, ni estas sxangxigxantaj ĉiuj elementoj post ĝi al la maldekstra.

112
00:07:16,800 --> 00:07:21,600
Kaj tio estas O (n) kosto

113
00:07:21,600 --> 00:07:26,100
ĉar kion se ni forpreni la unuan elementon?

114
00:07:26,100 --> 00:07:29,670
Do por ĉiu kopio, ni forigi -

115
00:07:29,670 --> 00:07:32,170
ĉiu forigo falas al O (n) operacio,

116
00:07:32,170 --> 00:07:41,520
kaj kiel ni n translokadoj, tio kondukas al O (n ^ 2) barajar.

117
00:07:41,520 --> 00:07:49,550
Okay. Tiel bona komenco. Bona komenco.

118
00:07:49,550 --> 00:07:55,290
>> Alia sugesto estas uzi iu konata kiel la Knuth barajar,

119
00:07:55,290 --> 00:07:57,540
aŭ la Fiŝista-Jaktoj barajar.

120
00:07:57,540 --> 00:07:59,630
Kaj estas vere lineara tempo barajar.

121
00:07:59,630 --> 00:08:02,200
Kaj la ideo estas tre simila.

122
00:08:02,200 --> 00:08:05,160
Denove, ni havas niajn enigo tabelo,

123
00:08:05,160 --> 00:08:08,580
sed anstataŭ uzi du tabeloj por nia eniro / eligo,

124
00:08:08,580 --> 00:08:13,590
ni uzas la unuan parton de la tabelo por kontroli kiu faras nia barajan parton,

125
00:08:13,590 --> 00:08:18,400
kaj ni observu spuro, kaj poste ni lasos la resto de nia tabelo por la unshuffled parton.

126
00:08:18,400 --> 00:08:24,330
Do jen kion mi volas diri. Ni dividas kun - ni elekti i,

127
00:08:24,330 --> 00:08:30,910
tabelo de 0 al 20.

128
00:08:30,910 --> 00:08:36,150
Nia nuna puntero estas indikante la unuan indicon.

129
00:08:36,150 --> 00:08:39,590
Ni elektas iu mi tie

130
00:08:39,590 --> 00:08:42,740
kaj nun ni interŝanĝi.

131
00:08:42,740 --> 00:08:47,690
Do, se ĉi tio estis 5 kaj tio estis 4,

132
00:08:47,690 --> 00:08:57,150
la rezultanta tabelo havos 5 tie kaj 4 tie.

133
00:08:57,150 --> 00:09:00,390
Kaj nun ni rimarku markilo tie.

134
00:09:00,390 --> 00:09:05,770
Ĉiu al la maldekstra estas barajadas,

135
00:09:05,770 --> 00:09:15,160
kaj ĉiu al la dekstra unshuffled.

136
00:09:15,160 --> 00:09:17,260
Kaj nun ni povas ripeti la procezon.

137
00:09:17,260 --> 00:09:25,210
Ni elektas hazarda indekso inter 1 kaj 20 nun.

138
00:09:25,210 --> 00:09:30,650
Do supozu nia nova i estas tie.

139
00:09:30,650 --> 00:09:39,370
Nun ni interŝanĝi ĉi i kun nia nuna nova pozicio tie.

140
00:09:39,370 --> 00:09:44,790
Do ni estas interŝanĝi tien kaj reen kiel ĉi tio.

141
00:09:44,790 --> 00:09:51,630
Lasu min porti la kodon por fari ĝin pli konkreta.

142
00:09:51,630 --> 00:09:55,290
Ni komencu per nia elekto de i -

143
00:09:55,290 --> 00:09:58,370
ni starti kun i egalas al 0, oni prenas hazarda loko j

144
00:09:58,370 --> 00:10:02,420
en la unshuffled parto de la tabelo, i al n-1.

145
00:10:02,420 --> 00:10:07,280
Do, se mi estas ĉi tie, elektu hazarda indekso inter ĉi tie kaj la resto de la tabelo,

146
00:10:07,280 --> 00:10:12,410
kaj ni interŝanĝi.

147
00:10:12,410 --> 00:10:17,550
Tio estas la tuta kodo necese barajar vian tabelo.

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

149
00:10:21,670 --> 00:10:25,530
>> Nu, unu bezonis demando estas, kial tiu korekta?

150
00:10:25,530 --> 00:10:28,360
Kial ĉiu permuto egale verŝajna?

151
00:10:28,360 --> 00:10:30,410
Kaj mi ne iros tra la pruvo de ĉi tio,

152
00:10:30,410 --> 00:10:35,970
sed multaj problemoj en komputiko povas esti pruvita per indukto.

153
00:10:35,970 --> 00:10:38,520
Kiel multaj el vi estas familiara kun indukto?

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

155
00:10:40,590 --> 00:10:43,610
Do vi povas pruvi la praveco de ĉi tiu algoritmo per simpla indukto,

156
00:10:43,610 --> 00:10:49,540
kie estas via indukta hipotezo estus, supozi ke

157
00:10:49,540 --> 00:10:53,290
mia barajar revenas ĉiun permuto egale verŝajna

158
00:10:53,290 --> 00:10:56,120
supren al la unua i elementoj.

159
00:10:56,120 --> 00:10:58,300
Nun, konsideru mi + 1.

160
00:10:58,300 --> 00:11:02,550
Kaj laux la vojo ni elekti nia indekso j por interŝanĝi,

161
00:11:02,550 --> 00:11:05,230
tio kondukas al - kaj tiam vi laboras ekster la detaloj,

162
00:11:05,230 --> 00:11:07,390
almenaŭ plenan pruvon pri tio, kial tiu algoritmo redonas

163
00:11:07,390 --> 00:11:12,800
ĉiu permuto kun egale verŝajna probablo.

164
00:11:12,800 --> 00:11:15,940
>> Bone, apud problemo.

165
00:11:15,940 --> 00:11:19,170
Do "donita tabelo de entjeroj, postive, nula, negativa,

166
00:11:19,170 --> 00:11:21,290
skribi funkcion kiu kalkulas la maksimuma sumo

167
00:11:21,290 --> 00:11:24,720
de iu continueous subarray de la enigo tabelo. "

168
00:11:24,720 --> 00:11:28,370
Ekzemplo jen, en la kazo kie ĉiuj nombroj estas pozitiva,

169
00:11:28,370 --> 00:11:31,320
tiam nuntempe la plej bona elekto estas preni la tuta tabelo.

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

171
00:11:34,690 --> 00:11:36,780
Kiam vi havas iujn negativaj en tie,

172
00:11:36,780 --> 00:11:38,690
en ĉi tiu kazo ni volas nur la du unuaj

173
00:11:38,690 --> 00:11:44,590
ĉar elekti -1 kaj / aŭ -3 venigos nia sumo sube.

174
00:11:44,590 --> 00:11:48,120
Foje ni eble devus komenci en la mezo de la tabelo.

175
00:11:48,120 --> 00:11:53,500
Kelkfoje ni volas elekti nenion, temas pli bone ne fari ion.

176
00:11:53,500 --> 00:11:56,490
Kaj kelkfoje estas pli bone doni la falo,

177
00:11:56,490 --> 00:12:07,510
ĉar la afero post ĝi estas super granda. Do neniu ideoj?

178
00:12:07,510 --> 00:12:10,970
(Studento, nekomprenebla) >> Jes.

179
00:12:10,970 --> 00:12:13,560
Supozu mi ne prenas -1.

180
00:12:13,560 --> 00:12:16,170
Tiam ĉu mi elektu 1.000 kaj 20.000,

181
00:12:16,170 --> 00:12:18,630
aŭ mi simple elektas la 3 miliardoj.

182
00:12:18,630 --> 00:12:20,760
Nu, la plej bona elekto estas preni ĉiujn numerojn.

183
00:12:20,760 --> 00:12:24,350
Ĉi -1, malgraŭ esti negativa,

184
00:12:24,350 --> 00:12:31,340
la tuta sumo estas pli bona ol se mi ne preni -1.

185
00:12:31,340 --> 00:12:36,460
Do unu el la pintoj mi menciis pli frue estis konstati la klare evidentaj

186
00:12:36,460 --> 00:12:40,540
kaj la malpura forto solvon unue.

187
00:12:40,540 --> 00:12:44,340
Kio estas la bruta forto solvon en ĉi tiu problemo? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Nu, mi kredas ke la malpura forto solvo

189
00:12:46,890 --> 00:12:52,600
estus adicii ĉiujn eblajn kombinojn (nekomprenebla).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Do Jane ideon estas preni ĉiun eblan -

191
00:12:58,250 --> 00:13:01,470
Mi simpligas - estas preni ĉiun eblan kontinua subarray,

192
00:13:01,470 --> 00:13:07,840
komputi lia sumo, kaj poste prenu la maksimumo de ĉiuj eblaj kontinua subarrays.

193
00:13:07,840 --> 00:13:13,310
Kio unike identigas subarray en mia enigo tabelo?

194
00:13:13,310 --> 00:13:17,380
Kiel, kio du aferojn mi bezonas? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Studento, nekomprenebla) >> Ĝuste.

196
00:13:19,970 --> 00:13:22,130
Al suba baro sur la indekso kaj supera baro indekso

197
00:13:22,130 --> 00:13:28,300
unike determinas kontinua subarray.

198
00:13:28,300 --> 00:13:31,400
[Ina studento] Ĉu ni taksanta estas tabelo de solaj nombroj?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Do ŝi demando estas, ĉu ni supozante nia tabelo -

200
00:13:34,280 --> 00:13:39,000
estas nia tabelo ĉiuj solaj nombroj, kaj la respondo estas ne.

201
00:13:39,000 --> 00:13:43,390
>> Se ni uzi nian bruta forto solvon, tiam la komenco / fino indeksoj

202
00:13:43,390 --> 00:13:47,200
unike determinas nian kontinua subarray.

203
00:13:47,200 --> 00:13:51,680
Do, se ni persisti por ĉiuj eblaj komenco enskriboj,

204
00:13:51,680 --> 00:13:58,320
por ĉiuj fino enskriboj> aŭ = komenci, kaj <n,

205
00:13:58,320 --> 00:14:05,570
vi komputi la sumon, kaj tiam ni preni la maksimuman sumon ni vidis ĝis nun.

206
00:14:05,570 --> 00:14:07,880
Ĉu ĉi tiu estas klara?

207
00:14:07,880 --> 00:14:12,230
Kio estas la granda O de tiu solvo?

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

209
00:14:16,660 --> 00:14:18,860
Ne tute n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Notu ke ni persisti de 0 al n,

211
00:14:25,250 --> 00:14:27,520
do jen unu por buklo.

212
00:14:27,520 --> 00:14:35,120
Ni persisti denove de preskaŭ la komenco ĝis la fino, alia por buklo.

213
00:14:35,120 --> 00:14:37,640
Kaj nun, ene de tiu, ni devas sumigi ĉiu eniro,

214
00:14:37,640 --> 00:14:43,810
do jen alia por buklo. Do ni havas tri anidado por bukloj, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Ĉi tio iras kiel deirpunkto.

216
00:14:46,560 --> 00:14:53,180
Nia solvo estas ne pli malbona, ol n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ĉu ĉiuj komprenas la bruta forto solvo?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Pli bona solvo estas uzi ideo nomita dinamika programado.

219
00:14:59,950 --> 00:15:03,040
Se vi prenos CS124, kiu estas Algoritmoj kaj Datumoj Strukturoj,

220
00:15:03,040 --> 00:15:05,680
vi fariĝos tre konas ĉi tiun teknikon.

221
00:15:05,680 --> 00:15:12,190
Kaj la ideo estas, provu konstrui solvojn al malgrandaj problemoj unue.

222
00:15:12,190 --> 00:15:17,990
Kion mi celas per tio estas, ni aktuale devas maltrankviligi du aferoj: komenco kaj fino.

223
00:15:17,990 --> 00:15:29,340
Kaj tio estas ĝena. Kio se ni povus forigi unu el tiuj parametroj?

224
00:15:29,340 --> 00:15:32,650
Unu ideo estas - we're donita nia originala problemo,

225
00:15:32,650 --> 00:15:37,470
trovi la maksimuma sumo de ajna subarray en rango [ho, n-1].

226
00:15:37,470 --> 00:15:47,400
Kaj nun ni havas novan subproblem, kie ni scias, en nia nuna indekso i,

227
00:15:47,400 --> 00:15:52,520
ni scias ke ni devas fini tie. Nia subarray devas finiĝi je la nuna indekso.

228
00:15:52,520 --> 00:15:57,640
Do la ceteraj problemo estas, kie ni komencos nian subarray?

229
00:15:57,640 --> 00:16:05,160
Ĉu ĉi sencon? Okay.

230
00:16:05,160 --> 00:16:12,030
Do mi kodita ĉi, kaj ni rigardu kion tio signifas.

231
00:16:12,030 --> 00:16:16,230
En la codirectory, ekzistas programo nomata subarray,

232
00:16:16,230 --> 00:16:19,470
kaj ĝi portas numeron de artikoloj,

233
00:16:19,470 --> 00:16:25,550
kaj denove la maksimuma subarray sumo en mia barajan listo.

234
00:16:25,550 --> 00:16:29,920
Do ĉi-kaze, nia maksimuma subarray estas 3.

235
00:16:29,920 --> 00:16:34,850
Kaj tio prenita de nur uzante 2 kaj 1.

236
00:16:34,850 --> 00:16:38,050
Ni kuras ĝin denove. Estas ankaŭ 3.

237
00:16:38,050 --> 00:16:40,950
Sed ĉi tiun fojon, rimarku kiom ni akiris la 3.

238
00:16:40,950 --> 00:16:46,690
Ni prenis la - ni simple prenu la 3 sin

239
00:16:46,690 --> 00:16:49,980
ĉar ĝi estas ĉirkaŭita de negativaj sur ambaŭ flankoj,

240
00:16:49,980 --> 00:16:55,080
kiu alportos sumo <3.

241
00:16:55,080 --> 00:16:57,820
Ni kuras je 10 eroj.

242
00:16:57,820 --> 00:17:03,200
Ĉi-foje ĝi estas 7, ni prenu la ĉefan 3 kaj 4.

243
00:17:03,200 --> 00:17:09,450
Ĉi-foje ĝi estas 8, kaj ni atingos ke per prenante 1, 4 kaj 3.

244
00:17:09,450 --> 00:17:16,310
Por tiel doni al vi intuicio pri kiel ni povas solvi ĉi transformita problemo,

245
00:17:16,310 --> 00:17:18,890
ni rigardu tiun subarray.

246
00:17:18,890 --> 00:17:23,460
Ni donis ĉi enigo tabelo, kaj ni konas la respondo estas 8.

247
00:17:23,460 --> 00:17:26,359
Ni prenu la 1, 4, kaj 3.

248
00:17:26,359 --> 00:17:29,090
Sed ni rigardu kiom ni efektive havas tiun respondon.

249
00:17:29,090 --> 00:17:34,160
Ni rigardu la maksimuma subarray kiu enfluis en ĉiu el tiuj indeksoj.

250
00:17:34,160 --> 00:17:40,780
Kio estas la maksimuma subarray kiu havas por enflui en la unua pozicio?

251
00:17:40,780 --> 00:17:46,310
[Studenta] Nulo. >> Nulo. Nur ne prenas la -5.

252
00:17:46,310 --> 00:17:50,210
Tie okazas al esti 0 tiel. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Studento, nekomprenebla)

254
00:17:56,470 --> 00:17:58,960
[Yu] Ho, pardonu, estas -3.

255
00:17:58,960 --> 00:18:03,220
Do tiu estas 2, ĉi tiu estas -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Do -4, kio estas la maksimuma subarray fini tiun pozicion

257
00:18:08,690 --> 00:18:12,910
kie -4 estas? Nulo.

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

259
00:18:22,570 --> 00:18:28,060
Nun, mi devas fini je la loko kie -2 estas.

260
00:18:28,060 --> 00:18:39,330
Do 6, 5, 7, kaj la lasta estas 4.

261
00:18:39,330 --> 00:18:43,480
Sciante, ke tiuj estas miaj enskriboj

262
00:18:43,480 --> 00:18:48,130
por la transformita problemo kie mi devas fini je ĉiu el tiuj indeksoj,

263
00:18:48,130 --> 00:18:51,410
tiam mia fina respondo estas justa, preni sweep trans,

264
00:18:51,410 --> 00:18:53,580
kaj prenu la maksimuma nombro.

265
00:18:53,580 --> 00:18:55,620
Do en tiu kazo ĝi estas 8.

266
00:18:55,620 --> 00:19:00,010
Ĉi tio implicas ke la maksimuma subarray finiĝas ĉe ĉi tiu indico,

267
00:19:00,010 --> 00:19:04,970
kaj komencis ie antaŭ ĝi.

268
00:19:04,970 --> 00:19:09,630
Ĉu ĉiuj komprenas ĉi transformita subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Nu, ni kalkuli la rekursieca por ĉi tio.

270
00:19:22,160 --> 00:19:27,990
Ni konsideru nur la unuaj kelkaj enskriboj.

271
00:19:27,990 --> 00:19:35,930
Do jen tio estis 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Kaj tiam estis -2 tie, kaj kiu alportis ĝin al 6.

273
00:19:39,790 --> 00:19:50,800
Do se mi nomas la eniron en la pozicio i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
kiel mi povas uzi la respondo al antaŭa subproblem

275
00:19:54,910 --> 00:19:59,360
respondi tiun subproblem?

276
00:19:59,360 --> 00:20:04,550
Se mi rigardas, diru, ĉi eniro.

277
00:20:04,550 --> 00:20:09,190
Kiel mi povas kalkuli la respondon 6 por rigardi

278
00:20:09,190 --> 00:20:18,780
kombino de tablo kaj la respondoj al la antaŭaj subproblemo en ĉi tabelo? Jes?

279
00:20:18,780 --> 00:20:22,800
[Ina studento] Vi prenu la tabelo de sumoj

280
00:20:22,800 --> 00:20:25,430
en la pozicio ĝuste antaŭ ĝi, do la 8an,

281
00:20:25,430 --> 00:20:32,170
kaj tiam vi aldonas la nunan subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Do ŝi sugesto estas por rigardi tiujn du nombroj,

283
00:20:36,460 --> 00:20:40,090
ĉi tiu numero kaj ĉi tiu numero.

284
00:20:40,090 --> 00:20:50,130
Do tiu 8 raportas al la respondo de la subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Kaj ni nomas mia enigo tabelo A.

286
00:20:57,300 --> 00:21:01,470
Por trovi maksimuma subarray kiu enfluas en pozicio i,

287
00:21:01,470 --> 00:21:03,980
Mi havas du eblojn: Mi povas aŭ daŭrigi la subarray

288
00:21:03,980 --> 00:21:09,790
kiu enfluis en la antaŭa indekso, aŭ komenci novan tabelo.

289
00:21:09,790 --> 00:21:14,190
Se mi estus por daŭrigi la subarray kiu komencis ĉe la antaŭa indico,

290
00:21:14,190 --> 00:21:19,260
tiam la maksimuma sumo mi povas atingi estas la respondo al la antaŭa subproblem

291
00:21:19,260 --> 00:21:24,120
plus la nuna tabelo eniro.

292
00:21:24,120 --> 00:21:27,550
Sed, mi ankaux havas la elekton de komenci novan subarray,

293
00:21:27,550 --> 00:21:30,830
en kiu kazo la sumo estas 0.

294
00:21:30,830 --> 00:21:42,860
Do la respondo estas max de 0, subproblem i - 1, plus la nuna tabelo eniro.

295
00:21:42,860 --> 00:21:46,150
Ĉu ĉi rekursieca sencon?

296
00:21:46,150 --> 00:21:50,840
Nia rekursieca, kiel ni ĵus malkovris, estas subproblem i

297
00:21:50,840 --> 00:21:54,740
estas egala al la maksimumo de la antaŭa subproblem plus miajn nuna tabelo eniro,

298
00:21:54,740 --> 00:22:01,490
kio signifas daŭrigi la antaŭan subarray,

299
00:22:01,490 --> 00:22:07,250
aŭ 0, komenci novan subarray en mia nuna indekso.

300
00:22:07,250 --> 00:22:10,060
Kaj unufoje ni konstruis ĉi tabelo de solvoj, tiam nia fina respondo,

301
00:22:10,060 --> 00:22:13,950
nur faru lineara balaita tra la subproblem tabelo

302
00:22:13,950 --> 00:22:19,890
kaj prenu la maksimuma nombro.

303
00:22:19,890 --> 00:22:23,330
Ĉi tiu estas ĝusta apliko de tio, kion mi ĵus diris.

304
00:22:23,330 --> 00:22:27,320
Do ni kreu novan subproblem tabelo, subproblemo.

305
00:22:27,320 --> 00:22:32,330
La unua ero estas ĉu 0 aŭ la unua eniro, la maksimumo de tiuj du.

306
00:22:32,330 --> 00:22:35,670
Kaj dum la resto de la subproblemo

307
00:22:35,670 --> 00:22:39,810
ni uzas la ĝustan rekursieca ni ĵus malkovrita.

308
00:22:39,810 --> 00:22:49,960
Nun ni kalkulas la maksimumo de nia subproblemo tabelo, kaj tio estas nia fina respondo.

309
00:22:49,960 --> 00:22:54,130
>> Do kiom spaco ni uzas en ĉi tiu algoritmo?

310
00:22:54,130 --> 00:23:01,470
Se vi nur prenis CS50, tiam vi eble ne diskutis spaco tre multe.

311
00:23:01,470 --> 00:23:07,750
Nu, unu afero noti estas, ke mi nomis malloc tie kun amplekso n.

312
00:23:07,750 --> 00:23:13,590
Kion tio sugestas al vi?

313
00:23:13,590 --> 00:23:17,450
Ĉi tiu algoritmo uzas lineara spaco.

314
00:23:17,450 --> 00:23:21,030
Ĉu ni povas fari pli bone?

315
00:23:21,030 --> 00:23:30,780
Ĉu estas io, kiun vi rimarkos ke estas nenecese komputi la fina respondo?

316
00:23:30,780 --> 00:23:33,290
Mi supozas pli bonan demando estas, kio informo

317
00:23:33,290 --> 00:23:40,680
ni ne bezonis portadi la tuta vojo tra la fino?

318
00:23:40,680 --> 00:23:44,280
Nun, se ni rigardas tiujn du linioj,

319
00:23:44,280 --> 00:23:47,720
ni nur zorgas pri la antaŭa subproblem,

320
00:23:47,720 --> 00:23:50,910
kaj ni nur zorgas pri la maksimuma ni iam vidis ĝis nun.

321
00:23:50,910 --> 00:23:53,610
Komputi nia fina respondo, ni ne bezonas la tutan aron.

322
00:23:53,610 --> 00:23:57,450
Ni nur bezonas la lasta numero, du lastaj ciferoj.

323
00:23:57,450 --> 00:24:02,630
Lasta numero por la subproblem tabelo, kaj lasta numero por la maksimumo.

324
00:24:02,630 --> 00:24:07,380
Do, fakte, ni povas kunfandi tiujn maŝojn kune

325
00:24:07,380 --> 00:24:10,460
kaj iru de lineara spaco al konstanta spaco.

326
00:24:10,460 --> 00:24:15,830
Nuna sumo ĝis nun, ĉi tie, anstataŭas la rolo de subproblem, nia subproblem tabelo.

327
00:24:15,830 --> 00:24:20,020
Do nuna sumo, ĝis nun, estas la respondo al la antaŭa subproblem.

328
00:24:20,020 --> 00:24:23,450
Kaj tiu sumo, ĝis nun, prenas la lokon de nia max.

329
00:24:23,450 --> 00:24:28,100
Ni kalkulas la maksimuma kiel ni iru kune.

330
00:24:28,100 --> 00:24:30,890
Kaj tiel ni iros de lineara spaco al konstanta spaco,

331
00:24:30,890 --> 00:24:36,650
kaj ni ankaux havas lineara solvon al niaj subarray problemo.

332
00:24:36,650 --> 00:24:40,740
>> Tiuj specoj de demandoj vi ricevos dum intervjuo.

333
00:24:40,740 --> 00:24:44,450
Kio estas la tempa komplekseco; kio estas la spaca komplekseco?

334
00:24:44,450 --> 00:24:50,600
Ĉu vi povas fari pli bone? Ĉu ekzistas aĵoj kiuj estas nenecesa teni ĉirkaŭe?

335
00:24:50,600 --> 00:24:55,270
Mi faris ĉi reliefigi analizoj kiujn vi devus preni sur via propra

336
00:24:55,270 --> 00:24:57,400
kiel vi laboras tra tiuj problemoj.

337
00:24:57,400 --> 00:25:01,710
Ĉiam petante vin, "Ĉu mi povas fari pli bone?"

338
00:25:01,710 --> 00:25:07,800
Fakte, ĉu ni povas fari pli bone ol tio?

339
00:25:07,800 --> 00:25:10,730
Ordigi de lertaĵo demando. Vi ne povas, ĉar vi bezonas

340
00:25:10,730 --> 00:25:13,590
almenaŭ legis la eniro al la problemo.

341
00:25:13,590 --> 00:25:15,570
Do la fakto, ke vi bezonas almenaŭ legis la eniro al la problemo

342
00:25:15,570 --> 00:25:19,580
signifas ke vi ne povas fari pli bone ol lineara tempo,

343
00:25:19,580 --> 00:25:22,870
kaj vi ne povas fari pli bone ol konstanta spaco.

344
00:25:22,870 --> 00:25:27,060
Do tiu estas, fakte, la plej bona solvo por tiu problemo.

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

346
00:25:33,040 --> 00:25:35,190
>> Borso problemo:

347
00:25:35,190 --> 00:25:38,350
"Donita aro de n entjeroj, pozitivaj, nulo, aŭ negativa,

348
00:25:38,350 --> 00:25:41,680
kiuj reprezentas la prezo de la sako sur n tagoj,

349
00:25:41,680 --> 00:25:44,080
skribi funkcion por kalkuli la maksimuman profiton vi povos fari

350
00:25:44,080 --> 00:25:49,350
pro tio ke vi aĉeti kaj vendi ekzakte 1 stock ene tiuj n tagoj. "

351
00:25:49,350 --> 00:25:51,690
Esence, ni volas aĉeti malalta, vendi altaj.

352
00:25:51,690 --> 00:25:58,580
Kaj ni volas eltrovi la plej bona profito oni povas fari.

353
00:25:58,580 --> 00:26:11,500
Reiros al mia bekon, kio estas la tuj klara, plej simpla respondo, sed ĝi estas malrapida?

354
00:26:11,500 --> 00:26:17,690
Jes? (Studento, nekomprenebla) >> Jes.

355
00:26:17,690 --> 00:26:21,470
>> Do vi simple iru kvankam kaj rigardi la stock prezoj

356
00:26:21,470 --> 00:26:30,550
je ĉiu punkto en tempo, (nekomprenebla).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, do ŝi solvo - ŝia sugesto de komputado

358
00:26:33,990 --> 00:26:37,380
la plej malalta kaj komputanta la plej alta ne nepre laboras

359
00:26:37,380 --> 00:26:42,470
ĉar la plej alta povus okazi antaŭ la plej malalta.

360
00:26:42,470 --> 00:26:47,340
Do kio estas la bruta forto solvo por tiu problemo?

361
00:26:47,340 --> 00:26:53,150
Kio estas la du aĵoj kiuj mi bezonas por unike difini la utilo mi faru? Ĝuste.

362
00:26:53,150 --> 00:26:59,410
La bruta forto solvo estas - ho, jes, Georgo sugesto estas ni nur bezonas du tagojn

363
00:26:59,410 --> 00:27:02,880
por unike difini la profito de tiuj du tagoj.

364
00:27:02,880 --> 00:27:06,660
Do ni komputi ĉiu paro, kiel aĉeti / vendi,

365
00:27:06,660 --> 00:27:12,850
komputi la profito, kiu povus esti negativa aŭ pozitiva aŭ nula.

366
00:27:12,850 --> 00:27:18,000
Komputi la maksimuma profito, ke ni faros post ripetanta super ĉiuj paroj de tagoj.

367
00:27:18,000 --> 00:27:20,330
Tio estos nia fina respondo.

368
00:27:20,330 --> 00:27:25,730
Kaj tiu solvo estos O (n ^ 2), ĉar tie estas n elekti du paroj -

369
00:27:25,730 --> 00:27:30,270
de tempo, kiun vi povas elekti inter fino tagoj.

370
00:27:30,270 --> 00:27:32,580
Okay, do mi ne tuj transiros malpura forto solvon ĉi tie.

371
00:27:32,580 --> 00:27:37,420
Mi tuj diros al vi ke estas n logo n solvo.

372
00:27:37,420 --> 00:27:45,550
Kio algoritmo vi aktuale scias ke estas n logo n?

373
00:27:45,550 --> 00:27:50,730
Ne estas atuto demando.

374
00:27:50,730 --> 00:27:54,790
>> Kunfandi varon. Kunfandi varo estas n logo n,

375
00:27:54,790 --> 00:27:57,760
kaj fakte, unu maniero solvi tiun problemon estas uzi

376
00:27:57,760 --> 00:28:04,400
a merge speco ia ideo nomas, en ĝenerala, dividi kaj venki.

377
00:28:04,400 --> 00:28:07,570
Kaj la ideo estas kiel sekvas.

378
00:28:07,570 --> 00:28:12,400
Vi volas komputi la plej bona buy / vendi paro en la maldekstra duono.

379
00:28:12,400 --> 00:28:16,480
Trovu la bona profito oni povas fari, nur kun la unua n super du tagoj.

380
00:28:16,480 --> 00:28:19,780
Tiam vi volas oompute la plej bona buy / vendi paron ĉe la dekstra duono,

381
00:28:19,780 --> 00:28:23,930
do la lasta n super du tagoj.

382
00:28:23,930 --> 00:28:32,400
Kaj nun la demando estas, kiel ni kunfandi tiujn solvojn reen kune?

383
00:28:32,400 --> 00:28:36,320
Jes? (Studento, nekomprenebla)

384
00:28:36,320 --> 00:28:49,890
>> Bone. Do mi desegnis bildon.

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

386
00:29:03,870 --> 00:29:06,450
>> Ekzakte. Georgo solvo estas ĝuste dekstre.

387
00:29:06,450 --> 00:29:10,040
Do lia sugesto estas, unue komputi la plej bona buy / vendas paro,

388
00:29:10,040 --> 00:29:16,050
kaj tio okazas en la maldekstra duono, do ni nomas tio maldekstra, maldekstra.

389
00:29:16,050 --> 00:29:20,790
Best aĉeti / vendi paro kiu okazas en la dekstra duono.

390
00:29:20,790 --> 00:29:25,180
Sed se ni nur kompare tiuj du nombroj, ni mankis la kazo

391
00:29:25,180 --> 00:29:30,460
kie ni aĉeti tie kaj vendi ie en la dekstra duono.

392
00:29:30,460 --> 00:29:33,810
Ni aĉetas en la maldekstra duono, vendi en la dekstra duono.

393
00:29:33,810 --> 00:29:38,490
Kaj la plej bona maniero por kalkuli la plej bona buy / vendas paro kiu ĉirkaŭprenas ambaŭ duonoj

394
00:29:38,490 --> 00:29:43,480
estas al komputi la minimuma tie kaj kalkuli la maksimuman tie

395
00:29:43,480 --> 00:29:45,580
kaj prenu lian diferencon.

396
00:29:45,580 --> 00:29:50,850
Do la du kazoj kie la buy / vendas paro okazas nur ĉi tie,

397
00:29:50,850 --> 00:30:01,910
nur ĉi tie, aŭ en ambaŭ duonoj estas difinita per ĉi tiuj tri nombroj.

398
00:30:01,910 --> 00:30:06,450
Do nia algoritmo por kunfandi nian solvaĵoj reen kune,

399
00:30:06,450 --> 00:30:08,350
ni volas kalkuli la plej bona buy / vendas paro

400
00:30:08,350 --> 00:30:13,120
kie ni aĉetas en la maldekstra duono kaj vendi en la dekstra duono.

401
00:30:13,120 --> 00:30:16,740
Kaj la plej bona maniero fari tion estas por kalkuli la plej malalta prezo en la unua duono,

402
00:30:16,740 --> 00:30:20,360
la plej alta prezo en la dekstra duono, kaj prenu lian diferencon.

403
00:30:20,360 --> 00:30:25,390
La rezultanta tri profitojn, tiuj tri numeroj, vi prenos la maksimumo de la tri,

404
00:30:25,390 --> 00:30:32,720
kaj tio estas la plej bona profito vi povas fari sur tiuj unuaj kaj fino tagoj.

405
00:30:32,720 --> 00:30:36,940
Jen la grava linioj estas en ruĝa.

406
00:30:36,940 --> 00:30:41,160
Ĉi tiu estas rekursia alvoko al komputi la respondon en la maldekstra duono.

407
00:30:41,160 --> 00:30:44,760
Ĉi tiu estas rekursia alvoko al komputi la respondon en la dekstra duono.

408
00:30:44,760 --> 00:30:50,720
Tiuj du por maŝojn komputi la min kaj la max sur la maldekstra kaj dekstra duono, respektive.

409
00:30:50,720 --> 00:30:54,970
Nun mi kalkulas la profiton, ke trairas ambaŭ duonoj,

410
00:30:54,970 --> 00:31:00,530
kaj la fina respondo estas la maksimumo de tiuj tri.

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

412
00:31:04,120 --> 00:31:06,420
>> Do, certe, ni havas algoritmon, sed la granda demando estas,

413
00:31:06,420 --> 00:31:08,290
kio estas la tempa komplekseco de tiu?

414
00:31:08,290 --> 00:31:16,190
Kaj la kialo, kial mi menciis merge varo estas ke tiu formo de dividi la respondo

415
00:31:16,190 --> 00:31:19,200
en du kaj poste kunfandi nian solvaĵoj dorso kune

416
00:31:19,200 --> 00:31:23,580
Estas precize la formo de merge varon.

417
00:31:23,580 --> 00:31:33,360
Do lasu min iri tra la daŭro.

418
00:31:33,360 --> 00:31:41,340
Se ni difini funkcion t (n) por esti la nombro de paŝoj

419
00:31:41,340 --> 00:31:50,010
por n tagoj,

420
00:31:50,010 --> 00:31:54,350
niaj du rekursiaj alvokoj

421
00:31:54,350 --> 00:32:00,460
estas ĉiu tuj kostos t (n / 2),

422
00:32:00,460 --> 00:32:03,540
kaj tie estas du el tiuj alvokoj.

423
00:32:03,540 --> 00:32:10,020
Nun mi bezonas por kalkuli la minimumo de la maldekstra duono,

424
00:32:10,020 --> 00:32:17,050
kion mi povas fari en n / 2 horo, plus la maksimumo de la dekstra duono.

425
00:32:17,050 --> 00:32:20,820
Do ĉi tiu estas nur n.

426
00:32:20,820 --> 00:32:25,050
Kaj tiam pli iuj konstanta laboro.

427
00:32:25,050 --> 00:32:27,770
Kaj tion rekursieca ekvacio

428
00:32:27,770 --> 00:32:35,560
Estas ĝuste la rekursieca ekvacio por merge varon.

429
00:32:35,560 --> 00:32:39,170
Kaj ni ĉiuj scias ke merge varo estas n logo n tempon.

430
00:32:39,170 --> 00:32:46,880
Tial, nia algoritmo ankaŭ n logo n tempon.

431
00:32:46,880 --> 00:32:52,220
Ĉu ĉi tiu ripeto sencon?

432
00:32:52,220 --> 00:32:55,780
Nur mallongan recap de ĉi:

433
00:32:55,780 --> 00:32:59,170
T (n) estas la nombro de paŝoj al komputi la maksimuma profito

434
00:32:59,170 --> 00:33:02,750
Super la apartajxo de n tagoj.

435
00:33:02,750 --> 00:33:06,010
La vojo ni disigis nian rekursie alvokoj

436
00:33:06,010 --> 00:33:11,980
estas nomante nian solvon en la unua n / 2 tagoj,

437
00:33:11,980 --> 00:33:14,490
do jen unu alvokon,

438
00:33:14,490 --> 00:33:16,940
kaj tiam ni nomas denove en la dua duono.

439
00:33:16,940 --> 00:33:20,440
Do jen du alvokoj.

440
00:33:20,440 --> 00:33:25,310
Kaj tiam ni trovos minimumo en la maldekstra duono, kiun ni povas fari en lineara tempo,

441
00:33:25,310 --> 00:33:29,010
trovi la maksimumo de la dekstra duono, kiun ni povas fari en lineara tempo.

442
00:33:29,010 --> 00:33:31,570
Do n / 2 + n / 2 estas simple n.

443
00:33:31,570 --> 00:33:36,020
Tiam ni havi iu konstanta laboro, kiu estas kiel fari aritmetiko.

444
00:33:36,020 --> 00:33:39,860
Ĉi rekursieca ekvacio estas precize la rekursieca ekvacio por merge varon.

445
00:33:39,860 --> 00:33:55,490
Tial, nia barajar algoritmo estas ankaŭ n log n.

446
00:33:55,490 --> 00:33:58,520
Do kiom spaco ni uzas?

447
00:33:58,520 --> 00:34:04,910
Ni reiru al la kodo.

448
00:34:04,910 --> 00:34:09,420
>> Pli bona demando estas, kiom da pilo kadroj ni iam havos je ĉiu momento?

449
00:34:09,420 --> 00:34:11,449
Ekde ni uzas rekursio,

450
00:34:11,449 --> 00:34:23,530
la nombro de pilo kadroj determinas nian spacon uzado.

451
00:34:23,530 --> 00:34:29,440
Ni konsideru n = 8.

452
00:34:29,440 --> 00:34:36,889
Ni nomas barajar la 8,

453
00:34:36,889 --> 00:34:41,580
kio vokos barajar en la unuaj kvar elementoj,

454
00:34:41,580 --> 00:34:46,250
kio vokos al barajar en la unuaj du elementoj.

455
00:34:46,250 --> 00:34:51,550
Do nia stako estas - tio estas nia stako.

456
00:34:51,550 --> 00:34:54,980
Kaj tiam ni nomas barajar denove la 1,

457
00:34:54,980 --> 00:34:58,070
kaj tio nia bazo kazo estas, ke ni revenu tuj.

458
00:34:58,070 --> 00:35:04,700
Ĉu ni iam havos pli ol tio multaj stako kadroj?

459
00:35:04,700 --> 00:35:08,880
Ne, ĉar ĉiufoje kiam ni alvoko,

460
00:35:08,880 --> 00:35:10,770
rekursia alvoko al barajar,

461
00:35:10,770 --> 00:35:13,950
ni dividas nian grandecon en duono.

462
00:35:13,950 --> 00:35:17,020
Do la maksimuma nombro de pilo kadroj ni iam havos je ĉiu momento

463
00:35:17,020 --> 00:35:28,460
estas de ordo de logo n pilo kadroj.

464
00:35:28,460 --> 00:35:42,460
Ĉiu pilo kadro havas konstantan spaco,

465
00:35:42,460 --> 00:35:44,410
kaj sekve la tuta kvanto de spaco,

466
00:35:44,410 --> 00:35:49,240
la maksimuma kvanto da spaco ni iam uzas estas O (log n) spaco

467
00:35:49,240 --> 00:36:03,040
kie n estas la nombro de tagoj.

468
00:36:03,040 --> 00:36:07,230
>> Nun, ĉiam petas vin, "Ĉu ni povas fari pli bone?"

469
00:36:07,230 --> 00:36:12,390
Kaj en aparta, ni povas redukti tiun al problemo ni jam solvita?

470
00:36:12,390 --> 00:36:20,040
Al aludo: ni nur diskutas du aliaj problemoj antaŭ ĉi tio, kaj ĝi ne tuj estos barajar.

471
00:36:20,040 --> 00:36:26,200
Ni povas konverti tiun sakon problemo en la maksimuma subarray problemo.

472
00:36:26,200 --> 00:36:40,100
Kiel ni povas fari ĉi tion?

473
00:36:40,100 --> 00:36:42,570
Unu el vi? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Do la maksimuma subarray problemo,

477
00:36:59,940 --> 00:37:10,610
ni serĉas sumo super kontinua subarray.

478
00:37:10,610 --> 00:37:16,230
Kaj Emmy la sugesto por la akcioj problemo,

479
00:37:16,230 --> 00:37:30,720
konsideri la ŝanĝojn, aŭ la deltas.

480
00:37:30,720 --> 00:37:37,440
Kaj bildon de tio estas - tio estas prezo de la sako,

481
00:37:37,440 --> 00:37:42,610
sed se ni prenas la diferenco inter ĉiu sinsekva tago -

482
00:37:42,610 --> 00:37:45,200
do ni vidas, ke la maksimuma prezo, maksimuma profito ni povus fari

483
00:37:45,200 --> 00:37:50,070
estas, se ni aĉetus ĉi tie kaj vendi tie.

484
00:37:50,070 --> 00:37:54,240
Sed ni rigardu la kontinua - ni rigardu la subarray problemo.

485
00:37:54,240 --> 00:38:02,510
Do jen, ni povas fari - irante de tie al tie,

486
00:38:02,510 --> 00:38:08,410
ni havas pozitivan ŝanĝon, kaj tiam irante de tie al tie ni havas negativan ŝanĝon.

487
00:38:08,410 --> 00:38:14,220
Sed tiam, irante de tie al tie ni havas grandegan pozitivan ŝanĝon.

488
00:38:14,220 --> 00:38:20,930
Kaj jen estas la ŝanĝoj kiuj ni volas resumi por atingi nian finan profiton.

489
00:38:20,930 --> 00:38:25,160
Tiam ni havas pli negativajn ŝanĝoj ĉi tie.

490
00:38:25,160 --> 00:38:29,990
La ŝlosilo por redukti nian stock problemo en nia maksimuma subarray problemo

491
00:38:29,990 --> 00:38:36,630
estas al konsideri la deltas inter la tagoj.

492
00:38:36,630 --> 00:38:40,630
Do ni kreu novan tabelo nomis deltas,

493
00:38:40,630 --> 00:38:43,000
pravalorizi la unua eniro al esti 0,

494
00:38:43,000 --> 00:38:46,380
kaj tiam por ĉiu delta (i), lasu ke estu la diferenco

495
00:38:46,380 --> 00:38:52,830
de miaj enigo array (i), kaj batalarangxis (i - 1).

496
00:38:52,830 --> 00:38:55,530
Tiam ni nomas nian rutinon proceduro por maksimuma subarray

497
00:38:55,530 --> 00:39:01,500
pasante en delto de tabelo.

498
00:39:01,500 --> 00:39:06,440
Kaj ĉar maksimuma subarray estas lineara tempo,

499
00:39:06,440 --> 00:39:09,370
kaj ĉi redukto, tiu ĉi procezo de kreado ĉi delto tabelo,

500
00:39:09,370 --> 00:39:11,780
Ankaŭ estas lineara tempo,

501
00:39:11,780 --> 00:39:19,060
tiam la fina solvo por akcioj estas O (n) laboro pli O (n) laboro, estas ankoraŭ O (n) laboro.

502
00:39:19,060 --> 00:39:23,900
Do ni havas lineara tempo solvon al nia problemo.

503
00:39:23,900 --> 00:39:29,610
Ĉu ĉiuj komprenas ĉi transformo?

504
00:39:29,610 --> 00:39:32,140
>> En ĝenerala, bona ideo ke vi ĉiam devas

505
00:39:32,140 --> 00:39:34,290
estas provi redukti novan problemon, kiun vi vidas.

506
00:39:34,290 --> 00:39:37,700
Se ĝi aspektas familiaraj al malnova problemo,

507
00:39:37,700 --> 00:39:39,590
provi redukti ĝin al malnova problemo.

508
00:39:39,590 --> 00:39:41,950
Kaj se vi povas uzi ĉiujn ilojn kiuj vi uzas la malnovan problemon

509
00:39:41,950 --> 00:39:46,450
solvi la nova problemo.

510
00:39:46,450 --> 00:39:49,010
Do por kovri supren, teknika intervjuoj estas defiante.

511
00:39:49,010 --> 00:39:52,280
Ĉi tiuj problemoj estas probable iuj de la plej malfacilaj problemoj

512
00:39:52,280 --> 00:39:54,700
ke vi povus vidi en intervjuo,

513
00:39:54,700 --> 00:39:57,690
do se vi ne komprenas ĉiujn problemojn ke mi nur kovrita, tio estas bone.

514
00:39:57,690 --> 00:40:01,080
Ĉi tiuj estas kelkaj el la pli defia problemo.

515
00:40:01,080 --> 00:40:03,050
Praktiko, praktiko, praktiko.

516
00:40:03,050 --> 00:40:08,170
Mi donis multe da problemoj en la flugfolia, do definitive kontroli tiujn eksteren.

517
00:40:08,170 --> 00:40:11,690
Kaj bonŝancon en via intervjuo. Ĉiuj miaj rimedoj estas eldonitaj en ĉi-ligilo,

518
00:40:11,690 --> 00:40:15,220
kaj unu el miaj amikoj altranga proponis fari maketo teknika intervjuoj,

519
00:40:15,220 --> 00:40:22,050
do se vi estas interesata, retpoŝto Will Yao en tiu retadreso.

520
00:40:22,050 --> 00:40:26,070
Se vi havas iujn demandojn, vi povas peti mi.

521
00:40:26,070 --> 00:40:28,780
Ĉu vi infanoj havas specifajn demandojn rilataj al teknikaj intervjuoj

522
00:40:28,780 --> 00:40:38,440
aŭ ajna problemoj ni vidis ĝis nun?

523
00:40:38,440 --> 00:40:49,910
Okay. Nu, bonan sorton en via intervjuo.

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