1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Del 3 - Mer komfortabelt]

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

3
00:00:05,070 --> 00:00:07,310
>> [Dette er CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Så det første spørsmålet er merkelig formulert.

5
00:00:12,700 --> 00:00:17,480
GDB lar deg "feilsøke" et program, men mer spesifikt, hva betyr det lar deg gjøre?

6
00:00:17,480 --> 00:00:22,590
Jeg skal svare på det, og jeg vet ikke hva som egentlig forventet,

7
00:00:22,590 --> 00:00:27,910
så jeg gjetter det er noe langs linjene av den lar deg trinn for trinn

8
00:00:27,910 --> 00:00:31,540
gå gjennom programmet, samhandle med det, endre variabler, gjør alle disse tingene -

9
00:00:31,540 --> 00:00:34,270
utgangspunktet helt kontroll utførelsen av et program

10
00:00:34,270 --> 00:00:38,410
og inspisere enhver del av gjennomføringen av programmet.

11
00:00:38,410 --> 00:00:43,030
Så disse funksjonene lar deg feilsøke ting.

12
00:00:43,030 --> 00:00:44,830
Okay.

13
00:00:44,830 --> 00:00:50,520
Hvorfor krever binære søk som en matrise skal sorteres?

14
00:00:50,520 --> 00:00:53,360
Hvem ønsker å svare på det?

15
00:00:56,120 --> 00:01:00,070
[Student] Fordi det fungerer ikke hvis det ikke er sortert. >> Ja. [Latter]

16
00:01:00,070 --> 00:01:04,910
Hvis det ikke er sortert, så det er umulig å dele den i to

17
00:01:04,910 --> 00:01:07,850
og vet at alt til venstre er mindre og alt til høyre

18
00:01:07,850 --> 00:01:10,490
er større enn den midterste verdien.

19
00:01:10,490 --> 00:01:12,790
Så det må sorteres.

20
00:01:12,790 --> 00:01:14,170
Okay.

21
00:01:14,170 --> 00:01:17,570
Hvorfor er boble sortere i O n squared?

22
00:01:17,570 --> 00:01:23,230
Er det noen som først ønsker å gi en svært rask høyt nivå oversikt over hva boble slags er?

23
00:01:25,950 --> 00:01:33,020
[Student] Du i utgangspunktet gå gjennom hvert element, og du sjekker de første elementene.

24
00:01:33,020 --> 00:01:37,150
Hvis de er ute av der du kan utveksle dem, så du sjekke de neste få elementer og så videre.

25
00:01:37,150 --> 00:01:40,770
Når du kommer til slutten, så vet du at det største elementet er plassert på slutten,

26
00:01:40,770 --> 00:01:42,750
så du ignorere at en da du holder på å gå gjennom,

27
00:01:42,750 --> 00:01:48,490
og hver gang du må sjekke en mindre element før du gjør noen endringer. >> Ja.

28
00:01:48,490 --> 00:01:58,470
Det kalles boble slags fordi hvis du snur tabellen på sin side så det er opp og ned, vertikal,

29
00:01:58,470 --> 00:02:03,100
deretter de store verdier vil synke til bunnen og de små verdier vil boble opp til toppen.

30
00:02:03,100 --> 00:02:05,210
Det er hvordan den fikk navnet sitt.

31
00:02:05,210 --> 00:02:08,220
Og ja, du bare gå gjennom.

32
00:02:08,220 --> 00:02:11,190
Du fortsetter gjennom matrisen, bytte ut større verdi

33
00:02:11,190 --> 00:02:14,040
å få de største verdier til bunnen.

34
00:02:14,040 --> 00:02:17,500
>> Hvorfor er det O av n squared?

35
00:02:18,690 --> 00:02:24,620
Først ønsker alle å si hvorfor det er O n squared?

36
00:02:24,620 --> 00:02:28,760
[Student] Fordi for hver kjøring går det n ganger.

37
00:02:28,760 --> 00:02:32,100
Du kan bare være sikker på at du har tatt den største elementet hele veien ned,

38
00:02:32,100 --> 00:02:35,230
så må du gjenta at så mange elementer. >> Ja.

39
00:02:35,230 --> 00:02:41,800
Så husk hva big O betyr og hva store Omega betyr.

40
00:02:41,800 --> 00:02:50,560
Den store O er som øvre grense på hvor sakte det kan faktisk kjøre.

41
00:02:50,560 --> 00:02:58,990
Så ved å si det er O n kvadrat, er det ikke O av n eller annet det ville være i stand til å kjøre

42
00:02:58,990 --> 00:03:02,640
i lineær tid, men det er O n cubed

43
00:03:02,640 --> 00:03:06,390
fordi det er avgrenset av O av n cubed.

44
00:03:06,390 --> 00:03:12,300
Hvis det er avgrenset av O av n kvadrat, så det er avgrenset også av n cubed.

45
00:03:12,300 --> 00:03:20,280
Så det er n kvadrat, og i absolutt verste fall kan det ikke gjøre det bedre enn n squared,

46
00:03:20,280 --> 00:03:22,830
som er hvorfor det er O av n squared.

47
00:03:22,830 --> 00:03:31,200
Så for å se svak matematikk på hvordan det kommer ut til å være n squared,

48
00:03:31,200 --> 00:03:40,530
hvis vi har fem ting i vår liste, første gang hvor mange bytter vi kunne potensielt trenger å gjøre

49
00:03:40,530 --> 00:03:47,170
for å få dette? La oss faktisk bare -

50
00:03:47,170 --> 00:03:52,040
Hvor mange swapper vi nødt til å gjøre i den første kjøring av boble sortere gjennom array?

51
00:03:52,040 --> 00:03:53,540
[Student] n - 1. >> Ja.

52
00:03:53,540 --> 00:03:58,340
>> Hvis det er 5 elementer, vi kommer til å trenge å gjøre n - 1.

53
00:03:58,340 --> 00:04:01,100
Så på den andre hvor mange swapper vi nødt til å gjøre?

54
00:04:01,100 --> 00:04:03,440
[Student] n - 2. >> Ja.

55
00:04:03,440 --> 00:04:11,640
Og den tredje kommer til å være n - 3, og deretter for enkelhets skal jeg skrive de to siste

56
00:04:11,640 --> 00:04:15,270
som da vi kommer til å trenge å gjøre 2 swapper og 1 swap.

57
00:04:15,270 --> 00:04:19,899
Jeg antar det siste kan eller ikke kan faktisk trenger å skje.

58
00:04:19,899 --> 00:04:22,820
Er det en swap? Jeg vet ikke.

59
00:04:22,820 --> 00:04:26,490
Så disse er den samlede swaps eller i det minste sammenligninger du har å gjøre.

60
00:04:26,490 --> 00:04:29,910
Selv om du ikke bytte, du fortsatt trenger å sammenligne verdiene.

61
00:04:29,910 --> 00:04:33,910
Så det er n - 1 sammenligninger i første løp gjennom matrisen.

62
00:04:33,910 --> 00:04:42,050
Hvis du omorganisere disse tingene, la oss faktisk gjøre det seks ting så ting stable opp pent,

63
00:04:42,050 --> 00:04:44,790
og så skal jeg gjøre 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Så bare omorganisere disse summene, ønsker vi å se hvor mange sammenligninger vi gjør

65
00:04:49,910 --> 00:04:52,700
i hele algoritmen.

66
00:04:52,700 --> 00:04:56,550
Så hvis vi tar disse gutta her nede,

67
00:04:56,550 --> 00:05:07,470
så vi er fortsatt bare summere men mange sammenligninger det var.

68
00:05:07,470 --> 00:05:13,280
Men hvis vi oppsummere disse, og vi oppsummere disse, og vi oppsummere disse,

69
00:05:13,280 --> 00:05:18,130
det er fortsatt det samme problemet. Vi bare oppsummere de enkelte grupper.

70
00:05:18,130 --> 00:05:22,400
>> Så nå er vi summere 3 n-tallet. Det er ikke bare 3 n-tallet.

71
00:05:22,400 --> 00:05:27,650
Det er alltid kommer til å være n / 2 n-tallet.

72
00:05:27,650 --> 00:05:29,430
Så her har vi tilfeldigvis har seks.

73
00:05:29,430 --> 00:05:34,830
Hvis vi hadde 10 ting, så vi kunne gjøre denne grupperingen for 5 forskjellige par ting

74
00:05:34,830 --> 00:05:37,180
og ender opp med n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Slik at du alltid kommer til å få n / 2 n-tallet, og så dette vil vi skrive det ut til n squared / 2.

76
00:05:45,840 --> 00:05:48,890
Og så selv om det er den faktoren av halvparten, som skjer for å komme i

77
00:05:48,890 --> 00:05:54,190
grunn av det faktum at gjennom hver iterasjon over matrisen sammenligner vi 1 mindre

78
00:05:54,190 --> 00:05:58,040
så det er hvordan vi får over 2, men det er fortsatt n squared.

79
00:05:58,040 --> 00:06:01,650
Vi bryr oss ikke om den konstante faktoren av en halv.

80
00:06:01,650 --> 00:06:07,760
Så mye stor O ting som dette er avhengig av bare slags gjøre denne typen matematikk,

81
00:06:07,760 --> 00:06:12,260
gjør aritmetiske summer og geometriske rekker ting,

82
00:06:12,260 --> 00:06:17,750
men de fleste av dem i dette kurset er ganske grei.

83
00:06:17,750 --> 00:06:19,290
Okay.

84
00:06:19,290 --> 00:06:24,430
Hvorfor er innsetting sortere i Omega av n? Hva betyr omega?

85
00:06:24,430 --> 00:06:27,730
[To studenter snakker samtidig - uforståelige] >> Ja.

86
00:06:27,730 --> 00:06:30,630
Omega du kan tenke på som nedre grense.

87
00:06:30,630 --> 00:06:36,550
>> Så uansett hvor effektiv din innsetting sortere algoritmen er,

88
00:06:36,550 --> 00:06:41,810
uavhengig av listen som er vedtatt i, har det alltid å sammenligne minst n ting

89
00:06:41,810 --> 00:06:44,620
eller det må iterere over n ting.

90
00:06:44,620 --> 00:06:47,280
Hvorfor er det?

91
00:06:47,280 --> 00:06:51,190
[Student] Fordi hvis listen er allerede sortert, deretter gjennom den første iterasjon

92
00:06:51,190 --> 00:06:54,080
du kan bare garantere at den aller første elementet er den minste,

93
00:06:54,080 --> 00:06:56,490
og den andre iterasjon du kan bare garantere de to første er

94
00:06:56,490 --> 00:07:00,010
fordi du ikke vet at resten av listen er sortert. >> Ja.

95
00:07:00,010 --> 00:07:08,910
Hvis du passerer i en helt sortert liste, i det minste du har å gå over alle elementene

96
00:07:08,910 --> 00:07:12,180
å se at ingenting trenger å bli flyttet rundt.

97
00:07:12,180 --> 00:07:14,720
Så passerer over listen og si oh, er dette allerede sortert,

98
00:07:14,720 --> 00:07:18,240
det er umulig for deg å vite det er sortert før du sjekker hvert element

99
00:07:18,240 --> 00:07:20,660
å se at de er i sortert rekkefølge.

100
00:07:20,660 --> 00:07:25,290
Så den nedre grensen på innsetting sort er Omega n.

101
00:07:25,290 --> 00:07:28,210
Hva er det verste tilfellet kjøretiden flette slag,

102
00:07:28,210 --> 00:07:31,390
verste fall være store O igjen?

103
00:07:31,390 --> 00:07:37,660
Så i verste fall, hvordan merge slags kjøre?

104
00:07:42,170 --> 00:07:43,690
[Student] N log n. >> Ja.

105
00:07:43,690 --> 00:07:49,990
De raskeste generelle sortering algoritmer er n log n. Du kan ikke gjøre det bedre.

106
00:07:51,930 --> 00:07:55,130
>> Det finnes spesielle tilfeller, og hvis vi har tid i dag - men vi sannsynligvis won't -

107
00:07:55,130 --> 00:07:59,330
Vi kunne se en som gjør det bedre enn n log n.

108
00:07:59,330 --> 00:08:04,050
Men i det generelle tilfellet, kan du ikke gjøre det bedre enn n log n.

109
00:08:04,050 --> 00:08:09,680
Og flette slags skjer for å være den du bør vite for dette kurset som er n log n.

110
00:08:09,680 --> 00:08:13,260
Og så vil vi faktisk være å implementere det i dag.

111
00:08:13,260 --> 00:08:18,070
Og til slutt, i mer enn tre setninger, hvordan valg slags arbeid?

112
00:08:18,070 --> 00:08:20,370
Ønsker noen å svare på, og jeg vil telle setninger

113
00:08:20,370 --> 00:08:22,390
fordi hvis du går over 3 -

114
00:08:25,530 --> 00:08:28,330
Husker noen valg slags?

115
00:08:31,280 --> 00:08:37,809
Utvalg sorter er vanligvis ganske lett å huske akkurat fra navnet.

116
00:08:37,809 --> 00:08:45,350
Du bare iterere over tabellen, finne hva den største verdien er eller minste -

117
00:08:45,350 --> 00:08:47,290
den rekkefølgen du sortere i.

118
00:08:47,290 --> 00:08:50,750
Så la oss si at vi sortering fra minste til største.

119
00:08:50,750 --> 00:08:55,250
Du iterere over rekken, på jakt etter uansett minimum element er,

120
00:08:55,250 --> 00:08:59,750
Velg den, og så bare bytte den alt som er i første omgang.

121
00:08:59,750 --> 00:09:04,090
Og så i andre omgang over array, se etter minimum element igjen,

122
00:09:04,090 --> 00:09:07,490
Velg den, og deretter bytte den med hva som er i andre posisjon.

123
00:09:07,490 --> 00:09:10,650
Så vi er bare å velge og vrake minimumsverdiene

124
00:09:10,650 --> 00:09:16,050
og sette dem inn i fronten av matrisen før det er sortert.

125
00:09:19,210 --> 00:09:21,560
Spørsmål om det?

126
00:09:21,560 --> 00:09:25,710
>> Disse uunngåelig vises i skjemaene du må fylle ut når du sender inn pset.

127
00:09:29,010 --> 00:09:32,360
De er i utgangspunktet svar på disse.

128
00:09:32,360 --> 00:09:34,230
Ok, så nå koding problemer.

129
00:09:34,230 --> 00:09:40,140
Jeg har allerede sendt ut via e-post - Var det noen som ikke får det e? Okay.

130
00:09:40,140 --> 00:09:46,630
Jeg har allerede sendt ut via e-post plassen som vi skal bruke,

131
00:09:46,630 --> 00:09:52,120
og hvis du klikker på navnet mitt - så jeg tror jeg kommer til å være på bunnen

132
00:09:52,120 --> 00:09:57,170
på grunn av den bakover r - men hvis du klikker på navnet mitt vil du se to revisjoner.

133
00:09:57,170 --> 00:10:02,650
Revisjon 1 kommer til å bli jeg allerede kopiert og limt inn koden i Spaces

134
00:10:02,650 --> 00:10:06,900
for søket ting du er nødt til å gjennomføre.

135
00:10:06,900 --> 00:10:10,540
Og Revisjon 2 vil være den slags ting som vi gjennomfører etter det.

136
00:10:10,540 --> 00:10:15,770
Så du kan klikke på min Revisjon 1 og jobbe derfra.

137
00:10:17,350 --> 00:10:22,060
Og nå ønsker vi å implementere binære søk.

138
00:10:22,060 --> 00:10:26,470
>> Ønsker noen å bare gi en pseudokode høyt nivå forklaring

139
00:10:26,470 --> 00:10:31,440
av hva vi nødt til å gjøre for søk? Ja.

140
00:10:31,440 --> 00:10:36,170
[Student] Du bare ta midten av tabellen og se om det du leter etter

141
00:10:36,170 --> 00:10:38,650
er mindre enn det eller mer enn det.

142
00:10:38,650 --> 00:10:41,080
Og hvis det er mindre, kan du gå til den halvparten som er mindre,

143
00:10:41,080 --> 00:10:44,750
og hvis det er mer, kan du gå til den halvparten som er mer og gjenta deg at før du bare får én ting.

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

145
00:10:46,570 --> 00:10:51,320
Legg merke til at våre tall utvalg er allerede sortert,

146
00:10:51,320 --> 00:10:57,190
og så det betyr at vi kan dra nytte av det, og vi kunne først sjekke,

147
00:10:57,190 --> 00:11:00,390
okay, jeg ser for nummer 50.

148
00:11:00,390 --> 00:11:03,720
Så jeg kan gå inn i midten.

149
00:11:03,720 --> 00:11:07,380
Midten er vanskelig å definere når det er en enda rekke ting,

150
00:11:07,380 --> 00:11:10,820
men la oss bare si at vi vil alltid avkorte til midten.

151
00:11:10,820 --> 00:11:14,420
Så her har vi 8 ting, så midt ville være 16.

152
00:11:14,420 --> 00:11:17,330
Jeg leter etter 50, så 50 er større enn 16.

153
00:11:17,330 --> 00:11:21,310
Så nå kan jeg i utgangspunktet behandle min matrisen som disse elementene.

154
00:11:21,310 --> 00:11:23,450
Jeg kan kaste bort alt fra 16 over.

155
00:11:23,450 --> 00:11:27,440
Nå er min matrise er bare disse 4 elementene, og jeg gjentar.

156
00:11:27,440 --> 00:11:31,910
Så da jeg ønsker å finne midten igjen, som er tenkt å være 42.

157
00:11:31,910 --> 00:11:34,730
42 er mindre enn 50, så jeg kan kaste bort disse to elementene.

158
00:11:34,730 --> 00:11:36,890
Dette er min gjenværende array.

159
00:11:36,890 --> 00:11:38,430
Jeg kommer til å finne midten igjen.

160
00:11:38,430 --> 00:11:42,100
Jeg antar 50 var et dårlig eksempel fordi jeg var alltid kaste bort ting til venstre,

161
00:11:42,100 --> 00:11:48,280
men på samme måte hvis jeg ser etter noe

162
00:11:48,280 --> 00:11:52,100
og det er mindre enn elementet jeg for øyeblikket ser på,

163
00:11:52,100 --> 00:11:55,080
så jeg kommer til å kaste bort alt til høyre.

164
00:11:55,080 --> 00:11:58,150
Så nå må vi gjennomføre det.

165
00:11:58,150 --> 00:12:02,310
Legg merke til at vi trenger å passere i størrelse.

166
00:12:02,310 --> 00:12:06,730
Vi kan også ikke trenger å hardkode størrelse.

167
00:12:06,730 --> 00:12:11,640
Så hvis vi bli kvitt det # define -

168
00:12:19,630 --> 00:12:21,430
Okay.

169
00:12:21,430 --> 00:12:27,180
Hvordan kan jeg pent finne ut hva størrelsen på tallene matrise for tiden er?

170
00:12:27,180 --> 00:12:30,950
>> Hvor mange elementer er i tallene array?

171
00:12:30,950 --> 00:12:33,630
[Student] Numbers, braketter,. Lengden?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Det finnes ikke i C.

173
00:12:36,600 --> 00:12:38,580
Trenger. Lengde.

174
00:12:38,580 --> 00:12:42,010
Arrays har egenskaper, så det er ingen lengde tilhører arrays

175
00:12:42,010 --> 00:12:45,650
det vil bare gi deg imidlertid lenge det skjer for å være.

176
00:12:48,180 --> 00:12:51,620
[Student] Se hvor mye minne den har, og dividere med hvor mye - >> Ja.

177
00:12:51,620 --> 00:12:55,810
Så hvordan kan vi se hvor mye minne den har? >> [Student] sizeof. >> Ja, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof er operatør som kommer til å returnere størrelsen på tallene matrisen.

179
00:13:01,680 --> 00:13:10,060
Og det kommer til å bli uansett hvor mange heltall det er tider på størrelse med et heltall

180
00:13:10,060 --> 00:13:14,050
siden det er hvor mye minne det er faktisk å ta opp.

181
00:13:14,050 --> 00:13:17,630
Så hvis jeg vil at antall ting i rekken,

182
00:13:17,630 --> 00:13:20,560
så jeg kommer til å ønske å dele av størrelsen på et heltall.

183
00:13:22,820 --> 00:13:26,010
Okay. Så det lar meg passere i størrelse her.

184
00:13:26,010 --> 00:13:29,430
Hvorfor trenger jeg å passere i størrelse i det hele tatt?

185
00:13:29,430 --> 00:13:38,570
Hvorfor kan jeg ikke bare gjøre opp her int size = sizeof (høystakken) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Hvorfor dette ikke fungerer?

187
00:13:41,490 --> 00:13:44,470
[Student] Det er ikke en global variabel.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack eksisterer og vi kjører i tall som høystakken,

189
00:13:51,540 --> 00:13:54,700
og dette er en slags forvarsel om hva som kommer. Ja.

190
00:13:54,700 --> 00:14:00,170
[Student] Haystack er bare referansen til det, så det ville gå tilbake hvor stor den referansen er.

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

192
00:14:02,150 --> 00:14:09,000
Jeg tviler på forelesning som du har sett stabelen ennå virkelig, ikke sant?

193
00:14:09,000 --> 00:14:11,270
Vi har nettopp snakket om det.

194
00:14:11,270 --> 00:14:16,090
Så stabelen er der alle variabler kommer til å bli lagret.

195
00:14:16,090 --> 00:14:19,960
>> Noe minne som er tildelt for lokale variabler kommer i bunken,

196
00:14:19,960 --> 00:14:24,790
og hver funksjon får sin egen plass på stakken, er sin egen stack frame hva det heter.

197
00:14:24,790 --> 00:14:31,590
Så main har sin stack ramme, og innsiden av det kommer til å eksistere dette tall array,

198
00:14:31,590 --> 00:14:34,270
og det kommer til å være av størrelse sizeof (tall).

199
00:14:34,270 --> 00:14:38,180
Det kommer til å ha størrelse med tall delt på størrelsen av elementer,

200
00:14:38,180 --> 00:14:42,010
men at alle liv innenfor hoved stack ramme.

201
00:14:42,010 --> 00:14:45,190
Når vi kaller søk, får sin søken egen stack frame,

202
00:14:45,190 --> 00:14:48,840
sin egen plass til å lagre alle sine lokale variabler.

203
00:14:48,840 --> 00:14:56,420
Men disse argumentene - så høystakken er ikke en kopi av hele denne gruppen.

204
00:14:56,420 --> 00:15:00,990
Vi har ikke passere i hele matrisen som en kopi i søk.

205
00:15:00,990 --> 00:15:04,030
Den passerer bare en referanse til denne matrisen.

206
00:15:04,030 --> 00:15:11,470
Så søk kan få tilgang til disse tallene gjennom denne referansen.

207
00:15:11,470 --> 00:15:17,100
Det er fortsatt tilgang til ting som lever inne i main stack frame,

208
00:15:17,100 --> 00:15:22,990
men innerst inne, når vi kommer til pekere, bør som snart,

209
00:15:22,990 --> 00:15:24,980
dette er hva pekere er.

210
00:15:24,980 --> 00:15:29,400
Pekere er bare referanser til ting, og du kan bruke pekere tilgang til ting

211
00:15:29,400 --> 00:15:32,030
som er i andre ting "stable rammer.

212
00:15:32,030 --> 00:15:37,660
Så selv om tallene er lokale for main, kan vi fortsatt få tilgang til det gjennom denne pekeren.

213
00:15:37,660 --> 00:15:41,770
Men siden det er bare en peker, og det er bare en referanse,

214
00:15:41,770 --> 00:15:45,040
sizeof (høystakken) returnerer bare størrelsen av referansen selv.

215
00:15:45,040 --> 00:15:47,950
Den går ikke tilbake størrelsen på ting det er å peke på.

216
00:15:47,950 --> 00:15:51,110
Den går ikke tilbake den faktiske størrelsen på tall.

217
00:15:51,110 --> 00:15:55,660
Og slik at dette ikke kommer til å fungere som vi vil ha det til.

218
00:15:55,660 --> 00:15:57,320
>> Spørsmål om det?

219
00:15:57,320 --> 00:16:03,250
Pekere vil bli gått inn i betydelig mer blodig detalj i ukene som kommer.

220
00:16:06,750 --> 00:16:13,740
Og dette er grunnen til at mange ting som du ser, de fleste søk ting eller sortere ting,

221
00:16:13,740 --> 00:16:16,990
de er nesten alle kommer til å trenge å ta den faktiske størrelsen på matrisen,

222
00:16:16,990 --> 00:16:20,440
fordi i C, har vi ingen anelse om hva størrelsen på matrisen er.

223
00:16:20,440 --> 00:16:22,720
Du må manuelt gi det i.

224
00:16:22,720 --> 00:16:27,190
Og du kan ikke manuelt passere i hele matrisen fordi du er bare passerer i referansen

225
00:16:27,190 --> 00:16:30,390
og det kan ikke få størrelsen fra referansen.

226
00:16:30,390 --> 00:16:32,300
Okay.

227
00:16:32,300 --> 00:16:38,160
Så nå ønsker vi å gjennomføre det ble forklart før.

228
00:16:38,160 --> 00:16:41,530
Du kan jobbe på det for et øyeblikk,

229
00:16:41,530 --> 00:16:45,250
og du trenger ikke å bekymre deg for å få alt perfekt 100% arbeider.

230
00:16:45,250 --> 00:16:51,410
Bare skrive opp en halv pseudokode for hvordan du tror det skal fungere.

231
00:16:52,000 --> 00:16:53,630
Okay.

232
00:16:53,630 --> 00:16:56,350
Du trenger ikke å være helt ferdig med dette ennå.

233
00:16:56,350 --> 00:17:02,380
Men føles noen komfortabel med hva de har så langt,

234
00:17:02,380 --> 00:17:05,599
som noe vi kan jobbe med sammen?

235
00:17:05,599 --> 00:17:09,690
Ønsker noen å frivillig? Eller jeg vil tilfeldig plukke.

236
00:17:12,680 --> 00:17:18,599
Det trenger ikke å være rett ved andre tiltak, men noe vi kan endre til et fungerende stat.

237
00:17:18,599 --> 00:17:20,720
[Student] Sure. >> Ok.

238
00:17:20,720 --> 00:17:27,220
Så kan du lagre revisjon ved å klikke på den lille ikonet Lagre.

239
00:17:27,220 --> 00:17:29,950
Du ramya, ikke sant? >> [Student] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Så nå kan jeg vise revisjon og alle kan trekke opp revisjonen.

241
00:17:35,140 --> 00:17:38,600
Og her har vi - Ok.

242
00:17:38,600 --> 00:17:43,160
Så ramya gikk med den rekursive løsningen, som er definitivt en gyldig løsning.

243
00:17:43,160 --> 00:17:44,970
Det er to måter du kan gjøre dette problemet.

244
00:17:44,970 --> 00:17:48,060
Du kan enten gjøre det iterativt eller rekursivt.

245
00:17:48,060 --> 00:17:53,860
De fleste problemer du opplever som kan gjøres rekursivt kan også gjøres iterativt.

246
00:17:53,860 --> 00:17:58,510
Så her har vi gjort det rekursivt.

247
00:17:58,510 --> 00:18:03,730
>> Ønsker noen å definere hva det vil si å lage en funksjon rekursiv?

248
00:18:07,210 --> 00:18:08,920
[Student] Når du har en funksjon kalle seg

249
00:18:08,920 --> 00:18:13,470
og deretter kalle seg før det kommer ut med ekte og sann. >> Ja.

250
00:18:13,470 --> 00:18:17,680
En rekursiv funksjon er bare en funksjon som kaller seg.

251
00:18:17,680 --> 00:18:24,140
Det er tre store ting som en rekursiv funksjon må ha.

252
00:18:24,140 --> 00:18:27,310
Den første er åpenbart, kaller det selv.

253
00:18:27,310 --> 00:18:29,650
Den andre er base case.

254
00:18:29,650 --> 00:18:33,390
Så på et tidspunkt funksjonen må slutte å kalle seg selv,

255
00:18:33,390 --> 00:18:35,610
og det er hva base case er for.

256
00:18:35,610 --> 00:18:43,860
Så her vet vi at vi skal slutte, bør vi gi opp i våre søk

257
00:18:43,860 --> 00:18:48,150
når start lik slutt - og vi vil gå over hva det betyr.

258
00:18:48,150 --> 00:18:52,130
Men til slutt, det siste som er viktig for rekursive funksjoner:

259
00:18:52,130 --> 00:18:59,250
funksjonene eller annen måte må nærme seg base case.

260
00:18:59,250 --> 00:19:04,140
Som hvis du ikke faktisk oppdaterer noe når du gjør det andre rekursive kall,

261
00:19:04,140 --> 00:19:07,880
hvis du bokstavelig talt bare kalle funksjonen igjen med de samme argumentene

262
00:19:07,880 --> 00:19:10,130
og ingen globale variabler er endret eller noe,

263
00:19:10,130 --> 00:19:14,430
du vil aldri nå base case, i så fall det er ille.

264
00:19:14,430 --> 00:19:17,950
Det vil være en uendelig rekursjon og en stack overflow.

265
00:19:17,950 --> 00:19:24,330
Men her ser vi at oppdateringen skjer siden vi oppdaterer starte + end / 2,

266
00:19:24,330 --> 00:19:28,180
Vi oppdaterer slutten argumentet her, vi oppdaterer start argument her.

267
00:19:28,180 --> 00:19:32,860
Så i alle rekursive samtaler er vi oppdaterer noe. Okay.

268
00:19:32,860 --> 00:19:38,110
Vil du lede oss gjennom løsningen? >> Ja.

269
00:19:38,110 --> 00:19:44,270
Jeg bruker SearchHelp slik at hver gang jeg gjør denne funksjonen ringe

270
00:19:44,270 --> 00:19:47,910
Jeg har starten av hvor jeg ser etter i rekken og slutten

271
00:19:47,910 --> 00:19:49,380
hvor jeg ser tabellen.

272
00:19:49,380 --> 00:19:55,330
>> På hvert trinn der det er å si det er midt element, som er start + slutt / 2,

273
00:19:55,330 --> 00:19:58,850
er at lik det vi leter etter?

274
00:19:58,850 --> 00:20:04,650
Og hvis det er, så vi fant det, og jeg antar at blir sendt opp nivåer av rekursjon.

275
00:20:04,650 --> 00:20:12,540
Og hvis det ikke er sant, så sjekker vi om det midterste verdien i matrisen er for stor,

276
00:20:12,540 --> 00:20:19,320
i hvilket tilfelle vi se på venstre halvdel av matrisen ved å gå fra start til midten indeksen.

277
00:20:19,320 --> 00:20:22,710
Og ellers gjør vi slutten halvparten.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Okay.

279
00:20:24,740 --> 00:20:27,730
Det høres bra ut.

280
00:20:27,730 --> 00:20:36,640
Ok, så et par ting, og faktisk er dette en meget høyt nivå ting

281
00:20:36,640 --> 00:20:41,270
at du aldri trenger å vite for dette kurset, men det er sant.

282
00:20:41,270 --> 00:20:46,080
Rekursive funksjoner, vil du alltid høre at de er en dårlig deal

283
00:20:46,080 --> 00:20:51,160
fordi hvis du rekursivt kaller deg for mange ganger, får du stack overflow

284
00:20:51,160 --> 00:20:54,990
siden, som jeg sa tidligere, får hver sin funksjon egen stack ramme.

285
00:20:54,990 --> 00:20:59,500
Så hver samtale av den rekursive funksjonen får sin egen stack ramme.

286
00:20:59,500 --> 00:21:04,140
Så hvis du gjør 1000 rekursive samtaler, får du 1000 stabel rammer,

287
00:21:04,140 --> 00:21:08,390
og raskt du føre til å ha for mange stabel rammer og ting bare bryte.

288
00:21:08,390 --> 00:21:13,480
Så det er derfor rekursive funksjoner er generelt dårlig.

289
00:21:13,480 --> 00:21:19,370
Men det er en fin undergruppe av rekursive funksjoner kalles tail-rekursive funksjoner,

290
00:21:19,370 --> 00:21:26,120
og dette skjer for å være et eksempel på en der om kompilatoren merknader dette

291
00:21:26,120 --> 00:21:29,920
og det skal, tror jeg - i Clang hvis du passerer det-O2 flagget

292
00:21:29,920 --> 00:21:33,250
så det vil merke dette er halen rekursive og gjøre ting bra.

293
00:21:33,250 --> 00:21:40,050
>> Det vil gjenbruke samme stack ramme igjen og igjen for hver rekursiv samtale.

294
00:21:40,050 --> 00:21:47,010
Og så siden du bruker den samme stabelen ramme, trenger du ikke å bekymre deg for

295
00:21:47,010 --> 00:21:51,690
noensinne stable overfylte, og på samme tid, som du sa før,

296
00:21:51,690 --> 00:21:56,380
der når du kommer tilbake sant, så det må returnere opp alle disse stabel rammer

297
00:21:56,380 --> 00:22:01,740
og den 10. kallet til SearchHelp har å gå tilbake til det 9., har å gå tilbake til det 8..

298
00:22:01,740 --> 00:22:05,360
Så det trenger ikke å skje når funksjonene er halen rekursiv.

299
00:22:05,360 --> 00:22:13,740
Og så hva gjør denne funksjonen halen rekursive er varsel om at for en gitt samtale til SearchHelp

300
00:22:13,740 --> 00:22:18,470
den rekursive kall som det gjør er hva det tilbake.

301
00:22:18,470 --> 00:22:25,290
Så i den første samtalen til SearchHelp, vi enten umiddelbart return false,

302
00:22:25,290 --> 00:22:29,590
umiddelbart returnere true, eller vi gjør en rekursiv kall til SearchHelp

303
00:22:29,590 --> 00:22:33,810
der hva vi er tilbake er hva det ringes tilbake.

304
00:22:33,810 --> 00:22:51,560
Og vi kunne ikke gjøre dette hvis vi gjorde noe sånt int x = SearchHelp, retur x * 2,

305
00:22:51,560 --> 00:22:55,440
bare noen tilfeldige endringer.

306
00:22:55,440 --> 00:23:01,470
>> Så nå denne rekursive kall, denne int x = SearchHelp rekursiv samtale,

307
00:23:01,470 --> 00:23:05,740
ikke lenger hale rekursiv fordi det faktisk ikke å returnere

308
00:23:05,740 --> 00:23:10,400
tilbake til en tidligere stabel rammen slik at den forrige kallet til funksjonen

309
00:23:10,400 --> 00:23:13,040
Deretter kan gjøre noe med returverdi.

310
00:23:13,040 --> 00:23:22,190
Så dette er ikke hale rekursiv, men hva vi hadde før er pent halen rekursiv. Ja.

311
00:23:22,190 --> 00:23:27,000
[Student] Burde ikke andre base case kontrolleres første

312
00:23:27,000 --> 00:23:30,640
fordi det kan være en situasjon der når du passerer det argumentet

313
00:23:30,640 --> 00:23:35,770
du har start = slutt, men de er nålen verdi.

314
00:23:35,770 --> 00:23:47,310
Spørsmålet ble ikke kan vi kjøre inn i saken der slutten er nålen verdi

315
00:23:47,310 --> 00:23:52,000
eller start = slutt, riktig, start = slutt

316
00:23:52,000 --> 00:23:59,480
og du har faktisk ikke sjekket den aktuelle verdi ennå,

317
00:23:59,480 --> 00:24:03,910
deretter starte + end / 2 er bare kommer til å være den samme verdi.

318
00:24:03,910 --> 00:24:07,890
Men vi har allerede returnert falsk og vi vil aldri sjekket verdien.

319
00:24:07,890 --> 00:24:14,240
Så i det minste, i den første samtalen, hvis størrelse er 0, så vi ønsker å gå tilbake falske.

320
00:24:14,240 --> 00:24:17,710
Men hvis størrelsen er 1, så start ikke kommer til å like enden,

321
00:24:17,710 --> 00:24:19,820
og vi vil i det minste sjekke det ett element.

322
00:24:19,820 --> 00:24:26,750
Men jeg tror du har rett i at vi kan ende opp i en sak hvor begynner + end / 2,

323
00:24:26,750 --> 00:24:31,190
oppstart ender opp med å bli det samme som start + slutt / 2,

324
00:24:31,190 --> 00:24:35,350
men vi har aldri faktisk sjekket dette elementet.

325
00:24:35,350 --> 00:24:44,740
>> Så hvis vi først sjekke er midt element verdien vi leter etter,

326
00:24:44,740 --> 00:24:47,110
så kan vi umiddelbart returnere true.

327
00:24:47,110 --> 00:24:50,740
Else hvis de er like, så er det ingen vits i å fortsette

328
00:24:50,740 --> 00:24:58,440
siden vi bare kommer til å oppdatere til en sak hvor vi er på en enkelt-element array.

329
00:24:58,440 --> 00:25:01,110
Hvis det eneste element er ikke den vi leter etter,

330
00:25:01,110 --> 00:25:03,530
så alt er galt. Ja.

331
00:25:03,530 --> 00:25:08,900
[Student] Saken er at siden størrelsen er faktisk større enn antall av elementer i matrisen,

332
00:25:08,900 --> 00:25:13,070
Det er allerede en offset - >> Så vil størrelse -

333
00:25:13,070 --> 00:25:19,380
[Student] Si hvis matrisen var størrelse 0, så SearchHelp vil faktisk sjekke høystakk av 0

334
00:25:19,380 --> 00:25:21,490
på den første ring.

335
00:25:21,490 --> 00:25:25,300
Matrisen har størrelse 0, så 0 er - >> Ja.

336
00:25:25,300 --> 00:25:30,750
Det er en annen ting som - det kan være bra. La oss tenke.

337
00:25:30,750 --> 00:25:40,120
Så hvis matrisen hadde 10 elementer og den mellomste vi kommer til å sjekke er indeks 5,

338
00:25:40,120 --> 00:25:45,700
så vi sjekker 5, og la oss si at verdien er mindre.

339
00:25:45,700 --> 00:25:50,720
Så vi kaster bort alt fra 5 og oppover.

340
00:25:50,720 --> 00:25:54,030
Så starter + end / 2 kommer til å bli vår nye end,

341
00:25:54,030 --> 00:25:57,450
så ja, det er alltid kommer til å bo utover slutten av tabellen.

342
00:25:57,450 --> 00:26:03,570
Hvis det er en sak dersom det var partall eller oddetall, så ville vi sjekke, sier, 4,

343
00:26:03,570 --> 00:26:05,770
men vi er fortsatt kaster bort -

344
00:26:05,770 --> 00:26:13,500
Så ja, er slutt alltid kommer til å være utenfor selve enden av tabellen.

345
00:26:13,500 --> 00:26:18,350
Så de elementene vi fokuserer på, er slutten alltid kommer til å være den etter det.

346
00:26:18,350 --> 00:26:24,270
Og så hvis start gjør stadig like enden, er vi i en rekke størrelse 0.

347
00:26:24,270 --> 00:26:35,600
>> Den andre tingen jeg tenkte er at vi oppdaterer start skal starte + end / 2,

348
00:26:35,600 --> 00:26:44,020
så dette er tilfelle at jeg har problemer med, hvor skal + end / 2

349
00:26:44,020 --> 00:26:46,820
er elementet vi sjekker.

350
00:26:46,820 --> 00:26:58,150
La oss si at vi hadde denne 10-element array. Uansett.

351
00:26:58,150 --> 00:27:03,250
Så starter + end / 2 kommer til å være noe som dette,

352
00:27:03,250 --> 00:27:07,060
og hvis det er ikke verdien, sier vi vil oppdatere.

353
00:27:07,060 --> 00:27:10,060
Verdien er større, så vi ønsker å se på denne halvdelen av tabellen.

354
00:27:10,060 --> 00:27:15,910
Så hvordan vi oppdaterer start, skal vi oppdatere start nå være dette elementet.

355
00:27:15,910 --> 00:27:23,790
Men dette kan likevel fungere, eller i det minste, kan du gjøre start + slutt / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Student] Du trenger ikke å være start + slutt [hørbar] >> Ja.

