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

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

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

4
00:00:08,910 --> 00:00:12,420
Hi lahat, ako Kenny. Ako ay kasalukuyang isang junior pag-aaral computer science.

5
00:00:12,420 --> 00:00:17,310
Ako ng dating CS tf, at nais ko ako ay may ito kapag ako ay isang underclassman,

6
00:00:17,310 --> 00:00:19,380
at na kung bakit ako pagbibigay ito seminar.

7
00:00:19,380 --> 00:00:21,370
Kaya Umaasa ako na masisiyahan ka ito.

8
00:00:21,370 --> 00:00:23,470
Seminar na ito ay tungkol sa mga panteknikal na panayam,

9
00:00:23,470 --> 00:00:26,650
at sa lahat ng aking mga mapagkukunan ay maaaring matagpuan sa link na ito,

10
00:00:26,650 --> 00:00:32,350
ang link na ito dito mismo, ng ilang mga mapagkukunan.

11
00:00:32,350 --> 00:00:36,550
Kaya ko gumawa ng listahan ng mga problema, aktwal na, lubos ng ilang mga problema.

12
00:00:36,550 --> 00:00:40,800
Din ng pangkalahatang mga mapagkukunan ng pahina kung saan maaari naming mahanap ang mga tip

13
00:00:40,800 --> 00:00:42,870
sa kung paano upang maghanda para sa isang pakikipanayam,

14
00:00:42,870 --> 00:00:46,470
mga tip sa kung ano ang dapat mong gawin sa panahon ng isang aktwal na panayam,

15
00:00:46,470 --> 00:00:51,910
pati na rin kung paano lapitan ng mga problema at mga mapagkukunan para sa sanggunian sa hinaharap.

16
00:00:51,910 --> 00:00:53,980
Ang lahat ng ito online.

17
00:00:53,980 --> 00:00:58,290
At lang lagyan ng paunang salita ang seminar na ito, isang disclaimer,

18
00:00:58,290 --> 00:01:00,690
tulad ng ito ay dapat hindi - ang iyong paghahanda sa panayam

19
00:01:00,690 --> 00:01:02,800
hindi dapat limitado sa listahang ito.

20
00:01:02,800 --> 00:01:04,750
Lamang ito ay nilalayong maging isang gabay,

21
00:01:04,750 --> 00:01:08,890
at dapat mong tiyak ang lahat ng sinasabi ko na may isang butil ng asin,

22
00:01:08,890 --> 00:01:14,620
ngunit ring gamitin ang lahat ng ginamit ko upang makatulong sa iyo sa iyong paghahanda ng panayam.

23
00:01:14,620 --> 00:01:16,400
>> Pupunta ako upang mapabilis sa pamamagitan ng susunod na ilang mga slide

24
00:01:16,400 --> 00:01:18,650
upang maaari naming makapunta sa aktwal na mga pag-aaral ng kaso.

25
00:01:18,650 --> 00:01:23,630
Ang istraktura ng isang pakikipanayam para sa isang postion ng software engineering,

26
00:01:23,630 --> 00:01:26,320
ito ay karaniwang 30 sa 45 minuto,

27
00:01:26,320 --> 00:01:29,810
maramihang mga round, depende sa kumpanya.

28
00:01:29,810 --> 00:01:33,090
Madalas makikita mo ang coding sa isang puting board.

29
00:01:33,090 --> 00:01:35,960
Kaya isang puting board tulad nito, ngunit madalas sa isang mas maliit na scale.

30
00:01:35,960 --> 00:01:38,540
Kung nagkakaroon ka ng isang telepono pakikipanayam, malamang na gumagamit

31
00:01:38,540 --> 00:01:44,030
alinman collabedit o ng isang Google Doc sa gayon ay maaari nilang makita na Live coding

32
00:01:44,030 --> 00:01:46,500
habang ikaw ay kapanayamin sa telepono.

33
00:01:46,500 --> 00:01:48,490
Isang pakikipanayam mismo ay karaniwang 2 o 3 mga problema

34
00:01:48,490 --> 00:01:50,620
pagsubok ng kaalaman ng iyong computer science.

35
00:01:50,620 --> 00:01:54,490
At ito ay halos tiyak na sangkot sa coding.

36
00:01:54,490 --> 00:01:59,540
Ang mga uri ng mga katanungan na makikita mo ay karaniwang data istraktura at algorithm.

37
00:01:59,540 --> 00:02:02,210
At sa paggawa ng mga ganitong uri ng mga problema,

38
00:02:02,210 --> 00:02:07,830
sila tanungin mo, i, kung ano ang oras at pagiging kumplikado ng espasyo, malaki O?

39
00:02:07,830 --> 00:02:09,800
Madalas din nila magtanong ng mga mas mataas na antas na mga katanungan,

40
00:02:09,800 --> 00:02:12,530
ito, pagdidisenyo ng isang sistema,

41
00:02:12,530 --> 00:02:14,770
kung paano mo lay ang iyong code?

42
00:02:14,770 --> 00:02:18,370
Ano ang interface, kung ano ang klase, kung ano ang module mayroon ka sa iyong system,

43
00:02:18,370 --> 00:02:20,900
at paano ang mga nakikipag-ugnayan nang magkasama?

44
00:02:20,900 --> 00:02:26,130
Kaya data istraktura at algorithm pati na rin ang pagdidisenyo system.

45
00:02:26,130 --> 00:02:29,180
>> Ilang pangkalahatang mga tip bago namin sumisid sa sa aming mga pag-aaral ng kaso.

46
00:02:29,180 --> 00:02:32,300
Tingin ko ang pinaka-mahalagang panuntunan ay laging iniisip ang malakas.

47
00:02:32,300 --> 00:02:36,980
Pakikipanayam ay dapat na ang iyong pagkakataon upang ipakita ang iyong proseso sa pag-iisip.

48
00:02:36,980 --> 00:02:39,820
Ang punto ng pakikipanayam para sa tagapanayam upang masukat

49
00:02:39,820 --> 00:02:42,660
kung paano sa tingin mo at kung paano kang pumunta sa pamamagitan ng isang problema.

50
00:02:42,660 --> 00:02:45,210
Ang pinakamasama bagay na maaari mong gawin ay maging tahimik sa buong buong pakikipanayam.

51
00:02:45,210 --> 00:02:50,090
Na lang walang magandang.

52
00:02:50,090 --> 00:02:53,230
Kapag ikaw ay bibigyan ng isang katanungan, gusto mo ring upang tiyakin na nauunawaan mo ang tanong.

53
00:02:53,230 --> 00:02:55,350
Kaya ulitin ang tanong sa iyong sariling mga salita

54
00:02:55,350 --> 00:02:58,920
at pagtatangka upang gumana masinsinang ng ilang simpleng mga kaso ng pagsubok

55
00:02:58,920 --> 00:03:01,530
upang tiyakin na nauunawaan mo ang tanong.

56
00:03:01,530 --> 00:03:05,510
Paggawa sa pamamagitan ng ilang mga kaso ng pagsubok ay magbibigay sa iyo ng isang Swersey sa kung paano malutas ang problemang ito.

57
00:03:05,510 --> 00:03:11,210
Maaari mo ring matuklasan ng ilang mga pattern upang makatulong sa iyo na malutas ang problema.

58
00:03:11,210 --> 00:03:14,500
Ang kanilang malaking tip ay hindi bigo.

59
00:03:14,500 --> 00:03:17,060
Huwag bigo.

60
00:03:17,060 --> 00:03:19,060
Panayam ay mapaghamong, ngunit ang pinakamasama bagay na maaari mong gawin,

61
00:03:19,060 --> 00:03:23,330
sa karagdagan sa pagiging tahimik, ay nahahalata bigo.

62
00:03:23,330 --> 00:03:27,410
Hindi mo nais na magbigay na impression sa isang tagapanayam.

63
00:03:27,410 --> 00:03:33,960
Isang bagay na - ito, maraming mga tao, kapag sila ay pumunta sa isang pakikipanayam,

64
00:03:33,960 --> 00:03:37,150
tinangka nilang subukan upang mahanap ang pinakamahusay na solusyon sa unang,

