1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Alt 3 - Níos Compordach]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Ollscoil Harvard]

3
00:00:05,070 --> 00:00:07,310
>> Is é [seo CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Dá bhrí sin tá an chéad cheist focail strangely.

5
00:00:12,700 --> 00:00:17,480
GDB ligeann duit "dífhabhtaithe" clár, ach, níos mó go sonrach, cad é a ligean a dhéanann tú?

6
00:00:17,480 --> 00:00:22,590
Feicfidh mé freagra sin amháin, agus níl a fhios agam cad atá ag súil leis go díreach,

7
00:00:22,590 --> 00:00:27,910
mar sin tá mé guessing tá sé rud éigin feadh na línte de ligeann tú céim ar chéim

8
00:00:27,910 --> 00:00:31,540
siúl tríd an gclár, idirghníomhú leis, athróga maidir le hathrú, a dhéanann na nithe seo -

9
00:00:31,540 --> 00:00:34,270
go bunúsach rialú go hiomlán i gcrích de chlár

10
00:00:34,270 --> 00:00:38,410
agus iniúchadh a dhéanamh ar aon chuid áirithe de forghníomhú an chláir.

11
00:00:38,410 --> 00:00:43,030
Mar sin a ligean na gnéithe tú rudaí dífhabhtaithe.

12
00:00:43,030 --> 00:00:44,830
Maith go leor.

13
00:00:44,830 --> 00:00:50,520
Cén fáth a bhfuil cuardach dénártha a cheangal go eagar bheith curtha in eagar?

14
00:00:50,520 --> 00:00:53,360
Cé atá ag iarraidh a fhreagairt go?

15
00:00:56,120 --> 00:01:00,070
[Mac léinn] Toisc nach bhfuil sé ag obair más rud é nach bhfuil sé curtha in eagar. >> Yeah. [Gáire]

16
00:01:00,070 --> 00:01:04,910
Más rud é nach bhfuil sé curtha in eagar, ansin tá sé dodhéanta a roinnt i leath

17
00:01:04,910 --> 00:01:07,850
agus tá a fhios go bhfuil gach rud ar an taobh clé níos lú agus gach rud ar dheis

18
00:01:07,850 --> 00:01:10,490
níos mó ná an luach sa lár.

19
00:01:10,490 --> 00:01:12,790
Mar sin, ní mór é a bheith curtha in eagar.

20
00:01:12,790 --> 00:01:14,170
Maith go leor.

21
00:01:14,170 --> 00:01:17,570
Cén fáth go bhfuil saghas mboilgeog i O n cearnógach?

22
00:01:17,570 --> 00:01:23,230
An bhfuil aon duine ag iarraidh an chéad a thabhairt ar an-tapa ard-leibhéal forbhreathnú ar cad is saghas mboilgeog?

23
00:01:25,950 --> 00:01:33,020
[Mac léinn] leat dul go bunúsach trí gach eilimint agus a sheiceáil tú na heilimintí chéad chúpla.

24
00:01:33,020 --> 00:01:37,150
Má tá siad as nuair a mhalartú tú iad, ansin tú ag seiceáil na heilimintí atá amach romhainn agus mar sin de.

25
00:01:37,150 --> 00:01:40,770
Nuair a shroicheann tú an deireadh, ansin a fhios agat go bhfuil an ghné is mó curtha ag an deireadh,

26
00:01:40,770 --> 00:01:42,750
mar sin leat neamhaird a dhéanamh go ceann ansin tú a choinneáil ar ag dul tríd,

27
00:01:42,750 --> 00:01:48,490
agus tá gach am a théann tú a sheiceáil gné amháin níos lú go dtí go ndéanann tú aon athruithe. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Sé ar a dtugtar saghas mboilgeog mar má tá tú smeach an eagar ar a taobh mar sin tá sé suas agus síos, ingearach,

29
00:01:58,470 --> 00:02:03,100
ansin beidh na luachanna mór doirteal go bun agus beidh na luachanna beag mboilgeog suas go dtí an barr.

30
00:02:03,100 --> 00:02:05,210
Sin é an chaoi a fuair sé a ainm.

31
00:02:05,210 --> 00:02:08,220
Agus yeah, leat dul díreach trí.

32
00:02:08,220 --> 00:02:11,190
Tá tú a choinneáil ag dul tríd an eagar, swapping an luach níos mó

33
00:02:11,190 --> 00:02:14,040
leis na luachanna is mó a fháil chun an bun an leathanaigh.

34
00:02:14,040 --> 00:02:17,500
>> Cén fáth go bhfuil sé O n cearnógach?

35
00:02:18,690 --> 00:02:24,620
An chéad, an bhfuil duine ar bith ag iarraidh a rá cén fáth go bhfuil sé O n cearnógach?

36
00:02:24,620 --> 00:02:28,760
[Mac léinn] Mar gheall ar do gach reáchtáil téann sé amanna go n.

37
00:02:28,760 --> 00:02:32,100
Is féidir leat a bheith ach amháin cinnte go atá tú ag glacadh an ghné is mó ar fad ar an mbealach síos,

38
00:02:32,100 --> 00:02:35,230
ansin caithfidh tú a athdhéanamh gur le haghaidh eilimintí mar go leor. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Mar sin a choinneáil i gcuimhne cad a chiallaíonn mór O agus cad iad na modhanna Omega mór.

40
00:02:41,800 --> 00:02:50,560
An O mór is atá cosúil leis an uachtair cheangal ar conas mall féidir é a reáchtáil i ndáiríre.

41
00:02:50,560 --> 00:02:58,990
Mar sin, ag rá tá sé O n cearnógach, nach bhfuil sé O n nó eile go mbeadh sé in ann a reáchtáil

42
00:02:58,990 --> 00:03:02,640
in am líneach, ach tá sé O n cubed

43
00:03:02,640 --> 00:03:06,390
toisc go bhfuil sé teorantach le O n cubed.

44
00:03:06,390 --> 00:03:12,300
Má tá sé teorantach le O n cearnógach, ansin tá sé teoranta freisin n cubed.

45
00:03:12,300 --> 00:03:20,280
Mar sin, tá sé n cearnógach, agus sa chás is measa glan ní féidir é a dhéanamh níos fearr ná n cearnógach,

46
00:03:20,280 --> 00:03:22,830
agus sin an fáth go bhfuil sé O n cearnógach.

47
00:03:22,830 --> 00:03:31,200
Mar sin, a fheiceáil math beag ar an gcaoi a thagann sé amach a bheith n cearnógach,

48
00:03:31,200 --> 00:03:40,530
má táimid tar éis cúig rudaí i ár liosta, an chéad uair cé mhéad malairtí is gá dúinn a d'fhéadfadh a dhéanamh ar

49
00:03:40,530 --> 00:03:47,170
d'fhonn a fháil seo? Lig ndáiríre ach -

50
00:03:47,170 --> 00:03:52,040
Cé mhéad babhtálacha muid ag dul a bheith acu a dhéanamh i rith an chéad saghas mboilgeog tríd an eagar?

51
00:03:52,040 --> 00:03:53,540
[Mac léinn] n - 1. >> Yeah.

52
00:03:53,540 --> 00:03:58,340
>> Má tá 5 heilimintí, tá muid ag dul go mór a dhéanamh ar n - 1.

53
00:03:58,340 --> 00:04:01,100
Ansin, ar an dara ceann cé mhéad babhtálacha muid ag dul a bheith acu a dhéanamh?

54
00:04:01,100 --> 00:04:03,440
[Mac léinn] n - 2. >> Yeah.

55
00:04:03,440 --> 00:04:11,640
Agus is é an tríú dul a bheith n - 3, agus ansin mar áis beidh mé ag scríobh an dá cheann deiridh

56
00:04:11,640 --> 00:04:15,270
mar sin táimid ag dul go dtí gá a dhéanamh 2 babhtálacha agus 1 babhtála.

57
00:04:15,270 --> 00:04:19,899
Buille faoi thuairim mé féidir leis an ceann deireanach nó nach gá iarbhír a tharlóidh.

58
00:04:19,899 --> 00:04:22,820
An bhfuil sé babhtála? Níl a fhios agam.

59
00:04:22,820 --> 00:04:26,490
Mar sin, is iad seo na méideanna iomlána de bhabhtálacha nó ar a laghad comparáidí a bhfuil tú a dhéanamh.

60
00:04:26,490 --> 00:04:29,910
Fiú mura bhfuil tú babhtála, caithfidh tú fós a chur i gcomparáid leis na luachanna.

61
00:04:29,910 --> 00:04:33,910
Mar sin, tá n - 1 comparáidí i rith an chéad trí eagar.

62
00:04:33,910 --> 00:04:42,050
Má tá tú athchóiriú na rudaí seo, a ligean ar a dhéanamh i ndáiríre sé sé sin rudaí rudaí a Stack suas nicely,

63
00:04:42,050 --> 00:04:44,790
agus ansin beidh mé a dhéanamh 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Mar sin, rearranging ach na suimeanna, ba mhaith linn a fheiceáil conas a lán comparáidí a dhéanamh linn

65
00:04:49,910 --> 00:04:52,700
sa algartam ar fad.

66
00:04:52,700 --> 00:04:56,550
Mar sin má a thabhairt dúinn na guys síos anseo,

67
00:04:56,550 --> 00:05:07,470
ansin tá muid fós achoimre ach comparáidí, áfach, go leor go raibh.

68
00:05:07,470 --> 00:05:13,280
Ach má táimid suim na réimsí sin agus suim na againn agus suim na linn,

69
00:05:13,280 --> 00:05:18,130
tá sé fós an fhadhb chéanna. Táimid suim amháin iad siúd grúpaí áirithe.

70
00:05:18,130 --> 00:05:22,400
>> Mar sin anois táimid ag achoimre 3 n ar. Nach bhfuil sé ach 3 n ar.

71
00:05:22,400 --> 00:05:27,650
Tá sé seo ag dul i gcónaí a bheith n / 2 n ar.

72
00:05:27,650 --> 00:05:29,430
Mar sin anseo táimid ag tarlú go bhfuil 6.

73
00:05:29,430 --> 00:05:34,830
Má bhí againn 10 rudaí, ansin d'fhéadfadh muid é seo a ghrúpáil le haghaidh 5 péirí éagsúla chun rudaí

74
00:05:34,830 --> 00:05:37,180
agus deireadh suas le n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Mar sin, tá tú ag dul i gcónaí a fháil ar n / 2 n, agus mar sin seo beidh orainn a bhreacadh sé amach go n cearnaithe / 2.

76
00:05:45,840 --> 00:05:48,890
Agus mar sin cé go bhfuil sé an fachtóir de leath, rud a tharlaíonn le teacht i

77
00:05:48,890 --> 00:05:54,190
mar gheall ar an bhfíric go trí gach leagan thar an eagar comparáid idir 1 níos lú

78
00:05:54,190 --> 00:05:58,040
mar sin tá go conas a fháil againn an os cionn 2, ach tá sé fós n cearnógach.

79
00:05:58,040 --> 00:06:01,650
Ní chuirimid cúram faoi an fachtóir leanúnach go leith.

80
00:06:01,650 --> 00:06:07,760
Mar sin, ag brath a lán rudaí O mór mar seo ar díreach de chineál ar é seo a dhéanamh saghas math,

81
00:06:07,760 --> 00:06:12,260
déanamh suimeanna uimhríochta agus rudaí sraith iolraíoch,

82
00:06:12,260 --> 00:06:17,750
ach tá an chuid is mó acu sa chúrsa seo deas simplí.

83
00:06:17,750 --> 00:06:19,290
Maith go leor.

84
00:06:19,290 --> 00:06:24,430
Cén fáth go bhfuil saghas a chur isteach i Omega n? Cad a dhéanann óimige mean?

85
00:06:24,430 --> 00:06:27,730
[Beirt mhac léinn ag labhairt ag an am céanna - dothuigthe] Yeah. >>

86
00:06:27,730 --> 00:06:30,630
Is féidir Omega leat smaoineamh ar mar is ísle faoi cheangal.

87
00:06:30,630 --> 00:06:36,550
>> Mar sin, is cuma cé chomh éifeachtach go bhfuil do algartam saghas leanas a chur isteach,

88
00:06:36,550 --> 00:06:41,810
beag beann ar an liosta a tá ritheadh ​​i, tá sé i gcónaí a chur i gcomparáid ar a laghad n rudaí

89
00:06:41,810 --> 00:06:44,620
nó má tá sé iterate níos mó ná rudaí n.

90
00:06:44,620 --> 00:06:47,280
Cén fáth go bhfuil sin?

91
00:06:47,280 --> 00:06:51,190
[Mac léinn] Toisc má tá an liosta in eagar cheana féin, ansin tríd an leagan chéad

92
00:06:51,190 --> 00:06:54,080
Is féidir leat a ráthú ach amháin go bhfuil gné an-an chéad a laghad,

93
00:06:54,080 --> 00:06:56,490
agus an dara leagan féidir leat a ráthú ach an chéad dá bhfuil

94
00:06:56,490 --> 00:07:00,010
toisc nach bhfuil a fhios agat go bhfuil an chuid eile den liosta in eagar. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Má éiríonn leat i liosta go hiomlán in eagar, ar a laghad tá tú chun dul thar gach na heilimintí

96
00:07:08,910 --> 00:07:12,180
a fheiceáil go bhfuil aon rud mór a bhogadh timpeall.

97
00:07:12,180 --> 00:07:14,720
Mar sin, dul thar an liosta agus ag rá ó, tá sé seo curtha in eagar cheana féin,

98
00:07:14,720 --> 00:07:18,240
tá sé dodhéanta chun tú a fhios tá sé curtha in eagar go dtí go bhfuil tú ag seiceáil gach eilimint

99
00:07:18,240 --> 00:07:20,660
a fheiceáil go bhfuil siad in ord sórtáilte.

100
00:07:20,660 --> 00:07:25,290
Mar sin, an níos ísle cheangal ar saghas isteach Omega n.

101
00:07:25,290 --> 00:07:28,210
Cad an cás is measa ag rith am saghas merge,

102
00:07:28,210 --> 00:07:31,390
a bheith cás is measa O mór arís?

103
00:07:31,390 --> 00:07:37,660
Mar sin, i cás is measa, conas a chumasadh saghas ar siúl?

104
00:07:42,170 --> 00:07:43,690
[Mac léinn] N log n. >> Yeah.

105
00:07:43,690 --> 00:07:49,990
Is iad na is tapúla halgartaim sórtáil ginearálta n log n. Ní féidir leat a dhéanamh níos fearr.

106
00:07:51,930 --> 00:07:55,130
>> Tá cásanna speisialta, agus má táimid tar éis am lá atá inniu ann - ach tá muid won't is dócha -

107
00:07:55,130 --> 00:07:59,330
féidir linn a fheiceáil amháin go ndéanann níos fearr ná n log n.

108
00:07:59,330 --> 00:08:04,050
Ach sa chás ginearálta, ní féidir leat a dhéanamh níos fearr ná n log n.

109
00:08:04,050 --> 00:08:09,680
Agus a tharlaíonn merge sórtáil le bheith ar an ceann ba chóir a fhios agat ar an gcúrsa seo go bhfuil n log n.

110
00:08:09,680 --> 00:08:13,260
Agus mar sin beidh orainn i ndáiríre a bheith i bhfeidhm go lá atá inniu.

111
00:08:13,260 --> 00:08:18,070
Agus ar deireadh, i níos mó ná trí abairt, conas a dhéanann obair saghas roghnú?

112
00:08:18,070 --> 00:08:20,370
An bhfuil duine éigin ag iarraidh a fhreagairt, agus beidh count do abairtí mé

113
00:08:20,370 --> 00:08:22,390
mar má théann tú thar 3 -

114
00:08:25,530 --> 00:08:28,330
An bhfuil aon duine cuimhneamh saghas roghnú?

115
00:08:31,280 --> 00:08:37,809
Is saghas Roghnú go leor de ghnáth éasca le cuimhneamh ach an t-ainm.

116
00:08:37,809 --> 00:08:45,350
Tá tú iterate díreach os cionn an eagar, a fháil is cuma cad é an luach is mó nó is lú -

117
00:08:45,350 --> 00:08:47,290
cibé ordú a bhfuil tú ag sórtáil isteach

118
00:08:47,290 --> 00:08:50,750
Mar sin a ligean le rá táimid ag sórtáil ó lú go dtí mó.

119
00:08:50,750 --> 00:08:55,250
Tá tú iterate thar an eagar, ag lorg cuma cad é an ghné is lú,

120
00:08:55,250 --> 00:08:59,750
roghnú é, agus ansin babhtála sé ach is cuma cad é sa chéad áit.

121
00:08:59,750 --> 00:09:04,090
Agus ansin ar an pas dara thar an eagar, breathnú ar an ghné íosta arís,

122
00:09:04,090 --> 00:09:07,490
roghnú é, agus ansin é a mhalartú le cad atá sa suíomh dara.

123
00:09:07,490 --> 00:09:10,650
Mar sin, táimid ag ach ag piocadh agus a roghnú na luachanna íosta

124
00:09:10,650 --> 00:09:16,050
agus iad a chur isteach i os comhair an sraith dtí go bhfuil sé curtha in eagar.

125
00:09:19,210 --> 00:09:21,560
Ceisteanna ar sin?

126
00:09:21,560 --> 00:09:25,710
>> Siad seo dosheachanta ar na foirmeacha a bhfuil tú a líonadh amach nuair a bhíonn tú isteach an pset.

127
00:09:29,010 --> 00:09:32,360
Glacfar iad go bunúsach na freagraí ar na.

128
00:09:32,360 --> 00:09:34,230
Maith go leor, mar sin códú anois fadhbanna.

129
00:09:34,230 --> 00:09:40,140
Chuir mé cheana féin níos mó ná ríomhphost - Ní raibh duine ar bith a fháil go r-phost? Maith go leor.

130
00:09:40,140 --> 00:09:46,630
Chuir mé amach cheana féin níos mó ná r-phost an spás go bhfuil muid ag dul a bheith ag baint úsáide as,

131
00:09:46,630 --> 00:09:52,120
agus má dhéanann tú cliceáil ar mo ainm - mar sin mo thuairimse, Tá mé ag dul a bheith ag bun an

132
00:09:52,120 --> 00:09:57,170
mar gheall ar an r ar gcúl - ach má dhéanann tú cliceáil ar mo ainm mbainfidh tú a fheiceáil 2 athbhreithnithe.

133
00:09:57,170 --> 00:10:02,650
Tá Athbhreithniú 1 ag dul go dtí a chóipeáil mé cheana féin agus a ghreamú ar an gcód i Spásanna

134
00:10:02,650 --> 00:10:06,900
chun an rud cuardaigh bhfuil tú ag dul a bheith acu a chur i bhfeidhm.

135
00:10:06,900 --> 00:10:10,540
Agus beidh Athcheartú 2 an rud saghas a chur i bhfeidhm againn ina dhiaidh sin.

136
00:10:10,540 --> 00:10:15,770
Mar sin, is féidir leat cliceáil ar mo Athbhreithniú 1 agus obair ó ann.

137
00:10:17,350 --> 00:10:22,060
Agus anois ba mhaith linn a chur i bhfeidhm cuardaigh dénártha.

138
00:10:22,060 --> 00:10:26,470
>> An bhfuil aon duine ag iarraidh a thabhairt ach pseudocode ardleibhéil míniú

139
00:10:26,470 --> 00:10:31,440
an méid a táimid ag dul a bheith le déanamh ar chuardach? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Mac léinn] Tá tú a ghlacadh ach an lár an eagar agus a fheiceáil má cad tá tú ag lorg