357
00:27:27,850 --> 00:27:33,240
Vi har allerede sjekket dette elementet og vet at det er ikke den vi leter etter.

358
00:27:33,240 --> 00:27:36,800
Slik at vi ikke trenger å oppdatere start til å være dette elementet.

359
00:27:36,800 --> 00:27:39,560
Vi kan bare hoppe over det og oppdatere begynne å være dette elementet.

360
00:27:39,560 --> 00:27:46,060
Og er det noen gang en sak, la oss si at dette var slutten,

361
00:27:46,060 --> 00:27:53,140
så da starter ville være dette, start + end / 2 ville være dette,

362
00:27:53,140 --> 00:28:00,580
start + slutt - Ja, jeg tror det kan ende opp i uendelig rekursjon.

363
00:28:00,580 --> 00:28:12,690
La oss si det er bare et utvalg av størrelse 2 eller en rekke størrelse 1. Jeg tror dette vil fungere.

364
00:28:12,690 --> 00:28:19,490
Så nå er starten at element og slutten er en utover det.

365
00:28:19,490 --> 00:28:24,110
Så element som vi kommer til å sjekke er denne,

366
00:28:24,110 --> 00:28:29,400
og når vi oppdaterer start, skal vi oppdatere start til å være 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
som kommer til å ende oss tilbake med start blir dette elementet.

