1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seimineár: Agallaimh Teicniúil]

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

3
00:00:04,630 --> 00:00:08,910
[Tá sé seo CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Dia duit gach duine, tá mé Kenny. Tá mé faoi láthair ag déanamh staidéir ar eolaíocht ríomhaireachta sóisearach.

5
00:00:12,420 --> 00:00:17,310
Tá mé iar-CS TF, agus is mian liom go raibh mé seo nuair a bhí mé underclassman,

6
00:00:17,310 --> 00:00:19,380
agus sin an fáth a bhfuil mé ag tabhairt an seimineár seo.

7
00:00:19,380 --> 00:00:21,370
Mar sin, tá súil agam go mbainfidh tú taitneamh as é.

8
00:00:21,370 --> 00:00:23,470
Is é an seimineár seo faoi agallaimh teicniúla,

9
00:00:23,470 --> 00:00:26,650
agus is féidir gach mo acmhainní a fháil ag an nasc seo,

10
00:00:26,650 --> 00:00:32,350
an nasc seo ar dheis anseo, cúpla na n-acmhainní.

11
00:00:32,350 --> 00:00:36,550
Mar sin, rinne mé liosta de na fadhbanna, i ndáiríre, go leor le roinnt fadhbanna.

12
00:00:36,550 --> 00:00:40,800
Chomh maith leis sin ginearálta acmhainní leathanach áit ar féidir linn a leideanna a fháil

13
00:00:40,800 --> 00:00:42,870
maidir le conas a ullmhú le haghaidh agallaimh,

14
00:00:42,870 --> 00:00:46,470
leideanna maidir le cad ba cheart duit a dhéanamh le linn agallaimh iarbhír,

15
00:00:46,470 --> 00:00:51,910
chomh maith le conas a chur chuige fadhbanna agus acmhainní le haghaidh tagartha sa todhchaí.

16
00:00:51,910 --> 00:00:53,980
Tá sé ar fad ar líne.

17
00:00:53,980 --> 00:00:58,290
Agus díreach chun réamhrá ar an seimineár seo, séanadh,

18
00:00:58,290 --> 00:01:00,690
Níor chóir mar seo - a ullmhú do agallamh

19
00:01:00,690 --> 00:01:02,800
Níor chóir a bheith teoranta do liosta seo.

20
00:01:02,800 --> 00:01:04,750
Tá sé seo i gceist ach amháin a bheith ina threoir,

21
00:01:04,750 --> 00:01:08,890
agus ba chóir duit a ghlacadh cinnte gach rud a rá liom le gráin salainn,

22
00:01:08,890 --> 00:01:14,620
ach úsáid a bhaint freisin gach rud a úsáid mé chun cabhrú leat i do ullmhú agallamh.

23
00:01:14,620 --> 00:01:16,400
>> Tá mé ag dul chun dlús a chur tríd an sleamhnán amach romhainn

24
00:01:16,400 --> 00:01:18,650
ionas gur féidir linn a fháil chun an cás-staidéir iarbhír.

25
00:01:18,650 --> 00:01:23,630
Struchtúr ar agallamh do postion innealtóireacht bogearraí,

26
00:01:23,630 --> 00:01:26,320
de ghnáth go bhfuil sé 30 go 45 nóiméad,

27
00:01:26,320 --> 00:01:29,810
babhtaí il, ag brath ar an gcuideachta.

28
00:01:29,810 --> 00:01:33,090
Is minic go mbainfidh tú a códú ar bord bán.

29
00:01:33,090 --> 00:01:35,960
Mar sin gclár bán mar seo, ach is minic ar scála níos lú.

30
00:01:35,960 --> 00:01:38,540
Má tá tú tar éis agallamh teileafóin, beidh tú is dócha a bheith ag baint úsáide as

31
00:01:38,540 --> 00:01:44,030
ceachtar collabedit nó Doc Google ionas gur féidir leo a fheiceann tú beo códaithe

32
00:01:44,030 --> 00:01:46,500
agus tú á agallamh ar an teileafón.

33
00:01:46,500 --> 00:01:48,490
Tá agallamh féin de ghnáth 2 nó 3 fadhbanna

34
00:01:48,490 --> 00:01:50,620
tástáil do chuid eolais eolaíocht ríomhaireachta.

35
00:01:50,620 --> 00:01:54,490
Agus beidh sé beagnach cinnte i gceist códaithe.

36
00:01:54,490 --> 00:01:59,540
Is iad na cineálacha ceisteanna a mbainfidh tú a fheiceáil de ghnáth struchtúir sonraí agus halgartaim.

37
00:01:59,540 --> 00:02:02,210
Agus a dhéanamh ar na cineálacha fadhbanna,

38
00:02:02,210 --> 00:02:07,830
beidh siad a iarraidh ort, cosúil le, cad é an t-am agus castacht spás, mór O?

39
00:02:07,830 --> 00:02:09,800
Is minic a iarrann siad freisin ar leibhéal níos airde ceisteanna,

40
00:02:09,800 --> 00:02:12,530
mar sin, a dhearadh córas,

41
00:02:12,530 --> 00:02:14,770
conas a leagan amach do chód?

42
00:02:14,770 --> 00:02:18,370
Cad iad na Comhéadain, cad ranganna, cad modúil bhfuil tú i do chóras,

43
00:02:18,370 --> 00:02:20,900
agus conas a idirghníomhaíonn na chéile?

44
00:02:20,900 --> 00:02:26,130
Mar sin, struchtúir sonraí agus halgartaim chomh maith le córais a dhearadh.

45
00:02:26,130 --> 00:02:29,180
>> Roinnt leideanna ginearálta sula Léim in ár cás-staidéir.

46
00:02:29,180 --> 00:02:32,300
Sílim go bhfuil an riail is tábhachtaí i gcónaí a bheith ag smaoineamh amach os ard.

47
00:02:32,300 --> 00:02:36,980
Is é an t-agallamh ceaptha a bheith do dheis a thaispeáint as do phróiseas smaoineamh.

48
00:02:36,980 --> 00:02:39,820
Is é an pointe an t-agallamh le haghaidh an t-agallóir a mheas

49
00:02:39,820 --> 00:02:42,660
conas a cheapann tú, agus conas a théann tú trí fhadhb.

50
00:02:42,660 --> 00:02:45,210
Is é an rud is measa féidir leat a dhéanamh a bheith ciúin ar fud an agallamh ar fad.

51
00:02:45,210 --> 00:02:50,090
Sin díreach chomh maith uimh.

52
00:02:50,090 --> 00:02:53,230
Nuair a bheidh tú a thugtar ceist, ba mhaith leat freisin chun a dhéanamh cinnte go dtuigeann tú an cheist.

53
00:02:53,230 --> 00:02:55,350
Mar sin, arís an cheist ar ais i do chuid focal féin

54
00:02:55,350 --> 00:02:58,920
agus iarracht a bheith ag obair chríochnúil cásanna tástála cúpla simplí

55
00:02:58,920 --> 00:03:01,530
a dhéanamh cinnte go dtuigeann tú an cheist.

56
00:03:01,530 --> 00:03:05,510
Beidh Ag obair trí chásanna tástála cúpla a thabhairt duit freisin ar intuition ar an gcaoi a fhadhb seo a réiteach.

57
00:03:05,510 --> 00:03:11,210
D'fhéadfá a fháil amach fiú patrúin cúpla chun cabhrú leat an fhadhb a réiteach.

58
00:03:11,210 --> 00:03:14,500
Is é an tip mór chun nach fháil frustrated.

59
00:03:14,500 --> 00:03:17,060
Ná fháil frustrated.

60
00:03:17,060 --> 00:03:19,060
Agallaimh Tá dúshlánach, ach an rud is measa féidir leat a dhéanamh,

61
00:03:19,060 --> 00:03:23,330
chomh maith le bheith ciúin, is é a bheidh frustrated go feiceálach.

62
00:03:23,330 --> 00:03:27,410
Ní mian leat leis an tuiscint a thabhairt do agallóir.

63
00:03:27,410 --> 00:03:33,960
Rud amháin go bhfuil tú - mar sin, go leor daoine, nuair a théann siad isteach i agallamh,

64
00:03:33,960 --> 00:03:37,150
iad ag iarraidh chun iarracht a dhéanamh teacht ar an réiteach is fearr ar dtús,

65
00:03:37,150 --> 00:03:39,950
nuair i ndáiríre, níl de ghnáth réiteach glaringly soiléir.

66
00:03:39,950 --> 00:03:43,500
D'fhéadfadh sé a bheith mall, d'fhéadfadh sé a bheith mí-éifeachtach, ach ba chóir duit a lua sé ach,

67
00:03:43,500 --> 00:03:46,210
ach ionas go mbeidh tú phointe tosaigh as a bheith ag obair níos fearr.

68
00:03:46,210 --> 00:03:48,270
Chomh maith leis sin, is é ag cur in iúl an réiteach mall, i dtéarmaí

69
00:03:48,270 --> 00:03:52,160
castacht am mór O nó castacht spáis,

70
00:03:52,160 --> 00:03:54,450
Beidh léiriú don agallóir go dtuigeann tú

71
00:03:54,450 --> 00:03:57,510
na ceisteanna seo nuair a scríobh cód.

72
00:03:57,510 --> 00:04:01,440
Ní sin a dhéanamh a bheith eaglach chun teacht suas leis an algartam is simplí ar dtús

73
00:04:01,440 --> 00:04:04,950
agus ag obair ansin níos fearr ó ann.

74
00:04:04,950 --> 00:04:09,810
Ceisteanna ar bith go dtí seo? Maith go leor.

75
00:04:09,810 --> 00:04:11,650
>> Mar sin a ligean ar Léim isteach inár chéad fhadhb.

76
00:04:11,650 --> 00:04:14,790
"Mar gheall ar sraith de slánuimhreacha n, scríobh feidhm a Shuffle an eagar

77
00:04:14,790 --> 00:04:20,209
san áit sin go bhfuil gach permutations de na slánuimhreacha n seans céanna. "

78
00:04:20,209 --> 00:04:23,470
Agus glacadh leis go bhfuil tú ar fáil gineadóir slánuimhir randamach

79
00:04:23,470 --> 00:04:30,980
a ghineann slánuimhir i raon ó 0 go dtí mé, raon leath.

80
00:04:30,980 --> 00:04:32,970
An bhfuil gach duine a thuiscint cheist seo?

81
00:04:32,970 --> 00:04:39,660
Mé a thabhairt duit le sraith de slánuimhreacha n, agus ba mhaith liom a thabhairt duit Suaitheadh ​​é.

82
00:04:39,660 --> 00:04:46,050
I mo eolaire, scríobh mé cláir cúpla a thaispeáint cad is ciall agam.

83
00:04:46,050 --> 00:04:48,910
Tá mé ag dul Suaitheadh ​​le sraith de 20 eilimintí,

84
00:04:48,910 --> 00:04:52,490
ó -10 go 9,

85
00:04:52,490 --> 00:04:57,050
agus ba mhaith liom tú a aschur liosta mar seo.

86
00:04:57,050 --> 00:05:02,890
Mar sin, is é seo mo sraith ionchur sórtáilte, agus ba mhaith liom a thabhairt duit Suaitheadh ​​é.

87
00:05:02,890 --> 00:05:07,070
Beidh muid é a dhéanamh arís.

88
00:05:07,070 --> 00:05:13,780
An bhfuil gach duine a thuiscint an cheist? Maith go leor.

89
00:05:13,780 --> 00:05:16,730
Mar sin tá sé suas chun tú.

90
00:05:16,730 --> 00:05:21,220
Cad iad roinnt smaointe? An féidir leat é a dhéanamh mar n ^ 2, n logáil n, n?

91
00:05:21,220 --> 00:05:34,400
Oscailte do mholtaí.

92
00:05:34,400 --> 00:05:37,730
Maith go leor. Mar sin, aon smaoineamh, mhol Emmy,

93
00:05:37,730 --> 00:05:45,300
Is é an chéad uimhir randamach, slánuimhir randamach, i réimse a ríomh 0-20.

94
00:05:45,300 --> 00:05:49,840
Mar sin, glacadh leis go bhfuil ár sraith ar fad de 20.

95
00:05:49,840 --> 00:05:54,800
I ár léaráid de 20 eilimintí,

96
00:05:54,800 --> 00:05:58,560
is é seo ár sraith ionchur.

97
00:05:58,560 --> 00:06:04,590
Agus anois, tá a moladh a chruthú sraith nua,

98
00:06:04,590 --> 00:06:08,440
mar sin beidh sé seo an raon aschur.

99
00:06:08,440 --> 00:06:12,880
Agus atá bunaithe ar an ais i ag Rand -

100
00:06:12,880 --> 00:06:17,580
mar sin má bhí mé, a ligean ar rá, 17,

101
00:06:17,580 --> 00:06:25,640
cóip an eilimint an 17ú isteach an chéad staid.

102
00:06:25,640 --> 00:06:30,300
Anois, ní mór dúinn a scriosadh - is gá dúinn a athrú ar fad na gnéithe anseo

103
00:06:30,300 --> 00:06:36,920
níos mó ná sin go bhfuil bearna ag an deireadh agus ní poill sa lár.

104
00:06:36,920 --> 00:06:39,860
Agus anois táimid arís ar an bpróiseas.

105
00:06:39,860 --> 00:06:46,360
Anois táimid ag Pioc slánuimhir nua randamach idir 0 agus 19.

106
00:06:46,360 --> 00:06:52,510
Tá mé nua anseo, agus cóip muid ngné seo sa phost seo.

107
00:06:52,510 --> 00:07:00,960
Ansin againn míreanna athrú thar agus arís againn ar an bpróiseas go dtí go bhfuil muid ár sraith nua go hiomlán.

108
00:07:00,960 --> 00:07:05,890
Cad é an t-am a reáchtáil ar an algartam?

109
00:07:05,890 --> 00:07:08,110
Bhuel, a ligean ar breathnú ar an tionchar seo.

110
00:07:08,110 --> 00:07:10,380
Táimid ag aistriú gach eilimint.

111
00:07:10,380 --> 00:07:16,800
Nuair seo a bhaint i, táimid ag aistriú na heilimintí go léir tar éis é a ar an taobh clé.

112
00:07:16,800 --> 00:07:21,600
Agus is é sin an (n) O costas

113
00:07:21,600 --> 00:07:26,100
mar gheall ar cad má táimid réidh leis an chéad eilimint?

114
00:07:26,100 --> 00:07:29,670
Mar sin, le haghaidh gach aistriú, ní mór dúinn a bhaint -

115
00:07:29,670 --> 00:07:32,170
dtabhóidh gach aistriú a (n) O oibriú,

116
00:07:32,170 --> 00:07:41,520
agus ós rud é tá muid removals n, a thugann sé sin le (n ^ 2) Suaitheadh ​​O.

117
00:07:41,520 --> 00:07:49,550
Maith go leor. Mar sin tús maith. Tús maith.

118
00:07:49,550 --> 00:07:55,290
>> Tá moladh eile a úsáid rud éigin ar a dtugtar an Suaitheadh ​​Knuth,

119
00:07:55,290 --> 00:07:57,540
nó an Suaitheadh ​​Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
Agus tá sé i ndáiríre Suaitheadh ​​am líneach.

121
00:07:59,630 --> 00:08:02,200
Agus is é an smaoineamh an-chosúil.

122
00:08:02,200 --> 00:08:05,160
Arís, ní mór dúinn ár raon ionchur,

123
00:08:05,160 --> 00:08:08,580
ach seachas úsáid a bhaint dhá arrays le haghaidh ár n-ionchur / aschur,

124
00:08:08,580 --> 00:08:13,590
úsáidimid an chuid chéad an sraith súil a choinneáil ar ár sciar shuffled,

125
00:08:13,590 --> 00:08:18,400
agus táimid ag súil a choinneáil ar, agus ansin fág an chuid eile den ár sraith againn don chuid unshuffled.

126
00:08:18,400 --> 00:08:24,330
Mar sin, tá anseo cad is ciall agam. Tús a chur againn amach le - a roghnú againn i,

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

128
00:08:30,910 --> 00:08:36,150
Is é ár pointeoir atá ann faoi láthair atá dírithe ar an innéacs ar dtús.

129
00:08:36,150 --> 00:08:39,590
Roghnú muid roinnt anseo i

130
00:08:39,590 --> 00:08:42,740
agus anois táimid ag babhtála.

131
00:08:42,740 --> 00:08:47,690
Mar sin, má ba é seo 5 agus bhí sé seo 4,

132
00:08:47,690 --> 00:08:57,150
Beidh an sraith de thoradh a bheith 5 anseo agus 4 anseo.

133
00:08:57,150 --> 00:09:00,390
Agus anois faoi deara againn marcóir anseo.

134
00:09:00,390 --> 00:09:05,770
Tá gach rud ar an taobh clé shuffled,

135
00:09:05,770 --> 00:09:15,160
agus tá gach rud ar dheis unshuffled.

136
00:09:15,160 --> 00:09:17,260
Agus anois is féidir linn arís ar an bpróiseas.

137
00:09:17,260 --> 00:09:25,210
Roghnú againn innéacs randamach idir 1 agus 20 anois.

138
00:09:25,210 --> 00:09:30,650
Mar sin, is dócha ár nua atá i anseo.

139
00:09:30,650 --> 00:09:39,370
Anois táimid ag babhtáil seo i lenár phost nua atá ann faoi láthair anseo.

140
00:09:39,370 --> 00:09:44,790
Mar sin, is féidir linn a mhalartú ar ais agus amach é seo.

141
00:09:44,790 --> 00:09:51,630
Lig dom a thabhairt suas an cód chun é a dhéanamh níos nithiúla.

142
00:09:51,630 --> 00:09:55,290
Tús a chur againn lenár rogha i -

143
00:09:55,290 --> 00:09:58,370
tús a chur againn le cothrom liom a 0, ní mór dúinn a roghnú j suíomh randamach

144
00:09:58,370 --> 00:10:02,420
sa chuid unshuffled an eagar, a i n-1.

145
00:10:02,420 --> 00:10:07,280
Mar sin má tá mé anseo, a roghnú innéacs randamach idir anseo agus an chuid eile den eagar,

146
00:10:07,280 --> 00:10:12,410
agus táimid mhalartú.

147
00:10:12,410 --> 00:10:17,550
Is é seo go léir ar an gcód is gá chun Suaitheadh ​​do eagar.

148
00:10:17,550 --> 00:10:21,670
Ceisteanna ar bith?

149
00:10:21,670 --> 00:10:25,530
>> Bhuel, is gá ceist amháin go bhfuil, cén fáth seo ceart?

150
00:10:25,530 --> 00:10:28,360
Cén fáth go bhfuil gach permutation chomh dóchúil?

151
00:10:28,360 --> 00:10:30,410
Agus ní bheidh mé ag dul tríd an cruthúnas ar seo,

152
00:10:30,410 --> 00:10:35,970
ach is féidir go leor fadhbanna san eolaíocht ríomhaireachta a chruthú trí ionduchtú.

153
00:10:35,970 --> 00:10:38,520
Cé mhéad de tú eolach ar ionduchtaithe?

154
00:10:38,520 --> 00:10:40,590
Maith go leor. Cool.

155
00:10:40,590 --> 00:10:43,610
Mar sin, is féidir leat a chruthú ar an cruinneas an algartam trí ionduchtú simplí,

156
00:10:43,610 --> 00:10:49,540
i gcás ina mbeadh do hipitéis ionduchtaithe a bheith, glacadh leis go

157
00:10:49,540 --> 00:10:53,290
ar ais ar mo Suaitheadh ​​gach seans go cothrom permutation

158
00:10:53,290 --> 00:10:56,120
suas go dtí na heilimintí i dtús.

159
00:10:56,120 --> 00:10:58,300
Anois, a mheas i + 1.

160
00:10:58,300 --> 00:11:02,550
Agus ag an mbealach a roghnaímid ár j innéacs a mhalartú,

161
00:11:02,550 --> 00:11:05,230
seo mar thoradh ar - agus ansin tú ag obair amach na sonraí,

162
00:11:05,230 --> 00:11:07,390
ar a laghad cruthúnas iomlán cén fáth ar ais an algartam

163
00:11:07,390 --> 00:11:12,800
gach permutation le dóchúlacht chomh dócha.

164
00:11:12,800 --> 00:11:15,940
>> Gach ceart, fadhb eile.

165
00:11:15,940 --> 00:11:19,170
"Mar sin, tugadh le sraith de slánuimhreacha, postive, náid, diúltach,

166
00:11:19,170 --> 00:11:21,290
scríobh feidhm a ríomh, ríomhann an tsuim uasta

167
00:11:21,290 --> 00:11:24,720
d'aon subarray continueous an eagar ionchuir. "

168
00:11:24,720 --> 00:11:28,370
Is sampla anseo, i gcás ina bhfuil gach uimhreacha deimhneacha,

169
00:11:28,370 --> 00:11:31,320
ansin faoi láthair ar an rogha is fearr a chur ar an eagar ar fad.

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

171
00:11:34,690 --> 00:11:36,780
Nuair a bheidh tú roinnt negatives in ann,

172
00:11:36,780 --> 00:11:38,690
sa chás seo ba mhaith linn ach an chéad dá

173
00:11:38,690 --> 00:11:44,590
mar go mbeidh a roghnú -1 agus / nó -3 thabhairt ar ár suim síos.

174
00:11:44,590 --> 00:11:48,120
Uaireanta, d'fhéadfadh muid a bheith chun tús a chur i lár an eagar.

175
00:11:48,120 --> 00:11:53,500
Uaireanta, ba mhaith linn a roghnú aon rud ar chor ar bith; tá sé is fearr chun a ghlacadh rud ar bith.

176
00:11:53,500 --> 00:11:56,490
Agus uaireanta tá sé níos fearr a chur ar an titim,

177
00:11:56,490 --> 00:12:07,510
toisc go bhfuil an rud tar éis é a Super mór. Mar sin, aon smaointe?

178
00:12:07,510 --> 00:12:10,970
(Mac léinn, dothuigthe) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
Cuir Ní féidir liom a ghlacadh -1.

180
00:12:13,560 --> 00:12:16,170
Ansin, ceachtar roghnaigh mé 1,000 agus 20,000,

181
00:12:16,170 --> 00:12:18,630
nó I roghnú ach an 3 billiún.

182
00:12:18,630 --> 00:12:20,760
Bhuel, tá an rogha is fearr a ghlacadh na huimhreacha go léir.

183
00:12:20,760 --> 00:12:24,350
Seo -1, in ainneoin a bheith diúltach,

184
00:12:24,350 --> 00:12:31,340
Is é an tsuim iomlán níos fearr ná mar a bhí mé a ghlacadh -1.

185
00:12:31,340 --> 00:12:36,460
Mar sin, bhí ar cheann de na leideanna luaigh mé níos luaithe a lua soiléir go soiléir

186
00:12:36,460 --> 00:12:40,540
agus ar an réiteach bhfeidhm brute ar dtús.

187
00:12:40,540 --> 00:12:44,340
Cad é an réiteach bhfeidhm brute sa fhadhb seo? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Bhuel, Sílim go bhfuil an réiteach bhfeidhm brute

189
00:12:46,890 --> 00:12:52,600
Bheadh ​​a chur suas go léir na teaglamaí féideartha (dothuigthe).

190
00:12:52,600 --> 00:12:58,250
[Yu] Maith go leor. Dá bhrí sin tá smaoineamh Jane a thógáil gach is féidir -

191
00:12:58,250 --> 00:13:01,470
Tá mé paraphrasing - Is é a thógáil gach subarray is féidir leanúnach,

192
00:13:01,470 --> 00:13:07,840
ríomh a suim, agus ansin an t-uasmhéid de na subarrays féidir leanúnach a ghlacadh.

193
00:13:07,840 --> 00:13:13,310
Cad a aithníonn uathúil a subarray i mo sraith ionchur?

194
00:13:13,310 --> 00:13:17,380
Cosúil, cad dhá rud atá de dhíth orm? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Mac léinn, dothuigthe) An ceart. >>