141
00:10:36,170 --> 00:10:38,650
níos lú ná sin nó níos mó ná sin.

142
00:10:38,650 --> 00:10:41,080
Agus má tá sé níos lú, a théann tú chuig an leath sin níos lú,

143
00:10:41,080 --> 00:10:44,750
agus má tá sé níos mó, a théann tú chuig an leath sin níos mó agus arís tú go dtí go mbeidh tú a fháil ach rud amháin.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Yeah.

145
00:10:46,570 --> 00:10:51,320
Fógra go bhfuil ár uimhreacha eagar curtha in eagar cheana féin,

146
00:10:51,320 --> 00:10:57,190
agus mar sin ciallaíonn sé sin go féidir linn leas a bhaint as sin agus d'fhéadfadh muid seiceáil ar dtús,

147
00:10:57,190 --> 00:11:00,390
ceart go leor, tá mé ag lorg an uimhir 50.

148
00:11:00,390 --> 00:11:03,720
Mar sin, is féidir liom dul isteach sa lár.

149
00:11:03,720 --> 00:11:07,380
Meán-Is deacair a shainmhíniú nuair atá sé líon níos na rudaí,

150
00:11:07,380 --> 00:11:10,820
ach ligean ach a rá beidh muid ag teascadh i gcónaí chun an lár.

151
00:11:10,820 --> 00:11:14,420
Mar sin anseo ní mór dúinn 8 rudaí, ionas go mbeadh an lár a 16.

152
00:11:14,420 --> 00:11:17,330
Táim ag lorg 50, mar sin tá 50 níos mó ná 16.

153
00:11:17,330 --> 00:11:21,310
Mar sin, anois is féidir liom a chóireáil go bunúsach mo eagar mar na heilimintí sin.

154
00:11:21,310 --> 00:11:23,450
Is féidir liom caith amach gach rud ó 16 os a chionn.

155
00:11:23,450 --> 00:11:27,440
Anois tá mo eagar ach na heilimintí 4, agus mé arís.

156
00:11:27,440 --> 00:11:31,910
Mar sin, ansin ba mhaith liom a fháil ar an lár arís, a bhfuil ag dul a bheith 42.

157
00:11:31,910 --> 00:11:34,730
42 níos lú ná 50, ionas gur féidir liom a caith amach na dhá ghné.

158
00:11:34,730 --> 00:11:36,890
Is é seo mo sraith fágtha.

159
00:11:36,890 --> 00:11:38,430
Tá mé ag dul chun teacht ar an lár arís.

160
00:11:38,430 --> 00:11:42,100
Buille faoi thuairim mé 50 ba shampla droch toisc go raibh mé i gcónaí a chaitheamh ar shiúl rudaí ar an taobh clé,

161
00:11:42,100 --> 00:11:48,280
ach ag an beart céanna, más rud é go bhfuil mé ag lorg rud éigin

162
00:11:48,280 --> 00:11:52,100
agus tá sé níos lú ná an eilimint Táim ag lorg faoi láthair ag,

163
00:11:52,100 --> 00:11:55,080
ansin tá mé ag dul le caith amach gach rud ar dheis.

164
00:11:55,080 --> 00:11:58,150
Mar sin, anois is gá dúinn a chur i bhfeidhm go.

165
00:11:58,150 --> 00:12:02,310
Fógra gur gá dúinn chun pas a fháil i méid.

166
00:12:02,310 --> 00:12:06,730
Ní féidir linn a dhéanamh freisin crua-cód méid.

167
00:12:06,730 --> 00:12:11,640
Mar sin, má fhaigheann muid réidh a shainmhíníonn # -

168
00:12:19,630 --> 00:12:21,430
Maith go leor.

169
00:12:21,430 --> 00:12:27,180
Conas is féidir liom figiúr nicely amach cad é an méid de na eagar uimhreacha faoi láthair?

170
00:12:27,180 --> 00:12:30,950
>> Cé mhéad eilimintí atá sa sraith uimhreacha?

171
00:12:30,950 --> 00:12:33,630
[Mac léinn] Uimhreacha, lúibíní,. Fad?

172
00:12:33,630 --> 00:12:36,600
[Bowden] nach bhfuil ann i C.

173
00:12:36,600 --> 00:12:38,580
An riachtanas is gá. Fad.

174
00:12:38,580 --> 00:12:42,010
Ní gá eagair airíonna a bheith acu, mar sin níl aon mhaoin fad arrays

175
00:12:42,010 --> 00:12:45,650
a thabhairt díreach fada leat, áfach, a tharlaíonn sé a bheith.

176
00:12:48,180 --> 00:12:51,620
[Mac léinn] Féach cé mhéad cuimhne go bhfuil sé agus a roinnt ag cé mhéad - Yeah. >>

177
00:12:51,620 --> 00:12:55,810
Mar sin, conas is féidir linn a fheiceáil cé mhéad cuimhne go bhfuil sé? >> [Mac léinn] Is uimhir. >> Yeah, Is uimhir.

178
00:12:55,810 --> 00:13:01,680
Is é an t-oibreoir Is uimhir a ag dul ar ais an méid de na eagar uimhreacha.

179
00:13:01,680 --> 00:13:10,060
Agus sin ag dul a bheith slánuimhreacha, áfach, go leor tá amanna ar mhéid an slánuimhir

180
00:13:10,060 --> 00:13:14,050
ós rud é go bhfuil cé mhéad cuimhne tá sé ag cur i ndáiríre suas.

181
00:13:14,050 --> 00:13:17,630
Mar sin, más mian liom an líon rudaí i sraith,

182
00:13:17,630 --> 00:13:20,560
ansin tá mé ag dul go dtí gur mian a roinnt ag an méid de slánuimhir.

183
00:13:22,820 --> 00:13:26,010
Maith go leor. Mar sin ligeann bhfuil mé pas a fháil i méid anseo.

184
00:13:26,010 --> 00:13:29,430
Cén fáth is gá dom a pas a fháil i méid ar chor ar bith?

185
00:13:29,430 --> 00:13:38,570
Ní féidir Cén fáth a bhfuil mé díreach tar suas anseo méid slánuimhir = deachúlach (coca féir) / deachúlach (o)?

186
00:13:38,570 --> 00:13:41,490
Cén fáth nach bhfuil an obair?

187
00:13:41,490 --> 00:13:44,470
[Mac léinn] Níl sé athróg domhanda.

188
00:13:44,470 --> 00:13:51,540
Ann [Bowden] coca féir agus táimid ag dul i líon mar coca féir,

189
00:13:51,540 --> 00:13:54,700
agus tá sé den chineál seo a foreshadowing ar cad atá le teacht. Yeah.

190
00:13:54,700 --> 00:14:00,170
Is é [mac léinn] coca féir ach an tagairt dó, mar sin bheadh ​​sé ar ais cé chomh mór go bhfuil tagairt.

191
00:14:00,170 --> 00:14:02,150
Yeah.

192
00:14:02,150 --> 00:14:09,000
Amhras orm i léacht go atá tú ag feiceáil an chairn fóill i ndáiríre, ceart?

193
00:14:09,000 --> 00:14:11,270
Táimid tar éis labhairt díreach faoi sé.

194
00:14:11,270 --> 00:14:16,090
Dá bhrí sin tá an chairn ina bhfuil gach ceann de do athróg ag dul go dtí a stóráil.

195
00:14:16,090 --> 00:14:19,960
>> Tá aon chuimhne go tá leithdháileadh i gcomhair athróg áitiúla ag dul i an chairn,

196
00:14:19,960 --> 00:14:24,790
agus faigheann gach feidhm a spás féin ar an chairn, is é a fráma cruaiche féin cad atá sé ar a dtugtar.

197
00:14:24,790 --> 00:14:31,590
Mar sin, is mó Tá a fráma cruaiche, agus taobh istigh de sé ag dul a bheith ann leis an eagar uimhreacha,

198
00:14:31,590 --> 00:14:34,270
agus tá sé ag dul a bheith deachúlach méid (uimhreacha).

199
00:14:34,270 --> 00:14:38,180
Tá sé seo ag dul go bhfuil méid na n-uimhreacha roinnte de réir méid na n-eilimintí,

200
00:14:38,180 --> 00:14:42,010
ach go léir a saol taobh istigh de fhráma chairn phríomhchonraitheora.

201
00:14:42,010 --> 00:14:45,190
Nuair a ghlaonn muid cuardaigh, faigheann cuardaigh a fráma Stack féin,

202
00:14:45,190 --> 00:14:48,840
a spás féin chun é a stóráil go léir a n-athróg áitiúil.

203
00:14:48,840 --> 00:14:56,420
Ach na hargóintí - mar sin nach bhfuil coca féir cóip den eagar ar fad.

204
00:14:56,420 --> 00:15:00,990
Ní chuirimid pas a fháil sa réimse ar fad mar chóip i cuardaigh.

205
00:15:00,990 --> 00:15:04,030
Téann sé ach thagairt don eagar.

206
00:15:04,030 --> 00:15:11,470
Sin, is féidir cuardach teacht ar na huimhreacha tríd an tagairt.

207
00:15:11,470 --> 00:15:17,100
Tá sé seo rochtain fós ar na rudaí go beo taobh istigh de fhráma chairn phríomhchonraitheora,

208
00:15:17,100 --> 00:15:22,990
ach go bunúsach, nuair a fháil againn chun leideanna, ba chóir a bheith go luath,

209
00:15:22,990 --> 00:15:24,980
is é seo cad iad na leideanna.

210
00:15:24,980 --> 00:15:29,400
Leideanna bhfuil ach tagairtí do rudaí, agus is féidir leat leideanna a úsáid chun rudaí a rochtain

211
00:15:29,400 --> 00:15:32,030
atá i frámaí Stack rudaí eile '.

212
00:15:32,030 --> 00:15:37,660
Mar sin, cé go bhfuil líon áitiúil is mó, is féidir linn rochtain a fháil fós é tríd an pointeoir.

213
00:15:37,660 --> 00:15:41,770
Ach ós rud é tá sé ach pointeoir agus tá sé ach tagairt,

214
00:15:41,770 --> 00:15:45,040
Is uimhir (coca féir) Filleann ach an méid de na tagartha féin.

215
00:15:45,040 --> 00:15:47,950
Ní chuireann sé ar ais ar mhéid an rud é a dírithe.

216
00:15:47,950 --> 00:15:51,110
Ní chuireann sé ar ais ar an méid iarbhír na n-uimhreacha.

217
00:15:51,110 --> 00:15:55,660
Agus mar sin nach bhfuil sé seo ag dul ag obair mar ba mhaith linn dó.