368
00:28:33,160 --> 00:28:36,210
>> Så vi sjekker den samme element igjen og igjen.

369
00:28:36,210 --> 00:28:43,310
Så dette er tilfelle der hver rekursiv samtale må faktisk oppdatere noe.

370
00:28:43,310 --> 00:28:48,370
Så vi trenger å gjøre start + slutt / 2 + 1, ellers er det en sak

371
00:28:48,370 --> 00:28:50,710
der vi ikke egentlig oppdaterer start.

372
00:28:50,710 --> 00:28:53,820
Alle se det?

373
00:28:53,820 --> 00:28:56,310
Okay.

374
00:28:56,310 --> 00:29:03,860
Har noen spørsmål om denne løsningen eller flere kommentarer?

375
00:29:05,220 --> 00:29:10,280
Okay. Er det noen som har en iterativ løsning som vi alle kan se på?

376
00:29:17,400 --> 00:29:20,940
Har vi alle gjøre det rekursivt?

377
00:29:20,940 --> 00:29:25,950
Eller også jeg antar at hvis du åpnet hennes, så du kan ha overstyres det gamle.

378
00:29:25,950 --> 00:29:28,810
Betyr det automatisk lagre? Jeg er ikke positivt.

379
00:29:35,090 --> 00:29:39,130
Er det noen som har iterativ?