196
00:13:19,970 --> 00:13:22,130
A níos ísle cheangal ar an innéacs agus innéacs uachtair faoi cheangal

197
00:13:22,130 --> 00:13:28,300
uathúil chinneann subarray leanúnach.

198
00:13:28,300 --> 00:13:31,400
[Mac léinn Mná] An bhfuil meastachán a dhéanamh ar againn tá sé le sraith de uimhreacha ar leith?

199
00:13:31,400 --> 00:13:34,280
[Yu] Uimh Tá Mar sin, a cheist, ag glacadh leis muid ár sraith -

200
00:13:34,280 --> 00:13:39,000
Is é ár n-eagar gach uimhir ar leith, agus is é an freagra ar bith.

201
00:13:39,000 --> 00:13:43,390
>> Má úsáidimid ár réiteach bhfeidhm brute, ansin na hinnéacsanna tús / deireadh

202
00:13:43,390 --> 00:13:47,200
uathúil Cinneann ár subarray leanúnach.

203
00:13:47,200 --> 00:13:51,680
Mar sin, má táimid iterate do gach iontráil tús is féidir,

204
00:13:51,680 --> 00:13:58,320
agus le haghaidh gach iontráil deireadh> nó = a thosú, agus <n,

205
00:13:58,320 --> 00:14:05,570
ríomh tú an tsuim, agus ansin dúinn a chur ar an tsuim uasta againn le feiceáil go dtí seo.