218
00:15:55,660 --> 00:15:57,320
>> Ceisteanna ar sin?

219
00:15:57,320 --> 00:16:03,250
Beidh leideanna a bheith imithe i mion i bhfad níos mó gory i seachtainí atá le teacht.

220
00:16:06,750 --> 00:16:13,740
Agus is é sin an fáth a lán de na rudaí a fheiceann tú, rudaí a chuardaigh an chuid is mó nó rudaí a shórtáil,

221
00:16:13,740 --> 00:16:16,990
tá siad ag beagnach gach dul go mór chun an méid iarbhír an eagar,

222
00:16:16,990 --> 00:16:20,440
mar i C, ní mór dúinn aon smaoineamh cad é an méid de na eagar.

223
00:16:20,440 --> 00:16:22,720
Ní mór duit chun pas a fháil de láimh sé isteach

224
00:16:22,720 --> 00:16:27,190
Agus ní féidir leat pas a fháil de láimh sa réimse ar fad toisc go bhfuil tú ag dul díreach sa tagairt

225
00:16:27,190 --> 00:16:30,390
agus ní féidir é a fháil ar an méid ó na tagartha.

226
00:16:30,390 --> 00:16:32,300
Maith go leor.

227
00:16:32,300 --> 00:16:38,160
Mar sin, anois ba mhaith linn a chur i bhfeidhm míníodh an méid roimhe seo.

228
00:16:38,160 --> 00:16:41,530
Is féidir leat obair ar sé ar feadh nóiméid,

229
00:16:41,530 --> 00:16:45,250
agus ní gá duit a bheith buartha faoi ag fáil gach rud breá 100% oibre.

230
00:16:45,250 --> 00:16:51,410
Just a scríobh suas an pseudocode leath do conas a cheapann tú ba chóir sé ag obair.

231
00:16:52,000 --> 00:16:53,630
Maith go leor.

232
00:16:53,630 --> 00:16:56,350
Níl gá a dhéanamh go hiomlán le seo go fóill.

233
00:16:56,350 --> 00:17:02,380
Ach ní duine ar bith a bhraitheann compordach leis an méid atá siad go dtí seo,

234
00:17:02,380 --> 00:17:05,599
cosúil le rud éigin is féidir linn obair le chéile?

235
00:17:05,599 --> 00:17:09,690
An bhfuil aon duine ag iarraidh go deonach? Nó beidh mé Pioc randamach.

236
00:17:12,680 --> 00:17:18,599
Ní chuireann sé a bheith ceart ag aon bheart ach rud is féidir linn a mhodhnú i stát oibre.

237
00:17:18,599 --> 00:17:20,720
[Mac léinn] Cinnte. >> Maith go leor.

238
00:17:20,720 --> 00:17:27,220
Sin, is féidir leat a shábháil an t-athbhreithniú trí chliceáil ar an deilbhín Sábháil beag.

239
00:17:27,220 --> 00:17:29,950
Tá tú Ramya, ceart? >> [Mac léinn] Yeah. >> [Bowden] Maith go leor.

240
00:17:29,950 --> 00:17:35,140
Mar sin, anois is féidir liom féachaint ar do athbhreithniú agus is féidir gach duine a tharraingt ar an athbhreithniú ar bun.

241
00:17:35,140 --> 00:17:38,600
Agus anseo ní mór dúinn - Maith go leor.

242
00:17:38,600 --> 00:17:43,160
Mar sin, chuaigh Ramya leis an réiteach athchúrsach, a bhfuil cinnte ar réiteach bailí.

243
00:17:43,160 --> 00:17:44,970
Tá dhá bhealach is féidir leat a dhéanamh an fhadhb seo.

244
00:17:44,970 --> 00:17:48,060
Is féidir leat a dhéanamh ceachtar é iteratively nó go hathchúrsach.

245
00:17:48,060 --> 00:17:53,860
Is féidir fadhbanna is mó a bhíonn tú is féidir a dhéanamh go hathchúrsach a dhéanamh freisin iteratively.

246
00:17:53,860 --> 00:17:58,510
Mar sin anseo tá muid déanta go hathchúrsach.

247
00:17:58,510 --> 00:18:03,730
>> An bhfuil duine éigin ag iarraidh a shainiú cad a chiallaíonn sé a dhéanamh feidhm athchúrsach?

248
00:18:07,210 --> 00:18:08,920
[Mac léinn] Nuair a bheidh tú feidhm glaoch féin

249
00:18:08,920 --> 00:18:13,470
agus ansin glaoch féin go dtí go dtagann sé amach le fíor agus fíor. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
Tá feidhm athchúrsach ach feidhm a glaonna féin.

251
00:18:17,680 --> 00:18:24,140
Tá trí rudaí móra gur gá feidhm athchúrsach a bheith acu.

252
00:18:24,140 --> 00:18:27,310
Is é an chéad ar ndóigh, iarrann sé é féin.

253
00:18:27,310 --> 00:18:29,650
Is é an dara cás bonn.

254
00:18:29,650 --> 00:18:33,390
Mar sin, riachtanais ag pointe éigin an fheidhm chun stop a glaoch féin,

255
00:18:33,390 --> 00:18:35,610
agus is é go bhfuil an méid an gcás bonn le haghaidh.

256
00:18:35,610 --> 00:18:43,860
Mar sin anseo tá a fhios againn gur cheart dúinn stopadh, ba chóir dúinn a thabhairt suas i ár cuardaigh

257
00:18:43,860 --> 00:18:48,150
nuair is ionann tús deiridh - agus beidh muid ag dul thar cad a chiallaíonn sin.

258
00:18:48,150 --> 00:18:52,130
Ach ar deireadh, an rud deireanach gur tábhachtach d'fheidhmeanna recursive:

259
00:18:52,130 --> 00:18:59,250
Ní mór na feidhmeanna chuige ar bhealach an cás bonn.

260
00:18:59,250 --> 00:19:04,140
Cosúil más rud é nach bhfuil tú thabhairt cothrom le dáta i ndáiríre rud ar bith nuair a dhéanann tú an dara glao athchúrsach,

261
00:19:04,140 --> 00:19:07,880
má tá tú literally ag glaoch díreach an fheidhm arís leis na hargóintí céanna

262
00:19:07,880 --> 00:19:10,130
agus aon athróg domhanda athrú nó rud ar bith,

263
00:19:10,130 --> 00:19:14,430
ní bheidh tú teacht ar an mbunchás, agus sa chás sin go dona.

264
00:19:14,430 --> 00:19:17,950
Beidh sé ina athchúrsáil éigríochta agus thar maoil chairn.

265
00:19:17,950 --> 00:19:24,330
Ach anseo a fheicimid go bhfuil an nuashonrú ag tarlú ós rud é táimid thabhairt cothrom le dáta tús a + deireadh / 2,

266
00:19:24,330 --> 00:19:28,180
táimid thabhairt cothrom le dáta ar an argóint deiridh anseo, táimid thabhairt cothrom le dáta an argóint tús anseo.

267
00:19:28,180 --> 00:19:32,860
Mar sin, i ngach glaonna recursive táimid thabhairt cothrom le dáta rud éigin. Maith go leor.

268
00:19:32,860 --> 00:19:38,110
Ar mhaith leat chun siúl dúinn trí do réiteach? >> Cinnte.

269
00:19:38,110 --> 00:19:44,270
Tá mé ag baint úsáide as SearchHelp ionas go mbeidh gach uair mé an glaoch fheidhm

270
00:19:44,270 --> 00:19:47,910
Tá mé i dtús áit a bhfuil mé ag lorg an eagar agus deireadh

271
00:19:47,910 --> 00:19:49,380
an áit ina bhfuil mé ag breathnú ar an eagar.

272
00:19:49,380 --> 00:19:55,330
>> Ag gach céim nuair a dúirt sé go bhfuil sé an eilimint lár, a bhfuil tús + deireadh / 2,

273
00:19:55,330 --> 00:19:58,850
is é sin is comhionann leis an méid a táimid ag lorg?

274
00:19:58,850 --> 00:20:04,650
Agus má tá sé, ansin fuair muid é, agus buille faoi thuairim mé go bhfaigheann éirigh suas na leibhéil athchúrsáil.

275
00:20:04,650 --> 00:20:12,540
Agus más rud é nach bhfuil fíor, ansin linn a sheiceáil cibé an bhfuil an luach lár an eagar ró-mhór,

276
00:20:12,540 --> 00:20:19,320
agus sa chás sin táimid ag an leath clé den eagar ag dul ó thús go lár an innéacs.

277
00:20:19,320 --> 00:20:22,710
Agus ar shlí eile a dhéanann muid an leath deiridh.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Maith go leor.

279
00:20:24,740 --> 00:20:27,730
Sin fuaimeanna maith.

280
00:20:27,730 --> 00:20:36,640
Maith go leor, mar sin ar feadh cúpla rudaí, agus ar ndóigh,, is é seo an rud an-ard-leibhéal

281
00:20:36,640 --> 00:20:41,270
go ní bheidh ort a fhios don chúrsa seo, ach tá sé fíor.

282
00:20:41,270 --> 00:20:46,080
Feidhmeanna athchúrsach, éisteacht leat i gcónaí go bhfuil siad ag déileáil droch-

283
00:20:46,080 --> 00:20:51,160
mar má ghlaonn tú go hathchúrsach féin uair an iomarca, gheobhaidh tú thar maoil chairn

284
00:20:51,160 --> 00:20:54,990
ó shin, mar a dúirt mé cheana, faigheann gach feidhm a fráma cruaiche féin.

285
00:20:54,990 --> 00:20:59,500
Mar sin, faigheann gach glaoch ar an bhfeidhm athchúrsach a fráma cruaiche féin.

286
00:20:59,500 --> 00:21:04,140
Mar sin, má dhéanann tú 1,000 glaonna recursive, gheobhaidh tú 1,000 frámaí Stack,

287
00:21:04,140 --> 00:21:08,390
agus go tapa tú mar thoradh ar a bhfuil frámaí Stack iomarca agus rudaí a bhriseadh díreach.

288
00:21:08,390 --> 00:21:13,480
Mar sin tá sin an fáth go bhfuil feidhmeanna recursive ginearálta dona.

289
00:21:13,480 --> 00:21:19,370
Ach tá go dtugtar fo-thacar deas feidhmeanna recursive eireaball-recursive feidhmeanna,

290
00:21:19,370 --> 00:21:26,120
agus a tharlaíonn sé seo a bheith ina shampla amháin i gcás fógraí má tiomsaitheoir seo

291
00:21:26,120 --> 00:21:29,920
agus ba chóir dó, I mo thuairimse, - i clang má éiríonn tú é an-O2 bratach

292
00:21:29,920 --> 00:21:33,250
ansin beidh sé faoi deara é seo eireaball recursive agus rudaí a dhéanamh go maith.

293
00:21:33,250 --> 00:21:40,050
>> Beidh sé athúsáid an fráma cruaiche céanna arís agus arís eile le haghaidh gach glao athchúrsach.

294
00:21:40,050 --> 00:21:47,010
Agus mar sin ós rud é tá tú ag baint úsáide as an fráma cruaiche céanna, ní gá duit a imní faoi

295
00:21:47,010 --> 00:21:51,690
riamh chairn cur thar maoil, agus ag an am céanna, mar a dúirt tú roimh,

296
00:21:51,690 --> 00:21:56,380
i gcás aon uair amháin tú ar ais fíor, ansin tá sé ar ais suas gach ceann de na frámaí Stack

297
00:21:56,380 --> 00:22:01,740
agus tá an glao 10ú SearchHelp Tá filleadh ar an 9ú lá, chun filleadh ar an 8ú.

298
00:22:01,740 --> 00:22:05,360
Mar sin, nach gá go dtarlódh nuair a bhíonn feidhmeanna eireaball athchúrsach.

299
00:22:05,360 --> 00:22:13,740
Agus mar sin cad a dhéanann an eireaball feidhm athchúrsach fógra gur le haghaidh aon ghlao a thugtar do searchHelp

300
00:22:13,740 --> 00:22:18,470
Is é an glao athchúrsach go tá á dhéanamh cad a sheoladh ar ais.

301
00:22:18,470 --> 00:22:25,290
Mar sin, sa chéad ghlaoch chun SearchHelp, táimid ag ceachtar ar ais láithreach bréagach,

302
00:22:25,290 --> 00:22:29,590
láithreach ar ais fíor, nó a dhéanamh linn glao athchúrsach go SearchHelp

303
00:22:29,590 --> 00:22:33,810
áit a bhfuil cad a táimid ag filleadh ar a bhfuil go glaoch ar ais.

304
00:22:33,810 --> 00:22:51,560
Agus ní raibh muid ábalta é seo a dhéanamh más rud é go raibh muid rud éigin cosúil le slánuimhir x = SearchHelp, ar ais x * 2,

305
00:22:51,560 --> 00:22:55,440
ach roinnt athruithe randamach.

306
00:22:55,440 --> 00:23:01,470
>> Mar sin, anois nglao seo athchúrsach, an slánuimhir x = SearchHelp glaoch athchúrsach,

307
00:23:01,470 --> 00:23:05,740
Tá a thuilleadh eireaball athchúrsach mar gheall ar a dhéanann sé i ndáiríre a thabhairt ar ais

308
00:23:05,740 --> 00:23:10,400
ar ais go dtí fráma Stack roimhe seo ionas go mbeidh an glaoch roimhe seo don fheidhm

309
00:23:10,400 --> 00:23:13,040
ansin is féidir rud éigin a dhéanamh leis an luach ar ais.

310
00:23:13,040 --> 00:23:22,190
Mar sin, nach bhfuil an eireaball athchúrsach, ach cad a bhí againn roimh nicely eireaball athchúrsach. Yeah.

311
00:23:22,190 --> 00:23:27,000
Mura [mac léinn] an cás bonn dara a sheiceáil ar dtús

312
00:23:27,000 --> 00:23:30,640
toisc go bhféadfadh a bheith ann ar staid ina nuair a théann tú é an argóint

313
00:23:30,640 --> 00:23:35,770
tú tús a chur = deireadh, ach tá siad an luach snáthaid.

314
00:23:35,770 --> 00:23:47,310
An cheist nach féidir a bhí muid ag siúl isteach sa chás go bhfuil deireadh an luach snáthaid

315
00:23:47,310 --> 00:23:52,000
nó tús = deireadh, go cuí, tús a chur = deireadh

316
00:23:52,000 --> 00:23:59,480
agus nach bhfuil tú ag seiceáil i ndáiríre an luach ar leith go fóill,

317
00:23:59,480 --> 00:24:03,910
tús a chur ansin + deireadh / 2 ag dul ach a bheith an luach céanna.

318
00:24:03,910 --> 00:24:07,890
Ach againn ar ais cheana féin bréagach agus muid riamh a sheiceáil i ndáiríre an luach.

319
00:24:07,890 --> 00:24:14,240
Mar sin, ar a laghad, sa chéad ghlaoch, más rud é méid 0, ansin ba mhaith linn a thabhairt ar ais bréagach.

