1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Mintegia: Elkarrizketak teknikoak]

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

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

4
00:00:08,910 --> 00:00:12,420
Kaixo guztioi, Kenny naiz. Gaur egun, I am ikasten informatika junior.

5
00:00:12,420 --> 00:00:17,310
CS TF ohia naiz, eta hau izan nuen, underclassman bat izan dut nahi dut,

6
00:00:17,310 --> 00:00:19,380
eta hori zergatik mintegi hau ematen dut.

7
00:00:19,380 --> 00:00:21,370
Beraz, gozatzeko aukera izatea espero dut.

8
00:00:21,370 --> 00:00:23,470
Mintegia hau tekniko buruzko elkarrizketak da,

9
00:00:23,470 --> 00:00:26,650
eta nire baliabide guztiak esteka honetan aurki daitezke,

10
00:00:26,650 --> 00:00:32,350
eskubide hau hemen baliabide pare bat.

11
00:00:32,350 --> 00:00:36,550
Beraz, arazoak zerrenda bat egin dut, egia esan, nahiko arazo gutxi.

12
00:00:36,550 --> 00:00:40,800
Halaber, oro har, baliabide orrialdean non aholku aurki ditzakegu

13
00:00:40,800 --> 00:00:42,870
nola prestatu elkarrizketa bat,

14
00:00:42,870 --> 00:00:46,470
zer egin behar duzu benetako elkarrizketa zehar aholkuak,

15
00:00:46,470 --> 00:00:51,910
eta baita nola arazoak eta baliabideak etorkizunean erreferentzia hurbiltzeko.

16
00:00:51,910 --> 00:00:53,980
Da online.

17
00:00:53,980 --> 00:00:58,290
Eta, besterik ez, mintegi honetan, lege oharra Prólogo,

18
00:00:58,290 --> 00:01:00,690
atsegin dute hau egin beharko lukete ez - zure elkarrizketa prestatzeko

19
00:01:00,690 --> 00:01:02,800
ez litzateke zerrenda honetan mugatuta dago.

20
00:01:02,800 --> 00:01:04,750
Hori bakarrik esan nahi du gida bat izan nahi,

21
00:01:04,750 --> 00:01:08,890
eta behin betiko hartu behar duzu, gatz ale bat esaten dut dena,

22
00:01:08,890 --> 00:01:14,620
baina ere erabili guztia lagunduko dizu zure elkarrizketa prestatzeko erabiltzen dut.

23
00:01:14,620 --> 00:01:16,400
>> Abiadura noa datozen diapositiba bidez

24
00:01:16,400 --> 00:01:18,650
beraz, benetako kasu praktikoak eskuratu ahal izango dugu.

25
00:01:18,650 --> 00:01:23,630
Software ingeniaritza postion elkarrizketa baten egitura,

26
00:01:23,630 --> 00:01:26,320
normalean, 30 eta 45 minutu da.

27
00:01:26,320 --> 00:01:29,810
erronda bat baino gehiago, enpresaren arabera.

28
00:01:29,810 --> 00:01:33,090
Askotan zuri-taula duzu kodifikazioa.

29
00:01:33,090 --> 00:01:35,960
Hau atsegin dute, baina askotan, neurri txikiagoan taula zuri bat, beraz.

30
00:01:35,960 --> 00:01:38,540
Ari zaren telefono-elkarrizketa bat izanez gero, ziurrenik duzu erabiliz

31
00:01:38,540 --> 00:01:44,030
bai collabedit edo Google Doc ikus daitezke kodeketa bizi zaren

32
00:01:44,030 --> 00:01:46,500
zu ari den bitartean, telefonoz elkarrizketatu.

33
00:01:46,500 --> 00:01:48,490
Elkarrizketa bat bera da, normalean 2 edo 3 arazo

34
00:01:48,490 --> 00:01:50,620
zure informatika ezagutza probatzeko.

35
00:01:50,620 --> 00:01:54,490
Eta ia behin betiko izango da inplikatzeko kodifikazioa.

36
00:01:54,490 --> 00:01:59,540
Galdera mota egingo ikusten izan ohi dira Datu-egitura eta algoritmoak.

37
00:01:59,540 --> 00:02:02,210
Eta mota horiek egiteko arazoak,

38
00:02:02,210 --> 00:02:07,830
eskatuko dizu dute, bezala, denbora eta espazioaren konplexutasuna, big O zer da?

39
00:02:07,830 --> 00:02:09,800
Sarritan eskatu ere, goi-maila galderak,

40
00:02:09,800 --> 00:02:12,530
beraz, sistema bat diseinatu,

41
00:02:12,530 --> 00:02:14,770
nola arautuko zure kodea?

42
00:02:14,770 --> 00:02:18,370
Zer interfaces, zer klaseak, zer modulu egin behar zure sisteman,

43
00:02:18,370 --> 00:02:20,900
eta nola horiek elkarreragin elkarrekin?

44
00:02:20,900 --> 00:02:26,130
Beraz, datu egiturak eta algoritmoak diseinatzeko sistemak, baita.

45
00:02:26,130 --> 00:02:29,180
>> Aholku batzuk gure kasuan ikasketak murgiltze aurretik.

46
00:02:29,180 --> 00:02:32,300
Arau garrantzitsuena da beti pentsatzen ozen uste dut.

47
00:02:32,300 --> 00:02:36,980
Zure pentsamendu-prozesu off erakusteko aukera izango da, ustezko elkarrizketa.

48
00:02:36,980 --> 00:02:39,820
Erreportajearen puntua da elkarrizketatzaileak neurtzeko

49
00:02:39,820 --> 00:02:42,660
nola pentsatzen duzun eta nola arazo baten bitartez.

50
00:02:42,660 --> 00:02:45,210
Egin ahal izango duzu gauza txarrena da isila elkarrizketa osoan zehar.

51
00:02:45,210 --> 00:02:50,090
Hori besterik ez da ez ona.

52
00:02:50,090 --> 00:02:53,230
Duzunean galdera bat eman ere, nahi duzun galdera ulertzen ziur egiteko.

53
00:02:53,230 --> 00:02:55,350
Beraz, galdera errepikatu zure hitzetan

54
00:02:55,350 --> 00:02:58,920
eta saiakera sakon bat erraz batzuk test kasu lan egiteko

55
00:02:58,920 --> 00:03:01,530
Ziur galdera ulertzen.

56
00:03:01,530 --> 00:03:05,510
Test batzuk kasu bidez lan egiten du, halaber, arazo hau nola konpondu intuizio bat emango dizu.

57
00:03:05,510 --> 00:03:11,210
Batzuk eredu bat ere aurkituko dezakezu arazoa konpontzeko laguntzeko.

58
00:03:11,210 --> 00:03:14,500
Bere big tip ez da zapuztu.

59
00:03:14,500 --> 00:03:17,060
Ez zaitez zapuztu.

60
00:03:17,060 --> 00:03:19,060
Elkarrizketak zaila, baina egin dezakezu gauzarik txarrena,

61
00:03:19,060 --> 00:03:23,330
isila izateaz gain, nabarmen behar zapuztuta.

62
00:03:23,330 --> 00:03:27,410
Ez duzu nahi inpresioa ematen dioten elkarrizketa bat.

63
00:03:27,410 --> 00:03:33,960
Gauza bat - beraz, jende askok eta askok, joan elkarrizketa bat sartzen dira,

64
00:03:33,960 --> 00:03:37,150
konponbide onena aurkitzeko lehen saiatu saiatzen dira,