380
00:29:39,130 --> 00:29:42,430
Vi kan gå gjennom det sammen hvis ikke.

381
00:29:46,080 --> 00:29:48,100
Ideen er kommer til å være den samme.

382
00:30:00,260 --> 00:30:02,830
Iterativ løsning.

383
00:30:02,830 --> 00:30:07,140
Vi kommer til å ønske å utgangspunktet gjøre det samme ideen

384
00:30:07,140 --> 00:30:16,530
der vi ønsker å holde styr på den nye enden av tabellen og den nye starten av tabellen

385
00:30:16,530 --> 00:30:18,510
og gjøre det om og om igjen.

386
00:30:18,510 --> 00:30:22,430
Og hvis det vi holder styr på som starten og slutten noensinne møtes,

387
00:30:22,430 --> 00:30:29,020
da vi ikke fant den, og vi kan return false.

388
00:30:29,020 --> 00:30:37,540
Så hvordan gjør jeg det? Alle som har forslag eller kode for meg å trekke opp?

389
00:30:42,190 --> 00:30:47,450
[Student] Gjør en stund loop. >> Ja.

390
00:30:47,450 --> 00:30:49,450
Du kommer til å ønske å gjøre en loop.

391
00:30:49,450 --> 00:30:51,830
>> Visste du har koden jeg kunne trekke opp, eller hva skulle du foreslå?

392
00:30:51,830 --> 00:30:56,340
[Student] Jeg tror det. >> Greit. Dette gjør ting enklere. Hva var navnet ditt?

393
00:30:56,340 --> 00:30:57,890
[Student] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revisjon 1. Okay.

395
00:31:04,190 --> 00:31:13,200
Low er det vi kalte starte før.

396
00:31:13,200 --> 00:31:17,080
Opp er ikke helt hva vi kalte slutten før.

397
00:31:17,080 --> 00:31:22,750
Egentlig er slutt nå i matrisen. Det er et element vi bør vurdere.

398
00:31:22,750 --> 00:31:26,890
Så lav er 0, er opp størrelsen av matrisen - 1,

399
00:31:26,890 --> 00:31:34,780
og nå er vi looping, og vi sjekker -

400
00:31:34,780 --> 00:31:37,340
Jeg antar du kan gå gjennom den.

401
00:31:37,340 --> 00:31:41,420
Hva var din tenkning gjennom dette? Lede oss gjennom koden din.

402
00:31:41,420 --> 00:31:49,940
[Student] Sure. Se på høystakken verdi i midten og sammenlign det med nål.

403
00:31:49,940 --> 00:31:58,520
Så hvis det er større enn nål ditt, så du vil - oh, faktisk, bør det være bakover.

404
00:31:58,520 --> 00:32:05,180
Du kommer til å ønske å kaste bort den høyre halvdelen, og så ja, det burde være slik.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Så dette bør være mindre? Er det det du sa? >> [Student] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okay. Mindre.

407
00:32:10,390 --> 00:32:15,700
Så hvis det vi ser på er mindre enn hva vi ønsker,

408
00:32:15,700 --> 00:32:19,410
så ja, vi ønsker å kaste bort den venstre halvdelen,

409
00:32:19,410 --> 00:32:22,210
som betyr at vi oppdaterer alt vi vurderer

410
00:32:22,210 --> 00:32:26,610
ved å flytte lav til høyre for matrisen.

411
00:32:26,610 --> 00:32:30,130
Dette ser bra ut.

412
00:32:30,130 --> 00:32:34,550
Jeg tror det har det samme problemet som vi sa på den forrige,

413
00:32:34,550 --> 00:32:49,760
der hvis lav er 0 og opp er 1, deretter lav + opp / 2 kommer til å sette opp til å bli det samme igjen.

414
00:32:49,760 --> 00:32:53,860
>> Og selv om det ikke er tilfelle, er det fortsatt mer effektiv i det minste

415
00:32:53,860 --> 00:32:57,630
å bare kaste bort elementet vi bare så på som vi vet er galt.

416
00:32:57,630 --> 00:33:03,240
Så lav + opp / 2 + 1 - >> [student] Det burde være den andre veien.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Eller denne skal være - 1 og den andre en bør være + 1.

418
00:33:05,900 --> 00:33:09,580
[Student] Og det bør være en dobbel likhetstegn. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Student] Yeah.

420
00:33:14,540 --> 00:33:15,910
Okay.

421
00:33:15,910 --> 00:33:21,280
Og til slutt, nå som vi har denne + 1 - 1 ting,

422
00:33:21,280 --> 00:33:31,520
er det - det kan ikke være - er det noen gang mulig for lav til å ende opp med en høyere verdi enn opp?

423
00:33:35,710 --> 00:33:40,320
Jeg tror den eneste måten som kan skje - Er det mulig? >> [Student] Jeg vet ikke.

424
00:33:40,320 --> 00:33:45,220
Men hvis det blir avkortet og da får minus at 1 og deretter - >> Ja.

425
00:33:45,220 --> 00:33:47,480
[Student] Det ville muligens bli søl opp.

426
00:33:49,700 --> 00:33:53,940
Jeg tror det skal være bra bare fordi

427
00:33:53,940 --> 00:33:58,800
for det å ende opp lavere de måtte være lik, tror jeg.

428
00:33:58,800 --> 00:34:03,070
Men hvis de er like, så vi ville ikke ha gjort det mens loop til å begynne med

429
00:34:03,070 --> 00:34:06,670
og vi ville bare ha returnert verdien. Så jeg tror vi bra nå.