320
00:24:14,240 --> 00:24:17,710
Ach má tá méid 1, ansin nach bhfuil tús ag dul go dtí deireadh cothrom,

321
00:24:17,710 --> 00:24:19,820
agus beidh muid ar a laghad a sheiceáil an eilimint amháin.

322
00:24:19,820 --> 00:24:26,750
Ach is dóigh liom go bhfuil tú ceart i gur féidir linn deireadh suas i gcás ina dtosaíonn + deireadh / 2,

323
00:24:26,750 --> 00:24:31,190
tús chríochnaíonn suas a bheith mar an gcéanna le tús + deireadh / 2,

324
00:24:31,190 --> 00:24:35,350
riamh ach a sheiceáil againn i ndáiríre an eilimint.

325
00:24:35,350 --> 00:24:44,740
>> Mar sin, má táimid seiceáil ar dtús go bhfuil an ghné lár an luach táimid ag lorg,

326
00:24:44,740 --> 00:24:47,110
ansin is féidir linn ar ais láithreach fíor.

327
00:24:47,110 --> 00:24:50,740
Eile má tá siad cothrom, ansin níl aon phointe i ag leanúint ar

328
00:24:50,740 --> 00:24:58,440
ós rud é táimid ag dul díreach a thabhairt suas chun dáta le cás ina bhfuil muid ar raon amháin ngné seo.

329
00:24:58,440 --> 00:25:01,110
Más rud é nach bhfuil eilimint amháin an ceann táimid ag lorg,

330
00:25:01,110 --> 00:25:03,530
ansin tá gach rud mícheart. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Mac léinn] Is é an rud go bhfuil ós rud é méid iarbhír níos mó ná an líon na n-eilimintí sa sraith,

332
00:25:08,900 --> 00:25:13,070
tá cheana féin fhritháireamh - >> Beidh Mar sin, méid -

333
00:25:13,070 --> 00:25:19,380
[Mac léinn] Abair má bhí an sraith méid 0, ansin beidh an SearchHelp seiceáil iarbhír coca féir de 0

334
00:25:19,380 --> 00:25:21,490
ar an chéad ghlaoch.

335
00:25:21,490 --> 00:25:25,300
Tá an raon méide 0, mar sin tá an 0 - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Níl rud eile go - d'fhéadfadh sé a bheith go maith. A ligean ar smaoineamh.

337
00:25:30,750 --> 00:25:40,120
Mar sin, má bhí an sraith 10 heilimintí agus is é an ceann lár táimid ag dul a sheiceáil innéacs 5,

338
00:25:40,120 --> 00:25:45,700
mar sin táimid ag seiceáil 5, agus a ligean ar rá go bhfuil an luach níos lú.

339
00:25:45,700 --> 00:25:50,720
Mar sin, táimid ag caitheamh gach rud ar shiúl ó 5 ar aghaidh.

340
00:25:50,720 --> 00:25:54,030
Mar sin, tús a + Tá deireadh / 2 ag dul a bheith ar ár deireadh nua,

341
00:25:54,030 --> 00:25:57,450
mar sin yeah, tá sé ag dul i gcónaí chun fanacht thar dheireadh na eagar.

342
00:25:57,450 --> 00:26:03,570
Má tá sé cás má bhí sé fiú nó corr, ansin ba mhaith linn a sheiceáil, a rá, 4,

343
00:26:03,570 --> 00:26:05,770
ach táimid ag caitheamh fós ar shiúl -

344
00:26:05,770 --> 00:26:13,500
Mar sin, yeah, tá deireadh ag dul i gcónaí a bheith níos faide ná an deireadh iarbhír an eagar.

345
00:26:13,500 --> 00:26:18,350
Mar sin, na heilimintí táimid ag díriú ar, tá deireadh dul i gcónaí a bheith ar an duine ina dhiaidh sin.

346
00:26:18,350 --> 00:26:24,270
Agus mar sin má dhéanann tús riamh deireadh cothrom, tá muid i sraith de mhéid 0.

347
00:26:24,270 --> 00:26:35,600
>> Is é an rud eile Bhí mé ag smaoineamh táimid thabhairt cothrom le dáta tús a thosú + deireadh / 2,

348
00:26:35,600 --> 00:26:44,020
mar sin é seo an cás go bhfuil mé ag dtrioblóid leis, i gcás ina dtosaíonn + deireadh / 2

349
00:26:44,020 --> 00:26:46,820
Is é an ghné táimid ag seiceáil.

350
00:26:46,820 --> 00:26:58,150
Ligean le rá a bhí againn an raon 10-eilimint. Cibé rud a.

351
00:26:58,150 --> 00:27:03,250
Mar sin, tús a + Tá deireadh / 2 ag dul a bheith rud éigin mar seo amháin,

352
00:27:03,250 --> 00:27:07,060
agus más rud é nach bhfuil an luach, a rá ba mhaith linn a thabhairt cothrom le dáta.

353
00:27:07,060 --> 00:27:10,060
Is é an luach níos mó, agus mar sin ba mhaith linn chun breathnú ar an leath de na eagar.

354
00:27:10,060 --> 00:27:15,910
Mar sin, conas táimid thabhairt cothrom le dáta thús, tá muid ag cothrom le dáta thús a bheith anois ngné seo.

355
00:27:15,910 --> 00:27:23,790
Ach d'fhéadfadh sé seo fós ag obair, nó ar a laghad an-, is féidir a dhéanamh leat tús + deireadh / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Mac léinn] Ní gá duit a bheith ag tosú + deireadh [inaudible] >> Yeah.

357
00:27:27,850 --> 00:27:33,240
Táimid tar éis a sheiceáil cheana ngné seo agus tá a fhios nach bhfuil sé an ceann a táimid ag lorg.

358
00:27:33,240 --> 00:27:36,800
Mar sin, ní mór dúinn tús a thabhairt cothrom le dáta a bheith ngné seo.

359
00:27:36,800 --> 00:27:39,560
Is féidir linn a skip ach é agus a nuashonrú tús a bheith ngné seo.

360
00:27:39,560 --> 00:27:46,060
Agus tá riamh cás, a ligean ar rá, go raibh na críche sin,

361
00:27:46,060 --> 00:27:53,140
Bheadh ​​sin ansin tosú sé seo a bheith, tús a + deireadh / bheadh ​​2 seo,

362
00:27:53,140 --> 00:28:00,580
tús a + deireadh - Yeah, I mo thuairimse, is féidir é deireadh suas i athchúrsáil éigríochta.

363
00:28:00,580 --> 00:28:12,690
Ligean le rá tá sé ach le sraith de mhéid 2 nó le sraith de mhéid 1. Sílim go mbeidh an obair seo.

364
00:28:12,690 --> 00:28:19,490
Mar sin, faoi láthair, is é tús go bhfuil eilimint agus deireadh 1 thar sé.

365
00:28:19,490 --> 00:28:24,110
Mar sin, tá an eilimint sin táimid ag dul a sheiceáil an gceann seo,

366
00:28:24,110 --> 00:28:29,400
agus ansin nuair a thabhairt cothrom le dáta thús, tá muid ag cothrom le dáta thús a bheith 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
atá ag dul go dtí deireadh ar ais chugainn leis an tús a bheith ngné seo.

368
00:28:33,160 --> 00:28:36,210
>> Mar sin, táimid ag seiceáil an ghné chéanna arís agus arís eile.

369
00:28:36,210 --> 00:28:43,310
Mar sin, is é seo an cás ina mbeadh ar gach glaoch athchúrsach cothrom le dáta i ndáiríre rud éigin.

370
00:28:43,310 --> 00:28:48,370
Mar sin, ní mór dúinn a dhéanamh tús + deireadh / 2 + 1, nó eile níl cás

371
00:28:48,370 --> 00:28:50,710
i gcás nach bhfuil muid ag cothrom le dáta i ndáiríre tús.

372
00:28:50,710 --> 00:28:53,820
Tá ag gach duine a fheiceáil go?

373
00:28:53,820 --> 00:28:56,310
Maith go leor.

374
00:28:56,310 --> 00:29:03,860
An bhfuil aon duine ceist ar an réiteach nó tuairimí ar bith níos mó?

375
00:29:05,220 --> 00:29:10,280
Maith go leor. An bhfuil aon duine a bheith atriallach réiteach gur féidir linn breathnú go léir ag?

376
00:29:17,400 --> 00:29:20,940
An raibh linn a dhéanamh ar fad é go hathchúrsach?

377
00:29:20,940 --> 00:29:25,950
Nó chomh maith buille faoi thuairim mé má d'oscail tú dá cuid, ansin d'fhéadfadh tú a bheith sáraithe do cheann roimhe sin.

378
00:29:25,950 --> 00:29:28,810
An é a shábháil go huathoibríoch? Níl mé dearfach.

379
00:29:35,090 --> 00:29:39,130
An bhfuil aon duine a bheith atriallach?

380
00:29:39,130 --> 00:29:42,430
Is féidir linn siúl tríd sé le chéile más rud é nach.

381
00:29:46,080 --> 00:29:48,100
Is é an smaoineamh ag dul a bheith mar an gcéanna.

382
00:30:00,260 --> 00:30:02,830
Atriallach réiteach.

383
00:30:02,830 --> 00:30:07,140
Táimid ag dul a iarraidh a dhéanamh go bunúsach an smaoineamh céanna

384
00:30:07,140 --> 00:30:16,530
nuair ba mhaith linn a choinneáil ar an deireadh nua an eagar agus tús nua ar an eagar

385
00:30:16,530 --> 00:30:18,510
agus é sin a dhéanamh thar agus os a chionn.

386
00:30:18,510 --> 00:30:22,430
Agus má cad tá muid ag súil a choinneáil ar an tús agus an deireadh riamh Trasnaigh,

387
00:30:22,430 --> 00:30:29,020
ansin ní raibh muid ag teacht air agus is féidir linn ar ais bréagach.

388
00:30:29,020 --> 00:30:37,540
Mar sin, conas is féidir liom a dhéanamh? Duine ar bith a bheith moltaí nó cód le haghaidh dom a tharraingt suas?

389
00:30:42,190 --> 00:30:47,450
[Mac léinn] Déan lúb tamaill. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Tá tú ag dul a iarraidh a dhéanamh lúb.

391
00:30:49,450 --> 00:30:51,830
>> An raibh tú ag cód raibh mé in ann tarraingt suas, nó cad a bhí tú ag dul a mholadh?

392
00:30:51,830 --> 00:30:56,340
[Mac léinn] I mo thuairimse, mar sin. >> Gach ceart. Déanann sé seo rudaí níos éasca. Cad é do ainm?

393
00:30:56,340 --> 00:30:57,890
[Mac léinn] Lucas.

394
00:31:00,140 --> 00:31:04,190
Athbhreithniú 1. Maith go leor.

395
00:31:04,190 --> 00:31:13,200
Teocht is Ísle: Is é rud ar a dtugtar linn tús a roimh.

396
00:31:13,200 --> 00:31:17,080
Níl Suas go maith cad a dtugtar againn deireadh roimh.

397
00:31:17,080 --> 00:31:22,750
I ndáiríre, tá deireadh anois laistigh den eagar. Tá sé ina ghné ba cheart dúinn a mheas.

398
00:31:22,750 --> 00:31:26,890
Mar sin, íseal 0, is é suas an méid de na eagar - 1,

399
00:31:26,890 --> 00:31:34,780
agus anois táimid ag looping, agus táimid ag seiceáil -

400
00:31:34,780 --> 00:31:37,340
Buille faoi thuairim mé féidir leat siúl tríd.

401
00:31:37,340 --> 00:31:41,420
Cad é do smaoineamh tríd an? Siúl dúinn trí do chód.

402
00:31:41,420 --> 00:31:49,940
[Mac léinn] Cinnte. Féach ar an luach coca féir i lár agus é a chur i gcomparáid le snáthaid.

403
00:31:49,940 --> 00:31:58,520
Mar sin, má tá sé níos mó ná do snáthaid, ansin ba mhaith leat - ó, i ndáiríre, ba chóir a bheith ar gcúl.

404
00:31:58,520 --> 00:32:05,180
Tá tú ag dul a iarraidh le caith amach an leath ceart, agus mar sin yeah, ba chóir a bheith ar an mbealach.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Mar sin ba chóir é seo a bheith níos lú? An bhfuil go bhfuil an méid a dúirt tú? >> [Mac léinn] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Maith go leor. Níos lú.

407
00:32:10,390 --> 00:32:15,700
Mar sin, má cad táimid ag féachaint ar níos lú ná cad ba mhaith linn,

408
00:32:15,700 --> 00:32:19,410
ansin yeah, ba mhaith linn a caith amach an leath chlé,

409
00:32:19,410 --> 00:32:22,210
rud a chiallaíonn táimid ag cothrom le dáta gach rud táimid ag smaoineamh ar

410
00:32:22,210 --> 00:32:26,610
ag bogadh íseal do cheart an eagar.

411
00:32:26,610 --> 00:32:30,130
Breathnaíonn sé seo go maith.

412
00:32:30,130 --> 00:32:34,550
I mo thuairimse, tá sé an cheist chéanna a dúirt muid ar an cheann roimhe sin,

413
00:32:34,550 --> 00:32:49,760
i gcás má tá íseal 0 agus suas 1, ansin íseal + suas / 2 ag dul a chur ar bun le bheith ar an rud céanna arís.

414
00:32:49,760 --> 00:32:53,860
>> Agus fiú más rud é nach bhfuil an cás, tá sé fós níos éifeachtaí ar a laghad

415
00:32:53,860 --> 00:32:57,630
le caith díreach amach an eilimint d'fhéach muid díreach ag a fhios againn go bhfuil mícheart.

416
00:32:57,630 --> 00:33:03,240
Mar sin, íseal + suas / 2 + 1 - >> [mac léinn] Ba chóir a bheith ar an bhealach eile.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Nó ba chóir é seo a bheith - 1 agus ba chóir an ceann eile + 1.

418
00:33:05,900 --> 00:33:09,580
[Mac léinn] Agus is ionann ba chóir go mbeadh dúbailte shíniú. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Mac léinn] Yeah.

420
00:33:14,540 --> 00:33:15,910
Maith go leor.

421
00:33:15,910 --> 00:33:21,280
Agus ar deireadh, anois go bhfuil an 1 + - 1 rud,

422
00:33:21,280 --> 00:33:31,520
tá sé - ní fhéadfadh sé a bheith - tá sé riamh agus is féidir do íseal chun deireadh suas le luach níos mó ná suas?

423
00:33:35,710 --> 00:33:40,320
Sílim go bhfuil an t-aon bhealach is féidir a tharlaíonn - An féidir é? >> [Mac léinn] Níl a fhios agam.

424
00:33:40,320 --> 00:33:45,220
Ach má thagann sé teasctha agus ansin faigheann lúide go 1 agus ansin - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Mac léinn] Bheadh ​​sé a fháil messed b'fhéidir suas.

426
00:33:49,700 --> 00:33:53,940
I mo thuairimse, ba chóir é a bheith go maith ach amháin mar gheall

427
00:33:53,940 --> 00:33:58,800
chun é a deireadh suas níos ísle a bheadh ​​siad a bheith cothrom, I mo thuairimse.