65
00:03:37,150 --> 00:03:39,950
kapag talaga, may karaniwang isang nandidilat halata na solusyon.

66
00:03:39,950 --> 00:03:43,500
Maaaring maging mabagal, maaaring ito ay hindi mabisa, ngunit dapat mo lamang ihayag ito,

67
00:03:43,500 --> 00:03:46,210
lamang kaya mayroon kang isang panimulang punto kung saan ay mas mahusay.

68
00:03:46,210 --> 00:03:48,270
Gayundin, pagturo out ang solusyon ay mabagal, sa mga tuntunin ng

69
00:03:48,270 --> 00:03:52,160
malaking O oras kumplikado o pagiging kumplikado ng espasyo,

70
00:03:52,160 --> 00:03:54,450
ay nagpapakita sa tagapanayam na nauunawaan mo

71
00:03:54,450 --> 00:03:57,510
mga isyung ito kapag sumusulat code.

72
00:03:57,510 --> 00:04:01,440
Kaya huwag matakot upang makabuo ng ang pinakasimpleng algorithm unang

73
00:04:01,440 --> 00:04:04,950
at pagkatapos ay mas mahusay mula doon.

74
00:04:04,950 --> 00:04:09,810
Anumang mga katanungan sa ngayon? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Kaya natin sumisid sa aming unang problema.

76
00:04:11,650 --> 00:04:14,790
"Dahil isang array ng mga integer n, magsulat ng isang function na shuffles ang array

77
00:04:14,790 --> 00:04:20,209
sa lugar tulad na ang lahat ng mga permutations ng integer n pantay malamang. "

78
00:04:20,209 --> 00:04:23,470
At angkinin mayroon kang makuha ang isang random generator integer

79
00:04:23,470 --> 00:04:30,980
na bumubuo ng isang integer sa isang hanay mula 0 hanggang i, kalahati hanay.

80
00:04:30,980 --> 00:04:32,970
Ba ang lahat maunawaan ang tanong na ito?

81
00:04:32,970 --> 00:04:39,660
Ako magbibigay sa iyo ng isang array ng mga integer n, at Gusto kong shuffle ito.

82
00:04:39,660 --> 00:04:46,050
Sa aking direktoryo, ako nagsulat ng ilang mga programa upang ipakita kung ano ang ibig sabihin ko.

83
00:04:46,050 --> 00:04:48,910
Pupunta ako sa shuffle isang array ng 20 mga elemento,

84
00:04:48,910 --> 00:04:52,490
mula sa -10 sa 9,

85
00:04:52,490 --> 00:04:57,050
at gusto kong mong output ng listahan tulad nito.

86
00:04:57,050 --> 00:05:02,890
Kaya ito ay aking pinagsunod-sunod input array, at Gusto kong shuffle ito.

87
00:05:02,890 --> 00:05:07,070
Susubukan naming gawin itong muli.

88
00:05:07,070 --> 00:05:13,780
Ba ang lahat maunawaan ang tanong? Okay.

89
00:05:13,780 --> 00:05:16,730
Kaya ito ay hanggang sa iyo.

90
00:05:16,730 --> 00:05:21,220
Ano ang ilang mga ideya? Maaari mong gawin ito bilang n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Buksan sa mga mungkahi.

92
00:05:34,400 --> 00:05:37,730
Okay. Kaya isang ideya, na iminungkahi ng Emmy,

93
00:05:37,730 --> 00:05:45,300
compute muna ng random na numero, random ng integer, sa isang hanay mula 0 hanggang 20.

94
00:05:45,300 --> 00:05:49,840
Kaya ipagpalagay aming array ay may haba ng 20.

95
00:05:49,840 --> 00:05:54,800
Sa aming diagram ng 20 elemento,

96
00:05:54,800 --> 00:05:58,560
ito ang aming input array.

97
00:05:58,560 --> 00:06:04,590
At ngayon, ang kanyang mga mungkahi ay upang lumikha ng isang bagong array,

98
00:06:04,590 --> 00:06:08,440
kaya ito ay ang output ng array.

99
00:06:08,440 --> 00:06:12,880
At batay sa i ibinalik sa pamamagitan ng ribete -

100
00:06:12,880 --> 00:06:17,580
kaya kung i ay, sabihin nating, 17,

101
00:06:17,580 --> 00:06:25,640
kopyahin ang ika-17 na elemento sa unang posisyon.

102
00:06:25,640 --> 00:06:30,300
Ngayon ay kailangan naming tanggalin - kailangan namin upang ilipat ang lahat ng mga elemento dito

103
00:06:30,300 --> 00:06:36,920
sa paglipas ng sa gayon ay mayroon kaming isang agwat sa dulo at walang butas sa gitna.

104
00:06:36,920 --> 00:06:39,860
At ngayon namin ulitin ang proseso.

105
00:06:39,860 --> 00:06:46,360
Ngayon namin pumili ng isang bagong random integer sa pagitan ng 0 at 19.

106
00:06:46,360 --> 00:06:52,510
Mayroon kaming isang bagong i dito, at kopyahin namin ang elemento na ito sa posisyon na ito.

107
00:06:52,510 --> 00:07:00,960
Pagkatapos namin shift ang mga item sa paglipas at ulitin namin ang proseso hanggang mayroon namin ang aming buong bagong array.

108
00:07:00,960 --> 00:07:05,890
Ano ang run oras ng algorithm na ito?

109
00:07:05,890 --> 00:07:08,110
Well, sabihin isaalang-alang ang epekto ng mga ito.

110
00:07:08,110 --> 00:07:10,380
Paglilipat namin ang bawat elemento.

111
00:07:10,380 --> 00:07:16,800
Kapag naming alisin ang i, paglilipat namin ay ang lahat ng mga elemento matapos itong sa kaliwa.

112
00:07:16,800 --> 00:07:21,600
At iyon ay isang gastos ng O (n)

113
00:07:21,600 --> 00:07:26,100
dahil kung ano ang kung aalisin namin ang unang elemento?

114
00:07:26,100 --> 00:07:29,670
Kaya para sa bawat pag-alis, alisin namin ang -

115
00:07:29,670 --> 00:07:32,170
sa bawat pag-alis matatamo ng operasyon O (n),

116
00:07:32,170 --> 00:07:41,520
at dahil n pag-alis namin, ito ay humahantong sa isang shuffle O (n ^ 2).

117
00:07:41,520 --> 00:07:49,550
Okay. Kaya magandang simula. Magandang simula.

118
00:07:49,550 --> 00:07:55,290
>> Mungkahi ng isa pang ay upang gamitin ang isang bagay na kilala bilang shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
o ang Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
At ito ay talagang isang linear na oras shuffle.

121
00:07:59,630 --> 00:08:02,200
At ideya ay halos katulad na.

122
00:08:02,200 --> 00:08:05,160
Muli, mayroon kaming ang aming input array,

123
00:08:05,160 --> 00:08:08,580
ngunit sa halip ng paggamit ng dalawang array para sa aming input / output,

124
00:08:08,580 --> 00:08:13,590
ginagamit namin ang unang bahagi ng array upang subaybayan ang aming shuffled bahagi,

125
00:08:13,590 --> 00:08:18,400
at hindi na namin subaybayan, at pagkatapos namin iwanan ang natitira sa aming array para sa unshuffled bahagi.

126
00:08:18,400 --> 00:08:24,330
Kaya narito ang kung ano ang ibig sabihin ko. Simulan namin off ang may - pinili naming i,

127
00:08:24,330 --> 00:08:30,910
isang array mula 0 hanggang 20.

128
00:08:30,910 --> 00:08:36,150
Aming kasalukuyang pointer ay tumuturo sa unang index.

129
00:08:36,150 --> 00:08:39,590
Pinili namin ang ilang i dito

130
00:08:39,590 --> 00:08:42,740
at ngayon kami magpalitan.

131
00:08:42,740 --> 00:08:47,690
Kaya kung ito ay 5 at ito ay 4,

132
00:08:47,690 --> 00:08:57,150
nagreresulta array ay may 5 dito at 4 dito.

133
00:08:57,150 --> 00:09:00,390
At ngayon, tandaan namin ang isang marker dito.