206
00:14:05,570 --> 00:14:07,880
An bhfuil sé seo soiléir?

207
00:14:07,880 --> 00:14:12,230
Cad é an O mór an réiteach?

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

209
00:14:16,660 --> 00:14:18,860
Ní leor n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Tabhair faoi deara go bhfuil muid iterate ó 0 go n,

211
00:14:25,250 --> 00:14:27,520
mar sin go ceann amháin le haghaidh lúb.

212
00:14:27,520 --> 00:14:35,120
Táimid iterate arís ó thús beagnach go deireadh, ceann eile le haghaidh lúb.

213
00:14:35,120 --> 00:14:37,640
Agus anois, ina theannta sin, ní mór dúinn a suim suas gach iontráil,

214
00:14:37,640 --> 00:14:43,810
mar sin tá go ceann eile le haghaidh lúb. Mar sin, ní mór dúinn trí neadaithe do lúb, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Maith go leor. Téann sé seo mar phointe tosaigh.

216
00:14:46,560 --> 00:14:53,180
Is é ár réiteach aon níos measa ná n ^ 3.

217
00:14:53,180 --> 00:14:55,480
An bhfuil gach duine a thuiscint an réiteach bhfeidhm brute?

218
00:14:55,480 --> 00:14:59,950
>> Maith go leor. Tá réiteach níos fearr ag baint úsáide as smaoineamh ar a dtugtar cláir dinimiciúil.