428
00:33:58,800 --> 00:34:03,070
Ach má tá siad cothrom, ansin ní ba mhaith linn a dhéanamh ar an lúb agus chun tús a chur leis

429
00:34:03,070 --> 00:34:06,670
agus táimid go mbeadh díreach tar éis filleadh ar an luach. Mar sin, I mo thuairimse, tá muid go maith anois.

430
00:34:06,670 --> 00:34:11,530
Fógra go cé go bhfuil an fhadhb seo a thuilleadh recursive,

431
00:34:11,530 --> 00:34:17,400
den chineál céanna i smaointe sin i bhfeidhm nuair is féidir linn a fheiceáil conas é seo lends sin go héasca é féin

432
00:34:17,400 --> 00:34:23,659
a réiteach athchúrsach ag an bhfíric go bhfuil muid ag cothrom le dáta ach an innéacsanna arís agus arís eile,

433
00:34:23,659 --> 00:34:29,960
táimid ag déanamh an fhadhb níos lú agus níos lú, tá muid ag díriú ar fho-thacar de na eagar.

434
00:34:29,960 --> 00:34:40,860
[Mac léinn] Má tá íseal 0 agus suas 1, go mbeadh siad araon 0 + 1/2, a bheadh ​​téigh go dtí 0,

435
00:34:40,860 --> 00:34:44,429
agus ansin bheadh ​​duine a bheith + 1, bheadh ​​duine a bheith - 1.

436
00:34:47,000 --> 00:34:50,870
[Mac léinn] Cá bhfuil seiceáil againn comhionannas?

437
00:34:50,870 --> 00:34:55,100
Cosúil má tá an ceann lár ndáiríre snáthaid?

438
00:34:55,100 --> 00:34:58,590
Ní Táimid ag déanamh faoi láthair go bhfuil? Oh!

439
00:35:00,610 --> 00:35:02,460
Má it's -

440
00:35:05,340 --> 00:35:13,740
Tá. Ní féidir linn ach a dhéanamh ar an tástáil síos anseo mar a rá a ligean ar lár chéad -

441
00:35:13,740 --> 00:35:16,430
[Mac léinn] Tá sé cosúil i ndáiríre ní caith amach an cheangal.

442
00:35:16,430 --> 00:35:20,220
Mar sin, má tá tú caith amach na cheangal, tá tú chun é a sheiceáil ar dtús nó cibé.

443
00:35:20,220 --> 00:35:23,350
Ah. Yeah. >> [Mac léinn] Yeah.

444
00:35:23,350 --> 00:35:29,650
Mar sin, anois ní mór dúinn a thrown away an ceann d'fhéach sé againn faoi láthair ar,

445
00:35:29,650 --> 00:35:33,260
rud a chiallaíonn go mór dúinn anois a bheith chomh maith

446
00:35:33,260 --> 00:35:44,810
más rud é (coca féir [(íseal + suas) / 2] == snáthaid), ansin is féidir linn ar ais fíor.

447
00:35:44,810 --> 00:35:52,070
Agus cé acu a chuir mé eile nó díreach más rud é, ciallaíonn sé literally an rud céanna

448
00:35:52,070 --> 00:35:57,110
toisc go mbeadh sé seo ar ais fíor.

449
00:35:57,110 --> 00:36:01,450
Mar sin, beidh mé eile más rud é, ach ní chuireann sé ábhar.

450
00:36:01,450 --> 00:36:10,440
>> Mar sin, eile más rud é seo, eile seo, agus tá sé seo an rud coitianta a dhéanamh liom

451
00:36:10,440 --> 00:36:14,340
i gcás fiú má tá sé an cás ina bhfuil gach rud go maith anseo,

452
00:36:14,340 --> 00:36:22,780
cosúil nach féidir íseal a bheith níos mó ná suas, nach bhfuil sé réasúnaíocht fiú faoi cé acu an é go bhfuil fíor.

453
00:36:22,780 --> 00:36:28,010
Mar sin, is féidir leat chomh maith a rá cé go bhfuil íseal níos lú ná nó cothrom le

454
00:36:28,010 --> 00:36:30,720
nó le linn íseal níos lú ná

455
00:36:30,720 --> 00:36:35,300
mar sin a tharlaíonn má tá siad riamh chomhionann nó íseal chun pas a fháil suas,

456
00:36:35,300 --> 00:36:40,130
ansin is féidir linn briseadh amach as an lúb.

457
00:36:41,410 --> 00:36:44,630
Ceisteanna, imní, tuairimí?

458
00:36:47,080 --> 00:36:49,270
Maith go leor. Breathnaíonn sé seo go maith.

459
00:36:49,270 --> 00:36:52,230
Anois, ba mhaith linn saghas a dhéanamh.

460
00:36:52,230 --> 00:37:04,030
Má théann muid go dtí mo athbhreithniú an dara, feicimid na huimhreacha céanna,

461
00:37:04,030 --> 00:37:07,550
ach anois tá siad a thuilleadh in ord sórtáilte.

462
00:37:07,550 --> 00:37:12,840
Agus ba mhaith linn saghas a chur i bhfeidhm ag baint úsáide as aon algartam i O n log n.

463
00:37:12,840 --> 00:37:17,240
Mar sin, a algartam a cheapann tú ba chóir dúinn a chur i bhfeidhm anseo? >> [Mac léinn] Merge saghas.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Is Cumaisc saghas O (n log n), agus mar sin go cad táimid ag dul a dhéanamh.

465
00:37:23,810 --> 00:37:26,680
Agus is é an fhadhb ag dul a bheith go leor den chineál céanna,

466
00:37:26,680 --> 00:37:31,920
nuair a lends sé go héasca é féin a réiteach athchúrsach.

467
00:37:31,920 --> 00:37:35,580
Is féidir linn teacht freisin suas le réiteach atriallach más mian linn,

468
00:37:35,580 --> 00:37:42,540
ach beidh athchúrsáil níos éasca anseo agus ba chóir a dhéanamh cuardach ar dúinn.

469
00:37:45,120 --> 00:37:49,530
Buille faoi thuairim mé beidh muid ag siúl trí saghas merge chéad uair,

470
00:37:49,530 --> 00:37:54,280
cé go bhfuil físeán álainn ar saghas merge cheana féin. [Gáire]

471
00:37:54,280 --> 00:37:59,780
Mar sin, merge sórtáil tá - Tá mé ag wasting oiread sin den pháipéar seo.

472
00:37:59,780 --> 00:38:02,080
Ó, níl ach aon chlé.

473
00:38:02,080 --> 00:38:03,630
Mar sin, merge.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Maith go leor.

476
00:38:29,910 --> 00:38:33,460
Merge Bíonn dhá arrays ar leith.

477
00:38:33,460 --> 00:38:36,780
Ina n-aonar dá arrays bhfuil an dá eagar.

478
00:38:36,780 --> 00:38:40,970
Seo sraith, 1, 3, 5, curtha in eagar sin. Seo sraith, 0, 2, 4, curtha in eagar.

479
00:38:40,970 --> 00:38:46,710
Anois, cad ba cheart merge a dhéanamh le chéile iad i sraith amháin go bhfuil curtha in eagar féin.

480
00:38:46,710 --> 00:38:57,130
Mar sin, ba mhaith linn le sraith de mhéid 6 go bhfuil dul chun bheith ar na gnéithe taobh istigh de sé

481
00:38:57,130 --> 00:38:59,390
in ord sórtáilte.

482
00:38:59,390 --> 00:39:03,390
>> Agus mar sin is féidir linn leas a bhaint as an bhfíric go bhfuil an dá arrays atá curtha in eagar

483
00:39:03,390 --> 00:39:06,800
seo a dhéanamh in am líneach,

484
00:39:06,800 --> 00:39:13,510
bhrí am líneach má tá an sraith x méid agus tá sé seo y méid,

485
00:39:13,510 --> 00:39:20,970
ansin ba chóir go mbeadh an t-algartam iomlán O (x + y). Maith go leor.

486
00:39:20,970 --> 00:39:23,150
Mar sin, moltaí.

487
00:39:23,150 --> 00:39:26,030
[Mac léinn] Níorbh fhéidir linn tús ó thaobh na láimhe clé?

488
00:39:26,030 --> 00:39:30,150
Mar sin, beidh tú a chur ar an 0 síos ar dtús agus ansin an 1 agus ansin anseo tá tú ag an 2.

489
00:39:30,150 --> 00:39:33,320
Mar sin tá sé cineál cosúil go bhfuil tú cluaisín a tá bogadh go dtí an ceart. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
I gcás an dá de na arrays má táimid ag díriú ach ar an eilimint leftmost.

491
00:39:41,070 --> 00:39:43,530
Mar gheall ar an dá arrays atá curtha in eagar, tá a fhios againn go bhfuil na heilimintí 2

492
00:39:43,530 --> 00:39:46,920
Is iad na gnéithe is lú i gceachtar eagar.

493
00:39:46,920 --> 00:39:53,500
Mar sin, ciallaíonn sé sin go mór 1 de na heilimintí sin 2 an ghné is lú in ár sraith cumaiscthe.

494
00:39:53,500 --> 00:39:58,190
Tharlaíonn sé ach ionas go mbeidh an lú an ceann ar an am ceart seo.

495
00:39:58,190 --> 00:40:02,580
Mar sin, beimid ag tabhairt 0, tá sé isteach ar an taobh clé toisc go bhfuil níos lú ná 0 1,

496
00:40:02,580 --> 00:40:08,210
sin a chur 0, tá sé isteach i ár seasamh sa chéad, agus ansin thabhairt cothrom le dáta seo againn

497
00:40:08,210 --> 00:40:12,070
díriú anois ar an chéad eilimint.

498
00:40:12,070 --> 00:40:14,570
Agus anois táimid arís.

499
00:40:14,570 --> 00:40:20,670
Mar sin anois táimid ag comparáid a dhéanamh idir 2 agus 1. 1 níos lú, mar sin beidh orainn a chur isteach 1.

500
00:40:20,670 --> 00:40:25,300
Táimid ag cothrom le dáta an pointeoir a chur in iúl ar an Guy.

501
00:40:25,300 --> 00:40:33,160
Anois, a dhéanann muid arís, agus mar sin 2. Cuirfidh sé seo cothrom le dáta, na 2, 3 i gcomparáid.

502
00:40:33,160 --> 00:40:37,770
Sé seo cothrom le dáta, ansin 4 agus 5.

503
00:40:37,770 --> 00:40:42,110
Mar sin, is é sin chumaiscthe.

504
00:40:42,110 --> 00:40:49,010
>> Ba chóir go mbeadh sé soiléir go leor go bhfuil sé in am líneach ó againn dul díreach i ngach gné uair amháin.

505
00:40:49,010 --> 00:40:55,980
Agus is é sin an chéim is mó a chur i bhfeidhm a bhfuil merge sórtáil seo a dhéanamh.

506
00:40:55,980 --> 00:40:59,330
Agus nach bhfuil sé go crua.

507
00:40:59,330 --> 00:41:15,020
A rudaí cúpla a bheith buartha faoi é a ligean ar rá go raibh muid chumasc 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Sa chás seo táimid ag deireadh suas sa scéal ina bhfuil an ceann seo ag dul a bheith níos lú,

509
00:41:30,930 --> 00:41:36,160
ansin dúinn cothrom le dáta an pointeoir, tá an ceann seo ag dul a bheith níos lú, cothrom le dáta seo,

510
00:41:36,160 --> 00:41:41,280
Tá an ceann seo níos lú, agus anois tá tú a aithint

511
00:41:41,280 --> 00:41:44,220
nuair atá tú ag rith go hiarbhír as na n-eilimintí a chur i gcomparáid leis.

512
00:41:44,220 --> 00:41:49,400
Ós rud é go mór dúinn a úsáid cheana féin an sraith ar fad,

513
00:41:49,400 --> 00:41:55,190
tá gach rud sa sraith anois isteach díreach isteach anseo.

514
00:41:55,190 --> 00:42:02,040
Mar sin, má táimid ar siúl riamh sa phointe nuair atá ceann de na arrays astu go hiomlán cheana féin,

515
00:42:02,040 --> 00:42:06,510
ansin dúinn a chur díreach na gnéithe uile an eagar eile agus iad a chur isteach i ndeireadh na eagar.

516
00:42:06,510 --> 00:42:13,630
Mar sin, is féidir linn a chur isteach ach 4, 5, 6. Maith go leor.

517
00:42:13,630 --> 00:42:18,070
Is é sin an rud amháin chun faire amach do.

518
00:42:22,080 --> 00:42:26,120
Cur chun feidhme ba chóir a bheith ar chéim 1.

519
00:42:26,120 --> 00:42:32,600
Cumaisc a shórtáil ansin bunaithe ar sin, tá sé 2 céimeanna, 2 céimeanna amaideach.

520
00:42:38,800 --> 00:42:42,090
A ligean ar thabhairt ach an eagar.

521
00:42:57,920 --> 00:43:05,680
Mar sin, merge sórtáil é, céim 1 a bhriseadh go hathchúrsach an eagar i halves.

522
00:43:05,680 --> 00:43:09,350
Mar sin, roinneadh an eagar seo i leatha.

523
00:43:09,350 --> 00:43:22,920
Tá muid anois 4, 15, 16, 50 agus 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Agus anois a dhéanaimid é arís agus scar muid seo i leatha.

525
00:43:25,800 --> 00:43:27,530
Ach beidh mé é a dhéanamh ar an taobh seo.

526
00:43:27,530 --> 00:43:34,790
Mar sin, 4, 15 agus 16, 50.

527
00:43:34,790 --> 00:43:37,440
Ba mhaith linn a dhéanamh ar an rud céanna thar anseo.

528
00:43:37,440 --> 00:43:40,340
Agus anois scar muid sé i leatha arís.

529
00:43:40,340 --> 00:43:51,080
Agus ní mór dúinn 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Mar sin, is é sin ár gcás bonn.

531
00:43:53,170 --> 00:44:00,540
Nuair atá na arrays ar mhéid 1, ansin dúinn stop a chur leis an scoilteadh i halves.

532
00:44:00,540 --> 00:44:03,190
>> Anois, cad a dhéanaimid leis seo?

533
00:44:03,190 --> 00:44:15,730
Táimid deireadh suas beidh sé seo a bhriseadh síos freisin i 8, 23, 42, agus 108.

534
00:44:15,730 --> 00:44:24,000
Mar sin anois go bhfuil muid ag an bpointe seo, céim anois dhá cheann de chineál merge Tá chumasc ach péire ar na liostaí.

535
00:44:24,000 --> 00:44:27,610
Mar sin, ba mhaith linn a chumasadh seo. Táimid ag glaoch díreach chumasadh.

536
00:44:27,610 --> 00:44:31,410
Tá a fhios againn go mbeidh merge ar ais ar na in ord sórtáilte.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Anois, ba mhaith linn a chumasadh seo, agus go mbeidh ar ais liosta leis na in ord sórtáilte,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Merge muid iad siúd - ní féidir liom scríobh - 8, 23 agus 42, 108.