134
00:09:00,390 --> 00:09:05,770
Lahat sa kaliwa ay shuffled,

135
00:09:05,770 --> 00:09:15,160
at lahat sa kanan ay unshuffled.

136
00:09:15,160 --> 00:09:17,260
At ngayon maaari naming ulitin ang proseso.

137
00:09:17,260 --> 00:09:25,210
Pinili namin ang isang random na index sa pagitan ng 1 at 20 ngayon.

138
00:09:25,210 --> 00:09:30,650
Kaya ipagpalagay ang aming bagong i dito.

139
00:09:30,650 --> 00:09:39,370
Ngayon swap namin ito i sa aming kasalukuyang bagong posisyon dito.

140
00:09:39,370 --> 00:09:44,790
Kaya namin pagpapalit pabalik-balik tulad nito.

141
00:09:44,790 --> 00:09:51,630
Hayaan akong ilabas ang code upang gawin itong mas kongkreto.

142
00:09:51,630 --> 00:09:55,290
Magsisimula kami sa aming pagpipilian ng i -

143
00:09:55,290 --> 00:09:58,370
simulan namin na may kasing-halaga i sa 0, namin pumili ng isang random na lokasyon j

144
00:09:58,370 --> 00:10:02,420
sa ang unshuffled bahagi ng array, i n-1.

145
00:10:02,420 --> 00:10:07,280
Kaya kung ako dito, pumili ng isang random na index sa pagitan ng dito at sa ibang bahagi ng array,

146
00:10:07,280 --> 00:10:12,410
at swap namin.

147
00:10:12,410 --> 00:10:17,550
Ito ay ang lahat ng mga code na kinakailangan upang shuffle iyong array.

148
00:10:17,550 --> 00:10:21,670
Anumang mga katanungan?

149
00:10:21,670 --> 00:10:25,530
>> Well, kailangan isa ang tanong ay, kung bakit ay ito tama?

150
00:10:25,530 --> 00:10:28,360
Bakit bawat permutasyon pantay malamang?

151
00:10:28,360 --> 00:10:30,410
At hindi ako ay pumunta sa pamamagitan ng katibayan ng ito,

152
00:10:30,410 --> 00:10:35,970
ngunit maraming mga problema sa computer science ay napatunayan sa pamamagitan ng pagtatalaga sa tungkulin.

153
00:10:35,970 --> 00:10:38,520
Paano marami sa inyo ang pamilyar sa induction?

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

155
00:10:40,590 --> 00:10:43,610
Sa gayon maaari mong patunayan ang kawastuhan ng ang algorithm na ito sa pamamagitan ng simpleng induction,

156
00:10:43,610 --> 00:10:49,540
kung saan ay ang iyong induction teorya, ipinapalagay na

157
00:10:49,540 --> 00:10:53,290
ang aking shuffle nagbabalik sa bawat permutasyon pantay malamang

158
00:10:53,290 --> 00:10:56,120
hanggang sa ang unang i elemento.

159
00:10:56,120 --> 00:10:58,300
Ngayon, isaalang-alang ang i + 1.

160
00:10:58,300 --> 00:11:02,550
At sa pamamagitan ng ang paraan na pinili namin sa aming index j sa swap,

161
00:11:02,550 --> 00:11:05,230
ito ay humahantong sa - at pagkatapos kang magtrabaho ang mga detalye,

162
00:11:05,230 --> 00:11:07,390
hindi bababa sa isang buong katibayan kung bakit algorithm na ito ay nagbabalik

163
00:11:07,390 --> 00:11:12,800
bawat permutasyon may pantay malamang na posibilidad.

164
00:11:12,800 --> 00:11:15,940
>> Lahat ng karapatan, sa tabi problema.

165
00:11:15,940 --> 00:11:19,170
Kaya "bibigyan ng isang array ng mga integer, postive, zero, negatibong,

166
00:11:19,170 --> 00:11:21,290
magsulat ng isang function na kinakalkula ang maximum na kabuuan

167
00:11:21,290 --> 00:11:24,720
ng anumang continueous subarray ng input array. "

168
00:11:24,720 --> 00:11:28,370
Isang halimbawa dito ay, sa kaso na kung saan ang lahat ng mga numero ay positibo,

169
00:11:28,370 --> 00:11:31,320
pagkatapos ay kasalukuyang ang pinakamahusay na pagpipilian ay upang gawin ang buong array.

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

171
00:11:34,690 --> 00:11:36,780
Kapag mayroon kang ilang mga negatibo sa doon,

172
00:11:36,780 --> 00:11:38,690
sa kasong ito gusto lang namin ang unang dalawang

173
00:11:38,690 --> 00:11:44,590
dahil ang pagpili ng -1 at / o -3 ay dalhin ang aming kabuuan.

174
00:11:44,590 --> 00:11:48,120
Minsan maaari naming magsimula sa gitna ng array.

175
00:11:48,120 --> 00:11:53,500
Minsan gusto naming pumili ng wala sa lahat; pinakamahusay na hindi tumagal ng anumang.

176
00:11:53,500 --> 00:11:56,490
At kung minsan ito ay mas mahusay na upang gawin ang pagkahulog,

177
00:11:56,490 --> 00:12:07,510
dahil ang bagay na ito pagkatapos na ito ay sobrang malaki. Kaya ang anumang mga ideya?

178
00:12:07,510 --> 00:12:10,970
(Mag-aaral, hindi maintindihan) >> Oo.

179
00:12:10,970 --> 00:12:13,560
Ipagpalagay na hindi ko nagsasagawa ng -1.

180
00:12:13,560 --> 00:12:16,170
Pagkatapos alinman pinili ko ang 1,000 at 20,000,

181
00:12:16,170 --> 00:12:18,630
o ko lang piliin ang 3 bilyong.

182
00:12:18,630 --> 00:12:20,760
Well, ang pinakamahusay na pagpipilian ay upang gawin ang lahat ng mga numero.

183
00:12:20,760 --> 00:12:24,350
Ito -1, sa kabila ng pagiging negatibong,

184
00:12:24,350 --> 00:12:31,340
ang buong kabuuan ay mas mahusay kaysa sa ay hindi ko na kumuha -1.

185
00:12:31,340 --> 00:12:36,460
Kaya isa sa mga tip na nabanggit ko mas maaga ay upang ihayag ang malinaw halata

186
00:12:36,460 --> 00:12:40,540
at taong malupit na puwersa solusyon muna.

187
00:12:40,540 --> 00:12:44,340
Ano ang taong malupit na puwersa solusyon ang problemang ito? Oo?

188
00:12:44,340 --> 00:12:46,890
[Jane] Well, sa tingin ko ang mga taong malupit na puwersa solusyon

189
00:12:46,890 --> 00:12:52,600
ay upang magdagdag ng hanggang ang lahat ng posibleng mga kumbinasyon (hindi maintindihan).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Kaya Jane ng ideya gumawa ng bawat posibleng -

191
00:12:58,250 --> 00:13:01,470
Ako paraphrasing - ay upang gumawa ng bawat posibleng tuloy-tuloy na subarray,

192
00:13:01,470 --> 00:13:07,840
compute ang kabuuan nito, at pagkatapos ay ang pinakamataas na ng lahat ng mga posibleng tuloy-tuloy na subarrays.

193
00:13:07,840 --> 00:13:13,310
Ano ang natatanging nagpapakilala sa ng subarray sa aking input array?

194
00:13:13,310 --> 00:13:17,380
Tulad ng, kung ano ang dalawang bagay ang kailangan kong? Oo?

195
00:13:17,380 --> 00:13:19,970
(Mag-aaral, hindi maintindihan) >> Karapatan.

196
00:13:19,970 --> 00:13:22,130
Ang isang mas mababang sumunod sa index at upper bound index

197
00:13:22,130 --> 00:13:28,300
natatanging tumutukoy isang patuloy na subarray.

198
00:13:28,300 --> 00:13:31,400
[Babae mag-aaral] namin pagtantya ang isang hanay ng mga natatanging mga numero?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Kaya kanyang tanong, kami ipagpalagay aming array -