430
00:34:06,670 --> 00:34:11,530
Legg merke til at selv om dette problemet er ikke lenger rekursive

431
00:34:11,530 --> 00:34:17,400
samme type ideer gjelder hvor vi kan se hvordan dette så lett gir seg

432
00:34:17,400 --> 00:34:23,659
til en rekursiv løsning av det faktum at vi bare oppdatering av indeksene igjen og igjen,

433
00:34:23,659 --> 00:34:29,960
vi gjør problemet mindre og mindre, fokuserer vi på en undergruppe av tabellen.

434
00:34:29,960 --> 00:34:40,860
[Student] Hvis lav er 0 og opp er en, ville de begge være 0 + 1/2, noe som ville gå til 0,

435
00:34:40,860 --> 00:34:44,429
og da ville være + 1, ville man være - en.

436
00:34:47,000 --> 00:34:50,870
[Student] Hvor er vi sjekker likestilling?

437
00:34:50,870 --> 00:34:55,100
Som hvis den midterste er faktisk nål?

438
00:34:55,100 --> 00:34:58,590
Vi er ikke tiden gjør det? Oh!

439
00:35:00,610 --> 00:35:02,460
Hvis det er -

440
00:35:05,340 --> 00:35:13,740
Ja. Vi kan ikke bare gjøre testen her nede fordi la oss si den første midten -

441
00:35:13,740 --> 00:35:16,430
[Student] Det er faktisk liker ikke kaste bort den bundne.

442
00:35:16,430 --> 00:35:20,220
Så hvis du kaster bort bundet, må du sjekke det første eller hva.

443
00:35:20,220 --> 00:35:23,350
Ah. Ja. >> [Student] Yeah.

444
00:35:23,350 --> 00:35:29,650
Så nå har vi kastet bort den vi i dag sett på,

445
00:35:29,650 --> 00:35:33,260
noe som betyr at vi nå må også ha

446
00:35:33,260 --> 00:35:44,810
if (høystakken [(lav + opp) / 2] == p), så kan vi returnere true.

447
00:35:44,810 --> 00:35:52,070
Og om jeg legger andre eller bare hvis, det betyr bokstavelig talt det samme

448
00:35:52,070 --> 00:35:57,110
fordi dette ville ha returnert sant.

449
00:35:57,110 --> 00:36:01,450
Så jeg skal sette else if, men det spiller ingen rolle.

450
00:36:01,450 --> 00:36:10,440
>> Så annet hvis dette, ellers dette, og dette er en vanlig ting jeg gjør

451
00:36:10,440 --> 00:36:14,340
der selv om det er tilfelle der alt er bra her,

452
00:36:14,340 --> 00:36:22,780
som lav aldri kan være større enn opp, er det ikke verdt resonnement om hvorvidt det er sant.

453
00:36:22,780 --> 00:36:28,010
Så du kan like godt si mens lav er mindre enn eller lik

454
00:36:28,010 --> 00:36:30,720
eller mens lav er mindre enn

455
00:36:30,720 --> 00:36:35,300
så hvis de noen gang likt eller lav skjer til å passere,

456
00:36:35,300 --> 00:36:40,130
så kan vi bryte ut av denne loopen.

457
00:36:41,410 --> 00:36:44,630
Spørsmål, bekymringer, kommentarer?

458
00:36:47,080 --> 00:36:49,270
Okay. Dette ser bra ut.

459
00:36:49,270 --> 00:36:52,230
Nå ønsker vi å gjøre slag.

460
00:36:52,230 --> 00:37:04,030
Hvis vi går til min andre revisjon, ser vi de samme tallene,

461
00:37:04,030 --> 00:37:07,550
men nå er de ikke lenger i sortert rekkefølge.

462
00:37:07,550 --> 00:37:12,840
Og vi ønsker å implementere Sorter etter en algoritme O n log n.

463
00:37:12,840 --> 00:37:17,240
Så hvilken algoritme tror du vi bør iverksette her? >> [Student] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Flette sort er O (n log n), så det er det vi kommer til å gjøre.

465
00:37:23,810 --> 00:37:26,680
Og problemet kommer til å bli ganske lik,

466
00:37:26,680 --> 00:37:31,920
der det gir lett seg en rekursiv løsning.

467
00:37:31,920 --> 00:37:35,580
Vi kan også komme opp med en iterativ løsning hvis vi vil,

468
00:37:35,580 --> 00:37:42,540
men rekursjon vil være lettere her, og vi skal gjøre rekursjon.

469
00:37:45,120 --> 00:37:49,530
Jeg tror vi vil gå gjennom flette slag først,

470
00:37:49,530 --> 00:37:54,280
selv om det er en nydelig video på Merge slags allerede. [Latter]

471
00:37:54,280 --> 00:37:59,780
Så flette slags det er - jeg kaster bort så mye av dette papiret.

472
00:37:59,780 --> 00:38:02,080
Å, det er bare en igjen.

473
00:38:02,080 --> 00:38:03,630
Så flette.

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

475
00:38:26,090 --> 00:38:27,440
Okay.

476
00:38:29,910 --> 00:38:33,460
Merge tar to separate arrays.

477
00:38:33,460 --> 00:38:36,780
Individuelt de to arrayene er begge sorteres.

478
00:38:36,780 --> 00:38:40,970
Så denne matrise, 1, 3, 5, sortert. Denne matrise, 0, 2, 4, sortert.

479
00:38:40,970 --> 00:38:46,710
Nå hva fusjonere bør gjøre er å kombinere dem i en enkelt rekke som selv sortert.

480
00:38:46,710 --> 00:38:57,130
Så vi ønsker en rekke størrelse 6 som kommer til å ha disse elementene innsiden av det

481
00:38:57,130 --> 00:38:59,390
i sortert rekkefølge.

482
00:38:59,390 --> 00:39:03,390
>> Og så kan vi dra nytte av det faktum at disse to arrays er sortert

483
00:39:03,390 --> 00:39:06,800
å gjøre dette i lineær tid,

484
00:39:06,800 --> 00:39:13,510
lineær tid mening hvis denne tabellen er størrelse x og dette er størrelsen y,

485
00:39:13,510 --> 00:39:20,970
deretter den totale algoritme bør være O (x + y). Okay.

486
00:39:20,970 --> 00:39:23,150
Så forslag.

487
00:39:23,150 --> 00:39:26,030
[Student] Kan vi starte fra venstre?

488
00:39:26,030 --> 00:39:30,150
Så du vil sette 0 ned først og deretter 1 og deretter her du er på 2.

489
00:39:30,150 --> 00:39:33,320
Så det er litt som du har en fane som skal flytte til høyre. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
For begge disse arrays hvis vi bare fokusere på den venstre element.

491
00:39:41,070 --> 00:39:43,530
Fordi begge arrays er sortert, vet vi at disse to elementene

492
00:39:43,530 --> 00:39:46,920
er de minste elementene i enten array.

493
00:39:46,920 --> 00:39:53,500
Så det betyr at en av de to elementene må være det minste elementet i vår fusjonerte array.

494
00:39:53,500 --> 00:39:58,190
Det bare så skjer at den minste er en på rett denne gangen.

495
00:39:58,190 --> 00:40:02,580
Så vi tar 0, sett den på venstre fordi 0 er mindre enn 1,

496
00:40:02,580 --> 00:40:08,210
så ta 0, sette det inn i vår første posisjon, og da vi oppdatere denne

497
00:40:08,210 --> 00:40:12,070
å nå fokusere på det første elementet.

498
00:40:12,070 --> 00:40:14,570
Og nå har vi gjenta.

499
00:40:14,570 --> 00:40:20,670
Så nå er vi sammenligne to og en. 1 er mindre, så vi får sett 1.

500
00:40:20,670 --> 00:40:25,300
Vi oppdaterer denne pekeren til å peke til denne fyren.

501
00:40:25,300 --> 00:40:33,160
Nå gjør vi det igjen, så to. Dette vil oppdatere, sammenligne disse to, tre.

502
00:40:33,160 --> 00:40:37,770
Dette oppdaterer, deretter 4 og 5.

503
00:40:37,770 --> 00:40:42,110
Så det er flettingen.

504
00:40:42,110 --> 00:40:49,010
>> Det bør være ganske åpenbart at det er lineær tid siden vi bare gå over hvert element gang.

505
00:40:49,010 --> 00:40:55,980
Og det er den største skritt for å implementere fusjonere slags gjør dette.

506
00:40:55,980 --> 00:40:59,330
Og det er ikke så vanskelig.

507
00:40:59,330 --> 00:41:15,020
Et par ting å bekymre seg er la oss si at vi ble sammenslåing 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
I dette tilfellet ender vi opp i situasjonen der dette kommer til å bli mindre,

509
00:41:30,930 --> 00:41:36,160
så vi oppdaterer denne pekeren, er dette en kommer til å være mindre, oppdatere denne,

510
00:41:36,160 --> 00:41:41,280
dette er mindre, og nå må du kjenne

511
00:41:41,280 --> 00:41:44,220
når du faktisk har kjørt ut av elementer for å sammenligne med.

512
00:41:44,220 --> 00:41:49,400
Siden vi allerede har brukt hele denne array,

513
00:41:49,400 --> 00:41:55,190
alt i denne matrisen er nå bare satt inn her.

514
00:41:55,190 --> 00:42:02,040
Så hvis vi noen gang får det punktet hvor en av våre arrays er helt fusjonert allerede,

515
00:42:02,040 --> 00:42:06,510
så vi bare ta alle elementene i den andre rekke og sette dem inn i slutten av tabellen.

516
00:42:06,510 --> 00:42:13,630
Så vi kan bare sette 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Det er én ting å se opp for.

518
00:42:22,080 --> 00:42:26,120
Implementering som bør være trinn 1.

519
00:42:26,120 --> 00:42:32,600
Flett sortere da basert på det, det er to trinn, to dumme trinn.

520
00:42:38,800 --> 00:42:42,090
La oss bare gi denne tabellen.

521
00:42:57,920 --> 00:43:05,680
Så flette slag, er trinn 1 til rekursivt bryte rekken i halvdeler.

522
00:43:05,680 --> 00:43:09,350
Så dele denne tabellen i halvdeler.

523
00:43:09,350 --> 00:43:22,920
Vi har nå 4, 15, 16, 50 og 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Og nå gjør vi det igjen, og vi delt disse inn halvdeler.

525
00:43:25,800 --> 00:43:27,530
Jeg vil bare gjøre det på denne siden.

526
00:43:27,530 --> 00:43:34,790
SO 4, 15 og 16, 50.

527
00:43:34,790 --> 00:43:37,440
Vi ville gjøre det samme over her.

528
00:43:37,440 --> 00:43:40,340
Og nå har vi delt det inn i halvdeler igjen.

529
00:43:40,340 --> 00:43:51,080
Og vi har 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Så det er vår base case.

531
00:43:53,170 --> 00:44:00,540
Når arrays er av størrelse 1, så vi stoppe med delingen i halvdeler.

532
00:44:00,540 --> 00:44:03,190
>> Nå hva gjør vi med dette?

533
00:44:03,190 --> 00:44:15,730
Vi ender opp dette vil også brytes ned i 8, 23, 42, og 108.

534
00:44:15,730 --> 00:44:24,000
Så nå som vi er på dette punktet, nå trinn to av fletting slag er bare å flette par til listene.

535
00:44:24,000 --> 00:44:27,610
Så vi ønsker å slå sammen disse. Vi bare ringe flette.

536
00:44:27,610 --> 00:44:31,410
Vi vet fusjonere vil returnere disse i sortert rekkefølge.

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

538
00:44:33,920 --> 00:44:41,440
Nå ønsker vi å flette disse, og som vil returnere en liste med de i sortert rekkefølge,

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

540
00:44:44,160 --> 00:44:57,380
Vi fletter dem - jeg kan ikke skrive - 8, 23 og 42, 108.

541
00:44:57,380 --> 00:45:02,890
Så vi har fusjonert par gang.

542
00:45:02,890 --> 00:45:05,140
Nå er vi bare slå igjen.

543
00:45:05,140 --> 00:45:10,130
Legg merke til at hver av disse listene er sortert i seg selv,