541
00:44:57,380 --> 00:45:02,890
Mar sin, ní mór dúinn péirí cumaiscthe aon uair amháin.

542
00:45:02,890 --> 00:45:05,140
Anois táimid ag merge go díreach arís.

543
00:45:05,140 --> 00:45:10,130
Fógra go bhfuil gach ceann de na liostaí seo curtha in eagar ann féin,

544
00:45:10,130 --> 00:45:15,220
agus ansin is féidir linn a chumasadh ach na liostaí a fháil ar liosta de mhéid 4 atá curtha in eagar

545
00:45:15,220 --> 00:45:19,990
agus chumasadh leis an dá liostaí a fháil ar liosta de mhéid 4 go bhfuil curtha in eagar.

546
00:45:19,990 --> 00:45:25,710
Agus ar deireadh, is féidir linn a chumasadh leis an dá liostaí de mhéid 4 a fháil ar liosta amháin de mhéid 8 go bhfuil curtha in eagar.

547
00:45:25,710 --> 00:45:34,030
Mar sin, a fheiceáil go bhfuil sé seo foriomlán n log n, chonaic muid cheana féin go bhfuil merge líneach,

548
00:45:34,030 --> 00:45:40,390
mar sin nuair a bhíonn muid ag déileáil le cumasc seo, mar sin cosúil leis an costas iomlán merge

549
00:45:40,390 --> 00:45:43,410
i gcás an dá liosta bhfuil ach 2 mar -

550
00:45:43,410 --> 00:45:49,610
Nó go maith, tá sé O n, ach n anseo ach na heilimintí 2, mar sin tá sé 2.

551
00:45:49,610 --> 00:45:52,850
Agus beidh ar na 2 2 agus beidh na 2 a 2 agus beidh na 2 a 2,

552
00:45:52,850 --> 00:45:58,820
mar sin ar fud gach ceann de na cumasc gur gá dúinn a dhéanamh, deireadh muid suas a dhéanamh n.

553
00:45:58,820 --> 00:46:03,210
Cosúil le 2 + 2 + 2 + 2 8, a bhfuil n,

554
00:46:03,210 --> 00:46:08,060
mar sin tá an costas a chumasc sa tacar n.

555
00:46:08,060 --> 00:46:10,810
Agus ansin an rud céanna anseo.

556
00:46:10,810 --> 00:46:16,980
Beidh muid chumasadh na 2, ansin na 2, agus ina n-aonar seo chumasadh ceithre oibríocht a ghlacadh,

557
00:46:16,980 --> 00:46:23,610
beidh sé seo merge a ghlacadh ceithre oibríochtaí, ach arís, idir gach ceann de na,

558
00:46:23,610 --> 00:46:29,030
deireadh muid suas a chumasc n rudaí iomlán, agus mar sin tógann an chéim seo n.

559
00:46:29,030 --> 00:46:33,670
Agus tógann sé sin gach leibhéal eilimintí n á chomhcheangal.

560
00:46:33,670 --> 00:46:36,110
>> Agus cé mhéad leibhéil atá ann?

561
00:46:36,110 --> 00:46:40,160
Ag gach leibhéal a fhásann, ár sraith de réir méid 2.

562
00:46:40,160 --> 00:46:44,590
Seo iad ár arrays de mhéid 1, anseo tá siad de mhéid 2, anseo tá siad de mhéid 4,

563
00:46:44,590 --> 00:46:46,470
agus ar deireadh, tá siad de mhéid 8.

564
00:46:46,470 --> 00:46:56,450
Mar sin, ós rud é go dúbailt é, tá dul chun bheith ina san iomlán log n de na leibhéil.

565
00:46:56,450 --> 00:47:02,090
Mar sin, le logáil n leibhéil, gach leibhéal an duine aonair cur n-oibríochtaí iomlána,

566
00:47:02,090 --> 00:47:05,720
a fháil againn ar log n algartam.

567
00:47:05,720 --> 00:47:07,790
Ceisteanna?

568
00:47:08,940 --> 00:47:13,320
An ndearna daoine cheana féin dul chun cinn ar an mbealach chun é seo?

569
00:47:13,320 --> 00:47:18,260
An bhfuil aon duine cheana féin i stát nuair is féidir liom a tharraingt suas díreach a n-cód?

570
00:47:20,320 --> 00:47:22,260
Féidir liom a thabhairt nóiméad.

571
00:47:24,770 --> 00:47:27,470
Tá sé seo ar cheann ag dul a bheith níos faide.

572
00:47:27,470 --> 00:47:28,730
Liom a mholadh go mór athuair -

573
00:47:28,730 --> 00:47:30,510
Ní gá duit athchúrsáil a dhéanamh le haghaidh merge

574
00:47:30,510 --> 00:47:33,750
mar gheall ar é a dhéanamh cuardach ar do merge, agus tú ag dul a bheith acu chun pas a fháil a bunch de mhéideanna éagsúla.

575
00:47:33,750 --> 00:47:37,150
Is féidir leat, ach tá sé annoying.

576
00:47:37,150 --> 00:47:43,720
Ach tá athchúrsáil do shórtáil féin éasca go leor.

577
00:47:43,720 --> 00:47:49,190
Tá tú ach glaoch literally saghas ar leath chlé, saghas ar leath ceart. Maith go leor.

578
00:47:51,770 --> 00:47:54,860
Duine ar bith aon rud is féidir liom a tharraingt suas go fóill?

579
00:47:54,860 --> 00:47:57,540
Nó eile beidh mé a thabhairt nóiméad.

580
00:47:58,210 --> 00:47:59,900
Maith go leor.

581
00:47:59,900 --> 00:48:02,970
Duine ar bith go bhfuil rud éigin is féidir linn obair leis?

582
00:48:05,450 --> 00:48:09,680
Nó eile beidh muid ag obair go díreach leis seo agus ansin a leathnú ó ann.

583
00:48:09,680 --> 00:48:14,050
>> Duine ar bith a bheith níos mó ná seo gur féidir liom a tharraingt suas?

584
00:48:14,050 --> 00:48:17,770
[Mac léinn] Yeah. Is féidir leat a tharraingt suas mianach. >> Gach ceart.

585
00:48:17,770 --> 00:48:19,730
Tá!

586
00:48:22,170 --> 00:48:25,280
[Mac léinn] Bhí a lán de na coinníollacha. >> Ó, shoot. An féidir leat -

587
00:48:25,280 --> 00:48:28,110
[Mac léinn] Caithfidh mé a shábháil. >> Yeah.

588
00:48:32,420 --> 00:48:35,730
Mar sin, rinne muid a dhéanamh ar an chumasadh ar leithligh.

589
00:48:35,730 --> 00:48:38,570
Oh, ach nach bhfuil sé go dona.

590
00:48:39,790 --> 00:48:41,650
Maith go leor.

591
00:48:41,650 --> 00:48:47,080
Dá bhrí sin tá saghas féin ach glaoch mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Mínigh dúinn cad a dhéanann mergeSortHelp.

593
00:48:49,530 --> 00:48:55,700
[Mac léinn] MergeSortHelp deas a dhéanann i bhfad an dhá chéim is mó,

594
00:48:55,700 --> 00:49:01,270
a bhfuil a shórtáil gach leath de na eagar agus ansin leis an mbeirt acu chumasadh.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Maith go leor, mar sin a thabhairt dom an dara.

596
00:49:10,850 --> 00:49:13,210
Sílim - >> [mac léinn] is gá dom a -

597
00:49:17,100 --> 00:49:19,400
Yeah. Tá mé ag iarraidh rud éigin.

598
00:49:19,400 --> 00:49:23,100
I merge, realize mé gur gá dom a chruthú sraith nua

599
00:49:23,100 --> 00:49:26,530
toisc nach raibh mé in ann é a dhéanamh i bhfeidhm. >> Tá. Ní féidir leat. Cheartú.

600
00:49:26,530 --> 00:49:28,170
[Mac léinn] Mar sin mé a chruthú sraith nua.

601
00:49:28,170 --> 00:49:31,510
Rinne mé dearmad ag deireadh na merge a ath-athrú.

602
00:49:31,510 --> 00:49:34,490
Maith go leor. Ní mór dúinn sraith nua.

603
00:49:34,490 --> 00:49:41,000
I saghas merge, tá sé seo beagnach i gcónaí fíor.

604
00:49:41,000 --> 00:49:44,340
Cuid de chostas an algartam níos fearr am-ciallmhar

605
00:49:44,340 --> 00:49:47,310
Tá beagnach i gcónaí de dhíth orthu a úsáid cuimhne le beagán níos mó.

606
00:49:47,310 --> 00:49:51,570
Mar sin anseo, is cuma conas a dhéanann tú chumasadh saghas,

607
00:49:51,570 --> 00:49:54,780
bheadh ​​de dhíth ort dosheachanta a úsáid roinnt cuimhne breise.

608
00:49:54,780 --> 00:49:58,240
Sé nó sí a cruthaíodh sraith nua.

609
00:49:58,240 --> 00:50:03,400
Agus ansin a rá leat ag an deireadh is gá dúinn ach a chóipeáil eagar nua isteach sa réimse bunaidh.

610
00:50:03,400 --> 00:50:04,830
[Mac léinn] I mo thuairimse, mar sin, yeah.

611
00:50:04,830 --> 00:50:08,210
Níl a fhios agam má oibríonn i dtéarmaí comhaireamh trí thagairt nó cibé -

612
00:50:08,210 --> 00:50:11,650
Yeah, beidh sé ag obair. >> [Mac léinn] Maith go leor.

613
00:50:20,620 --> 00:50:24,480
An raibh tú iarracht a reáchtáil seo? >> [Mac léinn] No, ní go fóill. >> Maith go leor.

614
00:50:24,480 --> 00:50:28,880
Bain triail as sé ag rith, agus ansin beidh mé ag caint faoi sé le haghaidh an dara.

615
00:50:28,880 --> 00:50:35,200
[Mac léinn] is gá dom a bhfuil na fréamhshamhlacha fheidhm agus gach rud, áfach, ceart?

616
00:50:37,640 --> 00:50:40,840
An fréamhshamhlacha feidhme. Ó, i gceist agat cosúil le - Tá.

617
00:50:40,840 --> 00:50:43,040
Sórtáil ag glaoch mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Mar sin, d'fhonn a shórtáil a ghlaoch mergeSortHelp, ní mór mergeSortHelp a bheith acu sainmhínithe

619
00:50:47,390 --> 00:50:56,370
roimh a shórtáil nó mór dúinn ach an fhréamhshamhail. Just a chóipeáil agus a ghreamú go.

620
00:50:56,370 --> 00:50:59,490
Agus mar an gcéanna, tá mergeSortHelp ag glaoch merge,

621
00:50:59,490 --> 00:51:03,830
ach nach bhfuil merge sainithe go fóill, ionas gur féidir linn in iúl ach a fhios mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
go bhfuil go bhfuil an méid merge ag dul chun breathnú cosúil le, agus go bhfuil sin.

623
00:51:09,950 --> 00:51:15,730
Mar sin, mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Tá an tsaincheist anseo áit a bhfuil muid aon chás bonn.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp Tá recursive, mar sin aon fheidhm athchúrsach

626
00:51:38,110 --> 00:51:42,610
ag dul go dtí gá de chineál éigin cás bonn ar an eolas nuair a stopadh go hathchúrsach ag glaoch féin.

627
00:51:42,610 --> 00:51:45,590
Cad é ár gcás bonn ag dul a bheith anseo? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Mac léinn] Má tá an méid 1? >> [Bowden] Tá.

629
00:51:49,110 --> 00:51:56,220
Mar sin, cosúil le chonaic muid ceart ann, stop muid arrays scoilteadh

630
00:51:56,220 --> 00:52:01,850
nuair a fuair muid i arrays de mhéid 1, atá curtha in eagar gan dabht iad féin.

631
00:52:01,850 --> 00:52:09,530
Mar sin, má bhíonn méid 1, tá a fhios againn go bhfuil an eagar curtha in eagar cheana féin,

632
00:52:09,530 --> 00:52:12,970
ionas gur féidir linn ar ais go díreach.

633
00:52:12,970 --> 00:52:16,880
>> Fógra go bhfuil ar neamhní, mar sin ní féidir linn a anything ar leith ar ais, ní mór dúinn ar ais go díreach.

634
00:52:16,880 --> 00:52:19,580
Maith go leor. Mar sin go bhfuil ár chás bonn.

635
00:52:19,580 --> 00:52:27,440
Buille faoi thuairim mé d'fhéadfadh ár gcás bonn a freisin má tharlaíonn dúinn a bheith chumasc le sraith de mhéid 0,

636
00:52:27,440 --> 00:52:30,030
ba mhaith linn is dócha a stopadh ag pointe éigin,

637
00:52:30,030 --> 00:52:33,610
ionas gur féidir linn a rá ach méid níos lú ná 2 nó níos lú ná nó cothrom le 1

638
00:52:33,610 --> 00:52:37,150
ionas go mbeidh an obair seo le haghaidh aon eagar anois.

639
00:52:37,150 --> 00:52:38,870
Maith go leor.

640
00:52:38,870 --> 00:52:42,740
Mar sin go bhfuil ár chás bonn.

641
00:52:42,740 --> 00:52:45,950
Anois, ba mhaith leat chun siúl linn trí chumasadh?

642
00:52:45,950 --> 00:52:49,140
Cad a chiallaíonn seo go léir cásanna seo?

643
00:52:49,140 --> 00:52:54,480
Suas anseo, tá muid ag déanamh ach an smaoineamh céanna, an -

644
00:52:56,970 --> 00:53:02,470
[Mac léinn] is gá dom a bheith ag dul mhéid leis na glaonna mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Dúirt mé freisin méid mar bunscoile breise agus nach bhfuil sé ann, cosúil le méid / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, méid / 2, méid / 2. >> [Mac léinn] Yeah, agus freisin san fheidhm thuas chomh maith.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Anseo? >> [Mac léinn] Just a mhéid. >> [Bowden] Oh. Méid, méid? >> [Mac léinn] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Maith go leor.

649
00:53:23,010 --> 00:53:26,580
Lig dom smaoineamh ar feadh soicind.

650
00:53:26,580 --> 00:53:28,780
An bhfuil muid ag siúl isteach i gceist?

651
00:53:28,780 --> 00:53:33,690
Táimid ag déileáil i gcónaí ar an taobh clé mar 0. >> [Mac léinn] Uimh

652
00:53:33,690 --> 00:53:36,340
Sin mícheart freisin. Tá brón orm. Ba chóir go mbeadh sé tús. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Maith go leor. Is maith liom go níos fearr.

654
00:53:39,230 --> 00:53:43,880
Agus deireadh. Maith go leor.

655
00:53:43,880 --> 00:53:47,200
Mar sin, anois is mian leat chun siúl linn trí chumasadh? >> [Mac léinn] Maith go leor.

656
00:53:47,200 --> 00:53:52,150
Tá mé ag siúl díreach tríd an eagar nua go bhfuil mé a cruthaíodh.

657
00:53:52,150 --> 00:53:57,420
Is é an méid ar mhéid an chuid den réimse sin ba mhaith linn a bheith curtha in eagar