200
00:13:34,280 --> 00:13:39,000
ang aming array lahat ng mga natatanging mga numero, at ang sagot ay hindi.

201
00:13:39,000 --> 00:13:43,390
>> Kung naming gamitin ang aming taong malupit na puwersa ng solusyon, pagkatapos ay ang mga indeks ng pagsisimula / pagtatapos

202
00:13:43,390 --> 00:13:47,200
natatanging tinutukoy ng aming tuloy-tuloy na subarray.

203
00:13:47,200 --> 00:13:51,680
Kaya kung umulit namin para sa lahat ng posibleng mga entry sa simula,

204
00:13:51,680 --> 00:13:58,320
at para sa lahat ng mga entry sa pagtatapos> o = upang magsimula, at <n,

205
00:13:58,320 --> 00:14:05,570
compute mo ang kabuuan, at pagkatapos namin ang maximum na kabuuan na nasaksihan namin sa ngayon.

206
00:14:05,570 --> 00:14:07,880
Ba itong malinaw?

207
00:14:07,880 --> 00:14:12,230
Ano ang malaking O na ito solusyon?

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

209
00:14:16,660 --> 00:14:18,860
Hindi pa n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Tandaan na umulit namin mula 0 hanggang n,

211
00:14:25,250 --> 00:14:27,520
sa gayon ay ang isa para sa loop.

212
00:14:27,520 --> 00:14:35,120
Namin umulit muli mula sa halos simula sa dulo, isa pang para sa loop.

213
00:14:35,120 --> 00:14:37,640
At ngayon, sa loob na, mayroon kaming upang ipahayag sa ilang kataga bawat entry,

214
00:14:37,640 --> 00:14:43,810
kaya na ang isa pang para sa loop. Kaya mayroon kaming tatlong Nested para sa mga loop, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Pupunta ito bilang isang panimulang punto.

216
00:14:46,560 --> 00:14:53,180
Ang aming solusyon ay walang mas masahol pa kaysa sa n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ba ang lahat maunawaan ang taong malupit na puwersa solusyon?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Ang isang mas mahusay na solusyon ay ang paggamit ng ideya na tinatawag na dynamic programming.

219
00:14:59,950 --> 00:15:03,040
Kung magdadala sa iyo CS124, na algorithm at Data istraktura,

220
00:15:03,040 --> 00:15:05,680
mong maging pamilyar sa diskarteng ito.

221
00:15:05,680 --> 00:15:12,190
At ideya, subukan upang bumuo ng mga solusyon sa mas maliliit na problema sa unang.

222
00:15:12,190 --> 00:15:17,990
Ano ang ibig sabihin ko sa pamamagitan ng ito, kasalukuyan kaming mag-alala tungkol sa dalawang bagay: pagsisimula at pagtatapos.

223
00:15:17,990 --> 00:15:29,340
At na ang nakakainis. Paano kung kami makakuha ng mapupuksa ng isa sa mga parameter?

224
00:15:29,340 --> 00:15:32,650
Ang isang ideya ay sa - lubos na binigyan ng aming orihinal na problema,

225
00:15:32,650 --> 00:15:37,470
mahanap ang maximum na kabuuan ng anumang subarray sa isang hanay [O, n-1].

226
00:15:37,470 --> 00:15:47,400
At ngayon kami ay may isang bagong subproblem, kung saan alam namin, sa aming kasalukuyang index i,

227
00:15:47,400 --> 00:15:52,520
alam namin dapat namin pagtibayin may. Ang aming subarray dapat magtapos sa kasalukuyang index.

228
00:15:52,520 --> 00:15:57,640
Kaya ang natitirang problema ay, kung saan dapat namin simulan aming subarray?

229
00:15:57,640 --> 00:16:05,160
Ba ito magkaroon ng kahulugan? Okay.

230
00:16:05,160 --> 00:16:12,030
Kaya ko ang code up na ito, at tingnan natin kung ano ang ibig sabihin nito.

231
00:16:12,030 --> 00:16:16,230
Sa ang codirectory, isang programa na tinatawag na subarray,

232
00:16:16,230 --> 00:16:19,470
at ito ay tumatagal ng bilang ng mga item,

233
00:16:19,470 --> 00:16:25,550
at nagbabalik ang pinakamalaki subarray kabuuan sa aking shuffled listahan.

234
00:16:25,550 --> 00:16:29,920
Kaya sa kasong ito, ang aming pinakamalaki subarray ay 3.

235
00:16:29,920 --> 00:16:34,850
At na kinuha sa pamamagitan ng lamang gamit ang 2 at 1.

236
00:16:34,850 --> 00:16:38,050
Natin patakbuhin itong muli. Rin 3.

237
00:16:38,050 --> 00:16:40,950
Ngunit ang oras na ito, tandaan kung paano namin nakuha ang 3.

238
00:16:40,950 --> 00:16:46,690
Kinuha namin ang - lang ang dadalhin namin ang 3 mismo

239
00:16:46,690 --> 00:16:49,980
dahil ito ay napapalibutan ng negatibo sa magkabilang panig,

240
00:16:49,980 --> 00:16:55,080
na dalhin ang isang kabuuan <3.

241
00:16:55,080 --> 00:16:57,820
Natin patakbuhin sa 10 mga item.

242
00:16:57,820 --> 00:17:03,200
Oras na ito ito ay 7, namin ang nangungunang 3 at 4.

243
00:17:03,200 --> 00:17:09,450
Oras na ito ito ay 8, at makuha namin na sa pamamagitan ng pagkuha ng 1, 4 at 3.

244
00:17:09,450 --> 00:17:16,310
Kaya upang mabigyan ka ng Swersey sa kung paano maaari naming malutas ang ito transformed problema,

245
00:17:16,310 --> 00:17:18,890
sabihin tingnan sa subarray.

246
00:17:18,890 --> 00:17:23,460
Kami ay ibinigay ang input array, at alam namin ang sagot ay 8.

247
00:17:23,460 --> 00:17:26,359
Isinasaalang-alang namin ang 1, 4, at 3.

248
00:17:26,359 --> 00:17:29,090
Ngunit ipaalam sa tumingin sa kung paano aktwal na nakuha namin na sagot.

249
00:17:29,090 --> 00:17:34,160
Tingnan natin sa pinakamalaki subarray na natapos sa bawat ng mga indeks ng.

250
00:17:34,160 --> 00:17:40,780
Ano ang pinakamalaki subarray na may magtapos sa unang posisyon?

251
00:17:40,780 --> 00:17:46,310
[Mag-aaral] Zero. >> Zero. Lamang huwag gawin ang -5.

252
00:17:46,310 --> 00:17:50,210
Narito ito ay pagpunta sa 0 pati na rin. Oo?

253
00:17:50,210 --> 00:17:56,470
(Mag-aaral, hindi maintindihan)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, paumanhin, ay isang -3.

255
00:17:58,960 --> 00:18:03,220
Kaya ito ay isang 2, ito ay isang -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Kaya -4, ano ang pinakamalaki subarray upang tapusin na posisyon

257
00:18:08,690 --> 00:18:12,910
kung saan -4 sa? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Ngayon, kailangan kong magtapos sa lokasyon kung saan -2 sa.

260
00:18:28,060 --> 00:18:39,330
Kaya 6, 5, 7, at ang huling isa ay 4.

261
00:18:39,330 --> 00:18:43,480
Alam na ito ang aking mga entry

262
00:18:43,480 --> 00:18:48,130
para ang transformed na problema kung saan ako dapat magtapos sa bawat ng mga indeks ng,

263
00:18:48,130 --> 00:18:51,410
pagkatapos ay ang aking panghuling sagot lamang, isang sweep sa buong,

264
00:18:51,410 --> 00:18:53,580
at ang maximum na bilang.

265
00:18:53,580 --> 00:18:55,620
Kaya sa kasong ito ito ay 8.

266
00:18:55,620 --> 00:19:00,010
Nagpapahiwatig ito na ang pinakamalaki subarray ay nagtatapos sa index na ito,

267
00:19:00,010 --> 00:19:04,970
at nagsimulang isang lugar bago ito.