544
00:45:10,130 --> 00:45:15,220
og da kan vi bare slå sammen disse listene for å få en liste over størrelse 4 som er sortert

545
00:45:15,220 --> 00:45:19,990
og slå sammen disse to listene for å få en liste over størrelse 4 som er sortert.

546
00:45:19,990 --> 00:45:25,710
Og til slutt, kan vi slå de to lister over størrelsen 4 for å få en liste over størrelsen 8 som er sortert.

547
00:45:25,710 --> 00:45:34,030
Så for å se at dette er generelle n log n, vi allerede så at flettingen er lineær,

548
00:45:34,030 --> 00:45:40,390
så når vi har å gjøre med sammenslåing disse, så som den totale kostnaden for flettingen

549
00:45:40,390 --> 00:45:43,410
for disse to listene er bare 2 fordi -

550
00:45:43,410 --> 00:45:49,610
Eller vel, det er O av n, men n her er bare disse to elementene, så det er to.

551
00:45:49,610 --> 00:45:52,850
Og disse to vil være 2, og disse to vil være 2, og disse to vil være 2,

552
00:45:52,850 --> 00:45:58,820
så over alle de fusjonerer som vi trenger å gjøre, ender vi opp med å gjøre n.

553
00:45:58,820 --> 00:46:03,210
Som 2 + 2 + 2 + 2 er 8, som er n,

554
00:46:03,210 --> 00:46:08,060
slik at kostnaden for sammenslåing i dette settet er n.

555
00:46:08,060 --> 00:46:10,810
Og så det samme her.

556
00:46:10,810 --> 00:46:16,980
Vi vil slå sammen disse to, da disse to, og individuelt denne sammenslåingen vil ta fire operasjoner,

557
00:46:16,980 --> 00:46:23,610
Dette fusjonere vil ta fire operasjoner, men nok en gang, mellom alle disse,

558
00:46:23,610 --> 00:46:29,030
vi ender opp sammenslåing n totalt ting, og så dette trinnet tar n.

559
00:46:29,030 --> 00:46:33,670
Og så hvert nivå tar n elementer blir slått sammen.

560
00:46:33,670 --> 00:46:36,110
>> Og hvor mange nivåer er det?

561
00:46:36,110 --> 00:46:40,160
På hvert nivå, vokser vår rekke av størrelse 2.

562
00:46:40,160 --> 00:46:44,590
Her våre arrays er av størrelse 1, her er de på størrelse 2, her er de i størrelse 4,

563
00:46:44,590 --> 00:46:46,470
og til slutt, de er av størrelse 8.

564
00:46:46,470 --> 00:46:56,450
Så siden det er en dobling, er det kommer til å være totalt log n av disse nivåene.

565
00:46:56,450 --> 00:47:02,090
Så med log n nivåer, hvert enkelt nivå tar n samlede virksomhet,

566
00:47:02,090 --> 00:47:05,720
vi får en n log n algoritme.

567
00:47:05,720 --> 00:47:07,790
Spørsmål?

568
00:47:08,940 --> 00:47:13,320
Har folk allerede gjort fremskritt på hvordan å gjennomføre dette?

569
00:47:13,320 --> 00:47:18,260
Er det noen som allerede er i en tilstand hvor jeg kan bare trekke opp koden sin?

570
00:47:20,320 --> 00:47:22,260
Jeg kan gi et minutt.

571
00:47:24,770 --> 00:47:27,470
Dette kommer til å bli lenger.

572
00:47:27,470 --> 00:47:28,730
Jeg anbefaler går igjen -

573
00:47:28,730 --> 00:47:30,510
Du trenger ikke å gjøre rekursjon for flettingen

574
00:47:30,510 --> 00:47:33,750
fordi å gjøre rekursjon for flettingen, du nødt til å passere en haug med forskjellige størrelser.

575
00:47:33,750 --> 00:47:37,150
Du kan, men det er irriterende.

576
00:47:37,150 --> 00:47:43,720
Men rekursjon for sortering seg selv er ganske enkelt.

577
00:47:43,720 --> 00:47:49,190
Du bare bokstavelig ringe slag på venstre halvdel, sortere på høyre halvdel. Okay.

578
00:47:51,770 --> 00:47:54,860
Alle som har noe jeg kan trekke opp ennå?

579
00:47:54,860 --> 00:47:57,540
Ellers vil jeg gi et minutt.

580
00:47:58,210 --> 00:47:59,900
Okay.

581
00:47:59,900 --> 00:48:02,970
Alle som har noe vi kan jobbe med?

582
00:48:05,450 --> 00:48:09,680
Ellers får vi bare jobbe med dette og deretter utvide derfra.

583
00:48:09,680 --> 00:48:14,050
>> Alle som har mer enn dette at jeg kan trekke opp?

584
00:48:14,050 --> 00:48:17,770
[Student] Yeah. Du kan trekke opp mine. >> Greit.

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

586
00:48:22,170 --> 00:48:25,280
[Student] Det var mange forhold. >> Å, skyte. Kan du -

587
00:48:25,280 --> 00:48:28,110
[Student] Jeg må lagre det. >> Ja.

588
00:48:32,420 --> 00:48:35,730
Så vi gjorde gjøre flettingen separat.

589
00:48:35,730 --> 00:48:38,570
Oh, men det er ikke så ille.

590
00:48:39,790 --> 00:48:41,650
Okay.

591
00:48:41,650 --> 00:48:47,080
Så slags er i seg selv bare å ringe mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Forklare oss hva mergeSortHelp gjør.

593
00:48:49,530 --> 00:48:55,700
[Student] MergeSortHelp ganske gjør mye de to hovedtrinn,

594
00:48:55,700 --> 00:49:01,270
som er å sortere hver halvdel av matrisen, og deretter å slå dem begge.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Ok, så gi meg et sekund.

596
00:49:10,850 --> 00:49:13,210
Jeg tror dette - >> [student] Jeg trenger å -

597
00:49:17,100 --> 00:49:19,400
Ja. Jeg mangler noe.

598
00:49:19,400 --> 00:49:23,100
I merge, innser jeg at jeg må opprette en ny matrise

599
00:49:23,100 --> 00:49:26,530
fordi jeg ikke kunne gjøre det på plass. >> Ja. Du kan ikke. Korrigere.

600
00:49:26,530 --> 00:49:28,170
[Student] Så jeg oppretter en ny matrise.

601
00:49:28,170 --> 00:49:31,510
Jeg glemte på slutten av fusjonerer til re-endre.

602
00:49:31,510 --> 00:49:34,490
Okay. Vi trenger en ny rekke.

603
00:49:34,490 --> 00:49:41,000
I flette slag, er dette nesten alltid sant.

604
00:49:41,000 --> 00:49:44,340
Del av kostnaden for en bedre algoritme tidsmessig

605
00:49:44,340 --> 00:49:47,310
er nesten alltid ønsker å bruke litt mer minne.

606
00:49:47,310 --> 00:49:51,570
Så her, uansett hvordan du gjør flette sortere,

607
00:49:51,570 --> 00:49:54,780
du ville uunngåelig trenger å bruke litt ekstra minne.

608
00:49:54,780 --> 00:49:58,240
Han eller hun opprettet en ny array.

609
00:49:58,240 --> 00:50:03,400
Og så sier du på slutten vi bare trenger å kopiere ny rekke i den opprinnelige matrisen.

610
00:50:03,400 --> 00:50:04,830
[Student] Jeg tror det, ja.

611
00:50:04,830 --> 00:50:08,210
Jeg vet ikke om det fungerer i forhold til å telle ved henvisning eller hva -

612
00:50:08,210 --> 00:50:11,650
Ja, det vil fungere. >> [Student] Okay.

613
00:50:20,620 --> 00:50:24,480
Visste du prøve å kjøre dette? >> [Student] Nei, ikke ennå. >> Ok.

614
00:50:24,480 --> 00:50:28,880
Prøve å kjøre den, og så skal jeg snakke om det for et sekund.

615
00:50:28,880 --> 00:50:35,200
[Student] Jeg trenger å ha alle funksjoner prototyper og alt, ikke sant?

616
00:50:37,640 --> 00:50:40,840
Funksjonstastene prototyper. Å, du mener som - Ja.

617
00:50:40,840 --> 00:50:43,040
Sorter kaller mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Så for at sortere å ringe mergeSortHelp, må mergeSortHelp enten er definert

619
00:50:47,390 --> 00:50:56,370
før sorter eller vi trenger bare en prototype. Bare kopier og lim det.

620
00:50:56,370 --> 00:50:59,490
Og på samme måte, er mergeSortHelp ringer flette,

621
00:50:59,490 --> 00:51:03,830
men flettingen ikke er definert ennå, så vi kan bare la mergeSortHelp vite

622
00:51:03,830 --> 00:51:08,700
at det er det flette kommer til å se ut, og det er det.

623
00:51:09,950 --> 00:51:15,730
Så mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Vi har et problem her hvor vi har ingen base case.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp er rekursiv, så noen rekursiv funksjon

626
00:51:38,110 --> 00:51:42,610
kommer til å trenge noen form for base case å vite når du skal stoppe rekursivt å kalle seg selv.

627
00:51:42,610 --> 00:51:45,590
Hva er vår base case kommer til å bli her? Ja.

628
00:51:45,590 --> 00:51:49,110
[Student] Hvis størrelsen er en? >> [Bowden] Ja.

629
00:51:49,110 --> 00:51:56,220
Så som vi så der, vi stoppet splitting arrays

630
00:51:56,220 --> 00:52:01,850
når vi fikk inn matriser av størrelse 1, som uunngåelig er sortert seg selv.

631
00:52:01,850 --> 00:52:09,530
Så hvis størrelsen er lik 1, vet vi matrisen er allerede sortert,

632
00:52:09,530 --> 00:52:12,970
så vi kan bare gå tilbake.

633
00:52:12,970 --> 00:52:16,880
>> Legg merke til at er ugyldig, slik at vi ikke kommer tilbake noe spesielt, vi bare tilbake.

634
00:52:16,880 --> 00:52:19,580
Okay. Så det er vår base case.

635
00:52:19,580 --> 00:52:27,440
Jeg tror vår base case kan også være hvis vi måtte være en sammenslåing en rekke størrelse 0,

636
00:52:27,440 --> 00:52:30,030
vi sannsynligvis vil stoppe på et tidspunkt,

637
00:52:30,030 --> 00:52:33,610
så vi kan bare si størrelse mindre enn 2 eller mindre enn eller lik 1

638
00:52:33,610 --> 00:52:37,150
slik at dette vil fungere for enhver matrise nå.

639
00:52:37,150 --> 00:52:38,870
Okay.

640
00:52:38,870 --> 00:52:42,740
Så det er vår base case.

641
00:52:42,740 --> 00:52:45,950
Nå trenger du ønsker å lede oss gjennom flettingen?

642
00:52:45,950 --> 00:52:49,140
Hva gjør alle disse tilfellene betyr?

643
00:52:49,140 --> 00:52:54,480
Her oppe, vi bare gjør det samme idé, -

644
00:52:56,970 --> 00:53:02,470
[Student] Jeg trenger å være bestått størrelse med alle mergeSortHelp samtaler.

645
00:53:02,470 --> 00:53:10,080
Jeg har lagt størrelse som en ekstra primære og det er ikke der, som størrelse / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, størrelse / 2, størrelse / 2. >> [Student] Ja, og også i den ovenfor fungerer så godt.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Her? >> [Student] Bare størrelse. >> [Bowden] Oh. , Størrelse? >> [Student] Yeah.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Okay.

649
00:53:23,010 --> 00:53:26,580
La meg tenke et sekund.

650
00:53:26,580 --> 00:53:28,780
Kjøre vi inn i en sak?

651
00:53:28,780 --> 00:53:33,690
Vi er alltid behandle venstre som 0. >> [Student] Nei

652
00:53:33,690 --> 00:53:36,340
Det er også galt. Unnskyld. Det bør være start. Ja.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Jeg liker det bedre.

654
00:53:39,230 --> 00:53:43,880
Og slutten. Okay.

655
00:53:43,880 --> 00:53:47,200
Så nå vil du lede oss gjennom flettingen? >> [Student] Okay.