658
00:53:57,420 --> 00:54:03,460
agus ag iarraidh a fháil ar an eilimint gur chóir dom a chur sa chéim eagar nua.

659
00:54:03,460 --> 00:54:10,140
Mar sin, chun é sin a dhéanamh, ar an gcéad mé ag seiceáil má leanann an leath clé den eagar go bhfuil gnéithe ar bith níos mó,

660
00:54:10,140 --> 00:54:14,260
agus más rud é nach é, ansin a théann tú síos go dtí an coinníoll eile, a deir go díreach

661
00:54:14,260 --> 00:54:20,180
ceart go leor, ní mór dó a bheith i sraith ceart, agus beidh a chur go bhfuil muid ar an innéacs reatha newArray.

662
00:54:20,180 --> 00:54:27,620
>> Agus ansin a mhalairt, tá mé ag seiceáil má tá an taobh dheis de na eagar críochnaithe chomh maith,

663
00:54:27,620 --> 00:54:30,630
agus sa chás sin chuir mé díreach i thaobh na láimhe clé.

664
00:54:30,630 --> 00:54:34,180
Ní fhéadfadh go dtarlódh sé sin i ndáiríre is gá. Níl mé cinnte.

665
00:54:34,180 --> 00:54:40,970
Ach mar sin féin, tá an dá cheann eile a sheiceáil cé acu de na dhá níos lú i thaobh na láimhe clé nó an ceart.

666
00:54:40,970 --> 00:54:49,770
Agus chomh maith i ngach cás, tá mé ag incriminteach cibé placeholder mé INCRIMINT.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Maith go leor.

668
00:54:52,040 --> 00:54:53,840
Breathnaíonn go maith.

669
00:54:53,840 --> 00:54:58,800
An bhfuil aon duine tuairimí nó imní nó ceisteanna?

670
00:55:00,660 --> 00:55:07,720
Mar sin, na ceithre chás atá againn chun rudaí a thabhairt isteach díreach a bheith - nó tá sé cosúil cúig -

671
00:55:07,720 --> 00:55:13,100
ach ní mór dúinn a bhreithniú cibé an bhfuil an eagar chlé rith amach na rudaí is gá dúinn a chumasadh,

672
00:55:13,100 --> 00:55:16,390
cibé an bhfuil eagar ceart rith amach na rudaí is gá dúinn a chumasadh -

673
00:55:16,390 --> 00:55:18,400
Tá mé ag dírithe ar rud ar bith.

674
00:55:18,400 --> 00:55:21,730
Mar sin, cibé an bhfuil an eagar chlé rith amach de rudaí nó go mbeidh an eagar ceart rith amach na rudaí.

675
00:55:21,730 --> 00:55:24,320
Tá na dhá chás.

676
00:55:24,320 --> 00:55:30,920
Ní mór dúinn freisin an cás fánach ar cibé an bhfuil an rud chlé níos lú ná an rud ceart.

677
00:55:30,920 --> 00:55:33,910
Ansin, ba mhaith linn a roghnú an rud chlé.

678
00:55:33,910 --> 00:55:37,630
Tá na cásanna.

679
00:55:37,630 --> 00:55:40,990
Mar sin, bhí an ceart seo, ionas go mbeidh go.

680
00:55:40,990 --> 00:55:46,760
Eagar chlé. Tá sé 1, 2, 3. Maith go leor. Mar sin, yeah, sin iad na ceithre rudaí a d'fhéadfadh muid ag iarraidh a dhéanamh.

681
00:55:50,350 --> 00:55:54,510
Agus ní bheidh muid ag dul thar atriallach réiteach.

682
00:55:54,510 --> 00:55:55,980
Ní ba mhaith liom a mholadh -

683
00:55:55,980 --> 00:56:03,070
Is Cumaisc saghas sampla de feidhm go bhfuil an dá ní eireaball recursive,

684
00:56:03,070 --> 00:56:07,040
nach bhfuil sé éasca a dhéanamh eireaball athchúrsach,

685
00:56:07,040 --> 00:56:13,450
ach freisin nach bhfuil sé an-éasca a dhéanamh atriallach.

686
00:56:13,450 --> 00:56:16,910
Tá sé seo an-éasca.

687
00:56:16,910 --> 00:56:19,170
Seo i bhfeidhm saghas merge,

688
00:56:19,170 --> 00:56:22,140
merge, is cuma cad a dhéanann tú, tá tú ag dul a thógáil chumaiscthe.

689
00:56:22,140 --> 00:56:29,170
>> Mar sin, merge sórtáil tógtha ar barr na merge Tá go hathchúrsach ach na trí línte.

690
00:56:29,170 --> 00:56:34,700
Iteratively, tá sé níos annoying agus níos deacra chun machnamh.

691
00:56:34,700 --> 00:56:41,860
Ach faoi deara go nach bhfuil sé eireaball athchúrsach ó mergeSortHelp - nuair a iarrann sé é féin -

692
00:56:41,860 --> 00:56:46,590
ní mór é fós chun rudaí a dhéanamh i ndiaidh an tuairisceáin glaoch athchúrsach.

693
00:56:46,590 --> 00:56:50,830
Mar sin, ní mór an fráma cruaiche bheith ann fiú tar éis ghlaoch seo.

694
00:56:50,830 --> 00:56:54,170
Agus ansin nuair a ghlaonn tú é seo, caithfidh an fráma cruaiche bheith ann

695
00:56:54,170 --> 00:56:57,780
mar gheall ar fiú tar éis an ghlao, ní mór dúinn fós a chumasadh.

696
00:56:57,780 --> 00:57:01,920
Agus tá sé nontrivial a dhéanamh ar an eireaball athchúrsach.

697
00:57:04,070 --> 00:57:06,270
Ceisteanna?

698
00:57:08,300 --> 00:57:09,860
Gach ceart.

699
00:57:09,860 --> 00:57:13,400
Mar sin, dul ar ais ar a shórtáil - OH, tá dhá rud ba mhaith liom a thaispeáint. Maith go leor.

700
00:57:13,400 --> 00:57:17,840
Ag dul ar ais a shórtáil, beidh orainn é seo a dhéanamh go tapa.

701
00:57:17,840 --> 00:57:21,030
Nó cuardaigh. Sórtáil? Sórtáil de. Yeah.

702
00:57:21,030 --> 00:57:22,730
Dul ar ais chuig an tús saghas.

703
00:57:22,730 --> 00:57:29,870
Is mian linn a chruthú algartam go sórtálfar an eagar ag baint úsáide as aon algartam

704
00:57:29,870 --> 00:57:33,660
i O n.

705
00:57:33,660 --> 00:57:40,860
Mar sin é an chaoi sé seo indéanta? An bhfuil aon duine aon saghas -

706
00:57:40,860 --> 00:57:44,300
Hinted mé roimh ar -

707
00:57:44,300 --> 00:57:48,300
Má tá muid ar tí é a fheabhsú ó n log n go dtí O de n,

708
00:57:48,300 --> 00:57:51,450
ní mór dúinn feabhas ar ár algartam am-ciallmhar,

709
00:57:51,450 --> 00:57:55,250
rud a chiallaíonn cad tá muid ag dul go dtí gá a dhéanamh chun a dhéanamh suas le sin?

710
00:57:55,250 --> 00:57:59,520
[Mac léinn] Spás. >> Yeah. Táimid ag dul a bheith ag baint úsáide as níos mó spáis.

711
00:57:59,520 --> 00:58:04,490
Agus ní fiú amháin níos mó spáis, tá sé spás exponentially níos mó.

712
00:58:04,490 --> 00:58:14,320
Mar sin, I mo thuairimse, tá an cineál seo algartam rud éigin pseudo, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Ní féidir liom cuimhneamh orthu. Rud éigin pseudo.

714
00:58:18,980 --> 00:58:22,210
Ach tá sé mar gheall ar gá dúinn úsáid a bhaint as spás an oiread sin

715
00:58:22,210 --> 00:58:28,610
go bhfuil sé seo indéanta ach ní réalaíoch.

716
00:58:28,610 --> 00:58:31,220
>> Agus conas is féidir linn seo a bhaint amach?

717
00:58:31,220 --> 00:58:36,810
Is féidir linn seo a bhaint amach má ráthaíocht againn go bhfuil aon eilimint áirithe i raon

718
00:58:36,810 --> 00:58:39,600
faoi ​​bhun méid áirithe.

719
00:58:42,070 --> 00:58:44,500
Mar sin a ligean ach a rá go bhfuil méid 200,

720
00:58:44,500 --> 00:58:48,130
Tá aon eilimint i sraith thíos mhéid 200.

721
00:58:48,130 --> 00:58:51,080
Agus é seo i ndáiríre an-réadúil.

722
00:58:51,080 --> 00:58:58,660
Is féidir leat an-éasca a bheith le sraith bhfuil a fhios agat gach rud ann

723
00:58:58,660 --> 00:59:00,570
ag dul a bheith níos lú ná le huimhir éigin.

724
00:59:00,570 --> 00:59:07,400
Cosúil má tá tú roinnt veicteoir go hiomlán ollmhór nó rud éigin

725
00:59:07,400 --> 00:59:11,810
ach tá a fhios agat gach rud ag dul a bheith idir 0 agus 5,

726
00:59:11,810 --> 00:59:14,790
ansin tá sé ag dul a bheith i bhfad níos tapúla a dhéanamh.

727
00:59:14,790 --> 00:59:17,930
Agus is é an cheangal ar aon cheann de na heilimintí 5,

728
00:59:17,930 --> 00:59:21,980
sin an cheangal, is é sin cé mhéad cuimhne tú ag dul a bheith ag baint úsáide.

729
00:59:21,980 --> 00:59:26,300
Mar sin, tá an cheangal 200.

730
00:59:26,300 --> 00:59:32,960
Go teoiriciúil tá i gcónaí faoi cheangal toisc gur féidir slánuimhir ach amháin suas go dtí 4 billiún,

731
00:59:32,960 --> 00:59:40,600
ach tá go réalaíoch ó shin ba mhaith linn a bheith ag baint úsáide as spás

732
00:59:40,600 --> 00:59:44,400
ar an ord 4 billiún. Mar sin, tá go réalaíoch.

733
00:59:44,400 --> 00:59:47,060
Ach anseo beidh muid a rá ár cheangal 200.

734
00:59:47,060 --> 00:59:59,570
Is é an trick a dhéanamh i O n linn a dhéanamh eile sraith a dtugtar comhaireamh de mhéid BOUND.

735
00:59:59,570 --> 01:00:10,470
Mar sin, i ndáiríre, tá sé seo aicearra le haghaidh - agam nach iarbhír a bhfuil a fhios má dhéanann clang seo.

736
01:00:11,150 --> 01:00:15,330
Ach i GCC ar a laghad - a dhéanann clang ag glacadh leis I'm sé ró -

737
01:00:15,330 --> 01:00:18,180
beidh sé seo thúsú ach an sraith iomlán a bheith 0s.

738
01:00:18,180 --> 01:00:25,320
Mar sin, más rud é nach bhfuil mé ag iarraidh a dhéanamh sin, ansin d'fhéadfadh liom a dhéanamh ar leithligh le haghaidh (slánuimhir i = 0;