65
00:03:37,150 --> 00:03:39,950
denean, benetan, ez da normalean glaringly bistako irtenbide bat.

66
00:03:39,950 --> 00:03:43,500
Motela izango da agian, eraginkorra izan daiteke, baina besterik ez behar duzu aipatu,

67
00:03:43,500 --> 00:03:46,210
beraz, hobeto lan egiteko abiapuntua besterik ez duzu.

68
00:03:46,210 --> 00:03:48,270
Era berean, konponbidea seinalatuz motela da, termino

69
00:03:48,270 --> 00:03:52,160
big O denbora konplexutasuna edo espazio konplexutasuna,

70
00:03:52,160 --> 00:03:54,450
ulertzen duzu elkarrizketatzaileak erakusteko

71
00:03:54,450 --> 00:03:57,510
gai horiek kodea idatziz.

72
00:03:57,510 --> 00:04:01,440
Beraz, ez izan beldurrik errazena algoritmoa lehen

73
00:04:01,440 --> 00:04:04,950
eta, ondoren, lan hobea bertatik.

74
00:04:04,950 --> 00:04:09,810
Edozein galdera, beraz, orain arte? Ongi da.

75
00:04:09,810 --> 00:04:11,650
>> Hargatik gure arazoa lehen murgiltzea.

76
00:04:11,650 --> 00:04:14,790
"N zenbaki osoen array bat, array shuffles funtzio bat idatzi

77
00:04:14,790 --> 00:04:20,209
lekua, hala nola, n osoko zenbakien permutazio guztiak dira berdin litekeena. "

78
00:04:20,209 --> 00:04:23,470
Eta bere gain hartzen duzu eskuragarri zenbaki bat ausazko generator

79
00:04:23,470 --> 00:04:30,980
barruti bat zenbaki oso bat sortzen 0-tik i, erdi-sorta.

80
00:04:30,980 --> 00:04:32,970
Denek ulertzen ez du galdera hau?

81
00:04:32,970 --> 00:04:39,660
N zenbaki osoen array bat ematen dizut, eta nahastu du nahi dut.

82
00:04:39,660 --> 00:04:46,050
Nire direktorioa, zer esan nahi dut erakusteko programa bat gutxi idatzi nuen.

83
00:04:46,050 --> 00:04:48,910
20 elementu array bat nahastu noa,

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

85
00:04:52,490 --> 00:04:57,050
eta hau atsegin zerrenda bat bistaratu nahi dut.

86
00:04:57,050 --> 00:05:02,890
Beraz, hau da nire sarrera array ordenatuko da, eta nahastu du nahi dut.

87
00:05:02,890 --> 00:05:07,070
Egin dugu berriro.

88
00:05:07,070 --> 00:05:13,780
Denek ulertu galdera? Ongi da.

89
00:05:13,780 --> 00:05:16,730
Beraz, sortu da.

90
00:05:16,730 --> 00:05:21,220
Zer dira ideia batzuk? Ezin da egin n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Iradokizunak Ireki.

92
00:05:34,400 --> 00:05:37,730
Ongi da. Beraz, ideia, Emmy iradokitako

93
00:05:37,730 --> 00:05:45,300
da lehen compute ausazko zenbaki bat, ausazko zenbaki oso, tarte bat 0-tik 20.

94
00:05:45,300 --> 00:05:49,840
Beraz gure array 20 luzera du.

95
00:05:49,840 --> 00:05:54,800
Gure 20 elementu diagrama,

96
00:05:54,800 --> 00:05:58,560
hau da, gure sarrera array da.

97
00:05:58,560 --> 00:06:04,590
Eta orain, bere iradokizun array berri bat sortzeko,

98
00:06:04,590 --> 00:06:08,440
beraz, hau izango da irteera array.

99
00:06:08,440 --> 00:06:12,880
Eta itzuli aus i oinarritutako

100
00:06:12,880 --> 00:06:17,580
beraz, izan zen i, demagun, 17,

101
00:06:17,580 --> 00:06:25,640
lehen posizioan sartu kopiatu elementu 17an.

102
00:06:25,640 --> 00:06:30,300
Orain ezabatu behar dugu, elementu guztiak mugitzeko behar dugu hemen

103
00:06:30,300 --> 00:06:36,920
beraz gainean amaieran hutsune bat eta erdian zulo ez dugula.

104
00:06:36,920 --> 00:06:39,860
Eta orain, prozesua errepikatu dugu.

105
00:06:39,860 --> 00:06:46,360
Ausazko zenbaki oso berri bat 0 eta 19 artean hautatzeko orain dugu.

106
00:06:46,360 --> 00:06:52,510
I berri bat izan dugu hemen, eta elementu hau kopiatu dugu jarrera hori.

107
00:06:52,510 --> 00:07:00,960
Ondoren, elementu filmea dugu eta gehiagoko prozesua errepikatu ditugu gure berri array arte.

108
00:07:00,960 --> 00:07:05,890
Zer da algoritmo hau denbora run?

109
00:07:05,890 --> 00:07:08,110
Beno, dezagun honen eragina kontuan hartu.

110
00:07:08,110 --> 00:07:10,380
Elementu aldatzearen behin ari gara.

111
00:07:10,380 --> 00:07:16,800
Hori kendu dugu i, elementu guztiak ari gara aldatzearen ondoren ezkerrera.

112
00:07:16,800 --> 00:07:21,600
Eta hori O (n) kostua

113
00:07:21,600 --> 00:07:26,100
zer delako lehenengo elementu ezabatu badugu?

114
00:07:26,100 --> 00:07:29,670
Beraz kentzea bakoitzean, kendu

115
00:07:29,670 --> 00:07:32,170
kentzea bakoitzean bat O (n) eragiketa incurs

116
00:07:32,170 --> 00:07:41,520
dugu eta kentzeko n geroztik, hau bat O (n ^ 2) nahastu eramaten du.

117
00:07:41,520 --> 00:07:49,550
Ongi da. Irteeran onak. Good Irteeran.

118
00:07:49,550 --> 00:07:55,290
>> Iradokizun bat da, zerbait Knuth nahastu bezala ezagutzen erabili,

119
00:07:55,290 --> 00:07:57,540
edo Fisher-Yates nahastu.

120
00:07:57,540 --> 00:07:59,630
Eta benetan lineal bat da, denbora nahastu.

121
00:07:59,630 --> 00:08:02,200
Eta ideia oso antzekoa da.

122
00:08:02,200 --> 00:08:05,160
Berriz ere, gure sarrera array dugu,

123
00:08:05,160 --> 00:08:08,580
baina bi array erabiliz gure sarrera / irteera ordez,

124
00:08:08,580 --> 00:08:13,590
array lehen zati erabiltzen ditugu gure zati nahastu segimendua egiteko,

125
00:08:13,590 --> 00:08:18,400
eta jarraipena dugu, eta, ondoren, gure array gainerako utziko dugu unshuffled zati.

126
00:08:18,400 --> 00:08:24,330
Hortaz, hona hemen zer esan nahi dut. Hasiko gara - i bat aukeratu dugu,

127
00:08:24,330 --> 00:08:30,910
0-tik 20 array bat.

128
00:08:30,910 --> 00:08:36,150
Gure gaur egungo erakuslea da lehenengo indizea seinalatuz.

129
00:08:36,150 --> 00:08:39,590
I hemen batzuk aukeratzen ditugu

130
00:08:39,590 --> 00:08:42,740
eta gaur egun trukatzeko.

131
00:08:42,740 --> 00:08:47,690
Beraz, bada, 5 izan zen, eta hau izan zen 4.