268
00:19:04,970 --> 00:19:09,630
Ba ang lahat maunawaan ang transformed subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Well, sabihin malaman kung ang pag-ulit para sa.

270
00:19:22,160 --> 00:19:27,990
Natin isaalang-alang ang mga unang ilang entry.

271
00:19:27,990 --> 00:19:35,930
Kaya dito ito ay 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
At pagkatapos ay nagkaroon ng -2 dito, at dinala ito sa 6.

273
00:19:39,790 --> 00:19:50,800
Kaya kung tawagan ko ang entry sa posisyon i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
kung paano ang maaari kong gamitin ang sagot sa isang nakaraang subproblem

275
00:19:54,910 --> 00:19:59,360
sagutin ang subproblem na ito?

276
00:19:59,360 --> 00:20:04,550
Kung titingnan ko sa, sabihin nating, ang entry na ito.

277
00:20:04,550 --> 00:20:09,190
Paano ko compute ang sagot 6 sa pamamagitan ng pagtingin sa

278
00:20:09,190 --> 00:20:18,780
ng isang kumbinasyon ng array na ito at ang mga sagot sa nakaraang subproblems sa array? Oo?

279
00:20:18,780 --> 00:20:22,800
[Babae mag-aaral] mo ang hanay ng mga sums

280
00:20:22,800 --> 00:20:25,430
sa posisyon tama bago ito, kaya ang 8,

281
00:20:25,430 --> 00:20:32,170
at pagkatapos mong idagdag ang kasalukuyang subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Kaya ang kanyang mungkahi ay upang tingnan ang dalawang numerong ito,

283
00:20:36,460 --> 00:20:40,090
ang numerong ito at ang numerong ito.

284
00:20:40,090 --> 00:20:50,130
Kaya ito 8 ay tumutukoy sa sagot para sa subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
At sabihin tawagan ang aking input array A.

286
00:20:57,300 --> 00:21:01,470
Upang mahanap ang isang pinakamalaki subarray na nagtatapos sa posisyon i,

287
00:21:01,470 --> 00:21:03,980
Mayroon akong dalawang mga pagpipilian: Maaari ko bang ipagpatuloy ang subarray

288
00:21:03,980 --> 00:21:09,790
na natapos na sa nakaraang index, o magsimula ng isang bagong array.

289
00:21:09,790 --> 00:21:14,190
Kung ako ay upang ipagpatuloy ang subarray na nagsimula sa nakaraang index,

290
00:21:14,190 --> 00:21:19,260
pagkatapos ay ang maximum na kabuuan na maaari kong makamit ang sagot sa nakaraang subproblem

291
00:21:19,260 --> 00:21:24,120
pati na rin ang kasalukuyang array entry.

292
00:21:24,120 --> 00:21:27,550
Ngunit, ko rin ang pagpili ng simula ng isang bagong subarray,

293
00:21:27,550 --> 00:21:30,830
kung saan ang kabuuan ay 0.

294
00:21:30,830 --> 00:21:42,860
Kaya ang sagot ay max na 0, subproblem i - 1, pati na rin ang kasalukuyang array entry.

295
00:21:42,860 --> 00:21:46,150
Ba ang pag-ulit na ito ay may kabuluhan?

296
00:21:46,150 --> 00:21:50,840
Ang aming pag-ulit, namin natuklasan, ang subproblem i

297
00:21:50,840 --> 00:21:54,740
katumbas ng maximum ng nakaraang subproblem pati na ang aking kasalukuyang array entry,

298
00:21:54,740 --> 00:22:01,490
na nangangahulugan ipagpatuloy ang nakaraang subarray,

299
00:22:01,490 --> 00:22:07,250
o 0, magsimula ng isang bagong subarray sa aking kasalukuyang index.

300
00:22:07,250 --> 00:22:10,060
At sabay-sabay na binuo namin ang talahanayan na ito ng mga solusyon, at pagkatapos ay aming panghuling sagot,

301
00:22:10,060 --> 00:22:13,950
lamang gawin ang isang linear sweep sa buong array subproblem

302
00:22:13,950 --> 00:22:19,890
at ang maximum na bilang.

303
00:22:19,890 --> 00:22:23,330
Ito ay isang eksaktong pagpapatupad ng kung ano ang sinabi ko lang.

304
00:22:23,330 --> 00:22:27,320
Kaya kaming lumikha ng bagong array subproblem, subproblems.

305
00:22:27,320 --> 00:22:32,330
Ang unang entry ay alinman sa 0 o ang unang entry, ang maximum na mga dalawang.

306
00:22:32,330 --> 00:22:35,670
At para sa iba pang mga bahagi ng subproblems

307
00:22:35,670 --> 00:22:39,810
ginagamit namin ang eksaktong pag-ulit na lang namin natuklasan.

308
00:22:39,810 --> 00:22:49,960
Ngayon compute namin ang maximum ng aming mga subproblems array, at na ang aming panghuling sagot.

309
00:22:49,960 --> 00:22:54,130
>> Kaya kung magkano ang space ay namin ang paggamit sa algorithm?

310
00:22:54,130 --> 00:23:01,470
Kung mo lamang ang kinuha CS50, hindi mo maaaring tinalakay espasyo talaga.

311
00:23:01,470 --> 00:23:07,750
Well, isang bagay na dapat tandaan ay na tinatawag ko ang malloc dito sa n laki.

312
00:23:07,750 --> 00:23:13,590
Ano ang na iminumungkahi sa iyo?

313
00:23:13,590 --> 00:23:17,450
Algorithm na ito ay gumagamit ng linear espasyo.

314
00:23:17,450 --> 00:23:21,030
Maaari naming gawin mas mahusay?

315
00:23:21,030 --> 00:23:30,780
Mayroon bang anumang bagay na napansin mo na ay hindi kailangan upang makalkula ang panghuling sagot?

316
00:23:30,780 --> 00:23:33,290
Hulaan ko na ang isang mas mahusay na tanong ay, kung ano ang impormasyon

317
00:23:33,290 --> 00:23:40,680
hindi namin kailangan upang dalhin ang lahat ng mga paraan sa pamamagitan ng sa dulo?

318
00:23:40,680 --> 00:23:44,280
Ngayon, kung tiningnan namin sa mga dalawang linya,

319
00:23:44,280 --> 00:23:47,720
namin lamang pakialam tungkol sa nakaraang subproblem,

320
00:23:47,720 --> 00:23:50,910
at lamang namin pakialam tungkol sa maximum na nasaksihan namin sa ngayon.

321
00:23:50,910 --> 00:23:53,610
Upang makalkula ang aming panghuling sagot, hindi namin kailangan ang buong array.

322
00:23:53,610 --> 00:23:57,450
Kailangan lamang namin ang huling bilang, ang huling dalawang numero.

323
00:23:57,450 --> 00:24:02,630
Huling na numero para sa subproblem array, at ang huling bilang para sa maximum na.

324
00:24:02,630 --> 00:24:07,380
Kaya, sa katunayan, maaari naming pusible mga loop

325
00:24:07,380 --> 00:24:10,460
at pumunta mula sa linear espasyo sa pare-pareho ang espasyo.

326
00:24:10,460 --> 00:24:15,830
Kasalukuyang kabuuan sa ngayon, narito, pumapalit papel ng subproblem, ang aming subproblem array.

327
00:24:15,830 --> 00:24:20,020
Kaya kasalukuyang kabuuan, sa ngayon, ang sagot sa nakaraang subproblem.

328
00:24:20,020 --> 00:24:23,450
At kabuuan na, sa ngayon, tumatagal ang lugar ng aming mga max.

329
00:24:23,450 --> 00:24:28,100
Kino-compute namin ang maximum na bilang pumunta kami sa kahabaan.

330
00:24:28,100 --> 00:24:30,890
At kaya pumunta kami mula sa linear espasyo sa pare-pareho ang espasyo,

331
00:24:30,890 --> 00:24:36,650
at kami ay mayroon ding isang linear na solusyon sa aming subarray problema.

332
00:24:36,650 --> 00:24:40,740
>> Mga uri ng mga katanungan ay kang makakuha sa panahon ng isang pakikipanayam.