656
00:53:47,200 --> 00:53:52,150
Jeg bare vandre gjennom denne nye utvalget som jeg har laget.

657
00:53:52,150 --> 00:53:57,420
Dens størrelse er størrelsen av den del av matrisen som vi ønsker å være sortert

658
00:53:57,420 --> 00:54:03,460
og prøver å finne elementet som jeg skal legge i det nye utvalget trinn.

659
00:54:03,460 --> 00:54:10,140
Så for å gjøre det, først skal jeg sjekke om den venstre halvdelen av tabellen fortsetter å ha noen flere elementer,

660
00:54:10,140 --> 00:54:14,260
og hvis det ikke gjør det, så du går ned til det andre tilstand, som bare sier

661
00:54:14,260 --> 00:54:20,180
okay, det må være i riktig array, og vi vil sette det i dagens indeks newArray.

662
00:54:20,180 --> 00:54:27,620
>> Og så ellers, jeg sjekke om høyre side av tabellen er også ferdig,

663
00:54:27,620 --> 00:54:30,630
i så fall bare jeg satt i venstre.

664
00:54:30,630 --> 00:54:34,180
Det kan faktisk ikke være nødvendig. Jeg er ikke sikker.

665
00:54:34,180 --> 00:54:40,970
Men uansett, de to andre sjekk hvilke av de to er mindre i venstre eller høyre.

666
00:54:40,970 --> 00:54:49,770
Og også i hvert enkelt tilfelle, jeg økes hvilken plassholder jeg øke.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Okay.

668
00:54:52,040 --> 00:54:53,840
Det ser bra ut.

669
00:54:53,840 --> 00:54:58,800
Har noen kommentarer eller bekymringer eller spørsmål?

670
00:55:00,660 --> 00:55:07,720
Så de fire sakene som vi må ta ting i bare å være - eller det ser ut som fem -

671
00:55:07,720 --> 00:55:13,100
men vi må vurdere om den venstre tabellen har gått tom for ting vi trenger å fusjonere,

672
00:55:13,100 --> 00:55:16,390
om retten utvalg har gått tom for ting vi trenger å fusjonere -

673
00:55:16,390 --> 00:55:18,400
Jeg peker på noe.

674
00:55:18,400 --> 00:55:21,730
Så om den venstre tabellen har gått tom for ting eller rett matrisen har gått tom for ting.

675
00:55:21,730 --> 00:55:24,320
De er to tilfeller.

676
00:55:24,320 --> 00:55:30,920
Vi trenger også trivielle tilfelle av hvorvidt den venstre ting er mindre enn det rette.

677
00:55:30,920 --> 00:55:33,910
Så vi ønsker å velge den venstre tingen.

678
00:55:33,910 --> 00:55:37,630
De er de tilfeller.

679
00:55:37,630 --> 00:55:40,990
Så dette var rett, så det er det.

680
00:55:40,990 --> 00:55:46,760
Array igjen. Det er 1, 2, 3. Okay. Så ja, de er de fire tingene vi kanskje vil gjøre.

681
00:55:50,350 --> 00:55:54,510
Og vi vil ikke gå over en iterativ løsning.

682
00:55:54,510 --> 00:55:55,980
Jeg vil ikke anbefale -

683
00:55:55,980 --> 00:56:03,070
Flette sorter er et eksempel på en funksjon som er både ikke hale rekursive

684
00:56:03,070 --> 00:56:07,040
det er ikke lett å gjøre det halen rekursive

685
00:56:07,040 --> 00:56:13,450
men også det er ikke veldig lett å gjøre det iterativ.

686
00:56:13,450 --> 00:56:16,910
Dette er veldig enkelt.

687
00:56:16,910 --> 00:56:19,170
Denne implementasjonen av fletting slag,

688
00:56:19,170 --> 00:56:22,140
flette, uansett hva du gjør, du kommer til å bygge flettingen.

689
00:56:22,140 --> 00:56:29,170
>> Så flette slag bygget på toppen av Merge rekursivt er bare disse tre linjene.

690
00:56:29,170 --> 00:56:34,700
Iterativt, er det mer irriterende og vanskeligere å tenke på.

691
00:56:34,700 --> 00:56:41,860
Men merker at det ikke er halen rekursive siden mergeSortHelp - når den kaller seg selv -

692
00:56:41,860 --> 00:56:46,590
det fortsatt behov for å gjøre ting etter dette rekursive kallet returnerer.

693
00:56:46,590 --> 00:56:50,830
Så denne bunken rammen må fortsette å eksistere selv etter ringer dette.

694
00:56:50,830 --> 00:56:54,170
Og så når du ringer dette må stabelen rammen fortsette å eksistere

695
00:56:54,170 --> 00:56:57,780
fordi selv etter at samtalen, vi trenger fortsatt å fusjonere.

696
00:56:57,780 --> 00:57:01,920
Og det er nontrivial å gjøre denne halen rekursiv.

697
00:57:04,070 --> 00:57:06,270
Spørsmål?

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

699
00:57:09,860 --> 00:57:13,400
Så kommer tilbake for å sortere - oh, det er to ting jeg vil vise. Okay.

700
00:57:13,400 --> 00:57:17,840
Går tilbake til å sortere, vil vi gjøre dette raskt.

701
00:57:17,840 --> 00:57:21,030
Eller søk. Slag? Sorter. Ja.

702
00:57:21,030 --> 00:57:22,730
Går tilbake til begynnelsen av slag.

703
00:57:22,730 --> 00:57:29,870
Vi ønsker å lage en algoritme som sorterer tabellen ved hjelp av en algoritme

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

705
00:57:33,660 --> 00:57:40,860
Så hvordan er dette mulig? Har noen noen form for -

706
00:57:40,860 --> 00:57:44,300
Jeg antydet før på -

707
00:57:44,300 --> 00:57:48,300
Hvis vi er i ferd med å forbedre seg n log n til O av n,

708
00:57:48,300 --> 00:57:51,450
Vi har forbedret vår algoritme tidsmessig,

709
00:57:51,450 --> 00:57:55,250
noe som betyr hva vi kommer til å trenge å gjøre for å gjøre opp for det?

710
00:57:55,250 --> 00:57:59,520
[Student] Space. >> Ja. Vi kommer til å bruke mer plass.

711
00:57:59,520 --> 00:58:04,490
Og ikke engang bare mer plass, er det eksponentielt mer plass.

712
00:58:04,490 --> 00:58:14,320
Så jeg tror denne typen algoritme er pseudo noe, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Jeg kan ikke huske. Pseudo noe.

714
00:58:18,980 --> 00:58:22,210
Men det er fordi vi trenger å bruke så mye plass

715
00:58:22,210 --> 00:58:28,610
at dette er oppnåelig, men ikke realistisk.

716
00:58:28,610 --> 00:58:31,220
>> Og hvordan oppnår vi dette?

717
00:58:31,220 --> 00:58:36,810
Vi kan oppnå dette dersom vi garantere at en bestemt element i matrisen

718
00:58:36,810 --> 00:58:39,600
er under en viss størrelse.

719
00:58:42,070 --> 00:58:44,500
Så la oss bare si at størrelsen er 200,

720
00:58:44,500 --> 00:58:48,130
noe element i en matrise er under størrelse 200.

721
00:58:48,130 --> 00:58:51,080
Og dette er faktisk veldig realistisk.

722
00:58:51,080 --> 00:58:58,660
Du kan veldig lett ha en matrise som du vet alt i det

723
00:58:58,660 --> 00:59:00,570
kommer til å være mindre enn et antall.

724
00:59:00,570 --> 00:59:07,400
Som hvis du har noen helt enormt vektor eller noe

725
00:59:07,400 --> 00:59:11,810
men du vet alt kommer til å være mellom 0 og 5,

726
00:59:11,810 --> 00:59:14,790
så det kommer til å være betydelig raskere å gjøre dette.

727
00:59:14,790 --> 00:59:17,930
Og den bundne på noen av elementene er 5,

728
00:59:17,930 --> 00:59:21,980
så dette bundet, som er hvor mye minne du skal bruke.

729
00:59:21,980 --> 00:59:26,300
Så det bundne er 200.

730
00:59:26,300 --> 00:59:32,960
I teorien er det alltid en bundet siden et heltall kan bare være opp til 4 milliarder kroner,

731
00:59:32,960 --> 00:59:40,600
men det er urealistisk siden da vi skulle bruke plass

732
00:59:40,600 --> 00:59:44,400
i størrelsesorden 4 milliarder kroner. Så det er urealistisk.

733
00:59:44,400 --> 00:59:47,060
Men her vil vi si vår grense er 200.

734
00:59:47,060 --> 00:59:59,570
Kunsten å gjøre det i O av n er vi foreta en ny array kalt tellinger av størrelse BUNDET.

735
00:59:59,570 --> 01:00:10,470
Så egentlig er dette en snarvei for - jeg faktisk ikke vet om Clang gjør dette.

736
01:00:11,150 --> 01:00:15,330
Men i GCC i det minste - jeg antar Clang gjør det også -

737
01:00:15,330 --> 01:00:18,180
Dette vil bare starte hele array å være 0s.