132
00:08:47,690 --> 00:08:57,150
ondorioz array 4 5 Hemen eta hemen izango dute.

133
00:08:57,150 --> 00:09:00,390
Eta orain, markatzaile bat kontutan izan dugu hemen.

134
00:09:00,390 --> 00:09:05,770
Ezkerraldean Dena nahastu,

135
00:09:05,770 --> 00:09:15,160
eta eskubidea dena unshuffled.

136
00:09:15,160 --> 00:09:17,260
Eta orain, prozesua errepikatu ahal izango dugu.

137
00:09:17,260 --> 00:09:25,210
1 eta 20 arteko indizea ausazko gaur egun bat aukeratzen dugu.

138
00:09:25,210 --> 00:09:30,650
Beraz, demagun gure berri hemen da i.

139
00:09:30,650 --> 00:09:39,370
Orain i hau swap dugu gure gaur egungo egoera berria hemen.

140
00:09:39,370 --> 00:09:44,790
Beraz, ez dugu atzera eta aurrera aldaketa hau atsegin dute.

141
00:09:44,790 --> 00:09:51,630
Dezagun ekarri me kodea hormigoizko gehiago egin.

142
00:09:51,630 --> 00:09:55,290
Hasten dugu gure i aukeratu -

143
00:09:55,290 --> 00:09:58,370
0 i berdinak hasten gara, ausazko kokaleku j jaso dugu

144
00:09:58,370 --> 00:10:02,420
array unshuffled zatia, n-1 i.

145
00:10:02,420 --> 00:10:07,280
Hemen nago, aukeratu hemen eta gainerako array arteko indize ausazko

146
00:10:07,280 --> 00:10:12,410
eta trukatzeko.

147
00:10:12,410 --> 00:10:17,550
Kodea zure array Nahastu beharrezkoa da.

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

149
00:10:21,670 --> 00:10:25,530
>> Beno, galdera behar bat da, zergatik zuzena hau da?

150
00:10:25,530 --> 00:10:28,360
Zergatik da permutazio bakoitzean bereko?

151
00:10:28,360 --> 00:10:30,410
Eta ez dut horren froga bidez,

152
00:10:30,410 --> 00:10:35,970
baina informatika arazo ugari indukzio frogatu daiteke.

153
00:10:35,970 --> 00:10:38,520
Nola asko dira indukzio ezagutzen?

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

155
00:10:40,590 --> 00:10:43,610
Algoritmo honen zuzentasuna indukzio simple Beraz, frogatu ahal izango duzu,

156
00:10:43,610 --> 00:10:49,540
non zure indukzio-hipotesia litzateke, bere gain hartzen duten

157
00:10:49,540 --> 00:10:53,290
nire nahastu itzultzen behin permutazio bereko

158
00:10:53,290 --> 00:10:56,120
lehen i elementuak.

159
00:10:56,120 --> 00:10:58,300
Orain, kontuan hartu i + 1.

160
00:10:58,300 --> 00:11:02,550
Eta gure indizea j swap aukeratu dugu,

161
00:11:02,550 --> 00:11:05,230
hau dakar, eta, ondoren, lan xehetasunak

162
00:11:05,230 --> 00:11:07,390
gutxienez, algoritmo hau zergatik itzultzen froga osoa

163
00:11:07,390 --> 00:11:12,800
probabilitate bereko permutazio bakoitzean.

164
00:11:12,800 --> 00:11:15,940
>> Guztiak eskubidea, hurrengo arazoa.

165
00:11:15,940 --> 00:11:19,170
Beraz, "Emandako zenbaki osoen array, postive, zero, negatiboa,

166
00:11:19,170 --> 00:11:21,290
gehienez batura kalkulatzen duen funtzio bat idatzi

167
00:11:21,290 --> 00:11:24,720
sarrera array continueous subarray edozein ".

168
00:11:24,720 --> 00:11:28,370
Adibide bat hemen da, non zenbaki guztiak positiboak dira kasuan,

169
00:11:28,370 --> 00:11:31,320
ondoren, gaur egun, aukerarik onena da array osoa hartzeko.

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

171
00:11:34,690 --> 00:11:36,780
Negatibo batzuk bertan,

172
00:11:36,780 --> 00:11:38,690
Kasu honetan, nahi dugu lehen bi

173
00:11:38,690 --> 00:11:44,590
-1 eta / edo -3 aukeratzeagatik duelako gure batura jarriko du behera.

174
00:11:44,590 --> 00:11:48,120
Batzuetan, array-erdian hasten gara dezake.

175
00:11:48,120 --> 00:11:53,500
Batzuetan, ezer ez guztietan aukeratu nahi dugu, hobe da ezer ez dute.

176
00:11:53,500 --> 00:11:56,490
Eta batzuetan, hobe da jaitsiera,

177
00:11:56,490 --> 00:12:07,510
ondoren gauza super handi delako. Ideiak edozein Beraz?

178
00:12:07,510 --> 00:12:10,970
(Ikaslea, ulertezina) >> Bai.

179
00:12:10,970 --> 00:12:13,560
Demagun ez dut hartu -1.

180
00:12:13,560 --> 00:12:16,170
Gero bai, 1.000 eta 20.000 aukeratu dut,

181
00:12:16,170 --> 00:12:18,630
edo hautatu dut 3 milioi.

182
00:12:18,630 --> 00:12:20,760
Beno, aukerarik onena da zenbaki guztiak hartu.

183
00:12:20,760 --> 00:12:24,350
-1, Negatiboak izan arren,

184
00:12:24,350 --> 00:12:31,340
batura osoa da hobea baino ez dut -1 hartzeko.

185
00:12:31,340 --> 00:12:36,460
Beraz, aholkuak lehenago aipatu dut bat izan zen argi eta garbi bistako adieraziko

186
00:12:36,460 --> 00:12:40,540
eta brute indarrean aurreneko irtenbidea.

187
00:12:40,540 --> 00:12:44,340
Zer da arazo hau indarrean brute irtenbidea? Bai?

188
00:12:44,340 --> 00:12:46,890
[Jane] Beno, uste dut brute indarrean irtenbide

189
00:12:46,890 --> 00:12:52,600
gehitu konbinazio posible guztiak (ulertezina) izango litzateke.

190
00:12:52,600 --> 00:12:58,250
[Yu] Larreina. Beraz, Jane ideia da posible guztiak hartzeko

191
00:12:58,250 --> 00:13:01,470
Parafraseatuz naiz da eta ahalik eta etengabeko subarray bakoitzean hartu,

192
00:13:01,470 --> 00:13:07,840
konputatzeko bere batura, eta gero, etengabeko posible guztiak subarrays gehienezko hartu.

193
00:13:07,840 --> 00:13:13,310
Zer bakarrean subarray bat identifikatzen nire sarrerako array?

194
00:13:13,310 --> 00:13:17,380
Bezala, zer bi gauza egin behar dut? Bai?

195
00:13:17,380 --> 00:13:19,970
(Ikaslea, ulertezina) >> eskubidea.

196
00:13:19,970 --> 00:13:22,130
A txikiagoa indize eta goi-koadernatuta indizea lotuak

197
00:13:22,130 --> 00:13:28,300
bakarrean etengabeko subarray bat zehazten du.

198
00:13:28,300 --> 00:13:31,400
[Emakumezkoak ikaslea] estimatzea zenbaki berezia da array bat da?

199
00:13:31,400 --> 00:13:34,280
[Yu] N º Beraz, bere galdera da, ari suposatuz gure array dugu