219
00:14:59,950 --> 00:15:03,040
Má tá tú CS124, a bhfuil halgartaim agus Struchtúir Sonraí,

220
00:15:03,040 --> 00:15:05,680
beidh tú a bheith an-eolach ar an teicníc.

221
00:15:05,680 --> 00:15:12,190
Agus is é an smaoineamh, déan iarracht a thógáil suas ar réitigh ar fhadhbanna níos lú ar dtús.

222
00:15:12,190 --> 00:15:17,990
Cad a chiallaíonn mé ag an bhfuil sé seo, atá againn faoi láthair a bheith buartha faoi dhá rud: tús agus deireadh.

223
00:15:17,990 --> 00:15:29,340
Agus sin annoying. Cad a tharlaíonn má d'fhéadfadh muid a fháil haitheantas coibhneasta de cheann amháin de na paraiméadair?

224
00:15:29,340 --> 00:15:32,650
Tá smaoineamh amháin go - we're tugadh ár fhadhb bunaidh,

225
00:15:32,650 --> 00:15:37,470
teacht ar an tsuim uasta aon subarray i raon [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Agus anois táimid tar éis subproblem nua, nuair a fhios againn, inár innéacs reatha i,

227
00:15:47,400 --> 00:15:52,520
tá a fhios againn ní mór dúinn i gcrích ann. Ní mór ár subarray deireadh ag an t-innéacs reatha.

228
00:15:52,520 --> 00:15:57,640
Dá bhrí sin tá an fhadhb atá fágtha, ba chóir áit linn tús ár subarray?

229
00:15:57,640 --> 00:16:05,160
An bhfuil an ciall a bhaint as? Maith go leor.

230
00:16:05,160 --> 00:16:12,030
Mar sin, tá mé códaithe seo suas, agus a ligean ar breathnú ar cad a chiallaíonn sé.

231
00:16:12,030 --> 00:16:16,230
Sa codirectory, níl clár ar a dtugtar subarray,

232
00:16:16,230 --> 00:16:19,470
agus tógann sé líon na míreanna,

233
00:16:19,470 --> 00:16:25,550
agus tugann sé an tsuim subarray uasta i mo liosta shuffled.

234
00:16:25,550 --> 00:16:29,920
Mar sin, sa chás seo, is é ár subarray uasta 3.

235
00:16:29,920 --> 00:16:34,850
Agus tá a tógadh ag díreach ag baint úsáide as 2 agus 1.

236
00:16:34,850 --> 00:16:38,050
A ligean ar siúl arís. Tá sé freisin 3.

237
00:16:38,050 --> 00:16:40,950
Ach an uair seo, faoi deara conas a fuair muid an 3.

238
00:16:40,950 --> 00:16:46,690
Chuir muid an - táimid a ghlacadh ach na 3 féin

239
00:16:46,690 --> 00:16:49,980
toisc go bhfuil sé timpeallaithe ag negatives ar an dá thaobh,

240
00:16:49,980 --> 00:16:55,080
a thabharfaidh suim <3.

241
00:16:55,080 --> 00:16:57,820
A ligean ar siúl ar 10 míreanna.

242
00:16:57,820 --> 00:17:03,200
An uair seo tá sé 7, a chur orainn an 3 rá agus 4.

243
00:17:03,200 --> 00:17:09,450
An uair seo tá sé 8, agus muid a fháil go trí 1, 4 agus 3.

244
00:17:09,450 --> 00:17:16,310
Mar sin, a thabhairt duit ar intuition ar conas is féidir linn a fhadhb seo a réiteach a chlaochlú,

245
00:17:16,310 --> 00:17:18,890
a ligean ar ghlacadh le breathnú ar an subarray.

246
00:17:18,890 --> 00:17:23,460
Táimid tugtha seo sraith ionchur, agus tá a fhios againn go bhfuil an freagra 8.

247
00:17:23,460 --> 00:17:26,359
Glacann muid ar an 1, 4, agus 3.

248
00:17:26,359 --> 00:17:29,090
Ach a ligean ar breathnú ar conas a fuair muid i ndáiríre go fhreagra.

249
00:17:29,090 --> 00:17:34,160
A ligean ar breathnú ar an subarray uasta a chríochnaigh ag gach ceann de na innéacsanna.

250
00:17:34,160 --> 00:17:40,780
Cad é an subarray uasta go bhfuil deireadh ag ionad an chéad?

251
00:17:40,780 --> 00:17:46,310
[Mac Léinn] nialais. >> Nialais. Ní Just a dhéanamh a chur ar an -5.

252
00:17:46,310 --> 00:17:50,210
Anseo tá sé ag dul a bheith 0 chomh maith. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Do mhic léinn, dothuigthe)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, tá brón orainn, tá sé -3.

255
00:17:58,960 --> 00:18:03,220
Mar sin, tá sé seo le 2, tá sé seo -3.

256
00:18:03,220 --> 00:18:08,690
Maith go leor. Mar sin, -4 tá, cad é an subarray uasta chun deireadh a phost sin

257
00:18:08,690 --> 00:18:12,910
áit a bhfuil -4 ag? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Anois, caithfidh mé deireadh ag an suíomh ina bhfuil -2 ag.

260
00:18:28,060 --> 00:18:39,330
Mar sin 6, 5, 7, agus an ceann deireanach 4.

261
00:18:39,330 --> 00:18:43,480
A fhios agam go bhfuil na mo iontrálacha

262
00:18:43,480 --> 00:18:48,130
chun an fhadhb a chlaochlú ina Caithfidh mé deireadh ag gach ceann de na innéacsanna,

263
00:18:48,130 --> 00:18:51,410
ansin tá mo freagra deiridh ach, a chur le sweep ar fud,

264
00:18:51,410 --> 00:18:53,580
agus a chur ar an líon uasta.

265
00:18:53,580 --> 00:18:55,620
Mar sin, sa chás seo tá sé 8.

266
00:18:55,620 --> 00:19:00,010
Ciallaíonn sé seo go deireadh an subarray uasta ag an innéacs,