333
00:24:40,740 --> 00:24:44,450
Ano ang oras kumplikado, ano ang espasyo kumplikado?

334
00:24:44,450 --> 00:24:50,600
Maaari mong gawin mas mahusay? May mga bagay na hindi kinakailangang upang panatilihin sa paligid?

335
00:24:50,600 --> 00:24:55,270
Ginawa ko ito upang i-highlight ang mga pinag-aaralan na dapat mong gawin sa iyong sariling

336
00:24:55,270 --> 00:24:57,400
habang ikaw ay nagtatrabaho sa pamamagitan ng mga problemang ito.

337
00:24:57,400 --> 00:25:01,710
Laging humihiling sa iyong sarili, "Maaari ko bang gawin mas mahusay na?"

338
00:25:01,710 --> 00:25:07,800
Sa katunayan, maaari naming gawin mas mahusay kaysa sa ito?

339
00:25:07,800 --> 00:25:10,730
-Uri-uriin ng isang nanlilinlang tanong. Hindi ka maaari, dahil kailangan mo

340
00:25:10,730 --> 00:25:13,590
hindi bababa sa basahin ang input sa problema.

341
00:25:13,590 --> 00:25:15,570
Kaya ang katotohanan na kailangan mong hindi bababa sa basahin ang input sa problema

342
00:25:15,570 --> 00:25:19,580
nangangahulugan na hindi mo maaaring gawin mas mahusay kaysa sa linear oras,

343
00:25:19,580 --> 00:25:22,870
at hindi mo maaaring gawin mas mahusay kaysa sa pare-pareho ang espasyo.

344
00:25:22,870 --> 00:25:27,060
Kaya ito ay, sa katunayan, ang pinakamahusay na solusyon sa problemang ito.

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

346
00:25:33,040 --> 00:25:35,190
>> Problema sa merkado ng stock:

347
00:25:35,190 --> 00:25:38,350
"Dahil isang array ng n integer, positibo, zero, o negatibong,

348
00:25:38,350 --> 00:25:41,680
na kumakatawan sa presyo ng stock sa n araw,

349
00:25:41,680 --> 00:25:44,080
magsulat ng isang function upang makalkula ang pinakamataas na kita maaari mong gawin

350
00:25:44,080 --> 00:25:49,350
ibinigay na kang bumili at magbenta ng eksaktong 1 stock sa loob ng mga n araw. "

351
00:25:49,350 --> 00:25:51,690
Mahalaga, gusto naming bumili mababa, magbenta ng mataas.

352
00:25:51,690 --> 00:25:58,580
At gusto naming malaman ang pinakamahusay na kita na maaari kaming magsagawa ng.

353
00:25:58,580 --> 00:26:11,500
Pagpunta pabalik sa aking tip, ano ang agad na malinaw, ang pinakasimpleng sagot, ngunit ito ay mabagal?

354
00:26:11,500 --> 00:26:17,690
Oo? (Mag-aaral, hindi maintindihan) >> Oo.

355
00:26:17,690 --> 00:26:21,470
>> Kaya gusto mong pumunta lamang bagaman at tumingin sa mga presyo ng stock

356
00:26:21,470 --> 00:26:30,550
sa bawat punto sa oras, (hindi maintindihan).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, kaya ang kanyang solusyon - kanyang mungkahi ng computing

358
00:26:33,990 --> 00:26:37,380
ang pinakamababang at compute ang pinakamataas na ay hindi agad gumana

359
00:26:37,380 --> 00:26:42,470
dahil ang pinakamataas na maaaring maganap bago ang pinakamababang.

360
00:26:42,470 --> 00:26:47,340
Kaya kung ano ang taong malupit na puwersa solusyon sa problemang ito?

361
00:26:47,340 --> 00:26:53,150
Ano ang dalawang bagay na kailangan ko upang natatanging matukoy ang kita gumawa ako? Kanan.

362
00:26:53,150 --> 00:26:59,410
Ang taong malupit na puwersa solusyon - oh, kaya, George ng mungkahi kailangan lamang namin ng dalawang araw ng

363
00:26:59,410 --> 00:27:02,880
natatanging matukoy ang kita ng mga dalawang araw.

364
00:27:02,880 --> 00:27:06,660
Kaya compute namin ang bawat pares, i Bumibili / Nagpapalit,

365
00:27:06,660 --> 00:27:12,850
compute ang kita, na maaaring negatibong o positibong o zero.

366
00:27:12,850 --> 00:27:18,000
Compute ang maximum profit na ginawa namin pagkatapos iterating sa paglipas ng lahat ng mga pares ng mga araw.

367
00:27:18,000 --> 00:27:20,330
Na ang aming panghuling sagot.

368
00:27:20,330 --> 00:27:25,730
At ang solusyon na O (n ^ 2), dahil may n pumili ng dalawang pares -

369
00:27:25,730 --> 00:27:30,270
ng mga araw na maaari mong makapili sa mga araw ng pagtatapos.

370
00:27:30,270 --> 00:27:32,580
Okay, kaya hindi ako pagpunta sa pumunta sa ibabaw ng taong malupit na puwersa solusyon dito.

371
00:27:32,580 --> 00:27:37,420
Ako pagpunta sa sabihin sa iyo na may n solusyon log n.

372
00:27:37,420 --> 00:27:45,550
Ano algorithm ang kasalukuyan mong malaman na n log n?

373
00:27:45,550 --> 00:27:50,730
Hindi isang nanlilinlang tanong.

374
00:27:50,730 --> 00:27:54,790
>> Pagsamahin-uuri. Pagsamahin-uuri n log n

375
00:27:54,790 --> 00:27:57,760
at sa katunayan, ang isang paraan ng paglutas sa problemang ito ay upang gamitin ang

376
00:27:57,760 --> 00:28:04,400
isang uri ng pagsasama-uuri ng ideya na tinatawag na, sa pangkalahatan, hatiin at lupigin.

377
00:28:04,400 --> 00:28:07,570
At ideya ay ang mga sumusunod.

378
00:28:07,570 --> 00:28:12,400
Nais mong i-compute ang pinakamahusay na bumili / magbenta ng pares sa kaliwang kalahati.

379
00:28:12,400 --> 00:28:16,480
Hanapin ang pinakamahusay na kita na maaari mong gawin, sa mga unang n sa loob ng dalawang araw ng.

380
00:28:16,480 --> 00:28:19,780
Pagkatapos nais mong oompute ang pinakamahusay na bumili / magbenta ng pares sa kanang kalahati,

381
00:28:19,780 --> 00:28:23,930
kaya ang huling n sa loob ng dalawang araw ng.

382
00:28:23,930 --> 00:28:32,400
At ngayon ang tanong ay, kung paano namin sumanib pabalik ang mga solusyon na ito nang magkasama?

383
00:28:32,400 --> 00:28:36,320
Oo? (Mag-aaral, hindi maintindihan)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Kaya ipaalam sa akin gumuhit ng larawan.

385
00:28:49,890 --> 00:29:03,870
Oo? (George, hindi maintindihan)

386
00:29:03,870 --> 00:29:06,450
>> Mismong. Akmang-akma ang George ng solusyon.

387
00:29:06,450 --> 00:29:10,040
Kaya ang kanyang mungkahi ay, compute muna ang pinakamahusay na bumili / magbenta ng pares,

388
00:29:10,040 --> 00:29:16,050
at na nangyayari sa kaliwang kalahati, kaya sabihin tumawag na kaliwa, ang natitira.

389
00:29:16,050 --> 00:29:20,790
Pinakamahusay na bumili / magbenta ng pares na nangyayari sa kanang kalahati.

390
00:29:20,790 --> 00:29:25,180
Ngunit kung lamang namin kumpara ang dalawang numerong ito, kami ay Kulang ang kaso

391
00:29:25,180 --> 00:29:30,460
kung saan kami bumili dito at magbenta ng isang lugar sa kanang kalahati.

392
00:29:30,460 --> 00:29:33,810
Bumili kami sa kaliwang kalahati, ibenta sa kanang kalahati.