200
00:13:34,280 --> 00:13:39,000
gure array berezia zenbakiak da, eta erantzuna ez da.

201
00:13:39,000 --> 00:13:43,390
>> Erabili dugu gure brute indarrean konponbidea, ondoren, hasiera / amaiera indizeak

202
00:13:43,390 --> 00:13:47,200
bakarrean, gure etengabeko subarray zehazten du.

203
00:13:47,200 --> 00:13:51,680
Beraz, batetik bestera joateko Irteeran posible sarrerak dugu,

204
00:13:51,680 --> 00:13:58,320
eta azken sarrera guztiak> edo =, hasteko eta <n

205
00:13:58,320 --> 00:14:05,570
batura kalkulatzeko, eta, ondoren, ikusi dugu, orain arte, gehienez batura hartuko dugu.

206
00:14:05,570 --> 00:14:07,880
Hau argi eta garbi?

207
00:14:07,880 --> 00:14:12,230
Zer da O big irtenbide hau?

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

209
00:14:16,660 --> 00:14:18,860
Ez da nahiko n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Kontuan 0-tik n batetik bestera joateko,

211
00:14:25,250 --> 00:14:27,520
beraz, loop bat da.

212
00:14:27,520 --> 00:14:35,120
Batetik bestera joateko dugu berriro ia hasieratik amaierara arte, beste begizta.

213
00:14:35,120 --> 00:14:37,640
Eta gaur egun, horren barruan, sarrera bakoitzean laburbildu dugu,

214
00:14:37,640 --> 00:14:43,810
beraz, beste begizta. Beraz, hiru begiztak for habiaratuak, n ^ 3 dugu.

215
00:14:43,810 --> 00:14:46,560
Ongi da. Abiapuntu gisa doa.

216
00:14:46,560 --> 00:14:53,180
Gure soluzioa ez n ^ 3 baino okerrago.

217
00:14:53,180 --> 00:14:55,480
Denek ulertu brute indarrean irtenbidea?

218
00:14:55,480 --> 00:14:59,950
>> Ongi da. Konponbide bat hobea dinamikoa programazio izeneko ideia bat erabiltzen ari da.

219
00:14:59,950 --> 00:15:03,040
Hartu duzu CS124 bada, eta Algoritmoak eta Datu Egiturak

220
00:15:03,040 --> 00:15:05,680
teknika hau oso ezaguna bihurtu ahal izango duzu.

221
00:15:05,680 --> 00:15:12,190
Eta ideia da, eta saiatu konponbideak eraikitzeko txikiagoa arazoak lehen aldiz.

222
00:15:12,190 --> 00:15:17,990
Zer esan nahi dut, hau da, gaur egun dugun bi gauza kezkatu: hasieran eta amaieran.

223
00:15:17,990 --> 00:15:29,340
Eta hori da gogaikarriak. Zer parametro horietako bat kentzeko bada ezin izan gara?

224
00:15:29,340 --> 00:15:32,650
We're gure jatorrizko arazoa kontuan hartuta, - ideia bat da.