267
00:19:00,010 --> 00:19:04,970
agus thosaigh sé áit éigin os a chomhair.

268
00:19:04,970 --> 00:19:09,630
An bhfuil gach duine a thuiscint seo subarray chlaochlú?

269
00:19:09,630 --> 00:19:22,160
>> Maith go leor. Bhuel, a ligean ar an figiúr amach an atarlú seo.

270
00:19:22,160 --> 00:19:27,990
Ligean ar a mheas ach an chéad chúpla iontrálacha.

271
00:19:27,990 --> 00:19:35,930
Mar sin anseo a bhí sé 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Agus ansin bhí -2 anseo, agus a thug sé síos go dtí 6.

273
00:19:39,790 --> 00:19:50,800
Mar sin, má ghlaonn mé an iontráil ag seasamh i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
conas is féidir liom an freagra a úsáid chun a subproblem roimhe seo

275
00:19:54,910 --> 00:19:59,360
chun an cheist seo subproblem?

276
00:19:59,360 --> 00:20:04,550
Má mé ag amharc ar, a ligean le rá, an iontráil seo.

277
00:20:04,550 --> 00:20:09,190
Conas is féidir liom a ríomh an freagra 6 trí bhreathnú ar

278
00:20:09,190 --> 00:20:18,780
meascán de seo, eagar agus na freagraí ar subproblems roimhe seo eagar? Tá?

279
00:20:18,780 --> 00:20:22,800
[Mac léinn Mná] a ghlacadh tú an sraith de shuimeanna

280
00:20:22,800 --> 00:20:25,430
sa suíomh ceart os a comhair, mar sin na 8,

281
00:20:25,430 --> 00:20:32,170
agus ansin cuir tú ar an subproblem reatha.

282
00:20:32,170 --> 00:20:36,460
[Yu] Mar sin, tá sí moladh ag féachaint ar na dhá uimhir,

283
00:20:36,460 --> 00:20:40,090
an uimhir seo agus an líon sin.

284
00:20:40,090 --> 00:20:50,130
Mar sin, tagraíonn sé seo 8 an freagra don subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Agus a ligean ar glaoch ar mo A. sraith ionchur

286
00:20:57,300 --> 00:21:01,470
D'fhonn a fháil ar subarray uasta a chríochnaíonn ag seasamh i,

287
00:21:01,470 --> 00:21:03,980
Tá mé dhá rogha: Is féidir liom leanúint ar aghaidh ceachtar an subarray

288
00:21:03,980 --> 00:21:09,790
a chríochnaigh ar an t-innéacs roimhe sin, nó tús a chur le sraith nua.

289
00:21:09,790 --> 00:21:14,190
Má bhí mé a leanúint ar an subarray a thosaigh ag an t-innéacs roimhe sin,

290
00:21:14,190 --> 00:21:19,260
ansin tá an tsuim uasta is féidir liom a bhaint amach freagra na subproblem roimhe seo

291
00:21:19,260 --> 00:21:24,120
móide an iontráil eagar atá ann faoi láthair.

292
00:21:24,120 --> 00:21:27,550
Ach, tá mé freisin an rogha a thosú subarray nua,

293
00:21:27,550 --> 00:21:30,830
agus sa chás sin an tsuim 0.

294
00:21:30,830 --> 00:21:42,860
Mar sin, tá an freagra uasta de 0, subproblem i - 1, móide an iontráil eagar atá ann faoi láthair.

295
00:21:42,860 --> 00:21:46,150
An bhfuil an atarlú ciall?

296
00:21:46,150 --> 00:21:50,840
Ár atarlú, mar a fuair sé amach againn ach tá subproblem i

297
00:21:50,840 --> 00:21:54,740
is comhionann leis an t-uasmhéid an subproblem roimhe móide mo iontráil eagar atá ann faoi láthair,

298
00:21:54,740 --> 00:22:01,490
rud a chiallaíonn leanúint ar aghaidh leis subarray roimhe sin,

299
00:22:01,490 --> 00:22:07,250
nó 0, tús a chur le subarray nua ar mo innéacs reatha.

300
00:22:07,250 --> 00:22:10,060
Agus nuair a ní mór dúinn tógtha suas an tábla seo na réitigh, ansin is é ár freagra deiridh,

301
00:22:10,060 --> 00:22:13,950
ach a dhéanamh ar sweep líneach ar fud an raon subproblem

302
00:22:13,950 --> 00:22:19,890
agus a chur ar an líon uasta.

303
00:22:19,890 --> 00:22:23,330
Is é seo an cur i bhfeidhm beacht cad a dúirt mé díreach.

304
00:22:23,330 --> 00:22:27,320
Mar sin, táimid a chruthú sraith subproblem nua, subproblems.

305
00:22:27,320 --> 00:22:32,330
Is é an chéad iontráil ceachtar 0 nó an chéad iontráil, an t-uasmhéid den dá.

306
00:22:32,330 --> 00:22:35,670
Agus don chuid eile de na subproblems

307
00:22:35,670 --> 00:22:39,810
úsáidimid an atarlú cruinn amach againn ach.

308
00:22:39,810 --> 00:22:49,960
Anois táimid ag ríomh an t-uasmhéid ar ár sraith subproblems, agus gur ar ár freagra deiridh.

309
00:22:49,960 --> 00:22:54,130
>> Mar sin, cé mhéad spás atá in úsáid againn sa algartam?

310
00:22:54,130 --> 00:23:01,470
Má tá tú ag glacadh ach CS50, ansin ní bheadh ​​agat a phlé spás mór.

311
00:23:01,470 --> 00:23:07,750
Bhuel, tá rud amháin a thabhairt faoi deara gur iarr mé malloc anseo le n méid.

312
00:23:07,750 --> 00:23:13,590
Cad a dhéanann a mholadh a thabhairt duit?

313
00:23:13,590 --> 00:23:17,450
Úsáideann an algartam spás líneach.

314
00:23:17,450 --> 00:23:21,030
An féidir linn a dhéanamh níos fearr?

315
00:23:21,030 --> 00:23:30,780
An bhfuil aon rud go tú faoi deara go bhfuil gá a ríomh an freagra deiridh?

316
00:23:30,780 --> 00:23:33,290
Buille faoi thuairim mé go bhfuil ceist níos fearr, cén t-eolas

317
00:23:33,290 --> 00:23:40,680
ní mór dúinn a dhéanamh an bealach ar fad tríd go dtí an deireadh?

318
00:23:40,680 --> 00:23:44,280
Anois, má táimid ar an dá línte seo,

319
00:23:44,280 --> 00:23:47,720
linn cúram ach thart ar an subproblem roimhe sin,

320
00:23:47,720 --> 00:23:50,910
agus muid cúram ach thart ar an t-uasmhéid againn atá feicthe riamh go dtí seo.

321
00:23:50,910 --> 00:23:53,610
A ríomh ar ár freagra deiridh, ní mór dúinn an eagar ar fad.

322
00:23:53,610 --> 00:23:57,450
Againn ach is gá an líon seo caite, anuas dhá uimhir.

323
00:23:57,450 --> 00:24:02,630
Uimhir seo caite le haghaidh an sraith subproblem, agus uimhir caite le haghaidh an t-uasmhéid.

324
00:24:02,630 --> 00:24:07,380
Mar sin, i ndáiríre, is féidir linn a fuse na lúb le chéile

325
00:24:07,380 --> 00:24:10,460
agus dul ó spás líneach le spás leanúnach.

326
00:24:10,460 --> 00:24:15,830
Tsuim atá ann faoi láthair go dtí seo, anseo in ionad an ról subproblem, ár eagar subproblem.

327
00:24:15,830 --> 00:24:20,020
Tsuim sin atá ann faoi láthair, a mhéid, is é an freagra ar an subproblem roimhe sin.

328
00:24:20,020 --> 00:24:23,450
Agus an tsuim sin, go dtí seo, glacann an áit a bhí ár max.

329
00:24:23,450 --> 00:24:28,100
Ríomh againn an t-uasmhéid mar a théann muid chomh maith.

330
00:24:28,100 --> 00:24:30,890
Agus mar sin a théann muid ó spás líneach spás leanúnach,

331
00:24:30,890 --> 00:24:36,650
agus ní mór dúinn freisin ar réiteach líneach ar ár fhadhb subarray.