393
00:29:33,810 --> 00:29:38,490
At ang pinakamahusay na paraan upang makalkula ang pinakamahusay Bumibili / Nagpapalit pares na sumasaklaw ng parehong halves

394
00:29:38,490 --> 00:29:43,480
upang makalkula ang minimum dito at compute ang maximum dito

395
00:29:43,480 --> 00:29:45,580
at dalhin ang kanilang mga pagkakaiba.

396
00:29:45,580 --> 00:29:50,850
Kaya ang dalawang mga kaso na kung saan ang Bumibili / Nagpapalit pares nangyayari lamang dito,

397
00:29:50,850 --> 00:30:01,910
lamang dito, o sa parehong halves ay tinukoy sa pamamagitan ng mga tatlong numero.

398
00:30:01,910 --> 00:30:06,450
Kaya ang aming algorithm upang sumanib ang aming mga solusyon pabalik sama-sama,

399
00:30:06,450 --> 00:30:08,350
gusto naming upang makalkula ang pinakamahusay na bumili / magbenta ng pares

400
00:30:08,350 --> 00:30:13,120
kung saan kami bumili sa kaliwang kalahati at magbenta sa tamang kalahati.

401
00:30:13,120 --> 00:30:16,740
At ang pinakamahusay na paraan upang gawin iyon ay upang makalkula ang pinakamababang presyo sa unang kalahati,

402
00:30:16,740 --> 00:30:20,360
ang pinakamataas na presyo sa kanang kalahati, at kanilang mga pagkakaiba.

403
00:30:20,360 --> 00:30:25,390
Ang resultang tatlong kita, ang tatlong numero, kukuha ka ng hanggang sa tatlong,

404
00:30:25,390 --> 00:30:32,720
at na ang pinakamahusay na kita maaari kang magsagawa ng sa mga unang at end na mga araw.

405
00:30:32,720 --> 00:30:36,940
Narito ang mga mahalagang linya ng pula.

406
00:30:36,940 --> 00:30:41,160
Ito ay isang recursive tawag upang makalkula ang sagot sa kaliwang kalahati.

407
00:30:41,160 --> 00:30:44,760
Ito ay isang recursive tawag upang makalkula ang sagot sa kanang kalahati.

408
00:30:44,760 --> 00:30:50,720
Ang dalawang para sa loop compute ang min at ang max sa kaliwa at kanang kalahati, ayon sa pagkakasunud-sunod.

409
00:30:50,720 --> 00:30:54,970
Ngayon ko compute ang kita na sumasaklaw sa parehong halves,

410
00:30:54,970 --> 00:31:00,530
at ang panghuling sagot ay ang maximum na ang tatlong.

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

412
00:31:04,120 --> 00:31:06,420
>> Kaya, sigurado, mayroon kaming isang algorithm, ngunit ang mas malaking tanong ay,

413
00:31:06,420 --> 00:31:08,290
ano ang oras ng pagiging kumplikado ng mga ito?

414
00:31:08,290 --> 00:31:16,190
At ang dahilan kung bakit nabanggit ko ang pagsasama-uuri ay na ang form na ito ng hatiin ang sagot

415
00:31:16,190 --> 00:31:19,200
sa dalawang at pagkatapos ay pinagsasama ang aming mga solusyon pabalik sama-sama

416
00:31:19,200 --> 00:31:23,580
ay eksaktong paraan ng pagsasama-uuri.

417
00:31:23,580 --> 00:31:33,360
Kaya hayaan mo akong pumunta sa pamamagitan ng tagal.

418
00:31:33,360 --> 00:31:41,340
Kung tinukoy na namin ang isang function t (n) na ang bilang ng mga hakbang

419
00:31:41,340 --> 00:31:50,010
para sa mga n araw,

420
00:31:50,010 --> 00:31:54,350
aming dalawang recursive tawag

421
00:31:54,350 --> 00:32:00,460
ang bawat gastos t (n / 2),

422
00:32:00,460 --> 00:32:03,540
at may dalawa sa mga tawag na ito.

423
00:32:03,540 --> 00:32:10,020
Ngayon ay kailangan ko upang makalkula ang minimum na kaliwang kalahati,

424
00:32:10,020 --> 00:32:17,050
na maaari kong gawin sa n / 2 oras, pati na rin ang maximum na ng tamang kalahati.

425
00:32:17,050 --> 00:32:20,820
Kaya ito ay lamang n.

426
00:32:20,820 --> 00:32:25,050
At pagkatapos plus ilang pare-pareho sa trabaho.

427
00:32:25,050 --> 00:32:27,770
At pag-ulit equation na ito

428
00:32:27,770 --> 00:32:35,560
ay eksakto ang pag-ulit ng equation para sa pagsasama-uuri.

429
00:32:35,560 --> 00:32:39,170
At namin ang lahat ng alam na ang pagsasama-uuri n log n oras.

430
00:32:39,170 --> 00:32:46,880
Samakatuwid, ang aming mga algorithm ay din n log n oras.

431
00:32:46,880 --> 00:32:52,220
Ba ang pag-ulit na ito ay may kabuluhan?

432
00:32:52,220 --> 00:32:55,780
Isang maikling pagbabalik-tanaw ng mga ito:

433
00:32:55,780 --> 00:32:59,170
T (n) ay ang bilang ng mga hakbang upang makalkula ang pinakamataas na kita

434
00:32:59,170 --> 00:33:02,750
sa ibabaw ng kurso ng n araw.

435
00:33:02,750 --> 00:33:06,010
Ang paraan namin hatiin aming mga recursive tawag

436
00:33:06,010 --> 00:33:11,980
sa pamamagitan ng pagtawag sa aming mga solusyon sa unang araw n / 2,

437
00:33:11,980 --> 00:33:14,490
kaya na isang tawag,

438
00:33:14,490 --> 00:33:16,940
at pagkatapos ay tinatawag naming muli sa ikalawang kalahati.

439
00:33:16,940 --> 00:33:20,440
Kaya na ang dalawang tawag.

440
00:33:20,440 --> 00:33:25,310
At pagkatapos ay nakita namin isang minimum na sa kaliwang kalahati, na maaari naming gawin sa linear oras,

441
00:33:25,310 --> 00:33:29,010
hanapin ang maximum ng kanang kalahati, na maaari naming gawin sa linear oras.

442
00:33:29,010 --> 00:33:31,570
Kaya n / 2 + n / 2 lamang n.

443
00:33:31,570 --> 00:33:36,020
Pagkatapos kami ay may ilang mga pare-pareho ang trabaho, na tulad ng ginagawa aritmetika.

444
00:33:36,020 --> 00:33:39,860
Ang pag-ulit equation na ito ay eksakto ang pag-ulit ng equation para sa pagsasama-uuri.

445
00:33:39,860 --> 00:33:55,490
Samakatuwid, ang aming algorithm sa shuffle din n log n.

446
00:33:55,490 --> 00:33:58,520
Kaya kung magkano ang space ay namin ginagamit?

447
00:33:58,520 --> 00:34:04,910
Natin bumalik sa code.

448
00:34:04,910 --> 00:34:09,420
>> Ang isang mas mahusay na tanong ay, kung gaano karaming mga stack frame namin sa anumang naibigay na sandali?

449
00:34:09,420 --> 00:34:11,449
Dahil kami ay gamit ng recursion,

450
00:34:11,449 --> 00:34:23,530
ang bilang ng mga frame ng stack ay tumutukoy sa paggamit ng aming espasyo.

451
00:34:23,530 --> 00:34:29,440
Natin isaalang-alang ang n = 8.

452
00:34:29,440 --> 00:34:36,889
Tinatawag namin ang shuffle sa 8,

453
00:34:36,889 --> 00:34:41,580
na tawagan ang shuffle sa unang apat na entry,

454
00:34:41,580 --> 00:34:46,250
na tumawag ng shuffle sa unang dalawang entry.

455
00:34:46,250 --> 00:34:51,550
Kaya ang aming stack ay - ito ang aming stack.

456
00:34:51,550 --> 00:34:54,980
At pagkatapos ay tinatawag naming shuffle muli sa 1,

457
00:34:54,980 --> 00:34:58,070
at iyon ang kung ano ang aming base kaso ay, kaya namin bumalik agad.