738
01:00:18,180 --> 01:00:25,320
Så hvis jeg ikke ønsker å gjøre det, så jeg kunne separat gjøre for (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <BOUND; i + +) og teller [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Så nå er alt initialisert til 0.

741
01:00:35,260 --> 01:00:39,570
Jeg iterere over matrise min,

742
01:00:39,570 --> 01:00:51,920
og hva jeg gjør er jeg telle antall av hver - La oss gå ned her.

743
01:00:51,920 --> 01:00:55,480
Vi har fire, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Hva jeg regnet er antall forekomster av hvert av disse elementene.

745
01:01:00,010 --> 01:01:03,470
La oss faktisk legge til et par mer her med noen gjentakelser.

746
01:01:03,470 --> 01:01:11,070
Så verdien vi har her, er verdien av det kommer til å være array [i].

747
01:01:11,070 --> 01:01:14,850
Så val kan være 4 eller 8 eller hva.

748
01:01:14,850 --> 01:01:18,870
Og nå er jeg telle hvor mange av den verdien jeg har sett,

749
01:01:18,870 --> 01:01:21,230
så teller [val] + +;

750
01:01:21,230 --> 01:01:29,430
Når dette er gjort, er teller kommer til å se noe sånt 0001.

751
01:01:29,430 --> 01:01:42,190
La oss gjøre teller [val] - BUNDET + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nå det er bare å ta hensyn til det faktum at vi starter fra 0.

753
01:01:48,230 --> 01:01:50,850
Så hvis 200 kommer til å være vår største nummeret,

754
01:01:50,850 --> 01:01:54,720
deretter 0-200 er 201 ting.

755
01:01:54,720 --> 01:02:01,540
Så teller, vil det se ut som 00001 fordi vi har en 4.

756
01:02:01,540 --> 01:02:10,210
Da vil vi ha 0001 der vi har en 1 i 8. indeksen teller.

757
01:02:10,210 --> 01:02:14,560
Vi har en 2 i det 23. indeksen teller.

758
01:02:14,560 --> 01:02:17,630
Vi har en 2 i den 42. indeksen teller.

759
01:02:17,630 --> 01:02:21,670
Så vi kan bruke teller.

760
01:02:34,270 --> 01:02:44,920
Så num_of_item = teller [i].

761
01:02:44,920 --> 01:02:52,540
Og så hvis num_of_item er 2, det betyr at vi ønsker å sette to av antall i

762
01:02:52,540 --> 01:02:55,290
i vår sortert array.

763
01:02:55,290 --> 01:03:02,000
Så vi trenger å holde styr på hvor langt vi er inn i matrisen.

764
01:03:02,000 --> 01:03:05,470
Så indeks = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Jeg vil bare skrive det.

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

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
Er det det jeg vil? Jeg tror det er det jeg vil.

769
01:03:35,100 --> 01:03:38,290
Ja, dette ser bra. Okay.

770
01:03:38,290 --> 01:03:43,050
Så forstår alle hva hensikten med mitt teller matrise er?

771
01:03:43,050 --> 01:03:48,140
Det er å telle antallet forekomster av hvert av disse tallene.

772
01:03:48,140 --> 01:03:51,780
Så jeg gjentar over det teller array,

773
01:03:51,780 --> 01:03:57,190
og i-te posisjonen i teller matrisen

774
01:03:57,190 --> 01:04:01,930
er antall jeg er som skal vises i min sorteres array.

775
01:04:01,930 --> 01:04:06,840
Det er derfor tellinger av 4 kommer til å bli en

776
01:04:06,840 --> 01:04:11,840
og tellinger av 8 kommer til å bli 1, tellinger av 23 kommer til å være to.

777
01:04:11,840 --> 01:04:16,900
Så det er hvor mange av dem jeg ønsker å sette inn i min sortert array.

778
01:04:16,900 --> 01:04:19,200
Så jeg bare gjøre det.

779
01:04:19,200 --> 01:04:28,960
Jeg setter num_of_item jeg er i min sortert array.

780
01:04:28,960 --> 01:04:31,670
>> Spørsmål?

781
01:04:32,460 --> 01:04:43,100
Og så igjen, dette er lineær tid siden vi bare gjentar over denne gang,

782
01:04:43,100 --> 01:04:47,470
men det er også lineær i hva dette nummeret skjer for å være,

783
01:04:47,470 --> 01:04:50,730
og så det er svært avhengig av hva din grense er.

784
01:04:50,730 --> 01:04:53,290
Med en bundet på 200, er det ikke så ille.

785
01:04:53,290 --> 01:04:58,330
Hvis du utvilsomt kommer til å bli 10.000, så det er litt verre,

786
01:04:58,330 --> 01:05:01,360
men hvis du utvilsomt kommer til å være 4 milliarder kroner, som er helt urealistisk

787
01:05:01,360 --> 01:05:07,720
og denne matrisen er nødt til å være av størrelse 4 milliarder kroner, noe som er urealistisk.

788
01:05:07,720 --> 01:05:10,860
Så det er det. Spørsmål?

789
01:05:10,860 --> 01:05:13,270
[Uhørlig student respons] >> Ok.

790
01:05:13,270 --> 01:05:15,710
Jeg innså en annen ting når vi skulle gjennom.

791
01:05:17,980 --> 01:05:23,720
Jeg tror problemet var i Lucas 'og trolig hver eneste vi har sett.

792
01:05:23,720 --> 01:05:26,330
Jeg glemte helt.

793
01:05:26,330 --> 01:05:31,040
Det eneste jeg ønsket å kommentere er at når du arbeider med ting som indekser,

794
01:05:31,040 --> 01:05:38,320
du aldri virkelig se dette når du skriver en for løkke,

795
01:05:38,320 --> 01:05:41,120
men teknisk, når du arbeider med disse indeksene,

796
01:05:41,120 --> 01:05:45,950
du bør stort sett alltid forholde seg til usignerte heltall.

797
01:05:45,950 --> 01:05:53,850
Grunnen til dette er når du arbeider med signerte heltall,

798
01:05:53,850 --> 01:05:56,090
så hvis du har 2 signert heltall og du legger dem sammen

799
01:05:56,090 --> 01:06:00,640
og de ender opp for stor, så du ender opp med et negativt tall.

800
01:06:00,640 --> 01:06:03,410
Så det er hva heltallsoverflyt er.

801
01:06:03,410 --> 01:06:10,500
>> Hvis jeg legger 2 milliarder og 1 milliard, ender jeg opp med negativ 1 milliard.

802
01:06:10,500 --> 01:06:15,480
Det er hvordan heltall arbeider på datamaskiner.

803
01:06:15,480 --> 01:06:17,510
Så problemet med å bruke -

804
01:06:17,510 --> 01:06:23,500
Det er fint bortsett fra hvis lav skjer for å være 2 milliarder og opp skjer for å være 1 milliard,

805
01:06:23,500 --> 01:06:27,120
så dette kommer til å være negativ 1 milliard og deretter skal vi dele det med 2

806
01:06:27,120 --> 01:06:29,730
og ender opp med negativ 500 millioner.

807
01:06:29,730 --> 01:06:33,760
Så dette er bare et problem hvis du tilfeldigvis være å søke gjennom en rekke

808
01:06:33,760 --> 01:06:38,070
milliarder av ting.

809
01:06:38,070 --> 01:06:44,050
Men hvis lav + opp skjer med overløp, så det er et problem.

810
01:06:44,050 --> 01:06:47,750
Så snart vi gjør dem usignert, deretter 2 milliarder pluss 1 milliard er 3 milliarder kroner.

811
01:06:47,750 --> 01:06:51,960
3000000000 delt på 2 er 1,5 milliarder kroner.

812
01:06:51,960 --> 01:06:55,670
Så så snart de er usignerte, alt er perfekt.

813
01:06:55,670 --> 01:06:59,900
Og så det er også et problem når du skriver din for looper,

814
01:06:59,900 --> 01:07:03,940
og faktisk, det sannsynligvis det automatisk.

815
01:07:09,130 --> 01:07:12,330
Det vil faktisk bare kjefte på deg.

816
01:07:12,330 --> 01:07:21,610
Så hvis dette tallet er for stor til å være i akkurat et heltall, men det ville passe i en usignert heltall,

817
01:07:21,610 --> 01:07:24,970
det vil kjefte på deg, så det er derfor du aldri virkelig kjøre inn i saken.

818
01:07:29,150 --> 01:07:34,820
Du kan se at en indeks aldri kommer til å være negativ,

819
01:07:34,820 --> 01:07:39,220
og så når du gjentar i en matrise,

820
01:07:39,220 --> 01:07:43,970
du kan nesten alltid si usignert int i, men du egentlig ikke må.

821
01:07:43,970 --> 01:07:47,110
Ting kommer til å jobbe ganske mye like bra.

822
01:07:48,740 --> 01:07:50,090
Okay. [Hvisker] Hva er klokka?

823
01:07:50,090 --> 01:07:54,020
Den siste tingen jeg ønsket å vise - og jeg vil bare gjøre det virkelig rask.

824
01:07:54,020 --> 01:08:03,190
Du vet hvordan vi har # define slik at vi kan # define MAX som 5 eller noe?

825
01:08:03,190 --> 01:08:05,940
La oss ikke gjøre MAX. # Define BUNDET som 200. Det er hva vi gjorde før.

826
01:08:05,940 --> 01:08:10,380
Som definerer en konstant, som bare kommer til å bli kopiert og limt inn

827
01:08:10,380 --> 01:08:13,010
uansett hvor vi måtte skrive bundet.

828
01:08:13,010 --> 01:08:18,189
>> Så vi kan faktisk gjøre mer med # definerer.

829
01:08:18,189 --> 01:08:21,170
Vi kan # definere funksjoner.

830
01:08:21,170 --> 01:08:23,410
De er egentlig ikke fungerer, men vi vil kalle dem funksjoner.

831
01:08:23,410 --> 01:08:36,000
Et eksempel kan være noe sånt som MAX (x, y) er definert som (x <y y: x). Okay.

832
01:08:36,000 --> 01:08:40,660
Så du bør bli vant til trefoldig operatør syntaks,

833
01:08:40,660 --> 01:08:49,029
men er x mindre enn y? Returnere y, ellers returnere x.

834
01:08:49,029 --> 01:08:54,390
Så du kan se at du kan gjøre dette til en egen funksjon,

835
01:08:54,390 --> 01:09:01,399
og funksjonen kan være som bool MAX tar 2 argumenter, må du returnere.

836
01:09:01,399 --> 01:09:08,340
Dette er en av de vanligste jeg ser gjort som dette. Vi kaller dem makroer.

837
01:09:08,340 --> 01:09:11,790
Dette er en makro.

838
01:09:11,790 --> 01:09:15,859
Dette er bare syntaksen for det.

839
01:09:15,859 --> 01:09:18,740
Du kan skrive en makro til å gjøre hva du vil.

840
01:09:18,740 --> 01:09:22,649
Du ofte se makroer for debugging printfs og sånt.

841
01:09:22,649 --> 01:09:29,410
Så en type printf, det er spesielle konstanter i C som understreker LINE understrekning,

842
01:09:29,410 --> 01:09:31,710
2 understreker LINE understrek,

843
01:09:31,710 --> 01:09:37,550
og det er også jeg tror 2 understreker FUNC. Det kan være det. Noe sånt.

844
01:09:37,550 --> 01:09:40,880
Disse tingene vil bli erstattet med navnet på funksjonen

845
01:09:40,880 --> 01:09:42,930
eller antall av linjen som du er på.

846
01:09:42,930 --> 01:09:48,630
Ofte skriver du debugging printfs det ned her kunne jeg da bare skrive

847
01:09:48,630 --> 01:09:54,260
Feilsøke og det vil skrive ut linjenummer og funksjon som jeg måtte være i

848
01:09:54,260 --> 01:09:57,020
at det møtt som DEBUG uttalelse.

849
01:09:57,020 --> 01:09:59,550
Og du kan også skrive ut andre ting.

850
01:09:59,550 --> 01:10:05,990
Så én ting du bør se opp for er hvis jeg tilfeldigvis # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
som noe som 2 * y og 2 * x.

852
01:10:11,380 --> 01:10:14,310
Så uansett grunn, skje du å gjøre det mye.

853
01:10:14,310 --> 01:10:16,650
Så gjør det en makro.

854
01:10:16,650 --> 01:10:18,680
Dette er faktisk brutt.

855
01:10:18,680 --> 01:10:23,050
Jeg vil kalle det ved å gjøre noe som DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Så hva skal returneres?

857
01:10:28,840 --> 01:10:30,580
[Student] 12.

858
01:10:30,580 --> 01:10:34,800
Ja, bør 12 returneres, og 12 er returnert.

859
01:10:34,800 --> 01:10:43,350
3 blir erstattet for x, blir seks erstattet for y, og vi kommer tilbake 2 * 6, som er 12 år.

860
01:10:43,350 --> 01:10:47,710
Hva nå om dette? Hva skal returneres?

861
01:10:47,710 --> 01:10:50,330
[Student] 14. >> Ideelt sett 14.

862
01:10:50,330 --> 01:10:55,290
Problemet er at hvordan hasj definerer arbeid, husk det er en bokstavelig kopiere og lime

863
01:10:55,290 --> 01:11:00,160
på stort sett alt, så hva dette kommer til å bli tolket som

864
01:11:00,160 --> 01:11:11,270
er 3 mindre enn 1 pluss 6, 2 ganger 1 pluss 6, 2 ganger 3.

865
01:11:11,270 --> 01:11:19,780
>> Så på grunn av dette nesten alltid du bryte alt i parentes.

866
01:11:22,180 --> 01:11:25,050
Enhver variabel du nesten alltid bryte i parentes.

867
01:11:25,050 --> 01:11:29,570
Det er tilfeller der du ikke trenger å, som jeg vet at jeg ikke trenger å gjøre det her

868
01:11:29,570 --> 01:11:32,110
fordi mindre enn det som er stort sett alltid bare kommer til å fungere,

869
01:11:32,110 --> 01:11:34,330
selv om det kanskje ikke engang være sant.

870
01:11:34,330 --> 01:11:41,870
Hvis det er noe latterlig som DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
så det kommer til å bli erstattet med tre mindre enn 1 er lik lik 2,

872
01:11:49,760 --> 01:11:53,460
og så så det kommer til å gjøre 3 mindre enn 1, betyr det lik 2,

873
01:11:53,460 --> 01:11:55,620
som er ikke hva vi ønsker.

874
01:11:55,620 --> 01:12:00,730
Så for å unngå eventuelle operatorpresedens problemer,

875
01:12:00,730 --> 01:12:02,870
alltid brytes i parentes.

876
01:12:03,290 --> 01:12:07,700
Okay. Og det er det, 5:30.

877
01:12:08,140 --> 01:12:12,470
Hvis du har noen spørsmål om pset, gi oss beskjed.

878
01:12:12,470 --> 01:12:18,010
Det skal være moro, og hackeren utgaven også er mye mer realistisk

879
01:12:18,010 --> 01:12:22,980
enn hacker utgave av fjorårets, så vi håper at mange av dere prøver.

880
01:12:22,980 --> 01:12:26,460
Fjorårets var veldig overveldende.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]