739
01:00:25,320 --> 01:00:31,500
i <cheangal; i + +) agus comhaireamh [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Mar sin, anois tá gach rud initialized chun 0.

741
01:00:35,260 --> 01:00:39,570
I iterate thar mo eagar,

742
01:00:39,570 --> 01:00:51,920
agus cad mé ag déanamh mé ag comhaireamh an líon de gach - ligean ar dul síos anseo.

743
01:00:51,920 --> 01:00:55,480
Tá 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Cad Tá mé ag comhaireamh ar líon tarluithe de gach ceann de na heilimintí sin.

745
01:01:00,010 --> 01:01:03,470
A ligean ar chur i ndáiríre cúpla níos mó i anseo le roinnt repeats.

746
01:01:03,470 --> 01:01:11,070
Mar sin, an luach atá againn anseo, tá an luach na ag dul a bheith eagar [i].

747
01:01:11,070 --> 01:01:14,850
Mar sin, d'fhéadfadh a bheith Val 4 nó 8 nó cibé.

748
01:01:14,850 --> 01:01:18,870
Agus anois tá mé ag comhaireamh cé mhéad de go bhfuil luach mé le feiceáil,

749
01:01:18,870 --> 01:01:21,230
mar sin chomhaireamh [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Tar éis é seo a dhéanamh, tá comhaireamh ag dul rud éigin chun breathnú cosúil le 0001.

751
01:01:29,430 --> 01:01:42,190
Déanaimis comhaireamh a dhéanamh [Val] - BOUND + 1.

752
01:01:42,190 --> 01:01:48,230
>> Anois go díreach chun cuntas a thabhairt ar an bhfíric go bhfuil muid ag tosú ó 0.

753
01:01:48,230 --> 01:01:50,850
Mar sin, má tá 200 ag dul a bheith ár n-uimhir is mó,

754
01:01:50,850 --> 01:01:54,720
ansin 0-200 201 rudaí.

755
01:01:54,720 --> 01:02:01,540
Mar sin, comhaireamh, beidh sé cuma mhaith 00,001 toisc go bhfuil muid ar cheann 4.

756
01:02:01,540 --> 01:02:10,210
Ansin, beidh orainn 0001 nuair a beidh orainn a bheith 1 ar an innéacs 8ú count.

757
01:02:10,210 --> 01:02:14,560
Beidh muid a bheith 2 san innéacs 23ú count.

758
01:02:14,560 --> 01:02:17,630
Beidh muid a bheith 2 san innéacs 42ú count.

759
01:02:17,630 --> 01:02:21,670
Mar sin, is féidir linn úsáid count.

760
01:02:34,270 --> 01:02:44,920
Mar sin, num_of_item = chomhaireamh [i].

761
01:02:44,920 --> 01:02:52,540
Agus mar sin má tá num_of_item 2, ciallaíonn sin ba mhaith linn a chur isteach 2 de líon i

762
01:02:52,540 --> 01:02:55,290
isteach inár eagar curtha in eagar.

763
01:02:55,290 --> 01:03:02,000
Mar sin, ní mór dúinn súil a choinneáil ar cé chomh cóngarach agus tá muid isteach ar an eagar.

764
01:03:02,000 --> 01:03:05,470
= Innéacs sin 0.

765
01:03:05,470 --> 01:03:09,910
Eagar - beidh mé ag scríobh díreach é.

766
01:03:16,660 --> 01:03:18,020
Comhaireamh -

767
01:03:19,990 --> 01:03:28,580
eagar [innéacs + +] = i;

768
01:03:28,580 --> 01:03:32,490
An é sin cad ba mhaith liom? Sílim go bhfuil cad ba mhaith liom.

769
01:03:35,100 --> 01:03:38,290
Sea, Breathnaíonn an dea-. Maith go leor.

770
01:03:38,290 --> 01:03:43,050
Mar sin, ní gach duine a thuiscint cad é an cuspóir de mo eagar chomhaireamh?

771
01:03:43,050 --> 01:03:48,140
Tá sé comhaireamh ar líon tarluithe de gach ceann de na huimhreacha.

772
01:03:48,140 --> 01:03:51,780
Ansin tá mé iterating thar an eagar chomhaireamh,

773
01:03:51,780 --> 01:03:57,190
agus an seasamh sháith sa réimse comhaireamh

774
01:03:57,190 --> 01:04:01,930
Is é an líon Tá i Ba chóir sin le feiceáil i mo eagar curtha in eagar.

775
01:04:01,930 --> 01:04:06,840
Sin an fáth go bhfuil líonta na 4 ag dul a bheith 1

776
01:04:06,840 --> 01:04:11,840
agus tá sé scór de 8 ag dul a bheith 1, comhaireamh de 23 ag dul a bheith 2.

777
01:04:11,840 --> 01:04:16,900
Mar sin, go conas a lán acu ba mhaith liom a chur isteach i mo eagar curtha in eagar.

778
01:04:16,900 --> 01:04:19,200
Ansin, is féidir liom go díreach.

779
01:04:19,200 --> 01:04:28,960
Tá mé isteach i num_of_item Tá mé i mo eagar curtha in eagar.

780
01:04:28,960 --> 01:04:31,670
>> Ceisteanna?

781
01:04:32,460 --> 01:04:43,100
Agus mar sin arís, is é seo am líneach ós rud é táimid iterating díreach os cionn an aon uair amháin,

782
01:04:43,100 --> 01:04:47,470
ach tá sé chomh maith líneach i cad a tharlaíonn an líon seo a bheith,

783
01:04:47,470 --> 01:04:50,730
agus mar sin braitheann sé go mór ar cad é do cheangal.

784
01:04:50,730 --> 01:04:53,290
Le cheangal de 200, ní go go dona.

785
01:04:53,290 --> 01:04:58,330
Má tá do cheangal ag dul a bheith 10,000, ansin go bhfuil beagán níos measa,

786
01:04:58,330 --> 01:05:01,360
ach má tá do cheangal ag dul a bheith 4 billiún, tá go hiomlán neamhréadúil

787
01:05:01,360 --> 01:05:07,720
agus tá an eagar ag dul a bheith a bheith ar mhéid 4 billiún, atá réalaíoch.

788
01:05:07,720 --> 01:05:10,860
Mar sin tá go sin. Ceisteanna?

789
01:05:10,860 --> 01:05:13,270
[Fhreagra mac léinn inaudible] >> Maith go leor.

790
01:05:13,270 --> 01:05:15,710
Thuig mé rud amháin eile nuair a bhí muid ag dul tríd.

791
01:05:17,980 --> 01:05:23,720
Sílim go bhfuil an fhadhb a bhí i Lucas agus is dócha gach ceann amháin againn le feiceáil.

792
01:05:23,720 --> 01:05:26,330
Rinne mé dearmad go hiomlán.

793
01:05:26,330 --> 01:05:31,040
Is é an rud amháin a bhí mé a trácht a dhéanamh ar nuair a bhíonn tú ag déileáil le rudaí mar innéacsanna,

794
01:05:31,040 --> 01:05:38,320
tú riamh a fheiceáil i ndáiríre seo nuair a bhíonn tú ag scríobh do lúb,

795
01:05:38,320 --> 01:05:41,120
ach go teicniúil, aon uair a bhíonn tú ag déileáil leis na hinnéacsanna,

796
01:05:41,120 --> 01:05:45,950
ba chóir duit a deas i gcónaí i bhfad déileáil le slánuimhreacha gan síniú.

797
01:05:45,950 --> 01:05:53,850
Is é an chúis atá leis seo nuair a bhíonn tú ag déileáil le slánuimhreacha sínithe,

798
01:05:53,850 --> 01:05:56,090
mar sin má tá tú 2 slánuimhreacha sínithe agus cuir tú iad le chéile

799
01:05:56,090 --> 01:06:00,640
agus deireadh siad suas ró-mhór, ansin tú deireadh suas le uimhir dhiúltach.

800
01:06:00,640 --> 01:06:03,410
Mar sin, go cad é thar maoil slánuimhir.

801
01:06:03,410 --> 01:06:10,500
>> Má cuir mé 2 billiún agus 1 billiún, tá mé deireadh suas le diúltach 1 billiún.

802
01:06:10,500 --> 01:06:15,480
Sin conas a oibríonn slánuimhreacha ar ríomhairí.

803
01:06:15,480 --> 01:06:17,510
Mar sin, an fhadhb leis úsáid a bhaint as -

804
01:06:17,510 --> 01:06:23,500
Go breá ach amháin má tharlaíonn íseal a bheith 2 billiún agus suas tharlaíonn a bheith 1 billiún,

805
01:06:23,500 --> 01:06:27,120
ansin tá sé seo ag dul a bheith diúltach 1 billiún agus ansin táimid ag dul a roinnt go bhfuil ag 2

806
01:06:27,120 --> 01:06:29,730
agus deireadh suas le diúltacha 500 milliún.

807
01:06:29,730 --> 01:06:33,760
Mar sin, tá sé seo i gceist ach amháin má tharlaíonn tú a bheith ag cuardach trí eagar

808
01:06:33,760 --> 01:06:38,070
na billiúin rudaí.

809
01:06:38,070 --> 01:06:44,050
Ach má tharlaíonn + íseal go dtí thar maoil, ansin é sin an fhadhb.

810
01:06:44,050 --> 01:06:47,750
Chomh luath agus a théimid ar sín iad, ansin tá 2 billiún móide 1 billiún 3 billiún.

811
01:06:47,750 --> 01:06:51,960
Tá 3 billiún roinnt ar 2 1.5 billiún.

812
01:06:51,960 --> 01:06:55,670
Mar sin, mar a luaithe is atá siad gan síniú, tá gach rud foirfe.

813
01:06:55,670 --> 01:06:59,900
Agus mar sin tá go maith i gceist nuair a bhíonn tú ag scríobh do do lúba,

814
01:06:59,900 --> 01:07:03,940
agus i ndáiríre, a dhéanann sé is dócha go huathoibríoch.

815
01:07:09,130 --> 01:07:12,330
Beidh sé i ndáiríre yell díreach ag tú.

816
01:07:12,330 --> 01:07:21,610
Mar sin, má tá an uimhir seo ró-mhór a bheith i slánuimhir ach ach bheadh ​​sé oiriúnach i slánuimhir gan sín,

817
01:07:21,610 --> 01:07:24,970
beidh sé yell ag tú, agus mar sin go bhfuil riamh cén fáth a ritheann tú i ndáiríre an cheist.

818
01:07:29,150 --> 01:07:34,820
Is féidir leat a fheiceáil go bhfuil riamh innéacs ag dul a bheith diúltach,

819
01:07:34,820 --> 01:07:39,220
agus mar sin nuair a bhíonn tú iterating thar eagar,

820
01:07:39,220 --> 01:07:43,970
is féidir leat beagnach i gcónaí a rá gan síniú slánuimhir i, ach ní gá duit i ndáiríre go.

821
01:07:43,970 --> 01:07:47,110
Tá rudaí ag dul a bheith ag obair go leor i bhfad díreach chomh maith.

822
01:07:48,740 --> 01:07:50,090
Maith go leor. [Whispers] Cén t-am é?

823
01:07:50,090 --> 01:07:54,020
An rud deireanach bhí mé a thaispeáint - agus beidh mé a dhéanamh go díreach tapaidh sé i ndáiríre.

824
01:07:54,020 --> 01:08:03,190
Tá a fhios agat conas ní mór dúinn a shainiú # ionas gur féidir linn a shainiú # MAX mar 5 nó rud éigin?

825
01:08:03,190 --> 01:08:05,940
Ní Lig a dhéanamh MAX. # Shainiú BOUND mar 200. Sin an méid a rinne muid roimh.

826
01:08:05,940 --> 01:08:10,380
A shainmhíníonn ar tairiseach, atá ag dul díreach a chóipeáil agus a ghreamú

827
01:08:10,380 --> 01:08:13,010
cibé áit a tharlóidh linn a scríobh BOUND.

828
01:08:13,010 --> 01:08:18,189
>> Mar sin, is féidir linn a dhéanamh iarbhír níos mó le # sainmhíniú.

829
01:08:18,189 --> 01:08:21,170
Is féidir linn a shainiú # feidhmeanna.

830
01:08:21,170 --> 01:08:23,410
Nach bhfuil siad i ndáiríre feidhmeanna, ach beidh orainn glaoch orthu a chomhlíonadh.

831
01:08:23,410 --> 01:08:36,000
Bheadh ​​Sampla rud éigin cosúil le MAX (x, y) Is é an sainmhíniú (x <y y:? X). Maith go leor.

832
01:08:36,000 --> 01:08:40,660
Mar sin, ba chóir duit a fháil a úsáidtear chun comhréir oibreoir trínártha,

833
01:08:40,660 --> 01:08:49,029
ach tá níos lú ná x y? Fill ar ais y, ar ais eile x.

834
01:08:49,029 --> 01:08:54,390
Mar sin, is féidir leat a fheiceáil gur féidir leat a dhéanamh an fheidhm seo ar leith,

835
01:08:54,390 --> 01:09:01,399
agus d'fhéadfadh an fheidhm a bheith cosúil le thógann bool MAX 2 argóintí, seo ar ais.

836
01:09:01,399 --> 01:09:08,340
Tá sé seo ar cheann de na cinn is coitianta a fheiceáil déanta agam mar seo. Glaoch orainn iad a Macraí.

837
01:09:08,340 --> 01:09:11,790
Is é seo an macra.

838
01:09:11,790 --> 01:09:15,859
Is é seo ach an chomhréir chun é.

839
01:09:15,859 --> 01:09:18,740
Is féidir leat scríobh macra a dhéanamh cibé mian leat.

840
01:09:18,740 --> 01:09:22,649
Tú a fheiceáil go minic Macraí le haghaidh debugging printfs agus rudaí.

841
01:09:22,649 --> 01:09:29,410
Mar sin, i ndáil le cineál printf, tá tairisigh speisialta i C cosúil le béim LÍNE béim,

842
01:09:29,410 --> 01:09:31,710
2 béim LÍNE béim,

843
01:09:31,710 --> 01:09:37,550
agus níl freisin I mo thuairimse, 2 béim FEIDHMEANNA. D'fhéadfadh a bheith Sin é. Rud éigin mar sin.

844
01:09:37,550 --> 01:09:40,880
Beidh na rudaí a chur in ionad leis an ainm na feidhme

845
01:09:40,880 --> 01:09:42,930
nó uimhir an líne go bhfuil tú ar.

846
01:09:42,930 --> 01:09:48,630
Go minic, a scríobh tú printfs debugging go síos anseo raibh mé in ann ansin a scríobh ach

847
01:09:48,630 --> 01:09:54,260
Debug agus taispeáin líon líne agus feidhm a tharlaíonn mé a bheith ann

848
01:09:54,260 --> 01:09:57,020
gur bhain sé an ráiteas sin dífhabhtaithe.

849
01:09:57,020 --> 01:09:59,550
Agus is féidir leat a phriontáil freisin rudaí eile.

850
01:09:59,550 --> 01:10:05,990
Mar sin, tá rud amháin ba chóir duit ag faire amach do má tharlaíonn liom a shainmhíniú # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
mar rud éigin cosúil le 2 * y agus 2 * x.

852
01:10:11,380 --> 01:10:14,310
Mar sin, ar chúis ar bith, a tharlóidh leat a dhéanamh go bhfuil a lán.

853
01:10:14,310 --> 01:10:16,650
Mar sin, go mbeadh sé ina macra.

854
01:10:16,650 --> 01:10:18,680
Tá sé seo briste i ndáiríre.

855
01:10:18,680 --> 01:10:23,050
Ba mhaith liom a ghlaoch air ag déanamh rud éigin cosúil le DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Mar sin, cad ba cheart a chur ar ais?

857
01:10:28,840 --> 01:10:30,580
[Mac léinn] 12.

858
01:10:30,580 --> 01:10:34,800
Sea, ba chóir 12 a sheoladh ar ais, agus 12 ar ais.

859
01:10:34,800 --> 01:10:43,350
3 Faigheann ionad le haghaidh x, faigheann 6 in ionad le haghaidh y, agus seol ar ais dúinn 2 * 6, a bhfuil 12.

860
01:10:43,350 --> 01:10:47,710
Anois, cad faoi seo? Cad ba chóir a chur ar ais?

861
01:10:47,710 --> 01:10:50,330
[Mac léinn] 14. >> Go hidéalach, 14.

862
01:10:50,330 --> 01:10:55,290
Is í an tsaincheist sin an chaoi hash sainmhíniú obair, cuimhnigh go bhfuil sé cóip litriúil agus greamaigh

863
01:10:55,290 --> 01:11:00,160
gach rud deas i bhfad, mar sin cad tá sé seo ag dul a léirmhíniú mar

864
01:11:00,160 --> 01:11:11,270
Tá 3 níos lú ná 1 móide 6, 2 uair 1 móide 6, 2 uair 3.

865
01:11:11,270 --> 01:11:19,780
>> Mar sin, ar an gcúis tú beagnach i gcónaí wrap gach rud i lúibíní.

866
01:11:22,180 --> 01:11:25,050
Aon athróg tú beagnach i gcónaí wrap i lúibíní.

867
01:11:25,050 --> 01:11:29,570
Tá cásanna nuair nach gá duit a, cosúil le a fhios agam nach gá dom a dhéanamh anseo

868
01:11:29,570 --> 01:11:32,110
toisc go bhfuil níos lú ná go leor i bhfad i gcónaí ag dul díreach a bheith ag obair,

869
01:11:32,110 --> 01:11:34,330
cé nach fhéadfadh a bheith fiú fíor.

870
01:11:34,330 --> 01:11:41,870
Má tá rud éigin ridiculous cosúil le DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
ansin go ag dul a fháil in ionad le 3 níos lú ná 1 is ionann is ionann 2,

872
01:11:49,760 --> 01:11:53,460
agus mar sin ansin tá sé ag dul a dhéanamh 3 níos lú ná 1, ní go 2 cothrom,

873
01:11:53,460 --> 01:11:55,620
nach bhfuil cad ba mhaith linn.

874
01:11:55,620 --> 01:12:00,730
Mar sin, d'fhonn cosc ​​ar aon oibreoir fadhbanna tosaíocht,

875
01:12:00,730 --> 01:12:02,870
i gcónaí wrap i lúibíní.

876
01:12:03,290 --> 01:12:07,700
Maith go leor. Agus sin é, 05:30.

877
01:12:08,140 --> 01:12:12,470
Má tá aon cheist agat maidir leis an pset, in iúl dúinn.

878
01:12:12,470 --> 01:12:18,010
Ba chóir go mbeadh sé spraoi, agus an t-eagrán hacker freisin i bhfad níos réadúla

879
01:12:18,010 --> 01:12:22,980
ná an t-eagrán hacker na bliana seo caite, mar sin tá súil againn go bhfuil iarracht a lán de tú é.

880
01:12:22,980 --> 01:12:26,460
Last bliana a bhí an-mór.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]