332
00:24:36,650 --> 00:24:40,740
>> Tá na cineálacha ceisteanna a gheobhaidh tú le linn agallaimh.

333
00:24:40,740 --> 00:24:44,450
Cad é an chastacht am; cad é an chastacht spáis?

334
00:24:44,450 --> 00:24:50,600
An féidir leat a dhéanamh níos fearr? An bhfuil rudaí a bhfuil gá leo a choinneáil ar fud?

335
00:24:50,600 --> 00:24:55,270
Rinne mé seo aird a tharraingt ar anailísí gur chóir duit a chur ar do chuid féin

336
00:24:55,270 --> 00:24:57,400
mar a tá tú ag obair trí mheán na fadhbanna seo.

337
00:24:57,400 --> 00:25:01,710
I gcónaí a iarraidh ort féin, "An féidir liom a dhéanamh níos fearr?"

338
00:25:01,710 --> 00:25:07,800
Go deimhin is féidir, ní mór dúinn a dhéanamh níos fearr ná é seo?

339
00:25:07,800 --> 00:25:10,730
Sórtáil de cheist trick. Ní féidir leat, mar is gá duit

340
00:25:10,730 --> 00:25:13,590
ar a laghad, a léamh an t-ionchur ar an bhfadhb.

341
00:25:13,590 --> 00:25:15,570
Mar sin, ar an bhfíric gur gá duit ar a laghad an t-ionchur a léamh ar an bhfadhb

342
00:25:15,570 --> 00:25:19,580
Ciallaíonn sé seo nach féidir leat a dhéanamh níos fearr ná am líneach,

343
00:25:19,580 --> 00:25:22,870
agus ní féidir leat a dhéanamh níos fearr ná spás leanúnach.

344
00:25:22,870 --> 00:25:27,060
Mar sin, tá sé seo, i ndáiríre, an réiteach is fearr chun an fhadhb seo.

345
00:25:27,060 --> 00:25:33,040
Ceisteanna? Maith go leor.

346
00:25:33,040 --> 00:25:35,190
>> Fhadhb margadh stoc:

347
00:25:35,190 --> 00:25:38,350
"Mar gheall ar sraith de slánuimhreacha n, dearfach, náid, nó diúltach,

348
00:25:38,350 --> 00:25:41,680
a léiríonn an praghas ar stoc thar laethanta n,

349
00:25:41,680 --> 00:25:44,080
scríobh feidhm a ríomh ar an brabús mó is féidir leat a dhéanamh

350
00:25:44,080 --> 00:25:49,350
ós rud é go leat a cheannach agus a dhíol go díreach 1 stoc laistigh de na laethanta n. "

351
00:25:49,350 --> 00:25:51,690
Go bunúsach, ba mhaith linn a cheannach íseal, a dhíol ard.

352
00:25:51,690 --> 00:25:58,580
Agus ba mhaith linn a figiúr amach an brabús is fearr is féidir linn a dhéanamh.

353
00:25:58,580 --> 00:26:11,500
Ag dul ar ais go dtí mo tip, cad é an soiléir láithreach, freagra simplí, ach tá sé mall?

354
00:26:11,500 --> 00:26:17,690
Tá? (Mac léinn, dothuigthe) >> Tá.

355
00:26:17,690 --> 00:26:21,470
>> Mar sin, bheadh ​​tú ag dul díreach cé agus breathnú ar na praghsanna stoc

356
00:26:21,470 --> 00:26:30,550
ag gach pointe in am, (dothuigthe).

357
00:26:30,550 --> 00:26:33,990
[Yu] Maith go leor, mar sin a réiteach - a mholadh na ríomhaireachta

358
00:26:33,990 --> 00:26:37,380
nach bhfuil an ísle agus ríomh an líon is airde obair gá

359
00:26:37,380 --> 00:26:42,470
mar a d'fhéadfadh an líon is airde a tharlaíonn roimh an ráta is ísle.

360
00:26:42,470 --> 00:26:47,340
Mar sin, cad é an réiteach bhfeidhm brute ar an bhfadhb seo?

361
00:26:47,340 --> 00:26:53,150
Cad iad an dá rudaí a bhfuil gá dom a chinneadh uathúil an brabús a dhéanamh liom? Ceart.

362
00:26:53,150 --> 00:26:59,410
Is é an réiteach bhfeidhm brute - ó, mar sin, moladh Sheoirse is gá dúinn ach dhá lá

363
00:26:59,410 --> 00:27:02,880
a chinneadh uathúil an brabús de na dhá lá.

364
00:27:02,880 --> 00:27:06,660
Mar sin, táimid ríomh gach péire, cosúil le cheannach / a dhíol,

365
00:27:06,660 --> 00:27:12,850
ríomh brabús, d'fhéadfadh a bheith diúltach nó dearfach nó nialas.

366
00:27:12,850 --> 00:27:18,000
Ríomh an brabús uasta a dhéanamh linn tar éis iterating thar gach péirí lá.

367
00:27:18,000 --> 00:27:20,330
Beidh go bhfuil ár freagra deiridh.

368
00:27:20,330 --> 00:27:25,730
Agus beidh go réiteach O (n ^ 2), toisc go bhfuil n dhá phéire a roghnú -

369
00:27:25,730 --> 00:27:30,270
na laethanta gur féidir leat a roghnú i measc laethanta deiridh.

370
00:27:30,270 --> 00:27:32,580
Maith go leor, mar sin ní mé ag dul chun dul thar an réiteach bhfeidhm brute anseo.

371
00:27:32,580 --> 00:27:37,420
Tá mé ag dul a insint duit go bhfuil an log n réiteach.

372
00:27:37,420 --> 00:27:45,550
Cén algartam bhfuil a fhios agat faoi láthair go bhfuil n log n?

373
00:27:45,550 --> 00:27:50,730
Níl sé ceist trick.

374
00:27:50,730 --> 00:27:54,790
>> Cumaisc saghas. Is Cumaisc saghas n log n,

375
00:27:54,790 --> 00:27:57,760
agus i ndáiríre, tá bealach amháin a réiteach an fhadhb seo a úsáid

376
00:27:57,760 --> 00:28:04,400
chineál saghas merge de smaoineamh ar a dtugtar, i gcoitinne, roinnt agus conquer.

377
00:28:04,400 --> 00:28:07,570
Agus is é an smaoineamh mar seo a leanas.

378
00:28:07,570 --> 00:28:12,400
Ba mhaith leat a ríomh ar an cheannach is fearr / péire a dhíol sa leath chlé.

379
00:28:12,400 --> 00:28:16,480
Faigh an brabús is fearr is féidir leat a dhéanamh, ach leis an chéad n ar feadh dhá lá.

380
00:28:16,480 --> 00:28:19,780
Ansin mian leat a oompute an cheannach is fearr / péire a dhíol ar an leath ceart,

381
00:28:19,780 --> 00:28:23,930
mar sin n deireanach ar feadh dhá lá.

382
00:28:23,930 --> 00:28:32,400
Agus anois tá an cheist, conas is féidir linn a chumasc leis na réitigh ar ais le chéile?

383
00:28:32,400 --> 00:28:36,320
Tá? (Do mhic léinn, dothuigthe)

384
00:28:36,320 --> 00:28:49,890
>> Maith go leor. Mar sin, lig dom a tharraingt pictiúr.

385
00:28:49,890 --> 00:29:03,870
Tá? (George, dothuigthe)

386
00:29:03,870 --> 00:29:06,450
>> Go díreach. Tá réiteach Sheoirse go díreach ceart.

387
00:29:06,450 --> 00:29:10,040
Mar sin, tá a moladh, a ríomh ar dtús leis an is fearr a cheannach / a dhíol péire,

388
00:29:10,040 --> 00:29:16,050
agus a tharlaíonn sa leath chlé, mar sin a ligean glaoch go clé, ar chlé.

389
00:29:16,050 --> 00:29:20,790
Fearr a cheannach / a dhíol péire a tharlaíonn i leath ceart.

390
00:29:20,790 --> 00:29:25,180
Ach má gcomparáid againn ach an dá uimhir, tá muid ag iarraidh an cás

391
00:29:25,180 --> 00:29:30,460
nuair linn a cheannach agus a dhíol anseo áit éigin sa leath ceart.