458
00:34:58,070 --> 00:35:04,700
Namin ay may higit pa kaysa sa mga ito maraming stack frame?

459
00:35:04,700 --> 00:35:08,880
No Dahil sa bawat oras na gawin namin ng pananalangin,

460
00:35:08,880 --> 00:35:10,770
isang recursive na pananalangin sa shuffle,

461
00:35:10,770 --> 00:35:13,950
hinati namin ang aming laki sa kalahati.

462
00:35:13,950 --> 00:35:17,020
Kaya ang maximum na bilang ng mga frame ng stack namin sa anumang naibigay na sandali

463
00:35:17,020 --> 00:35:28,460
sa pagkakasunud-sunod ng mga log n stack frame.

464
00:35:28,460 --> 00:35:42,460
Bawat stack frame ay may pare-pareho na espasyo,

465
00:35:42,460 --> 00:35:44,410
at samakatuwid ay ang kabuuang halaga ng espasyo,

466
00:35:44,410 --> 00:35:49,240
ang maximum na halaga ng puwang namin ginagamit O (log n) espasyo

467
00:35:49,240 --> 00:36:03,040
kung saan ang n ay ang bilang ng mga araw.

468
00:36:03,040 --> 00:36:07,230
>> Ngayon, palaging tanungin ang inyong sarili, "Maaari ba kaming gawin mas mahusay na?"

469
00:36:07,230 --> 00:36:12,390
At sa partikular, maaari naming bawasan ito sa isang problema na namin na malutas?

470
00:36:12,390 --> 00:36:20,040
Isang pahiwatig: lamang namin tinalakay ng dalawang iba pang mga problema bago ito, at hindi ito pagpunta sa shuffle.

471
00:36:20,040 --> 00:36:26,200
Maaari naming i-convert ito problema sa merkado ng stock sa ang pinakamalaki subarray problema.

472
00:36:26,200 --> 00:36:40,100
Paano namin gawin ito?

473
00:36:40,100 --> 00:36:42,570
Isa mo? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Kaya ang pinakamalaki subarray problema,

477
00:36:59,940 --> 00:37:10,610
kaming naghahanap ng para sa isang kabuuan sa isang tuloy-tuloy na subarray.

478
00:37:10,610 --> 00:37:16,230
At Emmy mungkahi para sa mga problema ng mga stock,

479
00:37:16,230 --> 00:37:30,720
isaalang-alang ang mga pagbabago, o ang mga deltas.

480
00:37:30,720 --> 00:37:37,440
At ang isang larawan na ito ay - ito ay ang presyo ng stock,

481
00:37:37,440 --> 00:37:42,610
ngunit kung kinuha namin ang pagkakaiba sa pagitan ng bawat magkakasunod na araw -

482
00:37:42,610 --> 00:37:45,200
kaya namin makita na ang maximum na presyo, maximum profit kami maaaring magsagawa ng

483
00:37:45,200 --> 00:37:50,070
kung bumili kami dito at magbenta dito.

484
00:37:50,070 --> 00:37:54,240
Ngunit tingnan natin sa tuloy-tuloy na - tingnan natin sa problema subarray.

485
00:37:54,240 --> 00:38:02,510
Kaya dito, maaari kaming magsagawa ng - pagpunta mula dito sa dito,

486
00:38:02,510 --> 00:38:08,410
mayroon kami ng positibong pagbabago, at pagkatapos ng pagpunta mula dito dito kami ay may isang negatibong pagbabago.

487
00:38:08,410 --> 00:38:14,220
Ngunit pagkatapos, pagpunta mula dito sa dito mayroon kaming isang malaking positibong pagbabago.

488
00:38:14,220 --> 00:38:20,930
At ito ay ang mga pagbabago na gusto namin upang ipahayag sa ilang kataga upang makakuha ng ang aming panghuling kita.

489
00:38:20,930 --> 00:38:25,160
Pagkatapos kami ay may higit pang mga negatibong mga pagbabago dito.

490
00:38:25,160 --> 00:38:29,990
Ang susi sa pagbabawas ng aming stock problema sa aming mga problema sa pinakamalaki subarray

491
00:38:29,990 --> 00:38:36,630
ay upang isaalang-alang ang mga deltas sa pagitan ng mga araw.

492
00:38:36,630 --> 00:38:40,630
Kaya namin lumikha ng isang bagong array na tinatawag deltas,

493
00:38:40,630 --> 00:38:43,000
initialize ang unang entry na 0,

494
00:38:43,000 --> 00:38:46,380
at pagkatapos ay para sa bawat delta (i), sabihin na ang pagkakaiba

495
00:38:46,380 --> 00:38:52,830
ng aking input array (i), at array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Pagkatapos tawagan namin ang aming nakagawiang pamamaraan para sa isang pinakamalaki subarray

497
00:38:55,530 --> 00:39:01,500
pagpasa sa isang delta ng array.

498
00:39:01,500 --> 00:39:06,440
At dahil ang pinakamalaki subarray linear oras,

499
00:39:06,440 --> 00:39:09,370
at ito pagbabawas, ang proseso ng paglikha ng ang delta array na ito,

500
00:39:09,370 --> 00:39:11,780
ding linear oras,

501
00:39:11,780 --> 00:39:19,060
pagkatapos ay ang panghuling solusyon para sa mga stock ay O (n) trabaho plus O (n) trabaho, pa rin ang O (n) na trabaho.

502
00:39:19,060 --> 00:39:23,900
Kaya mayroon kami ng linear oras solusyon sa aming problema.

503
00:39:23,900 --> 00:39:29,610
Ba ang lahat maunawaan ang pagbabago na ito?

504
00:39:29,610 --> 00:39:32,140
>> Sa pangkalahatan, ang isang magandang ideya na dapat palagi kang may

505
00:39:32,140 --> 00:39:34,290
ay subukan upang mabawasan ang isang bagong problema na nakakakita ka.

506
00:39:34,290 --> 00:39:37,700
Kung mukhang pamilyar sa isang lumang problema,

507
00:39:37,700 --> 00:39:39,590
subukang bawasan ito sa isang lumang problema.

508
00:39:39,590 --> 00:39:41,950
At kung maaari mong gamitin ang lahat ng mga tool na ginamit mo sa lumang problema

509
00:39:41,950 --> 00:39:46,450
upang malutas ang mga bagong problema.

510
00:39:46,450 --> 00:39:49,010
Kaya upang tapusin, teknikal na panayam ay hamon.

511
00:39:49,010 --> 00:39:52,280
Ang mga problemang ito ay marahil ilang ng mas mahirap na mga problema

512
00:39:52,280 --> 00:39:54,700
na maaari mong makita sa isang pakikipanayam,

513
00:39:54,700 --> 00:39:57,690
kaya kung hindi mo maunawaan ang lahat ng mga problema ko lang sakop, okay lang.

514
00:39:57,690 --> 00:40:01,080
Mga ito ay ilan sa ang mga mas mahirap na mga problema.

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

516
00:40:03,050 --> 00:40:08,170
Nagbigay ako ng maraming ng mga problema sa hand-awt, kaya tiyak na suriin ang mga out.

517
00:40:08,170 --> 00:40:11,690
At good luck sa iyong mga panayam. Lahat ng aking mga mapagkukunan ay nai-post sa link na ito,

518
00:40:11,690 --> 00:40:15,220
at isa ng aking mga kaibigan sa senior ay inaalok sa gawin ng mga kunwaring mga teknikal na panayam,

519
00:40:15,220 --> 00:40:22,050
kaya kung interesado ka, email Will Yao sa email address na iyon.

520
00:40:22,050 --> 00:40:26,070
Kung mayroon kang ilang mga katanungan, maaari mong hilingin sa akin.

521
00:40:26,070 --> 00:40:28,780
Ka ba guys may partikular na mga tanong na may kaugnayan sa mga teknikal na panayam

522
00:40:28,780 --> 00:40:38,440
o anumang mga problema na nasaksihan namin sa ngayon?

523
00:40:38,440 --> 00:40:49,910
Okay. Well, good luck sa iyong mga panayam.

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