225
00:15:32,650 --> 00:15:37,470
gehienezko barruti bat edozein subarray batura [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Eta orain berri bat subproblem, non gauden jakin behar dugu, gaur egungo gure indizea i,

227
00:15:47,400 --> 00:15:52,520
badakigu ez ondorioztatu behar dugu. Uneko indizea Gure subarray behar amaituko da.

228
00:15:52,520 --> 00:15:57,640
Gainerako arazoa da Beraz, non behar gure subarray hasteko dugu?

229
00:15:57,640 --> 00:16:05,160
Ba al du zentzurik? Ongi da.

230
00:16:05,160 --> 00:16:12,030
Beraz, kodetu Nik, hau, eta dezagun zer esan nahi hau begiratu.

231
00:16:12,030 --> 00:16:16,230
: Codirectory da, ez dago subarray izeneko programa bat da,

232
00:16:16,230 --> 00:16:19,470
eta elementu kopurua hartzen du,

233
00:16:19,470 --> 00:16:25,550
eta subarray batura maximoa itzultzen du nire zerrenda nahastu.

234
00:16:25,550 --> 00:16:29,920
Beraz, kasu honetan, gure subarray maximoa 3.

235
00:16:29,920 --> 00:16:34,850
Eta hori besterik ez, 2 eta 1 erabiliz hartu.

236
00:16:34,850 --> 00:16:38,050
Dezagun exekutatu berriro. Gainera, 3.

237
00:16:38,050 --> 00:16:40,950
Baina une honetan, kontutan izan nola 3 genuen.

238
00:16:40,950 --> 00:16:46,690
Hartu genuen hartu besterik ez dugu 3 bera

239
00:16:46,690 --> 00:16:49,980
eta negatiboak delako inguratuta bi aldeetan,

240
00:16:49,980 --> 00:16:55,080
batura bat ekarriko du, <3.

241
00:16:55,080 --> 00:16:57,820
Dezagun 10 elementuak exekutatzeko.

242
00:16:57,820 --> 00:17:03,200
Oraingo honetan 7 da, liderra 3 eta 4. Hartuko dugu.

243
00:17:03,200 --> 00:17:09,450
Oraingo honetan 8 da, eta 1, 4 eta 3 hartu lortuko dugu.

244
00:17:09,450 --> 00:17:16,310
Beraz, nola intuizioa emateko eraldatu arazo hau konpondu ahal izango dugu,

245
00:17:16,310 --> 00:17:18,890
dezagun subarray honetan begirada bat.

246
00:17:18,890 --> 00:17:23,460
Emandako sarrera array hau gara, eta badakigu erantzuna 8.

247
00:17:23,460 --> 00:17:26,359
1, 4, eta 3 hartuko dugu.

248
00:17:26,359 --> 00:17:29,090
Baina nola lortu benetan erantzuna begiratu.

249
00:17:29,090 --> 00:17:34,160
Maximoa duen indize horietako bakoitzean subarray amaitu.

250
00:17:34,160 --> 00:17:40,780
Zer da maximoa subarray duen lehen posizioan bukatzen da?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Just ez hartu -5.

252
00:17:46,310 --> 00:17:50,210
0 izango baita egingo. Bai?

253
00:17:50,210 --> 00:17:56,470
(Ikaslea, ulertezina)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, barkatu, -3 da.

255
00:17:58,960 --> 00:18:03,220
2 Beraz, -3 da.

256
00:18:03,220 --> 00:18:08,690
Ongi da. Beraz, -4, zer maximoa subarray posizio hori amaitzeko

257
00:18:08,690 --> 00:18:12,910
non -4 da? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Orain, non -2 da behar dut amaituko da.

260
00:18:28,060 --> 00:18:39,330
6 Beraz, 5, 7, eta azkena 4.

261
00:18:39,330 --> 00:18:43,480
Horiek dira nire sarrerak ezagutzea

262
00:18:43,480 --> 00:18:48,130
arazoa eraldatu non indize horietako bakoitzean amaitzeko behar dut,

263
00:18:48,130 --> 00:18:51,410
gero, nire final erantzuna besterik ez da, hartu Ekorketa baten zehar,

264
00:18:51,410 --> 00:18:53,580
eta gehienezko hartu.

265
00:18:53,580 --> 00:18:55,620
Beraz, kasu honetan, 8.

266
00:18:55,620 --> 00:19:00,010
Horrek esan nahi du maximoa subarray indize honetan amaitzen da,

267
00:19:00,010 --> 00:19:04,970
eta nonbait hasi aurretik.

268
00:19:04,970 --> 00:19:09,630
Denek ulertu eraldatu subarray hau?

269
00:19:09,630 --> 00:19:22,160
>> Ongi da. Beno, dezagun hau errepikatze irudikatu.

270
00:19:22,160 --> 00:19:27,990
Dezagun kontuan hartu lehen sarrera batzuk bakarrik.

271
00:19:27,990 --> 00:19:35,930
Hortaz, hona hemen 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Eta gero bat -2 izan zen hemen, eta ekarri behera 6.

273
00:19:39,790 --> 00:19:50,800
Beraz, bada posizioan sarrera deitzen I i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
nola egin dezaket erantzuna erabili dut aurreko subproblem

275
00:19:54,910 --> 00:19:59,360
subproblem honi erantzuteko?

276
00:19:59,360 --> 00:20:04,550
Begiratzen dut bada, demagun, baina sarrera hau.

277
00:20:04,550 --> 00:20:09,190
Nola egin dezaket erantzun 6 konputatu I begira

278
00:20:09,190 --> 00:20:18,780
array eta array honetan subproblems aurreko erantzun konbinazio bat? Bai?

279
00:20:18,780 --> 00:20:22,800
[Emakumezkoak ikaslea] batuketa array hartuko duzu

280
00:20:22,800 --> 00:20:25,430
posizio eskuinera aurretik, 8, beraz,

281
00:20:25,430 --> 00:20:32,170
eta, ondoren, gaur egungo subproblem gehitu duzu.

282
00:20:32,170 --> 00:20:36,460
[Yu] bere iradokizuna da, bi zenbaki horiek begiratu,

283
00:20:36,460 --> 00:20:40,090
Zenbaki hau, eta zenbaki hau.

284
00:20:40,090 --> 00:20:50,130
Beraz, hau 8 erantzun subproblem kodea (1 - i) egiten dio erreferentzia.

285
00:20:50,130 --> 00:20:57,300
Eta dezagun nire sarrera array A. deitu

286
00:20:57,300 --> 00:21:01,470
Ordena maximoa subarray posizioa i amaitzen da,

287
00:21:01,470 --> 00:21:03,980
Bi aukera daukat: bai dut jarraitu subarray

288
00:21:03,980 --> 00:21:09,790
aurreko indizea amaitu zen, edo array berri bat hasteko.

289
00:21:09,790 --> 00:21:14,190
Ziren I subarray aurreko indizea hasi, jarraitu nahi izanez gero,

290
00:21:14,190 --> 00:21:19,260
gero gehienezko batura lor daiteke I, aurreko subproblem erantzun

291
00:21:19,260 --> 00:21:24,120
plus egungo array sarrera.

292
00:21:24,120 --> 00:21:27,550
Baina, izan ere berri subarray hasierako aukeratu dut,

293
00:21:27,550 --> 00:21:30,830
Kasu horretan, batura 0 da.

294
00:21:30,830 --> 00:21:42,860
1, gehi uneko array sarrera - Beraz, erantzuna 0 max, subproblem i.

295
00:21:42,860 --> 00:21:46,150
Errepikatze horrek ez du zentzurik?

296
00:21:46,150 --> 00:21:50,840
Gure errepikatze, besterik ez dugu aurkitu, subproblem i

297
00:21:50,840 --> 00:21:54,740
gehienez aurreko subproblem plus, nire uneko array sarrera berdina da,

298
00:21:54,740 --> 00:22:01,490
horrek esan nahi du jarraitu aurreko subarray,

299
00:22:01,490 --> 00:22:07,250
edo 0, nire uneko indizea subarray berri bat hasteko.

300
00:22:07,250 --> 00:22:10,060
Eta behin eraiki dugu, irtenbideak taula honetan, eta ondoren gure behin betiko erantzuna,

301
00:22:10,060 --> 00:22:13,950
Ekorketa lineala egin bat subproblem array zehar

302
00:22:13,950 --> 00:22:19,890
eta gehienezko hartu.

303
00:22:19,890 --> 00:22:23,330
Inplementazio zehatza da zer esan besterik ez dut.

304
00:22:23,330 --> 00:22:27,320
Beraz, subproblems array berri bat subproblem sortu dugu.

305
00:22:27,320 --> 00:22:32,330
0 edo lehen sarrera, gehienez bi horien lehen sarrera da.

306
00:22:32,330 --> 00:22:35,670
Eta subproblems, gainerako

307
00:22:35,670 --> 00:22:39,810
aurkitu besterik ez dugu zehatza errepikatze erabiltzen dugu.

308
00:22:39,810 --> 00:22:49,960
Orain gure subproblems array gehienez konputatu dugu, eta, gure behin betiko erantzuna.

309
00:22:49,960 --> 00:22:54,130
>> Beraz, zenbat espazio algoritmo hau erabiltzen ari gara?

310
00:22:54,130 --> 00:23:01,470
Dituzun hartu baino ez bada CS50, eta gero, agian ez duzu eztabaidatu espazio asko.

311
00:23:01,470 --> 00:23:07,750
Beno, gauza bat kontutan izan da malloc deitu dut hemen tamaina n.

312
00:23:07,750 --> 00:23:13,590
Zer esan gomendatzen?

313
00:23:13,590 --> 00:23:17,450
Algoritmo honek espazio lineala erabiltzen du.

314
00:23:17,450 --> 00:23:21,030
Ezin hobeto egiten dugu?

315
00:23:21,030 --> 00:23:30,780
Ba al dago ezer ez da beharrezkoa azken erantzuna kalkulatzeko nabarituko duzula?

316
00:23:30,780 --> 00:23:33,290
I guess galdera bat hobea da, zein informazio

317
00:23:33,290 --> 00:23:40,680
egin behar, ez dugu modu guztiak aurrera eraman ahal izateko amaieran?

318
00:23:40,680 --> 00:23:44,280
Orain, bi lerro hauek kontuan hartuz gero,

319
00:23:44,280 --> 00:23:47,720
, aurreko subproblem buruz baino ez dugu nahi,

320
00:23:47,720 --> 00:23:50,910
eta inoiz ikusi dugu, orain arte, gehienez buruz baino ez dugu zaindu.

321
00:23:50,910 --> 00:23:53,610
Gure azken erantzuna kalkulatzeko, ez dugu behar array osoa.

322
00:23:53,610 --> 00:23:57,450
Azken zenbakia, azken bi zenbakiak bakarrik behar dugu.

323
00:23:57,450 --> 00:24:02,630
Azken zenbakia subproblem array, eta azken gehienezko kopurua.

324
00:24:02,630 --> 00:24:07,380
Beraz, hain zuzen ere, loops horiek Fuse ahal izango dugu elkarrekin

325
00:24:07,380 --> 00:24:10,460
eta espazio lineal espazio etengabeko joan.

326
00:24:10,460 --> 00:24:15,830
Oraingo batura beraz, orain arte, hemen, subproblem, gure subproblem array rola ordezkatzen du.

327
00:24:15,830 --> 00:24:20,020
Beraz, gaur egungo batura, eta, beraz, orain arte,, aurreko subproblem erantzuna da.

328
00:24:20,020 --> 00:24:23,450
Eta batura hori, eta, beraz, orain arte, gure max lekua hartzen du.

329
00:24:23,450 --> 00:24:28,100
Gehienez konputatu dugu, joan gara.

330
00:24:28,100 --> 00:24:30,890
Eta, beraz, espazio lineal joan gara etengabe espazioa

331
00:24:30,890 --> 00:24:36,650
dugu gure subarray arazoa konpontzeko lineal bat.

332
00:24:36,650 --> 00:24:40,740
>> Elkarrizketa batean galdera-mota hauek izango duzu.

333
00:24:40,740 --> 00:24:44,450
Zer da denbora konplexutasuna da; espazioaren konplexutasuna zer da?

334
00:24:44,450 --> 00:24:50,600
Ezin hobeto egin nahi duzu? Ba al dago alferrikako mantendu diren gauzak?

335
00:24:50,600 --> 00:24:55,270
Hau nik egin dut zure hartu behar aztertzen nabarmendu

336
00:24:55,270 --> 00:24:57,400
ari zaren arazoak horien bidez lan.

337
00:24:57,400 --> 00:25:01,710
Beti zeure buruari galdetuz, "Ezin hobeto egin dut?"

338
00:25:01,710 --> 00:25:07,800
Izan ere, hori baino hobeto egin dugu?

339
00:25:07,800 --> 00:25:10,730
Ordena trikimailu galdera bat. Ezin duzu, behar duzu delako

340
00:25:10,730 --> 00:25:13,590
gutxienez, arazo sarrera irakurri.

341
00:25:13,590 --> 00:25:15,570
Izan ere, behar duzu, eta, gutxienez, irakurri Beraz, sarrerako arazoa

342
00:25:15,570 --> 00:25:19,580
esan nahi du ezin duzula egin denbora lineala baino hobea da,

343
00:25:19,580 --> 00:25:22,870
eta ezin duzu etengabeko espazioa baino hobeto.

344
00:25:22,870 --> 00:25:27,060
Beraz, hau da, hain zuzen ere, arazo hau konponbide onena.

345
00:25:27,060 --> 00:25:33,040
Zalantzak dituzu? Ongi da.

346
00:25:33,040 --> 00:25:35,190
>> Burtsa arazoa:

347
00:25:35,190 --> 00:25:38,350
"N zenbaki osoko, positiboa, zero, edo negatiboa array bat,

348
00:25:38,350 --> 00:25:41,680
stock baten prezioa n egunetan zehar,

349
00:25:41,680 --> 00:25:44,080
funtzio bat idatzi gehienezko irabazien kalkulatzeko egin dezakezu

350
00:25:44,080 --> 00:25:49,350
ematen, erosi eta saldu zehazki 1 stock eguneko epean n horiek ".

351
00:25:49,350 --> 00:25:51,690
Funtsean, baxua erosi, saldu handiko nahi dugu.

352
00:25:51,690 --> 00:25:58,580
Eta egin ahal ditugu irabazien onena irudikatu nahi dugu.

353
00:25:58,580 --> 00:26:11,500
Atzera eginez, nire tip, zer berehala argi eta garbi, erantzun sinpleena da, baina motela da?

354
00:26:11,500 --> 00:26:17,690
Bai? (Ikaslea, ulertezina) >> Bai.

355
00:26:17,690 --> 00:26:21,470
>> Beraz, nahi duzun joan nahiz eta stock prezioak begiratu

356
00:26:21,470 --> 00:26:30,550
une bakoitzean, (ulertezina).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ados, eta, beraz, bere irtenbide - bere informatika gomendioa

358
00:26:33,990 --> 00:26:37,380
txikiena eta handiena kalkulatzeko, ez du zertan lan

359
00:26:37,380 --> 00:26:42,470
altuena, baxuena aurretik ere gerta liteke.

360
00:26:42,470 --> 00:26:47,340
Beraz, zer brute indarrean Arazo honen konponbidea da?

361
00:26:47,340 --> 00:26:53,150
Zer dira bi gauza bakarra irabazi egin zehaztu behar dut? Eskuin.

362
00:26:53,150 --> 00:26:59,410
Brute indarrean soluzioa - oh, beraz, George iradokizuna da, bi egun besterik ez dugu behar.

363
00:26:59,410 --> 00:27:02,880
bi egun horietan irabazi bakarrean zehazteko.

364
00:27:02,880 --> 00:27:06,660
Beraz, bikote bakoitzak konputatu dugu, nahi erosi / saldu,

365
00:27:06,660 --> 00:27:12,850
konputatzeko irabazi, negatiboa edo positiboa edo zero izan daiteke.

366
00:27:12,850 --> 00:27:18,000
Kontatu gehienezko irabazien egun bikote guztiak baino gehiago errepikatzean ondoren egiten dugu.

367
00:27:18,000 --> 00:27:20,330
Hori da gure erantzuna behin betiko izango da.

368
00:27:20,330 --> 00:27:25,730
Eta konponbide O (n ^ 2) izango da, ez dagoelako n bi bikote aukeratu -

369
00:27:25,730 --> 00:27:30,270
egun, azken egun artean aukeratu ahal izango dituzu.

370
00:27:30,270 --> 00:27:32,580
Ados, beraz, ez naiz hemen indarrean brute irtenbide baino gehiago joan behar.

371
00:27:32,580 --> 00:27:37,420
Esango dizut ez dagoela log n irtenbide bat n noa.

372
00:27:37,420 --> 00:27:45,550
Zer algoritmoa ez gaur egun ezagutzen duzun n log n?

373
00:27:45,550 --> 00:27:50,730
Ez da trikimailu galdera bat.

374
00:27:50,730 --> 00:27:54,790
>> Batu sort. Batu sort-n log-n da,

375
00:27:54,790 --> 00:27:57,760
eta hain zuzen ere, arazo hau konpontzeko modu bat da erabili

376
00:27:57,760 --> 00:28:04,400
merge sort ideia mota deitzen zaio, oro har, zatitzea eta konkistatzeko.

377
00:28:04,400 --> 00:28:07,570
Eta ideia da honela.

378
00:28:07,570 --> 00:28:12,400
Best buy konputatu / bikotea saldu ezkerreko erdia nahi duzu.

379
00:28:12,400 --> 00:28:16,480
Aurkitu eta irabazien onena egin dezakezu, bi egunetan zehar lehen n.

380
00:28:16,480 --> 00:28:19,780
Orduan, onena erosi oompute / bikotea eskuineko erdia saldu nahi baduzu,

381
00:28:19,780 --> 00:28:23,930
beraz, azken bi egunetan zehar n.

382
00:28:23,930 --> 00:28:32,400
Eta orain, galdera da, nola irtenbide hauek batu ditugu atzera elkarrekin?

383
00:28:32,400 --> 00:28:36,320
Bai? (Ikaslea, ulertezina)

384
00:28:36,320 --> 00:28:49,890
>> Ados. Beraz, let irudi bat marraztu me.

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

386
00:29:03,870 --> 00:29:06,450
>> Zehazki. George irtenbide zehazki eskubidea da.

387
00:29:06,450 --> 00:29:10,040
Bere iradokizun Beraz, lehenik eta behin, konputatu buy / Saldu bikote onena,

388
00:29:10,040 --> 00:29:16,050
eta ezkerreko zatian gertatzen da, beraz, dezagun dei ezker, ezkerretik.

389
00:29:16,050 --> 00:29:20,790
Best erosi / saldu eskuineko erdia gertatzen den bikotea.

390
00:29:20,790 --> 00:29:25,180
Baina besterik ez dugu aldean bada, bi zenbaki horiek, kasu ari gara falta

391
00:29:25,180 --> 00:29:30,460
non hemen erosi eta saldu nonbait eskuineko erdia.

392
00:29:30,460 --> 00:29:33,810
Ezkerreko erdia erosi dugu, eskuineko erdia saltzen.

393
00:29:33,810 --> 00:29:38,490
Eta onena buy / Saldu bikotea halves bi luzeago kalkulatzeko modurik onena

394
00:29:38,490 --> 00:29:43,480
gutxieneko konputatu da hemen eta gehienez kalkulatzeko hemen

395
00:29:43,480 --> 00:29:45,580
eta dute aldea.

396
00:29:45,580 --> 00:29:50,850
Buy / Saldu bikotea gertatzen da bi kasuetan bakarrik hemen, beraz,

397
00:29:50,850 --> 00:30:01,910
bakarrik, edo halves bi hiru zenbaki horiek definitzen da.

398
00:30:01,910 --> 00:30:06,450
Gure algoritmoa Beraz, gure irtenbideak batu itzuli batera,

399
00:30:06,450 --> 00:30:08,350
buy / Saldu bikote onena konputatu nahi dugu

400
00:30:08,350 --> 00:30:13,120
ezkerreko erdia non erosi eta eskuineko erdia saldu dugu.

401
00:30:13,120 --> 00:30:16,740
Eta hori egiteko modurik onena da txikiena prezioa kalkulatzeko, lehenengo seihilekoan,

402
00:30:16,740 --> 00:30:20,360
eskuineko erdia prezio handiena, eta aldea hartu.

403
00:30:20,360 --> 00:30:25,390
Emaitzeko hiru irabaziak, hiru zenbaki horiek, gehienez, hiru hartzen duzu,

404
00:30:25,390 --> 00:30:32,720
eta horiek lehen eta bukaera egunetan zehar mozkin egin dezakezu hori.

405
00:30:32,720 --> 00:30:36,940
Here garrantzitsua lerro gorri dira.

406
00:30:36,940 --> 00:30:41,160
Ezkerreko erdia erantzuna kalkulatzeko dei errekurtsiboa da.

407
00:30:41,160 --> 00:30:44,760
Dei errekurtsiboa erantzuna kalkulatzeko eskuineko zatia da.

408
00:30:44,760 --> 00:30:50,720
Hauek bi begiztak konputatzeko min eta max ezkerreko eta eskuineko erdia, hurrenez hurren.

409
00:30:50,720 --> 00:30:54,970
Orain halves bi irabazi luzeago konputatu I,

410
00:30:54,970 --> 00:31:00,530
eta azken erantzun horiek hiru gehienez.

411
00:31:00,530 --> 00:31:04,120
Ongi da.

412
00:31:04,120 --> 00:31:06,420
>> Beraz, ziur aski, algoritmo bat dugu, baina handiagoa da galdera,

413
00:31:06,420 --> 00:31:08,290
zer da hau konplexutasuna denbora?

414
00:31:08,290 --> 00:31:16,190
Eta zergatik aipatu dut merge sort formulario hau zatitzen erantzuna

415
00:31:16,190 --> 00:31:19,200
bi sartu eta, ondoren, gure irtenbideak batuz itzuli batera

416
00:31:19,200 --> 00:31:23,580
zehazki merge sort.

417
00:31:23,580 --> 00:31:33,360
Hargatik joan iraupena bidez.

418
00:31:33,360 --> 00:31:41,340
Definitu dugu funtzioa t (n) bada urratsen kopurua izango

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

420
00:31:50,010 --> 00:31:54,350
gure bi dei errekurtsiboak

421
00:31:54,350 --> 00:32:00,460
bakoitzeko kostua t (n / 2),

422
00:32:00,460 --> 00:32:03,540
eta ez da bi dei horiek.

423
00:32:03,540 --> 00:32:10,020
Orain ezker erdia gutxienez konputatu behar dut,

424
00:32:10,020 --> 00:32:17,050
n / 2 denbora, gehi eskuineko erdia gehienez egin ahal izango dut.

425
00:32:17,050 --> 00:32:20,820
Beraz, hori besterik ez da, n.

426
00:32:20,820 --> 00:32:25,050
Eta gero, etengabeko lan batzuk gehi.

427
00:32:25,050 --> 00:32:27,770
Eta errepikatze ekuazio honen

428
00:32:27,770 --> 00:32:35,560
hain zuzen ere, errepikatze merge sort ekuazioa.

429
00:32:35,560 --> 00:32:39,170
Eta denok dakigu, merge sort n log n denbora da.

430
00:32:39,170 --> 00:32:46,880
Hori dela eta, gure algoritmoa da, baita ere n log n denbora.

431
00:32:46,880 --> 00:32:52,220
Iterazio honetan ez du zentzurik?

432
00:32:52,220 --> 00:32:55,780
Just honen laburpena txiki bat:

433
00:32:55,780 --> 00:32:59,170
Gehienezko irabazien urratsen kopurua kalkulatzeko T (n)

434
00:32:59,170 --> 00:33:02,750
n egun osoan zehar.

435
00:33:02,750 --> 00:33:06,010
Zatitu dugu gure dei errekurtsiboak

436
00:33:06,010 --> 00:33:11,980
n / 2 lehen egunetan gure irtenbide deituz da,

437
00:33:11,980 --> 00:33:14,490
beraz, dei bat da,

438
00:33:14,490 --> 00:33:16,940
eta, ondoren, berriro deitzen diogu bigarren erdian.

439
00:33:16,940 --> 00:33:20,440
Beraz, bi deiak.

440
00:33:20,440 --> 00:33:25,310
Eta gero, gutxienez bat aurkituko dugu ezkerreko erdia, denbora lineala egin ahal izango dugu,

441
00:33:25,310 --> 00:33:29,010
aurkitu eskuineko erdia, gehienez, denbora lineala egin ahal izango dugu.

442
00:33:29,010 --> 00:33:31,570
Beraz, n / 2 + n / 2 besterik ez da n.

443
00:33:31,570 --> 00:33:36,020
Ondoren, etengabeko lan batzuk ditugu, aritmetika egiten bezalakoa da.

444
00:33:36,020 --> 00:33:39,860
Errepikatze-ekuazioa hau da, hain zuzen ere errepikatze merge sort ekuazioa.

445
00:33:39,860 --> 00:33:55,490
Hori dela eta, gure nahastu algoritmoa ere n n saioa.

446
00:33:55,490 --> 00:33:58,520
Beraz, zenbat espazio erabiltzen ari gara?

447
00:33:58,520 --> 00:34:04,910
Dezagun itzuli kodea.

448
00:34:04,910 --> 00:34:09,420
>> Galdera bat hobea da, zenbat pila markoak edozein une jakin dugu inoiz izan?

449
00:34:09,420 --> 00:34:11,449
Ari gara errekurtsio erabiliz geroztik,

450
00:34:11,449 --> 00:34:23,530
gure erabilera espazio pila fotograma kopurua zehazten du.

451
00:34:23,530 --> 00:34:29,440
Dezagun kontuan hartu n = 8.

452
00:34:29,440 --> 00:34:36,889
Nahastu deitzen diogu, 8,

453
00:34:36,889 --> 00:34:41,580
nahastu deituko lehen lau sarrerak,

454
00:34:41,580 --> 00:34:46,250
lehen bi sarrerak nahastu deituko.

455
00:34:46,250 --> 00:34:51,550
Beraz, gure pila da, hau da, gure pila da.

456
00:34:51,550 --> 00:34:54,980
Eta ondoren, nahastu berriro deitzen diogu 1,

457
00:34:54,980 --> 00:34:58,070
eta horrek zer da gure oinarria kasuan, eta, beraz, berehala itzuliko gara.

458
00:34:58,070 --> 00:35:04,700
Dugu inoiz hau pila asko fotograma baino gehiago?

459
00:35:04,700 --> 00:35:08,880
Aldi bakoitzean deitzeko bat egiten dugu delako,

460
00:35:08,880 --> 00:35:10,770
Nahastu deitzeko recursive,

461
00:35:10,770 --> 00:35:13,950
gure tamaina erdia zatitzen dugu.

462
00:35:13,950 --> 00:35:17,020
Pila fotograma kopurua gehienez Beraz, edozein une jakin dugu inoiz

463
00:35:17,020 --> 00:35:28,460
log n pila fotograma ordena da.

464
00:35:28,460 --> 00:35:42,460
Pila marko bakoitzak etengabeko espazioa du,

465
00:35:42,460 --> 00:35:44,410
eta, beraz, espazioaren zenbatekoa, guztira,

466
00:35:44,410 --> 00:35:49,240
espazioaren zenbatekoa, gehienez erabili dugu inoiz O (log n) espazioa da

467
00:35:49,240 --> 00:36:03,040
non n egun kopurua da.

468
00:36:03,040 --> 00:36:07,230
>> Orain, beti galdetu zeure burua, "Ezin hobeto egiten dugu?"

469
00:36:07,230 --> 00:36:12,390
Eta, batez ere, ezin hori murrizteko dugu dagoeneko konpondu arazo bat?

470
00:36:12,390 --> 00:36:20,040
Aholkua: beste bi arazo eztabaidatu besterik ez dugu aurretik, eta ez da nahastu izango.

471
00:36:20,040 --> 00:36:26,200
Burtsa hau arazo bihurtu ahal izango dugu subarray maximoa arazoa.

472
00:36:26,200 --> 00:36:40,100
Nola egin dezakegu hori?

473
00:36:40,100 --> 00:36:42,570
Duzu bat? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Maximoa arazoa Beraz subarray

477
00:36:59,940 --> 00:37:10,610
batura bat bilatzen ari gara etengabeko subarray zehar.

478
00:37:10,610 --> 00:37:16,230
Eta Emmy stock arazoa iradokizun,

479
00:37:16,230 --> 00:37:30,720
iritziz, aldaketa, edo deltak.

480
00:37:30,720 --> 00:37:37,440
Eta argazki bat da, hau da stock baten prezioa,

481
00:37:37,440 --> 00:37:42,610
baina egun bakoitzean partiduko arteko aldea hartu badugu -

482
00:37:42,610 --> 00:37:45,200
beraz, gehienezko prezioa, gehienezko irabazien egin izan dugu ikusiko dugu

483
00:37:45,200 --> 00:37:50,070
erosi dugu hemen, eta hemen saltzeko.

484
00:37:50,070 --> 00:37:54,240
Baina etengabe begiratu dezagun subarray arazoa begiratu.

485
00:37:54,240 --> 00:38:02,510
Hortaz, hona hemen, egin ahal izango dugu, hemendik aurrera hemen joan,

486
00:38:02,510 --> 00:38:08,410
positiboa aldaketa bat dugu, eta, ondoren, hemendik aurrera hemen negatiboa aldaketa bat dugu.

487
00:38:08,410 --> 00:38:14,220
Baina orduan, hemendik aurrera hemen positiboa aldaketa handi bat izan dugu.

488
00:38:14,220 --> 00:38:20,930
Eta aldaketa horiek laburbildu nahi dugun gure azken irabazien iritsi dira.

489
00:38:20,930 --> 00:38:25,160
Ondoren, aldaketa gehiago negatiboa izan dugu hemen.

490
00:38:25,160 --> 00:38:29,990
, Gure stock arazoa murrizteko gure subarray maximoa arazoa gakoa

491
00:38:29,990 --> 00:38:36,630
egun arteko deltak kontuan hartu behar da.

492
00:38:36,630 --> 00:38:40,630
Beraz izeneko deltak array berri bat sortu dugu,

493
00:38:40,630 --> 00:38:43,000
hasieratu 0 izango lehen sarrera,

494
00:38:43,000 --> 00:38:46,380
eta, ondoren, delta bakoitzean (i), utzi aldea

495
00:38:46,380 --> 00:38:52,830
nire sarrera array (i), eta array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Ondoren, gure maximoa subarray prozedura errutina deitzen dugun

497
00:38:55,530 --> 00:39:01,500
delta baten array igaroz.

498
00:39:01,500 --> 00:39:06,440
Lineal denbora maximoa subarray delako,

499
00:39:06,440 --> 00:39:09,370
eta murrizketa hori, delta array hau sortzeko prozesu honetan,

500
00:39:09,370 --> 00:39:11,780
da ere denbora lineala,

501
00:39:11,780 --> 00:39:19,060
ondoren stock behin betiko irtenbidea O (n) lan-plus O (n) lana da, oraindik O (n) lana.

502
00:39:19,060 --> 00:39:23,900
Beraz, lineal bat denbora gure arazoa konpontzeko behar dugu.

503
00:39:23,900 --> 00:39:29,610
Denek ulertzen ez du eraldaketa hau?

504
00:39:29,610 --> 00:39:32,140
>> Oro har, ideia ona da beti izan behar duzula

505
00:39:32,140 --> 00:39:34,290
ari zaren arazo berri bat ikusteko murrizten saiatuko da.

506
00:39:34,290 --> 00:39:37,700
Badirudi arazo zahar bat ezagutzen baduzu,

507
00:39:37,700 --> 00:39:39,590
saiatuko da arazo zahar murrizteko.

508
00:39:39,590 --> 00:39:41,950
Eta arazo zaharrak erabiltzen duzun tresna erabiltzen baduzu

509
00:39:41,950 --> 00:39:46,450
arazoa konpontzeko.

510
00:39:46,450 --> 00:39:49,010
Beraz, itzulbiratu, tekniko elkarrizketak dira erronka.

511
00:39:49,010 --> 00:39:52,280
Arazo horiek dira ziurrenik arazo zailagoa batzuk

512
00:39:52,280 --> 00:39:54,700
elkarrizketa bat ikusi liteke,

513
00:39:54,700 --> 00:39:57,690
beraz, arazo besterik ez dut estaltzen ez baduzu ulertzen, ados.

514
00:39:57,690 --> 00:40:01,080
Hauek arazo gehiago Challenging batzuk dira.

515
00:40:01,080 --> 00:40:03,050
Praktika, praktikan, praktikan.

516
00:40:03,050 --> 00:40:08,170
Esku-en arazo asko eman dut, eta, beraz, behin betiko egiaztatu duten.

517
00:40:08,170 --> 00:40:11,690
Eta sorte on zure elkarrizketak. Nire baliabide guztiak esteka honetan etan

518
00:40:11,690 --> 00:40:15,220
eta nire lagunak senior bat eskaini du mock tekniko elkarrizketak egin,

519
00:40:15,220 --> 00:40:22,050
hala badagokio interesatuta bazaude, email Will Yao duten e-posta helbidea.

520
00:40:22,050 --> 00:40:26,070
Zalantzaren bat izanez gero, galdetu ahal izango duzu.

521
00:40:26,070 --> 00:40:28,780
Do you guys tekniko elkarrizketak lotutako galdera zehatzei

522
00:40:28,780 --> 00:40:38,440
edo ikusi dugu, orain arte, inolako arazorik?

523
00:40:38,440 --> 00:40:49,910
Ongi da. Beno, sorte on zure elkarrizketak.

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