392
00:29:30,460 --> 00:29:33,810
Cheannach muid sa leath chlé, a dhíol sa leath ceart.

393
00:29:33,810 --> 00:29:38,490
Agus an bealach is fearr a ríomh is fearr a cheannach / a dhíol péire a théann trasna an dá leath

394
00:29:38,490 --> 00:29:43,480
Is é a ríomh an t-íosmhéid anseo agus an t-uasmhéid a ríomh anseo

395
00:29:43,480 --> 00:29:45,580
agus a gcuid difríocht.

396
00:29:45,580 --> 00:29:50,850
Mar sin, an dá gcásanna ina dtarlaíonn an péire a cheannach / a dhíol ach amháin anseo,

397
00:29:50,850 --> 00:30:01,910
ach anseo, nó ar an dá leath sainithe ag na trí uimhreacha.

398
00:30:01,910 --> 00:30:06,450
Mar sin, ár n-algartam a chumasadh ár n-réitigh ar ais le chéile,

399
00:30:06,450 --> 00:30:08,350
ba mhaith linn a ríomh is fearr a cheannach / a dhíol péire

400
00:30:08,350 --> 00:30:13,120
nuair linn a cheannach ar an leath clé agus a dhíol ar an leath ceart.

401
00:30:13,120 --> 00:30:16,740
Agus is é an bealach is fearr chun é sin a dhéanamh a ríomh an praghas is ísle sa chéad leath,

402
00:30:16,740 --> 00:30:20,360
an praghas is airde sa leath ceart, agus a ghlacadh a difríocht.

403
00:30:20,360 --> 00:30:25,390
Is iad na trí bharr sin brabúis, na trí uimhreacha, go dtógfaidh tú an t-uasmhéid de na trí,

404
00:30:25,390 --> 00:30:32,720
agus sin é an brabús is fearr is féidir leat a dhéanamh thar na laethanta seo an chéad agus deiridh.

405
00:30:32,720 --> 00:30:36,940
Seo iad na línte tábhachtacha i dearg.

406
00:30:36,940 --> 00:30:41,160
Is é seo an glao athchúrsach a ríomh an freagra sa leath chlé.

407
00:30:41,160 --> 00:30:44,760
Is é seo an glao athchúrsach a ríomh an freagra sa leath ceart.

408
00:30:44,760 --> 00:30:50,720
Tá an dá le haghaidh lúb ríomh min agus an uas ar an leath chlé agus ar dheis, faoi seach.

409
00:30:50,720 --> 00:30:54,970
Anois liom a ríomh brabús a théann trasna an dá leath,

410
00:30:54,970 --> 00:31:00,530
agus is é an freagra deiridh an t-uasmhéid de na trí.

411
00:31:00,530 --> 00:31:04,120
Maith go leor.

412
00:31:04,120 --> 00:31:06,420
>> Mar sin, cinnte, ní mór dúinn algartam, ach tá an cheist níos mó,

413
00:31:06,420 --> 00:31:08,290
cad é an chastacht am seo?

414
00:31:08,290 --> 00:31:16,190
Agus is é an fáth a luaigh mé merge sórtáil go roinneann an fhoirm seo an freagra

415
00:31:16,190 --> 00:31:19,200
i dhá agus ansin chumasc ár n-réitigh ar ais le chéile

416
00:31:19,200 --> 00:31:23,580
é go díreach an cineál saghas chumaiscthe.

417
00:31:23,580 --> 00:31:33,360
Mar sin, lig dom dul tríd an tréimhse.

418
00:31:33,360 --> 00:31:41,340
Má shainmhínítear muid feidhm t (n) a bheith ar líon na céimeanna

419
00:31:41,340 --> 00:31:50,010
le haghaidh laethanta n,

420
00:31:50,010 --> 00:31:54,350
ár dhá glaonna recursive

421
00:31:54,350 --> 00:32:00,460
Tá gach dul chun costas t (n / 2),

422
00:32:00,460 --> 00:32:03,540
agus tá dhá cheann de na glaonna.

423
00:32:03,540 --> 00:32:10,020
Anois, is gá dom a ríomh an t-íosmhéid de leath chlé,

424
00:32:10,020 --> 00:32:17,050
inar féidir liom a dhéanamh i n / 2 am, móide an t-uasmhéid leath ceart.

425
00:32:17,050 --> 00:32:20,820
Mar sin, tá sé seo n go díreach.

426
00:32:20,820 --> 00:32:25,050
Agus ansin chomh maith le roinnt oibre i gcónaí.

427
00:32:25,050 --> 00:32:27,770
Agus an chothromóid atarlú

428
00:32:27,770 --> 00:32:35,560
é go díreach an chothromóid arís le haghaidh saghas chumaiscthe.

429
00:32:35,560 --> 00:32:39,170
Agus tá a fhios againn go léir go bhfuil merge sórtáil n logáil n am.

430
00:32:39,170 --> 00:32:46,880
Dá bhrí sin, is é ár n-algartam freisin log n am.

431
00:32:46,880 --> 00:32:52,220
An bhfuil an leagan ciall?

432
00:32:52,220 --> 00:32:55,780
Just a recap gairid seo:

433
00:32:55,780 --> 00:32:59,170
Is é T (n) líon na céimeanna a ríomh ar an brabús uasta

434
00:32:59,170 --> 00:33:02,750
le linn na laethanta n.

435
00:33:02,750 --> 00:33:06,010
An bealach scoilt muid suas ár glaonna recursive

436
00:33:06,010 --> 00:33:11,980
Is trí ghlaoch ar ár réiteach ar na laethanta n / 2 an chéad,

437
00:33:11,980 --> 00:33:14,490
ionas go bhfuil ceann glaoch,

438
00:33:14,490 --> 00:33:16,940
agus ansin tugaimid arís ar an dara leath.

439
00:33:16,940 --> 00:33:20,440
Mar sin, go dhá ghlaoch.

440
00:33:20,440 --> 00:33:25,310
Agus ansin a fháil againn ar a laghad ar an leath chlé, is féidir linn a dhéanamh in am líneach,

441
00:33:25,310 --> 00:33:29,010
teacht ar an uasmhéid an leath ceart, is féidir linn a dhéanamh in am líneach.

442
00:33:29,010 --> 00:33:31,570
Mar sin, n / 2 Is é + n / 2 ach n.

443
00:33:31,570 --> 00:33:36,020
Ansin tá roinnt oibre leanúnach, atá cosúil a dhéanamh uimhríocht.

444
00:33:36,020 --> 00:33:39,860
Is é seo an chothromóid atarlú go díreach ar an chothromóid arís le haghaidh saghas chumaiscthe.

445
00:33:39,860 --> 00:33:55,490
Dá réir sin, is é ár algartam Suaitheadh ​​freisin n logáil n.

446
00:33:55,490 --> 00:33:58,520
Mar sin, cé mhéad spás atá in úsáid againn?

447
00:33:58,520 --> 00:34:04,910
A ligean ar dul ar ais chuig an gcód.

448
00:34:04,910 --> 00:34:09,420
>> Tá ceist níos fearr, cé mhéad frámaí Stack bhfuil againn riamh ag aon am ar leith?

449
00:34:09,420 --> 00:34:11,449
Ós rud é go bhfuil muid ag baint úsáide as athchúrsáil,

450
00:34:11,449 --> 00:34:23,530
chinneann líon na frámaí chairn ár úsáid spáis.

451
00:34:23,530 --> 00:34:29,440
Ligean ar a mheas n = 8.

452
00:34:29,440 --> 00:34:36,889
Glaoch orainn Suaitheadh ​​ar 8,

453
00:34:36,889 --> 00:34:41,580
a ghlaoch Suaitheadh ​​ar na ceithre hiontrálacha,

454
00:34:41,580 --> 00:34:46,250
a glaoch ar Suaitheadh ​​ar an dá iontráil ar dtús.

455
00:34:46,250 --> 00:34:51,550
Mar sin, is é ár Stack - is é seo ár n-chairn.

456
00:34:51,550 --> 00:34:54,980
Agus ansin tugaimid Suaitheadh ​​arís ar 1,

457
00:34:54,980 --> 00:34:58,070
agus go cad é ár gcás bonn, mar sin againn ar ais láithreach.

458
00:34:58,070 --> 00:35:04,700
An bhfuil muid riamh níos mó ná seo frámaí Stack go leor?

459
00:35:04,700 --> 00:35:08,880
Uimh Mar gheall ar gach uair a dhéanann muid ar agairt,

460
00:35:08,880 --> 00:35:10,770
a agairt athchúrsach le Suaitheadh,

461
00:35:10,770 --> 00:35:13,950
roinnimid ár méid ina dhá leath.

462
00:35:13,950 --> 00:35:17,020
Mar sin, an líon is mó de fhrámaí chairn atá againn riamh ag aon am ar leith

463
00:35:17,020 --> 00:35:28,460
Is ar an ord frámaí log n chairn.

464
00:35:28,460 --> 00:35:42,460
Tá gach fráma Stack spás leanúnach,

465
00:35:42,460 --> 00:35:44,410
agus dá bhrí sin an méid iomlán de spás,

466
00:35:44,410 --> 00:35:49,240
Is é an t-uasmhéid spáis linn a úsáid riamh O (log n) spás

467
00:35:49,240 --> 00:36:03,040
áit a bhfuil n líon na laethanta.

468
00:36:03,040 --> 00:36:07,230
>> Anois, i gcónaí a iarraidh ort féin, "An féidir linn a dhéanamh níos fearr?"

469
00:36:07,230 --> 00:36:12,390
Agus go háirithe, an féidir linn é seo a laghdú go bhfuil fadhb againn réiteach cheana féin?

470
00:36:12,390 --> 00:36:20,040
A leid: plé againn ach dhá fhadhb eile roimhe seo, agus níl sé ag dul a bheith Suaitheadh.

471
00:36:20,040 --> 00:36:26,200
Is féidir linn a thiontú ar an bhfadhb margadh stoc isteach an bhfadhb subarray uasta.

472
00:36:26,200 --> 00:36:40,100
Conas is féidir linn seo a dhéanamh?

473
00:36:40,100 --> 00:36:42,570
Ceann de tú? Emmy?

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

475
00:36:47,680 --> 00:36:53,860
[Yu] díreach.

476
00:36:53,860 --> 00:36:59,940
Mar sin, an fhadhb subarray uasta,

477
00:36:59,940 --> 00:37:10,610
táimid ag lorg suim thar subarray leanúnach.

478
00:37:10,610 --> 00:37:16,230
Agus moladh Emmy don fhadhb stoic,

479
00:37:16,230 --> 00:37:30,720
bhreithniú na n-athruithe, nó deilteanna.

480
00:37:30,720 --> 00:37:37,440
Agus is é an pictiúr seo - is é seo an praghas de stoc,

481
00:37:37,440 --> 00:37:42,610
ach má bhí muid an difríocht idir gach lá as a chéile -

482
00:37:42,610 --> 00:37:45,200
mar sin againn a fheiceáil go bhfuil an praghas uasta, brabús uasta d'fhéadfaí linn a dhéanamh

483
00:37:45,200 --> 00:37:50,070
Is é má táimid a cheannach anseo agus a dhíol anseo.

484
00:37:50,070 --> 00:37:54,240
Ach a ligean ar breathnú ar an leanúnach - ligean ar breathnú ar an bhfadhb subarray.

485
00:37:54,240 --> 00:38:02,510
Mar sin anseo, is féidir linn a dhéanamh - ag dul ó anseo chun anseo,

486
00:38:02,510 --> 00:38:08,410
ní mór dúinn a athrú dearfach, agus ansin dul ó anseo chun anseo ní mór dúinn a athrú diúltach.

487
00:38:08,410 --> 00:38:14,220
Ach ansin, ag dul ó anseo chun anseo ní mór dúinn a athrú ollmhór dearfach.

488
00:38:14,220 --> 00:38:20,930
Agus iad seo na hathruithe a theastaíonn uainn chun achoimre a fháil ar ár brabús deiridh.

489
00:38:20,930 --> 00:38:25,160
Ansin tá athruithe níos diúltaí anseo.

490
00:38:25,160 --> 00:38:29,990
An eochair chun a laghdú ár fhadhb stoc isteach inár fhadhb subarray uasta

491
00:38:29,990 --> 00:38:36,630
Is é a bhreithniú deilteanna idir lá.

492
00:38:36,630 --> 00:38:40,630
Mar sin, táimid a chruthú sraith nua ar a dtugtar deilteanna,

493
00:38:40,630 --> 00:38:43,000
thúsú an chéad iontráil a bheith 0,

494
00:38:43,000 --> 00:38:46,380
agus ansin do gach deilt (i), a ligean ar a bheith ar an difríocht

495
00:38:46,380 --> 00:38:52,830
mo eagar ionchur (i), agus eagar (i - 1).

496
00:38:52,830 --> 00:38:55,530
Ansin tugaimid ár nós imeachta gnáthamh le haghaidh subarray uasta

497
00:38:55,530 --> 00:39:01,500
dul i sraith a deilt ar.

498
00:39:01,500 --> 00:39:06,440
Agus toisc go bhfuil subarray uasta am líneach,

499
00:39:06,440 --> 00:39:09,370
agus an laghdú seo, an próiseas seo a chruthú eagar deilte,

500
00:39:09,370 --> 00:39:11,780
Tá freisin am líneach,

501
00:39:11,780 --> 00:39:19,060
ansin tá an réiteach deiridh le haghaidh stoc O (n) obair móide O (n) obair, fós O (n) obair.

502
00:39:19,060 --> 00:39:23,900
Mar sin, ní mór dúinn a réiteach am líneach ar ár fhadhb.

503
00:39:23,900 --> 00:39:29,610
An bhfuil gach duine a thuiscint athrú seo?

504
00:39:29,610 --> 00:39:32,140
>> Go ginearálta, is smaoineamh maith gur chóir duit a bheith i gcónaí

505
00:39:32,140 --> 00:39:34,290
Tá iarracht a laghdú fadhb nua go bhfuil tú ag féachaint ar.

506
00:39:34,290 --> 00:39:37,700
Má tá sé ar an eolas ar fhadhb d'aois,

507
00:39:37,700 --> 00:39:39,590
déan iarracht a laghdú sé le fadhb d'aois.

508
00:39:39,590 --> 00:39:41,950
Agus más féidir leat é a úsáid go léir na huirlisí go bhfuil tú a úsáidtear ar an bhfadhb d'aois

509
00:39:41,950 --> 00:39:46,450
an fhadhb a réiteach nua.

510
00:39:46,450 --> 00:39:49,010
Mar sin, chun wrap suas, tá agallaimh teicniúla dúshlánach.

511
00:39:49,010 --> 00:39:52,280
Tá na fadhbanna is dócha roinnt de na fadhbanna níos deacra

512
00:39:52,280 --> 00:39:54,700
go mb'fhéidir go mbeadh tú a fheiceáil in agallamh,

513
00:39:54,700 --> 00:39:57,690
mar sin más rud é nach dtuigeann tú na fadhbanna a chlúdaítear mé díreach tar éis, tá sé ceart go leor.

514
00:39:57,690 --> 00:40:01,080
Seo iad roinnt de na fadhbanna níos dúshlánaí.

515
00:40:01,080 --> 00:40:03,050
Cleachtais, cleachtais, cleachtas.

516
00:40:03,050 --> 00:40:08,170
Thug mé a lán de na fadhbanna sa bhileog, mar sin cinnte a sheiceáil amach na.

517
00:40:08,170 --> 00:40:11,690
Agus dea-luck ar do agallaimh. Gach mo acmhainní sa phost ag an nasc seo,

518
00:40:11,690 --> 00:40:15,220
agus tá ceann de mo chairde sinsearach ar fáil a dhéanamh agallaimh teicniúla bréag,

519
00:40:15,220 --> 00:40:22,050
mar sin má tá suim agat, Will r-phost Yao ag an seoladh r-phoist.

520
00:40:22,050 --> 00:40:26,070
Má tá tú roinnt ceisteanna, is féidir leat a iarraidh orm.

521
00:40:26,070 --> 00:40:28,780
An bhfuil tú guys ceisteanna sonracha a bhaineann le hagallaimh teicniúla

522
00:40:28,780 --> 00:40:38,440
nó fadhbanna ar bith againn le feiceáil go dtí seo?

523
00:40:38,440 --> 00:40:49,910
Maith go leor. Bhuel, luck maith ar do agallaimh.

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